Shock graphs and shape matching

We have been developing a theory for the generic representation of 2-D shap e, where structural descriptions are derived from the shocks (singularities ) of a curve evolution process, acting on bounding contours. We now apply t he theory to the problem of shape matching. The shocks are organized into a directed, acyclic shock graph, and complexity is managed by attending to t he most significant (central) shape components first. The space of all such graphs is highly structured and can be characterized by the rules of a sho ck graph grammar. The grammar permits a reduction of a shock graph to a uni que rooted shock tree. We introduce a novel tree matching algorithm which f inds the best set of corresponding nodes between two shock trees in polynom ial time. Using a diverse database of shapes, we demonstrate our system's p erformance under articulation, occlusion, and moderate changes in viewpoint .