Learning an image manifold for retrieval

Xiaofei He, Wei-Ying Ma, HongJiang ZhangACM Multimedia 2004 · DOI

TL;DR

This paper proposes a novel approach to image retrieval by learning a mapping from low-level image features to a high-level semantic space. By assuming images lie on a low-dimensional manifold and leveraging relevance feedback, the system learns to represent images in a way that aligns with human perception, significantly improving retrieval accuracy.

What Problem Does This Paper Address?

Content-Based Image Retrieval (CBIR) aims to find images similar to a query image. Traditional CBIR systems often assume images exist in a Euclidean space and rely on simple distance metrics. However, the authors argue that image spaces are more naturally represented as non-linear submanifolds embedded in high-dimensional Euclidean spaces. This "image manifold" has an intrinsic metric structure that differs from the ambient Euclidean space. The core problems addressed are: 1) How to accurately represent images, and 2) How to effectively judge similarity, especially when the underlying data structure is non-linear and the number of data points is small, making it difficult to discover the intrinsic manifold structure.

Methods

The paper introduces a two-pronged approach:

  1. Retrieval on Image Manifold: This method uses a relevance feedback scheme to estimate geodesic distances on the image manifold.
  2. Candidate Generation: For a query, k-nearest neighbors are found.
  3. Subgraph Construction: A graph is built where nodes are images, and edge weights represent distances (Euclidean if small, otherwise infinity).
  4. Geodesic Distance Calculation: Floyd's algorithm is used to compute shortest-path distances on the graph, approximating geodesic distances on the manifold.
  5. Ranking: Images are ranked based on these geodesic distances.
  6. Feedback Loop: Relevant images are added to the database, and the process iterates.
  7. Learning a Semantic Space: This approach aims to "flatten" the image manifold into a Euclidean semantic space where distances are consistent with human perception.
  8. Inferring Semantic Distances: User interactions (positive/negative examples) are used to adjust a distance matrix, shortening distances between relevant images and lengthening distances to irrelevant ones.
  9. Laplacian Eigenmaps (LE): This technique is used to find a low-dimensional embedding (LE semantic space) that preserves pairwise distances from the inferred semantic matrix. This space is specific to the training database.
  10. Radial Basis Function (RBF) Neural Network: An RBF network is trained to map low-level image features to the LE semantic space. This learned mapping function creates a "RBFNN semantic space" that is defined everywhere, allowing new images to be mapped and retrieved.

Datasets

  • Corel Dataset: Used for experiments. It consists of 3,000 images from 30 semantic categories, with 100 images per category.
  • Training Set: 2,700 images (90 per category).
  • Testing Set: 300 images (10 per category) used to evaluate generalization capability.
  • Features: Combined feature vectors of 435 dimensions, including color features (histogram, moment, coherence) and texture features (Tamura coarseness histogram, directionary, pyramid wavelet texture).

Key Insights and Ideas

  • Manifold Assumption is Crucial: The paper strongly suggests that images don't naturally reside in a Euclidean space but on a lower-dimensional manifold. Ignoring this intrinsic structure leads to suboptimal retrieval.
  • Relevance Feedback as Manifold Discovery: User feedback is not just for refining results but is actively used to discover and approximate the underlying manifold structure.
  • Semantic Space as a "Flat" Manifold: The goal of learning a semantic space is to transform the complex, non-linear manifold into a simple, Euclidean space where standard distance metrics work well and align with human intuition.
  • RBFNN for Generalization: While LE semantic space is powerful, it's limited to the training set. The RBFNN acts as a crucial bridge, learning a generalizable mapping function that allows retrieval for unseen images.
  • Geodesic vs. Euclidean Distance: The paper demonstrates that geodesic distances on the manifold are more appropriate for similarity measurement than simple Euclidean distances in the ambient feature space, especially when data points are sparse.

Key Results

  • Improved Retrieval Accuracy: The proposed "retrieval on image manifold" algorithm outperforms Rui's algorithm (a baseline) when operating in the low-level feature space, highlighting the benefit of considering manifold structure.
  • Semantic Space Superiority: Retrieval performance in both LE semantic space and the learned RBFNN semantic space significantly outperforms retrieval in the low-level feature space, especially at the initial query stage (without feedback).
  • RBFNN Approximation Accuracy: The RBFNN semantic space achieves retrieval performance very close to the LE semantic space, indicating that the RBFNN accurately approximates the optimal mapping function.
  • Generalization Capability: The RBFNN demonstrates strong generalization, performing well on query images outside the training database.
  • Dimensionality Impact: The optimal dimensionality of the semantic space is found to be closely related to the number of semantic classes in the database, suggesting a principled way to choose dimensionality.

Limitations and Future Work

  • Empirical vs. Theoretical Proof of Manifold Presence: The authors acknowledge that while their results provide indirect evidence, there's no definitive proof that manifold properties are always crucial or that such structures are actually present in all image datasets.
  • Nature of the Semantic Mapping: The exact properties of the true mapping from low-level features to high-level semantics remain unclear. It's unknown if it's one-to-one or many-to-one, and the theoretical underpinnings of its statistical learning are still being explored.
  • Future Work: The paper implicitly suggests further theoretical investigation into the nature of semantic spaces and the conditions under which manifold structures are critical for image retrieval.

Summary updated

BibTeX
@inproceedings{he2004learning,
  author = {Xiaofei He and Wei-Ying Ma and HongJiang Zhang},
  title = {{Learning an image manifold for retrieval}},
  booktitle = {ACM Multimedia},
  year = {2004},
  doi = {10.1145/1027527.1027532},
}
Figure