“Local barycentric coordinates” by Zhang, Deng, Liu, Patanè, Bouaziz, et al. …
Conference:
Type(s):
Title:
- Local barycentric coordinates
Session/Category Title: Smash and Stretch
Presenter(s)/Author(s):
Abstract:
Barycentric coordinates yield a powerful and yet simple paradigm to interpolate data values on polyhedral domains. They represent interior points of the domain as an affine combination of a set of control points, defining an interpolation scheme for any function defined on a set of control points. Numerous barycentric coordinate schemes have been proposed satisfying a large variety of properties. However, they typically define interpolation as a combination of all control points. Thus a local change in the value at a single control point will create a global change by propagation into the whole domain. In this context, we present a family of local barycentric coordinates (LBC), which select for each interior point a small set of control points and satisfy common requirements on barycentric coordinates, such as linearity, non-negativity, and smoothness. LBC are achieved through a convex optimization based on total variation, and provide a compact representation that reduces memory footprint and allows for fast deformations. Our experiments show that LBC provide more local and finer control on shape deformation than previous approaches, and lead to more intuitive deformation results.
References:
1. Ambrosio, L., Fusco, N., and Pallara, D. 2000. Functions of Bounded Variation and Free Discontinuity Problems. Oxford University Press.
2. Bach, F., Jenatton, R., Mairal, J., and Obozinski, G. 2012. Optimization with sparsity-inducing penalties. Foundations and Trends in Machine Learning 4, 1, 1–106.
3. Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning 3, 1, 1–122.
4. Bresson, X., Laurent, T., Uminsky, D., and Von Brecht, J. 2013. Multiclass total variation clustering. In Advances in Neural Information Processing Systems, 1421–1429.
5. Bruckstein, A., Donoho, D., and Elad, M. 2009. From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51, 1, 34–81.
6. Chambolle, A., Caselles, V., Cremers, D., Novaga, M., and Pock, T. 2010. An introduction to total variation for image analysis. Theoretical Foundations and Numerical Methods for Sparse Recovery 9, 263–340.
7. Chan, T. F., and Vese, L. A. 2001. Active contours without edges. IEEE Trans. Image Process. 10, 2, 266–277.
8. Chan, T., Esedoglu, S., Park, F., and Yip, A. 2006. Total variation image restoration: Overview and recent developments. In Handbook of Mathematical Models in Computer Vision, N. Paragios, Y. Chen, and O. Faugeras, Eds. Springer US, 17–31.
9. Chan, R., Chan, T., and Yip, A. 2011. Numerical methods and applications in total variation image restoration. In Handbook of Mathematical Methods in Imaging, O. Scherzer, Ed. Springer New York, 1059–1094.
10. Chartrand, R. 2007. Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Process. Lett. 14, 10, 707–710.Cross Ref
11. Combettes, P. L., and Pesquet, J.-C. 2011. Proximal splitting methods in signal processing. In Fixed-Point Algorithms for Inverse Problems in Science and Engineering, H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz, Eds. Springer, 185–212.
12. Crane, K., Weischedel, C., and Wardetzky, M. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Trans. Graph. 32, 5, 152:1–152:11.
13. Dasgupta, G., and Wachspress, E. L. 2008. Basis functions for concave polygons. Comput. Math. Appl. 56, 2, 459–468.
14. Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of surface meshes. Comput. Graph. Forum 21, 4, 209–218.Cross Ref
15. Elsey, M., and Esedoglu, S. 2009. Analogue of the total variation denoising model in the context of geometry processing. Multiscale Modeling & Simulation 7, 4, 1549–1573.Cross Ref
16. Evans, L. C., and Gariepy, R. F. 1992. Measure Theory and Fine Properties of Functions. CRC Press.
17. Farbman, Z., Hoffer, G., Lipman, Y., Cohen-Or, D., and Lischinski, D. 2009. Coordinates for instant image cloning. ACM Trans. Graph. 28, 3, 67:1–67:9.
18. Floater, M. S. 2003. Mean value coordinates. Comput. Aided Geom. Des. 20, 1, 19–27.
19. Garcí A, F. G., Paradinas, T., Coll, N., and Patow, G. 2013. *Cages: A multilevel, multi-cage-based system for mesh deformation. ACM Trans. Graph. 32, 3, 24:1–24:13.
20. Ge, D., Jiang, X., and Ye, Y. 2011. A note on the complexity of Lp minimization. Mathematical Programming 129, 2, 285–299.
21. Goldstein, T., and Osher, S. 2009. The split Bregman method for L1-regularized problems. SIAM J. Imaging Sci. 2, 2, 323–343.
22. Goldstein, T., Bresson, X., and Osher, S. 2010. Geometric applications of the split Bregman method: Segmentation and surface reconstruction. J. Sci. Comput. 45, 1-3, 272–293.
23. Grasmair, M., 2010. A coarea formula for anisotropic total variation regularisation. NRN Report No. 103.
24. Hiyoshi, H., and Sugihara, K. 2000. Voronoi-based interpolation with higher continuity. In Proc. SoCG, 242–250.
25. Hormann, K., and Floater, M. S. 2006. Mean value coordinates for arbitrary planar polygons. ACM Trans. Graph. 25, 4, 1424–1441.
26. Hormann, K., and Sukumar, N. 2008. Maximum entropy coordinates for arbitrary polytopes. Comput. Graph. Forum 27, 5, 1513–1520.
27. Jacobson, A., Baran, I., Popović, J., and Sorkine, O. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4, 78:1–78:8.
28. Jacobson, A., Weinkauf, T., and Sorkine, O. 2012. Smooth shape-aware functions with controlled extrema. Comput. Graph. Forum 31, 5, 1577–1586.
29. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26.
30. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3, 561–566.
31. Krantz, S. G., and Parks, H. R. 2002. A Primer of Real Analytic Functions, 2nd ed. Birkhäuser.
32. Landreneau, E., and Schaefer, S. 2010. Poisson-based weight reduction of animated meshes. Comput. Graph. Forum 29, 6, 1945–1954.Cross Ref
33. Lellmann, J., and Schnörr, C. 2011. Continuous multiclass labeling approaches and algorithms. SIAM J. Imaging Sci. 4, 4, 1049–1096.
34. Li, X.-Y., and Hu, S.-M. 2013. Poisson coordinates. IEEE Trans. Vis. Comput. Graph. 19, 2, 344–352.
35. Li, Z., Levin, D., Deng, Z., Liu, D., and Luo, X. 2010. Cage-free local deformations using green coordinates. Visual Comput. 26, 6-8, 1027–1036.
36. Li, X.-Y., Ju, T., and Hu, S.-M. 2013. Cubic mean value coordinates. ACM Trans. Graph. 32, 4, 126:1–126:10.
37. Lipman, Y., Kopf, J., Cohen-Or, D., and Levin, D. 2007. GPU-assisted positive mean value coordinates for mesh deformations. In Proc. SGP, 117–123.
38. Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Trans. Graph. 27, 3, 78:1–78:10.
39. Möbius, A. F. 1827. Der barycentrische Calcul: ein neues Hülfsmittel zur analytischen Behandlung der Geometrie. Barth.
40. Osserman, R. 1978. The isoperimetric inequality. Bulletin of the American Mathematical Society 84, 6, 1182–1238.Cross Ref
41. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1, 15–36.Cross Ref
42. Rudin, L. I., Osher, S., and Fatemi, E. 1992. Nonlinear total variation based noise removal algorithms. Phys. D 60, 1-4, 259–268.
43. Rustamov, R. M. 2011. Multiscale biharmonic kernels. Comput. Graph. Forum 30, 5, 1521–1531.Cross Ref
44. Schaefer, S., Ju, T., and Warren, J. 2007. A unified, integral construction for coordinates over closed curves. Comput. Aided Geom. Des. 24, 8–9, 481–493.
45. Sibson, R. 1981. A brief description of natural neighbour interpolation. In Interpreting Multivariate Data, V. Barnett, Ed. John Wiley & Sons, 21–36.
46. Takayama, K., Sorkine, O., Nealen, A., and Igarashi, T. 2010. Volumetric modeling with diffusion surfaces. ACM Trans. Graph. 29, 6, 180:1–180:8.
47. Wan, F. Y. 1995. Introduction to the Calculus of Variations and Its Applications, 2nd ed. Chapman & Hall.
48. Weber, O., and Gotsman, C. 2010. Controllable conformal maps for shape deformation and interpolation. ACM Trans. Graph. 29, 4, 78:1–78:11.
49. Weber, O., Ben-Chen, M., and Gotsman, C. 2009. Complex barycentric coordinates with applications to planar shape deformation. Comput. Graph. Forum 28, 2, 587–597.Cross Ref
50. Weber, O., Ben-Chen, M., Gotsman, C., and Hormann, K. 2011. A complex view of barycentric mappings. Comput. Graph. Forum 30, 5, 1533–1542.Cross Ref
51. Weber, O., Poranne, R., and Gotsman, C. 2012. Biharmonic coordinates. Comput. Graph. Forum 31, 8, 2409–2422.
52. Weiss, P., Blanc-Fraud, L., and Aubert, G. 2009. Efficient schemes for total variation minimization under constraints in image processing. SIAM J. Sci. Comput. 31, 3, 2047–2080.
53. Wu, C., and Tai, X.-C. 2010. Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models. SIAM J. Imaging Sci. 3, 3, 300–339.
