三次样条曲线的生成算法的研究

1、三次样条曲线的生成算法本文由天空乐园河南自考网整理分享摘要三次样条函数曲线具有的最高多项式插值精度是三次多项式函数，对其进行推广构造的三次参数样条曲线应至少具有同样的插值精度。本文讨论了构造三次参数样条曲线中节点选取问题，相邻两节点之间的跨度规范化为 1，提出了构造 2GC 三次参数样条曲线的新方法。文中首先讨论了 2GC 三次参数样条曲线需满足的连续性方程，然后讨论了平面有序五点确定一组三次多项式函数曲线和平面有序六点唯一确定一条三次多项式函数曲线。 在此基础上， 提出了为给定数据点选取节点值的新方法。 新方法构造的 2GC 三次参数样条曲线具有三次多项式函数的插值精度。 最后以具体数据点对

2、新方法和已有的四种节点选取方法构造的插值曲线的精度做了比较。关键词：三次样条曲线；曲线拟合；计算机图形学自1946年美国数学家 I. J. Schoenberg 提出样条函数1以来，样条函数以其构造简单、易于计算又有很好的力学背景等特点而被广泛用于科学计算、 工程设计和计算机辅助设计等领域，成为最重要的曲线和曲面构造方法之一。在样条函数的应用中，三次样条函数由于具有极小模性质、 最佳逼近性质和很强的收敛性2,3,4等而成为最主要的方法应用于构造插值曲线和曲面。 用样条函数方法构造三次插值曲线，曲线的连续性基本可满足实际应用的要求。当曲线的端点条件确定之后，曲线的精度和形状是由曲线需满足的连续性

3、方程唯一决定的。在小挠度的情况下，插值曲线的精度和形状都是非常理想的。对大挠度曲线和任意平面数据点，则需推广三次样条函数方法构造三次参数样条曲线，此时需知道每个数据点处的参数值（节点值） 。在实际应用中，这些参数值一般是无法预先给定的，所以构造三次参数样条曲线的第一步是对给定数据点参数化，即为每个数据点指定节点值。如果指定的节点值是精确的，给定适当的端点条件，可使构造的插值曲线的代数精度达到三次参数多项式。构造三次参数样条曲线，当曲线的端点条件确定之后，能够决定曲线插值精度的量只有节点。因此构造三次参数样条曲线的关键是如何选择节点。目前常用的节点选取方法有 4种，均匀参数化法、累加弦长参数化法

4、、向心参数化法5和修正弦长参数化法6。这些方法虽然在实际中得到了较为广泛的应用，但从逼近的角度看，它们的插值精度较低，其插值多项式的最高精度是线性的。 最近一个确定节点的方法7具有二次多项式插值精度， 如果用来构造三次参数样条曲线，这个精度也是较低的。三次样条函数曲线具有的最高多项式插值精度是三次多项式函数，对其进行推广构造的三次参数样条曲线应至少具有同样的插值精度。从这一目标出发，本文讨论了构造三次参数样条曲线中节点选取问题，相邻两节点之间的跨度规范化为 1，提出了构造 2GC 三次参数样条曲线的新方法。文中首先讨论了 2GC 三次参数样条曲线需满足的连续性方程，然后讨论了平面有序五点确定一

5、组三次多项式函数曲线和平面有序六点唯一确定一条三次多项式函数曲线。 在此基础上， 提出了为给定数据点选取节点值的新方法。 新方法构造的 2GC 三次参数样条曲线具有三次多项式函数的插值精度。 最后以具体数据点对新方法和已有的四种节点选取方法构造的插值曲线的精度做了比较。平面自由曲线不能用一个标准代数方程精确表示。实际中应用很多，如轮船船身放样。将放样过程抽象为:平面上给定若干点（型值点），找一个代数方程，逼近或插值上述型值点。理论上，n个点，可以找到一个n-1次多项式来逼近，但n太大时，多项式次数太高，计算复杂，难以控制。工程上，降低次数，且分段定义。样条函数自提出以来，以其构造简单，易于计算

