一種改進的分裂合并圖像分割算法

黃 猛 唐 琳 胡世安等

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

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

中圖分類號:TP391

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

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

1遺傳算法

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

2 基于改進遺傳算法的分裂合并圖像分割算法

2.1 圖像分割原理

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

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

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

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

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

2.2.1 染色體編碼

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

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

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

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

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

(2) 邊緣模糊性度量。

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

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

(1) 選擇算子。

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

(2) 交叉算子。

交叉操作采用改進的兩點交叉法,編碼序列中的基因碼在交叉操作后允許重復(fù),正是依靠產(chǎn)生重復(fù)基因碼,圖像區(qū)域才得以進一步分裂或合并。此外,如果區(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給出了交叉操作的一個示例,子個體Child的第5～10位基因繼承了個體玃2,其余位的基因繼承了個體玃1。而第11位被改變?yōu)楂r5,第7位被改變?yōu)閞7。

(3) 變異算子。

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

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

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

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

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

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

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

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

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

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

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

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

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

3 圖像分割仿真試驗

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

4 結(jié) 語

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

參 考 文 獻

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

[2]李敏強,寇紀淞.遺傳算法的基本理論與應(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)用與軟件實現(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]

作者簡介 黃 猛 男,1977年出生,江蘇徐州人,工程師。研究方向為算法分析、通信工程。