Paris, S., Durand, F.: A topological approach to hierarchical segmentation using mean shift. IEEE Neural Networks for Signal Processing Workshop (1999) Mika, S., Rätsch, G., Weston, J., Schölkopf, B., Müller, K.-R.: Fisher discriminant analysis with kernels. Lowe, D.: Implementation of the scale invariant feature transform (2007), Koontz, W.L.G., Narendra, P., Fukunaga, K.: A graph-theoretic approach to nonparametric cluster analyisis. Knuth, D.: The Art of Computer Programming: Seminumerical Algorithms, 3rd edn., vol. 2 (1998) Hein, M., Bousquet, O.: Hilbertian metrics and positive definite kernels on probability measures. Grauman, K., Darrell, T.: Unsupervised learning of categories from sets of partially matching image features. Journal of Machine Learninig Research (2001)įukunaga, K., Hostler, L.D.: The estimation of the gradient of a density function, with applications in pattern recognition. ECCV (2004)įine, S., Scheinberg, K.: Efficient SVM training using low-rank kernel representations. ICCV (2001)Ĭsurka, G., Dance, C.R., Dan, L., Willamowski, J., Bray, C.: Visual categorization with bags of keypoints. PAMI 24(5) (2002)Ĭomaniciu, D., Ramesh, V., Meer, P.: The variable bandwidth mean shift and data-driven scale selection. Pattern Recognition (2006)Ĭomaniciu, D., Meer, P.: Mean shift: A robust approach toward feature space analysis. ICML (2006)Ĭheng, Y.: Mean shift, mode seeking, and clustering. Journal of Machine Learninig Research 3(1) (2002)Ĭarreira-Perpiñán, M.: Fast nonparametric clustering with gaussian blurring mean-shift. This process is experimental and the keywords may be updated as the learning algorithm improves.īach, F.R., Jordan, M.I.: Kernel independent componet analysis. These keywords were added by machine and not by the authors. We illustrate our algorithms to clustering data on manifolds, image segmentation, and the automatic discovery of visual categories. We also show that the accelerated medoid shift can be used to initialize mean shift for increased efficiency.

Like medoid shift, quick shift operates in non-Euclidean spaces in a straightforward manner. We propose remedies for this problem, by introducing a novel, simple and extremely efficient clustering algorithm, called quick shift, that explicitly trades off under- and over-fragmentation. Finally, we show that, under certain conditions, medoid shift fails to cluster data points belonging to the same mode, resulting in over-fragmentation. We then exploit kernel methods to extend both mean shift and the improved medoid shift to a large family of distances, with complexity bounded by the effective rank of the resulting kernel matrix, and with explicit regularization constraints. This makes medoid shift considerably faster than mean shift, contrarily to what previously believed. We show that the complexity of the recently introduced medoid-shift algorithm in clustering N points is O( N 2), with a small constant, if the underlying distance is Euclidean.

B and m quickshift