An alternative derivation of the DLT for homographies

What if in the linear system A \mathbf{x} = \mathbf{b} the unknowns are not \mathbf{x} but the matrix A? Of course, if we have a sufficient number N of such systems A \mathbf{x}^{(1)} = \mathbf{b}^{(1)}A \mathbf{x}^{(2)} = \mathbf{b}^{(2)}, … with the same matrix A and independent second hands, we can stack them, and solve

x_1^{(1)} A_{11}+x_2^{(1)} A_{12}+ \cdots + x_n^{(1)} A_{1n}= b_1^{(1)}

x_1^{(N)} A_{m1}+x_2^{(N)} A_{m2}+ \cdots + x_n^{(N)} A_{mn}= b_m^{(N)}

for the m \times n unknowns A_{11} \cdots A_{mn} .  A similar problem arises when looking for a planar homography:

\begin{bmatrix} H_{11} & H_{12} & H_{13} \\ H_{21} & H_{22} & H_{23} \\ H_{31} & H_{32} & H_{33} \end{bmatrix} \begin{bmatrix} u \\ v \\ w \end{bmatrix} \propto \begin{bmatrix} u' \\ v' \\ w' \end{bmatrix}                                                    (1)

given a sufficient number of couples of homogeneous points ((u^{(i)}, v^{(i)}, w^{(i)}), (u'^{(i)}, v'^{(i)}, w'^{(i)})), i \in 1 \cdots M, M \geq 4 . It is to be noted that the problem is not identical as we have here \propto meaning proportionality, not equality; this because, with homogeneous coordinates, (u, v, w) and \lambda (u, v, w), with \lambda \neq 0, do represent the same point, and as a consequence the homography matrix H , while being full rank for regular homographies, is also defined up to a scale factor.

The correct method to solve this problem (eg Hartley&Zisserman, Multiple View Geometry in Computer Vision, §4.1) is to transform the system H \mathbf{u} \propto \mathbf{u'}  by applying a cross product with \mathbf{u}' to both hands, so that the second hand vanishes and we are left with the set of homogeneous linear equations \mathbf{u'} \times H \mathbf{u}=0 , containing for each sample (\mathbf{u}, \mathbf{u'}) three equations in the unknown entries of H. Only two of such equations are linearly independent, so one can be discarded.

This method is the so called DLT, short for Direct Linear Transformation. It works fine, albeit the cross product smells of deus ex machina math trick. One can get the same result in a way that, in my opinion, is more elegant if one recognizes that the real problem is not the homogeneity of the involved quantities in itself, but the related fact that u, v, w, u', v', w' are not observable: the observables are the ratios \frac{u}{w}, \frac{v}{w}, \frac{u'}{w'}, \frac{v'}{w'} instead (provided that we have no point at infinity). So one should manipulate the equations (1) to make these ratios emerge. Start with

\dfrac{u'_i}{w'_i} = \dfrac{H_{11} u_i + H_{12} v_i + H_{13} w_i}{H_{31} u_i + H_{32} v_i + H_{33} w_i}

\dfrac{v'_i}{w'_i} = \dfrac{H_{21} u_i + H_{22} v_i + H_{23} w_i}{H_{31} u_i + H_{32} v_i + H_{33} w_i}

whence:

H_{11} u_i + H_{12} v_i + H_{13} w_i - \dfrac{u'_i}{w'_i} H_{31} u_i - \dfrac{u'_i}{w'_i} H_{32} v_i - \dfrac{u'_i}{w'_i} H_{33} w_i = 0

H_{21} u_i + H_{22} v_i + H_{23} w_i - \dfrac{v'_i}{w'_i} H_{31} u_i - \dfrac{v'_i}{w'_i} H_{32} v_i - \dfrac{v'_i}{w'_i} H_{33} w_i = 0

Last, divide by w_i :

H_{11} \dfrac{u_i}{w_i} + H_{12} \dfrac{v_i}{w_i} + H_{13} - \dfrac{u'_i}{w'_i} H_{31} \dfrac{u_i}{w_i} - \dfrac{u'_i}{w'_i} H_{32} \dfrac{v_i}{w_i} - \dfrac{u'_i}{w'_i} H_{33} = 0

H_{21} \dfrac{u_i}{w_i} + H_{22} \dfrac{v_i}{w_i} + H_{23} - \dfrac{v'_i}{w'_i} H_{31} \dfrac{u_i}{w_i} - \dfrac{v'_i}{w'_i} H_{32} \dfrac{v_i}{w_i} - \dfrac{v'_i}{w'_i} H_{33} = 0

and you are left with the two DLT equations.

Advertisements
This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

3 Responses to An alternative derivation of the DLT for homographies

  1. a Tayeb Basta says:

    The question is: do the two DLT equations we are left with ensure a single H?

    • vpindarico says:

      Two equations are not enough; as said, you need four or more samples (couples of points) for a total of eight or more equations. Eight are sufficient even if H has nine entries, because H is defined up to a scale factor.
      I add here that no three of the four points must be aligned.

  2. Pingback: Reconstruction of 3D points from images in a calibrated binocular system | Tramp's Trifles

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s