Bezier曲线和BSpline曲线的拟合问题

Bzeier曲线和BSpline曲线的插值拟合问题

目录

一、问题重述 ................................................................................... 2

二、Bezier曲线的插值和拟合 ......................................................... 2

2.1 Bezier曲线的定义 .............................................................. 2

2.2 Bezier曲线的性质 .............................................................. 3

2.3 三次Bezier曲线的插值 ..................................................... 3

2.3.1 工程应用中常用的三次Bezier插值的算法 ............. 3

2.3.2 改进的三次Bezier插值的算法 ................................. 4

2.3.3 两种Bezier插值的算法比较....................................... 5

2.4 Bezier曲线的拟合 .............................................................. 5

三、BSpline曲线的插值和拟合 ....................................................... 5

3.1 BSpline曲线的定义 ............................................................ 5

3.2 B样条性质 ......................................................................... 6

3.3 均匀B样条 .......................................................................... 6

3.4 三次B样条插值算法 ........................................................... 7

3.4 结合实际情况的三次样条插值算法改进 ............................ 8

3.5 两种BSpline插值的比较 ..................................................... 8

四、Bezier曲线与BSpline曲线的区别和联系 ................................ 9

五、上述算法在实际血管提取中的应用 ......................................... 9

1

一、问题重述

在图像中任意点两个点，软件能自动提取出以这两点为端点的一段血管，要求提取到的血管必须经过客户所点的两点作为提取血管的两个端点。

在OnGetEdge()的函数里，首先通过自动增长获取血管两条边缘的采样点数据，接下来的问题就是要拟合这些采样点，生成两条比较光滑的血管边缘曲线。得到的拟合（插值）曲线有以下4点要求：

1、精确插入客户所点的起始点终点，作为曲线的两个端点；

2、拟合的曲线具有较好的光滑性

3、具有较高的拟合精度和较快的拟合速度

4、要求拟合曲线点八连通

上述的实际问题转化为有序离散点的插值拟合问题。所谓插值拟合，就是通过诸如采样、实验等方法获得若干离散的数据，根据这些数据，得到一个连续的函数（也就是曲线）或者更加密集的离散方程与已知数据相吻合。这个过程叫做拟合。插值是曲线必须通过已知点的拟合。常用的插值方法有拉格朗日插值、牛顿插值、埃尔米特插值、样条函数插值等。

其中，样条插值可以使用低阶多项式样条实现较小的插值误差，这样就避免了使用高阶多项式所出现的龙格现象，所以样条插值得到了流行。三次B样条插值不仅运行速度较快，而且因为其分段连续带来的特有的卓越的性能，有效提高了血管边缘的平滑程度，锯齿状的现象大大减少。本文接下来将主要介绍Bezier曲线和B样条的插值拟合。

二、Bezier曲线的插值和拟合

2.1 Bezier曲线的定义

【定义1】n次Bezier曲线是由n+1个控制点和以Bernstein多项式为基底共同生成

n

的参数曲线，其数学表达式为：B(t)db(t),t[0,1]，其中，d(i0,...,n)为n

iii

i0

n控制点，b(t)(1t)niti,i0,...,n为Bernstein基。

ini

Fig.1是一条三次的Bezier曲线，有四个控制点。工程应用上常使用二次或三次Bezier曲线做采样点的插值拟合以及制图设计。

Fig.1 三次Bezier曲线

2.2 Bezier曲线的性质

1、插值于两个端点，即Berize曲线开始于d0并结束于dn。 2、Bezier曲线的起始点（结束点）相切于控制多边形（控制点以此首位连接所形成的封闭的多边形）的第一节（最后一节），即B'(0)//d0d1,B'(1)//dn1dn。

3、Bezier曲线是直线的充分必要条件是控制点共线。

2.3三次Bezier曲线的插值

插值要求得到的曲线精确的通过采样点，四个控制点决定一条Bezier曲线，插值M个点(M>4)设计到曲线拼接连续性的问题，要求达到切线连续。

2.3.1 工程应用中常用的三次Bezier插值的算法

三次Bezier曲线的数学表达是为：

133332B(t)dibi(t)ttt13i01331d0d6301,t[0,1]300d2000d3(1)

Fig.2 三次Bezier曲线的结构

【算法一】

Step 1：已知采样点P0,P1,P2,...,Pn，两端各自增加一个虚拟控制点P1,Pn1，分别求出P1P0,P0P1,...,PnPn1的中点M0,M1,...,Mn1。

Step 2：分别求出M0M1,M1M2,...,MnMn1的中点D0,D1,...,Dn。 ''Step 3：将Di沿着DiPi，对应的Mi,Mi1移到Mi,Mi1。 i的方向移到P'Step 4：保持Pi点不变收缩线段Mi'Mi'1到Mi''Mi''1，且Mi'M'

