A robust framework for content-based retrieval by spatial similarity in image databases

ABSTRACT

A framework for retrieving images by spatial similarity (FRISS) in ima ge databases is presented. In this framework, a robust retrieval by spatial similarity (RSS) algorithm is defined as one that incorporates both directional and topological spatial constraints, retrieves similar images, and recognized images even after they undergo translation, scaling, rotation (both perfect and multiple), or any arbitrary combination of transformatioins. The FRISS framework is discussed and used as a base for comparing various existing RSS algorithms. Analysis shows that none of them satisfies all the FRISS specifications. An algorithm, SIMdtc, is then presented. SIMdtc introduces the concept of a rotation correction angle(RCA) to align objects in one image spatially closer to matching objects in another image for more accurate similarity assessment. Similarity between two images is a function of the number of common objects between them and the closeness of directional and topological spatial relationships between object pairs in both images. The SIMdtc retrieval is invariant under translation, scaling, and perfect rotation, and the algorithm is able to rank multiple rotation variants. The algorithm was tested using synthetic images and the TESSA image database. Analysis shows the robustness of the SIMdtc algorithm over current algorithms.

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: CARLSON, B. 1997. MPEG-7 for multimedia searching: Room for video content recognition?. Adv. Imaging 12, 3 (Mar.), 21-22.
• 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: CHANG, S. K. AND JUNGERT, E. 1991. Pictorial data management based upon the theory of symbolic projections. J. Visual Lang. Comput. 2, 3 (Sept.), 195-215.
• 5: 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]
• 6: 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]
• 7: EAKINS, g. P. 1996. Automatic image content retrieval: Are we going anywhere?. In Proceedings of the 3rd International Conference on Electronic Library and Visual Information Research (May).
• 8: M. J. Egenhofer, Spatial SQL: A Query and Presentation Language, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.86-95, February 1994 [doi>10.1109/69.273029]
• 9: EGENHOFER, M. J. AND FRANZASA, R. D. 1991. Point-set topological spatial relations. J. Geogr. Inf. Syst. 5, 2, 161-174.
• 10: EGENHOFER, M. J. AND FRANZASA, R. D. 1995. On the equivalence of topological relations. J. Geogr. Inf. Syst. 9, 2, 133-152.
• 11: EL-KWAE, E. AND KABUKA, M.A. 1996. A Boolean neural network approach for image understanding. In Proceedings of the Artificial Neural Network in Engineering Conference (ANNIE '96, St Louis, MO, Nov. 10-13). 437-442.
• 12: Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146]
• 13: William I. Grosky , Rajiv Mehrotra, Index-based object recognition in pictorial data management, Computer Vision, Graphics, and Image Processing, v.52 n.3, p.416-436, Dec. 1990 [doi>10.1016/0734-189X(90)90085-A]
• 14: Venkat Naidu Gudivada, A unified framework for retrieval in image databases, University of Southwestern Louisiana, Lafayette, LA, 1993
• 15: Venkat N. Gudivada, TESSA—an image testbed for evaluating 2-D spatial similarity algorithms, ACM SIGIR Forum, v.28 n.2, p.17-36, Fall 1994 [doi>10.1145/195498.195502]
• 16: GUDIVADA, V. N. 1995a. On spatial similarity measures for multimedia applications. In Proceedings of SPIE--Storage and Retrieval for Still Images and Video Databases III (San Jose, CA, Feb. 9-10). SPIE, Bellingham, WA, 363-372.
• 17: GUDIVADA, V. N. 1995b. OR-String: A geometry-based representation for efficient and effective retrieval of images by spatial similarity. Tech. Rep. CS-95-02. School of Electrical and Computer Science, Ohio University, Athens, OH.
• 18: GUDIVADA, V. N. AND JUNG, G. S. 1995. An algorithm for content-based retrieval in multimedia databases. In Proceedings of the International Conference on Multimedia Computing and Systems (Hiroshima, Japan, June 17-23). 90-97.
• 19: 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]
• 20: Hou, T. -Y., LuI, P., AND CHUI, M.Y. 1992. A content-based indexing technique using relative geometry features. In Image Storage and Retrieval Systems. Proceedings of SHE--The International Society for Optical Engineering, vol. 1662.
• 21: HUANG, P. W. AND JEAN, Y. R. 1994. Using 2D C~-strings as spatial knowledge representation for image database systems. Pattern Recognit. 27, 9, 1249-1257.
• 22: T. Joseph , A. F. Cardenas, PICQUERY: A High Level Query Language for Pictorial Database Management, IEEE Transactions on Software Engineering, v.14 n.5, p.630-638, May 1988 [doi>10.1109/32.6140]
• 23: LEE, Y. C. AND CHIN, F. L. 1995. An iconic query language for topological relationships in GIS. J. Geogr. Inf. Syst. 9, 1, 25-46.
• 24: 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]
• 25: 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]
• 26: 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]
• 27: LI, J. Z., Ozsu, T., AND SZAFRON, D. 1996. Spatial reasoning rules in multimediamanagement systems. Tech. Rep. TR96-05. University of Alberta, Edmonton, Canada.
• 28: MARAGOS, P. A. AND SCHAFER, R.W. 1986. Morphological skeleton representation and coding of binary images. IEEE Trans. Acoust. Speech Signal Process. 34, 5 (Oct.), 1228-1244.
• 29: Dimitris Papadias , Timos Sellis , Yannis Theodoridis , Max J. Egenhofer, Topological relations in the world of minimum bounding rectangles: a study with R-trees, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.92-103, May 22-25, 1995, San Jose, California, United States
• 30: PENTLAND, A., PICARD, R. W., AND SCLROFF, S. 1994. Photobook: Content-based manipulation of image databases. In Proceedings of SPIE--Storage and Retrieval for Image and Video Database H (San Jose, CA, Feb. 6-10). SPIE, Bellingham, WA, 34-47.
• 31: PETRAGLIA, G., SEBILTO, M., TuccI, M., AND TORTORA, G. 1996. Normalized index for image databases. In Intelligent Image Database Systems, S. K. Chang, E. Jungert, and G. Tortora, Eds. World Scientific Series on Software Engineering and Knowledge Engineering, vol. 5. World Scientific Publishing Co., Inc., River Edge, NJ, 43-69.
• 32: PETRAKIS, E. 1993. Image representation, indexing and retrieval based on spatial relationships and properties of objects. Ph.D. Dissertation. Dept. of Computer Science, University of Crete.
• 33: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 34: TRAHANIAS, P. E. 1992. Binary shape recognition using the morphological skeleton transform. Pattern Recognit. 25, 1 (Jan. 1992), 1277-1288.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Design, Experimentation, Measurement

Keywords:
content-based retrieval, image databases, multimedia databases, query formulation, retrieval models, similarity retrieval, spatial similarity