Survey of Corner Detection Algorithms
FAN Na, YU Li, and XU Bo-xia (The 8357 Research Institute of the Third Research Academy of CASIC Tianjin 300308) Abstract ： As a more important feature of image, corner contains voluminous information of image features. In the domain of computer vision, such as three-dimensional reconstruction, motion estimation, object tracking, image registration and image matching, corner of image play an important role.this paper attempt to summarize and detailedly introduce corner detection algorithms, and summarize the developments of these algorithms in recent years. Key words: Feature Information；Computer Vision；Corner Detection 1 引言 角点并没有明确的定义，一般将图像中 亮度变化剧烈的点或图像边缘上曲率取极 大值的点认为是角点。从形态上来说，角点 包括L、T、Y、X和箭头型角点等。角点作 为图像的重要特征， 保留了图像的绝大部分 的特征信息，又有效地减少了信息的数据 量， 从而有效地提高了运算速度以及匹配的 可靠性。 总结现有的角点检测算子的评价方 法，总体上有以下几个标准[1]： (1)稳定性：即同一场景图像在亮度、 对比度等因素变化的情况下， 检测出的角点 数目及位置应当稳定 (2)可靠性：即在算子的可变参数改变 情况下，不影响生成的角点的质量，只改变 检测出角点的数目；检测到的角点具有平 移、旋转、伸缩不变性 (3)鲁棒性：即算法的抗噪性能，在一 定的噪声干扰下， 算子仍然具有很强的角点 检测能力 (4)准确性：主要指不发生误检测以及 角点位置定位准确 (5)高效性： 是指算法的计算速度快慢， 算法速度必须足够快以满足图像处理系统 的要求 经过几十年的研究与探索，产生了许多 检测角点的方法，但大致可以分为四类：基 于灰度图像的角点检测算法、 基于二值图像 的角点检测算法、 基于边缘特征的角点检测 算法以及支持矢量机角点检测算法。 本文中
角点检测算法综述
范娜，俞利，徐伯夏 （中国航天科工集团第三研究院 8357 所 天津 300308）
摘要：角点作为图像的一个重要特征，它保留了图像绝大部分的特征信息。角点在三维场景 重建、运动估计、目标跟踪以及图像配准与图像匹配等计算机视觉领域有着重要的作用。本 文对角点检测算法的类别进行总结， 对各类算法进行了详细介绍， 并对近几年来各类算法发 展与改进进行了总结。 关键词：特征信息；计算机视觉；角点检测
对上述四类方法进行了阐述， 并详细的介绍 了这四类方法中典型的具有代表性的角点 检测算法。 2 角点检测算法研究现状 2.1 基于灰度图像的角点检测 2.1.1 Harris 角点检测算法 Harris 角 点 检 测 算 法 是 C.Harris 和 M.J.Stephens 于 1988 年提出的一种基于信 号特征提取算子， 它是对 Moravec 角点检测 算法的改进。Harris 算子利用角点与自相关 函数的曲率特性有关这一特点， 定义自相关 函数， 自相关函数描述了局部图像灰度的变 化程度，可表示为：
利用泰勒公式将上式展开，化简上式可得：
E ( X , Y ) wu ,v [uX vY ]
u,v
X2 wu ,v (u, v) u ,v XY
XY (u, v)T 2 Y
其中 wu ,v 为高斯窗口在 (u , v ) 处的系数，
f f ， Y ， X 、Y 是一阶方向微 X x x
算；最后利用文献中提出的算子求出凹角 点。将原图和补图获得的角点进行异或操 作，得到全部角点。二值图像处于灰度和边 缘轮廓图像的中间步骤， 所以专门针对此类 图像的角点检测方法并不多见。 2.3 基于边缘特征的角点检测方法 2.3.1 基于边缘链码的角点检测 基于边缘链码的角点检测算法是在 20 世纪七十年代末 Freeman H 等人提出的， 是 最早的基于边缘的角点检测算法。 该算法是 沿着数字曲线或边界像素以 8 或 4 邻接的方 式移动，对每一个移动方向进行数字编码； 然后根据相邻码值之间的差别确定角点和 可疑角点。对于可疑角点，通过曲率大小进 一步判断是否为真正的角点。 20 世纪九十年 代， Bribiesca 对 Freeman 链码进行了两次改 进： 用小直线段的斜率对其进行编码以及顶 点链码的方式。 顶点链码中的每个码的码值 表示该码元有几个顶点是区域边界的顶点。 基于边界链码的角点检测方法主要包 括图像预分割、 对预分割后得到的图像的边 界轮廓进行顺序编码和根据边缘轮廓链码 对图像中的角点进行提取三个步骤[9]。 2.3.2 基于小波变换的角点检测 基于小波变换的角点检测方法的思想 是：首先用边缘检测算子提取目标边缘，选 取具有极大值检测能力的小波， 在多个尺度 下进行小波变换， 求取小波系数的模极大值 点得到角点的候选点集； 然后使用一定的筛 选规则，选出正确的角点集。文献[10]基于 协方差矩阵和小波变换来提取角点， 该方法 中利用协方差矩阵来构建方向角函数； 然后 对该方向角函数在不同尺度下进行小波变 换，最终根据小波变换的响应值确定角点。
分， 反映了图像中每个像素点的灰度变化方 向。 定义 M 为像素点 ( x, y ) 的自相关矩阵，
2 则M X XY XY ，为了避免矩阵 M 进行 Y2
特征值分解，方便运算，则将角点响应函数 表示为：
R ( x, y ) det M ( x, y ) k tr M ห้องสมุดไป่ตู้ x, y )
E ( x, y )
w
u ,v
u ,v
f ( x u , y v ) f (u , v )
2
双掩膜来定义进行非极大值抑制的局部范 围， 然后结合 K 均值聚类方法进行非极大值 抑制， 最终通过像素点的角点响应函数是否 满足预设角点判定条件来确定角点。 2.1.2 SUSAN 角点检测算法 SUSAN 角点检测算法是 1997 年由英 国牛津大学的 S.M.Smith 和 J.M.Brady 提出 的一种低层次图像处理小核值相似区的方 法。 该方法的原理是定义一个圆形模板对图 像中的像素进行覆盖， 将圆形模板的中心像 素（定义其为‘核’）与同一模板中的其他 像素分别进行灰度值的比较， 当灰度值之差 少于某一设定阈值 t 时，认为该像素与核具 有相同或相似的灰度值并把由这些像素组 成 的 区 域 定 义 为 核 值 相 似 区 (Univalue Segment Assimilating Nucleus ， USAN) 。当 圆形模板处于图像背景或图像内部时， USAN 区域的面积最大； 当模板开始与图像 边缘重叠时，USAN 区域的面积变小，当模 板的中心像素位于角点处时， USAN 区域面
2.3.3 基于曲率尺度空间的角点检测 在 Witkin 和 Koenderink 提出的尺度空 间的图像分析理论的基础上，Mokhtarian 及 Suomela 提 出 了 基 于 曲 率 尺 度 空 间 （Curvature Scale Space，CSS）的角点检测 算法。该算法首先使用 canny 算子在原图像 中检测边缘， 计算不同尺度下边缘曲线的曲 率值； 然后将高尺度下的局部曲率极值点作 为候选角点，最后逐步减小尺度，在多个低 尺度处跟踪定位角点。 文献[11]提出了一种以 CSS 角点检测为 基础， 在较小的尺度检测出所有的局部极值 点的方法， 并根据曲率的局部性质构造自适 应阈值，先获得候选角点；然后计算出候选 角点的角度， 根据角度大小来决定真伪角点 并去除伪角点。基于 CSS 算法的角点检测 精度依赖于尺度选择的好坏， 以及自适应阈 值的 CSS 算法在小尺度下阈值和夹角的计 算受离散数据引起的噪声的影响，文献[12] 提出一种基于多尺度曲率乘积的角点检测 算法（MSCP） ，该算法的思想是利用 canny 算子提取边缘轮廓； 然后计算多个尺度下的 曲率乘积，以此来增强角点曲率，抑制噪声 曲率；最后通过一个全局阈值来提取角点。 文献[13]提出一种基于多尺度曲率多项式的 角点检测方法， 该方法的基本思想是首先获 得不同尺度下轮廓上各点的曲率值， 然后针 对不同尺度下局部极大值点计算曲率的加 权和；对于非极值点计算曲率积，最终利用 多尺度曲率积和多尺度曲率和与设定的判 定凹凸角点的阈值进行比较来获取角点。 2.4 基于支持向量机角点检测算法 在 Vapnik 等人提出的支持向量机机器 学习方法的基础上， 夏辉[14]等人提出一种基
于支持向量机的角点检测算法来检测标定 模板中模式固定的角点。 该算法在确定角点 和非角点数目后，分别以他们为中心选取
2
其中 1 、 2 为矩阵 M 的特征值， k 为经验
积达到最小。 文献 [5] 中用在响应圆域内与核像素点 灰度值相同， 且与核像素点邻接连通的区域 来代替 SUSAN 核同值吸收区，避免了传统 SUSAN 方法中漏检和误检的问题。文献[6] 中首先将图像的像素点分为边缘点、 内部点 和背景点，在此基础上对边缘点进行 SUSAN 算法处理， 然后检查提取到的角点， 分别对真角点附近的伪角点以及边缘轮廓 上的伪角点采用不同的方法进行去除。 2.1.3 基于模板匹配的角点检测算法 基于模板匹配的角点检测算法利用一 个 n n 的二维矩阵作为角点检测的模板， 分析常见角点的类型， 根据角点的类型对模 板内的各像素进行编码； 然后利用模板与待 测图像作相关匹配， 让模板在待测图像中逐 点移动，在每一点处，计算角点响应函数， 角点响应函数值越大说明相似性越高， 则该 检测图像与该模板越相似。 基于模板匹配的 角点检测方法中模板的半径越大， 能够检测 到的角点类型越多， 但同时计算量也大大增 加。 针对上述特点， 文献[7]中扩大模板半径， 同时对算法进行改进，简化模板，在增加可 检角点类型的同时也提高了计算速度。 2.2 基于二值图像的角点检测 二值图像角点检测的形态骨架法[8]是刘 文予等人提出的一种基于二值图像和形态 骨架的角点检测方法， 该方法中将二值图像 看成是一个多边形， 则多边形的角点一定在 骨架的延长线上， 并且角点所对应的骨架点 的最大圆盘应该趋于0，检测骨架点中最大 圆盘为0的点，即为角点。同时为了获得凹 角点，对原图像求补，为了克服原图与补图 的边界不一致问题，对补图做一次膨胀运