i10.6M'

iMi1。记

1''2Mi''为Pi，Mi1为Pi。

21Step 5：分别以PP,...,n1为4个控制点按照（1

）式画出一条三iiPi1Pi1,i0,1

次的Bezier曲线，得到的Bezier曲线插值于每一个采样点P0,P1,P2,...,Pn，且分片一次连续。

Fig.3 算法一的示意图

2.3.2改进的三次Bezier插值的算法

由于采样点本身就存在着误差和噪音等诸多因素的影响，插值于每一个采样点得到的Bezier曲线不一定能完全反映真实的数据情况。所以不要求精确的插值每一个采样点。改进的算法步骤如下：

【算法二】

Step 1：已知采样点P0,P1,P2,...,Pn，分别求出P0P1,PP12,...,Pn1Pn的中点M1,M2,...,Mn。

Step 2：依次以P0M1PM12,M2P2M3P3,PM34P4M5,...分别画出一条三次的Bezier曲线。依次下去，若剩下的点不足四个控制点，则添加相同的虚拟点Pn1Pn，Mn1Pn，直至满足四个点画一条Bezier曲线，这样得到的Bezier曲线精确的插值与两个端点及部分中间点，且分片一次连续。

Fig.4算法二的示意图

2.3.3 两种Bezier插值的算法比较

1）两种算法都精确插值了两端端点，且都是分片一次连续的。

2）算法一精确插入了每一个采样点，算法二精确插入了接近一半的采样点及采样点的中点。在采样误差较大的情况下，算法二对算法一的改进也不是很大。

3）整体来说，算法二比算法一的计算量要少，更易理解，也更能贴近实际数据。

4）在实际数据有很大尖点的情况下，由于算法二不是点点插值，可能拟合不好，不能拟合出尖点的情况，理论上减少分段长度可以避免这种情况。

2.4 Bezier曲线的拟合

拟合不要求曲线通过每一个采样点，只要求曲线“很接近”采样点就行。“很接近”的评价标准常为最小平法逼近。拟合的一般步骤：

设采样点为P0,P1,P2,...,Pn，拟合的Bezier曲线为B(t),t[0,1]

Step 1：将P0,P1,P2,...,Pn参数化到[0,1]区间上的值，即求t0,t1,t2,...,tn，ti[0,1]。常采用弦长参数法

Step 2：对每一段三次的Bezier曲线，有

线的控制点。

按照这种算法需要反求控制顶点，随着数据采集量的增大，计算量成n2倍增长，(PB(t))iiii042最小，需要求每一段Bezier曲且反求控制点的矩阵若为病态矩阵，则求解更耗时间，拟合的结果也不尽人意。

三、BSpline曲线的插值和拟合

3.1 BSpline曲线的定义

【定义2】给定m1个节点ti，分布在[0,1]区间，满足：t0t1t2...tm。一个n次B样条定义为S(t)db(t),t[0,1]。其中，d为控制点，b(t)为B样n

iimini

i0

1tjttj1b(t):others0条基函数，定义为：ttjn1tjn1tn1bn(t):b(t)bj1(t)jjtjntjtjn1tj10j

当节点等距时，称B样条为均匀节点样条。

Fig.5 B样条基的递推定义

3.2 B样条性质

1、样条基函数的次数与控制顶点数无关。

2、【定义2】中的BSpline曲线是分段连续的，每一段都是一条n次的曲线，共有m1n段曲线，且曲线之间是n1次连续的。

3、控制点的移动对样条曲线的影响是局部的。

3.3均匀B样条

当B样条是均匀的时候，对于给定的n，每个B样条基是其他样条基的平移拷贝而已。对于三次均匀B样条，由上述定义的B样条曲线是分段连续的曲线，每一段的性质都是相同的，将B样条基转化为多项式函数的基，得到每一段曲线的矩阵表示形式：

13132Si(t)ttt1631331did630i1,fort[0,1]030di2410di3(2)

Fig.6 均匀三次B样条示意图

3.4三次B样条插值算法

下面介绍三次B样条插值的算法。

【算法三】

已知型值点（采样点）P0,P1,P2,...,Pn共n+1个，确定B样条曲线控制点的个数有m+1个，记为d0,d1,...,dm，则分段B样条的个数为m-2条，记为：S0(t),S1(t),...,Sm3(t)。 Step 1：将P0,P1,P2,...,Pn弦长参数化到区间[0,1]。记iPi1Pi,S

ji0n1i， 则有：t00,ti1Tj,i1,2,...,n，记型值点数组b[P...P0P1n]。

j0S

Step 2：对每一段三次B样条曲线Si(t)，记录该段曲线在型值点数组b中的始末位置，设为Pfirst,Pend，i0,1,...,m3。

