Apprentissage de distance pour l'annotation d'images par plus proches voisins

Matthieu Guillaumin, Jakob Verbeek, Cordelia Schmid, Thomas MensinkHAL 2010

TL;DR

This paper introduces TagProp, a novel weighted nearest neighbor model for image annotation that learns an optimal distance metric. By learning this metric, TagProp significantly improves state-of-the-art performance in image annotation and retrieval tasks, especially for rare words.

What Problem Does This Paper Address?

The automatic annotation of images is a crucial but challenging problem in computer vision. As the volume of visual data explodes, efficiently and accurately assigning descriptive keywords to images becomes essential for organization, search, and understanding. Existing methods often struggle with the nuances of image content and the long-tail distribution of keywords (many rare words). While nearest neighbor approaches have shown promise, they typically rely on fixed or ad-hoc distance metrics, failing to optimize this crucial component for the specific task of annotation. This paper aims to bridge this gap by proposing a method that learns the optimal distance metric for image annotation.

Methods

The core of the proposed method, TagProp, is a weighted nearest neighbor model trained discriminatively. Instead of using a fixed distance, TagProp learns a distance metric that maximizes the likelihood of tag predictions on the training set. This learning is achieved by optimizing the weights assigned to neighbors, which can be based on either their rank or their distance to the query image.

Key methodological contributions include:

  • Weighted Nearest Neighbors: Neighbors are not treated equally; their influence is weighted.
  • Metric Learning: The distance metric used to define neighbors is learned, allowing for optimal combination of various visual similarities (e.g., color histograms, shape descriptors).
  • Discriminative Training: The model is trained to directly optimize prediction performance, rather than relying on generative assumptions.
  • Logistic Discrimination per Word: A novel approach to modulate the predicted probabilities for each word, specifically boosting the recall of rare words. This is achieved by adding two parameters per word to the nearest neighbor predictions.

Datasets

The authors evaluated their models on three publicly available image datasets:

  • Corel 5k: A standard benchmark for image annotation and retrieval, containing 5000 images with 1-5 manual annotations per image and a vocabulary of 260 words.
  • ESP Game: A large dataset obtained from an online game, known for its diversity and challenging nature, containing approximately 20,000 images.
  • IAPR TC12: A dataset of around 20,000 images with multilingual descriptions, adapted for image annotation tasks.

Key Insights and Ideas

  • The Importance of Learned Metrics: The paper strongly suggests that learning the distance metric is crucial for achieving state-of-the-art performance in image annotation, outperforming fixed or ad-hoc combinations of distances.
  • Addressing the Long-Tail Problem: The per-word logistic discrimination is a clever way to specifically improve the recall of rare words, which are often a bottleneck in annotation systems.
  • Direct Optimization is Key: Unlike previous attempts at metric learning for this task, TagProp integrates metric learning directly into the prediction model, leading to better results.
  • Nearest Neighbors Remain Powerful: Despite the rise of deep learning, well-tuned nearest neighbor methods, especially with learned metrics, can still achieve competitive and even superior results on specific tasks.

Key Results

TagProp, particularly the $\sigma$ML variant (which combines learned distance and per-word logistic discrimination), significantly outperforms existing state-of-the-art methods across all three datasets and multiple evaluation metrics.

  • Corel 5k: Achieved a gain of 5% in precision, 9% in recall, and identified 20 more words with positive recall compared to previous work.
  • ESP Game and IAPR TC12: Showed improvements of 18% (resp. 17%) in precision and 6% (resp. 2%) in recall.
  • Complex Queries: For complex image retrieval queries, TagProp achieved approximately 10% better mAP and BEP scores.
  • Rare Word Improvement: The $\sigma$ML variant showed substantial gains in recall for rare words, as visualized in Figure 2.

Limitations and Future Work

  • Computational Complexity: While the authors mention strategies to manage complexity, learning the metric and optimizing weights can still be computationally intensive, especially for very large datasets.
  • Future Work: The authors suggest extending the model to image region annotation, enabling object detection and recognition. They also propose exploring the model for more complex tasks beyond simple keyword annotation.

Summary updated

Abstract

National audience
BibTeX
@inproceedings{guillaumin2010apprentissage,
  author = {Matthieu Guillaumin and Jakob Verbeek and Cordelia Schmid and Thomas Mensink},
  title = {{Apprentissage de distance pour l'annotation d'images par plus proches voisins}},
  booktitle = {HAL},
  year = {2010},
}
Figure