# Multiple View Geometry

\( \newcommand{\T}{\mathsf{T}} \newcommand{\ve}[1]{\mathbf{#1}} \newcommand{\M}[1]{\mathbf{#1}} \newcommand{\costAML}{J_{\mathrm{AML}}} \newcommand{\costALS}{J_{\mathrm{ALS}}} \newcommand{\de}{\mathbf{\theta}} \newcommand{\estALS}{\widehat{\de}_{\mathrm{ALS}}} \newcommand{\costDIR}{J_{\mathrm{DIR}}} \newcommand{\Lambdab}{\mathbf{\Lambda}} \newcommand{\cov}[2][]{\Lambdab_{#2}^{#1}} \newcommand{\estDIR}{\widehat{\de}_{\mathrm{DIR}}} \newcommand{\estGAML}{\widehat{\de}_{\mathrm{GAML}}} \newcommand{\estAML}{\widehat{\de}_{\mathrm{AML}}} \newcommand{\etab}{\mathbf{\eta}} \newcommand{\kappab}{\mathbf{\kappa}} \)

A classic problem in computer vision, called *multiple view geometry*, is to recover the three-dimensional structure of a scene
given several images taken from different vantage points. Working primarily with Wojciech Chojnacki, I am studying various
compelling unsolved problems. What makes multiple view geometry so challenging is that the underlying projective models
lead to non-linear errors-in-variables parameter estimation problems. Hence Wojciech and I find ourselves working at the interface
of various disciplines such as numerical analysis, projective geometry, statistics and computer science.

We are particularly interested in:

- devising new parameter estimation techniques which result in estimates with desirable properties (e.g. unbiased and consistent);
- devising new unconstrained optimisation methods which are simpler to implement and faster than established schemes such as Levenberg--Marquardt;
- deriving and imposing constraints associated with various mathematical models in multiple view geometry;
- creating new constrained optimisation methods which naturally and reliably enforce constraints.

Hence our research endeavours can be characterised as both theoretical and practical.

## 1 Robust Multiple Homography Estimation: An Ill-Solved Problem

Images in two views of world points lying on a planar surface are
related by a homography matrix. Planar surfaces are ubiquitous in urban
environments, and this makes estimating multiple homography matrices
from image measurements between two views an important step in many
applications such as augmenting reality, stitching and warping images,
calibrating cameras, finding a metric reconstruction, and detecting
non-rigid motion. Because of the diverse utility of homography matrices,
researchers often exploit the task of estimating multiple homographies
to demonstrate the merits of robust multi-structure estimation methods.
In fact, some robust multi-structure estimation methods, such as
*multiRANSAC* ^{[1]}, were specifically
designed to address the multi-homography estimation problem. However, an
inadvertent oversight has crept into multi-structure estimation methods,
one that persists in all state-of-the-art methods that we are familiar
with, namely the failure to recognise that a set of homographies that
each of these schemes produces is actually *not* a genuine set of
homographies between two views of the same scene. A collection of
homography matrices forms a valid set only if the matrices satisfy
consistency constraints implied by the rigidity of the motion and the
scene. If the constraints are not deliberately enforced, they are not
satisfied in typical scenarios. Hence, one of the fundamental problems
in estimating multiple homography matrices is to find a way to enforce
the consistency constraints---a task reminiscent of that of enforcing
the rank-two constraint in the case of the fundamental matrix
estimation.

The consequence of homographies being incompatible can clearly be
appreciated by examining the extent to which a fundamental matrix
constructed from an incompatible set of homographies can represent the
epipolar geometry of the scene. As is well known, given a homography
\( \M{H} \) between the first and second views induced by a plane in the
scene, the underlying fundamental matrix \( \M{F} \) can be written as
$$
\begin{align}
\label{eq:12}
\M{F} = \M{H}^{-\T}[\ve{e}]_{\times},

\end{align}
$$
where \( \ve{e} \) represents the epipole in the first image. If
\( {\M{H}_i}_{i=1}^{I} \) is a set of homographies, then, as it turns out,
the epipole in the first image is a fixed point of any homology with
matrix of the form \( \M{H}^{-1}_j\M{H}_i \) and can be retrieved as the
eigenvector corresponding to a non-repeated eigenvalue of any of the
\( \M{H}^{-1}_j\M{H}_i \)'s. If the homography matrices \( \M{H}_i \) are
incompatible, the various homology matrices \( \M{H}^{-1}_j\M{H}_i \) will
also be incompatible and will lead to different estimates of the epipole
in the first image. This in turn will lead to different estimates of the
fundamental matrix, as exemplified in Figure X. Moreover, if a
fundamental matrix is constructed by selecting a particular homography
matrix \( \M{H}_{i_0} \) in \eqref{eq:12} , then even though the resulting
fundamental matrix may be compatible with \( \M{H}_{i_0} \), it will not be
compatible with the remaining homographies \( \M{H}_i \), \( i \neq i_0 \).
Hence, given multiple incompatible homographies, it is possible to
construct multiple incompatible fundamental matrices. This subtlety is
overlooked in all robust multi-structure estimation methods that we are
familiar with.

Explicit formulae for all constraints that must be satisfied in order
for a collection of homographies to form a valid set have so far eluded
the vision community. It was only as recently as 2011 that a decisive
answer pertaining to even just the *number* of constraints was given
^{[2]} ^{[3]}. There are
several reasons why knowledge of explicit formulae for homography
constraints would be advantageous:

- with explicit constraints it would be possible to devise new homography estimation methods that enforce full compatibility without recourse to latent variables;
- one could investigate new global optimisation methods for
multi-homography estimation, analogous to what has recently been
achieved for fundamental matrix estimation
^{[4]}^{[5]}; and - one could establish a new generation of robust multi-structure fitting methods that, unlike existing methods, yield estimates with consistent epipolar geometry.

In this paper we take a step toward achieving the goal of determining all homography constraints. We derive two new sets of consistency constraints and use them to measure, for the first time, the extent to which separately estimated homographies are mutually incompatible. Our findings indicate that none of the state-of-the-art multi-structure estimation methods adequately address the problem of multiple homography estimation, as none of them enforce consistency constraints. Consequently, robust multiple homography estimation continues to be an ill-solved problem.

**Fig 1.**Comparison of epipolar lines associated with two fundamental matrices computed from two separately estimated homographies. The epipolar lines associated with the two fundamental matrices do not overlap, and thereby demonstrate that the two homographies do not share the same epipolar geometry and hence are incompatible.

## 2 Enforcing Consistency Constraints in Uncalibrated Multiple Homography Estimation using Latent Variables.

An approach is presented to estimating a set of interdependent homography matrices linked together by latent variables. The approach allows enforcement of all underlying consistency constraints while accounting for the arbitrariness of the scale of each individual matrix. The input data is assumed to be in the form of a set of homography matrices individually estimated from image data with no regard to the consistency constraints, appended by a set of error covariances, each associated with a corresponding matrix from the previous set. A statistically-motivated cost function is introduced for upgrading, via optimisation, the input data to a set of homography matrices satisfying the constraints. The function is invariant to a change of any of the individual scales of the input matrices. The proposed approach is applied to the particular problem of estimating a set of homography matrices induced by multiple planes in the 3D scene between two views. An optimisation algorithm for this problem is developed that operates on natural underlying latent variables, with the use of those variables ensuring that all consistency constraints are satisfied. Experimental results indicate that the algorithm outperforms previous schemes proposed for the same task and is fully comparable in accuracy with the `gold standard' bundle adjustment technique, rendering the whole approach both of practical and theoretical interest. With a view to practical application, it is shown that the proposed algorithm can be incorporated into the familiar RANSAC technique so that the resulting modified scheme is capable of robust fitting of fully consistent homographies to data with outliers.

## 3 Sampson Distance Based Joint Estimation of Multiple Homographies

Two images of a scene consisting of multiple flat surfaces are related by a collection of homography matrices. Practitioners typically estimate these homographies separately thereby violating inherent inter-homography constraints that arise naturally out of the rigid geometry of the scene. We demonstrate that through a suitable choice of parametrisation multiple homographies can be jointly estimated in a manner so as to satisfy all inter-homography constraints. Unlike the cost functions used previously for solving this problem, our cost function does not correspond to fitting one set of homography matrices to another set of homography matrices. Instead, we utilise the Sampson distance for homography matrix estimation and operate directly on image data points. By using the Sampson distance and working directly on data points, we expedite the application of a vast amount of knowledge that already exists for Sampson-distance-based single homography or fundamental matrix estimation. The estimation framework reported in this paper establishes a new baseline for joint multiple homography estimation and at the same time raises intriguing new research questions. The work may be of interest to a broad range of researchers who require the estimation of homography matrices as part of their solution.

## 4 References

[1]: M. Zuliani, C. S. Kenney, and B. S. Manjunath, “The multiRANSAC
algorithm and its application to detect planar homographies,” in *Proc.
int. conf. image processing*, 2005, vol. 3, pp. 153–156.

[2]: W. Chojnacki and A. van den Hengel, “A dimensionality result for
multiple homography matrices,” in *Proc. 13th int. conf. computer
vision*, 2011, pp. 2104–2109.

[3]: W. Chojnacki and A. van den Hengel, “On the dimension of the set
of two-view multi-homography matrices,” *Complex Anal. Oper. Theory*,
vol. 7, no. 2, pp. 465–484, 2013.

[4]: Y. Zheng, S. Sugimoto, and M. Okutomi, “A branch and contract
algorithm for globally optimal fundamental matrix estimation,” in *Proc.
IEEE conf. computer vision and pattern recognition*, 2011, pp.
2953–2960.

[5]: Y. Zheng, S. Sugimoto, and M. Okutomi, “A practical
rank-constrained eight-point algorithm for fundamental matrix
estimation,” in *Proc. IEEE conf. computer vision and pattern
recognition*, 2013, pp. 1546–1553.