一种基于金字塔相似层的SIFT双向匹配算法研究

文雪中,马红(重庆市勘测院,重庆 400020)

一种基于金字塔相似层的SIFT双向匹配算法研究

文雪中∗,马红
(重庆市勘测院,重庆 400020)

摘 要:针对SIFT特征匹配算法误匹配点多和特征空间中遍历搜索速度慢的问题,提出了一种基于分层策略的SIFT双向特征匹配算法。首先,建立待匹配图像的金字塔影像,计算图像的SIFT特征点,并根据不同金字塔层将特征点划分为不同的集合;其次,选择某一层集合,在另一图像中寻找相似层,并确定两幅图像金字塔层之间的相似关系,在相似层之间设置阈值完成单方向匹配;然后,利用单向匹配结果完成已配对点集合的反向匹配。实验结果证明本文方法能降低匹配时间,提高匹配正确率。

关键词:SIFT特征匹配;金字塔;双向匹配;图像配准

1　引 言

长期以来,图像匹配一直是模式识别、计算机视觉等领域的研究热点,而图像的局部不变特征,是研究图像匹配的一个关键[1]。Lindeberg研究了图像局部不变特征方法的理论基础[2],而Lowe完善并实现了Lindeberg的理论;提出了SIFT(Scale Invariant Feature transform,即尺度不变特征变换)算子[3,4],它对几何旋转、尺度缩放、亮度变化保持不变性,对视角变化、仿射变换、噪声也保持一定的稳定性[1]。

SIFT算子的缺点是计算量大,误匹配点较多,对视角变化的稳定性不强;众多学者对SIFT提出了很多改进方法,如PCA-SIFT算法利用主成分分析法对SIFT描述子进行降维处理[5],SUFT算法提高了特征点检测速度[6],ASIFT算法增强了稳定性[7]。这些算法都继承了SIFT的思想,并在特征点检测或特征点描述上做了改进,但极少涉及对SIFT匹配策略的改进和优化。目前,SIFT算法的实现仍然是在整个特征空间进行的,当特征点空间较大时,匹配速度慢,且误匹配率高[8,9]。本文针对这两个问题,提出一种基于金字塔相似层间的特征匹配算法,减少特征空间搜索时间,并同时利用双向匹配策略进行匹配,提高匹配正确率。

2　SIFT特征匹配的基本原理

SIFT特征匹配算法是基于尺度空间理论完成的,主要包括尺度空间极值点检测、特征点定位、特征点方向确定、特征点描述符生成、特征点匹配[10,11],其基本流程如图1所示。

图1　SIFT特征匹配算法的基本流程

2．1高斯差分金字塔建立

利用DoG算子(Difference-of-Gaussian)构建高斯差分金字塔是实现SIFT特征匹配中极值点检测的基础。如式(1)所示,将一系列不同核值的高斯函数G (x,y,σ)与图像I(x,y)做卷积运算,即可得到高斯尺度空间L(x,y,σ);根据式(2),对高斯尺度空间进行采样可得到高斯金字塔,将相邻的高斯尺度空间做差即可得到高斯差分尺度空间[12]。

高斯卷积核是实现尺度变换的唯一变换核,针对图像I(x,y),其尺度空间L(x,y,σ)为原始图像与一个可变尺度的二维高斯函数G(x,y,σ)的卷积运算。

将高斯差分尺度空间中间层的每个像素分别与同一层相邻的8个像素、上层和下层各9个像素进行比较,确保在尺度空间和二维图像空间都检测到局部极值,找出极值点,即为特征匹配的候选点[13]。

2．2特征点定位

检测到的极值点在位置和尺度上用2×2的Hessian矩阵H计算其稳定性,用稳定性度量标准η剔除不稳定的点(一般为对比度较低的极值点和边缘上的极值点),剩下的极值点即为稳定性强的图像特征点。H矩阵和η分别如式(3)和式(4)所示。

其中,γ是控制特征点稳定性的参数,表示最大特征值和最小特征值的比值。

2．3特征点方向确定

以某一特征点为中心,在高斯尺度空间中,计算该特征点及其领域点的梯度幅值m和方向θ,如式(5)和式(6)所示;利用直方图统计特征点及其领域的梯度方向,并把直方图的峰值作为特征点的主要方向,若存在其他方向能量高于主方向能量的80%,那么这些方向即为特征点的辅助方向[9,13]。

2．4特征点描述符生成

将坐标轴旋转至特征点主方向,把特征点的16× 16窗口分为16个4×4的子窗口。计算每个字窗口中16个像素点的梯度方向,将所有梯度方向做高斯加权求和,得到一个包含8个方向梯度的种子点,最后得到一个128的特征向量[14,15]。

