来源： Hello AI World

引言

本文讲述霍夫变换的一些内容，并加入一些理解性东西，参考了部分博客等相关性内容。希望能对霍夫变换有所了解，也希望看到的人如果发现错误及时帮忙纠正。博主水平有限，还望赐教。

历史和简介

历史

霍夫变换（Hough Transform） 是在1959年由气泡室（Bubble Chamber）照片的机器分析而发明，发明者Paul Hough在1962年获得美国专利，被命名为Method and Means for Recognizing Complex Patterns（用于识别复杂图案的方法和手段）。该专利对直线采用斜截距参数化，但由于斜率可能变成无穷大，这有可能导致无限变换空间（unbounded transform space）。

现在使用的霍夫变换是1972年由 Richard Duda 和 Peter Hart 所发明，称为“广义霍夫变换[GHT]”（Use of the Hough Transformation to Detect Lines and Curves in Pictures，1972）。

然后1981年在 Dana H. Ballard 的计算机视觉社区中出现一篇文章名为 Generalizing the Hough transform to detect arbitrary shapes，从而推广开来。

该文描述了使用模板匹配原理对霍夫变换进行修改。要知道霍夫变换最初是为了分析定义的形状（如线、圆、椭圆等）而开发。通过了解其形状并旨在其找出图像中的位置和方向，这种改变使得霍夫变换能够检测用其模型描述的任意对象。这将图像中查找对象（用模型描述）的问题通过查找模型在图像中的位置来解决。利用广义霍夫变换（GHT），找到模型位置的问题转换为寻找将模型映射到图像中的变换参数的问题。给定变换参数的值，就可以确定模型在图像中的位置。

后来产生了更多霍夫变换的变体和扩展，比如KHT,3DKHT，这里不细致说明。

简介

霍夫变换是一个特征提取技术。其可用于隔离图像中特定形状的特征的技术，应用在图像分析、计算机视觉和数字图像处理领域。目的是通过投票程序在特定类型的形状内找到对象的不完美实例。这个投票程序是在一个参数空间中进行的，在这个参数空间中，候选对象被当作所谓的累加器空间中的局部最大值来获得，所述累加器空间由用于计算霍夫变换的算法明确地构建。最基本的霍夫变换是从黑白图像中检测直线(线段)。Hough变换主要优点是能 容忍特征边界描述中的间隙，并且相对不受图像噪声的影响 。

原理

霍夫变换最简单的是检测直线。我们知道，直线的方程表示可以由斜率和截距表示（这种表示方法，称为斜截式），如下所示：

如果用参数空间表示则为 ,即用斜率和截距就能表示一条直线。

但是这样会参数问题，垂直线的斜率不存在（或无限大），这使得斜率参数 的值接近于无限。为此，为了更好的计算，Richard O. Duda和Peter E. Hart在1971年4月，提出了Hesse normal form(Hesse法线式)

其中 是原点到直线上最近点的距离(其他人可能把这记录为 ，下面也可以把r看成参数 )， 是 轴与连接原点和最近点直线之间的夹角。如图1所示。

因此，可以将图像的每一条直线与一对参数 相关联。这个参数 平面有时被称为霍夫空间，用于二维直线的集合。

在概念上，霍夫变换很接近Radon变换有人将之看成同一变换的不同形式

经过Hough变换，将图像空间中的一个点映射到Hough空间，如图2所示。

图2：固定一个点（3,4），在角度 取 时，r的取值范围情况. 该图是用matlab绘制，代码如下

% 一个点的坐标为（3,4）
x=3;
y=4;
%将给定的一个定点映射到霍夫变换空间
theta=0:pi/200:2*pi;% 角度
r=x*cos(theta)+y*sin(theta);
plot(theta,r);%绘图
set(gca,'XTick',[0:pi/10:2*pi]);   % 修改x轴坐标间隔
 xlabel('变量\theta')
 ylabel('变量r')

继续正题内容，图2显示了经过定点 时 的关系。显示了在极坐标对极径极角平面绘出所有通过该定点的直线, 将得到一条正弦曲线。正弦曲线的形状取决于，点到所定义原点的距离 。通常， 越大，正弦曲线的振幅越大，反之则会越小。

