霍夫变换与直线检测

背景

霍夫变换应该是在边缘检测的基础上的，如果要在如下这张图中做直线的检测，opencv有很多边缘检测的算法得到一个8bit的图，本文所述的霍夫变换的原理也是在这个边缘检测的结果上进行的

边缘检测结果

算法基础

极坐标变换

笛卡尔坐标系中的任意一点（x,y）都可以表示成ρ=x·cosθ+y·sinθ，的形式，而后者（ρ,θ）是极坐标。而在这个极坐标系下，一个（ρ, θ）是可以表示一条直线，如下图。

（ρ, θ）表示的直线

这样的直线的表示方式具有以下性质：

1. 极坐标中的一个点（ρ, θ）就表示笛卡尔坐标系中的一条直线
2. 笛卡尔坐标系中过某一个点（x,y）的所有直线在极坐标中变为一条正弦曲线

证明：假设点（x,y），令sinα=x/sqrt(x²+y²)，cosα=y/sqrt(x²+y²)。
ρ=sqrt(x²+y²)·(sinα·cosθ+cosα·sinθ)=sqrt(x²+y²)·sin(α+θ)。即表示一条振幅为sqrt(x²+y²)，相位为α的正弦曲线。

笛卡尔坐标系中过某一点的直线在极坐标下表示为一条正弦曲线

3. 笛卡尔坐标系中过点A和B的直线（直线AB），在极坐标系中表现为两条正弦曲线的相交（即一条正弦曲线表示过A的所有直线，一条正弦曲线表示过B的所有直线，两条正弦曲线的交点就表示直线AB）

这张图表明五点共线，就是五条正弦曲线交点处表示的那条直线

算法

现假设我们已经有上文中所述的边缘检测的结果，这个边缘检测的结果与原图等大，边缘检测结果中的值都是0-255之间的，假设一个原图为640*480，其中边缘点有n个（n<=640*480）。我们可以针对每一个边缘点在极坐标中画一条正弦曲线（上述的性质2），共n条正弦曲线。然后分别这些正弦曲线两两之间的交点坐标是多少（只需要0~π之间的交点即可），时间复杂度是n(n-1)/2。然后寻找穿过的线最多的交点，一个交点有越多的线，就表示有越多点共线。
上述的算法是很显然的，但是效率是O(n²)，太低了。因此[2]作者做了如下的改进：

1. 把ρ和θ离散化，例如ρ（-R<ρ<R）等分为2R份，步长为1，θ步长为1°，把180度等分180分。
2. 建立一个二维数组（accumulator array），大小为2R*180，数组中的每个元素代表经过当前（ρ,θ）的直线的点的数量。

这个例子θ步长为20°，ρ步长为2

步骤

1. 对每个点，找出他们在图中的坐标(x,y)
2. 根据公式ρ=x·cosθ+y·sinθ，把x,y和θ（以上图为例θ=0°、±20°、±40°、±60°……±160°）带入算出ρ，在找出accumulator array中找到对应的ρ并对数组中对应计数+1
3. 计算完所有点后，找出accumulator中最大的一些数（或设定一个阈值），他们的索引(ρ,θ)即为最后索引到的直线

OpenCV中的函数HoughLines

OpenCV中相关的函数有

cv2.HoughLinesP() # 与上述步骤略有不同
cv2.HoughLines() # 与上述步骤几乎完全相同
cv2.HoughCircles() # 利用霍夫变换画圆

其中，HoughLins中的参数，rho和theta的含义就是上述表格中的ρ和θ的步长，threshold是阈值，即accumulator中大于threshold的直线会被选出，代表至少有threshold个点经过了这条直线。min_theta和max_theta代表的是θ的范围。

可以看出，HoughLines这个函数的执行效率取决于rho、theta、min_theta和max_theta，当然，也取决于边缘检测结果中边缘像素的数量n。

参考文献

[1] P.V.C. Hough,Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959.

[2] Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures,"Comm. ACM, Vol. 15, pp. 11–15 (January, 1972).

[3] https://blog.csdn.net/songzitea/article/details/17027849

[4] https://blog.csdn.net/shanchuan2012/article/details/74010561