Design and evaluation of algorithms for image retrieval by spatial similarity

ABSTRACT

Similarity-based retrieval of images is an important task in many image database applications. A major class of users' requests requires retrieving those images in the database that are spatially similar to the query image. We propose an algorithm for computing the spatial similarity between two symbolic images. A symbolic image is a logical representation of the original image where the image objects are uniquely labeled with symbolic names. Spatial relationships in a symbolic image are represented as edges in a weighted graph referred to as spatial-orientation graph. Spatial similarity is then quantified in terms of the number of, as well as the extent to which, the edges of the spatial-orientation graph of the database image conform to the corresponding edges of the spatial-orientation graph of the query image.The proposed algorithm is robust in the sense that it can deal with translation, scale, and rotational variances in images. The algorithm has quadratic time complexity in terms of the total number of objects in both the database and query images. We also introduce the idea of quantifying a system's retrieval quality by having an expert specify the expected rank ordering with respect to each query for a set of test queries. This enables us to assess the quality of algorithms comprehensively for retrieval in image databases. The characteristics of the proposed algorithm are compared with those of the previously available algorithms using a testbed of images. The comparison demonstrated that our algorithm is not only more efficient but also provides a rank ordering of images that consistently matches with the expert's expected rank ordering.

REFERENCES

• 1: P. Bollmann , F. Jochum , U. Reiner , V. Weissmann , H. Zuse, The LIVE-project: retrieval experiments based on evaluation viewpoints, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.213-214, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253527]
• 2: C. C. Chang , S. Y. Lee, Retrieval of similar pictures on pictorial databases, Pattern Recognition, v.24 n.7, p.675-681, 1991 [doi>10.1016/0031-3203(91)90034-3]
• 3: Margaret Irvine Chock, A data base management system for image processing, 1982
• 4: FISHER, W. 1958. On grouping for maximum homogeneity. J. Am. Stat. Assoc. 53, 789-798.
• 5: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: GUDWADA, V.N. 1993. A unified framework for retrieval in image databases. Ph.D. dissertation, Univ. of Southwestern Louisiana, Lafayette, La.
• 8: Suh-Yin Lee , Man-Kwan Shan , Wei-Pang Yang, Similarity retrieval of iconic image database, Pattern Recognition, v.22 n.6, p.675-682, November 1989 [doi>10.1016/0031-3203(89)90004-6]
• 9: RAGHAVAN, V. V. AND GUDIVADA, V. N. 1990. A domain independent similarity measure for symbolic images. In 1st Indian Computing Congress (Hyderabad, India, Nov.). 195-203.
• 10: TAMURA, H. AND YOKOYA, N. 1984. Image database systems: A survey. Part. Recog. 17, 1, 29-43.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

General Terms:
Algorithms, Design

Keywords:
image databases, image retrieval, image retrieval systems, rotational invariance, spatial similarity