吳文江,李明霞,2,3,蓋榮麗

1(中國科學(xué)院 沈陽計算技術(shù)研究所,沈陽 110004) 2(中國科學(xué)院大學(xué),北京 100049) 3(大連工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院,遼寧 大連 116034) 4(大連大學(xué) 信息工程學(xué)院,遼寧 大連 116622)

1 引 言

NURBS(non-uniform rational B-Spline)是非均勻有理B樣條的簡稱,是一種用于描述曲線和曲面幾何形狀的數(shù)學(xué)表示方法.通過使用NURBS可以實(shí)現(xiàn)對復(fù)雜曲線和曲面的準(zhǔn)確建模和描述,從而為數(shù)字化制造和工業(yè)設(shè)計提供了強(qiáng)有力的支持.因此,NURBS在工業(yè)設(shè)計、數(shù)值控制加工、計算機(jī)圖形學(xué)等領(lǐng)域中得到廣泛應(yīng)用.在ISO發(fā)布的工業(yè)產(chǎn)品數(shù)據(jù)交換標(biāo)準(zhǔn)STEP中,NURBS被視為定義工業(yè)產(chǎn)品幾何形狀的唯一數(shù)學(xué)方法.它為標(biāo)準(zhǔn)解析形式的基本曲線和曲面的精確表示和設(shè)計提供了通用的數(shù)學(xué)表示,因此在逆向工程中得到了廣泛的應(yīng)用[1].而影響NURBS曲線擬合精度的主要因素是節(jié)點(diǎn)向量選擇、數(shù)據(jù)點(diǎn)參數(shù)化和控制點(diǎn)求解.控制點(diǎn)的數(shù)量在很大程度上決定了NURBS樣條擬合算法的復(fù)雜性[2-4].

目前,許多學(xué)者和機(jī)構(gòu)都對NURBS曲線進(jìn)行了深入地研究,并取得了大量的研究成果.在控制點(diǎn)的計算方法中,最小二乘法是應(yīng)用最廣泛的方法.用最小二乘法計算控制點(diǎn)主要有兩種方式,一種是根據(jù)精度要求減少控制點(diǎn)的個數(shù),從原始數(shù)據(jù)點(diǎn)開始,在滿足精度要求的前提下逐步減少控制點(diǎn)的個數(shù),直到不滿足精度,取不滿足精度時的上一組控制點(diǎn)作為最終控制點(diǎn);另一個是根據(jù)精度要求從最少控制點(diǎn)個數(shù)依次增加控制點(diǎn),直到滿足精度為止.其中,第1種方法的計算量遠(yuǎn)高于第2種方法,特別是在處理有噪聲的密集點(diǎn)時,往往會得到不滿意的控制點(diǎn).因此,主要采用第2種方法[5,6].

