# Similarity metric between two sets of points with varying densities

How can I create a similarity metric that describes the top left set of points as more similar to the bottom left set of points than the top right set of points? Clearly least-squares distance doesn't work.

UPDATE Hausdorff distance looks good. Now here's a more difficult problem:

Lets say the images (the sets of points) may be rotated, translated, and scaled differently from one another. I want to use the Procrustes algorithm to recover the relative rotation, translation, and scaling, but the Procrustes algorithm is a minimization problem over vectors that contain equal numbers of points. When the densities of the points vary between images, points between images don't correspond well. How can I normalize the input to the Procrustes algorithm to make my image comparison algorithm invariant to varying point densities?

To be more concrete, below are some of the images I would like to compare. I don't want the matcher to be thrown off by borders that are thicker relative to the details inside the borders.

• Can you objectivate verbally why bottom-left is more similar than top-right ? – user65203 May 30 '14 at 17:22
• As humans, we can tell that the images on the left are more circular than the images on the right, and the image on the left contains the letter "v" rather than a "+". – Rose Perrone May 30 '14 at 17:25
• Least-squares distance isn't defined as such between point sets. Do you know about the Hausdorff distance ? – user65203 May 30 '14 at 17:27
• Do you mean that your similarity measure should take into account segmentation of the point set into shapes, shapes being taken from a predefined "alphabet" ? In other terms, should a symbolic description be used ? – user65203 May 30 '14 at 17:28
• @YvesDaoust There should be no other supervision other than two sets of points that need to be matched. I want to know if there's a way to compare the sets of points without resorting to comparing contours and computing some sort of optical character recognition. – Rose Perrone May 30 '14 at 17:30

Suggestion:

Use the binarized outlines, apply thinning and vectorization (Douglas-Peucker); if possible, decompose in a sequence of line segments and circular arcs (this is uneasy).

(Actually, you are pretty lucky to have those well contrasted outlines, you should exploit them.)

This will allow two things:

• perform a preliminary classification by outline shape;

• register the image based on the outline center and orientation (except for the circular pills).

After registration and selection of relevant templates, point-wise similarity metrics can be used (SAD, SSD, NGC...), but unbinarized images are required.

Alternatively, interest point descriptors could do.

Lets say the images (the sets of points) may be rotated, translated, and scaled differently from one another

One thing that I've used successfully for aligning two point clouds is Sampled Consensus Initial Alignment (SAC-IA) followed by Iterative Closest Points (ICP). Both are available in Point Cloud Library (PCL). The method essentially gives you the transformation matrix from one to the other.

There are tutorials available for both here and here.