Image segmentation using linked mean-shift vectors and its implementation on GPU

This paper proposes a new approach to meanshift- based image segmentation that uses a non-iterative process to determine the maxima of the underlying density, which are called modes. To identify the mode, the proposed approach performs a mean-shift process on each pixel only once, and uses the resulting mean-shift vectors to construct links for the pairs of pixels, instead of iteratively performing the mean-shift process. Then, it groups the pixels of the same mode, connected through the links, into the same cluster. Although the proposed approach performs the mean-shift process only once, it provides comparable segmentation quality to the conventional approaches. In experiments using benchmark images, the processing time was reduced to a quarter, while probabilistic rand index and segmentation covering were well maintained; they were degraded by only 0.38% and 1.87%, respectively. Furthermore, the proposed algorithm improves the locality of the required data and compute-intensity of the algorithm, which are important factors for utilizing the GPU effectively. The proposed algorithm, when implemented on a GPU, improved the processing speed by over 75 times compared to implementation on a CPU, while the conventional approach was accelerated by about 15 times.