图像处理 环境建模 最小二乘法 计算机视觉
第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
成都 610041 ) 摘要:提出了一种利用最小二乘法迭代修正随机圆检测的改进算法。 ...当椭圆检测时,陈海峰,雷华 等[10]提出了基于最小二乘法对此问题改进。本文...
基于最小二乘法的椭圆拟合... 4页 免费 基于最小二乘法的椭圆拟合... 6页....101 摘要 :提 出了一种 利用最小二 乘法迭代修正随机 圆检测 的改进算法 ...
基于最小二乘法的椭圆拟合改进算法基于最小二乘法的...针对这种情况, 采用随机理论的思想, 先随机选取 6... 椭圆的鲁棒精确提取在图像 识别与计算机视觉中有着...
基于最小二乘法的椭圆拟合改进算法_数学_自然科学_专业资料。基于最小二乘法研究...所以会对椭圆拟合的最后结果产生偏差.针对这种情况,采用随机理论的思想,先随机...
变换 的椭圆检测算法 , 〔一 了〕, 其基 本 , 原理是从 图像 中随机选取三个边缘像素点在每一 个点周 围定 义一个邻域并利用最小二乘法在每个 阴丰...
基于最小二乘法的椭圆拟合改进算法闫摘 蓓 王 斌 ... 椭圆的鲁棒精确提取在图像 识别与计算机视觉中有着...最小二乘法是在随机误差为正态分布时, [ 4] 由...
? ? ? , 利用最小二乘法对这三个窗口中 的所 有边缘点进行椭圆拟 ? 合...) ? , 于是 人们又提出了一种改进的基于随机 + / 变换的椭圆检测算法 0% ...
基于最小二乘法的椭圆拟合改进算法_IT/计算机_专业...识别与计算机视觉中有着特别重要的意义.常用 的椭圆...本文提出一种算法:在所有样本点中随机取6 个点(...
基于最小二乘法的一种椭圆中心定位方法 文章利用CACH算法对数字影像进行预处理,最小二乘方法进行椭圆中心定位,在数字摄影测量中左右影响对标志中心图像坐标上非常有效...
热门文档