Computing geodesic paths encoding a curvature prior for curvilinear structure tracking.

In this paper, we introduce an efficient method for computing curves minimizing a variant of the Euler-Mumford elastica energy, with fixed endpoints and tangents at these endpoints, where the bending energy is enhanced with a user-defined and data-driven scalar-valued term referred to as the curvature prior. In order to guarantee that the globally optimal curve is extracted, the proposed method involves the numerical computation of the viscosity solution to a specific static Hamilton-Jacobi-Bellman (HJB) partial differential equation (PDE). For that purpose, we derive the explicit Hamiltonian associated with this variant model equipped with a curvature prior, discretize the resulting HJB PDE using an adaptive finite difference scheme, and solve it in a single pass using a generalized fast-marching method. In addition, we also present a practical method for estimating the curvature prior values from image data, designed for the task of accurately tracking curvilinear structure centerlines. Numerical experiments on synthetic and real-image data illustrate the advantages of the considered variant of the elastica model with a prior curvature enhancement in complex scenarios where challenging geometric structures appear.

Efficient acceleration of the convergence of the minimum free energy path via a path-planning generated initial guess.

We demonstrate that combining a shifted clustering algorithm with a fast-marching-based algorithm can generate accurate approximations of the minimum energy path (MEP) given a free energy landscape (FEL). Using this approximation as the initial guess for the MEP, followed by further refinement with the string method (referred to as the fast marching tree (FMT)-string combined approach), significantly reduces the number of iterations required for MEP convergence. This approach saves substantial time compared to using linear interpolation (LI) for the initial guess. Our method offers a viable solution for obtaining an effective initial guess of the MEP when an approximate or converged FEL is available. This work highlights the potential of applying FMT-based approaches to extract the MEP in chemical reactions.

Sensor Fusion for Social Navigation on a Mobile Robot Based on Fast Marching Square and Gaussian Mixture Model.

Mobile robot navigation has been studied for a long time, and it is nowadays widely used in multiple applications. However, it is traditionally focused on two-dimensional geometric characteristics of the environments. There are situations in which robots need to share space with people, so additional aspects, such as social distancing, need to be considered. In this work, an approach for social navigation is presented. A multi-layer model of the environment containing geometric and topological characteristics is built based on the fusion of multiple sensor information. This is later used for navigating the environment considering social distancing from individuals and groups of people. The main novelty is combining fast marching square for path planning and navigation with Gaussian models to represent people. This combination allows to create a continuous representation of the environment from which smooth paths can be extracted and modified according to dynamically captured data. Results prove the practical application of the method on an assistive robot for navigating indoor scenarios, including a behavior for crossing narrow passages. People are efficiently detected and modeled to assure their comfort when robots are around.

FM2 Path Planner for UAV Applications with Curvature Constraints: A Comparative Analysis with Other Planning Approaches.

This paper studies the Fast Marching Square (FM2) method as a competitive path planner for UAV applications. The approach fulfills trajectory curvature constraints together with a significantly reduced computation time, which makes it overperform with respect to other planning methods of the literature based on optimization. A comparative analysis is presented to demonstrate how the FM2 approach can easily adapt its performance thanks to the introduction of two parameters, saturation α and exponent ß, that allow a flexible configuration of the paths in terms of curvature restrictions, among others. The main contributions of the method are twofold: first, a feasible path is directly obtained without the need of a later optimization process to accomplish curvature restrictions; second, the computation speed is significantly increased, up to 220 times faster than other optimization-based methods such as, for instance, Dubins, Euler-Mumford Elastica and Reeds-Shepp. Simulation results are given to demonstrate the superiority of the method when used for UAV applications in comparison with the three previously mentioned methods.

Multi UAV Coverage Path Planning in Urban Environments.

Coverage path planning (CPP) is a field of study which objective is to find a path that covers every point of a certain area of interest. Recently, the use of Unmanned Aerial Vehicles (UAVs) has become more proficient in various applications such as surveillance, terrain coverage, mapping, natural disaster tracking, transport, and others. The aim of this paper is to design efficient coverage path planning collision-avoidance capable algorithms for single or multi UAV systems in cluttered urban environments. Two algorithms are developed and explored: one of them plans paths to cover a target zone delimited by a given perimeter with predefined coverage height and bandwidth, using a boustrophedon flight pattern, while the other proposed algorithm follows a set of predefined viewpoints, calculating a smooth path that ensures that the UAVs pass over the objectives. Both algorithms have been developed for a scalable number of UAVs, which fly in a triangular deformable leader-follower formation with the leader at its front. In the case of an even number of UAVs, there is no leader at the front of the formation and a virtual leader is used to plan the paths of the followers. The presented algorithms also have collision avoidance capabilities, powered by the Fast Marching Square algorithm. These algorithms are tested in various simulated urban and cluttered environments, and they prove capable of providing safe and smooth paths for the UAV formation in urban environments.

