Hash Ranking With Weighted Asymmetric Distance for Image Search
Hash Ranking With Weighted Asymmetric Distance for Image Search
复制标题
图像搜索的加权非对称距离哈希排序
DOI：
10.1109/tci.2017.2736980
复制
发表时间：
2017-12
影响因子：
5.4
通讯作者：
Keqiu Li
中科院分区：
文献类型：
--
作者：
Yuan Cao;Heng Qi;Jien Kato;Keqiu Li
图像搜索可以看作是在图像特征空间中进行大规模的近似最近邻（ANN）搜索。散列排序方法由于其占用内存少和搜索效率高的优点而被广泛应用于人工神经网络搜索。通常，散列排序方法面临两个问题：二进制编码和二进制代码排序。本文重点讨论后者。在现有的工作中，二进制哈希码的排序通常是基于汉明距离或非对称距离来实现的。当不同的候选点到查询点具有相同的汉明距离时，汉明距离容易导致混乱的排名。因此，最近的工作更倾向于非对称距离而不是汉明距离。在计算非对称距离时，需要给出合理的查询无关值。在现有的方法中，这些值通常由样本候选点的平均值来近似。然而，当候选点的分布不均匀时，平均值是没有意义的，导致错误的排名结果。针对这一问题，本文提出了两种加权非对称距离算法，即基于大津阈值的算法（WoRank）和基于得分计算的算法（WsRank）。这两个算法的过程是相似的，包括两个步骤。在第一步中，我们根据候选点的相应分布计算每个比特上的查询无关值，以减少近似误差。在第二步中，我们考虑到每个比特的区分能力，计算按位权重，以进一步提高检索精度。WoRank和WsRank之间的区别在于查询独立值和位权重的计算方法。为了评估所提出的算法，我们进行了大量的实验上四个著名的数据集，即SIFT，CIFAR-10，MNIST，NUS-WIDE。实验结果表明，该算法可以实现高达22%的性能增益超过汉明距离为基础的排名和现有的非对称距离为基础的排名13%。我们还发现WoRank适用于特征数据集（SIFT），而WsRank适用于图像数据集。
Image search can be viewed as a problem of large-scale approximate nearest neighbor (ANN) search in image feature space. Hash ranking methods have been widely used for ANN search because of their two benefits: less memory usage and high search efficiency. Generally, the hash ranking methods face two problems: binary encoding and binary code ranking. This paper focuses on the latter. In existing work, the ranking of binary hash codes is usually implemented based on Hamming distance or asymmetric distance. Hamming distance easily leads to confusing ranking when different candidate points share the same Hamming distance to the query point. Therefore, recent work prefers the asymmetric distance to Hamming distance. When computing asymmetric distance, it is necessary to give reasonable query-independent values. These values are usually approximated by average values of sample candidate points in existing methods. However, when the distribution of candidate points is not uniform, average values are meaningless, leading to wrong ranking results. To address this problem, we propose two kinds of weighted asymmetric distance algorithms, namely, the Otsu threshold based algorithm (WoRank) and the score calculation based algorithm (WsRank) in this paper. The processes of these two proposed algorithms are similar, consisting of two steps. In the first step, we compute the query-independent values on each bit in accordance with corresponding distribution of candidate points to reduce the approximation error. In the second step, we compute bitwise weights in consideration of each bit's discriminative power to further improve the retrieval accuracy. The differences between WoRank and WsRank are the computation methods of query-independent values and bitwise weights. To evaluate the proposed algorithms, we conduct a large number of experiments on four well-known datasets, namely, SIFT, CIFAR-10, MNIST, and NUS-WIDE. The results show that the proposed algorithms can achieve up to 22% performance gains over Hamming distance based ranking and 13% over the existing asymmetric distance based ranking. We also find WoRank is suitable for feature dataset (SIFT), while WsRank is suitable for image datasets.
登录
查看更多内容
DOI：
10.1023/b:visi.0000029664.99615.94
发表时间：
2004-11-01
影响因子：
19.5
作者：
Lowe, DG
通讯作者：
Lowe, DG
DOI：
10.1109/iccv.2013.177
发表时间：
2013-12
期刊：
2013 IEEE International Conference on Computer Vision
影响因子：
--
作者：
Giorgos Tolias;Yannis Avrithis;H. Jégou
通讯作者：
Giorgos Tolias;Yannis Avrithis;H. Jégou
DOI：
10.1145/1991996.1992012
发表时间：
2011-04
期刊：
Proceedings of the 1st ACM International Conference on Multimedia Retrieval
影响因子：
--
作者：
Yu-Gang Jiang;Jun Wang;Shih-Fu Chang
通讯作者：
Yu-Gang Jiang;Jun Wang;Shih-Fu Chang
DOI：
--
发表时间：
2009
期刊：
--
影响因子：
--
作者：
A. Krizhevsky
通讯作者：
A. Krizhevsky
DOI：
10.4086/toc.2012.v008a014
发表时间：
2012-07
期刊：
Theory Comput.
影响因子：
--
作者：
Sariel Har-Peled;P. Indyk;R. Motwani
通讯作者：
Sariel Har-Peled;P. Indyk;R. Motwani