Recognizing Rigid Patterns of Unlabeled Point Clouds

Rigid structures such as cars or any other solid objects are often represented by finite clouds of unlabeled points. The most natural equivalence on these point clouds is rigid motion or isometry that maintains all inter-point distances. Rigid patterns of point clouds can be fully identified only by complete isometry invariants (also called equivariant descriptors) that should have no false negatives (isometric clouds having different descriptions) and no false positives (non-isometric clouds with the same description). Noise in data motivates a search for invariants that are continuous under perturbations of points in a suitable metric. We propose a continuous and complete invariant for finite clouds of unlabeled points in any Euclidean space. For a fixed dimension, a new metric for this invariant is computable in a polynomial time in the number of points. The talk is based on the CVPR 2023 paper with Daniel Widdowson.