Heuristically Driven Front Propagation for Fast Geodesic Extraction
Cohen, Laurent D.; Peyré, Gabriel (2008), Heuristically Driven Front Propagation for Fast Geodesic Extraction, International Journal for Computational Vision and Biomechanics, 1, 1, p. 55-67
TypeArticle accepté pour publication ou publié
External document linkhttp://hal.archives-ouvertes.fr/hal-00365292/en/
Journal nameInternational Journal for Computational Vision and Biomechanics
MetadataShow full item record
Abstract (EN)This paper presents a new method to quickly extract geodesic paths on images and 3D meshes. We use a heuristic to drive the front propagation procedure of the classical Fast Marching. This results in a modification of the Fast Marching algorithm that is similar to the A$^*$ algorithm used in artificial intelligence. In order to find very quickly geodesic paths between any given pair of points, two methods are proposed to devise an heuristic that restrict the front propagation. The multiresolition heuristic computes the heuristic using a propagation on a coarse map. For applications where pre-computation is acceptable, the landmark-based heuristic pre-computes distance maps to a sparse set of landmark points. We introduce various distortion metrics in order to quantify the errors introduced by the heuristically driven propagations. We show that both heuristic approaches bring a large speed-up for large scale applications that require the extraction of geodesics on images and 3D meshes.
Subjects / Keywordsgeodesics; A* algorithm; heuristic; shortest paths; Fast Marching
Showing items related by title and author.
Segmentation of 3D tubular objects with adaptive front propagation and minimal tree extraction for 3D medical imaging Deschamps, Thomas; Cohen, Laurent D. (2007) Article accepté pour publication ou publié