基于多結點樣條的自由曲線最小誤差逼近及其應用

余建德， 黃 靜

（1. 澳門科技大學資訊科技學院，澳門；

2. 北師大珠海分校信息技術與軟件工程學院，廣東 珠海 519085）

基于多結點樣條的自由曲線最小誤差逼近及其應用

余建德1， 黃 靜2

（1. 澳門科技大學資訊科技學院，澳門；

2. 北師大珠海分校信息技術與軟件工程學院，廣東 珠海 519085）

多結點樣條函數具有良好的局部性，而最小二乘法對數據擬合的全局性較好， 因此多結點樣條函數最小二乘逼近的穩定性及數值精度都能得到有效的保證。該文綜合兩者的特點，實現了自由曲線離散數據最小逼近誤差數學模型的建立。同時應用此數學模型于一些平面及空間（甚至一些帶噪音的）自由曲線擬合上和幾何造型骨骼化上，測試其對各種自由曲線的擬合效果，結果證明最小逼近效果明顯。

計算機應用；最小誤差逼近；多結點樣條；自由曲線

1 問題的提出

在實際應用特別是在反向工程中，對工件測量（數字化）之后得到的是一系列離散數據，為了實現工件的再加工或誤差評定，必須對這些離散數據進行光滑而精確的曲線曲面重構，即數學建模。為實現高效率高精度光滑建模，以用于CAD/CAM 系統，研究曲線曲面最小誤差逼近擬合建模具有重要意義。

在建模領域，通常使用B樣條對曲線曲面進行插值建模[1-4]，而多結點樣條近年來也因為它的各種優勢而被廣范用于插值法建模方面，且效果顯著。多結點樣條函數最早是針對插值問題提出的，1975年，齊東旭教授[5-7]給出了多結點樣條基本函數的構造及計算格式；后繼的文獻[8-11]給出進一步的理論分析和應用。對插值問題而言，多結點技術的最大優點是導致插值過程無須求解任何方程組，而且插值格式具有局部性，這是與通常樣條函數插值（三彎矩算法）在計算上的根本區別。被廣泛應用的B樣條曲線擬合方法雖然也不必求解方程組，也具有局部性，但在幾何造型的應用中，因其無法保證通過型值點而給工程計算帶來不便，因此多結點方法在工程應用上和理論研究上受到重視。

鑒于曲線建模是曲面建模的基礎，本文研究這種甚具潛力的多結點樣條擬合建模及其關鍵問題，實驗表明，所建立的曲線擬合數學模型逼近擬合效果頗佳。

2 多結點樣條函數

多結點基本樣條函數是通過對等距結點 B樣條基本函數的平移及迭加而構成。 記I為單位算子，μ為平均算子，對任意給定的常數 ξ，定義

圖 1 多結點樣條基本函數

多結點樣條基本函數（見圖1）的性質類似于B樣條基本函數，其主要區別在于：不是非負函數，這將導致它構成的插值格式不是線性正算子，因此插值結果對數據而言不具有保凸性，這是追求顯式解，局部性及基數型性質等優越性付出的代價。盡管如此，正如B樣條基本函數插值對數據沒有保凸性，但仍然實用一樣，多結點樣條插值也仍然是實用的，它已被成功地應用于飛機外形，進氣道，機翼，海洋，地質的數據處理以及動畫片的計算機制作等領域。

多結點技巧的意義首先在于構造顯式插值格式。此外，基本函數的有界支集性質保證了插值曲線（面）的局部性，有利于數據處理，如果為整數結點上給定的數據，則多結點樣條插值函數可寫為

當給出確定的邊界約束條件之后，即可明確給出求和的上下限，對于給定幾何造型的型值點，其參數形式的多結點樣條曲線定義為

3 多結點樣條最小逼近誤差擬合數學模型

（1） 數學模型的建立值得注意的是，由于多結點樣條基函數的性質，使得該方程組的系數矩陣具有帶狀對角特點，條件數較好，方程組求解容易速度快，求出的系數為型值點的代表點。這一特點使得用多結點樣條最小逼近誤差擬合數學模型的方法優于其他方法。

矩陣表達式為

4 實例分析及其應用

利用參數形式的三次多結點樣條作最佳逼近的例子。

（1） 平面曲線的擬合（見圖2）

下列兩例子的原曲線參數方程分別為

圖2 平面曲線擬合

從這兩個例子表明，用多結點樣條最佳逼近的擬合，對于帶有噪音的平面離散數據，依然可以較好地重構原曲線（見圖2），而且所使用的段數較少，只需16段，即17個擬合系數，即可較好地完成對1024個點的數據擬合。

（2） 空間曲線的擬合（見圖3）

下列兩例子(例1和例2)的原曲線參數方程分別為

圖3 空間曲線擬合

圖3(a)和圖3(b)的4個圖分別是原曲線，原曲線離散化（1024點），帶噪音的離散點及 32段三次多結點樣條擬合曲線；圖3(c)和圖3(d)的3個圖分別是帶噪音的離散點云數據，32段三次多結點樣條擬合曲線及擬合后曲線的立體形狀。例子表明，使用較少段數（這里是 32段）的多結點樣條對于帶噪音的空間離散數據，其擬合效果良好。

