Neil Glossop

07-28-1995, 01:33 AM

Hi Biomech-lers,

Here is the summary of the resonses to my follow up on cubic splines.

Many thanks to all who responded.

Neil

--

N. Glossop, Ph.D.,

Toronto, Canada

neil@isgtec.com

------------------------------------------------------------------

My original posting:

Jesus Dapena wrote in a recent summary about splines,

> I would advise you very strongly to stay away from CUBIC splines.

> Usually (always?) they force the second derivative to be zero at the

> beginning and end of the data set. When that is not the case in the

> activity being analyzed (i.e., almost always), the result is very distorted

> data in the early and late parts of the trial (and even the middle parts can

> get messed up too).

I am not sure how much I agree with this statement, and would ask for a

little feedback from list members. While it is true that cubic splines

force the second derivitives to be zero, cubics and piecewise cubics are

often used to interpolate data. Where I would think that this causes a

particular problem is in taking the *derivitives* in order to calculate

velocity and acceleration.

As you rightly point out,

> The differences between cubic and quintic spline was shown very

> clearly in Kit Vaughan's Ph.D. dissertation (University of Iowa, ca. 1981)

> when he fit cubic and quintic splines to the vertical location data of a

> free-falling ball. The quintic gave a beautiful fit, with acceleration very

> near 9.81 m/s2 throughout the entire airborne period. The cubic forced

> acceleration to be zero at the beginning and end of the data set, the curve

> then overshot the 9.81 m/s2 value in the middle part of the trial; the whole

> curve was distorted, so that acceleration was not near 9.81 m/s2 hardly

> anywhere at all.

This is hardly unexpected when taking derivitives. If you are only

interested in *position* information, I might suggest (although I don't know

for sure), that cubics would be more than adequate. My experience with

higher order fits is that they tend to oscillate excessively. The oscillation

tends to badly interpolate the original data. This may however, just be an

artifact of very high order fits (>10 df say), I can't say for sure since I

have not done any recently.

> I have been using splines for about twenty years now, and my

> experience tells me that quintic spline is excellent, but you don't want to

> touch cubic spline with a ten foot pole!

I guess what I am saying is that I don't think cubics are that bad if you

are sticking to interpolation of position data alone. If you want to take

derivitives, use a higher order interpolation, but watch out for artifacts

on the positional interpolation.

I'd appreciate any additional discussion on this, and will post replys sent

to me.

Cheers,

Neil

--

N. Glossop, Ph.D.,

Toronto, Canada

neil@isgtec.com

------------------------------------------------------------------

From: "Beth Todd"

Organization: College of Engineering

> Jesus Dapena wrote in a recent summary about splines,

>

> > I would advise you very strongly to stay away from CUBIC splines.

> > Usually (always?) they force the second derivative to be zero at the

> > beginning and end of the data set. When that is not the case in the

> > activity being analyzed (i.e., almost always), the result is very distorted

> > data in the early and late parts of the trial (and even the middle parts can

> > get messed up too).

>

> I am not sure how much I agree with this statement, and would ask for a

> little feedback from list members. While it is true that cubic splines

> force the second derivitives to be zero, cubics and piecewise cubics are

> often used to interpolate data. Where I would think that this causes a

> particular problem is in taking the *derivitives* in order to calculate

> velocity and acceleration.

>

When I taught a numerical methods course a couple of years ago, I

taught the students that there were five different possible schemes

for constraining the endpoints. (I'm not a mathematician, so there

may be other methods that I'm not aware of.) These conditions are

1) Clamped cubic spline where the first derivatives are specified at

the endpoints; this will give zero second derivatives.

2) Natural cubic spline; the endpoints are set to zero

3) The second derivatives are extrapolated to the endpoints.

4) The second derivatives are constant near the endpoints.

5) The second derivatives are specified at the endpoints.

Not all of the endpoint contraints give zero second derivatives, and

I was surprised when I read the message that you're commenting on.

My reference is "Numerical Methods for Mathematics, Science, and

Engineering", 2nd Ed., by John H. Mathews, Prentice Hall, 1992.

> As you rightly point out,

>

> > The differences between cubic and quintic spline was shown very

> > clearly in Kit Vaughan's Ph.D. dissertation (University of Iowa, ca. 1981)

