基于曲率分析的三次Bezier曲線采樣方法的研究

張 嫻，張志毅，田素壘，陳 敏

西北農林科技大學 信息工程學院，陜西 楊凌 712100

基于曲率分析的三次Bezier曲線采樣方法的研究

張 嫻，張志毅，田素壘，陳 敏

西北農林科技大學 信息工程學院，陜西 楊凌 712100

1 引言

在圖形圖像處理，逆向工程等應用中，對無序散列點進行三維重建一直是研究的熱點問題。這個問題可歸納成以下三個部分：在三維空間中對物體進行采樣得到數據點集；根據這些數據點建立物體模型；利用插入算法調整模型逼近于數據點，盡可能使模型和真實數據點之間的誤差逼近于零。其中，數據點采樣決定著整個建模的優劣。然而當前的采樣標準制定困難，很難總結成公式或是一套定理，現有的大多數重建算法忽略了這個問題。如果數據采樣不當，則重建算法有可能產生失真。常見的失真出現于模型的邊緣范圍，可以人工增加一些數據信息，或是調整模型來消除這種失真現象。有一些失真情況是在數據采樣時，采樣密度沒有科學依據，會出現在曲線變化均勻的情況下在低曲率附近選取很多不必要的數據點，從而造成數據量變多，更使得重建算法計算量變大，這也是現今建模中常見的問題之一。對于重建算法中出現的這些問題，Nina Amenta[1-2]和M.Gopi[3]等人提出了一些采樣標準，但是都沒有具體算法步驟。因此，針對上述這些情況，提出一種具體而有效的采樣方法顯得極為重要。

本文在總結前人研究的基礎上，提出一種基于曲率分析的三次Bezier曲線采樣方法。該方法首先對掃描數據點進行三次Bezier曲線擬合，獲取三次Bezier曲線的特征點，在特征點處分割曲線并對曲線做曲率分析（即找出曲線上的曲率極大值），最后對數據點采樣。

2 前期工作

2.1 擬合曲線

在獲取到掃描的數據點之后，根據LesA.Piegl[4]和WayneTiller[4]提出算法對數據點整理擬合成曲線表達。擬合的曲線表達是采用的三次Bezier曲線[5]的定義式來實現。

2.2 三次Bezier曲線特征點

特征點，定義為拐點和奇異點[6-7]兩種情況。拐點和奇異點存在的條件都是曲線的曲率為零。由曲率定義式可知，為零的情況只有定義式的分子為零，分子為零有以下兩種情況：曲線的一階導數和二階導數的叉乘為零，或者是曲線的一階導數為零并且二階導數不為零。這樣，當叉乘為零時，得到的點稱之為拐點。當屬于第二種情況時，得到的點稱之為奇異點。針對這兩種情況推導出曲線的特征點的公式。

三次Bezier曲線的定義式如下：

其中，Pi為Bezier曲線的控制點。

當曲線位于XY平面上時，曲率可表示為：

設定：

根據計算機輔助幾何設計（CAGD）理論，可以滿足C′(t)×C"(t)=0的參數t所對應的點C(t)是曲線的拐點。對于矢量C′(t)和C"(t)，可能引起其叉積為零的可能性有以下兩種情況：

當C′(t)×C"(t)=0并且C′(t)≠0時，可以得到k(t)=0。此時在t兩側且無限接近t處對應的兩個矢量C′(t-)×C"(t-) 與C′(t+)×C"(t+)相對于C′(t)來說應具有相反指向，所以此時的點C(t)被稱為非奇異拐點。

當C′(t)×C"(t)=0并且C′(t)=0時，可以得到k(t)=0/0,這將導致人們無法計算此點處的曲率。根據C′(t)具有連續性可知，此時的C′(t-)與C′(t+)相對于曲線來說應具有相反指向。一般地，滿足C′(t)=0的點被稱為曲線的奇異點。奇異點是一種特殊的拐點。

左邊的園里，雕塑著熊貓，兩個大熊貓在長著山蔥的草坪上玩耍，悠閑自得。梅花鹿在那顆沙果樹的根部矗立著，很難讓人發現，只有在八九月份，人們摘不到樹上的沙果時，他才被用上。

設定：

則拐點相對應的參數t表示如公式（6）所示：

當C′(t)=0時，可推出奇異點對所應的參數t如公式（7）所示：

由公式（6）和（7）中，計算特征點的參數值t，最后代入公式（1）中求出特征點的坐標值。

2.3 數據點采樣

