|
The Iterative Closest Point (ICP) algorithm has been used to align point sets under rigid transformations to minimize a root mean squared error in photogrammetry, computer vision, molecular biology, and other applications. We have been investigating a series of topics related to ICP, including (a) bounding the maximum number of iterations required for ICP to converge; (b) extending ICP to curves in 3D and to point sets in higher dimensions; (c) incorporating constraints to the alignment, e.g., finding an alignment in which the two shapes do not intersect; (f) radius of convergence to global maximum.
There are no known bounds on how many iterations (of matchings) are required for ICP to converge other than the trivial exponential upper bound. We have established a linear lower bound and are investigating tightening both upper and lower bounds. To extend the algorithm to curves, instead of simply sampling points in the curve we use the actual representation of the curves and compute the best alignment for a given correspondence between the two curves. We are currently developing algorithm for computing a correspondence between two curves embedded in 3-space.
In another work we have developed a near-linear approximation algorithm for computing the minimum-weight matching between two point sets in the plane. That is, given two sets P and Q of n points each, it finds a one-to-one mapping between P and Q so that the sum of distances between mapped points of P and Q is near minimum. This is the first near-linear algorithm for this problem. It can be plugged into the above ICP framework to align two point sets under rotation and translation.