R d X = {x i, i = 1,, n} Y = {y j, j = 1,, }.. n P = [p i,j p i,j X x i Y y j. C P. p i,j = 1, i = 1,, n j=1 C P = p i,j : n (1) p i,j 1,

Size: px

Start display at page:

Download "R d X = {x i, i = 1,, n} Y = {y j, j = 1,, }.. n P = [p i,j p i,j X x i Y y j. C P. p i,j = 1, i = 1,, n j=1 C P = p i,j : n (1) p i,j 1,"

暗陌崔
5 years ago
Views:

1 33 3 Vol. 33, No ACTA AUTOMATICA SINICA March, TP391 A CQPOCS Algorith for Fast Feature Point Matching LIAN Wei 1 LIANG Yan 1 PAN Quan 1 CHENG Yong-Mei 1 ZHANG Hong-Cai 1 Abstract A clustering and quadratic prograing based projection onto convex sets (CQPOCS) algorith for fast feature point atching is presented in this paper. Via feature point clustering, the proble of atching odel point set and taget point set is converted in to the proble of atching corresponding clusters, thus reducing the coputational cost. Then, quatratic prograing based POCS algorith is used to solve the cluster atching proble without incurring the successive POCS algorith s accuulating deviation due to successive projections onto row convex sets and colun convex sets. Siulation results show that our CQPOCS algorith has satisfactory atching accuracy and coputational safety. Key words clustering, point atching, POCS Besl McKay (Iterated closest point ICP) [1... Chui Rangarajan (Robust Point Matching RPM) [ Received June 17, 25; in revised for June 7, 26 (64411, ) Supported by National Natural Science Foundation of P. R. China (64411, ) School of Autoation, Northwestern Polytechnical University, Xi an 7172 DOI: 136/aas Barend Michael (Projection onto convex sets POCS) [6.. (Successive POCS SPOCS). SPOCS. Belongie (Shape context SC) [7.... Barend Michael [6 (Clustering and quadratic prograing based POCS CQPOCS). 1) Barend. 2) Barend SPOCS

2 R d X = {x i, i = 1,, n} Y = {y j, j = 1,, }.. n P = [p i,j p i,j X x i Y y j. C P. p i,j = 1, i = 1,, n j=1 C P = p i,j : n (1) p i,j 1, j = 1,, i=1 p i,j, i, j [3 Ω P C P E(Ω, P ) = i,j p i,j y j Ω(x i ) 2 + Φ(Ω) (2). 2 Φ(Ω) Ω. Ω P. Ω E Ω E = Ω Ω E P Ẽ(P ) = E(Ω, P ) (3) [6 Ẽ(P ) REPEAT [ P w+1 = P w η P w+1 = T P ( P w+1 ) w w + 1 UNTIL P w e E(P w ) e E(P w ) // // Ẽ(P w ) (3) T P (P w ) P w C P η. 3 T P (P w ). [6 SPOCS C P C r P = P : C c P = P : p i,j = 1, j=1 p i,j, n p i,j 1, i=1 p i,j, i i, j j i, j P w. T P (P w ) P w CP r Cc P.. T P (P w ) P C P P P w T P (P w )... X {Γ x k, k = 1,, } Γ x k k. Y {Γ y l, l = 1,, q }. q Q = [q k,l q k,l X Γ x k Y Γ y l. C Q. C Q = q k,l : q Γ y l q k,l = 1, k = 1,, Γ x k q k,l 1, l = 1,, q q k,l, k, l (4). C Q. C P C Q.

3 P C P q k,l Q C Q i Γ x k,j Γy l Γ x k Γy l p i,j C Q [ p i,j q k,l i Γ x C k,j Γ y P l n P w C P n P w C Q T Q (P w ) arg in (q k,l p w Q C Q i,j) 2 k,l T Q (P w ) arg in Q C Q k,l i Γ x k,j Γy l Γ x k Γ y l (q k,l p w k.l) 2 (5) P p w i Γ k.l x k,j Γy p w i,j l Γ x k Γy l. T P (P w ) T Q (P w ). T Q (P w ) T P (P w ) 1 T Q (P w ). p i,j q k,l i Γ x k,j Γ y l Q X Y. 3.1 (5) q J(Q) = Γ x k Γ y l ( q k,l pk,l) w 2 (6) (4) Q. 2. Q = { q k,l } S 1 = {(k, l) : q k,l > } S 1 = {(k, l) : q k,l = } S 2 = {l : Γx k q k,l < 1} S 2 = {l : nq Γx k q k,l = 1} Q q k,l = λ k µ l λ k Γ y l µ l Γ x k + 2 Γ x k Γ y l pw k,l 2 Γ x k Γy l, (k, l) S 1, (k, l) S 1 (7) µ l =, l S 2 (8) n q δ k,l λk ( nq ) δ k,l Γ x k Γ y l µ l + 2 δ k,l Γ x k p w k,l = 2, l S 2 (9) ( q ) δ k,l Γ y l Γ x k λ k δ k,l µ l l S2 q +2 δ k,l Γ y l pw k,l = 2, k = 1,, (1) δ k,l = 1, (k, l) S 1 (11) δ k,l =, (k, l) S 1 (12). (6) (4) Lagrange J(Q) q J(q k,l, λ k, µ l, γ k,l ) = Γ x k Γ y l (q k,l p w k,l) 2 + q λ k ( Γ y l q k,l 1)+ q µ l ( Γ x k q k,l 1) q γ k,l q k,l (13) λ k µ l γ k,l Lagrange. Q Karush-Kuhn-Tucker J q k,l = (14) µ l (15) γ k,l (16) n q µ l ( Γ x k q k,l 1) = (17) γ k,l q k,l = (18) (17) (18). (14) q k,l = λ k Γ y l µ l Γ x k + γ k,l + 2 Γ x k Γ y l pw k,l 2 Γ x k Γy l, k = 1,, ; l = 1,, q (19) (18) (7).

4 3 243 δ k,l = { 1, (k, l) S1, (k, l) S 1 C Q δ k,l Γ x k q k,l = 1, l S 2 q δ k,l Γ y l q k,l = 1, k = 1,, (19) ( nq ) δ k,l Γ x n q δ k,l λk k δ k,l Γ y l µ l + Γ y γ k,l l ( q ) δ k,l Γ y l Γ x k n q +2 δ k,l Γ x k p w k,l = 2, l S 2 q q λ k δ k,l µ l + (2) δ k,l Γ x k γ k,l q +2 δ k,l Γ y l pw k,l = 2, k = 1,, (21) δ k,l γ k,l = (2) (21) l S 2 µ l = (21) 2 l S 2 δ k,l µ l. (9) (1). (17) (8). (9) (1). (9) (1) [ R T L t λ µ = 2 (22) K R s 1 λ [ λk µ [ µ l,, l S 2 R [δ k,l [,,;l S 2 nq δ k,l Γ x L diag k Γ y l [ l S 2 q δ k,l Γ y l K diag Γ x k [,, nq t 2 δ k,l Γ x k p w k,l s 2 δ k,l Γ y l pw k,l [ q l S 2,, diag. S 1 S 2 S 1 S 2 (22) / [ QR (22). R T L B = B QR K R [ [ R 11 R [ 12 BΠ = Q 1 Q 2 = Q 1 R 11 R 12 Π [Q 1 Q 2 R 11. (17) λ µ { [ } t [ λ = Π R 1 11 Q T 1 2 s (23) µ S 1 S 2 (23) (7) T Q (P w ). [7 S 1 S 2 T Q (P w ) S 1 S 2 Q S 1 S 2 Q S 1 S 2.. S 1, S 2 REPEAT (23) Lagrange λ µ (7) q k,l ; S 1, S 2 S 1 S 1 {(k, l) : q k,l }; S 2 S 2 {l : Γx k q k,l 1} UNTIL q k,l, (k, l) Γx k q k,l 1, l 3.2 n = = q [7 O(n 3 ) O(n 3 q). SPOCS [6 O(n 4 ). 4 CQPOCS SPOCS RPM SC CQPOCS.

244 33 RPM. CQPOCS SPOCS RPM Ω Φ(Ω) Φ(Ω) [3. CQPOCS SPOCS [6. RPM [3. 4.1 CQPOCS SPOCS RPM SC Chui-Rangarajan [5,8,9 4. 3 1) ( ).. 2) (.1.5 ).. 3) (.5 2.5 ).. ( ). 1. 1 ( ).

CQPOCS (a) (b) (c) CQPOCS (d) SPOCS (e) RPM (f) SC Fig. 4 4 Matching of feature points extracted fro iages. CQPOCS Γ x k q k,l Γ y l Γ y arg ax q k,l Γ x k. l. 4 3 ( 246 ).

5 RPM. CQPOCS SPOCS RPM Ω Φ(Ω) Φ(Ω) [3. CQPOCS SPOCS [6. RPM [ CQPOCS SPOCS RPM SC Chui-Rangarajan [5,8, ) ( ).. 2) (.1.5 ).. 3) ( ).. ( ) ( )... CQPOCS [1 1/1. Matlab Pentiu GHz 256MB PC. 4 2 ( ) CQPOCS SC SPOCS RPM SC. SC. 3. CQPOCS RPM SPOCS. CQPOCS SPOCS 4.46 RPM SC CQPOCS. CQPOCS. 4.2 [9 4. CQPOCS (a) (b) (c) CQPOCS (d) SPOCS (e) RPM (f) SC Fig. 4 4 Matching of feature points extracted fro iages. CQPOCS Γ x k q k,l Γ y l Γ y arg ax q k,l Γ x k. l. 4 3 ( 246 ). CQPOCS SPOCS. RPM. SC CQPOCS. 4.3 CQPOCS 4.1 CQPOCS 5 ( 246 )... R 1.5. R = R = R = R =

6 Fig. 1 Chui-Rangarajan ( 1 ) ( 2 4 ) Chui-Rangarajan synthesized data sets: teplate point sets (colun 1) and exaples of target point sets for deforation, noise, and outlier tests (coluns 2-4) 2.4 Degree of Deforation Noise Level Outlier to Data Ratio Degree of Deforation Noise Level Outlier to Data Ratio 2 CQPOCS( ) SPOCS( ) RPM( ) SC( ) Chui-Rangarajan ( ) Fig. 2 Results of the CQPOCS( ), SPOCS( ), RPM( ) and SC( ) algoriths on the Chui-Rangarajan synthesized data sets. The error bars indicate the standard deviation of the error. Top row: the shape of fish. Botto row: the shape of a Chinese character

7 CQPOCS ( 1 ), SPOCS ( 2 ), RPM ( 3 ) SC ( 4 ) Fig. 3 Point atching results of the CQPOCS (colun 1), SPOCS (colun 2), RPM (colun 3), and SC (colun 4) algoriths on curves Degree of Deforation Noise Level Outlier to Data Ratio 5 CQPOCS (R = ( ) R = 5( ) R =.2( ) R =.25( ) ) ( ). Fig. 5 Results of the CQPOCS algorith with respect to different clustering radiuses (R = ( ), R = 5( ), R =.2( ) and R =.25( ) ties of the width of points sets) on the Chui-Rangarajan synthesized data sets of a Chinese character. The error bars indicate the standard deviation of the error Degree of Deforation Noise Level Outlier to Data Ratio 6 CQPOCS ( ( ) C ( ) K ( )) ( ). Fig. 6 Results of the CQPOCS algorith with respect to different clustering algoriths (farest point clustering ( ), C ean clustering ( ) and K ean clustering ( )) on the Chui-Rangarajan synthesized data sets of a Chinese character. The error bars indicate the standard deviation of the error

3 247 4.1 CQPOCS. 1/4. 6.. C CQPOCS CQPOCS. 5 paper.)... E-ail: lianwei3@gail.co (LIAN Wei Ph. D. candidate. His research interest covers iage, video registation and osaic and coputer vision.

IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(4): 239 256 2 Chui H, Rabo J, Duncan J, Schultz R, Rangarajan A.

Proceedings of Inforation Processing in Medical Iaging, Berlin: Springer, 1999, 168 181 3 Gold S, Rangarajan A, Lu C P, Pappu S, Mjolsness E.

The softassign procrustes atching algorith. In: Proceedings of Inforation Processing in Medical Iaging. Berlin: Springer, 1997. 29 42 5 Chui H, Rangarajan A.

IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, 26(11): 1526 153 7 Medasani S, Krishnapura R, YoungSik C. Graph atching by relaxation of fuzzy assignents.

8 CQPOCS. 1/ C CQPOCS CQPOCS. 5 paper.)... E-ail: lianwei3@gail.co (LIAN Wei Ph. D. candidate. His research interest covers iage, video registation and osaic and coputer vision. Corresponding author of this.... References 1 Besl P J, McKay N D. A ethod for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(4): Chui H, Rabo J, Duncan J, Schultz R, Rangarajan A. Registration of cortical anatoical structures via robust 3D point atching. Proceedings of Inforation Processing in Medical Iaging, Berlin: Springer, 1999, Gold S, Rangarajan A, Lu C P, Pappu S, Mjolsness E. New algoriths for 2-D and 3-D point atching: pose estiation and correspondence. Pattern Recognition, 1998, 31(8): Rangarajan A, Chui H, Bookstein F. The softassign procrustes atching algorith. In: Proceedings of Inforation Processing in Medical Iaging. Berlin: Springer, Chui H, Rangarajan A. A new point atching algorith for non-rigid registration. Coputer Vision and Iage Understanding, 23, 89: Barend J V W, Michael A V W. A POCS-based graph atching algorith. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, 26(11): Medasani S, Krishnapura R, YoungSik C. Graph atching by relaxation of fuzzy assignents. IEEE Transactions on Fuzzy Systes, 21, 9(1): Belongie S, Malik J, Puzicha J. Shape atching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22, 24(4): Zheng Y F, Doerann D. Robust point atching for nonrigid shapes by preserving local neighborhood structures. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26, 28(4): Gonzalez T. Clustering to iniize the axiu intercluster distance. Theoretical Coputer Science, 1985, 38: (LIANG Yan Assistant Professor. His research interest covers coplex dynaic syste odeling, estiation, control and siulation, inforation fusion, sensoring and control and iage understanding. ).. (PAN Quan Professor. His research interest covers control theory and application, ulti-target tracking and recognition, inforation fusion, iage process and intelligent inforation processing.). /. (CHENG Yong-Mei Assistant Professor. Her research interest covers inforation fusion, active/passive target tracking, signal and inforation processing, and cognition coputation.).. (ZHANG Hong-Cai Professor. His research interest covers control theory and application, ulti-target tracking and recognition, inforation fusion, dynaic syste odeling, estiation and control and intelligent inforation processing.)

,,.,, : 1),,,,, 2),,,,, 3),,,,,,,,,, [6].,,, ( ),, [9], : 1), 2),,,,, 3),,, 2.,, [10].,,,,,,,,, [11]. 2.1,, [12],, ;, ; Fig. 1 1 Granular hier

,,.,, : 1),,,,, 2),,,,, 3),,,,,,,,,, [6].,,, ( ),, [9], : 1), 2),,,,, 3),,, 2.,, [10].,,,,,,,,, [11]. 2.1,, [12],, ;, ; Fig. 1 1 Granular hier 36 7 Vol. 36, No. 7 2010 7 ACTA AUTOMATICA SINICA July, 2010 1, 2 1, 2, 3 1, 2,,,,,,, DOI,,, 10.3724/SP.J.1004.2010.00923 Distributed Simulation System Hierarchical Design Model Based on Quotient Space