[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Efficient and effective Querying by Image Content

  • Published:
Journal of Intelligent Information Systems Aims and scope Submit manuscript

Abstract

In the QBIC (Query By Image Content) project we are studying methods to query large on-line image databases using the images' content as the basis of the queries. Examples of the content we use include color, texture, shape, position, and dominant edges of image objects and regions. Potential applications include medical (“Give me other images that contain a tumor with a texture like this one”), photo-journalism (“Give me images that have blue at the top and red at the bottom”), and many others in art, fashion, cataloging, retailing, and industry. We describe a set of novel features and similarity measures allowing query by image content, together with the QBIC system we implemented. We demonstrate the effectiveness of our system with normalized precision and recall experiments on test databases containing over 1000 images and 1000 objects populated from commercially available photo clip art images, and of images of airplane silhouettes. We also present new methods for efficient processing of QBIC queries that consist of filtering and indexing steps. We specifically address two problems: (a) non Euclidean distance measures; and (b) the high dimensionality of feature vectors. For the first problem, we introduce a new theorem that makes efficient filtering possible by bounding the non-Euclidean, full cross-term quadratic distance expression with a simple Euclidean distance. For the second, we illustrate how orthogonal transforms, such as Karhunen Loeve, can help reduce the dimensionality of the search space. Our methods are general and allow some “false hits” but no false dismissals. The resulting QBIC system offers effective retrieval using image content, and for large image databases significant speedup over straightforward indexing alternatives. The system is implemented in X/Motif and C running on an RS/6000.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • ACM SIGIR.Proceedings of International Conference on Multimedia Information Systems, Singapore, 1991.

  • Franz Aurenhammer. Voronoi diagrams — a survey of a fundamental geometric data structure.ACM Computing Surveys, 23(3)345–405, September 1991.

    Google Scholar 

  • D. Ballard and C. Brown.Computer Vision. Prentice Hall, 1982.

  • N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The r *-tree: an efficient and robust access method for points and rectangles.ACM SIGMOD, pages 322–331, May 1990.

  • Elizabeth Binaghi, Isabella Gagliardi, and Raimondo Schettini. Indexing and fuzzy logic-based retrieval of color images. InVisual Database Systems, II, IFIP Transactions A-7, pages 79–92. Elsevier Science Publishers, 1992.

  • W. E. Blanz, D. Petkovic, and J. L. Sanz.Algorithms and Architectures for Machine Vision, pages 279–315. ed. C.H. Chen, Marcel Decker Inc., 1989.

  • A. E. Cawkell. Imaging systems and picture collection management: A review.Information Services and Use, 12:301–325, 1992.

    Google Scholar 

  • C. C. Chang and S. Y. Lee. Retrieval of similar pictures on pictorial databases.Pattern Recognition, 24(7):675–680, 1991.

    Google Scholar 

  • Chin-Chen Chang and Tzong-Chen Wu. Retrieving the most similar symbolic pictures from pictorial databases.Information Processing and Management, 28(5):581–588, 1992.

    Google Scholar 

  • Zen Chen and Shinn-Ying Ho. Computer vision for robust 3D aircraft recognition with fast library search.Pattern Recognition, 24(5):375–390, 1991.

    Google Scholar 

  • S. Christodoulakis, M. Theodoridou, F. Ho, M. Papa, and A. Pathria. Multimedia document presentation, information extraction and document formation in minos: a model and a system.ACM TOOIS, 4(4), October 1986.

  • R. Duda and P. Hart.Pattern Classification and Scene Analysis. Wiley, New York, 1973.

    Google Scholar 

  • P. G. B. Enser. Query analysis in a visual information system.Journal of Document and Text Management, l(l):25–52, 1993.

    Google Scholar 

  • W. Equitz. Retrieving images from a database using texture — algorithms from the QBIC system. Research report, IBM Almaden Research Center, San Jose, CA, 1993.

    Google Scholar 

  • C. Faloutsos. Signature-based text retrieval methods: a survey.IEEE Data Engineering, 13(l):25–32, March 1990.

    Google Scholar 

  • Edward A. Fox. Advances in interactive digital multimedia systems.IEEE Computer, 24(10):9–21, October 1991.

    Google Scholar 

  • K. Fukunaga.Introduction to Statistical Pattern Recognition. Academic Press, second edition, 1990.

  • William I. Grosky, Peter Neo, and Rajiv Mehrotra. A pictorial index mechanism for model-based matching.Data and Knowledge Engineering, 8:309–327, 1992.

    Google Scholar 

  • A. Guttman. R-trees: a dynamic index structure for spatial searching.Proc. ACM SIGMOD, pages 47–57, June 1984.

  • Kyoji Hirata and Toshikazu Kato. Query by visual example. InAdvances in Database Techonology EDBT '92, Third International Conference on Extending Database Technology, Vienna, Austria, March 1992. Springer-Verlag.

  • G. M. Hunter and K. Steiglitz. Operations on images using quad trees.IEEE Trans, on PAMI, PAMI-1(2):145–153, April 1979.

    Google Scholar 

  • Mikihiro Ioka. A method of defining the similarity of images on the basis of color information. Technical report RT-0030, IBM Tokyo Research Lab, 1989.

  • M. A. Ireton and C. S. Xydeas. Classification of shape for content retrieval of images in a multimedia database. InSixth International Conference on Digital Processing of Signals in Communications, pages 111–116, Loughborough, UK, 2–6 Sept., 1990. FEE.

    Google Scholar 

  • H. V. Jagadish. Spatial search with polyhedra.Proc. Sixth IEEE Int'l Conf. on Data Engineering, February 1990.

  • H. V. Jagadish. A retrieval technique for similar shapes. InInternational Conference on Management of Data, SIGMOD 91, pages 208–217, Denver, CO, May 1991. ACM.

    Google Scholar 

  • R. Jain and W. Niblack. Nsf workshop on visual information management, February 1992.

  • Anil K. Jain.Fundamentals of Digital Image Procssing. Prentice-Hall, Englewood Cliffs, NJ, 1989.

    Google Scholar 

  • T. Kato, T. Kurita, H. Shimogaki, T. Mizutori, and K. Fujimura. A cognitive approach to visual interaction. InInternational Conference of Multimedia Information Systems, MIS'91, pages 109–120. ACM and National University of Singapore, January 1991.

  • Toshikazu Kato, Takio Kurita, Nobuyuki Otsu, and Kyoji Hirata. A sketch retrieval method for full color image database. InInternational Conference on Pattern Recognition (ICPR), pages 530–533, The Hague, The Netherlands, September 1992. IAPR.

    Google Scholar 

  • Yehezkel Lamdan and Haim J. Wolfson. Geometric hashing: A general and efficient model-based recognition scheme. In2nd International Conference on Computer Vision (ICCV), pages 238–249, Tampa, Florida, 1988. IEEE.

    Google Scholar 

  • Suh-Yin Lee and Fang-Jung Hsu. 2d c-string: A new spatial knowledge representation for image database systems.Pattern Recognition, 23(10):1077–1087, 1990.

    Google Scholar 

  • Suh-Yin Lee and Fang-Jung Hsu. Spatial reasoning and similarity retrieval of images using 2D C-string knowledge representation.Pattern Recognition, 25(3):305–318, 1992.

    Google Scholar 

  • M. D. McIlroy. Development of a spelling list.IEEE Trans, on Communications, COM-30(l):91–99, January 1982.

    Google Scholar 

  • Rajiv Mehrotra and William I. Grosky. Shape matching utilizing indexed hypotheses generation and testing.IEEE Transactions on Robotics and Automation, 5(l):70–77, 1989.

    Google Scholar 

  • Makoto Miyahara and Yasuhiro Yoshida. Mathematical transform of (R,G,B) color data to Munsell (H,V,C) color data. InVisual Communication and Image Processing, volume 1001, pages 650–657. SPIE, 1988.

  • David Mumford. The problem with robust shape descriptions. InFirst International Conference on Computer Vision, pages 602–606, London, England, June 1987. IEEE.

    Google Scholar 

  • David Mumford. Mathematical theories of shape: Do they model perception ? InGeometric Methods in Computer Vision, volume 1570, pages 2–10. SPEE, 1991.

  • A. Desai Narasimhalu and Stavros Christodoulakis. Multimedia information systems: the unfolding of a reality.IEEE Computer, 24(10):6–8, October 1991.

    Google Scholar 

  • W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, and P. Yanker. The QBIC project: Querying images by content using color, texture, and shape. In1S&T/SPIE 1993 International Symposium on Electronic Imaging: Science & Technology, Conference 1908, Storage and Retrieval for Image and Video Databases, February 1993.

  • J. Nievergelt, H. Hinterberger, and K. C. Sevcik. The grid file: an adaptable, symmetric multikey file structure.ACM TODS, 9(1):38–71, March 1984.

    Google Scholar 

  • Michael Otterman. Approximate matching with high dimensionality r-trees. M.Sc. scholarly paper, Dept. of Computer Science, Univ. of Maryland, College Park, MD, 1992. supervised by C. Faloutsos.

    Google Scholar 

  • William K. Pratt.Digital Image Processing. John Wiley and Sons, Inc, New York, NY, second edition, 1991.

    Google Scholar 

  • C. R. Rao.Linear Statistical Inference and Its Applications. Wiley Series In Probability and Mathematical Statistics. John Wiley & Sons, New York, second edition, 1973.

    Google Scholar 

  • G. Salton and M.J. McGill.Introduction to Modern Information Retrieval. McGraw-Hill, 1983.

  • H. Samet.The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1989.

  • D. G. Severance and G. M. Lohman. Differential files: Their application to the maintenance of large databases.ACM TODS, l(3):256–267, September 1976.

    Google Scholar 

  • Dennis Shasha and Tsong-Li Wang. New techniques for best-match retrieval.ACM TOIS, 8(2):140–158, April 1990.

    Google Scholar 

  • Michael J. Swain and Dana H. Ballard. Color indexing.International Journal of Computer Vision, 7(1):11–32, 1991.

    Google Scholar 

  • Hideyuki Tamura, Shunji Mori, and Takashi Yamawaki. Texture features corresponding to visual perception.IEEE Transactions on Systems, Man, and Cybernetics, SMC-8(6):460–473, 1978.

    Google Scholar 

  • Satoshi Tanaka, Mitsuhide Shima, Jun'ichi Shibayama, and Akira Maeda. Retrieval method for an image database based on topological structure. InApplications of Digital Image Processing, volume 1153, pages 318–327. SPE, 1989.

  • Gabriel Taubin and David B. Cooper. Recognition and positioning of rigid objects using algebraic moment invariants. InGeometric Methods in Computer Vision, volume 1570, pages 175–186. SPJE, 1991.

  • Koji Wakimoto, Mitsuhide Shima, Satoshi Tanaka, and Akira Maeda. An intelligent user interface to an image database using a figure interpretation method. In9th Int. Conference on Pattern Recognition, volume 2, pages 516–991, 1990.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Maryland, College Park, MD

    C. Faloutsos

  2. IBM Almaden Research Center, K54/802, 650 Harry Road, 95120-6099, San Jose, CA

    R. Barber, M. Flickner, J. Hafner, W. Niblack & D. Petkovic

  3. Previously with IBM Almaden Research Center, Storm Technology, 1861 Landings Drive, 94043, Mountain View, CA

    W. Equitz

Authors
  1. C. Faloutsos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. Barber
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. Flickner
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. J. Hafner
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. W. Niblack
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. D. Petkovic
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. W. Equitz
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

On sabbatical from Univ. of Maryland, College Park. His work was partially supported by SRC, by the National Science Foundation under the grant IRI-8958546 (PYI).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Faloutsos, C., Barber, R., Flickner, M. et al. Efficient and effective Querying by Image Content. J Intell Inf Syst 3, 231–262 (1994). https://doi.org/10.1007/BF00962238

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00962238

Keywords

Search

Navigation