Shape Codification Indexing and Retrieval Using the Quad-Tree Structure

Shape Codification Indexing and Retrieval Using the Quad-Tree Structure

Saliha Aouat (Department of Computer Science, LRIA Laboratory, USTHB University, Algiers, Algeria)
Copyright: © 2013 |Pages: 21
DOI: 10.4018/ijcvip.2013010101
OnDemand PDF Download:
List Price: $37.50


The author presents in this paper a new approach for indexing and Content-based image retrieval based on the Quad-tree structure. The 3D objects are represented by their silhouettes and codified following the filling rate of each quadrant at different levels of the quad-tree subdivision. The author proposes a modified linear codification for silhouettes, this method improves the processing time because, in opposite to the traditional algorithms, the author’s algorithm has not a processing time that is proportional to the number of pixels in the image. As the same descriptor may characterize a set of different shapes, the author proposes also, efficient similarity measures to distinguish different objects having the same index in order to apply the approach to the retrieval process.
Article Preview

1. 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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 7: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 6: 2 Issues (2016)
Volume 5: 2 Issues (2015)
Volume 4: 2 Issues (2014)
Volume 3: 4 Issues (2013)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing