Machine Learning for Signal Processing

Linear  Algebra

Problem: 

• Given the world-cordinates of a set of $N$ points, $P^w_r(i) = (X^w_r(i), Y^w_r(i), Z^w_r(i)),~~i=1\cdots N$, $N>7$, and their corresponding camera image plane coordinates $P^c_i(i) = (X^c_i(i),Y^c_i(i)),~~i=1\cdots N$, show how $r_{11}\cdots r_{23}$ and $X_0$ can be recovered. Assume $Y_0 = 1$.
• Solution: We get the following equation. \[ -Y^c_i(i)X^w_r(i)r_{11} -Y^c_i(i)Y^w_r(i)r_{12} -Y^c_i(i)Z^w_r(i)r_{13} + X^c_i(i)X^w_r(i)r_{21} + X^c_i(i)Y^w_r(i)r_{22} + X^c_i(i)Z^w_r(i)r_{23} + Y^c_i(i)X_0 = X^c_i(i) \] We can write the above for all given points in a matrix form: \[ WR = V \] where \[ W = \begin{bmatrix}-Y^c_i(1)X^w_r(1)&-Y^c_i(1)Y^w_r(1)&-Y^c_i(1)Z^w_r(1)& X^c_i(1)X^w_r(1)&X^c_i(1)Y^w_r(1) & X^c_i(1)Z^w_r(1)& Y^c_i(1) \\ -Y^c_i(2)X^w_r(2)&-Y^c_i(2)Y^w_r(2)&-Y^c_i(2)Z^w_r(2)& X^c_i(2)X^w_r(2)&X^c_i(2)Y^w_r(2) & X^c_i(2)Z^w_r(2)& Y^c_i(2) \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ -Y^c_i(N)X^w_r(N)&-Y^c_i(N)Y^w_r(N)&-Y^c_i(N)Z^w_r(N)& X^c_i(N)X^w_r(N)&X^c_i(N)Y^w_r(N) & X^c_i(N)Z^w_r(N)& Y^c_i(N) \end{bmatrix} \], \[ R = \begin{bmatrix}r_{11}\\r_{12}\\r_{13}\\r_{21}\\r_{22}\\r_{23}\\X_0\end{bmatrix} \] and \[ V = \begin{bmatrix}X^c_i(1)\\X^c_i(2)\\\cdots\\X^c_i(N)\end{bmatrix} \] The solution is now obtained as: \[ R = pinv(W)V \]
• You are given the camera image plane coordinates $P^c_i(i) = (X^c_i(i),Y^c_i(i)),~~i=1\cdots N$ of $N$ points. You are also given the vector difference $P^w_r(i) - P^w_r(j)$ between their corresponding real-world coordinates in the world-coordinate system for $K$ $(i,j)$ pairs, $K>7$. You are not given the absolute coordinates $P^r_i(i)$ for any point, however. Show how $r_{11}\cdots r_{23}$ and $X_0$ can be recovered. Once again assume $Y_0 = 1$. (Hint: Since the world-coordinate origin is not specified, you can choose it to be convenient value, e.g. one of the provided points).
• Solution: This problem is not linear. It is quadratic, since $X^w_r, Y^w_r, Z^w_r$ and $r_{ij}$ are all unknown, and the equations we have are in terms of their productes. There is no closed form linear solution. This is what is known as a quadratic programming problem, requiring iterative solution.

  However, an approximate solution may be obtained as follows. Given the vector difference $D_x(i,j) = X^w_r(i) - X^w_r(j)$, $D_y(i,j) = Y^w_r(i) - Y^w_r(j)$ $D_z(i,j) = Z^w_r(i) - Z^w_r(j)$ between two points $i$ and $j$ we can extend the equation given above as follows: \[ \hat{W}\hat{R} = \hat{V} \] where \[ \hat{W} = \begin{bmatrix}W&0 & 0 \\ 0 & X^w_r(i_1)& -X^w_r(j_1)\\ 0 & Y^w_r(i_1)& -Y^w_r(j_1)\\ 0 & Z^w_r(i_1)& -Z^w_r(j_1)\\\cdots&\cdots&\cdots\\ 0 & X^w_r(i_l)& -X^w_r(j_l)\\ 0 & Y^w_r(i_l)& -Y^w_r(j_l)\\ 0 & Z^w_r(i_l)& -Z^w_r(j_l)\end{bmatrix} \] where the "0"s represent blocks of zeros (submatrices) of the appropriate sizes, and $(i_k, j_k)$ represents the $k$-th pair of points between which the vector difference is given. \[ \hat{R} = \begin{bmatrix}R \\ 1 \\ -1\end{bmatrix} \] and \[ \hat{V} = \begin{bmatrix}V\\D_x(i_1,j_1) \\D_y(i_1,j_1) \\D_z(i_1,j_1) \\\cdots \\D_x(i_l,j_l) \\D_y(i_l,j_l) \\D_z(i_l,j_l) \end{bmatrix} \] We can now solve this as follows: Initialize $\hat{R}$. The above becomes a linear equation in $X^w_r(i), Y^w_r(i), Z^w_r(i)$, which can be solved via a pinv. Having estimated these points, solve for $\hat{R}$. Fix $\hat{R}$ and solve for $X^w_r(i), Y^w_r(i), Z^w_r(i)$. Iterate.

  Alternately, we will assume the value of some points, as we do in part 3, where we assume that the nearest corners of all three grids ($XY$, $YZ$ and $XZ$ are at a known distance -- 7 cm -- from the corner.

  We will give full marks to anyone who has identified this as a quadratic problem.