霍夫变换是一种找出图形的方法。我们在计算机中处理图像。图像由很多小点组成。这些小点叫做像素。每个像素有它的位置。像素还有颜色信息。我们想找到图像里的直线或者圆。人眼很容易看出直线和圆。计算机不行。计算机只认识数字。我们需要一种数学办法告诉计算机。

我们来看怎么找直线。一条直线可以用方程表示。最简单的方程是y等于kx加b。k是直线的斜率。b是直线在y轴上的截距。图像空间里每一个点对应一条直线。反过来一条直线对应很多点。图像里可能有几个点在同一条直线上。这些点就是我们要找的直线。

霍夫变换换了一个思路。我们不直接在图像里找直线。我们去参数空间里找。什么是参数空间？我们有两个参数k和b。k和b可以组成一个平面。这个平面就是参数空间。图像里的一个点对应参数空间里的一条直线。为什么？因为对于一个固定的点，很多直线可以经过它。这些直线的k和b满足一个关系。这个关系就是b等于负xk加y。这是一个直线方程。x和y是图像里点的坐标。所以图像空间的一个点变成参数空间的一条直线。

如果图像里有三个点在一条直线上。这三个点每个点对应参数空间的一条直线。这三条直线会交于一点。这个交点就是我们要的k和b。它代表图像里穿过这三个点的直线。计算机的工作就是在参数空间找交点。交点越多的参数说明它对应的直线越可能存在于图像中。

实际使用中，y等于kx加b有一个问题。当直线垂直时，k变成无穷大。这不好计算。所以我们换一种直线表示法。我们用极坐标方程。直线方程写成r等于x乘cosθ加y乘sinθ。r是原点到直线的距离。θ是直线的法线与x轴的夹角。这样任何直线都可以表示。没有无穷大的问题。

霍夫变换的步骤是这样的。第一步，我们得到一张图像。图像可能是彩色的。我们把它变成黑白。然后我们检测图像的边缘。边缘是图像里颜色变化很大的地方。物体的边界通常就是边缘。有很多算法可以找边缘。比如Canny边缘检测算法。找完边缘我们得到一个二值图像。图像里只有两种值。一种是白色代表边缘点。一种是黑色代表背景。

第二步，我们初始化参数空间。参数现在是r和θ。r的范围是从负图像对角线长度到正图像对角线长度。θ的范围是从0度到180度。我们把参数空间分成很多小格子。每个小格子是一个累加器。开始所有累加器都是零。

第三步，我们遍历图像里的每个边缘点。对于每个边缘点，我们尝试所有可能的θ值。θ从0变到180。每一步增加一度。对于每个θ，我们用公式算出r。r等于x乘cosθ加y乘sinθ。x和y是边缘点的坐标。cos和sin需要把角度变成弧度计算。算出的r可能不是整数。我们把它四舍五入到最近的整数。然后我们找到对应的累加器。这个累加器的位置是(r,θ)。我们把这个累加器的值加一。

第四步，所有边缘点处理完后，我们查看参数空间。累加器值大的地方就是可能的直线。因为很多边缘点贡献给了同一个(r,θ)。我们设定一个阈值。比如只有累加器值大于50的我们才考虑。我们找到所有超过阈值的累加器。每个这样的累加器对应一条直线。我们用(r,θ)值可以还原出直线方程。然后在原图像上画出这条直线。

霍夫变换也可以找圆。圆的方程更复杂。圆需要三个参数。圆心坐标(a,b)和半径r。所以参数空间变成三维。图像空间的一个点对应参数空间的一个圆锥面。如果多个点在同一个圆上，这些圆锥面会交于一点。这个点就是圆的参数(a,b,r)。三维参数空间需要更多计算。内存也需要更多。我们有一些办法减少计算量。比如我们知道圆的半径范围。我们可以限定r的最小值和最大值。这样搜索空间变小了。

找圆的霍夫变换步骤类似。第一步还是检测边缘。第二步初始化三维累加器数组。参数是a、b和r。第三步对于每个边缘点，我们尝试所有可能的半径r。对于每个r，我们根据圆的方程算出可能的圆心。圆心在一个圆周上。我们把这个圆周上的所有累加器加一。第四步找到累加器值大的位置。这些位置就是可能的圆。

霍夫变换有很多应用。交通监控中识别车道线。车道线一般是直线。我们可以用霍夫变换找到它们。工业检测中零件上的孔洞。孔洞是圆形。霍夫变换可以找出这些圆。医学图像中细胞的轮廓。细胞近似圆形。霍夫变换可以帮助计数。文档分析中表格的线条。表格由直线组成。霍夫变换可以提取这些直线。

霍夫变换有一些优点。它对噪声不敏感。图像里有一些杂点没关系。几个点不对齐也不影响。因为它基于投票机制。只有足够多的点同意才形成直线。它对部分遮挡有效。物体被挡住一部分。剩下的边缘点依然可以投票。它可以找出多个图形。一次处理能找到所有直线和圆。

霍夫变换也有缺点。它计算量很大。特别是参数空间维度高的时候。找圆比找直线慢很多。它需要大量内存。累加器数组可能非常大。它可能找到错误的图形。如果阈值设得不对，会有误检。它不能处理复杂图形。只能处理能用简单方程表示的图形。

人们提出很多改进方法。概率霍夫变换只使用一部分边缘点。随机选一些点进行投票。这样计算更快。渐进概率霍夫变换一边投票一边检测。找到一条直线就移除相关点。然后继续找下一条。圆霍夫变换用梯度信息减少计算。边缘点的梯度方向指向圆心。这样可以缩小圆心搜索范围。

霍夫变换的实现很简单。很多计算机视觉库都有现成函数。OpenCV是一个常用的库。它提供霍夫直线变换和霍夫圆变换函数。我们只需要输入图像。设定一些参数。比如阈值和最小距离。函数返回找到的直线或圆。我们可以直接在图像上画出结果。

我们用一个例子说明。假设我们有一张道路图片。图片中有两条车道线。图片可能有点模糊。天空中有云。路面上有影子。我们想自动检测车道线。首先把彩色图片变成灰度图片。然后使用Canny算法找边缘。我们得到一个边缘图像。白色线条是边缘。大部分边缘是车道线的。也有一些是其他物体的。

我们应用霍夫直线变换。设定阈值参数。累加器值超过30的我们认为是直线。我们得到很多直线参数。有些直线很短。有些直线是倾斜的。我们过滤掉水平方向的直线。车道线一般是倾斜的。我们合并相近的直线。最后得到两条主要的直线。这两条线就是车道线。我们在原图上用红色画出这两条线。这样我们就完成了车道线检测。

另一个例子是检测硬币。我们有一张硬币图片。图片中有几个硬币。可能有些重叠。我们想数一数有几个硬币。首先还是检测边缘。然后使用霍夫圆变换。我们知道硬币的大小范围。我们设定半径的最小值和最大值。我们设定圆心之间的最小距离。这样同一个硬币不会检测多次。我们得到一系列圆参数。每个圆对应一个硬币。我们数一数圆的个数。这就是硬币的数量。我们在每个硬币上画一个绿色圆圈。

霍夫变换的基本思想就是这样。它是一种投票机制。图像空间的问题变成参数空间的问题。在参数空间找聚集点。这些点对应图像中的图形。这个方法很通用。它可以扩展到其他图形。椭圆可以用五个参数表示。参数空间是五维的。理论上霍夫变换可以处理任何能用方程表示的图形。实际中受限于计算能力。

霍夫变换是计算机视觉的基础工具。它出现在很多教材中。它帮助计算机理解图像中的简单形状。虽然现在有更先进的深度学习方法。但霍夫变换仍然有用。它简单可靠。不需要训练数据。在很多实际系统中还在使用。