基于遺傳算法的圖像閾值分割的研究

周愛(ài)霞+李春貴+陶佳偉

摘要：圖像閾值分割技術(shù)在圖像分析和圖像識(shí)別中有著重要的意義。目前在實(shí)際應(yīng)用領(lǐng)域中，現(xiàn)有的圖像閾值分割算法存在著如目標(biāo)輪廓模糊，耗時(shí)性，或一些重要細(xì)節(jié)被忽視掉等問(wèn)題。針對(duì)這些問(wèn)題該文展開(kāi)了研究，重點(diǎn)研究了圖像閾值分割法中經(jīng)典算法最大類(lèi)間方差（Otsu）算法。為了解決 Otsu 算法用時(shí)長(zhǎng)這一問(wèn)題，該文結(jié)合遺傳算法以及它的特點(diǎn)，將遺傳算法用于Otsu的圖像分割方法中并對(duì)閾值進(jìn)行尋優(yōu)，加快了算法的收斂速度。實(shí)驗(yàn)結(jié)果表明，該文的算法具有良好實(shí)時(shí)性、分割效果好的特點(diǎn)。

關(guān)鍵詞：遺傳算法；Otsu算法；圖像分割；閾值

中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）04-0198-04

Study on Image Threshold Segmentation based on Genetic Algorithm

ZHOU Ai-xia1， LI Chun-gui 1，2， TAO Jia-wei 1

（1. Guangxi University of Science and Technology， College of Electrical and Information Engineering， Liuzhou 545006， China；2.Guangxi University of Science and Technology， Computer Science and Communication Engineering Institute， Liuzhou 545006， China）

Abstract： Image thresholding segmentation is of importan significance for image analysis and recognition. Presently， there are several problems in the existed thresholding segmentation algorithms when applied in the practical application， such as time consuming， the vaguely， or important details are ignored. Aimed at these problems， this dissertation expands a series of researches， the typical threshold segmentation algorithm， Otsu， is chosen as the center point of the research. In order to overcome time-consuming of the Otsu algorithm better， Combining genetic algorithm with its characteristics， let it applied to Otsu image segmentationAlgorithm to find the best threshold， improved the convergence rate of the algorithm.The experimental results show that the new algorithm is not only higher quality but also possess a well real-time.

Key words： the genetic algorithm； Otsu method； image segmentation； threshold

1 概述

圖像分割其應(yīng)用在很多領(lǐng)域都十分廣泛，并且涉及了各種不同類(lèi)型圖像，它在圖像處理、人工智能等多個(gè)領(lǐng)域中非常重要，是計(jì)算機(jī)視覺(jué)中關(guān)鍵的步驟[1]。對(duì)計(jì)算機(jī)視覺(jué)中的圖像理解的關(guān)鍵要看圖像分割結(jié)果的好壞。圖像分割技術(shù)主要有區(qū)域分割技術(shù)、閾值分割技術(shù)、直方圖法和邊緣分割技術(shù)等。

圖像閾值分割的關(guān)鍵是選取一個(gè)適當(dāng)?shù)拈撝担褕D像分成灰度級(jí)不同的兩部分（目標(biāo)區(qū)和背景區(qū)），從而判斷出圖像中的每個(gè)像素點(diǎn)是在屬于哪個(gè)部分，進(jìn)而產(chǎn)生了對(duì)應(yīng)的二值圖像[2]。目前，現(xiàn)有的閾值分割算法，如直方圖閾值分割、迭代式閾值分割、Otsu閾值分割等[3]。Otsu法是基于整幅圖像的統(tǒng)計(jì)特性，來(lái)實(shí)現(xiàn)圖像閾值的選取，分割效果良好，但它對(duì)目標(biāo)大小和噪聲十分敏感，其運(yùn)算量大，運(yùn)行速度緩慢影響了其應(yīng)用的實(shí)時(shí)性。

隨著遺傳算法、神經(jīng)網(wǎng)絡(luò)、蟻群算法等理論不斷發(fā)展，它們與圖像分割領(lǐng)域中的一些方法相結(jié)合，從而出現(xiàn)了很多新的圖像分割方法。其中遺傳算法是借鑒了生物界進(jìn)化規(guī)律，演化而來(lái)的隨機(jī)化搜索算法，它具有并行性、自適應(yīng)性以及魯棒性等優(yōu)點(diǎn)[4]。

為了確定最佳閾值來(lái)獲得理想的分割效果，把閾值分割法與其他的一些分割方法相結(jié)合使用。本文利用遺傳算法具有的快速尋優(yōu)等特點(diǎn)對(duì)其進(jìn)行了改進(jìn)，提出一種求解Otsu最大值的遺傳算法，這種方法能快速準(zhǔn)確的找出圖像最佳分割閾值，得到理想的分割效果。

2 改進(jìn)的Otsu算法

2.1 Otsu算法

最大類(lèi)間方差法又稱(chēng)為Otsu算法，在1980年，Otsu算法被日本的大津展之提出來(lái)，該算法是在灰度直方圖的基礎(chǔ)上采用最小二乘法原理而推導(dǎo)出來(lái)的。其基本原理是：找到最佳閾值并用它把灰度直方圖分割成兩部分，使兩部分之間的方差取得最大值，也就是具有最大的分離性[5]。

[C0]類(lèi)像素的平均灰度值為：

則圖像中背景和目標(biāo)的類(lèi)間方差公式為：

2.2 改進(jìn)Otsu算法閾值的選取方法

依據(jù)上面對(duì)Otsu算法的分析， Otsu算法對(duì)于目標(biāo)與背景是用平均灰度值進(jìn)行表示的。除了用灰度均值表示外， 灰度分布還可以用方差來(lái)表示。圖像的灰度分布均勻性我們用灰度平均方差來(lái)表示，目標(biāo)區(qū)域與背景區(qū)域的內(nèi)部分布較均勻，而對(duì)于邊界及其附近的點(diǎn)灰度值的其躍變比較大。故對(duì)于圖像的邊界點(diǎn)灰度躍變的情況可以近似的用平均方差值來(lái)反映，若是分割出區(qū)域中的某部分的平均方差與總圖的平均方差相差不大，則說(shuō)明該部分很有可能被分割到了整個(gè)邊界以及其附近的點(diǎn)，出現(xiàn)目標(biāo)和背景的錯(cuò)分，因此把平均方差去換成Otsu算法中的平均灰度值是合理的[7]，我們將公式（8）進(jìn)行如下改進(jìn)：

[δ2k=ω0δ0-δT2+ω1δ1-δT2] （9）

其中，[δ0]和[δ1]分別表示背景和目標(biāo)區(qū)間灰度統(tǒng)計(jì)的平均方差，[δT]是表示整幅圖像的平均方差。

通過(guò)實(shí)際圖像驗(yàn)證，改進(jìn)的Otsu閾值選取方法是有效的 ，其灰度均值被圖像灰度分布的平均方差值取代，因此，其具有自身特點(diǎn)，如對(duì)灰度值發(fā)生的線性變化該方法不受影響， 閾值的求取也不受那些導(dǎo)致了平均方差發(fā)生線性變化干擾的不影響。

我們可以看出，在Otsu法準(zhǔn)則函數(shù)的推導(dǎo)的過(guò)程中， 用窮盡的搜索方法可以獲得最佳閾值，但計(jì)算量確實(shí)很大，用時(shí)長(zhǎng)。因此，我們利用遺傳算法來(lái)求解這一問(wèn)題。

3 基于遺傳算法的圖像閾值分割方法

3.1 遺傳算法的基本原理

遺傳算法（Genetic Algorithm， GA）是一種模擬生物進(jìn)化機(jī)制搜索和優(yōu)化的算法。它是從20世紀(jì)80年代末及90年代初開(kāi)始流行的， 廣泛地應(yīng)用于大型工業(yè)的自動(dòng)化處理上，具有魯棒性、并行性和自適應(yīng)性等特點(diǎn)[8]。遺傳算法根據(jù)優(yōu)勝劣汰的原則，且依據(jù)適應(yīng)度函數(shù)或目標(biāo)函數(shù)，對(duì)群體的個(gè)體施加遺傳操作（選擇、交叉、變異）， 完成了群體內(nèi)個(gè)體的結(jié)構(gòu)重組迭代過(guò)程 ，群體中的個(gè)體在這個(gè)過(guò)程中一代代地進(jìn)行了優(yōu)化并且逐漸逼近了最優(yōu)的解。具體算法框圖如圖1所示。

遺傳算法是一種非線性的求解過(guò)程，與線性求解相比其速度明顯快些，由于其對(duì)于求解每一條染色體的適應(yīng)度函數(shù)是分開(kāi)的，因此它的遺傳運(yùn)算也相對(duì)獨(dú)立，這一點(diǎn)對(duì)并行計(jì)算非常適用。在實(shí)際應(yīng)用中，遺傳算法的應(yīng)用達(dá)到的效果不錯(cuò)。

