基于模糊匹配的多級車牌匹配技術

摘 要： 在當前技術中，車牌之間的匹配一般采用的是精確匹配，其不足以滿足旅行時間、OD調查等研究的需要。針對此問題，設計了一種基于模糊匹配的多級車牌匹配技術。該方法通過限定車牌經過上下游交叉路口的時間間隔、計算車牌之間的編輯距離進行車牌的模糊匹配，將匹配成功的車牌的旅行時間用四分位數法進行異常數據的剔除，并通過北京市某路段的實測數據進行驗證。實驗發現多級車牌匹配技術可以很好地提高車牌的匹配率，從而為基于車牌的其他研究提供更有效、可靠的數據。

關鍵詞： 車牌匹配； 模糊匹配； 編輯距離； 閾值

中圖分類號： TN911.73?34； TP301.6 文獻標識碼： A 文章編號： 1004?373X（2015）07?0135?04

0 引 言

隨著智能交通技術的發展，城市交通管理系統和公路交通管理系統的自動化、智能化水平在不斷提高，視頻監控設備、電子拍照設備、移動監測設備被廣泛地布設在路網中的觀測站、收費站及重要路口，通過車牌自動識別技術可以從這些設備獲取圖片、視頻中提取車牌信息。當前，我國城市路網和國道、省道等公路網每天都在獲取超過百萬計的車輛檢測信息，包括車牌號、車輛通過路口的時刻、路口ID等。然而這些信息卻沒有得到足夠的重視和高效的利用，當前的車牌利用停留在車速測量、不停車收費、交通違章的初級階段，未能從網絡化、全局化、軌跡化的角度來分析利用車牌數據，造成了車牌資源的很大浪費。

近年來，ITS技術的發展使牌照自動識別技術更加完善，車牌捕獲率和識別率有了顯著提高，車牌號作為全世界惟一對車輛身份進行識別的標識，它的特殊性和重要性決定了車牌識別系統成為城市智能交通管理系統中不可或缺的重要組成部分。通過對比同一輛車經過上下游路口車牌被識別到的時刻，可以對一輛車連續通過兩個路口的旅行時間進行計算[1]，可以分析該路段的交通狀態[2?3]、延誤、路段服務水平等交通分析評價指標，還可以分析車輛的出行軌跡[4]等，而這些分析的前提是要對得到的車牌號進行匹配、處理。

現在的車牌識別系統雖然有了很大的發展，但是由于車牌的污損、模糊、遮擋、天氣等原因，識別車牌的準確率達到100%是不可能的。如果車牌沒有被正確讀取，精確的車牌匹配會損失掉這部分數據，影響后續工作的完成，因此選用合適的方法對車牌進行匹配顯得尤為重要。

本文設計的車牌匹配方法采用多級匹配策略：一級匹配，限定車牌經過上下游交叉路口的時間間隔；二級匹配，車牌模糊匹配、設定閾值，增加匹配成功率；三級匹配，異常數據剔除。通過北京市某路段的實測數據進行驗證。圖1為車牌多級匹配流程框架圖。

圖1 多級匹配流程框架圖

1 限定時間間隔

車牌數據為車輛通過停車線后檢測區域時識別得到，車輛通過每個路口時，其車牌將被識別并存儲。車輛正常行駛，經過上下游路口的間隔時間是在一定范圍內的，如果間隔時間過大，則不能進行有效地車牌匹配數據。原因在于：上下游交叉口獲取的相同車牌數據可能來源于車輛的二次出行，甚至是多次出行。在限定的時間間隔內進行車牌匹配，可以有效地減少這種情況的發生。對于交通量大的路口，每天都有海量的車牌數據，在匹配之前限定范圍，可以大大減少車牌匹配的工作量，加快匹配速度。車牌識別系統中可能出現如“京A12345”、“京A12845”，這種情況有可能源于車牌系統識別錯誤，將3識別為8，也有可能本身就是兩個不同的車牌，限定時間間隔可以減少這種情況出現的匹配誤差。限定車牌經過上下游交叉路口的時間間隔可以很好地提高基礎數據的質量。

