樹的譜及其在圖像匹配中的應用.pdf

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

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

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

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