MultiStencils Fast Marching Methods: A Highly Accurate Solution to the Eikonal Equation on Cartesian Domains

A wide range of computer vision applications require an accurate solution of a particular Hamilton-Jacobi (HJ) equation known as the Eikonal equation. In this paper, we propose an improved version of the fast marching method (FMM) that is highly accurate for both 2D and 3D Cartesian domains. The new...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on pattern analysis and machine intelligence 2007-09, Vol.29 (9), p.1563-1574
Main Authors: Hassouna, M.S., Farag, A.A.
Format: Article
Language:English
Subjects:
Application software
Applied sciences
Artificial intelligence
Cartesian
Computer science
control theory
systems
Computer vision
Derivatives
Eikonal equation
Exact sciences and technology
fast marching methods
Grid computing
Iterative algorithms
Level set
level set methods
Mathematical analysis
Mathematical models
monotonically advancing fronts
Multi-stencils fast marching methods
Nonlinear equations
Partial differential equations
Path planning
Pattern analysis
Pattern recognition. Digital image processing. Computational geometry
Shape
Studies
Three dimensional
Tracking
Two dimensional
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A wide range of computer vision applications require an accurate solution of a particular Hamilton-Jacobi (HJ) equation known as the Eikonal equation. In this paper, we propose an improved version of the fast marching method (FMM) that is highly accurate for both 2D and 3D Cartesian domains. The new method is called multistencils fast marching (MSFM), which computes the solution at each grid point by solving the Eikonal equation along several stencils and then picks the solution that satisfies the upwind condition. The stencils are centered at each grid point and cover its entire nearest neighbors. In 2D space, two stencils cover 8-neighbors of the point, whereas in 3D space, six stencils cover its 26-neighbors. For those stencils that are not aligned with the natural coordinate system, the Eikonal equation is derived using directional derivatives and then solved using higher order finite difference schemes. The accuracy of the proposed method over the state-of-the-art FMM-based techniques has been demonstrated through comprehensive numerical experiments.
ISSN:0162-8828
1939-3539
DOI:10.1109/TPAMI.2007.1154