哈夫变换在目标检测中的应用

刘正铃 黄小海 刘玉学

摘要：本文介绍了Hough变换的原理，说明了Hough变换的点线对偶性。尤其是在极坐标变换下对直线和圆的检测进行了深入的研究。

关键词：哈夫变换；图像边缘；直线检测；极坐标

中图分类号:TP131 文献标识码:A

Researsh on Hough Transformation in Target Detection

Liu Zheng-lingHuang Xiao-haiLiu Yu-xue

（Institute ofMathematics and Information Engineering, Sanming college,Sanming Fujian ,365004)

Abstract： This paper illustrate the principle of the Hough transformation and studies the point-line duality of the Hough transformation. Especially under the polar coordinate transformation,the problem about straigh line and circle's detection is explained deeply.

Key words: Hough transform; image edge; line detection; polar coordinates

引言

哈夫(Hough)变换是利用图象全局特性而将边缘象素连接起来组成区域封闭边界的1种方法。在预先知道区域形状的条件下，利用哈夫变换可以方便地得到边界曲线而将不连续的边缘象秦点连接起来。Hough变换在计算机视觉、军事防御、办公自动化等领域都得到了普遍的关注和广泛的应用。Hough变换1962年由Paul Hough提出，并在美国作为专利[1]。它所实现的是一种从图像空间到参数空间的映射关系。设在图像空间有一个目标，其轮廓可用代数方程表示，哈夫变换就是将图像空间转化为参数空间的一种变换[2]。基于哈夫变换，可利用图像的全局特性将目标边缘像素连接起来组成目标区域的封闭边界，或直接对图像中已知形状的目标进行边缘检测。哈夫变换的主要优点是：具有图像全局特性，受噪声和边界间断的影响比较小，运算量较小，具有较好的鲁棒性[3]。但现有文献对哈夫变换在极坐标中的应用，存在不同的形式和论述，容易造成概念混淆。

本文详细叙述哈夫变换的基本原理，及在直线检测中的应用。尤其是对极坐标下直线的标准方程，进行详细地推导和论述，对哈夫变换的应用进行有益的补充。

1 哈夫变换

1.1 基本哈夫变换原理

基本哈夫变换的原理可借助如下的点—线对偶性解释。在图像空间xy中，考虑一个定点（xi，yi）和经过该点的直线斜截式方程：

yi=axi+b （1）

其中a为斜率， b为截距。则通过点（xi，yi）的直线有无数条，虽对应不同的a和b值，但均满足上述直线方程。现将式(1)改写为：

b=-xia+yi （2）

式（2）可认为代表参数空间ab中的一条直线方程，如图1所示。其中： -xi为斜率，yi 为截距。由于（xi，yi）为定点，因此等式(2)可看作参数空间ab中关于定点（xi，yi）唯一直线方程。

同理，在参数空间中，第2个点（xj，yj）也有与之相关唯一直线方程：

b=-xja+yj （3）

若在参数平面内，式(2)与式(3)所决定的直线相交，如图1所示。设交点为（a'，b'），此时将以参数a'为斜率，参数为截距。对应在图像空间xy中，就是一条同时经过定点（xi，yi）和定点（xj，yj）的直线方程参数。即有：

y=a'x+b' (4)

则式(4)即为同时经过定点（xi，yi）和定点（xj，yj）的直线斜截式方程。

由此可知在图像空间中共线的点对应在参数空间里相交的线。反过来，在参数空间中相交于同1个点的所有直线在图像空间里都有共线点与之对应。这就是点-线的对偶性。哈夫变换就是将图像空间xy中的点是否共线的问题转换为在参数空间ab中是否相交于共同交点的问题。例如，图像空间中有直线y=x，取该直线上的3个点：A(0，0)，B(1，1)，C(2，2)，显而易见，过A点的直线满足条件b=0；过B点的直线满足条件1=a+b；过C点的直线满足条件2=2a+b，这3个方程就对应着参数平面上的3条直线，而这3条直线相交于一点（a=1，b=0）。同样，原图像上直线y=x上的其它点对应参数平面上的直线也会通过点（a=1，b=0），这一性质提供了解决问题的方法.这就是Hough变换的基本思想.就是把图像平面上的点对应到参数平面上的线，最后通过统计特性来解决问题.

1.2基本哈夫变换检测直线

假设图像空间xy中，存在n个定点，则利用哈夫变换检测它们是否共线的具体步骤如下：

（1）对参数空间中a和b的可能取值范围进行量化，根据量化结果构造一个二维累加数组A(a，b)，其中amin≤a≤amax，bmin≤b≤bmax，该二维数组的初始化为零；

（2）对每个xy空间中的给定点（xi，yi），让a取定所有可能的值，用式（2）计算出b，根据a和b的值累加A，参数点(a，b)每出现一次，该单元累加器A(a，b)=A(a，b)+1，即累加值等于参数点(a，b)重复出现的次数。

（3）根据累加后A中最大值所对应的a和b，就可求出对应n个点中最多数的点所确定的直线[4 ]。

1.3基本哈夫变换检测圆

哈夫变换不仅可以用来检测直线和连接处在同一直线上的点，也可以用来检测满足解析式f(x，c)=0形式的各类曲线并把曲线的点连接起来。这里x是1个坐标矢量， c是系数矢量。例如圆的一般方程为：

(x-a)2+(y-b)2=r2 (5)

此时式（5）中有3个参数a，b，r，所以在检测圆周时，需要在参数空间里建立一个3维的累加数组A，其单元可写为A(a，b，r)，让a和b的值依次变化而根据式（5）计算出r，并对A累加：A(a，b，r)=A(a，b，r)+1。可见对圆周的检测与检测直线上的点原理相同，只是由于是3个参数，计算量增加了许多。因此实际中哈夫变换在检测简单曲线中更能体现它的优越性[5]。

