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

arXiv: https://arxiv.org/abs/2104.00303 · HTML: https://mlsanity.com/paper/2104.00303/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 103 references that are in the map.
- First posted on arXiv 1 Apr 2021.

## Builds on (most cited first, 10 of 10)

- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [A Tutorial on Kernel Density Estimation and Recent Advances](https://mlsanity.com/paper/1704.03924/) (2017)
- [Deep Mean-Shift Priors for Image Restoration](https://mlsanity.com/paper/1709.03749/) (2017)
- [DBSCAN++: Towards fast and scalable density clustering](https://mlsanity.com/paper/1810.13105/) (2018)
- [Quickshift++: Provably Good Initializations for Sample-Based Mean Shift](https://mlsanity.com/paper/1805.07909/) (2018)
- [Image Restoration using Autoencoding Priors](https://mlsanity.com/paper/1703.09964/) (2017)
- [On the Consistency of Quick Shift](https://mlsanity.com/paper/1710.10646/) (2017)
- [On the Convergence of the Mean Shift Algorithm in the One-Dimensional Space](https://mlsanity.com/paper/1407.2961/) (2014)
- [On the Convergence and Consistency of the Blurring Mean-Shift Process](https://mlsanity.com/paper/1305.1040/) (2013)
- [Statistical Inference Using Mean Shift Denoising](https://mlsanity.com/paper/1610.03927/) (2016)

## Built on by (most cited first, 9 of 9)

- [Contrastive Mean-Shift Learning for Generalized Category Discovery](https://mlsanity.com/paper/2404.09451/) (2024)
- [Probabilistic Point Cloud Modeling via Self-Organizing Gaussian Mixture Models](https://mlsanity.com/paper/2302.00047/) (2023)
- [GridShift: A Faster Mode-seeking Algorithm for Image Segmentation and Object Tracking](https://mlsanity.com/paper/2206.02200/) (2022)
- [Clustering by Hill-Climbing: Consistency Results](https://mlsanity.com/paper/2202.09023/) (2022)
- [Unleashing the Potential of All Test Samples: Mean-Shift Guided Test-Time Adaptation](https://mlsanity.com/paper/2507.00462/) (2025)
- [Incomplete Gamma Kernels: Generalizing Locally Optimal Projection Operators](https://mlsanity.com/paper/2205.01087/) (2022)
- [Bagged k-Distance for Mode-Based Clustering Using the Probability of Localized Level Sets](https://mlsanity.com/paper/2210.09786/) (2022)
- [Category Level 6D Object Pose Estimation from a Single RGB Image using Diffusion](https://mlsanity.com/paper/2412.11420/) (2024)
- [Almost Linear Time Consistent Mode Estimation and Quick Shift Clustering](https://mlsanity.com/paper/2503.07995/) (2025)

## Abstract (arXiv)

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.