黃 猛 唐 琳 胡世安等

摘 要:圖像分割是圖像分析和目標(biāo)識(shí)別中的關(guān)鍵技術(shù)之一。在傳統(tǒng)圖像分割方法的基礎(chǔ)上,提出一種將改進(jìn)的自適應(yīng)遺傳算法與合并分裂法相結(jié)合的圖像分割算法。針對(duì)遺傳算法運(yùn)算速度低,容易陷入局部最優(yōu)值、早熟收斂等缺點(diǎn),在此通過對(duì)遺傳操作算子的改進(jìn)、適應(yīng)度評(píng)價(jià)函數(shù)的科學(xué)設(shè)計(jì)以及交叉和變異概率的自適應(yīng)調(diào)整來(lái)降低圖像分割產(chǎn)生的誤差。計(jì)算機(jī)仿真結(jié)果證明,該算法能夠取得較好的圖像分割效果。

關(guān)鍵詞:目標(biāo)識(shí)別;圖像分割;自適應(yīng);遺傳算法;適應(yīng)度

中圖分類號(hào):TP391

圖像分割是圖像分析和目標(biāo)識(shí)別中的關(guān)鍵技術(shù)之一。圖像分割過程中,難免會(huì)產(chǎn)生一些誤差。這些誤差將直接影響到圖像處理的效果和目標(biāo)識(shí)別的準(zhǔn)確性,如何使這些誤差降到最小是圖像分割的重要指標(biāo)。

遺傳算法作為一種概率搜索的尋優(yōu)算法,因其在解決非線性問題上具有良好的適用性,在圖像分析領(lǐng)域得到了廣泛的應(yīng)用。但是傳統(tǒng)遺傳算法本身也存在著┮恍┆缺陷,如早熟、局部最優(yōu)解、占據(jù)較大的存儲(chǔ)空間和運(yùn)算時(shí)間,并且在實(shí)際應(yīng)用中缺乏對(duì)特定知識(shí)的利用,保證不了對(duì)圖像分割的計(jì)算效率和可靠性要求。為了將圖像分割過程中產(chǎn)生的誤差降至最小,本文結(jié)合傳統(tǒng)的圖像分割技術(shù),提出一種將改進(jìn)的遺傳算法與合并分裂法相結(jié)合的圖像分割算法,通過對(duì)交叉和變異概率的自適應(yīng)調(diào)整,降低圖像分割產(chǎn)生的誤差。

1遺傳算法

遺傳算法( Genetic Algorithm,GA) 基于達(dá)爾文的進(jìn)化論和孟德爾的自然遺傳學(xué)說(shuō),是模擬遺傳選擇和自然淘汰的生物進(jìn)化過程中一種隨機(jī)搜索與全局優(yōu)化算法。1975年,Holland在其專著中提出了GA的概念和方法,因其具有很強(qiáng)的解決問題能力和廣泛的適應(yīng)性,因而近年來(lái)滲透到研究與工程的各個(gè)領(lǐng)域,取得了良好的效果[2,3]。遺傳算法利用某種編碼技術(shù)將問題的解轉(zhuǎn)化成為染色體的數(shù)據(jù)串,其基本思想是模擬由這些染色體數(shù)據(jù)串組成群體的進(jìn)化過程。遺傳算法通過有組織、隨機(jī)地交換信息來(lái)重新結(jié)合那些適應(yīng)性好的串,在每一代中,利用上一代結(jié)果中適應(yīng)性好的位和段生成一個(gè)新的串的群體;作為額外添加,偶爾也要在串的結(jié)構(gòu)中嘗試用新的位和段來(lái)替代原有部分。

2 基于改進(jìn)遺傳算法的分裂合并圖像分割算法

2.1 圖像分割原理

圖像分割的步驟如下:首先,將圖像分割成不同的區(qū)域;其次,在分割后的相關(guān)區(qū)域中提取目標(biāo)特征;再次,根據(jù)提取的目標(biāo)特征以及相關(guān)的結(jié)構(gòu)信息對(duì)其進(jìn)行分類和識(shí)別;最后,給出對(duì)整幅圖像分析結(jié)果的描述信息。在圖像被分割成區(qū)域后,可以進(jìn)一步從中提取目標(biāo)特征,進(jìn)行目標(biāo)識(shí)別,例如在海洋中識(shí)別出艦船等。

圖像的分割依據(jù)是根據(jù)圖像的灰度、顏色、紋理和邊緣等特征,把圖像分成各自滿足某種相似性準(zhǔn)則或具有某種同質(zhì)特征連通區(qū)域的集合。目前,圖像分割已經(jīng)有很多成熟的方法。本文針對(duì)圖像分割中引起的較大誤差,提出一種將改進(jìn)的自適應(yīng)遺傳算法與合并分裂法相結(jié)合的圖像分割算法,以有效降低圖像分割過程中產(chǎn)生的誤差。

分裂合并分割法的原理:從整個(gè)圖像出發(fā),根據(jù)圖像和各區(qū)域的不均勻性,把圖像或區(qū)域分裂成新的子區(qū)域;根據(jù)毗鄰區(qū)域的均勻性,把毗鄰的子區(qū)域合并成新的較大區(qū)域。設(shè)用R表示整個(gè)圖像,用R璱表示分割成的一個(gè)圖像區(qū)域;并假設(shè)同一區(qū)域R璱中的所有像素都滿足某一相似性準(zhǔn)則時(shí),P(R璱)=玊RUE,否則㏄(R璱)=獸ALSE。當(dāng)P(R璱)=玊RUE時(shí),不再進(jìn)一步分割該區(qū)域;當(dāng)P(R璱)=獸ALSE時(shí),繼續(xù)將該區(qū)域分成大小相同的四個(gè)更小的象限區(qū)域。在這種分割過程中,必定存在R環(huán)的每個(gè)子區(qū)域R璲與R璴的某個(gè)子區(qū)域R璳具有相同性質(zhì),也即P(R璲∪R璳)=玊RUE,這時(shí)就可以把R璲和R璳Ш喜⒆槌尚碌那域。

2.2 圖像分割的改進(jìn)遺傳算法實(shí)現(xiàn)

使用改進(jìn)的自適應(yīng)遺傳算法實(shí)現(xiàn)分裂合并圖像分割的方法具體如下。

2.2.1 染色體編碼

假設(shè)最大圖像分割區(qū)域數(shù)目為玭,則個(gè)體的染色體編碼為一個(gè)整數(shù)序列,即:

I璳={r璱|i=1,2,…,n}。式中:r璱對(duì)應(yīng)于一個(gè)固定位置的分區(qū)序號(hào);k為個(gè)體編號(hào)。

2.2.2 適應(yīng)度函數(shù)

遺傳算法中的一個(gè)個(gè)體對(duì)應(yīng)一個(gè)圖像分割,個(gè)體適應(yīng)度的評(píng)價(jià)實(shí)際上是對(duì)該個(gè)體所描述的圖像分割質(zhì)量的衡量。在沒有分割參照情況時(shí),圖像分割評(píng)價(jià)可以包括兩方面的內(nèi)容:區(qū)域一致性度量和邊緣模糊性度量。

(1) 區(qū)域一致性度量

(2) 邊緣模糊性度量。

前面討論局部對(duì)比度時(shí),只考慮兩個(gè)鄰接區(qū)域邊界部分的模糊性。所有區(qū)域邊界模糊性的綜合度量其公式如下:

遺傳算法中個(gè)體的適應(yīng)度評(píng)價(jià)可以采用上述兩種度量的綜合形式,以反映個(gè)體圖像在經(jīng)歷一系列分裂合并過程后圖像的分割質(zhì)量。個(gè)體的適應(yīng)度F計(jì)算為┮恢灤遠(yuǎn)攘縂與邊緣模糊性度量E的乘積形式,Ъ:

(1) 選擇算子。

選擇操作使用按比例的適應(yīng)度分配方法,個(gè)體的適應(yīng)度越高,其被選擇的概率就越大。輪盤賭是一種常用的選擇方法,其原理是:以個(gè)體的相對(duì)適應(yīng)度玃,將整個(gè)賭盤分成大小不同的扇面,個(gè)體被選擇的概率與該扇面的圓心角成正比。圓心角越大,該扇面被選擇的可能性就越大;圓心角越小,該扇面被選擇的可能性就越小。于是各個(gè)扇面的大小就決定了各個(gè)體被遺傳到下一代群體中的概率。

(2) 交叉算子。

交叉操作采用改進(jìn)的兩點(diǎn)交叉法,編碼序列中的基因碼在交叉操作后允許重復(fù),正是依靠產(chǎn)生重復(fù)基因碼,圖像區(qū)域才得以進(jìn)一步分裂或合并。此外,如果區(qū)域r璱與其毗鄰的區(qū)域r璲合并,即I璳[i]=i,I璳[j]=i,則其他已經(jīng)合并到區(qū)域r璲的區(qū)域r璴也相應(yīng)地合并到區(qū)域r璱,即I璳[l]=i,因此所有合并到區(qū)域r璱的區(qū)域基因碼都是i。И

圖2給出了交叉操作的一個(gè)示例,子個(gè)體Child的第5～10位基因繼承了個(gè)體玃2,其余位的基因繼承了個(gè)體玃1。而第11位被改變?yōu)楂r5,第7位被改變?yōu)閞7。

(3) 變異算子。

變異操作結(jié)合局部對(duì)比度設(shè)計(jì)┮恢知?jiǎng)討B(tài)變異算子。所謂局部對(duì)比度是用來(lái)刻畫區(qū)域邊界信息模糊性的一種度量。

在一個(gè)分割對(duì)應(yīng)的個(gè)體基因碼中,變異操作分兩個(gè)步驟:首先計(jì)算個(gè)體編碼序列中所有基因碼表示區(qū)域的局部對(duì)比度,按輪盤賭法計(jì)算一個(gè)個(gè)體編碼中基因變異概率,概率的大小與其對(duì)應(yīng)的區(qū)域局部對(duì)比度成正比;接下來(lái)確定區(qū)域的分裂或者合并,若某區(qū)域的基因變異概率大于預(yù)定變異概率P璵,則對(duì)該區(qū)域隨機(jī)的選擇發(fā)生合并或分裂。區(qū)域合并對(duì)象為與之鄰接區(qū)域中相對(duì)距離u﹊j最小者,而分裂只發(fā)生在該區(qū)域已經(jīng)與其他區(qū)域合并時(shí),從其他區(qū)域分離出來(lái)。圖4為一個(gè)個(gè)體變異的示例,假定第二位和第五位基因變異概率大于預(yù)定變異概率P璵,則區(qū)域r5和r7被選擇決定合并或分裂。若決定r5合并,與r5相對(duì)距離最小者為r2,則r5并入r2,┑諼濯位基因碼變?yōu)閞2;若決定r7分裂,由于此前r7已與r11合并,這時(shí)將r7分離出來(lái),則第7位基因碼不變,第11位和12位變?yōu)閞11。И

2.2.4 交叉和變異概率的自適應(yīng)選擇

多數(shù)情況下,種群中不同個(gè)體的適應(yīng)度不盡相同,因此可以用適應(yīng)度分布的離散程度來(lái)表征種群的“早熟”程度。種群在進(jìn)化過程中發(fā)生“早熟”的主要表現(xiàn)是:種群內(nèi)適應(yīng)度暫時(shí)最大的一些個(gè)體相互重復(fù)或趨同,使得它們有較大的概率參與下一代的選擇復(fù)制操作,且它們之間交叉后的子代也不會(huì)與父代有太大的變化,導(dǎo)致遺傳算法尋優(yōu)過程十分緩慢,降低搜索效率。因此,要正確判斷一個(gè)種群是否會(huì)發(fā)生“早熟”主要看這個(gè)種群當(dāng)前適應(yīng)度最大的那些個(gè)體是否重復(fù)或相互趨同?；诖怂枷?在此給出了基于適應(yīng)度分布離散程度來(lái)評(píng)價(jià)種群“早熟”程度的指標(biāo):

