基于Laplace譜的點(diǎn)模式匹配方法研究

鮑新雪，王曉紅

（1.貴州大學(xué) 礦業(yè)學(xué)院，貴州 貴陽 550025；2.貴州大學(xué) 林學(xué)院，貴州 貴陽 550025）

圖像匹配就是指通過一定的匹配算法在兩幅或多幅圖像之間識別同名點(diǎn)。遙感圖像匹配是指將取自同一目標(biāo)區(qū)域的兩幅或多幅圖像在空間位置上最佳匹配起來［1］。就當(dāng)前的圖像匹配技術(shù)水平，基于特征的影像匹配較基于灰度的影像匹配體現(xiàn)出了較高的可靠性和魯棒性等諸多優(yōu)勢，而且點(diǎn)特征又是諸多特征中較為穩(wěn)定且易于識別的特征，因此，點(diǎn)模式匹配技術(shù)在一定程度上可以很好地實現(xiàn)圖像的匹配，對它的研究具有極大的理論意義和實踐價值。點(diǎn)模式匹配技術(shù)在諸多領(lǐng)域都有廣泛的應(yīng)用，總結(jié)起來包括以下三點(diǎn)［2］：

1）實現(xiàn)從不同的角度拍攝同一地物的多視點(diǎn)影像的三維重建。

2）對來自不同傳感器、不同時間獲取的同一場景的影像數(shù)據(jù)進(jìn)行融合和建模，或者在醫(yī)學(xué)成圖中（MRI／CT影像）在不同條件、不同應(yīng)用程序控制下對同一部位獲取的影像數(shù)據(jù)進(jìn)行融合和建模。

3）用基于模型的方法跟蹤和識別在圖像中涉及的模塊，以及在民事、農(nóng)業(yè)、地質(zhì)、軍隊等應(yīng)用的遙感數(shù)據(jù)。

Scott和Longuet－Higgins最早提出將圖譜知識應(yīng)用到點(diǎn)模式匹配中，但僅適用于較為簡單的圖像在理想條件下的匹配［3］。直到特征點(diǎn)鄰域灰度矩陣相關(guān)系數(shù)這一概念的引入，使得真實圖像的匹配效果得到極大地改進(jìn)。后來，Shapiro和Brady通過構(gòu)造特征點(diǎn)集，引入鄰近矩陣等相關(guān)概念，在極大程度上克服了旋轉(zhuǎn)情況下圖像匹配效果差的缺點(diǎn)［4－5］。隨后，譜束的引用較好地克服了點(diǎn)集的不同結(jié)構(gòu)帶來的問題；容錯核函數(shù)代替高斯函數(shù)又改進(jìn)了對點(diǎn)抖動的健壯性［4，6］。Wang又提出用Laplace矩陣來代替鄰近矩陣完成圖像匹配。最近Carcassoni又把EM算法和譜圖理論結(jié)合起來，這一結(jié)合使得運(yùn)用譜方法進(jìn)行匹配的準(zhǔn)確度有了很大地提高。

1 基于Laplace譜的點(diǎn)模式匹配

基于特征點(diǎn)的匹配問題一直以來都是遙感應(yīng)用領(lǐng)域內(nèi)比較關(guān)注的問題，如在實現(xiàn)地物的三維重建時，常采用點(diǎn)模式匹配的方法實現(xiàn)圖像匹配，重建地物。而基于譜圖理論的點(diǎn)模式匹配方法可以簡單地描述為：從兩幅選定的待匹配圖像中提取出各自的特征點(diǎn)，分別形成特征點(diǎn)集，然后在此基礎(chǔ)上建立兩個特征點(diǎn)集中相應(yīng)點(diǎn)之間一一對應(yīng)的關(guān)系［7］。具體進(jìn)行該方法的匹配操作時，首先要把圖用集合的形式表示，集合中的點(diǎn)元素與選取的特征點(diǎn)一一對應(yīng)，且兩個點(diǎn)元素之間的關(guān)系可用來表示相應(yīng)的圖中的邊。根據(jù)集合表示的圖形，就可以通過對矩陣進(jìn)行特征分解的方法得到特征點(diǎn)之間的幾何關(guān)系。這樣就可以把原來圖像中的重要信息都反映到一個空間里，便于對兩幅圖像的特征點(diǎn)間的對應(yīng)關(guān)系進(jìn)行比較。下面介紹基于Laplace譜的匹配算法。

