一種基于加權投票的圖像匹配改進方法

張麗麗，羅 斌，湯 進，孫登第

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

1 概述

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

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

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

2 親鄰矩陣及目標函數的建立

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

記指標向量為：

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

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

文獻[4]提出對親鄰矩陣W 進行譜分解，再結合貪心算法得到特征點之間的最優匹配。

3 圖像匹配方法

3.1 基于加權投票的圖像匹配方法

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

3.2 基于加權投票的圖像匹配改進方法

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

圖1 基于加權投票的圖像匹配改進方法

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

各級安全參與人員可在線創建和啟動檢查計劃，系統生成并推送對應的檢查表至檢查人的手持終端，檢查人持手持終端按照標準檢查表進行比對檢查，并反饋問題。

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

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

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

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

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

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

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

4 實驗結果與分析

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

4.1 模擬數據實驗

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

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

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

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

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

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

4.2 真實圖像實驗

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

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

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

圖5 部分圖像匹配結果

4.3 運行時間分析

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

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

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

5 結束語

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

[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]鄭雪梅,范 勇,石琦凱,等.一種基于點的快速圖像配準算法[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]張昌芳,楊宏文,胡衛東,等.一種用于點模式匹配的改進型譜方法[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.