A sufficient condition for the convergence of the mean shift algorithm with Gaussian kernel

Highlights

• Incompleteness of the previous proofs for the convergence of MS algorithm is reviewed.

• I showed the gradient function is always nonzero outside the convex hull of the data.

• The convergence of the MS algorithm with isolated stationary points is proved.

• A sufficient condition for Gaussian KDE to have isolated stationary points is given.

Abstract

The mean shift (MS) algorithm is a non-parametric, iterative technique that has been used to find modes of an estimated probability density function (pdf). Although the MS algorithm has been widely used in many applications, such as clustering, image segmentation, and object tracking, a rigorous proof for its convergence is still missing. This paper tries to fill some of the gaps between theory and practice by presenting specific theoretical results about the convergence of the MS algorithm. To achieve this goal, first we show that all the stationary points of an estimated pdf using a certain class of kernel functions are inside the convex hull of the data set. Then the convergence of the sequence generated by the MS algorithm for an estimated pdf with isolated stationary points will be proved. Finally, we present a sufficient condition for the estimated pdf using the Gaussian kernel to have isolated stationary points.