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

CBIR with a subspace tree: principal component analysis versus averaging

  • Regular Paper
  • Published:
Multimedia Systems Aims and scope Submit manuscript

Abstract

The subspace tree is an indexing method for large multi-media databases. The search in such a tree starts at the subspace with the lowest dimension. In this subspace, the set of all possible similar images is determined. In the next subspace, additional metric information corresponding to a higher dimension is used to reduce this set. We compare theoretically and empirically data-dependent mappings into subspaces (principal component analysis) with data-independent mapping (averaging). The empirical experiments are performed on an image collection of 30,000 images.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Andoni, A., Dater, M., Indyk, P., Immorlica, N., Mirrokni, V.: Locality-sensitive hashing using stable distributions. In: Darrell, T., Indyk, P., Shakhnarovich, G. (eds.) Nearest Neighbor Methods in Learning and Vision: Theory and Practice, chap. 4, MIT-Press, Cambridge (2006)

  2. Baeza-Yates, R., Ribeiro-Neto, B.: Modeling. In: Baeza-Yates, R., Ribeiro-Neto, B. (eds.) Modern Information Retrieval. chap. 2, pp. 19–71. Addison-Wesley, (1999)

  3. Blei, D.M., Jordan, M.I.: Modeling annotated data. In: Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pp. 127–134 (2003)

  4. Böhm, C., Berchtold, S., Kei, D., A.K.: Searching in high-dimensional spaces—index structures for improving the performance of multimedia databases. ACM Computing Surveys, 33(3), 322–373 (2001)

  5. Burt, P.J., Adelson, E.H.: The laplacian pyramidas a compact image code. IEEE Trans. Commun. COM-31(4), 532–540 (1983)

    Article  Google Scholar 

  6. Chen, Y., Wang, J.Z.: Image categorization by learning and reasoning with regions. J. Mach. Learn. Res.5, 913–939 (2004)

    Google Scholar 

  7. Ciaccia, P., Patella, M.: Searching in metric spaces with user-defined and approximate distances. ACM Trans. Database Syst. 27(4), 398–437 (2002)

    Google Scholar 

  8. de Sá, J.P.M.: Pattern Recognition: Concepts, Methods and Applications. Springer, Heidelberg (2001)

    Google Scholar 

  9. Dunckley, L.: Multimedia Databases, An Object-Rational Approach. Addison Wesley, USA (2003)

    Google Scholar 

  10. Faloutsos, C.: Modern information retrieval. In: Baeza-Yates, R., Ribeiro-Neto, B. (eds.) Modern Information Retrieval, chap. 12, pp. 345–365. Addison-Wesley, Reading (1999)

  11. Faloutsos, C., Barber, R., Flickner, M., Hafner, J., Niblack, W., Petkovic, D., Equitz, W.: Efficient and effective querying by image content. J. Intell. Inf. Syst. 3(3/4), 231–262 (1994)

    Article  Google Scholar 

  12. Flickner, M., Sawhney, H., Niblck, W., Ashley, J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petkovic, D., Steele, D., Yanker, P.: Query by image and video content the QBIC system. In: IEEE Computer, pp. 23–32 (1995)

  13. Fonseca, M.J., Jorge, J.A.: Indexing high-dimensional data for content-based retrieval in large databases. In: Proceedings of the 8th International Conference on Database Systems for Advanced Applications, pp. 267–274 (2003)

  14. Gonzales, R.C., Woods, E.W.: Digital Image Processing, second edition. Prentice Hall, Upper Saddle River (2001)

    Google Scholar 

  15. Hove, L.-J.: Extending image retrieval systems with a thesaurus for shapes. Master’s thesis, Institute for Information and Media Sciences—University of Bergen (2004)

  16. Jedrzejek C., C.L.: Fast closest codewordsearch algorithm for vector quantization. In: Proceedings of the IEEE Information Theory Workshop ITW’95 (1995)

  17. Jeon, J., Lavrenko, V., Manmatha, R.: Automatic image annotation and retrieval using cross-media relevance models. In: Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pp. 119–126 (2003)

  18. Lang, S.: Linear Algebra. Addison-Wesley, Reading (1970)

    MATH  Google Scholar 

  19. Li, J., Wang, J.: Automatic linguistic indexing of pictures by a statistical modeling approach. IEEE Trans. Pattern Anal. Mach. Learn. 25(9), 1075–1088 (2003)

    Article  Google Scholar 

  20. Li, J., Wang, J.: Studying digital imagery of ancient paintings by mixtures of stochastic models. In: IEEE Transactions on Pattern Analysis and Machine Learning, pp. 1–15 (2003b)

  21. Lv, Q., Josephson, W., Wang, Z., Charikar, M., Li, K.: Multi-probe lsh: Efficient indexing for high-dimensional similarity search. In: Proceedings of the 33rd international conference on Very large data bases, pp. 950–961 (2007)

  22. Mirmehdi, M., Periasamy, R.: Cbir with perceptual region features. In: BMVC (2001)

  23. Nadler, M., Smith, E.P.: Pattern Recognition Engineering. Wiley, New York (1993)

    MATH  Google Scholar 

  24. Niblack, W., Barber, R., Equitz, W., Flickner, M., Glasman, E.H., Petkovic, D., Yanker, P., Faloutsos, C., and Taubin, G. (1993). The qbic project: Querying images by content, using color,texture, and shape. In: Storage and Retrieval for Image and Video Databases (SPIE), pp. 173–187

  25. Olafsson, A., Jonsson, B., Amsaleg, L.: Dynamic behavior of balanced nv-trees. In: International Workshop on Content-Based Multimedia Indexing Conference Proceedings, IEEE, pp. 174–183 (2008)

  26. Paolo Ciaccia, Marco Patella, P.Z.: M-tree: an efficient access method for similarity search in metric spaces. In: VLDB, pp. 426–435 (1997)

  27. Quack, T., Mönich, U., Thiele, L., Manjunath, B.S.: Cortina: a system for large-scale, content-based web image retrieval. In: Proceedings of the 12th annual ACM international conference on Multimedia, pp. 508–511 (2004)

  28. Sakurai, Y., Yoshikawa, M., Uemura, S., Kojima, H.: Spatial indexing of high-dimensional data based on relative approximation. VLDB J. 11(2), 93–108 (2002)

    Article  Google Scholar 

  29. Smeulders, A., Worring, M., Santini, S., Gupta, A., Jain, R.: Content-based image retrieval at the end of the early years. IEEE Trans. Pattern Anal. Mach. Intell. 22(12), 1349–1380 (2000)

    Article  Google Scholar 

  30. Wang, J., Li, J., Wiederhold, G.: Simplicity: Semantics-sensitive integrated matching for picture libraries. IEEE Trans. Pattern Anal. Mach. Intell. 23(9), 947–963 (2001)

    Article  Google Scholar 

  31. Wang, J.Z., Wiederhold, G., Firschein, O., Wei, S.X.: Content-based image indexing and searching using daubechies wavelets. Int. J. Digit. Libr. 1(4), 311–328 (1997)

    Google Scholar 

  32. Wichert, A.: Content-based image retrieval by hierarchical linear subspace method. J. Intell. Inf. Syst. 31(1), 85–107 (2008)

    Article  MathSciNet  Google Scholar 

  33. Wichert, A.: Subspace indexing for extremely high-dimensional cbir. In: International Workshop on Content-Based Multimedia Indexing Conference Proceedings, IEEE, pp. 330–338 (2008b)

  34. Wichert, A.: Subspace tree. In: International Workshop on Content-Based Multimedia Indexing Conference Proceedings, IEEE, pp. 38–44 (2009)

  35. Wichert, A., Teixeira, P., Santos, P., Galhardas, H.: Subspace tree: High dimensional multimedia indexing with logarithmic temporal complexity. J. Intell. Inf. Syst. 35(3), 495–516 (2010)

    Article  Google Scholar 

  36. Zaniolo, C., Ceri, S., Snodgrass, R.T., Zicari, R., Faloutsos, C.: Advanced Database Systems. Morgan Kaufmann, San Francisco (1997)

    Google Scholar 

Download references

Acknowledgments

This work was supported by Fundao para a Cencia e Tecnologia (FCT) (INESC-ID multiannual funding) through the PIDDAC Program funds.

Author information

Authors and Affiliations

  1. Department of Informatics, INESC-ID/IST, Technical University of Lisboa, Lisbon, Portugal

    Andreas Wichert & André Filipe da Silva Veríssimo

Authors
  1. Andreas Wichert
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. André Filipe da Silva Veríssimo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andreas Wichert.

Additional information

Communicated by Balakrishnan Prabhakaran.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wichert, A., da Silva Veríssimo, A.F. CBIR with a subspace tree: principal component analysis versus averaging. Multimedia Systems 18, 283–293 (2012). https://doi.org/10.1007/s00530-011-0248-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00530-011-0248-7

Keywords

Search

Navigation