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

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

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

1 概述

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

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

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

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

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

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

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

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

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

3 圖像匹配方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 模擬數(shù)據(jù)實(shí)驗(yàn)

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

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

圖2 點(diǎn)集之間僅存在位置擾動(dòng)的匹配結(jié)果

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

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

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

4.2 真實(shí)圖像實(shí)驗(yàn)

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

表1給出了30組圖像之間的平均匹配精度和相對(duì)目標(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組真實(shí)圖像的匹配性能比較

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

4.3 運(yùn)行時(shí)間分析

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

表2 3種方法的運(yùn)行時(shí)間比較 s

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

5 結(jié)束語

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

[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]鄭雪梅,范 勇,石琦凱,等.一種基于點(diǎn)的快速圖像配準(zhǔn)算法[J].計(jì)算機(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)東,等.一種用于點(diǎn)模式匹配的改進(jìn)型譜方法[J].計(jì)算機(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.