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 ( sets of pixels). The goal of segmentation is to simpl ...

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 electronic circuitry that executes instructions comprising a computer program. The CPU performs basic arithmetic, logic, controlling, and ...

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 whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lat ...

, 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, east, south, and west, commonly denoted by their initials N, E, S, and W respectively. Relative to north, the directions east, south, and west are a ...

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

undirected In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ...

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. T ...

(MST) is a minimum-weight,

cycle Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in soc ...

-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 ...

. 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 In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small positive integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that possess d ...

. 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 , 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