DP Contour Morphing 2005 3 A Graduation Thesis of College of Engineering, Chubu University Contour Morphing based on continuous DP matching Taichi Nomura
1 1 2 3 2.1 Flash Shape Tweening : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 2.2 Contour Morphing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 3 Contour Morphing 7 3.1 : : : : : : : : : : : : : : : : : : 8 3.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 3.2.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 3.2.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 3.2.3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12 3.3 DP : : : : : : : : : : : : : : : : : 13 3.3.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 15 3.3.2 DP : : : : : : : : : : : : : : : : : : : : : : : : : : : 15 3.3.3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 3.4 : : : : : : : : : : : : : : : : : : : : : : 18 3.5 : : : : : : : : : : : : : : : : : : : 19 4 21 4.1 : : : : : : : : : : : : : : : : : : : : : : 21 4.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : 22 5 27 29 iii
31 iv
2.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 2.2 Flash Shape Tweening : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 3.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 3.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 3.3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 3.4 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 3.5 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 3.6 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 3.7 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12 3.8 : : : : : : : : : : : : : : : : : : : : : : : : : : : 13 3.9 DP : : : : : : : : : : : : : : : : : : : : : : : : 14 3.10 2 : : : : : : : : : : : : : : : : : : : : : : : 14 3.11 DP pass : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 15 3.12 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17 3.13 : : : : : : : : : : : : : : : : : : : : 17 3.14 : : : : : : : : : : : : : : : : : : : : : : : : : : : 18 3.15 : : : : : : : : : : : : : : : : : : : 20 4.1 : : : : : : : : : : : : : : : : : : : : : : : : 21 4.2 : : : : : : : : : : : : : : : : : : : : : : 22 4.3 1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 24 4.4 2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 4.5 3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 26 v
1 Cong Parvin [1] Flash(Macromedia,Inc.) Shape Tweening shape hint DP Contour Morphing DP (Continuous Dynamic Programming matching) 5 2 3 Contour Morphing 4 Contour Morphing Flash Shape 1
1 Tweening 5 2
2 2.1 2.1: 3
2 2.1 Flash Shape Tweening Flash Shape Tweening Flash Shape Tweening 2.2 2.2: Flash Shape Tweening Flash Shape Tweening shape hint Shape hint 2.2 Contour Morphing i hint DP Contour Morphing Contour Morphing DP 4
2.2. Contour Morphing 5
3 Contour Morphing Contour Morphing 5 3.1: 7
3 Contour Morphing 3.1 Flash Shape Tweening 2 4 3.4 3.2: 3.3 3.3: 8
3.1. 4 Flash Shape Tweening (3.1) x =(1 t) 3 x 1 +3(1 t) 2 tx 2 + 3(1 t)t 2 x 3 + t 3 x 4 y =(1 t) 3 y 1 + 3(1 t) 2 ty 2 +3(1 t)t 2 y 3 + t 3 y 4 (0» t» 1) (3.1) (x 1 ;y 1 ) (x 2 ;y 2 ); (x 3 ;y 3 ) (x 4 ;y 4 ) t t 3.4 t 0.1 10 3.4: 9
3 Contour Morphing 3.2 DP 3.2.1 (x c ;y c ) x c = 1 I IX i=1 x i ; y c = 1 I IX i=1 y i (3.2) (x c ;y c ) I (x i ;y i ) (x c ;y c ) (x i ;y i ) d(i) (3.3) q d(i) = (x i x c ) 2 +(y i y c ) 2 (3.3) 3.5 i j d s (i) d t (i) 3.5: 10
3.2. 3.2.2 DP DP d s (i) :(1» i» I) d t (j) :(1» j» J) I;J 2 (I < J ; 2J <I) 2 3.6 3.6: 11
3 Contour Morphing 3.2.3 d s ;d t (3.4) d 0 (i) = d(i) d min d max d min (i =0; 1; ;I) (3.4) d max d(i) d min d(i) d s ;d t 1 0 3.6 3.7 3.7: 12
3.3. DP 3.3 DP DP [3] [4] [5] DP DP 3.8 3.8: DP 3.9 d s (0) d s (I) 3.10 2 13
3 Contour Morphing 3.9: DP 3.10: 2 14
3.3. DP 3.3.1 i 2 j (3.5) 8 >< >: g(i; 0) =0 (i =0; 1;:::;2I) g(0;j) = 1 (j =1; 2;:::;J) (3.5) I J g(i; 0) 0 g(0;j) d t 3.3.2 DP DP 3.11 3.11: DP pass DP (3.6) 3 (a); (b); (c) g(i; j) =min 8 >< >: g(i 1;j 2) + 2 ld(i; j 1) g(i 1;j 1) + ld(i; j) g(i 2;j 1) + 2 ld(i 1;j) :(a) :(b) :(c) 9 >= >; + ld(i; j) (3.6) 15
3 Contour Morphing (3.6) ld(i; j)(local distance) (3.7) d s (i);d t (j) 2 ld(i; j) =(d s (i) d t (j)) 2 (3.7) g(i,j) (3.8) c(i; j) = 8 >< >: c(i 1;j 2) + 3 c(i 1;j 1) + 2 c(i 2;j 1) + 3 if(a) if(b) if(c) (3.8) (3.9) G(i) = g(i; J) c(i; J) (3.9) 3.3.3 (3.10) G(i; J) i 0 (J=2» i» 2I) i 0 = argmin (J=2»i»2I)G(i; J) (3.10) (3.6) (a); (b); (c) (j = 0) 3.12 16
3.3. DP 3.12: 3.13 3.13: 17
3 Contour Morphing 3.4 (3.11) x 0 =(1 ff)x s + ffx t y 0 =(1 ff)y s + ffy t 0 <ff<1 (3.11) (x s ;y s ) (x t ;y t ) (x 0 ;y 0 ) ff 3.14 3.14: 18
3.5. 3.5 (3.1) (x 1 ;y 1 ) 1(x 2 ;y 2 ) 2(x 3 ;y 3 ) (x 4 ;y 4 ) x; y (x 1 ;y 1 ) (x 4 ;y 4 ) x 1 x 4 y 1 y 2 ( x ) (3.12) t x x 2 ;x 3 x 2 = 2 3 x 1 + 1 3 x 4 ; x 3 = 1 3 x 1 + 2 3 x 4 (3.12) y 2 ;y 3 2 (3.1) (3.13) (3(1 t) 2 t)y 2 + (3(1 t)t 2 )y 3 + ((1 t) 3 y 1 + t 3 y 4 y) (3.13) (3.13) (3.14) a = 3(1 t) 2 t b =3(1 t)t 2 (3.14) c =(1 t) 3 y 1 + t 3 y 4 y (3.13)(3.14) 8 >< >: a 1 y 2 + b 1 y 3 + c 1 =0 a 2 y 2 + b 2 y 3 + c 2 =0 (3.15) (3.15) y 2 = b 1c 2 b 2 c 1 a 1 b 2 a 2 b 1 (3.16) y 3 = a 1c 2 a 2 c 1 a 2 b 1 a 1 b 2 (3.17) 19
3 Contour Morphing 2 t y 2 2 t y 2 ;y 3 3.15 3.15: 20
4 4.1 4.1: Flash Shape Tweening shape hint Contour Morphing hint shape hint 21
4 4.2 Contour Morphing Flash Shape Tweening 4 1 4 Contour Morphing Flash Shape Tweening shape hint0,1,2 2,3 3 ( ) 4.3 4.4 4.5 5 Flash Shape Tweening shape hint1,2 shape hint 2 50 (1) (0) (-1) 4.2 4.2: 4.2 Flash Shape Tweening hint2 t 22
4.2. t >» 1% 5% 5% t Contour Morphing hint shape hint 2 ShapeTweening Contour Morphing Shape Tweening 23
4 4.3: 1 24
4.2. 4.4: 2 25
4 4.5: 3 26
5 DP Contour Morphing Contour Morphing Contour Morphing Flash Shape Tweening Contour Morphing hint Flash Shape Tweening shape hint Contour Morphing 27
29
[1] G. Cong,B. parvin, A New Regularized Approach for Contour Morphing " Computer Vision and Pattern Recognition, Vlo.1,pp. 1458-1463, 2000. [2] H. Fujiyoshi, A. J. Lipton, T. Kanade, Real-Time Human MotionAnalysis by Image Skeletonization IEICE Trans. Inf. & Syst., Vol.E87-D, No.1,pp. 113-120, 2004. [3] H. Sakoe, S. Chiba, Dynamic Programming Algorithm Optimization for Spoken Word Redognition" IEE Trans. Acoust., Speech, and Signal Process., Vol.ASSP-26, pp. 43-49, 1978. [4] Y. Ohta, T.Kanade, Stereo by Two-Level Dynamic Programming" Proc. of the Ninth International Joint Conference onartificial Intelligence, Vol. 2, pp. 1120-1126, 1985. [5] D. Geiger, A. Gupta, L. A. Costa, J. Vlontzos, Dynamic Programming for Detecting, Tracking, and Matching Deformable Contours" IEEE Transactions on pattern analysis and machine intelligence, Vol.17, No.3, pp. 294-295, 2004. 31
DP ( ) 2005 3