Indexing Using Quadtrees:

Indexing procedure is triggered whenever a new image is submitted to the DB: the image is processed and a quadtree-based color structure descriptor is stored in the DB in the form of a XML document.
Retrieval is performed on the basis of a sketch drawn by the user, which is transformed into a quadtree structure consistent with the description of the images in the DB and sent to the retrieval engine. The retrieval module compares the description given by the user with those already available in the DB (in XML format) and returns to the user interface a sorted list of the images. Here is an schema representing Indexing and retrieval system:

Each image, which is submitted for indexing to the database, is partitioned using a quadtree structure, for achieving a compact representation of the color distribution in the image. In this work, the quadtree segmentation is used to extract a compact description of the distribution of colors in an image: a hierarchical structure is associated to the image, in which a dominant color is associated to leaves as well as to intermediate nodes of the quadtree.
The descriptor is extracted in 3 steps:

1. the image color space is quantized to 64 representative colors, following the recommendations by MPEG-7 committee.
2. the quadtree is recursively built from the color-quantized image, up to a given size of blocks represented by each leaf. Each leaf or node is assigned the dominant color in the corresponding image region. The dominant color is defined as the color with the higher percentage of occurrence inside the region represented by the node.

schemair1.png

For matching procedure, color structure descriptor is first extracted from sample image and then matched with the descriptors associated to the images contained in the DB. Now here we can have a result image in certain range of tolerance according to two criterion : Quadtree Structure Similarity (QSS) and Quadtree Color Similarity(QCS). The main concept is that the difference in the structure of two quadtrees can be evaluated through the number of changes in the structure that need to be performed to make one of the quadtrees equivalent to the other. This process is called quadtree warping. Once the two quadtrees have the same structure, they are recursively navigated and the difference is computed between the colors of
the corresponding leaves. The final formula as stated in [2], used for the similarity matching(SM) is the following:
$SM = \alpha_{1}QSS + \alpha_{2}QCS \hfill$