基于最小二乘的圆及椭圆检测算法

1、基于最小二乘原理的圆及椭圆检测算法*孔 兵 王 昭 谭玉山（西安交通大学激光与红外应用研究所，西安，, ）摘 要 在光学测量中，圆或椭圆检测检测是经常用到的一项关键技术。检测算法的精度、速度直接影响了光学测量的精度及速度，而传统的检测算法如重心法、Hough变换法等在检测精度或速度上存在不足之处。本文首次提出的基于最小二乘原理的圆及椭圆检测算法，达到亚像素级的定位精度，而且还具有很快的计算速度，可适用于实时的光学测量。关键词 最小二乘算法 图像处理 圆 椭圆中图分类号 TP391The Circle and Ellipse Detection Algorithm

2、Based on Least Square MethodKONG Bing WANG Zhao TAN Yu-Shan(Institute of Laser & Infrared Technology Application, Xian Jiaotong University, Xian, )AbstractThe circle and ellipse detection is the key technique, which is always used in the optical measurement. The precision and speed of the detection

3、algorithm influence those of the optical measurement system directly. The traditional algorithms such as gravity model, Hough transform are unsatisfactory in some conditions. The circle and ellipse detection algorithm based on the least square method is firstly referred in this paper. The orientatio

4、n precision is in the order of inferior pixels, and the speed is fast with the algorithm. The algorithm is suitable for the real-time optical measurement.Key wordsLSM(least square method), digital image processing, circle, ellipse0引 言激光光斑中心检测在激光扫描三角法、激光准直仪、激光光斑分析仪等光学测量、检测手段中是一项关键技术1,2，检测算法的精度、速度直接影响

5、了光学测量的精度及速度。传统的光斑中心检测算法有重心法、中值法，以及Hough变换法1。前两种算法要求光斑图像分布比较均匀，否则将会参生较大误差。后一种算法需逐点投票、记录，所用时间较多，而且精度也不够高。然而由于在实际光学测量中，由于存在的散斑、被测物面反射特性不均匀以及光学系统的影响，导致光斑信号强度分布极不均匀，而且测量中一般对实时性要求较高，采用上述算法均有其不足之处。本文首次提出了基于最小二乘原理的圆及椭圆检测算法，可以同时检测光斑中心及半径（或长、短轴），达到亚像素级的定位精度，而且还具有毫秒级的计算速度，可适用于实时的光学测量。1传统圆检测算法11 重心法*受自然科学基金()及西

6、安交通大学在职博士基金资助以图1为例进行分析，假设光斑图像处于二维平面坐标系中，大小为，光斑图像是经过预处理后得到二值图像（下同），图中较亮的区域即代表了激光光斑，可表示为图1 光斑图像（1）重心法计算的光斑中心为（2）以时间复杂度来考虑算法的速度，假设光斑直径为，以下均做相同的假设，（2）式是在光斑区域内求和，因此时间复杂度为3。该算法简单明了，计算速度较快，在光斑光强比较均匀的情况下（对应的图1中光斑形状比较规则）不失为一种好的算法。但是该算法受光斑形状影响比较大，而且只能获取光斑的中心不能检测半径，在某些需要计算光斑半径的测量中不能适用。12 Hough变换法采用Hough变换检测任意曲

7、线的原理如下4：检测曲线的参数方程记为（3）其中，为方程参数，为空间图像点坐标。对于图像中任一空间点，可由（3）式变换为参数空间中的一条曲线。对图像曲线上个点进行上述变换，在参数空间得到条曲线，由（3）式可知这条曲线必定经过同一点，根据参数空间的此点坐标便可确定图像空间域中的曲线。直线、圆的参数方程分别为： （4）（5）Hough变换是将空间域内每个轮廓点带入参数方程（3），根据计算结果对参数空间中的量化点按就近原则进行投票，得票最多的点既为所求图像空间域中曲线对应的参数空间点。由（5）式，圆的参数空间为，其中表示圆心，表示半径，因此采用Hough变换可以检测出激光光斑的中心及半径。Hough

