基于轮廓曲线的角点识别方法

谢志明，黄伟琼，黄道平

(华南理工大学自动化科学与工程学院，广州 510640)

基于轮廓曲线的角点识别方法

谢志明，黄伟琼，黄道平

(华南理工大学自动化科学与工程学院，广州 510640)

Harris角点检测算法是一种经典的角点检测算子，针对其过于依赖阈值选取及计算量大的缺点，论文提出一种改进的基于轮廓曲线的角点识别的方法，通过判断边缘点方向性，先确定出粗角点，再采取由小尺度到大尺度逐步剔除伪角点的方法，最终实现角点识别。实验结果表明，文中方法对角点提取的时间仅为Harris算法的5%，而且角点定位精确，漏检率低。

Harris算法;角点检测;轮廓曲线;角点定位

0 前言

图像中的角点包含着图像的重要信息，为具有高曲率的点，一般为图像中两条或者多条轮廓边界的相交点或者灰度变化较为剧烈的点［1］。相对于图像整体像素，图像上的角点数较少，却包含着图像的重要信息，即它在有效减少信息量的同时，还保留着图像中物体的重要特征信息，故角点的角点提取对后面的图像分析具有重要意义，而且角点检测在大多数的视觉处理任务中都有基础性的意义，如运动估计、图像匹配、摄像机标定、形状分析以及视觉的定位和测量等方面。在机器视觉中，角点检测被证实为一种重要的分析手段，正确识别角点，能够有效识别图像中物体形状，进而进行图像匹配以及参数计算［1］。

目前常用的角点检测算法可归纳为3类:基于二值图像的角点检测、基于轮廓曲线的角点检测、基于灰度图像的角点检测。Harris算子是基于图像灰度的角点检测方法，它通过计算像素点所在位置的梯度变化来检测角点，若像素点所在位置的x方向梯度与y方向梯度的绝对值均比较大，则将该像素点判定为角点。然而传统的Harris算子因为对图像上所有像素点都进行角点响应函数计算，如果图片像素值较大，则计算量大，耗时较多，不能进行实时性处理;而且，Harris算子对角点响应函数执行非极大值抑制时，角点提取的效果依赖于阈值的设定:若阈值设置过大，则会导致有用角点信息的丢失;阈值设置过小，则会导致大量伪角点被提取。针对Harris算子耗时大及阈值设置不当的问题，本文在Harris算子的思想上，提出一种改进的基于轮廓曲线的角点检测方法。

1 Harris角点检测算法

Harris角点检测算子［2］是Harris等人在1988年提出的［3］，是基于 Moravec 算子［4］的改进方法。Moravec 算子通过计算各像素沿 0°、45°、90°、135°等四个不同角度方向的平均灰度变化值，并选取最小值为该像素点的兴趣值［5］。该算法简单快速，但存在各向异性性、容易识别伪角点以及不能有效抑制噪声等不足。针对这些不足，Harris受信号处理中自相关函数的启发，给出与自相关函数相联系的矩阵M［5］。M阵的特征值是自相关函数的一阶曲率，在两个曲率值都高的情况下，认为该点是特征点，从而可以改进Moravec算子识别出伪角点的不足。并且通过使用高斯滤波器平滑图像来消除噪声对于角点检测的影响。

Harris算法以Moravec算法为基础，以目标像素点为中心，取一个小窗口，将窗口沿上、下、左、右4个方向移动，计算窗口内的灰度变化，并取最小值为该像素点的兴趣值，即角点响应函数值，再将该兴趣值与阈值相比对，若大于，则认为该像素点为角点［1，5-6］。在某一点的图像灰度自相关函数可以表示如式(1):

图像在像素点(x，y)的极值曲率就可用矩阵M的特征值表示:如果矩阵M的两个特征值都比较小，说明点(x，y)在平滑区域;如果矩阵M的有一个特征值比较大，一个特征值比较小，说明(x，y)在边缘上;如果矩阵M两个特征值都比较大，表明此时图像窗口沿任意方向的曲率都非常大，说明点(x，y)为图像的角点。

角点响应函数可表示如式(5):

其中Det(M)为矩阵M的行列式，Det(M)=AB－C2，Tr(M)为矩阵M的迹，Tr(M)=A+B。当在某点R(x，y)大于给定的阈值时，认为该点为角点。

由于Harris角点检测算法对角点的定位精度较差，过于依赖所选取的阈值，阈值过大，容易漏检角点;若阈值过小，则易检测出伪角点。在影像测量中，对图像中的图形进行尺寸计算是在图像边缘信息基础上进行的，由Harris算子中所提出的角点检测是依据像素点所在位置的梯度变化所启发，提出了一种基于轮廓曲线的角点检测方法。

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

图像边缘包含着图像丰富的信息，是图像分析的重要内容，在影像测量中，对图像中的图形进行尺寸计算是在图像边缘信息基础上进行的，本角点识别方法在对图像进行预处理后，采用Roberts算子对图像进行边缘像素点识别，得到图像的单像素边缘。对图像的单像素边缘进行局部放大，可观察到角点在边缘轮廓上具有明显的特点，与周围边缘点具有一定的夹角，根据这一特点，提出一种基于轮廓曲线的角点检测方法。

通过观察图像的边缘放大图，可发现在小模板窗口中，图像边缘像素点排列呈现出单方向性，即0°、45°、90°、135°四种方向边缘，当角点出现时，在像素点两边会出现两种角度方向，本文的角点检测算法是针对角点周围的边缘点相对位置信息的这种特点提出来的，为减小计算量，先采用小窗口模板(3*3)对角点进行粗定位，再用大窗口进行角点精确定位。算法实现如下:

(1)先对图像进行中值滤波处理，再采用roberts算子进行边缘单像素提取。

Roberts边缘提取算子如式(7):

(2)对3*3窗口内的边缘像素进行方向判断，若只有一个边缘方向，则为普通边缘点;若包括两种方向信息，则先判断为粗角点。由图1c的角点粗定位图可知，角点都被检测出来了，但是同时也检测出了很多伪角点，需要对角点进行筛选，精确定位。

图1 角点粗定位实验结果

采用3*3模板如图2，计算模板中心点与两边像素点的夹角θ:

即若中心点 w5 两边的边缘点同在 0°、45°、90°、135°方向，则确定该边缘点为非角点。

图2 3*3窗口模板

(3)在粗角点处采用由小尺度到大尺度模板，求角点两边直线夹角θ，若θ＜15°，即两边直线几近成一条直线，则该角点为伪角点，去除之;反之，则为真角点，保持该角点信息。

3 时间复杂度分析

采用Harris算法进行图像角点识别时，需要计算图像中每一个像素点的角点响应值，若Harris算法采用5*5的方形模板，方向导数采用Roberts算子，则计算每个像素点的角点响应值中所需乘法次数为:(4+1+2+2+1)*(5*5)+4=254，加法次数为:(3+3+3)*(5*5)+2=227。采用本文所提出的基于轮廓曲线的角点识别方法进行角点识别时，计算边缘点时候每个像素加减法次数为2次，每个边缘点加减法12次，从粗角点到最终角点确认:加减法4次，乘除法3次;一般情况下，边缘点和粗角点占图像总像素比例较小，故每个像素点计算次数为:加减法:2+12+4=18，乘除法:3。对于大小为N*M像素的图像，不考虑边界的影响，将两个方法的时间复杂度用表1进行比较:

表1 时间复杂度分析

4 角点提取实验结果与分析

本节采用一张1024*1280的工件图片对两个算法分别进行实验，并对结果进行分析比较。

4.1 实验结果

通过图3和图4两幅实验结果图比较分析可知，图3中方框所选中的角点为Harris角点检测算法多检测出的伪角点，图4中实线圆选中的角点为本文角点检测方法的精确定位角点，虚线圆中为漏掉的角点。

图3 Harris角点检测

图4 基于曲线轮廓的角点检测

4.2 实验结果时间复杂度分析

两算法运行时间对比见表2。

表2 两算法运行时间对比

4.3 角点识别精确度分析

角度识别精度见表3。

表3 角点识别精确度

通过图3和图4两幅实验结果图比较分析可发现，本文提出的基于曲线轮廓的角点检测算法对角点的提取比较完整，漏检率较低，且运行速度快，算法实现简单，适用于实时性的视觉测量系统。

5 结论

本文分析了Harris角点检测算法的原理及其存在的缺点，针对其计算量大，非实时性的特点，提出一种改进的基于轮廓曲线的角点检测算法，采用小尺度到大尺度逐步去除伪角点的方法。实验结果表明，本文方法对角点提取的时间仅为Harris算法的5%，而且角点定位精确，漏检率低。不过本文所提出的基于轮廓曲线的角点识别方法对噪声比较敏感，须在后续工作中进行改进，提高它的抗噪性能。

［1］张海燕，李元媛，储晨昀.基于图像分块的多尺度Harris角点检测方法［J］.计算机应用，2011，31(2):356－357.

［2］HARRISC，STEPHENSM.A combined corner and edge detector［C］.Proceedings of the Fourth Alvey Vision Conference，Manchester，UK，1998:147 －151.

［3］韩莹.数字图像角点检测算法探讨［J］.科技信息，2011:631.

［4］MORAVECHP.Towards automatic visual obstacle avoidance［C］.Proceedings of international joint conference on artificial intelligence，canbridge，MA，USA，1977:584－590.

［5］郭晓晶.图像角点检测方法的研究［D］.青岛:青岛大学，2009.

［6］王葳，唐一平，任娟莉，等.一种改进的harris角点提取算法［J］.光学精密工程，2008，16(10):1995－2001.

［7］Kitchen L，Rosenfeld A.Gray-level Corner Detection［J］.Pattern Recognition Letters，1982，1(2):95 －102.

［8］Mokhtarian F，Suomela R.Robust Image Corner Detection Through Curvature Scale Space［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，1998，20(12):1376－1381.

［9］ Freeman H，Davis L S.A Corner Fiding Algorithm for Chain-coded Curves［J］.IEEE Transaction on Computers，1977，C －26(3):297 －303.

［10］Wang H，Brandy M.Real-time Corner Detection Algorithm for Motion Estimation［J］.Image and Vision Computing，1995，13(9):695－703.

(编辑 赵蓉)

Identification Method Based on the Corner of the Contour Curve

XIE Zhi-ming，HUANGWei-qiong，HUANG Dao-ping
(College of Automation Science and Engineering，South China University of Technology，Guangzhou 510640，China)

Harris corner detection algorithm is a classical corner detection operator，for the shortcomings of over-reliance on the threshold and lots of calculation，this paper presents an improvedmethod of identification based on the corner of the contour curve，by judging the direction of edge points，determining the rough corners firstly，then gradually eliminating the pseudo-corner from small scale to large scale，finally achieving corner distinguished.The experimental result shows that the time of thismethod on corner extraction is just5%of the Harris algorithm，and locating corner precisely w ith low undetected.

harris algorithm;corner detection;profile curve;corner locating

TH165;TP391.41

A

1001－2265(2013)03－0090－03

2012－07－09;

2012－08－21

谢志明(1985—)，男，广州人，华南理工大学自动化科学与工程学院硕士研究生，主要从事数控机床方面的研究，(E－mail)jimmy_ming@163.com;黄道平(1961—)，男，广东河源人，华南理工大学自动化科学与工程学院教授，博士生导师，主要从事神经网络，Matlab教学与仿真等研究。