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

Size: px

Start display at page:

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

京慷昝
7 years ago
Views:

1 39 9 Vol. 39, No ACTA AUTOMATICA SINICA September, ,,., ;,,, ;,,. LTS Hausdorff (Least trimmed square Hausdorff distance, LTS-HD),.,,.,,. DOI, LTS Hausdorff,,,,.., 2013, 39(9): /SP.J 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): [1],,., Manuscript received June 15, 2012; accepted November 29, 2012 (973 ) (2009CB320902), ( ), (2010GZS0168) Supported by National Basic Research Program of China (973 Program) (2009CB320902), National Natural Science Foundation of China ( ), and Natural Science Foundation of Jiangxi Province (2010GZS0168) Recommended by Associate Editor LIU Yi-Jun School of Aeronautical Manufacturing Engineering, Nanchang Hangkong University, Nanchang School of Information Engineering, Nanchang Hangkong University, Nanchang School of Software, Nanchang Hangkong University, Nanchang ,., [2] :. [3 5],,,.,,,.,. ( ),,., Besl [6] (Iterative closest point, ICP), [7 8]

2 ,.,, [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), 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],,., ( )

3 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 ˆx 1... ˆx i... ˆx n a b e P = ŷ 1... ŷ i... ŷ n, A = c d f (4) A 6, 3 A.,, A 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.

4 , x p 1 p 2 h, h p 1p 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 , Canny., Canny.,,,, 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.

5 9 : 1451,,.,,,,.. O C, 9, , (t 1, t 3 ) 18. 2), 0 1,, f(t 1, t 3 ) = 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; O C T, R C O C LTS-HD, τ ( 2 ), R C O C ;, s 1 = s 1 + η, s 1 η ( 50), s 1 > N (N R C ), R C O C ; 1, S 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 = ) N,. G, 20, , T A; A R C R C ;, LTS-HD R C O C,. 1.1,,, LTS-HD,.

6 ,,,. : 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 ( ) M M M (M )., 2, M M, M M M,,, ,,,. 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, , 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 ),,,, ( ) , , 3 1,, S; 2 ; 3 3 4, LTS-HD,, T., LTS-HD, δ LTS-HD

7 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, , 5. 4,, %. Chiropter, Chiropter,,. 5, 1 Table 1 Model and target images Table 2 2 Actual affine transformation matrices

8 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 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] Tsang [17]

10 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] Tsang [17] 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): Zitová B, Flusser J. Image registration methods: a survey. Image and Vision Computing, 2003, 21(11):

11 9 : 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): 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): 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, 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): 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): Liu Y H. Improving ICP with easy implementation for freeform surface matching. Pattern Recognition, 2004, 37(2): Hrkać T, Kalafatić Z, Krapac J. Infrared-visual image registration based on corners and Hausdorff distance. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 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): (,,.., 2007, 30(6): ) 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): (,,.., 2009, 35(3): ) 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): (,,,,. Co-motion., 2010, 36(9): ) 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): 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): (,,,.., 2012, 38(4): ) 15 Tsang P W M. A genetic algorithm for aligning object shapes. Image and Vision Computing, 1997, 15(11): 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): 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): 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): Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press, Mei Xiang-Ming, Liu Zeng-Xian, Wang Hui-Chun, Wang Zhi-Qiu. Higher Geometry (Third edition). Beijing: Higher Education Press, (,,,. ( 3 ). :, ).,.. 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.).. 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.).. chujun99602@163.com (CHU Jun Professor at the School of Software, Nanchang Hangkong University. Her research interest covers image processing and computer vision.)

9期张秀伟等: 基于 Co-motion 的可见光热红外图像序列自动配准算法 (a) 建筑物场景正午时的红外可见光图像对 (a) Thermal-visual image pair of building scene at noon (b) 道路场景红外可见光图像对 (b) Thermal-

9期张秀伟等: 基于 Co-motion 的可见光热红外图像序列自动配准算法 (a) 建筑物场景正午时的红外可见光图像对 (a) Thermal-visual image pair of building scene at noon (b) 道路场景红外可见光图像对 (b) Thermal- 36 9 Vol. 36, No. 9 2010 9 ACTA AUTOMATICA SINICA September, 2010 Co -motion 1 1 1 1 1 Co-motion, Co-motion,.,,,.,,. 8. DOI, Co-motion,, 10.3724/SP.J.1004.2010.01220 Automatic Visual-thermal Image Sequence