Abstract
This paper presents a new algorithm for matching two sets of 3D data points that has a better polynomial time complexity, O(N exp 2.5), than previous techniques. There is no restriction on the amount of missing point-pair correspondence between the two sets of data, provided that a majority of the data points between the two images are consistent in terms of rigidity constraints. The algorithm makes use of the Hough bucketing technique for determining the optimal solution, with a modest 1D Hough space for the rotational space search. The search in the translational space is carried out sequentially. No restrictions on all six transformation parameters are imposed, and any arbitrarily shaped surface can be registered, provided a unique solution exists. The only assumption made is that the surface be piecewise smooth to allow surface normal calculations on most regions except at discontinuity boundaries. Experimental results showed successful registrations of a simple bottle and a couple of anatomical surfaces captured in 64 x 64 range images with the execution time of about half a minute per registration on a personal computer. (Author)