樹的譜及其在圖像匹配中的應(yīng)用.pdf

1、譜圖理論主要研究圖的譜性質(zhì)和圖的結(jié)構(gòu)性質(zhì)之間的關(guān)系，期望通過譜性質(zhì)來刻畫結(jié)構(gòu)性質(zhì)．圖的鄰接譜與Laplace譜一直是譜圖理論中的研究熱點(diǎn)．利用譜(尤其是譜半徑)來刻畫一些特殊的圖類是國(guó)內(nèi)外學(xué)者的關(guān)注的焦點(diǎn)．譜圖理論在圖像處理中發(fā)揮有效的作用．利用圖的特征值與特征向量的性質(zhì)，可以給出兩幅圖像特征點(diǎn)之間的對(duì)應(yīng)關(guān)系．
　　本文主要研究?jī)蓚€(gè)方面的問題：(1)在所有給定最大度和階數(shù)的樹中，刻畫具有最大譜半徑的樹；(2)利用圖的最小生成樹及其

2、Laplace譜性質(zhì)，給出圖像特征點(diǎn)的匹配算法．
　　近年來，研究者對(duì)如下問題非常有興趣，即在給定某個(gè)圖參數(shù)的情形下，刻畫極端的譜性質(zhì)，如譜半徑，代數(shù)連通度等．這些工作包括：在給定直徑的樹中，Kirkland與Neumann給出了代數(shù)連通度的一個(gè)下界，F(xiàn)allat，Kirkland刻畫出分別具有最大，最小代數(shù)連通度的樹，Guo與Shao按照鄰接譜半徑對(duì)樹進(jìn)行排序；在給定最大度的樹中，Lin與Guo刻畫了具有最小鄰接譜半徑的樹，并把

3、樹的排序進(jìn)一步擴(kuò)展，zhang，Li，Guo則根據(jù)Laplace譜半徑對(duì)樹進(jìn)行排序．
　　在給定最大度的樹中，我們應(yīng)用頂點(diǎn)賦值的思想，給出了尋找具有最大鄰接譜半徑Laplacian譜半徑的一種簡(jiǎn)單方法．相對(duì)于已有工作對(duì)圖的特征多項(xiàng)式的大量計(jì)算，我們的方法避免了計(jì)算，運(yùn)用純粹組合安排的想法．此外，相對(duì)于已有結(jié)論對(duì)最大度的限制，我們的結(jié)果對(duì)一般的最大度成立．
　　Scott和Longuet-Higgins首次將圖譜方法應(yīng)用于圖像

4、匹配分析．此方法后來被Shapiro，Brandy，Carcassoni，Myers等推廣．這些工作的主要想法是：(1)構(gòu)造賦權(quán)完全圖，(2)獲取賦權(quán)完全圖的譜信息以刻畫特征信息．
　　我們認(rèn)為：賦權(quán)完全圖強(qiáng)調(diào)任意兩個(gè)節(jié)點(diǎn)之間都有權(quán)，信息豐富，但太多的信息往往會(huì)增加問題處理的復(fù)雜性。因此，從節(jié)約的角度，我們從賦權(quán)完全圖中找出其最小生成樹，對(duì)最小生成樹獲取其Laplace譜信息，進(jìn)而實(shí)現(xiàn)特征匹配．模擬實(shí)驗(yàn)表明該算法對(duì)平移，旋轉(zhuǎn)，縮放