JATIT Keterangan : Telah dipublikasikan pada :

JATIT Keterangan : Telah dipublikasikan pada : http://www.jatit.org/volumes/Vol51No3/fiftyfirst_3_2013.php

Journal of Theoretical and Applied Information Technology 31st May 2013. Vol. 51 No.3 © 2005 - 2013 JATIT & LLS. All rights reserved.

ISSN: 1992-8645

www.jatit.org

E-ISSN: 1817-3195

POINT CLOUD REGISTRATION FOR A NON-DEFORMABLE OBJECT USING SURFACE CURVATURE FEATURES 1

EKO MULYANTO YUNIARNO, 2MOCHAMAD HARIADI, AND 3MAURIDHI HERY PURNOMO.

1

PhD Candidate, Dept. of Electrical Engineering, Institute of Technology Sepuluh Nopember (ITS), Indonesia 2 Assoc Prof., Dept. of Electrical Engineering, Institute of Technology Sepuluh Nopember (ITS), Indonesia 3 Prof., Department of Electrical Engineering, Institute of Technology Sepuluh Nopember (ITS), Indonesia E-mail: [email protected], [email protected], [email protected] ABSTRACT Recently, many applications require 3D information of an object (i.e. point cloud) such as 3D image scanning, 3D surface reconstruction and etc. However many researches on point cloud registration face many challenges especially for increasing the accuracy of point cloud matching. This research employs surface curvature features in discrete surfaces. A surface curvature feature is a pointer of ridges that are invariant to rigid body transformations. In this paper, a new algorithm of point cloud registration for non deformable object is proposed. This algorithm employs surface curvature features estimated by fitting knearest neighbor of local point to hyperbolic paraboloid equation. The proposed algorithm is implemented with Iterative Closest Point (ICP) technique and quantitatively evaluated and compared with common techniques for point cloud registration. Experimental results demonstrate that the proposed technique approximately 63% faster and 23% more accurate than iterative closest point with angular invariant feature (ICP-AIF) registration techniques. These results are obtained by testing the proposed frame work with noise, different pose of point cloud and overlapped area. Keywords: Registration, Point Cloud, Surface Curvature Feature.

1. INTRODUCTION Recently, 3D computer models of real world objects have been widely used for virtual reality applications such as business (real estate, architecture), education (electronic museums, multimedia books) and entertainment (3D interactive games, movie)[10]. It is also to construct a virtual environment of a real environment for Industrial Robotics and inverse engineering purposes[19]. To build a 3D model required the coordinates of the object surface is collected from a 3D acquisition equipment such as a 3D scanner[14] or by using multiview 3D image reconstruction technique [13]. Due to its high density, the data point is often referred to as point cloud. A point cloud of a single view can not accommodate the entire shape of the object due to self occlusion and the limitation of the field of view of the 3D scanner[12]. To build the entire object required some data points captured from multiple viewpoints to obtain the entire surface [10]. Furthermore, point cloud is registered to obtain a complete 3D model. The

registration of point clouds can be defined as the process of estimating the rigid transformation that places point clouds in to a common coordinate system[2]. To register point cloud it is started by data matching method to establishing correspondences between two point clouds followed by transformation estimation[11]. Iterative closest point algorithm (ICP)[4] is a common algorithm registration that widely used by researchers. ICP and its invariant [5][3][6][15] is based on metric distance techniques to find the closest point to establish correspondence. This techniques can lead the registration algorithm converge to a local minima because the closest points is not exactly represent compatible point on the original surface. Some researches using features such as color[10], curvature[9], spin image[17] that have extracted from a set of point interest previously selected in both point cloud to find the compatible points. Two points are compatible if the value of the associated features lies below a threshold. This paper proposes a novel registration algorithm for non-deformable object based on

506


ISSN: 1992-8645

www.jatit.org

E-ISSN: 1817-3195

surface curvature matching to find the closest point. Non-deformable object is a special case of a system of particles where in the distances between all particles remains unchanged. In the proposed algorithm, the surface curvature is represented by surface curvature feature is extracted from a local surface. To find the closest compatible point, we match the points by finding the nearest surface curvature feature in one point cloud to another point cloud. 2. POINT CLOUD REGISTRATION AND SURFACE CURVATURE FEATURE

Fig 1. The view of curvature direction

2..1. Point Cloud Registration Multiple point clouds that obtained from 3D range acquisition equipment are in the local coordinate system with respect to the range finder. The purpose of point clouds registration is to find the relative position and orientation one point cloud to another point cloud. Given two point set ଵ , . . , ே and ଵ , . . , ே where N the number point. If ௜ is the ith data point of the whole data point set P and ௜ denote the ith data point of the whole data of point set Y which ௜ , ௜ is pair point matching. Point cloud registration problem is to find rigid transformation parameters , with R is rotation matrix and is translation vector which minimize a cost function in the least square distance metrics following: N r r r min r ∑ (R. pi + t ) − yi R ,t

i =1

(1)

2.2. Surface Curvature On a Non-Deformable-object, surface curvature is an important feature because of its invariance with respect to the rigid transformation[1]. Surface curvature is defined as the curvature of a curve on the surface passing through a point. The maximum curvature (k1) and the minimum curvature (k2) of the curve is referred as the principal curvature.

Fig 2. The Relation Between Angle And Z Coordinate Of Closest Curve C, With Which Surface Curvature Feature Can Be Constructed.

The associated vector of the principal curvature is called as principal directions ( and ). Fig.1 shows the Principal directions and normal vector at a point on surface S construct a local coordinate at point [18]. 2.3. Surface Curvature Feature Definition Suppose S is a local surface which centered at point and the normal vector of surface S pointing to positive Z axis. If is located at origin and is a point that lie on the local surface S. Fig.2 shows, in cylindrical coordinates system is represented as graph function , which r is the radius of the point to the central point and is the angle between the reference direction on the chosen plane and the line from the origin to the projection of on the plane. If r is set to α , it will be obtained a closed curve c on local surface S whithin α. Sampling those z coordinate of the closed curve c at θ= θ1, θ2,., θk one lap will obtain the relation between the angle and the z coordinates of the closed curve on local surface S at radius α.

507


ISSN: 1992-8645

www.jatit.org

E-ISSN: 1817-3195

This relationship is defined as the surface curvature feature of the point which denoted by ଵ , ଶ , . . , ௞ .

minimum curvature of the local surface S are ଵ and ଶ respectively. The eigenvector of matrix hessian H are the principal direction of local surface S , .

3. REGISTRATION POINT CLOUD USING SURFACE CURVATURE FEATURE.

3.3. Point Cloud Matching Using Surface Curvature Feature.

3.1. Surface Normal Estimation Geometry properties such as normal vectors and principal direction have an important role within the proposed frame work. This geometry property is used to construct local coordinate system in the whole point in every point cloud. This section describes the estimation of normal vectors for each point. Our work adopt Thürme, et al [16] for finding normal vector of a point. The Normal vector at a point ௜ is estimated by calculating the angle-weighted average of the normal vector of the triangle arranged by the point ௜ and its neighbors. If ௜ ௜ଵ , ௜ଶ , . . , ௜௞ , ௜௝ ∈ , ௜௝ ௜ is k neighboring points are connected directly to the r point pi the surface normal vector is r r r r k ( qij − pi × qij +1 − pi ) r 1 (3) ni = k wj r r r r qij − pi × qij +1 − pi j =1

Given two point set ଵ , ଶ , . . , ே and ᇱ . If ௜ is the ith of the whole ᇱ ଵᇱ , ଶᇱ , . . , ேᇱ data point set P and ௝ᇱ is the jth data point of the whole data point set P. Let ప ᇱ ᇱ ᇱ ௜ଵ , ௜ଶ , . . , ௜௞ and "௝ᇱ # "௝ଵ , ௝ଶ , . . , ௝௞ # are surface curvature feature related to the point ௜ and point ௝ᇱ respectively. The point matching strategy is finding the closest point with respect of the surface curvature feature distance. The surface curvature distance of ௜ $ "௝ᇱ # is : r r d ( SCF ( pi ), SCF ( p ′j )) =

 −1  w j = cos   

r r r r qij − pi × qij +1 − pi r r r r qij − pi qij +1 − pi

    

− z ′jk ) 2

(7)

(8)

3.4. Rigid transformation estimation Rigid transformation of two point sets

r { pi }iN=1

and { pc′ ( i ) }i =1 is estimating by calculated the matrix r rotation R and the vector translation t that

r

The principal curvature and principal direction is calculated by decomposition of eigenvalue and eigenvector of hessian matrix of the local surface of point pi [7]. This local surface is estimated by fitting of k nearest neighborhood of ௜ to hyperbolic paraboloid function : (5) z = f ( x, y ) = a x 2 + b y 2 + cxy + dx + ey + g 2

The hessian matrix of (5) is

a c  H =  c b

ik

r r  N c (i ) = arg min  ∑ d ( SCF ( pi ), SCF ( p′j ))   j∈{1..N '}  i =1

(4)

3.2. Principal Curvature and Principal Direction Estimation.

2

k =1

ᇱ between two point sets P Correspondence ௜ , ௖ሺ௝ሻ and P’ is computed based on c(i).

∑

where wj is the weight which is the angle two successive tangent vectors.

K

∑ (z

N

minimize the distance error between

r { pi }iN=1 and

r { pc′ (i ) }iN=1 as follow:  NP r r r r (R, t ) = arg min  ∑ Rpi + t − p c′ (i ) )  r i =1 R ,t 

   

(9)

Where areas, we solved the rotation matrix R and r the translation vector t using Singular Value Decomposition (SVD) as described in [8].

(6) 3.5. Proposed Registration Algorithm.

If ଵ and ଶ are the eigenvalue of matrix hessian H which | ଵ |> | ଶ | then the maximum and the

In this paper, we propose 3D registration using surface curvature feature. Our registration

508


ISSN: 1992-8645

www.jatit.org

algorithm is based on standard iterative closest point (ICP) algorithm proposed by Besl[4] but unlike the standard ICP, our algorithm registration using surface curvature feature to find the coordinate closest compatible point. Given two set of point cloud ଵ , ଶ , . . , ே and ᇱ %ଵᇱ , ଶᇱ , . . , ேᇱ ᇲ & which N and N’ are the number of point in point sets P and P′ respectively. Registration techniques is initialized by setting rotation matrix R0 to unit 'ଷൈଷ ∈ ଷൈଷ , translation vector ଴ to (0,0,0), iteration index m to 0 and P0 = P . The registration

E-ISSN: 1817-3195

ᇱ ௠௜ , ௠௖ሺ௝ሻ

which is have distance less than the threshold td and surface curvature feature distance vector less than threshold tc to remove false pair matching. Step 6: Calculate the root mean square error as the cost function NP r r X = ∑ ( R ( m+1) p( m+1) i + t( m+1) ) − p(′m+1) i i =1

2

(11)

If ߳ less than threshold t then terminated the iteration else repeat step 4.

algorithm using surface curvature feature can be stated as follows: Step1: Construct local coordinate system of each point. The local coordinate system of each point is constructed from the normal vector and the principal direction of each point. The estimation of normal vector and principal direction in a point is described on sub section 3.1 and sub section 3.2.

(a)

Step 2: Construct surface curvature feature vector for each point. Based on the local coordinate system that has calculated in Step 1, the surface curvature of point ௜ and ௝ᇱ is calculated by finding the z coordinate of the point on local surface of point ௜ and ௝ᇱ within radius r from z axis and angles θ1, θ2,., θk from reference axis x. The surface curvature feature vector of point ௜ and point ௝ᇱ are ௜ ௜ଵ , ௜ଶ , . . , ௜௞ and ᇱ ᇱ ᇱ "௝ᇱ # "௝ଵ , ௝ଶ , . . , ௝௞ # respectively. Step 3: Find pair matching point between two sets ᇱ P and P’. The pair matching point ௠௜ , ௠௖ሺ௝ሻ is calculated by finding the closest distance between two surfaces curvature feature ௠௜ and ᇱ "௠௝ # as described in sub section 3. 3. Step 4: Estimated rotational and translational transformation matrix for (m+1) iteration. The rotational matrix R(m+1) and transformation vector ሺ௠ାଵሻ is estimated by minimizing the distance error ே

ᇱ between ௠௜ ே ௠௖ሺ௜ሻ & ௜ୀଵ and % ௜ୀଵ sub section 3.4

as described in

Step 5: Apply the registration of each point in Pm: ሺ௠ାଵሻ௜ ሺ௠ାଵሻ ሺ௠ାଵሻ௜ +ሺ௠ାଵሻ௜

|(10)

Step 6: Update correspondence. Correspondence ᇱ ሺ௠ାଵሻ௜ , ሺ௠ାଵሻ௖ሺ௝ሻ is updated by selecting the pair

(b) Fig. 3.Point cloud models of test object : (a) wave, (b) bunny

4. EXPERIMETS AND RESULT In this section, we evaluate the performance of proposed registration algorithm We is test the proposed algorithm on two objects wave and bunny object. The wave objects is a pair synthetic surfaces that are consisting 10000 vertex obtained from non-uniform sampling of 3D sinusoidal surface. Overlap area, pose, and noises of the wave objects can be adjusted to test the proposed algorithm performance in different setting. The bunny object is obtained from data repository of Stanford University that is consisting five different views. The amount of points of each view is shown in table 1 while each view pose is shown on Fig.4.

509


ISSN: 1992-8645

www.jatit.org 20

Rms registration error (mm)

We called our algorithm registration as iterative closest point using surface curvature feature (ICPTable 1. The Number Of Point Each View Of Bunny Object

View-1 View-2 View-3 View-4 View-5

Amount of point 40256 40097 30379 31701 35336

E-ISSN: 1817-3195

Pose (degree) 0 45 90 270 315

ICP ICP-AIF ICP-SCF

15

10

5

0

10

20

30

40

50

Iteration

(a) Rms registration error (mm)

20

(a)

(b)

ICP ICP-AIF ICP-SCF

15

10

5

0

10

20

30

40

50

Iteration

(b) Rms registration error (mm)

20

(d)

(c)

15

10

5

0

(e)

ICP ICP-AIF ICP-SCF

10

20

30

40

50

Iteration

(c) Fig 5. Rms Registration Error (Ground Truth) Of Wave Object Vs Iteration (Count/Number) With Different Amounts Of Noise : (A) 2%,(B) 7% And (C) 10% Noise.

Fig.4. Pose of each view of the bunny object (a) 0o, (b)45 o, (c)90 o, (d) 270 o, and (e) 315 o

SCF). We compare our algorithm with original Iterative Closest Point Algorithm (ICP)[4] and ICP with angular invariant feature algorithm (ICP-AIF)[9]. We know the real conjugate points between point clouds. Therefore, we measure RMS distance error between two ground truth point sets. All registration result is plotted as graphic RMS registration error (ground truth) as a function of iteration number. The tests are performed on a computer with a processor "Intel" Core (TM) 2 Duo CPU, frequency 2 GHz and a memory of 2 GB.

4.1. Registration Algorithm Test For Object

Wave

We perform three different tests to the wave object: noise, overlapped areas, and pose test. 4.1.1 Noise test. In the noise test, we set the overlap area of surfaces fix 90% and the pose is set by rotating one of the

510


ISSN: 1992-8645

www.jatit.org

E-ISSN: 1817-3195 6


surface 5 degree to x-axis and y-axis. We perform three tests by adding 2%, 7%, and 10% noise on each test to both surface . The registration results are plotted in Fig. 3, RMS registration as a function of iteration number. Fig. 5 shows that proposed algorithm convergent at 5, 10 and 13 iteration in 2%, 7% and 10% noise testing with 2 mm rms registration error however ICP algorithm convergent at 30 iteration with rms error registration 3 mm in all noise testing. The result of ICP-AIF registration shows that ICP-AIF

4 3 2 1 0

10 5

20

30

40

50

Iteration

(a) ICP ICP-AIF ICP-SCF

30

4 3 2 1

5

10

15

20

25

30

Iteration

(b) 6

15 10 5

10

20

30

40

50

Iteration

(b) 30


25

ICP ICP-AIF ICP-SCF

20

0

ICP ICP-AIF ICP-SCF

25

ICP ICP-AIF ICP-SCF

5 4 3 2 1 0

20

5

10

15

20

25

30

Iteration

15

(c) Fig 7. Rms registration error (ground truth) of wave object in different pose by rotating one of the surface to x-axis and follow to y-axis: (a) 4,(b) 10 and (c) 17.

10 5 0

20

5

0



30 25

15

(a)

15

10

10

6

20

0

5

Iteration

ICP ICP-AIF ICP-SCF



30 25

ICP ICP-AIF ICP-SCF

5

10

20

30

40

50

Iteration

(c) Fig 6. Rms Registration Error (Ground Truth) Of Wave Object Vs Iteration (Count/Number) With Different Overlap Area Rate : (A) 86%,(B) 68% And (C) 41% Of Overlapped Area Rate Between Two Surfaces.

convergent at 15 and 30 iteration in 2% and 7% noise test with registration error rms 3 mm. When ICP-AIF is tested with 10% noise, the algorithm failed to reach converge. 4.1.2 Overlapped area test Overlapped area is part of the surfaces that have common area. In the overlapped area test, we test

511


ISSN: 1992-8645

www.jatit.org

E-ISSN: 1817-3195


150 ICP ICP-AIF ICP-SCF 100

50

0

10

20

30

40

50

Iteration

Fig 8. Rms Registration Error (Ground Truth) Result Of Object Vs Iteration (Count/Number) Of View-1 And View2 Of Bunny Object.

the proposed algorithm to the wave object in three different percentage of overlapped area which are 86%, 68%, and 41%. We set noise rate fixed to 2% and set pose by rotating one of the surface 5 degree to the x axis and y-axis. The result is plotted in fig 6 as RMS registration error as the function of iteration number. Fig.5 shows that our proposed algorithm converge well at 5,10, and 15 iteration with rms error 2 mm in 86%, 68%, and 41% overlapped test while the ICP-AIF achieve convergence at 15, 23, and 29 iteration with rms registration error 3mm. Registration with ICP algorithm convergence well in 45 iteration in 86% overlap area test with the rms error (ground truth) 5mm. While in test with overlap less than 68% of the registration is fails. 4.1.3 Pose test To test the algorithm in different pose we rotate one of the surface to the x-axis and to y-axis by 4,10, and 17 degree. Noise and surface overlapped area is set fixed 2% and 80% respectively. The result is plotted in Fig.7 RMS registration error as function of the number of iteration. Our proposed algorithm convergent at 1,2, and 4 iteration with rms registration error 0.4 mm at 4, 10, and 17 degree pose test while ICP-AIF convergent at 5,

Fig. 9 The Result Of Registration All Views Of Bunny Object. Each View Is Transformed Relatively To View- 1.

20, and 25 iteration with RMS error registration 0.45. The result of ICP registration test shows that in 4 degree pose test ICP convergent well at 20 iteration with rms error registration 0.45 while at 10 and 17 degree pose test, ICP convergent at more than 30 iteration. 4.2. Registration Algorithm Test For Bunny Object We use five views of the bunny object to test our proposed algorithm which each view is shown in Fig.8. Each view have relative pose of 45o except View-3 and View-4 have relative pose of 90o. We test all of view by registering the nearest pair view. Fig.8 is the result of View-1 and View-2 registration of bunny object. It is shows that the ICP-SCF achieve convergence at 5 iterations with rms error registration 0.317 mm however ICP-AIF algorithm achieve convergence at 30 iterations with RMS registration error 0.336. The registration result of ICP algorithm shows that the algorithm fail to achieve convergence. This condition occurs in other registration test. All of result test is summarized in Table 3. We don’t include the result of ICP registration because the ICP algorithm fail to achieve convergence when it tested to the bunny object. The registration result of all view of bunny object is shown in Table 3. We compare the iteration convergence amount, convergence time, Rms error registration and processing time after 50 iteration between ICP-SCF and ICP AIF. Proposed algorithm convergent in average

Table 3 Result Of Bunny Objects Registration Iteration Convergence Registration View 1-View 2 View 2-View 3 View 3-View 4 View 4-View 5 Average

ICP-AIF 43 47 48 63 50.25

ICP-SCF 28 43 49 26 36.5

Convergence Time (sec) ICP-AIF ICP-SCF 0.100 0.032 0.053 0.050 0.047 0.039 0.065 0.019 0.066 0.035

512

RMS Error Registration (mm) ICP-AIF ICP-SCF 0.336 0.317 0.326 0.339 0.294 0.275 0.443 0.299 0.397 0.307

Processing Time After 50 iteration (sec) ICP- AIF ICP-SCF 0.109 0.045 0.054 0.053 0.279 0.053 0.047 0.032 0.122 0.045


ISSN: 1992-8645

www.jatit.org

36.6 iteration or in 0.035 second with RMS registration error average 0.307 mm while ICPAIF algorithm convergent in average 50.25 iteration or in 0.066 second with rms registration error average 0.397 mm. Processing time average after 50 iteration of the proposed algorithm takes 0.045 second while ICP-AIF takes 0.122 second. It shows that our algorithm 63% faster and 23% more accurate than ICP-AIF. Fig.9 shows the result of all views of bunny object. Each view is transformed relatively to View-1 as the result of registration process.

[6]

[7]

[8]

5. CONCLUSION This research proposes an algorithm for point cloud registration base on surface curvature features estimated by fitting k-nearest neighbor of local point to hyperbolic paraboloid equation. The proposed algorithm is implemented with Iterative Closest Point (ICP) technique so called ICP-SCF. In experiment we compare ICP-SCF vs ICP and ICP-AIF then testing them with noise, rigid transformation and overlapped area. In the experiment, while ICP algorithm fail to achieve convergence, ICP-SCF demonstrates approximately 63% faster and 23% more accurate than ICP-AIF.

[2]

[3]

[4]

[5]

[10]

[11]

[12]

REFERENCE : [1]

[9]

Agam, G. and Tang, X.T.X. 2005. A Sampling framework for accurate curvature estimation in discrete surfaces. IEEE Transactions on Visualization and Computer Graphics. 11, 5 (2005), pp 573– 583. Arun, K.S., Huang, T.S. and Blostein, S.D. 1987. Least-Squares Fitting of Two 3-D Point Sets. IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI9, 5 (Sep. 1987),pp 698–700. Bergevin, R., Soucy, M., Gagnon, H. and Laurendeau, D. 1996. Towards a general multi-view registration technique. IEEE Transactions on Pattern Analysis and Machine Intelligence. 18, 5 pp (May. 1996), 540–547. Besl, P.J. and McKay, N.D. 1992. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence. 14, 2 (1992), pp 239– 256. Chen, Y. and Medioni, G. Object modeling by registration of multiple range images. Proceedings. 1991 IEEE International

[13]

[14]

[15]

[16]

513

E-ISSN: 1817-3195

Conference on Robotics and Automation pp 2724–2729. Gérard Blais, M.D.L. 1993. Registering Multiview Range Data to Create 3D Computer Objects. IEEE Transactions on Pattern Analysis and Machine Intelligence. 17, (1993), pp 820–824. Hartmann, E. 1999. On the curvature of curves and surfaces defined by normal forms. Computer Aided Geometric Design. 16, 5 (Jun. 1999), pp 355–376. Huang;D.Bloestein, K.S.A.S. 1987. LeastSquaresof Two Point Sets. IEE Transactions On Pattern Analysis And Machine Intelligence. PAMI-9, 5 (1987), 698–699. Jiang, J., Cheng, J. and Chen, X. 2009. Registration for 3-D point cloud using angular-invariant feature. Neurocomputing. 72, 16-18 (Oct. 2009), 3839–3844. Johnson, A.E. and Kang, S.B. 1998. Registration and Integration of Textured 3D Data. (1998), 1–25. Kim, D. and Kim, D. 2010. A Fast ICP Algorithm for 3-D Human Body Motion Tracking. IEEE Signal Processing Letters. 17, 4 (Apr. 2010), 402–405. Krishnan, S., Lee, P.Y., Moore, J.B. and Venkatasubramanian, S. 2005. Global Registration of Multiple 3D Point Sets via Optimization-on-a-Manifold. SGP ’05 Proceedings of the third Eurographics symposium on Geometry processing. (2005). Leung, C. and Lovell, B.C. 2003. 3D Reconstruction through Segmentation of Multi-View Image Sequences. Proceedings of the 2003 APRS Workshop on Digital Image Computing. (2003), pp 87–92. OuYang, D. and Feng, H.-Y. 2005. On the normal vector estimation for point cloud data from smooth surfaces. ComputerAided Design. 37, 10 (Sep. 2005), pp 1071–1079. Park, S.-Y. and Subbarao, M. 2003. An accurate and fast point-to-plane registration technique. Pattern Recognition Letters. 24, 16 (Dec. 2003), 2967–2976. Thürmer, G. and Wüthric, C. 1998. Computing Vertex Normals from Polygonal Facets. Journal of Graphics Tools. 3, 1 (1998), pp 43–46.


ISSN: 1992-8645

[17]

[18]

[19]

www.jatit.org

Torre-Ferrero, C., Llata, J.R., Robla, S. and Sarabia, E.G. 2009. A similarity measure for 3D rigid registration of point clouds using image-based descriptors with low overlap. 2009 IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops. (Sep. 2009), pp 71–78. Zhihong, M., Guo, C., Yanzhao, M. and Lee, K. 2011. Curvature estimation for meshes based on vertex normal triangles. Computer-Aided Design. 43, 12 (Dec. 2011), 1561–1566. Zhou, H. and Liu, Y. 2006. 3D Modelling from Multi-view Registered Range Images Using K-means Clustering. 2006 IEEE International Conference on Industrial Technology (2006), pp 722–727.

514

E-ISSN: 1817-3195

Jurnal Kursor Keterangan : Telah dipublikasikan pada : http://kursor.trunojoyo.ac.id/?p=494

ISSN 0216 – 0544

Vol. 6, No. 4, Juli 2012

POINT CORRESPONDENCECORRECTION BASED ON SURFACECURVATURE FEATURES a

Eko Mulyanto Yuniarno,bMochamad Hariadi, cMauridhi Hery Purnomo a,b,c

Electrical Engineering Dept., Faculty of Industrial Technology Sepuluh Nopember Institute of Technology, Surabaya 60111 E-mail:[email protected] Abstrak

Model komputer object 3D dari suatu nyata telah banyak digunakan di berbagai macam aplikasi seperti motion capture, visi computer dan komputer grafik. Untuk membangun model komputer 3D tersebut, data point cloud multiview objek nyata dari beberapa sudut pandang yang diperoleh dari scanner 3D harus diregistrasi untuk diletakan pada sistem koordinat acuan yang sama. Salah satu langkah yang penting didalam registrasi adalah korespondensi Salah korespondensi akan mempengaruhi kualitas registrasi. Pada paper ini diusulkan teknik baru perbaikan korespondensi sehingga kualitas registrasi dapat ditingkatkan. Perbaikan korespondensi dimulai dengan mencari kandidat pasangan titik pada dua point cloud menggunakan konstrain rigid dua titik referensi dan dilanjutkan dengan perbaikan korespondensi dengan menggunakan fitur kurfatur permukaan. Teknik tersebut diaplikasikan pada tiga algorithma registrasi yaitu ICP, ICP-AIF dan ICP-SCF dan hasilnya dibandingkan dengan algorithma registrasi tanpa perbaikan korespondensi. Hasil percobaan menunjukan bahwa algorithma registrasi dengan perbaikan korespondensi 63% lebih cepat, 23% lebih akurat dan 530% lebih banyak menemukan korespondensi yang tepat dibanding dengan registrasi algorithma tanpa perbaikan korespondensi. Kata kunci: Regsitrasi, Point Cloud, Surface Curvature Feature, Korespondensi. Abstract

3D computer model of a real object has been widely used in various applications such as motion capture, computer vision and computer graphics. To build a 3D computer model, multiview data point cloud of real object from different view point that obtained from a 3D scanner must be registered to placing the multiview data point cloud into a common coordinate system. Correspondence to find pair point matching is an important step in registration. False correspondence will affected to the registration quality.A novel technique of point correspondence correction between two point clouds is presented in this paper. The correspondence technique is started by selecting pair point matching candidate base on two reference point constraint then followed by correspondence correction using surface curvature feature. We tested the technique by applying thecorrespondence correction technique into three registration algorithm registration which is ICP, ICP-AIF and ICP-SCF then compare it with the original registration algorithm The result shows that registration algorithm using correspondence correction 63% faster, 23% more accurate and to find 530% more correct pair matching point than the original registration algorithm. Key words: Registration, Point Cloud, Surface Curvature Feature, Correspondence.

190 Jurnal Ilmiah KURSOR Vol. 6, No. 4, Juli 2012, hlm. 189-196

INTRODUCTION Constructing a 3D computer model of a real object from 3D surface measurement data has various applications in computer graphics, virtual reality, computer vision and reverse engineering. To build a 3D model it is necessary to have the 3D information of the object surface which is collected by scanning device such as Laser scanner. However, most scanning device can only acquire partial information on the object surface at one viewpoint. In order to obtain a complete model, multiple acquisition from different pose must be performed. Then the derived local point cloud must be transformed into a common coordinate system. This procedure is usually referred to as registration. Registration is performed within two stage, correspondence to find pair compatible point and follow by estimation of the transformation motion. Correspondence is difficult task. False to find correspondence will be affected to the registration quality. So exactly find point correspondence and effectively reject false matching pairs are important for increase registration accuracy. Iterativeclosestpointalgorithm(ICP)[1] is a common algorithm registration that widely used by researchers. ICP and its invariant [2][3][4][5] establish correspondence by finding the closest point base on the metric distance techniques to find closest compatible point. This techniques can lead the registration algorithm converge to a local minima because the closest points is not exactly represent compatible point on the original surface. Some researches improve correspondence point using features such as color[6], curvature[7], spin image[8]that have extracted from a set of point interest previously selected in both point cloud to find the compatible points. Two points arecompatible if the valueof theassociatedfeaturesliesbelow athreshold. To find correct correspondence Liu [9] propose three constraint. These can remove false point pair moderately but effective is only the overlapped surface is closest enough. This paper propose a correspondence correction technique to increase the number of correct compatible point. To find correct compatible point first we select candidate correspondence point using two reference point constraint then correspondence correction using

surface curvature feature is performed. Our technique is successful to increase the number of correct compatible point during correspondence stage.

RIGID OBJECT MOTION A rigid-body can be regarded as a set of N points remains constant under an arbitrary motion undergone by the set. Given two sets of point and that derived from 3D scanner device from different view. Distance any point on rigid object is constant (1) where

and

are any point at P.

Rigid objects motion have six degree of freedom. Three coordinates are needed to locate the bodys’s center of mass and three is to describe its orientation. [10]. The relation set point P and P’ as follow: (2) where R is the orientation matrix and T is the translation vector. Using set of two correspond point which , the motion of set point P to P’ can be estimated by minimizing the distance of correspondence point using the least square distance metrics. N    min   ( Rp i  t )  y i R ,t

(3)

i 1

Arun et all using SVD to calculated the rigid motion R and T’[11] Distance of Two Vector Given two vector and and distance between vector denoted:

which . The and vector (4)

Which d is distance operator. In this paper d will be use as represent the distance of two vector.

Yuniarno et al., Point Correspondence Correction…191

can be , matching points stated as correct pair correspond point if satisfy the constraint: (8) and (9) Figure1. Object Ais Transformed into A’ Using Rigid Motion, is Two Reference Point, is The Conjugate of . Liu’s Point Constraint To increase the number of correct correspondence Liu propose three constrain to find point matching.Let ( ) and ( ) are two pair point. Point pair constraint as follows [9] are: 1) Orientation constraint (5)

Where and are the reference point and its conjugate respectively. Base on rigid constraint using two reference point,a pair correspondence point can be computed which based on c(i) as follow:  N N c(i)  arg min   (r1i  r1' j )2  (r2i  r2' j ) 2 j  i 1 j 1





0.5

   

(10)

where , , and

2) Rigidity constraint (6) 3) Matching error constraint. (7) With This three constraint canremove moderate of false pair point matching. Rigid Constraint Using Two Reference Point This section will investigate rigid constraint using two reference point for predict the correct position of pair point matching. The Liu’s rigidity constraint using one point as reference point is effective when the overlapped surface is closest enough. Our correspondence technique correction fix false correspondence precisely by predict the correct position of the pair point matching using two reference point as rigidity constraint. Figure1 shows a rigid object A is transformed into A’ using rigid transformation. If two point set and t are the point cloud that obtained using 3D scanner device of the object A and its transformed A’ respectively. Based on rigid constraint using two reference point, pair

SURFACE CURVATURE FEATURE Surface curvatureis definedasthe curvature ofacurveon thesurfacepassing through a point. On a rigid object, surface curvature is an important feature because of its invariance with respect to the rigid transformation[12]. Base of this idea we establish surface curvature feature of point to predict surface geometry of a point. Suppose S is a local surface which centered at point and the normal vector of surface S pointing to positive Z axis. If is located at origin and is a point that lie on the local surface S. Figure 2shows, in cylindrical coordinates system isrepresented as graph function which r is the radius of the point to the central point and is the angle between the reference direction on the chosen plane and the line from the originto the projection of on the plane. If r is set to , it will be obtained a closed curve c on local surface S withinSampling those z coordinate of the closed curvecat kone lap will obtain the relation between the angle and the z coordinates of the closed curve on local surface S at radius 


