最小二乘改进算法及其在椭圆拟合中的应用

图 ２ 归一化最小二乘算法拟合结果的误差及 标准差分布图
法对拟合参数进行求解可以得到拟合椭圆的特征参数， 如表 ２ 所示。
表 ２ 最小二乘算法拟合结果 ＩＤ １ ２ ３ ４ ｏｘ ２ ４６ １ ． ８３８ ０４５ ２ ２３０． ８３８ ０４３ ２ ５３６ ． ８３７ ９０ １ ２ ３０７ ． ８３７ ８７６ ｏｙ ６４４． ９９９ ６２０ ６ ６６６ ． ９９９ ５７８ ８ １ ４６３ ． ９９９ ３３０ ０ １ ４８３ ． ９９９ ３０ １ ０ ａ １４． ２４９ ０５６ ４８ １４． ２４９ １ １ ８ ２９ １４． ２４９ ４９２ ７３ １４． ２４９ ５３０ ３６ ｂ １４． ２０５ ２９６ ６９ １４． ２０５ ２３５ ８３ １４． ２０４ ８６７ ２４ １４． ２０４ ８３０ ６９ θ －１ ． ３ １０ ７８ １ ０９９ －１ ． ２７６ ７９０ ６５２ －１ ． ０５２ ７ １６ ０７９ －１ ． ００７ ７９７ ６２４
０ 引言
视觉测量系统中， 边缘检测提取的准确性直接影响 了最 终测 量 的 精 度。 边 缘 检 测 的 过 程 是 使 用 数 学方法提取图像像元中具有亮度值（ 灰度） 空间方向梯度大 的 边、 线特征 的过 程。边 缘检 测和边 缘 提取 是图像处理和计算机视觉中的基本问题， 其目的在于将数 字图像中亮 度 变 化 明 显 的 点 标 识 出 来。图 像 属性中的显著变化通常反映了属性的重要事件和变化。在边缘检测技术中常用的一种方法就是对提取 的轮廓边缘进行拟合。椭圆拟合在数字图像处理、 计算机视觉和模式识别中有着很重要的地位， 但是由 于在很多实际图像中不仅存在噪声， 还存在一些难 以剔除 的孤立 点， 因 此， 找 到 一 种 稳 健、 有 效、 易用的 椭圆拟合方法一直很难。
· ２０· ｆｏｒ ｉ ＝１ ： ｍ
河 南 科 技 大 学 学 报 ：自 然 科 学 版 ２０ １４ 年
Ａｂａｒ（ ｉ， １） ＾ ２ ＋ Ａｂａｒ（ ｉ， ２） ＾ ２） ； ｓｃａｌｅ ＝ ｓｃａｌｅ ＋ ｓｑｒｔ （ ｅｎｄ ｓｃａｌｅ ＝ ｓｃａｌｅ ／ ｍ； ｓｃａｌｅ ＝ ｓｑｒｔ （ ２） ／ ｓｃａｌｅ ； ／ ／ 得到变换因子 ／ 开始执行变换 ／ ｔ ＝ ｚｅｒｏｓ （ ３， ３） ； ｔ（ １， １ ） ＝ ｓｃａｌｅ ； ｔ（ ２， ２ ） ＝ ｓｃａｌｅ ； ｔ（ ３， ３） ＝ １ ； ｔ（ １， ３ ） ＝ －ｓｃａｌｅ ｄＣｅｎｔｅｒＸ ； ｔ（ ２， ３ ） ＝ －ｓｃａｌｅ ｄＣｅｎｔｅｒＹ ； 经过本算法处理后， 可以得到由一系列连续的点组 成一 个椭 圆。对 参 数 进 行 反 归 一 化 处 理 后 可 以 得到各参数在绝对坐标系中的坐标值。 根据拟合出的方程的参数可以求得拟合椭圆的特征参数， 如表 １ 所示。
第３期
马向南等： 最小二乘改进算法及其在椭圆拟合中的应用
· １ ９·
所给出的图像中进行拟合时的不足。
１ 引入归一化的最小二乘拟合算法
归一化是一种简化计算法， 即将有量纲的表达式 经过变 换， 化 为 无 量 纲 的 表 达 式， 成 为 纯 量。将 这 种方法应用于椭圆拟合中， 可以弱化椭圆上位置不同的点对椭圆方程参数估计贡献的差别， 减小拟合出 的椭圆产生偏差的可能性。因此， 本文将归一化方法应用到了椭圆的最小二乘拟合中。该算法步骤为： （ １） 将要处理的图像调入系统。 ２） 用 ｃａｎｄｄｙ 算法对图像进行边缘检测。 （ （ ３） 搜索连续点， 并将搜索结果作为潜在边缘的点集。 ４） 判断点集是否满足控制条件， 若满足转入下一步， 否则转入步骤（ ３） 。 （ （ ５） 将符合条件的点集进行坐标归一化处理。 （ ６） 利用最小二乘算法对归一化后的坐标点进行椭圆拟合。 （ ７） 判断拟合结果是否满足精度要求， 满足， 转入下一步， 否则转入步骤（ ３） 。 （ ８） 对拟合结果进行反归一化处理， 对椭圆参数进行求解。 本算法旨在检测并拟合输入图像中所有满足控制条件的椭圆。其核心 思想 是在 ｃａｎｎｙ 边缘检 测的 基础上， 增加控制条件进行判断， 将符合要求的准椭圆 转换到归一 化坐 标 系， 再利用传统的最小二乘算 法进行拟合。其流程图如图 １ 所示。 本文采用两种 控 制 条 件： 椭圆周长 ｎ Ｍａｘ ： 椭 圆 最 大 周 长； ｎ Ｍｉｎ ： 椭圆 的范 围 （ 最小周长） 和在归一 化 坐 标 系 下 的 拟 合 度（ ｔｈ ＿ ＧＯＦ ： 观测值到拟合曲线的均方 根误差阈值） 。更改 控 制 条 件 可 以 选 择 输入图像中不同的椭圆。 由于采用了归 一 化 的 方 法， 本算法 较传统的拟合方法有着独特的优势： （ １） 将不同位置不同尺 度下的 椭圆 都转换到归一 化 坐 标 系 下 进 行 拟 合， 相 比于不 归 一 化， 其 数 值 计 算 更 加 稳 定， 且所有 椭 圆 可 在 同 一 尺 度 下 进 行 拟 合 度的比较。 （ ２） 采用二次曲线拟合点集求解亚像素级的椭圆几何中心， 比灰 度重 心法、 高斯 曲面 拟合法 等 方法 更准确。 ３） Ｈｏｕｇｈ 变换检测椭圆法需要对图像中任意一对边缘点确定其是否为椭圆的最远点， 需要占用大 （ 量的空间， 且非常慢， 因而很少用于实际检测中。本算 法以连续 点集为 考察 对象， 相 比 于 Ｈｏｕｇｈ 变 换 法 计算速度更快捷， 因此， 具有较强的实用性。
第 ３５ 卷 第 ３ 期 ２０ １４ 年 ６ 月
河 南 科 技 大 学 学 报 ：自 然 科 学 版 Ｊｏｕｒｎａｌ ｏｆ Ｈｅｎａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ： Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ
Ｖｏｌ． ３５ Ｊｕｎ．
Ｎｏபைடு நூலகம் ３ ２０ １４
文章编号： １６７２ － ６８７ １ （ ２０ １４ ） ０３ － ００ １ ８ － ０４
最小二乘改进算法及其在椭圆拟合中的应用
马向南， 李 航， 刘丽丽， 刘志伟
（ 河南科技大学 机电工程学院， 河南 洛阳 ４７ １００３ ） 摘要： 提出一种像素级边缘检测椭圆拟合新算法， 用该算法对最小二乘算法进行了改进。首先， 将符合要求 的 准椭圆转化到归一化坐标系； 然后利用最小二乘法进行亚像素级椭圆拟合； 最后， 采用二次曲线拟合点集求 解 出亚像素及椭圆几何中心。在给定的图形中， 利用本文提出的改进像素级边缘检测算法可以明显提高拟合 不 确定度和拟合精度。 关键词： 最小二乘法； 边缘检测； 椭圆拟合； 亚像素 中图分类号： ＴＰ３９ １ 文献标志码： Ａ
８］ 。 因 此， 本文对 不足， 但是由于目标函数的表达非 常 复 杂， 所 以 求 解 过 程 工 作 量 很 大， 而且不易实现［
代数拟合法进行了改进， 旨在解决代数拟合中各参数贡献不同的问题， 弥补传统的最小二乘拟合在本文
基金项目： 河南省基础与前沿技术研究计划重大基金项目（ ０８２３００４ １ ３２０４ ） 作者简介： 马向南（ １９８６ －） ， 男， 河南周口人， 硕士生； 李 航（ １９６４ －） ， 男， 河南洛阳人， 教授， 博士， 硕士生导师， 主要研究方向为数 控机床精度检测和误差补偿、 移动机器人运动控制技术 ． 收稿日期： ２０ １ ３ － ０９ －１５
图 １ 算法流程图
２ 实验结果及分析
２． １ 求解结果 本文提出的算法采用 Ｍａｔｌａｂ 得以实现， 实验结果是在一台安 装有 Ｍａｔｌａｂ ７ ． ０ 的机器上 运行 的。由 于一般的图片很大， Ｍａｔｌａｂ 程序遍历图像搜索椭圆耗 时 较 长， 为 提 高 图 像 的 检 测 效 率， 在算法开始前对 图像进行预处理。方法为提取感兴趣区域， 只在该区域 检测 椭圆， 因 此 提 高 了 检 测 的 目 标 性， 从而提升 了检测速度。 首先对边缘进行检测， 然后需要对准椭圆点进行归一化处理： Ａｂａｒ ＝［ Ａ（ ： ， １ ）－ｄＣｅｎｔｅｒＸＡ （ ： ， ２ ）－ｄＣｅｎｔｅｒＹ ］ ；
不确定度这一概念通常用来表述由于测量误差存在 而对测 量值不 能 肯 定 的 程 度， 同时也可以用于 表述可信赖度， 它可以作为拟合准确度的一个评价指标。不确定度愈小， 说明拟合结果具有越高的可信 赖度， 拟合精度也就越高。随着不确定度的数值变得越 大， 测 量结果 的 可 信 赖 度 也 随 之 降 低， 相应的拟 合精度也就越低。不确定度可以广泛应用于直线、 圆及椭圆拟合结果的评价中 ［１ ０ －１ ２ ］。本文引入了 不确 定度的概念作为拟合精度的评价指标。一方面利用这 一概念可以 方便 将 可 信 赖 度 量 化； 另一方面也方 便了不同方法之间的可对比性。 经过计算， 含归一化的最小二乘拟合算法对本 文中给定的二值图拟合的不确定度的大小如图 ２ 所 示。图 ２ 中， 横 坐 标 表 示 了 点 的 编 号， 在这里共选 取了 ８２ 个点。纵坐标 表 示 了 产 生 的 不 确 定 度 的 大 小， 其 含义 为观测点 与拟合 出 的椭圆 边界的 几何 距 离， 当点位于拟合椭 圆 之 内 时， 距 离 为 负； 而当点位 于拟合椭圆以外时， 则距离为正。 ２． ２ 实验对比 为进一步 评 估 归 一 化 引 入 最 小 二 乘 拟 合 算 法 后的优 越 性， 本文采 用传统 最 小二乘 法在同 样 的条 件下进 行 边 界提取和最 小二乘拟 合， 利用 同 样的 方
表 １ 含归一化过程的最小二乘算法拟合结果 ＩＤ １ ２ ３ ４ ｏｘ ２ ２ ２ ２ ４６ １ ． ８３７ ２３０． ８３７ ５３６ ． ８３７ ３０７ ． ８３７ ６４９ ６４９ ６４９ ６４９ ｏｙ ６４５ ６６７ １ ４６４ １ ４８４ ａ １４． ２３８ ８８ １ １４． ２３８ ８８ １ １４． ２３８ ８８ １ １４． ２３８ ８８ １ ７６ ７６ ７６ ７６ ｂ １４． ２３６ ７０３ １４． ２３６ ７０３ １４． ２３６ ７０３ １４． ２３６ ７０３ ９６ ９６ ９６ ９６ １． ５７０ １． ５７０ １． ５７０ １． ５７０ θ ７９６ ７９６ ７９６ ７９６ ３２７ ３２７ ３２７ ３２７
４ －６ ］ ８ －９ ］ Ｈｏｕｇｈ 变换 ［ 以及 Ｋａｌｍａｎ 滤波 法 ［ 。 Ｈｏｕｇｈ 变换 目前， 常用的拟合方法有最小二乘拟合 ［１ －３ ］、
是把离散的边缘点连接成直线或闭 合 曲 线 常 用 的 算 法。 其 原 理 是 利 用 图 像 空 间 与 参 数 空 间 的 对 应 关 系， 将图像空间像素点利用某一解析形式转化到参数空间， 通过在参数空间进行简单的累加统计来完成 因 为参数 过多会 大 大 增 加 算 法 检测任务， 一般而言， 使用 Ｈｏｕｇｈ 变换进行检测只限于两个参数 的情 况， 是一种经典的最 优滤波。 该方 法通 过状态 转 移方 的耗时和空间复杂度。 Ｋａｌｍａｎ 滤波常用在控制论中， 程对状态进行预测， 再结合观测值对预测进行修正， 通 过这样的不 断更 新 修 正 进 行 状 态 的 估 计， 最终形 成拟合后的椭圆。然而这种方法却容易受到噪声和孤立点的影响， 最终导致结果不准确。 最小二乘拟合是最早的椭圆拟合方法， 它是数据拟合中的基本方法， 其思想为考虑数据受随机噪声 的影响进而追求整体误差的最小化。这种方法最为直 观、 简 单、 同时 比 较 实 用， 因此是拟合当中最常用 的方法。最小二乘法的做法是在假设测量点产生的随机误差为正 态分 布 的 前 提 下， 采用最大似然估计 方法推出的一个最优估计解的方法， 这种方法的约 束条件 是使误差的 平 方 和 达 到 最 小。由 于 误 差 的 大 小可以直接反映出拟合过程的可信赖度， 因此这种 方法常 被认为是最 可 信 赖 的 方 法 之 一。最 小 二 乘 技 术主要是寻找参数集合， 从而最小化数据点与椭圆 之间的 距离度量。这 里 的 距 离 度 量 常 见 的 有 几 何 距
９］ 离和代数距离 ［ 。最小二乘拟合有两类求解办法， 代数拟合法和几何拟合法。
首先， 求解最小值的式子在几何变换下是变化的； 另外， 代数拟 合 没 有 考 虑 在 椭 圆 上 不 同 位 置 的 点 对椭圆方程参数估计的影响， 使用这种方法可能使拟合出 的椭圆产生 偏 差。 几 何 拟 合 法 可 以 弥 补 这 些