Multiple View Geometry in Computer Vision Chapter 4 Solutions

Here’s a quick index to all the problems in this chapter. I have skipped the text for notes and only included the text for the exercises.

iii iv v vi viii

The main index can be found here.

Note that there is a typographical error in Note (i). $H{\text{x}}_i=k(x_i,y_i,1{)}^T$ should be $H{\text{x}}_i=k(x_i^{\prime },y_i^{\prime },1{)}^T$ instead.

III. Scaling unbounded point sets. In the case of points at or near infinity in a plane, it is neither reasonable nor feasible to normalize coordinates using the isotropic (or non-isotropic) scaling schemes presented in this chapter, since the centroid and scale are infinite or near infinite. A method that seems to give good results is to normalize the set of points ${\text{x}}_i=(x_i,y_i,w_i{)}^T$ such that $$\sum _i{x}_i=\sum _i{y}_i=0;\sum _i{x}_i^2+y_i^2=2\sum _i{w}_i^2;\sum _i{x}_i^2+y_i^2+w_i^2=1\forall i$$
Note that the coordinates $x_i$ and $y_i$ appearing here are the homogeneous coordinates, and the conditions no longer imply that the centroid is at the origin. Investigate methods of achieving this normalization, and evaluate its properties.

An equivalent problem, that of normalizing line coordinates when some lines pass through or near the origin, is discussed in detail in the paper “A new normalized method on line-based homography estimation” ¹. I recommend reading the paper to get a complete understanding of how the normalization reduces the condition number of the DLT matrix, making it less sensitive to noise. I will summarize below the transformations that lead to the required normalizations, and their properties. The goal is to spread out the points around the origin instead of having clusters of points far apart.

The following matrix $T$ ensures that $\sum _i{x}_i=\sum _i{y}_i=0\forall i$. In effect, it makes the relative distribution of the point coordinates more homogeneous about the $w$-axis in the $xyw$ 3D space.

$$T=\left(\begin{array}{ccc}1& 0& -\frac{\sum x_i}{\sum w_i}\\ 0& 1& -\frac{\sum y_i}{\sum w_i}\\ 0& 0& 1\end{array}\right)$$

The following matrix $S$, applied after $T$, ensures that $\sum _i{x}_i^2+y_i^2=2\sum _i{w}_i^2\forall i$. It makes the ratio of distance of a point from the $xy$ plane to its distance from the $w$ axis equal to $\sqrt{2}$, thus make the distribution of the point coordinates in $xyw$ space more homogeneous.

$$S=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& \sqrt{\frac{\sum _{i=1}^n{x}_i^2+y_i^2}{2\sum _{i=1}^n{w}_i^2}}\end{array}\right)$$

Finally ${\text{x}}_i/\parallel \begin{array}{c}{\text{x}}_i\end{array}\parallel$ ensures that $\sum _i{x}_i^2+y_i^2+w_i^2=1\forall i$, thus making the transformed point coordinates lie on the unit sphere centered at the origin.

Note that simply satisfying the constraint $\sum _i{x}_i^2+y_i^2+w_i^2=1\forall i$ without requiring the other two does not help much as demonstrated by Fig. 2a in the paper which shows that after such a normalization three points are clustered near (0, 0, 1) and one point is far away near (0.5, 0.8, 0), in other words, the matrix is still ill-conditioned.

In effect, the normalizing transformations reduce the condition number of the matrix by homogeneously distributing the point coordinates around the origin in 3D space.

IV. Transformation invariance of DLT. We consider computation of a 2D homography by minimizing algebraic error $\parallel \begin{array}{c}\text{Ah}\end{array}\parallel$ subject to various constraints. Prove the following cases:
(a) If $\parallel \begin{array}{c}\text{Ah}\end{array}\parallel$ is minimized subject to the constraint $h_9=H_{33}=1$, then the result is invariant under change of scale but not translation of coordinates.
(b) If instead the constraint is $H_{31}^2+H_{32}^2=1$ then the result is similarity invariant.
(c) Affine case: The same is true for the constraint $H_{31}=H_{32}=0;H_{33}=1$.

For each case, we need to prove that the given transformation class preserves the constraint under the transformation $\tilde{H}=T^{\prime }H{T}^{-1}$.

Note that in each case, we are only concerned with the last row of $\tilde{H}$.

