New accelerated graph-based method of image segmentation applying minimum spanning tree

In this paper problem of graph based image segmentation is considered. In particular, attention is paid to minimal spanning tree based algorithm proposed by Felzenszwalb and Huttenlocher (FH). Although the method yields high quality results for various classes of images, its application is limited mainly to off-line processing. Its due to the very long execution time of the FH method, which in the case of high resolution images, requires processing of millions of vertices and edges contained within the resulting graph. Therefore, some improvements to the FH method are proposed in this paper. The modifications aim at the reduction of algorithm execution time and the usage of computer host memory. These goals are achieved both by reducing the size of input image graph and by applying the methods of GPU parallel computing at initial stages of the algorithm. As the reduction of graph size is obtained by processing meta-pixels representing homogenous regions, the new method is most suitable for the segmentation of images including rare, structurally complex objects distributed over nonuniform background. Results obtained by the introduced approach are compared with the results of the original FH method and other popular graph-based approaches to image segmentation. The comparison includes both the accuracy of image segmentation and the execution time. Analysis of the results clearly shows, that the proposed approach in many cases can significantly accelerate segmentation process without a noticeable loss of image segmentation quality.