“Biharmonic Distance” by Lipman, Rustamov and Funkhouser
Conference:
Type(s):
Title:
- Biharmonic Distance
Presenter(s)/Author(s):
Abstract:
Measuring distances between pairs of points on a 3D surface is a fundamental problem in computer graphics and geometric processing. For most applications, the important properties of a distance are that it is a metric, smooth, locally isotropic, globally “shape-aware,” isometry-invariant, insensitive to noise and small topology changes, parameter-free, and practical to compute on a discrete mesh. However, the basic methods currently popular in computer graphics (e.g., geodesic and diffusion distances) do not have these basic properties. In this article, we propose a new distance measure based on the biharmonic differential operator that has all the desired properties. This new surface distance is related to the diffusion and commute-time distances, but applies different (inverse squared) weighting to the eigenvalues of the Laplace-Beltrami operator, which provides a nice trade-off between nearly geodesic distances for small distances and global shape-awareness for large distances. The article provides theoretical and empirical analysis for a large number of meshes.
References:
- Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., and Davis, J. 2005. Scape: Shape completion and animation of people. ACM Trans. Graph. 24, 3, 408–416.
- Berger, M. 2003. A Panoramic View of Riemannian Geometry. Springer-Verlag, Berlin.
- Botsch, M., Bommes, D., and Kobbelt, L. 2005. Efficient linear system solvers for mesh processing. In Mathematics of Surfaces XI. Lecture Notes in Computer Science, vol. 3604. Springer, 62–83.
- Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2006. Efficient computation of isometry-invariant distances between surfaces. SIAM J. Sci. Comput. 28, 5, 1812–1836.
- Coifman, R. R. and Lafon, S. 2006. Diffusion maps. Appl. Comput. Harmonic Anal. 21, 1, 5–30.
- Fouss, F., Pirotte, A., Michel Renders, J., and Saerens, M. 2006. Random-walk computation of similarities between nodes of a graph, with application to collaborative recommendation. IEEE Trans. Know. Data Engin. 19.
- Giorgi, D., Biasotti, S., and Paraboschi, L. 2007. SHREC:SHape REtrieval Contest: Watertight models track. http://watertight.ge.imati.cnr.it/.
- Goes, F. D., Goldenstein, S., and Velho, L. 2008. A hierarchical segmentation of articulated bodies. Comput. Graph. Forum (Special Issue of Symposium on Geometry Processing) 27, 5, 1349–1356.
- Gordon, W. J. and Wixom, J. A. 1978. Shepard’s method of “metric interpolation” to bivariate and multivariate interpolation. Math. Comput. 32, 141, 253–264.
- Grinspun, E., Gingold, Y., Reisman, J., and Zorin, D. 2006. Computing discrete shape operators on general meshes. Comput. Graph. Forum 25, 3, 547–556. (Eurographics 2006 Best Paper, 3rd Place).
- John, F. 1986. Partial Differential Equations. Springer-Verlag.
- McKean, J. and Singer, I. M. 1967. Curvature and the eigenvalues of the laplacian. J. Differential Geom. 1.
- Mémoli, F. and Sapiro, G. 2005. A theoretical and computational framework for isometry invariant recognition of point cloud data. Found. Comput. Math. 5, 3, 313–347.
- Meyer, M., Desbrun, M., Schröder, P., and Barr, A. H. 2002. Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and Mathematics III, H.-C. Hege and K. Polthier, Eds. Springer, 35–57.
- Papadimitriou, C. 1985. An algorithm for shortest-path motion in three dimensions. Inf. Process. Lett. 20, 259–163.
- Pinkall, U. and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Exper. Math. 2, 15–36.
- Qiu, H. and Hancock, E. R. 2007. Clustering and embedding using commute times. IEEE Trans. Pattern Anal. Mach. Intell. 29, 11, 1873–1890.
- Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proceedings of the 23rd ACM National Conference. ACM, New York, 517–524.
- Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., and Hoppe, H. 2005. Fast exact and approximate geodesics on meshes. ACM Trans. Graph. 24, 3, 553–560.
- Yen, L., Fouss, F., Decaestecker, C., Francq, P., and Saerens, M. 2007. Graph nodes clustering based on the commute-time kernel. In Proceedings of the 11th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD’07). Lecture Notes in Computer Science.