(a)

Figure 2. The relation between angle and z coordinate of closest curve c, with which surface curvature feature can be constructed. Build surface curvature feature of each point on set point P and P’.

(b) Figure 5. Correspondence Comparison Result. (A) Without Correspondence Correction and (B) Using Correspondence Correction. This relationship is defined as the surface curvature feature of the point which denoted by:

Establish raw correspondence using surface curvature feature.

. (11)

CORRESPONDENCE CORRECTION USING SURFACE CURVATURE FEATURE

Refference point selection.

Establish correspondence correspodence correction surface curfature feature.

with using

Figure 3. Proposed Technique to Establish Correspondence Correction Using Surface Curvature Feature.

(a)

(b)

(c)

In this paper we propose new correspondence correction technique based on curvature correction as shown on Figure 3. The proposed correspondence correction technique is started by build surface curvature feature in all point. This feature is used to predict the geometry of the surface at a point. Based on these surface curvature feature a raw correspondence is established to find pair point matching withrespect to the similarity of the surface geometry.Within the pair point that obtained from raw correspondence we select two point as point reference to establish point constraint using two point reference. After the reference point is found correspondence correction can be establish by considering surface geometry using surface curvature feature. Raw Correspondence Using Surface Curvature Feature

(e)

(d)

Figure 4. Pose of each view of the bunny object (a) 0o, (b)45 o, (c)90 o, (d) 270 o, and (e) 315 o.

