NJU1healer的个人博客分享 http://blog.sciencenet.cn/u/NJU1healer

博文

经典霍夫变换(Hough Transform)

已有 9264 次阅读 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变换主要优点是能容忍特征边界描述中的间隙,并且相对不受图像噪声的影响。

(二)原理

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

image.png

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

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

image.png

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

image.png

图1

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

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

image.png

图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

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

image.png

图3

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

image.png

图 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,所有点都如此进行计算后,可以设置一个阈值,投票大于这个阈值的可以认为是找到的直线。下图是从一个博客摘用。

image.png    image.png    image.png

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

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

image.png

(三)实现使用的例子说明描述

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

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


image.png

图7  简单闭合矩形

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

image.png

图8

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

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

image.png

图9

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

image.png

图10

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

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

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

image.png

图11

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

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

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

image.png

图12

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

image.png

图13

  将这个结果反霍夫变换(并将它覆盖在原来的结果上,见图14)

image.png

图14:相对阈值设置为40%。

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

image.png

图15

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

image.png

图16

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

image.png

图17

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

————————————————

【参考】

经典霍夫变换(Hough Transform)(matlab,python)

https://blog.csdn.net/yuyuntan/article/details/80141392

       点滴分享,福泽你我!Add oil!



https://blog.sciencenet.cn/blog-3428464-1240702.html

上一篇:边缘检测
下一篇:布尔运算
收藏 IP: 45.146.122.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2023-3-25 12:42

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部