Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2010, Vol. 11 Issue (9): 677-689    DOI: 10.1631/jzus.C0910668
    
Fast and accurate kernel density approximation using a divide-and-conquer approach
Yan-xia Jin*,1, Kai Zhang2, James T. Kwok2, Han-chang Zhou3
1 School of Electronics and Computer Science and Technology, North University of China, Taiyuan 030051, China 2 Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong, China 3 Key Laboratory of Instrumentation Science and Dynamic Measurement, North University of China, Taiyuan 030051, China
Fast and accurate kernel density approximation using a divide-and-conquer approach
Yan-xia Jin*,1, Kai Zhang2, James T. Kwok2, Han-chang Zhou3
1 School of Electronics and Computer Science and Technology, North University of China, Taiyuan 030051, China 2 Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong, China 3 Key Laboratory of Instrumentation Science and Dynamic Measurement, North University of China, Taiyuan 030051, China
 全文: PDF 
摘要： Density-based nonparametric clustering techniques, such as the mean shift algorithm, are well known for their ?exibility 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 ?t to a single, representative density function. The key novelty presented here is the ef?cient 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 ?ltering/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.
关键词： Nonparametric clustering;  Kernel density estimation;  Mean shift;  Image filtering    
Abstract: Density-based nonparametric clustering techniques, such as the mean shift algorithm, are well known for their ?exibility 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 ?t to a single, representative density function. The key novelty presented here is the ef?cient 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 ?ltering/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.
Key words: Nonparametric clustering    Kernel density estimation    Mean shift    Image filtering
收稿日期: 2009-11-03 出版日期: 2010-09-07
CLC:  TP391  
基金资助: Project  (No.  9140C1204060809)  supported  by  the  National  Key Laboratory Foundation of China
通讯作者: Yan-xia JIN     E-mail: jinyanxia_730128@163.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Yan-xia Jin
Kai Zhang
James T. Kwok
Han-chang Zhou

引用本文:

Yan-xia Jin, Kai Zhang, James T. Kwok, Han-chang Zhou. Fast and accurate kernel density approximation using a divide-and-conquer approach. Front. Inform. Technol. Electron. Eng., 2010, 11(9): 677-689.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/jzus.C0910668    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2010/V11/I9/677

[1] Gwang-Min Choe, Tian-jiang Wang, Fang Liu, Chun-Hwa Choe, Hyo-Son So, Chol-Ung Pak. An advanced integrated framework for moving object tracking[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(10): 861-877.