,.,, [9] Harris, Hausdorff, ; [10],,,. [11],,,,,., [12 13] ; [14], ;,,.,,., ( ), [15 17],. Tsang [15],,,. Tsang [16] (Simple genetic algorithm

39 9 Vol. 39, No. 9 2013 9 ACTA AUTOMATICA SINICA September, 2013 1 2 3,,., ;,,, ;,,. LTS Hausdorff (Least trimmed square Hausdorff distance, LTS-HD),.,,.,,. DOI, LTS Hausdorff,,,,.., 2013, 39(9): 1447 1457 10.3724/SP.J.1004.2013.01447 Affine Registration Based on Chord Height Point and Genetic Algorithm ZHANG Gui-Mei 1 JIANG Shao-Bo 2 CHU Jun 3 Abstract It is difficult to recognize objects when they are distorted and partially occluded or broken. In order to solve the problems, a new registration algorithm combining chord height point with genetic algorithm is proposed in this paper. Firstly, we define the chord height point and prove it is affine invariant. Then, the global optimal affine transformation matrix is calculated by using three pairs of corresponding points, where two corresponding points in the contours of model and target are searched by the genetic algorithm, and the chord height point is used as the third pair of corresponding points. Finally, linear search is introduced to search the local optimal affine transform matrix, and the accuracy of registration is improved. We use least trimmed square Hausdorff distance (LTS-HD) to measure the similarity between the model and target, so our method can deal with object partially occlued and broken. Furthermore, the registration speed is improved by using genetic algorithm to search corresponding points and only searching two pairs of corresponding points. The theory analysis and experimental results show that our algorithm can be effectively used for affine registration, and can deal with objects partially occlued and broken. Key words point Affine registration, least trimmed square Hausdorff distance (LTS-HD), genetic algorithm, chord height Citation Zhang Gui-Mei, Jiang Shao-Bo, Chu Jun. Affine registration based on chord height point and genetic algorithm. Acta Automatica Sinica, 2013, 39(9): 1447 1457 [1],,., 2012-06-15 2012-11-29 Manuscript received June 15, 2012; accepted November 29, 2012 (973 ) (2009CB320902), (61063030), (2010GZS0168) Supported by National Basic Research Program of China (973 Program) (2009CB320902), National Natural Science Foundation of China (61063030), and Natural Science Foundation of Jiangxi Province (2010GZS0168) Recommended by Associate Editor LIU Yi-Jun 1. 330063 2. 330063 3. 330063 1. School of Aeronautical Manufacturing Engineering, Nanchang Hangkong University, Nanchang 330063 2. School of Information Engineering, Nanchang Hangkong University, Nanchang 330063 3. School of Software, Nanchang Hangkong University, Nanchang 330063,., [2] :. [3 5],,,.,,,.,. ( ),,., Besl [6] (Iterative closest point, ICP), [7 8]

1448 39,.,, [9] Harris, Hausdorff, ; [10],,,. [11],,,,,., [12 13] ; [14], ;,,.,,., ( ), [15 17],. Tsang [15],,,. Tsang [16] (Simple genetic algorithm and quality migrants, SGA-QM), [15],,. Tsang [17],,,. ( [17] 128 ) 100 %, [15] [16],,,., ( ). : 1), ; 2),,,,,,, ; 3) LTS-HD (Least trimmed squre Hausdorff distance), LTS-HD,, ; 4),. 1 1.1 Hausdorff Hausdorff,. : A = {a 1, a 2,, a p } B = {b 1, b 2,, b q }, A, B Hausdorff : H(A, B) = max{h(a, B), h(b, A)} (1) h(a, B) = max a A min b B a b h(b, A) = max b B min a A b a (2) A B.,., Hausdorff,,., Hausdorff LTS-HD [18] : h LTS (A, B) = 1 Γ d(a, B) i (3) Γ i=1, Γ = δ N A, N A A, δ [0.6, 0.9], δ ; d(a, B) i A a B i. (3), A B LTS-HD A B,. 1.2 Holland [19],,., ( )

9 : 1449.,,. ( ),,., : 1), ( ) ; 2), ; 3), ; 4).,. 1.3,,, 10,. Q P, : AQ = P (4), x 1... x i... x n Q = y 1... y i... y n 1... 1... 1 ˆx 1... ˆx i... ˆx n a b e P = ŷ 1... ŷ i... ŷ n, A = c d f 1... 1... 1 0 0 1 (4) A 6, 3 A.,, A. 2 1. p 1 p 2, p 1 p 2, p 1 p 2 p 1 p 2.,. n, : n, p 1 p 2 (n + 1)/2 ; n, n/2.,. 1, h p 1 p 2. 1 Fig. 1 p 1p 2 ( ) p 1 p 2 ( ) Curve p 1p 2 (left) and curve p 1 p 2 (right) 1. p 1 p 2, h. p 1p 2 p 1 p 2, h h,, h p 1p 2.. 1, p 1 p 2 p 1p 2,, p 1 p 2 p 1 p 2, p 1 p 1, p 2 p 2. x p 1 p 2, x xx p 1 p 2, x p 1p 2 x, x x x p 1p 2. p 1x p 2 p 1xp 2. [20],, : S p 1 x p 2 S p1xp 2 S p 1 x p 2 S p1xp 2 = C, C = 1 2 p 1p 2 x x = 1 2 p 1p 2 xx p 1p 2 x x p 1 p 2 xx p 1 p 2 p 1p 2, = C p 1p 2 p 1 p 2 = C 1, C 1 x x xx = C C 1 = k, k : xx, x x. xx x, x p 1 p 2, x p 1p 2., xx n (n ), x p 1 p 2 ( x p 1 p 2 p 1 p 2 (n + 1)/2 n/2 xx ), x x, x p 1p 2 p 1 p 2 (n + 1)/2 n/2 x x, x p 1p 2.

1450 39, x p 1 p 2 h, h p 1p 2. 2. p 1 p 2, h, p 1p 2 p 1 p 2, h, h h.. h h. h p 1 p 2, p 1 p 2 p 1 p 2. h 1 h p 1p 2, 1, h 1 p 1p 2., h p 1p 2. p 1p 2 h 1 h,. h h 1, h h. 1 2.,.,,,,,. 3 2, :, A, A. 2 ( : S; : T ; : ) Fig. 2 Sketch map of contour curves registration (Model contour and seed point set S (left); Target contour of and test point set T (middle); Registration result of two contour curves (right)), : 1) R C = { R C i i = 1, 2,, N}, N, R C,,, R C i = ( R x i, R y i ) R C i. R C R C A ; S = [s 1, s 2, s 3 ], S R C,, s 1, s 2, s 3. 2) O C = { O C j j = 1, 2,, M}, M, O C,, O C j = ( O x j, O y j ) O C j. T = [t 1, t 2, t 3 ], T O C,, t 1, t 2, t 3. 4,,, 3 ;, 3, 3,. 4.1 :, R C S ( s 1, s 3 s 2, s 1 =1);, O C T ;, S T A, A R C R C ;, R C O C LTS-HD, τ, R C O C,, s 1 = s 1 + η (η ), s 1 > N (N R C ), R C O C,, R C S. 3. 4. 4.1.1, Canny., Canny.,,,,. 4.1.2 S R C S, : 1. R C s 1 s 3, s 3 s 1 1/3. s 1 =1, R C., s 1 s 3, ; s 1 s 3,., 1/3.

9 : 1451,,.,,,,.. O C, 9, 512. 512, (t 1, t 3 ) 18. 2), 0 1,, f(t 1, t 3 ) = 1 1 + H LTS ( R C, O C) (5) Fig. 3 3 Flow chart of rough registration 2. 2, s 1 s 3 ( ), s 2. s 1, s 2, s 3, S; 4. 3. O C T, R C O C LTS-HD, τ ( 2 ), R C O C ;, 4. 4. s 1 = s 1 + η, s 1 η ( 50), s 1 > N (N R C ), R C O C ; 1, S. 4.1.3 T T,.,,,,., O C t 1 t 3, t 1 t 3 t 2, T. s 1 s 3 t 1 t 3, 2,, t 2 s 2, T S, A. O C, A T. : 1) (t 1, t 3 ). H LT S ( R C, O C) R C O C LTS-HD., R C R C A. 3).,,.. : (N) (p c ) (p m ) (G). :, ;., : N = 100, p c = 0.8, p m = 0.2, G = 200. 4) N,. G, 20,. 4.1.4., T A; A R C R C ;, LTS-HD R C O C,. 1.1,,, LTS-HD,.

1452 39 4.2,,,. : 1) T., O C t 1 t 3 (5 10 ) l 1 l 3 (l 1 l 3 ),, l 1 l 3 t 1 t 3, t 2, l 1 l 3 T. 2) S T A, A R C R C, R C O C LTS-HD, l 1 l 3 LTS-HD. 3) l 1 l 3 LTS-HD,, T T, A, R C O C 4.3 4.3.1 3 ( ) M M M (M )., 2, M M, M M M,,,. 4.3.2,,,. m, n, t. : 1), LTS-HD O(M N), N. O(M N) O(t m n), O(M N t m n); 2),, 1,, M/2,, O((1 + M/2)/2) O(t m), O(M t m); 3), P (P 10 20), LTS- HD O(M N P P ), O(M P P ). O(M N P P )+ O(M P P ). O(M t m) O(M N t m n), P t m, 2) 3) 1), O(M N t m n). 3 O(M N t m n). t n,. 4.3.3, O(m n). O(P P ), O(m n),. O(m n). 3 O(m n). n,. 5 : Pentium D2.60 GHz CPU, 1.0 GB, Matlab 2010a. 5.1, MPEG7 CE-Shape-1 Part B. 1, 6, 2 (, Chiropter ),,,, ( ). 5.2 1., 1 6. 3, 3 1,, S; 2 ; 3 3 4, LTS-HD,, T., LTS-HD, δ 0.9. 3 LTS-HD

9 : 1453,. 2. ( ),, 50 %., 1 6 ( ). 4, 4 1 ; 4 2,, S; 4 3 4, LTS-HD,, T. 1.1 LTS-HD, 1.1 (3), δ [0.6, 0.9], δ, 1 ( ),, δ 1 δ 0.9,, LTS-HD, δ 0.7,. 4 LTS-HD,. 5.3, LTS-HD,, 3 4 LTS-HD. : 1) ; 2) ; 3)., LTS-HD ;,., [16 17] ( Tsang [16] Tsang [17] [16 17] ),. 3, 200. 4., 5. 4,, 6 100 %. Chiropter, Chiropter,,. 5, 1 Table 1 Model and target images Table 2 2 Actual affine transformation matrices

1454 39 Table 3 3 Rough and precise registration results of model and target contours,. 3, ( ),,.,, A est 2 A,. 5 6, A A est 2, 2 2-., Tsang [16] Tsang [17].,,,

9 : 1455 Table 4 4 ( ) Registration results of partial occlusion and broken contours 5 A A est 2 Table 5 The average absolute error A A est 2 Hammer Apple Bird Fish Camel Chiropter Tsang [16] 13.4608 8.4529 10.0534 15.2018 12.3529 14.7514 Tsang [17] 19.7238 14.3769 11.8050 12.8736 9.3517 12.2653 0.6153 0.8613 0.9508 0.2089 3.7017 3.1113

1456 39 6 A A est 2 / A 2 Table 6 The average relative error A A est 2 / A 2 Hammer Apple Bird Fish Camel Chiropter Tsang [16] 0.0530 0.0871 0.0914 0.1168 0.0863 0.2269 Tsang [17] 0.0776 0.1482 0.1073 0.0990 0.0653 0.1187 0.0024 0.0089 0.0098 0.0016 0.0259 0.0479 Fig. 4 4 Registration success rates of three algorithms Fig. 5 5 Average number of generations to attain success registration of three algorithms, Tsang [16] Tsang [17].,. 6., ;, 2,, ;, ;, ; LTS-HD,.,,., Tsang [16] Tsang [17].,, ;, Tsang [16] Tsang [17].,, A.,,. References 1 Brown L G. A survey of image registration techniques. ACM Computing Surveys, 1992, 24(4): 325 376 2 Zitová B, Flusser J. Image registration methods: a survey. Image and Vision Computing, 2003, 21(11): 977 1000

