200 3 A Graduation Thesis of College of Engineering, Chubu University Keypoint Matching of Range Data from Features of Shape and Appearance Yohsuke Murai
1 1 2 2.5D 3 2.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 2.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 2.3 2.5D : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 3 3.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.1.1 SIFT : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.1.2 : : : : : : : : : : : : : : : : : : : : : : : 8 3.1.3 : : : : : : : : : : : : : : : : : : : : : 11 3.2 : : : : : : : : : : : : : : : : : : : : : : : : 14 3.2.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14 3.2.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 15 3.2.3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 18 3.2.4 SIFT : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19 3.3 : : : : : : : : : : : : : : : : : : : : : : : : : 23 3.3.1 Shape Index : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23 3.3.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 24 3.3.3 : : : : : : : : : : : 25 4 2 4.1 : : : : : : : : : : : : : : : : : : : 2 iii
5 29 5.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29 5.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29 5.3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30 33 35 3 iv
2.1 : : : : : : : : : : : : : : : : : : : : : : 3 2.2 Vivid 9i : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 2.3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 2.4 3 2.5 : : : : : : : : : : : : : : : : : : : : : : : : 5 3.1 SIFT : : : : : : : : : : : : : : : : : : : : : 8 3.2 Difference-of-Gaussian : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 3.3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 3.4 DoG : : : : : : : : : : : : : : : : : : : : : : : : : : 11 3.5 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 15 3. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 3. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 3.8 2.5D : : : : : : : : : : : : : : : : : : : : 18 3.9 : : : : : : : : : : : : : : : : : : : : : : : : : 19 3.10 : : : : : : : : : : : : : : : : : : : : : : : : 21 3.11 2 : : : : : : : : : : : : : : : 21 3.12 : : : : : : : : : : : : : : : : 22 3.13 SIFT : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22 3.14 Shape Index : : : : : : : : : : : : : : : : : : : : : : : : : 23 3.15 Shape Index : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 4.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 28 5.1 1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30 5.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 31 v
3.1 (12.1) : : : : : : : 14 3.2 Shape Index : : : : : : : : : : : : : : : : : : 25 5.1 : : : : : : : : : : : : : : : : : : : : : : 30 5.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 31 vii
1 3 3 3 3 1 3 3 3 3 [2] 3 3 3 3 1
1 2 3 4 5 2
2 2.5D 3 2.5D 2.1 ( 2.1(a)) ( 2.1(b)) 2.1: 3
2 2.5D 2.2 2.1(a) Vivid 9i(Konica Minolta[1]) ( 2.2) 2.2: Vivid 9i Vivid 1m ( 2.3) 2.3 2.5D (z) ( 2.4) 2 2.5 4
2.3. 2.5D 2.3: 2.4: 3 2.5 5
3 2.5D ( ) 3.1 () 2 SIFT[3] 3.1.1 SIFT SIFT(Scale Invariant Feature Transform) SIFT
3 (detection) (description) 2 ffl ffl ffl ffl 3.1 SIFT 3.1: SIFT SIFT 3.1.2 2 8
3.1. Difference-of-Gaussian (ff) G(x; y; ff) I(x; y) L(x; y; ff) Difference-of-Gaussian(DoG) L(x; y; ff) =G(x; y; ff) Λ I(x; y) (3.1) G(x; y; ff) = 1 2 +y 2 )=2ff 2 2ßff 2 e (x DoG D(x; y; ff) DoG (3.2) D(x; y; ff) =L(x; y; kff) L(x; y; ff) (3.3) k DoG DoG 3.2 3.2: Difference-of-Gaussian DoG 3.3 DoG 3 ( ) 8 3 3 2 ( fl ) 9
3 3.3: DoG 3.4 3.4(a) DoG ff 1 3.4(b) DoG ff 2 ff 2 =2ff 1 10
3.1. 3.4: DoG 3.1.3 x =(x; y; ff) T DOG D(x) D(x) =D + @D T x + 1 @2 D @x 2 xt @x x (3.4) 2 (3.4) x 0 @D @x + @ 2 D ^x =0 (3.5) 2 @x 11
3 ^x () @ 2 D ^x = @D 2 @x @x (3.) 2 4 @ 2 D @ff 2 @ 2 D @ffy @ 2 D @ffx @ 2 D @ffy @ 2 D @y 2 @ 2 D @yx @ 2 D @ffx @ 2 D @yx @ 2 D @x 2 3 2 5 4 ff y x 3 5 = 2 4 @D @ff @D @y @D @x 3 5 (3.) (3.) ^x 2 4 ff y x 3 5 = 2 4 @ 2 D @ff 2 @ 2 D @ffy @ 2 D @ffx @ 2 D @ffy @ 2 D @y 2 @ 2 D @yx @ 2 D @ffx @ 2 D @yx @ 2 D @x 2 3 5 1 2 4 @D @ff @D @y @D @x 3 5 (3.8) (3.8) ^x 3.1.3 (3.8) ^x = @2 1 D @D @x 2 @x (3.9) (3.4) D(^x) =D + 1 T @D ^x (3.10) 2 @x 3.1.3 ^x 2 H 12
3.1. H = 2 4 D xx D xy D xy D yy 3 5 (3.11) 1 ff 2 fi Tr(H) Det(H) Tr(H) = D xx + D yy = ff + fi (3.12) Det(H) = D xx D yy (D xy ) 2 = fffi (3.13) fl 1 2 ff = flfi Tr(H) 2 Det(H) = (ff + fi)2 fffi = (flfi + fi)2 (fl +1)2 = flfi 2 fl (3.14) Tr(H) 2 Det(H) < (fl +1)2 fl (3.15) [3] fl = 10 12:1 3.1 2 SIFT 2 2.5D 13
3 3.1: (12.1) 02.2148 11.4040 135.3535 9.41118 5.30522.1518 31.582010.0848 18.85913 4.1112 3.2 3.2.1 3 3 (x; y; z) 3 3.5(a) OAB O OA A OB B A(x 1 ;y 1 ;z 1 )B(x 2 ;y 2 ;z 2 ) A B A B =(y 1 z 2 z 1 y 2 ; z 1 x 2 x 1 z 2 ; x 1 y 2 y 1 x 2 ) (3.1) 14
3.2. ( 3.5(b)) 1 N(n 1 ;n 2 ;n 3 ) N ^N = knk = ψ! 1 knk N = n1 n 2 n 3 knk knk knk q (3.1) n 2 1 + n 2 2 + n 2 3 (3.18) ^N 3.5: 3.2.2 3.2.1 z ( 3.) 3 15
3 3.: 2 4 X 0 Y 0 Z 0 1 3 5 = 2 4 1 0 0 Tx 0 1 0 Ty 0 0 1 Tz 0 0 0 1 3 5 2 4 X Y Z 1 3 5 (3.19) Tx;Ty;Tzx y z 2 4 X 0 Y 0 Z 0 1 3 5 = 2 4 1 0 0 0 0 cos sin 0 0 sin cos 0 0 0 0 1 3 5 2 4 X Y Z 1 3 5 (3.20) 2 4 X 0 Y 0 Z 0 1 3 5 = 2 4 cos 0 sin 0 0 1 0 0 sin 0 cos 0 0 0 0 1 3 5 2 4 X Y Z 1 3 5 (3.21) 1
3.2. 2 4 X 0 Y 0 Z 0 1 3 5 = 2 4 cos sin 0 0 sin cos 0 0 0 0 1 0 0 0 0 1 3 2 5 4 X Y Z 1 3 5 (3.22) z y x y x 3. ff; fi 3. 3.: N(nx; ny; nz) ff; fi ff = arccos fi = arccos ψ! nz p nx2 + nz 2 ψ p! nx2 + nz p 2 nx2 + ny 2 + nz 2 (3.23) (3.24) 1
3 3.2.3 2 2.5D ( 3.8) z 2 3.9 3.8: 2.5D 18
3.2. 3.2.4 SIFT 3.9: SIFT 3.1.2 DoG 3.1.2 2 3.1.3 3.1.3 2 2 2.5D 19
3 SIFT 3.2.4 L(x; y) m(x; y) (x; y) m(x; y) = q (L(x +1;y) L(x 1;y)) 2 +(L(x; y +1) L(x; y 1)) 2 (3.25) (x; y) = tan 1 ((L(x; y +1) L(x; y 1))=(L(x +1;y) L(x 1;y))) (3.2) 3.10 h w(x; y) = G(x; y; ff) m(x; y) (3.2) h = X x X y w(x; y) ffi [ ; (x; y)] (3.28) ffi Kronecker 1.5 h 3 3 80% 3.10 1 80% 1 2 ( 3.11) 3.2.4 ( 3.12) 20
3.2. w(x, y) G(x, y,) m(x, y) 3.10: 3.11: 2 21
3 3.12: 3.2.4 3.13 3.13 4 4 1 8 3.13: SIFT 128 22
3.3. 3.3 3.1 Shape Index[4] 3.3.1 Shape Index Shape Index 0:0 ο 1:0 3 3.14 Shape Index 3.14: Shape Index 2.5D p Shape Index S(p) k 1 (p);k 2 (p) (k 1 (p) >k 2 (p)) S(p) = 1 2 1 ß tan 1 k 1(p)+k 2 (p) k 1 (p) k 2 (p) (3.29) Shape Index p k 1 = k 2 =0 (3.29) 0 0 0:0 ο 1:0 23
3 3.3.2 Shape Index 2.5D p p H = 2 4 @ 2 z @x 2 @ 2 z @x@y @ 2 z @x@y @ 2 z @y 2 3 5 (3.30) x; y; z 2.5D 2 p z (2 ) 2 p z 1 3 3 z z Z p (x; y) Z i d i z Z p = P n i=1 P n i=1 Z i d i (3.31) 1 d i z 3.15 Shape Index Shape Index 0 cup 24
3.3. Shape Index 1 cap 3.15 Shape Index Shape Index 3.15: Shape Index 3.3.3 Shape Index Shape Index 3.2: Shape Index Shape Index 1 1.0 ο 0.85 Cap ο Dome 2 0.85ο0.5 Dome ο Ridge 3 0.5 ο 0.25 Ridge ο Saddle ridge 4 0.25 ο 0.5 Saddle ridge ο Saddle 5 0.5 ο 0.35 Saddle ο Saddle rut 0.35 ο 0.25 Saddle rut ο Rut 0.25 ο 0.125 Rut ο Trough 8 0.125 ο 0.0 Trough ο Cup 25
3 2
4 4.1 3 2.5D R 1 S R 1 =(s R 1 1 ;sr 1 2 ; ;sr 1 128 )T R 2 S R 2 =(s R 2 1 ;sr 2 2 ; ;sr 2 128 )T d(s R 1 ; S R 2 )= X128 i=1 q (s R 1 i s R 2 i ) 2 (4.1) ( 4.1) 2.5D 2
4 4.1: 28
5 5.1 Vivid 5.2 2.5D 2 SIFT 29
5 5.3 5.1 1.5% 5.1: [%] SIFT 11 99 84. 131 2 1.5 + 4 49.2.2% SIFT 5.1 SIFT 5.1 5.1: 1 30
5.3. 5.2 5.1 5.2: [%] SIFT 9 5 55.5 22 0 0 + 11 4 3.3 SIFT 5.2 5.2: SIFT SIFT 31
2.5D SIFT 33
35
[1] Konica Minolta VIVID 9i non-contact 3D laser scanner", http://konicaminolta.jp/products/industrial/instrument/3d/vivid9i/index.html [2] Xiaoguang Lu, Dirk Colbry, and Anil K. Jain, Three-Dimensional Model Based Face Recognition," International Conference on Pattern Recognition, (2004), pp. 32-3. [3] D. G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints", International Journal of Computer Vision, 0(2), pp.91-110 (2004). [4] Chitra Dorai, Anil K. Jain, COSMOS - A Representatin Scheme for 3D Free-Form Objects," IEEE Trans. on PAMI, vol. 19, no. 10, pp. 1115-1130, 199. 3
() 200 3