“Geometric optimization via composite majorization” by Shtengel, Poranne, Sorkine-Hornung, Kovalsky and Lipman
Conference:
Type:
Title:
- Geometric optimization via composite majorization
Session/Category Title: Mappings and Deformations
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Many algorithms on meshes require the minimization of composite objectives, i.e., energies that are compositions of simpler parts. Canonical examples include mesh parameterization and deformation. We propose a second order optimization approach that exploits this composite structure to efficiently converge to a local minimum.Our main observation is that a convex-concave decomposition of the energy constituents is simple and readily available in many cases of practical relevance in graphics. We utilize such convex-concave decompositions to define a tight convex majorizer of the energy, which we employ as a convex second order approximation of the objective function. In contrast to existing approaches that largely use only local convexification, our method is able to take advantage of a more global view on the energy landscape. Our experiments on triangular meshes demonstrate that our approach outperforms the state of the art on standard problems in geometry processing, and potentially provide a unified framework for developing efficient geometric optimization algorithms.
References:
1. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2015. Seamless surface mappings. ACM Transactions on Graphics (TOG) 34, 4 (2015), 72.Google ScholarDigital Library
2. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 449–458. Google ScholarCross Ref
3. Mirela Ben-Chen, Ofir Weber, and Craig Gotsman. 2009. Variational harmonic maps for space deformation. In ACM Transactions on Graphics (TOG), Vol. 28. ACM, 34. Google ScholarDigital Library
4. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013. Integer-grid maps for reliable quad meshing. ACM Transactions on Graphics (TOG) 32, 4 (2013), 98.Google ScholarDigital Library
5. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. In ACM Transactions On Graphics (TOG), Vol. 28. ACM, 77. Google ScholarDigital Library
6. Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press. Google ScholarCross Ref
7. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A simple geometric model for elastic deformations. In ACM Transactions on Graphics (TOG), Vol. 29. ACM, 38. Google ScholarDigital Library
8. Edward Chien, Renjie Chen, and Ofir Weber. 2016. Bounded distortion harmonic shape interpolation. ACM Transactions on Graphics (TOG) 35, 4 (2016), 105.Google ScholarDigital Library
9. Ingrid Daubechies, Michel Defrise, and Christine De Mol. 2004. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications on Pure and Applied Mathematics 57, 11 (2004), 1413–1457. Google ScholarCross Ref
10. Ingrid Daubechies, Ronald DeVore, Massimo Fornasier, and C. Sinan Güntürk. 2010. Iteratively reweighted least squares minimization for sparse recovery. Communications on Pure and Applied Mathematics 63, 1 (2010), 1–38. Google ScholarCross Ref
11. Mathieu Desbrun, Mark Meyer, and Pierre Alliez. 2002. Intrinsic parameterizations of surface meshes. In Computer Graphics Forum, Vol. 21. Wiley Online Library, 209–218. Google ScholarCross Ref
12. Xiao-Ming Fu and Yang Liu. 2016. Computing inversion-free mappings by simplex assembly. ACM Transactions on Graphics (TOG) 35, 6 (2016), 216.Google ScholarDigital Library
13. Emden R Gansner, Yehuda Koren, and Stephen North. 2004. Graph drawing by stress majorization. In International Symposium on Graph Drawing. Springer, 239–250.Google Scholar
14. Philip Hartman and others. 1959. On functions representable as a difference of convex functions. Pacific J. Math 9, 3 (1959), 707–713. Google ScholarCross Ref
15. Kai Hormann and Günther Greiner. 2000. MIPS: An efficient global parametrization method. Technical Report. DTIC Document.Google Scholar
16. Qi-Xing Huang, Martin Wicke, Bart Adams, and Leonidas Guibas. 2009. Shape decomposition using modal analysis. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 407–416. Google ScholarCross Ref
17. David R Hunter and Kenneth Lange. 2004. A tutorial on MM algorithms. The American Statistician 58, 1 (2004), 30–37. Google ScholarCross Ref
18. Alec Jacobson, Daniele Panozzo, and others. 2016. LibIGL: A simple C++ geometry processing library. (2016). http://libigl.github.io/libigl/.Google Scholar
19. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Trans. Graph. 35, 4, Article 134 (July 2016), 11 pages.Google ScholarDigital Library
20. A. Kuzmin, M. Luisier, and O. Schenk. 2013. Fast Methods for Computing Selected Elements of the Green’s Function in Massively Parallel Nanoelectronic Device Simulations. In Proc. Euro-Par. 533–544. Google ScholarDigital Library
21. Vivek Kwatra, Irfan Essa, Aaron Bobick, and Nipun Kwatra. 2005. Texture optimization for example-based synthesis. ACM Transactions on Graphics (ToG) 24, 3 (2005), 795–802. Google ScholarDigital Library
22. K. Lange. 2013. Optimization. Springer. Google ScholarCross Ref
23. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics (TOG) 21, 3 (2002), 362–371. Google ScholarDigital Library
24. Yaron Lipman. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics (TOG) 31, 4 (2012), 108.Google ScholarDigital Library
25. Yaron Lipman, Stav Yagev, Roi Poranne, David W Jacobs, and Ronen Basri. 2014. Feature matching with bounded distortion. ACM Transactions on Graphics (TOG) 33, 3 (2014), 26.Google ScholarDigital Library
26. Thomas Lipp and Stephen Boyd. 2014. Variations and extension of the convex-concave procedure. Optimization and Engineering (2014), 1–25.Google Scholar
27. Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J Gortler. 2008. A local/global approach to mesh parameterization. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 1495–1504.Google ScholarDigital Library
28. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2016. Towards Real-time Simulation of Hyperelastic Materials. arXiv preprint arXiv:1604.07378 (2016).Google Scholar
29. James Martens. 2010. Deep learning via Hessian-free optimization. In Proceedings of the 27th International Conference on Machine Learning (ICML-10). 735–742.Google ScholarDigital Library
30. Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. 2008. Spectral conformal parameterization. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 1487–1494. Google ScholarCross Ref
31. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-aligned Global Parametrization. ACM Transactions on Graphics (TOG) 33, 4 (2014), Article No. 135. Google ScholarDigital Library
32. Jorge Nocedal and Stephen Wright. 2006. Numerical Optimization. Springer Science & Business Media.Google Scholar
33. Ulrich Pinkall and Konrad Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1 (1993), 15–36. Google ScholarCross Ref
34. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Maps. ACM Transactions on Graphics (TOG) 36, 2 (2017), 16:1–16:16.Google ScholarDigital Library
35. Olaf Schenk, Matthias Bollhöfer, and Rudolf A. Römer. 2008. On Large-Scale Diagonalization Techniques for the Anderson Model of Localization. SIAM Rev. 50, 1 (2008), 91–112. Google ScholarDigital Library
36. Olaf Schenk, Andreas Wächter, and Michael Hagemann. 2007. Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization. Computational Optimization and Applications 36, 2–3 (2007), 321–341.Google ScholarDigital Library
37. Nicol N Schraudolph. 2002. Fast curvature matrix-vector products for second-order gradient descent. Neural Computation 14, 7 (2002), 1723–1738. Google ScholarDigital Library
38. John Schreiner, Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2004. Inter-surface mapping. In ACM Transactions on Graphics (TOG), Vol. 23. ACM, 870–877. Google ScholarDigital Library
39. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Transactions on Graphics (TOG) 34, 4, Article 70 (July 2015), 9 pages.Google ScholarDigital Library
40. Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. 2015. Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. ACM Transactions on Graphics (TOG) 34, 4 (2015), 66.Google ScholarDigital Library
41. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry processing, Vol. 4.Google ScholarDigital Library
42. Chengcheng Tang, Xiang Sun, Alexandra Gomes, Johannes Wallner, and Helmut Pottmann. 2014. Form-finding with polyhedral meshes made simple. ACM Transactions on Graphics (TOG) 33, 4 (2014), 70–1. Google ScholarDigital Library
43. Joseph Teran, Eftychios Sifakis, Geoffrey Irving, and Ronald Fedkiw. 2005. Robust quasistatic finite elements and flesh simulation. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. ACM, 181–190. Google ScholarDigital Library
44. Max Wardetzky, Miklós Bergou, David Harmon, Denis Zorin, and Eitan Grinspun. 2007. Discrete quadratic curvature energies. Computer Aided Geometric Design 24, 8 (2007), 499–518. Google ScholarDigital Library
45. Ofir Weber, Ashish Myles, and Denis Zorin. 2012. Computing extremal quasiconformal maps. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1679–1689. Google ScholarDigital Library
46. Hongyi Xu, Funshing Sin, Yufeng Zhu, and Jernej Barbic. 2015. Nonlinear material design using principal stretches. ACM Transactions on Graphics (TOG) 34, 4 (2015), 75.Google ScholarDigital Library
47. Alan L Yuille and Anand Rangarajan. 2003. The concave-convex procedure. Neural Computation 15, 4 (2003), 915–936. Google ScholarDigital Library
