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:
- 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.
- 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.
- 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.
- 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.
- 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