Let $T$ be a similarity transformation. Any affine transformation leaves the last component of a homogeneous vector unchanged. Hence the last row of $H$ will be left unchanged by multiplication with $T^{\prime }$, i.e $T^{\prime }H$.

Thus the last row of $\tilde{H}$ only depends on the result of right multiplication with $T^{-1}$, i.e. $H{T}^{-1}$.

(a) If $T$ represented a change of scale transform then so would $T^{-1}$. Such a matrix would have the last column as $(0,0,1{)}^T$ and hence would leave $H_{33}$ unchanged. Hence if $H_{33}=1$, then ${\tilde{H}}_{33}=1$.

If $T$ represented a translation, then so would $T^{-1}$. Such a matrix would have the last column as $(-t_x,-t_y,1{)}^T$ making ${\tilde{H}}_{33}=-t_x{H}_{31}-t_y{H}_{32}+H_{33}$. Hence $H_{33}$ being equal to 1 would not imply that ${\tilde{H}}_{33}=1$.

Thus, if $\parallel \begin{array}{c}\text{Ah}\end{array}\parallel$ is minimized subject to the constraint $h_9=H_{33}=1$, then the result is invariant under change of scale but not translation of coordinates.

(b) If $T$ represented a similarity transform then the first two columns of $T^{-1}$ would be $(cos\theta /s,-sin\theta /s,0{)}^T$ and $(sin\theta /s,cos\theta /s,0{)}^T$. This means ${\tilde{H}}_{31}=1/s(H_{31}cos\theta -H_{32}sin\theta )$ and ${\tilde{H}}_{32}=1/s(H_{31}sin\theta +H_{32}cos\theta )$. Furthermore,

$${\tilde{H}}_{31}^2+{\tilde{H}}_{32}^2=1/s^2\left[\right(H_{31}cos\theta -H_{32}sin\theta {)}^2+(H_{31}sin\theta +H_{32}cos\theta {)}^2]$$ $$=1/s^2(H_{31}^{2}co{s}^2\theta +H_{32}^{2}si{n}^2\theta -2H_{31}{H}_{32}sin\theta cos\theta +H_{31}^{2}si{n}^2\theta +H_{32}^{2}co{s}^2\theta +2H_{31}{H}_{32}sin\theta cos\theta )$$ $$=1/s^2(H_{31}^{2}co{s}^2\theta +H_{32}^{2}si{n}^2\theta +H_{31}^{2}si{n}^2\theta +H_{32}^{2}co{s}^2\theta )$$ $$=1/s^2(H_{31}^2+H_{32}^2)$$ $$=1/s^2$$

As $H_{31}^2+H_{32}^2=1$ implies ${\tilde{H}}_{31}^2+{\tilde{H}}_{32}^2=constant$, the DLT algorithm will be invariant under this constraint.

(c) From the discussion in (b), we can see that if $H_{32}=H_{31}=0$ then ${\tilde{H}}_{32}={\tilde{H}}_{31}=0$. The last column of $T^{-1}$ will be of the form $(a,b,1{)}^T$ if $T$ is a similarity transform leading to ${\tilde{H}}_{33}=a{H}_{31}+b{H}_{32}+H_{33}=0+0+H_{33}=1$. As the constraints $H_{32}=H_{31}=0;H_{33}=1$ imply ${\tilde{H}}_{32}={\tilde{H}}_{31}=0;{\tilde{H}}_{33}=1$, the DLT algorithm will be invariant under these constraints.

V. Expressions for image coordinate derivative. For the map ${\text{x}}^{\prime }=(x^{\prime },y^{\prime },w^{\prime }{)}^T=H\text{x}$, derive the following expressions (where ${\tilde{\text{x}}}^{\prime }=(\widetilde{x^{\prime }},\widetilde{y^{\prime }}{)}^T=(x^{\prime }/w^{\prime },y^{\prime }/w^{\prime })$ are the inhomogeneous coordinates of the image point):
(a) Derivative wrt $\text{x}$ $$\partial {\tilde{\text{x}}}^{\prime }/\partial \text{x}=\frac{1}{w^{\prime }}\left(\begin{array}{c}{\text{h}}^{1T}-\widetilde{x^{\prime }}{\text{h}}^{3T}\\ {\text{h}}^{2T}-\widetilde{y^{\prime }}{\text{h}}^{3T}\end{array}\right)$$ where ${\text{h}}^{jT}$ is the $j$-th row of $H$.
(b) Derivative wrt $H$ $$\partial {\tilde{\text{x}}}^{\prime }/\partial \text{h}=\frac{1}{w^{\prime }}\left(\begin{array}{ccc}{\text{x}}^T& 0& -\widetilde{x^{\prime }}{\text{x}}^T\\ 0& {\text{x}}^T& -\widetilde{y^{\prime }}{\text{x}}^T\end{array}\right)$$ with $\text{h}$ as defined in (4.2-p89).

