Fitting multiple geometrical entities into a given 2D Trajectory

Hi,

I have two dimensional data (containing x and y coordinates data).I want to fit multiple 2D Geometrical entities such as Line,circle,ellipse and arc into this data

For example, in the attached image (Rectangle.jpg), I want to fit 4 lines into it and make it a rectangle or square.

Similarly,in the attached image (ZigZag.jpg), I want to fit 5 lines.

In the attached image (Line_ArcCombined.png) file,I would like to fit 3 Lines and 2 arcs.

Basically,I would like to fit multiple geometrical entities into a given 2D Trajectory data (consisting of x,y vertices data).

I would be really glad,if someone can give me any idea/references to achieve it.

Thanks a lot in advance!MathWorks

[Math Enthusiast]

@Adam Danz: please do help!

[KSSV]

Attach your original image, which gives you (x,y).

[Math Enthusiast]

@KSSV: I have attached a textfile, "RawData_Scaled.txt" file.

The trajectory looks like this

[KSSV]

So you want a circel, ellipse, square wwith in this trajectory?

[Math Enthusiast]

No,not square..Just want to detect lines,circular/elliptical arcs in this trajectory.

Like,For the above trajectory,I would like to detect 5 lines, 4 arcs.

So,once I detect these entities..I just want to understand,the indices of the points constituting line and indices of the points,constituing arc.

For example,if I have 100 points in my data set. I would like to know the info, like:

1-20 points: constitute line

21-45: constitute circular arc.

46-80: constitute line

81-100: constitute arc.

[John D'Errico]

The human brain is very good at pattern recognition, so we expect that computers should do it as easily. And then we have all these movies and tv shows, where any hacker can type two lines of code and do anything, or Kirk can tell the computer something vague like verify the Riemann hypothesis, and in seconds it is done (all while we hear the sounds of tape thrashing and punch cards being processed. Lights blink on and off a lot. Yeah, right.)

Anyway, look at the curve shown in Line_ArcCombined.png. In there, I can see 3 lines, or is it 4 or 5 lines? Is that an elliptical arc? Or is it another line? The point is, you have a very noisy curve. At best, you have something that needs highly subjective, fuzzy processing. Is a given arc a straight line? Two lines, with a break in the middle? Or is a piece of an elliptical arc a better approximation?

And of course, you want something that will handle any general shape, closed curve or not.

Sigh.

[Math Enthusiast]

@John: I would expect it to be a collection of 3 Lines,2 circular arcs.

I know that, in some cases, there might be a discrepancy.

But I just want to get a rough idea of the algorithm,to try it with some of my samples.

As of now,I just want to divide my whole trajectory into Lines and circular arcs.

Hope you get my point.

[Math Enthusiast]

I would just like to know atleast the algorithm to find dominant points (like ,the point,where a curve 1 is being transoformed to curve 2).

[John D'Errico]

Again. The human brain is very good at these things. So good in fact, that it seems easy. But as I said in that example green curve you show, there are good arguments for several interpretations. How many lines? I can easily argue for 5 or even 6 linear segments. And those curved arcs? There are at least 2 such arcs, with an extra third long graceful arc with large radius of curvature on the right side. Is that a straight line? Or an arc? Maybe several straight lines? Any arc is well approximated by a set of small straight lines.

So be honest. It is not quite so trivial to do even for a person, since it is easy for two people to look at the same figure and make very different decisions.

As far as "the algorithm" goes, there is not any single such thing. You talk about something called "the algorithm", as if there is some special algorithm that the rest of us know, but are just keeping secret. There are lots of ad hoc schemes one can think of, based on tools in image processing, curve fitting, etc. Is smoothing necessary? Even there though, if noise is present, at what point is a noisy line just a collection of saw tooth segments?

Learn something about image processing, if you have pictures of curves. You might start with the Hough transform, with various edge detector schemes, etc. You might want to learn about tools for curve fitting, because at some point this needs to becomes a curve. You might want to learn about tools like the singular value decomposition, because vertical lines are difficult to deal with, especially noisy vertical lines, and the SVD can help you to solve the problem with lines at any arbitrary angle.

As far as finding the transition point between two curves goes, this too can be difficult, because that is often a fuzzy area, again, especially so in the presence of noise. Effectively, you are looking for a point where a slope changes. You can think of a slope in terms of derivatives, but estimating the slope of a curve in the presence of noise is what is called an ill-posed problem. The slope estimation amplifies the noise, so it becomes difficult to pin down where the slope changed. In the end, this all becomes learning a lot of mathematics, a lot of different methods, from different domains. You might look at tools like Kalman filters, where you can try to assess the probability that one curve has transformed into another. In the presence of noise, exactly where does that transformation occur, or did it happen somewhat smoothly?

You probably want to learn about statistical methodology too, because that is the science of how to work with noisy processes.

My point is, there is not a single magical algorithm here. There is a lot of mathematics, and what you use, where you go can depend on exactly what you need in the end, on what you know about the class of problems you are trying to solve. Sorry, but so far from what you have said, it is not even clear if this is mainly an image processing problem or essentially a curve fitting problem. I'd suggest you need to start learning the tools of at least one of those areas however, and the broader you can make your education, the better off you will be.

[Math Enthusiast]

@John: Thanks for your explanation. I was thinking of something like this. First apply some filter to the data(in order to remove the noise) - may be, something like Quadra Filter.

Then,I can find the radius of curvature of this filtered data.From that, we could visualise all local maxima and minimuma points.Those points are supposes to be,the junctions,where curve transformation is taking place.

Whats your opinion on this logic?

[Math Enthusiast]

Still waiting for the update from someone.

Please help me to resolve this issue.