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

(貴州大學(xué)　大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽(yáng) 550025)

?

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

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

(貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽(yáng) 550025)

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

圖像分割；最大類(lèi)間方差；遺傳算法；模擬退火算法

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

文獻(xiàn)[6]利用遺傳算法能夠改善傳統(tǒng)閾值分割方法的分割效率，但由于基本遺傳算法存在收斂性差、容易早熟等特點(diǎn)，給尋找準(zhǔn)最優(yōu)解帶來(lái)很大困難。因此本篇文章對(duì)基本遺傳算法進(jìn)行優(yōu)化，介紹一種改進(jìn)的遺傳算法與Otsu法則結(jié)合的算法。

1　Otsu閾值法

l979年，Otsu提出了一種閾值分割方法，該算法計(jì)算簡(jiǎn)單，不受圖像對(duì)比度和亮度的影響。它主要是通過(guò)最大類(lèi)間方差準(zhǔn)則[7]來(lái)確定區(qū)域分割門(mén)限。其基本原理是任意選取某一灰度值為閾值門(mén)限將圖像劃分為兩大類(lèi)，計(jì)算兩類(lèi)灰度分布的方差。若差值越大，即表示目標(biāo)和背景之間的區(qū)別更加明顯，差值達(dá)到最大時(shí)的灰度值就是最佳閾值。其基本過(guò)程可以描述如下：

(1)

(2)式中：Ps0和Ps1分別為s0類(lèi)和s1類(lèi)對(duì)應(yīng)灰度值i在(0,1,…,t)和(t+1,t+2,…,L-1)出現(xiàn)的概率之和。

s0類(lèi)和s1類(lèi)的灰度均值分別為

(3)

(4)

式中：μs0和μs1分別為s0類(lèi)和s1類(lèi)的灰度均值。

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

(5)

s0類(lèi)和s1類(lèi)的類(lèi)間方差即Otsu法準(zhǔn)則函數(shù)為

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

Ps0Ps1(μs0-μs1)2

(6)

式中：F(t)為s0類(lèi)和s1類(lèi)的類(lèi)間方差函數(shù)。

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

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

值分割

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

遺傳算法[8]是一種在計(jì)算機(jī)上模擬生物自然選擇和進(jìn)化的尋優(yōu)搜索算法，具有高度并行、自適應(yīng)、隨機(jī)等特點(diǎn)。主要通過(guò)模擬自然進(jìn)化中的基因選擇、交叉和突變現(xiàn)象來(lái)完成搜索過(guò)程。

由于遺傳算法具有快速尋優(yōu)的功能，而Otsu法計(jì)算最佳閾值的過(guò)程本質(zhì)上是求取最優(yōu)解的過(guò)程，因此，將遺傳算法和Otsu法結(jié)合在一起，可以達(dá)到提高計(jì)算效率的目的。本節(jié)主要是利用遺傳算法對(duì)Otsu法求解圖像的最佳分割閾值的過(guò)程進(jìn)行優(yōu)化，如圖1所示為圖像分割的整體實(shí)現(xiàn)過(guò)程。

圖1　遺傳算法閾值分割實(shí)現(xiàn)流程

在傳統(tǒng)的遺傳算法中，交叉率和變異率都是預(yù)先設(shè)定的，這樣得出的結(jié)果不能顯示出群體適應(yīng)度的變化，最終可能導(dǎo)致收斂速度變得比較緩慢的情況。因此，為了避免發(fā)散或陷入局部最優(yōu)，要保持群體較好的多樣性，這就需要自適應(yīng)地調(diào)整pc和pm。所以，在自適應(yīng)遺傳算法中[9]，可以利用如下公式對(duì)pc和pm進(jìn)行自動(dòng)調(diào)整

(7)

(8)

式中：k1和k2是0～1之間的調(diào)整系數(shù)；Fmax為種群中最大適應(yīng)度值；F′為交叉操作兩個(gè)體中較大適應(yīng)度值；Fav為群體平均適應(yīng)度值；Fm為待變異個(gè)體的適應(yīng)度值。

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

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

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