所以我们可以得到一个结论，给定平面中的单个点，那么通过该点的所有直线的集合对应于 平面中的正弦曲线，这对于该点是独特的。一组两个或更多点形成一条直线将产生在该线的 处交叉的正弦曲线。因此，检测共线点的问题可以转化为找到并发曲线的问题。

例子1

考虑下面三个点，这里显示为黑点

该图显示了Hough变换的第一步，三点和六个可能的角度分组。最左边的图像显示正在转换的第一个点。首先，绘制不同角度的线条，全部经过第一点。这些显示为实线。其次，对于每条实线，找到也将原点平分的垂线（法线，或者说连接原点垂直于线段的线），这些显示为虚线。然后找到虚线的长度和角度。这些值显示在图表下方的表格中。这对被转换的三个点中的每一个都重复该过程。然后将结果绘制成图，有时称为霍夫空间图。

这显示一个霍夫空间图，三点和六个可能的角度。这是前面表格中数据的一个简单图表。线彼此交叉的点表示由作为变换输入的三个点形成的线的角度和距离.

图4显示的曲线相交的点给出距离和角度。该距离和角度表示与被测试点相交的线。在图4中，所示的线条在粉红点相交; 这对应于图3中的实线粉红线，其穿过所有三个点。

在图像分析上下文，边缘段的点（一个或多个）的坐标 在图像中是已知的，并且因此作为参数线等式中的常量，而 与 是未知变量是我们要寻找的。如果我们绘制由 每个定义的可能值 ，笛卡尔图像空间中的点映射到极性霍夫参数空间中的曲线（即正弦曲线）。这个点到曲线的变换是直线的霍夫变换。当在霍夫参数空间中查看时，在笛卡尔图像空间中共线的点变得很明显，因为它们产生在相同 点相交的曲线。

例子2

以下是显示包含两条粗线的光栅图像上的霍夫变换结果的不同示例。

该变换的结果存储在矩阵中。单元格值表示通过任意点的曲线数量。更高的单元格值变得更亮。两个明显的亮点是两条线的霍夫参数。从这些点的位置，可以确定输入图像中两条线的图像中心的角度和距离。

霍夫变换提取直线如何实现？实现机理是为何？ 通过将霍夫参数空间量化为有限间隔或累加器单元来实现变换。随着算法的运行，每个算法都把 转换为一个离散化的 曲线，并且沿着这条曲线的累加器单元被递增。累加器阵列中产生的峰值表示图像中存在相应的直线的有力证据。  注意，现在我们考虑的是直线的霍夫变换（先不去考虑圆，圆的情况稍后简单说明）。累加器阵列的维度是二维的（也就是r和 )。

用霍夫变换检测圆时，累加器是三维累加器，目前不去论述

那么对于图像来说， 处的每个像素及其邻域，霍夫变换算法被用于确定该像素是否有足够的直线证据。如果是，它将计算该线的参数 ，然后查找参数落入的累加器箱，并增加该箱的值（投票值）。通过查找具有最高值的箱，通常通过查找累加器空间中的局部最大值，可以提取最可能的线，并且读出它们的（近似的）几何定义。

找到这些峰的最简单方法是通过应用某种形式的阈值，但其他技术可能在不同情况下产生更好的结果 - 确定找到哪些行以及有多少。由于返回的行不包含任何长度信息，因此通常有必要在下一步中查找图像的哪些部分与哪些行匹配。此外，由于边缘检测步骤中存在缺陷误差，通常会在累加器空间中出现错误，这可能使得找到合适的峰值以及适当的线条变得非常重要。

线性霍夫变换的最终结果是类似于累加器的二维阵列（矩阵），该矩阵的一个维度是量化角度 ，另一个维度是量化距离r。矩阵的每个元素的值等于位于由量化参数 表示的线上的点或像素的总和。所以具有最高值的元素表示输入图像中代表最多的直线。在某些论文中，可能把累计器单元的结果认为是投票值。换句话说，将每个交点看成一次投票，也就是说 ，所有点都如此进行计算后，可以设置一个阈值，投票大于这个阈值的可以认为是找到的直线。下图是从一个博客摘用。

分别为原图，阈值为30，20时候检测到的直线。对于大于阈值的点,有其Hough space的参数对 通过逆映射我们可以得到图像空间中的直线：

实现使用的例子说明描述

