盛東良， 詹劍良， 朱 丹

(紹興職業(yè)技術學院 機電工程與交通學院，浙江 紹興 312000)

1 引 言

根據ISO 1101-1983[1],圓度定義為：包圍所有數據點的兩個同心圓之間的最小徑向間距。最小區(qū)域標準的目標是找到一對包含所有數據點且徑向偏差最小的同心圓。圓度評估是一個非線性問題，為了獲得最小區(qū)域的解決方案，相關學者已對評估算法作了許多研究。這些算法須具有高效、穩(wěn)健的特點，并通過減時來生成結果。

最小二乘擬合技術是圓度評估的常用方法，以找到合適的圓心位置為最小化目標函數值，該目標函數值是來自擬合圓的數據點的平方誤差的總和。最小二乘技術在計算中很有效，是坐標測量機(CMM)的早期模型中可用的方法[2]。但是，獲得的圓度的值被夸大了約10%，這在公差不斷減小的情況下，是不能接受的。

Murthy T S R等[3,4]提出了一種二維單純形搜索方法來解決圓度問題。單純形搜索技術高效且易于編碼，但是不能保證全局性的最小解決方案，例如圓度問題。Yeralan S和Ventura J A等[5,6]提出了一種尋找圓心和半徑的方法，可以最大程度地減少數據點和圓之間的最大垂直距離，該方法的復雜度較高，并且使用啟發(fā)式算法來改進計算。Lai K等[7]提出了一種計算幾何技術來解決圓度問題，但該解決方案沒有找到最小的徑向間隔。Le V B等[8]也曾闡述過類似的方法。

Huang J[9]改進了一種基于Voronoi圖的新方法，該方法表明最小的徑向分離圓心只能在X型頂點上獲得，頂點由4個關鍵數據點確定。此方法的缺點是需要大量的計算，尤其是在數據點數量很大時，文獻[10]中Huang J進一步提出了一種新的計算策略，目標是盡早隔離關鍵數據點，以便減少冗余數據點的計算。

國內很多學者從不同角度對圓度誤差的最小區(qū)域評定算法進行了大量的研究，提出了很多評定圓度誤差的優(yōu)化算法，比較有代表性的算法有：仿增量算法[11]，搜索算法[12～14]、計算幾何算法[15]及一些其他算法[16,17]等，這些算法均具有一定的實用價值，但大都較復雜，實際應用較難。

本文提出了一種基于搜索理想圓心的新算法，以期解決圓度問題。該算法的目的是找到理想的圓心，以及距離該圓心最遠和最近的點。對于每次迭代，根據距上一個圓心的最遠和最近的點來搜索下一個圓心。

2 幾何特性及數學模型

2.1 幾何特性

令S={Pi|i=1,2,…,n}是數據點集，其中Pi表示第i個數據點。圓度的目標函數是兩個同心圓之間的徑向差，集合S的所有數據點必須位于其中。圓度評估的目標區(qū)域是兩個同心圓之間的圓形區(qū)域，見圖1。

圖1 兩個同心圓之間的區(qū)域Fig.1 The area between two concentric circles

最小區(qū)域是目標函數值最小的目標區(qū)域。故圓度是從最小區(qū)域獲得的最小目標值，一旦獲得相應的圓心，就可以輕松評估圓度的目標函數。因此，計算效率取決于確定理想圓心的速度。為了找到理想圓心的有效算法，需要建立一系列數學模型。

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)

根據最小區(qū)域準則，目標是確定圓心(x0,y0)，使h為最小值。然后，可以建立用于確定最小區(qū)域圓心以及評估圓度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 算法流程

本文提出了一種新的快速搜索圓心方法，更有效地解決圓度問題。該算法的本質是不斷更新每次迭代確定的圓心，直到誤差符合要求。其優(yōu)點在于：在圓度計算中，只需要搜索理想的圓心即可，因此計算容易編碼，并且可以在很短的時間內獲得足夠的精度，計算流程如圖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

根據提出的算法，首先，通過最小二乘技術確定近似圓心。使用這些測量數據點和近似圓心，可以創(chuàng)建以一對同心圓為邊界的最小區(qū)域，見圖6。最小區(qū)域的外接圓和內切圓分別由圓心點O，最遠的數據點3和最近的數據點4構成。顯然最小區(qū)域的值不是最小，因此，必須更新圓心直至滿足最小區(qū)域標準。即：沿著方向矢量l移動圓心，該方向矢量是線和線之間的等分線，步長為λ。然后，對圓心重復相同的計算，直到計算圓度大于前圓度。前圓度即為最終圓度評定結果。

圖6 最小區(qū)域Fig.6 Smallest area

從表2計算結果比對可以看出，本文方法時間僅需0.025 823 s，滿足最小區(qū)域標準。計算得到圓度為0.0106 mm，圓心坐標為(267.649 3,12.130 4)。最小二乘法可以快速解決圓度問題，而區(qū)域搜索法[12]需要很長時間才能獲得最準確的結果，兩者差異明顯。本文提出的算法所需時間比區(qū)域搜索法要少得多，而兩者計算得到圓度差值僅為0.000 7 mm，顯示了提高算法的效率，具有較高的準確性，可以滿足工程要求。

表2 計算結果比對Tab.2 Calculation result comparison

結果驗證了所提出算法，通過不斷更新圓心的方案，結合計算模型，縮短了計算時間，從而高效地解決了圓度問題。該策略未包括在每次計算迭代時確定最佳步長λ和方向矢量l這些參數。若在計算過程中能更好地確定這些參數，則可更大程度地簡化問題，節(jié)省更多的計算時間。但是，這些參數的確定仍然受到限制，需要做進一步的研究方可有利于消除這些限制。

5 結 論

本文提出了一種基于快速搜索圓心的圓度新算法，建立一系列理論模型，通過不斷更新圓心，使距離圓心的最遠點和最近點找到移動圓心的方向，再通過式(5)和式(6)計算下一個圓心，當計算得到的圓度大于上一個圓度時，停止迭代。實驗結果表明該圓度算法符合最小區(qū)域標準，可以有效地在較短時間內獲得足夠準確的計算結果。與區(qū)域搜索法相比，該算法的計算誤差<1 μm，計算效率可提高10倍以上 ，在工程應用中有較好的實用價值。