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:
- Storage Overhead: Storing millions of raw feature vectors (e.g., SIFT or Deep features) requires substantial RAM.
- 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
tanhactivation to relax bits during training, eventually forcing them toward discrete binary values (-1 or 1).
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:
- Initial Search: The system identifies the top 100 candidates using hash codes and a graph-based search (e.g., HNSW).
- Feature Reconstruction: The decoder reconstructs the features of these candidates from their binary codes.
- Asymmetric Re-ranking: Reconstructed features are re-ranked against the original query feature. This asymmetric approach significantly boosts precision without requiring original database features.
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