（3） 基于多結點樣條最佳逼近骨骼化

設想幾何造型是由它的骨骼和骨骼外圍的噪音數據組成，那么骨骼化的過程就相當于去噪音的過程，只要選擇好合適的段數，通過多結點樣條最佳逼近來實現幾何造型的骨骼化是可行的（見圖4）。文獻[15]應用及優化了組合模板的概念提出一種快速實用的細化算法，下面是該算法圖4（中）與本文算法（右）的比較例子：

圖4 幾何造型的骨骼化實例比較

5 結 論

本文實現了多結點樣條最佳逼近曲線建模，方程組因條件數較好求解容易速度快，求出的系數為型值點的代表點。這一特點使得用多結點樣條最小逼近誤差擬合數學模型的方法優于其他方法，具有很大靈活性。參數化的多結點樣條最佳逼近對于平面及空間離散數據，甚至是帶噪音的離散數據，擬合效果良好。應用多結點樣條最佳逼近的去噪音性質，實驗及證實多結點樣條最佳逼近還具備對幾何造形骨骼化的能力，其骨骼化效果滿意。

[1] Toni Prahasto, Sanjeev Bedi. Optimization of knots for the multi curve B-spline approximation[C]// Proceedings of the Geometric Modeling and Processing 2000, Hong Kong, China. IEEE Computer Society, 2000: 150.

[2] Asif Masood, Muhammad Sarfraz, Shaiq A Haq. Curve approximation with quadratic B-splines[C]//Ninth International Conference on Information Visualisation (IV'05), 2005: 419-424.

[3] Byung-Gook Lee, Joon Jae Lee, Jaechil Yoo. An efficient scattered data approximation using multilevel B-splines based on quasi-interpolants[C]//Fifth International Conference on 3-D Digital Imaging and Modeling (3DIM'05), 2005: 110-117.

[4] Les A Piegl, Wayne Tiller. Approximating surfaces of revolution by nonrational B-splines [J]. IEEE Computer Graphics and Applications, 2003, 23(3): 46-52.

[5] 齊東旭. 關于多結點基數型δ-spline插值(I)[J]. 吉林大學學報(自然科學版), 1975, (1): 70-81.

[6] 齊東旭. 關于多結點基數型 δ-spline插值(II)[J]. 吉林大學學報(自然科學版), 1976, (2): 36-44.

[7] 齊東旭. 關于多結點基數型 δ-spline插值(III)[J]. 吉林大學學報(自然科學版), 1979, (3): 1-8.

[8] 齊東旭, 梁振珊. 多結點樣條磨光(I)[J]. 高等學校計算器學學報, 1979, 1(2): 196-200.

[9] 齊東旭, 梁振珊. 多結點樣條磨光(II)[J]. 高等學校計算器學學報, 1981, 3(1): 65-74.

[10] 齊東旭. 多結點樣條插值曲線與曲面的矩陣表達式及余項估計[J]. 計算數學, 1982, 4(3): 244-252.

[11] 李華山, 丁 瑋, 齊東旭. 多結點樣條插值及其多尺度細化算法[J]. 中國圖像圖形學報, 1997, 2(10): 701-706.

[12] LeBourgeois F, Emptoz H. Skeletonization by gradient regularization and diffusion[C]//Ninth International Conference on Document Analysis and Recognition (ICDAR 2007) Vol 2, 2007: 1118-1122.

[13] 唐 瑤, 張錫哲, 王鉦旋. 一種中國書法作品的骨架提取算法[J]. 工程圖學學報, 2006, 27(5): 98-104.

[14] Takuya Oda, Yuichi Itoh, Wataru Nakai, et al. Interactive skeleton extraction using geodesic distance[C]// 16th International Conference on Artificial Reality and Telexistence—— Workshops (ICAT' 06), 2006: 275-281.

[15] 梅 園, 孫懷江, 夏德深. 一種基于改進后模板的圖像快速細化算法[J]. 中國圖像圖形學報, 2006, 11(9): 1306-1311.

Least Error Approximation and Its Application for Free-Form Curves Based on Multi-Knots Spline

U Kin-Tak1, HUANG Jing2
( 1. Faculty of Information Technology, Macao University of Science and Technology, Macao, China; 2. College of Information Technology and Software Engineering, Beijing Normal University, Zhuhai Campus, Zhuhai Guangdong 519085, China )

Muti-knots spline has good locality and least square method has good global characteristics for data fitting. Therefore, the stability and numerical accuracy of least square method based on multi-knots spline approximation could be reached effectively. This paper combines the advantages of them and completes the model building of the free-form curves with least approximation error based on multi-knots spline. Meanwhile, this method is applied to the free-form-curve fitting of some plane and space (even with noise) data and Geometry Shape Skelectonization. The fitting results show that the least approximation effect is good.

computer application; least error approximation; multi-knots spline; free-form-curves

TP 391.41

A

：1003-0158(2010)01-0088-06

2008-08-05

澳門科技發展基金資助項目（018/2005A，045/2006A）；北京師范大學珠海分校重點資助項目（Z06007）

余建德（1973-），男，廣東中山人，講師，博士研究生，主要研究方向為數字信號處理算法。