OpenCV3學習（11.5） FAST特征檢測器FastFeatureDetector

簡介

      FAST特征檢測的特點是簡單、快速、有效。作者為了在實時幀速率情況下進行高速特征檢測，提出FAST特征檢測。 相比SIFT、DoG、Harris、SUSAN等比較耗時的特征檢測方法，FAST隻利用周圍的像素進行比較，速度大大加快。注意：FAST隻是一種特征點檢測算法，并不涉及特征點的特征描述。

       大多數特征檢測算法通過在圖像上計算角點響應函數（C），然後檢測超過門檻值（并且是局部最大值）的像素。 如Harris特征使用的角點響應函數： 

其中：

          Shi-Tomasi特征使用的角點響應函數： 

        另一類角點探測器的工作原理是檢查一小塊圖像，看它是否看起來像一個角點。 由于不計算二階導數，是以不需要降噪步驟（例如高斯平滑）。 是以，這些角點檢測器在計算上是有效的，因為對于檢測到的每個角點隻檢查少量的像素。 是以，它們僅具有諸如模糊圖像的大尺寸特征。FAST角點檢測屬于這一類。 

          FAST算法是基于角點檢測的圖像特征.一個特征點檢測的算法的第一步是定義什麼是特征點,FAST算法定義特征點是如果某個像素點和他周圍領域足夠多的像素點處于不同區域,那麼這個像素點就是特征點,對于灰階圖像來說,也就是該點的灰階值和其周圍足夠多的像素點的灰階值不同,那麼這個像素點就是一個特征點.

FAST算法的步驟:

從圖檔中選取一個坐标點P,擷取該點的像素值,接下來判定該點是否為特征點.

選取一個以選取點P坐标為圓心的半徑等于r的Bresenham圓(一個計算圓的軌迹的離散算法,得到整數級的圓的軌迹點),一般來說,這個圓上有16個點,如下所示

使用FAST進行功能檢測:

1、p在圖像中選擇一個被識别為興趣點的像素。令它的強度為 Ip； 

2、選擇一個合适的門檻值t； 

3、考慮被測像素周圍的16個像素的圓圈。 

4、如果這16個像素中存在一組ñ個連續的像素的像素值，比 Ip+t 大，或比 Ip−t小，則像素p是一個角點。ñ被設定為12。 

5、使用一種快速測試（high-speed test）可快速排除了大量的非角點。這個方法隻檢測在1、9、5、13個四個位置的像素，（首先檢測1、9位置的像素與門檻值比是否太亮或太暗，如果是，則檢查5、13）。如果p是一個角點，則至少有3個像素比 Ip+t大或比 Ip−t暗。如果這兩者都不是這樣的話，那麼p就不能成為一個角點。然後可以通過檢查圓中的所有像素，将全部分段測試标準應用于通過的對候選的角點。這種探測器本身表現出很高的性能，但有一些缺點： 

- 它不能拒絕n <12的候選角點。當n<12時可能會有較多的候選角點出現 

- 檢測到的角點不是最優的，因為它的效率取決于問題的排序和角點的分布。 

- 角點分析的結果被扔掉了。過度依賴于門檻值

- 多個特征點容易擠到一起。 

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

1、機器學習角點探測器

選擇一組用于訓練的圖像（最好來自目标應用區域），在每個圖像中運作FAST算法以查找特征點。對于每個特征點，将其周圍的16個像素存儲為一個向量。擷取所有圖像的特征向量P。對于圓上的每個位置x∈{1..16}，這16個相對于p的位置（由p→x表示）的像素有以下3種狀态： 

1. 根據這些狀态，特征向量P被細分為3個子集 

   

   ,

   

   ,

   

   。
2. 定義一個新的布爾變量 Kp，若p是一個角點，則為true，否則為false。
3. 使用ID3算法（決策樹分類器）使用變量來查詢每個子集，利用 Kp确認其真實類别。通過測量Kp的熵，選擇産生關于候選像素是否是一個角點的資訊最多的x。
4. 遞歸地應用于所有的子集，直到它的熵為零。
5. 這樣建立的決策樹用于其他圖像的快速檢測。