> > when he fit cubic and quintic splines to the vertical location data of a

> > free-falling ball. The quintic gave a beautiful fit, with acceleration very

> > near 9.81 m/s2 throughout the entire airborne period. The cubic forced

> > acceleration to be zero at the beginning and end of the data set, the curve

> > then overshot the 9.81 m/s2 value in the middle part of the trial; the whole

> > curve was distorted, so that acceleration was not near 9.81 m/s2 hardly

> > anywhere at all.

>

> This is hardly unexpected when taking derivitives. If you are only

> interested in *position* information, I might suggest (although I don't know

> for sure), that cubics would be more than adequate. My experience with

> higher order fits is that they tend to oscillate excessively. The oscillation

> tends to badly interpolate the original data. This may however, just be an

> artifact of very high order fits (>10 df say), I can't say for sure since I

> have not done any recently.

>

As a rule of thumb, I told the students not to use a polynomial of

order higher than 6 due to the excessive oscillations. I'm not

exactly sure why I chose 6--must have been something that I read in

Mathews' book.

Beth Todd

Dr. Beth A. Todd

Assistant Professor

Engineering Science and Mechanics

Box 870278

University of Alabama

Tuscaloosa, AL 35487-0278

btodd@coe.eng.ua.edu

(205)348-1623

fax: (205)348-7240

------------------------------------------------------------------

From: Dale.Knochenmuss@UC.EDU (Dale Knochenmuss)

I agree that cubic splines can be fine to use as long as some thought is

given to what you are doing and what you want from the data.

For many applications, the most desirable way to fit a curve to data is to

come up with a single equation that provides a reasonable approximation to

the entire data set. When the set is long or complex, this is often not

possible or computationally difficult. Segmental approaches (or splines)

are then an alternative. They attempt to use a series of equations to fit

the complete data set. Each equation fits just a portion of the data, but

when you string them together end-to-end, you have a mathematical

approximation to the entire data set. It becomes important for each

equation to blend smoothly into the next since the physical process being

approximated does not, typically, have discontinuities..

It is generally advisable to accomplish curve fitting with an equation, or

equations, of the lowest possible order. This avoids the erratic behavior

you mentioned that can result from higher order equations. Starting with

the lowest possible order, an equation of order one has obvious limitations

since so many kinds of data are nonlinear. Splines made up of linear

equations also have the disadvantage that slopes don't match at the

boundaries between equations so there will be discontinuities in the fit.

Sets of second order (quadratic) equations can fit many types of data and

can be calculated so that the slopes of adjacent equations match at the

boundary. They cannot, however, guarantee that the curvature (second

derivative) will match, thus causing discontinuities.

Third order equations can be found which will match both slope and curvature

at each boundary, eliminating discontinuities and providing a smooth fit.

Splines made up of third order equations are therefore the lowest order

which provide smooth fits through the first and second derivatives (slope

and curvature). This is why cubic splines are often used for curve fitting.

The problem, then, lies in how the beginning and end of the data set are

handled. Jesus Dapena referred to forcing one or more of the derivatives to

be zero at one or both ends. This makes sense only if the physical process

being modelled is known to meet, or approximate, this condition at the

beginning and/or of the test. The important point, I think, is that this is

not the only option and should not be used if it is not appropriate.

Referring to "Applied Numerical Analysis" by Curtis F. Gerald and Patrick O.

Wheatley, Addison-Wesley Publishing, 4th edition, 1989, four options are

suggested for handling end points:

1) Assume the end cubics are linear (Dapena's case)

2) Assume the end cubics approach parabolas

3) Linearly extrapolate from the nearest known data points

4) Assume fixed (but non-zero) values at the ends

Gerald and Wheatley suggest option 4 as being reasonable if a derivative

estimate is available.

Referring to the example application of fitting curves to vertical location

data of a free-falling object, if an analysis of the system being tested

results in the conclusion that the acceleration is non-zero throughout the

test, then it is obviously not a good idea to apply a curve-fitting routine

which forces zero values at the beginning and end. If you know enough to

make an estimate for the end points, a third-order fit might yield

acceptable results. If the available knowledge of the system isn't

sufficient to make an estimate, then it might be better to go with the

higher order fit. I think you are correct in saying that third order

