(MIRU2005) ( ) Radim Šára Globally Optimal Range Image Registration by G

Size: px

Start display at page:

Download "(MIRU2005) ( ) Radim Šára Globally Optimal Range Image Registration by G"

しげじろうなつ
5 years ago
Views:

1 (MIRU0) 0 ( ) Radim Šára ikuko@cc.tuat.ac.jp, sara@cmp.felk.cvut.cz, sugimoto@nii.ac.jp Globally Optimal Range Image Registration by Graph Kernel Algorithm Ikuko Shimizu OKATANI, Radim ŠÁRA, and Akihiro SUGIMOTO Tokyo Univ. of Agri. and Tech. Czech Technical University National Institute of Informatics ikuko@cc.tuat.ac.jp, sara@cmp.felk.cvut.cz, sugimoto@nii.ac.jp Abstract Automatic range image registration without any prior knowledge of the viewpoint requires identifying common regions across different range images and then establishing point correspondences in these regions. We formulate this as a graph-based optimization problem. More specifically, we define a graph in which each vertex represents a putative match of two points, each edge represents binary consistency decision between two matches, and each edge orientation represents match quality from worse to better putative match. Then strict sub-kernel defined in the graph is maximized. The maximum strict sub-kernel algorithm enables us to uniquely determine the largest consistent matching of points. To evaluate the quality of a single match, we employ the histogram of triple products that are generated by all surface normals in a point neighborhood. Our experimental results show the effectiveness of our method for coarse range image registration. Key words graph kernel, globally optimal, local features, registration, range images CG CAD/CAM 3 3 3

2 Besl [2] ICP (Iterative Closest Point) ICP (1) (2) (1) (2) 2 ICP [4], [], [9], [], [], [1], [], [], [], [] S 1 x n n i(i = 1,..., n) x S 3 3 S = n n i=1 in i n > 2 {n i } S 1 R t (R, t) (coarse registration) S = R S R S S = UDU S : [3] Johnson Hebert [] S = U D (U ) = R U D U R. (1) 2 x y 2 ( (R, t)) x y Stein Medioni [] S S x y (1) Chua Jarvis [] Higuchi [11] D = D, (2) U P = R U. (3) P 3 3 s 1 = s 2 = 1 P = diag(s 1, s 2, s 1 s 2 ) [] [] P 4 1 [] (2) (3) S 1 S 2 P P M( = P ) R1: ( ) p M (R p, t p ) R2: ( ) 1 1 [1], [1] 1 2 3

3 (x 1, y 1) (x 1, y 2) (x 1, y 1) (x 1, y 2) (a) one (b) two (c) one (d) none (x 2, y 1) (x 2, y 2) (a) G (x 2, y 1) (x 2, y 2) (b) G D y 1 y 2 x 1 [0.0, 0.0] [0., 0.9] x 2 [0., 0.] [0.2, 0.2] 2 (e) one (f) none (g) one incomplete (, (a) ) 1 (c) c(p) 2 2 SSK M = {(x 1, y 2 ), (x 2, y 1 )} p M 1 R4 R3: ( ) p, q M 2 (R p, t p ) = (R q, t q ) R4: ( ) p = (x, y) M x S 1 y S p = (x, y) V P G = (V, E) c(p) = [c(p), c(p)] c(p) c(p) c(p) > = 0 p = (x i, y j ) x G V x i S 1, y j S 2 y 2 R1 R2 R3 G c( ) G = (V, E) R2 D = (V, A A ) (A A = ) M = P M p q A A 2 G p, q p, q x 1 S 1 y 1 S 2 c(p) < c(q) c(p) x 1 S 2 p q p = (x 1, y 1) M M q i = (x 1, y i) ((p, q) A ) 2 c(p) c(q) (i = 1) s j = (x j, y 1 ) (j = 1) ((p, q), (q, p) A) p q i s j D 1(a) G A R3 G A (R, t) x i 1(b) y j x k x l c(p) p P p = (x i, y j) q = (x k, y l ) 2 p, q D (strict sub-kernel; SSK ) [1] D = (V, A A ) 1(a) G K = V 2 K 2. 3 D SSK M 1 K D M 2 G 2 p K (p, q) A A r K M (q, r) A G = (V, E) V [1] G V 2 (p, q) A A p q 4

