0
$\begingroup$

Are there any known algorithms for uniquely identifying some set of points despite scaling, moving and with some amount of threshold?

I have an "ideal" set of points with coordinates and I need to check if other set matches the ideal one. Other set could be rotated, scaled or distorted a bit (points could be placed with slight offset).

All sets have one common property: there are 2 points located farthest apart. This can be used to, at least, negate rotation. We do know angle (45deg) that line between farthest points create with axis, and we do know needed distance between them.

I've tried following algorithm:

  1. Rotate "other" set to some point (so that farthest points create line that is 45 degrees to "x" axis);
  2. Scale set so farthest points distance = "ideal" distance;
  3. Use sort of GeoHashing algorithm to get point hash with some accuracy (like threshold).

But that approach gave nothing. "GeoHashing" produces semi random results and probably not suitable for 1000x1000 calculations. And using geometric operations furthermore reduced accuracy (initial distortion of points + inaccuracy of some geometric methods).

EDIT:

I want to add some details to it:

  1. Points set contains only 5 points (including those distant ones);
  2. There could be several "ideal" point sets and I want to find if given set matches something (that's why I used GeoHash);
  3. Basically task is to find matching polygon/set of points with given accuracy. If points do not match exactly (not located in the same coordinates), but are pretty close to ideal location (like +-2) it's a match.
$\endgroup$
  • 2
    $\begingroup$ What counts as a match? Do you require each point in one set to be aligned with another point in the other set? Or might some points have no match? Are you OK with an algorithm that, given the two sets, checks whether they match? Or do you really need a way to obtain a unique hash / canonical form given a single set of points? I'm not sure what GeoHashing is or why it didn't work; can you share any more about what that is, how it works, and why it didn't work? $\endgroup$ – D.W. Mar 22 at 1:39
  • $\begingroup$ After your step 2, I would try solving an Assignment problem in which one set (the "workers") are one point set, and the other set (the "tasks") are the other point set, and the cost of each possible pair of points, one from each set, is the Euclidean distance between them. Return YES iff the solution cost (sum of distances of matched point pairs) is under some threshold. $\endgroup$ – j_random_hacker Mar 22 at 1:41
  • $\begingroup$ Don't add "EDIT:". Just revise our question so it reads well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755. $\endgroup$ – D.W. Mar 22 at 19:04
1
$\begingroup$

I'll assume you are given two sets of points and want to determine whether one can be transformed to match the other. This is the pointset registration problem in computer vision. There are standard algorithms for this problem.

One of the crucial challenges is outliers -- e.g., points in the first set that don't have any corresponding point in the second set, or that have a large amount of error in their location. If you don't have outliers in your setting, then the problem becomes noticeably easier: simple least-squares linear regression might suffice.

If you have to deal with outliers, one standard way is to use RANSAC to find a rigid transformation that, when applied to the first set, makes it match the second set. A rigid transformation is determined by the correspondence between two points. So, you can use RANSAC: repeatedly pick a pair of points in the first set, choose a candidate pair of points in the second set for them to be matched to, compute the rigid transformation that maps the first two points to the latter two points, apply it to all points in the first set, find all inliers (points that are well-matched), update your estimate of the rigid transformation, count the number of inliers, and do this many times and keep the best rigid transformation you've found.

There are many other approaches as well. If you do some research, you should be able to find many algorithms, techniques, and even existing tools.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.