Abstract
Hashing has been widely used for large-scale search due to its low storage cost and fast query speed. By using supervised information, supervised hashing can significantly outperform unsupervised hashing. Recently, discrete supervised hashing and deep hashing are two representative progresses in supervised hashing. On one hand, hashing is essentially a discrete optimization problem. Hence, utilizing supervised information to directly guide discrete (binary) coding procedure can avoid sub-optimal solution and improve the accuracy. On the other hand, deep hashing, which integrates deep feature learning and hash-code learning into an end-to-end architecture, can enhance the feedback between feature learning and hash-code learning. The key in discrete supervised hashing is to adopt supervised information to directly guide the discrete coding procedure in hashing. The key in deep hashing is to adopt the supervised information to directly guide the deep feature learning procedure. However, there have not existed works which can use the supervised information to directly guide both discrete coding procedure and deep feature learning procedure in the same framework. In this paper, we propose a novel deep hashing method, called deep discrete supervised hashing (DDSH), to address this problem. DDSH is the first deep hashing method which can utilize supervised information to directly guide both discrete coding procedure and deep feature learning procedure, and thus enhance the feedback between these two important procedures. Experiments on three real datasets show that DDSH can outperform other state-of-the-art baselines, including both discrete hashing and deep hashing baselines, for image retrieval.
Introduction
In the era of massive data, finding similar images quickly requires hashing: mapping high-dimensional images into short, binary codes (e.g., 32 bits). This allows for lightning-fast searches using Hamming distance.
Existing research typically falls into two camps. Most "deep hashing" methods use deep learning to extract features but rely on relaxation strategies—treating discrete binary bits as continuous values during training to make them compatible with gradient descent. This often leads to sub-optimal binary codes. Conversely, "discrete supervised hashing" methods optimize binary codes directly but usually rely on hand-crafted features rather than learning them from scratch.
Deep Discrete Supervised Hashing (DDSH) bridges this gap by creating a unified framework where supervised labels (knowing which images are similar) directly influence both the discrete optimization of the codes and the training of the neural network.
Methods
The DDSH architecture consists of two main components: a Feature Learning Part and a Loss Part.
- Feature Learning: The framework utilizes a CNN-F architecture comprising 5 convolutional layers and 3 fully-connected layers. The final layer outputs a vector that is passed through a
signfunction to generate binary codes. - Discrete Optimization via Column Sampling: To handle the massive computational cost of comparing every image pair in a large dataset, DDSH uses a "column sampling" method. It randomly samples a subset of the training data to serve as anchors.
- Alternating Learning Strategy: The model trains in two alternating steps:
- Step 1: Fix the CNN and optimize the discrete binary codes for the sampled set using Binary Quadratic Programming (BQP). This ensures the codes are truly discrete and optimal for the given features.
- Step 2: Fix the binary codes and update the CNN parameters. Since the
signfunction has a zero gradient, the authors use atanhrelaxation during backpropagation to allow the network to learn "hash-friendly" features.
Datasets
The authors evaluated DDSH on three standard image retrieval benchmarks, ranging from single-label digits to multi-label natural scenes:
- CIFAR-10: 60,000 images across 10 classes (single-label).
- SVHN (Street View House Numbers): Over 600,000 images of digits in natural scenes (single-label).
- NUS-WIDE: A large-scale dataset of ~270,000 images with multi-label annotations.
Key Insights and Results
DDSH consistently outperformed nine state-of-the-art baselines, including popular deep methods like DPSH and DSH. The "aha moment" of this research is that supervised information shouldn't just be at the end of the pipeline. By including similarity labels in both the discrete code optimization and the feature learning, the two processes provide better feedback to each other.
- Accuracy (MAP): On CIFAR-10 with 32-bit codes, DDSH achieved a Mean Average Precision (MAP) of 0.835, significantly higher than DSH (0.786) and DPSH (0.740).
- Consistency: The performance gains were consistent across all bit lengths (12, 24, 32, and 48 bits) and all three datasets.
- Lookup Success: In hash lookup tasks (finding a neighbor within a small Hamming radius), DDSH reached a success rate of nearly 0.9 for 48-bit codes on CIFAR-10, outperforming competitors by a wide margin.
Conclusion and Future Work
By avoiding the common pitfall of "continuous relaxation," DDSH achieves state-of-the-art accuracy in large-scale image retrieval. While the code optimization is discrete, the CNN update still relies on a tanh approximation to handle gradients. Finding a way to perform truly discrete gradient-based updates for the neural network remains an open challenge. Additionally, the authors note that extending this discrete optimization framework from pairwise labels to triplet labels (ranking A as more similar to B than C) is a promising direction for future research.
Summary updated