1.1 基于Laplace譜的點(diǎn)模式匹配算法描述

假設(shè)兩幅待匹配圖像I，J，且從圖像I中提取出n 個特征點(diǎn)（k1，k2，…，kn），那么，以這n 個特征點(diǎn)作為節(jié)點(diǎn)構(gòu)造出圖像I的完全圖，根據(jù)得到的完全圖即可獲得圖像I的Laplace矩陣［8－10］

式中：σ是一個常數(shù)。同理，對圖像J也可以得到相應(yīng)的Laplace矩陣L（J）。

對得到的矩陣L（I）和L（J）分別進(jìn)行奇異值分解，有

式中：ΔI、ΔJ分別是由矩陣L（I），L（J）的奇異值組成的對角陣，且對角線上的元素自左上角至右下角依次遞減排列（元素值均大于或等于0）；U和V均為n階正交矩陣。

值得注意的問題是，為了使矩陣U和V的列向量間距離盡可能小，不能對矩陣L（I）和L（J）進(jìn)行同一約束條件的奇異值分解。因此，往往采用在第一個處理好的基礎(chǔ)上再處理第二個，即先把矩陣L（I）分解完成得矩陣U，再以矩陣U的列向量為基礎(chǔ)，完成矩陣L（J）的分解，得矩陣V。然后，對矩陣V的列向量進(jìn)行相應(yīng)的符號校正，在校正過程中會形成一個最佳符號矩陣S，把校正后的矩陣記做V＊，即V＊＝VS。分別記U 和V＊的行向量為u（i）和v＊（i），且它們分別對應(yīng)圖像I和J的第i個點(diǎn)和第j個點(diǎn)，則

可知，u（i），v＊（i）間 距 與 u（i）（v＊（j））T負(fù) 相 關(guān)，也 即u（i）（v＊（j））T越大，則圖像I中的第i個特征點(diǎn)和圖像J中的第j個特征點(diǎn)有最大可能性的匹配關(guān)系。有匹配關(guān)系矩陣P如下

假設(shè)矩陣中的任一元素P是其所在行和列中的最大值，就可認(rèn)為圖像I中的第i個特征點(diǎn)和圖像J中的第j個特征相匹配，但這種方法僅適用于提取的特征點(diǎn)數(shù)相同的兩幅圖像。如果從兩幅圖像中提取出的特征點(diǎn)數(shù)目不同，分別為m和n，且m＜n，對于提取出n個特征點(diǎn)的圖像只處理前（m－1）個特征點(diǎn)和最后一個特征點(diǎn)的特征向量；對于提取出m個特征點(diǎn)的圖像則處理全部特征點(diǎn)的特征向量。

1.2 基于Laplace譜的點(diǎn)模式匹配算法流程

第一步：分別從兩幅待匹配的圖像中提取出各自的特征點(diǎn)，并把它們作為節(jié)點(diǎn)組成各自的結(jié)構(gòu)圖，然后根據(jù)結(jié)構(gòu)圖分別生成各自相應(yīng)的Laplace矩陣；

第二步：對得到的Laplace矩陣分別進(jìn)行奇異值分解，而后把其中任一分解結(jié)果作為基準(zhǔn)，對另一分解結(jié)果進(jìn)行相應(yīng)的符號校正；

第三步：根據(jù)前面的結(jié)果構(gòu)造出能夠反映圖像匹配程度的矩陣P，通過比較矩陣P中的任一元素在其所屬行和列的大小，可得兩幅圖像中相應(yīng)特征點(diǎn)的匹配結(jié)果，據(jù)此完成匹配。

2 實驗及結(jié)果

2.1 實驗設(shè)計

