简述Hough变换检测图像曲线的方法及其优点

在预先知道区域形状的条件下，利用Hough变换可以方便地得到边界曲线而将不连续的边缘像素点连接起来，其主要优点是检出曲线的能力受噪声和曲线间断的影响较小，是一种快速的形状检出方法。

（一）Hough变换的基本思想

Hough变换的基本思想是点——线的对偶性，即图像空间中共线的点对应于参数空间中相交的线；反过来，在参数空间中相交于同一点的所有线在图像空间中都有共线的点与之对应。如图4-39a所示，在直角坐标系中的一条直线l，原点到该直线的垂直距离为ρ，垂线与x轴的夹角为θ，则这条直线方程为

而直线l用极坐标表示则为点（ρ，θ），如图4-39b所示。可见直角坐标系中的一条直线对应极坐标系中的一点，这种由线到点的变换就是Hough变换。

在直角坐标系中过任一点（x0，y0）的直线系（图4-39c）满足：

式中，φ=arctan（y0/x0）。因此这些直线在极坐标系中对应的点（ρ，θ）构成图4-39d中的一条正弦曲线。反之，在极坐标系中位于这条正弦曲线上的点，对应直角坐标系中过点（x0，y0）的一条直线，如图4-39e所示。设平面上有若干点，过每点的直线系分别对应于极坐标系中的一条正弦曲线。若这些正弦曲线有共同的交点（ρ′，θ′），如图4-39f，则这些点共线，且对应的直线方程为

图4-39　Hough变换

（二）Hough变换检测曲线

当给定图像空间中的一些边缘点时，可以通过Hough变换确定连接这些点的直线或曲线方程。把在图像空间中的曲线检测问题转换到参数空间中对点的检测，通过在参数空间里进行简单的累加统计即可完成检测任务。

算法的基本思想是对图像进行坐标变换，使之在另一个坐标空间的特定位置上出现峰值，因此检出曲线即是找出峰值位置。例如，利用Hough变换检测图像平面中是否有通过A和B两点的直线。算法的主要思想如下：设通过A、B两点的直线方程为

式中，a和b分别为直线的斜率和截距。把直角坐标（x，y）空间映射到斜率-截距的（a，b）空间，即

这时，任一点（xi，yi）映射到（a，b）空间是一条直线，即

若通过A和B两点的直线的a和b为常数a0和b0，即映射空间（a，b）中的一个固定点（a0，b0），则无论（xi，yi）如何变化，b0=-a0xi+yi都通过（a0，b0）。这样可以在内存中建立一个存储区对应于（ai，bi），其中的内容是统计（xi，yi）有多少次通过（ai，bi），每通过一次，以（ai，bi）为地址的内容加1。这样，这个内存累加地址中，累加数最大者的地址就是（a0，b0）。然后在原（x，y）空间中，用（a0，b0）即可找到通过A、B两点的直线。

直角坐标（x，y）空间不仅可以映射到斜率-截距空间，也可以映射到其他参数空间。例如（x，y）空间中的直线还可以写作

式中，r0是原点到该直线的垂直距离；θ0是垂距r0与x轴正方向的夹角。因此直角坐标空间中的直线映射到极坐标参数空间（r，θ）中为一点（r0，θ0）。而直角坐标空间中的一点（x0，y0）对应于极坐标参数空间的一条正弦曲线：

同理，如果需要检出（x，y）空间中的圆心在（a0，b0）且半径为r的圆：

则可以映射到（a，b）空间。若r固定，则在直角坐标空间中，半径为r的圆上的各点（xi，yi）在（a，b）的空间中过一个点（a0，b0）。与检测直线相同，此时需在内存中建立一个（ai，bi）的离散阵列内存空间。然后，把（x，y）空间中所有满足式（4-123）的点（xi，yi）找出来，（a，b）存储空间中以（ai，bi）为地址的内容加1。最后在（a，b）存储阵列中找到峰值位置（a∗，b∗），从而确定（x，y）空间中圆的存在。若r不固定，这时参数空间增加到三维，由a、b和r组成，如按照上述方法直接计算，则计算量增大。若已知圆的边缘点，而且边缘方向已知，则可减少一维处理，把式（4-123）对x取导数，有(www.xing528.com)

这表示参数a和b不独立。利用式（4-124），只需在由两个参数（例如a和r）组成的参数空间中建立一个二维累加数组，则计算量缩减很多。

此外，该方法可同样用于其他二次曲线，例如椭圆

双曲线

抛物线

等其他可以用解析式表达的曲线。

（三）广义Hough变换

可将Hough变换进行推广，用于检测图像中是否存在某一特定形状的物体，特别是较难用解析公式表示的某些形状物体，可以用广义Hough变换找出图像中具有这种形状的物体的位置。

例如，图4-40所示的任意形状物体，在物体内部选择一个任意点（xc，yc）为参考点，从边界上任一点（x，y）到参考点（xc，yc）的连线长度为r，它与x轴正方向的夹角是α，φ是边界在点（x，y）处的切线t的法线n与x轴正方向的夹角（即边界在（x，y）处的梯度方向）。r和α都是φ的函数，即可把r和α表示为以φ为参数的函数r（φ）和α（φ）。则（xc，yc）应满足以下关系式：

设某已知边界R，可按φ的大小列成一个二维表格，即φi～（a，r），确定φi后，可从此表格中查出a和r，经式（4-128）计算得到（xc，yc）。

对已知形状建立R表格后，开辟一个二维存储区，遍历整幅图像，对各像素都查询已建立的R表格，然后计算（xc，yc）。若对于各像素计算出的（xc，yc）很集中，就表示已找到该形状的边界。具体步骤如下：

1）对待检测物体的边界建立一个二维的R表，以φ的步进值求r和α。

2）在内存中建立一个存储区，存储内容是累加的。把（xc，yc）从最小到最大用步进表示，并作为地址，记作A（xcmin-max，ycmin-max），存储阵列内容初始化为0。

3）对图像边界上的每一点（xi，yi），计算φ，查原来的R表计算（xc，yc）。

4）使相应的存储内容A（xc，yc）加1，即A（xc，yc）←A（xc，yc）+1。在阵列中找到一个最大值，就找出了图像中的待检测物体边界。

图4-40　广义Hough变换