羅 媺,孫 涵,劉寧鐘

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京 211106)

1 引 言

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

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

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

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

2 特征點(diǎn)的匹配和提純

2.1 特征點(diǎn)匹配方法

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

KD-Tree是目前在特征匹配上應(yīng)用最廣泛的一種數(shù)據(jù)結(jié)構(gòu),它通過(guò)將空間劃分為互不重疊的子空間,提高了檢索效率.對(duì)所有特征點(diǎn),給定一個(gè)數(shù)據(jù)點(diǎn)時(shí),為了在這組數(shù)據(jù)中快速找到其近鄰,KD-Tree采用分治思想,將空間劃分為兩部分.在子空間中,又將其劃分為兩部分,如此直到所有數(shù)據(jù)點(diǎn)都?xì)w類(lèi).

2.2 匹配提純方法

在匹配點(diǎn)提純上,隨機(jī)抽樣一致性RANSAC(Random Sample Consensus)是目前公認(rèn)的準(zhǔn)確率比較高的模型估計(jì)算法.它通過(guò)采樣和驗(yàn)證兩個(gè)步驟,求解使大部分特征點(diǎn)都能滿足的數(shù)學(xué)模型參數(shù).然而,RANSAC算法的缺點(diǎn)是效率不高,至少需要4個(gè)匹配點(diǎn)對(duì)來(lái)估計(jì)模型參數(shù);而且它計(jì)算參數(shù)的迭代次數(shù)沒(méi)有上限,如果設(shè)置迭代次數(shù)的上限,可能得不到最優(yōu)的結(jié)果,甚至?xí)詈艽?

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

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

本文采用主流的RANSAC算法進(jìn)行對(duì)比實(shí)驗(yàn),RANSAC在SIFT特征篩選中的流程是:

第1步.從樣本集中隨機(jī)選取一個(gè)包含4個(gè)匹配點(diǎn)對(duì)的RANSAC樣本集.

第2步.根據(jù)這4個(gè)匹配點(diǎn)對(duì)計(jì)算模型M.

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

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

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

2.3 常見(jiàn)誤匹配情況分析

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

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

3 鄰近特征點(diǎn)集夾角一致性約束與度量

3.1 鄰近特征點(diǎn)夾角定義

3.2 鄰近特征點(diǎn)集夾角一致性約束

特征點(diǎn)與其周?chē)徑c(diǎn)夾角一致原則基本思想如下:

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

1)當(dāng)圖像沒(méi)有明顯的仿射變換時(shí),α為零;

2)當(dāng)圖像僅有縮放變換時(shí),α為零;

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

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

相關(guān)系數(shù)即歸一化的協(xié)方差.它的定義為兩個(gè)向量的協(xié)方差除以它們的標(biāo)準(zhǔn)差:

(1)

相關(guān)系數(shù)的范圍在-1到1之間浮動(dòng),不會(huì)因?yàn)橛?jì)量單位的變化數(shù)值太大或太小,相對(duì)于協(xié)方差有便于橫向比較的優(yōu)勢(shì).

圖1 鄰近特征點(diǎn)夾角Fig.1 Adjacent points′ angles

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

(2)

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

4.1 算法描述

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

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

4.2.1 實(shí)驗(yàn)設(shè)置與算法性能評(píng)價(jià)指標(biāo)

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

4.2.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

輸入：模板圖像中特征點(diǎn)坐標(biāo)Oi(i=1…N)，待匹配圖像中對(duì)應(yīng)匹配點(diǎn)坐標(biāo)O′i(i=1…N)；Oi的鄰近點(diǎn)坐標(biāo)Pj(j=1…M)，待匹配圖像中對(duì)應(yīng)點(diǎn)坐標(biāo)P′j(j=1…M)．輸出：true?判定為正確匹配對(duì)；false?判定為誤匹配對(duì)．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ù)集上實(shí)驗(yàn).連線表示原始匹配特征點(diǎn)對(duì),其中本文算法剔除的特征點(diǎn)對(duì)用加粗線表示.同一車(chē)型如圖4(a),圖4(c),圖4(e),圖4(g)所示,不是同一車(chē)型的情況如圖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

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

圖4 車(chē)型分類(lèi)Fig.4 Vehicle classification

對(duì)250張包含5種車(chē)型正視視角的圖片分類(lèi)統(tǒng)計(jì)結(jié)果如表3所示,對(duì)車(chē)型的分類(lèi)準(zhǔn)確率達(dá)到了90%以上.

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

ResidEast＿ParkBikeTreesInriaCompCarsRANSAC本文RANSAC本文RANSAC本文RANSAC本文RANSAC本文RANSAC本文準(zhǔn)確率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時(shí)間/S21．87．47．31．82．00．420．65．82．60．79．73．4

5 結(jié) 論

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

表3 本文算法車(chē)型分類(lèi)正確率
Table 3 Proposed algorithm vehicle classification precision

車(chē)型1車(chē)型2車(chē)型3車(chē)型4車(chē)型5總正確分類(lèi)數(shù)4645414647225圖片總數(shù)5050505050250正確分類(lèi)率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.

附中文參考文獻(xiàn)：

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

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

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

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

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

[8] 黃 燦.基于局部特征的車(chē)輛識(shí)別[D].上海:上海交通大學(xué),2010.

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

[12] 王亞偉,許廷發(fā),王吉暉.改進(jìn)的匹配點(diǎn)提純算法mRANSAC[C].中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議,2013:163-167.

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