霍夫变换可用于识别最适合一组给定边缘点的曲线的参数。该边缘描述通常从诸如Roberts Cross，Sobel或 Canny边缘检测器的特征检测算子获得，并且可能是嘈杂的，即其可能包含对应于单个整体特征的多个边缘片段。此外，由于边缘检测器的输出仅限定图像中的特征的位置，所以霍夫变换进一步是确定两个特征是什么（即检测其具有参数（或其他）的特征描述）以及 它们有多少个存在于图像中。

为了详细说明霍夫变换，我们从两个闭合矩形的简单图像开始。

简单闭合矩形

使用 Canny边缘检测器可产生一组边界描述的这个部分，如图8所示。

这里我们看到了图像中的整体边界，但是这个结果并没有告诉我们这个边界描述中的特征的身份（和数量）。在这种情况下，我们可以使用Hough（线检测）变换来检测该图像的八个单独的直线段，从而确定对象的真实几何结构。

如果我们使用这些边缘/边界点作为Hough变换的输入，则会 在笛卡尔空间中的每个边缘点的极坐标空间中生成一条曲线。当被视为强度图像时，累加器阵列看起来像图9所示

可以利用直方图  均衡技术使得图像可以让我们看到包含在低强度像素值中的信息模式，如图10所示。

注意，虽然 和 是概念上的极坐标，但是累加器空间以横坐标 和纵坐标 的矩形绘制 。请注意，累加器空间环绕图像的垂直边缘，因此实际上只有8个实际峰值。

由梯度图像中的共线点生成的曲线 在霍夫变换空间中的峰中相交。这些交点表征原始图像的直线段。有许多方法可用于从累加器阵列中提取这些亮点或局部最大值。例如，一个简单的方法涉及阈值处理，然后 对累加器阵列图像中孤立的亮点集群进行一些细化处理。这里我们使用相对阈值来提取 ，对应于原始图像中的每条直线边缘的点。（换句话说，我们只采用累加器数组中的那些局部最大值，其值等于或大于全局最大值的某个固定百分比。）

从Hough变换空间（即，反霍夫变换）映射回笛卡尔空间产生一组图像主题的线描述。通过将该图像叠加在原始的反转版本上，我们可以确认霍夫变换找到两个矩形的8个真实边的结果，并且因此揭示了遮挡场景的基础几何形状。

从Hough变换空间（即，反霍夫变换）映射回笛卡尔空间产生一组图像主题的线描述。通过将该图像叠加在原始的反转版本上（见图11），我们可以确认霍夫变换找到两个矩形的8个真实边的结果，并且因此揭示了遮挡场景的基础几何形状。

请注意，在这个简单的例子中，检测到的和原始图像线的对齐精度显然不完美，这取决于累加器阵列的量化。（还要注意许多图像边缘有几条检测线，这是因为有几个附近的霍夫空间峰值具有相似的线参数值，存在控制这种效应的技术，但这里没有用来说明标准霍夫变换。）

还要注意，由霍夫变换产生的线条的长度是无限的。如果我们希望识别产生变换参数的实际线段，则需要进一步的图像分析以便查看这些无限长线的哪些部分实际上具有点。

为了说明Hough技术对噪声的鲁棒性，Canny边缘描述已被破坏 （由椒盐噪声引起）， 在Hough变换之前，如图12所示。

绘制在霍夫空间的结果如图13所示。

将这个结果反霍夫变换（并将它覆盖在原来的结果上，见图14）

图14：相对阈值设置为40％。

可以通过变换图像来研究Hough变换对特征边界中的间隙的敏感性（使用了画图工具进行编辑，见图15）

然后我们再将其变换到霍夫变换空间，表示为图16所示。

然后使用40%的相对阈值去对图像反霍夫变换（同样也是叠加在原图上

在这种情况下，因为累加器空间没有接收到前面例子中的条目数量，只能找到7个峰值，但这些都是结构相关的线。

前面的例子都不是自然实例。下面展示自然实例的例子。

城市场景

在第一种情况下，我们有一个城市场景，这些建筑物被雾遮住，见图18。

如果我们想要找到建筑物的真实边缘，边缘检测器（例如Canny）无法很好地恢复这些信息，如图19所示。

但是，霍夫变换可以检测到一些表示遮挡区域内建筑物边缘的直线。原始图像的直方图均衡累加器空间表示如图20所示。

