一种改进的高精度视频帧间匹配算法

1、引言

　　图像匹配技术是数字图像处理领域的一项重要研究，并已在计算机视觉、虚拟现实场景生成、航空航天遥感测量、医学影像分析、光学和雷达跟踪、景物制导等领域得到了广泛的应用。它涉及到许多相关领域，如图像预处理、图像采样、图像分割、特征提取等，并且将计算机视觉、多维信号和数值计算方法等紧密结合在一起。因此，如何找到一种有效的图像匹配方法，使得它能快速而准确的从大量信息中找出所需图像信息成为急待需要解决的问题。

　　特征法[1]是图像匹配算法中的一种经典方法，其原理是选取图像中的典型特征作为运动估计的基本单元，这种方法比较接近于人的视觉特性，主要受制于特征提取的稳定性和特征定位的精确性。而SIFT (scale in-variant feature transform)特征[2,3]是一种对尺度、旋转、亮度、仿射、噪音等都具有不变性的图像局部特征。所以，本文针对视频帧间匹配的要求，结合SIFT特征对尺度和旋转具有不变性的优点，将欧式距离判别和RANSAC法融合到对SIFT特征点的匹配计算中，通过研究得到了一种高精度的视频帧间匹配算法。

2、基于SIFT特征的视频帧间匹配

　　在需要处理的视频帧间图像中，普遍地存在旋转和尺度缩放，而常用的Harris角点[4] 和K-L角点[5]不适用于这种场合。SIFT特征是分别在两帧图像的高斯差分尺度空间（DOG scale-space）提取出的图像局部特征，以某段在直升机上拍摄的航拍视频为例，对视频中某两帧图像的SIFT特征点进行匹配，仿真结果如图1所示。

                            
              图1 视频中某两帧图像的SIFT特征匹配结果

　　仿真结果表明，SIFT特征不仅具有对旋转、尺度缩放、亮度变化的不变性，而且对视角变化、仿射变换、噪声也具有一定程度的稳定性。由于该算法不以单个像素作为研究对象，所以提高了对图像局部变形的适应能力。

　　但是在传统的仅采用欧式距离判别法对特征点进行匹配的过程中，仍旧存在误匹配问题。图2是将相邻两帧图像中提取的特征点在同一帧图像中显示，可以根据性质将误匹配点分为两类：第一类是完全匹配错误的点，如图2方框（a）所示，即被配对的两帧图像上的两个点实际上不是一对具有匹配关系的点，他们具有相同或极其相似的SIFT特征向量，但他们并不是同一个图像特征；第二类是有误差的匹配点，如图2方框（b）所示，即两个点虽然是同一个图像特征，但是由于镜头的晃动，图像的局部运动及其他扰动的影响，同一个点在两帧图像中的坐标差异与其他大部分点的坐标差异相比，存在较大的偏差。这两种情况都会影响到运动参数估计的准确度，因此都是需要被去除的误匹配点。

                             图2 欧式距离法判别匹配点

　　实验表明，利用欧式距离进行关键点匹配的匹配精度基本取决于比例阈值r 的大小，r 取值过大会出现大量错匹配点，而r取值过小可能得到的匹配点数目过少。然而存在这样的情况，即如果两帧图像上的某两个不同的特征点的特征向量的欧式距离值非常小，则阈值r 需要取足够小的值才有可能去掉这一对错误的匹配点，这样一来匹配点总数目就太少甚至为零，甚至无法进行后面的参数计算。故单纯靠调节欧式距离匹配中的比例阈值r无法解决上述误配点问题，难以达到高精度、数目适中的特征点匹配结果。

3、匹配准则的改进

　　RANSAC法和传统的方法的区别在于传统的方法先把全部的数据点作为内点而计算出初始参数值，然后重新计算并统计内点和外点；而RANSAC法最开始是利用一部分数据作为内点得到初始值，然后寻找数据集中所有别的内点。即应用RANSAC法对欧式距离法粗匹配的特征点进行准确度检验，可以最大限度地减少噪声及外点的影响。所以，本文首先采用关键点特征向量的欧式距离判定视频中某两帧图像的特征点相似性，进行粗略匹配，然后利用RANSAC法对粗略匹配结果进行迭代演算[7,8]，通过二次精确匹配来剔除粗匹配中的误配点，得到精确的匹配点，从而得到精确的图像匹配结果。

3.1 欧式距离判别法的一次粗匹配

　　当两帧图像的SIFT特征向量生成后，首先采用关键点特征向量的欧式距离作为两帧图像中关键点的相似性判定度量。欧氏距离（Euclidean distance）是一个通常采用的距离定义，它是在n维空间中两个点之间的真实距离。

