基于遺傳算法的二維Otsu算法改進

摘 要:為改善傳統二維0tsu閾值分割算法處理圖像時計算復雜度高、實時性差等缺點，將遺傳算法應用到二維Otsu灰度圖像閾值尋優中，并提出一種改進的自適應遺傳算法。實驗證明，新的算法對灰度圖像有較好的分割效果，與傳統算法相比，分割圖像清晰，實時性也得到了明顯的改進。

關鍵詞:二維Otsu法;閾值分割;自適應遺傳算法

中圖分類號:TP301.6 文獻標志碼:A

文章編號:1001-3695(2010)03-1189-03

doi:10.3969/j.issn.1001-3695.2010.03.0108

2D Otsu algorithm improvement based on genetic algorithm

JIANG Yu-sheng，SONG Xiang-li，REN Jing-jing

(College of Communication Engineering，Chongqing University，Chongqing 400044， China)

Abstract:The traditional two-dimensional Otsu threshold segmentation algorithm had the high computation complexity and poor real-time in processing image.To solve these problems，this paper adopted an improved adaptive genetic algorithm(IAGA)and used in the 2D Otsu gray image segmentation method.It was proved that the new method not only acquired a good effect， but also compared with the traditional 2D Otsu method， the segmented images were more clear and the real-time was advanced obviously.

Key words:2D Otsu method;threshold segmentation;adaptive genetic algorithm

0 引言

圖像分割是從圖像分析到圖像處理的一個關鍵步驟，對多媒體通信起著相當重要的作用，其效果的好壞將直接影響視覺系統的性能。其中，閾值算法[1]因其實現簡單、計算量小、實時性高，而成為圖像分割中最基本和應用最廣泛的技術之一。Sahoo等人[2]通過實驗證明，最大類間方差(Otsu)法是一種很好的閾值化方法。Otsu法是利用圖像中的灰度直方圖，以目標與背景之間的方差最大而動態地確定圖像分割閾值，是經典的非參數、無監督自適應閾值選取方法，不需要其他先驗知識，應用范圍很廣，至今仍是最常用的圖像分割方法之一。但一維像素灰度值僅僅反映了每個圖像像素的自身灰度分布，沒有反映出像素與鄰域的空間相關信息，因而在實際應用中，由于噪聲等干擾因素的存在，灰度直方圖不一定存在明顯的波峰和波谷，此時如果僅根據一維灰度特征來進行圖像分割，往往會產生比較嚴重的分割錯誤?；谶@一點，劉建莊等人[3]提出了基于圖像像素灰度和像素點鄰域平均灰度的二維直方圖閾值分割算法。二維Otsu算法充分利用了圖像像素與其鄰域的空間相關信息，因而比僅利用圖像灰度直方圖的一維0tsu算法具有更強的抗噪聲能力。但是，二維Otsu法增加了計算的復雜性。為克服二維Otsu法計算復雜度高、實時性差、易受噪聲干擾等缺點，本文利用遺傳算法固有的并行性和不易陷入局部最優的特點[4~7]，并對一種自適應遺傳算法進行了改進，將改進的自適應遺傳算法應用到二維Otsu圖像分割中，在尋找最佳閾值的過程中節約了時間，達到了較好的分割效果。

1 二維Otsu算法

設圖像的灰度等級為L，若在圖像的每個像素點計算其鄰域平均灰度值，則鄰域平均圖像的灰度等級也為L，計算每個像素點鄰域的平均灰度，由此形成一個二元組:像素的灰度值i與其鄰域灰度的平均值j。設二元組(i， j)出現的頻數為fij，N為圖像總的像素點數，則可以定義相應的聯合概率Pij為

Pij=fijN(i， j=1，2，3，…，L)(1)

且有N=L-1i=0L-1j=0fij，L-1i=0L-1j=0Pij=1

當閾值為(s，t)時，二維直方圖被分成四個部分，如圖1所示。1、3表示目標和背景，且有不同的概率密度子函數分布。

兩類的概率分別為

ω1=si=0tj=0Pij=ω1(s，t)(2)

