基于改進的蟻群算法的邊緣連接方法

宋建軍， 侯志強， 余旺盛

(空軍工程大學電訊工程學院，西安 710077)

0 引言

邊緣檢測在圖像處理和計算機視覺中有著重要的作用，通過檢測圖像邊緣可以完成對圖像的分割，其正確性和自適應性在一定程度上影響著目標檢測和識別的智能化程度。由于噪聲的干擾、圖像中的背景以及圖像內容的復雜性影響，僅僅使用某種傳統的邊緣檢測算子如 Roberts，Sobel，Prewitt，Kirsch，Laplacian 和Canny［1］等來進行邊緣的提取，而不進行邊緣連接的話，最后檢測出來的邊緣可能存在不連續現象，因此需要對獲得的邊緣圖像做進一步的處理，即邊緣連接。經過多年的研究，已經得到了多種邊緣連接方法。例如，膨脹細化法［2］通過多次膨脹細化實現邊緣的連接，會使圖像邊緣過度失真;最小點對法［2］直接使用直線連接兩個相鄰邊緣端點，此方法得到的補償邊緣不能正確地反映原始圖像邊緣信息;填充小間隙法［3］相對于邊緣簡單的圖像連接的效率和準確度比較高，但是對于邊緣復雜的圖像，可能造成圖像過度分割，效果較差;Hough變換法［3］，并不是所有的邊緣都能滿足特定的形狀，適用于此方法。基于模糊判決的圖像邊緣連接方法［4］，主要是基于局部范圍內梯度值來決定像素屬于邊緣的隸屬度，選擇隸屬度大的為邊緣點。文獻［5］提出結合分水嶺算法實現邊緣連接，在Canny算子檢測到目標粗略輪廓的基礎上，從基于標記的分水嶺算法的過分割結果中根據最小距離準則搜索缺失的邊緣段進行邊緣連接。

蟻群算法是一種組合優化問題的啟發式搜索算法，具有并行性、離散性、魯棒性、正反饋的特點。近幾年有不少學者將蟻群算法用于改進邊緣檢測算法。在基于蟻群優化的邊緣檢測算法中，大多選擇圖像像素的灰度梯度作為螞蟻的啟發信息。文獻［6］提出一種基于梯度定義和蟻群算法的邊緣提取算法;文獻［7］提出了基于多態蟻群優化的圖像邊緣檢測，而邊緣連接可以看成一個尋找最優邊緣像素點的過程;文獻［8］提出使用蟻群算法來補償傳統邊緣檢測方法沒有檢測出來的邊緣，通過引入原始圖像信息，得到的補償邊緣能夠正確反映原始圖像信息，但是螞蟻尋找路徑的過程盲目性較大，容易陷入局部解，無法充分地連接斷裂邊緣;文獻［9］在改進Canny算子檢測的結果上，引入了方向信息，對螞蟻尋找路徑起一定指引作用，但是得到的補償邊緣正確性較低。本文提出一種基于改進的蟻群算法的邊緣連接方法，從原始的彩色圖像得到能見度矩陣，通過能見度矩陣設置每個像素點的初始信息激素，并控制信息激素的更新;綜合考慮梯度幅值和梯度方向來確定啟發式引導函數，使螞蟻沿著真正的邊緣行走;并且考慮了螞蟻的走向問題，從而既保證了連接邊緣的正確性，也在一定程度上降低了螞蟻陷入局部解的可能性，從而能充分地連接斷裂邊緣。

1 蟻群算法

蟻群算法又稱螞蟻算法，是由意大利科學家M.Dorigo［10］等人受自然界螞蟻尋找食物的過程啟發而提出的一種新型搜索優化算法。

根據蟻群算法基本原理，假設第m只螞蟻的當前位置為(x0，y0)，(i，j)為像素點(x0，y0)的其中一個領域像素，根據式(1)的路徑轉移規則選擇路徑

式中，N表示其中可選路徑的集合，也就是像素點(x0，y0)的8鄰域像素集合，但不包括螞蟻記憶走過的路徑。

隨著每個螞蟻的移動，各個像素上的信息激素強度將發生變化，經過一次迭代后，要對每個像素點的信息激素強度進行更新。像素點(i，j)處的信息激素強度根據式(4)進行調整

式中:ρ為信息激素的揮發率;Δτ(i，j)為本次循環中經過像素點(i，j)處的螞蟻留下的信息激素的總和。

2 改進的蟻群算法

2.1 能見度矩陣的求取

由于對單獨彩色平面的處理并不總是等于直接在顏色向量空間中的處理，分別計算圖像梯度然后形成彩色圖像可能得到與人眼視覺特性不一致的結果。因此，在彩色向量空間直接計算梯度比以單獨的分量圖像為基礎計算梯度具有更高的準確度。本文采用彩色向量空間梯度算法［2］，直接在RGB向量空間計算梯度。

設 r、g、b是 RGB 彩色空間沿 R、G、B 軸的單位向量，像素(x，y)沿水平方向和垂直方向的彩色梯度可用向量來表述

數量gxx、gyy、gxy定義為這些向量的點乘

據此可得彩色圖像I的梯度為

式中

像素(x，y)在原始的彩色圖像的能見度矩陣中的對應值為

式中:▽Imax(θ)表示彩色圖像 I中的最大梯度值;▽I(x，y)(θ)表示像素(x，y)的梯度值。一般來說，如果像素(x，y)在邊緣上，ξ(x，y)的值很大，如果像素(x，y)不在邊緣上，ξ(x，y)的值較小。用能見度矩陣初始化每個像素的信息激素。

2.2 螞蟻初始位量的設置

如果在邊緣圖像的每個邊緣點上放若干只螞蟻，搜索量相當大，文獻［11］提出通過提取邊緣端點，將它們作為螞蟻的初始位置，從而大大地降低了搜索量。首先對邊緣圖像進行相關處理，使邊緣為單像素，且邊緣像素值為255，背景為0。然后根據式(10)計算像素的連接數，連接數為1的像素即為邊緣端點。

如果E=1，則此像素點即為邊緣的端點。式中:f(xk)表示像素點x的像素值;k代表8鄰域的第k鄰域，見圖1。根據式(10)對每一個邊緣像素點進行端點判斷，得到端點的集合，這些端點即為螞蟻的初始位置。

圖1 像素x的8鄰域Fig.1 Eight neighborhoods of pixel x

2.3 啟發式引導函數設置

設(x0，y0)為螞蟻的初始位置，(i，j)是以(x0，y0)為中心3×3結構的鄰域像素，可根據梯度幅值和梯度方向的相近程度來判斷像素(x0，y0)與(i，j)的相似性。像素間的相似性公式為

2.4 信息激素更新規則

蟻群算法的負反饋作用就是通過信息激素的更新實現的，為了防止早熟收斂行為，引入了信息激素的最大值和最小值的限制，即 τmin≤τi，j≤τmax。具體更新規則如式(13)所示。

式中:Np表示螞蟻m所得到的路徑的長度，即路徑所包含像素點的個數;和σξ分別表示螞蟻m所得到的路徑上的像素所對應的能見度矩陣中元素值的均值和方差。越大，表明螞蟻m所得到的這條路徑與其領域的像素的對比度越大，邊緣的可能性越大，則留下的信息激素越多;σξ越小，表明螞蟻m所得到的這條路徑上的像素更可能屬于同一條邊緣，避免螞蟻經過邊緣之間時在非邊緣處留下信息激素。

2.5 螞蟻停止行走規則

在探索的過程中，一幅圖像包含許多邊緣端點。因此一些螞蟻可能會尋找到一些重復的圖像區域，產生許多無效的探索路徑。為了減少探索路徑的次數，提高運算速度，本文提出了以下4種措施。

1)設置最長記憶路徑長度。人工螞蟻具有記憶功能，能夠記憶所走過的路徑。如果螞蟻在此次路徑尋找過程中，走過的路徑長度大于設定值L，則螞蟻停止行走，即尋找失敗。

2)將一個端點設為初始位置，當螞蟻行走到端點自身的邊緣像素時，螞蟻停止行走，即尋找失敗。

3)當螞蟻走到其他端點處的螞蟻所走過的路徑時，則螞蟻停止行走，即尋找成功。

4)當螞蟻走到除端點自身邊緣以外的其他邊緣點時，則螞蟻停止行走，即尋找成功。

3 算法步驟

1) 初始化 C，L，τmin，τmax，ρ，q0，α，β 等參數。

2)對原始的彩色圖像進行Canny邊緣檢測，使邊緣像素值為255，背景為0，并根據式(10)對邊緣圖像進行端點提取，同時，根據能見度矩陣設置每個像素點的初始信息激素的強度。

3)選擇一個端點，并且標記此端點所屬的邊緣，同時在該端點處放置m只螞蟻，接著轉步驟4);如果所有端點都已處理，則算法結束。

4)選擇一只螞蟻根據式(1)規則進行轉移，并保留路徑。如果滿足2.5小節給出的停止行走規則，此螞蟻停止行走。判斷所有螞蟻是否都已完成探索過程，如果是則進行步驟5)，否則繼續進行步驟4)。

5)在所有連接成功的路徑中，選擇fm最大的路徑作為選擇的端點在本次迭代過程中獲得的最佳路徑，并與原最優路徑進行比較，如果更優，則替代最優路徑。同時根據式(13)來更新信息激素的強度。更新完成后，清除所有已找到路徑，進入步驟6)。

6)判斷迭代是否停止，如果不停止，則返回步驟4);如果停止，則將得到的最優路徑與原邊緣圖像進行疊加，并剔除已進行連接的邊緣，同時返回步驟3)。

4 實驗結果及分析

本文所有的處理過程均是在Matlab7.0下編程實現的。實驗過程中一些參數的選擇為:C=1，L=30，τmin=0.001，τmax=10，ρ=0.1，q0=0.9，α =1，β =2，迭代次數為100次。測試圖像及其處理結果如圖2和圖3所示。圖2a和圖3a是原始的Lena圖像和House圖像;圖2b和圖3b是經過Canny算子邊緣檢測的邊緣圖像;圖2c和圖3c是根據文獻［8］中方法得到的結果;圖2d和圖3d是根據文獻［9］中方法得到的結果;圖2e和圖3e是使用本文改進方法得到的結果。

通過仿真試驗比較，發現采用文獻［8］中方法得到補償的效果比較差，有的邊緣沒有連接起來，例如圖2c中Lena圖的頭頂的邊緣還沒有完全連接起來，圖3c中樹枝也存在斷裂部分。由于文獻［8］中螞蟻尋找路徑的過程盲目性較大，容易陷入局部解，無法充分地連接斷裂邊緣;而根據文獻［9］中方法得到補償效果相對文獻［8］較好，但是效果仍然不理想，例如圖2d中Lena圖的頭頂出現虛假邊緣。由于文獻［9］中引入了方向信息，對螞蟻尋找路徑起一定指引作用，但是得到的補償邊緣正確性較低。本文改進方法能夠補償所有的斷裂邊緣，并且補償結果與原圖像邊緣信息完全吻合，比其他兩種方法更好。

圖2 仿真結果對比Fig.2 Comparison of simulation results

圖3 仿真結果對比Fig.3 Comparison of simulation results

5 結束語

蟻群算法是一種較新的應用于組合優化問題的啟發式搜索算法。本文將蟻群算法應用于圖像邊緣檢測領域中，進行了有效的探索，提出了一種基于改進蟻群算法的邊緣連接方法。該方法利用能見度矩陣來設置像素點的初始信息激素和調節信息激素的更新，從而減小了在算法運行初期定位錯誤的概率，提高了迭代過程中信息更新的準確性，提高了算法的時間性能。實驗結果表明，得到的補償邊緣能夠很好地反映原始圖像信息，連接效果較好，能滿足一些應用場合對邊緣檢測的輪廓封閉性需要。但基于蟻群算法的邊緣連接方法中的參數是人為設定的，而沒有理論上指導，根據圖像的自身特征自適應地調整參數可能會取得更好的邊緣連接效果，有待于實驗驗證。同時蟻群算法花費的時間很大，也需要進一步研究。

［1］ CANNY J.A computational approach to edge detection［J］.IEEE Transactions on Pattern Analysis And Machine Intelligence，1986，8(6):678－698.

［2］ 岡薩雷斯.數字圖像處理［M］.北京:電子工業出版社，2005:420－482.

［3］ 董梁.基于哈夫變換的圖像邊緣連接［J］.現代電子技術，2008，31(18):149－150.

［4］ 楊紹清，賈傳瑩.基于模糊判決的圖像邊緣連接［J］.光學技術，2002，28(2):108－112.

［5］ 劉榮，侯志強，譚洪波.結合分水嶺變換的彩色圖像邊緣檢測算法［J］.微計算機信息，2010，26(9):189－191.

［6］ 陳亮，郭雷.一種基于蟻群算法的邊緣提取算法［J］.光子學報，2010，39(4):759－763.

［7］ 張健，周激流，何坤，等.基于多態蟻群優化的圖像邊緣檢測［J］.計算機工程與應用，2011，47(3):20－23.

［8］ LU D S，CHEN C C.Edge detection improvement by ant colony optimization ［J］.Pattern Recognition Letters，2008，29(4):416－425.

［9］ WONG Y P，SOH V C M，BAN K W，et al.Improved canny edges using ant colony optimization［C］//The Fifth International Conference on Computer Graphics，Imaging and Visualisation，Penang，2008:197－202.

［10］ DORIGO M，CARO G D.The ant colony optimization meta－heuristic［C］//New Ideas in Optimization，London，1999:1－27.

［11］ 路漫漫，滕奇志.蟻群算法實現的圖像邊緣連接［J］.計算機應用，2010，30(4):932－935.