Similarity between two geometric shapes

Question

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?

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.

Answer 1

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.