i CG ICP(Iterative Closest Point) ICP 2 2 ICP 2 2 2

Size: px

Start display at page:

Download "i CG ICP(Iterative Closest Point) ICP 2 2 ICP 2 2 2"

しげのぶかやぬま
5 years ago
Views:

1 24 2 2

2 i CG ICP(Iterative Closest Point) ICP 2 2 ICP 2 2 2

3 ii 2 2 ICP ICP /frame 1.8 /frame ICP ICP 2

4 Comparing performance among registration methods of multi-view Point Clouds Abstract iii Yasuhiro NAKAI 3D models are useful for making realistic CG contents and improving systems for prediction of traffic accident and so on. It is desirable that such 3D models are acquired from real objects. Range scanner is one of the accurate methods of capturing 3D shapes of a real object. Because this method is based on the principles of triangulation, we cannot acquire whole shapes, but only partial shape which is visible from single viewpoint. In order to capture whole shape, we need to capture the object from multiple viewpoints and align them appropriately. Such alignment is performed by estimating the optimal rigid transformations from the captured shapes. This process is called as registration, and estimating the rigid transformations as motion estimation. We aim to realize accurate registration for acquiring complete 3D model from captured shapes. ICP (Iterative Closest Point) algorithm is a well-known method of registration. ICP algorithm automatically performs registration for given pair of partial shape. Each shape generally consists of many points. This method makes correspondence of points between the shapes by finding closest point of one shape for each point of the other. Then this method estimates the rigid transformation that minimizes the sum of distance between corresponding points. By iteratively making correspondence and estimating rigid transformation, we can perform registration for given shapes. When the rigid transformation to be estimated is large, ICP algorithm requires good initial transformation or iterative improvement fails. In order to prevent such failure, we acquire sequence of partial shapes by capturing the slowly moving object, and we perform the registration for neighboring shapes. In order to align multiple partial shapes for acquiring whole one, we need to align every shape into common partial shape. In order to perform registration for pair of distant shapes, which are each shape and the common one, we repeatedly estimate the transformation for pair of adjacent shapes and accumu-

5 iv late them for performing registration for pair of distant shapes. This method, we denote initial registration, can avoid to fail registration. However, since the transformations that are estimated between adjacent shapes have small error, it leads accumulated error in the registration for distant pair. In order to improve the accuracy, we propose methods of registration that remove the accumulated error by running thorough the registration. In this study, we used a method; sequential registration, and proposed another method; hierarchical registration. In sequential registration, we perform ICP registration for first two adjacent shapes in the sequence, and integrate them into one shape. This process decreases the number of shapes in the sequence one by one. We repeat this process until all the shapes in the sequence are integrated into one shape. Since this method does not accumulate rigid transformations, we can say that registration error is not accumulated. However, the number of points in the first shape increases in steps, thus the registration takes more computational cost. In hierarchical registration, we divide all shapes in turn into some blocks that include a certain number of shapes. In each block, we perform the initial registration and integrate them into one shape. We repeat this process until we acquire only one integrated shape. To evaluate the accuracy of these registration methods quantitatively, we performed two experiments. In first experiment, we investigate the relation between the stability of registration for two shapes and the amount of motion. In second experiment, we performed the registration methods for multiple shapes, and compared the accuracy and computational costs. We can evaluate the accuracy of them visually, but quantitative evaluation is difficult. In this study, we put fluorescent markers on the object and measure its rigid motion as groundtruth. By comparing the registration using the markers and ICP registration, we evaluate the accuracy of them quantitatively. Because of these experiments, we can say that sequential registration the best about the accuracy and hierarchical registration is the best about computational cost.

6 ICP ICP

7 1 3 3 CG ICP(Iterative Closest Point) [4] ICP ICP [3][5][6] 2, [7] ICP 1

8 [1] [1] [2] 2

9 N 2 N 1 1 (a) ( ) (b) 1: 3

2.2 1 2 2: 2 2 S 0,S 1 s i S i (x i;l,y i;l,z i;l )( l=0,1,,s i -1) S i S i = x i;0 x i;1 x i;2

10 : 2 2 S 0,S 1 s i S i (x i;l,y i;l,z i;l )( l=0,1,,s i -1) S i S i = x i;0 x i;1 x i;2 x i;si 1 y i;0 y i;1 x i;2 y i;si 1 z i;0 z i;1 x i;2 z i;si (1) S 1 S 0 M 1,0 t 1,0 4

