一种基于Hough变换新的亚像素定位算法

陈光静，陈明贵，肖玉强

（1.西安通信学院电子工程系，陕西西安710106；2.西安电子科技大学机电工程学院，陕西西安710071）

测量的方式、方法正向多样化发展，对几何量测量来说，其测量尺度正在向两个极端发展——小尺寸方向和大尺寸方向。小尺寸方向是指新型微米测量和纳米测量的研究与应用；大尺寸测量指几米至几百米范围内物体的空间位置、尺寸、形状、运动轨迹等的测量，数字摄影测量是近几年发展起来的一种非接触测量技术［1］，已广泛用于几何量的测量中，其测量精度的关键技术之一是亚像素定位算法。本文分析了数字摄影测量的基本原理，提出了一种基于Hough变换的用于检测直线和圆的亚像素定位算法，并对亚像素定位算法进行了仿真和实验，结果表明亚像素定位精度能达到0.02像素［2］，有效地提高了数字摄影测量的精度。提下，像点、光心和物点满足共线方程，即三点共线。精确地确定由像点和光心组成的射线是摄影测量的关键，要做到这一点，就要注意两个关键因素：1）精确地确定摄影系统的系统参数，如光心、光轴和焦距；2）精确地提取目标的对应像点的位置。

式（1）就是摄影测量学中最基本的共线方程，其中物点、光心和像点这三点必须在同一条直线上。该表达式反应了空间物点的坐标（xw，yw，zw）和光心坐标T及光轴角度R和对应像点（X，Y）之间的数学关系。

根据共线方程，在摄像机内部参数确定的条件下，利用若干个已知的物点和相应的像点坐标，就可以根据式（1）求解出摄像机的6个外参数，即摄像机的光心坐标和光轴方位

1 数字摄影测量的基本原理

摄像机模型是光学成像几何关系的简化，最简单的模型为线性模型（或者称为针孔模型）。在满足针孔模型假设的前的信息。

2 基于Hough变换的亚像素定位法

对图像中目标进行定位是基于图像精密测量的最基本和最重要的任务之一。标志中心的亚像素定位是进行摄像机标定前的必须步骤，其定位精度直接影响着后面的标定精度，是顺利进行摄影测量的基础。

由于标定模板及用定向反光材料制作的标志多是由矩形和圆构成的，为了达到对矩形和圆形中心的子像素级精度定位，首先用边缘检测算子对矩形和圆形的边缘进行整像素级精度粗定位，然后对像素级边缘点进行亚像素级定位，从而确定标志中心的精确位置。

Hough变换是利用图像全局特性而将边缘像素连接起来组成区域封闭边界的一种方法。在预先知道区域形状的条件下，利用Hough变换可以方便地得到边界曲线而将不连续的像素边缘点连接起来，可以直接检测某些已知形状的目标，如直线和圆。本文充分利用Hough变换的优点，针对其在检测直线和圆方面的缺点进行改进，提出了用于检测直线的二次Hough变换法和用于检测圆的三等分Hough变换法。

2.1 边缘点粗定位

像素级边缘点检测方法主要是用经典的边缘提取算子，如Sobel算子、Prewitt算子、LoG算子和Cany算子等。这些经典算子是微分法，都要计算像素点（i，j）处的梯度，因此，本文采用了3×3的卷积模板，如图1所示。

图1 边缘点粗定位采用的卷积模板Fig.1 The unfolding pattern for rude locate of edge-point

其中梯度分量为：

梯度幅值为：

梯度方向为：

2.2 用于检测直线的二次Hough变换及矩形中心的亚像素定位方法

在利用Hough变换进行直线检测方面具有并行实现、受噪声和曲线间断的影响小等主要优点，但也存在很多不足［3-4］。例如：难于找到累加器数组的局部最大值，精度低，存储空间较大，计算速度较低。为了解决这些问题，本文在传统Hough变换的基础上进行改进，通过使用二次Hough变换的方法来克服存储空间以及计算精度和速度方面的问题。

第一次Hough变换主要用于直线位置的粗定位。进行第一次Hough变换的时候可以很好地去除噪声的干扰。

第二次Hough变换主要用于直线的精确定位，通过对第一次Hough变换后得到的步长进行进一步细分。经过第二次Hough变换可以快速得到直线的参数，且具有较高的定位精度。

利用二次Hough变换得到其参数空间坐标系中的参数，这些参数点对应它们在图像坐标系中的特征直线。根据参数坐标，得到（ρ，θ），由极坐标方程

从而可以写出直线方程

2.3 用于检测圆的三等分Hough变换及圆心的亚像素定位方法

对于图像存在噪声和边缘不连续性等干扰，Hough变换具有较强的鲁棒性，长期以来成为圆检测的主要方法，被认为是高效的匹配滤波工具，但传统Hough变换存在以下几个主要的缺点[5-7]：1）计算量大，占用内存大；2）检测性能受参数离散间隔制约；3）存在多个圆或椭圆时检测性能不佳。为克服上述缺点，本文对传统Hough变换进行改进，提出了圆的三等分Hough变换检测方法。

圆的方程可表示为：

假定圆心O点坐标为（x0，y0），圆的半径为R，已知圆上a，b，c三点的坐标分别为（xa，ya）、（xb，yb）、（xc，yc），三点与圆心之间所成的夹角∠aob、∠boc、∠coa均为120°，则圆心坐标为：

圆的半径为

这里，取半径为

在由x0、y0、R所组成三维参量空间中，映射到参量空间中的圆心和半径为式（4）和式（5）所确定的一些点。对这些点进行统计累积，每选取的一组点，它所确定的圆心坐标和半径的累积值增加1。当对所有队列中的点进行完这种操作后，具有最大累积值的点作为圆的参数。

3 仿真及实验

为了验证本文提出的直线与圆的亚像素定位算法的精度及可靠性，选择含有正方形和圆形标志的模板为测量对象，共进行了两方面的实验，1）用计算机仿真直线和圆，对理想边缘加入误差进行模拟计算；2）用数码相机拍摄实际标志模板的图像，然后进行处理。

3.1 计算机仿真模拟

3.1.1 正 方形标志仿真

正方形标志仿真用来验证直线定位算法的有效性。表1是定位中心的试验数据（表中为部分结果），其中D=（xw-x）2+（yw-y）2体现了该算法的精度。

表1 正方形标志定位中心仿真数据Tab.1 Location center simulation data of square indicator

从上表可看出，直线定位算法对正方形标志中心的定位精度在0.003 mm以内，说明直线定位算法具有很好的定位效果，能把误差控制在有效范围内。

3.1.2 圆 形标志仿真实验

本文在模板成像实验中，实际标志图像的边缘点进行椭圆最小二乘拟合后，各点相对于拟合椭圆边界均有偏差值，将这些偏差值当作实际误差加入到模拟椭圆的边缘点上，然后进行拟合，从而可以计算加入实际误差（或噪声）的中心定位精度。

这里采用了LoG算子粗定位边缘点及其亚像素边缘点的实际拟合偏差。图2（a）的实际边缘点数为48个，粗定位边缘点拟合后各点偏差的均方根（RMS）为0.380像素，亚像素拟合后的RMS为0.148像素；图2（b）的实际边缘点数为40个，粗定位边缘点拟合后各点偏差的RMS为0.441像素，亚像素拟合后的RMS为0.146像素。模拟椭圆的圆心坐标为（40，40），加入实际偏差后的中心计算结果见表2。

表2 圆形标志定位中心仿真数据Tab.2 Location center simulation data of circle indicator

从上表可看出，粗定位边缘对标志中心的定位精度在0.02～0.1像素，亚像素边缘对标志中心的定位精度优于0.02像素。

3.2 实际模板成像实验

3.2.1 正 方形标志成像实验

采用普通数码相机（Panasonic DMC-LZ8）对标定模板中的正方形进行拍摄照片，由于畸变的存在，实际正方形成像后呈长方形。但由于正方形和长方形中心的定位方法基本一样，所以成像后的长方形中心即可近似认为是原模板中对应正方形的中心。表3是定位中心的实验数据（表中为部分结果），其中D=（xw-x）2+（yw-y）2体现了该实验算法的精度。

表3 正方形标志定位中心实验数据Tab.3 Location center experiment data of square indicator

从上表可看出，直线定位算法对正方形标志中心的定位精度在0.005 mm以内，精度较仿真实验略低，但仍能说明直线定位算法具有很高的定位精度。

3.2.2 圆 形标志成像实验

采用普通数码相机对RRT标志拍摄照片（图2），图2（a）近似为理想的“二值”圆，图2（b）是偏离摄影光轴的标志影像，呈椭圆形且相对于图2（a）其反差较小。

图2 定向反光标志的“准二值影像”Fig.2 The quasi-two-value image of directional glisten indicator

为了验证算法的精度，进行了以下两方面的实验：1）用不同算子粗定位的像素级边缘点拟合椭圆中心；2）对相同图像用亚像素精度的像素边缘点拟合椭圆中心。

实验1）中，边缘点粗定位分别采用了阈值分割法、Sobel算子以及LoG算子，粗定位边缘点和相应的亚像素边缘点拟合的标志中心结果见表4。

表4 圆形标志定位中心实验数据Tab.4 Location center experiment data of circle indicator

从上表可看出，不同的粗定位算法得到的结果是不一样的，标志影像质量较好时差异较小（圆形标志X和Y分量差值为0.07像素和0.04像素），而标志影像质量不是很好时差异较大（椭圆标志X和Y分量差值均为0.1像素）；当采用亚像素边缘拟合标志中心时，不同的算法其结果差异很小，最大只有0.02像素，这与实验1）的结果是一致的。

由于摄影是透视成像，越是处在像片边缘的圆形标志，其成像后椭圆度越高。对不同椭圆度的标志图像进行了处理，在适当曝光确保成像质量的前提下，其结果与上述实验是一致的。

4 结论

针对直线边缘检测和圆边缘检测，分别采用二次Hough变换法和三等分Hough变换法，通过使用二次Hough变换的方法，克服了直线边缘计算精度低和速度慢的问题，通过使用三等分Hough变换法，克服了传统Hough变换法圆边缘检测性能受参数离散间隔制约及精度低的问题。仿真和实验表明新算法的亚像素定位精度能达到0.02像素以内，由此见，采用新的亚像素算法可有效提高了数字摄影测量的精度。

[1]于起峰，陆宏伟，刘肖琳.基于图像的精密测量与运动测量[M].北京：科学出版社，2002.

[2]肖玉强.基于数字摄影测量的大尺寸精密测试技术研究[D].西安：西安电子科技大学，2010.

[3]李强兵，刘文予.基于Hough变换的快速矩形检测算法[J].微计算机信息，2007，23（11-1）：248-250.

LI Qiang-bing，LIU Wen-yu.The quick rectangle detection algorithm based on Hough transform[J].Control&Automation，2007，23（11-1）:248-250.

[4]刘良江，王耀南.一种基于Hough变换的圆的检测方法[M].湖南：湖南大学，2007.

[5]Edmundson K，Baker L.Photogrammetric measurement of the arecibo primary reflector surface the coordinate measurement systems committee conf[J].Albuquerque，NM，2001，（8）：l3-l7.

[6]Jensen K，Anastassiou D.Subpixel edge localization and the interpolation of still images[J].IEEE Trans.on IP，1995，4（3）:285-295

[7]Beghdadi A，Negrate A L.Contrast enhancement technique based on local detection of edge[J].Computer Vision，Graphics and Image Processing，1989，46（2）:162-174