基于稀疏结构的图像特征匹配算法①

包晓安, 詹秀娟, 张俊为, 王 强, 胡玲玲, 桂江生

(浙江理工大学 信息学院,杭州 310018)

图像匹配是目标跟踪、图像检索和图像全景拼接等多个应用领域中重要的组成部分[1-4]. 目前匹配算法主要是基于图像特征学习的,该类方法对于复杂环境的图像匹配仍能保持较好的稳定性,已逐渐成为图像匹配研究的主流方向.

SIFT算法[5]是公认性能最好的特征匹配算法之一,适用于图像的尺度、旋转变换、光线强弱变化等各种复杂情况下. 但是算法的复杂度较高,影响特征点的检测速度和匹配速度. 快速鲁棒特征(SURF)算法[6]是对SIFT的改进,该算法采用海森矩阵,使特征点的检测速度提高几倍,但降低了匹配准确率. PCA-SIFT算法[7],其思想是用主元分析法[8]代替SIFT算法中直方图方法,提高算法运行的速度,但匹配数目较少. 近年来也产生了一些性能较好的算法,如Xu等[9]是将局部轮廓信息和全局信息融合,并结合改进的DTW技术,通过计算全局最佳匹配路径,能够实现局部匹配. Chen等[10]通过基础矩阵计算特征点极线,并通过极线约束剔除错误匹配. Ren等[11]是将彩色信息和灰度信息叠加,形成改进的SURF特征描述子,并采用双向搜索策略实现特征匹配.

特征匹配时,无论是最佳路径的选择,还是采用双向搜索策略,都会有效提高匹配正确率. 但是多数匹配算法是对图像进行全局特征点检测,而且特征匹配时使用全局搜索策略,也会影响算法运行速度. 针对上述问题,提出一种基于稀疏结构的图像特征匹配(Sparse Structure Matching,SSM)算法. 通过分析每个像素点的稀疏度值,筛选出稀疏度高的像素点所在的区域,作为结构稀疏度区域,缩小特征点的提取范围,加快特征点检测的速度,并通过最佳描述子的选择实现特征匹配.

1 SSM算法

SSM算法是在特征点提取之前,通过稀疏度值的高低筛选出结构区域,然后对结构区域进行特征提取,这样就避免了在全局进行特征点提取,减少了一些不稳点特征点的数量,这就使特征点生成过程,缩短特征点检测时间,且采用最佳描述子匹配的准确率得到有效提高.

1.1 稀疏函数

在图像中一个较小邻域的灰度发生急剧的变化,其实体现的就是图像的结构. 而灰度变换和空间变换对局部结构的影响较小[12]. 一般图像的轮廓、图形的拐角、交叉区域包含了图像中大部分结构. 在图像中,一个图像块与其邻域中的其余图像块之间一般存在一定的联系.

如图1所示,其中,图像块用实线框区域表示,其邻域用虚线框区域表示. 图中A位于图像中平滑区域,其邻域内有较多的相似图像块[13]. 而位于图像中结构区域的B,其邻域范围内有很少的相似图像块.

Xu等[14]根据图像中图像块和它邻域内其它图像块之间的一个相似度,来定义图像稀疏结构的概念. 对图像全局进行图像块的划分,假设将图像中某一像素点m为中心的邻域窗口记为N(m),其大小为25×25.以该像素点为中心的图像块记为ψm,其大小为7×7,ψmi是其邻域窗口中以mi为中心的邻域块,领域窗口N(m)中所有的mi的集合记为Ns(m),即：

图1 不同区域的图像块及其邻域

直方图能够反映图像的灰度分布,以直方图计算相似度,复杂度低. 梯度信息反映了相邻像素之间的相对变化、连接紧密程度以及图像的方向特征,所以引用文献[15]中的梯度信息相似性度量,将梯度信息与直方图相似性度量结合,增加衡量图像块位于结构区域的可信度,计算图像块的直方图,则不同图像块直方图之间的相似性定义为：

式(2)中,H(m,mi)表示图像块ψm的直方图和邻域范围中其余图像块ψmi的直方图的相似度,h1i表示图像块ψm灰度级为i时的像元个数,h2i表示图像块ψmi灰度级为i时的像元个数,灰度级l=255. 两图像块相似度越高,其直方图越相似,那么H(m,mi)的值就越小.

如图1中A的邻域内图像块C和A比较相似,其直方图之间的相似度较高; 而D则与A相差较大,其直方图之间相似度较低,所以采用直方图的方法能够较好的衡量图像块之间的相似度.

图像块ψm与图像块ψmi之间的相似度定义为：

式 (3)中,d(Гm,Гmi)表示在梯度模值图像中,以m与mi为中心的图像块间的距离,α=5,用来控制相似度的衰减程度.P(m)是归一化系数,使

