摘 要：為了更好地反映自然界的優(yōu)勝劣汰，提出改進(jìn)的遺傳算法。在改進(jìn)的交叉與變異運(yùn)算中引入個(gè)體的適應(yīng)度。把改進(jìn)的遺傳算法應(yīng)用于車牌圖像分割中，并根據(jù)車牌中字符分布的特點(diǎn)，利用車牌內(nèi)部灰度值的變化頻率實(shí)現(xiàn)車牌定位。實(shí)驗(yàn)結(jié)果表明該算法不僅可以獲得較好的車牌分割效果，而且能提高車牌定位的速度。

關(guān)鍵詞：遺傳算法；車牌定位；圖像分割；個(gè)體適應(yīng)度

中圖分類號(hào)：TP391.4 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1004-373X(2008)10-155-02

Application of Improved Genetic Algorithm in License Plate Location

CHEN Mei

(School of Electrical Information and Automation Engineering，Qufu Normal Unversity，Rizhao，276826，China)



Abstract：The improved genetic algorithm is proposed in order to better reflect the survival of the fittest.In the new algorithm，the fitness is introduced in the operation of crossover and mutation.The improved genetic algorithm is applied to the image segmentation of license plate，according to the character distributing in the license plate，license plate localization is implemented by the gray change frequency location.Experiment results show the algorithm can not only get better effect of segmentation to the license plate，but also improve the speed of license plate location.

Keywords：genetic algrithm;license plate location;image segmentation;fitness

車牌識(shí)別技術(shù)是計(jì)算機(jī)視覺、圖像處理技術(shù)與模式識(shí)別技術(shù)的融合，其主要是采用計(jì)算機(jī)圖像處理技術(shù)對(duì)車牌的圖像進(jìn)行分析，自動(dòng)提取車牌信息，確定車牌號(hào)。一般，在車牌自動(dòng)識(shí)別系統(tǒng)中，處理的關(guān)鍵技術(shù)問題是車牌的定位及字符的識(shí)別。由于在識(shí)別時(shí)進(jìn)行字符特征提取和識(shí)別的對(duì)象都是在車牌區(qū)域內(nèi)，所以從自然背景中分割出車牌區(qū)域，并正確識(shí)別矩形區(qū)域內(nèi)字符是提高汽車自動(dòng)識(shí)別系統(tǒng)識(shí)別率的關(guān)鍵， 對(duì)此人們提出了許多方法，如運(yùn)用多層次分割對(duì)車牌進(jìn)行定位^[1]，運(yùn)用小波與形態(tài)學(xué)的車牌圖象分割方法^[2]，基于彩色和紋理分析的車牌定位方法^[3]等。圖像分割的最常用方法是閾值法，用改進(jìn)的遺傳算法可以較快地獲得車牌圖像的分割及定位。 

遺傳算法是一種通過模擬生物選擇和進(jìn)化過程搜索最優(yōu)解的方法^[4]。在實(shí)數(shù)編碼的遺傳算法中，交叉概率及變異概率一般為一個(gè)定值，缺少一定的自適應(yīng)性。為了使交叉與變異運(yùn)算更好地反映自然界的優(yōu)勝劣汰，本文提出改進(jìn)的遺傳算法，在其交叉與變異運(yùn)算中引入個(gè)體的適應(yīng)度，使適應(yīng)度較大的個(gè)體，參與交叉與變異的可能性較大。

1 改進(jìn)遺傳算法

遺傳算法是一種通過模擬自然界的進(jìn)化過程搜索最優(yōu)解的方法，其在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，并利用選擇、交叉和變異運(yùn)算對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。在圖像閾值分割算法中的關(guān)鍵問題是閾值的選取，利用遺傳算法的目的就是要得到最佳分割閾值。 改進(jìn)遺傳算法的具體實(shí)現(xiàn)步驟如下： 

(1) 圖像編碼：在圖像分閾值割中，傳統(tǒng)的編碼是將圖像閾值編碼成由0或1組成的有限長度的字符串。這種方式的編碼長度影響求解精度且不直觀，本文采用了具有直觀、易操作的實(shí)數(shù)直接編碼方式^[5]，即每個(gè)個(gè)體用一個(gè)n維的實(shí)向量來表示圖像的閾值。

(2) 初始種群的生成：隨機(jī)地產(chǎn)生n個(gè)個(gè)體組成的初始群體，該群體代表一些可能圖像閾值的集合。

(3) 選擇適應(yīng)度函數(shù)：遺傳算法對(duì)一個(gè)個(gè)體的好壞用適應(yīng)度函數(shù)值來評(píng)價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。將信息論中 Shannon 熵概念用于圖像分割時(shí)，測量圖像灰度直方圖的熵，以便求得最佳分割閾值。

對(duì)于灰度范圍{0，1，…，l-1}的直方圖，其熵測量表示為：

HT=－∑l－1i=0piln pi

其中，pi為第i個(gè)灰度出現(xiàn)的概率：pi=niW×H，其中W×H為圖像的大?。籲i為圖像中灰度值為i的像素的個(gè)數(shù)。

若閾值為t，則：pt=∑[DD(]t[]i=0[DD)]pi，Ht=－∑[DD(]t[]i=0[DD)]piln pi，與每個(gè)分布有關(guān)的熵分別為 HA(t)和 HB(t)：

[WB]HA(t)=－∑ti=0piplnpt－1pt=ln pt+Htpt

HB(t)=－ln(1－pt)+Htpt

熵判別的定義式為：

H(t)=HA(t)+HB(t)=ln pt(1－pt)+Htpt+HT－Ht1－pt

當(dāng)H(t)函數(shù)的值越大，圖像分割效果就越好，因此可將該函數(shù)作為遺傳算法中的適應(yīng)度函數(shù)。

(4)選擇:

選擇運(yùn)算主要實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作，適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率??；當(dāng)適應(yīng)度非常小時(shí)就會(huì)被淘汰。選擇算子采用輪盤賭選擇方法;

(5) 交叉:

交叉運(yùn)算是兩個(gè)父體根據(jù)交叉概率按某種方式相互交換其部分基因而產(chǎn)生一組新的個(gè)體。為了使適應(yīng)度較高的父體的特性遺傳到新個(gè)體較好中，這里采用改進(jìn)的交叉運(yùn)算，其表達(dá)式為：

XY=［P(x)×X+P(y)×Y］［P(x)+P(y)］，P(x)=H(x)[HT4]/∑ni=1H(i)

其中XY為新個(gè)體，X，Y分別為2個(gè)父體;P(x)，P(y)分別為2個(gè)父體的被遺傳到下一代的概論；H(x)為其適應(yīng)度。通過改進(jìn)的交叉運(yùn)算每兩個(gè)父體都可能會(huì)產(chǎn)生一個(gè)新的個(gè)體，由于把父體的適應(yīng)度考慮到表達(dá)式中，其能夠更好的反映生物界的優(yōu)勝劣汰的特點(diǎn)。

(6) 變異:

變異運(yùn)算是按一定的概率將個(gè)體編碼串中的某些基因值用其他基因值來替換，來形成一個(gè)新的個(gè)體。他決定了遺傳算法的局部搜索能力，同時(shí)保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索。

在實(shí)數(shù)編碼方式下，變異操作對(duì)個(gè)體X作用一個(gè)隨機(jī)偏差量，在進(jìn)化規(guī)劃和進(jìn)化策略^[6]中一般采用高斯變異算子，用正態(tài)分布的隨機(jī)變量作為變異操作中的偏差量。為了能較好地反映生物界的進(jìn)化，采用的是與適應(yīng)度有關(guān)的量來作為偏差量，即：

X′=X+M×P(x)

其中，M是隨迭代次數(shù)增加而逐漸減少的量，令M=C#8226;(C－N)，C表示一常量；N表示迭代次數(shù)。

(7) 遺傳算法的終止條件：

對(duì)新的一代，重新計(jì)算其適應(yīng)度，經(jīng)過新的選擇、交叉和變異后，循環(huán)操作，如圖1所示。使群體中最優(yōu)個(gè)體的適應(yīng)度不斷提高，若算法達(dá)到規(guī)定的迭代次數(shù)或經(jīng)過一定的迭代次數(shù)后群體的適應(yīng)度不在發(fā)生變化，此時(shí)算法停止，具有最高適應(yīng)度的個(gè)體即為分割閾值。

圖1 遺傳算法的流程圖

