Topic: Cubic Spline Interpolation Bug

Cubic spline interpolation in Graph has a bug. In the attached image, the red curve is Graph's internal cubic spline interpolation for an 8-point data set. The blue curve is linear interpolation of a 100-point data set produced by an external cubic spline interpolation utility. The utility is here:

http://ham-radio.com/k6sti/spline.exe

You can use the utility to accurately graph smooth curves. It is a DOS program that reads a .CSV file and writes OUT.CSV containing the interpolated data set. It writes 100 points by default, but you can tell it to use up to 1000 points. Type SPLINE at the command prompt for details.

Brian

Post's attachments

test.png, 7 kb, 656 x 360
test.png 7 kb, 420 downloads since 2011-01-17 

Re: Cubic Spline Interpolation Bug

I have actually recently been made aware of the problem. I will fix it as soon as possible.

3 (edited by k6sti 2011-01-22 13:54:10)

Re: Cubic Spline Interpolation Bug

I've updated the utility to allow up to 3000 input or output points.

One time I implemented cubic spline interpolation I sampled the output at pixel resolution for screen display, essentially doing away with any implicit linear interpolation in the output. That seems like overkill since all display engines will plot a line (implicit linear interpolation). But the computer hardware could handle it (it was a real-time display) and it gave the most accurate output possible so I went ahead and did it. (I believe I still used the line function to fill in pixels for adjacent points that differed greatly in Y value.) The input data was a sparse FFT and I was displaying a signal spectrum. The pixel-interpolated curve looked perfectly smooth even though the input data was extremely jagged due to sparse sampling. Perhaps Graph could use this approach.

Brian

Re: Cubic Spline Interpolation Bug

I have now been looking into this and there doesn't seem to be any bugs in the implementation of cubic splines in Graph. The difference in the image shown is because Graph uses 2-dimension cubic splines as opposed to 1-dimension cubic splines. The 2-dimension splines seem to work much better than 1-dimension and will therefore be kept as it is for now. More types of interpolation may be added in the future.

Re: Cubic Spline Interpolation Bug

The red curve generated by Graph is clearly incorrect. The abrupt kink between X = 40 and X = 50 should not be there. The part between X = 30 and X = 40, as well as between X = 50 and X = 100, looks like straight linear interpolation and is obviously incorrect.

The blue curve, which is a cubic spline interpolation external to Graph, provides the expected smoothing. Graph should generate an identical curve.

Brian

Re: Cubic Spline Interpolation Bug

Here's another example. I sampled a sine wave at 0, 170, 190, and 360 deg. The red curve Graph generated to interpolate these four points goes $matches[1] at 180 degrees, where it provides three values for the single-valued function. This is clearly wrong. The blue curve from the external cubic spline interpolator generates a reasonable curve even though it does not reach +1 at 90 deg and -1 at 270 deg.

Brian

Post's attachments

sine.png, 7.11 kb, 656 x 360
sine.png 7.11 kb, 455 downloads since 2011-03-01 

Re: Cubic Spline Interpolation Bug

The red curve seems to be a much better interpolation of the four points than the blue. The blue curve overshoots heavily.

8 (edited by k6sti 2011-03-03 02:40:35)

Re: Cubic Spline Interpolation Bug

As I explained, the function I took the four samples from was a sine wave. The blue curve is vastly more accurate at reconstructing the original function than the red curve. Not only does the red curve provide a very poor reconstruction, it yields an impossible three-valued function. That's not just a simple error. It is grossly wrong. It is completely out to lunch. It makes no sense whatsoever. Interpolation is not a matter of drawing a line through some points that looks esthetically pleasing. It is a matter of accurately approximating a smooth function given a limited number of samples of it.

Brian

Re: Cubic Spline Interpolation Bug

Here is a further example. I added points at 10 deg and 350 deg for a total of six samples of a sine wave. The additional points improve the accuracy of the blue curve, which now more closely approaches the correct values of +1 at 90 deg and -1 at 270 deg. The red curve looks nothing like a sine wave, continues to yield an impossible three values in the middle, and now ignores the endpoints, dropping suddenly and discontinuously to zero. It is dead wrong.

Brian

Post's attachments

sine.png, 7.46 kb, 656 x 360
sine.png 7.46 kb, 424 downloads since 2011-03-03 

Re: Cubic Spline Interpolation Bug

One more example. Here I sampled a sine wave at 0, 90, 270, and 360 deg. The blue curve, which is an external cubic spline interpolator, yields an excellent approximation to the sampled function. The shape is symmetrical and the extreme values are correct. But the red curve, which is Graph's version of cubic spline interpolation, is skewed. Its peaks are in the wrong place and its magnitude exceeds 1, which is impossible for a sine wave. When Graph's interpolation behaves this way on a user-supplied data set where the underlying function is unknown, who would realize that it is in error? I often read interpolated points from a curve. Which curve yields the most accurate values?

Brian

Post's attachments

sine.png, 7.99 kb, 656 x 360
sine.png 7.99 kb, 423 downloads since 2011-03-03 

Re: Cubic Spline Interpolation Bug

Here's a final example. I sampled a sine wave at 0, 30, 330, and 360 deg. Now the red curve goes backwards at 0 and 360, yielding an impossible two values at those points. Which curve makes sense? Which curve better approximates a sine wave? Which curve do you want to read values from?

Brian

Post's attachments

sine.png, 8.2 kb, 656 x 360
sine.png 8.2 kb, 422 downloads since 2011-03-03 

Re: Cubic Spline Interpolation Bug

It was never the intention to use point series to create sine waves. If you want a sine wave you should create it as a function. The cubic splines was intentioned to create a smooth line between the points as an alternative to linear interpolation. Maybe instead of calling it Linear, Cubic splines and Half cosine I should have called them Algorithm 1, Algorithm 2 and Algorithm 3, but that seemed a little silly.

13 (edited by k6sti 2011-03-04 00:16:11)

Re: Cubic Spline Interpolation Bug

Ivan, I just used a sine wave as an example. I am not creating a function. I am sampling a known function so that it is easy to tell whether the interpolation is reasonable. The defects I've highlighted apply to any function or curve. They are not unique to sine waves. They apply also to measured data, as shown in my first example.

The interpolation method you are using does not yield curves that make sense, curves that are useful for obtaining accurate values between the points supplied, or curves that are mathematically correct. The method as implemented is entirely bogus. It is bizarre. It does not always yield single-valued functions. It bears no relation to a proper interpolation, whether you choose to use the name cubic spline or call it something else. No one who uses cubic spline interpolation in Graph can trust the outcome. It can give such crazy results that it is impossible to predict what it might do. That's why I offered my external interpolation utility. You must export data to it and then import the interpolated points, but at least it gives valid results. It would be so much easier if Graph would simply do it all internally. What would be so hard about that?

All you need to create a useful cubic spline interpolation is to use the code I sent you. It is standard code. I have used it for years in several different programs without any problems or weird results whatsoever. Call it spline1 and call the method you now use spline2. At least give users a choice.

I have no idea why you are unable to understand this issue. Just look at the examples I've provided and use common sense.

Brian

14 (edited by k6sti 2011-03-05 18:33:24)

Re: Cubic Spline Interpolation Bug

Ivan, I spent several hours yesterday going through my collection of dozens and dozens of Graph plots. I compared Graph's interpolation with a standard cubic spline. Graph's interpolation works more or less OK when there are lots of samples and when the spacing isn't too nonuniform. But when there are one or more samples with significantly different spacing, it can yield funny plots that are not representative of the underlying process being sampled. This behaviour is insidious, allowing bad data to pass for good.

I use Graph to draw plots of measured data from my electronics hobby. I take manual readings from lab instruments, both analog and digital, and then use Graph to plot the points. Due to time constraints, I can't always collect as many samples as I'd like. Sometimes I sample outlier points just to complete a curve. I rely on smooth interpolation to fill in the missing data. The problem with Graph's interpolation is that you can't trust it to do a reasonable job of filling in missing points. It can generate funny curves that are nothing like the underlying process you've measured. But ordinary cubic spline interpolation works in these cases.

If you want to keep the current Graph interpolation, I strongly recommend that you add standard cubic spline interpolation that a user can invoke when necessary. Users will have to determine for themselves when to use one interpolation or another, but at least they will have the option of plotting correct, valid curves.

Cubic spline interpolation smooths a curve by making certain assumptions about the first and second derivatives of the underlying function that the data represents. Sometimes real data does not conform to those assumptions. For example, some of the electrical signals I measure may saturate. The plotted curve suddenly becomes a constant value. The circuits are operating correctly but they exhibit discontinuous or nonsmooth derivatives. Any cubic spline interpolation may generate nonconstant interpolated values over a region of constant data due to the influence of adjacent regions. Usually the error is small, but the deviation of a nonflat curve can obscure the underlying saturation, which may be entirely normal. The user is left to explain the unexpected behavior exhibited by the plot. I have added an option to my cubic spline interpolator that enables it to preserve saturated data values. See the next message. If you implement a standard cubic spline interpolation, you might consider adding such a feature. It is not often needed, but it can make the interpolation model more realistic for some data.

Brian

15 (edited by k6sti 2011-03-05 18:20:17)

Re: Cubic Spline Interpolation Bug

I decided to simply implement clipping. The program lets you set lower and upper clipping thresholds. Interpolated points that fall beyond a threshold are set to the threshold value. This is simple, versatile, and easily understood.

I've updated the program at the URL given earlier.

Adding normal cubic spline interpolation to Graph would allow users to plot coarsely or unevenly sampled data without generating funny curves. Adding optional clipping thresholds for all interpolation methods would permit it to generate realistic curves for data with natural saturation.

Brian

Post's attachments

test1.png, 6.19 kb, 656 x 360
test1.png 6.19 kb, 413 downloads since 2011-03-05 

Re: Cubic Spline Interpolation Bug

k6sti wrote:

Ivan, I just used a sine wave as an example. I am not creating a function. I am sampling a known function so that it is easy to tell whether the interpolation is reasonable. The defects I've highlighted apply to any function or curve. They are not unique to sine waves. They apply also to measured data, as shown in my first example.

The interpolation method you are using does not yield curves that make sense, curves that are useful for obtaining accurate values between the points supplied, or curves that are mathematically correct. The method as implemented is entirely bogus. It is bizarre. It does not always yield single-valued functions. It bears no relation to a proper interpolation, whether you choose to use the name cubic spline or call it something else. No one who uses cubic spline interpolation in Graph can trust the outcome. It can give such crazy results that it is impossible to predict what it might do. That's why I offered my external interpolation utility. You must export data to it and then import the interpolated points, but at least it gives valid results. It would be so much easier if Graph would simply do it all internally. What would be so hard about that?

All you need to create a useful cubic spline interpolation is to use the code I sent you. It is standard code. I have used it for years in several different programs without any problems or weird results whatsoever. Call it spline1 and call the method you now use spline2. At least give users a choice.

I have no idea why you are unable to understand this issue. Just look at the examples I've provided and use common sense.

Brian

Brian, those exactly same 3 or  points  could have been from a different function, not sine function. Then what, would you expect that an interpolation method in one case will resemble to sine function, in other case--to another function??? Think about it! Interpolation methods are not intended to give the original function, but, as Ivan pointed, just to give a function that satisfies some smoothness conditions. That's all! Only in case you provide more and more points, the method will begin to give a graph close to the original particular function.
Read more about interp. on wiki...

Re: Cubic Spline Interpolation Bug

Ivan Johansen wrote:

The red curve seems to be a much better interpolation of the four points than the blue. The blue curve overshoots heavily.

smile))

Good reply, Ivan.

Re: Cubic Spline Interpolation Bug

Victor, you can draw any curve you want through a set of given points. That doesn't mean that all curves are equally valid or useful. The problem with Graph's interpolation method is that it can generate curves that are not representative of commonly encountered data, or that are not smooth, or that are impossible. When I say not representative, I mean that if you take more data samples, they will not lie on or anywhere near the curve Graph generated for the original samples. The curve has mislead you and given a false impression. When I say not smooth, I mean that Graph can insert kinks, abrupt changes of slope that are not warranted by the data, and it can generate straight line segments where a smoothly curved line is appropriate. When I say impossible, I am referring to the fact that Graph can generate curves that have multiple Y values for one X value. The curve is not just in error, it is nonsensical.

Brian

Re: Cubic Spline Interpolation Bug

Here are two more examples. One plots samples from a second-order process and the other plots samples from a third-order process. The red curve is Graph's internal interpolation, while the blue curve is from an external cubic spline interpolator. In both cases the red curve does not well represent the underlying process. If I had taken more data samples, they would lie exactly on the blue curves, not on the red.

Another way to state my objection is that most commonly encountered processes are low-order. They are inherently smooth. Attempting to model them as high-order processes will yield invalid and misleading results unless you have a lot of data samples. Graph's interpolation acts as if its model order were much higher than that of ordinary cubic spline interpolation. It yields curves that are less smooth, change more abruptly, and are more like connecting the dots with linear interpolation. Commonly encountered data isn't like that.