周雅情等提出了一種基于關(guān)鍵點(diǎn)的最小二乘漸進(jìn)迭代逼近算法[7].該算法首先根據(jù)曲率選取關(guān)鍵點(diǎn)作為第1組控制點(diǎn),然后選取均勻控制點(diǎn)作為第2組控制點(diǎn).最后,使用排序算法根據(jù)足跡對控制點(diǎn)進(jìn)行排序.在算法迭代過程中,需要不斷調(diào)整均勻選取控制點(diǎn)的間隔和個數(shù),而且結(jié)果是相對隨機(jī)的,不一定是最優(yōu)的.袁佶鵬討論了數(shù)據(jù)點(diǎn)的獲取和預(yù)處理方法.根據(jù)小線段之間的夾角、相鄰小線段與數(shù)據(jù)點(diǎn)的長度比對數(shù)據(jù)集進(jìn)行預(yù)劃分[8].該算法為后續(xù)關(guān)鍵點(diǎn)識別提供了依據(jù).王愛增等通過中間控制邊矢量和旋轉(zhuǎn)軸中選取合適的節(jié)點(diǎn)矢量和旋轉(zhuǎn)角度,并通過縮放因子使其滿足單調(diào)性,由此構(gòu)造出曲率單調(diào)變化的NURBS樣條曲線,并通過數(shù)學(xué)方法證明了該方法[9].任利娟等提出了一種基于壓縮控制點(diǎn)的B樣條重建算法[10].該方法無需反算控制點(diǎn)即可在控制點(diǎn)對曲線進(jìn)行插補(bǔ),并引入形狀參數(shù)對控制點(diǎn)的切線特征和曲率特征進(jìn)行控制和調(diào)整.通過調(diào)整形狀參數(shù),可以提高擬合曲線的擬合精度.Seefried A提出了一種基于隱式約束的B-樣條連續(xù)可微軌跡生成方法,通過一組參數(shù)和一個二次規(guī)劃問題來計算B-樣條的控制點(diǎn).該方法可用于具有常量約束一階和二階導(dǎo)數(shù)和常量約束輸入的系統(tǒng)[11].Soumya D.Mohanty等使用粒子群算法進(jìn)行了B樣條節(jié)點(diǎn)的自由放置,但是節(jié)點(diǎn)的自由放置產(chǎn)生了節(jié)點(diǎn)聚類問題,從而導(dǎo)致過擬合現(xiàn)象發(fā)生,他們通過顯式正則化來抵消這種不良影響,達(dá)到了自適應(yīng)樣條擬合的目的[12].利用等弦長法對給定的離散點(diǎn)進(jìn)行曲率計算,并利用曲率分析方法提取關(guān)鍵特征點(diǎn),然后根據(jù)這些特征點(diǎn)構(gòu)造初始曲線.在曲線擬合迭代過程中,采用不斷在最大擬合誤差處插入新的插值點(diǎn)的方式以構(gòu)建新的近似曲線,直到插入新的插值點(diǎn)時擬合誤差不能大大減小.陳良驥等在使用NURBS樣條插值時根據(jù)數(shù)據(jù)點(diǎn)的曲率提出了一種新的特征點(diǎn)選取方法,可以壓縮海量離散刀位點(diǎn)數(shù)據(jù)[13].以上算法都是根據(jù)曲率進(jìn)行特征點(diǎn)選取,然后再根據(jù)特征點(diǎn)擬合或者插值得到初始曲線,進(jìn)行迭代,最終得到最優(yōu)的曲線.用這些方法進(jìn)行曲線擬合時,特征點(diǎn)的個數(shù)及位置是提高擬合精度的關(guān)鍵.

劉華勇等構(gòu)造了帶局部形狀參數(shù)的代數(shù)三角樣條曲線曲面,滿足一定的連續(xù)性,還具有局部性,能調(diào)整曲線曲面的外形,但是曲線只有C1連續(xù)[14].梁福生通過對離散點(diǎn)的幾何特征進(jìn)行分析,提出了一種新的節(jié)點(diǎn)布置方法,可以用較少的節(jié)點(diǎn)數(shù)量達(dá)到給定的擬合精度,實(shí)現(xiàn)了離散微段刀具軌跡精確重構(gòu)并有效減少節(jié)點(diǎn)向量的數(shù)量[15].張蒙等利用最小二乘漸進(jìn)迭代逼近算法對擬合曲線的控制點(diǎn)、節(jié)點(diǎn)和權(quán)值進(jìn)行優(yōu)化,從而得到高精度的曲線.優(yōu)化過程中,每一種變量類型都獨(dú)立進(jìn)行,以避免參數(shù)間的相互影響[16].李莎莎等采取插值和逼近同時進(jìn)行的B樣條擬合曲線方法,給每個數(shù)據(jù)點(diǎn)賦予權(quán)重,在迭代過程中根據(jù)誤差來調(diào)節(jié)權(quán)重,生成新的擬合曲線,如此迭代來得到高精度逼近曲線[17].以上算法都是通過多次迭代來增加控制點(diǎn)個數(shù)從而提高擬合精度,時間成本較大,且當(dāng)控制點(diǎn)個數(shù)增加到一定程度就很難再通過增加控制點(diǎn)個數(shù)來提高擬合精度,過多的控制點(diǎn)有時反而會引發(fā)曲線變形和扭曲.

蘆穗豪等基于改進(jìn)麻雀搜索算法,通過自動迭代內(nèi)節(jié)點(diǎn)向量配置,以誤差作為適應(yīng)度值進(jìn)行迭代,多次迭代后得到符合目標(biāo)精度的擬合曲線[18].蓋榮麗等提出了一種基于粒子群優(yōu)化算法求解最優(yōu)控制點(diǎn)的非均勻有理B樣條曲線擬合算法,使用粒子群優(yōu)化算法以擬合誤差作為適應(yīng)度值,對控制點(diǎn)位置進(jìn)行優(yōu)化,在不改變控制點(diǎn)個數(shù)的前提下進(jìn)一步提高了擬合精度[19].TIAN Xiao-qiang提出了一種基于粒子群優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的NURBS曲面改進(jìn)方法[20],將粒子群優(yōu)化BP神經(jīng)網(wǎng)絡(luò)應(yīng)用于NURBS曲面節(jié)點(diǎn)向量的訓(xùn)練.首先,利用累積弦長的參數(shù)化方法計算數(shù)據(jù)點(diǎn)的節(jié)點(diǎn)向量.然后,利用粒子群優(yōu)化BP神經(jīng)網(wǎng)絡(luò)建立節(jié)點(diǎn)向量預(yù)測模型.最后,由于使用了預(yù)測的節(jié)點(diǎn)向量,實(shí)現(xiàn)了快速且高精度的NURBS曲面.LI Xun等在解決移動機(jī)器人路徑規(guī)劃問題時提出了一種改進(jìn)粒子群算法集成方案,該方案綜合了均勻分布、指數(shù)衰減慣性權(quán)重、三次樣條插值函數(shù)和增強(qiáng)型控制的學(xué)習(xí)因子,以擺脫粒子群算法的應(yīng)用限制和收斂速度慢的缺點(diǎn)[21].Johannes Bureick等提出了一種精英遺傳算法用于調(diào)節(jié)B樣條的節(jié)點(diǎn)向量,以此來達(dá)到提高曲線擬合精度的目的[22].劉明增等提出一種基于漸進(jìn)迭代逼近的B樣條擬合方法,根據(jù)數(shù)據(jù)點(diǎn)的曲率特征選取數(shù)據(jù)點(diǎn)構(gòu)成初始擬合曲線,再根據(jù)初始擬合曲線的誤差分布逐步增加數(shù)據(jù)點(diǎn)直到滿足指定精度.但是算法中的B樣條的節(jié)點(diǎn)刪除步驟,會導(dǎo)致B樣條曲線發(fā)生較大的變化,從而導(dǎo)致誤差增大,繼而會增大迭代步數(shù)[23].以上都是通過優(yōu)化算法來優(yōu)化控制點(diǎn)位置或者參數(shù)位置來提高擬合精度,本質(zhì)上也是反復(fù)迭代,且優(yōu)化算法本身參數(shù)較復(fù)雜,計算量較大,結(jié)果隨機(jī)且比較費(fèi)時.

根據(jù)NURBS曲線的局部性,更改一個區(qū)域內(nèi)的曲線對其余區(qū)域的曲線沒有任何影響,本文利用此特性,對NURBS曲線的擬合誤差進(jìn)行分段分析,根據(jù)誤差分布及數(shù)據(jù)飽和度,提出了誤差敏感段的概念,將曲率變化平緩、誤差較低的區(qū)域進(jìn)行NURBS曲線擬合,而將誤差敏感區(qū)域使用其他的曲線代替,從而在無需迭代且不增加控制點(diǎn)的前提下通過對誤差敏感段的特殊處理來消除局部較大誤差,從而提高整體圖形的擬合效率和擬合精度.

2 NURBS曲線及性質(zhì)

2.1 NURBS曲線定義

一條p次NURBS曲線定義為[24]:

(1)

其中,{Pi}稱為控制點(diǎn),由{Pi}為頂點(diǎn)構(gòu)成的多邊形稱為控制多邊形,{wi}是權(quán)因子,{Ni,p(u)}是定義在非周期節(jié)點(diǎn)矢量U上的p次B樣條基函數(shù):

(2)

(3)

U如下:

(4)

一般令a=0,b=1,且對所有的i,wi>0.

2.2 NURBS曲線的局部修改性

根據(jù)式(2)可知,Ni,0(u)是一個階梯函數(shù),在半開區(qū)間u∈[ui,ui+1)外都是零.根據(jù)式(3)可知,當(dāng)p>0時Ni,p(u)是兩個p-1次基函數(shù)的線性組合.

根據(jù)基函數(shù)N1,3的計算過程,可以看到如果u?[ui,ui+p+1),則Ni,p(u)=0,這個性質(zhì)稱為基函數(shù)的局部支撐性.例如:N1,3是N1,0,N2,0,N3,0和N4,0的線性組合,因此N1,3僅在u∈[u1,u5)上非零.

根據(jù)基函數(shù)的局部支撐性,在任意給定的節(jié)點(diǎn)區(qū)間[uj,uj+1)內(nèi),最多有p+1個Ni,p是非零的,它們是Nj-p,p,…,Nj,p,例如在[u3,u4)上,0次基函數(shù)中只有N3,0是非零的,因此在該區(qū)間上非零的3次基函數(shù)只有N0,3,…N3,3.因此當(dāng)移動控制點(diǎn)Pi或改變權(quán)因子wi時,僅影響區(qū)間u∈[ui,ui+p+1)段曲線的形狀,這個性質(zhì)稱為NURBS曲線的局部修改性[23,24].

