Unsupervised Rank-Preserving Hashing for Large-Scale Image Retrieval

Svebor Karaman, Xudong Lin, Xuefeng Hu, Shih-Fu Chang

Abstract

Unsupervised Rank-Preserving Hashing (URPH) addresses the storage and retrieval efficiency challenges in large-scale image search. By mapping high-dimensional features into compact binary codes while preserving their original similarity rankings, URPH eliminates the need to store raw feature vectors. A novel decoder-based reconstruction mechanism allows for high-precision asymmetric re-ranking using only compressed data. Evaluated on SIFT1M and Deep1M benchmarks, URPH demonstrates significant improvements in recall and memory efficiency over state-of-the-art unsupervised hashing methods.

Introduction

In large-scale image retrieval, images are typically represented as high-dimensional feature vectors. Finding similar images involves an Approximate Nearest Neighbor (ANN) search, which faces two primary bottlenecks:

  1. Storage Overhead: Storing millions of raw feature vectors (e.g., SIFT or Deep features) requires substantial RAM.
  2. The Re-ranking Trap: Most existing hashing methods produce short codes that lack sufficient discriminative power. Consequently, systems often perform a fast initial search with hash codes followed by a slow re-ranking step using original, uncompressed features. This dependency necessitates storing the original data, undermining the benefits of compression.

URPH aims to create a self-sufficient system that compresses features effectively enough to allow the deletion of original data while maintaining high retrieval accuracy.

Methodology

The URPH architecture integrates a Hashing Model and a Decoder to enable efficient retrieval and reconstruction.

Training the Hashing Model

The hashing model employs a shallow neural network to map input features to binary codes. The training objective is defined by three primary loss functions:

  • Rank-Preserving Loss ($L_R$): This loss focuses on preserving the relative order of image triplets. If Image A is closer to a query than Image B in the original feature space, the model is penalized if this ranking is inverted in the Hamming space. A weighting scheme prioritizes the accuracy of top-ranked results.
  • Bit Uncorrelation Loss ($L_U$): Ensures each bit in the hash code provides unique information, minimizing redundancy.
  • Binarization Loss ($L_B$): Uses a tanh activation to relax bits during training, eventually forcing them toward discrete binary values (-1 or 1).
Training framework of URPH with rank-preserving and reconstruction losses

Retrieval and Asymmetric Re-ranking

To eliminate the need for original database features, a decoder is trained to reconstruct features from binary hash codes. The retrieval pipeline proceeds as follows:

  1. Initial Search: The system identifies the top 100 candidates using hash codes and a graph-based search (e.g., HNSW).
  2. Feature Reconstruction: The decoder reconstructs the features of these candidates from their binary codes.
  3. Asymmetric Re-ranking: Reconstructed features are re-ranked against the original query feature. This asymmetric approach significantly boosts precision without requiring original database features.
Retrieval pipeline of URPH

Experiments and Results

The method was evaluated on two standard benchmarks: SIFT1M (1 million 128-dimensional descriptors) and Deep1M (1 million 96-dimensional deep features).

  • Accuracy: URPH consistently outperformed state-of-the-art unsupervised methods such as ITQ and OPH. On the Deep1M dataset with 128-bit codes, it achieved relative gains of approximately 35% in Recall@1 compared to the next best baseline.
  • Compression Efficiency: For the SIFT1M dataset, memory requirements were reduced from 488MB (original features) to 34MB (hash codes and graph structure), representing a reduction of over 90%.
  • Search Speed: The average search time for a 1-million image database was approximately 5ms, with the reconstruction and re-ranking steps adding only 0.2ms of overhead.

Conclusion

URPH demonstrates that focusing on rank preservation rather than absolute distance yields more robust retrieval in high-dimensional spaces. By leveraging a reconstruction-based re-ranking mechanism, the system achieves high accuracy while drastically reducing storage requirements. Future work will explore deeper architectures and billion-scale deployments.

Summary updated

BibTeX
@inproceedings{karaman2019unsupervised,
  author = {Svebor Karaman and Xudong Lin and Xuefeng Hu and Shih-Fu Chang},
  title = {{Unsupervised Rank-Preserving Hashing for Large-Scale Image Retrieval}},
  booktitle = {ICMR},
  year = {2019},
  url = {https://openreview.net/forum?id=l_-g_fK6xGS},
}
Figure