Before I wrote my own cubic spline interpolator, whenever I encountered problems with Graph's cubic spline I would simply plot the data points as dots and use Graph's linear interpolation to connect them. The resulting curve wasn't at all smooth, but the obvious straight-line segments and the visible dots provided immediate visual clues about the nature of the model. Anyone looking at the plot could immediately grasp what had been done without obtaining a false impression. They realized that the data wasn't really piecewise linear. But when I simply used Graph's cubic spline to plot a curve without marking the data points, the unavoidable impression was that the data followed the curve as shown. In fact, in some places it wasn't near the curve at all, but the user had no way to know this.

Ivan could keep his program from plotting misleading curves by simply offering ordinary cubic spline interpolation as an option.

Brian

Post's attachments

par.png, 7.66 kb, 656 x 360
par.png 7.66 kb, 433 downloads since 2011-03-06 

tri.png, 6.78 kb, 656 x 360
tri.png 6.78 kb, 431 downloads since 2011-03-06 

20 (edited by victor 2011-03-08 07:36:42)

Re: Cubic Spline Interpolation Bug

Ivan Johansen wrote:

I have now been looking into this and there doesn't seem to be any bugs in the implementation of cubic splines in Graph. The difference in the image shown is because Graph uses 2-dimension cubic splines as opposed to 1-dimension cubic splines. The 2-dimension splines seem to work much better than 1-dimension and will therefore be kept as it is for now. More types of interpolation may be added in the future.

Ivan, I just made some little research about cubic spline interpolation. So, what do you mean by 1-dimensional and 2-dimensional cubic splines? Did you actually intend to interpolate a third variable, like z=f(x,y)? That could be the issue then.
Please see http://docs.scipy.org/doc/scipy/referen … olate.html , or other.
Also, some other simple cubic spline (called 'natural') do interpolate, indeed, in a more expected way. http://en.wikipedia.org/wiki/Spline_interpolation (I tried the example there in the end with 3 points); also read the 3rd external link in the same wiki page.

Re: Cubic Spline Interpolation Bug

Brian,
I just informed myself a bit more about cubic spline interpolation. You see, there are indeed very many variations of cubic splines.
  But I agree with you that the one provided by Ivan does not behave in the most expected way. For instance, I repeated the interpolation provided at http://en.wikipedia.org/wiki/Interpolation , at the end of the article (the 3 points interp. ) and "Graph" give "strange" results in comparison with the Natural type (see wiki) of cubic spline.

Thanks for pointing out; I will also write to Ivan.

Re: Cubic Spline Interpolation Bug

It was never a goal to make an interpolation function where every x-coordinate has exactly one y-coordinate. The goal was to make a line between the points that was more smooth than a linear interpolation, and I think that goal has been reached.

The normal 1-dimensional cubic spline does not work for my goal in all cases so I used the 2-dimensional variation instead. It is basically a parametric function where both x(t) and y(t) is interpolated as cubic splines.

I think I first saw it at MathWorld:
http://mathworld.wolfram.com/CubicSpline.html

There is also an interactive Java applet here:
http://www.cse.unsw.edu.au/~lambert/spl … cubic.html

But I understand that other people have other goals. It was always my intention to add more interpolation algorithms, but no matter how many I add there will always be some complaining that I have not implemented their favorite variation. However I will consider adding 1-dimensional cubic splines.

Post's attachments

Cubic spline.png, 4.46 kb, 460 x 372
Cubic spline.png 4.46 kb, 454 downloads since 2011-03-11 

Re: Cubic Spline Interpolation Bug

Hi Ivan,

maybe we (at least me and Brian) just don't know what is the 2-D cubic spline suitable for. But one thing is sure: if you add one, (or better several) cubic splines of the 1-dimensional types (including the so called "natural" one - described for instance in the above wikipedia link) -- then everybody will be happy, and no more questions will arise.

Re: Cubic Spline Interpolation Bug

The picture in my last message should explain it. It creates a more smooth line between the points than just connecting them with a straight line. But I will try to implement 1-dimensional cubic spline to make you and Brian happy. smile

Re: Cubic Spline Interpolation Bug

I have now added the 1D cubic splines as an interpolation option in the latest beta version.