Interpolation Function in C or C++

finnpark

Hello Everyone,

I am trying to source a reliable function to carry out interpolation. It is for average out speech contents for speech recognition using C/C++.

There are a lot of Interpolation functions on the net but could anyone reccommend a good reliablke one, perhaps one they have used before themselves.

Thanks

satchmo

What sort of interpolation? If you're after simple linear interpolation, then it's just a matter of calculating ((1-x)A+xB) to interpolate between A and B, where x is the interpolant in the range [0,1], and A and B are the values to interpolate between. If you're after a more accurate way of interpolating (very likely given what you're doing), you'll need to read up more... like this for starters: http://en.wikipedia.org/wiki/Interpolation

finnpark

Thanks for that.

It would be La Grange Interpolation that I would be Interested in.

Talliesin

finnpark wrote:

It would be La Grange Interpolation that I would be Interested in.

A public-domain C++ library that includes such functionality is available at <http://okmij.org/ftp/packages.html#cpp.linalg>.

finnpark

Thanks for that , this may do the trick.

silverside

Numerical Recipes book (free online at www.nr.com) is a good first port of call.

finnpark

Hello Everyone Again,

I have just discovered that Linear Interpolation will do the trick for me.

I am currently using the interp1 function in Matlab, which uses Linear Interpolation by default. This is the Matlab Function Definition:http://www.mathworks.com/access/helpdesk/help/techdoc/ref/interp1.html.

newy=interp1(oldx,oldy,newx);


newy=8*124 matrix with a total of 55 steps between rows instead of 124(this is what will be returned)

oldy = 8*124 matrix which goes from 1:124 in steps of 1
oldx = 124*1 in steps of 1
newx = 124*1 with a total of 55 steps between rows insted of 124 in oldx




Here is my Matlab code in total that I am tring to convert to C:

