基于改進差分演化的高效圖像分割算法

摘 要： 差分演化算法的實現簡單有效，但其搜索能力較弱，對此提出一種基于貝塔分布的控制參數動態設置策略以提高差分演化的優化效果，并將其應用于圖像分割問題。首先，將圖像的直方圖按強度分為兩類，并按類內方差、類間方差與總方差總結為待優化的目標函數；然后，使用改進的差分演化算法搜索圖像分割目標函數的最優解，其中在每輪迭代中使用貝塔分布動態的設置控制參數。仿真實驗表明，該方法獲得了較好的優化結果，并獲得了較好的圖像分割效果。

關鍵詞： 貝塔分布； 差分演化； 圖像分割； 閾值化分割； 控制參數

中圖分類號： TN911.73?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2016）14?0087?05

High efficient image segmentation algorithm based on improved differential evolution

FAN Zehua， BAI Tiecheng

（College of Information Engineering， Tarim University， Alar 843300， China）

Abstract： The differential evolution algorithm is effective and easy to realize， but it has poor search ability， so a control parameter dynamic setting strategy based on beta distribution is proposed to improve the optimization effect of the differential evolution， and applied to the image segmentation. In the scheme， the image histograms are divided into two classes according their intensity， and summarized to the waiting optimization target function according to the inner?class variance， inter?class variance and total variance. And then， the improved differential evolution algorithm is used to search the optimal solution of the image segmentation target function， in which the beta distribution is used to set the control parameters dynamically in each iteration. The simulation experiment results show that the proposed method can obtain better optimal result and good image segmentation effect.

Keywords： beta distribution； differential evolution； image segmentation； thresholding segmentation； control parameter

0 引 言

圖像分割是圖像處理領域中最基礎的圖像分析方法之一，其主要目標是將圖像劃分為若干個相關性較低的區域，從而做后續的進一步分析[1?2]。基于閾值的圖像分割方法是一種極為重要的方法，目前已有大量的研究對傳統閾值圖像分割方法進行了改進，并且獲得了較好的效果。隨著人工智能的迅速發展，許多研究引入智能優化技術搜索圖像分割的最優組合解或者帕累托解，極大地提高了圖像分割的效果[3]。已有較多的文獻分別引入不同的人工智能方法對圖像分割進行處理，均取得了較好的效果，其中包括遺傳算法[4]、粒子群[5]、細菌覓食算法[6]、布谷鳥搜索[7]、蜂群優化[8]等。

DE（差分演化）[9]是一種模擬生物進化的隨機模型，通過反復迭代，使得那些適應環境的個體被保存了下來。但相比于進化算法，DE保留了基于種群的全局搜索策略，采用實數編碼、基于差分的簡單變異操作和一對一的競爭生存策略，降低了遺傳操作的復雜性[10]。DE的性能主要依賴兩個要素：試驗向量生成策略，包括變異與交叉操作；控制參數：種群大小（NP），縮放因子（F）和交叉率（CR）。本文改進的差分演化方法在每輪迭代中采用貝塔分布來動態地調節[F]與[CR]控制參數以期提高差分演化算法的優化效果。本文將改進的差分演化方法應用于直方圖閾值化分割問題中，貝塔分布使得控制參數出現取值范圍兩級的頻率更高，因此每輪迭代中控制參數選擇極值的概率較高，提高了差分演化的優化性能，并且獲得的圖像分割效果優于其他的分割方法。

1 差分演化

本文基于文獻[9]的差分演化版本，其主要步驟如下：

步驟1（控制參數定義）：設置DE的控制參數，即[NP]，[F]，[CR]與結束條件[tmax]；

步驟2（初始化種群）：為了初始化一個種群（解向量），在第一代將所有的個體隨機、均勻地分布，將當前迭代次數設為[t=1]。

步驟3（目標函數評價）：計算種群中每個個體的目標函數值，將目標函數作為適應度函數。

步驟4（變異操作）：生成變異向量最簡單的方法是將縮放因子[F]乘以兩個隨機向量的差分值，將結果與第三個隨機向量相加。該變異方法如下：

式中：序號[i，r1，r2，r3∈1，2，…，NP]表示種群中個體的序號；[t]表示迭代次數；[xi（t）=xi1（t），xi2（t），…，xin（t）T]表示[n]維的向量中第[i]個個體的位置。向量[zi（t）=zi1（t），zi2（t），…，zin（t）T]代表變異向量的第[i]個個體的位置。

步驟5（交叉操作）：交叉操作的目的是將當代的成員混合以生成一個新的后代。一般的指數交叉中，首先在范圍[1，[D]]中隨機選擇一個整數[n]，將該整數作為目標向量中的一個起始點，作為交叉向量的開始位置；同時從范圍[1，[D]]中選擇另一個整數[L]，[L]表示目標向量中所包含的供體向量中元素的數量。然后根據給定的交叉率[CR]可獲得試驗向量[ui（t+1）]。

步驟6（選擇操作）：選擇操作決定是否將本輪迭代的試驗向量代替下一代的解。將向量[ui（t+1）]對應的適應度值與[xi（t）]對應的適應度值相比較，假設[f]表示目標函數，選擇操作可表示如下：

步驟7（結束條件）：檢查結束條件，如果滿足結束條件，則結束收斂過程；否則，增加迭代次數[t=t+1]，然后轉至步驟3。

1.1 本文改進的差分演化方法

[F]的作用是控制探索向量的長度[xr2（t）-xr3（t）]，決定所生成的后代與點[xr1（t）]的距離；在原DE中，[F]的范圍是（0，2]。CR主要作用是控制種群的多樣性，CR取值主要依賴問題的性質，因此對于非可分目標函數或者多模態函數的優化，CR取值0.9～1之間較為合適；而對于可分目標函數，CR取值0～0.2較為合適。

原DE在步驟4與步驟5中分別使用常量[F]與CR，為了提高DE算法的性能，本文基于貝塔概率分布[11]對[F]與CR參數進行動態的調節，[0，1]區間內貝塔分布的概率密度為：

式中：均值等于[a（a+b）]，方差為[a（a+b）2（a+b+1）]；[Γ（·）]表示伽瑪函數?？煽闯鯷a]與[b]的值決定了密度函數的形狀，如果是對稱的分布，則[a]與[b]的值是相同的。在本文中，采用Matlab的命令betarnd（a，b，1）生成貝塔分布，在本文的改進DE中，[F]與CR值的生成腳本見表1。

注：[rand]在[0，1]區間生成均勻的偽隨機數

如圖1所示是一次實驗中本方法所獲得的一組[F]與CR值的頻率分布，從中可看出貝塔分布使得[F]與CR出現取值范圍兩級的頻率更高，因此每輪迭代中控制參數選擇極值的概率較高，由此增強了搜索性能。

獲得的[F]與[CR]值的頻率分布

2 圖像分割

本文圖像分割基于直方圖多級閾值化的分割方法，其中閾值采用Otsu優化方法[12]。

假設一個圖像的直方圖為[f（x，y）]，其強度值范圍是[0，L-1]，其中[（x，y）]是一個像素的卡迪爾坐標，[L-1]是最大的強度值，其計算方法為[h（rk）=nk]，其中，[rk]表示第[k]個強度值；[nk]表示強度為[rk]的像素數量。假設[g（x，y）]表示[f（x，y）]的圖像分割結果，如果閾值為[NT]，結果圖像表示如下：

閾值的定義為[Ti，i=1，2，…，NT]，Otsu方法的基本思想是使用一個閾值將像素劃分為兩組，并計算兩組之間的方差，Otsu方法基于像素出現在直方圖與正態曲線的概率對圖像進行較好地分割。假設圖像的強度共有[N]級，[pi]表示出現在圖像中第[i]個強度等級的概率，可得：

[pi=niN， N=i=1Lni] （5）

考慮兩個像素分類[C0]與[C1]，分別為背景與前景像素類，其閾值設為[k]。因此[C0]對應的像素強度范圍是[1，2，…，k]，[C1]對應的像素強度范圍是[[k+1，][k+2，]…，L]。[C0]與[C1]類的概率計算如下：

上述步驟將閾值選擇的問題歸總為一個閾值[k]的選擇問題，即最終需要優化一個指標組合[（λ；K；η）]。基于Otsu準則，將圖像分割問題作為優化程序，可得本文的優化目標函數：

圖像分割的目標是求式（15）的最大值。而對于RGB圖像，則需要對三個顏色通道分別分割三次即可實現彩色圖像的分割。

3 實驗與結果分析

3.1 Benchmark

如圖2所示是本文的實驗圖像。其中X光片與彩色圖像是Electrophysics公司技術文檔中的一幅圖像。

