1 引言

随着科技水平的发展与进步,机器视觉技术在众多领域得到了越来越广泛的应用,而目标识别是图像处理和计算机视觉的一个重要课题^[1-6],在目标识别的过程中,直线检测又是至关重要的一步,广泛应用于目标追踪、尺寸检测、相机标定等众多领域。

Hough变换是Hough^[7]于1962年提出的一种使用表决原理的参数估计技术,已经成为处理图像中直线检测问题的一种经典算法,目前绝大多数的直线检测算法都是基于标准Hough变换(HT)技术的。Hough变换对于噪声不敏感,具有较强的稳健性,但仍存在计算量大、复杂度高、峰值难以确定等问题。基于此,许多研究人员提出了改进算法,如Xu等^[8]提出随机Hough变换(RHT),利用随机性,采用一种“多对一”的映射方式,在一定程度上解决了占用内存高、计算量大的问题,但同时由于随机采点,在处理复杂图像时引入大量无效单元,算法效率不高;Matas等^[9]提出概率Hough变换(PPHT)算法,其核心思想是在进行图像像素映射时,将像素点映射到具有更大概率的参数域单元中,从而减少了算法处理时间,但仍存在计算量大,占用内存高且无法确定端点位置的问题;张振杰等^[10]提出基于Hough一维变换的直线检测算法,将极坐标参数空间简化为一维空间,在计算复杂度和储存空间方面得到了一定程度的改进;Ji等^[11]通过放大直线峰值与噪声之间差异,引入局部增强算子,从而得到更加精确的局部累加峰值,但需要对图像进行全局遍历,效率不高;刁燕等^[12]将边界分为有序和无序两类,提出基于概率的局部Hough变换优化算法;孙俊峰等^[13]提出结合像素局部对比度和全局虚警抑制的直线检测算法,提高了直线检测的稳健性;张江鑫等^[14]利用梯度信息进行像素点聚类,然后对聚类点进行RHT直线检测,减小了参数空间的占用单元,但是会将相互平行的直线上的像素点归为一类,仍存在无效累计的问题。

目前已有的直线检测算法相较于标准Hough变换已经有了一定程度的提升,但在均衡性方面还有待提高。基于此,本文提出一种基于改进RHT的直线检测算法,处理过程主要包括:基于8邻域搜索的边缘图像分组、基于梯度方向差分的直线边缘预检测、基于随机抽样一致性(RANSAC)算法的改进RHT直线边缘细分和直线精确处理。

2 标准Hough变换存在问题描述

2.1 标准Hough变换直线检测算法

标准Hough变换本质是一种从图像空间到参数空间的映射关系,如图1所示,其中(ρ,θ)表示原点到直线距离的向量,该向量与直线垂直,ρ表示向量长度,θ表示向量方向;将图像空间中的特征信息映射到参数空间,将参数空间离散化,利用共线点在参数空间相交的对偶性,遍历图像中每一个像素,并映射到参数空间,对参数空间累加“投票”,并通过局部峰值检测出直线参数,映射回图像空间中,即为原图像中直线的检测结果;由于直线的斜率存在无穷大情况,因此Hough变换通常在极坐标系下进行。

图 1. Hough变换示意图

Fig. 1. Hough transformation diagram

下载图片 查看所有图片

2.2 标准Hough变换直线检测存在的问题

王竞雪等^[15]对于标准Hough变换直线检测存在的问题进行了详细描述,将其分为确定性问题和不确定性问题两类,本文结合实际应用中直线检测的需求,将标准Hough变换直线检测过程存在的主要问题描述如下。

1) 实时性问题。由于标准Hough变换需要遍历图像中的每一个像素,并将其映射到参数空间进行累加投票,因此在处理大尺寸图片时所需要的计算量十分庞大;由Hough变换的处理过程可知,其内存消耗与“投票”间隔成反比,对于一幅尺寸为948 pixel×650 pixel大小的图片,设置ρ的量化宽度为1,θ的量化宽度为0.001°,硬件平台为Intel(R)Core(TM)i7-6700、3.40 GHz、8 G,软件平台为Matlab2014a,采用标准Hough变换进行直线检测所需的时间为57.65 s,不能满足工业生产实时性要求,不具备实用价值。

