总第２５９期 ２０１１年第５期 计算机与数字工程 Ｃｏｍｐｕｔｅｒ＆Ｄｉｇｉｔａｌ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏ１．３９ Ｎｏ．５ １４２ 基于改进Ｈａｒｒｉｓ算法的角点检测 房超王小鹏牛云鹏王超 （兰州交通大学电子与信息工程学院兰州 ７３００７０） 摘要提出了一种改进的Ｈａｒｒｉｓ角点检测方法。该方法在Ｈａｒｒｉｓ角点检测求得角点响应函数后，利用双掩膜来定 义进行非极大值抑制的局部范围，结合Ｋ均值聚类方法进行非极大值抑制，若像素点的角点响应函数值满足预设角点判定 条件，则将该像素点定义为角点。实验结果表明，该方法无需进行阈值选择，提高了角点检测精度。 关键词Ｈａｒｒｉｓ角点检测；特征提取；Ｋ均值聚类 ＴＮ９１１．７３ 中图分类号Ｃｏｒｎｅｒ Ｄｅｔｅｃｔｉｏｎ Ｂａｓｅｄ ｏｎ Ａｎ Ｉｍｐｒｏｖｅｄ Ｈａｒｒｉｓ Ａｌｇｏｒｉｔｈｍ Ｆａｎｇ Ｃｈａｏ Ｗａｎｇ Ｘｉａｏｐｅｎｇ Ｎｉｕ Ｙｕｎｐｅｎｇ Ｗａｎｇ Ｃｈａｏ （Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ＆Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｌａｎｚｈｏｕ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ ７３００７０） Ａｂｓｔｒａｃｔ Ａｎ ｉｍｐｒｏｖｅｄ ｈａｒｒｉｓ－ｂａｓｅｄ ｃｏｒｎｅｒ ｄｅｔｅｃｔｉｏｎ ｍｅｔｈｏｄ ｉｓ ｐｒｅｓｅｎｔｅｄ ｉｎ ｔｈｅ ｐａｐｅｒ．Ｆｉｒｓｔｌｙ，ｔｈｅ ｃｏｒｎｅｒ ｒｅｓｐｏｎｓｅ ｆｕｎｃｔｉｏｎ ｏｆ ｔｈｅ Ｈａｒｒｉｓ ｃｏｒｎｅｒ ｄｅｔｅｃｔｉｏｎ ｓｈｏｕｌｄ ｂｅ ｏｂｔａｉｎｅｄ．Ｓｅｃｏｎｄｌｙ，ｔｈｅ ｔｗｏ－ｍａｓｋｓ ａｒｅ ｄｅｆｉｎｅｄ ｔｈｅ ｓｃｏｐｅ ｏｆ ｎｏｎ－ｍａｘｉｍａ ｓｕｐｐｒｅｓｓｉｏｎ ａｎｄ ｔｈｅ Ｋ ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｉｓ ｕｓｅｄ ｔｏ ｓｔａｒｔ ｏｎ ｔｈｅ ｎｏｎ－ｍａｘｉｍａ ｓｕｐｐｒｅｓｓｉｏｎ．Ｔｈｉｒｄｌｙ，ｉｆ ｔｈｅ ｖａｌｕｅ ｏｆ ｔｈｅ ｐｉｘｅｌ ｃｏｔ— ｎｅｒ ｒｅｓｐｏｎｓｅ ｆｕｎｃｔｉｏｎ ｉｓ ａｇｒｅｅ ｗｉｔｈ ｔｈｅ ｐｒｅｓｅｔ ｃｏｎｄｉｔｉｏｎｓ，ｔｈｅ ｐｉｘｅｌ ｉｓ ｄｅｆｉｎｅｄ ａｓ ｔｈｅ ｃｏｒｎｅｒ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｉｓ ｍｅｔｈｏｄ ｄｏｅｓ ｎｏｔ ｒｅｑｕｉｒｅ ｔｈｅ ｔｈｒｅｓｈｏｌｄ ｓｅｌｅｃｔｉｏｎ ａｎｄ ｉｅｐｒｏｖｅ ｔｈｅ ｐｒｅｃｉｓｉｒｏｎ ｏｆ ｃｏｒｎｅｒ ｄｅｔｅｃｔｉｏｎ． Ｋｅｙ Ｗｏｒｄｓ Ｈａｒｒｉｓ ｃｏｒｎｅｒ ｄｅｔｅｃｔｉｏｎ，ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ，Ｋ ｍｅａｎｓ Ｃｌａｓｓ Ｎｕｍｂｅｒ ＴＮ９１１．７３ １ 引言 角点一般是指图像中亮度变化剧烈的像素点 的设定。若阈值设置过大，则会导致有用角点信 息的丢失；阈值设置过小，则会导致大量伪角点被 提取。 或者指图像中梯度值和梯度变化率都很高的像素 点，它反映了图像的局部特征。角点检测是图像处 理应用中的一个关键预处理步骤，常用于图像匹 配、运动物体跟踪以及目标识别等方面。基于图像 边缘轮廓的方法和基于图像灰度的方法是角点检 测主要应用的两种方法。 文献［１］提出了基于双阈值的Ｈａｒｒｉｓ角点 检测改进算法，利用双阈值法去除伪角点，文献 ［２］提出了基于曲线拟合的Ｈａｒｒｉｓ角点检测改 进算法，利用拟合曲线上峰值的位置来确定角点 坐标。针对阈值设置不当引起的问题，文中提出 基于双掩膜与Ｋ均值聚类的Ｈａｒｒｉｓ角点检测改 进方法。 Ｈａｒｒｉｓ算子是基于图像灰度的角点检测方 法，它通过计算像素点所在位置的梯度变化来检 测角点，若像素点所在位置的ｏ２７方向梯度与Ｙ方 ２ Ｈａｒｒｉｓ角点检测算法 Ｈａｒｒｉｓ通过运用微分运算和自相关矩阵改进 了Ｍｏｒａｖｅｃ角点检测算法 。用微分算子重新定 义灰度强度变化的公式，其灰度强度变化表示为： 向梯度的绝对值均比较大，则将该像素点判定为 角点。然而传统的Ｈａｒｒｉｓ算子对角点响应函数执 行非极大值抑制时，角点提取的效果依赖于阈值 ＊收稿日期：２０１０年１１月２３日，修回日期：２０１０年１２月３０日 作者简介：房超，男，硕士研究生，研究方向：数字图像处理。王小鹏，男，教授，研究方向：数字图像分析。牛云鹏，男， 硕士研究生，研究方向：数字图像处理。王超，男，硕士研究生，研究方向：信号分析。 ２０１１年第５期 计算机与数字工程 １４３ Ｅ ， （ｚ， ）一 一 叫 ， ［Ｌ厂（ ＋ ， ＋ ）－－ｆ（ｘ， ）］ 点响应函数风的值在两个大小不等的掩膜内均为 极大值并且此极大值对应的ｉｎ（Ｉ （ ， ）ｆ）大于 ： …［甜ｘ＋ ｙ＋ｏ（ ＋ ）］ Ｓ 类中ｌｎ（ｆ Ｉ）的均值，则该点就被定义为角点。 此方法无需进行选择阈值，提高角点检测精度。 ３．１改进方法 ≈ ：叫…ＥｕＸ￣ｖＹ］ 一 …，［ ㈩ 现代相机主要噪声源是光子噪声，因此角点响 应函数 受到信号自身和乘性噪声的影响。在检 其中，Ｗ…为高斯窗口在（“， ）处的系数，ｘ一 ，ｙ 测局部极大值时，灰度值较小、光度较暗区域的局 —ｏ ｊ＿，它们是像素点在Ｘ方向和ｙ方向的一阶梯 度，反映图像中每个像素点的灰度变化方向，若像 素点（ｚ， ）在两个方向灰度都发生足够大的变化则 提取为角点。 一阶梯度算子反映的是像素点在任意方向上 的灰度强度的变化，因而能够有效地区分角点和边 缘像素点，这样使角点检测算子具有旋转不变性。 同时Ｈａｒｒｉｓ检测算法选取高斯函数为检测窗口， 对图像进行平滑滤波再提取角点，对噪声有较好的 抑制作用。 定义像素点（ｚ，Ｙ）的自相关矩阵为：Ｍ一 ［ 。飙 分另ＪＩ是矩阵Ｍ的两个特征 值，为了避免对矩阵Ｍ进行特征值分解，Ｈａｒｒｉｓ定 义了角点响应函数，表达式如下： Ｒ＾一ｄｅｔＭ－－ｋ（ｔｒｌ￣ｉ） （２） 其中，ｄｅｔＭ是矩阵Ｍ的行列式且ｄｅｔＭ＝ａｌ× ２，ｔｒＭ 是矩阵Ｍ的迹且ｔｒＭ＝２ ＋ ，ｋ是一个大于０的参 数，一般取值为０．０４。ｄｅｔＭ在边缘处较小而在角点 处较大，ｔｒＭ在边缘和角点处保持一致。因此，当像 素点（ ， ）的Ｒｈ值为局部最大时，即为角点。 ３改进的Ｈａｒｒｉｓ角点检测 在实际应用中，Ｈａｒｒｉｓ角点检测算法也存在一 些不足：１）Ｈａｒｒｉｓ角点检测算法的定位精度较差， 同时还可能漏掉一些实际的角点。２）Ｈａｒｒｉｓ角点 检测需要在设定阈值的基础上进行非极大值抑制， 提取角点的准确度取决于阈值的设定。阈值设定 过大则会引起角点信息的丢失，阈值设定过小又会 导致大量伪角点被提取。 针对上述问题，提出了一种Ｈａｒｒｉｓ角点检测 改进方法，利用双掩膜（Ｓ 与Ｓ ）来定义非极大值 抑制的局部范围，结合Ｋ均值聚类方法［ （可以 将Ｓ 与Ｓ。掩膜视为两个类，如图１所示）进行非 极大值抑制，若Ｓ 掩膜内的中心像素点（ｚ， ）的角 部极大值与叠加有乘性噪声、灰度值较大、光度较 亮区域的局部极大值不易区分。为了将这种乘性 噪声转化为加性噪声，将对角点响应函数 进行 对数处理，在ｌｎ（ｊＲ １）中，噪声的方差于图像 的灰度值。标准差可以滤除由噪声引起的局部极 大值。由于ｌｎ（１Ｒ ｆ）的局部均值能够用于估计标 准差并可以反映光照强度的参数，因此它可以用于 检测局部极大值。 在确定局部极大值时，采用Ｋ均值聚类算法， 此算法与Ｏｔｓｕ算法ｌ＿７川］有着相同的结果，但它不 用对全局进行彻底搜索，只需对定义的类进行搜 索，提高了运算的速度。用ｌｎ（ｉＲ ｆ）的平均值对Ｋ 均值聚类方法进行初始化，双掩膜内的像素聚为 Ｓ 与Ｓ：两类，如图１所示，其ｉｎ（ｊ １）的均值分 别记为 与 ，若ｉｎ（！Ｒ （ｚ， ）！）＞ ，则Ｓ 与 Ｓｚ内的局部极值会被检测到；若 一 ｚ＜Ｏ，则Ｓ 与Ｓｚ内不存在局部极值。 … ・ 改进Ｈａｒｒｉｓ角点 … 一 ；； 检测方法是将上述的Ｋ ：十一 均值聚类算法用于局部 ｉ ｊ＿＿ ｉ－●一 范围的非极大值抑制， 其原理是：首先利用 Ｈａｒｒｉｓ角点检测算法求 出角点的响应函数 ， 图１双掩膜与聚类 然后设计两个大小不等 的掩膜（文中采用的双掩膜大小分别为：３×３与１５ ×１５），将这两个掩膜同时作为对Ｒ， 进行非极大值 抑制的局部范围并将这两个掩膜视为两类，分别计 算这两类ｉｎ（｝Ｒ Ｉ）的均值，记为 与 。。最后查 找这两个掩膜内的最大值并对查找的结果进行分 析：若满足３×３掩膜内的最大值与１５×１５掩膜内 的最大值的个数为一且相等并且此最大值对应的 是同一个像素点（ ， ）的Ｒ 值，那么像素点（ｚ， ） 将有可能是角点，若还满足像素点（ ）是３×３掩 膜内的中心像素点并且ｌｎ（ｉＲ （ ， ，）ｆ）＞ ，则像 素点（ｚ， ）是角点。 １４４ 房超等：基于改进Ｈａｒｒｉｓ算法的角点检测 第３９卷 ３．２实现步骤 该方法的步骤为：１）利用Ｈａｒｒｉｓ角点检测算 法求出角点的响应函数 。２）设计大小分别为３ ×３和１５×１５的两个掩膜，记为 ３ 。和∞ｌｓ ，将 角点检测方法的阈值设为Ｔ一０．００１ＭＡＸ（ ）与 Ｔ一０．Ｏ５ＭＡＸ（Ｒ ）时，角点检测的准确度分别为 ５６．６３ 与４０．３５ ，其准确度低于改进Ｈａｒｒｉｓ角 点检测方法的准确度。从表中可以看出阈值选择 这两个掩膜作为对尺 进行非极大值抑制的局部范 围。３）将这两个掩膜视为两类，分别计算这两类ｌｎ 不当会导致角点的丢失或冗余，而改进的Ｈａｒｒｉｓ 角点检测方法无需进行阈值选择，提高了角点检测 的精度，但该方法也存在着不足，即不能很好的克 服角点漏检的问题。 表１ 实验对比结果（丁表示进行非极大值抑制的阈值． （ＪＲ Ｊ）的均值，记为 与 。。４）查找这两个掩膜 内的最大值并做如下分析：（１）ＭＡＸ（叫 ）一 ＭＡＸ（ ）并且此最大值的个数为一；（２） （ｚ， ）＝ＭＡＸ（∽×３）＝ＭＡＸ（ｃｏ４×４）；（３）像素点（ ， ） 为 。 。掩膜内的中心像素点；（４）ｌｎ（ｉ风（ｚ，ｙ）Ｉ）＞ ；若上述四个条件同时满足，则可将像素点（ ， ） 确定为角点。５）把两个掩膜同时进行距离为单位 像素的平移，平移方式为如图２所示的之字形平 移，每平移一次就进行一次步骤４）的分析，直到整 幅图像被分析检测完为止。 图２掩膜平移方式图 ４实验结果与分析 为了验证改进方法的有效性，将此改进方法在 ＭＡＴＬＡＢ平台上予以实现并与传统的Ｈａｒｒｉｓ算 法角点检测结果进行比较。 嗣 （ａ）本文方法 （ｂ）７ ０ ００１ＭＡ （Ｒ ） （ｃ）７。＿Ｏ ０５ＭＡ （Ｒ ） 图３ Ｈａｒｒｉｓ角点检测算法与本文算法的仿真结果 从图３（ｂ）和图３（ｃ）可以看出传统的Ｈａｒｒｉｓ角 点检测算法在进行非极大值抑制时主要依赖于阈 值的选择，阈值选择过小，会提取出了大量的伪角 点，阈值设置过大，会导致有用角点的丢失。改进 的Ｈａｒｒｉｓ角点检测算法的仿真结果如图３（ａ）所 示，我们从图中可以看出利用双掩膜与Ｋ均值聚 类改进后的Ｈａｒｒｉｓ角点检测方法能有效检测出角 点信息，无需进行阈值设置，提高了角点检测的精 度。图中Ｔ表示进行非极大值抑制的阈值，ＭＡＸ 表示掩膜内Ｒ 的最大值。 表１是两种方法的实验结果对比，传统Ｈａｒｒｉｓ ＭＡＸ表示掩膜内Ｒ＾的最大值） 角点检测方法 正确角伪角漏检角准确度 点数 点数点数 （％） Ｔ—Ｏ．００１ＭＡＸ（Ｒ＾）４７ ２７ ９ ５６．６３ Ｈａｒｒｉｓ角点检测 Ｔ一０．Ｏ５Ｍ Ｘ（Ｒ ） ２３ １ ３３ ４Ｏ．３５ Ｈａｒｒｉｓ角点检测 文中方法 ４７ ２ ９ ８１．Ｏ３ ５ 结语 提出改进Ｈａｒｒｉｓ角点检测方法利用双掩膜设 定进行非极大值抑制的局部范围，结合Ｋ均值聚 类方法进行非极大值抑制，此方法无需进行阈值选 择，克服了传统Ｈａｒｒｉｓ角点检测算法依靠经验选 取阈值的不确定性造成的角点丢失或冗余问题，提 高了角点检测的精度。 参考文献 ［１］毛雁明，兰美辉，王运琼，等．一种改进的基于Ｈａｒｒｉｓ角点 检测方法口］．计算机技术与发展，２００９，５（１９）：１３０￣１３３ ［２］龚平，刘相滨，周鹏．一种改进的Ｈａｒｒｉｓ角点检测算法 Ｉ－Ｊ］．计算机工程与应用，２０１０，４６（１１）：１７３￣１７５ ［３］Ｈａｒｒｉｓ Ｃ，Ｓｔｅｐｈｅｎｓ Ｍ．Ａ ｃｏｍｂｉｎｅｄ ｃｏｒｎｅｒ ａｎｄ ｅｄｇｅ ｄｅｔｅｃｔｏｒ［Ｃ￣／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４ｔｈ Ａｌｖｅｙ ｖｉｓｉｏｎ ｃｏｎ— ｆｅｒｅｎｃｅ，ｌ９８８：ｌ４７～１５１ ［４］Ｆｌｏｒｅ Ｆａｉｌｌｅ．Ａｄａｐｔｉｎｇ Ｉｎｔｅｒｅｓｔ Ｐｏｉｎｔ Ｄｅｔｅｃｔｉｏｎ ｔｏ Ｉｌｌｕ— ｕｒｉｎａｔｉｏｎ Ｃｏｎｄｉｔｉｏｎｓ［Ｊ］．Ｄｉｇｉｔａｌ Ｉｍａｇｅ Ｃｏｍｐｕｔｉｎｇ： Ｔｅｃｈｎｉｑｕｅｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２００３，１２（１０）：４９９￣５０８ ［５］Ｔｒｉｅｒ，Ｏ．Ｄ，Ｊａｉｎ，八Ｋ．Ｇｏａｌ ｄｉｒｅｃｔｅｄ ｅｖａｌｕａｔｉｏｎ ｏｆ ｂｉｎａｒｉｚａｔｉｏｎ ｍｅｔｈｏｄｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，１９９５，１２（１７）：１１９１ —～１２０１ ［６］孙士保，秦克云．改进的ｋ平均聚类算法研究［Ｊ］．计算 机工程，２００７，１３（３３）：２００￣２０１ ［７３ Ｎ．Ｏｔｓｕ．Ａ ｔｈｒｅｓｈｏｌｄ ｓｅｌｅｃｔｉｏｎ ｍｅｔｈｏｄ ｆｒｏｍ ｇｒａｙ－ｌｅｖｅｌ ｈｉｓｔｏｇｒａｍｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ．Ｓｙｓｔｅｍｓ，Ｍａｎ，ａｎｄ Ｃｙ— ｂｅｒｎｅｔｉｃｓ，１９７９，１（９）：６２￣６６ ［８］许向阳，宋恩明，金良海．Ｏｔｓｕ准则的阈值性质分析 ［Ｊ］．电子学报，２００９，１２（３７）：２７１６￣２７１９
