MeanShift++: Extremely Fast Mode-Seeking With Applications to Segmentation and Object Tracking
This addresses the computational bottleneck for users of MeanShift in applications like image segmentation and object tracking, though it is an incremental improvement focused on speed.
The paper tackles the slow runtime of the MeanShift clustering algorithm by proposing MeanShift++, which uses a grid-based approach to accelerate mode-seeking, achieving over 10,000x speedup with competitive clustering results on benchmarks and nearly identical image segmentations.
MeanShift is a popular mode-seeking clustering algorithm used in a wide range of applications in machine learning. However, it is known to be prohibitively slow, with quadratic runtime per iteration. We propose MeanShift++, an extremely fast mode-seeking algorithm based on MeanShift that uses a grid-based approach to speed up the mean shift step, replacing the computationally expensive neighbors search with a density-weighted mean of adjacent grid cells. In addition, we show that this grid-based technique for density estimation comes with theoretical guarantees. The runtime is linear in the number of points and exponential in dimension, which makes MeanShift++ ideal on low-dimensional applications such as image segmentation and object tracking. We provide extensive experimental analysis showing that MeanShift++ can be more than 10,000x faster than MeanShift with competitive clustering results on benchmark datasets and nearly identical image segmentations as MeanShift. Finally, we show promising results for object tracking.