# Boundary-Aware Hashing for Hamming Space Retrieval
## 1 Introduction  
The image retrieval system extracts features from each image in a database and stores them. The query image extracts the same feature vector and then performs distance matching with the feature vector in the database. The image is returned corresponding to the closest feature vector as the search result. It is widely used in the fields of pattern recognition, image search, duplicate detection, computer vision, e-commerce, etc. However, in the era of big data, large-scale and high-dimensional image data has brought a huge burden to the image retrieval system [1; 2; 3]. One popular and promising solution is deep supervised hashing, which has the advantages of lightweight storage and efficient computation [4; 5; 6]. Deep supervised hashing involves linear scan (Hamming ranking) or Hamming space retrieval. Linear scan outputs the ranked list based on the Hamming distance, and the time complexity on a dataset of size \(N\) is \(O(N)\)[7; 8]. Hamming space retrieval executes the search through hash table lookups and returns data points within a small Hamming ball because it has the time complexity of \(O(1)\) when the radius of the Hamming ball is not more than 2 [9]. Therefore, it is more suitable for large-scale databases than the linear scan and has become popular in recent years. The linear scan can be used for Hamming space retrieval, and it can obtain a satisfying retrieval performance when the code length is small, such as 8 bits or 16 bits. However, as the code length increases, the Hamming space becomes highly sparse, which makes it difficult to pull similar pairs into the Hamming ball and results in performance degradation [10; 11; 12; 13]. To address this issue, deep Cauchy hashing (DCH) [7] and maximum-margin Hamming hashing (MMHH) [9] are specifically proposed for Hamming space retrieval. DCH [7] designs a pairwise cross-entropy loss based on the Cauchy distribution to push dissimilar pairs out of the Hamming ball. Nevertheless, it does not considered the Hamming ball as an absolute boundary, and it is possible to prune out some similar pairs, which results in decreased recall, especially for the longer code length. MMHH [9] introduces the radius of the Hamming ball as an absolute boundary. It can pull similar pairs into the ball. However, the loss is invariant for both similar and dissimilar pairs in the Hamming ball. Therefore, it is difficult to push the dissimilar pairs out of the ball, which results in poor precision. A solution that can improve the performance of Hamming space retrieval is that the model mainly learns the push of dissimilar pairs inside the Hamming ball and the pull of similar pairs outside the ball. Contrastive loss is designed by comparing the pull to similar and push to dissimilar samples, and it can effectively cluster similar samples. It is usually used in dimension reduction learning [14; 15], metric learning [16; 17], and so on. Deep supervised hashing (DSH) [15] is a contrastive loss based on the hashing algorithm, but it does not consider the absolute boundary, and its gradient intersection point and marginal threshold increase as code length increases, as shown in Figure 1a. It is difficult to concentrate similar pairs into Hamming ball with the absolute boundary. To solve this problem, in this paper, an exponential function is introduced for dissimilar pairs whose convergence boundary corresponds to the marginal threshold, which does not vary with code length. A logarithmic function is used to encourage small distance for similar pairs. Furthermore, absolute boundary (i.e., Hamming radius) information is introduced to guide the gradient intersection of contrastive loss near the boundary. It implements the conditions that push is bigger than pull inside the Hamming ball and that pull is bigger than push outside the ball, as shown in Figure 1b. This can improve both recall and precision, especially for longer code lengths. Based on the above loss, a Boundary-Aware Hashing (BAH) architecture is proposed for Hamming space retrieval.