# Transforming matrix-equation to overdetermined minimum problem

i have broken down my problem to plainmath and could really use some help.

Basis: I have an image. In this image I have several UV-XYZ pairs. So i know the 3d position of serveral Pixels.

Given the following equations from 3d to 2d space.

$Z_{c} \begin{pmatrix} U \\ V \\ 1 \end{pmatrix} = \begin{pmatrix} f & 0 & px \\ 0 & f & py \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} r_{1} & r_{2} & r_{3} & t_{1}\\ r_{4} & r_{5} & r_{6} & t_{2}\\ r_{7} & r_{8} & r_{9} & t_{3} \end{pmatrix} \begin{pmatrix} X \\ Y \\ Z \\ 1 \end{pmatrix}$

f, px, py are known constants. Many $UV \to XYZ$ pairs are known. I want to get $r_{1} - r_{9}, t_{1}, t_{2}$ and $t_{3}$

I can transform to:

$\begin{pmatrix} f & 0 & px \\ 0 & f & py \\ 0 & 0 & 1 \end{pmatrix} ^{-1} \begin{pmatrix} U \\ V \\ 1 \end{pmatrix} = \frac 1 Z_{c} \begin{pmatrix} r_{1} & r_{2} & r_{3} & t_{1}\\ r_{4} & r_{5} & r_{6} & t_{2}\\ r_{7} & r_{8} & r_{9} & t_{3} \end{pmatrix} \begin{pmatrix} X \\ Y \\ Z \\ 1 \end{pmatrix}$

The $Z_{c}$ is the Z-Coordinate of the point AFTER the multiplication with the unknown transformation matrix.

$Z_{c} = \begin{pmatrix} r_{7} & r_{8} & r_{9} & t_{3} \end{pmatrix} \begin{pmatrix} X \\ Y \\ Z \\ 1 \end{pmatrix}$ This leads to these equations for U and V: $U_{k} = \frac {r_{1}X + r_{2}Y + r_{3}Z + t_{1}} {r_{7}X + r_{8}Y + r_{9}Z + t_{3}} V_{k} = \frac {r_{4}X + r_{5}Y + r_{6}Z + t_{2}} {r_{7}X + r_{8}Y + r_{9}Z + t_{3}}$

The question in the end is quite simple. I need to transform this equation into sth., so I can apply 50-100 $UV \to XYZ$ pairs and get the camera position and rotation. Without the $Z_{c}$ it is pretty easy to transform into sth. like this:

$\begin{pmatrix} U_{1} + V_{2} + 1 \\ U_{4} + V_{5} + 1 \\ \vdots \end{pmatrix} = \begin{pmatrix} X_{1} & Y_{1} & Z_{1} & 1 & X_{2} & Y_{2} & Z_{2} & 1 & X_ {3} & Y_{3} & Z_{3} & 1 \\ X_{4} & Y_{4} & Z_{4} & 1 & X_{5} & Y_{5} & Z_{5} & 1 & X_ {6} & Y_{6} & Z_{6} & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \end{pmatrix} \begin{pmatrix} r_{1} \\ r_{2} \\ r_{3} \\ t_{1} \\ r_{4} \\ r_{5} \\ r_{6} \\ t_{2} \\ r_{7} \\ r_{8} \\ r_{9} \\ t_{3} \end{pmatrix}$

I hope you get the idea. I dont know if its correct, but it seems like it. So this is a classical overdetermined linear equation (if you add 100 Rows), which I could have solved with a QR-Decomposition (i hope its called like that). But I can't apply this idea to the new Problem with $Z_{c}$. Leaves me clueless.

-
Come on guys. There needs to be a solution for this. This is the very last piece in the assemblyline to complete my application... –  xeed Mar 15 '13 at 19:33

Let me do some rearranging and substituting to give you a more concise formula:

Your very first formula with the substitution $$Z_{c} = \begin{pmatrix} r_{7} & r_{8} & r_{9} & t_{3} \end{pmatrix} \begin{pmatrix} X \\ Y \\ Z \\ 1 \end{pmatrix}$$

gives

$$\begin{pmatrix} U \\ V \\ 1 \end{pmatrix} \begin{pmatrix} r_{7} & r_{8} & r_{9} & t_{3} \end{pmatrix} \begin{pmatrix} X \\ Y \\ Z \\ 1 \end{pmatrix} = \begin{pmatrix} f & 0 & px \\ 0 & f & py \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} r_{1} & r_{2} & r_{3} & t_{1}\\ r_{4} & r_{5} & r_{6} & t_{2}\\ r_{7} & r_{8} & r_{9} & t_{3} \end{pmatrix} \begin{pmatrix} X \\ Y \\ Z \\ 1 \end{pmatrix}$$

