Image annotation by large-scale content-based image retrieval

Xirong Li, Le Chen, Lei Zhang, Fuzong Lin, Wei-Ying MaACM Multimedia 2006 · DOI

TL;DR

This paper introduces a novel image annotation system that leverages large-scale web image databases for content-based image retrieval and keyword mining. By avoiding explicit training stages and instead relying on efficient search and clustering, the system can handle a potentially unlimited vocabulary and achieve impressive results on open datasets.

What Problem Does This Paper Address?

Automatic image annotation, the task of assigning descriptive keywords to images, has been a long-standing challenge. Traditional approaches often rely on supervised learning with limited training data, which restricts the vocabulary of possible annotations and struggles with the vast and ever-growing nature of web-scale image collections. This paper aims to bridge this gap by developing a system that can effectively annotate images using readily available, large-scale, and richly annotated web data, without requiring a predefined, limited vocabulary.

Methods

The proposed system operates in two main stages:

  1. Content-Based Image Retrieval (CBIR): Given an uncaptioned image, the system first performs a CBIR search against a massive image database. This search is facilitated by a novel Multi-Index algorithm designed for efficient indexing of high-dimensional visual features. This allows for the retrieval of visually similar images from millions of entries.
  2. Keyword Mining: Once a set of visually similar images is retrieved, the system employs Search Result Clustering (SRC) to mine representative keywords from the annotations (titles, surrounding text) of these retrieved images. These keywords are then ranked by salience and used to annotate the original uncaptioned image.

A key innovation is the Multi-Index algorithm, which combines multiple indexing techniques (e.g., K-means and VA⁺-File) to overcome the "curse of dimensionality" and achieve efficient approximate nearest neighbor search in high-dimensional spaces, crucial for large-scale datasets.

Datasets

  • Corel Database: Used for initial model comparison. It consists of 5,000 images with 371 keywords.
  • U. Washington (UW) Image Database: A larger dataset of 2.4 million web images, crawled from photo forums, which are described as having rich and accurate annotations. This dataset was used for more comprehensive experiments. The UW dataset used for evaluation in Section 3.2 consists of 1109 images and 351 unique words.

Key Insights and Ideas

  • Leveraging Web-Scale Data: The paper demonstrates that large-scale, readily available web data, even with its inherent noise, can be a powerful resource for image annotation, surpassing the limitations of small, curated datasets.
  • Search-Centric Approach: By reframing annotation as a search and mining problem rather than a supervised learning task, the system avoids the need for explicit training stages and can adapt to a much larger vocabulary.
  • Multi-Index for Efficiency: The proposed Multi-Index algorithm is crucial for making high-dimensional CBIR feasible on web-scale datasets, balancing precision and efficiency by combining multiple indexing strategies.
  • Open Vocabulary Advantage: The system's ability to annotate with an "unlimited vocabulary" is a significant advantage, as it more closely reflects real-world scenarios where new concepts and words emerge.
  • Closed vs. Open Datasets: The performance difference between experiments on curated (Corel) and open (UW) datasets highlights the practical challenges of annotating real-world, unconstrained image collections.

Key Results

  • Model Comparison (Corel Dataset): The proposed search-based annotation approach achieved competitive results, comparable to or better than established methods like Machine Translation (MT), Multi-Instance Learning (MIL), and Cross-Media Relevance Models (CMRM) on the Corel dataset. For example, average precision was 0.39 for the search approach compared to 0.20-0.41 for others.
  • Efficiency: The Multi-Index system achieved an average annotation time of 0.5 seconds per image on a dataset of 2.4 million images.
  • UW Dataset Performance: While auto-evaluation on the UW dataset yielded precision of 0.18 and recall of 0.22, human checks showed significant improvements, with actual precision of 0.18 and recall of 0.22 (HC-Web), representing a 157.1% and 100% improvement over auto-evaluation respectively.
  • Vocabulary Expansion: The system identified 9 new, correct annotations on a subset of the UW dataset that were outside the original UW vocabulary, demonstrating its ability to discover and utilize a broader range of keywords.

Limitations and Future Work

  • Global Features: The current system relies on global image features, which are effective for image-level concept annotation but less so for object-level annotation.
  • Future Work: The authors plan to investigate indexing and utilizing local features to improve annotation quality, especially for images with complex objects. They also aim to explore more sophisticated similarity measures to retrieve more semantically relevant image sets. The challenge of annotating open datasets without prior knowledge remains a significant area for future research.

Summary updated

BibTeX
@inproceedings{li2006image,
  author = {Xirong Li and Le Chen and Lei Zhang and Fuzong Lin and Wei-Ying Ma},
  title = {{Image annotation by large-scale content-based image retrieval}},
  booktitle = {ACM Multimedia},
  year = {2006},
  doi = {10.1145/1180639.1180764},
}
Figure