Quantized Correlation Hashing for Fast Cross-Modal Search

Botong Wu, Qiang Yang, Wei-Shi Zheng, Yizhou Wang, Jingdong Wang

Abstract

Cross-modal retrieval, such as searching for images using text queries, requires efficient hashing techniques to handle large-scale datasets. Traditional methods often separate correlation maximization from binary quantization, leading to a "quantization gap" that degrades performance. This paper introduces Quantized Correlation Hashing (QCH), a framework that jointly optimizes for cross-modal correlation and quantization loss. By treating quantization as an integral part of the learning process, QCH achieves state-of-the-art retrieval accuracy across diverse datasets including Wiki, NUS-WIDE, and 58W-CIFAR.

Introduction

In our multi-modal world, the ability to search across domains—for example, using a text query to find relevant images—is increasingly critical. To make this search fast enough for massive databases, researchers use hashing to convert complex data into short strings of binary bits.

The primary challenge in current hashing techniques lies in the "quantization gap." Most existing methods follow a two-step process: first, they learn a continuous representation that maximizes correlation between modalities, and then they quantize (round) those values into binary bits. This separation often leads to sub-optimal solutions because the rounding process ignores the carefully learned relationships between domains. This paper proposes that to achieve optimal search results, hashing functions and the quantization process must be learned simultaneously.

Proposed Method: Quantized Correlation Hashing (QCH)

Overview of the cross-modal hashing framework showing the training of hash functions and the search process across image and text modalities.

The core innovation of QCH is a unified objective function that balances two competing needs: correlation maximization and quantization loss minimization.

  1. Correlation Maximization: This ensures that an image and its corresponding text result in similar binary codes. The framework uses a "maximum margin" version of cosine similarity to measure this relationship.
  2. Quantization Loss Minimization: This ensures the binary codes remain as close as possible to the original continuous features, thereby preserving maximum information during the conversion.

To solve this complex optimization problem, the authors employ several mathematical strategies. They derive an upper bound for the objective function to facilitate optimization and transform the multi-modal problem into a single "unimodal" framework. Finally, an alternating optimization strategy is used to iteratively update projection weights and binary codes until the model converges.

Experimental Evaluation

The model was evaluated on three diverse real-world datasets:

  • Wiki: 2,866 image-text pairs from Wikipedia categorized into 10 classes.
  • NUS-WIDE: A large-scale dataset of nearly 270,000 images and associated Flickr tags.
  • 58W-CIFAR: A massive dataset of over 580,000 images used to test multi-view capabilities by extracting different visual features (GIST and HOG) as separate modalities.

Key Results and Insights

Mean Average Precision (MAP) comparison of QCH against state-of-the-art methods (CMSSH, CVH, SCM, etc.) across varying training set sizes for both image-to-text and text-to-image tasks.

QCH was compared against several state-of-the-art methods, including CMSSH, CVH, and SCM. In almost every test case across all three datasets, QCH achieved the highest Mean Average Precision (MAP) scores. For instance, on the Wiki dataset, QCH achieved a MAP of 0.2239 with 8-bit codes, significantly outperforming competitors like CVH (0.1962).

Key findings include:

  • Joint Optimization Advantage: Incorporating quantization loss directly into the learning objective significantly boosts retrieval accuracy compared to two-step methods.
  • Consistency Across Tasks: Unlike methods that favor one retrieval direction, QCH showed balanced performance for both image-to-text and text-to-image tasks.
  • Scalability and Efficiency: The method scales effectively to datasets with over half a million objects and maintains a performance lead even as bit length increases, demonstrating superior use of the "bit budget."

Conclusion and Future Work

QCH provides a robust solution for cross-modal search by bridging the quantization gap. While highly effective, future work could explore non-linear or deep learning-based features to capture even more complex data relationships. Additionally, extending the framework to fully unsupervised scenarios where no pairing information is available remains an open challenge.

Summary updated

Abstract

Cross-modal hashing is designed to facilitate fast search across domains. In this work, we present a cross-modal hashing approach, called quantized correlation hashing (QCH), which takes into consideration the quantization loss over domains and the relation between domains. Unlike previous approaches that separate the optimization of the quantizer independent of maximization of domain correlation, our approach simultaneously optimizes both processes. The underlying relation between the domains that describes the same objects is established via maximizing the correlation between the hash codes across the domains. The resulting multi-modal objective function is transformed to a unimodal formalization, which is optimized through an alternative procedure. Experimental results on three real world datasets demonstrate that our approach outperforms the state-of-the-art multi-modal hashing methods.
BibTeX
@inproceedings{wu2015quantized,
  author = {Botong Wu and Qiang Yang and Wei-Shi Zheng and Yizhou Wang and Jingdong Wang},
  title = {{Quantized Correlation Hashing for Fast Cross-Modal Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure