Homography from the Correspondences of Lines

Recently I stumbled upon a task where I had to find a mapping between a camera and a target plane, but with a little twist. I could define line equations in the plane, and once I had captured the image and found the corresponding lines, the problem boiled down to calculating the homography based on line correspondences. Following the famous solution from the Multiple View Geometry book ¹, I arrived at a simple result.

Let’s assume we have a line in the target plane $ L_i $ given by

$$ \begin{equation} L_i = ( a_i^p, b_i^p, c_i^p )^T :\ L_i^T \mathbf{X}^p = 0, \qquad \qquad (1) \label{ref:eq1} \end{equation} $$

where $ \mathbf{X}^p = \begin{pmatrix} x^p \\ y^p \\ 1 \end{pmatrix} $ — point in the target plane. It’s projection in the image we denote as $ l_i $:

$$ l_i = (a_i^i, b_i^i, c_i^i)^T :\ l_i^T \mathbf{ X}^i = 0, $$

$ \mathbf{X}^i = \begin{pmatrix} x^i \\ y^i \\ 1 \end{pmatrix} $ — being a point in the image.
A homography $ \mathbf{H} $ takes a point in the projector plane $ \mathbf{X}^p $ and sends it to the image plane: $$ \mathbf{X}^i = \mathbf{H} \mathbf{X}^p. $$

So for any point in the laser plane satisfying $ (1) $ we can write:

$$ l_i^T \mathbf{H} \mathbf{X}^p = 0. $$

Line $ L_i $ may be represented by any two points $ \mathbf{X}_0^p $ and $ \mathbf{X}_1^p $, so we have two equations for $ L_i \rightarrow l_i $ correspondence:

$$ \begin{equation} \begin{split} l_i^T \mathbf{H} \mathbf{X}_0^p &= 0, \qquad \qquad (2) \\ l_i^T \mathbf{H} \mathbf{X}_1^p &= 0. \end{split} \label{ref:eq2} \end{equation} $$

If the $ j $-th row of the matrix H is denoted by $ \mathbf{h}^{iT} $, then we may write:

$$ \mathbf{H} \mathbf{X}^p = \begin{pmatrix} \mathbf{h}^{1T} \mathbf{X}^p \\ \mathbf{h}^{2T} \mathbf{X}^p \\ \mathbf{h}^{3T} \mathbf{X}^p \end{pmatrix} $$

We can rewrite $ (2) $ in terms of $ \mathbf{h}^{iT} $:

$$ \begin{equation} \begin{split} a_i^i \mathbf{h}^{1T} \mathbf{X}_0^p + b_i^i \mathbf{h}^{2T} \mathbf{X}_0^p + c_i^i \mathbf{h}^{3T} \mathbf{X}_0^p &= 0, \qquad (3) \\ a_i^i \mathbf{h}^{1T} \mathbf{X}_1^p + b_i^i \mathbf{h}^{2T} \mathbf{X}_1^p + c_i^i \mathbf{h}^{3T} \mathbf{X}_1^p &= 0. \end{split} \label{ref:eq3} \end{equation} $$

We can take any two points on $ L_i $, but for the simplicity we may choose these ones:

$$ \begin{equation} \begin{split} \mathbf{X}_0^p = \begin{pmatrix} -\dfrac{c_i^p}{a_i^p} \\ 0\\ 1 \end{pmatrix}, \quad \mathbf{X}_1^p = \begin{pmatrix} 0 \\ -\dfrac{c_i^p}{b_i^p} \\ 1 \end{pmatrix}. \end{split} \qquad \qquad (4) \label{ref:eq4} \end{equation} $$

Plugging $ (4) $ into $ (3) $ and having components of $ \mathbf{H} = \begin{pmatrix} h_{00} & h_{01} & h_{02} \\ h_{10} & h_{11} & h_{12} \\ h_{20} & h_{21} & h_{22} \end{pmatrix} $ we are obtaining:

$$ \begin{equation} \begin{split} a_i^i ( -\dfrac{c_i^p}{a_i^p} h_{00} + h_{02} ) + b_i^i ( -\dfrac{c_i^p}{a_i^p} h_{10} + h_{12} ) + c_i^i ( -\dfrac{c_i^p}{a_i^p} h_{20} + h_{22} ) &= 0, \\ a_i^i ( -\dfrac{c_i^p}{b_i^p} h_{01} + h_{02} ) + b_i^i ( -\dfrac{c_i^p}{b_i^p} h_{11} + h_{12} ) + c_i^i ( -\dfrac{c_i^p}{b_i^p} h_{21} + h_{22} ) &= 0. \end{split} \end{equation} $$

After collecting terms around $ h $ we can write:

$$ \begin{equation} \begin{split} \begin{pmatrix} -a_i^i \dfrac{c_i^p}{a_i^p} & 0 & a_i^i & -b_i^i \dfrac{c_i^p}{a_i^p} & 0 & b_i^i & -c_i^i \dfrac{c_i^p}{a_i^p} & 0 & c_i^i \\ 0 & -a_i^i \dfrac{c_i^p}{b_i^p} & a_i^i & 0 & -b_i^i \dfrac{c_i^p}{b_i^p} & b_i^i & 0 & -c_i^i \dfrac{c_i^p}{b_i^p} & c_i^i \end{pmatrix} \times \\ \times \begin{pmatrix} h_{00} & h_{01} & h_{02} & h_{10} & h_{11} & h_{12} & h_{20} & h_{21} & h_{22} \end{pmatrix}^T = 0 \end{split} \end{equation} $$

or simply:

$$ \begin{equation} \begin{split} \mathbf{A}_i \mathbf{h} = 0. \end{split} \end{equation} $$

Each line correspondence gives two constraints on $ \mathbf{H} $. Given a set of such line correspondences, we obtain a set of equations $ \mathbf{A} \mathbf{h} = 0 $. To solve this, one might use SVD of $ \mathbf{A} $ and the unit singular vector corresponding to the smallest singular value is the solution $ \mathbf{h} $. Note, that lines shouldn’t be all mutually collinear, otherwise we would have an underdetermined system.