4.2 Canny邊緣偵測#

概念說明#

John Canny 在 1986 年提出「最優邊緣偵測器」的三個準則：

低錯誤率：真邊緣不漏、假邊緣不多。
良好定位：偵測到的點盡量靠近真實邊緣中心。
單一響應：一條邊緣只回報一次，不要多條重複線。

Canny 從數學推導出最佳濾波器近似為高斯的一階導數，並把整個流程組織成四道工序。今日「Canny 演算法」指這個完整 pipeline：

步驟一：高斯平滑。用 σ 控制的核心模糊影像抑制雜訊。σ 是尺度旋鈕：σ 大→只留粗輪廓、細節消失；σ 小→細節多但雜訊也多。

步驟二：計算梯度。用 Sobel 求 gx、gy 與大小 M、方向 θ。

步驟三：非極大值抑制 (Non-Maximum Suppression, NMS)。粗門檻後一條邊會變成寬數像素的「山脊」；NMS 沿著梯度方向檢查每個像素，只有比兩側鄰居都強的才留下，把山脊削成 1 像素寬。具體做法：把 θ 量化成 0°、45°、90°、135° 四個方向，各對應兩個比較鄰居。

步驟四：雙門檻滯後追蹤 (hysteresis)。單一門檻的兩難：高門檻斷掉弱邊緣、低門檻引入假邊緣。Canny 用兩個門檻 T_high、T_low（經驗比例約 2:1 ~ 3:1）：

M ≥ T_high：確定是邊緣（強邊緣）。
T_low ≤ M < T_high：弱邊緣——只有當它（直接或間接）連接到一個強邊緣時才保留。
M < T_low：捨棄。

滯後追蹤讓連續的邊緣得以完整保留（弱段接著強段），而孤立的雜訊弱響應被斬除。這可用堆疊式 flood fill 實作。

演算法步驟#

影像轉灰階、轉 float。
高斯模糊（參數 σ）。
Sobel 求 gx、gy → M、θ。
NMS：θ 量化四方向，比較對應兩鄰居，非局部極大者歸零。
雙門檻：標記強/弱邊緣。
從每個強邊緣做連通追蹤（BFS/DFS），吸收相連的弱邊緣。
輸出 0/255 邊緣圖。

Python 程式碼範例#

import numpy as np
from PIL import Image

rng = np.random.default_rng(4)
img = np.full((50, 50), 100.0)
img[:, 25:] = 180
img[10:20, 35:45] = 0
img += rng.normal(0, 4, (50, 50))

def gaussian1d(k, sigma):
    x = np.arange(k) - k//2
    g = np.exp(-x**2/(2*sigma**2)); return g/g.sum()

def blur(img, k=5, sigma=1.2):
    g = gaussian1d(k, sigma)
    t = np.apply_along_axis(lambda r: np.convolve(r, g, "same"), 1, img)
    return np.apply_along_axis(lambda c: np.convolve(c, g, "same"), 0, t)

def conv3(img, K):
    P = np.pad(img, 1, mode="edge")
    out = np.zeros(img.shape)
    for y in range(img.shape[0]):
        for x in range(img.shape[1]):
            out[y, x] = (P[y:y+3, x:x+3] * K).sum()
    return out

def canny(img, th=120, tl=50):
    s = blur(img)
    gx = conv3(s, np.array([[-1,0,1],[-2,0,2],[-1,0,1]]))
    gy = conv3(s, np.array([[-1,-2,-1],[0,0,0],[1,2,1]]))
    M = np.hypot(gx, gy)
    ang = (np.degrees(np.arctan2(gy, gx)) + 180) % 180   # 0~180
    H, W = M.shape
    nms = M.copy()
    for y in range(1, H-1):
        for x in range(1, W-1):
            a = ang[y, x]
            if a < 22.5 or a >= 157.5:   n1, n2 = M[y, x-1], M[y, x+1]
            elif a < 67.5:               n1, n2 = M[y-1, x+1], M[y+1, x-1]
            elif a < 112.5:              n1, n2 = M[y-1, x], M[y+1, x]
            else:                        n1, n2 = M[y-1, x-1], M[y+1, x+1]
            if M[y, x] < n1 or M[y, x] < n2:
                nms[y, x] = 0
    strong, weak = nms >= th, (nms >= tl) & (nms < th)
    edge = strong.copy()
    stack = list(zip(*np.where(strong)))            # 滯後追蹤
    while stack:
        y, x = stack.pop()
        for dy in (-1, 0, 1):
            for dx in (-1, 0, 1):
                ny, nx = y+dy, x+dx
                if 0 <= ny < H and 0 <= nx < W and weak[ny, nx] and not edge[ny, nx]:
                    edge[ny, nx] = True
                    stack.append((ny, nx))
    return edge

for T_h, T_l in [(50, 20), (120, 50), (300, 120)]:
    e = canny(img, T_h, T_l)
    print(f"T_high={T_h}: 邊緣像素 {e.sum()//255}")

e = canny(img, 120, 50)
print("NMS 前 1 像素寬測試：邊緣總數/邊緣線長度比 ≈ 1 表示單響應")

執行後可見：門檻太低（50）時雜訊產生大量假邊緣像素；太高（300）時方塊的弱邊緣被遺漏；中間值得到乾淨、細而完整的輪廓。這展示雙門檻的調參直覺。

複雜度分析#

四道工序均 O(H·W)：高斯模糊（可分離）O(H·W·k)、Sobel O(H·W)、NMS O(H·W)（每像素固定兩次比較）、滯後追蹤每像素最多進出堆疊一次 O(H·W)。總計 O(H·W)，常數約為純 Sobel 的數倍。空間 O(H·W)（M、θ、nms、edge）。主要成本在 Python 迴圈；向量化 NMS 可用四個方向的遮罩平行處理。σ 與雙門檻是僅有的三個參數，實務上 σ=1~2、T_high 為梯度最大值的 10~30% 是常用起點。

練習#

把 NMS 移除直接門檻化，觀察邊緣厚度變成 3~4 像素；量化比較 NMS 前後「每單位邊緣長度的像素數」。
對含 σ=10 強雜訊的影像測試 σ=0.5、1.5、3.0 的 Canny，找出「雜訊假邊緣數 < 10 且真邊緣保留 > 90%」的 σ。
說明為何滯後追蹤必須用連通性而非「弱邊緣一律保留」。設計一個會被「一律保留」欺騙的假邊緣影像並驗證。