(cubic) equations are likely to be sufficient if you are only going to be

working with the positional data. This also provides a result with less

computational effort and minimizes the risk of erratic results.

Regards,

Dale

----------

Dale R. Knochenmuss

University of Cincinnati

Noyes-Giannestras Biomechanics Laboratories

Dale.Knochenmuss@UC.Edu

------------------------------------------------------------------

From: "Ton van den Bogert"

Neil,

I agree with your comments on cubic vs. quintic splines; I had

almost sent a similar reply to Jesus Dapena's posting.

In my experience, cubic splines are fine for 1st derivatives

unless you have a large amount of smoothing which makes the

boundary effects (cubic spline is straight line at the endpoints)

extend too far.

The oscillation problems with quintic splines that you mention

only occur, as far as I have seen, when there are gaps in the

data. As you say, interpolation can become very wild. For

typical, regularly spaced data, the quintic spline gives

essentially the same result as the cubic spline. Except the

quintic spline is better at the endpoints, especially the 2nd

derivative.

Still, I tend to use cubic splines whenever I don't need a 2nd

derivative. I guess that decision is based on saving computer

time.

-- Ton van den Bogert

Human Performance Laboratory

University of Calgary

------------------------------------------------------------------

From: Victor Ng-Thow-Hing

There are various formulations for basis functions of cubic splines that

do different things. Catmull-Rom and Hermite both have the ability to

interpolate points. Several spline segments are often used to fit data

points. The most popular formulations like Bezier and B-spline can have

some built in constraints for C1 and c2 continuity, but these can be

circumvented by using tricks like multiple knots for B-splines.

For higher degree splines, there is always the danger of greater instability

with the curve shape (eg., unwanted oscillations), especially when fitting

data. NURBS (non-rational uniform B-splines) also get around many problems

and can represent a wide variety of shapes, such as cusps, and perfect

circles.

In conclusion, I think cubic splines are very stable and useful.

Vic.

------------------------------------------------------------------

From: dapena@valeri.hper.indiana.edu

Neil:

It is possible that cubic spline data may be OK if you are only

interested in location data, and not interested in getting derivatives. But

getting merely ***location*** data seems to be a rather unusual final

objective. And you will have to beware if you later on get derivatives from

the cubic-spline smoothed data at any later point in the process, by

whatever method.

I have not used cubic spline for a very long time now, but my rough

recollection is that the cubic did not oscillate any less than the quintic.

(I am just writing from memory, an untrustworthy thing!) So I don't think

the cubic provides any advantage.

Jesus Dapena

------------------------------------------------------------------

From: Glen Niebur

Neil Glossop wrote:

>Jesus Dapena wrote in a recent summary about splines,

>> I would advise you very strongly to stay away from CUBIC splines.

>> Usually (always?) they force the second derivative to be zero at the

>> beginning and end of the data set. When that is not the case in the

>> activity being analyzed (i.e., almost always), the result is very distorted

>> data in the early and late parts of the trial (and even the middle parts can

>> get messed up too).

>I am not sure how much I agree with this statement, and would ask for a

>little feedback from list members. While it is true that cubic splines

>force the second derivitives to be zero, cubics and piecewise cubics are

>often used to interpolate data.

Cubic splines need not force a zero second derivative at the end points of the

curve. This is only the case for "Natural" end conditions. Other end

conditions are possible, such as clamped end conditions where we can

apply a known first derivative.

A more useful end condition is the "Quadratic" end condition which sets

the second derivative at the final point equal to the second derivative

and the next to last point at the 2nd derivative at the first point

equal to the second derivative at the second point. For "reasonably"

high sampling rates, this should be a good approximation.

Another good choice is the "not a knot" end condition. This end condition

will cause the first two segments and the last two segments to interpolate

a single cubic curve.

Finally, for cyclic events, you can specify that the second derivatives

are equal at the first and last points.

In summary, it isn't necessarily cubic splines which are bad, it is the

common "natural" end condition implementation that isn't particularly

appropriate to many problems.

A good reference for spline interpolation is:

Farin, Gerald, 1988, "Curves and Surfaces for Computer Aided Geometric

Design," Academic Press

Glen

Glen Niebur |

Mayo Clinic | This space intentionally left blank.

Biomechanics Lab |