如果我们将相对阈值设置为70％，我们会得到如图21所示的反霍夫变换图像。

这里只能检测到几条长边，并且在很多线条或边缘片段几乎共线的地方存在很多重复。应用更大的相对阈值（即50％）会产生如图22所示效果。

会产生更多的预期线条，但会以许多共线边缘碎片产生的许多虚假线条为代价。

最后一个例子来自遥感应用。在这里，我们想要检测图像中的街道

遥感应用

图23显示了一个合理的矩形城市扇区（rectangular city sector）。我们可以使用Canny边缘检测器来检测该图像，如图24所示。

但是，街道信息不能单独用作边缘检测器的输出。

图25表明霍夫线检测器能够恢复这些信息中的一些。但由于原始图像的对比度较差，因此确定了一组有限的特征（即街道）。

实现算法描述

摘取一篇博客的算法描述：

1. 初始化 空间， 表示在该参数表示的直线上的像素点的个数)
2. 对于每一个像素点 ，在参数空间中找出满足 的 对，然后令
3. 统计所有 的大小，取出 的参数 （τ是预设的阈值）

但我觉得这并不是十分完整的算法流程。所以我将其改进描述如下

1. 读取原始图并转换成灰度图，采用边缘检测算子（如Canny）转换成二值化边缘图像
2. 然后对该图像进行霍夫变换
3. 先使用峰值检测函数，找到大于阈值的霍夫变换单元（局部最大值应该最可能是线，步长和量化会影响效果）
4. 将上述识别出的一组候选峰，需要确定与其相关的线段及其起始点和终止点（这需要一定的算法，很多论文对此都做了改进，诸如蝴蝶形状宽度，峰值走廊）
5. 然后描绘于原图（或结果图）上

代码实现

matlab版本

原图

%读取图像
I  = imread('huofu.jpg');
% 转换成灰度图
grayI = rgb2gray(I);

% 创建二进制图像
BW = edge(grayI,'canny');
% 使用二值图像创建Hough变换。
[H,T,R] = hough(BW);
imshow(H,[],'XData',T,'YData',R,...
            'InitialMagnification','fit');
xlabel('\theta'), ylabel('\rho');
axis on, axis normal, hold on;
% 在图像的霍夫变换中查找峰值
P  = houghpeaks(H,5,'threshold',ceil(0.3*max(H(:))));
x = T(P(:,2)); y = R(P(:,1));
plot(x,y,'s','color','white');
% 找到线条并绘制它们
lines = houghlines(BW,T,R,P,'FillGap',5,'MinLength',7);
figure, imshow(I), hold on
max_len = 0;
for k = 1:length(lines)
   xy = [lines(k).point1; lines(k).point2];
   plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','green');

   % 绘制线条的开始和结束
   plot(xy(1,1),xy(1,2),'x','LineWidth',2,'Color','yellow');
   plot(xy(2,1),xy(2,2),'x','LineWidth',2,'Color','red');

   % 确定最长线段的端点
   len = norm(lines(k).point1 - lines(k).point2);
   if ( len > max_len)
      max_len = len;
      xy_long = xy;
   end
end
% 通过为青色着色来突出显示最长的线段
plot(xy_long(:,1),xy_long(:,2),'LineWidth',2,'Color','cyan');

运行结果

只是个示范使用，参数可自调。

python实现

#! python2
# coding: utf-8

import numpy as np
import matplotlib.pyplot as plt

from skimage.transform import hough_line
from skimage.draw import line

img = np.zeros((100, 150), dtype=bool)
img[30, :] = 1
img[:, 65] = 1
img[35:45, 35:50] = 1
rr, cc = line(60, 130, 80, 10)
img[rr, cc] = 1
img += np.random.random(img.shape) > 0.95

out, angles, d = hough_line(img)

fix, axes = plt.subplots(1, 2, figsize=(7, 4))

axes[0].imshow(img, cmap=plt.cm.gray)
axes[0].set_title('Input image')

axes[1].imshow(
    out, cmap=plt.cm.bone,
    extent=(np.rad2deg(angles[-1]), np.rad2deg(angles[0]), d[-1], d[0]))
axes[1].set_title('Hough transform')
axes[1].set_xlabel('Angle (degree)')
axes[1].set_ylabel('Distance (pixel)')

plt.tight_layout()
plt.show()

运行结果

Opencv实现