Article Preview
Top1. Introduction
The easiest way to recognize a query object is to find the model (or the models) in the image database that look alike the query. The problem can be considered like an indexing problem. The indexing and retrieval processes lead to characterize the objects with descriptors and distances in order to compare and classify them.
Various methods have been developed in order to represent shapes in an abstract and efficient way while still preserving important shape features. The most interesting methods may be classified as follow:
Part-based methods where a silhouette is decomposed into parts (Aouat & Larabi, 2009a ; Aouat & Larabi, 2009b; Mokhtarian, 1995; Pitas & Venetsanopoulos, 1990; Rosin, 1990; Siddiqi & Kimia, 1995; Wang et al., 2011), aspect-graph methods that are viewer-centered representations of a three-dimensional object (Cyr & Kimia, 2004; Koenderink & Doorn, 1976), methods that use medial axis of silhouettes (Geiger et al., 2003; Ruberto, 2004; Arandjelovic & Zisserman, 2010), methods based on the shock graph (Trinh & Kimia, 2011; Siddiqi & Kimia 1996), methods using graph for shape representation (Badawy & Kamel, 2002; Ma, & Latecki, 2011), approximation of outline shape by 2D features (Cronin, 2003; Grosky & Mehrota, 1990; Nelson & Selinger, 1998; Petrakis et al., 2002; Berretti & Bimbo, 2000), methods based on the reference points of outline shapes (Mokhtarian & Mackworth, 1992; Alvarado et al., 2002; Shao & Kittler, 1999), methods based on the attributes of outline shapes (Arica & Vural, 2003; Bernier & Landry 2003; Orrite & Herreo, 2004; Sethi et al., 2004), methods based on the shape context introduced to describe the coarse distribution of the rest of the shape with respect to a given point of the shape (Belongie et al., 2002), appearance-based methods (Davis, 2002; Yang et al., 2008), and tree based methods specially quad-tree representation methods (Stewart, 1986; Guttman, 1984; Claccia et al., 1997; Hunter & Steiglitz, 1979; Graham, 1972; Hadi et al., 2009; Aouat & Larabi, 2010b).
Hierarchical data structures are important representations in many domains. Quad-trees and related hierarchical data structures are surveyed in (Samet, 1980; Samet, 1984).
Quad-trees are used extensively in computer graphics and computer vision. Mainly, quad-trees can be manipulated and accessed much quicker than other models. For that reason, quad-trees are very popular in fractal graphics. Recursive pictures can be implemented easily using quad-trees. Other advantages of quad-trees include:
- •
Erasing a picture takes only one step. All that is required is to set the root node to neutral;
- •
Zooming to a particular quadrant in the tree is a one step operation;
- •
To reduce the complexity of the image, it suffices to remove the final level of nodes;
- •
Accessing particular regions of the image is a very fast operation. This is useful for updating certain regions of an image.