and now we have

$$\left[\begin{pmatrix} f & 0 & px \\ 0 & f & py \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} r_{1} & r_{2} & r_{3} & t_{1}\\ r_{4} & r_{5} & r_{6} & t_{2}\\ r_{7} & r_{8} & r_{9} & t_{3} \end{pmatrix}-\begin{pmatrix}0 & 0 & U \\ 0 & 0 & V \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} r_{1} & r_{2} & r_{3} & t_{1}\\ r_{4} & r_{5} & r_{6} & t_{2}\\ r_{7} & r_{8} & r_{9} & t_{3} \end{pmatrix} \right] \begin{pmatrix} X \\ Y \\ Z \\ 1 \end{pmatrix} = 0$$ or $$\begin{pmatrix} f & 0 & px - U \\ 0 & f & py - V \\ 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} r_{1} & r_{2} & r_{3} & t_{1}\\ r_{4} & r_{5} & r_{6} & t_{2}\\ r_{7} & r_{8} & r_{9} & t_{3} \end{pmatrix} \begin{pmatrix} X \\ Y \\ Z \\ 1 \end{pmatrix} = 0$$

$$\begin{pmatrix} f & 0 & px - U \\ 0 & f & py - V \\ 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} r_{1}X + r_{2}Y + r_{3}Z + t_{1}\\ r_{4}X + r_{5}Y + r_{6}Z + t_{2}\\ r_{7}X + r_{8}Y + r_{9}Z + t_{3} \end{pmatrix} = 0$$ This gives the two equations

$$fXr_{1} + fYr_{2} + fZr_{3} + ft_{1}+ (px - U)Xr_{7} + (px - U)Yr_{8} + (px - U)Zr_9 + (px - U)t_{3} = 0$$ $$fXr_{4} + fYr_{5} + fZr_{6} + ft_{2}+ (py - V)Xr_{7} + (py - V)Yr_{8} + (py - V)Zr_9 + (py - V)t_{3} = 0$$

I tried to format into matrix times the r and t vector, but the equation was too wide to fit. This formulation allows for the separation into unknowns though.

-
Can't edit anymore: Thanks man, can't I transform your last 2 equations to this: $\begin{pmatrix} fX & fY & fZ & f & 0 & 0 & 0 & 0 & (px-U)X & (px-U)Y & (px-U)Z & (px-U) \\ 0 & 0 & 0 & 0 & fX & fY & fZ & f & (py-V)X & (py-V)Y & (py-V)Z & (py-V) \\ \end{pmatrix} \begin{pmatrix} r_{1} \\ r_{2} \\ r_{3} \\ t_{1} \\ r_{4} \\ r_{5} \\ r_{6} \\ t_{2} \\ r_{7} \\ r_{8} \\ r_{9} \\ t_{3} \end{pmatrix} = 0$ I should be able to solve this with a QR-Decomposition or another method. Did you mean this formulation does not fit on the site? Then I'm sorry. ^^ –  xeed Mar 16 '13 at 20:40
Yeah, that's the one. On my display it was cut off, I figured you could take it from there. –  adam W Mar 16 '13 at 21:20
Well, I tried this equation in matlab. Code: pastebin.com/iGwkru4S I'm not a Matlab genius, but I tried solving it according to this: mathworks.de/de/help/matlab/math/… The message I get is that the matrix has a rank of 11. I dont really know why. I'll continue to figure it out, but maybe you are able to get me there faster. – –  xeed Mar 17 '13 at 14:23
The matrix should have rank less than $12$ in order to have a non-zero solution for the r/t vector. If it has rank less than $11$ then there are more than one solution. So it sounds right that it has rank $11$. –  adam W Mar 17 '13 at 16:09
Sooo, i'm pretty sure that i'm right. There are 12 variables, so the matrix needs to have rank 12 to have only one solution. I finally got some non zero values from this equation using SVD. The good thing: rank 11 leaves only a unsolved factor, which i have to apply to get the correct values for Rt. If i can't figure out how to get a rank 12 koefficientmatrix, i PROBABLY can figure this factor out by applying some rotationmatrix properties. And again. Thanks to you, you were huge help. I'm actually looking forward to go to work tomorrow. ^^ –  xeed Mar 18 '13 at 0:57