基于谱特征的图像匹配算法*

朱明　梁栋†　范益政　张艳　颜普

(1.安徽大学 计算智能与信号处理教育部重点实验室, 安徽 合肥 230039; 2.安徽大学 电子信息工程学院,

安徽 合肥 230601; 3.安徽大学 数学科学学院, 安徽 合肥 230601)

基于谱特征的图像匹配算法*

朱明1,2梁栋1,2†范益政3张艳2颜普2

(1.安徽大学 计算智能与信号处理教育部重点实验室, 安徽 合肥 230039; 2.安徽大学 电子信息工程学院,

安徽 合肥 230601; 3.安徽大学 数学科学学院, 安徽 合肥 230601)

摘要：传统基于谱图的图像匹配算法大多利用特征点集中点的位置关系进行匹配,并未充分利用特征点周围的灰度信息,为此,文中提出了一种基于谱特征的图像匹配算法,该算法利用线图谱来反映特征点周围灰度的变化,对特征点周围的邻域点进行分层,并对每层中的点构造线图,通过线图谱获取特征点的谱特征;理论分析表明，该谱特征具有旋转不变性、亮度线性变化不变性及对噪声的较高鲁棒性.最后,利用匈牙利算法求解匹配问题,输出匹配结果.实验结果表明,文中算法具有较高的匹配精度,在待匹配图像间存在较大形变时,也可以获得较好的匹配结果.

关键词：图像匹配;局部特征;特征描述;线图

图像匹配是指通过一定的匹配算法寻找两幅或多幅图像中像素点之间的匹配关系,是计算机视觉、图像处理、模式识别等领域的研究热点,也是众多相关理论研究的基础.根据匹配基元的不同,可以将图像匹配方法分为3类:区域匹配、相位匹配和特征匹配方法[1],其中特征匹配方法相对于另外两类方法具有计算量小、速度快、鲁棒性高等优点,是应用较多的一种方法.特征匹配方法首先对图像进行预处理以提取其高层次的特征,然后建立两幅图像之间特征的匹配关系,通常使用的特征基元有点特征[2]、边缘特征[3]和区域特征[4],其中点特征是另外两种特征的基础,应用最为广泛.

特征点匹配问题在计算机视觉领域中常被作为一个图匹配问题来处理,通过以待匹配点集中点作为顶点,顶点之间按照一定的规则条件设定边来构造图,图可以反映点之间的相互关系,是一种非常重要而有效的结构信息表示方式.近年来,谱图理论[5]作为一种有效的数学工具被引入到图像匹配问题的研究中,并发挥了重要作用.文献[6-7]较早地将谱方法应用于特征点匹配,文献[8]在文献[6]的基础上融入了特征点周围的灰度信息,获得了较高的匹配精度;文献[9]利用不同权值函数构造邻接矩阵,考虑了不同权值函数对点匹配的影响,并将图谱分析方法和期望最大化(EM)算法结合起来,通过特征点的亲近矩阵来获得特征点匹配;文献[10]采用分组方法来提高谱匹配的精度;文献[11]对无向赋权图的邻接谱进行优化以提高匹配精度;文献[12-13]利用多重约束方法进行特征点匹配;文献[14]采用对随机点积图的邻接谱进行交替嵌入和匹配的迭代方式进行点模式匹配;文献[15]对无向赋权图定义了近似亲近矩阵,并通过计算近似亲近矩阵的谱来实现匹配,该方法旨在提高计算速度,以适应大规模点集的匹配;文献[16]提出了一种谱上下文的局部结构描述子,并成功用于处理点模式匹配问题,该描述子可以描述点集的属性,对特征点的位置抖动及出格点的存在问题具有较高的鲁棒性,定义了近似距离序,并用于度量近邻点的几何一致性,将特征点集的匹配问题转化为在一一对应限制条件下的优化问题,通过概率松弛算法来求解该优化问题;文献[17]提出了一种基于有向图模型的特征匹配方法,该方法相对于无向图模型具有较好的判别性,以及对旋转和缩放变换具有不变性.

