| Object recognition is one of the central problems in computer vision, and shape is an important cue. This thesis deals primarily with two shape-based recognition approaches. The first approach relies on matching the outline curves of shapes by comparing their intrinsic properties like length and curvature. The optimal alignment is found by minimizing an energy functional using dynamic programming. The notion of an alignment curve is introduced to ensure symmetric treatment of the curves being matched. While the curve-based approach gives excellent recognition results for some databases, curves do not have a notion of the interior of the shape, and is not robust to those variations in shape that affect the overall part structure.; The limitations of the curve-based approach necessitates the second approach, based on matching shock graphs of shapes. The distance between two shapes is defined in terms of a minimum-cost deformation path between them. The transitions of the shock graph are used to define equivalence classes for shapes and deformation paths to make the search for the optimal path practical. The edit distance algorithm is used to find the optimal path. This approach is robust in the presence of boundary perturbations, articulation and deformation of parts, viewpoint variation, occlusion, etc., and gives intuitive results for indexing into shape databases.; Shape comparison techniques tend to be expensive to compute, which necessitates the design of efficient algorithms to search the shape database. A shape indexing approach that relies on a bestfirst search of the k nearest neighbor graph is developed. This method is approximate, but gives good indexing efficiency.; Segmentation, or extracting the objects of interest from the background, is a crucial step for shape-based recognition. This thesis describes a level set-based method to segment grey-scale images. The main idea is to use the inter-region shock graph as a predictor of the true boundaries, and to modulate the evolution of the regions. This approach, namely, the Skeletally Coupled Deformable Model (SCDM), resolves the lack of convergence of traditional deformable models. |
