Efficient benchmarking of content-based image retrieval via resampling

ABSTRACT

While content-based image retrieval (CBIR) is an expanding field, and new approaches to ever more effective retrieval are frequently proposed, relatively little attention has so far been paid to the process of evaluating the effectiveness of CBIR methods. Most of the reported evaluations use standard IR evaluation methodologies, with little consideration of their statistical significance or appropriateness for CBIR, which makes it difficult to assess the precise impact of individual methods. In this paper, we present a new approach for evaluating CBIR systems which provides both efficient and statistically-sound performance evaluation. The approach is based on stratified sampling, and provides a significant improvement over existing evaluation approaches. Comprehensive experiments using our approach to evaluate a range of CBIR methods have shown that the approach reduces not only the estimation error, but also reduces the size of the test data set required to achieve specific estimation error levels.

REFERENCES

• 1: Gift: the gnu image-finding tool, http://www.gnu.org/software/gift, 2004.
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: T. benchathlon network. http://www.benchathlon.net.
• 4: W. Cochran. Sampling Techniques. John Wiley & Sons, 1977.
• 5: Alexander Dimai, Assessment of Effectiveness of Content Based Image Retrieval Systems, Proceedings of the Third International Conference on Visual Information and Information Systems, p.525-532, June 02-04, 1999
• 6: B. Efron. The jackknife, the bootstrap, and other resampling plans. Society of Industrial and Applied Mathematics CBMS-NSF Monographs, 38, 1982.
• 7: B. Efron and G. Gong. A leisurely look at the bootstrap, the jackknife, and cross-validation. The American Statistician, 31:3648, 1983.
• 8: B. Efron and R. Tibshirani. An Introduction to the Bootstrap. New York: Chapman & Hall, 1993.
• 9: N. Gunther and G. Beretta. A benchmark for image retrieval using distributed systems over the internet: Birds-i. Technical report, HP Labs, Palo Alto, Technical Report HPL-2000-162, 2001.
• 10: M. Gurney and R. S. Jewett. Construction orthogonal replications for variance estimation. Journal of the American Statistical Association, 70(532):819--821, 1975.
• 11: A. S. Hedayat, N. J. A. Sloane, and J. Stufken. Orthogonal Arrays: Theory and Applications. Springer-Verlag, 1999.
• 12: Jing Huang , S. Ravi Kumar , Mandar Mitra, Combining supervised learning with color correlograms for content-based image retrieval, Proceedings of the fifth ACM international conference on Multimedia, p.325-334, November 09-13, 1997, Seattle, Washington, United States [doi>10.1145/266180.266383]
• 13: The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces, Proceedings of the 15th International Conference on Data Engineering, p.440, March 23-26, 1999
• 14: 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]
• 15: Clement H. C. Leung , Horace Ho-Shing Ip, Benchmarking for Content-Based Visual Information Search, Proceedings of the 4th International Conference on Advances in Visual Information Systems, p.442-456, November 02-04, 2000
• 16: M. Markus and R. Visser. Applying the bootstrap to generate confidence regions in multiple correspondence analysis. In Proceeding of Bootstrapping and Relating Techniques Conf., 1990.
• 17: Henning Müller , Paul Clough , William Hersh , Thomas Deselaers , Thomas Lehmann , Antoine Geissbuhler, Evaluation axes for medical image retrieval systems: the imageCLEF experience, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101358]
• 18: H. Muller, W. Muller, S. Marchand-Maillet, D. Squire, and T. Pun. Automated benchmarking in contentbased image retrieval. In Proceedings of the Second International Conference on Multimedia and Exposition(ICME'01), 2001.
• 19: Henning Müller , Wolfgang Müller , David McG. Squire , Stéphane Marchand-Maillet , Thierry Pun, Performance evaluation in content-based image retrieval: overview and proposals, Pattern Recognition Letters, v.22 n.5, p.593-601, April 2001 [doi>10.1016/S0167-8655(00)00118-5]
• 20: A. Desai Narasimhalu , Mohan S. Kankanhalli , Jiankang Wu, Benchmarking Multimedia Databases, Multimedia Tools and Applications, v.4 n.3, p.333-356, May 1997 [doi>10.1023/A:1009641123797]
• 21: Apostol Natsev , Rajeev Rastogi , Kyuseok Shim, WALRUS: A Similarity Retrieval Algorithm for Image Databases, IEEE Transactions on Knowledge and Data Engineering, v.16 n.3, p.301-316, March 2004 [doi>10.1109/TKDE.2003.1262183]
• 22: Anne H. H. Ngu , Quan Z. Sheng , Du Q. Huynh , Ron Lei, Combining multi-visual features for efficient indexing in a large image database, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.4, p.279-293, April 2001
• 23: T. Pfund and S. Marchand-Maillet. Dynamic multimedia annotation tool. Internet Imaging III, 4672:206 224, 2002.
• 24: C. Sarndal, B. Swensson, and J. Wretman. Model Assisted Survey Sampling. Springer-Verlag, 1992.
• 25: Jialie Shen , Anne H. H. Ngu , John Shepherd , Du Q. Huynh , Quan Z. Sheng, CMVF: a novel dimension reduction scheme for efficient indexing in a large image database, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872842]
• 26: Nikhil V. Shirahatti , Kobus Barnard, Evaluating Image Retrieval, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.955-961, June 20-26, 2005 [doi>10.1109/CVPR.2005.147]
• 27: Christos Theoharatos , Nikolaos A. Laskaris , George Economou , Spiros Fotopoulos, A Generic Scheme for Color Image Retrieval Based on the Multivariate Wald-Wolfowitz Test, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.808-819, June 2005 [doi>10.1109/TKDE.2005.85]
• 28: James Z. Wang , Jia Li , Gio Wiederhold, SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture LIbraries, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.9, p.947-963, September 2001 [doi>10.1109/34.955109]
• 29: K. M. Wolter. Introduction to Variance Estimation. Springer series in statistics. Springer-Verlag, 1985.
• 30: W. Y. Ma , B. S. Manjunath, NeTra: a toolbox for navigating large image databases, Proceedings of the 1997 International Conference on Image Processing (ICIP '97) 3-Volume Set-Volume 1, p.568, October 26-29, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  J. Computer Applications
  J.5 ARTS AND HUMANITIES

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
evaluation, image retrieval, sampling