Interpolation w/ cubic convolution kernel - boundary treatment?

My problem is not dsp related, but the method is closely related to
methods in dsp, so I am hoping to get some help here.

I am using the symmetric cubic convolution kernel ("Catmull-Rom
splines") to interpolate data over a limited range in a variable x.
For the interpolation I am using typically 10 nodes which are
equidistant in x.
Example: The interpolated function between nodes 4 and 5 is computed
based on the data points at nodes 3,4,5,6
A nice property of the Catmull-Rom splines is that I get a continuous
1st derivative everywhere.

My question is now: how should I treat the ranges near the boundary?
With 10 nodes, how should I interpolate the data between node 9 and
10? So far I am using linear interpolation here - but this is
conceptually ugly (and it's not precise, although the latter is not my
biggest problem since I want a _nice_ solution).
I am especially worried that in my current approach the interpolated
function has no continuous 1st derivative at node 9.

Is there a solution, in which I could use e.g. a non-symmetric
convolution kernel to interpolate between nodes 9 and 10, based on the
nodes 8,9,10 or maybe 7,8,9,10 - in a way that I get a continuous 1st
derivative everywhere?
I have not found any discussion about the boundary-treatment in the
literature (and neither on the Google-wide web). In image processing
sometimes people mirror the image at the boundaries (i.e. they would
introduce a hypothetical 11th node for which the data value is set
equal to the data at the 9th node and then interpolate using the data
points at nodes 8,9,10,11) - but this would not work in my case.

What I really want in the end, is the _kernel_ for the interpolation
at
the boundaries.

Any help is appreciated!
Markus

On Apr 27, 2:00 am, Markus <iandj...@yahoo.com> wrote:
> My problem is not dsp related, but the method is closely related to
> methods in dsp, so I am hoping to get some help here.
>
> I am using the symmetric cubic convolution kernel ("Catmull-Rom
> splines") to interpolate data over a limited range in a variable x.
> For the interpolation I am using typically 10 nodes which are
> equidistant in x.
> Example: The interpolated function between nodes 4 and 5 is computed
> based on the data points at nodes 3,4,5,6
> A nice property of the Catmull-Rom splines is that I get a continuous
> 1st derivative everywhere.
>
> My question is now: how should I treat the ranges near the boundary?
> With 10 nodes, how should I interpolate the data between node 9 and
> 10? So far I am using linear interpolation here - but this is
> conceptually ugly (and it's not precise, although the latter is not my
> biggest problem since I want a _nice_ solution).
> I am especially worried that in my current approach the interpolated
> function has no continuous 1st derivative at node 9.
>
> Is there a solution, in which I could use e.g. a non-symmetric
> convolution kernel to interpolate between nodes 9 and 10, based on the
> nodes 8,9,10 or maybe 7,8,9,10 - in a way that I get a continuous 1st
> derivative everywhere?
> I have not found any discussion about the boundary-treatment in the
> literature (and neither on the Google-wide web). In image processing
> sometimes people mirror the image at the boundaries (i.e. they would
> introduce a hypothetical 11th node for which the data value is set
> equal to the data at the 9th node and then interpolate using the data
> points at nodes 8,9,10,11) - but this would not work in my case.
>
> What I really want in the end, is the _kernel_ for the interpolation
> at
> the boundaries.
>
> Any help is appreciated!
> Markus

The common way with natural cubic splines is the requirement that the
2nd derivative == 0 at the knots. But basically you have correctly
noticed that something must give at the endpoints. You need more
constraints than are given. What is important to your interpolated
function? Do you know the slope at the endpoints?

Clay

On Apr 27, 4:26 pm, Clay <phys...@bellsouth.net> wrote:
> On Apr 27, 2:00 am, Markus <iandj...@yahoo.com> wrote:
>
>
>
> > My problem is not dsp related, but the method is closely related to
> > methods in dsp, so I am hoping to get some help here.
>
> > I am using the symmetric cubic convolution kernel ("Catmull-Rom
> > splines") to interpolate data over a limited range in a variable x.
> > For the interpolation I am using typically 10 nodes which are
> > equidistant in x.
> > Example: The interpolated function between nodes 4 and 5 is computed
> > based on the data points at nodes 3,4,5,6
> > A nice property of the Catmull-Rom splines is that I get a continuous
> > 1st derivative everywhere.
>
> > My question is now: how should I treat the ranges near the boundary?
> > With 10 nodes, how should I interpolate the data between node 9 and
> > 10? So far I am using linear interpolation here - but this is
> > conceptually ugly (and it's not precise, although the latter is not my
> > biggest problem since I want a _nice_ solution).
> > I am especially worried that in my current approach the interpolated
> > function has no continuous 1st derivative at node 9.
>
> > Is there a solution, in which I could use e.g. a non-symmetric
> > convolution kernel to interpolate between nodes 9 and 10, based on the
> > nodes 8,9,10 or maybe 7,8,9,10 - in a way that I get a continuous 1st
> > derivative everywhere?
> > I have not found any discussion about the boundary-treatment in the
> > literature (and neither on the Google-wide web). In image processing
> > sometimes people mirror the image at the boundaries (i.e. they would
> > introduce a hypothetical 11th node for which the data value is set
> > equal to the data at the 9th node and then interpolate using the data
> > points at nodes 8,9,10,11) - but this would not work in my case.
>
> > What I really want in the end, is the _kernel_ for the interpolation
> > at
> > the boundaries.
>
> > Any help is appreciated!
> > Markus
>
> The common way with natural cubic splines is the requirement that the
> 2nd derivative == 0 at the knots. But basically you have correctly
> noticed that something must give at the endpoints. You need more
> constraints than are given. What is important to your interpolated
> function? Do you know the slope at the endpoints?
>
> Clay

Thanks for your reply!
Unfortunately there are no constraints on the slope.
For this reason I had proposed to use one more node on the
other side (inside the accessible range).
But I don't know how to use this to construct a kernel (which
would be non-symmetric).

Markus

"Clay" <physics@bellsouth.net> wrote in message : The common way with 
natural cubic splines is the requirement that the
: 2nd derivative == 0 at the knots.

You mean the knots at the end points.

 But basically you have correctly
: noticed that something must give at the endpoints.

Yes, unless you are clever.  You can insert a knot or point to make the 
first and second derivatives what ever you want at the end points.  The down 
side is that you need to insert points.

 You need more
: constraints than are given.

Yes, the extra points are the constraints. Where to place them is the trick.

Peter Nachtwey

On Apr 27, 2:00 am, Markus <iandj...@yahoo.com> wrote:
> My problem is not dsp related, but the method is closely related to
> methods in dsp, so I am hoping to get some help here.
>
> I am using the symmetric cubic convolution kernel ("Catmull-Rom
> splines") to interpolate data over a limited range in a variable x.
> For the interpolation I am using typically 10 nodes which are
> equidistant in x.
> Example: The interpolated function between nodes 4 and 5 is computed
> based on the data points at nodes 3,4,5,6
> A nice property of the Catmull-Rom splines is that I get a continuous
> 1st derivative everywhere.

sounds like Hermite polynomials.

> My question is now: how should I treat the ranges near the boundary?
> With 10 nodes, how should I interpolate the data between node 9 and
> 10? So far I am using linear interpolation here - but this is
> conceptually ugly (and it's not precise, although the latter is not my
> biggest problem since I want a _nice_ solution).
> I am especially worried that in my current approach the interpolated
> function has no continuous 1st derivative at node 9.
>
> Is there a solution, in which I could use e.g. a non-symmetric
> convolution kernel to interpolate between nodes 9 and 10, based on the
> nodes 8,9,10 or maybe 7,8,9,10 - in a way that I get a continuous 1st
> derivative everywhere?
> I have not found any discussion about the boundary-treatment in the
> literature (and neither on the Google-wide web). In image processing
> sometimes people mirror the image at the boundaries (i.e. they would
> introduce a hypothetical 11th node for which the data value is set
> equal to the data at the 9th node and then interpolate using the data
> points at nodes 8,9,10,11) - but this would not work in my case.
>
> What I really want in the end, is the _kernel_ for the interpolation
> at
> the boundaries.

quadratic polynomial?  now you have three constraints to satisfy
instead of four.

r b-j

On Apr 28, 11:36 am, robert bristow-johnson
<r...@audioimagination.com> wrote:
> On Apr 27, 2:00 am, Markus <iandj...@yahoo.com> wrote:
>
> > My problem is not dsp related, but the method is closely related to
> > methods in dsp, so I am hoping to get some help here.
>
> > I am using the symmetric cubic convolution kernel ("Catmull-Rom
> > splines") to interpolate data over a limited range in a variable x.
> > For the interpolation I am using typically 10 nodes which are
> > equidistant in x.
> > Example: The interpolated function between nodes 4 and 5 is computed
> > based on the data points at nodes 3,4,5,6
> > A nice property of the Catmull-Rom splines is that I get a continuous
> > 1st derivative everywhere.
>
> sounds like Hermite polynomials.
>
>
>
> > My question is now: how should I treat the ranges near the boundary?
> > With 10 nodes, how should I interpolate the data between node 9 and
> > 10? So far I am using linear interpolation here - but this is
> > conceptually ugly (and it's not precise, although the latter is not my
> > biggest problem since I want a _nice_ solution).
> > I am especially worried that in my current approach the interpolated
> > function has no continuous 1st derivative at node 9.
>
> > Is there a solution, in which I could use e.g. a non-symmetric
> > convolution kernel to interpolate between nodes 9 and 10, based on the
> > nodes 8,9,10 or maybe 7,8,9,10 - in a way that I get a continuous 1st
> > derivative everywhere?
> > I have not found any discussion about the boundary-treatment in the
> > literature (and neither on the Google-wide web). In image processing
> > sometimes people mirror the image at the boundaries (i.e. they would
> > introduce a hypothetical 11th node for which the data value is set
> > equal to the data at the 9th node and then interpolate using the data
> > points at nodes 8,9,10,11) - but this would not work in my case.
>
> > What I really want in the end, is the _kernel_ for the interpolation
> > at
> > the boundaries.
>
> quadratic polynomial?  now you have three constraints to satisfy
> instead of four.
>
> r b-j

Right: Quadratic Polynomials is what I need - but a special version:
one which has (at the left boundary) one point at the left, and two
points on the right side, i.e. a non-symmetric version.
I was no able to find a kernel for this. Do you know how such a kernel
looks like?

Markus

On Apr 27, 11:25 pm, "Peter Nachtwey" <pnacht...@comcast.net> wrote:
> "Clay" <phys...@bellsouth.net> wrote in message : The common way with
>
> natural cubic splines is the requirement that the
> : 2nd derivative == 0 at the knots.
>
> You mean the knots at the end points.
>
>  But basically you have correctly
> : noticed that something must give at the endpoints.
>
> Yes, unless you are clever.  You can insert a knot or point to make the
> first and second derivatives what ever you want at the end points.  The down
> side is that you need to insert points.
>
>  You need more
> : constraints than are given.
>
> Yes, the extra points are the constraints. Where to place them is the trick.
>
> Peter Nachtwey

Thanks for your reply. However in my specific case I can not use any
additional points. The problem requires to come up with an optimal
solution for a given set of (equidistant) points.
Markus

Markus wrote:

> Thanks for your reply!
> Unfortunately there are no constraints on the slope.
> For this reason I had proposed to use one more node on the
> other side (inside the accessible range).
> But I don't know how to use this to construct a kernel (which
> would be non-symmetric).

	I suspect that your use of the wording "convolution kernel" is a bit
fast and loose. A spline interpolation is equivalent to convolution when
it is used to shift the data. So if you have a time series of  N data
points you want to create a new series with N-2 points that is shifted
in time and lie in between the original your Catmull-Rom spline
interpolation would look identical to convolution. The actual kernel you
would be using would depend on the amount of shift. If you wanted to
compute the extra 2 data points at the beginning and end it would be
relatively easy to create a special kernel for the ends, but again what
that kernel would look like would depend on the amount of shift.

-jim

----== 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 =----

On Apr 29, 1:12 am, Markus <iandj...@yahoo.com> wrote:
> On Apr 28, 11:36 am, robert bristow-johnson
>
>
>
> <r...@audioimagination.com> wrote:
> > On Apr 27, 2:00 am, Markus <iandj...@yahoo.com> wrote:
>
> > > My problem is not dsp related, but the method is closely related to
> > > methods in dsp, so I am hoping to get some help here.
>
> > > I am using the symmetric cubic convolution kernel ("Catmull-Rom
> > > splines") to interpolate data over a limited range in a variable x.
> > > For the interpolation I am using typically 10 nodes which are
> > > equidistant in x.
> > > Example: The interpolated function between nodes 4 and 5 is computed
> > > based on the data points at nodes 3,4,5,6
> > > A nice property of the Catmull-Rom splines is that I get a continuous
> > > 1st derivative everywhere.
>
> > sounds like Hermite polynomials.
>
> > > My question is now: how should I treat the ranges near the boundary?
> > > With 10 nodes, how should I interpolate the data between node 9 and
> > > 10? So far I am using linear interpolation here - but this is
> > > conceptually ugly (and it's not precise, although the latter is not my
> > > biggest problem since I want a _nice_ solution).
> > > I am especially worried that in my current approach the interpolated
> > > function has no continuous 1st derivative at node 9.
>
> > > Is there a solution, in which I could use e.g. a non-symmetric
> > > convolution kernel to interpolate between nodes 9 and 10, based on the
> > > nodes 8,9,10 or maybe 7,8,9,10 - in a way that I get a continuous 1st
> > > derivative everywhere?
> > > I have not found any discussion about the boundary-treatment in the
> > > literature (and neither on the Google-wide web). In image processing
> > > sometimes people mirror the image at the boundaries (i.e. they would
> > > introduce a hypothetical 11th node for which the data value is set
> > > equal to the data at the 9th node and then interpolate using the data
> > > points at nodes 8,9,10,11) - but this would not work in my case.
>
> > > What I really want in the end, is the _kernel_ for the interpolation
> > > at
> > > the boundaries.
>
> > quadratic polynomial?  now you have three constraints to satisfy
> > instead of four.
>
> > r b-j
>
> Right: Quadratic Polynomials is what I need - but a special version:
> one which has (at the left boundary) one point at the left, and two
> points on the right side,

not quite, what you want is a quadratic polynomial that meets both
points on the left and right (as you say) but not a second point
further to the right, and the third constraint is match the derivative
on the right to the derivative of the 3rd order polynomial one segment
to the right.

r b-j



> i.e. a non-symmetric version.
> I was no able to find a kernel for this. Do you know how such a kernel
> looks like?
>
> Markus

On Apr 30, 8:41 am, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Apr 29, 1:12 am, Markus <iandj...@yahoo.com> wrote:
>
>
>
>
>
> > On Apr 28, 11:36 am, robert bristow-johnson
>
> > <r...@audioimagination.com> wrote:
> > > On Apr 27, 2:00 am, Markus <iandj...@yahoo.com> wrote:
>
> > > > My problem is not dsp related, but the method is closely related to
> > > > methods in dsp, so I am hoping to get some help here.
>
> > > > I am using the symmetric cubic convolution kernel ("Catmull-Rom
> > > > splines") to interpolate data over a limited range in a variable x.
> > > > For the interpolation I am using typically 10 nodes which are
> > > > equidistant in x.
> > > > Example: The interpolated function between nodes 4 and 5 is computed
> > > > based on the data points at nodes 3,4,5,6
> > > > A nice property of the Catmull-Rom splines is that I get a continuous
> > > > 1st derivative everywhere.
>
> > > sounds like Hermite polynomials.
>
> > > > My question is now: how should I treat the ranges near the boundary?
> > > > With 10 nodes, how should I interpolate the data between node 9 and
> > > > 10? So far I am using linear interpolation here - but this is
> > > > conceptually ugly (and it's not precise, although the latter is not my
> > > > biggest problem since I want a _nice_ solution).
> > > > I am especially worried that in my current approach the interpolated
> > > > function has no continuous 1st derivative at node 9.
>
> > > > Is there a solution, in which I could use e.g. a non-symmetric
> > > > convolution kernel to interpolate between nodes 9 and 10, based on the
> > > > nodes 8,9,10 or maybe 7,8,9,10 - in a way that I get a continuous 1st
> > > > derivative everywhere?
> > > > I have not found any discussion about the boundary-treatment in the
> > > > literature (and neither on the Google-wide web). In image processing
> > > > sometimes people mirror the image at the boundaries (i.e. they would
> > > > introduce a hypothetical 11th node for which the data value is set
> > > > equal to the data at the 9th node and then interpolate using the data
> > > > points at nodes 8,9,10,11) - but this would not work in my case.
>
> > > > What I really want in the end, is the _kernel_ for the interpolation
> > > > at
> > > > the boundaries.
>
> > > quadratic polynomial?  now you have three constraints to satisfy
> > > instead of four.
>
> > > r b-j
>
> > Right: Quadratic Polynomials is what I need - but a special version:
> > one which has (at the left boundary) one point at the left, and two
> > points on the right side,
>
> not quite, what you want is a quadratic polynomial that meets both
> points on the left and right (as you say) but not a second point
> further to the right, and the third constraint is match the derivative
> on the right to the derivative of the 3rd order polynomial one segment
> to the right.
>
> r b-j
>
>
>
> > i.e. a non-symmetric version.
> > I was no able to find a kernel for this. Do you know how such a kernel
> > looks like?
>
> > Markus- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
It is just a matter of sovling some simultaneous equations.  Second
order interplation equations.
x(f)=(1-f)*x0+f*x1+0.5*(x2-2*x1+x0)*f*(1-f)   for x0->x1
x(f)=(1-f)*x1+f*x2+0.5*(x2-2*x1+x0)*f*(1-f)   for x1->x2
f is a fraction from 0 to 1.

I don't see see why you are using a Catmull-Rom interpolator.  I
generated an arbitrary 3rd order equation to generate 4 points at
equal intervals.  The C-R couldn't even calculate the same
coefficients in my test equation.   So what makes C-R so special if it
isn't as accurate as other methods?  I would think that a 3rd order
inpolator should be able to reconstruct a third order polynomial
exactly from 4 points.

Peter Nachtwey