2 車牌圖像的分割

車牌定位是對(duì)采集到的圖像，能自動(dòng)確定車牌的位置。車牌的定位主要是車牌圖像的分割。車牌圖像分割的閾值通過改進(jìn)的遺傳算法獲得。設(shè)定種群數(shù)目為10， 最大迭代次數(shù)為30。用實(shí)數(shù)對(duì)圖像的閾值進(jìn)行編碼，經(jīng)過選擇、交叉及變異操作后，并計(jì)算適應(yīng)度，若經(jīng)過一定迭代次數(shù)后當(dāng)滿足算法終止的條件時(shí)，得到具有最高適應(yīng)度的個(gè)體便是車牌圖像分割的閾值。根據(jù)得到的閾值對(duì)車牌原始圖像（見圖2）進(jìn)行閾值分割，其表示為：

g(x，y)=Tif(g(x，y)≤T)

255if(g(x，y)>T) 

其中g(shù)(x，y)為各點(diǎn)灰度值，T為分割的閾值。分割圖像后的如圖3所示。

[XC<10t2.tif>]

圖2 原始圖像

[XC<10t3.tif>]

圖3 閾值分割后的圖像

3 車牌的定位

車牌圖像具有比較顯著特征：車牌為近似水平的矩形區(qū)域；矩形區(qū)域內(nèi)有連續(xù)按水平方向排列的字符，字符灰度與車牌底色灰度存在明顯的差別。由于車牌區(qū)字符分布較密集，每個(gè)字符有固定的寬度，且字符間有固定間距，所以在車牌處水平方向上灰度值的變化比車輛的其他非車牌區(qū)域的變化頻率要高。這樣就可利用灰度值的變化頻率，來對(duì)車牌進(jìn)行定位。車牌一般在車身上較低的位置，其下方基本上沒有明顯的邊緣密集區(qū)域，采用從下向上的處理方法，這樣不但可以減小運(yùn)算的速度，還可避免車身中其他文字的干擾。

圖4中的黑色線段為車牌區(qū)某一水平線上各點(diǎn)的灰度值分布情況。由灰度值的分布可知，車牌區(qū)的灰度值變化率較高，非車牌區(qū)的灰度值變化率較小，如圖5所示。在從下向上處理的過程中，灰度值變化率較高的區(qū)域可以作為車牌區(qū)。根據(jù)車牌的固定長寬比，便可較準(zhǔn)確地定位整個(gè)車牌區(qū)，如圖6所示。

圖4 車牌區(qū)的灰度值分布情況

圖5 非車牌區(qū)的灰度值分布情況

圖6 定位后的車牌

4 結(jié) 語

本文對(duì)改進(jìn)遺傳算法在車牌定位中的應(yīng)用進(jìn)行了研究和實(shí)驗(yàn)，通過對(duì)車牌圖像的分割及定位，表明通過該算法可以獲得較好的車牌分割效果，不僅提高了車牌定位的速度，同時(shí)結(jié)合車牌及車牌中字符的分布特點(diǎn)，提高了車牌識(shí)別的實(shí)時(shí)性。

參 考 文 獻(xiàn)

［1］苑瑋琦，傘曉鐘.一種汽車牌照多層次分割定位方法［J］.中國體視學(xué)與圖像分析，2004，9(4)：239-243.［2］戴青云，余英林.一種基于小波與形態(tài)學(xué)的車牌圖像分割方法［J］.中國圖像圖形學(xué)報(bào)，2000，5(5)：412-415.

［3］郭捷，施鵬飛.基于彩色和紋理分析的車牌定位方法[J].中國圖像圖形學(xué)報(bào)，2002，7(5):472-476.

［4］陳國良.遺傳算法及其應(yīng)用［M］.北京：人民郵電出版社，1999.

［5］Wright A H.Genetic Algorithm for Real Parameter Optimization.In:Rawlins Ged.Foundations of Genetic Algorithms，San Francisco:Morgan Kaufmann，1991.

［6］Fogel D B.An Introduction to Simulated Evolutionary Optimization［J］.IEEE Transactions on Neural Networks，1994，5(1):3-14.

作者簡介 陳 梅 女，1975年出生，講師，碩士。主要研究方向?yàn)閳D像處理。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。