3.2 基于遺傳算法的Otsu的圖像分割

遺傳算法具有兩大顯著優(yōu)點(diǎn)即隱含并行性和對(duì)全局信息有效的利用能力，前者可以提高算法的速度，有利于實(shí)時(shí)處理；后者可以使遺傳算法具有較強(qiáng)的魯棒性，同時(shí)可有效避免陷入局部最優(yōu)[9]。Otsu算法選取閾值的實(shí)質(zhì)就是為了使其類(lèi)間方差最大，需在解的空間中找到一個(gè)最優(yōu)解，而遺傳算法能快速非線性查找到最優(yōu)的解以及最大方差。其具體做法如下：

1）產(chǎn)生初始群體：初始群體的規(guī)模會(huì)影響到遺傳算法的執(zhí)行效率和結(jié)果。如果對(duì)其選取的過(guò)偏，會(huì)造成最優(yōu)解的收斂慢，耗時(shí)長(zhǎng)的缺點(diǎn)。這里取20個(gè)。

2）編碼：對(duì)實(shí)現(xiàn)解空間數(shù)值進(jìn)行編碼，采用二進(jìn)制編碼，由于本文用的灰度圖是由0～255個(gè)灰度值組成的，正好是對(duì)應(yīng)了一個(gè)8位的二進(jìn)制即一個(gè)字節(jié)，因此將各個(gè)染色體編碼為8位二進(jìn)制。

3）計(jì)算適應(yīng)度值：每一代中都有很多不同的染色體，對(duì)于哪些染色體遺傳給下一代這是有其適應(yīng)度值的大小決定的，通過(guò)適應(yīng)度函數(shù)求取染色體的適應(yīng)度值。由Otsu的分割閾值方法，把染色體的方差作為其適應(yīng)度函數(shù)，即公式（9）。根據(jù)公式（9）計(jì)算每一條染色體的適應(yīng)度值。

4）選擇：遺傳運(yùn)算中的種子選擇適應(yīng)性好的染色體，其中被選中概率的大小與其適應(yīng)度值的大小成正比，其值對(duì)染色體用自然選擇中優(yōu)勝劣汰，又稱(chēng)為競(jìng)爭(zhēng)。保證適應(yīng)度值大的染色體進(jìn)行遺傳運(yùn)算，這樣一代代地進(jìn)行，逐步淘汰適應(yīng)度值小的染色體。

5）交叉：交叉運(yùn)算，就是將染色體中的某些基因進(jìn)行互換。本文采用了一種自適應(yīng)交叉概率，即對(duì)其適應(yīng)度值比群體平均的適應(yīng)度值高的染色體，我們賦予它較低交叉概率，以便保護(hù)其進(jìn)入下一代；對(duì)于其適應(yīng)度值比群體平均適應(yīng)度值低的染色體，賦予它較大交叉概率，以便使之淘汰[10]。采用的自適應(yīng)交叉概率公式如下：

當(dāng)時(shí)，[Pc=Pc1] （10）

當(dāng)[f1≥favg]時(shí)，[Pc=Pc2fmax-f1fmax-favg] （11）

其中，[f1]為要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值，[favg]為每代種群的平均適應(yīng)度值，[fmax]為種群中最大的適應(yīng)度值，[Pc1]為最大交叉概率，[Pc2]為最小交叉概率。

6）變異：變異運(yùn)算是將某一個(gè)染色體中的任一位碼按照變異概率[Pm]來(lái)取反操作，是為了防止過(guò)早收斂而產(chǎn)生局部的最優(yōu)解而非整體的最優(yōu)解。

當(dāng)[f2

當(dāng)[f1≥favg]時(shí)，[Pm=Pm2fmax-f2fmax-favg] （13）

其中，[f2]為要變異的個(gè)體的適應(yīng)度值，[Pm1]為最大變異概率，[Pm2]為最小變異概率。

7）終止條件：規(guī)定若經(jīng)過(guò)20代進(jìn)化，群體中最高適應(yīng)度值沒(méi)有發(fā)生變化則為穩(wěn)定條件 ，群體中適應(yīng)度值最高的染色體作為最優(yōu)解。

4 實(shí)驗(yàn)結(jié)果與分析

本文用圖像大小為256×256的rice.png進(jìn)行實(shí)驗(yàn)。利用Otsu算法、改進(jìn)Otsu算法以及基于遺傳算法的Otsu算法分別對(duì)rice原圖進(jìn)行分割，其效果圖如圖2所示。從分割效果是來(lái)看，改進(jìn)Otsu法 和基于遺傳算法的Otsu法的分割效果較好，噪聲點(diǎn)較少。

加入高斯噪聲和椒鹽噪聲后的圖像如圖3（a）和圖3（c）所示。經(jīng)過(guò)基于遺傳算法的Otsu法分割后的圖像分別為圖3（b）和圖3（d）。從圖3可以看出本文提出的算法在圖像分割過(guò)程中具有較好的抗噪聲能力。

從表1中可以看出，利用基于遺傳算法的Otsu算法對(duì)rice圖像和含有噪聲的rice圖像進(jìn)行分割的所用時(shí)間明顯少于其他兩種算法所用的時(shí)間。實(shí)驗(yàn)結(jié)果表明，Otsu算法結(jié)合遺傳算法對(duì)圖像進(jìn)行分割，其將分割效果及處理速度進(jìn)行了優(yōu)化，得到了更好的分割效率，抗干擾能力強(qiáng)。

為了驗(yàn)證本文算法的性能，對(duì)圖像大小為255×255的coins.png進(jìn)行實(shí)驗(yàn)，通過(guò)與文獻(xiàn)[4]算法及文獻(xiàn)[9]算進(jìn)行比較。它們的效果圖如圖4所示。

從圖4中可以看出，文獻(xiàn)[4]算法和文獻(xiàn)[9]算法的分割效果圖中硬幣上有噪聲點(diǎn)，而本算法的分割圖非常清晰，其尤其是抗噪性強(qiáng)。從表2中看出，文獻(xiàn)[9]算法的閾值明顯高于其他兩種算法，其噪聲點(diǎn)也最多，而文獻(xiàn)[4]算法的用時(shí)最長(zhǎng)。

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

本文對(duì)Otsu算法實(shí)驗(yàn)研究后得出Otsu算法分割質(zhì)量好、適用范圍廣的優(yōu)點(diǎn)，但它的處理速度較慢。為了進(jìn)一步提高它的處理速度，利用遺傳算法具有快速尋優(yōu)及尋找全局最優(yōu)解的特點(diǎn)，本文提出了將遺傳算法用于Otsu算法的圖像分割方法中對(duì)閾值進(jìn)行尋優(yōu)。實(shí)驗(yàn)結(jié)果表明基于遺傳算法的Otsu法分割效果好，提高了圖像分割算法的抗噪能力，大大縮短了圖像分割的時(shí)間，有利于圖像的實(shí)時(shí)處理，具有廣泛的應(yīng)用前景

參考文獻(xiàn)：

[1] 宋寅卯，劉磊.圖像分割研究方法及進(jìn)展[J].電腦學(xué)習(xí)，2010（2）.

[2] 韓思奇，王蕾.圖像分割的閾值法綜述[J].系統(tǒng)工程與電子技術(shù)，2002（6）.

[3] 陳冬嵐，劉京南，余玲玲.幾種圖像分割閾值選取方法的比較與研究[J].機(jī)械制造與自動(dòng)化，2003（1）.

[4] 種勁松，周孝寬，王宏琦，等.基于遺傳算法的圖像閾值分割.電子科學(xué)學(xué)刊，2000， 22（5）：785- 790.

[5] Bo Peng， Lei Zhang， David Zhang. A survey of graph theoretical approaches to image segmentation [J]. Pattern Recognition. 2013（3）.

[6] 郭臻，陳遠(yuǎn)知.圖像閾值分割算法研究[J].中國(guó)傳媒大學(xué)學(xué)報(bào)： 自然科學(xué)版，2008，15（2）：77-82.

[7] 李惠光，姚磊，石磊. 改進(jìn)的Otsu理論在圖像閾值選取中的應(yīng)用[J].計(jì)算機(jī)仿真，2007（4）.

[8] 鄭宏，潘勵(lì).基于遺傳算法的圖像閾值的自動(dòng)選取[J].中國(guó)圖像圖形學(xué)報(bào)，1999，4（4）：67-79.

[9] 陳杰，阜艷.基于遺傳算法的圖像分割的研究[J].現(xiàn)代電子技術(shù)，2010（14）.

[10] 張新明，孫印杰，鄭延斌.二維直方圖準(zhǔn)分的Otsu圖像分割及其快速實(shí)現(xiàn)[J].電子學(xué)報(bào)，2011（8）.