Dual diffusion model of spreading activation for content-based image retrieval

ABSTRACT

This paper introduces a content-based information retrieval method inspired by the ideas of spreading activation models. In response to a given query,the proposed approach computes document ranks as their final activation values obtained upon completion of a diffusion process. This diffusion process,in turn,is dual in the sense that it models the spreading of the query 's initial activation simultaneously in two similarity domains: low-level feature-based and high-level semantic.The formulation of the diffusion process relies on an approximation that makes it possible to compute the final activation as a solution to a linear system of differential equations via a matrix exponential without the need to resort to an iterative simulation.The latter calculation is performed efficiently by adapting a sparse routine based on Krylov sub-space projection method.The empirical performance of the described dual diffusion model has been evaluated in terms of precision and recall on the task of content-based digital image retrieval in query-by-example scenario. The obtained experimental results demonstrate that the proposed method achieves better overall performance compared to traditional feature-based approaches. This performance improvement is attained not only when both similarity domains are used, but also when a diffusion model operates only on the feature-based similarities.

References

1. D. Aswath, S. T. Ahmed, J. D'cunha, and H. Davulcu. Boosting item keyword search with spreading activation. In Web Intelligence pages 704--707, 2005.
2. R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval Addison Wesley, 1999.
3. J.-Y. Bouguet, C. Dulong, I. Kozintsev, and Y. Wu. Requirements for benchmarking personal image retrieval systems. In S. Santini, R. Schettini, and T.Gevers, editors, Proceedings of SPIE Photonics West, Electronic Imaging volume 6061. SPIE, 2006.
4. C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines 2001. Software available at http://www.csie.ntu.edu.tw/¿cjlin/libsvm.
5. F. Crestani. Application of spreading activation techniques in information retrieval. Artificial Intelligence Review 11(6): 453--582, 1997.
6. F. Crestani and P. L. Lee. Searching the web by constrained spreading activation. Information Processing and Management 36(4):585--605, 2000.
7. N. Cristianini, J. Shawe-Taylor, and H. Lodhi. Latent semantic kernels. Journal of Intelligent Information Systems 18(2-3):127--152, 2002.
8. S. Deerwester, S. Dumais, G. Furnas, T. Landauer, and R. Harshman. Indexing by latent semantic analisys.Journal of the American Society of Information Science 41(6):391--407, 1990.
9. K.-S. Goh, B. Li, and E. Y. Chang. Using one-class and two-class SVMs for multiclass image annotation. IEEE Transactions on Knowledge and Data Engineering 17(10): 1333--1346, 2005.
10. B. Haasdonk and C. Bahlmann. Learning with distance substitution kernels. In 26th Pattern Recognition Symposium of the German Association for Pattern Recognition (DAGM 2004)Tübingen, Germany, 2004. Springer Verlag.
11. M. Hochbruck and C. Lubich. On Krylov subspace to the matrix exponential operator. SIAM Journal on Numerical Analysis 34(5): 1911--1925, 1997.
12. J. Huang, S. R. Kumar, M. Mitra, W.-J. Zhu, and R. Zabih. Image indexing using color correlograms.In CVPR '97: Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97) page 762, Washington, DC, USA, 1997. IEEE Computer Society.
13. J. Kandola, J. Shawe-Taylor, and N. Cristianini. Learning semantic similarity. In S. T. S. Becker and K. Obermayer, editors, Advances in Neural Information Processing Systems 15 pages 657--664. MIT Press, Cambridge, MA, 2003.
14. R. I. Kondor and J. D. Lafferty. Diffusion kernels on graphs and other discrete input spaces.In ICML '02: Proceedings of the Nineteenth International Conference on Machine Learning pages 315--322, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc.
15. M. Magennis and C. J. van Rijsbergen. The potential and actual effectiveness of interactive query expansion. In SIGIR '97: Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval pages 324--332, New York, NY, USA, 1997. ACM Press.
16. G. A. Miller. Wordnet: a lexical database for English. Commun. ACM 38(11):39--41, 1995.
17. B. R. Munson, D. F. Young,and T. H. Okiishi. Fundamentals of Fluid Mechanics John Wiley & Sons,1990.
18. S. E. Preece. A Spreading Activation Network Model for Information Retrieval PhD thesis, University of Illinois at Urbana-Champaign, 1981.
19. P. Resnik. Using information content to evaluate semantic similarity in a taxonomy. In International Joint Conference for Artificial Intelligence (IJCAI-95) pages 448--453, 1995.
20. D. E. Rumelhart and D. A. Norman. Representation in memory. In Steven's handbook of experimental psychology volume 2, pages 511--587. Wiley, 1988.
21. G. Salton. Automatic Information Organization and Retrieval. McGraw Hill Text, 1968.
22. G. Salton and C. Buckley. On the use of spreading activation methods in automatic information. In SIGIR '88: Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval pages 147--160, New York, NY, USA, 1988. ACM Press.
23. B. Schölkopf, J. C. Platt, J. C. Shawe-Taylor, A. J. Smola, and R. C. Williamson. Estimating the support of a high-dimensional distribution. Neural Comput. 13(7): 1443--1471, 2001.
24. R. B. Sidje. Expokit: a software package for computing matrix exponentials. ACM Transactions on Mathematical Software 24(1): 130--156, 1998.
25. G. Siolas and F. d'Alché-Buc. Support vector machines based on a semantic kernel for text categorization. IJCNN 05:5205, 2000.
26. D. M. J. Tax. Ddtools, the data description toolbox for matlab, June 2006. version 1.5.3.
27. D. M. J. Tax and R. P. W. Duin. Support vector data description. Mach. Learn. 54(1):45--66, 2004.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision problems

        • Object recognition

• Information systems

  • Information retrieval

    • Retrieval models and ranking

• Mathematics of computing

  • Mathematical analysis

    • Differential equations

      • Ordinary differential equations