## Abstract

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(n^{2} + 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 language | English (US) |
---|---|

Title of host publication | SIGGRAPH'08 |

Subtitle of host publication | International Conference on Computer Graphics and Interactive Techniques, ACM SIGGRAPH 2008 Papers 2008 |

Publisher | Association for Computing Machinery |

State | Published - 2008 |

Externally published | Yes |

Event | ACM SIGGRAPH 2008 Papers 2008, SIGGRAPH'08 - Los Angeles, CA, United States Duration: Aug 11 2008 → Aug 15 2008 |

### Other

Other | ACM SIGGRAPH 2008 Papers 2008, SIGGRAPH'08 |
---|---|

Country/Territory | United States |

City | Los Angeles, CA |

Period | 08/11/08 → 08/15/08 |

## Keywords

- 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