Moravec 角点检测:一切的起点
角点检测的历史有一 个明确的起点:1977 年,Hans Moravec 在斯坦福 AI 实验室为一辆叫做 Stanford Cart 的漫游车写视觉里程计。这辆车每次移动一米,停下来拍 9 张照片,再靠立体匹配算深度。Moravec 需要在图像里找一些"有区分度"的点作为匹配的锚点——不能是天空那样的一片均匀区(哪个点都长得一样,匹配不上),也不能是墙的边缘(沿着边缘滑动依然长得一样,会漏定位)。他要的是那种"往哪个方向挪都变样"的点。这就是角点(corner)作为视觉特征最早的定义。
后来的所有角点检测器——Harris、Shi-Tomasi、SUSAN、FAST——本质上都在改进 Moravec 的这个思路。所以先看清楚 Moravec 做了什么、又为什么不够好,才能理解后面几十年的演进。
1. 核心直觉:小窗口平移看变化
给图像 ,在位置 开一个小窗口 (Moravec 原文里是 、 或 )。把这个窗口沿方向 移动一个像素,与原位置的内容做像素差平方和:
这就是最经典的 SSD(Sum of Squared Differences),也叫自相似度。 大表示挪动后差别大,说明这个位置有"结构"; 小表示挪动后几乎一样,位置本身没什么区分度。
三种典型局部结构的 曲面长什么样:
平坦区 边缘 角点
E │ E │ E │
│ ───────── │ ╱╲ │ ╱╲
│ │ ╱ ╲ │ ╱ ╲
│ │───── ───── │ ╱ ╲
└──────── (u,v) └──────── (u,v) └──────── (u,v)
各方向都很小 垂直边缘方向大 各方向都很大
沿边缘方向小
角点的判据一目了然: 在所有方向上都足够大。问题是"所有方向"要怎么算,硬件资源有限的 1977 年不可能对每一个方向枚举 SSD。
2. Moravec 的近似:4 个离散方向
Moravec 只测 4 个方向:水平、垂直、两条对角线,也就是 (以及它们的负方向,但 SSD 对称,不必重复)。然后取这 4 个 里的最小值作为该点的"兴趣度"(interest value):
为什么是最小?因为角点要求所有方向都变化大——最差的那个方向如果都变化很大,其它方向就更大。反过来,只要有任何一个方向变化小(沿着某条边缘滑动), 就把这个点否掉了。这正是"最脆弱的方向决定强度"的逻辑,和后来 Shi-Tomasi 取 的思路一模一样,只不过 Shi-Tomasi 换成了矩阵特征值。
得到 图之后,做阈值 + 非极大值抑制(NMS):先把 小于阈值的点扔掉,再在 或 邻域里只保留局部最大值。剩下的就是 Moravec 角点。
3. 算法伪代码
输入: 灰度图 I, 窗口半径 r, 阈值 T
输出: 角点集合 P
1. 对每个像素 (x,y):
对每个方向 (u,v) ∈ {(1,0),(0,1),(1,1),(1,-1)}:
E(u,v) = 0
for s in [-r, r]:
for t in [-r, r]:
d = I[x+s+u, y+t+v] - I[x+s, y+t]
E(u,v) += d*d
C(x,y) = min E(u,v) // 4 个方向取最小
2. 阈值: 保留 C(x,y) > T 的点
3. NMS: 在 3x3 邻域内只保留局部最大 C 的点
4. 返回剩下的 (x,y) 作为角点
计算复杂度 , 是像素数。1970 年代的机器上跑一张几百像素宽的图像要几秒钟。Stanford Cart 走一米要处理十几分钟的图像——这也是为什么后来 Moravec 说"我们的车子想的比走的多得多"。
4. 三个致命缺陷
Moravec 检测器能用,但它有三个结构性问题,直接催生了 Harris 1988 的改进。
4.1 各向异性:只测 4 个方向
只是"对角"方向,但 、 呢?如果一条边缘沿着 方向倾斜,那么在 4 个测试方向上,SSD 都会比较大——因为这些方向都不是沿边缘的滑动方向,最小值不为零。结果本来是边缘的位置被误判为角点。
反过来,如果一个真正的角点恰好开口方向在 附近,某个测试方向可能碰巧沿着一条较弱的边缘滑,SSD 意外偏小,最小值被拉低,角点被漏检。
问题的根源是 4 个离散方向对旋转不闭合——图像旋转一下, 值就变了。这个缺陷在几何标定、拼接、结构光扫描这类需要旋转不变性的任务里是致命的。
Harris 1988 的解决办法是用一阶 Taylor 展开把 变成一个连续函数:
于是"所有方向"变成了"矩阵 的最小特征值",天然是各向同性的。这一步跨越是从离散采样到微分几何的跳跃。
4.2 二值窗函数:噪声敏感
Moravec 的窗口 是矩形二值窗——窗内权重全 1,窗外全 0。这个窗函数在频率域里是 sinc,有很强的旁瓣。含义是:窗口边界上的像素和中心像素权重一样,一旦有一个孤立噪声点掉进窗内,它对 的贡献等同于中心的角点结构。
后果是 图上会有大量伪极大值,NMS 之后还是留下一堆随机点。想抑制这种噪声,直接的办法是先做高斯平滑(参考灰度变换与空间滤波),但这又会削弱真正的角点响应。Moravec 的原始实现里没有加权,工程上只能靠加大阈值来筛,代价是召回率下降。
Harris 直接把矩形窗换成高斯窗 ——中心权重高、边缘权重衰减,天然对偏离中心的噪声不敏感。这是一个几乎没有额外计算成本的巨大改进。
4.3 只看最小值,丢掉了方向分布信息
是一个信息压缩极高的操作。它只告诉你"最弱方向有多弱",完全不告诉你其它方向是什么样、方向分布是不是均匀。想象两种局部结构:
- A:4 个方向 值都是 100。这是一个理想角点,方向分布均匀。
- B:3 个方向 值是 500,1 个方向是 100。这更像一个 T 型交点或畸形结构,某一方向仍然容易滑动。
两者 Moravec 值一样(都是 100),但 A 才是稳定的角点。Harris 用两个特征值 联合刻画,把"方向分布均匀性"编码进检测器里——Harris 响应 惩罚"一大一小"的情况;Shi-Tomasi 索性直接取 ,逻辑上比 Moravec 更精确但保留了对方向分布的敏感。
5. 从 Moravec 到 Harris 的对照
把两代检测器放在一起:
| 维度 | Moravec 1977 | Harris 1988 |
|---|---|---|
| 变化度量 | 4 方向 SSD | 结构张量 的特征值 |
| 方向刻画 | 离散 4 方向 | 连续(所有方向) |
| 窗函数 | 矩形二值 | 高斯 |
| 响应函数 | 4 方向 | |
| 旋转不变 | 否 | 是 |
| 计算量 | 4 次 SSD/像素 | 一次梯度 + 行列式 |
Harris 的每一处改进都精确对应 Moravec 的一个缺陷。这不是巧合——Chris Harris 和 Mike Stephens 的论文明确说"our method addresses the drawbacks of Moravec's detector"。理解 Moravec 就理解了 Harris 的动机。
6. 一个数值小例子
考虑一个理想的 L 形角点,灰度值如下( 黑, 白):
0 0 0 0 0
0 0 0 0 0
0 0 255 255 255
0 0 255 255 255
0 0 255 255 255
在角点 位置,用 窗做 4 个方向 SSD:
- 向右:窗口内几乎不变(右边还是同样的 L),
- 向下:类似,
- 对角:窗口滑到白色内部, 变大
- 反对角:窗口滑到黑色内部, 变大
= 前两个方向的 ——Moravec 把真实角点漏检了。原因? 窗口太小,向右/向下平移一格时,L 结构自相似,SSD 为零。这类"离散平移让某些方向意外自相似"的情况在实际图像里非常常见。这就是为什么现代实现基本都不再直接用 Moravec,除非当作教学演示。
7. Moravec 的遗产
尽管有这么多缺陷,Moravec 检测器的历史地位无可动摇。它奠定了几个观念:
- 角点是局部自相似性的极小点——这个定义一直沿用到 SUSAN 和 FAST
- "最弱方向决定强度"—— 操作在 Shi-Tomasi 里被继 承
- 阈值 + 非极大值抑制——所有稀疏关键点检测器的标准流水线
Moravec 本人后来把重心转向了移动机器人的其它问题(栅格地图、贝叶斯占据推理),但角点检测这条线索被 Harris、Kanade、Shi、Tomasi、Smith、Rosten 一代一代接下来。当你在 OpenCV 里调用 cv::goodFeaturesToTrack,看到出来那一堆整齐的角点,请记得这条路的起点是斯坦福 1977 年那辆一米一停的漫游车。