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

黃 猛 唐 琳 胡世安等

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

關鍵詞:目標識別;圖像分割;自適應;遺傳算法;適應度

中圖分類號:TP391

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

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

1遺傳算法

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

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

2.1 圖像分割原理

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

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

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

2.2 圖像分割的改進遺傳算法實現

使用改進的自適應遺傳算法實現分裂合并圖像分割的方法具體如下。

2.2.1 染色體編碼

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

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

2.2.2 適應度函數

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

(1) 區域一致性度量

(2) 邊緣模糊性度量。

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

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

(1) 選擇算子。

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

(2) 交叉算子。

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

圖2給出了交叉操作的一個示例,子個體Child的第5～10位基因繼承了個體玃2,其余位的基因繼承了個體玃1。而第11位被改變為玶5,第7位被改變為r7。

(3) 變異算子。

變異操作結合局部對比度設計┮恢知動態變異算子。所謂局部對比度是用來刻畫區域邊界信息模糊性的一種度量。

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

2.2.4 交叉和變異概率的自適應選擇

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

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

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

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

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

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

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

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

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

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

3 圖像分割仿真試驗

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

4 結 語

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

參 考 文 獻

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

[2]李敏強,寇紀淞.遺傳算法的基本理論與應用[M].北京:科學出版社,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]李俊山,李旭輝.數字圖像處理[M].北京:清華大學出版社,2007.

[5]王小平,曹立明.遺傳算法[CD2]理論、應用與軟件實現[M].西安:西安交通大學出版社,2002.

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

[7]云慶夏,黃光球,王戰權.遺傳算法和遺傳規劃[M].北京:冶金工業出版社,1997.

[8]李麗.基于遺傳算法的艦船航行路徑規劃技術研究[D].哈爾濱:哈爾濱工程大學,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年出生,江蘇徐州人,工程師。研究方向為算法分析、通信工程。