2) 参数空间的伪峰值问题。由于图像中噪声和小短线的影响,图像空间中可能存在伪峰值点,根据投票阈值的不同,可能出现直线误检现象。

3) 直线过连接问题。标准Hough变换直线检测可能将不在同一连通域中的像素点检测为同一直线,或将噪声点与边缘点检测为同一直线。

4) 线段端点定位和长度确定问题。标准Hough变换直线检测无法获得线段的端点坐标和长度。

3 基于改进RHT的直线检测算法

算法的流程如图2所示,主要分为4步:1) 8邻域边缘图像分组可以排除小短线和噪声影响,解决直线检测过程中过连接问题;2) 直线边缘预检测可以排除不含有直线特征的连通域,提高算法的检测效率,解决计算量大、占用内存高的问题;3) 直线边缘细分可以提取出连通域中的直线边缘像素点,解决直线检测过程中线段长度确定问题和伪峰值问题;4) 对直线进行精确处理,得出线段端点坐标并通过最小二乘法计算直线的精确参数,从而进一步解决目前标准Hough变换直线检测存在的问题。

图 2. 算法检测流程

Fig. 2. Flow chart of algorithmic detection

下载图片 查看所有图片

3.1 8邻域边缘分组

8邻域边缘分组是对边缘图像进行遍历搜索,并对连通边缘进行聚类分组,从而将图像分为不同的连通域,在边缘检测的基础上,具体分组过程如下。

1) 图像预处理,生成边缘图像,设定边缘最短像素数阈值T_min。

2) 对边缘图像进行全局遍历,判断是否存在未标记的边缘像素点,若存在未标记的边缘像素P₀,则进行新的边界跟踪;否则结束算法,图3所示为P₀的8邻域。

3) 对于边缘像素点P₀,按照逆时针方向,即从P₁开始到P₈结束,判断其8邻域内是否存在其他边缘像素点,若存在,则建立边缘分组E_n,n(n=1,2,3,…)表示边缘分组编号;若不存在,即P₁~P₈像素点灰度值均为0,则像素点P₀为孤立像素点,结束当前边界追踪,并返回步骤1),同时将像素点P₀置零。

图 3. P0的8邻域

Fig. 3. 8 neighborhoods of P0

下载图片 查看所有图片

4) 将8邻域内的边缘像素点加入到当前边缘分组中,并将像素点P₀置零。

5) 将步骤4)中边缘分组的最后一个像素点作为当前点继续搜索,判断其8邻域内是否存在其他边缘像素点,若存在,则返回步骤4);若不存在,则按照顺时针方向依次选取步骤4)中像素点P₀的8邻域内检测到的边缘像素点作为当前点,直到P₀的8邻域内的像素点全部检测结束。

6) 重复步骤2)~5),直到整个图像遍历结束。

7) 判断每一个边缘分组像素数目是否大于阈值T_min,如果不满足,则为小短线或者噪声,将该边缘分组去除,不参与后续处理,从而排除小短线和噪声的影响。

3.2 基于梯度方向差分的直线边缘预检测

在8邻域边缘分组的基础上,对分组后的像素点进行基于梯度方向差分的直线边缘预检测。

图像上某点的梯度向量表示为

∇f(x,y)=Gx(x,y)Gy(x,y)=∂f∂x∂f∂y,(1)

式中(x,y)表示像素点的坐标,G_x(x,y)和G_y(x,y)分别表示像素点在x和y方向上的梯度。梯度方向为像素点(x,y)灰度增长最快的方向,定义为

α(x,y)=arctanGy(x,y)Gx(x,y),α(x,y)∈-π2,π2。(2)

