α-MeanShift plus plus : Improving MeanShift plus plus for Image Segmentation

MeanShift is one of the popular clustering algorithms and can be used to partition a digital image into semantically meaningful regions in an unsupervised manner. However, due to its prohibitively high computational complexity, a grid-based approach, called MeanShift++, has recently been proposed and succeeded to surprisingly reduce the computational complexity of MeanShift. Nevertheless, we found that MeanShift++ still has computational redundancy and there is room for improvement in terms of accuracy and runtime; thus, we propose an improvement to MeanShift++, named alpha-MeanShift++. We first attempt to minimize the computational redundancy by using an additional hash table. Then, we introduce a speedup factor (alpha) to reduce the number of iterations required until convergence, and we use more neighboring grid cells for the same bandwidth to improve accuracy. Through intensive experiments on image segmentation benchmark datasets, we demonstrate that alpha-MeanShift++ can run 4.1-4.6 x faster on average (but up to 7 x) than MeanShift CC and achieve better image segmentation quality.

Automated summary

MeanShift++ is an improved clustering algorithm that can partition a digital image faster and with higher accuracy compared to MeanShift. It minimizes computational redundancy by introducing a hash table and a speedup factor to reduce the number of iterations required for convergence.