4-points Congruent Sets for Robust Surface Registration

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-filtering or denoising 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²+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 extension 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.

Results:

Reconstruction from raw scans using 4-points congruent sets. Reconstruction results from nine input scans of a shinny water jug. Neighboring scans have 40% overlap or less, and required an average of 16 seconds for fully automatic alignment starting from arbitrary initial poses. Pairwise alignment results are robust even with low overlap. Typical pairwise alignments are shown in images on the left-half, where for visualization we roughly mark the overlap regions in blue. The final alignment result (right-half) is obtained without any data smoothing, outlier removal, local ICP refinement, global error distribution, or any assumption about starting alignment.

Advantage of directly registering raw noisy data. (Left) Denoising the original scans before registration can be harmful: Given two scans P and Q, we pre-smooth them, use the smoothed versions to compute local descriptors to establish correspondence and compute an aligning transform. We use this transform to align the original dataset Q to P, and finally smooth the combined models. (Right) Directly aligning the noisy data using 4PCS, and then smoothing the result yields a higher quality surface. In both cases, the same MLS operator is used for surface smoothing. Further reduction of noise from the left column models results in significant loss of high frequency features.

Extracting affine invariant congruent 4-points. (Left) Given a base B={a,b,c,d} consisting of four (approximately) coplanar points, we extract the two ratios r₁ and r₂. (Middle) For any point-pair {q₁,q₂}, there can be two assignments corresponding to {a,b}, and another two assignments corresponding to {c,d} leading to 4 possible intermediate points. These points are computed as e₁=q₁+r₁(q₂-q₁) and e₂=q₁+r₂(q₂-q₁). (Right) Now, given a set of coplanar points Q, we want to extract a 4-points set which is congruent to the given base B up to affine transforms. For each pair of points {q₁, q₂} in Q, we compute four intermediate points as described. For simplicity, we just indicate two points per point-pair in the figure. A set of 4 points is approximately congruent to given B, if e₁ ~ e₂. In this example, {a,b,c,d} is approximately congruent to {q₅, q₃, q₄, q₁}.

Aligning aerial scans of the old city of Jerusalem. Given two aerial scans P and Q, in arbitrary initial poses, we align them using 4PCS algorithm. Use of wide base for alignment results in stable alignment even for such flat aerial scans. The small overlap between the scans makes this a challenging example. In the zoom-inset, we show the improvement in alignment after three steps of ICP refinement, a step orthogonal to our algorithm.

Aligning building facades. Given two building facades in arbitrary starting poses, 4PCS successfully aligns the scans. This is a challenging case for automatic registration since the scans comprise of noisy data with large flat featureless regions. This example has very few distinct features that can be reliably detected using any local descriptors. (Middle) The result is without any ICP refinement. (Right) We color the error in 4PCS alignment when compared to the final position after ICP refinement. In our scale, we set the length of the bounding box diagonal of the model to unity. Points with error more than 0.01 are marked in blue. Notice that even without ICP refinement our algorithm aligns the scans very reliably.