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

1、Bzeier曲线和BSpline曲线的插值拟合问题目录一、问题重述 2二、Bezier曲线的插值和拟合 22.1 Bezier曲线的定义22.2 Bezier曲线的性质 32.3 三次Bezier曲线的插值 32.3.1工程应用中常用的三次 Bezier插值的算法 32.3.2 改进的三次Bezier插值的算法42.3.3两种Bezier插值的算法比较 52.4 Bezier曲线的拟合 5三、BSpIine曲线的插值和拟合53.1 BSpIine曲线的定义 53.2 B样条性质63.3均匀B样条63.4三次B样条插值算法73.4 结合实际情况的三次样条插值算法改进 83.5两种BSpIine插

2、值的比较 8四、Bezier曲线与BSpIine曲线的区别和联系 9五、上述算法在实际血管提取中的应用 9、问题重述在图像中任意点两个点， 软件能自动提取出以这两点为端点的一段血管，要求提取到的血管必须经过客户所点的两点作为提取血管的两个端点。在OnGetEdge（）的函数里，首先通过自动增长获取血管两条边缘的采样点数据，接 下来的问题就是要拟合这些采样点，生成两条比较光滑的血管边缘曲线。得到的拟合（插值）曲线有以下4点要求：1、精确插入客户所点的起始点终点，作为曲线的两个端点；2、拟合的曲线具有较好的光滑性3、具有较高的拟合精度和较快的拟合速度4、要求拟合曲线点八连通上述的实际问题转化为有序

3、离散点的插值拟合问题。所谓插值拟合，就是通过诸如采样、实验等方法获得若干离散的数据，根据这些数据，得到一个连续的函数（也就是曲线）或者更加密集的离散方程与已知数据相吻合。这个过程叫做拟合。插值是曲线必须通过已知点的拟合。常用的插值方法有拉格朗日插值、牛顿插值、埃尔米特插值、样条函数插值等。其中，样条插值可以使用低阶多项式样条实现较小的插值误差，这样就避免了使用高阶多项式所出现的龙格现象，所以样条插值得到了流行。 三次B样条插值不仅运行速度较快，而且因为其分段连续带来的特有的卓越的性能，有效提高了血管边缘的平滑程度，锯齿状的现象大大减少。本文接下来将主要介绍Bezier曲线和B样条的插值拟合。B

4、ezier曲线的插值和拟合2.1 Bezier曲线的定义【定义1】n次Bezier曲线是由n+1个控制点和以Bernstein多项式为基底共同生成的参数曲线，其数学表达式为：nB(t dibin(t), t 0,1，其中，di(i=0,.,n)为i=0n控制点，bin (t )= . (1-t)r, i =0,.,n 为 Bernstein 基。Fig.1是一条三次的Bezier曲线，有四个控制点。工程应用上常使用二次或三次Bezier曲线做采样点的插值拟合以及制图设计。PlFig.1三次Bezier曲线2.2 Bezier曲线的性质1、 插值于两个端点，即Berize曲线开始于d0并结束于d

5、n。2、Bezier曲线的起始点（结束点）相切于控制多边形（控制点以此首位连接所形成的封闭的多边形）的第一节（最后一节） ，即B'（0） /d0d, B'（1）/dn_（dn。3、Bezier曲线是直线的充分必要条件是控制点共线。2.3三次Bezier曲线的插值插值要求得到的曲线精确的通过采样点，四个控制点决定一条 Bezier曲线，插值M个点（M>4）设计到曲线拼接连续性的问题，要求达到切线连续。2.3.1工程应用中常用的三次 Bezier插值的算法三次Bezier曲线的数学表达是为:33 32B(t)db (t) |t t ti =0-1 3 -3n 3 -631 I

6、-3 3 0J001 ldold1 ,“0,1d2(1)0_d3Fig.2三次Bezier曲线的结构【算法一】P，Pn1，分别Step 1 ：已知采样点P0,R,P2,.,P，两端各自增加一个虚拟控制点求出PPnAP,巳巳十的中点M°,M1,.,Mn十。Step 2：分别求出 MoMjMMz'.rMnMn 4 的中点 D0,D1,.,Dn。Step 3：将Di沿着DiR的方向移到P，对应的Mi, M i 1移到M ；, M ；计。IItHHIIIIStep 4：保持P点不变收缩线段 MjM"到MjMr，且Mj M“ =0.6M 。记 Mj 为 P1，MiHr为 P2

7、。2 1Step 5：分别以PR PP十,i =0,1,., n1为4个控制点按照（1）式画出一条三次的Bezier曲线，得到的Bezier曲线插值于每一个采样点P0,R,P2,.,Fn，且分片一次连续。2.3.2改进的三次Bezier插值的算法由于采样点本身就存在着误差和噪音等诸多因素的影响， 插值于每一个采样点得到 的Bezier曲线不一定能完全反映真实的数据情况。 所以不要求精确的插值每一个采样点。 改进的算法步骤如下：【算法二】Step 1 :已知采样点P0, R,Pn ，分别求出F0R , RP2 ,Pn/Pn的中点M1, M2,., Mn。Step 2：依次以 P0M1P1M 2,

8、 M2P2M3F3, F3M 4P4M5,.分别画出一条三次的 Bezier曲线。依次下去，若剩下的点不足四个控制点，则添加相同的虚拟点Pn仃Pn ,Mn1，直至满足四个点画一条Bezier曲线，这样得到的Bezier曲线精确的插值与两个端点及部分中间点，且分片一次连续。233两种Bezier插值的算法比较1) 两种算法都精确插值了两端端点，且都是分片一次连续的。2) 算法一精确插入了每一个采样点，算法二精确插入了接近一半的采样点及采样点的 中点。在采样误差较大的情况下，算法二对算法一的改进也不是很大。3) 整体来说，算法二比算法一的计算量要少，更易理解，也更能贴近实际数据。4) 在实际数据有

9、很大尖点的情况下，由于算法二不是点点插值，可能拟合不好，不能 拟合出尖点的情况，理论上减少分段长度可以避免这种情况。2.4 Bezier曲线的拟合拟合不要求曲线通过每一个采样点，只要求曲线“很接近”采样点就行。“很接近”的评价标准常为最小平法逼近。拟合的一般步骤：设采样点为P0,R, P2Pn，拟合的Bezier曲线为B(t),t 0,1Step 1： 将 P0,R,P2,.,Pn参数化到0,1区间上的值，即求 t0,t1,t2,.,tn，t 0,1。常采用弦长参数法4Step 2：对每一段三次的 Bezier曲线，有(R - B©)2最小，需要求每一段 Bezier曲 i=0线的控

10、制点。2按照这种算法需要反求控制顶点，随着数据采集量的增大，计算量成n倍增长，且反求控制点的矩阵若为病态矩阵，则求解更耗时间，拟合的结果也不尽人意。三、BSpline曲线的插值和拟合3.1 BSpline曲线的定义【定义2】给定m 1个节点ti，分布在0,1区间，满足：t0 : 1 ： t2 : . ： tm。m一个n次B样条定义为S(t)djbjn(t) t 0,1。其中，di为控制点，bjn(t)为B样i =0条基函数，定义为：1 t £t < t *-0"、Lj 7 7j 十bj(t):=卫othersbjn(t)=j 町讪+ 血b：(t)tj4ntjtj_t

11、j-h当节点等距时，称 B样条为均匀节点样条。Fig.5 B样条基的递推定义3.2 B样条性质1、样条基函数的次数与控制顶点数无关。2、 【定义2】中的BSpline曲线是分段连续的，每一段都是一条n次的曲线，共有 m- n段曲线，且曲线之间是 n-1次连续的。3、控制点的移动对样条曲线的影响是局部的。3.3均匀B样条n,每个B样条基是其他样条基的平移拷贝而已。当B样条是均匀的时候，对于给定的 对于三次均匀 是相同的，将S(t) = t3 t2-312【drdi.di 七一,for t 0,1(2)B样条，由上述定义的 B样条曲线是分段连续的曲线，每一段的性质都 B样条基转化为多项式函数的基，

12、得到每一段曲线的矩阵表示形式：2即起点在AV V.VJ边V" 的中线，禺Vi点1曲处PU)r即终点在AV.V.V,底边中线.离 X点旧处Fig.6均匀三次B样条示意图3.4三次B样条插值算法F面介绍三次B样条插值的算法。【算法三】已知型值点(采样点)P0,R,P2,.,Pn共n+1个，确定B样条曲线控制点的个数有 m+1个，记为d°,di,，dm，则分段B样条的个数为m-2条，记为：So(t),Si(t),，Sm,(t)。nVStep 1：将 P0, R, P2,., Pn 弦长参数化到区间0,1。记A j = P半一 P，S=£ 也j，7j 1则有：鮎=0

