Recognition of shapes by editing shock graphs

This paper presents a novel recognition framework which is based on matching shock graphs of 2D shape outlines, where the distance between two shapes is defined to be the cost of the least action path deforming one shape to another. Three key ideas render the implementation of this frame-work practical. First, the shape space is partitioned by defining an equivalence class on shapes, where two shapes with the same shock graph topology are considered to be equivalent. Second, the space of deformations is discretized by defining all deformations with the same sequence of shock graph transitions as equivalent. Shock transitions are points along the deformation where the shock graph topol-ogy changes. Third, we employ a graph edit distance al-gorithm that searches in the space of all possible transition sequences and finds the globally optimal sequence in poly-nomial time. The effectiveness of the proposed technique in the presence of a variety of visual transformations in-cluding occlusion, articulation and deformation of parts, shadow and highlights, viewpoint variation, and boundary perturbations is demonstrated. Indexing into two separate databases of roughly 100 shapes results in 13242$5 accuracy for top three matches and 6679845 for the next three matches.