A nearest-neighbor approach to relevance feedback in content based image retrieval

ABSTRACT

High retrieval precision in content-based image retrieval can be attained by adopting relevance feedback mechanisms. The main difficulties in exploiting relevance information are i) the gap between user perception of similarity and the similarity computed in the feature space used for the representation of image content, and ii) the availability of few training data (users typically label a few dozen of images). At present, SVM are extensively used to learn from relevance feedback due to their capability of effectively tackling the above difficulties. However, the performances of SVM depend on the tuning of a number of parameters. In this paper a different approach based on the nearest neighbor paradigm is proposed. Each image is ranked according to a relevance score depending on nearest-neighbor distances. This approach is proposed both in low-level feature spaces, and in "dissimilarity spaces", where image are represented in terms of their dissimilarities from the set of relevant images. Reported results show that the proposed approach allows recalling a higher percentage of images with respect to SVM-based techniques.

REFERENCES

• 1: David W. Aha , Dennis Kibler , Marc K. Albert, Instance-Based Learning Algorithms, Machine Learning, v.6 n.1, p.37-66, Jan. 1991 [doi>10.1023/A:1022689900470]
• 2: Althoff, K-D. Case-Based Reasoning. In Chang S. K. (ed.) Handbook on Software Engineering and Knowledge Engineering, World Scientific, 2001, 549--588
• 3: Bir Bhanu , Anlei Dong, Concepts Learning with Fuzzy Clustering and Relevance Feedback, Proceedings of the Second International Workshop on Machine Learning and Data Mining in Pattern Recognition, p.102-116, July 25-27, 2001
• 4: Markus M. Breunig , Hans-Peter Kriegel , Raymond T. Ng , Jörg Sander, LOF: identifying density-based local outliers, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.93-104, May 15-18, 2000, Dallas, Texas, United States
• 5: Bruno, E., Loccoz, N., Maillet, S. Learning user queries in multimodal dissimilarity spaces. Proc. of the 3rd Int'l Workshop on Adaptive Multimedia Retrieval, 2005.
• 6: Cox, I. J., Miller, M. L., Minka, T. P., Papathomas TV, Yianilos, P. N. The Bayesian image retrieval system, PicHunter: theory, implementation, and psychophysical experiments. IEEE Trans. on Image Processing 9, 2000, 20--37
• 7: Dasarathy, D. V. (Ed.) Nearest Neighbor Norms: NN Pattern Classification Techniques. IEEE Press, 2001.
• 8: Alberto Del Bimbo, Visual information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 9: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 10: Robert P. W. Duin , Dick de Ridder , David M. J. Tax, Experiments with a featureless approach to pattern recognition, Pattern Recognition Letters, v.18 n.11-13, p.1159-1166, Nov., 1997 [doi>10.1016/S0167-8655(97)00138-4]
• 11: Frederix, G., Caenen, G., Pauwels, E. J. PARISS: Panoramic, Adaptive and Reconfigurable Interface for Similairty Search. Proc. of ICIP 2000 Intern. Conf. on Image Processing. WA 07.04, vol. III, 2000, 222--225
• 12: Giacinto, G., Roli F. Dissimilarity Representation of Images for Relevance Feedback in Content-Based Image Retrieval. In: Perner P. (Ed.) Machine Learning and Data Mining in Pattern Recognition. LNAI 2734, Springer-Verlag, Berlin, 2003, 202--214
• 13: Giacinto, G, Roli, F. Bayesian Relevance Feedback for Content-Based Image Retrieval. Pattern Recognition 37, 2004, 1499--1508
• 14: Giacinto, G., Roli, F. Instance-Based Relevance Feedback for Image Retrieval. In Saul L. K., Weiss Y., and Bottou L.: Advances in Neural Information Processing Systems 17, MIT Press, 2005, 489--496
• 15: Hastie, T., Tibshirani, R., Friedman, J. The elements of statistical learning. Springer, 2001
• 16: Yoshiharu Ishikawa , Ravishankar Subramanya , Christos Faloutsos, MindReader: Querying Databases Through Multiple Examples, Proceedings of the 24rd International Conference on Very Large Data Bases, p.218-227, August 24-27, 1998
• 17: Michael S. Lew , Nicu Sebe , Chabane Djeraba , Ramesh Jain, Content-based multimedia information retrieval: State of the art and challenges, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP), v.2 n.1, p.1-19, February 2006 [doi>10.1145/1126004.1126005]
• 18: Michael Lindenbaum , Shaul Markovitch , Dmitry Rusakov, Selective Sampling for Nearest Neighbor Classifiers, Machine Learning, v.54 n.2, p.125-152, February 2004 [doi>10.1023/B:MACH.0000011805.60520.fe]
• 19: David McG. Squire , Wolfgang Müller , Henning Müller , Thierry Pun, Content-based query of image databases: inspirations from text retrieval, Pattern Recognition Letters, v.21 n.13-14, p.1193-1198, Dec. 2000 [doi>10.1016/S0167-8655(00)00081-7]
• 20: Giang P. Nguyen , Marcel Worring , Arnold W. M. Smeulders, Similarity learning via dissimilarity space in CBIR, Proceedings of the 8th ACM international workshop on Multimedia information retrieval, October 26-27, 2006, Santa Barbara, California, USA [doi>10.1145/1178677.1178695]
• 21: Michael Ortega , Yong Rui , Kaushik Chakrabarti , Kriengkrai Porkaew , Sharad Mehrotra , Thomas S. Huang, Supporting Ranked Boolean Similarity Queries in MARS, IEEE Transactions on Knowledge and Data Engineering, v.10 n.6, p.905-925, November 1998 [doi>10.1109/69.738357]
• 22: Elzbieta Pekalska , Robert P. W. Duin, Dissimilarity representations allow for building good classifiers, Pattern Recognition Letters, v.23 n.8, p.943-956, June 2002 [doi>10.1016/S0167-8655(02)00024-7]
• 23: Elzbieta Pekalska , Robert P. W. Duin, The Dissimilarity Representation for Pattern Recognition: Foundations And Applications (Machine Perception and Artificial Intelligence), World Scientific Publishing Co., Inc., River Edge, NJ, 2005
• 24: Jing Peng , Bir Bhanu , Shan Qing, Probabilistic feature relevance learining for content-based image retrieval, Computer Vision and Image Understanding, v.75 n.1-2, p.150-164, July/Aug. 1999 [doi>10.1006/cviu.1999.0770]
• 25: Rui, Y., Huang, T. S., Mehrotra, S. Content-based image retrieval with relevance feedback in MARS. In Proceedings of the IEEE International Conference on Image Processing, IEEE Press, 1997, 815--818
• 26: Yong Rui , Thomas S. Huang, Relevance feedback techniques in image retrieval, Principles of visual information retrieval, Springer-Verlag, London, 2000
• 27: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 28: Simone Santini , Ramesh Jain, Similarity Measures, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.9, p.871-883, September 1999 [doi>10.1109/34.790428]
• 29: Simone Santini , Ramesh Jain, Integrated Browsing and Querying for Image Databases, IEEE MultiMedia, v.7 n.3, p.26-39, July 2000 [doi>10.1109/93.879766]
• 30: Stan Sclaroff , Marco La Cascia , Saratendu Sethi , Leonid Taycher, Mix and match features in the ImageRover search engine, Principles of visual information retrieval, Springer-Verlag, London, 2000
• 31: 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]
• 32: Tao, D., Tang, X., Li, X., Rui, Y. Direct Kernel Biased Discriminant Analysis: A New Content-based Image Retrieval Relevance Feedback Algorithm. IEEE Trans. on Multimedia 8, 2006, 716--727
• 33: Dacheng Tao , Xiaoou Tang , Xuelong Li , Xindong Wu, Asymmetric Bagging and Random Subspace for Support Vector Machines-Based Relevance Feedback in Image Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.7, p.1088-1099, July 2006 [doi>10.1109/TPAMI.2006.134]
• 34: Tax, D. One-class classification. PhD thesis, Delft University of Technology, The Netherlands, 2001
• 35: Tieu, K., Viola, P. Boosting Image Retrieval. Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, vol. 1, 2001, 228--235
• 36: 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]
• 37: Zhang L. Lin, F., Zhang. B. Support Vector Machine Learning for Image Retrieval. Proc. IEEE Int'l Conf. Image Processing, 2001, 721--724
• 38: Zhou, X. Huang, TS. Small Sample Learning During Multimedia Retrieval Using Biasmap. Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, vol. 1, 2001, 11--17
• 39: Zhou, X., Huang, TS. Relevance Feedback for Image Retrieval: A Comprehensive Review," ACM Multimedia Systems 8, 2003, 536--544

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Experimentation, Theory

Keywords:
dissimilarity representation, image retrieval, nearest-neighbor, relevance feedback