Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:
enter image description here

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

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]$$

Awesome draw of the model

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)

share|improve this question
1  
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

2 Answers 2

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.

share|improve this answer
    
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).

This whole book is about this topic so believe me that it is comprehensive.

As an alternative look at this book by Richard Szeliski (Microsoft). It is freely downloadable (but there is also a pay-for version if you are flush with cash). This topic is only dealt with in chapter six (and following) - the rest is general computer vision and image processing. Hence the presentation is condensed.

There are also tutorials on the web (for example a detailed one by Marc Pollefeys). And Wikipedia is also better than nothing.

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!

Even better than reading about this in books, use a library: For example there is the Qualcomm AR library that works with Android and IOS and ties in with Unity 3D. Or there is the PTAM camera tracking + augmentation software for non-commercial purposes. The default works only with firewire cameras (and that refers to the 1394 standard - just having a video stream over a firewire cable - DV video for example - is not the same). It is written in C and was developed for linux and uses lots of C-libraries. There have been various ports to other OSes (also different cameras): these are by the original authors (Mac OSX and Windows). And there was also a port to C# for Windows by Bob Mottram.

There are also other frameworks!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.