Fast Mean Shift with Accurate and Stable Convergence


Ping Wang, Dongryeol Lee, Alexander Gray, James M. Rehg ;
Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, PMLR 2:604-611, 2007.


Mean shift is a powerful but computationally expensive method for nonparametric clustering and optimization. It iteratively moves each data point to its local mean until convergence. We introduce a fast algorithm for computing mean shift based on the dual-tree. Unlike previous speed-up attempts, our algorithm maintains a relative error bound at each iteration, resulting in significantly more stable and accurate convergence. We demonstrate the benefit of our method in clustering experiments with real and synthetic data.

Related Material