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

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

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

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

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

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

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

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

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

關鍵詞：圖像匹配;局部特征;特征描述;線圖

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

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

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

1基于譜特征的圖像匹配

1.1　譜特征

1.1.1圖譜

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

(1)

1.1.2特征點的譜特征

若僅僅利用點v及其8個鄰域點來構造圖,獲得其譜特征,則對于v的特征描述不夠充分.因此,可以取v的(2k+1)2-1個鄰域點(k為v的鄰域點層數(shù)),如圖2所示.若不加區(qū)分地將所選鄰域點全部按照1.1.1節(jié)中所描述的方法來構造圖,進而獲得v的譜特征,理論上可行,但計算復雜度非常高,因為相應的鄰接矩陣大小為4k(k+1)×4k(k+1),當k取較大值時,鄰接矩陣的構造以及譜分解的實現(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　圖像匹配

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

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

(2)

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

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

(3)

設立目標函數(shù)

(4)

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

(5)

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

(6)

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

1.3　算法性能分析

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

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

1.4　算法復雜度分析

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

2實驗與結果分析

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

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

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

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

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

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

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

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

3結論

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

參考文獻:

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

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