查找图像中椭圆轮廓的快速随机hough变换-阿里云开发者社区

开发者社区> nothingfinal> 正文

查找图像中椭圆轮廓的快速随机hough变换

简介:
+关注继续查看

查找图像中椭圆轮廓的快速随机hough变换

  图像中椭圆轮廓的查找在视频监控等领域有着广泛的应用,经典hough变换给我们提供了一种查找各种图形轮廓的方法,特别是在直线查找方面具有非常高的精确度。但是由于经典hough变换的基本原理是将图像空间转换到参数空间,所以对于椭圆这种参数较多的图形轮廓来说计算量较大,实时性有所降低。

  随机hough变换是经典hough变换的一个变型,这种算法在查找直线、圆以及椭圆等方法都具有较高的鲁棒性。从Range的角度来看,随机hough变换的本质就是一种基于可更新模板的模板匹配方法。下图是一张Range基于这种方法检测行人头部的效果。

  

  下面对随机hough进行一个简单的介绍:

  

  随机hough变换是经典hough变换的盖然论变型。被广泛应用到圆弧等图形(线、圆、椭圆等)的检测中。Hough变换的基本思想是对图像上的潜在圆弧采用一种投票机制,最后算法通过检查最高的投票分数来确定具有最高分圆弧的存在。随机hough变换和经典hough的不同在于通过分析几何性质避免把时间浪费在给每个非零像素投票的过程上。因此,有效地改进了处理时间并且减少了所需要的存储空间。

产生背景

       虽然hough变换被广泛应用到图形检测上,但它主要有两点不足:(1) 对于图像上的每个非零像素,不管是不是要查找的形状的参数都会在投票过程中被累加;(2) 累加器数组(或者hough空间)以一种启发方式定义。要想计算的精度越好,就需要定义越高的参数空间。这两点往往使得系统需要较大的存储开销,而且影响系统的实时性。

实现

       圆弧可以完全由它上面的一定数量的点来决定,和HT比起来,RHT正是利用了这个优势。例如,两点决定一条直线,一个椭圆或圆可由三点确定。为了阐述RHT的思想,我们可以想象下一个椭圆的确定过程:1) 由随机选择的点进行椭圆拟合;2) 更新累加器数组以及相应的匹配度;3) 输出那些大于预定义阈值的椭圆。

椭圆拟合

       定义椭圆的一般公式为:a(x − p)2 + 2b(x − p)(y − q) + c(y − q)2 + 1 = 0,约束条件:ac − b2 > 0。

       但是要确定一个椭圆我们仅需要三个点。

RHT由在椭圆上随机选择三个点开始,设为X1,X2和X3。第一步是找到这三个点处的切线,可以通过对其相邻像素的一个小窗口进行最小二乘拟合一条直线来找到该点处的切线;

第二步是要找出这些切线的交叉点,这点很容易做到。设交叉点为T12和T23,设两条线段X1X2以及X2X3的中点分别是M12和M23。然后椭圆的中心就是T12M12和T23M23的交点。

假设上步求出的椭圆中心坐标为(X0,Y0),设x’=x-x0,y’=y-y0,那么椭圆方程为:

ax'2 + 2bx'y' + cy'2 = 1。现在,我们可以通过带入X1,X2和X3的坐标来解方程求出参数a、b和c。

累加

       椭圆参数被计算出来后,累加器数组就可以相应的更新了。和经典的hough变换不同,RHT没有维护一个"grid of buckets"作为累加器数组。它首先计算新检测到得椭圆和已保存在累加器数组中的椭圆的相似度。可以采用不同计算标准来计算相似度。一旦相似度超出了预定义的门限值,就用这两个椭圆的平均来替换掉累加器数组中的椭圆,同时将它的score加1。.

终止

       一旦某个候选椭圆的score超过了门限值,这个椭圆就是一个被检测出的椭圆。将其从图像和累加器数组中删除,以便该算法更快的找到其他椭圆。当算法循环数目达到最大值或者所有椭圆都被检测出时,算法停止。

伪代码

while (we find ellipses OR not reached the maximum epoch) {
    for(a fixed number of iterations) {
        Find a potential ellipse.
        if(the ellipse is similar to an ellipse in the accumulator)
            Replace the one in the accumulator with the average of two ellipses and add 1 to the score;
        else
            Insert the ellipse into an empty position in the accumulator with a score of 1;
    }
    Select the ellipse with the best score and save it in a best ellipse table;
    Elliminate the pixels of the best ellipse from the image;
    Empty the accumulator;

}

  随机hough和经典的hough有些不同,如果你不了解经典hough可以参考下《hough变换原理》一文,这里不再赘述。

相关参考

1.http://blog.csdn.net/icerain_3321/article/details/1665280

2. D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol.13, No.2, p.111-122, 1981

3. L. Xu, E. Oja, and P. Kultanan, "A new curve detection method: Randomized Hough transform (RHT)", Pattern Recog. Lett. 11, 1990, 331-338.

4. S. Inverso, “Ellipse Detection Using Randomized Hough Transform”, www.saminverso.com/res/vision/EllipseDetectionOld.pdf, May 20, 2002

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
notepad++ 查找引用(Find Reference)(适用于c c++及各类脚本比如lua、python等)
在程序开发过程中,程序员经常用到的一个功能就是查找引用(Find Reference),Visual Studio里面的对应功能是“查找所有引用”(Find All References)。     我在使用notepad++写代码的时候一开始一直因为找不到类似的功能而苦恼。
1328 0
在查找预编译头时遇到意外的文件结尾。是否忘记了向源中添加“#include "StdAfx.h"”?
版权声明:本文为 testcs_dn(微wx笑) 原创文章,非商用自由转载-保持署名-注明出处,谢谢。 https://blog.csdn.net/testcs_dn/article/details/51460043 错误 16 error C1010: 在查找预编译头时遇到意外的文件结尾。
629 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10538 0
【算法导论】二分查找
1. 描述(查找算法):   输入:n个数的一个序列 A = (a1, a2, a3,.....an)和一个值v   输出:下表 i 使得 v=A[i] 或者 v 不在A中出现时,输出 NIL   二分查找的前提是A必须是有序序列, 以下全部假设是A是非降序序列 2.
921 0
lua跨平台文件夹遍历匹配查找
require"lfs" --[[Desc:在B路径D文件中下 搜寻A路径下的没用到的C类文件;      并且将没用到的B类文件名称打印出来; 设置好路径拖到lua自带编辑器中即可运行之;]] --目标所在路径(A)(eg:png所在路径) PNG_FILE_PAT...
778 0
+关注
nothingfinal
软件开发,安全加密
1069
文章
341
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载