@article{2007-IUPR-18Dec_1303,
author = {Oliver Wirjadi and Thomas Breuel},
title = {A Branch and Bound Algorithm for Finding the Modes in Kernel Density Estimates},
journal = {Int. J. Computational Intelligence and Applications},
year = {2008},
note = {accepted for publication},
pdf = {2007-IUPR-18Dec_1303.pdf},
__utma = {43439421.2042395030.1195725849.1195725849.1197557618.2},
__utmz = {43439421.1195725849.1.1.utmccn=(direct)|utmcsr=(direct)|utmcmd=(none)},
abstract = {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.},
category = {machine learning;image segmentation}
}