TESSA—an image testbed for evaluating 2-D spatial similarity algorithms

ABSTRACT

In multimedia database applications, a major class of users' requests require retrieving those images in the database that are spatially similar to the query image. To process such queries, a spatial similarity algorithm is required. A spatial similarity algorithm assesses the degree to which the spatial relationships among the domain objects in a database image conform to those specified in the query image. The recent ubiquitous interest in multimedia information systems has spurred a great interest in spatial similarity algorithms. A standard testbed of images is required not only to systematically evaluate these algorithms but also to compare and contrast them. However, there is no such testbed of images available for this purpose.In this paper, we describe a collection of images, referred to as TESSA, as a testbed for investigating the robustness of spatial similarity algorithms and their further use in evaluating the retrieval effectiveness of these algorithms. The TESSA collection comprises 160 images and are produced by generating 15 variants of each of the 10 original images. Image variants are produced by scale, rotation, and translation, and by an arbitrary composition of these three transformations. The variants are designed to inquire into the robustness of spatial similarity algorithms. To facilitate their further use in evaluating the retrieval effectiveness, each image in TESSA is considered as a query in turn, and an expert is asked to provide a rank ordering of the TESSA images with respect to the query image vis-a-vis expert provided rank ordering. System provided rank ordering for a query image is the rank ordering of TESSA images induced by a spatial similarity algorithm with respect to the query. Retrieval effectiveness of spatial similarity algorithms is then characterized by using R_norm measure. This measure is based on both the expert and system provided rank orderings.

REFERENCES

• 1: D. Benson and G. Zick. Spatial and symbolic queries for 3-d image data. In <i>Storage and Retrieval for Image and Video Databases</i>, pages 134--145, SPIE, Vol. 1908, 1993.
• 2: 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]
• 3: 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]
• 4: S. K. Chang , C. W. Yan , D. C. Dimitroff , T. Arndt, An Intelligent Image Database System, IEEE Transactions on Software Engineering, v.14 n.5, p.681-688, May 1988 [doi>10.1109/32.6147]
• 5: S. -K. Chang , E. Jungert , Y. Li, Invited talk: the design of pictorial databases based upon the theory of symbolic projections, Proceedings of the first symposium on Design and implementation of large spatial databases, p.303-323, February 1990, Santa Barbara, California, United States
• 6: S. K. Chang, C. Lee, and C. Dow. A 2-D String matching algorithm for conceptual pictorial queries. In <i>Image Storage and Retrieval Systems</i>, pages 47--58, SPIE, Vol. 1662, 1992.
• 7: S. K. Chang , Q. Y. Shi , C. W. Yan, Iconic indexing by 2-D strings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.3, p.413-428, May 1987 [doi>10.1109/TPAMI.1987.4767923]
• 8: V. Gudivada and G. Jung. <i>A Linear Time Algorithm for Retrieval by Spatial Similarity in Multimedia Database Applications.</i> Technical Report, Ohio University, Department of Computer Science, Athens, OH, 1994. TR-19943.
• 9: Venkat N. Gudivada , Vijay V. Raghavan, Design and evaluation of algorithms for image retrieval by spatial similarity, ACM Transactions on Information Systems (TOIS), v.13 n.2, p.115-144, April 1995 [doi>10.1145/201040.201041]
• 10: V. Gudivada and V. Raghavan. A system for retrieving images by content. In <i>Intelligent Multimedia Information Retrieval Systems and Management</i>, Rockefeller University, New York, October 1994.
• 11: T.-Y. Hou et al. A content-based indexing technique using relative geometry features. In <i>Storage and Retrieval for Image and Video Databases</i>, pages 59--68, SPIE, Vol. 1662, 1992.
• 12: Suh-Yin Lee , Fang-Jung Hsu, 2D C-string: a new spatial knowledge representation for image database systems, Pattern Recognition, v.23 n.10, p.1077-1087, 1990 [doi>10.1016/0031-3203(90)90004-5]
• 13: Suh-Yin Lee , Fang-Jung Hsu, Spatial reasoning and similarity retrieval of images using 2D C-string knowledge representation, Pattern Recognition, v.25 n.3, p.305-318, March 1992 [doi>10.1016/0031-3203(92)90112-V]
• 14: 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]
• 15: A. Prasad Sistla , Clement T. Yu , R. Haddad, Reasoning About Spatial Relationships in Picture Retrieval Systems, Proceedings of the 20th International Conference on Very Large Data Bases, p.570-581, September 12-15, 1994

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems

General Terms:
Algorithms, Experimentation, Measurement