LinuxQuestions.org
Support LQ: Use code LQ3 and save $3 on Domain Registration
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 02-28-2005, 02:46 AM   #1
leonidg
Member
 
Registered: Dec 2004
Posts: 73

Rep: Reputation: 15
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
 
Old 03-02-2005, 12:25 PM   #2
jim mcnamara
Member
 
Registered: May 2002
Posts: 964

Rep: Reputation: 34
Numerical recipes in C.

The book is online free here:

http://www.library.cornell.edu/nr/bookcpdf.html
 
Old 03-02-2005, 04:50 PM   #3
dakensta
Member
 
Registered: Jun 2003
Location: SEUK
Distribution: Debian & OS X
Posts: 194

Rep: Reputation: 35
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?
 
Old 03-03-2005, 03:51 AM   #4
leonidg
Member
 
Registered: Dec 2004
Posts: 73

Original Poster
Rep: Reputation: 15
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
 
Old 03-03-2005, 09:37 AM   #5
dakensta
Member
 
Registered: Jun 2003
Location: SEUK
Distribution: Debian & OS X
Posts: 194

Rep: Reputation: 35
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'.

Last edited by dakensta; 03-03-2005 at 12:14 PM.
 
Old 03-06-2005, 04:47 AM   #6
leonidg
Member
 
Registered: Dec 2004
Posts: 73

Original Poster
Rep: Reputation: 15
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
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



All times are GMT -5. The time now is 09:41 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration