Introduction
Establishing correspondences between two sets of points—such as 3D landmarks and their 2D projections—is a foundational challenge in computer vision, often referred to as the "chicken-and-egg" problem of pose estimation. To determine camera pose, one needs correspondences; conversely, to find correspondences, a pose model is typically required. Traditional approaches like RANSAC rely on a "solve-and-test" loop, which can fail when no initial matches are available or when multiple independent motions are present. This paper proposes a higher-order graph matching framework that leverages geometric constraints directly, bypassing the need for a global transformation model or appearance-based features.
Methodology: From Invariants to Constraints
While traditional higher-order matching relies on geometric invariants (like angles or cross-ratios) that remain constant across views, many problems—such as Perspective-n-Point (PnP)—lack such intra-image invariants. The authors shift the focus from invariants to constraints.
The Resultant Trick
The core innovation lies in representing geometric configurations as univariate polynomials. For a minimal set of points (e.g., three points for the P3P problem), the geometric constraints can be analytically reduced to a single polynomial equation, $q_S(x) = 0$.
If two overlapping sets of points, $S$ and $S'$, belong to the same valid geometric model, their respective polynomials must share a common root. To quantify this consistency without explicitly solving the equations, the authors utilize the Sylvester resultant. The magnitude of the smallest singular value of the Sylvester matrix serves as an affinity score for hyper-edges in a graph matching framework. These scores populate an affinity tensor, which is then optimized using a sparse tensor power iteration algorithm to find the most consistent set of correspondences.
Experimental Evaluation
The method was rigorously tested using synthetic simulations across three geometric problems:
- P3P: Three-point Calibrated Absolute Pose.
- 3P1: Three-plus-One Calibrated Relative Pose.
- up2p: Two-point Calibrated Absolute Pose for a vertical camera.
Simulations involved 10 "inlier" 3D points with varying levels of Gaussian pixel noise and random "outlier" points, reaching up to 100% of the inlier count.
Key Results and Discussion
The proposed method demonstrates high precision and robustness. In noise-free environments, the algorithm achieves 100% matching accuracy with a relatively small number of samples.
As shown in the performance plots, the system maintains high accuracy even in the presence of significant outliers, provided that image noise remains low (typically $\sigma < 0.5$ pixels). A key advantage of this graph-matching approach is its inherent support for articulated or multi-model motion. Unlike global solvers, it can successfully group and match points moving independently, as demonstrated in the up2p simulations.
Limitations
Despite its theoretical elegance, the approach faces practical challenges. Constructing the affinity tensor is computationally intensive, requiring significant parallelization (e.g., via GPUs) for real-time applications. Furthermore, performance degrades under high noise conditions ($\sigma > 1.0$ pixel), where geometric constraints become less distinct, reducing the reliability of the Sylvester resultant as a consistency metric.
Conclusion
By reformulating geometric matching as a polynomial consistency problem, this work provides a robust alternative to traditional pose estimation loops. The use of resultants allows for the evaluation of geometric hypotheses without explicit model solving, offering a flexible framework for complex scenarios like articulated motion. Future work will focus on optimizing the computational pipeline and validating the method on real-world datasets.
Summary updated