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

(1.安徽大學(xué) 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室, 安徽 合肥 230039; 2.安徽大學(xué) 電子信息工程學(xué)院,

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

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

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

(1.安徽大學(xué) 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室, 安徽 合肥 230039; 2.安徽大學(xué) 電子信息工程學(xué)院,

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

摘要：傳統(tǒng)基于譜圖的圖像匹配算法大多利用特征點(diǎn)集中點(diǎn)的位置關(guān)系進(jìn)行匹配,并未充分利用特征點(diǎn)周?chē)幕叶刃畔?為此,文中提出了一種基于譜特征的圖像匹配算法,該算法利用線圖譜來(lái)反映特征點(diǎn)周?chē)叶鹊淖兓?對(duì)特征點(diǎn)周?chē)泥徲螯c(diǎn)進(jìn)行分層,并對(duì)每層中的點(diǎn)構(gòu)造線圖,通過(guò)線圖譜獲取特征點(diǎn)的譜特征;理論分析表明，該譜特征具有旋轉(zhuǎn)不變性、亮度線性變化不變性及對(duì)噪聲的較高魯棒性.最后,利用匈牙利算法求解匹配問(wèn)題,輸出匹配結(jié)果.實(shí)驗(yàn)結(jié)果表明,文中算法具有較高的匹配精度,在待匹配圖像間存在較大形變時(shí),也可以獲得較好的匹配結(jié)果.

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

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

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

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

1基于譜特征的圖像匹配

1.1　譜特征

1.1.1圖譜

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

(1)

1.1.2特征點(diǎn)的譜特征

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

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

圖2　特征點(diǎn)v及其鄰域點(diǎn)Fig.2　Feature point v and its neighbors

圖3　v鄰域點(diǎn)的多個(gè)層次圖Fig.3　Several layers of v’s neighbors

1.2　圖像匹配

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

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

(2)

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

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

(3)

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

(4)

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

(5)

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

(6)

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

1.3　算法性能分析

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

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

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

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

2實(shí)驗(yàn)與結(jié)果分析

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

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

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

表2　4種算法的運(yùn)行時(shí)間對(duì)比Table2　Comparisonofrunningtimeamongfouralgorithms

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

表3　真實(shí)圖像的統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果Table3　Statisticexperimentalresultsofrealimages

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

在較大仿射變換下兩幅Boat圖像的匹配實(shí)驗(yàn)結(jié)果如圖5所示,每幅圖像選取了40個(gè)特征點(diǎn).SD算法主要利用特征點(diǎn)周?chē)泥徲蛐畔⑦M(jìn)行譜特征的構(gòu)造,當(dāng)待匹配的圖像間存在較大形變時(shí),在分層數(shù)較小的情形下,特征點(diǎn)周?chē)木植繀^(qū)域較小,受形變的影響相對(duì)較小,算法性能較為穩(wěn)定.當(dāng)分層數(shù)為16時(shí),SD算法能夠獲得35對(duì)正確匹配點(diǎn),SMT算法獲得20對(duì)正確匹配點(diǎn),而SM、HM算法受仿射變換的影響較大,分別只獲得3對(duì)和2對(duì)正確匹配點(diǎn).

3結(jié)論

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

參考文獻(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-譜的點(diǎn)模式匹配算法 [J].華南理工大學(xué)報(bào):自然科學(xué)版,2011,39(7):102-108.

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

[19]張光澄.非線性最優(yōu)化計(jì)算方法 [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

中圖分類(lèi)號(hào)：TP391

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

作者簡(jiǎn)介：朱明(1984-),男,博士,講師,主要從事計(jì)算機(jī)視覺(jué)、圖像處理、模式識(shí)別研究.E-mail: zhu_m@163.com? 通信作者： 梁棟(1963-),男,博士,教授,博士生導(dǎo)師,主要從事計(jì)算機(jī)視覺(jué)、圖像處理、模式識(shí)別研究.E-mail: dliang@ahu.edu.cn

*基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61501003,61172127,11371028,61401001);高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金資助項(xiàng)目(20113401110006);安徽大學(xué)博士科研啟動(dòng)基金資助項(xiàng)目(02303319-33190182);安徽大學(xué)青年骨干教師培養(yǎng)項(xiàng)目(023003301-12333010284)

收稿日期：2014-11-18

文章編號(hào)：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)