「基础算法」简单霍夫变换的源码实现

图像处理中，检测直线或者圆等有固定方程式表示的物体时，可以考虑用霍夫变换来做。

对于一个二值图像，

如下图：

这个变换的思路：

1 利用两点的坐标计算出直线的斜率k和截距b，由于k的取值有无穷大的值，表示起来不方便，所以将k用角度来表示，即arctan(k)得到直线与水平线的夹角。b其实也需要做一些映射，将[负无穷，正无穷]映射到[-N,N] 上。

2 取图像上任意一对点的坐标，计算他们对应直线的arctan(k), 和b 。不同的一对点，计算得到的arttan(k)，b有可能相同，如果两队点都共线。

3 假设图像上有M对点，那么我们一共得到M个 [arctan(k),b]

4 统计arctan(k)取值 -90度至90度之间，b取值-N,至N之间时，对应于每个特定的[arctan(k),b]的直线数目。比如统计出[arctan(k)=45度，b=0]对应的直线数据，统计出[arctan(k)=-20度，b=35]对应的直线数目。

最终，我们得到一个180*2N的矩阵，如下图：

可以看到，图片的右下部分最亮，图像的下边缘对应的是斜率接近90度的直线，说明原图中，存在垂直的直线。

图片的中间部分有数量不多的点，中间部分对应于斜率为零的直线，说明原图上有一些水平线。

以往都是直接调用opencv库的，但是有些情况下，是不能调用库的，必须自己写了，

下面是我写的代码：

 60 def get_line_list(point_list):
 61     import numpy as np
 62     k_dist_list=np.zeros(181)
 63     k_b_matrix=np.zeros((181,181))
 64     N=len(point_list)
 65     for i in range(0,N):
 66         p1 = point_list[i]
 67         for j in range(i+1,N):
 68             p2 = point_list[j]
 69             dist,k,b=get_line_coef_length(p1,p2)
 70             if np.abs(b)<=90:
 71                 k_b_matrix[k,int(b+90)]+=1
 72             if dist>k_dist_list[k]:
 73                 k_dist_list[k]=dist
 74     return k_dist_list,k_b_matrix

point_list是python中的list,里面取的就是上面二值图上所有点的坐标。

63行声明了一个矩阵：181*181的

69行计算了两个点p1,p2所在直线的斜率k和截距b,

71行是统计语句，将矩阵中k行，int(b+90)位置+1，遇到斜率为k,截距为int(b+90]的直线时，就在矩阵中相应位置+1.

这里主要有个函数get_line_coef_length,代码如下：

44 def get_line_coef_length(p1,p2):
 45     import numpy as np
 46     x1,y1=p1
 47     x2,y2=p2
 48     xe=x1-x2
 49     ye=y1-y2
 50     dist = np.sqrt(xe*xe+ye*ye)
 51     k=float(y2)-float(y1)
 52     if x2-x1==0:
 53         return dist,180,y1
 54     k=k/(float(x2)-float(x1))
 55     k_theta = int(np.arctan(k)/3.14*180.0+90.0)
 56     b = y1-k*x1
 57     #线段长度，角度
 58     return dist,k_theta,b

51行--55行是计算斜率的，这里当斜率为无穷大时，我们将其设定为180，为什么呢？

因为角度的取值范围是[-90,90],这个下标是从-90开始的，但是我们矩阵k_b_matrix的下标是从零开始的，所以将[-90,90]映射到了[0,180].

也正是因为如此，在55行，有个+90.0.

这就是霍夫变换了，原理简答，比形态学的方法找直线好用很多。

需要整份代码的可以私信我。

另外我这里有源码写的提取联通区域，计算联通区域最小外接矩形，没有调用任何库，可以写在任何设备上，需要的话，可以向我咨询。

我这里还有几个例子：