A Shock Grammar For Recognition Kaleem Siddiqi Benjamin B. Kimia Department of Electrical Engineering McGill University Montreal, Canada H3A lY2 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, we show that shock patterns are not arbitrary but obey the rules of a grammar, and in addition satisfy specific topo- logical and geometric constraints. Shock hypotheses that violate the grammar or are topologically or geometrically invalid are pruned to enforce global consistency. Sur- vivors 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 recogni- tion: several examples illustrate its stability with rota- tions, scale changes, occlusion and movement of parts, even at very low resolutions. 1 Introduction What does it mean to recognize an object from its shape? Informally, this implies an identification of the shape with a familiar category or class of objects, Fig- ure 1. This notion of categorization is crucial to many vision tasks, such as searching a database of shapes rapidly, reasoning about the attributes of new or un- familiar shapes, etc. Curiously, whereas this ability to categorize appears to come naturally and effortlessly to humans, it has been extremely difficult to formalize for computers. In this paper, we address the computational aspects of this problem; specifically, we investigate the description of generic shape classes from the mathemat- ical perspective of curve evolution. Figure 1: These birds are effortlessly grouped into two cate- gories, based on similarity in “form”. Existing proposals for shape representation emphasize Division of Engineering Brown University Providence, RI 02912 properties of its region, e.g., symmetry and thickness [l], or of its boundary, e.g., curvature extrema I:20] and in- flection points, or of both [2]. An alternate classification is according to those where shape is viewed statically as a combination of primitives, e.g. , generalized cylinders, versus those where shape is explained developmentally via a set of processes acting on a simpler shape [14]. Returning to the region-based symmetrac axis transform (SAT) [l], this view has spawned a vast literature on the theoretical and computational aspects of skeletons. How- ever, it is unfortunate that Blum’s key insig;ht that the SAT provides for qualitative shape descriptions in terms of “shape morphemes”, e.g., disc, worm, wedge, flare, etc., is usually forgotten. Curiously, an evolutionary ap proach to shape description supports and complements this view, and gives it a sound mathematical founda- tion [8, 101. To elaborate, Kimia et al. explore deforma- tions of the shape’s boundary, a special case of which is deformation by a linear function of curvature K: (1) = (Po - PI@ 1 { &O) = C*(s). 1 Here C is the boundary vector of coordinates, N” is the outward normal, s is the path parameter, t is the time duration (magnitude) of the deformation, and PO, are constants. The space of all such deformations is spanned by the ratio /30//3I and time t, constituting the two axes of the reaction-diffusion space. Underlying the represen- tation of shape in this space are a set of shocks [ll], or entropy-satisfying singularities, which develop during the evolution and are classified into four types, Figure 2 (left): 1) A FIRST-ORDER SHOCK is a discontinuity in ori- entation of the shape’s boundary; 2) A SECOND-ORDER SHOCK is formed when two distinct non-neighboring boundary points collide, but none of their immediate neighbors collapse together; 3) A THIRD-OFLDER SHOCK is formed when two distinct non-neighboring boundary points collide, such that the neighboring boundary points also collapse together’ ; and 4) A FOURTH-ORDER SHOCK is formed when a closed boundary collapses onto a single Whereas third-order shocks are not generic they merit a dis- tinct classification because of their psychophysical relevance [9] and the abundance of biological and man-made objects with “bend- 507 1063-6919/96 $5.00 0 1996 IEEE Authorized licensed use limited to: The University of Utah. Downloaded on February 18,2010 at 11:38:54 EST from IEEE Xplore. Restrictions apply.Figure 2: LEFT: The four shock types. & RIGHT: The sides of the shape triangle represent continua of shapes; the ex- tremes correspond to the “parts”, “bends” and “protmsions” nodes [9]. point. While these definitions are intuitive, they do not easily lend themselves to algorithms for shock detection. A key idea of this paper is that shock computations can be made robust by relying not only on better (subpixel) local detectors and classifiers, but also on global inter- actions between shocks, through a shock grammar. In related work, Leymarie and Levine have simulated the grassfire transform using active contours [13]; Scott et al. have suggested the use of wave propagation to obtain the full symmetry set [21]; Kelly and Levine have demon- strated the use of annular operators in obtaining coarse object descriptions from real imagery [7]; and Pizer et al. have proposed a computational model for object rep resentation via “cores”, or regions of high medialness in intensity images [2]. Our work extends the above ap- proaches in a number of ways, which are perhaps best un- derstood in the context of the distinction between shocks and skeletons. The set of shocks which form along the reaction axis reduces to the traditional skeleton when information re- garding type, group, and salience is discarded [23]. How- ever, first, the notion of type is essential to capture qual- itative aspects of shape, leading to generic perceptual shape classes’ and algorithms for obtaining them, Sec- tion 2. Second, the grouping of shocks depends not only on their type but also on sequential, geometric and topo- logical constraints obtained