Theoretical Concepts and Technical Aspects on Image Segmentation

Background

Graph-based image segmentation techniques generally represent the problem in terms of a graph, G =(V,E) where each node v_i Ɛ V corresponds to a pixel inthe image, and the edges in E connect certain pairs of neighboring pixels. A weight is associated with each edge based on some property of the pixels that it connects, such as their image intensities. Depending on the method, there may or may not be an edge connecting each pair of vertices. The earliest graph based methods use fixed thresholds and local measures in computing segmentation.

Different cluster-structures can be detected using algorithms on minimum spanning tree. The dataset used by Zahn include Fisher Iris data in four dimensional space. The work of Zahn (1971) presents a segmentation method based on the minimum spanning tree (MST) of the graph. This method has been applied both to point clustering and to image segmentation. For image segmentation the edge weights in the graph are based on the differences between pixel intensities, whereas for point clustering the weights are based on distances between points. The segmentation criterion in Zahn’s method is to break MST edges with large weights, which is inadequate. Differences between pixels within the high variability region can be larger than those between the ramp and the constant region. Thus, depending on the threshold, simply breaking large weight edges would either result in the high variability region being split into multiple regions, or would merge the ramp and the constant region together.