9.3 模板比對與霍夫轉換#

概念說明#

本節介紹兩個解決「全局幾何搜尋」的經典方法，它們的搜尋對象不同：模板比對找「一小塊影像」，霍夫轉換找「一組滿足參數方程的像素」。

模板比對 (template matching)：給定小圖（模板 T，如 w×h），在目標影像 I 上滑動，計算每個位置的相似度，峰值即模板位置。最常用的指標是正規化互相關 (NCC)：

NCC(x, y) = Σ T(x',y')·I(x+x', y+y') / √(Σ T² · Σ I²)

取值 [−1, 1]，1 表示完全相同。正規化的好處是對亮度與對比的線性變化不敏感。另一常見選擇是平方差之和 SSD（越小越好）。模板比對的弱點：對旋轉、尺度、非線性光照敏感——模板稍微轉個 5° 匹配就崩壞；此時應改用特徵匹配（上一節）。它的強項是簡單、精確、可解釋，適合受控環境（工業檢測、UI 元素定位、固定場景的目標追蹤初定位）。

霍夫轉換 (Hough Transform, 1962/1972) 解決的問題：第 4 章的邊緣偵測給出一堆離散的邊緣點，哪些點構成一條直線？直接枚舉點對組合是指數級的。霍夫的洞察是對偶性：影像空間的一條直線 y = mx + b 對應參數空間 (m, b) 的一個點；而影像空間的一個點 (x₀, y₀) 對應參數空間的一條線 b = −x₀m + y₀。共線的點 → 參數空間的線相交於同一點。於是演算法變成：每個邊緣點在參數空間「投票」給所有過它的直線，得票最高的參數就是影像中的直線。

實務用極座標表示避免垂直線的 m = ∞ 問題：

ρ = x·cosθ + y·sinθ

參數空間是 (ρ, θ) 的二維累加器（θ 離散成 180 格，ρ 離散成影像對角線長度格）。每個邊緣點沿 θ 掃 180 次，各投一票。峰值搜尋（含非極大值抑制）輸出直線清單。推廣：圓 Hough（三參數 (a, b, r)，用梯度方向降維加速）、廣義霍夫 (GHT，任意形狀用 R-table)。霍夫對雜訊與遮擋魯棒（斷開的虛線也能投出峰值），但累加器維度隨參數數量爆炸，三參數以上就昂貴。

演算法步驟#

模板比對：1. 模板與影像皆減去均值、除以標準差（正規化）。2. 滑動窗口逐位置算 NCC。3. 找全域最大值（可設門檻取多個）。

直線霍夫：1. 邊緣偵測 + 門檻化得邊緣點集。2. 建立累加器 A[θ][ρ] 歸零。3. 每個邊緣點對每個 θ 計算 ρ 並累加。4. 找 A 的局部峰值（超過票數門檻的極大）。5. 把 (ρ, θ) 轉回直線，可沿影像邊界截取線段。

Python 程式碼範例#

import numpy as np

# ---- 模板比對 ----
scene = np.zeros((50, 50))
scene[20:30, 30:40] = 100          # 目標：10×10 亮方塊
scene[5:12, 5:12] = 50             # 干擾：較暗方塊
tmpl = np.full((10, 10), 100.0)

def ncc(I, T):
    H, W = I.shape; h, w = T.shape
    Tz = T - T.mean()
    Tn = np.sqrt((Tz**2).sum())
    best = np.zeros((H-h+1, W-w+1))
    for y in range(H-h+1):
        for x in range(W-w+1):
            P = I[y:y+h, x:x+w]
            Pz = P - P.mean()
            best[y, x] = (Tz*Pz).sum() / (Tn*np.sqrt((Pz**2).sum()) + 1e-9)
    return best

score = ncc(scene, tmpl)
y, x = np.unravel_index(score.argmax(), score.shape)
print(f"模板比對最佳位置: ({x}, {y}), NCC = {score.max():.3f}（真實 (30,20)）")
print("干擾方塊處 NCC =", score[5, 5].round(3))

# ---- 直線霍夫 ----
# 建立含兩條直線的邊緣圖
edge = np.zeros((60, 60), bool)
edge[15, 5:55] = True                    # 水平線 y=15
for i in range(40):                      # 45° 斜線
    edge[i, i+15] = True
edge[40, 45] = True                      # 雜訊點

H, W = edge.shape
theta_bins, rho_max = 180, int(np.hypot(H, W))
A = np.zeros((2*rho_max, theta_bins))
ys, xs = np.where(edge)
for theta_deg in range(theta_bins):
    t = np.radians(theta_deg)
    rho = (xs*np.cos(t) + ys*np.sin(t)).astype(int) + rho_max
    np.add.at(A[:, theta_deg], rho, 1)

# 找峰值（票數 >= 35 的極大）
votes = A.max(axis=1) - 0
peaks = []
for i in range(2*rho_max):
    for j in range(theta_bins):
        if A[i, j] >= 35 and A[i, j] == A[max(0,i-2):i+3, max(0,j-3):j+3].max():
            peaks.append((A[i, j], i - rho_max, j))
peaks.sort(reverse=True)
print("霍夫偵測到的直線 (票數, ρ, θ°):", [(int(v), r, t) for v, r, t in peaks[:4]])
print("理論: 水平線 y=15 → ρ=15, θ=90°；斜線 → ρ≈10.6, θ=135°")

執行後：NCC 在 (30, 20) 得 1.000（亮方塊與模板完全一致），暗方塊處因正規化掉到接近 0 甚至負值（模板比內容亮）；霍夫的兩條真直線得到約 50 與 40 票的明顯峰值，單一雜訊點最多只投 180 個不同 (ρ,θ) 中每格 1 票、達不到門檻——「投票門檻」就是霍夫的抗雜訊機制。

複雜度分析#

模板比對：每位置 w·h 次乘加，O((W−w+1)(H−h+1)·w·h)——對 1000×1000 影像配 100×100 模板約 10¹⁰ 次運算，樸素實作很慢。加速：FFT 版互相關（卷積定理，第 5 章）把相關項降到 O(N log N)；積分圖把 ΣI、ΣI² 變 O(1)，NCC 的分母部分免重算。霍夫：邊緣點數 E，每點 θ_bins 次投票，O(E·180)，加峰值搜尋 O(acc)。累加器空間 O(ρ·θ)（直線）但圓霍夫是 O(W·H·r) 級的三維——參數維度是指數負擔，這是霍夫的死穴。模板比對輸出「位置」，霍夫輸出「幾何參數」；當目標形狀可參數化且可能有遮擋時，霍夫幾乎是唯一解。

練習#

把模板旋轉 10° 後再做 NCC 比對，量化峰值下降程度；再對同一場景用 9.2 節的特徵匹配方法定位目標，比較兩者的旋轉容忍度。
實作 FFT 加速的互相關，測量與樸素版本在 512×512 影像、64×64 模板下的執行時間比。
對本節邊緣圖加入 100 個隨機雜訊點，測試霍夫票數門檻 30/40/50 下偵測到的假直線數，找出抗雜訊與漏檢的平衡點。