像素点的梯度方向垂直于该点的边缘方向,因此直线上像素点的梯度方向大致相同,利用梯度方向信息可以进行直线定位,排除非直线边缘;但在实际应用时,由于梯度方向精度不高,往往需要设定误差θ_r,对(θ±θ_r)范围内的边缘点进行累加,则同一直线上像素点梯度方向差值最大可以达到2θ_r,难以保证检测精度。基于此,本文提出梯度方向差分概念,对于任意边缘组E{x_i,y_i}(i=1,2,3,…,m),其中i表示某一边缘分组中像素点的编号,m为边缘分组中最大像素数目;相邻两像素点的梯度方向差分Δα定义为

Δαi=α(xi+1,yi+1)-α(xi,yi),i=1,2,…,m-1。(3)

设定差分阈值T_α,依次求出每一边缘组E_n,n表示边缘分组的编号,将相邻两像素点的梯度方向差分,建立投票空间,判断梯度方向差分是否满足阈值要求并进行累加投票,并根据投票结果排除不含有直线特征的边缘组,从而解决直线检测过程中非直线边缘造成的无效累加问题。

设定梯度方向差分阈值为T_α,累加阈值为T_max,直线边缘预检测的过程如下:

1) 初始化累加器次数N_En=0。

2) 对边缘分组后的图像,计算边缘分组E_n中相邻像素点梯度方向差分Δα_i;这里将梯度方向转化到无符号区域,即

α(x,y)=α(x,y)+π,α(x,y)<0α(x,y),others。(4)

3) 判断Δα_i<T_α,i=1,2,…,m-1,若成立,则对应累加器N_En=N_En+1。

4) 判断每一边缘分组累加器N_En≥T_max,若成立,则该边缘分组存在直线;反之,则该边缘分组不含有直线特征,将边缘分组中像素点置零,不参与后续处理。

设定累加阈值T_max=80,梯度方向差分阈值T_α=0.08,对于图4(a)所示图像,进行8邻域边缘分组和直线边缘预检测得到处理后的结果如图4(b)和(c)所示。

由图4(c)可知,处理后的图像有效地排除了非直线边缘,提取出含有直线特征的边缘组。

图 4. 基于梯度方向差分的直线边缘预检测。(a)实验图像;(b) 8邻域边缘分组情况;(c)含有直线特征的边缘

Fig. 4. Linear edge detection based on gradient direction difference. (a) Experimental image; (b) 8 neighborhood edge group; (c) edges profile with straight line feature

下载图片 查看所有图片

3.3 基于改进RHT算法的直线边缘细分

图像中直线包含两种情况:1) 理想的独立直线边缘;2) 包含直线特征的闭合边缘。对于包含直线特征的边缘,需要进一步细分,将边缘分组中的直线特征提取出来。文献[ 6]提出的RHT算法通过预先假定直线参数,实现直线像素点的聚类,但由于随机取点具有盲目性会造成无效累计,因此需要更有针对性地采点,从而建立大概率直线参数模型,避免非直线模型造成的投票无效累计问题。RANSAC算法^[16]假设将样本数据分为“内点”、“外点”和“噪声点”,“内点”为满足给定数学模型的正确数据,“噪声点”和“外点”均为不符合给定数学模型的数据,其计算过程的实质是模型的假设与验证的过程。基于RANSAC算法思想,在RHT随机采点建立直线参数模型时,首先进行参数判断,不符合要求的模型不参与后续累加,从而在一定程度上避免RHT随机性问题。

本文算法将RHT算法中抽取2个点改为选取4个样本像素点,其中2个样本点作为假设“内点”,建立目标数学模型,另外2个假设“内点”建立验证模型,具体步骤如下:

1) 从直线边缘预处理后的图像中随机抽取4个假设“内点”,p(x_k,y_k),k=a,b,c,d。根据其中两个“内点”p(x_a,y_a)、p(x_b,y_b)建立直线参数方程1,得到直线的参数(ρ,θ)。

2) 根据另外两个“内点”p(x_c,y_c)、p(x_d,y_d)建立直线参数方程2,得到直线的参数(ρ^*,θ^*),

