基于混合核的超球面支持向量機(jī)車牌字符識別

胡 霖

(中國石油大學(xué)勝利學(xué)院 教學(xué)科研處,山東 東營 257000)

車牌字符識別算法直接影響車牌識別的效果,目前最常用的方法有以下3種:模板匹配、人工神經(jīng)網(wǎng)絡(luò)以及支持向量機(jī)[1]。其中,支持向量機(jī)方法因可以有效避免局部極值問題得到更廣泛應(yīng)用。對支持向量機(jī)在實際應(yīng)用中的研究,主要采用以下兩種方法:一是與另外的分類算法相組合;二是優(yōu)化核函數(shù)提高其自身性能。但當(dāng)把經(jīng)典支持向量機(jī)推廣到多分類領(lǐng)域時[2-3],計算復(fù)雜程度均較高。Tax[4]等人首次采用球體形式來包含樣本數(shù)據(jù)。朱美琳[5]等人研究將這種球體形式加入支持向量機(jī),改進(jìn)其分類策略。施隆照[6]等人提出一種組合支持向量機(jī)方案,算法采用一類超球面和標(biāo)準(zhǔn)SVM進(jìn)行車牌字符識別,過程較繁瑣,且默認(rèn)采用徑向基核作為核函數(shù),沒有深入論證分類正確率與核函數(shù)選擇關(guān)系問題。在車牌字符識別應(yīng)用中,超球面支持向量機(jī)雖然能夠獲得比傳統(tǒng)支持向量機(jī)更好的分類效果,但對其核函數(shù)的選取仍然沒有成熟方案。針對以上不足,本文提出一種超球面混合核支持向量機(jī)(MHS-SVM),在分析了超球支持向量機(jī)分類計算方法和各種核函數(shù)的基礎(chǔ)上,采用多項式核函數(shù)與徑向基核函數(shù)兩者的線性組合構(gòu)建混合核函數(shù)進(jìn)行優(yōu)化。該算法首先對選取的車牌字符圖片進(jìn)行特征提取,然后分別將單一徑向基核函數(shù)和混合核函數(shù)應(yīng)用到超球面支持向量機(jī)決策函數(shù)中,找到徑向基核函數(shù)參數(shù)和線性組合交叉概率的最優(yōu)取值。通過對加州理工學(xué)院Computational Vision研究小組Cars 1999 (Rear) 2數(shù)據(jù)集[7]進(jìn)行測試,最后將本文算法結(jié)果與已有方案進(jìn)行比對,算法在車牌字符識別上提高了識別正確率,同時保持了較高的識別速率。

1 超球面+核函數(shù)

1.1 超球面支持向量機(jī)

超球面支持向量機(jī)目前得到了越來越廣泛的關(guān)注,相比于傳統(tǒng)支持向量機(jī),它力求找到一個半徑最小的超球面來分類數(shù)據(jù),而不是為待分類樣本尋找超平面[8]。該方法將數(shù)據(jù)映射到Hilbert空間,可通過改進(jìn)的多類分類策略獲得比傳統(tǒng)支持向量機(jī)更好的學(xué)習(xí)能力和分類效果。

超球面支持向量機(jī)將同質(zhì)數(shù)據(jù)盡量用半徑最小的超球面來包含,數(shù)據(jù)空間被分割成了幾個超球,類似在立體空間中的一個個肥皂泡。圖1以三超球重疊來示意樣本分布。構(gòu)造出的每一個超球?qū)?yīng)一類樣本數(shù)據(jù),采用這種方案可以使算法的復(fù)雜性降低,明顯減少二次規(guī)劃難度從而使大樣本處理成為可能。另外,如果針對新來的樣本需要新增類別,只需添加一個該類別的新超球,大大提高了可擴(kuò)展性。

圖1 樣本分布在重疊三超球中的情況

假定現(xiàn)在使用超球面支持向量機(jī)對樣本進(jìn)行k類劃分:k個元素集維度設(shè)為n,對于每個集合用Vm表示,找出一個最小超球面,vm是最小超球面的球心,Rm是最小超球面的半徑,使得最小的超球面包含所有采樣點xim。目標(biāo)函數(shù)為

(1)

利用Lagrange優(yōu)化方法轉(zhuǎn)化為對偶問題:

(2)

目標(biāo)是拉格朗日乘數(shù)。將公式(2)中的內(nèi)積運算用核函數(shù)代替,推導(dǎo)出用于特征空間中分類超球的二次規(guī)劃公式:

為驗證本文提出的空間圓弧擬合優(yōu)化方法的準(zhǔn)確性，對圖2中的數(shù)據(jù)點云，用基于拉格朗日乘子法的空間圓弧擬合方法進(jìn)行擬合。分別進(jìn)行2組各5次擬合實驗，其中一組應(yīng)用了RANSAN算法剔除錯誤點，擬合結(jié)果如表3所示，分析結(jié)果如圖4所示。同時，將本文優(yōu)化方法與傳統(tǒng)空間圓弧擬合方法進(jìn)行比較，擬合結(jié)果如表4所示，分析結(jié)果如圖5所示。

(3)

決策函數(shù)力求找到樣本點x到球心的最小距離,具體函數(shù)如下:

fm(x)=[K(x,x)-2K(x,am)+K(am,am)]-(Rm)2,

m=1,…,k.

(4)

通過將準(zhǔn)備好的車牌字符集代入公式(4)中訓(xùn)練,可以標(biāo)識出各類超球的相對位置。在實際應(yīng)用中,用決策函數(shù)求出新樣本點與各類超球的距離,距離最小的超球所代表的類型即是該樣本點的類型。核函數(shù)的選取會直接影響最終的分類效果。接下來將詳細(xì)論證混合核函數(shù)的構(gòu)造過程。

1.2 核函數(shù)

傳統(tǒng)支持向量機(jī)處理的是線性樣本數(shù)據(jù),但數(shù)據(jù)往往并不是理想化的,對非線性狀態(tài)的數(shù)據(jù)的識別和分類是有必要的。核函數(shù)可以將低維的非線形狀態(tài)的數(shù)據(jù)轉(zhuǎn)映為高維,克服低維空間的不利因素,從而成功地構(gòu)筑出超平面。內(nèi)核函數(shù)的選擇會對支持向量機(jī)的執(zhí)行效果產(chǎn)生很大的影響。

核函數(shù)計算如公式(5)所示:

K(X,Z)=〈ω(X)·ω(Z)〉.

(5)

線性核、多項式核、Sigmoid核以及徑向基核是核函數(shù)的4種主要類型[9]。

(1)線性核:

(6)

公式(6)表示線性核計算內(nèi)積來對數(shù)據(jù)進(jìn)行處理。經(jīng)過這種處理可以把原始區(qū)域和映射后區(qū)域的數(shù)據(jù)進(jìn)行整合。

(2)多項式核:

(7)

公式(7)計算多項式空間內(nèi)積,注重整體的數(shù)據(jù)。為了降低計算復(fù)雜度,往往需要將多項式中高維的計算轉(zhuǎn)換成低維。

(3)Sigmoid核:

(8)

公式(8)核函數(shù)關(guān)注全面最優(yōu)樣本數(shù)據(jù)。

(4)Gauss徑向基核(RBF):

(9)

公式(9)性能受參數(shù)選擇和局部擾動,映射維度可以任意。特征空間參數(shù)越小映射維度越低,參數(shù)越大擬合度越嚴(yán)重。自由度高和可控性強(qiáng)使得徑向基核在實際應(yīng)用中被廣泛采用。設(shè)置較小的參數(shù)可以有效地提高分類的能力,但同時泛化能力會降低。

RBF學(xué)習(xí)性能較強(qiáng),但泛化不足,而多項式核泛化性能較強(qiáng),將兩者結(jié)合起來構(gòu)成混合核,可進(jìn)一步提高超球面支持向量機(jī)分類性能。

對混合核創(chuàng)建一個矩陣M=mij,選擇多項式核和RBF進(jìn)行線性的組合[10],矩陣單個元素表達(dá)式為

mij=mmulti(xi,xj)=ampoly(xi,xj)+(1-a)mRBF.

(10)

式中,a為權(quán)值,a∈(0,1)。

通過式(10)替換式(4)中的核函數(shù)部分,將上述MHS-SVM算法應(yīng)用到車牌字符識別中,對徑向基核函數(shù)的參數(shù)以及線性組合權(quán)值選取不同區(qū)間的值,確定不同參數(shù)對識別結(jié)果的影響,抉擇出最終解。