Given two point set and . If is the ith of the whole data point set P and is the jth data point of the whole data point set P. Let and


are surface curvature feature related to the point and point respectively. The point matching strategy is finding the closest point with respect of the surface curvature feature distance. Raw correspondence between two point sets P and P’ is computed based on cr(i) is follow:

which and its conjugate . The pair reference point is selected from .Where is the index of the selected reference point,   N N (r )2  (r )2 0.5  dt  (16) i  arg max count     j i

j



ij



ij



The pair point matching that obtained from this correspondence is contain closest pair point with respect to the surface curvature feature.

reference point candidate by finding the maximum number pair point matching which has the distance with the reference point candidate under dt. (17) and (18)

Reference Point Selection

Then the selected reference point and its conjugate are

   N c (i )  arg min   d ( SCF ( pi ), SCF ( pj ))  r  j{1..N '} i 1

(12)

Our correspondence correction technique employ two reference point constraint to predict correct position of the pair point matching. Two references point and its conjugate is selected from pairpoint thatobtained from raw correspondence using surface curvature feature. We select the reference point and its conjugate within three criteria to guarantee that the reference point and it’s conjugate point is represent the same point onreal surface. Our three criteria to find the reference point are: 1) The distance of the two references point is long enough above the minimum allowable distance limit

, and ={

Correspondence Correction Using Surface Curvature Feature. Our correspondence correction technique need reference points and its conjugate exactly closest to a same point in real surface. But due to self similarity, noise introduced by scanner and nonuniform sampling of point cloud we must correct the correspondentionby considering the surface geometry at the point and Equation (10) can be modified as.  N N c(i )  arg min   (r1i  r1' j ) 2 j  i 1 j 1



(13) 2) The differences between distances of the references point and the distance its is small under conjugate points maximum allowable tolerance limit . (14) 3) The surface geometry of the references point must identical with its conjugate point which is the distance between two surface curvature vector under maximal allowable tolerance limit

