7.3.2 Hough变换学习视频在线视频

同学们好

今天我们给大家介绍图像分割中的另一种边缘线跟踪的方法

我们知道边缘线的检测，要经过两个过程

首先进行边缘点的检测，然后再将边缘点连接成边缘线

但是，由于噪声干扰以及图像成像时不均匀的光照的影响

那么通过边缘点检测，就很少真正能够得到一组

完整描述一条边缘线的点集

那么通过局部边缘连接，也就很难得到准确的边缘线

而哈夫变换，能够根据待检测曲线对应的像素间的一个整体关系

检测出已知形状的曲线，并以参数方程的形式进行描述

哈夫变换的优点，就是它抗噪声干扰点以及断点的影响

哈夫变换的基本原理，实际上就是把图像中需要检测的直线

或者是有规律的曲线转换成寻找参数空间的峰值点问题

那么下面，我们以检测直线为例进行说明

首先我们看一下，假如说我现在有一个图像

图像中有n个点，我们现在要求从这n个点中确定一条直线

并且，在这条直线上贡献的点最多

那首先，我们能够想到的最直接的办法就是

我们知道任意两点确定了一条直线

所以，我们一共能够找出二分之n乘n-1条直线

首先计算出二分之n乘n-1条直线

然后，我们再找出每条直线上一共有多少个

刚才那n个点中一共有多少个点

也就是说，要找出最接近直线的点的集合

大概需要n的三次方的计算

那么这么做我们说好处就是非常直观，但实际上它有一个明显的缺点

这个缺点就是运算量巨大，实际情况是不容易满足的

比如说，我们现在图像中有256个点

光是第二步我们就要计算256的三次方，这么多次计算来进行比较

那么，256的3次方是1600多万次计算

因此，我们说这样做就是不太理想

那我们换一种思路来考虑这个问题

在xy平面上，也就是说在图像空间中

我们如果说有一个点用(x,y)来表示

那么，所有过这个(x,y)这个点的直线都应该满足这样的一个直线方程

就是y等于px加q，其中的这个p是斜率，q是截距

如果我们把y等于px加q这个方程的变形一下，写成q等于负px加y

那么这个时候，表示在参数空间p和q这个参数空间中

一条直线，这条直线是过了p和q这个点的一条直线

也就是说，我如果在图像空间xy中，我找到了一个点（xi，yi）

那么所有过（xi，yi）的直线的通用方程，由这个公式来进行描述

同样，我们把它转换到p和q空间之后，变成了q等于负的pxi+yi

那么这个式子说明在XY空间中的一个点

如果我们把它转换到pq空间，对应的就是一条直线

这条直线的斜率是负的xi，截距是yi

同样，如果我在平面，这个图像空间XY中,找到另外一个点（xj，yj）

一样我们写出它的通用方程，然后转换到pq空间

那么因此，我们就得到这样的一个情况

就是说，在XY空间中我们找到一个点（xi，yi）

那么这个点映射到p和q这个参数空间对应的就是这样的一条直线

同样，在XY平面中我们的（xj，yj）这个点，映射到p和q这个参数空间的时候

对应的是这样的一条直线

而如果，在xy平面中这两个点是处在一条直线上的

那么，这两个点处在一条直线上，就意味着这两个点它所对应的方程呢

应该是有相同的p值和q值

那也就是说，在p和q这个空间中，这两条直线必然要相交于同一点

这就是我们说，哈夫变换检测直线就转换成了

寻找共线点最多的直线的问题

就变成了在参数空间中，去寻找极大指点的问题

那么为了寻找这个峰值点

我们就把参数空间p和q量化成很多个小方格

这个小方格称作计数单元

然后根据每一个边缘点，我们带入p的量化值

然后根据这个p值，可以计算出q值

然后把这个值量化以后,量化后的值

必然在这个小格子中，会落入到其中的某一个格子里头

那么如果落入到某一个格子，就把这个小格子的计数单元加1

这样当所有的边缘点都计算完成之后

我们对这个计数单元进行检测，如果我们只需要检测一条直线

