9.2 特徵描述與匹配SIFT與BRIEF#

概念說明#

角點只給了「哪裡」，匹配還需要「那裡長什麼樣」——描述子 (descriptor) 把特徵點周圍的影像內容編碼成向量，兩張影像的匹配就是「在描述子空間找最近鄰」。

SIFT (Scale-Invariant Feature Transform, Lowe 1999/2004) 是里程碑，完整流程：

尺度空間極值：對影像做一系列逐漸增大的高斯模糊（尺度空間），相鄰兩層相減得 DoG (Difference of Gaussians)——它是 LoG（4.3 節）的廉價近似。在 DoG 金字塔中找「同層 8 鄰居 + 上下層各 9 鄰居共 26 個都比不過」的極值點 → 尺度不變的候選關鍵點。σ 與斑點尺寸的理論關係（σ ≈ 直徑/(2√2)）在此直接派上用場。
關鍵點定位：對 DoG 擬合二次曲面取極值（次像素定位），剔除對比弱（邊緣雜訊）與邊緣上的點（用 Hessian 檢查兩特徵值比）。
方向指定：在關鍵點尺度上計算梯度方向直方圖（36 桶），主峰方向 = 關鍵點方向 → 之後的描述以該方向為基準 → 旋轉不變。
描述子：以關鍵點為中心取 16×16 區域，分 4×4 子區，每個子區算 8 方向梯度直方圖 → 128 維向量。對長度做歸一化 → 光照（線性）不變。

匹配：兩張圖的描述子做最近鄰（歐氏距離），並用比值測試 (ratio test)：最近距離 / 次近距離 < 0.8 才接受——歧義的匹配（兩個候選差不多近）多半是錯的。最後可用 RANSAC + 單應矩陣（7.3 節）剔除殘餘的幾何不一致匹配。

BRIEF (2010) 走完全相反的路：不找尺度空間、不做方向歸一，描述子是一串二進位比較。在關鍵點周圍隨機挑 N 對點（用固定種子的機率分布，如高斯對），每對做一次亮度比較：

τ(p; a, b) = 1 if p(a) < p(b) else 0

N=256 對 → 256 位元 = 32 位元組的描述子。匹配用 Hamming 距離——CPU 有 popcount 指令，比歐氏距離快一個數量級。BRIEF 快但不具旋轉與尺度不變性；後繼者 ORB 加入旋轉不變的方向與學習過的取樣對，成為實務上「免費」的預設。設計哲學的對比很有教育意義：SIFT 追求不變性與魯棒（適合寬基線匹配、3D 重建），BRIEF/ORB 追求速度（適合即時追蹤、嵌入式）。

演算法步驟（BRIEF 迷你版）#

用 Harris 取角點（上一節）。
在每個角點周圍取 9×9 區域，先輕微平滑（抗雜訊）。
用固定種子生成 256 對取樣位置 (aᵢ, bᵢ)。
每對比較亮度得 1 位元，串成 256-bit 描述子。
兩圖間以 Hamming 距離最近鄰 + 門檻匹配。

Python 程式碼範例#

import numpy as np

rng = np.random.default_rng(13)
def patch(img, cx, cy, r=4):
    return img[cy-r:cy+r+1, cx-r:cx+r+1].astype(np.float64)

def brief(img, pts, n=256, r=4, seed=0):
    prng = np.random.default_rng(seed)
    P = prng.integers(-r, r+1, size=(n, 2, 2))     # n 對 (a, b) 偏移
    desc = []
    for cx, cy in pts:
        p = patch(img, cx, cy, r)
        pa = p[P[:,0,0]+r, P[:,0,1]+r]
        pb = p[P[:,1,0]+r, P[:,1,1]+r]
        desc.append((pa < pb).astype(np.uint8))
    return np.array(desc), P

def hamming(a, b):
    return int((a != b).sum())

# 影像一：一個方框角點；影像二：同一方框平移 (10, 5) 且亮度 +30
img1 = np.zeros((40, 40), np.uint8); img1[8:24, 8:24] = 100
img2 = np.zeros((50, 50), np.uint8); img2[13:29, 18:34] = 130

def corners(img):
    # 極簡版：直接取方框四角（省略 9.1 的完整 Harris）
    b = img > 50
    ys, xs = np.where(b)
    y0, y1, x0, x1 = ys.min(), ys.max(), xs.min(), xs.max()
    return [(x0+4, y0+4), (x1-4, y0+4), (x0+4, y1-4), (x1-4, y1-4)]

c1, c2 = corners(img1), corners(img2)
d1, _ = brief(img1, c1)
d2, _ = brief(img2, c2)

print("四對角點的 Hamming 距離（平移+亮度變化後）:")
for i in range(4):
    print(f"  {c1[i]} ↔ {c2[i]}: {hamming(d1[i], d2[i])}/256")

# 匹配：最近鄰
matches = []
for i in range(len(d1)):
    dists = [hamming(d1[i], d2[j]) for j in range(len(d2))]
    j = int(np.argmin(dists))
    if min(dists) < 60:
        matches.append((c1[i], c2[j], min(dists)))
print("匹配數:", len(matches), "/ 4")
# 檢查位移是否一致
offs = [(b[0]-a[0], b[1]-a[1]) for a, b, _ in matches]
print("匹配的位移向量:", offs, "（應皆 ≈ (10, 5)）")

執行後：同一角點平移且亮度 +30 後，BRIEF 描述子的 Hamming 距離仍然很小（大部分比較位元的結果不變，因為亮度平移不改變相對大小關係），四個角點全部被正確匹配，且位移向量一致——這個一致性正是後續用單應矩陣驗證幾何的依據。

複雜度分析#

SIFT：尺度空間構建是多次高斯模糊 O(s·N·k)（s 層）；極值搜尋 O(N)；描述子每關鍵點 O(16²·8)。整體 O(N) 每影像（對固定層數與關鍵點密度），但常數極大——SIFT 原始實作每張百萬像素圖數百毫秒。匹配 n×m 描述子暴力最近鄰 O(n·m·128)，KD-tree/BBF 或詞袋 (BoW) 可大幅加速。BRIEF：描述每關鍵點 O(256) 次比較，匹配 O(n·m) 次 popcount——快約百倍，代價是不變性較弱。空間：SIFT 描述子 512 bytes/點，BRIEF 32 bytes/點。選型原則：離線、寬基線、要求召回率 → SIFT；即時、小資源 → ORB/BRIEF。

練習#

把影像二的方框旋轉 20° 再匹配，觀察 BRIEF 匹配失敗率上升；解釋原因並說明 ORB 的方向歸一如何修復它。
實作 ratio test：對每個描述子計算最近與次近 Hamming 距離之比，統計不同門檻 (0.7/0.8/0.9) 下的正確匹配率與錯誤匹配數。
SIFT 用 DoG 近似 LoG。對半徑 6 的圓形斑點，分別用 5.3 節的 LoG 與「σ 與 σ·1.6 的兩次高斯相減」計算中心響應，比較兩者的峰值尺度是否一致。