王丹　周錦程

【摘 要】二維最大熵圖像閾值分割法是在整個(gè)二維灰度空間上搜索相關(guān)參數(shù)，從而使得圖像的總熵取得最大值的優(yōu)化問題，該算法計(jì)算量大、耗時(shí)長。為此，我們將二維最大熵的圖像閾值分割方法中的相關(guān)技術(shù)引入到遺傳算法中，以降低算法的復(fù)雜度。具體地，結(jié)合二維最大熵圖像分割法的特點(diǎn)，我們對(duì)傳統(tǒng)遺傳算法中的選擇算子、交叉算子和變異算子等進(jìn)行了優(yōu)化設(shè)計(jì)，以加快算法的收斂性。實(shí)驗(yàn)結(jié)果表明，本文設(shè)計(jì)的基于遺傳算法的二維最大熵圖像分割方法所分割的圖像優(yōu)于一般常用的圖像分割算法。

【關(guān)鍵詞】遺傳算法；二維最大熵法；圖像分割；閾值分割

An Improved Genetic Algorithm for Image Segmentation

WANG Dan ZHOU Jin-cheng

（School of Mathematics and Statistics，Qiannan Normal College for Nationalities， Duyun Guizhou 558000， China）

【Abstract】The two-dimensional maximum entropy method is an optimization problem for the parameters search in the whole two-dimensional gray space to obtain the maximum total entropy of an image. Thus， the amount of the calculation would be large and the time cost would be high. In order to reduce the complexity of the algorithm， we introduce the relevant technology of the two-dimensional maximum entropy method into the genetic algorithm for image segmentation problem. Specifically， considered with the characteristics of two-dimensional entropy image segmentation method， we optimize the selection， crossover and mutation operators in the traditional genetic algorithm， so as to accelerate the convergence of the search process. Experimental results show that our genetic algorithm with two-dimensional maximum entropy method is better than the common image segmentation algorithm.

【Key words】Genetic algorithm； Two-dimensional maximum entropy method； Image segmentation； Threshold segmentation

0 引言

遺傳算法（Genetic Algorithm， GA）[1]是由美國Michigan大學(xué)的Holland于1975年提出的一種隨機(jī)自適應(yīng)的全局搜索算法。它是一種通過借鑒進(jìn)化論中適者生存、優(yōu)勝劣汰的遺傳機(jī)制演化而來的計(jì)算模型。該算法的基本思想最先由Holland[2]在1962年提出，之后陸續(xù)有研究者提及了該算法的一些基本概念[3-6]，“遺傳算法”這個(gè)術(shù)語在1967年首先由Bagley在其博士論文中使用，但直至1975年，遺傳算法的數(shù)學(xué)框架與理論才由Holland[7]在其專著中進(jìn)行了系統(tǒng)而詳細(xì)的表述。

早期的遺傳算法主要被用于求解函數(shù)優(yōu)化問題和人工自適應(yīng)系統(tǒng)的研究與設(shè)計(jì)。隨著遺傳算法的不斷改進(jìn)與完善，它為解決復(fù)雜優(yōu)化問題提供了一種嶄新且有效的思路，其良好的搜索能力得了廣大學(xué)者的關(guān)注和認(rèn)可。當(dāng)前，遺傳算法的應(yīng)用范圍已被逐漸延伸到了組合優(yōu)化、圖像處理、網(wǎng)絡(luò)通信、模式識(shí)別等眾多復(fù)雜優(yōu)化領(lǐng)域。

圖像分割[8]是圖像處理及前期視覺中常常用到的一種基本技術(shù)，也是大多數(shù)圖像分析及視覺系統(tǒng)的重要組成部分。所謂圖像分割是指根據(jù)圖像的灰度、幾何形狀、空間紋理、色彩等特征把圖像劃分成若干個(gè)互不相交的區(qū)域，使得這些特征在不同區(qū)域間表現(xiàn)出明顯的不同，而在在同一區(qū)域內(nèi)，表現(xiàn)出一致性或相似性。本文將主要研究遺傳算法在圖像分割中的應(yīng)用。

1 相關(guān)概述

1.1 遺傳算法