上述方法大多利用特征点集中点的位置关系进行匹配,并未充分利用特征点周围的灰度信息,文献[8]即使在谱方法中融入了特征点周围的灰度信息,但也仅仅涉及了特征点周围区域的灰度整体信息,如方差、均值等.在待匹配图像间存在较大形变时,特征点周围的局部区域相对较为稳定,是需要充分利用的信息.为此,文中提出了一种基于谱特征的图像匹配算法,对图像中的特征点进行了描述,通过图谱来反映特征点周围灰度的变化,从而获得特征点的谱特征,并利用谱特征进行特征点匹配.首先,为了降低算法的运算量,对待匹配图像中特征点的周围区域进行分层;其次,在每层中构造相应的线图,并计算线图的邻接谱;然后,结合每层的邻接谱构造特征点的谱特征;最后,建立相应的数学模型,并利用匈牙利算法求解模型,输出匹配结果.

1基于谱特征的图像匹配

1.1　谱特征

1.1.1图谱

通过将像素点作为顶点、顶点之间按照一定的规则条件设定边来构造的图,可以反映点之间的相互关系,是一种非常重要而有效的结构信息表示方式.在一幅大小为m×n的图像I中取定一个非边界点v,v的特征可以由v与其邻域点的属性值间的相互关系来确定,因此,可以利用图的性质来反映v的特征.

(1)

1.1.2特征点的谱特征

若仅仅利用点v及其8个邻域点来构造图,获得其谱特征,则对于v的特征描述不够充分.因此,可以取v的(2k+1)2-1个邻域点(k为v的邻域点层数),如图2所示.若不加区分地将所选邻域点全部按照1.1.1节中所描述的方法来构造图,进而获得v的谱特征,理论上可行,但计算复杂度非常高,因为相应的邻接矩阵大小为4k(k+1)×4k(k+1),当k取较大值时,邻接矩阵的构造以及谱分解的实现都需要很高的计算代价.

图1　原图像及其特征值图像Fig.1　Original image and its images related to eigenvalues

图2　特征点v及其邻域点Fig.2　Feature point v and its neighbors

图3　v邻域点的多个层次图Fig.3　Several layers of v’s neighbors

1.2　图像匹配

设I与J是两幅待匹配图像,v1,v2,…,vs为I中的s个特征点,u1,u2,…,us为J中的s个特征点,分别利用1.1.2节中的方法计算所选择特征点的谱特征.构造I与J的特征点之间的相似度矩阵C,其元素为

cij=‖fI(vi)-fJ(uj)‖,i,j=1,2,…,s

(2)

其中cij表示vi与uj特征之间的距离.

令pij表示vi是否与uj匹配的状况,即

(3)

设立目标函数

(4)

为了实现一一对应,设定下述约束条件:

(5)

求解最优匹配关系实际上是一个0-1规划问题,相应的数学模型为

(6)

文中采用匈牙利算法[19]求解上述模型.文中算法的具体步骤如下:①利用Harris算法提取待匹配图像I与J的特征点;②对每个特征点利用1.1.2节中的方法计算谱特征;③利用所获得的谱特征根据式(2)构造匹配矩阵C;④建立相应的数学模型;⑤利用匈牙利算法求解模型,输出匹配结果.

1.3　算法性能分析

文中算法主要依赖于所构造的谱特征,该谱特征的性质主要体现在以下几方面.

(1)旋转不变性.文中的谱特征是利用特征点的邻域点构造图,通过对图的邻接矩阵进行谱分解获得相应的谱特征,而矩阵的谱分解具有置换不变性,因此该谱特征对旋转具有不变性.

1.4　算法复杂度分析

在生成特征之后,匹配的计算复杂度来自于匈牙利算法,匈牙利算法的计算复杂度为O(bd),其中d为点数,b为边数.在本算法中构造的完全二部图,在待匹配特征点均为d的情形下,b=d2,因此计算复杂度为O(d3).

2实验与结果分析

实验图像取自于CMU/VASC图像数据库的图像序列,选取了第0、5、10、15、20、25、30、35、60帧共9幅图像(第0帧为原图像),对每幅图像提取40个特征点进行实验.选用SMT算法[11]、SM算法[12]、HM算法[13]与文中算法(SD算法)进行对比,SM算法和HM算法均取σ=300.第0帧与第60帧图像的正确匹配点数随着分层数的变化如表1所示,可以发现,获得正确匹配的点数随着分层数的增加而增加,在第0帧、第60帧的实验中,当分层数达到17时,所选取的40个特征点均能获得正确的匹配.

4种方法在第0帧与第60帧图像的100次匹配实验中的平均运行时间如表2所示，运行平台为Matlab(R2012b),电脑配置为Intel(R)Core(TM)i7- 4790CPU@3.6GHz、8核、16GB内存.从表2可见,HM算法的运行时间较短,融入矩阵分解、优化迭代的SM、SMT算法的运行时间较长.SD算法的运行时间随着分层数k的增大而增加,当k=12时,匹配正确率为90%,高于其他3种算法,运行时间也最短.

表1　第0帧与第60帧图像的正确匹配点数随着分层数的变化Table1　Changesofthenumberofcorrectmatchingpointsofthe0thand60thframeswiththenumberoflayers

表2　4种算法的运行时间对比Table2　Comparisonofrunningtimeamongfouralgorithms

表3是所选取图像序列的实验统计结果,以第60帧图像作为基准图像,其他图像与之进行匹配,实验中SD算法采用的分层数为16.根据统计结果,当帧数差减少时,两幅图像的视角差变小,正确匹配的点数增加,SD算法相对于SM、HM、SMT算法具有较好的匹配效果,SMT算法的匹配效果要略优于SM、HM算法,当两幅图像的帧数差小于等于30时,4种算法均能获得100%的匹配正确率.部分实验结果如图4所示.

表3　真实图像的统计实验结果Table3　Statisticexperimentalresultsofrealimages

图4　部分真实图像的实验结果Fig.4　Some experimental results of real images

在较大仿射变换下两幅Boat图像的匹配实验结果如图5所示,每幅图像选取了40个特征点.SD算法主要利用特征点周围的邻域信息进行谱特征的构造,当待匹配的图像间存在较大形变时,在分层数较小的情形下,特征点周围的局部区域较小,受形变的影响相对较小,算法性能较为稳定.当分层数为16时,SD算法能够获得35对正确匹配点,SMT算法获得20对正确匹配点,而SM、HM算法受仿射变换的影响较大,分别只获得3对和2对正确匹配点.

3结论

文中提出了一种基于谱特征的图像匹配算法,该算法通过对图像中特征点的描述和图谱来反映特征点周围灰度的变化,从而获得特征点的谱特征,并利用谱特征进行特征点匹配.理论分析结果表明,所获得的谱特征具有旋转不变性、亮度线性变化不变性及对噪声的高鲁棒性;实验结果表明,文中算法具有较高的匹配精度,可以处理具有较大形变图像的匹配问题.但文中的区域划分较简单,在降低算法运算量的同时丢失了一部分信息(如不同层的像素点之间的关系),今后拟寻找更好的区域划分方法,以在确保算法运算量的同时尽可能反映出更多的信息.

参考文献:

[1]CaiLD,MayhewJ.Anoteonsomephasedifferencingalgorithmsfordisparityestimation[J].InternationalJournalofComputerVision,1997,22(2):111-124.

[2]LiJ.Animagefeaturepointmatchingalgorithmbasedonfixedscalefeaturetransformationoriginal[J].Optik-InternationalJournalforLightandElectronOptics,2013,124(13):1620-1623.

[3]PremaratneP,PremaratneM.Imagematchingusingmomentinvariants[J].Neurocomputing,2014,137:65-70.

[4]YammenS,MuneesawangP.Cartridgecaseimagematchingusingeffectivecorrelationareabasedmethod[J].ForensicScienceInternational,2013,229(1/2/3):27- 42.

[5]FanRKChung.Spectralgraphtheory[M].WashingtonDC:AmericanMathematicalSociety,1997.

[6]ScottGL,Longuet-HigginsHC.Analgorithmforassociatingthefeaturesoftwoimages[J].ProceedingsoftheRoyalSocietyofLondonSeriesB：BiologicalSciencesB,1991,244(1309):21-26.

[7]ShapiroLS,BradyJM.Feature-basedcorrespondence：aneigenvectorapproach[J].ImageVisionComputing,1992,10(5):283-288.

[8]PiluM.Adirectmethodforstereocorrespondencebasedonsingularvaluedecomposition[C]∥ProceedingsofIEEEConferenceonComputerVisionandPatternRecognition.SanJuan:IEEE,1997:261-266.

[9]CarcassoniM,HancockER.Spectralcorrespondenceforpointpatternmatching[J].PatternRecognition,2003,36(1):193-204.

[10]CarcassoniM,HancockER.Correspondencematchingwithmodalclusters[J].IEEEPatternAnalysisandMachineIntelligence,2003,25(12):1609-1615.

