=?iso-8859-1?q?Discrete_B=E9zier_interpolation?=

Hi,

I'm currently trying to find a way to interpolate a 1-dimensional
signal using something like B=E9zier interpolation, my main problem
being that I don't know exactly what matches to what I want.

Basically, the signal that I want to interpolate is a user-created
sound envelope in order to modulate a signal with it. Therefore, I
consider windowed-sinc interpolation unsuitable due to the riples it
would create, as well as spline interpolation, because it makes the
curve have to go through the original points and thus you can get the
"overshoot" effect that I want to avoid. The user-created envelope has
a fixed sampling rate which is the sampling rate of the desired
resulting signal divided by a certain ratio, for example 72.

The B=E9zier interpolation sounds suitable, however I find that there
are two problems with it. The first is that I don't see how to directly
obtain equally spaced points, and secondly it seems that it would take
an order as high as I have original points, and I absolutly want to
avoid that, not even because of the computational cost but because I
want my original points to have an influence limited to the very close
neighborhood.

As hard as I've looked on Google, mostly anything I've found about the
B=E9zier interpolation and such applies to 2D vector graphics and 3D,
which is also vector graphics, and hardly anything related to 1D
signals with a fixed sampling rate.

So what I'm looking for is a method for interpolating 1D fixed sampling
rate signals into a 1D fixed sampling rate signal which sampling rate
would be the original sampling rate mutiplied by a certain factor, the
curve would have to go through is original points, to avoid any
overshoot/riple effect, and, in order to limit the influence of
original points, no point shall need more than 4 original points to be
calculated.

Thanks in advance

Michel Rouzic wrote:
>
> Basically, the signal that I want to interpolate is a user-created
> sound envelope in order to modulate a signal with it. Therefore, I
> consider windowed-sinc interpolation unsuitable due to the riples it
> would create, as well as spline interpolation, because it makes the
> curve have to go through the original points and thus you can get the
> "overshoot" effect that I want to avoid. The user-created envelope has
> a fixed sampling rate which is the sampling rate of the desired
> resulting signal divided by a certain ratio, for example 72.

i dunno how to do Bezier, but it seems to me, if you are not needing to
go exactly through the original points, you can use a windowed moving
average.  essentially a LPF where the impulse response is the window
function for smoothing.

FWIW,

r b-j

Check out Catmull-Rom splines.  An example of various splines is at:

http://www.cse.unsw.edu.au/~lambert/splines/

-- 
Marco
________________________
Marc Reinig
UCO/Lick Observatory
Laboratory for Adaptive Optics

"Michel Rouzic" <Michel0528@yahoo.fr> wrote in message 
news:1160720651.332717.290830@h48g2000cwc.googlegroups.com...
Hi,

I'm currently trying to find a way to interpolate a 1-dimensional
signal using something like B&#4294967295;zier interpolation, my main problem
being that I don't know exactly what matches to what I want.

Basically, the signal that I want to interpolate is a user-created
sound envelope in order to modulate a signal with it. Therefore, I
consider windowed-sinc interpolation unsuitable due to the riples it
would create, as well as spline interpolation, because it makes the
curve have to go through the original points and thus you can get the
"overshoot" effect that I want to avoid. The user-created envelope has
a fixed sampling rate which is the sampling rate of the desired
resulting signal divided by a certain ratio, for example 72.

The B&#4294967295;zier interpolation sounds suitable, however I find that there
are two problems with it. The first is that I don't see how to directly
obtain equally spaced points, and secondly it seems that it would take
an order as high as I have original points, and I absolutly want to
avoid that, not even because of the computational cost but because I
want my original points to have an influence limited to the very close
neighborhood.

As hard as I've looked on Google, mostly anything I've found about the
B&#4294967295;zier interpolation and such applies to 2D vector graphics and 3D,
which is also vector graphics, and hardly anything related to 1D
signals with a fixed sampling rate.

