Abstract
Recent increase in the availability of warped images projected onto a curved manifold, especially omnidirectional spherical ones, coupled with the success of higher-order assignment methods, has sparked an interest in the search for improved higher-order matching algorithms on warped images due to projection. Although, currently, several existing methods “flatten” such 3D images to use planar graph/hypergraph matching methods, they still suffer from severe distortions and other undesired artifacts, which result in inaccurate matching. Alternatively, current planar methods cannot be trivially extended to effectively match points on images warped on curved manifold. Hence, matching on these warped images persists as a formidable challenge. In this paper, we pose the assignment problem as finding a bijective map between two graph induced simplicial complexes, which are higher-order analogues of graphs. We propose a constrained quadratic assignment problem (QAP) that matches each p-skeleton of the simplicial complexes, iterating from the highest to the lowest dimension. The accuracy and robustness of our approach are illustrated on both synthetic and real-world spherical/warped (projected) images with known ground-truth correspondences. We significantly outperform existing state-of-the-art spherical matching methods on a diverse set of datasets.
Introduction: The Challenge of Warped Image Matching
In computer vision, "point correspondence" is the task of finding the same physical point across different images. While well-studied for flat (planar) images, this task becomes significantly more difficult when images are warped onto curved manifolds, such as omnidirectional camera views, fish-eye lenses, or the curved surface of the human retina in OCT scans.
The traditional approach is to "flatten" these 3D images into 2D planes. However, flattening introduces severe geometric distortions and non-linear artifacts that degrade the performance of standard matching algorithms. Conversely, existing planar matching methods do not scale well to the intrinsic geometry of a sphere or a cylinder. This research proposes matching points directly on the curved manifold without destructive flattening, achieving up to a 49.7% reduction in matching error compared to state-of-the-art methods.
Methodology: Higher-Order Simplicial Complexes
The proposed framework moves beyond simple graph matching by utilizing Simplicial Complexes, which are higher-order generalizations of graphs.
1. Building the Complex
A graph-induced simplicial complex is constructed from landmark points. Unlike a standard graph, which only considers points (0-simplices) and edges (1-simplices), this structure includes higher-order "simplices" such as triangles (2-simplices) and tetrahedrons (3-simplices). This captures the local topology of the space more effectively than simple pairwise distances.
2. Affine Weight Vectors and Geodesics
To describe each point, the authors use "affine weight vectors" based on barycenters of neighboring simplices. These act as locally invariant descriptors that handle complex transformations (rotation, scaling, shear) better than simple distance metrics. Crucially, the model uses geodesic distances—the shortest path along the curved surface—rather than straight-line Euclidean distances to respect the intrinsic geometry of the manifold.
3. Hierarchical Matching (QAP)
The matching is formulated as a Quadratic Assignment Problem (QAP), solved hierarchically. The algorithm matches the highest-dimensional structures first (e.g., triangles) and uses those successful matches to constrain the matching of lower-dimensional structures (edges and points). This top-down approach acts as a powerful filter: if a group of points forming a higher-order simplex matches well, it is highly likely the individual points within that group are correct, significantly reducing the search space and error rates.
Experimental Results
The researchers evaluated their approach on several datasets, including five warped/spherical datasets (Kamaishi, Chessboard, Desktop, Parking, Table) and four difficult 2D planar datasets (Magazine, Building, Books, Butterfly). They also highlighted applications in medical imaging, specifically 3D fundus images of the eye (OCT scans).
Key Findings
- Superior Accuracy: On warped manifolds, the proposed method significantly outperformed existing spherical matching methods. For instance, in the Parking dataset, it achieved 0.0% error, compared to 23.7% for the next best traditional higher-order method (Tensor).
- Significant Error Reduction: The method achieved up to a 49.7% reduction in matching error on warped images and a 42.2% reduction on flat planar images compared to state-of-the-art baselines.
- Robustness: Ablation studies demonstrated high resilience to affine transformations, including 40° rotations, reflections, scaling, and shear, maintaining low error rates where other descriptors like ORB or BRISK failed.
Conclusion and Future Directions
By representing landmark points as simplicial complexes and solving a hierarchical QAP, this method provides a robust and accurate solution for point correspondence on curved manifolds. While the method currently relies on pre-detected landmark points, the authors suggest that future work could involve integrating these combinatorial structures into Spherical CNNs to capture even deeper latent structures in warped image data.
Summary updated