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

張曉聞，任勇峰

中北大學 儀器與電子學院，太原030051

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

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

1 相關理論

1.1 稀疏表示

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

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

1.2 拓撲相似性約束條件

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

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

圖1 角度順序約束

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

圖2 位置順序約束

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

圖3 鄰域約束

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

圖4 三角形位置約束

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

圖5 三角形剖分約束

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

本文所提算法先進行圖像特征檢測，得到待匹配圖像的最大輪廓相似度區域；在此基礎上利用稀疏編碼對特征稀疏表示，建立稀疏模型，將復雜特征變得單一化，但又不影響特征的分類方式，將相同類別或者相同屬性的特征歸為同一特征集，結合稀疏表示和鄰域互信息的類屬屬性學習，得到變換矩陣，用以表示圖像。最后，利用結構化的拓撲相似性，對輪廓內外相關聯的點進行優化。

2.1 特征檢測

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

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

2.2 圖像表示

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

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

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

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

這個問題可以通過A的偽逆進行解決，但是x2并不能很好地用來識別特征y。通常x2是稠密的，有著與很多來自不同集合的特征對應的非零元素。為了解決這個問題，轉而利用以下思路：一個有效的特征y通常可以被只來自同一集合的特征充分地表示。只要目標類的數量k足夠大，這個表示往往是稀疏的。舉個例子，當k=20 的時候，解向量x0中只有5%的元素是非零的。x0越稀疏，特征樣本y屬于哪一個集合就越容易被準確地判定。

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

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

這個問題可以通過線性編程方法在多項式時間內求解。當解非常稀疏時，甚至會有更高效的解決辦法。

2.3 算法設計及流程

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

圖6 算法流程圖

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

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

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

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

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

3 實驗結果及分析

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

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

圖7 旋轉與縮放

圖8 光照變化

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

圖9 視角變化

圖10 模糊變化

圖11 JPEG壓縮

表1 對比數據

4 結論

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