微粒群優化的Canny邊緣檢測方法

陳燕龍

（廣州航海高等專科學校信息與通訊工程學院，廣東 廣州 510725）

1.引言

圖像的邊緣是圖像的最基本特征。邊緣檢測在圖像分割、圖像增強及圖像壓縮等領域中有著廣泛的應用，而且一直是數字圖像處理領域研究的熱點和焦點問題。圖像邊緣蘊含了豐富的內在信息，主要劃分為階躍狀和屋脊狀兩種類型。階躍狀邊緣兩側的灰度值變化明顯，屋脊狀邊緣則位于灰度增加與減少的交界處。傳統的圖像邊緣檢測方法大多是從圖像的高頻分量中提取邊緣信息，微分運算是邊緣檢測與提取的主要手段。由于傳統的邊緣檢測方法對噪聲敏感，所以實際運用效果有一定的局限性。近年來，越來越多的新技術被引入到邊緣檢測方法中，如數學形態學、小波變換、神經網絡和分形理論等。

Canny提出了最佳邊緣檢測算子即Canny算子[1]，得到了廣泛的應用，并成了與其它實驗結果作比較的標準。其原因在于他最先建立了優化邊緣檢測算子的理論基礎，提出了迄今為止定義最為嚴格的邊緣檢測的三個標準。另外就是其相對簡單的算法使得整個過程可以在較短的時間內實現。實驗結果也表明，Canny算子在處理受加性高斯白噪聲污染的圖像方面獲得了良好的效果[2]。

但是在應用Canny算子進行邊緣檢測時，對像素梯度進行模非極大值抑制后，要設定高、低2個閾值進行邊緣篩選，這2個閾值的選取目前還沒有統一的標準，對不同的圖像缺乏自適應性，而且無法消除局部噪聲干擾，在檢測出偽邊緣的同時還會丟失一些灰度值變化緩慢的局部邊緣。本文在對傳統Canny算法進行分析的基礎上，提出了一種基于微粒群優化算法的Canny算法，針對不同圖像自適應地生成動態閾值，取得了良好的檢測精度和準確度。并與基于遺傳算法進行優化的結果進行了比較。

2.Canny算法

2.1 最佳逼近函數

對一幅圖像進行邊緣檢測，一般可分為三步：濾波、增強和檢測。Canny算法也是一個具有類似步驟的多階段的優化算法。Canny給出的評價邊緣檢測性能的3個指標如下：

(1)高信噪比準則。即輸出信號的信噪比大，使得非邊緣點或邊緣判斷為非邊緣點的概率最小。信噪比(SNR)的數學表達式為

其中，f(x)是邊界為[-ω，+ω]的濾波器脈沖響應；G(x)為邊緣函數；σ為高斯噪聲的均方根。信噪比越大，誤檢率越低。

(2)高定位精度準則。即檢出的邊緣點與實際邊緣點距離最小，使定位精度最高。定位精度的數學表達式為

其中，G’(-x)和f’(x)分別為G(-x)和f(x)的一階導數。Localization的值越大，定位精度越高。

(3)單一邊緣響應準則。即和每個邊緣有且只有一個響應，最大限度抑制偽邊緣出現。要保證單一邊緣響應，檢測算子脈沖響應導數的零交叉點平均距離應滿足

設高斯二維函數為

式(4)即為滿足3個準則的最佳逼近函數。Canny以上述指標和準則為基礎，利用泛函求導方法導出高斯函數的一階導數，推導出最優邊緣檢測算子的一個近似實現：邊界點位于圖像被高斯函數平滑后的梯度幅度的極大值點。

2.2 實現過程

(1)平滑圖像。利用式(5)所示的一維高斯函數對原始圖像進行平滑除噪，從而得到平滑圖像I(x，y)。

其中*表示卷積，f(x，y)是原始圖像，σ是高斯函數的散布參數，用它控制平滑程度。

(2)計算梯度方向和幅值。采用2×2鄰域一階偏導的有限差分計算平滑后的圖像I(x，y)的梯度方向和幅值：

其中，gx和gy分別為原圖像I(x，y)被濾波器fx和fy沿行、列作用的結果。

(3)對梯度圖像進行非極大值抑制。若像素點(x，y)的梯度幅值M(x，y)不小于梯度方向上兩個相鄰像素點的梯度幅值，則判斷該點為可能的邊緣點[3]。

(4)雙閾值方法檢測和連接邊緣。取兩次閾值th1（低閾值）和th2（高閾值），對梯度圖像進行雙閾值化處理，可得到一個高閾值檢測結果和低閾值檢測結果，再在前者中連接邊緣輪廓，連接到端點時，到后者尋找弱邊緣點，彌補前者的邊緣間隙。

3.微粒群優化算法

3.1 標準微粒群優化算法（PSO）

PSO算法是由Eberhart和Kennedy于1995年首次提出[3]一種進化計算技術（evolutionary computation）。類似其它進化類算法，PSO算法采用群體和進化的概念，根據個體的適應值大小進行操作。不同的是，PSO算法將每個個體看作是在n維搜索空間中的一個沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行。該速度是由個體飛行經驗和群體的飛行經驗進行動態調整，最終使所有微粒趨近全局最好位置。

在標準PSO算法中，一個包含有M個粒子的群體，每個微粒的維數為n，其中Xi=(xi1，xi2，…，xin)為微粒i的當前位置；Vi=(vi1，vi2，…，vin)為微粒i的當前速度向量；Pi=(pi1，pi2，…，pin)是微粒i的個體最好位置；Pg為所有微粒在當前的全體最好位置。標準PSO算法的進化公式如下：

其中，ω(t)是慣性因子，一般可以設為隨進化而線性減少；t為當前進化代數；φ2是加速因子，通常在0～2間選取；μi～U(0，1)是兩個相互獨立的隨機數。為了減少在進化過程中微粒離開搜索空間的可能性，可以給速度Vi限定一個范圍Vi∈[Vmin，Vmax]。

為了要保證算法的收斂性，每個微粒必須要收斂于各自的Pi點，這是由微粒的追隨性和微粒群的集聚性決定的。從動力學的角度來看，PSO算法中微粒的收斂過程是以Pi點為吸引子，隨著速度的變小而不斷地接近Pi點。因此在整個過程中，在Pi點處實際存在某種形式的吸引勢能場吸引著微粒，這正是微粒能保持聚集性的原因。但是在標準PSO微粒群系統中，微粒的收斂是以軌道的形式實現的，且微粒的速度總是有限的，因此在搜索過程中微粒的搜索空間是一個有限的區域，不能覆蓋整個可行的空間。所以標準PSO算法不能保證以概率1收斂到全局最優解，甚至不能收斂到局部最優解，這正是其最大的缺點，所以許多學者對標準算法的改進進行了很多的探索。

3.2 基于量子行為的微粒群優化算法（QPSO）

量子化的微粒群算法[4，5]是從量子力學的角度對標準PSO算法的繼承和推廣。在QPSO中，微粒群按下面三個公式移動：

其中：φ，u=rand，mbest是微粒群的平均最優位置，pid為Pid和Pgd之間的隨機點；a為QPSO的收縮擴張系數，它是QPSO算法收斂性的重要參數，取值方法為

其中MAXITER是迭代的最大次數，具體a取值視情況而定；T為當前迭代次數。

PSO和QPSO的區別在于進化的方法不同，即更新微粒位置的方法不同。在PSO算法中，微粒必須在一個有限的搜索范圍內以確保微粒群的聚集性，使算法收斂于一個最優點或局部最優點。而在QPSO算法中，微粒能以某一確定的概率出現在整個可行的搜索空間中任意一個位置。而這樣的位置可能比當前群體中的個體極值具有更好的適應值，所以QPSO算法能較好地克服標準PSO算法在收斂性能上的不足。

4.基于微粒群優化算法的Canny邊緣檢測

4.1 平滑后對圖像作灰度拉伸

對圖像進行平滑，除噪的同時也會使灰度的變化范圍變窄，一些邊緣變得比較平緩，從而在后續的邊緣檢測中容易丟失邊緣。為改變這種情況，在平滑后，對圖像做灰度拉伸，增大圖像的灰度分布的動態變換范圍，增強對比度和邊緣灰度的變換速率。

其中，對于灰度級為256的圖像來說，Mg=Mf=255。a、b為常數，不同情況下灰度拉伸的a、b的取值要根據具體的條件進行選擇。

4.2 微粒群優化算法求取閾值

從Canny算子的原理可以看出，影響算法性能的兩個重要因素是σ和閾值Hth、Lth的選取。對于灰度平坦的圖像，用較小的σ可以取得很好的平滑效果，但如果圖象復雜度增加，σ也要有相應的增加。這會導致高斯平滑模板相應的增大，平滑的速度也大幅度變慢。本文實驗中，σ取固定值1。

一幅在光照條件不好的情況下拍攝的圖像，很可能會出現灰度分布的不均勻。這時，如果選擇高閾值的Canny算子進行檢測，圖像的某些部分會丟失邊緣；而選擇低閾值Canny算子進行檢測，又會出現很多虛假的邊緣。可見，雖然雙閾值法使Canny算子提取的邊緣更具有魯棒性，但閾值的選擇對結果影響很大，而對不同的圖像確定不同的閾值又較困難。

本文采用基于量子行為的微粒群優化算法（QPSO）選代求取最優閾值，作為Canny算子的高閾值Hth，對于低閾值的選擇，通過選擇為高閾值的一定比例因子實現，一般取Lth＝k Hth，其中比例因子k取1.5～2.5。

基于實時性的考慮，我們選取的適應度函數是最大類間方差的計算函數。計算公式為：

其中t表示用來處理圖像的閾值，w1(t)表示圖像中灰度值小于閾值的像素的總和，w2(t)表示表示圖像中灰度值大于閾值的像素的總和，u1(t)表示圖像中灰度值小于t的像素的平均灰度值，u2(t)表示圖像中灰度值大于t的像素的平均灰度值，u(t)為目標圖像的灰度均值。通過QPSO算法，找出使得σ (t)2最大的t的值，作為Canny算法的高閾值。算法流程如下：

(1)迭代次數t=0，對種群的每個粒子的位置向量進行初始化；

(2)根據目標函數計算每個粒子的目標函數值；

(3)更新每個粒子的新局部最優位置Pij；

(4)更新全局最優位置Pgj；

(5)根據(3)式計算mbest；

(6)根據(4)式計算每個粒子隨機點pid；

(7)根據式(5)更新每個粒子的新位置；

(8)判斷參數估計是否達到預定迭代步數或預定精度，條件滿足則終止。否則，t＝t+1，返回(2)。

5.仿真結果

為了驗證算法的結果，將本文算法與傳統的Canny算法進行了實驗對比。結果見圖1。

圖1 仿真實驗結果

實驗中還采用檢測圖像的品質系數[6]R來評估算法的性能：

其中，m是真實邊緣數；n是檢測出的邊緣數；d(i)表示第i條邊緣與響應的檢測邊緣的距離，a為比例常數，可取為0.1，當R=1時是檢測的理想狀況。結果見表1。

從圖1可以看出，傳統Canny算法存在一些假邊緣，同時丟失了一些真邊緣。而本文算法不需要事先設定閾值，優化產生的閾值使得檢測準確性得到較大的提高，邊緣完整，定位準確，能夠更好地保留邊界和圖像細節。從表1可以看出，本文算法所得邊緣圖像的品質系數明顯高于傳統Canny方法。

表1 圖1中邊緣圖像的品質系數

與采用標準微粒群算法（PSO）和遺傳算法（GA）進行選代求取最優閾值的結果進行對比發現，PSO沒有遺傳操作，其計算復雜度比GA低，QPSO的優勢在于簡單容易實現并且沒有許多參數需要調整，收斂的速度快。比較結果見表2。

表2 迭代次數比較

6.結論

本文采用改進的微粒群優化算法對傳統的Canny算法進行了改進，改善了對差分背景的圖像邊緣檢測的效果，通過微粒群優化算法產生的閾值適應性好，自動化程度高。因為QPSO算法迭代次數少，算法的開銷不大，顯著提高了閾值選取的速度。雖然算法的運算復雜度和運算時間要稍大于普通的Canny算子，但優于采用遺傳算法進行優化的情況，對實時性無明顯影響。

[1]Canny J，A Computational Approach to Edge Detection[J].IEEE Transon PAM I，1986，8(6)：679-698.

[2]Zhang Bin，He Sai-xian.Improved Edge-detection Method Based on Canny algorithm[J].Infrared Technology，2006 28(3)：165-169.

[3]Kennedy J，Eberhart R.Particle Swarm Optimization[C].Proceedings of IEEE IntConf on Network，1995：1942-1948.

[4]SUN Jun，XUWenbo.A global search strategy of quantum-behaved particle swarm optim ization：proc.Of IEEE Conference on Cybernetics and Intelligent Systems[C].Singapore：[s.n.]，2004：111-116.

[5]SUN Jun，FENG Bin，XU Wenbo.Particle swarm optim ization w ith particles having quantum behavior：proc of Congress on Evolutionary Computation，2004：325-331.

[6]William K.Pratt數字圖像處理[M].鄧魯華，張延恒等譯.北京：機械工業出版社，2005：330-332.