霍夫变换(Hough Transform)

简介

霍夫变换(Hough Transform)最初用于检测图像中的直线或者圆等几何图形,主要应用在图像分析、计算机视觉和数字图像处理领域。后来经过拓展,可适用于任意图形的检测,及一些参数取值的检测。

霍夫直线变换的基本思想

如果两点 (xi, yi) 和 (xj, yj) 都在一条直线上,那么它们在x-y平面上有相同的斜率和y轴的截距。

对于一个点 (xi, yi) ,经过直线 yi = axi + b,其中a为斜率,b为y轴截距。可以把该式改写为 b = (-xi)a+ yi ,使a为自变量,b为因变量,a可取[amin, amax],代入a可求出对应的b值。a和b的关系可以在参数空间(即a-b平面)上作图。把参数空间分隔为一个一个格子(累加器),然后把 (a, b) 对应的格子A(a, b) 加 1。
也就是说,一个点可以使参数空间的一系列累加器都加 1。

对于另外一个点 (xj, yj) ,把 yj = axj + b 改写为 b = (-xj)a+ yj ,作同样的操作,对应的一系列累加器加1。

然后把所有点都如法炮制。在参数空间中,必然有一些累加器的值是比较大的,这些累加器对应的 (a, b) 值便是原图中可能的直线的参数。

这样,即实现了把原始图像中给定直线的检测问题,转化为寻找参数空间的(局部)最大值问题。
然而,以上方法存在一个缺陷:若斜率不存在或无穷大,将导致a, b 的值也无穷大,需要无限个累加器,而这是不可能的。

因此,后来又提出了直线的另外一种表示方法:ρ = xcosθ + ysinθ,其中ρ是原点到直线上最近点的距离,θ是x轴与连接原点和最近点直线之间的夹角,如下图所示。

ρ = xcosθ + ysinθ 可由一开始的 y = ax + b 推得。斜率 a 等于 -cotθ,y 轴截距 b 等于 ρ/sinθ,即 y = -cotθ · x + ρ/sinθ。

因此,图像中的每一条直线可与一对参数 (ρ, θ) 相关联。这个参数(ρ, θ) 平面有时被称为霍夫空间,用于二维直线的集合。

由辅助角公式 asinx + bcosx = √(a²+b²)sin(x+arctan(b/a)) 可知,给定x和y的值,ρ = xcosθ + ysinθ 的图像将是一条正弦曲线。其中 -90°≤θ≤90°,-√2 D≤ρ≤√2 D,D为原图像的对角线长度。这样累加器的数目就可以控制,例如 θ 精确到 1°,ρ 取整。

所以我们可以得到一个结论,给定平面中的单个点,那么通过该点的所有直线的集合对应于 (ρ, θ) 平面中的一条正弦曲线

例子

下图是包含两条粗线的光栅图像上的霍夫变换结果的例子。右下图中,越亮的地方代表累加器越大的值,可以从中看出原图有2根直线。

对于下图中复杂一点的例子,其霍夫空间也会更复杂。可见值最高的3个累加器正确地找到了3条直线。

算法的实现

  1. 读取原始图并转换成灰度图,采用边缘检测算子(如Canny)转换成二值化边缘图像;
  2. 对该图像进行霍夫变换;
  3. 找到大于阈值的累加器,和对应的 ρ, θ 参数。

概率霍夫变换

用刚才的方法,找到的都是直线;而我们在实际应用中,可能更关心线段的提取。这就需要概率霍夫变换(Probabilistic Hough Transform)。

概率霍夫变换在 skimage、openCV 等库中均有实现,就不从底层开始推导了。它需要 minLineLength(线段的最短长度)和 maxLineGap(线段间允许的最大间隔,间隔之内的2条线段将被连接成1条线段)等参数。代码可参考文末的 openCV 文档。

例子
原图
边缘
使用概率霍夫变换后,提取的最长直线

霍夫圆变换

类似的,要在原图中定位圆,给定平面中的一个点且半径已知,则通过该点的所有圆的集合对应于一个圆,类似“3点确定一个圆”的原理。

而当半径未知,则可在一定半径范围内进行搜索。当然,这会使性能下降。

算法的实现

  1. 读取原始图并转换成灰度图,采用边缘检测算子(如Canny)转换成二值化边缘图像;
  2. 给定半径R,对于每个图像中的边缘点(a, b),按照参数方程 x = a + Rcos(θ) 和 y = b + Rsin(θ) 将那些可能是一个圆中心的单元格值进行累加;
  3. 找到大于阈值的累加器,和对应的 a, b 参数;
  4. 若半径未知,改变R的值,重复步骤2~3,直到遍历完半径范围。
例子
原图
霍夫空间
处理结果

相关参考

1. [Gonzalez and Woods] Rafael C. Gonzalez and Richard E. Woods, Chapter 10, Digital Image Processing, Second Edition, Pearson Education, Inc.
2. 经典霍夫变换(Hough Transform), https://blog.csdn.net/yuyuntan/article/details/80141392
3. openCV doc, https://docs.opencv.org/3.4.5/d6/d10/tutorial_py_houghlines.html
4. Harvey Rhody, Hough transformfor detecting circles

发表评论

验证码 *