2.3 NURBS曲線導(dǎo)矢

由式(1)可知求NURBS曲線導(dǎo)矢可通過求B樣條基函數(shù)的導(dǎo)數(shù)得到,由式(3)可得基函數(shù)的求導(dǎo)公式為:

(5)

故,NURBS曲線的一階導(dǎo)矢可表示為:

(6)

其中,

(7)

3 基于誤差敏感區(qū)域特殊處理的NURBS曲線擬合算法

3.1 誤差敏感區(qū)域定義

NURBS曲線形狀受控制點(diǎn)影響,控制點(diǎn)的最優(yōu)位置無法精確求得,只能通過算法逼近,這就會導(dǎo)致有些部分的擬合曲線效果很好,非常貼近甚至插值于原始數(shù)據(jù)點(diǎn),而有些部分的擬合曲線則與原始數(shù)據(jù)點(diǎn)的距離相差較大,誤差大,擬合效果不理想.本論文通過對節(jié)點(diǎn)區(qū)間誤差的分析,識別并標(biāo)記出其中對整體擬合效果影響較大的區(qū)域,定義為誤差敏感區(qū)域.具體定義如下:

根據(jù)NURBS曲線的局部修改性,以uj為分界點(diǎn)對NURBS曲線進(jìn)行分段,修改某個區(qū)間[uj,uj+p+1)內(nèi)的曲線對其他曲線沒有影響,因此可以按照區(qū)間[uj,uj+p+1)對曲線進(jìn)行分段替換.

為了便于描述,定義區(qū)間[uj,uj+1)內(nèi)包含的原始數(shù)據(jù)點(diǎn)占總數(shù)據(jù)點(diǎn)的百分比為區(qū)間數(shù)據(jù)飽和度,飽和度越高則區(qū)間涵蓋的數(shù)據(jù)點(diǎn)越多,即壓縮比越高,以此來反映區(qū)間數(shù)據(jù)的壓縮情況.如果段誤差較低,且數(shù)據(jù)飽和度較高,說明該段的擬合精度較高,效果理想;如果段誤差明顯高于平均誤差,且數(shù)據(jù)飽和度不高,說明該段的擬合精度不高,且增加控制點(diǎn)無法明顯改善此情況,則將該段定義為誤差敏感段,進(jìn)行替換.

3.2 初始控制點(diǎn)計算

為了準(zhǔn)確描述待加工工件的形狀,原始數(shù)據(jù)點(diǎn)一般都比較密集且數(shù)量較大,如果直接使用所有的原始數(shù)據(jù)點(diǎn)來擬合NURBS曲線,會因?yàn)榭刂泣c(diǎn)過多而導(dǎo)致曲線扭曲,且算法的時間復(fù)雜度也會因此急劇增加,從而導(dǎo)致擬合效果和擬合效率都欠佳,因此有必要對原始數(shù)據(jù)點(diǎn)進(jìn)行壓縮,從中挑選出能代表工件關(guān)鍵特征的數(shù)據(jù)點(diǎn),稱之為關(guān)鍵點(diǎn).

最簡單的選取方式是以固定的間隔選取,然而這種方式初始關(guān)鍵點(diǎn)的數(shù)目不容易確定,且由于工件的形狀一般并不是均勻分布,故而選取的點(diǎn)不一定能代表工件的關(guān)鍵形狀.本文提出了一種基于特征點(diǎn)加輔助點(diǎn)的關(guān)鍵點(diǎn)選取方式.

曲率代表曲線的彎曲程度,因此曲率的變化趨勢可以在一定程度上體現(xiàn)工件曲線的變化趨勢,因此本文以離散點(diǎn)曲率作為參考值進(jìn)行關(guān)鍵點(diǎn)的選取.本文選用局部曲率極值點(diǎn)、拐點(diǎn)及折痕點(diǎn)作為初步關(guān)鍵點(diǎn)候選值.

曲率極值點(diǎn)、拐點(diǎn)和折痕點(diǎn)雖然代表了工件曲線的特征信息,但是如果僅使用這些點(diǎn)作為數(shù)據(jù)點(diǎn)來擬合NURBS曲線,誤差較大,不能滿足加工精度要求,因此需要額外添加輔助點(diǎn)來保證加工精度.

