iccv iccv2013 iccv2013-384 knowledge-graph by maker-knowledge-mining
Source: pdf
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.
Reference: text
sentIndex sentText sentNum sentScore
1 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. [sent-4, score-1.645]
2 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. [sent-7, score-1.82]
3 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. [sent-9, score-0.375]
4 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. [sent-17, score-1.493]
5 Challenges in Dictionary Learning to incorporate the supervision information in dictionary learning, without incurring additional parameters. [sent-20, score-0.917]
6 Moreover, the optimal dictionary size is automatically learned from the input data. [sent-21, score-0.963]
7 Although a variety of aspects of dictionary learning have been studied by these prior studies, there still remain three following challenges that hinder the further use of dictionary learning to solve practical problems. [sent-32, score-1.666]
8 Most, if not all, existing dictionary learning algorithms, e. [sent-34, score-0.746]
9 , [8, 10, 9], routinely used the squared ℓ2-norm as loss function to measure the reconstruction errors in their optimization objectives. [sent-36, score-0.213]
10 Same as other least square minimization based algorithms in data mining and machine learning, such dictionary learning methods are sensitive to noisy and outlier training samples. [sent-37, score-0.976]
11 Therefore, a dictionary robust against noisy and outlier samples is important 11 114455 for achieving good performance in contemporary real-world applications. [sent-39, score-0.894]
12 In traditional sparse learning, motivated by compressed sensing [6], dictionaries are always designed to be over-complete [5]. [sent-41, score-0.294]
13 Consequently, from information theory perspective, many basis vectors in the dictionary are redundant, which are detrimental to the subsequent sparse solver. [sent-43, score-0.923]
14 Moreover, existing methods usually pre-specify the dictionary size using either heuristics or prior knowledge before learning, whereas a principled way to determine the optimal dictionary size with respect to a specific input data set is seldom studied. [sent-44, score-1.637]
15 Thus, learning a compact and efficient dictionary with automatically determined optimal dictionary size is highly desirable in practice. [sent-45, score-1.574]
16 Traditional sparse learning [5] and dictionary learning [8] are designed for a set of signals without human annotations, therefore supervision information are not used even when it is available. [sent-47, score-1.054]
17 In order to make use of the prior labeling knowledge to improve the discriminativity of the learned dictionary, several recent studies [18, 10, 9] have made attempts to incorporate supervision information via additional regularization terms to the original dictionary learning objectives. [sent-48, score-1.178]
18 Therefore, taking advantage of supervision information contained in the training data without incurring extra parameters and keep the learning model compact is another important practical issue in designing an effective dictionary. [sent-50, score-0.434]
19 Our Contributions Among the above three challenges in dictionary learning, the first two are rarely addressed in the literature. [sent-53, score-0.716]
20 ∙ ∙ We address the dictionary robustness problem by using a new ℓ2,0+ -norm ltoiossn afruyn rcotbiouns,t wnehsisc phr oisb a generalization of traditional ℓ2,1-norm loss function [11, 4], yet more robust against noisy and outlier training samples. [sent-56, score-1.026]
21 Mathematically, instead of using the traditional ℓ2,1-norm regularization to impose structured sparsity, we use the ℓ2,0+ - ∙ ∙ ∙ norm regularization, which can more closely approximate ℓ2,0 constraint to better select dictionary bases. [sent-58, score-0.871]
22 By further developing the structured sparse regularizatBioyn f fuortrh deart ad adaptation, teh set supervision irnsefo rremgautliaorniz aofa classification task is gracefully incorporated without incurring additional parameters. [sent-59, score-0.345]
23 Learning a Semi-Supervised Robust Dictionary In this section, we gradually develop our objective to learn a semi-supervised robust dictionary, followed by an efficient algorithm to optimize the proposed objective with a rigorous proof of its convergence. [sent-65, score-0.315]
24 Finally, we describe the classification rules using the learned dictionaries. [sent-66, score-0.176]
25 lized to ℓ푟,푝-norm as ∥M∥푟,푝 = (∑푖(∑푗∣푚푖푗∣푟)푟푝)푝1, which is a valid norm because it ∣푣푖∣푝)1푝 1When 푝 ≥ 1, ∥v∥푝 = (∑푖푛=1 strictly defines a norm that satisWfiesh ethne 푝 푝th ≥ree 1 norm condi(tio∑ns, wh∣i푣le∣ it) )defines a quasinorm when 0 < 푝 < 1. [sent-81, score-0.266]
26 Sparse Coding via ℓ0+-norm Minimization Traditional sparse coding tasks deal with the problem to represent an input vector (e. [sent-88, score-0.193]
27 Concretely, given an input signal x ∈ ℝ푑 and a fixed dictionary consisting of 푟 pbautsis s gvneactloxr s D∈ ℝ= [d1, . [sent-91, score-0.778]
28 , d푟] ∈ ℝ푑×푟 (allowing 푟 > to make the dictionary over-complete), the task is to learn a new representation a ∈ ℝ푟 of the signal x by minimizing tnheew following objective ∈[1 ℝ4, 1]: 푑 퐽0 (a) = ∥a ∥0 , 푠. [sent-94, score-0.933]
29 To tackle this, in practice a is often learned by minimizing the following objective [14, 8, 10]: 퐽1 (a) = ∥x − Da ∥ 22 + 휆 ∥a ∥ 1 , (2) where 휆 > 0 is a tradeoff parameter to balance the relative importance of the reconstruction error and the sparsity of the learned coefficients. [sent-99, score-0.529]
30 When the input data satisfy the restricted isometry property [5, 14], the ℓ1-norm regularization in Eq. [sent-100, score-0.181]
31 As a result, the learned a is sparse with very few non-zero coefficients [5, 14]. [sent-103, score-0.222]
32 approximate ,퐽 ∥0a t∥han→ →퐽1 ∥ ain∥ terms of objective value, and could lead to a more sparse a given the same 휆. [sent-113, score-0.18]
33 (1–4), the dictionary D and its basis vectors in the learning objectives are assumed to be fixed. [sent-128, score-0.952]
34 Recently, the advances in sparse coding have shown that linearly decomposing a signal using a few atoms of a learned dictionary instead of a predefined one usually leads to state-ofthe-art performance for a number of practical computer vision applications [7, 13, 10, 15]. [sent-129, score-1.074]
35 Specifically, we can jointly learn the dictionary D and the sparse representations A from the input signals by minimizing the following objective [8, 13, 10]: 퐽D′푠(. [sent-130, score-1.071]
36 ,A∥)d =푗∥ ∥2X≤ − 1, D ∀A 1∥ ≤F2+ 푗 ≤ 휆∥ 푟A ,∥1,1, (5) where the constraints on the ℓ2-norms of the basis vectors are used to avoid degenerate solutions, because the reconstruction errors in the first term of Eq. [sent-132, score-0.2]
37 1 푟, atso 풞ac inhi tehvee s beqeutteelr sparsity, we learn the dictionary by minimizing the following objective: 퐽D(DD∈,풞A)= ∥X − DA∥F2+ 휆∥A∥푝푝,푝 . [sent-136, score-0.764]
38 (6) the objective 퐽D uses squared ℓ2-norm to measure reconstruction errors, therefore same as other least square optimization objectives in machine learn- ing and data mining, 퐽D is sensitive to noisy and outlier training samples. [sent-141, score-0.511]
39 Because dictionary learning is typically performed on data sets with large sample sizes where outlier samples are inevitable by nature, the learned dictionary could be seriously biased. [sent-142, score-1.77]
40 Therefore, robustness against outlier training samples needs to be taken into account in dictionary learning for its practical use. [sent-143, score-0.985]
41 However, when the number of noisy data samples is big or some 2 11 114477 outlier data samples are deviated very far from the true data distribution, a more robust loss function is desired. [sent-146, score-0.495]
42 (8) as ℓ2,0+ -norm loss function, which is more robust to outliers than both squared Frobenius norm loss function and ℓ2,1-norm loss function. [sent-162, score-0.394]
43 Learning Adaptive Dictionary Compared to the standard dictionary learning objective in Eq. [sent-165, score-0.833]
44 (8) has better sparsity and improved robustness against noisy and outlier training samples. [sent-167, score-0.297]
45 Therefore, selecting only the most relevant dictionary bases by pruning the redundant ones is of essential use to reduce the computational load for practical applications. [sent-172, score-0.804]
46 To this end, we consider to learn a compact dictionary that is adaptive to input data. [sent-173, score-0.872]
47 (8), all the basis vectors in the learned dictionary D are evenly treated and used in subsequent signal representations. [sent-176, score-1.007]
48 However, because the underlying high-level patterns of input signals are not known beforehand, the dictionary may contain redundancy. [sent-177, score-0.789]
49 Moreover, the dictionary size has to be specified before learning, whereas how to determine the optimal dictionary size in a principled way is rarely studied in literature. [sent-178, score-1.506]
50 As a result, the dictionary size is automatically determined by the learned A and irrelevant basis vectors are pruned. [sent-180, score-1.0]
51 As a result, ℓ2,푝-norm regularization could better approximate ℓ2,0-norm constraint to select dictionary bases, by which we minimize the following objective: 퐽RA-DD(∈D풞,A)= ? [sent-189, score-0.764]
52 Apparently, the dictionary size ∣풟X∈ ∈∣ i풟s learned fcroolmum tnhse. [sent-231, score-0.852]
53 Learning Semi-Supervised Dictionary Because incorporating the supervision information to learn a discriminative dictionary usually improves the performance of subsequent classifications [10, 9, 3, 18], we further develop the 퐽RA-D in Eq. [sent-239, score-0.91]
54 Different from existing works that incorporate label information by an additional term, we make use of the structural sparsity on the representation coefficient matrix A, such that no extra parameter is required and our model is easier to fine tune. [sent-241, score-0.244]
55 Given a classification task with 퐾 classes, besides the input data {x푖}푖푛=1, we also have their associated class labels. [sent-242, score-0.177]
56 For convenience, we write X푘 ∈ ℝ푑×푛푘 as the data matrix of the 푘-th class consisting ∈all of its 푛푘 training data points. [sent-245, score-0.178]
57 We also write X0 as the unlabeled data matrix, whose columns are the unlabeled data points. [sent-246, score-0.277]
58 Thus,A˜ is the sparse coefficient matrix˜ cor- denote respond˜ing to X˜, and ˜A푘 is the coefficient matrix fo˜r the data points belo˜nging ˜to the 푘-th class and A0 is that for unlabeled data. [sent-258, score-0.241]
59 Obviously, th∈e ℝ resulted D푘 is adaptive 풟to both input data and class supervision information of the 푘-th class. [sent-281, score-0.323]
60 Again, the dictionary size of D푘 is automatically determined by ∣풟푘 . [sent-282, score-0.76]
61 Because we learn the dictionaries from both the la∣b풟ele∣d. [sent-283, score-0.197]
62 Exploiting both unlabeled and labeled data in a unified framework without incurring extra parameters is an important advantage of the proposed method. [sent-286, score-0.236]
63 Classification Using Learned Dictionaries Given an unlabeled data point x, and the learned dictionaries D푘 (1 ≤ 푘 ≤ 퐾), we may compute the sparse representation o(f1 x ≤w 푘ith ≤ respect teo mthaey 푘 c-othm cpluatses, t ah(e푘 s) ,by solving the following problem: ∣ am(푘in) ? [sent-299, score-0.54]
64 Our goal is to cluster the face images, by which we examine the data representation capability of the learned dictionary when 푝 and 푞 in the proposed dictionary learning objectives vary in the range of 0. [sent-350, score-1.856]
65 In order to evaluate the data representation capability of the learned dictionaries, we conduct the experiment in an unsupervised way. [sent-354, score-0.334]
66 Specifically, we do not assign labels to the data points and conduct 퐾-means clustering on the learned data representations. [sent-355, score-0.338]
67 We learn dictionaries DX and the corresponding data representations A ryacAu0 . [sent-356, score-0.303]
68 Clustering accuracy using the learned dictionary by the proposed method vs. [sent-363, score-0.813]
69 We v{ary the value of 푝 and 푞, an}d report the 퐾-means clustering accuracy using the learned representations A. [sent-373, score-0.245]
70 , the dictionary learned with smaller 푝 and 푞 has better data representation capability, which clearly confirms the correctness to use ℓ2,0+ -norm loss function and regularization in dictionary learning. [sent-378, score-1.835]
71 We vary the size of the super-dictionary, denoted as ∣D ∣, and examine the learned sduaptae adaptive dictionary asisze ∣D, ∣d,en aontde dex as ∣iDneX th h∣,e al enadr report tahdea p퐾tiv-eme daicntsi clustering accuracy using th∣e, laenadrn reedrepresentations A. [sent-386, score-1.018]
72 We also report the 퐾-means clustering accuracy on the learned representations by the efficient sparse coding (ESC) method [8], a baseline sparse learning method, in which the dictionary size is specified as that of ∣D∣ . [sent-387, score-1.27]
73 We choose the ESC method for comparison, because it is an unsupervised dictionary learning method by directly solving its optimization objective, similar to our 퐽RA-D method but not robustifying the reconstruction errors. [sent-390, score-0.806]
74 퐾-means clustering accuracy using the sparse representations learned by the proposed 퐽RA-D method and ECS method on the three benchmark data sets. [sent-392, score-0.393]
75 A first glance at the results in Table 1 show that, the clustering accuracies using the sparse representations learned by our method are consistently better than those by ESC method, which validate the effectiveness of the proposed method in terms of data representation. [sent-408, score-0.393]
76 Upon a more careful examination on the results, we can see that, although the sizes of the pre-specified superdictionary D vary in a very large range, the sizes of the learned data adaptive dictionaries DX remain considerably stable. [sent-409, score-0.499]
77 First, when the size of the super-dictionary varies in a rather big range, the clustering performance on the learned representations of the data by our method does not fluctuate too much. [sent-411, score-0.339]
78 This confirms that the data representation power of the learned dictionary is not heavily dependent on the pre-specified size of the super-dictionary. [sent-412, score-0.993]
79 In other words, our method is able to automatically determine the optimal compact dictionary bases. [sent-413, score-0.789]
80 As can be seen, the sizes of the learned data adaptive dictionaries ∣DX ∣ are comparable to tlheaer ground atr autdha pcltiavsse n duicmtiboenarsr ioefs a ∣Dll the∣ athreree c odmaptaa rseabtsl. [sent-418, score-0.419]
81 However, the clustering accuracy on the data representations learned by the ESC method degrades very quickly when the dictionary 11 115500 size decreases. [sent-420, score-1.023]
82 This is because the representation power of its learned dictionary generally depends on the number of available basis vectors, which is also the reason why dictionaries are usually designed to be over-complete in traditional sparse learning. [sent-421, score-1.209]
83 , 50 in either the AT&T; data set or the BinAlpha data set, the representation capability of our method is also degraded. [sent-424, score-0.226]
84 This again confirms that real world data have certain inherent patterns and in sparse learning the dictionary size should be greater than this in- herent pattern number. [sent-425, score-1.014]
85 In summary, our method has demonstrated superior data representation capability through data adaptation, which is generally satisfactory in a variety of data conditions. [sent-426, score-0.281]
86 Improved Classification Performance Because making use of supervision information via enhanced data adaptation is an important advantage of the proposed method, we evaluate it in classification tasks. [sent-431, score-0.313]
87 We compare our methods against the following most recent dictionary learning methods. [sent-433, score-0.746]
88 For unsupervised dictionary learning methods, we compare to the two baseline methods including the K-SVD [1] method and the efficient sparse coding (ESC) method [8]. [sent-434, score-0.893]
89 For supervised dictionary methods, we compare to the discriminative K-SVD (D-K-SVD) method [9], the supervised dictionary learning (SDC) [10] method, and the group sparse coding (GSC) [3] method. [sent-435, score-1.577]
90 Once the sparse representations of the input data are learned by these methods, support vector machine (SVM) is used for classification. [sent-438, score-0.374]
91 The results in the top part are for classifications on the original data, while those in the bottom part are for classification on noisy data (20% training samples are incorrectly labeled to emulate noise). [sent-463, score-0.266]
92 This also confirms that our enhanced data adaptation can improve the classification performance by taking advantage of supervision information. [sent-542, score-0.365]
93 Conclusions In this paper, we presented a novel dictionary learning method to address two important seldom studied issues in conventional sparse learning, i. [sent-547, score-0.869]
94 Different from existing dictionary learning 11 1155 11 Table 3. [sent-550, score-0.746]
95 030 methods that use squared ℓ2 loss function, we employed a new ℓ2,0+ -norm loss function to measure the reconstruction errors in our objectives, such that outlier samples have less importance and our objectives are more robust. [sent-833, score-0.549]
96 In addition, instead of using additional terms to incorporate supervision information, we exploited such information by data adaptation via structural sparse regularization. [sent-834, score-0.354]
97 Due to the data adaptation nature, the dictionaries learned by our methods are adaptive to not only the input data but also their class labels, which improves the discriminativity of the learned dictionaries and makes them more suitable for classification tasks. [sent-836, score-0.986]
98 Because we use ℓ2,0+ regularization to adaptively select prominent basis vectors from a super-dictionary, the optimal dictionary size is automatically learned from the input data. [sent-837, score-1.154]
99 An efficient algorithm to solve the objective was described, together with the rigorous proof of its convergence. [sent-838, score-0.196]
100 Image denoising via sparse and redundant representations over learned dictionaries. [sent-880, score-0.314]
wordName wordTfidf (topN-words)
[('dictionary', 0.684), ('esc', 0.226), ('dictionaries', 0.165), ('learned', 0.129), ('supervision', 0.123), ('outlier', 0.121), ('gsc', 0.118), ('binalpha', 0.106), ('sdl', 0.106), ('dx', 0.105), ('da', 0.102), ('objectives', 0.095), ('sparse', 0.093), ('nie', 0.091), ('objective', 0.087), ('loss', 0.085), ('incurring', 0.082), ('capability', 0.082), ('superdictionary', 0.08), ('regularization', 0.08), ('sparsity', 0.076), ('hinder', 0.071), ('norm', 0.071), ('adaptive', 0.07), ('basis', 0.068), ('clustering', 0.065), ('unlabeled', 0.064), ('learning', 0.062), ('rigorous', 0.062), ('usps', 0.062), ('reconstruction', 0.06), ('cai', 0.055), ('adaptation', 0.055), ('data', 0.055), ('noisy', 0.054), ('coding', 0.054), ('quasinorm', 0.053), ('reuters', 0.053), ('confirms', 0.052), ('representations', 0.051), ('minimizing', 0.048), ('signal', 0.048), ('colorado', 0.047), ('proof', 0.047), ('classification', 0.047), ('robustness', 0.046), ('input', 0.046), ('trecvid', 0.044), ('vectors', 0.043), ('bases', 0.042), ('fine', 0.042), ('redundant', 0.041), ('fined', 0.041), ('discriminativity', 0.041), ('compact', 0.04), ('write', 0.039), ('emulate', 0.039), ('arlington', 0.039), ('squared', 0.039), ('size', 0.039), ('heng', 0.038), ('automatically', 0.037), ('practical', 0.037), ('classifications', 0.036), ('traditional', 0.036), ('samples', 0.035), ('extra', 0.035), ('subsequent', 0.035), ('aspects', 0.034), ('representation', 0.034), ('conduct', 0.034), ('weaknesses', 0.033), ('enhanced', 0.033), ('sydney', 0.032), ('obviously', 0.032), ('principled', 0.032), ('learn', 0.032), ('challenges', 0.032), ('battle', 0.032), ('correctness', 0.032), ('cand', 0.032), ('pages', 0.031), ('sapiro', 0.031), ('beforehand', 0.031), ('raw', 0.031), ('studies', 0.031), ('examine', 0.031), ('raina', 0.03), ('seldom', 0.03), ('signals', 0.03), ('texas', 0.03), ('errors', 0.029), ('easier', 0.029), ('outliers', 0.029), ('atoms', 0.029), ('patterns', 0.029), ('class', 0.029), ('incorporate', 0.028), ('tagging', 0.028), ('optimal', 0.028)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999928 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.
2 0.58321583 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.
3 0.42517713 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.39561161 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.38966376 197 iccv-2013-Hierarchical Joint Max-Margin Learning of Mid and Top Level Representations for Visual Recognition
Author: Hans Lobel, René Vidal, Alvaro Soto
Abstract: Currently, Bag-of-Visual-Words (BoVW) and part-based methods are the most popular approaches for visual recognition. In both cases, a mid-level representation is built on top of low-level image descriptors and top-level classifiers use this mid-level representation to achieve visual recognition. While in current part-based approaches, mid- and top-level representations are usually jointly trained, this is not the usual case for BoVW schemes. A main reason for this is the complex data association problem related to the usual large dictionary size needed by BoVW approaches. As a further observation, typical solutions based on BoVW and part-based representations are usually limited to extensions of binary classification schemes, a strategy that ignores relevant correlations among classes. In this work we propose a novel hierarchical approach to visual recognition based on a BoVW scheme that jointly learns suitable midand top-level representations. Furthermore, using a maxmargin learning framework, the proposed approach directly handles the multiclass case at both levels of abstraction. We test our proposed method using several popular bench- mark datasets. As our main result, we demonstrate that, by coupling learning of mid- and top-level representations, the proposed approach fosters sharing of discriminative visual words among target classes, being able to achieve state-ofthe-art recognition performance using far less visual words than previous approaches.
6 0.35119414 244 iccv-2013-Learning View-Invariant Sparse Representations for Cross-View Action Recognition
7 0.33251715 188 iccv-2013-Group Sparsity and Geometry Constrained Dictionary Learning for Action Recognition from Depth Maps
8 0.29345408 359 iccv-2013-Robust Object Tracking with Online Multi-lifespan Dictionary Learning
9 0.28980431 51 iccv-2013-Anchored Neighborhood Regression for Fast Example-Based Super-Resolution
10 0.27009684 20 iccv-2013-A Max-Margin Perspective on Sparse Representation-Based Classification
11 0.21519625 96 iccv-2013-Coupled Dictionary and Feature Space Learning with Applications to Cross-Domain Image Synthesis and Recognition
12 0.20959209 114 iccv-2013-Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution
13 0.2077198 45 iccv-2013-Affine-Constrained Group Sparse Coding and Its Application to Image-Based Classifications
14 0.19743609 398 iccv-2013-Sparse Variation Dictionary Learning for Face Recognition with a Single Training Sample per Person
15 0.17509261 245 iccv-2013-Learning a Dictionary of Shape Epitomes with Applications to Image Labeling
16 0.15127707 298 iccv-2013-Online Robust Non-negative Dictionary Learning for Visual Tracking
17 0.14581813 204 iccv-2013-Human Attribute Recognition by Rich Appearance Dictionary
18 0.12812781 34 iccv-2013-Abnormal Event Detection at 150 FPS in MATLAB
19 0.12705332 425 iccv-2013-Tracking via Robust Multi-task Multi-view Joint Sparse Representation
20 0.12531377 189 iccv-2013-HOGgles: Visualizing Object Detection Features
topicId topicWeight
[(0, 0.24), (1, 0.207), (2, -0.158), (3, -0.028), (4, -0.486), (5, -0.202), (6, -0.285), (7, -0.092), (8, -0.105), (9, -0.035), (10, 0.023), (11, 0.083), (12, 0.019), (13, 0.058), (14, -0.099), (15, 0.042), (16, -0.022), (17, 0.048), (18, 0.026), (19, 0.029), (20, 0.012), (21, -0.081), (22, 0.039), (23, 0.091), (24, 0.051), (25, -0.069), (26, -0.011), (27, -0.034), (28, 0.056), (29, -0.041), (30, 0.006), (31, 0.031), (32, -0.021), (33, -0.064), (34, -0.031), (35, -0.007), (36, 0.009), (37, 0.032), (38, -0.01), (39, 0.05), (40, -0.002), (41, -0.007), (42, -0.026), (43, -0.008), (44, 0.031), (45, -0.013), (46, 0.005), (47, -0.019), (48, -0.009), (49, 0.038)]
simIndex simValue paperId paperTitle
1 0.98003167 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.
same-paper 2 0.97234929 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.92525381 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.
4 0.85792357 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.85500282 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.
6 0.81732941 51 iccv-2013-Anchored Neighborhood Regression for Fast Example-Based Super-Resolution
7 0.80510849 197 iccv-2013-Hierarchical Joint Max-Margin Learning of Mid and Top Level Representations for Visual Recognition
8 0.7620436 114 iccv-2013-Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution
9 0.73414385 188 iccv-2013-Group Sparsity and Geometry Constrained Dictionary Learning for Action Recognition from Depth Maps
10 0.72548664 45 iccv-2013-Affine-Constrained Group Sparse Coding and Its Application to Image-Based Classifications
11 0.69013935 96 iccv-2013-Coupled Dictionary and Feature Space Learning with Applications to Cross-Domain Image Synthesis and Recognition
12 0.69000822 244 iccv-2013-Learning View-Invariant Sparse Representations for Cross-View Action Recognition
13 0.67653149 398 iccv-2013-Sparse Variation Dictionary Learning for Face Recognition with a Single Training Sample per Person
14 0.6037935 34 iccv-2013-Abnormal Event Detection at 150 FPS in MATLAB
15 0.5887664 359 iccv-2013-Robust Object Tracking with Online Multi-lifespan Dictionary Learning
16 0.58776385 19 iccv-2013-A Learning-Based Approach to Reduce JPEG Artifacts in Image Matting
17 0.55808681 258 iccv-2013-Low-Rank Sparse Coding for Image Classification
18 0.52726191 245 iccv-2013-Learning a Dictionary of Shape Epitomes with Applications to Image Labeling
19 0.52647227 14 iccv-2013-A Generalized Iterated Shrinkage Algorithm for Non-convex Sparse Coding
20 0.50133878 189 iccv-2013-HOGgles: Visualizing Object Detection Features
topicId topicWeight
[(2, 0.103), (7, 0.026), (12, 0.017), (26, 0.103), (27, 0.011), (31, 0.065), (42, 0.13), (48, 0.014), (64, 0.05), (73, 0.052), (78, 0.042), (89, 0.145), (90, 0.139), (98, 0.015)]
simIndex simValue paperId paperTitle
same-paper 1 0.87563932 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.
2 0.86741138 15 iccv-2013-A Generalized Low-Rank Appearance Model for Spatio-temporally Correlated Rain Streaks
Author: Yi-Lei Chen, Chiou-Ting Hsu
Abstract: In this paper, we propose a novel low-rank appearance model for removing rain streaks. Different from previous work, our method needs neither rain pixel detection nor time-consuming dictionary learning stage. Instead, as rain streaks usually reveal similar and repeated patterns on imaging scene, we propose and generalize a low-rank model from matrix to tensor structure in order to capture the spatio-temporally correlated rain streaks. With the appearance model, we thus remove rain streaks from image/video (and also other high-order image structure) in a unified way. Our experimental results demonstrate competitive (or even better) visual quality and efficient run-time in comparison with state of the art.
3 0.84970343 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.
4 0.84606427 360 iccv-2013-Robust Subspace Clustering via Half-Quadratic Minimization
Author: Yingya Zhang, Zhenan Sun, Ran He, Tieniu Tan
Abstract: Subspace clustering has important and wide applications in computer vision and pattern recognition. It is a challenging task to learn low-dimensional subspace structures due to the possible errors (e.g., noise and corruptions) existing in high-dimensional data. Recent subspace clustering methods usually assume a sparse representation of corrupted errors and correct the errors iteratively. However large corruptions in real-world applications can not be well addressed by these methods. A novel optimization model for robust subspace clustering is proposed in this paper. The objective function of our model mainly includes two parts. The first part aims to achieve a sparse representation of each high-dimensional data point with other data points. The second part aims to maximize the correntropy between a given data point and its low-dimensional representation with other points. Correntropy is a robust measure so that the influence of large corruptions on subspace clustering can be greatly suppressed. An extension of our method with explicit introduction of representation error terms into the model is also proposed. Half-quadratic minimization is provided as an efficient solution to the proposed robust subspace clustering formulations. Experimental results on Hopkins 155 dataset and Extended Yale Database B demonstrate that our method outperforms state-of-the-art subspace clustering methods.
5 0.84234107 140 iccv-2013-Elastic Net Constraints for Shape Matching
Author: Emanuele Rodolà, Andrea Torsello, Tatsuya Harada, Yasuo Kuniyoshi, Daniel Cremers
Abstract: We consider a parametrized relaxation of the widely adopted quadratic assignment problem (QAP) formulation for minimum distortion correspondence between deformable shapes. In order to control the accuracy/sparsity trade-off we introduce a weighting parameter on the combination of two existing relaxations, namely spectral and game-theoretic. This leads to the introduction of the elastic net penalty function into shape matching problems. In combination with an efficient algorithm to project onto the elastic net ball, we obtain an approach for deformable shape matching with controllable sparsity. Experiments on a standard benchmark confirm the effectiveness of the approach.
6 0.84173077 150 iccv-2013-Exemplar Cut
7 0.8413896 427 iccv-2013-Transfer Feature Learning with Joint Distribution Adaptation
8 0.83819008 80 iccv-2013-Collaborative Active Learning of a Kernel Machine Ensemble for Recognition
9 0.83679473 276 iccv-2013-Multi-attributed Dictionary Learning for Sparse Coding
10 0.83651686 277 iccv-2013-Multi-channel Correlation Filters
11 0.83620292 290 iccv-2013-New Graph Structured Sparsity Model for Multi-label Image Annotations
12 0.83562088 126 iccv-2013-Dynamic Label Propagation for Semi-supervised Multi-class Multi-label Classification
13 0.83525258 326 iccv-2013-Predicting Sufficient Annotation Strength for Interactive Foreground Segmentation
14 0.83407879 194 iccv-2013-Heterogeneous Image Features Integration via Multi-modal Semi-supervised Learning Model
15 0.83394861 137 iccv-2013-Efficient Salient Region Detection with Soft Image Abstraction
16 0.83177865 156 iccv-2013-Fast Direct Super-Resolution by Simple Functions
17 0.83139676 328 iccv-2013-Probabilistic Elastic Part Model for Unsupervised Face Detector Adaptation
18 0.83089626 44 iccv-2013-Adapting Classification Cascades to New Domains
19 0.83027625 43 iccv-2013-Active Visual Recognition with Expertise Estimation in Crowdsourcing
20 0.83026069 188 iccv-2013-Group Sparsity and Geometry Constrained Dictionary Learning for Action Recognition from Depth Maps