Hough变换基本原理

Hough变换是由Paul Hough于1962年提出的一种检测圆的算法，它的基本思想是将图像从原图像空间变换到参数空间，在参数空间中，使用大多数边界点都满足的某种参数形式作为图像中的曲线的描述，它通过设置累加器对参数进行累积，其峰值对应的点就是所需要的信息。

Hough变换最大的优点是对噪声不敏感。

对于满足直线方程y=ax+b的某一个点（x0,y0），对应于参数平面(a,b)上的一条直线b= y0-ax0，而来自于这条直线上的其他数据点也必然对应于参数平面(a,b)上的直线，且相交于特定的参数点（a,b）。

在实际应用中，为了避免垂直直线斜率无穷大的问题，通常采用直线极坐标的方程r=xcosq+ysinq，显然此时参数面变为（r，q）面。

直线由两点A(x1,y1)和B(x2,y2)定义（如下图a所示）。

通过点A的所有直线可由方程y1=k x1+q表示，其中k和q是表示斜率和截距的一定值，如果我们将k和q认为是参数空间的话，此时通过点A的所有直线就可以表示为q= - x1 k + y1 （如图b所示）。

同理，通过点B的所有直线可由方程y2=k x2+q表示，在参数空间k和q中，通过点B的所有直线就可以表示为q= - x2 k + y2，此时，图b中两条直线的唯一公共交点表示的就是图a中连接A、B两点的直线。

这样，原图像空间中直线上的每一点都可以映射为参数空间k和q中的一条直线，我们对参数空间的点进行累计，其峰值就对应图像空间中要确定的直线。

因此，对于Hough变换，有以下对应关系：

• 图像空间的一条直线在参数空间映射为一个点。
• 图像空间的一个点映射为参数空间的一条正弦曲线。
• 图像空间的一条直线上的多个共线点映射为参数空间相交于一点的多条正弦曲线。

Hough变换的具体算法步骤如下：

• 适当的量化参数空间。
• 将参数空间的每一个单元看作一个累加器。
• 初始化累加器为0。
• 对图像空间的每一点，在其所满足参数方程对应的累加器上加1。
• 累加器存储的最大值即为对应的图形的参数。

Hough圆检测原理及方法

Hough变换不仅适用于直线检测，还适用于任何形式的f(x,a)=0所表示的图形的检测，其中x 表示坐标向量，a表示系数向量。下边我们对Hough变换检测圆的原理做简要介绍。

对于一个半径为r，圆心为（a,b）的圆，我们将其表示为：

此时x=[x,y]T，a=[a,b,r]T，其参数空间为三维。

显然，图像空间上的一点（x,y），在参数空间中对应着一个圆锥，如下图所示。

而图像空间的一个圆就对应着这一簇圆锥相交的一个点，这个特定点在参数空间的三维参数一定，就表示一定半径一定圆心坐标的图像空间的那个圆。

上述方法是经典的Hough圆检测方法的原理，它具有精度高，抗干扰能力强等优点，但由于该方法的参数空间为三维，要在三维空间上进行证据累计的话，需要的时间和空间都是庞大的，在实际应用中不适用。

为加快Hough变换检测圆的速度，学者们进行了大量研究，也出现了很多改进的Hough变换检测圆的方法。

如利用图像梯度信息的Hough变换，对圆的标准方程对x求导得到下式：

从上式看出，此时的参数空间从半径r，圆心（a,b）三维，变成了只有圆心（a,b）的二维空间，利用这种方法检测圆其计算量明显减少了。

但这种改进的Hough变换检测圆的方法其检测精度并不高，原因在于，此种方法利用了边界斜率。

从本质上讲，边界斜率其实是用曲线在某一点的弦的斜率来代替的，这种情况下，要保证不存在误差，只有在弦长为零的情况。

但在数字图像中，曲线的表现形式是离散的，其在某一点处的斜率指的是此点右向n步斜率或是左向n步斜率。

如果弦长过小了，斜率的量化误差就会增大。

这种方法比较适用于干扰较少的完整圆形目标。

除了上述方法外，还有其他的一些Hough圆检测算法。

如随机Hough变换，它的主要思想是通过在图像空间中随机抽样来降低内存需求与计算时间，具体做法是在图像空间中随机选取不共线的三点映射到参数空间，参数空间的单元集是一个动态链表结构，当参数单元陈列的值到达一定阈值就认为其确定了一个圆，将其作为候选圆，再通告证据累计统计图像空间中落在该候选圆上的点数，若点数大于一定阈值，确认为真实圆。

此种方法有效的降低了计算量和时间消耗，但其也存在一定问题，如无效累积量大，检测效率不高等，其检测精度也低于经典的Hough变换。

另外还有王建峰等改进的快速随机Hough变换，其基本思想是，考虑到圆必定在其外接正方形之内，为了减少随机Hough变换的无效累计，可以只对外接正方形之内的像素进行计算，之外的像素可以直接排除，这样大大降低了计算时间。

可以取边缘厚度为一个较小数t，对于任意三点确定对应的参数圆心（a,b）和半径r,边缘点集中的点di（dix,diy），如果有dix >a+r+t或dix <a-r-t或diy >b+r+t或diy <b-r-t，则不必对其进行计算。

通过这种方法就可以排除大量不是候选圆的点，提高了速度。

这种方法的缺点是没有解决好候选圆外接或者内切正方形的边长问题。

通常情况下，影响常规Hough变换的运算速度的因素主要有：参数空间的维数，边缘点的数量，运算的复杂性，参数空间的离散化程度，以及最后的峰值检测等。