Assignment No 8
Image Segmentation Using Minimum Spanning Trees
Image segmentation refers to partitioning an image into pairwise disjoint regions. In each region, the pixels are similar to one another. Minimum spanning trees can be used to produce image segmentation.
In this assignment, you deal with images in the human-readable ASCII PPM format. Read an image from a ppm file, and store the image in three two-dimensional arrays of R, G, B components. Prepare an undirected weighted graph G as follows. The vertices of G are the pixels of the image. Two vertices are adjacent if and only if their corresponding pixels (conceived as unit squares) share an edge or a corner. Therefore, each pixel has exactly eight neighbors (except those lying on the image boundary). The weight of an edge (u,v) in G is taken to be the color distance between the pixels corresponding to u and v. If u and v have RGB values (r1,g1,b1) and (r2,g2,b2), then their color distance is defined as |r1 − r2| + |g1 − g2| + |b1 − b2|. Similar pixels therefore have small distances.
After the graph is prepared, a minimum spanning tree T of G is computed by Prim's algorithm. Suppose that we want to break the image into s segments. The s − 1 costliest edges in T are identified and deleted from T. We get a forest with s connected components, each standing for a region in the segmented image.
Run multiple BFS/DFS traversals on this forest to identify the s components. For each component, use a single color, and store the segmented image in the ppm format.
Sample Output
The following segmentation is produced with s = 16.
Input image Segmented image 
gzipped ppm file gzipped ppm file