吳 昊1，汪榮貴2，方 帥2，楊萬挺2

?

基于最小類內(nèi)差和最大類間差的圖像分割算法研究

吳 昊，汪榮貴，方 帥，楊萬挺

（1. 合肥師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，安徽合肥 230061；2. 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽合肥 230009）

針對現(xiàn)有二維Otsu圖像分割算法未考慮到目標(biāo)和背景這二類像素自身的內(nèi)聚性，提出一種新的自適應(yīng)二維Otsu算法。該算法通過待分割圖像的二維直方圖，分別統(tǒng)計(jì)類內(nèi)的絕對差、類間總體離差以反映類內(nèi)、類間的離散度，從而構(gòu)造出新閾值判別函數(shù)。通過一種改進(jìn)的遺傳算法優(yōu)化二維閾值判別函數(shù)，自動得到較理想的分割閾值。實(shí)驗(yàn)結(jié)果表明，與其它閾值判別函數(shù)相比，通過優(yōu)化新的閾值判別函數(shù)得到的二維閾值，具有了較好的分割效果，能夠更好地保留了目標(biāo)物的輪廓，而且計(jì)算量小。

圖像分割；二維Otsu法；閾值判別函數(shù)；類內(nèi)最小差；類間最大差

圖像分割是圖像進(jìn)一步分析和理解的基礎(chǔ)，是實(shí)現(xiàn)圖像按特性分成互不重疊的不同區(qū)域的過程，實(shí)現(xiàn)這一過程常使用閾值法。最大類間方差算法（Otsu算法）就是一種經(jīng)典的基于閾值的圖像分割方法，其基本思想是通過對圖像的灰度直方圖的統(tǒng)計(jì)，計(jì)算出目標(biāo)和背景的最大類間方差值，由此確定圖像的分割閾值。最初的Otsu算法基于一階直方圖，方法簡單、實(shí)時性好，因而得到廣泛的應(yīng)用。然而，當(dāng)圖像中的目標(biāo)和背景的灰度區(qū)別不明顯時，應(yīng)用此方法分割會使圖像的信息丟失，出現(xiàn)比較嚴(yán)重的分割錯誤。為此，文獻(xiàn)[4]提出了一種通過使用二維直方圖的來確定閾值的算法，即二維Otsu圖像分割算法。該方法既包含了像素的灰度信息，又包含了像素的鄰域空間信息，相比一維Otsu算法具有更好的分割效果。然而，計(jì)算復(fù)雜程度較高，并且閾值選擇標(biāo)準(zhǔn)僅單方面考慮類間方差，未考慮到目標(biāo)和背景這二類像素的自身內(nèi)聚性，因而常導(dǎo)致分割后目標(biāo)輪廓的細(xì)節(jié)比較模糊，而且該算法運(yùn)行時間長，自適應(yīng)性差。

很多學(xué)者對文獻(xiàn)[4]提出的算法進(jìn)行了改進(jìn)，如文獻(xiàn)[5-6]針對二維直方圖進(jìn)行了修正，對目標(biāo)區(qū)域和背景區(qū)域進(jìn)行重新劃分，文獻(xiàn)[7]也對類內(nèi)的離散測度進(jìn)行了考慮，但是增加了公式的復(fù)雜性，使得計(jì)算量加大。文獻(xiàn)[8]把二維Otsu算法推廣到三維，閾值判別函數(shù)的推導(dǎo)過程較繁瑣，算法時間代價也是較大的。

本文提出一種新的自適應(yīng)二維Otsu算法。該算法設(shè)計(jì)了一種新的閾值識別函數(shù)，使得對像素的分類不但考慮到類間方差的最大性，而且考慮了類內(nèi)像素的內(nèi)聚性；并且計(jì)算大都基于絕對值，減少了運(yùn)算的復(fù)雜度。通過提出并使用一種改進(jìn)的遺傳算法不斷優(yōu)化二維閾值識別函數(shù)，自動得到較理想的分割閾值，實(shí)現(xiàn)算法的自適應(yīng)性。實(shí)驗(yàn)結(jié)果表明，應(yīng)用本文提出閾值識別函數(shù)，其分割效果能夠保留較清晰地目標(biāo)物輪廓細(xì)節(jié)，而且計(jì)算量較小。

1 二維最大類間方差法

