朱明　梁棟?　范益政　張艷　顏普

(1.安徽大學(xué) 計算智能與信號處理教育部重點實驗室, 安徽 合肥 230039; 2.安徽大學(xué) 電子信息工程學(xué)院,

安徽 合肥 230601; 3.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 安徽 合肥 230601)

基于譜特征的圖像匹配算法*

朱明1,2梁棟1,2?范益政3張艷2顏普2

(1.安徽大學(xué) 計算智能與信號處理教育部重點實驗室, 安徽 合肥 230039; 2.安徽大學(xué) 電子信息工程學(xué)院,

安徽 合肥 230601; 3.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 安徽 合肥 230601)

摘要：傳統(tǒng)基于譜圖的圖像匹配算法大多利用特征點集中點的位置關(guān)系進(jìn)行匹配,并未充分利用特征點周圍的灰度信息,為此,文中提出了一種基于譜特征的圖像匹配算法,該算法利用線圖譜來反映特征點周圍灰度的變化,對特征點周圍的鄰域點進(jìn)行分層,并對每層中的點構(gòu)造線圖,通過線圖譜獲取特征點的譜特征;理論分析表明，該譜特征具有旋轉(zhuǎn)不變性、亮度線性變化不變性及對噪聲的較高魯棒性.最后,利用匈牙利算法求解匹配問題,輸出匹配結(jié)果.實驗結(jié)果表明,文中算法具有較高的匹配精度,在待匹配圖像間存在較大形變時,也可以獲得較好的匹配結(jié)果.

關(guān)鍵詞：圖像匹配;局部特征;特征描述;線圖

圖像匹配是指通過一定的匹配算法尋找兩幅或多幅圖像中像素點之間的匹配關(guān)系,是計算機(jī)視覺、圖像處理、模式識別等領(lǐng)域的研究熱點,也是眾多相關(guān)理論研究的基礎(chǔ).根據(jù)匹配基元的不同,可以將圖像匹配方法分為3類:區(qū)域匹配、相位匹配和特征匹配方法[1],其中特征匹配方法相對于另外兩類方法具有計算量小、速度快、魯棒性高等優(yōu)點,是應(yīng)用較多的一種方法.特征匹配方法首先對圖像進(jìn)行預(yù)處理以提取其高層次的特征,然后建立兩幅圖像之間特征的匹配關(guān)系,通常使用的特征基元有點特征[2]、邊緣特征[3]和區(qū)域特征[4],其中點特征是另外兩種特征的基礎(chǔ),應(yīng)用最為廣泛.

特征點匹配問題在計算機(jī)視覺領(lǐng)域中常被作為一個圖匹配問題來處理,通過以待匹配點集中點作為頂點,頂點之間按照一定的規(guī)則條件設(shè)定邊來構(gòu)造圖,圖可以反映點之間的相互關(guān)系,是一種非常重要而有效的結(jié)構(gòu)信息表示方式.近年來,譜圖理論[5]作為一種有效的數(shù)學(xué)工具被引入到圖像匹配問題的研究中,并發(fā)揮了重要作用.文獻(xiàn)[6-7]較早地將譜方法應(yīng)用于特征點匹配,文獻(xiàn)[8]在文獻(xiàn)[6]的基礎(chǔ)上融入了特征點周圍的灰度信息,獲得了較高的匹配精度;文獻(xiàn)[9]利用不同權(quán)值函數(shù)構(gòu)造鄰接矩陣,考慮了不同權(quán)值函數(shù)對點匹配的影響,并將圖譜分析方法和期望最大化(EM)算法結(jié)合起來,通過特征點的親近矩陣來獲得特征點匹配;文獻(xiàn)[10]采用分組方法來提高譜匹配的精度;文獻(xiàn)[11]對無向賦權(quán)圖的鄰接譜進(jìn)行優(yōu)化以提高匹配精度;文獻(xiàn)[12-13]利用多重約束方法進(jìn)行特征點匹配;文獻(xiàn)[14]采用對隨機(jī)點積圖的鄰接譜進(jìn)行交替嵌入和匹配的迭代方式進(jìn)行點模式匹配;文獻(xiàn)[15]對無向賦權(quán)圖定義了近似親近矩陣,并通過計算近似親近矩陣的譜來實現(xiàn)匹配,該方法旨在提高計算速度,以適應(yīng)大規(guī)模點集的匹配;文獻(xiàn)[16]提出了一種譜上下文的局部結(jié)構(gòu)描述子,并成功用于處理點模式匹配問題,該描述子可以描述點集的屬性,對特征點的位置抖動及出格點的存在問題具有較高的魯棒性,定義了近似距離序,并用于度量近鄰點的幾何一致性,將特征點集的匹配問題轉(zhuǎn)化為在一一對應(yīng)限制條件下的優(yōu)化問題,通過概率松弛算法來求解該優(yōu)化問題;文獻(xiàn)[17]提出了一種基于有向圖模型的特征匹配方法,該方法相對于無向圖模型具有較好的判別性,以及對旋轉(zhuǎn)和縮放變換具有不變性.

