Homography From Two Orientation- and Scale-Covariant Features

Dániel Baráth, Zuzana Kukelova

Abstract

This paper proposes a geometric interpretation of the angles and scales provided by orientation- and scale-covariant feature detectors, such as SIFT. By deriving two new general constraints on these parameters, the authors introduce a solver for estimating a homography from a minimal set of only two correspondences. This approach significantly reduces the number of iterations required by robust estimators like RANSAC, achieving a 10–100x speedup over the traditional four-point algorithm without sacrificing numerical stability or accuracy.

Introduction

In computer vision, a homography is a transformation that maps points from one plane to another, a fundamental task for applications like image stitching and 3D reconstruction. Traditionally, the "gold standard" for calculating this transformation is the 4-point algorithm. However, when images contain outliers (incorrect matches), robust estimation techniques like RANSAC are employed.

The efficiency of RANSAC is inversely proportional to the number of points required per sample; as the sample size increases, the number of iterations needed to find an outlier-free set grows exponentially. While previous attempts to reduce this number relied on complex "affine" features that are slow to detect, this paper demonstrates how to leverage common, fast features like SIFT or SURF—which provide a point, an orientation, and a scale—to estimate a homography using just two correspondences.

Methods

The authors bridge the gap between simple point coordinates and complex local geometry through a novel mathematical framework:

  1. Geometric Interpretation: The SIFT output is modeled as a local affine transformation. By decomposing the Jacobian of the projection functions, the researchers relate the SIFT scale and rotation directly to the elements of the homography matrix.
Geometric interpretation of orientation- and scale-covariant features
  1. Elimination Ideal Theory: Using algebraic geometry tools (specifically Macaulay2), the authors "eliminated" unknown nuisance variables, such as local surface shear and anisotropic scale. This process yielded two new, general constraints that depend solely on the parameters provided by standard detectors.
  2. The 2-SIFT Solver: By combining these constraints with standard point correspondence equations, a solver was created to determine the 8 degrees of freedom of a homography matrix from only two SIFT features.
  3. Numerical Stability: To ensure accuracy across diverse datasets, a normalization method for orientation and scale parameters was introduced, preventing instability when dealing with noisy data or large coordinate values.

Key Results and Insights

The proposed 2SIFT solver was evaluated against synthetic and real-world datasets, including AdelaideRMF, Multi-H, Malaga, and Strecha.

  • Efficiency Gains: The jump from a 4-point sample to a 2-point sample is transformative for RANSAC. In a scene with 90% outliers, the 2-point solver requires approximately 458 iterations, whereas the 4-point solver requires over 46,000. In real-world tests, this translated to a 30x to 100x speedup.
  • Competitive Accuracy: Despite using half the points, the re-projection error remained comparable to the 4-point (4PT) algorithm. On the Strecha dataset, 2SIFT achieved a mean error of 1.42 pixels in 1.4 seconds, compared to 4PT's 1.25 pixels in 10.2 seconds.
Distribution of average transfer error for different solvers
  • Information at "No Cost": Most modern detectors already calculate orientation and scale for matching purposes. This research proves that this "free" data contains sufficient geometric information to halve the required input points for homography estimation.

Conclusion

By mathematically unlocking the geometric potential of orientation- and scale-covariant features, this paper provides a significantly more efficient path for homography estimation. While the method's accuracy is dependent on the quality of the feature detector's scale and angle estimates, the massive reduction in RANSAC iterations makes it a powerful tool for real-time computer vision applications. Future work may extend these general constraints to non-planar scenes, such as fundamental matrix estimation.

Summary updated

Abstract

This paper proposes a geometric interpretation of the angles and scales which the orientation- and scale-covariant feature detectors, e.g. SIFT, provide. Two new general constraints are derived on the scales and rotations which can be used in any geometric model estimation tasks. Using these formulas, two new constraints on homography estimation are introduced. Exploiting the derived equations, a solver for estimating the homography from the minimal number of two correspondences is proposed. Also, it is shown how the normalization of the point correspondences affects the rotation and scale parameters, thus achieving numerically stable results. Due to requiring merely two feature pairs, robust estimators, e.g. RANSAC, do significantly fewer iterations than by using the four-point algorithm. When using covariant features, e.g. SIFT, the information about the scale and orientation is given at no cost. The proposed homography estimation method is tested in a synthetic environment and on publicly available real-world datasets.
BibTeX
@inproceedings{barath2019homography,
  author = {Dániel Baráth and Zuzana Kukelova},
  title = {{Homography From Two Orientation- and Scale-Covariant Features}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2019},
  url = {https://openreview.net/forum?id=KAuylHNQAJH},
}
Figure