直线度误差测量—翻译

1、 直线度误差测量 一种为了估计直线度最小误差区域快速而简单算法来自坐标抽摘要：过去已经有各种各样的方法来判定最小区域直线度误差，但是这些方法都有它们各自的缺点。一种来自平面坐标抽的新的，快速，简单的算法被提出来计算直线度误差。它确保了最小区域的解决方法。一个例子和实验数据可以证明。模拟实验的结果使计算这个算法的时间复杂度得以确定也可以显示它的优点。关键词：坐标测量机（CMM） 算法 直线度误差一·介绍 在工业能力观中通过坐标测量机来估计各种产品的性能已经是非常的广泛和受欢迎了。在许多情况被探索之后，直线度是一个典型的特征。例如：机床的分层，游标卡尺的梁。当用坐标测量机来判定直线度误差

2、时，坐标测量机主要是获得了工作空间的坐标。在那之后，这些坐标用软件设备分析出来得到测量结果。本文介绍了一种新的从二维坐标数据判定直线度误差的方法。 根据IOS（一种绘图操作系统），“当来自一个理想的几何形式的附加面一个单独的坐标的距离等于或小于这个特定的公差的值的时候，一个单独的公差特征的直线度被认为是正确的。这个理想直线的方向将会被选择是因为它是最大距离与这个被考虑的特征点的真实表面之间最小的可能值。”因此直线度误差是把真实表面围起来的两条平行线之间的最短距离，也可以称为最小区域的直线度误差。然而判定参考线的正确性的不仅仅是算数计算那么简单，许多测量坐标机的开发者运用各种近似值，但是在政府工

3、业数据变换计划警报后他们就变的谨慎了。 在过去为了判定最小区域直线度误差各种各样的办法都已经被提出过了。Murthy and Abdin讨论运用各种方法从最小平方和普通最小平方开始单纯性搜索法和螺旋性搜索法技术。Dhanish and Shunmugam运用线性，非连续的切比雪夫逼近的理论从格式数据方面来判定直线度误差，在这里参考线是用来和测量线排列成一线的，而不是为了坐标数据运用的。Carr and Ferreira用了国际商业机器公司（IBM）的软件包库来获得最小区域的解决方法。Cheraghi等人开发了一般线性程序以一种特殊的搜索方法来判定最小区域直线度。首先凸形构造被确定，然后双点的对

4、应点也就被确认了。所有的距离被估算出来后，最小值就作为直线度误差。Orady等人用单纯搜索法来计算最小区域直线度误差。Chen and Fan用了微软Excle中广义约化梯度法来判定直线度误差。Huang提出了一个基于凸出点的测定上的方法。他有着准确的判定那就是三个点足够确定最小区域度误差，但是提出的这个方案中没有一个方法可以删除已经加入的点。他已经表明在一个定义的点集中有六到七个点剩余，那就意味着最佳的解决方法还没有被找到。举一个可以得出计算结果的例子，凸出的点是11, 64, 47,67, 33, 86和89，得出最佳解的点应该是被单独定义的点47,67,89。 大多数上述所提到的方法中都

5、是有针对性的解决问题，这些算法都尽可能的快确不能利用到数据本身的特性。例如启发式法中的模拟退火法，遗传算法和神经网络法都很快，但是都不能保证得到最佳解。Liu等人采用了一种将遗传算法和几何特性相混合的方法。然而，更好和更快的算法是永远的利益。在这篇文章当中，一种新的算法被提出，这种算法的每一步以一种非常简单的形式呈现，是的任何一个用户觉得这种算法易于编程。 实验与模拟数据相较于该算法的执行时间和冒泡排序，堆排序这两种排序算法都展现出来了。二·问题的数学定义 用(x1, y1),(x2, y2),.,(xi, yi),.,(xn,yn)来代表该测量线上的n个点在xy平面内的x,y坐标。

6、我们的目标是找出理想直线的斜率l0和截距y0，这条直线上的点是给出的最适合的点。至于这条理想直线的误差点(xi, yi)已经被给ei=yi-(yo+loxo)1+lo²。我们用emax来指代误差值中的最大值，用emin来指代误差值中的最小值。然后，直线度误差h就可以用h = emaxemin来计算。根据最小区域准则，当h最小化时我们的目标值由l0 和y0来判定。图一 ·直线度误差的定义三·算法 该算法的大致过程如下：在第一步和第二步中，我们根据数据确定一条近似线然后旋转坐标轴是x轴沿着数据点。至于这条线，我们先忽略直线度偏离的非直线性，在第三步到第十四步中判定最小

