iccv iccv2013 iccv2013-409 knowledge-graph by maker-knowledge-mining
Source: pdf
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.
Reference: text
sentIndex sentText sentNum sentScore
1 org 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. [sent-2, score-1.981]
2 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. [sent-3, score-0.89]
3 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. [sent-4, score-0.975]
4 Introduction Mapping high dimensional image data into binary codes plays an indispensable role for efficient storing and searching of large scale image databases. [sent-6, score-0.19]
5 Owing to storage efficiency and sublinear search time, compact binary codes have been widely applied to various vision applications such as object recognition [20], image retrieval [23], lo- cal descriptor matching [6, 19] and binary feature matching [2, 9, 17, 21] etc. [sent-7, score-0.325]
6 Learning compact binary code has been traditionally treated as a “similarity-preserving” problem with objective to map similar data points into similar binary codes. [sent-8, score-0.311]
7 Often original data points are assumed to reside in a highdimensional Euclidean space while (dis-)similarity between binary codes is quantified by Hamming distance. [sent-9, score-0.19]
8 Recent work demonstrate considerable performance improvements with a discernible shift of research focus to (semi-)supervised approaches, in which the learning of hash functions is invariably governed by some forms of label information. [sent-14, score-0.773]
9 Despite empirical justifications with large databases, the choice of objective functions for these methods is to some extent heuristic and it remains an open question to exploit label information in a consistent and theoretically sound manner. [sent-16, score-0.121]
10 The research presented in this paper, therefore, proposes to formulate binary hash code learning 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 (Section 3). [sent-17, score-1.768]
11 Furthermore, a rigours proof of the convergence of the upper bound for arbitrary sequential learning algorithms is presented in Theorem 1. [sent-18, score-0.331]
12 Consequently, minimizing the upper bound for existing hash code learning algorithms leads to consistent performance improvements, regardless of whether original algorithms are unsupervised or supervised (Section 4). [sent-19, score-0.923]
13 The processing time of converting a query data point into binary codes (i. [sent-20, score-0.224]
14 coding time) is a crucial performance parameter for nearest neighbour search algorithms. [sent-22, score-0.126]
15 Having short coding time is of particular interest for vision applications such as fast keypoint recognition [16] and image localization [18] etc, in which query images may contain up to 10K features and the coding time amounts to a significant portion of the total processing time. [sent-23, score-0.246]
16 While the coding time is considered a constant for projection based hash functions, we demonstrate in Section 4. [sent-24, score-0.707]
17 4 that it actually can be reduced by order of magnitudes by exploiting simple yet discriminative binary tests ofinput feature vectors. [sent-25, score-0.191]
18 The proposed Haar-Like hash function, albeit suboptimal in terms of precision rate, is preferred due to its high speed and computational simplicity for real-time applications running on mobile devices. [sent-26, score-0.728]
19 Related Work We review below only supervised hash code learning methods and refer readers to two journal articles [19, 4] for thorough reviews of this active research area. [sent-28, score-0.783]
20 2616 Supervised hash learning methods: Kullis and Darrell proposed to minimize reconstruction errors between both similar and dissimilar data points [7]. [sent-29, score-0.668]
21 [12] used a supervised term to minimize empirical errors between data point pairs associated with three types of label i. [sent-32, score-0.095]
22 Motivated by the hinger loss in SVMs, Norouzi and Fleet proposed to minimize the upper bound on empirical loss of similar (or dissimilar) point pairs [13], and extended the method to incorporate ranking loss defined on triplets of binary codes [14]. [sent-35, score-0.481]
23 Similar loss function was used in [10] to encode proximity comparison information of labelled data. [sent-36, score-0.079]
24 Binary tests: There are abundant literatures related to binary test descriptors. [sent-39, score-0.103]
25 Owing to its fast calculation speed, binary test has long been adopted to extract Haar-like features for real-time object detection [22]. [sent-40, score-0.103]
26 BRIEF descriptor completely abandoned the training phase, but had to resort to long code lengths ranging from 128 to 256 bits [2]. [sent-43, score-0.166]
27 More recent ORB descriptor decorrelated BRIEF features by using a learning step to search for binary tests with means near 0. [sent-44, score-0.212]
28 D-Brief descriptors [21] was trained to reduce code lengths while maintaining high discriminative power. [sent-46, score-0.115]
29 Theoretic Analysis This section lays down theoretic foundation for a sequential binary hash code learning framework and presents a rigorous proof of the convergence property of the framework. [sent-50, score-1.073]
30 A Statistical Learning Framework for Binary Code Learning We treat learning optimal binary codes as a typical multiclass classification problem, in which a p-dimensional observation x = (x1, x2 , . [sent-53, score-0.239]
31 A hash function h : Rp → {0, 1} is often treated as a mapping of an observation x →to { a single bo fitt binary ceodd aes. [sent-71, score-0.694]
32 Depending on the outcome of the hash function, the entire sample space S = Rp is partitioned into two complementary B-subsets that are defined as follows: [b]hS = {x ∈ S | h(x) = b }, b = 0 or 1. [sent-72, score-0.591]
33 Thi∪s d[1e]finition of B-s∩ub [s1e]ts i=s generic sapnedcaciaclolym [m∅]o∅dates to different families of hash functions such as linear transform, kernelized or more complex hash functions used e. [sent-74, score-1.374]
34 , hK} partitions the space S into 2K non-overlapping B-sub}se ptsa1r , which are intersections of B-subsets of each hash function: [b1b2. [sent-80, score-0.591]
35 When ambiguity seems unlikely, hK and S are omitted and binary codes are denoted as b1. [sent-94, score-0.19]
36 bK] is observed, the posterior probability of class Cm is given by Bayes Theorem: πm ? [sent-101, score-0.059]
37 K The probability of Bayes decision error by choosing the class MAP estimate C m˜ that has the largest posterior probability is: π m˜ ? [sent-114, score-0.135]
38 =1 K and the total probability of error for a given set of hash functions hK is: P(e | hK) = ? [sent-125, score-0.721]
39 Our goal is to seek a set of hash functions that minimizes the total probability of Bayes decision errors: h∗K = argmhiKnP(e | hK). [sent-133, score-0.763]
40 (2) 1Depending on different hash functions, certain binary codes may correspond to empty B-subsets. [sent-134, score-0.781]
41 2617 Minimizing the objective function (2) is akin to minimizing empirical training error in recent supervised hashing learning methods [24, 23, 12]. [sent-136, score-0.213]
42 ) function in the class MAP estimate makes it difficult to analyze the convergence property of the minimization of (2). [sent-138, score-0.058]
43 In the rest of the paper, we first present a rigorous proof of the convergence of an upper bound on P(e) and then illustrate how to use the upper bound to supervise a variety of hash code learning algorithms. [sent-139, score-1.143]
44 Since H(π) is a constant for a given problem, it immediately follows that the upper bound of the probability of error is minimized by maximizing (4): h∗K = argmhaKxJSDπ(p1,. [sent-193, score-0.174]
45 (5) Remark 1: The JSD measure as an objective function can be intuitively interpreted as the combination of an unsupervised and a supervised terms: maximizing the first term H? [sent-197, score-0.07]
46 ,N, K, L begin hK = ∅; πi = NNi; Ii∅ = 1Ni×1; where Ni := #data points in class i; hl = sgn(xwl) and H = sgn(xW) , where W = [w1, . [sent-214, score-0.093]
47 These two opposing terms conspire to minimize the upper bound of the probability of MAP decision errors. [sent-226, score-0.216]
48 Remark 2: Owing to the convexity of KL divergence, Theorem 1 below proves that the upper bound of the Bayesian decision error is monotonically decreasing when a sequential learning approach repeatedly adds more hash functions except for some pathological cases. [sent-227, score-0.989]
49 = Remark 3: the condition above is satisfied even for random hash functions and thus Theorem 1 also proves the convergence property of the well-known Locality Sensitive Hashing (LSH) method [5]. [sent-314, score-0.72]
50 in the following section, to select the hash function which maximizes JSD at each step is a preferred option to random selection of hash functions. [sent-321, score-1.214]
51 Experiments Section 3 lays down theoretic foundation for a sequential binary hash code learning framework. [sent-323, score-0.965]
52 In this section, we demonstrate how to adopt this generic framework to train existing learning algorithms with labelled datasets. [sent-324, score-0.086]
53 Four publicly available datasets, namely CIFAR10, CIFAR100, LabelMe22k and SIFT10K, are used to compare the proposed hash code learning approach against existing methods. [sent-336, score-0.713]
54 100 nearest neighbours are provided for each class and there is one query SIFT descriptor per class that is used for testing in our experiments. [sent-350, score-0.084]
55 Two examples precision curves measured at Hamming radius 0 and 1for hash codes lengths ranging from 8 to 64 bits are illustrated in Figure 1 (left column). [sent-353, score-0.851]
56 Mean average precision (mAP) are often used to quantify performances of different methods. [sent-354, score-0.117]
57 In this work, we measure mAP only for Hamming radius no greater than 3 since high precision rates prevent unnecessarily long lists of retrieved items. [sent-355, score-0.127]
58 Sequential Learning with JSD We first demonstrate how to supervise the well-known LSH with a sequential learning algorithm 1. [sent-358, score-0.162]
59 A set of L candidate linear projections wl ∈ Rp×1, l= 1, . [sent-359, score-0.121]
60 L are randomly generated and applied to∈ tRhe whole dataset hl = sgn(xwl)2. [sent-362, score-0.068]
61 Outcomes of candidate projections are concatenated into a binary matrix H ∈ {0, 1}N×L. [sent-363, score-0.193]
62 Ibi1 Binary vector K ∈ {0, 1}Ni 1 indicates those points that are associated with∈ cl {a0s,s1 1i} and binary code b1. [sent-370, score-0.176]
63 This pbi1 K∩[1]hl way can be efficiently computed by counting “1” bits in the intersection of K and corresponding column vectors hl, and thereafter normalizing the count with Ibi1 pib1. [sent-374, score-0.081]
64 The whole JSD-based learning process is implemented as a binary tree growing algorithm in MATLAB codes. [sent-379, score-0.152]
65 This supervised approach leads to significant performance improvement as compared to random projection adopted in LSH. [sent-383, score-0.106]
66 Figure 1 illustrates improvements in precision rates measured on CIFAR10 dataset with both Euclidean neighbour and semantic labels. [sent-384, score-0.234]
67 Figure 2 (left) illustrates how the precision of JSD algorithm is positively related to the number of candidate hash functions L. [sent-386, score-0.804]
68 Whereas a small number of 200 candidates lead to significant improvement over random projections in LSH, 50 times more candidates improves about 10% precision only. [sent-387, score-0.133]
69 Figure 3 shows that there is a graceful precision loss due to noisy or partial labels. [sent-389, score-0.122]
70 With 50% random labels, the precision of JSD learning decreases about 20% yet still outperforming LSH. [sent-390, score-0.129]
71 Training with 1% labels, the incurred precision loss is no more than 5%. [sent-391, score-0.151]
72 JSD improvements of other methods Algorithm 1 can also be used to improve other binary code learning methods with a minor modification, i. [sent-394, score-0.262]
73 by appending outputs of existing methods He ∈ {0, 1}N×K to candidate projection outcomes H ← H ∪ H∈e. [sent-396, score-0.103]
74 { 0T,h1is} generic approach o pfr exploiting ltacobmel eisn fHor ←ma tHion ∪ can be applied to any hash coding learning algorithms in a consistent manner. [sent-397, score-0.72]
75 Figures 4 illustrates performance improvements of one unsupervised (SH [26]) and three supervised methods (BRE [7], ITQ [3] and KSH [12]) measured on CIFAR10 dataset with Euclidean labels. [sent-399, score-0.107]
76 Quantitative performance comparison, in terms of mean average precision (mAP), are summarized in Figure 5 in which six sets of data/labels are used. [sent-401, score-0.08]
77 It is observed that performances of JSD-based learning approaches compare favourably with those of original methods in the majority of comparisons. [sent-402, score-0.086]
78 In the bottom two panels, however, performances in KSH/JSD column no longer excel but JSD learning methods still outperform the original methods in the majority of cases (with minor exceptions marked by “‡”). [sent-408, score-0.116]
79 stance, Table 1 summarizes numbers of hash functions that are selected from different methods in one example run. [sent-416, score-0.687]
80 In particular, the last column shows percentage of hash functions that are selected from corresponding learning methods, averaged over different lengths of hash codes. [sent-417, score-1.399]
81 Noticeably, KSH contributes the majority of selected hash functions and this seems in accordance with high precision rates of KSH reported in Figure 4 as well as Table 4. [sent-418, score-0.814]
82 First, the preparation time (Tp) of candidate matrix H is approximately proportional to the number of candidates L (also see Figure 2 right). [sent-422, score-0.085]
83 Instead, the processing time of converting a query data point into binary codes (i. [sent-444, score-0.224]
84 coding time) is a crucial performance parameter for nearest neighbour search algorithms. [sent-446, score-0.126]
85 While the coding time is often considered a constant for projection based hash functions, it actually can be reduced by order of magnitudes by exploiting simple yet discriminative binary tests of input feature vectors. [sent-447, score-0.898]
86 This family ∈o fR hash functions constitute a special subset of the well-known linear projections that have only two non-zero elements (1 and −1 respectively) in each column 2621 Figure 6. [sent-454, score-0.77]
87 Three columns on left: Precision-recall curves with varying code lengths. [sent-456, score-0.073]
88 Random selection of HALFs (rHALF) does not necessarily guarantee satisfactory precision rates, instead, we adopt the proposed JSD learning algorithm to boost precision rates of random HALFs (denoted as rHALF-JSD hereafter). [sent-465, score-0.256]
89 As compared with other methods, Figure 6 shows that the curve of rHALF-JSD (red solid line) lies almost exactly between unsupervised (LSH, rHALF and SH) and supervised methods (BRE, ITQ and KSH). [sent-467, score-0.07]
90 The practical value of rHALF-JSD lies in its extremely short coding time Tc (see Table 3). [sent-470, score-0.08]
91 Since there is no matrix multiplication involved, the per query coding time is at least two orders of magnitude faster than other projection based methods for 5 12-dimensional GIST vectors. [sent-471, score-0.175]
92 This speedup is particularly useful for real-time applications such as fast keypoint recognition [16] and image localization [18] in which query images may contain up to 10K features and the coding time amounts to a significant portion of the total processing time. [sent-472, score-0.166]
93 First, we formulated binary hash coding learning within a statistical learning framework in which an upper bound of the proba- Table3. [sent-476, score-1.012]
94 bility of Bayes decision errors is derived for arbitrary hash functions. [sent-485, score-0.633]
95 Since the convergence property of such a sequential learning method is rigorously proved, one is able to freely apply the JSD-based learning approach to different hash functions as long as sufficient number of labelled data are available. [sent-486, score-0.926]
96 Second, we proposed a very simple and fast hash function which is able to reduce the coding time by two order of magnitudes as compared with other projection based methods. [sent-488, score-0.735]
97 As for future work, we advocate the JSD-based learning approach as a generic framework to combine different learning algorithms. [sent-490, score-0.098]
98 Iterative quantization: A procrustean approach to learning binary codes. [sent-743, score-0.177]
99 Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. [sent-750, score-0.264]
100 Small codes and large image [21] [22] [23] [24] [25] [26] databases for recognition. [sent-862, score-0.087]
wordName wordTfidf (topN-words)
[('hash', 0.591), ('jsd', 0.509), ('hk', 0.22), ('hs', 0.143), ('ksh', 0.132), ('halfs', 0.106), ('binary', 0.103), ('functions', 0.096), ('codes', 0.087), ('rhalf', 0.085), ('precision', 0.08), ('coding', 0.08), ('code', 0.073), ('lsh', 0.072), ('sequential', 0.071), ('supervised', 0.07), ('bound', 0.07), ('upper', 0.07), ('hashing', 0.069), ('hl', 0.068), ('dhk', 0.064), ('hamming', 0.064), ('euclidean', 0.063), ('bayes', 0.061), ('tests', 0.06), ('bre', 0.06), ('vs', 0.059), ('divergence', 0.054), ('pi', 0.054), ('projections', 0.053), ('keypoint', 0.052), ('theorem', 0.051), ('bits', 0.051), ('rp', 0.051), ('learning', 0.049), ('itq', 0.049), ('jensen', 0.049), ('shannon', 0.049), ('preparation', 0.048), ('rates', 0.047), ('neighbour', 0.046), ('ts', 0.044), ('lengths', 0.042), ('supervise', 0.042), ('xwl', 0.042), ('decision', 0.042), ('norouzi', 0.042), ('loss', 0.042), ('sh', 0.04), ('theoretic', 0.04), ('owing', 0.04), ('dx', 0.038), ('pm', 0.038), ('sgn', 0.038), ('panels', 0.038), ('lays', 0.038), ('neighbourhoods', 0.038), ('proof', 0.038), ('improvements', 0.037), ('rigorous', 0.037), ('performances', 0.037), ('labelled', 0.037), ('candidate', 0.037), ('projection', 0.036), ('probability', 0.034), ('query', 0.034), ('remark', 0.034), ('convergence', 0.033), ('orb', 0.033), ('nni', 0.033), ('ipi', 0.033), ('font', 0.033), ('preferred', 0.032), ('compact', 0.032), ('wl', 0.031), ('lepetit', 0.031), ('calonder', 0.031), ('column', 0.03), ('outcomes', 0.03), ('incurred', 0.029), ('dissimilar', 0.028), ('bronstein', 0.028), ('magnitudes', 0.028), ('bit', 0.028), ('tp', 0.028), ('ln', 0.027), ('pb', 0.026), ('strecha', 0.026), ('brevity', 0.026), ('labels', 0.026), ('mobile', 0.025), ('empirical', 0.025), ('class', 0.025), ('procrustean', 0.025), ('orders', 0.025), ('priori', 0.025), ('ni', 0.025), ('ih', 0.025), ('fleet', 0.024), ('semantic', 0.024)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000007 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.
2 0.52912039 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.
3 0.42523131 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.
4 0.42067966 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.33413237 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.
6 0.15670878 337 iccv-2013-Random Grids: Fast Approximate Nearest Neighbors and Range Searching for Image Search
8 0.079362988 400 iccv-2013-Stable Hyper-pooling and Query Expansion for Event Detection
10 0.072789542 162 iccv-2013-Fast Subspace Search via Grassmannian Based Hashing
11 0.066234328 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
12 0.062824808 319 iccv-2013-Point-Based 3D Reconstruction of Thin Objects
13 0.062204313 258 iccv-2013-Low-Rank Sparse Coding for Image Classification
14 0.060878634 221 iccv-2013-Joint Inverted Indexing
15 0.058269896 294 iccv-2013-Offline Mobile Instance Retrieval with a Small Memory Footprint
16 0.054136414 165 iccv-2013-Find the Best Path: An Efficient and Accurate Classifier for Image Hierarchies
17 0.051874094 404 iccv-2013-Structured Forests for Fast Edge Detection
18 0.051753752 384 iccv-2013-Semi-supervised Robust Dictionary Learning via Efficient l-Norms Minimization
19 0.050701525 140 iccv-2013-Elastic Net Constraints for Shape Matching
20 0.05009589 241 iccv-2013-Learning Near-Optimal Cost-Sensitive Decision Policy for Object Detection
topicId topicWeight
[(0, 0.147), (1, 0.07), (2, -0.074), (3, -0.102), (4, -0.055), (5, 0.337), (6, 0.003), (7, -0.002), (8, -0.27), (9, 0.147), (10, -0.234), (11, 0.135), (12, -0.02), (13, -0.169), (14, 0.01), (15, 0.049), (16, -0.139), (17, 0.173), (18, -0.151), (19, 0.075), (20, 0.001), (21, 0.042), (22, 0.033), (23, 0.01), (24, 0.036), (25, -0.036), (26, -0.024), (27, 0.002), (28, -0.002), (29, -0.021), (30, 0.023), (31, 0.003), (32, -0.002), (33, 0.01), (34, -0.033), (35, -0.004), (36, -0.014), (37, 0.008), (38, -0.0), (39, -0.002), (40, -0.021), (41, 0.028), (42, -0.01), (43, -0.01), (44, -0.024), (45, 0.007), (46, -0.014), (47, -0.001), (48, -0.01), (49, -0.011)]
simIndex simValue paperId paperTitle
1 0.96520251 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.96026313 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.94881845 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.
same-paper 4 0.92852974 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.88090014 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.40514085 221 iccv-2013-Joint Inverted Indexing
9 0.33256784 400 iccv-2013-Stable Hyper-pooling and Query Expansion for Event Detection
10 0.3012352 337 iccv-2013-Random Grids: Fast Approximate Nearest Neighbors and Range Searching for Image Search
11 0.30018404 287 iccv-2013-Neighbor-to-Neighbor Search for Fast Coding of Feature Vectors
12 0.29128507 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
13 0.27257672 171 iccv-2013-Fix Structured Learning of 2013 ICCV paper k2opt.pdf
14 0.25309086 332 iccv-2013-Quadruplet-Wise Image Similarity Learning
15 0.24853018 248 iccv-2013-Learning to Rank Using Privileged Information
16 0.24110384 241 iccv-2013-Learning Near-Optimal Cost-Sensitive Decision Policy for Object Detection
17 0.23938054 112 iccv-2013-Detecting Irregular Curvilinear Structures in Gray Scale and Color Imagery Using Multi-directional Oriented Flux
18 0.23492394 34 iccv-2013-Abnormal Event Detection at 150 FPS in MATLAB
19 0.23220499 258 iccv-2013-Low-Rank Sparse Coding for Image Classification
20 0.23039895 130 iccv-2013-Dynamic Structured Model Selection
topicId topicWeight
[(2, 0.185), (7, 0.28), (12, 0.011), (26, 0.056), (31, 0.029), (35, 0.01), (40, 0.017), (42, 0.078), (64, 0.027), (73, 0.027), (89, 0.153), (95, 0.011), (98, 0.01)]
simIndex simValue paperId paperTitle
same-paper 1 0.83970875 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.
2 0.83730757 178 iccv-2013-From Semi-supervised to Transfer Counting of Crowds
Author: Chen Change Loy, Shaogang Gong, Tao Xiang
Abstract: Regression-based techniques have shown promising results for people counting in crowded scenes. However, most existing techniques require expensive and laborious data annotation for model training. In this study, we propose to address this problem from three perspectives: (1) Instead of exhaustively annotating every single frame, the most informative frames are selected for annotation automatically and actively. (2) Rather than learning from only labelled data, the abundant unlabelled data are exploited. (3) Labelled data from other scenes are employed to further alleviate the burden for data annotation. All three ideas are implemented in a unified active and semi-supervised regression framework with ability to perform transfer learning, by exploiting the underlying geometric structure of crowd patterns via manifold analysis. Extensive experiments validate the effectiveness of our approach.
3 0.83171427 415 iccv-2013-Text Localization in Natural Images Using Stroke Feature Transform and Text Covariance Descriptors
Author: Weilin Huang, Zhe Lin, Jianchao Yang, Jue Wang
Abstract: In this paper, we present a new approach for text localization in natural images, by discriminating text and non-text regions at three levels: pixel, component and textline levels. Firstly, a powerful low-level filter called the Stroke Feature Transform (SFT) is proposed, which extends the widely-used Stroke Width Transform (SWT) by incorporating color cues of text pixels, leading to significantly enhanced performance on inter-component separation and intra-component connection. Secondly, based on the output of SFT, we apply two classifiers, a text component classifier and a text-line classifier, sequentially to extract text regions, eliminating the heuristic procedures that are commonly used in previous approaches. The two classifiers are built upon two novel Text Covariance Descriptors (TCDs) that encode both the heuristic properties and the statistical characteristics of text stokes. Finally, text regions are located by simply thresholding the text-line confident map. Our method was evaluated on two benchmark datasets: ICDAR 2005 and ICDAR 2011, and the corresponding F- , measure values are 0. 72 and 0. 73, respectively, surpassing previous methods in accuracy by a large margin.
Author: Jiwen Lu, Gang Wang, Pierre Moulin
Abstract: This paper presents a new approach for image set classification, where each training and testing example contains a set of image instances of an object captured from varying viewpoints or under varying illuminations. While a number of image set classification methods have been proposed in recent years, most of them model each image set as a single linear subspace or mixture of linear subspaces, which may lose some discriminative information for classification. To address this, we propose exploring multiple order statistics as features of image sets, and develop a localized multikernel metric learning (LMKML) algorithm to effectively combine different order statistics information for classification. Our method achieves the state-of-the-art performance on four widely used databases including the Honda/UCSD, CMU Mobo, and Youtube face datasets, and the ETH-80 object dataset.
5 0.7791903 323 iccv-2013-Pose Estimation with Unknown Focal Length Using Points, Directions and Lines
Author: Yubin Kuang, Kalle Åström
Abstract: In this paper, we study the geometry problems of estimating camera pose with unknown focal length using combination of geometric primitives. We consider points, lines and also rich features such as quivers, i.e. points with one or more directions. We formulate the problems as polynomial systems where the constraints for different primitives are handled in a unified way. We develop efficient polynomial solvers for each of the derived cases with different combinations of primitives. The availability of these solvers enables robust pose estimation with unknown focal length for wider classes of features. Such rich features allow for fewer feature correspondences and generate larger inlier sets with higher probability. We demonstrate in synthetic experiments that our solvers are fast and numerically stable. For real images, we show that our solvers can be used in RANSAC loops to provide good initial solutions.
7 0.7543875 229 iccv-2013-Large-Scale Video Hashing via Structure Learning
8 0.70904309 239 iccv-2013-Learning Hash Codes with Listwise Supervision
9 0.70132196 13 iccv-2013-A General Two-Step Approach to Learning-Based Hashing
10 0.69922411 83 iccv-2013-Complementary Projection Hashing
11 0.6977607 446 iccv-2013-Visual Semantic Complex Network for Web Images
12 0.69549644 374 iccv-2013-Salient Region Detection by UFO: Uniqueness, Focusness and Objectness
13 0.69258738 376 iccv-2013-Scene Text Localization and Recognition with Oriented Stroke Detection
14 0.69107372 214 iccv-2013-Improving Graph Matching via Density Maximization
15 0.69068688 153 iccv-2013-Face Recognition Using Face Patch Networks
16 0.68671143 244 iccv-2013-Learning View-Invariant Sparse Representations for Cross-View Action Recognition
17 0.68460548 253 iccv-2013-Linear Sequence Discriminant Analysis: A Model-Based Dimensionality Reduction Method for Vector Sequences
18 0.68142968 347 iccv-2013-Recursive Estimation of the Stein Center of SPD Matrices and Its Applications
19 0.67832685 191 iccv-2013-Handling Uncertain Tags in Visual Recognition
20 0.67729288 294 iccv-2013-Offline Mobile Instance Retrieval with a Small Memory Footprint