级联Hough变换直线特征提取方法

2018-01-18满增光刘军军

制造业自动化 2017年11期

满增光，邵烨，武星，刘军军

（1.常熟理工学院机械工程学院，常熟 215500；2.南京航空航天大学机电学院，南京 210016）

0 引言

Hough变换是Paul Hough在1962年为了在二值图像中检测直线而引入的一种有效方法，其将在图像空间中检测直线问题转换为在参数空间中搜索局部极值问题，从而使直线检测得到极大简化。Hough变换在机器视觉领域有着极为广泛和重要的应用，如用于车道线、车位线检测[1,2]、车牌校正定位[3,4]、电路板线路检测[5,6]等。Hough变换具有较强的抗干扰能力，不仅可以检测直线，还可以检测圆、椭圆[7,8]等图形。

Hough变换的优点在于，它是一种全局检测算法，不需要给定直线参数的初值，对构成直线的点集没任何要求，可以是致密的，也可以是稀疏的，每一个构成点都同等对待，具有很强的抗干扰能力。然而，也正因为标准Hough变换所具有的全局算法特性，搜索的参数空间过于全面，导致其为了获得精确的直线参数，必须提高参数空间的分辨率，从而降低了标准Hough变换的计算效率。因此，为了有效提高标准Hough变换的计算效率，本文提出一种级联Hough变换直线检测方法。

1 标准Hough变换

1.1 Hough变换基本原理

如图1所示，图像空间中的一条直线l可以表示为：

其中，ρ为原点到直线l的距离；θ为通过坐标原点做直线l的垂线，该垂线与x轴正方向的夹角。

图1 图像空间中的直线表示

对于属于直线l上的点Pi(xi,yi)，i∈(0,N)，N为直线l上点的个数，都满足式，即：

在参数空间中，xi和yi为常数，θ和ρ为变量，上式便表示为一条曲线。因此，图像空间中直线l的参数便对应于参数空间中多条曲线的交点。

1.2 标准Hough变换

标准Hough变换利用上述原理，将连续的θ和ρ分别以进行离散化，如图2所示。在离散的参数空间即空间中，将求取多条曲线的交点问题转换为采用投票方式，搜索局部极大值的问题，即在定义域所确定的范围内搜索问题的解，其中为图像空间中可能存在的直线参数ρ的最大值。因此，解的精度与参数空间的离散化程度有关，越小，获得的解的精度越高，同时计算量也越大，计算效率越低。

图2 标准Hough变换

2 级联Hough变换

希望获得高精度的解是标准Hough变换计算量大的原因之一。事实上，标准Hough变换将更多的计算浪费在不存在解的空间中。鉴于此，本文提出一种级联Hough变换，采用多级Hough变换串联的策略。多级Hough变换构成一个由顶层Hough变换到底层Hough变换的结构，顶层Hough变换搜索参数空间范围大，分辨率低，而底层Hough变换搜索参数空间范围小，分辨率高，从而解决标准Hough变换计算效率低的问题。

如图3所示是一个由顶层、中层和底层三层Hough变换构成的级联Hough变换。在顶层Hough变换中，参数空间搜索域为全部搜索域，参数空间分辨率为和如图4所示。假设在顶层Hough变换中，得到的直线参数解为以此为中间值，确定中层Hough变换的参数空间搜索域为如图5所示，在中层Hough变换中，以分辨率执行Hough变换，其中N为一自定义正整数，得到直线参数解为最后，如图6所示，在底层Hough变换中，以为中间值，确定底层Hough变换的参数空间搜索域为再以分辨率执行Hough变换，得到直线参数的最终精确解为

由图4～图6可见，级联Hough变换从顶层Hough变换到底层Hough变换时一个逐步缩小搜索域同时提高参数空间分辨率即提高直线参数的解精度的过程。可以预见，当级联Hough变换达到与标准Hough变换相同的解精度且N为2时，前者的计算效率将比后者提高近50%。

图3 三层级联Hough变换结构

图4 顶层Hough变换

图5 中层Hough变换

图6 底层Hough变换

3 实验结果与分析

为了验证本文方法的性能，在配置为Win732位，CPU2.3GHz，内存3G的电脑上，用C++和OpenCV实现了本文所提方法，并与OpenCV中自带的标准Hough变换方法进行对比。标准Hough变换方法中个像素；本文方法中即N=2，采用二级Hough变换，个像素。图7所示为原始二值图像，其像素大小为500×500，图中共计11条直线，若不重复计算点值为1的像素共5500个。

图7 原始二值图像

如图8(a)和(b)所示，分别为标准Hough变换和本文方法处理后得到的直线特征提取结果。从图中可以看出标准Hough变换与本文方法所提取的直线几乎没有差别，但是计算所需时间却相差很大，前者所需时间为29ms，而后者所需时间为17ms。通过与标准Hough变换方法对比可知，本文方法在得到相同结果的前提下，计算效率提高近50%。如果采用三级级联Hough变换，进一步降低顶层Hough变换的角度分辨率，可预知计算效率会也会进一步提高。