[Louisda16th]

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.

[Gloin]

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.

[Louisda16th]

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 .

This post has been edited by Louisda16th: 08 May 2010 - 06:50 AM

[macosxnerd101]

You can use the Mean Value Theorem to estimate at x = 12. It looks something like: f'© = (y2-y1)/(x2-x1).

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 y-axis as the x-axis and vice versa for evaluating the function (to compensate for a function not being able to have two equal y-coordinates). When you go to graph the function in your program, just place the x- and y-coordinates where they should normally go. So for example, given f(x) = x^2, evaluate f(x) using the y-coordinate as the param to get x (so you're evaluating the inverse of the inverse function). Then plug in (x,y) to draw.

[Louisda16th]

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).