(a) It is clear that

$$\frac{\partial {\text{h}}^{iT}\text{x}}{\partial x_1}={\text{h}}_{i1},\frac{\partial {\text{h}}^{iT}\text{x}}{\partial y_1}={\text{h}}_{i2},\frac{\partial {\text{h}}^{iT}\text{x}}{\partial w_1}={\text{h}}_{i3}$$

Hence, $$\frac{\partial {\text{h}}^{iT}\text{x}}{\partial \text{x}}={\text{h}}^{iT}$$

Now, $$\widetilde{x^{\prime }}=x^{\prime }/w^{\prime }$$ $$=\frac{{\text{h}}^{1T}\text{x}}{{\text{h}}^{3T}\text{x}}$$

Applying the chain rule $$\partial {\tilde{x}}^{\prime }/\partial \text{x}=\frac{1}{{\text{h}}^{3T}\text{x}}\frac{\partial {\text{h}}^{1T}\text{x}}{\partial \text{x}}-\frac{{\text{h}}^{1T}\text{x}}{({\text{h}}^{3T}\text{x}{)}^2}\frac{\partial {\text{h}}^{3T}\text{x}}{\partial \text{x}}$$

Substituting the values of the partial derivatives we calculated earlier $$\partial {\tilde{x}}^{\prime }/\partial \text{x}=\frac{1}{{\text{h}}^{3T}\text{x}}{\text{h}}^{1T}-\frac{{\text{h}}^{1T}\text{x}}{({\text{h}}^{3T}\text{x}{)}^2}{\text{h}}^{3T}$$

Substituting $x^{\prime }={\text{h}}^{1T}\text{x}$ and $w^{\prime }={\text{h}}^{3T}\text{x}$ $$\partial {\tilde{x}}^{\prime }/\partial \text{x}=\frac{1}{w^{\prime }}{\text{h}}^{1T}-\frac{x^{\prime }}{(w^{\prime }{)}^2}{\text{h}}^{3T}$$

Finally, substituting $\widetilde{x^{\prime }}=x^{\prime }/w^{\prime }$ $$\partial {\tilde{x}}^{\prime }/\partial \text{x}=\frac{1}{w^{\prime }}{\text{h}}^{1T}-\frac{\widetilde{x^{\prime }}}{w^{\prime }}{\text{h}}^{3T}$$ $$=\frac{1}{w^{\prime }}({\text{h}}^{1T}-\widetilde{x^{\prime }}{\text{h}}^{3T})$$

By applying a similar process we observe that $$\partial {\tilde{y}}^{\prime }/\partial \text{x}==\frac{1}{w^{\prime }}({\text{h}}^{2T}-\widetilde{y^{\prime }}{\text{h}}^{3T})$$

Hence, we have established that $$\partial {\tilde{\text{x}}}^{\prime }/\partial \text{x}=\frac{1}{w^{\prime }}\left(\begin{array}{c}{\text{h}}^{1T}-\widetilde{x^{\prime }}{\text{h}}^{3T}\\ {\text{h}}^{2T}-\widetilde{y^{\prime }}{\text{h}}^{3T}\end{array}\right)$$

(b) In a similar fashion, applying the chain rule, we get $$\partial {\tilde{x}}^{\prime }/\partial \text{x}=\frac{1}{{\text{h}}^{3T}\text{x}}\frac{\partial {\text{h}}^{1T}\text{x}}{\partial \text{h}}-\frac{{\text{h}}^{1T}\text{x}}{({\text{h}}^{3T}\text{x}{)}^2}\frac{\partial {\text{h}}^{3T}\text{x}}{\partial \text{h}}$$

