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