iccv iccv2013 iccv2013-13 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Guosheng Lin, Chunhua Shen, David Suter, Anton van_den_Hengel
Abstract: Most existing approaches to hashing apply a single form of hash function, and an optimization process which is typically deeply coupled to this specific form. This tight coupling restricts the flexibility of the method to respond to the data, and can result in complex optimization problems that are difficult to solve. Here we propose a flexible yet simple framework that is able to accommodate different types of loss functions and hash functions. This framework allows a number of existing approaches to hashing to be placed in context, and simplifies the development of new problemspecific hashing methods. Our framework decomposes the hashing learning problem into two steps: hash bit learning and hash function learning based on the learned bits. The first step can typically be formulated as binary quadratic problems, and the second step can be accomplished by training standard binary classifiers. Both problems have been extensively studied in the literature. Our extensive experiments demonstrate that the proposed framework is effective, flexible and outperforms the state-of-the-art.
Reference: text
sentIndex sentText sentNum sentScore
1 Here we propose a flexible yet simple framework that is able to accommodate different types of loss functions and hash functions. [sent-3, score-1.048]
2 This framework allows a number of existing approaches to hashing to be placed in context, and simplifies the development of new problemspecific hashing methods. [sent-4, score-0.881]
3 Our framework decomposes the hashing learning problem into two steps: hash bit learning and hash function learning based on the learned bits. [sent-5, score-1.806]
4 The first step can typically be formulated as binary quadratic problems, and the second step can be accomplished by training standard binary classifiers. [sent-6, score-0.291]
5 Introduction Recently hashing methods have been widely used for a variety of applications, but have been particularly successful when applied to approximate nearest neighbor search. [sent-10, score-0.42]
6 Hashing methods construct a set of hash functions that map the original high-dimensional data into a compact binary space. [sent-11, score-0.872]
7 The resulting binary codes enable fast similarity search on the basis ofthe Hamming distance between codes. [sent-12, score-0.321]
8 In general, hash functions are generated with the aim of preserving some notion of similarity between data points. [sent-15, score-0.775]
9 One of the seminal approaches in this vein is locality-sensitive hashing (LSH) [2], which randomly generates hash functions to approximate cosine similarity. [sent-16, score-1.173]
10 In this category, a number of methods have been proposed, for example: spectral hashing (SPH) [15], multi-dimension spectral hashing (MDSH) [14], iterative quantization (ITQ) [3] and inductive manifold hashing [11]. [sent-22, score-1.414]
11 These methods do not rely on labeled data and are thus categorized as unsupervised hashing methods. [sent-23, score-0.462]
12 Recent works include supervised hashing with ker- nels (KSH) [8], minimal loss hashing (MLH) [10], supervised binary reconstructive embeddings (BRE) [5], semisupervised sequential projection learning hashing (SPLH) [13] and column generation hashing [7], etc. [sent-25, score-2.251]
13 Loss functions for hashing are typically defined on the basis of the Hamming distance or Hamming affinity of similar and dissimilar data pairs. [sent-26, score-0.786]
14 Hamming affinity is calculated by the inner product of two binary codes (a binary code takes a value of {−1, 1}). [sent-27, score-0.606]
15 Existing methods thus tend to optimize a single form of hash functions, the parameters of which are directly optimized against the overall loss function. [sent-28, score-0.832]
16 The common forms of hash functions are linear perceptron functions (MLH, SPLH, LSH), kernel functions (KSH), eigenfunctions (SPH, MDSH). [sent-29, score-1.199]
17 The optimization procedure is then coupled with the selected family of hash function. [sent-30, score-0.673]
18 Different types of hash functions offer a trade-off between testing time and ranking accuracy. [sent-31, score-0.81]
19 As an example, the loss functions in MDSH, KSH and BRE all take a similar form that aims to minimize the difference between the Hamming affinity (or distance) and the ground truth of data pairs. [sent-34, score-0.548]
20 However, the optimization procedures used in these methods are coupled with the form of hash functions (eigenfunctions, kernel functions) and thus different optimization techniques are needed. [sent-35, score-0.911]
21 Self-Taught Hashing (STH) [16] is a method which decomposes the learning procedure into two steps: binary code generating and hash function learning. [sent-36, score-0.85]
22 We extend this idea and propose a general two-step approach to hashing of which STH can be seen as a specific example. [sent-37, score-0.42]
23 Our framework, however, is able to accommodate many different loss functions defined on the Hamming affinity of data pairs, such as the loss function used in KSH, BRE or MLH. [sent-39, score-0.818]
24 This more general family of loss functions may consider both similar and dissimilar data pairs. [sent-40, score-0.402]
25 In order to produce effective binary codes in this first step, we develop a new technique based on coordinate descent. [sent-41, score-0.312]
26 We show that at each iteration of coordinate descent, we can formulate the optimization problem of any Hamming affinity loss as a binary quadratic problem. [sent-42, score-0.66]
27 This formulation unifies different types of objective functions into the same optimization problem, which significantly simplifies the optimization effort. [sent-43, score-0.288]
28 (1) We propose a flexible hashing framework that decomposes the learning procedure into two steps: binary codes inference step and hash function learning step. [sent-45, score-1.411]
29 This decom- position simplifies the problem and enables the use of different types of loss functions and simplifies the hash function learning problem into a standard binary classification problem. [sent-46, score-1.248]
30 An arbitrary classifier, such as linear or kernel support vector machines (SVM), boosting, neural networks, may thus be adopted to train the hash functions. [sent-47, score-0.666]
31 (2) For binary code inference, we show that optimization using different types of loss functions (e. [sent-48, score-0.603]
32 , loss functions in KSH, BRE, MLH) can be solved as a series of binary quadratic problems. [sent-50, score-0.539]
33 2 loss, exponential loss, hinge loss) defined on Hamming affinity of data pairs can be equivalently converted into a standard quadratic function. [sent-54, score-0.328]
34 Based on this key observation, we propose a general block coordinate decent method that is able to incorporate many different types of loss functions in a unified manner. [sent-55, score-0.529]
35 To show the flexibility, we evaluate our method using different types of loss functions and different formats of hash functions (linear SVM, kernel SVM, Adaboost with decision stumps, etc). [sent-58, score-1.206]
36 xn} ⊂ Rd, the goal of hashing is to learn a set of hash functions that are able to preserve some notion of similarity between data points. [sent-64, score-1.218]
37 In this case yij is the (i, j)-th element of the matrix Y, which is an affinity value of the data pair (xi, xj). [sent-66, score-0.342]
38 In the case of unsupervised learning, yij can be defined as the Euclidean distance or Gaussian affinity on data points. [sent-68, score-0.391]
39 Φ(·) is a set of m hash functions: Φ(·) = [h1(·) , h2 (·) , . [sent-69, score-0.609]
40 The output of the hash functions are m-bit binary codes: Φ(x) ∈ {−1, 1}m. [sent-73, score-0.872]
41 (1) Here δij ∈ {0, 1} indicates whether the relation between two data points is defined, and L(Φ(xi) , Φ(xj) ; yij) is a loss function that measures the how well the binary codes match the expected affinity (or distance) yij . [sent-77, score-0.844]
42 Many different types of loss functions L(·) have been devised, and will be discussed in detail in the next section. [sent-78, score-0.396]
43 Most existing methods try to directly optimize objective (1) in order to learn the parameters of hash functions [5, 8, 10, 14]. [sent-79, score-0.753]
44 This inevitably means that the optimization process is tightly coupled to the form of hash functions used, which makes it non-trivial to extend a method to use another different format of hash functions. [sent-80, score-1.426]
45 Following the idea of STH [16], we decompose the learning procedure into two steps: the first step for binary code inference and the second step for hash function learning. [sent-82, score-0.839]
46 : Z ∈ {−1,1}m×n, (2) where Z is the matrix of m-bit binary codes for all data points, and zi is the binary code vector corresponding to i-th data point. [sent-87, score-0.52]
47 The second step is to learn hash functions based on the binary codes obtained in the first step, which is achieved by solving the optimization problem: n mΦ(i·n)i? [sent-88, score-1.064]
48 To learn the k-th hash function hk (·), the optimization can be written: n mhk(i·n)i? [sent-92, score-0.669]
49 (·, ·) is an loss function defined on two codes; zi,k is the binary code corresponding to the i-th data point and the k-th bit. [sent-96, score-0.416]
50 Clearly, the above optimization is a binary classification problem which is to minimize a kind of loss given the binary labels. [sent-97, score-0.498]
51 As in classification, one 22555533 Algorithm 1Block coordinate decent for learning binary codes (Step-1) 1: Input: affinity matrix Y, bit length m, number of cyclic iteration r. [sent-100, score-0.701]
52 , m 5: Solve the binary quadratic problem (BQP) in (13) to obtain the binary codes of t-th bit. [sent-105, score-0.446]
53 6: Update the codes of the t-th bit in the code matrix Z. [sent-106, score-0.283]
54 9: Output: the matrix of binary codes Z can also use a convex surrogate to replace the zero-one loss. [sent-108, score-0.314]
55 Typical surrogate loss functions are hinge loss, logistic loss, etc. [sent-109, score-0.417]
56 The resulting classifier is the hash function that we aim to learn. [sent-110, score-0.632]
57 For example, we can learn perceptron hash functions by training a linear SVM. [sent-112, score-0.825]
58 The linear perceptron hash function has the form: (w? [sent-113, score-0.704]
59 (5) We could also train, for example, an RBF-kernel SVM, or Adaboost as hash functions. [sent-115, score-0.609]
60 Here we describe a kernel hash function that is learned using a linear SVM on kernel-transferred features (referred to as SVM-KF). [sent-116, score-0.689]
61 The hash function learned by SVM-KF has a form as follows: h(x) = sign ? [sent-117, score-0.632]
62 We evaluate variety of different kinds of hash function in the Experiments Section below. [sent-128, score-0.632]
63 These tests show that Kernel hash functions often offer better ranking precision but require much more evaluation time than linear perceptron hash functions. [sent-129, score-1.434]
64 The hash functions learned by SVMKF represents a trade-off between kernel SVM and linear SVM. [sent-130, score-0.81]
65 The method proposed here is labeled Two-Step Hashing (TSH), the steps are as follows: • • Step-1 : Solving the optimization problem in (2) using block coordinate decent (Algorithm 1) to obtain binary codes for each training data point. [sent-131, score-0.439]
66 Step-2: Solving the binary classification problem in (4) for each bit based on the binary codes obtained at Step-1 . [sent-132, score-0.452]
67 Solving binary quadratic problems Optimizing (2) in Step-1 for the entire binary code matrix can be difficult. [sent-134, score-0.36]
68 Moreover, we show that at each iteration, any pairwise Hamming affinity (or distance) based loss can be equivalently formulated as a binary quadratic problem. [sent-136, score-0.588]
69 z(k)∈ {−1,1}n, (7) where lk is the loss function defined on the k-th bit: lk (zi,k , zj,k) = L(zi,k , zj,k , z¯ i , z¯ j ; yij ) . [sent-144, score-0.49]
70 Based on the following proposition, we are able to rewrite any Hamming affinity (or distance) based loss function L(·) into a standard quadratic problem. [sent-150, score-0.484]
71 For any loss function l(z1, z2) that is defined on a pair of binary input variables z1, z2 ∈ {− 1, 1} and l(1, 1) = l(− 1, 1) , l(1, 1) = l(1, 1), we can define a quadratic function g(z1, z2) that is equal to l(z1, z2). [sent-152, score-0.441]
72 (9) (10) Here l(11), l(−11) are constants, l(11) is the loss output on identical input pair: l(11) = l(1, 1), and l(−11) is the loss output on distinct input pair: l(−11) = l(−1, 1). [sent-157, score-0.446]
73 Any hash loss function l(·, ·) which is defined on the Hamming affinity between, or Hamming distance of, data − − 22555544 pairs is able to meet the requirement that: l(1, 1) = l(−1, −1) , l(1, −1) = l(1, −1). [sent-167, score-1.082]
74 Here we describe a selection of such loss functions, most of which arise from recently proposed hashing methods. [sent-197, score-0.643]
75 We evaluate these loss functions in the Experiments Section below. [sent-198, score-0.367]
76 If not specified, yij = 1if the data pair is similar, and yij = −1 if the data pair is dissimilar. [sent-200, score-0.324]
77 TSH-KSH The KSH loss function is based on Hamming affinity using ? [sent-202, score-0.408]
78 MDSH also uses a similar form of loss function (weighted Hamming affinity instead): LKSH(zi, zj) = (z? [sent-204, score-0.408]
79 (17) Table 2: Training time (in seconds) for TSH using different loss functions, and several other supervised methods on 3 datasets. [sent-208, score-0.297]
80 Note that the second step of learning the hash functions can be easily parallelised. [sent-211, score-0.772]
81 Here d¯ is the average Euclidean distance of top 100 nearing neighbours and t is 22555555 Table 1: Results (using hash codes of 32 bits) of TSH using different loss functions, and a selection of other supervised and unsupervised methods on 3 datasets. [sent-228, score-1.128]
82 The results show that Step-1 of our method is able to generate effective binary codes that outperforms those of competing methods on the training data. [sent-230, score-0.297]
83 If not specified, our method TSH use SVM with RBF kernel as hash functions. [sent-243, score-0.666]
84 Following the same setting as other hash methods [8, 13], we generate pseudo-labels for supervised methods according to the ? [sent-253, score-0.683]
85 In detail, a data point is labelled as a relevant neighbour to the query if it lies in the top 2 perlowing a common setting in many supervised hashing methods [5, 8, 10], we randomly select 2000 examples as testing queries, and the rest is served as database. [sent-255, score-0.522]
86 Using different loss functions We evaluate the performance of our method TSH using different loss functions on 3 datasets: LabelMe, MNIST, CIFAR10. [sent-260, score-0.734]
87 STHs-RBF is the STHs method using RBF kernel hash functions. [sent-264, score-0.666]
88 Our method also uses SVM with RBF kernel as hash functions. [sent-265, score-0.666]
89 This demonstrates the effectiveness of coordinate descent based hashing codes learning procedure (Step 1of our framework). [sent-275, score-0.632]
90 Compared to STHs-RBF, even though we are using the same formate of hash function, our overall objective function and the bit-wise binary code inference algorithm may be more effective. [sent-276, score-0.82]
91 Notice that in the second step, learning hash functions by binary classification can be easily paralleled which would make our method even more efficient. [sent-296, score-0.891]
92 (satD−minoserpCb120864 08BinaryT S coH d−eRKLS16FtleBuVmnMgpth(enum24brofits)32 Figure 5: Code compression time using different hash functions. [sent-299, score-0.609]
93 Using different hash functions We evaluate our method using different hash functions. [sent-304, score-1.362]
94 The hash functions are SVM with RBF kernel (TSH-RBF), linear SVM with kernel transferred feature (TSH-KF), linear SVM (TSH-LSVM), Adaboost with decision-stump (TSH-Stump, 2000 iterations). [sent-305, score-0.886]
95 The testing time for different hash functions are shown in Fig. [sent-308, score-0.781]
96 It shows that the kernel hash functions (TSH-RBF and TSH-KF) achieve best performance in similarity search. [sent-310, score-0.832]
97 However, the testing of linear hash functions is much faster than kernel hash functions. [sent-311, score-1.447]
98 Conclusion We have shown that it is possible to place a wide variety of learning-based hashing methods into a unified framework, and that doing so provides insights into the strengths, weaknesses, and commonality between various competing methods. [sent-327, score-0.42]
99 One of the key insights is the fact that the code generation and hash function learning processes may be seen as separate steps, and that the latter may accurately be formulated as a classification problem. [sent-328, score-0.702]
100 Iterative quantization: a procrustean approach to learning binary codes for large-scale image retrieval. [sent-356, score-0.293]
wordName wordTfidf (topN-words)
[('hash', 0.609), ('hashing', 0.42), ('ksh', 0.225), ('loss', 0.223), ('hamming', 0.176), ('yij', 0.162), ('affinity', 0.162), ('codes', 0.155), ('functions', 0.144), ('mdsh', 0.137), ('binary', 0.119), ('bre', 0.111), ('mlh', 0.098), ('tsh', 0.088), ('splh', 0.087), ('supervised', 0.074), ('perceptron', 0.072), ('lableme', 0.069), ('zj', 0.062), ('rbf', 0.061), ('bit', 0.059), ('bqp', 0.059), ('zi', 0.058), ('kernel', 0.057), ('cyclic', 0.053), ('quadratic', 0.053), ('spectral', 0.051), ('code', 0.051), ('decent', 0.05), ('mnist', 0.05), ('mz', 0.048), ('itq', 0.045), ('sph', 0.045), ('svm', 0.043), ('az', 0.043), ('unsupervised', 0.042), ('lk', 0.041), ('simplifies', 0.041), ('hengel', 0.04), ('labelme', 0.04), ('dh', 0.04), ('proposition', 0.039), ('bres', 0.039), ('izj', 0.039), ('spher', 0.039), ('sths', 0.039), ('relaxation', 0.038), ('shen', 0.038), ('coordinate', 0.038), ('reconstructive', 0.038), ('exponential', 0.037), ('optimization', 0.037), ('kin', 0.037), ('sth', 0.036), ('dissimilar', 0.035), ('lsh', 0.033), ('ijl', 0.032), ('klsh', 0.032), ('equivalently', 0.031), ('den', 0.03), ('adaboost', 0.03), ('decomposes', 0.029), ('types', 0.029), ('eigenfunctions', 0.029), ('testing', 0.028), ('tiny', 0.028), ('bits', 0.028), ('coupling', 0.028), ('hinge', 0.028), ('iteration', 0.028), ('coupled', 0.027), ('quantization', 0.026), ('inductive', 0.026), ('distance', 0.025), ('embeddings', 0.024), ('able', 0.023), ('function', 0.023), ('picked', 0.023), ('similarity', 0.022), ('surrogate', 0.022), ('reformulated', 0.022), ('block', 0.022), ('datasets', 0.021), ('retrieved', 0.021), ('kernelized', 0.021), ('accommodate', 0.02), ('elastic', 0.02), ('written', 0.019), ('transferred', 0.019), ('truth', 0.019), ('learning', 0.019), ('embedding', 0.019), ('spherical', 0.019), ('par', 0.019), ('inference', 0.018), ('steps', 0.018), ('matrix', 0.018), ('kulis', 0.018), ('pairs', 0.017), ('agh', 0.017)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000001 13 iccv-2013-A General Two-Step Approach to Learning-Based Hashing
Author: Guosheng Lin, Chunhua Shen, David Suter, Anton van_den_Hengel
Abstract: Most existing approaches to hashing apply a single form of hash function, and an optimization process which is typically deeply coupled to this specific form. This tight coupling restricts the flexibility of the method to respond to the data, and can result in complex optimization problems that are difficult to solve. Here we propose a flexible yet simple framework that is able to accommodate different types of loss functions and hash functions. This framework allows a number of existing approaches to hashing to be placed in context, and simplifies the development of new problemspecific hashing methods. Our framework decomposes the hashing learning problem into two steps: hash bit learning and hash function learning based on the learned bits. The first step can typically be formulated as binary quadratic problems, and the second step can be accomplished by training standard binary classifiers. Both problems have been extensively studied in the literature. Our extensive experiments demonstrate that the proposed framework is effective, flexible and outperforms the state-of-the-art.
2 0.65272909 229 iccv-2013-Large-Scale Video Hashing via Structure Learning
Author: Guangnan Ye, Dong Liu, Jun Wang, Shih-Fu Chang
Abstract: Recently, learning based hashing methods have become popular for indexing large-scale media data. Hashing methods map high-dimensional features to compact binary codes that are efficient to match and robust in preserving original similarity. However, most of the existing hashing methods treat videos as a simple aggregation of independent frames and index each video through combining the indexes of frames. The structure information of videos, e.g., discriminative local visual commonality and temporal consistency, is often neglected in the design of hash functions. In this paper, we propose a supervised method that explores the structure learning techniques to design efficient hash functions. The proposed video hashing method formulates a minimization problem over a structure-regularized empirical loss. In particular, the structure regularization exploits the common local visual patterns occurring in video frames that are associated with the same semantic class, and simultaneously preserves the temporal consistency over successive frames from the same video. We show that the minimization objective can be efficiently solved by an Acceler- ated Proximal Gradient (APG) method. Extensive experiments on two large video benchmark datasets (up to around 150K video clips with over 12 million frames) show that the proposed method significantly outperforms the state-ofthe-art hashing methods.
3 0.55869091 83 iccv-2013-Complementary Projection Hashing
Author: Zhongming Jin, Yao Hu, Yue Lin, Debing Zhang, Shiding Lin, Deng Cai, Xuelong Li
Abstract: Recently, hashing techniques have been widely applied to solve the approximate nearest neighbors search problem in many vision applications. Generally, these hashing approaches generate 2c buckets, where c is the length of the hash code. A good hashing method should satisfy the following two requirements: 1) mapping the nearby data points into the same bucket or nearby (measured by xue long l i opt . ac . cn @ a(a)b(b) the Hamming distance) buckets. 2) all the data points are evenly distributed among all the buckets. In this paper, we propose a novel algorithm named Complementary Projection Hashing (CPH) to find the optimal hashing functions which explicitly considers the above two requirements. Specifically, CPHaims at sequentiallyfinding a series ofhyperplanes (hashing functions) which cross the sparse region of the data. At the same time, the data points are evenly distributed in the hypercubes generated by these hyperplanes. The experiments comparing with the state-of-the-art hashing methods demonstrate the effectiveness of the proposed method.
4 0.5420593 239 iccv-2013-Learning Hash Codes with Listwise Supervision
Author: Jun Wang, Wei Liu, Andy X. Sun, Yu-Gang Jiang
Abstract: Hashing techniques have been intensively investigated in the design of highly efficient search engines for largescale computer vision applications. Compared with prior approximate nearest neighbor search approaches like treebased indexing, hashing-based search schemes have prominent advantages in terms of both storage and computational efficiencies. Moreover, the procedure of devising hash functions can be easily incorporated into sophisticated machine learning tools, leading to data-dependent and task-specific compact hash codes. Therefore, a number of learning paradigms, ranging from unsupervised to supervised, have been applied to compose appropriate hash functions. How- ever, most of the existing hash function learning methods either treat hash function design as a classification problem or generate binary codes to satisfy pairwise supervision, and have not yet directly optimized the search accuracy. In this paper, we propose to leverage listwise supervision into a principled hash function learning framework. In particular, the ranking information is represented by a set of rank triplets that can be used to assess the quality of ranking. Simple linear projection-based hash functions are solved efficiently through maximizing the ranking quality over the training data. We carry out experiments on large image datasets with size up to one million and compare with the state-of-the-art hashing techniques. The extensive results corroborate that our learned hash codes via listwise supervision can provide superior search accuracy without incurring heavy computational overhead.
5 0.52912039 409 iccv-2013-Supervised Binary Hash Code Learning with Jensen Shannon Divergence
Author: Lixin Fan
Abstract: This paper proposes to learn binary hash codes within a statistical learning framework, in which an upper bound of the probability of Bayes decision errors is derived for different forms of hash functions and a rigorous proof of the convergence of the upper bound is presented. Consequently, minimizing such an upper bound leads to consistent performance improvements of existing hash code learning algorithms, regardless of whether original algorithms are unsupervised or supervised. This paper also illustrates a fast hash coding method that exploits simple binary tests to achieve orders of magnitude improvement in coding speed as compared to projection based methods.
7 0.14127606 400 iccv-2013-Stable Hyper-pooling and Query Expansion for Event Detection
9 0.13155113 337 iccv-2013-Random Grids: Fast Approximate Nearest Neighbors and Range Searching for Image Search
10 0.10660149 162 iccv-2013-Fast Subspace Search via Grassmannian Based Hashing
11 0.079349756 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
12 0.07798969 221 iccv-2013-Joint Inverted Indexing
13 0.067035243 319 iccv-2013-Point-Based 3D Reconstruction of Thin Objects
14 0.058890995 10 iccv-2013-A Framework for Shape Analysis via Hilbert Space Embedding
15 0.054079879 222 iccv-2013-Joint Learning of Discriminative Prototypes and Large Margin Nearest Neighbor Classifiers
16 0.051162921 123 iccv-2013-Domain Adaptive Classification
17 0.048003424 384 iccv-2013-Semi-supervised Robust Dictionary Learning via Efficient l-Norms Minimization
18 0.047972836 437 iccv-2013-Unsupervised Random Forest Manifold Alignment for Lipreading
19 0.047758441 238 iccv-2013-Learning Graphs to Match
20 0.047130402 333 iccv-2013-Quantize and Conquer: A Dimensionality-Recursive Solution to Clustering, Vector Quantization, and Image Retrieval
topicId topicWeight
[(0, 0.133), (1, 0.088), (2, -0.092), (3, -0.113), (4, -0.075), (5, 0.437), (6, 0.01), (7, 0.012), (8, -0.326), (9, 0.2), (10, -0.32), (11, 0.159), (12, -0.038), (13, -0.223), (14, -0.017), (15, 0.055), (16, -0.167), (17, 0.212), (18, -0.203), (19, 0.08), (20, -0.005), (21, 0.088), (22, 0.037), (23, 0.015), (24, 0.047), (25, -0.019), (26, -0.047), (27, 0.006), (28, -0.014), (29, -0.006), (30, 0.026), (31, 0.012), (32, 0.011), (33, 0.006), (34, -0.041), (35, 0.004), (36, -0.008), (37, 0.014), (38, -0.026), (39, -0.008), (40, -0.021), (41, -0.01), (42, -0.004), (43, -0.021), (44, -0.002), (45, 0.008), (46, 0.008), (47, 0.007), (48, -0.025), (49, -0.02)]
simIndex simValue paperId paperTitle
same-paper 1 0.96177357 13 iccv-2013-A General Two-Step Approach to Learning-Based Hashing
Author: Guosheng Lin, Chunhua Shen, David Suter, Anton van_den_Hengel
Abstract: Most existing approaches to hashing apply a single form of hash function, and an optimization process which is typically deeply coupled to this specific form. This tight coupling restricts the flexibility of the method to respond to the data, and can result in complex optimization problems that are difficult to solve. Here we propose a flexible yet simple framework that is able to accommodate different types of loss functions and hash functions. This framework allows a number of existing approaches to hashing to be placed in context, and simplifies the development of new problemspecific hashing methods. Our framework decomposes the hashing learning problem into two steps: hash bit learning and hash function learning based on the learned bits. The first step can typically be formulated as binary quadratic problems, and the second step can be accomplished by training standard binary classifiers. Both problems have been extensively studied in the literature. Our extensive experiments demonstrate that the proposed framework is effective, flexible and outperforms the state-of-the-art.
2 0.95461756 83 iccv-2013-Complementary Projection Hashing
Author: Zhongming Jin, Yao Hu, Yue Lin, Debing Zhang, Shiding Lin, Deng Cai, Xuelong Li
Abstract: Recently, hashing techniques have been widely applied to solve the approximate nearest neighbors search problem in many vision applications. Generally, these hashing approaches generate 2c buckets, where c is the length of the hash code. A good hashing method should satisfy the following two requirements: 1) mapping the nearby data points into the same bucket or nearby (measured by xue long l i opt . ac . cn @ a(a)b(b) the Hamming distance) buckets. 2) all the data points are evenly distributed among all the buckets. In this paper, we propose a novel algorithm named Complementary Projection Hashing (CPH) to find the optimal hashing functions which explicitly considers the above two requirements. Specifically, CPHaims at sequentiallyfinding a series ofhyperplanes (hashing functions) which cross the sparse region of the data. At the same time, the data points are evenly distributed in the hypercubes generated by these hyperplanes. The experiments comparing with the state-of-the-art hashing methods demonstrate the effectiveness of the proposed method.
3 0.93729419 239 iccv-2013-Learning Hash Codes with Listwise Supervision
Author: Jun Wang, Wei Liu, Andy X. Sun, Yu-Gang Jiang
Abstract: Hashing techniques have been intensively investigated in the design of highly efficient search engines for largescale computer vision applications. Compared with prior approximate nearest neighbor search approaches like treebased indexing, hashing-based search schemes have prominent advantages in terms of both storage and computational efficiencies. Moreover, the procedure of devising hash functions can be easily incorporated into sophisticated machine learning tools, leading to data-dependent and task-specific compact hash codes. Therefore, a number of learning paradigms, ranging from unsupervised to supervised, have been applied to compose appropriate hash functions. How- ever, most of the existing hash function learning methods either treat hash function design as a classification problem or generate binary codes to satisfy pairwise supervision, and have not yet directly optimized the search accuracy. In this paper, we propose to leverage listwise supervision into a principled hash function learning framework. In particular, the ranking information is represented by a set of rank triplets that can be used to assess the quality of ranking. Simple linear projection-based hash functions are solved efficiently through maximizing the ranking quality over the training data. We carry out experiments on large image datasets with size up to one million and compare with the state-of-the-art hashing techniques. The extensive results corroborate that our learned hash codes via listwise supervision can provide superior search accuracy without incurring heavy computational overhead.
4 0.89411891 409 iccv-2013-Supervised Binary Hash Code Learning with Jensen Shannon Divergence
Author: Lixin Fan
Abstract: This paper proposes to learn binary hash codes within a statistical learning framework, in which an upper bound of the probability of Bayes decision errors is derived for different forms of hash functions and a rigorous proof of the convergence of the upper bound is presented. Consequently, minimizing such an upper bound leads to consistent performance improvements of existing hash code learning algorithms, regardless of whether original algorithms are unsupervised or supervised. This paper also illustrates a fast hash coding method that exploits simple binary tests to achieve orders of magnitude improvement in coding speed as compared to projection based methods.
5 0.87333685 229 iccv-2013-Large-Scale Video Hashing via Structure Learning
Author: Guangnan Ye, Dong Liu, Jun Wang, Shih-Fu Chang
Abstract: Recently, learning based hashing methods have become popular for indexing large-scale media data. Hashing methods map high-dimensional features to compact binary codes that are efficient to match and robust in preserving original similarity. However, most of the existing hashing methods treat videos as a simple aggregation of independent frames and index each video through combining the indexes of frames. The structure information of videos, e.g., discriminative local visual commonality and temporal consistency, is often neglected in the design of hash functions. In this paper, we propose a supervised method that explores the structure learning techniques to design efficient hash functions. The proposed video hashing method formulates a minimization problem over a structure-regularized empirical loss. In particular, the structure regularization exploits the common local visual patterns occurring in video frames that are associated with the same semantic class, and simultaneously preserves the temporal consistency over successive frames from the same video. We show that the minimization objective can be efficiently solved by an Acceler- ated Proximal Gradient (APG) method. Extensive experiments on two large video benchmark datasets (up to around 150K video clips with over 12 million frames) show that the proposed method significantly outperforms the state-ofthe-art hashing methods.
8 0.33496898 221 iccv-2013-Joint Inverted Indexing
9 0.29485062 400 iccv-2013-Stable Hyper-pooling and Query Expansion for Event Detection
10 0.24803853 337 iccv-2013-Random Grids: Fast Approximate Nearest Neighbors and Range Searching for Image Search
11 0.24119276 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
12 0.2214905 171 iccv-2013-Fix Structured Learning of 2013 ICCV paper k2opt.pdf
13 0.21764775 287 iccv-2013-Neighbor-to-Neighbor Search for Fast Coding of Feature Vectors
14 0.21092661 332 iccv-2013-Quadruplet-Wise Image Similarity Learning
15 0.20165233 347 iccv-2013-Recursive Estimation of the Stein Center of SPD Matrices and Its Applications
16 0.20155308 227 iccv-2013-Large-Scale Image Annotation by Efficient and Robust Kernel Metric Learning
17 0.19745968 248 iccv-2013-Learning to Rank Using Privileged Information
18 0.19658121 112 iccv-2013-Detecting Irregular Curvilinear Structures in Gray Scale and Color Imagery Using Multi-directional Oriented Flux
19 0.18657315 178 iccv-2013-From Semi-supervised to Transfer Counting of Crowds
20 0.1822554 34 iccv-2013-Abnormal Event Detection at 150 FPS in MATLAB
topicId topicWeight
[(2, 0.549), (7, 0.037), (26, 0.037), (31, 0.03), (42, 0.063), (64, 0.022), (73, 0.012), (77, 0.016), (89, 0.11), (98, 0.015)]
simIndex simValue paperId paperTitle
same-paper 1 0.90130186 13 iccv-2013-A General Two-Step Approach to Learning-Based Hashing
Author: Guosheng Lin, Chunhua Shen, David Suter, Anton van_den_Hengel
Abstract: Most existing approaches to hashing apply a single form of hash function, and an optimization process which is typically deeply coupled to this specific form. This tight coupling restricts the flexibility of the method to respond to the data, and can result in complex optimization problems that are difficult to solve. Here we propose a flexible yet simple framework that is able to accommodate different types of loss functions and hash functions. This framework allows a number of existing approaches to hashing to be placed in context, and simplifies the development of new problemspecific hashing methods. Our framework decomposes the hashing learning problem into two steps: hash bit learning and hash function learning based on the learned bits. The first step can typically be formulated as binary quadratic problems, and the second step can be accomplished by training standard binary classifiers. Both problems have been extensively studied in the literature. Our extensive experiments demonstrate that the proposed framework is effective, flexible and outperforms the state-of-the-art.
2 0.88360643 294 iccv-2013-Offline Mobile Instance Retrieval with a Small Memory Footprint
Author: Jayaguru Panda, Michael S. Brown, C.V. Jawahar
Abstract: Existing mobile image instance retrieval applications assume a network-based usage where image features are sent to a server to query an online visual database. In this scenario, there are no restrictions on the size of the visual database. This paper, however, examines how to perform this same task offline, where the entire visual index must reside on the mobile device itself within a small memory footprint. Such solutions have applications on location recognition and product recognition. Mobile instance retrieval requires a significant reduction in the visual index size. To achieve this, we describe a set of strategies that can reduce the visual index up to 60-80 compared to a scatannd raerddu iens tthaen vceis rueatrli ienvdaelx xim upple tom 6en0t-8at0io ×n found on ddte osk atops or servers. While our proposed reduction steps affect the overall mean Average Precision (mAP), they are able to maintain a good Precision for the top K results (PK). We argue that for such offline application, maintaining a good PK is sufficient. The effectiveness of this approach is demonstrated on several standard databases. A working application designed for a remote historical site is also presented. This application is able to reduce an 50,000 image index structure to 25 MBs while providing a precision of 97% for P10 and 100% for P1.
3 0.84529841 446 iccv-2013-Visual Semantic Complex Network for Web Images
Author: Shi Qiu, Xiaogang Wang, Xiaoou Tang
Abstract: This paper proposes modeling the complex web image collections with an automatically generated graph structure called visual semantic complex network (VSCN). The nodes on this complex network are clusters of images with both visual and semantic consistency, called semantic concepts. These nodes are connected based on the visual and semantic correlations. Our VSCN with 33, 240 concepts is generated from a collection of 10 million web images. 1 A great deal of valuable information on the structures of the web image collections can be revealed by exploring the VSCN, such as the small-world behavior, concept community, indegree distribution, hubs, and isolated concepts. It not only helps us better understand the web image collections at a macroscopic level, but also has many important practical applications. This paper presents two application examples: content-based image retrieval and image browsing. Experimental results show that the VSCN leads to significant improvement on both the precision of image retrieval (over 200%) and user experience for image browsing.
4 0.83418989 352 iccv-2013-Revisiting Example Dependent Cost-Sensitive Learning with Decision Trees
Author: Oisin Mac Aodha, Gabriel J. Brostow
Abstract: Typical approaches to classification treat class labels as disjoint. For each training example, it is assumed that there is only one class label that correctly describes it, and that all other labels are equally bad. We know however, that good and bad labels are too simplistic in many scenarios, hurting accuracy. In the realm of example dependent costsensitive learning, each label is instead a vector representing a data point’s affinity for each of the classes. At test time, our goal is not to minimize the misclassification rate, but to maximize that affinity. We propose a novel example dependent cost-sensitive impurity measure for decision trees. Our experiments show that this new impurity measure improves test performance while still retaining the fast test times of standard classification trees. We compare our approach to classification trees and other cost-sensitive methods on three computer vision problems, tracking, descriptor matching, and optical flow, and show improvements in all three domains.
5 0.82194161 191 iccv-2013-Handling Uncertain Tags in Visual Recognition
Author: Arash Vahdat, Greg Mori
Abstract: Gathering accurate training data for recognizing a set of attributes or tags on images or videos is a challenge. Obtaining labels via manual effort or from weakly-supervised data typically results in noisy training labels. We develop the FlipSVM, a novel algorithm for handling these noisy, structured labels. The FlipSVM models label noise by “flipping ” labels on training examples. We show empirically that the FlipSVM is effective on images-and-attributes and video tagging datasets.
6 0.80606872 214 iccv-2013-Improving Graph Matching via Density Maximization
7 0.80533773 244 iccv-2013-Learning View-Invariant Sparse Representations for Cross-View Action Recognition
8 0.76855201 374 iccv-2013-Salient Region Detection by UFO: Uniqueness, Focusness and Objectness
9 0.71249151 239 iccv-2013-Learning Hash Codes with Listwise Supervision
10 0.69268274 153 iccv-2013-Face Recognition Using Face Patch Networks
11 0.69206834 409 iccv-2013-Supervised Binary Hash Code Learning with Jensen Shannon Divergence
12 0.68189985 83 iccv-2013-Complementary Projection Hashing
13 0.67122406 322 iccv-2013-Pose Estimation and Segmentation of People in 3D Movies
14 0.66095418 229 iccv-2013-Large-Scale Video Hashing via Structure Learning
15 0.6130479 313 iccv-2013-Person Re-identification by Salience Matching
16 0.61279863 248 iccv-2013-Learning to Rank Using Privileged Information
17 0.60721475 368 iccv-2013-SYM-FISH: A Symmetry-Aware Flip Invariant Sketch Histogram Shape Descriptor
18 0.60330957 73 iccv-2013-Class-Specific Simplex-Latent Dirichlet Allocation for Image Classification
19 0.59890807 378 iccv-2013-Semantic-Aware Co-indexing for Image Retrieval
20 0.58891588 443 iccv-2013-Video Synopsis by Heterogeneous Multi-source Correlation