求解圖像邊緣檢測的遺傳算法

陳桂霞

摘 要： 圖像邊緣檢測技術是圖像分析處理中的關鍵。以Sobel邊緣檢測方法為基礎，針對Sobel算子尋優的困難性提出了應用遺傳算法進行圖像邊緣檢測的方案。為了更好地提高遺傳算法的全局收斂性能和求解精度，在遺傳算法中加入了自適應機制和精英反向學習機制，從而提高了尋找最優解的效率，在一定程度上遏制了算法的早熟現象和標準遺傳算法解精度較低的弱點。

關鍵詞： 圖像邊緣檢測； 遺傳算法； Sobel算子； 反向學習

中圖分類號：TP312 文獻標志碼：A 文章編號：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 引言

基于內容的圖像識別和理解，是新一代網絡搜索引擎的重要研究方向，而圖像邊緣檢測技術是其中的關鍵，它在圖像的分析處理中有著非常重要的意義。如何尋找與圖像真實邊緣線相對應的實際邊緣，長期以來一直是數字圖像處理領域的研究熱點，因為邊緣的特征反映了圖像灰度的不連續性，它提供了一幅圖像的大量有效和有價值的信息。本文以Sobel[3]邊緣檢測方法為基礎，介紹一種改進的遺傳算法圖像邊緣檢測方法，并通過在遺傳算法中加入自適應變異算子和反向學習機制來提高遺傳算法的收斂能力。

1 數字圖像邊緣

對于一幅圖像，不同區域的灰度值是不相同的，而這些不同的區域之間往往是邊緣的體現，灰度值的不連續是形成圖像的主要原因。這種灰度值的不連續性可通過數學方法中的求導方法檢測出來。比較常見的經典邊緣檢測方法一般都是通過一階導數和二階導數的求解來檢測圖像邊緣的灰度值。圖像灰度邊緣是非常復雜的，基于采取樣本的原因，獲得的實際圖像中的邊緣是有坡度的，一般可以用位置、朝向、幅度、均值、斜率這五個參數來描述。所謂邊緣檢測也常指通過計算獲得邊緣五個參數數據。基于檢測原理，可以采用多種不同的方法來檢測邊緣，主要包括基于梯度的邊緣檢測算子和二階導數算子。

2 Sobel邊緣檢測算子

在3×3鄰域內做加權平均和差分運算，以此為基礎，Sobel在另一個著名的圖像邊緣檢測算子Prewitt基礎上，提出了一個新穎的圖像邊緣算子—Sobel算子，其計算過程如公式1。

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

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

3 面向圖像邊緣檢測的遺傳算法

3.1 遺傳算法的編碼設計

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

3.2 適應度函數設計

依據灰度圖像的特性，把一幅圖像分解成背景和目標兩個部分。目標和背景之間的方差值越大，表示組成圖像的兩部分差別越大，如果一部分背景被錯分為目標或者是目標被錯分為背景，則會導致兩部分的差別變小。所以，類間方差最大的分割則表明錯分的概率最小。

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

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

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

3.3 求解圖像邊緣檢測的標準遺傳算法

將種群中的染色體應用8位二進制數進行編碼，一條染色體代表一個解，基于上一節描述最大類間方差法作為遺傳算法的適應度函數，則求解圖像邊緣檢測的標準遺傳算法步驟如下：

算法1 標準遺傳算法（GA[1]）

Step1. 利用Sobel算子逐點計算原始圖像從而獲取梯度圖像。

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

Step2.1. 染色體初始化。在解空間內，隨機生成40條染色體作為初始種群。

Step2.2. 交叉算子。隨機選擇兩條染色體，以單點交叉方式交叉，交叉概率設為0.6。

Step2.3. 變異算子。對各個染色體采用均勻變異算子，執行變異。

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

Step3. 依據閾值大小，假如圖像的梯度值大于或等于閾值，便可以確定該點為最初始的邊緣點，該點方向就是邊界點的方向，否則就是一個無邊點。

3.4 遺傳算法的相關改進

由于標準遺傳算法容易收斂于局部最優，解精度低，所以要在標準遺傳算法中引入反向學習機制。考慮到在算法的進化迭代過程中，適應度優秀的個體代表了種群的收斂和前進方向，能夠更好地勘探新解，同時由于加強精英個體周圍的鄰域搜索，對于提高算法解的精度亦有幫助，所以針對種群的精英個體執行反向學習策略。

