模糊理論的圖像分割算法研究（三）

1、模糊理論的圖像分割算法研究（三）    4.遺傳操作 遺傳操作主要包括:選擇(selection )、交叉(crossover)、變異mutation)三個操作數(shù)。 1)選擇 選擇過程是模仿自然選擇現(xiàn)象，從父代種群中選出優(yōu)良個體。個體的適應(yīng)度值越大，在子代中將有更多的機(jī)會作為父代產(chǎn)生一個或多個子代個體。通常選用適應(yīng)度比例法(輪盤賭方式roulette wheel )確定選擇次數(shù)，該法中的各個體選擇概率和其適應(yīng)度值成比例。 2)交叉 最簡單的交叉操作為單點(diǎn)交叉:首先，對父代個體進(jìn)行隨機(jī)配對;然后，配對個體隨機(jī)設(shè)定交叉位置;最后，交換配對個體的部分信息。當(dāng)染

2、色體長度為l時，l-1有個交叉位置，單點(diǎn)交叉可實(shí)現(xiàn)l- 1種不同的交叉結(jié)果。 個體進(jìn)行隨機(jī)配對;然后，配對個體隨機(jī)設(shè)定交叉位置;最后，交換配對個體的部分信息。當(dāng)染色體長度為l時，l-1有個交叉位置，單點(diǎn)交叉可實(shí)現(xiàn)l- 1種不同的交叉結(jié)果。 父代個體a 10011|011        10011100 新個體a 父代個體b 01101|100        01101011 新個體b 3)變異 變異操作隨機(jī)選擇變異基因序號，根據(jù)一定的變異概率pm對該序號基

3、因進(jìn)行變異。對于二進(jìn)制編碼個體通常采用0變?yōu)閘， 1變?yōu)?。    1 0 0 1 1 0 1             1 0 1 1 0 1      變異位 5.控制參數(shù) 控制參數(shù)主要有:種群規(guī)模、迭代次數(shù)、交叉概率、變異概率等。對此標(biāo)準(zhǔn)遺傳算法都設(shè)為固定值。標(biāo)準(zhǔn)遺傳算法的特點(diǎn)是: 1)輪盤賭選擇方法: 2)隨機(jī)配對; 3)單點(diǎn)交叉，生成兩個子代個體: 4)種群內(nèi)允許相同個體出現(xiàn)。 可見，遺傳算法從任一初始化種群

4、出發(fā)，通過選擇(使優(yōu)秀個體有更多機(jī)會傳給子代)，交叉(體現(xiàn)優(yōu)秀個體間的信息交換)，變異(引入新的個體，保持種群的多樣性)操作種群一代一代的進(jìn)化到搜索空間中最優(yōu)點(diǎn)附近，直至收斂到最優(yōu)解點(diǎn)。遺傳算法不是直接作用在問題空間中，而是編碼空間中，而且遺傳操作非常簡單。這使得遺傳算法具有了簡單，通用，魯棒性強(qiáng)的特點(diǎn)。 第六章 基于遺傳算法的最大類間方差分割法 6.1 普通最大類間方差法（otsu法）簡介 由 otsu于 1978 年提出的最大類間方差法以其計(jì)算簡單、穩(wěn)定有效而一直廣為使用。該方法又稱為大津閾值分割法，是在判決分析最小二乘法原理的基礎(chǔ)上推導(dǎo)得出的，算法較為簡單。此方法由于其簡便性和分割準(zhǔn)確性

5、在圖像分割中被大量采用，但是缺點(diǎn)在于與，與后文所述的基于遺傳算法最大類間方差法相比，要求得最佳閾值，需要遍歷灰度范圍0l-1內(nèi)的所有像素并計(jì)算方差，最后比較得出最大方差，計(jì)算量大同時效率也很低，運(yùn)算時間偏長。25。 基本思路：選取的最佳閾值t應(yīng)當(dāng)使得不同類間的分離性最好。首先計(jì)算基于直方圖得到各分割特征值的發(fā)生概率，并以閾值變量t將分割特征值分為兩類，然后求出每一類的類內(nèi)方差及類間方差，選取使得類間方差最大，類內(nèi)方差最小的t作為最佳閾值。具體步驟如下： 設(shè)原始灰度圖像灰度級為l，灰度級為i的象素點(diǎn)數(shù)目為ni，則圖像的全部象素?cái)?shù)為    按閾值t可將所有象

6、素劃分兩類：c0= (0,1,2,t)和c1 = (t +1,t + 2,l -1) 。而c0和c1類的類出現(xiàn)概率w及均值 分別由下列各式給出：    式中： 。 不難得出，對任何t值，下式都能成立：    c0和c1類的方差可由下式求得：      定義類內(nèi)方差w、類間方差b、總體方差t 為：    引入    則最佳閾值t*可選擇為： t* = max(t) 在圖像處理過程中，原有的

7、圖像分割方法都不可避免的會產(chǎn)生誤差，這些誤差會影響到圖像處理和識別的效果。如何使這些誤差最小是使計(jì)算機(jī)視覺達(dá)到實(shí)用化的重要要求。遺傳算法其固有的并行性和不易陷入局部最優(yōu)的特點(diǎn)使之非常適于大規(guī)模搜索空間的尋優(yōu)，因此，己廣泛應(yīng)用于圖像處理領(lǐng)域。圖像分割是一個在復(fù)雜的參量空間中尋找最優(yōu)分割參量的問題，遺傳算法可以有效的尋找參量空間的全局最優(yōu)值，從而為解決圖像分割中的參量選擇難題提供了有力的保證。本章將著重討論基于遺傳算法的最大類間方差分割法在圖像分割中的應(yīng)用。 6.2  最大類間方差圖像分割的遺傳算法描述 正如前文所述，最大類間方差的求解過程就是在解空間中找到一個最優(yōu)解，使得類間方差最大。

8、為了改進(jìn)普通最大類間方差法，采用遺傳算法，求其尋找最優(yōu)解的過程進(jìn)行改進(jìn)。遺傳算法的最大類間方差法步驟如下: 1)  建立初始種群并編碼。 在matlab中，通過函數(shù)crtbp建立初始種群，在0255之間以同等概率隨機(jī)產(chǎn)生初始種群，通常初始種群的規(guī)模選取不易過大。隨機(jī)的在0255之間以同等概率生成40個個體a 1 a40作為第一次尋優(yōu)的初始的種群。通過函數(shù)bs2rv進(jìn)行二進(jìn)制碼和實(shí)值的轉(zhuǎn)變。因?yàn)閳D像的灰度級在0255之間，所以將染色體編碼成8位二進(jìn)制碼，它代表某個閾值。（函數(shù)源代碼參見附錄二、附錄三） 2) 適應(yīng)度函數(shù)計(jì)算各個體的適應(yīng)度值。采用公式 p1=s1/i; p2=s2/j f

9、(k)=i*j*(p1-p2)* (p1-p2)/(256*256) 作為適應(yīng)度函數(shù)對個體進(jìn)行適應(yīng)度計(jì)算。式中，f(k)為適應(yīng)度函數(shù)；i為目標(biāo)圖像的像素?cái)?shù)j為背景圖像的像素?cái)?shù)；s1 為目標(biāo)圖像的像素和，s2為背景圖像的像素和。（函數(shù)源代碼參見附錄四）3) 選擇：: 與標(biāo)準(zhǔn)遺傳算法略有不同，本例未采用輪盤賭方法進(jìn)行選擇操作，而是以matlab中的高級函數(shù)select作為選擇程序。在這種方法中，需要設(shè)定代溝，即整個種群在每一代中沒有完全被復(fù)制，有部分剩余。本例設(shè)代溝ggap=0.9，即每次遺傳后子代數(shù)量為父代的90%。（函數(shù)源代碼參見附錄五）。 4)   交叉: 在matlab

10、中使用高級函數(shù)recombin實(shí)現(xiàn)。即在當(dāng)前種群中每次選取兩個個體按設(shè)定的交叉概率（0.7）進(jìn)行交叉操作，生成新的一代種群; （函數(shù)源代碼參見附錄六）。 5)  變異: 在matlab中使用函數(shù)mut實(shí)現(xiàn)。即根據(jù)一定的變異概率pm，選取當(dāng)前種群的每一行對應(yīng)一個個體并用概率pm變異每一個元素，從而形成新一代群體。（函數(shù)源代碼參見附錄七） 6)  終止 本程序中選擇指定代數(shù)（50代）作為尋優(yōu)循環(huán)跳出的判斷條件。判斷跳出條件是否滿足，若不滿足，則以新生成的群體作為第一代群體，轉(zhuǎn)到步驟3繼續(xù)尋優(yōu)，否則轉(zhuǎn)到步驟7。 7)  將最后一代群體中適應(yīng)度最大的個體作為最優(yōu)結(jié)果，將其

11、反編碼（采用bs2rv函數(shù)），即為所求的最佳分割閾值。 6.3  實(shí)驗(yàn)結(jié)果與效果對比圖 為了驗(yàn)證算法的效果，選用一幅she的jpg圖像進(jìn)行實(shí)驗(yàn)，原始圖像顯示： 圖6.1 原始圖像 對上圖進(jìn)行灰度變化后的灰度圖像如下：    圖6.2 灰度圖象 在對灰度圖像轉(zhuǎn)化為索引圖像并將其數(shù)據(jù)類型轉(zhuǎn)化為雙精度型之后的圖片如下：    圖6.3 索引圖像 此時，就可對上圖進(jìn)行基于遺傳算法的最大類間方差分割法進(jìn)行處理了。設(shè)定初始群體的數(shù)目n=40，交叉概率p c=0. 9，代溝為0.9，變異率為pm采用默認(rèn)值。最大迭代數(shù)g=50。實(shí)驗(yàn)結(jié)果及數(shù)據(jù)如下： 通過50次迭代尋優(yōu)后，找到最優(yōu)化閾值m=162:    圖6.4