Nothing Special   »   [go: up one dir, main page]

Skip to main content

Heuristically Driven Front Propagation for Geodesic Paths Extraction

  • Conference paper
Variational, Geometric, and Level Set Methods in Computer Vision (VLSM 2005)

Part of the book series: Lecture Notes in Computer Science ((LNIP,volume 3752))

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Deschamps, T., Cohen, L.: Fast Extraction of Minimal Paths in 3D Images and Applications to Virtual Endoscopy. Medical Image Analysis 5 (2001)

    Google Scholar 

  2. Stout, W.B.: Smart moves: Intelligent path-finding. Game Developer (1996)

    Google Scholar 

  3. Sethian, J.: Level Sets Methods and Fast Marching Methods, 2nd edn. Cambridge University Press, Cambridge (1999)

    Google Scholar 

  4. Tsitsiklis, J.: Efficient Algorithms for Globally Optimal Trajectories. IEEE Trans. on Automatic Control 40, 1528–1538 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  5. Cohen, L.D., Kimmel, R.: Global Minimum for Active Contour models: A Minimal Path Approach. International Journal of Computer Vision 24, 57–78 (1997)

    Article  Google Scholar 

  6. Cohen, L.: Multiple Contour Finding and Perceptual Grouping Using Minimal Paths. Journal of Mathematical Imaging and Vision 14, 225–236 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  7. Cormen, T.H., Leiserson, C.E., Rivest, R.R.: Introduction to Algorithms. MIT Press, Cambridge, Massachusetts (1990)

    MATH  Google Scholar 

  8. Kimmel, R., Amir, A., Bruckstein, A.M.: Finding shortest paths on surfaces using level sets propagation. IEEE Trans. on PAMI 17, 635–640 (1995)

    Google Scholar 

  9. Nilsson, N.: Problem-solving Methods in Artificial Intelligence. McGraw-Hill, New York (1971)

    Google Scholar 

  10. Korf, R.E.: Depth-first iterative-deepening: an optimal admissible tree search. Artif. Intell. 27, 97–109 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  11. Droske, M., Meyer, M., Rumpf, M., Schaller, C.: An adaptive level set method for interactive segmentation of intracranial tumors. Neurosurgical Research 27 (2005)

    Google Scholar 

  12. 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)

    Google Scholar 

  13. Peyré, G.: Fast marching toolbox, available on Matlab Central (2005), http://www.mathworks.com/matlabcentral/

  14. Rohnert, H.: Shortest paths in the plane with convex polygonal obstacles. Inf. Process. Lett. 23, 71–76 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  15. 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)

    Article  Google Scholar 

  16. Kimmel, R., Sethian, J.A.: Optimal algorithm for shape from shading and path planning. Journal of Mathematical Imaging and Vision 14, 237–244 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  17. Sun, C., Pallottino, S.: Circular shortest path in images. Pattern Recognition 36, 711–721 (2003)

    Article  Google Scholar 

  18. Appleton, B., Talbot, H.: Globally optimal geodesic active contours. Journal of Mathematical Imaging and Vision (to appear, 2005)

    Google Scholar 

  19. Sethian, J., Kimmel, R.: Computing Geodesic Paths on Manifolds. Proc. Natl. Acad. Sci. 95, 8431–8435 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  20. Hoppe, H.: Progressive meshes. In: Proc. of SIGGRAPH 1996, pp. 99–108 (1996)

    Google Scholar 

  21. Peyré, G., Cohen, L.D.: Geodesic Remeshing Using Front Propagation. In: Proc. IEEE Variational, Geometric and Level Set Methods 2003, pp. 33–40 (2003)

    Google Scholar 

  22. Floater, M.S., Hormann, K., Reimers, M.: Parameterization of Manifold Triangulations. In: Approximation Theory X: Abstract and Classical Analysis, pp. 197–209 (2002)

    Google Scholar 

  23. Surazhsky, V., Alliez, P., Gotsman, C.: Isotropic remeshing of surfaces: a local parameterization approach. In: Proceedings of 12th International Meshing Roundtable (2003)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics