Step 4 : Find grid

Process to find grid and numbers :

Now, we must find the 4 corners of the grid. There are 2 steps :

1. find all the possible straight lines in the grid
2. find the 4 corners with the intersection of the 4 farthest straight lines

To find all the possible straight lines in the grid, we use the well known Hough transform algorithm .

Here is the equation of a straight line in Hessian normal form :

      r = x . cos(θ) + y . sin(θ)

For each point (x, y) in our array obtained in the preceding step, we vary θ  from 0 to 180 to get r. And, (θ,r) becomes the coordinates of a new array named accumulator.

A thoroughly understandable explanation of this algorithm is given in . . . Burger and Burge's marvellous book again,  in chapter 9 on page 155.

Do you want to see some lines of Java code for this algorithm? Why not? Check chapter 9 just here :
Chapter 9 Detecting Simple Curves

You can also find some useful short and visual  explanations of the algorithm here :
Hough Transform in Wikipedia

Now, let us try to find the 4 corners. How do we do that? First, we find the leftmost, rightmost, topmost and bottommost lines in the accumulator array. With the intersection of each of these 4 fines, we find the 4 corners. Is it not that easy? In the Burger and Burge's marvellous book, there is a section which title is "Analyzing the Accumulator Array" on page 163 which does just what we want. What a great book!

Here a brief analysis of Hough transform algorithm :
Advantages :

• easy to program
• find the grid even if the shape of the Sudoku is not straight
• find grid even if we do not have any of the 4 corners in the photo

Disavantages :

• poor performance because there are too many calculations and iterations

To improve the performance of the algorithm, we use 3 techniques :

1. cos(θ) and sin(θ) are put in cache because we need them in many calculations
2. we vary θ from 0 to 180 by 4; it is enough to find the grid
3. we take (x,y) in the original array at each 5 points; it is enough to find the grid

On Nexus One with Android 2.2, it takes 0.08 second to process this step 4. Finally, the performance is not so bad.

  Display :

In the screen shots of the same photos, we see the 4 straight lines in green and also the 4 corners in red . . . when there is a corner on the photo :