為了驗證基于Laplace譜的點(diǎn)模式匹配算法的準(zhǔn)確度及穩(wěn)定性，明確如下實驗思路：

首先選擇特征鮮明的仿真圖像（紋理稀疏，無明顯的灰度梯度信息）作為實驗數(shù)據(jù)，在Matlab環(huán)境下分別實現(xiàn)在理想和存在噪聲情況下的圖像匹配，并分析匹配結(jié)果，通過匹配結(jié)果驗證該算法的準(zhǔn)確度及穩(wěn)定性［11］。其中，特征點(diǎn)是通過 Harris角點(diǎn)檢測法獲取的，其檢測公式為

然后利用該匹配技術(shù)完成真實影像的匹配，分析匹配結(jié)果驗證該匹配技術(shù)的可行性。最后通過和基于灰度的圖像匹配技術(shù)的對比分析，驗證該匹配技術(shù)的優(yōu)勢。匹配技術(shù)實現(xiàn)流程如圖1所示。

圖1 匹配技術(shù)流程

2.2 技術(shù)實現(xiàn)及結(jié)果分析

2.2.1 仿真數(shù)據(jù)技術(shù)實現(xiàn)及結(jié)果分析

在理想情況下的匹配結(jié)果如圖2所示，匹配結(jié)果分析如表1所示。

圖2 理想情況下的匹配結(jié)果

表1 理想情況下匹配結(jié)果分析

存在噪聲情況下的匹配結(jié)果如圖3所示，匹配結(jié)果分析如表2所示。

圖3 存在噪聲情況下的匹配結(jié)果

表2 存在噪聲情況下匹配結(jié)果分析

旋轉(zhuǎn)變換矩陣：

根據(jù)三組仿真數(shù)據(jù)匹配結(jié)果可知該算法的匹配成功率都非常不錯，對于平移匹配的成功率則為100%。雖然當(dāng)圖像發(fā)生仿射變換以及存在噪聲時的匹配效果不是非常理想，但是在一定程度上也是很好地完成了圖像的匹配，穩(wěn)定性高。

2.2.2 利用該技術(shù)實現(xiàn)真實圖像匹配及結(jié)果分析

真實圖像匹配結(jié)果如圖4所示，匹配結(jié)果分析見表3；遙感影像匹配結(jié)果見圖5，匹配結(jié)果分析見表4。

圖4 真實圖像匹配結(jié)果

表3 真實影像匹配結(jié)果分析

圖5 遙感影像匹配結(jié)果

表4 遙感影像匹配結(jié)果分析

以上實驗表明，基于Laplace譜的點(diǎn)模式匹配算法具有不錯的匹配效果，但也存在一定的弊端，雖然把復(fù)雜的圖像簡化成了簡單的求解特征值和特征向量的問題很方便，但是，該匹配算法對提取特征點(diǎn)的準(zhǔn)確度要求較高，因此，在進(jìn)行特征點(diǎn)的提取時，一定要先對待匹配影像的形變以及噪聲等因素引起的特征點(diǎn)位的變化做相關(guān)的預(yù)測，以便選取合適的特征點(diǎn)提取算法，確保特征點(diǎn)提取的準(zhǔn)確性。在進(jìn)行基于譜分析方法的匹配時，以待匹配圖像的結(jié)構(gòu)圖的矩陣為基礎(chǔ)來完成兩幅圖像匹配，而結(jié)構(gòu)圖是以提取的特征點(diǎn)為依據(jù)的，因此，對特征點(diǎn)的提取要十分注意。

2.2.3 與基于灰度的圖像匹配技術(shù)實現(xiàn)及結(jié)果分析

1）基于灰度的圖像匹配實現(xiàn)。如圖6及表5所示，基于灰度的圖像匹配算法是以像素為基礎(chǔ)的，所以該算法實現(xiàn)較為簡單，但是計算量很大［12－15］。通過這一組實驗結(jié)果可知，隨著匹配模板尺寸的增大，即像元數(shù)量增多，匹配所用的時間就會越長，匹配誤差增大，匹配吻合度下降，效果變差。

