張麗麗，羅 斌，湯 進(jìn)，孫登第

(1.計算智能與信號處理教育部重點實驗室，合肥 230039；2.安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院安徽省工業(yè)圖像處理與分析重點實驗室，合肥 230039)

1 概述

圖像匹配是圖像處理中的關(guān)鍵技術(shù)之一，在遙感圖像分析、醫(yī)學(xué)圖像分析、計算機視覺等方面有著重要的應(yīng)用[1]。圖像的特征點是圖像中灰度信號二維變化較大的圖像點，對圖像形變、灰度變化以及遮擋等具有較好的適應(yīng)能力，因此，基于特征點的圖像匹配是一種重要的圖像匹配方法。而建立圖像特征點之間的正確匹配是計算機視覺和模式識別領(lǐng)域中的一個基本問題，也是圖像匹配的研究熱點。事實上求解特征點之間的正確匹配是一個典型的NP問題，學(xué)者們提出了很多近似方法。目前，基于特征點的圖像匹配方法主要分為2類：(1)先通過特征點之間的相似性度量得到特征點之間的初始匹配，再使用排錯算法得到滿足某種特性的特征點匹配，而當(dāng)特征點之間的相似性度量不明顯時，該種算法往往得不到滿意的結(jié)果[2-3]；(2)主要考慮特征點之間的幾何關(guān)系，再結(jié)合特征點之間的相似性度量直接獲得特征點匹配[4-5]。

在第(2)類方法中，文獻(xiàn)[4]提出建立以特征點集之間的候選匹配為頂點的圖，再通過對所有頂點之間的親鄰矩陣進(jìn)行譜分解以得到特征點之間的最優(yōu)匹配。采用譜方法求解特征點匹配問題往往具有較好的匹配效果[4,6-7]，得到廣泛的應(yīng)用，但是其中親鄰矩陣(特別是當(dāng)特征點集的規(guī)模較大時)的譜分解需要耗費大量的時間[7]。文獻(xiàn)[7]提出使用加權(quán)投票方法，將每個候選匹配同時作為投票者和接收投票者，最后通過簡單的加法運算和排序操作確定出最優(yōu)匹配。雖在運行時間上明顯減少，但是特征點之間的匹配精度難以保持。

投票方法是一種有效的決策方法，在圖像處理與模式識別中具有廣泛的應(yīng)用[8-9]。本文提出一種改進(jìn)的基于加權(quán)投票的圖像匹配方法，認(rèn)為每個候選匹配作為投票者和接收投票者，以一定的權(quán)重進(jìn)行投票，并給出一種估計每個候選匹配投票權(quán)重的方法。

2 親鄰矩陣及目標(biāo)函數(shù)的建立

記矩陣A、B為待匹配的2幅圖像，提取的特征點集分別為：

記指標(biāo)向量為：

候選匹配之間的親鄰矩陣 W=(Wij)，i, j=1,2,…,K，其中，W 的對角元表示特征點的特征描述向量之間的親鄰程度，非對角元表示候選匹配之間的幾何一致性親鄰程度，即：

基于特征點的圖像匹配可歸結(jié)為從候選匹配中尋找滿足一定限制的匹配，使得所選的匹配之間的幾何一致性最大，即：

文獻(xiàn)[4]提出對親鄰矩陣W 進(jìn)行譜分解，再結(jié)合貪心算法得到特征點之間的最優(yōu)匹配。

3 圖像匹配方法

3.1 基于加權(quán)投票的圖像匹配方法

基于加權(quán)投票的圖像匹配方法[7]將每個候選匹配作為投票者，每個投票者不僅給其他候選匹配投票，還接收其他候選匹配的投票，而投票值估計為兩候選匹配之間的親鄰程度 W((i,i'),(j,j'))，并將每個候選匹配接收投票的累積和作為正確匹配的評價值，即：

3.2 基于加權(quán)投票的圖像匹配改進(jìn)方法

基于權(quán)重的加權(quán)投票是一種普遍的投票方式，每個參與者以一定權(quán)重對其他參與者進(jìn)行投票。本文提出一種改進(jìn)的基于加權(quán)投票的圖像匹配方法，認(rèn)為每個候選匹配不僅基于親鄰程度對其他候選匹配進(jìn)行投票，而且以一定的權(quán)重進(jìn)行投票，如圖1所示，實線表示候選匹配(1,1')，虛線表示其他與候選匹配(1,1')不沖突的候選匹配。

圖1 基于加權(quán)投票的圖像匹配改進(jìn)方法

本文給出一種估計候選匹配投票權(quán)重的方法：計算每個候選匹配(i,i′)的接收投票值累積和c'(i,i′)并歸一化，即得其投票權(quán)重c(i,i′)。這樣接收投票累積和越大，表明該候選匹配為正確匹配的可能性越大，那么對其他候選匹配投票的權(quán)重也越大。

