Hough 变换及在图像直线检测中的应用

前言

我们接着上一篇直线平面空间(x,y plane)和标准参数化空间(normal parameterization)的转换及其性质的基础篇来继续深入并且使用 Hough 变换来检测图像中存在的直线或圆形。

Hough 变换

在前言提到的直线参数化的文章就是直线的 Houg 变换,就是直线的平面坐标转换成参数化坐标,这里就不详细讲了,可以参见直线平面空间(x,y plane)和标准参数化空间(normal parameterization)的转换及其性质及里面的参考文献。这里主要讲下圆的 Hough 变换,其实也很简单的。
我们知道,平面坐标的圆的基本表达式为:

$$\left ( x - a \right )^{2} + \left ( x - b \right )^{2} = c^{2}$$

那么图像上的任意点$(x_{i}, y_{i})$,转换成由 3 个参数$(a, b, c)$空间定义的面:

$$(x_{i} - a)^2 + (y_{i} - b)^2 = c^2$$

上述的式子表示,每个图像上点会转换成一个三维参数空间的直立圆锥。如果这些对应于图像上的点的圆锥相较于一个点$(a_{0}, b_{0}, c_{0})$,那么这些图像上的点都位于由这三个特定参数$(a_{0}, b_{0}, c_{0})$定义的圆上,即:

$$(x - a_{0})^2 + (y - b_{0})^2 = c_{0}^2$$

对于计算过程,我们可以使用代表三维参数空间的三维数组累加器,具体的计算会在下一节讲解。

算法过程及其理解

现在讲讲直线参数化后,如何使用参数化后的直线来寻找平面坐标下的图像直线。
一般地,n 条曲线会相交于 $n(n - 1) / 2$ 个点,这些点对应于平面坐标的图像点对的直线。原则上,我们可以通过在参数空间找相交的一致点,从而能找到图像点的共线点集(参数空间中相交于同一点的曲线对应的平面上的点集就是共线的点集)。但是,这个过程会因为图像点集数的增加而使计算耗时爆发式增长。
所以,我们可以使用 Hough 提出的解析代数的方法进行寻找。
首先,我们指定可接受的 $\theta, \rho$ 误差,并且网格化 $\theta-\rho$坐标平面。$\theta, \rho$网格化值区间定义为:

$$0 \leqslant \theta < \pi \\ - R \leq \rho \leq R$$

其中,$R$表示视网膜的大小(这个可以这样理解:眼睛所看到的范围)。
对于网格化后的值,比如,$\theta$被划分为$d_{1}$个值,$\rho$被划分为$d_{2}$个值,那么$\theta$的值分别为$0$,$\pi / d_{1}$,$2\pi / d_{1}$,...,$\pi$,类似地,$\rho$的值分别为$-R$,$-R + \frac{2R}{d_{2}}$,...,$R$。
之后,我们使用以这些量化后的$\theta, \rho$值作为下标值的二维累加器数组来记录参数化曲线进入每个小网格的次数。
小网格所表示的含义:相当于每条曲线相交的点所处的位置。小网格就是相交的位置。

算法过程:
step1:对于每个图像上的点(像素点),转换成参数化曲线;
step2:对参数 $ \theta, \rho $ 进行量化;
step3:取$ \theta $量化后的每个值,根据式$ \rho = x_{1}cos\theta + y_{1}sin\theta $计算对应的$\rho$值;
step4:记录由step3计算的$ \theta, \rho $,来记录step1的曲线进入各小网格的次数;
step5:从二维数组累加器中获得值相对大的元素所对应的曲线,这些曲线所对应的平面坐标的点就是共线的点;
step6:step5的各点集进行连接就是图像上的直线;
step7:完成。

算法实例

暂略

优缺点

  1. 识别的结果对$ \theta, \rho $的量化值比较敏感;好的量化值会有更好的分辨率,但这会增加计算时间,并且会有接近共线的点会聚集在二维累加器数组的几个元素内(即本来是一条线的,但量化值过小会导致无意义的多条线)。
  2. 量化值过小会导致把不相近的点识别为共线的点。这种不相关的点会导致正常直线段扭曲。另外,基于此,有些无意义的点也会被识别为共线。

参考文献

use-of-the-hough-transformation-to-detect-lines-and-curves-in-pictures

系列文章

直线平面空间(x,y plane)和标准参数化空间(normal parameterization)的转换及其性质

追求梦想,做最好的自己