基于改進遺傳算法的圖像邊緣特征提取*

喬玲玲　毛曉菊

(商丘學院計算機工程學院　商丘　476113)

?

基于改進遺傳算法的圖像邊緣特征提取*

喬玲玲毛曉菊

(商丘學院計算機工程學院商丘476113)

摘要遺傳算法作為一種實用、穩健的優化搜索算法，已經滲透到許多學科及工程領域，在數字圖像處理中的應用亦日趨廣泛。為了能夠快速有效地提取出圖像的邊緣，對遺傳算法的選擇、交叉和變異算子分別進行了改進，并將其應用到圖像邊緣特征提取中。實驗結果表明，改進遺傳算法在保證有效地提取出邊緣的基礎上，提高了收斂性能，是一種有效的、可靠的優化算法，具有一定的實用價值。

關鍵詞遺傳算法; 邊緣特征提取; 閾值; 圖像分割

Class NumberTP391

1引言

在對圖像的研究分析中，多數情況下只對其中的某些部分感興趣，例如一幅遙感圖像，從軍事的角度可能只對機場、導彈基地、兵工廠等軍事目標比較關心；而從其它的角度如環境生態方面考慮，則只對森林、濕地、草地等目標感興趣。這些目標在圖像中形成具有獨特性質的區域，為了對其進行識別和分析，需要把這些區域分離出來，然后提取區域所具有的特征，進而對其識別和分類，這就是圖像分割要研究的問題。在對圖像分割過程中，不可避免的會存在一些誤差，這些誤差會影響圖像處理的效果，如何使這些誤差最小是使機器視覺達到實用化的重要要求。遺傳算法在這些圖像分割中的優化計算方面找到了用武之地。

2遺傳算法描述

2.1基本思想

遺傳算法類似于自然進化，通過作用于染色體上的基因尋找好的染色體來求解問題。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產生的每個染色體進行評價，并基于適應值來選擇染色體，使適應性好的染色體有更多的繁殖機會。在遺傳算法中，通過隨機方式產生若干個所求解問題的數字編碼，即染色體，形成初始群體；通過適應度函數給每個個體一個數值評價，淘汰低適應度的個體，選擇高適應度的個體參加遺傳操作，經過遺傳操作后的個體集合形成下一代新的種群，對這個新種群進行下一輪進化。遺傳算法的具體描述如下：

1) 初始化群體；

2) 計算群體上每個個體的適應度值；

3) 按由個體適應度值所決定的某個規則選擇將進入下一代的個體；

4) 按概率Pc進行交叉操作；

5) 按概率Pm進行突變操作；

6) 沒有滿足某種停止條件，則轉第2)步，否則進入7)；

7) 輸出種群中適應度值最優的染色體作為問題的滿意解或最優解。

程序的停止條件最簡單的有如下兩種：完成了預先給定的進化代數則停止；種群中的最優個體在連續若干代沒有改進或平均適應度在連續若干代基本沒有改進時停止。

2.2選擇操作

選擇操作也叫復制操作，根據個體的適應度函數值所度量的優、劣程度決定它在下一代是被淘汰還是被遺傳。一般地說，選擇將使適應度較大(優良)個體有較大的存在機會，而適應度較小(低劣)的個體繼續存在的機會也較小。最常用的選擇算子是基本遺傳算法中的輪盤賭選擇[1]和比例選擇算子[2]。但對于各種不同的問題，它們并不是最合適的選擇算子，因此對選擇算子進行改進，采用確定式采樣選擇[3]。

確定式采樣選擇方法的基本思想是按照一種確定的方式來進行選擇操作。其具體操作過程是：

1) 設群體大小為N，各個個體的適應度為Fi(i=1，2，…，N)，計算群體中各個個體在下一代群體中的期望生存數目Ni，如式(1)所示：

(1)

2.3交叉操作

遺傳算法中的所謂交叉運算，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區別于其他進化算法的重要特征，它在遺傳算法中起著關鍵作用，是產生新個體的主要方法。

