Hough Transform 霍夫变换原理

Hough Transform 霍夫变换

原理

 在笛卡尔坐标系中，一条直线由两个A=(x1, y1)和B=(x1, y2)确定，如下图：

 将直线y=kx + b可写成关于(k, q)的函数表达式:

 对应的变换通过图形直观的表示如下图：

 变换后的空间我们叫作霍夫空间。即：笛卡尔坐标系中的一条直线，对应于霍夫空间中的一个点。反过来，同样成立，霍夫空间中的一条线，对应笛卡尔坐标系中的一个点，如下图所示：

 我们再来看下A、B两个点，对应霍夫空间的情形：

 A映射到霍夫空间中是一条直线，B也映射到霍夫空间中的一条直线，这两条直线在霍夫空间中有一个交点。这个交点就表示了笛卡尔坐标系中由A、B两点所构成的直线的斜率和截距。
 再看一下三点共线的情况，如下图：

 可以看出，如果笛卡尔坐标系的点共线，那么这些点在霍夫空间中对应的直线交于一点。
 如果不止一条直线，如下图所示：

 我们选择尽可能多的直线汇成的点，上图中三条直线汇成A、B两点，将其对应回笛卡尔坐标系中的直线如下图所示：

 到这里，我们似乎已经完成了霍夫变换的求解，但如果像下图这种情况时：

 上图中，直线的斜率是不存在的。为了解决这个问题，我们考虑将笛卡尔坐标系转为极坐标。

 在极坐标下是一样的，极坐标中的点对应霍夫空间的线，这是的霍夫空间参数不再是(k, q)了，而是(ρ, θ)的空间，ρ是原点到直线的垂直距离，θ表示直线的垂线与横轴顺时针方向的夹角，垂直线的角度为0度，水平线的角度是180度。

 我们只需要求得霍夫空间中的交点的位置，即可得到原坐标系下的直线。

实现流程

 假设有一个大小是100x100的图片，使用霍夫变换检测图片中的直线，则步骤如下：

• 直线都可以用(ρ, θ)表示，首先创建一个2D数组，我们可以叫作累加器，初始化所有制为0，行表示ρ，列表示θ。
  
  该数组的大小决定了结果的准确性，若希望角度的精度为1度，那就需要180列。对于ρ，最大值为图片对角线的距离，如果希望精度达到像素级别，行数应该与图像的对角线距离相等。

• 取二值图轮廓边缘的的第一个点(x, y)，将其带入直线的极坐标公式中，然后遍历θ的取值：0，1，2，…，180，分别求出对应的ρ值，如果这个数值在上述累加器中存在对应的位置，则该位置加1。

• 取二值图轮廓边缘的的第一个点(x, y)，重复上述步骤，更新累加器。

• 搜索累加器中的最大值，并找到对应的(ρ,θ)，就可将图像中的直线表示出来。