一種利用鄰近特征點夾角一致性約束的匹配提純方法

羅 媺,孫 涵,劉寧鐘

(南京航空航天大學 計算機科學與技術學院,南京 211106)

1 引 言

特征匹配[1]是檢驗圖像相似性的一個重要方法,廣泛應用在目標識別、跟蹤等領域.特征匹配的精度和速度一直是研究關注的重點.到目前為止,多數(shù)特征匹配的方法在利用局部特征點匹配時,未考慮到全局信息,很容易出現(xiàn)誤匹配,因此如何篩選出正確的匹配點對是提高匹配正確率的關鍵問題.

1987年,Fischler[2]等人提出了隨機抽樣一致性(RANSAC)方法,該方法通過迭代抽取觀測數(shù)據(jù)子集,用其來擬合模型參數(shù),直到模型能滿足足夠多的樣本點,則認為該子集是正確的.該方法是目前主流的匹配點提純方法.2008年,龔聲蓉[3]等提出了基于視差梯度約束的匹配點提純算法,該方法在RANSAC的基礎上,在計算變換模型之前,加入基于視差梯度約束的預檢驗過程,先檢驗隨機選取的點是否存在誤匹配,若存在,則重新選取.2015年,謝亮[4]等人提出了一種利用Hough變換的匹配點對提純算法.先觀察兩幅圖像的對應關系,選擇一個合適的數(shù)學模型,利用Hough變換確定模型方程參數(shù)的解.然后檢驗最開始的匹配點對,剔除不符合模型方程的匹配點對.

車型分類[5]作為智能交通的一個研究分支,是近年來研究的熱點問題.2003年,劉怡光[6]等人利用多層前向神經(jīng)網(wǎng)絡進行目標識別,介紹了網(wǎng)絡拓撲結構并應用在車型分類上,該方法結合模式識別和模糊邏輯,進行了監(jiān)督學習,通過大量實驗表明對車型的輪廓分類有較高的準確率,并且對像素的干擾有一定抵抗能力.2004年,陳愛斌[7]提出了一種利用K-L變換提取車輛特征,得到降維特征子空間,再用BP神經(jīng)網(wǎng)絡進行車型分類的方法.2010年,黃燦[8]提出一種基于局部特征的車輛識別方法,利用SIFT特征將車型精確分類至48種.

利用神經(jīng)網(wǎng)絡解決車型分類問題雖然有很強的擬合能力,但不能直觀地觀察到推理過程,信息丟失也較為嚴重.利用特征匹配解決車型分類問題時,先用傳統(tǒng)方法提取特征,再計算兩幅圖像特征描述子歐氏距離,誤匹配較多.針對車輛這類特定目標的對稱性強、局部區(qū)域相似較多的特性,本文提出了一種基于鄰近特征點夾角一致性約束的匹配提純方法,并應用于車型分類上.該方法充分考慮了特定目標幾何結構上重復性較多的特點,通過鄰近點夾角約束和空間區(qū)塊約束,不僅能剔除一些明顯錯誤的匹配點,還能將局部相似但空間位置不同的誤匹配點剔除.

2 特征點的匹配和提純

2.1 特征點匹配方法

提取出特征點后,需要根據(jù)一定的規(guī)則判定兩幅圖像中哪些特征點為匹配點對.常用的方法是先利用KD-Tree查詢,找到最近距離和次近距離的點,若最近距離與次近距離之比大于某個比率,則判定這兩個特征點為匹配點對.計算KD-Tree時,最簡單的是每一個特征點與另一幅圖中所有特征點逐一比較,計算出所有的距離,即窮舉法,這種方法雖然省去了數(shù)據(jù)預處理時間,但因為檢測出的特征點往往數(shù)目很多,窮舉法效率很低,如何利用一種數(shù)據(jù)結構,提升檢索效率是需要解決的問題.

KD-Tree是目前在特征匹配上應用最廣泛的一種數(shù)據(jù)結構,它通過將空間劃分為互不重疊的子空間,提高了檢索效率.對所有特征點,給定一個數(shù)據(jù)點時,為了在這組數(shù)據(jù)中快速找到其近鄰,KD-Tree采用分治思想,將空間劃分為兩部分.在子空間中,又將其劃分為兩部分,如此直到所有數(shù)據(jù)點都歸類.

2.2 匹配提純方法

在匹配點提純上,隨機抽樣一致性RANSAC(Random Sample Consensus)是目前公認的準確率比較高的模型估計算法.它通過采樣和驗證兩個步驟,求解使大部分特征點都能滿足的數(shù)學模型參數(shù).然而,RANSAC算法的缺點是效率不高,至少需要4個匹配點對來估計模型參數(shù);而且它計算參數(shù)的迭代次數(shù)沒有上限,如果設置迭代次數(shù)的上限,可能得不到最優(yōu)的結果,甚至會偏差很大.

