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

Bzeier曲线和BSpline曲线的插值拟合问题目录一、问题重述1二、Bezier曲线的插值和拟合12.1 Bezier曲线的定义12.2 Bezier曲线的性质22.3 三次Bezier曲线的插值22.3.1 工程应用中常用的三次Bezier插值的算法22.3.2 改进的三次Bezier插值的算法32.3.3 两种Bezier插值的算法比较42.4 Bezier曲线的拟合4三、BSpline曲线的插值和拟合43.1 BSpline曲线的定义43.2 B样条性质53.3 均匀B样条53.4 三次B样条插值算法63.4 结合实际情况的三次样条插值算法改进73.5 两种BSpline插值的比较8四、Bezier曲线与BSpline曲线的区别和联系8五、上述算法在实际血管提取中的应用9一、问题重述在图像中任意点两个点，软件能自动提取出以这两点为端点的一段血管，要求提取到的血管必须经过客户所点的两点作为提取血管的两个端点。在OnGetEdge()的函数里，首先通过自动增长获取血管两条边缘的采样点数据，接下来的问题就是要拟合这些采样点，生成两条比较光滑的血管边缘曲线。得到的拟合（插值）曲线有以下4点要求：1、精确插入客户所点的起始点终点，作为曲线的两个端点；2、拟合的曲线具有较好的光滑性3、具有较高的拟合精度和较快的拟合速度4、要求拟合曲线点八连通上述的实际问题转化为有序离散点的插值拟合问题。所谓插值拟合，就是通过诸如采样、实验等方法获得若干离散的数据，根据这些数据，得到一个连续的函数（也就是曲线）或者更加密集的离散方程与已知数据相吻合。这个过程叫做拟合。插值是曲线必须通过已知点的拟合。常用的插值方法有拉格朗日插值、牛顿插值、埃尔米特插值、样条函数插值等。其中，样条插值可以使用低阶多项式样条实现较小的插值误差，这样就避免了使用高阶多项式所出现的龙格现象，所以样条插值得到了流行。三次B样条插值不仅运行速度较快，而且因为其分段连续带来的特有的卓越的性能，有效提高了血管边缘的平滑程度，锯齿状的现象大大减少。本文接下来将主要介绍Bezier曲线和B样条的插值拟合。二、Bezier曲线的插值和拟合2.1 Bezier曲线的定义【定义1】n次Bezier曲线是由n+1个控制点和以Bernstein多项式为基底共同生成的参数曲线，其数学表达式为：，其中，为控制点，为Bernstein基。Fig.1是一条三次的Bezier曲线，有四个控制点。工程应用上常使用二次或三次Bezier曲线做采样点的插值拟合以及制图设计。Fig.1 三次Bezier曲线2.2 Bezier曲线的性质1、插值于两个端点，即Berize曲线开始于并结束于。2、Bezier曲线的起始点（结束点）相切于控制多边形（控制点以此首位连接所形成的封闭的多边形）的第一节（最后一节），即。3、Bezier曲线是直线的充分必要条件是控制点共线。2.3 三次Bezier曲线的插值插值要求得到的曲线精确的通过采样点，四个控制点决定一条Bezier曲线，插值M个点(M4)设计到曲线拼接连续性的问题，要求达到切线连续。2.3.1 工程应用中常用的三次Bezier插值的算法三次Bezier曲线的数学表达是为：Fig.2 三次Bezier曲线的结构【算法一】Step 1：已知采样点，两端各自增加一个虚拟控制点，分别求出的中点。Step 2：分别求出的中点。Step 3：将沿着的方向移到，对应的移到。Step 4：保持点不变收缩线段到，且。记为，为。Step 5：分别以为4个控制点按照（1）式画出一条三次的Bezier曲线，得到的Bezier曲线插值于每一个采样点，且分片一次连续。Fig.3 算法一的示意图2.3.2 改进的三次Bezier插值的算法由于采样点本身就存在着误差和噪音等诸多因素的影响，插值于每一个采样点得到的Bezier曲线不一定能完全反映真实的数据情况。所以不要求精确的插值每一个采样点。改进的算法步骤如下：【算法二】Step 1：已知采样点，分别求出的中点。Step 2：依次以分别画出一条三次的Bezier曲线。依次下去，若剩下的点不足四个控制点，则添加相同的虚拟点，直至满足四个点画一条Bezier曲线，这样得到的Bezier曲线精确的插值与两个端点及部分中间点，且分片一次连续。Fig.4 算法二的示意图2.3.3 两种Bezier插值的算法比较1）两种算法都精确插值了两端端点，且都是分片一次连续的。2）算法一精确插入了每一个采样点，算法二精确插入了接近一半的采样点及采样点的中点。在采样误差较大的情况下，算法二对算法一的改进也不是很大。3）整体来说，算法二比算法一的计算量要少，更易理解，也更能贴近实际数据。4）在实际数据有很大尖点的情况下，由于算法二不是点点插值，可能拟合不好，不能拟合出尖点的情况，理论上减少分段长度可以避免这种情况。2.4 Bezier曲线的拟合拟合不要求曲线通过每一个采样点，只要求曲线“很接近”采样点就行。“很接近”的评价标准常为最小平法逼近。拟合的一般步骤：设采样点为，拟合的Bezier曲线为Step 1： 将参数化到0,1区间上的值，即求，。常采用弦长参数法Step 2： 对每一段三次的Bezier曲线，有最小，需要求每一段Bezier曲线的控制点。按照这种算法需要反求控制顶点，随着数据采集量的增大，计算量成倍增长，且反求控制点的矩阵若为病态矩阵，则求解更耗时间，拟合的结果也不尽人意。三、BSpline曲线的插值和拟合3.1 BSpline曲线的定义【定义2】给定个节点，分布在区间，满足：。一个次B样条定义为。其中，为控制点，为B样条基函数，定义为：当节点等距时，称B样条为均匀节点样条。Fig.5 B样条基的递推定义3.2 B样条性质1、样条基函数的次数与控制顶点数无关。2、【定义2】中的BSpline曲线是分段连续的，每一段都是一条n次的曲线，共有段曲线，且曲线之间是次连续的。3、控制点的移动对样条曲线的影响是局部的。3.3 均匀B样条当B样条是均匀的时候，对于给定的n，每个B样条基是其他样条基的平移拷贝而已。对于三次均匀B样条，由上述定义的B样条曲线是分段连续的曲线，每一段的性质都是相同的，将B样条基转化为多项式函数的基，得到每一段曲线的矩阵表示形式：Fig.6 均匀三次B样条示意图3.4 三次B样条插值算法下面介绍三次B样条插值的算法。【算法三】已知型值点（采样点）共n+1个，确定B样条曲线控制点的个数有m+1个，记为，则分段B样条的个数为m-2条，记为：。Step 1：将弦长参数化到区间0,1。记，则有：，记型值点数组。Step 2：对每一段三次B样条曲线，记录该段曲线在型值点数组中的始末位置，设为， 。Step 3：将每一段B样条曲线的型值点弦长参数化到0,1区间，记为。Step 4：记系数矩阵，由以及（2）式，求出系数矩阵。记： 则 为稀疏矩阵。Step 5：记，由，即可反求出控制点。即。（这里为矩阵的广义逆，可直接调用矩阵类的方法）Step 6：根据每一段的控制顶点，拟合出一条三次的B样条曲线。即：算法特点：插值于每一个型值点3.4 结合实际情况的三次样条插值算法改进算法三中，系数矩阵A虽然是稀疏的，但是如果矩阵维数很庞大，求解矩阵的逆将会非常耗时间，造成用户体验差，又因为采样点的不精确性，所以要求插值于每一个型值点并不是很合理，故提出改进的方法，即可直接以型值点（采样点）作为三次B样条曲线的控制顶点，避免了反求控制点带来的庞大的计算量。【算法四】已知型值点共n+1个，为了生成的B样条曲线经过两个端点，还得在两个端点外分别加入一个虚拟点，记为。这样分段B样条的个数为n条，记为：Step 1： 记Step 2：根据每一段的控制顶点，拟合出一条三次的B样条曲线。即：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中，可以看出：四种算法都插值于端点。算法一、三更多的插值采样点，而算法二、四只是贴近于原始采样点，更符合实际应用。而对