ADAPTIVE DUAL AK-D TREE SEARCH ALGORITHM FOR ICP REGISTRATION
APPLICATIONS
Jiann-Der Lee1, Shih-Sen Hsieh1, Chung-Hsien Huang1, Li-Chang Liu1, Chien-Tsai Wu2,3, Shin-Tseng
Lee2,3, and Jyi-Feng Chen2,3
1
Department of Electrical Engineering, Chang Gung University, Tao-Yuan, Taiwan
2
Medical Augmented Reality Research Center, Chang Gung Memorial Hospital, Lin-Kou, Taiwan
3
Department of Neurosurgery, Chang Gung Memorial Hospital, Taiwan
ABSTRACT suitable to outlier data. One weakness of using K-D tree
and AK-D tree is that a false nearest neighbor point may be
An algorithm for finding coupling points plays an important found because one projection plane of k planes is
role in the Iterative Closest Point algorithm (ICP) which is considered on partitioning a k-dimension space into two
widely used in registration applications in medical and 3-D groups to build the node tree. Based on the efficiency of
architecture areas. In recent researches of finding coupling AK-D tree’s computation, we use AK-D tree twice in two
points, Approximate K-D tree search algorithm (AK-D tree) different geometrical projection orders for determining true
is an efficient nearest neighbor search algorithm with significant coupling points which influence the registration
comparable results. We proposed Adaptive Dual AK-D tree accuracy in later ICP stages. An adaptive threshold in the
search algorithm (ADAK-D tree) for searching and proposed Adaptive Dual AK-D tree search algorithm
synthesizing coupling points as significant control points to (ADAK-D tree) is used to reserve sufficient coupling points
improve the registration accuracy in ICP registration for a valid result. Facial point data of the same object from
applications. ADAK-D tree utilizes AK-D tree twice in different capture equipments are tested in the experiments.
different geometrical projection orders to reserve true Experimental results show that the registration of using
nearest neighbor points used in later ICP stages. An ADAK-D tree is more robust than the registration of using
adaptive threshold in ADAK-D tree is used to reserve AK-D tree.
sufficient coupling points for a smaller alignment error. This paper is organized as in the following. The
Experimental results are shown that the registration details of ADAK-D tree algorithm are presented in Section
accuracy of using ADAK-D tree is improved more than the 2. The experiment results on facial surface data are shown
result of using AK-D tree and the computation time is in Section 3. We discuss the future research directions in
acceptable. Section 4.
2. ADAPTIVE DUAL AK-D TREE SEARCH
ALGORITHM
1. INTRODUCTION
In the search structure of K-D tree and AK-D tree, the node
Registrations on computer medical imaging have been used tree is generated by splitting a k-dimension space along with
to assistant medical doctors and surgeons for tracking a fixed geometrical projecting direction order. For example,
specific locations such as tumors or developing a medical 3-D data are continuously split into two groups by
reality environment in last decades. Besl and McKay [3] projecting data into x, y, and z axes iteratively to build the
proposed the Iterative Closest Point algorithm (ICP) which node tree. Because only one projection direction or a
has become a popular registration trend [1][4][5][6][7]. The projection plane of k-dimensions is considered to split the
K-D search method (K-D tree) was used in [3] as the nearest space each time, two truly nearest neighbor points may be
neighbor search algorithm. Greenspan and Yurick [2] located at two far sub-root nodes in a node tree. The
proposed the Approximate K-D tree search algorithm (AK- backtracking in K-D tree reduces this error but it takes
D tree) by excluding the backtracking in K-D tree and massive runtime. To a true geometrical nearest-neighbor
giving a more tolerable minimum distance between query point, the same point should be returned in any geometrical
and returned point sets. Greenspan and Yurick claimed that projection plane order when using AK-D tree or K-D tree.
the computation time of the best performance using AK-D A simple example is shown in Fig. 1. Four points as P1, P2,
tree is 7.6% and 39% of the computation time using K-D P3 and P4 are split by the x-y axis order first in Fig. 1(a). A
tree and Elias respectively. It is indicated that AK-D tree is given query point Q1 which is really close to P2 recognizes
1424403677/06/$20.00 ©2006 IEEE 177 ICME 2006
Authorized licensed use limited to: RMIT University. Downloaded on July 03,2010 at 11:58:07 UTC from IEEE Xplore. Restrictions apply.
P4 as its closest point in Fig. 1(a). On the other hand, if 4 automatically adjusted by the previous iteration information.
points are split by the y-x axis order, then the Q1’s closest If the situation without sufficient coupling points happens,
point is P2. i.e. P decreases in this iteration, then T increases, which
cause the increase of P in the next iteration.
3. EXPERIMENTAL RESULTS
Facial surface data from laser scan and face-camera
equipments were used to examine the performances of using
AK-D tree and ADAK-D tree in the synthetic experiments.
Laser-scan facial surface data were 11291 points captured
by LinearLaser (LSH II 150) made by 3dfamily Technology
(a) (b) Co.. Face-camera facial surface structured data were 4255
FIGURE 1. 2-D split results based on different projection axis points captured by DigiFace Face Camera made by
orders. (a) the split result based on the x-y axis order, and (b) the 3dfamily Technology Co.. In the synthetic experiments, the
split result based on the y-x axis order reference data were translated and rotated to generate
variant floating data. In the cases of (a), (b) and (c) as in
Based on this assumption, we utilize AK-D tree twice in Table 1 and Table 2, the reference data were translated by
two projection axis orders of “x, y, z” and “z, y, x” to 10 mm along x, y, and z axes respectively to generate 3
examine the queried results. AK-D tree is used here floating data sets. In the cases of (d), (e) and (f), the
because of its runtime efficiency. If two returned queried reference data were rotated by 5 degrees around X, Y and Z
results using AK-D tree in two different projection plane axes respectively to generate the other 3 floating data sets.
orders are very close, then this query point and the returned To measure the performance, root-square-error (RMS)
queried point are reserved as significant coupling points, distance [8] is the measurement unit. The numerical
otherwise this query point is rejected. comparisons of registration results of laser scan facial
ADAK-D tree is a 5-step process to search and surface data and face-camera surface data are shown in
determine significant coupling points used as control points Table 1 and Table 2 respectively. The visual registration
in ICP. In each iteration in ICP, the nearest neighbor points results in Table 1 of using AK-D tree and ADAK-D tree are
are found in the following 5 steps. Assume that there is a shown in Figure 2 and Figure 3 respectively.
minimum 3-D rectangular box C to contain the complete
floating data and M is the area of the biggest plane of C. TABLE 1. The comparison of registration results of laser scan
The initial P is the amount of total floating points. facial surface data.
Step 1. The insert tree of reference/model data is built as AK-D tree method [2] ADAK-D tree method
Database 1 by using AK-D tree in the projection axis order RMS Computation RMS Computation
of “x, y, z” iteratively. (mm) time (second) (mm) time (second)
(a) 16.536 2.25 0.197 5.5
Step 2. The insert tree of reference/model data is built as
(b) 6.474 1.734 0.196 5.531
Database 2 by using AK-D tree in the projection axis order
(c) 2.54 1.984 0.197 5.75
of “z, y, x” iteratively. (d) 2.551 2 0.198 5.797
Step 3. The threshold T is computed by Eq. 1. (e) 2.538 2 0.196 5.64
M (f) 2.527 1.985 1.062 5.656
T= (1)
P TABLE 2. The comparison of registration results of face-camera
Step 4. To a query point from the floating data set, if the surface data.
distance between two returned queried points from Database AK-d tree method [2] ADAK-d tree method
1 and Database 2 is smaller than the distance T, this query RMS Computation RMS Computation
point and the returned queried point from Database 1 are (mm) time (second) (mm) time (second)
reserved as a pair of significant coupling points. (a) 1.584 3.141 0.198 4.375
Step 5. After that all floating points are queried, P is (b) 1.502 3.156 0.192 4.329
updated by the reserved pair number. (c) 1.387 3.14 1.64 4.39
The reserved significant points after using ADAK- (d) 1.71 3.156 1.572 4.453
D tree are coupling points [6] to compute the best (e) 1.71 3.172 0.196 4.375
translation and rotation parameters in later ICP stages. (f) 1.531 3.125 0.401 4.329
Avoiding falling into an extremely bad local minimum in
ICP because of insufficient coupling points, T in Step 3 is
178
Authorized licensed use limited to: RMIT University. Downloaded on July 03,2010 at 11:58:07 UTC from IEEE Xplore. Restrictions apply.
FIGURE 3. The visual registration results using ADAK-D tree on
laser scan facial surface data in Table 1. (a) the visual result in
Table 1(a), (b) the visual result in Table 1(b), (c) the visual result
in Table 1(c), (d) the visual result in Table 1(d), (e) the visual
result in Table 1(e), and (f) the visual result in Table 1(f).
About the computation time in the experiments,
(a) (b) face-camera data use more bits on storage and computation
than laser scan data, and the more bits result in consuming
more runtime. The RMS of registration result of using AK-
D tree in Table 1(a) is high because the solution is trapped
into a local minimum. In Table 1, the computation time of
using ADAK-D tree is 2 to 3 times the computation time of
using AK-D tree because ADAK-D tree requires extra time
on Step 3 and 4.
(c) (d) In the third experiment, CT facial surface data and
laser scan facial surface data are registered. CT facial
surface data are extracted from CT data first. The model
data are CT facial surface data with 17876 points as shown
in Fig. 4(a), and the floating data are laser scan facial
surface data with 9889 points as shown in Fig. 4(b). The
RMS of the registration result using AKD-tree as in Fig. 4(c)
is 2.475 mm and the runtime is 3.219 seconds. The RMS of
(e) (f)
FIGURE 2. The visual registration results using AK-d tree on the registration result using ADAK-D tree as in Fig. 3(d) is
laser scan surface data in Table 1. (a) the visual result in Table 1.163 mm and the runtime is 4.438 seconds.
1(a), (b) the visual result in Table 1(b), (c) the visual result in
Table 1(c), (d) the visual result in Table 1(d), (e) the visual result
in Table 1(e), and (f) the visual result in Table 1(f).
(a) (b)
(a) (b)
(c) (d)
FIGURE 4. The visual registration results from laser scan facial
surface data to CT facial surface data. (a) the CT facial surface
(c) (d) data, (b) the laser scan facial surface data, (c) the registration result
using AK-D tree, and (d) the registration result using ADAK-D
tree.
From the experiment results, ADAK-D tree has
more robust registration results for an ICP registration
rather than AK-D tree in most cases.
(e) (f)
179
Authorized licensed use limited to: RMIT University. Downloaded on July 03,2010 at 11:58:07 UTC from IEEE Xplore. Restrictions apply.
4. CONCLUSIONS AND FUTURE DIRECTIONS Reconstructive Plastic Surgery,” Proceedings of IEEE
International Symposium on Biomedical Imaging: Macro to Nano,
A novel nearest neighbor search algorithm for vol. 1, pp. 740-743, 2004.
determining significant coupling points has been presented.
[6] T. Jost and H. Hugli, “A Multi-resolution ICP with Heuristic
This proposed method utilizes AK-D tree twice in different Closest Point Search for Fast and Robust 3D Registration of Range
projection direction orders to determine the true nearest Images,” Proceedings of Fourth International Conference on 3-D
neighbor point. An adaptive threshold for a true nearest Digital Imaging and Modeling (3DIM), pp. 427-433, 2003.
neighbor point matins sufficient control points and enhances
the robustness. From the experimental results of facial point [7] V. Patoglu and R.B. Gillespie, “A Closest Point Algorithm For
data, the ADAK-D tree method has more robust registration Parametric Surfaces With Global Uniform Asymptotic Stability,”
accuracies than the AK-D tree method in most cases, and First Joint Eurohaptics Conference and Symposium On Haptic
the runtime of using ADAK-D tree doesn’t always linearly Interfaces For Virtual Environment And Teleoperator Systems
increase because fewer significant coupling points are used (WHC 2005), pp. 348-355, 2005.
in later ICP stages. In the current experiments, the
[8] V. Zagrodsky, V. Walimbe, C.R. Castro-Pareja, J.X. Qin, J.M.
operation time to capture facial surface data requires 5 to 15 Song, and R. Shekar, “Registration-assisted Segmentation of Real-
minutes according to desired resolutions, and this period is time 3-D Echocardiographic Data Using Deformable Models,”
not preferred in a practical situation. In the future, more IEEE Trans. On Medical Imaging, vol. 24, No. 9, Sept. 2005, pp.
surface data captured from variant equipments will be tested. 1089-1099.
For example, we like to perform the registration between
pre-stored CT data and the outline data captured from a 3-D
digitizer in a short period to compute the coordinate relation
between coordinates of an indoor operation space and a
medical virtual environment. The final purpose of this
study is to assist medical doctors on searching desired
information immediately within pre-stored medical imaging
during an operation simulation.
ACKNOWLEDGEMENTS
This work was supported by Ministry of Economic Affairs,
Taiwan under Technology Development Program for
Academia (TDPA) in the project of developing a Brain
Medical Augmented Reality System with Grant No. 94-EC-
17-A-19-S1-035.
REFERENCES
[1] D. Chetverikov, D. Stepanov and P. Krsek, “Robust Euclidean
Alignment of 3D Point Sets: The Trimmed Iterative Closest Point
Algorithm,” Image and Vision Computing, vol. 23, No. 3, 2005, pp.
299-309.
[2] M. Greenspan and M. Yurick, “Approximate K-D Tree Search
for Efficient ICP,” Proceedings of Fourth International
Conference on 3-D Digital Imaging and Modeling (3DIM), pp.
442-448, 2003.
[3] P.J. Besl and N.D. McKay, “A Method for Registration of 3D
Shapes,” IEEE Transactions on Pattern Analysis and Machine
Intelligence, vol. 14(2), pp. 239-256, 1992.
[4] S. Rusinkiewicz and M. Levoy, “Efficient Variants of the ICP
Algorithm,” Proceedings of Fourth International Conference on 3-
D Digital Imaging and Modeling (3DIM), pp. 145-152, 2001.
[5] S.M. Bhandarkar, A.S. Chowdhury, Y. Tang, J. Yu and E.W.
Tolllner, “Surface Matching Algorithms Computer Aided
180
Authorized licensed use limited to: RMIT University. Downloaded on July 03,2010 at 11:58:07 UTC from IEEE Xplore. Restrictions apply.