2．5SIFT特征匹配

在SIFT特征匹配算法中,用欧式距离作为特征点描述符相似性的度量因子。假定图像M的特征点集合为A={a1,a2,…,aM},图像N的特征点集合为B = {b1,b2,…,bN},那么图像M中某个特征点描述与图像N中某个特征点描述符的欧式距离如式(7)所示。

设图像M中某个特征向量am与N中特征向量bm有最短欧式距离为dmm,与特征向量bk有次短欧式距离为dmk(且m≠k),若两个距离满足式(8),则认为该匹配点对正确。

其中,T为匹配阈值,一般取[0．4,0．8]之间的常数[9,12]。

3　SIFT特征匹配策略的改进

现有SIFT特征匹配算法在整个特征点向量集合中进行搜索匹配,若集合元素很多时,匹配时间较长,因此需要构建金字塔检测图像不同尺寸下的特征点,在图像金字塔相似层之间进行搜索,减少搜索时间,提高匹配效率。另一方面,SIFT特征向量的匹配采用最邻近距离算法完成,这种在参考图像中寻找待匹配图像特征点对应点的方式是带有方向性的,即为待匹配图像到参考图像的单向匹配,算法虽然简便,但误匹配概率较大。因此,需要对SIFT单向匹配算法进行改正,将唯一性约束引入到匹配策略中,实现SIFT特征向量的双向匹配,可以减少误匹配点,进而提高匹配的正确率。本文改进后的匹配算法流程如图2所示。

图2　本文算法流程

其中,T1、T2为匹配阈值,在实验过程中T1、T2不相互影响,可取相同值。

具体步骤如下:

第一步,针对两幅待匹配的影像M和N,分别建立金字塔影像,并确定两幅影像金字塔层之间的相互关系。

第二步,计算图像M和图像N的SIFT特征点,并将处于同一个金字塔层的特征点组成一个集合;得到图像M的特征点集合A={{A1},{A2},…,{Am}},图像N的特征点集合B={{B1},{B2},…,{Bn}}。其中Ai表示图像M中处于某一金字塔层的特征点。

第三步,取出图像M中某一层的特征点子集Ai,分别在图像N的特征点子集中进行匹配,如果图像M的特征点子集Ai与图像N的特征点子集Bj有最大匹配点数,那么图像M的第i层金字塔与图像N的第j层金字塔相似,同理可求得图像M的第i+k层与图像N的j+k层相似。

第四步,根据单向SIFT特征向量的匹配算法,计算特征点子集Ai到Bj的匹配点对,剔除阈值小于T1的匹配点对,保留匹配阈值大于T1的匹配点对,作为Ai到Bj的匹配点对集合。

第五步,根据第四步中计算得到的匹配点对集合,用同样的方式逆向计算特征点子集Bj中已经被匹配的点在特征点子集Ai中的匹配点对,即求已被匹配点在特征点子集Ai中的最邻近与次邻近的距离比率,若比率小于匹配阈值T2,才作为正确匹配点[10],否则剔除匹配点对,最后得到的匹配点对即为特征点子集Ai与Bj的双向匹配结果。

这种基于金字塔层的双向匹配策略比单纯的SIFT算法约束条件更强,一方面可以降低检索时间,提高匹配效率,另一方面可以检测出更多的误匹配点,提高匹配的正确性;使得在大面幅的图像匹配中适用性更强。

4　匹配实验及结果分析

为了全面验证本文改进算法的性能,本文选择了不同焦距拍摄的图像分别进行原始算法匹配和本文算法匹配实验,从算法耗时、匹配点数以及匹配正确率三个方面进行比较,实验环境如表1所示。

本文实验环境 表1

本文选取一组不同焦距不同角度拍摄的图像进行实验,分辨率为1 200×1 800,检测到的特征点数为1 051 和866。对图像的特征点分别用原匹配策略和本文改进匹配策略进行匹配,匹配结果如图3和图4所示,两种算法的耗时、匹配点数、正确率结果如表2所示。

图3　原SIFT特征匹配结果

图4　本文算法匹配结果

原SIFT匹配算法与本文改进匹配算法的结果对比 表2

根据表2的统计结果可知:在计算耗时上,改进匹配策略的算法耗时是原匹配算法耗时的0．65倍;在匹配点数上,针对同样多的特征点,原匹配算法能匹配191对特征点,改进后的匹配算法能匹配112对特征点,匹配点数减少了约58%;在匹配正确率上,原匹配算法正确率为81．15%,改进后的匹配算法匹配正确率为95．53%。进一步分析,本文改进后的匹配算法虽然在匹配的特征点数上有所消减,但匹配效率提高了35%,匹配正确率提升了14．38%。本文改进的匹配策略能明显降低匹配时间,提升匹配正确率,在大幅面图像匹配中具有明显优势。

