Solved

Wanted to convert vector of points I have to parametric equation of curve

Posted on 2015-01-19
24
136 Views
Last Modified: 2015-03-20
Dear All

I have vector of points for the curve..I wanted to retrieve parametric equation of the curve with the help of these points.
Can I do so?If yes ,please guide me for the same.

Thanks.
0
Comment
Question by:BYTECHINDIA
  • 9
  • 6
  • 4
  • +2
24 Comments
 
LVL 84

Expert Comment

by:ozo
Comment Utility
Do you also know the parameter values at those points?

There are an infinite number of functions that pass through any set of points,
and there are many simple ways of finding some example of such a function,
but deciding which such function is preferable in a given application may not be an easy or well defined problem.

If the parameter values are another set of free variables, that could further multiply the number of potential functions that fit, which can potentially make the problem of finding some example of such a function easier, and can potentially make the problem of finding the preferred example of such a function more difficult.
0
 

Author Comment

by:BYTECHINDIA
Comment Utility
Thanks for the reply.
No parameter are also unknown.
I will explain you what I exactly wanted to do..

I have set of points for the curve/line.Now I wanted to retrieve attributes/property of that curve by which I can redraw that again.(approximatley).
I am not sure whether it is possible or not.Please help as I am quite new to these concepts.
Thanks
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
It is possible.  But whether it is easy or hard, and whether the results are satisfactory or unsatisfactory may depend on many things.
Do you know or have reason to expect that the parametric equations will have a particular form?
Can you quantify how approximately you want to redraw the curve?
Can you quantify a trade off between simpler functional forms and closer approximations?
0
 
LVL 13

Expert Comment

by:frankhelk
Comment Utility
The solution to that problem has several ways depending on the type of formula that describes the curve and if the points do match exactly or have (ie.e meaurement) errors.

A common algorithm to appxoximate a given type of formula into existing data is the "least squares" method. It's by far to complex to explain here, but for certain cases it's already coded somewhere - just serarch for "least squares fit" and dig thru the results ...
0
 
LVL 27

Expert Comment

by:d-glitch
Comment Utility
How much data do you have, and what does it represent?  Temperatures, unemployment, stock prices?

Do you have some sample or dummy data you can share?  The more we know, the more we can help.
0
 
LVL 13

Expert Comment

by:frankhelk
Comment Utility
For a better understanding of the "least squares fit" algorithm:

To fit a parametric curve into a vector of given, exact matching X,Y points, you need to have at least as much X,X points as you have unknown parameters in your formula. Simple example:

If your parametric curve formula reads Y = a * x^2 + b * x + c you have 3 unknown parameters (a, b and c). Therefore you'll need 3 independent X,Y point to solve that puzzle. With that, it's some basic algebra.

But that simple approach fails if there are too few points (which couldn't be cured) or the points are not exactly matching the formula, i.e. due to measurement uncertainties. And here comes the least squares algorithm into account ...

It's usually used with more points than unknown parameters and works by iterative approximation. It uses some start values for the parameters and calculates the deviation of the points from the estimated values of the curve. Each deviation is squared and the squares are summed. That sum is a measurement for the quality of the approximation.

In the next iteration step the algorithm varies the parameters slightly and tries to minimize the sum of squares. By using the squares, two things are achieved: The sum doesn't have to deal with negative values, and points with great deviations have more weight when the parameters are varied. The variation of the parameters follows specific rules and contains differential mathematics ...

You could find a detailled description of the algorithm in the english Wikipedia at the lemma "Least squares (function approximation)" and the more basic article "Least Squares".
0
 
LVL 32

Expert Comment

by:sarabande
Comment Utility
if you have equidistant points regarding the x-axis and if the original curve is smooth rather than serrated you may use spline interpolation to create an approximation of the curve. the idea is to use polynomial approximation but not for the whole curve but for little parts (splines) and have the polynomials the same derivatives in knots what makes the whole curve looking smoothly.

see http://blog.ivank.net/interpolation-with-cubic-splines.html for cubic splines.

Sara
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
Several approaches have been suggested, each appropriate to different types of problems.
There is still not enough information to determine which, if any, of these types your problem belongs to.
0
 

Author Comment

by:BYTECHINDIA
Comment Utility
Thanks frankhelk,
I am looking at "least square method".You explained very well.Thanks.
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
If the "least square method" above is appropriate to your problem then there is no need for iterative approximation, as it can be solved directly by inverting a 3x3 matrix
0
 
LVL 13

Expert Comment

by:frankhelk
Comment Utility
@ozo: As I've explained, there's only one scenario where this could be solved without interative approximation: You have exact as much points as unknown parameters in your formula, and the points are exact (AKA not disturbed by noise, measurement problems, etc.). If you have less points, your solution would be an infinite heap of possible functions. In the other cases, you'll need iterative approximation.

@BYTECHINDIA: You'll possibly have to fiddle around with the inital parameter values (start values). If chosen bad, the iteration result might be lousy, or you might end up with not comming to convergence. I've used a software packet named NCSS several times for function approximation, but that packet is for the hard core statistics freak and not really cheap ....
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 

Author Comment

by:BYTECHINDIA
Comment Utility
I am sorry I din get meaning of " inverting a 3x3 matrix"
Can you please elaborate..
0
 
LVL 27

Expert Comment

by:d-glitch
Comment Utility
The best first step for understanding your data is to plot it.  You can do this very easily with Excel.  
Then you can draw the sort of curve through the data that would be acceptable for your application.
If you are willing to share the plot and drawing with us, we can all make some progress.

Inverting a matrix is the essential step in the least squares method.  Excel can also handle this task.  
But if you don't understand matrix inversion, we may need to go back a few steps.
Do you understand the concept of a matrix representing a system of equations?
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
The best first step for understanding your data is to plot it.
If you are willing to share the plot and drawing with us, we can all make some progress
However, there may be reason to be cautious about doing that, because it can make it impossible to judge how likely it would be that any equation that you or we come up with would generalize to the parts of the curve for which you do not have points.

With enough free parameters, you can fit any set of points to an arbitrary accuracy,
so just because an equation fits the points you are given does not give you reason to believe that it will also fit at other places you haven't sampled.
But, when you can fit many points to a good accuracy with few free parameters,
(where "many", "few" and "good" can be given precise mathematical definitions)
then you can make certain probabilistic conclusions about how likely it will be that
the euation will also be a good fit on the points you haven't sampled.
When you apply a specific algorithm, you can quantify the number of free parameters that are being tried.
When you try a bunch of different algorithms, there are ways to quantify the total number of free parameters being tried over the set of all those algorithms.
But it can be very hard to know the set of algorithms tried when people look at a set of points and come up with an equation,
and it can be even harder when a bunch of people look at it, especially when you don't even know how many people are looking at it.
0
 
LVL 13

Expert Comment

by:frankhelk
Comment Utility
@ozo:

I agree - curve fitting is some kind of fine art. Using it without refering to the neuronal net device between your ears could lead to (euphemistic spoken) very bad fitted results. And using it on a regular computed basis requires underlying data that comes from a well known source ... in a way that the matching function type is well known and good start values of the parameters are easily to be determined.

If not, one has to plot the data and think a bit about it ... choosing a proper function type is done best when one understands the basic properties (i.e. physical laws) behid the data. Proper start values need some consideration, too.

And last but not least, the fitted function is usually of (very) limited use outside of the underlying data range: If the data points the function is fitted into range from x= 1 to X=100, I wouldn't expect usable results for X=1000. Or X=150, to be true.
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
curve fitting is some kind of fine art
It can be a science, if you follow a careful discipline.

plot the data and think a bit
If you want to be able to justify a statement that a function you come up with has at least a certain probability of being with at least a certain accuracy for points not in your sample set, then that is what you should not do before first
choosing a proper function type [which] is done best when one understands the basic properties behind the data

But we still don't know whether the purpose of the curve fitting in question is art, or science.
0
 
LVL 13

Expert Comment

by:frankhelk
Comment Utility
I think that good science is indeed some kind of fine art ... both need inspiration, hard work, discipline ... and sometimes a good helping of stubborness ;-)

And you're right - understanding the basics of the data is the first requirement of good curve fitting. But having a plot of the data will help anyhow ...
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
Having a plot of the data could help, but the point I'm trying to make (although I still don't know whether the point is pertinent to this particular question) is that it could also hurt, because making certain mathematical statements about the generalizeability of a function derived from a set of data requires knowing something about the space of functions that was searched through in order to find a function that fit the data.
But when you just "think a bit about it" waiting for the muse to strike, you can't define the space of functions that you were searching through.
0
 
LVL 13

Expert Comment

by:frankhelk
Comment Utility
I agree ... definitely.

Just a faint remark, a bit abroad of pure science:

Sometimes the laws behind the data are present but hidden, anyhow a generic function type might already be sufficient. In that case a plot might help to attract the muse ;-) I know that results from such curve fits are be taken with a hint of sceptic, but nevertheless they might me helpful.
0
 
LVL 27

Expert Comment

by:d-glitch
Comment Utility
This question has made zero progress because:

1.

We have not been allowed to see the data.

2.

We don't know the source or utility of the data:  It could be a physical, socioeconomic, or random process.  Or something even more interesting.

3.

We don't know even how much data we are talking about.

4.

We don't know the intent or requirements of the curve fitting.  It could be compression, comprehension, extrapolation.  Or something else.

My all-time favorite extrapolation question:
     http://www.experts-exchange.com/Programming/Algorithms/Q_24761243.html
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
I am looking at "least square method"
Perhaps it would help if we described the type of data for which least square is most appropriate.

If you know that the data was produced by a process of the form
a*f(x)+b*g(x)+c*h(x)+...+ gaussian random number
for known functions f(x),g(x),h(x),... and unknown parameters values a,b,c,...
and you have data samples of from least as many x points as there are unknown parameter values.
then ordinary least square can produce the maximum likelyhood estimator for a,b,c,...
An efficient method to find those values essentially involves matrix inversion for a matrix of the same order as the number of unknown values you are trying to find.

Based on knowledge of the source or utility of the data, and how much data we are talking about, there can be an art form to selecting an appropriate set of f(x),g(x),h(x),.. functions with which to use this method.
One commonly used set is x^0, x^1, x^2, ...


The main thing here that suggests to me that this problem might not be of that type, is that the x values also seem to be free parameters.
But it sounds like it could be converted into a problem of that type by arbitrarily fixing the x values.  e.g. to 0,1,2,...
How well this might fit the intent or requirements of the problem is unknown.
0
 

Author Comment

by:BYTECHINDIA
Comment Utility
Hello All

Thanks to all of you for the comments.As I am working on imageprocessing algo using opencv.In opencv I found approxpoly function which basically coverts set of vector points into polynomial which basically help to redraw the curve  and can help me for matching purpose also.Currently using that only.The complete overview of project is not yet clear and this is our first project towards image processing,I might have put different question.Currently keeping the question open till the complete picture of project comes out.

Thanks again to all of you for the kind support.
0
 
LVL 84

Accepted Solution

by:
ozo earned 500 total points
Comment Utility
How does converting a set of vector points into a polynomial help for matching purpose?
0

Featured Post

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

Entering a date in Microsoft Access can be tricky. A typo can cause month and day to be shuffled, entering the day only causes an error, as does entering, say, day 31 in June. This article shows how an inputmask supported by code can help the user a…
If you’re thinking to yourself “That description sounds a lot like two people doing the work that one could accomplish,” you’re not alone.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now