Skip to main content
SpringerLink
Log in

Kernel Vector Approximation Files for Relevance Feedback Retrieval in Large Image Databases

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

Abstract

Many data partitioning index methods perform poorly in high dimensional space and do not support relevance feedback retrieval. The vector approximation file (VA-File) approach overcomes some of the difficulties of high dimensional vector spaces, but cannot be applied to relevance feedback retrieval using kernel distances in the data measurement space. This paper introduces a novel KVA-File (kernel VA-File) that extends VA-File to kernel-based retrieval methods. An efficient approach to approximating vectors in an induced feature space is presented with the corresponding upper and lower distance bounds. Thus an effective indexing method is provided for kernel-based relevance feedback image retrieval methods. Experimental results using large image data sets (approximately 100,000 images with 463 dimensions of measurement) validate the efficacy of our method.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Amari and S. Wu, “Improving support vector machine classifiers by modifying kernel functions,” Neural Networks, Vol. 12, No. 6, pp. 783–789, 1999.

    Article  PubMed  Google Scholar 

  2. F.R. Bach and M.I. Jordan, “Kernel independent component analysis,” Journal of Machine Learning Research, Vol. 3, pp. 1–48, 2002.

    Article  Google Scholar 

  3. Y. Chen, X. Zhou, and T. Huang, “One-class SVM for learning in image retrieval,” in Proceedings of IEEE ICIP, Thessaloniki, Greece, 2001, pp. 815–818.

  4. P. Ciaccia, M. Patella, and P. Zezula, “M-tree: An efficient access method for similarity search in metric spaces,” in Proceedings of the International Conference on Very Large Databases, 1997, pp. 426– 435.

  5. N. Cristianini and J. Shawe-Taylor, An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods, Cambridge, UK: Cambridge University Press 2000.

    Google Scholar 

  6. N. Cristianini, J. Shawe-Taylor, and H. Lodhi, “Latent semantic kernels,” in Proceedings of ICML-01, 18th International Conference on Machine Learning, C. Brodley and A. Danyluk (Eds.), Williams College, US, 2001, pp. 66–73.

  7. H. Ferhatosmanoglu, E. Tuncel, D. Agrawal, and A. Abbadi, “Vector approximation based indexing for non-uniform high dimensional data sets,” in Proc. of ACM International Conf. on Information and Knowledge Management, 2000, pp. 202–209.

  8. A. Guttman, “R-tree: A dynamic index structure for spatial searching,” in Proceedings of ACM SIGMOD International Conference on Management of Data, 1984, pp. 47–47,

  9. D. Heisterkamp, J. Peng, and H. Dai, “An Adaptive Quasiconformal Kernel Metric for Image Retrieval,” in Proceedings of IEEE CVPR, Kauai Marriott, Hawaii, 2001, pp. 236–243.

  10. Y. Ishikawa, R. Subramanya, and C. Faloutsos, “Mind reader: Querying databases through multiple examples,” in Proceedings of 24th International Conference on Very Large Data Bases, 1998, pp. 218–227.

  11. L.M. Manevitz and M. Yousef, “One-class SVMs for document classification,” Journal of Machine Learning Research, Vol. 2, pp. 139–154, 2001.

    Article  Google Scholar 

  12. K. Muller, S. Mika, G. Ratsch, K. Tsuda, and B. Scholkopf, “An introduction to kernel-based learning algorithms,” IEEE Transactions on Neural Networks Vol. 12 No. 2, pp. 181–201, 2001.

    Article  Google Scholar 

  13. P. Murphy and D. Aha, “UCI repository of machine learning databases,” www.cs.uci.edu/mlearn/MLRepository.html.

  14. J. Peng, B. Banerjee, and D.R. Heisterkamp, “Kernel index for relevance feedback retrieval in large image databases,” in 9th International Conference on Neural Information Processing, 2002a.

  15. J. Peng, B. Bhanu, and S. Qing, “Probabilistic feature relevance learning for content-based image retrieval,” Computer Vision and Image Understanding, Vol. 75, Nos. 1/2, pp. 150–164, 1999.

    Article  Google Scholar 

  16. J. Peng, D.R. Heisterkamp, and H.K. Dai, “Adaptive kernel metric nearest neighbor classification,” in Proceedings of IEEE International Conference on Pattern Recognition, Quebec City, Canada, 2002b.

  17. Y. Rui and T. Huang, “Optimizing learning in image retrieval,” in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Hilton Head Island, South Carolina, 2000, pp. 236–243.

  18. B. Scholkopf, et al., “Input space versus feature space in kernel-based methods,” IEEE Transactions on Neural Networks, Vol. 10, No. 5, pp. 1000–1017, 1999.

    Article  Google Scholar 

  19. B. Scholkopf, A. Smola, and K.-R. Muller, “Nonlinear component analysis as a kernel eigenvalue problem,” Neural Computation, Vol. 10, pp. 1299–1319, 1998.

    Article  Google Scholar 

  20. B. Scholkopf and A.J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, Cambridge, MA: MIT Press, 2002.

    Google Scholar 

  21. D. Tax and R. Duin, “Data domain description by support vectors,” in Proceedings of ESANN, 1999, pp. 251–256.

  22. Tešić, J. and B. Manjunath, “Nearest neighbor search for relevance feedback,” in Proceedings of IEEE Computer Society on Computer Vision and Pattern Recognition, Vol. II, 2003, pp. 643–648.

    Google Scholar 

  23. M.E. Tipping, “Sparse Kernel Principal Component Analysis,” in Advances in Neural Information Processing Systems, 2000, pp. 633–639.

  24. V.N. Vapnik, Statistical Learning Theory, Adaptive and Learning Systems for Signal Processing, Communications, and Control, New York: Wiley, 1998.

    Google Scholar 

  25. R. Webber, J. Schek, and S. Blott, “A quantitative analysis and performance study for similarity-search methods in high-dimensional space,” in Proceedings of the International Conference on Very Large Databases, 1998, pp. 194–205.

  26. R. Weber and S. Blott, “An approximation-based data structure for similarity search,” Technical Report 24, ESPRIT project HERMES (no. 9141), 1997. Available at http://www-dbs.ethz.ch/weber/paper/HTR24.ps.

  27. P. Wu and B. Manjunath, “Adaptive nearest neighbor search for relevance feedback in large image databases,” in Proceedings of the ACM Multimedia, 2000, pp. 202–209.

  28. P. Yianilos, “Data structures and algorithms for nearest neighbor search in general metric spaces,” in the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1992, pp. 311–321.

  29. X. Zhou and T. Huang, “Small sample learning during multimedia retrieval using BiasMap,” in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Kauai Marriott, Hawaii, 2001, Vol. 1, pp. 11–17.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Oklahoma State University, Stillwater, OK, 74078, USA

    Douglas R. Heisterkamp

  2. Electrical Engr. and Computer Science, Tulane University, New Orleans, LA, 70118, USA

    Jing Peng

Authors
  1. Douglas R. Heisterkamp
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jing Peng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Douglas R. Heisterkamp.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Heisterkamp, D.R., Peng, J. Kernel Vector Approximation Files for Relevance Feedback Retrieval in Large Image Databases. Multimed Tools Appl 26, 175–189 (2005). https://doi.org/10.1007/s11042-005-0454-4

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-005-0454-4

Keywords

Search

Navigation