13、63; =送一也j,i =1,2,.,n，记型值点数组R . PJT。 j =0 SStep 2:对每一段三次 B样条曲线S(t)，记录该段曲线在型值点数组b中的始末位置，设为 P；rst，Rnd，i =0,1，,m -3。Step 3 :将每一段B样条曲线的型值点PL,Pfirst,.,Peind_1,Peind弦长参数化到0,1区间，记为 t first , tfirst 行，tend,tend (i = 0,1,，m - 3)。Step 4：记系数矩阵 A F(n1) (m+1)，由 S (tfirst )= P；irst，,S (t；nd)二 Pnd 以及(2)式,求出系数矩阵A。记：

14、132132f1(t)( -t33t2 -3t 1), f2(t)(3t3 -6t24),6 61 3 1 3 f3(t)(-3t3 3t 3t 1),f4(t) t36 6f1(fst)f2(fst)f3(fst)f4(t：rst)Md)f2(t：d) f3(t：d)f4(t：d)f1 (t first )af2(t first )f3 (t first )af4(t first )af1(te0nd)f2(t0nd)f3(t!nd)f4(t0nd)1 f1 (t first )91 f2(tfirst )a1f3 (t first )91t(tend)1f2(tend )1f3 (tend

15、 )1f4(tend)1f4(tfirst )A为稀疏矩阵。Step 5：记 x=d0 d1 . dmT，由 A b ，即可反求出控制点 d0,d1,.,dm。即 x =A b1(这里AJ为矩阵的广义逆，可直接调用矩阵类的方法)Step 6:根据每一段的控制顶点，拟合出一条三次的B样条曲线。3即: S(tZ dqfj/t),i =0,1,.,m, t0,1j=0算法特点：插值于每一个型值点3.4结合实际情况的三次样条插值算法改进算法三中，系数矩阵A虽然是稀疏的，但是如果矩阵维数很庞大，求解矩阵的逆将会非常耗时间，造成用户体验差，又因为采样点的不精确性，所以要求插值于每一个 型值点并不是很合理，

16、故提出改进的方法，即可直接以型值点(采样点)作为三次B样条曲线的控制顶点，避免了反求控制点带来的庞大的计算量。【算法四】已知型值点 丘，只,.，尺共n+1个，为了生成的 B样条曲线经过两个端点，还得在两个端点外分别加入一个虚拟点，记为P_J, R 4。这样分段B样条的个数为n条，记为：S0(t),S(t),.,Sn(t)Step 1：记 P=2F0 R, Pn卅=2R RdStep 2：根据每一段的控制顶点，拟合出一条三次的B样条曲线。3即: S(t)=2： P话fj卅(t), i =0,1,.,n-1,"0,1j =03.5两种BSpline插值的比较1) 两种算法都精确插值了两端

17、端点，且都是分片二次连续的。2) 算法四比算法三的计算量要少的多，但算法三插值于每一个采样点，而算法四只插 值于两个端点。3) 在采样误差大的情况下，算法四优于算法三，但如果采样比较精确，从贴近原始数 据讲，则算法三比算法四好。四、Bezier 曲线与 BSpline 曲线的区别和联系B 样条方法是在保留 Bezier 方法的优点， 同时克服其由于整体表示带来不具有局部性质 的缺点， 及解决在描述复杂形状时带来的连接问题下提出来的。 在样条曲线取重节点的情况 下， BSpline 曲线退化成 Bezier 曲线。他们的区别主要有以下 4 点：1、Bezier曲线的基函数次数等于控制顶点数减 1

18、。B样条曲线基函数次数与控制顶点数 无关。2、Bezier 曲线的基函数是 Beinstein 基函数，它是个多项式函数。 B 样条曲线的基函数 是多项式样条。3、 Bezier 曲线是一种特殊表示形式的参数多项式曲线。B 样条曲线则是一种特殊表示 形式的参数样条曲线。4、 Bezier 曲线缺乏局部性质，即修改任意一个控制顶点都会对曲线整体产生影响。B 样条曲线具有性质，即修改一个控制顶点只会对几段曲线产生影响。五、上述算法在实际血管提取中的应用实际证明， 四种算法对原数据点的插值（拟合）效果都很好， 但由实际问题提出的四点 要求，且实际采样点的误差是肯定存在的，而算法四因其具有计算简单，光滑性高等特点， 要优于其他的算法。下图是在取相同的起始点，终点的情况下，四种算法插值（拟合）的结果。Si 去二.改进的 Bezier 畀法一I Hezier插值笄法四，克进的BSpfcr播值jj法三BSpliiff插佢Fig.8四种算