It is clear that $$\partial {\text{h}}^{1T}\text{x}/\partial \text{h}=\left(\begin{array}{ccc}{\text{x}}^T& 0& 0\end{array}\right)$$ $$\partial {\text{h}}^{2T}\text{x}/\partial \text{h}=\left(\begin{array}{ccc}0& {\text{x}}^T& 0\end{array}\right)$$ $$\partial {\text{h}}^{3T}\text{x}/\partial \text{h}=\left(\begin{array}{ccc}0& 0& {\text{x}}^T\end{array}\right)$$

Substituting this into the expansion above $$\partial {\tilde{x}}^{\prime }/\partial \text{h}=\frac{1}{{\text{h}}^{3T}\text{x}}\left(\begin{array}{ccc}{\text{x}}^T& 0& 0\end{array}\right)-\frac{{\text{h}}^{1T}\text{x}}{({\text{h}}^{3T}\text{x}{)}^2}\left(\begin{array}{ccc}0& 0& {\text{x}}^T\end{array}\right)$$

Substituting $x^{\prime }={\text{h}}^{1T}\text{x}$ and $w^{\prime }={\text{h}}^{3T}\text{x}$ $$\partial {\tilde{x}}^{\prime }/\partial \text{x}=\frac{1}{w^{\prime }}\left(\begin{array}{ccc}{\text{x}}^T& 0& 0\end{array}\right)-\frac{x^{\prime }}{(w^{\prime }{)}^2}\left(\begin{array}{ccc}0& 0& {\text{x}}^T\end{array}\right)$$

Finally, substituting $\widetilde{x^{\prime }}=x^{\prime }/w^{\prime }$ $$\partial {\tilde{x}}^{\prime }/\partial \text{x}=\frac{1}{w^{\prime }}\left(\begin{array}{ccc}{\text{x}}^T& 0& 0\end{array}\right)-\frac{\widetilde{x^{\prime }}}{w^{\prime }}\left(\begin{array}{ccc}0& 0& {\text{x}}^T\end{array}\right)$$

$$=\frac{1}{w^{\prime }}\left(\begin{array}{ccc}{\text{x}}^T& 0& -\widetilde{x^{\prime }}{\text{x}}^T\end{array}\right)$$

Performing a similar process for $\widetilde{y^{\prime }}$, we get $$\partial {\tilde{y}}^{\prime }/\partial \text{x}=\frac{1}{w^{\prime }}\left(\begin{array}{ccc}0& {\text{x}}^T& -\widetilde{y^{\prime }}{\text{x}}^T\end{array}\right)$$

Hence, we have established that $$\partial {\tilde{\text{x}}}^{\prime }/\partial \text{h}=\frac{1}{w^{\prime }}\left(\begin{array}{ccc}{\text{x}}^T& 0& -\widetilde{x^{\prime }}{\text{x}}^T\\ 0& {\text{x}}^T& -\widetilde{y^{\prime }}{\text{x}}^T\end{array}\right)$$

VI. Sampson error with non-isotropic error distributions. The derivation of Sampson error in section 4.2.6(p98) assumed that points were measured with circular error distributions. In the case where the point $\text{X}=(x,y,x^{\prime },y^{\prime })$ is measured with covariance matrix ${\Sigma }_{\text{x}}$ it is appropriate instead to minimize the Mahalanobis norm ${\parallel \begin{array}{c}{\delta }_{\text{x}}\end{array}\parallel }_{{\Sigma }_{\text{x}}}^2={\delta }_{\text{x}}^T{\Sigma }_{\text{x}}^{-1}{\delta }_{\text{x}}$. Show that in this case the formulae corresponding to (4.11-p99) and (4.12-p99) are $${\delta }_{\text{x}}=-{\Sigma }_{\text{x}}{J}^T(J{\Sigma }_{\text{x}}{J}^T{)}^{-1}ϵ$$ and $${\parallel \begin{array}{c}{\delta }_{\text{x}}\end{array}\parallel }_{{\Sigma }_{\text{x}}}^2={ϵ}^T(J{\Sigma }_{\text{x}}{J}^T{)}^{-1}ϵ$$ Note that if the measurements in the two images are independent, then the covariance matrix ${\Sigma }_{\text{x}}$ will be block-diagonal with two $2\times 2$ diagonal blocks corresponding to the two images.

