Fast and Globally Optimal Rigid Registration of 3D Point Sets by Transformation Decomposition

1 INTRODUCTION

• Existing global registration methods use BnB to guarantee a global solution, but their excessive runtimes compromise practicability.Source: §1 · pp. 1–2
• BnB is exponential in parameter-space dimensionality, while bound evaluation can require O(N^2) pairwise point calculations.Source: §1 · p. 2

• Three orders of magnitude faster than existing global methods and approximately 10 times faster than Go-ICP.Source: §1 · p. 2

1 INTRODUCTION

• Translation-invariant vectors let the method search rotation first, then translation, decomposing the six-dimensional BnB problem into two three-dimensional searches.Source: §1 · p. 2
• The proposed 3D Integral Volume accelerates bound evaluation in both the rotation and translation searches.Source: §1 · p. 2

2.1 Global Point Set Registration Methods

• Prior global methods include Go-ICP’s nested rotation-and-translation BnB and approaches with costly or restrictive requirements; this method also decomposes the search and accelerates it with 3DIV.Source: §2.1 · p. 3

2.2 Rotation Search

• The paper’s raw-point rotation search is contrasted with feature-match methods and with MCIRC-ML, described as the best-performing pure rotation search method before this work.Source: §2.2 · p. 3

Contributions

• Translation-invariant vectors align through the original sets’ relative rotation while remaining unchanged by translation, enabling rotation search followed by translation search.Source: Contributions · p. 3
• The method uses a distance-based consensus-set objective and derives a geometric bound for evaluating it.Source: Contributions · p. 3
• The proposed 3D Integral Volume accelerates bound evaluation, and its construction time is described as extremely small.Source: Contributions · p. 3
• Three orders of magnitude faster than state-of-the-art global methods and approximately 10 times faster than Go-ICP accelerated by DT.Source: Contributions · p. 3

3.1 Problem Formulation of 3D Rigid Point Set Registration

• Rigid registration seeks a transformation in SE(3) composed of rotation and translation, scoring alignment by consensus maximization with an L∞ distance.The paper describes the consensus strategy as inherently robust to outliers.Source: §3.1 · p. 4

3.2 Transformation Decomposition by Translation Invariant Vectors

• Two 3-DOF searches replace direct 6-DOF optimization: TIV alignment finds the relative rotation, then aligned points are searched for translation.The rotation of the TIVs is also the optimal relative rotation of the original point sets.Source: §3.2 · p. 4
• Long TIVs are selected because all pairwise differences grow quadratically, short vectors are noise-sensitive, and rotation preserves length, narrowing possible matches.TIVs are constructed by subtracting pairs of points.Source: §3.2 · p. 4
• The pipeline applies 3DIV-accelerated global searches to both stages, using selected TIVs for rotation and rotationally aligned point sets for translation.The two original point sets are aligned after both optimal rotation and translation are found.Source: Figure 2 · p. 5

4.1 Geometric Matching under The L2 Distance

• The rotation objective maximizes the number of TIV consensus pairs whose Euclidean distance is at most the inlier threshold.The optimal rotation is selected given the moving and fixed TIV sets and the predefined threshold.Source: §4.1 · p. 5

4.2 Representation of Rotation And Geometric Bound

• Angle-axis vectors place all rotations inside a π-ball, embedded in a cube that BnB subdivides and prunes using bounds.The uncertainty ball around each rotated moving point supplies the geometric basis for an upper bound on consensus count.Source: §4.2 · pp. 5–6

4.3 The Geometric Bound under L∞Distance

• The L∞ formulation replaces the uncertainty ball with a centered cube, making consensus checks amenable to exact, efficient 3DIV evaluation.The cubic bound is looser than the ball or patch bounds, but supports faster bound calculations.Source: §4.3 · p. 6, §4.4 · p. 7

4.4 Fast Bound Evaluation Based on 3DIV