(15) By filtering raw pair matching point using these criteria we will have M pair candidate of reference point which

}

 (r2i  r2' j ) 2  w  k ij2

where

  k ij  d (SCF ( pi ), SCF ( p 'j ))



0.5



(19)

is the

distance between surface curvature feature of point and surface curvature feature of point , w is weight to show the surface geometry contribution to find the pair matching point.

RESULT AND DISCUSSION In this section, we evaluate the performance of proposed correspondence correction technique. We test the proposed technique to the bunny object. The bunny object isobtainedfromdatarepository of Stanford University that is consisting five different views. The amount of points of each view is



150 Original ICP ICP- Using Correspondence Correction

100

50

0

10

20

30

40

50

Iteration

(a)


50 Original ICP-AIF ICP-AIF Using Correspondence Correction 40

30

20

10

0

10

20

30

40

50

60

Iteration

(b) 50


shown in Table 1 while each view pose is shown on Figure4 We apply our correspondence correction to three registration algorithm which is Iterative Closest Point algorithm (ICP)[1],Iterative Closest Point with angular invariant feature algorithm (ICPAIF)[7] and Closest Point with Surface Curvature Feature(ICP-SCF) and comparewith original registration algorithm. As we know the real conjugate points between point clouds. Therefore, we measure RMS distance error between two ground truth point sets. All registration result is plotted as graphic RMS registration error (ground truth) as a function of iteration number.During the registration process there are many false correspondence that introduce by registration algorithm technique as shown on Figure 5(a). By implementing our correspondence correction technique, false correspondence can be fixed as shown on Figure 5(b). The comparison of registration result between original registration algorithm and registration algorithm is shown on Figure 6. We test the registration algorithm to the view-1 and view 2 of bunny objects. Figure 6.a. shows that the original ICP registration algorithm fail to toconvergent however ICP registration using correspondence correction can achieve convergence at 10 iteration with 5 mm RMS error registration with out any initial transformation. By applying correspondence correction to ICP-AIF and ICP-SCF convergence iteration is reduced from 73 and 28 into 21 and 13, the registration error is decrease from 0.61 mm and 0.33mm without correspondence correction into 0.30 mm and 0.27 with correspondence correction. The correspondence result is increase also from 143 and1510 with out correspondence correction become 3496 and 5261 using correspondence correction. Table 2 shows the registration result of all view of bunny objects. We compare the iteration convergence, RMS error registration and correspondence result between original registration algorithm and registration algorithm using correspondence correction. Our correspondence correction can reduce the iteration convergence from average 60.8 without correspondence correction into average 22.5 using correspondence correction.

Original ICP-SCF ICP-SCF Using Correspondence Correction 40

30

20

10

0

10

20

30

40

50

Iteration

(c) Figure 6. The RMS Error Registration of The View-1 and View-2 of Bunny Object Result Comparison Using Correspondence Correction and With Out Correspondention Correction to The View-1 and View-2 of Bunny Object. (a) ICP, (b) ICP-AIF,and (C) ICP-SCF.


Table 1. The Number of Point Each View of Bunny Object.

View-1 View-2 View-3 View-4 View-5

Amount of point 40256 40097 30379 31701 35336

Pose (degree) 0 45 90 270 315

The registration error is also decrease average 0.5 mm without correspondence correction into average 0.35 mm with correspondence correction. The correspondence result is increase from average 422.9 with correspondence correction into average 2661 without correspondence correction. It shows that registration using correspondence correction 63% faster , 30% more accurate and 530% more correspondence result than original registration algorithm. We have not included the ICP registration comparison result into Table 2 because the original ICP registration fail in all registration test but as shown in figure 5 ICP can achieve convergence using our correspondence correction. Figure 7 shows the result of registration all views of bunny object using correspondence correction. Each view is transformed relatively to View-1 as the result of registration process.

CONCLUSION This research proposes a correspondence correction for point cloud registration base on

surface curvature features. The surface curvature feature estimate correct position by compare the surface geometry of at a point. In experiment we compare three original registration algorithm ICP, ICP-AIF and ICPSCF with ICP, ICP-AIF and ICP-SCF using correspondence correction. The result shows that registration algorithm using correspondence correction 63% faster, 23% more accurate and 530% more correspondence result than the original registration algorithm. For further works the proposed correspondence correction technique can be used for multi rigid object segmentation and registration. Segmentation is separate an object into its part while the registration is construct an object from its components. Segmentation and registration of multi rigid objects is useful in various applications such as reverse engineering, computer vision and computer graphics.

Figure 7. The Registration Result of All Views of The Bunny Object Whicheach View is Transformed Relativelyto View-1.

Table 2. Registration Comparison Result. Iteration Convergence Registration Registration Algorithm

ICP-AIF

ICP-SCF

Average

view 1-view 2 view 2 view 3 view1 view 5 view 5-view 4 view 1-view 2 view 2 view 3 view1 view 5 view 5-view 4

RMSError Registration(mm)

Using Original Original Correspondence Algorithm Algorithm Correction 73 21 0.61 87 34 1.22 20 83 15 0.43 28 13 0.33 66 41 0.35 48 17 0.26 37 19 0.35 60.28 22.5 0.50

Using Correspondence Correction 0.30 0.46 0.61 0.38 0.27 0.29 0.27 0.29 0.35

Original Algorithm 143 46 49 1510 153 447 608 422.28

Correspondence Result Using Correspondence Correction 3486 955 2991 2448 5261 665 3490 1992 2661.00


REFERENCES [1] BeslPJ. and McKay ND. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence. 14:239–256. 1992. [2] Chen Y and Medioni G.Object modeling by registration of multiple range images. Proceedings of IEEE International Conference on Robotics and Automation. 2724–2729. 1991. [3] Bergevin R, Soucy M, Gagnon H, and Laurendeau D.Towards a general multiview registration technique. IEEE Transactions on Pattern Analysis and Machine Intelligence. 18:540–547. 1996. [4] Gérard Blais MDL. Registering Multiview Range Data to Create 3D Computer Objects. IEEE Transactions on Pattern Analysis and Machine Intelligence. 17:820–824.1993. [5] Park SY and Subbarao M. An accurate and fast point-to-plane registration technique. Pattern Recognition Letters. 24: 2967– 2976. 2003. [6] Johnson AE and Kang SB. Registration and Integration of Textured 3-D Data. 1– 25.1998 [7] Jiang J, Cheng J, and Chen X. Registration for 3-D point cloud using angular-

invariant feature. 72:3839–3844. 2009.

Neurocomputing.

[8] Torre-Ferrero C, Llata JR, Robla S, and Sarabia EG. A similarity measure for 3D rigid registration of point clouds using image-based descriptors with low overlap. Proceedings of IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops. 71–78. 2009. [9] Liu Y. Constraints for closest point finding. Pattern Recognition Letters. 2008. [10] Bernal J, Flowers-Cano R, and CarbajalDominguez A. Exact calculation of the number of degrees of freedom of a rigid body composed of n particles. Revista mexicana de física E. 55:191–195. 2009. [11] Arun KS, Huang TS, and Blostein SD. Least-Squares Fitting of Two 3-D Point Sets. IEEE Transactions on Pattern Analysis and Machine Intelligence. 9:698– 700. 1987. [12] Agam G and Tang XTX. A Sampling framework for accurate curvature estimation in discrete surfaces. IEEE Transactions on Visualization and Computer Graphics. 11:573–583. 2005.

SESINDO 2010

SESINDO 2010-Jurusan Sistem Informasi ITS

McGegas, penangkap gerakan manusia untuk industri kreatif Eko Mulyanto 1) ,Supeno Mardi S.N.2), ,Surya Sumpeno3), Muhtadin4) , Mochamad Hariadi 5) 1,2,3,4,5 Jurusan Teknik Elektro, ITS Surabaya 60111 E-mail : [email protected])

Abstract McGegas adalah perangkat lunak penangkap gerak (motion capture software) yangn ditujukan untuk membantu indutri kreatif animasi dan perfilman. Dengan software McGegas, gerakan aktor manusia menggunakan 14 buah active marker sebagai model untuk objek 3D, dapat ditangkap (captured) dari 8 kamera , dengan pada 30 frame per second. Hasil dari proses capture tersebut lalu ditransformasikan menjadi gerakan model 3D dalam bentuk Bio Vision Hierarchy yang diinginkan. Performansi McGegas dalam menangkap pola gerakan dasar manusia secara umum. diuji dengan tingkat kecepatan. Hasil yang didapatkan menunjukkan McGegas sudah bias merekonstruksi gerakan dasar manusia menjadi model animasi 3dimensi. Kata kunci : Motion Capture McGegas, active marker, Bio Vision Hierarchy, model animasi 3D

1. PENDAHULUAN Industri kreatif merupakan sektor yang diperkirakan mampu bertahan menghadapi krisis tahun 2009 sebab basisnya adalah kreativitas dari sumber daya manusia yang tak terbatas. Ketergantungan teknologi dan bahan baku produk itu dari luar negeri pun termasuk rendah. Saat ini telah muncul banyak industri kecil dan menengah yang bergerak dalam industri kreatif, beberapa di antaranya berupa rumah-rumah produksi animasi. Salah satu produk yang dibutuhkan oleh rumah produksi adalah mesin penangkap gerakan manusia (motion capture) , yang berguna untuk mempercepat proses pengerjaan animasi dan membuat gerakan yang rumit namun alamiah. Kami telah berhasil membuat McGegas, mesin penangkap gerakan manusia berbasis marker dengan menggunakan kamera web cam. McGegas terdiri dari tiga bagian besar. Yang pertama adalah motion capture software. Yang kedua adalah animation database engine, dan yang ketiga adalah render farm.

marker-marker magnetik yang ditempelkan pada tubuh artis. Perangkat ini berharga sangat mahal dan memerlukan kalibrasi yang tidak mudah. Contoh sistem yang menggunakan optis adalah sistem yang memanfaatkan sensor kamera, biasanya berupa kamera dengan kecepatan tinggi dan berharga mahal. Kontribusi penelitian kami adalah :  Membuat teknik yang bisa menggabungkan beberapa kamera webcam berbiaya rendah untuk membuat sistem motion capture.  Membuat jenis penanda dengan harga yang murah. Penanda yang kami buat berasal dari bahan styrofoam dengan ukuran yang penanda yang cocok dan mudah dikenali oleh kamera webcam. 3. SISTEM MOTION CAPTURE MCGEGAS Desain system motion capture yang telah kami kembang tersebut dapat dilihat pada gambar 1.

