基于種內(nèi)協(xié)同克隆選擇的Otsu圖像分割算法

童成意

長沙師范學院電子信息工程系，長沙 410100

基于種內(nèi)協(xié)同克隆選擇的Otsu圖像分割算法

童成意

長沙師范學院電子信息工程系，長沙 410100

1 引言

圖像分割是圖像處理和計算機視覺中的關(guān)鍵技術(shù)之一，其結(jié)果的好壞將直接決定視覺系統(tǒng)的性能。在眾多圖像分割方法中，閾值分割法因其簡潔直觀、計算量小、易于實現(xiàn)而成為一種最基本的分割算法并獲得了廣泛應用[1]。目前已出現(xiàn)的閾值分割方法多達十余種，常用的有最大類間方差（Otsu）法[2]、最小誤差法[3]和最大熵法[4]等。其中Otsu法是基于圖像的灰度直方圖，以最大類間方差為準則選擇最佳閾值，不需要其他先驗知識，是一種非常有效的閾值分割法。一維Otsu法只考慮了圖像的灰度信息，而未考慮像素間空間位置的相關(guān)性，因此，當圖像的灰度直方圖不呈明顯的波峰和波谷時，僅根據(jù)一維灰度信息進行圖像分割，往往難以取得理想的分割效果，對此，劉健莊[5]等提出了基于二維直方圖的Otsu算法。二維Otsu法在利用圖像灰度特征的同時兼顧了像素間的空間相關(guān)性，因此比一維Otsu法具備更強的抗噪性，但是，二維Otsu法擴大了閾值搜索空間，造成了計算的復雜性。

針對二維Otsu閾值法存在計算復雜度高，實時性差等缺陷，許多學者進行了深入研究，提出了很多改進方法，如：Gong[6]等提出了一種二維Otsu法的快速遞推算法，大大提高了算法的運算速度；郎咸朋[7]等提出了基于積分圖像的快速二維Otsu算法，減少了算法的計算量，實現(xiàn)了圖像的快速分割；徐長新[8]等通過縮小閾值搜索的空間，從而改善了算法的實時性。此外，隨著智能優(yōu)化技術(shù)的發(fā)展，運用智能優(yōu)化算法求解最佳閾值逐漸成為圖像分割的研究熱點，取得了很多成果，如：將遺傳算法應用于二維Otsu圖像分割[9]，將差分算法應用于二維最小類方差閾值分割[10]，將微粒群算法應用于二維最小交叉熵閾值分割[11]等。但是，智能優(yōu)化算法往

往收斂速度慢，且易于陷入局部極值。對此，本文對克隆選擇算法進行改進，提出一種基于種內(nèi)協(xié)同的克隆選擇算法（CSACS），并用其求解二維Otsu的最佳閾值，實驗結(jié)果表明，CSACS的分割結(jié)果與傳統(tǒng)二維Otsu法基本相同，且運算速度快，能較好地滿足實時性要求。

2 二維Otsu算法

設(shè)原圖像f的尺寸為M×N，灰度級為L，計算f中像素的鄰域均值得其平滑圖像g，則g的尺寸和灰度級也分別為M×N和L。設(shè)灰度級為i，其鄰域均值為j的像素出現(xiàn)的頻數(shù)為mij，則可得灰度值-鄰域灰度均值的二維直方圖，相應的概率密度pij為：

如圖1所示，對于任意閾值(s,t)，可將直方圖分為A、B、C、D四個區(qū)域，其中A、B分別對應于圖像的目標和背景，而遠離對角線的C、D則對應于邊緣和噪聲，目標和背景出現(xiàn)的概率分別為：

圖1 二維Otsu法直方圖劃分

目標和背景的均值矢量分別為：

在二維Otsu法中假設(shè)區(qū)域C，D的概率和為0，則w0+w1≈1，那么總體均值可表示為：

當類間方差S(s,t)取得最大值時的閾值(s,t)即為最佳閾值。

3 基于CSACS的二維Otsu圖像分割

