改進遺傳算法在車牌定位中的應用

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

關鍵詞：遺傳算法；車牌定位；圖像分割；個體適應度

中圖分類號：TP391.4 文獻標識碼：B

文章編號：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

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

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

1 改進遺傳算法

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

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

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

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

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

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

其中，pi為第i個灰度出現的概率：pi=niW×H，其中W×H為圖像的大小；ni為圖像中灰度值為i的像素的個數。

若閾值為t，則：pt=∑[DD(]t[]i=0[DD)]pi，Ht=－∑[DD(]t[]i=0[DD)]piln pi，與每個分布有關的熵分別為 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

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

(4)選擇:

選擇運算主要實現對群體中的個體進行優勝劣汰操作，適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小；當適應度非常小時就會被淘汰。選擇算子采用輪盤賭選擇方法;

(5) 交叉:

交叉運算是兩個父體根據交叉概率按某種方式相互交換其部分基因而產生一組新的個體。為了使適應度較高的父體的特性遺傳到新個體較好中，這里采用改進的交叉運算，其表達式為：

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

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

(6) 變異:

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

在實數編碼方式下，變異操作對個體X作用一個隨機偏差量，在進化規劃和進化策略^[6]中一般采用高斯變異算子，用正態分布的隨機變量作為變異操作中的偏差量。為了能較好地反映生物界的進化，采用的是與適應度有關的量來作為偏差量，即：

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

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

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

對新的一代，重新計算其適應度，經過新的選擇、交叉和變異后，循環操作，如圖1所示。使群體中最優個體的適應度不斷提高，若算法達到規定的迭代次數或經過一定的迭代次數后群體的適應度不在發生變化，此時算法停止，具有最高適應度的個體即為分割閾值。

圖1 遺傳算法的流程圖

2 車牌圖像的分割

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

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

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

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

[XC<10t2.tif>]

圖2 原始圖像

[XC<10t3.tif>]

圖3 閾值分割后的圖像

3 車牌的定位

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

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

圖4 車牌區的灰度值分布情況

圖5 非車牌區的灰度值分布情況

圖6 定位后的車牌

4 結 語

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

參 考 文 獻

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

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

［4］陳國良.遺傳算法及其應用［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年出生，講師，碩士。主要研究方向為圖像處理。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。