Lecture Notes in Computer Science

A Modified Soft-Shape-Context ICP Registration System 

of 3-D Point Data 

Jiann-Der Lee

1

, Chung-Hsien Huang

1

, Li-Chang Liu

1

, Shih-Sen Hsieh

1

,  

Shuen-Ping Wang

1

, and Shin-Tseng Lee

2

 

1

 Department of Electrical Engineering, Chang Gung University, Tao-Yuan, Taiwan  

[e-mail], [e-mail], 

[e-mail], {m9321039,m9321042}@stmail.cgu.edu.tw 

2

 Department of Neurosurgery, Chang Gung Memorial Hospital, Lin-Kuo, Taiwan 

[e-mail]  

Abstract. A facial point data registration system based on ICP is presented.  

The reference facial point data are extracted from patient’s pre-stored CT 

images, and the floating facial point data are captured from the patient directly 

by using a touch or non-touch capture device.  A modified soft-shape-context 

ICP, which includes an adaptive dual AK-D tree for searching the closest point 

and a modified objective function, is embedded in this system.  The adaptive 

dual AK-D tree searches the closest-point pair and discards insignificant control 

coupling points by an adaptive distance threshold on the distance between the 

two returned closest points which are searched by using AK-D tree search 

algorithm in two different partition orders.  In the objective function of ICP, we 

utilize the modified soft-shape-context information which is one kind of 

projection information to enhance the robustness of the objective function.  

Relying on registering the floating data to the reference data, the system 

provides the geometric relationship for a medical assistant system and a pre-

operative training.  Experiment results of using touch and non-touch capture 

devices to capture floating point data are performed to show the superiority of 

the proposed system. 

Keywords: ICP, KD-tree, Shape context, registration. 

1   Introduction 

Besl and McKay [8] proposed the Iterative Closest Point algorithm (ICP) which has 

become a popular trend especially in 3D point data registration [10-12] and suggested 

using the K-D tree for the nearest neighbor search.  Later Greenspan [7] proposed the 

Approximate K-D tree search algorithm (AK-D tree) by excluding the backtracking in 

K-D tree and giving more searching bin space.  Greenspan claimed that the 

computation time of the best performance using AK-D tree is 7.6% and 39% of the 

computation time using K-D tree and Elias [7][6], respectively.  One weakness of 

using K-D tree and AK-D tree is that a false nearest neighbor point may be found 

because only one projection plane is considered on partitioning a k-dimension space 

into two groups to build the node tree in one partition iteration.  In order to improve 

724 

J.-D. Lee et al. 

search for the best closest point pair which affects the translation matrixes in ICP, we 

use AK-D tree twice in two different geometrical projection orders for determining 

the true nearest neighbor point to form significant coupling points used in later ICP 

stages.  An adaptive threshold is used in the proposed Adaptive Dual AK-D tree 

search algorithm in order to reserve sufficient coupling points for a valid result.   

In the objective function of ICP, we modify the soft-shape-context idea proposed 

by Liu and Chen [2].  In soft-shape-context ICP (SICP) [2], each point generates a bin 

histogram and a low-pass filter is used to smooth the neighbor histogram values.  For 

3-D point data, the computation time to generate bin histograms for all point data is 

huge so in order to reduce the computation time of using SICP, we only compute two 

bin histograms for the centroid points of reference and floating data.  We propose a 

registration system for facial point data by combining the modified soft-shape-context 

concept and ADAK-D tree.  The floating facial point data are captured on-site from a 

touch or non-touch capture device, and the reference point data are extracted from 

pre-stored CT images in DICOM format.  Experimental results will show that the 

registration results of the proposed system are more accurate than the results of using 

ICP and SICP.  After the registration, surgeons can use mouse to click on the desired 

location on any slice of CT images in the user’s interface or use the digitizer to touch 

the desired location on the patient’s face, and these locations will be shown in the 

registration result sub-window as information survey.  The purpose of the proposed 

system is to rebuild a medical virtual reality environment to assist surgeons for the 

pre-operation assistance and training.   

2   Background of ICP Algorithm 

2.1   The Approximate K-D Tree Search Algorithm 

ICP registers the floating data to reference data by finding the best matching relation 

with the minimum distance between two data sets.  Iterations in ICP are summarized 

as the following 5 steps. 

Step 1. Search the closest neighbor points X

k

 from the reference data set X to a 

given floating data P

K

 of the floating data set P, i.e. d(P

K

, X

k

)=min{d(P

K

, X)}. 

Step 2. Compute the transformation which comprises a rotation matrix R and a 

translation matrix T by using least square method. 

Step 3. Calculate the mean square error of the objective function. 

2

1

)

(

1

)

,

(

∑

=

−

−

=

p

N

i

i

i

p

T

p

R

x

N

T

R

e

 

(1) 

Step 4. Apply R and T to P.  If the stop criterions are reached, then the algorithm 

stops. Otherwise it goes to the second step. 

Step 5. Find the best transform parameters of R and T with the minimum e(R,T). 

In the closest-point-search step, K-D tree and AK-D tree [7] are widely used.  In  

K-D tree, one of k dimensions is used as a key to split the complete space, and the key 

is stored in a node to generate a binary node tree.  The root node contains the 

complete bin regions, and the leaf nodes contain a sub-bin region.  To a query point 

 

A Modified Soft-Shape-Context ICP Registration System of 3-D Point Data 

725 

P

i

, the key of P

i

 is compared with the keys in nodes of  Q to find the most matched 

leaf node q

b

.  All points in the node bin region of q

b

 are computed to find the closest 

point.  The Ball-within-bounds (BWB) test [7] is performed to avoid a false closest 

point in K-D tree.  In AK-D tree, more bin regions are searched for an approximate 

closest point, and the BWB test is discarded to reduce the computations.  

2.2   The Soft-Shape-Context ICP Registration 

The shape context [9] is a description of the similarity of the corresponding shapes 

between two images.  Two shapes are calculated to obtain a transformation relation 

by changing one shape according the minimum square error of the transformation 

matrix equation.  To a given image D, every point d

i

 in D, i.e.

i

d

D

∈

, is computed the 

bin information to generate a bin histogram defined below. 

( )

(

)

{

}

B

k

k

bin

d

d

d

d

k

h

i

j

i

j

i

,..,

1

,

)

(

:

#

=

∈

−

≠

=

  

(2) 

where  B is the total bin number.  An amount of the segmented bins affects the 

similarity result.  If a segmented bin area is too small, the similarity information is too 

noisy.  If a segmented bin area is too big, the similarity information contains the 

rough global information without the local difference information.  To two given 

images D and F, a cost function defined in (3) is computed for the shape similarity. 

( )

( )

[

]

( )

( )

∑

=

+

−

=

B

k

F

D

F

D

DF

k

h

k

h

k

h

k

h

C

1

2

2

1

  

(3) 

Liu and Chen [8] proposed a soft-shape-context ICP (SICP) by adding the shape 

context information into the objective function in ICP.  A symmetric triangular 

function 

)

(

l

K

Triang

 is used to increase the neighbor bin accumulations at K to smooth 

the bins. This triangular function is similar to a low-pass filter to reduce the sensitivity 

around the bin boundaries.  The histogram of the soft shape context is called SSC and 

defined in (4). 

∑

=

⋅

=

)

(

)

(

)

(

)

(

j

j

j

d

label

K

d

K

d

h

Triang

SSC

l

l

l

  

(4) 

where 

l

 is from one to B for a B-bin diagram and the center is d

j

.  Each point d

j

 

generates a B-bin histogram which is one kind of projection information.  The 

objective function in ICP is added with the soft-shape-context information and is 

rewritten in (5). 

∑

⋅

+

−

−

=

i

i

j

shape

i

j

p

q

E

T

p

R

q

T

R

e

)}

,

(

)

(

{

)

,

(

α

  

(5) 

(

)

∑

=

−

=

B

p

q

i

j

shape

i

j

SSC

SSC

p

q

E

1

)

(

)

(

)

,

(

l

l

l

  

(6) 

and 

α is a weighting value to balance values.  Liu and Chen claimed that the 

experimental results of 2-D images of using ICP with soft shape context are superior 

to the results of using ICP and ICP with shape context in [2]. 

726 

J.-D. Lee et al. 

3   The Proposed Adaptive Registration System 

3.1   The Proposed Registration System 

To assist surgeons to track the interested regions in the pre-stored CT images, we 

propose a registration system to register the facial point data captured from 3-D range 

scanning equipment to the facial point data of pre-stored CT images.  The flowchart 

of the proposed registration system is shown in Fig. 1.  

 

Fig. 1. The proposed system flowchart 

The first process is the point-data capture process.  The reference facial point data 

are extracted from pre-stored CT imaging according the grayscale values and the 

desired width, and the floating facial point data are captured immediately from a 

patient in the operation space by using 3-D range scanning equipment.  The second 

process is the trimming process to discard undesired areas of the floating point data to 

reduce computation time and to increase the registration accuracy.  The third process 

is the registration process. We proposed a modified soft-shape-context ICP registrat-

ion including an adaptive dual AK-D tree search algorithm (ADAK-D) for the nearest 

neighbor point searching and an ICP with modified soft shape context information in 

the objective function.  The capture functions of a laser range scanner named 

LinearLaser (LSH II 150) [14] and a 3-D digitizer MicroScribe3D G2X [15] are 

embedded in the system to capture on-site floating point data.  

The system interface is shown in Fig. 2. The red line in the left sub-window of the 

user’s interface is used to assign the desired face width to be extracted from pre-

stored CT imaging or other DICOM images, and we can select the desired slice and 

brightness and contrast of the organs such as skin or bone tissues to obtain the model 

data set.  The right sub-window is used to discard unwanted areas of floating point 

 

A Modified Soft-Shape-Context ICP Registration System of 3-D Point Data 

727 

data and to display the registration result.  After the registration, the new target 

imported from a 3-D digitizer or the target inside the CT image pointed by the mouse 

are able to be displayed in the right sub-window, too. An example is shown in Fig. 2 

where the black point in the registration result of the right sub-window is respected to 

the clicked point in the CT image. 

 

Fig. 2. The system interface. The pointed target inside a CT slice is displayed in the registered 

coordinate as the black point. 

3.2   The Adaptive Dual AK-D Tree Search Algorithm 

In the search structure of K-D tree and AK-D tree, the node tree is generated by 

splitting a k-dimension space along with a fixed geometrical projecting direction 

order.  Because only one projection direction or a projection plane of k-dimensions is 

considered to split the space each time, two truly nearest neighbor points may be 

located at two far sub-root nodes in a binary node tree.  It is assumed that if a nearest-

neighbor point is true, then the same point should be returned in any geometrical 

projection plane order when using AK-D tree or K-D tree. 

Based on this assumption, we utilize AK-D tree twice in two projection axis orders 

of “x,  y,  z” and “z,  y,  x” to examine the queried results.  AK-D tree is used here 

because of its runtime efficiency.  If two returned queried results using AK-D tree in 

two different projection plane orders are very close, then this query point and the 

returned queried point are reserved as significant coupling points, otherwise this 

query point is rejected. The proposed ADAK-D tree is a 5-step process to search and 

determine significant coupling points used in ICP.  In each iteration of ICP, the 

nearest neighbor points are found in the following 5 steps.  It’s assumed that there is a 

minimum 3-D rectangular box  C to contain the complete floating data and M is the 

area of the biggest plane of C.  The initial P is the amount of total floating points. 

Step 1. The node tree of reference/model data is built as Database 1 by using AK-D 

tree in the x-y-z projection axis order iteratively. 

Step 2. The node tree of reference/model data is built as Database 2 by using AK-D 

tree in the z-y-x projection axis order iteratively. 

 

728 

J.-D. Lee et al. 

Step 3. The threshold T is computed by Eq. 7. 

/

T

M

P

=

  

(7) 

Step 4. To a query point from the floating data set, if the distance between two 

returned queried points from Database 1 and Database 2 is smaller than the distance 

T, this query point and the returned queried point from Database 1 are reserved as a 

pair of significant coupling points. 

Step 5. After that all floating points are queried, P is updated by the reserved pair 

number. 

The reserved significant points after using ADAK-D tree are coupling points [12] 

used to compute the best translation and rotation parameters in later ICP stages. In 

order to avoid falling into a local minimum during ICP because of insufficient 

coupling points, T in Step 3 is automatically adjusted by the previous iteration 

information.  If the situation without sufficient coupling points happens, i.e. P 

decreases in this iteration, then T increases in the next iteration, which causes the 

increase of P in the next iteration. 

3.3   The Modified Soft-Shape-Context ICP 

The SICP has a practical weakness when it is used on 3-D point data.  To 3-D point 

data, each point of the floating data and reference data generates its bin histogram in 

the soft-shape-context ICP.  This processing consumes huge computation time and 

causes ICP to appear weaker when compared with other registration algorithms such 

as using Mutual Information [3][4] and Genetic Algorithm (GA)[1][5].  To reduce the 

computation time of generating bin histograms, only two bin histograms of the 

centroid points of the floating and reference data are calculated and the equations of 

(5) and (6) are rewritten as (8) and (9). 

∑

⋅

+

−

−

=

i

c

c

shape

i

j

p

q

E

T

p

R

q

T

R

e

)

,

(

}

)

(

{

)

,

(

α

  

(8) 

(

)

1

( ,

)

( )

( )

c

c

B

shape

C

C

q

p

E

q p

SSC

SSC

=

=

−

∑

l

l

l

  

(9) 

and q

c

 and p

c

 are the centroid points of data sets q and p. 

For the closest point search algorithm in the modified SICP (MSICP), ADAK-D tree 

is used. The proposed system utilizes the modified soft-shape-context ICP together with 

procedures and functions suggested by people of interest in the medical field to build 

a brain virtual reality environment. 

4   Experimental Results 

The synthetic and real experiments are performed to compare the proposed ICP 

registration algorithms against other methods.  In the synthetic experiments, the 

reference point data set is translated by 10 mm along x, y, and z axes as well as rotated 

10 degrees around each of the three axes to generate 6 floating point data sets which 

 

A Modified Soft-Shape-Context ICP Registration System of 3-D Point Data 

729 

labeled as (a), (b), (c), (d), (e), and (f) respectively. In the real experiments, the 

reference data sets are obtained from the pre-stored CT images, and the floating data 

sets are captured from a touch or non-touch capture device.  

4.1   The Comparisons of ICP with AK-D Tree and ADAK-D Tree 

In the synthetic experiments, the reference point data sets with 11291 points and are 

captured by LinearLaser.  Then six floating data sets are generated from each 

reference point data set and listed in Table 1.  The root-square-error (RMS) distance 

[13] is used to measure the performance.  The RMS of registration result of using 

AK-D tree in Table 1(a) is high because the solution was trapped in a local minimum.  

The results in Table 1 have shown that the proposed method has improved the 

accuracies over the AK-D method in most of the cases.  

In the real experiments, using real data, CT facial point data are extracted from pre-

stored CT data first.  The reference data are CT facial point data with 17876 points as 

shown in Fig. 3(a) and the first floating data are laser scan facial point data with 9889 

points as shown in Fig. 3(b).  The RMS of the registration result using AK-D tree as  

 

Table 1. The comparison of registration results of using laser-scan surface data 

AK-D tree method [11] 

ADAK-D tree method 

 

RMS (mm) 

Runtime(sec.) 

RMS (mm) 

Runtime(sec.) 

(a) 16.53 

2.25 

0.19 

5.5 

(b) 6.47 

1.73 

0.19 

5.53 

(c) 2.54 

1.98 

0.19 

5.75 

(d) 2.55 

2.00 

0.19 

5.79 

(e) 2.53 

2.00 

0.19 

5.64 

(f) 2.52 

1.98 

1.06 

5.65 

 

 

 

                (a)                            (b)                          (c)                         (d)