Are two point sets identical?

[Steve Gray]

I have two sets, A and B, each consisting of an equal number of points (a dozen or less).
Either A and B are quite dissimilar or B and A are identical except one is rotated by an arbitrary
angle w.r.t. to the other. The positions and scales are the same to within about 2% of the diameter
of the sets.. What is a good, fast way to tell whether the sets are the same?
I could compare histograms of the (squared) point-point distances, but is there a better
way?

[Kenneth Sloan]

Steve Gray <ste...@adelphia.net> writes:

There are a number of statistics used to analyze 2D points. These
generally involve lengths and angles, using the
NearestNeighbor, or the k-NearestNeighors, or sometimes ALL of the pairs
of points. These could certainly be used for matching tasks.
You've mentioned one of these (distribution of all lengths).

I've used these methods in the past to characterize sampling patterns,
and could probably dig up a reasonable reference if you are interested.
If so, please contact me privately.

You might also consider computing moments. This could allow you to
recover the relative rotation (and perhaps scale) as well as matching.

For FAST, I would probably begin by computing the convex hulls. The two
sequences of Length^2 for each edge in the two convex hulls will be
similar (up to rotation, and the small possible scaling).

There are probably other "signatures" you can compute from the Convex
Hull.

Finally, I might mention a variation on the Generalized Hough Transform
idea. You might use one of the point sets as the "template" and then
let the other point set "vote" into an accumulator array that covers the
parameter space of scale and rotation. The range of the scale parameter
can be limited to the 2% you mentioned. Translation can be handled by
computing the centroids of the point sets.

Rather than look for evidence of EQUALITY, you might consider using a
collection of fast methods, each designed to bear witness to some
obvious reason why the two point sets are different. Moments (about the
centroids) are probably a good example of this idea. Matching moments
do not prove that the point sets match - but mis-matching moments
definitely rule out a match.

Enough?

--
Kenneth Sloan sl...@uab.edu
Computer and Information Sciences (205) 934-2213
University of Alabama at Birmingham FAX (205) 934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/

[Christer Ericson]

In article <d640o0d4g1qp70i0d...@4ax.com>,
ste...@adelphia.net says...

Hmm.. How about this?

Use principal component analysis (PCA). That is, compute the
eigenvectors for the covariance matrix of the points. This
gives you an orthogonal set of axes for both point sets,
i.e. the axes of a coordinate system for each set. Compute
the centroid of each set and use it as the coordinate system
origin.

Compute the spread of the sets along each axis. Assume, without
loss of generality, that we can order the spread from widest
to narrowest. For the point sets to be the same, the widest
spread for set A would have to match the widest spread for
set B, etc. That is, we have established a one-to-one
matching of the coordinate systems.

Now just compute the local coordinate positions of the points
in set A with respect to the established coordinate system.
Ditto for set B in its coordinate system.

Sort the two point sets, (lexicographically, or on distance
from the origin, or some such) and compare the two sorted sets
in a pairwise fashion. If all pairs of points are within your
2% tolerance, you're good. Otherwise, the sets are different.

Granted, this is not 100% foolproof. Since your sets aren't
exactly identical (except for the rotation), the two
coordinate systems are not guaranteed to match exactly.
It should be close enough for government work though.

Christer Ericson
Sony Computer Entertainment, Santa Monica