Interpolation w/ cubic convolution kernel - boundary treatment?

On Apr 30, 10:39 am, Peter Nachtwey <p...@deltacompsys.com> wrote:
> 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- Hide quoted text -
>
> - Show quoted text -

Oops should be
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

Peter Nachtwey

On Apr 30, 12:41 pm, Peter Nachtwey <p...@deltacompsys.com> wrote:
> On Apr 30, 10:39 am, Peter Nachtwey <p...@deltacompsys.com> wrote:
>
>
>
> > 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- Hide quoted text -
>
> > - Show quoted text -
>
> Oops should be
> 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
>
> Peter Nachtwey

I have now found what I was looking for!
The following article describes in eq (5) a non-symmetric kernel for
interplations in the region close to the boundary (and one half is
identical to the Catmull-Rom kernel):
G.-H. Cottet, P. Poncet, "Advances in direct numerical simulations of
3D wall-bounded flows by Vortex-in-Cell methods", J Comp. Phys 193
(2003) 136.
The document is here:
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHY-49R5FDD-1&_user=3902909&_coverDate=01%2F01%2F2004&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000061728&_version=1&_urlVersion=0&_userid=3902909&md5=66c343753edd5ab1a12655ecff09c7a6

Thanks to everybody for your input,
Markus