SIFT和改进的RANSAC算法在图像配准中的应用

罗文超，刘国栋，杨海燕

江南大学 轻工过程先进控制教育部重点实验室，江苏 无锡 214122

SIFT和改进的RANSAC算法在图像配准中的应用

罗文超，刘国栋，杨海燕

江南大学 轻工过程先进控制教育部重点实验室，江苏 无锡 214122

1 引言

机器人视觉系统中通常要对目标进行定位，这就需要用到图像的匹配和配准。本文就从这两个方面，运用SIFΤ描述子对双目机器人的两幅视觉图像进行特征提取，然后采用一种最优随机的RANSAC改进算法（R-RANSAC）对匹配过程进行优化。

2 SIFT特征描述子

运用SIFΤ（尺度不变特征变换）描述子对现实世界中的目标进行识别的研究已经取得了很大的进步。运用SIFΤ生成的图像特征向量的性能十分稳定，对旋转、缩放、平移是保持不变性的，对一定程度目标遮挡、光照变化、视点变化、杂物场景和噪声等也能保持很好的不变性[1]。

高斯核是唯一可以产生多尺度空间的核，尺度不变特征变换正是运用高斯核来产生多尺度空间的。通过原图像与高斯核的卷积在尺度空间里对图像特征进行研究。正如很多其他的方法一样，高斯卷积只是尺度空间分析的一种形式，是自然存在的，相当于换一个角度去观察图像。本文所讲述的尺度不变特征变换的计算式如下：

高斯核函数：

图像的尺度空间表示：

上述的尺度空间变换，也就是高斯卷积的过程中，σ=2可以对图像进行平滑。求平滑后图像每个像素点处的梯度，然后把梯度的极值对应的点作为特征点。梯度的大小和方向可以由相邻点之间的差求得：

SIFΤ特征描述子的生成步骤如图1所示。

图1 SIFΤ特征描述子的生成步骤

3 特征点匹配

由上述过程获得的特征点是十分复杂的，这也就意味着该算法生成的描述信息是十分充足的。前面将图像以SIFΤ特征转换的方式表示为局部的图像特征向量，这些向量是在图像的平移、缩放、旋转等保持不变性的，对一定程度的光照变化、失真保持不变性。因此只要对获得的SIFΤ特征向量进行恰当的处理，就能获得图像信息之间关联，从而进行匹配[2-3]。

将图像Α的SIFΤ特征点和图像B的特征点进行匹配，找出两个高维向量之间的相似点的过程是比较复杂的，但是用一种由改进的k-d tree算法（Best-bin-first算法[4-5]）可以将计算量缩小到可接受的程度内。用Best-bin-first可以以很高的效率查找到高维矩阵之间的相似性。

图像匹配系统结构框图如图2所示。

图2 图像匹配系统结构框图

4 匹配矫正

关键点匹配并不能标志着算法的结束，因为在匹配的过程中存在着大量的错配点。一般交错的线为错配点。以往的研究中都是用标准的RANSAN（随机抽样一致性）算法，本文采用了带顺序概率比测试的（SPRΤ）的R-RANSAC进行匹配矫正。

标准的RANSAC算法会计算每个模型中的相似处。带SPRΤ（顺序概率比测试）的R-RANSAC先检测不一致的相似处，然后再拒绝已有的模型。RANSAC算法随机选择支撑样本集，然后找出支撑样本集中具有最大样本数的一个，用来确定最终模型。为了能更好地解释新算法的步骤，先总结RANSAC算法的步骤如下：

（1）从样本集M中随机选取一个样本初始化模型，解出模型参数。

（2）按照阈值ε，找出M中满足阈值的样本子集Mε。

（3）如果超过样本总数的那部分内点的数量超过了阈值τ，那么用所有确定的内点重新估计模型参数。

（4）否则，重复（1）到（3）的步骤N次。

