目標

在本章中，

• 我們將瞭解FAST算法的基礎知識。
• 我們將使用OpenCV功能對FAST算法進行探索。

理論

我們看到了幾個特徵檢測器，其中很多真的很棒。但是，從實時應用程序的角度來看，它們不夠快。最好的例子是計算資源有限的SLAM（同時定位和製圖）移動機器人

作為對此的解決方案，Edward Rosten和Tom Drummond在2006年的論文“用於高速拐角檢測的機器學習”中提出了FAST（加速分段測試的特徵）算法（後來在2010年對其進行了修訂）。該算法的基本內容如下。有關更多詳細信息，請參閱原始論文（所有圖像均取自原始論文）。

使用FAST進行特徵檢測

1. 選擇圖像中是否要識別為興趣點的像素p，使其強度為I_p
2. 選擇適當的閾值t
3. 考慮被測像素周圍有16個像素的圓圈。（見下圖）
4. 現在，如果圓中存在一組（共16個像素）n個連續的像素，它們均比I_p + t 亮，或者比I_p-t 都暗，則像素 p 是一個角。（在上圖中顯示為白色虛線）。n被選為12。
5. 建議使用高速測試以排除大量的非角區域。此測試僅檢查1、9、5和13處的四個像素（如果第一個1和9太亮或太暗，則對其進行測試。如果是，則檢查5和13）。如果p是一個角，則其中至少三個必須全部比 I_p + t 亮或比 I_p-t 暗。如果以上兩種情況都不是，則p不能為角。然後，可以通過檢查圓中的所有像素，將完整的分段測試標準應用於通過的候選項。該檢測器本身具有很高的性能，但有幾個缺點： 它不會拒絕n < 12的候選對象。 像素的選擇不是最佳的，因為其效率取決於問題的順序和角落外觀的分佈。 高速測試的結果被丟棄了。 彼此相鄰地檢測到多個特徵。

機器學習的方法解決了前三點。使用非最大抑制來解決最後一個問題。

讓機器學習一個角檢測器

1. 選擇一組圖像進行訓練（最好從目標應用程序域中進行訓練）
2. 在每個圖像中運行FAST算法以查找特徵點。
3. 對於每個特徵點，將其周圍的16個像素存儲為矢量。對所有圖像執行此操作以獲得特徵向量P。
4. 這16個像素中的每個像素（例如x）可以具有以下三種狀態之一：

1. 取決於這些狀態，特徵矢量P被細分為3個子集，Pd, Ps, P_b。
2. 定義一個新的布爾變量K_p，如果p是一個角，則為true，否則為false。
3. 使用ID3算法（決策樹分類器）使用變量Kp查詢每個子集，以獲取有關真實類的知識。它選擇x，該x通過Kp的熵測得的有關候選像素是否為角的信息最多。
4. 遞歸地將其應用於所有子集，直到其熵為零為止。
5. 這樣創建的決策樹用於其他圖像的快速檢測。

非最大抑制

在相鄰位置檢測多個興趣點是另一個問題。通過使用非極大抑制來解決。

1. 計算所有檢測到的特徵點的得分函數V。V是p與16個周圍像素值之間的絕對差之和。
2. 考慮兩個相鄰的關鍵點並計算它們的V值。
3. 丟棄較低V值的那個。

總結

它比其他現有的拐角檢測器快幾倍。

但是它對高水平的噪聲並不魯棒。它取決於閾值。

OpenCV中的高速拐角檢測器

它被稱為OpenCV中的任何其他特徵檢測器。如果需要，您可以指定閾值，是否要應用非極大抑制，要使用的鄰域等。對於鄰域，定義了三個標誌，分別為cv.FAST_FEATURE_DETECTOR_TYPE_5_8，cv.FAST_FEATURE_DETECTOR_TYPE_7_12和cv.FAST_FEATURE_DETECTOR_TYPE_9_16。以下是有關如何檢測和繪製FAST特徵點的簡單代碼。

<code>import numpy as npimport cv2 as cvfrom matplotlib import pyplot as pltimg = cv.imread('simple.jpg',0)# 用默認值初始化FAST對象fast = cv.FastFeatureDetector_create()# 尋找並繪製關鍵點kp = fast.detect(img,None)img2 = cv.drawKeypoints(img, kp, None, color=(255,0,0))# 打印所有默認參數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)# 關閉非極大抑制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)/<code>

查看結果。第一張圖片顯示了帶有nonmaxSuppression的FAST，第二張圖片顯示了沒有nonmaxSuppression的FAST：

附加資源

1. Edward Rosten and Tom Drummond, “Machine learning for high speed corner detection” in 9th European Conference on Computer Vision, vol. 1, 2006, pp. 430–443.
2. Edward Rosten, Reid Porter, and Tom Drummond, "Faster and better: a machine learning approach to corner detection" in IEEE Trans. Pattern Analysis and Machine Intelligence, 2010, vol 32, pp. 105-119.

閱讀更多 人工智能遇見磐創 的文章

關鍵字: 算法 像素 角點