Multistencils fast marching methods: A highly accurate solution to the eikonal equation on Cartesian domains

被引:248
作者
Hassouna, M. Sabry [1 ]
Farag, Aly A. [1 ]
机构
[1] Univ Louisville, Dept Elect & Comp Engn, Comp Vis & Image Proc Lab, Louisville, KY 40292 USA
基金
美国国家科学基金会;
关键词
multistencils fast marching methods; monotonically advancing fronts; fast marching methods; level set methods; Eikonal equation;
D O I
10.1109/TPAMI.2007.1154
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:1563 / 1574
页数:12
相关论文
共 38 条
[1]  
Abd El Munim HE, 2005, IEEE I CONF COMP VIS, P930
[2]   A FAST LEVEL SET METHOD FOR PROPAGATING INTERFACES [J].
ADALSTEINSSON, D ;
SETHIAN, JA .
JOURNAL OF COMPUTATIONAL PHYSICS, 1995, 118 (02) :269-277
[3]  
Bouix S, 2003, PROC CVPR IEEE, P449
[4]   Registration of medical images using an interpolated closest point transform: Method and validation [J].
Cao, ZJ ;
Pan, SY ;
Li, R ;
Balachandran, R ;
Fitzpatrick, MJ ;
Chapman, WC ;
Dawant, BM .
MEDICAL IMAGING 2003: IMAGE PROCESSING, PTS 1-3, 2003, 5032 :325-333
[5]  
CERVENY V, 1985, J GEOPHYS-Z GEOPHYS, V58, P2
[6]   A simple level set method for solving Stefan problems [J].
Chen, S ;
Merriman, B ;
Osher, S ;
Smereka, P .
JOURNAL OF COMPUTATIONAL PHYSICS, 1997, 135 (01) :8-29
[7]   Some improvements of the fast marching method [J].
Chopp, DL .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2001, 23 (01) :230-244
[8]  
Danielsson PE, 2003, LECT NOTES COMPUT SC, V2749, P1154
[9]  
Deschamps T, 2002, INT C PATT RECOG, P731, DOI 10.1109/ICPR.2002.1044862
[10]  
Dijkstra E.W., 1959, Numerische mathematik, V1, P269, DOI [10.1007/BF01386390, DOI 10.1007/BF01386390]