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

1、基于IGA的三維OTSU算法的改進(jìn)張玉連，褚巧龍，郭貴冰 （燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島，066004）摘要：在圖像分割中三維OTSU閾值分割算法充分考慮了像素之間的灰度相關(guān)信息，較一維和二維OTSU閾值法的分割效果好，但其計(jì)算復(fù)雜性高、實(shí)時(shí)性差。為此，本文提出了將免疫遺傳算法應(yīng)用到三維OTSU閾值尋優(yōu)中，并采用遞推的方法來(lái)減少適應(yīng)度函數(shù)的計(jì)算。實(shí)驗(yàn)表明，與傳統(tǒng)的三維OTSU閾值分割算法相比，圖像分割清晰，實(shí)時(shí)性得到明顯改善。關(guān)鍵詞：圖像分割；三維OTSU閾值分割法；免疫遺傳算法中圖分類號(hào):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 引言圖像分割是圖像處理的一個(gè)關(guān)鍵步驟，是計(jì)算機(jī)視覺(jué)和人工智能中基本而關(guān)鍵的技術(shù)之一。閾值分割因其計(jì)算簡(jiǎn)單、實(shí)時(shí)性高，而成為圖像分割的應(yīng)用最廣泛的關(guān)鍵技術(shù)之一。在眾多閾值分割算法中，由Otsu1在1979年提出的1維最大類間方差法，因其計(jì)算簡(jiǎn)單、分割效果較好而得到廣泛應(yīng)用，但其僅僅利用像素本身的灰度信息

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

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

8、過(guò)程中節(jié)約了時(shí)間，提高了算法的實(shí)時(shí)性，達(dá)到了較好的分割效果。1 三維Otsu閾值分割法對(duì)于一幅的數(shù)字圖像，我們用來(lái)表示處像素點(diǎn)的灰度值，用來(lái)表示處的鄰域的平均灰度值，定義如下： (1)用表示處鄰域的灰度中值，定義如下： (2)從和的定義可以看出，如果圖像的灰度級(jí)為，那么相應(yīng)的鄰域平均灰度級(jí)和鄰域中值的灰度級(jí)也為。我們將由、和組成的三元組定義為三維直方圖，該三維直方圖定義在一個(gè)的立方體區(qū)域內(nèi)，其三個(gè)坐標(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)所示的八個(gè)區(qū)域，具體的區(qū)域劃分如圖1(c)和(d)所示。由于目標(biāo)內(nèi)部和背景內(nèi)部的像素點(diǎn)之間的相關(guān)性較強(qiáng)，像素點(diǎn)的灰度值、鄰域均值和鄰域中值非常接近；而目標(biāo)和背景的邊界附近的像素點(diǎn)，以上三個(gè)值之間的差異會(huì)比較明顯?；谝陨险J(rèn)識(shí)，區(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)，為了表示方便，將這兩個(gè)區(qū)域分別表示成和，則背景和目標(biāo)分別出現(xiàn)的概率為： (4) (5)背景和目標(biāo)對(duì)應(yīng)的均值矢量分別為： (6) (7)三維直方圖上總的均值矢量為： (8)前面我們已經(jīng)假設(shè)區(qū)域27的概率之和近似為0，則可知： (9) (10)定義類間的離差矩陣 (11)使用的跡作為類間的離散度測(cè)度，有 (12)這里，。則最佳閾值即為離散度測(cè)度取得最大值時(shí)，即 (13)2 基于IGA的三維OTSU算法的改進(jìn)遺傳算法是根據(jù)生物進(jìn)化的模型提出的一種進(jìn)化算法，它模擬生物優(yōu)勝劣汰的繁衍過(guò)程，算法的步驟主要是初

11、始化群體、適應(yīng)度評(píng)估、選擇、遺傳和變異等。遺傳算法具有易編碼、操作簡(jiǎn)單、全局解空間搜索等優(yōu)點(diǎn)，但也有待改進(jìn)的地方：易退化、早熟收斂、收斂性能差等。免疫算法是模擬生物體的免疫系統(tǒng)對(duì)從外界入侵的細(xì)菌、病毒進(jìn)行防御的一種優(yōu)化算法，其特點(diǎn)是操作簡(jiǎn)單、收斂速度快，算法的核心是疫苗的提取和接種。目前，免疫遺傳算法(Immunity Genetic Algorithm，簡(jiǎn)稱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)編碼由于圖像的灰度級(jí)別為0255，將每個(gè)染色體的編碼長(zhǎng)度設(shè)置為8bit，對(duì)于使用三維OTSU閾值法進(jìn)行分割，這里定義的每條染色體的長(zhǎng)度即為24bit，它表示某個(gè)閾值。(2)初始化 對(duì)于初始群體的產(chǎn)生，一般采用的是隨機(jī)的方法。由于初始群體的規(guī)模會(huì)影響算法的執(zhí)行效率和結(jié)果。規(guī)模太大，則計(jì)算復(fù)雜性提高，運(yùn)行時(shí)間較長(zhǎng)；規(guī)模太小，則會(huì)導(dǎo)致搜索空間國(guó)小，不利于求取最優(yōu)解。我們?cè)趨^(qū)間0255以同等概率隨機(jī)生成30個(gè)個(gè)體，作為初始群體。(3)適應(yīng)度函數(shù)的確定 在遺傳過(guò)程中，每一代都有許多不同的染色體，適應(yīng)度的大小將決定都有哪些

13、染色體遺傳到下一代。本文采用的適應(yīng)度函數(shù)是式(12)，適應(yīng)度值越大，則越接近最優(yōu)解。本文在前面已經(jīng)介紹過(guò)，式(12)已經(jīng)由遞推算法對(duì)其進(jìn)行了優(yōu)化，其計(jì)算復(fù)雜度由O(L6)降到了O(L3)，大大提高了運(yùn)算速度，本文在計(jì)算適應(yīng)度值時(shí)，也是使用遞推算法進(jìn)行計(jì)算的。(4)選擇機(jī)制本文采用的選擇機(jī)制是賭盤法選擇機(jī)制。將每個(gè)個(gè)體按照適應(yīng)度值的大小分布在讀盤上，其所占的面積與其適應(yīng)度的大小成正比。適應(yīng)度大的個(gè)體其遺傳到下一代的概率較大、個(gè)體數(shù)目較多，利于種群的優(yōu)化；適應(yīng)度小的個(gè)體被遺傳到下一代的概率較小、個(gè)體數(shù)目較少，但可以保證群體的多樣性以及適應(yīng)度小的個(gè)體的某些優(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)度值，表示待交叉的兩個(gè)個(gè)體之間的適應(yīng)度較大者。(6)疫苗提取本文采取的疫苗提取的方法是從當(dāng)代交叉后的群體中，以適應(yīng)度最好的個(gè)體的全部基因的有效信息作為疫苗進(jìn)行提取。由于免疫系統(tǒng)產(chǎn)生的抗體具有很強(qiáng)的針對(duì)性，所以適應(yīng)度較高的抗體含有解決問(wèn)題的特征信息。在改進(jìn)后

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

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

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

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

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