本文采用非等概率融合單點交叉算子，該方法融合了“非等概率選擇交叉位置”[4～5]和“應用邏輯操作”兩種方法的優點。首先非等概率地選取交叉位置，然后對交叉位置右邊的基因進行邏輯操作，產生新的后代。具體操作如下：等概率產生一個0到length-1(length為編碼長度)的隨機整數T，當T=0或T=1時選擇第一個基因為交叉位置，否則選取第T個基因為交叉位置。然后對兩個父輩個體的T十1位到length位進行邏輯操作，用“與”操作產生后代1，用“或”操作產生后代2。

2.4變異操作

遺傳算法中的所謂變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。

對變異算子的一個改進方向是根據群體的進化程度調整變異概率的值[6]，其基本思想為：當群體比較集中時，意味著它可能陷于局部極值或存在早熟現象，于是對它進行一個大變異[7]操作，獨立隨機地產生新的個體，以便求出全局最優值或脫離早熟現象。變異概率如公示(2)所示：

(2)

采用最大適應度Fmax、最小適應度Fmin、適應度平均值Favg這三個變量來衡量群體適應度的集中程度，然后根據適應度集中程度，決定是否采取大變異操作。同時采取最優保存策略來保證最優個體不被大的變異概率Pm破壞掉。

3基于閾值的圖像邊緣特征提取

本文介紹一種基于閾值的圖像邊緣提取方法，其原則是：設灰度圖像的灰度級數目為level，則像素點的灰度級取值范圍為{0，1，2，…，level-1}，設(x，y)為灰度圖像中像素點的坐標，f(x,y)為該像素點的灰度級[8～9]。對于閾值t，若像素點滿足下列條件之一，則認為該點為圖像邊緣。

1)f(x,y)≥t且f(x-1,y)

2)f(x,y)≤t且f(x-1,y)>t

3)f(x,y)≥t且f(x,y-1)

4)f(x,y)≤t且f(x,y-1)>t

這種方法具有良好的抗噪聲性能，可以檢測出有效的邊緣[10]。判斷最優閾值的方法是，檢驗出的邊緣數目最多的閾值即為最優閾值。對于不同的閾值，可以檢驗出的邊緣數目也不同。

4實驗結果及分析

圖1　閾值分割的遺傳算法框圖

在這里，本文的控制參數如下：群體規模N為20，交叉概率為0.85，變異概率為0.01。遺傳算法運行代數為30代，當算法執行到最大代數或經過10代未進化(群體的最高適應度未發生變化)，就認為得到了最優閾值，跳出遺傳運算，得到圖像的邊緣提取結果。算法的流程圖如圖1所示。

本文對美女圖像進行實驗，實驗結果如圖2和圖3所示。

圖2　美女圖像

圖3　GA

選用遺傳算法對于某一優化問題尋優收斂所需的平均進化次數作為檢驗指標。所謂平均進化次數是指，對于某一目標函數重復地做尋優試驗而得到的進化次數的平均值。

每次試驗結果可能不同，因此本文對于圖像的分割法進行了30次試驗。取其平均值作為檢驗指標。得到表1所示的試驗數據。

表1　美女圖像的性能指標

從表1可以看出，窮盡法得到的邊緣是實際最優解。GA收斂到最優解的能力比較強，得到的閾值很接近最優解。

5結語

本文以遺傳算法的未收斂次數和平均進化次數兩個評價指標為參考，將遺傳算法應用于圖像的邊緣特征提取中，試驗結果表明，遺傳算法在保證有效地提取出邊緣的基礎上，提高了收斂性能。本文雖然對遺傳算法的理論及其在圖像的邊緣特征提取中的應用作了一些有益的研究，但無論是遺傳算法理論本身還是其在圖像邊緣特征提取中的應用和研究都有待進一步探討和完善。因此進一步的研究遺傳算法以及遺傳算法和其它方法的結合及其在圖像邊緣特征提取中的應用，將對數字圖像的智能信息處理有一定的影響。

參 考 文 獻

