MeanShift++: Extremely Fast Mode-Seeking With Applications to Segmentation and Object Tracking

Abstract

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.

References in corpus (7)

• scikit-image: Image processing in Python
• OpenML: networked science in machine learning
• Deep Mean-Shift Priors for Image Restoration
• Image Restoration using Autoencoding Priors
• On the Convergence of the Mean Shift Algorithm in the One-Dimensional Space
• Chernoff-Hoeffding Inequality and Applications
• Statistical Inference Using Mean Shift Denoising