9 : 1457 3 Lu X S, Zhang S, Su H, Chen Y Z. Mutual information-based multimodal image registration using a novel joint histogram estimation. Computerized Medical Imaging and Graphics, 2008, 32(3): 202 209 4 Lee J H, Kim Y S, Lee D, Kang D G, Ra J B. Robust CCD and IR image registration using gradient-based statistical information. IEEE Signal Processing Letters, 2010, 17(4): 347 350 5 Zhang X Q, Men T, Liu C, Yang J. Infrared and visible images registration using BEMD and MI. In: Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology. Chengdu, China: IEEE, 2010. 644 647 6 Besl P J, McKay H D. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239 256 7 Sharp G C, Lee S W, Wehe D K. ICP registration using invariant features. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(1): 90 102 8 Liu Y H. Improving ICP with easy implementation for freeform surface matching. Pattern Recognition, 2004, 37(2): 211 226 9 Hrkać T, Kalafatić Z, Krapac J. Infrared-visual image registration based on corners and Hausdorff distance. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2007. 383 392 10 Gao Feng, Wen Gong-Jian, Lv Jin-Jian. An optimal algorithm for IR/visual image registration based on mainline-pairs. Chinese Journal of Computers, 2007, 30(6): 1014 1021 (,,.., 2007, 30(6): 1014 1021) 11 Su Juan, Lin Xing-Gang, Liu Dai-Zhi. A multi-sensor image registration algorithm based on structure feature edges. Acta Automatica Sinica, 2009, 35(3): 251 257 (,,.., 2009, 35(3): 251 257) 12 Zhang Xiu-Wei, Zhang Yan-Ning, Yang Tao, Zhang Xin- Gong, Shao Da-Pei. Automatic visual-thermal image sequence registration based on co-motion. Acta Automatica Sinica, 2010, 36(9): 1220 1231 (,,,,. Co-motion., 2010, 36(9): 1220 1231) 13 Bilodeau G A, Torabi A, Morin F. Visible and infrared image registration using trajectories and composite foreground images. Image and Vision Computing, 2011, 29(1): 41 50 14 Lian Lin, Li Guo-Hui, Zhang Jun, Tu Dan. An automatic registration algorithm of infrared and visible images based on optimal mapping of edges. Acta Automatica Sinica, 2012, 38(4): 570 581 (,,,.., 2012, 38(4): 570 581) 15 Tsang P W M. A genetic algorithm for aligning object shapes. Image and Vision Computing, 1997, 15(11): 819 831 16 Tsang P W M, Yuen T Y F. Affine invariant matching of broken boundaries based on an enhanced genetic algorithm and distance transform. IET Computer Vision, 2008, 2(3): 142 149 17 Tsang P W M, Situ W C. Affine invariant matching of broken boundaries based on simple genetic algorithm and contour reconstruction. Pattern Recognition Letters, 2010, 31(9): 771 780 18 Sim D G, Kwon O K, Park R H. Object matching algorithms using robust Hausdorff distance measures. IEEE Transactions on Image Processing, 1999, 8(3): 425 429 19 Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press, 1975 20 Mei Xiang-Ming, Liu Zeng-Xian, Wang Hui-Chun, Wang Zhi-Qiu. Higher Geometry (Third edition). Beijing: Higher Education Press, 2008. 13 (,,,. ( 3 ). :, 2008. 13).,.. E-mail: guimei.zh@163.com (ZHANG Gui-Mei Professor at the School of Aeronautical Manufacturing Engineering, Nanchang Hangkong University. Her research interest covers image processing, computer vision, and pattern recognition. Corresponding author of this paper.).. E-mail: jiangshbo2010@163.com (JIANG Shao-Bo Master student at the School of Information Engineering, Nanchang Hangkong University. His research interest covers image processing and pattern recognition.).. E-mail: chujun99602@163.com (CHU Jun Professor at the School of Software, Nanchang Hangkong University. Her research interest covers image processing and computer vision.)