　　计算两帧图像中特征点的欧式距离的公式是：

                                       （1）
 
　　Xi1表示第一帧图像上某一点的第i 维坐标，Xi2表示第二帧图像上某一点的第i 维坐标。
 
　　判断准则：取图像1中的某个关键点，计算出图像2中与其欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离d1除以次近的距离d2少于某个比例阈值r ，则接受这一对匹配点，否则抛弃。

3.2 RANSAC法的二次精确匹配

　　RANSAC(Random Sampling Consensus) 法[6]的基本思想是在进行参数估计时，不是不加区分地对待所有可用的输入数据，而是首先针对具体问题设计出一个目标函数，然后迭代地估计该函数的参数值，利用这些初始参数值把所有的数据分为所谓的“内点”（Inliers, 即满足估计参数的点）和“外点”（Outliers，即不满足估计参数的点），最后反过来用所有的“内点” 重新计算和估计函数的参数。

　　本文中的全局运动包括尺度变换、旋转变换和平移变换。如果用X 和Y 表示一帧图像中任意一个特征点的位置坐标，x 和y 表示另一帧图像中任意一个特征点的位置坐标，L 表示这两帧图像之间的尺度变换，θ表示旋转变换， a 和b 表示平移变换。那么，计算全局运动参数可以用相似变换表示如下： （2）

　　在两帧图像的粗匹配点中选出8 对，利用它们的坐标信息，组成一个方程组，计算出运动参数，利用参数把第二帧图像中所有的点都变换到第一帧图像上，反变换后的点坐标用X’,Y’表示，则：

                                 （3）
 
　　判断准则：如果某一点变换到第一帧图像上能和它在第一帧图像上的对应点重合或者基本重合（位移值小于1象素），即：

                     （4）
 
　　那它们就是该变换确定的一对对应点。若对应点的个数占区域中全部点个数的比例达到一定的阈值（人工选定），那就认为这组变换关系是可接受的。利用经该变换确定的所有对应点即内点以最小二乘的方法去重新求解运动参数，至此匹配点检验结束，不再向下计算。若对应点比例不能达到要求，则重新选择一组点，再去计算它们所对应的运动参数。如果对于每一组求出的运动参数，对应点的比例都达不到设定的阈值，则判定这两帧图之间不存在匹配关系。

4、实验结果及分析

　　在实验中，视频图像大小为884×662，视频帧率为25fps，计算机配置为AMD Athlon(tm) 64×2 Dual Core Processor 5000+，内存2.00GB。图3为欧式距离判别法的一次粗匹配得到的匹配点，其中（a）、（b）分别为在两帧图像中得到的匹配点，（c）表示特征点在两帧图像中的点位移，可以看出，绝大多数点位移是微小的，故（c）中的长线表示点位移值较大，证明该匹配点为误配点。

                   （a）　　　　（b） 　　　（c）
                 图3 欧式距离判别法的一次粗匹配结果

　　图4为经过RANSAC法的二次精确匹配得到的匹配结果，由4（c）可得，经过二次匹配，去掉了一次粗匹配中错配的点和由于局部运动造成的有误差的匹配点，得到了完全正确的匹配结果。表1 给出了用传统欧式距离判别算法和本文的欧式距离—RANSAKC二次匹配法对视频帧间图像进行SIFT特征匹配所得结果。

                       （a） 　　　（b） 　　　（c）
           图4 经过RANSAC法二次匹配检验得到的匹配结果
 
表1 欧式距离法和RANSAC二次匹配法的视频帧间图像特征匹配结果比较

          
　　经过对该段视频430帧图像的处理，得出单纯采用欧式距离匹配算法得到的平均正确匹配率为96.2%，平均峰值信噪比为21.8541dB，其中单次正确匹配率100%的帧数为8帧，而本文所用的欧式距离-RANSAC两次匹配法的平均正确匹配率为98.8%，平均峰值信噪比为31.2271dB，单次正确匹配率100%的帧数为349帧，有效地减少了误配点数，根据峰值信噪比（PSNR）值可以看出视频帧间图像的匹配精度得到了显著提高。

5、结论

　　本文研究了视频帧间图像特征的提取和匹配问题，采用关键点SIFT特征向量的欧式距离判定视频中某两帧图像的特征点相似性进行粗略匹配，通过采用RANSAC法的二次精确匹配算法最大限度地减少噪声及外点的影响，从而解决粗匹配中的误匹配点问题。仿真试验表明，该算法能够有效地解决仅采用欧式距离判别法进行匹配时的误匹配问题，显著地提高视频帧间图像的匹配精度，同时仿真试验还显示出该算法具有较强的鲁棒性。