| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
MultiStencils Fast Marching Methods: A Highly Accurate Solution to the Eikonal Equation on Cartesian Domains
September 2007 (vol. 29 no. 9)
pp. 1563-1574
A wide range of computer vision applications require an accurate solution of a particular Hamilton- Jacobi (HJ) equation, known as the Eikonal equation. In this paper, we propose an improved version of the fast marching method (FMM) that is highly accurate for both 2D and 3D Cartesian domains. The new method is called multi-stencils fast marching (MSFM), which computes the solution at each grid point by solving the Eikonal equation along several stencils and then picks the solution that satisfies the upwind condition. The stencils are centered at each grid point and cover its entire nearest neighbors. In 2D space, 2 stencils cover the 8-neighbors of the point, while in 3D space, 6 stencils cover its 26-neighbors. For those stencils that are not aligned with the natural coordinate system, the Eikonal equation is derived using directional derivatives and then solved using higher order finite difference schemes. The accuracy of the proposed method over the state-of-the-art FMM-based techniques has been demonstrated through comprehensive numerical experiments.
[1] S. Osher and J. Sethian, “Fronts Propagating with Curvature Speed: Algorithms Based on Hamilton-Jacobi Formulations,” J.Computational Physics, vol. 79, pp. 12-49, 1988.
[2] D. Adalsteinsson and J. Sethian, “A Fast Level Set Method for Propagating Interfaces,” J. Computational Physics, vol. 118, pp. 269-277, 1995.
[3] R. Kimmel and J.A. Sethian, “Optimal Algorithm for Shape from Shading and Path Planning,” J. Math. Imaging and Vision, vol. 14, no. 3, pp. 237-244, 2001.
[4] R. Kimmel and A.M. Bruckstein, “Shape Offsets via Level Sets,” Computer-Aided Design, vol. 25, no. 5, pp. 154-162, 1993.
[5] M.S. Hassouna, A.E. Abdel-Hakim, and A. Farag, “Robust Robotic Path Planning Using Level Sets,” Proc. IEEE Int'l Conf. Image Processing, pp. 473-476, 2005.
[6] T. Deschamps and L.D. Cohen, “Fast Extraction of Tubular and Tree 3D Surfaces with Front Propagation Methods,” Proc. Int'l Conf. Pattern Recognition, pp. 731-734, 2002.
[7] Z. Cao, S. Pan, R. Li, R. Balachandran, M.J. Fitzpatrick, W.C. Chapman, and B.M. Dawant, “Registration of Medical Images Using an Interpolated Closest Point Transform: Method and Validation,” Proc. SPIE Int'l Soc. Optical Eng. Medical Imaging, pp.325-333, 2003.
[8] H.E.A.E. Munim and A.A. Farag, “A Shape-Based Segmentation Approach: An Improved Technique Using Level Sets,” Proc. IEEE Int'l Conf. Computer Vision, pp. 930-935, 2005.
[9] R. Kimmel, D. Shaked, N. Kiryati, and A. Bruckstein, “Skeletonization via Distance Maps and Level Sets,” Computer Vision and Image Understanding, vol. 62, no. 3, pp. 382-391, 1995.
[10] M.S. Hassouna and A.A. Farag, “Robust Centerline Extraction Framework Using Level Sets,” Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 458-465, June 2005.
[11] V. Cerveny, “Ray Synthetic Seismograms for Complex Two- and Three-Dimensional Structures,” J. Geophysics, vol. 58, pp. 2-26, 1985.
[12] J. Vidale, “Finite-Difference Calculation of Traveltimes in Three Dimensions,” J. Geophysics, vol. 55, pp. 521-526, 1990.
[13] J. van Trier and W. Symes, “Upwind Finite-Difference Calculation of Traveltimes,” J. Geophysics, vol. 56, pp. 812-821, 1991.
[14] P. Podvin and I. Lecomte, “Finite Difference Computation of Traveltimes in Very Contrasted Velocity Models: A Massively Parallel Approach and Its Associated Tools,” Geophysical J. Int'l, vol. 105, pp. 271-284, 1991.
[15] S. Kim, “ENO-DNO-PS: A Stable, Second-Order Accuracy Eikonal Solver,” Soc. Exploration Geophysicists, pp. 1747-1750, 1999.
[16] D.L. Chopp, “Some Improvements on the Fast Marching Method,” SIAM J. Scientic Computing, vol. 23, no. 1, pp. 230-244, 2001.
[17] H. Zhao, “A Fast Sweeping Method for Eikonal Equations,” J.Math. and Computing, vol. 74, no. 250, pp. 603-627, 2005.
[18] J. Sethian, Level Sets Methods and Fast Marching Methods, second ed. Cambridge Univ. Press, 1999.
[19] R. Kimmel and J. Sethian, “Fast Marching Methods on Triangulated Domains,” Proc. Nat'l Academy of Sciences, vol. 95, no. 11, pp.8341-8435, 1998.
[20] J.A. Sethian and A. Vladimirsky, “Fast Methods for the Eikonal and Related Hamilton-Jacobi Equations on Unstructured Meshes,” Proc. Nat'l Academy of Sciences, vol. 97, no. 11, pp.5699-5703, 2000.
[21] J. Qian, Y. Zhang, and H. Zhao, “Fast Sweeping Methods for Eikonal Equations on Triangulated Meshes,” UCLA CAM Report 05-07, 2005, to appear in SIAM J. Numerical Analysis.
[22] R. Tsai, H. Zhao, and S. Osher, “Fast Sweeping Algorithms for a Class of Hamilton-Jacobi Equations,” SIAM J. Numerical Analysis, vol. 41, no. 2, pp. 673-694, 2003.
[23] C.Y. Kao, S. Osher, and J. Qian, “Lax-Friedrichs Sweeping Scheme for Static Hamilton-Jacobi Equations,” J. Computational Physics, vol. 196, no. 1, pp. 367-391, 2004.
[24] Y.-T. Zhang, H.-K. Zhao, and J. Qian, “High Order Fast Sweeping Methods for Static Hamilton-Jacobi Equations,” J. Scientific Computing, to appear.
[25] C. Kao, S. Osher, and R. Tsai, “Fast Sweeping Methods for Hamilton-Jacobi Equations,” SIAM J. Numerical Analysis, vol. 42, pp. 2612-2632, 2005.
[26] P.A. Gremaud and C.M. Kuster, “Computational Study of Fast Methods for the Eikonal Equation,” SIAM J. Scientific Computing, vol. 27, no. 6, pp. 1803-1816, 2006.
[27] S. Bouix, K. Siddiqi, and A. Tannenbaum, “Flux Driven Fly Throughs,” Proc. IEEE Computer Vision and Pattern Recognition, pp.449-454, June 2003.
[28] A. Telea, “An Image Inpainting Technique Based on the Fast Marching Method,” J. Graphics Tools, vol. 9, no. 1, pp. 23-34, 2004.
[29] P.E. Danielsson and Q. Lin, “A Modified Fast Marching Method,” Proc. Scandinavian Conf. Image Analysis, pp. 1154-1161, 2003.
[30] S. Kim, “An o(n) Level Set Method for Eikonal Equations,” SIAM J. Scientific Computing, vol. 22, no. 6, pp. 2178-2193, 2001.
[31] L. Yatziv, A. Bartesaghi, and G. Sapiro, “O(N) Implementation of the Fast Marching Algorithm,” J. Computational Physics, vol. 212, pp. 393-399, Mar. 2006.
[32] M.S. Hassouna and A.A. Farag, “Accurate Tracking of Monotonically Advancing Fronts,” Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 355-362, June17–22, 2006.
[33] J. Tsitsiklis, “Efficient Algorithms for Globally Optimal Trajectories,” IEEE Trans. Automatic Control, vol. 40, no. 9, pp. 1528-1538, 1995.
[34] J.A. Sethian and A. Vladimirsky, “Ordered Upwind Methods for Static Hamilton-Jacobi Equations: Theory and Algorithms,” SIAM J. Numerical Analysis, vol. 41, no. 1, pp. 325-363, 2003.
[35] S. Godunov, “Finite Difference Method for Numerical Computation of Discontinuous Solutions of the Equations of Fluid Dynamics,” Matematicheskii Sbornik, pp. 47-271, 1959, translated from Russian by I. Bohachevsky.
[36] H. Zhao, “Fast Sweeping Method for Eikonal Equations,” Math. Computation, vol. 74, pp. 603-627, 2004.
[37] E.W. Dijkstra, “A Note on Two Problems in Connection with Graphs,” Numerische Mathematik, vol. 1, pp. 269-271, 1959.
[38] S. Chen, B. Merriman, S. Osher, and P. Smereka, “A Simple Level Set Method for Solving Stefan Problem,” J. Computational Physics, vol. 138, no. 1, pp. 8-29, 1997.
[39] R. Kimmel and J. Sethian, “Computing Geodesic Paths on Manifolds,” Proc. Nat'l Academy of Sciences USA, vol. 95, no. 15, pp.8431-8435, 1998.
[40] J. Qian, Y. Zhang, and H. Zhao, “A Fast Sweeping Method for Static Convex Hamilton-Jacobi Equations,” UCLA CAM Report 06-37, 2002, J. Scientific Computing, to appear.
Index Terms:
Multi-stencils fast marching methods, monotonically advancing fronts, fast marching methods, level set methods, Eikonal equation
Citation:
M. Sabry Hassouna, A. A. Farag, "MultiStencils Fast Marching Methods: A Highly Accurate Solution to the Eikonal Equation on Cartesian Domains," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 9, pp. 1563-1574, June 2007, doi:10.1109/TPAMI.2007.1154