二維最大類間方差法是一種二維閾值分割方法，原理如下：假設(shè)原圖像的灰度等級為，大小為，則圖像中的每個像素點(diǎn)的值對應(yīng)于一個灰度級，掃描整幅圖像，計(jì)算圖像中的每個像素點(diǎn)的鄰域灰度值，得到一幅平滑圖像，顯然的灰度等級也為。設(shè)表示圖像中像素點(diǎn)的灰度值為，其鄰域平均灰度值為的像素點(diǎn)出現(xiàn)的次數(shù)，由此得到該圖像點(diǎn)灰度值－鄰域灰度值的二維直方圖。那么二維聯(lián)合概率密度

圖1表示某一幅圖像的二維直方圖，圖2中是其對應(yīng)的平面投影圖，軸表示每個像素點(diǎn)的灰度值，軸表示每個像素點(diǎn)的灰度鄰域平均值。點(diǎn)灰度值和其鄰域灰度均值差別不是很大，因而大都集中在對角線附近。遠(yuǎn)離對角線的灰度對可以看成是對應(yīng)圖像的噪聲和邊緣點(diǎn)。

圖1 一幅圖像的二維直方圖

圖2 二維灰度直方圖的平面投影圖

（4）

在絕大多數(shù)情況下，噪聲和邊緣點(diǎn)的概率非常的小，對應(yīng)于圖2中的區(qū)域II和IV。它們的概率可近似看成是0，這樣就可以認(rèn)為，此時和這兩類對應(yīng)的均值矢量為

（6）

總體均值為

定義離散度矩陣

用離散度矩陣的跡作為背景和目標(biāo)類的離散度的測度

當(dāng)這個離散度矩陣的跡為最大值時取得的分割閾值就為最優(yōu)的閾值，即

（10）

2 新的閾值識別函數(shù)構(gòu)造方法

上述二維Otsu法所用的閾值識別函數(shù)（即離散度矩陣的跡）只考慮到目標(biāo)類和背景類的方差大小，也就說類間的方差越大，分割的效果越好。然而，上述算法的通過離散度矩陣并計(jì)算其跡來反映背景類和目標(biāo)類之間的離散度測度，可以看出式(8)、式(9)有多次平方的運(yùn)算，復(fù)雜度較高，計(jì)算非常耗時；同時算法也沒有考慮到其目標(biāo)類和背景類的每類自身像素的分類信息，也就是說沒有考慮類內(nèi)的內(nèi)聚性。為此本文在不增加計(jì)算量的基礎(chǔ)上設(shè)計(jì)一種新的閾值識別函數(shù)來取代離散度矩陣的跡這種離散度測度。

絕對差和平均離差是各數(shù)值相對于平均數(shù)的離散程度的重要統(tǒng)計(jì)量，兩者的統(tǒng)計(jì)過程都是以計(jì)算絕對值為基礎(chǔ)的，其計(jì)算復(fù)雜程度相對較低，因而，本文將絕對差和平均離差引入到閾值判別函數(shù)的設(shè)計(jì)中。假定設(shè)為待分割圖像的二維閾值，先統(tǒng)計(jì)圖像目標(biāo)類與背景類各自類內(nèi)的絕對差，得到總體類內(nèi)絕對差之和；再統(tǒng)計(jì)目標(biāo)類和背景類兩類之間的總體平均離差；然后把總體類內(nèi)絕對差之和和類間總體離差的商作為閾值識別函數(shù)，流程如下（見圖3）。

圖3 本文閾值識別函數(shù)構(gòu)造流程

類內(nèi)絕對差和類間總體離差公式，都是根據(jù)絕對差和離差的定義，并將其推廣到二維，應(yīng)用于待分割的圖像二維直方圖中推導(dǎo)得到的。

兩類的總體類內(nèi)絕對差為

（12）

那么可得目標(biāo)類和背景類總體的類內(nèi)絕對差之和

（14）

對于二個類，定義其類間平均離差為

同樣對此，可以推廣到二維。根據(jù)第1節(jié)給出的二維直方圖，設(shè)為待分割圖像的二維閾值，式(7)已給出總體均值向量。則目標(biāo)類和背景類的類間平均離差為

（16）

綜合式(14)和式(16)得到式(17)如下

從式(17)中可以看出，分子反映的屬性為類內(nèi)的內(nèi)聚性；分母反映屬性的是類間的離散度。因而，當(dāng)取最小值時，既保證了目標(biāo)類和背景類的最大化離散度，且又能是得目標(biāo)類和背景類各類的內(nèi)聚性最好。本文將使用來作為閾值判別向量。

本文將在第3節(jié)中通過設(shè)計(jì)一種改進(jìn)的遺傳算法，以式(17)為適應(yīng)度函數(shù)，自動得到合適的閾值向量。有了閾值向量，就可以實(shí)現(xiàn)對灰度圖像的二值化分割，分類函數(shù)如下

3 自適應(yīng)的閾值向量求解方法

通過上述分析，本文改進(jìn)的二維Otsu算法選取最佳閾值向量的過程也就是選取使得目標(biāo)函數(shù)即閾值識別函數(shù)取得最小值的過程，是一種尋最優(yōu)解的過程，可以通過遺傳算法自適應(yīng)求出，具體算法的流程圖如圖4所示。

傳統(tǒng)遺傳算法對交叉和變異做統(tǒng)一的操作，對收斂性有很大影響，往往會陷入局部最優(yōu)解，這是一個經(jīng)典難題，目前有很多學(xué)者都針對這個問題進(jìn)行研究，本文根據(jù)不同的適應(yīng)度值對種群進(jìn)行分類，對不同的種群采用不同的交叉方法和變異概率，即采用基于海明距離判別的交叉方式、基于動態(tài)變化的變異概率，一定程度上避免了陷入局部最優(yōu)。下面介紹本文閾值向量的自適應(yīng)求解過程，并且比較了與傳統(tǒng)遺傳算法在選擇、交叉、變異算子上的差異。

圖4 遺傳算法優(yōu)化閾值識別函數(shù)流程圖

（1）編碼

對于給定是實(shí)際問題，確立采用16位二進(jìn)制編碼。

（2）初始化

設(shè)初始化種群的大小為popsize，初始化可以通過隨機(jī)數(shù)產(chǎn)生器隨機(jī)生成一個popsize行，16列的矩陣。

（3）適應(yīng)度函數(shù)

（4）選擇

傳統(tǒng)遺傳算法中采用的是輪盤賭的選擇方式，通常會導(dǎo)致種群失去多樣性，遺傳算法也就過早地喪失了其進(jìn)化能力。

本文采取的選擇方法是，首先將父代中部分適應(yīng)度值最高的個體保留，直接進(jìn)入子代；對于部分次優(yōu)的個體經(jīng)過一定的突變后得到的優(yōu)秀個體同樣也可進(jìn)入子代，即通過不同的父代種群進(jìn)化得到子代種群。這種種群構(gòu)造方式不僅確保了優(yōu)秀個體進(jìn)入下一代，同時，又保證了種群的多樣性，使得種群中相似個體出現(xiàn)的概率降低了，提高以下的交叉、變異操作的效率，也提高了整個算法的收斂性。

（5）交叉

交叉操作是進(jìn)化算法中遺傳算法具備的原始性的獨(dú)有特征。傳統(tǒng)的交叉算子存在一個問題，就是當(dāng)進(jìn)化到局部最優(yōu)時，種群中很多個體都非常相似，這就是“近親”。也就是說很大程度上作交叉的個體交換的串是相同的，交叉操作也就失去了作用。

本文為了避免“近親”交叉，對交配池中隨機(jī)選擇的交叉?zhèn)€體對進(jìn)行海明距離（兩個個體串的對應(yīng)比特取值不同的比特?cái)?shù)）的判斷。若選擇的個體對海明距離，則按照原定的交叉概率進(jìn)行交叉操作；反之若，則判定這對個體是“近親”，替換掉其中的一個個體，進(jìn)行重新判定，直到滿足條件或者群體中的所有個體都被嘗試替換為止。

（6）變異

本文中采用一種動態(tài)的變異概率，以此來增加種群的多樣性?；舅悸肥桥袛喈?dāng)前種群是不是“早熟”，若是則以一個較大的概率進(jìn)行變異操作；反之則按常規(guī)概率進(jìn)行變異操作。定義是當(dāng)前種群中最優(yōu)的適應(yīng)度，是當(dāng)前種群的平均適應(yīng)度，若，其中，稱為密集因子，則判定種群沒有“早熟”，以常規(guī)概率進(jìn)行變異操作；反之認(rèn)為種群“早熟”，以遠(yuǎn)大于常規(guī)概率對種群中所有個體進(jìn)行變異操作，產(chǎn)生多個個體進(jìn)入下一代，以此保證種群擺脫局部收斂。

4 實(shí)驗(yàn)分析

實(shí)驗(yàn)選取一幅醫(yī)學(xué)CT圖像、一幅腦核磁共振圖像(MRI圖像)等六幅圖像通過與一維Otsu算法、文獻(xiàn)[4]提出算法進(jìn)行比較以驗(yàn)證本文算法性能。實(shí)驗(yàn)平臺是Pentium 4，內(nèi)存為512MB，運(yùn)行環(huán)境為Matlab7.0。

實(shí)驗(yàn)中的參數(shù)設(shè)定如下：

