Description:
The function MSFM2D/MSFM3D calculates the shortest distance from a list of points to all other pixels in an 2D or 3D image, using the Multistencil Fast Marching Method (MSFM). This method gives more accurate distances by using second order derivatives and cross neighbors.
The function SHORTESTPATH traces the shortest path from start point to source point using Runge Kutta 4 in the 2D or 3D distance map.
Implementation:
The 2D fast marching method is implemented in both Matlab-code and c-code. The c-code uses a custom build unsorted binary tree minimum search which out performs a normal binary sorted tree. The c-code is more than 500 times as fast as the matlab-code (compiled with the Microsoft Visual compiler).
Literature:
We used two papers:
- J. Andreas Baerentzen "On the implementation of fast marching methods for 3D lattices"
- M. Sabry Hassouna et al. "Multistencils Fast Marching Methods: A Highly Accurate Solution to the Eikonal Equation on Cartesian Domains"
We compared the results of our implementation with the results in the paper:
- Normal fast marching 1th order, exact the same results.
- 2th order, significant smaller errors than in the paper.
- Multistencil 1th order, larger errors than in the paper
- Multistencil 2th order, significant worse results than published in the paper.
We also compared our implementation with another independent implementation to see if we made some errors in the multistencil extension, but got exact the same results.
Conclusion, enable 2th order or Multistencil but not at the same time because it will not give better results, at least with our implementation.
Examples:
Compile the c-code with mex msfm2d.c; mex msfm3d.c; mex rk4.c;
Try the examples in the help of msfm2d and shortestpath
|
