canny算法

canny算法

Canny邊緣檢測算法是John F. Canny於 1986 年開發出來的一個多級邊緣檢測算法。 截止2014年8月, Canny發表的該篇論文,已被引用19000餘次。

算法概述

Canny邊緣檢測運算元是John F. Canny於 1986 年開發出來的一個多級邊緣檢測算法。更為重要的是 Canny 創立了 邊緣檢測計算理論(Computational theory of edge detection)解釋這項技術如何工作。

通常情況下邊緣檢測的目的是在保留原有圖像屬性的情況下,顯著減少圖像的數據規模。目前有多種算法可以進行邊緣檢測,雖然Canny算法年代久遠,但可以說它是邊緣檢測的一種標準算法,而且仍在研究中廣泛使用。

最優邊緣準則

Canny 的目標是找到一個最優的邊緣檢測算法,最優邊緣檢測的含義是:

(1)最優檢測:算法能夠儘可能多地標識出圖像中的實際邊緣,漏檢真實邊緣的機率和誤檢非邊緣的機率都儘可能小;

(2)最優定位準則:檢測到的邊緣點的位置距離實際邊緣點的位置最近,或者是由於噪聲影響引起檢測出的邊緣偏離物體的真實邊緣的程度最小;

(3)檢測點與邊緣點一一對應:運算元檢測的邊緣點與實際邊緣點應該是一一對應。

為了滿足這些要求 Canny 使用了變分法(calculus of variations),這是一種尋找最佳化特定功能的函式的方法。最優檢測使用四個指數函式項表示,但是它非常近似於高斯函式的一階導數。

算法的實現步驟

Canny邊緣檢測算法可以分為以下5個步驟:

套用高斯濾波來平滑圖像,目的是去除噪聲

找尋圖像的強度梯度(intensity gradients)

套用非最大抑制(non-maximum suppression)技術來消除邊誤檢(本來不是但檢測出來是)

套用雙閾值的方法來決定可能的(潛在的)邊界

利用滯後技術來跟蹤邊界

1.

套用高斯濾波來平滑圖像,目的是去除噪聲

2.

找尋圖像的強度梯度(intensity gradients)

3.

套用非最大抑制(non-maximum suppression)技術來消除邊誤檢(本來不是但檢測出來是)

4.

套用雙閾值的方法來決定可能的(潛在的)邊界

5.

利用滯後技術來跟蹤邊界

1. 圖像平滑(去噪聲)

任何邊緣檢測算法都不可能在未經處理的原始數據上很好地工作,所以第一步是對原始數據與高斯 mask 作卷積,得到的圖像與原始圖像相比有些輕微的模糊(blurred)。這樣,單獨的一個像素噪聲在經過高斯平滑的圖像上變得幾乎沒有影響。以下為一個5X5高斯濾波器(高斯核,標準差\delta=1.4),其中A為原始圖像,B為平滑後的圖像。

canny算法 canny算法
canny算法 canny算法

2. 尋找圖像中的強度梯度

Canny算法的基本思想是找尋一幅圖像中灰度強度變化最強的位置。所謂變化最強,即指梯度方向。平滑後的圖像中每個像素點的梯度可以由Sobel運算元(一種卷積運算)來獲得(opencv中有封裝好的函式,可以求圖像中每個像素點的n階導數)。首先,利用如下的核來分別求得沿水平(x)和垂直(y)方向的梯度G_X和G_Y。

K_{GX} = [-1 0 1 ; -2 0 2 ; -1 0 1], K_{GY} = {-1 -2 -1 ; 0 0 0 ; 1 2 1}

之後便可利用公式來求得每一個像素點的梯度度量值(gradient magnitude,可能翻譯得不準確)。

canny算法 canny算法
canny算法 canny算法

,有時為了計算簡便,也會使用G_X和G_Y的無窮大範數來代替二範數。把平滑後的圖像中的每一個點用G代替,可以獲得如下圖像。從下圖可以看出,在變化劇烈的地方(邊界處),將獲得較大的梯度度量值G,對應的顏色為白色。然而,這些邊界通常非常粗,難以標定邊界的真正位置。為了做到這一點(參考非極大抑制Non-maximum suppression一節),還必須存儲梯度方向,其公式如下圖所示。也就是說在這一步我們會存數兩塊數據,一是梯度的強度信息,另一個是梯度的方向信息。

canny算法 canny算法

3. 非極大抑制Non-maximum suppression

這一步的目的是將模糊(blurred)的邊界變得清晰(sharp)。通俗的講,就是保留了每個像素點上梯度強度的極大值,而刪掉其他的值。對於每個像素點,進行如下操作:

a) 將其梯度方向近似為以下值中的一個(0,45,90,135,180,225,270,315)(即上下左右和45度方向)

b) 比較該像素點,和其梯度方向正負方向的像素點的梯度強度

c) 如果該像素點梯度強度最大則保留,否則抑制(刪除,即置為0)

為了更好的解釋這個概念,看下圖。

canny算法 canny算法

圖中的數字代表了像素點的梯度強度,箭頭方向代表了梯度方向。以第二排第三個像素點為例,由於梯度方向向上,則將這一點的強度(7)與其上下兩個像素點的強度(5和4)比較,由於這一點強度最大,則保留。處理後效果如下圖所示。

canny算法 canny算法

上圖中,可以想像,邊界處的梯度方向總是指向垂直於邊界的方向,即最後會保留一條邊界處最亮的一條細線。

4.雙閾值(Double Thresholding)

經過非極大抑制後圖像中仍然有很多噪聲點。Canny算法中套用了一種叫雙閾值的技術。即設定一個閾值上界和閾值下界(opencv中通常由人為指定的),圖像中的像素點如果大於閾值上界則認為必然是邊界(稱為強邊界,strong edge),小於閾值下界則認為必然不是邊界,兩者之間的則認為是候選項(稱為弱邊界,weak edge),需進行進一步處理。經過雙閾值處理的圖像如下圖所示

canny算法 canny算法

上圖中右側強邊界用白色表示,弱邊界用灰色表示。

5.利用滯後的邊界跟蹤

這裡就不細作解釋了。大體思想是,和強邊界相連的弱邊界認為是邊界,其他的弱邊界則被抑制。

以上內容均翻譯自參考文獻【4】

上一個百科版本:

圖像中的邊緣可能會指向不同的方向,所以 Canny 算法使用 4 個 掩模(mask) 檢測水平、垂直以及對角線方向的邊緣。原始圖像與每個 mask 所作的卷積都存儲起來。對於每個點我們都標識在這個點上的最大值以及生成的邊緣的方向。這樣我們就從原始圖像生成了圖像中每個點亮度梯度圖以及亮度梯度的方向。以下兩個公式分別求取高斯濾波後圖像的梯度幅值及其方向的表達式。這一步,也叫稱為非極大抑制(Non-maximum suppression)。

canny算法 canny算法
canny算法 canny算法

3. 在圖像中跟蹤邊緣

較高的亮度梯度比較有可能是邊緣,但是沒有一個確切的值來限定多大的亮度梯度是邊緣多大又不是,所以 Canny 使用了滯後閾值。

滯後閾值(Hysteresis thresholding) 需要兩個閾值,即高閾值與低閾值。假設圖像中的重要邊緣都是連續的曲線,這樣我們就可以跟蹤給定曲線中模糊的部分,並且避免將沒有組成曲線 的噪聲像素當成邊緣。所以我們從一個較大的閾值開始,這將標識出我們比較確信的真實邊緣,使用前面導出的方向信息,我們從這些真正的邊緣開始在圖像中跟蹤 整個的邊緣。在跟蹤的時候,我們使用一個較小的閾值,這樣就可以跟蹤曲線的模糊部分直到我們回到起點。

一旦這個過程完成,我們就得到了一個二值圖像,每點表示是否是一個邊緣點。

一個獲得亞像素精度邊緣的改進實現是在梯度方向檢測二階方嚮導數的過零點,它在梯度方向的三階方嚮導數滿足符號條件。

滯後閾值也可以用於亞像素邊緣檢測。

參數設定

Canny 算法包含許多可以調整的參數,它們將影響到算法的計算的時間與實效。

高斯濾波器的大小:第一步所有的平滑濾波器將會直接影響 Canny 算法的結果。較小的濾波器產生的模糊效果也較少,這樣就可以檢測較小、變化明顯的細線。較大的濾波器產生的模糊效果也較多,將較大的一塊圖像區域塗成一個 特定點的顏色值。這樣帶來的結果就是對於檢測較大、平滑的邊緣更加有用,例如彩虹的邊緣。

雙閾值:使用兩個閾值比使用一個閾值更加靈活,但是它還是有閾值存在的共性問題。設定的閾值過高,可能會漏掉重要信息;閾值過低,將會把枝節信息看得很重要。很難給出一個適用於所有圖像的通用閾值。目前還沒有一個經過驗證的實現方法。

OpenCV中的Canny函式

採用 Canny 算法做邊緣檢測

void cvCanny( const CvArr* image, CvArr* edges, double threshold1,double threshold2, int aperture_size=3 );

--image 輸入圖像.

--edges 輸出的邊緣圖像

--threshold1 第一個閾值

--threshold2 第二個閾值

--aperture_size Sobel 運算元核心大小 (見 cvSobel).

函式 cvCanny 採用 CANNY 算法發現輸入圖像的邊緣而且在輸出圖像中標識這些邊緣。threshold1和threshold2 當中的小閾值用來控制邊緣連線,大的閾值用來控制強邊緣的初始分割。

相關詞條

相關搜尋

熱門詞條

聯絡我們