Input description: Two polygonal shapes, and .
Problem description: How similar are and ?
Discussion: Shape similarity is a problem that underlies much of pattern recognition. Consider a system for optical character recognition (OCR). We have a known library of shape models representing letters and the unknown shapes we obtain by scanning a page. We seek to identify an unknown shape by matching it to the most similar shape model.
The problem of shape similarity is inherently ill-defined, because what ``similar'' means is application dependent. Thus no single algorithmic approach can solve all shape matching problems. Whichever method you select, expect to spend a large chunk of time tweaking it so as to achieve maximum performance. Don't kid yourself - this is a difficult problem.
Among your possible approaches are:
Computing the area of the symmetric difference reduces to finding the intersection or union of two polygons, as discussed in Section , and then computing areas, as discussed in . The difficult part of computing Hamming distance is finding the right alignment, or overlay, of the two polygons. For certain applications, such as OCR, the overlay problem is simplified because the characters are inherently aligned with the page and thus not free to rotate. Hamming distance is particularly simple and efficient to compute on bit-mapped images, since after alignment all we do is sum the differences of the corresponding pixels.
Although Hamming distance makes sense conceptually and can be simple to implement, it captures only a crude notion of shape and is likely to be ineffective in most applications.
Which is better, Hamming or Hausdorff? It depends upon your application. As with Hamming distance, computing the right alignment between the polygons can be difficult and time-consuming. Again, Hausdorff distance captures only a crude notion of shape.
How good are the resulting classifiers? It depends upon the application. Like any ad hoc method, neural networks usually take a fair amount of tweaking and tuning to realize their full potential.
One caveat. Because your classifier was developed by a black box, you never really know why your classifier is making its decisions, so you can't know when it will fail. An interesting case was a system built for the military to distinguish between images of cars and tanks. It performed very well on test images but disastrously in the field. Eventually, someone realized that the car images had been filmed on a sunnier day than the tanks, and the program was classifying solely on the presence of clouds in the background of the image!
Implementations: The Stuttgart Neural Network Simulator supports many types of networks and training algorithms, as well as sophisticated graphical visualization tools under X11. It has been ported to many flavors of UNIX. It is available for ftp from ftp.informatik.uni-stuttgart.de [18.104.22.168] in directory /pub/SNNS as SNNSv4.1.tar.gz (1.4 MB, Source code) and SNNSv4.1.Manual.ps.gz (1 MB, Documentation). It may be best to first have a look at the file SNNSv4.1.Readme. More information can be found in the WWW under http://www.informatik.uni-stuttgart.de/ipvr/bv/projekte/snns/snns.html
An alternate distance metric between polygons can be based on its angle turning function [ACH 91]. An implementation in C of this turning function metric by Eugene K. Ressler is provided on the algorithm repository http://www.cs.sunysb.edu/ algorith.
Notes: General books on pattern classification algorithms include [DH73, JD88]. A wide variety of computational geometry approaches to shape similarity testing have been proposed, including [AMWW88, ACH 91, Ata84, AE83, BM89, OW85].
A linear-time algorithm for computing the Hausdorff distance between two convex polygons is given in [Ata83], with algorithms for the general case reported in [HK90].
Related Problems: Graph isomorphism (see page ), thinning (see page ).