在本節中，采樣過程可概括為三個部分：在特征點處分割曲線；曲率分析；數據點采樣。為了確保每一段曲線中不存在特征點的情況，在采樣之前，必須在特征點處分割曲線。在分割的基礎上，對每一段曲線做曲率分析，獲取每一段曲線的曲率的極大值，即曲率半徑的極小值。分割后的曲線曲率變化可歸納為四種情況及每種情況的判斷條件如表1所示。

2.3.1 曲線分割

本節里，利用de Casteljau[8]分割遞推算法對曲線分割。de Casteljau遞推計算公式表示如下：

對于三次Bezier曲線，只需求(P10，P11，P21，P02，P12)。分割后曲線的控制點變為[P0，P10，P02，Q(t)]和[Q(t)，P12，P21，P3]，這里Q(t)為特征點坐標，P0，P3為Bezier曲線的首末控制點。

如表1所示，在分割后曲線曲率變化只有四種情況。每一種情況有不同的判斷條件。這里，定義曲線首末兩端的參數值分別為t0和t1,t2為t0和t1的中間值，具體判斷如下。

根據曲率和曲率導數的定義式，首先計算出首末端點和中間點的曲率和曲率導數分別為k(t0),k(t1),k(t2)和k′(t0), k′(t1),k′(t2)。詳細如表1所示。

表1 曲線曲率變化情況判斷

通過上述條件，可判斷曲線曲率變化屬于哪一種情況，當屬于第一種或第二種或第四種情況時，曲率的極大值位于端點處。其中第三種情況包括兩種類型：曲率由大變小再變大；曲率由小變大再變小；如果屬于第一種類型，運用表1中的判斷條件直接算出曲率極大值，如果屬于第二種類型，運用二分法計算出曲率極大值。

2.3.3 采樣

采樣密度（間隔）取決于曲率半徑的極小值。如果采樣的圖形只有一條輪廓，則采樣密度為每一段曲線長度除以曲率半徑的值和該段曲線長度開平方的值相比較下的最小值（這里所說的曲線是每四個控制點控制的一段曲線）；如果是多層輪廓，則采樣的密度為曲率半徑的極小值和輪廓間的距離相比較下的最小值。采樣原則詳細如下。

（1）數據為多層輪廓時

設采樣密度為d，采樣點數為N，每四個控制點控制的曲線段長度為length，該段曲率半徑為r，輪廓之間的距離為l，則d=min(r，l)。采樣點個數N=length/d，參數值t的變化間隔t=t+1/N。

（2）數據為一層輪廓時

采樣具體算法如下：

輸入：

根據如上算法，針對不同情況計算出曲線參數值t的變化率后，t在0到1之前取值，變化率為1 N，代入三次Bezier曲線的表達式，計算出曲線采樣點坐標值。

3 算法概述

根據前面幾節內容，采樣算法可分為如下幾個步驟：

步驟1對原始數據進行三次Bezier曲線擬合，擬合誤差自由選定。

步驟2對每一段三次Bezier曲線，執行特征點算法，求出曲線特征點。

步驟3運用de Casteljau分割遞推算法在特征點處對三次Bezier曲線分割。

步驟4對分割后的每一段曲線進行曲率分析，求出每一段曲線的曲率極大值。

步驟5根據2.3節中提出的采樣標準進行數據點采樣。

4 實驗結果

實驗結果為均勻三次分段Bezier周期曲線，三次分段Bezier非周期曲線兩種類型。圖1～圖3分別表示非均勻節點矢量和均勻節點矢量下對數據擬合后采樣的結果，圖1和圖2的數據來源于儀器掃描獲取的山體數據，圖3的數據來源于軟件中通過自由點擊鼠標獲取控制點從而擬合成曲線。圖1，2中的（a），（b）分別表示原始數據和數據采樣后的結果顯示。圖3中的（a），（b）分別表示三次非周期Bezier曲線和數據采樣后的結果顯示。表2顯示了圖1到圖3中數據點數和采樣后數據點數的對比。

（1）均勻三次分段Bezier周期曲線

圖1 均勻三次分段Bezier周期曲線的采樣結果

圖2 均勻三次周期Bezier曲線的采樣結果

（2）均勻三次分段Bezier非周期曲線

圖3 均勻三次分段Bezier非周期曲線的采樣結果

表2 圖1到圖3中原始數據點數和采樣后點數對比

5 結論

