A unified method for segmentation and edge detection using graph theory

Methods of image segmentation and edge detection based on graph theoretic representations of images are described. The image is mapped onto a weighted graph and, from this graph, spanning trees are used to describe regions and edges in the image. Edge detection is shown to be a dual problem to segmentation. Two methods are developed for both segmentation and edge detection, providing four related techniques. The simpler method uses the Shortest Spanning Tree (SST) to partition the graph and to form a segmentation or edge detection. The second method applies the first method recursively to incorporate global pictorial information into the graph, removing many problems of the simpler method and of other pixel-linking algorithms. An important property of the segmentation and edge detection methods is that image features may be described in a hierarchical way.