CODEWITHSUNDEEP
algorithmgeometry
loneboat
loneboat

Reputation: 2945

Algorithm: Find 2d orientation from constellation of known points?

Problem

Given a set of known cartesian points (set A), and a 2d transformation (rotation, translation, scale) of some subset of those points (set B), find the orientation of the subset (rotation, translation, scale) relative to the original set of points.

I.E. Suppose I take a "picture" of a known set of 2d points on a wall. I want to know what position the camera was in relative to "upright and centered" when the picture was taken. Some of the points may not be visible in the picture (they may be occluded). (in this analogy, assume the camera is orthoganal and always pointed directly at the plane of the wall, so you don't need to take distortion or perspective into account)

Proposed approach:

Step 1: Scale B to the same "range" as A

Don't know how; open to suggestions. Maybe take the area of a convex hull around all the points in B, and scale it to nearly that of the convex hull around A. This is tricky, because points may be missing from B.

Step 2: Match some arbitrary point in "B" to its twin in "A"

Pick some random point in set B. Call this point K. Somehow take a "fingerprint" of K relative to all the other points in B (using distance only). Find its match in A by fingerprinting all points in A and taking the point with the most similar fingerprint of K.

Step 3: Rotate B (around K) until all points in B are aligned with a point in A

Multiple solutions are possible, so keep rotating though 360d looking for solutions.

That's just shooting from the hip, I may be way off base. Anyone have any ideas?

Upvotes: 2

Views: 1138

Answers (3)

Lajos Arpad
Lajos Arpad

Reputation: 76787

"Give me a place to stand on, and I will move the Earth" Archimede

I think we should follow the steps of Archimede

Arpi's algoritm: We must choose a point (X1) of set A with coordinates (0, 0). (this will be the place to stand on)

Choose another point (X2) and put it on the OX vector (to simplify things)

All the other points' coordinates from set A will be calculated based on the coordinates of X1(0, 0) and X2(some_Coordinate, 0).

Now, choose a point from set B (Y1) and that will be the center of the B set. Choose another point from set B (Y2) and put it to OX of the B set. Now, we have a scale scalar and a rotation angle. If this will be a solution, than Y1 in the B set represents X1 from the A set and Y2 from the B set represents X2 from the A set. If we can find a map between the B set and A set based on this, using all the points of the B set and Yi <> Yj if i <> j, where i and j are the indexes of the points in our representation than we have a potential solution and we store that. End of Arpi's algoritm

To find all the potential solutions you must do the following:

foreach point in A as X1 do
    foreach point in A as X2 do
        arpi's algoritm(X1, X2)

Of course, you can optimize this, but for the sake of simplicity I described it without optimizations (complications), it will be your job to optimize this and only if you need that.

Upvotes: 1

Drew Hall
Drew Hall

Reputation: 29055

Assuming you don't actually know the correspondence between the points in the two clouds, you could try a statistical approach.

First, compute the mean x0 of the original cloud, then compute the mean x1 of the subset cloud. The difference of the mean vectors, x1-x0, is a good estimate of the required translation.

Now, subtract the relevant mean vector from each set to give two clouds centered at the origin. Compute the covariance matrix for each cloud and find its eigenvalues and eigenvectors. The required rotation can be found from the eigenvectors, while the scaling corresponds to the eigenvalues.

Compose all of this and you should have a good statistical estimate of the desired transform. Obviously, its quality will be a function of how well the subset spans the original set.

Upvotes: 2

Zack Bloom
Zack Bloom

Reputation: 8417

I would attempt to minimize the deviation between the target points and the found points. Meaning I would pair each target point with a found point, and apply any transformation (rotation, scale or skew) to all the target points which decreases the sum of the deviations. I would repeat this for all potential pairs, eventually taking the match to be the set of pairs and the necessary transformations with the smallest total deviation.

The real question is how you optimize this so the performance to be better than O(n^2). I suppose some sort of heuristic matching, perhaps caching the intermediary results, or finding a method of eliminating some pairs earlier in the process.

Upvotes: 0

Related Questions