B-spline反求控制顶点

 
B样条曲线拟合时（https://blog.csdn.net/hanmingjunv5/article/details/106137002），曲线是不通过数据点的，这样对于曲线的插补来说，是不合理的。因此，需要根据给定的数据点来求解控制顶点，使拟合的曲线通过全部数据点。

 

推导

曲线定义：
$$C(u)=\sum _{i=0}^n{N}_{i,p}(u)P_i(1)$$
B-Spline曲线存在n+1个位置的控制顶点。

将每个控制顶点的基函数写成矩阵形式如下：
 
$$N=\left[\begin{array}{ccccc}{N}_{0,p}(t_0)& N_{1,p}(t_0)& N_{2,p}(t_0)& \cdots & N_{n,p}(t_0)\\ N_{0,p}(t_1)& N_{1,p}(t_1)& N_{2,p}(t_1)& \cdots & N_{n,p}(t_1)\\ & \cdots & & & \\ N_{0,p}(t_n)& N_{1,p}(t_n)& N_{2,p}(t_n)& \cdots & N_{n,p}(t_n)\end{array}\right]$$

 
控制顶点写成矩阵形式如下：
 
$$P=\left[\begin{array}{ccccc}p(01)& p(02)& p(03)& \cdots & p(0s)\\ p(11)& p(12)& p(13)& \cdots & p(1s)\\ & \cdots & & & \\ p(n1)& p(n2)& p(n3)& \cdots & p(ns)\end{array}\right]$$

s为点位数据的维度，例如3D数据，s=3

数据点写成矩阵形式如下：
 
$$C=\left[\begin{array}{ccccc}c(01)& c(02)& c(03)& \cdots & c(0s)\\ c(11)& c(12)& c(13)& \cdots & c(1s)\\ & \cdots & & & \\ c(n1)& c(n2)& c(n3)& \cdots & c(ns)\end{array}\right]$$
则式子(1)可以写成如下形式：
$$\begin{gathered} \mathbf{C}=\mathbf{N}\ast \mathbf{P} \\ 因此： \\ \mathbf{P}={\mathbf{N}}^{-1}\ast \mathbf{C} \end{gathered}$$
即可求解控制顶点P。
 

求解基函数系数矩阵

使用de-boor算法计算基函数系数矩阵，伪代码如下。

Input: n, p, m, u, and m+1 clamped knots { u0, ..., um }
Output: Coefficients N0,p(u), N1,p(u), ..., Nn,p(u) in N[0], N[1], ..., N[n]
Algorithm:
	Initialize N[0..n] to 0; // initialization
	if u = u0 then // rule out special cases
		N[0] = 1.0;
		return
	else u = um then
		N[n] = 1.0
		return
	end if
	// now u is between u0 and um

	Let u be in knot span [uk,uk+1);
	N[k] := 1.0 // degree 0 coefficient
	for d :=1 to p do // degree d goes from 1 to p
		begin
			N[k-d] =  * N[(k-d)+1]; // right (south-west corner) term only
			for i := k-d+1 to k-1 do // compute internal terms
				N[i] :=  * N[i] +  * N[i+1];
			N[k] =  * N[k]; // let (north-west corner) term only
	end
	// array N[0..n] has the coefficients.

 

python结果仿真-3次B-Spline曲线

图中，

红色点位原始数据点；

黑色点为求解的控制点；

红色曲线为由原始数据点拟合的B-Spline曲线；

黑色曲线为由控制顶点拟合的B-Spline曲线。

可知，黑色曲线通过全部数据点，算法验证成功。

 

节点向量的选取

在计算控制顶点时，发现以下问题。

数据点总共n+1个，如果由此数据点构造节点向量，使用均匀向量法，得到n-3个非0非1控制节点。同样，控制顶点的数量也为n+1个，加上首尾0、1的节点，总共n-1个节点。二计算基函数系数矩阵时，需要n+1个节点，因此，好少两个节点。

这里有两个处理方法：
 

方法一：

仍然采用均匀向量法，在计算基函数系数矩阵时，添加在首尾添加两个节点：
$$\begin{array}{rl}& 原始使用的节点向量：\\ & \mathbf{U}=[0,u_1,u_2,\cdots ,u_{n-3},1]\\ & 增加后的节点向量：\\ & \mathbf{U}=[0,t_1,u_1,u_2,\cdots ,u_{n-3},t_2,1]\\ & t_1=u_1/2\\ & t_2=(n-3+1)/2\end{array}$$
这样计算后，即可按照伪代码中的算法计算n+1个控制顶点。

 

方法二：

使用弧长法计算节点向量。

由n+1个数据点，得到n段线段长度:
$$\begin{gathered} L=[l_1,l_2,l_3,\cdots ,l_n] \\ S=sum(L) \end{gathered}$$
则原始节点向量定义为：
$$knots=[0,0,0,0,\frac{l_1+l_2}{S},\frac{l_1+l_2+l_3}{S},\cdots ,\frac{l_1+l_2+\cdots +l_{n-1}}{S},1,1,1,1]$$
增加后的节点向量：
$$knot{s}^{{}^{\prime }}=[0,0,0,0,\frac{{\mathbf{l}}_1}{\mathbf{S}},\frac{l_1+l_2}{S},\frac{l_1+l_2+l_3}{S},\cdots ,\frac{l_1+l_2+\cdots +l_{n-1}}{S},\frac{l_1+l_2+\cdots +l_{n-1}+{\mathbf{l}}_{\mathbf{n}}}{S},1,1,1,1]$$
按照伪代码中的算法计算n+1个控制顶点。