Step 3：将每一段B样条曲线的型值点Pfirst,Pfirst1,...,Pend1,Pend弦长参数化到[0,1]区间，记为tfirst,tfirst1,...,tend1,tend(i0,1,...,m3)。

Step 4：记系数矩阵AF

求出系数矩阵A。记： (n1)(m+1)iiiiiiiiii，由Si(tfirst)Pfirst,...,Si(tend)Pend以及（2）式，iiii

11f1(t)(t33t23t1),f2(t)(3t36t24),66 11f3(t)(3t33t3t1),f4(t)t3

66

f1(t0

first)

f(t0)1end

则A000f2(tend)f3(tend)f4(tend)1111f1(tfirst)f2(tfirst)f3(tfirst)f4(tfirst)1111f1(tend)f2(tend)f3(tend)f4(tend) mmmf1(tmfirst)f2(tfirst)f3(tfirst)f4(tfirst)mmmmf1(tend)f2(tend)f3(tend)f4(tend)00f2(t0first)f3(tfirst)f4(tfirst)

A为稀疏矩阵。

1xb，Step 5：记x[d0d1...dm]T，由A即可反求出控制点d0,d1,...,dm。即xAb。

（这里A为矩阵的广义逆，可直接调用矩阵类的方法）

Step 6：根据每一段的控制顶点，拟合出一条三次的B样条曲线。

即：Si(t)1d

j03ijfj1(t),i0,1,...,m,t[0,1]

算法特点：插值于每一个型值点

3.4 结合实际情况的三次样条插值算法改进

算法三中，系数矩阵A虽然是稀疏的，但是如果矩阵维数很庞大，求解矩阵的逆将会非常耗时间，造成用户体验差，又因为采样点的不精确性，所以要求插值于每一个型值点并不是很合理，故提出改进的方法，即可直接以型值点（采样点）作为三次B样条曲线的控制顶点，避免了反求控制点带来的庞大的计算量。

【算法四】

已知型值点P0,P1,...,Pn共n+1个，为了生成的B样条曲线经过两个端点，还得在两个端点外分别加入一个虚拟点，记为P这样分段B样条的个数为n条，记为：1,Pn1。

S0(t),S1(t),...,Sn1(t)

Step 1：记P12P0P1,Pn12PnPn1

Step 2：根据每一段的控制顶点，拟合出一条三次的B样条曲线。

即：Si(t)P

j03i1jfj1(t),i0,1,...,n1,t[0,1]

Fig.7算法四结果示意图

3.5 两种BSpline插值的比较

1）两种算法都精确插值了两端端点，且都是分片二次连续的。

2）算法四比算法三的计算量要少的多，但算法三插值于每一个采样点，而算法四只插值于两个端点。

3）在采样误差大的情况下，算法四优于算法三，但如果采样比较精确，从贴近原始数据讲，则算法三比算法四好。

四、Bezier曲线与BSpline曲线的区别和联系

B样条方法是在保留Bezier方法的优点，同时克服其由于整体表示带来不具有局部性质的缺点，及解决在描述复杂形状时带来的连接问题下提出来的。在样条曲线取重节点的情况下，BSpline曲线退化成Bezier曲线。

他们的区别主要有以下4点：

1、Bezier曲线的基函数次数等于控制顶点数减1。B样条曲线基函数次数与控制顶点数无关。

2、Bezier曲线的基函数是Beinstein基函数，它是个多项式函数。B样条曲线的基函数是多项式样条。

3、Bezier曲线是一种特殊表示形式的参数多项式曲线。B样条曲线则是一种特殊表示形式的参数样条曲线。

4、Bezier曲线缺乏局部性质，即修改任意一个控制顶点都会对曲线整体产生影响。B样条曲线具有性质，即修改一个控制顶点只会对几段曲线产生影响。

五、上述算法在实际血管提取中的应用

实际证明，四种算法对原数据点的插值（拟合）效果都很好，但由实际问题提出的四点要求，且实际采样点的误差是肯定存在的，而算法四因其具有计算简单，光滑性高等特点，要优于其他的算法。

下图是在取相同的起始点，终点的情况下，四种算法插值（拟合）的结果。

Fig.8四种算法拟合血管采样点的结果

从Fig.8中，可以看出：四种算法都插值于端点。算法一、三更多的插值采样点，而算法二、四只是贴近于原始采样点，更符合实际应用。

而对于算法二和算法四，两种拟合的结果都差不多。但算法四比算法二拟合的结果要光滑些。

【结论】同时使用三次Bezier曲线和三次B样条曲线进行插值时，所得到的曲线都是分段连续的，但是Bezier曲线是分段一次连续，而样条曲线是分段二次连续，光滑性更好。对于Bezier曲线的每一段都需要4个控制点，n段就需要4n个控制点，而对于BSpline曲线，n段只需要n+3个控制点即可。所以一般情况下，更常用B样条曲线进行插值拟合。