霍夫变换与直线检测霍夫变换与直线检测

背景霍夫变换应该是在边缘检测的基础上的，如果要在如下这张图中做直线的检测，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<ρ
建立一个二维数组（accumulator array），大小为2R*180，数组中的每个元素代表经过当前（ρ,θ）的直线的点的数量。

文章图片
这个例子θ步长为20°，ρ步长为2 步骤

对每个点，找出他们在图中的坐标(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