“Spectral coarsening of geometric operators” by Liu, Jacobson and Ovsjanikov
Conference:
Type(s):
Title:
- Spectral coarsening of geometric operators
Session/Category Title: Maps and Operators
Presenter(s)/Author(s):
Abstract:
We introduce a novel approach to measure the behavior of a geometric operator before and after coarsening. By comparing eigenvectors of the input operator and its coarsened counterpart, we can quantitatively and visually analyze how well the spectral properties of the operator are maintained. Using this measure, we show that standard mesh simplification and algebraic coarsening techniques fail to maintain spectral properties. In response, we introduce a novel approach for spectral coarsening. We show that it is possible to significantly reduce the sampling density of an operator derived from a 3D shape without affecting the low-frequency eigenvectors. By marrying techniques developed within the algebraic multigrid and the functional maps literatures, we successfully coarsen a variety of isotropic and anisotropic operators while maintaining sparsity and positive semi-definiteness. We demonstrate the utility of this approach for applications including operatorsensitive sampling, shape matching, and graph pooling for convolutional neural networks.
References:
1. Martin S. Andersen, Joachim Dahl, and Lieven Vandenberghe. 2010. Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones. Mathematical Programming Computation 2, 3 (Dec 2010).Google ScholarCross Ref
2. Mathieu Andreux, Emanuele Rodola, Mathieu Aubry, and Daniel Cremers. 2014. Anisotropic Laplace-Beltrami operators for shape analysis. In European Conference on Computer Vision. Springer, 299–312.Google Scholar
3. George B Arfken and Hans J Weber. 1999. Mathematical methods for physicists.Google Scholar
4. Mathieu Aubry, Ulrich Schlickewei, and Daniel Cremers. 2011. The wave kernel signature: A quantum mechanical approach to shape analysis. In Computer Vision Workshops (ICCV Workshops), 2011 IEEE International Conference on. IEEE, 1626–1633.Google ScholarCross Ref
5. Mikhail Belkin, Jian Sun, and Yusu Wang. 2009. Constructing Laplace operator from point clouds in R d. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1031–1040. Google ScholarDigital Library
6. William N Bell. 2008. Algebraic multigrid for discrete differential forms. (2008).Google Scholar
7. Gaurav Bharaj, David IW Levin, James Tompkin, Yun Fei, Hanspeter Pfister, Wojciech Matusik, and Changxi Zheng. 2015. Computational design of metallophone contact sounds. ACM Transactions on Graphics (TOG) 34, 6 (2015), 223. Google ScholarDigital Library
8. Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press. Google ScholarDigital Library
9. William L Briggs, Steve F McCormick, et al. 2000. A multigrid tutorial. Vol. 72. Siam.Google Scholar
10. Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. 2017. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine 34, 4 (2017), 18–42.Google ScholarCross Ref
11. Peter Burt and Edward Adelson. 1983. The Laplacian pyramid as a compact image code. IEEE Transactions on communications 31, 4 (1983), 532–540.Google ScholarCross Ref
12. Desai Chen, David I. Levin, Wojciech Matusik, and Danny M. Kaufman. 2017. Dynamics-Aware Numerical Coarsening for Fabrication Design. ACM Trans. Graph. 34, 4 (2017). Google ScholarDigital Library
13. Desai Chen, David I. W. Levin, Shinjiro Sueda, and Wojciech Matusik. 2015. Data-driven Finite Elements for Geometry and Material Design. ACM Trans. Graph. 34, 4 (2015). Google ScholarDigital Library
14. Jiong Chen, Hujun Bao, Tianyu Wang, Mathieu Desbrun, and Jin Huang. 2018. Numerical Coarsening Using Discontinuous Shape Functions. ACM Trans. Graph. 37, 4 (2018). Google ScholarDigital Library
15. Jie Chen and Ilya Safro. 2011. Algebraic distance on graphs. SIAM Journal on Scientific Computing 33, 6 (2011), 3468–3490. Google ScholarDigital Library
16. Paolo Cignoni, Marco Callieri, Massimiliano Corsini, Matteo Dellepiane, Fabio Ganovelli, and Guido Ranzuglia. 2008. Meshlab: an open-source mesh processing tool.. In Eurographics Italian chapter conference, Vol. 2008. 129–136.Google Scholar
17. Paolo Cignoni, Claudio Montani, and Roberto Scopigno. 1998. A comparison of mesh simplification algorithms. Computers & Graphics 22, 1 (1998), 37–54.Google ScholarCross Ref
18. Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik. 2017. EMNIST: an extension of MNIST to handwritten letters. arXiv preprint arXiv:1702.05373 (2017).Google Scholar
19. David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2004. Variational shape approximation. ACM Trans. on Graph. (2004). Google ScholarDigital Library
20. Etienne Corman, Justin Solomon, Mirela Ben-Chen, Leonidas Guibas, and Maks Ovsjanikov. 2017. Functional characterization of intrinsic and extrinsic geometry. ACM Transactions on Graphics (TOG) 36, 2 (2017), 14. Google ScholarDigital Library
21. Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems. 3844–3852. Google ScholarDigital Library
22. Mathieu Desbrun, Mark Meyer, Peter Schröder, and Alan H Barr. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In Proceedings of the 26th annual conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 317–324. Google ScholarDigital Library
23. Timothy Dozat. 2016. Incorporating nesterov momentum into adam. (2016).Google Scholar
24. Matthew Fisher, Boris Springborn, Alexander I Bobenko, and Peter Schroder. 2006. An algorithm for the construction of intrinsic Delaunay triangulations with applications to digital geometry processing. In ACM SIGGRAPH 2006 Courses. ACM, 69–74. Google ScholarDigital Library
25. Michael Garland and Paul S Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 209–216. Google ScholarDigital Library
26. Michael Garland and Paul S Heckbert. 1998. Simplifying surfaces with color and texture using quadric error metrics. In Visualization’98. Proceedings. IEEE, 263–269. Google ScholarDigital Library
27. Daniela Giorgi, Silvia Biasotti, and Laura Paraboschi. 2007. SHape REtrieval Contest 2007: Watertight Models Track. http://watertight.ge.imati.cnr.it/.Google Scholar
28. Igor Guskov, Andrei Khodakovsky, Peter Schröder, and Wim Sweldens. 2002. Hybrid meshes: multiresolution using regular and irregular refinement. In Proceedings of the eighteenth annual symposium on Computational geometry. ACM, 264–272. Google ScholarDigital Library
29. Hugues Hoppe. 1996. Progressive meshes. In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. ACM, 99–108. Google ScholarDigital Library
30. Hugues Hoppe. 1999. New quadric metric for simplifying meshes with appearance attributes. In Visualization’99. Proceedings. IEEE, 59–510. Google ScholarDigital Library
31. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. 1993. Mesh Optimization. In Proc. SIGGRAPH. 19–26. Google ScholarDigital Library
32. Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral meshing in the wild. ACM Transactions on Graphics (TOG) 37, 4 (2018), 60. Google ScholarDigital Library
33. Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. http://libigl.github.io/libigl/.Google Scholar
34. Miao Jin, Junho Kim, Feng Luo, and Xianfeng Gu. 2008. Discrete surface Ricci flow. IEEE Transactions on Visualization and Computer Graphics 14, 5 (2008), 1030–1043. Google ScholarDigital Library
35. Karsten Kahl and Matthias Rottmann. 2018. Least Angle Regression Coarsening in Bootstrap Algebraic Multigrid. arXiv preprint arXiv:1802.00595 (2018).Google Scholar
36. Lily Kharevych, Patrick Mullen, Houman Owhadi, and Mathieu Desbrun. 2009. Numerical coarsening of inhomogeneous elastic materials. ACM Trans. on Graph. (2009). Google ScholarDigital Library
37. Vladimir G Kim, Yaron Lipman, and Thomas Funkhouser. 2011. Blended intrinsic maps. In ACM Transactions on Graphics (TOG), Vol. 30. ACM, 79. Google ScholarDigital Library
38. Rasmus Kyng and Sushant Sachdeva. 2016. Approximate gaussian elimination for laplacians-fast, sparse, and simple. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on. IEEE, 573–582.Google ScholarCross Ref
39. Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998. Gradient-based learning applied to document recognition. Proc. IEEE 86, 11 (1998), 2278–2324.Google ScholarCross Ref
40. Dingzeyu Li, Yun Fei, and Changxi Zheng. 2015. Interactive Acoustic Transfer Approximation for Modal Sound. ACM Trans. Graph. 35, 1 (2015). Google ScholarDigital Library
41. Or Litany, Tal Remez, Emanuele Rodolà, Alexander M Bronstein, and Michael M Bronstein. 2017. Deep Functional Maps: Structured Prediction for Dense Shape Correspondence.. In ICCV. 5660–5668.Google Scholar
42. Oren E Livne and Achi Brandt. 2012. Lean algebraic multigrid (LAMG): Fast graph Laplacian linear solver. SIAM Journal on Scientific Computing 34, 4 (2012), B499–B522.Google ScholarDigital Library
43. Richard H MacNeal. 1949. The solution of partial differential equations by means of electrical networks. Ph.D. Dissertation. California Institute of Technology.Google Scholar
44. Thomas A Manteuffel, Luke N Olson, Jacob B Schroder, and Ben S Southworth. 2017. A Root-Node-Based Algebraic Multigrid Method. SIAM Journal on Scientific Computing 39, 5 (2017), S723–S756.Google ScholarCross Ref
45. Ahmad Nasikun, Christopher Brandt, and Klaus Hildebrandt. 2018. Fast Approximation of Laplace-Beltrami Eigenproblems. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 121–134.Google Scholar
46. Dorian Nogneng and Maks Ovsjanikov. 2017. Informative descriptor preservation via commutativity for shape matching. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 259–267. Google ScholarDigital Library
47. Luke N Olson, Jacob Schroder, and Raymond S Tuminaro. 2010. A new perspective on strength measures in algebraic multigrid. Numerical Linear Algebra with Applications 17, 4 (2010), 713–733.Google ScholarCross Ref
48. Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. 2012. Functional maps: a flexible representation of maps between shapes. ACM Transactions on Graphics (TOG) 31, 4 (2012), 30. Google ScholarDigital Library
49. A Cengiz Öztireli, Marc Alexa, and Markus Gross. 2010. Spectral sampling of manifolds. In ACM Transactions on Graphics (TOG), Vol. 29. ACM, 168. Google ScholarDigital Library
50. Gabriel Peyré and Stéphane Mallat. 2005. Surface compression with geometric bandelets. In ACM Transactions on Graphics (TOG), Vol. 24. ACM, 601–608. Google ScholarDigital Library
51. Ulrich Pinkall and Konrad Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experimental mathematics 2, 1 (1993), 15–36.Google Scholar
52. Jovan Popović and Hugues Hoppe. 1997. Progressive simplicial complexes. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 217–224. Google ScholarDigital Library
53. Yixuan Qiu. 2018. spectra: C++ Library For Large Scale Eigenvalue Problems.Google Scholar
54. https://github.com/yixuan/spectra/.Google Scholar
55. John W Ruge and Klaus Stüben. 1987. Algebraic multigrid. In Multigrid methods. SIAM, 73–130.Google Scholar
56. Raif M Rustamov, Maks Ovsjanikov, Omri Azencot, Mirela Ben-Chen, Frédéric Chazal, and Leonidas Guibas. 2013. Map-based exploration of intrinsic shape differences and variability. ACM Transactions on Graphics (TOG) 32, 4 (2013), 72. Google ScholarDigital Library
57. Peter Schroder. 1996. Wavelets in computer graphics. Proc. IEEE 84, 4 (1996), 615–625.Google ScholarCross Ref
58. William J Schroeder, Jonathan A Zarge, and William E Lorensen. 1992. Decimation of triangle meshes. In ACM siggraph computer graphics, Vol. 26. ACM, 65–70. Google ScholarDigital Library
59. Andrei Sharf, Thomas Lewiner, Gil Shklarski, Sivan Toledo, and Daniel Cohen-Or. 2007. Interactive topology-aware surface reconstruction. ACM Trans. on Graph. (2007). Google ScholarDigital Library
60. Anja Struyf, Mia Hubert, and Peter Rousseeuw. 1997. Clustering in an Object-Oriented Environment. Journal of Statistical Software (1997).Google Scholar
61. Klaus Stuben. 2000. Algebraic multigrid (AMG): an introduction with applications. Multigrid (2000).Google Scholar
62. Yifan Sun and Lieven Vandenberghe. 2015. Decomposition methods for sparse matrix nearness problems. SIAM J. Matrix Anal. Appl. 36, 4 (2015), 1691–1717.Google ScholarCross Ref
63. Rasmus Tamstorf, Toby Jones, and Stephen F McCormick. 2015. Smoothed aggregation multigrid for cloth simulation. ACM Trans. on Graph. (2015). Google ScholarDigital Library
64. Lieven Vandenberghe and Martin S. Andersen. 2015. Chordal Graphs and Semidefinite Optimization. Found. Trends Optim. 1, 4 (2015). Google ScholarDigital Library
65. Matthias Vestner, Zorah Lähner, Amit Boyarski, Or Litany, Ron Slossberg, Tal Remez, Emanuele Rodolà, Alexander M. Bronstein, Michael M. Bronstein, Ron Kimmel, and Daniel Cremers. 2017. Efficient Deformable Shape Correspondence via Kernel Matching. In 3DV.Google Scholar
66. Han Xiao, Kashif Rasul, and Roland Vollgraf. 2017. Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms. arXiv:cs.LG/cs.LG/1708.07747Google Scholar
67. Jinchao Xu and Ludmil Zikatanov. 2017. Algebraic multigrid methods. Acta Numerica 26 (2017), 591–721.Google ScholarCross Ref
68. Yang Zheng, Giovanni Fantuzzi, Antonis Papachristodoulou, Paul Goulart, and Andrew Wynn. 2017. Fast ADMM for semidefinite programs with chordal sparsity. In American Control Conference.Google ScholarCross Ref
69. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).Google Scholar
