Path reducing watershed for the GPU

The watershed transform is a popular image segmentation procedure from mathematical morphology used in many applications of computer vision. This paper proposes a novel parallel watershed procedure designed for GPU implementation. Our algorithm constructs paths of steepest descent and reduces these paths into direct pointers to catchment basin minima in logarithmic time, also crucially incorporating successful resolution of plateaux. Three implementation variants and their parameters are analysed through experiments on 2D and 3D images; a comparison against the state-of-the-art shows a runtime improvement of around 30%. For 3D images of 128 megavoxels execution times of approximately 1.5–2 seconds are achieved