A New Divide and Conquer Algorithm for Graph-based Image and Video Segmentation

The concept of the shortest (or minimum) spanning tree (SST)and recursive SST (RSST) of an undirected weighted graph has been successfully applied in image segmentation and edge detection. This paper presents a divide-and-conquer approach for (R)SST based image segmentation in order to overcome the problem of high computational complexity associated with conventional graph algorithms. In the simplest form, the proposed approach, block-based RSST (BRSST), first divides the image into rectangular blocks, finds the (R)SST of each block individually using conventional graph algorithms and, then, merges the (R)SSTs of all image blocks to form an (R)SST of the entire image. Efficient merging algorithms are presented in this paper. We proved a theorem showing that the (R)SST obtained by the merging algorithms is one of the (R)SST that would be found by applying to the entire image the same algorithm used for finding the (R)SST of each image block. Theoretical analysis and experimental results have shown that BRSST has significantly reduced the computational cost. In addition, an incremental BRSST is proposed for video segmentation and results are presented