余建德， 黃 靜

（1. 澳門科技大學(xué)資訊科技學(xué)院，澳門；

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

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

余建德1， 黃 靜2

（1. 澳門科技大學(xué)資訊科技學(xué)院，澳門；

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

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

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

1 問題的提出

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

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

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

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

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

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

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

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

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

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

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

矩陣表達(dá)式為

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

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

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

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

圖2 平面曲線擬合

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

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

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

圖3 空間曲線擬合

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

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

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

圖4 幾何造型的骨骼化實(shí)例比較

5 結(jié) 論

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

[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é)點(diǎn)基數(shù)型δ-spline插值(I)[J]. 吉林大學(xué)學(xué)報(bào)(自然科學(xué)版), 1975, (1): 70-81.

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

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

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

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

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

[11] 李華山, 丁 瑋, 齊東旭. 多結(jié)點(diǎn)樣條插值及其多尺度細(xì)化算法[J]. 中國圖像圖形學(xué)報(bào), 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]. 工程圖學(xué)學(xué)報(bào), 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ìn)后模板的圖像快速細(xì)化算法[J]. 中國圖像圖形學(xué)報(bào), 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ā)展基金資助項(xiàng)目（018/2005A，045/2006A）；北京師范大學(xué)珠海分校重點(diǎn)資助項(xiàng)目（Z06007）

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