formable templates, on the one hand, or (ii) local edge The use of shape as a cue for indexing into pictorial databases similarity, on the other.
has been traditionally based on global invariant statistics and
In this paper we propose that a symmetry-based repredeformable templates, on the one hand, and local edge correlasentation is an intermediate representation that retains the tion on the other. This paper proposes an intermediate apadvantages of local, edge-based correlation approaches, as proach based on a characterization of the symmetry in edge well as of global, deformable models, and, in addition, maps. The use of symmetry matching as a joint correlation offers two distinct benefits. First, in the computation of a measure between pairs of edge elements further constrains the similarity score between two edge maps, the similarity of comparison of edge maps. In addition, a natural organization the symmetry set of edge maps offers further discriminaof groups of symmetry into a hierarchy leads to a graph-based tion by encoding relational structures of pairs of edge elerepresentation of relational structure of components of shape that allows for deformations by changing attributes of this ments. Second, the hierarchical relations of symmetries relational graph. A graduated assignment graph matching algocaptured in a graph structure offers global discrimination rithm is used to match symmetry structure in images to stored power. The use of symmetry in indexing, however, is faced prototypes or sketches. The results of matching sketches and with several difficult challenges. First, the use of traditional grey-scale images against a small database consisting of a variskeletons, as loci of symmetries of a shape, requires a ety of fish, planes, tools, etc., are promising. © 1998 Academic Press difficult presegmentation of an image into figure and ground. Recent approaches [36,25,39,42] aim to recover symmetries directly from images. We use the approach of
1. Introduction
propagating edge elements to recover symmetries directly from images [38,39,37]. Second, the traditional view of Shape is a significant cue for queries into pictorial dataskeletons does not lead to a natural hierarchical organizabases, yet its potential in practical systems has not been tion of symmetries. In contrast, shocks, or singularities fully explored. The QBIC systems relied on invariant statistics such as shape moments and eccentricity [24]. In another arising from the dynamic evolution of shape, augment the traditional skeleton with a notion of direction, speed, or-approach user-drawn sketches are matched against images [11,2]; e.g., in QVE, the image edges are first abstracted der, and type, as well as a shock grammar which governs the dynamic relationship between shock types and shock through a series of image size reduction, media filtering, coarse edge detection, and global pruning, and then they groups. We utilize this structure and create an intrinsic shock graph as initially proposed in [13]. An alternative are matched against the sketch using a correlation-based similarity score. Gray [10] evaluated this approach and use of symmetry of shape in graphical form is presented in [30], but this requires a segmented shape. The third noted its sensitivity with variations of the sketch from the underlying shape and pointed to the need to include defor-challenge is the matching of these graphs under both similarity transformations (rotation, translation, and scaling), mations in this process. Mehrotra and Grosky matched a chain code representation of edges for retrieval [23]. Del and nonrigid deformations (bending, stretching, etc.). We adapt the ''graduated assignment '' technique [8] to our Bimbo [2,3] in a series of papers advocated the use of deformations and elastic matching both of 1D representa-domain involving both discrete variables representing the relational structure and continuous variables representing tions and 2D templates. Lei and Cooper use algebraic invariants of patches of long contours extracted from the arbitrary deformations as graph attributes and similarity parameters. Fourth, the matching should naturally lead to image. Sclaroff [28] uses modal matching [29] to measure distance from shape prototypes. In summary, the majority the formation of categories and prototypes. Our proposed notion of similarity naturally leads to multiple levels of of these approaches have either relied on (i) global methods such as invariant statistics, shape measures, and de-structural similarity (graph structure), parametric similar-366