霍夫变换是一种特征提取技术，用于图像分析、计算机视觉、模式识别和数字图像处理。其目的是通过投票程序来寻找某一类形状中不完美的对象实例。该投票程序在参数空间中进行，算法显式构建的累加器空间中的局部最大值即为候选对象。在数学上，它是平面上的拉东变换，至少自1917年起就为人所知，但霍夫变换特指其在图像分析中的应用。
经典霍夫变换最初关注的是识别图像中的直线，但此后已扩展到识别任意形状的位置，最常见的是圆或椭圆。如今普遍使用的变换形式由理查德·杜达和彼得·哈特于1972年发明，他们将其称为“广义霍夫变换”，以区别于保罗·霍夫1962年的相关专利。该技术由达娜·H·巴拉德通过1981年发表于期刊的文章《将霍夫变换推广到检测任意形状》在计算机视觉社区中推广开来。
历史
霍夫变换最初由保罗·霍夫于1959年为机器分析气泡室照片而发明。它于1962年作为美国专利3,069,654获得授权，并归属于美国原子能委员会，名称为“识别复杂图案的方法与手段”。该专利对直线使用了斜率-截距参数化，这会导致变换空间无界，因为斜率可以趋于无穷大。
如今普遍使用的rho-theta参数化首次由理查德·杜达和彼得·哈特在1972年发表于《美国计算机学会通讯》的论文《在图像中使用霍夫变换检测直线和曲线》中描述。这种参数化自至少20世纪30年代起就已是拉东变换的标准形式。弗兰克·奥戈尔曼和M·B·克洛斯于1976年在《IEEE计算机学汇刊》上发表了变体，题为《通过特征点的共线性寻找图像边缘》。现代形式如何被发明的故事详见彼得·哈特2009年发表于《IEEE信号处理杂志》的文章《霍夫变换是如何被发明的》。
理论
在数字图像的自动化分析中，经常出现检测简单形状（如直线、圆或椭圆）的子问题。边缘检测器可作为预处理阶段，用于获取所需曲线上的图像点。然而，由于图像数据或边缘检测器的缺陷，可能存在缺失点或理想形状与噪声边缘点之间的空间偏差。霍夫变换通过对一组参数化的图像对象执行显式投票程序来解决这一问题，从而能够将边缘点分组为对象候选。
检测直线
最简单的情况是检测直线。一般来说，直线y = mx + b可以表示为参数空间中的点(b, m)，但垂直线会因斜率值无界而带来问题。杜达和哈特提出使用黑塞标准形式：r = x cos(theta) + y sin(theta)，其中r是从原点到直线上最近点的距离，theta是x轴与连接原点到该最近点的线段之间的角度。直线上的每个向量都垂直于从原点出发的长度为r的线段。交点位于P0 = (r cos(theta), r sin(theta))。对于直线上的任意点P，向量P - P0必须与P0正交，即满足(P - P0)点积P0 = 0，这简化为r(x cos(theta) + y sin(theta)) = r^2(cos^2(theta) + sin^2(theta))。
算法与投票程序
在实践中，霍夫变换将参数空间离散化为累加器数组。对于图像中的每个边缘点，算法计算所有可能对应于穿过该点的形状的参数值（例如，直线的r和theta），并递增相应的累加器单元。处理完所有点后，累加器中的局部最大值指示可能的形状候选。该投票程序对噪声和缺失数据具有鲁棒性，因为它不要求形状上的所有点完美对齐。
扩展与应用
由达娜·巴拉德于1981年提出的广义霍夫变换，通过使用参考点和边缘方向表将技术扩展到任意形状。这使得检测超出直线、圆和椭圆的复杂形状成为可能。该变换已广泛应用于自动驾驶、医学成像和工业检测等领域。在Computer vision系统中，它常与边缘检测算法结合使用，以在数字图像处理流程中识别对象。其在拉东变换中的数学基础将其与Machine learning和Artificial intelligence应用中更广泛的图像分析技术联系起来。
局限性与变体
经典霍夫变换的一个局限性是其计算成本，尤其是在高维参数空间中。诸如概率霍夫变换和霍夫圆变换等变体已被开发以提高效率。概率版本对边缘点进行子采样以减少计算，而圆变换则使用三维参数空间（中心x、中心y、半径）。这些变体通常在opencv等库中实现，并用于实时系统，包括自动驾驶车辆和Robotics中的系统。
参见
- radon-transform
- edge-detection
- Computer vision
- image-processing