cvpr cvpr2013 cvpr2013-63 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Lei Zhang, Yongdong Zhang, Jinhu Tang, Ke Lu, Qi Tian
Abstract: Binary hashing has been widely used for efficient similarity search due to its query and storage efficiency. In most existing binary hashing methods, the high-dimensional data are embedded into Hamming space and the distance or similarity of two points are approximated by the Hamming distance between their binary codes. The Hamming distance calculation is efficient, however, in practice, there are often lots of results sharing the same Hamming distance to a query, which makes this distance measure ambiguous and poses a critical issue for similarity search where ranking is important. In this paper, we propose a weighted Hamming distance ranking algorithm (WhRank) to rank the binary codes of hashing methods. By assigning different bit-level weights to different hash bits, the returned binary codes are ranked at a finer-grained binary code level. We give an algorithm to learn the data-adaptive and query-sensitive weight for each hash bit. Evaluations on two large-scale image data sets demonstrate the efficacy of our weighted Hamming distance for binary code ranking.
Reference: text
sentIndex sentText sentNum sentScore
1 edu 0 ct an Abstract Binary hashing has been widely used for efficient similarity search due to its query and storage efficiency. [sent-11, score-0.643]
2 In most existing binary hashing methods, the high-dimensional data are embedded into Hamming space and the distance or similarity of two points are approximated by the Hamming distance between their binary codes. [sent-12, score-0.759]
3 The Hamming distance calculation is efficient, however, in practice, there are often lots of results sharing the same Hamming distance to a query, which makes this distance measure ambiguous and poses a critical issue for similarity search where ranking is important. [sent-13, score-0.386]
4 In this paper, we propose a weighted Hamming distance ranking algorithm (WhRank) to rank the binary codes of hashing methods. [sent-14, score-0.821]
5 By assigning different bit-level weights to different hash bits, the returned binary codes are ranked at a finer-grained binary code level. [sent-15, score-0.944]
6 We give an algorithm to learn the data-adaptive and query-sensitive weight for each hash bit. [sent-16, score-0.479]
7 Recently, binary hashing [20, 21, 16, 14, 12, 3, 6, 11] is becoming increasingly popular for efficient approximated nearest neighbor (ANN) search due to its good query and storage efficiency. [sent-21, score-0.838]
8 The goal of binary hashing is to learn binary representations for data such that the neighborhood structure in the original data space can be preserved after embedded into Hamming space. [sent-22, score-0.611]
9 Given a dataset, binary hashing generates binary code for each data point and approximates the distance or similarity of two points by the Hamming distance between their binary codes, which means most hashing methods rank the returned results based on their Hamming distances to query. [sent-23, score-1.452]
10 However, since the Hamming distance is discrete and bounded by the code length, in practice, there will be a lot of data points sharing the same Hamming distance to the query and the ranking of these data points is ambiguous, which poses a critical issue for similarity search, e. [sent-25, score-0.587]
11 As a result, most existing binary hashing methods lack in providing a good ranking of results. [sent-28, score-0.629]
12 In this paper, we propose a weighted Hamming distance ranking algorithm (WhRank) to improve the ranking performance of binary hashing methods. [sent-29, score-0.853]
13 By assigning different bit-level weights to different hash bits, it is possible to rank two binary codes sharing the same Hamming distance to a query at a finer-grained binary code level, and gives binary hashing methods the ability to distinguish between the relative importance of different bits. [sent-30, score-1.613]
14 We also give an algorithm to learn a set of dynamic bit-level weights of hash bits for a given query. [sent-31, score-0.636]
15 By taking account of the information provided by the hash functions and dataset, we learn a set of dataadaptive and query-sensitive bit-level weights to reveal the relative importance of different hash bits. [sent-32, score-0.939]
16 Recently, hashing based methods [5, 3, 24] has been widely used for efficient similarity search in a large variety of applications due to its efficiency in terms of query speed and storage space. [sent-43, score-0.643]
17 The goal of binary hashing is to map each dataset point to a compact binary code such that similar data points in the original data space can be mapped to similar binary codes in Hamming space. [sent-44, score-0.962]
18 However, long code results in low recall since the collision probability of similar points mapped to similar binary codes decreases exponentially as the code length increases. [sent-47, score-0.456]
19 As a result, LSH-related methods usually construct multi-tables to ensure a reasonable probability that a query will collide with its near neighbors in at least one of the tables, which leads to a long query time and increases the memory occupation. [sent-48, score-0.414]
20 Semantic Hashing [17] adopts a deep generative model based on restricted Boltzmann machine to learn the hash functions that map similar points to similar binary codes. [sent-50, score-0.562]
21 Spectral Hashing (SPH) [21] uses spectral graph partitioning strategy for hash function learning and uses the simple analytical eigenfunction solution of 1-D Laplacians as the hash function. [sent-51, score-0.889]
22 In most existing binary hashing methods, including those methods discussed above, the returned results of a given query are simply ranked based on their Hamming distance to the query. [sent-56, score-0.845]
23 The calculation of Hamming distance is efficient, however, since this distance metric gives each hash bit the same weight, it unable to distinguish between the relative importance of different bits and causes ambiguity for ranking. [sent-57, score-0.888]
24 One way to alleviate this ambiguity is assigning different bit-level weights to different hash bits. [sent-58, score-0.475]
25 In [20], each bit of the binary code is assigned with a bit-level weight, while in [4], the aim is to weight the overall Hamming distance of local features for image matching. [sent-60, score-0.426]
26 propose a query-adaptive Hamming distance for image retrieve which assigns dynamic weights to hash bits, such that each bit is treated differently and dynamically. [sent-63, score-0.708]
27 In [22], the authors propose a query-sensitive hash code ranking algorithm (QsRank) for PCA-based hashing methods. [sent-67, score-1.036]
28 Given a query, QsRank assigns two weights to each hash bit and defines a score function to measure the confidence of the neighbors of a query mapped to a binary code. [sent-68, score-0.991]
29 First, QsRank is developed only for PCAbased binary hashing while WhRank can be applied to most existing binary hashing methods. [sent-72, score-1.023]
30 In most binary hashing algorithms, the distance between two points is simply measured by the Hamming distance between their binary codes. [sent-78, score-0.741]
31 With the bit-level weights, the returned binary codes can be ranked by the weighted Hamming distance at 111555888755 a finer-grained binary code level rather than at the original integer Hamming distance level. [sent-89, score-0.635]
32 The bit-level weight associated with hash bit k is denoted as ωk. [sent-90, score-0.619]
33 Note that, our algorithm is not to propose a new binary hashing method, but to give a ranking algorithm to improve the search accuracy of most existing binary hashing methods. [sent-92, score-1.184]
34 { xThe} paradigm of binary hashing is to first use a set of linear or non-linear hash functions F = {fk : Rd → R}kK=1 to map x ∈ X to F(x) ∈ RK, fK(x))T and then binarize F(x) = (f1(x), ··· , by comparing each fk (x) with a thresh(oxld) ,T··k ·to , get a K-bit binary code H(x) ∈ {0, 1}K. [sent-95, score-1.262]
35 Hence, the binary hash function is hcokd d(xe )H =(x s)gn ∈(f {k0 (,x1)} Tk). [sent-96, score-0.544]
36 Each(x xd)im −en Tsion of H(x) is called a hash bit, and for a query q and its neighbor p, if the k-th bit of H(q) and H(p) is different, we call there is a bit-flipping on hash bit k. [sent-98, score-1.434]
37 Data-Adaptive Weight We introduce a term discriminating power to denote the ability of a hash function hk (x) mapping similar data points to the same bit (0/1). [sent-102, score-0.895]
38 A hash function hk (x) is called discriminative if the probability of similar data points mapped to the same bit by hk (x) is not small (> 0. [sent-103, score-1.169]
39 The more discriminative hk (x), the more discriminative hash bit k. [sent-105, score-0.852]
40 Obviously, the discriminating power of a hash function is dependent on the algorithm generates it and the dataset used for training. [sent-106, score-0.509]
41 PCAH [20], SPH [21], ITQ [3] and AGH [12], the discriminating power of different hash function is intrinsically different. [sent-109, score-0.487]
42 For a hash function with a stronger discriminating power, it’s less likely for this hash function to generate different bits for two neighbor points. [sent-110, score-1.134]
43 In other word, for a query q and two data points p(1) , p(2) sharing the same Hamming distance (1) to q, where H(p(1) ) and H(p(2) ) are different with H(q) on hash bits k1 and k2 respectively. [sent-111, score-0.868]
44 If hash bit k1 is more discriminative than k2, then p(1) is considered to be less similar with q than p(2) , since the bit-flipping on hash bit k1 gives a higher confidence that p(1) is not a neighbor of q than that on k2. [sent-112, score-1.269]
45 To make DHw (H(q) , H(p(1) )) larger than DHw (H(q) , H(p(2) )), ωk1 should be larger than ωk2 , which means the more discriminative a hash bit k is, the larger the associated weight ωk is. [sent-113, score-0.632]
46 hash function hk (x)) is related to the probability of similar points mapped to the same bit by hk (x), given a hash function hk (x), we can use the distribution of hk (p) − hk (q), where p ∈ N(q), to reveal how discriminative( hpa)s h− b hit k is. [sent-116, score-2.332]
47 Histograms of the differences between the unbinarized hash values of a query and its neighbors, generated by ITQ [3] and SPH [21]. [sent-118, score-0.676]
48 However, since hk (p) and hk (q) are binarized, too much useful information is lost. [sent-120, score-0.466]
49 An alternative is to use the distribution of the difference between their unbinarized hash values, i. [sent-121, score-0.524]
50 If sk (p, q)( pis) −difstributed in a small interval centered around 0, then the probability of hk (p) = hk (q) is high, yielding a high discriminative hash bit k. [sent-124, score-1.123]
51 As can be seen from this figure, the distributions are all Bell-shaped, as all these binary hashing methods try to minimize the distances between similar points after hashing. [sent-127, score-0.536]
52 As a result, ωk is a function of the distribution of sk, which is parameterized by the its mean μk and standard deviation σk: − ωk = g(μk , σk) (1) Note that, hash bit k is more discriminative if σk is smaller, therefore, ωk = g(μk, σk) should be monotonically nonincreasing w. [sent-128, score-0.649]
53 2, as shown, the probability of bit-flipping on hash bit k increases with the standard deviation σk. [sent-133, score-0.619]
54 Query-Sensitive Weight Meanwhile, for a specified data point q, the probability of its neighbor p mapped to a bit different from Hk (q) by hash function hk (x) is also dependent on q itself. [sent-136, score-0.997]
55 Intuitively, if |fk (q) Tk | is small, then after adding a random nitioviseely n,˜ i tfo | q, iqt’)s more likely tlhl,at th fekn n( aqf t+e rn˜ a)d ldi ensg on tahned opposite side of Tk as compared to fk (q), which means the probability of hk (p) differs from hk (q) for p ∈ N(q) is high. [sent-137, score-0.628]
56 A query q is mapped to “101”, the binary codes of p1, p2 and p3 are “001”, “1 11”, “1 10” respectively. [sent-140, score-0.417]
57 However, it’s more suitable to rank the hash code “1 10” and “1 11” before “001” because q is far from the threshold of hash function h1, it’s less likely for a near neighbor of q lies on the opposite side of h1. [sent-142, score-1.037]
58 The probability of a query q’s neighbor, p, mapped to a bit different from h(q) by hash function h(x) = sgn(f(x) T). [sent-153, score-0.85]
59 In this section, we give a simple method to calculate the data-adaptive and query-sensitive bit-level weight ωk (q) of each hash bit k for a given query q, and we will show that ωk (q) satisfies the abovementioned constraints theoretically. [sent-169, score-0.828]
60 Therefore, given a query q and a binary code h, a function parameterized by Pr(h|H(q)) is used as a probabilisttiico interpretation odf DHw (rH(h(q|H) , (hq)). [sent-171, score-0.365]
61 As a result, given a query q, the weighted Hamming distance between H(q) and a binary code h is defined as follows: DHw(H(q), h) ≈ −log Pr(h|H(q)) (3) 0ph012 h1 10 1qp2 13h103Pr(Δhk(q)≠0Tkf (q)Prs(kΔ=hfk (qp)=-f0k( )q(x) Figure 3. [sent-183, score-0.463]
62 The Right illustrates the probability of a neighbor of q mapped to a different bit by hash function fk (x), Tk is the binary threshold. [sent-185, score-0.986]
63 Assume all the hash bits are independent [22], we have: Pr(h|H(q)) = ? [sent-186, score-0.592]
64 k = = where Pr(hk hk (q)) (denoted by Pr(Δhk (q) 0)) is the probability ohf hash bit k of h flipped as compared with that of H(q), and Pr(hk = hk (q)) (denoted by Pr(Δhk (q) = 0)) is the probability of hash bit k of h not flipped . [sent-190, score-1.734]
65 Apparently, these two probabilities are dependent on the specified query q and the hash function hk (x). [sent-191, score-0.869]
66 k∈S where S is the set of hash bits in h differ from H(q), and λk(q) = logPPrr((ΔΔhhkk((qq))? [sent-198, score-0.592]
67 −2, we can use the distribution of s(q + q) = fk (q + n˜ ) fk (q) with density function pdfk (s) to estimate( qPr +(Δ n˜h)k − −(q) f 0). [sent-211, score-0.36]
68 Given a query q, first the unbinarized hash value fk (q) of each hash bit k is calculated. [sent-229, score-1.405]
69 Note that, since we make no assumption about the hashing method used in the bit-level weights learning, our algorithm, WhRank, can be applied to different kinds of hashing methods. [sent-243, score-0.847]
70 (5), given a query q and a binary code h, DHw (H(q) , h) can be calculated efficiently as: ωT (q) (H(q) ⊗ h), where ⊗ means the xor of two binary cod(eqs a(Hnd( qω)( q⊗) =), w(ωh1e(rqe) ⊗, ω m2(eqa)n,s s· ·t · , ωxoKr( oqf) )twTo. [sent-246, score-0.473]
71 b Winhairley the weighted distances can now ) b,e· c·a ,lωculated by innerproduct operation, it is actually possible to avoid this computational cost by computing the traditional Hamming distance first, and then ranking the returned binary codes based on their weighted-Hamming distances to H(q). [sent-247, score-0.532]
72 Therefore, the ranking of the returned binary codes can be obtained with minor additional cost. [sent-248, score-0.392]
73 To learn the μk and σk of a hash function hk (x), we construct a training set consists of s query points, each of which has m neighbors. [sent-249, score-0.847]
74 The complexity of calculating the unbinarized hash values of each query and its neighbors is almost O(s(m + 1)d), and the complexity of calculating μk and σk is bounded by O(3sm). [sent-250, score-0.722]
75 3, our methods can be applied to different kinds of binary hashing methods. [sent-263, score-0.519]
76 In our experiments, some representative hashing methods, Locality Sensitive Hashing (LSH) [1], PCA Hashing (PCAH) [20], Iterative Quantization (ITQ) [3], Spectral Hashing (SPH) [21] and Anchor Graph Hashing (AGH) [12], are chosen to evaluate the effectiveness of WhRank. [sent-264, score-0.395]
77 Note that, the hash functions of LSH, PCAH and ITQ are linear, while those of SPH and AGH are nonlinear. [sent-267, score-0.436]
78 2 show that, WhRank is applicable to both linear and nonlinear hashing methods. [sent-269, score-0.395]
79 Since QsRank is developed only for PCA-based hashing methods, the comparisons are carried out on PCAH and ITQ. [sent-271, score-0.424]
80 Given a query, by ranking with traditional Hamming distance and our weighted Hamming distance, the returned top N nearest neighbors and the rankings are both different. [sent-272, score-0.383]
81 For MINST70K, a returned point is considered as a true neighbor of a query if they share the same digit label. [sent-281, score-0.359]
82 For ANN-SIFT1M, we use the same criterion as in [19]: a returned point is considered to be a true neighbor if it lies in the top 1% points closest to the query in terms of Euclidean distance in the original space. [sent-282, score-0.402]
83 Experimental Results To demonstrate the efficacy of applying our weighted Hamming distance for ranking, given a query, the returned results of each baseline hashing method are ranked by their traditional Hamming distance and the weighted Hamming distance to the query respectively. [sent-285, score-1.014]
84 The dataset is first embedded into Hamming space using each baseline hashing method. [sent-290, score-0.417]
85 It is easy to find out that, by ranking with our weighted Hamming distance (WhRank), all baseline hashing methods achieve a better search performance. [sent-299, score-0.676]
86 On average, we get a 5% higher precision for each hashing method. [sent-300, score-0.427]
87 Once again, we can easily find out that the performance of each baseline hashing method is improved when combined with WhRank. [sent-307, score-0.436]
88 5(c), even with a relatively short binary code (32 bits), the retrieval accuracy of each baseline method combined with WhRank is almost the same as, sometimes better than, that of the baseline method itself with a binary code of larger size (64 bits, 96 bits). [sent-310, score-0.452]
89 The experimental results demonstrate that applying WhRank to existing hashing methods yielding a more accurate similarity search result. [sent-321, score-0.448]
90 Since QsRank is developed only for PCA-based hashing method, The comparisons are carried out on PCAH [20] and ITQ [3]. [sent-323, score-0.424]
91 -neighbor search, in our experiments on MINST70K, given a query q and N, the 111555889199 (a) 48 bits (b) 64 bits (c) 96 bits Figure 5. [sent-325, score-0.646]
92 One remarkable advantage of WhRank over QsRank is that, the ranking model of WhRank is more general, thus WhRank is also applicable to other non-PCA-based hashing methods, e. [sent-340, score-0.521]
93 -neighbor search, while QsRank is not very effective for nearest neighbor search since the distance between a query and its nearest neighbor is often unknown in practice. [sent-344, score-0.479]
94 Conclusion Most existing binary hashing methods rank the returned results of a query simply with the traditional Hamming distance, which poses a critical issue for similarity search where ranking is important, since there can be many results sharing the same Hamming distance to the query. [sent-346, score-1.048]
95 When applied to existing hashing methods, different bit-level weights are assigned to different hash bits, and the returned results can be ranked at a finer-grained binary code level rather than at the original integer Hamming distance level. [sent-348, score-1.209]
96 The search performances of all evaluated hashing methods are improved when combined with WhRank. [sent-351, score-0.449]
97 First, WhRank can be applied to various kinds ofhashing methods while QsRank is only developed for PCA-based hashing methods. [sent-354, score-0.428]
98 -neighbor search, it’s not very effective for nearest neighbor search since the distance of a query to its nearest neighbor is unknown in practice. [sent-356, score-0.479]
99 Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. [sent-370, score-0.5]
100 Supervised [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] hashing with kernels. [sent-442, score-0.395]
wordName wordTfidf (topN-words)
[('hash', 0.436), ('hashing', 0.395), ('whrank', 0.384), ('hamming', 0.299), ('qsrank', 0.26), ('hk', 0.233), ('query', 0.178), ('bit', 0.157), ('bits', 0.156), ('dhw', 0.143), ('fk', 0.136), ('ranking', 0.126), ('binary', 0.108), ('pcah', 0.106), ('pr', 0.097), ('sph', 0.097), ('itq', 0.088), ('tk', 0.086), ('returned', 0.08), ('code', 0.079), ('codes', 0.078), ('neighbor', 0.07), ('agh', 0.064), ('lsh', 0.064), ('pdfk', 0.062), ('unbinarized', 0.062), ('distance', 0.056), ('mapped', 0.053), ('efficacy', 0.047), ('weighted', 0.042), ('discriminating', 0.036), ('search', 0.035), ('nearest', 0.035), ('neighbors', 0.032), ('precision', 0.032), ('retrieve', 0.032), ('digit', 0.031), ('laplace', 0.03), ('ranked', 0.028), ('weights', 0.027), ('weight', 0.026), ('erf', 0.026), ('distribution', 0.026), ('probability', 0.026), ('evaluations', 0.025), ('quantization', 0.025), ('dataadaptive', 0.025), ('fkk', 0.025), ('sk', 0.025), ('sharing', 0.024), ('pages', 0.023), ('annosearch', 0.022), ('china', 0.022), ('baseline', 0.022), ('lengths', 0.022), ('dependent', 0.022), ('nsfc', 0.02), ('hq', 0.019), ('combined', 0.019), ('weighting', 0.019), ('anchor', 0.018), ('similarity', 0.018), ('points', 0.018), ('storage', 0.017), ('monotonically', 0.017), ('locality', 0.017), ('developed', 0.017), ('give', 0.017), ('spectral', 0.017), ('eq', 0.017), ('beijing', 0.016), ('texas', 0.016), ('moreover', 0.016), ('rank', 0.016), ('kinds', 0.016), ('flipped', 0.015), ('compact', 0.015), ('sometimes', 0.015), ('ratio', 0.015), ('student', 0.015), ('apparently', 0.015), ('power', 0.015), ('distances', 0.015), ('calculation', 0.015), ('recall', 0.015), ('reveal', 0.015), ('bounded', 0.014), ('kulis', 0.014), ('assumption', 0.014), ('satisfies', 0.014), ('egou', 0.014), ('douze', 0.013), ('jiang', 0.013), ('hh', 0.013), ('academy', 0.013), ('discriminative', 0.013), ('ambiguity', 0.012), ('traditional', 0.012), ('smaller', 0.012), ('carried', 0.012)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999982 63 cvpr-2013-Binary Code Ranking with Weighted Hamming Distance
Author: Lei Zhang, Yongdong Zhang, Jinhu Tang, Ke Lu, Qi Tian
Abstract: Binary hashing has been widely used for efficient similarity search due to its query and storage efficiency. In most existing binary hashing methods, the high-dimensional data are embedded into Hamming space and the distance or similarity of two points are approximated by the Hamming distance between their binary codes. The Hamming distance calculation is efficient, however, in practice, there are often lots of results sharing the same Hamming distance to a query, which makes this distance measure ambiguous and poses a critical issue for similarity search where ranking is important. In this paper, we propose a weighted Hamming distance ranking algorithm (WhRank) to rank the binary codes of hashing methods. By assigning different bit-level weights to different hash bits, the returned binary codes are ranked at a finer-grained binary code level. We give an algorithm to learn the data-adaptive and query-sensitive weight for each hash bit. Evaluations on two large-scale image data sets demonstrate the efficacy of our weighted Hamming distance for binary code ranking.
2 0.48925164 223 cvpr-2013-Inductive Hashing on Manifolds
Author: Fumin Shen, Chunhua Shen, Qinfeng Shi, Anton van_den_Hengel, Zhenmin Tang
Abstract: Learning based hashing methods have attracted considerable attention due to their ability to greatly increase the scale at which existing algorithms may operate. Most of these methods are designed to generate binary codes that preserve the Euclidean distance in the original space. Manifold learning techniques, in contrast, are better able to model the intrinsic structure embedded in the original highdimensional data. The complexity of these models, and the problems with out-of-sample data, havepreviously rendered them unsuitable for application to large-scale embedding, however. In this work, we consider how to learn compact binary embeddings on their intrinsic manifolds. In order to address the above-mentioned difficulties, we describe an efficient, inductive solution to the out-of-sample data problem, and a process by which non-parametric manifold learning may be used as the basis of a hashing method. Our proposed approach thus allows the development of a range of new hashing techniques exploiting the flexibility of the wide variety of manifold learning approaches available. We particularly show that hashing on the basis of t-SNE [29] outperforms state-of-the-art hashing methods on large-scale benchmark datasets, and is very effective for image classification with very short code lengths.
3 0.48371351 236 cvpr-2013-K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes
Author: Kaiming He, Fang Wen, Jian Sun
Abstract: In computer vision there has been increasing interest in learning hashing codes whose Hamming distance approximates the data similarity. The hashing functions play roles in both quantizing the vector space and generating similarity-preserving codes. Most existing hashing methods use hyper-planes (or kernelized hyper-planes) to quantize and encode. In this paper, we present a hashing method adopting the k-means quantization. We propose a novel Affinity-Preserving K-means algorithm which simultaneously performs k-means clustering and learns the binary indices of the quantized cells. The distance between the cells is approximated by the Hamming distance of the cell indices. We further generalize our algorithm to a product space for learning longer codes. Experiments show our method, named as K-means Hashing (KMH), outperforms various state-of-the-art hashing encoding methods.
4 0.4037874 87 cvpr-2013-Compressed Hashing
Author: Yue Lin, Rong Jin, Deng Cai, Shuicheng Yan, Xuelong Li
Abstract: Recent studies have shown that hashing methods are effective for high dimensional nearest neighbor search. A common problem shared by many existing hashing methods is that in order to achieve a satisfied performance, a large number of hash tables (i.e., long codewords) are required. To address this challenge, in this paper we propose a novel approach called Compressed Hashing by exploring the techniques of sparse coding and compressed sensing. In particular, we introduce a sparse coding scheme, based on the approximation theory of integral operator, that generate sparse representation for high dimensional vectors. We then project sparse codes into a low dimensional space by effectively exploring the Restricted Isometry Property (RIP), a key property in compressed sensing theory. Both of the theoretical analysis and the empirical studies on two large data sets show that the proposed approach is more effective than the state-of-the-art hashing algorithms.
5 0.35312709 163 cvpr-2013-Fast, Accurate Detection of 100,000 Object Classes on a Single Machine
Author: Thomas Dean, Mark A. Ruzon, Mark Segal, Jonathon Shlens, Sudheendra Vijayanarasimhan, Jay Yagnik
Abstract: Many object detection systems are constrained by the time required to convolve a target image with a bank of filters that code for different aspects of an object’s appearance, such as the presence of component parts. We exploit locality-sensitive hashing to replace the dot-product kernel operator in the convolution with a fixed number of hash-table probes that effectively sample all of the filter responses in time independent of the size of the filter bank. To show the effectiveness of the technique, we apply it to evaluate 100,000 deformable-part models requiring over a million (part) filters on multiple scales of a target image in less than 20 seconds using a single multi-core processor with 20GB of RAM. This represents a speed-up of approximately 20,000 times— four orders of magnitude— when compared withperforming the convolutions explicitly on the same hardware. While mean average precision over the full set of 100,000 object classes is around 0.16 due in large part to the challenges in gathering training data and collecting ground truth for so many classes, we achieve a mAP of at least 0.20 on a third of the classes and 0.30 or better on about 20% of the classes.
6 0.26031339 249 cvpr-2013-Learning Compact Binary Codes for Visual Tracking
7 0.18925411 69 cvpr-2013-Boosting Binary Keypoint Descriptors
8 0.17111211 319 cvpr-2013-Optimized Product Quantization for Approximate Nearest Neighbor Search
9 0.16492991 79 cvpr-2013-Cartesian K-Means
10 0.15789159 246 cvpr-2013-Learning Binary Codes for High-Dimensional Data Using Bilinear Projections
11 0.11192923 189 cvpr-2013-Graph-Based Discriminative Learning for Location Recognition
12 0.10971431 403 cvpr-2013-Sparse Output Coding for Large-Scale Visual Recognition
13 0.10468608 343 cvpr-2013-Query Adaptive Similarity for Large Scale Object Retrieval
14 0.086736754 293 cvpr-2013-Multi-attribute Queries: To Merge or Not to Merge?
15 0.082297929 260 cvpr-2013-Learning and Calibrating Per-Location Classifiers for Visual Place Recognition
16 0.064735256 309 cvpr-2013-Nonparametric Scene Parsing with Adaptive Feature Relevance and Semantic Context
17 0.063092887 456 cvpr-2013-Visual Place Recognition with Repetitive Structures
18 0.059787646 82 cvpr-2013-Class Generative Models Based on Feature Regression for Pose Estimation of Object Categories
19 0.05834759 375 cvpr-2013-Saliency Detection via Graph-Based Manifold Ranking
20 0.05639419 151 cvpr-2013-Event Retrieval in Large Video Collections with Circulant Temporal Encoding
topicId topicWeight
[(0, 0.116), (1, -0.05), (2, -0.037), (3, 0.052), (4, 0.122), (5, 0.026), (6, -0.091), (7, -0.256), (8, -0.315), (9, -0.09), (10, -0.341), (11, 0.015), (12, 0.084), (13, 0.278), (14, 0.033), (15, 0.152), (16, 0.079), (17, 0.061), (18, -0.09), (19, 0.082), (20, -0.194), (21, -0.005), (22, -0.083), (23, 0.029), (24, -0.006), (25, -0.121), (26, 0.052), (27, -0.049), (28, 0.007), (29, 0.043), (30, -0.05), (31, -0.082), (32, -0.022), (33, 0.001), (34, 0.091), (35, 0.012), (36, -0.015), (37, 0.007), (38, -0.058), (39, -0.027), (40, -0.009), (41, -0.072), (42, -0.034), (43, -0.008), (44, -0.046), (45, 0.006), (46, 0.059), (47, 0.014), (48, 0.003), (49, 0.028)]
simIndex simValue paperId paperTitle
same-paper 1 0.96672487 63 cvpr-2013-Binary Code Ranking with Weighted Hamming Distance
Author: Lei Zhang, Yongdong Zhang, Jinhu Tang, Ke Lu, Qi Tian
Abstract: Binary hashing has been widely used for efficient similarity search due to its query and storage efficiency. In most existing binary hashing methods, the high-dimensional data are embedded into Hamming space and the distance or similarity of two points are approximated by the Hamming distance between their binary codes. The Hamming distance calculation is efficient, however, in practice, there are often lots of results sharing the same Hamming distance to a query, which makes this distance measure ambiguous and poses a critical issue for similarity search where ranking is important. In this paper, we propose a weighted Hamming distance ranking algorithm (WhRank) to rank the binary codes of hashing methods. By assigning different bit-level weights to different hash bits, the returned binary codes are ranked at a finer-grained binary code level. We give an algorithm to learn the data-adaptive and query-sensitive weight for each hash bit. Evaluations on two large-scale image data sets demonstrate the efficacy of our weighted Hamming distance for binary code ranking.
2 0.86116076 236 cvpr-2013-K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes
Author: Kaiming He, Fang Wen, Jian Sun
Abstract: In computer vision there has been increasing interest in learning hashing codes whose Hamming distance approximates the data similarity. The hashing functions play roles in both quantizing the vector space and generating similarity-preserving codes. Most existing hashing methods use hyper-planes (or kernelized hyper-planes) to quantize and encode. In this paper, we present a hashing method adopting the k-means quantization. We propose a novel Affinity-Preserving K-means algorithm which simultaneously performs k-means clustering and learns the binary indices of the quantized cells. The distance between the cells is approximated by the Hamming distance of the cell indices. We further generalize our algorithm to a product space for learning longer codes. Experiments show our method, named as K-means Hashing (KMH), outperforms various state-of-the-art hashing encoding methods.
3 0.85812736 87 cvpr-2013-Compressed Hashing
Author: Yue Lin, Rong Jin, Deng Cai, Shuicheng Yan, Xuelong Li
Abstract: Recent studies have shown that hashing methods are effective for high dimensional nearest neighbor search. A common problem shared by many existing hashing methods is that in order to achieve a satisfied performance, a large number of hash tables (i.e., long codewords) are required. To address this challenge, in this paper we propose a novel approach called Compressed Hashing by exploring the techniques of sparse coding and compressed sensing. In particular, we introduce a sparse coding scheme, based on the approximation theory of integral operator, that generate sparse representation for high dimensional vectors. We then project sparse codes into a low dimensional space by effectively exploring the Restricted Isometry Property (RIP), a key property in compressed sensing theory. Both of the theoretical analysis and the empirical studies on two large data sets show that the proposed approach is more effective than the state-of-the-art hashing algorithms.
4 0.82656986 223 cvpr-2013-Inductive Hashing on Manifolds
Author: Fumin Shen, Chunhua Shen, Qinfeng Shi, Anton van_den_Hengel, Zhenmin Tang
Abstract: Learning based hashing methods have attracted considerable attention due to their ability to greatly increase the scale at which existing algorithms may operate. Most of these methods are designed to generate binary codes that preserve the Euclidean distance in the original space. Manifold learning techniques, in contrast, are better able to model the intrinsic structure embedded in the original highdimensional data. The complexity of these models, and the problems with out-of-sample data, havepreviously rendered them unsuitable for application to large-scale embedding, however. In this work, we consider how to learn compact binary embeddings on their intrinsic manifolds. In order to address the above-mentioned difficulties, we describe an efficient, inductive solution to the out-of-sample data problem, and a process by which non-parametric manifold learning may be used as the basis of a hashing method. Our proposed approach thus allows the development of a range of new hashing techniques exploiting the flexibility of the wide variety of manifold learning approaches available. We particularly show that hashing on the basis of t-SNE [29] outperforms state-of-the-art hashing methods on large-scale benchmark datasets, and is very effective for image classification with very short code lengths.
5 0.53076041 319 cvpr-2013-Optimized Product Quantization for Approximate Nearest Neighbor Search
Author: Tiezheng Ge, Kaiming He, Qifa Ke, Jian Sun
Abstract: Product quantization is an effective vector quantization approach to compactly encode high-dimensional vectors for fast approximate nearest neighbor (ANN) search. The essence of product quantization is to decompose the original high-dimensional space into the Cartesian product of a finite number of low-dimensional subspaces that are then quantized separately. Optimal space decomposition is important for the performance of ANN search, but still remains unaddressed. In this paper, we optimize product quantization by minimizing quantization distortions w.r.t. the space decomposition and the quantization codebooks. We present two novel methods for optimization: a nonparametric method that alternatively solves two smaller sub-problems, and a parametric method that is guaranteed to achieve the optimal solution if the input data follows some Gaussian distribution. We show by experiments that our optimized approach substantially improves the accuracy of product quantization for ANN search.
6 0.49980116 79 cvpr-2013-Cartesian K-Means
7 0.47029543 163 cvpr-2013-Fast, Accurate Detection of 100,000 Object Classes on a Single Machine
8 0.47003454 249 cvpr-2013-Learning Compact Binary Codes for Visual Tracking
9 0.46809909 69 cvpr-2013-Boosting Binary Keypoint Descriptors
10 0.4545958 246 cvpr-2013-Learning Binary Codes for High-Dimensional Data Using Bilinear Projections
11 0.30136243 403 cvpr-2013-Sparse Output Coding for Large-Scale Visual Recognition
12 0.30037433 343 cvpr-2013-Query Adaptive Similarity for Large Scale Object Retrieval
13 0.23067079 293 cvpr-2013-Multi-attribute Queries: To Merge or Not to Merge?
14 0.21313721 189 cvpr-2013-Graph-Based Discriminative Learning for Location Recognition
15 0.18954696 260 cvpr-2013-Learning and Calibrating Per-Location Classifiers for Visual Place Recognition
16 0.189022 320 cvpr-2013-Optimizing 1-Nearest Prototype Classifiers
17 0.18192333 126 cvpr-2013-Diffusion Processes for Retrieval Revisited
18 0.18018471 157 cvpr-2013-Exploring Implicit Image Statistics for Visual Representativeness Modeling
19 0.17463696 353 cvpr-2013-Relative Hidden Markov Models for Evaluating Motion Skill
20 0.16532113 346 cvpr-2013-Real-Time No-Reference Image Quality Assessment Based on Filter Learning
topicId topicWeight
[(10, 0.113), (16, 0.038), (26, 0.023), (28, 0.013), (33, 0.19), (36, 0.111), (52, 0.181), (67, 0.101), (69, 0.049), (70, 0.038), (87, 0.044)]
simIndex simValue paperId paperTitle
same-paper 1 0.81246907 63 cvpr-2013-Binary Code Ranking with Weighted Hamming Distance
Author: Lei Zhang, Yongdong Zhang, Jinhu Tang, Ke Lu, Qi Tian
Abstract: Binary hashing has been widely used for efficient similarity search due to its query and storage efficiency. In most existing binary hashing methods, the high-dimensional data are embedded into Hamming space and the distance or similarity of two points are approximated by the Hamming distance between their binary codes. The Hamming distance calculation is efficient, however, in practice, there are often lots of results sharing the same Hamming distance to a query, which makes this distance measure ambiguous and poses a critical issue for similarity search where ranking is important. In this paper, we propose a weighted Hamming distance ranking algorithm (WhRank) to rank the binary codes of hashing methods. By assigning different bit-level weights to different hash bits, the returned binary codes are ranked at a finer-grained binary code level. We give an algorithm to learn the data-adaptive and query-sensitive weight for each hash bit. Evaluations on two large-scale image data sets demonstrate the efficacy of our weighted Hamming distance for binary code ranking.
2 0.77542895 413 cvpr-2013-Story-Driven Summarization for Egocentric Video
Author: Zheng Lu, Kristen Grauman
Abstract: We present a video summarization approach that discovers the story of an egocentric video. Given a long input video, our method selects a short chain of video subshots depicting the essential events. Inspired by work in text analysis that links news articles over time, we define a randomwalk based metric of influence between subshots that reflects how visual objects contribute to the progression of events. Using this influence metric, we define an objective for the optimal k-subshot summary. Whereas traditional methods optimize a summary ’s diversity or representativeness, ours explicitly accounts for how one sub-event “leads to ” another—which, critically, captures event connectivity beyond simple object co-occurrence. As a result, our summaries provide a better sense of story. We apply our approach to over 12 hours of daily activity video taken from 23 unique camera wearers, and systematically evaluate its quality compared to multiple baselines with 34 human subjects.
Author: Xiaolong Wang, Liang Lin, Lichao Huang, Shuicheng Yan
Abstract: This paper proposes a reconfigurable model to recognize and detect multiclass (or multiview) objects with large variation in appearance. Compared with well acknowledged hierarchical models, we study two advanced capabilities in hierarchy for object modeling: (i) “switch” variables(i.e. or-nodes) for specifying alternative compositions, and (ii) making local classifiers (i.e. leaf-nodes) shared among different classes. These capabilities enable us to account well for structural variabilities while preserving the model compact. Our model, in the form of an And-Or Graph, comprises four layers: a batch of leaf-nodes with collaborative edges in bottom for localizing object parts; the or-nodes over bottom to activate their children leaf-nodes; the andnodes to classify objects as a whole; one root-node on the top for switching multiclass classification, which is also an or-node. For model training, we present an EM-type algorithm, namely dynamical structural optimization (DSO), to iteratively determine the structural configuration, (e.g., leaf-node generation associated with their parent or-nodes and shared across other classes), along with optimizing multi-layer parameters. The proposed method is valid on challenging databases, e.g., PASCAL VOC2007and UIUCPeople, and it achieves state-of-the-arts performance.
4 0.7720716 102 cvpr-2013-Decoding, Calibration and Rectification for Lenselet-Based Plenoptic Cameras
Author: Donald G. Dansereau, Oscar Pizarro, Stefan B. Williams
Abstract: Plenoptic cameras are gaining attention for their unique light gathering and post-capture processing capabilities. We describe a decoding, calibration and rectification procedurefor lenselet-basedplenoptic cameras appropriatefor a range of computer vision applications. We derive a novel physically based 4D intrinsic matrix relating each recorded pixel to its corresponding ray in 3D space. We further propose a radial distortion model and a practical objective function based on ray reprojection. Our 15-parameter camera model is of much lower dimensionality than camera array models, and more closely represents the physics of lenselet-based cameras. Results include calibration of a commercially available camera using three calibration grid sizes over five datasets. Typical RMS ray reprojection errors are 0.0628, 0.105 and 0.363 mm for 3.61, 7.22 and 35.1 mm calibration grids, respectively. Rectification examples include calibration targets and real-world imagery.
5 0.76621395 236 cvpr-2013-K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes
Author: Kaiming He, Fang Wen, Jian Sun
Abstract: In computer vision there has been increasing interest in learning hashing codes whose Hamming distance approximates the data similarity. The hashing functions play roles in both quantizing the vector space and generating similarity-preserving codes. Most existing hashing methods use hyper-planes (or kernelized hyper-planes) to quantize and encode. In this paper, we present a hashing method adopting the k-means quantization. We propose a novel Affinity-Preserving K-means algorithm which simultaneously performs k-means clustering and learns the binary indices of the quantized cells. The distance between the cells is approximated by the Hamming distance of the cell indices. We further generalize our algorithm to a product space for learning longer codes. Experiments show our method, named as K-means Hashing (KMH), outperforms various state-of-the-art hashing encoding methods.
6 0.75716132 319 cvpr-2013-Optimized Product Quantization for Approximate Nearest Neighbor Search
7 0.74550647 288 cvpr-2013-Modeling Mutual Visibility Relationship in Pedestrian Detection
8 0.74163437 267 cvpr-2013-Least Soft-Threshold Squares Tracking
9 0.73838717 79 cvpr-2013-Cartesian K-Means
10 0.73730499 248 cvpr-2013-Learning Collections of Part Models for Object Recognition
11 0.73728156 339 cvpr-2013-Probabilistic Graphlet Cut: Exploiting Spatial Structure Cue for Weakly Supervised Image Segmentation
12 0.73698533 2 cvpr-2013-3D Pictorial Structures for Multiple View Articulated Pose Estimation
13 0.73583907 179 cvpr-2013-From N to N+1: Multiclass Transfer Incremental Learning
14 0.73449051 363 cvpr-2013-Robust Multi-resolution Pedestrian Detection in Traffic Scenes
15 0.73379409 110 cvpr-2013-Dense Object Reconstruction with Semantic Priors
16 0.73322403 122 cvpr-2013-Detection Evolution with Multi-order Contextual Co-occurrence
17 0.73287398 414 cvpr-2013-Structure Preserving Object Tracking
18 0.73166633 119 cvpr-2013-Detecting and Aligning Faces by Image Retrieval
19 0.73129618 60 cvpr-2013-Beyond Physical Connections: Tree Models in Human Pose Estimation
20 0.73076957 225 cvpr-2013-Integrating Grammar and Segmentation for Human Pose Estimation