相關：SIFT原理與源碼解析
SURF原理與源碼解析
在實時的視訊流進行中，需要對每一幀特征提取，對算法處理速度上有很高的要求，傳統的SIFT,Harris等特征點提取很難滿足。由此提出Fast（Features from Accelerated Segment Test），由于不涉及尺度，梯度，等複雜運算，Fast檢測器速度非常快。它使用一定鄰域内像元的灰階值與中心點比較大小去判斷是否為一個角點。但它的缺點是不具有方向性,尺度不變性。
轉載請注明出處：http://blog.csdn.net/luoshixian099/article/details/48294967
Fast角點提取步驟（以Fast-12-16為例）：
1.以固定半徑為圓的邊上取16個像素點（圖中白色框出的位置），與中心點像素值Ip做差。
2.若邊上存在連續的12（N>12,若為Fast-9,隻需要N>9）個點滿足 ( I(x)-I(p) )>threshold 或者 ( I(x)-I(p) ) < -threshold。(其中I(x)表示邊上的像素值，I(p)為中心點像素值，threshold為設定的門檻值。)則此點作為一個候選角點。如圖上的虛線連接配接的位置。通常為了加速計算，直接比較1,5,9,13位置的內插補點，超過三個即視為一個候選點（存在連續的12個像元的必要條件），否則直接排除。
3.非極大值抑制，排除不穩定角點。采用強度響應函數：
即一個角點強度值定義為中心點與邊上的12個角點像素內插補點的絕對值累加和。
opencv源碼解析：
同上面原理部分不同，opencv中預設采用Fast-9-16（還包括Fast-5-8,Fast-7-12）.即在周圍取16個像素點，若超過連續9個點與中心點內插補點大于門檻值即成為候選角點。
角點強度計算方法不采用上面的公式所描述，而是采用最小的內插補點(見代碼分析)作為其角點強度值。
#include <stdio.h>
#include <iostream>
#include "cv.h"
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/core/core.hpp"
#include "opencv2/features2d/features2d.hpp"
using namespace std;
using namespace cv;
int main( int argc, char** argv )
{
Mat img_1 = imread( "F:\\Picture\\hotel.jpg");
if( !img_1.data )
{
return -1; }
FastFeatureDetector detector(50,true); //第一個參數為門檻值，第二個采用非最大值抑制
std::vector<KeyPoint> keypoints_1;
detector.detect( img_1, keypoints_1 );//調用FAST_t函數檢測，見下面詳細解析
drawKeypoints(img_1,keypoints_1,img_1,Scalar::all(255));
imshow("HOTEL",img_1);
waitKey(0);
return 0;
}
void FAST_t(InputArray _img, std::vector<KeyPoint>& keypoints, int threshold, bool nonmax_suppression)
{
Mat img = _img.getMat();
const int K = patternSize/2, N = patternSize + K + 1;
int i, j, k, pixel[25];
makeOffsets(pixel, (int)img.step, patternSize);
keypoints.clear();
threshold = std::min(std::max(threshold, 0), 255);//保證門檻值在0-255之間。
uchar threshold_tab[512];
for( i = -255; i <= 255; i++ )
threshold_tab[i+255] = (uchar)(i < -threshold ? 1 : i > threshold ? 2 : 0); //分類成為darker、similar、brighter三種
AutoBuffer<uchar> _buf((img.cols+16)*3*(sizeof(int) + sizeof(uchar)) + 128);
uchar* buf[3];
buf[0] = _buf; buf[1] = buf[0] + img.cols; buf[2] = buf[1] + img.cols;//儲存對應角點強度值，否則為0
int* cpbuf[3];
cpbuf[0] = (int*)alignPtr(buf[2] + img.cols, sizeof(int)) + 1;//儲存角點位置，+1為了存儲這一行的角點總數
cpbuf[1] = cpbuf[0] + img.cols + 1;
cpbuf[2] = cpbuf[1] + img.cols + 1;
memset(buf[0], 0, img.cols*3);
for(i = 3; i < img.rows-2; i++)
{
const uchar* ptr = img.ptr<uchar>(i) + 3;
uchar* curr = buf[(i - 3)%3];
int* cornerpos = cpbuf[(i - 3)%3];
memset(curr, 0, img.cols);
int ncorners = 0;
if( i < img.rows - 3 )
{
j = 3;
/*采用9點分割測試，加快檢測速度
檢測任意一個直徑兩端的像素點，若同時與中心點相似，必定不是角點
因為至少要占一半的數量
*/
for( ; j < img.cols - 3; j++, ptr++ )
{
int v = ptr[0];
const uchar* tab = &threshold_tab[0] - v + 255;
int d = tab[ptr[pixel[0]]] | tab[ptr[pixel[8]]];//
if( d == 0 ) // 加快檢測速度[0]與[8]兩個點都與中心點灰階值相近，排除這個點
continue;
d &= tab[ptr[pixel[2]]] | tab[ptr[pixel[10]]];//直徑兩端兩個點都相近，則為0
d &= tab[ptr[pixel[4]]] | tab[ptr[pixel[12]]];//
d &= tab[ptr[pixel[6]]] | tab[ptr[pixel[14]]];//每隔45度選取一個點
if( d == 0 ) //
continue;
d &= tab[ptr[pixel[1]]] | tab[ptr[pixel[9]]];
d &= tab[ptr[pixel[3]]] | tab[ptr[pixel[11]]];
d &= tab[ptr[pixel[5]]] | tab[ptr[pixel[13]]];
d &= tab[ptr[pixel[7]]] | tab[ptr[pixel[15]]];
if( d & 1 ) // darker 中心值大，周圍小的情況
{
int vt = v - threshold, count = 0;
for( k = 0; k < N; k++ ) //且連續一半的像素點灰階內插補點( v-x > threshold )大于門檻值
{
int x = ptr[pixel[k]];
if(x < vt)
{
if( ++count > K )
{
cornerpos[ncorners++] = j;
if(nonmax_suppression)//非最大值抑制
curr[j] = (uchar)cornerScore<patternSize>(ptr, pixel, threshold);//計算角點的強度響應值,最小的內插補點（絕對值）
break;
}
}
else
count = 0;
}
}
if( d & 2 )//brighter 中心值小，周圍值大的情況
{
int vt = v + threshold, count = 0;
for( k = 0; k < N; k++ ) //連續一半的像素點灰階內插補點( x-v < threshold )大于門檻值
{
int x = ptr[pixel[k]];
if(x > vt)
{
if( ++count > K )
{
cornerpos[ncorners++] = j;
if(nonmax_suppression)
curr[j] = (uchar)cornerScore<patternSize>(ptr, pixel, threshold);//計算角點的強度響應值,最小的內插補點（絕對值）
break;
}
}
else
count = 0;
}
}
}
}
cornerpos[-1] = ncorners;//存儲第i行上的角點總數量
if( i == 3 )
continue;
/*與鄰域的8個角點響應值做比較，非角點的響應值為0*/
const uchar* prev = buf[(i - 4 + 3)%3]; //相鄰的兩行
const uchar* pprev = buf[(i - 5 + 3)%3];//
cornerpos = cpbuf[(i - 4 + 3)%3];//存儲角點的列位置
ncorners = cornerpos[-1]; //存儲第i行上的角點總數量
for( k = 0; k < ncorners; k++ )
{
j = cornerpos[k];
int score = prev[j];
if( !nonmax_suppression || //非極大值抑制,用角點強度值比較周圍8個強度響應值
(score > prev[j+1] && score > prev[j-1] &&
score > pprev[j-1] && score > pprev[j] && score > pprev[j+1] &&
score > curr[j-1] && score > curr[j] && score > curr[j+1]) )
{
keypoints.push_back(KeyPoint((float)j, (float)(i-1), 7.f, -1, (float)score));
}
}
}
}
角點的強度計算方法：若采用Fast-9-16,計算連續的9個位置與中心位置的內插補點的絕對值，取最小的一個內插補點作為其強度值。
int cornerScore<16>(const uchar* ptr, const int pixel[], int threshold)//角點強度計算
{
const int K = 8, N = K*3 + 1;
int k, v = ptr[0];
short d[N];
for( k = 0; k < N; k++ ) //計算與周圍16個像素點的內插補點,儲存在d[k]中
d[k] = (short)(v - ptr[pixel[k]]);
int a0 = threshold;
for( k = 0; k < 16; k += 2 ) //周圍像素小于中心點像素
{
int a = std::min((int)d[k+1], (int)d[k+2]);
a = std::min(a, (int)d[k+3]);
if( a <= a0 )
continue;
a = std::min(a, (int)d[k+4]);
a = std::min(a, (int)d[k+5]);
a = std::min(a, (int)d[k+6]);
a = std::min(a, (int)d[k+7]);
a = std::min(a, (int)d[k+8]);
a0 = std::max(a0, std::min(a, (int)d[k]));
a0 = std::max(a0, std::min(a, (int)d[k+9]));
}
int b0 = -a0;
for( k = 0; k < 16; k += 2 )//周圍像素點大于中心像素點
{
int b = std::max((int)d[k+1], (int)d[k+2]);
b = std::max(b, (int)d[k+3]);
b = std::max(b, (int)d[k+4]);
b = std::max(b, (int)d[k+5]);
if( b >= b0 )
continue;
b = std::max(b, (int)d[k+6]);
b = std::max(b, (int)d[k+7]);
b = std::max(b, (int)d[k+8]);
b0 = std::min(b0, std::max(b, (int)d[k]));
b0 = std::min(b0, std::max(b, (int)d[k+9]));
}
threshold = -b0-1;
return threshold;
}
參考文章：Edward Rosten et.:Machine Learning for High-Speed Corner Detection
http://blog.csdn.net/kezunhai/article/details/11290749
http://www.edwardrosten.com/work/fast.html