在求得图像块之间的相似度之后,图像块的稀疏度函数就可以定义为：

式(4)中,|Ns(m)|是集合中元素个数; |N(m)|表示邻域窗口中元素的个数.

1.2 稀疏结构区域的标记

通过对图像分析,由稀疏度函数求解出每个图像块的稀疏度值S(m),利用块结构稀疏概念将图像划分为两类[16]：一是包含大量结构信息的结构区域,称为结构块; 二是包含大量纹理信息或平滑区域的非结构区域,称为非结构块. 图像中结构区域、非结构区域的结构稀疏度是不同的,结构区域的结构稀疏度值较高一般在0.7～1.0之间,而非结构区域的稀疏度值一般小于0.3.

在运算中,将阈值设置为0.7,这样对于不同的图像基本都可以筛选出它们的结构区域. 结构块的稀疏度值都大于规定的阈值,则为稀疏结构区域,认定关系表述为：

式(5)中S(m)为图像块的稀疏度值,ξ=0.7为规定的阈值. 相反,非结构块的稀疏度值都小于规定的阈值.在一般情况下,在一幅图像中结构块的数量远少于非结构块的个数,所以只对标记的结构块进行特征提取,提取的特征稳定性好且能有效减少处理的区域.

图2 稀疏结构区域的标记

计算每个像素的稀疏度值,通过定义的阈值,将稀疏度值高的区域筛选出来,进行标记,如图2所示.

1.3 稀疏结构区域的SIFT特征提取

采用SIFT的方法对有标记的稀疏结构区域进行极值点检测、关键点定位和方向分配. 极值点的检测,如图3(a),对图像特征方向的定位,如图3(b)所示.

1.4 最佳描述子选择及特征匹配

通过关键点周围区域梯度信息得到SIFT描述子.关键点及其周围部分像素点都包含在描述子中,而图像匹配的质量依赖于特征提取的描述子,因此如何找到最佳的描述子,是提高匹配准确率的一种方法. 描述子的有效性不仅取决于图像内的外观,而且取决于图像间的变化,因此对于图像匹配,最佳的描述子通常是图像相关或者是区域相关[17].

图3 极值点检测及SIFT特征

特征匹配是通过在特征点邻域内搜索多个描述子中的一个,该邻域内所有的描述子就作为候选描述子.特征点之间距离可能相隔几个像素,特别是对于邻域内两个相距最近的特征点,它们的描述子相似度较高,在对这两点寻找对应匹配点时,导致错误匹配的概率就会增高. 在邻域内的候选描述子中寻找一个描述子能使该特征点与其相距最近的特征点进行区分,这样的描述子就是该特征点的最佳描述子. 将最佳描述子选择问题转化为构造图的能量最小化问题.

(1) 构造图

若给定待匹配图像Ip和IQ,特征点分别是构造图G,由顶点集v和边集ε组成,表示为G(v,ε). 图G中每个顶点在本文中即是对应于图像Ip中的特征点Cp,顶点的数量|v|=Np. 如果在某一邻域大小为K的区域中,Cj是距离Ci最近的邻点,则连接它们对应的顶点vi和vj的边为eij,且复合变量每个顶点与复合变量相关联,该复合变量wi表示通过描述子di将特征点与特征点进行匹配,此时选择的描述子di,即是最佳的描述子; 而特征点与特征点是在最佳描述子下的最佳匹配对.

(2) 寻找合理的图的标号

式(6)表示特征点邻域内描述子的评估功率取最小值,gi(wi)为邻域内选择的描述子的评估功率.

式(7)中,n是空间邻域的个数,si是特征点索引,di是描述子索引. 其中,

式(8)中,Y是特征点的特征向量是在描述子di下,特征点之间的光度相异函数,dist是特征向量之间的欧式距离. 同理,是在描述子di下,特征点之间的光度相异函数.

(3) 最佳描述子及特征匹配

当式(6)的取值为最小时,则选择的这个合理的标号为W=wi,故由可知,邻域内选择的描述子di,是的最佳描述子,该描述子下的特征点的匹配是最佳的匹配; 否则,该描述子就不属于最佳描述子,这样的描述子无法区分相邻匹配点对故被舍去.

1.5 算法运行步骤

本文算法步骤如下：

步骤1. 分别将两幅利用式(4)计算图像块的稀疏度值,用式(5)进行筛选,得到稀疏结构区域,对该区域进行标记;

步骤2. 构造尺度空间. 将待匹配图像与高斯核函数卷积可得到待匹配图像的尺度空间,为：

式(9)、(10)中,(x0,y0)是像素点的位置,σ决定图像平滑程度. 将高斯尺度空间中相邻两层相减得到高斯差分金字塔,对其特征进行归一化,可以得到明显的差分图像蕴含的特征,这些特征就是要提取的稳定特征.

