DSPRelated.com
Forums

Interpolation with specified end derivatives

Started by jungledmnc January 2, 2009
robert bristow-johnson wrote:

> i think it's called Hermite polynomial interpolation or > something like that. Duane Wise and i did a paper about a > decade ago about comparing different polynomial interpolations > (Lagrange vs. Hermite vs. B- spline) for sampled audio but i > can't find it.
I have that PDF. Since you refer to this every now and then, I could upload it to www.musicdsp.org, with a pointer to Olli Niemitalo's paper too. What do you think? Martin -- Quidquid latine scriptum est, altum videtur.
On Jan 3, 2:13&#4294967295;pm, Martin Eisenberg <martin.eisenb...@udo.edu> wrote:
> robert bristow-johnson wrote: > > i think it's called Hermite polynomial interpolation or > > something like that. &#4294967295;Duane Wise and i did a paper about a > > decade ago about comparing different polynomial interpolations > > (Lagrange vs. Hermite vs. B- spline) for sampled audio but i > > can't find it. > > I have that PDF. Since you refer to this every now and then, I could > upload it towww.musicdsp.org, with a pointer to Olli Niemitalo's > paper too. What do you think?
i have it in pdf too. it would be fine by me, but i am not the sole author (nor the primary author). i'll try to contact Duane and see if he feels okay about it. as far as i'm concerned, if AES didn't publish it in the Journal, then i don't think their interest counts. i don't think the paper is earth-shattering. it was just that i did a short analytical study with drop-sample (ZOH) and linear interpolation to see how far up you would have to upsample (using a really good sinc- like interpolator with no images below the upsampled Nyquist to worry about) to get a specified S/N if it were linearly (or ZOH) interpolated and then down sampled (or re-sampled) resulting in all of those images above Nyquist (that are attenuated due to the sinc or sinc^2 frequency response) folding back into the baseband. this was as a means of implementing any arbitrary (and possibly changing, like in ASRC) sample rate conversion ratio. the result i got to achieve 120 dB S/N for linear was about 2^9 and for ZOH about 2^19. expect your polyphase coef lookup table to be about 2^5 or 2^6 (the number of taps in the FIR) times bigger. Duane did some numerical crunching on it that roughly confirmed my analytic result for ZOH and linear interpolation. then he did it for 4-point (3rd order) Lagrange, Hermite, a higher-order osculating interpolator, and B-spline. B-spline had the best S/N (but also attenuated the baseband at higher frequencies, which would need to be compensated) and i sorta figured out why which i put into the presentation of the paper (but i don't think is in the paper). the reason is that the B-spline is really just the ZOH (sinc in the frequency domain) and linear (sinc^2) carried to a higher order (sinc^ (order+1)). for the same order of Lagrange or Hermite, there were other terms of lower order powers of sinc added to the sinc^(order +1). that made the notches at integer multiples of the upsampled frequency (where the images are) less deep. so the best frequency response we could hope for was a pure sinc^(order+1) function and anything added to it messed it up. or was, at least, less optimum. now, usually i think memory is cheaper than computation time, so i think using linear and having an 8K or 16K lookup table for coefficients is good enough. so the higher order (3rd) in the paper was more of an academic exercise. Olli took this much farther and did a more extensive study of it. i'll get a hold of Duane and see what he says about uploading it to music-dsp. r b-j
On Jan 3, 7:23&#4294967295;am, "jungledmnc" <jungled...@gmail.com> wrote:
> Thanks a lot guys! I expected cubic polynomials, but I just did not know > how to satisfy my needs. I like the bezier and hermite interpolations. > Btw. the thing is there is a book about interpolation with end derivatives > so I thought it is quite complicated. So I tried to think about some weird > stuff like aligning a circle, nonlinear (sine) interpolation between two > lines defined by the derivatives and such :-))... > > So thanks again! Finally something to study. > > There were some questions about purpose - this should be very realtime and > there may be many purposes - audio envelopes, signal shapes...
are you interpolating uniformly-sampled data and you just want to match the derivatives on both ends of the interpolated segment to the neighboring segments? that's a sorta solved problem. i have to find and dig up the paper to tell you exactly how the 4 FIR coefs are computed. but they're cubic functions of the fractional delay. not too expensive, but linear interpolation is a lot cheaper. r b-j
> >are you interpolating uniformly-sampled data and you just want to >match the derivatives on both ends of the interpolated segment to the >neighboring segments? that's a sorta solved problem. i have to find >and dig up the paper to tell you exactly how the 4 FIR coefs are >computed. but they're cubic functions of the fractional delay. not >too expensive, but linear interpolation is a lot cheaper. > >r b-j >
No no, I use the hermite interpolation for upsampling and such interpolation stuff a lot, but this time the value of the interpolation curve must be available for any point, any time, ... I think the hermite interpolation fits my needs! Thanks guys!
On Jan 3, 6:49&#4294967295;pm, "jungledmnc" <jungled...@gmail.com> wrote:
> >are you interpolating uniformly-sampled data and you just want to > >match the derivatives on both ends of the interpolated segment to the > >neighboring segments? &#4294967295;that's a sorta solved problem. &#4294967295;i have to find > >and dig up the paper to tell you exactly how the 4 FIR coefs are > >computed. &#4294967295;but they're cubic functions of the fractional delay. &#4294967295;not > >too expensive, but linear interpolation is a lot cheaper. > > > No no, I use the hermite interpolation for upsampling and such > interpolation stuff a lot, but this time the value of the interpolation > curve must be available for any point, any time,
that can also be accomplished with a regular-old polyphase filter bank (to upsample) *and* some polynomial interpolation that might be lower order (like 1st-order or linear interpolation). in fact, if memory is cheap and computational effort is expensive, the polyphase thing with linear interpolation between the upsampled points may be cheaper than, for each and every sample, figuring out 4 different coefficients each with a 3rd-order polynomial.
> ... I think the hermite > interpolation fits my needs! Thanks guys!
did you get the closed form for the hermite polynomials for all 4 coefficients? r b-j

