B 樣條曲線逼近偏差的精確求解算法*

江本赤 韓 江 夏 鏈

(合肥工業(yè)大學(xué)CIMS 研究所，安徽 合肥 230009)

B 樣條是計(jì)算機(jī)輔助設(shè)計(jì)中的重要研究方向，已被確定為描述工業(yè)產(chǎn)品幾何形狀的數(shù)學(xué)標(biāo)準(zhǔn)［1-2］。在逆向工程等應(yīng)用中，常需要用B 樣條曲線逼近實(shí)測的有序數(shù)據(jù)點(diǎn)列［3-4］。國內(nèi)外學(xué)者就此類問題開展大量的研究［3-7］，并取得了重要成果。Park 等人［5］提出了基于自適應(yīng)誤差控制的逼近算法，該方法無需事先指定控制頂點(diǎn)數(shù)目;徐進(jìn)等人［6］提出了可自動(dòng)識(shí)別特征點(diǎn)的B 樣條曲線逼近技術(shù)，該方法可有效控制曲線的形狀細(xì)節(jié);Yoshimoto 等人［7］提出了一種適用于平面離散數(shù)據(jù)點(diǎn)擬合的遺傳算法，該方法對(duì)光滑數(shù)據(jù)的擬合效果較好。

偏差反映了曲線與離散點(diǎn)之間的逼近程度，是衡量逼近質(zhì)量的重要指標(biāo)。上述文獻(xiàn)中的算法都包含了基于偏差控制的迭代運(yùn)算，而偏差計(jì)算的結(jié)果將決定迭代的次數(shù)，并影響相關(guān)參數(shù)的調(diào)整方向。從理論上講，偏差值應(yīng)為以數(shù)據(jù)點(diǎn)為圓心并與曲線相切的圓弧半徑，但此法太過復(fù)雜，顯然不可取。目前最常見的偏差計(jì)算方法，主要是先對(duì)數(shù)據(jù)點(diǎn)參數(shù)化，然后求出各參數(shù)值在曲線上的對(duì)應(yīng)點(diǎn)，并將數(shù)據(jù)點(diǎn)與對(duì)應(yīng)點(diǎn)之間的距離作為該點(diǎn)處的逼近偏差。事實(shí)上，該方法的可靠性較差，在絕大多數(shù)情況下所求得的對(duì)應(yīng)點(diǎn)不是最近點(diǎn)，其計(jì)算值存在較大誤差，甚至可能是實(shí)際偏差值的數(shù)倍，容易因?yàn)椤罢`判”而增加多余的迭代次數(shù)，嚴(yán)重影響了算法的效率。因此，對(duì)于B 樣條曲線逼近偏差計(jì)算方法的研究很有必要。

基于上述考慮，在對(duì)常用參數(shù)化方法進(jìn)行分析比較的基礎(chǔ)上，本文提出一種曲線對(duì)應(yīng)點(diǎn)鄰域搜索比較的偏差求解方法。對(duì)于某具體的數(shù)據(jù)點(diǎn)，在使用常規(guī)方法求出曲線上的對(duì)應(yīng)點(diǎn)之后，再將其領(lǐng)域內(nèi)的曲線離散成若干個(gè)細(xì)分點(diǎn)，并分別求出該數(shù)據(jù)點(diǎn)與各細(xì)分點(diǎn)間的距離，最后將最小距離值作為曲線與該點(diǎn)之間的偏差。該方法顯著改善了偏差計(jì)算結(jié)果的可靠性和準(zhǔn)確性，可更真實(shí)地反映B 樣條曲線的逼近精度。

1 B 樣條曲線逼近

1.1 B 樣條曲線定義

B 樣條曲線的方程為［8］

式中:p 為次數(shù);Pi為曲線的控制頂點(diǎn);Ni，p(u)為B 樣條基函數(shù)，是定義在節(jié)點(diǎn)矢量U 上的p 次分段多項(xiàng)式，其數(shù)值由公式(2)和(3)求出。

節(jié)點(diǎn)矢量U 中a 和b 的重復(fù)度都為p+1，除非特別聲明，通常取a=0，b=1。

1.2 B 樣條曲線逼近

與插值不同的是，B 樣條逼近不要求曲線嚴(yán)格通過而是最接近給定數(shù)據(jù)點(diǎn)，以捕獲給定數(shù)據(jù)的形狀，且每點(diǎn)處的偏差都小于誤差界限。圖1 所示的是一條B樣條曲線逼近離散點(diǎn)的情形。

2 逼近偏差計(jì)算方法

先來看B 樣條曲線逼近中最小二乘法的偏差控制與計(jì)算方法。對(duì)于給定m+1 個(gè)數(shù)據(jù)點(diǎn)Qk(k=0，1，…，m)，先確定參數(shù)值{u'k}，使包含n+1 個(gè)控制頂點(diǎn)的曲線滿足下面兩個(gè)條件:

(1)曲線通過首尾點(diǎn)，即Q0=C(0)，Q1=C(1);

(2)其余數(shù)據(jù)點(diǎn)Qk在最小二乘的意義下被逼近，即

關(guān)于n+1 個(gè)變量Pi達(dá)到最小值。

其中的C(u'k)是數(shù)據(jù)點(diǎn)Qk在曲線上的對(duì)應(yīng)點(diǎn)，為曲線在該點(diǎn)的逼近偏差，而C(u'k)與數(shù)據(jù)點(diǎn)參數(shù)值u'k的獲取方法有關(guān)。下面對(duì)幾種最常見參數(shù)化方法進(jìn)行分析比較。

2.1 常見參數(shù)化方法的對(duì)比與分析

最常見參數(shù)化方法有3 種，即均勻參數(shù)化、弦長參數(shù)化和向心參數(shù)化。其中，均勻參數(shù)化計(jì)算最為簡單，即弦長參數(shù)化方法如下:

當(dāng)數(shù)據(jù)點(diǎn)均勻分布時(shí)均勻參數(shù)化與弦長參數(shù)化的結(jié)果相同。而向心參數(shù)化方法如下:

現(xiàn)在用上述3 種參數(shù)化方法，分別求解圖1 所示的B 樣條曲線偏差情況。圖2 所示的是對(duì)應(yīng)點(diǎn)C(u'k)分布，圖3 所示的是各自的偏差分布情況。

為了進(jìn)一步說明不同參數(shù)化方法的使用效果，下面再分別計(jì)算另一組數(shù)據(jù)點(diǎn)的逼近偏差，圖4 所示的是數(shù)據(jù)點(diǎn)在曲線上對(duì)應(yīng)點(diǎn)，其偏差數(shù)值的分布情況見圖5。

通過圖3 和圖5 可以看出，在相同條件下，弦長參數(shù)化所求出的偏差數(shù)值最小，這是由于它在分配參數(shù)時(shí)考慮了相鄰數(shù)據(jù)點(diǎn)的距離大小;向心參數(shù)化對(duì)相鄰數(shù)據(jù)點(diǎn)的距離值進(jìn)行了開方處理，弱化了原始數(shù)據(jù)信息的影響(在曲線插值中處理數(shù)據(jù)點(diǎn)急轉(zhuǎn)彎變化時(shí)，它可以得到比弦長參數(shù)化更好的效果);而均勻參數(shù)化對(duì)應(yīng)的偏差值最大，則是由于它在分配參數(shù)時(shí)沒有參考任何數(shù)據(jù)點(diǎn)的原始信息。因此，在求解B 樣條曲線逼近偏差的過程中，用弦長參數(shù)化方法分配原始數(shù)據(jù)點(diǎn)的參數(shù)最為合理。

通過圖2 和圖4 可以看出，無論采用哪一種參數(shù)化方法，所求出對(duì)應(yīng)點(diǎn)C(u'k)都不同程度地偏離了其應(yīng)有位置。即使落在曲線上、理論偏差為零的數(shù)據(jù)點(diǎn)，其求出的偏差數(shù)值也可能很大，即實(shí)際曲線早已達(dá)到逼近精度要求，而不必要的迭代計(jì)算仍需繼續(xù)進(jìn)行。最極端的情況是，僅僅由于對(duì)應(yīng)點(diǎn)嚴(yán)重偏離應(yīng)有位置，導(dǎo)致求出的偏差值永遠(yuǎn)達(dá)不到預(yù)定精度要求。

鑒于此，下面提出一種計(jì)算數(shù)據(jù)點(diǎn)在曲線上對(duì)應(yīng)點(diǎn)的改進(jìn)方法，適用于B 樣條曲線逼近中的偏差計(jì)算。

2.2 鄰域搜索比較法

為了改善逼近偏差計(jì)算結(jié)果的可靠性，對(duì)于所有原始數(shù)據(jù)點(diǎn)，先用常規(guī)方法求出其在曲線上的對(duì)應(yīng)點(diǎn)C(u'k)，再在C(u'k)的鄰域內(nèi)將曲線離散成若干細(xì)分點(diǎn)，并分別計(jì)算細(xì)分點(diǎn)與原始數(shù)據(jù)點(diǎn)的距離。記Qk點(diǎn)的參數(shù)為u'k，求解曲線在第k 個(gè)數(shù)據(jù)點(diǎn)Qk處逼近偏差的具體操作步驟如下:

(1)求出各細(xì)分點(diǎn)對(duì)應(yīng)的參數(shù)。在u'k左右各取出w 個(gè)對(duì)稱的參數(shù)值，即

u"j=(u'k-wΔu")+jΔu"，j=0，1，…，2w

(2)分別計(jì)算數(shù)據(jù)點(diǎn)Qk與各細(xì)分點(diǎn)間的距離Lj。Lj=Qk-C(u"j)，j=0，1，…，2w。

(3)求出Lj的最小值Lk。Lk=min(Lj)，作為曲線在Qk點(diǎn)處的逼近偏差。

此處需要指出的是，由于Δu"=Δu'2w 且Δu'=t(u'k+1-u'k-1)，t∈(0，1］，故C(u'k)點(diǎn)的鄰域大小被限制在前后兩原始數(shù)據(jù)點(diǎn)C(u'k-1)與C(u'k+1)之間，并可以通過系數(shù)t 來調(diào)節(jié)2w+1 個(gè)細(xì)分點(diǎn)的疏密程度。在w 取較大值的同時(shí)，t 的取值越小，細(xì)分點(diǎn)越集中，所求逼近偏差值的可靠性越高。圖6 所示的分別是取w=2，t=0.4 和w=3，t=0.2 時(shí)所得的細(xì)分離散點(diǎn)的情況。

3 實(shí)例驗(yàn)證

為了驗(yàn)證上述方法的可行性和有效性，下面仍以圖1 所示的數(shù)據(jù)為例，取w=3，t=0.2，結(jié)合均勻參數(shù)化、弦長參數(shù)化和向心參數(shù)化方法，將改進(jìn)前后的效果進(jìn)行對(duì)比，比較的結(jié)果如圖7、圖8 和圖9 所示。

通過比較不難看出，本文所提方法顯著提高了逼近偏差計(jì)算結(jié)果的準(zhǔn)確性。

4 結(jié)語

本文分析了現(xiàn)有B 樣條曲線逼近偏差的計(jì)算方法存在的問題，并在此基礎(chǔ)上探索出了一種基于鄰域搜索比較的精確偏差求解方法，得出了如下結(jié)論:

(1)逼近偏差的計(jì)算精度問題，不僅影響對(duì)曲線逼近效果的評(píng)價(jià)，同時(shí)也直接影響曲線逼近的算法效率。

(2)適當(dāng)擴(kuò)大在曲線上搜索和比較的范圍，可顯著改善偏差計(jì)算結(jié)果的可靠性。

(3)通過調(diào)整鄰域搜索法中的分辨率參數(shù)，可以有效控制曲線上細(xì)分點(diǎn)的范圍和密度，進(jìn)而實(shí)現(xiàn)對(duì)逼近偏差計(jì)算精度的調(diào)節(jié)。

［1］Park H，Lee J H.B-spline curve fitting based on adaptive curve refinement using dominant points［J］.Computer-Aided Design，2007，39(6):439-451.

［2］程仙國，劉偉軍，張鳴.特征點(diǎn)的B 樣條曲線逼近技術(shù)［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2011，23(10):1714-1718.

［3］Piecl L A，Tiller W.Least-square B-spline curve approximation with arbitrary end derivatives［J］.Engineering with Computers，2000，16(2):109-116.

［4］趙世田，趙東標(biāo)，付瑩瑩.測量數(shù)據(jù)點(diǎn)的高精度B 樣條曲線擬合算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16(8):1708-1713.

［5］Park H，Kim K，Lee S C.A method for approximate NURBS curve compatibility based on multiple curves refitting［J］.Computer-Aided Design，2000，32(4):237-252.

［6］徐進(jìn)，柯映林，曲巍崴.基于特征點(diǎn)自動(dòng)識(shí)別的B 樣條曲線逼近技術(shù)［J］.機(jī)械工程學(xué)報(bào)，2009，45(11):212-217.

［7］Yoshimoto F，Harada T，Yoshimoto Y.Data fitting with a spline using a real-coded genetic algorithm［J］.Computer-Aided Design，2003，35(8):751-760.

［8］Les Piegl，Wayne Tiller.非均勻有理B 樣條［M］.2 版.北京:清華大學(xué)出版社，2010.