�2008年3月第34卷第3期北京航空航天大学学报JournalofBeijingUniversityofAeronauticsandAstronauticsMarch�2008Vo.l34�No�3�收稿日期:2007�06�29�作者简介:闫�蓓(1965-),女,河北邱县人,副教授,yanbe@ibuaa.edu.cn.基于最小二乘法的椭圆拟合改进算法闫�蓓��王�斌��李�媛(北京航空航天大学自动化科学与电气工程学院,北京100083)��摘���要:基于最小二乘法研究了一种改进的椭圆拟合算法.最小二乘椭圆拟合算法,由于包含误差较大样本点在内的所有样本点都参与运算,所以会对椭圆拟合的最后结果产生偏差.针对这种情况,采用随机理论的思想,先随机选取6个点拟合椭圆,然后计算与此椭圆匹配的所有样本点个数.重复此过程一定次数,采用投票机制,匹配样本点多的椭圆即为最优椭圆,构造了一种快速准确剔除误差较大样本点的改进椭圆拟合算法,并在实际图像应用中验证了算法能够有效地处理包含有较大比例误差点的样本空间,拟合出具有高精度的椭圆,并且算法的速度能够满足实时性的要求.关�键�词:最小二乘拟合;曲线拟合;椭圆拟合中图分类号:O241.5文献标识码:A����文章编号:1001�5965(2008)03�0295�04Optmialellipsefittingmethodbasedonleast�squareprincipleYanBei�WangBin�LiYuan(SchoolofAutomationScienceandElectricalEngineering,BeijingUniversityofAeronauticsandAstronautics,Beijing100083,China)Abstract:Thefragmentalellipsefittingalgorithmbasedonleastsquarewasstudied.Theellipse�con�straintalgebraicfittingalwaysprovidesanellipticalsolution,butthebiasisinevitablyaddedtoresultbecausethealgorithminvolvesallthesampledataincludingsomemuchbiaseddata.Basedonthissituation,theran�domtheorywasintroduced.Firs,tanellipsewasfittedbysixpointswhichwereselectedrandomly.Thenthenumberofpointswhichmatchtheellipsewascalculated.Repeatingtheprocesssometimes,accordingtothevotingmechanism,thebestellipseistheellipsewhosematchingpointnumberislarges.tArapidalgorithmwiththeabilitytoabandonthebiasedsampledatawaspresented.Theapplicationofalgorithminareal�timeimageprocessingsystemdemonstratesthatthisalgorithmcanefficientlyfitanellipsetoexperimentaldatain�cludingasignificantpercentageofgrosserrorsandtherapidityofthealgorithmcanmeettherequirementofre�al�timesystem.Keywords:leastsquarefitting;curvefitting;ellipsefitting��在计算机视觉中,二次曲线与点、直线一样被认为是最基本的图像特征.现实生活中大量物体的透视投影均为椭圆,椭圆拟合是后续物件辨识与测量的先决条件,椭圆的鲁棒精确提取在图像识别与计算机视觉中有着特别重要的意义.常用的椭圆拟合方法主要有3类:基于HOUGH变换的椭圆拟合方法,基于不变矩方法,基于最小二乘法(LSM,Least�SquareMethod).在这3种方法中,最小二乘法是在随机误差为正态分布时,由最大似然法推出的一个最优估计技术,它可使测量误差的平方和最小,因此也被视为从一组测量值中求出一组未知量的最可信赖的方法之一.在开发人眼瞳孔中心定位算法过程中,需要先用图像处理的方法提取人眼瞳孔的边界样本点,然后对这些样本点进行椭圆拟合求取瞳孔中心.但由于提取的瞳孔边界样本点不可避免地存在一些误差较大的样本点,如果直接将包含这些误差较大样本点在内的所有样本点用最小二乘法进行椭圆拟合,拟合误差比较大,不能满足系统要求.本文提出一种算法:在所有样本点中随机取6个点(由于至少5个点唯一确定一个椭圆),利用基于代数距离最小二乘法拟合一个椭圆,测量所有样本点到这个椭圆的距离,把距离小于某一阈值的点称为匹配点,否则称为杂质点,统计匹配点的总个数.重复这个过程100~200次,求得所有椭圆中匹配点最多的即为最优椭圆.实践证明:通过本算法进行椭圆拟合,可以大大降低拟合误差,并且由于算法所需计算时间较少,完全可以应用在实时系统中.1�椭圆表示和最小二乘法拟合1.1�椭圆的表示方法在二维平面坐标系中,椭圆一般可以用2种形式来表示,一种是利用圆锥曲线方程的代数形式表...