11 3 1 R 1,0 3 3 M 1,0 = R 1,0 t 1,0 0 1 (2) S 1 S 0 S all [ ] S all = S 0 M 1,0 S 1 (3) fps 10 (a) (b) 3: 2 4 5

i,y i,z i,1) p mar 1 p mar 0 M mar 1,0 2.

12 (a) A (b) B 4: S 0,S 1 S i (i=0,1) 1 3 p mar i =(x i,y i,z i,1) p mar 1 p mar 0 M mar 1, p mar 0 = M mar 1,0 p mar 1 (4) 1 1 M mar 2 S 0,S

13 ( 5) 5:

14 3.2 ICP 3.2 ICP ICP (Iterative Closest Point Algorithm) 1 ICP 2 s q S Q s p S P S Q S P q p ICP S P p S Q q 2 q p (q p) P s p ICP 3 q p [ ] T [ ] T q = x q y q z q 1, p = x p y p z p 1 (5) s p l (q l p l ) p l q l q l p l M icp M icp M icp M icp q l 8

15 q l = arg min q Q q M icp p l (6) 2.2 M icp 3 t icp 3 3 R icp 4 4 M icp = Ricp t icp 0 1 (7) s p l (q l p l ) M icp s p d d = s p q l M icp p l (8) l s q,s p 2. ICP p q M icp M icp M icp = arg min M s p q l Mp l (9) l s p M p Mp l q l M RANSAC RANSAC RANSAC 9

16 3. M icp k d k 1 d k δ d k d k 1 < δ (10) ICP ICP ICP 2 ICP ICP 2 1 ICP

17 1 ICP ICP ICP N S 0,S 1,,S N S i s i S i 2.2 (1) 11

18 S i = x i;0 x i;1 x i;2 x i;si 1 y i;0 y i;1 x i;2 y i;si 1 z i;0 z i;1 x i;2 z i;si (11) (a) (b) 6: S 0,S 1,,S N N + 1 N ICP 6(b) S 0 S 1,,S N S 0 S 1 2 ICP S 0 S i (i 0) ICP ICP 6(b) 6(a) S 0 S 1 S 1 S 2 2 6(a) 12

19 S 0 S 1 S 1 S 2 S 0 S 1,,S N S 0 S 1 ICP M icp 1,0 S 1 S 2 M icp 1,0 M icp 2,1 M icp 3,2 M icp N,N 1 S 0 S i S i S i 1 S i 2 S 0 S i M icp i,0 M icp i,0 = M icp 1,0 M icp 2,1...M icp i,i 1 (12) S 1,,S N S 0 S all S all S all = [S 0, M icp 1,0,, M icp N,0S N ] (13) 7 ICP ICP ICP N 1 ICP N 1 S 0,,S N M icp i,i 1 ICP N ICP O(N) M icp j,i =M icp i+1,i M icp j,j 1 (0 i j N) M icp j,i S i S j 6 M icp i+1,i,,m icp j,j 1 j i S i S j M icp j,i S icp j,i 13

7: M icp 1,0,M icp 2,0,,M icp N,0 S 1, S N S icp 1,0, S icp N,0 S icp j,i (j i) M icp j,i S 0 S icp 1,0, S icp N,0 ICP 4.2 4.3 4.

20 7: M icp 1,0,M icp 2,0,,M icp N,0 S 1, S N S icp 1,0, S icp N,0 S icp j,i (j i) M icp j,i S 0 S icp 1,0, S icp N,0 ICP S 0 S icp 1,0 S seq 1,0 S seq 1,0 S icp 2,0 S seq 2,0 2 S seq N,0 8 S 0 S k (1 k N) M icp 1,0 M icp 2,1...M icp k,k 1 k S 0 S k (1 k N) S seq k 1,0 Sicp k,0 M seq k,0 M seq k,0 S 0 S k 1 1 S k 14

21 8: S seq N,0 S all = [S 0, M seq 1,0 S icp 1, M seq 2,0 S icp 2,..., M seq N,0S icp N ] (14) ICP M icp 1,0,,M icp N,N 1 N 1 Sicp 1,0, S icp N,0 S 0 M seq 1,0,,M seq N,0 N 1 M icp 1,0,,M icp N,N 1 ICP M seq 1,0,,M seq N,0 ICP S seq 1,0 S seq 2,0 S seq N,0 S N 1 ICP 3 2 ICP 2 N 1 15

