基于曲率分析的三次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