一種基于快速搜索圓心的圓度新算法

盛東良， 詹劍良， 朱 丹

(紹興職業(yè)技術(shù)學(xué)院 機(jī)電工程與交通學(xué)院，浙江 紹興 312000)

1 引 言

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

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

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

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

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

本文提出了一種基于搜索理想圓心的新算法，以期解決圓度問(wèn)題。該算法的目的是找到理想的圓心，以及距離該圓心最遠(yuǎn)和最近的點(diǎn)。對(duì)于每次迭代，根據(jù)距上一個(gè)圓心的最遠(yuǎn)和最近的點(diǎn)來(lái)搜索下一個(gè)圓心。

2 幾何特性及數(shù)學(xué)模型

2.1 幾何特性

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

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

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

2.2 數(shù)學(xué)模型

令(x1,y1),(x2,y2),…，(xi,yi),…，(xn,yn)表示xy平面中被測(cè)圓的n個(gè)點(diǎn)的x和y坐標(biāo)。必須找到理想圓的圓心(x0,y0)，見圖2。

圖2 圓度Fig.2 Roundness

第i個(gè)點(diǎn)(xi,yi)相對(duì)于理想圓心的半徑為

(1)

將這些半徑值中的最大值表示為rmax，將最小值表示為rmin，圓度h為

h=rmax-rmin

(2)

根據(jù)最小區(qū)域準(zhǔn)則，目標(biāo)是確定圓心(x0,y0)，使h為最小值。然后，可以建立用于確定最小區(qū)域圓心以及評(píng)估圓度hmin的數(shù)學(xué)模型為

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

=min{rmax}-max{rmin}

(3)

為了使圓度最小，根據(jù)距離上一個(gè)圓心的最遠(yuǎn)的點(diǎn)(xmax,ymax)和最近的點(diǎn)(xmin,ymin)更新圓心。即：沿著外部等分線l移動(dòng)圓心，以便最小化rmax和最大化rmin，見圖3。

圖3 更新圓心Fig.3 Update center

更新圓心的計(jì)算如下：

(4)

(5)

(6)

3 算法流程

本文提出了一種新的快速搜索圓心方法，更有效地解決圓度問(wèn)題。該算法的本質(zhì)是不斷更新每次迭代確定的圓心，直到誤差符合要求。其優(yōu)點(diǎn)在于：在圓度計(jì)算中，只需要搜索理想的圓心即可，因此計(jì)算容易編碼，并且可以在很短的時(shí)間內(nèi)獲得足夠的精度，計(jì)算流程如圖4所示。算法的關(guān)鍵步驟如下：

(1) 用最小二乘法確定給定點(diǎn)的近似圓心。

(2) 計(jì)算半徑ri，它是第i個(gè)點(diǎn)到圓心的距離。拾取最遠(yuǎn)和最近的點(diǎn)。根據(jù)式(4)計(jì)算方向矢量。

(3) 更新圓心，然后重復(fù)步驟2，直到計(jì)算圓度比上一個(gè)圓度值大，即前后圓度之差小于0。

(4) 輸出前圓度，即為最終評(píng)定結(jié)果。

圖4 算法流程Fig.4 Algorithm flow

4 驗(yàn)證與討論

基于所提出的算法解決圓度問(wèn)題的示例見表1，此示例中采用文獻(xiàn)[12]給出的被測(cè)實(shí)際圓的測(cè)量數(shù)據(jù)，表中列出了50個(gè)數(shù)據(jù)點(diǎn)的坐標(biāo)。

表1中的該組數(shù)據(jù)是在Global FX777型三坐標(biāo)測(cè)量機(jī)上，對(duì)φ=63.5 mm的圓孔進(jìn)行實(shí)測(cè)獲得的，50個(gè)數(shù)據(jù)點(diǎn)的坐標(biāo)如圖5所示。

圖5 數(shù)據(jù)點(diǎn)Fig.5 Data point

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

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

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

表2 計(jì)算結(jié)果比對(duì)Tab.2 Calculation result comparison

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

5 結(jié) 論

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