角点检测算法概述
在计算机视觉领域，角点检测是特征提取的基础步骤之一，常用于图像匹配、目标跟踪、SLAM 等应用。角点（Corner）是指图像中强度变化剧烈的点，通常位于物体边缘的交汇处。本文将详细讲解两种经典的角点检测算法：Harris 角点检测 和 FAST (Features from Accelerated Segment Test)，并比较它们的优缺点。
Harris 角点检测算法
Harris 角点检测算法由 Chris Harris 和 Mike Stephens 于 1988 年提出，是基于图像梯度的经典方法。它通过分析图像局部窗口的强度变化来判断是否为角点。
基本原理
想象在一个小图像窗口上进行平移（u, v）：
- 如果窗口位于平坦区域，所有方向变化都很小。
- 如果位于边缘，只沿边缘方向变化小，其他方向变化大。
- 如果位于角点，所有方向变化都剧烈。
数学公式
计算角点响应函数 R：
$$R = \det(M) - k [\text{tr}(M)]^2$$
具体展开为：
$$\det(M) = I_x^2 I_y^2 - (I_x I_y)^2 = \lambda_1 \lambda_2$$
其中 $\lambda_1$ 和 $\lambda_2$ 是矩阵 M 的特征值，k 是经验常数（典型取值 0.04 ∼ 0.06）。判断准则如下：
- 如果 R 大且正：角点
- 如果 R 负：边缘
- 如果 |R| 小：平坦区域
计算结构张量矩阵 M 的元素：
$$M = \sum_{w} w(x,y) \begin{bmatrix} I_x^2 & I_x I_y \ I_x I_y & I_y^2 \end{bmatrix}$$
（对窗口内像素求和，通常加高斯加权）。
计算图像在 x 和 y 方向的梯度：
$$I_x = \frac{\partial I}{\partial x}, \quad I_y = \frac{\partial I}{\partial y}$$
通常使用 Sobel 算子。
最后进行非极大值抑制（Non-maximal suppression）和阈值化得到最终角点。
Harris 算法鲁棒性强，对旋转有一定不变性，但计算量较大，需要梯度计算和高斯平滑。
改进：Shi-Tomasi 算法
1994 年，Jianbo Shi 和 Carlo Tomasi 提出改进，避免了敏感的 k 参数，直接使用最小特征值作为响应：
$$R = \min(\lambda_1, \lambda_2)$$
当 R 大于阈值时即为'好特征点'（Good Features to Track）。在 OpenCV 中，cv2.goodFeaturesToTrack() 即实现此版本，稳定性更好。
Harris 对旋转具有不变性，对光照变化较鲁棒，但缺乏尺度不变性，且计算密集（需多次卷积）。
FAST 角点检测算法
FAST 算法由 Edward Rosten 和 Tom Drummond 于 2006 年提出（2010 年改进），旨在实现高速角点检测，特别适合实时应用。
基本原理
以候选像素 p 为中心，考察半径为 3 的 Bresenham 圆上的 16 个像素。如果存在连续 N 个（常用 N=9 或 12）像素的强度都显著比 p 亮（或都显著比 p 暗），则 p 为角点。
阈值 t 控制敏感度。
加速技巧
- 高频剔除：先只检查 4 个正交像素（1、5、9、13）。若至少 3 个满足条件，再检查全部 16 个（剔除率 >90%）。
- 机器学习优化：使用 ID3 决策树为每个位置训练最优检查顺序。
- 非极大值抑制：计算角点分数 V。
FAST 极快，常用于实时视频处理（如 ORB 特征中使用）。
