基于輪廓約束點的B樣條曲面擬合算法

江本赤　韓　江　田曉青　夏　鏈

合肥工業大學，合肥，230009

基于輪廓約束點的B樣條曲面擬合算法

江本赤韓江田曉青夏鏈

合肥工業大學，合肥，230009

提出了一種面向截面測量數據的B樣條曲面擬合算法。首先對原始數據點列進行降噪處理，然后遴選出曲率優勢點，并將其作為初始的輪廓約束點，得到插值于約束點的初始曲線。再在需改善擬合精度的區域增加約束點，直至獲得滿足精度要求的B樣條曲線。最后以約束點數目最多的曲線為準，在其余的曲線上增加差額數目的約束點，并進行平均弦長參數化，構造出B樣條曲線簇，最終獲得B樣條擬合曲面。仿真實驗結果表明，該方法可顯著壓縮曲面模型的控制頂點數目，具有較高的曲面重構效率。

逆向工程；輪廓約束點；B樣條；曲面擬合

0　引言

由截面測量數據進行曲面重構是科學計算可視化(visualization in scientific computing,VISC)的重要內容之一，在醫學可視化、無損探傷和逆向工程等領域應用廣泛[1]。B樣條具有凸包性、連續性與光滑性等諸多優點，故在曲面重構中被廣泛采用[2-3]。對于數目龐大的測量數據點，若采用直接插值的方法獲取B樣條曲面，將導致節點和控制頂點數量過大，給后續的曲面光順與修改、數據交換等造成負擔[4-5]。因此，在滿足數據輪廓精度要求的前提下，如何使曲面的數學模型包含盡量小的數據量，一直是該領域研究熱點問題之一。

文獻[6-11]對B樣條曲面擬合中的相關技術，包括散亂點數據參數化和數據壓縮等進行了研究。早期有代表性的插值方法[6]是先插值各截面數據點列構造B樣條曲線，再通過節點插入獲得可相容的曲線簇，最后對曲線簇的控制頂點放樣得到插值曲面。這種方法較直觀，但由于引入了節點插入操作，勢必會引起控制頂點數量的膨脹[2]。為此，Piegl等[7]構造了具有非退化特性的參數區間，以增加節點選擇的靈活性，使所得的控制頂點數目明顯減少；在此基礎上，Park[8]采用能量極小化方法進一步壓縮了曲面模型的數據量。王文珂等[10]借鑒傳統蒙皮算法的思想，提出了一種由無序B樣條曲線來擬合B樣條曲面的算法，可得到滿足誤差要求的光滑擬合曲面，但當曲線數目較多時該算法會遇到數值穩定性問題。綜合上述情況，對B樣條曲面擬合相關技術展開進一步研究仍然非常必要。

本文提出一種面向截面測量數據的擬合算法。首先采用弦高法剔除原始數據點中的壞點，以得到較光滑的線形數據點列；然后求出離散曲率值，將超過平均曲率值的局部曲率極大值點定義為曲率優勢點，并作為曲線輪廓的初始約束點，得到初始的插值B樣條曲線；再計算出偏差分布情況，并將超過允許誤差的局部偏差極大值點增補為輪廓約束點，直到滿足擬合精度要求；然后以約束點數最多的曲線為準，將其余曲線的約束點補齊以得到拓撲矩形的數據點陣；最后計算出公用的節點矢量，獲得最終的B樣條單向蒙皮曲面。對一組截面測量數據的曲面擬合實驗驗證了算法的可行性。

1　截面B樣條曲線的獲取

對于各截面測量數據，先用弦高法對截面數據進行消噪處理，然后根據點列的曲率分布情況，確定曲率優勢點并將優勢點作為型值點，計算出各截面的初始B樣條曲線。

1.1數據預處理

掃描數據點中一般會包含失真點，它們不能反映實際輪廓且對曲線光順性存在較大影響，稱作噪聲點或壞點。在截面掃描數據點中，如果某個數據點偏離其相鄰的兩個點，且偏離程度超過預設值，則可視為壞點。關于剔除壞點的研究報道較多，針對截面測量數據的線形分布特點，本文采用文獻[12]中的弦高差方法來去除壞點，對于考察點Pi，連接兩個相鄰點得到弦線Pi-1Pi+1，如果點Pi到該弦的距離大于允許誤差，則將該點剔除。圖1所示是某截面數據預處理效果。

圖1　預處理后的某截面數據

下面以圖1中的數據點為例，闡述獲取截面B樣條曲線的具體步驟。

1.2輪廓約束點的確定

1.2.1離散曲率計算

本文采用文獻[13]給出的近似法，將數據點Pi處的曲率Ki近似為3個相鄰點Pi-1、Pi和Pi+1所在圓弧的曲率。圖1中數據點的曲率分布情況如圖2所示。

