cvpr cvpr2013 cvpr2013-191 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Bo Jiang, Chris Ding, Bio Luo, Jin Tang
Abstract: Principal Component Analysis (PCA) is a widely used to learn a low-dimensional representation. In many applications, both vector data X and graph data W are available. Laplacian embedding is widely used for embedding graph data. Wepropose a graph-Laplacian PCA (gLPCA) to learn a low dimensional representation of X that incorporates graph structures encoded in W. This model has several advantages: (1) It is a data representation model. (2) It has a compact closed-form solution and can be efficiently computed. (3) It is capable to remove corruptions. Extensive experiments on 8 datasets show promising results on image reconstruction and significant improvement on clustering and classification.
Reference: text
sentIndex sentText sentNum sentScore
1 In many applications, both vector data X and graph data W are available. [sent-7, score-0.088]
2 Laplacian embedding is widely used for embedding graph data. [sent-8, score-0.448]
3 Wepropose a graph-Laplacian PCA (gLPCA) to learn a low dimensional representation of X that incorporates graph structures encoded in W. [sent-9, score-0.147]
4 This model has several advantages: (1) It is a data representation model. [sent-10, score-0.041]
5 Extensive experiments on 8 datasets show promising results on image reconstruction and significant improvement on clustering and classification. [sent-13, score-0.081]
6 Introduction In many computer vision applications, the dimensionality of data are usually very high. [sent-15, score-0.04]
7 An effective approach is dimensionality reduction: in low-dimensional space the class distribution becomes more apparent which signifi- cantly improves the machine learning results. [sent-16, score-0.085]
8 There are several dimension reduction methods suitable for different data types. [sent-17, score-0.04]
9 If the input data are vector data with feature vectors, Principal Component Analysis (PCA) and Linear Discriminative Analysis (LDA) are the two most widely used algorithms because of their relative simplicity and effectiveness. [sent-18, score-0.044]
10 These methods generally deal with the case where data mainly lie in a linear data manifold. [sent-19, score-0.078]
11 , which can deal with the case with data lying in nonlinear manifolds. [sent-21, score-0.07]
12 When the input data are graph data in the form of pairwise similarities (or distances) as the graph edge weights, Laplacian Embedding is a classical method[8, 1]. [sent-22, score-0.132]
13 These methods generally deal with the case where data mainly lie in a nonlinear data manifold. [sent-24, score-0.108]
14 Of course, given a vector data, we can use kernel to build similarity matrix and thus the graph data. [sent-25, score-0.065]
15 And from a graph data, we can produce low dimensional embedding that results in vector data. [sent-26, score-0.263]
16 Thus the distinction between vector data and graph is sometimes blurred. [sent-27, score-0.066]
17 In these approaches, the input data types are assumed to be same, either all graph data, or all vector data. [sent-30, score-0.066]
18 However, as mentioned above, one may transform data from one type to another type to match the requirement that data be of same type in these learning approaches. [sent-31, score-0.044]
19 In this paper, we assume the input data contains vector data X and graph data W. [sent-32, score-0.11]
20 Our task is to learn a low dimensional data representation of X that incorporates the cluster information encoded in graph data W. [sent-33, score-0.194]
21 We propose to use Laplacian embedding coordinates directly into the data representation for X. [sent-34, score-0.243]
22 The resulting graph-Laplacian PCA (gLPCA) model has three aspects: (1) data representation, (2) data embedding, (3) a closed form solution which can be efficiently computed. [sent-35, score-0.069]
23 Laplacian Embedding We start with a brief introduction of principal component analysis and Laplacian embedding. [sent-39, score-0.079]
24 Principal Component Analysis Let the input data matrix X = (x1, . [sent-42, score-0.043]
25 PCA [10, 3] finds the optimal low-dimensional (k-dim) subspace defined by the principal directions U = (u1, . [sent-47, score-0.071]
26 The projected data points in the new subspace are V RT = (v1, . [sent-51, score-0.038]
27 VTV = I (1) 333444999200 In addition, PCA relates closely to K-means clustering naturally [4]. [sent-59, score-0.081]
28 The principal components V are actually the continuous solution of the cluster membership indicators in the K-means clustering method. [sent-60, score-0.209]
29 This provides a motivation to relate PCA to Laplacian embedding whose primary purpose is clustering. [sent-61, score-0.218]
30 Manifold Embedding using Graph Laplacian PCA provides an embedding for the data lying on a linear manifold. [sent-64, score-0.242]
31 However, in many applications, data lie in a nonlinear manifold. [sent-65, score-0.068]
32 One popular method is to use graph Laplacian based embedding. [sent-66, score-0.044]
33 Given the pairwise similarity data matrix W ∈ Rn×n containing the edge weights on a graph wmiatthr n Wnod ∈es, R Laplacian embedding [8, 1] preserves the local geometrical relationships and maximizes the smoothness with respect to the intrinsic manifold of the data set in the low embedding space. [sent-67, score-0.556]
34 Let QT = (q1, q2, · · · qn) ∈ Rk×n be the embedding coordinates of the n da,t·a· points. [sent-68, score-0.202]
35 (2) provide an approximation solution for the Ration Cut spectral clustering[2], i. [sent-87, score-0.057]
36 , they can be seen as the relaxation solution of the cluster indicators (qi for data i) in the spectral clustering objective function. [sent-89, score-0.23]
37 This is similar to PCA being the spectral relaxation of K-means clustering [4]. [sent-90, score-0.135]
38 We wish to learn a low dimensional data representation of X that incorporates data cluster structures inherent in W, i. [sent-93, score-0.151]
39 , a representation regularized by the data manifold encoded in W. [sent-95, score-0.101]
40 Lowest 5 eigenvalues of Gβ for the AT&T; and MNIST datasets. [sent-124, score-0.04]
41 1 The optimal solution (U∗ , Q∗) of gLPCA are given by Q∗ = (v1, v2, · · · , vk) (4) U∗ = XQ∗ , (5) where v1, v2 , · · · , vk are the eigenvectors corresponding to the first k sm,a·l·le·s ,t eigenvalues of the matrix Gα = −XTX + αL, L ≡ D − W. [sent-128, score-0.177]
42 QTQ = I Thus, the optimal Q∗ can be obtained by computing eigenvectors corresponding to the first k smallest eigenvalues of the matrix Gα. [sent-145, score-0.13]
43 Properties of gLPCA We use the largest eigenvalue of kernel matrix XTX to normalize XTX. [sent-149, score-0.084]
44 Similar, we use ξn, the largest eigenvalue of Laplacian matrix L to normalize L. [sent-150, score-0.084]
45 (11) I Therefore, the solution of Q are given by the eigenvectors of Gβ : Gβ= (1 − β)(I −XλTnX) + βξLn (12) ≤ ≤ Clearly, parameter β should be in the range 0 β 1. [sent-161, score-0.094]
46 In this case, however, the data representation gLPCA is still valid because U = XQ is well-defined and xi ? [sent-165, score-0.041]
47 2 The matrix Gβ has the following properties: (1) Gβ is semi-positive definite; (2) e = (1 · · · 1)T is an eigenvector of Gβ: Gβe = (1 − β)e. [sent-168, score-0.081]
48 (13) (3) Any other eigenvector v is orthogonal to e. [sent-169, score-0.06]
49 First, because λn is the largest eigenvalue of XTX, thus I XTX/λn is s. [sent-171, score-0.063]
50 Thus e is an eigenvector of XTX with zero eigenvalue. [sent-181, score-0.06]
51 Also, it is well-known that e is an eigenvector of L with zero eigenvalue. [sent-182, score-0.06]
52 Third, for any symmetric real matrix Gβ, it non-degenerate eigenvectors are mutually orthogonal. [sent-184, score-0.09]
53 Since e is an eigenvector, thus all other eigenvectors are orthogonal to e. [sent-185, score-0.069]
54 2, we write the matrix Gβ as Gβ= (1 − β)(I −XλTnX) + β(ξLn+eneT) (14) Here, we added eeT/n in the Laplacian matrix part. [sent-188, score-0.042]
55 2, this does not change any eigenvectors and eigenvalues, except it shifts the trivial eigenvector e up to have eigenvalue 1, the largest eigenvalue of Gβ. [sent-190, score-0.237]
56 This is useful because it guarantees that the computed lowest k eigenvectors does not contain e. [sent-191, score-0.069]
57 Two examples of eigenvalues distributions are shown in Fig. [sent-192, score-0.04]
58 To illustrate the data representation aspect of gLPCA, we run gLPCA on the original and occluded images from AT&T; face dataset (more details given in the Experiments section). [sent-197, score-0.108]
59 In each panel, the top row contains 10 original images ofone person, 2nd - 5th rows contain reconstructed images (columns of UQT) at β = 0, 0. [sent-202, score-0.037]
60 Here we did two experiments, one using the original images, another using occluded images. [sent-206, score-0.041]
61 Only images of 2 persons (out of total 40 persons) in each experiment are shown due to space limitation. [sent-207, score-0.034]
62 These features indicate that the class structures are generally more apparent in gLPCA representation, and motivate us to use it for data clustering and semi-supervised learning tasks. [sent-210, score-0.188]
63 In general, residual errors remain close to PCA at small §β5, a. [sent-220, score-0.045]
64 n Idn go slightly higher arto rths ere Laplacian embedding (mLEal)l limit β = 1. [sent-221, score-0.248]
65 This is a bit surprising because in this LE limit, Q is entirely determined by Laplacian embedding and does not involve the data X (although the graph similarity W captures some relationship of the data). [sent-222, score-0.268]
66 We demonstrate the embedding aspect of gLPCA using 2D visualization. [sent-237, score-0.202]
67 96I85L 32490 of 40 persons) from AT&T; face dataset as the input, and then run PCA, Laplacian embedding and gLPCA, respectively(more details are given in the Experiments Section). [sent-245, score-0.228]
68 However, in gLPCA embedding, class structures are more apparent than in PCA or LE. [sent-248, score-0.067]
69 2 (20) The solution of this proximal operator is known [11] to be ei = max(1 −μ? [sent-303, score-0.05]
70 Experiments To validate the effectiveness of our models, we run gLPCA and RgLPCA on eight datasets, including AT&T;, Bin-alpha1, MNIST, USPS, COIL202 and three UCI datasets3 (ISOLET1, Libras Movement (LMove) and Mul- tiple Feature Data Set (MFeat)). [sent-311, score-0.042]
71 We do both clustering and semisupervised learning on these datasets. [sent-313, score-0.081]
72 To be complete, we also compare to some other embedding methods including the Locality Preserving Projections (LPP)[9] and Normalized Cut (Ncut)[13, 7]4 and original data. [sent-331, score-0.221]
73 First we perform clustering task on PCA, LE, LPP, Ncut and original data representations to evaluate them. [sent-332, score-0.122]
74 We use K-means and semi-NMF clustering [5] algorithms for this evaluation. [sent-333, score-0.081]
75 We use accuracy (ACC), normalized mutual information (NMI) and purity (PUR) as the measurements of the clustering qualities. [sent-334, score-0.107]
76 We run K-means with random initialization 50 times and use the average clustering results. [sent-335, score-0.107]
77 To see how gLPCA model performs at different regularization parameter β, we show in Figure 6 the K-means clustering accuracy on five datasets: AT&T;, MNIST, USPS, BinAlpha, and COIL20 datasets. [sent-336, score-0.081]
78 (2) gLPCA results are generally in-between PCA (at β = 0) results and Laplacian embedding (at β = 1) results. [sent-338, score-0.22]
79 The complete clustering results are shown in Table 3. [sent-342, score-0.081]
80 From Table 3, we observe that (1) both PCA and LE usually provide better clustering results than original data does, demonstrating the usefulness of PCA and LE. [sent-343, score-0.122]
81 (2) gLPCA consistently performs better than classic PCA, Laplacian embedding and other methods. [sent-344, score-0.202]
82 This is consistent with the 4Ncut uses eigenvectors Q of (D − W) with QTDQ = I orthonormalizNactiuotn u. [sent-345, score-0.069]
83 3 that class structures are more apparent ionb gLPCA representation. [sent-351, score-0.067]
84 Second, we perform classification on PCA, LE and original data representations using regression and KNN classification methods. [sent-352, score-0.073]
85 We perform clustering and classification tasks on these datasets and compare with several other models, including the original data, standard PCA and L21PCA[6]. [sent-361, score-0.116]
86 We use K-means and regression algorithms for clustering and classification, respectively. [sent-362, score-0.081]
87 For clustering, the accuracy (ACC), normalized mutual information (NMI) and purity (PUR) are used as the measurements of the clustering qualities. [sent-363, score-0.107]
88 We run K-means with random initialization 50 times and use the average clustering results. [sent-364, score-0.107]
89 (2) L21PCA can generally return better performance than the original data and standard PCA on all the datasets. [sent-369, score-0.059]
90 (3) RgLPCA generally performs better than other data representation models. [sent-371, score-0.059]
91 Summary Graph-Laplacian PCA incorporates PCA and Laplacian embedding (LE) simultaneously to provide a lowdimensional representation that incorporates graph structures. [sent-373, score-0.329]
92 The minor residual increase at the LE limit (β = 1) in Fig. [sent-377, score-0.073]
93 4 shows that the embedding Q ob333444999755 Table 4. [sent-378, score-0.202]
94 584201936750 tained in gLPCA retains the correct manifold information. [sent-386, score-0.043]
95 3 are the basic reasons why gLPCA performs better in clustering aen bda semi-supervised learning as compared ewri tinh PCA, LE, and other methods. [sent-389, score-0.081]
96 Laplacian eigenmaps and spectral technques for embedding and clustering. [sent-398, score-0.234]
97 A generalization of principal component analysis to the exponential family. [sent-411, score-0.079]
98 R1-PCA: Rotational invariant L1-norm principal component analysis for robust subspace factorization. [sent-431, score-0.095]
99 Spectral relaxation models and structure analysis for k-way graph clustering and bi-clustering. [sent-439, score-0.147]
100 Principal manifolds and nonlinear dimensionality reduction via tangent space alignment. [sent-487, score-0.084]
wordName wordTfidf (topN-words)
[('glpca', 0.818), ('pca', 0.216), ('uqt', 0.212), ('embedding', 0.202), ('laplacian', 0.164), ('rglpca', 0.14), ('qtq', 0.133), ('clustering', 0.081), ('xtx', 0.074), ('lpp', 0.071), ('eigenvectors', 0.069), ('ncut', 0.066), ('le', 0.065), ('qt', 0.062), ('eigenvector', 0.06), ('qtlq', 0.06), ('tnx', 0.06), ('principal', 0.055), ('mnist', 0.05), ('ding', 0.049), ('residual', 0.045), ('eigenvalue', 0.045), ('graph', 0.044), ('manifold', 0.043), ('alm', 0.042), ('usps', 0.042), ('eigenvalues', 0.04), ('binalpha', 0.04), ('trqt', 0.04), ('xq', 0.036), ('arlington', 0.035), ('persons', 0.034), ('tr', 0.034), ('nmi', 0.033), ('apparent', 0.032), ('spectral', 0.032), ('incorporates', 0.032), ('pur', 0.031), ('nonlinear', 0.03), ('proposition', 0.029), ('limit', 0.028), ('indicators', 0.027), ('locality', 0.027), ('qi', 0.027), ('purity', 0.026), ('cu', 0.026), ('run', 0.026), ('ei', 0.025), ('solution', 0.025), ('acc', 0.025), ('fixing', 0.024), ('component', 0.024), ('panel', 0.023), ('ln', 0.022), ('vk', 0.022), ('data', 0.022), ('relaxation', 0.022), ('updating', 0.022), ('occluded', 0.022), ('illustrative', 0.022), ('cluster', 0.021), ('matrix', 0.021), ('knn', 0.02), ('original', 0.019), ('representation', 0.019), ('reduction', 0.018), ('lagrange', 0.018), ('structures', 0.018), ('dimensionality', 0.018), ('lying', 0.018), ('tangent', 0.018), ('generally', 0.018), ('dar', 0.018), ('uvt', 0.018), ('anhui', 0.018), ('arto', 0.018), ('cantly', 0.018), ('chqding', 0.018), ('cian', 0.018), ('eyi', 0.018), ('hefei', 0.018), ('ofone', 0.018), ('qtdq', 0.018), ('wmahetrriex', 0.018), ('preserving', 0.018), ('largest', 0.018), ('dimensional', 0.017), ('class', 0.017), ('encoded', 0.017), ('primary', 0.016), ('vtv', 0.016), ('mqin', 0.016), ('corroborate', 0.016), ('coil', 0.016), ('tiple', 0.016), ('lie', 0.016), ('kn', 0.016), ('classification', 0.016), ('subspace', 0.016), ('science', 0.016)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999964 191 cvpr-2013-Graph-Laplacian PCA: Closed-Form Solution and Robustness
Author: Bo Jiang, Chris Ding, Bio Luo, Jin Tang
Abstract: Principal Component Analysis (PCA) is a widely used to learn a low-dimensional representation. In many applications, both vector data X and graph data W are available. Laplacian embedding is widely used for embedding graph data. Wepropose a graph-Laplacian PCA (gLPCA) to learn a low dimensional representation of X that incorporates graph structures encoded in W. This model has several advantages: (1) It is a data representation model. (2) It has a compact closed-form solution and can be efficiently computed. (3) It is capable to remove corruptions. Extensive experiments on 8 datasets show promising results on image reconstruction and significant improvement on clustering and classification.
2 0.093467608 223 cvpr-2013-Inductive Hashing on Manifolds
Author: Fumin Shen, Chunhua Shen, Qinfeng Shi, Anton van_den_Hengel, Zhenmin Tang
Abstract: Learning based hashing methods have attracted considerable attention due to their ability to greatly increase the scale at which existing algorithms may operate. Most of these methods are designed to generate binary codes that preserve the Euclidean distance in the original space. Manifold learning techniques, in contrast, are better able to model the intrinsic structure embedded in the original highdimensional data. The complexity of these models, and the problems with out-of-sample data, havepreviously rendered them unsuitable for application to large-scale embedding, however. In this work, we consider how to learn compact binary embeddings on their intrinsic manifolds. In order to address the above-mentioned difficulties, we describe an efficient, inductive solution to the out-of-sample data problem, and a process by which non-parametric manifold learning may be used as the basis of a hashing method. Our proposed approach thus allows the development of a range of new hashing techniques exploiting the flexibility of the wide variety of manifold learning approaches available. We particularly show that hashing on the basis of t-SNE [29] outperforms state-of-the-art hashing methods on large-scale benchmark datasets, and is very effective for image classification with very short code lengths.
3 0.090416342 405 cvpr-2013-Sparse Subspace Denoising for Image Manifolds
Author: Bo Wang, Zhuowen Tu
Abstract: With the increasing availability of high dimensional data and demand in sophisticated data analysis algorithms, manifold learning becomes a critical technique to perform dimensionality reduction, unraveling the intrinsic data structure. The real-world data however often come with noises and outliers; seldom, all the data live in a single linear subspace. Inspired by the recent advances in sparse subspace learning and diffusion-based approaches, we propose a new manifold denoising algorithm in which data neighborhoods are adaptively inferred via sparse subspace reconstruction; we then derive a new formulation to perform denoising to the original data. Experiments carried out on both toy and real applications demonstrate the effectiveness of our method; it is insensitive to parameter tuning and we show significant improvement over the competing algorithms.
4 0.087115347 270 cvpr-2013-Local Fisher Discriminant Analysis for Pedestrian Re-identification
Author: Sateesh Pedagadi, James Orwell, Sergio Velastin, Boghos Boghossian
Abstract: Metric learning methods, , forperson re-identification, estimate a scaling for distances in a vector space that is optimized for picking out observations of the same individual. This paper presents a novel approach to the pedestrian re-identification problem that uses metric learning to improve the state-of-the-art performance on standard public datasets. Very high dimensional features are extracted from the source color image. A first processing stage performs unsupervised PCA dimensionality reduction, constrained to maintain the redundancy in color-space representation. A second stage further reduces the dimensionality, using a Local Fisher Discriminant Analysis defined by a training set. A regularization step is introduced to avoid singular matrices during this stage. The experiments conducted on three publicly available datasets confirm that the proposed method outperforms the state-of-the-art performance, including all other known metric learning methods. Furthermore, the method is an effective way to process observations comprising multiple shots, and is non-iterative: the computation times are relatively modest. Finally, a novel statistic is derived to characterize the Match Characteris- tic: the normalized entropy reduction can be used to define the ’Proportion of Uncertainty Removed’ (PUR). This measure is invariant to test set size and provides an intuitive indication of performance.
5 0.079091303 379 cvpr-2013-Scalable Sparse Subspace Clustering
Author: Xi Peng, Lei Zhang, Zhang Yi
Abstract: In this paper, we address two problems in Sparse Subspace Clustering algorithm (SSC), i.e., scalability issue and out-of-sample problem. SSC constructs a sparse similarity graph for spectral clustering by using ?1-minimization based coefficients, has achieved state-of-the-art results for image clustering and motion segmentation. However, the time complexity of SSC is proportion to the cubic of problem size such that it is inefficient to apply SSC into large scale setting. Moreover, SSC does not handle with out-ofsample data that are not used to construct the similarity graph. For each new datum, SSC needs recalculating the cluster membership of the whole data set, which makes SSC is not competitive in fast online clustering. To address the problems, this paper proposes out-of-sample extension of SSC, named as Scalable Sparse Subspace Clustering (SSSC), which makes SSC feasible to cluster large scale data sets. The solution of SSSC adopts a ”sampling, clustering, coding, and classifying” strategy. Extensive experimental results on several popular data sets demonstrate the effectiveness and efficiency of our method comparing with the state-of-the-art algorithms.
6 0.074450992 241 cvpr-2013-Label-Embedding for Attribute-Based Classification
7 0.067037016 259 cvpr-2013-Learning a Manifold as an Atlas
8 0.066873305 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
9 0.060635488 93 cvpr-2013-Constraints as Features
10 0.054093946 306 cvpr-2013-Non-rigid Structure from Motion with Diffusion Maps Prior
11 0.053682312 109 cvpr-2013-Dense Non-rigid Point-Matching Using Random Projections
12 0.053288508 437 cvpr-2013-Towards Fast and Accurate Segmentation
13 0.050626069 316 cvpr-2013-Optical Flow Estimation Using Laplacian Mesh Energy
14 0.04889708 371 cvpr-2013-SCaLE: Supervised and Cascaded Laplacian Eigenmaps for Visual Object Recognition Based on Nearest Neighbors
15 0.048864577 180 cvpr-2013-Fully-Connected CRFs with Non-Parametric Pairwise Potential
16 0.048487615 267 cvpr-2013-Least Soft-Threshold Squares Tracking
17 0.048084874 135 cvpr-2013-Discriminative Subspace Clustering
18 0.046841279 442 cvpr-2013-Transfer Sparse Coding for Robust Image Representation
19 0.046582256 92 cvpr-2013-Constrained Clustering and Its Application to Face Clustering in Videos
20 0.04291271 237 cvpr-2013-Kernel Learning for Extrinsic Classification of Manifold Features
topicId topicWeight
[(0, 0.085), (1, -0.003), (2, -0.029), (3, 0.032), (4, 0.03), (5, -0.002), (6, -0.027), (7, -0.079), (8, -0.033), (9, -0.034), (10, 0.018), (11, -0.004), (12, -0.065), (13, -0.048), (14, -0.009), (15, 0.002), (16, -0.053), (17, -0.005), (18, -0.045), (19, 0.03), (20, 0.009), (21, 0.03), (22, 0.022), (23, -0.015), (24, 0.019), (25, -0.017), (26, 0.016), (27, -0.012), (28, -0.012), (29, -0.058), (30, 0.021), (31, 0.032), (32, 0.015), (33, -0.027), (34, -0.027), (35, 0.033), (36, -0.006), (37, 0.05), (38, -0.003), (39, -0.009), (40, -0.054), (41, -0.007), (42, -0.027), (43, 0.006), (44, 0.039), (45, -0.038), (46, -0.033), (47, 0.048), (48, -0.002), (49, -0.038)]
simIndex simValue paperId paperTitle
same-paper 1 0.9320063 191 cvpr-2013-Graph-Laplacian PCA: Closed-Form Solution and Robustness
Author: Bo Jiang, Chris Ding, Bio Luo, Jin Tang
Abstract: Principal Component Analysis (PCA) is a widely used to learn a low-dimensional representation. In many applications, both vector data X and graph data W are available. Laplacian embedding is widely used for embedding graph data. Wepropose a graph-Laplacian PCA (gLPCA) to learn a low dimensional representation of X that incorporates graph structures encoded in W. This model has several advantages: (1) It is a data representation model. (2) It has a compact closed-form solution and can be efficiently computed. (3) It is capable to remove corruptions. Extensive experiments on 8 datasets show promising results on image reconstruction and significant improvement on clustering and classification.
2 0.80488551 405 cvpr-2013-Sparse Subspace Denoising for Image Manifolds
Author: Bo Wang, Zhuowen Tu
Abstract: With the increasing availability of high dimensional data and demand in sophisticated data analysis algorithms, manifold learning becomes a critical technique to perform dimensionality reduction, unraveling the intrinsic data structure. The real-world data however often come with noises and outliers; seldom, all the data live in a single linear subspace. Inspired by the recent advances in sparse subspace learning and diffusion-based approaches, we propose a new manifold denoising algorithm in which data neighborhoods are adaptively inferred via sparse subspace reconstruction; we then derive a new formulation to perform denoising to the original data. Experiments carried out on both toy and real applications demonstrate the effectiveness of our method; it is insensitive to parameter tuning and we show significant improvement over the competing algorithms.
3 0.80125445 379 cvpr-2013-Scalable Sparse Subspace Clustering
Author: Xi Peng, Lei Zhang, Zhang Yi
Abstract: In this paper, we address two problems in Sparse Subspace Clustering algorithm (SSC), i.e., scalability issue and out-of-sample problem. SSC constructs a sparse similarity graph for spectral clustering by using ?1-minimization based coefficients, has achieved state-of-the-art results for image clustering and motion segmentation. However, the time complexity of SSC is proportion to the cubic of problem size such that it is inefficient to apply SSC into large scale setting. Moreover, SSC does not handle with out-ofsample data that are not used to construct the similarity graph. For each new datum, SSC needs recalculating the cluster membership of the whole data set, which makes SSC is not competitive in fast online clustering. To address the problems, this paper proposes out-of-sample extension of SSC, named as Scalable Sparse Subspace Clustering (SSSC), which makes SSC feasible to cluster large scale data sets. The solution of SSSC adopts a ”sampling, clustering, coding, and classifying” strategy. Extensive experimental results on several popular data sets demonstrate the effectiveness and efficiency of our method comparing with the state-of-the-art algorithms.
4 0.74912852 93 cvpr-2013-Constraints as Features
Author: Shmuel Asafi, Daniel Cohen-Or
Abstract: In this paper, we introduce a new approach to constrained clustering which treats the constraints as features. Our method augments the original feature space with additional dimensions, each of which derived from a given Cannot-link constraints. The specified Cannot-link pair gets extreme coordinates values, and the rest of the points get coordinate values that express their spatial influence from the specified constrained pair. After augmenting all the new features, a standard unconstrained clustering algorithm can be performed, like k-means or spectral clustering. We demonstrate the efficacy of our method for active semi-supervised learning applied to image segmentation and compare it to alternative methods. We also evaluate the performance of our method on the four most commonly evaluated datasets from the UCI machine learning repository.
5 0.71725619 109 cvpr-2013-Dense Non-rigid Point-Matching Using Random Projections
Author: Raffay Hamid, Dennis Decoste, Chih-Jen Lin
Abstract: We present a robust and efficient technique for matching dense sets of points undergoing non-rigid spatial transformations. Our main intuition is that the subset of points that can be matched with high confidence should be used to guide the matching procedure for the rest. We propose a novel algorithm that incorporates these high-confidence matches as a spatial prior to learn a discriminative subspace that simultaneously encodes both the feature similarity as well as their spatial arrangement. Conventional subspace learning usually requires spectral decomposition of the pair-wise distance matrix across the point-sets, which can become inefficient even for moderately sized problems. To this end, we propose the use of random projections for approximate subspace learning, which can provide significant time improvements at the cost of minimal precision loss. This efficiency gain allows us to iteratively find and remove high-confidence matches from the point sets, resulting in high recall. To show the effectiveness of our approach, we present a systematic set of experiments and results for the problem of dense non-rigid image-feature matching.
6 0.68646955 259 cvpr-2013-Learning a Manifold as an Atlas
7 0.68186432 135 cvpr-2013-Discriminative Subspace Clustering
8 0.65612733 215 cvpr-2013-Improved Image Set Classification via Joint Sparse Approximated Nearest Subspaces
9 0.63609463 9 cvpr-2013-A Fast Semidefinite Approach to Solving Binary Quadratic Problems
10 0.57867652 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
11 0.53391463 276 cvpr-2013-MKPLS: Manifold Kernel Partial Least Squares for Lipreading and Speaker Identification
12 0.52353626 178 cvpr-2013-From Local Similarity to Global Coding: An Application to Image Classification
13 0.51970172 126 cvpr-2013-Diffusion Processes for Retrieval Revisited
14 0.51383889 270 cvpr-2013-Local Fisher Discriminant Analysis for Pedestrian Re-identification
15 0.49872518 306 cvpr-2013-Non-rigid Structure from Motion with Diffusion Maps Prior
16 0.49754256 106 cvpr-2013-Deformable Graph Matching
17 0.49378723 91 cvpr-2013-Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds
18 0.49271894 223 cvpr-2013-Inductive Hashing on Manifolds
19 0.48958734 433 cvpr-2013-Top-Down Segmentation of Non-rigid Visual Objects Using Derivative-Based Search on Sparse Manifolds
20 0.48682034 250 cvpr-2013-Learning Cross-Domain Information Transfer for Location Recognition and Clustering
topicId topicWeight
[(10, 0.082), (16, 0.064), (26, 0.037), (28, 0.013), (33, 0.257), (67, 0.036), (69, 0.073), (76, 0.016), (77, 0.012), (87, 0.042), (90, 0.255)]
simIndex simValue paperId paperTitle
1 0.90210831 409 cvpr-2013-Spectral Modeling and Relighting of Reflective-Fluorescent Scenes
Author: Antony Lam, Imari Sato
Abstract: Hyperspectral reflectance data allows for highly accurate spectral relighting under arbitrary illumination, which is invaluable to applications ranging from archiving cultural e-heritage to consumer product design. Past methods for capturing the spectral reflectance of scenes has proven successful in relighting but they all share a common assumption. All the methods do not consider the effects of fluorescence despite fluorescence being found in many everyday objects. In this paper, we describe the very different ways that reflectance and fluorescence interact with illuminants and show the need to explicitly consider fluorescence in the relighting problem. We then propose a robust method based on well established theories of reflectance and fluorescence for imaging each of these components. Finally, we show that we can relight real scenes of reflective-fluorescent surfaces with much higher accuracy in comparison to only considering the reflective component.
same-paper 2 0.80251509 191 cvpr-2013-Graph-Laplacian PCA: Closed-Form Solution and Robustness
Author: Bo Jiang, Chris Ding, Bio Luo, Jin Tang
Abstract: Principal Component Analysis (PCA) is a widely used to learn a low-dimensional representation. In many applications, both vector data X and graph data W are available. Laplacian embedding is widely used for embedding graph data. Wepropose a graph-Laplacian PCA (gLPCA) to learn a low dimensional representation of X that incorporates graph structures encoded in W. This model has several advantages: (1) It is a data representation model. (2) It has a compact closed-form solution and can be efficiently computed. (3) It is capable to remove corruptions. Extensive experiments on 8 datasets show promising results on image reconstruction and significant improvement on clustering and classification.
3 0.801633 106 cvpr-2013-Deformable Graph Matching
Author: Feng Zhou, Fernando De_la_Torre
Abstract: Graph matching (GM) is a fundamental problem in computer science, and it has been successfully applied to many problems in computer vision. Although widely used, existing GM algorithms cannot incorporate global consistence among nodes, which is a natural constraint in computer vision problems. This paper proposes deformable graph matching (DGM), an extension of GM for matching graphs subject to global rigid and non-rigid geometric constraints. The key idea of this work is a new factorization of the pair-wise affinity matrix. This factorization decouples the affinity matrix into the local structure of each graph and the pair-wise affinity edges. Besides the ability to incorporate global geometric transformations, this factorization offers three more benefits. First, there is no need to compute the costly (in space and time) pair-wise affinity matrix. Second, it provides a unified view of many GM methods and extends the standard iterative closest point algorithm. Third, it allows to use the path-following optimization algorithm that leads to improved optimization strategies and matching performance. Experimental results on synthetic and real databases illustrate how DGM outperforms state-of-the-art algorithms for GM. The code is available at http : / / human s en s ing . c s . cmu .edu / fgm.
4 0.7566998 306 cvpr-2013-Non-rigid Structure from Motion with Diffusion Maps Prior
Author: Lili Tao, Bogdan J. Matuszewski
Abstract: In this paper, a novel approach based on a non-linear manifold learning technique is proposed to recover 3D nonrigid structures from 2D image sequences captured by a single camera. Most ofthe existing approaches assume that 3D shapes can be accurately modelled in a linear subspace. These techniques perform well when the deformations are relatively small or simple, but fail when more complex deformations need to be recovered. The non-linear deformations are often observed in highly flexible objects for which the use of the linear model is impractical. A specific type of shape variations might be governed by only a small number of parameters, therefore can be wellrepresented in a low dimensional manifold. We learn a nonlinear shape prior using diffusion maps method. The key contribution in this paper is the introduction of the shape prior that constrain the reconstructed shapes to lie in the learned manifold. The proposed methodology has been validated quantitatively and qualitatively on 2D points sequences projected from the 3D motion capture data and real 2D video sequences. The comparisons oftheproposed man- ifold based method against several state-of-the-art techniques are shown on different types of deformable objects.
Author: Jiangbo Lu, Hongsheng Yang, Dongbo Min, Minh N. Do
Abstract: Though many tasks in computer vision can be formulated elegantly as pixel-labeling problems, a typical challenge discouraging such a discrete formulation is often due to computational efficiency. Recent studies on fast cost volume filtering based on efficient edge-aware filters have provided a fast alternative to solve discrete labeling problems, with the complexity independent of the support window size. However, these methods still have to step through the entire cost volume exhaustively, which makes the solution speed scale linearly with the label space size. When the label space is huge, which is often the case for (subpixelaccurate) stereo and optical flow estimation, their computational complexity becomes quickly unacceptable. Developed to search approximate nearest neighbors rapidly, the PatchMatch method can significantly reduce the complexity dependency on the search space size. But, its pixel-wise randomized search and fragmented data access within the 3D cost volume seriously hinder the application of efficient cost slice filtering. This paper presents a generic and fast computational framework for general multi-labeling problems called PatchMatch Filter (PMF). For the very first time, we explore effective and efficient strategies to weave together these two fundamental techniques developed in isolation, i.e., PatchMatch-based randomized search and efficient edge-aware image filtering. By decompositing an image into compact superpixels, we also propose superpixelbased novel search strategies that generalize and improve the original PatchMatch method. Focusing on dense correspondence field estimation in this paper, we demonstrate PMF’s applications in stereo and optical flow. Our PMF methods achieve state-of-the-art correspondence accuracy but run much faster than other competing methods, often giving over 10-times speedup for large label space cases.
6 0.73801243 292 cvpr-2013-Multi-agent Event Detection: Localization and Role Assignment
7 0.73740667 61 cvpr-2013-Beyond Point Clouds: Scene Understanding by Reasoning Geometry and Physics
8 0.73690075 271 cvpr-2013-Locally Aligned Feature Transforms across Views
9 0.73652762 364 cvpr-2013-Robust Object Co-detection
10 0.73530155 130 cvpr-2013-Discriminative Color Descriptors
11 0.73523712 138 cvpr-2013-Efficient 2D-to-3D Correspondence Filtering for Scalable 3D Object Recognition
12 0.73500931 221 cvpr-2013-Incorporating Structural Alternatives and Sharing into Hierarchy for Multiclass Object Recognition and Detection
13 0.73454648 70 cvpr-2013-Bottom-Up Segmentation for Top-Down Detection
14 0.73420417 245 cvpr-2013-Layer Depth Denoising and Completion for Structured-Light RGB-D Cameras
15 0.73418677 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
16 0.73415393 330 cvpr-2013-Photometric Ambient Occlusion
17 0.73405248 403 cvpr-2013-Sparse Output Coding for Large-Scale Visual Recognition
18 0.73367667 424 cvpr-2013-Templateless Quasi-rigid Shape Modeling with Implicit Loop-Closure
19 0.7334044 384 cvpr-2013-Segment-Tree Based Cost Aggregation for Stereo Matching
20 0.7332086 317 cvpr-2013-Optimal Geometric Fitting under the Truncated L2-Norm