上述方法大多利用特征點集中點的位置關(guān)系進(jìn)行匹配,并未充分利用特征點周圍的灰度信息,文獻(xiàn)[8]即使在譜方法中融入了特征點周圍的灰度信息,但也僅僅涉及了特征點周圍區(qū)域的灰度整體信息,如方差、均值等.在待匹配圖像間存在較大形變時,特征點周圍的局部區(qū)域相對較為穩(wěn)定,是需要充分利用的信息.為此,文中提出了一種基于譜特征的圖像匹配算法,對圖像中的特征點進(jìn)行了描述,通過圖譜來反映特征點周圍灰度的變化,從而獲得特征點的譜特征,并利用譜特征進(jìn)行特征點匹配.首先,為了降低算法的運算量,對待匹配圖像中特征點的周圍區(qū)域進(jìn)行分層;其次,在每層中構(gòu)造相應(yīng)的線圖,并計算線圖的鄰接譜;然后,結(jié)合每層的鄰接譜構(gòu)造特征點的譜特征;最后,建立相應(yīng)的數(shù)學(xué)模型,并利用匈牙利算法求解模型,輸出匹配結(jié)果.

1基于譜特征的圖像匹配

1.1　譜特征

1.1.1圖譜

通過將像素點作為頂點、頂點之間按照一定的規(guī)則條件設(shè)定邊來構(gòu)造的圖,可以反映點之間的相互關(guān)系,是一種非常重要而有效的結(jié)構(gòu)信息表示方式.在一幅大小為m×n的圖像I中取定一個非邊界點v,v的特征可以由v與其鄰域點的屬性值間的相互關(guān)系來確定,因此,可以利用圖的性質(zhì)來反映v的特征.

(1)

1.1.2特征點的譜特征

若僅僅利用點v及其8個鄰域點來構(gòu)造圖,獲得其譜特征,則對于v的特征描述不夠充分.因此,可以取v的(2k+1)2-1個鄰域點(k為v的鄰域點層數(shù)),如圖2所示.若不加區(qū)分地將所選鄰域點全部按照1.1.1節(jié)中所描述的方法來構(gòu)造圖,進(jìn)而獲得v的譜特征,理論上可行,但計算復(fù)雜度非常高,因為相應(yīng)的鄰接矩陣大小為4k(k+1)×4k(k+1),當(dāng)k取較大值時,鄰接矩陣的構(gòu)造以及譜分解的實現(xiàn)都需要很高的計算代價.

圖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　圖像匹配

設(shè)I與J是兩幅待匹配圖像,v1,v2,…,vs為I中的s個特征點,u1,u2,…,us為J中的s個特征點,分別利用1.1.2節(jié)中的方法計算所選擇特征點的譜特征.構(gòu)造I與J的特征點之間的相似度矩陣C,其元素為

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

(2)

其中cij表示vi與uj特征之間的距離.

令pij表示vi是否與uj匹配的狀況,即

(3)

設(shè)立目標(biāo)函數(shù)

(4)

為了實現(xiàn)一一對應(yīng),設(shè)定下述約束條件:

(5)

求解最優(yōu)匹配關(guān)系實際上是一個0-1規(guī)劃問題,相應(yīng)的數(shù)學(xué)模型為

(6)

文中采用匈牙利算法[19]求解上述模型.文中算法的具體步驟如下:①利用Harris算法提取待匹配圖像I與J的特征點;②對每個特征點利用1.1.2節(jié)中的方法計算譜特征;③利用所獲得的譜特征根據(jù)式(2)構(gòu)造匹配矩陣C;④建立相應(yīng)的數(shù)學(xué)模型;⑤利用匈牙利算法求解模型,輸出匹配結(jié)果.

1.3　算法性能分析

文中算法主要依賴于所構(gòu)造的譜特征,該譜特征的性質(zhì)主要體現(xiàn)在以下幾方面.

(1)旋轉(zhuǎn)不變性.文中的譜特征是利用特征點的鄰域點構(gòu)造圖,通過對圖的鄰接矩陣進(jìn)行譜分解獲得相應(yīng)的譜特征,而矩陣的譜分解具有置換不變性,因此該譜特征對旋轉(zhuǎn)具有不變性.

1.4　算法復(fù)雜度分析

在生成特征之后,匹配的計算復(fù)雜度來自于匈牙利算法,匈牙利算法的計算復(fù)雜度為O(bd),其中d為點數(shù),b為邊數(shù).在本算法中構(gòu)造的完全二部圖,在待匹配特征點均為d的情形下,b=d2,因此計算復(fù)雜度為O(d3).

2實驗與結(jié)果分析

