基于IGA的三維OTSU算法的改進(jìn)

1、基于IGA的三維OTSU算法的改進(jìn)張玉連，褚巧龍，郭貴冰 （燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島，066004）摘要：在圖像分割中三維OTSU閾值分割算法充分考慮了像素之間的灰度相關(guān)信息，較一維和二維OTSU閾值法的分割效果好，但其計算復(fù)雜性高、實(shí)時性差。為此，本文提出了將免疫遺傳算法應(yīng)用到三維OTSU閾值尋優(yōu)中，并采用遞推的方法來減少適應(yīng)度函數(shù)的計算。實(shí)驗表明，與傳統(tǒng)的三維OTSU閾值分割算法相比，圖像分割清晰，實(shí)時性得到明顯改善。關(guān)鍵詞：圖像分割；三維OTSU閾值分割法；免疫遺傳算法中圖分類號:TP391Three-dimensional Otsu Threshold Algorit

2、hm Based On The Improved of Immunity Genetic AlgorithmZhang Yu-lian,Chu Qiao-long,Guo Gui-bing(College of Information Science and Engineering,Yanshan University,Qinhuangdao Hebei ,066004,China)Abstract The three-dimensional OTSU thresholding segmentation method utilizes gray level correlation inform

3、ation between each of pixel in image segmentation field,and it have better segmentation result than one-dimensional and two-dimensional thresholding,but it had the high complex computational complexity and poor real-time.So,this paper adopted an immunity genetic algorithm and used in the search of t

4、hree-dimensional OTSU optimizing threshold,and the repeat computations of the fitness function in iteration are reduced significantly using recursion. The experimental results show that compared with the traditional three-dimensional OTSU thresholding segmentation method,the image segmentation clear

5、,and the real-time had be improved.Key words:image segmentation;three-dimensional OTSU thresholding segmentation method; immunity genetic algorithm0 引言圖像分割是圖像處理的一個關(guān)鍵步驟，是計算機(jī)視覺和人工智能中基本而關(guān)鍵的技術(shù)之一。閾值分割因其計算簡單、實(shí)時性高，而成為圖像分割的應(yīng)用最廣泛的關(guān)鍵技術(shù)之一。在眾多閾值分割算法中，由Otsu1在1979年提出的1維最大類間方差法，因其計算簡單、分割效果較好而得到廣泛應(yīng)用，但其僅僅利用像素本身的灰度信息

6、，沒有利用像素之間的空間信息，并且信噪比較低，遇到較復(fù)雜的圖像時，容易產(chǎn)生較嚴(yán)重的分割錯誤。針對這一點(diǎn)，我國學(xué)者劉健莊2等人在1993年提出了基于自身灰度和鄰域平均灰度的二維Otsu閾值分割法，其抗噪聲能力要強(qiáng)于1維Otsu閾值分割法，并且圖像處理效果也有明顯改善。但是，隨著噪聲的增加，圖像的信噪比不斷降低，圖像的分割效果也越來越差。為此，景曉軍等人3引入了鄰域中值作為第三個特征，構(gòu)造了三維直方圖，并提出了三維Otsu閾值分割法，使得對于低信噪比的圖像有了更好的分割效果，并給出了一個遞歸算法，是得三維Otsu法的計算復(fù)雜度從O(L6)降到了O(L3)。范九倫等人4在此基礎(chǔ)上指出了景曉軍給出的遞

7、歸公式的錯誤并加以改正，同時給出了一組新的遞推公式，計算復(fù)雜度仍為O(L3)，但時間有所減少，并且證明了加入了混合噪聲的圖像的處理效果更好。雖然遞推算法的引入使得三維Otsu閾值分割法的計算復(fù)雜度降低了，但是計算時間仍較長，也容易受到噪聲干擾，基于此點(diǎn)，本文提出了將免疫遺傳算法融入到三維Otsu閾值分割法中，既可利用遺傳算法的固有的并行性、不易陷入局部最優(yōu)和全局搜索的特點(diǎn)，在將免疫因子融入到遺傳算法的時候，也緩解了遺傳算法的退化現(xiàn)象，克服了遺傳算法的早熟收斂和收斂性能差的缺點(diǎn)，大大提高了搜索效率5?？偠灾瑢⒚庖哌z傳算法應(yīng)用到三維Otsu閾值分割算法中，提高了該算法的抗噪能力，在搜索最佳閾值

8、過程中節(jié)約了時間，提高了算法的實(shí)時性，達(dá)到了較好的分割效果。1 三維Otsu閾值分割法對于一幅的數(shù)字圖像，我們用來表示處像素點(diǎn)的灰度值，用來表示處的鄰域的平均灰度值，定義如下： (1)用表示處鄰域的灰度中值，定義如下： (2)從和的定義可以看出，如果圖像的灰度級為，那么相應(yīng)的鄰域平均灰度級和鄰域中值的灰度級也為。我們將由、和組成的三元組定義為三維直方圖，該三維直方圖定義在一個的立方體區(qū)域內(nèi)，其三個坐標(biāo)分別表示像素的灰度值、鄰域均值和鄰域中值，如圖1(a)所示。將直方圖上任意一點(diǎn)的向量發(fā)生的頻率定義為，由下式確定： (3)其中是出現(xiàn)的頻數(shù)，。(a)三維直方圖的定義域775611163442(b)

9、三維直方圖區(qū)域的劃分02424433(c)區(qū)域0、2、3、4的劃分11616775(d)區(qū)域1、5、6、7的劃分圖1 三維直方圖區(qū)域Fig.1 D histogram region根據(jù)上面給出的三維直方圖定義，若是選取的閾值點(diǎn)，則三維直方圖被分成如圖1(b)所示的八個區(qū)域，具體的區(qū)域劃分如圖1(c)和(d)所示。由于目標(biāo)內(nèi)部和背景內(nèi)部的像素點(diǎn)之間的相關(guān)性較強(qiáng)，像素點(diǎn)的灰度值、鄰域均值和鄰域中值非常接近；而目標(biāo)和背景的邊界附近的像素點(diǎn)，以上三個值之間的差異會比較明顯。基于以上認(rèn)識，區(qū)域0和區(qū)域1分別被看成背景和目標(biāo)，區(qū)域27被看成邊緣和噪聲。由于邊界和噪聲區(qū)域的像素點(diǎn)遠(yuǎn)遠(yuǎn)小于背景和目標(biāo)的像素點(diǎn)，

10、所以我們將區(qū)域27的所有像素點(diǎn)的概率和近似為0。三維直方圖中的區(qū)域0和1分別代表圖像的背景和目標(biāo)，為了表示方便，將這兩個區(qū)域分別表示成和，則背景和目標(biāo)分別出現(xiàn)的概率為： (4) (5)背景和目標(biāo)對應(yīng)的均值矢量分別為： (6) (7)三維直方圖上總的均值矢量為： (8)前面我們已經(jīng)假設(shè)區(qū)域27的概率之和近似為0，則可知： (9) (10)定義類間的離差矩陣 (11)使用的跡作為類間的離散度測度，有 (12)這里，。則最佳閾值即為離散度測度取得最大值時，即 (13)2 基于IGA的三維OTSU算法的改進(jìn)遺傳算法是根據(jù)生物進(jìn)化的模型提出的一種進(jìn)化算法，它模擬生物優(yōu)勝劣汰的繁衍過程，算法的步驟主要是初

11、始化群體、適應(yīng)度評估、選擇、遺傳和變異等。遺傳算法具有易編碼、操作簡單、全局解空間搜索等優(yōu)點(diǎn)，但也有待改進(jìn)的地方：易退化、早熟收斂、收斂性能差等。免疫算法是模擬生物體的免疫系統(tǒng)對從外界入侵的細(xì)菌、病毒進(jìn)行防御的一種優(yōu)化算法，其特點(diǎn)是操作簡單、收斂速度快，算法的核心是疫苗的提取和接種。目前，免疫遺傳算法(Immunity Genetic Algorithm，簡稱IGA)存在多種結(jié)合模式，本為所采取的是將免疫因子融入到遺傳算法當(dāng)中，可以有效克服遺傳算法的早熟收斂和收斂性能差的缺點(diǎn)，提高收斂速和搜索效率6,7。本文又將傳統(tǒng)的免疫遺傳算法進(jìn)行了還進(jìn)，將三維OTSU閾值法和改進(jìn)后的免疫遺傳算法結(jié)合到一起

