FAST（Features from Accelerated Segment Test）角检测算法原理详解和C++代码实现

FAST（Features from Accelerated Segment Test）是一种经典的角点检测算法，由 Edward Rosten 和 Tom Drummond 于 2006 年提出，设计目标是：以极高速度检测出图像中的角点特征，特别适合实时系统（如 SLAM、视觉里程计、跟踪等）。

一、FAST 算法基本原理

1.1 核心思想：加速段测试（Segment Test）

对于图像中一个像素点 $p$，以其为中心画一个半径为 3 的圆（即 Bresenham circle，包含 16 个像素点），判断其是否为角点：

**定义：像素 $p$ 是角点，当且仅当圆上的至少 n 个连续像素（n 一般为 12）**满足以下条件之一：

• 比 $p$ 的像素值亮很多：$I_x\ge I_p+t$
• 比 $p$ 的像素值暗很多：$I_x\le I_p-t$

其中：

• $I_p$：中心点像素值
• $I_x$：圆上某个点的像素值
• $t$：阈值（contrast threshold）

1.2 加速策略：提前淘汰（Early Rejection）

为了避免对所有 16 个点逐一判断，FAST 引入了加速判断机制：

• 先测试圆上的固定 4 个点（1、5、9、13 号位置），若至少有 3 个点与中心像素强烈不同（大于 t 的对比度差），才继续完整测试 16 点；
• 否则直接淘汰。

这一步骤大幅减少了不必要的计算，提高了角点检测效率。

二、数学公式与推导

2.1 圆上像素坐标公式（以 $p=(x,y)$ 为中心）：

圆上的 16 个像素相对坐标如下：

表示第 $k$ 个圆点：

$$p_k=(x+\Delta x_k,y+\Delta y_k)$$

2.2 角点判断公式

定义亮度差阈值 $t$，对于圆上第 $k$ 个像素点，定义：

$$d_k=I(p_k)-I(p)$$

则角点判定条件为：

• 存在一段长度为 $n$ 的连续子序列 { d k } \{ d_k \} {dk​}，使得：

  • 全部满足 $d_k>t$ （亮）
  • 或全部满足 $d_k<-t$（暗）

FAST 最常用的是 $n=12$。

三、非 OpenCV 的纯实现思路

可以使用如下伪代码进行实现：

bool is_corner(const cv::Mat& img, int x, int y, int t) {
    static const int offset[16][2] = {
        {0,-3}, {1,-3}, {2,-2}, {3,-1}, {3,0}, {3,1}, {2,2}, {1,3},
        {0,3}, {-1,3}, {-2,2}, {-3,1}, {-3,0}, {-3,-1}, {-2,-2}, {-1,-3}
    };

    int Ip = img.at<uchar>(y, x);
    int count_bright = 0, count_dark = 0;

    // early rejection (positions: 1, 5, 9, 13)
    int check[4] = {0, 4, 8, 12};
    int pass = 0;
    for (int i = 0; i < 4; ++i) {
        int dx = offset[check[i]][0], dy = offset[check[i]][1];
        int val = img.at<uchar>(y + dy, x + dx);
        if (val > Ip + t || val < Ip - t) pass++;
    }
    if (pass < 3) return false;

    // full segment test
    for (int i = 0; i < 16; ++i) {
        count_bright = count_dark = 0;
        for (int j = 0; j < 12; ++j) {
            int idx = (i + j) % 16;
            int dx = offset[idx][0], dy = offset[idx][1];
            int val = img.at<uchar>(y + dy, x + dx);
            if (val > Ip + t) count_bright++;
            else if (val < Ip - t) count_dark++;
            else break;

            if (count_bright == 12 || count_dark == 12) return true;
        }
    }
    return false;
}

可以将其嵌入图像遍历过程中，检测角点。

四、纯C++代码实现

// FAST Corner Detector with BMP Loading and Non-Maximum Suppression
// By YZS
// Date Time 3th.April 2025

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdint>
#include <fstream>
#include <algorithm>

struct Point {
    int x, y;
    uint8_t score;
};

class GrayImage {
public:
    int width, height;
    std::vector<uint8_t> data;

    bool loadBMP(const std::string& filename) {
        std::ifstream file(filename, std::ios::binary);
        if (!file) return false;

        uint8_t header[54];
        file.read(reinterpret_cast<char*>(header), 54);
        width = *reinterpret_cast<int32_t*>(&header[18]);
        height = *reinterpret_cast<int32_t*>(&header[22]);
        int offset = *reinterpret_cast<int32_t*>(&header[10]);
        int row_padded = (width * 3 + 3) & (~3);

        data.assign(width * height, 0);
        file.seekg(offset);
        for (int i = height - 1; i >= 0; --i) {
            std::vector<uint8_t> row(row_padded);
            file.read(reinterpret_cast<char*>(row.data()), row_padded);
            for (int j = 0; j < width; ++j) {
                uint8_t r = row[j * 3 + 2];
                uint8_t g = row[j * 3 + 1];
                uint8_t b = row[j * 3];
                data[i * width + j] = static_cast<uint8_t>(0.299 * r + 0.587 * g + 0.114 * b);
            }
        }
        return true;
    }

    uint8_t& at(int x, int y) {
        return data[y * width + x];
    }
};

const int circle_offsets[16][2] = {
    {0, -3}, {1, -3}, {2, -2}, {3, -1},
    {3, 0},  {3, 1},  {2, 2},  {1, 3},
    {0, 3},  {-1, 3}, {-2, 2}, {-3, 1},
    {-3, 0}, {-3, -1},{-2, -2},{-1, -3}
};

bool isCorner(const GrayImage& img, int x, int y, int threshold, uint8_t& score) {
    int Ip = img.at(x, y);
    int brighter = 0, darker = 0;

    int test_idx[4] = {0, 4, 8, 12};
    int passed = 0;
    for (int i : test_idx) {
        int dx = circle_offsets[i][0], dy = circle_offsets[i][1];
        int val = img.at(x + dx, y + dy);
        if (val >= Ip + threshold || val <= Ip - threshold)
            ++passed;
    }
    if (passed < 3) return false;

    int max_score = 0;
    for (int i = 0; i < 16; ++i) {
        int count_bright = 0, count_dark = 0;
        for (int j = 0; j < 12; ++j) {
            int idx = (i + j) % 16;
            int dx = circle_offsets[idx][0], dy = circle_offsets[idx][1];
            int val = img.at(x + dx, y + dy);
            if (val >= Ip + threshold) ++count_bright;
            else if (val <= Ip - threshold) ++count_dark;
            else break;
        }
        if (count_bright == 12 || count_dark == 12) {
            max_score = std::max(max_score, std::abs(Ip - img.at(x + circle_offsets[i][0], y + circle_offsets[i][1])));
        }
    }
    score = static_cast<uint8_t>(max_score);
    return max_score > 0;
}

std::vector<Point> nonMaximumSuppression(const std::vector<Point>& corners, int radius) {
    std::vector<Point> result;
    for (const auto& p : corners) {
        bool is_max = true;
        for (const auto& q : corners) {
            if (q.x == p.x && q.y == p.y) continue;
            if (std::abs(q.x - p.x) <= radius && std::abs(q.y - p.y) <= radius) {
                if (q.score > p.score) {
                    is_max = false;
                    break;
                }
            }
        }
        if (is_max) result.push_back(p);
    }
    return result;
}

int main() {
    GrayImage img;
    if (!img.loadBMP("test.bmp")) {
        std::cerr << "Failed to load BMP image.\n";
        return 1;
    }

    int threshold = 20;
    std::vector<Point> corners;

    for (int y = 3; y < img.height - 3; ++y) {
        for (int x = 3; x < img.width - 3; ++x) {
            uint8_t score = 0;
            if (isCorner(img, x, y, threshold, score)) {
                corners.push_back({x, y, score});
            }
        }
    }

    auto nms_corners = nonMaximumSuppression(corners, 3);

    std::cout << "Detected " << nms_corners.size() << " corners after NMS.\n";
    for (auto& p : nms_corners) {
        std::cout << "Corner: (" << p.x << ", " << p.y << ") Score: " << (int)p.score << "\n";
    }

    return 0;
}

五、FAST 优缺点

优点

• **极快：**每个像素只需处理极少量比较运算
• 适用于实时系统
• 易于实现，无需复杂数学

缺点

• 无方向信息（需要后续 Harris 或 Shi-Tomasi 等加权评分）
• 对噪声较敏感
• 不具备尺度不变性（如 SIFT）

六、优化与扩展

• FAST + Non-max Suppression（非极大值抑制）： 保留最强响应点
• FAST + Harris 评分： 提高角点稳定性
• FAST-ER（机器学习优化的版本）
• ORB 特征： 基于 FAST + BRIEF 描述子 + orientation vector