哈里斯边角侦测

哈里斯边角侦测(Harris Corner Detector)是被广泛运用在电脑视觉的算法，主要是用于从影像中找出代表边角的特征点。最早是由Chris Harris 和Mike Stephens在1988年所提出，在当时是莫拉维克边角侦测器的改进版本。与 莫拉维克边角侦测器相比，不是对局部小块区域作45度角移动，而是考量了方向性值直接算出边角的微分值，这个方法在当时已被证明可以更准确地去分辨出边角。自从哈里斯边角侦测器被提出后，后续有很多算法试着去改良它，而这类的算法也在很多影像处理的应用上被采用作为前处理。

概要介绍

角落的概念就是它相邻的区域有两条截然不同方向的边，换句话说，角落也是两条边的接点，而这条边的附近有剧烈的亮度变化。边角是影像重要的特征，基本上边角的特性不会受到旋转、平移以及影像亮度的影响。虽然边角只是一张影像中的一小部分，但是通常却代表着一张影像中最重要的特征，因为它们的资讯相较于整张影像，富有代表性且可以被应用在影像接合，动作追踪，建立二维马赛克，立体视觉，以及相关的电脑视觉领域。

为了找出影像中的边角，科学家们提出了很多不同种的边角测试器包含Kanade-Lucas-Tomasi (KLT) 算子，哈里斯算子是其中最简单，有效，及可信赖的方法。这两种受欢迎的方法均是以局部结构矩阵来当作基础，相较于Kanade-Lucas-Tomasi (KLT)边角侦测，就算影像经过旋转或者是亮度的调整，哈里斯边角侦测具有良好的结果重现性，因此，它更被常使用在立体匹配及影像数据库检索。虽然仍有不少的缺点及限制，哈里斯边角侦测依然在电脑视觉的应用中是相当重要且基础的技术。

哈里斯边角侦测的发展

在不失去一般性的状况下，我们假设使用的是一张二维的灰阶影像。在这里以$I$代表这张影像，假设我们现在针对一小块局度区域$(x,y)\in W$移动了$(\Delta x,\Delta y)$，以$f$代表这两块小区域的加总平方差(SSD)，可以写作

$f(\Delta x,\Delta y)={\underset {(x,y)\in W}{\sum }}\left(I(x,y)-I(x+\Delta x,y+\Delta y)\right)^{2}.$

$I(x+\Delta x,y+\Delta y)$ 可以用泰勒展开去近似，以$I_{x}$和$I_{y}$分别代表$I$在$x$和$y$方向的偏微分，于是可以近似成

$I(x+\Delta x,y+\Delta y)\approx I(x,y)+I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y,$

所以$f(x,y)$可以写成

$f(\Delta x,\Delta y)\approx {\underset {(x,y)\in W}{\sum }}\left(I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y\right)^{2}.$

如果以矩阵的形式来表达,

$f(\Delta x,\Delta y)\approx {\begin{pmatrix}\Delta x&\Delta y\end{pmatrix}}M{\begin{pmatrix}\Delta x\\\Delta y\end{pmatrix}},$

其中$M$代表结构张量,

$M={\underset {(x,y)\in W}{\sum }}{\begin{bmatrix}I_{x}^{2}&I_{x}I_{y}\\I_{x}I_{y}&I_{y}^{2}\end{bmatrix}}={\begin{bmatrix}{\underset {(x,y)\in W}{\sum }}I_{x}^{2}&{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}\\{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}&{\underset {(x,y)\in W}{\sum }}I_{y}^{2}\end{bmatrix}}.$

哈里斯边角侦测的流程

一般而言，哈里斯边角侦测算法可以分成下列几个步骤:

1. 彩色影像转换成灰阶影像
2. 空间微分的计算
3. 建构结构张量
4. 计算哈里斯响应
5. 非极大值抑制

彩色影像转换成灰阶影像

如果输入是一张彩色影像，第一步便是转换成灰阶影像，可以加快处理速度

空间微分的计算

第二步是计算整张图的$I_{x}(x,y),I_{y}(x,y)$ 。

建构结构张量

有了$I_{x}(x,y),I_{y}(x,y)$的资讯后，我们便可以建构结构张量$M$。

计算哈里斯响应

在这一步，我们会运用下列的近似的式子来计算结构张量矩阵的最小的特征值:

$\lambda _{min}\approx {\frac {\lambda _{1}\lambda _{2}}{(\lambda _{1}+\lambda _{2})}}={\frac {det(M)}{trace(M)}}$

$trace(M)=m_{11}+m_{22}$

另外一种常见的哈里斯响应是

$R=det(M)-k(trace(M))^{2}=\lambda _{1}\lambda _{2}-k(\lambda _{1}+\lambda _{2})^{2}$

而k是一个由经验所订出来的常数，$k\in [0.04,0.06]$。

非极大值抑制

由于只靠前面的步骤选出的特征点很可能会在一小块区域有很多个，我们希望能在局部区域选出值最大的，因此会设定各个拥有局部最大值的特征点的距离不能太接近，如此便可以有效选出比较分散在整张图的特征点。

改进的侦测算法

1. 哈里斯-拉普拉斯边角侦测

2. Differential Morphological Decomposition Based Corner Detector

3. Multi-scale Bilatera Structure Tensor Based Corner Detector

应用

1. 影像对齐，影像缝合，影像配准

2. 建立二维马赛克

3. 三维场景建模及重建

4. 动作侦测

5. 物体识别

6. 基于内容的影像检索

7. 影片追踪

更多

• Structure tensor
• Harris affine region detector
• Corner detection
• Feature detection (computer vision)
• Computer vision
• List of computer vision topics

外部链接

• "Learn OpenCV by Examples : Harris Corner Detection"（页面存档备份，存于互联网档案馆）
• "Harris Corner Detection - OpenCV Documentation"（页面存档备份，存于互联网档案馆）
• "Harris Corner Detection - OpenCV-Python Tutorials"（页面存档备份，存于互联网档案馆）