Geometric Polynomial Constraints in Higher-Order Graph Matching

Mayank Bansal, Kostas DaniilidisarXiv 2014 · arXiv

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

Consistency check between overlapping point sets using shared polynomial roots.

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.

Average accuracy vs. number of samples for scenarios (a) without outliers and (b) with outliers across different noise levels (σ).

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

Abstract

Correspondence is a ubiquitous problem in computer vision and graph matching has been a natural way to formalize correspondence as an optimization problem. Recently, graph matching solvers have included higher-order terms representing affinities beyond the unary and pairwise level. Such higher-order terms have a particular appeal for geometric constraints that include three or more correspondences like the PnP 2D-3D pose problems. In this paper, we address the problem of finding correspondences in the absence of unary or pairwise constraints as it emerges in problems where unary appearance similarity like SIFT matches is not available. Current higher order matching approaches have targeted problems where higher order affinity can simply be formulated as a difference of invariances such as lengths, angles, or cross-ratios. In this paper, we present a method of how to apply geometric constraints modeled as polynomial equation systems. As opposed to RANSAC where such systems have to be solved and then tested for inlier hypotheses, our constraints are derived as a single affinity weight based on $n>2$ hypothesized correspondences without solving the polynomial system. Since the result is directly a correspondence without a transformation model, our approach supports correspondence matching in the presence of multiple geometric transforms like articulated motions.
BibTeX
@misc{bansal2014geometric,
  author = {Mayank Bansal and Kostas Daniilidis},
  title = {{Geometric Polynomial Constraints in Higher-Order Graph Matching}},
  year = {2014},
  eprint = {1405.6261},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1405.6261},
}
Figure