robert bristow-johnson wrote:
> > On Jan 3, 6:49 pm, "jungledmnc" <jungled...@gmail.com> wrote: > > >are you interpolating uniformly-sampled data and you just want to > > >match the derivatives on both ends of the interpolated segment to the > > >neighboring segments? that's a sorta solved problem. i have to find > > >and dig up the paper to tell you exactly how the 4 FIR coefs are > > >computed. but they're cubic functions of the fractional delay. not > > >too expensive, but linear interpolation is a lot cheaper. > > > > > > No no, I use the hermite interpolation for upsampling and such > > interpolation stuff a lot, but this time the value of the interpolation > > curve must be available for any point, any time, > > that can also be accomplished with a regular-old polyphase filter bank > (to upsample) *and* some polynomial interpolation that might be lower > order (like 1st-order or linear interpolation). in fact, if memory is > cheap and computational effort is expensive, the polyphase thing with > linear interpolation between the upsampled points may be cheaper than, > for each and every sample, figuring out 4 different coefficients each > with a 3rd-order polynomial.
The OP didn't explain what he is doing but if it is that he needs to calculate a large number of points along a curve span there are very efficient recursive subdivision algorithms that would beat your polyphase filter method in both memory and computational cost. This is why bezier spans are used for generating the 1000s of curve points you see displayed on your computer screen as you read this message. -jim
> > > ... I think the hermite > > interpolation fits my needs! Thanks guys! > > did you get the closed form for the hermite polynomials for all 4 > coefficients? > > r b-j
No no, I want to create an envelope consisting of several segments made
using different curve types and be able to access any point as quickly as
possible. So recursive subdivisions and such are not really the way here.
But thanks anyway!

dmnc

jungledmnc wrote:
> > No no, I want to create an envelope consisting of several segments made > using different curve types and be able to access any point as quickly as > possible.
When you say "as quickly as possible" Do you mean the method that you can get to working form as soon as possible or do you mean the method that executes in the least amount of time?
>So recursive subdivisions and such are not really the way here. > But thanks anyway! > > dmnc
> >When you say "as quickly as possible" Do you mean the method that you can
get to
>working form as soon as possible or do you mean the method that executes
in the
>least amount of time? > > >>So recursive subdivisions and such are not really the way here. >> But thanks anyway! >> >> dmnc >
Good question Jim :-)).. Sorry, I mean method that executes as quickly as possible.
On Jan 4, 11:44&#4294967295;am, "jungledmnc" <jungled...@gmail.com> wrote:
> >When you say "as quickly as possible" Do you mean the method that you can > >get to working form as soon as possible or do you mean the method that > >executes n the least amount of time? > > > Good question Jim :-)).. Sorry, I mean method that executes as quickly as > possible.
dmnc, can you be a little more specific about what you're doing? are you interpolating uniformly spaced points of an amplitude envelope? if so, what are the problems with using a big lookup table to get the weighting coefficients to combine adjacent samples? are they non- uniformly spaced? is there some reason you do not expect the interpolated value to be anything other than a linear combination of some set of adjacent points on both sides of the interpolated location? we understand you want infinite resolution on the location of the interpolated point. and that you want your interpolated function to be smooth. (why not more derivatives than just the 0th and 1st?) i don't think you are considering all of the issues when you repeat "no, no, ...". i suspect you do not understand what we're saying. r b-j