ω3=L-1i=s+1L-1j=t+1Pij=ω3(s，t)(3)

兩類對應的均值矢量為

μ1=(μ1i，μ1j)T=(si=0

tj=0iPijω1，si=0

tj=0jPijω1)T(4)

μ3=(μ3i，μ3j)T=(L-1i=s+1

L-1j=t+1iPijω3，L-1i=s+1

L-1j=t+1jPijω3)T(5)

二維直方圖總的均值矢量為

μT=(μTi，μTj)T=(L-1i=0

L-1j=0iPij，L-1i=0L-1j=0

)jPij)T(6)

假定遠離直方圖對角線的Pij為零，即二、四象限的Pij可以忽略不計，則可以得到一個類間離散測度:

SB(s，t)=ω1(s，t)(μ1-μT)T(μ1-μT)+

ω3(s，t)(μ3-μT)T(μ3-μT)=ω1(μ1-μT)T(μ1-μT)+ω3(μ3-μT)T(μ3-μT)=ω1[(μ1i-μTi)2+(μ1j-μTj)2]+ω3[(μ3i-μTi)2+(μ3j-μTj)2](7)

那么最佳的閾值(s*，t*)滿足下式:

SB(s*，t*)=max{SB(s，t)}(8)

2 基于GA的二維Otsu算法改進

遺傳算法是一種借鑒生物界自然選擇和進化機制發展起來的高度并行、隨機、自適應的搜索算法。它使用群體搜索技術，將種群代表一組問題的解，通過對當前種群施加選擇、交叉、變異等遺傳操作，從而產生新一代的種群，并逐步使種群進化到包含近似最優解狀態。隱含并行性和對全局信息的有效利用能力的特點使遺傳算法非常適于大規模搜索空間的尋優。求閾值的過程是一種尋優的過程，符合遺傳算法的基本思想。為了縮短尋優的時間，在求閾值過程中，將遺傳算法應用其中[5，6]，從而實現優化的過程。

二維Otsu法的求解過程就是在解空間中找到一個最優解，使式(8)成立。本文將二維Otsu法與遺傳算法相結合，并對自適應遺傳算法(AGA)[7]進行了改進，提出一種改進的自適應遺傳算法，防止過早收斂和冗余迭代操作，達到了較好的效果。改進算法的主要步驟如下:

a)編碼。由于圖像的灰度級在0～255，將每個染色體編碼為8 bit二進制碼。那么，對于二維Otsu分割，這里定義染色體串長為16 bit，它代表某個閾值。

b)初始群體的生成。初始群體的規模影響到遺傳算法的執行效率和結果。規模太大，則將增加計算復雜性;規模太小，則搜索空間有限，不利于求取最優解。在0～255以同等概率隨機生成20個個體，作為第一次尋優的初始種群。

c)適應度函數的確定。每一代中都有許多不同的染色體存在，決定哪些染色體將遺傳給下一代的因素是個體的適應度大小。在本文中，選擇式(7)作為適應度函數。適應度值越大，越有可能接近最優解。

d)遺傳算子的確定。

(a)選擇機制。本文采用了將賭輪式選擇和排序選擇相結合的混合選擇機制，有利于進化后期保持群體的多樣性。若設種群的大小為n，而個體k的適應度值為fk，首先將fk從大到小進行排序，大的排在前，小的排在后;然后再執行賭輪選擇。避免了選擇概率與適應度偏離的問題，又保證了適應度值最大的優良個體能通過交叉操作產生新的個體，逐步淘汰適應度值小的劣質個體。

(b)交叉算子。它決定了遺傳算法的全局搜索能力，要求它既不要過分干涉個體編碼串中的優良模式，又要能有效地產生出較好的新個體模式。本文采用改進的自適應非線性交叉操作，如式(9)所示。

Pc=Pcmax-Pcmin1+logf*-fmax- f*>

Pcmax f*≤(9)

對于二維Otsu法采用雙點交叉，交叉概率為Pc，最大交叉概率Pcmax=0.90，最小交叉概率Pcmin=0.45。其中:f*表示交叉的兩個個體中較大的適應度值;fmax和分別表示種群中最大適應度值和平均適應度值。

