iccv iccv2013 iccv2013-20 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Zhaowen Wang, Jianchao Yang, Nasser Nasrabadi, Thomas Huang
Abstract: Sparse Representation-based Classification (SRC) is a powerful tool in distinguishing signal categories which lie on different subspaces. Despite its wide application to visual recognition tasks, current understanding of SRC is solely based on a reconstructive perspective, which neither offers any guarantee on its classification performance nor provides any insight on how to design a discriminative dictionary for SRC. In this paper, we present a novel perspective towards SRC and interpret it as a margin classifier. The decision boundary and margin of SRC are analyzed in local regions where the support of sparse code is stable. Based on the derived margin, we propose a hinge loss function as the gauge for the classification performance of SRC. A stochastic gradient descent algorithm is implemented to maximize the margin of SRC and obtain more discriminative dictionaries. Experiments validate the effectiveness of the proposed approach in predicting classification performance and improving dictionary quality over reconstructive ones. Classification results competitive with other state-ofthe-art sparse coding methods are reported on several data sets.
Reference: text
sentIndex sentText sentNum sentScore
1 Despite its wide application to visual recognition tasks, current understanding of SRC is solely based on a reconstructive perspective, which neither offers any guarantee on its classification performance nor provides any insight on how to design a discriminative dictionary for SRC. [sent-12, score-0.422]
2 In this paper, we present a novel perspective towards SRC and interpret it as a margin classifier. [sent-13, score-0.374]
3 The decision boundary and margin of SRC are analyzed in local regions where the support of sparse code is stable. [sent-14, score-0.761]
4 A stochastic gradient descent algorithm is implemented to maximize the margin of SRC and obtain more discriminative dictionaries. [sent-16, score-0.537]
5 Experiments validate the effectiveness of the proposed approach in predicting classification performance and improving dictionary quality over reconstructive ones. [sent-17, score-0.408]
6 In SRC, a test signal x is represented as a sparse linear combination of the atoms in a dictionary D composed of training data from all classes, i. [sent-21, score-0.703]
7 However, due to noise corruption and subspace overlap, the nonzero coefficients in α are usually associated with atoms from more than one class in practice. [sent-26, score-0.342]
8 Due to the absence of a feasible performance metric for SRC, the design of its dictionary (which serves as the parameter for both representation and classification) has been more or less heuristic so far. [sent-30, score-0.289]
9 Originally, an SRC dictionary is constructed by directly including all the training samples [24], which is not efficient and practical when the size of training set is huge. [sent-31, score-0.363]
10 Traditional dictionary learning methods specialized for sparse representation, such as Method of Optimal Direction (MOD) [8], K-SVD [1], and the ? [sent-33, score-0.401]
11 In this paper, we present a novel margin-based perspective towards SRC and propose a maximum margin performance metric that is specifically designed for learning the dictionaries of SRC. [sent-40, score-0.528]
12 Large margin classifiers [2] are well studied by the machine learning community, and they have many desirable properties such as robustness to noise and outlier, and theoretical connection with generalization bound. [sent-41, score-0.396]
13 Due to the complex nonlinear mapping induced by sparse coding, evaluating the margin of SRC is nontrivial. [sent-42, score-0.451]
14 2 that the decision boundary of SRC is a continuous piecewise quadratic surface, and the margin of a sample is approximated as its distance to the tangent plane of the decision function in a local region where the support of sparse code is stable. [sent-44, score-1.205]
15 3 to use the hinge loss of approximated margin as a metric for the classification performance and generalization capability of SRC. [sent-46, score-0.557]
16 A stochastic gradient descent algorithm is then implemented to maximize the margin of SRC and obtain more discriminative dictionaries. [sent-47, score-0.537]
17 To the best of our knowledge, we are the first to conduct margin analysis on SRC and optimize its dictionary by margin maximization. [sent-48, score-0.944]
18 It is shown on several data sets that our algorithm can learn very compact dictionaries that attain much higher accuracies than the conventional dictionaries in SRC; the performance is also competitive with other state-of-the-art methods based on sparse coding. [sent-51, score-0.365]
19 In SRC, a dictionary D ∈ Rm×n with n atoms iys composed o Inf CSR RclCa,ssa-dwicisteio snuabr-ydDict ∈ion Raries Dc ∈ Rm×nc such that D = [D1, . [sent-61, score-0.505]
20 SRC makes classification decision based on the residual of signal approximated by the sub-code of each class: rc = ? [sent-77, score-0.441]
21 Consider two classes c1 and c2, and assume the dictionary D is given. [sent-87, score-0.296]
22 e Arelflo three, tchoen ldoi-cal neighborhood around x where the active set (and signs1) of signal’s sparse code remains stable is a convex polytope. [sent-112, score-0.299]
23 1 The decision function of SRC is a piecewise quadratic function of input signal with the form of f(x) = fΛ (x) , (9) for any x in the convex polytope defined by Eq. [sent-117, score-0.41]
24 Since there are a set of quadratic decision functions each devoted to a local area of x, SRC is capable of classifying data which cannot be linearly or quadratically separated in a global sense. [sent-119, score-0.26]
25 The decision boundary of SRC can be adapted to each local area in the most discriminative and compact way, which shares a similar idea with locally adaptive metric learning [7]. [sent-120, score-0.382]
26 To find the decision boundary of SRC, we simply need to check at what values of x, f(x) will vary from positive to negative, as the decision threshold is 0. [sent-123, score-0.451]
27 Thus we can easily see that f(x) is also continuous over the entire domain of x, and the points on the decision boundary of SRC have to satisfy f(x) = 0, which is stated in the following proposition. [sent-125, score-0.275]
28 2 The decision boundary of SRC is a piecewise quadratic hypersurface defined by f(x) = 0 . [sent-127, score-0.378]
29 Margin Approximation for SRC For linear classifiers, the margin of a sample is defined as its distance from the decision hyperplane. [sent-130, score-0.574]
30 In the context of SRC, we similarly define the margin of a sample x0 as its distance to the closest point on the decision boundary: minf(x)=0 ? [sent-131, score-0.574]
31 function f(x), it is difficult to evaluate the associated margin directly. [sent-136, score-0.36]
32 Instead, we estimate x0’s margin by approximating f(x) with its tangent plane at x0. [sent-137, score-0.39]
33 1, if we have two contiguous polytopes corresponding respectively to two stable active sets, Λ1 and Λ2, which are the same except for one entry, then with a high probability the gradient of decision function in the two polytopes will be approximately the same near their border: ∇fΛ1 ≈ ∇fΛ2 . [sent-155, score-0.578]
34 3, we are more interested in the data samples near the decision boundary when optimizing a large margin classifier. [sent-158, score-0.638]
35 Therefore, our approximation is also suitable for the use with margin maximization. [sent-160, score-0.368]
36 Once the decision function f(x) is linearly approximated, the margin γ of x0 is simply its distance (with sign) to the hyperplane f(x) = 0: γ(x0) =? [sent-161, score-0.556]
37 It should be noted that the decision function gradient ∇f is not defined on the borders of convex polytopes with d∇ifffe irse nnto atc dteivfien seedt so. [sent-168, score-0.361]
38 f x0 itself should not be taken into account when we calculate the margin of x0. [sent-180, score-0.34]
39 Top: decision function f(x) for class “7” against class “4” in the MNIST data set and its approximations, where x changes in the 1D neighborhood of a sample x0 in the direction of gradient ∇f(x0) . [sent-182, score-0.454]
40 M2 graphically illustrates our margin approximation approach for one image sample x0 from class “7” in the MNIST digits data set. [sent-192, score-0.525]
41 We evaluate the ground truth value of decision function f(x) at a series of data points x in a 1D interval generated by shifting x0 along the direction of ∇f(x0), and record all the points where the active set of sparse code changes. [sent-193, score-0.498]
42 We can see that the piecewise smooth f(x) (plotted as a red curve) can be well approximated by the tangent of local quadratic decision function (green asterisk) in a neighborhood where the active set (whose stable region is delimitated by red plus) does not change too much. [sent-194, score-0.519]
43 The margin (indicated by golden arrow) we find for this example is very close to its true value. [sent-197, score-0.34]
44 2 also shows how the appearance of the image signal is distorted to the imposter class “4” from its true class “7” as it moves along the gradient of decision function. [sent-199, score-0.537]
45 Maximum-Margin Dictionary Learning The concept of maximum margin has been widely employed in training classifiers, and it serves as the cornerstone of many popular models including SVM. [sent-201, score-0.368]
46 The classi- cal analysis on SVM [22] established the relationship between the margin of the training set and the classifier’s generalization error bound. [sent-202, score-0.398]
47 Recently, a similar effort has been made for sparsity-based linear predictive classifier [18], which motivates us to design the dictionary for SRC from a perspective based on the margin analysis given in Sec. [sent-203, score-0.659]
48 Learning a discriminative dictionary pDle∗s f:o {rx SRC can be generally formulated as the following optimization problem: D∗= argD m∈iDnN1? [sent-209, score-0.298]
49 (12) where D denotes Rm×n dictionary space with unit-norm awthoemres. [sent-211, score-0.264]
50 TDo dmeanxoitmesiz Re the margin of a training sample close to the decision boundary of SRC, we follow the similar idea in SVM and define the loss function L(x, y; D) using a multiSclVasMs hinge feufinnceti thoen: L(x,y;D) =? [sent-212, score-0.747]
51 =y where b is a non-negative parameter controlling the minimum required margin between classes, and γ(x,y,c) =2? [sent-215, score-0.34]
52 2, (14) is the margin of sample x with label y calculated against a = competing class c y, which is adopted from Eq. [sent-217, score-0.436]
53 Different from what is defined in SVM, the margin we use here is unnormalized since the unit dictionary atom constraint ensures the objective function is bounded. [sent-222, score-0.661]
54 Moreover, (13) promotes multi-class margin by summing over all possible imposter classes c and optimizing the single parameter D that is shared by all classes. [sent-223, score-0.477]
55 Suc−h requirement is consistent with the classification scheme in (2), and it has also been enforced in other dictionary learning algorithms such as [16]. [sent-226, score-0.347]
56 In addition, we further introduce a novel term in the denominator of (14), which normalizes the nonuniform gradient of SRC decision function in different local regions and leads to a better estimation to the true sample margin. [sent-227, score-0.315]
57 In our algorithm, the dictionary is first initialized with a reasonable guess D0 (which can be the concatenation of sub-dictionaries obtained by applying K-means or random selection to each class). [sent-232, score-0.264]
58 Then we go through the whole data set multiple times and iteratively update the dictionary with decreasing step size until convergence. [sent-233, score-0.264]
59 In the t-th iteration, a single sample (x, y) is drawn from the data set randomly and the dictionary is updated in the direction of the gradient of its loss function: Dt = Dt−1 − ρt[∇DL(x,y; Dt−1)]T, (15) where ρt is the step size at iteration t. [sent-234, score-0.412]
60 =sses y γw(ixth, zero margin gradient (γ(x, y, c) > b) or zero sub-gradient (γ(x, y, c) = b). [sent-241, score-0.401]
61 We realize from the results in [18] that the active set Λ for any particular sample x is stable when there is a small perturbation applied to dictionary D. [sent-245, score-0.456]
62 Since the approximation of margin is also based on a locally stable Λ, we can safely deduce that γ(x, y, c) is a differentiable function of D. [sent-246, score-0.475]
63 In addition, since (14) depends only on DΛ, we just need to update those dictionary atoms corresponding to the active set Λ of each sample x. [sent-248, score-0.636]
64 The dictionary updating rule in (15) can be rewritten as : DtΛ = DΛt−1 + ρt · [∇DΛγ(x, y, c)]T, (17) which is repeated for all c ∈ C(x, y). [sent-249, score-0.264]
65 cO fonrcme th oef dictionary is updated in the current iteration, all its atoms are projected to the unit ball to comply with the constraint that D ∈ D. [sent-251, score-0.525]
66 (17) will add ec to all the active atoms associated with class c and subtract ey from all the active atoms associated with class y, both with a scaling factor proportional to each atom’s sparse coefficient. [sent-262, score-0.967]
67 In addition, (17) also uses the overall reconstruction error e and the projections of ec and ey as the ingredients to update the active atoms from all the classes, which is reasonable because the sparse code is jointly determined by all the active atoms. [sent-264, score-0.696]
68 (16) that only those difficult samples that have small margins against the imposter classes are selected to participate in dictionary training. [sent-266, score-0.541]
69 The accuracy of SRC margin approximation, which is key to the effectiveness of our method, is first investigated. [sent-273, score-0.34]
70 Because it is impossible to find the exact margin of a sample 1221 0. [sent-274, score-0.378]
71 Distributions of estimated margin γ(x) and residual different rc2 rc1 plotted against directional margin measured in the gradient d−irerction ∇f(x). [sent-276, score-0.862]
72 x0, we use the shortest distance between x0 and the decision boundary in the gradient direction ∇f(x0) as a surrogate to tbhoeu ground ntr tuhthe margin. [sent-279, score-0.339]
73 Dictionary atoms for MNIST digits data, learned using unsupervised sparse coding (row 1, 3) and MMDL (row 2, 4). [sent-304, score-0.466]
74 Correlation between the first principal component of atoms from different dictionaries and the LDA directions of the MNIST training data. [sent-307, score-0.398]
75 The image patterns of some dictionary atoms obtained using MMDL are shown in Fig. [sent-311, score-0.505]
76 5, together with those obtained using unsupervised sparse coding [13], which were used to initialize the dictionary in MMDL. [sent-312, score-0.428]
77 The discriminative atoms trained with MMDL look quite different from their initial reconstructive appearances, and place more emphasis on local edge features that are unique to each class. [sent-313, score-0.342]
78 The discriminative power of our learned dictionary can be further demonstrated in Fig. [sent-314, score-0.298]
79 6, which shows that, compared with K-means and unsupervised sparse coding, the MMDL algorithm learns dictionary atoms whose first principle component has a much higher correlation with most of the LDA directions (especially the first one) of the training data. [sent-315, score-0.712]
80 Although LDA directions may not be optimal for SRC, our dictionary atoms appear to be more devoted to discriminative features instead of reconstructive ones. [sent-316, score-0.655]
81 For both data sets, we compare the performance of SRC with dictionaries obtained from the full training set (“Full”), random subsampling of training set (“Subsample”), KSVD [1], K-means (“Kmeans”), unsupervised sparse coding (“Unsup”) [13], and our MMDL algorithm. [sent-329, score-0.323]
82 For extended YaleB(AR face), 15(5) atoms per subject are used for all the dictionaries expect for “Full”, and λ is set as 0. [sent-331, score-0.344]
83 MMDL is shown to be advantageous over other methods in terms of both accuracy and dictionary compactness, residual for predicted class Figure 7. [sent-340, score-0.407]
84 Distributions of correctly and incorrectly classified test samples plotted against estimated margin and reconstruction residual using the atoms from predicted class. [sent-341, score-0.775]
85 From left to right: original sample; reconstruction with atoms of predicted class; reconstruction with atoms of truth class; sparse coefficients. [sent-347, score-0.677]
86 Note that we are unable to evaluate SRC with the “Full” setting because the memory required for the operation on such a huge dictionary exceeds our system capacity (32GB). [sent-349, score-0.264]
87 7 reveals the distinct distributions of correctly and incorrectly classified samples in terms of estimated margin and reconstruction residual with predicted class. [sent-351, score-0.499]
88 The incorrect samples are observed to have higher residuals and smaller margins, which is expected since hard samples typically can not be well represented by the corresponding classes and lie close to the boundary of imposter classes. [sent-352, score-0.282]
89 This provides another evidence to show the accuracy of our margin estimation. [sent-353, score-0.34]
90 Therefore, the estimated margin can also serve as a metric of classification confidence, based on which the classification results could be further refined. [sent-354, score-0.479]
91 The digit “7” in (a) is misclassified as “2” with a large margin due to the strong inter-class similarity and high intra-class variation insufficiently captured by the training set. [sent-357, score-0.392]
92 The digit “5” in (b) cannot be faithfully represented by any class; such an outlier has a very small margin and thus can be potentially detected for special treatment. [sent-358, score-0.364]
93 Conclusion and Future Directions An in-depth analysis ofthe classification margin for SRC is presented in this paper. [sent-360, score-0.397]
94 We show that the decision boundary of SRC is a continuous piecewise quadratic hypersurface, and it can be approximated by its tangent plane in a local region to facilitate the margin estimation. [sent-361, score-0.785]
95 A learning algorithm based on stochastic gradient descent is derived to maximize the margins of training samples, which generates compact dictionaries with substantially improved discriminative power observed on several data sets. [sent-362, score-0.472]
96 In the future work, we will explore better ways to approximate the margin of samples far away from the decision boundary in the hope to further improve dictionary quality. [sent-363, score-0.902]
97 It would also be of great interest to establish a strict relationship between the margin and generalization performance of SRC, so that a better knowledge can be gained about under what circumstances is SRC expected to perform best. [sent-364, score-0.37]
98 Learning a discriminative dictionary for sparse coding via label consistent K-SVD. [sent-448, score-0.462]
99 Classification and clustering via dictionary learning with structured incoherence and shared features. [sent-518, score-0.327]
100 Distance metric learning for large margin nearest neighbor classification. [sent-538, score-0.391]
wordName wordTfidf (topN-words)
[('src', 0.62), ('margin', 0.34), ('dictionary', 0.264), ('mmdl', 0.252), ('atoms', 0.241), ('decision', 0.196), ('sparse', 0.111), ('imposter', 0.105), ('dictionaries', 0.103), ('margins', 0.097), ('mnist', 0.094), ('active', 0.093), ('polytopes', 0.084), ('reconstructive', 0.067), ('yaleb', 0.065), ('residual', 0.063), ('gradient', 0.061), ('digits', 0.061), ('signal', 0.059), ('boundary', 0.059), ('class', 0.058), ('classification', 0.057), ('code', 0.055), ('stochastic', 0.053), ('coding', 0.053), ('tangent', 0.05), ('face', 0.048), ('dt', 0.047), ('pages', 0.046), ('ec', 0.046), ('samples', 0.043), ('hypersurface', 0.042), ('unsup', 0.042), ('army', 0.042), ('quadratic', 0.041), ('piecewise', 0.04), ('stable', 0.04), ('hinge', 0.04), ('approximated', 0.039), ('ar', 0.039), ('sample', 0.038), ('atom', 0.037), ('incoherence', 0.037), ('lvq', 0.037), ('plotted', 0.035), ('dc', 0.035), ('nas', 0.034), ('polytope', 0.034), ('discriminative', 0.034), ('perspective', 0.034), ('rm', 0.033), ('mairal', 0.033), ('proposition', 0.032), ('classes', 0.032), ('reconstruction', 0.031), ('generalization', 0.03), ('lda', 0.029), ('descent', 0.029), ('approximation', 0.028), ('training', 0.028), ('rc', 0.027), ('accuracies', 0.027), ('loss', 0.026), ('safely', 0.026), ('ry', 0.026), ('learning', 0.026), ('directions', 0.026), ('adobe', 0.026), ('ey', 0.026), ('sign', 0.025), ('metric', 0.025), ('digit', 0.024), ('discrimination', 0.024), ('bach', 0.024), ('pc', 0.023), ('direction', 0.023), ('devoted', 0.023), ('directional', 0.023), ('coefficients', 0.022), ('whose', 0.022), ('predicted', 0.022), ('icassp', 0.021), ('perturbation', 0.021), ('predictive', 0.021), ('compact', 0.021), ('subspace', 0.021), ('tno', 0.021), ('nx', 0.021), ('locally', 0.021), ('continuous', 0.02), ('ball', 0.02), ('ff', 0.02), ('predicting', 0.02), ('maximize', 0.02), ('dl', 0.02), ('ponce', 0.02), ('tx', 0.02), ('function', 0.02), ('correlation', 0.02), ('collaborative', 0.019)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000007 20 iccv-2013-A Max-Margin Perspective on Sparse Representation-Based Classification
Author: Zhaowen Wang, Jianchao Yang, Nasser Nasrabadi, Thomas Huang
Abstract: Sparse Representation-based Classification (SRC) is a powerful tool in distinguishing signal categories which lie on different subspaces. Despite its wide application to visual recognition tasks, current understanding of SRC is solely based on a reconstructive perspective, which neither offers any guarantee on its classification performance nor provides any insight on how to design a discriminative dictionary for SRC. In this paper, we present a novel perspective towards SRC and interpret it as a margin classifier. The decision boundary and margin of SRC are analyzed in local regions where the support of sparse code is stable. Based on the derived margin, we propose a hinge loss function as the gauge for the classification performance of SRC. A stochastic gradient descent algorithm is implemented to maximize the margin of SRC and obtain more discriminative dictionaries. Experiments validate the effectiveness of the proposed approach in predicting classification performance and improving dictionary quality over reconstructive ones. Classification results competitive with other state-ofthe-art sparse coding methods are reported on several data sets.
2 0.35474074 45 iccv-2013-Affine-Constrained Group Sparse Coding and Its Application to Image-Based Classifications
Author: Yu-Tseh Chi, Mohsen Ali, Muhammad Rushdi, Jeffrey Ho
Abstract: This paper proposes a novel approach for sparse coding that further improves upon the sparse representation-based classification (SRC) framework. The proposed framework, Affine-Constrained Group Sparse Coding (ACGSC), extends the current SRC framework to classification problems with multiple input samples. Geometrically, the affineconstrained group sparse coding essentially searches for the vector in the convex hull spanned by the input vectors that can best be sparse coded using the given dictionary. The resulting objectivefunction is still convex and can be efficiently optimized using iterative block-coordinate descent scheme that is guaranteed to converge. Furthermore, we provide a form of sparse recovery result that guarantees, at least theoretically, that the classification performance of the constrained group sparse coding should be at least as good as the group sparse coding. We have evaluated the proposed approach using three different recognition experiments that involve illumination variation of faces and textures, and face recognition under occlusions. Prelimi- nary experiments have demonstrated the effectiveness of the proposed approach, and in particular, the results from the recognition/occlusion experiment are surprisingly accurate and robust.
3 0.28721523 276 iccv-2013-Multi-attributed Dictionary Learning for Sparse Coding
Author: Chen-Kuo Chiang, Te-Feng Su, Chih Yen, Shang-Hong Lai
Abstract: We present a multi-attributed dictionary learning algorithm for sparse coding. Considering training samples with multiple attributes, a new distance matrix is proposed by jointly incorporating data and attribute similarities. Then, an objective function is presented to learn categorydependent dictionaries that are compact (closeness of dictionary atoms based on data distance and attribute similarity), reconstructive (low reconstruction error with correct dictionary) and label-consistent (encouraging the labels of dictionary atoms to be similar). We have demonstrated our algorithm on action classification and face recognition tasks on several publicly available datasets. Experimental results with improved performance over previous dictionary learning methods are shown to validate the effectiveness of the proposed algorithm.
4 0.28200841 161 iccv-2013-Fast Sparsity-Based Orthogonal Dictionary Learning for Image Restoration
Author: Chenglong Bao, Jian-Feng Cai, Hui Ji
Abstract: In recent years, how to learn a dictionary from input images for sparse modelling has been one very active topic in image processing and recognition. Most existing dictionary learning methods consider an over-complete dictionary, e.g. the K-SVD method. Often they require solving some minimization problem that is very challenging in terms of computational feasibility and efficiency. However, if the correlations among dictionary atoms are not well constrained, the redundancy of the dictionary does not necessarily improve the performance of sparse coding. This paper proposed a fast orthogonal dictionary learning method for sparse image representation. With comparable performance on several image restoration tasks, the proposed method is much more computationally efficient than the over-complete dictionary based learning methods.
5 0.27009684 384 iccv-2013-Semi-supervised Robust Dictionary Learning via Efficient l-Norms Minimization
Author: Hua Wang, Feiping Nie, Weidong Cai, Heng Huang
Abstract: Representing the raw input of a data set by a set of relevant codes is crucial to many computer vision applications. Due to the intrinsic sparse property of real-world data, dictionary learning, in which the linear decomposition of a data point uses a set of learned dictionary bases, i.e., codes, has demonstrated state-of-the-art performance. However, traditional dictionary learning methods suffer from three weaknesses: sensitivity to noisy and outlier samples, difficulty to determine the optimal dictionary size, and incapability to incorporate supervision information. In this paper, we address these weaknesses by learning a Semi-Supervised Robust Dictionary (SSR-D). Specifically, we use the ℓ2,0+ norm as the loss function to improve the robustness against outliers, and develop a new structured sparse regularization com, , tom. . cai@sydney . edu . au , heng@uta .edu make the learning tasks easier to deal with and reduce the computational cost. For example, in image tagging, instead of using the raw pixel-wise features, semi-local or patch- based features, such as SIFT and geometric blur, are usually more desirable to achieve better performance. In practice, finding a set of compact features bases, also referred to as dictionary, with enhanced representative and discriminative power, plays a significant role in building a successful computer vision system. In this paper, we explore this important problem by proposing a novel formulation and its solution for learning Semi-Supervised Robust Dictionary (SSRD), where we examine the challenges in dictionary learning, and seek opportunities to overcome them and improve the dictionary qualities. 1.1. Challenges in Dictionary Learning to incorporate the supervision information in dictionary learning, without incurring additional parameters. Moreover, the optimal dictionary size is automatically learned from the input data. Minimizing the derived objective function is challenging because it involves many non-smooth ℓ2,0+ -norm terms. We present an efficient algorithm to solve the problem with a rigorous proof of the convergence of the algorithm. Extensive experiments are presented to show the superior performance of the proposed method.
6 0.25966352 188 iccv-2013-Group Sparsity and Geometry Constrained Dictionary Learning for Action Recognition from Depth Maps
7 0.22044803 354 iccv-2013-Robust Dictionary Learning by Error Source Decomposition
8 0.18373102 197 iccv-2013-Hierarchical Joint Max-Margin Learning of Mid and Top Level Representations for Visual Recognition
9 0.18172495 244 iccv-2013-Learning View-Invariant Sparse Representations for Cross-View Action Recognition
10 0.16706233 398 iccv-2013-Sparse Variation Dictionary Learning for Face Recognition with a Single Training Sample per Person
11 0.15459621 14 iccv-2013-A Generalized Iterated Shrinkage Algorithm for Non-convex Sparse Coding
12 0.15413977 51 iccv-2013-Anchored Neighborhood Regression for Fast Example-Based Super-Resolution
13 0.15397887 6 iccv-2013-A Convex Optimization Framework for Active Learning
14 0.14182499 359 iccv-2013-Robust Object Tracking with Online Multi-lifespan Dictionary Learning
15 0.1258799 114 iccv-2013-Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution
16 0.11488962 97 iccv-2013-Coupling Alignments with Recognition for Still-to-Video Face Recognition
17 0.10925776 265 iccv-2013-Mining Motion Atoms and Phrases for Complex Action Recognition
18 0.10562447 96 iccv-2013-Coupled Dictionary and Feature Space Learning with Applications to Cross-Domain Image Synthesis and Recognition
19 0.10526194 448 iccv-2013-Weakly Supervised Learning of Image Partitioning Using Decision Trees with Structured Split Criteria
20 0.10062961 232 iccv-2013-Latent Space Sparse Subspace Clustering
topicId topicWeight
[(0, 0.195), (1, 0.148), (2, -0.119), (3, -0.035), (4, -0.314), (5, -0.139), (6, -0.123), (7, -0.038), (8, -0.052), (9, -0.047), (10, 0.006), (11, 0.067), (12, 0.018), (13, 0.039), (14, -0.046), (15, 0.038), (16, -0.046), (17, 0.002), (18, -0.017), (19, 0.051), (20, -0.017), (21, -0.06), (22, -0.015), (23, 0.021), (24, 0.021), (25, -0.047), (26, 0.002), (27, 0.072), (28, 0.123), (29, -0.032), (30, -0.04), (31, -0.018), (32, -0.085), (33, -0.064), (34, -0.023), (35, 0.046), (36, 0.032), (37, -0.017), (38, 0.028), (39, 0.008), (40, 0.028), (41, 0.012), (42, -0.0), (43, 0.075), (44, -0.032), (45, -0.03), (46, 0.013), (47, -0.028), (48, -0.006), (49, 0.073)]
simIndex simValue paperId paperTitle
same-paper 1 0.96536815 20 iccv-2013-A Max-Margin Perspective on Sparse Representation-Based Classification
Author: Zhaowen Wang, Jianchao Yang, Nasser Nasrabadi, Thomas Huang
Abstract: Sparse Representation-based Classification (SRC) is a powerful tool in distinguishing signal categories which lie on different subspaces. Despite its wide application to visual recognition tasks, current understanding of SRC is solely based on a reconstructive perspective, which neither offers any guarantee on its classification performance nor provides any insight on how to design a discriminative dictionary for SRC. In this paper, we present a novel perspective towards SRC and interpret it as a margin classifier. The decision boundary and margin of SRC are analyzed in local regions where the support of sparse code is stable. Based on the derived margin, we propose a hinge loss function as the gauge for the classification performance of SRC. A stochastic gradient descent algorithm is implemented to maximize the margin of SRC and obtain more discriminative dictionaries. Experiments validate the effectiveness of the proposed approach in predicting classification performance and improving dictionary quality over reconstructive ones. Classification results competitive with other state-ofthe-art sparse coding methods are reported on several data sets.
2 0.90173602 384 iccv-2013-Semi-supervised Robust Dictionary Learning via Efficient l-Norms Minimization
Author: Hua Wang, Feiping Nie, Weidong Cai, Heng Huang
Abstract: Representing the raw input of a data set by a set of relevant codes is crucial to many computer vision applications. Due to the intrinsic sparse property of real-world data, dictionary learning, in which the linear decomposition of a data point uses a set of learned dictionary bases, i.e., codes, has demonstrated state-of-the-art performance. However, traditional dictionary learning methods suffer from three weaknesses: sensitivity to noisy and outlier samples, difficulty to determine the optimal dictionary size, and incapability to incorporate supervision information. In this paper, we address these weaknesses by learning a Semi-Supervised Robust Dictionary (SSR-D). Specifically, we use the ℓ2,0+ norm as the loss function to improve the robustness against outliers, and develop a new structured sparse regularization com, , tom. . cai@sydney . edu . au , heng@uta .edu make the learning tasks easier to deal with and reduce the computational cost. For example, in image tagging, instead of using the raw pixel-wise features, semi-local or patch- based features, such as SIFT and geometric blur, are usually more desirable to achieve better performance. In practice, finding a set of compact features bases, also referred to as dictionary, with enhanced representative and discriminative power, plays a significant role in building a successful computer vision system. In this paper, we explore this important problem by proposing a novel formulation and its solution for learning Semi-Supervised Robust Dictionary (SSRD), where we examine the challenges in dictionary learning, and seek opportunities to overcome them and improve the dictionary qualities. 1.1. Challenges in Dictionary Learning to incorporate the supervision information in dictionary learning, without incurring additional parameters. Moreover, the optimal dictionary size is automatically learned from the input data. Minimizing the derived objective function is challenging because it involves many non-smooth ℓ2,0+ -norm terms. We present an efficient algorithm to solve the problem with a rigorous proof of the convergence of the algorithm. Extensive experiments are presented to show the superior performance of the proposed method.
3 0.87419784 161 iccv-2013-Fast Sparsity-Based Orthogonal Dictionary Learning for Image Restoration
Author: Chenglong Bao, Jian-Feng Cai, Hui Ji
Abstract: In recent years, how to learn a dictionary from input images for sparse modelling has been one very active topic in image processing and recognition. Most existing dictionary learning methods consider an over-complete dictionary, e.g. the K-SVD method. Often they require solving some minimization problem that is very challenging in terms of computational feasibility and efficiency. However, if the correlations among dictionary atoms are not well constrained, the redundancy of the dictionary does not necessarily improve the performance of sparse coding. This paper proposed a fast orthogonal dictionary learning method for sparse image representation. With comparable performance on several image restoration tasks, the proposed method is much more computationally efficient than the over-complete dictionary based learning methods.
4 0.87235731 354 iccv-2013-Robust Dictionary Learning by Error Source Decomposition
Author: Zhuoyuan Chen, Ying Wu
Abstract: Sparsity models have recently shown great promise in many vision tasks. Using a learned dictionary in sparsity models can in general outperform predefined bases in clean data. In practice, both training and testing data may be corrupted and contain noises and outliers. Although recent studies attempted to cope with corrupted data and achieved encouraging results in testing phase, how to handle corruption in training phase still remains a very difficult problem. In contrast to most existing methods that learn the dictionaryfrom clean data, this paper is targeted at handling corruptions and outliers in training data for dictionary learning. We propose a general method to decompose the reconstructive residual into two components: a non-sparse component for small universal noises and a sparse component for large outliers, respectively. In addition, , further analysis reveals the connection between our approach and the “partial” dictionary learning approach, updating only part of the prototypes (or informative codewords) with remaining (or noisy codewords) fixed. Experiments on synthetic data as well as real applications have shown satisfactory per- formance of this new robust dictionary learning approach.
5 0.84773362 45 iccv-2013-Affine-Constrained Group Sparse Coding and Its Application to Image-Based Classifications
Author: Yu-Tseh Chi, Mohsen Ali, Muhammad Rushdi, Jeffrey Ho
Abstract: This paper proposes a novel approach for sparse coding that further improves upon the sparse representation-based classification (SRC) framework. The proposed framework, Affine-Constrained Group Sparse Coding (ACGSC), extends the current SRC framework to classification problems with multiple input samples. Geometrically, the affineconstrained group sparse coding essentially searches for the vector in the convex hull spanned by the input vectors that can best be sparse coded using the given dictionary. The resulting objectivefunction is still convex and can be efficiently optimized using iterative block-coordinate descent scheme that is guaranteed to converge. Furthermore, we provide a form of sparse recovery result that guarantees, at least theoretically, that the classification performance of the constrained group sparse coding should be at least as good as the group sparse coding. We have evaluated the proposed approach using three different recognition experiments that involve illumination variation of faces and textures, and face recognition under occlusions. Prelimi- nary experiments have demonstrated the effectiveness of the proposed approach, and in particular, the results from the recognition/occlusion experiment are surprisingly accurate and robust.
6 0.83378571 276 iccv-2013-Multi-attributed Dictionary Learning for Sparse Coding
7 0.77624553 188 iccv-2013-Group Sparsity and Geometry Constrained Dictionary Learning for Action Recognition from Depth Maps
8 0.77059656 197 iccv-2013-Hierarchical Joint Max-Margin Learning of Mid and Top Level Representations for Visual Recognition
10 0.72253788 114 iccv-2013-Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution
11 0.71609271 51 iccv-2013-Anchored Neighborhood Regression for Fast Example-Based Super-Resolution
12 0.66688251 14 iccv-2013-A Generalized Iterated Shrinkage Algorithm for Non-convex Sparse Coding
13 0.65848887 258 iccv-2013-Low-Rank Sparse Coding for Image Classification
14 0.64100099 34 iccv-2013-Abnormal Event Detection at 150 FPS in MATLAB
15 0.62493527 96 iccv-2013-Coupled Dictionary and Feature Space Learning with Applications to Cross-Domain Image Synthesis and Recognition
16 0.6077956 244 iccv-2013-Learning View-Invariant Sparse Representations for Cross-View Action Recognition
17 0.53529817 401 iccv-2013-Stacked Predictive Sparse Coding for Classification of Distinct Regions in Tumor Histopathology
18 0.5159958 19 iccv-2013-A Learning-Based Approach to Reduce JPEG Artifacts in Image Matting
19 0.48514295 359 iccv-2013-Robust Object Tracking with Online Multi-lifespan Dictionary Learning
20 0.46962941 6 iccv-2013-A Convex Optimization Framework for Active Learning
topicId topicWeight
[(2, 0.093), (7, 0.015), (12, 0.012), (26, 0.107), (31, 0.047), (42, 0.124), (48, 0.022), (64, 0.029), (73, 0.036), (78, 0.014), (89, 0.138), (97, 0.22), (98, 0.016)]
simIndex simValue paperId paperTitle
1 0.9220618 373 iccv-2013-Saliency and Human Fixations: State-of-the-Art and Study of Comparison Metrics
Author: Nicolas Riche, Matthieu Duvinage, Matei Mancas, Bernard Gosselin, Thierry Dutoit
Abstract: Visual saliency has been an increasingly active research area in the last ten years with dozens of saliency models recently published. Nowadays, one of the big challenges in the field is to find a way to fairly evaluate all of these models. In this paper, on human eye fixations ,we compare the ranking of 12 state-of-the art saliency models using 12 similarity metrics. The comparison is done on Jian Li ’s database containing several hundreds of natural images. Based on Kendall concordance coefficient, it is shown that some of the metrics are strongly correlated leading to a redundancy in the performance metrics reported in the available benchmarks. On the other hand, other metrics provide a more diverse picture of models ’ overall performance. As a recommendation, three similarity metrics should be used to obtain a complete point of view of saliency model performance.
2 0.87108213 347 iccv-2013-Recursive Estimation of the Stein Center of SPD Matrices and Its Applications
Author: Hesamoddin Salehian, Guang Cheng, Baba C. Vemuri, Jeffrey Ho
Abstract: Symmetric positive-definite (SPD) matrices are ubiquitous in Computer Vision, Machine Learning and Medical Image Analysis. Finding the center/average of a population of such matrices is a common theme in many algorithms such as clustering, segmentation, principal geodesic analysis, etc. The center of a population of such matrices can be defined using a variety of distance/divergence measures as the minimizer of the sum of squared distances/divergences from the unknown center to the members of the population. It is well known that the computation of the Karcher mean for the space of SPD matrices which is a negativelycurved Riemannian manifold is computationally expensive. Recently, the LogDet divergence-based center was shown to be a computationally attractive alternative. However, the LogDet-based mean of more than two matrices can not be computed in closed form, which makes it computationally less attractive for large populations. In this paper we present a novel recursive estimator for center based on the Stein distance which is the square root of the LogDet di– vergence that is significantly faster than the batch mode computation of this center. The key theoretical contribution is a closed-form solution for the weighted Stein center of two SPD matrices, which is used in the recursive computation of the Stein center for a population of SPD matrices. Additionally, we show experimental evidence of the convergence of our recursive Stein center estimator to the batch mode Stein center. We present applications of our recursive estimator to K-means clustering and image indexing depicting significant time gains over corresponding algorithms that use the batch mode computations. For the latter application, we develop novel hashing functions using the Stein distance and apply it to publicly available data sets, and experimental results have shown favorable com– ∗This research was funded in part by the NIH grant NS066340 to BCV. †Corresponding author parisons to other competing methods.
3 0.8359099 227 iccv-2013-Large-Scale Image Annotation by Efficient and Robust Kernel Metric Learning
Author: Zheyun Feng, Rong Jin, Anil Jain
Abstract: One of the key challenges in search-based image annotation models is to define an appropriate similarity measure between images. Many kernel distance metric learning (KML) algorithms have been developed in order to capture the nonlinear relationships between visual features and semantics ofthe images. Onefundamental limitation in applying KML to image annotation is that it requires converting image annotations into binary constraints, leading to a significant information loss. In addition, most KML algorithms suffer from high computational cost due to the requirement that the learned matrix has to be positive semi-definitive (PSD). In this paper, we propose a robust kernel metric learning (RKML) algorithm based on the regression technique that is able to directly utilize image annotations. The proposed method is also computationally more efficient because PSD property is automatically ensured by regression. We provide the theoretical guarantee for the proposed algorithm, and verify its efficiency and effectiveness for image annotation by comparing it to state-of-the-art approaches for both distance metric learning and image annotation. ,
same-paper 4 0.83363605 20 iccv-2013-A Max-Margin Perspective on Sparse Representation-Based Classification
Author: Zhaowen Wang, Jianchao Yang, Nasser Nasrabadi, Thomas Huang
Abstract: Sparse Representation-based Classification (SRC) is a powerful tool in distinguishing signal categories which lie on different subspaces. Despite its wide application to visual recognition tasks, current understanding of SRC is solely based on a reconstructive perspective, which neither offers any guarantee on its classification performance nor provides any insight on how to design a discriminative dictionary for SRC. In this paper, we present a novel perspective towards SRC and interpret it as a margin classifier. The decision boundary and margin of SRC are analyzed in local regions where the support of sparse code is stable. Based on the derived margin, we propose a hinge loss function as the gauge for the classification performance of SRC. A stochastic gradient descent algorithm is implemented to maximize the margin of SRC and obtain more discriminative dictionaries. Experiments validate the effectiveness of the proposed approach in predicting classification performance and improving dictionary quality over reconstructive ones. Classification results competitive with other state-ofthe-art sparse coding methods are reported on several data sets.
5 0.82728398 412 iccv-2013-Synergistic Clustering of Image and Segment Descriptors for Unsupervised Scene Understanding
Author: Daniel M. Steinberg, Oscar Pizarro, Stefan B. Williams
Abstract: With the advent of cheap, high fidelity, digital imaging systems, the quantity and rate of generation of visual data can dramatically outpace a humans ability to label or annotate it. In these situations there is scope for the use of unsupervised approaches that can model these datasets and automatically summarise their content. To this end, we present a totally unsupervised, and annotation-less, model for scene understanding. This model can simultaneously cluster whole-image and segment descriptors, therebyforming an unsupervised model of scenes and objects. We show that this model outperforms other unsupervised models that can only cluster one source of information (image or segment) at once. We are able to compare unsupervised and supervised techniques using standard measures derived from confusion matrices and contingency tables. This shows that our unsupervised model is competitive with current supervised and weakly-supervised models for scene understanding on standard datasets. We also demonstrate our model operating on a dataset with more than 100,000 images col- lected by an autonomous underwater vehicle.
6 0.80090129 372 iccv-2013-Saliency Detection via Dense and Sparse Reconstruction
7 0.79150832 50 iccv-2013-Analysis of Scores, Datasets, and Models in Visual Saliency Prediction
8 0.77696109 425 iccv-2013-Tracking via Robust Multi-task Multi-view Joint Sparse Representation
9 0.77432299 369 iccv-2013-Saliency Detection: A Boolean Map Approach
10 0.76932347 91 iccv-2013-Contextual Hypergraph Modeling for Salient Object Detection
11 0.76313627 371 iccv-2013-Saliency Detection via Absorbing Markov Chain
12 0.75613815 71 iccv-2013-Category-Independent Object-Level Saliency Detection
13 0.74289274 180 iccv-2013-From Where and How to What We See
14 0.73293024 137 iccv-2013-Efficient Salient Region Detection with Soft Image Abstraction
15 0.72381663 396 iccv-2013-Space-Time Robust Representation for Action Recognition
16 0.72091293 257 iccv-2013-Log-Euclidean Kernels for Sparse Representation and Dictionary Learning
17 0.72023821 45 iccv-2013-Affine-Constrained Group Sparse Coding and Its Application to Image-Based Classifications
18 0.71880704 326 iccv-2013-Predicting Sufficient Annotation Strength for Interactive Foreground Segmentation
19 0.71584189 384 iccv-2013-Semi-supervised Robust Dictionary Learning via Efficient l-Norms Minimization
20 0.71571457 80 iccv-2013-Collaborative Active Learning of a Kernel Machine Ensemble for Recognition