喬玲玲　毛曉菊

(商丘學(xué)院計(jì)算機(jī)工程學(xué)院　商丘　476113)

?

基于改進(jìn)遺傳算法的圖像邊緣特征提取*

喬玲玲毛曉菊

(商丘學(xué)院計(jì)算機(jī)工程學(xué)院商丘476113)

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

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

Class NumberTP391

1引言

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

2遺傳算法描述

2.1基本思想

遺傳算法類似于自然進(jìn)化，通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題。與自然界相似，遺傳算法對(duì)求解問題的本身一無所知，它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)。在遺傳算法中，通過隨機(jī)方式產(chǎn)生若干個(gè)所求解問題的數(shù)字編碼，即染色體，形成初始群體；通過適應(yīng)度函數(shù)給每個(gè)個(gè)體一個(gè)數(shù)值評(píng)價(jià)，淘汰低適應(yīng)度的個(gè)體，選擇高適應(yīng)度的個(gè)體參加遺傳操作，經(jīng)過遺傳操作后的個(gè)體集合形成下一代新的種群，對(duì)這個(gè)新種群進(jìn)行下一輪進(jìn)化。遺傳算法的具體描述如下：

1) 初始化群體；

2) 計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值；

3) 按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代的個(gè)體；

4) 按概率Pc進(jìn)行交叉操作；

5) 按概率Pm進(jìn)行突變操作；

6) 沒有滿足某種停止條件，則轉(zhuǎn)第2)步，否則進(jìn)入7)；

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

程序的停止條件最簡(jiǎn)單的有如下兩種：完成了預(yù)先給定的進(jìn)化代數(shù)則停止；種群中的最優(yōu)個(gè)體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)時(shí)停止。

2.2選擇操作

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

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

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

(1)

2.3交叉操作

遺傳算法中的所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起著關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。

本文采用非等概率融合單點(diǎn)交叉算子，該方法融合了“非等概率選擇交叉位置”[4～5]和“應(yīng)用邏輯操作”兩種方法的優(yōu)點(diǎn)。首先非等概率地選取交叉位置，然后對(duì)交叉位置右邊的基因進(jìn)行邏輯操作，產(chǎn)生新的后代。具體操作如下：等概率產(chǎn)生一個(gè)0到length-1(length為編碼長(zhǎng)度)的隨機(jī)整數(shù)T，當(dāng)T=0或T=1時(shí)選擇第一個(gè)基因?yàn)榻徊嫖恢茫駝t選取第T個(gè)基因?yàn)榻徊嫖恢?。然后?duì)兩個(gè)父輩個(gè)體的T十1位到length位進(jìn)行邏輯操作，用“與”操作產(chǎn)生后代1，用“或”操作產(chǎn)生后代2。

2.4變異操作

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

對(duì)變異算子的一個(gè)改進(jìn)方向是根據(jù)群體的進(jìn)化程度調(diào)整變異概率的值[6]，其基本思想為：當(dāng)群體比較集中時(shí)，意味著它可能陷于局部極值或存在早熟現(xiàn)象，于是對(duì)它進(jìn)行一個(gè)大變異[7]操作，獨(dú)立隨機(jī)地產(chǎn)生新的個(gè)體，以便求出全局最優(yōu)值或脫離早熟現(xiàn)象。變異概率如公示(2)所示：

(2)

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

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

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

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

這種方法具有良好的抗噪聲性能，可以檢測(cè)出有效的邊緣[10]。判斷最優(yōu)閾值的方法是，檢驗(yàn)出的邊緣數(shù)目最多的閾值即為最優(yōu)閾值。對(duì)于不同的閾值，可以檢驗(yàn)出的邊緣數(shù)目也不同。

4實(shí)驗(yàn)結(jié)果及分析

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

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

本文對(duì)美女圖像進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2和圖3所示。

圖2　美女圖像

圖3　GA

選用遺傳算法對(duì)于某一優(yōu)化問題尋優(yōu)收斂所需的平均進(jìn)化次數(shù)作為檢驗(yàn)指標(biāo)。所謂平均進(jìn)化次數(shù)是指，對(duì)于某一目標(biāo)函數(shù)重復(fù)地做尋優(yōu)試驗(yàn)而得到的進(jìn)化次數(shù)的平均值。

每次試驗(yàn)結(jié)果可能不同，因此本文對(duì)于圖像的分割法進(jìn)行了30次試驗(yàn)。取其平均值作為檢驗(yàn)指標(biāo)。得到表1所示的試驗(yàn)數(shù)據(jù)。

表1　美女圖像的性能指標(biāo)

從表1可以看出，窮盡法得到的邊緣是實(shí)際最優(yōu)解。GA收斂到最優(yōu)解的能力比較強(qiáng)，得到的閾值很接近最優(yōu)解。

5結(jié)語

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

參 考 文 獻(xiàn)

[1] 李敏強(qiáng),寇紀(jì)淞,林丹,等.遺傳算法的基本理論與應(yīng)用[M].北京:科學(xué)出版社,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] 郭東偉,周春光,劉大有.遺傳算法取代時(shí)間的分析[J].計(jì)算機(jī)研究和發(fā)展,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] 王永良,陳輝,萬群,等.空間譜估計(jì)理論與算法[M].北京:清華大學(xué)出版社,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ìn)型遺傳算法及其應(yīng)用研究[J].上海大學(xué)學(xué)報(bào),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ìn)遺傳算法搜索性能的大變異操[J].控制理論與應(yīng)用,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ǐn),李娟,劉成云,等.基于最大熵的灰度閾值選取方法[J].武漢科技大學(xué)學(xué)報(bào):自然科學(xué)版,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日

作者簡(jiǎn)介:喬玲玲,女,碩士研究生,講師,研究方向：圖像處理，物聯(lián)網(wǎng)。毛曉菊,女,講師,研究方向：計(jì)算機(jī)網(wǎng)絡(luò)，圖形圖像。

中圖分類號(hào)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