Fast Methods for Eikonal Equations: An Experimental Survey
---
paper_title: Comparison of active contour and fast marching methods of hippocampus segmentation

paper_content:

The hippocampus is a part of the limbic system and plays an important role in long-term memory and spatial navigation. As part of hippocampal imaging studies, the region of the hippocampus is usually segmented manually, which is a time-consuming process. Here, we describe a comparison of the active contour model (ACM) and the fast marching method (FMM) using magnetic resonance (MR) images of the human brain. We determine optimized input parameters for both models to segment the hippocampus using T1-weighted MR images, and we found that the ACM provided superior performance compared with the FMM without significant additional computational expense.
---
paper_title: A fast marching level set method for monotonically advancing fronts.

paper_content:

Abstract ::: A fast marching level set method is presented for monotonically advancing fronts, which leads to an extremely fast scheme for solving the Eikonal equation. Level set methods are numerical techniques for computing the position of propagating fronts. They rely on an initial value partial differential equation for a propagating level set function and use techniques borrowed from hyperbolic conservation laws. Topological changes, corner and cusp development, and accurate determination of geometric properties such as curvature and normal direction are naturally obtained in this setting. This paper describes a particular case of such methods for interfaces whose speed depends only on local position. The technique works by coupling work on entropy conditions for interface motion, the theory of viscosity solutions for Hamilton-Jacobi equations, and fast adaptive narrow band level set methods. The technique is applicable to a variety of problems, including shape-from-shading problems, lithographic development calculations in microchip manufacturing, and arrival time problems in control theory.
---
paper_title: VDB: High-resolution sparse volumes with dynamic topology

paper_content:

We have developed a novel hierarchical data structure for the efficient representation of sparse, time-varying volumetric data discretized on a 3D grid. Our “VDB”, so named because it is a Volumetric, Dynamic grid that shares several characteristics with Bptrees, exploits spatial coherency of time-varying data to separately and compactly encode data values and grid topology. VDB models a virtually infinite 3D index space that allows for cache-coherent and fast data access into sparse volumes of high resolution. It imposes no topology restrictions on the sparsity of the volumetric data, and it supports fast (average O(1)) random access patterns when the data are inserted, retrieved, or deleted. This is in contrast to most existing sparse volumetric data structures, which assume either static or manifold topology and require specific data access patterns to compensate for slow random access. Since the VDB data structure is fundamentally hierarchical, it also facilitates adaptive grid sampling, and the inherent acceleration structure leads to fast algorithms that are well-suited for simulations. As such, VDB has proven useful for several applications that call for large, sparse, animated volumes, for example, level set dynamics and cloud modeling. In this article, we showcase some of these algorithms and compare VDB with existing, state-of-the-art data structures.
---
paper_title: A FAST SWEEPING METHOD FOR EIKONAL EQUATIONS

paper_content:

In this paper a fast sweeping method for computing the numerical solution of Eikonal equations on a rectangular grid is presented. The method is an iterative method which uses upwind difference for discretization and uses Gauss-Seidel iterations with alternating sweeping ordering to solve the discretized system. The crucial idea is that each sweeping ordering follows a family of characteristics of the corresponding Eikonal equation in a certain direction simultaneously. The method has an optimal complexity of O(N) for N grid points and is extremely simple to implement in any number of dimensions. Monotonicity and stability properties of the fast sweeping algorithm are proven. Convergence and error estimates of the algorithm for computing the distance function is studied in detail. It is shown that 2 n Gauss-Seidel iterations is enough for the distance function in n dimensions. An estimation of the number of iterations for general Eikonal equations is also studied. Numerical examples are used to verify the analysis.
---
paper_title: Generalized fast marching method: applications to image segmentation

paper_content:

In this paper, we propose a segmentation method based on the generalized fast marching method (GFMM) developed by Carlini et al. (submitted). The classical fast marching method (FMM) is a very efficient method for front evolution problems with normal velocity (see also Epstein and Gage, The curve shortening flow. In: Chorin, A., Majda, A. (eds.) Wave Motion: Theory, Modelling and Computation, 1997) of constant sign. The GFMM is an extension of the FMM and removes this sign constraint by authorizing time-dependent velocity with no restriction on the sign. In our modelling, the velocity is borrowed from the Chan–Vese model for segmentation (Chan and Vese, IEEE Trans Image Process 10(2):266–277, 2001). The algorithm is presented and analyzed and some numerical experiments are given, showing in particular that the constraints in the initialization stage can be weakened and that the GFMM offers a powerful and computationally efficient algorithm.
---
paper_title: Fast Marching Method Seismic Traveltimes with Reconfigurable Field Programmable Gate Arrays

paper_content:

This paper presents a hardware based least time path fast marching method for seismic traveltime calculation. The hardware implementation uses field programmable gate array (FPGA) reconfigurable computing technology and applies it to a compute intensive seismic problem. The algorithm transformation process is described at a system level and at a detailed hardware level.
---
paper_title: Online Safe Trajectory Generation for Quadrotors Using Fast Marching Method and Bernstein Basis Polynomial

paper_content:

In this paper, we propose a framework for online quadrotor motion planning for autonomous navigation in unknown environments. Based on the onboard state estimation and environment perception, we adopt a fast marching-based path searching method to find a path on a velocity field induced by the Euclidean signed distance field (ESDF) of the map, to achieve better time allocation. We generate a flight corridor for the quadrotor to travel through by inflating the path against the environment. We represent the trajectory as piecewise Bezier curves by using Bernstein polynomial basis and formulate the trajectory generation problem as typical convex programs. By using Bezier curves, we are able to bound positions and higher order dynamics of the trajectory entirely within safe regions. The proposed motion planning method is integrated into a customized light-weight quadrotor platform and is validated by presenting fully autonomous navigation in unknown cluttered indoor and outdoor environments. We also release our code for trajectory generation as an open-source package.
---
paper_title: 3D distance fields: a survey of techniques and applications

paper_content:

A distance field is a representation where, at each point within the field, we know the distance from that point to the closest point on any object within the domain. In addition to distance, other properties may be derived from the distance field, such as the direction to the surface, and when the distance field is signed, we may also determine if the point is internal or external to objects within the domain. The distance field has been found to be a useful construction within the areas of computer vision, physics, and computer graphics. This paper serves as an exposition of methods for the production of distance fields, and a review of alternative representations and applications of distance fields. In the course of this paper, we present various methods from all three of the above areas, and we answer pertinent questions such as How accurate are these methods compared to each other? How simple are they to implement?, and What is the complexity and runtime of such methods?.
---
paper_title: A fast sweeping algorithm for accurate solution of the tilted transversely isotropic eikonal equation using factorization

paper_content:

ABSTRACTTraveltime computation is essential for many seismic data processing applications and velocity analysis tools. High-resolution seismic imaging requires eikonal solvers to account for anisotropy whenever it significantly affects the seismic wave kinematics. Moreover, computation of auxiliary quantities, such as amplitude and take-off angle, relies on highly accurate traveltime solutions. However, the finite-difference-based eikonal solution for a point-source initial condition has upwind source singularity at the source position because the wavefront curvature is large near the source point. Therefore, all finite-difference solvers, even the high-order ones, show inaccuracies because the errors due to source-singularity spread from the source point to the whole computational domain. We address the source-singularity problem for tilted transversely isotropic (TTI) eikonal solvers using factorization. We solve a sequence of factored tilted elliptically anisotropic (TEA) eikonal equations iteratively,...
---
paper_title: Computational Study of Fast Methods for the Eikonal Equation

paper_content:

A computational study of the fast marching and the fast sweeping methods for the eikonal equation is given. It is stressed that both algorithms should be considered as "direct" (as opposed to iterative) methods. On realistic grids, fast sweeping is faster than fast marching for problems with simple geometry. For strongly nonuniform problems and/or complex geometry, the situation may be reversed. Finally, fully second order generalizations of methods of this type for problems with obstacles are proposed and implemented.
---
paper_title: A FAST ITERATIVE METHOD FOR EIKONAL EQUATIONS

paper_content:

In this paper we propose a novel computational technique to solve the Eikonal equation efficiently on parallel architectures. The proposed method manages the list of active nodes and iteratively updates the solutions on those nodes until they converge. Nodes are added to or removed from the list based on a convergence measure, but the management of this list does not entail an extra burden of expensive ordered data structures or special updating sequences. The proposed method has suboptimal worst-case performance but, in practice, on real and synthetic datasets, runs faster than guaranteed-optimal alternatives. Furthermore, the proposed method uses only local, synchronous updates and therefore has better cache coherency, is simple to implement, and scales efficiently on parallel architectures. This paper describes the method, proves its consistency, gives a performance analysis that compares the proposed method against the state-of-the-art Eikonal solvers, and describes the implementation on a single instruction multiple datastream (SIMD) parallel architecture.
---
paper_title: O(N) Implementation of the Fast Marching Algorithm

paper_content:

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.
---
paper_title: Computer-aided renal cancer quantification and classification from contrast-enhanced CT via histograms of curvature-related features

paper_content:

In clinical practice, renal cancer diagnosis is performed by manual quantifications of tumor size and enhancement, which are time consuming and show high variability. We propose a computer-assisted clinical tool to assess and classify renal tumors in contrast-enhanced CT for the management and classification of kidney tumors. The quantification of lesions used level-sets and a statistical refinement step to adapt to the shape of the lesions. Intra-patient and inter-phase registration facilitated the study of lesion enhancement. From the segmented lesions, the histograms of curvature-related features were used to classify the lesion types via random sampling. The clinical tool allows the accurate quantification and classification of cysts and cancer from clinical data. Cancer types are further classified into four categories. Computer-assisted image analysis shows great potential for tumor diagnosis and monitoring.
---
paper_title: A comparison of Fast Marching, Fast Sweeping and Fast Iterative Methods for the solution of the eikonal equation

paper_content:

We compare the computational performance of the Fast Marching Method, the Fast Sweeping Method and of the Fast Iterative Method to determine a numerical solution to the eikonal equation. We point out how the FIM outperforms the other two thanks to its parallel processing capabilities.
---
paper_title: Fast methods for the Eikonal and related Hamilton- Jacobi equations on unstructured meshes.

paper_content:

The Fast Marching Method is a numerical algorithm for solving the Eikonal equation on a rectangular orthogonal mesh in O(M log M) steps, where M is the total number of grid points. The scheme relies on an upwind finite difference approximation to the gradient and a resulting causality relationship that lends itself to a Dijkstra-like programming approach. In this paper, we discuss several extensions to this technique, including higher order versions on unstructured meshes in Rn and on manifolds and connections to more general static Hamilton-Jacobi equations.
---
paper_title: Efficient algorithms for globally optimal trajectories

paper_content:

Presents serial and parallel algorithms for solving a system of equations that arises from the discretization of the Hamilton-Jacobi equation associated to a trajectory optimization problem of the following type. A vehicle starts at a prespecified point x/sub 0/ and follows a unit speed trajectory x(t) inside a region in /spl Rfr//sup m/, until an unspecified time T that the region is excited. A trajectory minimising a cost function of the form /spl int//sub 0//sup T/ r(x(t))dt+q(x(T)) is sought. The discretized Hamilton-Jacobi equation corresponding to this problem is usually served using iterative methods. Nevertheless, assuming that the function r is positive, one is able to exploit the problem structure and develop one-pass algorithms for the discretized problem. The first m resembles Dijkstra's shortest path algorithm and runs in time O(n log n), where n is the number of grid points. The second algorithm uses a somewhat different discretization and borrows some ideas from Dial's shortest path algorithm; it runs in time O(n), which is the best possible, under some fairly mild assumptions. Finally, the author shows that the latter algorithm can be efficiently parallelized: for two-dimensional problems and with p processors, its running time becomes O(n/p), provided that p=O(/spl radic/n/log n). >
---
paper_title: Full waveform inversion guided by travel time tomography

paper_content:

Full waveform inversion (FWI) is a process in which seismic data in time or frequency domain is fit by changing the velocity of the media under investigation. The problem is non-linear, and therefore optimization techniques have been used to find a geological solution to the problem. The main problem in fitting the data is the lack of low spatial frequencies. This deficiency often leads to a local minimum and to non-geologic solutions. In this work we explore how to obtain low frequency information for FWI. Our approach involves augmenting FWI with travel time tomography, which has low-frequency features. By jointly inverting these two problems we enrich FWI with information that can replace low frequency data. In addition, we use high order regularization in a preliminary inversion stage to prevent high frequency features from polluting our model in the initial stages of the reconstruction. This regularization also promote the low-frequencies non-dominant modes that exist in the FWI sensitivity. By applying a smoothly regularized joint inversion we are able to obtain a smooth model than can later be used to recover a good approximation for the true model. A second contribution of this paper involves the acceleration of the main computational bottleneck in FWI--the solution of the Helmholtz equation. We show that the solution time can be significantly reduced by solving the equation for multiple right hand sides using block multigrid preconditioned Krylov methods.
---
paper_title: Concurrent Segmentation and Recognition with Shape-Driven Fast Marching Methods

paper_content:

We present a variational framework that integrates the statistical boundary shape models into a Level Set system that is capable of both segmenting and recognizing objects. Since we aim to recognize objects, we trace the active contour and stop it near real object boundaries while inspecting the shape of the contour instead of enforcing the contour to get a priori shape. We get the location of character boundaries and character labels at the system output. We developed a promising local front stopping scheme based on both image and shape information for fast marching systems. A new object boundary shape signature model, based on directional Gauss gradient filter responses, is also proposed. The character recognition system that employs the new boundary shape descriptor outperforms the other systems, based on well-known boundary signatures such as centroid distance, curvature etc.
---
paper_title: Some Improvements for the Fast Sweeping Method

paper_content:

In this paper, we outline two improvements to the fast sweeping method to improve the speed of the method in general and more specifically in cases where the speed is changing rapidly. The conventional wisdom is that fast sweeping works best when the speed changes slowly, and fast marching is the algorithm of choice when the speed changes rapidly. The goal here is to achieve run times for the fast sweeping method that are at least as fast, or faster, than competitive methods, e.g. fast marching, in the case where the speed is changing rapidly. The first improvement, which we call the locking method, dynamically keeps track of grid points that have either already had the solution successfully calculated at that grid point or for which the solution cannot be successfully calculated during the current iteration. These locked points can quickly be skipped over during the fast sweeping iterations, avoiding many time-consuming calculations. The second improvement, which we call the two queue method, keeps all of the unlocked points in a data structure so that the locked points no longer need to be visited at all. Unfortunately, it is not possible to insert new points into the data structure while maintaining the fast sweeping ordering without at least occasionally sorting. Instead, we segregate the grid points into those with small predicted solutions and those with large predicted solutions using two queues. We give two ways of performing this segregation. This method is a label correcting (iterative) method like the fast sweeping method, but it tends to operate near the front like the fast marching method. It is reminiscent of the threshold method for finding the shortest path on a network, [F. Glover, D. Klingman, and N. Phillips, Oper. Res., 33 (1985), pp. 65-73]. We demonstrate the numerical efficiency of the improved methods on a number of examples.
---
paper_title: A new ray tracing technique for crosshole radar traveltime tomography based on multistencils fast marching method and the steepest descend method

paper_content:

We presented a new ray tracing technique which is applicable for crosshole radar traveltime tomography. The new algorithm divides the ray tracing process into two steps: First the wavefront propagation times of all grid points in a velocity field are calculated using the multistencils fast marching method (MSFM), and then the ray tracing paths having the minimum traveltime can be easily obtained by following the steepest gradient direction from the receiver to the transmitter. In contrast to traditional fast marching method (FMM) and higher accuracy fast marching method (HAFMM), MSFM algorithm calculates traveltimes using two stencils at the same time, and the information in diagonal direction can be included, thus the calculation accuracy and efficiency can be improved greatly. In order to verify the accuracy and efficiency of the new ray tracing method, we test the proposed scheme on two synthetic velocity models where the exact solutions can be calculated, and we compared our results with the one obtained by a FMM based and a HAFMM based steepest descend ray tracing methods. This comparison indicated that the suggested ray tracing technique can achieve much better results both on accuracy and efficiency compared to the FMM based and the HAFMM based steepest descend ray tracing methods.
---
paper_title: Fast sweeping method for the factored eikonal equation

paper_content:

We develop a fast sweeping method for the factored eikonal equation. By decomposing the solution of a general eikonal equation as the product of two factors: the first factor is the solution to a simple eikonal equation (such as distance) or a previously computed solution to an approximate eikonal equation. The second factor is a necessary modification/correction. Appropriate discretization and a fast sweeping strategy are designed for the equation of the correction part. The key idea is to enforce the causality of the original eikonal equation during the Gauss-Seidel iterations. Using extensive numerical examples we demonstrate that (1) the convergence behavior of the fast sweeping method for the factored eikonal equation is the same as for the original eikonal equation, i.e., the number of iterations for the Gauss-Seidel iterations is independent of the mesh size, (2) the numerical solution from the factored eikonal equation is more accurate than the numerical solution directly computed from the original eikonal equation, especially for point sources.
---
paper_title: Can local single-pass methods solve any stationary Hamilton-Jacobi-Bellman equation?

paper_content:

The use of local single-pass methods (like, e.g., the Fast Marching method) has become popular in the solution of some Hamilton-Jacobi equations. The prototype of these equations is the eikonal equation, for which the methods can be applied saving CPU time and possibly memory allocation. Then, some natural questions arise: can local single-pass methods solve any Hamilton- Jacobi equation? If not, where the limit should be set? This paper tries to answer these questions. In order to give a complete picture, we present an overview of some fast methods available in literature and we briey analyze their main features. We also introduce some numerical tools and provide several numerical tests which are intended to exhibit the limitations of the methods. We show that the construction of a local single-pass method for general Hamilton-Jacobi equations is very hard, if not impossible. Nevertheless, some special classes of problems can be actually solved, making local single-pass methods very useful from the practical point of view. games, and it has a great impact in many areas, such as robotics, aeronautics, electrical and aerospace engineering. In particular, for control/game problems, an approximation of the value function allows for the synthesis of optimal control laws in feedback form, and then for the computation of optimal trajectories. The value function for a control problem (resp., dierential game) can be characterized as the unique viscosity solution of the corresponding Hamilton-Jacobi-Bellman (HJB) equation (resp., Hamilton-Jacobi-Isaacs (HJI) equation), and it is obtained by passing to the limit in the well known Bellman's Dynamic Programming (DP) principle. The DP approach can be rather expensive from the computational point of view, but in some situations it gives a real advantage when compared to methods based on the Pontryagin's Maximum Principle, because the latter approach allows one to compute only open-loop controls and locally-optimal trajectories. Moreover, weak solutions to HJ equations are nowadays well understood in the framework of viscosity solutions, which oers the correct notion of solution for many applied problems.
---
paper_title: A parallel fast sweeping method for the Eikonal equation

paper_content:

We present an algorithm for solving in parallel the Eikonal equation. The efficiency of our approach is rooted in the ordering and distribution of the grid points on the available processors; we utilize a Cuthill-McKee ordering. The advantages of our approach is that (1) the efficiency does not plateau for a large number of threads; we compare our approach to the current state-of-the-art parallel implementation of Zhao (2007) [14] and (2) the total number of iterations needed for convergence is the same as that of a sequential implementation, i.e. our parallel implementation does not increase the complexity of the underlying sequential algorithm. Numerical examples are used to illustrate the efficiency of our approach.
---
paper_title: A fast marching algorithm for the factored eikonal equation

paper_content:

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. However, when used for a point source, the original eikonal equation is known to yield inaccurate numerical solutions, because of a singularity at the source. In this case, the factored eikonal equation is often preferred, and is known to yield a more accurate numerical solution. One application that requires the solution of the eikonal equation for point sources is travel time tomography. This inverse problem may be formulated using the eikonal equation as a forward problem. While this problem has been solved using FS in the past, the more recent choice for applying it involves FM methods because of the efficiency in which sensitivities can be obtained using them. However, while several FS methods are available for solving the factored equation, the FM method is available only for the original eikonal equation.In this paper we develop a Fast Marching algorithm for the factored eikonal equation, using both first and second order finite-difference schemes. Our algorithm follows the same lines as the original FM algorithm and requires the same computational effort. In addition, we show how to obtain sensitivities using this FM method and apply travel time tomography, formulated as an inverse factored eikonal equation. Numerical results in two and three dimensions show that our algorithm solves the factored eikonal equation efficiently, and demonstrate the achieved accuracy for computing the travel time. We also demonstrate a recovery of a 2D and 3D heterogeneous medium by travel time tomography using the eikonal equation for forward modeling and inversion by Gauss-Newton.
---
paper_title: 3-D imaging using higher order fast marching traveltimes

paper_content:

Recently, fast marching methods (FMM) beyond first order have been developed for producing rapid solutions to the eikonal equation. In this paper, we present imaging results for 3‐D prestack Kirchhoff migration using traveltimes computed using the first‐order and second‐order FMM on several 3‐D prestack synthetic and real data sets. The second order traveltimes produce a much better image of the structure. Moreover, insufficiently sampled first order traveltimes can introduce consistent errors in the common reflection point gathers that affect velocity analysis. First‐order traveltimes tend to be smaller than analytic traveltimes, which in turn affects the migration velocity analysis, falsely indicating that the interval velocity was too low.
---
paper_title: Efficient algorithms for globally optimal trajectories

paper_content:

Presents serial and parallel algorithms for solving a system of equations that arises from the discretization of the Hamilton-Jacobi equation associated to a trajectory optimization problem of the following type. A vehicle starts at a prespecified point x/sub 0/ and follows a unit speed trajectory x(t) inside a region in /spl Rfr//sup m/, until an unspecified time T that the region is excited. A trajectory minimising a cost function of the form /spl int//sub 0//sup T/ r(x(t))dt+q(x(T)) is sought. The discretized Hamilton-Jacobi equation corresponding to this problem is usually served using iterative methods. Nevertheless, assuming that the function r is positive, one is able to exploit the problem structure and develop one-pass algorithms for the discretized problem. The first m resembles Dijkstra's shortest path algorithm and runs in time O(n log n), where n is the number of grid points. The second algorithm uses a somewhat different discretization and borrows some ideas from Dial's shortest path algorithm; it runs in time O(n), which is the best possible, under some fairly mild assumptions. Finally, the author shows that the latter algorithm can be efficiently parallelized: for two-dimensional problems and with p processors, its running time becomes O(n/p), provided that p=O(/spl radic/n/log n). >
---
paper_title: A fast marching level set method for monotonically advancing fronts.

paper_content:

Abstract ::: A fast marching level set method is presented for monotonically advancing fronts, which leads to an extremely fast scheme for solving the Eikonal equation. Level set methods are numerical techniques for computing the position of propagating fronts. They rely on an initial value partial differential equation for a propagating level set function and use techniques borrowed from hyperbolic conservation laws. Topological changes, corner and cusp development, and accurate determination of geometric properties such as curvature and normal direction are naturally obtained in this setting. This paper describes a particular case of such methods for interfaces whose speed depends only on local position. The technique works by coupling work on entropy conditions for interface motion, the theory of viscosity solutions for Hamilton-Jacobi equations, and fast adaptive narrow band level set methods. The technique is applicable to a variety of problems, including shape-from-shading problems, lithographic development calculations in microchip manufacturing, and arrival time problems in control theory.
---
paper_title: A FAST SWEEPING METHOD FOR EIKONAL EQUATIONS

paper_content:

In this paper a fast sweeping method for computing the numerical solution of Eikonal equations on a rectangular grid is presented. The method is an iterative method which uses upwind difference for discretization and uses Gauss-Seidel iterations with alternating sweeping ordering to solve the discretized system. The crucial idea is that each sweeping ordering follows a family of characteristics of the corresponding Eikonal equation in a certain direction simultaneously. The method has an optimal complexity of O(N) for N grid points and is extremely simple to implement in any number of dimensions. Monotonicity and stability properties of the fast sweeping algorithm are proven. Convergence and error estimates of the algorithm for computing the distance function is studied in detail. It is shown that 2 n Gauss-Seidel iterations is enough for the distance function in n dimensions. An estimation of the number of iterations for general Eikonal equations is also studied. Numerical examples are used to verify the analysis.
---
paper_title: Fronts propagating with curvature dependent speed: algorithms based on Hamilton–Jacobi formulations

paper_content:

We devise new numerical algorithms, called PSC algorithms, for following fronts propagating with curvature-dependent speed. The speed may be an arbitrary function of curvature, and the front also can be passively advected by an underlying flow. These algorithms approximate the equations of motion, which resemble Hamilton-Jacobi equations with parabolic right-hand sides, by using techniques from hyperbolic conservation laws. Non-oscillatory schemes of various orders of accuracy are used to solve the equations, providing methods that accurately capture the formation of sharp gradients and cusps in the moving fronts. The algorithms handle topological merging and breaking naturally, work in any number of space dimensions, and do not require that the moving surface be written as a function. The methods can be also used for more general Hamilton-Jacobi-type problems. We demonstrate our algorithms by computing the solution to a variety of surface motion problems.
---
paper_title: Path Planning for Autonomous Underwater Vehicles

paper_content:

Efficient path-planning algorithms are a crucial issue for modern autonomous underwater vehicles. Classical path-planning algorithms in artificial intelligence are not designed to deal with wide continuous environments prone to currents. We present a novel Fast Marching (FM)-based approach to address the following issues. First, we develop an algorithm we call FM* to efficiently extract a 2-D continuous path from a discrete representation of the environment. Second, we take underwater currents into account thanks to an anisotropic extension of the original FM algorithm. Third, the vehicle turning radius is introduced as a constraint on the optimal path curvature for both isotropic and anisotropic media. Finally, a multiresolution method is introduced to speed up the overall path-planning process
---
paper_title: Concurrent Segmentation and Recognition with Shape-Driven Fast Marching Methods

paper_content:

We present a variational framework that integrates the statistical boundary shape models into a Level Set system that is capable of both segmenting and recognizing objects. Since we aim to recognize objects, we trace the active contour and stop it near real object boundaries while inspecting the shape of the contour instead of enforcing the contour to get a priori shape. We get the location of character boundaries and character labels at the system output. We developed a promising local front stopping scheme based on both image and shape information for fast marching systems. A new object boundary shape signature model, based on directional Gauss gradient filter responses, is also proposed. The character recognition system that employs the new boundary shape descriptor outperforms the other systems, based on well-known boundary signatures such as centroid distance, curvature etc.
---
paper_title: Comparison of active contour and fast marching methods of hippocampus segmentation

paper_content:

The hippocampus is a part of the limbic system and plays an important role in long-term memory and spatial navigation. As part of hippocampal imaging studies, the region of the hippocampus is usually segmented manually, which is a time-consuming process. Here, we describe a comparison of the active contour model (ACM) and the fast marching method (FMM) using magnetic resonance (MR) images of the human brain. We determine optimized input parameters for both models to segment the hippocampus using T1-weighted MR images, and we found that the ACM provided superior performance compared with the FMM without significant additional computational expense.
---
paper_title: A fast marching level set method for monotonically advancing fronts.

paper_content:

Abstract ::: A fast marching level set method is presented for monotonically advancing fronts, which leads to an extremely fast scheme for solving the Eikonal equation. Level set methods are numerical techniques for computing the position of propagating fronts. They rely on an initial value partial differential equation for a propagating level set function and use techniques borrowed from hyperbolic conservation laws. Topological changes, corner and cusp development, and accurate determination of geometric properties such as curvature and normal direction are naturally obtained in this setting. This paper describes a particular case of such methods for interfaces whose speed depends only on local position. The technique works by coupling work on entropy conditions for interface motion, the theory of viscosity solutions for Hamilton-Jacobi equations, and fast adaptive narrow band level set methods. The technique is applicable to a variety of problems, including shape-from-shading problems, lithographic development calculations in microchip manufacturing, and arrival time problems in control theory.
---
paper_title: VDB: High-resolution sparse volumes with dynamic topology

paper_content:

We have developed a novel hierarchical data structure for the efficient representation of sparse, time-varying volumetric data discretized on a 3D grid. Our “VDB”, so named because it is a Volumetric, Dynamic grid that shares several characteristics with Bptrees, exploits spatial coherency of time-varying data to separately and compactly encode data values and grid topology. VDB models a virtually infinite 3D index space that allows for cache-coherent and fast data access into sparse volumes of high resolution. It imposes no topology restrictions on the sparsity of the volumetric data, and it supports fast (average O(1)) random access patterns when the data are inserted, retrieved, or deleted. This is in contrast to most existing sparse volumetric data structures, which assume either static or manifold topology and require specific data access patterns to compensate for slow random access. Since the VDB data structure is fundamentally hierarchical, it also facilitates adaptive grid sampling, and the inherent acceleration structure leads to fast algorithms that are well-suited for simulations. As such, VDB has proven useful for several applications that call for large, sparse, animated volumes, for example, level set dynamics and cloud modeling. In this article, we showcase some of these algorithms and compare VDB with existing, state-of-the-art data structures.
---
paper_title: Generalized fast marching method: applications to image segmentation

paper_content:

In this paper, we propose a segmentation method based on the generalized fast marching method (GFMM) developed by Carlini et al. (submitted). The classical fast marching method (FMM) is a very efficient method for front evolution problems with normal velocity (see also Epstein and Gage, The curve shortening flow. In: Chorin, A., Majda, A. (eds.) Wave Motion: Theory, Modelling and Computation, 1997) of constant sign. The GFMM is an extension of the FMM and removes this sign constraint by authorizing time-dependent velocity with no restriction on the sign. In our modelling, the velocity is borrowed from the Chan–Vese model for segmentation (Chan and Vese, IEEE Trans Image Process 10(2):266–277, 2001). The algorithm is presented and analyzed and some numerical experiments are given, showing in particular that the constraints in the initialization stage can be weakened and that the GFMM offers a powerful and computationally efficient algorithm.
---
paper_title: Reconstructing neuronal morphology from microscopy stacks using fast marching

paper_content:

Automated algorithms to build accurate models of 3D neuronal arborization is much in demand due to large volume of microscopy data. We present a tracking algorithm for automatic and reliable extraction of neuronal morphology. It is robust to ambiguous branch discontinuities, variability of intensity and curvature of fibres, arbitrary branch cross-sections, noise and irregular background illumination. We complete the presentation of our method with demonstration of its performance on synthetic data modeling challenging scenarios and on confocal microscopy data of Olfactory Projection fibres from DIADEM data set with promising results.
---
paper_title: Online Safe Trajectory Generation for Quadrotors Using Fast Marching Method and Bernstein Basis Polynomial

paper_content:

In this paper, we propose a framework for online quadrotor motion planning for autonomous navigation in unknown environments. Based on the onboard state estimation and environment perception, we adopt a fast marching-based path searching method to find a path on a velocity field induced by the Euclidean signed distance field (ESDF) of the map, to achieve better time allocation. We generate a flight corridor for the quadrotor to travel through by inflating the path against the environment. We represent the trajectory as piecewise Bezier curves by using Bernstein polynomial basis and formulate the trajectory generation problem as typical convex programs. By using Bezier curves, we are able to bound positions and higher order dynamics of the trajectory entirely within safe regions. The proposed motion planning method is integrated into a customized light-weight quadrotor platform and is validated by presenting fully autonomous navigation in unknown cluttered indoor and outdoor environments. We also release our code for trajectory generation as an open-source package.
---
paper_title: Path planning algorithm for unmanned surface vehicle formations in a practical maritime environment

paper_content:

Unmanned surface vehicles (USVs) have been deployed over the past decade. Current USV platforms are generally of small size with low payload capacity and short endurance times. To improve effectiveness there is a trend to deploy multiple USVs as a formation fleet. This paper presents a novel computer based algorithm that solves the problem of USV formation path planning. The algorithm is based upon the fast marching (FM) method and has been specifically designed for operation in dynamic environments using the novel constrained FM method. The constrained FM method is able to model the dynamic behaviour of moving ships with efficient computation time. The algorithm has been evaluated using a range of tests applied to a simulated area and has been proved to work effectively in a complex navigation environment.
---
paper_title: Concurrent Segmentation and Recognition with Shape-Driven Fast Marching Methods

paper_content:

We present a variational framework that integrates the statistical boundary shape models into a Level Set system that is capable of both segmenting and recognizing objects. Since we aim to recognize objects, we trace the active contour and stop it near real object boundaries while inspecting the shape of the contour instead of enforcing the contour to get a priori shape. We get the location of character boundaries and character labels at the system output. We developed a promising local front stopping scheme based on both image and shape information for fast marching systems. A new object boundary shape signature model, based on directional Gauss gradient filter responses, is also proposed. The character recognition system that employs the new boundary shape descriptor outperforms the other systems, based on well-known boundary signatures such as centroid distance, curvature etc.
---
paper_title: Online Safe Trajectory Generation for Quadrotors Using Fast Marching Method and Bernstein Basis Polynomial

paper_content:

In this paper, we propose a framework for online quadrotor motion planning for autonomous navigation in unknown environments. Based on the onboard state estimation and environment perception, we adopt a fast marching-based path searching method to find a path on a velocity field induced by the Euclidean signed distance field (ESDF) of the map, to achieve better time allocation. We generate a flight corridor for the quadrotor to travel through by inflating the path against the environment. We represent the trajectory as piecewise Bezier curves by using Bernstein polynomial basis and formulate the trajectory generation problem as typical convex programs. By using Bezier curves, we are able to bound positions and higher order dynamics of the trajectory entirely within safe regions. The proposed motion planning method is integrated into a customized light-weight quadrotor platform and is validated by presenting fully autonomous navigation in unknown cluttered indoor and outdoor environments. We also release our code for trajectory generation as an open-source package.
---
paper_title: Path planning algorithm for unmanned surface vehicle formations in a practical maritime environment

paper_content:

Unmanned surface vehicles (USVs) have been deployed over the past decade. Current USV platforms are generally of small size with low payload capacity and short endurance times. To improve effectiveness there is a trend to deploy multiple USVs as a formation fleet. This paper presents a novel computer based algorithm that solves the problem of USV formation path planning. The algorithm is based upon the fast marching (FM) method and has been specifically designed for operation in dynamic environments using the novel constrained FM method. The constrained FM method is able to model the dynamic behaviour of moving ships with efficient computation time. The algorithm has been evaluated using a range of tests applied to a simulated area and has been proved to work effectively in a complex navigation environment.
---
paper_title: VDB: High-resolution sparse volumes with dynamic topology

paper_content:

We have developed a novel hierarchical data structure for the efficient representation of sparse, time-varying volumetric data discretized on a 3D grid. Our “VDB”, so named because it is a Volumetric, Dynamic grid that shares several characteristics with Bptrees, exploits spatial coherency of time-varying data to separately and compactly encode data values and grid topology. VDB models a virtually infinite 3D index space that allows for cache-coherent and fast data access into sparse volumes of high resolution. It imposes no topology restrictions on the sparsity of the volumetric data, and it supports fast (average O(1)) random access patterns when the data are inserted, retrieved, or deleted. This is in contrast to most existing sparse volumetric data structures, which assume either static or manifold topology and require specific data access patterns to compensate for slow random access. Since the VDB data structure is fundamentally hierarchical, it also facilitates adaptive grid sampling, and the inherent acceleration structure leads to fast algorithms that are well-suited for simulations. As such, VDB has proven useful for several applications that call for large, sparse, animated volumes, for example, level set dynamics and cloud modeling. In this article, we showcase some of these algorithms and compare VDB with existing, state-of-the-art data structures.
---
paper_title: 3D distance fields: a survey of techniques and applications

paper_content:

A distance field is a representation where, at each point within the field, we know the distance from that point to the closest point on any object within the domain. In addition to distance, other properties may be derived from the distance field, such as the direction to the surface, and when the distance field is signed, we may also determine if the point is internal or external to objects within the domain. The distance field has been found to be a useful construction within the areas of computer vision, physics, and computer graphics. This paper serves as an exposition of methods for the production of distance fields, and a review of alternative representations and applications of distance fields. In the course of this paper, we present various methods from all three of the above areas, and we answer pertinent questions such as How accurate are these methods compared to each other? How simple are they to implement?, and What is the complexity and runtime of such methods?.
---
paper_title: Concurrent Segmentation and Recognition with Shape-Driven Fast Marching Methods

paper_content:

We present a variational framework that integrates the statistical boundary shape models into a Level Set system that is capable of both segmenting and recognizing objects. Since we aim to recognize objects, we trace the active contour and stop it near real object boundaries while inspecting the shape of the contour instead of enforcing the contour to get a priori shape. We get the location of character boundaries and character labels at the system output. We developed a promising local front stopping scheme based on both image and shape information for fast marching systems. A new object boundary shape signature model, based on directional Gauss gradient filter responses, is also proposed. The character recognition system that employs the new boundary shape descriptor outperforms the other systems, based on well-known boundary signatures such as centroid distance, curvature etc.
---
paper_title: A new ray tracing technique for crosshole radar traveltime tomography based on multistencils fast marching method and the steepest descend method

