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

马向南，李 航，刘丽丽，刘志伟

（河南科技大学机电工程学院，河南洛阳471003）

0 引言

视觉测量系统中，边缘检测提取的准确性直接影响了最终测量的精度。边缘检测的过程是使用数学方法提取图像像元中具有亮度值（灰度）空间方向梯度大的边、线特征的过程。边缘检测和边缘提取是图像处理和计算机视觉中的基本问题，其目的在于将数字图像中亮度变化明显的点标识出来。图像属性中的显著变化通常反映了属性的重要事件和变化。在边缘检测技术中常用的一种方法就是对提取的轮廓边缘进行拟合。椭圆拟合在数字图像处理、计算机视觉和模式识别中有着很重要的地位，但是由于在很多实际图像中不仅存在噪声，还存在一些难以剔除的孤立点，因此，找到一种稳健、有效、易用的椭圆拟合方法一直很难。

目前，常用的拟合方法有最小二乘拟合［1－3］、Hough变换［4－6］以及Kalman滤波法［8－9］。Hough变换是把离散的边缘点连接成直线或闭合曲线常用的算法。其原理是利用图像空间与参数空间的对应关系，将图像空间像素点利用某一解析形式转化到参数空间，通过在参数空间进行简单的累加统计来完成检测任务，一般而言，使用Hough变换进行检测只限于两个参数的情况，因为参数过多会大大增加算法的耗时和空间复杂度。Kalman滤波常用在控制论中，是一种经典的最优滤波。该方法通过状态转移方程对状态进行预测，再结合观测值对预测进行修正，通过这样的不断更新修正进行状态的估计，最终形成拟合后的椭圆。然而这种方法却容易受到噪声和孤立点的影响，最终导致结果不准确。

最小二乘拟合是最早的椭圆拟合方法，它是数据拟合中的基本方法，其思想为考虑数据受随机噪声的影响进而追求整体误差的最小化。这种方法最为直观、简单、同时比较实用，因此是拟合当中最常用的方法。最小二乘法的做法是在假设测量点产生的随机误差为正态分布的前提下，采用最大似然估计方法推出的一个最优估计解的方法，这种方法的约束条件是使误差的平方和达到最小。由于误差的大小可以直接反映出拟合过程的可信赖度，因此这种方法常被认为是最可信赖的方法之一。最小二乘技术主要是寻找参数集合，从而最小化数据点与椭圆之间的距离度量。这里的距离度量常见的有几何距离和代数距离［9］。最小二乘拟合有两类求解办法，代数拟合法和几何拟合法。

首先，求解最小值的式子在几何变换下是变化的；另外，代数拟合没有考虑在椭圆上不同位置的点对椭圆方程参数估计的影响，使用这种方法可能使拟合出的椭圆产生偏差。几何拟合法可以弥补这些不足，但是由于目标函数的表达非常复杂，所以求解过程工作量很大，而且不易实现［8］。因此，本文对代数拟合法进行了改进，旨在解决代数拟合中各参数贡献不同的问题，弥补传统的最小二乘拟合在本文所给出的图像中进行拟合时的不足。

1 引入归一化的最小二乘拟合算法

归一化是一种简化计算法，即将有量纲的表达式经过变换，化为无量纲的表达式，成为纯量。将这种方法应用于椭圆拟合中，可以弱化椭圆上位置不同的点对椭圆方程参数估计贡献的差别，减小拟合出的椭圆产生偏差的可能性。因此，本文将归一化方法应用到了椭圆的最小二乘拟合中。该算法步骤为：

（1）将要处理的图像调入系统。

（2）用canddy算法对图像进行边缘检测。

（3）搜索连续点，并将搜索结果作为潜在边缘的点集。

（4）判断点集是否满足控制条件，若满足转入下一步，否则转入步骤（3）。

（5）将符合条件的点集进行坐标归一化处理。

（6）利用最小二乘算法对归一化后的坐标点进行椭圆拟合。

（7）判断拟合结果是否满足精度要求，满足，转入下一步，否则转入步骤（3）。

（8）对拟合结果进行反归一化处理，对椭圆参数进行求解。

本算法旨在检测并拟合输入图像中所有满足控制条件的椭圆。其核心思想是在canny边缘检测的基础上，增加控制条件进行判断，将符合要求的准椭圆转换到归一化坐标系，再利用传统的最小二乘算法进行拟合。其流程图如图1所示。

本文采用两种控制条件：椭圆周长的范围（nMax：椭圆最大周长；nMin：椭圆最小周长）和在归一化坐标系下的拟合度（th_GOF：观测值到拟合曲线的均方根误差阈值）。更改控制条件可以选择输入图像中不同的椭圆。

由于采用了归一化的方法，本算法较传统的拟合方法有着独特的优势：

（1）将不同位置不同尺度下的椭圆都转换到归一化坐标系下进行拟合，相比于不归一化，其数值计算更加稳定，且所有椭圆可在同一尺度下进行拟合度的比较。

图1 算法流程图

（2）采用二次曲线拟合点集求解亚像素级的椭圆几何中心，比灰度重心法、高斯曲面拟合法等方法更准确。

（3）Hough变换检测椭圆法需要对图像中任意一对边缘点确定其是否为椭圆的最远点，需要占用大量的空间，且非常慢，因而很少用于实际检测中。本算法以连续点集为考察对象，相比于Hough变换法计算速度更快捷，因此，具有较强的实用性。

2 实验结果及分析

2.1 求解结果

