背景
霍夫变换应该是在边缘检测的基础上的，如果要在如下这张图中做直线的检测，opencv有很多边缘检测的算法得到一个8bit的图，本文所述的霍夫变换的原理也是在这个边缘检测的结果上进行的
算法基础
极坐标变换
笛卡尔坐标系中的任意一点（x,y）都可以表示成ρ=x·cosθ+y·sinθ，的形式，而后者（ρ,θ）是极坐标。而在这个极坐标系下，一个（ρ, θ）是可以表示一条直线，如下图。
这样的直线的表示方式具有以下性质：
- 极坐标中的一个点（ρ, θ）就表示笛卡尔坐标系中的一条直线
- 笛卡尔坐标系中过某一个点（x,y）的所有直线在极坐标中变为一条正弦曲线
证明：假设点（x,y），令sinα=x/sqrt(x2+y2)，cosα=y/sqrt(x2+y2)。
ρ=sqrt(x2+y2)·(sinα·cosθ+cosα·sinθ)=sqrt(x2+y2)·sin(α+θ)。即表示一条振幅为sqrt(x2+y2)，相位为α的正弦曲线。
- 笛卡尔坐标系中过点A和B的直线（直线AB），在极坐标系中表现为两条正弦曲线的相交（即一条正弦曲线表示过A的所有直线，一条正弦曲线表示过B的所有直线，两条正弦曲线的交点就表示直线AB）
算法
现假设我们已经有上文中所述的边缘检测的结果，这个边缘检测的结果与原图等大，边缘检测结果中的值都是0-255之间的，假设一个原图为640*480，其中边缘点有n个（n<=640*480）。我们可以针对每一个边缘点在极坐标中画一条正弦曲线（上述的性质2），共n条正弦曲线。然后分别这些正弦曲线两两之间的交点坐标是多少（只需要0~π之间的交点即可），时间复杂度是n(n-1)/2。然后寻找穿过的线最多的交点，一个交点有越多的线，就表示有越多点共线。
上述的算法是很显然的，但是效率是O(n2)，太低了。因此[2]作者做了如下的改进：
- 把ρ和θ离散化，例如ρ（-R<ρ<R）等分为2R份，步长为1，θ步长为1°，把180度等分180分。
- 建立一个二维数组（accumulator array），大小为2R*180，数组中的每个元素代表经过当前（ρ,θ）的直线的点的数量。
步骤
- 对每个点，找出他们在图中的坐标(x,y)
- 根据公式ρ=x·cosθ+y·sinθ，把x,y和θ（以上图为例θ=0°、±20°、±40°、±60°……±160°）带入算出ρ，在找出accumulator array中找到对应的ρ并对数组中对应计数+1
- 计算完所有点后，找出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
