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

江本赤 韓 江 夏 鏈

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

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

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

基于上述考慮，在對常用參數化方法進行分析比較的基礎上，本文提出一種曲線對應點鄰域搜索比較的偏差求解方法。對于某具體的數據點，在使用常規方法求出曲線上的對應點之后，再將其領域內的曲線離散成若干個細分點，并分別求出該數據點與各細分點間的距離，最后將最小距離值作為曲線與該點之間的偏差。該方法顯著改善了偏差計算結果的可靠性和準確性，可更真實地反映B 樣條曲線的逼近精度。

1 B 樣條曲線逼近

1.1 B 樣條曲線定義

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

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

節點矢量U 中a 和b 的重復度都為p+1，除非特別聲明，通常取a=0，b=1。

1.2 B 樣條曲線逼近

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

2 逼近偏差計算方法

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

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

(2)其余數據點Qk在最小二乘的意義下被逼近，即

關于n+1 個變量Pi達到最小值。

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

2.1 常見參數化方法的對比與分析

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

當數據點均勻分布時均勻參數化與弦長參數化的結果相同。而向心參數化方法如下:

現在用上述3 種參數化方法，分別求解圖1 所示的B 樣條曲線偏差情況。圖2 所示的是對應點C(u'k)分布，圖3 所示的是各自的偏差分布情況。

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

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

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

鑒于此，下面提出一種計算數據點在曲線上對應點的改進方法，適用于B 樣條曲線逼近中的偏差計算。

2.2 鄰域搜索比較法

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

(1)求出各細分點對應的參數。在u'k左右各取出w 個對稱的參數值，即

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

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

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

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

3 實例驗證

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

通過比較不難看出，本文所提方法顯著提高了逼近偏差計算結果的準確性。

4 結語

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

(1)逼近偏差的計算精度問題，不僅影響對曲線逼近效果的評價，同時也直接影響曲線逼近的算法效率。

(2)適當擴大在曲線上搜索和比較的范圍，可顯著改善偏差計算結果的可靠性。

(3)通過調整鄰域搜索法中的分辨率參數，可以有效控制曲線上細分點的范圍和密度，進而實現對逼近偏差計算精度的調節。

［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］程仙國，劉偉軍，張鳴.特征點的B 樣條曲線逼近技術［J］.計算機輔助設計與圖形學學報，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］趙世田，趙東標，付瑩瑩.測量數據點的高精度B 樣條曲線擬合算法［J］.計算機集成制造系統，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］徐進，柯映林，曲巍崴.基于特征點自動識別的B 樣條曲線逼近技術［J］.機械工程學報，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 版.北京:清華大學出版社，2010.