一种图像局部特征快速匹配算法*

张格森，陈东生，王怀野，陆振林

（1.北京航天微系统研究所，北京 100094；2.中国航天时代电子公司博士后科研工作站，北京 100094）

一种图像局部特征快速匹配算法*

张格森1，2，陈东生1，王怀野1，陆振林2

（1.北京航天微系统研究所，北京 100094；2.中国航天时代电子公司博士后科研工作站，北京 100094）

在图像处理和机器视觉领域，SIFT是目前被广泛应用的一种基于局部特征的图像匹配算法。针对SIFT算法匹配速度较慢和常常存在错误匹配对的问题，本文提出在匹配过程中采用角度相似性分析替代传统的欧式距离分析法，由此提高匹配速度，然后通过RANSAC一致性筛选删除错误匹配对，最后通过实验验证了新算法的有效性。新算法结构清晰，计算简便，易于硬件实现。

图像匹配；局部特征；SIFT；角度相似性；RANSAC

0 引言

图像匹配是指通过图像分析方法在两幅或者多幅图像中寻找同名点的过程[1]。图像匹配是机器视觉和图像处理领域的核心问题之一，是目标识别技术的重要研究内容，广泛应用于遥感影像处理、目标识别与跟踪、医学图像处理和图像制导技术等领域。目前，常用的图像匹配算法主要有基于区域统计性特征的图像匹配和基于局部特征的匹配两大类[2]，而由于图像场景的复杂性和局部特征具有更好的鲁棒性，基于局部特征的图像匹配算法日益成为该领域研究的主流方向[3]。

迄今为止，SIFT（Scale Invariant Feature Transform）算法[4]被公认为具有很好的鲁棒性，是最适合在复杂场景中应用的一种局部特征匹配算法，已成为目前最主流的图像匹配算法之一[5]。根据 SIFT算法的原理，SIFT算法能够很好地抵御图像尺度变换、旋转变换和仿射变换，当图像存在一定程度的噪声时，也能够实现图像匹配，因此该算法常常被用于一些复杂场景的图像匹配问题。但是，SIFT需要生成很高维度的描述向量，匹配时利用欧式空间距离法分析描述向量的相似性，运算量大，很大程度上限制了该算法在实际硬件系统中的应用。目前，针对SIFT算法简化运算的研究主要聚焦在如何简化描述向量方面，如 PCA-SIFT[6]，而对描述向量匹配过程中运算量大的问题研究较少。针对该问题，本文以角度相似性分析为基本思路，提出了一种易于实现的图像局部特征快速匹配算法，提升算法性能。

1 SIFT匹配算法原理

SIFT匹配算法主要包括特征点搜索、描述向量生成和特征点匹配三个基本步骤。

1.1 特征点搜索

SIFT特征点搜索也称特征点检测，主要分为三个基本步骤：尺度空间生成、空间邻域极大值搜索和特征点精确定位[4]。

(1)尺度空间生成

目前，已经有文献用数学方法证明了高斯核是产生信号多尺度空间的惟一有效核[7]，由高斯核生成的尺度空间满足尺度、平移以及旋转不变性等。对于二维图像I(x，y)，其尺度空间L(x，y，σ)的定义为：

其中，σ为尺度空间的尺度因子，⊗表示在x和y双方向的卷积运算，G(x，y，σ)为高斯核函数，G(x，y，σ)的定义为：

(2)空间邻域极大值搜索

Lowe在文献[4]中提出，在某个尺度上搜索图像斑点，可以先在两个相邻的高斯尺度空间图像之间做减运算，求得一个 DoG（Difference of Gaussian）响应值图像D(x，y，σ)，D(x，y，σ)的公式为：

其中，k为两个相邻尺度倍数的常数。

在实际操作中，DoG是通过建立图像的尺度空间金字塔来实现的[8]。在尺度空间金字塔中，每一个像素点和其26个邻域(包含同尺度相邻点和上下相邻尺度的相邻点共26点)进行比较，实现空间范畴的局部极大值搜索，得到的所有极大值点构成的集合即为特征点的备选集合。建立备选集合时，可去除对比度较低的极值点，由此对集合进行初步提纯。

