More Web Proxy on the site http://driver.im/

article

Short note: O(N) implementation of the fast marching algorithm

Authors:

Alberto Bartesaghi,

Guillermo SapiroAuthors Info & Claims

Journal of Computational Physics, Volume 212, Issue 2

Pages 393 - 399

https://doi.org/10.1016/j.jcp.2005.08.005

Published: 01 March 2006 Publication History

Abstract

In this note we present an implementation of the fast marching algorithm for solving Eikonal equations that in practice reduces the original run-time from O(NlogN) to linear. This lower run-time cost is obtained while keeping an error bound of the same order of magnitude as the original algorithm. This improvement is achieved introducing the straight forward untidy priority queue, obtained via a quantization of the priorities in the marching computation. We present the underlying framework, estimations on the error, and examples showing the usefulness of the proposed approach.

References

[1]

{1} J. Ahn, S. Oh, Dynamic calendar queue, in: Proceedings of the Thirty-Second Annual Simulation Symposium, 1999, p. 20.]]

Digital Library

[2]

{2} M. Boue, P. Dupuis, Markov chain approximation for deterministic control problems with affine dynamics and quadratic cost in the control, SIAM Journal on Numerical Analysis 36 (1999) 667-695.]]

Digital Library

[3]

{3} R. Brown, Calendar queues: A fast O(1) priority queue implementation for the simulation event set problem, Communications of the ACM 31 (1988) 1220-1227.]]

Digital Library

[4]

{4} L.D. Cohen, R. Kimmel, Global minimum for active contours models: A minimal path approach, International Journal of Computer Vision 24 (1997) 57-78.]]

Digital Library

[5]

{5} P. Danielsson, Euclidean distance mapping, Computer Graphics and Image Processing 14 (1980) 227-248.]]

[6]

{6} A.X. Falco, J.K. Udupa, F.K. Miyazawa, An ultra-fast user-steered image segmentation paradigm: Livewire on the fly, IEEE Transactions on Medical Imaging 19 (1) (2000) 55-62.]]

[7]

{7} J. Helmsen, E.G. Puckett, P. Collela, M. Dorr, Two new methods for simulating photolithography development in 3D, in: Proceedings of SPIE Microlithography IX, 1996, p. 253.]]

[8]

{8} R. Kimmel, Numerical Geometry of Images: Theory, Algorithms, and Applications, Springer-Verlag, New York, 2004.]]

Digital Library

[9]

{9} R. Kimmel, J.A. Sethian, Computing geodesic paths on manifolds, Proceedings of the National Academy of Sciences 95 (15) (1998) 8431-8435.]]

[10]

{10} R. Kimmel, J.A. Sethian, Optimal algorithm for shape from shading and path planning, Journal of Mathematical Imaging and Vision 14 (3) (2001) 237-244.]]

Digital Library

[11]

{11} K. Leong Tan, L. Thng, Snoopy calendar queue, in: Proceedings of the 32nd Conference on Winter Simulation, 2000, pp. 487-495.]]

Digital Library

[12]

{12} F. Memoli, G. Sapiro, Fast computation of weighted distance functions and geodesies on implicit hyper-surfaces, Journal of Computational Physics 173 (2) (2001) 730-764.]]

Digital Library

[13]

{13} R. Rönngren, J. Riboe, R. Ayani, Lazy queue: A new approach to implementing the pending-event set, in: Proceedings of the 24th Annual Symposium on Simulation, 1991, pp. 194-204.]]

Digital Library

[14]

{14} J.A. Sethian, A fast marching level-set method for monotonically advancing fronts, Proceedings of the National Academy of Sciences 93 (4) (1996) 1591-1595.]]

[15]

{15} J.A. Sethian, Level Set Methods: Evolving Interfaces in Geometry, Fluid Mechanics, Computer Vision and Materials Sciences, Cambridge University Press, 1996.]]

[16]

{16} M. Thorup, On RAM priority queues, in: Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 59-67.]]

Digital Library

[17]

{17} Y.R. Tsai, L.T. Cheng, S. Osher, H.K. Zhao, Fast sweeping algorithms for a class of Hamilton-Jacobi equations, SIAM Journal on Numerical Analysis 41 (2) (2002) 673-694.]]

[18]

{18} J.N. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Transactions on Automatic Control 40 (1995) 1528-1538.]]

[19]

{19} Y. Zhang, J. Qian, H.K. Zhao, High order fast sweeping methods for static Hamilton-Jacobi equations, Journal of Scientific Computing (to appear).]]