12、，可以改善三維OTSU閾值法的分割效果，提高運(yùn)算速度。改進(jìn)算法的主要步驟如下：(1)編碼由于圖像的灰度級別為0255，將每個染色體的編碼長度設(shè)置為8bit，對于使用三維OTSU閾值法進(jìn)行分割，這里定義的每條染色體的長度即為24bit，它表示某個閾值。(2)初始化 對于初始群體的產(chǎn)生，一般采用的是隨機(jī)的方法。由于初始群體的規(guī)模會影響算法的執(zhí)行效率和結(jié)果。規(guī)模太大，則計算復(fù)雜性提高，運(yùn)行時間較長；規(guī)模太小，則會導(dǎo)致搜索空間國小，不利于求取最優(yōu)解。我們在區(qū)間0255以同等概率隨機(jī)生成30個個體，作為初始群體。(3)適應(yīng)度函數(shù)的確定 在遺傳過程中，每一代都有許多不同的染色體，適應(yīng)度的大小將決定都有哪些

13、染色體遺傳到下一代。本文采用的適應(yīng)度函數(shù)是式(12)，適應(yīng)度值越大，則越接近最優(yōu)解。本文在前面已經(jīng)介紹過，式(12)已經(jīng)由遞推算法對其進(jìn)行了優(yōu)化，其計算復(fù)雜度由O(L6)降到了O(L3)，大大提高了運(yùn)算速度，本文在計算適應(yīng)度值時，也是使用遞推算法進(jìn)行計算的。(4)選擇機(jī)制本文采用的選擇機(jī)制是賭盤法選擇機(jī)制。將每個個體按照適應(yīng)度值的大小分布在讀盤上，其所占的面積與其適應(yīng)度的大小成正比。適應(yīng)度大的個體其遺傳到下一代的概率較大、個體數(shù)目較多，利于種群的優(yōu)化；適應(yīng)度小的個體被遺傳到下一代的概率較小、個體數(shù)目較少，但可以保證群體的多樣性以及適應(yīng)度小的個體的某些優(yōu)秀基因片段。(5)交叉算子 在三維Otsu

14、算法中，采用的是雙點(diǎn)交叉，交叉概率為。在迭代初期交叉概率選的大一些，可以增強(qiáng)搜索能力；在迭代后期可以選的小一些，避免一些優(yōu)秀的基因遭到破壞，并提高收斂速度。鑒于以上觀點(diǎn)，本文采用的自適應(yīng)交叉概率為： (14)式中代表了當(dāng)前遺傳代數(shù)，代表遺傳終止代數(shù)， (15) (16)式(15)和式(16)中，表示最大適應(yīng)度值，表示最小適應(yīng)度值，表示平均適應(yīng)度值，表示待交叉的兩個個體之間的適應(yīng)度較大者。(6)疫苗提取本文采取的疫苗提取的方法是從當(dāng)代交叉后的群體中，以適應(yīng)度最好的個體的全部基因的有效信息作為疫苗進(jìn)行提取。由于免疫系統(tǒng)產(chǎn)生的抗體具有很強(qiáng)的針對性，所以適應(yīng)度較高的抗體含有解決問題的特征信息。在改進(jìn)后

15、的算法中，提取最優(yōu)個體基因作為疫苗時采用疫苗更新，即在每一代個體進(jìn)行交叉后，選出當(dāng)代中適應(yīng)度最好的個體的全部基因作為疫苗，進(jìn)行接種，這樣可使每一代接種的疫苗最優(yōu)，還不影響算法的收斂性。(7)變異算子 為了增強(qiáng)算法的局部搜索能力，本文采用的變異算子為非均勻變異算子，隨著進(jìn)化代數(shù)的增加，變異基因位的取值范圍越小、與原基因位的值越接近，這樣可以保證在進(jìn)化的后期保住最優(yōu)個體的基因。本文選取的變異概率為： (17)其中：=0.1為最大變異概率，=0.002為最小變異概率，為要變異個體的適應(yīng)度值，和分別表示當(dāng)代中最大適應(yīng)度和平均適應(yīng)度。(8)疫苗接種 本文選取的疫苗接種方法是動態(tài)疫苗接種，即對當(dāng)代群體中的