設(shè)第t代種群由個(gè)體X1璽,X2璽,…,X琈璽構(gòu)成,適應(yīng)度分別為F1璽,F2璽,…,F琈璽。種群個(gè)體的平均適應(yīng)度璽=∑Mi=1F琲璽/M;最優(yōu)個(gè)體適應(yīng)度為F﹖玬ax;﹖玬ax代表適應(yīng)度大于璽的個(gè)體平均適應(yīng)度。定義F﹖玬ax與﹖玬axе間的差值:[JP]

ИЕぁ=F﹖玬ax-﹖玬ax猍JY](14)И

式中:Еぁ溆美幢碚髦秩旱摹霸縭斐潭取?。可诣€闖,當(dāng)Δ′增大時(shí),種群趨于發(fā)散;Δ′減小時(shí),種群趨于相同。此方法只計(jì)算F﹖玬ax與﹖玬ax的差值,不涉及適應(yīng)度低于平均適應(yīng)度的個(gè)體,從而避免了那些適應(yīng)度較差的個(gè)體對(duì)Δ′У撓跋,更能反映種群中那些適應(yīng)度較好的個(gè)體之間的趨同程度。

選擇合適的遺傳算子執(zhí)行概率,是遺傳算法能否收斂到最優(yōu)解的關(guān)鍵之一[9]。在傳統(tǒng)的遺傳算法中,交叉概率玃璫、變異概率玃璵等控制參數(shù)與種群進(jìn)化過程無(wú)關(guān),從始至終都保持定值。近年來(lái)的研究表明,控制參數(shù)對(duì)系統(tǒng)性能有重要的影響。交叉概率玃璫的高低將決定解群體的更新和搜索速度的快慢。玃璫太大會(huì)使算法的探測(cè)能力越強(qiáng),越容易探測(cè)到新的優(yōu)良個(gè)體,增加算法的收斂速度;玃璫太小會(huì)使搜索停滯不前。變異對(duì)于保持解群體結(jié)構(gòu)的多樣性,防止算法“早熟”是一種重要手段:變異概率玃璵太小時(shí),難以產(chǎn)生新的基因塊;┆玃璵太大又會(huì)使遺傳算法變成隨機(jī)搜索,從而失去其優(yōu)良特性。

由此可知,交叉概率和變異概率對(duì)于遺傳算法的收斂性能都有重要的影響。

用不變的控制參數(shù)來(lái)控制遺傳進(jìn)化,很容易導(dǎo)致“早熟”,降低算法的搜索效率。目前,調(diào)整遺傳算法中控制參數(shù)較好的方法是動(dòng)態(tài)自適應(yīng)技術(shù),其基本思想是使玃璫,玃璵在進(jìn)化過程中根據(jù)種群的實(shí)際情況,隨機(jī)調(diào)整大小[5]。

具體做法為:當(dāng)種群趨于收斂時(shí),減小玃璫,增大玃璵,即降低交叉的概率,提高變異的概率,以保持種群的多樣性,避免“早熟”;當(dāng)種群個(gè)體發(fā)散時(shí),增大玃璫,減小玃璵,即提高交叉的概率,降低變異的概率,使種群趨于收斂,增加算法的收斂速度。

根據(jù)前述評(píng)價(jià)種群“早熟”程度的指標(biāo)Δ′,給出自適應(yīng)調(diào)整遺傳算法控制參數(shù)的策略,使得交叉概率玃璫、變異概率玃璵在進(jìn)化過程中隨著Δ′的變化而改變,該策略數(shù)學(xué)公式為:

式中:k1,k2>0。由于Δ′始終大于或等于0,所以玃璫取值范圍在[0.5,1]之間,玃璵的取值范圍在[0,0.5]之間。從上式可見,在進(jìn)化過程中,玃璫,玃璵根據(jù)Δ′取值的不同而動(dòng)態(tài)地自適應(yīng)調(diào)整:當(dāng)種群個(gè)體趨于離散(即Δ′變大)時(shí),玃璫增大,玃璵減小,種群開發(fā)優(yōu)良個(gè)體能力增強(qiáng);當(dāng)種群個(gè)體趨于收斂(即Δ′變小)時(shí),玃璫減小,玃璵增大,種群產(chǎn)生新個(gè)體能力增強(qiáng)。

3 圖像分割仿真試驗(yàn)

圖5給出了一幅軍艦圖片的分割過程,原圖是大小為256×256的灰度圖像,使用上述算法對(duì)其進(jìn)行分割測(cè)試。種群大小為60,交叉和變異概率自適應(yīng)調(diào)整系數(shù)玨1=2.0,k2=4.0,預(yù)定分割區(qū)域最小和最大面積α,β分別取5,20。圖5為挑選出若干代中最佳個(gè)體對(duì)應(yīng)的分割結(jié)果,大約到200代后達(dá)到比較好的分割效果。[LL]

4 結(jié) 語(yǔ)

對(duì)傳統(tǒng)圖像分割算法進(jìn)行了改進(jìn)和擴(kuò)充,提出了┮恢知將改進(jìn)的自適應(yīng)遺傳算法與合并分裂法相結(jié)合的圖像分割算法。通過對(duì)每代種群“早熟”程度的判斷,實(shí)現(xiàn)對(duì)交叉和變異概率的自適應(yīng)調(diào)整;基于啟發(fā)式知識(shí)來(lái)設(shè)計(jì)允許基因重復(fù)的交叉算子,對(duì)標(biāo)準(zhǔn)遺傳算子進(jìn)行改進(jìn);并使用區(qū)域一致性度量和邊緣模糊性度量作為算法的適應(yīng)度函數(shù),符合圖像分割的實(shí)際情況。仿真結(jié)果證明,該算法能夠在較短的時(shí)間內(nèi)實(shí)現(xiàn)對(duì)原始圖像的分割,并取得較好的分割效果。

參 考 文 獻(xiàn)

[1]唐國(guó)新,陳雄,袁楊.基于改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(18):4 446[CD*2]4 449.

[2]李敏強(qiáng),寇紀(jì)淞.遺傳算法的基本理論與應(yīng)用[M].北京:科學(xué)出版社,2002.

[3]Holland J H.Adaptation in Natural and Artificial Systems:An Introductory Analysis with Applications to Biology,Control and Artificial Intelligence[M].MA:MIT Press,1992.

[4]李俊山,李旭輝.數(shù)字圖像處理[M].北京:清華大學(xué)出版社,2007.

[5]王小平,曹立明.遺傳算法[CD2]理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2002.

[6]Mat Buckland.游戲編程中的人工智能技術(shù)[M].吳祖增,沙鷹,譯.北京:清華大學(xué)出版社,2006.

[7]云慶夏,黃光球,王戰(zhàn)權(quán).遺傳算法和遺傳規(guī)劃[M].北京:冶金工業(yè)出版社,1997.

[8]李麗.基于遺傳算法的艦船航行路徑規(guī)劃技術(shù)研究[D].哈爾濱:哈爾濱工程大學(xué),2006.

[JP2][9]Grefenstette J J.Lamrckian Learning in Multiagent Environments[A].Proceedings of the Fourth International Conference on Genetic Algorithms[C].San Mateo,CA,1991:303[CD*2]310.[JP]

作者簡(jiǎn)介 黃 猛 男,1977年出生,江蘇徐州人,工程師。研究方向?yàn)樗惴ǚ治?、通信工程?/p>