步骤3. 采用经典SIFT算法对两幅图像中有标记的稀疏结构区域中进行极值点检测和关键点定位.

步骤4. 统计关键点邻域的梯度信息生成SIFT描述子.

步骤5. 利用式(7)计算描述子的评估功率,利用式(6)找到评估功率的最小值. 在最佳描述子下,将特征点进行匹配,对匹配的两特征点进行连线,直到图像Ip中所有特征点找到其在图像IQ中的对应匹配点为止.

2 算法测试及结果分析

实验运行环境为Matlab R2014b版本,Intel(R)Core(TM)i5-3210M 2.3 GHz 4 GB内存的PC机. 实验5组图像数据,分别为cat、flower、lena、build和street,图像分辨率均为400 dpi.

2.1 匹配结果比较

为验证本文算法的普适性,使用不同类型的图像,将SSM算法与三种算法进行比较.

图4是选择5种图像数据的特征匹配结果图,图中每根线代表一对特征匹配对,图(a)、(b)、(c)和(d)分别表示SIFT、SURF、PCA-SIFT和SSM算法匹配结果. 从图中可以看出,图(d)相比于其它算法的匹配对个数较多.

图4 SIFT、SURF、PCA-SIFT和SSM算法特征匹配结果

匹配结果数据用表1列出,可知cat图像的匹配结果中,SSM方法的匹配对数是SIFT方法的2.1倍,是SURF方法的6.3倍,是PCA-SIFT方法的8.9倍.flower图像的匹配结果中,SSM方法的匹配对数是SIFT方法的1.3倍,是SURF方法的1.7倍,是PCASIFT方法的2.0倍. lena图像匹配结果中,SSM方法的匹配对数是SIFT方法的1.6倍,是SURF方法的1.9倍,是PCA-SIFT方法的2.5倍. build图像的匹配结果中,SSM方法的匹配对数是SIFT方法的7.7倍,是SURF方法的7.0倍,是PCA-SIFT方法的9.2倍.street图像的匹配结果中,SSM方法的匹配对数是SIFT方法的5.7倍,是SURF方法的6.6倍,是PCA-SIFT方法的7.5倍. 5组数据中,SSM方法的匹配对个数比其它三种方法高出1.3～9.2倍.

表1 SIFT、SURF、PCA-SIFT和SSM算法匹配对个数数据统计

为了直观表明SSM方法的优越性,画出了四种算法得到的特征点匹配对数的柱状图,如图5. 可以看出,对于任意一组图像数据,SSM算法的匹配对数都比其它三种算法多出1.3倍以上. 选择的图像包括：单个对象、自然景物、建筑物和室外复杂场景,采用SSM算法,匹配效果都得到提高,足以说明SSM算法的普适性.

图5 特征匹配对个数对比图

2.2 匹配速率

为了准确评估SSM算法性能,分别对图像在亮度、旋转、尺度、加椒盐噪声和仿射变换等复杂情况下进行对比试验,性能分析中选择lena图像作为试验对象.

将SSM算法与SIFT、PCA-SIFT、SURF三种方法,在特征检测时间和特征匹配时间进行比较. 算法运行时间对比,如图6所示,由图(a)可以看出,对于不同的图像变换,由于SURF通过海森矩阵定位兴趣点,所以检测耗时最短; 而SSM算法是在稀疏结构区域进行特征点检测,有效的缩小了检测范围,但是在寻找稀疏结构区域时也会增加计算复杂度,虽然在检测速度上优于PCA-SIFT算法和SIFT算法,但是仍然没有SURF算法检测速度快. 由图(b)可知,SSM算法匹配时间最短,SIFT算法耗时最长. 因为本文方法不是对图像进行全局寻找匹配点,而是在稀疏结构区域进行全局搜索,这样就会大大减少搜索区域,节省很多时间.而其它三种算法均是对图像进行全局的特征点搜索,每搜索一个特征点,都要进行一次步骤5,要将所有特征点一一匹配也是一个浩大的工程. 所以本文算法在匹配速度上是优于其它三种算法的.

图6 算法运行时间对比图

2.3 匹配准确率

为了直观反应算法的匹配效果,定义了匹配准确率函数P.P越大说明错误匹配对越少,算法的匹配效果越好. 假设图像Ip和图像IQ进行特征匹配时,匹配总数为f,其中错误匹配数为f1,那么匹配准确率可以定义为：