各級安全參與人員可在線創(chuàng)建和啟動檢查計劃，系統(tǒng)生成并推送對應(yīng)的檢查表至檢查人的手持終端，檢查人持手持終端按照標(biāo)準(zhǔn)檢查表進(jìn)行比對檢查，并反饋問題。

按照此種方式得到的每個候選匹配的綜合投票值構(gòu)成其為正確匹配的評價值，即：

其中，c(j,j′)為候選匹配(j,j′)投票的權(quán)重。因此，特征點i的最優(yōu)匹配為

綜上所述，基于加權(quán)投票的圖像匹配方法具體描述如下：

Step1 利用式(1)、式(2)計算親鄰矩陣W ，根據(jù)式(5)、式(6)計算所有候選匹配投票的權(quán)重c。

Step2 利用式(7)計算每個候選匹配的評價值，記作向量 x?；初始化解向量x為K×1的零向量；初始化候選匹配矩陣L。

Step4 從矩陣L中刪除所有與匹配a?相沖突的匹配，即如果 a?=(i,i′)，那么所有形如 (i,j′)與 (j,i′)的匹配都與a?相沖突。

Step5 如果L已空，則返回解向量x；否則，返回至Step3。

4 實驗結(jié)果與分析

為驗證本文方法的有效性和穩(wěn)定性，本文進(jìn)行了模擬數(shù)據(jù)實驗和真實圖像實驗。選擇譜匹配方法(SM)[4]和基于加權(quán)投票的圖像匹配方法(WVPC)[7]與本文改進(jìn)的基于加權(quán)投票的圖像匹配方法(IWVPC)進(jìn)行對比，通過匹配精度和目標(biāo)函數(shù)值來評估算法的性能，其中，匹配精度=實際正確的匹配數(shù)/總的匹配數(shù)；目標(biāo)值根據(jù)式(3)計算而得。

4.1 模擬數(shù)據(jù)實驗

模擬數(shù)據(jù)通過以下方式產(chǎn)生：由計算機隨機產(chǎn)生np=25個服從均勻分布的模板集P，其中，均勻分布的區(qū)域大小為，保證每個大小為256×256的區(qū)域內(nèi)有10個點。實驗通過點的位置抖動和增加噪聲點2種方式來驗證該算法的抗噪性能和抗出格點性能。在點的位置隨機擾動實驗中，對模板集P在每個點位置上增加高斯噪聲來得到目標(biāo)集Q，即Q=P+ε( ε～N(0,σ2)，σ表示高斯噪聲水平)。在增加噪聲點實驗中，對模板集P所在區(qū)域內(nèi)隨機增加出格點來構(gòu)造目標(biāo)集Q。本文對生成的模板集和目標(biāo)集進(jìn)行模擬仿真，每組實驗均進(jìn)行50次蒙特卡羅實驗。實驗中的參數(shù)設(shè)定如下：親鄰矩陣中的對角元為0，親鄰矩陣的非對角元中 σd=10。

圖2、圖3分別給出了模板集與目標(biāo)集之間僅存在位置擾動，且位置擾動逐漸增大(噪聲水平σ從 1變化到 10)和僅存在出格點，且出格點逐漸增加(出格點從 0增加到 30)時，3種算法得到的模板集與目標(biāo)集之間的匹配精度和目標(biāo)函數(shù)值；而圖4表示出格點數(shù)固定為15，模板集與目標(biāo)點集之間還存在位置擾動，且位置擾動逐漸增大(噪聲水平σ從1變化到10)時，3種算法得到的模板集與目標(biāo)集之間的匹配精度和目標(biāo)函數(shù)值。

圖2 點集之間僅存在位置擾動的匹配結(jié)果

圖3 點集之間僅存在出格點的匹配結(jié)果

圖4 點集之間存在位置擾動和出格點的匹配結(jié)果

從圖2～圖4中可以看出，SM算法對點集的位置擾動和出格點的存在具有良好的魯棒性，IWVPC算法比WVPC算法在匹配精度和目標(biāo)函數(shù)值上都具有較大的提高，與SM算法的匹配精度和目標(biāo)函數(shù)值接近，驗證了增加候選匹配投票的權(quán)重以得到的綜合投票結(jié)果的有效性。因此，候選匹配權(quán)重的引入使 WVPC算法的匹配效果有了較大的提升。

4.2 真實圖像實驗

