Step 6 : Find numbers and show them on the grid

Process to find grid and numbers

We found the grid and this grid is now square. The objective of step 6 is to find the numbers. They are 3 steps to do this :

1. find the 81 squares
2. find and isolate the number in a square
3. recognize the number in a square

As we have the coordinates of the 4 corners, it is now quite simple to calculate the coordinates of the 81 squares of the Sudoku. We just have to divide the width by 9 and the height by 9.

To find and isolate the number in a square, we use 2 techniques :

1. remove isolated pixel (it is what we call pac-man transformation)
2. famous flood fill

The pac-man transformation comes from the old Pac-Man game. In the square, we first remove all the isolated 1 sticked at a region. And with the useful flood fill technique, we find the largest region which is, by the way, the number. Here is an example for the number 8  :

To recognize the number, there area huge number of techniques. We tested many of them. One we have not yet tested is neural network. We will probably use it in a next version of our application. For now, we use our own technique based on the shape of the number.  And the technique is based again on the fabulous floodfill algorithm.

So, to recognize the number, we still apply the same useful flood fill technique like this:

• flood fill upper left region with 2
• flood fill  lower left region with 3
• flood fill  upper right region with 4
• flood fill  lower right region with 5
• flood fill  all the others regions (holes) with 6 and over
• do not flood fill the first line, the last line, the first column and the last column

We obtain this for the number 8 :

Next, we define a threshold which depends on the height of the number. When :

• the largest region in the upper left < threshold
• the largest region in the lower left < threshold
• the largest region in the upper right < threshold
• the largest region in the lower right < threshold
• the next largest region in the upper part of the number >= threshold
• the next largest region in the lower part of the number >= threshold

we recognize the number 8.

Here is another example. When :

• the largest region in the upper left < threshold
• the largest region in the lower left >= threshold
• the largest region in the upper right >= threshold
• the largest region in the lower right < threshold

we recognize the number 5.

Here are some characteristics of our technique :

1. it is very easy to understand
2. it is very simple to program
3. it is very fast
4. it is almost completly independent of the usual font used in Sudoku grid (we choose a different font for each photo presented below)
5. the recognition rate is quite good

But, we think the recognition rate of the neural network algorithm is probably better. We will test it in a next version.

Now, what do we do to find numbers at any angle from 0° to 360°? Here is the pseudo-code :

Find numbers

If there is 0 number

                Rotate 90°

                Find numbers

                If there are duplicate numbers in lines, columns or grids 3X3

                               Rotate 270°

                               Find numbers

                               If number of duplicate numbers at 90° < number of duplicate numbers at 270°

                                               Give numbers at 90°

                               Else

                                               Give numbers at 270°

                Else

                               Give numbers at 90°

Else

If there are duplicate numbers in lines, columns or grids 3X3

                Rotate 180°

                Find numbers

                If number of duplicate numbers at 0° < number of duplicate numbers at 180°

                               Give number at 0°
                Else

                               Give numbers at 180°

                Else

                               Give numbers at 0°

It is that simple!

By the way, all numbers and letters have normally a height larger than the width. When we find a number where the width is larger than the height, we consider it is not a number. That is why we can have the condition "If there is 0 number".

  

Display

As you certainly remember, we started a thread in step 1 to find the grid and the numbers. So, before we display the next screen, we have to wait for the thread to be finished.

In the screen shots of the same photos, we now see the numbers :

There are 2 steps for demo 5 :

There are 3 steps for demo 6; in step 1, we find 0 number :