基于多結(jié)點樣條的自由曲線最小誤差逼近及其應(yīng)用

余建德， 黃 靜

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

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

基于多結(jié)點樣條的自由曲線最小誤差逼近及其應(yīng)用

余建德1， 黃 靜2

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

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

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

計算機應(yīng)用；最小誤差逼近；多結(jié)點樣條；自由曲線

1 問題的提出

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

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

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

2 多結(jié)點樣條函數(shù)

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

圖 1 多結(jié)點樣條基本函數(shù)

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

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

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

3 多結(jié)點樣條最小逼近誤差擬合數(shù)學模型

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

矩陣表達式為

4 實例分析及其應(yīng)用

利用參數(shù)形式的三次多結(jié)點樣條作最佳逼近的例子。

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

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

圖2 平面曲線擬合

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

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

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

圖3 空間曲線擬合

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

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

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

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

5 結(jié) 論

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

[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] 齊東旭. 關(guān)于多結(jié)點基數(shù)型δ-spline插值(I)[J]. 吉林大學學報(自然科學版), 1975, (1): 70-81.

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

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

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

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

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

[11] 李華山, 丁 瑋, 齊東旭. 多結(jié)點樣條插值及其多尺度細化算法[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

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

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