A Fast O(N) Implementation of the Fast Marching Algorithm
Liron
Yatziv, Alberto Bartesaghi and Guillermo
Sapiro.
Journal of Computational Physics, vol. 212, pp. 393-399, 2006
A Fast O(N) Implementation of the Fast Marching AlgorithmLiron
Yatziv, Alberto Bartesaghi and Guillermo
Sapiro. |
|
In this note we present an implementation of the fast marching algorithm for solving Eikonal equations that reduces the original run-time from O(N log N) 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.
O_N_fast_marching.pdf (507 KB) updated 07/1/05
bibtex entry
Time Measurements
| Experiment | Image Size | Number of pixels | Measurement Run-Time* [Seconds] | |
|
P3 1.2 GHz |
P4 2 GHz |
|||
| Maze | 770x1053 | 810,810 | 0.601 | 0.240 |
| Lake | 1163x1463 | 1,701,469 | 1.552 | 0.591 |
| Random Uniform |
2000x2000 |
4,000,000 | 2.354 | 1.212 |
| Random Normal |
2000x2000 |
4,000,000 | 2.344 | 1.261 |
| F=1 |
2000x2000 |
4,000,000 | 2.313 | 1.282 |
* Using our implementation, the time required to compute distance map for the whole image from a single seed.
| back |