Outlier Robust ICP for Minimizing Fractional RMSD

Jeff M. Phillips, Ran Liu, and Carlo Tomasi

The most common distance used to determine the similarity between atoms of two protein structures, between corresponding landmarks from two robots' perspectives, between 3D reconstruction range data from two angles is the ubiquitous root mean squared distance (RMSD), or lesions on a skin cancer patient. 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. (See publication here.)

This heuristic approach is complemented by work on the first polynomial algorithm to provably approximate the minimum RMSD distance between two point sets under rotation and translation. (See publication here.)