圖2　離散點的曲率求解

1.2.2輪廓約束點的遴選

經預處理之后的密集數據點，其曲率分布能大體反映出輪廓走勢。圖1中的點列共包含202個數據點，為了壓縮擬合曲線的數據量，現通過曲率值來確定初始輪廓約束點，以下簡稱約束點。

首先考慮曲率極大值法。即數據點Pi處的曲率值Ki，需同時滿足條件Ki>Ki-1和Ki>Ki+1。找出曲率極大值所對應的數據點，并將其作為約束點。則圖1中的數據點包含67個約束點，其擬合情形如圖3所示。由此得到數據點與擬合曲線間的最大偏差值為0.144 mm，平均偏差值為0.051 mm，均方差為0.028 mm，偏差分布情況見圖4。

圖3　曲率極大值法擬合效果

圖4　圖3對應的擬合偏差分布

從圖3所示的約束點分布情況來看，該方法較有效地壓縮了數據量，但即使在相對平直的局部區域，也分布了比較密集的約束點，顯然沒有必要。

再來考察曲率臨界值法。事先設定曲率臨界值Kcrt，將曲率值滿足Ki>Kcrt的數據點作為約束點。不失一般性，此處將離散曲率的平均值Kavg設為臨界值，即Kcrt=Kavg。對于圖1中的數據點，用此方法確定的約束點為64個，所得擬合曲線如圖5所示。最大擬合偏差值為0.969 mm，平均偏差值為0.100 mm，均方差為0.229 mm，偏差分布情況見圖6。

圖5　曲率臨界值法擬合效果

圖6　圖5對應的擬合偏差分布

由圖5可見，約束點可提取輪廓彎曲的局部區域，但由于該區域的離散曲率值一般都大于平均值，故約束點非常密集，而相對平直的區域約束點過少，這種分布顯然也是不可取的。

上述兩種確定約束點的方法，各有優劣。為利用二者的優點，本文選取超過平均曲率值的曲率極大值點作為約束點。即同時滿足以下兩個條件：①Ki>Ki-1且Ki>Ki+1；②Ki>Kavg。此處將符合上述條件的數據點稱為曲率優勢點，并將其作為輪廓約束點，對于開曲線，則需將首尾兩個端點直接當作約束點。

采用曲率優勢點法，則圖1中的數據點只包含31個約束點，其擬合情形如圖7所示。由此得到最大擬合偏差值為0.918 mm，平均偏差值為0.164 mm，均方差為0.261 mm，偏差分布情況見圖8。

圖7　曲率優勢點法擬合效果圖

圖8　圖7對應的擬合偏差分布

與圖3和圖5相比，圖7中的約束點數目得到了進一步的縮減，同時能在一定程度上保證數據點的輪廓精度。下面將插值于曲率優勢點的曲線作為初始曲線。

誠然，由曲率優勢點所確定的曲線，盡管大大壓縮了數據量，但并不能保證擬合精度。若初始曲線存在擬合偏差超過預設值的局部區域，則需進行局部優化。

1.3擬合精度的優化

由圖8可以看出，只有少量數據點處的擬合偏差值為零，因此偏差曲線一般會出現多個峰值，記允許誤差為[δ]，若初始曲線的某些峰值大于[δ]，則直接將偏差峰值對應的數據點增設為約束點。也就是說，新的約束點將由兩部分構成，即曲率優勢點和少數偏差峰值數據點。

以圖7中的初始擬合曲線為例，設[δ]=0.5 mm，對照圖8可知，需要增加2個約束點，新曲線的擬合效果如圖9所示。相應的擬合偏差最大值為0.235 mm，平均偏差值為0.060 mm，均方差為0.057 mm，分布情況見圖10。

圖9　初始曲線的局部擬合精度優化

圖10　圖9對應的擬合偏差分布

可見，增加約束點之后，曲線局部區域的擬合精度得到了明顯改善，而此時的輪廓約束點數為33個。該方法與曲率極值法和曲率臨界值法相比，顯然更加合理。當然，若偏差峰值仍大于[δ]，則需采用相同方法增加約束點，直到獲得滿足要求的B樣條曲線。

2　B樣條曲面的構造

利用上述方法，可以獲得滿足精度要求的各截面B樣條曲線，但是這些曲線是孤立的，缺乏相容性。各截面數據輪廓曲率變化各異，因而各節點矢量也不盡相同。由于B樣條曲面具有張量積特性，需要解決曲線之間的相容性問題。為此，下面設法獲取各截面曲線公用的節點矢量。

2.1公用節點矢量的獲取

2.1.1約束點的參數化

