SIFT 演算法深度解析：從尺度空間極值到特徵描述子完整流程

1. 綜述

SIFT (Scale-Invariant Feature Transform) 產生的特徵對旋轉、尺度具不變性，對光照、視角變化具部分不變性。主要四階段：

1. 尺度空間極值檢測：以高斯差分 (DoG) 尋找潛在關鍵點。
2. 關鍵點精確定位：泰勒展開插值 + 門檻過濾低對比度/邊緣響應點。
3. 方向分配：依局部梯度直方圖決定主/輔方向，賦予旋轉不變性。
4. 特徵描述子生成：鄰域梯度統計 → 128 維向量 → 歸一化 + 截斷 → 強健描述子。

2. 詳細流程與數學基礎

2.1 尺度空間表示與高斯金字塔

尺度空間 L(x,y,σ) = G(x,y,σ) * I(x,y)。DoG 近似 LoG (Laplacian of Gaussian)：

D(x,y,σ) = L(x,y,kσ) - L(x,y,σ) ≈ (k-1) σ² ∇²G

• 金字塔 O 組，每組 S+3 層（S 個間隔 + 上下各 1 層供極值搜尋）。
• 下一組首層由上組倒數第三層隔點取樣得來，減少卷積運算。
• 預設參數：σ₀=1.6, S=3, O=log₂(min(W,H))-2。輸入影像先雙線性放大 2 倍（等效 σ=1.0），再以 σ₀=1.6 建立第 0 組第 0 層。

2.2 極值檢測（離散空間）

每個候選點與同層 8 鄰域 + 上下層各 9 點共 26 點比較，確為局部極大/極小才保留。搜尋範圍：各組第 1 ~ S 層。

2.3 亞像素插值精確定位

泰勒展開至二階：

X̂ = -H⁻¹ ∇D （偏移向量）

D(X̂) = D(0) + ½ ∇Dᵀ X̂ （插值極值）

• 若任一維度偏移 |X̂| > 0.5 → 移動中心點重新插值，直到收斂或超過迭代上限/邊界則捨棄。
• 若 |D(X̂)| < 0.03（假設灰度 0~1）→ 對比度過低，捨棄。

2.4 邊緣響應抑制（Hessian 主曲率比）

Hessian 矩陣 H = [[Dxx, Dxy], [Dxy, Dyy]]。特徵值比率 r = λ_max/λ_min。
檢查 Tr(H)² / Det(H) < (r+1)²/r。Lowe 建議 r=10 → 門檻 121/10=12.1。超過者為邊緣點，捨棄。

2.5 關鍵點尺度計算

σ_total = σ₀ × 2^{o + (s + σ_sub)/S}。若輸入影像曾放大 2 倍，最終尺度除以 2。

2.6 方向分配

• 在關鍵點尺度對應的高斯圖像上，半徑 3 × 1.5 × σ 範圍內計算梯度幅值/角度。
• 36 個 bin (每 10°) 直方圖，高斯加權（σ = 1.5×關鍵點尺度）。
• 最高峰為主方向；達主峰 80% 以上的次峰產生輔方向（複製關鍵點賦予不同方向）。
• 直方圖抛物線插值求精確角度。

2.7 特徵描述子 (128 維)

• 以關鍵點為中心，4×4 子區域，每子區域 4×4 像素（間距 m×σ, m=3）。
• 座標旋轉對齊主方向，每子區域計算 8 方向梯度直方圖 → 4×4×8 = 128 維。
• 高斯加權（σ = 0.5 × 4 × 3 × σ = 6σ）。
• 歸一化 → 截斷大於 0.2 的值為 0.2 → 再歸一化（提升鑑別度）。

3. 待釐清疑問

1. 鄰域半徑計算為何使用去除組索引 o 後的尺度？
2. 對比度門檻 0.03 在代碼中實為 0.03/S，除以間隔數 S 的理論依據？

4. 參考文獻

1. D. Lowe, "Distinctive Image Features from Scale-Invariant Keypoints", 2004
2. T. Lindeberg, "Scale-space theory: A basic tool for analysing structures at different scales"
3. 王永明、王貴錦，《圖像局部不變性特徵與描述》，國防工業出版社
4. C. Harris & M. Stephens, "A combined corner and edge detector", 1988

本文整理自「UnderTheHood」博客，原文出處：https://underthehood.blog.51cto.com/2531780/658350 | 基於 OpenCV 2.3 / Rob Hess 開源實作