直升机跟踪基于Matlab的模板匹配算法研究鲍文华

1283第二十八届（2012）全国直升机年会论文直升机跟踪基于Matlab的模板匹配算法研究鲍文华王方田胡学敏（73602部队，南京232100）摘要：模板匹配是一种常用的直升机跟踪算法。论文在研究目前主要的算法基础上，重点比较分析了MAD和SSDA两种算法。SSDA算法由于减少了在每个待匹配位置上的计算量和采用改进的计算方法，从而实现跟踪的快速性和准确性。Matlab由于具有丰富的图像处理函数、强大的矩阵运算能力和可视化能力，在图像处理领域中得到了广泛的应用。然后将MAD和SSDA算法在Matlab平台上进行编程和仿真实验，并对录制的图像匹配时间进行对比，仿真实验结果证明了SSDA算法的优越性。关键词：模板匹配；相似性；SSDA；仿真0引言模板匹配在近几十年来一直是人们研究的热点和难点，最早的研究是在70年代美国从事飞行器辅助导航系统等军事应用研究中提出来的。经历了10多年的发展，从80年代以后，其应用逐步从原来单纯的军事应用扩大到其它领域。国内外现阶段对图像匹配研究主要是以提高匹配的精度和速度为主，同时对匹配方法的通用性及鲁棒性也有一定要求。已研究比较多的匹配方法主要分为基于图像灰度的匹配方法和基于图像特征的匹配方法。本课题针对直升机跟踪中基于Matlab的模板匹配算法快速性、准确性的要求运用序贯相似性检测算法（SSDA），通过Matlab进行仿真计算，以实现模板匹配的快速性和准确性。1基于灰度的模板匹配算法模板匹配是指用一个较小的图像，即模板与源图像进行比较，以确定在源图像中是否存在与该模板相同或相似的区域，若该区域存在，还可确定其位置并提取该区域。这种算法利用连续图像之间的相关性，为识别目标建立了模板，而该模板的本身就包含了目标的区域信息、灰度分布信息、纹理特征等，克服了基于边缘特征匹配算法的目标特征的单一性，所以其匹配性能要好于基于边缘特征的匹配，抗干扰性能也要好于后者。基于相关的目标跟踪寻找最佳匹配点，需要一个从以前图像中得到的目标模板[4]。设目标模板T为一个MM的参考图像，搜索图S为一个NN图像)(NM，T在S上平移，模板下覆盖的那块搜索图叫做子图jiS,，),(ji为子图中心点左上角点在S中的坐标，叫参考点。比较T和jiS,的内容。若两者一致，或极其相似，则点),(ji则为所寻找的最佳匹配点。基于灰度的匹配算法是模板匹配中常用的方法，此类算法简单，无需对匹配对象进行分割和特征提取，且有通用的数学模型对匹配进行误差估计、相似程度判定。需要解决的问题是：对噪声、图像光照变化较敏感，运算速度慢，且不适应于存在旋转缩放情况的匹配对象。本节主要研究并比较几种直接基于灰度的图像匹配算法：平均绝对差算法（MAD，MeanAbsoluteDifferences），归一化积相关(NCC，NormalizedCrosscorrelation)，序贯相似性检测法(SSDA，SequentialSimilarityDetectionAlgorithm)，并结合实验分析各算法的特点。1.1MAD算法MAD算法即平均绝对差算法，是Leese最早提出来的一种匹配算法。设搜索图S为NM，模1284板图为NN，则MAD算法可定义为：MiNjjiTyjxiSMNyxd11),(),(1),((1-1)其中),(yxd为相似性度量函数在偏移量为),(yx时的匹配度量值，当),(yxd取值最小时认为),(yx是最佳匹配位置。很显然，这种方法计算过程非常简单，无需复杂的乘除法运算，但是对噪声比较敏感，在加噪声的情况下，匹配准确率随着信噪比的增加而减少。1.2NCC算法归一化积相关是一种典型的基于灰度的相关算法，其原理如下：假设待搜索图像S的尺寸为MM，模板T的尺寸为NN，NM。其中NM,代表图像象素．模板T在图像S上平移，搜索窗口所覆盖的子图记作jiS,，),(ji为子图的左上角顶点在搜索图S中的坐标。通过相关函数计算子图与实时图的灰度相关值。对搜索图自上面下、自左面右遍历搜索，记录下每一个子图位置的互相关值。互相关值最大的子图位置即为匹配位置。在实际匹配应用中，搜索图和模板的相似性是通过度量函数来度量的，则归一化积相关匹配算法可定义为：mmnnmmnnjijimmnnjijiTnmTSnmSTnmTSnmSjiR112112,,11,,),(),(),(),(),((1-2)这种方法的优点是抗白噪声干扰能力强，且在灰度变化及几何畸变不大的情况下精度很高，它的这种优点非常突出，但该方法受局部光照变化的影响，且匹配速度较慢。1.3SSDA算法传统的模板匹配算法，匹配速度较慢，在实际应用中受到限制。为了加快模板匹配速度，因此人们提出了一种快速高效的模板匹配算法——序贯相似性检测算法(SSDA，SequentialSimilarityDetectionAlgorithm)。传统模板匹配算法在每个待匹配位置上都要做2M(M为模板的大小，如图1所示)次相关计算，计算量很大。为了减少在每个待匹配位置上的计算量，人们提出了序贯相似性检测算法。序贯相似性检测算法是对传统模板匹配算法的改进，其要点如下：设模板T叠放在搜索图S上平移，模板覆盖下的那块搜索图设为子图jiS,，),(ji为这块子图的左上角像点在S图中的坐标，则i和j的取值范围为1,1MNji，如图1-3所示。(a)被搜索图(b)模板图T子图jis,MN+1M-1MMMN-1M-1(a)子图S(b)模板T图1-3模板匹配算法示意图1285（1）定义绝对误差值：|),(),(),(|),,,(,TnmTjiSnmSnmjikkjikk其中：),(jiS为模板覆盖下的搜索子图的像素平均值，T为模板位图像素平均值。),(1),(11,2nmSMjiSMmNNji（1-3）),(1112nmTMTMmNN（1-4）（2）取一个不变的阈值KT；（3）在子图中),(,nmSji随机选取像素点，计算它同T中对应点的误差值，然后把这点的差值同其他点对的差值累加起来，当累加R次误差超过KT，则停止累加，并记下累加次数R，定义SSDA的检测曲面为：kMrTRjiI21min|),(（1-5）（4）把),(jiI值最大的点定为匹配点，因为在这一点上需要很多次累加才能使总误差超过KT。如图1-4所示。kT010203040),(jiIABC图1-4累积误差增长曲线SSDA算法以随机不重复的顺序选取像素对，在用上述描述的方法进行计算时，不需要计算所有的像素，只要其总误差超过阈值KT就可以说明当前位置为非匹配位置，停止本次计算，否则进行下一位置的测试，直至找到匹配点为止。2模板匹配算法程序设计与分析本章主要在Matlab平台上实现对MAD算法和SSDA算法的编程，再通过对米-171和直-九直升机视频图像的匹配结果进行仿真分析，证明了SSDA算法的优越性。2.1MAD模板匹配算法程序设计部分MAD该程序的流程如图2-1所示。1286图2-1MAD算法流程图根据流程图的设计思路，算法实现细节如下：Ⅰ：%读取原图像(搜索图)yuantu=imread('F:\毕业设计\编程\171-1.jpg');%读取原图像Ⅱ：%获取原图像和匹配图像的尺寸[yuantu_height,yuantu_width]=size(yuantu);%获取原图象的大小尺寸，其值为[高，宽]，将原图象的高度值赋给pipei_width，将原图象的宽度值赋给yuantu_width[temp_height,temp_width]=size(temp_picture);%获取匹配图象的大小尺寸，其值为[高，宽]，将匹配图象的高度值赋给temp_height，将匹配图象的宽度值赋给temp_widthⅢ:%显示出原图imshow(yuantu);%显示原图像Ⅳ:[temp_picture,rect]=imcrop(yuantu);%图像剪裁Ⅴ:rectangle('Position',rect);%写入矩形Ⅵ:searchimage=temp_picture;Ⅶ:min=temp_height*temp_width*10;Ⅷ:tic;%计时Ⅸ:set(gcf,'pointer','watch');%算法部分:fori=1:yuantu_height-temp_height;forj=1:yuantu_width-temp_widthsearchimage=yuantu(i:i+temp_height-1,j:j+temp_width-1);he=0;form=1:temp_heightforn=1:temp_widthhe=he+abs(searchimage(m,n)-temp_picture(m,n));endend获取模板MAD匹配得到最大的匹配点（i,j）模板开始结束1287ifheminmaxheight=i;maxwidth=j;min=he;endendendset(gcf,'pointer','arrow');maxheightmaxwidthrectangle('Position',[maxwidth,maxheight,temp_width,temp_height],'EdgeColor','r');%显示红色标记匹配区域time=toc;%显示时间2.2SSDA模板匹配算法程序设计部分程序的流程图如图2-2所示。图2-2SSDA算法流程图获取模板图像获取待搜索区域图像进行相关性计算搜索完成？相关次数R累加N开始Y大于阈值T否？取R最大的匹配点（i,j）模板结束YN1288根据流程图的设计思路，算法实现细节如下：Ⅰ：%读取原图像(搜索图)yuantu=imread('F:\毕业设计\编程\171-1.jpg');%读取原图像Ⅱ：%获取原图像和匹配图像的尺寸[yuantu_height,yuantu_width]=size(yuantu);%获取原图象的大小尺寸，其值为[高，宽]，将原图象的高度值赋给pipei_width，将原图象的宽度值赋给yuantu_width；[temp_height,temp_width]=size(temp_picture);%获取匹配图象的大小尺寸，其值为[高，宽]，将匹配图象的高度值赋给temp_height，将匹配图象的宽度值赋给temp_widthⅢ:%显示出原图imshow(yuantu);%显示原图像Ⅳ:[temp_picture,rect]=imcrop(yuantu);%图像剪裁Ⅴ:rectangle('Position',rect);%写入矩形Ⅵ:searchimage=temp_picture;Ⅶ:min=temp_height*temp_width*10;Ⅷ:tic;%计时Ⅸ:set(gcf,'pointer','watch');%算法部分:forn=1:temp_heightform=1:temp_widthxiangguan=xiangguan+abs(double(yuantu(y+n-1,x+m-1))-double(temp_picture(n,m)));if(xiangguan=T)break;elseR(y,x)=R(y,x)+1;endendendendendmax=0;fory=1:(yuantu_height-temp_height)forx=1:(yuantu_width-temp_width)if(R(y,x)max)max=R(y,x);MaxY=y;MaxX=x;endend1289endset(gcf,'pointer','arrow');MaxYMaxXtime=toc3仿真实验本论文将MAD算法和SSDA算法进行了比较。仿真环境如下：采用DUOT2130处理器，512MDDR2内存，软件环境为WindowsXP3及Matlab7.0。仿真实验1：使用MAD算法和SSDA算法对录制的米-1