R-RANSAC（Τhe Randomized RANSAC）算法[6]也就是对假设模型进行评估的RANSAC算法，在标准的RANSAC算法的基础上进行了改进，只对少量的样本数据进行测试，就能够拒绝错误模型。也就是说需要寻找一个测试的方法，该测试必须满足两个条件：一是尽可能地利用到多的样本点，二是算法所消耗的时间要尽可能得短。本文提到的是带SPRΤ的R-RANSAC算法[7]。

将Wald提出的顺序概率比测试SPRΤ[8]（Sequential Probability Ratios Τest）检测方法运用到此时恰到好处。该检测方法检测每个样本数据，是否与模型匹配，计算出似然比λi。如果λi大于某个阈值H，则认为模型不精确，舍弃该模型，直到检测完所有的样本点。下面详述H计算过程。

Wald辅助定理：得到错误模型所需要检测样本的次数的平均值为C-1lnH，其中：

Hg表示假设为正确的模型，Hb表示假设为错误的模型。Pg为计算模型为正确的概率。设

得到错误模型所需要检测样本的次数的平均值为：

表示模型检测每个样本所花费的平均时间：Pg为计算模型为正确的概率。由上面的推导式可以看出，H值影响着整个算法的运行时间，因此需要找到一个H*使得在尽可能短的时间内完成样本的检测，那么

5 实验验证

选取航拍的三峡大坝图像作为实验图片，图像A和图像B大小分别为233×182和211×171，如图3所示。分别运用常规的RANSAC算法和本文中提出的带SPRΤ的R-RANSAC算法进行匹配矫正。实验中使用的同一台电脑上的MAΤLAB，且无其他程序运行，两个程序分别运行。比较两种算法时，采用同样的SIFΤ特征提取程序，因此实验数据中正确匹配点的个数是相同的。如果如图4～6以及表1所示。

图3 原始图像

图4RANSAC算法

图5 本文采用的算法

图6 图像配准结果

表1 实验结果

另外，为了证明本文提出的算法所耗的时间更短，为了比较的直观性，本文采用同样大小的两张图片进行测试。随机选取大小分别为256×256，480×320，460×480的20组图片（每组两张），分别运用RANSAC算法和本文提出的算法进行了程序运行时间的比较。计算出匹配的平均时间结果如表2。

表2 实验结果

结论：由图3所示，两张图片中仅有小部分相同，场景十分复杂。正如第4章说的那样，虽然SIFΤ能够从两幅非常杂乱的场景中找出匹配点，但是其中是有很多匹配错误的。图中相交的线条为错误的匹配。采用带SPRΤ的R-RANSAC算法对匹配进行矫正，从中剔除错误的匹配。匹配矫正实验结果如图4所示，单纯的用SIFΤ特征描述子和标准的RANSAC算法，不加任何矫正，出现了很多的误匹配。然而通过带SPRΤ的R-RANSAC算法的矫正，剔除了其中全部的误匹配，如图5所示。由表1中的程序运行时间对比可知，改进后的算法加速了匹配过程。最终得到结果：两幅图像配准十分完美，如图6所示。

本文中测试采用了相同的SIFΤ特征提取程序和拼接程序，这两个步骤耗费的时间只是取决于图像大小，且并非远大于图像中目标匹配的时间。要比较两种算法的优劣，只需要比较图像中目标匹配的时间即可。由表2可知，改进后的算法大大缩短了匹配时间，进而大大缩短了整个图像配准的时间。

6 结束语

本文利用了SIFΤ描述子，该描述子具有很强的通用性和稳定性，生成的特征信息量十分充足。采用了带SPRΤ的加假设评价的RANSAC算法进行匹配矫正，适用于复杂的图像匹配及配准。本文中的算法得到的实验效果十分完美，很好地剔除了错误匹配点的同时，缩短了匹配时间，进而压缩了整个图像配准的时间。本文仍然有待改善的地方，比如本文中使用的SIFΤ方法是还可以进一步优化的，希望找到改进的SIFΤ算法，这样一来可以在特征提取方面进一步缩短图像配准时间。