2哈夫变换的改进

2.1哈夫变换的极坐标形式

使用等式y=ax+b表示一条直线带来的一个问题是，当直线接近竖直方向时将使a和b都接近于无穷而大大增加计算量.解决这一难点的方法是使用直线的极坐标方程：

ρ=xcosθ +ysinθ，-π/2≤θ≤π/2 （6）

如图2所示ρ表示原点到直线的垂直距离， θ表示该垂线与x轴正向的夹角。

该直线的极坐标方程的推导过程如下：

如图2所示。则有下式成立：

a=tanα＝－（tanθ)-1 (7)

x0=ρcosθ，y0=ρsinθ (8)

将（7），（8）两式带入等式y=ax+b，得ρsinθ=－（tanθ)-1ρcosθ+b。从而

b=ρsinθ+（tanθ)-1ρcosθ。 (9)

将式（9）代入直线方程y=ax+b。经整理，得原直线方程可转化为 ρ=xcosθ+ysinθ。

图3是过点（xi，yi）和点（xj，yj）的直线，在参数空间θρ中，经过定点（xi，yi）、（xj，yj）的唯一参数方程分别为：

ρ=xicosθ+yisinθ (10)

ρ=xjcosθ+yjsinθ （11）

式（10）、（11）分别对应参数空间θρ中的一条正弦曲线。这样图像空间xy中的点对应于新参数空间θρ中的一条正弦曲线。则将直线上的所有特征点都进行这种映射后，参数空间中就会出现很多正弦曲线，所有这些正弦曲线都经过过参数空间的定点（θ'，ρ'）。因此检测在图像空间中共线的点转化为在参数空间θρ里检测正弦曲线的交点。

2.2改进的哈夫变换检测直线

假设图像空间xy中，存在n个定点，则利用哈夫变换检测它们是否共线的具体步骤如下：

(1)对参数空间中参数θ和ρ的取值范围进行量化，θ通常取值[-π/2，π/2]，ρ通常取值[-N，N]， N为图像长度.然后根据量化结果构造一个二维数组A[θ，ρ]，其中θmin≤θ≤θmax，ρmin≤ρ≤ρmax，该二维数组初始化为零。

(2)对xy空间中的给定点（xi，yi）其中1≤i≤n，让θ取遍所有可能的值，根据式(5)计算出ρ，注意需对θ和ρ的结果进行取整操作。参数点（θ，ρ）每出现一次，该单元累加器A[θ，ρ]=A[θ，ρ]+1，即累加值等于参数点（θ，ρ）重复出现的次数。

(3)根据计算最后所得结果，二维数组累积器A[θ，ρ]中的最大值，对应n个定点中最多数的点所确定的直线。

为了能够调整精确度，可以对计算的尺度进行不同的设定。例如，将参数空间的θ轴[θmin，θmax]划分为K份，那么对应于每个定点（xi，yi），有K个 θ值对应K个ρ值。K值越大，则计算出的共线性越粗略；K值越小，则计算出的共线性越精细，甚至可以达到亚像素级。因此在参数空间θρ的尺度划分，决定了计算出的共线点的精确度。在计算量上，每个点需进行K次计算，总共n个点，因此需要nK次计算。实际中K小于n，因此计算量小于n2。可见哈夫变换有明显的计算优越性。

2.3 改进的哈夫变换检测圆

圆的哈夫变换可用下列参数方程表示：

(x-ρcosθ)2+(y-ρsinθ)2=r2 （12）

其中r为半径， ρ为圆心距原点长度， θ为圆心和原点连线与 轴的夹角θ。

此变换有以下性质：

(1) （x，y）域中一点对应于（ρ，θ，r）变换域中一个面。

(2) （ρ，θ，r）变换域中一点对应于（x，y）域中一个圆。

(3) （x，y）域中一圆上的n个点对应于（ρ，θ，r）变换域中经过一公共点的n个面。一个圆只有一个圆心和半径，当n足够大时，在（ρ，θ，r）变换域中不存在也不可能有第二个公共点。

(4) （ρ，θ，r）变换域中一面上的n点对应于（x，y）域中经过一公共点的n个圆。

圆的检测跟直线的检测相似，但因为圆的Hough变换参数方程有三个参数：ρ，θ，r，从而在分小单元时得将三个参数分段，构成一个小单元（□ρ， □θ，□r），在每小单元设一累加器，然后对图像中每一有效点进行变换。待图像中全部有效点都变换完成后，对各小单元进行检测。找出公共点，并将其代入方程：

(x-ρcosθi)2+(y-ρsinθi)2=ri2 （13）

从而得出逼近的圆的方程。

4 结束语

本文研究了Hough变换在直线和圆检测中的应用，并将他推广应用到一般曲线的检测，事实上，对于检测任意已知表达形式的曲线，累加器的维数实关键，因为随着累加器的维数增加，计算量会大幅增加，如何通过降维的思想设立累加器以及在极坐标下对一般曲线的检测，还有待近一步研究。

参考文献

[1]王仁康. 图象工程 上册:图象处理和分析[M].北京：清华大学出版社，2005.187-182

[2]冈萨雷斯.数字图像处理[M].北京:电子工业出版社,2003.474-479

[3]章毓晋.图像分析[M].北京:清华大学出版社,2005.140-150

[4]邱力为,宋子善. 直线参数检测的快速哈夫变换[J]. 北京航空航天大学学报,2003,(8)

[5]王菁菁,范影乐. 基于Hough变换的圆检测技术[J]. 杭州电子科技大学学报,2005,(4)

作者简介：

刘正铃(Liu Zheng-ling)(1987-)，男，汉族，福建宁德人，单位：三明学院数学与信息工程学院学生。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文