22 O(N + N 1 l=1 l) O(N 2 ) N 4.3 9: S 0 S 1 S N S 0 S icp 1 S icp N S0 hier S1 hier S N hier 1 a( a N) a f N a f f a f 1 16

23 f 1 N 2 N a 3 N a 2 a S hier ua a,,s hier ua 1 Sua 1,ua a hier u f N a f ua u= N a f 1 1 (f=1) N S hier 0,,S hier a 1 (S0 hier ) S a 1,0 hier Shier a,,s2a 1 hier (Shier a ) S0 hier M icp a,0 S2a 1,a hier S hier 0 N a S hier N,N (a 1) Shier a 1,0 2 (f=2) S hier a 1,0 Shier 2a 1,a (Shier a 1,0 Shier 2a 1,a) (S2a 1,a hier Shier 3a 1,2a) ICP a Sua 1,(u 1)a hier Shier (u+1)a 1,ua Shier (u+a 1)a 1,(u+a 2)a S hier (u+a 1)a 1,(u 1)a S hier N,0 f N ICP a f 1 N 1 f 1 1 a f 1 a f 1 f=log a N log an O( a i 1 N) (15) i=1 O( alog a N 1 N) (16) a 1 x = a log a N 1 a log a x + 1 = log a N (17) x = N 1 (18) 17

24 O( N 1 N) a=2 a 1 O(N(N 1)) a ICP ICP ICP 4 ICP ICP ICP ICP ICP s p l (l=1,,s p ) p l 18

25 M mar M mar p l l p l ICP M icp M icp p l ϵ ϵ = sp l=1 M icp p l M mar p l s p (19) ICP 5.2 ICP ϵ ϵ 2 2 ICP ICP Point Cloud Library[8] 2 S i S j i j ICP i j A 156 B 105 1frame ω= A kω = /frame B kω =1.8, ,

26 /frame (k=1,2,3,4,5,6) ϵ kω (S 0,S k ),(S 1,S k+1 ),(S 2,S k+2 ), 1 (S 0,S k ),(S 209,S 209+k ) 210 A B 11(a) 12(a) A 1.2 /frame /frame /frame /frame 6.0 /frame 7.2 /frame B /frame /frame /frame 3.6 /frame A ICP ICP ICP Y A B 11(b) 12(b) A 10 B A

27 A ICP 30 10(a) (a) (b) 10 (c) 20 (d) 30 (e) 40 (f) 50 10: ( A) ICP 1 1 A 1.2 /frame B 1.8 /frame ICP 30, 216 A B 13 21

28 (a) (b) 11: ( A) 22

29 (a) (b) 12: ( B) 23

30 A B A B 216 A 60 2 B A B 216 A B A Point CLoud Library 1: A

31 (a) A (b) B 13: (a) (b) (c) 14: 3 ICP ( A) 25

32 (a) (b) (c) 15: 3 ICP ( B) 2: B ICP ICP 2 ICP ICP 26

33 2 1 3 [1], :,, pp (1990). [2],,,,, : Belief-Propagation,. D,, Vol. 93, No. 8, pp (2010). [3] Godin, G., Laurendeau, D. and Bergevin, R.: A Method for the Registration of Attributed Range Images, Int. Conf. on 3D Imaging and Modeling, Quebec, May 28, pp (2001). 27

34 [4] Rusinkiewicz, S. and Levoy, M.: Efficient Variants of the ICP Algorithm, Third International Conference on 3D Digital Imaging and Modeling (3DIM) (2001). [5] Masuda, T. and Yokoya, N.: A robust method for registration and segmentation of multiple range images, Comput. Vis. Image Underst., Vol. 61, pp (1995). [6] Trucco, E., Fusiello, A. and Roberto, V.: Robust Motion and Correspondence of Noisy 3-D Point Sets with Missing Data (1999). [7] Masuda, T.: Registration and integration of multiple range images by matching signed distance fields for object shape modeling, Comput. Vis. Image Underst., Vol. 87, pp (2002). [8] Rusu, R. B. and Cousins, S.: 3D is here: Point Cloud Library (PCL), International Conference on Robotics and Automation, Shanghai, China (2011). 28

2 ( ) i

2 ( ) i 25 Study on Rating System in Multi-player Games with Imperfect Information 1165069 2014 2 28 2 ( ) i ii Abstract Study on Rating System in Multi-player Games with Imperfect Information Shigehiko MORITA