Digital Library

[20]

{20} H.K. Zhao, Fast sweeping method for Eikonal equations, Mathematics of Computation 74 (2004) 603-627.]]

Cited By

Zhang QHou JAdikusuma YWang WHe YOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)NeuroGFProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666977(19485-19501)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666977
López BMuñoz JQuevedo FMonje CGarrido SMoreno L(2023)4D Trajectory Planning Based on Fast Marching Square for UAV TeamsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.333600825:6(5703-5717)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TITS.2023.3336008
Shin SSummers R(2022)Deep Reinforcement Learning for Small Bowel Path Tracking Using Different Types of AnnotationsMedical Image Computing and Computer Assisted Intervention – MICCAI 202210.1007/978-3-031-16443-9_53(549-559)Online publication date: 18-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-16443-9_53
Show More Cited By

Index Terms

Short note: O(N) implementation of the fast marching algorithm

Recommendations

Short note: A high-order Padé ADI method for unsteady convection-diffusion equations

A high-order alternating direction implicit (ADI) method for computations of unsteady convection-diffusion equations is proposed. By using fourth-order Pade schemes for spatial derivatives, the present scheme is fourth-order accurate in space and second-...
A fast marching algorithm for the factored eikonal equation

The eikonal equation is instrumental in many applications in several fields ranging from computer vision to geoscience. This equation can be efficiently solved using the iterative Fast Sweeping (FS) methods and the direct Fast Marching (FM) methods. ...
Short Note: On reinitializing level set functions

In this paper, we consider reinitializing level functions through equation @f"t+sgn(@f^0)(@?@?@f@?-1)=0[16]. The method of Russo and Smereka [11] is taken in the spatial discretization of the equation. The spatial discretization is, simply speaking, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computational Physics

Journal of Computational Physics Volume 212, Issue 2

1 March 2006

418 pages

ISSN:0021-9991

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2005.

Publisher

Academic Press Professional, Inc.

United States

Publication History

Published: 01 March 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang QHou JAdikusuma YWang WHe YOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)NeuroGFProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666977(19485-19501)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666977
López BMuñoz JQuevedo FMonje CGarrido SMoreno L(2023)4D Trajectory Planning Based on Fast Marching Square for UAV TeamsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.333600825:6(5703-5717)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TITS.2023.3336008
Shin SSummers R(2022)Deep Reinforcement Learning for Small Bowel Path Tracking Using Different Types of AnnotationsMedical Image Computing and Computer Assisted Intervention – MICCAI 202210.1007/978-3-031-16443-9_53(549-559)Online publication date: 18-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-16443-9_53
Avots EMadadi MEscalera SGonzàlez JBaro XPällin PAnbarjafari G(2019)From 2D to 3D geodesic-based garment matchingMultimedia Tools and Applications10.1007/s11042-019-7739-578:18(25829-25853)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s11042-019-7739-5
Krayer BMüller S(2019)Generating signed distance fields on the GPU with ray mapsThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-019-01683-w35:6-8(961-971)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00371-019-01683-w
Chen DCohen L(2018)Fast Asymmetric Fronts Propagation for Image SegmentationJournal of Mathematical Imaging and Vision10.1007/s10851-017-0776-760:6(766-783)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s10851-017-0776-7
Garrido SMoreno LMartn Flvarez D(2017)Fast marching subjected to a vector fieldpath planning method for mars roversExpert Systems with Applications: An International Journal10.1016/j.eswa.2017.02.01978:C(334-346)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1016/j.eswa.2017.02.019
Qin YHan XYu HYu YZhang J(2016)Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagationACM Transactions on Graphics10.1145/2897824.292593035:4(1-13)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2897824.2925930
Haltakov VUnger CIlic S(2016)Geodesic pixel neighborhoods for 2D and 3D scene understandingComputer Vision and Image Understanding10.1016/j.cviu.2015.11.008148:C(164-180)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.cviu.2015.11.008
Shin SLee SNoh KYun ILee K(2016)Extraction of Coronary Vessels in Fluoroscopic X-Ray Sequences Using Vessel Correspondence OptimizationMedical Image Computing and Computer-Assisted Intervention - MICCAI 201610.1007/978-3-319-46726-9_36(308-316)Online publication date: 17-Oct-2016
https://dl.acm.org/doi/10.1007/978-3-319-46726-9_36
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents