Manolis Lourakis

Institute of Computer Science,

Foundation for Research and Technology - Hellas,

Heraklion, Crete, Greece

*Last updated Dec. 17, 2011*

This page concerns `homest`, a C/C++ library for homography estimation that is distributed
under the GNU General Public License (GPL).
A homography (sometimes also called
a *collineation*) is a general plane to plane projective transformation whose estimation from
matched image features is often necessary in several vision tasks. A homography has eight degrees of
freedom and is represented by a non-singular homogeneous 3x3 matrix.
`homest` implements a technique for non-linear, robust homography estimation from matched
image point features. This technique computes a homography estimate that minimizes an appropriate
cost function defined on matching points (currently either non-symmetric transfer error, symmetric
transfer error, Sampson error or reprojection error) and includes robust regression techniques for
coping with outliers. Briefly, the algorithm implemented by `homest` is the following:

- Normalization of point coordinates to improve conditioning as described in R.I. Hartley “In Defense of the Eight-Point Algorithm”, IEEE Trans. on PAMI, Vol. 19, No. 6, pp. 580-593, Jun. 1997.
- Least Median of Squares (LMedS) linear fitting to detect outliers, see P. Rousseeuw, “Least Median of Squares Regression”, Journal of the American Statistics Association, Vol. 79, No. 388, pp. 871-880, Dec. 1984. To ensure adequate spatial distribution of point quadruples over the image, LMedS random sampling employs the bucketing technique proposed in Z. Zhang, R. Deriche, O. Faugeras, Q.T. Luong, “A Robust Technique for Matching Two Uncalibrated Images Through the Recovery of the Unknown Epipolar Geometry”, Artificial Intelligence, Vol. 78, Is. 1-2, pp. 87-119, Oct. 1995. Also published as INRIA RR-2273, May 1994.
- Non-linear refinement of the linear homography estimate by minimizing either (at the user's choice
and in increasing order of computational overhead):
- the (non-symmetric) homographic transfer error in the second image
- the symmetric homographic transfer error between the images
- the Sampson error
- the reprojection error

Note that the minimization of the reprojection error involves the estimation of “corrected” point coordinates for both images, so that the homography relation p'=H*p is satified precisely for the estimated homography H and all matching pairs of corrected points p, p'. Thus, this is the optimal method for estimating a homography but also the most expensive one in terms of the required computations. On the other hand, the approaches employing the symmetric transfer and Sampson errors constitute reasonable treadeoffs between accuracy and running time.

In all cases, the minimization is performed using the Levenberg-Marquardt algorithm, see M.I.A. Lourakis, “levmar: Levenberg-Marquardt Nonlinear Least Squares Algorithms in C/C++”, [web page] http://www.ics.forth.gr/~lourakis/levmar/.

More details on homography estimation can be found in chapter 4 of R. Hartley and A. Zisserman's textbook titled “Multiple View Geometry in Computer Vision”, Cambridge University Press, 2003. Note that

To compile, `homest` requires the levmar
Levenberg-Marquardt non-linear least squares package, which in turn relies on BLAS/LAPACK.

The source code is distributed in a gzip'ed tar file. It has been tested under linux with
gcc/lcc and under windows with
MSVC but should compile with any ANSI compliant C compiler. Remember to include `homest.h` from your C/C++ code.

Current version: homest-1.4

For historical reasons, older versions of `homest` are also available:

- [ homest-1.3 ] :: [ homest-1.2 ] :: [ homest-1.1 ] :: [ homest-1.0 ]

hits since Fri Jul 21 17:06:21 EEST 2006 |