2
3
Abstract Ths thess dscusses the method of construct skeleton for 3D trangle mesh. Skeleton s used n buldng realstc anmaton, shape analyss, mesh generaton, path plannng, feature recognton, and so on. We hope to construct skeleton based on 3D trangle mesh especally for anmaton and model search. Ths skeleton needn t to be as accurate as Medal Axs, and need less tme to construct. We brng out our skeleton constructon method based on Progressve Mesh. No complcated structures are nvolved n our method. At the same tme, t s automated and smpler to mplement. It s also robust to nose and holes of 3D data. Ths thess conssts of fve parts. Frst, the applcaton of skeleton for 3D model and man steps to construct skeleton are ntroduced. Next, basc defnton of skeleton and related works are gven. 3D data acquston and range data regstraton and ntegraton are the man content of the thrd part. In the fourth part, skeleton constructon method s descrbed concsely. Dscusson s the fnal of ths thess. Key Word: skeleton, medal axs, progressve mesh, I-K skeleton, trangular mesh 4
... 7... 7 1.1... 7 1.2... 8 1.3... 8 1.4... 9 1.5...11... 12 2.1... 12 2.2... 13 2.3... 17... 19 3.1... 19... 19... 19 3.2... 22... 23... 26... 26... 28 5
... 28... 28... 29... 34 4.1... 36 4.2... 37... 37... 38... 40... 40... 41... 42... 42... 42 4.3... 43... 54... 55 6
200 7
8
1 2 9
1 2 3 4 1 10
11
12
13
14
15
16
17
18
19
p, j 20
21
22
A = p } B = p } = 1,2,..., N ' { p = Rp + T + D R T R T D { ' 23
e = N = 1 p ( Rp ' + T ) 2 R p ' p q } q } q { { ' ' ' ' = p p q = p p N H = = 1 q ' q T H T = UΛV Λ X T X = VU X X R X X N Λ λ 1 > λ2 > λ3 = 0 H T T T H = λ1u1v1 + λ2u2v2 + 0 u3v3 u U V v H v u3 3 T X = VU e X ' ' = V U T V ' = v, v, v ] [ 1 2 3 24
X X X ' A B e X M S = S S xx yx zx S S S xy yy zy S S S xz yz zz n S = x x S = x y x, q x xx = 1 n q, ' q, xy = 1 q, q, q M N M ( S N = xx + S S S S yz zx xy yy S S S + S zy xz yx zz ) ( S xx S yz S S S xy zx S yy S + S zy S yx xz zz ) ( S S S xx S zx xy + S yz S + S yy + S xz yx S zy zz ) ( S S S S xx xy zx yz S S + S + S yy yx xz zy + S zz ) N e N det( N λi ) = 0 I λ m e m ( N λ I) e = 0 m n < 10) O(n) n m 25
26
N p 2 f ( T ) = ( Tp q j ) q j T p q q p q N p 2 f ( T ) = ( T p q k k, j ) Q P T 0 j j 27
R 3 28
j d, j w, j j D j = w, j w d, j, j W j = w, j 29
30
31
32
33
34
35
36
V = ν,..., ν } R 3 { 1 m K R m m 3 K R φ ( K ) φ : R m V R V ( r, g, b) n, n, n ) ( u, v) ( x y z M = ( K, V, D, S) V D f = j, k, l} K d S K ( v, f ) s ( v, f ) { f 37
Mˆ M 0 M 0 M ˆ = M n 0 1 Mˆ PM M, M,..., M LOD PM Mˆ n ecol({ v s, vt}) vs vt vs v v, v, v } v, v, v } ν M 0 t M ˆ = M n { s t l { t s r s ( Mˆ 1 1 1 0 0 M n ecol ) n ecol ecol =... M M. M, < n m 0 0 M M V t = m { v1,..., v 1} 0 + { s, v m + 1} ecol v 0 + M v j ν j 38
vsplt( s, l, r, t, A) v v v, v, v } v, v, v } v, v } = 0 { s t l { t s r { s t ν s ν t v v v d v v v S ( v,.), S( v,.), S( v,{ v, v, v }) S v,{ v, v, v }) ( s t l s t l s d { s, t, l } { t, s, r } ( r t s r Mˆ M 0 M 0 vsplt1 vsplt 1... ( M vsplt 0 1 n M n = Mˆ ) 0 vsplt ( s, l, r, A ) ( M,{ vsplt0,..., vsplt n 1}) Mˆ v r t 39
M vsplt +1 M M M + 1 vsplt ( s, l, r, A + 1 + 1 G = ( ν, ν )) M (α ) s m0 + + 1 G G 0 α 1 M (0) M M (1) M M vs t, v G (1) = M + 1 M G +1 + 1 G ( α) = ( K, V ( α)) M + 1 M M + 1 0 + + 1 m vs t G ν ( α) j + 1 ( α) ν j + (1 α) ν s 1 ν j = v j = +, j { s, m, j { s, m 0 0 + + 1} + + 1} M M + 1 M 1 M 0 vsplt Mˆ 40
Mˆ Mˆ Mˆ vsplt s, l, r ) s ( +1 + 1 +1 + 1 M ν s ν m + + 1 M + 1 0 v s v s v m + + 1 0 +1 v s ν s M d d v, v, v } v, v, v } { s t l { t s r M m0 = 0 m 0 << n 6 log 2 (n) n vsplt s log ( n ) 5) n ( 2 + 41
M c vsplt ( s, l, r, A ) { 1 { vs, v, } l v r v s vsplt c,..., vsplt n } Mˆ M ˆ = M n 0 M M ν s E dst 42
43
44
45
46
47
48
49
50
O( nlog n) O (log n) O(1) 51
52
53
54
[1] P. Gbln, B.B. Kma, A Formal Classfcaton of 3D Medal Axs Ponts and Ther Local Geometry, IEEE Trans. on PAMI, vol. 26, no. 2, 2004, pp. 238-251. [2] H. Hoppe, Progressve Meshes, ACM SIGGRAPH Proc., 1996, pp. 99-108. [3] H. Blum, Bologcal Shape and Vsual Scence, Journal of Theoretcal Bology, no. 38, 1973, pp. 205-287. [4] L. Lam, et al., Thnnng MethodologesA comprehensve Survey, IEEE Trans. on PAMI, vol. 14, no. 9, 1992, pp. 869-885. [5] C. Ma, M. Sonka, A Fully Parallel 3D Thnnng Algorthm and Its Applcatons, Computer Vson and Image Understandng, vol. 64, no. 3, 1996, pp. 420-433. [6] G. Malandan, S. Fernandez-Vdal, Eucldean Skeletons, Image and vson Computng, vol. 16, no. 5, 1998, pp. 317-327. [7] B. B. Kma, et al., Shapes, Shocks, and Deformatons, I: The Components of Shape and the Reacton-Dffuson Space, Internatonal Journal of Computer Vson, vol. 15, no. 3, 1995, pp.189-224. [8] J. Gomes, O. Faugeras, Reconclng Dstance Functons and Level Sets, Journal of Vsual Communcaton and Image Representaton, vol. 11, 2000, pp. 209-223. [9] M. Zerroug, R. Nevata, Three-Dmensonal Descrptons Based on the Analyss of the Invarant and Quas-Invarant Propertes of some Curved-Axs Generalzed Cylnders, IEEE Trans. on PAMI, vol. 18, no. 3, 1996, pp. 237-253. [10] A. Okabe, et al., Spatal Tessellatons: Concepts and Applcatons of Vorono Dagrams, Probablty and Statstcs, New York, New York: Wley, second ed., 2000. [11] M. Techmann, S. Teller, Asssted Artculaton of Closed Polygonal Models, Proc. 9th Eurographcs Workshop on Anmaton and Smulaton, 1998, pp. 254-268. [12] A. Verroust, F. Lazarus, Extractng Skeletal Curves from 3D Scattered Data, The Vsual Computer, vol. 16, no. 1, 2000, pp. 15-25. 55
[13] M. Hsada, et al., A 3D Vorono-based Skeleton and Assocated Surface Feature, Pacfc Conference on Computer Graphcs and Applcatons, 2001, pp. 89-96. [14] B. Horn, Closed-form Soluton of Absolute Orentaton Usng Unt Quaternons, Journal of Optcal Socety of Amerca, vol. 4, no. 4, 1987, pp. 629-642. [15] O. D. Faugeras, M. Hebert, The Representaton, Recognton and Locatng of 3D Objects, Internatonal Journal of Robotc Research, vol. 5, no. 3, 1986, pp. 27-52. [16] K. S. Arun, et al., Least-Squares Fttng of Two 3-D Pont Sets, IEEE Trans. on PAMI, vol. 9, no. 5, 1987, pp. 698-700. [17] R. Bergevn, et al., Estmatng the 3D Rgd Transformaton Between Two Range Vews of a Complex Object, Proceedngs of the 11th Internatonal Conference on Pattern Recognton, 1992, pp. 478-482. [18] P. Besl, N. McKay, A Method for Regstraton of 3-D Shapes, IEEE Trans. on PAMI, vol. 14, no. 2, 1992, pp. 239-256. [19] J. D. Bossonnat, Representng 2-D and 3-D Shapes wth the Delaunay Trangulaton, Proceedngs of the 7th Internatonal Conference on Pattern Recognton, 1984, pp. 745-748. [20] H. Hoppe, et al., Surface Reconstructon from Unorganzed Ponts, ACM SIGGRAPH Proc., 1992, pp. 71-78. [21] N. Amenta, et al., A New Vorono-Based Surface Reconstructon Algorthm, ACM SIGGRAPH Proc., 1998, pp. 415-421. [22] M. Soucy, D. Laurendeau, Mult-Resoluton Surface Modelng from Multple Range Vews, Proceedngs of the IEEE Computer Socety Conference on CVPRC, 1992, pp. 348-353. [23] G. Turk, M. Levoy, Zppered Polygon Meshes from Range Images, ACM SIGGRAPH Proc., 1994, pp. 311-318. [24] B. Curless, M. Levoy, A Volumetrc Method for Buldng Complex Models 56
from Range Images, ACM SIGGRAPH Proc., 1996, pp. 303-311. [25] H. Hoppe, et al., Mesh Optmzaton, ACM SIGGRAPH Proc., 1993, pp. 19-26. [26] X. L, et al., Decomposng Polygon Meshes for Interactve Applcatons. ACM Symp. on Interatve 3D Graphcs, 2001, pp. 35-42. [27] J. D. Talbot, Accurate Characterzaton of Skn Deformatons Usng Range Data, Thess for Degree of Master of Scence, 1998. [28] H. Blum, R. Nagel, Shape Descrpton Usng Weghted Symmetrc Axs Features, Pattern Recognton, vol. 10, no. 3, 1978, pp. 167-180. [29] T. K. Dey, W. Zhao, Approxmatng the Medal Axs from the Vorono Dagram wth a Convergence Guarantee, Euoropean Symposum on Algorthms, 2002, pp.387-398. [30] M. Foskey, et al., Effcent Computaton of A smplfed Medal Axs, Symposum on Sold Modelng and Applcatons, 2003, pp. 96-107. [31] T. Culver, et al., Accurate Computaton of the Medal Axs of a Polyhedron, Proc. 5th Symposum on Sold Modelng and Applcatons, 1999, pp. 179-190. [32] R. Ognewcz, M. Ilg, Vorono Skeletons: Theory and Applcatons, IEEE Conference on Computer Vson and Pattern Recognton, 1992, pp. 63-70. [33] T. W. Pa, J. H. Hansen, Boundary-Constraned Morphologcal Skeleton Mnmzaton and Skeleton Reconstructon, IEEE Trans. on PAMI, vol. 16,No. 2, 1994, pp. 201-209. [34] H. Ren, G. Xu, Artculated-Model Based Upper-lmb Pose Estmaton, IEEE Internatonal Symposum on CIRA, 2001, pp. 450-454. [35] J. Chao, et al., A Herarchcal Invarant Representaton of Spatal Topology of 3D Objects and Its Applcaton to Object Recognton, IEEE Internatonal Conference on Pattern Recognton, 2000, pp. 1920-1923. [36] M. Etzon, A. Rappoport, Computng Vorono Skeletons of a 3-D Polyhedron by Space Subdvson. Computatonal Geometry: Theory and Applcatons, vol. 21, no. 3, 2002, pp. 87-120. [37] M. Sato, et al., TEASAR: Tree-struture Extracton Algorthm for Accurate 57
and Robust Skeletons, Pacfc Conference on Computer Graphcs and Applcatons, 2000, pp. 281-287. [38] B. Allen, et al., The Space of Human Body Shapes: Reconstructon and Parameterzaton from Range Scans, ACM SIGGRAPH, vol. 22, no. 3, 2003, pp. 587-594. [39] A. C. Fang, N. S. Pollard, Effcent Synthess of Physcally Vald Human Moton, ACM SIGGRAPH Proc., 2003, pp. 417-426. [40] S. Capell, et al., Interactve Skeleton-Drven Dynamc Deformatons, ACM SIGGRAPH Proc., 2002, pp. 586-593. [41] H. Fllbrandt, et al., Extracton of 3D Hand Shape and Posture from Image Sequences for Sgn Language Recognton, Proceedngs of the IEEE Internatonal Workshop on AMFG, 2003, pp. 181-186. [42] L. P. Morency, et al., Pose Estmaton Usng 3D Vew-Based Egenspaces, Proceedngs of the IEEE Internatonal Workshop on AMFG, 2003, pp.45-52. [43] I. Cohen, H. L, Inference of Human Postures by Classfcaton of 3D Human Body Shape, Proceedngs of the IEEE Internatonal Workshop on AMFG, 2003, pp. 74-81. [44] CG http://www.cgtmes.com.cn/lst.aspx?cd=212004. [45] 1998. 58
59
60