2013年,王亞偉[12]等人提出了一種改進的匹配點提純算法mRANSAC.它針對數(shù)字圖像離散采樣導致匹配點不能對應,一個變換矩陣往往不能模擬出所有正確匹配點的缺點,利用多個變換矩陣增加匹配點數(shù),并根據(jù)具體應用環(huán)境,設計了并集法、減集法、自適應內(nèi)點數(shù)閾值法三種策略,使匹配提純結果比RANSAC高出60%到300%.但是對于形變較大的圖像,由于無法自適應設置距離誤差,可能會出現(xiàn)正確率不高或較多錯誤匹配點對沒有剔除的情況.

2014年,趙洋洋[13]等人提出了一種基于偏移空間局部一致性的匹配點對提純算法,也是一種RANSAC的改進算法.在計算模型參數(shù)之前,首先計算將初始匹配點映射到偏移空間,保持偏移空間局部一致性的點會落入集中的幾個Bin內(nèi),只保留落入這些Bin內(nèi)的點.然后再利用RANSAC算法對這些點進行提純.該算法能剔除一些噪音,但當形變大,落入Bin內(nèi)的點集中度不高時,可能會剔除很多正確的匹配點對.

本文采用主流的RANSAC算法進行對比實驗,RANSAC在SIFT特征篩選中的流程是:

第1步.從樣本集中隨機選取一個包含4個匹配點對的RANSAC樣本集.

第2步.根據(jù)這4個匹配點對計算模型M.

第3步.根據(jù)樣本集、模型M和誤差度量函數(shù)計算滿足當前模型的一致集,并記錄一致集中元素個數(shù).

第4步.根據(jù)當前一致集中元素個數(shù)判斷是否最優(yōu)一致集,即包含最多元素個數(shù)的集,若是則更新當前最優(yōu)一致集.

第5步.更新當前錯誤概率p,如果p小于允許最小錯誤概率則停止,否則繼續(xù)步驟1到步驟4.

2.3 常見誤匹配情況分析

在有光照、顏色變化的車輛圖片上,初步利用SIFT特征點建立KD-Tree結構,尋找到最近和次近鄰,使用距離比值法初步篩選出匹配點對后,對錯誤的匹配點對觀察,總結其規(guī)律,歸為兩類:某些含有重復結構的地方,如車牌的四個角,車標,前擋板處的特征點很容易誤匹配到相似結構處.

針對以上兩種情況, 都是因為沒有考慮全局信息引起的.為了盡可能減少這兩種誤匹配, 本文利用了特征點和其鄰近點的約束關系, 將那些錯誤的匹配點對初步篩選出來.通過觀察發(fā)現(xiàn)誤匹配點中心小區(qū)域內(nèi)圖像差異很大, 利用這個特性, 再進行小區(qū)域內(nèi)直方圖對比, 可以進一步確定是否為誤匹配.

3 鄰近特征點集夾角一致性約束與度量

3.1 鄰近特征點夾角定義

3.2 鄰近特征點集夾角一致性約束

特征點與其周圍鄰近點夾角一致原則基本思想如下:

若待匹配圖像和模板圖像的某對特征點是正確匹配點對,通過3.1節(jié)描述分別計算出θ和θ＾′,得到夾角差α后,應當有如下關系:

1)當圖像沒有明顯的仿射變換時,α為零;

2)當圖像僅有縮放變換時,α為零;

在本方法中,為了排除圖像的噪聲干擾,設置了2個松弛參數(shù),分別是偏移角度上限θ和容錯個數(shù)nError.僅當偏移夾角差超過偏移角度上限,并且超過這個閾值的鄰近點個數(shù)大于容錯個數(shù)時,才判定該對中心點為誤匹配點對.

3.3 基于相關系數(shù)的度量方法

相關系數(shù)即歸一化的協(xié)方差.它的定義為兩個向量的協(xié)方差除以它們的標準差:

(1)

相關系數(shù)的范圍在-1到1之間浮動,不會因為計量單位的變化數(shù)值太大或太小,相對于協(xié)方差有便于橫向比較的優(yōu)勢.

圖1 鄰近特征點夾角Fig.1 Adjacent points′ angles

在本文中, 為了計算出兩幅圖像的相似性, 我們先獲取匹配點對周圍1/M*Width*Height大小窗口的區(qū)塊, 得到其灰度化圖像的直方圖, 計算兩幅直方圖的歸一化相關系數(shù)[14]d:

(2)

4 利用鄰近特征點集夾角一致性約束的匹配提純算法

4.1 算法描述

算法1.利用鄰近特征點集夾角一致性約束的匹配提純算法(見表1)

4.2 實驗結果與分析

