Recognition of Shapes by Editing their Shock Graphs

Thomas B. Sebastian,  Philip N. Klein,  Benjamin B. Kimia

Brown University, Providence RI, USA

Abstract

We present a novel framework for the recognition of objects based on their silhouettes. The main idea is to measure the distance between two shapes as the minimum extent of deformation necessary for one shape to match another. Since the space of deformations is very high-dimensional, three steps are taken to make the search practical: (i) we define an equivalence class for shapes based on the topological equivalence of their shock graphs; (ii) we define an equivalence class for  deformation paths based on the equivalence of their sequence of shock transitions (locus of shock instabilities); and (iii) we consider deformation paths which consist of a pair of ``simplifying'' paths from each shape to a common shape. Despite this discretization of the shape space and associated deformation paths, which tremendously reduces the search requirement, there still remain numerous paths to consider. We have developed an edit-distance algorithm for shock graphs which finds the optimal path in polynomial time, where the cost of each paths is the sum of the deformation edits to a shock transition. The resulting correspondences between two shock graphs are intuitive as illustrated by numerous examples. We examine the robustness of the match in the presence of an extensive  variety of visual transformations  including boundary perturbations, articulation and deformation of parts, viewpoint variation,  illumination changes leading to segmentation errors, scale changes, and  finally partial occlusion, and show that the matching results are invariant to a significant range of  transformations. The recognition rates on two distinct databases of 99 and 216 shapes each indicate highly successful within category matches (100% in top three matches), and render the framework potentially usable in a range of recognition from shape applications.

Details

Relevant Publications

Acknowledgements