本文提出的算法采用Matlab得以实现，实验结果是在一台安装有Matlab 7.0的机器上运行的。由于一般的图片很大，Matlab程序遍历图像搜索椭圆耗时较长，为提高图像的检测效率，在算法开始前对图像进行预处理。方法为提取感兴趣区域，只在该区域检测椭圆，因此提高了检测的目标性，从而提升了检测速度。

首先对边缘进行检测，然后需要对准椭圆点进行归一化处理：

经过本算法处理后，可以得到由一系列连续的点组成一个椭圆。对参数进行反归一化处理后可以得到各参数在绝对坐标系中的坐标值。

根据拟合出的方程的参数可以求得拟合椭圆的特征参数，如表1所示。

表1 含归一化过程的最小二乘算法拟合结果

不确定度这一概念通常用来表述由于测量误差存在而对测量值不能肯定的程度，同时也可以用于表述可信赖度，它可以作为拟合准确度的一个评价指标。不确定度愈小，说明拟合结果具有越高的可信赖度，拟合精度也就越高。随着不确定度的数值变得越大，测量结果的可信赖度也随之降低，相应的拟合精度也就越低。不确定度可以广泛应用于直线、圆及椭圆拟合结果的评价中［10－12］。本文引入了不确定度的概念作为拟合精度的评价指标。一方面利用这一概念可以方便将可信赖度量化；另一方面也方便了不同方法之间的可对比性。

经过计算，含归一化的最小二乘拟合算法对本文中给定的二值图拟合的不确定度的大小如图2所示。图2中，横坐标表示了点的编号，在这里共选取了82个点。纵坐标表示了产生的不确定度的大小，其含义为观测点与拟合出的椭圆边界的几何距离，当点位于拟合椭圆之内时，距离为负；而当点位于拟合椭圆以外时，则距离为正。

图2 归一化最小二乘算法拟合结果的误差及标准差分布图

2.2 实验对比

为进一步评估归一化引入最小二乘拟合算法后的优越性，本文采用传统最小二乘法在同样的条件下进行边界提取和最小二乘拟合，利用同样的方法对拟合参数进行求解可以得到拟合椭圆的特征参数，如表2所示。

表2 最小二乘算法拟合结果

通过对比可以发现：两种方法在长短轴的差别较大，由于拟合偏差不太大，所以也用其拟合不确定度来评价，其不确定度大小如图3所示。图3中，横坐标表示点的编号，在这里共选取了82个点。纵坐标表示产生的不确定度的大小，其含义为观测点到拟合出的椭圆边界的几何距离，当点位于拟合椭圆之内时，距离为负；而当点位于拟合椭圆以外时，则距离为正。

图3 最小二乘算法拟合结果的误差及标准差分布图

通过图2和图3的对比可以看出：两种方法拟合出结果的不确定度走势相同，但大小上存在差异，改进后的最小二乘拟合在误差控制上的能力要优于传统的最小二乘拟合。因此，采用归一化后进行最小二乘拟合在工程中对图像数据进行拟合处理具有精度优势。由于采用了归一化处理，算法的鲁棒性同时得到了保证，经测试，在上文中给定的电脑配置上对给定的图像进行处理，程序的运行和处理时间能够控制在20 ms内，完全满足性能的需求，故该算法具有实际意义。

3 结束语

由于传统最小二乘法把所有样本点都近似为准确值，因此拟合出的椭圆误差比较大。为了提高椭圆拟合的精度，本文利用归一化处理对传统的最小二乘拟合算法进行了改进。经过两种方法对比，本文中的算法在求取最优椭圆的过程中能够将杂质点的影响降低，提高准确度的同时也增强了系统的鲁棒性。另外，不同点之间的贡献度也得到了体现，因此可以减小可能带来的偏差。本文当中的算法所需要的运行时间也较短，在样本点为200～600个时，运算时间能够控制在20 ms以内，因此完全能够满足实时系统要求。

［1］ 安新源，周宗潭，胡德文.椭圆拟合的非线性最小二乘方法［J］.计算机工程与应用，2009，45（18）：188－190.

［2］ 闫蓓，王斌，李媛.基于最小二乘法的椭圆拟合改进算法［J］.北京航空航天大学学报，2008（3）：295－298.

［3］ 吕洪赫，姚振杰，易卫东.基于对称性的最小二乘拟合随机椭圆检测算法［J］.电子测量技术，2011（5）：37－41.

［4］ 陈立，万鹏，何涛，等.基于Hough变换的亚像素椭圆检测［J］.湖北工业大学学报，2005（5）：132－134.

［5］ 程军涛，段明德，刘鑫，等.摩托车覆盖件的逆向设计［J］.河南科技大学学报：自然科学版，2009，30（5）：21－23.

［6］ 杨苏.基于局部分析的Hough变换形状检测关键技术研究［D］.秦皇岛：燕山大学，2009.

［7］ 夏菁.椭圆拟合方法的比较研究［D］.广州：暨南大学，2007.

［8］ 华瑞娟.多椭圆拟合的算法研究［D］.广州：暨南大学，2010.

［9］ 曹芳.计算机视觉中的各点异性回归技术［D］.上海：上海海事大学，2004.

［10］ 雷贤卿，李言，李济顺，等.截面最小二乘圆心位置的余弦回归提取法［J］.河南科技大学学报：自然科学版，2006，27（1）：13－17.

［11］ 来雪梅，王雪萍，张海燕.实验数据的拟合及其不确定度表示［J］.中北大学学报：自然科学版，2009（5）：481－484.

［12］ 倪骁骅.形状误差测量结果不确定度的研究及应用［D］.合肥：合肥工业大学，2002.