胡 霖

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

(3)

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

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

m=1,…,k.

(4)

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

1.2 核函數(shù)

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

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

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

(5)

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

(1)線性核:

(6)

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

(2)多項(xiàng)式核:

(7)

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

(3)Sigmoid核:

(8)

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

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

(9)

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

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

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

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

(10)

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

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

2 特征提取

2.1 數(shù)據(jù)來(lái)源

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

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

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

對(duì)上述字符‘O’的直線拼接即是從第一行開始,每一行鏈接到前一行最后一個(gè)元素而構(gòu)成一維矢量。這樣處理的一維矢量雖然很長(zhǎng),但因?yàn)楹撕瘮?shù)的選取并沒(méi)有帶來(lái)計(jì)算的增加,而且避免了復(fù)雜處理過(guò)程中字符矩陣的復(fù)雜處理和特征損失。

圖3 無(wú)干擾情況下字符‘O’的9*9存儲(chǔ)矩陣

3 試驗(yàn)與分析

3.1 試驗(yàn)過(guò)程

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

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

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

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

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

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

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

3.2 試驗(yàn)分析

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

表3 與其他算法對(duì)比情況

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

4 結(jié)束語(yǔ)

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