假定當前路口有一要匹配的車牌[A，]在下游路口選取10 min（可以根據上下游路口的路段長度及交通狀況等進行調整）內的車牌數據進行匹配，這樣減少了匹配的工作量，同時提高了匹配的準確率。

2 模糊匹配算法

現階段的車牌匹配大多采用精確匹配，車牌的精確匹配是指查找的車牌與搜索到的車牌完全相同，是最理想的匹配方式。但是，這種方法匹配要求嚴格，存在一些弊端，當車牌識別錯誤時，無法返回匹配結果，不能滿足研究的需要，故需要尋找一種匹配率較高的方法。

車牌其實就是一串字符串，可以通過研究各種字符串的匹配算法實現車牌的匹配。字符串匹配[5]可以分為精確匹配和模糊匹配。本文的車牌匹配采用后一種，即模糊匹配[6]。

2.1 編輯距離的定義

本文擬采用“編輯距離”[7?8]的概念實現模糊字符串的匹配。通俗地講，編輯距離算法是指兩個字符串之間，由一個字符串通過一些編輯操作可以變換成另外一個字符串所需要的最少編輯次數。這里的編輯操作包括從字符串中刪除、插入、更改一個字符，稱為一個編輯距離，它能夠體現兩個字符串的差異。

起始的編輯距離是0，然后操作一次編輯距離就加1，直到這個字符串已經完全變成另外一個字符串。操作的次數越多，那么編輯距離就越大，最少操作次數代表了最精確的操作，也就是變換過程中的最優解。

例如將kid變換成king，可以按照這樣的步驟轉變：

（1） 將kid中的第三個字符d變成n（kid→kin）；

（2） 在kin的后面添加g（kin→king）。

經過了2次編輯操作，那么kid到king的編輯距離為2。

通過計算編輯距離，可以得出最佳匹配。

2.2 算法實現

車牌字符串具有如下的特點：

（1） 汽車牌照的位數固定，一般為7位，最多的如武警車牌（WJ01?12345）等極少數為9位。

（2） 對汽車牌照進行模糊匹配時與字符串有所不同，字符的匹配順序不能顛倒。

基于車牌的特性，車牌匹配的編輯操作不能有刪除、插入，只考慮從字符串中將一個字符改為另一個字符的操作。

假設現在已求得A的前[i-1]個字符編輯成B的前[i-1]個字符的最短編輯距離，此時如果A、B的第i個字符相同，顯然無需任何字符操作就可以在原來的基礎上得到A、B的前i個字符相同，此時的編輯距離就是[Di=Di-1]；如果A、B的第i個字符不相同，則可以通過更改A的第i個字符為B的第i個字符，此時也可以在原來的基礎上使得A、B的第i個字符相同，由于只做了一個修改操作，因此[Di=Di-1+1。]

綜上所述[D（i）]的遞推公式如下：

[D（i）=0，i=0MIND（i-1），D（i-1）+1，A（i）=B（i）A（i）≠B（i）] （1）