[1] 李敏強,寇紀淞,林丹,等.遺傳算法的基本理論與應用[M].北京:科學出版社,2002:512-557.

LI Minqiang, KOU Jisong, LIN Dan, et al. The basic theory and application of genetic algorithm[M]. Beijing: Science Press,2002:512-557.

[2] 郭東偉,周春光,劉大有.遺傳算法取代時間的分析[J].計算機研究和發展,2001,38(10):1211-1216.

GUO Dongwei, ZHOU Chunguang, LIU Dayou. Analysis of Takeover Time for Genetic Algorithms[J]. Journal of Computer Research & Development,2001,38(10):1211-1216.

[3] 王永良,陳輝,萬群,等.空間譜估計理論與算法[M].北京:清華大學出版社,2004:78-102.

WANG Yongliang, CHEN Hui, WAN Qun, et al. Spatial Spectral Estimation Theory And Algorithm[M]. Beijing: Tsinghua University Press,2004:78-102.

[4] 章坷,劉貴忠.交叉位置非等概率選取的遺傳算法[J].信息與控制,1997,26(1):53-60.

ZHANG Ke, LIU Guizhong. Selecting Crossover Site With Unequal Probability In Genetic Algorithms[J]. Information and Control,1997,26(1):53-60.

[5] M. Srinivas, L. M. Patnaik. Adaptive probabilities of crossover and Mutation in Genetic Algorithm[J]. IEEE Transactions On Systems, Man and Cybernetics,1994,24(4):656-667.

[6] 高艷霞,劉峰,王道洪.改進型遺傳算法及其應用研究[J].上海大學學報,2004,10(suppl):249-253.

GAO Yanxia, LIU Feng, WANG Daohong. Modified Genetic Algorithm and Its Application[J]. Journal of Shanghai University,2004,10(suppl):249-253.

[7] 馬均水,劉貴忠,賈玉蘭.改進遺傳算法搜索性能的大變異操[J].控制理論與應用,1998,15(3):404-408.

MAO Junshui, LIU Guizhong, JIA Yulan. Improved Genetic Algorithm on Search of Big Mutation Operation[J]. Control Theory and Applications,1998,15(3):404-408.

[8] 吳謹,李娟,劉成云,等.基于最大熵的灰度閾值選取方法[J].武漢科技大學學報:自然科學版,2004,27(1):58-60.

WU Jin, LI Juan, LIU Chengyun, et al. A Method for Gray2Level Threshold Selection Based on Maximum Entropy[J]. J. of Wuhan Uni. of Sci. & Tech.,2004,27(1):58-60.

[9] Lee S U, Chung S Y, Park R H. A comparative study of global thresholding Techniques for segmentation Computer Vision[J]. Graphics and Image Processing,1990,52:171-190.

[10] R. Kohler. A segmention system based on thresholding[J]. Computer Vision, Graphics and Image Processing,1981,15:319-338.

收稿日期:2016年1月12日,修回日期:2016年2月28日

作者簡介:喬玲玲,女,碩士研究生,講師,研究方向：圖像處理，物聯網。毛曉菊,女,講師,研究方向：計算機網絡，圖形圖像。

中圖分類號TP391

DOI:10.3969/j.issn.1672-9722.2016.07.035

Edge Feature Abstract of Image Based on Improved Genetic Algorithm

QIAO LinglingMAO Xiaoju

(Department of Computer, Shangqiu University, Shangqiu476113)

AbstractAs a kind of practical and sane optimum searching algorithm, the genetic algorithms has already permeated into many disciplines and project fields, whose application in digital image processing is also extensive day by day. In order to quickly and efficiently extract the edge of the image, in this paper, the selection, crossover and mutation operator of genetic algorithm are improved, and it is applied to extract the edge of the image. The experimental results show that improved gentic algorithm can detect satisfactory edges as well as improve convergence, which is a kind of efficient and reliable optimization arithmetic, having some applied value.

Key Wordsgenetic algorithm, edge feature abstract, threshold, image segmentation