文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 基于最小二乘法的改进的随机椭圆检测算法
侵权投诉

基于最小二乘法的改进的随机椭圆检测算法

图像处理 环境建模 最小二乘法 计算机视觉

第8期

陈海峰,等:基于最小二乘法的改进的随机椭圆检测算法

1361

(randomsampleconsensus,RANSAC)思想的算法、遗传算法以及结合椭圆几何特性的算法.这些算法大致可以分为投票(类聚)和最优化2大类.Hough变换、RANSAC算法都是采用映射的方法,将样本点映射到参数空间,采用累加器或者类聚的方法来检测椭圆.这类算法具有很好的健壮性,能够一次检测多个椭圆,但是需要复杂的运算和大量的存储空间.最优化方法包括最小二乘拟合算法、遗传算法以及其他最优化椭圆拟合方法.这类方法的主要特点在于准确性高,但是通常需要预先进行分割或分组处理,无法直接用于多个椭圆的检测,对噪声的敏感程度高于前一类方法.

近年来,人们对椭圆检测的研究大多在数据点收集、椭圆真伪的验证和各类方法相互结合的方向上展开.Cheng等人[1]提出的受限随机Hough变换(restrictedrandomizedHoughtransform,RRHT),限制了点选取的范围,有效缩短了算法运行的时间,提高了算法的效率.Qiao等人[2]推荐的基于圆弧的椭圆验证方法极大地减少了虚假椭圆的输出.Li等人提出的随机椭圆检测(randomizedellipsede tection,RED)方法,巧妙地结合了最小二乘法和随机Hough变换的优点,实现了基于随机Hough变换并利用最小二乘法进行椭圆拟合的检测方法,该方法不需要占用大量的存储空间,另外对噪声不敏感,能够快速检测多个椭圆.

本文首先分析了RED算法,针对基于直接最小二乘法的椭圆拟合的特点,引入了一个可能椭圆边缘点收集和椭圆重新拟合的迭代过程,提出了一种基于最小二乘法的改进的随机椭圆检测算法,解决了原算法中存在的问题.通过对具有不同噪声的仿真图片和实际图片的实验,验证了算法改进的有效性.

[3 4]

数.np表示集合V中边缘点的数量,当其与图片中边缘点总数的比值小于Tem时,终止椭圆检测算法.在可能椭圆上选中的任意两点之间的距离必须大于阈值Ta.Td表示所选的第4点到可能椭圆边界的距离的阈值.Tr为椭圆残缺率阈值.

2)当f=Tf或者np<Tem时,算法终止;否则,随机从V中选择4个点pi(i=1,2,3,4),然后从V中除去所选的4个点,V=V-{pi}.

3)根据选中的4个边缘点求出可能的椭圆,保证在选中的用于求解椭圆参数的3个点中任意2个点之间的距离都大于Ta,同时第4个点到可能椭圆边界的距离不能超过Td.否则,将pi(i=1,2,3,4)返回到V中,f=f+1,跳转到步骤2).

4)假设Eijk是可能的一个椭圆.设计数器n=0.对于V中的点pm,检查它到椭圆Eijk边界的距离是否小于阈值Td.如果是,则n=n+1,并将pm从V中去除.在遍历V中所有点之后,得到ne=n,即为满足阈值Td的边缘点的个数.

5)如果ne Tr!Cijk,其中Cijk是可能椭圆Eijk

的周长,则跳转到步骤6).在其他情况下,认为这个可能的椭圆不是一个真实的椭圆,将步骤4)中的ne个边缘点返回到V中,f=f+1,跳转到步骤2).6)可能存在的椭圆Eijk被证实是真实存在的一个椭圆.将f重置,跳转到步骤2).1.2 RED算法中存在的问题

RED算法使用直接最小二乘法椭圆拟合(di rectleastsquaresfittingofellipse)算法来求解可能椭圆的参数.Halir等人[5]指出由于该拟合算法是基于代数距离而非几何距离的,因而当拟合含有噪声的椭圆弧时,得到的椭圆通常偏小.当拟合图像中的椭圆数据点时,由于算法本身就有这种倾向,若选取的3个窗口中心点之间的距离较近,加上图像光栅化的影响(图像中椭圆的边缘点相对于理想的边缘点而言噪声总是存在的),拟合出来的椭圆和真实的椭圆差别很大.Li等人的算法只能依靠在提取可能椭圆时,随机选取的3点之间保持适当的距离,和在椭圆确认过程中使用较大的值来解决这个拟合算法带来的问题.但是这种处理方法在实际处理过程中存在较为明显的缺陷.

1)算法的效率严重地依赖于参数Ta,不合适的Ta不仅增加了算法中证据收集的计算量,还会浪费很多有效采样次数.而且合适的Ta值会随着被检测椭圆的大小发生变化,因此当处理包含大小差异较大的椭圆图形的图片时,Ta的值难以确定.

)a,Tr1 RED算法

1.1 RED算法介绍

RED方法首先随机选取3个边缘点,并分别以这3个边缘点为中心,定义具有相同大小的窗口,利用最小二乘法把这3个窗口中的所有边缘点拟合成一个假设存在的椭圆.然后在图像中随机选取第4个边缘点,判断这个点是否在假设的椭圆上.如果是,则椭圆存在的可能性较大,接着引入证据收集过程来验证椭圆是否真实存在.算法步骤如下.

1)将所有边缘点pi=(ui,vi)加入集合V中.初始化失败,计数器f=0.令Tf、Tem、Ta、Td、Tr分别f

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email