Minimum spanning tree-based segmentation
Encyclopedia
Image segmentation introduction
Image segmentationSegmentation (image processing)
In computer vision, segmentation refers to the process of partitioning a digital image into multiple segments . The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze...
strives to partition a digital image into regions of pixels with similar properties, e.g. homogeneity. The higher-level region representation simplifies image analysis tasks such as counting objects or detecting changes, because region attributes (e.g. average intensity or shape) can be compared more readily than raw pixels.
Motivation for graph-based methods
To speed up segmentation of large images, the work could be divided among several CPUs. One means of accomplishing this involves splitting images into tiles that are processed independently. However, regions that straddle a tile border might be split up or lost if the fragments do not meet the segmentation algorithm's minimum size requirements. A trivial workaround involves overlapping tiles, i.e. allowing each processor to consider additional pixels around its tile's border. Unfortunately this increases the computational load, since the processors on both sides of a tile boundary are performing redundant work. Also, only objects smaller than the tile overlap are guaranteed to be preserved, which means that long objects such as rivers in aerial imagery are still likely to be split. In some cases, the independent tiles' results can be fused to approximate the true results.An alternative exists in the form of graph-based segmentation methods. The connectivity information inherent to graphs allows performing independent work on parts of the original image, and reconnecting them to yield an exact result as if processing had occurred globally.
From images to graphs
The possibility of stitching together independent sub-images motivates adding connectivity information to the pixels. This can be viewed as a graph, the nodes of which are pixels, and edges represent connections between pixels. A simple and comparatively space-efficient variant of this is a grid graph, whereby each pixel is connected to its neighbors in the four cardinal directionCardinal direction
The four cardinal directions or cardinal points are the directions of north, east, south, and west, commonly denoted by their initials: N, E, S, W. East and west are at right angles to north and south, with east being in the direction of rotation and west being directly opposite. Intermediate...
s. Since the pixel neighborship relation is symmetric, the resulting graph is undirected and only half its edges (e.g. each pixel's eastern and southern neighbor) need be stored. The final step calls for encoding pixel similarity information in edge weights, so that the original image is no longer needed. In the simplest case, edge weights are computed as the difference of pixel intensities.
Minimum Spanning Tree segmentation algorithms
A Minimum Spanning TreeMinimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
(MST) is a minimum-weight, cycle-free subset of a graph's edges such that all nodes are connected. In 2004, Felzenszwalb introduced a segmentation method based on Kruskal's MST algorithm
Kruskal's algorithm
Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
. Edges are considered in increasing order of weight; their endpoint pixels are merged into a region if this doesn't cause a cycle in the graph, and if the pixels are 'similar' to the existing regions' pixels. Detecting cycles is possible in near-constant time with the aid of a disjoint-set data structure
Disjoint-set data structure
In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:* Find: Determine which set a particular element...
. Pixel similarity is judged by a heuristic, which compares the weight to a per-segment threshold. The algorithm outputs multiple disjunct MSTs, i.e. a forest; each tree corresponds to a segment. The complexity of the algorithm is quasi-linear because sorting edges is possible in linear time via counting sort
Counting sort
In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to...
.
In 2009, Wassenberg et al. developed an algorithm that computes multiple independent Minimum Spanning Forests and then stitches them together. This enables parallel processing without splitting objects on tile borders. Instead of a fixed weight threshold, an initial connected-component labeling is used to estimate a lower bound on the threshold, which can reduce both over- and undersegmentation. Measurements show that the implementation outperforms Felzenszwalb's sequential algorithm by an order of magnitude.