為了驗證本文方法解決實際圖像匹配問題的能力，從Caltech-101和 MSRC數(shù)據(jù)集中選取了 30組圖像，用MSER[10]及 SIFT[2]描述子生成候選匹配，使用相互映射誤差[11]來度量特征區(qū)域之間的相似性，令SIFT算法中確定候選匹配的閾值δ=0.6。該部分實驗中的參數(shù)設(shè)定如下：親鄰矩陣中的對角元為0，親鄰矩陣的非對角元中 σd=5。

表1給出了30組圖像之間的平均匹配精度和相對目標(biāo)函數(shù)值，部分圖像匹配結(jié)果如圖 5所示。其中，圖 5(b)的匹配精度為9/9，目標(biāo)函數(shù)值為16.3972；圖5(c)的匹配精度為7/9，目標(biāo)函數(shù)值為13.7917；圖5(d)的匹配精度為9/9，目標(biāo)函數(shù)值為16.1435。從表1可以看出，本文的IWVPC算法在匹配精度和目標(biāo)函數(shù)值上遠(yuǎn)高于WVPC算法，接近SM算法的結(jié)果。

表1 30組真實圖像的匹配性能比較

圖5 部分圖像匹配結(jié)果

4.3 運行時間分析

與SM、WVPC方法相比，本文提出的IWVPC方法區(qū)別在于候選匹配為正確匹配評價值的計算上。為比較 3種方法的時間效率，本文在主頻2 GHz、內(nèi)存1 GB的PC機上比較 3種方法在親鄰矩陣的大小變化時的運行時間，比較結(jié)果如表2所示。

表2 3種方法的運行時間比較 s

在表2中，隨著候選匹配之間的親鄰矩陣大小的增加，SM方法中對親鄰矩陣進(jìn)行譜分解所需運行時間顯著增加，而WVPC方法和IWVPC方法在計算候選匹配為正確匹配的評價值時僅需較少的運行時間。雖與WVPC方法相比，IWVPC方法的運行時間有微小的增加，但是根據(jù)前面的實驗結(jié)果，IWVPC方法卻具有接近SM方法的匹配效果。

5 結(jié)束語

本文給出一種改進(jìn)的基于加權(quán)投票的圖像匹配方法。首先建立特征點候選匹配之間的親鄰矩陣，然后對每個候選匹配投票的權(quán)重進(jìn)行估計，再將其他候選匹配對其投票結(jié)果的積累和作為該候選匹配為正確匹配的評價值，最后通過簡單的數(shù)學(xué)運算和排序操作來確定最優(yōu)匹配。模擬和真實實驗結(jié)果表明，本文方法具有較好的匹配效果和較少的運行時間。今后的工作將主要研究新的圖像匹配方法，以進(jìn)一步提高圖像匹配的匹配精度和時間效率。

[1]Liu Zhaoxia,An Jubai.A Robust Point Matching Algorithm for Image Registration[C]//Proc.of the 3rd International Conference on Machine Vision.Hong Kong,China: [s.n.],2010.

[2]David G L.Distinctive Image Features from Scale-invariant Keypoints[J].International Journal of Computer Vision,2004,60(2): 91-110.

[3]鄭雪梅,范 勇,石琦凱,等.一種基于點的快速圖像配準(zhǔn)算法[J].計算機工程,2012,38(1): 220-221.

[4]Marius L,Martial H.A Spectral Technique for Correspondence Problems Using Pairwise Constraints[C]//Proc.of the 10th IEEE International Conference on Computer Vision.Beijing,China: [s.n.],2005.

[5]張昌芳,楊宏文,胡衛(wèi)東,等.一種用于點模式匹配的改進(jìn)型譜方法[J].計算機工程,2009,35(2): 10-12.

[6]Tao Dacheng,Li Xuelong,Wu Xindong,et al.Geometric Mean for Subspace Selection[J].IEEE Transactions on Pattern Analysis Machine Intelligence,2009,31(2): 260-274.

[7]Yuan Yuan,Pang Yanwei,Wang Kongqiao,et al.Efficient Image Matching Using Weighted Voting[J].Pattern Recognition Letters,2012,33(4): 471-475.

[8]Yaron L,Thomas F.M?bius Voting for Surface Correspondence[J].ACM Transactions on Graphics,2009,28(3): 1-12.

[9]Oscar K A,Tai Chiew-Lan,Daniel C,et al.Electors Voting for fast Automatic Shape Correspondence[J].Computer Graphics Forum,2010,29(2): 645-654.

[10]Jiri M,Ondrej C,Martin U,et al.Robust Wide-baseline Stereo from Maximally Stable Extremal Regions[J].Image and Vision Computing,2004,22(10): 761-767.

[11]Minsu C,Lee Jungmin,Kyoung M L.Feature Correspondence and Deformable Object Matching via Agglomerative Correspondence Clustering[C]//Proc.of the 12th IEEE International Conference on Computer Vision.Kyoto,Japan:[s.n.],2009.