“Spectral sampling of manifolds”
Conference:
Type(s):
Title:
- Spectral sampling of manifolds
Session/Category Title: Sampling & filtering
Presenter(s)/Author(s):
Moderator(s):
Abstract:
A central problem in computer graphics is finding optimal sampling conditions for a given surface representation. We propose a new method to solve this problem based on spectral analysis of manifolds which results in faithful reconstructions and high quality isotropic samplings, is efficient, out-of-core, feature sensitive, intuitive to control and simple to implement. We approach the problem in a novel way by utilizing results from spectral analysis, kernel methods, and matrix perturbation theory. Change in a manifold due to a single point is quantified by a local measure that limits the change in the Laplace-Beltrami spectrum of the manifold. Hence, we do not need to explicitly compute the spectrum or any global quantity, which makes our algorithms very efficient. Although our main focus is on sampling surfaces, the analysis and algorithms are general and can be applied for simplifying and resampling point clouds lying near a manifold of arbitrary dimension.
References:
1. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. T. 2001. Point set surfaces. In VIS ’01, IEEE Computer Society, Washington, DC, USA, 21–28. Google ScholarDigital Library
2. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. T. 2003. Computing and rendering point set surfaces. IEEE Transactions on Computer Graphics and Visualization 9, 1, 3–15. Google ScholarDigital Library
3. Alliez, P., Meyer, M., and Desbrun, M. 2002. Interactive geometry remeshing. ACM Trans. Graph. 21, 3, 347–354. Google ScholarDigital Library
4. Alliez, P., Verdière, E. C. D., Devillers, O., and Isenburg, M. 2003. Isotropic surface remeshing. In SMI ’03, IEEE Computer Society, Washington, DC, USA, 49. Google ScholarDigital Library
5. Belkin, M., and Niyogi, P. 2006. Convergence of laplacian eigenmaps. In NIPS, 129–136.Google Scholar
6. Belkin, M., Sun, J., and Wang, Y. 2009. Constructing laplace operator from point clouds in rd. In SODA ’09, 1031–1040. Google ScholarDigital Library
7. Cignoni, P., Rocchini, C., and Scopigno, R. 2001. Metro: Measuring error on simplified surfaces. Computer Graphics Forum 17, 2, 167–174.Google ScholarCross Ref
8. Coifman, R. R., and Lafon, S. 2006. Diffusion maps. Applied and Computational Harmonic Analysis 21, 1, 5–30.Google ScholarCross Ref
9. Dey, T. K., and Goswami, S. 2003. Tight cocone: a water-tight surface reconstructor. In SM ’03, ACM, New York, NY, USA, 127–134. Google ScholarDigital Library
10. Dey, T. K., Rajan, P., and Wang, Y. 2010. Convergence, stability, and discrete approximation of laplace spectra. In SODA ’10, ACM. to appear. Google ScholarDigital Library
11. Drineas, P., and Mahoney, M. W. 2005. Approximating a gram matrix for improved kernel-based learning. In Learning Theory, vol. 3559. Springer Berlin / Heidelberg, 323–337. Google ScholarDigital Library
12. Fu, Y., and Zhou, B. 2008. Direct sampling on surfaces for high quality remeshing. In SPM ’08, ACM, New York, NY, USA, 115–124. Google ScholarDigital Library
13. Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In SIGGRAPH 97: Proc. of the 24th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 209–216. Google ScholarDigital Library
14. Grigor’yan, A. 1998. Estimates of heat kernels on riemannian manifolds. In Spectral Theory and Geometry. ICMS Instructional Conference, Cambridge Univ. Press, 140–225.Google Scholar
15. Guennebaud, G., and Gross, M. 2007. Algebraic point set surfaces. ACM Trans. Graph. (SIGGRAPH 2007) 26, 3, 23.1–23.9. Google ScholarDigital Library
16. Ham, J., Lee, D. D., Mika, S., and Schölkopf, B. 2004. A kernel view of the dimensionality reduction of manifolds. In ICML ’04, ACM, New York, NY, USA, 47. Google ScholarDigital Library
17. Kesavan, S. 1998. Listening to the shape of a drum. Resonance 3, 49–58. 10.1007/BF02841422.Google ScholarCross Ref
18. Kitago, M., and Gopi, M. 2006. Efficient and prioritized point subsampling for csrbf compression. In Symp. on Point-based Graphics, Eurographics. Google ScholarDigital Library
19. Lafon, S., and Lee, A. 2006. Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization. Pattern Analysis and Machine Intelligence, IEEE Transactions on 28, 9 (Sept.), 1393–1403. Google ScholarDigital Library
20. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 27, 1 (March), 114–129.Google ScholarCross Ref
21. Lai, Y.-K., Zhou, Q.-Y., Hu, S.-M., Wallner, J., and Pottmann, H. 2007. Robust feature classification and editing. IEEE Trans. Vis. Comp. Graphics 13, 1, 34–45. Google ScholarDigital Library
22. Levin, D. 2003. Mesh-independent surface interpolation. Geometric Modeling for Scientific Visualization, 37–49.Google Scholar
23. Lévy, B. 2006. Laplace-beltrami eigenfunctions towards an algorithm that “understands” geometry. In Shape Modeling International, IEEE Computer Society, 13.Google Scholar
24. Liu, R., Jain, V., and Zhang, H. 2006. Subsampling for efficient spectral mesh processing. In Computer Graphics International, 172–184. Google ScholarDigital Library
25. Moghaddam, B., Gruber, A., Weiss, Y., and Avidan, S. 2008. Sparse regression as a sparse eigenvalue problem. In Information Theory and Applications Workshop, 2008, 121–127.Google Scholar
26. Öztireli, C., Guennebaud, G., and Gross, M. 2009. Feature preserving point set surfaces based on non-linear kernel regression. In Eurographics 2009, 493–501.Google Scholar
27. Öztireli, C., Alexa, M., and Gross, M. 2010. Spectral sampling of manifolds: Extended version. Tech. Rep. 683, ETH Zürich.Google Scholar
28. Pauly, M., Gross, M., and Kobbelt, L. P. 2002. Efficient simplification of point-sampled surfaces. In VIS ’02, IEEE Computer Society, Washington, DC, USA, 163–170. Google ScholarDigital Library
29. Reuter, M., Wolter, F.-E., and Peinecke, N. 2006. Laplace-beltrami spectra as “shape-dna” of surfaces and solids. Computer-Aided Design 38, 4, 342–366. Google ScholarDigital Library
30. Rustamov, R. M. 2007. Laplace-beltrami eigenfunctions for deformation invariant shape representation. In SGP07, Eurographics Association, Barcelona, Spain, A. Belyaev and M. Garland, Eds., 225–233. Google ScholarDigital Library
31. Schölkopf, B., Smola, A., and Müller, K.-R. 1998. Nonlinear component analysis as a kernel eigenvalue problem. Neural Comput. 10, 5, 1299–1319. Google ScholarDigital Library
32. Schreiner, J., Scheidegger, C., Fleishman, S., and Silva, C. 2006. Direct (re)meshing for efficient surface processing. Computer Graphics Forum (Eurographics 2006) 25, 3, 527–536.Google Scholar
33. Sun, J., Ovsjanikov, M., and Guibas, L. J. 2009. A concise and provably informative multi-scale signature based on heat diffusion. Comput. Graph. Forum 28, 5, 1383–1392. Google ScholarCross Ref
34. Taubin, G. 1995. A signal processing approach to fair surface design. In SIGGRAPH 95: Proc. of the 22nd annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 351–358. Google ScholarDigital Library
35. Ulichney, R. 1987. Digital halftoning. MIT Press, Cambridge, MA, USA. Google ScholarDigital Library
36. Valette, S., Chassery, J. M., and Prost, R. 2008. Generic remeshing of 3d triangular meshes with metric-dependent discrete voronoi diagrams. IEEE Transactions on Visualization and Computer Graphics 14, 369–381. Google ScholarDigital Library
37. Wardetzky, M., Mathur, S., Kälberer, F., and Grinspun, E. 2007. Discrete laplace operators: no free lunch. In SGP ’07, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 33–37. Google ScholarDigital Library
38. Witkin, A., and Heckbert, P. S. 1994. Using particles to sample and control implicit surfaces. In 21st annual conference on Computer graphics and interactive techniques, ACM Press, 269–278. Google ScholarDigital Library
39. Yan, D.-M., Lévy, B., Liu, Y., Sun, F., and Wang, W. 2009. Isotropic remeshing with fast and exact computation of restricted voronoi diagram. Comput. Graph. Forum (Symp. on Geometry Processing 2009) 28, 5, 1445–1455. Google ScholarDigital Library
40. Zhang, H., van Kaick, O., and Dyer, R. 2007. Spectral methods for mesh processing and analysis. In Eurographics State-of-the-art Report, 1–22.Google Scholar
