結(jié)合稀疏表示與拓撲相似性的圖像匹配算法

張曉聞，任勇峰

中北大學(xué) 儀器與電子學(xué)院，太原030051

隨著計算機及科學(xué)技術(shù)的飛速發(fā)展，與圖像處理相關(guān)的各種應(yīng)用也越來越受研究學(xué)者的追捧。圖像處理可廣泛用于航空航天[1]、國防建設(shè)[2]、醫(yī)療診斷[3]、機器視覺[4]等各個方面。圖像匹配方法主要是用于圖像預(yù)處理后，圖像拼接、圖像融合、圖像理解等環(huán)節(jié)。研究學(xué)者們已經(jīng)提出了各種不同的匹配方法，大體可以分為以下幾類：基于解釋的匹配方法、基于特定理論的匹配方法、基于灰度像素信息的匹配方法、基于亞像素的匹配方法和基于特征的匹配方法?；诮忉尩膱D像匹配[5]核心是基于圖像的關(guān)系結(jié)構(gòu)進行匹配，該方法的優(yōu)點是計算量小，但同時使得結(jié)構(gòu)之間的關(guān)系表述不全面，并且缺乏一套完善的衡量體系。因此，該種方法并未取得突破性進展；基于特定理論的圖像匹配，顧名思義是與目前現(xiàn)有的特定理論進行結(jié)合而進行的匹配，常見的特定理論有神經(jīng)網(wǎng)絡(luò)[6]和小波變換[7]等。這些方法的決定因素是根據(jù)特定理論進行的，會加入學(xué)習(xí)或迭代等過程，在進行圖像匹配時會花費大量的時間。因此，實用性和實時性相對較差；基于灰度像素信息的匹配[8]核心技術(shù)是圖像相關(guān)技術(shù)，目前提出了各種快速匹配的方法，但是相比較其他方法，該方法的匹配精度不高，而且在實際工作中會出現(xiàn)實時性差等問題，該方法靈活性較低，因此很少被應(yīng)用到實際問題?；趤喯袼氐钠ヅ浞椒╗9]的匹配像元是基于圖像的亞像素進行，經(jīng)過圖像信息比對，粗略信息和精細信息匹配等過程后，計算像元偏移量。在實際應(yīng)用中，使用單一的方法會花費大量的時間，或者所能達到的精度是有限的，但將這兩種方法相結(jié)合，又會造成算法的復(fù)雜度增高；基于特征的匹配方法[10]以特征為屬性，利用啟發(fā)式等方法計算相似性度量。該方法可以克服利用灰度信息進行匹配的缺點，提高匹配精確度，由于特征點比像素點要少，因而可以減少匹配時間，所以該方法在實際應(yīng)用中適用廣泛。

這幾種方法在匹配精度上都取得了一定的進展，但是匹配效率與時間復(fù)雜度相矛盾的問題解決方法卻一直不盡如人意。因此，本文針對該問題，提出了一種基于稀疏矩陣和拓撲相似性的圖像匹配方法。該方法結(jié)合稀疏表示和鄰域互信息的類屬屬性和拓撲相似性的結(jié)構(gòu)特征，對圖像進行匹配。匹配過程中，本文先通過對圖像進行特征檢測，計算輪廓相似度，找到待匹配圖像中相似的最大輪廓區(qū)域，對輪廓區(qū)域內(nèi)的特征點進行稀疏模型建立，通過計算得到變換矩陣，用以表示圖像。最后利用拓撲約束將檢測輪廓內(nèi)外相關(guān)聯(lián)的點進行優(yōu)化，以達到高度匹配的效果。

1 相關(guān)理論

1.1 稀疏表示

稀疏表示是近20年來信號處理領(lǐng)域研究的熱點話題，稀疏表示是以超完備字典為基礎(chǔ)，用盡可能少的原子來表示信號，得到更為簡單的信號表達方式，使人們能清楚、全面、容易地獲取該信號所蘊含的各種信息，方便進一步對信號加工處理[11]。用數(shù)學(xué)思維描述，即如何通過最小數(shù)量的系數(shù)盡可能更多地描述信號的能量。信號的類型不同，致使其在不同條件、不同變換下的系數(shù)及分布都會有所不同[12]。目前，信號稀疏表示用數(shù)學(xué)形式表示如下：

其中，y為觀測數(shù)據(jù)，D為字典，x為待估稀疏向量，λ為正則參數(shù)，k(1 ≤k＜2)為稀疏度量。其中，λ與k未知，需要預(yù)先確定（雖然通常取k=1，但k＜1 時模型更加靈活）。

1.2 拓撲相似性約束條件

在文獻[13]中將圖像檢測的特征點劃分為平面，根據(jù)攝像機模型知識及三角形幾何關(guān)系，各個平面的特征點在兩幅圖像之間的投影具有拓撲穩(wěn)定性，滿足如下5條拓撲相似性約束條件：