(3)特征点精确定位

特征点精确定位时，通过三维二次函数来拟合特征点，由此可以获得特征点的精确位置和尺度值，此外，为了确保所提取特征点的稳定性，基于Hessian矩阵计算主曲率，去除在边缘上极值点。

1.2 描述向量生成

SIFT描述向量生成主要包括求取特征点主方向和特征点描述两个基本步骤。

(1)求取特征点主方向

对于某个特征点，首先在其尺度图像中设定一定范围为邻域区域，在邻域中计算每个点的梯度 M(x，y)和方向θ(x，y)，其表达式分别为：

统计邻域区域内的梯度及方向数据，构建直方图，直方图中的主峰值则为特征点的主方向，若在直方图中存在一个次峰值，其能量相当于主峰值80%以上，则将这个方向确定为特征点的辅方向[9]。至此，特征点有了四个参数信息(x，y，σ，θ)，分别为特征点坐标、尺度信息、方向信息。确定主方向和辅方向的作用是使特征点具有旋转不变性。

(2)描述向量生成

在对每个特征点进行描述时，首先将尺度图像坐标轴旋转至主方向上，在特征点邻域范围划定4×4共16个子区域，在每个子区域，将0～360°全方向划分为 8个子方向（每个子方向宽度为 45°），统计各子方向梯度强度，构建8维子区域描述向量。对于16个子区域，则最终生成 4×4×8=128维描述向量，描述向量也称描述子或特征向量。

1.3 特征点匹配

特征点匹配的目的是在原图像和待匹配图像中寻找相似程度高的特征点对，通常特征点在图像间都是一对一关系，因此点对匹配时仅考虑相似度最近邻情况。

目前的匹配方法主要采用欧式距离分析法[4]，对于k维向量Xi和 Xj，其欧式距离公式为：

式(7)中，Min{Dis}为求得的最近邻，secMin{Dis}为求得的次近邻，TDis表示最近邻与次近邻的比值阈值。若式(7)成立，则认定最近邻相对应的特征点对为正确匹配对。通常，TDis在0.6～0.75之间取值。

欧式距离分析法能够有效实现特征点对的相似性筛选，物理意义明确，但该方法运算速度慢，制约了SIFT算法的应用范围。

为删除一些易混淆点对，采用最优与次优比值的方法，对于欧式距离来说，即为最近邻与次近邻比值的方法。在运算中，若最近邻与次近邻比值小于预设的阈值，则认定为正确匹配对，认定关系式可表述为：

2 改进的匹配算法

为了提升匹配速度和进一步筛选匹配对，本文提出角度相似性分析和随机抽样一致性(Random Sample Consensus，RANSAC)筛选[10]相结合的方法，简化匹配运算并删除不符合空间一致性关系的错误匹配对。该算法以SIFT描述向量为处理对象，包括描述向量预匹配和匹配点对筛选两个基本步骤。

2.1 描述向量预匹配

描述向量预匹配以角度相似性作为匹配准则，该方法也可称为角度相似性匹配。角度相似性分析的原理：对于两个单位向量，其夹角与弧长正相关，夹角很小时，弧长与弦长近似相等，弦长即为欧式距离。因此，夹角大小与欧式距离正相关，可以利用夹角的大小来判断单位向量之间的相似程度。对于待匹配的k维单位向量，计算向量间的空间夹角，夹角越小，则这两个描述向量越相似。

k维空间中的向量夹角 Φij计算公式为：

对于SIFT描述向量，描述向量生成过程中已经进行过归一化运算，因此，式（8）可简化为：

因 Φ(i，j)较大时不符合相似性准则，因此，首先舍弃Φ(i，j)数值较大的情况。然后，利用最优与次优的比值大小来认定是否为正确匹配对，其认定关系可表述为：

