Indexing shapes in image databases using the centroid-radii model

In content-based image retrieval systems, the content of an image such as c olor, shapes and textures are used to retrieve images that are similar to a query image. Most of the existing work focus on the retrieval effectivenes s of using content for retrieval, i.e., study the accuracy (in terms of rec all and precision) of using different representations of content. In this p aper, we address the issue of retrieval efficiency, i.e., study the speed o f retrieval, since a slow system is not useful for large image databases. I n particular, we look at using the shape feature as the content of an image , and employ the centroid-radii model to represent the shape feature of obj ects in an image. This facilitates multi-resolution and similarity retrieva ls. Furthermore, using the model, the shape of an object can be transformed into a point in a high-dimensional data space. We can thus employ any exis ting high-dimensional point index as an index to speed up the retrieval of images. We propose a multi-level R-tree index, called the Nested R-trees (N R-trees) and compare its performance with that of the R-tree. Our experimen tal study shows that NR-trees can reduce the retrieval time significantly c ompared to R-tree, and facilitate similarity retrieval. We note that our NR -trees can also be used to index high-dimensional point data commonly found in many other applications. (C) 2000 Elsevier Science B.V. All rights rese rved.