基于离散优化的哈希编码学习方法

Learning to Hash with Discrete Optimization

哈希作为近似近邻搜索的一种主流方法,通过将样本索引为紧致的二值编码,在计算效率和存储上都非常高效.由于二值码的离散特性,以往的哈希方法往往需要将二值码松弛为实数值才能高效地进行优化,因此在优化完成后重新将实数值的结果量化为二值时难免会由于二值的汉明空间与实数值的欧氏空间之间的差异而遇到性能上的损失问题.为了更好地解决量化损失的问题,本文提出了一种深度离散优化哈希(Deep Discrete Optimization Hashing,DDOH)方法.首先,设计了一种新的离散优化算法,通过直接在二值的汉明空间中对二值码进行优化,得到具有强判别性的二值编码.然后,训练卷积神经网络模型拟合上述二值码,得到用于编码的哈希函数.在CIFAR-10和ImageNet-100两个常用的评测数据集上的实验显示,本文提出的方法在CIFAR-10数据库上与目前最好的方法达到了同样的性能,在ImageNet-100数据库上的平均准确率指标与已有方法相比提升了约2.2%,证明了该方法的有效性.

In recent years, billions of images are uploaded to the Internet every day, making it extremely difficult to find an interested image according to a user’s demand. This paper addresses the content-based image retrieval task, which aims at looking for database images that are similar to the given query image. However, due to the huge size of modern datasets, exact nearest neighbor search method cannot produce retrieval results in acceptable time. Therefore, approximate nearest neighbor search methods are proposed to sacrifice accuracy for acceptable retrieval time. As a mainstream approximate nearest neighbor (ANN) search method, hashing projects the original feature vectors of samples into very compact binary codes, and thus is very efficient in both computation and storage. As a result, hashing methods have received more and more research attention over the past twenty years. However, due to the discrete nature of binary codes, directly optimizing the binary codes is an NP-hard problem and the computation time required for obtaining the global optimum would be unacceptable. To deal with this problem, existing hashing methods can only perform optimization efficiently by relaxing the binary codes to real values, and optimize the real-valued counterpart of the objective function instead. After that, the optimum obtained in the relaxed real-valued space are again quantized to generate the real binary codes. However, there is no guarantee that the real-valued optimum would remain optimum after quantization, and thus existing methods inevitably suffer from performance drop when quantizing the real-valued optimization results into binary codes, due to the discrepancy between the binary Hamming space and the real-valued Euclidean space. To better deal with the problems of quantization, this paper proposes a novel hash learning method, named Deep Discrete Optimization Hashing (DDOH). First of all, the initial binary codes of all training image samples are obtained by one of the three binary code initialization methods proposed in this paper. After that, a discrete binary codes optimization algorithm is designed, which takes the initial binary codes of training images as well as their corresponding label information as inputs. The proposed optimization algorithm iteratively decides whether or not to flip certain binary bits in the binary codes with the Fisher’s law, and it is theoretically proved in this paper that by doing so, the proposed method would improve or at least would not decrease the discriminability of the binary codes in terms of the Fisher’s law. Next, to obtain the hash functions which would be used to encode new-coming images, a deep convolutional neural network (CNN) is trained to fit the aforementioned binary codes. Specifically, with the optimized binary codes, each bit can be seen as a binary classification problem, and all binary classifiers that share the same feature map of the CNN as training inputs are trained to perform as the hashing functions. Experiments on two widely studied datasets CIFAR-10 and ImageNet show that the proposed method achieves state of the art retrieval performance on CIFAR-10, and improves the performance of existing hashing methods by about 2.2% mean Average Precision (mAP) on ImageNet-100, validating the effectiveness of the proposed method.