窗口鄰域：3；種群大小：10；迭代次數(shù)：150；編碼長度：16；交叉概率：0.7；海明判別距離：2；較大變異概率：0.2；較小變異概率：0.01；密集因子：0.8。

表1給出了對每幅圖像各種算法的分割閾值。

表1 三種算法的閾值統(tǒng)計(jì)

主觀上從圖5~圖10可以看出用本文算法得到閾值化圖像與文獻(xiàn)[4]算法和一維Otsu算法相比背景和目標(biāo)物能夠更好區(qū)分出來。圖5(b)中，CT圖像四個部分的目標(biāo)物幾乎都連在一起，失去了輪廓信息；圖5(c)其分割效果更差，目標(biāo)物沒有能夠分割出來；應(yīng)用本文算法的結(jié)果，圖5(d)，其腦CT圖像的四個部分有著清晰地輪廓，分割效果比較理想；圖6(d)相對于圖6(b)和圖6(c)顯然有著更多的輪廓；圖7(b)中，帆船底部與水面沒有分開，文獻(xiàn)[4]算法的分割結(jié)果圖7(c)相對于一維Otsu有所改善，但與本文算法分割結(jié)果圖7(d)相比仍然有很多錯誤分割的地方。圖8紅外圖像的分割也是本文算法相對于一維Otsu和文獻(xiàn)[4]算法最大限度地將目標(biāo)物與背景分開，目標(biāo)物保留了較好的輪廓細(xì)節(jié)；對圖9，三種算法都取得了較好的效果，但是本文算法能夠很好地保留了坦克車輪的輪廓；圖10對米粒圖像的分割，一維Otsu算法和文獻(xiàn)[4]算法的分割結(jié)果含有很多的噪聲，本文算法分割后的結(jié)果米粒清晰可見。

通常人們對圖像分割的結(jié)果是以人的主觀判決為評價準(zhǔn)則，但對不同分割方法的處理結(jié)果作定量的評價也是必需的。本文中，作者采用兩個常用的圖像分割質(zhì)量評價指標(biāo)區(qū)域一致性和區(qū)域?qū)Ρ榷葋矶吭u價實(shí)驗(yàn)中的三種算法性能。

區(qū)域一致性是指分割區(qū)域內(nèi)部元素具有相似性（一致性）的分割結(jié)果，這種特征一致性可以通過計(jì)算區(qū)域內(nèi)的特征方差而得到，即，其中，。1或2，分別代表目標(biāo)區(qū)域和背景區(qū)域，為區(qū)域內(nèi)像素點(diǎn)的個數(shù)，為區(qū)域內(nèi)像素點(diǎn)的方差，為整幅圖像的像素點(diǎn)數(shù)。

從表2可以看出，對六幅圖像的處理，本文算法對區(qū)域一致性、區(qū)域?qū)Ρ榷葏?shù)都具有更好的指標(biāo)，與人的視覺基本一致。

表2 三種算法分割結(jié)果定量評價

本文算法中采用自適應(yīng)的改進(jìn)遺傳算法來尋優(yōu)最佳閾值向量，對于的計(jì)算次數(shù)為算法設(shè)置的循環(huán)代次，同樣，每計(jì)算一次都要累加計(jì)算、個點(diǎn)，所以本文算法的時間復(fù)雜度為。本文通過改進(jìn)的GA算法加速收斂進(jìn)程，平均收斂代數(shù)基本上保證在50代以內(nèi)，為了驗(yàn)證改進(jìn)的GA具有更好的收斂性，本文也做了改進(jìn)GA尋優(yōu)和傳統(tǒng)GA尋優(yōu)的性能比較實(shí)驗(yàn)。圖11~圖16分別對應(yīng)實(shí)驗(yàn)中的六幅圖像應(yīng)用GA和IGA進(jìn)行尋優(yōu)的進(jìn)化曲線。

圖11 腦CT圖GA和IGA進(jìn)化曲線比較

圖12 MRI圖GA和IGA進(jìn)化曲線比較

圖13 ship圖GA和IGA進(jìn)化曲線比較

圖14 紅外圖GA和IGA進(jìn)化曲線比較

圖15 tank圖GA和IGA進(jìn)化曲線比較

圖16 rice圖GA和IGA進(jìn)化曲線比較

圖11~圖16中，橫坐標(biāo)表示進(jìn)化的代數(shù)，縱坐標(biāo)表示適應(yīng)度值，這里尋優(yōu)得到得是1/的最大值。黑線是傳統(tǒng)GA的進(jìn)化曲線，加星號線是應(yīng)用改進(jìn)的GA(IGA)所得到的進(jìn)化曲線。顯然，應(yīng)用IGA算法所得到的最優(yōu)閾值顯然要好于傳統(tǒng)遺傳算法能夠更早的得到最優(yōu)解，也更加接近全局最優(yōu)解，一定程度上克服了傳統(tǒng)GA算法的“早熟”問題。