4.2.1 實驗設置與算法性能評價指標

本文在Mikolajczyk[15]的特征數(shù)據(jù)集和CompCars[16]數(shù)據(jù)集上實驗.通過考察正確率,召回率等指標,分析算法性能.由于nError與偏移角度上限θ互相獨立,偏移角度上限θ和容錯個數(shù)nError的設定通過控制變量,在保證其他參數(shù)不變的情況下,將一個參數(shù)在一定范圍內(nèi)浮動,利用準確率和召回率的ROC曲線,計算曲線下面積AUC評估性能.應用于車型分類時,將待識別圖片與模板車輛圖片匹配,歸入經(jīng)本文算法剔除后余下匹配點對最多的一組.

4.2.2 實驗結果及分析

分別獲得兩組最優(yōu)實驗結果:控制偏移角度上限不變,容錯個數(shù)nError從0到5變化時,召回率和準確率如圖2(a)所示.在nError=3時,曲線下面積達到最大,此時性能最好;控制容錯個數(shù)不變,偏移角度上限θ從0到60°變化時,召回率和準確率如圖2(b)所示.在θ=15°時.曲線下面積達到最大,此時性能最好.

在Mikolajczyk特征數(shù)據(jù)集上實驗,本文的算法與RANSAC算法對比如圖3(a),圖3(b)和圖3(c)所示,圖3(a)表示所有匹配點對,圖3(b)表示本文算法剔除的10個點對,圖3(c)表示RANSAC算法剔除的14個點對.可以看出,本文剔除的10個點有8個為誤匹配點對,RANSAC算法剔除的14個點中,有8個為真實誤匹配點.

表1 利用鄰近特征點集夾角一致性約束的匹配提純算法
Table 1 Matched points purification algorithm based on the consistency constraint of adjacent feature points′ angles

輸入：模板圖像中特征點坐標Oi(i=1…N)，待匹配圖像中對應匹配點坐標O′i(i=1…N)；Oi的鄰近點坐標Pj(j=1…M)，待匹配圖像中對應點坐標P′j(j=1…M)．輸出：true?判定為正確匹配對；false?判定為誤匹配對．Begin1．fori=1toN2． forj=1toM3． αij=cos-1(OiPj，O′iP′j)4． end5． end6． β=∑Ni=1∑Mj=1αij/(N×M)7． b=08． fori=1toN9． forj=1toM10． ifαij>β+θ11． b++12． endif13． end14． ifb

在CompCars數(shù)據(jù)集上實驗.連線表示原始匹配特征點對,其中本文算法剔除的特征點對用加粗線表示.同一車型如圖4(a),圖4(c),圖4(e),圖4(g)所示,不是同一車型的情況如圖4(b),圖4(d),圖4(f),圖4(h)所示,其正確匹配數(shù)目明顯少于前一組.

圖2 參數(shù)與性能Fig.2 Parameters and performance

圖3 RANSAC和本文方法提純示例Fig.3 RANSAC and the proposed method purify examples

對100張包含旋轉(zhuǎn)、縮放、模糊、馬賽克、光照變換的圖像分別進行RANSAC和本文算法提純,如表2所示,本文算法提純的正確率和對于許多包含旋轉(zhuǎn)縮放的數(shù)據(jù)集有很高的魯棒性,相比之下,RANSAC方法提純的正確率總體相當,但不穩(wěn)定,兩次同樣的輸入可能篩選出不同的匹配點對,召回率上RANSAC算法略高一些,在時間復雜度上,本文算法因為避免了迭代計算,較RANSAC有明顯優(yōu)勢,節(jié)省約2/3時間.

圖4 車型分類Fig.4 Vehicle classification

對250張包含5種車型正視視角的圖片分類統(tǒng)計結果如表3所示,對車型的分類準確率達到了90%以上.

表2 本文和RANSAC算法對比
Table 2 Proposed method and RANSAC purification contrast

ResidEast＿ParkBikeTreesInriaCompCarsRANSAC本文RANSAC本文RANSAC本文RANSAC本文RANSAC本文RANSAC本文準確率0．790．780．920．920．950．930．890．900．920．910．900．92召回率0．820．730．930．870．830．710．750．640．860．810．890．76時間/S21．87．47．31．82．00．420．65．82．60．79．73．4

5 結 論

本文提出了一種利用鄰近特征點夾角一致性約束的匹配提純方法,并應用于車型識別.該方法針對特定目標對稱性強、相似特征點多時容易產(chǎn)生誤匹配的情況,根據(jù)兩幅待匹配圖像中對應鄰近特征點夾角應當一致的原則,并利用局部圖像塊直方圖信息,對SIFT特征點匹配結果提純.本文方法對各種仿射變換有很強的抗干擾能力,并對一些濾鏡變換也有較強的魯棒性,與主流RANSAC方法的對比結果表明,準確率相當?shù)那闆r下,耗時更少.此方法應用到車型分類上,達到了百分之九十以上的準確率.

