基于橢圓形度量譜特征的圖像匹配算法

鮑文霞 余國芬 朱 明 梁 棟

(1安徽大學計算智能與信號處理教育部重點實驗室，合肥 230039 )(2中國人民解放軍陸軍軍官學院偏振光成像探測技術安徽省重點實驗室，合肥 230031)

圖像匹配是計算機視覺中的一個關鍵問題,在圖像分類與檢索、運動分析、立體視覺和三維重建等領域有著重要的應用．近年來,譜圖理論作為一種高效的數(shù)學描述工具被廣泛應用于圖像匹配問題中[1-4]．Leordeanu等[5]根據(jù)歐式度量構造特征點集的親近矩陣,并對親近矩陣進行譜分解,通過計算主特征向量之間的相似性來獲得匹配關系;在此基礎上,Yuan等[6]提出了權重投票策略,從而提高了譜特征匹配速度;Tang等[7]根據(jù)特征點之間的歐式距離關系,構造譜上下文結構描述符,然后定義近似距離序,將匹配問題轉(zhuǎn)化為優(yōu)化問題,該算法對特征點位置抖動具有一定的魯棒性;朱明等[8]基于特征點鄰域的灰度信息構造線圖,并定義其鄰接矩陣,通過對鄰接矩陣進行譜分解獲得譜特征,利用匈牙利算法求解匹配關系,提高了特征點集大小不同時的匹配精度;Yan等[9]根據(jù)特征點鄰域點構造有向圖的無符號Laplace矩陣,并對矩陣進行譜分解以獲得譜特征,將譜特征、譜隙向量和非抽樣Contourlet變換相結合,得到單調(diào)強度不變描述子,由于圖及其鄰接矩陣是基于鄰域強度值的相對關系建立的,因此得到的單調(diào)強度不變描述子對亮度變化具有魯棒性．

上述基于譜特征的圖像匹配算法在構造譜特征及度量譜特征相似性時采用的都是歐式度量,但歐式度量將輸入的樣本空間看成是各向同性的,這種假設在實際應用中并不成立,不能公平反映數(shù)據(jù)樣本維度分量之間的潛在關系．因此,研究者們在圖像匹配問題中采用考慮樣本維度分量間相關性的馬氏度量代替歐式度量．例如,Bo等[10]為了克服傳統(tǒng)圖變換匹配算法中存在的問題,提出了一種基于馬氏度量的加權圖變換匹配算法,對特征點構造K近鄰接圖,利用馬氏度量的中位數(shù)以及特征點與K近鄰點之間的夾角距離來計算權重矩陣,從而獲得匹配點對;Famouri等[11]在匹配點對上進行馬氏度量學習,得到幾何特性的分布,剔除其中的錯誤匹配,從而提高匹配精度．

采用馬氏度量的匹配算法雖然提高了匹配精度,但馬氏度量線性變換的局限性導致其不能描述樣本潛在的非線性關系,限制其實際應用范圍．為了拓寬基于譜特征的圖像匹配算法的應用范圍,引入對樣本數(shù)據(jù)具有更好區(qū)分性的橢圓形幾何,它具有能夠反映樣本空間結構信息或語義信息的分式線性變換;根據(jù)數(shù)據(jù)統(tǒng)計特性定義了橢圓形度量;利用橢圓形距離度量特征點之間的局部關系,獲取特征點的橢圓形度量譜特征;根據(jù)譜特征之間的相似性構造匹配矩陣,利用貪心算法求解匹配結果．

1 橢圓形度量

1.1 橢圓形幾何

給出一個半正定對稱矩陣G∈R(n+1)×(n+1),由該矩陣誘導出的特征向量x,y∈Rn的雙線性形式[12]為

(1)

式中,(xT,1)表示特征x的齊次坐標；G為半正定矩陣.令En={x∈Rn:σxx>0},定義ρ為

(2)

式中,k為與G相關的常數(shù)．

在En上,ρ滿足度量公理,即同時滿足如下4個條件:① 非負性,即ρ(x,y)≥0;② 同一性,即ρ(x,y)=0?x=y;③ 對稱性,即ρ(x,y)?ρ(y,x);④ 三角不等式,即ρ(x,z)≤ρ(x,y)+ρ(y,z)．因此,ρ為En上的度量．將(En,ρ)稱為橢圓形幾何,1/k為橢圓幾何空間的曲率．

1.2 橢圓形度量矩陣

給定一個半正定對稱矩陣G便可確定一個橢圓形度量ρG,此時稱G為橢圓形度量矩陣．

對于給定數(shù)據(jù)集X,其均值向量及協(xié)方差矩陣的廣義逆分別記為u和C．為了反映樣本空間結構信息,根據(jù)數(shù)據(jù)集的統(tǒng)計特征,定義橢圓形度量矩陣G為

(3)

式中,常數(shù)b的取值應使G為半正定矩陣．

數(shù)據(jù)集中任意2個樣本點x和y的橢圓形距離度量公式為

(4)

式中

(5)

式中,?x∈X,有σxx>0．

已知x和y之間的馬氏距離為

(6)

由式(4)可得

(7)

根據(jù)Euler公式可得

(8)

式中

由此可得

(9)

在橢圓形度量中,1/b為橢圓形幾何空間的曲率．而馬氏度量幾何是平坦的,其曲率為0．因此,當b→∞時,橢圓形幾何的曲率趨于0,即馬氏度量為橢圓形度量的極限形式．

2 橢圓形度量譜特征

假設I和J為2幅待匹配的圖像.圖像I中有s個特征點,記為點集P={u1,u2,…,us};圖像J中有s′個特征點,記為點集Q={v1,v2,…,vs′}．圖像中任意一個特征點的特征屬性可以用該點與其鄰近特征點之間的相互關系來描述．下面以特征點集P中的特征點ui為例,給出橢圓形度量譜特征的構造過程．

首先計算點集的平均最小橢圓形距離du為

(10)

式中,橢圓形度量矩陣GP由對應點集P計算得到．