gln@hercules.mayo.edu |

Here is the summary of the resonses to my follow up on cubic splines.

Many thanks to all who responded.

Neil

--

N. Glossop, Ph.D.,

Toronto, Canada

neil@isgtec.com

------------------------------------------------------------------

My original posting:

Jesus Dapena wrote in a recent summary about splines,

> I would advise you very strongly to stay away from CUBIC splines.

> Usually (always?) they force the second derivative to be zero at the

> beginning and end of the data set. When that is not the case in the

> activity being analyzed (i.e., almost always), the result is very distorted

> data in the early and late parts of the trial (and even the middle parts can

> get messed up too).

I am not sure how much I agree with this statement, and would ask for a

little feedback from list members. While it is true that cubic splines

force the second derivitives to be zero, cubics and piecewise cubics are

often used to interpolate data. Where I would think that this causes a

particular problem is in taking the *derivitives* in order to calculate

velocity and acceleration.

As you rightly point out,

> The differences between cubic and quintic spline was shown very

> clearly in Kit Vaughan's Ph.D. dissertation (University of Iowa, ca. 1981)

> when he fit cubic and quintic splines to the vertical location data of a

> free-falling ball. The quintic gave a beautiful fit, with acceleration very

> near 9.81 m/s2 throughout the entire airborne period. The cubic forced

> acceleration to be zero at the beginning and end of the data set, the curve

> then overshot the 9.81 m/s2 value in the middle part of the trial; the whole

> curve was distorted, so that acceleration was not near 9.81 m/s2 hardly

> anywhere at all.

This is hardly unexpected when taking derivitives. If you are only

interested in *position* information, I might suggest (although I don't know

for sure), that cubics would be more than adequate. My experience with

higher order fits is that they tend to oscillate excessively. The oscillation

tends to badly interpolate the original data. This may however, just be an

artifact of very high order fits (>10 df say), I can't say for sure since I

have not done any recently.

> I have been using splines for about twenty years now, and my

> experience tells me that quintic spline is excellent, but you don't want to

> touch cubic spline with a ten foot pole!

I guess what I am saying is that I don't think cubics are that bad if you

are sticking to interpolation of position data alone. If you want to take

derivitives, use a higher order interpolation, but watch out for artifacts

on the positional interpolation.

I'd appreciate any additional discussion on this, and will post replys sent

to me.

Cheers,

Neil

--

N. Glossop, Ph.D.,

Toronto, Canada

neil@isgtec.com

------------------------------------------------------------------

From: "Beth Todd"

Organization: College of Engineering

> Jesus Dapena wrote in a recent summary about splines,

>

> > I would advise you very strongly to stay away from CUBIC splines.

> > Usually (always?) they force the second derivative to be zero at the

> > beginning and end of the data set. When that is not the case in the

> > activity being analyzed (i.e., almost always), the result is very distorted

> > data in the early and late parts of the trial (and even the middle parts can

> > get messed up too).

>

> I am not sure how much I agree with this statement, and would ask for a

> little feedback from list members. While it is true that cubic splines

> force the second derivitives to be zero, cubics and piecewise cubics are

> often used to interpolate data. Where I would think that this causes a

> particular problem is in taking the *derivitives* in order to calculate

> velocity and acceleration.

>

When I taught a numerical methods course a couple of years ago, I

taught the students that there were five different possible schemes

for constraining the endpoints. (I'm not a mathematician, so there

may be other methods that I'm not aware of.) These conditions are

1) Clamped cubic spline where the first derivatives are specified at

the endpoints; this will give zero second derivatives.

2) Natural cubic spline; the endpoints are set to zero

3) The second derivatives are extrapolated to the endpoints.

4) The second derivatives are constant near the endpoints.

5) The second derivatives are specified at the endpoints.

Not all of the endpoint contraints give zero second derivatives, and

I was surprised when I read the message that you're commenting on.

My reference is "Numerical Methods for Mathematics, Science, and

Engineering", 2nd Ed., by John H. Mathews, Prentice Hall, 1992.

> As you rightly point out,

>

> > The differences between cubic and quintic spline was shown very

> > clearly in Kit Vaughan's Ph.D. dissertation (University of Iowa, ca. 1981)

> > when he fit cubic and quintic splines to the vertical location data of a

