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

胡承剛，高建瓴，喻明豪，白羽飛，陳 楠

（貴州大學 大數據與信息工程學院，貴陽 550025）

0 引 言

遺傳算法最早由美國Michigan 大學的教授John Holland模擬生物遺傳和進化提出［1］。二十世紀80 年代，De Jong 基于遺傳算法的思想在計算機上進行數值優化實驗，歸納總結形成其基本框架。遺傳算法通過將目標函數的自變量映射為生物遺傳進化中的染色體，對染色體編碼來實現向下進化，并找到使目標函數最優的染色體；同時，遺傳過程中加入了交叉和變異操作，來優化下一代染色體。遺傳算法中染色體的編碼方式有浮點數編碼和二進制編碼兩種方式。不同的染色體編碼方式和采取的變異算子、交叉算子的差異同樣造成了遺傳算法不同［2］。由于遺傳算法是一種全概率搜索優化算法，所以其對于目標函數的性質沒有要求，比如：可微、連續等，所以在很多實際問題中都有應用，比如：數值函數尋優、多目標優化、機器學習、圖像處理，最優路徑規劃、神經網絡的訓練等。

圖像分割是區分圖像中的對象和背景的過程。對于許多依賴于計算機視覺的應用，如醫學成像、衛星圖像中的物體定位、機器視覺、手指打印和人臉識別等許多應用來說，圖像分割是一項必不可少的預處理任務。圖像分割的準確性將對圖像處理的后續階段的有效性產生很大的影響。圖像分割問題已被研究數年，但由于圖像的不同模態直方圖等特征，圖像分割問題仍是一個有待進一步研究的問題。基于深度學習的圖像分割雖然有不錯的效果，但是需要大量標注數據來訓練神經網絡；基于閾值分割的Otsu 是經典的圖像分割算法，在單閾值分割時算法效率很高，但在多閾值分割時算法的速度極低，這是由于算法會遍歷圖像的每個像素點，計算類內方差和類間方差，算法速度慢；基于遺傳算法的閾值分割可以解決多閾值圖像分割效率低的問題。

本文分析遺傳算法及其改進算法的性能，提出一種混合改進的遺傳算法，并將改進的算法先用于數值函數尋優，以測試比較改進算法的性能；對圖像閾值分割進行分析，找到最佳的閾值來分割圖像，OTSU 算法遍歷像素的操作在多閾值分割時性能下降嚴重，通過對閾值分割算法分析，使用遺傳算法來尋找最佳閾值，以分割圖像。

1 混合改進的遺傳算法

1.1 自適應遺傳算法模型

遺傳算法在多個領域的研究表明其高效性，其性能取決于在迭代的最后是否能夠在函數優化中收斂到局部或者全局最優解。標準遺傳算法（SGA）采用固定控制參數方法，即固定交叉概率和變異概率，缺點明顯，因為前后期適應度不同，所以需要的交叉、變異概率也不同。趙大興等人提出基于適應度對交叉、變異概率作出改進，改進的選擇算子會根據個體適應度之間的相似性把種群分為若干組，以組為單位進行輪盤賭選擇，在選中的組中產生新的個體［3］；陳璐等人將遺傳算法分解為兩部分，通過第一次尋優找到優秀個體，將最佳個體再次放入第二個種群中，得到最后的最優解［4］；江濤等通過在適應度函數中加入路徑平滑度來改善遺傳算法［5］；陳友青等人提出一種改進算子的遺傳算法［6］。雖然這些研究在一定程度上改善了遺傳算法的性能，但是使用固定交叉概率和變異概率的方式固化了參數，算法前期和后期染色體使用的交叉概率、變異概率一樣，算法收斂速度問題依舊沒有得到很好的解決。

針對遺傳算法參數固定帶來的問題，M.Srinvas和L.M.Patnaik 提出了自適應遺傳算法（Adaptive GA，AGA），其思想是在迭代過程中根據種群適應度來自適應的調整交叉概率和變異概率［7］。公式（1）如下：

式中，pc，pm分別表示交叉概率和變異概率；fmax為當代種群最大適應度值；表示當代種群的平均適應度值；f表示變異個體的適應度值；f ′表示交叉兩個體中較大的適應度的值；ki（i＝1，2，3，4）為常數，取值范圍0＜ki≤1。

AGA 解決了算法前期和后期適應度高的個體和適應度低個體的交叉概率、變異概率相同的缺點。但自適應遺傳算法沒有從全局出發來控制交叉概率和變異概率，所以在算法后期容易陷入局部收斂，難以找到全局最優解。針對這個問題，曲志堅等人提出在算法進化過程中使用優秀個體代替適應度差的個體［2］；劉芳等人提出基于種群多樣性的IAGA 來改善算法后期易陷入局部最優解的問題［8］；閆春等人使用反正弦函數自適應調節變異概率［9］。

通過對遺傳算法以及各種改進方式的對比研究，本文提出了混合改進遺傳算法：根據種群密度和進化代數的協同性，改進交叉概率；通過對種群密度的統計，提出基于種群密度調整變異概率。

1.2 混合改進自適應遺傳算法

1.2.1 改進交叉概率

評價算法性能指標可以用進化性來指導，更好的下一代比上一代更能適應環境變化。評價算法進化性可以使用種群的密度來衡量，本文算法中計算每一代群體密度計算方式（2）如下：

分析每一代種群密度的變化可以掌握算法性能，受改進的自適應遺傳算法（IAGA）［10］的啟發，在種群密度的基礎上加上進化代數的因素，從種群迭代次數以及種群集中程度的考量，改進交叉概率，公式（3）如下：

其中，ρ1表示當前種群的集中程度，t是當前種群的進化代數。

1.2.2 基于種群中心區域密度改進變異概率

在算法進化的后期，種群內部已經趨于相對穩定的狀態，若算法此時得到的解是局部最優，由于狀態穩定，算法難以發生實質進化和走出局部最優解，如圖1 所示。自然界中的各種生物會經歷“天災”這樣的自然災害，基于這種思考，選擇設置類似于自然界中的“天災”設定，一定程度上將舊種群初始化為新的種群，從而走出此處局部最優解，并試圖尋找下一個可能的局部最優解，從而使模型更有希望與能力達到全局最優解。算法遭遇“天災”之前，變異概率隨之下降，同時設置“天災”發生后在正常的種群中心區域密度ρ2下，密度越高時，變異概率也會隨之上升。

圖1 種群密度變化圖Fig.1 Change of population density

為計算種群中心區域的密度ρ2設定參數：M表示群體所含的個體數目；fmax為種群最大適應度；fmin表示種群最小適應度；favg表示種群平均適應度，則t代種群的范圍M（H，t）如式（4）：

某個體的適應度到群體適應度均值之間的距離m（h），式（5）：

群體中心區域的半徑σ可以表示為式（6）：

某染色體適應度到當代群體適應度均值的距離小于σ的染色體數目N（δ，f），則群體中心的密度ρ2為式（7）：

通過對種群中心區域密度的分析，對變異概率改進如式（8）：

式中，T表示最大進化次數；t表示當前進化次數；tm是經歷“天災”的某代種群。

文中設定當中心區域密度達到0.5 時，種群經歷“天災”，之后變異概率會逐漸上升，如圖2 所示。

圖2 變異概率變化曲線Fig.2 Variation curve of mutation probability

2 仿真實驗結果

本文仿真實驗基于Windows 10（x64）操作系統，Intel（R）Core（TM）i5－7500 CPU 3.40 GHz主頻，RAM8G內存。編譯環境采用MATLAB R2018a。12 個函數的形式，尋優范圍和函數最優值見表1。使用12 個測試函數來對本文改進后的算法進行仿真測試，其中函數F2、F3、F5、F7－ F11 擁有許多局部極小值，F1、F4、F6、F12 用于多維空間測試。

表1 測試函數Tab.1 Test functions

實驗對表1 中的函數在搜索空間中進行優化測試，對比算法選擇SGA 以及IAGA，SGA 參數設置：pc＝0.7、pm＝0.01；IAGA 參數設置：pc1＝0.9，pc2＝0.6，pm1＝0.1，pm2＝0.001。使用12 個函數對算法進行2 維尋優性能測試分析，函數F1、F6、F10、F12 進行30 維測試。

2.1 改進算法性能測試

在2 維情況下，將SGA，IAGA與本文算法在12個測試函數上進行試驗，3 種算法獨立求解測試函數所得收斂曲線如圖3 所示，從F1～F5 函數在算法迭代50 次尋優的曲線，可以看出本文算法在函數F1～F5 上都能近似到最優效果；同時圖3 還給出了F6～F12 函數迭代200 次的尋優效果，可以看出本文算法收斂速度明顯快于SGA 和IAGA。由圖3 可以看出，通過種群密度和迭代次數的全局考慮，以及加入類似“天災”設置的情況下，算法收斂速度快，易跳出局部最優值，而其余兩種算法則出現收斂速度慢或陷入局部最優解等問題。雖然本文算法在前期函數F3 收斂速度略劣于前兩種算法，但是在中后期收斂速度明顯高于前兩種算法，對比來看本文算法更具優勢。

圖3 測試函數適應度變化曲線Fig.3 Fitness curve of test function

2.2 收斂精度與收斂率分析

實驗使用了表1 中測試函數F1～F6，進行了50 次獨立測試，測試結果見表2。可以看出本文算法在50 次獨立實驗中收斂精度上優于其余兩種算法，收斂率（在50 多次獨立實驗中的收斂次數）也明顯高于其余兩種算法，函數F3在50 次實驗中收斂次數也高于前兩種。30 維搜索空間優化實驗中改進算法對比SGA 和IAGA在收斂速度和跳出局部最優解能力更有優勢，收斂曲線如圖4 所示。

圖4 30 維搜索空間測試結果Fig.4 Test results of 30－dimensional search space

表2 函數F1～F6在50 次獨立實驗的200 代平均值以及收斂率對比Tab.2 Comparison of average and convergence rate of function F1～F6 in 50 independent experiments with 200 generations

3 改進遺傳算法圖像分割

3.1 Otsu 圖像分割

圖像分割是計算機視覺中一個重要的研究內容，在很多領域中都是一項必不可少的圖像預處理任務。基于閾值分割的大律法（Otsu）是經典的圖像分割算法，但是在多閾值分割任務上性能很差，處理圖像時間長，所以本文使用改進遺傳算法用于閾值圖像分割。圖像閾值分割經典算法是Otsu 算法，通過尋找灰度圖像中的最佳閾值來分割圖像，雖然在單閾值分割時Otsu 算法表現不錯，但是多閾值分割時一張圖像需要處理的時間過長，算法效率太低。使用改進的遺傳算法用于圖像分割，流程圖如圖5。

圖5 改進算法用于圖像分割流程圖Fig.5 Flow chart of improved algorithm for image segmentation

單個閾值把圖像像素分為兩類，Otsu 算法通過遍歷每個像素點尋找能最大化類間方差的點，這個像素點就是最佳閾值。多閾值是在單閾值的基礎上推廣而來。若有M個閾值（t1，t2…tM）將圖像分為M＋1 類（C0，C1…CM），分割標準的度量可以使用類間方差和類內方差共同決定。類內方差盡可能小，類間方差盡可能大，衡量標準則是類間方差和類內方差比值，式（9）：

其中，Sbb是類間方差，Swo是類內方差。

選取公式（9）為適應度函數，轉換為函數尋優中的求最大值問題。灰度圖像的像素級在［0，255］之間，閾值就是灰度值，將染色體編碼為比特向量，每一個向量都有L ×M位，L是log（灰度級數），M是閾值數，則每L位表示一個染色體，如圖6 所示。

圖6 像素編碼為染色體Fig.6 The pixels are encoded as chromosomes

3.2 圖像分割實驗

Otsu 算法在多閾值分割時出現分割速度慢、抗噪性能差的缺點，采用改進的遺傳算法優化Otsu 多閾值分割，能在一定程度上克服這些不足之處，實驗結果見表3、如圖7 所示。使用原Otsu 算法、SGA、IAGA 以及本文改進的算法對圖像進行分割，傳統Otsu 算法分割效率低；遺傳算法的加入解決效率低的問題，但由圖7 的實驗結果來看，SGA、IAGA 算法還有明顯的噪聲，在細小部分分割效果差。使用遺傳算法分割圖像在單閾值和多閾值時所用時間對比見表3。

圖7 圖像分割結果Fig.7 Image segmentation results

表3 四種方法分割時間對比Tab.3 Comparison among the four methods on time consumption

4 結束語

針對標準遺傳算法在進化過程難以跳出局部最優解、收斂率較低和收斂速度慢等問題，本文通過以下兩種方式改進遺傳算法：首先，考慮種群密度和進化代數的協同性，改進交叉概率，以增強交叉概率自適應性；其次，在進化過程中又設定類似于“天災”設置，結合進化代數改進變異概率，增強種群跳出局部最優解的能力。相較于簡單遺傳算法和自適應遺傳算法，本文算法在收斂速度和收斂率上有明顯優勢，在跳出局部最優解的能力上也優于SGA 和IAGA。通過改進算法分割圖像也達到不錯的效果，相較于傳統的Otsu 算法，結合遺傳算法優化之后效果更好，在與IAGA、SGA 優化對比中，本文改進算法更具有魯棒性，抗噪能力更強。