In this case, we need to find the extrema of ${\delta }_{\text{x}}^T{\Sigma }_{\text{x}}^{-1}{\delta }_{\text{x}}-2{\lambda }^T(J{\delta }_{\text{x}}-ϵ)$.

Derivative of ${\delta }_{\text{x}}^T{\Sigma }_{\text{x}}^{-1}{\delta }_{\text{x}}$ with respect to ${\delta }_{\text{x}}$ is $2{\delta }_{\text{x}}^T{\Sigma }_{\text{x}}^{-1}$ as ${\Sigma }_{\text{x}}^{-1}$ is symmetric (due to ${\Sigma }_{\text{x}}$ being symmetric). Hence taking the derivative of the whole expression with respect to ${\delta }_{\text{x}}$ and equating to zero will give us

$$2{\delta }_{\text{x}}^T{\Sigma }_{\text{x}}^{-1}-2{\lambda }^{T}J={\text{0}}^T$$ $$⟹{\delta }_{\text{x}}={\Sigma }_{\text{x}}{J}^T\lambda$$

Taking the derivative with respect to $\lambda$ and equating to zero will give us back the original constraint, $J{\delta }_{\text{x}}+ϵ$, as before. Substituting for ${\delta }_{\text{x}}$ leads to

$$J{\Sigma }_{\text{x}}{J}^T\lambda =-ϵ$$ $$⟹\lambda =-(J{\Sigma }_{\text{x}}{J}^T{)}^{-1}ϵ$$ $$⟹{\delta }_{\text{x}}=-{\Sigma }_{\text{x}}{J}^T(J{\Sigma }_{\text{x}}{J}^T{)}^{-1}ϵ$$

and

$${\parallel \begin{array}{c}{\delta }_{\text{x}}\end{array}\parallel }_{{\Sigma }_{\text{x}}}^2={\delta }_{\text{x}}^T{\Sigma }_{\text{x}}^{-1}{\delta }_{\text{x}}=(-{ϵ}^T(J{\Sigma }_{\text{x}}{J}^T{)}^{-T}J{\Sigma }_{\text{x}}^T\left){\Sigma }_{\text{x}}^{-1}\right(-{\Sigma }_{\text{x}}{J}^T\left(J{\Sigma }_{\text{x}}{J}^T{)}^{-1}ϵ\right)$$ $$=\left({ϵ}^T\right(J{\Sigma }_{\text{x}}{J}^T{)}^{-T}J{\Sigma }_{\text{x}}^T\left)\right({\Sigma }_{\text{x}}^{-1}{\Sigma }_{\text{x}}\left)\right(J^T\left(J{\Sigma }_{\text{x}}{J}^T{)}^{-1}ϵ\right)$$ $$=\left({ϵ}^T\right(J{\Sigma }_{\text{x}}{J}^T{)}^{-T}J{\Sigma }_{\text{x}}^T\left)\right(J^T\left(J{\Sigma }_{\text{x}}{J}^T{)}^{-1}ϵ\right)$$ $$={ϵ}^T\left(J{\Sigma }_{\text{x}}{J}^T{)}^{-T}\right(J{\Sigma }_{\text{x}}^T{J}^T\left)\right(J{\Sigma }_{\text{x}}{J}^T{)}^{-1}ϵ$$ $$={ϵ}^T(J{\Sigma }_{\text{x}}{J}^T{)}^{-T}ϵ$$ $$={ϵ}^T(J{\Sigma }_{\text{x}}^T{J}^T{)}^{-1}ϵ$$ $$={ϵ}^T(J{\Sigma }_{\text{x}}{J}^T{)}^{-1}ϵ$$

VIII. Minimizing geometric error for affine transformations. Given a set of correspondences $(x_i,y_i)⟷(x_i^{\prime },y_i^{\prime })$, find an affine transformation $H_A$ that minimizes geometric error (4.8-p95). We will step through the derivation of a linear algorithm based on Sampson’s approximation which is exact in this case. The complete method is summarized in algorithm 4.7.
(a) Show that the optimum affine transformation takes the centroid of the ${\text{x}}_i$ to the centroid of the ${\text{x}}_i^{\prime }$, so by translating the points to have their centroid at the origin, the translation part of the transformation is determined.

