Image Deskew

A good OCR (Optical Character Recognition) software would rely on a good number of algorithms. One of the crucial parts is to deskew the given text before it is recognized. The input image is mostly probably from a scanner where the operator does not always ensure that the text is in the correct direction. You will need to devise an algorithm to detect the skew angle of the given image.

To be more realistic for the time frame given to work on the solution, a series of constraints are guaranteed:
Ø The original image is at least 512 pixels in width and height.
Ø Each pixel is either black or white (black for the text and white for the background).
Ø The image would contain at least 15 lines of text, in either English or Chinese. The image will have enough information in order for the skew angle to be calculated.
Ø The skew angle will be from -45 degrees to 45 degrees (inclusive).

Input Description

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.

The first line contains two integers separated by a single space W and H (512 <= W, H <= 1,024), which are the width and height of the input image (in pixels). The following H lines contain W / 4 characters each, which are the hex representation of the image data. The left most pixel is the most significant bit of the hex string. It is guaranteed that W will be a multiple of 4.

Output Description

Results should be directed to standard output. Start each case with “Case #:” on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

For each case, output in a line a single integer from in range of -45 to 45, which is the skew angle. Judge’s test cases are carefully designed to have integer outputs only, so you do not have to worry about rounding errors.

Sample Input

Samples (input and respective images) are included as attachments.

Sample Output

Case 1:
-45

Case 2:
45