Lung Nodule Segmentation with a Region-Based Fast Marching Method.

When dealing with computed tomography volume data, the accurate segmentation of lung nodules is of great importance to lung cancer analysis and diagnosis, being a vital part of computer-aided diagnosis systems. However, due to the variety of lung nodules and the similarity of visual characteristics for nodules and their surroundings, robust segmentation of nodules becomes a challenging problem. A segmentation algorithm based on the fast marching method is proposed that separates the image into regions with similar features, which are then merged by combining regions growing with k-means. An evaluation was performed with two distinct methods (objective and subjective) that were applied on two different datasets, containing simulation data generated for this study and real patient data, respectively. The objective experimental results show that the proposed technique can accurately segment nodules, especially in solid cases, given the mean Dice scores of 0.933 and 0.901 for round and irregular nodules. For non-solid and cavitary nodules the performance dropped-0.799 and 0.614 mean Dice scores, respectively. The proposed method was compared to active contour models and to two modern deep learning networks. It reached better overall accuracy than active contour models, having comparable results to DBResNet but lesser accuracy than 3D-UNet. The results show promise for the proposed method in computer-aided diagnosis applications.

Path Planning and Collision Risk Management Strategy for Multi-UAV Systems in 3D Environments.

Multi-UAV systems are attracting, especially in the last decade, the attention of researchers and companies of very different fields due to the great interest in developing systems capable of operating in a coordinated manner in complex scenarios and to cover and speed up applications that can be dangerous or tedious for people: search and rescue tasks, inspection of facilities, delivery of goods, surveillance, etc. Inspired by these needs, this work aims to design, implement and analyze a trajectory planning and collision avoidance strategy for multi-UAV systems in 3D environments. For this purpose, a study of the existing techniques for both problems is carried out and an innovative strategy based on Fast Marching Square-for the planning phase-and a simple priority-based speed control-as the method for conflict resolution-is proposed, together with prevention measures designed to try to limit and reduce the greatest number of conflicting situations that may occur between vehicles while they carry out their missions in a simulated 3D urban environment. The performance of the algorithm is evaluated successfully on the basis of certain conveniently chosen statistical measures that are collected throughout the simulation runs.

Microseismic P-Wave Travel Time Computation and 3D Localization Based on a 3D High-Order Fast Marching Method.

The travel time computation of microseismic waves in different directions (particularly, the diagonal direction) in three-dimensional space has been found to be inaccurate, which seriously affects the localization accuracy of three-dimensional microseismic sources. In order to solve this problem, this research study developed a method of calculating the P-wave travel time based on a 3D high-order fast marching method (3D_H_FMM). This study focused on designing a high-order finite-difference operator in order to realize the accurate calculation of the P-wave travel time in three-dimensional space. The method was validated using homogeneous velocity models and inhomogeneous layered media velocity models of different scales. The results showed that the overall mean absolute error (MAE) of the two homogenous models using 3D_H_FMM had been reduced by 88.335%, and 90.593% compared with the traditional 3D_FMM. On that basis, the three-dimensional localization of microseismic sources was carried out using a particle swarm optimization algorithm. The developed 3D_H_FMM was used to calculate the travel time, then to conduct the localization of the microseismic source in inhomogeneous models. The mean error of the localization results of the different positions in the three-dimensional space was determined to be 1.901 m, and the localization accuracy was found to be superior to that of the traditional 3D_FMM method (mean absolute localization error: 3.447 m) with the small-scaled inhomogeneous model.

Automatic Fiber Length Measurements with a Multi-Stencil Fast Marching Method on Microscopy Images.

Fiber length has a strong impact on the mechanical properties of composite materials. It is one of the most important quantitative features in characterizing microstructures for understanding the material performance. Studies conducted to determine fiber length distribution have primarily focused on sample preparation and fiber dispersion. However, the subsequent image analysis is frequently performed manually or semi-automatically, which either requires careful sample preparation or manual intervention in the image analysis and processing. In this article, an image processing and analysis method has been developed based on medial axis transformation via the multi-stencil fast marching method for fiber length measurements on acquired microscopy images. The developed method can be implemented fully automatically and without any user induced delays. This method offers high efficiency, sub-pixel accuracy, and excellent statistical representativity.

