一種改進的遺傳算法在圖像分割中的應用

王丹　周錦程

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

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

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大學的Holland于1975年提出的一種隨機自適應的全局搜索算法。它是一種通過借鑒進化論中適者生存、優勝劣汰的遺傳機制演化而來的計算模型。該算法的基本思想最先由Holland[2]在1962年提出，之后陸續有研究者提及了該算法的一些基本概念[3-6]，“遺傳算法”這個術語在1967年首先由Bagley在其博士論文中使用，但直至1975年，遺傳算法的數學框架與理論才由Holland[7]在其專著中進行了系統而詳細的表述。

早期的遺傳算法主要被用于求解函數優化問題和人工自適應系統的研究與設計。隨著遺傳算法的不斷改進與完善，它為解決復雜優化問題提供了一種嶄新且有效的思路，其良好的搜索能力得了廣大學者的關注和認可。當前，遺傳算法的應用范圍已被逐漸延伸到了組合優化、圖像處理、網絡通信、模式識別等眾多復雜優化領域。

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

1 相關概述

1.1 遺傳算法

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

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

Step 2 初始群體的生成：隨機產生N個染色體，N個染色體構成了一個種群，遺傳算法以這N個染色體作為初始點開始迭代。

Step 3 個體評價：用適應值函數刻畫個體的優劣性。通常，針對不同的優化問題，需要設計不同的適應性函數。

Step 4 選擇運算：按照一定的規則從當前群體中選出優良的個體，其主要思想來自于達爾文的適者生存原則。

Step 5 交叉運算：新個體通過交叉操作獲得且繼承其父輩個體的特征，交叉體現了信息交換的思想。

Step 6 變異操作：將變異算子作用于新群體中的少部分個體，對這部分個體的染色體以一定的概率隨機地改變染色體中某些基因的編碼，變異是為了在群體中引入新的變種，確保種群的多樣性。

1.2 圖像分割

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

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

2 改進遺傳算法的圖像分割

2.1 二維最大熵圖像分割法

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

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

2.2 改進遺傳算法的圖像分割方法

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

（1）采用均勻分布隨機產生初始化種群。

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

（3）采用二維熵圖像分割法中的圖像的總熵H（s，t）作為我們算法的適應度評價函數。

（4）采用輪盤賭法和精英策略相結合的方案對染色體進行選擇操作。

（5）采用隨機產生的多個交叉點的方式進行多點交叉操作。

（6）采用隨機隨機按位取反的方式對個體進行變異操作。

（7）采用收斂程度和最大進化代數結合的停機策略，即終止條件為達到最大進化代數gmax，或者當前群體的平均適應度值與上一代群體的平均適應度值的絕對差小于ε。算法終止時，具有最高適應度值的個體作為最佳閾值。

本文構造改進遺傳算法的圖像分割方法的計算流程如下：

Step 1 設定種群數目N，對二維閾值進行二進制編碼，并隨機產生初始種群。

Step 2 對初始種群解碼，并根據式（2），式（3）和式（4）計算每個基因串的適應度值。

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

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

3 實驗結果及分析

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

4 結語

遺傳算法是一種獨立于問題領域且具有快速隨機搜索能力的隨機算法，該算法通過模擬自然進化過程搜索最優解，（下轉第117頁）（上接第109頁）其對全局信息的有效搜索能力，使得該方法只需檢測少量的結構就能反映搜索空間較大的區域，并能獲得較為穩定的最優解。由于傳統的二維最大熵法實質上是在二維灰度空間上搜索參數從而使圖像的總熵取得最大值，因此算法的計算量較大、耗時長。因此，本文結合二維最大熵法的特點，將二維最大熵的圖像閾值分割法中的相關技術引入到遺傳算法中，并設計了相應遺傳算法的選擇、交叉、變異等算子。實驗結果表明，我們所提出的算法能有效提高圖像分割的速度且能獲得較好的分割結果。

【參考文獻】

[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].北京：科學出版社，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].物理學報，2010，59（8）：5487-5495.

[責任編輯：湯靜]