A nearest neighbor method for efficient ICP

Publisher Website
Google Scholar
Abstract
A novel solution is presented to the Nearest Neighbor Prob- lem that is specifically tailored for determining correspon- dences within the Iterative Closest Point Algorithm. The reference point set is preprocessed by calculating for each point that neighborhood of points which lie within a certain distance of . The points within each -neighborhood are sorted by increasing distance to their respective . At runtime, the correspondences are tracked across iterations, and the previous correspondence is used as an estimate of the current correspondence. If the esti- mate satisfies a constraint, called the Spherical Constraint, then the nearest neighbor falls within the -neighborhood of the estimate. A novel theorem, the Ordering Theorem, is presented which allows the Triangle Inequality to effi- ciently prune points from the sorted -neighborhood from further consideration. The method has been implemented and is demonstrated to be more efficient than both the k-d tree and Elias meth- ods. After iterations, fewer than 2 distance calcula- tions were required on average per correspondence, which is close to the theoretical minimum of 1. Furthermore, af- ter 20 iterations the time expense per iteration was demon- strated to be negligibly more than simply looping through the points.

This publication has 8 references indexed in Scilit: