跳到主要内容

Moravec 角点检测:一切的起点

角点检测的历史有一个明确的起点:1977 年,Hans Moravec 在斯坦福 AI 实验室为一辆叫做 Stanford Cart 的漫游车写视觉里程计。这辆车每次移动一米,停下来拍 9 张照片,再靠立体匹配算深度。Moravec 需要在图像里找一些"有区分度"的点作为匹配的锚点——不能是天空那样的一片均匀区(哪个点都长得一样,匹配不上),也不能是墙的边缘(沿着边缘滑动依然长得一样,会漏定位)。他要的是那种"往哪个方向挪都变样"的点。这就是角点(corner)作为视觉特征最早的定义。

后来的所有角点检测器——Harris、Shi-Tomasi、SUSAN、FAST——本质上都在改进 Moravec 的这个思路。所以先看清楚 Moravec 做了什么、又为什么不够好,才能理解后面几十年的演进。

1. 核心直觉:小窗口平移看变化​

给图像 I(x,y)I(x,y),在位置 (x,y)(x,y) 开一个小窗口 WW(Moravec 原文里是 3×33\times 3、5×55\times 5 或 7×77\times 7)。把这个窗口沿方向 (u,v)(u,v) 移动一个像素,与原位置的内容做像素差平方和:

E(x,y;u,v)=∑(s,t)∈W[I(x+s+u, y+t+v)−I(x+s, y+t)]2E(x,y;u,v) = \sum_{(s,t)\in W} \big[I(x+s+u,\, y+t+v) - I(x+s,\, y+t)\big]^2

这就是最经典的 SSD(Sum of Squared Differences),也叫自相似度。EE 大表示挪动后差别大,说明这个位置有"结构";EE 小表示挪动后几乎一样,位置本身没什么区分度。

三种典型局部结构的 EE 曲面长什么样:

     平坦区                边缘                  角点
E │ E │ E │
│ ───────── │ ╱╲ │ ╱╲
│ │ ╱ ╲ │ ╱ ╲
│ │───── ───── │ ╱ ╲
└──────── (u,v) └──────── (u,v) └──────── (u,v)
各方向都很小 垂直边缘方向大 各方向都很大
沿边缘方向小

角点的判据一目了然:EE 在所有方向上都足够大。问题是"所有方向"要怎么算,硬件资源有限的 1977 年不可能对每一个方向枚举 SSD。

2. Moravec 的近似:4 个离散方向​

Moravec 只测 4 个方向:水平、垂直、两条对角线,也就是 (u,v)∈{(1,0),(0,1),(1,1),(1,−1)}(u,v)\in\{(1,0),(0,1),(1,1),(1,-1)\}(以及它们的负方向,但 SSD 对称,不必重复)。然后取这 4 个 EE 里的最小值作为该点的"兴趣度"(interest value):

CMoravec(x,y)=min⁡(u,v)∈DE(x,y;u,v),D={(1,0),(0,1),(1,1),(1,−1)}C_\text{Moravec}(x,y) = \min_{(u,v)\in D} E(x,y;u,v),\qquad D=\{(1,0),(0,1),(1,1),(1,-1)\}

为什么是最小?因为角点要求所有方向都变化大——最差的那个方向如果都变化很大,其它方向就更大。反过来,只要有任何一个方向变化小(沿着某条边缘滑动),min⁡\min 就把这个点否掉了。这正是"最脆弱的方向决定强度"的逻辑,和后来 Shi-Tomasi 取 min⁡(λ1,λ2)\min(\lambda_1,\lambda_2) 的思路一模一样,只不过 Shi-Tomasi 换成了矩阵特征值。

得到 CC 图之后,做阈值 + 非极大值抑制(NMS):先把 CC 小于阈值的点扔掉,再在 3×33\times 3 或 5×55\times 5 邻域里只保留局部最大值。剩下的就是 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) 作为角点

计算复杂度 O(N⋅r2⋅4)O(N\cdot r^2 \cdot 4),NN 是像素数。1970 年代的机器上跑一张几百像素宽的图像要几秒钟。Stanford Cart 走一米要处理十几分钟的图像——这也是为什么后来 Moravec 说"我们的车子想的比走的多得多"。

4. 三个致命缺陷​

Moravec 检测器能用,但它有三个结构性问题,直接催生了 Harris 1988 的改进。

4.1 各向异性:只测 4 个方向​

45∘45^\circ 只是"对角"方向,但 22.5∘22.5^\circ、67.5∘67.5^\circ 呢?如果一条边缘沿着 22.5∘22.5^\circ 方向倾斜,那么在 4 个测试方向上,SSD 都会比较大——因为这些方向都不是沿边缘的滑动方向,最小值不为零。结果本来是边缘的位置被误判为角点。

反过来,如果一个真正的角点恰好开口方向在 22.5∘22.5^\circ 附近,某个测试方向可能碰巧沿着一条较弱的边缘滑,SSD 意外偏小,最小值被拉低,角点被漏检。

问题的根源是 4 个离散方向对旋转不闭合——图像旋转一下,CC 值就变了。这个缺陷在几何标定、拼接、结构光扫描这类需要旋转不变性的任务里是致命的。

Harris 1988 的解决办法是用一阶 Taylor 展开把 E(u,v)E(u,v) 变成一个连续函数:

E(u,v)≈[uv]M[uv],M=∑W[Ix2IxIyIxIyIy2]E(u,v) \approx \begin{bmatrix}u & v\end{bmatrix} M \begin{bmatrix}u\\v\end{bmatrix},\quad M=\sum_{W}\begin{bmatrix}I_x^2 & I_xI_y\\I_xI_y & I_y^2\end{bmatrix}

于是"所有方向"变成了"矩阵 MM 的最小特征值",天然是各向同性的。这一步跨越是从离散采样到微分几何的跳跃。

4.2 二值窗函数:噪声敏感​

Moravec 的窗口 WW 是矩形二值窗——窗内权重全 1,窗外全 0。这个窗函数在频率域里是 sinc,有很强的旁瓣。含义是:窗口边界上的像素和中心像素权重一样,一旦有一个孤立噪声点掉进窗内,它对 EE 的贡献等同于中心的角点结构。

后果是 CC 图上会有大量伪极大值,NMS 之后还是留下一堆随机点。想抑制这种噪声,直接的办法是先做高斯平滑(参考灰度变换与空间滤波),但这又会削弱真正的角点响应。Moravec 的原始实现里没有加权,工程上只能靠加大阈值来筛,代价是召回率下降。

Harris 直接把矩形窗换成高斯窗 w(s,t)=exp⁡(−(s2+t2)/2σ2)w(s,t)=\exp(-(s^2+t^2)/2\sigma^2)——中心权重高、边缘权重衰减,天然对偏离中心的噪声不敏感。这是一个几乎没有额外计算成本的巨大改进。

4.3 只看最小值,丢掉了方向分布信息​

min⁡\min 是一个信息压缩极高的操作。它只告诉你"最弱方向有多弱",完全不告诉你其它方向是什么样、方向分布是不是均匀。想象两种局部结构:

  • A:4 个方向 EE 值都是 100。这是一个理想角点,方向分布均匀。
  • B:3 个方向 EE 值是 500,1 个方向是 100。这更像一个 T 型交点或畸形结构,某一方向仍然容易滑动。

两者 Moravec CC 值一样(都是 100),但 A 才是稳定的角点。Harris 用两个特征值 λ1,λ2\lambda_1,\lambda_2 联合刻画,把"方向分布均匀性"编码进检测器里——Harris 响应 R=det⁡(M)−k⋅tr(M)2R=\det(M)-k\cdot\mathrm{tr}(M)^2 惩罚"一大一小"的情况;Shi-Tomasi 索性直接取 min⁡(λ1,λ2)\min(\lambda_1,\lambda_2),逻辑上比 Moravec 更精确但保留了对方向分布的敏感。

5. 从 Moravec 到 Harris 的对照​

把两代检测器放在一起:

维度Moravec 1977Harris 1988
变化度量4 方向 SSD结构张量 MM 的特征值
方向刻画离散 4 方向连续(所有方向)
窗函数矩形二值高斯
响应函数min⁡\min 4 方向det⁡M−k tr2M\det M-k\,\mathrm{tr}^2 M
旋转不变否是
计算量4 次 SSD/像素一次梯度 + 2×22\times 2 行列式

Harris 的每一处改进都精确对应 Moravec 的一个缺陷。这不是巧合——Chris Harris 和 Mike Stephens 的论文明确说"our method addresses the drawbacks of Moravec's detector"。理解 Moravec 就理解了 Harris 的动机。

6. 一个数值小例子​

考虑一个理想的 L 形角点,灰度值如下(0=0= 黑,255=255= 白):

  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

在角点 (2,2)(2,2) 位置,用 3×33\times 3 窗做 4 个方向 SSD:

  • (1,0)(1,0) 向右:窗口内几乎不变(右边还是同样的 L),E≈0E\approx 0
  • (0,1)(0,1) 向下:类似,E≈0E\approx 0
  • (1,1)(1,1) 对角:窗口滑到白色内部,EE 变大
  • (1,−1)(1,-1) 反对角:窗口滑到黑色内部,EE 变大

C=min⁡C = \min = 前两个方向的 E≈0E \approx 0——Moravec 把真实角点漏检了。原因?3×33\times 3 窗口太小,向右/向下平移一格时,L 结构自相似,SSD 为零。这类"离散平移让某些方向意外自相似"的情况在实际图像里非常常见。这就是为什么现代实现基本都不再直接用 Moravec,除非当作教学演示。

7. Moravec 的遗产​

尽管有这么多缺陷,Moravec 检测器的历史地位无可动摇。它奠定了几个观念:

  • 角点是局部自相似性的极小点——这个定义一直沿用到 SUSAN 和 FAST
  • "最弱方向决定强度"——min⁡\min 操作在 Shi-Tomasi 里被继承
  • 阈值 + 非极大值抑制——所有稀疏关键点检测器的标准流水线

Moravec 本人后来把重心转向了移动机器人的其它问题(栅格地图、贝叶斯占据推理),但角点检测这条线索被 Harris、Kanade、Shi、Tomasi、Smith、Rosten 一代一代接下来。当你在 OpenCV 里调用 cv::goodFeaturesToTrack,看到出来那一堆整齐的角点,请记得这条路的起点是斯坦福 1977 年那辆一米一停的漫游车。