16、所有個體上的所有基因，一位一位的使用疫苗上相對應(yīng)的基因位對其進(jìn)行改變，并計算改變后的個體的適應(yīng)度值；若某些個體上的基因與疫苗上相對應(yīng)的基因相同，則該個體已經(jīng)是最優(yōu)個體，不再進(jìn)行接種，直接遺傳到下一代。在三維OTSU算法中，每個個體表示一個像素點(diǎn)，該像素點(diǎn)的灰度值、鄰域均值、鄰域中值為該個體上的基因，疫苗接種則是用適應(yīng)度值最高的個體上的這三個值來依次改變每個個體上的每一位基因，將對其適應(yīng)度值改變最大并有所提高的那一位基因用免疫疫苗所對應(yīng)的基因?qū)⑵涓采w，其它基因位保持不變。(9)免疫檢測 對已經(jīng)進(jìn)行疫苗接種的個體進(jìn)行檢測，即計算其接種后的適應(yīng)度值。若接種后的個體適應(yīng)度值優(yōu)于父代的適應(yīng)度值，則它的子

17、孫代替父代進(jìn)入下一代種群；若接種后其適應(yīng)度仍不如父代，則該個體將被父代中所對應(yīng)的個體取代。(10)終止準(zhǔn)則的確定 最大遺傳代數(shù)為40代；當(dāng)相鄰兩代的平均適應(yīng)度值的差在范圍0.000，0.005之內(nèi)時，則停止迭代。若不滿足終止準(zhǔn)則，則以新的群體為初始群體，轉(zhuǎn)到步驟(3)繼續(xù)進(jìn)行計算；若滿足，則輸出結(jié)果，結(jié)果為適應(yīng)度值最大的個體。該算法的流程圖如圖2所示。開始讀取圖像信息隨機(jī)產(chǎn)生初始種群編碼計算適應(yīng)度值選擇交叉種群更新(免疫檢測)變異提取疫苗疫苗接種滿足終止條件結(jié)束YN圖2 基于IGA的三維Otsu改進(jìn)算法流程圖Fig.2 Flow chart of three- dimensional Otsu

18、 improved arithmetic based on IGA3 實(shí)驗結(jié)果與分析仿真實(shí)驗是在處理器為AMD2800+，1.6GHz，內(nèi)存為1G的機(jī)器上進(jìn)行的，仿真環(huán)境為MATLAB7.0。本次實(shí)驗采用的是國際標(biāo)準(zhǔn)圖像Lean圖像，初始群體設(shè)置為30個個體，最大迭代次數(shù)為40代，實(shí)驗結(jié)果如圖3所示。(a)原始圖像 (b)三維Otsu算法處理后的圖像 (c)本文算法處理后的圖像圖3 Lean圖分割結(jié)果圖Fig.3 The result of Lean segmentation chart對比Lean圖的分割結(jié)果可以看出，圖3(c)較圖3(b)的分割效果較好，傳統(tǒng)三維Otsu閾值法求得的最佳閾值

19、為(138,125,126)，應(yīng)用本文的算法求得的閾值為(138,125,127)；而且，在使用本文中的算法對Lean圖像進(jìn)行處理時，在迭代到23代時便得到了最佳閾值，時間為42.37S，相對于使用傳統(tǒng)的三維Otsu算法處理Lean圖像的140.39S，時間還不到其三分之一，在運(yùn)算速度上有了大幅度的提高。實(shí)時性得到明顯提高，分割效果也得到了改善。4 結(jié)束語 三維Otsu閾值分割算法的抗噪能力、分割的穩(wěn)定性以及分割的效果相對于一維和二維Otsu算法，已經(jīng)有了很大的提高，但三維Otsu算法的時間復(fù)雜度較高，實(shí)時性很差。雖然運(yùn)用遞推法已經(jīng)將三維Otsu算法的時間復(fù)雜度從O(L6)降到了O(L3)，但對每一個候選閾值都計算一次的話，計算量非常大，仍然非常耗時。而基于免疫遺傳算法改進(jìn)的三維Otsu閾值分割算法，隨機(jī)生成初始群體的個數(shù)為30，最大迭代次數(shù)是40，而且實(shí)驗證明，往往不需要遺傳到40代便可求出最佳結(jié)果，與傳統(tǒng)的三維Ot