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.

The question I'm trying to figure out states that I have N points (Pa1x,Pa1y) , (Pa2x,Pa2y)...(PaNx,PaNx) which correspond to a Pixel plane xy of a camera, and other N points (Pb1w,Pb1z) , (Pb2w,Pb2z)...(PbNw,PbNz) which correspond to my 2D World Coordinate Frame wz.

I've to find the trasformation (Rotation + Translation) between these two sets of points so that i can translate the point from the camera space to the world space.I've made a lot of measures and i've got the two set of points, but how should i proceed now ?

share|improve this question

2 Answers 2

The Kabsch Algorithm gives the least square solution for the rotation matrix.

I solved this problem for sci.math. That solution gives the same rotation as the Kabsch Algorithm and shows that the least squares conformal affine transformation maps the mean of the source points to the mean of the destination points. I have reproduced the summary of the method below.

Summary of the method:

To find the least squares solution to $PM+R=Q$ for a given set $\{P_j\}_{j=1}^m$ and $\{Q_j\}_{j=1}^m$, under the restriction that the map be conformal, first compute the centroids $$ \begin{array}{} \bar{P}=\frac{1}{m}\sum_{j=1}^mP_j&\text{and}&\bar{Q}=\frac{1}{m}\sum_{j=1}^mQ_j \end{array} $$ Next, compute the matrix $$ \begin{align} S &=\sum_{j=1}^m(Q_j-\bar{Q})^T(P_j-\bar{P)}\\ &=\left(\sum_{j=1}^mQ_j^TP_j\right)-m\bar{Q}^T\bar{P} \end{align} $$ Let the Singular Value Decomposition of S be $$ S=UDV^T $$ where U and V are unitary and D is diagonal.

Next compute $\{c_k\}_{k=1}^m$ with $$ \begin{align} c_k &=\sum_{j=1}^m[(P_j-\bar{P}\;)V\;]_k[(Q_j-\bar{Q})U\;]_k\\ &=\left(\sum_{j=1}^m[P_jV\;]_k[Q_jU\;]_k\right)-m[\bar{P}V\;]_k[\bar{Q}U\;]_k \end{align} $$ where $[V\;]_k$ is coordinate $k$ of $V$ and define $$ a_k=\operatorname{signum}(c_k) $$ Let $I_k$ be the matrix with the $k^{th}$ diagonal element set to $1$ and all the other elements set to $0$. Then calculate $$ E=\sum_{k=1}^ma_kI_k $$ Compute the orthogonal matrix $$ W=VEU^T $$ If $\det(W)<0$ but $\det(W)>0$ is required, change the sign of the $a_k$ associated with the $c_k$ with the smallest absolute value.

If required, compute $r$ by $$ r\sum_{j=1}^m|P_j-\bar{P}\;|^2=\sum_{j=1}^m\left<(P_j-\bar{P}\;)W,Q_j-\bar{Q}\right> $$ or equivalently $$ r\left(\left(\sum_{j=1}^m|P_j|^2\right)-m|\bar{P}\;|^2\right)=\left(\sum_{j=1}^m\left<P_jW,Q_j\right>\right)-m\left<\bar{P}\;W,\bar{Q}\;\right> $$ Finally, we have the desired conformal map $Q = PM+R$ where $$ \begin{array}{} M=rW&\text{and}&R=\bar{Q}-\bar{P}M \end{array} $$

share|improve this answer
    
Since my problem is referred to 2D points, do you mean i've to solve the same algorithm (scalar) two times, one time for x,w points and the other time for y,z points? –  John Oct 31 '11 at 21:43
    
No. The algorithm above takes an array of $m$ points in $\mathbb{R}^n$ and produces an $n\times n$ array, $M$, and an $n$-vector, $R$. In your case, $n=2$. –  robjohn Nov 1 '11 at 0:00
    
It is a very good work.Please ,can you send me the code in which you implemented that?It would be very helpful for me.My email is jay.cage@gmail.com –  John Nov 1 '11 at 15:32
    
@John: I didn't write code for it. Ray Koopman at Simon Fraser University in Canada implemented it and tested it. You might be able to contact him using the link at the beginning of my answer. –  robjohn Nov 1 '11 at 15:57

if you put the points in a homogeneous coordinate system (add a third dimension which is $1$ for all points) then each relation can be expressed as $A*P_a=P_b$ with

$$A=\begin{bmatrix} cos(\theta) & -sin(\theta) & x_{trans} \\ sin(\theta) & cos(\theta) & y_{trans} \\ 0 & 0 & 1 \\ \end{bmatrix} $$

with $\theta$ the rotation and $(x_{trans}, y_{trans})$ the translation

note this assumes a affine transformation but with only rotation and translation this is the case

edit confused $\sin$ and $\cos$ in the transformation matrix

you can read more about this at the wiki

edit:

in other words you can express the equations as $\cos(\theta)*P_{aix} - \sin(\theta)*P_{aiy} + x_{trans} = P_{bix}$ and $\sin(\theta)*P_{aix} + \cos(\theta)*P_{aiy} + y_{trans} = P_{biy}$

or

$$\begin{bmatrix} P_{a1x} & -P_{a1y} & 1 &0\\ P_{a1y} & P_{a1x} & 0 &1\\ P_{a2x} & -P_{a2y} & 1 &0\\ P_{a2y} & P_{a2x} & 0 &1\\ ...\\ P_{aNx} & -P_{aNy} & 1 &0\\ P_{aNy} & P_{aNx} & 0 &1\\ \end{bmatrix}* \begin{bmatrix} \cos(\theta) \\ \sin(\theta) \\ x_{trans}\\ y_{trans} \end{bmatrix}= \begin{bmatrix} P_{a1x}\\ P_{a1y}\\ P_{a2x}\\ P_{a2y}\\ ...\\ P_{aNx}\\ P_{aNy}\\ \end{bmatrix} $$

and I believe you know how to solve that

share|improve this answer
    
The thing is that i don't know neither the rotation nor the translation.How do i get them? –  John Oct 31 '11 at 10:43
    
@John you solve $A$, you have 6 unknowns and N equations –  ratchet freak Oct 31 '11 at 11:22
    
@John I made an edit explaining the next step –  ratchet freak Oct 31 '11 at 11:49
    
thanks very much ..it was helpful. I was just wondering what represent the θ ...do you mean the axis and angle rotation representation ? I see that i need just the matrix A, but what represents the θ? Then,i'm thinking to solve that system (4 unknowns and N equations) with the pseudo-inverse.Is it right? –  John Oct 31 '11 at 21:04
    
@john $\theta$ is represented by $\sin(\theta)$ and $\cos(\theta)$ (most math libraries have a atan2(x,y) function you can pass those in to get $\theta$) –  ratchet freak Oct 31 '11 at 22:16

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.