{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T21:34:30Z","timestamp":1791063270656,"version":"4.1.0"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Imaging Sci."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>The kernel density estimate (KDE) is a nonparametric density estimate which has broad application in computer vision and pattern recognition. In particular, the mean shift procedure uses the KDE structure to cluster or segment data, including images and video. The usefulness of these twin techniques\u2014KDE and mean shift\u2014on large data sets is hampered by the large space or description complexity of the KDE, which in turn leads to a large time complexity of the mean shift procedure that is superlinear in the number of points. In this paper, we propose a sampling technique for KDE paring, i.e., the construction of a compactly represented KDE with much smaller description complexity. We prove that this technique has good properties in that the pared-down KDE so constructed is close to the original KDE in a precise mathematical sense. We then show how to use this pared-down KDE to devise a considerably faster mean shift algorithm, whose time complexity we analyze formally. 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, with the typical speed-up several orders of magnitude for large data sets. Finally, we present an application of the fast mean shift method to the efficient construction of multiscale graph structures for images, which can be used as a preprocessing step for more sophisticated segmentation algorithms.<\/jats:p>","DOI":"10.1137\/090765158","type":"journal-article","created":{"date-parts":[[2010,11,2]],"date-time":"2010-11-02T18:32:28Z","timestamp":1288722748000},"page":"878-903","source":"Crossref","is-referenced-by-count":7,"title":["KDE Paring and a Faster Mean Shift Algorithm"],"prefix":"10.1137","volume":"3","author":[{"given":"Daniel","family":"Freedman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pavel","family":"Kisilev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,11,2]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"S. Alpert, M. Galun, R. Basri, and A. Brandt,\n                      Image segmentation by probabilistic bottom-up aggregation and cue integration\n                      , in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'07), 2007.","DOI":"10.1109\/CVPR.2007.383017"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/j.imavis.2003.08.005"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/34.400568"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"C. Christoudias, B. Georgescu, and P. Meer,\n                      Synergism in low level vision\n                      , in Proceedings of the 16th International Conference on Pattern Recognition, IEEE Computer Society, Washington, DC, 2002, pp. 150\u2013155.","DOI":"10.1109\/ICPR.2002.1047421"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1177159"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/34.1000236"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"D. Comaniciu and V. Ramesh,\n                      Mean shift and optimal prediction for efficient object tracking\n                      , in Proceedings of the IEEE International Conference on Image Processing, Vol. 3, 2000, pp. 70\u201373.","DOI":"10.1109\/ICIP.2000.899297"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1195991"},{"key":"R10","unstructured":"D. DeMenthon,\n                      Spatio-temporal segmentation of video by hierarchical mean shift analysis\n                      , in Proceedings of the Statistical Methods in Video Processing Workshop, 2002."},{"key":"R11","unstructured":"L. Devroye and L. Gy\u00f6rfi,\n                      Nonparametric Density Estimation: The $L_1$ View\n                      , John Wiley & Sons, New York, 1985."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000022288.19776.77"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"D. Freedman and P. Kisilev,\n                      Fast mean shift by compact density representation\n                      , in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'09), 2009, pp. 1818\u20131825.","DOI":"10.1109\/CVPR.2009.5206716"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055330"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"B. Georgescu, I. Shimshoni, and P. Meer,\n                      Mean shift based clustering in high dimensions: A texture classification example\n                      , in Proceedings of the Ninth International Conference on Computer Vision, IEEE Computer Society, Washington, DC, 2003, pp. 456\u2013463.","DOI":"10.1109\/ICCV.2003.1238382"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.100"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF00202757"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"H. Guo, P. Guo, and H. Lu,\n                      A fast mean shift procedure with new iteration strategy and re-sampling\n                      , in Proceedings of the IEEE International Conference on Systems, Man and Cybernetics (SMC'06), Vol. 3, 2006, pp. 2385\u20132389.","DOI":"10.1109\/ICSMC.2006.385220"},{"key":"R19","unstructured":"A. Hatcher,\n                      Algebraic Topology\n                      , Cambridge University Press, Cambridge, UK, 2002."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"X. He, R. Zemel, and D. Ray,\n                      Learning and incorporating top-down cues in image segmentation\n                      , in Proceedings of the European Conference on Computer Vision, Lecture Notes in Comput. Sci. 3951, Springer-Verlag, Berlin, 2006, pp. 338\u2013351.","DOI":"10.1007\/11744023_27"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1251157"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"P. Kohli, L. Ladicky, and P. Torr,\n                      Robust higher order potentials for enforcing label consistency\n                      , in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'08), 2008.","DOI":"10.1109\/CVPR.2008.4587417"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262177"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/34.895974"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"D. Martin, C. Fowlkes, D. Tal, and J. Malik,\n                      A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics\n                      , in Proceedings of the Eighth International Conference on Computer Vision (ICCV 2001), IEEE Computer Society, Washington, DC, 2001, pp. 416\u2013423.","DOI":"10.1109\/ICCV.2001.937655"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160420503"},{"key":"R27","unstructured":"J. Munkres,\n                      Elements of Algebraic Topology\n                      , Addison\u2013Wesley, Menlo Park, CA, 1984."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"S. Paris and F. Durand,\n                      A topological approach to hierarchical segmentation using mean shift\n                      , in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'07), 2007.","DOI":"10.1109\/CVPR.2007.383228"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1971.10482356"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"B. Russell, A. Efros, J. Sivic, W. Freeman, and A. Zisserman,\n                      Using multiple segmentations to discover objects and their extent in image collections\n                      , in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'06), 2006, pp. 1605\u20131614.","DOI":"10.1109\/CVPR.2006.326"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"R32","unstructured":"B. Silverman,\n                      Density Estimation for Statistics and Data Analysis\n                      , Chapman & Hall\/CRC, London, 1986."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1109\/72.97913"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"A. Vedaldi and S. Soatto,\n                      Quick shift and kernel methods for mode seeking\n                      , in Proceedings of the European Conference on Computer Vision (ECCV), 2008, pp. 705\u2013718.","DOI":"10.1007\/978-3-540-88693-8_52"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"J. Wang, B. Thiesson, Y. Xu, and M. Cohen,\n                      Image and video segmentation by anisotropic kernel mean shift\n                      , in Proceedings of the European Conference on Computer Vision, Lecture Notes in Comput. Sci. 3024, Springer-Verlag, Berlin, 2004, pp. 238\u2013249.","DOI":"10.1007\/978-3-540-24671-8_19"},{"key":"R36","first-page":"604","volume":"2","author":"Wang P.","year":"2007","journal-title":"J. Mach. Learn. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065791000194"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"C. Yang, R. Duraiswami, N. Gumerov, and L. Davis,\n                      Improved fast Gauss transform and efficient kernel density estimation\n                      , in Proceedings of the Ninth IEEE International Conference on Computer Vision, 2003, pp. 664\u2013671.","DOI":"10.1109\/ICCV.2003.1238383"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"L. Yang, P. Meer, and D. Foran,\n                      Multiple class segmentation using a unified framework over mean-shift patches\n                      , in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'07), 2007.","DOI":"10.1109\/CVPR.2007.383229"}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090765158","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:58:12Z","timestamp":1787320692000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090765158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090765158"],"URL":"https:\/\/doi.org\/10.1137\/090765158","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}