Retrieving similar shapes effectively and efficiently

Abstract

In this paper, we address the following problem: given a large collection of shapes and a query shape, retrieve all shapes (from the shape database) that are similar to the query shape. A generalized centroid-radii model is used to model all forms of shapes - convex shapes, concave shapes and shapes with "holes". Under the model, a shape is represented by a set of vectors, each obtained from the radii emanating from the centroid of a virtual concentric ring. The model can also facilitate 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. To speed up the retrieval of similar shapes, we also propose a multi-level R-tree index, called the Nested R-trees (NR-trees). Unlike traditional high-dimensional index structures that index a high-dimensional point as it is (with its full dimension), the NR-trees splits the dimensionality of the point into a set of lower dimensions that are indexed by levels of the NR-trees. We also proposed a quick filtering mechanism to further prune the search space. We implemented a shape retrieval system that employs the generalized centroid-radii model and the NR-trees with the filtering mechanism. Our experimental study shows the effectiveness of the proposed shape model, and the efficiency of the NR-trees. The results also show that the filtering mechanism can significantly reduce the retrieval time.