一種改進(jìn)非極大值抑制的Canny邊緣檢測(cè)算法

李 旭, 王正勇, 吳曉紅, 滕奇志

(四川大學(xué)電子信息學(xué)院圖像信息研究所,四川成都610064)

1 引言

邊緣是圖像最基本的特征,邊緣檢測(cè)是圖像處理和計(jì)算機(jī)視覺(jué)中最為經(jīng)典和基礎(chǔ)的問(wèn)題之一,在物體識(shí)別、三維重建、圖像匹配、檢索等諸多方面有著重要應(yīng)用。經(jīng)典的邊緣算法認(rèn)為邊緣主要表現(xiàn)為圖像局部特征的不連續(xù)性,關(guān)于經(jīng)典邊緣檢測(cè)的算子集中在對(duì)灰度圖像的梯度研究,如Roberts算子、Sobel算子、Prewitt算子、Laplace算子、LOG算子等。

Pellegrino[1]和Nguyen[2]等通過(guò)實(shí)驗(yàn)系統(tǒng)地比較了常見(jiàn)邊緣檢測(cè)算子的性能后指出,在絕大多數(shù)情況下,Canny算子[3]具有最好的性能。Canny[3]提出了衡量邊緣檢測(cè)算法性能的3個(gè)理論準(zhǔn)則：檢測(cè)性能、定位精度和單邊響應(yīng),Canny算子正是對(duì)3個(gè)準(zhǔn)則同時(shí)進(jìn)行優(yōu)化的結(jié)果。近年來(lái)許多學(xué)者從圖像濾波、閾值的選取等方面對(duì)Canny算子進(jìn)行改進(jìn),提出了許多改善算法[4-7]。

Canny算子中非極大值抑制(NMS)過(guò)程,細(xì)化梯度幅值圖像中的屋脊帶,只保留梯度幅值局部最大值的點(diǎn),即圖像像素值變化最大的點(diǎn),實(shí)現(xiàn)邊緣的細(xì)化,提高定位精度和圖像邊緣的連貫性。然而傳統(tǒng)的Canny算子在進(jìn)行非極大值抑制時(shí),簡(jiǎn)單地將梯度幅值比梯度方向上相鄰點(diǎn)梯度幅值大的像素點(diǎn)檢測(cè)為邊緣點(diǎn),選擇進(jìn)行梯度幅值對(duì)比的相鄰點(diǎn)存在很大的隨意性,易產(chǎn)生隨機(jī)誤差,產(chǎn)生虛假邊緣。在深入研究圖像邊緣檢測(cè)的基礎(chǔ)上,從Canny算子的非極大值抑制(NMS)方面入手,聯(lián)系梯度方向周?chē)?個(gè)像素點(diǎn),引入鄰域相關(guān)系數(shù)進(jìn)行插值,將其作為對(duì)比點(diǎn)實(shí)現(xiàn)非極大值抑制過(guò)程,提高邊緣檢測(cè)準(zhǔn)確度,抑制虛假邊緣的產(chǎn)生,有效地實(shí)現(xiàn)邊緣檢測(cè)。

2 傳統(tǒng)Canny邊緣檢測(cè)算法

2.1 高斯一階導(dǎo)數(shù)濾波器平滑圖像

對(duì)圖像進(jìn)行平滑濾波,構(gòu)造濾波器,傳統(tǒng)Canny邊緣檢測(cè)算法選用高斯函數(shù)的一階導(dǎo)數(shù),是對(duì)信噪比與定位精度乘積最優(yōu)化的逼近。Canny算法首先使用二維高斯函數(shù)的一階導(dǎo)數(shù),對(duì)圖像進(jìn)行平滑[8],G為二維高斯函數(shù)：

其梯度矢量為：

利用對(duì)稱性和可分解性,可把▽G的二維濾波模板分解為兩個(gè)一維的行列濾波器。

其中σ為高斯濾波器參數(shù),控制著濾波的平滑程度,k為常數(shù),σ越小定位精度則越高,信噪比則越低,σ越大則情況反之。經(jīng)過(guò)多次試驗(yàn),σ=1.0時(shí)效果最好。

2.2 計(jì)算梯度的幅值M(i,j)與方向 θ i,j

采用2×2鄰域一階偏導(dǎo)的有限差分[8]來(lái)計(jì)算平滑后的圖像Ii,j梯度的幅值和方向。其中,x和y方向偏導(dǎo)數(shù)的兩個(gè)陣列Exi,j和Eyi,j分別為：

利用二階范數(shù)來(lái)計(jì)算梯度幅值：

梯度方向?yàn)椋?/p>

2.3 梯度幅值的非極大值抑制過(guò)程

Canny算子傳統(tǒng)的非極大值抑制(NMS)方法,簡(jiǎn)單地將目標(biāo)像素點(diǎn)的梯度幅值 M(i,j)分別與梯度幅值方向上兩端的鄰近像素點(diǎn)的梯度幅值 M′1(i,j)、M′2(i,j)進(jìn)行對(duì)比,若 M(i,j)＞M′2(i,j)且 M(i,j)＞M′1(i,j),則M(i,j)保持不變,否則M(i,j)=0,實(shí)現(xiàn)非極大值抑制過(guò)程。

2.4 檢測(cè)和連接邊緣

對(duì)經(jīng)過(guò)非極大值抑制(NMS)處理的梯度圖像用雙閾值算法檢測(cè)和連接邊緣。首先確定梯度直方圖分類的高、低2個(gè)閾值τh和τl。高低閾值的選擇決定了邊緣點(diǎn)的數(shù)量,邊緣點(diǎn)太少意味著一部分真實(shí)邊緣信息的丟失,而且影響連接邊緣,導(dǎo)致邊緣連續(xù)性下降,邊緣點(diǎn)太多又會(huì)引入噪聲邊緣,影響檢測(cè)效果。常規(guī)上高閾值依據(jù)梯度圖像的累計(jì)直方圖分析確定,Canny建議低閾值約為高閾值的一半。聯(lián)系實(shí)驗(yàn)中涉及的梯度圖像的累計(jì)直方圖分析,綜合考慮運(yùn)算效率,對(duì)比多次的實(shí)驗(yàn)檢測(cè)結(jié)果,確定 τh=0.7,τl=0.4時(shí)效果最佳。

3 基于非極大值抑制改進(jìn)的Canny邊緣檢測(cè)算法

3.1 改進(jìn)的非極大值抑制過(guò)程

傳統(tǒng)的非極大值抑制過(guò)程在選擇梯度幅值對(duì)比的鄰近像素點(diǎn)存在很大的隨意性,正如Basu[9]所指出“Canny算子在進(jìn)行非極大值抑制時(shí)簡(jiǎn)單地將梯度幅值比梯度方向上鄰近點(diǎn)梯度幅值大的像素點(diǎn)檢測(cè)為邊緣點(diǎn),而沒(méi)有考慮到這種差異是否大于隨機(jī)誤差導(dǎo)致的變化[9]”。梯度方向并不與鄰域像素點(diǎn)一一對(duì)應(yīng),存在重合等問(wèn)題,易產(chǎn)生隨機(jī)誤差,導(dǎo)致虛假邊緣出現(xiàn)。針對(duì)這些問(wèn)題,提出一種基于包括目標(biāo)像素點(diǎn)在內(nèi)的4像素點(diǎn),以及引入鄰域相關(guān)系數(shù)β在梯度方向上進(jìn)行插值的方法確定對(duì)比點(diǎn)。

如圖1(a)所示,以45°為界將坐標(biāo)系分為8個(gè)區(qū)域,依據(jù)中心對(duì)稱原理,只需考慮其4個(gè)區(qū)域,沿梯度方向θ(i,j)進(jìn)行插值。目標(biāo)像素點(diǎn)I(i,j)對(duì)應(yīng)的插值點(diǎn)為,假設(shè)垂直和水平方向上相鄰兩像素點(diǎn)距離為1,引入鄰域相關(guān)系數(shù)β,0＜β≤1,系數(shù)β為插值點(diǎn)與梯度方向上包括目標(biāo)像素點(diǎn)I(i,j)在內(nèi)的4點(diǎn)的相關(guān)度,β越接近于0,梯度方向上的插值點(diǎn)就越接近目標(biāo)像素點(diǎn) I(i,j),與其相關(guān)度就越大,反之沿梯度方向遠(yuǎn)離I(i,j),與之相關(guān)度隨即減少,但與沿梯度方向靠近的兩個(gè)像素點(diǎn)I(i-1,j+1)和 I(i-1,j+1)的相關(guān)度隨之增大。為了盡可能保證插值點(diǎn)與其它4點(diǎn)相關(guān)度相等,設(shè)定鄰域相關(guān)系數(shù)β=0.5。