（1）角度約束，l平面上任一點與鄰域內(nèi)點的連線所成夾角順序相同。如圖1所示，圖1（a）為參考圖像任一點與鄰域內(nèi)點相連所成夾角的順序，圖1（b）和圖1（c）為待匹配圖像中的正確與錯誤匹配順序。

圖1 角度順序約束

（2）直線位置約束，同一條直線上，參考圖像和匹配圖像特征點順序一致。如圖2 所示，圖2（b）中與的順序為正確匹配順序。

圖2 位置順序約束

（3）鄰域約束，l平面上參考圖像中點是點的鄰域，則待匹配圖像中匹配點仍然為的鄰域，如圖3（b）所示。

圖3 鄰域約束

（4）三角形位置約束。三角形與點的位置關(guān)系不變，參考圖像中位于三角形之外，則待匹配圖像中位于三角形之外，如圖4（b）所示（三種位置關(guān)系：三角形外、三角形內(nèi)、三角形上）。

圖4 三角形位置約束

（5）三角形剖分約束。參考圖像上特征點的三角形剖分與匹配圖像的三角形剖分一致，不存在交叉邊，如圖5所示。

圖5 三角形剖分約束

2 基于稀疏編碼和拓撲相似性的圖像匹配

本文所提算法先進行圖像特征檢測，得到待匹配圖像的最大輪廓相似度區(qū)域；在此基礎(chǔ)上利用稀疏編碼對特征稀疏表示，建立稀疏模型，將復(fù)雜特征變得單一化，但又不影響特征的分類方式，將相同類別或者相同屬性的特征歸為同一特征集，結(jié)合稀疏表示和鄰域互信息的類屬屬性學(xué)習(xí)，得到變換矩陣，用以表示圖像。最后，利用結(jié)構(gòu)化的拓撲相似性，對輪廓內(nèi)外相關(guān)聯(lián)的點進行優(yōu)化。

2.1 特征檢測

信息和特征是圖像匹配中最基本的處理和分析對象，是完成圖像后處理任務(wù)的先決條件。圖像特征依賴于圖像內(nèi)容，特征提取旨在獲取圖像中視覺特征信息，減少視覺特征數(shù)據(jù)量。通過特征進行圖像匹配反映的都是一些本質(zhì)特征和物理結(jié)構(gòu)信息。圖像本身來講就是一個矩陣，可以依靠矩陣分解獲取一些更加魯棒的特征來對圖像進行相似度的計算。相似度是實體間視覺相似度的度量，既有可能是目標之間，又有可能是場景之間。任何目標和場景的信息均存儲在反應(yīng)視覺特征的結(jié)構(gòu)單元中，可采用特征共享編碼矩陣表示實體間的相似關(guān)系[14]。

本文利用文獻[15]中的方法進行輪廓相似度的計算，找到圖像中相似性度量最大的輪廓區(qū)域，在輪廓區(qū)域內(nèi)進行其他操作。圖像特征提取是圖像理解中從圖像獲得數(shù)據(jù)信息并進行相關(guān)分析的前提條件和關(guān)鍵環(huán)節(jié)，主要分為基本特征提取和常用特征提取。在輪廓內(nèi)利用surf算法進行特征點檢測，檢測步驟為：（1）用Hessian矩陣求出每個像素點的值。（2）求出3×3×3 的立體鄰域的26個像素點，將兩者進行比較，若是其鄰域中的最大值，則保留，否則剔除。（3）利用插值法尋找其他的特征點及其所在的尺度值。（4）計算surf算子的主方向，以特征點設(shè)為圓心，計算Haar 小波響應(yīng)，通過一系列運算，得到最大矢量，即為特征點的主方向。

2.2 圖像表示

圖像表示是指通過某種方式對圖像數(shù)據(jù)進行變換獲得，使其本質(zhì)結(jié)構(gòu)更顯著或更容易理解。常用的基于基函數(shù)的變換有傅里葉變換、小波變換、主分量與獨立分量分析及稀疏編碼等[16]。用來自k個不同集合的帶有標簽的特征樣本來正確的判定新的特征屬于哪一集合。第i個感興趣特征的ni個特征表示為矩陣Ai=[Vi,1,Vi,2,…,Vi,ni] ∈Rm×ni的列，w×h的灰階圖像定義為向量V∈Rm(m=wh),Ai的所有列向量表示第i個感興趣區(qū)域的所有特征。假設(shè)來自于單個集合的特征確實處于同一子空間上。Ai=[vi,1,vi,2,…,vi,ni] ∈Rm×ni,任何來自第i集合的新特征都將大致能由處于同一個感興趣區(qū)域的特征線性表示如下：

其中ai,j是標量，ai,j∈R,j=1,2,…,ni。

由于新檢測特征屬于哪個集合在初始條件下是未知的，因此定義一個新的矩陣A表示來自k個目標集合所有的n個特征：然后y關(guān)于所有特征樣本的線性表示可以寫成：