為計算公用節點矢量，首先必須保證各曲線具有相同數量的約束點。前面得到的孤立B樣條曲線簇，盡管已滿足擬合精度要求，其擬合偏差曲線仍會存在多個峰值。現將各峰值點對應的數據點，按其偏差值由大到小的順序存入各自數組，稱作備用約束點數組。

記第i條曲線的現有約束點數目為Ci，Ci的最大值記為Cmax。為確保各曲線具有相同的節點數目，現從各備用數組中依次取出必要數目的約束點，對于第i條曲線，需取出Cmax-Ci個數據點作為約束點。至此，所有曲線的約束點數目都為Cmax。

接下來實現各約束點的參數化。為盡量考慮型值點的分布對曲線形狀的影響，此處采用平均弦長參數化方法。設共有k條截面曲線，對于每一條曲線，依次連接各約束點得到Cmax-1段弦線，記第i條曲線的第j個弦長值為Li,j，則曲線簇第j段的弦長平均值Lj為

(1)

j=1,2,…,Cmax-1

因此，用來計算節點矢量的總弦長d為

(2)

而其余參數

(3)

t=1,2,…,Cmax-2

2.1.2節點矢量的計算

記曲線次數為p，m=Cmax+p。下面計算曲線簇公用的節點矢量U。其中，u0=u1=…=up=0，um-p=um-p+1=…=um=1，中間的節點采用平均值法，用下式求出：

(4)

j=1,2,…,Cmax-p-1

這種方法得到的控制頂點與約束點的數目相等，避免了非奇異矩陣的產生，便于后續控制頂點的計算。

2.2控制網絡的反算

(5)

圖11所示的是B樣條曲線簇的矩形拓撲控制網絡示意圖。

圖11　控制頂點網絡

至此，曲面的節點矢量和控制頂點均已求出，即B樣條曲面已被定義。

3　仿真實驗與分析

為驗證本文算法的可行性與有效性，下面以一組截面點云數據為例，用一張雙三次B樣條曲面對其進行擬合。圖12所示的是經預處理之后的截面數據點，共21條線性點列，包含2557個數據點，分布在40mm×50mm×12mm的空間里，平均每條點列包含約120個數據點。

圖12　截面數據舉例

按照上述步驟，通過遴選曲率優勢點獲得了初始擬合曲線，并以[δ]=0.5 mm為逼近偏差約束條件，對局部區域進行了精度優化，最終得到了V向B樣條曲線簇(即各曲線的參數u為常數)，圖13所示的是其中的一條曲線。單條曲線包含的控制頂點數目最多為22個，最少為13個。

圖13　三次B樣條曲線

為滿足曲線簇的相容性要求，將所有曲線的輪廓約束點都增加至22個。然后運用平均弦長參數法，得到公用節點矢量為

U=(0，0，0，0，0.047，0.095，0.142，0.190，0.238，0.285，0.333，0.381，0.428，0.476，0.523，0.571，0.619，0.667，0.714，0.761，0.809，0.857，0.904，0.952，1，1，1，1)

V=(0，0，0，0，0.067，0.153，0.179，0.186，0.229，0.243，0.309，0.381，0.398，0.434，0.515，0.551，0.588，0.629，0.667，0.695，0.715，0.750，0.811，0.923，1，1，1，1)

所得的控制網絡為21行×22列，即共有462個控制頂點，如圖14所示。最終重構的B樣條蒙皮曲面見圖15。與原數據點數目相比，減少了2095個，即減少81.97%。

圖14　重構曲面的控制網絡

圖15　B樣條曲面重構

4　結論

(1)通過曲率優勢點法所確定的輪廓優勢點，可在提取截面數據基本形狀的前提下，大幅縮減曲面模型的數據量，為后續的數據運算奠定基礎。

(2)將初始擬合的偏差峰值對應點增設為B樣條曲線型值點，可快速有效地提高局部逼近精度。

(3)與曲率極大值法和曲率臨界值法相比，利用曲率優勢點法所得型值點的分布更加合理，可避免曲率較大區域的型值點過于密集，同時對于較平直的區域亦具有較高的輪廓保真度。

[1]王瑜,鄭津津,周洪軍,等.斷層輪廓的雙三次非均勻B樣條曲面重構[J].中國科學技術大學學報, 2011, 41(5):384-391.

Wang Yu, Zheng Jinjin, Zhou Hongjun, et al. Bi-cubic Non-uniform B-spline Surface Reconstruction for Slice Contours[J].Journal of University of Science and Technology of China,2011,41(5):384-391.

[2]張麗艷,周來水,蔡煒斌,等.基于截面測量數據的B樣條曲面重建[J].應用科學學報,2002, 20(2): 173-177.

Zhang Liyan, Zhou Laishui, Cai Weibin, et al. B-spline Surface Reconstruction Based on Digitized Section Data[J]. Journal of Applied Sciences, 2002, 20 (2): 173-177.