遺傳模擬退火算法是遺傳算法和模擬退火算法共同組合構(gòu)成的一種優(yōu)化算法，可以克服各自的不足，實(shí)現(xiàn)優(yōu)勢(shì)互補(bǔ)。它是以遺傳算法為主體，將模擬退火算法融入其中。

下面是具體算法描述：

步驟1，給定初始化種群規(guī)模N，初始溫度T0，降溫衰減因子α，隨機(jī)產(chǎn)生初始種群。

步驟2，在當(dāng)前溫度Ti執(zhí)行如下操作。直至產(chǎn)生下一代新的群體：

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

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

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

步驟3，當(dāng)滿(mǎn)足收斂條件時(shí)，即Ti≤Tfinal時(shí)，算法終止；否則，繼續(xù)退火操作，Ti+1=αTi，轉(zhuǎn)至步驟2。

3　仿真結(jié)果及分析

本文利用MATLAB R2014b平臺(tái)進(jìn)行編程，選擇經(jīng)典圖像Rice和Lena作為測(cè)試，其分辨率為256×256，灰度級(jí)也是256。分別利用最大類(lèi)間方差法、基于遺傳算法的Otsu閾值分割和基于遺傳模擬退火算法的Otsu閾值分割3種算法對(duì)圖像進(jìn)行實(shí)驗(yàn)測(cè)試，實(shí)驗(yàn)結(jié)果如圖2、圖3以及表1、表2所示。

圖2　原圖及3種分割算法結(jié)果

圖3　Lena原圖及3種分割算法結(jié)果

測(cè)試最大類(lèi)間方差法遺傳算法本文算法閾值時(shí)間/s閾值時(shí)間/s閾值時(shí)間/s11250.18801210.11001270.078021250.20301290.14101270.094031250.21901290.12501250.0790均值1250.20331260.12531260.0840

表2Lena圖像分割閾值與運(yùn)行時(shí)間比較

測(cè)試最大類(lèi)間方差法遺傳算法本文算法閾值時(shí)間/s閾值時(shí)間/s閾值時(shí)間/s11000.25001000.17901020.109021000.2810980.19001040.110031000.21801000.17501020.0939均值1000.2497990.18131030.1043

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

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

4　結(jié)束語(yǔ)

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

[1]章毓晉.圖像分割[M].北京：清華大學(xué)出版社，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] 龍建武，申鉉京，陳海鵬.自適應(yīng)最小誤差閾值分割算法[J].自動(dòng)化學(xué)報(bào)，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ìn)遺傳算法的自動(dòng)閾值圖像分割方法[J].計(jì)算機(jī)仿真，2011，28(2)：312-315.

[6] 劉秋生，楚來(lái)國(guó)，楊繼昌.基于遺傳優(yōu)化的閾值選取方法[J].信號(hào)處理，2002，18(4)：374-377.

[7] 祁佳，劉紫燕.基于融合及形態(tài)學(xué)的自適應(yīng)閾值圖像邊緣檢測(cè)[J].電視技術(shù)，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ìn)遺傳算法的圖像分割方法[J].計(jì)算機(jī)應(yīng)用研究,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— )，女，碩士生導(dǎo)師，主要研究方向?yàn)闊o(wú)線通信、嵌入式通信；

吳俊熊(1991— )，碩士生，主要研究方向?yàn)閴嚎s感知技術(shù)、圖像重構(gòu)；

毛攀(1991— )，碩士生，主要研究方向?yàn)閰f(xié)作通信、資源分配；

帥暘(1990— )，碩士生，主要研究方向?yàn)閿?shù)字通信與信息系統(tǒng)。

責(zé)任編輯：時(shí)雯

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

國(guó)家自然科學(xué)基金項(xiàng)目(61263005)；貴州省軟科學(xué)研究項(xiàng)目(黔科合R字[2014]2025號(hào))

2016-01-14

文獻(xiàn)引用格式：劉紫燕，吳俊熊，毛攀,等.基于遺傳模擬退火算法的Otsu圖像分割研究[J].電視技術(shù)，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.