OpenCV Tutorials - Feature Detection and Description

在 feature detection 的部分，FAST (Features from Accelerated Segment Test) 可以說是目前速度最快的，以下簡單說明該演算法。

之前的幾個 feature detector 其實都算不錯，唯一的缺點是不夠快，FAST 在 2006 年被提出，於 2010 年改版。

FAST 的演算法，其實並不複雜，也就是不複雜，所以快：

要判斷在影像中的某個像素 P 是否為 feature，假定其灰階值為 I_p
選取適當的 threshold 值 - t
取該像素周圍的 16 個像素值來作比較，如下圖。
如果該像素 P 為 corner，則在這 16 個像素中，必有連續的 n 個像素其灰階值都大於 (I_p + t) 或都小於 (I_p - t) ，在論文中 n 為 12
High-speed Test：用來加速剔除非 corner 的像素。
這個方法會先檢查位於 1, 9, 5, 13 的像素值 (先是 1, 9，如果都大於或都小於，才會繼續檢查位於 5, 13)，如果 P 是 corner，則這四個像素中，至少會有三個的像素值為都大於 (I_p + t) 或都小於 (I_p - t) ，否則 P 不為 corner，判斷可能是 corner 之後，才會對周圍的 16 個像素作完整的判斷。
雖然 High-speed Test 提高了效率，不過還是有一些缺點：
1, 如果 n < 12，則效率會變差。
2, 關於所拿來測試的 4 個像素的位置選擇，並沒有作最佳化。
3, High-speed Test 的結果，在判斷完是否可能為 corner 之後，即沒再作利用。
4, 對同一個區域，可能會偵測到多個重疊的 feature。