Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces. (English) Zbl 0991.65018
Summary: An algorithm for the computationally optimal construction of intrinsic weighted distance functions on implicit hyper-surfaces is introduced. The basic idea is to approximate the intrinsic weighted distance by the Euclidean weighted distance computed in a band surrounding the implicit hyper-surface in the embedding space, thereby performing all the computations in a Cartesian grid with classical and efficient numerics.
Based on work on geodesics on Riemannian manifolds with boundaries, we bound the error between the two distance functions. We show that this error is of the same order as the theoretical numerical error in computationally optimal, Hamilton-Jacobi-based, algorithms for computing distance functions in Cartesian grids. Therefore, we can use these algorithms, modified to deal with spaces with boundaries, and obtain also for the case of intrinsic distance functions on implicit hyper-surfaces a computationally efficient technique.
The approach can be extended to solve a more general class of Hamilton-Jacobi equations defined on the implicit surface, following the same idea of approximating their solutions by the solutions in the embedding Euclidean space. The framework here introduced thereby allows for the computations to be performed on a Cartesian grid with computationally optimal algorithms, in spite of the fact that the distance and Hamilton-Jacobi equations are intrinsic to the implicit hyper-surface.
Based on work on geodesics on Riemannian manifolds with boundaries, we bound the error between the two distance functions. We show that this error is of the same order as the theoretical numerical error in computationally optimal, Hamilton-Jacobi-based, algorithms for computing distance functions in Cartesian grids. Therefore, we can use these algorithms, modified to deal with spaces with boundaries, and obtain also for the case of intrinsic distance functions on implicit hyper-surfaces a computationally efficient technique.
The approach can be extended to solve a more general class of Hamilton-Jacobi equations defined on the implicit surface, following the same idea of approximating their solutions by the solutions in the embedding Euclidean space. The framework here introduced thereby allows for the computations to be performed on a Cartesian grid with computationally optimal algorithms, in spite of the fact that the distance and Hamilton-Jacobi equations are intrinsic to the implicit hyper-surface.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
Keywords:
error bound; fast computations; algorithm; weighted distance functions; implicit hyper-surfaces; geodesics; Riemannian manifolds; Hamilton-Jacobi equationsReferences:
| [1] | Adalsteinsson, D.; Sethian, J. A., A fast level set method for propagating interfaces, J. Comput. Phys., 118, 269 (1995) · Zbl 0823.65137 |
| [2] | Alexander, R.; Alexander, S., Geodesics in Riemannian manifolds with boundary, Indiana Univ. Math. J., 30, 481 (1981) · Zbl 0469.53039 |
| [3] | Alexander, S.; Berg, I. D.; Bishop, R. L., The Riemannian obstacle problem, Illinois J. Math., 31, 167 (1987) · Zbl 0625.53045 |
| [4] | Ambrosio, L.; Dancer, N., Calculus of Variations and Partial Differential Equations (2000), Springer-Verlag: Springer-Verlag New York |
| [5] | Ambrosio, L.; Soner, H. M., Level set approach to mean curvature flow in arbitrary codimension, J. Diff. Geom., 43, 693 (1996) · Zbl 0868.35046 |
| [6] | Bartesaghi, A.; Sapiro, G., A system for the generation of curves on 3D brain images, Hum. Brain Mapping, 14, 1 (2001) |
| [7] | Barth, T. J.; Sethian, J. A., Numerical schemes for the Hamilton-Jacobi and level set equations on triangulated domains, J. Comput. Phys., 145, 1 (1998) · Zbl 0911.65091 |
| [8] | M. Bertalmio, L. T. Cheng, S. Osher, and, G. Sapiro, Variational problems and partial differential equations on implicit surfaces: The framework and examples in image processing and pattern formation, IMA University of Minnesota, preprint, June 2000.; M. Bertalmio, L. T. Cheng, S. Osher, and, G. Sapiro, Variational problems and partial differential equations on implicit surfaces: The framework and examples in image processing and pattern formation, IMA University of Minnesota, preprint, June 2000. |
| [9] | Blitz++ website: available at, www.oonumerics.org/blitz; Blitz++ website: available at, www.oonumerics.org/blitz |
| [10] | Bloomenthal, J., Introduction to Implicit Surfaces (1997) · Zbl 0948.65014 |
| [11] | Boue, M.; Dupuis, P., Markov chain approximation for deterministic control problems with affine dynamics and quadratic cost in the control, SIAM J. Numer. Anal., 36, 667 (1999) · Zbl 0933.65073 |
| [12] | Bruckstein, A. M., On shape from shading, Comp. Vision Graph. Image Proc., 44, 139 (1988) |
| [13] | Caselles, V.; Kimmel, R.; Sapiro, G.; Sbert, C., Minimal surfaces based object segmentation, IEEE-PAMI, 19, 394 (April 1997) |
| [14] | Chen, S.; Merriman, B.; Osher, S.; Smereka, P., J. Comput. Phys., 135, 8 (1995) |
| [15] | D. L. Chopp, Some improvements of the fast marching method, SIAM J. Sci. Comput, in press.; D. L. Chopp, Some improvements of the fast marching method, SIAM J. Sci. Comput, in press. · Zbl 0991.65105 |
| [16] | Cheng, L. T., The Level Set Method Applied to Geometrically Based Motion, Material Science, and Image Processing (June 2000) |
| [17] | Cheng, L. T.; Burchard, P.; Merriman, B.; Osher, S., Motion of Curves Constrained on Surfaces Using a Level Set Approach (September 2000) |
| [18] | Cohen, L. D.; Kimmel, R., Global minimum for active contours models: A minimal path approach, Int. J. Comput. Vis., 24, 57 (1997) |
| [19] | Crandall, M. G.; Lions, P. L., Two approximations of solutions of Hamilton-Jacobi equations, Math. Comp., 43, 1 (1984) · Zbl 0556.65076 |
| [20] | Crandall, M. G.; Lions, P. L., Viscosity solutions of Hamilton-Jacobi equations, Trans. Am. Math. Soc., 277 (1983) · Zbl 0874.49025 |
| [21] | Dijkstra, E., A note on two problems in connection with graphs, Numerische Math., 1, 269 (1959) · Zbl 0092.16002 |
| [22] | M. Desbrun, M. Meyer, P. Scröeder, and, A. Barr, Discrete differential-geometry operators in \(n\); M. Desbrun, M. Meyer, P. Scröeder, and, A. Barr, Discrete differential-geometry operators in \(n\) |
| [23] | S. Fomel, A variational formulation of the fast marching Eikonal solver, Stanford Exploration Project, Report SERGEY, May 1 (May 2000), pp. 357-376.; S. Fomel, A variational formulation of the fast marching Eikonal solver, Stanford Exploration Project, Report SERGEY, May 1 (May 2000), pp. 357-376. |
| [24] | Foote, R. L., Regularity of the distance function, Proc. Am. Math. Soc., 92 (September 1984) · Zbl 0528.53005 |
| [25] | Frisken, S. F.; Perry, R. N.; Rockwood, A.; Jones, T., Adaptively sampled fields: A general representation of shape for computer graphics, Computer Graphics (SIGGRAPH) (July 2000) |
| [26] | J. Gomes, and, O. Faugeras, Representing and evolving smooth manifolds of arbitrary codimension embedded in \(IR^nn\); J. Gomes, and, O. Faugeras, Representing and evolving smooth manifolds of arbitrary codimension embedded in \(IR^nn\) |
| [27] | Helmsen, J.; Puckett, E. G.; Collela, P.; Dorr, M., Two new methods for simulating photolithography development in 3D, Proc. SPIE Microlithography, IX, 253 (1996) |
| [28] | P. Hoch, and, M. Rascle, Hamilton-Jacobi equations on a manifold and applications to grid generation or refinement, available at, http://www-math.unice.fr/∼hoch/psfiles/hamja.ps; P. Hoch, and, M. Rascle, Hamilton-Jacobi equations on a manifold and applications to grid generation or refinement, available at, http://www-math.unice.fr/∼hoch/psfiles/hamja.ps · Zbl 1009.65063 |
| [29] | Ishii, H., A simple direct proof of uniqueness for solutions of the Hamilton-Jacobi equations of Eikonal type, Proc. Amer. Math. Soc., 100, 247 (1987) · Zbl 0644.35017 |
| [30] | Khaneja, N.; Miller, M. I.; Grenander, U., Dynamic programming generation of geodesics and sulci on brain surfaces, IEEE Trans. Pattern Anal. Mach. Intelligence, 20, 1260 (1998) |
| [31] | Kimmel, R., Numerical Geometry of Images: Theory, Algorithms, and Applications (October 1999) |
| [32] | Kimmel, R.; Sethian, J. A., Computing geodesic paths on manifolds, Proc. Nat. Acad. Sci., 95, 8431 (1998) · Zbl 0908.65049 |
| [33] | Kiryati, N.; Székely, G., Estimating shortest paths and minimal distances on digitized three dimensional surfaces, Pattern Recognition, 26, 1623 (1993) |
| [34] | Krishnamurthy, V.; Levoy, M., Fitting smooth surfaces to dense polygon meshes, Comput. Graph., 313 (1996) |
| [35] | Latombe, J. C., Robot Motion Planning (1991) |
| [36] | Lafon, F.; Osher, S., High order two dimensional nonoscillatory methods for solving Hamilton-Jacobi scalar equations, J. Comput. Phys., 123, 235 (1996) · Zbl 0849.65075 |
| [37] | Lee, J. M., Riemannian Manifolds, An Introduction to Curvature (1997) · Zbl 0905.53001 |
| [38] | C. Mantegazza, and, A. C. Menucci, Hamilton-Jacobi equations and distance functions on Riemannian manifolds, available at, http://cvgmt.sns.it/papers/manmen99/; C. Mantegazza, and, A. C. Menucci, Hamilton-Jacobi equations and distance functions on Riemannian manifolds, available at, http://cvgmt.sns.it/papers/manmen99/ |
| [39] | Marino, A.; Scolozzi, D., Boll. Un. Mat. Ital., 6 (1983) |
| [40] | S. Mauch, Closest point transform, available at, www.ama.caltech.edu/∼seanm/software/cpt/cpt.html; S. Mauch, Closest point transform, available at, www.ama.caltech.edu/∼seanm/software/cpt/cpt.html |
| [41] | F. Memoli, G. Sapiro, and, S. Osher, Harmonic maps onto implicit manifolds, preprint, March 2001.; F. Memoli, G. Sapiro, and, S. Osher, Harmonic maps onto implicit manifolds, preprint, March 2001. |
| [42] | Mitchell, J. S.B., An algorithmic approach to some problems in terrain navigation, Artif. Intelligence, 37, 171 (1988) · Zbl 0665.68090 |
| [43] | Mitchell, J. S.B.; Payton, D.; Keirsey, D., Planning and reasoning for autonomous vehicle control, Int. J. Intelligent Syst., 2, 129 (1987) |
| [44] | Osher, S., A level-set formulation for the solution of the Dirichlet problem for Hamilton-Jacobi equations, SIMA J. Numer. Anal., 24, 1145 (1993) · Zbl 0804.35021 |
| [45] | S. J. Osher, and, R. P. Fedkiw, Level set methods, UCLA CAM Report 00-07, February 2000.; S. J. Osher, and, R. P. Fedkiw, Level set methods, UCLA CAM Report 00-07, February 2000. · Zbl 1026.76001 |
| [46] | Osher, S. J.; Sethian, J. A., Fronts propagation with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79, 12 (1988) · Zbl 0659.65132 |
| [47] | Peng, D.; Merriman, B.; Osher, S.; Zhao, H.; Kang, M., A PDE-based fast local level set method, J. Comput. Phys., 155, 410 (1999) · Zbl 0964.76069 |
| [48] | Preparata, F. P.; Shamos, M. I., Computational Geometry (1990) |
| [49] | Rouy, E.; Tourin, A., A viscosity solutions approach to shape-from-shading, SIAM. J. Numer. Anal., 29, 867 (1992) · Zbl 0754.65069 |
| [50] | Sakai, T., Riemannian Geometry, 149 (1996) · Zbl 0886.53002 |
| [51] | Sethian, J., Fast marching level set methods for three-dimensional photolithography development, SPIE International Symposium on Microlithography (March 1996) |
| [52] | Sethian, J. A., A fast marching level-set method for monotonically advancing fronts, Proc. Nat. Acad. Sci., 93, 1591 (1996) · Zbl 0852.65055 |
| [53] | Sethian, J. A., Level Set Methods: Evolving Interfaces in Geometry, Fluid Mechanics, Computer Vision and Materials Sciences (1996) · Zbl 0859.76004 |
| [54] | Simon, L., Theorems on Regularity and Singularity of Energy Minimizing Maps (1996) · Zbl 0864.58015 |
| [55] | Taubin, G., Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations with applications to edge and range image segmentation, IEEE Trans. PAMI, 13, 1115 (1991) |
| [56] | Toga, A. W., Brain Warping (1998) |
| [57] | Thompson, P.; Woods, R.; Mega, M.; Toga, A., Mathematical/computational challenges in creating deformable and probabilistic atlases of the human brain, Human Brain Mapping, 9, 81 (2000) |
| [58] | Tsai, Y., Rapid and accurate computation of the distance function using grids (October 2000) |
| [59] | Tsitsiklis, J. N., Efficient algorithms for globally optimal trajectories, IEEE Trans. Autom. Control, 40, 1528 (1995) · Zbl 0831.93028 |
| [60] | D. C. Van Essen, H. Drury, S. Joshi, and, M. I. Miller, Functional and structural mapping of human cerebral cortex: Solutions are in the surfaces, Proc. Nat. Acad. Sci, 95, 788, February 1998.; D. C. Van Essen, H. Drury, S. Joshi, and, M. I. Miller, Functional and structural mapping of human cerebral cortex: Solutions are in the surfaces, Proc. Nat. Acad. Sci, 95, 788, February 1998. |
| [61] | Wandell, B.; Chial, S.; Backus, B., Cortical visualization, J. Cognit. Neurosci., 12, 739 (2000) |
| [62] | A. Witkin and P. Heckbert, Using particles to sample and control implicit surfaces, Computer Graphics (SIGGRAPH), pp. 269-278, 1994.; A. Witkin and P. Heckbert, Using particles to sample and control implicit surfaces, Computer Graphics (SIGGRAPH), pp. 269-278, 1994. |
| [63] | F. E. Wolter, Cut Loci in Bordered and Unbordered Riemannian manifolds, Doctoral Dissertation Technische Universität, Berlin, 1985.; F. E. Wolter, Cut Loci in Bordered and Unbordered Riemannian manifolds, Doctoral Dissertation Technische Universität, Berlin, 1985. · Zbl 0674.53049 |
| [64] | Wood, Z.; Desburn, M.; Schröder, P.; Breen, D., Semi-Regular mesh extraction from volume, Proc. IEEE Visualization (2000) |
| [65] | G. Yngve, and, G. Turk, Creating smooth implicit surfaces from polygonal meshes, Technical Report GIT-GVU-99-42, Graphics, Visualization, and Usability Center. Georgia Institute of Technology, 1999, available at, www.cc.gatech.edu/gvu/geometry/publications.html; G. Yngve, and, G. Turk, Creating smooth implicit surfaces from polygonal meshes, Technical Report GIT-GVU-99-42, Graphics, Visualization, and Usability Center. Georgia Institute of Technology, 1999, available at, www.cc.gatech.edu/gvu/geometry/publications.html |
| [66] | Yezzi, A.; Kichenassamy, S.; Olver, P.; Tannenbaum, A., Geometric active contours for segmentation of medical imagery, IEEE Trans. Medical Imaging, 16, 199 (1997) |
| [67] | Zhao, H.; Osher, S.; Merriman, B.; Kang, M., Implicit, non-parametric shape reconstruction from unorganized points using a variational level set method, Comp. Vision Image Understanding, 80, 295 (2000) · Zbl 1011.68538 |
| [68] | G. Zigelman, R. Kimmel, and, N. Kiryati, Texture Mapping using Surface Flattening via Multidimensional Scaling; G. Zigelman, R. Kimmel, and, N. Kiryati, Texture Mapping using Surface Flattening via Multidimensional Scaling |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
