對速度的渴求：即時特徵
上一篇我們建立了 SIFT 描述子：每個關鍵點都是一個 128 維的浮點數向量，由帶方向的梯度直方圖算出。它非常穩健 — 但代價很高。每個關鍵點都需要高斯模糊的影像金字塔、到處都要算梯度大小與方向，最後得到一個 128 維浮點向量。比對兩張影像時，要用歐氏（L2）距離比較成千上萬個這種向量，每次比較都要碰 128 個浮點數。在筆電上處理單張相片沒問題，但若是手機、無人機或機器人每秒要做 30 次以上，就是一場災難。
即時視覺 — 視覺 SLAM（機器人一邊建立房間地圖、一邊追蹤自身姿態）、擴增實境（把虛擬物件固定在移動的相機畫面上）、以及行動裝置 App — 根本負擔不起 SIFT 那種大量浮點的計算與比對。本篇發展兩個關鍵想法來解決它。想法一：用便宜的方框濾波器與積分影像來近似昂貴的高斯／導數機器 — 這給了我們 SURF 描述子。想法二：乾脆丟掉浮點向量，把關鍵點描述成一串是非測試的二值字串，用漢明距離在幾個 CPU 指令內完成比較 — 這給了我們 BRIEF、ORB 描述子 與 LBP。
- 積分影像 — 一個預先計算的技巧，讓任意矩形的求和只需四次查表（SURF 與人臉偵測背後的引擎）。
- SURF — 用方框濾波器加速 SIFT 的偵測器與描述子；仍是浮點向量（64 維），所以仍用 L2 距離。優化的是計算速度。
- BRIEF — 第一個二值描述子：一串強度比較的位元。記憶體極小、比對飛快，但不具旋轉不變性。
- ORB — 修補 BRIEF：加上快速角點偵測與方向，使其能抵抗旋轉，且完全免專利。即時應用的主力。
- LBP — 另一種風格的二值碼，針對紋理與人臉，以每像素碼的直方圖來總結。
積分影像：O(1) 的矩形求和
在理解 SURF 之前，我們需要一個美麗且可重複使用的技巧：積分影像（又稱為累積區域表，summed-area table）。它解決的問題是：許多演算法會反覆問「這個矩形內的像素值總和是多少？」用最直接的方法每個像素要加一次，所以大方框很慢，而且每個方框都要重付一次。積分影像讓你能在常數時間內 — 四次查表 — 回答任何矩形的總和，無論矩形多大。同樣的技巧也出現在著名的 Viola–Jones 人臉偵測器裡，因此值得真正搞懂。
每個積分影像的格子，儲存它左上方（含自身）所有像素的總和。
這樣讀它：II(x,y) 是積分影像在第 x 欄、第 y 列的值。右邊把原始影像 I(x',y') 對所有「欄 x' ≤ x 且 列 y' ≤ y」的像素求和 — 也就是從左上角一路到 (x,y) 的整個矩形。你不會每次從頭算這個總和；只要用遞迴式 II(x,y) = I(x,y) + II(x−1,y) + II(x,y−1) − II(x−1,y−1) 一次掃描就能建好整張表（最後一項抵消被重複計算的重疊區）。看一個具體的 4×4 影像（由上到下）：第1列 = [3 1 4 1]、第2列 = [5 9 2 6]、第3列 = [5 3 5 8]、第4列 = [9 7 9 3]。跑過遞迴式後得到積分影像：第1列 = [3 4 8 9]、第2列 = [8 18 24 31]、第3列 = [13 26 37 52]、第4列 = [22 42 62 80]。檢查一下：右下角的 80 正好等於全部 16 個像素的總和（9+22+21+28 = 80）。
左上角 (x0,y0)、右下角 (x1,y1) 的矩形總和 — 四次查表，任意大小。
這是排容原理（inclusion–exclusion）。II(x1,y1) 是從原點一路到矩形遠端角落的大區塊 — 但它包含了矩形上方的一條帶與左方的一條帶，那是我們不要的。減去 II(x0−1,y1)（矩形左邊的全部）與 II(x1,y0−1)（矩形上方的全部）。這兩條帶在左上區域重疊，剛剛被減了兩次，所以要把 II(x0−1,y0−1) 加回一次。讓我們還原例子中內部的 2×2 區塊（第 2–3 列、第 2–3 欄）。暴力法：像素 9+2+3+5 = 19。用公式，取 (x0,y0)=(2,2) 與 (x1,y1)=(3,3)：II(3,3) − II(1,3) − II(3,1) + II(1,1) = 37 − 13 − 8 + 3 = 19。完全相同 — 而且我們只碰了恰好四個數字，而非整個矩形。這個 O(1) 的矩形求和，正是讓 SURF 描述子 變快的關鍵，接下來就會看到。
一個 4×4 像素值方格疊上它的積分影像，四個角落格子被標亮，並用箭頭顯示產生矩形總和的加減模式。
SURF：加速版的 SIFT
SURF 描述子（Speeded-Up Robust Features，加速穩健特徵）是 SIFT 的快表親：整體配方相同 — 跨尺度偵測類似斑點的關鍵點，再用以梯度為基礎的向量描述每一個 — 但每個昂貴步驟都換成了 積分影像 能在 O(1) 內算出的東西。成果是保留 SIFT 大部分的穩健性，卻只花零頭的計算量。訣竅是不再計算精確的高斯導數響應，而改用粗糙的方框濾波器來近似它們，而方框濾波器不過就是幾個矩形求和。
回想第 2 篇：斑點是一塊大致呈圓形的亮／暗區域，會在二階導數響應（海森矩陣）於正確尺度上達到峰值之處被找到。SURF 把關鍵點偵測為近似海森行列式的極大值。SIFT 為了達到更大尺度，建了整座高斯影像金字塔（反覆模糊並降採樣）。SURF 則保持影像固定，改而放大濾波器：因為方框濾波器是用積分影像查表計算的，一個 9×9 濾波器與一個 27×27 濾波器花費完全相同 — 每個方框四次查表。這直接連回 斑點偵測：同樣的想法（高斯海森斑點），但機器大幅變便宜。
SURF 的斑點響應：方框濾波器近似海森矩陣的行列式。
海森矩陣是二階導數構成的矩陣；它的行列式在影像同時於兩個方向強烈彎曲之處會很大 — 正是斑點。這裡 D_xx 是水平方向二階導數的方框濾波器近似、D_yy 是垂直方向、D_xy 是混合（對角）二階導數 — 每個都用一小組矩形求和透過積分影像算出。權重 w ≈ 0.9 修正「用塊狀方框取代平滑高斯導數」所造成的誤差，使近似行列式仍能貼近真值。當 det(H_approx) 在空間與尺度上都是局部極大值時，你就得到一個 SURF 關鍵點。關鍵的收穫是：因為 D_xx、D_yy、D_xy 只是可調大小的方框濾波器，要達到更大尺度只需把方框放大 — 而不必重建模糊的影像金字塔。光是這一個替換，就佔了 SURF 加速的大部分。
至於描述子，SURF 仿照 SIFT，但維持方框濾波器的便宜。它在每個關鍵點周圍鋪一塊方形區域（旋轉到關鍵點的主方向），再切成 4×4 的 16 個子區域格子。在每個子區域裡取樣 Haar 小波響應 — 同樣只是量測 x 與 y 方向強度變化的方框濾波器，用積分影像查表算出 — 並累積四個數：Σdx、Σdy、Σ|dx|、Σ|dy|。這就是 16 個子區域 × 4 個值 = 一個精簡的 64 維向量（SIFT 128 維的一半）。它仍是浮點數，所以比對用 L2 距離，但計算與比較的速度大約是 SIFT 的兩倍。
影像上的熱力圖，類似斑點的區域亮成亮點，標示近似海森行列式的局部極大值。
BRIEF：用是非測試來描述
SURF 把浮點描述子變得更小更快，但它仍是浮點向量。BRIEF（Binary Robust Independent Elementary Features）提出一個更大膽的問題：如果描述子只是一串是非答案會怎樣？在關鍵點周圍，事先固定一組像素配對的樣式。對每一對問一個簡單問題 —「像素 A 是否比像素 B 暗？」— 並記下一個位元：是記 1，否記 0。把這些位元疊成一串字串。用 256 對就得到一個 256 位元的描述子，每個關鍵點只佔 32 位元組。對比 SIFT 的 128 個浮點數（512 位元組）：記憶體直接砍 16 倍，這還沒談到速度。
每個像素配對一個二值測試；描述子 d 就是這 n 個位元組成的字串。
拆解它：p 是關鍵點周圍的影像區塊；a 與 b 是其中兩個固定的取樣位置（只選一次，例如用隨機高斯樣式產生，並對每個關鍵點都重複使用）。I(a) 與 I(b) 是這兩點的（平滑後）強度。測試 τ 在 a 比 b 暗時輸出 1，否則輸出 0。完整描述子 d 是這 n 個測試依序排成的元組，例如 n = 256，所以 d 是一個 256 位元的字串。這個樣式對所有關鍵點都相同，正是這點讓兩個描述子能逐位元直接比較。（注意：BRIEF 會先模糊區塊，使單一像素的雜訊不會翻動某個位元。）
漢明距離：將兩個位元字串做 XOR，再數出 1 的個數。
要比較兩個二值描述子 d1 與 d2，使用漢明距離：兩者位元不同的位置數量。符號 ⊕ 是逐位元 XOR，會在兩字串不一致的位置恰好產生 1；popcount（位元計數）再數出這些 1。神奇之處在硬體：對 256 位元做 XOR 只是少數幾個 64 位元機器字，而大多數 CPU 都有單一的 popcount 指令，因此整個描述子比較只要幾個指令。對比之下，對 128 個浮點數做 L2 距離 — 128 次減法、128 次乘法、再加總，全是浮點運算。二值比對常快上一個數量級，且用的記憶體頻寬少很多，這正是它能解鎖即時影片的原因。
一個方形區塊方格，數條線段連接成對的取樣點，每條標示為一個二值強度比較測試。
ORB：定向 FAST 加上旋轉 BRIEF
BRIEF 又小又快，但有個明顯缺陷：相機一傾斜，固定的像素配對樣式就指向不同的內容，位元因而被打亂 — 它不具旋轉不變性。ORB 描述子（Oriented FAST and Rotated BRIEF）正是修補這點，且額外好處是完全免專利（不像 SIFT 與 SURF 過去那樣）。ORB 已成為即時視覺中實用又免費的主力。它把一個快速角點偵測器，與一個可導向版本的 BRIEF 描述子 結合起來。
偵測器是 FAST（Features from Accelerated Segment Test，加速分段測試特徵）。對一個候選像素，看它周圍小圓（半徑 3）上那一圈 16 個像素。若其中有一段連續的弧 — 例如 16 個裡有 9 個 — 全都比中心加上一個門檻還亮（或全都比中心減門檻還暗），它就是角點。一個巧妙的捷徑是先只測像素 1、5、9、13，立刻刷掉大多數平坦區塊 — 這就是 FAST 之所以快的原因。光靠 FAST 會給出很多角點卻沒有品質排序，所以 ORB 用 Harris 角點偵測器 的響應為每個評分，留下最強的。為了處理尺度，它在影像金字塔上跑 FAST（就是第 2 篇那個由粗到細的想法）。
現在來看旋轉的修補。為了給每個關鍵點一個方向，ORB 使用強度形心（intensity centroid）：把區塊裡的亮像素想成有質量，找出它們的平衡點，從區塊中心指向那個平衡點的方向就是關鍵點的角度。接著 ORB 在執行測試前，把整個 BRIEF 取樣樣式旋轉那個角度，於是無論相機如何旋轉，同一個實際結構都會被以相同方式取樣。
以強度形心、由影像矩求得區塊方向。
這裡 m_pq 是區塊的影像矩：對所有區塊像素求 x^p · y^q · I(x,y) 的總和，其中 x、y 是像素座標（從區塊中心量起），I(x,y) 是強度。三個矩最重要。m00 = Σ I 是總強度（總「質量」）。m10 = Σ x·I 與 m01 = Σ y·I 是以強度加權的 x、y 座標總和。形心 C 把它們各除以 m00，得到以亮度加權的平均位置 — 也就是區塊的「質心」。方向 θ = atan2(m01, m10) 就是「從區塊中心指向該形心」這個向量的角度（atan2 在四個象限都會回傳正確角度）。把每個 BRIEF 配對依 θ 導向 — 將每個取樣點繞中心旋轉 θ — 位元字串就具備旋轉不變性。ORB 還使用 rBRIEF：不用隨機配對，而是從訓練資料學出一組 256 個高變異（資訊量大）且低相關（不冗餘）的測試，使描述子更有鑑別力。正是這個組合驅動了像 ORB-SLAM 這樣的系統，能在一般硬體上即時追蹤相機在世界中的移動。
局部二值模式：一個位元組裝下紋理
局部二值模式（LBP）像 BRIEF 一樣是二值的，但目標不同。BRIEF 與 ORB 描述的是稀疏關鍵點，用來跨視角比對。LBP 則描述紋理 — 表面的細微結構（布料、樹皮、皮膚）— 並以人臉辨識聞名。想法是：在每個像素，把它周圍一圈的鄰居與它自己比較，把這些比較變成一個二進位數（每像素一個碼），再用這些碼的直方圖來總結整個區域。描述子不是碼本身，而是每個碼出現的頻率 — 這就是它捕捉紋理統計「感覺」而非單一點的原因。
單一像素的 LBP 碼：把每個鄰居與中心做門檻比較，再把位元讀成一個二進位數。
解碼它：g_c 是中心像素的強度。g_p（p = 0…P−1）是繞它、在半徑 R 的圓上取樣的 P 個鄰居 — 例如 P = 8 個鄰居、半徑 R = 1 就是 3×3 的那一圈。階梯函數 s(z) 在鄰居大於等於中心時輸出 1，否則 0。於是每個鄰居貢獻一個位元，我們把第 p 個位元乘以 2^p 再加總，把這一圈比較變成單一整數碼（P = 8 時為 0–255 — 恰好一個位元組）。注意它比較的是相對亮度，所以對整個區塊加一個常數（光照變化）不會改變碼：LBP 對單調的強度位移具有不變性，這對真實世界的光照來說極為寶貴。
# Worked 3x3 LBP example, P = 8, R = 1. # Patch (center g_c = 50), neighbors read clockwise from top-left: # 80 99 11 # 84 50 20 # 12 33 70 g_c = 50 # order p = 0..7 : TL, T, TR, R, BR, B, BL, L neighbors = [80, 99, 11, 20, 70, 33, 12, 84] bits = [1 if g >= g_c else 0 for g in neighbors] # -> [1,1,0,0,1,0,0,1] code = sum(b * (2 ** p) for p, b in enumerate(bits)) print(code) # 1 + 2 + 16 + 128 = 147 # As a byte (b7..b0) = 1001 0011 = 147
依照範例，鄰居 ≥ 50 給出位元（p0…p7）= 1,1,0,0,1,0,0,1，加權總和 2^0 + 2^1 + 2^4 + 2^7 = 1 + 2 + 16 + 128 = 147 — 用一個位元組描述該像素周圍的局部微紋理。接著把這個操作掃過整個區域，建一個有 256 個格子的直方圖，計算有多少像素產生了各個碼：這個直方圖就是 LBP 紋理描述子（而一張臉則是把臉部格網各小格的直方圖串接起來來描述）。你會遇到兩個改良：uniform LBP（均勻 LBP）只保留繞圈時 0↔1 轉換至多兩次的碼（這些捕捉了邊緣、斑點與角點，涵蓋大多數真實樣式），其餘全併到一個格子，把 256 格縮成 59 格；rotation-invariant LBP（旋轉不變 LBP）把每個碼旋轉到它的最小值，使紋理旋轉時描述子不變。
一個 3×3 像素方格，中心被標亮、周圍每格標示 0 或 1，並顯示得到的 8 位元碼。
選擇描述子：一張實用地圖
你現在有四個快速替代方案加上 SIFT 基準的工具箱。正確的選擇取決於幾個面向：各自計算多快、比對多快、佔多少記憶體、有多穩健／準確，以及 — 至關重要的 — 它需要哪一種距離度量。浮點描述子活在歐氏空間、用 L2 距離；二值描述子活在位元空間、用漢明距離。選錯度量，比對就會無聲地失敗。
Descriptor | Type | Compute | Matching | Memory | Distance | Rotation | Best for -----------|--------|---------|--------------|--------------|----------|----------|------------------------ SIFT | float | slow | slow | 128 floats | L2 | yes | max accuracy, offline SURF | float | medium | medium | 64 floats | L2 | yes | speed/accuracy balance BRIEF | binary | fast | very fast | 32 bytes | Hamming | NO | upright, controlled view ORB | binary | fast | very fast | 32 bytes | Hamming | yes | real-time, mobile, SLAM LBP | binary | fast | histogram | small hist. | chi-sq. | variant | texture, face recognition
具體建議：當準確度壓倒一切且你離線計算（固定資料集的影像拼接、3D 重建、基準測試）時，選 SIFT 描述子。任何即時、行動或嵌入式的場景，選 ORB 描述子 — 它是 SLAM 與 AR 的預設，因為又快、具旋轉不變性、且免專利。當你想要比 ORB 更準、又比 SIFT 更快，且不在意授權時，用 SURF 描述子 作為折衷。只有在你能保證直立、視角大致固定（例如固定的掃描器）且想要絕對最低成本時，才用純 BRIEF 描述子。而當任務是紋理分類或人臉辨識、而非點對點比對時，用 局部二值模式。
我們現在有了偵測器（角點、斑點）與描述子（SIFT、SURF、BRIEF、ORB、LBP）— 把影像轉成一組可比較指紋的完整詞彙。但描述子要等到你真正跨影像比對它、並剔除難免出現的壞比對後，才有用。那正是下一篇的主題：比對策略（暴力法與近似最近鄰）、比值測試（ratio test）、用 RANSAC 找出幾何一致的比對集合，最後把多張影像拼接成全景圖。你在這裡所做的每個選擇 — 浮點對二值、L2 對漢明 — 都直接影響那個比對該怎麼進行。