Generalized 4-Points Congruent Sets for 3D Registration

The 4-Points Congruent Sets (4PCS) algorithm is a state-of-the-art RANSAC-based algorithm for registering two partially overlapping 3D point sets using raw points. Unlike other RANSAC-based algorithms, which try to achieve registration by searching for matching 3-point bases, it uses a base of two coplanar pairs of points to reduce the search space matching bases. In this work, we first generalize the algorithm by allowing the two pairs to fall on two different planes which have an arbitrary distance, i.e. Degree of separation, between them. Furthermore, we show that increasing the degree of separation exponentially decreases the search space of matching bases. Using this property, we show that using the new generalized base allows for more efficient registration than the original 4PCS base type. We achieve a maximum run-time improvement of 83.10% for 3D registration.