# U of U CS 7960 - A Shock Grammar For Recognition (7 pages)

Previewing pages*1, 2*of 7 page document

**View the full content.**## A Shock Grammar For Recognition

Previewing pages
*1, 2*
of
actual document.

**View the full content.**View Full Document

## A Shock Grammar For Recognition

0 0 109 views

- Pages:
- 7
- School:
- University of Utah
- Course:
- Cs 7960 - Special Topics

**Unformatted text preview:**

A Shock Grammar For Recognition Kaleem Siddiqi Benjamin B Kimia Department of Electrical Engineering McGill University Montreal Canada H3A lY2 Division of Engineering Brown University Providence RI 02912 Abstract properties of its region e g symmetry and thickness l or of its boundary e g curvature extrema I 20 and inflection 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 However 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 a p proach to shape description supports and complements this view and gives it a sound mathematical foundation 8 101 To elaborate Kimia et al explore deformations of the shape s boundary a special case of which is deformation by a linear function of curvature K 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 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 1 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 Figure 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 unfamiliar 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 mathematical perspective of curve evolution O Po P I C s 1 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 representation 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 orientation 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 Figure 1 These birds are effortlessly grouped into two categories based on similarity in form Whereas third order shocks are not generic they merit a distinct classification because of their psychophysical relevance 9 and the abundance of biological and man made objects with bend Existing proposals for shape representation emphasize 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 Thlrd Ordcr Sscond Order F o uourth r t h Order Flrst Order First Figure 2 LEFT The four shock types RIGHT The sides of the shape triangle represent continua of shapes the extremes correspond to the parts bends and protmsions nodes 9 a b 5 d D f Figure 3 A classification of shock types based on the tangents and the local neighborhood of the two shock generating boundary points The curvature disparity is the sum of the two signed curvatures point While these definitions are intuitive they do not easily lend themselves t o algorithms for shock detection A key idea of this paper is t h a t shock computations can be made robust by relying not only on better subpixel local detectors and classifiers but also on global interactions 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 t o obtain the full symmetry set 21 Kelly and Levine have demonstrated 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 r e p resentation via cores or regions of high medialness in intensity images 2 Our work extends the above approaches in a number of ways which are perhaps best understood in the context of the distinction between shocks and skeletons 2 Shock Classification and Detection Local O p e r a t o r s In the design of shock detection operators we face two primary challenges t h a t of arriving at a complete shock classification scheme which leads to a computational algorithm for detection and t h a t of obtaining accurate geometric estimates without blurring across singularities We discuss shock classification and detection in turn 2 1 Classification of Shocks An intuitive approach is t o classify a shock based on properties of the boundary points which collide at it Figure 3 Whereas this classification provides insight it is difficult t o implement directly e g the mapping of a shock to its

View Full Document