cvpr cvpr2013 cvpr2013-87 knowledge-graph by maker-knowledge-mining
Source: pdf
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.
Reference: text
sentIndex sentText sentNum sentScore
1 cn Abstract Recent studies have shown that hashing methods are effective for high dimensional nearest neighbor search. [sent-17, score-0.928]
2 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. [sent-18, score-0.784]
3 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. [sent-21, score-0.476]
4 In particular, we introduce a sparse coding scheme, based on the approximation theory of integral operator, that generate sparse representation for high dimensional vectors. [sent-22, score-0.565]
5 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. [sent-23, score-0.723]
6 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. [sent-24, score-0.729]
7 Given the intrinsic difficulty of exact nearest neighbor search, many hashing algorithms are proposed for Approximate Nearest Neighbor (ANN) search [5, 6, 21]. [sent-27, score-0.859]
8 The key idea of these approaches is to generate binary codewords for high dimensional data points that preserve the similarity between data points. [sent-28, score-0.354]
9 Many hashing algorithms found their theoretic root in random projection, which is proved to be an effective method for preserving pairwise distances. [sent-29, score-0.774]
10 One problem with most random projection theories is that, in order to achieve a small error in distance preservation, a large number of random projections are required. [sent-30, score-0.241]
11 Even more disturbingly, the number of required random projections depends on the size of data set, making it less attractive for large databases. [sent-31, score-0.116]
12 For example, according to Jonson Lindenstrauss Theorem [10], to preserve the pairwise distances for a database of n data points, the number of needed random projections is O(ln n/? [sent-32, score-0.279]
13 Therefore, it is not a surprise the random projection based hashing methods do not perform well for short codes. [sent-35, score-0.802]
14 To address this problem, several learning based hashing methods are proposed. [sent-36, score-0.677]
15 Most of these algorithms learn the binary codes by exploiting the spectral properties of the data affinity matrix. [sent-37, score-0.246]
16 In spite of the success for relative small codes, these learning based approaches often fail to make significant improvement as code length increases [11]. [sent-38, score-0.092]
17 In this paper, we propose a novel approach called Compressed Hashing to address this challenge by exploring the techniques of sparse coding [8] and compressed sensing [7]. [sent-39, score-0.529]
18 The main idea is based on the Restricted Isometry Property (RIP) [3], which states that for any sparse vector, the random projection is able to preserve the Euclidean distances between high dimensional vectors with an overwhelming probability. [sent-40, score-0.558]
19 The probability in JL theorem is related to each vector, namely for any vector, there is a chance for the property to be failed. [sent-42, score-0.116]
20 As a result, to preserve the pairwise distance for all the data points, the number of random projections has to be dependent on the size ofthe database. [sent-43, score-0.248]
21 In contrast, the probability in RIP condition is related to the random matrix, namely nearly all random matrix generated by iid Gaussian will be able to preserve Euclidean distance for all 444444446 data points. [sent-44, score-0.193]
22 Because of this difference, the performance guarantee delivered by RIP applies to all vectors, making the number of random projections independent from the size of the database. [sent-45, score-0.116]
23 Note that the RIP only applies to the sparse vectors. [sent-46, score-0.12]
24 In order to meet the sparse requirement in RIP, we use a sparse coding scheme similar to [14] that generates compact sparse codes for high dimensional vectors. [sent-47, score-0.79]
25 The sparse codes are generated based on the approximation theory of integral operator and well preserve the relationship between vectors. [sent-48, score-0.523]
26 Given the sparse codes, we then explore the theory of compressed sensing [7] to project the sparse codes into a low dimensional space, and generate the hash codes based on the low dimensional projection. [sent-49, score-1.144]
27 Related Work Most hashing methods can be classified into two categories: the random projection based methods and the learning based methods. [sent-51, score-0.802]
28 The most notable approach for random projection based methods is Locality Sensitive Hashing [5, 1], which offers a sub-linear time search by trying to hash similar data points into the same entry of a hash table(s). [sent-52, score-0.352]
29 One drawback of many LSH approaches is that in order to preserve the locality of the data points, they have to generate long codewords, leading to large storage space and high computational cost. [sent-53, score-0.207]
30 Both entropy-based LSH approach [16] and Multi-Probe LSH [15] are proposed to reduce the storage limitation at the sacrifice of increasing the query time. [sent-54, score-0.074]
31 A common problem of random projection based hashing algorithms is that in order to achieve a satisfied performance, they require a large number of hash tables and long codewords. [sent-56, score-0.932]
32 However, the learning based hashing algorithms often work well for short codewords but fail to make significant improvement as code length increases [11]. [sent-59, score-0.846]
33 Compressed Hashing In this section, we will first describe the sparse coding scheme, which is based on the kernel density estimation, followed by the approach of projecting sparse vectors into low dimensional space using compressed sensing theory. [sent-61, score-0.769]
34 Sparse Coding using RBF Kernel Our goal is to create the sparse representations that preserve the relationship between the data points. [sent-64, score-0.223]
35 t aAbasssue,m we xa aen xd xb are tiws ao vdeactato points idn ? [sent-70, score-0.375]
36 oWfe u a(dxd)re isss Nthi,s w problem by exploring fth teh eco dnatcaebntarsaetio Dn. [sent-88, score-0.05]
37 ral operator L th : H no r→m dHe as L[f](·) =N1i? [sent-96, score-0.056]
38 H Based on the concentration inequality for integral operator, we can approximate L by a low rank operator, leading to a compact representation for data points in D. [sent-99, score-0.227]
39 ximply use random samgpMelionnreger o spr dekc-i fmrfoicemaalnlsy D ,1. [sent-112, score-0.045]
40 e x mthpel ya uncsheo rra points [a1m4]and we will discuss this in our experiments. [sent-117, score-0.048]
41 i) (3) 1The anchor points can be set to the cluster centers returned by the k-means algorithm with cluster number m. [sent-124, score-0.163]
42 444444557 As a result, we obtain a compact representation ? [sent-126, score-0.058]
43 h a pcorombapabciltit rye,p freors any xa aun(dx xb, |u? [sent-136, score-0.162]
44 be the integral operator constructed based on m ancho? [sent-151, score-0.107]
45 With a probability 1 δ, for any xa and xb, we have − ? [sent-154, score-0.162]
46 1 ball, to preserve pairwise distance, it is sufficient to keep the largest entries in vectors. [sent-200, score-0.158]
47 More specifically, let hs : Rm → Rm be a vector function, where the output of hs (z) ? [sent-201, score-0.078]
48 It is this reduced requirement that makes it possible to generate a small number of projections to accurately preserve the distances between the vectors. [sent-207, score-0.267]
49 (4), we are determined to keep the information of a small number of nearest anchors for each point and we get the final sparse representation of x z(x) =? [sent-209, score-0.34]
50 (x) stands for the s nearest anchors of x among anchoSr points. [sent-223, score-0.194]
51 dIts si sf important atroe snto atne cthhoatr sth oef xab aomveo sparse coding scheme is also used by Anchor Graph Hashing (AGH) [14]. [sent-224, score-0.261]
52 AGH uses this coding strategy to speed up the spectral analysis of the data while our motivation is to generate sparse codes to meet the sparse requirement in RIP. [sent-225, score-0.617]
53 In the next subsection, we show how the approximate nearest neighbor search can be effectively performed using these sparse vectors by exploring the RIP condition. [sent-226, score-0.394]
54 Approximate Sparse Random Projection Representation by Given the sparse representation ofthe data points, our next goal is to create binary codes that approximate the distances between the sparse vectors. [sent-229, score-0.511]
55 For any data point x and its sparse representation z(x) ∈ Rm generated by txhe a proposed sparse coding sonch ze(mx)e, we create a K-bits code b(x) = (b1(x), . [sent-230, score-0.421]
56 by a linear hashing method: it first projects z to a low dimensional space by K linear operators {φi ∈ Rm, i ∈ [K] }, i. [sent-234, score-0.765]
57 We first present the Restricted Isometry Property of random matrices as below. [sent-246, score-0.045]
58 1 in [2]) Assume K < m and let Φ be a random matrix of size m K whose entries are i. [sent-249, score-0.071]
59 small enough and K = cs log(m/s), where c is a constant independent of s, there exists a positive constant δs < 1such that with an overwhelming probability, we have the following inequality hold for any z ∈ Rm with hata mveo tshte s non-zero einnetrqiuesa (1 − δs)|z|22≤mK|Φ? [sent-256, score-0.096]
60 z|22≤ (1 + δs)|z|22 Below, we present the property of the random projection for sparse vectors, which follows directly from the Theorem 2 and the inequality in Eq. [sent-257, score-0.33]
61 at Arisxs uwmheos Ke en < 1Φ such tha−t w zit)h| an overwhelming probability, for any two vectors |z1| 1, |z2 | 1 1, we have ≤ L ≥ ? [sent-262, score-0.091]
62 2 norm of the difference between two sparse vectors, which justify the random projection approach for approximating the difference between sparse vectors in a ? [sent-265, score-0.405]
63 Computational Complexity Analysis Given N data points with the dimensionality d, the computational complexity of Compressed Hashing in the training stage is as follows: 1. [sent-270, score-0.048]
64 O(Nm(d + s)) : Generate sparse representation for data points (Step 2 in Alg. [sent-274, score-0.194]
65 O(NK) : Compute the hashing codes with respect to the median values (Step 4 in Alg. [sent-280, score-0.865]
66 In the testing stage, given a query point, Compressed Hashing needs O(m(d s)) to compress the query point into a sparse representation and needs O(mK) to obtain the binary codes. [sent-283, score-0.274]
67 Experiments In this section, we evaluate our Compressed Hashing (CH) algorithm on the high dimensional nearest neighbor search problem. [sent-285, score-0.247]
68 m 2: Generate sparse representation Z ∈ Rn× for data points in D, based on the anchor points in V , using Eq. [sent-291, score-0.357]
69 3: Generate linear projections Φ ∈ Rm×K by drawing Φj,k from N(0, 1/K) independently. [sent-293, score-0.098]
70 4: Compute the hashing code Y by thresholding Yi,? [sent-296, score-0.737]
71 i ∈ Rd; The random projection matrix: Φ ∈ Rm×K ; Binary hashing codes for the training samples: Y ∈ {0, 1}N×K Both data sets contain one million image features. [sent-300, score-0.986]
72 The data sets are publicly For each data set, we randomly select 10k data points as the queries and use the remaining to form the gallery database. [sent-302, score-0.071]
73 We use the same criterion as in [19], that a returned point is considered to be a true neighbor if it lies in the top 2 percentile points closest (measured by the Euclidian distance in the original space) to the query. [sent-303, score-0.115]
74 For each query, all the data points in the database available2. [sent-304, score-0.048]
75 We implement LSH, PCAH by ourselves, and use the codes provided by the authors for the algorithms KLSH, SIKH, SpH, USPLH and AGH. [sent-315, score-0.184]
76 To run KLSH, we use the Gaussian kernel and sample 300 training points to form the empirical kernel map. [sent-316, score-0.132]
77 Both our CH method and the AGH need an anchor-based sparse coding step and we use the exactly same strategy. [sent-320, score-0.215]
78 There are three parameters: the number of anchor points (m), the number of iterations (p) in k-means and the number of nearest anchors in sparse coding (s). [sent-321, score-0.572]
79 For both methods, the Gaussian kernel width parameter h is empirically3 set to be 0. [sent-323, score-0.042]
80 We can see that the random projection based algorithms (LSH, SIKH and KLSH) have a low MAP when the code length is short. [sent-329, score-0.24]
81 As the code length increases, the performances 3We estimate h by randomly choose 3000 samples and let h equal to the average of the pairwise distances. [sent-330, score-0.121]
82 On the other hand, the learning based algorithms, such as SpH and PCAH, have a high MAP when the code length is short. [sent-332, score-0.092]
83 However, they fail to make significant improvements as the code length increases. [sent-333, score-0.092]
84 Particularly, the performance of PCAH decreases as the code length increases. [sent-334, score-0.092]
85 This is consistent with previous work [19] and is probably because that most of the data variance is contained in the top few principal directions so that the later bits are calculated using the low-variance projections, leading to the poorly discriminative codes [19]. [sent-335, score-0.187]
86 By combining the techniques of sparse coding and com- iPronces0 . [sent-336, score-0.215]
87 The precision-recall curves of all algorithms on SIFT1M and GIST1M data sets for the codes of 64 bits. [sent-341, score-0.207]
88 444454880 pressed sensing, we successfully preserve the information in the low dimensional space. [sent-342, score-0.191]
89 As a result, the pro- posed CH method achieves satisfied performances on both data sets and almost outperforms its competitors for all code lengths. [sent-343, score-0.113]
90 Figure 2 presents the precisionrecall curves of all the algorithms on two data sets with the code of 64 bits. [sent-344, score-0.106]
91 The random projection based algorithms are relatively efficient, especially the LSH. [sent-347, score-0.148]
92 The proposed CH algorithm uses similar but less training time than AGH due to its fast process in converting the sparse vectors to binary codes. [sent-348, score-0.188]
93 The most expensive part in CH is to obtain the sparse representation for the query point. [sent-354, score-0.196]
94 Conclusion In this paper, we have developed a hashing algorithm for high dimensional nearest neighbor search by com- bining the techniques of sparse coding and compressed sensing. [sent-356, score-1.35]
95 Empirical studies on the large data sets show that the proposed algorithm scales well to data size and significantly outperforms the state-of-the-art hashing methods in retrieval accuracy. [sent-358, score-0.729]
96 In the future, we plan to further explore anchors selection methods that are both effective and computationally efficient for large data sets. [sent-359, score-0.127]
97 Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. [sent-364, score-0.859]
98 The restricted isometry property and its implications for compressed sensing. [sent-369, score-0.382]
99 Optimally sparse representation in general (non-orthogonal) dictionaries via ? [sent-404, score-0.146]
100 – [14] [15] [16] [17] [18] [19] [20] [21] Supervised hashing with kernels. [sent-441, score-0.677]
wordName wordTfidf (topN-words)
[('hashing', 0.677), ('rip', 0.232), ('compressed', 0.211), ('xb', 0.165), ('xa', 0.162), ('codes', 0.161), ('lsh', 0.149), ('agh', 0.133), ('anchors', 0.127), ('sparse', 0.12), ('anchor', 0.115), ('preserve', 0.103), ('klsh', 0.103), ('pcah', 0.1), ('isometry', 0.1), ('coding', 0.095), ('dimensional', 0.088), ('projection', 0.08), ('rm', 0.078), ('sikh', 0.077), ('usplh', 0.077), ('hash', 0.077), ('theorem', 0.076), ('sph', 0.073), ('projections', 0.071), ('neighbor', 0.067), ('nearest', 0.067), ('code', 0.06), ('operator', 0.056), ('codewords', 0.054), ('sensing', 0.053), ('jonson', 0.051), ('lindenstrauss', 0.051), ('pnmd', 0.051), ('xuelong', 0.051), ('integral', 0.051), ('overwhelming', 0.051), ('query', 0.05), ('exploring', 0.05), ('points', 0.048), ('ch', 0.047), ('locality', 0.047), ('random', 0.045), ('inequality', 0.045), ('hilbert', 0.044), ('kernel', 0.042), ('mk', 0.04), ('vectors', 0.04), ('property', 0.04), ('hs', 0.039), ('xn', 0.038), ('spectral', 0.034), ('rbf', 0.033), ('generate', 0.033), ('length', 0.032), ('compact', 0.032), ('theory', 0.032), ('restricted', 0.031), ('distances', 0.031), ('china', 0.03), ('lemma', 0.03), ('cand', 0.03), ('reproducing', 0.03), ('satisfied', 0.03), ('studies', 0.029), ('requirement', 0.029), ('sgn', 0.029), ('pairwise', 0.029), ('jl', 0.028), ('binary', 0.028), ('sequential', 0.028), ('kernelized', 0.028), ('singapore', 0.027), ('drawing', 0.027), ('median', 0.027), ('sc', 0.026), ('entries', 0.026), ('bits', 0.026), ('representation', 0.026), ('search', 0.025), ('meet', 0.025), ('pages', 0.025), ('approximate', 0.025), ('storage', 0.024), ('ball', 0.024), ('algorithms', 0.023), ('sets', 0.023), ('xy', 0.023), ('wait', 0.023), ('tdheefin', 0.023), ('annosearch', 0.023), ('hpa', 0.023), ('vldb', 0.023), ('itnhdee', 0.023), ('aica', 0.023), ('approx', 0.023), ('atne', 0.023), ('atroe', 0.023), ('clet', 0.023), ('cxtor', 0.023)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000011 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.
2 0.4939959 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.48213521 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 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.
5 0.28349823 249 cvpr-2013-Learning Compact Binary Codes for Visual Tracking
Author: Xi Li, Chunhua Shen, Anthony Dick, Anton van_den_Hengel
Abstract: A key problem in visual tracking is to represent the appearance of an object in a way that is robust to visual changes. To attain this robustness, increasingly complex models are used to capture appearance variations. However, such models can be difficult to maintain accurately and efficiently. In this paper, we propose a visual tracker in which objects are represented by compact and discriminative binary codes. This representation can be processed very efficiently, and is capable of effectively fusing information from multiple cues. An incremental discriminative learner is then used to construct an appearance model that optimally separates the object from its surrounds. Furthermore, we design a hypergraph propagation method to capture the contextual information on samples, which further improves the tracking accuracy. Experimental results on challenging videos demonstrate the effectiveness and robustness of the proposed tracker.
6 0.23513021 163 cvpr-2013-Fast, Accurate Detection of 100,000 Object Classes on a Single Machine
7 0.17691842 246 cvpr-2013-Learning Binary Codes for High-Dimensional Data Using Bilinear Projections
8 0.16260296 319 cvpr-2013-Optimized Product Quantization for Approximate Nearest Neighbor Search
9 0.10309268 69 cvpr-2013-Boosting Binary Keypoint Descriptors
10 0.098338448 79 cvpr-2013-Cartesian K-Means
11 0.095129862 110 cvpr-2013-Dense Object Reconstruction with Semantic Priors
12 0.084559605 189 cvpr-2013-Graph-Based Discriminative Learning for Location Recognition
13 0.081696369 178 cvpr-2013-From Local Similarity to Global Coding: An Application to Image Classification
14 0.07183601 422 cvpr-2013-Tag Taxonomy Aware Dictionary Learning for Region Tagging
15 0.071829692 53 cvpr-2013-BFO Meets HOG: Feature Extraction Based on Histograms of Oriented p.d.f. Gradients for Image Classification
16 0.068396635 304 cvpr-2013-Multipath Sparse Coding Using Hierarchical Matching Pursuit
17 0.065094784 164 cvpr-2013-Fast Convolutional Sparse Coding
18 0.062097691 442 cvpr-2013-Transfer Sparse Coding for Robust Image Representation
19 0.061982341 204 cvpr-2013-Histograms of Sparse Codes for Object Detection
20 0.061646778 343 cvpr-2013-Query Adaptive Similarity for Large Scale Object Retrieval
topicId topicWeight
[(0, 0.141), (1, -0.036), (2, -0.073), (3, 0.087), (4, 0.088), (5, 0.007), (6, -0.071), (7, -0.26), (8, -0.303), (9, -0.097), (10, -0.306), (11, 0.002), (12, 0.039), (13, 0.236), (14, 0.032), (15, 0.165), (16, 0.038), (17, 0.065), (18, -0.08), (19, 0.095), (20, -0.205), (21, 0.028), (22, -0.057), (23, -0.011), (24, 0.013), (25, -0.08), (26, 0.01), (27, -0.015), (28, -0.0), (29, 0.028), (30, -0.078), (31, -0.055), (32, -0.002), (33, -0.012), (34, 0.088), (35, 0.004), (36, -0.018), (37, 0.038), (38, 0.013), (39, -0.031), (40, -0.027), (41, -0.054), (42, -0.03), (43, -0.033), (44, 0.003), (45, 0.014), (46, 0.063), (47, 0.017), (48, -0.057), (49, 0.025)]
simIndex simValue paperId paperTitle
1 0.9361347 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.
same-paper 2 0.92953056 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.
3 0.87271041 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.
4 0.86948574 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.
5 0.55284423 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.52364469 249 cvpr-2013-Learning Compact Binary Codes for Visual Tracking
7 0.51858681 79 cvpr-2013-Cartesian K-Means
8 0.51118368 69 cvpr-2013-Boosting Binary Keypoint Descriptors
9 0.47894999 163 cvpr-2013-Fast, Accurate Detection of 100,000 Object Classes on a Single Machine
10 0.47320148 246 cvpr-2013-Learning Binary Codes for High-Dimensional Data Using Bilinear Projections
11 0.40395111 403 cvpr-2013-Sparse Output Coding for Large-Scale Visual Recognition
12 0.25123134 343 cvpr-2013-Query Adaptive Similarity for Large Scale Object Retrieval
13 0.24863133 442 cvpr-2013-Transfer Sparse Coding for Robust Image Representation
14 0.2479438 164 cvpr-2013-Fast Convolutional Sparse Coding
15 0.24611504 191 cvpr-2013-Graph-Laplacian PCA: Closed-Form Solution and Robustness
16 0.23441963 7 cvpr-2013-A Divide-and-Conquer Method for Scalable Low-Rank Latent Matrix Pursuit
17 0.23247591 320 cvpr-2013-Optimizing 1-Nearest Prototype Classifiers
18 0.22975779 178 cvpr-2013-From Local Similarity to Global Coding: An Application to Image Classification
19 0.22681694 404 cvpr-2013-Sparse Quantization for Patch Description
20 0.21763305 304 cvpr-2013-Multipath Sparse Coding Using Hierarchical Matching Pursuit
topicId topicWeight
[(10, 0.073), (16, 0.029), (26, 0.033), (33, 0.258), (36, 0.088), (67, 0.073), (69, 0.05), (70, 0.236), (87, 0.054)]
simIndex simValue paperId paperTitle
1 0.84412944 174 cvpr-2013-Fine-Grained Crowdsourcing for Fine-Grained Recognition
Author: Jia Deng, Jonathan Krause, Li Fei-Fei
Abstract: Fine-grained recognition concerns categorization at sub-ordinate levels, where the distinction between object classes is highly local. Compared to basic level recognition, fine-grained categorization can be more challenging as there are in general less data and fewer discriminative features. This necessitates the use of stronger prior for feature selection. In this work, we include humans in the loop to help computers select discriminative features. We introduce a novel online game called “Bubbles ” that reveals discriminative features humans use. The player’s goal is to identify the category of a heavily blurred image. During the game, the player can choose to reveal full details of circular regions ( “bubbles”), with a certain penalty. With proper setup the game generates discriminative bubbles with assured quality. We next propose the “BubbleBank” algorithm that uses the human selected bubbles to improve machine recognition performance. Experiments demonstrate that our approach yields large improvements over the previous state of the art on challenging benchmarks.
same-paper 2 0.8201977 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.
3 0.81900501 23 cvpr-2013-A Practical Rank-Constrained Eight-Point Algorithm for Fundamental Matrix Estimation
Author: Yinqiang Zheng, Shigeki Sugimoto, Masatoshi Okutomi
Abstract: Due to its simplicity, the eight-point algorithm has been widely used in fundamental matrix estimation. Unfortunately, the rank-2 constraint of a fundamental matrix is enforced via a posterior rank correction step, thus leading to non-optimal solutions to the original problem. To address this drawback, existing algorithms need to solve either a very high order polynomial or a sequence of convex relaxation problems, both of which are computationally ineffective and numerically unstable. In this work, we present a new rank-2 constrained eight-point algorithm, which directly incorporates the rank-2 constraint in the minimization process. To avoid singularities, we propose to solve seven subproblems and retrieve their globally optimal solutions by using tailored polynomial system solvers. Our proposed method is noniterative, computationally efficient and numerically stable. Experiment results have verified its superiority over existing algebraic error based algorithms in terms of accuracy, as well as its advantages when used to initialize geometric error based algorithms.
4 0.81698078 466 cvpr-2013-Whitened Expectation Propagation: Non-Lambertian Shape from Shading and Shadow
Author: Brian Potetz, Mohammadreza Hajiarbabi
Abstract: For problems over continuous random variables, MRFs with large cliques pose a challenge in probabilistic inference. Difficulties in performing optimization efficiently have limited the probabilistic models explored in computer vision and other fields. One inference technique that handles large cliques well is Expectation Propagation. EP offers run times independent of clique size, which instead depend only on the rank, or intrinsic dimensionality, of potentials. This property would be highly advantageous in computer vision. Unfortunately, for grid-shaped models common in vision, traditional Gaussian EP requires quadratic space and cubic time in the number of pixels. Here, we propose a variation of EP that exploits regularities in natural scene statistics to achieve run times that are linear in both number of pixels and clique size. We test these methods on shape from shading, and we demonstrate strong performance not only for Lambertian surfaces, but also on arbitrary surface reflectance and lighting arrangements, which requires highly non-Gaussian potentials. Finally, we use large, non-local cliques to exploit cast shadow, which is traditionally ignored in shape from shading.
5 0.80763817 150 cvpr-2013-Event Recognition in Videos by Learning from Heterogeneous Web Sources
Author: Lin Chen, Lixin Duan, Dong Xu
Abstract: In this work, we propose to leverage a large number of loosely labeled web videos (e.g., from YouTube) and web images (e.g., from Google/Bing image search) for visual event recognition in consumer videos without requiring any labeled consumer videos. We formulate this task as a new multi-domain adaptation problem with heterogeneous sources, in which the samples from different source domains can be represented by different types of features with different dimensions (e.g., the SIFTfeaturesfrom web images and space-time (ST) features from web videos) while the target domain samples have all types of features. To effectively cope with the heterogeneous sources where some source domains are more relevant to the target domain, we propose a new method called Multi-domain Adaptation with Heterogeneous Sources (MDA-HS) to learn an optimal target classifier, in which we simultaneously seek the optimal weights for different source domains with different types of features as well as infer the labels of unlabeled target domain data based on multiple types of features. We solve our optimization problem by using the cutting-plane algorithm based on group-based multiple kernel learning. Comprehensive experiments on two datasets demonstrate the effectiveness of MDA-HS for event recognition in consumer videos.
6 0.78219283 63 cvpr-2013-Binary Code Ranking with Weighted Hamming Distance
7 0.77907193 236 cvpr-2013-K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes
8 0.77385521 309 cvpr-2013-Nonparametric Scene Parsing with Adaptive Feature Relevance and Semantic Context
9 0.77282578 319 cvpr-2013-Optimized Product Quantization for Approximate Nearest Neighbor Search
10 0.7628957 110 cvpr-2013-Dense Object Reconstruction with Semantic Priors
11 0.76188296 179 cvpr-2013-From N to N+1: Multiclass Transfer Incremental Learning
12 0.75723851 79 cvpr-2013-Cartesian K-Means
13 0.75528079 284 cvpr-2013-Mesh Based Semantic Modelling for Indoor and Outdoor Scenes
14 0.75250953 267 cvpr-2013-Least Soft-Threshold Squares Tracking
15 0.75083768 119 cvpr-2013-Detecting and Aligning Faces by Image Retrieval
16 0.75012934 69 cvpr-2013-Boosting Binary Keypoint Descriptors
17 0.74982917 94 cvpr-2013-Context-Aware Modeling and Recognition of Activities in Video
18 0.74918967 322 cvpr-2013-PISA: Pixelwise Image Saliency by Aggregating Complementary Appearance Contrast Measures with Spatial Priors
19 0.74903822 416 cvpr-2013-Studying Relationships between Human Gaze, Description, and Computer Vision
20 0.74887669 223 cvpr-2013-Inductive Hashing on Manifolds