3
$\begingroup$

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.
$\endgroup$
3
  • 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, 2014 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, 2014 at 3:29
  • $\begingroup$ The distance should be robust to what ? $\endgroup$
    – user16034
    Sep 1, 2022 at 11:22

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ May be "Shape context" descriptor (eecs.berkeley.edu/Research/Projects/CS/vision/shape/…) suits better for this purpose. Also it has been already implemented in OpenCV - docs.opencv.org/trunk/modules/shape/doc/shape_distances.html $\endgroup$
    – old-ufo
    Mar 19, 2014 at 6:31
  • $\begingroup$ @old-ufo, great suggestion! How about posting an answer with that suggestion (and ideally a brief description of it), so I and others can upvote it? $\endgroup$
    – D.W.
    Mar 19, 2014 at 6:33
  • $\begingroup$ These point detectors/descriptors are useful for shape registration and will not work well in case of dissimilar shapes. They do not define a similarity measure. $\endgroup$
    – user16034
    Sep 1, 2022 at 11:13
  • $\begingroup$ @YvesDaoust, Good point. I agree with your criticism. I don't know what I was thinking. $\endgroup$
    – D.W.
    Sep 1, 2022 at 16:30
  • $\begingroup$ @D.W.: well, the OP seems satisfied... $\endgroup$
    – user16034
    Sep 1, 2022 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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