CSA以Burnet抗體克隆選擇學說為基礎(chǔ)，通過模擬機體受抗原入侵時，抗體與抗原的反應（如免疫細胞的分化與增殖，抗體細胞的產(chǎn)生等）而形成的優(yōu)化算法。CSA包括三個步驟：克隆、克隆變異與克隆選擇。CSA的具體原理與詳細步驟見文獻[12]。傳統(tǒng)的CSA僅是各個抗體單獨地進行克隆-變異-選擇過程，而沒有考慮抗體間的聯(lián)系，因而優(yōu)化效果往往不理想。對此，本文基于生物群體中成員的協(xié)作關(guān)系，對傳統(tǒng)CSA進行改進。

生物群體中成員的協(xié)作關(guān)系已被廣泛應用于優(yōu)化領(lǐng)域，如微粒群算法、蜂群算法、魚群算法等。在各種基于成員協(xié)作的優(yōu)化算法中，有兩條共同的規(guī)律：一是優(yōu)秀個體會吸引其他個體（如蜂群發(fā)現(xiàn)蜂蜜即表演舞蹈吸引更多工蜂等）；二是劣勢個體會排斥其他個體，使得個體遠離它（如處于危險環(huán)境的個體，會通知其他個體遠離危險）。對此，本文提出以下兩種協(xié)作關(guān)系，并將其引入CSA。

（1）優(yōu)勢抗體吸引其他抗體，優(yōu)勢越明顯，對其他抗體的吸引作用越強烈?？贵wi受其他抗體吸引作用的計算公式如下：

