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.