匹配pr查询

lf第18卷第2期l999年4月红外与毫米波学报J.
InfraredMillim.
WavesVn1.
18,No.
2Apr[1+1999基于遗传算法的快速图像相关匹配朱红赵亦工(西安电子科技天军程写夏磊泵再,西安,710071)弋摘要采用遣传算法研究了图像相关匹配问题,提出了快速图像相关匹配算法在最优匹配的前提下t其计算量较SSDA算法降低了一十数量级以上f可以采用NPROD匹配准则,改善在低图像对比度条件下的旺配精度;该算法每曲图像匹配计算时间基本恒定,便于工程应用.
.
蝴璧引言,u图像相关匹配跟踪技术是光电成像系统对运动和静止面目标跟踪的基本手段.
对于近距离面目标或尺寸很大的面目标,目标图像占据视场的大部分或充满视场,图像相关匹配的数据量和计算量很大.
图像相关匹配的计算实时性在一定程度上决定了该技术的实用性.
在工程上常用的快速图像相关匹配算法有两种;序贯相似检测算法(SSDA)m和多分辨率塔形结构算法(MPSA)口.
SSDA算法能够保证图像匹配的全局最优性,但SSDA算法只能采用MAD匹配准则,不能采用NPROD匹配准则,并且随目标位置不同,每帧图像所需的匹配时间不定,不便于工程实现.
MPSA算法可采用MAD和NPROD匹配准则,每帧图像所需的匹配时间基本恒定,但MPSA算法原理上存在失配的可能,特别是低对比度条件下失配的可能性更大,它以匹配精度的损失换得速度的提高.
因此,在保证最优匹配精度的前提下大幅度降低图像相关匹配的计算量是人们关注研究课题.
图像相关匹配的计算量取决于它寻找最佳匹配位置时采用的搜索策略.
现有的方法均采用遍历式搜索策略,因而计算量的降低有限,如果不采用新的搜索策略,则难以在计算量的降低上取得实质性的突破.
这是现有图像相关匹配算法的共同缺陷.
遗传算法是近年发展起来的新理论和新方法0],其主要优点是简单、通用、鲁棒性和适于并行处理-它采用非遍历寻优搜索策略,可以保证寻优搜索的结果具有全局最优性,所需的计算量较之遍历式搜索小得很多.
国外学者已经将遗传算法用于研究点模式匹配问题∞.
本文将遗传算法用于图像相关匹配算法的研究,提出了快速图像相关匹配算法.
在同样的匹配效果条件下,该算法在计算速度上较SSDA算法提高了一个数量级以上,并且可以采用NPROD匹配准则,提高在低信噪比条件下的匹配精度;该算法还具有每帧图像匹配计算时间基本恒定的优点,便于在实际系统中采用.
1算法原理将遗传算法用于图像相关匹配问题,要解决以下五个问题国防顼研基金(编号:94J1A.
5.
2)资助项目祷件收到刚胡1998—09-25,修改稿收到日期199812-07L,JL,.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
一-li盘l维普资讯http://www.
cqvip.
com(ipfc红外与毫米;皮学报J.
II主fraredMillim.
Wav臼Vol.
18.
No.
2April.
1999基于遗传算洼的快速图像相关匹配择-rN钉子18朱红赵在工《西安电子科技大军奋军程写在雾罩TZEE耳,西安.
71∞71)摘要采用遗传算法研究7图缘梧是在配问题.
提出了快速I!
l像相关区军算法在最优匹配能有官提下.
其计算量毒草SSDA算法降低了一本数量级以土z可以采坷NPROD匹盈准则,改善在短留您对比5董事件下的匹配精度'该算法每顿I!
l像匹革计算砖阂基本恒定,便于工程应蜀a关键部图缘相关在配,遗传算法,快速计算也/鸟.
.
.
:'fl~.
.
tDn冒疆军民,引言,"'-可""T.
r-'图像相关匹配跟踪技术是光电成像系统对运动和静止面曰标跟踪的基本子段.
对于近距离面目标或尺寸很大的面目标,目标图像占据视场的大部分或充满视场,图像相关匹配的数据量和计算量很大,题像相关匹配的计算实时住在一定程度上决定了该技术的实用性.
在工程上常用的快速图像裙关匹配算法有两种a序贯幸13ftt检测算法(SSDA)cll和多分辨率塔形结构算法(MPSA)[21.
SSDA算法能够保证图像匹配的全局最优性,但SSDA算法只能采用MAD匹配准则,不能采用NPROD匹配准贱,并豆黯目标位量不同,每核图像所需豹匹配tt-tl可不定,不便于工程实现.
MPSA算法可采1fiMAD和NPROD匹配准则,每帧图像所需的匹配tt-t间基本恒定,但MPSA算法原理上存在失重己的可能,特别是低对比度条件下失配灼可能性更大,官以匹配精度的损失挨得速度拍提高.
因此,在保证最优匹配精度的前提下大幅度降低图像相关匹配的计算量是人们关注研究课题.
题像丰E关匹雪己的计算量取决于宫寻找最佳匹配位置对采用自号搜索策黯.
现有的方法均采用遍历式搜索策略,因而计算量的降低有限,如果不采用新的搜索策略,则难以在计算量的降低上取得实质性的突破.
这是现有图像相关匹配算法的共同缺陷·遗传算法是近年发展起来的新理论和新方法时,其主要优点是简单、通用、鲁棒性和适于并行处理凰宫采用非遍历寻优搜索策略,可以保证寻优搜索的结果具有全局最优性,所需的计算量较之造历式搜索小得很多,国外学者已经将遗传算法用于研究点模式匹配问题[5J本文将遗传算法屑于图像相关匹配算法的研究,提出了快速图像相关匹配算法.
在同样的匹配效果条件下,该算法在计算速度上较SSDA算法提高了一个数量级以上,并且可以采用NPROD匹配准则,提高在低信暖比条件下的匹配精度z该算法还具有每帧图像匹配计算对问基本恒定的优点.
便于在实际系统中采用.
E算法原理将遗传算法用于图像相关匹配问题,要解决以下五个河12j,e匿防霸哥哥基金t编号,9t图像尺寸为N,XN,=460X256.
匹配模板的尺寸为M,XMz=64X64.
考虑到跟踪地面低对比度黯定西目标时.
匹配模板中的各个区域具有同等豹重要性.
所以在下面的仿真过程中无论MAD匹配准则或Nprod匹配准则,海采用单模板Illilfl!
.
2.
2仿真过程及参数人口数=30,进化代数=20'(1)匹配位置编码方式,Gray码.
(2)初始化z按四分之一模板的面积对实时图像进行划分,将实肘图像划分为14X8=112个矩形区域,采用黯机初始化的方式获得位于该区域内的两个"初始人口气计算所有初始人口的相关匹配度量显数,选择适应度最高韵30个人口作为遗传算法的画初始化人口气(3)线性化等级指标为1O-40C等缀增量d=1.
窗口基值w=10)'(4)交叉操作概率=1'自t无条件交叉);突变操作概率=司.
01.
(5)贪婪搜索区域z最大适应度人口对应的空间匹配位置题目3X3领域.
(击〉稳态无重复替代z逆向比较.
a~子代中的最优者与父代中部最差者比较,子代中次最优者与父代中豹次最差者比较,余者类推'如果前者大于后者,即用前者取代后者.
2.
3仿真参数选择依据原理上讲,对于一定数量的人口,遗传算法为了搜索到全局最佳解,需要较多的进化代数E当人口数和进化代数较少苦苦,遗传算法能否搜索到全局最优解,既与算法的处理过程和参数豹选择有关.
也与具体问题的性质有关.
上述初始化参数的选择,使得在每一个四分之一模板峦积大小的区域内有2个人口.
因此初始化所得到的30个初始化人口的匹配精度小于二分之一模板尺寸,即小于32个像素E理想情况医配精度达到1m分之一模板尺寸.
I!
P16个像素).
由于遗传算法的处理过程中引入了贪婪算子.
使得每一代人口中适应度最大的人口从局部最优匹配位置向全局最优区配位置至少移动一个像素,再考虑到其立遗传操作带来的寻优搜索能力,经20代人口进化后,将搜索到全局最优匹夜位置.
;iU2期朱红等:基于遗传算法的快速图像相关匹配仿真计算表明:在进化代数超过15代后,30个人口将集中在最优匹配位置周围大约1o*10个像素的区域内,当进化代数达到20代时,获得全局最优匹配位置.
2.
4匹配计算量分析遗传算法大幅度减少了图像相关匹配中模板匹配的次数,计算量大幅度降低,从理论上做如下分析.
(1)原始相关匹配.
窗匹配次数一(460—64+1)*4256—64+1)一1O1569.
(2)遗传算法相关匹配.
窗匹配次数一(初始化)+(代数)*[(人口数)+(贪婪搜索)]=(2*112)+2O*(3O+8)一984,(3)计算效率=101569/984c~103(倍),考虑到遗传算法在遗传操作时所需的额外计算量,实际的计算效率低于上述值.
2.
5仿真计算结果分析从图4(a)中取定匹配模板,在图4(b)中进行全场相关匹配.
用P166MMX微机计算结果如表1所示.
仿真中所选的图像亮度很高但对比度很低,图像中大部分区域没有明显的结构特征,某些匹配模板相似度很大(模板3和4,5和6,7和9),某些模板包含的是匀质区(模板lo),因此属于难度较大的图像相关匹配例子.
图4相隔若干帧的两幅地面目标红外图像Fig.
4Tw0infraredimagesofobjectsOnthegroundseparatedfromseveralflames衰1MAD匹配准则下不同匹配算法计算性能比较Table1Compa~sonofcomputationpel-formmlceoftUffeventmatehingalgortthins岫derMADmatchingcritert0n维普资讯http://www.
cqvip.
com2黯朱红等z基子遗传算法的快速图像相关匹配149仿真计算表明z在进化代数超过15代后.
30个人口将集中在最优匹配位置属国大约mX10个像素的区域内,当进化代数达到20代时,获得全局最优匹配位置.
2.
4匹配计算量分析遗传算法大幅度减少了图像相关匹配中模板匹配的次数,计算量大幅度降低,从理论上做部下分析.
(1)原始相关匹配.
窗匹配次数=(460-64+1)X(256臼+1)=101569.
(2)遗传算法相关匹配.
窗匹配次数=(协始化〉十{代数)X口人口数)+(贪婪搜索)J=(ZXl12)十ZOX(30十创=♀84.
(3)计算效率=1015691告"三~103(倍儿考虑到遗传算法在遗传操作时所需前额外计算量,实际始计算效率低于上述锺.
2.
5仿真计算结果分析从图4(心中取定匹配模板,在图4Cb)中进行全场相关匹配.
用P166MMX薇机计算结果如表1)j开示,街真中所选的图像亮度很高但对比度很低,图像中大部分区域没有明显的结构辛辛征.
某些匹昆模板招似度很文〈模板3秧垂.
5和6,7和份,某些模扳包含的是匀震区〈模板10).
西此属于难度较大的图像相关匹配例子.
(.
)(b)图4相隔若干脑前两幅地面目标红外rn像Fíg.
4τ胃口infraredimagesofobjectsonthegroundseparatedfromseveralframes表1MAD匹配准则下不同匹配算法计算性能比载Table1c.
.
mpa巾.
oofcompu.
tationperf'ormaneeofdifrere画tE国.
klJiag.
Igori由msunderMADmatch量撞事criteriOD序原始位置原结算法SSDA遗传算法号匹雹位置时间/,匹配位置时何/,主];)e位置时i哥/,1098.
96){}98咽96)43.
7(}98.
91)>22.
14(198.
96).
.
662(271、116)(271.
11&J43.
7(271.
116)22.
08(211.
116>在663(118.
102)(118.
102)43.
7(118,102122.
4.
1(219.
16>(3.
1(279.
16)14.
06(279.
16)ü.
667U98.
165J098.
165>4.
3.
7(198'165>23.
18(198唱165)0.
668(98.
176)(99.
176)4.
,3.
1(99.
176)24.
17支99.
116)0.
669(358'96){358.
96)43.
1(358.
96)22.
-41058.
~6)1).
6610(38嘈16)<39噎16143.
1<39噜16113.
62(39,16).
.
66iij4=a红外与毫米波学报l8卷从表1可见:在所有匹配位置上,匹配结果与传统方法相同.
在匹配计算所需的时间上,SSDA算法的速度比原始算法提高一倍左右,但所需的计算时间与匹配模板在图像中的位置有很大关系.
对于同样的匹配效果,遗传算法的速度较SSDA算法提高一个数量级以上,且匹配时间基本恒定(遗传算法中随机判决运算所带来的计算量波动,相比较而言,可以忽略).
采用Nprod匹配准则获得的匹配结果类似,差别在于传统算法需时134s,而遗传算法需时只2s.
我们利用上述仿真程序做过数百幅不同种类图像的相关匹配实验,得到相同的结果,由于篇幅的限制,本文仅给出其中一个难度较大的典型例子.
REiCERENCES1BarneaDI.
SilvermanHE.
Aclassofalgorithmsfordigitalimagegistration,IEEE,1972,C一21(2):179一I882KashefBG.
Asurveyofnewtechniquesforimageregistrationandmapping,SPIE,1983,443:222·2893GoldbergDE.
OptimizationandMachineLearning,Massachusetts:AddisonWesley,19894DavisL.
Handbook0,GeneticA咖nms,NewYork:VanNostrandReinhold,19915AnsariN,a1.
,andChaoticProgramming.
JohnWiley&Sons,lnc一,1992FASTIMAGEC0RRELATIVEMATCHlNGBASED0NGENETICALG0RITHM(DepartmentofZHUHongZHAOYi—GongandEauipment.
XidianUniversityXian.
Shaanxi710071,China)AbstractTheproblemofimagecorrelativematchingwasstudiedbymeansofgenetical—gorithmandafastimagecorrelativematchingalgorithmwaspresented.
Withtheconditionofoptimummatching,thecomputationamountofthealgorithmwasreducedmorethan10timescomparedwithSSDAalgorithm.
TheNPRODmatchingcriterioncanbeemployedinthisalgorithmtoimprovethematchingprecisionforthecaseoflowimagecontrast.
Thecomputationtimeisnearlyconstantformatchingeachframeofimagesinthepresentedal—gorithm,whichbringsconveniencetOthepracticalapplication—Keywordsimagecorrelationmatching,geneticalgorithm,fastcomputation.
TheprojeetsupportedbythePrellnfinaryRes~rehFoundat~nofNationalDefenseReceived1998_0925.
re-,ised19981207t、维普资讯http://www.
cqvip.
com旦旦组持与毫未应学报18卷从表1可觅z在所有匹配位置上.
匹配结果与传统方法极同.
在匹配计算所需的时间上.
SSDA算法的速度比原始算法提高一倍左右,但所需的计算时间与匹配模板在黯像中的位置有很大关系.
对于同样的匹配效果.
遗传算法的速度较SSDA算法提高→个数量级以上.
且匹配时间基本恒定〈遗传算法中随扒手11决运算所带来的计算量波动,相比较而言.
可以忽略L采用Nprod匹配准则获得的匹配结果类似,差别在了传统算法需时134s.
而遗传算法需Bt只2s.
我们利用上述仿真程序做过数百幅不同种类图像的相关匹配实验.
得到极肉的结果,由于篇幅的限制,本文仅给出其中一个难度较大的典型例子.
REFE童ENCES1BarneaD1.
SilvermanHE.
Adass01algorithmsfordigitalìmagere卑stration.
lEEE.
.
1972~C-21(2),119-1862KasbefBG.
Asurvey01new坦chnquesforlInBgeregtstrBtwnandmappng.
.
SFJE.
1983.
443:222-2393GoldbεrgDE.
Optìm臼田tonandMachmeLearnmg~Mas8achusetts~AddisonWesl呵.
19894DavisL.
HandbooRofGtmeiu:AIgonthms.
NewYork:VBnNostrBndRenhold,19915AnsariN,eta1.
Dynam-ic.
.
曲世幻'cùndChaotìcProgr-amming.
John百~iley&-so自.
lnc.
.
1992FASTIMAGECORRELATIVEMATCHINGBASEDONGENETICALGORITHM'ZHU泣.
ngZHAOYi-Gong(eputn田'1tofMea回国ment-contrulandEquipment,Xidiant.
;ni时四町,Xí'an.
Shaanx.
710071~Clna)AbstractTheprol七剖3才le曰mofimagec∞or盯r陀'elativema乞垃chiJ皿置E主gwass旺tudi止edhymeansofgen圣捶e立tlcεal-草gont让a让浊由h缸lmandaf.
缸as挝ti血z阻亘geε凹o恒玄r陀d沾a且艺忍白i由γ四err血nofop艺tr血Z虱E田毫u田JmI白natching.
thecomputationamountofthealgorithm胃部reducedmorethan10timescomparedwithSSDAalgorithm.
TheNPRODrr姐tchingε且自TlonεanbεemployedinthisalgorithmtoimprovethematchingprεcisionforthecaseofJowimagecontrast.
Thecomputation乞imeisnearlyconstantformatchingeachframeofimagesinthepre盹ntedal-gor-ithm.
,whichbringsconveniencp四位εpracticaJapplication.
区叼W田唱tsimagecorrelationmatching,geneticaJgorithm.
fastcomputation.
.
去Theproject四pp由全edbythePreliminaryR回国fchFoun出国nofNatlonalDefenseRece量,ved1998-09-25~t'ev咀ed1998-}2-01iis