Parallel algorithms for image processing: practical algorithms with experiments

We design and analyse parallel algorithms with the goal of obtaining exact bounds on their speed-ups on real machines. For this purpose, we employ the BSP* model, which is an extension of Valiant´s (1994) BSP (bulk-synchronous parallel) model and rewards blockwise communication. Further, we use Valiant´s notion of c-optimality. Intuitively, the speed-up of a c-optimal parallel algorithm for p processors tends to p/c, where the communication time is asymptotically smaller than the computation time. We consider a basic problem in image processing, viz. connected component labeling for 2D and 3D images. Our algorithms are randomized and 2-optimal with high probability for a wide range of BSP* parameters where the range becomes larger with growing input sizes. Our algorithms improve on previous results as they either need an asymptotically smaller amount of data to be communicated or fewer communication rounds. We further report on implementation work and experiments