cvpr cvpr2013 cvpr2013-69 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Tomasz Trzcinski, Mario Christoudias, Pascal Fua, Vincent Lepetit
Abstract: Binary keypoint descriptors provide an efficient alternative to their floating-point competitors as they enable faster processing while requiring less memory. In this paper, we propose a novel framework to learn an extremely compact binary descriptor we call BinBoost that is very robust to illumination and viewpoint changes. Each bit of our descriptor is computed with a boosted binary hash function, and we show how to efficiently optimize the different hash functions so that they complement each other, which is key to compactness and robustness. The hash functions rely on weak learners that are applied directly to the imagepatches, whichfrees usfrom any intermediate representation and lets us automatically learn the image gradient pooling configuration of the final descriptor. Our resulting descriptor significantly outperforms the state-of-the-art binary descriptors and performs similarly to the best floating-point descriptors at a fraction of the matching time and memory footprint.
Reference: text
sentIndex sentText sentNum sentScore
1 ch a Abstract Binary keypoint descriptors provide an efficient alternative to their floating-point competitors as they enable faster processing while requiring less memory. [sent-3, score-0.177]
2 In this paper, we propose a novel framework to learn an extremely compact binary descriptor we call BinBoost that is very robust to illumination and viewpoint changes. [sent-4, score-0.381]
3 Each bit of our descriptor is computed with a boosted binary hash function, and we show how to efficiently optimize the different hash functions so that they complement each other, which is key to compactness and robustness. [sent-5, score-0.739]
4 The hash functions rely on weak learners that are applied directly to the imagepatches, whichfrees usfrom any intermediate representation and lets us automatically learn the image gradient pooling configuration of the final descriptor. [sent-6, score-0.695]
5 Our resulting descriptor significantly outperforms the state-of-the-art binary descriptors and performs similarly to the best floating-point descriptors at a fraction of the matching time and memory footprint. [sent-7, score-0.59]
6 Binary descriptors are of particular interest as they require far less storage capacity and offer much faster ∗This work was supported in part by the Swiss National Science Foundation and the EU project MyCopter. [sent-14, score-0.156]
7 BinBo stlearnsabo stedhashfunctionCdforeachde- scriptor bit, jointly optimized over both the feature weighting (bd) and pooling strategy (hd). [sent-16, score-0.173]
8 matching times than conventional floating point descriptors [9, 27, 4, 15, 22, 30], or even quantized descriptors [3]. [sent-20, score-0.375]
9 To address these shortcomings, we propose a novel supervised learning framework that finds a low-dimensional but highly discriminative binary descriptor. [sent-24, score-0.172]
10 1, for each dimension we learn a hash function of the same form as an AdaBoost strong classifier, that is the sign of a linear combination of non-linear weak learners. [sent-26, score-0.3]
11 It is more general and powerful than those used in standard binary descriptors, which often rely on simple thresholded linear projections [30]. [sent-27, score-0.196]
12 The resulting binary descriptor which we refer to as BinBoost1 significantly outperforms its binary competitors. [sent-29, score-0.435]
13 Furthermore, with as few as 64 bits it exhibits a comparable accuracy to state-of-theart floating point or quantized descriptors at a fraction of the storage and matching cost. [sent-30, score-0.478]
14 Nevertheless, it is more complex to optimize, and we show how to efficiently optimize our hash functions using boosting. [sent-31, score-0.158]
15 As weak learners, we use gradient-based image features that are directly applied to the raw intensity image patches, which frees us from any intermediate representation and lets us automatically learn the image gradient pooling configuration of the final descriptor. [sent-32, score-0.334]
16 In Section 3 we describe our method: we first show how we construct our set of weak learners and how we find the Hamming embedding minimizing the exponential loss function. [sent-35, score-0.398]
17 We then explain how we use this approach to build our binary local feature descriptor and in Section 4 we compare it against the state of the art methods. [sent-36, score-0.31]
18 Related Work Many recent techniques form binary descriptors based on simple pixel intensity comparisons [4, 15, 22]. [sent-38, score-0.289]
19 Similarly, [37] develops a binary edge descriptor based on a histogram of normalized gradients. [sent-40, score-0.31]
20 Although more efficient, these hand-designed descriptors are generally not compact and not as accurate as their floating point equivalents. [sent-41, score-0.292]
21 Machine learning has been applied to improve both the efficiency and accuracy of image descriptor matching. [sent-42, score-0.207]
22 supervised hashing methods learn compact binary descriptors whose Hamming distance is correlated with the similarity in the original input space [9, 14, 23, 36, 35]. [sent-44, score-0.391]
23 Semantic hashing [23] trains a multi-layer neural network to learn representative, compact binary codes. [sent-45, score-0.264]
24 In [34, 9], iterative and sequential optimization strategies that find projections with minimal quantization error are explored. [sent-48, score-0.166]
25 While these approaches have proven highly effective for finding compact binary codes, they rely on a pre-defined distance or similarity measure and in many cases are limited to the accuracy of the origi- nal input space. [sent-49, score-0.25]
26 [10], however, they are less applicable to local descriptor matching where the appropriate choice of kernel function is less well understood. [sent-58, score-0.185]
27 Recent descriptor learning methods have emphasized the importance of learning not only the optimal weighting, but also the optimal shape or pooling configuration of the underlying representation [3, 26, 29]. [sent-59, score-0.374]
28 To make learning tractable, however, a limited set of pooling configurations was considered and restricted to circular, symmetrically arranged pooling regions centered about the patch. [sent-62, score-0.22]
29 As shown in our experiments, our binary descriptor achieves a similar accuracy to these methods at a fraction of the matching cost. [sent-63, score-0.336]
30 Jointly optimizing over descriptor weighting and shape poses a difficult problem due to the potentially large number of pooling configurations one might encounter. [sent-64, score-0.334]
31 As a result and unlike kernel methods, boosting is an efficient way to find a non-linear transformation of the input that is naturally parameterized over both the descriptor shape and weighting. [sent-69, score-0.254]
32 In [29], we proposed a descriptor we call Low-dimensional Boosted Gradient Map (L-BGM), whose similarity measure models the correlation between weak learners resulting in a compact description. [sent-72, score-0.654]
33 Although highly accurate, L-BGM computes a floating point descriptor and therefore its matching time is costly. [sent-74, score-0.304]
34 In this paper, we introduce a boosted binary descriptor that relies on the same image gradient-based features as [29]. [sent-75, score-0.389]
35 We define a sequential learning method similar to [16, 34] except, unlike these methods, our boosting approach learns both the optimal shape and weighting of the features associated with each bit. [sent-77, score-0.215]
36 Our descriptor can also be seen as a two layer neural network [23], since each coordinate of the descriptor is computed from a linear combination of pooled image features. [sent-78, score-0.37]
37 As shown in our experiments, this results in a highly accurate and compact binary descriptor. [sent-79, score-0.221]
38 Unlike hand-designed representations, we get similar performance to SIFT with as few as 8 bits, and do significantly better with increasing bit length, our final performance rivaling that of the leading binary and floating point descriptors. [sent-80, score-0.312]
39 The BinBoost Descriptor In this section, we first describe our BinBoost descriptor and show how to train it efficiently. [sent-82, score-0.216]
40 Problem formulation Given an image intensity patch x, we look for a binary descriptor C(x) = [C1(x) , . [sent-86, score-0.375]
41 , CD (x)] which maps the patch to a D-dimensional binary string. [sent-89, score-0.153]
42 hd,K(x)]T are K weak learners weighted by the vector bd = [bd,1 . [sent-98, score-0.512]
43 Our problem formulation is similar to [25] in the sense that [25] also learned a descriptor CSSC(x) by minimizing its exponential loss with Adaboost. [sent-104, score-0.185]
44 Expression (1), however, is more complex than the one used in [25], which considered functions of the simpler form CdSSC(x) = bdhd(x), with bd a scalar and hd a single weak learner. [sent-105, score-0.434]
45 Let {(xn, yn, ln)}nN=1 be a set of N labeled training pairs tsu {c(hx that ln =) +1 if image patches xn and yn correspond to the same physical point, and ln = −1 otherwise. [sent-109, score-0.237]
46 (2) aims at reducing the Hamming distances between descriptors of patches from positive pairs (ln = +1) while increasing the Hamming distances between descriptors of patches from negative pairs (ln = −1). [sent-124, score-0.428]
47 First the cd functions are not weighted, because for efficiency reasons we want to use the regular Hamming distances between descriptors instead of the weighted one. [sent-127, score-0.291]
48 Second, and more importantly, the cd functions are much more complex than the ones that are usually used, since they are a product of two strong classifiers. [sent-128, score-0.164]
49 The resulting optimization is discontinuous and highly non-convex and in practice the space of all possible weak learners h is discrete and prohibitively large. [sent-129, score-0.423]
50 Greedy optimization In this section we present a greedy algorithm for jointly optimizing over the weak classifiers ofeach bit, hd and their associated weights bd. [sent-133, score-0.345]
51 Using this fact, at iteration d, the optimal bd and hd can be taken as ? [sent-138, score-0.307]
52 The sign function in cd is non-differentiable, and Eq. [sent-147, score-0.193]
53 The sign function in the expression of Cd makes bd defined only up to a scale factor, and given an estimate for hd(x), we solve for bd by looking for mbadxbTdMbd, s. [sent-171, score-0.281]
54 (7) defines a standard eigenvalue problem and the optimal weights bd can therefore be found in closed-form as the eigenvector of M associated with its largest eigenvalue. [sent-181, score-0.164]
55 Weak learners In our implementation, we rely on weak learners that consider the orientations of intensity gradients over image regions [1, 29]. [sent-196, score-0.738]
56 Finally, we compare BinBoost with the state-of-the-art binary and floating point descriptors. [sent-210, score-0.219]
57 The ground truth available for each of these datasets describes 100k, 200k and 500k 222888777755 Train: Liberty, Test: Notre Dame (K=1 28 weak learners) q (# orientation bins) (a) Train: Liberty, Test: Notre Dame (q=8 orientation bins) × K (# weak learners) (b) Figure 2. [sent-218, score-0.42]
58 Influence of (a) the number of orientation bins q and (b) the number of weak learners K on the descriptor performance for dimensionalities D = 8, 16, 32, 64 bits. [sent-219, score-0.723]
59 Increasing the number of weak learners K from K = 128 to K = 256 provides only a minor improvement—at greatly increased computational cost—and, hence, we choose for our final descriptor K = 128. [sent-221, score-0.583]
60 In our experiments, we use subsampled patches of size 32 32 and the descriptors are tsraaminpelde on aetcachhe so fo fth sei 2e0 30k2 d×at a3s2et asn adn tdh we use tphteo she aldreout 100k dataset for testing. [sent-223, score-0.173]
61 BinBoost has only three main parameters that provide a clear trade-off between the performance and complexity of the final descriptor: the number of orientation bins used by the weak learner, the number of weak learners, and the final dimensionality of the descriptor. [sent-228, score-0.444]
62 Number of orientation bins q defines the granularity of the gradient-based weak learners. [sent-230, score-0.284]
63 For most of the values for D, the performances are optimal for q = 8 as finer orientation quantization does not lead to any performance improvement and we keep q = 8 in the remaining experiments. [sent-233, score-0.175]
64 Number of weak learners K determines how many gradient-based features are evaluated per dimension and in Fig. [sent-235, score-0.398]
65 Dimensionality D is the number of bits of our final descriptor. [sent-238, score-0.175]
66 3 shows that with D = 64 bits, our descriptor Dimensionality D (# bits) Figure 3. [sent-240, score-0.185]
67 4 the weak learners and their weighted orientations chosen for computing the first 8 bits. [sent-247, score-0.424]
68 The weak learners of similar orientations tend to cluster about different regions for each bit thus illus- × trating the complementary nature of the learned hash functions. [sent-248, score-0.616]
69 Comparison with the state of the art In this section we compare our approach against SIFT [17], SURF [2], the binary LDAHash descriptor [27], 222888777866 bits learned on 200k pairs of 32 32 patches from the Notre Dame dbiattsals eeat (best vni 2ew00ekd p on screen). [sent-251, score-0.561]
70 3F2o rp aetacchhe pixel o thf eth Ne figure we show the average orientation weighted by the weights of the weak learners bd. [sent-252, score-0.458]
71 For different bits, the weak learners cluster about different regions and orientations illustrating their complementary nature. [sent-253, score-0.424]
72 the binary BGM descriptor [29], Boosted SSC [25], LBGM [29], the binary ITQ descriptor applied on SIFT descriptors [9], and the fast binary BRIEF [4] and BRISK [15] descriptors. [sent-254, score-0.872]
73 It performs almost twice as well as SIFT in terms of 95% error rate, while requiring only 64 bits (8 bytes) instead of 128 bytes for SIFT. [sent-267, score-0.243]
74 Moreover, since BinBoost can be efficiently implemented using integral images, the computation time of our descriptor is comparable with that of SIFT using Vedaldi’s implementation— approximately 1ms per descriptor on a Macbook Pro with an Intel i7 2. [sent-268, score-0.37]
75 The performance improvement of BinBoost with respect to the recent binary descriptors, such as LDAHash or BRIEF, is even greater, BinBoost achieving a 95% error rate that is almost a factor of 3 lower than that obtained with these methods. [sent-270, score-0.173]
76 Since the dimensionality of the other binary descriptors can be varied depending on the required performance qual- ity, Fig. [sent-272, score-0.289]
77 5 compares the 95% error rates of these descriptors for different numbers of bits used. [sent-273, score-0.35]
78 95% error rates for binary descriptors of different dimensionality. [sent-276, score-0.3]
79 BinBoost outperforms the state-of-the-art binary descriptors and the improvement is especially visible for lower dimensionality. [sent-278, score-0.252]
80 1 01 0 Matching time per descriptor pair [μs] BRIEF (0. [sent-281, score-0.185]
81 In fact, with as few as 16 bits BinBoost performs as well as the next best descriptor, BGM, which is 128 bits long. [sent-300, score-0.35]
82 Moreover, our BinBoost descriptor remains competitive to the best descriptors of [3] and [26], even though the memory footprint of their descriptors is almost 4 times greater. [sent-301, score-0.439]
83 The real advantage of BinBoost, however, is its binary na- ture which allows for extremely tion using the Hamming distance2, of [3] and [26] are floating-point fast similarity computa- whereas the descriptors and cannot benefit from the same optimization, even when quantized very coarsely. [sent-302, score-0.279]
84 2On modern CPUs this can be implemented as a bitwise XOR operation on the descriptors followed by a POPCOUNT instruction which counts the number of bits set to 1. [sent-303, score-0.354]
85 Comparison of our BinBoost descriptor to the state-of-the-art binary (left) and floating-point (right) descriptors. [sent-305, score-0.31]
86 Our BinBoost descriptor significantly outperforms its binary competitors for all false positive rates. [sent-307, score-0.36]
87 95% error rates for different training and testing configurations and the corresponding results for BinBoost with 64 and 8 bits and its competitors. [sent-322, score-0.223]
88 Below the descriptor names we write the number of bytes used to encode them. [sent-324, score-0.228]
89 For the floating point descriptors (SIFT, SURF, L-BGM [29], Brown et al. [sent-325, score-0.221]
90 For reference, we also give the results of the floating-point descriptors: BinBoost performs similarly to the best floating-point descriptors even though it is shorter and binary which enables a significant speedup in processing time (See Fig. [sent-329, score-0.252]
91 over 2 To verify the performance of our descriptor, we also compare it to several binarization techniques applied on the recently proposed floating-point L-BGM descriptor that outperforms SIFT on the Liberty, Notre Dame and Yosemite datasets. [sent-333, score-0.257]
92 Binarizing the L-BGM coordinates by thresholding them at an optimal threshold found as in [27] results in large binarization errors significantly decreasing the accuracy of the resulting binary representation. [sent-336, score-0.22]
93 In contrast, sequential projection learning (S3PLH) [34] can find non-orthogonal projections that more faithfully mitigate binarization error, however, it requires a fairly large number of bits to recover LBGM’s original performance. [sent-338, score-0.384]
94 Unlike these methods, by effectively combining multiple weak learners within each hash function, our algorithm results in a more accurate predictor with far fewer bits. [sent-339, score-0.542]
95 Conclusion In this paper we presented an efficient framework to train highly discriminative binary local feature descriptors. [sent-341, score-0.181]
96 Leveraging the boosting-trick, we simultaneously optimize both the descriptor weighting and pooling strategy. [sent-342, score-0.371]
97 The proposed sequential learning scheme finds a single boosted hash function per dimension as a linear combination of nonlinear gradient-based weak learners. [sent-343, score-0.423]
98 Since we train our descriptor from intensity patches, our final binary descriptor does not rely on any pre-computed representation, and it outperforms the state ofthe art with only 64 bits per descriptor. [sent-344, score-0.767]
99 On the other hand, the sequential projection learning of S3PLH requires a fairly large number of bits to recover L-BGM’s original performance. [sent-362, score-0.27]
100 In contrast, by jointly optimizing over the feature weighting and pooling strategy of each bit, our BinBoost approach results in a highly compact and accurate binary descriptor whose performance is similar with L-BGM but at a fraction of the storage cost. [sent-363, score-0.61]
wordName wordTfidf (topN-words)
[('binboost', 0.61), ('learners', 0.248), ('notre', 0.198), ('descriptor', 0.185), ('dame', 0.184), ('bits', 0.175), ('hd', 0.17), ('cd', 0.164), ('weak', 0.15), ('yosemite', 0.142), ('descriptors', 0.127), ('binary', 0.125), ('hash', 0.121), ('bd', 0.114), ('hamming', 0.109), ('bgm', 0.108), ('brisk', 0.102), ('pooling', 0.099), ('ldahash', 0.095), ('floating', 0.094), ('liberty', 0.081), ('trzcinski', 0.081), ('boosted', 0.079), ('binarization', 0.072), ('compact', 0.071), ('bit', 0.071), ('boosting', 0.069), ('hashing', 0.068), ('ssc', 0.067), ('bdthd', 0.061), ('btdhd', 0.061), ('sift', 0.061), ('brief', 0.06), ('orientation', 0.06), ('itq', 0.052), ('sequential', 0.051), ('competitors', 0.05), ('weighting', 0.05), ('yn', 0.049), ('surf', 0.048), ('quantization', 0.048), ('bins', 0.047), ('patches', 0.046), ('sgn', 0.046), ('adaboost', 0.045), ('performances', 0.044), ('bytes', 0.043), ('simonyan', 0.043), ('projections', 0.042), ('lbgm', 0.041), ('ln', 0.038), ('optimize', 0.037), ('dimensionality', 0.037), ('intensity', 0.037), ('xn', 0.036), ('christoudias', 0.036), ('macbook', 0.036), ('popcount', 0.036), ('dimensionalities', 0.033), ('hashed', 0.033), ('lnd', 0.033), ('lepetit', 0.033), ('cpus', 0.032), ('train', 0.031), ('instruction', 0.03), ('pairs', 0.03), ('sign', 0.029), ('rely', 0.029), ('norouzi', 0.029), ('storage', 0.029), ('codes', 0.028), ('binarizing', 0.028), ('roc', 0.028), ('patch', 0.028), ('vedaldi', 0.027), ('quantized', 0.027), ('strecha', 0.027), ('defines', 0.027), ('fraction', 0.026), ('orientations', 0.026), ('error', 0.025), ('brown', 0.025), ('greedy', 0.025), ('highly', 0.025), ('optimized', 0.024), ('expression', 0.024), ('lets', 0.024), ('bronstein', 0.024), ('seem', 0.024), ('intermediate', 0.024), ('kulis', 0.023), ('rate', 0.023), ('predictor', 0.023), ('rates', 0.023), ('optimal', 0.023), ('increasing', 0.022), ('learning', 0.022), ('pro', 0.022), ('fairly', 0.022), ('modern', 0.022)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000004 69 cvpr-2013-Boosting Binary Keypoint Descriptors
Author: Tomasz Trzcinski, Mario Christoudias, Pascal Fua, Vincent Lepetit
Abstract: Binary keypoint descriptors provide an efficient alternative to their floating-point competitors as they enable faster processing while requiring less memory. In this paper, we propose a novel framework to learn an extremely compact binary descriptor we call BinBoost that is very robust to illumination and viewpoint changes. Each bit of our descriptor is computed with a boosted binary hash function, and we show how to efficiently optimize the different hash functions so that they complement each other, which is key to compactness and robustness. The hash functions rely on weak learners that are applied directly to the imagepatches, whichfrees usfrom any intermediate representation and lets us automatically learn the image gradient pooling configuration of the final descriptor. Our resulting descriptor significantly outperforms the state-of-the-art binary descriptors and performs similarly to the best floating-point descriptors at a fraction of the matching time and memory footprint.
2 0.18925411 63 cvpr-2013-Binary Code Ranking with Weighted Hamming Distance
Author: Lei Zhang, Yongdong Zhang, Jinhu Tang, Ke Lu, Qi Tian
Abstract: Binary hashing has been widely used for efficient similarity search due to its query and storage efficiency. In most existing binary hashing methods, the high-dimensional data are embedded into Hamming space and the distance or similarity of two points are approximated by the Hamming distance between their binary codes. The Hamming distance calculation is efficient, however, in practice, there are often lots of results sharing the same Hamming distance to a query, which makes this distance measure ambiguous and poses a critical issue for similarity search where ranking is important. In this paper, we propose a weighted Hamming distance ranking algorithm (WhRank) to rank the binary codes of hashing methods. By assigning different bit-level weights to different hash bits, the returned binary codes are ranked at a finer-grained binary code level. We give an algorithm to learn the data-adaptive and query-sensitive weight for each hash bit. Evaluations on two large-scale image data sets demonstrate the efficacy of our weighted Hamming distance for binary code ranking.
3 0.17227888 236 cvpr-2013-K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes
Author: Kaiming He, Fang Wen, Jian Sun
Abstract: In computer vision there has been increasing interest in learning hashing codes whose Hamming distance approximates the data similarity. The hashing functions play roles in both quantizing the vector space and generating similarity-preserving codes. Most existing hashing methods use hyper-planes (or kernelized hyper-planes) to quantize and encode. In this paper, we present a hashing method adopting the k-means quantization. We propose a novel Affinity-Preserving K-means algorithm which simultaneously performs k-means clustering and learns the binary indices of the quantized cells. The distance between the cells is approximated by the Hamming distance of the cell indices. We further generalize our algorithm to a product space for learning longer codes. Experiments show our method, named as K-means Hashing (KMH), outperforms various state-of-the-art hashing encoding methods.
4 0.13893415 223 cvpr-2013-Inductive Hashing on Manifolds
Author: Fumin Shen, Chunhua Shen, Qinfeng Shi, Anton van_den_Hengel, Zhenmin Tang
Abstract: Learning based hashing methods have attracted considerable attention due to their ability to greatly increase the scale at which existing algorithms may operate. Most of these methods are designed to generate binary codes that preserve the Euclidean distance in the original space. Manifold learning techniques, in contrast, are better able to model the intrinsic structure embedded in the original highdimensional data. The complexity of these models, and the problems with out-of-sample data, havepreviously rendered them unsuitable for application to large-scale embedding, however. In this work, we consider how to learn compact binary embeddings on their intrinsic manifolds. In order to address the above-mentioned difficulties, we describe an efficient, inductive solution to the out-of-sample data problem, and a process by which non-parametric manifold learning may be used as the basis of a hashing method. Our proposed approach thus allows the development of a range of new hashing techniques exploiting the flexibility of the wide variety of manifold learning approaches available. We particularly show that hashing on the basis of t-SNE [29] outperforms state-of-the-art hashing methods on large-scale benchmark datasets, and is very effective for image classification with very short code lengths.
5 0.12132993 163 cvpr-2013-Fast, Accurate Detection of 100,000 Object Classes on a Single Machine
Author: Thomas Dean, Mark A. Ruzon, Mark Segal, Jonathon Shlens, Sudheendra Vijayanarasimhan, Jay Yagnik
Abstract: Many object detection systems are constrained by the time required to convolve a target image with a bank of filters that code for different aspects of an object’s appearance, such as the presence of component parts. We exploit locality-sensitive hashing to replace the dot-product kernel operator in the convolution with a fixed number of hash-table probes that effectively sample all of the filter responses in time independent of the size of the filter bank. To show the effectiveness of the technique, we apply it to evaluate 100,000 deformable-part models requiring over a million (part) filters on multiple scales of a target image in less than 20 seconds using a single multi-core processor with 20GB of RAM. This represents a speed-up of approximately 20,000 times— four orders of magnitude— when compared withperforming the convolutions explicitly on the same hardware. While mean average precision over the full set of 100,000 object classes is around 0.16 due in large part to the challenges in gathering training data and collecting ground truth for so many classes, we achieve a mAP of at least 0.20 on a third of the classes and 0.30 or better on about 20% of the classes.
6 0.11904296 246 cvpr-2013-Learning Binary Codes for High-Dimensional Data Using Bilinear Projections
7 0.11237571 79 cvpr-2013-Cartesian K-Means
8 0.1082866 319 cvpr-2013-Optimized Product Quantization for Approximate Nearest Neighbor Search
9 0.10320648 248 cvpr-2013-Learning Collections of Part Models for Object Recognition
10 0.10309268 87 cvpr-2013-Compressed Hashing
11 0.09905988 249 cvpr-2013-Learning Compact Binary Codes for Visual Tracking
12 0.096409246 421 cvpr-2013-Supervised Kernel Descriptors for Visual Recognition
13 0.084543504 404 cvpr-2013-Sparse Quantization for Patch Description
14 0.083674505 403 cvpr-2013-Sparse Output Coding for Large-Scale Visual Recognition
15 0.07976798 254 cvpr-2013-Learning SURF Cascade for Fast and Accurate Object Detection
16 0.078800596 112 cvpr-2013-Dense Segmentation-Aware Descriptors
17 0.076468199 53 cvpr-2013-BFO Meets HOG: Feature Extraction Based on Histograms of Oriented p.d.f. Gradients for Image Classification
18 0.075096719 383 cvpr-2013-Seeking the Strongest Rigid Detector
19 0.072602108 234 cvpr-2013-Joint Spectral Correspondence for Disparate Image Matching
20 0.06996306 59 cvpr-2013-Better Exploiting Motion for Better Action Recognition
topicId topicWeight
[(0, 0.153), (1, -0.034), (2, -0.028), (3, 0.03), (4, 0.051), (5, 0.019), (6, -0.044), (7, -0.107), (8, -0.153), (9, -0.07), (10, -0.154), (11, -0.003), (12, 0.067), (13, 0.066), (14, 0.069), (15, 0.044), (16, 0.016), (17, -0.014), (18, 0.039), (19, 0.033), (20, -0.011), (21, -0.01), (22, -0.006), (23, -0.019), (24, 0.001), (25, 0.044), (26, -0.003), (27, -0.008), (28, -0.001), (29, -0.035), (30, 0.001), (31, 0.024), (32, 0.027), (33, -0.005), (34, -0.011), (35, 0.001), (36, -0.025), (37, 0.034), (38, 0.001), (39, 0.036), (40, 0.066), (41, 0.006), (42, -0.01), (43, -0.011), (44, 0.025), (45, -0.061), (46, 0.024), (47, 0.003), (48, 0.047), (49, -0.0)]
simIndex simValue paperId paperTitle
same-paper 1 0.91197973 69 cvpr-2013-Boosting Binary Keypoint Descriptors
Author: Tomasz Trzcinski, Mario Christoudias, Pascal Fua, Vincent Lepetit
Abstract: Binary keypoint descriptors provide an efficient alternative to their floating-point competitors as they enable faster processing while requiring less memory. In this paper, we propose a novel framework to learn an extremely compact binary descriptor we call BinBoost that is very robust to illumination and viewpoint changes. Each bit of our descriptor is computed with a boosted binary hash function, and we show how to efficiently optimize the different hash functions so that they complement each other, which is key to compactness and robustness. The hash functions rely on weak learners that are applied directly to the imagepatches, whichfrees usfrom any intermediate representation and lets us automatically learn the image gradient pooling configuration of the final descriptor. Our resulting descriptor significantly outperforms the state-of-the-art binary descriptors and performs similarly to the best floating-point descriptors at a fraction of the matching time and memory footprint.
2 0.81892049 236 cvpr-2013-K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes
Author: Kaiming He, Fang Wen, Jian Sun
Abstract: In computer vision there has been increasing interest in learning hashing codes whose Hamming distance approximates the data similarity. The hashing functions play roles in both quantizing the vector space and generating similarity-preserving codes. Most existing hashing methods use hyper-planes (or kernelized hyper-planes) to quantize and encode. In this paper, we present a hashing method adopting the k-means quantization. We propose a novel Affinity-Preserving K-means algorithm which simultaneously performs k-means clustering and learns the binary indices of the quantized cells. The distance between the cells is approximated by the Hamming distance of the cell indices. We further generalize our algorithm to a product space for learning longer codes. Experiments show our method, named as K-means Hashing (KMH), outperforms various state-of-the-art hashing encoding methods.
3 0.78250492 246 cvpr-2013-Learning Binary Codes for High-Dimensional Data Using Bilinear Projections
Author: Yunchao Gong, Sanjiv Kumar, Henry A. Rowley, Svetlana Lazebnik
Abstract: Recent advances in visual recognition indicate that to achieve good retrieval and classification accuracy on largescale datasets like ImageNet, extremely high-dimensional visual descriptors, e.g., Fisher Vectors, are needed. We present a novel method for converting such descriptors to compact similarity-preserving binary codes that exploits their natural matrix structure to reduce their dimensionality using compact bilinear projections instead of a single large projection matrix. This method achieves comparable retrieval and classification accuracy to the original descriptors and to the state-of-the-art Product Quantization approach while having orders ofmagnitudefaster code generation time and smaller memory footprint.
4 0.77049702 87 cvpr-2013-Compressed Hashing
Author: Yue Lin, Rong Jin, Deng Cai, Shuicheng Yan, Xuelong Li
Abstract: Recent studies have shown that hashing methods are effective for high dimensional nearest neighbor search. A common problem shared by many existing hashing methods is that in order to achieve a satisfied performance, a large number of hash tables (i.e., long codewords) are required. To address this challenge, in this paper we propose a novel approach called Compressed Hashing by exploring the techniques of sparse coding and compressed sensing. In particular, we introduce a sparse coding scheme, based on the approximation theory of integral operator, that generate sparse representation for high dimensional vectors. We then project sparse codes into a low dimensional space by effectively exploring the Restricted Isometry Property (RIP), a key property in compressed sensing theory. Both of the theoretical analysis and the empirical studies on two large data sets show that the proposed approach is more effective than the state-of-the-art hashing algorithms.
5 0.76215494 63 cvpr-2013-Binary Code Ranking with Weighted Hamming Distance
Author: Lei Zhang, Yongdong Zhang, Jinhu Tang, Ke Lu, Qi Tian
Abstract: Binary hashing has been widely used for efficient similarity search due to its query and storage efficiency. In most existing binary hashing methods, the high-dimensional data are embedded into Hamming space and the distance or similarity of two points are approximated by the Hamming distance between their binary codes. The Hamming distance calculation is efficient, however, in practice, there are often lots of results sharing the same Hamming distance to a query, which makes this distance measure ambiguous and poses a critical issue for similarity search where ranking is important. In this paper, we propose a weighted Hamming distance ranking algorithm (WhRank) to rank the binary codes of hashing methods. By assigning different bit-level weights to different hash bits, the returned binary codes are ranked at a finer-grained binary code level. We give an algorithm to learn the data-adaptive and query-sensitive weight for each hash bit. Evaluations on two large-scale image data sets demonstrate the efficacy of our weighted Hamming distance for binary code ranking.
6 0.74730879 79 cvpr-2013-Cartesian K-Means
7 0.73608637 223 cvpr-2013-Inductive Hashing on Manifolds
8 0.71855503 319 cvpr-2013-Optimized Product Quantization for Approximate Nearest Neighbor Search
9 0.70013291 404 cvpr-2013-Sparse Quantization for Patch Description
10 0.59796643 163 cvpr-2013-Fast, Accurate Detection of 100,000 Object Classes on a Single Machine
11 0.54368752 403 cvpr-2013-Sparse Output Coding for Large-Scale Visual Recognition
12 0.53167951 421 cvpr-2013-Supervised Kernel Descriptors for Visual Recognition
14 0.51716262 249 cvpr-2013-Learning Compact Binary Codes for Visual Tracking
15 0.51534951 38 cvpr-2013-All About VLAD
16 0.51530105 346 cvpr-2013-Real-Time No-Reference Image Quality Assessment Based on Filter Learning
17 0.5137099 268 cvpr-2013-Leveraging Structure from Motion to Learn Discriminative Codebooks for Scalable Landmark Classification
18 0.50270998 369 cvpr-2013-Rotation, Scaling and Deformation Invariant Scattering for Texture Discrimination
19 0.49394551 304 cvpr-2013-Multipath Sparse Coding Using Hierarchical Matching Pursuit
20 0.4910751 343 cvpr-2013-Query Adaptive Similarity for Large Scale Object Retrieval
topicId topicWeight
[(10, 0.101), (16, 0.026), (20, 0.014), (26, 0.036), (30, 0.179), (33, 0.244), (36, 0.036), (57, 0.025), (67, 0.088), (69, 0.047), (87, 0.108)]
simIndex simValue paperId paperTitle
same-paper 1 0.87038362 69 cvpr-2013-Boosting Binary Keypoint Descriptors
Author: Tomasz Trzcinski, Mario Christoudias, Pascal Fua, Vincent Lepetit
Abstract: Binary keypoint descriptors provide an efficient alternative to their floating-point competitors as they enable faster processing while requiring less memory. In this paper, we propose a novel framework to learn an extremely compact binary descriptor we call BinBoost that is very robust to illumination and viewpoint changes. Each bit of our descriptor is computed with a boosted binary hash function, and we show how to efficiently optimize the different hash functions so that they complement each other, which is key to compactness and robustness. The hash functions rely on weak learners that are applied directly to the imagepatches, whichfrees usfrom any intermediate representation and lets us automatically learn the image gradient pooling configuration of the final descriptor. Our resulting descriptor significantly outperforms the state-of-the-art binary descriptors and performs similarly to the best floating-point descriptors at a fraction of the matching time and memory footprint.
2 0.87000924 128 cvpr-2013-Discrete MRF Inference of Marginal Densities for Non-uniformly Discretized Variable Space
Author: Masaki Saito, Takayuki Okatani, Koichiro Deguchi
Abstract: This paper is concerned with the inference of marginal densities based on MRF models. The optimization algorithmsfor continuous variables are only applicable to a limited number of problems, whereas those for discrete variables are versatile. Thus, it is quite common to convert the continuous variables into discrete ones for the problems that ideally should be solved in the continuous domain, such as stereo matching and optical flow estimation. In this paper, we show a novel formulation for this continuous-discrete conversion. The key idea is to estimate the marginal densities in the continuous domain by approximating them with mixtures of rectangular densities. Based on this formulation, we derive a mean field (MF) algorithm and a belief propagation (BP) algorithm. These algorithms can correctly handle the case where the variable space is discretized in a non-uniform manner. By intentionally using such a non-uniform discretization, a higher balance between computational efficiency and accuracy of marginal density estimates could be achieved. We present a method for actually doing this, which dynamically discretizes the variable space in a coarse-to-fine manner in the course of the computation. Experimental results show the effectiveness of our approach.
3 0.85604942 468 cvpr-2013-Winding Number for Region-Boundary Consistent Salient Contour Extraction
Author: Yansheng Ming, Hongdong Li, Xuming He
Abstract: This paper aims to extract salient closed contours from an image. For this vision task, both region segmentation cues (e.g. color/texture homogeneity) and boundary detection cues (e.g. local contrast, edge continuity and contour closure) play important and complementary roles. In this paper we show how to combine both cues in a unified framework. The main focus is given to how to maintain the consistency (compatibility) between the region cues and the boundary cues. To this ends, we introduce the use of winding number–a well-known concept in topology–as a powerful mathematical device. By this device, the region-boundary consistency is represented as a set of simple linear relationships. Our method is applied to the figure-ground segmentation problem. The experiments show clearly improved results.
4 0.85289407 329 cvpr-2013-Perceptual Organization and Recognition of Indoor Scenes from RGB-D Images
Author: Saurabh Gupta, Pablo Arbeláez, Jitendra Malik
Abstract: We address the problems of contour detection, bottomup grouping and semantic segmentation using RGB-D data. We focus on the challenging setting of cluttered indoor scenes, and evaluate our approach on the recently introduced NYU-Depth V2 (NYUD2) dataset [27]. We propose algorithms for object boundary detection and hierarchical segmentation that generalize the gPb − ucm approach of [se2]g mbeyn mtaatkioinng t effective use oef t dheep gthP information. Wroea schho owf that our system can label each contour with its type (depth, normal or albedo). We also propose a generic method for long-range amodal completion of surfaces and show its effectiveness in grouping. We then turn to the problem of semantic segmentation and propose a simple approach that classifies superpixels into the 40 dominant object categories in NYUD2. We use both generic and class-specific features to encode the appearance and geometry of objects. We also show how our approach can be used for scene classification, and how this contextual information in turn improves object recognition. In all of these tasks, we report significant improvements over the state-of-the-art.
5 0.85131657 314 cvpr-2013-Online Object Tracking: A Benchmark
Author: Yi Wu, Jongwoo Lim, Ming-Hsuan Yang
Abstract: Object tracking is one of the most important components in numerous applications of computer vision. While much progress has been made in recent years with efforts on sharing code and datasets, it is of great importance to develop a library and benchmark to gauge the state of the art. After briefly reviewing recent advances of online object tracking, we carry out large scale experiments with various evaluation criteria to understand how these algorithms perform. The test image sequences are annotated with different attributes for performance evaluation and analysis. By analyzing quantitative results, we identify effective approaches for robust tracking and provide potential future research directions in this field.
6 0.83927768 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities
7 0.83913231 79 cvpr-2013-Cartesian K-Means
8 0.83867228 248 cvpr-2013-Learning Collections of Part Models for Object Recognition
9 0.83690017 256 cvpr-2013-Learning Structured Hough Voting for Joint Object Detection and Occlusion Reasoning
10 0.83159953 242 cvpr-2013-Label Propagation from ImageNet to 3D Point Clouds
11 0.83138019 71 cvpr-2013-Boundary Cues for 3D Object Shape Recovery
12 0.83127701 119 cvpr-2013-Detecting and Aligning Faces by Image Retrieval
13 0.83097219 98 cvpr-2013-Cross-View Action Recognition via a Continuous Virtual Path
14 0.83056748 72 cvpr-2013-Boundary Detection Benchmarking: Beyond F-Measures
15 0.82983088 222 cvpr-2013-Incorporating User Interaction and Topological Constraints within Contour Completion via Discrete Calculus
16 0.82939178 339 cvpr-2013-Probabilistic Graphlet Cut: Exploiting Spatial Structure Cue for Weakly Supervised Image Segmentation
17 0.82914156 225 cvpr-2013-Integrating Grammar and Segmentation for Human Pose Estimation
18 0.82914066 15 cvpr-2013-A Lazy Man's Approach to Benchmarking: Semisupervised Classifier Evaluation and Recalibration
19 0.82891572 322 cvpr-2013-PISA: Pixelwise Image Saliency by Aggregating Complementary Appearance Contrast Measures with Spatial Priors
20 0.82830781 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases