﻿ 角点检测技术综述
 计算机系统应用  2020, Vol. 29 Issue (1): 22-28 PDF

Review on Image Corner Detection
ZHU Si-Cong, ZHOU De-Long
College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China
Abstract: Corner detection is a basic subject in the field of machine vision and computer vision. Corner detection is sometimes called interest point. It not only simplifies the image information data, but also retains the more important feature information of the image to a certain extent. Corner detection includes three-dimensional scene reconstruction, motion estimation, visual tracking, image registration, and image matching. Computer vision has been widely used in the field of computer vision. This study classifies and describes the existing corner detection methods, which are mainly divided into gray-level intensity-based methods and edge contour-based methods. The other types of corner detection methods are also summarized, providing references for image corner detection technology.
Key words: corner detection     feature extraction     feature description     image processing

1 角点检测算法现状分析

1.1 基于灰度图像的角点检测

1.1.1 Moravec角点检测技术

1977年, Moravec[4]提出了Moravec角点检测算子, 其基本思想是通过在图像上移动一个二值矩形窗口来查找最小灰度值变化的最大值. 这种方法的缺点是响应值非各向同性, 对噪声和边缘敏感, 对旋转不具备不变形. Moravec算子作为第一个被广泛使用的角点检测算法, 开创了角点检测的新时代.

1.1.2 Harris角点检测技术及相关改进方法

 $R = ({\lambda _1}{\lambda _2}) - k{({\lambda _1} + {\lambda _2})^2} = \left| M \right| - k \cdot t{r^2}(M)\;$ (1)

