“Biharmonic Distance” by Lipman, Rustamov and Funkhouser

  • ©Yaron Lipman, Raif Rustamov, and Thomas (Tom) A. Funkhouser

Conference:


Type:


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:


    1. 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.
    2. Berger, M. 2003. A Panoramic View of Riemannian Geometry. Springer-Verlag, Berlin.
    3. 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.
    4. 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.
    5. Coifman, R. R. and Lafon, S. 2006. Diffusion maps. Appl. Comput. Harmonic Anal. 21, 1, 5–30.
    6. 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.
    7. Giorgi, D., Biasotti, S., and Paraboschi, L. 2007. SHREC:SHape REtrieval Contest: Watertight models track. http://watertight.ge.imati.cnr.it/.
    8. 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.
    9. 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.
    10. 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).
    11. John, F. 1986. Partial Differential Equations. Springer-Verlag.
    12. McKean, J. and Singer, I. M. 1967. Curvature and the eigenvalues of the laplacian. J. Differential Geom. 1.
    13. 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.
    14. 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.
    15. Papadimitriou, C. 1985. An algorithm for shortest-path motion in three dimensions. Inf. Process. Lett. 20, 259–163.
    16. Pinkall, U. and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Exper. Math. 2, 15–36.
    17. Qiu, H. and Hancock, E. R. 2007. Clustering and embedding using commute times. IEEE Trans. Pattern Anal. Mach. Intell. 29, 11, 1873–1890.
    18. 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. 
    19. 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.
    20. 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.

ACM Digital Library Publication:


Overview Page: