Full Text:   <1306>

CLC number: TP391

On-line Access: 2010-09-07

Received: 2009-11-03

Revision Accepted: 2010-04-06

Crosschecked: 2010-08-02

Cited: 1

Clicked: 3380

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2010 Vol.11 No.9 P.677-689


Fast and accurate kernel density approximation using a divide-and-conquer approach

Author(s):  Yan-xia Jin, Kai Zhang, James T. Kwok, Han-chang Zhou

Affiliation(s):  School of Electronics and Computer Science and Technology, North University of China, Taiyuan 030051, China, Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong, China, Key Laboratory of Instrumentation Science and Dynamic Measurement, North University of China, Taiyuan 030051, China

Corresponding email(s):   jinyanxia_730128@163.com

Key Words:  Nonparametric clustering, Kernel density estimation, Mean shift, Image filtering

Yan-xia Jin, Kai Zhang, James T. Kwok, Han-chang Zhou. Fast and accurate kernel density approximation using a divide-and-conquer approach[J]. Journal of Zhejiang University Science C, 2010, 11(9): 677-689.

@article{title="Fast and accurate kernel density approximation using a divide-and-conquer approach",
author="Yan-xia Jin, Kai Zhang, James T. Kwok, Han-chang Zhou",
journal="Journal of Zhejiang University Science C",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Fast and accurate kernel density approximation using a divide-and-conquer approach
%A Yan-xia Jin
%A Kai Zhang
%A James T. Kwok
%A Han-chang Zhou
%J Journal of Zhejiang University SCIENCE C
%V 11
%N 9
%P 677-689
%@ 1869-1951
%D 2010
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C0910668

T1 - Fast and accurate kernel density approximation using a divide-and-conquer approach
A1 - Yan-xia Jin
A1 - Kai Zhang
A1 - James T. Kwok
A1 - Han-chang Zhou
J0 - Journal of Zhejiang University Science C
VL - 11
IS - 9
SP - 677
EP - 689
%@ 1869-1951
Y1 - 2010
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C0910668

Density-based nonparametric clustering techniques, such as the mean shift algorithm, are well known for their flexibility and effectiveness in real-world vision-based problems. The underlying kernel density estimation process can be very expensive on large datasets. In this paper, the divide-and-conquer method is proposed to reduce these computational requirements. The dataset is first partitioned into a number of small, compact clusters. Components of the kernel estimator in each local cluster are then fit to a single, representative density function. The key novelty presented here is the efficient derivation of the representative density function using concepts from function approximation, such that the expensive kernel density estimator can be easily summarized by a highly compact model with very few basis functions. The proposed method has a time complexity that is only linear in the sample size and data dimensionality. Moreover, the bandwidth of the resultant density model is adaptive to local data distribution. Experiments on color image filtering/segmentation show that, the proposed method is dramatically faster than both the standard mean shift and fast mean shift implementations based on kd-trees while producing competitive image segmentation results.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Barbay, J., Golynski, A., Munro, J.I., Rao, S.S., 2007. Adaptive searching in succinctly encoded binary relations and tree-structured documents. Theor. Comput. Sci., 387(3):284-297.

[2]Bouezmarni, T., Rombouts, J.V.K., 2010. Nonparametric density estimation for multivariate bounded data. J. Statist. Plan. Infer., 140(1):139-152.

[3]Chang, D.X., Zhang, X.D., Zheng, C.W., 2009. A genetic algorithm with gene rearrangement for k-means clustering. Pattern Recogn., 42(7):1210-1222.

[4]Chang, H., Yeung, D.Y., 2008. Robust path-based spectral clustering. Pattern Recogn., 41(1):191-203.

[5]Comaniciu, D., Meer, P., 2002. Mean shift: a robust approach toward feature space analysis. IEEE Trans. Pattern Anal. Mach. Intell., 24(5):603-619.

[6]de Berg, M., van Kreveld, M., Overmars, M., Cheong, O., 2008. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, p.105-120.

[7]Fashing, M., Tomasi, C., 2005. Mean shift is a bound optimization. IEEE Trans. Pattern Anal. Mach. Intell., 27(3):471-474.

[8]Georgescu, B., Shimshoni, I., Meer, P., 2003. Mean Shift Based Clustering in High Dimensions: a Texture Classification Example. Proc. 9th IEEE Int. Conf. on Computer Vision, p.456-463.

[9]Han, B., Comaniciu, D., Zhu, Y., Davis, L., 2004. Incremental Density Approximation and Kernel-Based Bayesian Filtering for Object Tracking. Proc. IEEE Computer Society Conf. on Computer Version and Pattern Recognition, p.638-644.

[10]Mokkadem, A., Pelletier, M., Slaoui, Y., 2009. The stochastic approximation method for the estimation of a multivariate probability density. J. Statist. Plan. Infer., 139(7):2459-2478.

[11]Ozertem, U., Erdogmus, D., Jenssen, R., 2008. Mean shift spectral clustering. Pattern Recogn., 41(6):1924-1938.

[12]Parzen, E., 1962. On estimation of a probability density function and mode. Ann. Math. Statist., 33(3):1065-1076.

[13]Rao, S., de Martins Martins, A., Principe, J.C., 2009. Mean shift: an information theoretic perspective. Pattern Recogn. Lett., 30(3):222-230.

[14]Ren, W., Singh, S., Singh, M., Zhu, Y.S., 2009. State of the art on spatio-temporal information based video retrieval. Pattern Recogn., 42(2):267-282.

[15]Ruslan, S., Sam, R., 2003. Adaptive Overrelaxed Bound Optimization Methods. Proc. 20th Int. Conf. on Machine Learning, p.664-671.

[16]Shen, C., Brooks, M., 2005. Adaptive Over-Relaxed Mean Shift. Proc. 8th Int. Symp. on Signal Processing and Its Applications, p.575-578.

[17]Shen, C., Brooks, M., van den Hengel, A., 2007. Fast global kernel density mode seeking: application to localisation and tracking. IEEE Trans. Image Process., 16(5):1457-1469.

[18]Wang, X.H., Liu, J.L., 2009. Tracking multiple people under occlusion and across cameras using probabilistic models. J. Zhejing Univ.-Sci. A, 10(7):985-996.

[19]Xu, G., Xu, J.H., 2010. Efficient approximation algorithms for clustering point-sets. Comput. Geom., 43(1):59-66.

[20]Yu, S.Y., Wang, F.L., Xue, Y.F., Yang, J., 2009. Bayesian moving object detection in dynamic scenes using an adaptive foreground model. J. Zhejing Univ.-Sci. A, 10(12):1750-1758.

[21]Zhang, J., Zhang, K., Xu, X., Tse, C.K., Small, M., 2009. Seeding the kernels in graphs: towards multi-resolution community analysis. New J. Phys., 11(11):113003.

[22]Zhang, K., Kwok, J.T., 2007. Simplifying Mixture Models Through Function Approximation. Advances in Neural Information Processing Systems 19. MIT Press, Cambridge, MA, p.1577-1584.

[23]Zhang, K., Tang, M., Kwok, J.T., 2005. Applying Neighborhood Consistency for Fast Clustering and Kernel Density Estimation. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, 2:1001-1007.

[24]Zivkovic, Z., Cemgil, A.T., Krose, B., 2009. Approximate Bayesian methods for kernel-based object tracking. Comput. Vis. Image Understand., 113(6):743-749.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE