Abstract
In geometry processing, smoothness energies are commonly used to model scattered data interpolation, dense data denoising, and regularization during shape optimization. The squared Laplacian energy is a popular choice of energy and has a corresponding standard implementation: squaring the discrete Laplacian matrix. For compact domains, when values along the boundary are not known in advance, this construction bakes in low-order boundary conditions. This causes the geometric shape of the boundary to strongly bias the solution. For many applications, this is undesirable. Instead, we propose using the squared Frobenius norm of the Hessian as a smoothness energy. Unlike the squared Laplacian energy, this energy’s natural boundary conditions (those that best minimize the energy) correspond to meaningful high-order boundary conditions. These boundary conditions model free boundaries where the shape of the boundary should not bias the solution locally. Our analysis begins in the smooth setting and concludes with discretizations using finite-differences on 2D grids or mixed finite elements for triangle meshes. We demonstrate the core behavior of the squared Hessian as a smoothness energy for various tasks.
Supplemental Material
Available for Download
Supplemental movie and image files for, Natural Boundary Conditions for Smoothing in Geometry Processing
- E. D. Andersen and K. D. Andersen. 2000. The mosek interior point optimizer for linear programming: An implementation of the homogeneous algorithm. In High Performance Optimization. Kluwer Academic Publishers, 197--232.Google Scholar
- James Andrews, Pushkar Joshi, and Nathan Carr. 2011. A linear variational system for modeling from curves. Comput. Graph. Forum 30, 6, 1850--1861.Google ScholarCross Ref
- Omri Azencot, Maks Ovsjanikov, Frédéric Chazal, and Mirela Ben-Chen. 2015. Discrete derivatives of vector fields on surfaces—an operator approach. ACM Trans. Graph. 34, 3 (May 2015), Article 29, 13 pages. Google ScholarDigital Library
- Ilya Baran and Jovan Popović. 2007. Automatic rigging and animation of 3D characters. ACM Trans. Graph. 26, 3 (2007), 72:1--72:8. Google ScholarDigital Library
- Christopher Batty. 2010. Simulating Viscous Incompressible Fluids with Embedded Boundary Finite Difference Methods. Ph.D. Dissertation. University of British Columbia.Google Scholar
- M. Belkin and P. Niyogi. 2004. Semi-supervised learning on Riemannian manifolds. Mach. Learn. 56, 1--3 (2004), 209--239. Google ScholarDigital Library
- Miklos Bergou, Max Wardetzky, David Harmon, Denis Zorin, and Eitan Grinspun. 2006. A quadratic bending model for inextensible surfaces. In Proceedings of the 4th Eurographics Symposium on Geometry Processing (SGP’06). 227--230. Google ScholarDigital Library
- Morten Bojsen-Hansen and Chris Wojtan. 2016. Generalized non-reflecting boundaries for fluid re-simulation. ACM Trans. Graph. 35, 4 (2016), Article 96. Google ScholarDigital Library
- F. L. Bookstein. 1989. Principal warps: Thin-plate splines and the decomposition of deformations. IEEE Trans. Pattern Anal. Mach. Intell. 11, 6, 567--585. Google ScholarDigital Library
- Mario Botsch and Leif Kobbelt. 2004. A remeshing approach to multiresolution modeling. In Proceedings of the 2nd Eurographics Symposium on Geometry Processing (SGP’04). 189--196. Google ScholarDigital Library
- M. Botsch and L. Kobbelt. 2005. Real-time shape editing using radial basis functions. Comp. Graph. Forum 24, 3 (2005), 611--621.Google ScholarCross Ref
- D. Braess. 2002. Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics (2nd ed.; Vol. 13). Cambridge University Press.Google Scholar
- D. Braess, A. S. Pechstein, and J. Schöberl. 2017. An equilibration based a posteriori error estimate for the biharmonic equation and two finite element methods. arXiv:1705.07607.Google Scholar
- A. Bronstein, Y. Choukroun, R. Kimmel, and M. Sela. 2016. Consistent discretization and minimization of the l1 norm on manifolds. In Proceedings of the 4th International Conference on 3D Vision (3DV’16).Google Scholar
- Chen Cao, Derek Bradley, Kun Zhou, and Thabo Beeler. 2015. Real-time high-fidelity facial performance capture. ACM Trans. Graph. 34, 4, Article 46. Google ScholarDigital Library
- Chen Cao, Yanlin Weng, Shun Zhou, Yiying Tong, and Kun Zhou. 2014. Facewarehouse: A 3D facial expression database for visual computing. IEEE Trans. Vis. Comput. Graph. 20, 3, 413--425. Google ScholarDigital Library
- Renjie Chen and Ofir Weber. 2015. Bounded distortion harmonic mappings in the plane. ACM Trans. Graph. 34, 4, Article 73. Google ScholarDigital Library
- Daniel Cohen-Steiner and Mathieu Desbrun. 2002. Hindsight: LSCM and DNCP Are One and the Same. Technical Report. INRIA-USC.Google Scholar
- M. I. Comodi. 1989. The Hellan-Herrmann-Johnson method: Some new error estimates and postprocessing. Math. Comput. 52, 185 (1989), 17--29.Google ScholarCross Ref
- Richard Courant and David Hilbert. 1924. Methoden der Mathematischen Physik I. Knight, Berlin, Germany.Google Scholar
- Keenan Crane. 2009. A Cotangent Laplacian for Surfaces with Boundary. Technical Report. INRIA-USC.Google Scholar
- Fernando de Goes, Beibei Liu, Max Budninskiy, Yiying Tong, and Mathieu Desbrun. 2014. Discrete 2-tensor fields on triangulations. Comp. Graph. Forum 33, 5, 13--24.Google ScholarDigital Library
- Mathieu Desbrun, Mark Meyer, and Pierre Alliez. 2002. Intrinsic parameterizations of surface meshes. Comp. Graph. Forum 21, 3 (2002), 209--218.Google ScholarCross Ref
- 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 ACM SIGGRAPH Conference. Google ScholarDigital Library
- Stephan Didas and Joachim Weickert. 2004. Higher Order Variational Methods for Noise Removal in Signals and Images. Diploma Thesis. Saarland University, Saarbrücken.Google Scholar
- Stephan Didas, Joachim Weickert, and Bernhard Burgeth. 2009. Properties of higher order nonlinear diffusion filtering. J. Math. Imag. Vis. 35, 3 (2009), 208--226. Google ScholarDigital Library
- David L. Donoho and Carrie Grimes. 2003. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proc. Natl. Acad. Sci. U S A 100, 10, 5591--5596.Google ScholarCross Ref
- Lawrence C. Evans. 1998. Partial Differential Equations. American Mathematical Society, Providence, RI.Google Scholar
- Carlos A. Felippa. 2017. Advanced Finite Element Methods—Course Notes. Retrieved from https://www.colorado.edu/engineering/CAS/courses.d/AFEM.d/.Google Scholar
- Mark Finch, John Snyder, and Hugues Hoppe. 2011. Freeform vector graphics with controlled thin-plate splines. ACM Trans. Graph. 30, 6, Article 166. Google ScholarDigital Library
- M. Fisher, P. Schröder, M. Desbrun, and H. Hoppe. 2007. Design of tangent vector fields. ACM Trans. Graph. 26, 3 (2007), Article 56. Google ScholarDigital Library
- Bengt Fornberg. 1988. Generation of finite difference formulas on arbitrarily spaced grids. Math. Comput. 51, 184, 699--706.Google Scholar
- A. Garg, E. Grinspun, M. Wardetzky, and D. Zorin. 2007. Cubic shells. Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 91--98. Google ScholarDigital Library
- I. M. Gelfand and S. V. Fomin. 1963. Calculus of Variations. Prentice Hall.Google Scholar
- T. G. Georgiev. 2004. Photoshop healing brush: A tool for seamless cloning. In Proceedings of the ECCV ACV Workshop. 1--8.Google Scholar
- Mariano Giaquinta and Stefan Hildebrandt. 1996. Calculus of Variations I. Springer.Google Scholar
- Y. I. Gingold, P. Davidson, J. Han, and D. Zorin. 2006. A direct texture placement and editing interface. In Proceedings of the 19th Annual ACM Symposium on User Interface Software and Technology. 23--32. Google ScholarDigital Library
- A. Godil, A. Axenopoulos, P. Daras, T. Furuya, and R. Ohbuchi. 2009. SHREC 2009: Shape retrieval contest of partial 3D models. In Proceedings of the Eurographics Workshop on 3D Object Retrieval. Google ScholarDigital Library
- Lei He and Scott Schaefer. 2013. Mesh denoising via L0 minimization. ACM Trans. Graph. 32, 4, Article 64. Google ScholarDigital Library
- Klaus Hildebrandt, Christian Schulz, Christoph Von Tycowicz, and Konrad Polthier. 2011. Interactive surface modeling using modal analysis. ACM Trans. Graph. 30, 5, 119. Google ScholarDigital Library
- Ronald Hoppe, Dietrich Braess, and Christopher Linsenmann. 2016. A two-energies principle for the biharmonic equation and an a posteriori error estimator for an interior penalty discontinuous Galerkin approximation. ESAIM. Available at https://www.esaim-m2an.org.Google Scholar
- Jin Huang, Xiaohan Shi, Xinguo Liu, Kun Zhou, Li-Yi Wei, Shang-Hua Teng, Hujun Bao, Baining Guo, and Heung-Yeung Shum. 2006. Subspace gradient domain mesh deformation. ACM Trans. Graph. 25, 3 (2006), 1126--1134. Google ScholarDigital Library
- Alec Jacobson, Ilya Baran, Jovan Popović, and Olga Sorkine. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4 (2011), Article 78. Google ScholarDigital Library
- A. Jacobson, Z. Deng, L. Kavan, and J. P. Lewis. 2014. Skinning: Real-time shape deformation. In ACM SIGGRAPH 2014 Courses. Google ScholarDigital Library
- Alec Jacobson, Daniele Panozzo, Christian Shuller, Olga Diamanti, Qingnan Zhou. Sebastian Koch, Jeremie Dumas, et al. 2017. Libigl: A Simple C++ Geometry Processing Library. Retrieved from http://libigl.github.io/libigl.Google ScholarDigital Library
- Alec Jacobson, Elif Tosun, Olga Sorkine, and Denis Zorin. 2010. Mixed finite elements for variational surface modeling. In Proceedings of the 8th Eurographics Symposium on Geometry Pressing (SGP’10).Google ScholarCross Ref
- Alec Jacobson, Tino Weinkauf, and Olga Sorkine. 2012. Smooth shape-aware functions with controlled extrema. In Proceedings of the 10th Eurographics Symposium on Geometry Processing (SGP’12).Google ScholarDigital Library
- Ben Jones, Nils Thuerey, Tamar Shinar, and Adam W. Bargteil. 2016. Example-based plastic deformation of rigid bodies. ACM Trans. Graph. 35, 4, Article 34. Google ScholarDigital Library
- Ladislav Kavan, Dan Gerszewski, Adam Bargteil, and Peter-Pike Sloan. 2011. Physics-inspired upsampling for cloth simulation in games. ACM Trans. Graph. 34, 4, Article 93. Google ScholarDigital Library
- Kwang I. Kim, Florian Steinke, and Matthias Hein. 2009. Semi-supervised regression using Hessian energy with an application to semi-supervised dimensionality reduction. In Advances in Neural Information Processing Systems. Google ScholarDigital Library
- Bishnu P. Lamichhane. 2011. A stabilized mixed finite element method for the biharmonic equation based on biorthogonal systems. J. Comp. Appl. Math. 235, 17, 5188--5197.Google ScholarCross Ref
- E. Landreneau and S. Schaefer. 2010. Poisson-based weight reduction of animated meshes. Comp. Graph. Forum 29, 6 (2010), 1945--1954.Google ScholarCross Ref
- Stamatios Lefkimmiatis, Aurélien Bourquard, and Michael Unser. 2012. Hessian-based norm regularization for image restoration with biomedical applications. IEEE Trans. Image Process. 21, 3 (2012), 983--995. Google ScholarDigital Library
- B. Lévy, S. Petitjean, N. Ray, and J. Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3 (2002), 362--371. Google ScholarDigital Library
- W. L. Li. 2000. Free vibrations of beams with general boundary conditions. J. Sound Vib. 237, 4 (2000), 709--725.Google ScholarCross Ref
- Yaron Lipman, Raif Rustamov, and Thomas Funkhouser. 2010. Biharmonic distance. ACM Trans. Graph. 29, 3 (2010), Article 27. Google ScholarDigital Library
- Beibei Liu, Yiying Tong, Fernando De Goes, and Mathieu Desbrun. 2016. Discrete connection and covariant derivative for vector field analysis and design. ACM Trans. Graph. 35, 3, Article 23. Google ScholarDigital Library
- X. Y. Liu, C.-H. Lai, and K. A. Pericleous. 2015. A fourth-order partial differential equation denoising model with an adaptive relaxation method. Int. J. Comput. Math. 92, 3 (2015), 608--622. Google ScholarDigital Library
- Marius Lysaker, Arvid Lundervold, and Xue-Cheng Tai. 2003. Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and time. IEEE Trans. Image Process. 12, 12, 1579--1590. Google ScholarDigital Library
- Marius Lysaker and Xue-Cheng Tai. 2006. Iterative image restoration combining total variation minimization and a second-order functional. Int. J. Comput. Vis. 66, 1, 5--18. Google ScholarDigital Library
- Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. 2008. Spectral conformal parameterization. In Proceedings of the 6th Eurographics Symposium on Geometry Processing (SGP’08). Google ScholarDigital Library
- Ulrich Pinkall and Konrad Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experiment. Math. 2, 1 (1993), 15--36.Google ScholarCross Ref
- Jean Marc Roth. 2009. Higher Order Anisotropic Smoothing of Images. Ph.D. Dissertation. Saarland University.Google Scholar
- Leonid I. Rudin, Stanley Osher, and Emad Fatemi. 1992. Nonlinear total variation based noise removal algorithms. Phys. D: Nonlinear Phenom. 60, 1 (1992), 259--268. Google ScholarDigital Library
- Raif M. Rustamov. 2011. Multiscale Biharmonic Kernels. Retrieved from https://diglib.eg.org/handle/10.1111/v30i5pp1521-1531.Google Scholar
- R. Scholz. 1978. A mixed method for 4th order problems using linear finite elements. RAIRO Anal. Numér. 1, 85--90.Google ScholarCross Ref
- Olga Sorkine, Yaron Lipman, Daniel Cohen-Or, Marc Alexa, Christian Rössl, and Hans-Peter Seidel. 2004. Laplacian surface editing. In Proceedings of the 2nd Eurographics Symposium on Geometry Processing (SGP’04). 179--188. Google ScholarDigital Library
- Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. 27, 3, Article 77. Google ScholarDigital Library
- Gabriele Steidl. 2006. A note on the dual treatment of higher-order regularization functionals. Computing 76, 1--2 (2006), 135--148. Google ScholarDigital Library
- Gabriele Steidl, Stephan Didas, and Julia Neumann. 2005. Relations between higher order TV regularization and support vector regression. In Proceedings of the International Conference on Scale-Space Theories in Computer Vision. 515--527. Google ScholarDigital Library
- Florian Steinke and Matthias Hein. 2009. Non-parametric regression between manifolds. In Advances in Neural Information Processing Systems. 1561--1568. Google ScholarDigital Library
- Daniel Sýkora, Ladislav Kavan, Martin Čadík, Ondřej Jamriška, Alec Jacobson, Brian Whited, Maryann Simmons, and Olga Sorkine-Hornung. 2014. Ink-and-ray: Bas-relief meshes for adding global illumination effects to hand-drawn characters. ACM Trans. Graph. 33, 2, Article 16. Google ScholarDigital Library
- Demetri Terzopoulos. 1984. Multilevel reconstruction of visual surfaces: Variational principles and finite-element representations. In Multiresolution Image Processing and Analysis. Springer, 237--310.Google Scholar
- Demetri Terzopoulos. 1988. The computation of visible-surface representations. IEEE Trans. Pattern Anal. Mach. Intell. 10, 4 (1988), 417--438. Google ScholarDigital Library
- E. Tosun, Y. I. Gingold, J. Reisman, and D. Zorin. 2007. Shape optimization using reflection lines. In Proceedings of the 5th Eurographics Symposium on Geometry Processing (SGP’07). Google ScholarDigital Library
- Yu Wang, Alec Jacobson, Jernej Barbič, and Ladislav Kavan. 2015. Linear subspace design for real-time shape deformation. ACM Trans. Graph. 34, 4, Article 57. Google ScholarDigital Library
- Yu Wang, Alec Jacobson, Jernej Barbič, and Ladislav Kavan. 2017. Error in “Linear Subspace Design for Real-Time Shape Deformation”. Technical Report.Google Scholar
- Ofir Weber, Roi Poranne, and Craig Gotsman. 2012. Biharmonic coordinates. In Comput. Graph. Forum, 31, 2409--2422. Google ScholarDigital Library
- Tino Weinkauf, Yotam Gingold, and Olga Sorkine. 2010. Topology-based smoothing of 2D scalar fields with -continuity. Comput. Graph. Forum 29, 3 (2010), 1221--1230. Google ScholarDigital Library
- Li Xu, Cewu Lu, Yi Xu, and Jiaya Jia. 2011. Image smoothing via L0 gradient minimization. ACM Trans. Graph. 30, 6, Article 174. Google ScholarDigital Library
- Y.-L. You and M. Kaveh. 2000. Fourth-order partial differential equations for noise removal. IEEE Trans. Image Process. 9, 10 (2000), 1723--1730. Google ScholarCross Ref
- Jing Yuan, Christoph Schnörr, and Gabriele Steidl. 2009. Total-variation based piecewise affine regularization. In Proceedings of the International Conference on Scale Space and Variational Methods in Computer Vision. 552--564. Google ScholarDigital Library
- Hao Zhang, Oliver van Kaick, and Ramsay Dyer. 2007. Spectral methods for mesh processing and analysis. In Proceedings of the Eurographics State-of-the-Art Report. 1--22.Google Scholar
- Kun Zhou, Jin Huang, John Snyder, Xinguo Liu, Hujun Bao, Baining Guo, and Heung-Yeung Shum. 2005. Large mesh deformation using the volumetric graph Laplacian. ACM Trans. Graph, 24, 3 (2005), 496--503. Google ScholarDigital Library
- Kun Zhou, Weiwei Xu, Yiying Tong, and Mathieu Desbrun. 2010. Deformation transfer to multi-component objects. Comp. Graph. Forum 29, 2 (2010), 319--325.Google ScholarCross Ref
Index Terms
- Natural Boundary Conditions for Smoothing in Geometry Processing
Recommendations
A Smoothness Energy without Boundary Distortion for Curved Surfaces
Current quadratic smoothness energies for curved surfaces either exhibit distortions near the boundary due to zero Neumann boundary conditions or they do not correctly account for intrinsic curvature, which leads to unnatural-looking behavior away from ...
Square smoothing regularization matrices with accurate boundary conditions
This paper is concerned with the solution of large-scale linear discrete ill-posed problems. The determination of a meaningful approximate solution of these problems requires regularization. We discuss regularization by the Tikhonov method and by ...
Visual data denoising with a unified Schatten-p norm and ℓq norm regularized principal component pursuit
To address the visual processing problem with corrupted data, in this paper, we propose a non-convex formulation to recover the authentic structure from the corrupted data. Typically, the specific structure is assumed to be low rank, which holds for a ...
Comments