【《图像匹配的基本原理概述》6500字】

图像匹配的基本原理概述目录TOC\o"1-3"\h\u11501图像匹配的基本原理概述 1326841.1引言 1316131.2传统ORB特征点匹配算法 21.1引言现如今,图像匹配技术在各个领域都发挥了十分重要的作用,比如遥感[16]、运动物体检测和追踪[17]、图像拼接[18]、文本识别[19]等领域。此外，在科技前沿，比如探月工程，也采用了图像匹配的精准定位，以实现点对点的精确着陆，采用视觉导航技术，修正定位误差，就可以大幅提高着陆器的降落精度。图像匹配即根据纹理、灰度、特征、内容、结构及关系的对应关系，通过一致性和相似性的分析，在两幅或多幅图像之间识别相似影像目标的方法。图像匹配技术主要受图像描述方法的影响，图像描述就是图像信息的表示，可以将一张图像作为整体描述；也可以对其中的显著性特征进行描述。因此，图像匹配方法可以分为基于区域的匹配和基于特征的匹配。基于区域的匹配，采用局部或者整体的相似性测量，而不用检测整体图像结构。基于区域的图像匹配计算成本高昂，对图像失真敏感，外观会受噪音，光照，传感器影响，而且只适用于小的缩放，旋转或局部。基于特征的匹配，相比于传统匹配，具有更高的灵活性，鲁棒性，和广泛应用。基于特征的匹配方法通常更有效，能更好地处理几何变形。但它基于显著特征检测和描述、特征匹配和几何模型估计，这些都是具有挑战性的。一方面，在基于特征的图像匹配中，很难定义和提取现实世界三维空间中尺度、位置相同的大量特征来保证匹配性。另一方面，将N个特征点与另一幅图像中检测到的N个特征点进行匹配，这些特征通常是从高分辨率图像中提取的，点集中通常包含受控的异常值和噪声，给现有的匹配方法带来了很大的困难。虽然已经提出了各种局部描述符与检测到的特征相结合来简化匹配过程的方法，但局部外观信息的使用不可避免地会导致模糊和大量的虚假匹配，特别是对于图像质量低、内容重复、发生严重的非刚性变形和极端视点变化的图像。与此同时，信息社会对信息的要求越来越快速，从而，也提高了对匹配算法精确性、低内存以及实时性的要求，新的匹配算法也层出不穷，如前文提到的SIFT、SURF以及前文未提到的KAZE[19]等。这当中一种经典的算法就是ORB。ORB算法可以在提高匹配速度的同时，仍然保留了局部不变的特性。这之后，关于特征描述点如何进行匹配的问题，一直广受关注，各种经典算法和混合算法也依旧不断在被提出。因而，图像匹配的研究重点就是怎么样才能让图像匹配更加准确、高效、快速。1.2传统ORB特征点匹配算法ORB(OrientedFASTandRotatedBRIEF)是Rublee等人为了提升FAST(FeaturesFromAcceleratedSegmentTest)[20]检测子的效率和Harris[21]检测子的可靠性，在ICCV2011上提出的集成特征检测子和描述子的算法，这是一种将改进的o-FAST角点检测和rBRIEF特征描述子融合后的新型算法。该算法，配合FAST角点检测，用图像的灰度值作为权值的加权形心法，替检测子加上方向，同时，为了给BRIEF描述子[27]加上旋转不变性，引入了旋转矩阵。由上面的描述可知，ORB是一种基于视觉信息的算法。ORB算法融合了FAST和BRIEF分别在特征点检测和描述上的优点，使得原来的方法增加了平移不变性、旋转不变性和光照不变性。这个方法加快了提取速度，相对于SIFT、SURF，大概变快了一个数量级，甚至更多。并且，ORB描述子占用内存少，可在小型设备里使用，并满足实时性。1.1.1特征提取在FAST算子问世以前，使用的，往往都是根据自相关矩阵响应后得到的算子，如Harris角点检测子和SIFT以及SURF算子。通常，这些算法都通过灰度差的平方和来提取特征点。这种算子与卷积计算离不了关系，所以往往特征点提取因为卷积运算，它会使过程的计算量较为复杂，拖慢计算速度。2006年，EdwardRosten等[22]人提出了一种角点检测算子，FAST算法。该算法相对于SIFT、SURF等算子速度提高了一个数量级以上。ORB算法改进了FAST特征点检测不具备方向性的特点，保留了FAST算法的快速性，还引入了计算速度较快的二进制BRIEF描述子。用概念示意图1.1.1来表示整个ORB特征检测的过程：图1.1.1FAST特征点检测FAST特征点检测，其判定特征点的基本想法是，如果一个像素点与周围一定范围内的像素的灰度值相差较大，则判定此点为特征点。具体操作方法为，以要判定的像素点p为中心，取像素中心点p，以距离为固定范围3个像素单位为半径的圆，这样可以选取到十六个周围的像素点。判断条件是如果中心点的灰度值和设定阈值的和或小于中心点的灰度值和设定阈值的和，则满足条件。再设定一个固定值N，如果有连续地大于等于N个像素点满足这个条件，则此像素中心点可以被认为是特征点。一般将N定为12或9，在opencv，一个开源库中，通常将N设定为9，因为在实际操作中这样性能更好。ORB在检测的这个过程中，结合了FAST检测子和Harris检测子的优点，如，因为FAST检测子有检测准确率高，高效、速度快的优点，且在视频的拼接等实用场景中，可以快速得到结果，实时性高，所以选择FAST检测子，同时针对FAST特征检测子，优化它没有方向不变性的缺点。但是，FAST检测子还有缺点，比如，它没有尺度不变性，这导致其无法检测缩放后的图像的相对应的特征点。为了改变这一点，ORB算法在表现上添加了尺度、以及旋转的特性。它使用的方法就是构造金字塔，通过改变分辨率，得到多个分辨率的图像后，即每一层，在每一层的图像上都使用角点检测，从而就可以达到希望图像实现尺度的特性。如上所述，通常设置N为9，因为这个值在试验过程中具有更好的准确率和更快的检测速度，所以FAST检测子的阈值即为9，通常称之为FAST-9。但是，因为FAST检测子不能进行对角点的特征的描述，也不能提供这样的方法，并且它的边缘性不是很好，这样就要用到Harris角点检测的方法了，oFAST在对FAST检测子进行排序的时候，就用到了Harris的方法：1）首先，减小原来的阈值，让更多的特征点满足条件，落在这个阈值内。于是可以得到的特征点数目就会大于原来的N个；2）然后，通过Harris角点检测的排序方法，仍然得到N个特征点，当然，要选择在排序中位置最靠前的N个，最后就是如上所说的，用构建特征金字塔地方法，然后对每一层都进行角点检测，这样就可以建立尺度空间，从而得到尺度特性。oFAST相比于FAST而言，还有一个很重要的改变，就是增加了旋转不变性。通过引入描述符，再根据二进制描述符的个数画直方图，得到主方向，为FAST增加了方向特性，从而得到了旋转不变性。对此，文献中他用的是灰度重心法。具体做法为设置一个放大系数scaleFactor（通常为1.2）和金字塔的层数nLevels（通常取8）.将原图像按比例银子缩小成nLevels幅图像。缩放后的图像为：I'mpq=x,y其中，像素点(x,y)的灰度值用I(x,y)来表示。而图像的质心可以用下式来确定：C=m10m在ORB中，以关键点O为圆心，以r为半径，r代表3个像素值的圆描述所选取的区域。从这个区域中，确定x,y的值，即x,y的取值范围是[−3,3]，且在该圆形区域内。然后通过上述方法算出质心C，这样，便可以从一个向量得到一个方向向量OC，起点为几何中心O，终点为图像质心C，用向量OC的方向θ表示FAST关键的方向：θ=arctan⁡(m为了提高方法的旋转性不变，确保x和y在半径为r的圆形区域内，即x,y∈[−r,r]，r等于邻域半径，arctan表示取值区间在−π,π1.1.2特征描述ORB选择了BRIEF作为特征描述方法，属于二进制描述算法，BRIEF描述子，有描述简单、占用储存空间小、速度快的特点，这些是它的优点，但它也有缺点。为了使得图像在经过一定的旋转后仍然能够识别图像中的特征点，ORB对它进行了一些改动。BRIEF描述子选取点对的时候，是以当前特征点为原点建立的二维坐标系，这个二维坐标系的x轴就是水平方向，y轴就是垂直方向。这个二维坐标系不因图片方向的变化而改变，比如图片旋转，二维坐标系仍旧不变。从而可以以相同的取点方法取出不同的特征点，而经过计算后，得出的特征描述子也不相同，所以原始的BRIEF描述子不具有旋转不变性。而ORB算法改进了这一点，ORB在BRIEF的基础上，也采用了构建二维坐标系的方法，但是由上式(1.1.1)(1.1.2)(1.1.3)可知，ORB坐标系的x轴方向是由质心和形心的连线方向确定的，而y轴垂直于x轴。这样构造的二维坐标系，无论图像如何旋转，ORB选取的点对相对于坐标系是固定的。在不同的旋转角度下，我们以同一取点模式取出来的点是一致的。BRIEF原始算法如下：先对图像进行高斯滤波（方差为2，高斯窗口为9∗9）找到形心，先对图像进行窗口分割，将图像分为一个一个的5∗5窗口，随机取子窗口，根据里面的像素和得出比较结果，然后进行二进制赋值。（一般S=31）τp;x,y=1,ifp 其中，p(x)，p(y)，为通过高斯平滑，然后点x=(u,v)T的灰度值,分别取x=(u1,v1)，y=(u2,v2)所在5∗5子窗口的像素和。通过固定的、可重复的方法对匹配点对进行选择，最后可以得到一个点对集nd(x,y)，它必须是一对相对位置明确的点对。原文献中随机选取了128对点，使用图1.1.2五种选取随机点对的方法至于失配的标准，对这种描述子，文献通过设置一个阈值，如果是两个点的描述子，即一个描述子点对的汉明距离小于阈值的情况，则认为这两个描述子对应的特征点是匹配的，反之，则失配。如果计算机有SSE4.2指令集，一般现在的新的CPU架构都会有，则在计算汉明距离时能够计算得更加快速。从图像中的大窗口中，选N对小的窗口，重复步骤二，得到汉明距离，通过二进制位描述，这样得到的汉明距离其实就是特征点的描述子。（一般N=256）fnp= 其中，n一般选择128，256或512。位数不同，二进制编码的描述子对图像的描述就会有不同的能力，从而我们就可从不同的需求出发，有侧重地进行选择，如选择速度、选择效率或选择识别准确率。规定1字节=8位。从而BRIEF就有16、32和64，这三种不同的表示方法。SURF的描述子使用float类型表示的，它的每一维都是4个字节，而它有64个维度，因此4*64=256，SURF就有256个字节。由此可计算得，BRIEF最多是SURF的1/4，它所需的储存空间大大小于SURF，降低了计算机内存的占用率。BRIEF算法完成后，每一个特征点，（取n=256）都得到了256bit的二进制编码。从而，可以用向量，由0、1的二进制编码组成，来表示想要描述的角点。BRIEF算法的精彩之处在于BRIEF算子的n(x,y)二进制测试点对集，设图像区域p的邻域，p为中心点，点对(x,y)遵循高斯分布的定理：x,y~Gaussian0,1通过实践经验可知，当方差σ=15S时，BRIEF算子对各个特征点的区分性最好。BRIEF描述子，计算过程高效，快速，也十分方便简单。这个描述子也拥有视角变换、光照变化的鲁棒性，这一点和SIFT相同。然而，它没有旋转的鲁棒性，没有图像尺度金字塔，（SIFT的尺度空间，采用了下采样的方法，得到高斯金字塔，如图1.1.图1.1.3高斯金字塔尺度空间图1.1.4高斯金字塔构建过程因此，ORB也对原始的BRIEF进行了改进，使得特征描述部分的能力得到了提升，使其具有旋转不变性。ORB选择使用32维的BRIEF，有256位，并且对图像进行预处理，用积分的方式，对图像开展平滑处理。首先，用矩阵的形式，来对点集进行描述，从而可以给BRIEF一个入方向的描述。给每个nbit的测试点集xi,yi，定义一个2×n的矩阵S，如公式（S=x1x然后，求出θ，θ表示前文中提到的方向，从FAST中可以获得，可以从θ得到它相应的矩阵RA，测试点集Sθ=gnp,θ≔图1.1.5原始BRIEF方法，图像未旋转前坐标系与点的位置关系图1.1.6原始BRIEF方法，图像旋转后坐标系与点的位置关系图1.1.7ORB改进BRIEF后，图像未旋转时的坐标系与点的位置关系图1.1.8ORB改进BRIEF后，图像旋转后的坐标系与点的位置关系图1.1.5和图1.1.6表示的是未加入方向特征之前坐标系与点的位置关系，BRIEF设置的坐标系相对于点是不固定的，因此之后的描述子描述的对象就不同，从而可以更直接地看明白BRIEF不具备旋转不变性的原因。加入方向特征之后，如图1.1.7和图1.1.8所示，由OC表示x轴方向，则使得坐标系与点的相对位置是固定的，最后尽管是旋转后得出的描述子，也与未旋转前一样。但是，引入旋转不变性后，ORB的检测算法，相对于原始BRIEF算法而言，可区分性变差了，具体如图1.1.9所示，可以明显看出旋转后的BRIEF描述子的均值在各个区域都有，方差分布混淆，难以区分。图1.1.9不同特征向量均值为了使steeredBRIEF能更好地识别、区分各个特征点，从而形成更优的描述子。在方差和二进制串均值的选取上要格外注意。因为均值接近于0.5，方差更大的时候，上述性能更好，因此我们尽量在方差和均值的选择上注意这一点。ORB在测试点集上，以一个31×31像素的图像块作为选定的区域，这一点与原始BRIEF有差异。每一个5×5的子窗口就是要测试的区域，而原始的BRIEF是直接选取像素点作为要测试的点，ORB中的这种选择方法，就可以避免原始BRIEF受噪声影响较大的问题。1.1.3特征匹配过去几十年的图像匹配方法大致可以分为两类，一类是基于区域的匹配，另一类是基于特征的匹配。基于区域的匹配特指密集匹配，也叫图像配准，这种通常不检测特征。而基于特征的匹配，它们的特征点和它们的局部描述子是从图像对中提取出来的，从而图像匹配可以转化为对特征点的匹配，可以分为间接匹配和直接匹配，分别对应于用描述子和不用描述子。直接特征匹配，通过直接用空间几何关系和优化方法建立联系，可以粗分为图匹配和点集配准。与之相比，间接特征匹配将匹配视为一个两阶段问题。一般先从度量空间里判断的距离相似性建立初步对应。这样，就可以通过额外局部或全局几何约束从假设匹配集中去除错误匹配。稀疏特征对应的密集匹配经常需要转换模型估计的后续处理，比如图像重采样和插值（扭曲）。ORB得到描述子后，为了更好的匹配效果仍要从中进行选择，尽量选择高方差，高不相关性的点集，详细操作过程如下所示：进行τ统计，可以根据描述二进制串的值来进行计算。由从步骤1中得到的编码的平均值，并根据均值为0.5的偏差值来对各个窗口得到的值进行排序，储存由这些二进制编码得到的数据，放到容器T中。用贪婪算法来匹配：移出容器T中的顶层的第一个数据，将这个得到的结果存入容器R中。接着，比较容器T的后面的一个数据和R里的所有结果，判断这两个容器内数据的相关性。具体做法为，设置一个阈值，如果比较结果大于这个阈值，那么就可以舍弃掉这个描述串，因为它有冗余的信息；反之，结果容器R再添加一个数据。重复①=2\*GB3②步骤，等到容器R中有了256个结果，达到目的，就可以停止循环。但是，如果循环次数都完了，仍然没有满256个结