圖匹配問題的研究和算法設(shè)計.pdf

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

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

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

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

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

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

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