Cubic interpolation
 

Hello, friends,
I need to implement a cubic interpolation function,
something similar to the griddata function in matlab.
The idea is that I have an image (matrix), where I
have some sampled points. According to that points I
need to fill the whole matrix. The speed is also an
issue in that task. Obviously it is a pretty usual
task and I wondered whether there are some
implementations in c (c++), or maybe someone could
give me some hints for the code.
Thanks in Advance,
Leonid

Numerical recipes in C.

The book is online free here:

http://www.library.cornell.edu/nr/bookcpdf.html

A little more information would help with where you are stuck ... griddata is a fairly complex function and calls an exernal routine - the qhull suite is freely downloadable, so maybe you could start from there.

Where are you specifically stuck? Understanding the algorithm, coding, libraries?

Hello, dakensta, friends,
As the matter of fact I am stuck in the beginning, the issue is not very urgent for me, so after looking on matlab code of the function griddata, I found that it is connected to other issues like triangulations etc. and then I decided to look for known algorithms of non-uniform interpolations, but unfortunately didn't find anything. After that I just decided to look for help in forums, and to tell You the truth this is the first time I get a reply.
Thanks for any help,
Leonid

It partly depends on what you want to do with the data you have. If you ask five different people in five different fields you will get twenty five different answers ;)

If you want to pursue this, I suggest starting with the wikipedia article on interpolation (mostly focuses on 2D but the principles extend to 3 or more dimensions).

As a rough overview (which you probably already know) the key is finding a function from known output and input values that allows you to calculate a results where the outputs are unknown.

Finding this function can be performed using a number of different methods which depend principally on the function in question. Some will be performed explicity (plug known numbers into a function and it return parameters) others need to iterate repeatedly until an optimum set of parameters is found. Optimisation and searching are very big fields in themselves! You will find all sorts of variations which depend on the data itself and how reliable it is etc etc. but try not to lose sight of the fact that they are basically trying to do the same thing. (several methods are explained in the numerical recipe book linked above).

The other main facet is where the function is applied - locally to just a few points in a matrix (local areas could be determined using a triangulation method, for example), recalculating the function repeatedly over different points, or globaly over all your points. Naturally you also need to choose the right type of function to represent you data and the expected results.

A google for "scattered interpolation" turned up this file http://www.idiom.com/~zilla/Work/sca...erpolation.pdf (1.1Mb) which is a survey of scattered interpolation. It is not very good on it's own, I add, as it is a presentation and is obviously aimed at a specific audience and lacking the deatiled explanations of a text book or even web article but I think it gives enough terms for you to follow-up the specific methods.

A word of warning though - if you are not very mathematical (i.e. no university level mathematics, this includes me) some of it will look pretty ugly. Bear with it though, because the concepts are usually pretty straightforward - it is often just a matter of finding the right diagram or description at which point it will often 'click'.

dakensta, thanks again for your reply.
You touch the issue as a big research problem, and I really wanted to believe that it is pretty simple implemented by many other people task. I want to repeat what I have and what I need. Let's look on a problem as an image, say, size 1000*1000 pixels, where I know values of 10 pixels from the image, in different locations. I can also assume values for borders. What I need is to fill the whole image by interpolated values, using cubic interpolation as it is implemented in Matlab function griddata. I need it the same in C because of the speed matters, or at least the exact algorithm so I could implement it in my own. Because of the fact that the function is already implemented in Matlab, I really want to believe that it is implemented in C too. Other option is to use matlab compiler mcc, but I just didn't succeed doing it.
Thanks again, and hopefully my problem is more clear.
Leonid