1.1.3 基于SUSAN的角点检测技术

 $c(\mathop r\limits^ \rightharpoonup,\mathop {r_0}\limits^ \rightharpoonup) = \left\{ \begin{array}{l} 1\;\;\;{\rm{ if}}\left| {I(\mathop r\limits^ \rightharpoonup) - I(\mathop {r_0}\limits^ \rightharpoonup)} \right| \le t\\ 0\;\;\;{\rm{ if}}\left| {I(\mathop r\limits^ \rightharpoonup) - I(\mathop {r_0}\limits^ \rightharpoonup)} \right| > t \end{array} \right.$ (2)

 $R({r_0}) = \left\{ {\begin{array}{*{20}{c}} {g - n({r_0})}&{n({r_0}) < g}\\ 0&{n({r_0}) < g} \end{array}} \right.$ (3)

 $\;{\rm{ }}n({r_0}) = \sum\limits_{reD({r_0})} {c(r,{r_0})}$ (4)

1.1.4 FAST角点检测技术

1998年Trajkovic和Hedley[12]提出了一种快速角点检测算子, 其基本思想是研究在某点邻域内通过该点的任意一条直线上的灰度变化情况. 首先计算出水平和垂直方向灰度变化值, 然后构建一个角点度量函数来判断角点. 2006年Rosten和Drummond[13]提出了高速角点检测算子, 其基本思想是利用机器学习来加速角点检测过程. 上述两种算法也都对图像尺度变化敏感. 近年来, 针对当前FAST角点检测算法只能检测单一类型的角点, 并且单一阈值作用于整幅图像很难取得理想的效果等问题, Park等人[14]为了解决可穿戴设备的图像分辨率与系统功耗之间存在权衡这一问题, 提出了一种新的快速角点检测方法, 它在计算性能和可重复性方面优于以前的算法.

1.2 基于轮廓曲线的角点检测

1.2.1 基于Freeman链码的角点检测技术

2014年, 曾接贤等人[16]提出了一种曲率尺度空间与链码方向统计相结合的角点检测方法. 2017年, Rachmawati等人[17]提出了一种将高速角点检测与Freeman链码相结合的多边形逼近技术. 该方法利用一组图像角点构造了一串有序线段的近似多边形, 该近似多边形可以进一步用于形状表示和分析领域, 作为数字图像的轮廓描述. 2018年, 刘相湖等人[18]提出了一种对Freeman链码分析的角点检测算法, 该方法对Freeman链码发生变化时, 通过分析其连续前后多个点的链码是否符合一定的规则来判定角点.

1.2.2 基于CSS的角点检测算法

Mokhtarian等人[19]提出了曲率尺度空间(Curvature-Scale-Space, CSS)的角点检测器, 不同角度下的局部曲率被用于角点检测, 角度下追踪角点并改善定位准确性. CSS角点检测算法对轮廓的局部变化和噪声高度敏感而且很难选择合适的高斯尺度平滑轮廓和角点阈值. Zhong等人[20]提出了直接曲率尺度空间(DCSS), 方法是将平面曲线的曲率与高斯核直接转换而产生的CSS. 他们从理论上分析了DCSS在平面曲线拐角检测中的应用. 研究了孤立的单角和双角模型的尺度空间行为, 定义了若干模型属性, 使DCSS图像能够转化为树型组织, 从而能够在多尺度意义上进行角点检测. 2016年, 李伟生等人[21]提出了一种基于曲率多尺度的自适应角点检测算法AMCP (Adaptive Multi-scale Curvature Polynomial), 该算法结合了尺度多项式的方法, 并构造局部曲率显著度LCCS (Local Corners Curvature Saliency), 从而用自适应的阈值代替全局阈值, 极大地增强了算法应对尺度, 旋转等变化的鲁棒性.

1.2.3 利用弦到点的距离累加的角点检测算法

2008年, Awrangjeb等人[22]提出了利用弦到点的距离累加(CPDA)的角点检测算法, 该方法在对图像中的角点进行定位的同时产生最小的定位误差, 该算法有效的避免了CSS算法中存在的主要问题, 却存在着以下问题: 一是邻近角点被合并, 二是钝形角点被误删除, 三是无法有效剔除圆形角点. 2014年, Jin等人[23]针对基于弦对点距离积累、定位精度低、检测时间复杂度高等缺点, 采用先得到单尺度下的候选角点, 保持相邻角点, 然后计算了多尺度下候选角的特征值, 有效地消除了伪角. 2017年, Hossain等人[24]提出了一种基于CPDA改进的角点检测算法CADT. 该方法的预处理和改进步骤与CPDA相似, 但是有效的减少了定位误差和提高了平均重复性, 降低了角点的伪检率.

1.2.4 基于角度(Angle)的角点检测算法

1.2.5 多尺度Gabor滤波器的角点检测

2004年, Gao等人[27]提出的基于Gabor小波的角点检测算子. 多尺度Gabor滤波器的角点检测算法克服了在不同图像上的尺度选择问题. 该算法首先对图像进行边缘轮廓的提取, 进而用一组构建好的4个尺度8个方向Gabor滤波器的虚部对图像进行平滑处理, 并计算每个像素在其相同尺度下各个方向上Gabor滤波器虚部响应的归一化的和. 最后将每个边缘像素点在所有尺度下的乘积作为新的角点测度, 当角点测度大于预设阈值时, 则认定该点为角点. 2014年, Zhang等人[28]研究提出了一种基于轮廓的角点检测器, 该检测方法利用Gabor滤波器虚部在轮廓上的幅值响应. 与传统的通过分析边缘轮廓形状和搜索平面曲线上的局部曲率极大值来检测角点的方法不同, 该角点检测器结合了边缘轮廓的像素及其相应的灰度变化信息. 2016年, 田子怡等人[29]也提出了提出了一种基于边缘轮廓线的多尺度Gabor滤波器的角点检测算法. 2017年, 高华[30]提出了一个既利用到图像边缘轮廓信息又利用到图像灰度信息的基于Log-Gabor梯度方向一致性的角点检测算法, 以提高角点检测器的检测性能.

1.3 其他的角点检测技术

2 角点检测算法的测评技术

 $R = (1/2) \times {N_r} \times (1/{N_c} + 1/{N_m})$ (5)

 $E = \sqrt {\left( {1/{N_r}} \right) \times \sum\limits_{i = 1}^{{N_r}} {\left[ {{{(x_o^i - x_t^i)}^2} + {{\left( {y_o^i - y_t^i} \right)}^2}} \right]} }$ (6)

 图 1 角点重复率示意图

 图 2 角点定位误差示意图

 图 3 角点较少图像的检测示例

 图 4 角点较多图像的检测示例

3 角点检测算法的实际应用

4 结论与展望

 [1] Lebeda K, Hadfield S, Matas J, et al. Texture-independent long-term tracking using virtual corners. IEEE Transactions on Image Processing, 2016, 25(1): 359-371. DOI:10.1109/TIP.2015.2497141 [2] 刘阳成, 朱枫. 一种新的棋盘格图像角点检测算法. 中国图象图形学报, 2006, 11(5): 656-660. DOI:10.3969/j.issn.1006-8961.2006.05.008 [3] 章为川, 孔祥楠, 宋文. 图像的角点检测研究综述. 电子学报, 2015, 43(11): 2315-2321. DOI:10.3969/j.issn.0372-2112.2015.11.026 [4] Morevec HP. Towards automatic visual obstacle avoidance. Proceedings of the 5th International Joint Conference on Artificial Intelligence - Volume 2. Cambridge, UK. 1977. 584. [5] Harris C, Stephens M. A combined corner and edge detector. Proceedings of the 4th Alvey Vision Conference. Alvey, UK. 1988. 147–151. [6] Qiao YJ, Tang YC, Li JS. Improved Harris sub-pixel corner detection algorithm for chessboard image. Proceedings of the 2013 2nd International Conference on Measurement, Information and Control. Harbin, China. 2013: 1408–1411. [7] 卢伟家, 刘缠牢. 一种基于Harris特征点检测的改进算法. 仪表技术与传感器, 2017(12): 98-100, 104. DOI:10.3969/j.issn.1002-1841.2017.12.024 [8] Wang ZC, Li R, Shao ZH, et al. Adaptive Harris corner detection algorithm based on iterative threshold. Modern Physics Letters B, 2017, 31(15): 1750181. DOI:10.1142/S0217984917501810 [9] Smith SM, Brady JM. SUSAN—a new approach to low level image processing. International Journal of Computer Vision, 1997, 23(1): 45-78. DOI:10.1023/A:1007963824710 [10] He LY, Zhou XY. An auto-adaptive threshold pre-detection SUSAN corner detection Algorithm. Proceedings of the 2013 5th International Conference on Intelligent Human-Machine Systems and Cybernetics. Hangzhou, China. 2013. 511–514. [11] 王冠群, 马苗, 张艳宁, 等. 基于高斯变换的多尺度SUSAN角点检测方法. 计算机工程与应用, 2016, 52(12): 184-188. DOI:10.3778/j.issn.1002-8331.1407-0527 [12] Trajkovic M, Hedley M. Fast corner detection. Image and Vision Computing, 1988, 16(2): 75-87. [13] Rosten E, Drummond T. Machine learning for high-speed corner detection. Proceedings of the 9th European Conference on Computer Vision. Graz, Austria. 2006. 430–443. [14] Park S, Kim G, Park J, et al. A 1. 5nJ/pixel super-resolution enhanced FAST corner detection processor for high accuracy AR. Proceedings of the ESSCIRC 2014—40th European Solid State Circuits Conference. Venice Lido, Italy. 2014. 191–194. [15] 赵亚利, 章为川, 李云红. 图像边缘轮廓自适应阈值的角点检测算法. 中国图象图形学报, 2016, 21(11): 1502-1514. DOI:10.11834/jig.20161110 [16] 曾接贤, 李炜烨. 曲率尺度空间与链码方向统计的角点检测. 中国图象图形学报, 2014, 19(2): 234-242. [17] Rachmawati E, Supriana I, Khodra ML, et al. FAST corner detection in polygonal approximation of shape. Proceedings of the 2017 3rd International Conference on Science in Information Technology. Bandung, Indonesia. 2017. 166–170. [18] 刘相湖, 王涛, 张小哲. 对Freeman链码分析的角点检测算法. 计算机系统应用, 2018, 27(4): 202-208. DOI:10.15888/j.cnki.csa.006314 [19] Mokhtarian F, Suomela R. Robust image corner detection through curvature scale space. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998, 20(12): 1376-1381. DOI:10.1109/34.735812 [20] Zhong BJ, Liao WH. Direct curvature scale space: Theory and corner detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(3): 508-512. DOI:10.1109/TPAMI.2007.50 [21] 李伟生, 李泽亚. 一种改进的多尺度自适应角点检测方法. 计算机应用与软件, 2016, 33(1): 185-189. DOI:10.3969/j.issn.1000-386x.2016.01.047 [22] Awrangjeb M, Lu GJ. Robust image corner detection based on the chord-to-point distance accumulation technique. IEEE Transactions on Multimedia, 2008, 10(6): 1059-1072. DOI:10.1109/TMM.2008.2001384 [23] Jin YT, Wang WL, Zhao YW, et al. Fast corner detector based on chord-to-point distance accumulation. Computer Science, 2014, 41(4): 306-308, 313. [24] Hossain MA, Tushar AK. Chord Angle Deviation using Tangent (CADT), an efficient and robust contour-based corner detector. Proceedings of IEEE International Conference on Imaging, Vision & Pattern Recognition. Dhaka, Bangladesh. 2017. 1–6. [25] Sadat RMN, Sayeeda Z, Salehin MM, et al. A corner detection method using angle accumulation. Proceedings of the 14th International Conference on Computer and Information Technology. Dhaka, Bangladesh. 2011. 95–99. [26] 金亦挺, 王万良, 赵燕伟, 等. 基于角度累加的鲁棒角点检测算法. 计算机辅助设计与图形学学报, 2017, 29(11): 2005-2014. DOI:10.3969/j.issn.1003-9775.2017.11.006 [27] Gao X, Sattar F, Venkateswarlu R. Corner detection of gray level images using gabor wavelets. Proceedings of 2004 International Conference on Image Processing. Singapore, Singapore. 2004. 2669–2672. [28] Zhang WC, Wang FP, Zhu L, et al. Corner detection using Gabor filters. IET Image Processing, 2014, 8(11): 639-646. DOI:10.1049/iet-ipr.2013.0641 [29] 田子怡, 李云红. 基于多尺度Gabor滤波器的角点检测. 国外电子测量技术, 2016, 35(7): 75-79, 84. DOI:10.3969/j.issn.1002-8978.2016.07.019 [30] 高华. Log-Gabor梯度方向下的角点检测. 中国图象图形学报, 2017, 22(6): 797-806. [31] He AX, Yung NHC. Corner detector based on global and local curvature properties. Optical Engineering, 2008, 47(5): 057008. DOI:10.1117/1.2931681 [32] 刘文进, 张蕾, 孙劲光. 近邻传播聚类优化的角点检测改进算法. 计算机工程与应用, 2016, 52(9): 219-222. DOI:10.3778/j.issn.1002-8331.1405-0303 [33] 孔祥楠, 卫建华, 赵强, 等. 基于各向异性高斯核的角点检测. 电子测量技术, 2015, 38(8): 69-72. DOI:10.3969/j.issn.1002-7300.2015.08.016 [34] Xing YX, Zhang DY, Zhao JH, et al. Robust fast corner detector based on filled circle and outer ring mask. IET Image Processing, 2016, 10(4): 314-324. DOI:10.1049/iet-ipr.2014.0952 [35] Cho W, Park S, D’Avy J, et al. New corner detector using non-cornerness measure. Proceedings of IEEE International Conference on Consumer Electronics-Asia. Seoul, Repulic of Korea. 2016. 1–2. [36] Rockett PI. Performance assessment of feature detection algorithms: A methodology and case study on corner detectors. IEEE Transactions on Image Processing, 2003, 12(12): 1668-1676. DOI:10.1109/TIP.2003.818041 [37] Awrangjeb M, Lu GJ, Murshed M. An affine resilient curvature scale-space corner detector. Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing. Honolulu, HI, USA. 2007. I-1233–I-1236. [38] 洪磊, 嵇保健, 凌超. 一种棋盘格靶标不完整角点识别的修正算法. 计算机辅助设计与图形学学报, 2016, 28(9): 1521-1526. DOI:10.3969/j.issn.1003-9775.2016.09.015 [39] Lin XY, Zhu C, Zhang Q, et al. Geometric mesh corner detection using triangle principle. Electronics Letters, 2017, 53(20): 1354-1356. DOI:10.1049/el.2017.1353 [40] 谢志峰, 吴佳萍, 章曙涵, 等. 基于深度神经网络的烟码智能识别方法. 计算机辅助设计与图形学学报, 2019, 31(1): 111-117. [41] Li YS, Xu JJ, Xia RJ, et al. Extreme-constrained spatial-spectral corner detector for image-level hyperspectral image classification. Pattern Recognition Letters, 2018, 109: 110-119. DOI:10.1016/j.patrec.2018.03.022 [42] Wang LF, Zhao YN, Qin PL, et al. Fast Corner detection based on ORB and GroupSAC in complex scenes video image. Science Technology and Engineering, 2017, 17(2): 88-94. [43] 刘妍, 余淮, 杨文, 等. 利用SAR-FAST角点检测的合成孔径雷达图像配准方法. 电子与信息学报, 2017, 39(2): 430-436.