In my project, I need to use interpolation to find points near a given point and use these to calculate an approximate derivative. So if I have points y = {10, 13, 14, 11, 9} for x = 0 to 5 and I need to find the derivative at (x,y) = (2,14), I use interpolation find the values of y at x = 1.9 and 2.1. Then I find the difference of the two values and divide by 0.2.
The algorithm I used for interpolation is Newton's divided differences.
Now this works for most cases where the points seem to fit in a function y = polynomial of x.
However for curves such as this:
Newton's divided differences cannot be used since there are two values of y for the same value of x.
My question is, what algorithm would work in such cases?
I basically need to use this in feature point extraction of a face. These kind of curves occur at the lips and eyes.
4 Replies  3740 Views  Last Post: 11 May 2010  06:28 PM
Replies To: Interpolation Algorithms
#2
Re: Interpolation Algorithms
Posted 08 May 2010  06:44 AM
I'm assuming that currently you're interpolating using a function y=f(x) where x is discretized over time. What you should do instead to interpolate over two functions, x=f(t) and y=g(t) where t denotes the time.
#3
Re: Interpolation Algorithms
Posted 08 May 2010  06:49 AM
Thanks for your reply
Yes, I did do something like that. The face has points marked on it manually (called landmark points). And the coordinates of these points are stored. Each of these is assigned to a number which is basically the index of the landmark point. I made the coordinates x and y functions of these points. Although these indexes are integers, during interpolation, I calculated the coordinates of point number say 11.9 and 12.1 to calculate the derivate at point number 12. Will that work? I hope I made sense .
Yes, I did do something like that. The face has points marked on it manually (called landmark points). And the coordinates of these points are stored. Each of these is assigned to a number which is basically the index of the landmark point. I made the coordinates x and y functions of these points. Although these indexes are integers, during interpolation, I calculated the coordinates of point number say 11.9 and 12.1 to calculate the derivate at point number 12. Will that work? I hope I made sense .
This post has been edited by Louisda16th: 08 May 2010  06:50 AM
#4
Re: Interpolation Algorithms
Posted 11 May 2010  05:44 PM
You can use the Mean Value Theorem to estimate at x = 12. It looks something like: f'© = (y2y1)/(x2x1).
Also, as much as I enjoy using parametric equations as Gloin suggested, why don't you evaluate your function inverting the axes. That is, use the yaxis as the xaxis and vice versa for evaluating the function (to compensate for a function not being able to have two equal ycoordinates). When you go to graph the function in your program, just place the x and ycoordinates where they should normally go. So for example, given f(x) = x^2, evaluate f(x) using the ycoordinate as the param to get x (so you're evaluating the inverse of the inverse function). Then plug in (x,y) to draw.
Also, as much as I enjoy using parametric equations as Gloin suggested, why don't you evaluate your function inverting the axes. That is, use the yaxis as the xaxis and vice versa for evaluating the function (to compensate for a function not being able to have two equal ycoordinates). When you go to graph the function in your program, just place the x and ycoordinates where they should normally go. So for example, given f(x) = x^2, evaluate f(x) using the ycoordinate as the param to get x (so you're evaluating the inverse of the inverse function). Then plug in (x,y) to draw.
#5
Re: Interpolation Algorithms
Posted 11 May 2010  06:28 PM
Thanks for your reply
Well, why I felt it is better to use parametric equations is because not all sections of the face have the kind of curves shown in that figure. I did think of the mean value theorem, but I wasn't sure if it would work with points on a curve like this (the red curve):
Another idea I had is to find derivatives of the curve by breaking it down into segments and then use the method you've told me. However I still feel parametric equations would be better because I can take care of everything in one loop. If I interchange x and y (when required), I will require additional code to check when the curve should be represented as y = f(x) or x = g(y).
Well, why I felt it is better to use parametric equations is because not all sections of the face have the kind of curves shown in that figure. I did think of the mean value theorem, but I wasn't sure if it would work with points on a curve like this (the red curve):
Another idea I had is to find derivatives of the curve by breaking it down into segments and then use the method you've told me. However I still feel parametric equations would be better because I can take care of everything in one loop. If I interchange x and y (when required), I will require additional code to check when the curve should be represented as y = f(x) or x = g(y).
Page 1 of 1