Microseismic Event Location by Considering the Influence of the Empty Area in an Excavated Tunnel.

The velocity model is a key factor that affects the accuracy of microseismic event location around tunnels. In this paper, we consider the effect of the empty area on the microseismic event location and present a 3D heterogeneous velocity model for excavated tunnels. The grid-based heterogeneous velocity model can describe a 3D arbitrarily complex velocity model, where the microseismic monitoring areas are divided into many blocks. The residual between the theoretical arrival time calculated by the fast marching method (FMM) and the observed arrival time is used to identify the block with the smallest residual. Particle swarm optimization (PSO) is used to improve the location accuracy in this block. Synthetic tests show that the accuracy of the microseismic event location based on the heterogeneous velocity model was higher than that based on the single velocity model, independent of whether an arrival time error was considered. We used the heterogeneous velocity model to locate 7 blasting events and 44 microseismic events with a good waveform quality in the Qinling No. 4 tunnel of the Yinhanjiwei project from 6 June 2017 to 13 June 2017 and compared the location results of the heterogeneous-velocity model with those of the single-velocity model. The results of this case study show that the events located by the heterogeneous velocity model were concentrated around the working face, which matched the actual conditions of the project, while the events located by the single-velocity model were scattered and far from the working face.

Local Competition-Based Superpixel Segmentation Algorithm in Remote Sensing.

Remote sensing technologies have been widely applied in urban environments' monitoring, synthesis and modeling. Incorporating spatial information in perceptually coherent regions, superpixel-based approaches can effectively eliminate the "salt and pepper" phenomenon which is common in pixel-wise approaches. Compared with fixed-size windows, superpixels have adaptive sizes and shapes for different spatial structures. Moreover, superpixel-based algorithms can significantly improve computational efficiency owing to the greatly reduced number of image primitives. Hence, the superpixel algorithm, as a preprocessing technique, is more and more popularly used in remote sensing and many other fields. In this paper, we propose a superpixel segmentation algorithm called Superpixel Segmentation with Local Competition (SSLC), which utilizes a local competition mechanism to construct energy terms and label pixels. The local competition mechanism leads to energy terms locality and relativity, and thus, the proposed algorithm is less sensitive to the diversity of image content and scene layout. Consequently, SSLC could achieve consistent performance in different image regions. In addition, the Probability Density Function (PDF), which is estimated by Kernel Density Estimation (KDE) with the Gaussian kernel, is introduced to describe the color distribution of superpixels as a more sophisticated and accurate measure. To reduce computational complexity, a boundary optimization framework is introduced to only handle boundary pixels instead of the whole image. We conduct experiments to benchmark the proposed algorithm with the other state-of-the-art ones on the Berkeley Segmentation Dataset (BSD) and remote sensing images. Results demonstrate that the SSLC algorithm yields the best overall performance, while the computation time-efficiency is still competitive.

Application of neuroanatomical features to tractography clustering.

Diffusion tensor imaging allows unprecedented insight into brain neural connectivity in vivo by allowing reconstruction of neuronal tracts via captured patterns of water diffusion in white matter microstructures. However, tractography algorithms often output hundreds of thousands of fibers, rendering subsequent data analysis intractable. As a remedy, fiber clustering techniques are able to group fibers into dozens of bundles and thus facilitate analyses. Most existing fiber clustering methods rely on geometrical information of fibers, by viewing them as curves in 3D Euclidean space. The important neuroanatomical aspect of fibers, however, is ignored. In this article, the neuroanatomical information of each fiber is encapsulated in the associativity vector, which functions as the unique "fingerprint" of the fiber. Specifically, each entry in the associativity vector describes the relationship between the fiber and a certain anatomical ROI in a fuzzy manner. The value of the entry approaches 1 if the fiber is spatially related to the ROI at high confidence; on the contrary, the value drops closer to 0. The confidence of the ROI is calculated by diffusing the ROI according to the underlying fibers from tractography. In particular, we have adopted the fast marching method for simulation of ROI diffusion. Using the associativity vectors of fibers, we further model fibers as observations sampled from multivariate Gaussian mixtures in the feature space. To group all fibers into relevant major bundles, an expectation-maximization clustering approach is employed. Experimental results indicate that our method results in anatomically meaningful bundles that are highly consistent across subjects.

Modeling the propagation of tumor fronts with shortest path and diffusion models-implications for the definition of the clinical target volume.

Objective.The overarching objective is to make the definition of the clinical target volume (CTV) in radiation oncology less subjective and more scientifically based. The specific objective of this study is to investigate similarities and differences between two methods that model tumor spread beyond the visible gross tumor volume (GTV): (1) the shortest path model, which is the standard method of adding a geometric GTV-CTV margin, and (2) the reaction-diffusion model.Approach.These two models to capture the invisible tumor 'fire front' are defined and compared in mathematical terms. The models are applied to example cases that represent tumor spread in non-uniform and anisotropic media with anatomical barriers.Main results.The two seemingly disparate models bring forth traveling waves that can be associated with the front of tumor growth outward from the GTV. The shape of the fronts is similar for both models. Differences are seen in cases where the diffusive flow is reduced due to anatomical barriers, and in complex spatially non-uniform cases. The diffusion model generally leads to smoother fronts. The smoothness can be controlled with a parameter defined by the ratio of the diffusion coefficient and the proliferation rate.Significance.Defining the CTV has been described as the weakest link of the radiotherapy chain. There are many similarities in the mathematical description and the behavior of the common geometric GTV-CTV expansion method, and the definition of the CTV tumor front via the reaction-diffusion model. Its mechanistic basis and the controllable smoothness make the diffusion model an attractive alternative to the standard GTV-CTV margin model.

Rapid global path planning algorithm for unmanned surface vehicles in large-scale and multi-island marine environments.

A global path planning algorithm for unmanned surface vehicles (USVs) with short time requirements in large-scale and complex multi-island marine environments is proposed. The fast marching method-based path planning for USVs is performed on grid maps, resulting in a decrease in computer efficiency for larger maps. This can be mitigated by improving the algorithm process. In the proposed algorithm, path planning is performed twice in maps with different spatial resolution (SR) grids. The first path planning is performed in a low SR grid map to determine effective regions, and the second is executed in a high SR grid map to rapidly acquire the final high precision global path. In each path planning process, a modified inshore-distance-constraint fast marching square (IDC-FM2) method is applied. Based on this method, the path portions around an obstacle can be constrained within a region determined by two inshore-distance parameters. The path planning results show that the proposed algorithm can generate smooth and safe global paths wherein the portions that bypass obstacles can be flexibly modified. Compared with the path planning based on the IDC-FM2 method applied to a single grid map, this algorithm can significantly improve the calculation efficiency while maintaining the precision of the planned path.

Accounting for uncertainties in the position of anatomical barriers used to define the clinical target volume.

The definition of the clinical target volume (CTV) is becoming the weakest link in the radiotherapy chain. CTV definition consensus guidelines include the geometric expansion beyond the visible gross tumor volume, while avoiding anatomical barriers. In a previous publication we described how to implement these consensus guidelines using deep learning and graph search techniques in a computerized CTV auto-delineation process. In this paper we address the remaining problem of how to deal with uncertainties in positions of the anatomical barriers. The objective was to develop an algorithm that implements the consensus guidelines on considering barrier uncertainties. Our approach is to perform multiple expansions using the fast marching method with barriers in place or removed at different stages of the expansion. We validate the algorithm in a computational phantom and compare manually generated with automated CTV contours, both taking barrier uncertainties into account.

Marine Applications of the Fast Marching Method.

Path planning is general problem of mobile robots, which has special characteristics when applied to marine applications. In addition to avoid colliding with obstacles, in marine scenarios, environment conditions such as water currents or wind need to be taken into account in the path planning process. In this paper, several solutions based on the Fast Marching Method are proposed. The basic method focus on collision avoidance and optimal planning and, later on, using the same underlying method, the influence of marine currents in the optimal path planning is detailed. Finally, the application of these methods to consider marine robot formations is presented.

An Inverse Eikonal Method for Identifying Ventricular Activation Sequences from Epicardial Activation Maps.

