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

ＤＯＩ：１０．３７８５／ｊ．ｉｓｓｎ．１００８—９７３Ｘ．２００８．０８．０１５基于最小二乘法的改进的随机椭圆检测算法陈海峰１，雷华，孔燕波２，周柳云２，冯华君（１．浙江大学现代光学仪器国家重点实验室，浙江杭州３１００２７；２．宁波华光精密仪器有限公司，浙江宁波３１５１５３）摘要：为了提高数字图像中椭圆检测的效率和准确性，提出了一个基于最小二乘法的改进的随机椭圆检测算法．该算法随机选取图像中的３个边缘点，在以这３个点为中心的窗口内。从边缘点中拟合出可能椭圆，并通过随机选取的第４个边缘点来确认可能椭圆．利用直接最ｄｘ－－乘法椭圆拟合的特性，引入可能椭圆边缘点收集和椭圆重新拟合的迭代过程来提取最终的椭圆参数．通过对含有不同噪声的仿真图片和包括残缺椭圆的实际图片的实验表明，新算法的改进是有效的．与原算法相比，新算法降低了对参数的依赖性，提高了检测的速度、稳定性和准确性，同时保留了原算法的抗噪声能力．关键词：椭圆检测；随机检测；最ｄｘ－－乘法中图分类号：ＴＰ３９１文献标识码：Ａ文章编号：１００８—９７３Ｘ（２００８）０８—１３６０一０５ＡｎｉｍｐｒｏｖｅｄｒａｎｄｏｍｉｚｅｄａｌｇｏｒｉｔｈｍｆｏｒｄｅｔｅｃｔｉｎｇｅｌｌｉｐｓｅｓｂａｓｅｄｏｎｌｅａｓｔｓｑｕａｒｅａｐｐｒｏａｃｈＣＨＥＮＨａｉ—ｆｅｎ９１，ＬＥＩＨｕａｌ，ＫＯＮＧＹａｎ－ｂ０２，ＺＨＯＵＬｉｕ—ｙｕｎ２，ＦＥＮＧＨｕａ－ｊｕｎｌ（１．ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙｏｆＭｏｄｅｒｎＯｐｔｉｃａｌＩｎｓｔｒｕｍｅｎｔａｔｉｏｎ，ＺｈｅｊｉａｎｇＵｎｉｖｅｒｓｉｔｙ，Ｈａｎｇｚｈｏｕ３１００２７，Ｃｈｉｎａ；２．ＨｕａｇｕａｎｇＰｒｅｃｉｓｉｏｎＩｎｓｔｒｕｍｅｎｔＣｏ．Ｌｔｄ．，Ｎｉｎｇｂｏ３１５１５３，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ａｎｉｍｐｒｏｖｅｄｒａｎｄｏｍｉｚｅｄｅｌｌｉｐｓｅｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｔｏｏｎｌｅａｓｔｓｑｕａｒｅａｐｐｒｏａｃｈｗａｓｐｒｏｐｏｓｅｄｓｅ—ｅｎｈａｎｃｅｔｈｅｅｆｆｉｃｉｅｎｃｙａｎｄａｃｃｕｒａｃｙｏｆｅｌｌｉｐｓｅｄｅｔｅｃｔｉｏｎｉｎｄｉｇｉｔａｌｉｍａｇｅｓ．Ｔｈｉｓａｌｇｏｒｉｔｈｍｒａｎｄｏｍｌｙｕｓｅｓｌｅｃｔｓｔｈｒｅｅｅｄｇｅｐｏｉｎｔｓｉｎｔｈｅｉｍａｇｅ，ａｎｄｔｈｅｎｗｉｎｄｏｗｓ，ｗｈｉｃｈｗｈｅｔｈｅｒａａｒｅｌｅａｓｔｓｑｕａｒｅａｐｐｒｏａｃｈｔｏｆｉｔａｌｌｔｈｅｅｄｇｅｐｏｉｎｔｓｉｎｔｈｒｅｅｔｏｄｅｆｉｎｅｄｂｙｔｈｅｔｈｒｅｅｅｄｇｅｐｏｉｎｔｓ．Ｔｈｅｆｏｒｔｈｅｄｇｅｐｏｉｎｔｉｓｒａｎｄｏｍｌｙｓｅｌｅｃｔｅｄｊｕｄｇｅｐｏｓｓｉｂｌｅｅｌｌｉｐｓｅｅｘｉｓｔｓｉｎｔｈｅｉｍａｇｅ．Ｕｔｉｌｉｚｉｎｇｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｏｆｄｉｒｅｃｔｌｅａｓｔｓｑｕａｒｅｆｉｔｔｉｎｇｏｆｐｒｏｃｅｓｓｅｌｌｉｐｓｅ，ａｎｉｔｅｒａｔｉｏｎｔｏｅｘｔｒａｃｔｏｆｅｄｇｅｐｏｉｎｔｃｏｌｌｅｃｔｉｎｇａｎｄｅｌｌｉｐｓｅｒｅｆｉｔｔｉｎｇｏｆｐｏｓｓｉｂｌｅｅｌｌｉｐｓｅｗａｓｉｎｔｒｏｄｕｃｅｄｎａｔｕｒｅｔｈｅｆｉｎａｌｅｌｌｉｐｓｅ’Ｓｐａｒａｍｅｔｅｒｓ．Ａｒｔｉｆｉｃｉａｌｉｍａｇｅｓｗｉｔｈｄｉｆｆｅｒｅｎｔｌｅｖｅｌｓｏｆｎｏｉｓｅａｎｄｉｍａｇｅｓｃｏｎｔａｉｎｉｎｇｉｎｃｏｍｐｌｅｔｅｅｌｌｉｐｓｅｓｗｅｒｅｅｍｐｌｏｙｅｄｔｏｔｅｓｔｔｈｉｓａｌｇｏｒｉｔｈｍ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｉｍｐｒｏｖｅｍｅｎｔｓｐｅｎｄｅｎｃｅｏｎａｒｅｎｏｔａｂｌｅ．Ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｏｒｉｇｉｎａｌａｌｇｏｒｉｔｈｍ，ｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｒｅｄｕｃｅｓｔｈｅｄｅ—ａｒｇｕｍｅｎｔｓｏｆｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍ，ａｎｄｅｎｈａｎｃｅｓｔｈｅｓｐｅｅｄ，ｓｔａｂｉｌｉｔｙａｎｄａｃｃｕｒａｃｙｏｆｅｌｌｉｐｓｅｄｅ’ｔｅｃｔｉｏｎ，ｗｈｉｌｅｐｒｅｓｅｒｖｅｓｔｈｅａｎｔｉ—ｎｏｉｓｅａｂｉｌｉｔｙｏｆｔｈｅｏｒｉｇｉｎａｌａｌｇｏｒｉｔｈｍ．Ｋｅｙｗｏｒｄｓ：ｅｌｌｉｐｓｅｄｅｔｅｃｔｉｏｎ；ｒａｎｄｏｍｉｚｅｄｄｅｔｅｃｔｉｏｎ；ｌｅａｓｔｓｑｕａｒｅａｐｐｒｏａｃｈ．椭圆检测在模式识别领域一直是研究的热点．在过去的２０多年中，人们提出了很多椭圆检测算法．例如：基于Ｈｏｕｇｈ变换及其改进算法的椭圆检测算法、最ｄｘ＿－－乘拟合算法、基于随机抽样一致性收稿日期：２００７一０５—１８．基金项目：浙江大学学报Ｉ工学版）圈址：ｗｗｗ．ｊｏｔｌｒｎａｌｓ．ｚｉｕ．ｅｄｕ．ｃｎ／ｅｎｇ宁波市科技计划资助项目（２００６８１０００２７）．作者简介：陈海峰（１９８２一）。男，浙江台州人，硕士生，从事数字图像处理工作．Ｅ－ｍａｉｌ：ｏｐｔｉｃａｌｄｌｚ＠ｇｍａｉｌ．ｅｏｍ通讯联系人：冯华君，男．教授。博导．Ｅ－ｍａｉｌ：ｆｅｎｇｈｊ＠ｚｊｕ．ｅｄｕ．ｃｒｌ万方数据　第８期陈海峰，等：基于最小二乘法的改进的随机椭圆检测算法１３６１（ｒａｎｄｏｍｓａｍｐｌｅｃｏｎｓｅｎｓｕｓ，ＲＡＮＳＡＣ）思想的算法、遗传算法以及结合椭圆几何特性的算法．这些算法大致可以分为投票（类聚）和最优化２大类．Ｈｏｕｇｈ变换、ＲＡＮＳＡＣ算法都是采用映射的方法，将样本点映射到参数空间，采用累加器或者类聚的方法来检测椭圆．这类算法具有很好的健壮性，能够一次检测多个椭圆，但是需要复杂的运算和大量的存储空间．最优化方法包括最小二乘拟合算法、遗传算法以及其他最优化椭圆拟合方法．这类方法的主要特点在于准确性高，但是通常需要预先进行分割或分组处理，无法直接用于多个椭圆的检测，对噪声的敏感程度高于前一类方法．近年来，人们对椭圆检测的研究大多在数据点收集、椭圆真伪的验证和各类方法相互结合的方向上展开．Ｃｈｅｎｇ等人ｕ１提出的受限随机Ｈｏｕｇｈ变换（ｒｅｓｔｒｉｃｔｅｄｒａｎｄｏｍｉｚｅｄＨｏｕｇｈｔｒａｎｓｆｏｒｍ，Ｉ狠ＨＴ），限制了点选取的范围，有效缩短了算法运行的时间，提高了算法的效率．Ｑｉａｏ等人［２３推荐的基于圆弧的椭圆验证方法极大地减少了虚假椭圆的输出．Ｌｉ等人［３ｑ］提出的随机椭圆检测（ｒａｎｄｏｍｉｚｅｄｅｌｌｉｐｓｅｄｅ—ｔｅｃｔｉｏｎ，ＲＥＤ）方法，巧妙地结合了最小二乘法和随机Ｈｏｕｇｈ变换的优点，实现了基于随机Ｈｏｕｇｈ变换并利用最小二乘法进行椭圆拟合的检测方法，该方法不需要占用大量的存储空间，另外对噪声不敏感，能够快速检测多个椭圆．本文首先分析了ＲＥＤ算法，针对基于直接最小二乘法的椭圆拟合的特点，引入了一个可能椭圆边缘点收集和椭圆重新拟合的迭代过程，提出了一种基于最ｄｘ－－乘法的改进的随机椭圆检测算法，解决了原算法中存在的问题．通过对具有不同噪声的仿真图片和实际图片的实验，验证了算法改进的有效性．１ＲＥＤ算法１．１ＲＥＤ算法介绍ＲＥＤ方法首先随机选取３个边缘点，并分别以这３个边缘点为中心，定义具有相同大小的窗口，利用最ｄｘ－－乘法把这３个窗口中的所有边缘点拟合成一个假设存在的椭圆．然后在图像中随机选取第４个边缘点，判断这个点是否在假设的椭圆上．如果是，则椭圆存在的可能性较大，接着引入证据收集过程来验证椭圆是否真实存在．算法步骤如下．１）将所有边缘点Ｐ；一（“。，让）加入集合Ｖ中．初始化失败，计数器，＝０．令Ｔｈ丁ｅ。、Ｔａ、Ｌ、丁，分别为给定的５个阈值．瓦表示能够容忍的最大失败次万　方数据数．咒，表示集合Ｖ中边缘点的数量，当其与图片中边缘点总数的比值小于Ｔ。时，终止椭圆检测算法．在可能椭圆上选中的任意两点之间的距离必须大于阈值丁ａ．Ｔｄ表示所选的第４点到可能椭圆边界的距离的阈值．Ｔ，为椭圆残缺率阈值．２）当，＝丁ｆ或者ｎ，＜ｔ。时，算法终止；否则，随机从Ｖ中选择４个点Ｐｉ（ｉ一１，２，３，４），然后从ｙ中除去所选的４个点，Ｖ—Ｖ一｛Ｐｉ）．３）根据选中的４个边缘点求出可能的椭圆，保证在选中的用于求解椭圆参数的３个点中任意２个点之间的距离都大于ｔ，同时第４个点到可能椭圆边界的距离不能超过Ｔｄ．否则，将Ｐ。（ｉ＝１，２。３，４）返回到Ｖ中，．厂＝，＋１，跳转到步骤２）．４）假设Ｅ触是可能的一个椭圆．设计数器，２＝０．对于Ｖ中的点Ｐ。，检查它到椭圆Ｅ触边界的距离是否小于阈值Ｔ。．如果是，则押＝靠＋１，并将Ｐ。从Ｖ中去除．在遍历Ｖ中所有点之后，得到，ｚ。一，ｚ，即为满足阈值Ｔ。的边缘点的个数．５）如果挖。≥Ｔ，・Ｃ驰，其中Ｃ。。是可能椭圆Ｅ靴的周长，则跳转到步骤６）．在其他情况下，认为这个可能的椭圆不是一个真实的椭圆，将步骤４）中的竹。个边缘点返回到Ｖ中，，＝厂＋１，跳转到步骤２）．６）可能存在的椭圆Ｅ矾被证实是真实存在的一个椭圆．将．厂重置，跳转到步骤２）．１．２ＲＥＤ算法中存在的问题ＲＥＤ算法使用直接最小二乘法椭圆拟合（ｄｉ—ｒｅｃｔｌｅａｓｔｓｑｕａｒｅｓｆｉｔｔｉｎｇｏｆｅｌｌｉｐｓｅ）算法来求解可能椭圆的参数．Ｈａｌｉｒ等人［５１指出由于该拟合算法是基于代数距离而非几何距离的，因而当拟合含有噪声的椭圆弧时，得到的椭圆通常偏小．当拟合图像中的椭圆数据点时，由于算法本身就有这种倾向，若选取的３个窗口中心点之间的距离较近，加上图像光栅化的影响（图像中椭圆的边缘点相对于理想的边缘点而言噪声总是存在的），拟合出来的椭圆和真实的椭圆差别很大．Ｌｉ等人的算法只能依靠在提取可能椭圆时，随机选取的３点之间保持适当的距离，和在椭圆确认过程中使用较大的值来解决这个拟合算法带来的问题．但是这种处理方法在实际处理过程中存在较为明显的缺陷．１）算法的效率严重地依赖于参数Ｔａ，不合适的Ｔａ不仅增加了算法中证据收集的计算量，还会浪费很多有效采样次数．而且合适的Ｌ值会随着被检测椭圆的大小发生变化，因此当处理包含大小差异较大的椭圆图形的图片时，Ｌ的值难以确定．２）当ｔ取不到合适的值，Ｔｒ又无法选取较大１３６２浙江大学的数值时（也就是处理包含大小差别较大的残缺椭圆的图像），采用直接椭圆拟合算法得到的偏小的可能椭圆，会因为较小的Ｔ，值而被算法确认为真椭圆，从而产生误检．由于在检测到一个椭圆后，算法会将在这个椭圆上的边缘点去除。这种误检就可能导致一个真实存在的椭圆被分割成数个椭圆弧，继而引发更多的误检，使得算法的检测效率很低．３）算法只考虑了当选取的点之间距离较近时会拟合出虚假的椭圆，没有排除当距离过大时算法会从不同椭圆弧中拟合出虚假椭圆的情况．后一种情况会当丁，较小时，被算法确认为真椭圆，降低算法检测的效率．２改进的ＲＥＤ算法２．１改进的椭圆提取过程在ＲＥＤ算法的实际拟合过程中，用来拟合的边缘点始终位于最后拟合出来的椭圆的边界上．假设这些边缘点位于一个真实的椭圆上，那么可以选择适当的代数距离来收集距离拟合出的可能椭圆边界一定范围内的边缘点：Ｄ—ｆａｕ２＋６矗可＋ｃ扩＋ｄ“＋Ｐ可＋１ｆ．然后通过重新收集和重新拟合的迭代过程来找出这个真实的椭圆．通过此过程，无须事先找出最适合的Ｔａ，只要将选取的３个点之间的距离控制在一定的范围即可．在新的提取过程中，求取适当的代数距离阈值非常关键．一般来说，如果一个点位于椭圆上，那么理想的Ｄ值应该为零．实际上，由于图像是光栅化的，边缘上的点几乎不可能准确地落在椭圆的边界上．周１显示了一系列椭圆的Ｄ值的最大值和平均值．这些椭圆的长轴、短轴、中心位置都是一致的，惟一不同的就是椭圆长轴和Ｘ轴的夹角．从图１中不难看出，在实际情况下，光栅化后椭圆的Ｄ值大小随口发生很大的变化．因此，本算法０００Ｑ０ＯＯ—１．５一１．０—０．５００．５Ｉ．０１．５０／ｔａｄ圈１Ｄ－０曲线Ｆｉｇ．１／９－０ｃｕｒｖｅｓ万　方数据学报（工学版）第４２卷使用可能椭圆Ｅ稚求解自适应阈值Ｔ。：Ｔｄ＝ｌ口“★＋ｂｕＡ可Ａ＋。ｃＸ＋ｄｕＡ＋ｅｖＡ＋１Ｉ，１ＵＡ＝Ｕｏ＋（Ａ＋ｄ耐ｆ）・ＣＯＳ妒，｝．可Ａ＝口ｏ＋（Ａ＋ｄ删）・ｓｉｎ鼽Ｊ式中：ｕｏ、％为椭圆的中心点坐标，九。为点到椭圆边界的最大距离，Ａ、舻分别为椭圆的长轴长度和椭圆的偏转角度．在迭代过程中，需要考虑在边缘二值图像中噪声的影响．过量的噪声将会延长迭代收敛的过程，因此在执行之前需要将这些噪声点从边缘图像中去除．本文采用黎自强等人［６］提出的去除孤立和半连续噪声点的方法．这两类噪声点的定义如下：在图像空间中，若Ｐｉ（Ｕｉ，研）的８个相邻点都不是图像点，则称Ｐ为孤立噪声点．若只（辑，砧）的４×４邻域满足：１）边界点都不是图像点；２）除了Ｐ，（阮，ｑ），在其相邻点中还有ｌ～３个图像点，则称Ｐ为半连续噪声点．２．２改进算法的具体步骤改进的ＲＥＤ算法只须在原有算法的步骤５）和６）中插入新的椭圆提取过程．具体流程如下．１）初始化Ｔ一０；设置最大迭代次数Ｔｔ和最小变化率Ｌ，用于算法的终止；将行。的值赋给以。ｍ２）用收集来的位于可能椭圆边界附近的边缘点组成的可能椭圆边界点集合ｙ。来重新拟合可能椭圆Ｅ矾；丁＝Ｔ＋１．３）根据可能椭圆Ｅ触求解Ｔ。的大小；遍历集合Ｖ中的边缘点，寻找Ｄ≤Ｔｄ的边缘点，更新以。和可能椭圆边界点集合Ｖ。，并将咒。赋给以。。。；如果Ｉ竹。。一押。。。ｌ／以。埘＞Ｔ。并且Ｔ＜Ｔ。，则跳转到步骤２）；否则算法终止，Ｖ＝Ｖ—Ｖｅ；输出椭圆参数．３实验结果在一台Ｃｅｌｅｒｏｎ２．０ＧＨｚ的计算机上利用Ｍａｔｌａｂ６．５对改进的ＲＥＤ算法进行了仿真图片和实际图片的实验．主要分析算法改进前后检测的时间、准确率［７］和抗噪声的能力．对于每一副图片，取１００次检测的结果作为样本．选用的参数在各个实验中分别给出．在下面的图表中用Ｏｒｉｇ表示原ＲＥＤ算法，Ｍｏｄ表示改进的ＲＥＤ算法．实验１分别用原ＲＥＤ算法和改进的ＲＥＤ算法对３幅６４０×４８０的仿真图片进行检测，如图２（ａ）所示．其中图片１含有３个不同方向的完整椭圆；图片２含有３个不同方向的重叠的椭圆；图片３含有３个不同方向的部分重叠的椭圆弧，并且这些第８期陈海峰，等：基于最小二乘法的改进的随机椭圆检测算法表１实验选用的各个参数Ｔａｂ．１Ａｒｇｕｍｅｎｔｓｕｓｅｄｉｎｅｘｐｅｒｉｍｅｎｔ１图２（ｂ）、（ｃ）列出了原ＲＥＤ算法和改进的ＲＥＤ图片２图片３算法的检测结果．检测到的椭圆用粗线重绘，加号表（ａ）原图（仿真图片）示椭圆中心点位置．表３进一步给出了２个算法比较的结果，包括算法检测的最短时间ｔ而。、最长时间ｆ。。、平均时间ｔ。。、标准时间ｔ。。。和准确率Ｐ。．在本文设定的实验例子中，原ＲＥＤ算法无法继续使用Ｔａ、Ｔｒ的限制来解决拟合算法带来的问题，导致整个椭圆算法运行时间较长，稳定性不佳，有较多误检的情况影响其他真实存在椭圆的检测．改进的ＲＥＤ算法很好地解决了拟合算法带来的问题，无论在准确性、稳定性（ｂ）原ＲＥＤ算法检测结果上，还是在检测速度上都超越了原ＲＥＤ算法．实验２检测改进的ＲＥＤ算法抗椒盐噪声的能力．选用实验１中使用的仿真图片，在实验中加入的椒盐噪声的数量为Ｎ。。。，从边缘点数量的１倍逐渐增加到６倍．为保证对照的有效性，原ＲＥＤ算法处理的图片同样经过了前面提到的剔除２类噪声的处理．算法的参数和实验１相同．结果如图３和４所示．可以看出，改进的ＲＥＤ算法在３倍噪声以内时表现非常出色，在超过这个范围之后，算法的准确性和消耗（ｃ）改进的ＲＥＤ算法检测结果的时间都有所恶化，但是依然好于原ＲＥＤ算法．图２改进的ＲＥＤ算法与原ＲＥＤ算法的检测结果（仿实验３选用实际的图片对改进的ＲＥＤ算法进真图片）行测试，原ＲＥＤ算法作为对照．图片大小均为６４０×Ｆｉｇ．２ＤｅｔｅｃｔｉｏｎｒｅｓｕｌｔｓｏｆｉｍｐｒｏｖｅｄＲＥＤａｌｇｏｒｉｔｈｍａｎｄ４８０，图片４包含多个大小、方向各异，残缺度不同的ｏｒｉｇｉｎａｌＲＥＤａｌｇｏｒｉｔｈｍ（ａｒｔｉｆｉｃｉａｌｉｍａｇｅ）椭圆，图片５包含多个偏心率接近零的椭圆，如图５图片中包含的３个椭圆的大小差别较大．根据文献（ａ）所示．实验中选用绝对误差模板（ａｂｓｏｌｕｔｅｄｉｆｆｅｒ—［４］，实验选取Ｔ，＝ｏ．５，在原ＲＥＤ算法中根据符合ｅｎｃｅｍａｓｋ，ＡＤＭ）算法［８３作为边缘检测算子．同样选图片中最小残缺椭圆的检测要求，选取Ｔａ＝３０，算取Ｔｒ＝０．５，Ｔａ一３０，Ｔｅ。值则按照实际情况做了调法的具体参数如表ｌ所示．整，具体参数见表１．实验结果如表２与图５所示．裹２改进的ＲＥＤ算法与原ＲＥＤ算法的性能比较Ｔａｂ．２ＰｅｒｆｏｒｍａｎｃｅｃｏｍｐａｒｉｓｏｎｏｆｉｍｐｒｏｖｅｄＲＥＤａｌｇｏｒｉｔｈｍａｎｄｏｒｉｇｉｎａｌＲＥＤａｌｇｏｒｉｔｈｍ万　方数据１３６４浙江大学ＩＯＯ零８０、？乱６０２３＾，４５６』Ｖ们＿●ｔ＋Ｍｏｄ（图片１）＋Ｍｏｄ（图片２）＋Ｍｏｄ（图片３）。・‘Ｏｒｉｇ（图片１）一▲・Ｏｒｉｇ（１鍪ｌ片２）一－‘Ｏｒｉｇ（图片３）圈３在不同噪声下算法的准确性Ｆｉｇ．３Ｐｅｒｃｅｎｔａｇｅａｃｃｕｒａｃｙｗｉｔｈｍｕｌｔｉｐｌｅｎｏｉｓｅｓ２ｌ差ｌ２３４５６．－．４１－－Ｍｏｄ（图片１）＋Ｍｏｄ（１酮片２）＋Ｍｏｄ（１酮片３）儿。一・。Ｏｒｉｇ（图片１）一▲・Ｏｒｉｇ（图片２）一。。Ｏｒｉｇ（１奎ｌＪＬ｛３）图４在不同噪声下算法的执行时间Ｆｉｇ．４Ａｖｅｒａｇｅｃｏｍｐｕｔａｔｉｏｎｔｉｍｅｗｉｔｈｍｕｌｔｉｐｌｅｎｏｉｓｅｓ图片４矧片５（ａ）原图（实际图片）（ｂ）原ＲＥＤ算法检测结果（Ｃ）改进的ＲＥＤ算法检测结果圈５改进的ＲＥＤ算法与原ＲＥＤ算法检测结果（实际图片）Ｆｉｇ．５ＤｅｔｅｃｔｉｏｎｒｅｓｕｌｔｓｏｆｉｍｐｒｏｖｅｄＲＥＤａｌｇｏｒｉｔｈｍａｎｄｏｒｉｇｉｎａｌＲＥＤａｌｇｏｒｉｔｈｍ（ｒｅａｌｉｍａｇｅＪ４结语本文对原有的基于最ｄｘ－－乘法的随机椭圆检测万　方数据学报（工学版）第４２卷方法进行了改进．新方法在确认一个可能椭圆之后，使用自适应的Ｔ。阈值搜索边缘图片中距离可能椭圆边界一定范围内的点，并拟合出一个新的可能椭圆．通过重复上述搜索和重新拟合过程，准确地找到了图片中的椭圆．对仿真图片和实际图片的实验表明，改进算法有效解决了原方法存在的问题．使得算法对参数Ｔａ、丁，的依赖程度大大下降，改善了算法对不同情况的适应性．新算法在提高检测的速度、稳定性和准确性的同时，保留了原算法抗噪声的能力．参考文献（Ｒｅｆｅｒｅｎｃｅｓ）：Ｅ１３ＣＨＥＮＧＺｉ—ｇｕｏ，ＬＩＵＹｕｎ－ｃａｉ．ＥｆｆｉｃｉｅｎｔｔｅｃｈｎｉｑｕｅｆｏｒｅｌｌｉｐｓｅｄｅｔｅｃｔｉｏｎｕｓｉｎｇｒｅｓｔｒｉｃｔｅｄｒａｎｄｏｍｉｚｅｄＨｏｕｇｈｔｒａｎｓｆｏｒｍ［Ｃ］／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒ—ｅｎｃｅｏｎＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ：ＣｏｄｉｎｇａｎｄＣｏｍｐｕｔｉｎｇ．ＬａｓＶｅｇａｓ：ＩＥＥＥ，２００４，２：７１４—７１８．［２３ＱＩＡＯＹｕ，ＯＮＧＳＨ．Ａｒｃ－ｂａｓｅｄｅｖａｌｕａｔｉｏｎａｎｄｄｅｔｅｃ—ｔｉｏｎｏｆｅｌｌｉｐｓｅ［Ｊ］．ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ，２００７，４０（７）：１９９０—２００３．［３３ＬＩＬｉａｎｇ－ｆｕ，ＦＥＮＧＺｕ－ｒｅｎ，ＨＥＫａｉ—ｌｉａｎｇ．Ａｒａｎｄｏｍ—ｉｚｅｄａｌｇｏｒｉｔｈｍｆｏｒｄｅｔｅｃｔｉｎｇｍｕｌｔｉｐｌｅｅｌｌｉｐｓｅｓｂａｓｅｄｏｎｌｅａｓｔｓｑｕａｒｅａｐｐｒｏａｃｈ［Ｊ］．Ｏｐｔｏ－ｅｌｅｃｔｒｏｎｉｃｓＲｅｎｅｗ，２００５。１３（１）：６１—６７．［４］李良福，冯祖仁，贺凯良．一种基于随机Ｈｏｕｇｈ变化的椭圆检测算法研究［Ｊ］．模式识别与人工智能，２００５，１８（４）：４５９—４６４．ＬＩＬｉａｎｇ－ｆｕ。ＦＥＮＧＺｕ—ｒｅｎ，ＨＥＫａｉ—ｌｉａｎｇ．Ａｎｉｍ—ｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｆｏｒｅｌｌｉｐｓｅｓｄｅｔｅｃｔｉｏｎｂａｓｅｄｏｎｒａｎｄｏｍ—ｉｚｅｄＨｏｕｇｈｔｒａｎｓｆｏｒｍ［Ｊ］．ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎａｎｄＡｒｔｉ—ｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ，２００５，１８（４）：４５９—４６４．［５３ＨＡＬＩＲＲ，ＦＬＵＳＳＥＲＪ．Ｎｕｍｅｒｉｃａｌｌｙｓｔａｂｌｅｄｉｒｅｃｔｌｅａｓｔｓｑｕａｒｅｓｆｉｔｔｉｎｇｏｆｅｌｌｉｐｓｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ６ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｉｎＣｅｎｔｒａｌＥｕｒｏｐｅｏｎＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓａｎｄＶｉｓｕａｌｉｚａｔｉｏｎ．Ｐｌｚｅｎ：ＵｎｉｖｅｒｓｉｔｙｏｆＷｅｓｔＢｏｈｅｍｉａ，１９９８：１２５—１３２．［６］黎自强，腾弘飞．广义Ｈｏｕｇｈ变换：多圆的快速随机检测［Ｊ］．计算机辅助设计与图形学学报，２００６，１８（１）：２７—３３．ＬＩＺｉ—ｑｉａｎｇ。ＴＥＮＧＨｏｎｇ－ｆｅｉ．ＧｅｎｅｒａｌｉｚｅｄＨｏｕｇｈｔｒａｎｓ—ｆｏｒｍ：ｆａｓｔｒａｎｄｏｍｉｚｅｄｍｕｌｔｉ—ｃｉｒｃｌｅｄｅｔｅｃｔｉｏｎ［Ｊ］．Ｃｏｍ－ｐｕｔｅｒＡｉｄｅｄＤｅｓｉｇｎａｎｄＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ，２００６，１８（１）：２７—３３．［７３ＭｃＬＡｕＧＨＬＩＭＲＡ．ＲａｎｄｏｍｉｚｅｄＨｏｕｇｈｔｒａｎｓｆｏｒｍ：ｉｍｐｒｏｖｅｄｅｌｌｉｐｓｅｄｅｔｅｃｔｉｏｎｗｉｔｈｃｏｍｐａｒｉｓｏｎ［Ｊ］．ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎＬｅｔｔｅｒｓ，１９９８，１９（３）：２９９—３０５．［８］ＺＨＡＮＧＳｉ—ｃｈｅｎｇ，ＩＡＵＺｈｉ—ｑｉａｎｇ．Ａｒｏｂｕｓｔ，ｒｅａｌ－ｔｉｍｅｅｌｌｉｐｓｅｄｅｔｅｃｔｏｒ［Ｊ］．ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ，２００５，３８（２）：２７３—２８７．