This paper presents a new algorithm for the fast, shared memory, multi-core computation of augmented contour trees on triangulations. In contrast to most existing parallel algorithms our technique computes augmented trees, enabling the full extent of contour tree based applications including data segmentation. Our approach completely revisits the traditional, sequential contour tree algorithm to re-formulate all the steps of the computation as a set of independent local tasks. This includes a new computation procedure based on Fibonacci heaps for the join and split trees, two intermediate data structures used to compute the contour tree, whose constructions are efficiently carried out concurrently thanks to the dynamic scheduling of task parallelism. We also introduce a new parallel algorithm for the combination of these two trees into the output global contour tree. Overall, this results in superior time performance in practice, both in sequential and in parallel thanks to the OpenMP task runtime. We report performance numbers that compare our approach to reference sequential and multi-threaded implementations for the computation of augmented merge and contour trees. These experiments demonstrate the run-time efficiency of our approach and its scalability on common workstations. We demonstrate the utility of our approach in data segmentation applications.

Angiographic imaging is a crucial domain of medical imaging. In particular, Magnetic Resonance Angiography (MRA) is used for both clinical and research purposes. This article presents the first framework geared toward the design of virtual MRA images from real MRA images. It relies on a pipeline that involves image processing, vascular modeling, computational fluid dynamics and MR image simulation, with several purposes. It aims to provide to the whole scientific community (1) software tools for MRA analysis and blood flow simulation; and (2) data (computational meshes, virtual MRAs with associated ground truth), in an open-source/open-data paradigm. Beyond these purposes, it constitutes a versatile tool for progressing in the understanding of vascular networks, especially in the brain, and the associated imaging technologies. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.