A Geometric and Hypothesis-Based Method for Low-Overlap, Sparse, and Featureless Point Set Matching

This article proposes a general solution for point set matching that effectively addresses the challenges of low-overlap, sparse, or featureless point set matching (LSFPM). Unlike previous methods that mainly rely on feature or neighborhood similarity that often fail under such difficult conditions, this work proposes a Geometry-based Point Matching (GPM) method. GPM first introduces two geometric concepts: the “Structural Element” (SE) and the “Superstructural Element” (SSE), both of which are constructed based on local geometric structures. The SSE is an enhanced version of the SE. A descriptor for the SE, called the SE Descriptor (SED), is designed to encode the SE and facilitate an efficient geometry-based similarity metric. We demonstrate that the cosine similarity of SEDs is invariant to scale and rotation. Subsequently, a SE Matching Maximization (SEMM) problem is formulated to identify a size-penalized SSE set that maximizes the sum of similarities. This problem is efficiently solved using the proposed SEMM-MCMC (Markov Chain Monte Carlo) algorithm. The matched SSEs then vote on corresponding point matches, generating high-confidence one-to-one matches, low-confidence one-to-one matches and one-to-many matches. Finally, the InferMatch algorithm is proposed to jointly assess low-confidence one-to-one point set matching while simultaneously distinguishing one-to-many point set matching. The GPM approach can also complement other feature-based and motion-based methods. It has been extensively validated on both synthetic and real datasets, demonstrating its versatility in addressing various point set matching problems, and is not limited to the LSFPM problem. Extensive experiments on diverse datasets, including SPair-71k, UAVDT, VisDrone2021-MOT, and SparseMatch, further demonstrate the robustness and versatility of GPM. The proposed approach significantly improves matching performance under challenging conditions and effectively addresses key limitations of existing point set matching methods.