Laplacian optimal design for image retrieval

ABSTRACT

Relevance feedback is a powerful technique to enhance Content-Based Image Retrieval (CBIR) performance. It solicits the user's relevance judgments on the retrieved images returned by the CBIR systems. The user's labeling is then used to learn a classifier to distinguish between relevant and irrelevant images. However, the top returnedimages may not be the most informative ones. The challenge is thus to determine which unlabeled images would be the most informative (i.e., improve the classifier the most) if they were labeled and used as training samples. In this paper, we propose a novel active learning algorithm, called Laplacian Optimal Design (LOD), for relevance feedback image retrieval. Our algorithm is based on aregression model which minimizes the least square error on the measured (or, labeled) images and simultaneously preserves the local geometrical structure of the image space. Specifically, we assume that if two images are sufficiently close to each other, then their measurements (or, labels) are close as well. By constructing a nearest neighbor graph, the geometrical structure of the image space can be described by the graph Laplacian. We discuss how results from the field of optimal experimental design may be used to guide our selection of a subset of images, which gives us the most amount of information. Experimental results on Corel database suggest that theproposed approach achieves higher precision in relevance feedback image retrieval.

REFERENCES

• 1: A. C. Atkinson and A. N. Donev. Optimum Experimental Designs. Oxford University Press, 2002.
• 2: Mikhail Belkin , Partha Niyogi , Vikas Sindhwani, Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples, The Journal of Machine Learning Research, 7, p.2399-2434, 12/1/2006
• 3: F. R. K. Chung. Spectral Graph Theory, volume 92 of Regional Conference Series in Mathematics. AMS, 1997.
• 4: D. A. Cohn, Z. Ghahramani, and M. I. Jordan. Active learning with statistical models. Journal of Artificial Intelligence Research, 4:129--145, 1996.
• 5: A. Dong and B. Bhanu. A new semi-supervised em algorithm for image retrieval. In IEEE Conf. on Computer Vision and Pattern Recognition, Madison, WI, 2003.
• 6: P. Flaherty, M. I. Jordan, and A. P. Arkin. Robust design of biological experiments. In Advances in Neural Information Processing Systems 18, Vancouver, Canada, 2005.
• 7: King-Shy Goh , Edward Y. Chang , Wei-Cheng Lai, Multimodal concept-dependent active learning for image retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027664]
• 8: Xiaofei He, Incremental semi-supervised subspace learning for image retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027530]
• 9: Steven C. H. Hoi , Michael R. Lyu, A Semi-Supervised Active Learning Framework for Image Retrieval, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.302-309, June 20-26, 2005 [doi>10.1109/CVPR.2005.44]
• 10: Dionysius P. Huijsmans , Nicu Sebe, How to Complete Performance Graphs in Content-Based Image Retrieval: Add Generality and Normalize Scope, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.2, p.245-251, February 2005 [doi>10.1109/TPAMI.2005.30]
• 11: Yen-Yu Lin , Tyng-Luh Liu , Hwann-Tzong Chen, Semantic manifold learning for image retrieval, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101193]
• 12: Y. Rui, T. S. Huang, M. Ortega, and S. Mehrotra. Relevance feedback: A power tool for interative content-based image retrieval. IEEE Transactions on Circuits and Systems for Video Technology, 8(5), 1998.
• 13: Arnold W. M. Smeulders , Marcel Worring , Simone Santini , Amarnath Gupta , Ramesh Jain, Content-Based Image Retrieval at the End of the Early Years, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.12, p.1349-1380, December 2000 [doi>10.1109/34.895972]
• 14: Simon Tong , Edward Chang, Support vector machine active learning for image retrieval, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500159]
• 15: H. Yu, M. Li, H.-J. Zhang, and J. Feng. Color texture moments for content-based image retrieval. In International Conference on Image Processing, pages 24--28, 2002.
• 16: Kai Yu , Jinbo Bi , Volker Tresp, Active learning via transductive experimental design, Proceedings of the 23rd international conference on Machine learning, p.1081-1088, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143980]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Experimental design

General Terms:
Algorithms, Design, Theory

Keywords:
active learning, experimental design, image retrieval, regression, relevance feedback