式(10)中，Min{Φ}表示最小夹角(即最优夹角)，secMin{Φ}表示次小夹角(即次优夹角)，TΦ为最小夹角与次小夹角比值阈值，当式(10)成立时，最小夹角对应的匹配对即被认定为备选匹配对，经过遍历运算后，建立备选匹配对集合。需要注意根据角度相似性分析原理，作为无量纲的比值阈值TDis和TΦ应具有相同的取值区间，即TΦ同样可在0.6～0.75之间取值。

为了进一步减化运算，在实际算法设计中，计算向量之间夹角余弦值后仅保留最大和次大值，然后仅对最大和次大值做反余弦计算求取最小和次小角度值。

2.2 匹配点对筛选

由于图像场景的复杂性，不能避免在备选匹配对集合中有错误匹配对存在的情况。针对该问题，采用RANSAC算法[10]对特征点对进一步筛选，保证匹配点对空间关系的一致性。

RANSAC算法原理：认为正确的匹配对在图像中满足空间关系的一致性，因此，可以在备选集合中不断地随机性抽取匹配点对，利用抽取的匹配点对建立图像间空间投影矩阵，然后通过空间关系的一致性度量验证该空间投影关系的正确性，多次抽取和计算后，获得的一致性最强的空间投影矩阵即为实际的空间投影矩阵，由此可以删除备选集合中的错误匹配对。

RANSAC算法的基本步骤包括[10]：

(1)从备选集合中随机抽取 4对初始匹配点对（每个图像平面上的4个点须满足任意3点不共线），计算两平面之间的线性投影矩阵的参数。

(2)对于未被抽取到的特征点，通过步骤(1)中计算得到的投影矩阵计算其在另一平面中的坐标值，进而获得该坐标值与它预匹配的点之间的距离，若该距离很小，则该匹配点对认定为内点，否则认定为外点，记录内、外点数量。

(3)多次重复步骤(1)、(2)操作，选择内点数量最多时对应的投影矩阵参数作为正确的投影矩阵参数。

(4)对于被确认的投影矩阵，其相应的内点即被认定为正确的匹配点对。

经过上述筛选后，不满足空间一致性关系的匹配点对将被成功删除。

2.3 算法流程

本文算法的实现流程如图1所示。

新算法结构清晰、运算简便，易于向硬件系统移植。在实际应用中，可采用典型的DSP+FPGA双核心结构实现硬件设计。

图1 本文算法流程图

3 算法验证与分析

将图 2中原始图像 SCENE（分辨率：384×512）和目标图像BASMATI（分辨率：175×265）作为待匹配图像，采用本文算法进行实验。实验环境：Intel Core i3-2 350 M 2.30 GHz CPU、4 GB（3.07 GB可用）内存、Win7操作系统PC机，Matlab7.6。从图2可以看出，原始图像对应区域和目标图像之间存在尺度、旋转和仿射变换。

图2 原始图像（SCENE）和目标图像（BASMATI）

实验中，首先对SCENE图像和BASMATI图像进行SIFT特征点搜索，然后，分别用欧式距离分析和本文的角度相似性分析进行预匹配，当阈值 TDis和 TΦ取 0.65时，输出结果如图3和图4所示。

图 3 欧式距离法匹配结果(TDis=0.65)

在描述向量预匹配过程，欧式空间匹配法耗时6.31 s，而角度相似性匹配法耗时 4.19 s，运算速度明显提升。图3中，预匹配对总数量和正确匹配对数量分别为39和37，图4中，预匹配对总数量和正确匹配对数量分别为41和39。为了更好地说明算法的有效性，将比值阈值在0.6~0.75间取值，预匹配正确率统计结果如表1所示。

图 4 本文方法预匹配结果(TΦ=0.65)

表1 预匹配正确率统计

由于特征点匹配以遍历搜索为基本流程，因此比值阈值的大小不影响匹配耗时。经过预匹配后，再利用RANSAC空间一致性筛选删除错误匹配对，获得的最终匹配结果（TΦ=0.65）如图 5所示。

图5 RANSAC筛选后本文方法匹配结果(TΦ=0.65)

由图5可知，错误匹配对被RANSAC筛选成功删除。实验表明，当 TΦ在（0.6，0.75）范围内取值时，RANSAC同样能有效删除错误匹配对。

