哈里斯边角侦测

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

概要介绍

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

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

哈里斯边角侦测的发展 [1]

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

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

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

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

所以${\displaystyle f(x,y)}$可以写成

${\displaystyle 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}.}$

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

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

其中${\displaystyle M}$代表结构张量,

${\displaystyle 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}}.}$

哈里斯边角侦测的流程[3][4]

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

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

彩色影像转换成灰阶影像

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

空间微分的计算

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

建构结构张量

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

计算哈里斯响应

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

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

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

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

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

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

非极大值抑制

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

改进的侦测算法[5][6]

1. 哈里斯-拉普拉斯边角侦测^[7]

2. Differential Morphological Decomposition Based Corner Detector^[8]

3. Multi-scale Bilatera Structure Tensor Based Corner Detector^[9]

应用

1. 影像对齐，影像缝合，影像配准^[10]

2. 建立二维马赛克^[11]

3. 三维场景建模及重建^[12]

4. 动作侦测^[13]

5. 物体识别^[14]

6. 基于内容的影像检索^[15]

7. 影片追踪^[16]

更多

• Structure tensor（英语：Structure tensor）
• Harris affine region detector（英语：Harris affine region detector）
• Corner detection
• Feature detection (computer vision)（英语：Feature detection (computer vision)）
• Computer vision
• List of computer vision topics

参考资料

1. Chris Harris and Mike Stephens (1988). "A Combined Corner and Edge Detector". Alvey Vision Conference. 15.
2. Konstantinos G. Derpanis (2004). The harris corner detector. York University.
3. Harris Operator Corner Detection using Sliding Window Method - Google Scholar. scholar.google.com. [2015-11-29].
4. The Comparison and Application of Corner Detection Algorithms - Google Scholar. scholar.google.com. [2015-11-29].
5. Bellavia, F.; Tegolo, D.; Valenti, C. Improving Harris corner selection strategy. IET Computer Vision. 2011-03-01, 5 (2) [2018-07-05]. doi:10.1049/iet-cvi.2009.0127. （原始内容存档于2018-11-27）.
6. Rosten, Edward; Drummond, Tom. Leonardis, Aleš; Bischof, Horst; Pinz, Axel , 编. Machine Learning for High-Speed Corner Detection. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 2006-05-07: 430–443 [2018-07-05]. ISBN 978-3-540-33832-1. doi:10.1007/11744023_34#page-1. （原始内容存档于2020-08-08） （英语）.
7. A Comparison of Affine Region Detectors - Google Scholar. scholar.google.com. [2015-11-29].
8. Gueguen, L.; Pesaresi, M. Multi scale Harris corner detector based on Differential Morphological Decomposition. Pattern Recognition Letters: 1714–1719. [2018-07-05]. doi:10.1016/j.patrec.2011.07.021. （原始内容存档于2017-10-14）.
9. A Multi-scale Bilateral Structure Tensor Based Corner Detector - Google Scholar. scholar.google.com. [2015-11-29].
10. Kang, Juan; Xiao, Chuangbai; Deng, M.; Yu, Jing; Liu, Haifeng. Image registration based on harris corner and mutual information. 2011 International Conference on Electronic and Mechanical Engineering and Information Technology (EMEIT). 2011-08-01, 7: 3434–3437. doi:10.1109/EMEIT.2011.6023066.
11. Underwater Mosaic Creation using Video sequences from Different Altitudes - Google Scholar. scholar.google.com. [2015-12-02].
12. Automated reconstruction of 3D scenes from sequences of images - Google Scholar. scholar.google.com. [2015-12-02].
13. Liu, Meng; Wu, Chengdong; Zhang, Yunzhou. Multi-resolution optical flow tracking algorithm based on multi-scale Harris corner points feature. Control and Decision Conference, 2008. CCDC 2008. Chinese. 2008-07-01: 5287–5291. doi:10.1109/CCDC.2008.4598340.
14. Object Recognition from Local Scale-Invariant Features - Google Scholar. scholar.google.com. [2015-11-29].
15. Salient Points for Content Based Retrieval - Google Scholar. scholar.google.com. [2015-12-02].
16. Tracking and Recognition of Objects using SURF Descriptor and Harris Corner Detection - Google Scholar. scholar.google.com. [2015-12-02].

引用错误：在<references>标签中name属性为“harris2”的参考文献没有在文中使用
引用错误：在<references>标签中name属性为“dey2”的参考文献没有在文中使用
引用错误：在<references>标签中name属性为“derpanis2”的参考文献没有在文中使用

外部链接

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