求解圖像邊緣檢測(cè)的遺傳算法

陳桂霞

摘 要： 圖像邊緣檢測(cè)技術(shù)是圖像分析處理中的關(guān)鍵。以Sobel邊緣檢測(cè)方法為基礎(chǔ)，針對(duì)Sobel算子尋優(yōu)的困難性提出了應(yīng)用遺傳算法進(jìn)行圖像邊緣檢測(cè)的方案。為了更好地提高遺傳算法的全局收斂性能和求解精度，在遺傳算法中加入了自適應(yīng)機(jī)制和精英反向?qū)W習(xí)機(jī)制，從而提高了尋找最優(yōu)解的效率，在一定程度上遏制了算法的早熟現(xiàn)象和標(biāo)準(zhǔn)遺傳算法解精度較低的弱點(diǎn)。

關(guān)鍵詞： 圖像邊緣檢測(cè)； 遺傳算法； Sobel算子； 反向?qū)W習(xí)

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2018）11-73-03

Abstract： Image edge detection technology is the key to image analysis and processing. Based on the Sobel edge detection method， this paper proposes an image edge detection scheme based on the genetic algorithm for the difficulty of the optimization of the Sobel operator. In order to improve the global convergence performance and the accuracy of the genetic algorithm， the adaptive mechanism and elite reverse learning mechanism are added to the genetic algorithm to improve the genetic algorithm. The efficiency of finding the optimal solution， to a certain extent， curbed the premature convergence of the algorithm and the low accuracy of standard genetic algorithm.

Key words： image edge detection； genetic algorithm； Sobel operator； reverse learning

0 引言

基于內(nèi)容的圖像識(shí)別和理解，是新一代網(wǎng)絡(luò)搜索引擎的重要研究方向，而圖像邊緣檢測(cè)技術(shù)是其中的關(guān)鍵，它在圖像的分析處理中有著非常重要的意義。如何尋找與圖像真實(shí)邊緣線相對(duì)應(yīng)的實(shí)際邊緣，長(zhǎng)期以來(lái)一直是數(shù)字圖像處理領(lǐng)域的研究熱點(diǎn)，因?yàn)檫吘壍奶卣鞣从沉藞D像灰度的不連續(xù)性，它提供了一幅圖像的大量有效和有價(jià)值的信息。本文以Sobel[3]邊緣檢測(cè)方法為基礎(chǔ)，介紹一種改進(jìn)的遺傳算法圖像邊緣檢測(cè)方法，并通過在遺傳算法中加入自適應(yīng)變異算子和反向?qū)W習(xí)機(jī)制來(lái)提高遺傳算法的收斂能力。

1 數(shù)字圖像邊緣

對(duì)于一幅圖像，不同區(qū)域的灰度值是不相同的，而這些不同的區(qū)域之間往往是邊緣的體現(xiàn)，灰度值的不連續(xù)是形成圖像的主要原因。這種灰度值的不連續(xù)性可通過數(shù)學(xué)方法中的求導(dǎo)方法檢測(cè)出來(lái)。比較常見的經(jīng)典邊緣檢測(cè)方法一般都是通過一階導(dǎo)數(shù)和二階導(dǎo)數(shù)的求解來(lái)檢測(cè)圖像邊緣的灰度值。圖像灰度邊緣是非常復(fù)雜的，基于采取樣本的原因，獲得的實(shí)際圖像中的邊緣是有坡度的，一般可以用位置、朝向、幅度、均值、斜率這五個(gè)參數(shù)來(lái)描述。所謂邊緣檢測(cè)也常指通過計(jì)算獲得邊緣五個(gè)參數(shù)數(shù)據(jù)?；跈z測(cè)原理，可以采用多種不同的方法來(lái)檢測(cè)邊緣，主要包括基于梯度的邊緣檢測(cè)算子和二階導(dǎo)數(shù)算子。

2 Sobel邊緣檢測(cè)算子

在3×3鄰域內(nèi)做加權(quán)平均和差分運(yùn)算，以此為基礎(chǔ)，Sobel在另一個(gè)著名的圖像邊緣檢測(cè)算子Prewitt基礎(chǔ)上，提出了一個(gè)新穎的圖像邊緣算子—Sobel算子，其計(jì)算過程如公式1。

Sobel算子的兩個(gè)卷積算子模板分別是公式2和公式3。

因?yàn)镾obel算子將加權(quán)平均引入圖像的邊緣描述，它充分利用圖像本身的信息，對(duì)像素點(diǎn)上下左右的灰度值進(jìn)行加權(quán)運(yùn)算，依靠在圖像邊緣點(diǎn)處所到達(dá)的極值來(lái)完成圖像的邊緣檢測(cè)。該算子對(duì)于噪聲所產(chǎn)生的影響較小，能夠給噪聲產(chǎn)生一定的平滑作用，進(jìn)一步提供了相對(duì)準(zhǔn)確的邊緣配置信息。此外，由于描述圖像的信息被局部平均處理，會(huì)對(duì)圖像邊緣描述的準(zhǔn)確性產(chǎn)生一定的影響，所以檢測(cè)邊緣的過程可能會(huì)產(chǎn)生錯(cuò)誤信息。在對(duì)圖像邊緣檢測(cè)的精確度要求不高的情況下，Sobel算子仍然是一種運(yùn)算速度快，較為常用邊緣檢測(cè)算子。

3 面向圖像邊緣檢測(cè)的遺傳算法

3.1 遺傳算法的編碼設(shè)計(jì)

進(jìn)行圖像邊緣檢測(cè)時(shí)，由于圖像的灰度值范圍是0～255，可以用8位二進(jìn)制數(shù)表示一個(gè)解，進(jìn)而可將8位二進(jìn)制串當(dāng)作遺傳算法中的染色體。圖1表示灰度范圍條形值。例如染色體11111111代表的顏色如圖2所示，染色體01111101代表的顏色如圖3所示，染色體00101101代表的顏色如圖4所示。

3.2 適應(yīng)度函數(shù)設(shè)計(jì)

依據(jù)灰度圖像的特性，把一幅圖像分解成背景和目標(biāo)兩個(gè)部分。目標(biāo)和背景之間的方差值越大，表示組成圖像的兩部分差別越大，如果一部分背景被錯(cuò)分為目標(biāo)或者是目標(biāo)被錯(cuò)分為背景，則會(huì)導(dǎo)致兩部分的差別變小。所以，類間方差最大的分割則表明錯(cuò)分的概率最小。

假設(shè)f（x，y）是我們想要分割的客觀圖像，它的灰度范圍是{0，1，…，L-1}。通過閾值t，圖像像素將被分為公式4和公式5兩類。

C0和C1分別代表目標(biāo)和背景。這類圖像的平方誤差在C0和C1之間，表示為公式6。

這里t是閾值，ω0（t）是圖像灰度值小于閾值t的像素?cái)?shù)量。ω1（t）是圖像灰度值大于閾值t的像素?cái)?shù)量。μ0（t）是圖像灰度值小于閾值t的像素平均灰度值。μ1（t）是圖像灰度值大于閾值t的像素平均灰度值，使得σ（t）2最大值的t是最佳分割閾值。

3.3 求解圖像邊緣檢測(cè)的標(biāo)準(zhǔn)遺傳算法

將種群中的染色體應(yīng)用8位二進(jìn)制數(shù)進(jìn)行編碼，一條染色體代表一個(gè)解，基于上一節(jié)描述最大類間方差法作為遺傳算法的適應(yīng)度函數(shù)，則求解圖像邊緣檢測(cè)的標(biāo)準(zhǔn)遺傳算法步驟如下：

算法1 標(biāo)準(zhǔn)遺傳算法（GA[1]）

Step1. 利用Sobel算子逐點(diǎn)計(jì)算原始圖像從而獲取梯度圖像。

Step2. 應(yīng)用遺傳算法求解梯度圖像的最佳分割閾值。

Step2.1. 染色體初始化。在解空間內(nèi)，隨機(jī)生成40條染色體作為初始種群。

Step2.2. 交叉算子。隨機(jī)選擇兩條染色體，以單點(diǎn)交叉方式交叉，交叉概率設(shè)為0.6。

Step2.3. 變異算子。對(duì)各個(gè)染色體采用均勻變異算子，執(zhí)行變異。

Step2.4. 若算法符合停止條件，則輸出最佳閾值并終止算法；否則跳到Step2.2執(zhí)行。

Step3. 依據(jù)閾值大小，假如圖像的梯度值大于或等于閾值，便可以確定該點(diǎn)為最初始的邊緣點(diǎn)，該點(diǎn)方向就是邊界點(diǎn)的方向，否則就是一個(gè)無(wú)邊點(diǎn)。

3.4 遺傳算法的相關(guān)改進(jìn)

由于標(biāo)準(zhǔn)遺傳算法容易收斂于局部最優(yōu)，解精度低，所以要在標(biāo)準(zhǔn)遺傳算法中引入反向?qū)W習(xí)機(jī)制。考慮到在算法的進(jìn)化迭代過程中，適應(yīng)度優(yōu)秀的個(gè)體代表了種群的收斂和前進(jìn)方向，能夠更好地勘探新解，同時(shí)由于加強(qiáng)精英個(gè)體周圍的鄰域搜索，對(duì)于提高算法解的精度亦有幫助，所以針對(duì)種群的精英個(gè)體執(zhí)行反向?qū)W習(xí)策略。

為了提高運(yùn)算速度，設(shè)定一個(gè)概率p，產(chǎn)生以隨機(jī)數(shù)r=random（），當(dāng)r小于p時(shí)執(zhí)行精英反向搜索機(jī)制，否則執(zhí)行主體遺傳算法。

3.5 自適應(yīng)變異機(jī)制

為了更好地保護(hù)已求得的優(yōu)秀解不被丟失，需要引入一種自適應(yīng)變異算子。同時(shí)，為了使算法能夠較好地搜索優(yōu)秀個(gè)體周圍較小的鄰域，而對(duì)于適應(yīng)度較差的個(gè)體，則搜索其較大的鄰域，特引入自適應(yīng)變異率，其計(jì)算方法見公式7。該機(jī)制的變異概率能夠根據(jù)解的質(zhì)量自適應(yīng)地調(diào)整搜索區(qū)域，從而比較明顯地改善算法的搜索能力。

算法2 自適應(yīng)算子

Step1. 保存種群內(nèi)每一個(gè)個(gè)體的適應(yīng)度值。

Step2. 計(jì)算種群的適應(yīng)度總和，同時(shí)將最大的適應(yīng)度值保存。

Step3. 求解平均適應(yīng)度值并保存到average中。

Step4. 群體內(nèi)的個(gè)體執(zhí)行公式7的變異機(jī)制。

算法3 改進(jìn)的反向?qū)W習(xí)遺傳算法（IOBLGA[1]）

Begin

初始化群體p（t）；

while（停機(jī)不滿足） do

if rand（0，1）

執(zhí)行精英反向?qū)W習(xí)機(jī)制；

else

執(zhí)行自適應(yīng)遺傳算法；

endif

endwhile

end

4 仿真實(shí)驗(yàn)

為了驗(yàn)證算法的有效性，應(yīng)用JAVA實(shí)現(xiàn)該算法，并將標(biāo)準(zhǔn)遺傳算法（GA）與改進(jìn)遺傳算法（IOBLGA）進(jìn)行圖像邊緣檢測(cè)比較。兩個(gè)算法設(shè)定的種群規(guī)模、交叉概率、迭代次數(shù)均相同。設(shè)種群規(guī)模為40，交叉概率px=0.5，種群迭代次數(shù)30，兩個(gè)算法均單獨(dú)運(yùn)行30次，取各自的最佳效果圖。

將標(biāo)準(zhǔn)遺傳算法和改進(jìn)遺傳算法分別作用于同一幅圖，分別獲得邊緣檢測(cè)效果圖。對(duì)比兩個(gè)圖的求解效果，發(fā)現(xiàn)改進(jìn)遺傳算法在求解過程中所獲得的Sobel算子，較標(biāo)準(zhǔn)遺傳算法獲得的Sobel算子更逼近最優(yōu)值。一些應(yīng)用標(biāo)準(zhǔn)遺傳算法未檢測(cè)出的邊緣在改進(jìn)算法中有了比較好的呈現(xiàn)效果。

