Clustering via Geometric Median-Shift over Riemannian Manifolds

The mean shift algorithms have been successfully applied to many areas, such as data clustering, feature analysis, and image segmentation. However, they still have two limitations. One is that they are ineffective in clustering data with low dimensional manifolds because of the use of the Euclidean distance for calculating distances. The other is that they sometimes produce poor results for data clustering and image segmentation. This is because a mean may not be a point in a data set. In order to overcome the two limitations, we propose a novel approach for the median shift over Riemannian manifolds that uses the geometric median and geodesic distances. Unlike the mean, the geometric median of a data set is one of points in the set. Compared to the Euclidean distance, the geodesic distances can better describe data points distributed on Riemannian manifolds. Based on these two facts, we first present a novel density function that characterizes points on a manifold with the geodesic distance. The shift of the geometric median over the Riemannian manifold is derived from maximizing this density function. After this, we present an algorithm for geometric median shift over Riemannian manifolds, together with theoretical proofs of its correctness. Extensive experiments have demonstrated that our method outperforms the state-of-the-art algorithms in data clustering, image segmentation, and noise filtering on both synthetic data sets and real image databases.