4.6　Canny算法

Canny算法是John F.Canny于1986年開發出來的一個多級邊緣檢測算法。雖然Canny算法年代久遠，但可以說它是邊緣檢測的一種經典算法，因此被廣泛使用。

Canny的目標是找到一個最優的邊緣檢測算法，其含義如下：

①最優檢測。該算法能夠盡可能多地標識出圖像中的實際邊緣，漏檢真實邊緣的概率和誤檢非邊緣的概率都要盡可能小。

②最優定位準則。檢測到的邊緣點的位置距離實際邊緣點的位置最近，或者是由于噪聲影響引起檢測出的邊緣偏離物體的真實邊緣的程度最小。

③檢測點與邊緣點一一對應。算子檢測的邊緣點與實際邊緣點應該是一一對應。

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

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

①應用高斯濾波來平滑圖像，目的是去除噪聲。

②找尋圖像的強度梯度（intensity gradients）。

③應用非最大抑制（non-maximum suppression）技術來消除邊誤檢（本來不是但檢測出來是）。

④應用雙閾值的方法來確定可能的邊界。

⑤利用滯后技術來跟蹤邊界。

以下分別說明各個步驟。

（1）圖像平滑（去噪聲）

去噪聲處理是目標提取的重要步驟，第5章專門介紹各種圖像去噪聲處理方法。Canny算法的第一步是對原始數據與高斯濾波器（詳細內容見第5章）作卷積，得到的平滑圖像與原始圖像相比有些輕微的模糊（blurred）。這樣，單獨的一個像素噪聲在經過高斯平滑的圖像上變得幾乎沒有影響。以下為一個5×5高斯濾波器（高斯核的標準偏差σ=2），其中A為原始圖像，B為平滑后圖像。圖4.11是原圖像及高斯平滑結果圖像。

（2）尋找圖像中的強度梯度（梯度運算）

Canny算法的基本思想是找尋一幅圖像中灰度強度變化最強的位置，即梯度方向。平滑后的圖像中每個像素點的梯度可以由4.2節的Sobel算子等獲得。以Sobel算子為例，首先分別計算水平（x）和垂直（y）方向的梯度fx和fy；然后利用式（4.2）來求得每一個像素點的梯度強度值G。把平滑后圖像中的每一個點用G代替，可以獲得圖4.12的梯度強度圖像。從圖4.12可以看出，在變化劇烈的地方（邊界處），將獲得較大的梯度強度值G，對應的像素值較大。然而，由于這些邊界通常非常粗，難以標定邊界的真正位置，因此還必須存儲梯度方向［式（4.3）］，進行非極大抑制處理。也就是說這一步需要存儲兩塊數據，一是梯度的強度信息，另一個是梯度的方向信息。

（3）非極大抑制（non-maximum suppression）

這一步的目的是將模糊（blurred）的邊界變得清晰（sharp）。通俗地講，就是保留了每個像素點上梯度強度的極大值，而刪掉其他的值。

以梯度強度圖像為對象，對每個像素點進行如下操作：

a.將其梯度方向近似為0、45、90、135、180、225、270、315中的一個，即上下左右和45°方向。

b.比較該像素點和其梯度方向（正負）的像素值的大小。

c.如果該像素點的像素值最大，則保留，否則抑制（即置為0）。

為了更好地解釋這個概念，看下圖4.13。

圖中的數字代表了像素點的梯度強度，箭頭方向代表了梯度方向。以第二排第三個像素點為例，由于梯度方向向上，則將這一點的強度（7）與其上下兩個像素點的強度（5和4）比較，由于這一點強度最大，則保留。

對圖4.12進行非極大抑制處理結果如圖4.14所示。

（4）雙閾值（double thresholding）處理

經過非極大抑制后的圖像中仍然有很多噪聲點。Canny算法中應用了一種叫雙閾值的技術，即設定一個高閾值和低閾值，圖像中的像素點如果大于高閾值則認為必然是邊界（稱為強邊界，strong edge），將其像素值變為255；小于低閾值則認為必然不是邊界，將其像素值變為0，兩者之間的像素被認為是邊界候選點（稱為弱邊界，weak edge），像素值不變。

高閾值和低閾值的設定，采用第3章介紹的p參數法，一般分別設定直方圖下位（黑暗部分）80%和40%的位置會獲得較好的處理效果。也可以調整閾值的設定值，看看是否處理效果會更好。

在實際執行時，這一步只是通過比例計算出高閾值和低閾值的具體數值，并不改變圖4.14的像素值。

（5）滯后邊界跟蹤

對雙閾值處理后的圖像進行滯后邊界跟蹤處理，具體步驟如下：

①同時掃描非極大抑制圖像I（圖4.14）和梯度強度圖像G（圖4.12），當某像素p（x，y）在I圖像不為0，而在G圖像上大于高閾值、小于255時，將p（x，y）在I圖像和G圖像上都設為255（白色），將該像素點設為q（x，y），跟蹤以q（x，y）為開始點的輪廓線。

②考察q（x，y）在I圖像和G圖像的8鄰近區域，如果某個8鄰域像素s（x，y）在I圖像大于零，而在G圖像上大于低閾值，則在G圖像上設該像素為白色，并將該像素設為q（x，y）。

③循環進行步驟②，直到沒有符合條件的像素為止。

④循環執行步驟①～③，直到掃描完整個圖像為止。

⑤掃描G圖像，將不為白色的像素置0。

至此，完成Canny算法的邊緣檢測。圖4.15是滯后邊界跟蹤的結果。

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

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

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