宋建軍， 侯志強， 余旺盛

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

0 引言

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

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

1 蟻群算法

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

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

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

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

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

2 改進的蟻群算法

2.1 能見度矩陣的求取

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

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

數(shù)量gxx、gyy、gxy定義為這些向量的點乘

據(jù)此可得彩色圖像I的梯度為

式中

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

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

2.2 螞蟻初始位量的設(shè)置

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

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

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

2.3 啟發(fā)式引導函數(shù)設(shè)置

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

2.4 信息激素更新規(guī)則

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

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

2.5 螞蟻停止行走規(guī)則

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

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

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

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

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

3 算法步驟

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

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

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

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

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

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

4 實驗結(jié)果及分析

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

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

圖2 仿真結(jié)果對比Fig.2 Comparison of simulation results

圖3 仿真結(jié)果對比Fig.3 Comparison of simulation results

5 結(jié)束語

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

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

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

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

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

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

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

［7］ 張健，周激流，何坤，等.基于多態(tài)蟻群優(yōu)化的圖像邊緣檢測［J］.計算機工程與應(yīng)用，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－h(huán)euristic［C］//New Ideas in Optimization，London，1999:1－27.

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