4-points congruent sets for robust pairwise surface registration

Dror Aiger*, Niloy J. Mitra, Daniel Cohen-Or

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

245 Scopus citations


We introduce 4PCS, a fast and robust alignment scheme for 3D point sets that uses wide bases, which are known to be resilient to noise and outliers. The algorithm allows registering raw noisy data, possibly contaminated with outliers, without pre-nltering or denois-ing the data. Further, the method significantly reduces the number of trials required to establish a reliable registration between the underlying surfaces in the presence of noise, without any assumptions about starting alignment. Our method is based on a novel technique to extract all coplanar 4-points sets from a 3D point set that are approximately congruent, under rigid transformation, to a given set of coplanar 4-points. This extraction procedure runs in roughly O(n2 + k) time, where n is the number of candidate points and k is the number of reported 4-points sets. In practice, when noise level is low and there is sufficient overlap, using local descriptors the time complexity reduces to O(n + k). We also propose an ex tension to handle similarity and affine transforms. Our technique achieves an order of magnitude asymptotic acceleration compared to common randomized alignment techniques. We demonstrate the robustness of our algorithm on several sets of multiple range scans with varying degree of noise, outliers, and extent of overlap.

Original languageEnglish (US)
StatePublished - 2008
Externally publishedYes
EventACM SIGGRAPH 2008 Papers 2008, SIGGRAPH'08 - Los Angeles, CA, United States
Duration: Aug 11 2008Aug 15 2008


OtherACM SIGGRAPH 2008 Papers 2008, SIGGRAPH'08
Country/TerritoryUnited States
CityLos Angeles, CA


  • Affine invariant ratio
  • Computational geometry
  • Largest common pointset(LCP) measure
  • Pairwise surface registration
  • Partial shape matching
  • Scan alignment

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Human-Computer Interaction


Dive into the research topics of '4-points congruent sets for robust pairwise surface registration'. Together they form a unique fingerprint.

Cite this