• 3DIV extends integral-image counting to 3D, storing point counts for cuboids defined by each node and the starting vertex.Its construction adds each point to nodes satisfying coordinate inequalities relative to that point.Source: §4.4 · p. 6
• Counts for arbitrary cuboids are recovered from eight node values, enabling rapid checks for fixed points inside consensus cubes.When uncertainty-cube vertices do not coincide with volume nodes, the method checks a slightly larger cuboid.Source: §4.4 · pp. 6–7

5 EFFICIENT TRANSLATION SEARCH

• The optimal rotation is applied to the moving point set before the translation between that rotated set and the fixed set is searched globally.The translation search is also solved in the BnB framework.Source: §5 · p. 7
• Translation is parameterized by a 3D vector, with a sufficiently large fixed coordinate range producing a cubic initial branch and cubic sub-branches.The translation objective uses the same predefined inlier threshold as the rotation objective.Source: §5 · pp. 7–8
• The translation-search bound is rapidly evaluated with 3DIV built from the scene set, and BnB returns the translation maximizing the consensus objective.The algorithm subdivides translation cubes and prunes branches whose bounds do not exceed the best current score.Source: §5 · p. 8

6.1 Synthetic Data

• The synthetic tests used 11 models and compared runtime, angular error, translation error, and RMS under outliers, missing points, and noise.Models were downsampled to 500 points; methods that did not return a solution within 1,000 s were terminated.Source: §6.1 · pp. 8–9
• With the same rotation kernel, TIV-based decomposition reduced runtime by three orders of magnitude versus Glob-GM-ML, which failed to converge within 1,000 s in all experiments.TIV-MCIRC-ML and TIV-MCIRC had similar runtimes for outliers and missing points, while TIV-MCIRC-ML was faster with perturbed points.Source: §6.1 · pp. 9–10
• TIV-3DIV was three orders of magnitude faster than APM and Glob-GM-ML and approximately ten times faster than Go-ICP accelerated by DT; its accuracy was good enough for a global method.Its accuracy could easily be improved with local refinement.Source: §6.1 · p. 10

6.2 The Scalability of TIV-3DIV

• Rotation and translation search times increased slowly as point counts grew, while 3DIV construction time was very small.TIV construction and selection were not negligible because selection included sorting; the Hand model was tested at different point counts with TIV count set to 20% of points.Source: §6.2 · p. 11, Figure 13 · p. 11

6.3.1 Stanford Scanning Models

• On Stanford scanning models, TIV-3DIV was fastest in every experiment and had accuracy among the best; TIV-MCIRC-ML ran faster than TIV-MCIRC on these difficult registrations.Glob-GM-ML did not finish within 3,600 s, and Go-ICP failed on Armadillo and Happy Buddha.Source: §6.3.1 · p. 11, Table 4 · p. 14

6.3.2 Indoor Scan Data

• For the living-room point clouds, TIV-MCIRC and TIV-MCIRC-ML achieved the smallest translation error, Go-ICP the smallest angular error, and TIV-3DIV remained fastest with acceptable angular and translation errors.Go-ICP’s convergence threshold was 0.1 m.Source: §6.3.2 · p. 12

6.3.3 Clinical Data

• On the clinical registration task, only TIV-based methods finished within 3,600 s, and TIV-3DIV ranked first in both runtime and accuracy.TIV-MCIRC and TIV-MCIRC-ML errors were too large; preprocessing included manual segmentation to avoid excessive searching from large outliers.Source: §6.3.3 · p. 13, Table 6 · p. 15

7 CONCLUSION

• Transformation decomposition reduces a six-dimensional rigid-transformation search to a three-dimensional rotation search followed by a three-dimensional translation search, accelerating BnB optimization.The method also uses an L∞-based consensus-set objective.Source: §7 · p. 15
• A 3D Integral Volume speeds evaluation of the objective-function bounds in each branch of the parameter space.Source: §7 · p. 15
• Experiments on synthetic and real data found the proposed method three orders of magnitude faster than existing global methods and approximately ten times faster than distance-transform-accelerated Go-ICP.Source: §7 · p. 15