0
$\begingroup$

I have a set of $M$ data points $(x_j,y_j), 1 \le j \le M$ defined on an interval $[a,b]$ and I want to fit a periodic B-spline of order $k$ to these data. So my model will be: $$ f(x) = \sum_{i=1}^N c_i B_{i,k}(x;\mathbf{t}) $$ where the $N$ values $c_i$ are the control points (to be determined), $\mathbf{t}$ is the knot vector, and $B_{i,k}(x;\mathbf{t})$ is the usual B-spline basis function (see here for example).

Now for a least-squares fit with no conditions on the spline, I would simply define my $M \times N$ least squares matrix: $$ A_{ij} = B_{j,k}(x_i;\mathbf{t}) $$ and do the usual minimization: $$ \min_c ||y - A c||^2 $$ de Boor's book on splines contains explanations and code for solving this, and taking advantage of the banded structure of the $A^T A$ matrix. Unfortunatey his book is quite lacking on details for enforcing a periodic spline.

So I want my spline to match function values and derivatives at the interval endpoints: $$ f^{(d)}(a) = f^{(d)}(b) $$ for $0 \le d < k$. Some references (oriented more toward CAD applications), indicate that periodic B-splines can be achieved simply by using a uniform knot vector, though I don't really see how this would work.

In my case, to achieve the desired result, I can note that my condition above can be expressed as a matrix equation: $$ D c = 0 $$ where $D$ is a $(k-1) \times N$ matrix given by $$ D_{ij} = \frac{d^i}{dx^i} B_{j,k}(b;\mathbf{t}) - \frac{d^i}{dx^i} B_{j,k}(a; \mathbf{t}) $$ So this would give rise to a linear equality constrained least squares problem: $$ \min_c ||y - A c||^2 $$ subject to $Dc = 0$.

In principle this could be solved with the given LAPACK LSE routine (though of course that routine won't take advantage of the sparse structure of the matrix $A$). However, I have seen nothing in the B-spline literature about requiring LSE methods to compute periodic B-splines, so perhaps I am missing something simple?

Some literature, as I mentioned before says that all that is needed is to choose the knot vector carefully, but I cannot see how this would work for the least squares problem. Any advice is appreciated.

$\endgroup$
1
$\begingroup$

Say $m$ is the degree, $t\in[t_0,t_n)$ is a periodic parameter, and let $k=t_n-t_0$.
If you want linear constraints you have to choose a knot vector with the form:

$$\{t_{-m},\,\ldots,t_{-1},t_0,t_1,\,\ldots,t_m,\ \ldots..\ldots\ , t_{-m}+k,\,\ldots,t_{-1}+k,\;t_0+k,\;t_1+k,\,\ldots,t_m+k\}$$

That is the first $2m+1$ knots must be the same as the last $2m+1$ knots except for an additive term. If the knots is chosen this way, the constraints are that the first $m$ control points must be the same as the last $m$ control points.

What is described above is at least the simplest approach. It ensures that the velocity of the curve over the parameter is as differentiable as the curve itself. However, if that is not necessary you can consider geometric differentiability which merely demands the velocity vector at $t=t_0$ be proportional to that at $t=t_n$ by some positive factor $c$. Then the higher derivatives have to be proportional by integer powers of $c$. The knot vector can be chosen more flexibly (I don't know the exact form it has to have) and the resulting control point constraints remain linear.

Another less simple approach is to not keep the knots fixed, but then nonlinear constraints arise.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Does that knot vector ensure that all derivatives of the spline match at the endpoints? Or just the spline value itself? $\endgroup$ – vibe May 17 '19 at 20:20
  • $\begingroup$ @vibe All but the $m$'th derivative will agree. The $m$'th derivative of a B-spline is piecewise constant and is never continuous. $\endgroup$ – Oppenede May 17 '19 at 20:32
  • $\begingroup$ With this knot vector, won't there be a problem with the number of maximum knots allowed? For example, if I have cubic B-splines with $m=3$ and lets say $n=7$ control points, so that the number of knots is $n+m+1 = 11$, then your knot vector above would be $[t_{-3},t_{-2},t_{-1},t_0,t_1,t_2,t_3,t_{-3}+k,t_{-2}+k,t_{-1}+k,t_0+k,t_1+k,t_2+k,t_3+k]$ which has $14$ knots which is greater than the allowed $11$ maximum. Could you give an explicit example of what the knot vector would look like in this case? $\endgroup$ – vibe Jul 30 '19 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.