3.2 結果與分析

為了橫向評估本文分割算法的性能，將本文方法與FODPSO[5]進行比較。本文的差分演化算法種群大小為80，結束條件為40次迭代。為了處理整型的決策變量，將所有的解四舍五入轉化為整型。

第一組實驗：本組實驗兩種分割算法均設置6個閾值，如圖3所示是本文方法與FODPSO兩種方法對公共圖像Peppers與Lena的分割結果，可看出本方法對灰度圖像的分割效果優于FODPSO算法。

第二組實驗：為了研究閾值數量對本文算法性能的影響，將本方法的閾值數量分別設為2～6，圖4所示是彩色圖像的實驗結果，可明顯看出，本算法優于FODPSO算法，而閾值數量越多，本方法的性能優勢愈發明顯。

表2～表4所示是兩種優化方法的結果統計。表2與表4所示是30次獨立實驗所統計的目標函數值，其中每次獨立實驗的初始化種群均為隨機產生。將兩種算法的閾值數量均設為2～6，對于每個閾值范圍，表3統計了每組獨立實驗的最優結果。

從表2、表4可看出，由于閾值數量增加，決策變量數量隨之增加，因此本文對于復雜問題具有較好的性能?？傮w而言，本方法的圖像分割效果優于FODPSO算法。

4 結 論

本文將改進的差分演化方法應用于直方圖閾值化分割問題中，貝塔分布使得差分演化模型中控制參數出現取值范圍兩級的頻率更高，因此在每輪迭代中控制參數選擇極值的概率較高，由此增強了差分演化的搜索性能。本文在每輪迭代中采用貝塔分布動態地調節控制參數以期提高差分演化算法的優化效果，對比實驗結果表明，本方法提高了差分演化優化的搜索性能，并且獲得了較好的圖像分割效果。

參考文獻

[1] 劉松濤，殷福亮.基于圖割的圖像分割方法及其新進展[J].自動化學報，2012，38（6）：911?922.

[2] 張志斌，羅錫文，臧英，等.基于顏色特征的綠色作物圖像分割算法[J].農業工程學報，2011，27（7）：183?189.

[3] OSUNA?ENCISO V， CUEVAS E， SOSSA H. A comparison of nature inspired algorithms for multi?threshold image segmentation [J]. Expert systems with applications， 2013， 40（4）： 1213?1219.

[4] MANIKANDAN S， RAMAR K， IRUTHAYARAJAN M W， et al. Multilevel thresholding for segmentation of medical brain images using real coded genetic algorithm [J]. Measurement， 2014， 47（1）： 558?568.

[5] GHAMISI P， COUCEIRO M S， BENEDIKTSSON J A， et al. An efficient method for segmentation of images based on fractional calculus and natural selection [J]. Expert systems with applications， 2012， 39（16）： 2407?2417.

[6] SATHYA P D， KAYALVIZHI R. Modified bacterial foraging algorithm based multilevel thresholding for image segmentation [J]. Engineering applications of artificial intelligence， 2011， 24（4）： 595?615.

[7] BHANDARI A K， SINGH V K， KUMAR A， et al. Cuckoo search algorithm and wind driven optimization based study of satellite image segmentation for multilevel thresholding using Kapur’s entropy [J]. Expert systems with applications， 2014， 41（7）： 3538?3560.

[8] 阿里木·賽買提，杜培軍，柳思聰.基于人工蜂群優化的二維最大熵圖像分割[J].計算機工程，2012，38（9）：223?225.

[9] COELHO L D S， MARIANI V C， LEITE J V. Solution of Jiles?Atherton vector hysteresis parameters estimation by modified differential evolution approaches [J]. Expert systems with applications， 2012， 39（2）： 2021?2025.

[10] 孟紅云，張小華，劉三陽.用于約束多目標優化問題的雙群體差分進化算法[J].計算機學報，2008，31（02）：228?235.

[11] BALAKRISHNAN N， KOTZ S， JOHNSON N L. Continuous univariate distributions [M]. New York： Wiley?Interscience， 1996： 119.

[12] OHTSU N. A threshold selection method from gray?level histograms [J]. IEEE transactions on systems man cybernetics， 1979， 9（1）： 62?66.

[13] PANDA R， AGRAWAL S， BHUYAN S. Edge magnitude based multilevel thresholding using cuckoo search technique [J]. Expert systems with applications， 2013， 40（18）： 7617?7628.