liu cgi06 talk

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