where S11S1251 S21S22S23 The eigenvector corresponding to the maximum positive eigenvalue is a quaternion which minimizes the equation(21.6). An orthonormal rotation matrix R can be recovered from a quaternion q=[90, 91, 92, 93 by G+q2-9-932(qg-993)2(q1g3+9g2) R 2(qy2+g3)+q2-qi-932(q93-9q) 2(q93-992)2(g2q3+q)9+g2-q2-9 The procedure described above can also be applied to the case where more than three corre- sponding point pairs are provided 21.6 Matching problems IG WOS, IPWOS, IGWS or IPWS 21.6.1 Iterative Closest Point (ICP) algorithm [1 for IG WOS or IPWOS algorithm The point set P with Np points iFil from the data shape and the model shape X (with Nr supporting geometric primitives: points, lines, or triangles) are given The iteration is initialized by setting Po= P, go=[1,0, 0,0,0,0, 0 and k=0. The reg istration vectors are defined relative to the initial data set Po so that the final registration represents the complete transformation. Steps 1, 2, 3, and 4 are applied until convergence within a tolerance t a. Compute the closest points: Yk= C(Pk, X) b. Compute the registration:(k, dk)=Q(Po,Yk) C. Apply the registration: Pk+1=gi (Po) d. Terminate the iteration when the change in mean-square error falls below a preset threshold T>0 specifying the desired precision of the registration: Idk -dk+1 <T 21.6.2 ICP algorithm for scaling effects When initial information on transformation is provided, the ICP method can be extended to resolve scaling effects in the matching problem. A scaling factor o is included in the objective function(21.4). The scaling transformation is performed at step c in the iCP algorithm. In this case we have to provide seven initial values(three for translation, three for rotation and ling
where M = X 3 i=1 nimT i = s11 s12 s13 s21 s22 s23 s31 s32 s33 . (21.8) The eigenvector corresponding to the maximum positive eigenvalue is a quaternion which minimizes the equation (21.6). An orthonormal rotation matrix R can be recovered from a quaternion qˇ = [q0, q1, q2, q3] by R = q 2 0 + q 2 1 − q 2 2 − q 2 3 2(q1q2 − q0q3) 2(q1q3 + q0q2) 2(q1q2 + q0q3) q 2 0 + q 2 2 − q 2 1 − q 2 3 2(q2q3 − q0q1) 2(q1q3 − q0q2) 2(q2q3 + q0q1) q 2 0 + q 2 3 − q 2 1 − q 2 2 . (21.9) The procedure described above can also be applied to the case where more than three corresponding point pairs are provided. 21.6 Matching problems : IGWOS, IPWOS, IGWS or IPWS 21.6.1 Iterative Closest Point (ICP) algorithm [1] for IGWOS or IPWOS Algorithm • The point set P with Np points {p~i} from the data shape and the model shape X (with Nx supporting geometric primitives: points, lines, or triangles) are given. • The iteration is initialized by setting P0 = P, q~0 = [1, 0, 0, 0, 0, 0, 0]T and k = 0. The registration vectors are defined relative to the initial data set P0 so that the final registration represents the complete transformation. Steps 1,2,3, and 4 are applied until convergence within a tolerance τ . a. Compute the closest points: Yk = C(Pk, X). b. Compute the registration: (~qk, dk) = Q(P0, Yk). c. Apply the registration: Pk+1 = ~qk(P0). d. Terminate the iteration when the change in mean-square error falls below a preset threshold τ > 0 specifying the desired precision of the registration: |dk − dk+1| < τ . 21.6.2 ICP algorithm for scaling effects When initial information on transformation is provided, the ICP method can be extended to resolve scaling effects in the matching problem. A scaling factor σ is included in the objective function (21.4). The scaling transformation is performed at step c in the ICP algorithm. In this case we have to provide seven initial values (three for translation, three for rotation and one for scaling). 6
21.7 Matching problems: NG WOs or NPWOs 21.7.1 Search method 2 Chua and Jarvis 2 developed a method to align two objects through registration assuming no prior knowledge of correspondence between two range data sets. They use a bi-quadratic polynomial to fit data points in the local area in the least squares sense and calculate the principal curvatures and Darboux frames. Then they construct a list of sensed data points based on the fit error. Three seed points are selected to form the list such that the area of the triangle represented by the seed points becomes maximized to reduce any mismatch error. Three constraints(curvature, distance and direction) are imposed to sort out possible corresponding points out of the model data set. Then a list of transformations can be obtained from the candidate points and an optimum transformation is selected. Various searching algorithms are described and demonstrated in[2 21.7.2 Kh method The overall diagram of the KH method [8 is shown in Figure 21.1. The input of the process includes two objects and three pairs of the gaussian and the mean curvatures at three different non-collinear locations. The algorithm yields the minimum value of in the equation(21. 4) and the corresponding rotation matrix R and the translation vector t. Since no scaling effect is involved. we assume that a scaling factor g=1 Step 10 Step 10 is to select three non-collinear points m1, m2 and mg on ri away from the boundary of rI where each point has different, Gaussian K and mean curvature H values. At mi, we have Ki and Hi, where i= 1, 2, 3. Next, subdivide r2 into rational Bezier surface patches B, G=l,.,n)by inserting appropriate knots [ 5, 11]. Then for each rational Bezier surface patch B,, we express K, and H, in the bivariate rational Bernstein polynomial basis using rounded interval arithmetic to formulate the problem. This allows us to use the Interval Projected Polyhedron(IPP) algorithm [10, 13 for solving nonlinear polynomial systems. For ach pair Ki and Hi, we solve the following system of equations by the IPp technique. K(u,v)=K±6 H1(u,v)=H2±6H,(j=1,……, n and i=1,2,3) (21.10) where dk and H represent the uncertainty of estimated curvatures from data points. For each pair of Ki and Hi, a list of roots Li=(uik, Uik),(k=l, .. di) is obtained Step 12(selection process) A simple pruning search based on the Euclidean distance can be applied to the selection process. We have three lists of candidate points, Li=(uik, Vik),(k= 1, . di)from which one 3-tuple(n1, n2, n3) 2(v2k,t2k), (21.11)
21.7 Matching problems : NGWOS or NPWOS 21.7.1 Search method [2] Chua and Jarvis [2] developed a method to align two objects through registration assuming no prior knowledge of correspondence between two range data sets. They use a bi-quadratic polynomial to fit data points in the local area in the least squares sense and calculate the principal curvatures and Darboux frames. Then they construct a list of sensed data points based on the fit error. Three seed points are selected to form the list such that the area of the triangle represented by the seed points becomes maximized to reduce any mismatch error. Three constraints (curvature, distance and direction) are imposed to sort out possible corresponding points out of the model data set. Then a list of transformations can be obtained from the candidate points and an optimum transformation is selected. Various searching algorithms are described and demonstrated in [2]. 21.7.2 KH method The overall diagram of the KH method [8] is shown in Figure 21.1. The input of the process includes two objects and three pairs of the Gaussian and the mean curvatures at three different non-collinear locations. The algorithm yields the minimum value of Φ in the equation (21.4), and the corresponding rotation matrix R and the translation vector t. Since no scaling effect is involved, we assume that a scaling factor σ = 1. Step 10 Step 10 is to select three non-collinear points m1, m2 and m3 on r1 away from the boundary of r1 where each point has different, Gaussian K and mean curvature H values. At mi , we have Ki and Hi , where i = 1, 2, 3. Next, subdivide r2 into rational B´ezier surface patches Bj (j = 1, · · · , n) by inserting appropriate knots [5, 11]. Then for each rational B´ezier surface patch Bj , we express Kj and Hj in the bivariate rational Bernstein polynomial basis using rounded interval arithmetic to formulate the problem. This allows us to use the Interval Projected Polyhedron (IPP) algorithm [10, 13] for solving nonlinear polynomial systems. For each pair Ki and Hi , we solve the following system of equations by the IPP technique. Kj(u, v) = Ki ± δK, Hj(u, v) = Hi ± δH, (j = 1, · · · , n and i = 1, 2, 3), (21.10) where δK and δH represent the uncertainty of estimated curvatures from data points. For each pair of Ki and Hi , a list of roots Li = (uik, vik), (k = 1, · · · , di) is obtained. Step 12 (selection process) A simple pruning search based on the Euclidean distance can be applied to the selection process. We have three lists of candidate points, Li = (uik, vik), (k = 1, · · · , di) from which one 3-tuple (n1, n2, n3) n1 = r2(u1k, v1k), n2 = r2(u2k, v2k), n3 = r2(u3k, v3k), (21.11) 7