Shape reconstruction
Hi all! It's time for my next problem ;) And before I post it, i would just like to thank everyone in this forum for all the help I've gotten from you guys.
Anyways, I'm trying to reconstruct a shape from an unordered set of points. My goal is to do a (least squares) fit with a beizer spline, polynomial curve or whatever.
When I look at the points, it's really obvious that they form the shape of a smooth, NURB-looking line. But when I get a hold of this data, all points are shuffled, so I have no time information at hand. Neither do I know start or endpoints in this set.
What I've found so far is something that i found on the net: "meshless curve reconstruction". It tries to reorder the points in the most probable order (minimizing path length). The problem is that this algo is not very robust when it comes to noise (it expects a nice set of points, not a "band" of noisy samples).
After the reordering, i do a least squares fitting of a spline to the reordered set and regain the shape information.
As I said, the problem is robustness and I feel really stupid for not coming up with something better that doesn't take forever (I thought of the travelling salesman, which is hopeless). Perhaps I don't even need to reorder them? Can you do some sort of fit right away?
Is it really that hard to reconstruct a line from noisy data? I mean, it's obvious for any human and they can do it in a split second. Is it just me or is this really hard? Am I just searching for the wrong things?
[1549 byte] By [
ArneWeisea] at [2007-11-27 4:04:59]
# 1
Do I understand your question correctly:
You want to plot a graph, but you only have the Y-values, not the X-values?
You want to re-order the points so that the graph "looks smooth?
I presume the unknown X-values are intergal multiples of some step size? If they weren't and you could invent any X-value you like to go with any Y value, you could get any answer you want.
I presume the data is too numerous for a brute force test of every possible re-ordering?
At first I though this was trivial: Just arrange the points in ascending (or descending) order. There will always be at least two solutions - one the mirror image of the other.
However, this doesn't necessarily make "smooth".
For example, 1,2,4,5,7,8 is not "smooth"
1,4,7,8,5,2may be deemed "smoother" - it is a rising straight line joining a falling straight line.
It seems necessary first to define a criterion for "smoothness".
This might be "least variation of the derivative (=first order differences).
This could mean least sumsquare second order differences.
In the above example, the first order differences for 1,2,4,5,7,8 are
1,2,1,2,1 and the second order differences are 1,-1,1,-1 with a sumsquare of 4.
For 1,4,7,8,5,2 the 1st order differences are 3,3,1,-3,-3
The second order differences are 0,-2,-4,0. Sumsquare is 20.
HMM That criterion didn't work.
A spectral criterion might be more general - least high frequency noise for example.
This problem seems to be relates to the problem of reconstructing speech that has been encrypted by time-element scrambling.
Can you put limits on how far out of correct order any value could be in the original ordering? E.g. you are perhaps allowed to move it only +/-5 from where it originally appeard in your data sequence?
# 2
> Do I understand your question correctly:
>
> You want to plot a graph, but you only have the
> Y-values, not the X-values?
Nope, not quite... I've got both X and Y values, but I do not know how they are ordered in time.
>
> You want to re-order the points so that the graph
> "looks smooth?
Yes, or more specifically, I want to reconstruct the shape they represent. Imagine that you would have a spline with control points A & B. You would then print it with a crappy printer (with color bleed and bad resolution) and then scan the resulting image. You would then have a noisy representation of that spline, given in unordered pairs of XY coordinates (the time information is lost). What I wish to do, is to estimate A and B given the "image", the unordered set of XY points.
> I presume the data is too numerous for a brute force
> test of every possible re-ordering?
Yes, a naive approach to this problem is basically similar to the euclidean TSP. That version would try all possible reorderings and compute the one that produces the shortest length path. Ideally, you would want an algo that can exclude some "outlier" points, which would add even more to the complexity.
>
> This problem seems to be relates to the problem of
> reconstructing speech that has been encrypted by
> time-element scrambling.
Will look that up. Thanks for the tip.
>
> Can you put limits on how far out of correct order
> any value could be in the original ordering? E.g. you
> are perhaps allowed to move it only +/-5 from where
> it originally appeard in your data sequence?
Nope, unfortunately the reordering is not limited in any way.
# 3
The method you're looking for is something related to the problem of "the traveling salesman."
Google "solutions to the traveling salesman" and it will give you all sorts of methods to find the shortest path to connect a non-sorted array of points. A genetic algorithm is one method that works, but it may take longer than you want. Like I said, google that for some ideas.
Good luck.
# 4
> The method you're looking for is something related to
> the problem of "the traveling salesman."
Did you bother reading the original post?
Quote: "[...] I thought of the travelling salesman, which is hopeless [...]".
@ArneWeise: perhaps Kernel Methods is what you're looking for?
http://en.wikipedia.org/wiki/Kernel_Method
