7.1　传统Hough变换的直线检测［1］

保罗·哈夫于1962年提出了Hough变换法，并申请了专利。该方法将图像空间中的检测问题转换到参数空间，通过在参数空间里进行简单的累加统计完成检测任务，并用大多数边界点满足的某种参数形式来描述图像的区域边界曲线。这种方法对于被噪声干扰或间断区域边界的图像具有良好的容错性。Hough变换最初主要应用于检测图像空间中的直线，最早的直线变换是在两个笛卡儿坐标系之间进行的，这给检测斜率无穷大的直线带来了困难。1972年，杜达（Duda）将变换形式进行了转化，将数据空间中的点变换为ρ-θ参数空间中的曲线，改善了其检测直线的性能。该方法被不断地研究和发展，在图像分析、计算机视觉、模式识别等领域得到了非常广泛的应用，已经成为模式识别的一种重要工具。

直线的方程可以用式（7.1）来表示。

y=kx+b　　 （7.1）

其中，k和b分别是斜率和截距。过x-y平面上的某一点（x0，y0）的所有直线的参数都满足方程y0=kx0+b。即过x-y平面上点（x0，y0）的一族直线在参数k-b平面上对应于一条直线。

由于式（7.1）形式的直线方程无法表示x=c（c为常数）形式的直线（这时候直线的斜率为无穷大），所以在实际应用中，一般采用式（7.2）的极坐标参数方程的形式。

ρ=xcosθ+ysinθ　　 （7.2）

其中，ρ为原点到直线的垂直距离，θ为ρ与x轴的夹角（如图7.1所示）。

根据式（7.2），直线上不同的点在参数空间中被变换为一族相交于p点的正弦曲线，因此可以通过检测参数空间中的局部最大值p点，来实现x-y坐标系中直线的检测。

图7.1　Hough变换对偶关系示意图

一般Hough变换的步骤如下。

①将参数空间量化成m×n（m为θ的等份数，n为ρ的等份数）个单元，并设置累加器矩阵Q［m×n］；

②给参数空间中的每个单元分配一个累加器Q（θi，pj）（0<i<m-1， 0<j<n-1），并把累加器的初始值置为零；

③将直角坐标系中的各点（xk，yk）（k=1，2，…，s，s为直角坐标系中的点数）代入式（7.2），然后将θ0～θm-1也都代入其中，分别计算出相应的值pj；

④在参数空间中，找到每一个（θi，pj）所对应的单元，并将该单元的累加器加1，即Q（θi，pj）=Q（θi，pj）+1，对该单元进行一次投票；

⑤待x-y坐标系中的所有点都进行运算之后，检查参数空间的累加器，必有一个出现最大值，这个累加器对应单元的参数值作为所求直线的参数输出。

由以上步骤看出，Hough变换的具体实现是利用表决方法，即曲线上的每一点可以表决若干参数组合，赢得多数表决的参数就是胜者。累加器阵列的峰值就是表征一条直线的参数。Hough变换的这种基本策略还可以推广到平面曲线的检测。

图7.2表示了一个二值图像经过传统Hough变换的直线检测结果。图像大小为512×480像素，运算时间为652ms（CPU速度为1GHz）。

Hough变换是一种全局性的检测方法，具有极佳的抗干扰能力，可以很好地抑制数据点集中存在的干扰，同时还可以将数据点集拟合成多条直线。但是，Hough变换的精度不容易控制，因此，不适合对拟合直线的精度要求较高的实际问题。同时，它所要求的巨大计算量使其处理速度很慢，从而限制了它在实时性要求很高的领域的应用。

图7.2　二值图像经过传统Hough变换的直线检测结果