5 結(jié) 論

本文指出了傳統(tǒng)的二維Otsu算法的計(jì)算復(fù)雜程度較大，并且也只僅僅考慮類間最大方差，為此，本文在不增加計(jì)算復(fù)雜度的前提下，提出了并設(shè)計(jì)了一種既能反映類間方差又能反映類內(nèi)方差的閾值判別函數(shù)，得出了比傳統(tǒng)二維Otsu算法更好的分割效果，同時用來改進(jìn)的遺傳算法具有更好的群體多樣性和全局搜索能力。實(shí)驗(yàn)的結(jié)果驗(yàn)證了本文提出的方法具有更好、更快的分割效果，具有一定的實(shí)用價值。

[1] [美]岡薩雷斯. 數(shù)字圖像處理(第2版)[M]. 阮秋琦等譯. 北京: 電子工業(yè)出版社, 2003. 460-521.

[2] 姚 敏, 等. 數(shù)字圖像處理[M]. 北京: 機(jī)械工業(yè)出版社, 2006. 243-253.

[3] Otsu N. A threshold selection method from gray level histograms [J]. IEEE Trans on SMC, 1979, 9(1): 62-69.

[4] 劉健莊, 栗文青. 灰度圖像的二維Otsu自動閾值分割法[J]. 自動化學(xué)報(bào), 1993, 19(1): 101-105.

[5] 范九倫, 趙 鳳. 灰度圖像的二維Otsu曲線閾值分割法[J]. 電子學(xué)報(bào), 2007, 35(4): 751-755.

[6] 楊金龍, 張光南, 歷樹忠, 等. 基于二維直方圖的圖像分割算法研究[J]. 激光與紅外, 2008, (4): 400-403.

[7] 周云燕, 楊坤濤, 黃 鷹. 基于最小類內(nèi)離散度的改進(jìn)Otsu分割方法的研究[J]. 華中科技大學(xué)學(xué)報(bào), 2007, 35(2): 101-103.

[8] 范九倫, 趙 鳳, 張雪峰. 三維Otsu閾值分割方法的遞推算法[J]. 電子學(xué)報(bào), 2007, 35(7): 1398-1402.

[9] 丁明躍, 彭嘉雄, 萬發(fā)貫. 平均絕對差算法捕獲概率的估計(jì)[J]. 華中理工大學(xué)學(xué)報(bào), 1989, 17(5): 71-76.

[10] 郭福華, 鄧飛其. 推廣的半絕對離差和動態(tài)投資組合選擇[J]. 應(yīng)用數(shù)學(xué), 2007, 20(3): 446-451.

[11] 李敏強(qiáng), 寇紀(jì)淞, 林 丹, 等. 遺傳算法的基本理論與應(yīng)用[M]. 北京: 科學(xué)出版社, 2002. 163-208.

[12] 侯格賢, 畢篤彥. 圖像分割質(zhì)量評價方法研究[J]. 中國圖象圖形學(xué)報(bào), 2000, 5(1): 39-43.

Image Segmentation Algorithm Research Based on Minimum Within-cluster Difference and Maximum Between-cluster Difference

WU Hao, WANG Rong-gui, FANG Shuai, YANG Wan-ting

( 1. Department of Computer Science and Technology, Hefei Normal College, Hefei Anhui 230061, China;2. Faculty of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China )

The present two-dimensional Otsu image segmentation algorithm ignores the cohesiveness of foreground and background pixels. A novel method of threshold recognition algorithm is proposed, which, by using two-dimensional histogram of the target image, counts the absolute difference within the cluster and the average total deviation between the cluster to reflect the scattered difference, and then constructs a new threshold recognition function. An improved genetic algorithm is adopted to optimize the new threshold recognition function so as to obtain the ideal threshold value automatically. Experimental results show that the two-dimensional threshold value obtained through the optimized threshold recognition function is of good segmentation efficiency, of good retaining of the object outline and of low work amount of calculation.

image segmentation; two-dimensional Otsu algorithm; threshold recognition function; minimum within-cluster difference; maximum between-cluster difference

TP 391.41

A

1003-0158(2011)01-0067-09

2009-04-15

國家自然科學(xué)基金資助項(xiàng)目（60705015）；安徽省自然科學(xué)基金資助項(xiàng)目（070412054）

吳 昊（1983-），男，安徽舒城人，碩士，主要研究方向?yàn)閳D像處理、人工智能等。