一种基于快速搜索圆心的圆度新算法

盛东良， 詹剑良， 朱 丹

(绍兴职业技术学院 机电工程与交通学院，浙江 绍兴 312000)

1 引 言

根据ISO 1101-1983[1],圆度定义为：包围所有数据点的两个同心圆之间的最小径向间距。最小区域标准的目标是找到一对包含所有数据点且径向偏差最小的同心圆。圆度评估是一个非线性问题，为了获得最小区域的解决方案，相关学者已对评估算法作了许多研究。这些算法须具有高效、稳健的特点，并通过减时来生成结果。

最小二乘拟合技术是圆度评估的常用方法，以找到合适的圆心位置为最小化目标函数值，该目标函数值是来自拟合圆的数据点的平方误差的总和。最小二乘技术在计算中很有效，是坐标测量机(CMM)的早期模型中可用的方法[2]。但是，获得的圆度的值被夸大了约10%，这在公差不断减小的情况下，是不能接受的。

Murthy T S R等[3,4]提出了一种二维单纯形搜索方法来解决圆度问题。单纯形搜索技术高效且易于编码，但是不能保证全局性的最小解决方案，例如圆度问题。Yeralan S和Ventura J A等[5,6]提出了一种寻找圆心和半径的方法，可以最大程度地减少数据点和圆之间的最大垂直距离，该方法的复杂度较高，并且使用启发式算法来改进计算。Lai K等[7]提出了一种计算几何技术来解决圆度问题，但该解决方案没有找到最小的径向间隔。Le V B等[8]也曾阐述过类似的方法。

Huang J[9]改进了一种基于Voronoi图的新方法，该方法表明最小的径向分离圆心只能在X型顶点上获得，顶点由4个关键数据点确定。此方法的缺点是需要大量的计算，尤其是在数据点数量很大时，文献[10]中Huang J进一步提出了一种新的计算策略，目标是尽早隔离关键数据点，以便减少冗余数据点的计算。

国内很多学者从不同角度对圆度误差的最小区域评定算法进行了大量的研究，提出了很多评定圆度误差的优化算法，比较有代表性的算法有：仿增量算法[11]，搜索算法[12～14]、计算几何算法[15]及一些其他算法[16,17]等，这些算法均具有一定的实用价值，但大都较复杂，实际应用较难。

本文提出了一种基于搜索理想圆心的新算法，以期解决圆度问题。该算法的目的是找到理想的圆心，以及距离该圆心最远和最近的点。对于每次迭代，根据距上一个圆心的最远和最近的点来搜索下一个圆心。

2 几何特性及数学模型

2.1 几何特性

令S={Pi|i=1,2,…,n}是数据点集，其中Pi表示第i个数据点。圆度的目标函数是两个同心圆之间的径向差，集合S的所有数据点必须位于其中。圆度评估的目标区域是两个同心圆之间的圆形区域，见图1。

图1 两个同心圆之间的区域Fig.1 The area between two concentric circles

最小区域是目标函数值最小的目标区域。故圆度是从最小区域获得的最小目标值，一旦获得相应的圆心，就可以轻松评估圆度的目标函数。因此，计算效率取决于确定理想圆心的速度。为了找到理想圆心的有效算法，需要建立一系列数学模型。

2.2 数学模型

令(x1,y1),(x2,y2),…，(xi,yi),…，(xn,yn)表示xy平面中被测圆的n个点的x和y坐标。必须找到理想圆的圆心(x0,y0)，见图2。

图2 圆度Fig.2 Roundness

第i个点(xi,yi)相对于理想圆心的半径为

(1)

将这些半径值中的最大值表示为rmax，将最小值表示为rmin，圆度h为

h=rmax-rmin

(2)

根据最小区域准则，目标是确定圆心(x0,y0)，使h为最小值。然后，可以建立用于确定最小区域圆心以及评估圆度hmin的数学模型为

hmin=min{h}=min{rmax-rmin}

=min{rmax}-max{rmin}

(3)

为了使圆度最小，根据距离上一个圆心的最远的点(xmax,ymax)和最近的点(xmin,ymin)更新圆心。即：沿着外部等分线l移动圆心，以便最小化rmax和最大化rmin，见图3。

图3 更新圆心Fig.3 Update center

更新圆心的计算如下：

(4)

(5)

(6)

3 算法流程

本文提出了一种新的快速搜索圆心方法，更有效地解决圆度问题。该算法的本质是不断更新每次迭代确定的圆心，直到误差符合要求。其优点在于：在圆度计算中，只需要搜索理想的圆心即可，因此计算容易编码，并且可以在很短的时间内获得足够的精度，计算流程如图4所示。算法的关键步骤如下：

(1) 用最小二乘法确定给定点的近似圆心。

(2) 计算半径ri，它是第i个点到圆心的距离。拾取最远和最近的点。根据式(4)计算方向矢量。

(3) 更新圆心，然后重复步骤2，直到计算圆度比上一个圆度值大，即前后圆度之差小于0。

(4) 输出前圆度，即为最终评定结果。

图4 算法流程Fig.4 Algorithm flow

4 验证与讨论

基于所提出的算法解决圆度问题的示例见表1，此示例中采用文献[12]给出的被测实际圆的测量数据，表中列出了50个数据点的坐标。

表1中的该组数据是在Global FX777型三坐标测量机上，对φ=63.5 mm的圆孔进行实测获得的，50个数据点的坐标如图5所示。

图5 数据点Fig.5 Data point

根据提出的算法，首先，通过最小二乘技术确定近似圆心。使用这些测量数据点和近似圆心，可以创建以一对同心圆为边界的最小区域，见图6。最小区域的外接圆和内切圆分别由圆心点O，最远的数据点3和最近的数据点4构成。显然最小区域的值不是最小，因此，必须更新圆心直至满足最小区域标准。即：沿着方向矢量l移动圆心，该方向矢量是线和线之间的等分线，步长为λ。然后，对圆心重复相同的计算，直到计算圆度大于前圆度。前圆度即为最终圆度评定结果。

图6 最小区域Fig.6 Smallest area

从表2计算结果比对可以看出，本文方法时间仅需0.025 823 s，满足最小区域标准。计算得到圆度为0.0106 mm，圆心坐标为(267.649 3,12.130 4)。最小二乘法可以快速解决圆度问题，而区域搜索法[12]需要很长时间才能获得最准确的结果，两者差异明显。本文提出的算法所需时间比区域搜索法要少得多，而两者计算得到圆度差值仅为0.000 7 mm，显示了提高算法的效率，具有较高的准确性，可以满足工程要求。

表2 计算结果比对Tab.2 Calculation result comparison

结果验证了所提出算法，通过不断更新圆心的方案，结合计算模型，缩短了计算时间，从而高效地解决了圆度问题。该策略未包括在每次计算迭代时确定最佳步长λ和方向矢量l这些参数。若在计算过程中能更好地确定这些参数，则可更大程度地简化问题，节省更多的计算时间。但是，这些参数的确定仍然受到限制，需要做进一步的研究方可有利于消除这些限制。

5 结 论

本文提出了一种基于快速搜索圆心的圆度新算法，建立一系列理论模型，通过不断更新圆心，使距离圆心的最远点和最近点找到移动圆心的方向，再通过式(5)和式(6)计算下一个圆心，当计算得到的圆度大于上一个圆度时，停止迭代。实验结果表明该圆度算法符合最小区域标准，可以有效地在较短时间内获得足够准确的计算结果。与区域搜索法相比，该算法的计算误差<1 μm，计算效率可提高10倍以上 ，在工程应用中有较好的实用价值。