A Branch and Bound Algorithm for Finding the Modes in Kernel Density Estimates

Oliver Wirjadi, Thomas Breuel
International Journal Computational Intelligence and Applications volume 8 number 1, Pages 17-35, World Scientific, 3/2009


Kernel density estimators are established tools in non-parametric statistics. Due to their flexibility and ease of use, these methods are popular in computer vision and pattern recognition for tasks such as object tracking in video or image segmentation. The most frequently used algorithm for finding the modes in such densities (the mean shift) is a gradient ascent rule, which can converge to local optima. We propose a novel, globally optimal branch and bound algorithm for finding the modes in kernel densities. We show in experiments on datasets up to dimension five that the branch and bound method is faster than local optimization and observe linear scaling of our method with sample size. Quantitative experiments on simulated data show that the new method gives statistically significantly more accurate solutions than the mean shift algorithm. The mode localization accuracy is about 5 times more precise than that of the mean shift for all tested parameters. Applications to color image segmentation on an established benchmark test set also show measurably improved results when using global optimization.




@article{ WIRJ2009,
	Title = {A Branch and Bound Algorithm for Finding the Modes in Kernel Density Estimates},
	Author = {Oliver Wirjadi and Thomas Breuel},
	Month = {3},
	Year = {2009},
	Publisher = {World Scientific},
	Publisher = {8},
	Pages = {17-35},
	Journal = {International Journal Computational Intelligence and Applications},
	Number = {1}

Last modified:: 30.08.2016