谭升
非主流人工智能科学家 我和外面那些妖艳的货不一样

【数字图像处理】6.10:灰度图像-图像分割 霍夫变换(Hough Transform)–直线”

灰度图像-图像分割 霍夫变换(Hough Transform)–直线”

废话开始,要过年了,到处人心惶惶,沉下心写篇博客,下一篇就等农历新年以后了。马上新年了,希望自己在新年能提高技术,找到一份图像处理的好工作,也希望大家都能学习到更多的知识,做自己喜欢做的事情。
以前基本每天都写博客,坚持了三个月感觉确实有提高,也能把知识总结分享出来,看着每天博客的访问量不断增长,心里很有成就感,共同学习,共同进步,喜欢分享的人,才能获得别人的分享,好多优秀的同学并不喜欢分享知识,或者用很高深的话显示出自己的知识,现在想想,能用俗话说清相对论的人才是高手,让那些故弄玄虚,作假,抄袭欺骗国家欺骗人民的院士,专家都去shi吧。
废话稍微多了一点点,说说霍夫变换,Hough Transform,由Hough提出,问题原型是如何找到图像中的直线,后来延伸到可以检测出任何可以表示成方程的图形,霍夫变换的检测可以检测不完整的图形,也就是中间有间断的,并且霍夫变换对旋转具有不变性,对噪声不敏感,但是霍夫变换的缺点是需要的存储量较大,标准的霍夫变换运算量大,相对较慢。
本篇只介绍标准霍夫变换对直线的检测,放在图像分割这部分是因为冈萨雷斯书中将霍夫变换用于连接边缘。

数学原理

我们本篇只介绍检测直线,对于图像中直线,一般用方程 $y=kx+b$ ,式子中 $k$ 表示直线的斜率, $b$ 表示直线相对于y轴的截距,如图中所示:

如果按照正常思维,搜索图中的直线,使用穷举的方法,假设图像一共有N个像素任意两点可以构成一条直线,所以过一点应该有(N-1)/2条,所以全图像存在N(N-1)/2条直线,如果要确定一点是否是直线上的点,一共需要至少 $N^2(N-1)/2$ 次计算,这个代价的算法在实际中基本没有价值,于是,Hough提出了一种巧妙的方法,将直线表示成 $-b=xk-y$ 这种变换的意义在于自变量不是x而是k,y也不再是因变量,b变成了因变量,所以图像上任意两点,可以从(x,y)坐标系映射到(k,b)坐标系,系数选取点 $(x_1=1.8,y_1=7.6)$ 和点 $(x_2=3.4,y_2=10.8)$ ,绘制出两条曲线:

可以根据上图得出k=2,b=4,那么在$y=kx+b$的点的在k,b坐标系上的交点都在(2,-4)处,
根据上面我们可以利用这个特点,将一幅图像从(x,y)坐标系,转换到(k,b)坐标系,假设原图中有k个亮点,可以在(k,b)坐标系画出k条直线,那么越多的直线交于一点,说明该点的坐标为斜率和截距的直线点在原图中出现频率越大,那么我们就能根据这个特点找出这些点。
问题来了,当原图直线和x轴垂直时,斜率k趋近于无穷大,所以在(k,b)坐标系内无法表示,所以我们换一种方法,使用直线 $y=kx+b$ 的法线,截距为-b,那么这条直线为 $y=-\frac{1}{k}x-b$ ,如果使用参数方程,原直线为 $cos(\theta)y-sin(\theta)x=cos(\theta)b$ ,令 $\varrho=cos(\theta)b$ 原坐标的直线为 $cos(\theta)y-sin(\theta)x=\varrho$ ,那么法线的参数方程为 $sin(\theta)y+cos(\theta)*x=-\varrho$ ,方程坐标系为 $(\theta,\varrho)$ 。
将上面的思想应用到 $(\theta,\varrho)$ 坐标系,我们将得到,如下的信息,原图:

转换到参数坐标系:

交点出就是两条对角线的参数。
我们来观察一条直线的参数坐标系:
水平直线:

对应参数坐标系:

垂直直线:

对应参数坐标系:

45°直线:

对应参数坐标系:

-45°直线:

对应参数坐标系:

五条直线交于一点:

对应参数坐标系:

上图中越明亮的点说明重叠参数方程越多,我们来观察两条直线对应参数坐标系的立体情况:
原图:

平面的参数方程坐标系:

参数方程坐标系的立体显示:

#代码

效果

Hough变换输入图像因为边缘图像,或是二值图像效果如下图:
原图:

边缘检测:

霍夫直线检测:

原图:

边缘检测:

霍夫直线检测:

结论

霍夫变换可以有效的检测出图像中的直线,但需要设定一定的参数,比如定位参数坐标中极大值的方法,以避免错误的检出结果,广义的霍夫变换可以检测任何$g(\vec x,\vec c)=0$表示的形状,只是计算难度根据方程的复杂度决定,$\vec c$表示方程参数,参数越多需要的存储空间越大,需要的计算量也越大。
待续。。。

Advertisements
Share

You may also like...

说点什么

avatar
  Subscribe  
提醒

试录了几节线性代数视频课程,欢迎大家支持,
点击试看
点击购买更多内容

由于博客移至wordpress,部分公式和代码显示不正常,博主正在努力修改,如发现公式显示错误,请及时在文章下留言,感谢您的帮助,尽请原谅!