Let’s express the affine transformation as a composition of transformation and scaling (in that order) as $A=ST$, where $S$ is the scaling transform and $T$ is the translation.

Then $T$ will have the form $$\left(\begin{array}{ccc}1& 0& t_x\\ 0& 1& t_y\\ 0& 0& 1\end{array}\right)$$

with $\text{h}=(1,0,t_x,0,1,t_y,0,0,1{)}^T$.

The residual $ϵ$ in this case will be $$\left(\begin{array}{c}{y}_i^{\prime }{\text{h}}^{3T}{\text{x}}_i-w_i^{\prime }{\text{h}}^{2T}{\text{x}}_i\\ w_i^{\prime }{\text{h}}^{1T}{\text{x}}_i-x_i^{\prime }{\text{h}}^{3T}{\text{x}}_i\end{array}\right)=\left(\begin{array}{c}{w}_i{y}_i^{\prime }-w_i^{\prime }{y}_i+w_i{w}_i^{\prime }{t}_y\\ w_i^{\prime }{x}_i+w_i{w}_i^{\prime }{t}_x-w_i{x}_i^{\prime }\end{array}\right)$$

Assuming that $w_i=w_i^{\prime }=1$, the inhomogeneous coordinates are simply $x_i,y_i,x_i^{\prime },y_i^{\prime }$ and the residual can be written as $$\left(\begin{array}{c}{y}_i^{\prime }-y_i+t_y\\ x_i+t_x-x_i^{\prime }\end{array}\right)$$

The Jacobian for this residual will then be $$J=\left(\begin{array}{cccc}0& -1& 0& 1\\ 1& 0& -1& 0\end{array}\right)$$

$$⟹(J{J}^T{)}^{-1}=\frac{1}{2}I$$

where $I$ is the identity matrix.

The Sampson error for the $i^{th}$ correspondence can then be calculated as $${ϵ}_i^T(J{J}^T{)}^{-1}{ϵ}_i=\frac{1}{2}{ϵ}_i^T{ϵ}_i$$

From this it is clear that minimizing the geometric error is the same as minimizing the Sampson error which is the same as minimizing the algebraic error for a translation.

Expanding this error and dropping the constant, we get the error for the $i^{th}$ correspondence to be $$(y_i^{\prime }-y_i+t_y{)}^2+(x_i^{\prime }-x_i+t_x{)}^2$$ $$=y_i^{\prime 2}+y_i^2+t_y^2-2y_i^{\prime }{y}_i-2y_i{t}_y+2y_i^{\prime }{t}_y+x_i^{\prime 2}+x_i^2+t_x^2-2x_i^{\prime }{x}_i-2x_i{t}_x+2x_i^{\prime }{t}_x$$

The sum of the errors for all such correspondences will be $$=\sum _i{y}_i^{\prime 2}+\sum _i{y}_i^2+n{t}_y^2-2\sum _i{y}_i^{\prime }{y}_i-2t_y\sum _i{y}_i+2t_y\sum _i{y}_i^{\prime }+\sum _i{x}_i^{\prime 2}+\sum _i{x}_i^2+n{t}_x^2-2\sum _i{x}_i^{\prime }{x}_i-2t_x\sum _i{x}_i+2t_x\sum _i{x}_i^{\prime }{t}_x$$

To find the optimal values of $t_x$ and $t_y$ we take the derivatives w.r.t. $t_x$ and $t_y$ and set them to zero. By doing this we get

$$2n{t}_x+2\sum _i{x}_i^{\prime }-2\sum _i{x}_i=0$$ $$2n{t}_y+2\sum _i{y}_i^{\prime }-2\sum _i{y}_i=0$$

Hence, $$t_x=\frac{\sum _i{x}_i^{\prime }-\sum _i{x}_i}{n}={\overline{x}}^{\prime }-\overline{x}$$ $$t_y=\frac{\sum _i{y}_i^{\prime }-\sum _i{y}_i}{n}={\overline{y}}^{\prime }-\overline{y}$$

where $(\overline{x},\overline{y})$ and $({\overline{x}}^{\prime },{\overline{y}}^{\prime })$ are the centroids of the points in each image respectively.

Thus the translation portion of the optimal affine transformation takes the centroid of points in the first image to the centroid of the points in the second.

References