I have two shapes in a 2D space, not necessarily convex, and I'd like to compare how similar they are. How can I define a robust distance metric to measure their similarity, and how can I compute it?

Distance between two shapes

I am looking for a method which provides a short distance in case of:

  1. scaling;
  2. rotation;
  3. perhaps local scaling or rotation.

I see two possible solutions:

  1. transform the shapes into pixel-based matrices (bitmap) and compute a Levenshtein distance (but without enough robustness in the distance, in case of rotation for instance);
  2. transform the shapes into graphs and try to define a distance between them.
  • 2
    $\begingroup$ Computing the distance is probably not the issue here; you need to define what the distance is first! Is that your question, or do you have some idea (but not included it in the question)? Note that there are many, many possible distances between curves/shapes (min, max, avg, median, min max, max min, ...) $\endgroup$
    – Raphael
    Mar 19 '14 at 0:07
  • $\begingroup$ My question was about defining a metric more than computing it, sorry for the misunderstanding. Thanks @D.W. for your clarification. $\endgroup$
    – cynddl
    Mar 19 '14 at 3:29

One approach would be to use SIFT (or SURF, or other similar methods) to align one object to the other to account for scaling and rotation, and then compute a pixelwise distance based on the aligned images.

The right algorithm to use for alignment will depend upon the nature of the 2D images. If they are natural-color photographs taken using a camera, SIFT, SURF, etc. might work well. If they are black-and-white geometric shapes like shown in the question, you might do better to use image moments (e.g., Hu moments) or some other approach.


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.