So what I'm looking for is a method for interpolating 1D fixed sampling
rate signals into a 1D fixed sampling rate signal which sampling rate
would be the original sampling rate mutiplied by a certain factor, the
curve would have to go through is original points, to avoid any
overshoot/riple effect, and, in order to limit the influence of
original points, no point shall need more than 4 original points to be
calculated.

Thanks in advance

Michel Rouzic wrote:
> =

> Hi,
> =

> I'm currently trying to find a way to interpolate a 1-dimensional
> signal using something like B=E9zier interpolation, my main problem
> being that I don't know exactly what matches to what I want.
> =

> Basically, the signal that I want to interpolate is a user-created
> sound envelope in order to modulate a signal with it. =


I'm not understanding your statement of the problem. Are you writing
software? Do you want to have the user create a curve interactively on
screen? This curve will represent the shape of your sound envelop (which
I'm guessing, the software will then playback)? Where does the
interpolation part come in? Once the curve is defined - do you want to
be able to evaluate the curve at any arbitrary point so that you can
display it to the screen and use it for adjusting the gain of the sound
signal. Is the problem what sort of user input will be needed to create
this curve that represents the envelope?

-jim =




>Therefore, I
> consider windowed-sinc interpolation unsuitable due to the riples it
> would create, as well as spline interpolation, because it makes the
> curve have to go through the original points and thus you can get the
> "overshoot" effect that I want to avoid. The user-created envelope has
> a fixed sampling rate which is the sampling rate of the desired
> resulting signal divided by a certain ratio, for example 72.
> =

> The B=E9zier interpolation sounds suitable, however I find that there
> are two problems with it. The first is that I don't see how to directly=

> obtain equally spaced points, and secondly it seems that it would take
> an order as high as I have original points, and I absolutly want to
> avoid that, not even because of the computational cost but because I
> want my original points to have an influence limited to the very close
> neighborhood.
> =

> As hard as I've looked on Google, mostly anything I've found about the
> B=E9zier interpolation and such applies to 2D vector graphics and 3D,
> which is also vector graphics, and hardly anything related to 1D
> signals with a fixed sampling rate.
> =

> So what I'm looking for is a method for interpolating 1D fixed sampling=

> rate signals into a 1D fixed sampling rate signal which sampling rate
> would be the original sampling rate mutiplied by a certain factor, the
> curve would have to go through is original points, to avoid any
> overshoot/riple effect, and, in order to limit the influence of
> original points, no point shall need more than 4 original points to be
> calculated.
> =

> Thanks in advance

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

jim wrote:
> Michel Rouzic wrote:
> >
> > Hi,
> >
> > I'm currently trying to find a way to interpolate a 1-dimensional
> > signal using something like B=E9zier interpolation, my main problem
> > being that I don't know exactly what matches to what I want.
> >
> > Basically, the signal that I want to interpolate is a user-created
> > sound envelope in order to modulate a signal with it.
>
> I'm not understanding your statement of the problem. Are you writing
> software? Do you want to have the user create a curve interactively on
> screen? This curve will represent the shape of your sound envelop (which
> I'm guessing, the software will then playback)? Where does the
> interpolation part come in? Once the curve is defined - do you want to
> be able to evaluate the curve at any arbitrary point so that you can
> display it to the screen and use it for adjusting the gain of the sound
> signal. Is the problem what sort of user input will be needed to create
> this curve that represents the envelope?

Yes I am writing software. The software is non-interactive. The user
input is actually an image, the envelope is defined by the values of
one line in the image. That one line is considered an envelope with a
certain sampling rate, interpolated to the sampling rate of the signal
to modulate.

If you're wondering what can be the point of doing this, each line of
the user-created image file represents an envelope, each line matching
to a different signal, which is either a narrow bandwidth noise or a
sine, their bandwidth or frequency being determined by the position of
the line in the image, and a few user set parameters. Once every
envelope is interpolated and modulated with its matching signal,
everything is mixed together into a single signal and written to a
sound file.

robert bristow-johnson wrote:
> Michel Rouzic wrote:
> >
> > Basically, the signal that I want to interpolate is a user-created
> > sound envelope in order to modulate a signal with it. Therefore, I
> > consider windowed-sinc interpolation unsuitable due to the riples it
> > would create, as well as spline interpolation, because it makes the
> > curve have to go through the original points and thus you can get the
> > "overshoot" effect that I want to avoid. The user-created envelope has
> > a fixed sampling rate which is the sampling rate of the desired
> > resulting signal divided by a certain ratio, for example 72.
>
> i dunno how to do Bezier, but it seems to me, if you are not needing to
> go exactly through the original points, you can use a windowed moving
> average.  essentially a LPF where the impulse response is the window
> function for smoothing.

So basically I'd convolve my zero-stuffed signal with a (for example)
blackman window? I've already considered that before, as it would get
me pretty close to the result, but there's only one problem with it, it
should introduce scalopping on sloppy parts of my envelope, and I want
to avoid that.

Marc Reinig wrote:
> Check out Catmull-Rom splines.  An example of various splines is at:
>
> http://www.cse.unsw.edu.au/~lambert/splines/

Great link, thanks a lot, that's what I really needed. From giving
every method on this site a try, it seems that the cubic B-spline
matches exactly to what I'm looking for. The Catmull-Rom splines go
through the original points and therefore aren't suitable.

Now that I know this, one problem remains. Apparently the cubic
B-spline interpolation is based on putting together cubic B=E9zier
segments, so the implementation should be very similar, which means
that the problem of calculating directly my equally-spaced remains, and
since mostly any documentation online on B=E9zier interpolation is all
about 2D or 3D vectorial interpolation, I need help to find out how to
do that.

Michel Rouzic wrote:

> So what I'm looking for is a method for interpolating 1D fixed
> sampling rate signals into a 1D fixed sampling rate signal which
> sampling rate would be the original sampling rate mutiplied by a
> certain factor, the curve would have to go through is original
> points, to avoid any overshoot/riple effect, and, in order to
> limit the influence of original points, no point shall need more
> than 4 original points to be calculated.

Sounds like this paper I found linked somewhere just yesterday is a 
match: http://adsabs.harvard.edu/abs/1990A&A...239..443S
It gives a piecewise cubic interpolator with monotone pieces and a 
continuous first derivative.


Martin

-- 
Quidquid latine scriptum sit, altum viditur.

Michel Rouzic wrote:

> 
> Yes I am writing software. The software is non-interactive. The user
> input is actually an image, the envelope is defined by the values of
> one line in the image. That one line is considered an envelope with a
> certain sampling rate, interpolated to the sampling rate of the signal
> to modulate.
> 

A b-spline typically has the same basis functions as beziers. That is,
the b-spline is composed of bezier spans with constrained continuity at
the joints. There are pretty much 2 ways you can use your data points to
define a continuous b-spline curve that can be evaluated at any point
you like. 
	The easiest is to use the data points as the control points for the
curve and then when you compute the value of the curve at a between
point is just the weighted sum of the points in the immediate
neighborhood. For instance, for a cubic b-spline you have the weighted
sum of 4 points (2 on each side of the point being evaluated). The
calculation can be using the standard cubic polynomial form. This will
produce a smooth curve that does not pass thru the points. The
coefficients can be the standard b-spline coefficients (bezier) or other
forms. 
	What that is doing is creating a curve that passes thru a filtered
version of your original points. The filter is just a simple FIR low
pass filter. To get your curve to pass thru the data points you would
need to first apply the inverse of that FIR and then use the new set of
points to create the curve. Technically the inverse needs to be an IRR
filter applied in both directions. But it can also be done with another
FIR that is a truncated version of the IRR's. Doing it that way means
the curve won't pass perfectly thru the points but can be very close and
usually results in a smoother curve.

-jim
	




> If you're wondering what can be the point of doing this, each line of
> the user-created image file represents an envelope, each line matching
> to a different signal, which is either a narrow bandwidth noise or a
> sine, their bandwidth or frequency being determined by the position of
> the line in the image, and a few user set parameters. Once every
> envelope is interpolated and modulated with its matching signal,
> everything is mixed together into a single signal and written to a
> sound file.

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----