那么在这个计数单元中拥有最大值的那个点，它所对应的p和q值

就是我们要求的那个直线的所对应的斜率和截距

当然我们也知道，如果p和q在量化的过程中量化的比较粗

那么参数空间的凝聚效果就差

也就是说，我们的格子个数比较少，那么它凝聚效果差

求得这个直线方程就不够精确

反过来说，如果量化的过细，那么计算量就会增大

因此，对参数的量化要兼顾量化的精度和计算量

在平面直角坐标系中检测直线会出现这样一个问题

就是在直线接近于垂直的时候，它的斜率有可能会趋于无穷大

那么为了避免这种情况，可以采用极坐标的形式

在极坐标中一条直线可以用两个参数来表示分别是ρ和θ

其中的ρ表示的是坐标原点到直线的垂直距离

ρ表示的是坐标原点，到直线的垂直距离

而θ表示的是直线的法线和x轴的夹角

那么这样一来，我们就可以得出图像空间和参数空间的一个对应关系

根据这个式子我们可以看到

在xy平面上的一条直线转换到了ρ和θ空间中

实际上我们可以看到，对应的是ρ和θ这样的一个点

而在xy平面中的一个点，对应到ρ和θ空间中应该是一条正弦曲线

因此，我们总结出来

在图像空间xy空间和参数空间ρθ空间中的对应关系就是

图像空间中的一条直线，在ρ和θ这个参数空间中的映射为一个点

而在图像空间中的一个点，映射到参数空间中是一条正弦曲线

因此，图像空间中一条直线上多个共线的点映射到参数空间之后

就应该是相交于一点的多条正弦曲线

下面，我们用这个图来说明一下，这是一条直线

这条直线映射到ρ和θ空间中，对应的就是一个点

那么，这个是我们平面空间中的一个点，（xi，yi）这个点

映射到ρ和θ空间中，应该对应的是一条正弦曲线

那么这个，就是我们在这条直线上找到了a、b、c、d、e 5个点

也就是说，这5个点是共线的

那么在参数空间中，我们可以看到，一共是5条正弦曲线

而且这5条正弦曲线，相交于同一个点

这个就是我们说的，在极坐标的情况下，我们来检测直线

同样在参数空间，我们要把ρ和θ也量化成很多个小格子

那么计数的方式和平面直角坐标系中检测直线是一致的

需要说明的，就是哈夫变化不仅可以检测直线

而且也可以检测圆、椭圆、抛物线等等这些有解析表达式的曲线

下面我们在屏幕上给大家显示了用哈夫变换检测直线和圆的一个示例

这是一个含噪的图像，在这个图像中有一个黑色的圆

圆中有一个白色的三角形

这幅图用Sobel算子的一个检测结果

那么从这个图中我们可以看到

Sobel检测算子还是对这个噪声有一定的影响

而这个，是我们用哈夫变换检测的一个结果

那么，这两幅图进行比较哈夫变换检测是非常干净整齐的

下面这四幅图分别对应的就是哈夫变换检测直线和

哈夫变换检测圆的一个参数空间

这两幅图，是参数空间显示出来的

其中这幅图是哈夫变换检测直线的一个参数空间，用的是极坐标

在这个图中，我们明显的看到有三个高亮的点

这三个高亮的点，实际上对应于就是在图像空间中的3条直线

而这个圆的检测，我们在这里面假设

圆是半径已知，我们现在需要检测的是圆的圆心的位置

这个里面横和纵坐标，分别对应的就是圆点的位置

那在这个空间中，我们也可以看到最亮的点，是位于正中心

也就意味着中心这个点，应该是我们所需要检测的那个圆的圆心位置

那么，这是我们用哈夫变换检测出来的圆的结果

需要说明，就是哈夫变化除了能够检测可以用解析形式表示的曲线以外

也可以推广到任意形状的检测，一般我们就把它称作是广义哈夫变换

有兴趣的同学可以查阅相关的文献，进一步研究

好，今天主要内容就给大家介绍到这里

谢谢大家，再见