Biomedical Engineering Reference
In-Depth Information
the actual time, with a potential loss of accuracy [11], is to subsample the
original data sets. Criteria for sub-sampling include taking a simple fraction
of the original number [13], using multiple scales of increasing resolution [3],
or taking points in areas away from surface discontinuities [7], in areas of fine
detail [8], and in small random sets for robust transform estimation [14]. A
more accurate and slower alternative is to use the full original data sets, but
organize the closest point search using efficient data structures such as the
octree [10] and k-d tree [6]. The k-d tree is even more efficient,
O
(
N
log
N
),
when higher order features of the points are incorporated in the distance
metric.
1.4.4
Computing Intermediate Motions
Once a set of correspondences has been determined, a motion transform must
be computed that best aligns the points. The most common approach is to use
one of several least squares techniques to minimize the distances between corre-
sponding points [4, 6, 8, 11, 14, 7]. In certain cases [6], individual point contribu-
tions are weighted based on the suspected noise of different portions of the data
sets. More robust estimation using the least median squares technique (cluster-
ing many transforms computed from smaller sets of points) has been tried by
Masuda
et al.
[14]. Alternatively, a Kalman filter has been used to track the inter-
mediate motion at each iteration as new correspondences are computed [6].
More involved techniques compute the motion transform via some form of
search in the space of possible transforms, trying to minimize a cost function
such as the sum of distance errors across all corresponding points. Movements
in transform parameter space are computed based on the changing nature of
the function. Such standard search strategies as Levenberg-Marquardt [10, 12],
simulated annealing [13] and genetic algorithms [9] have been used. Correspon-
dences must be periodically updated during the search to keep the error function
current. Updating too frequently can drastically increase the amount of compu-
tation, while too few updates can lead to an incorrect minimization.
1.4.5
Initialization and Convergence of Searches
As mentioned earlier, an ICP-based refinement occurs after some initial set
of transformations has been determined. Some researchers assume that this
