圖匹配問題的研究和算法設計.pdf

1、本文探討了多媒體和計算機視覺領域的一項關鍵技術—圖匹配問題的形式化與算法設計。圖匹配的目標是通過不同事物之間在結構上的相似性，自動地建立兩個或者多個圖結構之間的節(jié)點對應關系。該問題在圖像處理、多媒體、計算機視覺、模式識別和圖形學，乃至生物信息學等領域得到了廣泛的研究和應用。本論文工作主要圍繞圖匹配問題的兩個方面：二圖匹配和多圖匹配及配準展開，研究成果集中在如下幾個方面：
　　首先，作者提出并考察了一種基于線性迭代梯度指派的二圖匹配

2、基準算法，對其收斂性質(zhì)從解空間可行域和相似度特征階數(shù)兩方面進行分析論證。對于任意給定的相似度矩陣，作者論證了離散域線性迭代梯度指派算法對于二階問題將陷入二重循環(huán)解，這一結論被推廣到解空間為連續(xù)域的對應算法?；谶@一理論分析，本文提出了一個自適應的目標函數(shù)松弛機制，保證新算法收斂到穩(wěn)態(tài)固定解。并進一步論證在問題階數(shù)為N的一般情況下，高階的線性迭代梯度指派算法具有N重循環(huán)解的性質(zhì)，就此作者提出了新算法保證收斂到穩(wěn)態(tài)解。理論和實驗結果表明，離

3、散域算法相對高效，而二階連續(xù)域算法顯示了更好的匹配精度。
　　其次，作者提出了在匹配變量交替更新框架下的多圖匹配形式化模型和迭代優(yōu)化算法，將每步迭代中的子問題轉化成一個數(shù)學上等價的二圖匹配問題。同時，該模型可以包容相似度矩陣分解形式和非分解形式，進而可以重用現(xiàn)有的基于兩種形式的任意二圖匹配算法。更進一步的，論文提出了一個基于兩兩匹配相容性的評估函數(shù)，以此來設定用于推動交替更新的基準圖與變量交替更新次序。實驗證明，這一機制提升了初始

4、解的質(zhì)量，并往往能夠加快算法迭代的收斂速度。另外，作者將該框架用于多個點集間參數(shù)化變換下的配準問題上，并提出了特定的迭代優(yōu)化配準算法，兼顧配準精度和速度。
　　再次，作者提出了另一個基于自舉提升框架的迭代算法。交替更新多圖匹配算法本質(zhì)上是一種期望最大化迭代過程，無法完全避免初始解精度和迭代過程中誤差累積對最終結果的負面影響。而自舉模型基于兩個重要的觀察：第一，獨立得到的兩兩匹配解可以通過傳遞點對應關系的方式得到相似度目標函數(shù)和精度

5、的提升；第二，在大噪聲的情況下，原有的目標函數(shù)無法與匹配精度完全一致，存在精度高的解反而對應的相似度目標函數(shù)得分更低的情況。這時，匹配相容性則與整體匹配精度的相關性更強。對于第一個觀察，論文設計了基于一階近似傳導的相似度目標函數(shù)自舉算法；對于第二個觀察，論文定義了基于一階傳導的匹配相容性正則項，進一步設計了漸進性注入匹配相容性項的自舉提升機制，并證明了部分算法的收斂性質(zhì)。作者還針對存在大量外點的情況，設計了從多個圖中進行公共內(nèi)點抽取的機

6、制。理論和實驗結果表明，基于正則化的自舉算法具有較強的魯棒性，特別是在匹配圖數(shù)目較多的情況下，顯示了出眾的匹配精度。
　　最后，作者設計了一個在圖屬性信息顯式表達下基于矩陣恢復凸優(yōu)化技術的多圖匹配算法。一方面，該方法挖掘了圖匹配與矩陣恢復這兩個問題直接的關聯(lián)，將多圖匹配問題轉換成一個矩陣的低秩和稀疏分解問題。這一轉化建立了近年來各種層出不窮的凸優(yōu)化技術與本屬于組合優(yōu)化問題的圖匹配之間的橋梁。另一方面，該方法假設屬性圖的點和邊權值信

7、息顯式給出，而非像本文提出的其他多圖匹配算法僅需給出兩圖間的相似度函數(shù)值。為了使得該方法具有更大的實際價值，作者對單個屬性圖信息的顯式構建進行了初步研究，提出了一個基于行為主體屬性個性化互激勵點過程模型，從事件數(shù)據(jù)中挖掘事件各個維度之間的關聯(lián)，定量描述潛在的屬性圖結構。理論和實驗結果表明，基于矩陣恢復的多圖匹配算法復雜度與待匹配的圖數(shù)目呈線性關系，且具有較好的整體匹配精度。
　　綜上所述，本文對圖匹配這一基本問題進行了廣泛深入的研