6、，及很好的力学背景等特点被广泛用于科学计算，工程设计和计算机辅助设计等领域，从而成为最重要的曲线和曲面构造方法之一。三次样条曲线在使用中存在局限性，且表示方法缺乏几何不变性。即当平面直角坐标系中得型值点发生旋转等几何变形时，其曲线的形状也发生变形，严重时甚至不能保证满足X1<X2<X3<Xn的条件，对表现曲线的几何形状极为不便；在使用autoCAD中spline命令绘制样条曲线时，可能导致各型值点的横坐标也不能满足X1<X2<X3<Xn的条件。为了解决这些问题，一些学者运用向心参数法在周期性三次样条曲线拟合控制多边形时，取得了很小的偏差；基于累加弦长的三次参

7、数样条曲线插值在数控系统中取得了较好的效果，但是以累加弦长为参数的三次参数样条曲线插值和基样条的函数插值在各分段曲线两端曲率的符号相同的情况下都有可能产生这段曲线上的拐点，造成曲线不光顾。因此一些准测提出检查多余的拐点，YE J等人修正了Kjellander的方法，并从累加弦长参数化和光顾函数两方面消除了三次参数样条的震荡和回折。在曲线拟合中，插值过程可具体使用线性（liner）插值，三系样条（spline）插值，立方(cubic)插值等方法，在曲线插值法中最常用的是线性插值法，它是估计2个主干点之间数值的最简单，最易实现的方法，但采用线性插值法会有以下缺点：1曲线不能显示连接主干点间的凸状弧

8、线；2从曲线导出远期曲线时会形成人为的“尖头”。因此，通常采用样条法来构造曲线，它通过构造多项式（1个或1组不同阶多项式）来形成1条把所有主干点连接起来的平滑曲线，一般常选择3次曲线（根据3次插值样条函数所得的曲线）进行拟合。3次样条曲线具有良好的数学特征，而且用3次曲线去拟合时，其结果要比线性插值估计更接近于工程实际情况，但是在工程应用中，我们利用三次样条插值方法，对相同的控制点，只可以得到1条光滑曲线，如果我们想基于相同的控制点，得到多条不同曲线，依靠传统算法，是无法实现的，这就限制了三次样条在工程中，特别是印刷领域中得应用。在印刷领域，特别市在工艺前端，传统的方法是利用曲线进行分色操作，

9、由于色彩的特殊性，即人眼对色彩的感觉不尽相同。如果只有1条色度曲线，那么工艺人员就无法对色彩效果进行有效的对比。因此印刷工艺的特殊性要求能够根据相同控制点，得出多条曲线，实现不同的印刷色彩效果，从中选出最佳的色度曲线。在这一点上，传统的方法是通过修改基本的控制点，生成新的控制曲线实行，本文提出改进的3次样条算法，实现了在相同的控制点上，生成了曲线不同的新曲线。增加了生成曲线的条数，从而使得印刷前端的工艺操作人员，对控制图像的色度曲线有更多的选择。三次参数样条曲线的构造设平面上给定了n个数据点 目标是构造一条对n个数据点插值的三次参数样条曲线 P (t)。设ti(待定)是与 iP相对应的节点，令

10、则区间上的三次参数曲线 Pi(t)可定义如下：其中为0,1区间上的三次埃尔米特基函数， 为节点ti处的切矢。 P t ()应满足的连续性方程是6,8：其中;令；则(2.2)可写成如下形式：其中；如果Si给定，则可得到(2.4)中的 Ni,i=1,2,n,由知，对i =1,2, ,n-1,(2.1)可写成如下形式：其中0s1。 显然，由(2.6)定义的样条曲线是 连续的。方程组(2.4)中有n 2方程，n个未知量,解方程组需增加两个端点条件，方法如下： (1) 对封闭或周期曲线 所以，(2) 两端点处的二阶导数为零此时，对(2.4)中的 i =2和n-1 ，相应的方程为所求方程中的未知量为(3)

11、 给定端点切向条件M1 和Mn ，其中F1和 F2的值确定将在第四节中讨论。 设，是给定数点中连续五点，与 Pj 相对应的节点是t j(待定)。为讨论方便，我们做如下变换。设不在一条直线上，把坐标变换分别施加到 Pi和 ti 。则在ovw坐标系中 的坐标为相应的节点值分别为 和其中 is 由(2.3)定义。对插值的三次参数曲线是其中；如果给定数据点是一条三次多项式函数曲线上的点，则 vi(s)和wi(s)中二次项系数之比等于三次项系数之比8，即化简得：其中 满足由于Q (s)是唯一的，从而有直接验证知，两式是等价的，并且可写成如下形式由( 3.4)知，这时一个关于 Si 的一元五次方程，用公式

12、法不能求出精确解。可用如下方法求精确解。考虑 Pk ，k=i-1,i+3，把变换(3.1)施加到 Pk ，由对称性得其中由(3.4)定义。联立(3.6)和(3.7)可求出精确解 Si 。因此平面六点可唯一定义一条三次多项式函数曲线。对边界数据点 Pi，当 3 = i ，相应于(3.7)的方程是联立 (3.6) 和 (3.8) 可求出精确解 S3对 P2 , 由 (3.4) 知，相应于 P2 的参数是所以，同理可求出。计算题可用两种方法计算 Si ：1) 对(3.6)直接用数值方法求；2) 联立(3.6)和(3.7)用公式法求。所求的 Si应满足下列条件：这样的Si可能多于一个。所以，平面有序五

13、点不能唯一决定一条三次多项式函数曲线。 确定 Si的方法是所有满足(3.9)的加权平均。 下面讨论权函数的取值。在所有中，只有一个值是所求的。考虑，如果给定数据点是三次多项式函数上的点，由(3.3)和(3.4)知，中应有一个Si,l满足如果给定数据点和 P k不是三次多项式上的点，则, 。在这种情况下，希望值小的Si,l对形成Si的影响大。为此定义Si由下式定义：显然，如果 Si,j ,满足Ei,j=0，则Si = Si,j。记(3.6)的右端为F(Si)。计算表明，在大多数情况下，F(Si)有符合(3.9)的两个实根或两个重根，如图 1所示。在图1 中，F(Si)虽然有三个实根，但左边的根不

14、符合条件(3.9)。如果(3.6)中没有满足(3.9)的Si，则选取F(Si) 在0,1区间上的极小值点(F(Si)在0,1区间上的极值点的值大于零)或极大值点(F(Si)在0,1区间上的极值点的值小于零)作为Si。例如，对图 2 所示的情况选取极大值点为Si。如果F(Si) 在0,1区间上既没有符合(3.9)的实根， 也没有符合条件的极小或极大值点，如图 3 所示，则Si的选取应极小化下式的值即，对应使(3.3)定义的两个三次参数曲线的三次项系数的差最小。 例子：本节我们以实例对新方法、累加弦长法、向心法，修正弦长法和二次精度法做比较。用于比较的数据点取自一条给定曲线。用五种方法分别对给定数

15、据点构造三次参数样条曲线，以样条曲线的插值精度对五种方法进行比较。定义数据点的曲线是其中，三次参数曲线 F(t) 具有如下性质：K = 1,2,3,4时是凸的，K = 5,6,7,8 时有两个拐点，K = 9时有一个尖点，K = 10 ,11,12 时有一个圈，图 4 是K = 3,6,9,12 时F (s)在区间0,1 上的图形。 用于比较的区间是0,1。区间被分成 20 个子区间定义数据点Pi=F(Ti) , i=0,1,2,20 ,Ti由下式定义其中00.25 。的取值使数据点相邻两弦长满足五种方法用绝对误差曲线 E(s) 比较,E(s) 定义如下其中 P(s) 表示五种方法构造的三次参

