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

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

西北農(nóng)林科技大學(xué) 信息工程學(xué)院，陜西 楊凌 712100

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

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

西北農(nóng)林科技大學(xué) 信息工程學(xué)院，陜西 楊凌 712100

1 引言

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

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

2 前期工作

2.1 擬合曲線

在獲取到掃描的數(shù)據(jù)點(diǎn)之后，根據(jù)LesA.Piegl[4]和WayneTiller[4]提出算法對數(shù)據(jù)點(diǎn)整理擬合成曲線表達(dá)。擬合的曲線表達(dá)是采用的三次Bezier曲線[5]的定義式來實(shí)現(xiàn)。

2.2 三次Bezier曲線特征點(diǎn)

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

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

其中，Pi為Bezier曲線的控制點(diǎn)。

當(dāng)曲線位于XY平面上時(shí)，曲率可表示為：

設(shè)定：

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

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

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

左邊的園里，雕塑著熊貓，兩個(gè)大熊貓?jiān)陂L著山蔥的草坪上玩耍，悠閑自得。梅花鹿在那顆沙果樹的根部矗立著，很難讓人發(fā)現(xiàn)，只有在八九月份，人們摘不到樹上的沙果時(shí)，他才被用上。

設(shè)定：

則拐點(diǎn)相對應(yīng)的參數(shù)t表示如公式（6）所示：

當(dāng)C′(t)=0時(shí)，可推出奇異點(diǎn)對所應(yīng)的參數(shù)t如公式（7）所示：

由公式（6）和（7）中，計(jì)算特征點(diǎn)的參數(shù)值t，最后代入公式（1）中求出特征點(diǎn)的坐標(biāo)值。

2.3 數(shù)據(jù)點(diǎn)采樣

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

2.3.1 曲線分割

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

對于三次Bezier曲線，只需求(P10，P11，P21，P02，P12)。分割后曲線的控制點(diǎn)變?yōu)閇P0，P10，P02，Q(t)]和[Q(t)，P12，P21，P3]，這里Q(t)為特征點(diǎn)坐標(biāo)，P0，P3為Bezier曲線的首末控制點(diǎn)。

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

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

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

通過上述條件，可判斷曲線曲率變化屬于哪一種情況，當(dāng)屬于第一種或第二種或第四種情況時(shí)，曲率的極大值位于端點(diǎn)處。其中第三種情況包括兩種類型：曲率由大變小再變大；曲率由小變大再變?。蝗绻麑儆诘谝环N類型，運(yùn)用表1中的判斷條件直接算出曲率極大值，如果屬于第二種類型，運(yùn)用二分法計(jì)算出曲率極大值。

2.3.3 采樣

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

（1）數(shù)據(jù)為多層輪廓時(shí)

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

（2）數(shù)據(jù)為一層輪廓時(shí)

采樣具體算法如下：

輸入：

根據(jù)如上算法，針對不同情況計(jì)算出曲線參數(shù)值t的變化率后，t在0到1之前取值，變化率為1 N，代入三次Bezier曲線的表達(dá)式，計(jì)算出曲線采樣點(diǎn)坐標(biāo)值。

3 算法概述

根據(jù)前面幾節(jié)內(nèi)容，采樣算法可分為如下幾個(gè)步驟：

步驟1對原始數(shù)據(jù)進(jìn)行三次Bezier曲線擬合，擬合誤差自由選定。

步驟2對每一段三次Bezier曲線，執(zhí)行特征點(diǎn)算法，求出曲線特征點(diǎn)。

步驟3運(yùn)用de Casteljau分割遞推算法在特征點(diǎn)處對三次Bezier曲線分割。

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

步驟5根據(jù)2.3節(jié)中提出的采樣標(biāo)準(zhǔn)進(jìn)行數(shù)據(jù)點(diǎn)采樣。

4 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

表2 圖1到圖3中原始數(shù)據(jù)點(diǎn)數(shù)和采樣后點(diǎn)數(shù)對比

5 結(jié)論

本文在分析三次Bezier曲線曲率的基礎(chǔ)上，提出了一種基于曲率分析的三次Bezier曲線采樣方法。結(jié)合三次Bezier曲線形狀特征點(diǎn)的算法，給出一種針對三維數(shù)據(jù)建

模中數(shù)據(jù)點(diǎn)采樣的標(biāo)準(zhǔn)。實(shí)驗(yàn)結(jié)果表明該算法在數(shù)據(jù)量大的情況下采樣得到的少數(shù)點(diǎn)完全可以表達(dá)出原圖形，并且達(dá)到數(shù)據(jù)量少的要求。

[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

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

三次Bezier曲線；特征點(diǎn)；曲率分析；采樣

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.

教育部留學(xué)回國人員科研啟動(dòng)費(fèi)（No.K314020901）；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助（No.Z109021004）。

張嫻（1987—），女，碩士研究生，研究領(lǐng)域：CAD/CG；張志毅（1974—），男，博士研究生，副教授，研究領(lǐng)域：CAD/CG；田素壘（1987—），男，碩士研究生，研究領(lǐng)域：CAD/CG；陳敏（1986—），女，碩士研究生，研究領(lǐng)域：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