> > free-falling ball. The quintic gave a beautiful fit, with acceleration very

> > near 9.81 m/s2 throughout the entire airborne period. The cubic forced

> > acceleration to be zero at the beginning and end of the data set, the curve

> > then overshot the 9.81 m/s2 value in the middle part of the trial; the whole

> > curve was distorted, so that acceleration was not near 9.81 m/s2 hardly

> > anywhere at all.

>

> This is hardly unexpected when taking derivitives. If you are only

> interested in *position* information, I might suggest (although I don't know

> for sure), that cubics would be more than adequate. My experience with

> higher order fits is that they tend to oscillate excessively. The oscillation

> tends to badly interpolate the original data. This may however, just be an

> artifact of very high order fits (>10 df say), I can't say for sure since I

> have not done any recently.

>

As a rule of thumb, I told the students not to use a polynomial of

order higher than 6 due to the excessive oscillations. I'm not

exactly sure why I chose 6--must have been something that I read in

Mathews' book.

Beth Todd

Dr. Beth A. Todd

Assistant Professor

Engineering Science and Mechanics

Box 870278

University of Alabama

Tuscaloosa, AL 35487-0278

btodd@coe.eng.ua.edu

(205)348-1623

fax: (205)348-7240

------------------------------------------------------------------

From: Dale.Knochenmuss@UC.EDU (Dale Knochenmuss)

I agree that cubic splines can be fine to use as long as some thought is

given to what you are doing and what you want from the data.

For many applications, the most desirable way to fit a curve to data is to

come up with a single equation that provides a reasonable approximation to

the entire data set. When the set is long or complex, this is often not

possible or computationally difficult. Segmental approaches (or splines)

are then an alternative. They attempt to use a series of equations to fit

the complete data set. Each equation fits just a portion of the data, but

when you string them together end-to-end, you have a mathematical

approximation to the entire data set. It becomes important for each

equation to blend smoothly into the next since the physical process being

approximated does not, typically, have discontinuities..

It is generally advisable to accomplish curve fitting with an equation, or

equations, of the lowest possible order. This avoids the erratic behavior

you mentioned that can result from higher order equations. Starting with

the lowest possible order, an equation of order one has obvious limitations

since so many kinds of data are nonlinear. Splines made up of linear

equations also have the disadvantage that slopes don't match at the

boundaries between equations so there will be discontinuities in the fit.

Sets of second order (quadratic) equations can fit many types of data and

can be calculated so that the slopes of adjacent equations match at the

boundary. They cannot, however, guarantee that the curvature (second

derivative) will match, thus causing discontinuities.

Third order equations can be found which will match both slope and curvature

at each boundary, eliminating discontinuities and providing a smooth fit.

Splines made up of third order equations are therefore the lowest order

which provide smooth fits through the first and second derivatives (slope

and curvature). This is why cubic splines are often used for curve fitting.

The problem, then, lies in how the beginning and end of the data set are

handled. Jesus Dapena referred to forcing one or more of the derivatives to

be zero at one or both ends. This makes sense only if the physical process

being modelled is known to meet, or approximate, this condition at the

beginning and/or of the test. The important point, I think, is that this is

not the only option and should not be used if it is not appropriate.

Referring to "Applied Numerical Analysis" by Curtis F. Gerald and Patrick O.

Wheatley, Addison-Wesley Publishing, 4th edition, 1989, four options are

suggested for handling end points:

1) Assume the end cubics are linear (Dapena's case)

2) Assume the end cubics approach parabolas

3) Linearly extrapolate from the nearest known data points

4) Assume fixed (but non-zero) values at the ends

Gerald and Wheatley suggest option 4 as being reasonable if a derivative

estimate is available.

Referring to the example application of fitting curves to vertical location

data of a free-falling object, if an analysis of the system being tested

results in the conclusion that the acceleration is non-zero throughout the

test, then it is obviously not a good idea to apply a curve-fitting routine

which forces zero values at the beginning and end. If you know enough to

make an estimate for the end points, a third-order fit might yield

acceptable results. If the available knowledge of the system isn't

sufficient to make an estimate, then it might be better to go with the

higher order fit. I think you are correct in saying that third order

(cubic) equations are likely to be sufficient if you are only going to be

