Fast Mean Shift with Accurate and Stable Convergence

[edit]

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.

Abstract

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