基于最小類內差和最大類間差的圖像分割算法研究

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

?

基于最小類內差和最大類間差的圖像分割算法研究

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

（1. 合肥師范學院計算機科學與技術系，安徽合肥 230061；2. 合肥工業大學計算機與信息學院，安徽合肥 230009）

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

圖像分割；二維Otsu法；閾值判別函數；類內最小差；類間最大差

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

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

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

1 二維最大類間方差法

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

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

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

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

（4）

在絕大多數情況下，噪聲和邊緣點的概率非常的小，對應于圖2中的區域II和IV。它們的概率可近似看成是0，這樣就可以認為，此時和這兩類對應的均值矢量為

（6）

總體均值為

定義離散度矩陣

用離散度矩陣的跡作為背景和目標類的離散度的測度

當這個離散度矩陣的跡為最大值時取得的分割閾值就為最優的閾值，即

（10）

2 新的閾值識別函數構造方法

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

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

圖3 本文閾值識別函數構造流程

類內絕對差和類間總體離差公式，都是根據絕對差和離差的定義，并將其推廣到二維，應用于待分割的圖像二維直方圖中推導得到的。

兩類的總體類內絕對差為

（12）

那么可得目標類和背景類總體的類內絕對差之和

（14）

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

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

（16）

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

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

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

3 自適應的閾值向量求解方法

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

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

圖4 遺傳算法優化閾值識別函數流程圖

（1）編碼

對于給定是實際問題，確立采用16位二進制編碼。

（2）初始化

設初始化種群的大小為popsize，初始化可以通過隨機數產生器隨機生成一個popsize行，16列的矩陣。

（3）適應度函數

（4）選擇

傳統遺傳算法中采用的是輪盤賭的選擇方式，通常會導致種群失去多樣性，遺傳算法也就過早地喪失了其進化能力。

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

（5）交叉

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

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

（6）變異

本文中采用一種動態的變異概率，以此來增加種群的多樣性。基本思路是判斷當前種群是不是“早熟”，若是則以一個較大的概率進行變異操作；反之則按常規概率進行變異操作。定義是當前種群中最優的適應度，是當前種群的平均適應度，若，其中，稱為密集因子，則判定種群沒有“早熟”，以常規概率進行變異操作；反之認為種群“早熟”，以遠大于常規概率對種群中所有個體進行變異操作，產生多個個體進入下一代，以此保證種群擺脫局部收斂。

4 實驗分析

實驗選取一幅醫學CT圖像、一幅腦核磁共振圖像(MRI圖像)等六幅圖像通過與一維Otsu算法、文獻[4]提出算法進行比較以驗證本文算法性能。實驗平臺是Pentium 4，內存為512MB，運行環境為Matlab7.0。

實驗中的參數設定如下：

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

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

表1 三種算法的閾值統計

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

通常人們對圖像分割的結果是以人的主觀判決為評價準則，但對不同分割方法的處理結果作定量的評價也是必需的。本文中，作者采用兩個常用的圖像分割質量評價指標區域一致性和區域對比度來定量評價實驗中的三種算法性能。

區域一致性是指分割區域內部元素具有相似性（一致性）的分割結果，這種特征一致性可以通過計算區域內的特征方差而得到，即，其中，。1或2，分別代表目標區域和背景區域，為區域內像素點的個數，為區域內像素點的方差，為整幅圖像的像素點數。

從表2可以看出，對六幅圖像的處理，本文算法對區域一致性、區域對比度參數都具有更好的指標，與人的視覺基本一致。

表2 三種算法分割結果定量評價

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

圖11 腦CT圖GA和IGA進化曲線比較

圖12 MRI圖GA和IGA進化曲線比較

圖13 ship圖GA和IGA進化曲線比較

圖14 紅外圖GA和IGA進化曲線比較

圖15 tank圖GA和IGA進化曲線比較

圖16 rice圖GA和IGA進化曲線比較

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

5 結 論

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

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

[2] 姚 敏, 等. 數字圖像處理[M]. 北京: 機械工業出版社, 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]. 自動化學報, 1993, 19(1): 101-105.

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

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

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

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

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

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

[11] 李敏強, 寇紀淞, 林 丹, 等. 遺傳算法的基本理論與應用[M]. 北京: 科學出版社, 2002. 163-208.

[12] 侯格賢, 畢篤彥. 圖像分割質量評價方法研究[J]. 中國圖象圖形學報, 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

國家自然科學基金資助項目（60705015）；安徽省自然科學基金資助項目（070412054）

吳 昊（1983-），男，安徽舒城人，碩士，主要研究方向為圖像處理、人工智能等。