Distributed bucket processing: A paradigm embedded in a framework for the parallel processing of pixel sets

Large datasets, such as pixels and voxels in 2D and 3D images can usually be reduced during their processing to smaller subsets with less datapoints. Such subsets can be the objects in the image, features – edges or corners – or more general, regions of interest. For instance, the transformation from a set of datapoints representing an image, to one or more subsets of datapoints representing objects in the image, is due to a segmentation algorithm and may involve both the selection of datapoints as well as a change in datastructure. The massive number of pixels in the original image, points to a data parallel approach, whereas the processing of the various objects in the image is more suitable for task parallelism. In this paper we introduce a framework for parallel image processing and we focus on an array of buckets that can be distributed over a number of processors and that contains pointers to the data from the dataset. The benefit of this approach is that the processor activity remains focussed on the datapoints that need processing and, moreover, that the load can be distributed over many processors, even in a heterogeneous computer architecture. Although the method is generally applicable in the processing of sets, in this paper we obtain our examples from the domain of image processing. As this method yields speedups that are data dependent, we derived a run-time evaluation that is able to determine if the use of distributed buckets is beneficial.