跳到主要内容

Harris 角点检测:把"角"变成一个矩阵的特征值问题

1988 年 Chris Harris 和 Mike Stephens 在 Alvey Vision Conference 上发了篇只有 6 页的短文《A Combined Corner and Edge Detector》。这篇文章后来成了计算机视觉引用最多的论文之一,不是因为它精巧,而是因为它把一个模糊的直觉——"角点就是往哪个方向移都有明显变化的点"——变成了一个能计算的特征值判别问题。

Harris 之前的 Moravec 角点检测已经有了核心思想:拿一个小窗口在图像上滑,看看窗口内像素平方差 SSD 在八个离散方向上的最小值。哪个点的"最小方向变化"仍然很大,哪个点就是角。但 Moravec 有三个硬伤:只测 8 个方向(各向异性)、二值窗(噪声敏感)、对边缘响应太强。Harris 用一次泰勒展开把这三个问题一次解决。

1. 从 SSD 到自相关矩阵​

考虑图像 I(x,y)I(x,y) 上一个位置 (x,y)(x,y) 处的窗口 WW,把窗口平移 (u,v)(u,v) 一小步,两个窗口的差异用加权平方和度量:

E(u,v)=∑(x,y)∈Ww(x,y) [I(x+u,y+v)−I(x,y)]2E(u,v)=\sum_{(x,y)\in W} w(x,y)\,\bigl[I(x+u,y+v)-I(x,y)\bigr]^2

w(x,y)w(x,y) 是窗函数——Harris 的第一处改进是不再用 Moravec 的方形二值窗,而用一个各向同性的高斯窗,位置偏离中心越远权重越低。

E(u,v)E(u,v) 是关于位移 (u,v)(u,v) 的一个曲面。移动方向敏感的点(角点)会有一个"上翘的碗",边缘方向会有"沿一条槽平坦、垂直方向陡"的马鞍形。直接计算 EE 太贵,Harris 的第二处改进:对 I(x+u,y+v)I(x+u,y+v) 做一阶泰勒展开:

I(x+u,y+v)≈I(x,y)+Ixu+IyvI(x+u,y+v)\approx I(x,y)+I_x u+I_y v

代回去:

E(u,v)≈∑w (Ixu+Iyv)2=[uv]M[uv]E(u,v)\approx \sum w\,(I_x u+I_y v)^2 = \begin{bmatrix}u&v\end{bmatrix} M \begin{bmatrix}u\\v\end{bmatrix}

其中的 2×22\times 2 矩阵是本文的主角,一般叫自相关矩阵、结构张量或者干脆就叫 MM:

M=∑(x,y)∈Ww(x,y)[Ix2IxIyIxIyIy2]M = \sum_{(x,y)\in W} w(x,y)\begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix}

Ix,IyI_x, I_y 是图像在该位置的一阶梯度,通常用 Sobel 算子 算。MM 的每一项都是"梯度乘积的高斯加权和"——工程实现上就是三张图(Ix2I_x^2、Iy2I_y^2、IxIyI_x I_y)分别做高斯滤波,然后逐像素组装。

这个变换的意义远比它看上去大:局部窗口内所有梯度的二阶统计被压缩成一个 2×22\times 2 矩阵,MM 是关于点 (x,y)(x,y) 的局部形状描述。

2. 特征值告诉你窗口里长什么样​

MM 是对称正半定的,两个特征值 λ1≥λ2≥0\lambda_1\ge\lambda_2\ge 0 有明确几何含义。因为 E(u,v)≈[u,v]M[u,v]TE(u,v)\approx [u,v]M[u,v]^T 定义了一个椭圆等高线,λ1,λ2\lambda_1, \lambda_2 就是椭圆的两个半轴长度的倒数平方。或者更直觉地:沿两个主方向移动窗口时 SSD 增长率的度量。

情况 A:平坦区域
λ1 ≈ 0, λ2 ≈ 0
往任何方向动都没变化 → 圆形小碗底

等高线:
─────
─ ─
─ ─ ← 几乎是平的
─ ─
─────

情况 B:边缘
λ1 >> λ2 ≈ 0
沿边缘方向动没变化,垂直方向大变化 → 长椭圆

等高线:
┌─────────────┐
│ │ ← 沿边缘方向 SSD 增长慢
│ │
└─────────────┘

情况 C:角点
λ1 ≥ λ2 >> 0
任何方向动都有变化 → 短粗椭圆或圆

等高线:
●●●
●●●●●
●●●

问题变成:判断两个特征值是否都足够大。

3. 响应函数 RR:为什么不直接算特征值​

直接算 λ1,λ2\lambda_1, \lambda_2 需要开根号(2×22\times 2 的特征多项式是 λ2−tr(M)λ+det⁡(M)=0\lambda^2-\text{tr}(M)\lambda+\det(M)=0,闭式解含 ⋅\sqrt{\cdot}),1988 年的硬件上每像素算一次开方并不便宜。Harris 定义了一个代理响应函数避开开方:

R=det⁡(M)−k (tr(M))2=λ1λ2−k(λ1+λ2)2R = \det(M) - k\,\bigl(\text{tr}(M)\bigr)^2 = \lambda_1\lambda_2 - k(\lambda_1+\lambda_2)^2

kk 是经验参数,通常取 0.04∼0.060.04\sim 0.06。

RR 的行为:

情况λ1,λ2\lambda_1,\lambda_2det⁡\dettr\text{tr}RR
平坦都小极小小≈0\approx 0
边缘一大一小小大大的负值
角点都大大大大的正值

阈值一分:R>TR>T 的点是候选角点,R<−TR<-T 的是边缘点,∣R∣|R| 小的是平坦区。同一个函数把角、边、面三分——原文标题里"combined corner and edge detector"就是这个意思。

kk 的直觉:R=λ1λ2−k(λ1+λ2)2R=\lambda_1\lambda_2-k(\lambda_1+\lambda_2)^2,令 α=λ1/λ2≥1\alpha=\lambda_1/\lambda_2\ge 1,则 R=λ22[α−k(1+α)2]R=\lambda_2^2[\alpha-k(1+\alpha)^2],R>0R>0 要求 α<1−2k+1−4k2k\alpha < \frac{1-2k+\sqrt{1-4k}}{2k}。k=0.04k=0.04 对应 α≲23\alpha \lesssim 23——意思是允许两个特征值差 23 倍以内都算角点。kk 越小对边缘越宽松(越多假角),kk 越大要求越圆钝的角。所以 kk 不是无关紧要的旋钮,它决定了"多长的椭圆还算角点"。

4. 窗函数选择:矩形 vs. 高斯​

原论文写得很清楚:矩形窗会让 RR 图产生阶梯状振铃(窗内某个强梯度突然进入/离开)。高斯窗把权重连续化,RR 图变得平滑,非极大值抑制才有可能可靠定位。

工程上高斯 σ\sigma 通常取 1 到 2 像素,窗口尺寸 6σ+16\sigma+1。σ\sigma 越大越抗噪声但角点定位越糊。这里已经隐含了 Harris 的一个基本假设:在选定的尺度下检测——它不知道自己在哪个尺度看角点。这也是后来 Lowe 做 SIFT 时必须解决的问题。

5. 非极大值抑制和亚像素定位​

阈值筛完后 RR 图上通常一个真角周围会有一堆高响应像素。要挑出代表点:

  1. 对每个候选像素 (x,y)(x,y),检查它是否在 3×33\times 3(或 5×55\times 5)邻域内是 RR 的最大值
  2. 是则保留,不是则丢弃

这一步和 Canny 里的 NMS 思路完全一样,只是 Canny 沿梯度方向搜索,Harris 是二维局部极大。

保留下来的点还只是像素级,很多任务(相机标定、SfM)需要更精确。做法是把 RR 图在极大点附近做二次曲面拟合,解方程得到亚像素坐标——这就进入了亚像素级角点检测的范畴。OpenCV 的 cornerSubPix 就是这么干的。

6. Harris 的不变性:什么变、什么不变​

评价一个特征检测子的语言是协变性/不变性:

变换Harris 表现
图像旋转不变(MM 的特征值不变,只有特征向量转)
灰度加常数不变(梯度不变)
灰度乘常数响应等比缩放,阈值需要重设
图像平移协变(角点位置也平移)
图像缩放不不变——尺度变了梯度大小和角点定义都变
仿射变换部分不变(仿射时特征值椭圆会拉伸,RR 不稳定)

尺度不变性的缺失是 Harris 最大的短板。远处的建筑物角在原图上是"角",放大 4 倍后同一个位置可能变成一段弧线——Harris 找不到它了。这直接推动了 90 年代末到 00 年代初的"多尺度特征"研究,SIFT、SURF、Harris-Laplace 都是围绕这个问题展开的。

7. 参考实现​

伪代码把上面的东西串起来:

def harris(I, sigma=1.0, k=0.04, thresh=0.01):
# 1. 梯度
Ix = sobel_x(I)
Iy = sobel_y(I)
# 2. 梯度乘积
Ixx, Iyy, Ixy = Ix*Ix, Iy*Iy, Ix*Iy
# 3. 高斯加权 → M 的三个独立分量
Sxx = gaussian_blur(Ixx, sigma)
Syy = gaussian_blur(Iyy, sigma)
Sxy = gaussian_blur(Ixy, sigma)
# 4. 响应函数
det_M = Sxx*Syy - Sxy*Sxy
tr_M = Sxx + Syy
R = det_M - k*tr_M*tr_M
# 5. 阈值 + NMS
R[R < thresh*R.max()] = 0
corners = non_max_suppression(R, size=3)
return corners

cv2.cornerHarris(img, blockSize=2, ksize=3, k=0.04) 里 blockSize 是高斯窗尺寸,ksize 是 Sobel 核大小,k 就是上面的 kk。

8. 局限与后继​

Harris 的三大问题:

  1. 无尺度选择:远近拍同一场景,检测到的角点集合不重合
  2. kk 是经验参数:不同图像最优 kk 不同,缺乏统一标准
  3. 对强纹理响应过高:布纹、草地这种"到处都是梯度"的区域会满屏假角

1994 年 Shi 和 Tomasi 从工程实用角度改了第 2 点——直接用 min⁡(λ1,λ2)\min(\lambda_1,\lambda_2) 代替 RR,去掉 kk。1998 年 Smith 提出的 SUSAN 换了完全不同的路子,不再基于梯度。2006 年 Rosten 的 FAST 追求极致速度,用像素强度比较代替浮点数矩阵运算。Harris 本身仍然是所有这些方法的祖先和基准。

9. 一个容易忽视的洞察​

Harris 论文里最有价值的东西其实不是响应函数 RR,而是用一阶泰勒展开把"局部图像结构"压缩成一个 2×22\times 2 矩阵这个动作。这个矩阵后来被叫做结构张量(structure tensor),出现在光流估计(Lucas-Kanade)、纹理分析、图像分割、各向异性扩散、GAN 局部拟合……几乎所有需要"局部方向性"信息的地方。

换句话说,Harris 真正的贡献是给出了一个通用工具——把一个像素邻域的信息浓缩成一个小矩阵,然后用矩阵代数(特征值、行列式、迹)回答问题。角点检测只是这个工具的一个具体应用。理解了结构张量,理解 Shi-Tomasi、KLT 追踪、甚至 SIFT 的 DoG 极值定位都会顺很多。