5　结 语

本文在研究SIFT特征匹配算法原理的基础上,针对原有SIFT匹配算法计算时间长、误匹配点多的问题,提出了一种基于金字塔相似层的双向匹配策略。与原匹配策略相比,改进后的匹配策略一方面通过金字塔相似层之间搜索匹配点,缩小了搜索范围,进而提高了匹配效率,另一方面,通过引入唯一性约束条件,利用匹配结果进行逆向匹配,将同时满足双向匹配的结果作为最终匹配结果,提高了匹配正确率;由于受金字塔相似层查找和反向阈值设定因素的影响,改进后的算法匹配点数有所下降。在图像幅面越大、特征点数越多的情况下,本文改进的匹配算法速度提升和正确率提升也越大,相对消减的匹配点数影响也越小,实用性也更强。

参考文献

[1] 闸旋,王慧,程挺等．一种基于分块策略的SIFT特征快速提取与匹配方法_闸旋[J]．测绘科学技术学报,2014, 31:505～509．

[2] Lindeberg T．Detection and Ridge Detection with Automatic Scale Selection[J]．International Journal of Computer Vision．1998,2(30):117～154．

[3] Lowe D G．Object Recognition from Local Scale-Invariant Features[A]．7th International Conference on Computer Vision．Corfu,1999:1150～1157．

[4] Lowe D G．Distinctive Image Feature Form Scale-Invariant Keypoints[ J]．International Journal of Computer Vision．2004,60(2):91～110．

[5] Yan K,Sukthankar R．PCA-SIFT:a more distinctive representation for local image descriptors[A]．New Youk:2004．

[6] Herbert B,Tinne T,Luc V G．SURF:speeded up robust features[J]．Computer vision and image understanding．2008, 3(110):346～359．

[7] Morel J M,Yu G．A per[J]．SIAM journal on imaging sciences,2009,9(2):438～469．

[8] 宛蓉,蒋丹妮,周天顺．基于改进的SIFT算法的异源影像匹配[J]．地理空间信息,2014,12(4):63～65．

[9] 卢朝梁,马丽华,陈豪．改进的SIFT特征匹配算法[J]．空军工程大学学报·自然科学版,2014,15(1):72～76．

[10] 吕倩利,邵永社．基于SIFT特征的异源遥感影像匹配方法研究[J]．计算机工程与应用,2012,48(36):171～175．

[11] 郑永斌,黄新生,丰松江．SIFT和旋转不变LBP相结合的图像匹配算法[J]．计算机辅助设计与图形学学报, 2010,22(2):286～292．

[12] 梁建国,马红．改进的SIFT双向匹配算法在异源影像匹配中的应用[J]．地理空间信息,2014,12(6):57～64．

[13] 刘焕敏,王华,段慧芬．一种改进的SIFT双向匹配算法[J]．兵工自动化,2009,28(6):89～91．

[14] 吕倩利,邵永社．基于SIFT特征的异源遥感影像匹配方法研究[J]．计算机应用与工程,2012,36(48)．

[15] 宋佳乾,汪西原．基于改进SIFT特征点匹配的图像拼接算法[J]．计算机测量与控制,2015,23(2):512～515．

Research on Sift Bidirectional Matching Algorithm Between the Similar Prymid Layers

Wen Xuezhong,Ma Hong
(Chongqing Survey Institute,Chongqing 400020,China)

Abstract:Aimed at the high wrong match points and slow matching speed in searching the whole database of feature points of SIFT feature matching method,we proposed an improved matching method of searching between the similar pyramid layers using bidirectional matching．First,we calculate the pyramid image and SIFT feature points of the input images,and divid the feature points into different sets according to the different pyramid layers．Then a layer set in the input image pyramid is chosen to search for the similar layer in the another image pyramids,and then the similarity between tow image pyramid layers is determined,and matching the feature points between the similarity pyramid layers by single direction．Finally,matches the feature points which have been matched by reverse direction．The experimental results demonstrate that this approach can reduce the matching time and improve the matching accuracy．

Key words:scale invariant features transform match;pyramid image;bidirectional match algorithm;image matching

文章编号:1672-8262(2015)04-99-04中图分类号:P234．1

文献标识码:A

收稿日期:∗2015—02—06

作者简介:文雪中(1979—),男,高级工程师,主要从事测绘地理信息工程建设管理工作。

基金项目:“十二五国家科技支撑计划”课题(2011BAH12B07-03)