Fast Methods for Eikonal Equations: An Experimental Survey

摘要

The Fast Marching Method is a very popular algorithm to computetimes-of-arrival maps (distances map measured in time units). Since theirproposal in 1995, it has been applied to many different applications such asrobotics, medical computer vision, fluid simulation, etc. Many alternativeshave been proposed with two main objectives: to reduce its computational timeand to improve its accuracy. In this paper, we collect the main approacheswhich improve the computational time of the standard Fast Marching Method,focusing on single-threaded methods and isotropic environments. 9 differentmethods are studied under a common mathematical framework and experimentally inrepresentative environments: Fast Marching Method with binary heap, FastMarching Method with Fibonacci Heap, Simplified Fast Marching Method, UntidyFast Marching Method, Fast Iterative Method, Group Marching Method, FastSweeping Method, Lock Sweeping Method and Double Dynamic Queue Method.