Seminar/2013-12-11

Mercredi 11 décembre 2013, 14h-15h30, Salle L0 du LRDE

A ``Diplomatic Parallel Algorithm for the Component Trees of High Dynamic Range Images

Michael Wilkinson - Johann Bernoulli Institute, University of Groningen, The Netherlands

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.

http://www.cs.rug.nl/~michael/