表3 本文算法車型分類正確率
Table 3 Proposed algorithm vehicle classification precision

車型1車型2車型3車型4車型5總正確分類數(shù)4645414647225圖片總數(shù)5050505050250正確分類率0．920．900．820．920．940．90

[1] Xu Yi,Zhou Jun,Zhou Yuan-hua.On stereo matching technology[J].Computer Engineering & Applications,2003,39(15):1-5.

[2] Fischler M A,Bolles R C.Random sample consensus:a paradigm for model fitting with applications to image analysis and automated cartography[M].Readings in Computer Vision:Issues,Problems,Principles,and Paradigms,Morgan Kaufmann Publishers Inc.,1987:726-740.

[3] Gong Sheng-rong,Zhao Wan-jin,Liu Chun-ping.Matched points purify algorithm based on gradient of disparity constraint[J].Journal of System Simulation,2008(S1):407-410.

[4] Xie Liang,Chen Shu,Zhang Jun,et al.Purifying algorithm for rough matched pairs using hough transform[J].International Journal of Image & Graphics,2015,20(8):1017-1025.

[5] Ki Y K,Baik D K.Vehicle-classification algorithm for single-loop detectors using neural networks[J].IEEE Transactions on Vehicular Technology,2006,55(6):1704-1711.

[6] Liu Yie-guang,You Zhi-sheng.An neural network for image object recognition and its application to car type recognition[J].Computer Engineering,2003,29(3):30-32.

[7] Chen Ai-bin.Vehicle recognition based on eigen-vehicle[J].Information Technology,2004,28(5):44-45.

[8] Huang Can.Vehicle recognition based on local feature[D].Shanghai:Shanghai Jiao TongUniversity,2010.

[9] Smith P L.New technique for estimating the MTF of an imaging system from its edge response[J].Applied Optics,1972,11(6):2974.

[10] Yue Si-cong,Zhao Rong-chun,Zheng Jiang-bin.MERF based edge detection with adaptive threshold[J].Dianzi Yu Xinxi Xuebao/journal of Electronics & Information Technology,2008,30(4):957-960.

[11] Caffarelli L,Nirenberg L,Spruck J.The dirichlet problem for nonlinear second order elliptic equations,III:Functions of the eigenvalues of the hessian[J].Acta Mathematica,1985,155(1):261-301.

[12] Wang Ya-wei,Xu Ting-fa,Wang Ji-hui.Improved matching point purification algorithm mRANSAC[C].Dongnan Daxue Xuebao,2013:163-167.

[13] Zhao Yang-yang,Li Xiao-qiang.Matching points purification based on offst space local consensus[J].Computer Applications & Software,2014,31(7):149-151.

[14] Lin L I.A concordance correlation coefficient to evaluate reproducibility[J].Biometrics,1989,45(1):255-268.

[15] Mikolajczyk K,Tuytelaars T,Schmid C,et al.A comparison of affine region detectors[J].International Journal of Computer Vision,2005,65(1-2):43-72.

[16] Yang L,Luo P,Loy C C,et al.A large-scale car dataset for fine-grained categorization and verification[C].Computer Vision and Pattern Recognition.IEEE,2015.

附中文參考文獻：

[1] 徐 奕,周 軍,周源華.立體視覺匹配技術[J].計算機工程與應用,2003,39(15):1-5.

[3] 龔聲蓉,趙萬金,劉純平.基于視差梯度約束的匹配點提純算法[J].系統(tǒng)仿真學報,2008(S1):407-410.

[4] 謝 亮,陳 姝,張 鈞,等.利用Hough變換的匹配對提純[J].中國圖象圖形學報,2015,20(8):1017-1025.

[6] 劉怡光,游志勝.一種用于圖像目標識別的神經(jīng)網(wǎng)絡及其車型識別應用[J].計算機工程,2003,29(3):30-32.

[7] 陳愛斌.基于特征車的汽車車型識別[J].信息技術,2004,28(5):44-45.

[8] 黃 燦.基于局部特征的車輛識別[D].上海:上海交通大學,2010.

[10] 岳思聰,趙榮椿,鄭江濱.基于多尺度邊緣響應函數(shù)的自適應閾值邊緣檢測算法[J].電子與信息學報,2008,30(4):957-960.

[12] 王亞偉,許廷發(fā),王吉暉.改進的匹配點提純算法mRANSAC[C].中國智能自動化學術會議,2013:163-167.

[13] 趙洋洋,李曉強.基于偏移空間局部一致性的匹配點提純[J].計算機應用與軟件,2014,31(7):149-151.