Image segmentation using minimum spanning trees

Abstract

A new image segmentation algorithm using minimum spanning trees is proposed in this thesis. In the algorithm, each pixel of an input image is considered as a node of an undirected connected weighted graph. The graph is formed by connecting four neighboring nodes of each node with each branch weight being the absolute gray value difference between its associated nodes. From the connected graph given above, an unconnected graph is constructed by eliminating those branches of branch weight greater than a given threshold. A minimum spanning forest of the unconnected graph is found. Each tree of the minimum spanning forest corresponds to a segmented region of the input image. It is shown that in the use of the new algorithm, dividing the input image into small subimages, segmenting each image, and combining the results of segmentation produces exactly the same result as the application of the algorithm to the input image. Thus, we can apply the algorithm to very large size images without rapid increase in time and space complexity. Two variations of the algorithm are made, in which regions found by the forest can be merged together depending on their average gray values and optionally their sizes, thus making the algorithm more flexible. Several examples are shown which clearly demonstrate the effectiveness of the algorithms. We can also note from these examples the closeness between the results and human perception. For comparisons, the results obtained by a well-known segmentation technique, split-and-merge are also shown. Finally, in this thesis, an object detection scheme based on region adjacency graph is studied as an application of image segmentation. Several examples are given demonstrating some usefulness of the scheme.