Interpolation Algorithms

Don't know whch ones to use.

Page 1 of 1

4 Replies - 3860 Views - Last Post: 11 May 2010 - 06:28 PM

#1 Louisda16th  Icon User is offline

  • dream.in.assembly.code
  • member icon

Reputation: 15
  • View blog
  • Posts: 1,967
  • Joined: 03-August 06

Interpolation Algorithms

Posted 04 May 2010 - 11:31 PM

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:

Attached Image

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Interpolation Algorithms

#2 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

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.
Was This Post Helpful? 2
  • +
  • -

#3 Louisda16th  Icon User is offline

  • dream.in.assembly.code
  • member icon

Reputation: 15
  • View blog
  • Posts: 1,967
  • Joined: 03-August 06

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 :(.

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

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,102
  • Joined: 27-December 08

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'© = (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.
Was This Post Helpful? 1
  • +
  • -

#5 Louisda16th  Icon User is offline

  • dream.in.assembly.code
  • member icon

Reputation: 15
  • View blog
  • Posts: 1,967
  • Joined: 03-August 06

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

Attached Image

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).
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1