A Shock Grammar for Recognition

Abstract

We confront the theoretical and practical difficulties of computing a representation for two-dimensional shape, based on shocks or singularities that arise as the shape's boundary is deformed. First, we develop subpixel local detectors for finding and classifying shocks. Second, to show that shock patterns are not arbitrary but obey the rules of a grammar, and in addition satisfy specific topological and geometric constraints. Shock hypotheses that violate the grammar or are topologically or geometrically invalid are pruned to enforce global consistency. Survivors are organized into a hierarchical graph of shock groups computed in the reaction-diffusion space, where diffusion plays a role of regularization to determine the significance of each shock group. The shock groups can be functionally related to the object's parts, protrusions and bends, and the representation is suited to recognition: several examples illustrate its stability with rotations, scale changes, occlusion and movement of parts, even at very low resolutions.