iccv iccv2013 iccv2013-221 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yan Xia, Kaiming He, Fang Wen, Jian Sun
Abstract: Inverted indexing is a popular non-exhaustive solution to large scale search. An inverted file is built by a quantizer such as k-means or a tree structure. It has been found that multiple inverted files, obtained by multiple independent random quantizers, are able to achieve practically good recall and speed. Instead of computing the multiple quantizers independently, we present a method that creates them jointly. Our method jointly optimizes all codewords in all quantizers. Then it assigns these codewords to the quantizers. In experiments this method shows significant improvement over various existing methods that use multiple independent quantizers. On the one-billion set of SIFT vectors, our method is faster and more accurate than a recent state-of-the-art inverted indexing method.
Reference: text
sentIndex sentText sentNum sentScore
1 An inverted file is built by a quantizer such as k-means or a tree structure. [sent-2, score-0.727]
2 It has been found that multiple inverted files, obtained by multiple independent random quantizers, are able to achieve practically good recall and speed. [sent-3, score-0.248]
3 Instead of computing the multiple quantizers independently, we present a method that creates them jointly. [sent-4, score-0.479]
4 Our method jointly optimizes all codewords in all quantizers. [sent-5, score-0.524]
5 On the one-billion set of SIFT vectors, our method is faster and more accurate than a recent state-of-the-art inverted indexing method. [sent-8, score-0.295]
6 The inverted indexing is built as a codebook of the codewords. [sent-20, score-0.312]
7 Given a query vector, the system finds the codeword of the query and checks those items in the list of this codeword. [sent-22, score-0.298]
8 An effective way to improve the recall of inverted indexing methods is to use multiple quantizers (also known as multiple hash tables [8, 26]). [sent-25, score-0.876]
9 In LSH each quantizer (hash table) is binning a low dimensional random subspace. [sent-29, score-0.475]
10 In the spirit of hash, all the above multi-quantizer methods create the quantizers independently and randomly. [sent-35, score-0.5]
11 The KLSH method [26] enjoys an advantage that its individual quantizer is (locally) optimal in the sense of minimizing quantization error [14]. [sent-36, score-0.522]
12 But we point out that for KLSH, the codewords from different codebooks tend to be similar. [sent-37, score-0.499]
13 This is because the k-means algorithm tends to put the codewords around densely distributed data even in different random trials. [sent-38, score-0.499]
14 Actually, the codewords can be different from each other only because of the local optimality of the kmeans nature. [sent-39, score-0.528]
15 The similar codewords would reduce the redundant coverage and limit the gain of multiple quantizers. [sent-40, score-0.499]
16 Suppose we want two quantizers each with two codewords. [sent-43, score-0.479]
17 If each quantizer is constructed randomly and independently as in KLSH, the two codewords in a quantizer will always be placed near the two peaks. [sent-44, score-1.448]
18 The space partitioning of the two quantizers are almost the same (Fig. [sent-45, score-0.515]
19 1 left), and the gain of having the second quantizer is lost. [sent-46, score-0.446]
20 Unless specified, in this paper we refer to LSH as a multiplequantizer method that uses inverted indexing, as it was described in [8, 2]. [sent-49, score-0.242]
21 33440169 biiuitsdtonrc1c3c2c4data c1c3c2c4 quantizce1r 1qc2 quantizce1r 1qc2 quantizerc 32qc4 quantizer c23qc4 KLSH Joint Figure 1. [sent-50, score-0.446]
22 We illustrate two quantizers with two codewords in each quantizer. [sent-53, score-0.978]
23 Top: the locations of the four codewords (c1 to c4). [sent-54, score-0.499]
24 Middle and Bottom: quantizer 1 and quantizer 2, with the partitioning boundaries. [sent-55, score-0.928]
25 When a query (q) is near any partitioning boundary, the independent quantizers may miss many true neighbors, while the joint quantizers can retrieve more true neighbors because the query is well inside at least one partition. [sent-56, score-1.277]
26 In the above example, we can instead generate all the four codewords jointly via a single pass of k-means clustering. [sent-57, score-0.551]
27 These four codewords are distant from each other (Fig. [sent-58, score-0.499]
28 Then we construct each quantizer by mutualexclusively selecting two codewords with some care, and the two resulting quantizers can be substantially different. [sent-60, score-1.439]
29 Any query that lies near the partitioning boundary of one quantizer can still find its k-NNs through the other quantizer, and the recall is improved. [sent-61, score-0.598]
30 With this motivation, in this paper we propose joint inverted indexing - a novel multiple-quantizer method. [sent-62, score-0.349]
31 Rather than construct quantizers independently, we create them jointly. [sent-63, score-0.479]
32 We first jointly optimize all the codewords of all quantizers. [sent-65, score-0.539]
33 The optimized codewords are then assigned to the quantizers, with a consideration that the total distortion of all quantizers is small. [sent-66, score-1.129]
34 When searching in one billion items for the first nearest neighbor of a query, our method takes less than ten milliseconds using a single thread and achieves over 90% recall in the first retrieved one hundred items (de- tailed in Sec. [sent-69, score-0.227]
35 In this paper, we focus on non-exhaustive search based on inverted indexing. [sent-80, score-0.235]
36 Inverted indexing could be built using a quantizer like k-means [22], a binary tree [10, 7], hierarchical k-means [11, 24], or a lattice [1]. [sent-81, score-0.571]
37 The k-means quantizer is (locally) optimal in terms of quantization distortion [14]. [sent-83, score-0.624]
38 It is an attractive way to use multiple quantizers to improve search accuracy. [sent-84, score-0.514]
39 For each single hash table, an inverted indexing system is built with each bin as an index, and each index has a list containing all the vectors in the bin. [sent-86, score-0.397]
40 But as discussed in the introduction, the codewords in the multiple quantizers can be similar in random trials. [sent-95, score-0.978]
41 This is actually a single quantizer method, whose quantizer is the Cartesian product of multiple subquantizers. [sent-97, score-0.926]
42 The finer quantization, in conjunction with a softassignment scheme, has shown great superiority to a single k-means quantizer [3]. [sent-102, score-0.473]
43 Formulation Denote the number of quantizers as L, and the number of codewords in each quantizer as K. [sent-109, score-1.424]
44 Background It is well-known that a k-means quantizer attempts to minimize the quantization distortion [14]: ? [sent-113, score-0.624]
45 -a Tlhieke d iasltgoortriitohnm in: (a1l)te crannati bvee olyp tuimpdizaetde tvhiea codewords {ck} and assign data to the clusters {Ck}. [sent-125, score-0.499]
46 If all the codewords {clk | 1 ≤ k ≤ K, 1 ≤ la n≤d cLo}d are ridn. [sent-138, score-0.499]
47 If it were not for the local optimality of k-means clustering, all the quantizers should be identical. [sent-141, score-0.479]
48 Joint Codewords Optimization In (2) the codewords in one quantizer are unaware of those in other quantizers. [sent-142, score-0.945]
49 So the independent optimization of any two quantizers may push the codewords towards similar positions due to the kmeans nature. [sent-143, score-1.007]
50 To overcome this issue, we propose to optimize all the codewords jointly. [sent-144, score-0.514]
51 We notice that in multiple inverted files, it is sufficient for a true datum to be correctly retrieved if it is covered by one of the L lists. [sent-145, score-0.283]
52 To jointly optimize all codewords of all quantizers, we propose to minimize the sum of the smallest distortion of all data: ? [sent-150, score-0.655]
53 A = naive way is to randomly assign the codewords in C without replacement2 to the L quantizers. [sent-178, score-0.535]
54 This implies that the joint codewords optimization is an effective method for multiple quantizers. [sent-183, score-0.578]
55 This is due to two nice properties of joint codewords optimization: (i) each x is expected to be accurately quantized at least once, in the sense of optimizing (4); (ii) the codewords among the quantizers are guaranteed to be sufficiently different from each other. [sent-184, score-1.531]
56 Notice that the quantization distortion of any individual quantizer has not been considered in (4). [sent-189, score-0.624]
57 For a better assignment, we consider the total distortion of all quantizers subject to a constraint. [sent-190, score-0.621]
58 We illustrate L=3 quantizers with K=8 codewords in each quantizer. [sent-208, score-0.978]
59 All L K codewords in all quantizers are generated simultaneously by k-means clustering. [sent-211, score-0.978]
60 quantizer i sa constructed by randomly selecting one codeword from each group without replacement. [sent-219, score-0.559]
61 The codewords in quantizer 1, 2, 3 are represented by ? [sent-220, score-0.945]
62 The objective function in (6) is the total distortion of all ×× quantizers as in (2). [sent-225, score-0.6]
63 The constraint in (7) means that the codewords must be mutual-exclusively selected from the fixed C. [sent-226, score-0.499]
64 As such, the codewords must be subject to the jointly optimized codewords in (4). [sent-227, score-1.074]
65 Because the set C has been fixed, the codewords cannot be arbitrarily updated (e. [sent-229, score-0.499]
66 L K codewords are generated by a single pass oerfa t kio-mn. [sent-244, score-0.526]
67 We divide the L K codewords into K groups (each group c doinvtiadiens t Le Lc×odKewords) (Fig. [sent-249, score-0.499]
68 We group the codewords by a random projection tree [9]. [sent-252, score-0.526]
69 A K-codeword quantizer is generated by randomly selecting one codeword from each of the K groups without replacement. [sent-254, score-0.559]
70 We repeat this for L times and construct all the L quantizers (Fig. [sent-255, score-0.479]
71 Discussions: × Intuitively, to make a quantizer with small distortion, we expect the K codewords of this quantizer to be dispersed. [sent-257, score-1.391]
72 So we group the codewords by a second pass of clustering (in Step 2, by a tree), and randomly select one codeword from each group to form a quantizer (in Step 3). [sent-258, score-1.085]
73 As such, we can avoid the codewords in any quantizer from being too Joint (rJaonidn-tas ign)99. [sent-259, score-0.945]
74 We can expect such a quantizer to have smaller distortion than a quantizer that randomly selects from the whole set C (as in “Joint (rand-assign)”). [sent-274, score-1.016]
75 Table 1 also gives the standard deviations (std) of total distortion in 10 random trails for both methods (all trails subject to the same constraint). [sent-277, score-0.242]
76 We have also tried to optimize the total distortion by greedily swapping pairs of codewords between quantizers. [sent-279, score-0.635]
77 For this database we build 3 quantizers with 8 codewords in each quantizer (L = 3, K = 8). [sent-288, score-1.424]
78 We can see that in KLSH some codewords of different quantizers are very similar. [sent-289, score-0.978]
79 4(a) we show the be33441192 c od siedsmiwemwilao lra rdsds × quantizer 1 quantizer 2 quantizer 3 quantizer 1 quantizer 2 quantizer 3 (a) KLSH (b) Joint Figure 3. [sent-291, score-2.676]
80 Top: the locations of all codewords in all quantizers. [sent-295, score-0.499]
81 The codewords in quantizer 1, 2, 3 are represented by ? [sent-298, score-0.945]
82 ), the cell where the query lies in each quantizer is shown by the partitioning boundary. [sent-306, score-0.55]
83 havior of these quantizers to a typical query point: due to the similar codewords, the gain of the multiple quantizers is limited. [sent-308, score-1.026]
84 In contrast, all the codewords are jointly optimized by our method (Fig. [sent-310, score-0.554]
85 Both KLSH and our method should scan all codewords given a query. [sent-496, score-0.499]
86 This can be time-consuming when the number of codewords is large, e. [sent-497, score-0.499]
87 5 all methods use the same number of quantizers (L). [sent-512, score-0.479]
88 5 shows that our joint quantizers outperform KLSH and other alternatives. [sent-520, score-0.533]
89 This implies KLSH benefits from the k-means quantizers that give smaller distortion than the other independent quantizers. [sent-523, score-0.606]
90 assign)” is a way that has jointly optimized codewords but has larger total distortion than the “Joint” way (Table 1). [sent-580, score-0.703]
91 This implies the jointly optimized codewords are very essential for good performance. [sent-583, score-0.579]
92 7 we investigate the recall versus the number of quantizers (L) at a given number N. [sent-588, score-0.513]
93 Comparisons with Inverted Multi-Index [3] We also compare with inverted multi-index [3], a recent state-ofthe-art inverted indexing method. [sent-596, score-0.509]
94 2, this method is actually a single quantizer method with finer quantization and soft-assignments. [sent-598, score-0.563]
95 Because it can be more complicate to encode residual vectors in multiple quantizers (KLSH and ours), we simply use PQ to encode the original vector (it is observed that encoding the original vector is inferior [3]). [sent-608, score-0.531]
96 Both KLSH and our method use L=16 quantizers here. [sent-615, score-0.479]
97 But because the short lists in its finer quantizer are “too short”, this operation retrieves a very large number oflists and takes more time (cache-unfriendly). [sent-619, score-0.596]
98 Each single quantizer uses one inverted file that stores all the vector IDs. [sent-626, score-0.683]
99 On the contrary, the inverted multi-index method [3] is memory efficient as a single quantizer method. [sent-636, score-0.681]
100 The training time is mainly on obtaining the L K codewords in the single pass of kmeans. [sent-651, score-0.526]
wordName wordTfidf (topN-words)
[('codewords', 0.499), ('quantizers', 0.479), ('quantizer', 0.446), ('klsh', 0.326), ('inverted', 0.214), ('clk', 0.185), ('distortion', 0.102), ('codeword', 0.091), ('indexing', 0.081), ('quantization', 0.076), ('lsh', 0.073), ('query', 0.068), ('lists', 0.063), ('hash', 0.054), ('joint', 0.054), ('adc', 0.05), ('trails', 0.05), ('ck', 0.049), ('retrieves', 0.047), ('trees', 0.046), ('querying', 0.043), ('ckl', 0.043), ('hashing', 0.04), ('rkd', 0.038), ('items', 0.037), ('bytes', 0.036), ('partitioning', 0.036), ('recall', 0.034), ('jegou', 0.033), ('retrieval', 0.03), ('retrieved', 0.03), ('optimized', 0.03), ('binning', 0.029), ('kmeans', 0.029), ('ckld', 0.028), ('clkin', 0.028), ('fineness', 0.028), ('multiplequantizer', 0.028), ('paulev', 0.028), ('randassign', 0.028), ('files', 0.028), ('finer', 0.027), ('billion', 0.027), ('tree', 0.027), ('pass', 0.027), ('documents', 0.027), ('implies', 0.025), ('retrieve', 0.025), ('dasgupta', 0.025), ('consumes', 0.025), ('jointly', 0.025), ('nearest', 0.024), ('datum', 0.023), ('file', 0.023), ('randomly', 0.022), ('lattices', 0.022), ('neighbors', 0.022), ('search', 0.021), ('independently', 0.021), ('randomized', 0.021), ('subject', 0.021), ('std', 0.021), ('memory', 0.021), ('comparisons', 0.02), ('encoding', 0.02), ('product', 0.02), ('neighbor', 0.02), ('douze', 0.02), ('checks', 0.019), ('stoc', 0.019), ('total', 0.019), ('indyk', 0.018), ('thread', 0.018), ('cartesian', 0.018), ('compact', 0.018), ('competitors', 0.017), ('symposium', 0.017), ('pages', 0.017), ('dot', 0.017), ('built', 0.017), ('residual', 0.016), ('vectors', 0.016), ('true', 0.016), ('optimize', 0.015), ('counted', 0.015), ('substantially', 0.015), ('gmm', 0.015), ('checking', 0.015), ('engines', 0.015), ('list', 0.015), ('way', 0.014), ('pq', 0.014), ('smallest', 0.014), ('alternatives', 0.014), ('toy', 0.014), ('near', 0.014), ('actually', 0.014), ('embedding', 0.014), ('isard', 0.013), ('short', 0.013)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999988 221 iccv-2013-Joint Inverted Indexing
Author: Yan Xia, Kaiming He, Fang Wen, Jian Sun
Abstract: Inverted indexing is a popular non-exhaustive solution to large scale search. An inverted file is built by a quantizer such as k-means or a tree structure. It has been found that multiple inverted files, obtained by multiple independent random quantizers, are able to achieve practically good recall and speed. Instead of computing the multiple quantizers independently, we present a method that creates them jointly. Our method jointly optimizes all codewords in all quantizers. Then it assigns these codewords to the quantizers. In experiments this method shows significant improvement over various existing methods that use multiple independent quantizers. On the one-billion set of SIFT vectors, our method is faster and more accurate than a recent state-of-the-art inverted indexing method.
2 0.1509991 354 iccv-2013-Robust Dictionary Learning by Error Source Decomposition
Author: Zhuoyuan Chen, Ying Wu
Abstract: Sparsity models have recently shown great promise in many vision tasks. Using a learned dictionary in sparsity models can in general outperform predefined bases in clean data. In practice, both training and testing data may be corrupted and contain noises and outliers. Although recent studies attempted to cope with corrupted data and achieved encouraging results in testing phase, how to handle corruption in training phase still remains a very difficult problem. In contrast to most existing methods that learn the dictionaryfrom clean data, this paper is targeted at handling corruptions and outliers in training data for dictionary learning. We propose a general method to decompose the reconstructive residual into two components: a non-sparse component for small universal noises and a sparse component for large outliers, respectively. In addition, , further analysis reveals the connection between our approach and the “partial” dictionary learning approach, updating only part of the prototypes (or informative codewords) with remaining (or noisy codewords) fixed. Experiments on synthetic data as well as real applications have shown satisfactory per- formance of this new robust dictionary learning approach.
3 0.14810109 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
Author: Jing Wang, Jingdong Wang, Gang Zeng, Rui Gan, Shipeng Li, Baining Guo
Abstract: In this paper, we propose a new data structure for approximate nearest neighbor search. This structure augments the neighborhoodgraph with a bridge graph. We propose to exploit Cartesian concatenation to produce a large set of vectors, called bridge vectors, from several small sets of subvectors. Each bridge vector is connected with a few reference vectors near to it, forming a bridge graph. Our approach finds nearest neighbors by simultaneously traversing the neighborhood graph and the bridge graph in the best-first strategy. The success of our approach stems from two factors: the exact nearest neighbor search over a large number of bridge vectors can be done quickly, and the reference vectors connected to a bridge (reference) vector near the query are also likely to be near the query. Experimental results on searching over large scale datasets (SIFT, GIST andHOG) show that our approach outperforms stateof-the-art ANN search algorithms in terms of efficiency and accuracy. The combination of our approach with the IVFADC system [18] also shows superior performance over the BIGANN dataset of 1 billion SIFT features compared with the best previously published result.
4 0.14554463 378 iccv-2013-Semantic-Aware Co-indexing for Image Retrieval
Author: Shiliang Zhang, Ming Yang, Xiaoyu Wang, Yuanqing Lin, Qi Tian
Abstract: Inverted indexes in image retrieval not only allow fast access to database images but also summarize all knowledge about the database, so that their discriminative capacity largely determines the retrieval performance. In this paper, for vocabulary tree based image retrieval, we propose a semantic-aware co-indexing algorithm to jointly San Antonio, TX 78249 . j dl@gmai l com qit ian@cs .ut sa . edu . The query embed two strong cues into the inverted indexes: 1) local invariant features that are robust to delineate low-level image contents, and 2) semantic attributes from large-scale object recognition that may reveal image semantic meanings. For an initial set of inverted indexes of local features, we utilize 1000 semantic attributes to filter out isolated images and insert semantically similar images to the initial set. Encoding these two distinct cues together effectively enhances the discriminative capability of inverted indexes. Such co-indexing operations are totally off-line and introduce small computation overhead to online query cause only local features but no semantic attributes are used for query. Experiments and comparisons with recent retrieval methods on 3 datasets, i.e., UKbench, Holidays, Oxford5K, and 1.3 million images from Flickr as distractors, manifest the competitive performance of our method 1.
5 0.11619718 400 iccv-2013-Stable Hyper-pooling and Query Expansion for Event Detection
Author: Matthijs Douze, Jérôme Revaud, Cordelia Schmid, Hervé Jégou
Abstract: This paper makes two complementary contributions to event retrieval in large collections of videos. First, we propose hyper-pooling strategies that encode the frame descriptors into a representation of the video sequence in a stable manner. Our best choices compare favorably with regular pooling techniques based on k-means quantization. Second, we introduce a technique to improve the ranking. It can be interpreted either as a query expansion method or as a similarity adaptation based on the local context of the query video descriptor. Experiments on public benchmarks show that our methods are complementary and improve event retrieval results, without sacrificing efficiency.
6 0.10997096 337 iccv-2013-Random Grids: Fast Approximate Nearest Neighbors and Range Searching for Image Search
8 0.10429615 83 iccv-2013-Complementary Projection Hashing
9 0.086978093 266 iccv-2013-Mining Multiple Queries for Image Retrieval: On-the-Fly Learning of an Object-Specific Mid-level Representation
10 0.084331758 450 iccv-2013-What is the Most EfficientWay to Select Nearest Neighbor Candidates for Fast Approximate Nearest Neighbor Search?
11 0.081335127 229 iccv-2013-Large-Scale Video Hashing via Structure Learning
12 0.07798969 13 iccv-2013-A General Two-Step Approach to Learning-Based Hashing
13 0.077071384 294 iccv-2013-Offline Mobile Instance Retrieval with a Small Memory Footprint
14 0.074791797 287 iccv-2013-Neighbor-to-Neighbor Search for Fast Coding of Feature Vectors
15 0.062380094 239 iccv-2013-Learning Hash Codes with Listwise Supervision
16 0.061761029 162 iccv-2013-Fast Subspace Search via Grassmannian Based Hashing
17 0.060878634 409 iccv-2013-Supervised Binary Hash Code Learning with Jensen Shannon Divergence
18 0.058709469 210 iccv-2013-Image Retrieval Using Textual Cues
19 0.058670696 334 iccv-2013-Query-Adaptive Asymmetrical Dissimilarities for Visual Object Retrieval
20 0.048173364 419 iccv-2013-To Aggregate or Not to aggregate: Selective Match Kernels for Image Search
topicId topicWeight
[(0, 0.083), (1, 0.03), (2, -0.045), (3, -0.061), (4, -0.022), (5, 0.152), (6, -0.003), (7, -0.025), (8, -0.109), (9, 0.049), (10, 0.026), (11, 0.035), (12, 0.024), (13, 0.022), (14, -0.009), (15, 0.037), (16, 0.054), (17, -0.047), (18, 0.045), (19, -0.021), (20, -0.008), (21, -0.025), (22, 0.007), (23, 0.025), (24, -0.027), (25, -0.023), (26, 0.016), (27, -0.025), (28, -0.004), (29, -0.025), (30, 0.018), (31, 0.006), (32, 0.013), (33, 0.023), (34, 0.018), (35, 0.017), (36, 0.006), (37, 0.005), (38, 0.037), (39, 0.057), (40, -0.009), (41, 0.073), (42, -0.05), (43, -0.015), (44, -0.015), (45, 0.024), (46, -0.007), (47, -0.104), (48, 0.035), (49, -0.005)]
simIndex simValue paperId paperTitle
same-paper 1 0.93782288 221 iccv-2013-Joint Inverted Indexing
Author: Yan Xia, Kaiming He, Fang Wen, Jian Sun
Abstract: Inverted indexing is a popular non-exhaustive solution to large scale search. An inverted file is built by a quantizer such as k-means or a tree structure. It has been found that multiple inverted files, obtained by multiple independent random quantizers, are able to achieve practically good recall and speed. Instead of computing the multiple quantizers independently, we present a method that creates them jointly. Our method jointly optimizes all codewords in all quantizers. Then it assigns these codewords to the quantizers. In experiments this method shows significant improvement over various existing methods that use multiple independent quantizers. On the one-billion set of SIFT vectors, our method is faster and more accurate than a recent state-of-the-art inverted indexing method.
2 0.76073074 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
Author: Jing Wang, Jingdong Wang, Gang Zeng, Rui Gan, Shipeng Li, Baining Guo
Abstract: In this paper, we propose a new data structure for approximate nearest neighbor search. This structure augments the neighborhoodgraph with a bridge graph. We propose to exploit Cartesian concatenation to produce a large set of vectors, called bridge vectors, from several small sets of subvectors. Each bridge vector is connected with a few reference vectors near to it, forming a bridge graph. Our approach finds nearest neighbors by simultaneously traversing the neighborhood graph and the bridge graph in the best-first strategy. The success of our approach stems from two factors: the exact nearest neighbor search over a large number of bridge vectors can be done quickly, and the reference vectors connected to a bridge (reference) vector near the query are also likely to be near the query. Experimental results on searching over large scale datasets (SIFT, GIST andHOG) show that our approach outperforms stateof-the-art ANN search algorithms in terms of efficiency and accuracy. The combination of our approach with the IVFADC system [18] also shows superior performance over the BIGANN dataset of 1 billion SIFT features compared with the best previously published result.
3 0.76018453 337 iccv-2013-Random Grids: Fast Approximate Nearest Neighbors and Range Searching for Image Search
Author: Dror Aiger, Efi Kokiopoulou, Ehud Rivlin
Abstract: We propose two solutions for both nearest neighbors and range search problems. For the nearest neighbors problem, we propose a c-approximate solutionfor the restricted version ofthe decisionproblem with bounded radius which is then reduced to the nearest neighbors by a known reduction. For range searching we propose a scheme that learns the parameters in a learning stage adopting them to the case of a set of points with low intrinsic dimension that are embedded in high dimensional space (common scenario for image point descriptors). We compare our algorithms to the best known methods for these problems, i.e. LSH, ANN and FLANN. We show analytically and experimentally that we can do better for moderate approximation factor. Our algorithms are trivial to parallelize. In the experiments conducted, running on couple of million im- ages, our algorithms show meaningful speed-ups when compared with the above mentioned methods.
Author: Yannis Avrithis
Abstract: Inspired by the close relation between nearest neighbor search and clustering in high-dimensional spaces as well as the success of one helping to solve the other, we introduce a new paradigm where both problems are solved simultaneously. Our solution is recursive, not in the size of input data but in the number of dimensions. One result is a clustering algorithm that is tuned to small codebooks but does not need all data in memory at the same time and is practically constant in the data size. As a by-product, a tree structure performs either exact or approximate quantization on trained centroids, the latter being not very precise but extremely fast. A lesser contribution is a new indexing scheme for image retrieval that exploits multiple small codebooks to provide an arbitrarily fine partition of the descriptor space. Large scale experiments on public datasets exhibit state of the art performance and remarkable generalization.
Author: Masakazu Iwamura, Tomokazu Sato, Koichi Kise
Abstract: Approximate nearest neighbor search (ANNS) is a basic and important technique used in many tasks such as object recognition. It involves two processes: selecting nearest neighbor candidates and performing a brute-force search of these candidates. Only the former though has scope for improvement. In most existing methods, it approximates the space by quantization. It then calculates all the distances between the query and all the quantized values (e.g., clusters or bit sequences), and selects a fixed number of candidates close to the query. The performance of the method is evaluated based on accuracy as a function of the number of candidates. This evaluation seems rational but poses a serious problem; it ignores the computational cost of the process of selection. In this paper, we propose a new ANNS method that takes into account costs in the selection process. Whereas existing methods employ computationally expensive techniques such as comparative sort and heap, the proposed method does not. This realizes a significantly more efficient search. We have succeeded in reducing computation times by one-third compared with the state-of-the- art on an experiment using 100 million SIFT features.
6 0.71531379 419 iccv-2013-To Aggregate or Not to aggregate: Selective Match Kernels for Image Search
7 0.70942265 400 iccv-2013-Stable Hyper-pooling and Query Expansion for Event Detection
8 0.70494884 334 iccv-2013-Query-Adaptive Asymmetrical Dissimilarities for Visual Object Retrieval
9 0.6951853 294 iccv-2013-Offline Mobile Instance Retrieval with a Small Memory Footprint
10 0.67150843 266 iccv-2013-Mining Multiple Queries for Image Retrieval: On-the-Fly Learning of an Object-Specific Mid-level Representation
11 0.65910256 378 iccv-2013-Semantic-Aware Co-indexing for Image Retrieval
12 0.64836621 287 iccv-2013-Neighbor-to-Neighbor Search for Fast Coding of Feature Vectors
13 0.63206995 162 iccv-2013-Fast Subspace Search via Grassmannian Based Hashing
14 0.53707749 446 iccv-2013-Visual Semantic Complex Network for Web Images
15 0.49895146 365 iccv-2013-SIFTpack: A Compact Representation for Efficient SIFT Matching
16 0.4950676 83 iccv-2013-Complementary Projection Hashing
17 0.48559839 409 iccv-2013-Supervised Binary Hash Code Learning with Jensen Shannon Divergence
18 0.47638837 239 iccv-2013-Learning Hash Codes with Listwise Supervision
19 0.47619489 131 iccv-2013-EVSAC: Accelerating Hypotheses Generation by Modeling Matching Scores with Extreme Value Theory
20 0.4630076 229 iccv-2013-Large-Scale Video Hashing via Structure Learning
topicId topicWeight
[(2, 0.114), (7, 0.019), (13, 0.015), (26, 0.042), (27, 0.011), (31, 0.047), (42, 0.065), (64, 0.029), (73, 0.015), (76, 0.325), (89, 0.171), (98, 0.017)]
simIndex simValue paperId paperTitle
1 0.74434417 164 iccv-2013-Fibonacci Exposure Bracketing for High Dynamic Range Imaging
Author: Mohit Gupta, Daisuke Iso, Shree K. Nayar
Abstract: Exposure bracketing for high dynamic range (HDR) imaging involves capturing several images of the scene at different exposures. If either the camera or the scene moves during capture, the captured images must be registered. Large exposure differences between bracketed images lead to inaccurate registration, resulting in artifacts such as ghosting (multiple copies of scene objects) and blur. We present two techniques, one for image capture (Fibonacci exposure bracketing) and one for image registration (generalized registration), to prevent such motion-related artifacts. Fibonacci bracketing involves capturing a sequence of images such that each exposure time is the sum of the previous N(N > 1) exposures. Generalized registration involves estimating motion between sums of contiguous sets of frames, instead of between individual frames. Together, the two techniques ensure that motion is always estimated betweenframes of the same total exposure time. This results in HDR images and videos which have both a large dynamic range andminimal motion-relatedartifacts. We show, by results for several real-world indoor and outdoor scenes, that theproposed approach significantly outperforms several ex- isting bracketing schemes.
same-paper 2 0.73893362 221 iccv-2013-Joint Inverted Indexing
Author: Yan Xia, Kaiming He, Fang Wen, Jian Sun
Abstract: Inverted indexing is a popular non-exhaustive solution to large scale search. An inverted file is built by a quantizer such as k-means or a tree structure. It has been found that multiple inverted files, obtained by multiple independent random quantizers, are able to achieve practically good recall and speed. Instead of computing the multiple quantizers independently, we present a method that creates them jointly. Our method jointly optimizes all codewords in all quantizers. Then it assigns these codewords to the quantizers. In experiments this method shows significant improvement over various existing methods that use multiple independent quantizers. On the one-billion set of SIFT vectors, our method is faster and more accurate than a recent state-of-the-art inverted indexing method.
3 0.66511333 118 iccv-2013-Discovering Object Functionality
Author: Bangpeng Yao, Jiayuan Ma, Li Fei-Fei
Abstract: Object functionality refers to the quality of an object that allows humans to perform some specific actions. It has been shown in psychology that functionality (affordance) is at least as essential as appearance in object recognition by humans. In computer vision, most previous work on functionality either assumes exactly one functionality for each object, or requires detailed annotation of human poses and objects. In this paper, we propose a weakly supervised approach to discover all possible object functionalities. Each object functionality is represented by a specific type of human-object interaction. Our method takes any possible human-object interaction into consideration, and evaluates image similarity in 3D rather than 2D in order to cluster human-object interactions more coherently. Experimental results on a dataset of people interacting with musical instruments show the effectiveness of our approach.
4 0.65992868 260 iccv-2013-Manipulation Pattern Discovery: A Nonparametric Bayesian Approach
Author: Bingbing Ni, Pierre Moulin
Abstract: We aim to unsupervisedly discover human’s action (motion) patterns of manipulating various objects in scenarios such as assisted living. We are motivated by two key observations. First, large variation exists in motion patterns associated with various types of objects being manipulated, thus manually defining motion primitives is infeasible. Second, some motion patterns are shared among different objects being manipulated while others are object specific. We therefore propose a nonparametric Bayesian method that adopts a hierarchical Dirichlet process prior to learn representative manipulation (motion) patterns in an unsupervised manner. Taking easy-to-obtain object detection score maps and dense motion trajectories as inputs, the proposed probabilistic model can discover motion pattern groups associated with different types of objects being manipulated with a shared manipulation pattern dictionary. The size of the learned dictionary is automatically inferred. Com- prehensive experiments on two assisted living benchmarks and a cooking motion dataset demonstrate superiority of our learned manipulation pattern dictionary in representing manipulation actions for recognition.
5 0.6126259 414 iccv-2013-Temporally Consistent Superpixels
Author: Matthias Reso, Jörn Jachalsky, Bodo Rosenhahn, Jörn Ostermann
Abstract: Superpixel algorithms represent a very useful and increasingly popular preprocessing step for a wide range of computer vision applications, as they offer the potential to boost efficiency and effectiveness. In this regards, this paper presents a highly competitive approach for temporally consistent superpixelsfor video content. The approach is based on energy-minimizing clustering utilizing a novel hybrid clustering strategy for a multi-dimensional feature space working in a global color subspace and local spatial subspaces. Moreover, a new contour evolution based strategy is introduced to ensure spatial coherency of the generated superpixels. For a thorough evaluation the proposed approach is compared to state of the art supervoxel algorithms using established benchmarks and shows a superior performance.
6 0.56576765 229 iccv-2013-Large-Scale Video Hashing via Structure Learning
7 0.56552899 322 iccv-2013-Pose Estimation and Segmentation of People in 3D Movies
8 0.56150663 448 iccv-2013-Weakly Supervised Learning of Image Partitioning Using Decision Trees with Structured Split Criteria
9 0.56047744 210 iccv-2013-Image Retrieval Using Textual Cues
10 0.56024504 374 iccv-2013-Salient Region Detection by UFO: Uniqueness, Focusness and Objectness
11 0.55820626 426 iccv-2013-Training Deformable Part Models with Decorrelated Features
12 0.55701149 419 iccv-2013-To Aggregate or Not to aggregate: Selective Match Kernels for Image Search
13 0.55684346 443 iccv-2013-Video Synopsis by Heterogeneous Multi-source Correlation
14 0.55603015 137 iccv-2013-Efficient Salient Region Detection with Soft Image Abstraction
15 0.55530262 409 iccv-2013-Supervised Binary Hash Code Learning with Jensen Shannon Divergence
16 0.55494291 404 iccv-2013-Structured Forests for Fast Edge Detection
17 0.55453682 238 iccv-2013-Learning Graphs to Match
18 0.5544908 73 iccv-2013-Class-Specific Simplex-Latent Dirichlet Allocation for Image Classification
19 0.55437863 368 iccv-2013-SYM-FISH: A Symmetry-Aware Flip Invariant Sketch Histogram Shape Descriptor
20 0.55433887 248 iccv-2013-Learning to Rank Using Privileged Information