Re: cubic convolution interpolation at boundaries?

On Apr 27, 5:42 pm, Fred Krogh <fkr...@xxxxxxxxxxxxxxxx> wrote:
Markus wrote:
On Apr 26, 5:35 pm, Fred Krogh <fkr...@xxxxxxxxxxxxxxxx> wrote:
Markus wrote:
On Apr 25, 5:00 pm, Fred Krogh <fkr...@xxxxxxxxxxxxxxxx> wrote:
Markus wrote:
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 between 8 and 12 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
My question is: how should I treat the ranges near the boundary?
If I am using 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 - and which results in 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 interpolate using the data
points at nodes 8,9,10,11) - but this would not work in my case.
Any help is appreciated!
Markus
The algorithm here,http://mathalacarte.com/cb/mom.fcg/ya58, generates
an interpolant with a continuous derivative. For the cubic case the
interpolant can be thought of as a linear combination of two quadratics
if there are two points on either side of the interpolation point. If
there are not two points on either side of the interpolation point, then
the quadratic using the nearest three points is used. For more details
see the link above.
Fred
This sounds pretty good. I think that my cubic convolution
interpolation kernel (the Catmull-Rom splines) is exactly what you
describe: a linear combination of two quadratics. And it is
straightforward to use your proposed method to compute the
interpolated result within the range near the boundary,
But my point is that I'm interested in how the _kernel_ looks like and
I'm not sure how to derive the kernel for a quadratic using the
nearest three points (for the ranges at the boundary). Do you know
the formula for this kernel?
Markus
The code mentioned above uses standard divided differences as described
in: "Fred T. Krogh, Efficient algorithms for polynomial interpolation
and numerical differentiation, Math. of Comp. 24, 109 (Jan. 1970)
185--190." The highest order difference is used differently than when
doing the usual cubic interpolation. I'm sorry, but I'm not clear on
what you mean by the kernel.
Fred

Thanks, I have already printed your paper but it does not provide the
answer that I'm looking for.

By 'kernel' I mean the function which determines the weights to be
assigned to the samples
of the data at the four surrounding nodes in order to compute the
value of the interpolant.

In detail:
At the position t, the interpolant I(t) is given by a sum over all
nodes i
which are located at positions t_i (i=1,2,3,...10). The sum contains
the product
of the data value d_i at node i times a weight f(t-t_i).
The function f(t-t_i) is the "kernel" of the interpolation (in signal
processing also
referred to as "impulse response")

I(t) = sum_i ( d_i f(t-t_i) )

The kernel for the Catmull-Rom Kernel is given by:
f(x) =
3/2 |x|^3 - 5/2 |x|^2 +1 if 0<= |x| < 1
-1/2|x|^3 + 5/2 |x|^2 -4 |x| +2 if 1<= |x| < 2
0 else

This works for all bins for which one has four support nodes, in other
words
for the whole region, except for the two intervals near the
boundaries.
Is it possible to write down a corresponding weight function (=kernel,
or impulse response) for your suggested quadratic solution near the
boundaries?
Markus

Generally one is better off using the difference form. But I believe
what you want is the Lagrange form rather than the Newton form of the
interpolating polynomial. Any introductory book on numerical analysis
should give this form and Google will give it to you online, search for
Lagrange interpolating polynomial. You will then need to take a linear
average of two of these to get the coefficients you want.
Fred

What you describe requires to have two nodes on either sider of the
interpolation interval. These are are not available for the first and
for the last intervals. E.g. in the first interval only a single point
on the left is available.
Markus

.

Relevant Pages

  • Re: cubic convolution interpolation at boundaries?
    ... For the interpolation I am using between 8 and 12 nodes which are ... convolution kernel to interpolate between nodes 9 and 10, ... sometimes people mirror the image at the boundaries (i.e. they would ... a linear combination of two quadratics. ...
    (sci.math.num-analysis)
  • Re: cubic convolution interpolation at boundaries?
    ... For the interpolation I am using between 8 and 12 nodes which are ... convolution kernel to interpolate between nodes 9 and 10, ... sometimes people mirror the image at the boundaries (i.e. they would ... a linear combination of two quadratics. ...
    (sci.math.num-analysis)
  • Re: cubic convolution interpolation at boundaries?
    ... For the interpolation I am using between 8 and 12 nodes which are ... convolution kernel to interpolate between nodes 9 and 10, ... I have not found any discussion about the boundary-treatment in the ... a linear combination of two quadratics. ...
    (sci.math.num-analysis)
  • Re: cubic convolution interpolation at boundaries?
    ... For the interpolation I am using between 8 and 12 nodes which are ... convolution kernel to interpolate between nodes 9 and 10, ... I have not found any discussion about the boundary-treatment in the ... a linear combination of two quadratics. ...
    (sci.math.num-analysis)
  • Re: Gibbs phenomenon
    ... I am trying to use 1D sinc interpolation, ... The Gibbs phenonmenon is a direct result of using a sinc. ... the way around this is to use a different kernel ...
    (comp.dsp)
Loading