(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210199054.X (22)申请日 2022.03.02 (71)申请人 深圳汇控智能技 术有限公司 地址 518103 广东省深圳市宝安区福海街 道和平社区和秀西路87号和景工业园 12栋201 (72)发明人 谢小辉　 (74)专利代理 机构 东莞市神州众达专利商标事 务所(普通 合伙) 44251 专利代理师 周松强 (51)Int.Cl. G06T 7/66(2017.01) G06T 7/60(2017.01) G06T 5/00(2006.01) G06F 17/16(2006.01)G06F 17/15(2006.01) G06F 17/11(2006.01) G06V 10/44(2022.01) (54)发明名称 一种基于多级优化的圆拟合 算法 (57)摘要 本发明公开了一种基于多级优化的圆拟合 算法， 涉及圆拟合算法技术领域。 本发明一种基 于多级优化的圆拟合算法， 包括如下步骤： 步骤 S1： 获取输入图片的轮廓， 对所有轮廓点进行一 次最小二乘圆拟合， 得到粗圆心和粗半径； 步骤 S2： 计算轮廓所有点和粗圆心的距离及其与粗半 径的差值d1； 步骤S3： 从上一步得到的点群随机 抽取三点， 利用圆的中垂线定理得到圆的半径r 和圆心坐标； 步骤S4： 依次迭代， 加入循环中断； 步骤S5： 对所得到的内群点用Tukey权重分配函 数进行精细化处理； 本发 明综合运用3σ准则、 随 机抽样一致性 （RANSAC） 、 Tukey权重分配函数迭 代依次实现粗大误差点剔除、 高质量内群点提 取、 精细化处 理， 从而达 到多级优化的目的。 权利要求书1页 说明书6页 附图1页 CN 114612550 A 2022.06.10 CN 114612550 A 1.一种基于多级优化的圆拟合算法， 其特征在于， 所述算法包含三个阶段： 粗大误差点 剔除、 高质量内群点提取、 精细化处理， 所述算法分别采用3σ 准则、 随机抽样一致性、 Tukey 权重分配函数 逐层优化， 包括如下步骤： 步骤S1： 获取输入图片的轮廓， 对所有轮廓点进行一 次最小二乘圆拟合， 得到粗圆心和 粗半径； 步骤S2： 计算轮廓所有点和粗圆心的距离及其与粗半径的差值d1， 求其均值及标准差 s， 比较d1与3s的大小， 若d1<＝3s， 该点留下， 否则剔除； 步骤S3： 从上一步得到的点群随机抽取三点， 利用圆的中垂线定理得到圆的半径r和圆 心坐标， 计算轮廓点与r的距离d2， 若|d2 ‑r|<＝t， 则该点为内群点， 统计内群点的数量， 进 入下一次的迭代； 步骤S4： 依次迭代， 加入循环中断， 设置迭代次数K＝(log(1 ‑p))/(log(1 ‑εm))， 达到所 设置的参数 条件时迭代结束； 步骤S5： 对所得到的内群点用Tukey权重分配函数进行精细 化处理， δ＝meadian(P)/2/ 0.625并不断迭代， 迭代的终止条件为|Ck+1 ‑Ck|<10‑2、 |Rk+1‑Rk|<10‑2。 2.根据权利要求1所述的一种基于多级优化的圆拟合算法， 其特征在于， 所述 圆拟合算 法引入置信度P进 行循环中断， 在循环过程中， 至少有一次采样， 使得采样出的m个点均为类 内点， 保证在循环的过程中， 至少有一次采样能取 得目标函数的最大值。 3.根据权利要求2所述的一种基于多级优化的圆拟合算法， 其特征在于， 所述置信度设 置为[0.95,0.9 9]。 4.根据权利要求1所述的一种基于多级优化的圆拟合算法， 其特征在于， 所述步骤S3设 置阈值t＝ k*r。 5.根据权利要求1所述的一种基于多级优化的圆拟合算法， 其特征在于， 所述步骤S4中 P为置信度， k 为迭代次数， m为子集大小， ε为类内点在点 集中所占的比例。 6.根据权利要求1所述的一种基于多级优化的圆拟合算法， 其特征在于， 所述步骤S5 中 C为圆心坐标， R为圆心半径。权　利　要　求　书 1/1 页 2 CN 114612550 A 2一种基于多级优化的圆拟合算法 技术领域 [0001]本发明涉及圆拟合 算法技术领域， 特别是 涉及一种基于多 级优化的圆拟合 算法。 背景技术 [0002]圆拟合是图像处理中比较常见的一种检测形式， 也是工业中较为常见的应用场 景， 而检测算法的准确度、 运行时间及稳定性关系到评价拟合圆算法的好坏， 目前常见的圆 拟合算法主要有 标准hough变换、 最小二乘法， Hough变换将参数映射到三维空间， 需要较大 的存储空间， 计算量大， 耗时巨大， Hough变换虽然一定程度上克服了离群点的影响， 保证了 算法检测的准确度， 但其前提是设置足够合适的参数， 过于依赖参数， 鲁棒性差， 最小二乘 法拟合圆以最小化误差的平方和为 目标使所有数据点最为接近， 即曲线拟合的最好， 因为 最小二乘法需要计算所有 数据点， 所以容易受到离群点的影响， 虽然其运行时间短， 但离群 点较多时， 准确度较差； [0003]目前圆拟合研究中， 更多关注Hough变换算法性能的改进， 标准Hough圆拟合是把 圆的参数映射到三维空间， 算法的运行时间较长以及运算空间的占用也较大， 其中包括一 种基于随机Hough变换的改进圆拟合算法， 该算法运用梯度方向信息来判断随机选择的三 点是否需要进行累积， 接着再利用确定候选圆范围的方法来缩小所要搜寻的像素点的范 围， 这种方法较好地解决了传统随机Hough变换中由于随机采样而造成的大量无效累积问 题， 还包括一种基于Hough、 梯度直方图相结合的算法， 首先利用Adaboost 算法识别出人脸， 随后运用Hough变换进 行人眼初检测， 再根据简化梯度直方图特征实现人眼的精确定位， 还 包括通过引入权重函数， 剔除掉偏差较大的离群点、 孤立点， 对筛选出满足条件的边缘离散 点变换为圆存在概率图， 接着根据峰值检测确定圆的参数， 该方法大大减轻了计算量； RANSAC算法与随机Hough变换算法相似， 通过随机抽样 筛选出满足设定条件的最多点集群， 再用圆模型上的点来拟合真实圆.这两种算法的共同缺点在于大量干扰点的存在会带来大 量无效抽样和累积， 准确度有待提升， 且设定不同的阈值t及 迭代次数可能会产生不同的结 果； 还包括对RANSAC算法进行了改进， 做法是首先对图像进行预处理， 滤去较短的图形边 缘， 对提取到的候选圆多次进一步抽样提取， 重复筛选， 从而一定程度上减少了无效的抽样 次数， 最后， 用最小二乘法对这些候选圆参数进一步拟合处理； 也有 人对最小二乘法进行改 进， 包括推导了一种基于最小二乘法的圆曲线拟合方法， 以原半径与拟合半径的几何距离 差值平方和最小为准则， 其中再结合迭代法， 在非均匀采集离散点的情形下可有效地提高 拟合精度， 还包括一种基于概率密度的最小二乘 圆拟合方法， 通过多次对数据进行重复拟 合， 求得每组的拟合圆心坐标和半径， 以概率密度分布的最大值作为性能指标得到最优拟 合值； [0004]以上研究更多的是分析某种圆拟合算法并针对性的进行改进， 未充分考虑融合不 同算法的优势互补； 因此， 我们提出一种基于多 级优化的圆拟合 算法。说　明　书 1/6 页 3 CN 114612550 A 3