輔助點(diǎn)的添加需要能夠盡可能的提升加工精度,因此,本文使用擬合誤差最大點(diǎn)作為輔助點(diǎn).先用初步關(guān)鍵點(diǎn)候選值中的數(shù)據(jù)點(diǎn)初步擬合曲線,找到擬合誤差最大的點(diǎn),將其加入到關(guān)鍵點(diǎn)候選值中,再用新的數(shù)據(jù)點(diǎn)重新擬合曲線,看是否滿足加工精度要求,如果不滿足,則重復(fù)前面過程.

得到特征點(diǎn)加輔助點(diǎn)組成的關(guān)鍵點(diǎn)后,可以使用最小二乘逼近的方法計算NURBS曲線擬合所需的一組控制點(diǎn),此時由該組控制點(diǎn)擬合得到的NURBS曲線滿足或者基本滿足加工的精度需要,作為本算法的初始控制點(diǎn).

3.3 參數(shù)化

傳統(tǒng)NURBS曲線擬合中的參數(shù)都是根據(jù)控制點(diǎn)計算得到的,但是本文算法需要使用NURBS參數(shù)uj作為分割點(diǎn)統(tǒng)計落入?yún)?shù)區(qū)間區(qū)間[uj,uj+1)的原始數(shù)據(jù)點(diǎn),因此參數(shù)的選擇既要反映數(shù)據(jù)點(diǎn)的分布規(guī)律,還要反映數(shù)據(jù)點(diǎn)與參數(shù)之間的聯(lián)系.假設(shè)原始數(shù)據(jù)有ON個點(diǎn),記作{Qi},i=0,…,ON-1,關(guān)鍵點(diǎn)有KN個點(diǎn),記作{Ki},i=0,…,KN-1,控制點(diǎn)有m個點(diǎn),記作{Pi},i=0,…,m-1.

本文采取的NURBS曲線參數(shù)計算方法如下:

1)首先對原始數(shù)據(jù)點(diǎn)進(jìn)行參數(shù)化,為了使得到的參數(shù)可以盡可能地反映原始數(shù)據(jù)點(diǎn)的分布規(guī)律,本文使用了積累弦長參數(shù)化方法如下:

(8)

其中,Li是線段Qi-1Qi的長度.

3)最后根據(jù)式(4)配置NURBS參數(shù)U如下:

(9)

3.4 擬合誤差計算

因?yàn)殡x散數(shù)據(jù)點(diǎn)一般規(guī)模比較大,且擬合時為了保證擬合精度參數(shù)步長一般較小,所以擬合誤差的計算是整個算法中最耗時的一個環(huán)節(jié).為了盡可能的在保證計算準(zhǔn)確性的情況下提高計算效率,需要盡快找到離散數(shù)據(jù)點(diǎn)的可能區(qū)域,且應(yīng)盡量縮小候選區(qū)域,這樣才能減少計算量,提高算法效率.

3.5 誤差敏感區(qū)域識別

為了盡量減少最終擬合曲線的分段,防止出現(xiàn)過多的碎片,保證曲線的大范圍連續(xù),誤差敏感區(qū)域的識別分為兩個階段:第1階段為獨(dú)立的誤差敏感段識別;第2階段為獨(dú)立敏感段的鄰近段聯(lián)合,將鄰近孤立段盡量整合成一個連續(xù)的區(qū)域.

記加工允許的輪廓誤差為ε,每個數(shù)據(jù)點(diǎn)Qi的逼近誤差為erri,平均擬合誤差為avgErr,第i段的段誤差為segErri,平均區(qū)間數(shù)據(jù)飽和度為avgCom,第i段的數(shù)據(jù)飽和度為comRatei,根據(jù)段誤差和區(qū)間數(shù)據(jù)飽和度提出敏感段判定準(zhǔn)則如下:

1)如果segErri≥C1*avgErr(C1>1),且comRatei≤C2*avgCom(C2<1),說明該段數(shù)據(jù)壓縮比較低且誤差較高,擬合情況不理想,則將該段標(biāo)記為誤差敏感段;

2)如果segErri≥avgErr,且comRatei≤avgCom,但segi不是敏感誤差段,如果其前后鄰域段{segi-2,segi-1,segi+1,segi+2}有誤差敏感段,為了保持區(qū)間的連貫性,則將該段標(biāo)記為誤差敏感段;

3)如果segi中包含逼近誤差超過輪廓誤差ε的點(diǎn),則將其標(biāo)記為誤差敏感段;

4)如果segi中包含逼近誤差超過C1*avgErr且所在段的數(shù)據(jù)飽和度低于區(qū)間數(shù)據(jù)飽和度閾值C2*avgCom,則將其標(biāo)記為誤差敏感段.