2 特征提取

2.1 數(shù)據(jù)來源

車牌圖片數(shù)據(jù)均取自加州理工學(xué)院Computational Vision研究小組Cars 1999 (Rear) 2數(shù)據(jù)集,樣例圖片如圖2所示。數(shù)據(jù)集中包括126張汽車車牌圖片,每張圖片采用896×592的jpg格式,每個車牌包含7個字符。將汽車車牌圖片隨機(jī)排序后分成X、Y、Z三個圖片數(shù)量相同的樣本集,首先訓(xùn)練Y、Z,用X來測試結(jié)果;第二次訓(xùn)練X、Z,用Y來測試結(jié)果;最后選取X、Y作為訓(xùn)練樣本,Z作為測試樣本;三次試驗得到識別率的平均值作為試驗的最終結(jié)果。

圖2 Cars 1999 (Rear) 2數(shù)據(jù)集樣例

歸一化采取簡單處理。將牌照字符圖像存儲到計算機(jī)中采用的是矩陣形式,字符‘O’存儲的矩陣(以9*9為例)如圖3所示。要方便支持向量機(jī)利用其進(jìn)行訓(xùn)練和試驗,有必要將它們降維轉(zhuǎn)換成一維形式,為保證識別的準(zhǔn)確性,計算的簡單性和硬件的易于實現(xiàn)特性,將字符矩陣轉(zhuǎn)換為一維矢量,根據(jù)直線拼接提取特征。

對上述字符‘O’的直線拼接即是從第一行開始,每一行鏈接到前一行最后一個元素而構(gòu)成一維矢量。這樣處理的一維矢量雖然很長,但因為核函數(shù)的選取并沒有帶來計算的增加,而且避免了復(fù)雜處理過程中字符矩陣的復(fù)雜處理和特征損失。

圖3 無干擾情況下字符‘O’的9*9存儲矩陣

3 試驗與分析

3.1 試驗過程

首先對訓(xùn)練樣本集中的字符進(jìn)行分割和特征提取轉(zhuǎn)換為一維矢量。第一步將公式(10)的權(quán)值a設(shè)置為0,僅用RBF作為核函數(shù),測試結(jié)果如表1所示。表中X|YZ表示的是將Y、Z作為訓(xùn)練集,X作為測試集,其他類似。從測試數(shù)據(jù)可以看出,選定γ=1.8,徑向基核支持向量機(jī)具有最優(yōu)的識別正確率。

第二步,在γ值確定的情況下,當(dāng)權(quán)值a分別取不同值時,測試結(jié)果表明,引入混合核以后的算法在識別正確率上有所提升(表2)。

表1 純徑向基核測試數(shù)據(jù)

表2 線性組合不同權(quán)值下測試數(shù)據(jù)

由上述試驗數(shù)據(jù)得出參數(shù)γ與a對算法識別正確率影響曲線如圖4,5所示。

圖4 純徑向基核超球平均識別正確率

圖5 混合核超球平均正確率

3.2 試驗分析

通過3.1中試驗步驟,針對測試數(shù)據(jù)集最終將徑向基核參數(shù)調(diào)為1.8,權(quán)值為0.35獲取最優(yōu)識別正確率。表3中列出本文測試結(jié)果與其他算法的對比情況。

表3 與其他算法對比情況

可以看出,本文提出的MHS-SVM算法較文獻(xiàn)[6]和[11]識別正確率有所提高。由于引入了多項式核函數(shù)計算量增多,識別時間較文獻(xiàn)[6]稍有增加,但比文獻(xiàn)[11]已有較大改進(jìn)。

4 結(jié)束語

針對支持向量機(jī)在車牌字符識別中應(yīng)用存在的問題,利用基于混合核的超球面支持向量機(jī)進(jìn)行改進(jìn)。新算法識別速率快,使用多項式核與徑向基核線性組合方式,并在此基礎(chǔ)上試驗決出針對車牌字符識別的最優(yōu)核參數(shù)與線性組合權(quán)值,進(jìn)一步提高了識別正確率。下一步研究方向?qū)L試其他核函數(shù)組合方案,并結(jié)合結(jié)構(gòu)化學(xué)習(xí)對核參數(shù)進(jìn)行深度優(yōu)化。