[11]FengW,LiuZQ,WanL,etal.Spectral-multiplicity-to-lerantapproachtorobustgraphmatching[J].PatternRecognition,2013,46(10):2819-2829.

[12]LeordeanuM,HebertM.Aspectraltechniqueforcorrespondenceproblemsusingpairwiseconstraints[C]∥ProceedingsofInternationalConferenceonComputerVision.Beijing:IEEE,2005:1482-1489.

[13]ZassR,ShashuaA.Probabilisticgraphandhypergraphmatching[C]∥ProceedingsofIEEEConferenceonComputerVisionandPatternRecognition.Anchorage:IEEE,2008:1221-1228.

[14]TangJ,JiangB,ZhengAH,etal.Graphmatchingbasedonspectralembeddingwithmissingvalue[J].PatternRecognition,2012,45(10):3768-3779.

[15]KangU,HebertM,ParkS.Fastandscalableapproximatespectralgraphmatchingforcorrespondenceproblems[J].InformationSciences,2013,220:306-318.

[16]TangJ,ShaoL,ZhenXT.Robustpointpatternmat-chingbasedonspectralcontext[J].PatternRecognition,2014,47(3):1469-1484.

[17]YangX,QiaoH,LiuZY.Featurecorrespondencebasedondirectedstructuralmodelmatching[J].ImageandVisionComputing,2015,33:57- 67.

[18]朱明,梁栋,唐俊,等.基于线图Q-谱的点模式匹配算法 [J].华南理工大学报:自然科学版,2011,39(7):102-108.

ZhuMing,LiangDong,TangJun,etal.PointpatternmatchingalgorithmbasedonQ-spectrumoflinegraph[J].JournalofSouthChinaUniversityofTechnology:NaturalScienceEdition,2011,39(7):102-108.

[19]张光澄.非线性最优化计算方法 [M].北京:高等教育出版社,2005:227-229.

[20]HoffmanAJ,WielandtHW.Thevariationofthespectrumofanormalmatrix[J].DukeMathematicalJournal,1953,20:37-39.

An Image Matching Algorithm Based on Spectral Features

ZhuMing1,2LiangDong1,2FanYi-zheng3ZhangYan2YanPu2

(1. Key Laboratory Intelligent Computing and Signal Processing of the Ministry of Education, Anhui University, Hefei 230039,

Anhui, China; 2. School of Electronics and Information Engineering, Anhui University, Hefei 230601, Anhui, China;

3. School of Mathematical Sciences, Anhui University, Hefei 230601, Anhui, China)

Abstract:The traditional image matching algorithm based on spectral graph usually matches the points with the position relationship of feature points, and the gray information around feature points is not fully utilized. In order to solve this problem, this paper proposes an image matching algorithm based on spectral features. This algorithm uses the spectrum of line graph to reflect the changes of the gray level around feature points, stratifies the neighbors of each feature point, and then constructs a line graph for the points of each layer. Thus, the spectral features of feature points are obtained from the spectrum of line graph. Theoretical analysis demonstrates that the spectral features are of rotation invariance, linear brightness variation invariance and strong robustness to noise. Finally, the Hungarian algorithm is used to solve the matching problem and output the matching results. Experimental results show that the proposed algorithm has a high matching accuracy, and it can also achieve better matching results under a larger deformation between the two images to be matched.

Key words:image matching; local feature; feature description; line graph

中图分类号：TP391

doi：10.3969/j.issn.1000-565X.2015.09.010

作者简介：朱明(1984-),男,博士,讲师,主要从事计算机视觉、图像处理、模式识别研究.E-mail: zhu_m@163.com† 通信作者： 梁栋(1963-),男,博士,教授,博士生导师,主要从事计算机视觉、图像处理、模式识别研究.E-mail: dliang@ahu.edu.cn

*基金项目：国家自然科学基金资助项目(61501003,61172127,11371028,61401001);高等学校博士学科点专项科研基金资助项目(20113401110006);安徽大学博士科研启动基金资助项目(02303319-33190182);安徽大学青年骨干教师培养项目(023003301-12333010284)

收稿日期：2014-11-18

文章编号：1000-565X(2015)09-0060-07

Foundation items： Supported by the National Natural Science Foundation of China(61172127,11371028,61501003,61401001) and the Specialized Research Fund for the Doctoral Program of Higher Education of China(20113401110006)