## Fast interpolation using radial basis functions

### Fast interpolation using radial basis functions

I have a problem of interpolating a 2D motion field. What I know is that the
motion field will be smooth (NO discontinuity) and I have some holes in it
which I need to fill. My data size is rather large: several thousands data
points and several thousand places to be interpolated as well. At the moment
I am trying to treat the horizontal and vertical component as two separate
2D surfaces and interpolate them separately using radial basis functions.
The trouble is: evaluating the coefficients for the RBFs from first
principles (i.e. inverting big matrices) is too time and memory consuming.
Does anyone out there know of a iterative method to solve the problem? I
would like an algorithm which is not too mathematical to understand.
Any help will be appreciated.

### Fast interpolation using radial basis functions

> I have a problem of interpolating a 2D motion field. What I know is that
the
> motion field will be smooth (NO discontinuity) and I have some holes in it
> which I need to fill. My data size is rather large: several thousands data
> points and several thousand places to be interpolated as well. At the
moment
> I am trying to treat the horizontal and vertical component as two separate
> 2D surfaces and interpolate them separately using radial basis functions.
> The trouble is: evaluating the coefficients for the RBFs from first
> principles (i.e. inverting big matrices) is too time and memory consuming.
> Does anyone out there know of a iterative method to solve the problem? I
> would like an algorithm which is not too mathematical to understand.
> Any help will be appreciated.

oops, I forgot. I was using exp(-ar^2) as my rbf function, but I think I can
also use thin plate spline
r^2.ln(r) with normalised coordinates (which lie within a unit square).

### Fast interpolation using radial basis functions

>I have a problem of interpolating a 2D motion field. What I know is that the
>motion field will be smooth (NO discontinuity) and I have some holes in it
>which I need to fill. My data size is rather large: several thousands data
>points and several thousand places to be interpolated as well. At the moment
>I am trying to treat the horizontal and vertical component as two separate
>2D surfaces and interpolate them separately using radial basis functions.
>The trouble is: evaluating the coefficients for the RBFs from first
>principles (i.e. inverting big matrices) is too time and memory consuming.
>Does anyone out there know of a iterative method to solve the problem? I
>would like an algorithm which is not too mathematical to understand.
>Any help will be appreciated.

Because of the size of the matrices you need to invert, interpolation
using radial basis functions is normally only useful when the number
of control points is limited. For large numbers of points, local
methods based on triangulation are much faster. If you really want to
use radial basis functions, consider that if you use exponential basis
functions with a reasonable radius, most of the matrix coefficients
will be extremely small. If you assume that any coefficient less than
some threshold is zero, you may be able to use some kind of sparse
matrix package, but inversion is going to be expensive in any case.

Jonathan Sachs
Digital Light & Color

### Fast interpolation using radial basis functions

>I have a problem of interpolating a 2D motion field. What I know is that the
>motion field will be smooth (NO discontinuity) and I have some holes in it
>which I need to fill. My data size is rather large: several thousands data
>points and several thousand places to be interpolated as well. At the moment
>I am trying to treat the horizontal and vertical component as two separate
>2D surfaces and interpolate them separately using radial basis functions.
>The trouble is: evaluating the coefficients for the RBFs from first
>principles (i.e. inverting big matrices) is too time and memory consuming.
>Does anyone out there know of a iterative method to solve the problem? I
>would like an algorithm which is not too mathematical to understand.
>Any help will be appreciated.

Mike Powell at the University of Cambridge has an efficient algorithm.  I
doubt that it is straightforward to implement.  However, he may have a

Tony

--

University of Southern Queensland   Phone:  (07) 4631 2943
Toowoomba, Queensland 4350          Fax:    (07) 4631 2721
AUSTRALIA               http://www.sci.usq.edu.au/~robertsa/home.html

I have a problem of interpolating a 2D motion field. What I know is that the
motion field will be smooth (NO discontinuity) and I have some holes in it
which I need to fill. My data size is rather large: several thousands data
points and several thousand places to be interpolated as well. At the moment
I am trying to treat the horizontal and vertical component as two separate
2D surfaces and interpolate them separately using radial basis functions.
The trouble is: evaluating the coefficients for the RBFs from first
principles (i.e. inverting big matrices) is too time and memory consuming.
Does anyone out there know of a iterative method to solve the problem? I
would like an algorithm which is not too mathematical to understand.
Any help will be appreciated.