雷賢卿，崔靜偉，王海洋

（1.河南科技大學機電工程學院，河南 洛陽 471003；2.洛陽軸研科技股份有限公司，河南 洛陽 471003）

橢圓輪廓度誤差幾何遍歷搜索算法

雷賢卿1，崔靜偉2，王海洋1

（1.河南科技大學機電工程學院，河南 洛陽 471003；2.洛陽軸研科技股份有限公司，河南 洛陽 471003）

結(jié)合橢圓幾何特性及其相關的評定問題的研究現(xiàn)狀，提出了橢圓輪廓度誤差的遍歷搜索算法。該算法的原理是以最小二乘橢圓兩焦點為初始參考點，按一定的規(guī)則分別布置一系列的網(wǎng)格點構造輔助焦點，依次以各輔助點為假定理想橢圓焦點，構造一系列的輔助橢圓作為假定理想橢圓。計算測量點到這些假定理想橢圓的距離極差，最終實現(xiàn)橢圓輪廓度誤差的最小區(qū)域評定。實例驗證表明：該算法可以有效、正確地評定橢圓輪廓度誤差。

誤差評定；橢圓度；遍歷搜索算法；最小區(qū)域

0 引言

橢圓輪廓度的公差帶是與理想橢圓等距的兩個橢圓等距線之間的區(qū)域。對于其輪廓的幾何參數(shù)和輪廓度誤差等的評定方法，國家標準尚未做出明確的規(guī)定和說明。但橢圓形零件在特殊場合的應用，如發(fā)動機活塞的裙部設計成中凸變橢圓形狀，以保證其吸能效果，這就使得橢圓線輪廓度精密測量及精確評定有著重要的價值。但關于橢圓輪廓度誤差的評定，國家和國際標準都沒有給出一種特定的評定算法。近年來橢圓輪廓度誤差的評定方法主要是運用最小二乘法，但最小二乘法的計算誤差較大，不能進行精確評定，很難符合實際測量的要求。不少學者都進行了橢圓輪廓度誤差評定的研究，比較有代表性的算法有：基于代數(shù)距離的最小二乘法［1－5］，正交最小二乘法［6］，矢函數(shù)法［7］，采用對應特征點法、一維搜索法（DFP）及一維搜索法的自適應調(diào)整的線輪廓誤差評定方法［8］，最小方差估計擬合算法［9］，橢圓直接擬合算法［10］，最大內(nèi)接橢圓法，最小外接橢圓法［11］。這些評定方法對于橢圓輪廓度誤差的評定都有一定的作用和效果。

本文結(jié)合橢圓輪廓度誤差幾何特性及其評定問題，提出了幾何遍歷搜索的橢圓輪廓度誤差最小區(qū)域評定算法，該算法可以有效、準確地評定橢圓度誤差。

1 幾何遍歷搜索算法的原理

首先通過橢圓輪廓上測量點的坐標值，以一定方法（如最小二乘法）確定參考橢圓，計算所有測量點到參考橢圓的距離極差值（橢圓輪廓度誤差，記為 e0）。如圖 1所示，以參考橢圓的兩焦點F1（x01，y01）、F2（x02，y02）為初始參考點，在其周圍以定邊長f（如最小二乘橢圓度誤差值或估計的橢圓度誤差值）分別布置一個正方形為搜索區(qū)域，將正方形區(qū)域的邊長分別進行n等分，并對搜索區(qū)域進行網(wǎng)格劃分，可得兩組（n＋1）2網(wǎng)格點，（n＋1）4對輔助點（即新的焦點坐標），計算測量點到輔助點所確定的假定理想橢圓的誤差值echa，可得到（n＋1）4個echa，其中這（n＋1）4個echa中的最小值記為e1。比較e0和e1的大小，根據(jù)橢圓度誤差的定義可知：e0和e1中較小值就是被測橢圓的最小區(qū)域橢圓度誤差。

2 幾何遍歷逼近算法的步驟

設橢圓輪廓上測量點的坐標值為：pi（xi，yi）， （i＝1，2，…，N）。

2.1 構造輔助點

以最小二乘橢圓的焦點坐標F01（x01，y01）、F02（x02，y02）為初始參考點（橢圓輪廓度誤差的最小二乘評定算法在許多參考文獻中均有詳細的介紹，本文不再重復）。以最小二乘橢圓輪廓度誤差或估計的橢圓輪廓度誤差值e0為定邊長f（f＝e0）構造正方形區(qū)域，對每個正方形區(qū)域的邊長進行n等分的網(wǎng)格劃分，得到兩組（n＋1）2個網(wǎng)格點，將兩組網(wǎng)格點進行組合可得（n＋1）4對輔助點。

輔助點坐標按式（1）～式（4）進行計算：首先，利用式（1）計算出正方形左上角的輔助點坐標Fv1（xv1，yv1）、Fv2（xv2，yv2）作為計算基點：

圖1 橢圓度誤差幾何遍歷搜索評定原理

以計算基點為參考點，利用式（2）和式（3）計算輔助點坐標Fv1（p，q）（xv1（p，q），yv1（p，q））、Fv2（p，q）（xv2（p，q），yv2（p，q）），（p，q＝1，2，…，n＋1）：

2.2 構造輔助橢圓

以輔助點Fv1（p，q）（xv1（p，q），yv1（p，q））（p，q＝1，2，…，n＋1）依次與輔助點Fv2（p，q）（xv2（p，q），yv2（p，q））（p，q＝1，2，…，n＋1）組合可得到（n＋1）4對假定理想橢圓焦點坐標，可構造出（n＋1）4個輔助橢圓。由橢圓的幾何特性可知：橢圓可以用下列5個獨立參數(shù)來唯一確定，長軸半徑、短軸半徑、中心坐標及長軸與x軸的夾角。

（Ⅰ）長軸半徑aj（j＝1，2，…，16）的確定。僅由兩焦點坐標無法確定一個橢圓，由橢圓定義可知：橢圓上的點到兩焦點坐標的距離之和為長軸半徑的2倍，本文利用測量點的坐標值，用式（5）計算所有測量點pi（xi，yi）（i＝1，2，…，N）分別到這（n＋1）4對焦點的距離dij（j＝1，2，…，（n＋1）4），作為（n＋1）4個輔助橢圓的長軸值。輔助橢圓長軸半徑值aj（j＝1，2，…，（n＋1）4）利用式（6）取所有測量點所確定的長軸半徑值的平均值。

（Ⅱ）短軸半徑bj（j＝1，2，…，（n＋1）4）的確定。利用式（7）根據(jù)兩焦點坐標計算輔助橢圓的焦距。由橢圓長、短半軸間的關系按式（8）確定短軸半徑。

（Ⅲ）中心坐標x0j、y0j（j＝1，2，…，（n＋1）4）的確定，由橢圓位置的幾何關系可得：

（Ⅳ）長軸與x軸的夾角θj（j＝1，2，…，（n＋1）4）的確定：

由以上得到橢圓主參數(shù)，則輔助橢圓的方程可表達為：

設橢圓的一般方程為x2＋Axy＋By2＋Cx＋Dy＋E＝0，將式（12）展開，計算假定理想橢圓的一般方程系數(shù)：

可得到（n＋1）4個輔助橢圓方程x2＋Ajxy＋Bjy2＋Cjx＋Djy＋Ej＝0，j＝1，2，…，（n＋1）4。

2.3 計算測量點到輔助橢圓的距離極差

設點Mij（Xij，Yij）為過測量點pi（xi，yi），（i＝1，2，…，N）的橢圓法線與輔助橢圓的交點，由于交點Mij（Xij，Yij）既在法線上又在輔助橢圓上，即點Mij（Xij，Yij）滿足方程組（14）：

用式（15）計算所有測量點到（n＋1）4個輔助橢圓的距離，其中測量點在輔助橢圓外側(cè)的最大距離與內(nèi)側(cè)的最小距離之差為橢圓度誤差echaj，即式（16）。

有（n＋1）4個輔助橢圓就可以得到（n＋1）4個距離極差值echaj，根據(jù)橢圓度誤差的定義可以知道，（n＋1）4個距離極差值中的最小者min echaj即為被測橢圓的最小區(qū)域橢圓度誤差，用F表示。

3 實例驗證

表1為文獻［6］中的橢圓的測量數(shù)據(jù)，利用本文所提算法對同一組數(shù)據(jù)處理結(jié)果比較，驗證橢圓度幾何遍歷搜索算法的正確性。設定初始條件如下：

（Ⅰ）初始參考點坐標：用最小二乘法計算的橢圓焦點坐標為F1（－11.283 1，－21.423 3）、F2（11.284 0，81.425 5）。

（Ⅱ）擴展區(qū)域的初始邊長：f＝e0（最小二乘法計算出的橢圓度誤差值e0＝0.004 9 mm）。