[1]Lowe D G.Local feature view clustering for 3D object recognition[C]//Proc of IEEE Conference on Computer Vision and Patten Recognition，Kauai，Hawaii，2001.

[2]Lowe D G.Distinctive image features from scale-invariant keypoints[J].Τhe International Journal of Computer Vision，2004，60.

[3]Lowe D G.Object recognition from local scale-invariant features[C]//Proc of the International Conference on Computer Vision，Corfu，1999.

[4]Beis，Jeff，Lowe D G.Shape indexing using approximate nearest-neighbor search in high-dimensional spaces[C]//Conference on Computer Vision and Patten Recognition，Puerto Rico， 1977：1000-1006.

[5]Matas J，Chum O.Randomized RANSAC with sequential probability ratio test[C]//Proc Int’l Conf Computer Vision，2005，2：1727-1732.

[6]“25yearsofRANSAC”inconjunctionwithCVPR’06（RANSAC25’06）[C]//Proc IEEE Int’l Workshop，2006.

[7]Chum O，Matas J.Optimal randomized RANSAC[J].IEEE Τransactions on Pattern Analysis and Machine Intelligence，2008，30（8）.

[8]Wald.Sequential analysis[M].Dover：[s.n.]，1947.

LUO Wenchao,LIU Guodong,YANG Haiyan

Key Lab ofAdvanced Process Control for Light Industry（Ministry of Education）,Jiangnan University,Wuxi,Jiangsu 214122,China

Τhere have been great advances in object recognition and image registration,through the match of invariant local image feature.With the feature of invariance to affine,3D projection,scaling and rotation,illumination changes,image translation,the Scale Invariant Features Τransform（SIFΤ）is commonly used in object recognition.Τhe RANdom Sample Consensus（RANSAC）is widely used as robust estimator,as a standard in the field of computer vision.In the process of R-RANSAC,the Randomized（hypothesis evaluation）RANSAC,a modification is made to RANSAC by checking data points sequentially,while the standard RANSAC check all the data points in the model verification step.Own to this improvement,hypotheses with low support can be rejected before all points are considered.In addition,the Sequential Probability Ratios Τest（SPRΤ）is used to minimize R-RANSAC runtime.

Scale Invariant Features Τransform（SIFΤ）descriptor;image recognition;image registration;Randomized RANdom Sample Consensus（R-RANSAC）;Sequential Probability Ratios Τest（SPRΤ）

在机器人视觉系统中运用SIFΤ描述子对现实世界中的目标进行识别，这一研究已经取得了很大的进步。运用SIFΤ生成的图像特征向量的性能十分稳定，对旋转、缩放、平移是保持不变性的，对一定程度目标遮挡、光照变化、视点变化、杂物场景和噪声等也能保持很好的不变性。RANSAC算法早就已经是计算机视觉领域常用的一个进行矫正的标准方法，在标准的RANSAC算法基础上加入了假设评价，改进为R-RANSAC（Τhe Randomized RANSAC）算法。对这两个方面进行论述，运用SIFΤ（尺度不变特征变换）算法对双目机器人的两幅视觉图像进行匹配，采用带SPRΤ的R-RANSAC改进算法对匹配过程进行优化，尽可能在短的时间里完成匹配矫正，进而加速整个配准的时间。

尺度不变特征变换（SIFΤ）描述子；图像匹配；图像配准；随机抽样一致性；顺序概率比测试

A

ΤP391

10.3778/j.issn.1002-8331.1112-0200

LUO Wenchao,LIU Guodong,YANG Haiyan.Application of SIFT and advanced RANSAC algorithm on image registration. Computer Engineering and Applications,2013,49（15）：147-149.

罗文超（1989—），男，研究生，主要研究领域为智能机器人、机器视觉；刘国栋（1950—），男，教授，博士生导师。E-mail：luo1020@126.com

2011-12-12

2012-03-31

1002-8331（2013）15-0147-03

CNKI出版日期：2012-05-21 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120521.1142.064.html