Indexing shapes in image databases using the centroid-radii model

Abstract

In content-based image retrieval systems, the content of an image such as color, shapes and textures are used to retrieve images that are similar to a query image. Most of the existing work focus on the retrieval effectiveness of using content for retrieval, i.e., study the accuracy (in terms of recall and precision) of using different representations of content. In this paper, we address the issue of retrieval efficiency, i.e., study the speed of retrieval, since a slow system is not useful for large image databases. In 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 objects in an image. This facilitates multi-resolution and similarity retrievals. 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 existing 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 (NR-trees) and compare its performance with that of the R-tree. Our experimental study shows that NR-trees can reduce the retrieval time significantly compared 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.