其中，x0=[0,…,0,αi,1,αi,2,…,αi,ni,0,…,0]T∈Rn，向量x0中除了和第i集合相關(guān)的元素是非零元素之外，其他的元素都是0。由于y是由x0線性表出，因此需要通過對線性方程組y=Ax進行求解，從而得到稀疏表示x0。顯然，當m ＞n時，方程組y=Ax是超定的，如果該方程組y=Ax存在精確解，那么它一定是唯一的。然而，方程組y=Ax往往是欠定的，通?？梢赃x擇最小l2范數(shù)來解決：

這個問題可以通過A的偽逆進行解決，但是x2并不能很好地用來識別特征y。通常x2是稠密的，有著與很多來自不同集合的特征對應(yīng)的非零元素。為了解決這個問題，轉(zhuǎn)而利用以下思路：一個有效的特征y通?？梢员恢粊碜酝患系奶卣鞒浞值乇硎?。只要目標類的數(shù)量k足夠大，這個表示往往是稀疏的。舉個例子，當k=20 的時候，解向量x0中只有5%的元素是非零的。x0越稀疏，特征樣本y屬于哪一個集合就越容易被準確地判定。

以上結(jié)論促使通過以下優(yōu)化問題來尋找y=Ax的最稀疏的解

其中‖ · ‖0表示l0范數(shù)，就是向量中非零元素的個數(shù)。事實上，如果A中的列處于一般的位置，y=Ax的一些解x中，只要x中的非零元素小于m/2,x就是唯一的稀疏解：即x0=x。然而，求解一個欠定線性方程組從而尋找最稀疏的解是一個難題，即使求大約解也很難：也就是說，在一般情況下，沒有比遍歷元素的所有子集更高效的方法來尋找x最稀疏的解。稀疏表示和壓縮感知新興理論最近的發(fā)展表明，如果x0被認為是足夠稀疏的，l0最小化問題的求解可以等同于以下的l1最小化問題的求解：

這個問題可以通過線性編程方法在多項式時間內(nèi)求解。當解非常稀疏時，甚至?xí)懈咝У慕鉀Q辦法。

2.3 算法設(shè)計及流程

綜合上述算法分析，算法的流程圖如圖6。

圖6 算法流程圖

根據(jù)算法的流程圖，給出算法的步驟如下：

步驟1對兩幅圖像進行特征檢測。

步驟2計算兩幅圖像的輪廓相似度，找到最佳輪廓。

步驟3通過檢測的特征進行稀疏模型建立得到稀疏變換矩陣。

步驟4滿足拓撲約束進行匹配。

3 實驗結(jié)果及分析

為了驗證算法的有效性，本文分別對圖像數(shù)據(jù)進行了實驗，將本文算法與其他匹配算法進行性能比較。實驗中所用圖像來自于INRIA數(shù)據(jù)集（http：//lear.inrialpes.fr/people/mikolajczyk/Database/）。本文通過對四種算法、五種變化進行了多次匹配實驗，每種變換根據(jù)圖像變化程度的不同，分別選用5 組圖像，每組圖像進行30 次實驗，通過計算圖像的查全率-查準率、匹配準確率和匹配時間，各類數(shù)據(jù)結(jié)果取平均，得到對比數(shù)據(jù)。

圖7～11為五種變化下使用的匹配圖像及四種算法的查全率-查準率對比結(jié)果，由圖可知，相較于旋轉(zhuǎn)縮放及JPEG壓縮兩種情況，其他三種變化下的查全率-查準率相對較低。

圖7 旋轉(zhuǎn)與縮放

圖8 光照變化

四種算法在五種變換下的匹配成功率與匹配時間的對比數(shù)據(jù)如表1 所示。從表1 中的數(shù)據(jù)可得結(jié)論，查全率和查準率在相同的誤配率下，只有模糊變換中時間慢于文獻[13]的方法，其他變換中，無論準確率還是時間方面，本文的效果數(shù)據(jù)都要優(yōu)于其他三種算法，因此，本文算法能較好地平衡時間與匹配效率的雙重指標。

圖9 視角變化

圖10 模糊變化

圖11 JPEG壓縮

表1 對比數(shù)據(jù)

4 結(jié)論

基于稀疏表示與拓撲相似性結(jié)合的圖像匹配算法先通過對圖像進行特征檢測，計算輪廓相似度，找到待匹配圖像中相似的最大輪廓區(qū)域，用稀疏編碼對輪廓內(nèi)特征進行稀疏表示，建立稀疏模型，將復(fù)雜特征變得單一化，但又不影響特征的分類方式，將相同類別或者相同屬性的特征歸為同一特征集，結(jié)合稀疏表示和鄰域互信息的類屬屬性學(xué)習(xí)。通過計算得到變換矩陣，用以表示圖像。利用結(jié)構(gòu)化的拓撲相似性，對輪廓內(nèi)外相關(guān)聯(lián)的點進行優(yōu)化。通過實驗分析，發(fā)現(xiàn)本文提出的方法無論是在客觀參數(shù)評價上還是匹配度計算方面，與其他圖像匹配算法相比較，都有明顯的優(yōu)勢，并且可以較好地平衡匹配效率與計算復(fù)雜度的問題。