由表2可以看出,在图像亮度变换的情况下,SSM算法的匹配准确率为91.5%,比其它三种算法高6.1%～13.2%,而SIFT准确率略低. 在图像旋转变换情况下,SSM算法的匹配准确率为98.3%,比其它三种算法高12.3%～34.6%,SIFT准确率还是相对较高,而旋转变换对SURF和PCA-SIFT的影响较大. 在图像尺度变换的情况下,SSM算法的匹配准确率为98.6%,比其它三种算法高8.5%～19.4%,SURF和PCA-SIFT的匹配准确率相对较低,而SIFT的匹配准确率是图像几种变换下最高的,SIFT具有较好的尺度不变性. 在图像加噪声的情况下,SSM算法的匹配准确率为97.8%,比其它三种算法高11.1%～36.1%,而噪声对SIFT的影响较大. 在仿射变换下,SSM算法的匹配准确率为90.2%,比其它三种算法高9.9%～15.8%. 由于SSM算法特征点稳定性较好,且采用最佳描述子下进行特征匹配,所以受图像外界影响较小. 因此在图像进行复杂变换时,SSM算法在匹配准确率上比其它三种算法更具有优势.

表2 4种算法匹配准确率统计表(单位：%)

3 结论

针对传统特征匹配算法特征点检测耗时长和匹配准确率低的问题,本文提出一种基于稀疏结构的图像特征匹配算法. 文中通过引入稀疏结构的概念,进而考虑到在稀疏结构区域提取特征点以缩小特征点的检测范围. 通过对实验结果的分析,我们可以看出,本文提出的SSM算法与其它的算法相比,无论在特征点的检测速度,还是在特征匹配速度,更或者是匹配准确率和算法普适性方面,都具有很好的优势. 但是本文算法也存在一些不足,比如在计算稀疏度值、筛选出稀疏度高的像素点所在的区域上,比其它的算法稍显复杂. 接下来的研究工作主要在两个方面：一是考虑到该方法存在一定的错误匹配,如果与误匹配剔除结合起来,会使算法性能更好. 二是将本文算法与目标跟踪算法相结合.

1 常发亮,马丽,乔谊正. 遮挡情况下基于特征相关匹配的目标跟踪算法. 中国图象图形学报,2006,11(6)：877-882. [doi：10.11834/jig.200606147]

2 周燕,曾凡智. 基于二维压缩感知和分层特征的图像检索算法. 电子学报,2016,44(2)：453-460.

3 曹世翔,江洁,张广军,等. 边缘特征点的多分辨率图像拼接. 计算机研究与发展,2011,48(9)：1788-1793.

4 郑启财,曾智勇,池燕玲. 改进的基于颜色和SIFT特征的图像检索方法. 计算机系统应用,2015,24(11)：129-133.[doi：10.3969/j.issn.1003-3254.2015.11.020]

5 Lowe DG. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision,2004,60(2)：91-110. [doi：10.1023/B：VISI.0000029664.99615.94]

6 Bay H,Tuytelaars T,Van Gool L. SURF：Speeded up robust features. In：Leonardis A,Bischof H,Pinz A,eds. Computer Vision-ECCV 2006. Berlin,Heidelberg：Springer,2006.404-417.

7 Ke Y,Sukthankar R. PCA-SIFT：A more distinctive representation for local image descriptors. Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington,DC,USA.2004. II-506-II-513.

8 黄炜,赵险峰,冯登国,等. 基于主成分分析进行特征融合的JPEG隐写分析. 软件学报,2012,23(7)：1869-1879.

9 徐贵力,赵妍,姜斌,等. 基于局部尺度特征描述和改进DTW技术的局部轮廓匹配算法. 电子学报,2016,44(1)：135-142.

10 陈洁,高志强,密保秀,等. 引入极线约束的SURF特征匹配算法. 中国图象图形学报,2016,21(8)：1048-1056. [doi：10.11834/jig.20160809]

11 任克强,胡梦云. 基于改进SURF算子的彩色图像配准算法. 电子测量与仪器学报,2016,30(5)：748-756.

12 王海明. 基于稀疏结构和SIFT特征的SAR图像配准研究[硕士学位论文]. 西安：西安电子科技大学,2014.

13 侯跃恩,李伟光,容爱琼,等. 融合背景信息的分块稀疏表示跟踪算法. 华南理工大学学报(自然科学版),2013,41(8)：21-27.

14 Xu ZB,Sun J. Image inpainting by patch propagation using patch sparsity. IEEE Transactions on Image Processing,2010,19(5)：1153-1165. [doi：10.1109/TIP.2010.2042098]

15 李志丹,和红杰,尹忠科,等. 结合颜色和梯度信息的稀疏图像修复算法. 计算机研究与发展,2014,51(9)：2081-2093. [doi：10.7544/issn1000-1239.2014.20130071]

16 程妮. 一种基于结构稀疏度的图像块分类方法. 现代计算机,2016,(17)：71-74. [doi：10.3969/j.issn.1007-1423.2016.17.015]

17 Hu YT,Lin YY. Progressive feature matching with alternate descriptor selection and correspondence enrichment.Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas,NV,USA. 2016.346-354.