[3]李濤,劉浩.B樣條曲面的雙向插值造型算法[J].計算機工程與應用, 2012,48(35):178-181.

Li Tao, Liu Hao. Bidirectional Interpolation Modeling Algorithm for B-spline Surface[J]. Computer Engineering and Applications, 2012, 48(35):178-181.

[4]杜興吉,周曉軍,吳瑞明,等.超聲檢測中復雜曲面數字化方法研究[J].中國機械工程,2005, 16(8):686-689.

Du Xingji,Zhou Xiaojun,Wu Ruiming,et al. Research on Sculptured Surface Digitizing on Ultrasonic Inspection[J]. China Mechanical Engineering,2005,16(8):686-689.

[5]Woodward C. Skinning Techniques for Interactive B-spline Surface Interpolation[J]. Computer-Aided Design，1988，20(8):441-451.

[6]李運平,周來水,王志國,等.基于剛架模型的多張B樣條曲面變形[J].中國機械工程, 2013，24(24):3355-3365.

Li Yunping, Zhou Laishui, Wang Zhiguo,et al. Shape Modification of Multi B-spline Surfaces Via Rigid Frame[J]. China Mechanical Engineering, 2013, 24(24):3355-3365.

[7]Piegl L，Tiller W. Reducing Control Points in Surface Interpolation[J].IEEE Computer Graphics and Applications, 2000, 20(5):70-74.

[8]Park H. Lofted B-spline Surface Interpolation by Linearly Constrained Energy Minimization[J].Computer-Aided Design, 2003, 35(14): 1261-1268.

[9]Weiss V, Andor L, Renner G, et al. AdvancedSurface Fitting Techniques[J].Computer Aided Geometric Design, 2002, 19(1):19-42.

[10]王文珂,李思昆.無序B樣條曲線的曲面擬合算法[J].計算機輔助設計與圖形學學報,2013, 25(5):679-685.

Wang Wenke, Li Sikun. B-spline Surface Fitting to Unorganized Curves[J].Journal of Computer-Aided Design & Computer Graphic, 2013, 25(5):679-685.

[11]劉俊,王啟富,陳立平,等.B樣條曲線曲面的二階預測壓縮算法[J].中國機械工程,2008,19 (3):304-307.

Liu Jun,Wang Qifu,Chen Liping,et al. Compression of B-spline Based on Local Coordinate Second-order Prediction[J]. China Mechanical Engineering, 2008, 19(3):304-307.

[12]何麗輝.反求工程中截面點云數據的預處理[J].鞍山師范學院學報, 2012,14(6):53-56.

He Lihui.Pre-process of Reversing Section Point Cloud Data in Engineering[J]. Journal of Anshan Normal University, 2012, 14(6):53-56.

[13]Zhou K, Wang G J, Jin H Z, et al. NURBS Interpolation Based on Exponential Smoothing Forecasting[J]. Int. J. Adv. Manuf. Technol., 2008, 39:1190-1196.

[14]Les P, Wayne T. 非均勻有理B樣條[M].2版.趙罡,穆國旺,王拉柱,譯.北京:清華大學出版社, 2010.

(編輯王艷麗)

B-spline Surface Fitting Algorithm Based on Contour’s Constraint Points

Jiang BenchiHan JiangTian XiaoqingXia Lian

Hefei University of Technology,Hefei,230009

Aiming at cross-sectional measured data, a B-spline surface fitting method was proposed. The original data points were denoised firstly, then vantage points of curvature were picked out and taken as the initial contour constraint points, and an initial curve interpolated with the constraint points was gained. After that, constraint points were added to the region whose fitting accuracy needed to be improved, until the B-spline curve could reach preset accuracy. Finally, subjecting to curve which contained the most constraint points, constraint points of the balance number were added to the rest of the curve, and average chord-length parameterization was conducted to construct a family of B-spline curves, and a B-spline fitting surface was obtained at last. Simulation results show that, this method can compress the number of control vertices of the surface model significantly with a high efficiency of surface reconstruction.

reverse engineering;contour’s constraint point; B-spline; curved surface fitting

2014-09-28

國家自然科學基金資助項目(51275147)

TP391.72< class="emphasis_italic">DOI

：10.3969/j.issn.1004-132X.2015.15.006

江本赤，男，1979年生。合肥工業大學機械與汽車工程學院博士研究生。主要研究方向為數控技術與裝備。發表論文10余篇。韓江，男，1963年生。合肥工業大學機械與汽車工程學院教授、博士研究生導師。田曉青，女，1987年生。合肥工業大學機械與汽車工程學院講師、博士。夏鏈(通信作者)，女，1964年生。合肥工業大學機械與汽車工程學院教授、博士。