基于特征点的图像匹配技术研究与应用

基于特征点的图像匹配技术研究及应用文献综述1.图像匹配的概念图像匹配[1]是指通过一定的匹配算法在两幅或多幅图像之间识别同名点，如二维图像匹配中通过比较目标区和搜索区中相同大小的窗口的相关系数，取搜索区中相关系数最大所对应的窗口中心点作为同名点。其实质是在基元相似性的条件下，运用匹配准则的最佳搜索问题。图像匹配中事先获得的图像称为基准图像（baseimage），在匹配过程中在线或者实时获得的图像称为实时图像（realtimeimage）。基准图像可以比实时图像大也可以比实时图像小。当基准图像比实时图像大时，匹配过程就是在基准图像中搜寻实时图像位置的过程；当实时图像比基准图像大时，匹配过程就是在实时图像中寻找作为目标的基准图像的过程。在地图导航系统[2]中，基准图像比实时图像大。如图1.1所示。基准图像实时图像待匹配区域dxdy搜索区域M1N1N2M2图1.1地图导航系统中的图像匹配示意图基准图像和实时图像是对同一对象有差别的近似描述，设𝑓𝑏(𝑥,𝑦)和𝑓𝑟(𝑥,𝑦)分别为基准图像和实时图像的灰度分布，在不考虑关照变换等影响下，两者存在如下关系：𝑓𝑟(𝑥,𝑦)=𝑓𝑏[𝑥+𝑑𝑥(𝑥,𝑦),𝑦+𝑑𝑦(𝑥,𝑦)]+𝑛(𝑥,𝑦)公式1.1其中𝑛(𝑥,𝑦)是高斯白噪声，可以通过一定的滤波方法滤除。𝑑𝑥(𝑥,𝑦),𝑑𝑦(𝑥,𝑦)是𝑓𝑟(𝑥,𝑦)上的点在X和Y方向上的位置偏差，称为定位噪声。位置偏差往往是因为图像的几何形变造成的。实际上利用计算机进行处理的并不是连续图像，图像的位置和灰度都被划分为离散的值，常用像素矩阵来表示一副图像。在地图匹配导航中，通常基准图像比实时图像大。直接进行相关匹配的两幅图像应该是大小一样的，为了确定实时图像在基准图像中的位置，就必须在基准图像中提出与实时图像大小相等的基准子图，并逐个与实时图像进行比较，以便找出与实时图像匹配的那个基本子图，从而确定实时图像在基准图像中的位置。所以一般图像匹配的过程就是不断从基准图像中提取基准子图与实时图像进行相关运算的过程，这个过程可以是线性遍历式的，也可以是非线性随机的搜索过程。在本课题中，我们选取左上角为原点作为坐标基准。如图1.1所示，大方框为基准图像，小方框代表实时图像，虚线方框内事待选的实验匹配位置区域，也就是进行匹配的搜索区域。如果顺序匹配（即试验所有的搜索区域）的话，易知总共有(𝑀1−𝑀2+1)×(𝑁1−𝑁2+1)个试验位置，其中只有一个是我们要找的匹配位置，即实时图像坐标原点在基准图像中的坐标：(𝑥∗,𝑦∗)，称为匹配点。2.图像匹配的方法[3]图像匹配的方法有很多，由已知模式，也就是模板图（如实时图像，到另一幅图像（如基准图）中搜索相匹配的子图像的过程，称为模板匹配。一般地，图像的模板匹配分为两大类：基于灰度值的方法和基于特征提取的方法。2.1灰度匹配灰度匹配的基本思想:以统计的观点将图像看成是二维信号，采用统计相关的方法寻找信号间的相关匹配。利用两个信号的相关函数，评价它们的相似性以确定同名点。灰度匹配通过利用某种相似性度量，如相关函数、协方差函数、差平方和、差绝对值和等测度极值，判定两幅图像中的对应关系。2.1.1ABS算法[4]最基本的灰度匹配方法为ABS(AbsoluteBalanceSearch)算法，它用模板图像和待匹配图像上的搜索窗口间的像素灰度值的差别来表示两者的相关性。这个差别值有三种计算方法：𝑀𝐴𝐷(𝑚,𝑛)=1𝑀𝑁∑|𝑓1(𝑥,𝑦)−𝑓2(𝑥+𝑚,𝑦+𝑛)|𝑥,𝑦公式2.1𝑆𝐴𝐷(𝑚,𝑛)=∑|𝑓1(𝑥,𝑦)−𝑓2(𝑥+𝑚,𝑦+𝑛)|𝑥,𝑦公式2.2𝑆𝑆𝐷(𝑚,𝑛)=∑|𝑓1(𝑥,𝑦)−𝑓2(𝑥+𝑚,𝑦+𝑛)|2𝑥,𝑦公式2.3其中MAD为平均绝对误差(MeanofAbsoluteDifferences)，SAD为绝对误差和(SumofAbsoluteDifferences)，SSD为平方误差和(SumofsquaredDifferences)，匹配时选择最大值处的(𝑚,𝑛)为匹配点。这种方法简单，但一旦图像灰度值发生线性变换，就无所适从了；而且不同的基准图像阈值也各不相同，很难事先确定，误匹配率较高。这种方法只能用于模板图像是基准图像中一部分的情况。2.1.2归一化互相关算法归一化互相关(NormalizedCorrelation)匹配算法是对ABS算法的改进，其基本原理是逐像素的把一个以一定大小的实时图像窗口的灰度矩阵，与参考图像的所有可能的窗口灰度阵列，计算互相关值，按互相关值的最大值来确定匹配位置，从理论上说就是采用图像相关技术。这种方法对图像灰度值的线性变换具有“免疫性”，不受灰度值的线性变换的影响。但这种方法在每一个像素点上都要计算互相关值，计算量太大，实际应用很难，只能作为理论分析。2.1.3幅度排序相关算法[2]其主要思想为：首先把模板图像中德所有灰度值按幅度大小排成列的形式，然后对它进行二进制编码，最后根据二进制排序的结果，把模板图像转化为二进制阵列的一个有序组合；然后顺序地将这些二进制排列与实时图像进行由粗到细的相关计算，直到确定出匹配点位置。以3×3模板为例，如图2.1所示，对模板中的数值按照二进制大小编码，若为奇数，则中间不编码。图2.1幅度排序预处理由图2.1中的①、②、③三列及其在模板图像中的位置，可以构成如图2.2所示的C1、C2、C3三个二进制阵列。这样匹配过程中，从左向右可以实现由粗到细的相关匹配。图2.2二进制阵列2.1.3序列相似性检测算法[5]序列相似性检测算法(SequentialSimilarityDetectionAlgorithms,SSDA)是一种快速的模板匹配算法，它是1972年Bamea和Silverman首先提出来的。该算法能很快丢弃不匹配的点，减少花在不匹配点上的计算量，从而提高匹配速度，算法比较简单，易于实现。SSDA是对公式2.1所示MAD算法的一种优化，MAD在计算时，要顺序地在匹配检测区域内计算有关各个(𝑥,𝑦)的差别值，然后找出最小值。而在SSDA中只计算局部匹配值，而不是每次匹配时都计算出模板图像中全部像素灰度绝对值，这样就可以大大节省计算量。SSDA计算时：a．定义绝对误差：𝜀=|𝑓(𝑖,𝑗)−𝑓̂(𝑖,𝑗)−𝑇(𝑖,𝑗)+𝑇̂(𝑖,𝑗)|公式2.4其中𝑓(𝑖,𝑗)为基准图像，𝑇(𝑖,𝑗)为模板图像，𝑓̂(𝑖,𝑗)=1𝑀𝑁∑∑𝑓(𝑖,𝑗)𝑁𝑗=1𝑀𝑖=1b．取阈值T；c．在𝑓(𝑖,𝑗)中随机选取像素点，计算它同𝑇(𝑖,𝑗)对应点的误差值，然后把误差求和，当累积到r次后误差超过固定阈值T，停止累加，记录上次数r，定义SSDA检测曲面：𝐼(𝑖,𝑗)={𝑟|min1≤𝑟≤𝑁∗𝑀[𝜀𝑇]|}公式2.5d．把𝐼(𝑖,𝑗)值最大的(𝑖,𝑗)点作为匹配点，因为这点上需要很多次累加才能使总误差超过T。图2.3给出了三条不同的误差积累曲线，其中A，B不是匹配点。图2.3固定门限T误差积累曲线2004年米长伟等人改进了SSDA，使门限T变为平行于图2.3中C的自适应值；并且把匹配过程分为粗匹配和精匹配两步，大大简化了计算量[6]。2009年胡凯等人把改进的SSDA用并行化实现，进一步降低了时间开销[7]。综上所述，利用灰度信息匹配方法的主要缺陷是计算量大，对各种图像的变换较为敏感（如光照变化、角度旋转等），所以这些方法较少被用于实际。2.2特征匹配特征匹配是指通过分别提取两个或多个图像的特征（点、线、面等特征），对特征进行参数描述，然后运用所描述的参数来进行匹配的一种算法[1]。基于特征的匹配所处理的图像一般包含的特征有颜色特征、纹理特征、形状特征、空间位置特征等。特征匹配首先对图像进行预处理来提取其高层次的特征，然后建立两幅图像之间特征的匹配对应关系，通常使用的特征基元有点特征、边缘特征和区域特征。特征匹配需要用到许多诸如矩阵的运算、梯度的求解、还有傅立叶变换和Taylor展开等数学运算。基于图像特征的匹配方法可以克服利用图像灰度信息进行匹配的缺点，由于图像的特征点比较像素点要少很多，大大减少了匹配过程的计算量；同时，特征点的匹配度量值对位置的变化比较敏感，可以大大提高匹配的精确程度；而且，特征点的提取过程可以减少噪声的影响，对灰度变化，图像形变以及遮挡等都有较好的适应能力。所以基于图像特征的匹配在实际中的应用越来越广泛。所使用的特征基元有点特征(明显点，角点，边缘点，高曲率点等)，边缘轮廓等。由于图像的边缘提取比较困难，而且其定位不好界定，故现在特征匹配中使用最多是特征点的匹配。它有以下优点[8]：1）图像的特征点比图像的像素点要少很多，从而大大减少了匹配的计算量；2）特征点的相似度量值对位置变化比较敏感，可以大大提高匹配的精度；3）特征点的提取过程可以减少噪声的影响，对灰度变化、图像形变以及遮挡等都有较好的适应能力；4）匹配后的特征点坐标可以直接用来估计图像之间的空间变换关系。因此，基于特征点的图像匹配方法是实现高精度、快速有效和适用性广的匹配算法比较好的选择3.基于特征点的图像匹配研究现状特征点是图像灰度在x和y轴方向上都有很大变化的一类局部点特征。它包含角点、拐点以及T-交叉点等，其中主要应用的是图像的角点。角点是图像的一种重要局部特征，他在图像匹配、目标描述与识别以及运动估计、目标跟踪等领域具有十分重要的作用。它是图像上灰度变换剧烈且和周围的邻点有显著差异的像素点。如图3.1所示，有L型、T型、X型和Y型等。图3.1角点示例图3.2Harris角点检测结果3.1角点检测角点检测的算法有很多，对不同类型的角点检测效果也有差异。目前角点检测算法主要分为两大类：一类是基于边缘图像的角点检测算法，这类算法需要对图像边缘惊醒编码，很大程度上依赖于图像的分割和边缘提取，而图像的分割和边缘提取本身具有相当大的难度和计算量，况且一旦边缘线发生中断，对角点的提取结果影响较大，所以这类算法有一定的局限性；第二类是基于图像灰度的角点检测，避开了上述的缺陷，直接考虑像素点领域的灰度变化，而不是整个目标的角点检测，这类算法主要通过计算曲率及梯度来达到检测监角点的目的。3.1.1Moravec角点检测算子[9]该方法的计算过程为：计算四个方向上的局部自相关，，选取最小值作为对应像素点的角点响应函数，对这个响应取门限，超过门限的为特征点。设图像灰度函数为I，在一定窗口上的灰度变化函数定义如下：𝐸𝑥,𝑦=∑𝑊𝑢,𝑣[𝐼(𝑢+𝑥,𝑣+𝑦)−𝐼(𝑣,𝑣)]2𝑢,𝑣公式3.1其中𝑊𝑢,𝑣表示当前图像窗口。Moravec算法响应时各项异性的，而且由于响应值是自相关的最小值，而不是自相关的差值，所以Moravec算法对强边界敏感，实现简单快速。3.1.2Harris角点检测算子[10]Harris使用自相关矩阵A改进了Moravec的方法。这种方法避免了使用离散的方向和偏移，它在窗口内使用高斯函数加权导数，取代了简单的求和。如果自相关矩阵A有两个大的特征值就表示该点为检测到的特征点。图3.3为Harris角点检测的示意图。在平滑区域窗口沿着各个方向移动均无灰度变化；边缘区域沿着边缘方向移动无灰度变化；角点区域沿着各个方向移动都有灰度变化。a.平滑区域b.边缘区域c.角点图3.3角点检测示意图将图像窗口平移[u,v]产生的灰度变化定义为：2,),(),(),(),(yxIvyuxIyxwvuEyx公式3.2对图像灰度函数Taylor展开：),(),(),(22vuOvIuIyxIvyuxIyx去掉高阶小量，得：22,),(,,),(yyxyxxyxIIIIIIyxwMvuMvuvuE公式3.3对于实对称矩阵