7、区域直线。在这之后的第十五步中，我们检查是否是非直线性，如果是，我们就相应地旋转数据点。我们不断重复直到旋转的x轴与确定的最小区域线之间的角变得很微小。一旦这些都完成了，我们就在原坐标系中确定了这条线的参数（第十六步）和直线度误差（第十七步）。 第一步：确定数据集合中两个最远的点（见图二2a）。如果两个点是从一个点的终点到另一个点的终点测量的，那么这两个点很容易确定。否则，我们可以利用这些点都几乎沿着一条直线这个依据，得出最大和最小x坐标的点可以被确认为最远的点。确定由这两个点确定的这个状态的直线与x轴之间的夹角。如果这个角大于45°，我们可以交换x轴和y轴的坐标，然后进行下一步。

8、第二步：根据这个来旋转坐标轴形成一个新的x轴，这个x轴平行于这条状态线。（见图二2b）。这样，我们获得了n对点，如：(xi, yi)xi= xi, cos+ yisin,和yi= - xisin + yi cos. 第三步：选一组三个点作为初始参考集（见图二 2c）。选出的这三个点最终是不是算法所汇聚的三个点没有关系。用(u1, 1), (u2, 2), (u3, 3)来指代选出的这三个点，其中u，v与x,y相一致。 第四步：算出1,2 和3，它们的计算公式已经给出1 = u3 -u2; 2 =u1 -u3; 3 = u2 -u1。第五步：计算标准偏差d, 它的计算方式如下：d=11+22+3

9、3 -|1|+|2|+|3|第六步：找到p1,p2和p3距离的值，使得这些距离值与经过参考集的这条线等同，如下：p1=1+（sgn(1)）dp2=2+（sgn(2)dp3=3+（sgn(3)）d这里sgn(k)表示。第七步：用过下面两个方程式解出yo,xo，找出与它们相等的参考线。p1= yo+ xou1p2= yo+ xou2p3= yo+ xou3这里的y截距和斜率是从坐标系中译处来的。 第八步：在已获得的等同了的参考线中所有已翻译的n个点中找到所谓的误差点ei=yi-(yo+xoxi) 第九步：找出ei绝对值中的最高值，这就是我们所说的最大误差值e*。 第十步：比较|e*|和|d|如果|

10、e*|d|，则在等同的参考线附近就是最小区域直线转换的坐标。这就是我们所要的最佳化准则。调到15步检查第一步选出的斜率是否完全正确。如果|e*|>|d|，则这个点i*就是相应的最大误差。xi,yi也可以被考虑在参考集当中。（见图二，2e）找到被丢弃的点，进入第十一步。 第十一步：我们利用Stiefel提出的方法被删除的点。在下面方程式中解出m1,m2和m3：m1+m2+m3+1=0m1u1+m2u2+m3u3+xi=0因为这里有两个方程式，而有三个未知量。假设出其中的一个ms的一个合适的值m3=1，然后解出剩下的值。 第十二步：计算出下面q1,q2和q3的比值：q1=m1/1,q2=m2

11、/2,q3=m2/3 第十三步：检查sgn(d)e*。如果它比0大，则这个点的最小值为q应该从参考集中被删除，否则，这个点的最大值应该被删除。（见图二2f） 第十四步：形成一个新的参考集，里面包括误差最大的点，但不包括在十二步中确定的最大值或最小值的点。我们把这些点再次用(u1, 1), (u2, 2), (u3, 3)来指代，这里u，v还是代表x,y，从第四步开始重复，直到达到第十步最佳的准则就确定了。 第十五步：检查旋转过的坐标系中的斜率是否足够小（见图二2g），如果是，我们停止重复，调到十六步在原始坐标系中找到截距和斜率。否则我们必须旋转原始坐标轴使得x轴与在第二步中已获得的等价参考线相

12、平行。但是这里要用+1/tanlo。 第十六步：原始坐标系中的最小区域线的斜率和y轴截距已经给出，这是最佳的求解方式：yo=yo/(cos losin)lo=(lo+tan)/(l-lotan)第十七步：在原始坐标系中所获得的线的点的误差可以用公式ei=(yi-yo-loxi)/ 1+lo²计算。这些误差值中的最小值和最大值用emin和emax来表示。则最小区域直线度误差h可以用公式h=emax-emin来计算。图二 算法计算当中几个重要的步骤。四·实例让我们现在将这种算法应用到数据集当中。表1中给出x,y轴坐标，计算得出结果。第一步：很明显，点3和8是最远的点。连接这两个

