Interpolation with specified end derivatives

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