為了進(jìn)一步對(duì)比兩個(gè)算法進(jìn)化過程中適應(yīng)度的變化情況，我們繪制了圖5來(lái)描述兩個(gè)算法的最佳個(gè)體變化趨勢(shì)。在圖5中，縱軸代表灰度圖像的灰度值范圍，橫軸代表運(yùn)行的次數(shù)，以此來(lái)對(duì)比標(biāo)準(zhǔn)遺傳算法和改進(jìn)遺傳算法運(yùn)行結(jié)束后，所獲得圖片的灰度閾值趨近最優(yōu)解的變化趨勢(shì)。從圖5可以看出，在標(biāo)準(zhǔn)遺傳算法邊緣檢測(cè)中加入精英反向?qū)W習(xí)和自適應(yīng)變異機(jī)制后，遺傳算法所獲得最優(yōu)解的次數(shù)有了明顯的提高，同時(shí)，求得的圖像閾值的波動(dòng)幅度有所降低?？梢姼倪M(jìn)遺傳算法在處理圖像邊緣檢測(cè)中比標(biāo)準(zhǔn)遺傳算法有了一定程度的提高。

表1展示了不同交叉率和不同變異方式下，標(biāo)準(zhǔn)遺傳算法與改進(jìn)遺傳算法所獲得最優(yōu)解個(gè)數(shù)。從表中數(shù)據(jù)可以看出，在相同情況下，改進(jìn)后的遺傳算法所獲得最優(yōu)解個(gè)數(shù)高于標(biāo)準(zhǔn)遺傳算法。

通過實(shí)驗(yàn)中多方面的對(duì)比，可以看到，改進(jìn)后的遺傳算法在求解圖像邊緣檢測(cè)問題時(shí)，有了更強(qiáng)的尋優(yōu)能力，處理圖像的效果得到了一定程度的提高。

5 結(jié)束語(yǔ)

本文針對(duì)Sobel算子尋優(yōu)的困難性提出了應(yīng)用遺傳算法進(jìn)行圖像邊緣檢測(cè)的方案。為了更好地提高遺傳算法的全局收斂性和求解精度，在遺傳算法中加入了自適應(yīng)機(jī)制和精英反向?qū)W習(xí)機(jī)制，從而提高了尋找最優(yōu)解的效率，也在一定程度上遏制了算法的早熟現(xiàn)象和標(biāo)準(zhǔn)遺傳算法解精度較低的弱點(diǎn)。通過仿真實(shí)驗(yàn)中圖像邊緣檢測(cè)效果及數(shù)據(jù)對(duì)比，我們驗(yàn)證出改進(jìn)的遺傳算法所檢測(cè)出的圖像邊緣更加清晰，且算法的穩(wěn)定性和求解精度也較傳統(tǒng)遺傳算法有了一定的提高。進(jìn)一步的研究將從理論上分析該算法的收斂必然性和求解精度，并推廣該算法用于解決其他相關(guān)問題，同時(shí)針對(duì)IOBLGA算法的優(yōu)缺點(diǎn)進(jìn)行多種群體智能算法的混合性研究，做到優(yōu)勢(shì)互補(bǔ)。

參考文獻(xiàn)（References）：

[1] 王培崇.群體智能算法及其應(yīng)用[M].電子工業(yè)出版社，2015.

[2] 汪慎文，丁立新.應(yīng)用精英反向?qū)W習(xí)策略的混合差分演化算法[J].武漢大學(xué)學(xué)報(bào)（理學(xué)版），2013.59（2）：111-116

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

[4] 周新宇，吳志健，王暉.一種精英反向?qū)W習(xí)的差分演算算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2013.31（10）：2129-2134

[5] 賀毅朝，王熙照，寇應(yīng)展.一種具有混合編碼的二進(jìn)制差分演化算法[J].計(jì)算機(jī)研究與發(fā)展，2007.44（9）：1476-1484

[6] 馬永杰，馬義德，蔣兆遠(yuǎn).一種快速遺傳算法及其收斂性[J].系統(tǒng)工程與電子技術(shù)，2009.31（3）：714-718

[7] 鞏敦衛(wèi)，郝國(guó)生，嚴(yán)玉若.交互式遺傳算法基于用戶認(rèn)知不確定性的定向變異[J].控制與決策，2010.25（1）：74-78