基于免疫遺傳算法的道路交通標(biāo)志圖像分割

汪宏海

?

基于免疫遺傳算法的道路交通標(biāo)志圖像分割

汪宏海

（浙江旅游職業(yè)學(xué)院，浙江，杭州 311231）

針對道路交通標(biāo)志圖像分割的問題，提出了一種基于免疫遺傳算法的實(shí)現(xiàn)方法。該算法利用免疫遺傳機(jī)制，將圖像的最佳閾值作為要求的解，設(shè)計(jì)了適合問題求解的抗體編碼方式、克隆算子和免疫選擇算子。仿真實(shí)驗(yàn)結(jié)果表明，所提算法能夠有效地求得道路交通標(biāo)志問題的最佳閾值。通過與傳統(tǒng)遺傳算法、改進(jìn)遺傳算法進(jìn)行對比實(shí)驗(yàn)，更好地說明了本算法能夠?qū)D像分割得到較為滿意的結(jié)果。

免疫遺傳算法；圖像分割；交通標(biāo)志；閾值；收斂性

1　概述

隨著物聯(lián)網(wǎng)時代智慧城市的快速建設(shè)，智能交通系統(tǒng)正逐步改善著交通運(yùn)輸質(zhì)量。道路與交通標(biāo)志圖像的分析和處理是智能交通應(yīng)用研究領(lǐng)域中重要組成部分，也是所面臨的圖形識別難題之一。圖像分割是圖像分析處理的關(guān)鍵技術(shù)之一，其目的是將圖像中的目標(biāo)和背景分離開來，為后續(xù)的分類、識別和檢索提供依據(jù)[1]。如何從圖像中快速、準(zhǔn)確地分割出道路交通標(biāo)志就變得十分重要[1]。

傳統(tǒng)的圖像分割方法包括閾值法、邊緣檢測法、區(qū)域跟蹤法等。其中，閾值分割方法因其實(shí)現(xiàn)簡單、計(jì)算量小、性能較穩(wěn)定而成為圖像分割中最基本和應(yīng)用最廣泛的分割技術(shù)[1]。它特別適用于目標(biāo)和背景占據(jù)不同灰度級范圍的圖像，不僅極大地壓縮了數(shù)據(jù)量，而且也大大地簡化了分析和處理步驟。但是，不同的閾值會直接導(dǎo)致圖像分割的不同結(jié)果，因此尋找一個最佳閾值已經(jīng)成為圖像分割的關(guān)鍵點(diǎn)。由于此問題經(jīng)過建模為NP問題，不同的研究者提出了不同的智能算法進(jìn)行求解。文獻(xiàn)[4]利用遺傳算法來選取閾值，文獻(xiàn)[5]對遺傳算法進(jìn)行了改進(jìn)。以上方法取得了較好的結(jié)果，但遺傳算法本身容易陷入局部最優(yōu)。免疫遺傳算法在遺傳算法的基礎(chǔ)上引入了濃度調(diào)節(jié)機(jī)制。進(jìn)行選擇操作時，遺傳算法只利用適應(yīng)度指標(biāo)對個體進(jìn)行評價，容易導(dǎo)致種群進(jìn)化單一。而免疫遺傳算法的選擇策略變?yōu)椋哼m應(yīng)度越高，濃度越小，個體復(fù)制的概率越大；適應(yīng)度越低，濃度越大，個體復(fù)制的概率越小。這樣就可以有效地調(diào)節(jié)選擇壓力，防止種群退化，并在局部和全局搜索上表現(xiàn)出不俗的能力，更適合用來求解最佳閾值[6-7]。本文通過應(yīng)用免疫遺傳算法，為道路交通標(biāo)志圖像處理提供有力的技術(shù)，求得圖像的最佳閾值，達(dá)到較好的效果。通過實(shí)驗(yàn)結(jié)果分析，本文算法優(yōu)于其他遺傳算法。

2 道路交通標(biāo)志圖像

道路與交通標(biāo)志的圖像分割就是根據(jù)圖像中目標(biāo)與背景的先驗(yàn)知識，對圖像中的目標(biāo)、背景精細(xì)標(biāo)記、定位，然后將目標(biāo)從背景或者偽目標(biāo)中分離開來。

道路與交通標(biāo)志中，物體與背景的對比較為明顯，使用閾值分割技術(shù)效果就很好。對灰度圖像的取閾值分割就是先確定一個處于圖像灰度取值范圍之中的灰度閾值，然后將圖像中的各個像素的灰度值與這個閾值相比較。所有灰度值大于或者等于此閾值的像素都被判為屬于物體；所有灰度值小于該閾值的像素被排除在物體之外[8]。

確定閾值是分割的關(guān)鍵。能確定一個合適的閾值，就可以方便地將圖像分割開來。

設(shè)(,)是二維數(shù)字圖像的平面坐標(biāo)，道路交通標(biāo)志的圖像灰度級的取值范圍定義：G={0,1,2,…,-1}（習(xí)慣上0代表最暗的像素點(diǎn)，-1代表最亮的像素點(diǎn)），位于坐標(biāo)(,)上的像素點(diǎn)的灰度級表示為(,)。設(shè)∈為分割閾值，B={0,1}代表一個二值灰度級，并且0,1=G，于是函數(shù)(,)在閾值上的分割結(jié)果可以表示為兩類：

即閾值將圖像分為兩類：

0={0,1,2,…,}

1={+1,+2,…,-1},

0與1分別代表目標(biāo)與背景。

圖像灰度級的概率分布為：

式中n表示的是灰度的像素?cái)?shù)；表示的是圖像的像素?cái)?shù)；P表示的是灰度級出現(xiàn)的概率。

C0與C1出現(xiàn)的概率分別為:

C0與C1的均值分別為：

使σ2取最大值時的t就是最佳閾值：

傳統(tǒng)的方法例如窮盡法需要遍歷灰度范圍內(nèi)的所有的圖像像素，然后再計(jì)算方差，計(jì)算量巨大，很顯然這樣的算法效率十分低下，并且結(jié)果也不夠優(yōu)秀。面對這樣的問題，智能優(yōu)化算法更適合用來求解，將會有快速高效的性能。

3 免疫遺傳算法實(shí)現(xiàn)圖像分割

3.1 免疫遺傳算法

免疫算法是人工智能領(lǐng)域重要的應(yīng)用之一，它是基于生物免疫系統(tǒng)基本機(jī)制，模仿了人體的免疫系統(tǒng)，達(dá)到解決問題的效果。具有動態(tài)性、自適應(yīng)、魯棒性強(qiáng)等優(yōu)點(diǎn)，已經(jīng)廣泛應(yīng)用在組合優(yōu)化、配置尋優(yōu)、人工智能等領(lǐng)域。免疫遺傳算法是免疫算法中的一種[9]。

免疫遺傳算法是針對遺傳算法控制收斂不足、記憶能力差、優(yōu)勢遺傳不夠明顯的問題而提出的一種更加智能的免疫算法。它的主要目的是防止種群的退化，有效地調(diào)節(jié)選擇壓力，避免進(jìn)化單一，使得種群能夠更好地保持多樣性。免疫遺傳算法不僅繼承了遺傳算法的健壯性和并行計(jì)算的優(yōu)良特點(diǎn)，更主要的是具有免疫算法的記憶功能、學(xué)習(xí)性以及自適應(yīng)性的優(yōu)點(diǎn)，在工程和研究領(lǐng)域有相當(dāng)大的研究價值和應(yīng)用潛力[10-11]。

3.2 抗體編碼

免疫算法中，抗體表示的是對應(yīng)要求解問題的解，因此抗體編碼就是免疫問題求解的關(guān)鍵技術(shù)之一，它主要是用來完成待求解問題的表示。在道路與交通標(biāo)志的圖像分割中，圖像的灰度級在0~255之間，數(shù)值范圍大小剛好是二進(jìn)制數(shù)的指數(shù)值，因此單個抗體編碼采用8位二進(jìn)制數(shù)。假設(shè)某個抗體的編碼為a= {a1, a2,…,a8}，把二進(jìn)制數(shù)轉(zhuǎn)為十進(jìn)制數(shù)值的大小就是單個抗體的值，它表示的是某個閾值。

3.3 算法的實(shí)現(xiàn)

道路、交通標(biāo)志圖像分割的過程就是將道路、交通標(biāo)志中的背景與目標(biāo)分離開來[12-13]。其關(guān)鍵在于求解找到一個最佳閾值，使得圖像的σ2最大，因此算法的目標(biāo)函數(shù)為：

maxF=σ2

利用免疫遺傳算法實(shí)現(xiàn)道路交通標(biāo)志圖像分割的原理流程圖如圖1所示：

圖1 算法流程圖

基于免疫遺傳算法對道路交通標(biāo)志圖像分割求解最佳閾值的具體步驟如下：

步驟1 種群初始化。采用隨機(jī)的方式產(chǎn)生初始抗體種群0，設(shè)置種群數(shù)=10，作為最初的候選解集。給定種群最大迭代次數(shù)gmax=50。

步驟2 計(jì)算抗體適應(yīng)度。對當(dāng)前群體Ak中的每一個抗體都進(jìn)行適應(yīng)度計(jì)算，適應(yīng)度值越高的說明圖像分割的效果越好，越接近最佳。

步驟3 記憶單元更新。對適應(yīng)度高的抗體進(jìn)行記憶存儲，形成記憶種群M。

步驟4 抗體的抑制和促進(jìn)。在免疫遺傳算法中通過使用濃度調(diào)節(jié)機(jī)制進(jìn)行個體復(fù)制，避免群體進(jìn)化單一，保持種群的多樣性，最后得到候選種群B。

抗體a的濃度的計(jì)算公式為：

更詳細(xì)的介紹可參考文獻(xiàn)[9]。

步驟5 交叉操作。對候選種群B執(zhí)行交叉操作T形成臨時群體C。

步驟6 變異操作。對種群C執(zhí)行變異操作T形成新的臨時群體D。

步驟7 免疫選擇。對種群D注射免疫疫苗M后，對所有的抗體執(zhí)行免疫選擇，選擇出前個個體作為優(yōu)勢抗體，生成下一代群體A，即最佳閾值候選解集。

步驟8 終止條件判斷。當(dāng)滿足終止條件的時候則停止，輸出適應(yīng)度值最高的抗體，它所表示的是最佳閾值，得到圖像分割結(jié)果；否則轉(zhuǎn)到步驟2。

4 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文算法對道路交通標(biāo)志圖像分割的性能，實(shí)驗(yàn)選取了道路和交通標(biāo)志兩種圖像作為原始圖像，分別使用免疫遺傳算法、傳統(tǒng)的遺傳算法[4]以及混合遺傳算法對圖像進(jìn)行分割[5]。其中實(shí)驗(yàn)參數(shù)中，設(shè)定種群規(guī)模為15，交叉概率為0.4，變異概率為0.1，最大迭代數(shù)為50。通過運(yùn)行程序，最終得到的分割結(jié)果。

圖2 道路圖像分割結(jié)果

圖2是道路圖像分割的結(jié)果。其中，圖2(a)是道路圖像原始圖像，圖2(b)是本文算法的圖像分割結(jié)果，圖2(c)是傳統(tǒng)遺傳算法所得到的圖像分割結(jié)果，圖2(d)是改進(jìn)遺傳算法所得到的圖像分割結(jié)果。從圖中可以清晰地看出，對道路圖像的分割，傳統(tǒng)的遺傳算法得到的圖像邊緣比較模糊，處理結(jié)果差；改進(jìn)的遺傳算法圖像結(jié)果邊緣比較清晰，能夠正確的分割出道路的輪廓，但是內(nèi)部沒有分割；本文所用的免疫遺傳算法得到的圖像邊緣清晰，車道線也明顯，圖像處理的結(jié)果較好。

圖3 交通標(biāo)志分割結(jié)果

圖3是交通標(biāo)志的分割結(jié)果。其中，圖3(a)是原始圖像，圖3(b)、圖2(c)和圖2(d)分別是本文算法、傳統(tǒng)遺傳算法以及混合遺傳算法所得到的圖像分割結(jié)果。從圖中可以直接的看出，傳統(tǒng)遺傳算法得到的結(jié)果中輪廓清晰，但是邊緣依然比較模糊；改進(jìn)遺傳算法分割圖像邊緣清晰，但其中的立桿不明顯；本文算法得到的圖像結(jié)果輪廓清晰，立桿明顯，處理效果較好。

對道路圖像利用上面三種算法分別進(jìn)行10次獨(dú)立實(shí)驗(yàn)，給出10次獨(dú)立運(yùn)行結(jié)果，對結(jié)果的均值和方差進(jìn)行比較，采用適應(yīng)度函數(shù)評價次數(shù)來評價算法的運(yùn)算量。比較結(jié)果如表1所示。

