Many methods have been developed to approach the computational complexity of graph matching, e.g. [15,20]; see a brief review in [9]. We modify the graduated assignment algorithm [6] to implement shock graph matching. Several factors motivate the use of this algorithm: First, it enforces two-way assignment via softassign [25,14] in contrast to relaxation labeling type algorithms which enforce one-way assignment. Second, it avoids poor local minimum by the use of graduated convexity [4,29] continuation technique. Third, this algorithm is efficient in comparison to current techniques (an order of magnitude better than relaxation labeling), partly due to an explicit encoding of sparsity. Fourth, the algorithm handles missing/extra nodes/links, which is important in matching shapes, and is superior in this regard to other existing techniques [6]. Finally, the algorithm is stable under noisy conditions [6]. For a more in-depth explanation of the algorithm, as well as references, please see our paper.
Here are some examples of matches between shock graphs of fish and rabbits respectively:
|
|
|
|
The following table shows the similarity of shapes across a continuum.
The following table shows the results of matching user-drawn sketches as well as grey-scale images against our database of 25 shapes:
