Biomedical Engineering Reference
In-Depth Information
The first such effort was by Chen and Medioni [7]. They have improved the
ICP algorithm by minimizing the distance from the sensed point to the nearest
estimated plane approximating the model surface. They begin by finding the
data point in the second set that is closest to a line through the point in the
first set in the direction of its estimated surface normal. Then the tangent plane
at this intersection point is used as the surface approximation. Yet finding the
estimated plane involves another iterative procedure which further adds to the
computation complexity. They reduced the complexity by selecting some impor-
tant points on the smooth surfaces of the object and used these points for the
registration. This works well if the smooth surfaces are uniformly distributed
over the object, which is not the case for many free-form objects. More accu-
rate but time-consuming estimates of the surface have also been used, such as
octrees [10], triangular meshes [11], and parametric surfaces [12].
Most researchers have used, the simple Euclidean distance in determining
the closest point [3, 4, 6, 7, 8, 9, 11, 12, 13, 14]. Fewer have used higher dimensional
feature vectors, such as including the estimated surface normal [15].
1.4.2
Thresholding Outliers
Most of the early algorithms were limited by the original assumption that one
data set was a subset of the other [4, 7, 8, 11, 12, 14]. Proposals to bypass this
limitation have involved imposing a heuristic threshold on either the distance
allowed between points in a valid pairing [6, 9, 10, 13, 15] and the deviation of
the surface normals of corresponding points [15]. Any point pairs which exceed
these thresholds or constrains are assumed to be incorrect. These thresholds
are usually predefined constants related to the estimated accuracy of the initial
transformations and can be difficult to choose robustly. Dynamically adjustable
thresholds have been based on both the distribution of the distance errors at
each iteration [6] and a fuzzy set classification of inlier and outliers correspon-
dences [16].
1.4.3
Computational Requirements
In all of the techniques, computing potential correspondences is generally the
most time-consuming step. In a brute-force approach [4, 15, 12], an
O
(
N
2
)
number of comparisons is performed to find N pairings. One way to reduce