表1 閾值分割10次結(jié)果比較

由以上結(jié)果可以看出，遺傳算法每次得到的最優(yōu)閾值波動較大，免疫遺傳算法相比較其他兩種算法較為穩(wěn)定。并且在得到解的同時，免疫遺傳算法評價次數(shù)最少，說明計(jì)算量較小，但卻可以得到較優(yōu)的結(jié)果。

5 結(jié)束語

本文提出的基于免疫遺傳算法求解道路交通標(biāo)志圖像分割的問題，把所要求的最佳閾值抗原進(jìn)行求解，實(shí)驗(yàn)結(jié)果表明了算法的有效性。通過與多種算法所得分割圖像結(jié)果進(jìn)行對比可以看出，免疫遺傳算法能夠得到較好的圖像分割最優(yōu)閾值，對圖像的處理效果較好。但是面對道路交通狀況較為復(fù)雜的情況會對圖像分割產(chǎn)生影響，這將是下一步繼續(xù)深入研究的內(nèi)容。

[1] 趙全華,高郡,趙雪梅. 結(jié)合KL距離與圖像域分塊的SAR圖像分割[J].控制與決策,2017,43(11):1126-1130.

[2] 尹曉葉,李俊吉. 基于增強(qiáng)布谷鳥搜索的圖像分割算法[J].控制工程,2017,32(10):116-120.

[3] Ma M, Liang J, Guo M, et al. SAR image segmentation based on Artificial Bee Colony algorithm[J].Applied Soft Computing, 2011, 11(8):5205-5214.

[4] 李婷,杜永貴. 基于云遺傳算法的閾值圖像分割法 微電子學(xué)與計(jì)算機(jī)[J]. 2015,12(5):389-396.

[5] 賀建峰,符增,易三莉. 基于遺傳算法的灰度-梯度熵多閾值圖像分割[J].計(jì)算機(jī)科學(xué)與探索,2015, 6(11):93-95.

[6] Gong M, Zhang L, Ma J, et al. Community detection in dynamic social networks based on multi-objective immune algorithm[J]. Journal of Computer Science and Technology. 2012, 27(3) :455-467.

[7] Mohanta R K, Sethi B. A Review of Genetic Algorithm application for Image Segmentation[J]. International Journal of Computer Technology and Applications. 2012, 03(02).

[8] 喬陽. 基于改進(jìn)遺傳算法的圖像分割方法[D]. 成都：電子科技大學(xué). 2013.

[9] Gong M, Chen X, Ma L, et al. Identification of multi-resolution network structures with multi- objective immune algorithm[J]. Soft Computing. 2013, 13(4): 1705-1717.

[10] 張向榮,騫曉雪,焦李成. 基于免疫譜聚類的圖像分割[J].軟件學(xué)報(bào). 2010, 21(9):2196-2205.

[11] 林正春,王知衍,張艷青. 最優(yōu)進(jìn)化圖像閾值分割算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2013,22(7):1201-1206.

ROAD TRAFFIC SIGN IMAGE SEGMENTATION BASED ON IMMUNE GENETIC ALGORITHM

WANG Hong-hai

（Tourism College of Zhejiang, Hangzhou, Zhejiang 311231, China）

To solve the problem in road traffic sign image segmentation, a image segmentation based on immune genetic algorithm was proposed. The algorithm used immune genetic mechanism and took the optimal threshold value of the image as the requirements of the solution. Antibody coding, cloning operator and immune selection operator that are suitable for solving the problem were design. The simulation results show that the proposed algorithm can effectively get the optimal threshold in the problem of road traffic signs. By comparing with the traditional genetic algorithm and the improved genetic algorithm, it better illustrates that the algorithm can obtain a satisfactory result for image segmentation.

immune genetic algorithm; image segmentation; road; traffic sign; threshold value; convergence

1674-8085(2018)01-0060-05

TP301.6

A

10.3969/j.issn.1674-8085.2018.01.013

2017-08-11；

2017-11-05

汪宏海(1977-)，男，江西樟樹人，副教授，主要從事圖像處理、智能算法等方面的研究(E-Mail:redsea54@163.com).