liu cgi06 talk

60 %
40 %
Information about liu cgi06 talk
Entertainment

Published on October 12, 2007

Author: GenX

Source: authorstream.com

Sub-sampling for Efficient Spectral Mesh Processing:  Sub-sampling for Efficient Spectral Mesh Processing Rong Liu, Varun Jain and Hao Zhang GrUVi lab, Simon Fraser University, Burnaby, Canada Roadmap:  Roadmap Background Nyström Method Kernel PCA (KPCA) Measuring Nyström Quality using KPCA Sampling Schemes Applications Conclusion and Future Work Roadmap:  Roadmap Background Nyström Method Kernel PCA (KPCA) Measuring Nyström Quality using KPCA Sampling Schemes Applications Conclusion and Future Work Spectral Applications:  Spectral Applications “affinity matrix” W, its eigen-decomposition Spectral Embedding:  Spectral Embedding i j W = EΛET n points, dimension 2 Bottlenecks:  Bottlenecks Computation of W, O(n2) . Apply sub-sampling to compute partial W. Eigenvalue decomposition of W, O(n3). Apply Nyström method to approximate the eigenvectors of W. How to sample to make Nyström work better ? Roadmap:  Roadmap Background Nyström Method Kernel PCA (KPCA) Measuring Nyström Quality using KPCA Sampling Schemes Applications Conclusion and Future Work Sub-sampling:  Sub-sampling Compute partial affinities n points Z = X U Y l sample points Nyström Method [Williams and Seeger, 2001]:  Nyström Method [Williams and Seeger, 2001] Approximate Eigenvectors W = , A = UΛUT Schur Complement:  Schur Complement Λ T = Schur Complement = C - BTA-1B Practically, SC is not useful to measure the quality of a sample set. SC = Roadmap:  Roadmap Background Nyström Method Kernel PCA (KPCA) Measuring Nyström Quality using KPCA Sampling Schemes Applications Conclusion and Future Work PCA and KPCA [Schölkopf et al, 1998]:  PCA and KPCA [Schölkopf et al, 1998] covariance matrix CX dimension 2 covariance matrix Cφ(X) X Training Set for KPCA:  Training Set for KPCA Nyström Method and KPCA:  Nyström Method and KPCA W = A = UΛUT U = U BTUΛ-1 Nyström KPCA w/ training set L = EΛET Roadmap:  Roadmap Background Nyström Method Kernel PCA (KPCA) Measuring Nyström Quality using KPCA Sampling Schemes Applications Conclusion and Future Work When Nyström Works Well ?:  When Nyström Works Well ? When the training set of KPCA works well ? Objective Function:  Objective Function minimize: maximize: evaluation: Compare Γ and SC:  Compare Γ and SC Given two sampling sets S1 and S2 Roadmap:  Roadmap Background Nyström Method Kernel PCA (KPCA) Measuring Nyström Quality using KPCA Sampling Schemes Applications Conclusion and Future Work How to sample: Greedy Scheme:  How to sample: Greedy Scheme Maximize: Greedy Sampling Scheme: A B Best candidate sampling scheme: To find the best 1% with probability 95%, we only need to search for the best one from a random subset of size 90 (log(0.01)/log(0.95)) regardless of the problem size. Properties of Γ:  Properties of Γ maximize 1T(A-11) A is symmetric. Diagonals of A are 1. Off-diagonals of A are in (0, 1). It can be shown that when A’s columns are canonical basis of the Euclidean space, the maxima is obtained. How to Sample: Farthest Point Scheme:  How to Sample: Farthest Point Scheme A = 1 1 1 … In order for A’s columns to be close to canonical basis, the off-diagonals should be close to zero. This means the distances between each pair of samples should be as large as possible, namely Samples are mutually farthest away. Farthest Sampling Scheme:  Farthest Sampling Scheme Roadmap:  Roadmap Background Nyström Method Kernel PCA (KPCA) Measuring Nyström Quality using KPCA Sampling Schemes Applications Conclusion and Future Work Mesh Correspondence:  Mesh Correspondence M(1) M(2) Slide26:  without sampling farthest point sampling random sampling (vertices sampled: 10, total vertices: 250) Slide27:  (vertices sampled: 10 total vertices: 2000) Slide28:  correspondence error against mesh size correspond a series a slimmed mesh with the original mesh a correspondence error at a certain vertex is defined as the geodesic distance between the matched point and the ground-truth matching point. Mesh Segmentation:  Mesh Segmentation M Slide30:  (b, d) obtained using farthest point sampling (a, c) obtained using random sampling faces sampled: 10 number in brackets: value of Γ Slide31:  w/o sampling, it takes 30s to handle a mesh with 4000 faces. 2.2 GHz Processor 1GB RAM Roadmap:  Roadmap Background Nyström Method Kernel PCA (KPCA) Measuring Nyström Quality using KPCA Sampling Schemes Applications Conclusion and Future Work Conclusion:  Conclusion Nyström approximation can be considered as using training data in Kernel PCA. Objective function Γ effectively quantifies the quality of a sample set. Γ leads to two sampling schemes: greedy scheme and farthest point scheme. Farthest point sampling scheme outperforms random sampling. Future Work:  Future Work Study the influence of kernel functions to Nyström method. Further improve the sampling scheme. Thank you ! Questions ?:  Thank you ! Questions ? Mesh Correspondence:  Mesh Correspondence Given any two models, M(1) and M(2), build the geodesic distance matrices D(1) and D(2). Dij encodes the geodesic distance between vertices i and j; D(1)  W(1) , D(2)  W(2) , using Gaussian kernel. Compute the eigenvalue decomposition of W(1) and W(2), and use the corresponding eigenvectors to define the spectral-embedded models M(1) and M(2). handle bending, uniform scaling and rigid body transformation. Compute the correspondence between M(1) and M(2). Mesh Segmentation:  Mesh Segmentation Given a model M, somehow define the distances between each pair of faces; the distances are stored in matrix D; D  W ; Compute the eigenvalue decomposition of W, and use the eigenvectors to spectral-embed the faces. Cluster (K-means) the embedded faces. Each cluster corresponds to a segment of the original model. Γ and Schur Complement:  Maximize: Given any two sampling sets S1 and S2 , S1 is superior to S2 iff Efficient to compute. Minimize: (schur complement) S1 is superior to S2 iff Very expensive to compute. Γ and Schur Complement

Add a comment

Related presentations

Related pages

Computer Graphics Laboratory - publications

~ publications ~ Journal Papers: Yuan-Ting Hu, ... Chun-Liang Liu, ... [People's Choice Best Talk Award] Liwei Chan, ...
Read more

Server Statistics - American Scientific Affiliation

World-Wide Web Access Statistics Generated by: WebStat 2.3.4 Last updated: Mon Aug 18 11:52:44 1997 Summary for Period: Jan 2 1996 to Dec 31 1996
Read more