2 非極大抑制

在篩選出來的候選角點中有很多是緊挨在一起的，需要通過非極大值抑制來消除這種影響。

為所有的候選角點都确定一個打分函數V，V的值可這樣計算：先分别計算Ip與圓上16個點的像素值內插補點，取絕對值，再将這16個絕對值相加，就得到了V 的值。

最後比較毗鄰候選角點的V值，把V值較小的候選角點pass掉。

至此，FAST算法結束。

在上面的步驟中我們令n=12，此時是FAST算法中的FAST-12，常用的還有FAST-9，即令n=9。

OpenCV3中FAST方法以FastFeatureDetector類的形式封裝，為Feature2D類的子類:

class CV_EXPORTS_W FastFeatureDetector : public Feature2D
{
public:
    enum
    {
        TYPE_5_8 = 0, TYPE_7_12 = 1, TYPE_9_16 = 2,
        THRESHOLD = 10000, NONMAX_SUPPRESSION=10001, FAST_N=10002,
    };
    CV_WRAP static Ptr<FastFeatureDetector> create( 
int threshold=10,                                                    bool nonmaxSuppression=true,
int type=FastFeatureDetector::TYPE_9_16 );
    CV_WRAP virtual void setThreshold(int threshold) = 0;
    CV_WRAP virtual int getThreshold() const = 0;
    CV_WRAP virtual void setNonmaxSuppression(bool f) = 0;
    CV_WRAP virtual bool getNonmaxSuppression() const = 0;
    CV_WRAP virtual void setType(int type) = 0;
    CV_WRAP virtual int getType() const = 0;
};
           

參數說明： Ptr<FastFeatureDetector> create( int threshold=10, bool nonmaxSuppression=true,

                                 int type=FastFeatureDetector::TYPE_9_16 );

　　threshold是指比較時邊緣軌迹點和中心點的內插補點,也就是第三步的門檻值t, nonmaxSuppression代表是否使用第五步非極大值抑制,如果發現fast檢測的結果有聚簇情況,那麼可以考慮采用,第三個參數type的取值來自于FastFeatureDetector枚舉,有如下取值:

1. TYPE_5_8 從軌迹中取8個點,當有5個點滿足條件,就是特征點.
2. TYPE_7_12 取軌迹12個點,7個滿足條件,就是特征點.
3. TYPE_9_16 取軌迹16個點,當9個滿足條件,就是特征點.

　　綜上所述我們可以看出,FAST檢測算法沒有多尺度的問題,是以計算速度相對較快,但是當圖檔中的噪點較多的時候,會産生較多的錯誤特征點,健壯性并不好,并且, 算法的效果還依賴于一個門檻值t。而且FAST不産生多尺度特征而且FAST特征點沒有方向資訊，這樣就會失去旋轉不變性.但是在要求實時性的場合,比如視訊監控的物體識别,是可以使用的.

 執行個體：

#include <opencv2/opencv.hpp>
#include<opencv2/features2d.hpp>
using namespace cv;
using namespace std;

int thre = 40;
Mat src;
void trackBar(int, void*);

int main(int argc, char** argv)
{
    src = imread("E:/image/image/house2.jpg"); 
    if (src.empty())
    {
        printf("can not load image \n");
        return -1;
    }
    namedWindow("input",WINDOW_AUTOSIZE);
    imshow("input", src);  

    namedWindow("output",WINDOW_AUTOSIZE);
    createTrackbar("threshould", "output", &thre,255, trackBar);
    cvWaitKey(0);  
    return 0;
}

void trackBar(int, void*)
{
    std::vector<KeyPoint> keypoints;
    Mat dst = src.clone();
    Ptr<FastFeatureDetector> detector = FastFeatureDetector::create(thre);
    detector->detect(src,keypoints);
    drawKeypoints(dst, keypoints, dst, Scalar::all(-1), DrawMatchesFlags::DRAW_OVER_OUTIMG);  
    imshow("output", dst);  
}
           

結果：

from:https://blog.csdn.net/akadiao/article/details/79189599