Efficient content-based indexing of large image databases

ABSTRACT

Large image databases have emerged in various applications in recent years. A prime requisite of these databases is the means by which their contents can be indexed and retrieved. A multilevel signature file called the Two Signature Multi-level Signature File (2SMLSF) is introduced as an efficient access structure for large image databases. The 2SMLSF encodes image information into binary signatures and creates a tree structures can be efficiently searched to satisfy a user's query. Two types of signatures are generated. Type I signatures are used at all tree levels except the leaf level and are based only on the domain objects included in the image. Type II signatures, on the other hand, are stored at the leaf level and are based on the included domain objects and their spatial relationships. The 2SMLSF was compared analytically to existing signature file techniques. The 2SMLSF significantly reduces the storage requirements; the index structure can answer more queries; and the 2SMLSF performance significantly improves over current techniques. Both storage reduction and performance improvement increase with the number of objects per image and the number of images in the database. For an example large image database, a storage reduction of 78% may be archieved while the performance improvement may reach 98%.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 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: DAVIS, R. S. AND KAMAMOHANARAO, K. 1983. A two-level superimposed coding scheme for partial match retrieval. Inf. Syst. 8, 4, 273-280.
• 7: A. Del Bimbo , W-X. He , E. Vicario, Using weighted spatial relationships in retrieval by visual contents, Image description and retrieval, Plenum Press, New York, NY, 1998
• 8: Uwe Deppisch, S-tree: a dynamic balanced signature index for office retrieval, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.77-87, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253189]
• 9: 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),
• 10: EGENHOFER, M. J. AND FRANZASA, R. D. 1991. Point-set topological spatial relations. J. Geogr. Inf. Syst. 5, 2, 161-174.
• 11: EGENHOFER, M. J. AND FRANZASA, R. D. 1995. On the equivalence of topological relations. J. Geogr. Inf. Syst. 9, 2, 133-152.
• 12: 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.
• 13: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• 14: Chris Faloutsos , Stavros Christodoulakis, Signature files: an access method for documents and its analytical performance evaluation, ACM Transactions on Information Systems (TOIS), v.2 n.4, p.267-288, Oct. 1984 [doi>10.1145/2275.357411]
• 15: 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]
• 16: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 17: Borko Furht , Stephen W. Smoliar , Hongjiang Zhang, Video and image processing in multimedia systems, Kluwer Academic Publishers, Norwell, MA, 1995
• 18: 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]
• 19: 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.{
• 20: 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.
• 21: 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.
• 22: 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]
• 23: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 24: HILDEBRANDT, J. AND TANG, K. 1996. A two and three dimensional ship database application. 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, 285-302.
• 25: Hou, T. -Y., LuI, P., AND CHUI, M.Y. 1992. A content-based indexing technique using relative geometry features. In Proceedings on Image Storage and Retrieval Systems, SHE--The International Society for Optical Engineering, vol. 1662.
• 26: HUANG, P. W. AND JEAN, Y. R. 1994. Using 2D C~-strings as spatial knowledge representation for image database systems. Pattern Recogn. 27, 9, 1249-1257.
• 27: Ibrahim Kamel , Christos Faloutsos, Hilbert R-tree: An Improved R-tree using Fractals, Proceedings of the 20th International Conference on Very Large Data Bases, p.500-509, September 12-15, 1994
• 28: 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]
• 29: 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]
• 30: LEE, S. Y. AND SHAN, M. K. 1990. Access methods of image databases. Int. J. Pattern Recogn. Artif. Intell. 4, 1, 27-44.
• 31: 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]
• 32: Dik Lun Lee , Young Man Kim , Gaurav Patel, Efficient Signature File Methods for Text Retrieval, IEEE Transactions on Knowledge and Data Engineering, v.7 n.3, p.423-435, June 1995 [doi>10.1109/69.390248]
• 33: Scott T. Leutenegger , J. M. Edgington , Mario A. Lopez, STR: A Simple and Efficient Algorithm for R-Tree Packing, Proceedings of the Thirteenth International Conference on Data Engineering, p.497-506, April 07-11, 1997
• 34: LI, J. Z., Ozsu, T., AND SZAFRON, D. 1996a. Spatial reasoning rules in multimediamanagement systems. Tech. Rep. TR96-05. University of Alberta, Edmonton, Canada.
• 35: LI, X., BHIDE, S., AND KABUKA, M. 1996b. Labeling of MR brain images using Boolean neural network. IEEE Trans. Medical Imaging 15, 5, 628-638.
• 36: King Ip Lin , H. V. Jagadish , Christos Faloutsos, The TV-tree: an index structure for high-dimensional data, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 37: 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.
• 38: PETRAKIS, E. AND ORPHANOUDAKIS, S. 1993. A generalized approach for image indexing and retrieval based on 2-D strings. In Proceedings of First Workshop on Spatial Reasoning (Bergen, Norway, Aug. 1993),
• 39: 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.
• 40: R. W. Picard , T. P. Minka, Vision texture for annotation, Multimedia Systems, v.3 n.1, p.3-14, Feb. 1995 [doi>10.1007/BF01236575]
• 41: ROBERTS, C. S. 1979. Partial-match retrieval via method of superimposed coding. In Proceedings on IEEE, 1624-1642.
• 42: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 43: Rohini K. Srihari, Automatic Indexing and Content-Based Retrieval of Captioned Images, Computer, v.28 n.9, p.49-56, September 1995 [doi>10.1109/2.410153]
• 44: TSAI, C., MANJUNATH, B. S., AND JAGADEESAN, R. 1995. Automated segmentation of brain MR images. Pattern Recogn. 28, 1825-1837.
• 45: TSENG, g., HWANG, T., AND YANG, W. 1994. Efficient image retrieval algorithms for large spatial databases. Int. J. Pattern Recogn. Artif. Intell. 8, 4, 919-944.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Image databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Documentation

Keywords:
content analysis and indexing, document managing, image databases, index generation, multimedia databases