博文

经典霍夫变换（Hough Transform）

已有 12251 次阅读 2020-7-5 15:21 |个人分类:数字图像处理|系统分类:科研笔记

见博文：https://blog.csdn.net/yuyuntan/article/details/80141392

霍夫变换（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变换主要优点是能容忍特征边界描述中的间隙，并且相对不受图像噪声的影响。

（二）原理

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

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

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

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

图1

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

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

图2

此图固定一个点（3,4），在角度θ取[0,2π]时，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显示了经过定点（3,4）时(r,θ)的关系。显示了在极坐标对极径极角平面绘出所有通过该定点的直线, 将得到一条正弦曲线。正弦曲线的形状取决于，点到所定义原点的距离r。通常，r越大，正弦曲线的振幅越大，反之则会越小。

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

例子1

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

图3

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

图 4

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

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

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

霍夫变换提取直线如何实现？实现机理是为何？

通过将霍夫参数空间量化为有限间隔或累加器单元来实现变换。随着算法的运行，每个算法都把(xi,yi)(xi,yi)转换为一个离散化的 (r,θ)(r,θ)曲线，并且沿着这条曲线的累加器单元被递增。累加器阵列中产生的峰值表示图像中存在相应的直线的有力证据。

注意，现在我们考虑的是直线的霍夫变换（先不去考虑圆，圆的情况稍后简单说明）。累加器阵列的维度是二维的（也就是r和θ)。用霍夫变换检测圆时，累加器是三维累加器，目前不去论述

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

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

线性霍夫变换的最终结果是类似于累加器的二维阵列（矩阵），该矩阵的一个维度是量化角度θ，另一个维度是量化距离r。矩阵的每个元素的值等于位于由量化参数 (r,θ)表示的线上的点或像素的总和。所以具有最高值的元素表示输入图像中代表最多的直线。

在某些论文中，可能把累计器单元的结果认为是投票值。换句话说，将每个交点看成一次投票，也就是说A(r,θ)=A(r,θ)+1，所有点都如此进行计算后，可以设置一个阈值，投票大于这个阈值的可以认为是找到的直线。下图是从一个博客摘用。

分别为原图，阈值为30，20时候检测到的直线。

对于大于阈值的点,有其Hough space的参数对(r,θ) 通过逆映射我们可以得到图像空间中的直线：

（三）实现使用的例子说明描述

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

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

图7 简单闭合矩形

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

图8

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

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

图9

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

图10

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

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

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