基于分层自适应遗传算法的图像配准
|
摘要
图像配准是图像分析和处理的基本问题,是评价两幅或多幅图像的相似性以确定同名点的过程。图像配准算法就是设法建立两幅图像之间的对应关系,确定相应几何变换参数,对两幅图像中的一幅进行几何变换的方法。本文将一种分层自适应遗传算法应用于基于特征的图像配准,保证了种群的多样性,加快了遗传算法的收敛速度。并且在算法中使用了LTS-Hausdorff距离作为图像配准的度量,使得整个算法在抵抗噪声和孤立点方面有很大优势,配准的精度也有所提高。
Image registration is one of the basic digital image processing methods , which mainlyregisters two or more digital images , mostly geometrically , obtained at di?erent time , bydi?erent sensors , on di?erent angle of view or on di?erent filming conditions . In recentyears , image registration is studied in many di?erent applying domains , so that it playsa very important role in computer vision , pattern recognition,medical image analysis andremote sensing . Image registration has become an essential part during many studies andresearches.
For the general problem of image registration , in case that two image of having o?setrelationship(including translation , rotation , scaling) are waiting for matching image T andthe reference image R , have the following shift relation :
The key problem of Image Registration is how to use e?ective methods to evaluate thesimilarity between images and the calculation of transformation parameters . In this paper, I use LTS-Hausdor? distance as the evaluation function , and use Hierarchical adaptivegenetic algorithm to calculate the parameters . This kind of method improve the accuracy ,stability , and e?ciency of Image Registration.
LTS(Least Trimmed Square)-Hausdro? distance is combination of the part Hausdor? distance and the average Hausdor? distance . It defined as :H = h×NA , NAis the number of point in the set , h∈[0.6, 0.9] , dB(a)(i) indicate that thei largest distance from point a to point b of set B . This method reduces impact of the noiseand isolated points on the accuracy and stability.
Genetic Algorithm base on Darwin’s genetic and natural selection calculation model .It is a way to search the optimal solution.
This paper combined hierarchical genetic algorithm with adaptive genetic algorithm ,use the high e?ciency of hierarchical genetic algorithm and maintaining diversity of adaptivegenetic algorithm , improve the computation speed.
Specifically , in the low-level operations :
I make PcandPmcan automatically change with fitness , because the choice of the crossoverprobability P(c) and mutation probability P(m)is the key of impact of algorithm behavior andperformance . It is a direct impact on the convergence of algorithm . The p(c) greater , newindividual generate faster.However , the possibility of Genetic model is damaged is greaterwhen P(c) is too large . High fitness individual structures are destroyed soon ; however , ifP(c) is too small,would slow the search process , as well as stagnation . For the mutationprobability P(m) , If P(m) is too small , it’s di?cult to have the structure of a new individual; If P(m) is too large , Genetic Algorithm then becomes a pure random search algorithm . Sowhen the fitness of individual populations of the set tend to line or tended to local optimum ,it makes P(c) and P(m) increased ; when the group fitness scattered , it makes P(c) and P(m)decreased . At the same time , for those group fitness is higher than the average fitness ofthe individual , the solution is be protected to access the next generation ; for those groupfitness is lower than the average fitness of the individual , the solution is swap out . Adaptivegenetic algorithm can help us work out the best P(c) and P(m) .
The computing of P(c) and P(m) as follows : fmax→the largest fitness value in the group ;favg→the average fitness value in each generation ;f→the larger of the two individual to be crossed fitness value ;f→fitness value of individual to varied fitness value。In this case , k1, k2, k3, k4∈(0, 1).
In the high-level operations :
First of all , it randomly generate N×n(N 2, n 2) samples , they then di-vide into N sub-populations , each sub-population contains n samples , independent ofeach sub-population genetic algorithm to run low-level operations , record them in GAi(i =1, 2,···, N) . It is best to set up sub-population characteristics with a great di?erence , thiscan produce a greater variety of mode .
After running to a certain algebraic in each sub-population of low-level genetic algo-rithm , record the results of population in R[1···N, 1···n] , R[i, j](i = 1···N, j = 1···n)indicate the i individual in the result population . At the same time , record the average fitnessof the results population in A[1···N] .
High-level genetic algorithm can be divided into the following three steps :
1 Selection :
Run Selection in array R base on A[1···N] . Some results population is copied becauseof their high average fitness value ; other results population is eliminated because of theirlow average fitness value .
2 Crossover :
If R[i, 1···n] and R[j, 1···n] are randomly assigned to one , moreover , the crossoveris from the location x , then R[i, x + 1,···, n] and R[j, x + 1,···, n] exchange of the corre-sponding part .
3 Mutation :
A small number of randomly generated new individuals to be replaced with randomlyselected individual in R[1···N, 1···n] .
Thus , the high-level genetic algorithm to run the end of the first round . Genetic Algo- rithm continue to operate in the new R[1···N, 1···n] .
According to the above parameters of the optimal solution derived , finish the transla-tion, rotation and stretching transformation .
At the last , finish image interpolation using Bi-cubic convolution :
Image registration is one of the basic digital image processing methods , which mainlyregisters two or more digital images , mostly geometrically , obtained at di?erent time , bydi?erent sensors , on di?erent angle of view or on di?erent filming conditions . In recentyears , image registration is studied in many di?erent applying domains , so that it playsa very important role in computer vision , pattern recognition,medical image analysis andremote sensing . Image registration has become an essential part during many studies andresearches.
For the general problem of image registration , in case that two image of having o?setrelationship(including translation , rotation , scaling) are waiting for matching image T andthe reference image R , have the following shift relation :
The key problem of Image Registration is how to use e?ective methods to evaluate thesimilarity between images and the calculation of transformation parameters . In this paper, I use LTS-Hausdor? distance as the evaluation function , and use Hierarchical adaptivegenetic algorithm to calculate the parameters . This kind of method improve the accuracy ,stability , and e?ciency of Image Registration.
LTS(Least Trimmed Square)-Hausdro? distance is combination of the part Hausdor? distance and the average Hausdor? distance . It defined as :H = h×NA , NAis the number of point in the set , h∈[0.6, 0.9] , dB(a)(i) indicate that thei largest distance from point a to point b of set B . This method reduces impact of the noiseand isolated points on the accuracy and stability.
Genetic Algorithm base on Darwin’s genetic and natural selection calculation model .It is a way to search the optimal solution.
This paper combined hierarchical genetic algorithm with adaptive genetic algorithm ,use the high e?ciency of hierarchical genetic algorithm and maintaining diversity of adaptivegenetic algorithm , improve the computation speed.
Specifically , in the low-level operations :
I make PcandPmcan automatically change with fitness , because the choice of the crossoverprobability P(c) and mutation probability P(m)is the key of impact of algorithm behavior andperformance . It is a direct impact on the convergence of algorithm . The p(c) greater , newindividual generate faster.However , the possibility of Genetic model is damaged is greaterwhen P(c) is too large . High fitness individual structures are destroyed soon ; however , ifP(c) is too small,would slow the search process , as well as stagnation . For the mutationprobability P(m) , If P(m) is too small , it’s di?cult to have the structure of a new individual; If P(m) is too large , Genetic Algorithm then becomes a pure random search algorithm . Sowhen the fitness of individual populations of the set tend to line or tended to local optimum ,it makes P(c) and P(m) increased ; when the group fitness scattered , it makes P(c) and P(m)decreased . At the same time , for those group fitness is higher than the average fitness ofthe individual , the solution is be protected to access the next generation ; for those groupfitness is lower than the average fitness of the individual , the solution is swap out . Adaptivegenetic algorithm can help us work out the best P(c) and P(m) .
The computing of P(c) and P(m) as follows : fmax→the largest fitness value in the group ;favg→the average fitness value in each generation ;f→the larger of the two individual to be crossed fitness value ;f→fitness value of individual to varied fitness value。In this case , k1, k2, k3, k4∈(0, 1).
In the high-level operations :
First of all , it randomly generate N×n(N 2, n 2) samples , they then di-vide into N sub-populations , each sub-population contains n samples , independent ofeach sub-population genetic algorithm to run low-level operations , record them in GAi(i =1, 2,···, N) . It is best to set up sub-population characteristics with a great di?erence , thiscan produce a greater variety of mode .
After running to a certain algebraic in each sub-population of low-level genetic algo-rithm , record the results of population in R[1···N, 1···n] , R[i, j](i = 1···N, j = 1···n)indicate the i individual in the result population . At the same time , record the average fitnessof the results population in A[1···N] .
High-level genetic algorithm can be divided into the following three steps :
1 Selection :
Run Selection in array R base on A[1···N] . Some results population is copied becauseof their high average fitness value ; other results population is eliminated because of theirlow average fitness value .
2 Crossover :
If R[i, 1···n] and R[j, 1···n] are randomly assigned to one , moreover , the crossoveris from the location x , then R[i, x + 1,···, n] and R[j, x + 1,···, n] exchange of the corre-sponding part .
3 Mutation :
A small number of randomly generated new individuals to be replaced with randomlyselected individual in R[1···N, 1···n] .
Thus , the high-level genetic algorithm to run the end of the first round . Genetic Algo- rithm continue to operate in the new R[1···N, 1···n] .
According to the above parameters of the optimal solution derived , finish the transla-tion, rotation and stretching transformation .
At the last , finish image interpolation using Bi-cubic convolution :
引文
[1] L.G.Brown.A survey of image registration technique,ACM Computing surveys[J].1992.
[2] Barbara Zitova,Jan Flusser.Image registration methods:A survey,Image and VisionComputing[J].2003:977-1000.
[3] Huttenlocher D P,Klanderman G A,Rucklidge W J.Comparing images using the Haus-dorf distance,IEEE Transactions on PAMI[J].1993:850-863.
[4] Dong-Gyu Sim,Oh-Kyu Kwon,and Rae-Hong Park.Object Matching Algorithms Us-ing Robust Hausdor? Distance Measures,IEEE Transactions On Image Processing[J].2004:425-428.
[5] Chalermwat P,El-Ghazawi T,Le Moigne J.Two-Phase Genetic Algorithm-Based Im-age Registration on Parallel Clusters[J].Journal of Future Generation ComputingSystems,2001:467-476.
[6] Brumby S,Theiler J,Perkins S,et al.Investigation of feature extraction by a geneticalgorithm[J].SPIE,1999:24-31.
[7] Daniel P.Huttcnlocher and William J.Rucklidge.A multi-resolution technique for com-paring images using the Hausdor? distance,IEEE Transactions un Pattern Analysis andMachine Intelligence[J].1993:705-706.
[8] Jialing C,James C.H.C,et al.CT and PET lung image registration and fusion in radiother-apy treatment planning using the chamfer-matching method,Int.J.Radiation OncologyBiol.Phys.[J].March,1999:883-891.
[9] G.Borgefors.Hierarchical chamfer matching:A parametric edge matching algorithm,IEEE Trans.Pattern Anal.Machine Intelligence[J].Nov.1988:849– 865.
[10] Health A,Sarkar S,Sanocki T.Comparison of Edge Detectors:A Methodology and InitialStudy.Computer Vision and Image Understanding[J].1998:38-54.
[11] Moghaddam B,Pentland A.Probabilistic visual learning for object representation, IEEETrans Pattern Analysis and Machine Intelligence[J].1997:696-710.
[12] Rowley H A,Baluja S,Kanade T.Neural Network Based Face Detection[J].IEEE TransPattern Analysis and Machine Intelligence,1998:23– 38.
[13] Roth D,Yang M H,Ahuja N.A Snow-Based Pace Detector[C].In:Advance in NeuralInformation Processing Systems.2000.
[14] Osuan E,Freund R,Girosi F.Training support vector machines:An application to facedetection.1997: 130-136.
[15] Viola P.Rapid objects detection using a boosted cascade of simple features, Proceedingsof IEEE Conference on Computer Vision and Pattern Recognition.2001: 5I1-518.
[16] Yong M,Ding X Q.Real-Time Multi-View Face Detection and Pose Estimation Basedon Cost-Sensitive AdaBoost,Tsinghua Science and Technology.2005:152-157.
[17] Maricor S,Birgitta M,Sami H,Mika L.Adaptive Skin Color Modeling Using the SkinLocus for Selecting Training Pixels,Pattern Recognition.2003:681-690.
[18] Moritz S,Erik G.Adaptive a Statistical Skin Color Model to Illumination Changes, FirstEuropean Conference on Color in Graphics,Imaging and Vision[C].2002.
[19]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[20]雷英杰,张善文,李旭武,周创明.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005.
[21]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2001.
[22]曹岩,李明雨.MATLAB R2006a基础篇[M].北京:化学工业出版社,2008.
[23] [美]罗纳德.N.布雷斯韦尔,殷勤业,张建国.傅里叶变换及其应用[M].西安:西安交通大学出版社,2005.
[2] Barbara Zitova,Jan Flusser.Image registration methods:A survey,Image and VisionComputing[J].2003:977-1000.
[3] Huttenlocher D P,Klanderman G A,Rucklidge W J.Comparing images using the Haus-dorf distance,IEEE Transactions on PAMI[J].1993:850-863.
[4] Dong-Gyu Sim,Oh-Kyu Kwon,and Rae-Hong Park.Object Matching Algorithms Us-ing Robust Hausdor? Distance Measures,IEEE Transactions On Image Processing[J].2004:425-428.
[5] Chalermwat P,El-Ghazawi T,Le Moigne J.Two-Phase Genetic Algorithm-Based Im-age Registration on Parallel Clusters[J].Journal of Future Generation ComputingSystems,2001:467-476.
[6] Brumby S,Theiler J,Perkins S,et al.Investigation of feature extraction by a geneticalgorithm[J].SPIE,1999:24-31.
[7] Daniel P.Huttcnlocher and William J.Rucklidge.A multi-resolution technique for com-paring images using the Hausdor? distance,IEEE Transactions un Pattern Analysis andMachine Intelligence[J].1993:705-706.
[8] Jialing C,James C.H.C,et al.CT and PET lung image registration and fusion in radiother-apy treatment planning using the chamfer-matching method,Int.J.Radiation OncologyBiol.Phys.[J].March,1999:883-891.
[9] G.Borgefors.Hierarchical chamfer matching:A parametric edge matching algorithm,IEEE Trans.Pattern Anal.Machine Intelligence[J].Nov.1988:849– 865.
[10] Health A,Sarkar S,Sanocki T.Comparison of Edge Detectors:A Methodology and InitialStudy.Computer Vision and Image Understanding[J].1998:38-54.
[11] Moghaddam B,Pentland A.Probabilistic visual learning for object representation, IEEETrans Pattern Analysis and Machine Intelligence[J].1997:696-710.
[12] Rowley H A,Baluja S,Kanade T.Neural Network Based Face Detection[J].IEEE TransPattern Analysis and Machine Intelligence,1998:23– 38.
[13] Roth D,Yang M H,Ahuja N.A Snow-Based Pace Detector[C].In:Advance in NeuralInformation Processing Systems.2000.
[14] Osuan E,Freund R,Girosi F.Training support vector machines:An application to facedetection.1997: 130-136.
[15] Viola P.Rapid objects detection using a boosted cascade of simple features, Proceedingsof IEEE Conference on Computer Vision and Pattern Recognition.2001: 5I1-518.
[16] Yong M,Ding X Q.Real-Time Multi-View Face Detection and Pose Estimation Basedon Cost-Sensitive AdaBoost,Tsinghua Science and Technology.2005:152-157.
[17] Maricor S,Birgitta M,Sami H,Mika L.Adaptive Skin Color Modeling Using the SkinLocus for Selecting Training Pixels,Pattern Recognition.2003:681-690.
[18] Moritz S,Erik G.Adaptive a Statistical Skin Color Model to Illumination Changes, FirstEuropean Conference on Color in Graphics,Imaging and Vision[C].2002.
[19]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[20]雷英杰,张善文,李旭武,周创明.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005.
[21]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2001.
[22]曹岩,李明雨.MATLAB R2006a基础篇[M].北京:化学工业出版社,2008.
[23] [美]罗纳德.N.布雷斯韦尔,殷勤业,张建国.傅里叶变换及其应用[M].西安:西安交通大学出版社,2005.