圖6 基于灰度的圖像匹配結(jié)果

表5 基于灰度的圖像匹配結(jié)果分析

2）基于Laplace譜的點(diǎn)模式匹配實現(xiàn)。如圖7及表6所示，這一組基于Laplace譜的匹配技術(shù)的實現(xiàn)表明，該匹配算法把復(fù)雜的圖像信息轉(zhuǎn)化為簡單的相關(guān)矩陣求解問題，不僅使復(fù)雜的問題簡單化，在一定程度上減輕了計算負(fù)擔(dān)，且匹配精度高而穩(wěn)定。

圖7 基于Laplace譜的點(diǎn)模式匹配結(jié)果

表6 基于Laplace譜的點(diǎn)模式匹配結(jié)果分析

通過上述兩種不同匹配技術(shù)的實現(xiàn)對比可知，在一定程度上基于Laplace譜的匹配算法比基于灰度的圖像匹配算法減輕了計算負(fù)擔(dān)，節(jié)約了計算時間，提高了匹配的精度，且穩(wěn)定性較好。該算法的匹配精度滿足當(dāng)前對圖像匹配精度［7］的要求。

3 結(jié)束語

本文實驗表明基于譜分析方法的點(diǎn)模式匹配算法在很好地概括影像中所包含的信息的前提下，把復(fù)雜的圖像簡化成簡單的求解特征值和特征向量的問題，在一定程度上使復(fù)雜的問題簡單化，減輕計算負(fù)擔(dān)，不僅在很大程度上減少工作量，而且解決傳統(tǒng)意義上基于圖像局部灰度信息匹配效果差的問題，很好地實現(xiàn)圖像的匹配。

［1］ 饒俊飛.基于灰度的圖像匹配方法研究［D］.武漢：武漢理工大學(xué)，2005.

［2］ LI Baihua，MENG Qingguang，HOLSTEIN H.Point Pattern Matching andApplications［J］.Aberystwyth U－niversity of Wales，2009，87（4）154－157.

［3］ 沈玲.基于圖譜的點(diǎn)模式匹配算法研究［D］.合肥：安徽大學(xué)，2010.

［4］ 王松濤.基于譜圖理論的點(diǎn)模式匹配算法研究［D］.武漢：武漢理工大學(xué)，2011.

［5］ 于志鵬，李曉明.基于譜圖理論的特征匹配原理研究［J］.太原師范學(xué)院學(xué)報，2012，11（2）：68－71.

［6］ 江波.基于圖譜理論的圖像描述與匹配算法研究［D］.合肥：安徽大學(xué)，2012.

［7］ 劉志忠.基于譜圖理論的結(jié)構(gòu)描述子及其在點(diǎn)模式匹配中的［D］.合肥：安徽大學(xué)，2014

［8］ 夏云.譜圖理論在圖像配準(zhǔn)中的應(yīng)用研究［D］.合肥：安徽大學(xué)，2010.

［9］ 唐俊，高天，梁棟，等.點(diǎn)模式匹配——基于譜描述子的算法［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2013，25（9）：1338－1343.

［10］張昌芳，楊宏文，胡衛(wèi)東，等.一種用于點(diǎn)模式匹配的該進(jìn)型譜方法［J］.計算機(jī)工程，2009，35（2）：10－12.

［11］黃金，石杏喜.基于Matlab的差分GPS算法分析與軟件測試［J］.黑龍江工程學(xué)院學(xué)報，2015，29（2）：30－34.

［12］卜麗靜，吳暢，何志博，等.利用紋理特征的SAR與光學(xué)圖像融合方法研究［J］.測繪工程，2015，24（5）：5－10.

［13］陳超.一種基于GMM和GraphCuts的圖像分割方法［J］.測繪工程，2014，23（12）：52－55.

［14］郭俊喜.多源高分辨率遙感影像自動匹配算法［J］.測繪工程，2014，23（7）：17－21.

［15］張建華，基于灰度的模板匹配算法研究［D］.呼和浩特：內(nèi)蒙古農(nóng)業(yè)大學(xué)，2013.