Back      Top     Next                   Kolloquium - DVI - F.Leymarie

Graph Matching Approach (Graduated Assignment)

We modify the graduated assignment algorithm to implement shock graph matching. Several factors motivate the use of this algorithm:

1. First, it enforces two-way assignment via "soft-assign" in contrast to classical relaxation labeling type algorithms which enforce one-way assignment.

2. Second, it avoids poor local minimum by the use of graduated convexity continuation technique.

3. 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.

4. Fourth, the algorithm handles missing/extra nodes/links, which is important in matching shapes, and is superior in this regard to other existing techniques.

5. Finally, the algorithm is stable under noisy conditions.

Examples of matches between shock graphs of fish & 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 shapes

Back      Top     Next