基于遺傳模擬退火算法的Otsu圖像分割研究

劉紫燕，吳俊熊，毛　攀，帥　暘

(貴州大學　大數據與信息工程學院，貴州 貴陽 550025)

?

基于遺傳模擬退火算法的Otsu圖像分割研究

劉紫燕，吳俊熊，毛攀，帥暘

(貴州大學大數據與信息工程學院，貴州 貴陽 550025)

針對目前基本遺傳算法在優化圖像分割算法中存在的易于早熟、陷入局部最優的不足，以最大類間方差函數為適應度函數，提出了一種基于改進遺傳算法的圖像閾值分割算法。對交叉、變異算子進行自適應改進，同時將模擬退火算法融入到遺傳算法中，使得對個體的評價更合理，既能克服種群退化現象，又改善算法的全局搜索能力，避免遺傳算法陷入局部最優。實驗結果顯示，與Otsu圖像分割法以及基于遺傳算法的圖像分割方法相比，使用該方法得出的閾值范圍更加穩定，執行效率更高，在圖像分割中獲得的分割效果更佳。

圖像分割；最大類間方差；遺傳算法；模擬退火算法

圖像分割[1](Image Segmentation)是圖像處理領域不可或缺的重要步驟，長期以來受到專家學者的重視和研究，更在工程實踐中得到廣泛運用。常用的圖像分割方法主要有三類：閾值分割法、邊緣檢測法和區域分割法等。其中閾值分割法由于實現的簡單性而成為圖像分割領域的一種重要方法[2]。但是，如何合理選擇閾值，獲得更佳的圖像分割效果，一直以來都是學者需要解決的問題。目前常用的閾值法存在以下缺點：最小誤差法[3]計算量大，不利于處理實時圖像，而且僅對小目標圖像具有好的分割效果；最大信息熵法[4]雖使圖像的信息量丟失最小，但因引入對數運算，其數學計算量相當龐大；二維閾值算法[5]圖像分割效果雖好，但計算量是以指數增長，運行時間較長；最大類間方差法對單峰的圖像分割效果很好，但實際上，多數圖像并不是簡單的單峰，若僅僅利用Otsu準則進行目標分割，很難得到穩定可靠的分割結果。因此，為了解決上述問題，研究者們提出將遺傳算法和Otsu法結合在一起使用。

文獻[6]利用遺傳算法能夠改善傳統閾值分割方法的分割效率，但由于基本遺傳算法存在收斂性差、容易早熟等特點，給尋找準最優解帶來很大困難。因此本篇文章對基本遺傳算法進行優化，介紹一種改進的遺傳算法與Otsu法則結合的算法。

1　Otsu閾值法

l979年，Otsu提出了一種閾值分割方法，該算法計算簡單，不受圖像對比度和亮度的影響。它主要是通過最大類間方差準則[7]來確定區域分割門限。其基本原理是任意選取某一灰度值為閾值門限將圖像劃分為兩大類，計算兩類灰度分布的方差。若差值越大，即表示目標和背景之間的區別更加明顯，差值達到最大時的灰度值就是最佳閾值。其基本過程可以描述如下：

(1)

(2)式中：Ps0和Ps1分別為s0類和s1類對應灰度值i在(0,1,…,t)和(t+1,t+2,…,L-1)出現的概率之和。

s0類和s1類的灰度均值分別為

(3)

(4)

式中：μs0和μs1分別為s0類和s1類的灰度均值。

那么圖像整體的灰度均值為

(5)

s0類和s1類的類間方差即Otsu法準則函數為

F(t)=Ps0(μs0-μ)2+Ps1(μs1-μ)2=

Ps0Ps1(μs0-μs1)2

(6)

式中：F(t)為s0類和s1類的類間方差函數。

方差度量的是灰度分布的均勻性，所以方差越大，表示圖像的兩部分灰度分布差別越大，即灰度分布越廣泛，若目標中一部分被誤分到背景中或背景中出的一部分被誤分到目標中，均會造成兩部分灰度差別變小。因此，要使錯分概率達到最小就要求類間方差達到最大。

2基于遺傳模擬退火算法的Otsu閾

值分割

2.1基于遺傳算法的Otsu閾值分割

遺傳算法[8]是一種在計算機上模擬生物自然選擇和進化的尋優搜索算法，具有高度并行、自適應、隨機等特點。主要通過模擬自然進化中的基因選擇、交叉和突變現象來完成搜索過程。

由于遺傳算法具有快速尋優的功能，而Otsu法計算最佳閾值的過程本質上是求取最優解的過程，因此，將遺傳算法和Otsu法結合在一起，可以達到提高計算效率的目的。本節主要是利用遺傳算法對Otsu法求解圖像的最佳分割閾值的過程進行優化，如圖1所示為圖像分割的整體實現過程。

圖1　遺傳算法閾值分割實現流程

在傳統的遺傳算法中，交叉率和變異率都是預先設定的，這樣得出的結果不能顯示出群體適應度的變化，最終可能導致收斂速度變得比較緩慢的情況。因此，為了避免發散或陷入局部最優，要保持群體較好的多樣性，這就需要自適應地調整pc和pm。所以，在自適應遺傳算法中[9]，可以利用如下公式對pc和pm進行自動調整

(7)

(8)

式中：k1和k2是0～1之間的調整系數；Fmax為種群中最大適應度值；F′為交叉操作兩個體中較大適應度值；Fav為群體平均適應度值；Fm為待變異個體的適應度值。

從式(7)、式(8)可以看出，個體適應度值高的解可以降低pc和pm的值，個體適應度值的解可以增大pc和pm的值。也就是說，當高適應度值的解加快遺傳算法收斂的同時，低適應度值的解卻可以規避GA陷入局部最優。

2.2基于遺傳模擬退火算法Otsu圖像閾值分割

雖然基于遺傳算法的Otsu法在方差計算次數和所用時間上比傳統Otsu法明顯減少,但在實際中，由于基本遺傳算法存在收斂能力差、容易早熟和其他不足，對圖像分割的閾值尋優帶來很大的困難，因此，如何極大地改善收斂速度和解決早熟已經成為至關重要的問題。而另一方面，模擬退火[10](SA)具有很強的局部搜索能力，對于這個特點，若能夠將SA算法融入到遺傳算法中，就可以提高遺傳算法的運行效率和求解質量。針對這些情況，根據圖像分割算法的特點，優化基本遺傳算法，提出一種閾值分割效果更佳的改進遺傳分割算法——遺傳模擬退火算法。

遺傳模擬退火算法是遺傳算法和模擬退火算法共同組合構成的一種優化算法，可以克服各自的不足，實現優勢互補。它是以遺傳算法為主體，將模擬退火算法融入其中。

下面是具體算法描述：

步驟1，給定初始化種群規模N，初始溫度T0，降溫衰減因子α，隨機產生初始種群。

步驟2，在當前溫度Ti執行如下操作。直至產生下一代新的群體：

1)利用式(6)，求取群體中每個個體的適應度值；

2)從群體中任意選取兩個個體xi和xj，進行交叉操作，交叉率依據式(7)，產生兩個新個體，分別求取其適應度值，然后計算出新舊個體的適應度值差，若差值大于0，則一定接收新個體，若差值小于0，則以一定概率exp{-[F(x′)-F(x)]/Ti}接收新個體；

3)進行變異操作，變異概率依式(8)進行，產生新個體x′后，同樣，新舊個體差值若大于0，則一定接收新個體，若差值小于0，則以概率exp{-[F(x′)-F(x)]/Ti}接收變異后的個體。

步驟3，當滿足收斂條件時，即Ti≤Tfinal時，算法終止；否則，繼續退火操作，Ti+1=αTi，轉至步驟2。

3　仿真結果及分析

本文利用MATLAB R2014b平臺進行編程，選擇經典圖像Rice和Lena作為測試，其分辨率為256×256，灰度級也是256。分別利用最大類間方差法、基于遺傳算法的Otsu閾值分割和基于遺傳模擬退火算法的Otsu閾值分割3種算法對圖像進行實驗測試，實驗結果如圖2、圖3以及表1、表2所示。

圖2　原圖及3種分割算法結果

圖3　Lena原圖及3種分割算法結果

測試最大類間方差法遺傳算法本文算法閾值時間/s閾值時間/s閾值時間/s11250.18801210.11001270.078021250.20301290.14101270.094031250.21901290.12501250.0790均值1250.20331260.12531260.0840

表2Lena圖像分割閾值與運行時間比較

測試最大類間方差法遺傳算法本文算法閾值時間/s閾值時間/s閾值時間/s11000.25001000.17901020.109021000.2810980.19001040.110031000.21801000.17501020.0939均值1000.2497990.18131030.1043

從圖2和圖3的仿真結果可以看到，遺傳模擬退火算法分割的結果是最佳的，從肉眼可以看出，它的噪聲最小，丟失的信息量最小，該算法更好地突出了感興趣的區域，體現出大米、人臉、頭發、帽子與背景的區別，圖像的細節得到更多的體現。基于遺傳算法的閾值分割法雖然較基本Otsu法有所改善，但是仍存在少量的噪聲，信息量丟失也較嚴重。

表1和表2是使用3種算法分別對Rice圖和Lena圖的閾值和運行時間的對比圖。閾值方面，由于遺傳算法具有隨機性，尋得的最優解可能不是準最優解，但一般都會在其附近；算法執行效率方面，最大類間方差法運行時間是最長的，隨著算法的逐步改進，執行效率越來越高，本文提出的遺傳模擬退火算法執行效率是最高的。在表1中遺傳模擬退火算法比遺傳算法平均縮短了大約40 ms，比Otsu法平均縮短了119 ms。在表2中遺傳模擬退火算法比遺傳算法平均縮短了大約77 ms，比Otsu法平均縮短了145 ms。因此，本文提出的算法在執行效率上有較大提高。

4　結束語

本文在研究最大類間方差法的基礎上，利用遺傳算法對最大類間方差函數進行了全局優化，然后將交叉概率和變異概率的計算公式進行自適應改進，防止陷入局部最優解，同時將模擬退火算法融合到遺傳算法當中，避免了種群退化現象，很好地改善了算法全局收斂的穩定性，保證了算法初期種群的多樣性，改善了后期較優個體的適應度。實驗結果表明，本文提出的基于遺傳模擬退火的閾值分割方法，相對于基本Otsu法和基于遺傳算法的閾值分割法而言，能夠大大縮短尋找閾值的時間，提高圖像分割的質量，使得感興趣區域信息量丟失最小，從而獲得更好的分割效果，同時也便于計算機視覺的后續處理。因此，將遺傳模擬退火算法用來處理圖像分割問題，具有一定的應用前景。

[1]章毓晉.圖像分割[M].北京：清華大學出版社，2001.

[2] CHENG Y B. The research on application of image segmentation upon bi-level threshold algorithm[J]. Advances in information sciences and service sciences，2012，4(3)：52-58.

[3] 龍建武，申鉉京，陳海鵬.自適應最小誤差閾值分割算法[J].自動化學報，2012，38(7)：1134-1144.

[4] WANG W Y，WANG F M. Maximum entropy method of image segmentation based on genetic algorithm[J]. Computer simulation，2011，28(8)：291-294.

[5] 何春華，胡迎春.基于改進遺傳算法的自動閾值圖像分割方法[J].計算機仿真，2011，28(2)：312-315.

[6] 劉秋生，楚來國，楊繼昌.基于遺傳優化的閾值選取方法[J].信號處理，2002，18(4)：374-377.

[7] 祁佳，劉紫燕.基于融合及形態學的自適應閾值圖像邊緣檢測[J].電視技術，2014，38(13)：36-38.

[8] WANG F J，LI J L，LIU S W，et al. An improved adaptive genetic algorithm for image segmentation and vision alignment used in microelectronic bonding[J]. IEEE transactions on mechatronics，2014，19(3)：916-923.

[9] 李康順，李茂民，張文生.一種基于改進遺傳算法的圖像分割方法[J].計算機應用研究,2009，26(11)：4364-4367.

[10] YANG Y F，WANG Y P. Simulated annealing spectral clustering algorithm for image segmentation[J]. Systems engineering and electronics，2014，25(3)：514-522.

劉紫燕(1977— )，女，碩士生導師，主要研究方向為無線通信、嵌入式通信；

吳俊熊(1991— )，碩士生，主要研究方向為壓縮感知技術、圖像重構；

毛攀(1991— )，碩士生，主要研究方向為協作通信、資源分配；

帥暘(1990— )，碩士生，主要研究方向為數字通信與信息系統。

責任編輯：時雯

Image segmentation on genetic simulated annealing algorithm

LIU Ziyan，WU Junxiong，MAO Pan，SHUAI Yang

(CollegeofBigDataandInformationEngineering，GuizhouUniversity，Guiyang550025，China)

To address some defects which basic genetic algorithm is exploded in this day and age，such as easy precocious and local optimum in optimizing image segmentation，the image threshold segmentation algorithm based on improved genetic algorithm is proposed in this article with considering Otsu as fitness function. The cross and mutation operators are optimized adaptively while the simulated annealing algorithm is fused into genetic algorithm. And then， individual evaluation is more rational. Not only can population degradation be overcome， but global search performance of the algorithm can be enriched by utilizing the optimized algorithm. The experimental result indicates that threshold range keeps more stable and operating efficiency is better，compared with Otsu and the basic genetic algorithm. As a result，the obtained image segmentation effect is more apparent and perfect.

image segmentation；Otsu；genetic algorithm；simulated annealing algorithm

TP391

A

10.16280/j.videoe.2016.08.003

國家自然科學基金項目(61263005)；貴州省軟科學研究項目(黔科合R字[2014]2025號)

2016-01-14

文獻引用格式：劉紫燕，吳俊熊，毛攀,等.基于遺傳模擬退火算法的Otsu圖像分割研究[J].電視技術，2016，40(8)：15-18.

LIU Z Y，WU J X，MAO P, et al.Image segmentation on genetic simulated annealing algorithm[J].Video engineering，2016,40(8)：15-18.