8.霍夫变换:线条——投票原理、霍夫空间、线的极坐标表示_2

2024-02-29 07:18

本文主要是介绍8.霍夫变换:线条——投票原理、霍夫空间、线的极坐标表示_2,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

投票原理

霍夫空间

线的极坐标表示


投票原理

就像我之前说的,检查每一行是不可能的,即使是一台非常非常快的电脑。

我们要做的是让数据告诉我们,让数据决定线在哪里。

因为这是民主,我们该怎么办?  

我们要做的是投票。

因此,投票是一种通用的技术,我们让特性投票给所有与之兼容的模型。

它的工作方式很简单:

1、循环遍历所有特征(特征指的是小的边缘点),每次为模型参数投票。

现在,对于我所需要的大多数特征来说,都是小的边缘点。

并且每个边缘点将对模型参数 或 其满意 或 一致的不同模型参数集投票。

2、寻找得到大量选票的模型参数。

当我们都完成了第一步,我们接下来需要寻找很多选票的模型参数,这些是我们要实例化的参数模型。

为什么投票有效?

嗯,投票的作用就像米老鼠、唐老鸭和劳拉·克劳馥永远不会当选加州州长一样。

第一:噪声和杂乱的特性也会投票,就像真实的特性一样。但通常情况下,他们的投票是跟大多数的优秀特征不一致。

第二:如果没有观察到一些特性,模型可以跨越多个片段。

另一个好处是:

即使圈子的一部分被遮挡而且没有任何特征可以投票,因为圈子的其余部分获得了很多选票,我们能够找到圆圈。

我们今天要用的例子是关于拟合线。

为了拟合直线,我们要问几个问题:

第一个问题:给定属于直线的点,直线是什么?

第二个问题:那里有多少条线?

第三个问题:哪些点属于哪条线的?

现在我们主要集中在这堂课的第一个问题,事实上,我们将要做的大部分工作,

但是我们正在讨论的内容的拓展使得做问题2和问题3时要变得很容易。

我们今天要讲的方法叫做霍夫变换(Hough Transform),这是一种投票技术,可以用来回答所有这些问题。

主要思想:

1、每个边缘点都会投票兼容的线条;

2、寻找那些能得到很多选票的线条;

也就是说,它会投票给任何通过它的旧线路,然后你就会寻找得到很多票的线条。

所以可能有两条,三条,四条线,你可以找到它们。

顺便说一下,如果你跟踪哪个点投给了哪条线,你也可以回去说哪个点属于那条线。

霍夫空间

我要给你们讲一下它是如何工作的,霍夫变换的关键是霍夫空间。

这是左边的图像空间中的一条线,我们要构造的是霍夫空间,右边是霍夫参数空间。

在这个表述中,我们有两个参数 m 和 b 。

所以,对于这条直线 y = m_{0}x + b_{0} ,它在Hough空间中的 m_{0}b_{0} 处表示:

这就是霍夫空间的意义所在。

这里的关键思想是:图像中的直线对应于霍夫空间中的一点。

现在我们要做一些不同的事情。

假设在图像空间中只有一个点,我们把这个点放在(x,y) 处:

那么,经过这一点的直线的方程是什么呢?

在图像空间中,我们知道经过这一点的直线满足 m 和 b。

它会满足方程 y = m_{0}x + b_{0},为了通过点(x_{0},  y_{0})它必须有一个 m 和一个 b 使这个方程成立。

通过一些简单的代数重排,就得到 b=-x_{0}m + y_{0},这是m b空间中直线的方程:

实际上,它是一条斜率为 -x_{0}m,截距为 y_{0} 的直线:

这里的思想是:图像空间中的一点是霍夫空间中的一条线。

这是对偶性。

如果增加一个点会怎样?

这是另一条直线:

这是一条直线 :b=-x_{1}m + y_{1}

现在有一个很酷的问题:什么样的直线是跟这两点的情况符合的?

它是Hough空间中的这两条线相交的地方:

因为那是m和b,它与穿过(x_{0}y_{0})的线 和 穿过(m_{1}b_{1})的线是一致的。

女士们,先生们,男孩们,女孩们,所有感兴趣的人,这就是我们如何从点中找到直线的方法。

现在我们要把它简化成一个算法,我们先用图形来展示给你看,然后再讲算法。

基本上,每个点都给了Hough空间中的一条直线。

我要做的是:我创建一个表格,这里是m和b,它是由一组箱子组成的:

每一个点都对经过的箱子进行投票,所以它会对经过的每个箱子投一票。

你收集了每个箱子的票数情况。每一个点都投过票,哪一个票数最多,那就是你的路线:

因此,基本上,我们将把选票投进箱子,然后找到最多选票的箱子。求这个点坐标就求出直线了。

但这里是用极坐标表示,因为极坐标更加细化,我们来看看下面这个例子:

在真正的代码和数学中实现这个之前,我们需要重新考虑一下出现以下这种情况该怎么表示:

这样的话,会出现好几条垂直线在一起,斜率m等于无穷大,而截距b怎么取值呢?

好的,我们要用一个更健壮的线条表示,这样我们就不会有任何不好的数值问题了。

我们要用的是直线的极坐标表示。

线的极坐标表示

d:从直线到原点的垂直距离。

\theta: 垂线与x轴的夹角。

在极坐标表示中,这条紫色的线由两个量定义。

其中一个就是这个距离d,这是一条直线到原点的垂直距离:

它是这条紫色的直线上离原点最近的点的距离。

第二个参数是:这条垂直线与x轴的夹角(\theta),如果你愿意,也可以是直线与坐标轴的夹角,

没关系,你只需要选择一个角度:

基本上我们得到的是一个距离和一个角度的极坐标(d,\theta)。

