RIS ID
12484
Abstract
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 over-come 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.
Publication Details
This article was originally published as: Li, W, Shi, M & Ogunbonba, P, A New Divide and Conquer Algorithm for Graph-based Image and Video Segmentation, IEEE 2005 7th Workshop on Multimedia Signal Processing, October 2005, 1-4. Copyright IEEE 2005.