根據(jù)上面識別出的誤差敏感段,進(jìn)行左右鄰近段掃描,整合最終誤差敏感區(qū)域.

1)如果segi-1和segi+1都是敏感誤差段,而segi是普通段,即兩段誤差敏感段之間有孤立的普通段,為了擴(kuò)大連續(xù)區(qū)域,則將segi也標(biāo)記為誤差敏感段,將[segi-1,segi+1]標(biāo)記為誤差敏感區(qū)域.

2)如果有連續(xù)的誤差敏感段,則將連續(xù)誤差敏感段整合為誤差敏感區(qū)域.

C1和C2可以根據(jù)目標(biāo)進(jìn)行更改,如果想要盡可能的提高擬合精度,則可以適當(dāng)降低C1提高C2的值;如果想要盡可能的保持曲線的連貫性,則可以適當(dāng)提高C1降低C2的值.一般C1取1.35～1.5,C2取0.5～0.65即可取得較好的效果.

3.6 銜接段處理

對銜接點(diǎn)約束如下:

1)連續(xù)性,即一段曲線的起點(diǎn)是另一段曲線的終點(diǎn),亦即A(0)=C(ua),且A(1)=C(ub);

2)光滑性,即兩段曲線在銜接點(diǎn)處的導(dǎo)數(shù)相同,亦即A′(0)=C′(ua)且A′(1)=C′(ub).

根據(jù)參數(shù)的計算方法可以在原始數(shù)據(jù)的參數(shù)U_中找到對應(yīng)于[uaub]的區(qū)間[u_cu_d],其中ua=u_c且ub=u_d.則數(shù)據(jù)點(diǎn){Qc…Qd}即使過渡曲線需要擬合或者插值的點(diǎn).

由于銜接點(diǎn)不一定正好是原始數(shù)據(jù)點(diǎn),為了保證銜接點(diǎn)條件(1)需要將銜接點(diǎn)加入數(shù)據(jù)點(diǎn)集UDS中,即UDS={C(ua),Qc…Qd,C(ub)}.

3.7 算法

在NURBS曲線的擬合中,由于加工形狀的變化不一,有時候會出現(xiàn)一些區(qū)域擬合效果很好,幾乎插值于原數(shù)據(jù)點(diǎn),而另一些區(qū)域則誤差較大不理想的情況.以往的方法會在誤差較大區(qū)域增加控制點(diǎn)來提高精度,但是當(dāng)區(qū)間內(nèi)包含數(shù)據(jù)點(diǎn)較少時,增加控制點(diǎn)很難使擬合曲線進(jìn)一步逼近原數(shù)據(jù)點(diǎn),反而會出現(xiàn)曲線扭曲、變形等情況.針對此問題,本論文提出了一種基于誤差敏感區(qū)域特殊處理的NURBS曲線擬合算法,算法流程如下:

1)首先對原始離散數(shù)據(jù)點(diǎn)進(jìn)行弦長參數(shù)化;

2)計算離散點(diǎn)的曲率值,根據(jù)離散點(diǎn)的曲率特征選取能代表圖形的關(guān)鍵點(diǎn),使用最小二乘逼近法得到NURBS曲線的初始控制點(diǎn);

3)根據(jù)上面闡述的參數(shù)化方法從原始數(shù)據(jù)點(diǎn)對應(yīng)的參數(shù)中提取出NURBS曲線的節(jié)點(diǎn)參數(shù);

4)進(jìn)行初始NURBS曲線擬合,計算初始誤差;

5)根據(jù)NURBS參數(shù)節(jié)點(diǎn)進(jìn)行誤差及數(shù)據(jù)飽和度分段分析,挑選出其中的初始誤差敏感段;

6)為了增加曲線的連續(xù)性,盡可能的減少孤立段,在5)的基礎(chǔ)上進(jìn)行敏感段前后鄰近段分析,并識別能夠納入敏感區(qū)域的鄰近段,確定最終敏感區(qū)域.

7)計算誤差敏感段所包含的原始數(shù)據(jù)點(diǎn)、起止銜接點(diǎn)坐標(biāo)及其導(dǎo)數(shù)值;

8)使用Akima和三次參數(shù)樣條進(jìn)行銜接替換;

9)輸出組合曲線.

4 算法驗(yàn)證

本文選用二維葉片和三維S試件兩種加工形狀進(jìn)行算法驗(yàn)證.其中,葉片有233個離散點(diǎn),S試件有361個離散點(diǎn).選用文獻(xiàn)[13]和文獻(xiàn)[19]中的算法作為對比算法,文獻(xiàn)[19]中分別選用粒子數(shù)20、30、50進(jìn)行80、100、200次迭代,選取最優(yōu)結(jié)果.

使用CPU 12th Gen Intel(R)Core(TM)i7-12700H,2.30 GHz,內(nèi)存16.0 GB的電腦配置,在Matlab下進(jìn)行運(yùn)行時間統(tǒng)計.

圖1 葉片初始擬合曲線及敏感誤差段Fig.1 Initial fitting curve and sensitive error segments of blade

先對二維葉片進(jìn)行本算法驗(yàn)證.首先計算離散點(diǎn)曲率值,并根據(jù)曲率值特征提取關(guān)鍵點(diǎn)進(jìn)行NURBS控制點(diǎn)計算,得到29個初始控制點(diǎn).

然后按照3.2節(jié)中的方法進(jìn)行參數(shù)化,以非零參數(shù)為分界點(diǎn)計算得到段平均誤差和數(shù)據(jù)飽和度.設(shè)置區(qū)間段平均誤差閾值系數(shù)C1=1.35,區(qū)間數(shù)據(jù)飽和度系數(shù)C2=0.65.

根據(jù)上文算法,可以識別出3段誤差敏感區(qū)域見圖 1.

對3段曲線誤差敏感段分別使用Akima樣條和三次參數(shù)樣條進(jìn)行替換,對銜接部分進(jìn)行放大對比,圖1中的敏感段①、②和③的放大圖分別如圖2～圖4所示.

圖2 葉片敏感段①Fig.2 Sensitive section ① of blade圖3 葉片敏感段②Fig.3 Sensitive section ② of blade圖4 葉片敏感段③Fig.4 Sensitive section ③ of blade

從圖2～圖4的對比結(jié)果可以看出相比于文獻(xiàn)[13]和文獻(xiàn)[19]中的算法,本文算法可以在誤差敏感區(qū)域更好的還原圖形形狀,其中三次參數(shù)樣條由于在銜接點(diǎn)具有C2連續(xù)性,因此其銜接效果比Akima更好.

仿真條件下,本文算法與文獻(xiàn)[13]和文獻(xiàn)[19]算法的擬合誤差對比如表1所示.可以看出本文算法在誤差控制上是最優(yōu)的,其最大誤差比文獻(xiàn)[13]和文獻(xiàn)[19]分別提升了52.44%和39.29%,平均誤差比文獻(xiàn)[13]和文獻(xiàn)[19]分別提升了16.67%和22.33%.對比文獻(xiàn)[13]的擬合誤差可以看出,本文算法通過3處誤差敏感區(qū)域的局部替換消除了原曲線中3處高誤差區(qū)域的誤差,從而達(dá)到了在不改變原有控制點(diǎn)和節(jié)點(diǎn)向量的前提下通過局部區(qū)間修改較大程度地提高擬合精度的目的.

表1 葉片誤差和運(yùn)行時間對比Table 1 Comparison of error and running time of blade

表1中本文算法的運(yùn)行時間按照三次參數(shù)樣條銜接進(jìn)行計算,對比表2中三次參數(shù)樣條和Akima單次銜接時間可以看出Akima銜接的運(yùn)行時間要更少,因此,運(yùn)行時間上本文算法和文獻(xiàn)[13]算法運(yùn)行時間相差不大,而文獻(xiàn)[19]因?yàn)樯婕皟?yōu)化算法的迭代運(yùn)算,其耗時最長,約是本文算法的72倍.

對三次參數(shù)樣條和Akima銜接段的計算時間進(jìn)行統(tǒng)計,見表2.

表2 程序段運(yùn)行時間對比Table 2 Comparison of program segment running time

NURBS樣條的擬合中耗時最大的程序段是擬合誤差的計算,每次控制點(diǎn)個數(shù)的增加都需要重新計算擬合誤差,控制點(diǎn)個數(shù)29～36之間單次擬合誤差的平均計算時間見表2.如果單純使用增加控制點(diǎn)個數(shù)來提高擬合精度的方法,當(dāng)控制點(diǎn)個數(shù)由29增加到36時才能達(dá)到本文算法的精度.此時,僅擬合誤差的計算就需要增加2.4059s,極大了增加了算法的時間開銷.而本文算法因?yàn)槭褂昧司植枯^大誤差段的插值銜接替換,在銜接段是插值于原數(shù)據(jù)點(diǎn)的,因次不僅可以直接消除局部較大誤差段,且在原擬合算法基礎(chǔ)上時間增加幾乎可以忽略不計.

