Monday, January 3, 2011

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 :

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



3 comments:

  1. Hello! Thanks for a very interesting program & these tutorials. I'm currently trying to implement a simple removing of perspective distortion using four points correspondences. I do it using the code from the book you mentioned in this article, but seems like I'm getting stuck with it: the process of transforming an image using PixelInterpolator class is very slow on android & when I try to use android's Matrix class I get very strange results even if I use setPolyToPoly method. Could you please share a piece of code that you use to correct image perspective on android?

    Thanks,
    Alexander

    ReplyDelete
  2. Hi!

    A piece of code is now presented.

    I hope it helps.

    Bonne journée!

    ReplyDelete
  3. Thank you very much for the great explanation! And again thanks for the awesome application!

    Thanks,
    Alexander

    ReplyDelete