iccv iccv2013 iccv2013-182 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jia Xu, Vamsi K. Ithapu, Lopamudra Mukherjee, James M. Rehg, Vikas Singh
Abstract: We study the problem of online subspace learning in the context of sequential observations involving structured perturbations. In online subspace learning, the observations are an unknown mixture of two components presented to the model sequentially the main effect which pertains to the subspace and a residual/error term. If no additional requirement is imposed on the residual, it often corresponds to noise terms in the signal which were unaccounted for by the main effect. To remedy this, one may impose ‘structural’ contiguity, which has the intended effect of leveraging the secondary terms as a covariate that helps the estimation of the subspace itself, instead of merely serving as a noise residual. We show that the corresponding online estimation procedure can be written as an approximate optimization process on a Grassmannian. We propose an efficient numerical solution, GOSUS, Grassmannian Online Subspace Updates with Structured-sparsity, for this problem. GOSUS is expressive enough in modeling both homogeneous perturbations of the subspace and structural contiguities of outliers, and after certain manipulations, solvable — via an alternating direction method of multipliers (ADMM). We evaluate the empirical performance of this algorithm on two problems of interest: online background subtraction and online multiple face tracking, and demonstrate that it achieves competitive performance with the state-of-the-art in near real time.
Reference: text
sentIndex sentText sentNum sentScore
1 edu / ~ j i axu /pro j e ct s / go su s / Abstract We study the problem of online subspace learning in the context of sequential observations involving structured perturbations. [sent-6, score-0.523]
2 In online subspace learning, the observations are an unknown mixture of two components presented to the model sequentially the main effect which pertains to the subspace and a residual/error term. [sent-7, score-0.79]
3 To remedy this, one may impose ‘structural’ contiguity, which has the intended effect of leveraging the secondary terms as a covariate that helps the estimation of the subspace itself, instead of merely serving as a noise residual. [sent-9, score-0.5]
4 We show that the corresponding online estimation procedure can be written as an approximate optimization process on a Grassmannian. [sent-10, score-0.188]
5 GOSUS is expressive enough in modeling both homogeneous perturbations of the subspace and structural contiguities of outliers, and after certain manipulations, solvable — via an alternating direction method of multipliers (ADMM). [sent-12, score-0.383]
6 We evaluate the empirical performance of this algorithm on two problems of interest: online background subtraction and online multiple face tracking, and demonstrate that it achieves competitive performance with the state-of-the-art in near real time. [sent-13, score-0.454]
7 Within the last few years, new developments in matrix factorization [36, 3] and sparse modeling [25, 38] have led to significant renewed interest in this construct, and has provided a suite of new models and optimization schemes for many variants of the problem. [sent-16, score-0.135]
8 Here, observations are presented sequentially, in the form of an unknown mixture of the primary subspace(s) plus a residual component. [sent-18, score-0.085]
9 The standard strategy of modeling the foregoing online estimation question is to assume that the observation is an unknown mixture of two components. [sent-20, score-0.197]
10 The first relates to the subspace terms comprising one or multiple subspaces (and with or without regularization). [sent-21, score-0.347]
11 But fitting the signal to high fidelity will necessarily involve a large degree of freedom in the subspace term, and so the model allows for a small amount of compensatory residual error this corresponds to the second term contributing to the observed signal. [sent-23, score-0.498]
12 To encourage the residual quantity to be small, most proposals impose a sparsity penalty on its norm [24, 15]. [sent-24, score-0.222]
13 Therefore, the main technical concern, both in the “batch” and online settings, is to efficiently estimate the subspace and if possible provide probabilistic guarantees of correct recovery. [sent-25, score-0.443]
14 Within the last year, a particularly relevant application of online subspace learning is in the context of keeping updated estimates of background and foreground layers for video data1. [sent-26, score-0.611]
15 Here, one exploits concepts from matrix completion for subspace estimation, by drawing i. [sent-27, score-0.395]
16 samples from each incoming frame, and adjusting the current subspace parameters using only the sub-sampled data [15]. [sent-30, score-0.319]
17 The mass of the signal outside the support of the subspace may then be labeled as foreground. [sent-31, score-0.384]
18 This strategy works quite well when the background is completely static: essentially, the model has seen several hundred frames and has converged to a good estimate already. [sent-32, score-0.094]
19 , a swaying tree) and/or it is undergoing changes due to camera motion, zoom or illumination differences, it takes time — 1We will use this as a running example throughout the paper in an effort to make certain ideas concrete (we present results for another application in Section 5. [sent-35, score-0.11]
20 Here, the residual must then compensate for a less than ideal estimate of the main effect, which leads to salt-pepper isolated foreground regions, scattered over the image. [sent-42, score-0.22]
21 One reason for this unsatisfactory behavior is that the model does not enforce spatial homogeneity in the foreground region. [sent-43, score-0.121]
22 Imposing ‘structure’ on the secondary term, such as asking for contiguity, has the highly beneficial effect that the residual serves a more important role than merely accounting for the error/corruption. [sent-44, score-0.194]
23 From a statistical modeling perspective, the residual structure acts as a covariate that improves the estimate of the main effect (the background reconstruction via subspace modeling). [sent-45, score-0.533]
24 , structured sparsity operator) is different and better reflects the needs of that domain. [sent-50, score-0.173]
25 For instance, Robust subspace learning [11, 13] and Generalized Principal Component Analysis (GPCA) [34] take a hybrid geometric/statistical view of separating heterogeneous ‘mixed’ data drawn from one or more subspaces. [sent-65, score-0.319]
26 More recently, theory from compressive sensing (also, matrix completion) [9], and matrix factorization [3] have been successfully translated into new models and optimization schemes for this problem. [sent-67, score-0.139]
27 Separately, several authors express subspace estimation as a non-negative matrix factorization (NMF) [36, 6, 3] and give rigorous recovery guarantees. [sent-70, score-0.453]
28 While the literature devoted to the batch setting above is interesting, there is also brisk research activity in vision, especially in the last two years, focused on the online version of this problem. [sent-71, score-0.255]
29 This has led to a set of powerful online subspace learning methods [37, 4, 15], which are related to the above ideas as well as a parallel body of work in manifold learning [14, 32] they leverage the fact that the to-be-estimated signal lies on a Grassmannian [32]. [sent-72, score-0.537]
30 In particular, GROUSE [4] and GRASTA [15] (an online variant of RPCA) show how the subspace updates can be accurately maintained in real time by using sub-sampling ideas. [sent-73, score-0.487]
31 As introduced in Section 1, the data V is a composition of a main effect (or signal) B and a secondary term (or outlier) X. [sent-87, score-0.109]
32 This assumption is reasonable since the variation in signal across consecutive frames is small enough that it allows the few (d ? [sent-90, score-0.095]
33 Now, if v ∈ Rn is an observation and x ∈ Rn is the corresponding outlier vector (lies outside the support of the subspace given by U), then v = Uw + x, where w is the coefficients vector for the current observation. [sent-95, score-0.414]
34 This expression is under constrained when both the signal and the outlier are unknown. [sent-96, score-0.122]
35 That is, we may ask that the outlier be spatial coherent ensuring that isolated detections scattered across the image are strongly discouraged. [sent-98, score-0.121]
36 Structured sparsity For the background estimation example, the texture/color of the foreground objects (i. [sent-103, score-0.263]
37 , outliers) is homogeneous and so the outliers should be contiguous in an image. [sent-105, score-0.085]
38 For multiple face tracking (which we elaborate later), we need to track a set of faces in a given video where the subspace constitutes the faces themselves. [sent-106, score-0.569]
39 But the outliers created by occlusions are not pixel sparse, instead, constitute contiguous regions distributed at different face positions [19]. [sent-107, score-0.15]
40 We do not want such occlusions to cause large changes in the online updates and destroy the notion of a face subspace. [sent-109, score-0.294]
41 To formalize this prior on the outlier, we use structured (or group) sparsity [39, 16, 17]. [sent-111, score-0.173]
42 For one image frame, the groups may correspond to sets of sliding windows on the image, super-pixels generated via a pre-processing method (which encourages perceptually meaningful groups), or potential face sub-regions. [sent-112, score-0.133]
43 s in group i; (1) where Djij is the jth diagonal element of Di. [sent-116, score-0.089]
44 1 where μi gives the weight for group iand lis the number of such groups. [sent-122, score-0.089]
45 Our group sparsity function h(·) in (2) has a mixed norm structure. [sent-124, score-0.257]
46 The inner norm is either l2 or l∞ (we use l2) forcing pixels in the corresponding group to be similarly weighted, and the outer norm is l1 which encourages sparsity (i. [sent-125, score-0.27]
47 Given an input data V ∈ Rn×m, our model estimates the subspace matrix U, the coefficient vector w, and the outlier x, at a given time point (where v denotes the given current observation) by the following minimization, (λ is a positive regularization parameter) UTUm=iInd,w,x i? [sent-133, score-0.416]
48 In fact, several recent papers [26, 10, 29] are devoted to ideas for optimizing the structured sparsity norm objectives alone, and even by itself, it gets complicated due to overlapping groups. [sent-141, score-0.287]
49 Because the changes in U are not drastic from one frame to the other, local updates of the variables in (3) are sufficient in practice. [sent-144, score-0.138]
50 Given the current observation v and the tuple (wk , xk , {zik}, {yik}) at kth iteration, the step-by-step updating of the tuple at (k + 1)th iteration is: (w,x)-minimization: To minimize (5) with respect to (w,x) alone, keeping all the other parameters fixed, we have mwi,xn λ2? [sent-179, score-0.29]
51 zi-minimization: Minimizing a specific zi for group i, is independent of the other zj? [sent-198, score-0.23]
52 2 yi-updating: We can now update yi, ∀i ∈ {1, · the gradient direction by, yik+1 = yki + ρi(Dixk+1 − zik+1) (8) · · , l} along (9) The above analysis shows that the key update steps (summarized in Algorithm 1) within a ADMM procedure can all be performed efficiently. [sent-210, score-0.217]
53 Algorithm 1ADMM for solving (w∗ ,x∗ ) In: Subspace matrix: U∗, observation: v, initial: x0, zi0,y0i, group operator: Di, hyper-parameters: λ, μ, ρ Out: Subspace coefficient: w∗ , structured outliers: x∗ Procedure: 1: for k = 0 → K do 5: A ←? [sent-216, score-0.169]
54 Update of U with estimated (w∗ , x∗) The key idea to update U is to refine it from the estimation (w∗ , x∗) derived from the current observation v on the Grassmannian. [sent-231, score-0.122]
55 ) in (5) with respect to the components of U and the gradient are given by ∂∂LU= λ(Uw∗+ x∗− v)w∗T= sw∗T (10) where s = λ(Uw∗ + x∗ − v) denotes the residual vector. [sent-233, score-0.125]
56 70) in [2], the gradient on the Grassmannian can be computed by ∇L = (I −UUT)∂∂LU= (I −UUT)sw∗T= sw∗T (11) (11) is valid because the residual vector s is orthogonal to all of the columns of U. [sent-235, score-0.125]
57 and q = Following [2, 15], we update U with a gradient stepsize η in the direction ? [sent-243, score-0.206]
58 −∇L as U(η) = U + (cos(ση) − 1)UqqT − sin(ση)pqT (12) 33337792 where η is the stepsize to update the subspace U on the Grassmann manifold. [sent-246, score-0.485]
59 We incorporate an adaptive stepsize η using the updating scheme by [20] but in the experiments, a constant stepsize works well also. [sent-247, score-0.264]
60 The subspace updating procedure (12) preserves the column-wise orthogonality of U. [sent-249, score-0.378]
61 The optimal subspace is not computed fully, and is instead updated by analyzing successive observations. [sent-252, score-0.319]
62 Applications We apply GOSUS to the problem of foreground/background separation and multiple face tracking/identity management. [sent-256, score-0.095]
63 3/mean(v) ,∀i = 1, · · · , l and stepsize η was 0. [sent-272, score-0.117]
64 An initial estimate of the background subspace was set as a random orthonormal matrix n d (where d = 5, n is equal to three times # of pixels in each frame). [sent-275, score-0.423]
65 Together with a 3 3 grid group structure (patches) and hierarchical tree group structure [19], we also use a coarse-to-fine superpixel group construction. [sent-280, score-0.307]
66 Pixels belonging to each superpixel form a group which can overlap with others. [sent-281, score-0.129]
67 The group construction captures the boundary information of objects and our evaluations show this setting works well. [sent-283, score-0.089]
68 In particular, from Table 1 we see that GOSUS competes very favorably with GRASTA, both being online methods. [sent-288, score-0.124]
69 This is particularly clear in data with dynamic background (Fountain, Campus) and illumination changes (Light Switch, Lobby). [sent-289, score-0.095]
70 Also note that RPCA and RPMF are batch models, and GOSUS attains better performance than either in almost all categories, which supports the intuition that imposing structure (spatial homogeneity) on the outliers enables it to improve estimating the subspace. [sent-290, score-0.145]
71 GOSUS starts with a random subspace and finds the correct background after 200 frames. [sent-293, score-0.383]
72 At frame t0+ 645, a person comes in, sits for a while, and leaves on frame t0 882. [sent-294, score-0.163]
73 GOSUS successfully learn the new background (notice the pose of the red chair) as early as frame t0 930. [sent-295, score-0.127]
74 Figure 3 shows example detections for four different videos (one frame for each) of our algorithm and several baselines. [sent-298, score-0.101]
75 Observe that outputs of GOSUS contain very few isolated foreground regions, unlike GRASTA and the other batch models RPCA and RPMF, which do not regularize the secondary term at all. [sent-301, score-0.278]
76 This shows that the structured sparsity used in GOSUS, is not only acting as a noise removal filter (on salt-and-pepper like foreground detections) but also improves the estimation of the perturbed (dynamic/moving) subspace. [sent-303, score-0.279]
77 Further note that GOSUS outperforms both batch models (RPCA and RPMF), since the latter do not use any form of spatial contiguity. [sent-304, score-0.09]
78 Overall, both Table 1and Figure 3 indicate that GOSUS improves background subtraction in various categories, and offers substantial improvements when the background is dynamic. [sent-305, score-0.175]
79 As shown in Figure 4, our method is competitive with [26], except there are some grid artifacts from [26] due to their group construction. [sent-307, score-0.089]
80 This is significantly faster than the bi-level process used in [26], and several orders of magni- tude faster than speed reported in [29], a method devoted to optimizing structured sparsity norm. [sent-309, score-0.214]
81 The structured sparsity prior refers to each circular region as a group. [sent-325, score-0.173]
82 The tracking and identity management procedure is related to face recognition approaches reported in [33, 19]. [sent-327, score-0.198]
83 We consider U as a face subspace, with each column representing an ‘eigenface’ . [sent-328, score-0.095]
84 The observed face vector is described by a combination of eigenfaces using w and structured outliers x, created by occlusion/disguise. [sent-329, score-0.23]
85 False positives from the face detector are rejected by thresholding the norm of x. [sent-331, score-0.139]
86 When a new face is found, we add a new label/identity to our signature window. [sent-336, score-0.095]
87 Firstly observe that Amy in frame 151 and frame 1009, is tracked correctly even with significant changes in camera shot. [sent-340, score-0.157]
88 However, different tracks for the same person may be introduced if the person (Rajesh/Sheldon marked as 3/4) disappears in the video for a long time or has dramatic facial expressions. [sent-342, score-0.114]
89 Though our preliminary application on multiple face tracking shows promising results for real videos, the current pipeline is limited (in terms of efficiency) to the output from the face detector. [sent-343, score-0.225]
90 On these videos (720 1280), it takes about 2 seconds to detect all possible faces (for each frame), whereas GOSUS on its own can process all 6000 frames with all detected faces in ∼ 20 seconds. [sent-344, score-0.154]
91 Also note that the face detector can only detect frontal faces (the face of the male in frame 151 is missing), and can introduce a sizeable number of false positives for real world videos. [sent-345, score-0.296]
92 Conclusion The main contribution of this paper is an intuitive yet expressive model, GOSUS, which exploits a meaningful structured sparsity term to significantly improve the accuracy of online subspace updates. [sent-348, score-0.616]
93 Our solution is based on ADMM, where most key steps in the update procedure reduce to simple matrix operations yielding real-time performance for several interesting problems in video analysis. [sent-350, score-0.118]
94 Smoothing proximal gradient method for general structured sparse learning. [sent-429, score-0.12]
95 A closed form solution to robust subspace estimation and clustering. [sent-447, score-0.354]
96 Incremental gradient on the grassmannian for online foreground and background separation in subsampled video. [sent-459, score-0.436]
97 Learning hierarchical invariant spatio-temporal features for action recognition with independent subspace analysis. [sent-504, score-0.319]
98 Learning multiview face subspaces and facial pose estimation using independent component analysis. [sent-522, score-0.23]
99 Analyzing the subspace structure of related images: Concurrent segmentation of image sets. [sent-552, score-0.319]
100 Online subspace learning on grassmann manifold for moving object tracking in video. [sent-616, score-0.42]
wordName wordTfidf (topN-words)
[('gosus', 0.579), ('subspace', 0.319), ('rpmf', 0.201), ('rpca', 0.175), ('zik', 0.156), ('zi', 0.141), ('grassmannian', 0.137), ('online', 0.124), ('stepsize', 0.117), ('dix', 0.117), ('dixk', 0.112), ('grasta', 0.103), ('uw', 0.097), ('face', 0.095), ('sparsity', 0.093), ('batch', 0.09), ('admm', 0.089), ('group', 0.089), ('residual', 0.085), ('secondary', 0.081), ('structured', 0.08), ('tuple', 0.078), ('foreground', 0.071), ('yik', 0.067), ('grassmann', 0.066), ('signal', 0.065), ('background', 0.064), ('frame', 0.063), ('rik', 0.062), ('factorization', 0.059), ('outlier', 0.057), ('balzano', 0.056), ('outliers', 0.055), ('djij', 0.05), ('iik', 0.05), ('intermittent', 0.05), ('rrikik', 0.05), ('swaying', 0.05), ('wallflower', 0.05), ('yki', 0.05), ('homogeneity', 0.05), ('update', 0.049), ('subtraction', 0.047), ('contiguity', 0.045), ('lobby', 0.045), ('updates', 0.044), ('norm', 0.044), ('faces', 0.043), ('fountain', 0.041), ('wk', 0.041), ('devoted', 0.041), ('gradient', 0.04), ('superpixel', 0.04), ('matrix', 0.04), ('facial', 0.04), ('mairal', 0.039), ('management', 0.039), ('uut', 0.039), ('switch', 0.038), ('groups', 0.038), ('observation', 0.038), ('videos', 0.038), ('mukherjee', 0.037), ('covariate', 0.037), ('person', 0.037), ('completion', 0.036), ('isolated', 0.036), ('suite', 0.036), ('yi', 0.035), ('tracking', 0.035), ('estimation', 0.035), ('constitutes', 0.034), ('gpca', 0.034), ('principal', 0.034), ('alternating', 0.034), ('xk', 0.033), ('keeping', 0.033), ('campus', 0.032), ('component', 0.032), ('changes', 0.031), ('mixed', 0.031), ('frames', 0.03), ('hyperparameters', 0.03), ('cand', 0.03), ('homogeneous', 0.03), ('updating', 0.03), ('di', 0.029), ('tip', 0.029), ('ideas', 0.029), ('procedure', 0.029), ('sw', 0.029), ('nsf', 0.029), ('slic', 0.029), ('contributing', 0.029), ('auc', 0.029), ('tv', 0.028), ('effect', 0.028), ('scattered', 0.028), ('subspaces', 0.028), ('static', 0.028)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000002 182 iccv-2013-GOSUS: Grassmannian Online Subspace Updates with Structured-Sparsity
Author: Jia Xu, Vamsi K. Ithapu, Lopamudra Mukherjee, James M. Rehg, Vikas Singh
Abstract: We study the problem of online subspace learning in the context of sequential observations involving structured perturbations. In online subspace learning, the observations are an unknown mixture of two components presented to the model sequentially the main effect which pertains to the subspace and a residual/error term. If no additional requirement is imposed on the residual, it often corresponds to noise terms in the signal which were unaccounted for by the main effect. To remedy this, one may impose ‘structural’ contiguity, which has the intended effect of leveraging the secondary terms as a covariate that helps the estimation of the subspace itself, instead of merely serving as a noise residual. We show that the corresponding online estimation procedure can be written as an approximate optimization process on a Grassmannian. We propose an efficient numerical solution, GOSUS, Grassmannian Online Subspace Updates with Structured-sparsity, for this problem. GOSUS is expressive enough in modeling both homogeneous perturbations of the subspace and structural contiguities of outliers, and after certain manipulations, solvable — via an alternating direction method of multipliers (ADMM). We evaluate the empirical performance of this algorithm on two problems of interest: online background subtraction and online multiple face tracking, and demonstrate that it achieves competitive performance with the state-of-the-art in near real time.
2 0.22112918 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.
3 0.19280797 232 iccv-2013-Latent Space Sparse Subspace Clustering
Author: Vishal M. Patel, Hien Van Nguyen, René Vidal
Abstract: We propose a novel algorithm called Latent Space Sparse Subspace Clustering for simultaneous dimensionality reduction and clustering of data lying in a union of subspaces. Specifically, we describe a method that learns the projection of data and finds the sparse coefficients in the low-dimensional latent space. Cluster labels are then assigned by applying spectral clustering to a similarity matrix built from these sparse coefficients. An efficient optimization method is proposed and its non-linear extensions based on the kernel methods are presented. One of the main advantages of our method is that it is computationally efficient as the sparse coefficients are found in the low-dimensional latent space. Various experiments show that the proposed method performs better than the competitive state-of-theart subspace clustering methods.
4 0.17801972 310 iccv-2013-Partial Sum Minimization of Singular Values in RPCA for Low-Level Vision
Author: Tae-Hyun Oh, Hyeongwoo Kim, Yu-Wing Tai, Jean-Charles Bazin, In So Kweon
Abstract: Robust Principal Component Analysis (RPCA) via rank minimization is a powerful tool for recovering underlying low-rank structure of clean data corrupted with sparse noise/outliers. In many low-level vision problems, not only it is known that the underlying structure of clean data is low-rank, but the exact rank of clean data is also known. Yet, when applying conventional rank minimization for those problems, the objective function is formulated in a way that does not fully utilize a priori target rank information about the problems. This observation motivates us to investigate whether there is a better alternative solution when using rank minimization. In this paper, instead of minimizing the nuclear norm, we propose to minimize the partial sum of singular values. The proposed objective function implicitly encourages the target rank constraint in rank minimization. Our experimental analyses show that our approach performs better than conventional rank minimization when the number of samples is deficient, while the solutions obtained by the two approaches are almost identical when the number of samples is more than sufficient. We apply our approach to various low-level vision problems, e.g. high dynamic range imaging, photometric stereo and image alignment, and show that our results outperform those obtained by the conventional nuclear norm rank minimization method.
5 0.13952102 314 iccv-2013-Perspective Motion Segmentation via Collaborative Clustering
Author: Zhuwen Li, Jiaming Guo, Loong-Fah Cheong, Steven Zhiying Zhou
Abstract: This paper addresses real-world challenges in the motion segmentation problem, including perspective effects, missing data, and unknown number of motions. It first formulates the 3-D motion segmentation from two perspective views as a subspace clustering problem, utilizing the epipolar constraint of an image pair. It then combines the point correspondence information across multiple image frames via a collaborative clustering step, in which tight integration is achieved via a mixed norm optimization scheme. For model selection, wepropose an over-segment and merge approach, where the merging step is based on the property of the ?1-norm ofthe mutual sparse representation oftwo oversegmented groups. The resulting algorithm can deal with incomplete trajectories and perspective effects substantially better than state-of-the-art two-frame and multi-frame methods. Experiments on a 62-clip dataset show the significant superiority of the proposed idea in both segmentation accuracy and model selection.
6 0.13579088 134 iccv-2013-Efficient Higher-Order Clustering on the Grassmann Manifold
7 0.12453104 94 iccv-2013-Correntropy Induced L2 Graph for Robust Subspace Clustering
8 0.12071889 122 iccv-2013-Distributed Low-Rank Subspace Segmentation
9 0.11662757 392 iccv-2013-Similarity Metric Learning for Face Recognition
10 0.11626311 162 iccv-2013-Fast Subspace Search via Grassmannian Based Hashing
11 0.11603938 264 iccv-2013-Minimal Basis Facility Location for Subspace Segmentation
12 0.11109443 438 iccv-2013-Unsupervised Visual Domain Adaptation Using Subspace Alignment
13 0.10829769 297 iccv-2013-Online Motion Segmentation Using Dynamic Label Propagation
14 0.10342965 354 iccv-2013-Robust Dictionary Learning by Error Source Decomposition
15 0.1002858 434 iccv-2013-Unifying Nuclear Norm and Bilinear Factorization Approaches for Low-Rank Matrix Decomposition
16 0.099529654 26 iccv-2013-A Practical Transfer Learning Algorithm for Face Verification
17 0.095152661 93 iccv-2013-Correlation Adaptive Subspace Segmentation by Trace Lasso
18 0.094418727 226 iccv-2013-Joint Subspace Stabilization for Stereoscopic Video
19 0.093410648 114 iccv-2013-Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution
20 0.091543555 157 iccv-2013-Fast Face Detector Training Using Tailored Views
topicId topicWeight
[(0, 0.227), (1, -0.009), (2, -0.065), (3, -0.011), (4, -0.146), (5, 0.025), (6, 0.057), (7, 0.167), (8, 0.103), (9, 0.03), (10, 0.059), (11, -0.011), (12, -0.085), (13, 0.018), (14, -0.076), (15, -0.072), (16, -0.019), (17, -0.015), (18, -0.047), (19, -0.005), (20, -0.03), (21, 0.062), (22, -0.071), (23, -0.111), (24, -0.042), (25, -0.061), (26, -0.006), (27, -0.052), (28, -0.022), (29, -0.027), (30, 0.025), (31, -0.009), (32, -0.001), (33, 0.002), (34, 0.019), (35, -0.004), (36, 0.033), (37, 0.026), (38, -0.027), (39, -0.042), (40, -0.084), (41, 0.007), (42, -0.039), (43, 0.038), (44, 0.005), (45, 0.035), (46, -0.018), (47, -0.037), (48, 0.044), (49, 0.012)]
simIndex simValue paperId paperTitle
same-paper 1 0.95128351 182 iccv-2013-GOSUS: Grassmannian Online Subspace Updates with Structured-Sparsity
Author: Jia Xu, Vamsi K. Ithapu, Lopamudra Mukherjee, James M. Rehg, Vikas Singh
Abstract: We study the problem of online subspace learning in the context of sequential observations involving structured perturbations. In online subspace learning, the observations are an unknown mixture of two components presented to the model sequentially the main effect which pertains to the subspace and a residual/error term. If no additional requirement is imposed on the residual, it often corresponds to noise terms in the signal which were unaccounted for by the main effect. To remedy this, one may impose ‘structural’ contiguity, which has the intended effect of leveraging the secondary terms as a covariate that helps the estimation of the subspace itself, instead of merely serving as a noise residual. We show that the corresponding online estimation procedure can be written as an approximate optimization process on a Grassmannian. We propose an efficient numerical solution, GOSUS, Grassmannian Online Subspace Updates with Structured-sparsity, for this problem. GOSUS is expressive enough in modeling both homogeneous perturbations of the subspace and structural contiguities of outliers, and after certain manipulations, solvable — via an alternating direction method of multipliers (ADMM). We evaluate the empirical performance of this algorithm on two problems of interest: online background subtraction and online multiple face tracking, and demonstrate that it achieves competitive performance with the state-of-the-art in near real time.
2 0.87870198 94 iccv-2013-Correntropy Induced L2 Graph for Robust Subspace Clustering
Author: Canyi Lu, Jinhui Tang, Min Lin, Liang Lin, Shuicheng Yan, Zhouchen Lin
Abstract: In this paper, we study the robust subspace clustering problem, which aims to cluster the given possibly noisy data points into their underlying subspaces. A large pool of previous subspace clustering methods focus on the graph construction by different regularization of the representation coefficient. We instead focus on the robustness of the model to non-Gaussian noises. We propose a new robust clustering method by using the correntropy induced metric, which is robust for handling the non-Gaussian and impulsive noises. Also we further extend the method for handling the data with outlier rows/features. The multiplicative form of half-quadratic optimization is used to optimize the nonconvex correntropy objective function of the proposed models. Extensive experiments on face datasets well demonstrate that the proposed methods are more robust to corruptions and occlusions.
3 0.82062805 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.
4 0.81777662 122 iccv-2013-Distributed Low-Rank Subspace Segmentation
Author: Ameet Talwalkar, Lester Mackey, Yadong Mu, Shih-Fu Chang, Michael I. Jordan
Abstract: Vision problems ranging from image clustering to motion segmentation to semi-supervised learning can naturally be framed as subspace segmentation problems, in which one aims to recover multiple low-dimensional subspaces from noisy and corrupted input data. Low-Rank Representation (LRR), a convex formulation of the subspace segmentation problem, is provably and empirically accurate on small problems but does not scale to the massive sizes of modern vision datasets. Moreover, past work aimed at scaling up low-rank matrix factorization is not applicable to LRR given its non-decomposable constraints. In this work, we propose a novel divide-and-conquer algorithm for large-scale subspace segmentation that can cope with LRR ’s non-decomposable constraints and maintains LRR ’s strong recovery guarantees. This has immediate implications for the scalability of subspace segmentation, which we demonstrate on a benchmark face recognition dataset and in simulations. We then introduce novel applications of LRR-based subspace segmentation to large-scale semisupervised learning for multimedia event detection, concept detection, and image tagging. In each case, we obtain stateof-the-art results and order-of-magnitude speed ups.
5 0.81418985 93 iccv-2013-Correlation Adaptive Subspace Segmentation by Trace Lasso
Author: Canyi Lu, Jiashi Feng, Zhouchen Lin, Shuicheng Yan
Abstract: This paper studies the subspace segmentation problem. Given a set of data points drawn from a union of subspaces, the goal is to partition them into their underlying subspaces they were drawn from. The spectral clustering method is used as the framework. It requires to find an affinity matrix which is close to block diagonal, with nonzero entries corresponding to the data point pairs from the same subspace. In this work, we argue that both sparsity and the grouping effect are important for subspace segmentation. A sparse affinity matrix tends to be block diagonal, with less connections between data points from different subspaces. The grouping effect ensures that the highly corrected data which are usually from the same subspace can be grouped together. Sparse Subspace Clustering (SSC), by using ?1-minimization, encourages sparsity for data selection, but it lacks of the grouping effect. On the contrary, Low-RankRepresentation (LRR), by rank minimization, and Least Squares Regression (LSR), by ?2-regularization, exhibit strong grouping effect, but they are short in subset selection. Thus the obtained affinity matrix is usually very sparse by SSC, yet very dense by LRR and LSR. In this work, we propose the Correlation Adaptive Subspace Segmentation (CASS) method by using trace Lasso. CASS is a data correlation dependent method which simultaneously performs automatic data selection and groups correlated data together. It can be regarded as a method which adaptively balances SSC and LSR. Both theoretical and experimental results show the effectiveness of CASS.
6 0.81061041 232 iccv-2013-Latent Space Sparse Subspace Clustering
7 0.76709545 357 iccv-2013-Robust Matrix Factorization with Unknown Noise
8 0.74719936 134 iccv-2013-Efficient Higher-Order Clustering on the Grassmann Manifold
9 0.74299347 264 iccv-2013-Minimal Basis Facility Location for Subspace Segmentation
10 0.73633134 314 iccv-2013-Perspective Motion Segmentation via Collaborative Clustering
11 0.65896183 310 iccv-2013-Partial Sum Minimization of Singular Values in RPCA for Low-Level Vision
12 0.64599913 434 iccv-2013-Unifying Nuclear Norm and Bilinear Factorization Approaches for Low-Rank Matrix Decomposition
13 0.64252722 60 iccv-2013-Bayesian Robust Matrix Factorization for Image and Video Processing
14 0.60660911 26 iccv-2013-A Practical Transfer Learning Algorithm for Face Verification
15 0.60223579 167 iccv-2013-Finding Causal Interactions in Video Sequences
16 0.58383876 14 iccv-2013-A Generalized Iterated Shrinkage Algorithm for Non-convex Sparse Coding
17 0.58228183 55 iccv-2013-Automatic Kronecker Product Model Based Detection of Repeated Patterns in 2D Urban Images
18 0.57364202 329 iccv-2013-Progressive Multigrid Eigensolvers for Multiscale Spectral Segmentation
19 0.56632471 226 iccv-2013-Joint Subspace Stabilization for Stereoscopic Video
20 0.54701191 393 iccv-2013-Simultaneous Clustering and Tracklet Linking for Multi-face Tracking in Videos
topicId topicWeight
[(2, 0.057), (7, 0.024), (12, 0.015), (26, 0.085), (27, 0.016), (31, 0.055), (42, 0.142), (48, 0.018), (64, 0.058), (73, 0.034), (89, 0.139), (95, 0.229), (98, 0.034)]
simIndex simValue paperId paperTitle
1 0.89776993 25 iccv-2013-A Novel Earth Mover's Distance Methodology for Image Matching with Gaussian Mixture Models
Author: Peihua Li, Qilong Wang, Lei Zhang
Abstract: The similarity or distance measure between Gaussian mixture models (GMMs) plays a crucial role in contentbased image matching. Though the Earth Mover’s Distance (EMD) has shown its advantages in matching histogram features, its potentials in matching GMMs remain unclear and are not fully explored. To address this problem, we propose a novel EMD methodology for GMM matching. We ?rst present a sparse representation based EMD called SR-EMD by exploiting the sparse property of the underlying problem. SR-EMD is more ef?cient and robust than the conventional EMD. Second, we present two novel ground distances between component Gaussians based on the information geometry. The perspective from the Riemannian geometry distinguishes the proposed ground distances from the classical entropy- or divergence-based ones. Furthermore, motivated by the success of distance metric learning of vector data, we make the ?rst attempt to learn the EMD distance metrics between GMMs by using a simple yet effective supervised pair-wise based method. It can adapt the distance metrics between GMMs to speci?c classi?ca- tion tasks. The proposed method is evaluated on both simulated data and benchmark real databases and achieves very promising performance.
2 0.8436299 237 iccv-2013-Learning Graph Matching: Oriented to Category Modeling from Cluttered Scenes
Author: Quanshi Zhang, Xuan Song, Xiaowei Shao, Huijing Zhao, Ryosuke Shibasaki
Abstract: Although graph matching is a fundamental problem in pattern recognition, and has drawn broad interest from many fields, the problem of learning graph matching has not received much attention. In this paper, we redefine the learning ofgraph matching as a model learningproblem. In addition to conventional training of matching parameters, our approach modifies the graph structure and attributes to generate a graphical model. In this way, the model learning is oriented toward both matching and recognition performance, and can proceed in an unsupervised1 fashion. Experiments demonstrate that our approach outperforms conventional methods for learning graph matching.
same-paper 3 0.81779438 182 iccv-2013-GOSUS: Grassmannian Online Subspace Updates with Structured-Sparsity
Author: Jia Xu, Vamsi K. Ithapu, Lopamudra Mukherjee, James M. Rehg, Vikas Singh
Abstract: We study the problem of online subspace learning in the context of sequential observations involving structured perturbations. In online subspace learning, the observations are an unknown mixture of two components presented to the model sequentially the main effect which pertains to the subspace and a residual/error term. If no additional requirement is imposed on the residual, it often corresponds to noise terms in the signal which were unaccounted for by the main effect. To remedy this, one may impose ‘structural’ contiguity, which has the intended effect of leveraging the secondary terms as a covariate that helps the estimation of the subspace itself, instead of merely serving as a noise residual. We show that the corresponding online estimation procedure can be written as an approximate optimization process on a Grassmannian. We propose an efficient numerical solution, GOSUS, Grassmannian Online Subspace Updates with Structured-sparsity, for this problem. GOSUS is expressive enough in modeling both homogeneous perturbations of the subspace and structural contiguities of outliers, and after certain manipulations, solvable — via an alternating direction method of multipliers (ADMM). We evaluate the empirical performance of this algorithm on two problems of interest: online background subtraction and online multiple face tracking, and demonstrate that it achieves competitive performance with the state-of-the-art in near real time.
4 0.79099751 16 iccv-2013-A Generic Deformation Model for Dense Non-rigid Surface Registration: A Higher-Order MRF-Based Approach
Author: Yun Zeng, Chaohui Wang, Xianfeng Gu, Dimitris Samaras, Nikos Paragios
Abstract: We propose a novel approach for dense non-rigid 3D surface registration, which brings together Riemannian geometry and graphical models. To this end, we first introduce a generic deformation model, called Canonical Distortion Coefficients (CDCs), by characterizing the deformation of every point on a surface using the distortions along its two principle directions. This model subsumes the deformation groups commonly used in surface registration such as isometry and conformality, and is able to handle more complex deformations. We also derive its discrete counterpart which can be computed very efficiently in a closed form. Based on these, we introduce a higher-order Markov Random Field (MRF) model which seamlessly integrates our deformation model and a geometry/texture similarity metric. Then we jointly establish the optimal correspondences for all the points via maximum a posteriori (MAP) inference. Moreover, we develop a parallel optimization algorithm to efficiently perform the inference for the proposed higher-order MRF model. The resulting registration algorithm outperforms state-of-the-art methods in both dense non-rigid 3D surface registration and tracking.
5 0.76972216 263 iccv-2013-Measuring Flow Complexity in Videos
Author: Saad Ali
Abstract: In this paper a notion of flow complexity that measures the amount of interaction among objects is introduced and an approach to compute it directly from a video sequence is proposed. The approach employs particle trajectories as the input representation of motion and maps it into a ‘braid’ based representation. The mapping is based on the observation that 2D trajectories of particles take the form of a braid in space-time due to the intermingling among particles over time. As a result of this mapping, the problem of estimating the flow complexity from particle trajectories becomes the problem of estimating braid complexity, which in turn can be computed by measuring the topological entropy of a braid. For this purpose recently developed mathematical tools from braid theory are employed which allow rapid computation of topological entropy of braids. The approach is evaluated on a dataset consisting of open source videos depicting variations in terms of types of moving objects, scene layout, camera view angle, motion patterns, and object densities. The results show that the proposed approach is able to quantify the complexity of the flow, and at the same time provides useful insights about the sources of the complexity.
6 0.7590577 111 iccv-2013-Detecting Dynamic Objects with Multi-view Background Subtraction
7 0.73262268 257 iccv-2013-Log-Euclidean Kernels for Sparse Representation and Dictionary Learning
8 0.73115015 114 iccv-2013-Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution
9 0.72618622 79 iccv-2013-Coherent Object Detection with 3D Geometric Context from a Single Image
10 0.71796781 427 iccv-2013-Transfer Feature Learning with Joint Distribution Adaptation
11 0.70475441 44 iccv-2013-Adapting Classification Cascades to New Domains
12 0.70426136 259 iccv-2013-Manifold Based Face Synthesis from Sparse Samples
13 0.70305145 328 iccv-2013-Probabilistic Elastic Part Model for Unsupervised Face Detector Adaptation
14 0.70273507 161 iccv-2013-Fast Sparsity-Based Orthogonal Dictionary Learning for Image Restoration
15 0.70207804 330 iccv-2013-Proportion Priors for Image Sequence Segmentation
16 0.70175308 130 iccv-2013-Dynamic Structured Model Selection
17 0.70066273 180 iccv-2013-From Where and How to What We See
18 0.69960213 277 iccv-2013-Multi-channel Correlation Filters
19 0.69953775 80 iccv-2013-Collaborative Active Learning of a Kernel Machine Ensemble for Recognition
20 0.69696343 26 iccv-2013-A Practical Transfer Learning Algorithm for Face Verification