19 Nov
2013
19 Nov
'13
2:17 p.m.
Chers collègues,
La deuxième session du séminaire Performance et Généricité du LRDE
(Laboratoire de Recherche et Développement de l'EPITA) du mois de décembre aura lieu
le
Mercredi 11 décembre 2013 (14h--15h30), Salle L0 du LRDE.
Au programme:
* 14h-15h30: A ``Diplomatic'' Parallel Algorithm for the Component Trees of High
Dynamic Range Images
-- Michael Wilkinson --- Johann Bernoulli Institute, University of Groningen, The
Netherlands
http://www.cs.rug.nl/~michael/
Component trees are essential tools in several morphological processing
methods, such as attribute filtering, or visualization, or the
computation of topological watersheds. Algorithms for computation of
these trees fall into two main categories: (i) Flood-filling algorithms,
exemplified by the algorithms of Salembier et al (1998), Hesselink
(2003), and Wilkinson (2011), and (ii) Union-find methods, such as
Najman and Couprie (2006), and Berger et al (2007). As images become
larger, and parallel computers become commonplace, there is an increased
need for concurrent algorithms to compute these trees. The first such
algorithm was published by Wilkinson et al in 2008, and was based on the
divide-and-conquer principle. It splits up the data spatially, computes
local component trees using any arbitrary algorithm which yields a
union-find type representation of each node, and glues these together
hierarchically. The main drawback of this method is that it does not
work well on high-dynamic-range images, because the complexity of the
glueing phase scales linearly with the number of grey levels.
In the current work, carried out by Moschini, Meijster, and Wilkinson
within the HyperGAMMA project, we develop a new algorithm for floating
point or high-dynamic-range integer images. It works in a two-tier
process, in which we first compute a pilot component tree at low dynamic
range in parallel, with one grey level per processor using dynamic
quantization, and Salembier's flood-filling method to build the local
trees, and the previous parallellization scheme. After this, a
refinement stage is performed. This refinement stage is based on the
algorithm of Berger et al. As such, the new algorithm combines the two
main types of algorithm in a single framework.
Timings on images of up to 3.9 GPixel indicate a speed-up of up to 22 on
64 cores. The algorithm is more than 14x faster than the fastest
sequential algorithm on the same machine. We will apply the new
algorithm to astronomical data sets, including improvements to the
SExtractor tool for object detection. The importance of the new
algorithm extends beyond computation of component trees because it
allows development of a fast alpha-tree algorithm suitable for any
pixel-difference metric in case of vector images (i.e. not just
$L_\infty$-based metrics on low dynamic range colour images).
-- Michael Wilkinson obtained an MSc in astronomy from the Kapteyn
Laboratory, University of Groningen in 1993, after which he worked on
image analysis of intestinal bacteria at the Department of Medical
Microbiology, University of Groningen, obtaining a PhD at the Institute
of Mathematics and Computing Science, also in Groningen, in 1995. After
this he worked as a researcher at the Johann Bernoulli Institute for
Mathematics and Computer Science (JBI) both on computer simulations and
on image analysis of diatoms. He is currently senior lecturer at the
JBI, working on morphological image analysis and especially connected
morphology. Apart from publishing in many journals and conferences, he
edited the book ``Digital Image Analysis of Microbes'' (John Wiley, UK,
1998) with Frits Schut, and is member of the Steering Committee of ISMM.
Pour plus de renseignements, consultez http://seminaire.lrde.epita.fr/.
L'entrée du séminaire est libre. Merci de bien vouloir diffuser cette
information le plus largement possible.
--
Akim Demaille
Akim.Demaille(a)lrde.epita.fr
_______________________________________________
Seminaire mailing list
Seminaire(a)lrde.epita.fr
https://lists.lrde.epita.fr/listinfo/seminaire