求 d 的距离公式基本上是这样表示:

这个公式是由直线公式转换而来:

y = (-\frac{cos\theta}{sin\theta})x+(\frac{r}{sin\theta})

 

经过化简之后,我们可以得出:

xcos\theta + ysin\theta = r

这里的 r 就是 d,也就是极径的距离。或者称向某个方向为移动了多少单位。

所以它有点丑,如果你喜欢三角学,那就太美了。如果你喜欢代数,那就太难看了,它比y = mx + b更难看。

但这个公式没有这个问题,我们的任何直线都是不规则的。你可以有任何你想要的方向,可以任意移动。

你可以直接穿过原点。d可以是0,也可以达到你需要的大小。

有趣的是,如果你看这个方程(图像空间中的点现在是Hough空间中的正弦段),

如果我们已经知道 x 和 y,我们剩下的是 d 和 \theta 是正弦曲线:

这就是为什么我们说:图像空间中的一点现在是霍夫空间的正弦曲线,我们一会儿会看到一个例子。

看,之前,图像空间中的一个点是霍夫空间中的一条线,霍夫空间中的一个点是图像空间中的一条线。

因为我们已经介绍了余弦(cos)和正弦(sin),它仍然是对偶性,但它不再是简单的点和线之间的关系。

关于这个的另一个评论,这里有一个冗余或歧义。

我这样画,这里是d:

所以如果 d 只能是正的:

这条线必须能够一路旋转:

因此 \theta 必须从 0 到 2π,也就是 0度 到 360度 。

但如果 d 可以是正的 或 可以是负的:

那么 \theta 只需要从 0 到 π ,也就是 0度 到 180度:

或 0 到 -π,也就是0度 到 -180度。这个想法是你只需要180度的覆盖范围。

你用哪种方法做并不重要,我们的算法会用一种特殊的方式来做。

但是这里有一个权衡,如果你让 d 从正 到 负,上面是负的,那么只有它必须从 0 到 π 。

事实上,如果你将它作为图像的原点,你可以限制更多的东西。

如果你想说直线必须在图像中。然后,它限制了更多,因为它必须切断象限,因此 \theta 和 d 受到更多限制。

但这些只是你在如何编写算法方面做出的选择。

对三角函数加深学习:

学习:sin cos 等函数图像。

对极坐标知识加深理解:

https://blog.csdn.net/sw3300255/article/details/82756184

https://blog.csdn.net/sw3300255/article/details/82776368

加深理解霍夫变换原理:

https://www.cnblogs.com/php-rearch/p/6760683.html

https://blog.csdn.net/m0_37264397/article/details/72729423


——学会编写自己的代码,才能练出真功夫。

这篇关于8.霍夫变换:线条——投票原理、霍夫空间、线的极坐标表示_2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/757968

相关文章

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

hdu4407容斥原理

题意: 有一个元素为 1~n 的数列{An},有2种操作(1000次): 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit

寻迹模块TCRT5000的应用原理和功能实现(基于STM32)

目录 概述 1 认识TCRT5000 1.1 模块介绍 1.2 电气特性 2 系统应用 2.1 系统架构 2.2 STM32Cube创建工程 3 功能实现 3.1 代码实现 3.2 源代码文件 4 功能测试 4.1 检测黑线状态 4.2 未检测黑线状态 概述 本文主要介绍TCRT5000模块的使用原理,包括该模块的硬件实现方式,电路实现原理,还使用STM32类

TL-Tomcat中长连接的底层源码原理实现

长连接:浏览器告诉tomcat不要将请求关掉。  如果不是长连接,tomcat响应后会告诉浏览器把这个连接关掉。    tomcat中有一个缓冲区  如果发送大批量数据后 又不处理  那么会堆积缓冲区 后面的请求会越来越慢。

Verybot之OpenCV应用二:霍夫变换查找圆

其实我是想通过这个程序来测试一下,OpenCV在Verybot上跑得怎么样,霍夫变换的原理就不多说了,下面是程序: #include "cv.h"#include "highgui.h"#include "stdio.h"int main(int argc, char** argv){cvNamedWindow("vedio",0);CvCapture* capture;i

PHP原理之内存管理中难懂的几个点

PHP的内存管理, 分为俩大部分, 第一部分是PHP自身的内存管理, 这部分主要的内容就是引用计数, 写时复制, 等等面向应用的层面的管理. 而第二部分就是今天我要介绍的, zend_alloc中描写的关于PHP自身的内存管理, 包括它是如何管理可用内存, 如何分配内存等. 另外, 为什么要写这个呢, 因为之前并没有任何资料来介绍PHP内存管理中使用的策略, 数据结构, 或者算法. 而在我们

Smarty模板执行原理

为了实现程序的业务逻辑和内容表现页面的分离从而提高开发速度,php 引入了模板引擎的概念,php 模板引擎里面最流行的可以说是smarty了,smarty因其功能强大而且速度快而被广大php web开发者所认可。本文将记录一下smarty模板引擎的工作执行原理,算是加深一下理解。 其实所有的模板引擎的工作原理是差不多的,无非就是在php程序里面用正则匹配将模板里面的标签替换为php代码从而将两者

Restful API 原理以及实现

先说说API 再说啥是RESRFUL API之前,咱先说说啥是API吧。API大家应该都知道吧,简称接口嘛。随着现在移动互联网的火爆,手机软件,也就是APP几乎快爆棚了。几乎任何一个网站或者应用都会出一款iOS或者Android APP,相比网页版的体验,APP确实各方面性能要好很多。 那么现在问题来了。比如QQ空间网站,如果我想获取一个用户发的说说列表。 QQ空间网站里面需要这个功能。