Multiple random walk and its application in content-based image retrieval

ABSTRACT

In this paper, we propose a transductive learning method for content-based image retrieval: Multiple Random Walk (MRW). Its basic idea is to construct two generative models by means of Markov random walks, one for images relevant to the query concept and the other for the irrelevant ones. The goal is to obtain the likelihood functions of both classes. Firstly, MRW generates two random walks with virtual absorbing boundaries, and uses the absorbing probabilities as the initial estimation of the likelihood functions. Then it refines the two random walks through an EM-like iterative procedure in order to get more accurate estimation of the likelihood functions. Class priors are also obtained in this procedure. Finally, MRW ranks all the unlabeled images in the database according to their posterior probabilities of being relevant. By using both labeled and unlabeled data, MRW can be seen as a transductive learning method, which has been demonstrated to outperform inductive ones by previous research work. Systematic experiments on a general-purpose image database consisting of 5,000 Corel images demonstrate the superiority of MRW over state-of-the-art techniques.

REFERENCES

• 1: Bilmes, J.A. A Gentle Tutorial of the EM Algorithm and Its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models. Technical Report UMIACS-TR-97-021, International Computer Science Institute and U.C. Berkeley, 1998.
• 2: Jingrui He , Mingjing Li , Hong-Jiang Zhang , Hanghang Tong , Changshui Zhang, Manifold-ranking based image retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027531]
• 3: Jingrui He , Hanghang Tong , Mingjing Li , Hong-Jiang Zhang , Changshui Zhang, Mean version space: a new active learning method for content-based image retrieval, Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval, October 15-16, 2004, New York, NY, USA [doi>10.1145/1026711.1026715]
• 4: Jing Huang , S. Ravi Kumar , Mandar Mitra , Wei-Jing Zhu , Ramin Zabih, Image Indexing Using Color Correlograms, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.762, June 17-19, 1997
• 5: Feng Jing , Mingjing Li , Hong-Jiang Zhang , Bo Zhang, An effective region-based image retrieval framework, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France [doi>10.1145/641007.641106]
• 6: Kokare, M., Chatterji, B.N., and Biswas, P.K. Comparison of similarity metrics for texture image retrieval. IEEE Conf. on Convergent Technologies for Asia-Pacific Region, vol. 2, pp. 571-575, 2003.
• 7: Li, B., Chang, E., and Wu, C.T. DPF-a perceptual distance function for image retrieval. Proc. IEEE Int. Conf. on Image Processing, vol. 2, pp. 597-600, 2002.
• 8: Fang Liu , Rosalind W. Picard, Periodicity, Directionality, and Randomness: Wold Features for Image Modeling and Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.7, p.722-733, July 1996 [doi>10.1109/34.506794]
• 9: Lovasz, L. Random walks on graphs: a survey. Combinatorics Paul Erdos is Eighty, vol. 2, pp. 1--46, 1993.
• 10: S. G. Mallat, A Theory for Multiresolution Signal Decomposition: The Wavelet Representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.7, p.674-693, July 1989 [doi>10.1109/34.192463]
• 11: B. S. Manjunath , W. Y. Ma, Texture Features for Browsing and Retrieval of Image Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.8, p.837-842, August 1996 [doi>10.1109/34.531803]
• 12: Greg Pass , Ramin Zabih , Justin Miller, Comparing images using color coherence vectors, Proceedings of the fourth ACM international conference on Multimedia, p.65-73, November 18-22, 1996, Boston, Massachusetts, United States [doi>10.1145/244130.244148]
• 13: Rocchio, J.J. Relevance feedback in information retrieval. The SMART Retrieval System, pp. 313--323, Prentice-Hall, Englewood Cliffs, NJ, 1971.
• 14: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, A Metric for Distributions with Applications to Image Databases, Proceedings of the Sixth International Conference on Computer Vision, p.59, January 04-07, 1998
• 15: Rui, Y., Huang, T.S., Ortega, M., and Mehrotra, S. Relevance feedback: a power tool for interactive content-based image retrieval. IEEE Trans. Circuits and Systems for Video Technology, vol. 8, pp. 644--655, 1998.
• 16: Schmid, C. A structured probabilistic model for recognition. Proc. IEEE Conf. on Computer Vision and Pattern Recognition, vol. 2, pp. 485--490, 1999.
• 17: Cordelia Schmid , Roger Mohr, Local Grayvalue Invariants for Image Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.5, p.530-535, May 1997 [doi>10.1109/34.589215]
• 18: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 19: Stricker, M., and Orengo, M. Similarity of color images. Storage and Retrieval for Image and Video Databases, Proc. SPIE 2420, pp 381--392, 1995.
• 20: Michael J. Swain , Dana H. Ballard, Color indexing, International Journal of Computer Vision, v.7 n.1, p.11-32, Nov. 1991 [doi>10.1007/BF00130487]
• 21: Szummer, M., and Jaakkola, T. Partially labeled classification with Markov random walks. Neural Information Processing Systems, 2002.
• 22: Tieu, K., and Viola, P. Boosting image retrieval. Proc. IEEE Conf. on Computer Vision and Pattern Recognition, vol. 1, pp. 228--235, 2000.
• 23: Wang, J.Z., Wiederhold, G., Firschein, O., and Sha, X.W. Content-based image indexing and searching using Daubechies' wavelets. Int. Journal of Digital Libraries, vol. 1, no. 4, pp. 311--328, 1998.
• 24: Wu, Y., Tian, Q., and Huang, T. Discriminant-EM algorithm with application to image retrieval. Proc. IEEE Conf. on Computer Vision and Pattern Recognition, vol. 1, pp. 155--162, 2000.
• 25: Zhang, L., Lin, F., and Zhang, B. Support vector machine learning for image retrieval. Proc. IEEE Int. Conf. on Image Processing, vol. 2, pp. 721--724, 2001.
• 26: Zhou, D., Bousquet, O., Lal, T.N., Weston, J., and Scholkopf, B. Learning with local and global consistency. Neural Information Processing Systems, 2003.
• 27: Zhou, D., Weston, J., Gretton, A., Bousquet, O., and Scholkopf, B. Ranking on data manifolds. Neural Information Processing Systems, 2003.
• 28: Zhou, X.S., Rui, Y., and Huang, T. Water-Filling: a novel way for image structural feature extraction. Proc. IEEE Int. Conf. on Image Processing, vol. 2, pp. 570--574, 1999.
• 29: Zhu, X., Ghahramani, Z., and Lafferty, J. Semi-supervised learning using Gaussian Fields and harmonic functions. Proc 12th Int. Conf. on Machine Learning, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Image databases

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Relevance feedback; Search process

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Markov random walk, class prior, generative model, image retrieval, likelihood function, relevance feedback