3、特征点提取与匹配：SIFT、SURF、ORB特征，暴力匹配与FLANN匹配
各位同学，今天我们来聊聊三维视觉里最基础、也最核心的一环——特征点提取与匹配。
说实话，我入行那会儿，第一个项目就是做全景图拼接。当时老板扔给我一堆照片，说“你把它拼起来”。我一脸懵，心想这玩意儿怎么搞？后来才知道，第一步就是找特征点。你想想看，两张图要拼在一起，总得知道哪些地方是重合的吧？特征点就是干这个的。
特征点说白了，就是图像里那些“与众不同”的像素点。比如角点、边缘点、纹理丰富的点。这些点有个好处：换个角度拍，它还在那儿。我们就是要找到这些点，然后描述它，最后把两张图里相同的点对应起来。
3.1 三大特征提取器：SIFT、SURF、ORB
业内常用的特征提取器，主流就三个：SIFT、SURF、ORB。我一个个说。
3.1.1 SIFT（尺度不变特征变换）
SIFT 是祖师爷级别的算法。2004年Lowe提出来的，到现在快20年了，依然能打。
核心思想：在不同尺度空间上找极值点。说白了，就是把图像放大缩小，在各个尺度上都找一遍角点。这样不管物体离得远还是近，都能找到。
我个人的经验：SIFT 的精度确实高，但速度慢。我在做无人机航拍拼接时，一张2000万像素的图，SIFT 要跑好几秒。实时性要求高的场景，基本不用它。
SIFT 的四个步骤：
- 尺度空间极值检测：用高斯差分金字塔找候选点
- 关键点定位：去掉低对比度和边缘响应点
- 方向分配：给每个关键点算一个主方向
- 描述子生成：在关键点周围取16x16区域，算梯度直方图，生成128维向量
嗯，这里要注意：SIFT 是有专利的。商用项目里用 SIFT 要小心，得买授权。不过学术研究无所谓。
3.1.2 SURF（加速稳健特征）
SURF 是 SIFT 的加速版。2006年提出来的，号称比 SIFT 快3倍。
改进点：
- 用积分图加速了 Hessian 矩阵的计算
- 用 Haar 小波响应代替了梯度直方图
- 描述子维度从128降到了64
我曾经在嵌入式设备上做过测试，SURF 确实比 SIFT 快不少。但说实话，现在用 SURF 的人越来越少了。为什么？因为 ORB 出来了，又快又免费。
避坑指南：我曾经在光照变化剧烈的场景下用 SURF，结果匹配效果很差。后来发现 SURF 对光照变化比较敏感。如果你做室内 SLAM，灯光忽明忽暗，建议慎用 SURF。
3.1.3 ORB（定向FAST和旋转BRIEF）
ORB 是我现在用得最多的特征。2011年由 OpenCV 实验室提出，完全开源免费。
ORB 的组成：
- FAST 角点检测：速度快到飞起，但本身没有尺度不变性
- BRIEF 描述子：二进制描述子，用汉明距离匹配，比欧氏距离快得多
- 改进：加了方向信息（旋转不变性）和尺度金字塔（尺度不变性）
ORB 的匹配速度有多快？我做过对比：同样1000个特征点，SIFT 匹配要50ms，ORB 只要5ms。10倍差距。
注意：ORB 的旋转不变性是通过灰度质心法实现的。如果图像旋转角度太大（超过45度），ORB 的匹配精度会下降。我建议在旋转变化大的场景下，适当增加特征点数量。
3.2 特征匹配：暴力匹配 vs FLANN
特征点提取完了，接下来就是匹配。说白了，就是给第一张图的每个特征点，在第二张图里找最像的那个。
3.2.1 暴力匹配（Brute-Force）
暴力匹配是最简单的方法。对于第一张图的每个特征点，计算它和第二张图所有特征点的距离，取最近的那个。
复杂度：O(n*m)，n和m分别是两张图的特征点数量。如果各1000个点，就要算100万次距离。
我刚开始做项目时，觉得暴力匹配太笨了。后来发现，当特征点数量不多（几百个）时，暴力匹配反而更稳定。因为它不会漏掉最优解。
// OpenCV 暴力匹配示例
cv::BFMatcher matcher(cv::NORM_HAMMING);
std::vector<cv::DMatch> matches;
matcher.match(descriptors1, descriptors2, matches);
// 按距离排序，取前30%好的匹配
std::sort(matches.begin(), matches.end());
matches.erase(matches.begin() + matches.size() * 0.3, matches.end());
3.2.2 FLANN 匹配（快速最近邻搜索库）
FLANN 是 Muja 和 Lowe 在2009年提出的。它用 KD-Tree 或 K-Means 树来加速搜索。
原理：把特征空间划分成多个区域，搜索时只查邻近区域，不用全量遍历。
适用场景：特征点数量大（几千甚至上万），对实时性要求高。
FLANN 的两种索引：
| 索引类型 | 适用描述子 | 特点 |
|---|---|---|
| KD-Tree | SIFT、SURF（浮点型） | 低维空间效果好（<10维），高维退化 |
| LSH（局部敏感哈希） | ORB、BRIEF（二进制型） | 高维二进制描述子专用 |
// OpenCV FLANN 匹配示例（ORB 用 LSH）
cv::FlannBasedMatcher matcher(
new cv::flann::LSHIndexParams(12, 20, 2),
new cv::flann::SearchParams(50)
);
std::vector<cv::DMatch> matches;
matcher.match(descriptors1, descriptors2, matches);
嗯，这里有个坑。我曾经用 FLANN 匹配 SIFT 特征，默认用了 KD-Tree，结果速度还不如暴力匹配。后来查资料才发现，SIFT 的128维特征在高维空间里，KD-Tree 的搜索效率会严重退化。这时候应该用层次 K-Means 树。
3.3 匹配结果优化
匹配完了，结果里肯定有很多错误匹配。我一般会做两步过滤：
- 距离阈值过滤：去掉距离太大的匹配对。一般取最小距离的2-3倍作为阈值。
- 交叉验证：从图1到图2匹配一次，再从图2到图1匹配一次，只有双向一致的才保留。
如果要做更严格的过滤，可以用 RANSAC 估计单应性矩阵或基础矩阵，把不符合几何约束的外点去掉。这个我们后面讲位姿估计时会详细说。
3.4 本章知识体系
下面这张图是我画的，把特征点提取与匹配的整个流程串起来了。你一看就明白。
最后说一句，特征点提取与匹配是三维视觉的基石。SLAM、三维重建、视觉里程计，全都离不开它。我建议你把 SIFT 和 ORB 的源码都读一遍，理解每个步骤在干什么。光调 API 是不够的，遇到问题你都不知道从哪下手。
好了，这一章就到这里。代码示例都在 OpenCV 里，自己动手跑一跑，感受一下不同特征的区别。