遺傳算法主要是通過模擬自然界中生物的遺傳進(jìn)化過程，對(duì)優(yōu)化問題的最優(yōu)解進(jìn)行搜索，它將種群中的所有個(gè)體作為潛在解的群里，引入類似自然進(jìn)化中的選擇、交叉和變異等算子對(duì)群體中的所有個(gè)體進(jìn)行進(jìn)化。遺傳算法的核心內(nèi)容主要包括以下五個(gè)方面：①設(shè)計(jì)相關(guān)參數(shù)的編碼；②設(shè)定初始群體；③設(shè)計(jì)適應(yīng)度函數(shù)；④設(shè)計(jì)遺傳操作；⑤設(shè)定控制參數(shù)。與傳統(tǒng)的搜索算法不同，遺傳算法在運(yùn)行中，首先要隨機(jī)產(chǎn)生一組初始解作為種群開始搜索，種群中的每個(gè)個(gè)體（編碼為染色體）被看做是問題的一個(gè)解。這些個(gè)體在后續(xù)迭代過程中不斷進(jìn)化。通常用適應(yīng)度值來度量每一代中各個(gè)染色體對(duì)應(yīng)的個(gè)體的優(yōu)劣，一般來說，對(duì)應(yīng)個(gè)體的適應(yīng)度值越大，表示該個(gè)體越優(yōu)秀，則該個(gè)體被選作種群中的父帶個(gè)體的概率也越大。新個(gè)體由父代個(gè)體對(duì)應(yīng)的染色體通過交叉或者變異操作而產(chǎn)生，這樣經(jīng)過若干代進(jìn)化之后，算法將收斂于最好的個(gè)體，該個(gè)體很有可能就是問題的最優(yōu)解或次優(yōu)解。遺傳算法主要包括如下步驟：

Step 1 編碼：遺傳算法在對(duì)解進(jìn)行搜索之前，需要先將解空間的解進(jìn)行編碼成特點(diǎn)的字符串。

Step 2 初始群體的生成：隨機(jī)產(chǎn)生N個(gè)染色體，N個(gè)染色體構(gòu)成了一個(gè)種群，遺傳算法以這N個(gè)染色體作為初始點(diǎn)開始迭代。

Step 3 個(gè)體評(píng)價(jià)：用適應(yīng)值函數(shù)刻畫個(gè)體的優(yōu)劣性。通常，針對(duì)不同的優(yōu)化問題，需要設(shè)計(jì)不同的適應(yīng)性函數(shù)。

Step 4 選擇運(yùn)算：按照一定的規(guī)則從當(dāng)前群體中選出優(yōu)良的個(gè)體，其主要思想來自于達(dá)爾文的適者生存原則。

Step 5 交叉運(yùn)算：新個(gè)體通過交叉操作獲得且繼承其父輩個(gè)體的特征，交叉體現(xiàn)了信息交換的思想。

Step 6 變異操作：將變異算子作用于新群體中的少部分個(gè)體，對(duì)這部分個(gè)體的染色體以一定的概率隨機(jī)地改變?nèi)旧w中某些基因的編碼，變異是為了在群體中引入新的變種，確保種群的多樣性。

1.2 圖像分割

當(dāng)前，常用圖像分割方法主要包括邊緣檢測(cè)法、區(qū)域分割法以及閾值分割法等。其中，閾值分割法因其計(jì)算量小、實(shí)現(xiàn)簡單、性能較為穩(wěn)定而成為圖像分割中最基本和應(yīng)用最廣泛的分割技術(shù)。當(dāng)前，已有很多基于閾值分割的處理方法，諸如最大類別方差法[9]（OTSU法），最小誤差法和最佳直方圖熵法[10]（KSW熵法）等等。其中，最佳直方圖熵法是將信息論中的最大熵原理應(yīng)用于圖像的閾值分割，往往可以找到最佳的分割閾值。

現(xiàn)有的閾值法，選取最佳閾值時(shí)盡管有很多準(zhǔn)則，但大多算法需要在全灰度范圍內(nèi)進(jìn)行搜索，因此搜索空間大、時(shí)間開銷多。因此，如何尋找易計(jì)算并且自適應(yīng)能力強(qiáng)的閾值方法在圖像處理工作中一直是值得研究的重要課題。遺傳算法是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，其對(duì)全局信息的有效搜索能力，使得該方法只需檢測(cè)少量的結(jié)構(gòu)就能反映搜索空間較大的區(qū)域，并獲得穩(wěn)定的最優(yōu)解。因此，本文通過有機(jī)地結(jié)合遺傳算法和二維最大熵閾值法，提出了一種新的圖像分割算法。該算法能有效提高圖像分割的速度且能獲得較好的分割結(jié)果。

2 改進(jìn)遺傳算法的圖像分割

2.1 二維最大熵圖像分割法

