摘  要： 針對一維閾值分割只考慮圖像的灰度級而不考慮像素的空間信息且需要目標(biāo)函數(shù)的問題，根據(jù)最優(yōu)進(jìn)化圖像閾值分割算法的基本思想，提出了一種無目標(biāo)函數(shù)的二維圖像閾值分割算法框架（2D-OEA）。2D-OEA將每個圖像二維信息向量看作一個染色體，假設(shè)最優(yōu)進(jìn)化方向存在，建立進(jìn)化方向更新模型；然后定義了染色體編碼規(guī)則，通過簡單隨機(jī)采樣初始化種群，再對種群進(jìn)行交叉變異運算、適值計算、選擇和閾值修正，得到穩(wěn)定的最優(yōu)二維閾值。分別從理論和實驗分析了假設(shè)和模型的合理性。實驗結(jié)果表明，假設(shè)和進(jìn)化方向更新模型合理，2D-OEA快速、穩(wěn)定且有效，分割結(jié)果優(yōu)于OEA。
關(guān)鍵詞： 閾值分割； 圖像分割； 遺傳算法； 二維直方圖； 灰度級

　閾值分割是圖像處理的一種重要方法，在圖像處理領(lǐng)域有著廣泛的應(yīng)用，如文本處理、粒子計數(shù)、細(xì)胞運動估計和目標(biāo)識別等。閾值分割的效果決定了后繼圖像處理和圖像分析的效果。閾值分割是指找到一個能把圖像分割為目標(biāo)和背景的最優(yōu)閾值。最優(yōu)閾值通常很難確定，學(xué)者們根據(jù)不同的標(biāo)準(zhǔn)提出了大量閾值分割的方法。ZHANG Y J[1]分析了1995年以前的大部分圖像分割方法，并將這些方法分成了三大類。SEZGIN M和SANKUR B[2]分析了2003年以前的40種主要的閾值分割方法，根據(jù)分割時考慮的圖像信息，將這此方法分為直方圖形狀、測試空間聚集度、熵、目標(biāo)屬性、空間相關(guān)性和局部灰度面6類。近年來，出現(xiàn)了許多新的閾值分割方法，如基于II型模糊邏輯理論的方法[3]、基于圖譜劃分理論的方法[4]和基于能量函數(shù)最優(yōu)化的方法[5]等。圖像閾值分割算法一般根據(jù)其他理論或某些標(biāo)準(zhǔn)定義一個目標(biāo)函數(shù)，然后通過求解最優(yōu)化問題得到最優(yōu)閾值。LUESSI M、EICHMANN M、SCHUSTER G M和KATSAGGELOS[6]將這些目標(biāo)函數(shù)分成兩類，并提出了一個求解的算法框架，該框架不僅可處理現(xiàn)有的閾值分割問題，還可以拓展到多級閾值情況。林正春、王知衍和張艷青[7]根據(jù)大多數(shù)閾值分割算法需要定義目標(biāo)函數(shù)的特點，結(jié)合進(jìn)化算法，提出了一種不需要目標(biāo)函數(shù)的圖像閾值分割算法——最優(yōu)進(jìn)化圖像閾值分割算法（OEA）。
　一般的圖像閾值分割算法僅利用了圖像的一維信息，通常是灰度信息。當(dāng)目標(biāo)信息和背景信息的均值相差較遠(yuǎn)且各自的標(biāo)準(zhǔn)差較小時，即直方圖的谷點明顯時，一維閾值分割方法能較好地將目標(biāo)和背景分開。若根據(jù)一維信息無法找出最優(yōu)閾值，解決方法主要有兩種：一是通過直方圖轉(zhuǎn)化，使得谷點更明顯；二是考慮更多的圖像信息，如圖像中各像素的空間信息，即二維圖像閾值分割算法。二維圖像閾值分割算法源于AHUJA V和ROSENFELD A[8]的研究以及KIRBY R L和ROSENFELD A[9]的研究。學(xué)者們根據(jù)二維閾值分割的思想，結(jié)合其他理論，提出了許多新的圖像閾值分割算法，如二維最大熵遺傳算法[10]、二維灰度直方圖非模糊性最大化方法[11]、基于二維Tsallis-Havrda-Charvát熵的方法[12]、基于改進(jìn)二維最大熵及粒子群遞推的方法[13]和基于二維最小Tsallis交叉熵的方法[14]等。本文針對一維圖像閾值分割算法一般不考慮像素的空間信息且需要目標(biāo)函數(shù)的問題，根據(jù)OEA的思想，提出了一種通用的、無目標(biāo)函數(shù)的二維圖像閾值分割算法框架（2D-OEA）。
1 二維最優(yōu)進(jìn)化圖像分割算法
　遺傳算法（GA）是受生物進(jìn)化理論的啟發(fā)而提出的，HOLLAND J[15]首次使用了遺傳算法一詞。GA原理簡單，不涉及復(fù)雜的數(shù)學(xué)知識，是一種有效的求解最優(yōu)化問題的方法。許多學(xué)者將GA和其他理論相結(jié)合，提出了很多有效的閾值分割方法。OEA[7]也是根據(jù)遺傳算法理論提出的一種新的圖像閾值分割算法。與一般方法不同，OEA不需要將閾值分割問題轉(zhuǎn)化來得到目標(biāo)函數(shù)，而是將圖像中的每個像素看作一個染色體，通過個體的進(jìn)化找到最優(yōu)閾值。與其他一維閾值分割方法類似，OEA也只利用了圖像一維信息。本文根據(jù)OEA的基本思想，結(jié)合圖像的二維信息，提出二維最優(yōu)進(jìn)化圖像閾值分割算法（2D-OEA）。
1.1 閾值更新模型
　圖像閾值分割算法一般根據(jù)其他理論將閾值分割問題轉(zhuǎn)化，以得到目標(biāo)函數(shù)，再輔以最優(yōu)化方法進(jìn)行求解。目標(biāo)函數(shù)的作用在于提供一個收斂方向，在進(jìn)化算法中起到進(jìn)化方向的作用，引導(dǎo)種群向著特定的方向進(jìn)化。實際上，生物的進(jìn)化并沒有“目標(biāo)函數(shù)”的指引，生物能自覺地向著最優(yōu)的進(jìn)化方向進(jìn)化。
圖像中的每個像素可看作是一個染色體，像素對應(yīng)的信息經(jīng)過編碼后得到染色體的基因。每代進(jìn)化后，種群聚集的地方即為種群當(dāng)前實際的進(jìn)化方向。圖像可看作由目標(biāo)和背景組成，因此種群中有兩類個體，而閾值即為分割兩類不同個體的分割面。如圖1所示，若閾值選在分割面S1處，當(dāng)種群向著S1進(jìn)化時，代表背景的個體離分割面較遠(yuǎn)，進(jìn)化后種群的聚集地將偏向S1的右方；若閾值選在分割面S3處，則進(jìn)化后種群的聚集地將偏向S3的左方。隨著進(jìn)化方向不斷地修正，當(dāng)分割面恰好將兩類個體分開時（即S2處），種群的進(jìn)化才能達(dá)成一致，穩(wěn)定地向該方向進(jìn)化。

　因此，種群存在一個最優(yōu)進(jìn)化方向T，種群總可以找到最優(yōu)進(jìn)化方向。由于最優(yōu)閾值事先無法確定，因此種群最初的進(jìn)化也無法進(jìn)行。給定一個初始閾值T0，由于最優(yōu)進(jìn)化方向存在，因此無論如何設(shè)定初始閾值，種群都應(yīng)穩(wěn)定地收斂到最優(yōu)閾值。種群進(jìn)化過程中受隨機(jī)因素ε的影響，每次進(jìn)化存在隨機(jī)誤差εi，隨機(jī)誤差采用正態(tài)分布模型。種群的進(jìn)化模型為：

1.2 2D-OEA
　在2D-OEA中，染色體對應(yīng)于一個二維向量，對該向量編碼后得到染色體的基因序列。2D-OEA是通用的二維閾值分割算法，不失一般性，本文選取常用的圖像二維信息（灰度和灰度均值）進(jìn)行實驗。若圖像的灰度級為L，則灰度均值的范圍為0~L?；叶?mdash;灰度均值二維直方圖如圖2所示，圖2（b）為圖2（a）的灰度-灰度均值二維直方圖及分區(qū)，圖2（c）為分區(qū)俯視圖。在閾值向量處用十字線將二維直方圖分成4個矩形區(qū)域，1區(qū)和3區(qū)分別代表目標(biāo)和背景，2區(qū)和4區(qū)均代表邊界和噪聲。

　為了檢測算法的性能，選擇一幅測試圖（如圖3（a）所示）進(jìn)行測試。設(shè)置不同的初始閾值，2D-OEA的計算過程如圖4所示。由圖4可知，無論初始閾值如何設(shè)置，2D-OEA得到的閾值都較穩(wěn)定，收斂性較好。圖4的實驗結(jié)果證明，最優(yōu)進(jìn)化方向存在，2D-OEA實現(xiàn)了無目標(biāo)函數(shù)的圖像二維閾值分割。2D-OEA初始閾值的設(shè)定對算法的計算速度有一定的影響，若設(shè)為隨機(jī)值，當(dāng)初始閾值距離最優(yōu)閾值較遠(yuǎn)時，需要較多的迭代次數(shù)來平滑此差距。圖像由目標(biāo)和背景組成，因此目標(biāo)和背景的比應(yīng)為0.5左右。將初始閾值設(shè)為區(qū)間中點將提高算法收斂的速度，因此下面的實驗初始閾值設(shè)為（0.5L，0.5L）。對圖3（a）進(jìn)行1 000次實驗，最優(yōu)閾值向量均值為（121.430 0，119.999 0），每次實驗得到的最優(yōu)閾值向量與最優(yōu)閾值向量均值的2-范數(shù)均值為1.758 9，2-范數(shù)方差為1.410 4；每次實驗進(jìn)化代數(shù)均值為3.215 0次，方差為0.924 8。實驗說明，2D-OEA收斂較快，收斂的穩(wěn)定性較好。

　本文針對一維圖像閾值分割算法只考慮圖像一維信息和傳統(tǒng)二維圖像閾值分割算法需要目標(biāo)函數(shù)的問題，根據(jù)OEA的思想，提出了一種通用的，無目標(biāo)函數(shù)的二維圖像閾值分割算法框架（2D-OEA）。2D-OEA對二維圖像信息編碼，然后對種群進(jìn)行交叉變異運算，計算出種群的適值，再根據(jù)選擇機(jī)制選擇出新的種群，提出了閾值更新模型和閾值修正方法，提高了算法的穩(wěn)定性。本文從理論上分析了算法的合理性，并以圖像的灰度-灰度均值二維直方圖為例，通過實驗驗證了算法的合理性。采用5幅常用的測試圖對2D-OEA進(jìn)行測試，實驗結(jié)果表明，2D-OEA快速、穩(wěn)定且有效，其分割結(jié)果優(yōu)于OEA。
　實驗中也發(fā)現(xiàn)了2D-OEA的一些起不足，如采用兩類的中點修正閾值顯然不是最優(yōu)的修正方法，采用簡單隨機(jī)采樣不能保證最好地體現(xiàn)圖像的二維信息特征。今后將致力于解決這些問題，繼續(xù)完善進(jìn)化方向更新模型。
參考文獻(xiàn)
[1] ZHANG Y. J. A survey on evaluation methods for image segmentation[J]. Pattern Recognition， 1996， 29（8）： 1335-1346.
[2] SEZGIN M， SANKUR B. Survey over image thresholding techniques and quantitative performance evaluation[J]. Journal of Electronic Imaging， 2004， 13（1）： 146-165
[3] YUKSEL M E， BORLU M. Accurate segmentation of dermoscopic images by image thresholding based on type-2 fuzzy logic[J]. IEEE Transactions on Fuzzy Systems， 2009， 17（4）： 976-982
[4] TAO W B， JIN H， ZHANG Y M， et al. Image thresholding using graph cuts[J]. IEEE Transactions on Systems Man and Cybernetics Part a-Systems and Humans， 2008， 38（5）： 1181-1195
[5] SAHA B N， RAY N. Image thresholding by variational minimax optimization[J]. Pattern Recognition， 2009， 42（5）： 843-856.
[6] LUESSI M， EICHMANN M， SCHUSTER G M， et al.Framework for efficient optimal multilevel image thresholding[J]. Journal of Electronic Imaging， 2009， 18（1）.
[7] Lin Zhengchun， Wang Zhiyan， Zhang Yanqing. Optimal evolution algorithm for image thresholding[J]. Journal of Computer-Aided Design & Computer Graphics， 2010，22（7）：1201-1206.
[8] AHUJA N， ROSENFEID A. A Note on the use of second-order gray-level statistics for threshold selection[J]. IEEE Transactions on Systems， Man and Cybernetics 1978， 8（12）： 895-898.
[9] KIRBY R L， ROSENFELD A. A Note on the use of （gray level， local average gray level）space as an aid in threshold selection [J]. IEEE Transactions on Systems， Man and Cybernetics， 1979， 9（12）： 860-864.
[10] 陳果，左洪福.圖像分割的二維最大熵遺傳算法[J]. 2002，14（6）：530-534.
[11] Qing Wang， Zheru Chi， Zhao R. Image thresholding by maximizing of nonfuzziness of the 2D grayscale histogram[J]. Computer Vision and Image Understanding， 2002， 85（2）： 100-116.
[12]    SAHOO P K， ARORA G. Image thresholding using two-dimensional Tsallis-Havrda-Charvat entropy[J]. Pattern Recognition letters， 2006， 27（6）： 520-528
[13]  吳一全，張金礦.基于改進(jìn)的二維最大熵及粒子群遞推的圖像分割[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 2008，20（10）：1338-1344.
[14] TANG Y G， DI Q Y， ZHAO L X， et al. Image thresholding segmentation based on two-dimensional minimum Tsallis-cross entropy[J]. Acta Physica Sinica， 2009， 58（1）： 9-15.
[15] HOLLAND J. Adaptation in natural and artificial systems[M]. University of Michigan， 1975.
[16] OTSU N. A threshold selection method from gray level histogram  [J]. IEEE Transactions on System， Man and Cybernetics， 1979， 9（1）： 62-67
[17] KITTLER J. ILLINGWORTH J. Minimum error thresholding[J]. Pattern Recognition， 1986， 19（1）： 41-47
[18] BOSCO G L. A genetic algorithm for image segmentation[C]. 11th International Conference on Image Analysis and rocessing，2001： 262-266.
[19] Zhao Xin， LEE M E， KIM S H. Improved image thresholding using ant colony optimization algorithm[C].Proceedings of Dalian， 2008： 210-215
[20] Lin Zhengchun， Wang Zhiyan， Zhang Yanqing. Image thresholding using particle swarm optimization[C]. Proceedings of MultiMedia and Information Technology， MMIT′08 International Conference， 2008： 245-248.