2. KONTRIBUSI PENELITIAN MOTION CAPTURE Hingga saat ini, metode yang umum dipakai dalam motion capture ada 2 jenis[1][2], yaitu non-optical system dan optical system. Salah satu contoh sistem non-optis adalah sistem yang memanfaatkan sensor magnetik yang menangkap koordinat bagian-bagian tubuh da[ri

Gambar 1 Sistem Motion Capture Mc Gegas

3

SESINDO 2010-Jurusan Sistem Informasi ITS Seperti yang dapat dilihat pada Gambar 1 sistem motion capture yang kami kembangkan terdiri atas 2 perangkat. Perangkat yang pertama adalah perangkat keras. Perangkat keras ini berisikan peralatan- peralatan yang digunakan dalam membantu proses penangkapan gerak. Sedangkan perangkat lain yang telah kamu kembangkan berupa perangkat lunak.. Tugas perangkat lunak disini digunakan untuk melakukan pemprosesan mula sampai dengan melakukan proses rekonstruksi bentuk 3D terhadap data video yang didapat. Perangkat keras motion captureMcGegas Perangkat keras motion capture McGegas terdiri atas :  :Ruang Penenangkap Gerak dengan dimensi 3x3x3 m yang dilengkapi dengan  8 buah kamera WebCam dengan resolusi HD 920x720 Pixel.  8 buah PC Windows dilengkapi dengan network card yang digunakan untuk menangkap gambar dari masing-masing kamera.  1 buah network switch untuk menghubungkan jaringan dari komputer.  1 buah pakaian mocap lengkap beserta marker untuk aktor.  1 set box mocap untuk peletakan kamera dan actor

rekonstruksi. Pada halaman ini dilakukan proses rekonstruksi dari data 2D menjadi data 3D berupa stik figure. Fitur-fitur yang terdapat pada perangkat lunak motion capture McGegas terdiri dari kalibrasi kamera, exkstraksi penanda, rekonstruksi 3D dan BVH maker.  Fitur Kalibrasi kamera : Fitur ini digunakan untuk mencari parameter intrinsik dan ekstrisik kamera. Kedua parameter tersebut berguna didalam melakukan rekonstruksi dari data 2D menjadi data 3D.  Fitur Ekstrasi : Fitur ini digunakan untuk memisahkan dan menemukan posisi penanda pada tiap-tiap frame pada data video yang diperoleh dari 8 buah kamera yang dipasang pada ruang motion capture  Fitur rekonstruksi 3D : Fiur ini digunakan untuk melakukan rekonstruks dari data 2d yang diperloleh pada ekstraksi penanda menjadi data 3D.  Fitur konversi ke BVH : Fitur ini digunakan untuk konversi dari data 3D menjadi data motion capture Biovision Hierarchy.

Desain ruang motion capture McGegas ditunjukan pada gambar 2. digunakan untuk menangkap gamar aktor yang telah mengenakan baju yang dilengkapi dengan aktif marker

Gambar 3. Halaman utama dan fitur-fitur pada perangkat lunak McGegas

Gambar 2 Dimensi Ruang Motion Capture

Perangkat Lunak Motion Capture McGegas Tampilan halaman pertama pada perangkat lunak McGegas ditunjukan pada gambar 3. Gambar 3 menunjukan fitur-fitur yang ada pada perangkat lunak motion capture McGegas. Sedangkan Gambar 4. ditunjukan halaman

Gambar 4. Halaman Rekonstruksi 3D.

4

SESINDO 2010-Jurusan Sistem Informasi ITS y

4. Langkah-Langkah Untuk didalam tersebut langkah berikut.

x

menangkap gerak actor dilakukan beberapa langkah. Langkah-langkah ditunjukan pada Tabel 1. Langkahtersebut dapat dijelaskan sebagai

Z z

( xi , y i , f )

Y

( xS , y S , z S ) M

Tabel 1. Langkah Motion Capture McGegas No. Langkah Penjelasan 1 Kalibrasi Kamera Menentukan parameter intrinsik dan parameter extrinsik pada kamera 2 Persiapan model Pemasangan marker pada model / aktor 3 Pengambilan Menangkap gambar video semua pergerakan dari model / aktor 4 Extraksi marker Mencari dan menemukan penanda pad tiap-tiap frame. 5 Rekontruksi 3D Melakukan rekontruksi marker dalam 3 dimensi, output data berupa koordinat 3 Dimensi dari marker 6 Konversi BVH Mengubah data koordinat 3 Dimensi kedalam format file Bio Vision Hierarchy (BVH).

Langkah 1. Kalibrasi Kamera Kalibrasi kamera digunakan untuk mencari parameter intrinsic dan parameter extrinsik.

( X S , YS , Z S )

O X

Gambar 5. Posisi dan Orentasi Kamera terahadap sistem koordinat dunia

Paramater kamera ekstrinsik tersebut dinyatakan dalam bentuk persamaan seperti yang terlihat pada persamaan 2..  xS  y   S  R  z S  0T3   1

XS  T   YS  1   Z S     1  …………………………..(2)

Dimana xs,ys dan zs adalah posisi pada koordinat kamera dan Xs,Ys dan Zs adalah posisi titik pada koordinat dunia R adalah factor rotasi dan T adalah faktor translasi. . Didalam mencari kedua macam parameter tersebut kami menggunakan metoda yang telah dikembangkan oleh Tsai. Tsai menggunakan cheker borad sperti yang di perlihatkan oleh Gambar 6..

Parameter intrisnsik adalah adalah parameter internal kamera yang berupa focal length, skala factor sumbu x dan sumbu y kamera, factor skew dan dsistorsi. Didalam penelitian ini model kamera yang digunakan adalah kamera lubang jarum. Dengan model ini maka matrix persamaan internal kamera yang digunakan di tunjukan pada persamaan (1). Dimana u,v,w adalah koordinat citra dalam koordinat homogen dan xs,ys dan zs adalah koordinat kamera. u   f v  0     w  0

0 f 0

x  0 0  S  y 0 0  S   zS  1 0   1

Gambar 6. Kalibrasi kamera dengan menggunakan cheker board..

Langkah 2. Persiapan Model. ................................. (1_

Selain parameter intrinsik kalibrasi juga dugunakan untuk menemukan parameter extrinsic. Parameter extrinsik adalah parameter yang berisi tentang posisi dan orientasi kamera terhadap system koordinat dunia. Seperti yang ditunjukan oleh Gambar 5.

Model disiapkan dengan menggunakan pakaian yang telah dilengkapi dengan marker. Terdapat 14 buah marker yang diletakan pada posisi titik persendian seperti yag ditunjukan pada Gambar 7.a. Tiap persendian tersebut diberi label dengan nama huruf dari A sampai dengan N sesuai dengan stik figure yang ditunjukan pada Gambar 7.b. Adapun daftar nama dan posisi dan

5

SESINDO 2010-Jurusan Sistem Informasi ITS nama marker uamg digunakan dalam penelitian ini ditunjukan pada Tabel 2

suatu penanda dapat dilihat setidaknya oleh oleh 2 buah kamera.

Tabel 2. Posisi dan Nama Marker Pada Aktor No 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Posisi Kepala Dada Bau Kiri Siku Kiri Pergelangan Tangan Kiri Bahu Kanan Siku Kanan Pergelangan tangan Kanan Pinggull Kiri Lutut Kiri Kaki Kiri Pinggul Kanan Lutu Kanan Kaki Kanan

Nama Label A B C D E F G H I J K L M N

Gambar 8. Aktor dengan Penanda Aktif Pada Sedang melakukan adegan didalam ruang Motion Capture Langkah 4. Ekstraksi Marker Extraksi marker dilakukan dengan melakukan proses threshold pada tiap-tiap frame.

Gambar 9. Hasil ekstrasi marker yang telah diberi nomor.

(a)

(b)

Gambar 7a. Gambar aktor menggunakan pakaian dengan penanda dan (b) Posisi Penanda pada persendian

Hasil extraksi tersebut berupa posisi marker pada tiap-tiap frame. Pada gambar 9 diperlihakan marker yang telah dikstraksi dan di beri nomor. Langkah 5.Rekonstruksi 3D

Langkah 3. Pengambilan DataVideo Untuk melakukan pengambilan data video seorang aktor yang telah mengenakan pakaian yang telah dilengkapi dengan penanda melakukan adegan didalam ruang motion capture seperti yang diperlihatkan oleh Gambar 8. Adegan tersebut direkam oleh 8 buah kamera dari 8 sudut pandang yang berbeda. Didalam pengambilan gambar video tersebut setiap penanda paling sedikit harus dapat direkam sedikitknya oleh 2 buah kamera karena proses rekonstruksi hanya dapat dilakukan bila

Rekonstruksi 3D dilakukan dengan menarik garis dari pusat proyeksi kamera ke posisi marker yang telah ditemukan. Titik potong antara garis yang didapat dari pusat proyeksi ke titik penanda pada antar tiap-tiap kamera tersebut merupakan hasil rekonstruksi 3D dari atas marker yang bersangkutan. Pada Gambar 10 terdapat dua buah kamera K1 dan K2. Bila C1 dan C2 adalah proyeksi penanda C pada kamera K1 dan K2 maka posisi C dapat di cari dengan mencari titik potong garis yang ditarik dari pusat proyeksi kamera K1 ke C1 dengan garis yang ditarik dari pusat proyeksi kamera K2 ke C2[3].

6

SESINDO 2010-Jurusan Sistem Informasi ITS

HIERARCHY ROOT Hips { OFFSET 0.00 0.00 0.00 CHANNELS 6 Xposition Yposition Zposition Zrotation Xrotation Yrotation JOINT LeftUpLeg ……… } MOTION …….

Gambar 10. Proses rekonstruksi 3D dengan menggunakan triangulasi.,

Bila proses tersebut dilakukan terhadap seluruh marker maka hasil yang didapat berupa stik figur. Pada Gambar 11 diperlihatkan rekonstruksi hasil rekonstruksi dari seluruh penanda menghasilkan bentuk stik figure[5].

Gambar 11. Stik figure hasil rekonstruksi terhadap seluruh marker.

Langkah 6. Bio Vision Hierarchy (BVH) Bio Vision Hierarchy adalah file standar yang digunakan pada motion capture. File tersebut digunakan pada banyak perangkat lunak untuk animasi seperti Blender, 3DSMac dan Maya. Oleh karena itu dalam penelitian ini kami mengembangkan perangkat lunak yang melakukan konversi dari data 3D menjadi data BVH. Bio Vision Hierarchy terdiri dari dua unsur utama, yaitu hirarki dan motion (gerakan). Sebuah file BVH dirancang untuk menyimpan gerakan yang dihasilkan oleh motion capture. Ini adalah cara ringkas untuk menyimpan gerak, hal itu tidak tergantung pada rincian geometri. Namun data ini khusus untuk file hirarki dan dimensi tubuh karakter, sehingga meskipun dapat mentransfer gerakan dari satu karakter ke yang lain, tetap harus diskala untuk masingmasing model karakter. Gambar 11 adalah adalah contoh BVH seorang yang berjalan.

Gambar 11 Struktur File BVH; .

Pada karakter manusia berjalan, Root yang digunakan adalah Hips atau pinggang. Untuk default awal gerakan maka semua gerakan berawal dari pinggang. Root pinggang (hips) memiliki tiga baris informasi, yaitu OFFSET, CHANNELS, dan JOINT. Untuk awal gerakan diberi default offset bernilai 0.00. CHANNELS memiliki 6 bagian informasi yaitu gerakan posisi (XYZ) dan rotasi (XYZ). Selanjutnya root harus memiliki informasi yaitu struktur gerakan dari pinggang terhubung dengan struktur kaki kiri atas dengan menggunakan perintah JOINT. Informasi yang ada pada struktur JOINT juga memiliki 3 baris informasi, hanya saja pada CHANNELS memiliki 3 bagian informasi yaitu rotasi (XYZ), hal ini berlaku untuk struktur JOINT dibawahnya

5. PENGUJIAN DAN PEMBAHASAN Pengujian ini dilakukan dengan melakukan gerakan dasar meliputi: Jalan Berputar, Jalan Ditempat, Gerakan Menendang, dan Gerakan Lompat Pemilihan gerakan ini diasarkan atas tingkat kesulitan masing gerakan. Pengujian terhadap Gerak Jalan Berputar Tabel 3 adalah hasil yang didapat dari rekonstruksi terhadap gerakan jalan berputar. Jalan berputar tersebut terdiri dari dari enam buah sub gerakan dimana tiap tiap sub gerakan rata-rata masing-masing berdurasi 20 frame. Dari ke enam sub gerakan tersebut semua berhasil di rekonstruksi. Tabel 3 Hasil Pengujian Jalan Berputar No

Sub Gerak

1

Siku kanan mengikuti tangan kanan ke belakang Siku kiri mengikuti tangan kiri kedepan Lutut kanan mengikuti kaki kanan kedepan

2 3

Rekonstruksi Berhasil

Jumlah Frame 21

Berhasil

21

Berhasil

20

7

SESINDO 2010-Jurusan Sistem Informasi ITS 4 5 6

Pinggul kiri kedepan Lutut kiri condong kebelakang Pundak kanan dan dada berotasi terhadap pundak kiri

Berhasil Berhasil

21 20

Berhasil

90

7. SIMPULAN

Pengujian Terhadap Gerak Jalan Ditempat Pengujian selanjutnya terhadap gerak jalan di tempat. Gerak Jalan ditempat terseut terdiri dari 8 sub gerakan dimana durasi tiap-tiap gerakan masing-masing terdiri dari sejumlah 17 frame seperti yang diperlihatkan pada tabel 4. Hasil dari rekonstriksi untuk masing-masing gerakan tersebut berhasil dilakukan untuk tiap-tiap sub gerakan.

Sub Gerak

1 2 3 4 5 6 7 8

Lutut kanan keatas Lutu kanan kebawah Kaki kanan keatas Kaki kanan kebawah Lutut kiri keatas Lutut kiri kebawah Kaki kiri keatas Kaki kiri kebawah

Rekonst ruksi Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil

Jumlah Frame 17 17 17 17 17 17 17 17

Pengujian Gerak Gerakan Menendang Pengujian selanjutnya terhadap gerak menendang gerak menendang terdiri dari 4 sub gerak sub gerak no 1 dan no 2 pada tabel 5 berdurasi 18 frame berhasil direkonstruksi sedangkan sub gerak no 3 dan no 4 berdurasi 10 dan 11 frame dengan hasil gagal di rekonstruksi. Tabel 5 Hasil Pengujian Gerakan Menendang No

Sub Gerak

1

Siku kiri mengikuti tangan kiri menekuk kedepan Siku kanan mengikuti tangan kanan menekuk kedepan Kaki kanan menendang kedepan Kaki kanan ditarik ketempat semula

2 3 4

1.

2.

Software motion capture McGegas terbukti sudah mendukung sebuah sistem low cost motion capture, yang bias merekonstruksi gerakan dasar manusia Secara keseluruhan, motion capture lebih cepat dari pekerjaan manual, karena untuk menggerakkan objek perlu ratusan titik yang harus digerakkan dengan pertimbangan naturalisasi gerakan yang dihasilkan.

6. DAFTAR PUSTAKA

Tabel 4 Hasil Pengujian Jalan ditempat N o

Peningkatan Kapasitas Iptek Sistem Produksi tahun anggaran 2010 nomer KP-2010-3462.

Rekonst ruksi Berhasil

Jumlah Frame 18

Berhasil

18

Gagal

10

Gagal

11

[1] Gutemberg B. Guerra-Filho, Optical Motion Capture: Theory and Implementation, RITA,Volume XII Número 2,2005 [2]R. Budiman,M. Bennamoun, D.Q. Huynh, Low Cost Motion Capture, Proc. Image and Vision Computing New Zealand, Dunedin, New Zealand, 28-29 November 2005 [3] Rifadil, M, Mulyanto E, Hariadi M,, Motion Capture Human Body Using Camera Webcam, Sesindo 2008 [4] Prastyono Eka, M, Mulyanto E, Hariadi M,Penangkapan Gerak Manusia 3D berdasar pada Penanda Aktif dengan Kamera Murah, Seninar Nasional Electical and It’s Education (SNEIE) 2009, Malang [5] Richard Hartley, Andrew Zisserman Multiple View Geometry In Computer Vision, CAMBRIDGE UNIVERSITY PRESS 2003 , Cambridge

6. PENGAKUAN Penelitian ini mendapat dukungan dana dari Kementrian Riset dan Teknologi (KRT) Indonesia, berupa kontrak riset Program Insentif

8

JATIT Keterangan : Telah dipublikasikan pada :

Recommend Documents