角點檢測快速算法 FAST 科技頭條網

目標

在這個章節,

我們將理解FAST算法的基本原理
並在openCV中使用FAST算法的函數.

原理

我們看到了幾個特性檢測器，其中很多都非常好. 但是從實時應用的角度來看，它們還不夠快. 一個很好的例子：比如要在計算資源有限的移動機器人上應用SLAM技術 (即使定位和地圖構建技術) 將出現問題。一個解決方案就是採用FAST算法，由Edward Rosten和Tom Drummond在他們2006年的論文《機器學習用於高速拐角檢測》中提出(後來在2010年進行了修訂)。算法的基本總結如下。

使用 FAST來檢測特徵

選擇圖像中的像素p作為興趣點或不作為興趣點。讓它的強度 I p.
選擇合適的閾值 t.
圍繞測試中的像素考慮一個由16個像素組成的圓圈 (如下圖所示)

那麼像素 p 是一個角點，如果圓圈中有一組相鄰的n個像素(為16個像素中的n個)，它們的亮度都大於 Ip+t, 或者比 Ip−t 暗. (在上圖中白色虛線表示). n 為12.
提出了一種排除大量非轉角的高速試驗方法。這個測試只檢查1,9,5和13處的4個像素(先測試1和9處的像素看是否它們太亮或太暗，如果是，那麼再檢查5和13)。如果p是一個角，那麼其中至少三個點的亮度必須大於Ip+t 或比Ip - t 暗。如果這兩者都不是，那麼 p 就不能是角。然後通過對圓形中所有像素的檢測，將全段測試準則應用到通過的候選對象上。該探測器本身表現出高性能，但有幾個弱點:

該算法不會拒絕大量 n < 12 的候選點.
像素的選擇不是最優的，因為它的效率取決於問題的排序和角的分佈。
快速測試的結果可能被丟棄。
多個特徵相鄰檢測。

前3點是用機器學習方法解決的。最後一個是使用非最大抑制。

機器學習角檢測器

選擇一組用於培訓的圖像 (最好來自檢測目標範圍的圖像)
對每一張圖像運用 FAST 算法找到特點.
對於每個特徵點，將其周圍的16個像素存儲為一個向量。對所有的圖像都這樣做，得到特徵向量P。
這16個像素中的每個像素(比如x)都可以有以下三種狀態之一:

5. 根據這些狀態，特徵向量P被細分為三個子集, Pd, Ps, Pb.

6. 定義一個新的布爾變量Kp，如果p是一個角，則為真，否則為假。

7. 使用ID3算法(決策樹分類器)查詢每個子集，使用變量Kp查詢關於真類。它選擇產生最多信息量的x作為是否是角的候選，可以通過計算Kp的熵來度量。

8. 遞歸地應用於所有子集，直到它的熵為零。

9. 所建立的決策樹用於其他圖像的快速檢測。

非最大值抑制

在相鄰位置檢測多個興趣點是另一個問題。採用非最大抑制法求解。

計算一個分數函數，V代表所有檢測到的特徵點。V是p和周圍16個像素值的絕對差值之和。
考慮兩個相鄰的關鍵點並計算它們的V值。
Discard t丟棄V值較低的那個。

總結

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

但它對高噪點的圖像效果並不好，依賴於閾值設定。

OpenCV中應用FAST

和其它特徵檢測器一樣。假如你想，你可以指定閾值，不管非最大值抑制用不用，鄰域都開啟。鄰域定義了3個標籤，cv.FAST_FEATURE_DETECTOR_TYPE_5_8, cv.FAST_FEATURE_DETECTOR_TYPE_7_12 and cv.FAST_FEATURE_DETECTOR_TYPE_9_16. 下面簡單的幾行代碼展示如何使用FAST函數檢測和繪製特徵點。

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
img = cv.imread('simple.jpg',0)
# Initiate FAST object with default values
fast = cv.FastFeatureDetector_create()
# find and draw the keypoints
kp = fast.detect(img,None)
img2 = cv.drawKeypoints(img, kp, None, color=(255,0,0))
# Print all default params
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)
# Disable nonmaxSuppression 

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)