Hough Transform 霍夫变换之直线检测

在图像处理中,经常需要找出一个平面上散点集中可能存在的直线,即直线检测。比较容易想到的办法是选取任意两个散点并计算其所在直线方程的k、b系数对;遍历全部散点两两计算,则出现频率较高的直线方程k、b系数对,即是图像中存在的直线。但是该方法过于暴力,当散点集规模较大时,效率十分低下。而通过 Hough Transform 霍夫变换则可以大大提高对散点集中存在的直线的检测效率

abstract.jpeg

Hough Transform 霍夫变换

笛卡尔坐标系下的参数空间

我们知道笛卡尔坐标系下,直线方程为y=kx+b。现在我们对该直线方程变形后有 b=-kx+y,这时我们不再把k、b看作是系数,而是将其分别作为参数空间的自变量、因变量,而x、y则看作是系数。这样我们就可以实现笛卡尔坐标系与其参数空间之间的映射

figure 1.jpeg

可以看到笛卡尔坐标系下的点A、B、M映射到参数空间中实际上是线,而笛卡尔坐标系中的直线AB、直线BM映射到参数空间中实际上是点E、F。即霍夫空间的对偶性。但由于垂直于X轴的直线,其斜率k无穷大、不存在,所以会导致点M、Z在参数空间中对应的线是平行的,没有交点,即该参数空间下无法描述k不存在的直线

极坐标系下的参数空间

figure 2.jpeg

直线l在极坐标系下的方程如下所示:

则对于直线l上任意一点Q而言,我们有:

figure 3.png

联立(1)、(2)式,可求得点Q在极坐标系下的参数空间方程

figure 4.png

这样我们就可以实现极坐标系与参数空间之间的映射

figure 5.jpeg

可以看到笛卡尔坐标系下的点A、B、M映射到极坐标系下的参数空间中实际上是线,而笛卡尔坐标系中的直线ABM映射到极坐标系下的参数空间中实际上是点F。即同样具备对偶性。且对于平行于X或Y轴的直线也可以很好映射到参数空间下,保证其有交点

直线检测

介绍完了Hough Transform之后,我们对于平面上的散点集中的直线检测就简单很多了。先通过极坐标系的参数空间将平面的散点集一一映射到其中,然后在参数空间中找出曲线相交较多的点,则其即为原散点集中被检测出的直线。故依据上图,我们可判定参数空间中的F点即为原散点集中被检测到的直线。通过Hough Transform,可以大大提高直线检测的效率

Note:

对于圆、椭圆等形状的检测,同样可以通过 Hough Transform 方法实现

0%