實驗圖像取自于CMU/VASC圖像數(shù)據(jù)庫的圖像序列,選取了第0、5、10、15、20、25、30、35、60幀共9幅圖像(第0幀為原圖像),對每幅圖像提取40個特征點進(jìn)行實驗.選用SMT算法[11]、SM算法[12]、HM算法[13]與文中算法(SD算法)進(jìn)行對比,SM算法和HM算法均取σ=300.第0幀與第60幀圖像的正確匹配點數(shù)隨著分層數(shù)的變化如表1所示,可以發(fā)現(xiàn),獲得正確匹配的點數(shù)隨著分層數(shù)的增加而增加,在第0幀、第60幀的實驗中,當(dāng)分層數(shù)達(dá)到17時,所選取的40個特征點均能獲得正確的匹配.

4種方法在第0幀與第60幀圖像的100次匹配實驗中的平均運行時間如表2所示，運行平臺為Matlab(R2012b),電腦配置為Intel(R)Core(TM)i7- 4790CPU@3.6GHz、8核、16GB內(nèi)存.從表2可見,HM算法的運行時間較短,融入矩陣分解、優(yōu)化迭代的SM、SMT算法的運行時間較長.SD算法的運行時間隨著分層數(shù)k的增大而增加,當(dāng)k=12時,匹配正確率為90%,高于其他3種算法,運行時間也最短.

表1　第0幀與第60幀圖像的正確匹配點數(shù)隨著分層數(shù)的變化Table1　Changesofthenumberofcorrectmatchingpointsofthe0thand60thframeswiththenumberoflayers

表2　4種算法的運行時間對比Table2　Comparisonofrunningtimeamongfouralgorithms

表3是所選取圖像序列的實驗統(tǒng)計結(jié)果,以第60幀圖像作為基準(zhǔn)圖像,其他圖像與之進(jìn)行匹配,實驗中SD算法采用的分層數(shù)為16.根據(jù)統(tǒng)計結(jié)果,當(dāng)幀數(shù)差減少時,兩幅圖像的視角差變小,正確匹配的點數(shù)增加,SD算法相對于SM、HM、SMT算法具有較好的匹配效果,SMT算法的匹配效果要略優(yōu)于SM、HM算法,當(dāng)兩幅圖像的幀數(shù)差小于等于30時,4種算法均能獲得100%的匹配正確率.部分實驗結(jié)果如圖4所示.

表3　真實圖像的統(tǒng)計實驗結(jié)果Table3　Statisticexperimentalresultsofrealimages

圖4　部分真實圖像的實驗結(jié)果Fig.4　Some experimental results of real images

在較大仿射變換下兩幅Boat圖像的匹配實驗結(jié)果如圖5所示,每幅圖像選取了40個特征點.SD算法主要利用特征點周圍的鄰域信息進(jìn)行譜特征的構(gòu)造,當(dāng)待匹配的圖像間存在較大形變時,在分層數(shù)較小的情形下,特征點周圍的局部區(qū)域較小,受形變的影響相對較小,算法性能較為穩(wěn)定.當(dāng)分層數(shù)為16時,SD算法能夠獲得35對正確匹配點,SMT算法獲得20對正確匹配點,而SM、HM算法受仿射變換的影響較大,分別只獲得3對和2對正確匹配點.

3結(jié)論

文中提出了一種基于譜特征的圖像匹配算法,該算法通過對圖像中特征點的描述和圖譜來反映特征點周圍灰度的變化,從而獲得特征點的譜特征,并利用譜特征進(jìn)行特征點匹配.理論分析結(jié)果表明,所獲得的譜特征具有旋轉(zhuǎn)不變性、亮度線性變化不變性及對噪聲的高魯棒性;實驗結(jié)果表明,文中算法具有較高的匹配精度,可以處理具有較大形變圖像的匹配問題.但文中的區(qū)域劃分較簡單,在降低算法運算量的同時丟失了一部分信息(如不同層的像素點之間的關(guān)系),今后擬尋找更好的區(qū)域劃分方法,以在確保算法運算量的同時盡可能反映出更多的信息.

參考文獻(xiàn):

[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].華南理工大學(xué)報:自然科學(xué)版,2011,39(7):102-108.

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

[19]張光澄.非線性最優(yōu)化計算方法 [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-),男,博士,講師,主要從事計算機(jī)視覺、圖像處理、模式識別研究.E-mail: zhu_m@163.com? 通信作者： 梁棟(1963-),男,博士,教授,博士生導(dǎo)師,主要從事計算機(jī)視覺、圖像處理、模式識別研究.E-mail: dliang@ahu.edu.cn

*基金項目：國家自然科學(xué)基金資助項目(61501003,61172127,11371028,61401001);高等學(xué)校博士學(xué)科點專項科研基金資助項目(20113401110006);安徽大學(xué)博士科研啟動基金資助項目(02303319-33190182);安徽大學(xué)青年骨干教師培養(yǎng)項目(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)