一般情況下，在圖像質(zhì)量較好和背景穩(wěn)定變化時(shí)，一維最大熵圖像分割算法能得到較好的分割結(jié)果，而對(duì)于具有較為復(fù)雜的背景或信噪比較低的圖像，其性能往往較差。文獻(xiàn)[11]提出了一種二維最大熵圖像分割算法，該算法采用了圖像各像素間的空間相關(guān)信息和像素的灰度分布信息，并使用像素灰度和鄰域平均灰度構(gòu)成的二維直方圖來搜索閾值，實(shí)驗(yàn)結(jié)果表明，該算法能獲得較好的分割效果。

設(shè)一幅N×N的圖像I有L級(jí)灰度G={0，1，…，L-1}，其s×s的鄰域的平均灰度也有L級(jí)灰度G={0，1，…，L-1}，相應(yīng)的二維直方圖表示為：h（i，j）=pij，0≤i，j≤L-1，其中i為像素灰度，j為s×s鄰域的平均灰度。pij由下式確定：

2.2 改進(jìn)遺傳算法的圖像分割方法

由于二維最大熵法實(shí)質(zhì)上是在二維灰度空間上搜索參數(shù)從而使圖像的總熵取得最大值，因此算法的計(jì)算量較大、耗時(shí)較長。為降低算法的復(fù)雜度，本文將二維最大熵的圖像閾值分割方法中的相關(guān)技術(shù)引入到遺傳算法中。具體地，結(jié)合二維熵圖像分割法的特點(diǎn)，我們對(duì)傳統(tǒng)遺傳算法中的選擇、交叉、變異等基本算子進(jìn)行設(shè)計(jì)，以加快算法的收斂性并確保得到較好的解。本文對(duì)遺傳算法的設(shè)計(jì)如下：

（1）采用均勻分布隨機(jī)產(chǎn)生初始化種群。

（2）由于圖像分割的處理對(duì)象是具有不同灰度級(jí)的像素點(diǎn)，本文考慮的分割圖像為256個(gè)灰度級(jí)，閾值參數(shù)滿足0≤s，t≤255，因此我們將灰度分割閾值（s，t）編碼為一個(gè)長度恰好為16位的二進(jìn)制串，并用其中的低8位用來編碼t，高8位用來編碼s。

（3）采用二維熵圖像分割法中的圖像的總熵H（s，t）作為我們算法的適應(yīng)度評(píng)價(jià)函數(shù)。

（4）采用輪盤賭法和精英策略相結(jié)合的方案對(duì)染色體進(jìn)行選擇操作。

（5）采用隨機(jī)產(chǎn)生的多個(gè)交叉點(diǎn)的方式進(jìn)行多點(diǎn)交叉操作。

（6）采用隨機(jī)隨機(jī)按位取反的方式對(duì)個(gè)體進(jìn)行變異操作。

（7）采用收斂程度和最大進(jìn)化代數(shù)結(jié)合的停機(jī)策略，即終止條件為達(dá)到最大進(jìn)化代數(shù)gmax，或者當(dāng)前群體的平均適應(yīng)度值與上一代群體的平均適應(yīng)度值的絕對(duì)差小于ε。算法終止時(shí)，具有最高適應(yīng)度值的個(gè)體作為最佳閾值。

本文構(gòu)造改進(jìn)遺傳算法的圖像分割方法的計(jì)算流程如下：

Step 1 設(shè)定種群數(shù)目N，對(duì)二維閾值進(jìn)行二進(jìn)制編碼，并隨機(jī)產(chǎn)生初始種群。

Step 2 對(duì)初始種群解碼，并根據(jù)式（2），式（3）和式（4）計(jì)算每個(gè)基因串的適應(yīng)度值。

Step 3 將適應(yīng)度最大的個(gè)體，即種群中最好的個(gè)體直接復(fù)制到下一代新種群中，然后對(duì)父代種群進(jìn)行采用本文提出的選擇、交叉和變異等遺傳算子運(yùn)算，從而繁殖出下一代新種群的其它N-1個(gè)基因串（個(gè)體）。

Step 4 如果達(dá)到終止準(zhǔn)則，則返回最好的基因串，并將其作為二維分割閾值分割圖像，算法結(jié)束；否則回到Step 3繼續(xù)下一代的繁衍。

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