paper_content:

We presented a new ray tracing technique which is applicable for crosshole radar traveltime tomography. The new algorithm divides the ray tracing process into two steps: First the wavefront propagation times of all grid points in a velocity field are calculated using the multistencils fast marching method (MSFM), and then the ray tracing paths having the minimum traveltime can be easily obtained by following the steepest gradient direction from the receiver to the transmitter. In contrast to traditional fast marching method (FMM) and higher accuracy fast marching method (HAFMM), MSFM algorithm calculates traveltimes using two stencils at the same time, and the information in diagonal direction can be included, thus the calculation accuracy and efficiency can be improved greatly. In order to verify the accuracy and efficiency of the new ray tracing method, we test the proposed scheme on two synthetic velocity models where the exact solutions can be calculated, and we compared our results with the one obtained by a FMM based and a HAFMM based steepest descend ray tracing methods. This comparison indicated that the suggested ray tracing technique can achieve much better results both on accuracy and efficiency compared to the FMM based and the HAFMM based steepest descend ray tracing methods.
---
paper_title: Full waveform inversion guided by travel time tomography

paper_content:

Full waveform inversion (FWI) is a process in which seismic data in time or frequency domain is fit by changing the velocity of the media under investigation. The problem is non-linear, and therefore optimization techniques have been used to find a geological solution to the problem. The main problem in fitting the data is the lack of low spatial frequencies. This deficiency often leads to a local minimum and to non-geologic solutions. In this work we explore how to obtain low frequency information for FWI. Our approach involves augmenting FWI with travel time tomography, which has low-frequency features. By jointly inverting these two problems we enrich FWI with information that can replace low frequency data. In addition, we use high order regularization in a preliminary inversion stage to prevent high frequency features from polluting our model in the initial stages of the reconstruction. This regularization also promote the low-frequencies non-dominant modes that exist in the FWI sensitivity. By applying a smoothly regularized joint inversion we are able to obtain a smooth model than can later be used to recover a good approximation for the true model. A second contribution of this paper involves the acceleration of the main computational bottleneck in FWI--the solution of the Helmholtz equation. We show that the solution time can be significantly reduced by solving the equation for multiple right hand sides using block multigrid preconditioned Krylov methods.
---
paper_title: Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms

paper_content:

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in 0(log n) amortized time and all other standard heap operations in 0(1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms.
---
paper_title: Random insertion into a priority queue structure

paper_content:

The average number of levels that a new element moves up when inserted into a heap is investigated. Two probabilistic models under which such an average might be computed are proposed. A `Lemma of Conservation of Ignorance' is formulated and used in the derivation of an exact formula for the average in one of these models. It is shown that this average is bounded by a constant and its asymptotic behaviour is discussed. Numerical data for the second model are also provided and analyzed.
---
paper_title: 3D distance fields: a survey of techniques and applications

paper_content:

A distance field is a representation where, at each point within the field, we know the distance from that point to the closest point on any object within the domain. In addition to distance, other properties may be derived from the distance field, such as the direction to the surface, and when the distance field is signed, we may also determine if the point is internal or external to objects within the domain. The distance field has been found to be a useful construction within the areas of computer vision, physics, and computer graphics. This paper serves as an exposition of methods for the production of distance fields, and a review of alternative representations and applications of distance fields. In the course of this paper, we present various methods from all three of the above areas, and we answer pertinent questions such as How accurate are these methods compared to each other? How simple are they to implement?, and What is the complexity and runtime of such methods?.
---
paper_title: A FAST SWEEPING METHOD FOR EIKONAL EQUATIONS

paper_content:

In this paper a fast sweeping method for computing the numerical solution of Eikonal equations on a rectangular grid is presented. The method is an iterative method which uses upwind difference for discretization and uses Gauss-Seidel iterations with alternating sweeping ordering to solve the discretized system. The crucial idea is that each sweeping ordering follows a family of characteristics of the corresponding Eikonal equation in a certain direction simultaneously. The method has an optimal complexity of O(N) for N grid points and is extremely simple to implement in any number of dimensions. Monotonicity and stability properties of the fast sweeping algorithm are proven. Convergence and error estimates of the algorithm for computing the distance function is studied in detail. It is shown that 2 n Gauss-Seidel iterations is enough for the distance function in n dimensions. An estimation of the number of iterations for general Eikonal equations is also studied. Numerical examples are used to verify the analysis.
---
paper_title: Generalized fast marching method: applications to image segmentation

paper_content:

In this paper, we propose a segmentation method based on the generalized fast marching method (GFMM) developed by Carlini et al. (submitted). The classical fast marching method (FMM) is a very efficient method for front evolution problems with normal velocity (see also Epstein and Gage, The curve shortening flow. In: Chorin, A., Majda, A. (eds.) Wave Motion: Theory, Modelling and Computation, 1997) of constant sign. The GFMM is an extension of the FMM and removes this sign constraint by authorizing time-dependent velocity with no restriction on the sign. In our modelling, the velocity is borrowed from the Chan–Vese model for segmentation (Chan and Vese, IEEE Trans Image Process 10(2):266–277, 2001). The algorithm is presented and analyzed and some numerical experiments are given, showing in particular that the constraints in the initialization stage can be weakened and that the GFMM offers a powerful and computationally efficient algorithm.
---
paper_title: Remarks on the O(N) implementation of the fast marching method

paper_content:

The fast marching algorithm computes an approximate solution to the eikonal equation in O(N log N) time, where the factor log N is due to the administration of a priority queue. Recently, Yatziv, Bartesaghi and Sapiro have suggested to use an untidy priority queue, reducing the overall complexity to O(N) at the price of a small error in the computed solution. In this paper, we give an explicit estimate of the error introduced, which is based on a discrete comparison principle. This estimates implies in particular that the choice of an accuracy level that is independent of the speed function F results in the complexity bound O(Fmax /Fmin N). A numerical experiment illustrates this robustness problem for large ratios Fmax /Fmin .
---
paper_title: O(N) Implementation of the Fast Marching Algorithm

paper_content:

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.
---
paper_title: Path Planning for Autonomous Underwater Vehicles

paper_content:

Efficient path-planning algorithms are a crucial issue for modern autonomous underwater vehicles. Classical path-planning algorithms in artificial intelligence are not designed to deal with wide continuous environments prone to currents. We present a novel Fast Marching (FM)-based approach to address the following issues. First, we develop an algorithm we call FM* to efficiently extract a 2-D continuous path from a discrete representation of the environment. Second, we take underwater currents into account thanks to an anisotropic extension of the original FM algorithm. Third, the vehicle turning radius is introduced as a constraint on the optimal path curvature for both isotropic and anisotropic media. Finally, a multiresolution method is introduced to speed up the overall path-planning process
---
paper_title: A FAST SWEEPING METHOD FOR EIKONAL EQUATIONS

paper_content:

In this paper a fast sweeping method for computing the numerical solution of Eikonal equations on a rectangular grid is presented. The method is an iterative method which uses upwind difference for discretization and uses Gauss-Seidel iterations with alternating sweeping ordering to solve the discretized system. The crucial idea is that each sweeping ordering follows a family of characteristics of the corresponding Eikonal equation in a certain direction simultaneously. The method has an optimal complexity of O(N) for N grid points and is extremely simple to implement in any number of dimensions. Monotonicity and stability properties of the fast sweeping algorithm are proven. Convergence and error estimates of the algorithm for computing the distance function is studied in detail. It is shown that 2 n Gauss-Seidel iterations is enough for the distance function in n dimensions. An estimation of the number of iterations for general Eikonal equations is also studied. Numerical examples are used to verify the analysis.
---
paper_title: Online Safe Trajectory Generation for Quadrotors Using Fast Marching Method and Bernstein Basis Polynomial

paper_content:

In this paper, we propose a framework for online quadrotor motion planning for autonomous navigation in unknown environments. Based on the onboard state estimation and environment perception, we adopt a fast marching-based path searching method to find a path on a velocity field induced by the Euclidean signed distance field (ESDF) of the map, to achieve better time allocation. We generate a flight corridor for the quadrotor to travel through by inflating the path against the environment. We represent the trajectory as piecewise Bezier curves by using Bernstein polynomial basis and formulate the trajectory generation problem as typical convex programs. By using Bezier curves, we are able to bound positions and higher order dynamics of the trajectory entirely within safe regions. The proposed motion planning method is integrated into a customized light-weight quadrotor platform and is validated by presenting fully autonomous navigation in unknown cluttered indoor and outdoor environments. We also release our code for trajectory generation as an open-source package.
---
paper_title: A fast sweeping algorithm for accurate solution of the tilted transversely isotropic eikonal equation using factorization

paper_content:

ABSTRACTTraveltime computation is essential for many seismic data processing applications and velocity analysis tools. High-resolution seismic imaging requires eikonal solvers to account for anisotropy whenever it significantly affects the seismic wave kinematics. Moreover, computation of auxiliary quantities, such as amplitude and take-off angle, relies on highly accurate traveltime solutions. However, the finite-difference-based eikonal solution for a point-source initial condition has upwind source singularity at the source position because the wavefront curvature is large near the source point. Therefore, all finite-difference solvers, even the high-order ones, show inaccuracies because the errors due to source-singularity spread from the source point to the whole computational domain. We address the source-singularity problem for tilted transversely isotropic (TTI) eikonal solvers using factorization. We solve a sequence of factored tilted elliptically anisotropic (TEA) eikonal equations iteratively,...
---
paper_title: Path planning algorithm for unmanned surface vehicle formations in a practical maritime environment

paper_content:

Unmanned surface vehicles (USVs) have been deployed over the past decade. Current USV platforms are generally of small size with low payload capacity and short endurance times. To improve effectiveness there is a trend to deploy multiple USVs as a formation fleet. This paper presents a novel computer based algorithm that solves the problem of USV formation path planning. The algorithm is based upon the fast marching (FM) method and has been specifically designed for operation in dynamic environments using the novel constrained FM method. The constrained FM method is able to model the dynamic behaviour of moving ships with efficient computation time. The algorithm has been evaluated using a range of tests applied to a simulated area and has been proved to work effectively in a complex navigation environment.
---
paper_title: Narrow passage path planning using fast marching method and support vector machine

paper_content:

This paper introduces a novel path planning method under non-holonomic constraint for car-like vehicles, which associates map discovery and heuristic search to attain an optimal resultant path. The map discovery applies fast marching method to investigate the map geometric information. After that, the support vector machine is performed to find obstacle clearance information. This information is then used as a heuristic function which helps greatly reduce the search space. The fast marching is performed again, guided by this function to generate vehicle motions under kinematic constraints. Experimental results have shown that this method is able to generate motions for non-holonomic vehicles. In comparison with related methods, the path generated by proposed method is smoother and stay farther away from the obstacles.
---
paper_title: Fast Sweeping Algorithms for a Class of Hamilton-Jacobi Equations

paper_content:

We derive a Godunov-type numerical flux for the class of strictly convex, homogeneous Hamiltonians that includes $H(p,q)=\sqrt{ap^{2}+bq^{2}-2cpq},$ $c^{2}<ab.$ We combine our Godunov numerical fluxes with simple Gauss--Seidel-type iterations for solving the corresponding Hamilton--Jacobi (HJ) equations. The resulting algorithm is fast since it does not require a sorting strategy as found, e.g., in the fast marching method. In addition, it providesa way to compute solutions to a class of HJ equations for which the conventional fast marching method is not applicable. Our experiments indicate convergence after a few iterations, even in rather difficult cases.
---
paper_title: Some Improvements for the Fast Sweeping Method

paper_content:

In this paper, we outline two improvements to the fast sweeping method to improve the speed of the method in general and more specifically in cases where the speed is changing rapidly. The conventional wisdom is that fast sweeping works best when the speed changes slowly, and fast marching is the algorithm of choice when the speed changes rapidly. The goal here is to achieve run times for the fast sweeping method that are at least as fast, or faster, than competitive methods, e.g. fast marching, in the case where the speed is changing rapidly. The first improvement, which we call the locking method, dynamically keeps track of grid points that have either already had the solution successfully calculated at that grid point or for which the solution cannot be successfully calculated during the current iteration. These locked points can quickly be skipped over during the fast sweeping iterations, avoiding many time-consuming calculations. The second improvement, which we call the two queue method, keeps all of the unlocked points in a data structure so that the locked points no longer need to be visited at all. Unfortunately, it is not possible to insert new points into the data structure while maintaining the fast sweeping ordering without at least occasionally sorting. Instead, we segregate the grid points into those with small predicted solutions and those with large predicted solutions using two queues. We give two ways of performing this segregation. This method is a label correcting (iterative) method like the fast sweeping method, but it tends to operate near the front like the fast marching method. It is reminiscent of the threshold method for finding the shortest path on a network, [F. Glover, D. Klingman, and N. Phillips, Oper. Res., 33 (1985), pp. 65-73]. We demonstrate the numerical efficiency of the improved methods on a number of examples.
---
paper_title: Narrow passage path planning using fast marching method and support vector machine

paper_content:

This paper introduces a novel path planning method under non-holonomic constraint for car-like vehicles, which associates map discovery and heuristic search to attain an optimal resultant path. The map discovery applies fast marching method to investigate the map geometric information. After that, the support vector machine is performed to find obstacle clearance information. This information is then used as a heuristic function which helps greatly reduce the search space. The fast marching is performed again, guided by this function to generate vehicle motions under kinematic constraints. Experimental results have shown that this method is able to generate motions for non-holonomic vehicles. In comparison with related methods, the path generated by proposed method is smoother and stay farther away from the obstacles.
---
paper_title: Comparison of active contour and fast marching methods of hippocampus segmentation

paper_content:

The hippocampus is a part of the limbic system and plays an important role in long-term memory and spatial navigation. As part of hippocampal imaging studies, the region of the hippocampus is usually segmented manually, which is a time-consuming process. Here, we describe a comparison of the active contour model (ACM) and the fast marching method (FMM) using magnetic resonance (MR) images of the human brain. We determine optimized input parameters for both models to segment the hippocampus using T1-weighted MR images, and we found that the ACM provided superior performance compared with the FMM without significant additional computational expense.
---
paper_title: VDB: High-resolution sparse volumes with dynamic topology

paper_content:

We have developed a novel hierarchical data structure for the efficient representation of sparse, time-varying volumetric data discretized on a 3D grid. Our “VDB”, so named because it is a Volumetric, Dynamic grid that shares several characteristics with Bptrees, exploits spatial coherency of time-varying data to separately and compactly encode data values and grid topology. VDB models a virtually infinite 3D index space that allows for cache-coherent and fast data access into sparse volumes of high resolution. It imposes no topology restrictions on the sparsity of the volumetric data, and it supports fast (average O(1)) random access patterns when the data are inserted, retrieved, or deleted. This is in contrast to most existing sparse volumetric data structures, which assume either static or manifold topology and require specific data access patterns to compensate for slow random access. Since the VDB data structure is fundamentally hierarchical, it also facilitates adaptive grid sampling, and the inherent acceleration structure leads to fast algorithms that are well-suited for simulations. As such, VDB has proven useful for several applications that call for large, sparse, animated volumes, for example, level set dynamics and cloud modeling. In this article, we showcase some of these algorithms and compare VDB with existing, state-of-the-art data structures.
---
paper_title: Reconstructing neuronal morphology from microscopy stacks using fast marching

paper_content:

Automated algorithms to build accurate models of 3D neuronal arborization is much in demand due to large volume of microscopy data. We present a tracking algorithm for automatic and reliable extraction of neuronal morphology. It is robust to ambiguous branch discontinuities, variability of intensity and curvature of fibres, arbitrary branch cross-sections, noise and irregular background illumination. We complete the presentation of our method with demonstration of its performance on synthetic data modeling challenging scenarios and on confocal microscopy data of Olfactory Projection fibres from DIADEM data set with promising results.
---
paper_title: A FAST ITERATIVE METHOD FOR EIKONAL EQUATIONS

paper_content:

In this paper we propose a novel computational technique to solve the Eikonal equation efficiently on parallel architectures. The proposed method manages the list of active nodes and iteratively updates the solutions on those nodes until they converge. Nodes are added to or removed from the list based on a convergence measure, but the management of this list does not entail an extra burden of expensive ordered data structures or special updating sequences. The proposed method has suboptimal worst-case performance but, in practice, on real and synthetic datasets, runs faster than guaranteed-optimal alternatives. Furthermore, the proposed method uses only local, synchronous updates and therefore has better cache coherency, is simple to implement, and scales efficiently on parallel architectures. This paper describes the method, proves its consistency, gives a performance analysis that compares the proposed method against the state-of-the-art Eikonal solvers, and describes the implementation on a single instruction multiple datastream (SIMD) parallel architecture.
---
paper_title: Computer-aided renal cancer quantification and classification from contrast-enhanced CT via histograms of curvature-related features

paper_content:

In clinical practice, renal cancer diagnosis is performed by manual quantifications of tumor size and enhancement, which are time consuming and show high variability. We propose a computer-assisted clinical tool to assess and classify renal tumors in contrast-enhanced CT for the management and classification of kidney tumors. The quantification of lesions used level-sets and a statistical refinement step to adapt to the shape of the lesions. Intra-patient and inter-phase registration facilitated the study of lesion enhancement. From the segmented lesions, the histograms of curvature-related features were used to classify the lesion types via random sampling. The clinical tool allows the accurate quantification and classification of cysts and cancer from clinical data. Cancer types are further classified into four categories. Computer-assisted image analysis shows great potential for tumor diagnosis and monitoring.
---
paper_title: Path planning algorithm for unmanned surface vehicle formations in a practical maritime environment

paper_content:

Unmanned surface vehicles (USVs) have been deployed over the past decade. Current USV platforms are generally of small size with low payload capacity and short endurance times. To improve effectiveness there is a trend to deploy multiple USVs as a formation fleet. This paper presents a novel computer based algorithm that solves the problem of USV formation path planning. The algorithm is based upon the fast marching (FM) method and has been specifically designed for operation in dynamic environments using the novel constrained FM method. The constrained FM method is able to model the dynamic behaviour of moving ships with efficient computation time. The algorithm has been evaluated using a range of tests applied to a simulated area and has been proved to work effectively in a complex navigation environment.
---
paper_title: Concurrent Segmentation and Recognition with Shape-Driven Fast Marching Methods

paper_content:

We present a variational framework that integrates the statistical boundary shape models into a Level Set system that is capable of both segmenting and recognizing objects. Since we aim to recognize objects, we trace the active contour and stop it near real object boundaries while inspecting the shape of the contour instead of enforcing the contour to get a priori shape. We get the location of character boundaries and character labels at the system output. We developed a promising local front stopping scheme based on both image and shape information for fast marching systems. A new object boundary shape signature model, based on directional Gauss gradient filter responses, is also proposed. The character recognition system that employs the new boundary shape descriptor outperforms the other systems, based on well-known boundary signatures such as centroid distance, curvature etc.
---
paper_title: Narrow passage path planning using fast marching method and support vector machine

paper_content:

This paper introduces a novel path planning method under non-holonomic constraint for car-like vehicles, which associates map discovery and heuristic search to attain an optimal resultant path. The map discovery applies fast marching method to investigate the map geometric information. After that, the support vector machine is performed to find obstacle clearance information. This information is then used as a heuristic function which helps greatly reduce the search space. The fast marching is performed again, guided by this function to generate vehicle motions under kinematic constraints. Experimental results have shown that this method is able to generate motions for non-holonomic vehicles. In comparison with related methods, the path generated by proposed method is smoother and stay farther away from the obstacles.
---
paper_title: Some Improvements for the Fast Sweeping Method

paper_content:

In this paper, we outline two improvements to the fast sweeping method to improve the speed of the method in general and more specifically in cases where the speed is changing rapidly. The conventional wisdom is that fast sweeping works best when the speed changes slowly, and fast marching is the algorithm of choice when the speed changes rapidly. The goal here is to achieve run times for the fast sweeping method that are at least as fast, or faster, than competitive methods, e.g. fast marching, in the case where the speed is changing rapidly. The first improvement, which we call the locking method, dynamically keeps track of grid points that have either already had the solution successfully calculated at that grid point or for which the solution cannot be successfully calculated during the current iteration. These locked points can quickly be skipped over during the fast sweeping iterations, avoiding many time-consuming calculations. The second improvement, which we call the two queue method, keeps all of the unlocked points in a data structure so that the locked points no longer need to be visited at all. Unfortunately, it is not possible to insert new points into the data structure while maintaining the fast sweeping ordering without at least occasionally sorting. Instead, we segregate the grid points into those with small predicted solutions and those with large predicted solutions using two queues. We give two ways of performing this segregation. This method is a label correcting (iterative) method like the fast sweeping method, but it tends to operate near the front like the fast marching method. It is reminiscent of the threshold method for finding the shortest path on a network, [F. Glover, D. Klingman, and N. Phillips, Oper. Res., 33 (1985), pp. 65-73]. We demonstrate the numerical efficiency of the improved methods on a number of examples.
---
paper_title: Computer-aided renal cancer quantification and classification from contrast-enhanced CT via histograms of curvature-related features

paper_content:

In clinical practice, renal cancer diagnosis is performed by manual quantifications of tumor size and enhancement, which are time consuming and show high variability. We propose a computer-assisted clinical tool to assess and classify renal tumors in contrast-enhanced CT for the management and classification of kidney tumors. The quantification of lesions used level-sets and a statistical refinement step to adapt to the shape of the lesions. Intra-patient and inter-phase registration facilitated the study of lesion enhancement. From the segmented lesions, the histograms of curvature-related features were used to classify the lesion types via random sampling. The clinical tool allows the accurate quantification and classification of cysts and cancer from clinical data. Cancer types are further classified into four categories. Computer-assisted image analysis shows great potential for tumor diagnosis and monitoring.
---
paper_title: 3-D imaging using higher order fast marching traveltimes

paper_content:

Recently, fast marching methods (FMM) beyond first order have been developed for producing rapid solutions to the eikonal equation. In this paper, we present imaging results for 3‐D prestack Kirchhoff migration using traveltimes computed using the first‐order and second‐order FMM on several 3‐D prestack synthetic and real data sets. The second order traveltimes produce a much better image of the structure. Moreover, insufficiently sampled first order traveltimes can introduce consistent errors in the common reflection point gathers that affect velocity analysis. First‐order traveltimes tend to be smaller than analytic traveltimes, which in turn affects the migration velocity analysis, falsely indicating that the interval velocity was too low.
---
paper_title: First-break traveltime tomography with the double-square-root eikonal equation

paper_content:

ABSTRACTFirst-break traveltime tomography is based on the eikonal equation. Because the eikonal equation is solved at fixed-shot positions and only receiver positions can move along the raypath, the adjoint-state tomography relies on inversion to resolve possible contradicting information between independent shots. The double-square-root (DSR) eikonal equation allows not only the receivers but also the shots to change position, and thus describes the prestack survey as a whole. Consequently, its linearized tomographic operator naturally handles all shots together, in contrast with the shotwise approach in the traditional eikonal-based framework. The DSR eikonal equation is singular for the horizontal waves, which require special handling. Although it is possible to recover all branches of the solution through postprocessing, our current forward modeling and tomography focuses on the diving wave branch only. We consider two upwind discretizations of the DSR eikonal equation and show that the explicit schem...
---
paper_title: Path Planning for Autonomous Underwater Vehicles

paper_content:

Efficient path-planning algorithms are a crucial issue for modern autonomous underwater vehicles. Classical path-planning algorithms in artificial intelligence are not designed to deal with wide continuous environments prone to currents. We present a novel Fast Marching (FM)-based approach to address the following issues. First, we develop an algorithm we call FM* to efficiently extract a 2-D continuous path from a discrete representation of the environment. Second, we take underwater currents into account thanks to an anisotropic extension of the original FM algorithm. Third, the vehicle turning radius is introduced as a constraint on the optimal path curvature for both isotropic and anisotropic media. Finally, a multiresolution method is introduced to speed up the overall path-planning process
---
paper_title: A fast marching level set method for monotonically advancing fronts.

paper_content:

Abstract ::: A fast marching level set method is presented for monotonically advancing fronts, which leads to an extremely fast scheme for solving the Eikonal equation. Level set methods are numerical techniques for computing the position of propagating fronts. They rely on an initial value partial differential equation for a propagating level set function and use techniques borrowed from hyperbolic conservation laws. Topological changes, corner and cusp development, and accurate determination of geometric properties such as curvature and normal direction are naturally obtained in this setting. This paper describes a particular case of such methods for interfaces whose speed depends only on local position. The technique works by coupling work on entropy conditions for interface motion, the theory of viscosity solutions for Hamilton-Jacobi equations, and fast adaptive narrow band level set methods. The technique is applicable to a variety of problems, including shape-from-shading problems, lithographic development calculations in microchip manufacturing, and arrival time problems in control theory.
---
paper_title: VDB: High-resolution sparse volumes with dynamic topology

paper_content:

We have developed a novel hierarchical data structure for the efficient representation of sparse, time-varying volumetric data discretized on a 3D grid. Our “VDB”, so named because it is a Volumetric, Dynamic grid that shares several characteristics with Bptrees, exploits spatial coherency of time-varying data to separately and compactly encode data values and grid topology. VDB models a virtually infinite 3D index space that allows for cache-coherent and fast data access into sparse volumes of high resolution. It imposes no topology restrictions on the sparsity of the volumetric data, and it supports fast (average O(1)) random access patterns when the data are inserted, retrieved, or deleted. This is in contrast to most existing sparse volumetric data structures, which assume either static or manifold topology and require specific data access patterns to compensate for slow random access. Since the VDB data structure is fundamentally hierarchical, it also facilitates adaptive grid sampling, and the inherent acceleration structure leads to fast algorithms that are well-suited for simulations. As such, VDB has proven useful for several applications that call for large, sparse, animated volumes, for example, level set dynamics and cloud modeling. In this article, we showcase some of these algorithms and compare VDB with existing, state-of-the-art data structures.
---
paper_title: A FAST SWEEPING METHOD FOR EIKONAL EQUATIONS

paper_content:

In this paper a fast sweeping method for computing the numerical solution of Eikonal equations on a rectangular grid is presented. The method is an iterative method which uses upwind difference for discretization and uses Gauss-Seidel iterations with alternating sweeping ordering to solve the discretized system. The crucial idea is that each sweeping ordering follows a family of characteristics of the corresponding Eikonal equation in a certain direction simultaneously. The method has an optimal complexity of O(N) for N grid points and is extremely simple to implement in any number of dimensions. Monotonicity and stability properties of the fast sweeping algorithm are proven. Convergence and error estimates of the algorithm for computing the distance function is studied in detail. It is shown that 2 n Gauss-Seidel iterations is enough for the distance function in n dimensions. An estimation of the number of iterations for general Eikonal equations is also studied. Numerical examples are used to verify the analysis.
---
paper_title: Generalized fast marching method: applications to image segmentation

paper_content:

In this paper, we propose a segmentation method based on the generalized fast marching method (GFMM) developed by Carlini et al. (submitted). The classical fast marching method (FMM) is a very efficient method for front evolution problems with normal velocity (see also Epstein and Gage, The curve shortening flow. In: Chorin, A., Majda, A. (eds.) Wave Motion: Theory, Modelling and Computation, 1997) of constant sign. The GFMM is an extension of the FMM and removes this sign constraint by authorizing time-dependent velocity with no restriction on the sign. In our modelling, the velocity is borrowed from the Chan–Vese model for segmentation (Chan and Vese, IEEE Trans Image Process 10(2):266–277, 2001). The algorithm is presented and analyzed and some numerical experiments are given, showing in particular that the constraints in the initialization stage can be weakened and that the GFMM offers a powerful and computationally efficient algorithm.
---
paper_title: Reconstructing neuronal morphology from microscopy stacks using fast marching

paper_content:

Automated algorithms to build accurate models of 3D neuronal arborization is much in demand due to large volume of microscopy data. We present a tracking algorithm for automatic and reliable extraction of neuronal morphology. It is robust to ambiguous branch discontinuities, variability of intensity and curvature of fibres, arbitrary branch cross-sections, noise and irregular background illumination. We complete the presentation of our method with demonstration of its performance on synthetic data modeling challenging scenarios and on confocal microscopy data of Olfactory Projection fibres from DIADEM data set with promising results.
---
paper_title: Online Safe Trajectory Generation for Quadrotors Using Fast Marching Method and Bernstein Basis Polynomial

paper_content:

In this paper, we propose a framework for online quadrotor motion planning for autonomous navigation in unknown environments. Based on the onboard state estimation and environment perception, we adopt a fast marching-based path searching method to find a path on a velocity field induced by the Euclidean signed distance field (ESDF) of the map, to achieve better time allocation. We generate a flight corridor for the quadrotor to travel through by inflating the path against the environment. We represent the trajectory as piecewise Bezier curves by using Bernstein polynomial basis and formulate the trajectory generation problem as typical convex programs. By using Bezier curves, we are able to bound positions and higher order dynamics of the trajectory entirely within safe regions. The proposed motion planning method is integrated into a customized light-weight quadrotor platform and is validated by presenting fully autonomous navigation in unknown cluttered indoor and outdoor environments. We also release our code for trajectory generation as an open-source package.
---
paper_title: Computational Study of Fast Methods for the Eikonal Equation

paper_content:

A computational study of the fast marching and the fast sweeping methods for the eikonal equation is given. It is stressed that both algorithms should be considered as "direct" (as opposed to iterative) methods. On realistic grids, fast sweeping is faster than fast marching for problems with simple geometry. For strongly nonuniform problems and/or complex geometry, the situation may be reversed. Finally, fully second order generalizations of methods of this type for problems with obstacles are proposed and implemented.
---
paper_title: Computer-aided renal cancer quantification and classification from contrast-enhanced CT via histograms of curvature-related features

paper_content:

In clinical practice, renal cancer diagnosis is performed by manual quantifications of tumor size and enhancement, which are time consuming and show high variability. We propose a computer-assisted clinical tool to assess and classify renal tumors in contrast-enhanced CT for the management and classification of kidney tumors. The quantification of lesions used level-sets and a statistical refinement step to adapt to the shape of the lesions. Intra-patient and inter-phase registration facilitated the study of lesion enhancement. From the segmented lesions, the histograms of curvature-related features were used to classify the lesion types via random sampling. The clinical tool allows the accurate quantification and classification of cysts and cancer from clinical data. Cancer types are further classified into four categories. Computer-assisted image analysis shows great potential for tumor diagnosis and monitoring.
---
paper_title: Path planning algorithm for unmanned surface vehicle formations in a practical maritime environment

paper_content:

Unmanned surface vehicles (USVs) have been deployed over the past decade. Current USV platforms are generally of small size with low payload capacity and short endurance times. To improve effectiveness there is a trend to deploy multiple USVs as a formation fleet. This paper presents a novel computer based algorithm that solves the problem of USV formation path planning. The algorithm is based upon the fast marching (FM) method and has been specifically designed for operation in dynamic environments using the novel constrained FM method. The constrained FM method is able to model the dynamic behaviour of moving ships with efficient computation time. The algorithm has been evaluated using a range of tests applied to a simulated area and has been proved to work effectively in a complex navigation environment.
---
paper_title: Narrow passage path planning using fast marching method and support vector machine

paper_content:

This paper introduces a novel path planning method under non-holonomic constraint for car-like vehicles, which associates map discovery and heuristic search to attain an optimal resultant path. The map discovery applies fast marching method to investigate the map geometric information. After that, the support vector machine is performed to find obstacle clearance information. This information is then used as a heuristic function which helps greatly reduce the search space. The fast marching is performed again, guided by this function to generate vehicle motions under kinematic constraints. Experimental results have shown that this method is able to generate motions for non-holonomic vehicles. In comparison with related methods, the path generated by proposed method is smoother and stay farther away from the obstacles.
---
paper_title: Fast methods for the Eikonal and related Hamilton- Jacobi equations on unstructured meshes.

paper_content:

The Fast Marching Method is a numerical algorithm for solving the Eikonal equation on a rectangular orthogonal mesh in O(M log M) steps, where M is the total number of grid points. The scheme relies on an upwind finite difference approximation to the gradient and a resulting causality relationship that lends itself to a Dijkstra-like programming approach. In this paper, we discuss several extensions to this technique, including higher order versions on unstructured meshes in Rn and on manifolds and connections to more general static Hamilton-Jacobi equations.
---
paper_title: Some Improvements for the Fast Sweeping Method

paper_content:

In this paper, we outline two improvements to the fast sweeping method to improve the speed of the method in general and more specifically in cases where the speed is changing rapidly. The conventional wisdom is that fast sweeping works best when the speed changes slowly, and fast marching is the algorithm of choice when the speed changes rapidly. The goal here is to achieve run times for the fast sweeping method that are at least as fast, or faster, than competitive methods, e.g. fast marching, in the case where the speed is changing rapidly. The first improvement, which we call the locking method, dynamically keeps track of grid points that have either already had the solution successfully calculated at that grid point or for which the solution cannot be successfully calculated during the current iteration. These locked points can quickly be skipped over during the fast sweeping iterations, avoiding many time-consuming calculations. The second improvement, which we call the two queue method, keeps all of the unlocked points in a data structure so that the locked points no longer need to be visited at all. Unfortunately, it is not possible to insert new points into the data structure while maintaining the fast sweeping ordering without at least occasionally sorting. Instead, we segregate the grid points into those with small predicted solutions and those with large predicted solutions using two queues. We give two ways of performing this segregation. This method is a label correcting (iterative) method like the fast sweeping method, but it tends to operate near the front like the fast marching method. It is reminiscent of the threshold method for finding the shortest path on a network, [F. Glover, D. Klingman, and N. Phillips, Oper. Res., 33 (1985), pp. 65-73]. We demonstrate the numerical efficiency of the improved methods on a number of examples.
---
paper_title: A new ray tracing technique for crosshole radar traveltime tomography based on multistencils fast marching method and the steepest descend method

paper_content:

We presented a new ray tracing technique which is applicable for crosshole radar traveltime tomography. The new algorithm divides the ray tracing process into two steps: First the wavefront propagation times of all grid points in a velocity field are calculated using the multistencils fast marching method (MSFM), and then the ray tracing paths having the minimum traveltime can be easily obtained by following the steepest gradient direction from the receiver to the transmitter. In contrast to traditional fast marching method (FMM) and higher accuracy fast marching method (HAFMM), MSFM algorithm calculates traveltimes using two stencils at the same time, and the information in diagonal direction can be included, thus the calculation accuracy and efficiency can be improved greatly. In order to verify the accuracy and efficiency of the new ray tracing method, we test the proposed scheme on two synthetic velocity models where the exact solutions can be calculated, and we compared our results with the one obtained by a FMM based and a HAFMM based steepest descend ray tracing methods. This comparison indicated that the suggested ray tracing technique can achieve much better results both on accuracy and efficiency compared to the FMM based and the HAFMM based steepest descend ray tracing methods.
---
paper_title: Comparison of active contour and fast marching methods of hippocampus segmentation

paper_content:

The hippocampus is a part of the limbic system and plays an important role in long-term memory and spatial navigation. As part of hippocampal imaging studies, the region of the hippocampus is usually segmented manually, which is a time-consuming process. Here, we describe a comparison of the active contour model (ACM) and the fast marching method (FMM) using magnetic resonance (MR) images of the human brain. We determine optimized input parameters for both models to segment the hippocampus using T1-weighted MR images, and we found that the ACM provided superior performance compared with the FMM without significant additional computational expense.
---
paper_title: VDB: High-resolution sparse volumes with dynamic topology

paper_content:

We have developed a novel hierarchical data structure for the efficient representation of sparse, time-varying volumetric data discretized on a 3D grid. Our “VDB”, so named because it is a Volumetric, Dynamic grid that shares several characteristics with Bptrees, exploits spatial coherency of time-varying data to separately and compactly encode data values and grid topology. VDB models a virtually infinite 3D index space that allows for cache-coherent and fast data access into sparse volumes of high resolution. It imposes no topology restrictions on the sparsity of the volumetric data, and it supports fast (average O(1)) random access patterns when the data are inserted, retrieved, or deleted. This is in contrast to most existing sparse volumetric data structures, which assume either static or manifold topology and require specific data access patterns to compensate for slow random access. Since the VDB data structure is fundamentally hierarchical, it also facilitates adaptive grid sampling, and the inherent acceleration structure leads to fast algorithms that are well-suited for simulations. As such, VDB has proven useful for several applications that call for large, sparse, animated volumes, for example, level set dynamics and cloud modeling. In this article, we showcase some of these algorithms and compare VDB with existing, state-of-the-art data structures.
---
paper_title: Generalized fast marching method: applications to image segmentation

paper_content:

In this paper, we propose a segmentation method based on the generalized fast marching method (GFMM) developed by Carlini et al. (submitted). The classical fast marching method (FMM) is a very efficient method for front evolution problems with normal velocity (see also Epstein and Gage, The curve shortening flow. In: Chorin, A., Majda, A. (eds.) Wave Motion: Theory, Modelling and Computation, 1997) of constant sign. The GFMM is an extension of the FMM and removes this sign constraint by authorizing time-dependent velocity with no restriction on the sign. In our modelling, the velocity is borrowed from the Chan–Vese model for segmentation (Chan and Vese, IEEE Trans Image Process 10(2):266–277, 2001). The algorithm is presented and analyzed and some numerical experiments are given, showing in particular that the constraints in the initialization stage can be weakened and that the GFMM offers a powerful and computationally efficient algorithm.
---
paper_title: Reconstructing neuronal morphology from microscopy stacks using fast marching

paper_content:

Automated algorithms to build accurate models of 3D neuronal arborization is much in demand due to large volume of microscopy data. We present a tracking algorithm for automatic and reliable extraction of neuronal morphology. It is robust to ambiguous branch discontinuities, variability of intensity and curvature of fibres, arbitrary branch cross-sections, noise and irregular background illumination. We complete the presentation of our method with demonstration of its performance on synthetic data modeling challenging scenarios and on confocal microscopy data of Olfactory Projection fibres from DIADEM data set with promising results.
---
paper_title: A FAST ITERATIVE METHOD FOR EIKONAL EQUATIONS

paper_content:

In this paper we propose a novel computational technique to solve the Eikonal equation efficiently on parallel architectures. The proposed method manages the list of active nodes and iteratively updates the solutions on those nodes until they converge. Nodes are added to or removed from the list based on a convergence measure, but the management of this list does not entail an extra burden of expensive ordered data structures or special updating sequences. The proposed method has suboptimal worst-case performance but, in practice, on real and synthetic datasets, runs faster than guaranteed-optimal alternatives. Furthermore, the proposed method uses only local, synchronous updates and therefore has better cache coherency, is simple to implement, and scales efficiently on parallel architectures. This paper describes the method, proves its consistency, gives a performance analysis that compares the proposed method against the state-of-the-art Eikonal solvers, and describes the implementation on a single instruction multiple datastream (SIMD) parallel architecture.
---
paper_title: Computer-aided renal cancer quantification and classification from contrast-enhanced CT via histograms of curvature-related features

paper_content:

In clinical practice, renal cancer diagnosis is performed by manual quantifications of tumor size and enhancement, which are time consuming and show high variability. We propose a computer-assisted clinical tool to assess and classify renal tumors in contrast-enhanced CT for the management and classification of kidney tumors. The quantification of lesions used level-sets and a statistical refinement step to adapt to the shape of the lesions. Intra-patient and inter-phase registration facilitated the study of lesion enhancement. From the segmented lesions, the histograms of curvature-related features were used to classify the lesion types via random sampling. The clinical tool allows the accurate quantification and classification of cysts and cancer from clinical data. Cancer types are further classified into four categories. Computer-assisted image analysis shows great potential for tumor diagnosis and monitoring.
---
paper_title: Full waveform inversion guided by travel time tomography

paper_content:

Full waveform inversion (FWI) is a process in which seismic data in time or frequency domain is fit by changing the velocity of the media under investigation. The problem is non-linear, and therefore optimization techniques have been used to find a geological solution to the problem. The main problem in fitting the data is the lack of low spatial frequencies. This deficiency often leads to a local minimum and to non-geologic solutions. In this work we explore how to obtain low frequency information for FWI. Our approach involves augmenting FWI with travel time tomography, which has low-frequency features. By jointly inverting these two problems we enrich FWI with information that can replace low frequency data. In addition, we use high order regularization in a preliminary inversion stage to prevent high frequency features from polluting our model in the initial stages of the reconstruction. This regularization also promote the low-frequencies non-dominant modes that exist in the FWI sensitivity. By applying a smoothly regularized joint inversion we are able to obtain a smooth model than can later be used to recover a good approximation for the true model. A second contribution of this paper involves the acceleration of the main computational bottleneck in FWI--the solution of the Helmholtz equation. We show that the solution time can be significantly reduced by solving the equation for multiple right hand sides using block multigrid preconditioned Krylov methods.
---
paper_title: Concurrent Segmentation and Recognition with Shape-Driven Fast Marching Methods

paper_content:

We present a variational framework that integrates the statistical boundary shape models into a Level Set system that is capable of both segmenting and recognizing objects. Since we aim to recognize objects, we trace the active contour and stop it near real object boundaries while inspecting the shape of the contour instead of enforcing the contour to get a priori shape. We get the location of character boundaries and character labels at the system output. We developed a promising local front stopping scheme based on both image and shape information for fast marching systems. A new object boundary shape signature model, based on directional Gauss gradient filter responses, is also proposed. The character recognition system that employs the new boundary shape descriptor outperforms the other systems, based on well-known boundary signatures such as centroid distance, curvature etc.
---
paper_title: First-break traveltime tomography with the double-square-root eikonal equation

paper_content:

ABSTRACTFirst-break traveltime tomography is based on the eikonal equation. Because the eikonal equation is solved at fixed-shot positions and only receiver positions can move along the raypath, the adjoint-state tomography relies on inversion to resolve possible contradicting information between independent shots. The double-square-root (DSR) eikonal equation allows not only the receivers but also the shots to change position, and thus describes the prestack survey as a whole. Consequently, its linearized tomographic operator naturally handles all shots together, in contrast with the shotwise approach in the traditional eikonal-based framework. The DSR eikonal equation is singular for the horizontal waves, which require special handling. Although it is possible to recover all branches of the solution through postprocessing, our current forward modeling and tomography focuses on the diving wave branch only. We consider two upwind discretizations of the DSR eikonal equation and show that the explicit schem...
---
paper_title: A new ray tracing technique for crosshole radar traveltime tomography based on multistencils fast marching method and the steepest descend method

paper_content:

We presented a new ray tracing technique which is applicable for crosshole radar traveltime tomography. The new algorithm divides the ray tracing process into two steps: First the wavefront propagation times of all grid points in a velocity field are calculated using the multistencils fast marching method (MSFM), and then the ray tracing paths having the minimum traveltime can be easily obtained by following the steepest gradient direction from the receiver to the transmitter. In contrast to traditional fast marching method (FMM) and higher accuracy fast marching method (HAFMM), MSFM algorithm calculates traveltimes using two stencils at the same time, and the information in diagonal direction can be included, thus the calculation accuracy and efficiency can be improved greatly. In order to verify the accuracy and efficiency of the new ray tracing method, we test the proposed scheme on two synthetic velocity models where the exact solutions can be calculated, and we compared our results with the one obtained by a FMM based and a HAFMM based steepest descend ray tracing methods. This comparison indicated that the suggested ray tracing technique can achieve much better results both on accuracy and efficiency compared to the FMM based and the HAFMM based steepest descend ray tracing methods.
---
paper_title: A FAST ITERATIVE METHOD FOR EIKONAL EQUATIONS

paper_content:

In this paper we propose a novel computational technique to solve the Eikonal equation efficiently on parallel architectures. The proposed method manages the list of active nodes and iteratively updates the solutions on those nodes until they converge. Nodes are added to or removed from the list based on a convergence measure, but the management of this list does not entail an extra burden of expensive ordered data structures or special updating sequences. The proposed method has suboptimal worst-case performance but, in practice, on real and synthetic datasets, runs faster than guaranteed-optimal alternatives. Furthermore, the proposed method uses only local, synchronous updates and therefore has better cache coherency, is simple to implement, and scales efficiently on parallel architectures. This paper describes the method, proves its consistency, gives a performance analysis that compares the proposed method against the state-of-the-art Eikonal solvers, and describes the implementation on a single instruction multiple datastream (SIMD) parallel architecture.
---
paper_title: A comparison of Fast Marching, Fast Sweeping and Fast Iterative Methods for the solution of the eikonal equation

paper_content:

We compare the computational performance of the Fast Marching Method, the Fast Sweeping Method and of the Fast Iterative Method to determine a numerical solution to the eikonal equation. We point out how the FIM outperforms the other two thanks to its parallel processing capabilities.
---
paper_title: Some Improvements for the Fast Sweeping Method

paper_content:

In this paper, we outline two improvements to the fast sweeping method to improve the speed of the method in general and more specifically in cases where the speed is changing rapidly. The conventional wisdom is that fast sweeping works best when the speed changes slowly, and fast marching is the algorithm of choice when the speed changes rapidly. The goal here is to achieve run times for the fast sweeping method that are at least as fast, or faster, than competitive methods, e.g. fast marching, in the case where the speed is changing rapidly. The first improvement, which we call the locking method, dynamically keeps track of grid points that have either already had the solution successfully calculated at that grid point or for which the solution cannot be successfully calculated during the current iteration. These locked points can quickly be skipped over during the fast sweeping iterations, avoiding many time-consuming calculations. The second improvement, which we call the two queue method, keeps all of the unlocked points in a data structure so that the locked points no longer need to be visited at all. Unfortunately, it is not possible to insert new points into the data structure while maintaining the fast sweeping ordering without at least occasionally sorting. Instead, we segregate the grid points into those with small predicted solutions and those with large predicted solutions using two queues. We give two ways of performing this segregation. This method is a label correcting (iterative) method like the fast sweeping method, but it tends to operate near the front like the fast marching method. It is reminiscent of the threshold method for finding the shortest path on a network, [F. Glover, D. Klingman, and N. Phillips, Oper. Res., 33 (1985), pp. 65-73]. We demonstrate the numerical efficiency of the improved methods on a number of examples.
---
paper_title: A new ray tracing technique for crosshole radar traveltime tomography based on multistencils fast marching method and the steepest descend method

paper_content:

We presented a new ray tracing technique which is applicable for crosshole radar traveltime tomography. The new algorithm divides the ray tracing process into two steps: First the wavefront propagation times of all grid points in a velocity field are calculated using the multistencils fast marching method (MSFM), and then the ray tracing paths having the minimum traveltime can be easily obtained by following the steepest gradient direction from the receiver to the transmitter. In contrast to traditional fast marching method (FMM) and higher accuracy fast marching method (HAFMM), MSFM algorithm calculates traveltimes using two stencils at the same time, and the information in diagonal direction can be included, thus the calculation accuracy and efficiency can be improved greatly. In order to verify the accuracy and efficiency of the new ray tracing method, we test the proposed scheme on two synthetic velocity models where the exact solutions can be calculated, and we compared our results with the one obtained by a FMM based and a HAFMM based steepest descend ray tracing methods. This comparison indicated that the suggested ray tracing technique can achieve much better results both on accuracy and efficiency compared to the FMM based and the HAFMM based steepest descend ray tracing methods.
---
paper_title: Planning Reliable Paths With Pose SLAM

paper_content:

The maps that are built by standard feature-based simultaneous localization and mapping (SLAM) methods cannot be directly used to compute paths for navigation, unless enriched with obstacle or traversability information, with the consequent increase in complexity. Here, we propose a method that directly uses the Pose SLAM graph of constraints to determine the path between two robot configurations with lowest accumulated pose uncertainty, i.e., the most reliable path to the goal. The method shows improved navigation results when compared with standard path-planning strategies over both datasets and real-world experiments.
---
paper_title: 1 A Tutorial on Graph-Based SLAM

paper_content:

Being able to build a map of the environment and to simultaneously localize within this map is an essential skill for mobile robots navigating in unknown environments in absence of external referencing systems such as GPS. This so-called simultaneous localization and mapping (SLAM) problem has been one of the most popular research topics in mobile robotics for the last two decades and efficient approaches for solving this task have been proposed. One intuitive way of formulating SLAM is to use a graph whose nodes correspond to the poses of the robot at different points in time and whose edges represent constraints between the poses. The latter are obtained from observations of the environment or from movement actions carried out by the robot. Once such a graph is constructed, the map can be computed by finding the spatial configuration of the nodes that is mostly consistent with the measurements modeled by the edges. In this paper, we provide an introductory description to the graph-based SLAM problem. Furthermore, we discuss a state-of-the-art solution that is based on least-squares error minimization and exploits the structure of the SLAM problems during optimization. The goal of this tutorial is to enable the reader to implement the proposed methods from scratch.
---
paper_title: Comparative study of retinal vessel segmentation methods on a new publicly available database

paper_content:

In this work we compare the performance of a number of vessel segmentation algorithms on a newly constructed retinal vessel image database. Retinal vessel segmentation is important for the detection of numerous eye diseases and plays an important role in automatic retinal disease screening systems. A large number of methods for retinal vessel segmentation have been published, yet an evaluation of these methods on a common database of screening images has not been performed. To compare the performance of retinal vessel segmentation methods we have constructed a large database of retinal images. The database contains forty images in which the vessel trees have been manually segmented. For twenty of those forty images a second independent manual segmentation is available. This allows for a comparison between the performance of automatic methods and the performance of a human observer. The database is available to the research community. Interested researchers are encouraged to upload their segmentation results to our website (http://www.isi.uu.nl/Research/Databases). The performance of five different algorithms has been compared. Four of these methods have been implemented as described in the literature. The fifth pixel classification based method was developed specifically for the segmentation of retinal vessels and is the only supervised method in this test. We define the segmentation accuracy with respect to our gold standard as the performance measure. Results show that the pixel classification method performs best, but the second observer still performs significantly better.
---
paper_title: Efficient algorithms for globally optimal trajectories

paper_content:

Presents serial and parallel algorithms for solving a system of equations that arises from the discretization of the Hamilton-Jacobi equation associated to a trajectory optimization problem of the following type. A vehicle starts at a prespecified point x/sub 0/ and follows a unit speed trajectory x(t) inside a region in /spl Rfr//sup m/, until an unspecified time T that the region is excited. A trajectory minimising a cost function of the form /spl int//sub 0//sup T/ r(x(t))dt+q(x(T)) is sought. The discretized Hamilton-Jacobi equation corresponding to this problem is usually served using iterative methods. Nevertheless, assuming that the function r is positive, one is able to exploit the problem structure and develop one-pass algorithms for the discretized problem. The first m resembles Dijkstra's shortest path algorithm and runs in time O(n log n), where n is the number of grid points. The second algorithm uses a somewhat different discretization and borrows some ideas from Dial's shortest path algorithm; it runs in time O(n), which is the best possible, under some fairly mild assumptions. Finally, the author shows that the latter algorithm can be efficiently parallelized: for two-dimensional problems and with p processors, its running time becomes O(n/p), provided that p=O(/spl radic/n/log n). >
---
paper_title: Globally optimal curvature-regularized fast marching for vessel segmentation.

paper_content:

We introduce a novel fast marching approach with curvature regularization for vessel segmentation. Since most vessels have a smooth path, curvature can be used to distinguish desired vessels from short cuts, which usually contain parts with high curvature. However, in previous fast marching approaches, curvature information is not available, so it cannot be used for regularization directly. Instead, usually length regularization is used under the assumption that shorter paths should also have a lower curvature. However, for vessel segmentation, this assumption often does not hold and leads to short cuts. We propose an approach, which integrates curvature regularization directly into the fast marching framework, independent of length regularization. Our approach is globally optimal, and numerical experiments on synthetic and real retina images show that our approach yields more accurate results than two previous approaches.
---
paper_title: A Third Order Accurate Fast Marching Method for the Eikonal Equation in Two Dimensions

paper_content:

In this paper, we develop a third order accurate fast marching method for the solution of the eikonal equation in two dimensions. There have been two obstacles to extending the fast marching method to higher orders of accuracy. The first obstacle is that using one-sided difference schemes is unstable for orders of accuracy higher than two. The second obstacle is that the points in the difference stencil are not available when the gradient is closely aligned with the grid. We overcome these obstacles by using a two-dimensional (2D) finite difference approximation to improve stability, and by locally rotating the grid 45 degrees (i.e., using derivatives along the diagonals) to ensure all the points needed in the difference stencil are available. We show that in smooth regions the full difference stencil is used for a suitably small enough grid size and that the difference scheme satisfies the von Neumann stability condition for the linearized eikonal equation. Our method reverts to first order accuracy near caustics without developing oscillations by using a simple switching scheme. The efficiency and high order of the method are demonstrated on a number of 2D test problems.
---
paper_title: Path Planning for Autonomous Underwater Vehicles

paper_content:

Efficient path-planning algorithms are a crucial issue for modern autonomous underwater vehicles. Classical path-planning algorithms in artificial intelligence are not designed to deal with wide continuous environments prone to currents. We present a novel Fast Marching (FM)-based approach to address the following issues. First, we develop an algorithm we call FM* to efficiently extract a 2-D continuous path from a discrete representation of the environment. Second, we take underwater currents into account thanks to an anisotropic extension of the original FM algorithm. Third, the vehicle turning radius is introduced as a constraint on the optimal path curvature for both isotropic and anisotropic media. Finally, a multiresolution method is introduced to speed up the overall path-planning process
---
paper_title: Fast Sweeping Methods for Static Hamilton-Jacobi Equations

paper_content:

We propose a new sweeping algorithm which discretizes the Legendre transform of the numerical Hamiltonian using an explicit formula. This formula yields the numerical solution at a grid point using only its immediate neighboring grid values and is easy to implement numerically. The minimization that is related to the Legendre transform in our sweeping scheme can either be solved analytically or numerically. We illustrate the efficiency and accuracy approach with several numerical examples in two and three dimensions.
---
paper_title: Image compression with anisotropic triangulations

paper_content:

We propose a new image compression method based on geodesic Delaunay triangulations. Triangulations are generated by a progressive geodesic meshing algorithm which exploits the anisotropy of images through a farthest point sampling strategy. This seeding is performed according to anisotropic geodesic distances which force the anisotropic Delaunay triangles to follow the geometry of the image. Geodesic computations are performed using a Riemannian Fast Marching, which recursively updates the geodesic distance to the seed points. A linear spline approximation on this triangulation allows to approximate faithfully sharp edges and directional features in images. The compression is achieved by coding both the coefficients of the spline approximation and the deviation of the geodesic triangulation from an Euclidean Delaunay triangulation. Numerical results show that taking into account the anisotropy improves the approximation by isotropic triangulations of complex images. The resulting geodesic encoder competes well with wavelet-based encoder such as JPEG-2000 on geometric images.
---
paper_title: The Path to Efficiency: Fast Marching Method for Safer, More Efficient Mobile Robot Trajectories

paper_content:

This article provides a comprehensive view of the novel fast marching (FM) methods we developed for robot path planning. We recall some of the methods developed in recent years and present two improvements upon them: the saturated FM square (FM2) and an heuristic optimization called the FM2 star (FM2*) method.
---
paper_title: Fast Sweeping Algorithms for a Class of Hamilton-Jacobi Equations

paper_content:

We derive a Godunov-type numerical flux for the class of strictly convex, homogeneous Hamiltonians that includes $H(p,q)=\sqrt{ap^{2}+bq^{2}-2cpq},$ $c^{2}<ab.$ We combine our Godunov numerical fluxes with simple Gauss--Seidel-type iterations for solving the corresponding Hamilton--Jacobi (HJ) equations. The resulting algorithm is fast since it does not require a sorting strategy as found, e.g., in the fast marching method. In addition, it providesa way to compute solutions to a class of HJ equations for which the conventional fast marching method is not applicable. Our experiments indicate convergence after a few iterations, even in rather difficult cases.
---
paper_title: Computational Study of Fast Methods for the Eikonal Equation

paper_content:

A computational study of the fast marching and the fast sweeping methods for the eikonal equation is given. It is stressed that both algorithms should be considered as "direct" (as opposed to iterative) methods. On realistic grids, fast sweeping is faster than fast marching for problems with simple geometry. For strongly nonuniform problems and/or complex geometry, the situation may be reversed. Finally, fully second order generalizations of methods of this type for problems with obstacles are proposed and implemented.
---
paper_title: Asymptotically optimal feedback planning using a numerical Hamilton-Jacobi-Bellman solver and an adaptive mesh refinement

paper_content:

We present the first asymptotically optimal feedback planning algorithm for nonholonomic systems and additive cost functionals. Our algorithm is based on three well-established numerical practices: 1 positive coefficient numerical approximations of the Hamilton-Jacobi-Bellman equations; 2 the Fast Marching Method, which is a fast nonlinear solver that utilizes Bellman's dynamic programming principle for efficient computations; and 3 an adaptive mesh-refinement algorithm designed to improve the resolution of an initial simplicial mesh and reduce the solution numerical error. By refining the discretization mesh globally, we compute a sequence of numerical solutions that converges to the true viscosity solution of the Hamilton-Jacobi-Bellman equations. In order to reduce the total computational cost of the proposed planning algorithm, we find that it is sufficient to refine the discretization within a small region in the vicinity of the optimal trajectory. Numerical experiments confirm our theoretical findings and establish that our algorithm outperforms previous asymptotically optimal planning algorithms, such as PRM* and RRT*.
---
paper_title: Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions

paper_content:

In this paper we present a novel probabilistic sampling-based motion planning algorithm called the Fast Marching Tree algorithm (FMT*). The algorithm is specifically aimed at solving complex motion planning problems in high-dimensional configuration spaces. This algorithm is proven to be asymptotically optimal and is shown to converge to an optimal solution faster than its state-of-the-art counterparts, chiefly PRM* and RRT*. The FMT* algorithm performs a "lazy" dynamic programming recursion on a predetermined number of probabilistically-drawn samples to grow a tree of paths, which moves steadily outward in cost-to-arrive space. As such, this algorithm combines features of both single-query algorithms (chiefly RRT) and multiple-query algorithms (chiefly PRM), and is reminiscent of the Fast Marching Method for the solution of Eikonal equations. As a departure from previous analysis approaches that are based on the notion of almost sure convergence, the FMT* algorithm is analyzed under the notion of convergence in probability: the extra mathematical flexibility of this approach allows for convergence rate bounds-the first in the field of optimal sampling-based motion planning. Specifically, for a certain selection of tuning parameters and configuration spaces, we obtain a convergence rate bound of order O(n-1/d+ρ), where n is the number of sampled points, d is the dimension of the configuration space, and ρ is an arbitrarily small constant. We go on to demonstrate asymptotic optimality for a number of variations on FMT*, namely when the configuration space is sampled non-uniformly, when the cost is not arc length, and when connections are made based on the number of nearest neighbors instead of a fixed connection radius. Numerical experiments over a range of dimensions and obstacle configurations confirm our the-oretical and heuristic arguments by showing that FMT*, for a given execution time, returns substantially better solutions than either PRM* or RRT*, especially in high-dimensional configuration spaces and in scenarios where collision-checking is expensive.
---
paper_title: A parallel fast sweeping method for the Eikonal equation

paper_content:

We present an algorithm for solving in parallel the Eikonal equation. The efficiency of our approach is rooted in the ordering and distribution of the grid points on the available processors; we utilize a Cuthill-McKee ordering. The advantages of our approach is that (1) the efficiency does not plateau for a large number of threads; we compare our approach to the current state-of-the-art parallel implementation of Zhao (2007) [14] and (2) the total number of iterations needed for convergence is the same as that of a sequential implementation, i.e. our parallel implementation does not increase the complexity of the underlying sequential algorithm. Numerical examples are used to illustrate the efficiency of our approach.
---

Title: Fast Methods for Eikonal Equations: An Experimental Survey

Section 1: INTRODUCTION
Description 1: Introduce the background, importance, applications, and objectives of the survey on Fast Methods for solving Eikonal equations.

Section 2: PROBLEM FORMULATION
Description 2: Detail the problem definition, the formulation of the Eikonal equation, and the n-dimensional discrete Eikonal equation.

Section 3: FAST MARCHING METHODS
Description 3: Introduce and describe the Fast Marching Method (FMM) and its related implementations, including FMM with binary and Fibonacci heaps, Simplified FMM (SFMM), and Untidy FMM (UFMM).

Section 4: FAST SWEEPING METHODS
Description 4: Present and explain the Fast Sweeping Method (FSM) and its enhancements like the Locking Sweeping Method (LSM).

Section 5: OTHER FAST METHODS
Description 5: Include descriptions of additional algorithms such as the Group Marching Method (GMM) and the Dynamic Double Queue Method (DDQM).

Section 6: EXPERIMENTAL COMPARISON
Description 6: Discuss the experimental setup and detailed comparisons of all the aforementioned methods through various experiments and case studies.

Section 7: DISCUSSION
Description 7: Provide an analysis and discussion based on the experimental results, highlighting the strengths and weaknesses of each method in different scenarios.

Section 8: CONCLUSIONS
Description 8: Summarize the findings of the survey, draw final conclusions, and suggest potential areas for future research.