定義半徑集Ru={rα|rα=αdu,α=1,2,…,5}.對于任意rα∈Ru,在點集P上選擇與特征點ui的橢圓形距離小于rα的特征點,構成ui的一個子特征點集Ωiα,即Ωiα={ul:ul∈P且ρGP(ui,ul)

其次,對子特征點集Ωiα構造無向加權圖,并根據(jù)橢圓形度量計算其關聯(lián)矩陣為

(11)

式中,β為常數(shù)因子,用于控制特征點之間的相互作用．

然后,對關聯(lián)矩陣Hiα進行譜分解可得

(12)

為了避免不等長向量之間的比較,基于特征值向量和譜隙向量的統(tǒng)計量來獲得定長的譜特征描述．計算Aiα的最大值Fm(Aiα)、平均值Fa(Aiα)和方差Fv(Aiα),計算公式為

(13)

特征點ui的橢圓形度量譜特征可用一個特征向量來表示,即

3 特征匹配

設特征點集P中特征點ui和特征點集Q中特征點vj的橢圓形度量譜特征向量分別為Ai和Bj,則匹配矩陣M的非對角元素Mij,ij定義為Ai,Bj之間的相似性,可由橢圓形度量計算得到，即

(14)

匹配矩陣M的非對角元素Mij,i′j′定義為特征點之間的幾何距離,即

(15)

式中，pii′,qjj′分別表示點集P,Q中任意2個特征點之間的橢圓形距離,即pii′=ρGP(ui,ui′),qjj′=ρGQ(vj,vj′),其中,ρGP,ρGQ為特征點之間的橢圓形距離,GP,GQ為點集P,Q的橢圓形度量矩陣;ρG″為pii′,qjj′之間的橢圓形距離,其中G″為特征點集P和Q構成的數(shù)據(jù)集的橢圓形度量矩陣．

根據(jù)構造的匹配矩陣M,采用通用的匹配數(shù)學模型[13-14],可將特征匹配問題描述為

(16)

式中,w為二進制分配矩陣W的列向量形式．當圖像I中特征點ui和圖像J中特征點vj匹配時,Wij為單位矩陣,否則Wij為零矩陣．

求解匹配問題轉(zhuǎn)換為求分配向量w*使式(16)中的目標函數(shù)最大化．采用貪心算法[5]求解該匹配數(shù)學模型,得到匹配結果．

4 算法流程

基于橢圓形度量譜特征的圖像匹配算法流程如下:

① 在待匹配圖像的特征點集中分別計算橢圓形度量矩陣;

② 為每個特征點構造橢圓形度量譜特征;

③ 利用橢圓形度量譜特征之間的相似性以及特征點之間的幾何距離計算匹配矩陣;

④ 根據(jù)通用的匹配數(shù)學模型,采用貪心算法求解匹配關系．

5 實驗結果與分析

為了驗證基于橢圓形度量譜特征的圖像匹配算法(EMSM算法)的性能,分別對模擬數(shù)據(jù)和真實圖像進行了實驗．

5.1 模擬數(shù)據(jù)實驗結果

首先,生成模擬數(shù)據(jù)點集P和Q．點集P由二維平面內(nèi)服從高斯分布N(0,1)的隨機點集構成,共計40個點．點集Q由點集P中的點經(jīng)過旋轉(zhuǎn)和平移變換并疊加一定的高斯噪聲得到,其中旋轉(zhuǎn)和平移變換的參數(shù)為一定范圍內(nèi)的隨機值,旋轉(zhuǎn)角度θ∈[-π,π],在x軸和y軸上的平移量t∈[-1,1],高斯噪聲的均值為0,方差為點集中最近距離平均值的倍數(shù)．然后,分別采用EMSM算法、SPCM算法[7]、SMT算法[2]以及SM算法[5]在模擬數(shù)據(jù)上進行100次獨立實驗,將匹配正確率的平均值作為實驗結果(見圖1)．由圖可知,噪聲改變時,EMSM算法仍然能夠保持較高的匹配精度,SM算法則受噪聲影響最嚴重．EMSM算法對噪聲具有較高的魯棒性,究其原因在于引入了對數(shù)據(jù)具有更好區(qū)分性的橢圓形度量來構造譜特征．

圖1 4種算法正確率隨噪聲變化曲線圖

5.2 真實圖像匹配結果

為驗證橢圓形度量譜特征的性能,采用CMU/VASC圖像數(shù)據(jù)庫中的序列圖像進行實驗．以hotel圖像序列中第0,10,20,30,40,50,60幀為例,在每幀圖像上提取40個特征點,分別用EMSM算法和MIID算法[9]對特征點構造譜特征,然后采用相同的匹配數(shù)學模型以及貪心算法將其余幀分別與第0幀進行匹配,實驗結果見圖2和表1．從實驗數(shù)據(jù)分析可得,EMSM算法較MIID算法具有更高的匹配精度,第60幀時仍然能夠達到100%的正確匹配率;僅第0和50幀的匹配精度沒有達到100%,這是因為其中2個特征點的位置基本重疊．

(a) 第0,10幀圖像匹配

(b) 第0,30幀圖像匹配

(c) 第0,50幀圖像匹配

(d) 第0,60幀圖像匹配圖2 4種算法在hotel圖像上的匹配實驗結果

表1 hotel圖像匹配實驗數(shù)據(jù)

其次,為了驗證基于橢圓形度量譜特征的圖像匹配算法的應用范圍,利用graffiti6圖像集中視角變化較大的2幅圖像進行匹配算法對比實驗．在每幅圖像中提取40個特征點,分別利用EMSM算法、SPCM算法[7]、SMT算法[2]以及SM算法[5]進行匹配,實驗結果見圖3和表2．從實驗數(shù)據(jù)分析可得,EMSM算法在視角變化較大情況下正確匹配率仍然保持100%．因此,EMSM算法對視角變化具有不變性．

(a) EMSM算法 (b) SPCM算法

(c) SMT算法 (d) SM算法圖3 4種算法在graffiti6圖像上的匹配實驗結果

表2 graffiti6圖像匹配實驗數(shù)據(jù)

然后,采用具有較大形變的2幅Boat圖像進行匹配實驗．在每幅圖像中提取40個特征點,分別用EMSM算法、SPCM算法[7]、SMT算法[2]以及SM算法[5]進行匹配,結果見圖4和表3．從實驗數(shù)據(jù)分析可得,EMSM算法匹配精度為100%,SPCM算法匹配精度次之,SMT算法的匹配精度僅為50%,SM算法的匹配精度最低．由此可知,EMSM算法對形變具有不變性．

(a) EMSM算法 (b) SPCM算法

(c) SMT算法 (d) SM算法圖4 4種算法在Boat圖像上的匹配實驗結果

表3 Boat圖像匹配實驗數(shù)據(jù)

定義的橢圓形度量具有能夠反應特征空間結構信息或語音信息的分式線性變換,對特征具有良好的區(qū)分性,能夠較為準確地對特征點之間的潛在關系進行建模．所構造的橢圓形度量譜特征根據(jù)特征點之間的相對橢圓形距離選擇子特征點集,而平移和旋轉(zhuǎn)變換不會改變特征點之間的相對距離,故橢圓形度量譜特征具有平移不變性、旋轉(zhuǎn)不變性以及尺度不變性．因此,基于橢圓形度量譜特征的圖像匹配算法在序列圖像以及視角變換、形變較大圖像匹配中基本上都能達到100%的匹配準確率,高于其他對比算法．

6 結論

1) 針對歐式度量不能反映數(shù)據(jù)維度分量之間的潛在關系以及馬氏度量不能描述樣本潛在非線性關系的缺點,定義了一種橢圓形度量．該度量能夠反映樣本空間結構信息或語義信息．