本文在分析三次Bezier曲線曲率的基礎上，提出了一種基于曲率分析的三次Bezier曲線采樣方法。結合三次Bezier曲線形狀特征點的算法，給出一種針對三維數據建

模中數據點采樣的標準。實驗結果表明該算法在數據量大的情況下采樣得到的少數點完全可以表達出原圖形，并且達到數據量少的要求。

[1]Amenta N，Bern M.Surface reconstruction by Voronoi filtering[C]//ACM Symposium on Computational Geometry.New York：ACM，1998：39-48.

[2]Amenta N，Bern M，Kamvysselis M.A new Voronoi-based surface reconstruction algorithm[C]//Proceedings ofACM SIGGRAPH.New York：ACM，1998：415-421.

[3]Gopi M，Krishnan S，Silva C T.Surface reconstruction based on lowerdimensionallocalized Delaunay triangulation[J]. Computer Graphics Forum，2000，19（3）：467-478.

[4]Piegl L，Tiller W.Surface approximation to scanned data[J]. The Visual Computer，2000，16（7）：386-395.

[5]Piegl L，Tiller W.The NURBS book[M].2nd ed.New York：Springer，1997：8-15.

[6]Zhang Zhiyi，Zhang Xian，Tian Sulei，et al.Extract shape characteristic points from cubic B-spline curve by segmented cubic Bezier curve[C]//The International Conference on Multimedia Technology.Ningbo，China：[s.n.]，2010，2：768-773.

[7]Zhang Zhiyi，Chen Min，Zhang Xian，et al.Analysis of inflection pointsforplanarcubic Beziercurve[C]//International Conference on Computational Intelligence and Software Engineering.Wuhan：[s.n.]，2009：456-461.

[8]Farin G.Curves and surfaces for computer aided geometric design-a practicalguide[M].4th ed.[S.l.]：Academic Press，1997：53-59.

ZHANG Xian,ZHANG Zhiyi,TIAN Sulei,CHEN Min

College of Information Engineering,Northwest A&F University,Yangling,Shaanxi 712100,China

In order to eliminate the shortcomings of large volumes data in three-dimensional modeling process,a fast and efficient sampling method based on curvature analysis of cubic Bezier curve is presented.In the method,the characteristic points and curvature maximum value of cubic Bezier curve are used as the reference standard of the sampling interval and density,the sampling of curve includes contours and single contour.For contours,the correlative factors are characteristic points,curvature minimum value of cubic Bezier curve,the interval between contours,and the length of curve.And for the single contours,the correlative factors are characteristic points,curvature minimum value of cubic Bezier curve and the length of curve.According to these factors,it calculates the number of sampling data.Some typical experimental results show that this method is feasible and effective for the sampling of 3D modeling.

cubic Bezier curve;characteristic points;curvature analysis;sampling

針對三維建模過程中數據量大的缺點，提出一種簡單的基于曲率分析的三次Bezier曲線采樣方法。該方法采用每個分段的三次Bezier曲線的特征點和該段曲率半徑的極小值作為采樣密度的判斷標準，曲線采樣主要分為多層輪廓和單一輪廓兩種情況，對于多層輪廓，采樣密度涉及到的因素有曲線特征點，曲率半徑極小值，輪廓之間的間距，曲線的長度。而對于單一輪廓，采樣密度涉及到的因素有曲線特征點，曲率半徑極小值，曲線的長度。通過以上因素，計算出采樣點的數目。實驗結果證明，提出的方法可行有效，可用于三維建模的數據點采樣。

三次Bezier曲線；特征點；曲率分析；采樣

A

TP391.41

10.3778/j.issn.1002-8331.1108-0451

ZHANG Xian,ZHANG Zhiyi,TIAN Sulei,et al.Sampling method based on curvature analysis of cubic Bezier curve. Computer Engineering and Applications,2013,49（5）：160-162.

教育部留學回國人員科研啟動費（No.K314020901）；中央高校基本科研業務費專項資金資助（No.Z109021004）。

張嫻（1987—），女，碩士研究生，研究領域：CAD/CG；張志毅（1974—），男，博士研究生，副教授，研究領域：CAD/CG；田素壘（1987—），男，碩士研究生，研究領域：CAD/CG；陳敏（1986—），女，碩士研究生，研究領域：CAD/CG。E-mail：Zhangxian-0905@163.com

2011-08-30

2011-11-09

1002-8331（2013）05-0160-03

CNKI出版日期：2011-12-09 http://www.cnki.net/kcms/detail/11.2127.TP.20111209.0959.009.html