2D IMAGE SEGMENTATION USING MINIMUM SPANNING-TREES

This paper presents a new algorithm for partitioning a gray-level imag e into connected homogeneous regions. The novelty of this algorithm li es in the fact that, by constructing a minimum spanning tree represent ation of a gray-level image, it reduces a region partitioning problem to a minimum spanning tree partitioning problem, and hence reduces the computational complexity of the region partitioning problem. The tree -partitioning algorithm, in essence, partitions a minimum spanning tre e into subtrees, representing different homogeneous regions, by minimi zing the sum of variations of gray levels over all subtrees under the constraints that each subtree should have at least a specified number of nodes, and two adjacent subtrees should have significantly differen t average gray-levels. Two (faster) heuristic implementations are also given for large-scale region partitioning problems. Test results have shown that the segmentation results are satisfactory and insensitive to noise.