[OpenCV筆記] 用於角點偵測的 FAST 演算法

 

1.FAST 演算法簡介

FAST (Features from Accelerated Segment Test) 演算法是由Edward Rosten 和 Tom Drummond 在 2006年的這天論文 "Machine learning for high-speed corner detection" （後來在2010年重新修訂）提出的角點偵測演算法。 

為什麼要提出 FAST 演算法呢？因為研究人員發現，雖然許多特徵偵測的演算法有非常棒的效果，但是運用在即時應用的情境中，卻不夠快，無法滿足 "即時" 的需求。

移動式機器人的SLAM應用就是代表性的例子。SLAM(Simultaneous Localization and Mapping) ，即同時定位與建圖。機器人在未知的環境中必須即時偵測環境中的特徵點，才能進一步了解自身的定位並建立地圖，透過自主導航才能進行延伸的應用。

雖然FAST比其他現有的角點檢測演算法快，但取決於閾值，它對抵抗高階雜訊的效果有限。

2.原理

2.1.使用 FAST 進行特徵偵測

Step1.在圖像中選擇一個像素 p ，將其強度設為 Ip。

Step2.選擇合適的閾值 t。

Step3.將像素p周圍的 16 個像素（圓圈上的 16 個像素）納入評估範圍。 （請參見下圖）

圖片來源：OpenCV Python：FAST Algorithm for Corner Detection

Step4.如果圓圈上的 16 個像素中存在一組 n 個連續像素（n 被設為 12），它們都比 Ip+t 亮，或都比 Ip-t 暗，那麼像素 p 是一個角點。（在上圖中顯示為白色虛線）。 

Step5.作者建議進行高速測試以排除大量非拐角。此測試僅檢查 1、9、5 和 13 處的四個像素（首先測試 1 和 9，檢視是否太亮或太暗。如果是，則接著檢查 5 和 13）。如果 p 是一個角點，那麼其中至少3個點必須比 Ip+t 亮或比 Ip-t 暗。通過上述測試的即可作為候選點。這種檢測器本身就表現出高性能，但有幾個弱點：

• 對於 n < 12，它不會拒絕盡可能多的候選者。換言之，候選點可能會很多。
• 像素的選擇不是最佳的，因為它的效率取決於問題的排序和角點外觀的分佈。
• 高速測試的結果被丟棄。
• 多個特徵被檢測到彼此相鄰。

前 3 個弱點可通過機器學習方法解決。最後一個弱點可使用非最大值抑制來解決的。

2.1.1.使用機器學習進行特徵偵測

Step1. 選擇一組圖像進行訓練（最好來自目標應用領域）

Step2. 在每個圖像中運行 FAST 算法以查找特徵點。

Step3. 對於每個特徵點，將其周圍的 16 個像素存儲為一個向量。對所有圖像都使用同樣的方法來得到特徵向量P。

Step4. 這 16 個像素中的每個像素（比如 x）可以具有以下三種狀態之一（如下圖）：

圖片來源：OpenCV Python：FAST Algorithm for Corner Detection

Step5. 根據上述3種狀態，特徵向量 P 被分為 3 個子集，Pd、Ps、Pb。

Step6. 定義一個新的布林(boolean)變量 Kp，如果 p 是角點則為真(True)，否則為假(False)。

Step7. 藉由 ID3 算法（決策樹分類器）使用變量 Kp 查詢每個子集，以獲取有關真實類別的知識。以 Kp 的熵進行量測，它選擇產生最多關於候選像素是否是角點的訊息的 x。

Step8. 遞歸（以同樣方法重複）應用於所有子集，直到其熵為零。

Step9. 經此創建的決策樹可用於其他圖像中，進行快速檢測。

2.1.2. Non-maximal Suppression（非極大值抑制）

多個特徵被檢測到彼此相鄰，可通過使用非極大值抑制來解決的。

Step1. 使用得分函數 V，對所有檢測到的特徵點進行計算。 V 是 p 和 16 個周圍像素值之間的絕對差之和。

Step2. 考慮兩個相鄰的關鍵點併計算它們的 V 值。

Step3. 丟棄 V 值較低的那個。

3.範例效果與範例程式碼

3.1. 範例效果

當閾值越大，所偵測到的角點會越少。

而關於非極大值抑制，"fast_true"表示使用非極大值抑制，偵測到的角點會越少。"fast_false"表示未使用非極大值抑制，多個特徵被檢測到彼此相鄰，因此偵測到的角點會較多。

閾值為10

圖片來源：Greatway9999

執行程式後的參數輸出結果：

Threshold: 10

nonmaxSuppression:True

neighborhood: 2

Total Keypoints with nonmaxSuppression: 1474

Total Keypoints without nonmaxSuppression: 5623

閾值為30

圖片來源：Greatway9999

3.2. 範例程式碼

import numpy as np

import cv2 

from matplotlib import pyplot as plt

img = cv2.imread('Lenna.jpg',0) 

# 使用預設值將FAST物件初始化

fast = cv2.FastFeatureDetector_create()

fast.setThreshold(10) #設定閾值。預設值為10，值越大，偵測到的角點會越少。

# 尋找並繪製關鍵點（角點）

kp = fast.detect(img,None)

img2 = cv2.drawKeypoints(img, kp, None, color=(255,0,0)) #cv.drawKeypoints的參數內容依序為:原圖、角點、輸出圖像、繪製角點之顏色。

# 顯示所有的預測參數

print( "Threshold: {}".format(fast.getThreshold()) )

print( "nonmaxSuppression:{}".format(fast.getNonmaxSuppression()) )

print( "neighborhood: {}".format(fast.getType()) )

print( "Total Keypoints with nonmaxSuppression: {}".format(len(kp)) )

#cv.imwrite('fast_true.png', img2)

cv2.imshow('fast_true',img2)

# 關閉 非最大值抑制

fast.setNonmaxSuppression(0)

kp = fast.detect(img, None)

print( "Total Keypoints without nonmaxSuppression: {}".format(len(kp)) )

img3 = cv.drawKeypoints(img, kp, None, color=(255,0,0))

#cv.imwrite('fast_false.png', img3)

cv2.imshow('fast_false',img3)

cv2.waitKey()

cv2.destroyAllWindows()

---

參考資料：

• OpenCV Python：FAST Algorithm for Corner Detection