working with the positional data. This also provides a result with less

computational effort and minimizes the risk of erratic results.

Regards,

Dale

----------

Dale R. Knochenmuss

University of Cincinnati

Noyes-Giannestras Biomechanics Laboratories

Dale.Knochenmuss@UC.Edu

------------------------------------------------------------------

From: "Ton van den Bogert"

Neil,

I agree with your comments on cubic vs. quintic splines; I had

almost sent a similar reply to Jesus Dapena's posting.

In my experience, cubic splines are fine for 1st derivatives

unless you have a large amount of smoothing which makes the

boundary effects (cubic spline is straight line at the endpoints)

extend too far.

The oscillation problems with quintic splines that you mention

only occur, as far as I have seen, when there are gaps in the

data. As you say, interpolation can become very wild. For

typical, regularly spaced data, the quintic spline gives

essentially the same result as the cubic spline. Except the

quintic spline is better at the endpoints, especially the 2nd

derivative.

Still, I tend to use cubic splines whenever I don't need a 2nd

derivative. I guess that decision is based on saving computer

time.

-- Ton van den Bogert

Human Performance Laboratory

University of Calgary

------------------------------------------------------------------

From: Victor Ng-Thow-Hing

There are various formulations for basis functions of cubic splines that

do different things. Catmull-Rom and Hermite both have the ability to

interpolate points. Several spline segments are often used to fit data

points. The most popular formulations like Bezier and B-spline can have

some built in constraints for C1 and c2 continuity, but these can be

circumvented by using tricks like multiple knots for B-splines.

For higher degree splines, there is always the danger of greater instability

with the curve shape (eg., unwanted oscillations), especially when fitting

data. NURBS (non-rational uniform B-splines) also get around many problems

and can represent a wide variety of shapes, such as cusps, and perfect

circles.

In conclusion, I think cubic splines are very stable and useful.

Vic.

------------------------------------------------------------------

From: dapena@valeri.hper.indiana.edu

Neil:

It is possible that cubic spline data may be OK if you are only

interested in location data, and not interested in getting derivatives. But

getting merely ***location*** data seems to be a rather unusual final

objective. And you will have to beware if you later on get derivatives from

the cubic-spline smoothed data at any later point in the process, by

whatever method.

I have not used cubic spline for a very long time now, but my rough

recollection is that the cubic did not oscillate any less than the quintic.

(I am just writing from memory, an untrustworthy thing!) So I don't think

the cubic provides any advantage.

Jesus Dapena

------------------------------------------------------------------

From: Glen Niebur

Neil Glossop wrote:

>Jesus Dapena wrote in a recent summary about splines,

>> I would advise you very strongly to stay away from CUBIC splines.

>> Usually (always?) they force the second derivative to be zero at the

>> beginning and end of the data set. When that is not the case in the

>> activity being analyzed (i.e., almost always), the result is very distorted

>> data in the early and late parts of the trial (and even the middle parts can

>> get messed up too).

>I am not sure how much I agree with this statement, and would ask for a

>little feedback from list members. While it is true that cubic splines

>force the second derivitives to be zero, cubics and piecewise cubics are

>often used to interpolate data.

Cubic splines need not force a zero second derivative at the end points of the

curve. This is only the case for "Natural" end conditions. Other end

conditions are possible, such as clamped end conditions where we can

apply a known first derivative.

A more useful end condition is the "Quadratic" end condition which sets

the second derivative at the final point equal to the second derivative

and the next to last point at the 2nd derivative at the first point

equal to the second derivative at the second point. For "reasonably"

high sampling rates, this should be a good approximation.

Another good choice is the "not a knot" end condition. This end condition

will cause the first two segments and the last two segments to interpolate

a single cubic curve.

Finally, for cyclic events, you can specify that the second derivatives

are equal at the first and last points.

In summary, it isn't necessarily cubic splines which are bad, it is the

common "natural" end condition implementation that isn't particularly

appropriate to many problems.

A good reference for spline interpolation is:

Farin, Gerald, 1988, "Curves and Surfaces for Computer Aided Geometric

Design," Academic Press

Glen

Glen Niebur |

Mayo Clinic | This space intentionally left blank.

Biomechanics Lab |

gln@hercules.mayo.edu |