8、变换需要对参数空间离散化，限制了检测精度，另外参数空间得票最多的点未必唯一，选择不同的点得到的图像空间曲线差异比较大。圆的Hough变换由于对每一个边界点都需要在三维参数空间内逐点投票、记录，时间复杂度为，计算时间比较长，而且占用计算机内存比较大，因此在实用中受到了限制。2 基于最小二乘原理的圆及椭圆检测算法21 圆检测算法基于圆拟合的激光光斑中心检测算法，根据最小二乘原理（残差平方和最小）用圆来逼近激光光斑轮廓。圆的方程为：（6）在此，取残差为：（7）其中，表示所有边界的集合，表示图像边界点坐标。残差平方和函数为：（8）根据最小二乘原理5，应有（9）即（10）将（10）式简化整理得：（11）

9、其中各参数可用下式表示：（12）对（11）式消掉二次项后整理为：（13）由上式便可推出参数的表达式，结合（11）式得圆参数为：（14）由（14）式可以看出，根据最小二乘原理的圆拟合推导出的光斑中心（及半径）检测算法虽然形式复杂，但仅对边界点循环一次就可计算出各参数，时间复杂度为，较为复杂的开根方运算只是在计算出中心参数后计算半径时仅计算一次，因此整个算法的计算速度将会很快。22 椭圆检测算法椭圆方程标准形式为：（15）将其变形为：（16）其中 同样取残差（17）残差平方和函数为：（18）由最小二乘原理有（19）即（20）将（10）式简化整理得：（21）其中，（22）将（21）式消掉二次项a2，

10、及三次项cb2得（23）其中，（24）记，（23）式化为：（25）由上式可解得的值，也就计算出的值，进而由（21）式计算的值（26）由也就可以计算椭圆长、短轴的值（27）同样，仅对边界点循环一次就可计算出椭圆各参数，时间复杂度为，算法具有很快的计算速度。3 通过迭代法进一步提高检测精度获得圆或椭圆的参数后，便可根据（7）式或（17）式获得各边界点残差，只要去掉残差较大的边界点，保留残差较小的边界点，重新按照（14）式或（25）、（26）、（27）式计算圆或椭圆的参数，经多次迭代便可进一步提高检测精度。在此可设定平均残差平方和作为阈值，平均残差平方和由下式求取(28)其中，残差平方和由（8）式或

11、（18）式求取。图2 圆形光斑检测4 实验生成一幅人工图像，图中的圆边界加入了干扰，原始中心为（344，288），如图2中小十字A所示，半径为199。在Pentium II266MHz计算机上分别对重心法及本方法进行了比较，重心法获取的中心坐标位置为（336.7,289.6 ），如图2中小十字线B所示，不能检测半径，所用计算时间为11ms。基于圆拟合的方法采用上述思想进行了两次迭代，检测的中心坐标为(341.0,287.9)，如图2中灰十字线C所示，半径为195.2，用灰色标记出检测出的圆，计算时间为3.3ms。生成另一幅人工图像，图中的椭圆边界同样加入了干扰，原始中心为（244，220），在

12、图3中以小十字所示，长短轴分别为。图a为没有经过迭代直接根据最小二乘法检测出的椭圆，图b为经过一次迭代检测出的椭圆，图c为经过两次迭代检测出的椭圆，图d为经过三次迭代检测出的椭圆。检测的中心，长、短轴，与理想中心变差，以及计算时间如表1所示，由此可见，采用最小二乘法检测椭圆并经23次迭代便可获较高的检测精度。(a)无迭代(b)一次迭代(c)两次迭代(d)三次迭代图3 椭圆形光斑检测表1 椭圆检测结果迭代次数中心长、短轴与理想中心偏差计算时间(ms)0233.8199.0180.2111.011.394.41236.2202.9187.7111.77.845.62241.8203.8195.33242.5204.0196.2111.21.547.85结论相对于重心法、Hough变换法，本文提出的基于圆及椭圆拟合的光斑检测算法除了光斑中心和半径（长、短轴）可同时检测外，还具有更快的计算速度及检测精度，可用于实时的光学测量及检测。参考文献1 杨耀权, 施仁, 于希宁, 高镗年. 用Hough变换提高激光光斑中心定位精度的算法. 光学学报, 1999, 19(12):165516602 Paul J, Frederick W, David L, Randy T. Nova