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 :

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