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

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

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

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

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

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

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

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