PDA

View Full Version : Summary of responses: Extrapolation/Spline routines for gait data



Alan R Morris
11-30-1997, 05:12 AM
Hello readers,

I have compiled a summary of the responses to my questions regarding
either extrapolation or spline-fitting routines to account for gaps
(missing) data from 3-dimensional gait or other movement records. Thanks
to all that responded. As far as I am concerned, it would appear that
choosing either Herman Woltrings Cross-Validation Spline fitting routines
or some other spline-fitting routine that simultaneously works on all
three dimensions, seems to be the most recommended technique - where the
splines can be fit to unequally spaced data and gap data will be pulled
off the fitted spline.

Thanks again,

Alan Morris
Research Engineer - Gait Lab
Bloorview MacMillan Centre
350 Rumsey Road
Toronto, Ontario
CANADA
M4G-1R8
Tel (416) 425-6220 x3508
Fax (416) 425-1634
email morrisa@ecf.utoronto.ca


Original Posting
> Hello BIOMCH-L readers,
>
> I am working in gait biomechanics and am writing code to fill in missing
> data from streams of 3-dimensional co-ordinate data. Our system generates
> 0 values in the co-ordinate file when a marker is out of camera-system
> view. Thus far I have tried polynomial curve fitting of varying orders
> based on datapoints prior to the missing value, and extrapolating the
> value. This method only met with limited success as the movement in
> different axes has behaviour of different (polynomial curve) orders. If
> the gap of missing markers is too large, the extrapolated point estimation
> diverges greatly, depending on the order of the polynomial fit.
>
> The second method I have tried is to fit a cubic spline to datapoints
> prior to the missing point in question. This is met with limited success.
>
> Questions:
>
> 1. Most, if not all interpolation procedures that I know of require
> equally spaced data; thus if there is a gap in ones dataset, a polynomial
> curve or spline cannot be fit to the dataset! Could anyone confirm this
> statement?
>
> 2. I would like to know from individuals that use movement data (gait and
> others), what types of extrapolation or curve-fitting procedures are
> commonly being used.
>
> 3. Does anyone know of a 3-dimensional spline technique whereby one can
> utilize all x,y,z co-ordinate data to extrapolate the next point(s)!
>
> I will post a follow-up with replies.
>
> Thanks
>
> Alan Morris



Subject: Re: Extrapolation techniques to fill gaps in movement data
------------------------------------------------------------------------------

Have you tried the ISB home page under the software page they have some curve
fitting code (quintic splines) that could help you. The code is in fortran
(have fun).

good luck.

Nelson Sierra

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

The extrapolation techniques we use are linear prediction (preferred)
and least squares (polynomial fitting). We have a paper currently in
press (Journal of Biomechanics), and you will be able to download the
program for the linear prediction extrapolation from ISB WWW (I 've
sent the files just three days ago !!!, and Denise is working on
that). If you want I can send you a photocopy of the paper's preprint.

Regarding some of your specific questions.

> 1. Most, if not all interpolation procedures that I know of require
> equally spaced data; thus if there is a gap in ones dataset, a polynomial
> curve or spline cannot be fit to the dataset! Could anyone confirm this
> statement?

For not equally spaced data you can fit a spline, I think a cubic
spline will do.

> 3. Does anyone know of a 3-dimensional spline technique whereby one can
> utilize all x,y,z co-ordinate data to extrapolate the next point(s)!

Can't you deal with 1 dimension each time ? I haven't ever heard of a
3-D spline.

Hope this is useful and contact me if you need any more help.

Giannis Giakas
Division of SHE
Staffordshire University
Stoke-on-Trent ST4 2DF

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

