霍夫变换直线检测(Line Detection)原理及示例

给定一幅图像(一般为二值图像)中的点集合,如何检测直线?

一种解决方法:任选一对点,决定一条线,然后测试所有其他点是否接近这条线,从而得出接近这条特殊线的所有点的子集。该方法比较复杂。另外一种方法便是采用霍夫变换。

霍夫变换是图像处理必然接触到的一个算法,它通过一种投票算法检测具有特定形状的物体,该过程在一个参数空间中通过计算累计结果的局部最大值得到一个符合该特定形状的集合作为霍夫变换结果,该方法可以进行圆,直线,椭圆等形状的检测。在车道线检测中,当初考虑的一个方案便是采用霍夫变换检测直线进行车道线提取。

霍夫变换(Hough Transform)

霍夫变换(Hough Transform)于1962年由Paul Hough 首次提出,后于1972年由Richard Duda和Peter Hart推广使用,是图像处理领域内从图像中检测几何形状的基本方法之一。经典霍夫变换用来检测图像中的直线,后来霍夫变换经过扩展可以进行任意形状物体的识别,例如圆和椭圆。
霍夫变换运用两个坐标空间之间的变换,将在一个空间中具有相同形状的曲线或直线映射到另一个坐标空间的一个点上形成峰值,从而把检测任意形状的问题转化为统计峰值问题。

霍夫直线检测(Hough Line Detection)

Hough直线检测的基本原理在于利用点与线的对偶性,在我们的直线检测任务中,即图像空间中的直线与参数空间中的点是一一对应的,参数空间中的直线与图像空间中的点也是一一对应的。这意味着我们可以得出两个非常有用的结论:

1)图像空间中的每条直线在参数空间中都对应着单独一个点来表示;
2)图像空间中的直线上任何一部分线段在参数空间对应的是同一个点。

因此Hough直线检测算法就是把在图像空间中的直线检测问题转换到参数空间中对点的检测问题,通过在参数空间里寻找峰值来完成直线检测任务。

霍夫直线检测的基本原理

关于对偶性

1)图像空间中的点与参数空间中的直线一一对应。
在图像空间x-y中,一条直线在直角坐标系下可以表示为:
y=kx+b
其中k和b是参数,表示直线的斜率和截距。
过某一点$A(x_0,y_0)$的所有直线的参数均满足方程$y_0=kx_0+b$
那么该方程在参数空间k-b中就对应了一条直线。以上过程如图1所示:

也就是说,图像空间x-y中的点$(x_0,y_0)$对应了参数空间k-b中的直线$b=−k∗x_0+y$.因此可以得到结论,图像空间中的点与参数空间中的直线一一对应。

2)图像空间中的直线与参数空间中的点一一对应

我们在直线y=kx+b上再增加一个点$B(x_1,y_1)$,那么点$B(x_1,y_1)$在参数空间k-b中同样对应了一条直线,如图2所示:

可以看到,图像空间x-y中的点A和点B在参数空间k-b中对应的直线相交于一点,这也就是说AB所确定的直线,在参数空间中对应着唯一一个点,而这个点的坐标值$(k_0,b_0)$也就是直线AB的参数。
以上就是在直线检测任务中关于对偶性的直观解释。这个性质也为我们解决直线检测任务提供了方法,也就是把图像空间中的直线对应到参数空间中的点,最后通过统计特性来解决问题。假如图像空间中有两条直线,那么最终在参数空间中就会对应到两个峰值点,依此类推。
如图3所示,图像空间中有5个点,将这5个点转换到参数空间k-b中对应着5条直线,每两条直线的交点可以确定图像空间中的一条直线,我们可以选择由尽可能多直线汇成的点,如A和B,将其参数空间中的坐标值作为图像空间中两条直线方程参数,由此便确定了两条直线,

总结来说,在参数k-b平面上相交直线最多的点,对应的x-y平面上的直线就是我们的解

参数空间的选择

上述为了方便讲解对偶性和霍夫变换的基本原理,我们的参数空间也选择了笛卡尔直角坐标系。但在实际应用中,参数空间是不能选择直角坐标系的,因为原始图像直角坐标空间中的特殊直线x=c(垂直x轴,直线的斜率为无穷大)是没办法在基于直角坐标系的参数空间中表示的。
或者,直观理解,如下图4所示,为一条垂直于x轴的直线,将各点转换到参数空间k-b后的情况:

可以看到,这些点在参数空间中的直线并没有交点。

那么能否采用其他方式进行表示呢?是的,一般我们采用极坐标方式作为参数空间。
图5所示,为图像坐标系到极坐标系参数空间的转换过程:

对于图像空间中的垂线来说,用极坐标可以表示为:
r=xcosθ+ysinθ=x
从上面可以看到,参数空间的每个点(ρ,θ)都对应了图像空间的一条直线,或者说图像空间的一个点在参数空间中就对应为一条曲线。参数空间采用极坐标系,这样就可以在参数空间表示原始空间中的所有直线了。
注意,此时图像空间(直角坐标系x-y)上的一个点对应到参数空间(极坐标系ρ-θ)上是一条曲线,确切的说是一条正弦曲线。
如图6所示,为图像空间到极坐标参数空间的转换过程:


这样就把在图像空间中检测直线的问题转化为在极坐标参数空间中找通过点(r,θ)的最多正弦曲线数的问题。霍夫空间中,曲线的交点次数越多,所代表的参数越确定,画出的图形越饱满。

利用霍夫变换检测直线

如前所述,霍夫直线检测就是把图像空间中的直线变换到参数空间中的点,通过统计特性来解决检测问题。具体来说,如果一幅图像中的像素构成一条直线,那么这些像素坐标值(x, y)在参数空间对应的曲线一定相交于一个点,所以我们只需要将图像中的所有像素点(坐标值)变换成参数空间的曲线,并在参数空间检测曲线交点就可以确定直线了。
在理论上,一个点对应无数条直线或者说任意方向的直线(在参数空间中坐标轴表示的斜率k或者说θ有无数个),但在实际应用中,我们必须限定直线的数量(即有限数量的方向)才能够进行计算。
因此,我们将直线的方向θ离散化为有限个等间距的离散值,参数ρ也就对应离散化为有限个值,于是参数空间不再是连续的,而是被离散量化为一个个等大小网格单元。将图像空间(直角坐标系)中每个像素点坐标值变换到参数空间(极坐标系)后,所得值会落在某个网格内,使该网格单元的累加计数器加1。当图像空间中所有的像素都经过霍夫变换后,对网格单元进行检查,累加计数值最大的网格,其坐标值(ρ0, θ0)就对应图像空间中所求的直线。如图7所示,为一个离散化过程。

霍夫变换直线检测步骤示例

总结:使用霍夫变换检测直线具体步骤:
1.彩色图像->灰度图
2.去噪(高斯核)
3.边缘提取(梯度算子、拉普拉斯算子、canny、sobel)
4.二值化(判断此处是否为边缘点,就看灰度值==255)
5.映射到霍夫空间(准备两个容器,一个用来展示hough-space概况,一个数组hough-space用来储存voting的值,因为投票过程往往有某个极大值超过阈值,多达几千,不能直接用灰度图来记录投票信息)
6.取局部极大值,设定阈值,过滤干扰直线
7.绘制直线、标定角点

霍夫直线检测的优缺点

优点:Hough直线检测的优点是抗干扰能力强,对图像中直线的殘缺部分、噪声以及其它共存的非直线结构不敏感,能容忍特征边界描述中的间隙,并且相对不受图像噪声的影响

缺点:Hough变换算法的特点导致其时间复杂度和空间复杂度都很高,并且在检测过程中只能确定直线方向,丢失了线段的长度信息。由于霍夫检测过程中进行了离散化,因此检测精度受参数离散间隔制约

霍夫直线检测的OpenCV实现->查看opencv官方文档

未经允许不得转载!霍夫变换直线检测(Line Detection)原理及示例

如遇到无法显示的问题,请先尝试刷新页面

客服联系邮箱:ai52learn@foxmail.com

本文地址:https://ai.52learn.online/937