為了提高運算速度，設定一個概率p，產生以隨機數r=random（），當r小于p時執行精英反向搜索機制，否則執行主體遺傳算法。

3.5 自適應變異機制

為了更好地保護已求得的優秀解不被丟失，需要引入一種自適應變異算子。同時，為了使算法能夠較好地搜索優秀個體周圍較小的鄰域，而對于適應度較差的個體，則搜索其較大的鄰域，特引入自適應變異率，其計算方法見公式7。該機制的變異概率能夠根據解的質量自適應地調整搜索區域，從而比較明顯地改善算法的搜索能力。

算法2 自適應算子

Step1. 保存種群內每一個個體的適應度值。

Step2. 計算種群的適應度總和，同時將最大的適應度值保存。

Step3. 求解平均適應度值并保存到average中。

Step4. 群體內的個體執行公式7的變異機制。

算法3 改進的反向學習遺傳算法（IOBLGA[1]）

Begin

初始化群體p（t）；

while（停機不滿足） do

if rand（0，1）

執行精英反向學習機制；

else

執行自適應遺傳算法；

endif

endwhile

end

4 仿真實驗

為了驗證算法的有效性，應用JAVA實現該算法，并將標準遺傳算法（GA）與改進遺傳算法（IOBLGA）進行圖像邊緣檢測比較。兩個算法設定的種群規模、交叉概率、迭代次數均相同。設種群規模為40，交叉概率px=0.5，種群迭代次數30，兩個算法均單獨運行30次，取各自的最佳效果圖。

將標準遺傳算法和改進遺傳算法分別作用于同一幅圖，分別獲得邊緣檢測效果圖。對比兩個圖的求解效果，發現改進遺傳算法在求解過程中所獲得的Sobel算子，較標準遺傳算法獲得的Sobel算子更逼近最優值。一些應用標準遺傳算法未檢測出的邊緣在改進算法中有了比較好的呈現效果。

為了進一步對比兩個算法進化過程中適應度的變化情況，我們繪制了圖5來描述兩個算法的最佳個體變化趨勢。在圖5中，縱軸代表灰度圖像的灰度值范圍，橫軸代表運行的次數，以此來對比標準遺傳算法和改進遺傳算法運行結束后，所獲得圖片的灰度閾值趨近最優解的變化趨勢。從圖5可以看出，在標準遺傳算法邊緣檢測中加入精英反向學習和自適應變異機制后，遺傳算法所獲得最優解的次數有了明顯的提高，同時，求得的圖像閾值的波動幅度有所降低。可見改進遺傳算法在處理圖像邊緣檢測中比標準遺傳算法有了一定程度的提高。

表1展示了不同交叉率和不同變異方式下，標準遺傳算法與改進遺傳算法所獲得最優解個數。從表中數據可以看出，在相同情況下，改進后的遺傳算法所獲得最優解個數高于標準遺傳算法。

通過實驗中多方面的對比，可以看到，改進后的遺傳算法在求解圖像邊緣檢測問題時，有了更強的尋優能力，處理圖像的效果得到了一定程度的提高。

5 結束語

本文針對Sobel算子尋優的困難性提出了應用遺傳算法進行圖像邊緣檢測的方案。為了更好地提高遺傳算法的全局收斂性和求解精度，在遺傳算法中加入了自適應機制和精英反向學習機制，從而提高了尋找最優解的效率，也在一定程度上遏制了算法的早熟現象和標準遺傳算法解精度較低的弱點。通過仿真實驗中圖像邊緣檢測效果及數據對比，我們驗證出改進的遺傳算法所檢測出的圖像邊緣更加清晰，且算法的穩定性和求解精度也較傳統遺傳算法有了一定的提高。進一步的研究將從理論上分析該算法的收斂必然性和求解精度，并推廣該算法用于解決其他相關問題，同時針對IOBLGA算法的優缺點進行多種群體智能算法的混合性研究，做到優勢互補。

參考文獻（References）：

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

[2] 汪慎文，丁立新.應用精英反向學習策略的混合差分演化算法[J].武漢大學學報（理學版），2013.59（2）：111-116

[3] 李敏強，寇紀淞，林丹.遺傳算法的基本理論與應用[M].科學出版社，2002.

[4] 周新宇，吳志健，王暉.一種精英反向學習的差分演算算法[J].小型微型計算機系統，2013.31（10）：2129-2134

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

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

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