Technical Reports
HPL-2009-217
Click here for full text:
Fast Mean Shift by Compact Density Representation
Freedman, Daniel; Kisilev, Pavel
HP Laboratories
HPL-2009-217
Keyword(s): clustering, fast algorithm, mean shift, sampling
Abstract: The Mean Shift procedure is a well established clustering technique that is widely used in imaging applications such as image and video segmentation, denoising, object tracking, texture classification, and others. However, the Mean Shift procedure has relatively high time complexity which is superlinear in the number of data points. In this paper we present a novel fast Mean Shift procedure which is based on the random sampling of the Kernel Density Estimate (KDE). We show theoretically that the resulting reduced KDE is close to the complete data KDE, to within a given accuracy. Moreover, we prove that the time complexity of the proposed fast Mean Shift procedure based on the reduced KDE is considerably lower than that of the original Mean Shift; the typical gain is of several orders for big data sets. Experiments show that image and video segmentation results of the proposed fast Mean Shift method are similar to those based on the standard Mean shift procedure. We also present a new application of the Fast Mean Shift method to the efficient construction of graph hierarchies for images; the resulting structure is potentially useful for solving computer vision problems which can be posed as graph problems, including stereo, semi-automatic segmentation, and optical flow.
8 Pages
Additional Publication Information: To be published in DCC (Snowbird, UT); CVPR (Miami Beach, FL), DCC 2009, CVPR 2009
External Posting Date: September 6, 2009 [Fulltext]. Approved for External Publication
Internal Posting Date: September 6, 2009 [Fulltext]