4 D SSK D SSK (p, q) A A 2 SSK q V p ( 2(c) SSK p p ) [1] p q( ) Step 1: K := p (2) q q Step 2: ( r) Step 3: D SSK Step : s s V D SSK Step : Step 2 (2) S 1 S 2 n SSK (2) O(n 4 ) c(p) D p V c(p) < c(p) O(n 3 ) SSK [1], [1] SSK 3. SSK [1] 1 SSK 2 S 1, S 2 2 x 1, x 2 S 1, y 1, y 2 S 2 S 1 c( ) 1(c) I 1 S 2 (x 1, y 1 ) (x 2, y 2 ) 2 S 2 I 1 I 2 P = I 1 I 2 D SSK 1(b) M = {(x 1, y 2 ), (x 2, y 1 )} SSK SSK SSK SSK 2 [1] 1 SSK 4 2 SSK 3(a) ( ) 3 ( ) (1) (2) (3) 3 (1) (2) (3) SSK [1] SSK 3(b) 2. 1 SKK [1] D = (V, A A ) p p x 3 f i F (x) = {f i (x) i = 1,..., t} 4 1 c( ) 1 SSK V V s V 3 D M Step 4: K s I c(p) SSK x x det[n, n 1, n 2 ] f i (x) = (x 1 x) (x 2 x). (4) S 1

5 a b c d f g h i (a) (b) (c) (d) 3 (a) 3 3 (= 2 4) (b) n 3 2 (c),(d) F 1 F 2 ((c) x (d) 04 ) [,, ] 3 t x, x 1, x 2 n, n 1, n 2 x, x 1, x 2 (4) 3 x, x 1, L(x) x 2 2 L(x) 4 t F (x) 2 t x i S x k S t = 2 3(c,d) 2 x i R x k S L(x) x (1) n(x) (2) t S j (x) (j = 1,..., t) (3) t F j (x) (j = 1,..., t) SSK ( ) (3) R L(x) 2 F j (x) F j (y) - KS ( F j (x), F j (y) ) c(x) = c(x) = L(x) SSK x y c(x, y) : t ( ( c(x, y) = 1 KS F j (x), F j (y) )) 2. () R3 j=1 c(x, y) c(x, y) n O(n 2 ) - 2 R I 1, I 2 SSK 3. 2 G 2 R2 R3 2 () 2 p = (x i, y j ) F j (x) F j (y) - [] q = (x k, y l ) 2 L(x) = std j=1 F j (x) ()

[ y l y j, m l, m j ] = R [ x k x i, n k, n i ], () S l = R S k R, S j = R S i R () R 3 x i S 1 m j y j S 2 1 2 S i S j x i, y j 1 1 4 n i 34 9 04 490 4 SSK SKK 4 Pooh 2 4.

6 [ y l y j, m l, m j ] = R [ x k x i, n k, n i ], () S l = R S k R, S j = R S i R () R 3 x i S 1 m j y j S S i S j x i, y j n i SSK SKK 4 Pooh 2 4. ( L(x) ) 2 2 Rick1 (i i + 1 Pooh Rick1 [] Pooh i ) Rick1 i i Rick1 i Rick [ ] ICP ( [ ] Pooh 2 ) Pooh Rick1 2 2 Pooh ± 1 Rick1 ± 1. ( ± 1 ) 2 ICP ICP ICP ICP 1 2 Pooh i i + 1 i Rick1 ICP M [1] Pooh ICP 1 ± 1. ICP