%Open the .mfc file below that was created bt the FEP        
        name= sprintf('c%dr%d.mfc',j,i);                                    % Get the name of the .mfc file   
        infileb = fopen(name,'rb');                                                       % Read the .mfc file
        mfc_contents1=fread(infileb,[8,inf],'double');                                    % Read file contents into matrix 
        fclose(infileb);                                                                  % Close the .mfc file
        
      
        % There should be 61 frames in each. Use the length function to find number of columns/frames
        num_frames = (length (mfc_contents1));                                                                %Find the number of frames in each repition of each file    
        % num_frames contains the number of frames per file
        
        
        % 1:length will be the current distance of the .mfc file read in with 1 in between each frame   
        oldx = 1:num_frames;      % Current X-axis 
        
        
       
        %The new distance between each frame
        % Lets average it out
        %1:new distance between frames:final frame number
        newx = 1:((num_frames-1)/(averageframes-1)):num_frames;                                                                       %New .mfc file distance. Frames will be seperate by a new distance due to the average defined at the top
        
       
        % Interp1(x, old y , new  x)
        % Interpolate below using the interp1 function
        mfc_contents2= (interp1(oldx,mfc_contents1',newx))';       
        % The new Y is returned in the matrix

For example: I am sending an old x value of 1:124 in steps of 1, new x value from 1:124 in certain smaller steps(only 55 steps), and I send Oldy which is from 1:124 in steps of 1 but is 8 numbers wide (oldy is a 124*8 matrix). I get back the interpolated newy value which will be 55 steps long from 1:124. Hope this makes sense.
Basically I want to interp a 8*124 matrix in steps of 1 to a 8*124 matrix with 55 steps max.

Thanks for any advice in advance and apologies for any unclear pts.

silverside

have you looked at the numerical recipes link i posted?
do you mean you just interpolate along one dimension?

should be a simple if tedious function to write, draw a graph, it will make things clearer.
basically
for each row
new x value(i) = 1 + (124-1)/54 * i (for i = 0 to 54)
at each x value
find max j where old_x_value(j) < new_x_value(i)

interpolate between old_y_value(j) and old_y_value(j+1) using
new_y_value(i) = old_y_value(j) + (new_x_value(i) - old_x_value(j))/(old_x_value(j+1)/old_x_value(j))*(old_y_value(j+1)-old_y_value(j))

tidy up the code, error check it, apply it to each row in the matrix, should work.

finnpark

Thanks lads,

I think I have it sorted now.

finnpark

Hello Again,

I have a prblem interpolating the Y axis. I have done the x-axis. Shown Below are the answrers that matlab produced for a single column for both x and y.

OldY

---

1.-> 2.3669
2.-> 2.1952
2.2010
2.1834
2.1139
2.1198
2.1778
2.2107
2.2020
2.1954
-
-
-
123.-> 2.3626
124.-> 2.2396

---

NewY
1.-> 2.3669
2.-> 2.1961
2.1172
2.2052
2.1963
2.1990
2.2109
2.1970
2.2104
2.2020
-
-
-
54.-> 2.4398
55.-> 2.2396

---

OldX
1.-> 1
2.-> 2
3
4
5
6
7
8
9
10
11
-
-
-
123-> 123
124-> 124

---

NewX(increased in steps of 2.2778)

1.-> 1.0000
2.-> 3.2778
5.5556
7.8333
10.1111
12.3889
14.6667
16.9444
19.2222
21.5000
23.7778
26.0556
-
-
-
54.-> 121.7222
55.-> 124.0000

---

Can anyone tell me how the newy was calculated, say how did 2.1952 in position2 on the old y become 2.1961 in position 2 in the new y?.

Basically what I am doing is reducing the column from being 124 long to 55 long therefore I am using interpolation to do this.

Hope you guys can help again, Thanks again for your time.

Finnpark.

silverside

I don't think you are getting what interpolation is.

new x 2 is between old x 3 and old x 4. So you gotta take a weighted average of old y 3 and old y 4 to guess the y value.

the weight on old y 3 and old y 4 depend on how near new x 2 is to old x 3 and old x 4.

I say again, draw a graph for a simple example. It will help you understand.

finnpark

Thanks Silverside,

I understand now well. I can do it on paper from reading the answers from the graph. I get roughly the same answers as Matlab got.

I can do on a graph no problem but I need to implement it now using C/C++.

interpolate between old_y_value(j) and old_y_value(j+1) using

new_y_value(i) = old_y_value(j) + (new_x_value(i) - old_x_value(j))/(old_x_value(j+1)/old_x_value(j))*(old_y_value(j+1)-old_y_value(j))

This is almost correct but is always just a little bit out. I will keep trying but if you see whats wrong let me know or if you have a simple way of doing it in C let me know also.

Many thanks Again,
Finn

silverside

hmm the code i posted may be wrong

try something on the lines of
x_left = ... (point before)
x_right = ... (point after)
y_left = ...
y_right = ...
slope = (y_right - y_left) / (x_right- x_left)

distance from left = x_new - x_left

new y = y_left + slope * distance from left

try that and post your code if it still fails.

finnpark

OK Thanks,

Now I have it working on paper. I have worked out a simple formula but the C compiler is giving me an error:

for(int n2=0; n2<1; n2++){

   for(int ny=0; ny<AVERAGE; ny++){
	   test=0.00;
	   count=0;

	   //static count=1;

	   while(test<newx[ny]){
		   test=oldx[count+1];
		   count++;
	   }

	   

newy[n2][ny]=oldy[count] + newx[ny];// - (oldx[count])) * ((oldy[count+1]) - (oldy[count]))); 

	  
	   cout<<newy[n2][ny];
	   cout<<endl;
   }

   }

The error is:
error C2111: pointer addition requires integral operand

It is referring to the line with the equation on it.

Any idea whats causing it ?

Finn

satchmo

Let's see how you declare and allocate those arrays, that's probably the problem.

finnpark

double oldy[8][55];

double* oldx;

double* newx;

double* newy[8][55];

Thanks Again

satchmo

Yeah you've declared the 2d array oldy, but when you do oldy[count] + ... you're not addressing it properly - oldy[count] is only a pointer and not an actual value in the array. This is why it's giving you the "pointer addition" error. You need to go back and read up on "arrays as pointers" in your textbook.

finnpark

Thanks Satchmo for pointimg out this. Sorry for asking something so obvious and trivial.