(c)變異算子。因其局部搜索能力而成為輔助算子，是將某一個體中任一位碼按變異概率進行取反操作的過程。變異算子Pm的非線性自適應選取方法為

Pm=Pmmax-Pmmin1+logf-fmax-f>

Pmmaxf≤(10)

其中:f為要變異個體的適應度值，Pmmax=0.1是最大變異概率;Pmmin=0.002是最小變異概率。該方法以為參照，優良個體和劣質個體對應不同的Pc、Pm值，保留優良個體，淘汰劣質個體，加快收斂速度，提高解的質量。

e)終止準則的設定。最大進化代數取40，終止準則為當相鄰兩代個體的平均適應度值的差的范圍在[0.000，0.005]之內時停止迭代。

若不滿足終止準則，以新的群體作為初始群體，轉到步驟c);若滿足，輸出結果。

f)最佳閾值的確定。將最后一代群體中適應度最大的作為最佳結果，將其反編碼，即所求的最佳分割閾值。

算法流程如圖2所示。

3 實驗結果與分析

仿真實驗是在MATLAB 7.0環境下進行的。為了驗證算法的優越性，這里選取了車牌圖像及國際標準圖像Lena進行了仿真實驗。其中每代取20個個體，遺傳迭代次數gen取40。實驗結果如表1、2以及圖3、4所示。

對比兩幅圖像的分割結果可以看出，圖3、4(c)較圖3、4(b)輪廓清晰，分割效果相當好。而且，遺傳算法在第25代左右就得到了圖像的最佳分割閾值，相比傳統二維Otsu算法，計算量明顯降低，時間上節約了37.25%左右。實時性得到了明顯的提高，達到了較理想的分割效果。

表1 車牌圖像分割比較

分割算法最佳閾值25次分割平均時間/s

二維Otsu法1030.83

基于GA的二維Otsu1070.52

表2 Lena圖像分割對應最優閾值

代數閾值代數閾值

19524118

10103……

1511140118

4 結束語

傳統二維Otsu圖像分割算法雖然也可以抑制一定的噪聲，分割的穩定性也較好，但對于每一對候選閾值都要按式(7)計算一次，計算量大，非常耗時。而基于遺傳算法改進的二維Otsu灰度圖像分割方法，初始群體取為30，最大繁殖代數為40代，且實驗表明，在第24代時已得出最佳閾值，對于有噪聲干擾的灰度圖像有較好的分割效果，與傳統的分割方法相比，運行時間得到了明顯的提高。可見，作為一種優化算法，遺傳算法應用到圖像分割領域時，可以大大縮短尋找閾值的時間，具有很好的應用前景。

參考文獻:

[1]

ZHANG Jun，HU Jing-lu.Image segmentation based on 2D Otsu method with histogram analysis[C]//Proc of International Conference on Computer Science and Software Engineering.2008:105-108.

[2]SAHOO P K，SOLTANI S，WONG A K C，et al.A survey of thresholding techniques[J].Computer Vision，Graphics and Image Processing，1988，41(2):233-260.

[3]劉建莊，栗文清.灰度圖像的二維Otsu自動閾值分割法[J].自動化學報，1993，19(1):101-105.

[4]XUE Sheng-jun，GUO Shao-yong，BAI Dong-ling.The analysis and research of parallel genetic algorithm[C]//Proc of the 4th International Conference on Wireless Communications，Networking and Mobile Computation.2008:1-4.

[5]雷英杰，張善文，李續武，等.MATLAB遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社，2005.

[6]ZHAO Xin，LEE M E，KIM S H.Improved image segmentation method based on optimized threshold using genetic algorithm[C]//Proc of IEEE/ACS International Conference on IEEE Computer Systems and Applications.2008:921-922.

[7]DENG Xiang-hui.Application of adaptive genetic algorithm in inversion analysis of permeability coefficients[C]//Proc of the 2nd International Conference on Genetic Evolutioning Computing.2008:61-65.