1 Pooh (i i + 1 i ) Pooh i 1 2 3 4 9 11 1 1 1 i 3 3 1 4 0 3 4 4 4 0 2 49 3 ICP ( i + 1 41 43 4 4 4 3 0 9 1 0 9 3 3 2 11 1 1 0 1 [ ]...9....0.....3.2..2.. [ ] 1.4 1.9 0. 2.2 0. 3. 3.4 0. 2.0 2.1. 0. 1.3 1.4 1. 1.4 1.1 0. 0.09 0.

7 1 Pooh (i i + 1 i ) Pooh i i ICP ( i [ ] [ ] [ ] [ ] ) ICP ( ) [ ] ( a ) ( b ) ( c ) ( d ) Pooh (a) (b), (c) (a) ICP (d) (b) ICP Pooh Rick1 ( 4 ) Pooh( ) Rick1( )., NII (No.401, No.10040, No.0). (1ET40) (ME ) [1] C. Berge. Graphs and Hypergraphs. North-Holland, 3. [2] P. J. Besl and N. D. McKay. A Method for Registration

3 43 49 4 1 3 4 9 1 1 3 1 1 1 4 2 43 3 3 9 1 3 1 4 1 3 9 343 2 3 40 0 9 4 9 9 2 0 1 2 4 1 1 40 2 90 9 2 2 9 4 4 2 3 1 2 2 2 1 49 0 49 1 0 2 9 0 3 3 32 3 4 1 2 1 2 3 2 4 3 2 3 94 1 4 3 41 90 1 1 4 93

A Survey of Free-Form Object Representation and Recognition Techniques. CVIU, 1:1 0, 01. [4] Y. Chen and G. Medioni. Object Modeling by Registration of Multiple Range Images. IVC, (3): 1, 92. [] C. S. Chua and R.

Registration and Integration of Multiple Object Views for 3D Model Construction. IEEE Trans. on PAMI, (1):3 9, 9. [] R. O. Duda, P. E. Hart and D. G. Stork. Pattern Classigication, 2nd edition.

Laurendeau, and R. Bergevin. A Method for 1 4 3 11 4 2 the Registration of Attributed Range Images. In Proc. of 49 3 3 11 3DIM, pages, 01. 1 [] E. Guest, E. Berry, R. A. Baldock, M. Fidrich, and M. A. 3 Smith.

Building 3-D Models from Unregistered Range Images. GMIP, (4): 3, 1 2 4 2 1 9 0 1 2 9. 2 9 1 [] A. E. Johnson and M. Hebert. Using Spin Images for Efficient Object Recognition in Cluttered 3D Scenes.

Registration and Integration of Multiple Range 9 3 2 43 Images by Matching Signed Distance Fields for Object Shape Modeling. CVIU, :1, 02. [1] S. Rusinkiewicz and M. Levoy.

8 Rick1 2 ( ) D Shapes. IEEE Trans. on PAMI, (2):2 2, 92. [3] R. J. Campbell and P. J. Flynn. A Survey of Free-Form Object Representation and Recognition Techniques. CVIU, 1:1 0, 01. [4] Y. Chen and G. Medioni. Object Modeling by Registration of Multiple Range Images. IVC, (3): 1, 92. [] C. S. Chua and R. Jarvis. 3D Free-Form Surface Registration and Object Recognition. IJCV, 1(1): 99, 9. [] C. Dorai, G. Wang, A. K. Jain, and C. Mercer. Registration and Integration of Multiple Object Views for 3D Model Construction. IEEE Trans. on PAMI, (1):3 9, 9. [] R. O. Duda, P. E. Hart and D. G. Stork. Pattern Classigication, 2nd edition. John Willey and Sons, Inc., [] J. Feldmar, N. Ayache, and F. Berring. Rigid, Affine and Locally Affine Registration of Free-Form Surfaces. IJCV, 3 4 (2):99 1, [9] G. Godin, D. Laurendeau, and R. Bergevin. A Method for the Registration of Attributed Range Images. In Proc. of DIM, pages, [] E. Guest, E. Berry, R. A. Baldock, M. Fidrich, and M. A. 3 Smith. Robust Point Correspondence Applied to Two and Three-Dimensional Image Registration. IEEE Trans. on PAMI, (2):1, 01. [11] K. Higuchi, M. Hebert, and K. Ikeuchi. Building 3-D Models from Unregistered Range Images. GMIP, (4): 3, [] A. E. Johnson and M. Hebert. Using Spin Images for Efficient Object Recognition in Cluttered 3D Scenes. IEEE Trans. on PAMI, ():4 9, [] P. Krsek, T. Pajdla, and V. Hlavac. Differential Invariants 9 49 as the Base of Triangulated Surface Registration. CVIU, 2 3 :2 3, [] T. Masuda. Registration and Integration of Multiple Range Images by Matching Signed Distance Fields for Object Shape Modeling. CVIU, :1, 02. [1] S. Rusinkiewicz and M. Levoy. Efficient Variants of the ICP Algorithm. In Proc. of 3DIM, pages 1, 01. [1] R. Šára. Finding the largest unambiguous component of stereo matching. In Proc ECCV, volume LNCS, pages , [1] R. Šára. Strict sub-kernels. In preparation. [] G. C. Sharp, S. W. Lee, and D. K. Wehe. ICP Registration Pooh 2 Using Invariant Features. IEEE Trans. on PAMI, (1):90 ( , 02. [] L. Silva, O. R. P. Bellon, and K. L. Boyer. Enhanced, Ro- ; ) bust Genetic Algorithms for Multiview Range Image Registration. In Proc. of 3DIM, pages 2 2, 03. [] F. Stein and G. Medioni. Structural indexing: Efficient 3-D object recognition. IEEE Trans. on PAMI, (2):, 92. [] G. Turk and M. Levoy. Zipped Polygon Meshes from Range Images. In ACM SIGGRAPH Computer Graphics, pages 1, 94. [] J. V. Wyngaerd and L. V. Gool. Automatic Crude Patch Registration: Toward Automatic 3D Model Building. CVIU, : 2, 02. [] Z. Zhang. Iterative Point Matching for Registration of Free- Form Curves and Surfaces. IJCV, (2):1 1, 94. [] The Ohio State University Range Image Repository. http: //sampl.eng.ohio-state.edu/~sampl/data/3ddb/rid/minolta/. 3

A Survey of Shape Model Generation from Multiple Range Images (1) ( ) (2) (3) Takeshi Masuda(1), Ikuko Shimizu Okatani(2), Ryusuke Sagawa(3) 1: Nation

A Survey of Shape Model Generation from Multiple Range Images (1) ( ) (2) (3) Takeshi Masuda(1), Ikuko Shimizu Okatani(2), Ryusuke Sagawa(3) 1: National Institute of Advanced Industrial Science and Technology