If I understand your first question correctly, The answer is to use the
equally spaced data before and after the data break, and replace the
missing data at the same interval, considering that the missing data occurs
over time t which is a integer multiple of the sampling rate of the present
data. The larger the break and higher the curvature of the missing curve,
compared to the curvature of the data present before and after the break,
the poorer the fit using a polynomial.
As for your second question, the most common are IMHO 3rd order
polynomial, as this is the easiest to implement.
Finally, there are a few protocols which implement non single
dimension interpolations, but they primarily depend upon the body model
used, and the number of markers available. If more than three markers are
used per segment, (an over determined solid body model) the paper by Spoor
& Velpaus (sp?) describes the algorythm. This only works if the segment is
determined, not under determined. If the data is underdetermined, (less
than three markers per segment) the segment based interpolation function
(or some variation on it can be used. I've attached an abstract of my own
work on the subject.

I hope this helps. But consider this. From a clinical standpoint, I don't
know of a study which shows how much data interpolated or real is actually
needed for a proper clincial use. Ideally, it's preferable to have
continuous real data, but whats worse case acceptable? If the subject of
study is unstable or tires easily, and the data is questionable, where does
one draw the line between the fatigue factor and the quality of the data?

Sincerely,

Micah Forstein MS
Motion Lab Engineer
Childrens Hospital Los Angeles
forstein@hsc.usc.edu

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

Long time ago, I experimented a little with gap-filling in
kinematic data.

You wrote:
>1. Most, if not all interpolation procedures that I know of require
>equally spaced data; thus if there is a gap in ones dataset, a polynomial
>curve or spline cannot be fit to the dataset! Could anyone confirm this

No, spline interpolation or smoothing does not require equally
spaced data. If you use Woltring's GCVSPL, you can enter t,x(t)
pairs as data and t does not have to be sampled at equal
intervals. You can download several version of this software
from the ISB web site.

However, although the software can handle it, try to avoid *very*
unevenly spaced data. Two reasons:

(1) If you have many points clustered, the weighting of the
spline fit will be affected. The spline will be 'attracted` to
this cluster, and this mey be at the expense of poor fit
elsewhere.

(2) As you have noticed, higher order polynomials can exhibit
wild varations in large gaps. I found cubic splines to be quite
safe, but quintic splines tend to get out of control. To a
certain extent, you can suppress these wild variations by
smoothing more (lower cut-off frequency) while creating the
spline. But this fails if the duration of the gap approaches the
reciprocal of the maximal frequency in the movement data.

The advantage of using GCVSPL is that you do smoothing and
interpolation at the same time. This is statistically optimal.
If you do interpolation first, and then smoothing, the smoothing
algorithm has no way of knowing that some data is not real and it
will treat all data points with equal weight. So it may be
attracted too much to those 'unreal' data points.

>3. Does anyone know of a 3-dimensional spline technique whereby one can
>utilize all x,y,z co-ordinate data to extrapolate the next point(s)!

This is something I have never used, but there is a spline
package by Wood and Jennings (University of Western Australia)
that can produce splines with constraints. For instance, you can
smooth x,y,z trajectories of all markers simultaneously, while
requiring that all mutual distances between markers on the same
rigid body remains constant. This extra information can vastly
improve the results, especially if you are interpolating; it will
prevent wild oscillations in the data.

Try searching for their publication, and you may be able to get a
copy of the software. This is probably not for the faint of
heart, though.

-- Ton van den Bogert

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


1. I had added an interpolation routine to my QuickSAND program for
myself but had not put
the new version on the web. This is now done. The interpolation is
based on the parameters
set for the spline routine and will interpolate to either a new
number of points or to a new
sampling frequency.

QuickSAND (Quick Smoothing and Numerical Differentiation) is a quick and
friendly freeware program for the Power Macintosh. Available at

http://jaw.fmnh.org/Software/programs.html

2. Based on how I understand your question, It seems you want to
interpolate missing values
located between known values but are doing this by extrapolation from
the previous values.
The spline routine avoids this by interpolating based on values before
and after the missing
value. The spline routine can have unequally space points (hence
missing values) and the GCV
criterion to find the smoothing parameter should be good for
interpolating missing values
since this is essentially what cross-validation is doing. If you truly
want to extrapolate you
might want to try linear prediction, which is described, among other
places, in the Numerical
Recipes books.

Hope this helps

Jeff Walker

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

The GCV splines will do the trick in some cases. It still is important to
check the result closely. Packages by either either Woltring or Dohrmann and
Busby gave me about the same performance.

The conservative approach is straight-line interpolation. It may be more viable
over large gaps.

later

Mike Murphy

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

Based on what you said, I feel your problem is that of blending and not
extrapolating. You have a large gap between your data set. Perhaps spline
fit to your data prior and after the gap is no problem. For fitting the
best possible curve to the gap in your data you could use Bspline least
square or B-spline interpolation. (The functions are both in matlab they
are called: SPAP2 for least-squares approximation by splines or SPAPI for
spline interpolatin. I cut a portion of an 3-D air foil and regenerated the
missed portion by SPAP2. It worked fine. The shape of airfoil seems to be
more complicated than gait trajectories.

regarding your 3 questions:
1) Both polynomial fit and spline fit can work fine with unequally spaced
data. Thus, the first comment is not correct. (try it for yourself in
matlab)

2) I used lowest order possible spline fit to my data without being very
unforgiving to the possible errors as when dealig with 3-D imaging of
segments, there are so many thing to worry about, and a lot other
approximations are involved. As well, Milad Ishac and Dr. David Winter have
a developed a software (KINGAIT I Think) that allows you manually or with
interpolation move a data point and look at the effect on three different
planes.

3) The spline techniques are not supposed to care whether your model is 2-D
or 3_D. Both mentioned functions in matlab work for 3-D data set. Maybe I
am not understanding your third question. Any way, If you play around with
the number of knots in SPAP2 matlab function, I feel you will get very
satisfactory fit.

mehran armand

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

I'm not clear what you are asking because in your three questions you
cover interpolation, extrapolation and approximation. Each of these are
different and have different solution methods. However, I'll try and
answer what I think your questions are.

> 1. Most, if not all interpolation procedures that I know of require
> equally spaced data; thus if there is a gap in ones dataset, a polynomial
> curve or spline cannot be fit to the dataset! Could anyone confirm this
> statement?

Interpolating and approximating polynomials and splines generally don't
require equal spacing between points. However, having equally spaced
points massively reduces the problem and equal spacing is the norm in a
lot of applications. One or both of these factors may be why generic
routines don't allow you to work with gaps in your data.

An example of the more extreme end of spline interpolation (which also has
constraints to counter some of the problems of interpolation!) is in the
area of key frame animation:

Ramamoorthi, R., Ball, C. and Barr, A.H. (1997) Dynamic splines with
constraints for animation. Technical Report CS-TR-97-03. California
Institute of Technology. ftp://ftp.cs.caltech.edu/tr/cs-tr-97-03.ps.Z

Least squares approximating polynomials (which I infer from the
"curve-fitting" reference in question 2 is what you're after - but I might
be wrong!) don't require equally spaced points. They are based on
minimising the least squares deviation between the raw y=f(x) data and a
set of predicted y data (at each raw x data point; P(y)).

> 2. I would like to know from individuals that use movement data (gait and
> others), what types of extrapolation or curve-fitting procedures are
> commonly being used.

It is generally not a good idea to extrapolate missing data points or,
especially, extrapolate beyond your data. There are some instances where
it is reasonable and/or necessary (eg. in key frame animation and for some
real-time biomechanical feedback methods that are developing) but
generally, for biomechanics applications at least, it should be avoided if
at all possible (or at worst it should be stated explicitly that
interpolation/extrapolation has taken place AND it MUST be justified).

The reason why extrapolation/interpolation is an exercise that needs very
careful justification is because of what you're actually doing. This is
best expressed by looking at dictionary definitions:

Interpolate: to change by the placement of new matter, esp. secretly or
without authorisation (furbished, altered, falsified).

Extrapolate: to guess (what is not known) from that which is known;
conjecture.

> 3. Does anyone know of a 3-dimensional spline technique whereby one can
> utilize all x,y,z co-ordinate data to extrapolate the next point(s)!

Any approximating polynomial (splines are more difficult) can be used to
do this but not particularly well, mostly because of end-point problems.
Extrapolation is usually only conducted by looking at the problem in the
form of an initial-value problem (see any good numerical analysis book
for extrapolation methods) but this probably isn't applicable in your
case.

Good luck and be careful out there in your extrapolated world!

Russell Best
Victoria University
Melbourne, AUSTRALIA

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


Have you tried interpolating using data from both before and after the
missing value?

Andrew Pinder

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

I may be late with my reply, but anyway...

Just some remarks:
The polynoms can be quite useful, if you filter your data first.
You usually get small errors in coordinate reconstruction when a marker
dis/appears ie. at the beginning and the end of the gap. If you fit any
kind of curve on that data then you end up with huge bumps in the gap
instead of a smooth filling. If you smooth off the edges of the gap
first, then you have more chance. Still, I found it difficult to
implement the idea in software.
I haven't tried splines.
To make it simple I wrote a program to fill the gaps manually and it
worked surpisingly well. It reads ASCII data and scales a small section
of the displacement graph on the screen and allows you to fill the gap
with the mouse. Some students used it with nice results. I can dig out
the code if you are interested (Turbo Pascal 7.0).
Bye,
Gabor Barton, MD

-------------------------------------------------------------------
To unsubscribe send UNSUBSCRIBE BIOMCH-L to LISTSERV@nic.surfnet.nl
For more information: http://www.kin.ucalgary.ca/isb/biomch-l.html
-------------------------------------------------------------------