Outlier Robust ICP for Minimizing Fractional RMSD

Jeff M. Phillips, Ran Liu, Carlo Tomasi

Abstract

We describe a variation of the iterative closest point (ICP) algorithm for aligning two point sets under a set of transformations. Our algorithm is superior to previous algorithms because (1) in determining the optimal alignment, it identifies and discards likely outliers in a statistically robust manner, and (2) it is guaranteed to converge to a locally optimal solution. To this end, we formalize a new distance measure, fractional root mean squared distance (FRMSD), which incorporates the fraction of inliers into the distance function. We lay out a specific implementation, but our framework can easily incorporate most techniques and heuristics from modern registration algorithms. We experimentally validate our algorithm against previous techniques on 2 and 3 dimensional data exposed to a variety of outlier types.

Introduction

Point-set registration—the process of aligning a "data" set of points to a "model" set—is a fundamental task in computer vision, medical imaging, and robotics. The standard tool for this task is the Iterative Closest Point (ICP) algorithm. However, standard ICP suffers from a significant limitation: it assumes every point in the data set has a corresponding point in the model.

In real-world applications, data is often corrupted by sensor noise, occlusions, or spurious "new data" that does not belong to the model. Standard ICP attempts to account for these outliers in its global average, which inevitably skews the final alignment. While variants like Trimmed ICP (TrICP) have been developed to address this, they often require the user to know the fraction of outliers in advance or rely on computationally expensive heuristic searches to estimate that fraction. This paper introduces Fractional ICP (FICP), a robust evolution that automatically identifies and ignores outliers by minimizing a novel objective function.

Methodology: Fractional RMSD

The core innovation of this work is the Fractional Root Mean Squared Distance (FRMSD). Unlike traditional metrics that use a fixed set of points, FRMSD includes the inlier fraction $f$ directly as a variable in the cost function:

$$FRMSD \propto \frac{1}{f^\lambda} \cdot RMSD(f)$$

In this formulation, $RMSD(f)$ represents the root mean squared distance of the best-fitting fraction $f$ of the data. As $f$ decreases, the $RMSD$ naturally decreases because the algorithm only considers the points that fit the model best. To prevent the trivial solution where the algorithm selects only a single perfectly matching point ($f \approx 0$), the term $\frac{1}{f^\lambda}$ acts as a penalty that increases as the fraction of points decreases.

The FICP Algorithm

The FICP algorithm extends the traditional ICP loop by adding a third optimization step. Each iteration consists of:

  1. Correspondence: For each data point, identify the closest point in the model.
  2. Transformation: Calculate the optimal rotation and translation for the current subset of points.
  3. Fraction Optimization: Determine the optimal fraction $f$ that minimizes the FRMSD.

This three-way optimization is mathematically guaranteed to converge to a local optimum, providing a rigorous foundation for the robust registration process.

Experimental Setup

The researchers validated FICP using a combination of 2D and 3D datasets:

  • SQUID Database: A collection of 1,100 2D fish contours used for large-scale statistical testing.
  • Stanford 3D Scanning Repository: Classic 3D models including the Bunny, Happy Buddha, and Dragon.

To test robustness, three types of synthetic noise were introduced: Occlusion (removing portions of the model), Deformation (shifting point positions), and New Data (adding random background noise).

Key Insights

The Role of $\lambda$

The parameter $\lambda$ determines the algorithm's aggressiveness in discarding outliers. Through statistical analysis involving Poisson processes for outliers and Gaussian noise for inliers, the authors identified ideal "general purpose" values: $\lambda \approx 1.3$ for 2D data and $\lambda \approx 0.95$ for 3D data.

Efficiency and Convergence

Unlike Trimmed ICP, which often requires a "Golden Ratio Search" (a nested, expensive search for the optimal fraction), FICP finds the optimal $f$ in $O(|D|)$ time within each iteration. Furthermore, FICP demonstrates a larger "funnel of convergence" than TrICP. By dynamically adjusting the inlier set, the algorithm is less likely to be pulled into poor local minima by distant outliers during the initial stages of alignment.

Results

Experimental results highlight several advantages of the FICP approach:

  • Computational Speed: FICP achieved approximately a 6x speedup over Trimmed ICP on the SQUID dataset by eliminating the need for nested searches.
  • Robust Accuracy: In scenarios with 25% outliers, FICP consistently recovered the true inlier fraction ($f \approx 0.75$) and maintained a low RMSD, whereas standard ICP was significantly skewed.
  • Real-World Application: On overlapping scans of the Stanford Dragon (taken 48° apart), FICP successfully aligned the overlapping regions (such as the tail) while ignoring the non-overlapping sections that typically cause standard ICP to fail.

Conclusion

FICP provides a statistically robust and computationally efficient framework for point-set registration. By incorporating the inlier fraction directly into the optimization objective, it removes the need for prior knowledge of outlier ratios. While FICP remains a local optimizer and is subject to local minima if the initial alignment is poor, its modular nature allows it to be combined with other modern ICP enhancements, such as point-to-plane metrics or advanced data structures like $d^2$-trees, to further improve performance in complex environments.

Summary updated

Abstract

We describe a variation of the iterative closest point (ICP) algorithm for aligning two point sets under a set of transformations. Our algorithm is superior to previous algorithms because (1) in determining the optimal alignment, it identifies and discards likely outliers in a statistically robust manner, and (2) it is guaranteed to converge to a locally optimal solution. To this end, we formalize a new distance measure, fractional root mean squared distance (frmsd), which incorporates the fraction of inliers into the distance function. We lay out a specific implementation, but our framework can easily incorporate most techniques and heuristics from modern registration algorithms. We experimentally validate our algorithm against previous techniques on 2 and 3 dimensional data exposed to a variety of outlier types.
BibTeX
@inproceedings{phillips2007outlier,
  author = {Jeff M. Phillips and Ran Liu and Carlo Tomasi},
  title = {{Outlier Robust ICP for Minimizing Fractional RMSD}},
  booktitle = {3DIM},
  year = {2007},
  url = {https://openreview.net/forum?id=3BVg81HUdxA},
}
Figure