Abstract
In this paper we present a simple modification of the Fast Marching algorithm to speed up the computation using a heuristic. This modification leads to an algorithm that is similar in spirit to the A* algorithm used in artificial intelligence. Using a heuristic allows to extract geodesics from a single source to a single goal very quickly and with a low memory requirement. Any application that needs to compute a lot of geodesic paths can gain benefits from our algorithm. The computational saving is even more important for 3D medical images with tubular structures and for higher dimensional data.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Deschamps, T., Cohen, L.: Fast Extraction of Minimal Paths in 3D Images and Applications to Virtual Endoscopy. Medical Image Analysis 5 (2001)
Stout, W.B.: Smart moves: Intelligent path-finding. Game Developer (1996)
Sethian, J.: Level Sets Methods and Fast Marching Methods, 2nd edn. Cambridge University Press, Cambridge (1999)
Tsitsiklis, J.: Efficient Algorithms for Globally Optimal Trajectories. IEEE Trans. on Automatic Control 40, 1528–1538 (1995)
Cohen, L.D., Kimmel, R.: Global Minimum for Active Contour models: A Minimal Path Approach. International Journal of Computer Vision 24, 57–78 (1997)
Cohen, L.: Multiple Contour Finding and Perceptual Grouping Using Minimal Paths. Journal of Mathematical Imaging and Vision 14, 225–236 (2001)
Cormen, T.H., Leiserson, C.E., Rivest, R.R.: Introduction to Algorithms. MIT Press, Cambridge, Massachusetts (1990)
Kimmel, R., Amir, A., Bruckstein, A.M.: Finding shortest paths on surfaces using level sets propagation. IEEE Trans. on PAMI 17, 635–640 (1995)
Nilsson, N.: Problem-solving Methods in Artificial Intelligence. McGraw-Hill, New York (1971)
Korf, R.E.: Depth-first iterative-deepening: an optimal admissible tree search. Artif. Intell. 27, 97–109 (1985)
Droske, M., Meyer, M., Rumpf, M., Schaller, C.: An adaptive level set method for interactive segmentation of intracranial tumors. Neurosurgical Research 27 (2005)
Papandreou, G., Maragos, P.: A fast multigrid implicit algorithm for the evolution of geodesic active contours. In: CVPR 2004, vol. II, pp. 689–694 (2004)
Peyré, G.: Fast marching toolbox, available on Matlab Central (2005), http://www.mathworks.com/matlabcentral/
Rohnert, H.: Shortest paths in the plane with convex polygonal obstacles. Inf. Process. Lett. 23, 71–76 (1986)
Melchior, P., Orsoni, B., Lavialle, O., Poty, A., Oustaloup, A.: Consideration of obstacle danger level in path planning using a* and fast-marching optimisation: comparative study. Signal Processing 11, 2387–2396 (2003)
Kimmel, R., Sethian, J.A.: Optimal algorithm for shape from shading and path planning. Journal of Mathematical Imaging and Vision 14, 237–244 (2001)
Sun, C., Pallottino, S.: Circular shortest path in images. Pattern Recognition 36, 711–721 (2003)
Appleton, B., Talbot, H.: Globally optimal geodesic active contours. Journal of Mathematical Imaging and Vision (to appear, 2005)
Sethian, J., Kimmel, R.: Computing Geodesic Paths on Manifolds. Proc. Natl. Acad. Sci. 95, 8431–8435 (1998)
Hoppe, H.: Progressive meshes. In: Proc. of SIGGRAPH 1996, pp. 99–108 (1996)
Peyré, G., Cohen, L.D.: Geodesic Remeshing Using Front Propagation. In: Proc. IEEE Variational, Geometric and Level Set Methods 2003, pp. 33–40 (2003)
Floater, M.S., Hormann, K., Reimers, M.: Parameterization of Manifold Triangulations. In: Approximation Theory X: Abstract and Classical Analysis, pp. 197–209 (2002)
Surazhsky, V., Alliez, P., Gotsman, C.: Isotropic remeshing of surfaces: a local parameterization approach. In: Proceedings of 12th International Meshing Roundtable (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Peyré, G., Cohen, L. (2005). Heuristically Driven Front Propagation for Geodesic Paths Extraction. In: Paragios, N., Faugeras, O., Chan, T., Schnörr, C. (eds) Variational, Geometric, and Level Set Methods in Computer Vision. VLSM 2005. Lecture Notes in Computer Science, vol 3752. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11567646_15
Download citation
DOI: https://doi.org/10.1007/11567646_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29348-4
Online ISBN: 978-3-540-32109-5
eBook Packages: Computer ScienceComputer Science (R0)