13、点的形成的直线与原来的x轴构成一个角= 0.52509°。第二步：根据这个旋转坐标轴使新的x轴平行于重点线，我们就得到了如表格中4和5栏中新的x,y坐标。第三步：我们选择数据集中的1,2,3点作为参考集中最初的点。与表3栏3中一致的u,v值就出现了。第四步：现在1=u3-u2= 12.3101 -50.2375 =-37.92742=u1-u3 =58.2937 12.3101 =45.98363=u2-u1= 50.2375 59.2937 =-8.0562第五步：参考值偏差d=-0.76274第六步：平行参考线应该经过这些点p1=1+（sgn(1)）d= 1.6978p2=2+（

14、sgn(2)d= 1.7239p3=3+（sgn(3)）d= 1.8467第七步：解出下面任意两个方程：1.6978=yo+lo*58.29371.7239= yo+ lo*50.23751.8467= yo+ lo*12.3101这样我们就得到了yo= 1.88655，lo=- 0.00323819。第八步：在点1旋转过的坐标系的误差已经给出e1= -0.76274，相似地，表3第二栏中给出的其他点的误差也可以计算出。第九步：ei绝对值最高的是点12的2.44625，因此这是我们的最大误差e*。第十步：因为|e*|>|d|，最佳值的情况不满足；我们需要参考集中的点i*=12的x轴xi=

15、71.1054 yi=-0.78995，确定这个点被排除，我们进入下一步。第十一步：我们需要解下面的方程式：m1+m2+m3+1=0m1* 58.2937+m2 *50.2375+m3* 12.3101=0，选m3=1然后解出，我们得到m1= 2.1176 m2=- 4.176 第十二步：算出q1的值，我们找出q1=m1/1=-0.0558,q2=-0.0895和q3=-1241。 第十三步：因为sgn(d)=(-)-2.44625，点1的最小值qi,所以这个点应该从参考集中删除。 第十四步：用过删除点1和添加点12形成新的参考集。重复步骤4到7.我们获得了表4的结果。进行到8至13步，我们发

16、现点12被删除点7加入了。表4第三栏中的结果就得出了。在下一个参考集中，点10代替点3包含进来.在实验4中，第十步的时候我们获得了最佳准则的值，即e*=|d|。第十五步：旋转坐标系的斜率是-0.031045，如果这个值相较于所要求的不够小。我们必须再次旋转原始坐标轴，因此，我们要根据角-0.556135，结果如表5所示。然后重复所有的步骤，在4次实验后，我们最终得到e*=1.52671，中间结果在表6。第十六步：原始坐标系中的y截距和斜率分别是yo=2.96430，lo=-0.621565第十七步：在原始坐标系中已获得的直线的误差ei=0.225871。相似地，其他点的误差也可以计算出，在表7

17、中给出。如果旋转的坐标系可以和原始的这条直线形成一条直线，然后这些计算出的误差将不同于在最后一次实验中用十五步得出的误差，这个误差值最高的是emax= 1.52671，最低的是emin=- 1.52671 ，因此直线度误=3.05342。五·计算的复杂性当然有很多算法解决这个问题，我们需要一些标准来决定哪一个是最好的算法。最常用的标准是比较算法解决问题的时间，这就是大家都知道的时间算法的复杂性。这个问题提出解的绝对时间是靠程序在电脑上运行的速度，可用内存，操作系统，编程效率编译器的质量等来决定的。因此作为一个性能的展示是没有用。如果我们考虑一个简单的程序为了在一个n个元素的列表中寻找

18、一个元素。最坏的办法可能就是比较这n个元素。我们说最坏的时间计算复杂度是n个元素的排序，用O（n）算法指出。平均起来，比较的次数应该是n/2。因此差不多与n相同的顺序，我们说这个算法的平均复杂度也是O（n）。一个决定复杂度的简单的方法是计算可执行算法所要求的步骤数，以最基本的操作而言，输入规模是一个功能。然而，在这个例子中如果操作数不能提前预测，这个算法是不灵活的。所以我们必须要采取实验方法。为了估计这个算法的时间计算复杂度，一个全因实验和两个复制计算出来，它的执行数1250，选择因素和水平在表8中给出。数据集通过生产对称分布形式的误差和加入的一条均匀随机分布截距和斜率的直线。这个提出的算法是用C+编译的，是在一个附带内存192MB和Windows 2000的操作系统的Pentium 600 PC上运行的。这个程序员用的是the gcc Mingw32 2.95.2 C/C+。解决这个问题的所花费的时间是由利用the A_TickCount开放式脚本源参数Auto