基于改進遺傳算法的圖像分割

高 欣， 卓東風， 劉國洋

（太原科技大學 電子信息工程學院，山西 太原 030024）

0 引言

在對圖像的研究中，圖像分割[1]是由圖像處理到圖像分析的重要步驟。圖像分割是根據圖像的灰度、顏色、幾何特性等，把圖像分成各具特色的區域，將圖像中感興趣的部分分割出來，圖像分割的好壞直接影響到圖像分析的結果，因此具有很重要的意義。圖像分割的常用方法有閾值分割法，邊緣檢測法和區域分割法等，其中閾值分割法是最基本，應用最廣泛的分割方法。許多學者已經提出了很多閾值分割的方法，其中OTSU提出的最大類間方差準則[2-3]來選取閾值的方法被認為是閾值分割的經典方法。由于多數圖像不是簡單的單峰，對于那些灰度直方圖的灰度級分布谷底不明顯的復雜圖像，單一的使用 OTSU準則并不能從圖像中穩定可靠的將目標分割出來，很難達到滿意的效果。很多人用遺傳算法和 OTSU法結合來解決上述問題，但是傳統的遺傳算法容易出現早熟收斂現象。為此本文對基本遺傳算法進行改進，提出一種改進的遺傳算法與 OTSU法則結合的優化算法。本文根據指數變換法的特點提出了一種基于指數變換的非線性的動態適應度函數[4]，使得對種群中個體的評價更為合理，從而保證算法的收斂性，避免早熟，提高全局搜索能力。

1 相關算法

1.1 OTSU分割方法

1979 年，N.OTSU提出最大類間方差法（稱為OTSU法），是一種性能良好的自動閾值選擇方法，直接計算出閾值，不需要對直方圖做預處理，計算簡單，穩定有效，優于其他閾值化算法，受到廣泛關注。它的基本思想是以某一灰度值為閾值將圖像中的像素分成兩類，計算它們的方差。差值越大，目標和背景之間的差異越大，差值最大時所得的灰度值為最佳閾值[5]。

設要待分圖像的像素為N，灰度級為L個（0,1,2,…,L-1），灰度值i的像素值為ni，那么各灰度值的概率設閾值k將圖像分成兩類c0和c1（目標和背景），則c0類和c1類的灰度值分別是（0,1,…,k）和（k+1,k+2,…,L-1）。c0類和c1類產生的概率分別為：

c0類和c1類平均灰度值分別為：

整體灰度平均值為：

其中閾值為k時灰度的平均值為：

兩類方差公式為：

變化0到L-1之間的k值，使得d(k)最大，此時k的取值為則k*為最佳分割閾值。因此，要計算出maxd(k)，必須對0到L-1之間所有的灰度值進行方差計算，計算量非常大，所以尋找一種有效快速的計算方法非常重要。

1.2 遺傳算法

遺傳算法[6-8]（GA，Genetic Algorithm）是模擬生物進化自然選擇和遺傳機制的一種尋優算法。模擬了生物進化機制，自然選擇和遺傳進化中發生的繁殖、交配和突變現象。遺傳算法在求解之前，首先要進行編碼，將問題空間的可行解表示成遺傳空間的串結構數據，生成一個可能潛在解集的初始種群，按照優勝劣汰，適者生存的原則，逐步演化產生出一群新的更適應環境的個體，使群體進化到搜索空間中越來越好的區域。在每一代，根據問題域中個體的適應度選擇個體，進行交叉組合和變異，一代又一代不斷繁殖、進化，最后收斂到一群最適應環境的個體并解碼，作為問題的最優解或近似最優解。

1.3 改進遺傳算法

遺傳算法在搜索選擇中以適應度函數為依據，利用種群中每個個體的適應度值來進行搜索，即用個體的適應度值對解的質量進行評價，適應度越高，解的質量越好，該個體被選擇的幾率越大，因此選擇合適的評價函數至關重要。一般基于遺傳算法的OTSU分割方法用公式7直接作為適應度函數。但在實際中，遺傳進化初期，往往會產生一些超常個體，他們的適應度值遠高于其他個體適應度值，這些超常個體因為競爭力太強而控制了選擇過程，導致早熟收斂現象，影響算法的全局優化；在進化過程中，會出現群體的平均適應度已接近最佳個體適應度，減弱個體間的競爭力，使優化過程無法趨于最優解。對于這2種情況，前者需要降低個體的適應度值，后者需要放大適應度值，以保證群體的多樣性。所以本文提出基于指數變換的非線性的動態適應度函數，將公式7進行改進之后作為遺傳算法的評價函數。改進后的新適應度函數為：

式（8）中，d*(k)是得到的新的適應度函數，a是一個隨進化代數增加而逐漸增加的動態變化的正數，t是當前的進化代數，T是最大遺傳代數，davg是當前種群的平均值。

基于改進遺傳算法的OTSU分割算法

算法步驟如下：

①編碼：由于圖像灰度值在0～255，對應一個8位二進制數，將染色體編成8位二進制碼。

②生成初始種群：產生規模為100的初始種群，設置最大進化代數為50，交叉概率Pc=0.6，變異概率Pm=0.02。

③適應度評估檢測：以式（8）為適應度函數。

④選擇：從當前種群中選擇優良的（適應度高的）個體，復制到下一代新種群中，舍棄適應度低的個體。

⑤交叉：對染色體中的某些相同的基因位按交叉概率Pc進行交換，產生新的種群。

⑥變異：變異就是對種群某個個體中的某些位進行異位，其異位的多少由變異概率Pm來決定從而形成新一代群體。

⑦終止條件：當算法執行到最大迭代次數或群體中的最高適應度值變化不大時，算法停止運行，對具有最高適應度值的個體進行解碼，即可求得最佳分割閾值k。

2 實驗結果

為了驗證上述方法的有效性和準確性，分別用基于遺傳算法的OTSU圖像分割算法和基于改進遺傳算法的OTSU圖像分割算法在matlab環境下對灰度級為256圖像進行分割實驗。實驗結果表明（如圖1所示），采用遺傳算法的OTSU圖像分割算法分割的圖像清晰，改進的算法較之經典遺傳算法在時間方面雖略有增加，但表現出了更好的全局搜索能力，突出感興趣的區域，獲得的分割效果更佳。

圖1 OTSU圖像

3 結語

本文針對標準遺傳算法易于早熟陷入局部最優的不足，提出了一種改進的基于遺傳算法的OTSU分割方法，用動態的適應度函數評價選擇個體，保證了算法初期種群的多樣性，提高了后期較優個體的適應度，有效地克服了早收斂。實驗結果表明，改進的算法較之傳統的遺傳算法，獲得的分割效果更好。

[1]章毓晉.圖像處理和分析[M].清華大學出版社，1999(03):179-180.

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

[3]肖超云，朱偉興.基于Otsu準則及圖像熵的閾值分割算法[J].計算機工程，2007，33(07)：188-189，209

[4]張思才，張方曉. 一種遺傳算法適應度函數的改進方法[J].計算機應用與軟件，2006，23(02):108-110.

[5]譚志存.遺傳聚類算法及其在圖像分割中的應用[D].重慶：西南大學，2009.

[6]李樂,陳鴻昶.一種改進的遺傳算法在聚類分析中的應用[J].通信技術，2009,42(03):263-265.

[7]薛嵐燕，程麗. 基于最大方差法和改進遺傳算法的圖像分割[J].計算機應用與軟件，2008,2(25)：221-222，247.

[8]楊淑瑩.模式識別與智能計算——matlab技術實現[M].北京：電子工業出版社，2008.