分析上述实验可知，本文算法的预匹配速度较传统方法明显提升，预匹配点对总数量和正确率均优于传统方法，引入RANSAC筛选后，错误的匹配对被成功删除。上述实验验证了本文算法的有效性。

4 结论

针对SIFT匹配运算速度较慢和存在错误匹配对的问题，本文提出采用角度相似性分析代替传统的欧式距离分析，引入RANSAC筛选删除不满足空间一致性关系的匹配对。实验结果表明，新算法计算速度和预匹配正确率均优于传统方法，且能够有效删除错误匹配对。后续的研究将重点着眼于如何进一步提升算法运算速度和算法的环境适应性等问题。

[1]ARICAN Z，FROSSARD P.Scale-invariant features and polar descriptors in omnidirectional imaging[J].IEEE Transaction on Image Processing，2012，21(5)：2412-2423.

[2]尧思远，王晓明，左帅.基于 SURF的特征点快速匹配算法[J].激光与红外，2014，44(3)：347-350.

[3]余先川，吕中华，胡丹.遥感图像配准技术综述[J].光学精密工程，2013，21(11)：2960-2972.

[4]LOWE D G.Distinctive image feature from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60(2)：91-110.

[5]杨天天，鲁云萍，张为华.一种基于GPGPU的 SIFT加速算法[J].电子技术应用，2015，41(1)：149-152，160.

[6]KE Y，SUKTHANKAR R.PCA-SIFT：A more distinctive representation for local image descriptors[C].Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition，Washington DC，USA：CVPR，2004(2)：506-513.

[7]白廷柱，侯喜报.基于SIFT算子的图像匹配算法研究[J].北京理工大学学报，2013，33(6)：622-627.

[8]杨娜娜，哈力旦·阿布都热依木，伊力亚尔·达吾提.基于SIFT图像配准的维吾尔语文字识别方法[J].传感器与微系统，2014，33(3)：40-43.

[9]王程冬，程筱胜，崔海华，等.SIFT算法在点云配准中的应用[J].传感器与微系统，2012，31(2)：149-152.

[10]LI B，MING D，YAN W，et al.Image matching based on two-column histogram hashing and improved RANSAC[J]. IEEE Geosciences and Remote Sensing Letters，2014，11 (8)：1433-1437.

A rapid matching algorithm via image local feature

Zhang Gesen1，2，Chen Dongsheng1，Wang Huaiye1，Lu Zhenlin2
（1.Beijing Aerospace Institute of Microsystems，Beijing 100094，China；2.Postdoctoral Workstation of China Aerospace Times Electronics Corporation，Beijing 100094，China）

In the fields of image processing and machine vision,SIFT is a widely adopted image matching algorithm based on local feature.In view of the slow speed of matching and the frequently existing of the inaccurate matching pairs,the analysis of angle similarity is presented to replace the conventional Euclidean distance analysis and improve the speed in matching process.Then, RANSAC consensus selection is performed to eliminate the inaccurate matching pairs.At last,the experimental results verify the validity of proposed algorithm.The new algorithm has the advantages of clear framework,easy calculation and being easily realized by hardware.

image matching；local feature；SIFT；angle similarity；RANSAC

TP391.4

A

10.16157/j.issn.0258-7998.2015.11.035

张格森，陈东生，王怀野，等.一种图像局部特征快速匹配算法[J].电子技术应用，2015，41(11)：124-127.

英文引用格式：Zhang Gesen，Chen Dongsheng，Wang Huaiye，et al.A rapid matching algorithm via image local feature[J]. Application of Electronic Technique，2015，41(11)：124-127.

2015-08-31）

张格森（1980-），男，博士，高级工程师，主要研究方向：图像处理与精确制导技术、信号检测与雷达成像。

国防科工局军贸科研项目；国防科工局民用航天基金(2014537)

陈东生（1962-），男，博士，研究员，主要研究方向：惯性导航与信息处理技术。

王怀野（1973-），男，博士，研究员，主要研究方向：机器视觉与制导控制技术。