2) 在特征描述階段,根據(jù)特征點之間的相對橢圓形距離選擇特征點子集,結合譜理論構造描述特征點屬性的橢圓形度量譜特征．

3) 在特征點匹配階段,利用橢圓形度量計算譜特征之間的相似性,從而得到匹配關系．

4) 模擬數(shù)據(jù)和圖像數(shù)據(jù)實驗結果表明,基于橢圓形度量譜特征的圖像匹配算法提高了匹配精度,并對噪聲具有較高的魯棒性,適用于圖像視角變換較大和形變較大的匹配問題．

參考文獻(References)

[1] Carcassoni M, Hancock E R. Spectral correspondence for point pattern matching[J].PatternRecognition, 2003,36(1): 193-204. DOI:10.1016/s0031-3203(02)00054-7.

[2] Feng W, Liu Z Q, Wan L, et al. A spectral-multiplicity-tolerant approach to robust graph matching[J].PatternRecognition, 2013,46(10): 2819-2829. DOI:10.1016/j.patcog.2013.03.003.

[3] Yang X, Qiao H, Liu Z Y. Feature correspondence based on directed structural model matching[J].ImageandVisionComputing, 2015,33: 57-67. DOI:10.1016/j.imavis.2014.11.001.

[4] Peng X, Yu Z, Yi Z, et al. Constructing the L2-graph for robust subspace learning and subspace clustering[J].IEEETransCybern, 2017,47(4): 1053-1066. DOI:10.1109/TCYB.2016.2536752.

[5] Leordeanu M, Hebert M. A spectral technique for correspondence problems using pairwise constraints [C]//TenthIEEEInternationalConferenceonComputerVision. Beijing, China, 2005: 1482-1489. DOI:10.1109/iccv.2005.20.

[6] Yuan Y, Pang Y, Wang K, et al. Efficient image matching using weighted voting[J].PatternRecognitionLetters, 2012,33(4): 471-475. DOI:10.1016/j.patrec.2011.02.008.

[7] Tang J, Shao L, Zhen X. Robust point pattern matching based on spectral context[J].PatternRecognition, 2014,47(3): 1469-1484. DOI:10.1016/j.patcog.2013.09.017.

[8] 朱明,梁棟,范益政,等.基于譜特征的圖像匹配算法 [J].華南理工大學學報(自然科學版),2015,43(9): 60-66. DOI:10.3969/j.issn.1000-565X.2015.09.010.

Zhu Ming, Liang Dong, Fan Yizheng, et al. Image matching algorithm based on spectral feature [J].JournalofSouthChinaUniversityofTechnology(NaturalScienceEdition), 2015,43(9): 60-66. DOI:10.3969/j.issn.1000-565X.2015.09.010. (in Chinese)

[9] Yan P, Liang D, Tang J, et al. Local feature descriptor invariant to monotonic illumination changes[J].JournalofElectronicImaging, 2016,25(1): 013023. DOI:10.1117/1.jei.25.1.013023.

[10] Bo D, Zhang G L, Cui X L. An algorithm of image matching based on Mahalanobis distance and weighted KNN graph [C]//2015InternationalConferenceonInformationScienceandControlEngineering. Shanghai, China, 2015: 116-121.

[11] Famouri M, Azimifar Z. A statistical approach to rank the matched image points [C]//2016 24thIranianConferenceonElectricalEngineering. Shiraz, Iran, 2016: 1214-1218. DOI:10.1109/iraniancee.2016.7585706.

[12] Klein F. Ueber die sogenannte Nicht-Euklidische geometrie[J].MathematischeAnnalen, 1970,6(2): 112-145. DOI:10.1007/BF01443189.

[13] Zhou F, Torre F D L. Deformable Graph Matching [C]//2013IEEEConferenceonComputerVisionandPatternRecognition. Portland, USA, 2013: 2922-2929. DOI:10.1109/cvpr.2013.376.

[14] Cho M, Sun J, Duchenne O, et al. Finding matches in a Haystack: A max-pooling strategy for graph matching in the presence of outliers [C]//ComputerVisionandPatternRecognition. Columbus, OH, USA, 2014: 2091-2098.DOI:10.1109/cvpr.2014.268.