iccv iccv2013 iccv2013-83 knowledge-graph by maker-knowledge-mining
Source: pdf
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.
Reference: text
sentIndex sentText sentNum sentScore
1 cn , Abstract Recently, hashing techniques have been widely applied to solve the approximate nearest neighbors search problem in many vision applications. [sent-13, score-0.739]
2 Generally, these hashing approaches generate 2c buckets, where c is the length of the hash code. [sent-14, score-0.988]
3 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 . [sent-15, score-0.769]
4 2) all the data points are evenly distributed among all the buckets. [sent-18, score-0.157]
5 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. [sent-19, score-0.692]
6 At the same time, the data points are evenly distributed in the hypercubes generated by these hyperplanes. [sent-21, score-0.21]
7 The experiments comparing with the state-of-the-art hashing methods demonstrate the effectiveness of the proposed method. [sent-22, score-0.621]
8 Given the intrinsic difficulty of exact nearest neighbors search, many hashing algorithms are proposed for Approximate Nearest Neighbors (ANN) search [1, 25, 27, 16, 7, 9]. [sent-29, score-0.739]
9 (a) The hyperplane a crosses the sparse region and the neighbors are quantized into the same bucket; (b) The hyperplane b crosses the dense region and the neighbors are quantized into the different buckets. [sent-32, score-0.628]
10 Apparently, the hyperplane a is more suitable as a hashing function. [sent-33, score-0.779]
11 Given a data set X ∈ Rd×n containing n d-dimensional points, a hashing algorithm uses c hash functions to generate a c-bit Hamming embedding Y ∈ Bc×n. [sent-35, score-1.059]
12 The k-th hash fautenc ati co-bn can mbem expressed as: ghk Y(x) ∈ = B sgn(wkTx − bk)1. [sent-36, score-0.367]
13 Each hash function can be seen as a hyperplane tox split the feature space into two regions. [sent-37, score-0.525]
14 Using c hash functions, a hash index can be built by assigning each point into a c-bit hash bucket corresponding to its c-bit binary code. [sent-38, score-1.189]
15 3) linear scan stage: a linear scan over these points is performed to return the required neighbors. [sent-40, score-0.117]
16 1The corresponding binary hash bit yk (x) = (1+ hk (x))/2. [sent-41, score-0.493]
17 can be simply computed as: 257 The above procedure shows that a good hashing method should satisfy two requirements: 1) mapping the nearby data points into the same bucket or nearby (measured by the hamming distance) buckets to ensure the accuracy. [sent-42, score-1.135]
18 2) all the data points are evenly distributed among all the buckets to reduce the linear scan time. [sent-43, score-0.482]
19 To satisfy the first requirement, the hyperplanes associated with the hash functions should cross the sparse region of the data distribution. [sent-44, score-0.589]
20 1, the hyperplane a crosses the sparse region and the neighbors are quantized into the same bucket while the hyperplane b crosses the dense region and the neighbors are quantized into the different buckets. [sent-46, score-0.687]
21 Apparently, the hyperplane a is more suitable as a hashing function. [sent-47, score-0.779]
22 These methods generate the hash functions randomly and fail to consider this requirement. [sent-51, score-0.418]
23 In order to satisfy the second requirement, many existing hashing algorithms (e. [sent-52, score-0.621]
24 , [7, 25, 24]) require that the data points are evenly separated by each hash function (hyperplane). [sent-54, score-0.494]
25 However, this does not guarantee that the data points are evenly distributed among all the hypercubes generated by the hyperplanes (hash functions). [sent-55, score-0.302]
26 2 gives an example: Both the hyperplane a and the hyperplane b partition the data evenly and they are both good one bit hash functions. [sent-57, score-0.837]
27 However, putting them together does not generate a good two bits hash function, as shown in Fig. [sent-58, score-0.436]
28 A better choice for two bits hash functions are hyperplanes c and d in Fig. [sent-60, score-0.579]
29 In this paper, we propose a novel algorithm named Complementary Projection Hashing (CPH) to find the optimal hashing functions which explicitly considering the above two requirements. [sent-62, score-0.692]
30 Specifically, CPH aims at sequentially finding a series of hyperplanes (hashing functions) which cross the sparse region of the data. [sent-63, score-0.171]
31 At the same time, the data points are evenly distributed in the hypercubes generated by these hyperplanes. [sent-64, score-0.21]
32 The experiments comparing with the state-of-the-art hashing methods demonstrate the effectiveness of the proposed method. [sent-65, score-0.621]
33 Background and Related Work The generic hashing problem is as follows: Given n data points X = [x1, . [sent-67, score-0.656]
34 , xn] ∈ Rd×n, find c hash functions to map a data point x to a ]c- ∈bits R hash code H(x) = [(1 + h1(x))/2, · · · , (1 + hc(x))/2] , where hk (x) ∈ {−1, 1} is the k-th hash function. [sent-70, score-1.215]
35 (a) (b) Both the hyperplane a and the hyperplane b can evenly separated the data. [sent-73, score-0.408]
36 (c) However, putting them together does not generate a good two bits hash function. [sent-74, score-0.436]
37 where wk is the projection vector and bk is the threshold. [sent-76, score-0.199]
38 Different hashing algorithms aim at finding different wk and bk with respect to the different objective functions. [sent-77, score-0.771]
39 One of the most popular hashing algorithms is Locality Sensitive Hashing (LSH) [1]. [sent-78, score-0.621]
40 Recently, many learning-based hashing methods [27, 16, 7, 9, 28, 14] are proposed to make use of the data distribution. [sent-86, score-0.621]
41 There are also many efforts on leveraging the label information into hash function learning, which leads to supervised hashing [20, 15] and semi-supervised hashing [25, 18]. [sent-98, score-1.609]
42 For obtaining more balanced buckets, we use a pairwise hash buckets balance condition to formulate the constraint of hyperplanes. [sent-101, score-0.761]
43 But, we use a soft constraint of minimizing the number of data points which nearby the hyperplanes to find the hyperplanes which cross the sparse region of the data. [sent-104, score-0.325]
44 [15] proposed a supervised hashing method, which used a label matrix involving three different kinds of labels (i. [sent-106, score-0.621]
45 But, our algorithm is an unsupervised hashing method and does not use this label matrix. [sent-110, score-0.621]
46 [9] proposed a hypersphere based hashing method and mainly focused on the pair-wise hash buckets balance. [sent-112, score-1.272]
47 Our method is a hyperplane based hashing method and explicitly considers the two requirements. [sent-114, score-0.779]
48 [29] also proposed a complementary information based hashing method. [sent-116, score-0.684]
49 The complementary information of the proposed method is dependent on the two requirements we described, which is different from [29] and used between projections in one hash table. [sent-118, score-0.466]
50 Crossing The Sparse Region Given a hyperplane f(x) = wTx −b crossing the sparse region, the number of data points inx −theb boundary region soef this hyperplane should be small. [sent-123, score-0.434]
51 It is easy to check that the distance of a point xi to the hyperplane [21] is di=|wT? [sent-124, score-0.199]
52 e boundary parameter ε > 0, we can find the hyperplane which cross the sparse region by solving the op- timization problem as follows: ? [sent-132, score-0.237]
53 To compute the k-th hash function, the penalty uik for data point xi is defined as: ? [sent-138, score-0.474]
54 The final objective func=tio 1n ( tio = =le 1ar·n· t·hne) k-th bit hashing function can be written as: ? [sent-143, score-0.683]
55 (2) By using the accumulative penalty uik, the hashing function for a new bit is complementary to the hashing functions of previous bits. [sent-146, score-1.418]
56 Approximating Balanced Buckets When we learn c-bits hashing functions, we have noticed that all the single bit hashing functions evenly separate the data set do not guarantee balanced buckets (all the data points are evenly distributed among all the 2c buckets). [sent-149, score-1.931]
57 Thus requiring one bit hashing function to evenly separate the data is not enough. [sent-150, score-0.775]
58 However, learning c hyperplanes which distributes all the data points into 2c hypercubes is generally NP-hard [8]. [sent-151, score-0.18]
59 We use a pair-wise hash buckets balance condition [9] to get a reasonable approximation. [sent-152, score-0.718]
60 The pair-wise hash buckets balance requires that every two hyperplanes split the whole space into four regions and each region has n/4 data points. [sent-153, score-0.818]
61 Suppose we have two hash functions h1(x) = sgn(w1Tx b1) and h2(x) = sgn(w2Tx − b2), if we have: ⎪⎧⎨⎪? [sent-156, score-0.418]
62 To learn the k-th bit hashing function, the pair-wise hash buckets balance condition can be formulated as: = = = = ? [sent-162, score-1.401]
63 This suggests that the pairwise hash buckets balance condition has a close connections to the orthogonal constrains of the graph-based hashing methods [27, 16]. [sent-169, score-1.339]
64 vjTvk = 0 (j = 1, · · · , k − 1) forces two bits to be mutually unco=rr 0ela (jte d= i 1n, o·r··de ,rk t o− m 1i)n fiomrciezse redundancy among bits [27, 16]. [sent-170, score-0.138]
65 The Objective Function Combining the above two requirements, the objective function to learn the k-th bit hashing function can be formulated as: wmk,ibnk? [sent-176, score-0.683]
66 In real applications, it is hard to find a set of linear hashing functions which achieve a good minimizer of Eq. [sent-183, score-0.672]
67 Motivated by Kernelized Locality Sensitive Hashing (KLSH) [13], we instead try to find a set of nonlinear hashing functions using the kernel trick. [sent-185, score-0.715]
68 j=1 where pk (j) denotes j-th element of pk which is a coefficient vector we need to learn. [sent-196, score-0.183]
69 Thus, the k-th bit nonlinear function can be written as fk (x) = pkT k(x) − bk and the objective function of CPH in the kernel space can be written as: mfkin? [sent-201, score-0.328]
70 Spectral Relaxation In this subsection, we discuss how to use spectral relaxation to compute an initial result of fk (x) = pkT k(x) −bk. [sent-215, score-0.15]
71 To simplify the relaxation, we centralize the kerkne(xl )m−atrbix and use bk = 0 as an initial threshold. [sent-216, score-0.178]
72 Gradient descent The eigenvector associated with the largest eigenvalue of eigen-problem (10) provides us an initial solution of pk (the initial value for bk is 0), we then use the gradient descent in pursuit of a better result. [sent-228, score-0.274]
73 n); c th uen infoumrmbelyr orafn bdiotsm floyr hashing csaomdepsl;e α, ε the parameters of CPH; K(·, ·) the kernel function. [sent-239, score-0.667]
74 6: end for 7: Use c hash functions {hk(x) = sgn(p∗kT k(x) b∗k)}kc=1 atos hcre fautnec binary chodes of X. [sent-249, score-0.447]
75 Outpu)t}: c hash functions {hk(x) = sgn(p∗kT k(x) − bk∗)}kc=1; Binary fcuondcetsio fnosr {thhe training samples: (Yx )∈ − { b0, )1}}n×c. [sent-250, score-0.418]
76 Binary codes for the training samples: Y ∈ {0,1} ∂ϕ∂(xx) Since = 21 (1 − ϕ(x)2), by simple algebra, the gradients of J respect t1o pk a(nxd) bk are: ∂J(∂ppkk,bk)=K¯Q, ∂J(∂pbkk,bk)= (−1) · 1TQ where Q = u˜k ? [sent-251, score-0.252]
77 n) samples and train c-bit hash function, the 261 computational complexity of CPH in the training stage is as follows: 1. [sent-271, score-0.412]
78 Experiments In this section, we evaluate our CPH algorithm on the high dimensional nearest neighbors search problem. [sent-289, score-0.118]
79 Following [25, 16, 9], we used three criteria to evaluate different aspects of hashing algorithms as follows: • Mean Average Precision (MAP): This is a classical mMeetarinc Ainv eIrRa community n[6 (]M. [sent-300, score-0.621]
80 AMPA):P T approximates tchael area under precision-recall curve [3] and evaluates the overall performance of a hashing algorithm. [sent-301, score-0.621]
81 This metric has been widely used to evaluate the performance of various hashing algorithms [25, 24, 7, 16, 9, 15]. [sent-302, score-0.621]
82 html • Hash Lookup Precision (HLP): Given a query, all the points Lino otkheu bpu Pcrkeectsis tiohant fHalLl wP)i:th Giniv a nsm aa qulle hamming radius r of the hamming code of the query will be retrieved and a linear scan over these points is performed to return the results. [sent-315, score-0.373]
83 o evaluate the precision with a predefined hamming radius in real scenarios. [sent-329, score-0.143]
84 The HLP is defined as the precision over all the points in the buckets that fall within hamming radius r of the hamming code of the query [24]. [sent-330, score-0.606]
85 Compared methods Seven state-of-the-art hashing algorithms for high dimensional nearest neighbors search are compared as follows: • • • • LSH: Locality Sensitive Hashing [1], which is fundamentally c baalsietyd on tshitei v rean Hdoamsh projection. [sent-337, score-0.765]
86 KLSH: Kernelized locality sensitive hashing [13], wKhLiSchH generalizes tdhe l oLScaHli tmye tshenodsi ttiov tehe h kaeshrnienlg space. [sent-338, score-0.703]
87 ITQ: Iterative quantization [7], which finds a rotation IoTf Qze:r Iot-ecreanttiveree qdu adanttaiz so as [to7 ,m winhimichize fi ntdhes quantization error of mapping this data to the vertices of a zerocentered binary hypercube. [sent-339, score-0.115]
88 SPH: Spherical hashing [9], which uses a hypersphereSbPasHed: Shpahsher fcualnchtaioshni ntog map hdiactha points yinpetor binary codes. [sent-342, score-0.685]
89 The hash lookup Precision @ hamming radius 2 of all the algorithms on the three data sets. [sent-348, score-0.514]
90 Specifically, KLSH, AGH, and CPH use the kernel trick to learn the nonlinear hashing function. [sent-353, score-0.664]
91 ε controls the size of the boundary region of each hashing function. [sent-360, score-0.655]
92 In the experiment, we randomly choose a hyperplane which can evenly separate the data. [sent-361, score-0.25]
93 By explicitly taking into account the two requirements (crossing the sparse region and balanced buckets) of a good hashing method, our CPH consistently outperforms its competitors almost on all the cases. [sent-373, score-0.754]
94 4 shows the hash lookup precision within hamming radius 2 of all the algorithms. [sent-375, score-0.539]
95 This mainly because many buckets become empty as the code length increase. [sent-377, score-0.312]
96 5 clearly shows the superiority of CPH over other hashing methods. [sent-383, score-0.621]
97 Conclusions In this paper, we propose a novel hashing algorithm named Complementary Projection Hashing (CPH) to obtain high search accuracy and high search speed simultaneously. [sent-385, score-0.705]
98 By learning complementary bits, CPH learns a series of hashing functions which cross the sparse data region and generate balanced hash buckets. [sent-386, score-1.224]
99 Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. [sent-394, score-0.673]
100 Compact hashing with joint optimization of search accuracy and time. [sent-437, score-0.653]
wordName wordTfidf (topN-words)
[('hashing', 0.621), ('hash', 0.367), ('cph', 0.32), ('buckets', 0.284), ('hyperplane', 0.158), ('bk', 0.15), ('lsh', 0.136), ('sgn', 0.133), ('vk', 0.107), ('hyperplanes', 0.092), ('evenly', 0.092), ('klsh', 0.092), ('pk', 0.082), ('hamming', 0.082), ('fk', 0.073), ('agh', 0.071), ('bits', 0.069), ('uik', 0.066), ('pktk', 0.064), ('tpk', 0.064), ('wktxi', 0.064), ('complementary', 0.063), ('bit', 0.062), ('bucket', 0.059), ('locality', 0.056), ('neighbors', 0.053), ('hypercubes', 0.053), ('kernelized', 0.051), ('functions', 0.051), ('itq', 0.05), ('kt', 0.049), ('projection', 0.049), ('pkt', 0.048), ('spectral', 0.046), ('balanced', 0.043), ('scan', 0.041), ('xi', 0.041), ('balance', 0.041), ('sph', 0.037), ('requirements', 0.036), ('radius', 0.036), ('points', 0.035), ('crosses', 0.035), ('hk', 0.035), ('region', 0.034), ('query', 0.034), ('nearest', 0.033), ('hlp', 0.032), ('joly', 0.032), ('mfkin', 0.032), ('rtree', 0.032), ('wjtxi', 0.032), ('wktx', 0.032), ('zerocentered', 0.032), ('search', 0.032), ('relaxation', 0.031), ('distributed', 0.03), ('binary', 0.029), ('crossing', 0.029), ('lookup', 0.029), ('centralize', 0.028), ('nmd', 0.028), ('shaanxi', 0.028), ('requirement', 0.028), ('code', 0.028), ('nearby', 0.027), ('quantization', 0.027), ('centralized', 0.026), ('vkt', 0.026), ('condition', 0.026), ('sensitive', 0.026), ('fundamentally', 0.026), ('china', 0.025), ('samples', 0.025), ('precision', 0.025), ('uen', 0.025), ('cross', 0.025), ('sh', 0.024), ('quantized', 0.024), ('spherical', 0.023), ('eigenvector', 0.022), ('nonlinear', 0.022), ('recall', 0.022), ('anchor', 0.022), ('nm', 0.022), ('kernel', 0.021), ('optics', 0.021), ('embedding', 0.02), ('codes', 0.02), ('sparse', 0.02), ('named', 0.02), ('heo', 0.02), ('stage', 0.02), ('eigenvalue', 0.02), ('coefficient', 0.019), ('neighbor', 0.019), ('nthge', 0.019), ('kc', 0.019), ('entropy', 0.018), ('ik', 0.018)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999887 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.
2 0.59320039 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 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.
4 0.42876771 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 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.19082141 337 iccv-2013-Random Grids: Fast Approximate Nearest Neighbors and Range Searching for Image Search
8 0.18036498 400 iccv-2013-Stable Hyper-pooling and Query Expansion for Event Detection
10 0.16123009 162 iccv-2013-Fast Subspace Search via Grassmannian Based Hashing
11 0.11162212 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
12 0.10429615 221 iccv-2013-Joint Inverted Indexing
13 0.092193767 123 iccv-2013-Domain Adaptive Classification
14 0.069226101 333 iccv-2013-Quantize and Conquer: A Dimensionality-Recursive Solution to Clustering, Vector Quantization, and Image Retrieval
15 0.069010779 319 iccv-2013-Point-Based 3D Reconstruction of Thin Objects
16 0.06189141 446 iccv-2013-Visual Semantic Complex Network for Web Images
17 0.057509106 347 iccv-2013-Recursive Estimation of the Stein Center of SPD Matrices and Its Applications
18 0.053082757 222 iccv-2013-Joint Learning of Discriminative Prototypes and Large Margin Nearest Neighbor Classifiers
19 0.047626514 294 iccv-2013-Offline Mobile Instance Retrieval with a Small Memory Footprint
20 0.045966864 378 iccv-2013-Semantic-Aware Co-indexing for Image Retrieval
topicId topicWeight
[(0, 0.115), (1, 0.067), (2, -0.087), (3, -0.111), (4, -0.073), (5, 0.426), (6, 0.023), (7, -0.008), (8, -0.315), (9, 0.206), (10, -0.271), (11, 0.144), (12, -0.019), (13, -0.173), (14, -0.003), (15, 0.044), (16, -0.122), (17, 0.163), (18, -0.155), (19, 0.054), (20, 0.011), (21, 0.066), (22, 0.046), (23, 0.006), (24, 0.018), (25, -0.025), (26, -0.05), (27, -0.007), (28, -0.022), (29, -0.013), (30, -0.006), (31, 0.005), (32, 0.021), (33, -0.009), (34, -0.028), (35, 0.001), (36, -0.002), (37, -0.007), (38, -0.004), (39, 0.005), (40, -0.002), (41, -0.017), (42, 0.018), (43, 0.013), (44, -0.001), (45, 0.016), (46, 0.003), (47, 0.007), (48, -0.024), (49, 0.009)]
simIndex simValue paperId paperTitle
same-paper 1 0.96871954 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.
2 0.94328684 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.93595779 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.88407701 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.87486178 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.39455947 221 iccv-2013-Joint Inverted Indexing
9 0.36810401 400 iccv-2013-Stable Hyper-pooling and Query Expansion for Event Detection
10 0.33847728 337 iccv-2013-Random Grids: Fast Approximate Nearest Neighbors and Range Searching for Image Search
11 0.3097747 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
12 0.26941103 162 iccv-2013-Fast Subspace Search via Grassmannian Based Hashing
13 0.2329202 287 iccv-2013-Neighbor-to-Neighbor Search for Fast Coding of Feature Vectors
15 0.22116151 347 iccv-2013-Recursive Estimation of the Stein Center of SPD Matrices and Its Applications
16 0.20277688 171 iccv-2013-Fix Structured Learning of 2013 ICCV paper k2opt.pdf
17 0.20078921 446 iccv-2013-Visual Semantic Complex Network for Web Images
18 0.19392675 332 iccv-2013-Quadruplet-Wise Image Similarity Learning
19 0.19233972 419 iccv-2013-To Aggregate or Not to aggregate: Selective Match Kernels for Image Search
20 0.19132867 319 iccv-2013-Point-Based 3D Reconstruction of Thin Objects
topicId topicWeight
[(2, 0.188), (7, 0.04), (12, 0.013), (26, 0.058), (31, 0.03), (42, 0.083), (48, 0.011), (64, 0.026), (73, 0.022), (74, 0.012), (77, 0.246), (78, 0.011), (89, 0.14), (95, 0.012)]
simIndex simValue paperId paperTitle
same-paper 1 0.80742168 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.
2 0.74332666 350 iccv-2013-Relative Attributes for Large-Scale Abandoned Object Detection
Author: Quanfu Fan, Prasad Gabbur, Sharath Pankanti
Abstract: Effective reduction of false alarms in large-scale video surveillance is rather challenging, especially for applications where abnormal events of interest rarely occur, such as abandoned object detection. We develop an approach to prioritize alerts by ranking them, and demonstrate its great effectiveness in reducing false positives while keeping good detection accuracy. Our approach benefits from a novel representation of abandoned object alerts by relative attributes, namely staticness, foregroundness and abandonment. The relative strengths of these attributes are quantified using a ranking function[19] learnt on suitably designed low-level spatial and temporal features.These attributes of varying strengths are not only powerful in distinguishing abandoned objects from false alarms such as people and light artifacts, but also computationally efficient for large-scale deployment. With these features, we apply a linear ranking algorithm to sort alerts according to their relevance to the end-user. We test the effectiveness of our approach on both public data sets and large ones collected from the real world.
3 0.72923064 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.
4 0.72449851 142 iccv-2013-Ensemble Projection for Semi-supervised Image Classification
Author: Dengxin Dai, Luc Van_Gool
Abstract: This paper investigates the problem of semi-supervised classification. Unlike previous methods to regularize classifying boundaries with unlabeled data, our method learns a new image representation from all available data (labeled and unlabeled) andperformsplain supervised learning with the new feature. In particular, an ensemble of image prototype sets are sampled automatically from the available data, to represent a rich set of visual categories/attributes. Discriminative functions are then learned on these prototype sets, and image are represented by the concatenation of their projected values onto the prototypes (similarities to them) for further classification. Experiments on four standard datasets show three interesting phenomena: (1) our method consistently outperforms previous methods for semi-supervised image classification; (2) our method lets itself combine well with these methods; and (3) our method works well for self-taught image classification where unlabeled data are not coming from the same distribution as la- beled ones, but rather from a random collection of images.
5 0.7175436 180 iccv-2013-From Where and How to What We See
Author: S. Karthikeyan, Vignesh Jagadeesh, Renuka Shenoy, Miguel Ecksteinz, B.S. Manjunath
Abstract: Eye movement studies have confirmed that overt attention is highly biased towards faces and text regions in images. In this paper we explore a novel problem of predicting face and text regions in images using eye tracking data from multiple subjects. The problem is challenging as we aim to predict the semantics (face/text/background) only from eye tracking data without utilizing any image information. The proposed algorithm spatially clusters eye tracking data obtained in an image into different coherent groups and subsequently models the likelihood of the clusters containing faces and text using afully connectedMarkov Random Field (MRF). Given the eye tracking datafrom a test image, itpredicts potential face/head (humans, dogs and cats) and text locations reliably. Furthermore, the approach can be used to select regions of interest for further analysis by object detectors for faces and text. The hybrid eye position/object detector approach achieves better detection performance and reduced computation time compared to using only the object detection algorithm. We also present a new eye tracking dataset on 300 images selected from ICDAR, Street-view, Flickr and Oxford-IIIT Pet Dataset from 15 subjects.
6 0.71586478 446 iccv-2013-Visual Semantic Complex Network for Web Images
7 0.71353638 13 iccv-2013-A General Two-Step Approach to Learning-Based Hashing
8 0.71322119 294 iccv-2013-Offline Mobile Instance Retrieval with a Small Memory Footprint
9 0.70740139 352 iccv-2013-Revisiting Example Dependent Cost-Sensitive Learning with Decision Trees
10 0.70572835 244 iccv-2013-Learning View-Invariant Sparse Representations for Cross-View Action Recognition
11 0.70522594 374 iccv-2013-Salient Region Detection by UFO: Uniqueness, Focusness and Objectness
12 0.70414513 214 iccv-2013-Improving Graph Matching via Density Maximization
13 0.70254672 181 iccv-2013-Frustratingly Easy NBNN Domain Adaptation
14 0.6988759 239 iccv-2013-Learning Hash Codes with Listwise Supervision
15 0.68914545 409 iccv-2013-Supervised Binary Hash Code Learning with Jensen Shannon Divergence
16 0.68227065 153 iccv-2013-Face Recognition Using Face Patch Networks
17 0.68096292 229 iccv-2013-Large-Scale Video Hashing via Structure Learning
18 0.67654121 322 iccv-2013-Pose Estimation and Segmentation of People in 3D Movies
19 0.67458153 85 iccv-2013-Compositional Models for Video Event Detection: A Multiple Kernel Learning Latent Variable Approach
20 0.66111028 248 iccv-2013-Learning to Rank Using Privileged Information