1、一种自动检测网格点的新算法摘 要: 针对 Harris 角点检测算法在精确定位时精度不高的缺点,提出了一种有效的改进算法。新算法采用亚象素定位方法，对 Harris 算法做出改进。此外，本论文为针对网格点图像提取了一种新的基于模板的角点提取算法，与传统方法相比，该算法具有两个明显的优点:无须人工干预，能够自动确定角点位置;定位精度高，角点的平均位置偏差在 1个像素以内。 关键词: Harris 算法；角点检测；亚像素；模板 中图分类号：TS736+.2 文献标识码： A 1引言 角点是图像的重要特征，通常定义为在图像边界上曲率足够高的点。由于角点对应于图像中信息含量高的位置，相对于原图而言，使
2、用角点进行摄像机标定、匹配和重建能够大大的提高精度。 本文主要对几种传统算法的优点和缺点做了详细的比较，同时针对Harris 算法定位不足的缺点做出改进。Harris 是通过计算梯度来实现角点检测的。但是由于 Harris 算法在计算梯度的时候用到差分求导的方式，只能精确到角点的象素级别。在计算机视觉研究中，经常需要获取更高精度的角点，Harris 算法存在的问题，一般可以通过亚像素算法进行改进。目前，应用亚像素算法来改进 Harris 角点检测的方法主要有以下两种：一种是利用二次曲面拟合特征点周围的灰度分布，通过求解该二次曲面的极值可以将特征点的精度提高到子象素级 1；另一种是从亚像素角点到
3、周围像素点的矢量应垂直于图像的灰度梯度这个观察事实得到的，通过最小化误差函数的迭代方法来获得亚像素级精度的坐标值3。这两种方法的计算量都比较大，需要求极值和利用迭代的方法，编程实现也比较复杂，本文采用二次均匀 B 样条对一次角点检测后的图像进行插值的方法，然后对插值后的图像进行二次角点检测，得到亚像素精度的角点坐标。 2Harris 算法的原理 Harris 算子是一种经典的角点提取算法，具有计算简单，稳定性和鲁棒性 2良好的优点。其算法如下： 首先计算 2*2 的矩阵 M： 其中， Ix 和 Iy 为图像沿和方向的灰度梯度，G(s)为高斯模板，主要作用是去除噪声的影响。 其次，然后按照下式计
4、算点的反应值：r= Det( )为取行列式值，Trace（M）为取矩阵的迹，K 一般取经验值 0.04。r 值越大，表明该点越是角点。当 r 大于零并且较大时，对应角点。如果 r 较小但是小于零，则对应与边缘区域。如果较小时，对应与图像的平坦区域。 由于 Harris 算子具有的上述优点，使其得到广泛的应用，但是该算法在计算矩阵 M 的时候，使用的是差分求导的方式，公式如下： 导致 Harris 算法在角点提取的时候只能够检测到角点的象素级坐标,在需要精确定位（摄像机标定和三维重建）的时候不能满足精度的要求。 3Harris 算法的理论分析与改进 3.1Harris 算法的理论分析 Harri
5、s 角点检测原理是对于一副图像，角点与自相关函数的曲率特性有关4。自相关函数描述了局部图像灰度的变化程度，可表示为： = = = 其中， 在某一点的图像灰度自相关函数的极值曲率可以有矩阵 M 的特征值近似表示。如果矩阵 M 的特征值都比较大，说明在该点的图像灰度系相关函数的两个正交方向上的极值曲率均较大，即可认为该点位角点5。 3.2 算法改进 本文通过二次均匀 B 样条插值对局部图像进行插值，然后进行角点检测，解决 Harris 算法精度不高的问题。由于二次均匀 B 样条曲面片可以转化为两个不同方向的 B 样条曲线6，而 B 样条具有很好的连续性和局部性，对噪声有很好的抑制作用，同时 B 样
6、条插值计算稳定性和速度也都比较好8，并且易于编程实现。所以可以通过 B 样条曲线对局部图像的横坐标和纵坐标进行插值，然后进行局部图像的角点提取，得到亚像素级的角点坐标。 算法的实现步骤如下： 根据下式计算每个点的 M 值; 式中，G(s)为高斯模板，Ix 和 Iy 为图像沿和方向的灰度梯度； 根据下式计算每个点的角点相应函数值7； = 式中，Det(M)表示 M 的行列式，Trace（M）为 M 的积； 如果点处的角点响应函数大于某一阈值，则点即为一次角点； 以一次角点为中心取一个邻域，根据下式对邻域进行插值； 式中，j 表示在不同的方向的插值; 表示 i 点的灰度值; 根据公式（1）和（2）
7、计算插值各点的响应函数值，如果点处的角点响应函数值大于某一阈值，则点即为所求的二次角点。 因为局部图像是原始图像插值后的图像，所以二次检测到的角点是亚像素精度的。 3.3 算法改进后出现的问题及解决方法 3.3.1 插值之后提取的角点出现两个或者多个情况 若插值后出现两个或者多个情况，可以对多个角点取平均值即为最终的角点坐标。 3.3.2 插值窗口的形成 插值窗口是以一次角点为中心取邻域，一般情况下，邻域的大小选取为 15*15 个像素左右，窗口过小，会影响图像整体灰度变化；窗口过大则会提高算法的复杂度。同时，为了防止重复计算，窗口的选择应尽量避免同一局部图像中存在两个或者两个以上的一次角点，
8、这也是插值窗口的选取标准之一。 4自动检测网格点的模板角点提取算法 针对网格点这种特殊的图像，提出了一种模板检测算法来提取网格点的图像。本文采用 3*3 的模板，将网格图像中可能出现的角点情况的模板记录下来，将图像和模板做比较记录下角点的位置。 算法实现步骤 第一步：针对网格点这种特殊的图像，网格线的角点类型主要有三类：T 型角点、直角型角点和十字型角点。模板主要包括以下几种： 第二步；对模板图像进行编码，本论文采用二进制的方法对模板进行编码：编码的方向如下：将生成的二进制数值转化为十进制数, 8 7 6 5 4 3 2 1 0 第三步：对图像进行降噪、膨胀、细化等一系列处理后，将图像和模板图
9、像进行比较，有相同的即为角点。 5实验分析 5.1 改进的 Harris 算法的实验分析 图 1 原始图像 表 1 从图像效果分析改进后的算法 一次角点提取局部图像： 标记角点插值后的图像： 二次角点提取局部图像： 表 2 根据角点坐标分析改进后的算法 编号 一次角点检测结果 二次角点检测结果 x y x y 1 10 200 10.4 199.1 2 40 149 40.0 148.1 3 41 199 40.8 198.1 4 70 172 69.8 171.6 5.2 自动检测网格点的模板角点提取算法的实验分析 图 2 原始图像 图 3 图像处理后的图像 图 4 提取角点后的图像 6结论
10、 6.1 改进的 Harris 算法 角点检测算法大都是为了三维重建或三维目标跟踪等，需满足:(1)检测准确性:不计噪声，即使最细小的角点，角点检测算法也应该可以检测的到。(2)定位性:检测到的角点应尽可能接近它们的真实位置。(3) 复杂性:检测算法的复杂性越小，运行速度就越快， 自动化程度就越高 6,7 。 从准确性和定位性分析改进之后的算法 经过多次实验分析改进之后图像角点的定位精度可以达到 110-1； 从算法效率角度分析改进之后的算法 实验提高了角点的定位精度，但是却降低了算法的运行速率，因为算法对图像中每个角点附近的局部图像分别进行角点检测，降低了角点检测的速率。原算法与改进之后算法
11、的效率比值为 N(N 为原算法检测到的角点个数)。 改进的算法不改变原有算法的优点，提高了原算法定位精度，但是改进算法降低了算法的效率。 6.2 模板提取算法 经过试验，模板提取算法可以在无须人工干预条件下，能够自动确定网格角点的位置并且定位 1 个像素以内。 参考文献 1 Harris C, Stephens M. A Combined Corner and Edge Detection. Proc, 4th Alvey Vis. Conf,1988:189-192. 2 李艳，彭嘉雄. 基于 D2 样条插值和 LOG 算子的亚象素边缘检测. 华中理工大学学报，2000，28（3）：7779 3 Mehrotra R, Niphani S, Corner Detection. Pattern Recognition, 1990, 23(1):1223-1233. 4 Wang H, Brady M. Real-time corner detection algorithm for motion estimation. Image and Vision Computing, 19 95,13(9):695-703 5袁萍，袁政鹏.一种应用于视觉测量标定的亚像素级特征点提取算法.现代机械.No 4, pages 14-15, 27, 2003
