7.2　过已知点Hough变换的直线检测［2］

以上介绍的Hough变换直线检测方法是一种穷尽式搜索，计算量和空间复杂度都很高，很难在实时性要求较高的领域内应用。为了解决这一问题，多年来许多学者致力于Hough变换算法的高速化研究。例如，将随机过程、模糊理论等与Hough变换相结合，或者将分层迭代、级联的思想引入到Hough变换过程中，大大提高了Hough变换的效率。本节以过已知点的改进Hough变换为例，介绍一种直线的快速检测方法。

过已知点的改进Hough变换方法，是在Hough变换基本原理的基础上，将逐点向整个参数空间的投票转化为仅向一个“已知点”参数空间投票的快速直线检测方法。其基本思想是：首先找到属于直线上的一个点，将这个已知点p0的坐标定义为（x0，y0），将通过p0的直线斜率定义为m，则坐标和斜率的关系可用下式表示：

（y-y0）=m（x-x0）　　 （7.3）

定义区域内目标像素pi的坐标为（xi，yi），（0≤i<n，n为区域内目标像素总数），则pi点与p0点之间连线的斜率mi可用下式表示：

mi=（yi-y0）/（xi-x0）　　 （7.4）

将斜率值映射到一组累加器上，每求得一个斜率，将使其对应的累加器的值加1，因为同一条直线上的点求得的斜率一致，所以当目标区域中有直线成分时，其对应的累加器出现局部最大值，将该值所对应的斜率作为所求直线的斜率。

当xi=x0时，mi为无穷大，这时式（7.4）不成立。为了避免这一现象，当xi=x0时，令mi=2，当mi>1或mi<-1时，采用式（7.5）的计算值替代mi，这样无限域的mi被限定在了（-1，3）的有限范围内。在实际操作时设定斜率区间为［-2，4］。

m'i=1/mi+2　　 （7.5）

过已知点Hough变换的具体步骤如下：

①将设定的斜率区间等分为10个子区间，即每个子区间的宽度为设定斜率区间宽度的1/10；

②为每个子区间设置一个累加器nj（1≤j≤10）；

③初始化每个累加器的值为0，即nj=0；

④从上到下，从左到右逐点扫描图像，遇到目标像素时，由式（7.4）及式（7.5）计算其与已知点p0之间的斜率m，m值属于哪个子区间就将哪个子区间累加器的值加1；

⑤当扫描完全部处理区域之后，将累加器的值为最大的子区间及其相邻的两个子区间（共3个子区间）作为下一次投票的斜率区间，重复上述①～④步，直到斜率区间的宽度小于设定斜率检测精度为止，例如，m=0.05，这时将累加值为最大的子区间的中间值经过式（7.5）设定条件的逆变换后作为所求直线的斜率值。

过已知点Hough变换的直线检测过程如图7.3所示。

图7.3　过已知点Hough变换直线检测过程

图7.4为过已知点Hough变换的直线检测结果，图中检出直线上的“+”表示已知点的位置，处理时间为35ms。也就是说，对于该图，在同等条件下，过已知点Hough变换的处理速度比一般Hough变换快将近20倍。

利用过已知点Hough变换的直线检测方法，其关键问题是如何正确地选择已知点。在实际操作中，一般选择容易获取的特征点为已知点，例如，某个区域内的像素分布中心等。

图7.4　过已知点Hough变换的直线检测结果

在实际应用中，往往通过对检测对象特征的分析，获取少量的目标像素点，通过减少处理对象来提高Hough变换的处理速度。检测对象的特征一般采用亮度或者颜色特征。例如，在检测公路车道线时，可以通过分析车道线的亮度或者某个颜色分量，首先找出车道线在每条横向扫描线上的分布中心点，然后仅对这些中心点进行Hough变换，就可以极大地提高处理速度。在进行特征点的提取时，某些特征点可能会出现误差，但是由于Hough变换的统计学特性，部分误差不会影响最终的检测结果。