A 3D Matching Method for Organic Training Samples Alignment Based on Surface Curvature Distribution

doi:10.4236/ojmi.2011.12006

Paper Menu >>

Journal Menu >>

Open Journal of Me di cal Imaging, 2011, 1, 43-47

doi:10.4236/ojmi.2011.12006 Published Online December 2011 (http://www.SciRP.org/journal/ojmi)

A 3D Matching Method for Organic Training Samples

Alignment Based on Surface Curvature Distribution

Guangxu Li, Hyoungseop Kim, Joo Kooi Tan, Seiji Ishikawa, Akiyoshi Yamamoto

Kyushu Institute of Technology, Kitakyushu, Japan

E-mail: [email protected]

Received October 19, 2011; revised November 18, 2011; accepted November 28, 2011

Abstract

The fundamental step to get a Statistical Shape Model (SSM) is to align all the training samples to the same

spatial modality. In this paper, we propose a new 3D alignment method for organic training samples match-

ing, whose modalities are orientable and surface figures could be recognized. It is a feature based alignment

method which matches two models depending on the distribution of surface curvature. According to the af-

fine transformation on 2D Gaussian map, the distances between the corresponding parts on surface could be

minimized. We applied our proposed method on 5 cases left lung training samples alignment and 4 cases

liver training samples alignment. The experiment results were performed on the left lung training samples

and the liver training samples. The availability of proposed method was confirmed.

Keywords: Training Samples Alignment, Statistical Shape Model, Gauss Map, K-Means

1. Introduction

Due to utilizing the priori information of shapes, Statis-

tical Shape Model (SSM) method shows concise and

robust for segmentation, analyzing and interpreting ana-

tomical objects from medical datasets [1]. The basic idea

in model building is to statistic the pattern of legal varia-

tion in the shapes and spatial relationships of structures

from a collection of training samples. A key step in

building a model involves establishing a dense corre-

spondence between shape boundaries and surface figures.

It is important to align all training samples in a common

coordinate frame firstly [2].

The training shapes alignment problems can be con-

cluded that the transformation between the same anat-

omy images at different modalities or represented by one

modality at different time [3]. In point sets based align-

ment method, the set of identified points is sparse com-

pared with the original image content, which makes for

relatively fast optimization procedures, but is difficult to

confirm the corresponding points. Some novel strategies

are reported to optimize measures such as the average

distance between each representative point, or iterated

minimal distances metric [4]. These methods are mostly

used to find rigid or affine transformations. Feature-

based alignment is largely founded on the use of differ-

ential geometry to describe local surface feature. Ac-

cording to the difference of local feature on parameter-

ized space, an appropriate transformation could be re-

quired. The statistical model building would benefit from

this technology. Because generally the landmarks posi-

tions always involve the local features of surface.

In this paper, we propose a feature-based alignment

method to reconcile the training samples of organs field

whose shape could be approximated by multi-faces. Bene-

fit from the Gauss map, the surface Gaussian curvature

could be reflected on the 2D spherical surface. Due to the

distributional independence of each face through Gauss

mapping, we can decide the modality by comparing the

distributional character.

In Section 2 we will review the Gauss-Bonnet theorem

applying to piecewise surface concisely. Based on it, we

will analyze an approximated Gauss mapping method for

triangular surface. After that, a mesh filter to eliminate

the illogical mapped points is introduced. In Section 3,

we will describe the alignment method on Gauss map.

Here, the K-means clustering method is used to obtain

the same quantity of the respective points, which are

utilized to remark the modalities of the models. And we

also give a simple solution of the alignment parameters.

Evaluation method incorporating corresponding land-

mark points is introduced in the last section. Some ex-

perimental results will be illustrated after that.

G. X. LI ET AL.

2. Surface Generation and Its Gauss Map

2.1. Organic Polygonal Surface Generation

The choice of shape representation is the first fundamen-

tal decision when designing statistical shape models. The

surface meshes representation is one of the most generic

methods. As well as it is convenient to general land-

marks using mesh resample technique. To get polygonal

surface training samples from body CT images, firstly,

we should extract the region of interest and represent it

by binary voxel data. The mesh is extracted by Marching

Cubes Algorithm introduced by Lorensen and Cline [5].

But the smoothness of the surface mesh generated by this

algorithm is quite rough. The mesh mean filter is op-

tional for mesh smoothing.

2.2. Gauss Map of Polygonal Surface

The Gaussian curvature of a point on a surface is an in-

trinsic measure of curvature, i.e., its value depends only

on how distances are measured on the surface. The Gauss-

Bonnet theorem links total curvature of a surface to its

topological properties [6,7]. The theorem also has inter-

esting consequences for triangles. It could be accounted

as follows:

Suppose D is a simply connected region on the surface,

ƏD is a piecewise smooth closed curve, kg is called the

geodesic curvature of the curve. Assume αj are the outer

angles of the vertices of ƏD. Then

dd π

pgj

KA ks









 (1)

If the geodesic curvature is smooth, then

dπ







 (2)

The integral operation will be replaced by the accu-

mulated sum operation, when we consider the piecewise

polygonal surface.

Figure 1(a) shows a polygonal cell with three faces

adjacent a vertex Vi. The number of the faces is not lim-

ited by three, we denote it by s. Gj represents one point in

the unit triangular face ViVi+1Vi+2, and the norm nj joints

this triangular face at it. The norm nj is given by









iii i

VVV V

nVVV V



 

 (3)

As the normal direction of each polygonal plane face

is special, mapping this unit face to a point on the Gaus-

sian sphere still makes sense.

G is the corresponding

point of G

j on Gauss map, in Figure 1(b), and it also

used to represent the mapping of the face ViVi+1Vi+2. Ac-

cording to the angular variety of the two vertices Gj, Gj+1,

(a)

(b)

Figure 1. One polygonal cell around a vertex and its Gauss

mapping. (a) The norms of triangular faces adjacent this

vertex; (b) One polygonal face unit on Gauss map.

the line segments GjM, MGj+1 could be projected to the

spherical segment 1





. In the same way, mapping of

the vertex Vi is loaded inside of the simple connection of

the region 11

jjs

GG G









, because the original surface

is smooth and continuous.

Support αj are the outer angles of the cell. Because the

Gaussian curvature on the Gauss sphere is one every-

where, from the Equation (2), the area of this cell Ai

could be simplified by

2(2)



 



 (4)

where βj is the intersection angle between two spherical

segments. Since spherical segments 1

GG

 and 1







are the mapping of the segments 1

j and

GMG



GNG







 respectively, if denote the projective angle of

βj as





, it is not difficult to proof that



 approaches

to βj.

As well as











then

2π





 (5)

The right part of the Equation (5) is the total Gauss

curvature at vertex Vi. So, this equation illustrates that

the area of the spherical polygonal cell on Gauss map

could be applied to estimate the curvature of the original

piecewise polygonal surface. When we minimized the

G. X. LI ET AL.45









area Ai, the norm of the vertex Vi could be approximated

by the sum of the norms of the faces around Vi.

2.3. Remove the Scattered Mapping Vertices

At some parts of polygonal surface, such as irregular

indentation and the boundary of object, the vigorous

change of curvature induces some vertices scattered after

gauss mapping. Here, a mesh filter is designed to reduce

the influence from that.

Apply the spherical coordinate to express the points on

Gauss map. Define θi ג [0,π] is the inclination angle

measured form a fixed zenith direction, and φi ג [0,2π) is

the azimuth angle. Then the variance of the spherical

coordinates could be formulated by Equation (6), which

describes how dispersive the point Vi to its neighbors,





iijij ijij

ijijij ij

EE EE

EEEE

 





 

 

 





 

 

 

(6)

where ,

ijji ijji







 

and E is the mean op-

erator. The “noise point” could be defined as which is

bigger than threshold.

3. Alignment on Gauss Map

3.1. Distribution of Local Surface Feature on

Gauss Map

On the Gauss map, we can facilitate to obtain the estima-

tion of geometric attributes of surface such as curvature

distribution, uniform continuity and smoothness. To the

same graphic pattern, this estimation has the similarity in

some sense.

In Fi gu re 2(a), we demonstrate mapping a 2D shape to

Gauss sphere. The cambered surface patches which have

continuous curvature are mapped continuous regions on

Gauss map spherical surface. The plane part P0P1 is con-

centrated into a point n0. The patch P1P2 is convex line

segment with a low curvature, the mapping is continuous

from n1 to n2 with a relative dispersive distribution. The

concave patch P2P3P0 has a bevel near the point P3, is

reflected region to n2n3n4n5 is seemed separated. Since

the discontinuity of curvature among the regions of sur-

face, the mapping points aggregate to some separations.

The modalities could be inferred from this “texture of

curvature”. Figure 2(b) shows a Gauss map of one case

of liver polygonal triangular surface. The mapping dis-

tribution is distinct.

3.2. Matching Solution by K-Means Clustering

Unfold the Gauss map according to the spherical coordi-

nates, as Figure 3(a), cluster of the point sets is obvious.

The intensive regions correspond to the main faces

which are relative flat on the original polygonal surface

of organic model. Following it, if find a metric to meas-

ure the distances between the main surfaces, the optimi

zation of alignment method could be performed.

The cluster method is used to describe the distribution

of the point sets. In detail, here we use the K-means clus-

tering algorithm to divide the point sets on 2D Gauss

map. The centroid of a cluster, denoted as the representa-

tive point, is the average point in the multidimensional

space defined by the dimensions. In a sense, it is the

center of gravity for the respective cluster. In this method,

the distance between two clusters is determined as the

difference between centroids. Reference [8] provides a

boosting algorithm which uses kd-tree structure. The

number of the classifiers is 21 and the initial seed points’

positions are set averagely.

The solution of the rigid parameters solution is based

on Berthold K.P. Horn [9]. The author provides a method

to decompose the effects from the translating, scale and

n1n3

n5n0

(a) (b)

Figure 2. Gaussian sphere. (a) Gauss mapping of 2D model;

(b) Gauss mapping of liver triangular surface.

(a) (b)

Figure 3. Alignment method illustration. (a) Representative

points obtained by k-means method. Shown on unfolded

Gauss map; (b) Rotation parameter optimization.

G. X. LI ET AL.

rotation. It is a coarse alignment method and could give a

simple solution when all the points are coplanar. In that

case, it has been inferred that to require the translation

minimize, just align the centers of gravity of two point

sets. Referring to the scale factor, actually it needn’t be

considered, for all surface maps are in the unit sphere.

The remaining task about the rotation is the solution of a

least squares problem in a plane, as Figure 3(b). The

vector vl,i points from one representative point to the

centroid on Gauss map of referent model, Corresponding

it vr,i is on the sample model. αi represents the angle be-

tween these two vectors pair. The solution of the rotation

amounts to minimize the

,,li ri

vv



The optimized deviation angle θ could be calculated

sin S



 2

(7)

where ,



,,liri

Cvv





,,li ri

Svv



4. Experiments Results

4.1. Similarity Criterion

Due to the intense variety of organ shapes, seeking for

corresponding points seems to be a difficult task. There

is ever lack of reliable measures to quantify model qual-

ity yet. In this study, the selection of the label points de-

pending on the anatomical structure drew an easy way of

implement. There are two steps: the position matching

that reconciling the center of models and regular the size

of the samples by mean radius of the whole vertices.

Then we choose 20 points, we call them label points, on

the polygonal surface. Evaluate the results by measure

the Euclidean distances sum of corresponding points.

4.2. Verification Experiments

To verify the alignment extent by proposed method, we

aligned one set of left lung training shapes, which gener-

ated by one lung polygonal surface model but the mo-

dalities were changed through rotation in 3D space. Us-

ing the same model is convenient to the quantitative

analysis. Map the vertices to the Gauss map and align the

points set using the method in Section 3.2. The results

are recorded in Table 1. The rotation volume represents

the rotation values of the model along the x axis, y axis

and z axis respectively. The Pre-Alignment is the origi-

nal mean distances of the label points and the Post-

4.3. Fitness Results

Alignment corresponds the distances after alignment.

were performed on training sam-

ples of left lung field and liver field. To evaluate the re-

sion

lignment evaluation, the relative posi-

tion of the training samples to the reference model is

the Regis-

tra

method.

Alignment experiments

sults of alignment, we compared the Euclidean distances

sum of corresponding label points between training sam-

ples and reference model. The improvement of distances

sum of the label points is applied to evaluate the avail-

ability of proposed method. 4 cases triangular polygonal

surface samples of left lung field and 3 cases on liver

were implied. The rotation column records the angle ad-

justment, discussed in Section 3.2. As well as the im-

provement rate is shown in Tables 2-3. The Pre-Align-

ment is the original mean distances of label points. The

Post-Alignment is the corresponding distances after

alignment.

4.4. Discus

According to the a

improved. The average improvement of Euclidean dis-

tances of label points is 1.3% on left lung field alignment

experiment results and 0.23% on liver field.

In [10], the author points out that in fact few registra-

tion papers attempt to follow up on the use of

tion. Many cases the registration problem is just satis-

fied the visualization requirement. In this research, the

purpose of the alignment is that force unique points on

the surface of training samples to their corresponding

points on referenced model. So the precision rate could

be improved with the alignment rate improving.

In this paper, we employed the plane Euclidean dis-

tance as the evaluate argument of the alignment

Table 1. Confirmation results on rotated one case of lung

ainning sample. tr

CaseOffset (x, y, z) Pre-Alignment Post-Alignment

1 0, 0, 0.0175 0.0381 0.0346

2 0, 0.0175, 0 0.1956 0.0191

3 0.0175, 0, 0 0.0810 0.0799

4 0.0349, 0 0.0349,0.4380 0.4424

le on letr ainning sample s.

Tab2. Fitness resultsft lung

aseRotationPre-Alignment Post-Alignment Improvement

1 0.02910.3214 0.3090 3.9%

2 0.07070.3395 0.3381 0.4%

3 0.03560.2503 0.2481 0.9%

4 0.05510.3340 0.3342 –0%

G. X. LI ET AL.

Taitnes on liveing sam

C RPre-t PostImpent

ble 3. Fs resultsr trainnples.

aseotation Alignmen-Alignment rovem

1 0.0385 0.3565 0.3543 0.6%

2 0.0405 0.6078 0.6012 1.1%

3 –0.0012 0.4422 0.4467 –1%

Buss me distance metric is spherical.

te evaluation by plane distance w in-

proposed a feature based alignment

set of training shapes for SSM model

olleagues and friends at the

ogy for their research

on medical image processing. Especially thank interna-

, “Statistical Shape Mod-

edical Image Segmentation: A review,”

Analysis, Vol. 13, No. 4, 2009, pp. 543-

t on the Gau

proxima

ap, th

Its ap

ould

uce the measurement error. Especially when the oriental

deviate of the training sample is large, as the case 4 in

Table 1 showed. Another sensible factor to the align-

ment accuracy is that the representative points generated

by K-means algorithm could not reflect the distribution

density of the mapping points. A better way to solve this

problem is using classifier method to assign the weight to

each representative point.

5. Conclusions

In this paper, we

method to match a

building. Considering the shape correspondence proc-

essing of the model building, we proposed a feature

based method and transform the 3D object alignment

problem into 2D Gaussian spherical space. Here, we in-

troduced the piecewise Gauss map theoretical foundation

and gave an approximated solution for triangular po-

lygonal surface. As well, we proposed using representa-

tive points to reflect the modality of the point sets on

Gauss map. While the K-means based clustering method

was employed to obtain these representative points. The

experimental results on the left lung and liver training

samples showed the availability of the proposed method.

However, in theory, this method is not elaborate yet,

because using Gauss map cannot describe the character

of surface reliably all the time.

As the future works, we will improve the surface para-

meterization method by conformal geometry theory. Ref-

erence [11] provides a previous works in this area. It is

undoubtedly a convictive way for the model alignment

and landmarks registration. As well, we will use sphere-

cal distance to replace the plane Euclidean distance when

metric the points on Gauss map. At last but not the least,

the classifier algorithm is expected to get a better de-

scription of the distributional regularity of surface points.

6. Acknowledgements

We would like to thank our c

Kyushu Institute of Technolbasis

tional exchange student Eloi Duchaussoy for always

having an open ear for many smart ideas to me. Thank T.

Heimann at Medical and Biological Infomatics at the

German Cancer Research Center. Without his kindly

help about the programming of triangular mesh structure,

we couldn’t complete this research on time. He is very

accommodating and intelligent.

7. References

[1] A. T. Heimann and H. Meinzer

els for 3D M

Medical Image

563. doi:10.1016/j.media.2009.05.004

[2] T. F. Cootes and C. J. Taylor, “Statistical Models of Ap-

pearance for Medical Image Analysis and Computer Vi-

sion,” SPIE Medical Imaging, Vol. 4322, No. 3, 2001, pp.

pp. 1-36.

236-248.

[3] J. B. A. Maintz and M. A. Viergever, “A Survey of Medi-

cal Image Registration,” Medical Image Analysis, Vol. 2,

No. 1, 1998,

doi:10.1016/S1361-8415(98)80001-7

[4] M. A. Audette, F. P. Ferrie and T. M. Peters, “An Algo-

rithmic Overview of Su

Medical Imaging,” Medical Image Ana

rface Registration Techniques for

lysis, Vol. 4, No. 3,

2000, pp. 201-217. doi:10.1016/S1361-8415(00)00014-1

[5] W. E. Lorensen and H. E. Cline, “Marching Cubes: A

High Resolution 3D Surface Construction Algorithm,”

ACM SIGGRAPH Computer Graphics, Vol. 21, No. 4,

1987, pp.163-169. doi:10.1145/37402.37422

[6] D. S. Meek and D. J. Walton, “On Surface Normal and

Gaussian Curvature Approximations Given Data Sampled

from Smooth Surface,” Computer Aided Geometric De-

sign, Vol. 17, No. 6, 2000, pp. 521-543.

doi:10.1016/S0167-8396(00)00006-6

[7] X. F. D. Gu and S.-T. Yau, “Computational Conformal

Geometry,” Higher Education Press, Be

90-95.

ijing, 2008, pp.

ation,” IEEE Transactions on Pattern Analysis

[8] T. Kanungo, N. S. Netanyahu and A. Y. Wu, “An Effi-

cient K-Means Clustering Algorithm: Analysis and Im-

plement

and Machine Intelligence, Vol. 24, No. 7, 2002, pp. 881-

892. doi:10.1109/TPAMI.2002.1017616

[9] B. K. P. Horn, “Closed-Form Solution of Absolute Ori-

entation Using Unit Quaternions,” Journal of the Optical

Society of America A, Vol. 4, No. 4, 1987, pp. 629-642.

doi:10.1364/JOSAA.4.000629

[10] T. Zrimec, S. Busayarat and P. Wilson, “A 3D Model of

the Human Lung,” Medical Image Computing and Com-

puter-Assisted Intervention, Vol. 3217, 2004, pp. 1074-

1075. doi:10.1007/978-3-540-30136-3_143

[11] X. Gu, Y. Wang, T. F. Chan, P. M. Thompson and S. Yau,

“Genus Zero Surface Conformal Mapping and Its Appli-

cation to Brain Surface Mapping,” IEEE Transactions on

Medical Imaging, Vol. 23, No. 8, 2004, pp. 949-958.

doi:10.1109/TMI.2004.831226