假定待匹配的車牌號是[A，]它是一串字符串設為[A{a1，a2，…，ai，…，am}]（[7≤m≤9]），在數據庫中等待要匹配的車牌號有n個，放在集合[S{B1，B2，…，Bj，…，Bn}][（0

算法的思想是將待匹配的車牌號[A]的第一個字符與數據庫中的[Bj]的第一個字符進行匹配，若相等，則[D（1）=0；]若不相等，則[D（1）=1。]繼續比較A的第二個字符和[Bj]的第二個字符；依次比較下去，直到字符串匹配完成，得到A和[Bj]的編輯距離[D（j）。]車牌數據庫中有n個待匹配的車牌，需要依次求出A與這n個車牌的編輯距離，編輯距離越小，其匹配度越高，要想得到一個與A匹配度最高的車牌，需要取A和[Bj]的編輯距離的最小值，即[D（A，Bj）=min{D（j）}。]

用C#代碼來實現A和某一[Bj]的編輯距離，如下：

private int Levenshtein_Distance（string A， string Bj）

{

int n；

int j = 1；

int[] D；

for （j = 1； j <= n； j++）

{

int m；

int temp = 0；

char ch1；

char ch2；

int i = 1；

D = new int[m + 1]；

D[i] = 0；

for （i = 1； i <= m； i++）

{

ch1 = A[i - 1]；

ch2 = Bj [i - 1]；

if （ch1.Equals（ch2））

{

temp = 0； //字符相同

}

else

{

temp = 1； //字符不同

}

D[i] = D[i - 1] + temp；

}

D[j]=D[i]；

return D[j]；

}

}

2.3 匹配方案

如何從海量的數據庫中搜索出需要匹配的車牌。解決這個問題之前，必須首先解決串的相似性如何定義。俄國的Vladimir Levenshtein在1965年就提出了用編輯距離[5]的概念來描述兩個字符串的相似程度，因此編輯距離又稱Levenshtein距離。編輯距離越小，其相似程度越高。編輯距離越大，其相似程度就越低。假設字符串的最大長度為L，編輯距離為[D（A，Bj），]相似度為S，那么：

[S=1-[D（A，Bj）]L] （2）

在當前技術下，車牌識別系統的識別率達不到100%，在車牌識別中可能將車牌“京CE0192”識別為 “京CEQ792”，這實際為同一車牌，為了提高匹配的效率，設定其相似度在一定的范圍。將閾值設為0.6，即[S>0.6]時，兩個車牌之間是匹配的。其中[S=1]時，[A]到[Bj]的操作次數是0，也就是完全匹配。

在交通流量比較大的路口，車牌數據比較多，每一次匹配都是海量數據，車牌匹配速度的快慢影響其設計系統的效率。車牌具有一些其他字符串沒有的特性，“京B12345”和“京C83345”在第4個字符時編輯距離為3，相似度已經超過了設定的閾值0.6，為了提高速度，這兩個車牌沒有必要匹配下去，可以大大的提高其效率。

3 異常數據剔除

經過上述方法匹配之后的車牌，依然會出現異常數據，這些異常數據可以用行程時間來進行剔除。出現異常行程時間數據主要有以下因素：系統誤差，由于采集車牌裝置出現誤差；異常交通行為，車輛在道路上偶然停車、車輛從道路上離開正常行駛軌跡等。一些異常的交通行為對交通流量產生震蕩，從而導致行程時間突變。這些數據都會顯著影響對路段旅行時間的估計，需要應用一定的篩選算法將其從數據中剔除，以便提高輸出數據的質量。

四分位數法[9]（Quartile）是統計學的一種分析方法，用于描述任何類型的數據，尤其是偏態數據的離散程度。簡單地說，就是將全部數據從小到大排列并分成4等分，處于三個分割點位置的數值就是四分位數，使用四分位數間距來反映變異程度的大小。其中，四分位數間距指的是：上四分位數與下四分位數之差。相關文獻給出了一種基于四分位數法的異常數據的處理方法：凡是超出此區間范圍之外的數據，都被認為是異常數據需要剔除：

[Z=[Q0.25-1.5R，Q0.75+1.5R]] （3）

[R=Q0.75-Q0.25] （4）

式中：[Z]表示有效數據區間；[Q0.25]表示位于[14]位置的數值，叫做下四分位值；[Q0.75]表示位于[34]位置的數值，稱為上四分位值；[R]表示四分位極差。

四分位數法的計算比較簡便，計算速度較快，圖2為四分位數法處理前后的效果。由圖2可以看出，通過四分位數法可以較好地處理掉旅行時間過大或過小的異常數據，為后續的統計分析等提供高質量的基礎數據。

4 實例分析

利用北京市利澤東二路口北向南和利澤東街口北向南的實測車牌識別數據進行三級匹配策略的實例分析，路口情況如圖3所示。

圖2 四分位數法處理前后的效果對比

圖3 測試路口圖

利用文中設計的匹配算法，對2014年2月6日24小時內經過兩個路口的車牌進行匹配。經人工匹配成功的有110對，經多級匹配之后成功的有106對，精確匹配的只有88對。

設定該路段的時間間隔為10 min，車輛京K06276在09：22：55經過利澤東二路口，在18：49：55經過利澤東街口，間隔時間大于設定的路段時間間隔，該算法可以很好地避免這種情況下的錯誤匹配。

按照設定的相似度閾值，匹配結果（去除精確匹配部分）如表1所示，為了對比實驗結果，人工做了車牌的匹配，匹配結果（去除精確匹配部分）如表2所示。

實驗結果表明，精確匹配的匹配率為80%，如果只通過精確匹配，則會遺漏掉表2中的數據。多級匹配的匹配率為96.36%，比人工實際的匹配結果少了4對，這4對車牌的相似度依次為0.43，0.43，0.29，0.57，超過設定的閾值，僅占整個匹配車牌的3.64%，說明設定的相似度閾值0.6是合理的。相似度閾值設置過小，會導致一些車牌不能匹配，達不到理想的匹配率。閾值設置過大，會導致匹配的錯誤率提高，速度降低。

表1 車牌模糊匹配結果

[利澤東二路口＼車輛經過時刻＼利澤東街口＼車輛經過時刻＼京ET8140＼2/6/2014 08：37：28＼京E1H140＼2/6/2014 08：37：47＼遼H2117F＼2/6/2014 08：39：50＼京H2117F＼2/6/2014 08：40：12＼津MZH569＼2/6/2014 09：01：28＼京MZH569＼2/6/2014 09：01：54＼京N9MC11＼2/6/2014 09：10：27＼京A9MC11＼2/6/2014 09：11：17＼京BN1113＼2/6/2014 09：16：59＼京HN1113＼2/6/2014 09：17：18＼遼LX9762＼2/6/2014 09：49：44＼京LX9762＼2/6/2014 09：50：59＼京BM4656＼2/6/2014 10：33：07＼京HM4656＼2/6/2014 10：34：07＼津GWM500＼2/6/2014 11：07：29＼京GWM500＼2/6/2014 11：07：51＼京BR9045＼2/6/2014 11：27：57＼京HR9045＼2/6/2014 11：28：14＼京Q9T097＼2/6/2014 13：04：25＼京Q91U97＼2/6/2014 13：05：20＼京QJ7686＼2/6/2014 14：43：25＼京QJ16H6＼2/6/2014 14：43：49＼京BQ2297＼2/6/2014 15：35：02＼京HQ2297＼2/6/2014 15：35：22＼京L81235＼2/6/2014 16：41：24＼京LH1235＼2/6/2014 16：42：28＼津QU2856＼2/6/2014 17：37：11＼京QU2856＼2/6/2014 17：37：46＼京KD6276＼2/6/2014 18：49：32＼京K06276＼2/6/2014 18：49：55＼京BN0848＼2/6/2014 22：16：51＼京HN084H＼2/6/2014 22：17：17＼]

表2 人工匹配結果

[利澤東二路口＼車輛經過時刻＼利澤東街口＼車輛經過時刻＼京ET8140＼2/6/2014 08：37：28＼京E1H140＼2/6/2014 08：37：47＼＼遼H2117F＼2/6/2014 08：39：50＼京H2117F＼2/6/2014 08：40：12＼＼津MZH569＼2/6/2014 09：01：28＼京MZH569＼2/6/2014 09：01：54＼＼京N9MC11＼2/6/2014 09：10：27＼京A9MC11＼2/6/2014 09：11：17＼＼京BN1113＼2/6/2014 09：16：59＼京HN1113＼2/6/2014 09：17：18＼＼遼LX9762＼2/6/2014 09：49：44＼京LX9762＼2/6/2014 09：50：59＼＼京BM4656＼2/6/2014 10：33：07＼京HM4656＼2/6/2014 10：34：07＼＼津GWM500＼2/6/2014 11：07：29＼京GWM500＼2/6/2014 11：07：51＼＼京BR9045＼2/6/2014 11：27：57＼京HR9045＼2/6/2014 11：28：14＼＼京Q9T097＼2/6/2014 13：04：25＼京Q91U97＼2/6/2014 13：05：20＼＼京L33798＼2/6/2014 14：42：07＼京K66708＼2/6/2014 14：42：25＼＼京QJ7686＼2/6/2014 14：43：25＼京QJ16H6＼2/6/2014 14：43：49＼＼京BQ2297＼2/6/2014 15：35：02＼京HQ2297＼2/6/2014 15：35：22＼＼京GLF198＼2/6/2014 15：55：19＼京F19898＼2/6/2014 15：56：22＼＼京L81235＼2/6/2014 16：41：24＼京LH1235＼2/6/2014 16：42：28＼＼京KL1110＼2/6/2014 17：29：18＼京1TT1T1＼2/6/2014 17：29：38＼＼津QU2856＼2/6/2014 17：37：11＼京QU2856＼2/6/2014 17：37：46＼＼京KD6276＼2/6/2014 18：49：32＼京K06276＼2/6/2014 18：49：55＼＼京BN0848＼2/6/2014 22：16：51＼京HN084H＼2/6/2014 22：17：17＼＼京1QAP18＼2/6/2014 22：19：39＼京NQC518＼2/6/2014 22：20：03＼＼＼＼＼＼＼]

圖4 各種匹配的匹配率對比圖

5 結 語

與其他交通信息采集技術相比較，基于車牌識別數據的交通信息采集技術具有工作連續性強、數據精確度高、檢測樣本量大等優點。車牌模糊匹配在運用車牌預測行程時間、判別交通狀態等方面有著至關重要的作用，是交通信息采集技術相關研究的基礎，本文通過多級匹配策略，給出了一種比較簡單快速的車牌模糊匹配算法，并進行了驗證。車牌多級匹配技術，可以提高車牌的利用率，實現車牌的自動化校核。

參考文獻

[1] DION Francois， RAKHA Hesham. Estimating dynamic roadway travel times using automatic vehicle identification data for low sampling rates [J]. Transportation Research Part B， 2006（40）： 745?746.

[2] 姜桂艷，常安德，牛世峰.基于車牌識別數據的交通擁堵識別方法[J].哈爾濱工業大學學報，2011，43（4）：131?135.

[3] 高林，劉新，尹紀軍，等.基于車牌識別數據的交通狀態判別方法研究[C]//第八屆中國智能交通年會優秀論文集.北京：中國智能交通協會，2013：270?279.

[4] 林瑜，陳紅潔，肖永來.基于車牌識別的交通分析應用研究[J].中國交通信息產業，2009（5）：101?104.

[5] 何畏.快速精確字符串匹配算法研究[D].合肥：合肥工業大學，2010.

[6] 姚心宇.中文地址識別系統中的地址表達與匹配[D].上海：華東師范大學，2012.

[7] LEVENSHTEIN V I. Binary codes capable of correcting deletions， insertions and reversals [J]. Soviet Physics?Doklady， 1966， 10（8）： 707?710.

[8] 趙作鵬，尹志民，王潛平，等.一種改進的編輯距離算法及其在數據處理中的應用[J].計算機應用，2009，29（2）：424?426.

[9] 柴華駿，李瑞敏，郭敏.基于車牌識別數據的城市道路旅行時間分布規律及估計方法研究[J].交通運輸系統工程與信息，2012，12（6）：41?47.

[10] NAVARRO G. A guided tour to approximate string matching [J]. ACM Computing Surveys ?CSUR， 2001， 33（1）： 31?88.