iccv iccv2013 iccv2013-134 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Suraj Jain, Venu Madhav Govindu
Abstract: The higher-order clustering problem arises when data is drawn from multiple subspaces or when observations fit a higher-order parametric model. Most solutions to this problem either decompose higher-order similarity measures for use in spectral clustering or explicitly use low-rank matrix representations. In this paper we present our approach of Sparse Grassmann Clustering (SGC) that combines attributes of both categories. While we decompose the higherorder similarity tensor, we cluster data by directly finding a low dimensional representation without explicitly building a similarity matrix. By exploiting recent advances in online estimation on the Grassmann manifold (GROUSE) we develop an efficient and accurate algorithm that works with individual columns of similarities or partial observations thereof. Since it avoids the storage and decomposition of large similarity matrices, our method is efficient, scalable and has low memory requirements even for large-scale data. We demonstrate the performance of our SGC method on a variety of segmentation problems including planar seg- mentation of Kinect depth maps and motion segmentation of the Hopkins 155 dataset for which we achieve performance comparable to the state-of-the-art.
Reference: text
sentIndex sentText sentNum sentScore
1 Abstract The higher-order clustering problem arises when data is drawn from multiple subspaces or when observations fit a higher-order parametric model. [sent-3, score-0.42]
2 Most solutions to this problem either decompose higher-order similarity measures for use in spectral clustering or explicitly use low-rank matrix representations. [sent-4, score-0.465]
3 While we decompose the higherorder similarity tensor, we cluster data by directly finding a low dimensional representation without explicitly building a similarity matrix. [sent-6, score-0.341]
4 By exploiting recent advances in online estimation on the Grassmann manifold (GROUSE) we develop an efficient and accurate algorithm that works with individual columns of similarities or partial observations thereof. [sent-7, score-0.321]
5 Since it avoids the storage and decomposition of large similarity matrices, our method is efficient, scalable and has low memory requirements even for large-scale data. [sent-8, score-0.269]
6 Introduction In computer vision, the most common scenario requiring higher-order clustering arises when observation vectors are drawn from multiple subspaces of a given vector space or when data fits multi-dimensional parametric forms. [sent-11, score-0.347]
7 Evidently, such clustering cannot be achieved using conventional methods that measure distances between or similarities of point pairs. [sent-14, score-0.23]
8 Review of Literature Since the literature on clustering is very extensive, in the following we will limit ourselves to a brief review of methods that are of directly relevance to our approach for higher-order clustering. [sent-22, score-0.205]
9 For a recent survey of methods for subspace clustering the reader may refer to [16]. [sent-23, score-0.33]
10 All the methods we consider use spectral clustering, see [12] for a tutorial on spectral clustering and [17] for a discussion of related methods in computer vision. [sent-24, score-0.409]
11 [8] defines a similarity measure for an n-tuple of data points which leads to a multiway similarity tensor. [sent-27, score-0.384]
12 A similarity matrix is estimated by sampling columns from the flattened form of the similarity tensor and spectral clustering is applied. [sent-28, score-0.894]
13 While the spectral clustering approach works with a few eigen-vectors of the similarity matrix, our second category of methods explicitly model the low-rank nature of similarity representations. [sent-30, score-0.549]
14 In [11] (LRR), subspace clustering is achieved by finding the lowest-rank representation of the data matrix using itself as the dictionary. [sent-37, score-0.367]
15 vances in convex optimization and can achieve the desired clustering in the presence of outliers. [sent-42, score-0.233]
16 While the methods of [18, 11, 6] can effectively solve the clustering problem, they are computationally expensive. [sent-43, score-0.205]
17 Additionally, while using different approaches, these methods eventually build a similarity matrix for spectral clustering, implying that the memory and computational load for these methods can become very large. [sent-45, score-0.41]
18 All of these factors imply that despite the desirable property of robustness to outliers, the methods of [18, 11, 6] cannot solve the clustering problem for large datasets. [sent-46, score-0.231]
19 Instead of applying spectral clustering to a similarity matrix, we utilise its low-rank properties to directly solve for clustering without explicitly building a similarity matrix. [sent-52, score-0.78]
20 Higher-Order Grouping using Tensors In this Section, we summarise the higher-order tensor decomposition of similarity relationships as presented in [8, 3]. [sent-60, score-0.234]
21 The N N similarity matrix S uses the similarity between xi and xj, S(i,j) = e−φ2(2xσi2,xj) (1) where φ(. [sent-65, score-0.314]
22 The spectral clustering problem is solved by using the K leading eigen-vectors U = {u1, · · · , uK} of S or equivalently in terms of a nUorm =ali {zued, Laplacian f oofrm S. [sent-68, score-0.307]
23 For clustering data into circles, φ(xi, xj) will always be equal to zero since we can always find a circle that passes through any two points xi and xj . [sent-78, score-0.39]
24 Similarly, for fitting data to a d-dimensional linear subspace, we need n > d + 1 observations as a ddimensional linear subspace needs (d + 1) parameters to specify it. [sent-80, score-0.237]
25 Therefore, to cluster such data, we need to test whether an n-tuple of points belongs to the same cluster for × n ≥ d + 2. [sent-81, score-0.247]
26 t Iwno o points oatr a ,ti smime i blaurti thya so rto a f bfien idtyefi cnaendn footr b a set of n points at a time. [sent-84, score-0.202]
27 Evidently, the problem of clustering using the N N · · · ×v dNe similarity toebnlsemor oPf cclaunsnteorti nbge uasdindrge tssheed N by spect·r·a·l clustering developed fPor c similarity mddartersicseeds. [sent-98, score-0.652]
28 yIn s [e8c],the problem of higher-order grouping was solved by decomposing the similarity tensor P into a two-dimensional similarity gm tahteri sxi Si. [sent-99, score-0.351]
29 l Utilising tPhe i ftaoc ta ttwhaot dPim iesn an ndimensional super-symmetric tensor, [a8c]t s thhoawte Pd ti shat a conventional spectral clustering can be applied to the similarity matrix S = PPT where P is the flattened matrix form of 3355 0125 the tensor P, i. [sent-100, score-0.615]
30 It omfu sIt, a elasoc hb eo fn wotehdic hth cato rthrees probability coof a msent ooff points belonging to the same cluster is independent of their ordering, i. [sent-113, score-0.2]
31 C I ins [ a8] s, tbhsee tau otfhio nrt proposed cttoe randomly tsweeleecnt columns of P with uniform probability to construct the similarity matrix S. [sent-128, score-0.316]
32 We distinguish between pure and mixed columns as columns that draw I from a single cluster or multiple clusters respectively. [sent-130, score-0.46]
33 Ideally, we wleou clldu lteikre otor cmounlsttirpulect cSlu only from pure columns but a uniform sampling strategy fails in this regard, especially for large N. [sent-131, score-0.295]
34 76% of columns are pure, implying that uniform sampling would not work well. [sent-134, score-0.262]
35 SCC starts by uniformly sampling the columns and clustering the data. [sent-136, score-0.4]
36 3, the computational load of estimating the entries in an individual column of P can be significant. [sent-145, score-0.303]
37 We recall here that a single column of P is nothing but the entries in the similarity tensor P(i, I), where I the selected set of is t(hne m1)i adrisittyin tecnt isonrdic Pe(si ,aIn)d, iw hise trhee I i insde thxe o sfe tlhecet ecdol suemtn of. [sent-146, score-0.413]
38 These two similarity measures )d aifnfder only Ito) the extent that 1out of n data points are different, i. [sent-151, score-0.222]
39 Such repeated estimation on n-tuple data points with (n 1) common edasttiam points oisn wna-tsutpefluel aantda tphoei similarity measure can o ben efficiently approximated in the following manner. [sent-157, score-0.323]
40 − Since n ≥ (d + 2), the data points indexed by I will theSmisnecleve ns f≥it t (hde parametric amtaod poeil as (innd e1d) b≥y Id +w l1l tdhaetam points are shuef pficairaenmt ettor fcit m a dd-edlim ase n(snio −na 1l parametric or subspace model. [sent-158, score-0.431]
41 P T(ih,e eIre) as eth, ew leik cealnih eofofidc ioenf ttlhye aipn-dprivoixdiumala points xi belong t(oi, Ithe) parametric hmooodde ol fd tehfien iendby the index set I,i. [sent-165, score-0.209]
42 6 results in a significant reduction in computational load since for each column in P we compute a single θ and then score all other points in X with respect to θ. [sent-168, score-0.239]
43 For each column in P, the SCC method of [3] will select 4 points to form the set I estimate and tohfe similarity lfeocrt a 4ll pootihnetrs points by carrying o auntd dth ees cimiracltee fitting for n = 5 points, a total of N (n 1) = 496 tfiitmtinesg. [sent-171, score-0.464]
44 6 is an approximation to the true similarity measure, when we select a pure set of indices I, tshime resulting amsuordee,l wθh(eIn) wweil ls e bleec ctl aos peu rtoe sthete o ftr iuned imceodse Il,. [sent-176, score-0.23]
45 To summarise our argument here, since we wei clll bsete using an oite sruamtivmea sampling technique rtoe , r seifnincee the selected columns to be drawn from pure cluster models, Eqn. [sent-179, score-0.44]
46 6 accurately represents the underlying similarity measure while greatly reducing the computational expense involved when compared to the computational load of estimating individual entries of a column in P as defined in both [8] and [3]. [sent-180, score-0.424]
47 1, much of the recent work on higher-order grouping presents different methods that build a similarity matrix between data points and then use spectral clustering. [sent-183, score-0.389]
48 We recall that for a dataset of N points, spectral clustering requires an N N similarity mNa ptroixin tSs o spf ewchtriaclh c tlhuset eKri leading eigen-vectors are estimated. [sent-185, score-0.428]
49 It is evident that as the data size N increases, so does the requirement for storage of S as well as the computational load for both estimating the entries of S and its eigen-decomposition. [sent-186, score-0.228]
50 f MS,o rUe oisv arl,s oif a UK- =dim {uen,si·o·n·a ,lu u ba}sis a roef tthhee column space of matrix P, implying that we could solve for clustering using P instead of S. [sent-192, score-0.358]
51 For a vector space RN, the space of all linear subspaces of K dimensions forms a compact Riemannian manifold known as the Grassmann manifold which is denoted as G(N, K). [sent-203, score-0.26]
52 For our purposes, we note that since P is an N C matrix of effective rank equal to sKin, tehe P eigen-vectors CU m =atr x{u o1f , ·e ·f ·f , utiKve} tahnakt we aslee tok span a eK ei-gdeimn-evnescitoonrsal subspace o,f· ·R··N ,,u i. [sent-214, score-0.187]
53 Therefore, our clustering problem nisn equivalent Gto( identifying a point ,U o u∈r G cl(uNst, eKri)ng. [sent-217, score-0.205]
54 GROUSE was specifically designed to track a K-dimensional subspace of RN and uses matrix columns as input to incrementally update the subspace U on the Grassmann manifold G(N, K). [sent-224, score-0.578]
55 In a manner similar to recent advances in matrix completion, GROUSE can efficiently learn the basis U even when only some of the entries of the columns of P are available. [sent-232, score-0.297]
56 This is a great advantage for our problem since by using GROUSE, we need not compute all the entries of a column of P. [sent-233, score-0.211]
57 Given U ∈ G(N, K), the optimal fit for the N servGaivtioenn Uma ∈trix G (PN can b),e t dheef ionpetdim as F(U) =W∈mRinK×C ||UW − P||2 C ob(7) We can now adapt this cost function to incrementally update U as we observe the columns of P one at a time. [sent-235, score-0.229]
58 Wthee case where only some entries of pj are available, the fitting error F(U, j) and residual vector r can be suitably modified to be defined using only the available entries of pj . [sent-246, score-0.528]
59 1: while Not Converged do 2: for T trials do 3: Randomly select I from within cluster 4: RCoannsdtorumclty sparse pj by estimating t raenrdom entries of P(i, I) using Eqn. [sent-260, score-0.341]
60 10 6: end for 7: Classify points in X using K-means on rows of U 8: Update sampling to current clusters 9: end while 5. [sent-262, score-0.202]
61 Sparse Grassmann Clustering (SGC) We can now state our algorithm that carries out higherorder clustering by combining an iterative refinement ofcolumn sampling with an incremental Grassmann update of U. [sent-263, score-0.342]
62 As we do not need all the entries of a column of P to update U, we can sparsely estimate a few of the entries in a given column pj . [sent-264, score-0.59]
63 We initially use uniform random sampling to draw columns from P to build an initial clustering estimate. [sent-266, score-0.457]
64 Subsequently, during each iteration, we draw T columns according to the current cluster estimates. [sent-267, score-0.228]
65 For each column we estimate a few of the entries using the approximate similarity of Eqn. [sent-268, score-0.357]
66 After each iteration, we carry out the K-means clustering of the rows of the Grassmann estimate U ∈ G(N, K) and update the sampling afsosrm tahen nn eesxtti mitaetraeti Uon ∈to G b(eN b,aKse)d on t uhped catuerre thnet clusters. [sent-271, score-0.367]
67 Due to the efficiency of the GROUSE algorithm, in all of our experiments we have found that our SGC algorithm rapidly converges to the final clustering estimate. [sent-274, score-0.205]
68 We note that while the initial random sampling produces a rough clustering estimate, over subsequent iterations, this estimate is progressively refined by our algorithm thus yielding increasingly pure columns. [sent-275, score-0.367]
69 Properties of the SGC algorithm Handling multiple subspaces : Most methods that carry out estimation on the Grassmann manifold fit a single 3355 0158 subspace to the observations. [sent-278, score-0.349]
70 Unlike other methods that fit a single subspace to the observations, we map the observations into a similarity representation that measures the similarity or affinity relationships between data points. [sent-282, score-0.44]
71 Thus, although the raw data points belong to a union of K subspaces, independent of K, our SGC method maps the data points into a representation that lies in a single subspace U ∈ G(N, K). [sent-283, score-0.365]
72 on T htou sso, lwvee tahree multiway clustering problem. [sent-285, score-0.246]
73 × Memory and computational requirements : From the arguments of [2], we can see that for an N point dataset to be clustered into K subspaces, each iteration of our SGC algorithm takes O(TNK + ρTK2) flops where ρ is the number of entries estimated in each sampled column. [sent-286, score-0.217]
74 In terms of storage requirements, our approach is extremely light-weight as it does not need to store the full N N similarity mhta tarsix i. [sent-287, score-0.183]
75 Sminetcheod K can sNol,v aes f wore th shea clustering oraft very large problems which cannot be handled by other approaches based on spectral clustering. [sent-293, score-0.307]
76 It is germane to remark here that the notion of sparsity in our SGC algorithm applies to the fact that we only need a sparse number of entries used in individual columns and this should not be confused with the nature of sparsity in methods such as SSC [6]. [sent-294, score-0.363]
77 result of clustering data points according to the model of a circle. [sent-320, score-0.306]
78 As can be seen our method can correctly segment points into 5 circles which cannot be achieved by spectral clustering using Eqn. [sent-321, score-0.506]
79 2, we show the clustering results achieved on the well-known psychophysical model of the Kanizsa triangle. [sent-324, score-0.205]
80 Since we sample points to build a model and score all other points with respect to this model, in our SGC method we can simultaneously cluster data into different types of geometric models. [sent-325, score-0.305]
81 In this instance during one iteration of the for-loop in Algorithm 1 we sample columns according to both the circle and line model. [sent-326, score-0.177]
82 It should be noted that the correct classification of points into circles or lines is automatically achieved using our approach where higher-order similarity information can be integrated across multiple types of models. [sent-329, score-0.364]
83 2 also demonstrates the robustness of our method since, as far as points on circles are concerned, the raw depth map of size (480 × 640) 3355 0169 pixels while (c) show the segmentation of the depth map into planes using our SGC algorithm. [sent-333, score-0.321]
84 The input data contains two intersecting circles of 100 points each, interspersed with 100 outlier points, i. [sent-339, score-0.199]
85 In our SGC method, the measured similarities between pairs of points that belong to the same circle is high, leading to the correct classification of the two circles as independent clusters. [sent-344, score-0.311]
86 Consequently, all the randomly scattered outlier points are assigned to the third ×× cluster as these points cannot be classified as belonging to either of the two circle clusters. [sent-345, score-0.385]
87 =Ho 3w07e2ve0r0, since we neither store the individual sampled columns of P nor actually estimate all entries of each column, our segmentation algorithm has a small memory footprint as we only need to estimate U ∈ G(307200, K) which is equivalent etoe storing iKm depth maps i3n0 memory. [sent-357, score-0.503]
88 I wt hwicillh b ies noted that none of the methods that build the full similarity matrix for segmentation can handle such large problems. [sent-358, score-0.242]
89 use 4 points to fit a plane and score all other points with respect to this plane. [sent-361, score-0.232]
90 While N = 307200 is very large, since GROUSE can work with sparse columns, we estimate the values for ×× only 20% of the entries in each column and use T = 1000 column samples per iteration in Algorithm 1. [sent-362, score-0.352]
91 We remark that some points at the left boundary of the cupboard are incorrectly classified since the Kinect estimates at a depth discontinuity are unreliable. [sent-365, score-0.247]
92 Similarly direct attempts at spectral clustering will not work due to the obvious memory bottleneck of representing an N N similarity ms matreixm foorry large evnaeluceks o off r Nepr. [sent-368, score-0.482]
93 Under an affine camera model, all feature tracks of a rigidly moving object lie in an affine subspace of dimension d = 3 or linear subspace of d = 4. [sent-373, score-0.25]
94 For an individual point track X(:, i) where i ∈/ I estimate the projection we error as ei =X (:,Ii −) w UhIerUeIT i) ∈/ X I(:, w ie), wstihmeraet eU tIh eis p trhojee cfittiteodn subspace fo=r t (heI n-tuple of selected points indexed by I. [sent-376, score-0.318]
95 For each iteration of Algorithm 1, we use T = 1000 columns, but for each column we only estimate 10% of the entries of each column. [sent-383, score-0.236]
96 Except for the last column presenting the results of our SGC method, all other columns corresponding to different methods are taken from Table 1 of [6]. [sent-385, score-0.207]
97 Conclusion In this paper we have presented our Sparse Grassmann Clustering (SGC) method that can solve the higher-order clustering problem by utilising the geometric structure of the Grassmann manifold. [sent-391, score-0.265]
98 As it uses partial observations to incrementally update the clustering representation on the Grassmann manifold, our method is computationally efficient and has a very low memory requirement. [sent-392, score-0.373]
99 Our method is efficient and scalable and can solve large-scale clustering problems such as segmenting Kinect depth maps. [sent-393, score-0.272]
100 Statistical computations on grassmann and stiefel manifolds for image and video-based recognition. [sent-493, score-0.499]
wordName wordTfidf (topN-words)
[('sgc', 0.53), ('grassmann', 0.462), ('grouse', 0.271), ('clustering', 0.205), ('entries', 0.132), ('columns', 0.128), ('scc', 0.128), ('subspace', 0.125), ('similarity', 0.121), ('spectral', 0.102), ('points', 0.101), ('pj', 0.099), ('circles', 0.098), ('manifold', 0.092), ('tensor', 0.081), ('ssc', 0.079), ('column', 0.079), ('subspaces', 0.076), ('cluster', 0.073), ('pure', 0.07), ('sampling', 0.067), ('uw', 0.064), ('kanizsa', 0.062), ('prob', 0.061), ('load', 0.059), ('venu', 0.055), ('memory', 0.054), ('hopkins', 0.051), ('circle', 0.049), ('xs', 0.046), ('update', 0.044), ('noted', 0.044), ('observations', 0.043), ('ekri', 0.041), ('multiway', 0.041), ('suraj', 0.041), ('depth', 0.041), ('kinect', 0.041), ('segmentation', 0.04), ('rtoe', 0.039), ('belong', 0.038), ('matrix', 0.037), ('sparse', 0.037), ('implying', 0.037), ('storage', 0.037), ('fitting', 0.037), ('uma', 0.037), ('cupboard', 0.037), ('madhav', 0.037), ('stiefel', 0.037), ('xi', 0.035), ('xin', 0.035), ('parametric', 0.035), ('classified', 0.035), ('indexed', 0.034), ('lrsc', 0.034), ('ppt', 0.034), ('outliers', 0.034), ('clusters', 0.034), ('individual', 0.033), ('remark', 0.033), ('govindu', 0.032), ('tphe', 0.032), ('flattened', 0.032), ('ddimensional', 0.032), ('summarise', 0.032), ('drawn', 0.031), ('requirements', 0.031), ('uniform', 0.03), ('hei', 0.03), ('utilising', 0.03), ('balzano', 0.03), ('fo', 0.03), ('geometric', 0.03), ('planar', 0.03), ('fit', 0.03), ('completion', 0.029), ('evidently', 0.029), ('suitably', 0.029), ('indian', 0.029), ('curvature', 0.029), ('clustered', 0.028), ('presence', 0.028), ('grouping', 0.028), ('draw', 0.027), ('visit', 0.027), ('till', 0.027), ('incrementally', 0.027), ('pn', 0.027), ('higherorder', 0.026), ('belonging', 0.026), ('carry', 0.026), ('property', 0.026), ('arguments', 0.026), ('utilise', 0.026), ('scalable', 0.026), ('store', 0.025), ('estimate', 0.025), ('similarities', 0.025), ('rank', 0.025)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999768 134 iccv-2013-Efficient Higher-Order Clustering on the Grassmann Manifold
Author: Suraj Jain, Venu Madhav Govindu
Abstract: The higher-order clustering problem arises when data is drawn from multiple subspaces or when observations fit a higher-order parametric model. Most solutions to this problem either decompose higher-order similarity measures for use in spectral clustering or explicitly use low-rank matrix representations. In this paper we present our approach of Sparse Grassmann Clustering (SGC) that combines attributes of both categories. While we decompose the higherorder similarity tensor, we cluster data by directly finding a low dimensional representation without explicitly building a similarity matrix. By exploiting recent advances in online estimation on the Grassmann manifold (GROUSE) we develop an efficient and accurate algorithm that works with individual columns of similarities or partial observations thereof. Since it avoids the storage and decomposition of large similarity matrices, our method is efficient, scalable and has low memory requirements even for large-scale data. We demonstrate the performance of our SGC method on a variety of segmentation problems including planar seg- mentation of Kinect depth maps and motion segmentation of the Hopkins 155 dataset for which we achieve performance comparable to the state-of-the-art.
2 0.37866539 114 iccv-2013-Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution
Author: Mehrtash Harandi, Conrad Sanderson, Chunhua Shen, Brian Lovell
Abstract: Recent advances in computer vision and machine learning suggest that a wide range of problems can be addressed more appropriately by considering non-Euclidean geometry. In this paper we explore sparse dictionary learning over the space of linear subspaces, which form Riemannian structures known as Grassmann manifolds. To this end, we propose to embed Grassmann manifolds into the space of symmetric matrices by an isometric mapping, which enables us to devise a closed-form solution for updating a Grassmann dictionary, atom by atom. Furthermore, to handle non-linearity in data, we propose a kernelised version of the dictionary learning algorithm. Experiments on several classification tasks (face recognition, action recognition, dynamic texture classification) show that the proposed approach achieves considerable improvements in discrimination accuracy, in comparison to state-of-the-art methods such as kernelised Affine Hull Method and graphembedding Grassmann discriminant analysis.
3 0.22419168 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.21892276 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.18074638 435 iccv-2013-Unsupervised Domain Adaptation by Domain Invariant Projection
Author: Mahsa Baktashmotlagh, Mehrtash T. Harandi, Brian C. Lovell, Mathieu Salzmann
Abstract: Domain-invariant representations are key to addressing the domain shift problem where the training and test examples follow different distributions. Existing techniques that have attempted to match the distributions of the source and target domains typically compare these distributions in the original feature space. This space, however, may not be directly suitable for such a comparison, since some of the features may have been distorted by the domain shift, or may be domain specific. In this paper, we introduce a Domain Invariant Projection approach: An unsupervised domain adaptation method that overcomes this issue by extracting the information that is invariant across the source and target domains. More specifically, we learn a projection of the data to a low-dimensional latent space where the distance between the empirical distributions of the source and target examples is minimized. We demonstrate the effectiveness of our approach on the task of visual object recognition and show that it outperforms state-of-the-art methods on a standard domain adaptation benchmark dataset.
6 0.16399513 314 iccv-2013-Perspective Motion Segmentation via Collaborative Clustering
7 0.14593621 297 iccv-2013-Online Motion Segmentation Using Dynamic Label Propagation
8 0.13579088 182 iccv-2013-GOSUS: Grassmannian Online Subspace Updates with Structured-Sparsity
9 0.10386028 361 iccv-2013-Robust Trajectory Clustering for Motion Segmentation
10 0.099202588 94 iccv-2013-Correntropy Induced L2 Graph for Robust Subspace Clustering
11 0.09800677 122 iccv-2013-Distributed Low-Rank Subspace Segmentation
12 0.097362727 264 iccv-2013-Minimal Basis Facility Location for Subspace Segmentation
13 0.096483648 93 iccv-2013-Correlation Adaptive Subspace Segmentation by Trace Lasso
14 0.093428701 119 iccv-2013-Discriminant Tracking Using Tensor Representation with Semi-supervised Improvement
15 0.086436085 319 iccv-2013-Point-Based 3D Reconstruction of Thin Objects
16 0.082142986 438 iccv-2013-Unsupervised Visual Domain Adaptation Using Subspace Alignment
17 0.076539822 259 iccv-2013-Manifold Based Face Synthesis from Sparse Samples
18 0.076068051 162 iccv-2013-Fast Subspace Search via Grassmannian Based Hashing
20 0.068934202 362 iccv-2013-Robust Tucker Tensor Decomposition for Effective Image Representation
topicId topicWeight
[(0, 0.173), (1, -0.028), (2, -0.064), (3, -0.009), (4, -0.161), (5, 0.118), (6, -0.013), (7, 0.107), (8, 0.143), (9, 0.013), (10, 0.07), (11, -0.003), (12, -0.144), (13, 0.018), (14, -0.02), (15, -0.086), (16, -0.017), (17, -0.047), (18, 0.015), (19, -0.022), (20, 0.001), (21, 0.113), (22, 0.069), (23, -0.01), (24, -0.022), (25, -0.055), (26, -0.03), (27, 0.039), (28, -0.056), (29, 0.017), (30, -0.077), (31, -0.019), (32, -0.091), (33, 0.019), (34, 0.035), (35, 0.075), (36, 0.093), (37, 0.022), (38, -0.129), (39, -0.035), (40, -0.082), (41, 0.025), (42, 0.019), (43, -0.068), (44, -0.107), (45, 0.064), (46, -0.025), (47, 0.032), (48, -0.045), (49, -0.139)]
simIndex simValue paperId paperTitle
same-paper 1 0.92555189 134 iccv-2013-Efficient Higher-Order Clustering on the Grassmann Manifold
Author: Suraj Jain, Venu Madhav Govindu
Abstract: The higher-order clustering problem arises when data is drawn from multiple subspaces or when observations fit a higher-order parametric model. Most solutions to this problem either decompose higher-order similarity measures for use in spectral clustering or explicitly use low-rank matrix representations. In this paper we present our approach of Sparse Grassmann Clustering (SGC) that combines attributes of both categories. While we decompose the higherorder similarity tensor, we cluster data by directly finding a low dimensional representation without explicitly building a similarity matrix. By exploiting recent advances in online estimation on the Grassmann manifold (GROUSE) we develop an efficient and accurate algorithm that works with individual columns of similarities or partial observations thereof. Since it avoids the storage and decomposition of large similarity matrices, our method is efficient, scalable and has low memory requirements even for large-scale data. We demonstrate the performance of our SGC method on a variety of segmentation problems including planar seg- mentation of Kinect depth maps and motion segmentation of the Hopkins 155 dataset for which we achieve performance comparable to the state-of-the-art.
2 0.74052411 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.
3 0.73105258 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.6638245 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.
5 0.63749349 114 iccv-2013-Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution
Author: Mehrtash Harandi, Conrad Sanderson, Chunhua Shen, Brian Lovell
Abstract: Recent advances in computer vision and machine learning suggest that a wide range of problems can be addressed more appropriately by considering non-Euclidean geometry. In this paper we explore sparse dictionary learning over the space of linear subspaces, which form Riemannian structures known as Grassmann manifolds. To this end, we propose to embed Grassmann manifolds into the space of symmetric matrices by an isometric mapping, which enables us to devise a closed-form solution for updating a Grassmann dictionary, atom by atom. Furthermore, to handle non-linearity in data, we propose a kernelised version of the dictionary learning algorithm. Experiments on several classification tasks (face recognition, action recognition, dynamic texture classification) show that the proposed approach achieves considerable improvements in discrimination accuracy, in comparison to state-of-the-art methods such as kernelised Affine Hull Method and graphembedding Grassmann discriminant analysis.
6 0.61365569 94 iccv-2013-Correntropy Induced L2 Graph for Robust Subspace Clustering
7 0.6066072 122 iccv-2013-Distributed Low-Rank Subspace Segmentation
8 0.58940572 264 iccv-2013-Minimal Basis Facility Location for Subspace Segmentation
9 0.57071078 182 iccv-2013-GOSUS: Grassmannian Online Subspace Updates with Structured-Sparsity
10 0.56946415 314 iccv-2013-Perspective Motion Segmentation via Collaborative Clustering
11 0.52531785 259 iccv-2013-Manifold Based Face Synthesis from Sparse Samples
12 0.51417738 329 iccv-2013-Progressive Multigrid Eigensolvers for Multiscale Spectral Segmentation
13 0.51389343 347 iccv-2013-Recursive Estimation of the Stein Center of SPD Matrices and Its Applications
14 0.4889698 421 iccv-2013-Total Variation Regularization for Functions with Values in a Manifold
15 0.46630394 257 iccv-2013-Log-Euclidean Kernels for Sparse Representation and Dictionary Learning
16 0.46160895 100 iccv-2013-Curvature-Aware Regularization on Riemannian Submanifolds
17 0.4591178 362 iccv-2013-Robust Tucker Tensor Decomposition for Effective Image Representation
18 0.45879903 10 iccv-2013-A Framework for Shape Analysis via Hilbert Space Embedding
19 0.45661458 297 iccv-2013-Online Motion Segmentation Using Dynamic Label Propagation
20 0.448614 119 iccv-2013-Discriminant Tracking Using Tensor Representation with Semi-supervised Improvement
topicId topicWeight
[(2, 0.077), (7, 0.027), (12, 0.01), (13, 0.018), (14, 0.188), (26, 0.078), (31, 0.048), (34, 0.015), (35, 0.015), (40, 0.011), (42, 0.112), (48, 0.021), (49, 0.015), (64, 0.037), (73, 0.042), (89, 0.159), (95, 0.026)]
simIndex simValue paperId paperTitle
same-paper 1 0.82304823 134 iccv-2013-Efficient Higher-Order Clustering on the Grassmann Manifold
Author: Suraj Jain, Venu Madhav Govindu
Abstract: The higher-order clustering problem arises when data is drawn from multiple subspaces or when observations fit a higher-order parametric model. Most solutions to this problem either decompose higher-order similarity measures for use in spectral clustering or explicitly use low-rank matrix representations. In this paper we present our approach of Sparse Grassmann Clustering (SGC) that combines attributes of both categories. While we decompose the higherorder similarity tensor, we cluster data by directly finding a low dimensional representation without explicitly building a similarity matrix. By exploiting recent advances in online estimation on the Grassmann manifold (GROUSE) we develop an efficient and accurate algorithm that works with individual columns of similarities or partial observations thereof. Since it avoids the storage and decomposition of large similarity matrices, our method is efficient, scalable and has low memory requirements even for large-scale data. We demonstrate the performance of our SGC method on a variety of segmentation problems including planar seg- mentation of Kinect depth maps and motion segmentation of the Hopkins 155 dataset for which we achieve performance comparable to the state-of-the-art.
2 0.76323378 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.
3 0.76163667 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.
4 0.76111543 349 iccv-2013-Regionlets for Generic Object Detection
Author: Xiaoyu Wang, Ming Yang, Shenghuo Zhu, Yuanqing Lin
Abstract: Generic object detection is confronted by dealing with different degrees of variations in distinct object classes with tractable computations, which demands for descriptive and flexible object representations that are also efficient to evaluate for many locations. In view of this, we propose to model an object class by a cascaded boosting classifier which integrates various types of features from competing local regions, named as regionlets. A regionlet is a base feature extraction region defined proportionally to a detection window at an arbitrary resolution (i.e. size and aspect ratio). These regionlets are organized in small groups with stable relative positions to delineate fine-grained spatial layouts inside objects. Their features are aggregated to a one-dimensional feature within one group so as to tolerate deformations. Then we evaluate the object bounding box proposal in selective search from segmentation cues, limiting the evaluation locations to thousands. Our approach significantly outperforms the state-of-the-art on popular multi-class detection benchmark datasets with a single method, without any contexts. It achieves the detec- tion mean average precision of 41. 7% on the PASCAL VOC 2007 dataset and 39. 7% on the VOC 2010 for 20 object categories. It achieves 14. 7% mean average precision on the ImageNet dataset for 200 object categories, outperforming the latest deformable part-based model (DPM) by 4. 7%.
5 0.7595222 137 iccv-2013-Efficient Salient Region Detection with Soft Image Abstraction
Author: Ming-Ming Cheng, Jonathan Warrell, Wen-Yan Lin, Shuai Zheng, Vibhav Vineet, Nigel Crook
Abstract: Detecting visually salient regions in images is one of the fundamental problems in computer vision. We propose a novel method to decompose an image into large scale perceptually homogeneous elements for efficient salient region detection, using a soft image abstraction representation. By considering both appearance similarity and spatial distribution of image pixels, the proposed representation abstracts out unnecessary image details, allowing the assignment of comparable saliency values across similar regions, and producing perceptually accurate salient region detection. We evaluate our salient region detection approach on the largest publicly available dataset with pixel accurate annotations. The experimental results show that the proposed method outperforms 18 alternate methods, reducing the mean absolute error by 25.2% compared to the previous best result, while being computationally more efficient.
6 0.75842595 126 iccv-2013-Dynamic Label Propagation for Semi-supervised Multi-class Multi-label Classification
7 0.758295 80 iccv-2013-Collaborative Active Learning of a Kernel Machine Ensemble for Recognition
8 0.75824904 208 iccv-2013-Image Co-segmentation via Consistent Functional Maps
9 0.75792444 206 iccv-2013-Hybrid Deep Learning for Face Verification
10 0.75770187 376 iccv-2013-Scene Text Localization and Recognition with Oriented Stroke Detection
11 0.75724828 188 iccv-2013-Group Sparsity and Geometry Constrained Dictionary Learning for Action Recognition from Depth Maps
12 0.75715476 445 iccv-2013-Visual Reranking through Weakly Supervised Multi-graph Learning
13 0.75714028 327 iccv-2013-Predicting an Object Location Using a Global Image Representation
14 0.75706244 182 iccv-2013-GOSUS: Grassmannian Online Subspace Updates with Structured-Sparsity
15 0.75705099 150 iccv-2013-Exemplar Cut
16 0.75691247 197 iccv-2013-Hierarchical Joint Max-Margin Learning of Mid and Top Level Representations for Visual Recognition
18 0.75608546 95 iccv-2013-Cosegmentation and Cosketch by Unsupervised Learning
19 0.75536966 328 iccv-2013-Probabilistic Elastic Part Model for Unsupervised Face Detector Adaptation
20 0.7552247 245 iccv-2013-Learning a Dictionary of Shape Epitomes with Applications to Image Labeling