基于IGA的三維OTSU算法的改進

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

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

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

8、過程中節(jié)約了時間，提高了算法的實時性，達到了較好的分割效果。1 三維Otsu閾值分割法對于一幅的數(shù)字圖像，我們用來表示處像素點的灰度值，用來表示處的鄰域的平均灰度值，定義如下： (1)用表示處鄰域的灰度中值，定義如下： (2)從和的定義可以看出，如果圖像的灰度級為，那么相應的鄰域平均灰度級和鄰域中值的灰度級也為。我們將由、和組成的三元組定義為三維直方圖，該三維直方圖定義在一個的立方體區(qū)域內，其三個坐標分別表示像素的灰度值、鄰域均值和鄰域中值，如圖1(a)所示。將直方圖上任意一點的向量發(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ù)上面給出的三維直方圖定義，若是選取的閾值點，則三維直方圖被分成如圖1(b)所示的八個區(qū)域，具體的區(qū)域劃分如圖1(c)和(d)所示。由于目標內部和背景內部的像素點之間的相關性較強，像素點的灰度值、鄰域均值和鄰域中值非常接近；而目標和背景的邊界附近的像素點，以上三個值之間的差異會比較明顯?；谝陨险J識，區(qū)域0和區(qū)域1分別被看成背景和目標，區(qū)域27被看成邊緣和噪聲。由于邊界和噪聲區(qū)域的像素點遠遠小于背景和目標的像素點，

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

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

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

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

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

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

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

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

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

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