B-spline curves

Question

I have a set of points which I want to smooth using B-spline curves.
My question is how can I implement B-spline curves to smooth these set of points?
I want to implement this using c++.

Is the amount of points fixed or variable? Anyway have a look at this Wikipedia page: http://en.wikipedia.org/wiki/B%C3%A9zier_curve — invalid_id, Aug 19 '14 at 09:04
There are lots of implementations of **de Boor's algorithm** in C++; try doing a web-search for it. — Evil Dog Pie, Aug 19 '14 at 09:06
You need to be clearer about what you want. Do you want a B-spline curve that smoothly connect (i.e., interpolate) all your data points or do you want your data points to be smoothed (i.e., reduction of noise in the data). — fang, Aug 19 '14 at 16:53
If you want the data points to be smoothed, you can look for topics in the area of least square fitting using spline functions. With LS fitting, you will need to assign parameters to each data points and solve a linear equation set to obtain the spline. The resulting spline will in general lie close to the data points. You can then re-evaluate the spline at the parameters to obtain a smoother set of data points. — fang, Aug 20 '14 at 01:26
Won't the least square fitting method give me a straight line? — Lakshya Kejriwal, Aug 20 '14 at 01:46
Least square fitting using spline function will not give you a straight line unless your data point distribution is more or less like a straight line. — fang, Aug 20 '14 at 03:08
I have been searching on least square fitting. Can you give me a link that explains it in an easy manner? — Lakshya Kejriwal, Aug 20 '14 at 03:17
This is a good reference [link](http://www.geometrictools.com/Documentation/BSplineCurveLeastSquaresFit.pdf). But I don't know whether it is easy to understand for you. — fang, Aug 20 '14 at 04:58

barak manos · Answer 1 · 2014-08-19T11:49:27.030

6

Here is a function for any given number of points:

void Spline(double x[N+1],double y[N+1], // input
            double A[N],double B[N],     // output
            double C[N],double D[N])     // output
{
    double w[N];
    double h[N];
    double ftt[N+1];

    for (int i=0; i<N; i++)
    {
        w[i] = (x[i+1]-x[i]);
        h[i] = (y[i+1]-y[i])/w[i];
    }

    ftt[0] = 0;
    for (int i=0; i<N-1; i++)
        ftt[i+1] = 3*(h[i+1]-h[i])/(w[i+1]+w[i]);
    ftt[N] = 0;

    for (int i=0; i<N; i++)
    {
        A[i] = (ftt[i+1]-ftt[i])/(6*w[i]);
        B[i] = ftt[i]/2;
        C[i] = h[i]-w[i]*(ftt[i+1]+2*ftt[i])/6;
        D[i] = y[i];
    }
}

Here is how you can print the results of this function:

void PrintSpline(double x[N+1],            // input
                 double A[N], double B[N], // input
                 double C[N], double D[N]) // input
{
    for (int i=0; i<N; i++)
    {
        cout << x[i] << " <= x <= " << x[i+1] << " : f(x) = ";
        cout << A[i] << "(x-" << x[i] << ")^3 + ";
        cout << B[i] << "(x-" << x[i] << ")^2 + ";
        cout << C[i] << "(x-" << x[i] << ")^1 + ";
        cout << D[i] << "(x-" << x[i] << ")^0";
        cout << endl;
    }
}

Please note that both functions assume x[0] < x[1] < ... < x[N].

edited Aug 19 '14 at 11:49

answered Aug 19 '14 at 09:24

barak manos

29,648
10
62
114

1

@shawshank: There's not a lot to explain assuming that you know how *Spline* works. But I will add a `PrintSpline` function so it might make it a little clearer... – barak manos Aug 19 '14 at 11:40
Well I don't know about splines in detail. So it became difficult for me to directly try and understand the code – Lakshya Kejriwal Aug 19 '14 at 12:14
@shawshank: I honestly don't understand your question. You say you have a set of points for which you want to create a *Spline* function, and then you say you don't know what a *Spline* function is????? – barak manos Aug 19 '14 at 15:08
I have been reading about splines for quite a few weeks now. But I don't know about them so much so that I can code it. I have read about de boor's recursive algorithm but couldn't get a hold of how to code it. – Lakshya Kejriwal Aug 19 '14 at 15:13
@shawshank: OK, I'll try to explain the idea behind *Spline* as simple as possible (i.e., with as little mathematical notation as possible): 1. You take several points and you create a function that goes through all of them. 2. For each pair of consecutive points, `x1` and `x2` there is a different 3rd degree polynomial (i.e., `Ax^3+Bx^2+Cx+D`) which is defined for all `x1 <= x <= x2`. 3. Those polynomials always "meet" each other at the end-points, so the entire function is continuous. Moreover, due to the nature of *Spline*, the entire function is also differentiable at those end-points. – barak manos Aug 19 '14 at 15:41
@shawshank: You can give it a try by calling `Spline` with your points, and then calling `PrintSpline` in order to print the function that will give you a *Spline* for your points. – barak manos Aug 19 '14 at 15:44
This looks like some sort of cubic interpolation. It generates a cubic polynomial between two consecutuve points. Interpolation scheme does not smooth data points. – fang Aug 19 '14 at 16:51
1

@fang: *Spline* provides a continuous and differentiable function in **all** the domain. I think that qualifies for "smoothing". In addition, this is what OP has asked for. – barak manos Aug 19 '14 at 17:46
So basically it gives a polynomial function that passes through all the data points to give a smooth curve – Lakshya Kejriwal Aug 20 '14 at 00:49
@barak: Well, IMHO, the OP is asking for methods/algorithms to smooth data points. – fang Aug 20 '14 at 01:23
@shawshank: Well, exactly... more or less that is... It gives a collection of polynomial functions, each one for a specific section of the graph. Their connection points are your input points, and even though they are different functions - not only do they "meet" at these points (thus making the entire function continuous), but they are also "smooth" at this points (thus making the entire function differentiable). – barak manos Aug 20 '14 at 05:57
@shawshank: In addition to the above, this old answer of mine at http://math.stackexchange.com/a/713284/131263 might help you to better understand. It shows an example for only 3 points (so the function is divided into 2 polynomials), but hopefully it will make it clearer for you. In general, given `N+1` points, you get a function which is divided into `N` polynomials. – barak manos Aug 20 '14 at 05:59
@fang: That is exactly what *Spline* does (where "smooth" means differentiable). – barak manos Aug 20 '14 at 06:00
@barak: OK. If you insist on "smooth" means differentiable in the context of "smoothing data points". – fang Aug 20 '14 at 06:08
@fang: From the title of the question (as well as its contents), it seems that OP wants to "spline" a set of points. I cannot be 100% sure of that of course, so I did my best under the current "circumstances" :) – barak manos Aug 20 '14 at 06:16

fang · Answer 2 · 2014-08-20T17:38:34.150

I originally recommend using Least Square fitting with spline functions to fit the data points, followed by resampling on the fitted spline to obtain a smoother set of data points (please see my comments after the OP). Here I would like to recommend a different approach, which could be simpler than the Least Square fitting approach:

1) create cubic Hermite curve interpolating all the data points. The cubic Hermite curve basically is a curve composed of many cubic polynomial curve segments in between two consecutive data points. A cubic Hermite curve is in general only C1 continuous.
2) use Kjellander method to smooth the cubic Hermite curve. This method basically compute the C2 discontinuity at the nodes (i.e., at the data points) and then adjust the nodes accordingly to reduce the C2 discontinuity.
3) After smoothing, the nodes of the cubic Hermite curve will be your new set of data points.

Here is a link for the Kjellander method (and other spline fairing methods). Source codes are available for download.

B-spline curves

2 Answers2

Linked