圖1 4個(gè)區(qū)域?qū)?yīng)的插值方式

如圖1(a)所示,依據(jù)參數(shù)β和鄰域像素點(diǎn)I(i-1,j),I(i-1,j+1)插值得到Kup,同理可得,依據(jù)參數(shù)β和鄰域像素點(diǎn)I(i,j),I(i,j+1)插值得到Kdown,Kup與Kdown分別為：

如圖1(b)所示,依據(jù)參數(shù)β和鄰域像素點(diǎn)I(i,j),I(i-1,j)插值得到Kleft,同理可得,依據(jù)參數(shù)β和鄰域像素點(diǎn) I(i,j+1),I(i-1,j+1)插值得到 Kright,Kleft與Kright分別為：

依據(jù)Kup與Kdown可得插入點(diǎn)其梯度幅值為：

如圖1(c)所示,依據(jù)參數(shù)β和鄰域像素點(diǎn)I(i,j),I(i-1,j)插值得到Kright,同理可得,依據(jù)參數(shù) β和鄰域像素點(diǎn)I(i,j-1),I(i-1,j-1)插值得到 Kleft,Kleft與Kright分別為：

依據(jù)Kleft與Kright可得插入點(diǎn)插入點(diǎn)的梯度幅值為：

如圖1(d)所示,依據(jù)參數(shù)β和鄰域像素點(diǎn)I(i-1,j),I(i-1,j-1)插值得到同理可得,依據(jù)參數(shù) β和鄰域像素點(diǎn)I(i,j),I(i,j-1)插值得到與分別為：

依據(jù)Kup與Kdown可得插入點(diǎn)X i,j,插入點(diǎn)X i,j的梯度幅值為：

X′(i,j)為X i,j關(guān)于中心對(duì)稱的插值點(diǎn),同理可得：

3.2 算法實(shí)現(xiàn)步驟

(1)用高斯一階導(dǎo)數(shù)濾波器對(duì)讀入圖像進(jìn)行濾波,平滑圖像。

(2)計(jì)算濾波后圖像的梯度幅值和梯度方向。

(3)利用改進(jìn)后的方法插值確定對(duì)比點(diǎn),與目標(biāo)像素點(diǎn)的梯度幅值進(jìn)行對(duì)比,完成新的非極大值抑制過(guò)程(Improved-NMS)。

(4)對(duì)處理過(guò)后的梯度圖像用雙閾值算法進(jìn)行檢測(cè)和連接,得到邊緣圖像。

4 實(shí)驗(yàn)結(jié)果與比較

實(shí)驗(yàn)用計(jì)算機(jī)配置為Celeron(R)2.93GHz,1G內(nèi)存,選擇Matlab編程實(shí)現(xiàn)算法,實(shí)驗(yàn)選取不同的3幅圖,分別采用傳統(tǒng)Canny算法、文獻(xiàn)[7]提出的選用GCV閾值小波濾波改進(jìn)的Canny算法、基于非極大值抑制改進(jìn)的Canny算法進(jìn)行邊緣檢測(cè)分析。實(shí)驗(yàn)中的相關(guān)參數(shù)取值如下：σ=1.0,τh=0.7,τl=0.4,β=0.5。由圖2的檢測(cè)結(jié)果可以看出,基于非極大值抑制改進(jìn)的Canny算法檢測(cè)出的邊緣圖像斷點(diǎn)相對(duì)于前兩種算法少,邊緣的連貫性好,對(duì)虛假邊緣的抑制有明顯的提高。經(jīng)典的Lena圖像中,文中算法對(duì)模特臉及帽子處虛假邊緣的抑制明顯,頭發(fā)處的邊緣細(xì)節(jié)的識(shí)別效果也有所改善。Pepper圖中辣椒的主體輪廓連貫性更好,表面的虛假邊緣得到抑制。在真實(shí)拍攝的風(fēng)景圖像上顯示基于非極大值抑制改進(jìn)的Canny邊緣檢測(cè)算法也具有更好的性能。

圖2 Canny邊緣檢測(cè)結(jié)果

文獻(xiàn)[10]介紹了一種評(píng)價(jià)圖像邊緣檢測(cè)效果的方法：用m表示檢測(cè)到的邊緣像素點(diǎn)的數(shù)目,n表示邊緣像素中滿足八鄰域單連通條件的像素點(diǎn)數(shù)目,n/m的大小反映了邊緣線形連接程度,其數(shù)值越小則連接程度越高,反之越差。邊緣的線性連接程度對(duì)總體的邊緣評(píng)價(jià)的影響體現(xiàn)在了錯(cuò)檢和漏檢中,當(dāng)邊緣連接程度高時(shí),邊緣的連通性就越好,錯(cuò)檢、漏檢則相對(duì)少。反之,錯(cuò)檢、漏檢相對(duì)就多。數(shù)值n/m越小則連接程度越高,提取的邊緣效果就越好,從表1可以看出改進(jìn)后算法的優(yōu)越性。

表1 實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)表

5 結(jié)束語(yǔ)

在傳統(tǒng)Canny算子基礎(chǔ)上,對(duì)Canny算子的非極大值抑制過(guò)程進(jìn)行改進(jìn),引入了依據(jù)目標(biāo)像素點(diǎn)梯度方向周?chē)?像素點(diǎn)的梯度和鄰域相關(guān)系數(shù)進(jìn)行插值的方法,準(zhǔn)確定位與目標(biāo)像素點(diǎn)梯度進(jìn)行對(duì)比的梯度點(diǎn),優(yōu)化了Canny算子的非極大值抑制過(guò)程。仿真實(shí)驗(yàn)結(jié)果表明,提取出的圖像邊緣更加豐富、清晰,邊緣的細(xì)節(jié)更加完整,連通性更好,對(duì)虛假的邊緣有更好的抑制。進(jìn)一步研究該邊緣檢測(cè)方法,使其對(duì)噪音不敏感,提高算法的魯棒性,這是今后需要努力的地方。

[1]F A Pellegrino.Edge Detection Revisited[J].IEEE Trans On System Man and Cybernetics.2004,34(3)：1500-1517.

[2]T B Nguyen,D Ziou.Contextual and Non-contextual Performance Evaluation of Edge Detectors[J].Pattern Recognition Letters,2000,21(8)：805-816.

[3]J F Canny.A Computational Approach to Edge Detection[J].IEEE Trans On Pattern Analysis and Machine Intelligence,1986,8(6)：679-698.

[4]王植,賀賽先.一種基于Canny理論的自適應(yīng)邊緣檢測(cè)方法[J].中國(guó)圖像圖形報(bào),2004,9(8)：957-961.

[5]李華強(qiáng),喻擎蒼,方玫.Canny算子中Otsu閾值分割法的運(yùn)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(9)：2297-2299.

[6]李二森,張保明,周曉明.自適應(yīng)Canny邊緣檢測(cè)算法研究[J].測(cè)繪科學(xué),2008,33(6)：119-120.

[7]黃劍玲,鄭雪梅.一種改進(jìn)的基于Canny算子的圖像邊緣提取算法[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(25)：170-172.

[8]賈云得.機(jī)器視覺(jué)[M].北京：科學(xué)出版社,2000：97-100.

[9]M Basu.Gaussian-based edge-detection methods-A survey[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C ：Applications and Reviews,2002,32(3)：252-260.

[10]Hu Dong,Tian Xiang-Zhong.A multi-directions algorithm for edge detection based on fuzzy mathematical morphology[C].Proceedings of 16th International Conference on Artificial Reality and Telexistence-Workshops ICAT'06.HangZhou ：IEEE Computer Society,2006：361-364.