2007 . 10) 2 #- f'l -il.it-f #r;ijt~;la~,ff {r!) PfHH,. -t-'Jl" t." C ,if it - ~~'F. ffii J -w-$.-A.tt~#Jl~ {r~ ~?fj ;f<>-f #r 'F lr!J-m-f>J. m \1!1 if1 «~~11!.Ar~fil.it ~#. ~ t -fr!.~ 1 lb J&i!l~~ {r!) n.a~.t.~ ~ Ii'"-<- \!!1 oo tt~ ~if.J 3••*••~•••-~~~~M~a~naa&*~~~~~•~~~---~~~~-t B!. Jfl. lfflit~: A.ttf¼'t; \!!]m:,fj}f,l~; t:..,~JJtttt~;~r.11 ij-f#f-0 Introduction In recent years, a great deal of research effort~ ha. been directed toward developing romputer-aided diagnosis . surgery simulation, computer-based virtual endoscopy and therapy planning systems!)-~:. Some recent imulation systems for laparoscopic urgery and arthroscopic surgery have been presented in renferences = 4-9] . The choice of a specific geometric represen-tation is of pr ime importance for simulators. This choice should be governed by the resulting trade-off between realism and interaction. In order to obtain a physically realistic surgery simulation . in the joint project ·· Augmented Reality ystem for Endoscopic Surgery and Operation", tetrahechal mesh was used to meet the requirement of Finite Element Analysis ( FEA) method to simulate the deformation of soft tissue and operation actions like cutting in the surgery, In the following sections, all the examples presented here mainly focus on the modeJing of human organs in arthroscopic knee sur gery. 1n this paper, three different algorithms are introduced to create the tetrahechal mesh directly from the segmented volume, which is represented by the regular volumetric data sets in 3D space. This is also the extension and typical application of conversion from 2D image to graphics. Basic Concepts Before we present the methods for generation of tetrahedral mesh. some basic concepts should be made clear, sucb as segmented volume and tissue boundary. This is the foundation of all the following algorithms. 1. 1 Segmented volume Modern scanning techniques and metho-dologies used in medicine provide us with many 3D volume data with embedded structures, uch as bones, muscles in CT and MR] data. :\!ormally the volume data i taken as a t rivariate function F ( .r • y. z) ampled over a 3D rectilinear g rid. Segmented volume is the result of the cla ·sification process applied on the volume data. 1t defines the tissue type of each node in the mesh. Let T = l t, I i = 0 . 1 . 2. · · · . p - l ' be a set of tissue identification numbers, P is the number of different types. The . egmented YOlume can be defined a. a trivariate discrete function F(.2-, y , z-) over the rectilinear volume grid ( n, m , k) with the value on the domain of T . such as : F<.x . y . z) = t, I t E T: x E [ l. 11] • y E [ 1 • m] • :: E t) , k ] l . 2 Tissue boundary \Vhen the segmented volume contains multiple tissues inside a ,·oxel . the tissue boundary can not be defined by traditional i. osurface terms. The basic idea of iso urface is to take the value defined on the volume grid as samples of a trilinear function over the 3D domains. The function should be continuous on the edge and the tissue boundary defined by isosurface is shown in Fig. 1 (a). But . in the segmented volume. the values on the grid no longer stand for samples of a continuous function. It only mean · the ID number of different ti sue types and can' t be used for bigger-or-smaller comparison. In thi case. the ti sue boundary inside a voxel can be defined by Fig. l ( b). It is a possible and reasonable configuration. Zesheng TA.~G. et al. Tetrahedral Mesh Generauon of Human Organ on Segmented Volume Data 3 ~ l Musdea Fa1 Bone -.!, (a) (b) Fig. I The comparison of isosurfare and the real boundary 1. 3 Tissue boundary inside a tetrahedron In each voxel, there could be at most 8 different tissue types. The configurations of distribution of tissue types in a voxel would have at most 88 ( 16 777 216 ) cases. Although we can simplify it by u ing rotarion symmetry , tbe situations of tissue boundRry RrP srill very complicated. We would like to simplify the problem by separating each voxel into 5 or 6 tetrahedra, and then just consider the tissue boundary problem inside each tetrahedron. The first 2 methods for c-re;iting tetrahedral are based on this idea. In order to keep the consistency of tis ue boundary between adjacent tetrahedra, the boundary edge on the surface of tetrahedron would be determined locally by the nodes on the surface. Here the ea es of boundary edge on the surface are illu ·trated in Fig. 2. Vlhen there are 3 tissue types existed in the triangle , the tissue boundary should take the centroid of the triangle and 3 midpoints of the tri;mgle edges to form the boundary. 6A& (a) ooe tissue (b) 1WO bssues (c) three tissues Fig. 2 The tissue boundary on the surface of each tetrahedron For the tetrahedral . there are at most 4 different tissue rypes corresponding to 4 cases m Fig. 3. When the tissue on the 4 nodes is of the same type . there is no boundary inside the tetrahedron. The cases of 2 tis ues coexisted has 2 configurations. the left of F ig. 3 (b) has only one triangle. the right one has 2 triangles to form the boundary. W"hen there are 3 tissue types, we have l. fact~ m case of F ,g. 2 l c ) and 2 face m case of Fig. 2 ( b ) . The final boundary consists of 5 triangles (Fig. 3. (c) ). (a) one Ussue (b) two tissues (c) three tissues (d) four tissues Fig. 3 The ~ of tissue boundary inside each tetrahedron The last case shown by Fig. 3 ( d) contains 4 .different tissues inside. All the faces of the tetrahedron are in the case of Fig. 2( c) . In order to give the boundary, we define 3 sets of points: .,, = {( x, , y, ) li=l , 2 ,3 . 4} , represent 4 nodes of the tet rahechon : ' l ~ l I S, = {(X, ,Y,) I x. =4 ~ I , , Y, =4 ~ y, : ,=1 , ...... (.r, , y , ) E Sp) • represents the center of the tetrahedron ; r = {( X, ,Yr) I f= 1,2 3 . 4 : X r = l ' 1 ' 3 ~ .r, . Y 1 = 3 ~ y , ; r-=-· .,-rt ,- 1...--r-1 (x . . y , ) E Sp t , represent the centers of 4 faces of the tetrahedron. The 6 edges are ordered as the following table :
4 Table l The indexes of 6 edgl!S in Fig. 3(d ) '.'iode index :'-iode i11dex --------! 3 2 1 1 3 6 2 2 -1 The column and row index (i. j) are of the 4 node indexes. T hen the edge indexe are given by rr~,-i I:'= ~ ,n-,-5-j ( 1 ) Then we can define the set of midpoint of 6 edges as follows. .. ={
6 voxel into a collection of tetrahedra Different configurations of tetrahedral, as weU as the different tissue boundaries, can be generated when the direction of diagonals on each faces of the voxel 1s changed. Fig. 8 shows an example with opposite diagonal on the face of a voxel. The dashed line is the tissue boundary extracted To keep the meshes of the same tissue matched at the common face of adjacent voxels, the decomposition of adjacent voxels should keep the same diagonal directions on their common face. .Fig. 8 Different decomposition of voxel may cause different tissue boundaries In this paper, 2 configurations ( Fig. 9) are selected because that they keep the same diagonal direction on the faces paraJlel to 3 axes. The nodes of each tetrahedron are defined as in the following Table 2. Fig. 9 Two configurations to decompose a ~·oxel into tetrahedra Table 2 'umber of nodes of each tetrahedron in Fig. 9 Sequence Configurarion number I n {0 . 1.3.4 1 10.1 .3.4 2 11.4.7 ,3} l l.-t.2. 3 3 I I .5. 7 .4 I 12.3 .4.7 4 0 .2 .3 . 71 {1 . 2.4.5 5 (l.2 .7. 51 H ,5.2.7 , 6 {2,5,6 , 71 :2.s .6.71 The order of nodes in each tetrahedron 1s defined that the normal of the face constructed by the first 3 nodes points toward the exterior of the tetrahedron. The order is very important for the definition of boundary faces. 2007. 1(1} 2. 1. 2 Tissue boundary extraction from tetrahe-dron Fig. 3 has already shown the tissue boundary in 4 cases. Here a detail description is presented. For the firs t ca:,e (Fig. 3 (a.,) , l nodes &re of the same tissue type. There is no tissue boundary inside. For the case on the left of Fig. 3 ( b) . only 1 triangle will be extracted for the tissue type 1. Ir is very easy to compute the coordinMes of the mid points in 3 edges to form the triangle. ln the case on the right of Fig. 3 (b) . there are 2 tissue types (t1 • t z ) and in Fig. 3 ( c) , there are 3 tissue types ( t 1 • t2 • t3 ) in which t 1 has 2 nodes . both t 2 and t3 has only one node. In all of these cases, the normal directions of triangles should be carefully designed. For the case of Fig. 3 ( d). there are 4 tissue types and 12 triangles to form the tissue boundary. Since each node is definitely different from others by their distinguished tissue type. the nodes and normal for each triangle become obvious. We have extracted 4 kinds of tissue boundaries for the segmented volume at knee part. The volume has totally 3 774 000 ( 148 X 170 X 150 ) voxels. 1t contains 4 types of tissues . air, hone , fat and muscle. Fig. 10 and Fig. 11 show the results. Fig. 10 The boundary mesh for bone (72 790 nodes, 144 588 triangles) 2. 2 Generating tetrahedral mesh Before the generation of the tetrahedral mesh, it is better to simplify the tissue boundary mesh at Zesheng TAl'\'G. et al. Tetrahedral Mesh Generation of Human Organs on Segmented Volume Data 7 Fig. 11 The boundary surface for fat (371 964 nodes, 717 942 triangles ) first. Although there are a Jot of me h impli-fication methods, like references [ 10-13 J. according to the mesh generated here . we have to narrow our election tO topology-preserved non-manifold mesh. simplification category. The suitable method can be found in reference [14] . Ba ed on the tissue boundary, we can use conforming Delaunay tetrahedralization method to generate the mesh. There are a lor of related works presented in the past few decades. The details of our implementation in the surgery simulation system can be found in reference [15] . Fig. 12 shows a section of the thigh model in tetrahedral mesh. v.1£:UJI T--,,_.,F_,,_C.,_N.» 1/Pl- lxtl Scq-, , . Gaw,-Jt -Fig. 12 Section of lhe model of human thigh 3 Volume-split Based Tetrahedralization The main idea of this algorithm is very irnilar with the Interval Volume TerrahedraJization [ :'(iel on97j which extracts the volume defined by a ~ F ( x , y, z) ~ /J directly from original non-segmented volume. We divide each voxel into 5 or 6 tetrahedra And then divide each tetrahedron int0 smaller tissue volumes according to tissue boundaries. 3. 1 Decomposition. of tissue volume There are 2 kinds of polyhedra for ti sue volumes, namely: Prism shaped polyhedra: Fig. 3(b) and Fig. 3 ( c). Each of these polyhedra has 6 vertices, 2 opposite triangular faces and 3 planar quadrilateral faces. Cube shaped polyhedra, Fig. 3 ( d) . The polyhedra of this configuration have 8 vertices and 6 planar quadrilateral faces. '.\Jow the problem is bow to decompose each of these distinct types of polyhedra into tetrahedra such that lead to a global tetrahedralization. Because all the polyhedra are convex, there is no problem for generating tetrahedral on each of them. But unless special provisions are made, it is possible that the tetrahedralization of a porrion of the tissue volume in one polyhedron could not join with the tetrahedralization of another ponion of the tissue volume in the adjacent polyhedron. This could happen, for example, if these 2 portions shared a common quadrilateral face but the diagonal selection of the quadrilateral is different in these 2 portions. In order to circumvent this problem and have consistent choices of edges on any of the common planar faces, the ·• coordinate connection rule ' is presented. This rule assumes that a global order on all the vertices is defined such that for any 2 vertices one is prior or greater than the other. 3. 2 Coordinate connection rule There is only one configuration for planar face , quadrilateral. The 4 nodes of each quadrilateral can be categorized into 4 sets: S 1 ( original nodes from segmented volume) . S2
8 ( midpoint of tetrahedron edge) . S3 ( center of tetrahedron face) , S1 ( center of tetrahedron). For points from different sets . we have following relations: Pi > P 2 > P3 > Pi V P1 E S1 • lr/ P1 E- S! , V P1 E S1. VP~ E- S, Where , it is called that P 1 is prior or greater than P.:! and etc. If 2 points are both from S1 , the comparison of the points coordinates is based on the order of z. .Y and .r component. 1n order to solve the error brought by floating point computat ion . a threshold is defined for equality in the comparison. For 2 points from~. normally the 2 edges they are lying on has a common node , the comparison will totally depends on 'the other nodes on that edge. There is no comparison for pair of points coming from the same set like S1 and Si . The selected diagonal to form the tetrahedralization will start from the greate t poi.m to the oppo ·ite node on that face. Actual ly the coordinate comparison 1s not necessary for the pair s of points from S1 • In our original segmented volume, the comparison of nodes has an obvious answer from their index triple. So if we keep this infor mation further into nodes order in the 6 tetrahedra as the result of decomposition o{ voxel, the coordinate connection rule can be simplified into index rule. , ow the decomposition of each tissue volumes in Fig. 3 can be illustrated as follows. 3. 3 Decomposition of situation 1 When there is only one tissue m the tetrahedron like Fig. 13, just insert the tetrahedron into the mesh list. Fig, 13 OnJy one tissue inside the telrahedron 2007 . 1(1 ) 3. 4 Decomposition of situation 2 When tbere are 2 tissue rypes with the nodes ratio of 1 to 3 as shown in F ig. 14, the tissue boundary split the original tetrahedron into 2 pans, one tetrahedron and one pnsm. The small tetrahedron is left to be part of the final me h. The prism is decomposed further into tetrahedra. In this prism, we got 3 nodes from or iginal segmented volume. Their comparisons are totally dependent on their original node index. The diagonal on 3 quadrilateral faces is well defined . For reference (16] . in this situation tbe prism is definitely decomposable. Fig. N I wo tissue types ,~ith the nodes ratio 1: 3 3. 5 Decomposition of situation 3 When the nodes ratio for 2 tissue types are equal as shown in Fig. 15 . the original tetrahedron is decomposed into 2 prisms P1 and Pz. Both of them are composed of 2 nodes from S1 and 4 nodes from S2 • Fig. 15 Two tissue types with the nodes ratio of 2 to 2 The diagonal on 2 faces with nodes from S1 1s well defined from their indexes. For the quadrilateral face with 4 nodes from S7 • the diagonal 1s determined by the end points Zesheng TA. "\!G. P l ;;I. Tetrahedral Mesh Generat ion of Human Organs on Segmented Volume Data 9 comparison of the edges on wbich the 4 nodes from S2 are lying. Starting from the mid point of the edge with the higher priority end point, the diagonal is connected lO the opposite node in the quadri lateral. 3. 6 Decomposition of s ituation 4 When there are 3 tissues as shown in F ig. 16. the terraheclron is decomposed into 2 prisms and 1 hexahedron. In each of the prisms, there are 2 quadrilateral faces which got only 1 node in S1 . so it is definitely lhe starting point to form the diagonal. The other quadrilateral face has 2 node from S2 and 2 points from S.,. The diagonal on this face will start from the~ node on the edge which has the greatest node except the common node of these 2 edges. The hexahedron has 2 S1 nodes. 4 ~ nodes and 2 S3 nodes. From the greater point of the 2 S1 points. we can settle down the diagonal direction on 3 quadrilateral faces. Another face which has I S1 point, 2 s~ points and 1 S3 point will have the diagonal start from the sl point. For 2 faces which have 2 S2 points and 2 S1 points . we have to make a choice from the S2 points. The selection will depend on the edges they lie on according co the method mentioned above. Fig.16 Three tissues inside the tetrahedron 3. 7 Decomposition of si tuatfon 5 When there are 4 different tissues as in Fig. 17, the tetrahedron 1s decomposed into 4 hexahedra Each of them has 1 S1 node . 3 S2 nodes, 3 sl nodes and l s4 node. Three quadrilateral face~ which have the 51 node will have the diagonal well defined The other 3 faces, each of which ha~ only 1 S 2 node . ~ is definitely the starung µomt of the d1agunai. Tht decomposition is pretty clear. a Fig. 17 Four tissue types inside the tetrahedron 3. 8 Using voxel merge for simplification The met hod presented here has a resolution even higher than lhat of the original segmented volume. This makes the generated mesh too big to be t reated even for the mesh simplification algorithms. For example, for volume with the resolution m X II X l, the mesh size would be at least 5 X m X 11 X / . Actually in most voxels , there is no tissue boundary . especially for the volume of human organ. It is not necessary to keep the same high resolution through the entire domain. The density of the mesh could be changed according to the local volume contents. H ere we use the following Voxel Merge method to simplify the volume. 1) Initialize a flag volume data ( level O) . each node has a flag to represent if it is a boundary node. The node in this volume corresponds to one voxel in the segmented volume. If the voxel has multiple tissue types. the corresponding flag volume node is marked as boundary node. Otherwise it is marked as non-boundary node. 2)For each node (i,j . k ) in level m of the flag
10 volume data. (DH it is a boundary node . nothing to do ; (2) If it is a non-boundary node. check the adjacenl nodes (i+l. j, k), (i-1. j-1 . k) , (i , j+l, k), (i, j . k+D, (i+L j, k+l) . (i,I, rr-1. k,l) , (1 , 1-l. k+IJ . lf at! tht:!>t: nodes are non-boundary , merge them together into a level m + I volume node, and the new node is marked as non-boundary node. 3) Repeat tep 2, until there i no new node generated. After the merge operation, we can begin to decompose the voxels. If the voxel is a boundary voxel. we can use the volume splitting method mentioned above to get the exact tissue volume. For the non-boundary voxeJ. what we nt:t:-tissue voxels only. For the voxel on level m, if it has a level m-1 neighbours ( either common edge or common face neighbours) . it is also called boundary voxel. Fig. 18 and Fig. 19 show 20 and 30 examples of the merge operation. After all the level of the merge operation has finished. we should go on with the decomposition. According tO the voxels with the neighbour nodes on the same level, just use the method mentioned above. For the boundary voxels, we have to rake some special treatment to meet the requirement of consistency on the boundary. Details are shown in reference =15]. I I I I I I I I I I t I 1 I I I I I r 2007. 1(1) Fig. 18 !\lerge Samples in 2D Fig. 19 )lerge E.xample in 3D 4 Feature Point Based Tetrahedralization 4. 1 Introduction In this section . a different method . feature point based tetrahedralizarion is presented The idea is coming from the feature point in image processing. Thi method keeps the rissues t accurate geometrical features just like the second algorithm. The generated tetrahedral mesh has the following attributes. 1) Accurate. The tissue boundary contained in the original dataset is kept accurately by the featured point selection. Zesheng TA'\G. et al. Tetrahedral Mesh Generation of Human Organs on Segmented Volume Data 11 2)Small scale. Becau e FEA 1s a very computational intensive process. 1t is impossible to simulate a large-scale dataset in real time. An automatic self-adaptive method is presented to vary tht d1::nsic} of mt!:;h noJt::::, according to Lht:: loca; features of the segmented volume. 3) Well-shaped. The quality of 30 mesh takes a very important role for the accuracy of FEA computation. A well-shaped mesh presents less error in the simuJation. ince Delaunay triangulation guarantees the well-shape of the final mesh . we follow this idea and classify our method a an incremental insertion algori thm in Delaunay triangulation category. It is composed of 3 phases. 1 )P lacement of t he mesh vertices. This phase would definitely affect the quality of the final meshes , such as the adaptive distribution of mesh density . the conformation to the tissue boundaries etc. In this section. three steps arf' takPn ro meet the e targets : coarse structured mesh, feature point selection and Steiner point placement. 2)Delaunay T riangulation. The Delaunay tetrahedralization of a point set is defined by the empty sphere condition. We will combine the incremental insertion and flipping based algorithm to generate the final mesh. 3) Restore the tissue boundary and et ele-ment · s tissue type. After the tetrahedralization . the boundary of different tissue may not be reserved according tO the empty sphere condition. Three basic flip operations are used to restore the boundary 4. 2 Points placement There are 3 kinds of points for incremental mseruon : feature point, Steiner point and s,ructured mesh point. Feature points !-hould include all pomts that repre ent the tissue · geometrical shape accu-rately. They take the responsibility for conforming to the generated mesh to the embedded tissue boundary. The displacement of Steiner point should take care of the adaptive mesh density. The structured mesh points are selected to solve the msauon tailun:: problt:m t:sptcialiy when the volume ize is roo big. 4. 2. 1 Feature point The most important concept of our method is the feature point. The feature point is the voxel edge midpoint which has abrupt gradient in the local neighbors. Fig. 20 gives a 2D slice of a simple segmented volume which has only 2 tissue types marked as circle and square. Fig. 21 illustrates the 2D slice of the boundary surfaces generated on the samplt! volume. Fig. 22 illustrates t he feature points on the slice of the sample volume with star *. Normally these feature points are the exact vertex of the simplified tissue boundary triangles. 0 0 0 a O D O D C O O O O D 0 D 0 0 0 0 D O O 0 a a o o a o a o 0 0 0 D O D D 0 0 0 0 0 0 D Q D 0 0 0 0 0 D O O 0 0 G O C D O 0 F ig. 20 2D slice of tagged volwne ODCCDOOD oc:oaoaco 0 Q. D O 0 0 D D oa.000000 0 0 0 0 C D O D 0 Q O O D 0 Q 0 O 0 O O D D 0 0 000000cc Fig. 21 Tissue boundary on the sample ~-olume 00000000 DDDDDDOO l D C O 0 0 0 0 ~*" 0 D D aooooooo 000':)0000 * I) " .... .. 0 " * Fig. 22 Featured point
12 The computation of feature points 1s pretty complicated. lt takes 3 step : 1 )Gradient computation of mid points of voxel edges ; 2) Companson uf the graJient:, m tht: local neighbors; 3) Error bounded simplification of feature points. There are 3 kinds of mid points . .z--0. 5 . y+ 0. 5, z,-0. 5 whicb lie on the voxel edges aligned to x. y and z axis respectively. The gradient can be obtained by the linear interpolation from it 2 X 2007. 1(1) neighbor voxel nodes. 1n order to include the tissue boundary point on the volume surfaces. we extend the volume size one slice at the 2 ends in each axis direction to represent a non-existing ti:;;,uo;: t; pc 111 ,he volume scgmenta ion. In the gradient companson step. the neighborhood of a mid point in all possible directions of tissue boundary should be considered (Fig. 23) . lf the mid point does not have the same gradient value with its neighburs, it is selecced as a feature point. x+0.5 node·s neighbors y+0.5 node·s neigJ,bors z-'-0.5 node·s neighbors Fig. 23 Neighborhood of a mid point to rompare gradient Jn the isosurfaces simplification method . an er ror bound is always taken into account. Here we can also define a global error limit to simplify feature points in the local neighbors. If two feature points have the following attributes, they can be merged together. l)They are in the neighborhood in Fig. 23. Z)They represent the boundary of same tissue paus. 3)Their gradient difference 1s less tban the global error bound. The 4 feature points at the corner in Fig. 22 are just the results of this simplification uµeration. 4. 2. 2 Steiner points placement Using these feature pomts . a coarse tetrahedral mesh can be generated But ordinarily the mesh quality is still bad at thi stage
14 takes the following 3 steps. l)Finding all the elements containing the crossing edge; 2) Finding the unchanged faces and points for new eJemems; 3) Tessellation and construction of new faces and elements. But in fact the above method is invalid when the polygon left for tessellation i not convex. T o solve this problem, three basic flip operations , Flip23 , Flip32 and Flip4Diagonal ( Fig. 27) are proposed. ~ _. ~ 23 Flip4Diagonal --- ~------......... --Flip 32 Fig. 27 Basic flip operations to restore tissue boundary The flip operation is dependent on the number of surrounding elements. 1 ) When the number of elements 3 . use Flip32 to delete the crossing edge. 2) When the number of elements 1s 4 . use F lip4Diagonal to swap the diagonal crossing edge. 3)When the number of element is more than 4 . use Flip23 and Flip4 operations recursively on the surrounding elements to decrease the number co 4 or 3 . then use above basic operations to solve the problem. Fig. 26 shows the crossing boundary edge on the surface of the sample volume data. Fig. 28 gives the final result with the tissue boundary restored. 4. 4 Set element tissue type \Vhen there is no crossing boundary element, 2007 . 1(1 l Fig. 28 The final tetrahedral mesh each element's tissue type can be determined by the follov;,i ng rule : l) If there is at least 1 voxel node in the element, the tissue type will be the same as the corresponding volume voxel node. 2) When all the nodes of the element are on the tissue boundary . using tri linear interpolation to compute the exact tissue type at the center of the element. 4. 5 Results We have implemented the algorithm in our knee arthro copy simulation system. For a segmented volume with resolution of 297 X 341 X 180 . and totally 18 229 860 voxels, our algorithm generates a tetrahedral me h with 94 953 nodes and 490 409 elements
16 ~l~ ~1-WJ 2007 ~ 6 JJ 30 B ~ r'I f;J- tt 1'. !l ~ -ffl loulll!ll of~ l..c.u Un,\'er.!-;tlltl~~~~~~{t-J IHt#,t1..?}-ii1l tt.~~-if.6!J-'l¾-$!-~@,-i¥~~ t•I :!: 21~#~-r ~ -~ 'f ~Jflt.:!: 121~!t##.ta ·*:i!i@A».il-#;fki!. ?}- 2 ffe u~ :!: ~ fil~~--i--~tl~I ~J.. £r!J.&1..f.lt $., ~ .J-{t-J#~}.ll¾-,, Ji.>!-il!.Jfl £,r:--.!f., J;.li;.i!e.~( Ylahalanobis distance) 81 ~ •/1.1:, Ji ~-1!-ili:..~Jlj ~ 81 1m J,. 1fLt¾m-,v\;J:f.,i--~.J•lii•l . ;ffl.:/.t.:ffi.11. ¥; x._§.~~ fll - >!-(]eave-one-out )~i!!Ai" 1 980 ik.~$: iii,Jti., Jf. ~td1!J .iI.4:~i11 .f-~.i& 98% C lb #-1-rtk A 00 i~ ¥1-f :it ~,l~ ai~F!l ¼J. ~ *J!.;ff ;fij -t 99 .~~•f±' #- ~ *..J!:-~at ~ii.~lf.. 1~-r.r :i?l. -ft#,!}lm¼-illflt.~1l., m 11r:atM 1:, ~ s ~, ~ ,,i,tJJr ~~JI.. $-JJL~.Jb ¥-~ YJ;. ZJf-#.~ *.$..aJl • Jtl it Jt-• i\l f}J~)l1J ~ ~~vfi-ti-{t-J~%Jt -;r4t{t-J o ruim~ = ~@, F.t•#*: m JJJ~ii1l : ~.-:t#~, .!f!J ,N?}-~1r; Jl'.-1!-u # Research on Auto Recognizing Counterfeiting Security Labels of Opfically Variable Ink Xiaolin TIAN' · . Chiwa SOli· (1, Faculry of lnformanon Technology, Macau Unlver·ity of Scienee and Technology. Macau, China) (2. TDM-TELEDIFU AO DE MACAU, Macau, China) Abstract: Based on research o f Hewlett Packard( HP ) security labels of Optically Variable Ink( OVT), a new and faster algorithm to identify OVI security labels by computer is proposed. The algorithm i:- ·pecially designed to use higher computer resolution as well as advanced techmques of PRIP 10 check if the HP OVI security label is genuine. Twelve statistical features have been extracted from two feature sub-irnag~ of every HP OVI security label. One of rhe feature sub-images is segmented from the background part of the label and the mher one i from the color shifting part. Five s tatisucal features have been selected from twelve to minimize the risk of mistaking false security labels as genuine ones. A linear classifier based on the Mahalanobi.s diMance has been used 10 test thi- algorithm. Eighty-one HP cartridge securit}' .eals have been tested 980 times in a generalized Leave-One-Out testing process. The correct recognition rate of the algorithm is over 98 Yc. In the meantime, the new proposed algorithm is robust and is easier ro be realized. Key \\Ords: OVl security label ; auto recognnion: statistical features: discnmmate analysis, algorithm design ,itfA a.J!ij,200,--01--os, fit# e JJ! , '.?007-03-19. " .i! tR. -ft~ : 81 , J, ,#.' ± '~ ±' ~ rH4.#.:. :k. ~ ~"itl# ;ft."" iuuut . .i.-:l-bJt ,t. ~~$,.it~ IHJ..r,V-2 ~~A i~.}j'] • E-mail: xhian@must.edu. mo, Tel: 853-8972046, o s1 -;;-mi. '.¥: m ~ £ m ~ffl e * ~J $\1111g I T ~g; £1'1 • f{lj~~if;fi" .-tl!ll/i.517-:f:1!!¥J~W1:it O :(f~--rflf l't-Jllff~1l~~~~iig < f9!Ji.!otr£JJ ~ )ff~f!Jttf:;t~ &b c W11:!rntr£flffl~~ < le§1il > > ~. ::kt ~ AA!'ftf,f li&b -mrt:JF Ttlt :W-~ .lt!!. a9 m ~. EB ~-IN: iiHl ;#1!UIHJf ii2~&be9Jtfa. ~m-~ 7 fN ~ ~~ im&b ffii~~:i; . :gJl:!1!££ , :!m~t/r( Hewlett P ackard) ITEflml~~~ ~~fflF~~mffi~~iflr,£¾~~~~~ fP~L fa~f9HJ~~.~fllriJ1t ,;Fef-t1TtaEflx~~.W-fltJ-::k51m~1, < AT~~•*mr~m••••~•~•·• 1t0iiJ~ffl71®~B91iJJi!l!iffi. {ff 2001 ~&-•• 0 jj_j U nu.m:~atJ9~'fil•L~ :ho T -$1 ffJ lf Jt0 m tl::fifHfti~{y.JJlJ~ ~s9·•rtt;~~fi',:?:. !;i/r01iJ'.ffl'~ ffl P ~lffijr§ llJ:f ~~-L a(JJH~ .. J!{tJl~JU ffi~~~i!; A;!;•~•lIJ'ti . film ntf1J~~·f!, !\ilWi~:tJ• *~ ,J)-; ~~ tR tii fnJi , ..El fl~Ill:IJ ftl~•?JJ'Ali ~ e ~ ~ tt. *Nfl- ~ffl~m• 5~-~M•••-A~ ~ H!HlUIHl?tWJ~~~{y.J 1l fa . '@~ ~-~iflillJ:f ~ 51W -ffl9c~:m:.~~tm::ktT/N:iJlfL ~ 2006 .if l FI 1 J3 OOtlti- -£(Samsung):(£Jt~Jrli~:MEi<L ~:boP~Tfflli~-~ f!lf-l'J91iJJ{Affi~ -m P AJ m 3M~ ~&~&M••n••R•••~••-~n a-;~fllrt.tJ. ;rn ffffl ~f;Hif {y.J llJi ~mJJtm J.i1JWi ~~~1¥-Jllli9~tt~ff. m 5 tv 1,rnu5,-~ , m m11 ~ M {y.J ~ tt 0-ffi ff . ~ 11J0-~ at~~~*iifi'1tffi. :ft ~~wt~tta91Elii ~}N1¥. 'tt'~...t..t~Jf i!¾: ~~~ § i/J ~}Jljl{ ® lHf Wi ~ffil:B9-@ff ~'lfl'J9~~~~c - .§.0-ffiffttm~ 3!J-~ . ~--~ ~1/J~JJtl~~l\ilfMJM~-B':l~~~
18 -1£~m:~llfi{ij~~, ~Jf51.m: fl!¥-i"ffi:ffl.1r ».. #JJ)51j,rffi 3~;~x~m•m••~~•3~1¥J••tt.• ~~~YJ,Ji!Jl, ~i!J.ff lJ.j~J YJtlM-1. a(] 13 a~ . mJc~ Jt 1ffi ¥ ~I{ ' M. #-ffi ff • r rnH& ~ ~ lli JH! 1¥] ~ iii N.~!t _j_Q~~-&. 1. 1 ~ ~~~ II1i ~~~ ff.l Ill~ t.H1lil!I~ ffi~ JI ••rr~~•~i¥J-~ll1i•• •a(]~#A•m $~~~~~ffm~mffl•~~•~•~- •~• iUiHJiffl a-'J ~f~ , ~•...t~E $,r-1¥.J iffi E 1N1!£ ~'@. ~~ ~E ~ c i; U • tJ~ ll; Ji %i mi Jl-1f 1t ~ · t't fiY 5E ffl J.JVu*~ .3/t. J:IU!t~.ffl~t'.EJ!itr•~ l}'J >'~-e!~J:Jf51.1~<@;~ ~ m•B!J~fim(lffl 2(a) ) .~~~!t5li,=ffi1-t~!ft-tl-l ~~ffi1'H9 :ii~#~ PJ m Ii'.:®: ~ B!J ii 1ft •it~ -¥. ii ttt:E111riHl1i:(M~@~ jlfiiJi#:iE~~JP:iliA~ J : ~l!J.An~l¥i~~if ®~~~it~lli ll 2 ~ ~ ~~-fiUn -!&~~ ~DlHt~lml 2< a)J!il 2 (b) . m*{l:(31'-#~;i ~ftJf-. 1Et~Rm~t/£.1c1iff~ft~. llf~:.l~lliX~ 2007 . l(]) jjlJJYrtE . [; 3 :£~-tt:k~l¥JJt@ll1ii!Hj•agf,lj~-=f Ill • ~ i:r AJ VJ~ tll J! Ji: WJ ~ ffi~ ffl It · IN WJ ~ :tJ~ Mf'&~'if ::!t-~J11Ufit@, ~~fftll::k -~E $5tE~$/c A Ji E.iF 1ft • r0, ~ o ~JJflwf-Jt: 1m l'.f.l ~ 5HJ$~ , l!PjPJ tli::f:i: ~f&~1Ui 0-#r tl-ll{.ffil~~f,J(~B~@ ~~~ H1!¥i B5tm~~~tt~. ~~tl-:WJ~~-'W~$*~~ ~ m;,tag ~ FoJ~wt~tt .1,n1 ,r jjtl tE~~ pg tt ~l\ti~tt•i;q~eJlll5t @l\tilEHUf Pl~@.ml5t ~3 li@~~~~-@~~~~tilt l . 2 $ ~:§~l!,1i1&~~~~ff.l~~m~ t'f-iiHffl ~ {llffirf eg ffi flel ~~ r II i:p ,r YJ1J m:~ tl-l 12 ffl!Ho .r1 - X g ,r-YJtl¾ffiOO~~rll-1}~B?t :I:: (R. G, B) l'(,J3¥-i$JffiW:tm 100 ~ 89 3¥-:J:5J ffi Ot1J ~ ffi > • 100 A-fm JE tiJ$ ::k B!J ffi M! 1-l'J ~~~~?tSB9~~•$•o ~ffl-~?t•~~-H:£~A ffi~ ~ 5Hi: 89 ~ tt¥@~ ~ ,r:1::£-H't!fil •#·~-~-A~~-1¥J•Wtt~~ff~~?t ttE9: • ~ ~ I'(,) '.It$:~ -W: !JF ~ ll,ij T @ -!lli . Jl-ff ~O T : .TI A 1af jJ-y tffl tr@. ,rfi: l¥J i$J ffi : .r~ A 1rjJ r ~ ~@. ,ril B9 :!1J ffi ; .r1 A 1erjJr~J!e5tiitt~ ffl ~ffi'. *] ¥-~ftJJ.r,I) !le Jil ,tJJii~~ ?HI It I _ r3 r. I); 16 ffifllll!: 29. 51 35.83 35.72 24 56. 04 59. 11 iUl v v V v v v ~liE ..c- Ii .r. It~ ru .ru flil'Jlie 6. 3] 0. ll 6. 21 32. 04 3. 07 35. 11 ill~ )' X X V X v ~1£12@~~~~~~~~ffi~~&t7J~ ~*~ ~*i:pllf!J.~tll~f\il~-~~M-ilil¥.lffi~ Be l¥J ti: ffi~:ffi'i :£W ll)Hii B9 • 1JJ ~ ii tl-l@: rf31 ~:k tt9 8 00~1:a . Jffl~TX~ 1/3 1¥.J~ffi:. tli ~ : ;;tJ-Li$ m ~~ ~ fPJ m 1r B!I DJ 5rtt. 11J iit ~~800~--~~ffi~~ffi-·ff(J{jllf?ttt,~ ~~-~m~m~~8B~tt~J{.@~MtHHf*~i:rff<~~* 60 0014 ~~JJ-~ 71lf~llJi{!Hl~f'l=~wll~tl* . ffl1JtUI * ~ 7 o 001t: fro' ill\ ffiit ;¥u 11 11 ® llJi ,JflL~ 15 fm~~ffl1r1ll1 ~,rffi:ff .#~rff t.}i'{ffi * P,Jrti J!j 1¥] 51-ffi rJi * . 4)~~l£ 1511,r~i:ti~i:r~tll~®llJJ-