16、数样条曲线之一， F(t) 为 (5.1)或(5.3)定义的曲线， P i(s)表示 P(s)在区间Si,Si+1上的部分，|P(s)-F(t)|表示点P(s)到F(t)的距离。 (5.2)中取 = 0.25 时，五种方法产生的最大绝对误差见表 1。 表 1 五种方法对(5.1)插值产生的最大误差E(s)新方法二次精度累加弦长修正弦长向心K=19.07e-6 1.68e-53.91e-44.97e-48.07e-4K=25.08e-6 9.24e-62.23e-52.77e-41.29e-3K=31.73e-7 4.89e-62.42e-55.50e-41.87e-3K=44.73e-5 1.

17、47e-54.50e-59.40e-42.37e-3K=51.01e-4 3.88e-45.43e-51.36e-32.70e-3K=63.60e-4 6.21e-42.60e-41.68e-32.73e-3K=74.33e-4 1.64e-31.44e-31.61e-32.06e-3K=82.19e-4 3.08e-44.25e-31.07e-31.37e-3K=92.68e-4 9.34e-41.11e-34.57e-41.84e-3K=102.75e-4 4.25e-46.32e-31.93e-32.31e-3K=111.72e-4 3.83e-43.15e-33.82e-33.70e-

18、3K=121.46e-4 3.79e-41.23e-35.17e-35.55e-3下面用一个椭圆定义数据点对五种方法构造的闭合曲线进行比较。椭圆的方程是X = 3cos(2t) (5.3)Y = 2sin(2t)区间0,1也被分成 20 个小区间定义数据点。 本例中也对用精确节点值构造的三次参数插值曲线进行比较。对应于(5.2)中不同的，六种方法产生的最大绝对误差见表 2。计算知，本例中 = 0时新方法和二次精度法指定的节点都是精确的。表 2说明，对本例，新方法构造的插值曲线的精度比用精确节点构造的插值曲线的精度高。 表 2 五种方法对椭圆插值产生的最大误差E(s) 精确参数新方法二次精度累加

19、弦长修正弦长向心 =.0 7.68e-57.68e-57.68e-56.65e-41.87e-43.56e-4 =.05 1.36e-41.16e-42.08e-47.55e-43.46e-34.68e-3 =.10 2.20e-41.68e-43.85e-48.41e-47.48e-31.02e-2 =.15 3.25e-42.26e-46.03e-49.23e-41.24e-21.65e-2 =.20 4.51e-42.88e-48.62e-41.00e-31.83e-22.37e-2 =.25 6.00e-4 3.53e-41.17e-31.07e-32.50e-23.18e-2我们还把

20、区间0,1分成 30、40 等个小区间对五种方法进行比较，其结果类似于表 1和表 2。总结：在平面上唯一确定一条三次多项式函数曲线需要 6 个有序数据点。 如果给定的 6 个有序数据点是三次多项式函数F 上的点，则 6 个数据点可精确定义F 。 对平面上给定的n个数据点，本文提出了一个对其进行参数化的新方法。用指定节点构造的三次参数样条曲线是 2GC 连续的，其多项式准确集包括所有三次和小于三次的函数多项式。实例计算也表明，新方法构造的三次参数样条曲线对给定数据点，尤其是对凸的数据点，具有较高的插值精度。 继续的工作是：研究是否存在一个对数据点参数化的方法，使构造的三次参数样条曲线的多项式准确集包括所有三次和小于三次的参数多项式。 推广本文思想构造对空间数据点插值的 2GC 三次参数样条曲线。 在对叠化的编辑模型分析的基础上，针对有些非叠化区域由于物体及摄像机运动的影响，也符合叠化编辑模型的特征，利用叠化所特有的连续一致性对候选收索区域进行确认，减少了因物体及摄像机运动所产生的误检，提高了算法的查准率。同时，本算法是在检测出切变镜头边界的基础上检测叠