ρ-ρ*≤δ1θ-θ*≤δ2,(5)

式中δ₁和δ₂是参数误差,若4点在同一直线上,则理论上δ₁=δ₂=0,但由于图像由离散的像素点组成,存在误差,故设定δ₁=δ₂=0.5,判断(5)式是否成立,若成立,则认为4个“内点”满足参数方程1,该参数方程有效,对应的直线可能在图像上;反之,则说明参数无效,返回步骤1)。

3) 求出边缘组中其他样本点到直线参数模型的距离,即

di-ab=ρ-xicosθ-yisinθ,i=1,2,…,m。(6)

4) 若d_i-ab满足小于点到直线距离阈值δ,则说明该像素点是“内点”,在直线上;反之,则说明该点不在直线上。

5) 统计该模型累加的“内点”数目,若数量满足最短直线像素数目,则模型成立,直线存在。

通过直线边缘细分可以有效地实现直线上像素点的聚类,为后续直线参数精确处理和端点定位提供基础。

3.4 直线的精确处理

直线精确处理的目的是为了获取直线的端点坐标、长度以及直线方程的精确参数。直线边缘细分后的点集中各像素点的坐标为(x_i,y_i),i=1,2,3,…,p,p表示每一直线聚类后像素点的数目,当直线参数45°≤θ≤135°时,将像素点根据X坐标从小到大进行排序,反之,则根据Y坐标进行从小到大排序,即可得到线段的端点坐标及长度。同时,将最小二乘算法应用到直线拟合中,从而得出直线的精确参数。对直线细分后的点集进行最小二乘算法拟合。为简化计算过程,这里直接采用直角坐标下的直线方程,进行拟合优化。优化的模型为

minϕ=∑i=1nyi-aoxi-bo2,(7)

式中a_o和b_o表示直线的参数,函数φ=f(a_o,b_o)对a_o和b_o求偏导数,经整理可得:

ao=n×∑i=1nxiyi-∑i=1nxi∑i=1nyin×∑i=1nxi2-∑i=1nxi2bo=n×∑i=1nyi-n×ao×∑i=1nxi。(8)

由于在直角坐标系下直线方程存在直线斜率无穷大的情况,因此在最小二乘拟合之前,首先判断下式是否成立:

n×∑i=1nxi2-∑i=1nxi2=0。(9)

若(9)式成立, 则直线方程为x=N,N为常数,满足:

N=∑i=1nxin。(10)

否则,根据(8)式得出直线参数。

通过直线精确处理,即可得出图像中线段的端点坐标和长度以及所在直线的精确参数,具有一定的实际应用价值。

4 实验结果与分析

为验证改进算法在检测直线时的稳定性和适应性,分别对仿真图像、近景楼房图像、道路图像等数字图像进行直线提取,并与标准Hough变换进行对比分析,其中算法处理时间是指图像经边缘检测后至线段提取完成所需要的处理时间,实验平台为Matlab R2014a。标准Hough变换直线检测算法采用Matlab中自带函数。

实验1。图4(a)为含有高斯噪声的仿真图像,大小为512 pixel×384 pixel,内部含有4条明显的直线特征,标准Hough变换和本文算法检测后的结果如图5所示。标准Hough变换的相关参数设置如下:ρ的量化间隔为1,θ的量化间隔0.01°,参数投票的累加阈值T=0.1n_max。本文算法相关参数设置如下:最短边缘像素阈值T_min=20,梯度方向差分阈值T_α=0.08,梯度方向差分累加阈值T_max=60,点到直线距离阈值δ= 2。

由实验结果可以看出,对于干扰较小,直线特征明显的仿真数字图像,本文算法和标准Hough变换直线检测算法均能有效地提取出图像中的直线特征,但在处理时间和算法效率方面,本文算法所需要的处理时间约为标准Hough变换的1/3,并且可以有效地提取出线段的端点坐标和长度。

图 5. 实验图像直线边缘检测。(a)标准Hough变换; (b)本文算法

Fig. 5. Linear edge detection of experimental image. (a) Standard Hough transform; (b) proposed algorithm

下载图片 查看所有图片

实验2。图6(a)是一幅含有较多直线特征的建筑物数字图像,大小为532 pixel×572 pixel,通过标准Hough和本文算法检测后的结果如图6(b)和(c)所示,标准Hough变换的相关参数设置如下:ρ的量化间隔为1,θ的量化间隔0.01°,参数投票的累加阈值T=0.1n_max。本文算法相关参数设置如下:最短边缘像素阈值T_min=25,梯度方向差分阈值T_α=0.08,梯度方向差分累加阈值T_max=80,点到直线距离阈值δ= 2。由于楼房图像中直线特征较多,求取线段的长度和端点坐标无实际意义,因此,并未进行线段端点坐标和长度的计算。

由实验结果可知,建筑物数字图像由于植物干扰,采用标准Hough变换进行直线检测在干扰部分产生大量错检,存在直线过连接现象,而本文算法可以很好地排除噪声干扰,有效地检测出图像中的直线特征,并且直线的连贯性较好。

实验3。汽车进行自主导航时常需要视觉进行道路识别以规划行驶路径,图7(a)是两边带有植物干扰的道路图片,大小为983 pixel×604 pixel,通过标准Hough和本文算法检测后的结果如图7(b)和(c)所示。标准Hough变换的相关参数设置如下:ρ的量化间隔为1,θ的量化间隔0.01°,参数投票的累加阈值T=0.3n_max。本文算法相关参数设置如下:最短边缘像素阈值T_min=60,梯度方向差分阈值T_α=0.08,梯度方向差分累加阈值T_max=100,点到直线距离阈值δ= 2。由于求取道路图像中线段的长度和端点坐标无实际意义,因此,并未进行线段端点坐标和长度的计算。

图 6. 建筑物图像直线边缘检测。(a)楼房图像;(b)标准Hough变换;(c)本文算法

Fig. 6. Linear edge detection of building image. (a) Building image; (b) standard Hough transform; (c) proposed algorithm

下载图片 查看所有图片

由实验结果可知,当标准Hough变换对道路图像进行直线检测时,由于道路两旁植物噪声干扰,未能很好地检测出道路边缘,而本文算法可以排除两旁噪声干扰,准确地识别出道路边缘信息,具有更好的实际应用价值。

图 7. 基于梯度方向差分的直线边缘预检测。(a)道路图像;(b)边缘检测图像;(c)标准Hough变换;(d)本文算法

Fig. 7. Linear edge detection based on gradient direction difference. (a) Road image; (b) edge detecting image; (c) standard Hough transform; (d) proposed algorithm

下载图片 查看所有图片

三组对比实验的统计结果如表1所示。

实验1中本文算法检测出的端点坐标及线段长度,如表2所示。

除以上三组对比实验外,本文还针对多个场景进行了直线检测,考虑篇幅有限,不一一列出。实验结果表明,本文算法能够有效地提取出不同种类数字图像中的直线特征,与标准Hough变换相比,具有更好的抗干扰能力,直线连贯性好,计算速度快,很大程度上解决了标准Hough实时性问题,为目标跟踪、尺寸检测、车辆导航等应用领域提供基础。

5 结论

提出了一种基于改进RHT的直线检测算法,通过8邻域追踪边缘分组,解决标准Hough变换直线检测中的过连接问题,提出像素点梯度方向差分概念,很大程度上避免了直线检测过程中无效累计问题,并基于RANSAC算法,提出带有直线参数模型预检验的改进RHT直线检测算法,进一步解决了无效累计问题,同时提高了算法检测效率,解决了标准Hough变换的实时性问题。

通过三组对比实验可知,本文算法在实时性和检测效果方面均优于标准Hough直线检测算法,且算法的均衡性更好,解决了目前标准Hough变换算法存在的实际问题,直线特征检测效果更加优越,从而可以更好地应用于实际生产中,具有一定的工程实际意义。