A key mechanism controlling cardiac function is the electrical activation sequence of the heart's main pumping chambers termed the ventricles. As such, personalization of the ventricular activation sequences is of pivotal importance for the clinical utility of computational models of cardiac electrophysiology. However, a direct observation of the activation sequence throughout the ventricular volume is virtually impossible. In this study, we report on a novel method for identification of activation sequences from activation maps measured at the outer surface of the heart termed the epicardium. Conceptually, the method attempts to identify the key factors governing the ventricular activation sequence - the timing of earliest activation sites (EAS) and the velocity tensor field within the ventricular walls - from sparse and noisy activation maps sampled from the epicardial surface and fits an Eikonal model to the observations. Regularization methods are first investigated to overcome the severe ill-posedness of the inverse problem in a simplified 2D example. These methods are then employed in an anatomically accurate biventricular model with two realistic activation models of varying complexity - a simplified trifascicular model (3F) and a topologically realistic model of the His-Purkinje system (HPS). Using epicardial activation maps at full resolution, we first demonstrate that reconstructing the volumetric activation sequence is, in principle, feasible under the assumption of known location of EAS and later evaluate robustness of the method against noise and reduced spatial resolution of observations. Our results suggest that the FIMIN algorithm is able to robustly recover the full 3D activation sequence using epicardial activation maps at a spatial resolution achievable with current mapping systems and in the presence of noise. Comparing the accuracy achieved in the reconstructed activation maps with clinical data uncertainties suggests that the FIMIN method may be suitable for the patient- specific parameterization of activation models.

Semi-automatic segmentation of whole-body images in longitudinal studies.

We propose a semi-automatic segmentation pipeline designed for longitudinal studies considering structures with large anatomical variability, where expert interactions are required for relevant segmentations. Our pipeline builds on the regularized Fast Marching (rFM) segmentation approach by Risseret al(2018). It consists in transporting baseline multi-label FM seeds on follow-up images, selecting the relevant ones and finally performing the rFM approach. It showed increased, robust and faster results compared to clinical manual segmentation. Our method was evaluated on 3D synthetic images and patients' whole-body MRI. It allowed a robust and flexible handling of organs longitudinal deformations while considerably reducing manual interventions.

Directional fast-marching and multi-model strategy to extract coronary artery centerlines.

BACKGROUND: Computed tomography angiography (CTA) is a non-invasive technique to image coronary arteries and evaluate coronary artery diseases (CAD). The diagnosis of CAD requires modeling anatomical structures and analyzing the function and pathology of the coronary arteries. Therefore, a robust and automated method for extracting reliable coronary artery centerlines is valuable in clinical practice. METHOD: We extracted coronary centerlines using the directional fast marching (DFM) method and improved DFM with a multi-model strategy. The method comprises model guidance, the application of vessel direction, and a multi-model strategy: (1) coronary models are constructed using registration techniques and then used as prior knowledge of the vessels; (2) the vessel direction, modified from the eigenvectors of the Hessian matrix and vesselness, is used to guide the search for the vessel points during fast marching; and (3) the multi-model strategy is applied to identify suboptimal results from the overall outcome as in multi-atlas segmentation. Overlap and accuracy metrics are used to assess the segmentation. The authors evaluated the performance of the proposed method on 32 CT cardiac angiography datasets from the Rotterdam Coronary Artery Algorithm Evaluation Framework (RCAAEF). The authors also studied the effect of models on DFM. RESULTS: For the quantitative evaluation, DFM improved the average overlap (OV) from 43.6% of a method without model information to 77.8%. In addition, with the ground truth delineated by experts, multi-model DFM (MM-DFM) obtained 83.5% average overlap (OV) in the training datasets and 86.6% in the test datasets. CONCLUSION: The authors propose a novel approach to extract coronary centerlines from CTA using DFM and further extend DFM to a multi-model strategy. DFM effectively applies the prior shape of the coronary vessels and vascular features within the target image and has the potential to achieve clinically relevant results.

FMST: an Automatic Neuron Tracing Method Based on Fast Marching and Minimum Spanning Tree.

Neuron reconstruction is an important technique in computational neuroscience. Although there are many reconstruction algorithms, few can generate robust results. In this paper, we propose a reconstruction algorithm called fast marching spanning tree (FMST). FMST is based on a minimum spanning tree method (MST) and improve its performance in two aspects: faster implementation and no loss of small branches. The contributions of the proposed method are as follows. Firstly, the Euclidean distance weight of edges in MST is improved to be a more reasonable value, which is related to the probability of the existence of an edge. Secondly, a strategy of pruning nodes is presented, which is based on the radius of a node's inscribed ball. Thirdly, separate branches of broken neuron reconstructions can be merged into a single tree. FMST and many other state of the art reconstruction methods were implemented on two datasets: 120 Drosophila neurons and 163 neurons with gold standard reconstructions. Qualitative and quantitative analysis on experimental results demonstrates that the performance of FMST is good compared with many existing methods. Especially, on the 91 fruitfly neurons with gold standard and evaluated by five metrics, FMST is one of two methods with best performance among all 27 state of the art reconstruction methods. FMST is a good and practicable neuron reconstruction algorithm, and can be implemented in Vaa3D platform as a neuron tracing plugin.