其中，t∈[1,n]，rand為[0，1）上的隨機數(shù)，f(ai)表示抗體i的親和度。

（2）劣勢抗體排擠其他抗體，環(huán)境越惡劣，對其他抗體的排擠越劇烈。與式（8）類似，給出抗體i受其他抗體排擠作用的計算公式如下：

劉佳走的時候，我去送他，他把領(lǐng)結(jié)摘了，要拿它換被我硬搶走的乳牙，我卻把領(lǐng)結(jié)一并搶了過來，歪里歪氣地說，這玩意兒跟上吊一樣樣的。

其中，t，rand和f(·)含義同上。

由式（8）、式（9）可得抗體i的位置更新公式：

其中，a′i(t+1)、a′i(t)分別表示抗體當前位置和上次迭代的位置。

基于CSACS的圖像分割流程如下：

步驟1算法初始化。設(shè)置算法的各項參數(shù)，在閾值搜索范圍內(nèi)隨機生成初始抗體群。

步驟2將式（7）作為抗體親合力函數(shù)，計算各個抗體的親合力。

步驟3按照式（8）和式（9）計算每個抗體受優(yōu)秀個體吸引和受劣勢個體排擠的程度。

步驟4依據(jù)式（10）移動抗體，實現(xiàn)抗體群的成員協(xié)作。

步驟5抗體克隆過程，為實現(xiàn)簡單，設(shè)每個抗體的克隆規(guī)模相同。

步驟6抗體變異，按照突變概率對步驟5的克隆群體進行高頻變異。

步驟7克隆選擇，從步驟6的抗體變異群體中選擇最優(yōu)抗體，如該抗體比原始抗體優(yōu)秀，則用其替換原始抗體。

步驟8判斷算法是否終止。如算法終止，則算法結(jié)束并輸出結(jié)果；否則，返回步驟2繼續(xù)。

4 實驗結(jié)果與討論

4.1 CSACS與CSA的經(jīng)典測試函數(shù)比較

測試對象函數(shù)f1、f2如下：

表1 CSACS與CSA的性能比較

函數(shù)f1為Schaffer’s函數(shù)，該函數(shù)有多處峰值，其中只有（0，0）為全局最大值，最大值為1。此函數(shù)的最大峰值周圍有若干圓脊，因而可以很好地測試算法跳出局部最優(yōu)的能力。

函數(shù)f2為Rosenbrock函數(shù)，該函數(shù)的每個等高線大致呈拋物線形，其全局最小值也位于拋物線形的山谷中（香蕉型山谷）。很容易找到這個山谷，但由于山谷內(nèi)的值變化不大，要找到全局的最小值相當困難，因而可以很好地測試算法的尋優(yōu)速度。其全局最小值位于（1，1），最小值為0。

為了比較CSACS與CSA的優(yōu)化性能，選擇f1、f2作為測試函數(shù)。參數(shù)設(shè)置如下：最大迭代次數(shù)為1 000，抗體種群規(guī)模為20，克隆規(guī)模為20，克隆變異率為0.2，每個函數(shù)獨立測試20次。實驗結(jié)果如表1所示。

由表1可知：在參數(shù)設(shè)置相同時，對于f1，CSACS獲得的最大值、最小值、平均值都大于CSA的相應值，CSACS結(jié)果的標準差小于CSA；對于f2，CSACS獲得的最大值、最小值、平均值都小于CSA的相應值，且CSACS結(jié)果的標準差小于CSA。故CSACS的優(yōu)化性能比CSA好，且比CSA穩(wěn)定。

4.2 基于CSACS的圖像分割測試

為了檢測CSACS在圖像分割方面的有效性，采用帶噪聲的Airplane、Lena、Cameraman三幅圖像進行仿真實驗，其中Airplane帶椒鹽噪聲、Lena帶高斯噪聲、Cameraman帶高斯-椒鹽混合噪聲，三幅圖像的分辨率均為512×512，灰度級為256。原始圖像如圖2所示。實驗分別采用一維Otsu法、傳統(tǒng)二維Otsu法、基于CSA的二維Otsu法和基于CSACS的二維Otsu法對圖像進行分割，其分割效果如圖3～圖6所示。對比結(jié)果可知：一維Otsu法的抗噪性差，不能對噪聲圖像進行有效的分割；與一維Otsu法相比，二維Otsu法雖然可能會丟失圖像的部分信息，但是抗噪性更強；基于CSACS的分割方法抗噪性比基于CSA的分割法好，尋找到的閾值更優(yōu)（如對于Lena圖像的分割，基于CSA的分割法帽沿分割不清晰，而基于CSACS的分割法能較好地對其進行區(qū)分）；基于CSACS的分割方法分割原理與傳統(tǒng)二維Otsu法相同，且能獲得與傳統(tǒng)二維Otsu法相同的分割效果。

圖2 原始圖像

圖3 一維Otsu法分割結(jié)果

圖4 傳統(tǒng)二維Otsu法分割結(jié)果

圖5 基于CSA的二維Otsu分割結(jié)果

圖6 基于CSACS的二維Otsu分割結(jié)果

為了進一步測試CSACS的性能，將CSACS與遺傳算法（GA）[13]、微粒群算法（PSO）[14]、差分進化算法（DE）[10]進行比較并與傳統(tǒng)二維Otsu算法進行對照。各種算法對Airplane、Lena和Cameraman的分割結(jié)果如表2所示。由表2可知：GA優(yōu)化能力較差，算法很難尋找到最優(yōu)值，且算法效率低；PSO、CSACS和DE的分割效果較好，與最優(yōu)值較為接近，且算法速度較快。CSACS由于考慮了種群內(nèi)成員間的合作關(guān)系，能使個體較快地靠近最優(yōu)個體遠離差的個體，從而取得了最快的收斂速度；同時由于克隆免疫算法具有較強的搜索能力，故CSACS在快速收斂的同時，具有較高的收斂精度。因此，CSACS算法能夠在獲得與傳統(tǒng)二維Otsu法相近的分割效果的同時其速度卻成倍提高，克服了傳統(tǒng)二維Otsu算法實時性差的缺點。

表2 CSACS與其他算法分割結(jié)果比較

5 結(jié)束語

本文將CSACS與傳統(tǒng)二維Otsu法相結(jié)合，用于圖像分割，不但繼承了傳統(tǒng)二維Otsu法的優(yōu)點，由于CSACS考慮了種群成員間的協(xié)作關(guān)系，計算速度快，能在較短時間內(nèi)對圖像進行分割，有效克服了傳統(tǒng)二維Otsu法計算量大、實時性差等不足。實驗測試表明基于CSACS的圖像分割在保證圖像分割效果的同時具有很好的實時性，在圖像處理領(lǐng)域有著較為廣泛的應用前景。

[1]吳一全，潘喆，吳文怡.二維直方圖區(qū)域斜分的最大熵閾值分割算法[J].模式識別與人工智能，2009，22（1）：162-168.

[2]Otsu N.A threshold selection method from gray-level histograms[J].IEEE Transactions on Systems，Man and Cybernetics，1979，9（1）：62-66.

[3]張新明，馮云芝，閆林，等.一種改進的二維最小誤差閾值分割方法[J].計算機科學，2012，39（8）：259-287.

[4]阿里木·賽買提，杜培軍，柳思聰.基于人工蜂群優(yōu)化的二維最大熵圖像分割[J].計算機工程，2012，38（9）：223-243.

[5]劉健莊，栗文青.灰度圖像的二維Otsu自動閾值分割法[J].自動化學報，1993，19（1）：101-105.

[6]Gong J，Li L Y，Chen W N.Fast recursive algorithm for twodimensional threshold[J].Pattern Recognition，1998，31（3）：295-300.

[7]郎咸朋，朱楓，郝穎明，等.基于積分圖像的快速二維Otsu算法[J].儀器儀表學報，2009，30（1）：39-43.

[8]徐長新，彭國華.二維Otsu閾值法的快速算法[J].計算機應用，2012，32（5）：1258-1260.

[9]江禹生，宋香麗，任晶晶.基于遺傳算法的二維Otsu算法改進[J].計算機應用研究，2010，27（3）：1189-1191.

[10]聶方彥，高潮，郭永彩.灰度圖像二維最小類方差遞推及差分演化的快速分割[J].計算機輔助設(shè)計與圖形學學報，2010，22（11）：1866-1873.

[11]吳一全，張曉杰，吳詩婳.基于混沌彈性粒子群優(yōu)化與基于分解的二維交叉熵閾值分割[J].上海交通大學學報，2011，45（3）：301-307.

[12]孫大為，常桂然，李鳳云，等.一種基于免疫克隆的偏好多維QoS云資源調(diào)度優(yōu)化算法[J].電子學報，2011，39（8）：1824-1831.

[13]Bhattacharya M，Das A，Chandana M.GA-based multiresolution fusion of segmented brain images using PD-，T1-and T2-weighted MR modalities[J].Neural Computing&Applications，2012，21（6）：1433-1447.

[14]Chander A，Chatterjee A，Siarry P.A new social and momentum component adaptive PSO algorithm for image segmentation[J].Expert Systems with Applications，2011，38（5）：4998-5004.

TONG Chengyi

Electronic Information Engineering Department,Changsha Normal University,Changsha 410100,China

Traditional two-dimensional Otsu’s method has the disadvantages of high computational complexity,poor real-time performance.In order to improve its efficiency,inspired by the collaborative relationships among group members,a Clonal Selection Algorithm based on Cooperation within Species（CSACS）is proposed.CSACS is compared with Clonal Selection Algorithm（CSA）,and is used to image segmentation.The experimental results show that：the algorithm can accelerate the convergence speed,has good real-time ability,and its segmentation effect is very well.

Clonal Selection Algorithm（CSA）;coevolution;image segmentation;Otsu

傳統(tǒng)二維Otsu算法存在計算復雜度高、實時性差等缺點。針對這一不足，受生物群體成員間協(xié)作關(guān)系的啟示，對克隆免疫算法進行改進，提出了一種基于種內(nèi)協(xié)同的克隆選擇算法（Clonal Selection Algorithm based on Cooperation within Species，CSACS），將其與克隆選擇算法（Clonal Selection Algorithm，CSA）進行對比測試，將其應用于二維Otsu圖像分割。測試實驗表明：該算法能加快收斂速度，具有較好的實時性，且分割效果較為理想。

克隆選擇算法；協(xié)同進化；圖像分割；Otsu

A

TP301.6

10.3778/j.issn.1002-8331.1304-0490

TONG Chengyi.Image threshold segmentation method based on CSACS.Computer Engineering and Applications,2013, 49（24）：161-164.

湖南省自然科學基金重點項目（No.13JJA002）。

童成意（1965—），男，副教授，研究領(lǐng)域為嵌入式系統(tǒng)及其應用，智能控制理論與應用，電力系統(tǒng)與控制。E-mail：329699077@qq.com

2013-05-06

2013-08-29

1002-8331（2013）24-0161-04