為了驗(yàn)證本算法,使用三維S形試件空間圖形再次進(jìn)行實(shí)驗(yàn)驗(yàn)證.按照前面闡述的算法,首先計算其離散點(diǎn)曲率,根據(jù)曲率特征選取曲率極值點(diǎn)、拐點(diǎn)和折痕點(diǎn)共55個數(shù)據(jù)點(diǎn)作為初始關(guān)鍵點(diǎn),以0.05mm為輪廓誤差需要添加8個輔助點(diǎn)組成最終63個關(guān)鍵點(diǎn),使用最小二乘逼近計算得到最初的65個控制點(diǎn).

根據(jù)初始控制點(diǎn)擬合得到原始NURBS曲線,根據(jù)NURBS曲線非零節(jié)點(diǎn)向量區(qū)間計算其段平均誤差和區(qū)間數(shù)據(jù)飽和度,并進(jìn)行誤差敏感段篩選.區(qū)間段平均誤差閾值系數(shù)C1和區(qū)間數(shù)據(jù)飽和度系數(shù)C2同上.

根據(jù)上文算法進(jìn)行誤差敏感段識別和敏感段鄰近區(qū)域合并,可以識別出兩段敏感誤差區(qū)域見圖5中①和②.

圖5 S試件敏感誤差段Fig.5 Sensitive error segments of S-shaped test piece

分別對兩個敏感誤差區(qū)域進(jìn)行Akima和三次參數(shù)樣條替換,同時與文獻(xiàn)[13]和文獻(xiàn)[19]算法進(jìn)行對比,其放大圖見圖6和圖7所示,分別對應(yīng)于圖5中敏感區(qū)域①和②.

仿真條件下,本文算法與文獻(xiàn)[13]和文獻(xiàn)[19]算法的擬合誤差對比見表3,本文算法最大誤差比文獻(xiàn)[13]和文獻(xiàn)[19]分別提升了25.38%和12.65%,平均誤差比文獻(xiàn)[13]和文獻(xiàn)[19]分別提升了9.86%和60.25%.

圖6 S試件敏感段①Fig.6 Sensitive section ① of S-shaped test piece

圖7 S試件敏感段②Fig.7 Sensitive section ② of S-shaped test piece

表3 S試件誤差和運(yùn)行時間對比Table 3 Comparison of error and running time of S-shaped test piece

S試件比葉片數(shù)據(jù)多了一個維度,控制點(diǎn)個數(shù)約是葉片的2倍,對比表1和表3可以看出當(dāng)原始數(shù)據(jù)點(diǎn)維度和個數(shù)增加時,本文算法和文獻(xiàn)[13]算法的運(yùn)行時間幾乎是線性增長的,不會隨著運(yùn)算規(guī)模的增長而耗時劇增.

5 總 結(jié)

針對NURBS樣條擬合中控制點(diǎn)過多會導(dǎo)致曲線變形且算法復(fù)雜度過高的問題,本文提出一種基于分段誤差和數(shù)據(jù)飽和度分析的誤差敏感段特殊處理的樣條擬合方法,在擬合曲線整體效果較理想,但是個別點(diǎn)或者區(qū)域不合格或者不理想的情況下,無需增加控制點(diǎn)個數(shù)和更改參數(shù),在原曲線的基礎(chǔ)上針對不理想段進(jìn)行局部替換,即可較大程度地提升擬合精度.如果想要更大程度的提高擬合精度,可以適當(dāng)降 低區(qū)間段平均誤差閾值系數(shù)C1和區(qū)間數(shù)據(jù)飽和度系數(shù)C2的值,這樣就可以增加局部大誤差的消除概率,從而更有效的降低擬合誤差,提高擬合精度.本文采用了Akima樣條和三次參數(shù)樣條分別對二維的葉片圖形和三維的S試件圖形進(jìn)行替換測試,并與文獻(xiàn)[13]和文獻(xiàn)[19]進(jìn)行了對比,證明了本文算法的有效性.另外,本文算法幾乎不增加原擬合算法的時間成本,在時間耗費(fèi)上要遠(yuǎn)遠(yuǎn)優(yōu)于通過增加控制點(diǎn)個數(shù)來提高精度的傳統(tǒng)算法和通過迭代優(yōu)化調(diào)整控制點(diǎn)位置的優(yōu)化算法.