HMOO 讀書筆記: 整理常見的 image feature detectors 與 feature descriptors

在選擇 feature detector 與 feature descriptor 時，我們重視的是其不變性。通常我們追求的不變性有旋轉（rotation invariant）、放大縮小（scale invariant），以及 affine 變換（affine invariant）[1]。本文將會整理常見的技巧以及 paper 中的方法，將分成 feature detector 與 feature descriptor 討論。

Feature Detectors

Rotation invariant

首先要提到的就是 Harris Corner Detector [2]（前文有相關資料）。Harris Corner Detector 是在一個 local window 內統計 \(I_x\) 與 \(I_y\) 的值： \[ M = \sum_{(x,y)\in W} \begin{bmatrix} I_x^2 & I_xI_y\\ I_xI_y & I_y^2 \end{bmatrix} \]概念上來說，若 M 的兩個特徵值都夠大則其為一個特徵點。實務上計算特徵值還需要分解比較麻煩，因此用此式子來判定其是否為一個角的特徵點： \[ R(M)=det(M)-k\ Trace(M)^2 \]而 k 通常設定在 0.04 至 0.06 之間。另一種做法是用 \(\frac{det(M)}{Trace(M)}\) 來近似小的特徵值進而來判定，可以參考資料 [2]。

另一種方式是用 Hessian 矩陣的特徵值來判定： \[ H=\begin{bmatrix} I_{xx} & I_{xy}\\ I_{xy} & I_{yy} \end{bmatrix} \]這個方法用的矩陣 H 與前面用的 M 應該是等價的，我們在前文有提過這兩個矩陣的近似。這兩種方法都只能達成 rotation invariant。

（註：SIFT [3] 用了 \(\frac{Trace(H)^2}{Det(H)}\) 來篩選特徵點。）

Scale invariant

Laplacian 或 Laplacian of Gaussian 搭配 local minimum 可用來解決 scale invariant 的問題 [4]。SIFT [3] 用的是 difference of Gaussian 來近似 Laplacian of Gaussian 的方法，而 SURF [5] 是用 Hessian of Laplacian 的行列式來找特徵點。這些方法都同時是 scale 及 rotation invariant。

Affine invariant

MSER [6, 7] 除了以上兩種不變性以外，也是 affine invariant。MSER 為 maximally stable extremal regions，簡單來說就是一小塊區域內所有像素都比其邊緣亮或暗。實務上會利用 image threshold、connected components 來實作：

生成不同的 threshold image。
連接 connected components。
針對不同 threshold image 中的同一個 connected component，計算 \(R_{x-1} - R_{x+1}\) 與 \(R_x\) 的比值，比值最小的會滿足 maximal stable 的條件。

在 feature detector 時，解決 scale invariant 的方法為在不同的解析度上計算 MSER [7]，並且利用橢圓形來近似此 MSER 進而達成 affine invariant。

其他的 detectors

以下列出來的 detectors 通常是為了能夠更快地找出特徵點，但代價就是不一定滿足所有的不變性條件。

FAST [8]：每個像素與其附近的圓上的像素直接比較像素值，用一些規則來決定是否為特徵點。若搭配 image pyramid 則可以 scale invariant。
ORB [9]：利用 FAST 加上計算了區域內像素質的質心，因此可以達成 rotation invariant。
BRISK [10]、FREAK [11]：也是利用 FAST 來找特徵點，之後會簡述其 descriptor。

Feature Descriptors

Feature descriptor 為描述特徵點附近局部特徵的向量，作法可以分為浮點數表示法或二進位表示法。參考資料 [12] 有一些實驗與分析。

Intensity invariant

BRIEF [13] 直接用特徵點與其附近的像素比較像素值，若大於為 1，否則為 0。這個方法只能達成 intensity invariant。

Rotation invariant

ORB [9] 改進了 BRIEF 的作法，利用前面所述的質心來得到此特徵點的方向，再計算 BRIEF 特徵向量。這樣便能達成 rotation invariant。

Scale invariant

BRISK [10] 與 FREAK [11] 用的方法非常類似，特徵向量也都是二進位表示法。向量本身與 BRIEF 相同，不同的點在於特徵點與哪些附近的像素做比較：兩個方法都是用 Gaussian kernel 找 sample，FREAK 採用類似視網膜的結構來採樣，與 BRISK 相比為每個 Gaussian kernel 之間會存在重複的區域。

SIFT 的特徵向量為統計附近的區域中梯度的直方圖（分成八個方向），而 SURF 只用了 \(\sum d_x\)、\(\sum d_y\)、\(\sum |d_x|\)、\(\sum |d_y|\)。兩者都是統計附近 4x4 的 sub-region（依照特徵的 scale 決定每一個 sub-region 的大小），因此 SIFT 特徵向量的維度為 128，而 SURF 的特徵向量維度為 64。