Fast Mean Shift with Accurate and Stable Convergence

Ping Wang, Dongryeol Lee, Alexander Gray, James M. Rehg; JMLR W&P 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.