Fast Integral MeanShift: Application to Color Segmentation of Document Images

Global Mean Shift algorithm is an unsupervised clustering technique already applied for color document image segmentation. Nevertheless, its important computational cost limits its application for document images. The complexity of the global approach is explained by the intensive search of colors samples in the Parzen window to compute the vector oriented toward the mean. For making it more flexible, several attempts have tried to decrease the algorithm complexity mainly by adding spatial information or by reducing the number of colors to shift or even by selecting a reduced number of colors to estimate the means of density function. This paper presents a fast optimized Mean Shift with a much reduced computational cost. This algorithm uses both the discretisation of the shift and the integral image which allow the computation of means into the Parzen windows with a reduced and fixed number of operations. With the discretisation of the color space, the fast optimised MeanShift also memorizes all existing paths to avoid shifting again colors along similar path. Despite the square shape of the Parzen windows and the uniform kernel used, the results are very similar to those obtained by the global Mean Shift algorithm. The proposed algorithm is compared to the different existing implementation of similar algorithms found in the literature.