# Augmented Reality Transformation Matrix Optimization

i am a software developer, i'm working on an Augmented Reality system.
I'd like to receive some advice in order to optimize my math model. My program has to be slim and fast.

Here's the situation:

This is a photo of my marker:

I want to find the transformation matrix that "normalize" the photo in order to get this:

I have 4 angles coordinates of the marker:
$$P{1} = (352; 90)$$ $$P{2} = (93; 384)$$ $$P{3} = (852; 283)$$ $$P{4} = (663; 677)$$

Equation to find a generic projective transformation of a point P(x,y):

$$\left[\begin{array}{c} x' \\ y' \\ z' \\ \end{array}\right]= \left[\begin{array}{ccc} h_{1,1} & h_{1,2} & h_{1,3} \\ h_{2,1} & h_{2,2} & h_{2,3} \\ h_{3,1} & h_{3,2} & h_{3,3} \end{array}\right]* \left[\begin{array}{c} x \\ y \\ 1 \\ \end{array}\right]$$

In algebric form (we don't need z' and it is divided in x' and y'): $$x' = \frac{h_{11}x + h_{12}y + h_{13}}{h_{31}x + h_{32}y + h_{33}}$$
$$y' = \frac{h_{21}x + h_{22}y + h_{23}}{h_{31}x + h_{32}y + h_{33}}$$

Supposing that H(3,3) is 1, I can find H by solving this 8 equation by 8 variables system: $$\left[\begin{array}{cccccccc} x_{1} & y_{1} & 1 & 0 & 0 & 0 & -x_{1}*x'_{1} & -y_{1}*x'_{1} \\ x_{2} & y_{2} & 1 & 0 & 0 & 0 & -x_{2}*x'_{2} & -y_{2}*x'_{2} \\ x_{3} & y_{3} & 1 & 0 & 0 & 0 & -x_{3}*x'_{3} & -y_{3}*x'_{3} \\ x_{4} & y_{4} & 1 & 0 & 0 & 0 & -x_{4}*x'_{4} & -y_{4}*x'_{4} \\ 0 & 0 & 0 & x_{1} & y_{1} & 1 & -x_{1}*y'_{1} & -y_{1}*y'_{1} \\ 0 & 0 & 0 & x_{2} & y_{2} & 1 & -x_{2}*y'_{2} & -y_{2}*y'_{2} \\ 0 & 0 & 0 & x_{3} & y_{3} & 1 & -x_{3}*y'_{3} & -y_{3}*y'_{3} \\ 0 & 0 & 0 & x_{4} & y_{4} & 1 & -x_{4}*y'_{4} & -y_{4}*y'_{4} \end{array}\right]* \left[\begin{array}{c} h_{1,1} \\ h_{1,2} \\ h_{1,3} \\ h_{2,1} \\ h_{2,2} \\ h_{2,3} \\ h_{3,1} \\ h_{3,2} \end{array}\right]= \left[\begin{array}{c} x'_{1} \\ x'_{2} \\ x'_{3} \\ x'_{4} \\ y'_{1} \\ y'_{2} \\ y'_{3} \\ y'_{4} \end{array}\right]$$

Considering that the final marker will have mx as width and my as height, the transformations of my 4 initial points will be: $$P'{1} = (0; 0)$$ $$P'{2} = (0; my)$$ $$P'{3} = (mx; 0)$$ $$P'{4} = (mx; my)$$

So the system, in my case, become: $$\left[\begin{array}{cccccccc} x_{1} & y_{1} & 1 & 0 & 0 & 0 & 0 & 0 \\ x_{2} & y_{2} & 1 & 0 & 0 & 0 & 0 & 0 \\ x_{3} & y_{3} & 1 & 0 & 0 & 0 & -x_{3}*mx & -y_{3}*mx \\ x_{4} & y_{4} & 1 & 0 & 0 & 0 & -x_{4}*mx & -y_{4}*mx \\ 0 & 0 & 0 & x_{1} & y_{1} & 1 & 0 & 0 \\ 0 & 0 & 0 & x_{2} & y_{2} & 1 & -x_{2}*my & -y_{2}*my \\ 0 & 0 & 0 & x_{3} & y_{3} & 1 & 0 & 0 \\ 0 & 0 & 0 & x_{4} & y_{4} & 1 & -x_{4}*my & -y_{4}*my \end{array}\right]* \left[\begin{array}{c} h_{1,1} \\ h_{1,2} \\ h_{1,3} \\ h_{2,1} \\ h_{2,2} \\ h_{2,3} \\ h_{3,1} \\ h_{3,2} \end{array}\right]= \left[\begin{array}{c} 0 \\ 0 \\ mx \\ mx \\ 0 \\ my \\ 0 \\ my \end{array}\right]$$

This model works: i tried in Matlab and Java.
My question is: could it be simplified or optimized?
This system has a lot of zeros, and that means that it has little "information"...
Should I change something?

(I could consider mx and my equals to 1, in order to semplify the system even more. but i'd like to reduce the number of equations if it's possible)

-
Your intuition is correct. The $0$s in the suggest that this system is a bit redundant. Yes of course it is possible to reduce the number of equations and get rid of the $0$. Compare it with the algorithms to estimate the fundamental matrix: there is the 8 point algorithm, then the 7 point one and the 5 point algorithm. Because reducing the number of points (equations) was so popular R. Hartley wrote this In Defence of the 8-point Algorithm. If you reduce equations you lose the linearity. Still there is work currently in this direction with groebner basis etc. –  Peter Sheldrick Jun 13 '12 at 20:58

Unless the transformation you are looking for is of some specific form which has dependence between elements, I think it is not possible to reduce the number of the equations. You have 9 unknowns here, so 9 equations is the minimum for a single solution. Since you are looking for projection, I may guess that the transformation of it is not of general form, so it might be a good idea to think about how the matrix should look.

For implementation, instead of using a linear equations solver during run-time, , I suggest to try solve the equation off line and then construct equations for each unknown.

-
sincerly, i don't have any idea about how the matrix should look :( where could i find some documentation? –  Oneiros Jan 5 '12 at 19:00
I can guess (again, only a guess) that it is the inverse of a multiplication of a perspective and a rotation. You can test this empirically by photo-shooting the marker at a known angle, calculating the inverse matrix (perspective should be know from camera parameters) and comparing with the solution of the linear system that you already developed. –  Artium Jan 5 '12 at 19:33

Oneiros, either pick up 'Multiple View Geometry' by Richard Hartley and Andrew Zisserman (expensive, lots of difficult math, but if you stick to it very helpful and comprehensive).

What you wrote is correct at first glance. In the equation $x=PX$ where $x$ is a $3\times 1$ vector and $X$ is a $4\times 1$ vector both in homogenous coordinates and $P$ is a $3\times 4$ projection matrix, does produce a lot of zeros if you solve for $P$ given $x$ and $X$ of solve for $X$ given $x$ and $P$ etc. That is a fact. Don't be afraid of lots of zeros in your matrix - even PDEs are modeled by matrices with lots of zeros (finite element/differences) and these models are developed by real mathematicans!