Step 3 : Flood fill

Process to find grid and numbers

We have to find the grid in the binary image (black and white image). A very simple way to do that is to use an algorithm for region marking using flood filling. It is amazing how it takes so few lines of Java code to find the largest region which is, by the way, the grid.

You could see the Java code beginning in chapter 11 on page 199 of Burger and Burge's marvellous book. There are 3 versions of pure Java code  in the book :

• Recursive version
• Depth-First version : we use this version
• Breadth-First version

You can see the Java code of chapter 11 here :
Java code of chapter 11 to find regions in binary images

Again, really a great book!

We will execute the same algorithm to find the numbers later.

You can find a piece of pseudo-code below.

Display

Here are the screen shots of the same photos we get after flood filling :

Pseudo-code

The definition of I is the same as the one on page 200.

Here is the pseudo-code to label all the regions and to identify the largest one:

label = 2 
label_ max = 0  // to keep the label of the largest region

masse_max = 0 // to help to identify the largest region

// label all the regions

for each (x, y) of I

             if (I(x,y) == 1)

                         masse = 0

                         floodfill(x, y)

                         if (masse > masse_max)

                                      masse_max = masse

                                      label_ max = label  // keep the label of the largest region

                         label++

// identify the largest region with 1 and all the others regions with 0

for each (x, y) of I

             if I(x,y) == label_max

                          I(x,y) = 1

             else

                          I(x,y) = 0

Here is the pseudo-code for floodfill(x,y) : depth-first version is used

// We do not use object to improve performance

pile[2][100000]       // this is the array representing the stack

// We use pile[2][100000] instead of pile[100000][2] to use less memory :

//   memory taken by pile[2][100000] = 2 * 16 + 2 * 100000 * 4 = 800 032 bytes

//   memory taken by pile[100000][2] = 100000 * 16 + 2 * 100000 * 4 = 2 400 000 bytes
// where 16 is the typical overhead for each line of the array

                     

pile[0][0] = x                    

pile[1][0] = y

pile_i = 1

pile_n = pile[0].length

// width is width of I : it is 512 for the application
// height is height of I : it is 512 for the application

while (pile_i != 0)

             pile_i--

             x = pile[0][pile_i]

             y = pile[1][pile_i]

             if (I[x][y] == 1)

                         I[x][y] = label

                         masse++

                         if (x + 1 < width && I[x + 1][y] == 1) {

                                      pile[0][pile_i] = x + 1

                                      pile[1][pile_i] = y

                                      pile_i++

                                      if (pile_i >= pile_n)

                                               return

                         }

                         if (y + 1 < height && I[x][y + 1] == 1) {

                                      pile[0][pile_i] = x

                                      pile[1][pile_i] = y + 1

                                      pile_i++

                                      if (pile_i >= pile_n)

                                               return

                         }

                         if (y - 1 >= 0 && I[x][y - 1] == 1) {

                                      pile[0][pile_i] = x

                                      pile[1][pile_i] = y - 1

                                      pile_i++

                                      if (pile_i >= pile_n)

                                               return

                         }

                         if (x - 1 >= 0 && I[x - 1][y] == 1) {

                                      pile[0][pile_i] = x - 1

                                      pile[1][pile_i] = y

                                      pile_i++

                                      if (pile_i >= pile_n)

                                               return

                         }

                         if (x - 1 >= 0 && y - 1 >= 0 && I[x - 1][y - 1] == 1) {

                                      pile[0][pile_i] = x - 1

                                      pile[1][pile_i] = y - 1

                                      pile_i++

                                      if (pile_i >= pile_n)

                                               return

                         }

                         if (x + 1 < width && y - 1 >= 0 && I[x + 1][y - 1] == 1) {

                                      pile[0][pile_i] = x + 1

                                      pile[1][pile_i] = y - 1

                                      pile_i++

                                      if (pile_i >= pile_n)

                                               return

                         }

                         if (x - 1 >= 0 && y + 1 < height && I[x - 1][y + 1] == 1) {

                                      pile[0][pile_i] = x - 1

                                      pile[1][pile_i] = y + 1

                                      pile_i++

                                      if (pile_i >= pile_n)

                                               return

                         }

                         if (x + 1 < width && y + 1 < height && I[x + 1][y + 1] == 1) {

                                      pile[0][pile_i] = x + 1

                                      pile[1][pile_i] = y + 1

                                      pile_i++

                                      if (pile_i >= pile_n)

                                               return

                         }

I hope it helps.