Image segmentation In digital image processing and computer vision, image segmentation is the process of partitioning a digital image into multiple image segments, also known as image regions or image objects (Set (mathematics), sets of pixels). The goal of segmen ...

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

CPU A central processing unit (CPU), also called a central processor, main processor, or just processor, is the primary processor in a given computer. Its electronic circuitry executes instructions of a computer program, such as arithmetic, log ...

s. 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 In graph theory, a lattice graph, mesh graph, or grid graph is a Graph (discrete mathematics), graph whose graph drawing, drawing, Embedding, embedded in some Euclidean space , forms a regular tiling. This implies that the group (mathematics), g ...

, whereby each pixel is connected to its neighbors in the four

cardinal direction The four cardinal directions or cardinal points are the four main compass directions: north (N), south (S), east (E), and west (W). The corresponding azimuths ( clockwise horizontal angle from north) are 0°, 90°, 180°, and 270°. The ...

s. Since the pixel neighborship relation is symmetric, the resulting graph is

undirected In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

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

minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. ...

(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. 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 In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of Disjoint sets, disjoint (non-overlapping) Set (mathematics), sets. Equivalently, it ...

. 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 is the process of determining the number of elements of a finite set of objects; that is, determining the size of a set. The traditional way of counting consists of continually increasing a (mental or spoken) counter by a unit for ever ...

. 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. In 2017, Saglam and Baykan used Prim's sequential representation of minimum spanning tree and proposed a new cutting criterion for image segmentation. They construct the MST with Prim's MST algorithm using the Fibonacci Heap data structure. The method achieves an important success on the test images in fast execution time.

References

{{Reflist, refs= {{citation , last1 = Chen , first1 = Minghua , last2 = Pavlidis , first2 = Theodosios , author2-link = Theodosios Pavlidis , doi = 10.1109/34.56195 , issue = 6 , journal =

IEEE Transactions on Pattern Analysis and Machine Intelligence ''IEEE Transactions on Pattern Analysis and Machine Intelligence'' (sometimes abbreviated as ''IEEE PAMI'' or simply ''PAMI'') is a monthly peer-reviewed scientific journal published by the IEEE Computer Society. Background The journal covers r ...

, pages = 588–594 , title = Image seaming for segmentation on parallel architecture , volume = 12 , year = 1990 {{citation , last1 = Felzenszwalb , first1 = Pedro F. , author1-link = Pedro Felipe Felzenszwalb , last2 = Huttenlocher , first2 = Daniel P. , author2-link = Daniel P. Huttenlocher , doi = 10.1023/B:VISI.0000022288.19776.77 , issue = 2 , journal = International Journal of Computer Vision , pages = 167–181 , title = Efficient graph-based image segmentation , volume = 59 , year = 2004, s2cid = 207663697 {{citation , last1 = Harfst , first1 = Gregory C. , last2 = Reingold , first2 = Edward M. , author2-link = Edward Reingold , doi = 10.1145/356458.356463 , issue = 3 , journal =

SIGACT News ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer. Publi ...

, pages = 86–95 , title = A potential-based amortized analysis of the union-find data structure , volume = 31 , year = 2000, s2cid = 14779624 {{citation , last1 = Haralick , first1 = Robert M. , author1-link = Robert Haralick , last2 = Shapiro , first2 = Linda G. , author2-link = Linda Shapiro , date = January 1985 , doi = 10.1016/s0734-189x(85)90153-7 , issue = 1 , journal = Computer Vision, Graphics, and Image Processing , pages = 100–132 , title = Image segmentation techniques , volume = 29 {{citation , last1 = Iivarinen , first1 = Jukka , last2 = Peura , first2 = Markus , last3 = Särelä , first3 = Jaakko , last4 = Visa , first4 = Ari , editor-last = Clark , editor-first = Adrian F. , contribution = Comparison of combined shape descriptors for irregular objects , contribution-url = https://www.bmva.org/bmvc/1997/papers/062/bmvc97.htm , publisher = British Machine Vision Association , title = Proceedings of the British Machine Vision Conference 1997, BMVC 1997, University of Essex, UK, 1997 , year = 1997 {{citation , last1 = Sağlam , first1 = Ali , last2 = Baykan , first2 = Nurdan Akhan , doi = 10.1016/j.patrec.2016.06.001 , journal = Pattern Recognition Letters , pages = 155–162 , title = Sequential image segmentation based on minimum spanning tree representation , volume = 87 , year = 2017, bibcode = 2017PaReL..87..155S {{citation , last1 = Wassenberg , first1 = Jan , last2 = Middelmann , first2 = Wolfgang , last3 = Sanders , first3 = Peter , author3-link = Peter Sanders (computer scientist) , editor1-last = Jiang , editor1-first = Xiaoyi , editor2-last = Petkov , editor2-first = Nicolai , editor2-link = Nicolai Petkov , contribution = An efficient parallel algorithm for graph-based image segmentation , doi = 10.1007/978-3-642-03767-2_122 , pages = 1003–1010 , publisher = Springer , series = Lecture Notes in Computer Science , title = Computer Analysis of Images and Patterns, 13th International Conference, CAIP 2009, Münster, Germany, September 2-4, 2009, Proceedings , volume = 5702 , isbn = 978-3-642-03766-5 , year = 2009

External links

Information on the PHMSF algorithm (Parallel Heuristic for Minimum Spanning Forests)
Spanning tree Image segmentation