基于隨機蕨的實時車輛匹配

楊晨暉,劉守達,王子明,郭義凡,李 輝

(廈門大學信息科學與技術學院，福建 廈門 361005)

車輛匹配是智能交通系統的重要組成部分,其在停車場智能管理、道路監控、高速路自動收費等方面有著廣泛的應用前景．

基于特征的匹配算法按照描述方式的不同,目前主要分為兩大類,一類是用于處理邊緣、角點等局部特征的強特征描述,目前使用最廣泛的是尺度不變特征(SIFT)算法,其主要思想最初是由David Lowe提出[1]．目前已經有很多研究人員在SIFT算法的基礎之上對算法進行了改進和完善．主要有2004年Ke等[2]提出的PCA-SIFT算法[2];2006年Bay等[3]提出快速SIFT(SURF)算法．2009年Yu提出仿射尺度不變特征變換(ASIFT)算法[4];另一類是以提取自然特征點的方式將特征的匹配轉化為多類別分類問題．其中最具代表的是Lepetit等[5]提出的隨機樹特征匹配算法,將寬基線特征匹配問題轉化為分類問題．隨機樹特征匹配算子不需要強特征描述．將計算量大的工作轉移到訓練階段,利用基準圖像上以穩定特征點為中心的鄰域塊作為訓練樣本,并用隨機樹分類器對其進行分類．在線階段則用訓練好的分類器對待匹配圖像上檢測到的特征點鄰域塊進行分類,從而達到匹配的目的．該類算法需要離線訓練,因此限制了其應用場景,但是在條件允許其進行離線訓練的情形下,該類算法在在線運行階段能夠快速準確甚至實時地進行匹配,因此其也得到了廣泛的應用．

本文在前人研究的基礎上,將隨機蕨引入到車臉匹配領域中．隨機蕨算法由Lepetit等[6]最早提出,是對基于隨機樹算法的進一步改進．將隨機樹的層次結構特征改為了非層次結構特征．隨機蕨將寬基線圖像匹配轉化為機器學習技術問題,將運算量較大的特征匹配部分轉移到分類器訓練中．本文研究基于隨機蕨的車輛匹配方法,并克服傳統匹配速度慢的特點,從而實現對車輛準確、實時的匹配．

1 快速車臉定位

車輛大部分顯著特征的“車臉”的概念,即車輛在多尺度、多視角下具有特征不變性的區域．在交通場景中相對于復雜的背景,車輛上的特征點顯得較少,背景上的特征點將很大程度上的干擾到車輛匹配效果,并且使匹配過程更加費時．本章首先對車輛可疑區域以及車牌區域的定位,并在此基礎上,結合先驗知識,很好地對“車臉”進行定位;最后給出了“車臉”的實驗結果,并對其進行了分析．

1.1 車輛可疑區域確定

要進行車輛區域確定,可以先通過背景差分將所有非背景的前景目標分割出來,然后進行閾值化處理,獲得二值化的差分圖,并通過Canny算子獲得車輛的邊緣,最后通有效性分析確定車輛可疑區域(如圖1)．

圖1 車輛可疑區域定位流程圖Fig.1 Interest region of vehicle extraction

1.2 快速車牌定位

首先對圖像進行預處理,主要包括彩色圖像灰度化和圖像局部增強以及豎直邊緣提取和背景曲線與噪聲濾除．本文采用Zheng等[7]提出的三次掃描法濾除背景曲線和噪聲．然后,利用滑動窗口法對車牌進行初定位．最后利用水平掃描法[8]對候選車牌圖像區域進行逐行掃描進行細定位．

圖中，車牌定位結果用紅色小矩形標出，車輛可疑區域用綠色矩形標出.結合車牌定位和車輛可疑區域定位結果，得到車輛位置，使用紅色矩形標出.圖2 車臉定位結果Fig.2 Cars face location

1.3 車臉定位

設檢測到的車輛區域的左右邊界離車牌的左右邊界的距離分別為l1和l2,則取車臉的左右邊界分別為min(l1,l2)加上車牌的左右邊界．同時考慮到車輛可疑區域提取時在邊緣提取時可能會使車輛的真實區域內縮,因此將獲取的車臉的左右邊界向兩邊擴展1/4個車牌寬度(如圖2).

2 基于隨機蕨的實時車輛匹配

為了能對提取特征點進行快速匹配,采用同隨機樹特征匹配算法[6]類似的基于隨機蕨的特征匹配算法,將寬基線圖像匹配轉化為機器學習技術問題將運算量較大的特征匹配部分轉移到分類器訓練中．離線階段,建立并訓練隨機蕨分類器,在線階段,將檢測到的特征點進行分類,獲取粗匹配結果,然后用改進的順序抽樣一致性(PROSAC)算法去除誤匹配．并通過實驗說明,本文的算法能夠很好地進行實時車輛匹配．

2.1 快速多尺度特征點提取

車輛圖片平坦部分較多,導致特征點數目較少,同時為了使檢測到的特征點具有尺度不變性,建立多尺度金字塔,分別對每個尺度尋找其顯著特征點．這樣即能使檢測到的特征點滿足尺度不變的特性,又能解決車輛區域較平坦、檢測到的特征點較少的缺點．同時其算法運行時間也不會提升很大,還是能夠很好地滿足實時的要求．對不同尺寸的多幅圖片進行實驗，得到實驗結果如表1.

表1 多尺度耗時分析Tab.1 Multi-scale time-consuming analysis

2.2 隨機蕨算法

隨機蕨算法由Lepetit等[6]最早提出,是對基于隨機樹算法的進一步改進．將隨機樹的層次結構特征改為非層次結構特征,如圖3所示,將隨機樹的每層結點選取相同的決策,則樹結構可以轉化為結構相對單一的蕨結構．

圖3 隨機蕨結構Fig.3 The structure of random ferns

基于隨機蕨的樸素貝葉斯分類器的基本思想和基于隨機樹的特征識別匹配類似,可以把基準圖像描述為H個顯著特征點,并為這H個顯著的特征點建立一個數據集K={k1,…,kH},同時將每個特征點k及以其為中心的鄰域塊p(k)可能出現的各種形式作為一類ci,i=1,…,H．在運行階段,對輸入圖像每個特征點kinput及以其為中心的鄰域塊p(kinput),判斷它是否屬于H個特征點中的一個類ci．

設fj,j=1,…,N為特征點鄰域塊p(kinput)產生的二元特征集,令p(kinput)的尺寸為L×L(一般取L=32),則fj取決于鄰域塊p(kinput)中在隨機生成的兩像素位置dj1和dj2的灰度值Idj1和Idj2的大小,這些隨機位置在分類器訓練時生成,并用在離線訓練與在線運行階段,即

(1)

p(kinput)所屬的類別可以定義為

(2)

式中C表示類別,式(2)可由貝葉斯公式轉化為

P(C=ci|f1,f2,…，fN)=

(3)

因為先驗概率P(C)為均勻分布,且公式(3)分母部分與類別無關,所以式(2)可以化為

(4)

由于fj之間的獨立性,

(5)

為了降低存儲量并保證fj之間的相關性,用半樸素貝葉斯分類器來代替樸素貝葉斯分類器．將fj分為M組,每組包含S=N/M個二元特征,在半樸素貝葉斯模型下,可以認為不同組的二元特征之間相互獨立,而同組內二元特征之間具有相關性，同時可以將這些組定義為蕨特征．則公式(3)中可以轉化為

(6)

式中Fm=[fσ(m,1),fσ(m,2),…，fσ(m,S)],m=1,…,M表示第m個蕨,fσ(m,j)表示范圍為1,…,N的隨機數．由此可知p(kinput)的所屬類別為

(7)

2.3 訓 練

對基準圖像進行一系列的操作來合成虛擬的特征圖像樣本集合．可以在基準圖像I0上提取特征點及其周圍(32×32)像素的鄰域塊,對其進行仿射變換獲得訓練集Btrain．

隨機產生Ntotal幅虛擬圖像,并將這些圖像Ii中檢測到的特征點對應到基準圖像I0中,并記錄特征點k在虛擬圖像中被檢測到的次數,即可求得特征點k的被檢測概率為

(8)

式中Ndetected為特征點k在虛擬圖像中被檢測到的次數．因此,可以取概率P(k)最高的H個特征點作為基準圖像的穩定特征點,并將其作為分類器的初始類進行分類訓練,即各特征點及其鄰域塊所屬的類為ci,i=1,…,H,實驗中取H=400．

由以上兩步,可以求得訓練圖像Btrain和分類器的初始類ci之后,對每個訓練圖像在L×L(取L=32)范圍內,按照隨機選取M×S(M=30,S=12)對像素位置dj1和dj2．對每個初始類ci根據這M×S對隨機位置上像素點的灰度值由式(1)計算類ci的M個隨機蕨中S個二元特征fi的值,并根據這個值計算出式(7)中的每個隨機蕨Fm和類ci的類條件概率P(Fm|C=ci)．

2.4 在線特征點檢測與匹配

在線檢測階段我們首先用快速多尺度特征點提取的方法提取前景車輛的特征點．由于檢測到的特征點不再用在分類器的建立上,非車輛上的特征點也可以快速的用分類器進行分類匹配．因此在線檢測階段不用進行車臉定位,而只要對背景差分提取的前景車輛進行檢測即可．

2.5 改進的PROSAC誤匹配特征對的剔除

確定了要配準的2幅圖像的對應點后,利用這些對應點對,以1幅圖像為參考,求解出2幅圖像之間的幾何變換矩陣H的參數,并由此來去除誤匹配．為此可以采用隨機抽樣一致性(RANSAC)算法來去除誤匹配．然而,當誤匹配特征對的數目在總的匹配特征對中所占的比例過大時,RANSAC算法不能很好地處理這種情況．由于隨機蕨的圖像匹配算法沒有直接對誤匹配對去除的策略,在2幅圖像間差距較大時,誤匹配對占總匹配對的比例可能會較大,所以在此時會失效．

可以采用PROSAC算法來進行模型擬合,剔除誤匹配特征對,PROSAC算法由Chum等[9]于2005年提出,該方法優先從高品質方程的數據子集中抽取樣本,即選取那些屬于正確匹配概率高的樣本,有利于迭代過程的快速收斂,能夠很好地應對誤匹配所占總匹配比例較大時的情形．

而在內點集合的應用上,由于PROSAC算法在初期就能迅速找到全部由內點組成的樣本，所以我們可以對PROSAC算法進行改進,交替從內點集中和有序的樣本集中選擇樣本點．改進的PROSAC算法如下:

t=0,n=m,n*=N重復,直到找到解:

1) 選擇假定的集合

如果n

2) 大小為m的半隨機樣本Mt

交替進行(i),(ii)：

(i)a從Bik(當前內點集合)中隨機選擇大小為m的隨機樣本，

(ii)b隨機從Un中選取m個點；

3) 模型參數估計

從樣本Mt中計算模型參數pt；

4) 模型驗證

找到參數為pt的模型的支持(例如一致的數據點),如果支持數目大于當前最大支持數,則更新當前所得內點集合Bik.

對下面2幅圖進行匹配并比較結果,其中實驗時最大迭代次數為1 500次,并且當內點集中的個數大于50時則退出循環，實驗結果如圖4所示.

圖4 粗匹配結果Fig.4 Initial match result

與RANSAC和PROSAC對比,結果如表2和表3所示.

表2 誤匹配較多時，各算法比較Tab.2 More mismatch situation,comparison of the algorithm

注：運行程序100次取平均值.

由實驗可知,改進后的PROSAC能夠很好的處理誤匹配點較多,和較少時的情形,能夠減少迭代次數,從而減少運行時間．

表3 誤匹配較少時，各算法比較Tab.3 Less mismatch situation, comparison of the algorithms

注：運行程序100次取平均值.

3 實驗結果與分析

首先對一段含有339幀的視頻進行測試,每幀圖片的大小為600×800像素，匹配結果為264幀匹配成功，75幀匹配失敗.在DEBUG模式下耗時26 487 ms,平均每次匹配耗時78.13 ms，其中每幀檢測特征點耗時平均為34.56 ms,匹配時間為43.57 ms；在RELEASE模式下耗時10 698 ms,平均每次匹配耗時31.56 ms，其中每幀檢測特征點耗時平均為18.23 ms,匹配時間為13.33 ms．分析可知,我們的匹配可以達到實時的要求．接著在尺寸、角度、光照、遮擋、噪聲等干擾情況下對本文的算法與SIFT進行比較．為了公平,在SIFT算法進行匹配時將“車臉”區域提前截取出來,作為基準圖像,同時將算法總耗時減去基準圖像檢測特征點的時間作為SIFT的匹配時間，實驗結果如圖5和表4所示.

左邊圖像是使用SIFT匹配的結果，右邊是使用本文算法匹配結果.從上到下，分別是在不同的尺度、角度、光照、遮擋、高斯噪聲、椒鹽噪聲條件下的比較.圖5 匹配結果對比Fig.5 Comparison of matches

通過以上實驗說明,本文算法在保證實時處理車輛匹配的同時,能夠很好地處理尺寸、角度、亮度變化,以及遮擋、噪聲等影響．在檢測到的匹配對和SIFT差不多的同時,誤匹配較少,匹配正確率接近100%．在時間上、性能上都比SIFT算法有大幅度提高．

4 結 論

本文結合車輛區域定位與車牌快速定位來對包含車輛大部分顯著特征的“車臉”區域進行定位．用隨機蕨思想將車輛匹配問題轉化為分類問題,將運算量大的部分轉移到分類器訓練過程中．同時結合車輛圖片的特征,引入多尺度的概念,提出了一種快速多尺度特征點檢測算法．離線訓練階段,產生大量的虛擬圖對分類器進行訓練,在線運行階段檢測特征點并將這些特征點所在的區域塊放到分類器中進行快速分類,產生初始匹配．對誤匹配的特征點進行精確匹配時,分析了RANSAC策略的不足,應用改進的PROSAC對隨機蕨匹配算法獲取的匹配對進行精確匹配．

表4 本文算法與SIFT算法對比結果Tab.4 Comparison between SIFT and the algorithm of this paper

實驗結果表明,基于隨機蕨的車輛匹配能夠快速實時地進行匹配,同時能夠很好地應對車輛尺度變化、角度變化、亮度變化、遮擋、鏡頭畸變以及復雜的交通環境等挑戰．

本文旨在實現車輛的實時匹配,結合車輛區域定位與車牌定位來實現“車臉”定位,同時引入隨機蕨的思想將車輛匹配問題轉化為特征點所在區域的分類問題,雖然能夠對車輛進行實時匹配,但仍然存在著一些不足和需要改進的地方,需要進一步的完善和提高:

1) 本文的隨機蕨分類器是建立在“車臉”特征點之上的,提取的“車臉”區域的準確性,將直接影響著后面的匹配效果．因此如何快速準確的提取“車臉”區域,還需要進一步的研究．

2) 離線訓練階段需要生產大量的虛擬圖像進行穩定特征點查找和分類器的建立,因此需要大量的計算．然而由于虛擬圖像之間、隨機蕨之間的相互獨立,可以利用多核編程來降低離線訓練時間,提高運算效率．

3) 本文的車輛匹配不能很好地處理同品牌同型號的車輛．當兩輛車是同一品牌同一型號時,單靠本文匹配方法不能很好地進行區分,需要車牌識別進行輔助．

4) 匹配依賴于分類器的分類結果,缺少誤匹配去除機制,在誤匹配很多時,可能會產生匹配失敗的情形．因此如何快速有效地去除誤匹配將是今后研究工作的重點．

[1] Lowe D G.Object recognition from local scale-invariant features[C]∥Computer Vision,1999.The Proceedings of the Seventh IEEE International Conference on.Kerkyra：IEEE，1999：1150-1157.

[2] Ke Y，Sukthankar R.PCA-SIFT:a more distinctive representation for local image descriptors[C]∥Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition.Washington：IEEE，2004：511-517.

[3] Bay H，Tuytelaars T，Gool L V.SURF:speeded up robust features[C]∥Computer Vision-ECCV 2006.Berlin：Springer-Verlag，2006：404-417.

[4] Morel J M，Yu G S.ASIFT:a new framework for fully affine invariant image comparison[J].Society for Industrial and Applied Mathematics Journal on Image Sciences，2009，2(2)：438-469.

[5] Lepetit V，Fua P.Keypoint recognition using randomized tree[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(9)：1465-1479.

[6] Ozuysal M，Calonder M，Lepeti V.Fast keypoint recognition using random ferns [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(3)：448-461.

[7] Zheng D N，Zhao Y N，Wang J X.An efficient method of license plate location[J].Pattern Recognition Letters，2005，26(15)：2431-2438.

[8] Parisi R，Di Claudio E D，Lucarelli G，et al.Car plate recognition by neural networks and image processing[C]∥Proceedings of the 1998 IEEE International Symposium on Circuits and Systems.Monterey,CA：IEEE，1998：195-198.

[9] Chum O，Matas J.Matching with PROSAC-progressive sample consensus[C]∥Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Diego,CA：IEEE,2005：220-226.