為驗(yàn)證本文算法的有效性和準(zhǔn)確性，分別用OTSU分割算法、文獻(xiàn)[12]提出的二維直方圖θ劃分最大Shannon熵圖像閾值分割算法和本文提出的基于改進(jìn)的遺傳算法的圖像分割算法，在matlab環(huán)境下對(duì)灰度級(jí)為256圖像進(jìn)行分割實(shí)驗(yàn)。三種算法對(duì)米粒圖像和標(biāo)準(zhǔn)Lenna圖像分割的實(shí)驗(yàn)結(jié)果如圖1、圖2所示。其中，基于遺傳算法的圖像熵分割結(jié)果圖采用隨機(jī)運(yùn)行20次得到的最好結(jié)果圖。圖1（a）是為源圖像，圖1（b）、（c）、（d）分別為三種算法的分割結(jié)果圖。從圖中可以看出，三種分割方法都能較好地分割源圖像，基于遺傳算法的圖像熵分割方法比OTSU分割算法提取了更多的米粒目標(biāo)，結(jié)果圖（d）中分割的圖像較圖（b）和圖（c）更清晰，提取了更多的米粒目標(biāo)。對(duì)標(biāo)準(zhǔn)Lenna圖的分割結(jié)果如圖2所示，其效果也優(yōu)于OTSU算法和文獻(xiàn)[12]中的算法。因此，綜合圖1和圖2的分割結(jié)果圖可見，本文算法比基于基本遺傳算法的圖像熵分割方法收斂快，分割閾值與OTSU相當(dāng)，能夠比較理想地完成對(duì)圖像的分割，分割的圖像清晰，表現(xiàn)出了更好的全局搜索能力，更能突出感興趣的區(qū)域，并獲得更好的分割效果。

4 結(jié)語

遺傳算法是一種獨(dú)立于問題領(lǐng)域且具有快速隨機(jī)搜索能力的隨機(jī)算法，該算法通過模擬自然進(jìn)化過程搜索最優(yōu)解，（下轉(zhuǎn)第117頁）（上接第109頁）其對(duì)全局信息的有效搜索能力，使得該方法只需檢測(cè)少量的結(jié)構(gòu)就能反映搜索空間較大的區(qū)域，并能獲得較為穩(wěn)定的最優(yōu)解。由于傳統(tǒng)的二維最大熵法實(shí)質(zhì)上是在二維灰度空間上搜索參數(shù)從而使圖像的總熵取得最大值，因此算法的計(jì)算量較大、耗時(shí)長。因此，本文結(jié)合二維最大熵法的特點(diǎn)，將二維最大熵的圖像閾值分割法中的相關(guān)技術(shù)引入到遺傳算法中，并設(shè)計(jì)了相應(yīng)遺傳算法的選擇、交叉、變異等算子。實(shí)驗(yàn)結(jié)果表明，我們所提出的算法能有效提高圖像分割的速度且能獲得較好的分割結(jié)果。

【參考文獻(xiàn)】

[1]Holland J H. Genetic algorithms[J]. Scientific American， 1992， 267（1）： 66-72.

[2]Holland J H. Outline for a logical theory of adaptive systems[J]. Journal of the ACM （JACM）， 1962， 9（3）： 297-314.

[3]Bagley J D. The behavior of adaptive systems which employ genetic and correlation algorithms[D]. Ph. D. Dissertation， University of Michigan. 1967.

[4]Cavicchio D J. Adaptive search using simulated evolution[D]. Ph. D. Dissertation， University of Michigan. 1970.

[5]Hollstien R B， Artificial Genetic Adaptation in Computer Control System. Ph. D[Z]. Dissertation， University of Michigan. 1970.

[6]De Jong K A. Analysis of the behavior of a class of genetic adaptive systems[D]. Ph. D. Dissertation， University of Michigan. 1975.

[7]Holland J H. Adaptation in natural and artificial systems[M]. 2nd ed. Cambridge： MIT Press， 1992.

[8]章毓晉.圖像分割[M].北京：科學(xué)出版社，2001.

[9]Otsu N. A Threshold Selection Method from Gray Level Histogram[J]. IEEE Trans on System Man and Cybernetics， 1979，9（1）：62-66.

[10]Kapur J N， Sahoo P K， Wong A K C. A new method for gray-level picture thresholding using the entropy of the histogram[J]. Computer Vision Graphics & Image Processing， 1985，29（3）：273-285.

[11]Abutaleb A S. Automatic thresholding of gray-level pictures using two-dimensional entropy[J]. Computer Vision Graphics & Image Processing， 1989，47（1）：22-32.

[12]吳一全，張金礦.二維直方圖θ劃分最大Shannon熵圖像閾值分割[J].物理學(xué)報(bào)，2010，59（8）：5487-5495.

[責(zé)任編輯：湯靜]