（Ⅲ）擴展區(qū)域劃分的網(wǎng)格點數(shù)：每個擴展區(qū)域劃分的網(wǎng)格點數(shù)為k（k分別取25，100，225，400），則組成k2對橢圓焦點坐標來進行計算。

數(shù)據(jù)處理結(jié)果見表2，與其他文獻中不同方法計算結(jié)果比較見表3。

表1 測量數(shù)據(jù) mm

表2 數(shù)據(jù)處理結(jié)果

表3 不同方法的計算結(jié)果比較

由表2和表3可以看出：本文提出的橢圓輪廓度幾何遍歷搜索算法結(jié)果與文獻［7］的計算結(jié)果中橢圓的主參數(shù)相一致，且評定結(jié)果更精確。

由表2可以看出：在使用本算法時，初始區(qū)域一定的情況下，網(wǎng)格點劃分越多，得到的誤差值呈現(xiàn)出越來越小的規(guī)律，所以算法是收斂的。當 k≥100時，所計算出的橢圓輪廓度誤差值之間相差小于0.000 1 mm，說明算法具有良好的穩(wěn)定性。所以在實際應用劃分網(wǎng)格時k≤100即可。這就說明幾何遍歷誤差最小區(qū)域評定算法可以有效、準確地評定橢圓輪廓度誤差。

4 結(jié)束語

結(jié)合橢圓度誤差的幾何特性，研究了橢圓輪廓度誤差的幾何遍歷搜索算法。該算法對測樣點是否均勻沒有要求，其原理簡單，易于編程。應用文獻［7］的測量數(shù)據(jù)，將幾何遍歷搜索算法應用于橢圓度誤差評定中，在每個搜索區(qū)域劃分網(wǎng)格點數(shù)分別為100時，計算結(jié)果分別比最小外接橢圓法［10］、最大內(nèi)接橢圓法［10］、矢函數(shù)法［6］計算的結(jié)果減小了2.6μm、2.9μm和3.0μm。計算結(jié)果證明：幾何遍歷搜索算法能夠有效地對橢圓輪廓度誤差進行精確評定，對三坐標測量機上橢圓輪廓度誤差的評定具有一定的借鑒作用。

［1］ 崔靜偉，雷賢卿，王海洋，等.基于最小二乘法的平面任意位置橢圓輪廓度誤差的精確計算［J］.制造業(yè)自動化，2013，35（2）：114－115，146.

［2］ Sung J A，Wolfgang R，Hans-Jurgen W.Least-squares Orthogonal Distances Fitting of Circle，Sphere，Ellipse，Hyperbola，and Parabola［J］.Pattern Recognition，2001，34：2283－2303.

［3］ 鄒益民，汪渤.一種基于最小二乘的不完整橢圓擬合算法［J］.儀器儀表學報，2006，27（7）：808－812.

［4］ 劉書桂，李蓬，那永林.基于最小二乘原理的平面任意位置橢圓的評價［J］.計量學報，2002，23（4）：245－247.

［5］ 馬前南，李航，劉麗麗，等.最小二乘改進算法及其在橢圓擬合中的應用［J］.河南科技大學學報：自然科學版，2014，35（3）：18－21.

［6］ W ijewickrema S，Esson C，Charlesl P A.A Novel Approach to Orthogonal Distance Least Squares Fitting of General Conics［C］／／ISA.2009：138－145.

［7］ 侯宇，張競，崔晨陽.復雜線輪廓度誤差坐標測量的數(shù)據(jù)處理方法［J］.計量學報，2002，23（1）：12－16.

［8］ 張琳，郭俊杰，姜瑞，等.自由曲線輪廓度誤差評定中的坐標系自適應調(diào)整［J］.儀器儀表學報，2002，23（2）：203－206.

［9］ Cui Y T，John W，Herbert R.Estimation of Ellipse Parameters Using Optimal Minimum Variance Estimator［J］.IEEE Trans PAMI，2002，24（5）：620－638.

［10］ Fitzgibbon A，Pilu M，F(xiàn)isher R B.Direct Least Square Fitting of Ellipses［J］.Pattern Analysis and Machine Intelligence 1999，21（5）：476－480.

［11］ 李秀明，石照耀.基于方程的橢圓輪廓度的評定［J］.北京工業(yè)大學學報，2009，35（10）：1303－1307.

TH161

A

1672－6871（2014）06－0009－05

國家自然科學基金項目（50875076）；河南省基礎與前沿技術研究計劃基金項目（122300413209，122300410114）

雷賢卿（1963－），男，河南洛寧人，教授，博士，碩士生導師，主要從事精密測試技術方面的研究.

2014－03－28