Partial polygon matching

Question

I am looking for fast procedures for polygon matching, i.e. checking polygon similarity under different transforms

• translation only,
• translation + rotation,
• translation + scaling,
• translation + rotation + scaling (= similarity).

The matching can be partial, meaning that there can be a good match on a significant fraction of the outline (say > 70%), and complete mismatch elsewhere.

The number of vertices is reasonable (say N<50).

In a variant of the problem, you need to compare two polygons. In another variant, you compare one polygon to a series of polygons, with preprocessing of the single polygon allowed.

Are you aware of solutions to this problem ?

Answer 1

I remember doing shape recognition for robotic machine vision back in the 70's, when we used an algorithm attributed to Heginbotham and Pugh, as follows: Find the center of gravity (centroid) of an object, then overlay a fixed number of circles on the object from the center to the minimum circumcircle. (Lets say 8 circles for an example, though the number is arbitrary.) Also overlay the object with a fixed number of radii, equally spaced in a star-like patterns - the number of radii defined by the convenient bit size of a machine word (which in today's world might be 64 - we used 32). Sample the 8 x 32 points where the radii and circles intersect and return as 8 machine words. Do the same for your target object, and compare by comparing bitmasks and counting the number of bits that match. Then do a cyclic shift of your bitmasks and compare again until all 32 angles have been tried. This satisfies your constraint of being both rotation independent and scale independent.

In the world of polygons, a simpler but more expensive algorithm might be: Find centroid. Scale target polygon so that its cirumcircle matches the test objects circumcircle. Rotate target polyon through a whole circle by however many steps you feel comfortable with. Do an AND operation between the two polygons and record the parameters of the one with the greatest matching area. As a refinement possibly repeat the algorithm between the best match angle and its two neighbours using a smaller step to fine-tune the result.

The only downside of this algorithm in your case is that you do allow objects with some features added or removed, in which case the center of gravity could be significantly displaced - whether this is a problem for you or not will depend on the details and degree of these tacked-on features. Perhaps you could come up with a better choice for the center point, perhaps by discarding the most eccentric single feature that sticks out?

PS Note if comparing a single target against multiple objects, it's more efficient to scale and rotate your target than the objects you are comparing it with, because you can cache those translations and rotations and re-use them.

Answer 2

Algorithms and methods for matching and computing distances between shapes can be classified roughly based on the locality of the features considered.

I would try to list some, to the best of my knowledge, Try searching for the keywords below

1. Some use differential properties of shapes (curvature-scale-space transform, ...)
2. Or a radial histogram of points (shape-contexts as mentioned in the answer by user1487195)
3. Statistical approaches (Image moments, zernike moments)
4. Fourier descriptors
5. Integral invariants

In general many of the methods will calculate (and may be store) some kind of a shape signature which is simpler than the shape itself also invariant to transformations/occlusion etc. (in case of shape-contexts this is the histogram). Then a matching phase would follow.

In my experience, the most time consuming part of the method of shape-contexts is matching, the signature is calculated rather easily. In matching (or for calculating distance) you need to find a good correspondence between the sampled points by using something similar to Hungarian method combined with thin-plate spline transformation. This might take some time if you have a large database of shapes.

I would recommend trying out Integral invariants. In your case it may be easier than it looks in the papers linked, if you are only dealing with polygons (as opposed to curves).

Integral Invariants for Shape Matching

Integral Invariant Signatures

There is no overall "best" method, only the ones that may suit your needs better. This is because different algorithms have different characteristics. For example methods that depend on more local features has an issue with sensitivity to noise, but may be better at recognising occluded shapes.

So I think you might want to send some time with each of the classes of algorithm (the list above is definitely not exhaustive) studying their characteristics.

Good luck.

Answer 3

EDIT: Original article came from Berkeley Original Article

A great place to start is with this great article from Stanford Shape Matching and object recognition Using Shape Contexts

The article contains many different types of pattern matching (brightness-based, graphed methods), and mathematical formulas to go with it. Most of the formulas evaluate a given image point by point.

You may need to compare a 'snapshot' of your polygon instead of traversing it with a turtle type algo that traces and records the angles of the polygon.