Step 5 : Perspective transformation

Process to find grid and numbers

Often, the grid is distorted and it is almost impossible to find numbers if the grid is not square. We need a way to map a distorted grid to a square grid. The miraculous way is to use perspective transformation also called projective mapping or 2D mapping. So, we want to transform the surrounded green grid at left toward the grid at right :

To use perspective transformation, there is a method named setPolyToPoly in Android Matrix class. But, sometimes, part of the corners of the grid are lost and, consequently, some numbers can be lost. So,  we decided to write our own pure Java code to do the perspective transformation.

But, where can we find all the information we needed to do that? For sure, now, you know the answer . . . in the Burger and Burge's marvellous book . . . of course. This is very clearly explained in chapter 16 page 380. It is named projective mapping in the book. As usual, you could find Java code here :

Chapter 16 Geometric Operations

You can find also a piece of Java code below.

Display

In the screen shots of the same 4 photos, we see the perspective transformations. Note the fourth one where we did not have the 4 corners in the original photo :

Java code

Here are the elements presented :

1. The image to analyze

2. A sample of source image in Excel : image1

3. A sample of target image in Excel : image2

4. Global variables to set before calling the perspective transformation function

5. Perspective transformation function not optimized but running fine

6. Perspective transformation function optimized and running fine

7. How to log image1 and image2 and import them in Excel

I hope it helps!

      

      

1. The image to analyze

2. A sample of source image in Excel : image1

3. A sample of target image in Excel : image2 

      

4. Global variables to set before calling the perspective transformation function

// SOURCE * * * * :          

// image1 : source image

// largueur : width  always set to 512 for my application

// hauteur : height always set to 512 for my application

// (x1p,y1p), (x2p,y2p), (x3p,y3p), (x4p,y4p) :

//              the coordinates of the 4 corners of the grid in the source image

// for the example image :

// x1p = -3.0, y1p = 157.0, x2p = 431.0, y2p = 49.0, x3p = 488.0, y3p = 450.0, x4p = 97.0, y4p = 505.0

// each cell contains 0 (black) or 1 (white)

// TARGET * * * * :

// image2 : target image

// sudoku_dim : width and height always set to 486 for my application

// each cell contains 0 (black) or 1 (white)

// SOURCE * * * * :

int largueur = 512;

int hauteur = 512;

short image1[][] = new short [hauteur][largueur]; // to set

double x1p, x2p, x3p, x4p, y1p, y2p, y3p, y4p; // to set

// TARGET * * * * :

int sudoku_dim = 486;

short image2[][] = new short [sudoku_dim][sudoku_dim];

5. Perspective transformation function not optimized but running fine

public void travaille_5_perspective_transformer_not_optimized() {

      

// There are many multiplications in the loop

// Average response time after many runs of 100 calls :

// 0,06 second on Samsung Galaxy S III : Dual core, 1500 MHz, Snapdragon S4 Krait, 2048 MB RAM with Android 4.0.4

// 0,21 second on Google Nexus S with Android 4.1.1

// 0,12 second on Google Nexus One with Android 2.3.4

      

       int x, y; // x, y on page 380

       int xp, yp; // x prime, y prime on page 380

        

       double a11, a12, a13, a21, a22, a23, a31, a32, a33; // on page 383

     

       // formula 16.28 on page 383

       a31 = ((x1p-x2p+x3p-x4p)*(y4p-y3p)-(y1p-y2p+y3p-y4p)*(x4p-x3p))/((x2p-x3p)*(y4p-y3p)-(x4p-x3p)*(y2p-y3p));

    

       // formula 16.29 on page 383

       a32 = ((y1p-y2p+y3p-y4p)*(x2p-x3p)-(x1p-x2p+x3p-x4p)*(y2p-y3p))/((x2p-x3p)*(y4p-y3p)-(x4p-x3p)*(y2p-y3p));

    

       // formula 16.17 on page 380

       a33 = 1;

    

       // formula 16.30 on page 383

       a11 = x2p-x1p+a31*x2p;

       a12 = x4p-x1p+a32*x4p;

       a13 = x1p;

    

       // formula 16.31 on page 383

       a21 = y2p-y1p+a31*y2p;

       a22 = y4p-y1p+a32*y4p;

       a23 = y1p;

       // Projective mapping via the unit square on page 382 : unit square to image2 dimension

       a31 = a31 / sudoku_dim;

       a32 = a32 / sudoku_dim;

       a11 = a11 / sudoku_dim;

       a12 = a12 / sudoku_dim;

       a21 = a21 / sudoku_dim;

       a22 = a22 / sudoku_dim;

        

       // for each point (x, y) in image2,

       //      we calculate (xp, yp) in image1 using formula 16.18 and 16.19 on page 380

       // the formulas are the ones presented in the book

           

       for (y = 0; y < sudoku_dim; y++)

           for (x = 0; x < sudoku_dim; x++) {

                

                xp = (int) ((a11*x +a12*y + a13) / (a31*x + a32*y + 1)); // formula 16.18 on page 380

                yp = (int) ((a21*x +a22*y + a23) / (a31*x + a32*y + 1)); // formula 16.19 on page 380

                

                if (yp >= 0 && yp < hauteur && xp >= 0 && xp < largueur)

                       image2[y][x] = image1[yp][xp];

                else

                       image2[y][x] = 0;

             

           }

    

}

6. Perspective transformation function optimized and running fine

public void travaille_5_perspective_transformer_optimized() {

      

 // Multiplications replaced by additions in the loop

 // Average response time after many runs of 100 calls :     

 // 0,03 second on Samsung Galaxy S III : Dual core, 1500 MHz, Snapdragon S4 Krait, 2048 MB RAM with Android 4.0.4

 // 0,10 second on Google Nexus S with Android 4.1.1

 // 0,07 second on Google Nexus One with Android 2.3.4

            

       int x, y; // x, y on page 380

       int xp, yp; // x prime, y prime on page 380

        

       double a11, a12, a13, a21, a22, a23, a31, a32, a33; // on page 383

   

       double numerateur_x = 0; // to improve performance

       double numerateur_y = 0; // to improve performance

       double denominateur = 0; // to improve performance  

        

       double numerateur_x_i = 0; // to improve performance

       double numerateur_y_i = 0; // to improve performance

       double denominateur_i = 0; // to improve performance  

               

       short la_ligne []; // to improve performance

     

       // formula 16.28 on page 383

       a31 = ((x1p-x2p+x3p-x4p)*(y4p-y3p)-(y1p-y2p+y3p-y4p)*(x4p-x3p))/((x2p-x3p)*(y4p-y3p)-(x4p-x3p)*(y2p-y3p));

    

       // formula 16.29 on page 383

       a32 = ((y1p-y2p+y3p-y4p)*(x2p-x3p)-(x1p-x2p+x3p-x4p)*(y2p-y3p))/((x2p-x3p)*(y4p-y3p)-(x4p-x3p)*(y2p-y3p));

    

       // formula 16.17 on page 380

       a33 = 1;

    

       // formula 16.30 on page 383

       a11 = x2p-x1p+a31*x2p;

       a12 = x4p-x1p+a32*x4p;

       a13 = x1p;

    

       // formula 16.31 on page 383

       a21 = y2p-y1p+a31*y2p;

       a22 = y4p-y1p+a32*y4p;

       a23 = y1p;

       // Projective mapping via the unit square on page 382 : unit square to image2 dimension

       a31 = a31 / sudoku_dim;

       a32 = a32 / sudoku_dim;

       a11 = a11 / sudoku_dim;

       a12 = a12 / sudoku_dim;

       a21 = a21 / sudoku_dim;

       a22 = a22 / sudoku_dim;

       

       // for each point (x, y) in image2,

       //      we calculate (xp, yp) in image1 using formula 16.18 and 16.19 on page 380

       // the formulas are transformed a bit to improve performance by avoiding many multiplications

    

       numerateur_x_i = a13;

       numerateur_y_i = a23;

       denominateur_i = a33;

          

       for (y = 0; y < sudoku_dim; y++) {

        

             numerateur_x = numerateur_x_i;

             numerateur_y = numerateur_y_i;

             denominateur = denominateur_i;

               

             la_ligne = image2[y]; // to improve performance

             for (x = 0; x < sudoku_dim; x++) {

                    xp = (int) (numerateur_x/denominateur + 0.5); // formula 16.18 on page 380

                    yp = (int) (numerateur_y/denominateur + 0.5); // formula 16.19 on page 380

                    if (yp >= 0 && yp < hauteur && xp >= 0 && xp < largueur)

                           la_ligne[x] = image1[yp][xp];

                    else

                           la_ligne[x] = 0;

             

                    numerateur_x += a11;

                    numerateur_y += a21;

                    denominateur += a31;

             }

        

             numerateur_x_i += a12;

             numerateur_y_i += a22;

             denominateur_i += a32;

               

       }

          

}     

7. How to log image1 and image2 and import them to Excel

7.1 Place this example code for image1 at the end of the optimized or not optimized function

      

       int i, j;

       String ligne;

       ligne = ", ";

       for (j = 0; j < image1[0].length; j++)

             ligne = ligne + "," + j;

       Log.i("Entete", ligne);

       for (i = 0 ; i < image1.length; i++) {

             ligne = "," + i;

            

             for (j = 0; j < image1[0].length; j++)

                    ligne = ligne + "," + image1[i][j];

                   

             Log.i("Ligne " + i, ligne);                   

       }    

    

7.2 Copy log and paste it in Excel

7.3 Select column A and use Data->Text to columns in Excel using comma as delimiter

7.4 Delete column A