代码收藏家 第16章：霍夫变换
第16章：霍夫变换
最初的霍夫变换只能用于检测直线，经过发展后，霍夫变换不仅能够识别直线，还能识别其他简单的图形结构，常见的有圆、椭圆等。实际上，只要是能够用一个参数方程表示的对象，都适合用霍夫变换来检测。
下面主要介绍霍夫直线变换和霍夫圆变换。
一、霍夫直线变换：
OpenCV 提供了函数 cv2.HoughLines()和函数 cv2.HoughLinesP()用来实现霍夫直线变换。下面首先介绍霍夫变换的基本原理，然后分别介绍这两个函数的基本使用方法。
1. 霍夫直线变换原理：
为了方便说明问题，先以我们熟悉的笛卡儿坐标系(即平面直角坐标系，与笛卡儿空间对应)为例来说明霍夫变换的基本原理。与笛卡儿坐标系对应，我们构造一个霍夫坐标系(对应于霍夫空间)。在霍夫坐标系中，横坐标采用笛卡儿坐标系中直线的斜率k，纵坐标使用笛卡儿坐标系中直线的截距b。
首先，我们观察笛卡儿空间中的一条直线在霍夫空间内的映射情况。例如下图中，左图是笛卡儿x-y坐标系(笛卡儿空间)，右图是霍夫k-b坐标系(霍夫空间)。在笛卡儿空间中，存在着一条直线y=k0x+b0，该直线的截距k0是已知的常量，截距b0也是已知的常量。将该直线映射到霍夫空间内，找到已知的点(k0,b0)，即完成映射。
从上述分析中可知，笛卡儿空间内的一条直线，其斜率为k，截距为b，映射到霍夫空间内成为一个点(k,b)。或者，可以这样理解，霍夫空间内的一个点(k0,b0)，映射到笛卡儿空间，就是一条直线y=k0x+b0。
这里，我们用“映射”这个词表达不同的空间(坐标系)之间的对应关系，也可以表述为“确定”。例如，上述关系可以表述为：
接下来，观察笛卡儿空间中的一个点在霍夫空间内的映射情况。如下图所示，在笛卡儿空间内存在一个点(x0,y0)，通过该点的直线可以表示为y0=kx0+b。其中，(x0,y0)是已知的常量，(k,b)是变量。
对于表达式y0=kx0+b，通过算术运算的左右移项，可以表示为b=−x0k+y0。将点(x0,y0)映射到霍夫空间时，可以认为对应的直线斜率为−x0，截距为y0，即b=−x0k+y0，如下图中右图的直线所示。
从上述分析可知：
下面我们看看笛卡儿空间中的两个点映射到霍夫空间的情况。例如，在下图中，左图的笛卡儿空间中存在着两个点(x0,y0)、(x1,y1)，分析这两个点映射到霍夫空间的情况。
为了方便理解，我们从不同的角度分析笛卡儿空间中这两个点到霍夫空间的映射情况。
角度1：笛卡儿空间的一个点会映射为霍夫空间的一条线。
在笛卡儿空间内，存在着任意两个点(x0,y0)、(x1,y1)。在霍夫空间中，这两个点对应着两条不同的直线。当然，通过分析可知，一条直线是b=−x0k+y0，另外一条直线是b=−x1k+y1。
角度2：笛卡儿空间的一条线会映射为霍夫空间的一个点
在笛卡儿空间内，存在着任意两个点(x0,y0)、(x1,y1)。这两个点一定能够用一条直线连接，将连接它们的直线标记为y=k1x+b1，则该直线的截距和斜率是(k1,b1)。也就是说，该直线在霍夫空间内映射为点(k1,b1)。
从上述分析可知：
换句话说，角度1决定了线条的数量，角度2决定了两条线相交的点。
这说明，如果在笛卡儿空间内有两个点A、B，它们能够连成一条直线y=k1x+b1，那么在霍夫空间中的点(k1,b1)上会有两条直线，分别对应着笛卡儿空间内的两个点A、B。
下面我们看看笛卡儿空间中的三个点映射到霍夫空间的情况。在下图中，左图是笛卡儿空间，其中存在(0,1)、(1,2)、(2,3)三个点。
下面从不同的角度分析笛卡儿空间中这三个点映射到霍夫空间的情况。
角度1：笛卡儿空间内的一个点会映射为霍夫空间的一条线。
例如，笛卡儿空间中的(0,1)、(1,2)、(2,3)三个点映射到霍夫空间时，每个点对应着一条直线，对应关系如表所示。
根据对应关系可知：
从上述分析可知，笛卡儿空间内的三个点映射为霍夫空间内的三条直线。
角度2：笛卡儿空间内的一条线会映射为霍夫空间的一个点。
例如，笛卡儿空间中的(0,1)、(1,2)、(2,3)三个点对应着直线y=x+1，斜率k为1，截距b为1。该直线y=x+1 映射到霍夫空间内的点(1,1)。
从上述角度1和角度2的分析可知：
这说明，如果在笛卡儿空间内有三个点，并且它们能够连成一条y=k1x+b1的直线，那么在霍夫空间中，对应的点(k1,b1)上会有三条直线，分别对应着笛卡儿空间内的三个点。
到此，我们已经发现，如果在笛卡儿空间内，有N个点能够连成一条直线y=k1x+b1，那么在霍夫空间内就会有N条直线穿过对应的点(k1,b1)。或者反过来说，如果在霍夫空间中，有越多的直线穿过点(k1,b1)，就说明在笛卡儿空间内有越多的点位于斜率为k1，截距为b1的直线y=k1x+b1上。
现在，我们看一个在笛卡儿空间内更多个点映射到霍夫空间的例子，也验证一下上述观点。在下图中，左图所示的是笛卡儿空间，其中有6个点，下面从不同的角度看下这6个点在右图霍夫空间的映射情况。
笛卡儿空间中的6个点：(0,1)、(1,2)、(2,3)、(3,4)、(3,2)、(1,4)，映射到霍夫空间时，每个点对应着一条直线，对应关系如表所示
根据对应关系可知：
从上述分析可知，笛卡儿空间内的6个点映射为霍夫空间内的6条直线
角度2：笛卡儿空间的一条线会映射为霍夫空间的一个点。
这里为了观察方便，将笛卡儿空间内连接了较多点的线绘制出来：连接点(0,1)、(1,2)、(2,3)、(3,4)的线LineA，连接点(2,3)、(3,2)、(1,4)的线LineB，连接点(0,1)、(3,2)的线LineC
需要注意，在笛卡儿空间内，各个点之间存在多条直线。例如在点(1,2)、(3,2)之间，点(3,2)、(3,4)之间，点(1,4)、(3,4)之间都存在着直线，这里做了简化，没有将上述直线都绘制出来。
下面分析笛卡儿空间内的三条直线LineA、LineB、LineC在霍夫空间内的映射情况。
在上图中可以看到，右图所示的霍夫空间内点A有4条直线穿过，点B有3条直线穿过，点C有2条直线穿过。分析上述关系：
综上所述，在霍夫空间内，经过一个点的直线越多，说明其在笛卡儿空间内映射的直线，是由越多的点所构成(穿过)的。我们知道，两个点就能构成一条直线。但是，如果有一个点是因为计算错误而产生的，那么它和另外一个点，也会构成一条直线，此时就会凭空构造出一条实际上并不存在的直线。这种情况是要极力避免的。
因此，在计算中，我们希望用更多的点构造一条直线，以提高直线的可靠性。也就是说，如果一条直线是由越多点所构成的，那么它实际存在的可能性就越大，它的可靠性也就越高。
因此，霍夫变换选择直线的基本思路是：选择有尽可能多直线交汇的点。
上面都是以我们熟悉的笛卡儿空间为例说明的。在笛卡儿空间中，可能存在诸如x=x0的垂线LineA的形式
此时，斜率k为无穷大，截距b无法取值。因此，上图中的垂线LineA无法映射到霍夫空间内。为了解决上述问题，可以考虑将笛卡儿坐标系映射到极坐标系上，如图所示。
在笛卡儿坐标系内使用的是斜率k和截距b，即用(k,b)表示一条直线。在极坐标系内，采用极径r(有时也用ρ表示)和极角θ来表示，即(r,θ)来表示。极坐标系中的直线可以表示为：
例如，上图中的直线LineA，可以使用极坐标的极径r和极角θ来表示。其中，r是直线LineA与图像原点O之间的距离，参数θ是直线LineA的垂线LineB与x轴的角度。在这种表示方法中，图像中的直线有一个(0~π)的角θ，而r的最大值是图像对角线的长度。用这种表示方法，可以很方便地表示上图中的3个点所构成的直线。
与笛卡儿空间和霍夫空间的映射关系类似：
一般来说，在极坐标系内的一条直线能够通过在霍夫坐标系内相交于一点的线的数量来评估。在霍夫坐标系内，经过一个点的线越多，说明其映射在极坐标系内的直线，是由越多的点所构成(穿过)的。因此，霍夫变换选择直线的基本思路是：选择由尽可能多条线汇成的点。
通常情况下，设置一个阈值，当霍夫坐标系内交于某点的曲线达到了阈值，就认为在对应的极坐标系内存在(检测到)一条直线。
上述内容是霍夫变换的原理，即使完全不理解上述原理，也不影响我们使用OpenCV提供的霍夫变换函数来进行霍夫变换。OpenCV本身是一个黑盒子，它给我们提供了接口(参数、返回值)，我们只需要掌握接口的正确使用方法，就可以正确地处理图像问题，无须掌握其内部工作原理。
在某种情况下，OpenCV库和Photoshop等图像处理软件是类似的，只要掌握了它们的使用方法，就能够得到正确的处理结果。在进行图像处理时，并不需要我们关注其实现原理等技术细节。但是，如果我们进一步了解其工作原理，对我们的工作也是有大有裨益的。
2. HoughLines函数：
OpenCV 提供了函数 cv2.HoughLines()用来实现霍夫直线变换，该函数要求所操作的源图像是一个二值图像，所以在进行霍夫变换之前要先将源图像进行二值化，或者进行 Canny 边缘检测。
函数cv2.HoughLines（）的语法格式为：
注意：
使用函数 cv2.HoughLines（）检测到的是图像中的直线而不是线段，因此检测到的直线是没有端点的。所以，我们在进行霍夫直线变换时所绘制的直线都是穿过整幅图像的。
绘制直线的方法是，对于垂直方向的直线（不是指垂线，是指垂直方向上的各种角度的直线），计算它与图像水平边界（即图像中的第一行和最后一行）的交叉点，然后在这两个交叉点之间画线。对于水平方向上的直线，采用类似的方式完成，只不过用到的是图像的第一列和最后一列。
在绘制线时，所使用的函数是cv2.line（）。该函数方便的地方在于，即使点的坐标超出了图像的范围，它也能正确地画出线来，因此没有必要检查交叉点是否位于图像内部。遍历函数cv2.HoughLines（）的返回值lines
import cv2
import numpy as np
import matplotlib.pyplot as plt
img = cv2.imread('./buliding.jpg')
gray_img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
edges = cv2.Canny(gray_img, 50, 150, apertureSize=3)
rgb_img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
new_img = rgb_img.copy()
print(lines)
for line in lines:
rho, theta = line[0]
a = np.cos(theta)
b = np.sin(theta)
x0 = a * rho
y0 = b * rho
x1 = int(x0 + 1000 * (-b))
y1 = int(y0 + 1000 * (a))
x2 = int(x0 - 1000 * (-b))
y2 = int(y0 - 1000 * (a))
cv2.line(new_img, (x1, y1), (x2, y2), (0, 0, 255), 2)
plt.subplot(131)
plt.imshow(rgb_img)
plt.axis('off')
plt.subplot(132)
plt.imshow(edges)
plt.axis('off')
plt.subplot(133)
plt.imshow(new_img)
plt.axis('off')
plt.show()
补充：OpenCV中HoughLines两个点(x1, y1)，(x2, y2)是如何求出的。
上图显示怎么放大线段到1000即当r=1000时的计算方法。可以是300也可是500、800。
3. HoughLinesP函数：
概率霍夫变换对基本霍夫变换算法进行了一些修正，是霍夫变换算法的优化。它没有考虑所有的点。相反，它只需要一个足以进行线检测的随机点子集即可。
为了更好地判断直线（线段），概率霍夫变换算法还对选取直线的方法作了两点改进：
在OpenCV中通过cv2.HoughLinesP()函数实现概率霍夫变换：
如果两点间的间隔超过了参数maxLineGap的值，就认为这两点不在一条线上。默认值为0。
import cv2
import numpy as np
import matplotlib.pyplot as plt
img = cv2.imread('buliding.jpg')
grey_img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
rgb_img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
new_img = rgb_img.copy()
edges = cv2.Canny(grey_img, 150, 200, apertureSize=3)
lines = cv2.HoughLinesP(edges, 1, np.pi / 180, 100, minLineLength=100, maxLineGap=30)
for line in lines:
x1, y1, x2, y2 = line[0]
cv2.line(new_img, (x1, y1), (x2, y2), (255, 0, 0), 2)
plt.subplot(131)
plt.imshow(rgb_img)
plt.title('img')
plt.axis('off')
plt.subplot(132)
plt.imshow(edges)
plt.title('edges')
plt.axis('off')
plt.subplot(133)
plt.imshow(new_img)
plt.title('rst')
plt.axis('off')
plt.show()
2. 霍夫圆环变换：
霍夫变换除了用来检测直线外，也能用来检测其他几何对象。实际上，只要是能够用一个参数方程表示的对象，都适合用霍夫变换来检测。
用霍夫圆变换来检测图像中的圆，与使用霍夫直线变换检测直线的原理类似。在霍夫圆变换中，需要考虑圆半径和圆心（x坐标、y坐标）共3个参数。在OpenCV中，采用的策略是两轮筛选。第1轮筛选找出可能存在圆的位置（圆心）；第2轮再根据第1轮的结果筛选出半径大小。
与用来决定是否接受直线的两个参数“接受直线的最小长度（minLineLength）”和“接受直线时允许的最大像素点间距（MaxLineGap）”类似，霍夫圆变换也有几个用于决定是否接受圆的参数：圆心间的最小距离、圆的最小半径、圆的最大半径。
在OpenCV中，通过函数cv2.HoughCircles（）实现霍夫圆变换，**该函数将Canny边缘检测和霍夫变换结合。**其语法格式为：
需要特别注意，在调用函数 cv2.HoughLinesCircles（）之前，要对源图像进行平滑操作，以减少图像中的噪声，避免发生误判。
import cv2
import numpy as np
import matplotlib.pyplot as plt
img = cv2.imread('xiangqi.jpg')
gray_img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
rgb_img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
new_img = rgb_img.copy()
circles = cv2.HoughCircles(gray_img, cv2.HOUGH_GRADIENT, 1, 100, param1=100, param2=30, minRadius=50, maxRadius=100)
print(circles)
circles = np.uint16(np.around(circles))
print(circles)
for i in circles[0, :]:
cv2.circle(new_img, (i[0], i[1]), i[2], (255, 0, 0), 10)
# 圆心
cv2.circle(new_img, (i[0], i[1]), 2, (255, 0, 0), 10)
plt.subplot(121)
plt.imshow(rgb_img)
plt.title('img')
plt.axis('off')
plt.subplot(122)
plt.imshow(new_img)
plt.title('rst')
plt.axis('off')
plt.show()
来源：李淳罡Lichungang
