基于改進遺傳算法的圖像邊緣檢測

孫海明，韓國強，鄭小秋

（1.湖北汽車工業學院機械工程學院，湖北十堰 442002；2.湖北中程科技產業技術研究院有限公司，湖北 十堰 442002）

圖像中灰度值跳躍的像素集合形成圖像的邊緣[1]。基于梯度邊緣檢測算子運用濾波模板與圖像進行卷積常見的算子有Roberts、Sobel、Prewitt，拉普拉斯算子和坎尼算子[2-5]。上述算子在定位精度及適應性上存在局限性。因此近年來許多功能強大的智能優化算法被應用到邊緣檢測中[6]。遺傳算法因其優秀的尋優能力被廣泛討論[7-9]。改進的天牛須算法具有良好的搜索能力，與其他算法結合克服了傳統算法陷入局部最優的困境[10]，文獻[7-9]中的算法與傳統算法相比在運行效率和準確性上的確有所提高，但算法具有一定的適應性和針對性。該文提出了一種改進的遺傳算法，將梯度變化率的最大方向作為改進遺傳算法的目標函數，將改進后的天牛須算法融入傳統的遺傳算法，在處理圖像時考慮整幅圖像的最優，不再局限于領域特性的最優，運用改進后的算法處理不同圖像時均能得到良好的邊緣結果。

1 圖像梯度

圖像中像素點灰度突變的位置是邊緣所在位置，檢測圖像邊緣的一種常用方法是對圖像中的灰度進行一階微分，將微分后得到的數定義為梯度[11]。設圖像中灰度函數為f(x,y)，點(x,y)處對應的梯度矢量為：

梯度的兩個重要性質是：

1）梯度的方向，與函數f(x,y)的最大變化率方向一致；

2）梯度的幅值，由式（2）表示：

梯度在θ方向的變化率為：

變化率最大方向的變化幅度為:

由梯度幅值計算公式可知，邊緣的方向不影響梯度的幅值。梯度相當于函數的斜率，直觀表述了函數變化的大小和方向，連續函數中可通過微分求解某點的斜率，而圖像是像素值組成的離散矩陣，不連續的距離求解可用差分代替微分進行計算，避免了復雜的平方、開方運算，梯度幅值可表示為：

對灰度圖進行邊緣檢測首先要確定其分割閾值，在應用遺傳算法進行圖像邊緣檢測時，挑選出最優閾值染色體，也需要建立相應的評價指標。按照該思路并通過分析圖像梯度的性質，在進行適應度函數設計時，依據灰度圖像的特性，在圖像灰度突變的位置把一幅圖像分解出邊緣輪廓。將式（4）作為目標函數，梯度幅值大于某一閾值則認為該點(x,y)為邊緣點，在圖像梯度變化率最大的方向進行分割閾值。

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

2.1 基于標準遺傳算法的邊緣檢測

1）基因編碼。由于圖像中每個像素的灰度值在0～255 之間，因此選擇二進制編碼方法，將每條染色體編碼為8 位二進制碼。

2）初始化種群和適應度。樣本的數量由像素的數量決定。樣本總數被分成n個總體。每個種群包含m個樣本，這些樣本被再生到數組R[1,2,…,n] 和數組B[1,2,…,n] 。在數組R中放入n個種群的優化結果，并將平均適應度儲存在數組B中。

3）確定染色體。染色體結構是遺傳算法的核心部分。對于染色體有以下操作：

①個體選擇。該文以像素為探討目標，采用精英選擇策略對個體進行更新。將當前種群中適應度最好的個體隨機替換為下一代種群中適應度最差的相同數目的個體。對于圖像的邊緣檢測，則是將遺傳算法的平均適應度，即對數組B[1,…,n]所代表的樣本種群之間進行特定的選拔使用。

②染色體交叉。交叉操作主要涉及群體中單個染色體上的基因片段的交叉交換，從而產生新的個體。由于像素具有二維信息，該文采用兩點交點法進行交點運算。如果R[1,2,…,n]和R[j,…,n] 隨機選取在一起，在x處(i≥1,j≤n,1 ≤x≤n-1)，R[i,x+1,…,n]和R[j,x+1,…,n] 互相交換相應的部件，染色體交叉過程如圖1 所示。

圖1 染色體交叉過程

③遺傳變異。該基因通過均勻突變隨機改變。在第一輪結束前，用少量隨機產生的具有低概率事件的新個體替換隨機選擇的個體。然后更新數組R[i,…,n] 及數組B[i,…,m]，并開始運行下一代，直到獲得滿意的結果[12]。

2.2 基于改進遺傳算法的圖像邊緣檢測算法

遺傳算法在處理圖像去噪問題時，只根據個體的適應度值選擇個體，可以取得較好的效果。然而，對于復雜背景下的多模態目標邊界提取問題，由于缺乏考慮種群的多樣性，遺傳算法容易過早收斂，陷入局部最優解，導致目標邊緣提取不完全或不準確。天牛須搜索優化算法是一種基于仿生原理的智能算法[13]，受到天牛覓食行為的啟發，根據天牛左右觸手接收到的不同食物氣味的強弱不同來確定搜索方向，確定方向后，跳轉到下一個位置，繼續搜索，直到找到全局氣味最大值點，即目標函數的最優解。BAS 搜索算法在尋優過程中只需要一個個體就可以實現全方位的搜索，不受函數形式和梯度信息的制約，在多目標優化中，各維度之間不相互干擾，降低了優化的復雜度。相比于其他優化算法不易陷入局部最優解、適用性強、過程簡單、運算量小，能夠更快尋找到目標函數的全局最優解。

考慮到固定步長的BAS算法每次搜索距離不變，而圖像中的梯度幅值一直在變化，搜索時可能遺漏掉重要的像素點，導致后期搜索誤差不斷放大，尤其弱邊緣和復雜邊緣會被忽略，影響邊緣檢測的精度。

為了解決上述問題，該文結合了一種改進的BAS 算法[14-16]。該算法通過改變步長參數來改變搜索步長，首先用較大的步長來確定搜索方向的近似范圍,再縮小參數進行精細搜索，最終找出最優解。這種變步長的辦法不僅提高了邊緣信息的精度還提高了運算的速度。

算法中涉及到的主要公式參數包含：隨機初始解x=rands(S,1)，x為(S,1)內的隨機初始值，問題維度S，天牛一次移動步長l，變步長參數E，參數衰變因子t隨迭代次數的增長而呈線性遞減t∈(0,1)，天牛兩須間距離d0，迭代次數n。

天牛須朝向的隨機變量為：

天牛左須坐標表達式為：

天牛右須坐標表達式為:

計算天牛須接收的氣味強度（即函數適應度值）為：

采用改進的變步長法計算天牛下一步要走的位置為：

終止條件為判別梯度變化率方向和天牛位置坐標與初始位置時相比差值是否滿足在設定范圍內，如果是，則終止計算；如果沒有，則繼續循環。圖像像素的坐標值為迭代結束后的適應度函數值，滿足目標函數式（4）的解為圖像的邊緣點。首先，對圖像進行遺傳運算。在達到預先設定的收斂條件后，將遺傳算法的局部最優解轉化為天牛須搜索的初始位置，然后進行天牛須搜索操作，最后顯示圖像的邊緣信息。

算法的基本步驟如下（i表示當前迭代次數，T表示最大迭代次數，設置為100）：

1）對圖像進行簡單處理，為算法中各參數設定初始值；

2）對像素點灰度值進行染色體編碼，由設定的種群大小隨機產生初始種群；

3）由式（3）推算種群中各個體的梯度變化率，計算個體的適應度值；

4）執行選擇、交叉和變異操作來產生下一代種群；

5）使用天牛須尋求指引新一代種群中參與交叉操作的父代交叉點位置發生移動，更新子代，提升種群多樣性；

6）若i＜T，則i′=i+1，轉步驟3），否則中止迭代；

7）算法結束，輸出種群中的最優解，即檢測到的圖像邊緣。

算法流程圖如圖2 所示。

3 實驗結果與分析

為了驗證算法的普適性，分別對像素點、lena像、汽車外形（圖3）進行了實驗仿真，直觀地體現出改進算法性能上的提升，將兩組不同的圖像分別進行基于遺傳算法的邊緣檢測和改進算法的邊緣檢測處理，從圖像的邊緣完整度來看，可以清晰地看出改進后的算法對多種形態下的圖像邊緣檢測結果都有很好的提升效果，邊緣更加完整。圖3 是檢測后的結果圖，分別從像素和整體邊緣進行對比。從圖3幾組對比圖能清晰地看出，改進后的算法對多種形態下的圖像邊緣檢測結果都有很好的提升效果，達到了對算法改進的目的。

圖3 圖像邊緣檢測結果

為了進一步比較兩種算法在進化過程中適應性的變化，圖4 中描述了兩種算法在運行完成后的性能釋放。從圖4 可以看出，利用天牛須搜索算法引導遺傳算法中交叉點位置的移動方向，改進的算法獲得最優解的次數明顯提高，且圖像閾值的波動范圍減小。由此可見，改進的遺傳算法在圖像邊緣檢測方面優于標準遺傳算法。

圖4 最優解趨勢圖

表1 顯示了改進后的邊緣檢測算法在其迭代100 次后相對于改進之前在不同交叉率下的最優解和收斂時間。數據顯示，改進遺傳算法得到的最優解數量要高于標準遺傳算法，收斂時間也有所提高。

表1 改進前后迭代100次獲得最優解個數對比

通過多次實驗對不同的圖片進行邊緣檢測且分析實驗數據，可以看出改進后的遺傳算法在進行圖像邊緣檢測時尋優能力得到增強，且處理不同的圖像時均有良好的效果。

4 結論

針對傳統梯度算子對圖像邊緣檢測滿意度不高的問題，提出將遺傳算法應用于圖像邊緣檢測，將梯度變化率作為目標函數進行求解，且針對遺傳算法應用在復雜圖像背景時容易出現局部最優解，提出了應用改進的天牛須搜索算法優化遺傳算法。實驗表明，在不同的圖像場景下均能獲得更加連續、清晰的邊緣。與已有的圖像邊緣檢測算法相比，改進后的算法不僅減少了收斂時間，且改進算法應用在同一圖片邊緣檢測時，獲得最優解個數的次數顯著提高，使邊緣準確性得到了提高，驗證了該算法具有較高的可行性和魯棒性。