Image segmentation

Volume segmentation of a 3D-rendered CT scan of the thorax: The anterior thoracic wall, the airways and the pulmonary vessels anterior to the root of the lung have been digitally removed in order to visualize thoracic contents:
– blue: pulmonary arteries
– red: pulmonary veins (and also the abdominal wall)
– yellow: the mediastinum
– violet: the diaphragm

Some of the practical applications of image segmentation are:

• Content-based image retrieval[4]
• Machine vision
• Medical imaging,[5][6] including volume rendered images from computed tomography and magnetic resonance imaging.
  • Locate tumors and other pathologies[7][8]
  • Measure tissue volumes
  • Diagnosis, study of anatomical structure[9]
  • Surgery planning
  • Virtual surgery simulation
  • Intra-surgery navigation
• Object detection[10]
  • Pedestrian detection
  • Face detection
  • Brake light detection
  • Locate objects in satellite images (roads, forests, crops, etc.)
• Recognition Tasks
  • Face recognition
  • Fingerprint recognition
  • Iris recognition
• Traffic control systems
• Video surveillance
• Video object co-segmentation and action localization[11][12]

Several general-purpose algorithms and techniques have been developed for image segmentation. To be useful, these techniques must typically be combined with a domain's specific knowledge in order to effectively solve the domain's segmentation problems.

There are three classes of segmentation techniques.

• Classical approaches
• AI based techniques
• Techniques not falling into the above two categories.[13]

• Semantic segmentation is an approach detecting, for every pixel, belonging class of the object.[14] For example, when all people in a figure are segmented as one object and background as one object.
• Instance segmentation is an approach that identifies, for every pixel, a belonging instance of the object. It detects each distinct object of interest in the image.[15] For example, when each person in a figure is segmented as an individual object.

The simplest method of image segmentation is called the thresholding method. This method is based on a clip-level (or a threshold value) to turn a gray-scale image into a binary image.

The key of this method is to select the threshold value (or values when multiple-levels are selected). Several popular methods are used in industry including the maximum entropy method, balanced histogram thresholding, Otsu's method (maximum variance), and k-means clustering.

Recently, methods have been developed for thresholding computed tomography (CT) images. The key idea is that, unlike Otsu's method, the thresholds are derived from the radiographs instead of the (reconstructed) image.[16][17]

New methods suggested the usage of multi-dimensional fuzzy rule-based non-linear thresholds. In these works decision over each pixel's membership to a segment is based on multi-dimensional rules derived from fuzzy logic and evolutionary algorithms based on image lighting environment and application.[18]

Source image.

Image after running k-means with k = 16. Note that a common technique to improve performance for large images is to downsample the image, compute the clusters, and then reassign the values to the larger image if necessary.

The K-means algorithm is an iterative technique that is used to partition an image into K clusters.[19] The basic algorithm is

1. Pick K cluster centers, either randomly or based on some heuristic method, for example K-means++
2. Assign each pixel in the image to the cluster that minimizes the distance between the pixel and the cluster center
3. Re-compute the cluster centers by averaging all of the pixels in the cluster
4. Repeat steps 2 and 3 until convergence is attained (i.e. no pixels change clusters)

In this case, distance is the squared or absolute difference between a pixel and a cluster center. The difference is typically based on pixel color, intensity, texture, and location, or a weighted combination of these factors. K can be selected manually, randomly, or by a heuristic. This algorithm is guaranteed to converge, but it may not return the optimal solution. The quality of the solution depends on the initial set of clusters and the value of K.

Motion based segmentation is a technique that relies on motion in the image to perform segmentation.

The idea is simple: look at the differences between a pair of images. Assuming the object of interest is moving, the difference will be exactly that object.

Improving on this idea, Kenney et al. proposed interactive segmentation . They use a robot to poke objects in order to generate the motion signal necessary for motion-based segmentation.

Interactive segmentation follows the interactive perception framework proposed by Dov Katz and Oliver Brock .

Compression based methods postulate that the optimal segmentation is the one that minimizes, over all possible segmentations, the coding length of the data.[20][21] The connection between these two concepts is that segmentation tries to find patterns in an image and any regularity in the image can be used to compress it. The method describes each segment by its texture and boundary shape. Each of these components is modeled by a probability distribution function and its coding length is computed as follows:

1. The boundary encoding leverages the fact that regions in natural images tend to have a smooth contour. This prior is used by Huffman coding to encode the difference chain code of the contours in an image. Thus, the smoother a boundary is, the shorter coding length it attains.
2. Texture is encoded by lossy compression in a way similar to minimum description length (MDL) principle, but here the length of the data given the model is approximated by the number of samples times the entropy of the model. The texture in each region is modeled by a multivariate normal distribution whose entropy has a closed form expression. An interesting property of this model is that the estimated entropy bounds the true entropy of the data from above. This is because among all distributions with a given mean and covariance, normal distribution has the largest entropy. Thus, the true coding length cannot be more than what the algorithm tries to minimize.

For any given segmentation of an image, this scheme yields the number of bits required to encode that image based on the given segmentation. Thus, among all possible segmentations of an image, the goal is to find the segmentation which produces the shortest coding length. This can be achieved by a simple agglomerative clustering method. The distortion in the lossy compression determines the coarseness of the segmentation and its optimal value may differ for each image. This parameter can be estimated heuristically from the contrast of textures in an image. For example, when the textures in an image are similar, such as in camouflage images, stronger sensitivity and thus lower quantization is required.

Histogram-based methods are very efficient compared to other image segmentation methods because they typically require only one pass through the pixels. In this technique, a histogram is computed from all of the pixels in the image, and the peaks and valleys in the histogram are used to locate the clusters in the image.[1] Color or intensity can be used as the measure.

A refinement of this technique is to recursively apply the histogram-seeking method to clusters in the image in order to divide them into smaller clusters. This operation is repeated with smaller and smaller clusters until no more clusters are formed.[1][22]

One disadvantage of the histogram-seeking method is that it may be difficult to identify significant peaks and valleys in the image.

Histogram-based approaches can also be quickly adapted to apply to multiple frames, while maintaining their single pass efficiency. The histogram can be done in multiple fashions when multiple frames are considered. The same approach that is taken with one frame can be applied to multiple, and after the results are merged, peaks and valleys that were previously difficult to identify are more likely to be distinguishable. The histogram can also be applied on a per-pixel basis where the resulting information is used to determine the most frequent color for the pixel location. This approach segments based on active objects and a static environment, resulting in a different type of segmentation useful in video tracking.

Edge detection is a well-developed field on its own within image processing. Region boundaries and edges are closely related, since there is often a sharp adjustment in intensity at the region boundaries. Edge detection techniques have therefore been used as the base of another segmentation technique.

The edges identified by edge detection are often disconnected. To segment an object from an image however, one needs closed region boundaries. The desired edges are the boundaries between such objects or spatial-taxons.[23][24]

Spatial-taxons[25] are information granules,[26] consisting of a crisp pixel region, stationed at abstraction levels within a hierarchical nested scene architecture. They are similar to the Gestalt psychological designation of figure-ground, but are extended to include foreground, object groups, objects and salient object parts. Edge detection methods can be applied to the spatial-taxon region, in the same manner they would be applied to a silhouette. This method is particularly useful when the disconnected edge is part of an illusory contour[27][28]

Segmentation methods can also be applied to edges obtained from edge detectors. Lindeberg and Li[29] developed an integrated method that segments edges into straight and curved edge segments for parts-based object recognition, based on a minimum description length (M_DL) criterion that was optimized by a split-and-merge-like method with candidate breakpoints obtained from complementary junction cues to obtain more likely points at which to consider partitions into different segments.

This method is a combination of three characteristics of the image: partition of the image based on histogram analysis is checked by high compactness of the clusters (objects), and high gradients of their borders. For that purpose two spaces have to be introduced: one space is the one-dimensional histogram of brightness H = H(B); the second space is the dual 3-dimensional space of the original image itself B = B(x, y). The first space allows to measure how compactly the brightness of the image is distributed by calculating a minimal clustering kmin. Threshold brightness T corresponding to kmin defines the binary (black-and-white) image – bitmap b = φ(x, y), where φ(x, y) = 0, if B(x, y) < T, and φ(x, y) = 1, if B(x, y) ≥ T. The bitmap b is an object in dual space. On that bitmap a measure has to be defined reflecting how compact distributed black (or white) pixels are. So, the goal is to find objects with good borders. For all T the measure M_DC = G/(k × L) has to be calculated (where k is difference in brightness between the object and the background, L is length of all borders, and G is mean gradient on the borders). Maximum of MDC defines the segmentation.[30]

Region-growing methods rely mainly on the assumption that the neighboring pixels within one region have similar values. The common procedure is to compare one pixel with its neighbors. If a similarity criterion is satisfied, the pixel can be set to belong to the same cluster as one or more of its neighbors. The selection of the similarity criterion is significant and the results are influenced by noise in all instances.

The method of Statistical Region Merging[31] (SRM) starts by building the graph of pixels using 4-connectedness with edges weighted by the absolute value of the intensity difference. Initially each pixel forms a single pixel region. SRM then sorts those edges in a priority queue and decides whether or not to merge the current regions belonging to the edge pixels using a statistical predicate.

One region-growing method is the seeded region growing method. This method takes a set of seeds as input along with the image. The seeds mark each of the objects to be segmented. The regions are iteratively grown by comparison of all unallocated neighboring pixels to the regions. The difference between a pixel's intensity value and the region's mean, ${\displaystyle \delta }$, is used as a measure of similarity. The pixel with the smallest difference measured in this way is assigned to the respective region. This process continues until all pixels are assigned to a region. Because seeded region growing requires seeds as additional input, the segmentation results are dependent on the choice of seeds, and noise in the image can cause the seeds to be poorly placed.

Another region-growing method is the unseeded region growing method. It is a modified algorithm that does not require explicit seeds. It starts with a single region ${\displaystyle A_{1}}$—the pixel chosen here does not markedly influence the final segmentation. At each iteration it considers the neighboring pixels in the same way as seeded region growing. It differs from seeded region growing in that if the minimum ${\displaystyle \delta }$ is less than a predefined threshold ${\displaystyle T}$ then it is added to the respective region ${\displaystyle A_{j}}$. If not, then the pixel is considered different from all current regions ${\displaystyle A_{i}}$ and a new region ${\displaystyle A_{n+1}}$ is created with this pixel.

One variant of this technique, proposed by Haralick and Shapiro (1985),[1] is based on pixel intensities. The mean and scatter of the region and the intensity of the candidate pixel are used to compute a test statistic. If the test statistic is sufficiently small, the pixel is added to the region, and the region’s mean and scatter are recomputed. Otherwise, the pixel is rejected, and is used to form a new region.

A special region-growing method is called ${\displaystyle \lambda }$-connected segmentation (see also lambda-connectedness). It is based on pixel intensities and neighborhood-linking paths. A degree of connectivity (connectedness) is calculated based on a path that is formed by pixels. For a certain value of ${\displaystyle \lambda }$, two pixels are called ${\displaystyle \lambda }$-connected if there is a path linking those two pixels and the connectedness of this path is at least ${\displaystyle \lambda }$. ${\displaystyle \lambda }$-connectedness is an equivalence relation.[32]

Split-and-merge segmentation is based on a quadtree partition of an image. It is sometimes called quadtree segmentation.

This method starts at the root of the tree that represents the whole image. If it is found non-uniform (not homogeneous), then it is split into four child squares (the splitting process), and so on. If, in contrast, four child squares are homogeneous, they are merged as several connected components (the merging process). The node in the tree is a segmented node. This process continues recursively until no further splits or merges are possible.[33][34] When a special data structure is involved in the implementation of the algorithm of the method, its time complexity can reach ${\displaystyle O(n\log n)}$, an optimal algorithm of the method.[35]

Using a partial differential equation (PDE)-based method and solving the PDE equation by a numerical scheme, one can segment the image.[36] Curve propagation is a popular technique in this category, with numerous applications to object extraction, object tracking, stereo reconstruction, etc. The central idea is to evolve an initial curve towards the lowest potential of a cost function, where its definition reflects the task to be addressed. As for most inverse problems, the minimization of the cost functional is non-trivial and imposes certain smoothness constraints on the solution, which in the present case can be expressed as geometrical constraints on the evolving curve.

The goal of variational methods is to find a segmentation which is optimal with respect to a specific energy functional. The functionals consist of a data fitting term and a regularizing terms. A classical representative is the Potts model defined for an image ${\displaystyle f}$ by

${\displaystyle \operatorname {argmin} _{u}\gamma \|\nabla u\|_{0}+\int (u-f)^{2}\,dx.}$

A minimizer ${\displaystyle u^{*}}$ is a piecewise constant image which has an optimal tradeoff between the squared L2 distance to the given image ${\displaystyle f}$ and the total length of its jump set. The jump set of ${\displaystyle u^{*}}$ defines a segmentation. The relative weight of the energies is tuned by the parameter ${\displaystyle \gamma >0}$. The binary variant of the Potts model, i.e., if the range of ${\displaystyle u}$ is restricted to two values, is often called Chan-Vese model.[43] An important generalization is the Mumford-Shah model[44] given by

${\displaystyle \operatorname {argmin} _{u,K}\gamma |K|+\mu \int _{K^{C}}|\nabla u|^{2}\,dx+\int (u-f)^{2}\,dx.}$

The functional value is the sum of the total length of the segmentation curve ${\displaystyle K}$, the smoothness of the approximation ${\displaystyle u}$, and its distance to the original image ${\displaystyle f}$. The weight of the smoothness penalty is adjusted by ${\displaystyle \mu >0}$. The Potts model is often called piecewise constant Mumford-Shah model as it can be seen as the degenerate case ${\displaystyle \mu \to \infty }$. The optimization problems are known to be NP-hard in general but near-minimizing strategies work well in practice. Classical algorithms are graduated non-convexity and Ambrosio-Tortorelli approximation.

Graph partitioning methods are an effective tools for image segmentation since they model the impact of pixel neighborhoods on a given cluster of pixels or pixel, under the assumption of homogeneity in images. In these methods, the image is modeled as a weighted, undirected graph. Usually a pixel or a group of pixels are associated with nodes and edge weights define the (dis)similarity between the neighborhood pixels. The graph (image) is then partitioned according to a criterion designed to model "good" clusters. Each partition of the nodes (pixels) output from these algorithms are considered an object segment in the image. Some popular algorithms of this category are normalized cuts,[45] random walker,[46] minimum cut,[47] isoperimetric partitioning,[48] minimum spanning tree-based segmentation,[49] and segmentation-based object categorization.

Supervised image segmentation using MRF and MAP

In terms of image segmentation, the function that MRFs seek to maximize is the probability of identifying a labelling scheme given a particular set of features are detected in the image. This is a restatement of the maximum a posteriori estimation method.

MRF neighborhood for a chosen pixel

The generic algorithm for image segmentation using MAP is given below:

1. Define the neighborhood of each feature (random variable in MRF terms).
   Generally this includes 1st-order or 2nd-order neighbors.
2. Set initial probabilities P(f_i)> for each feature as 0 or
3. where f_i ∈ Σ is the set containing features extracted
   for pixel i and define an initial set of clusters.
4. Using the training data compute the mean (μ_ℓi) and variance (σ_ℓi) for each label. This is termed as class statistics.
5. Compute the marginal distribution for the given labeling scheme P(f_i | ℓ_i) using Bayes' theorem and the class statistics calculated earlier. A Gaussian model is used for the marginal distribution.

   ${\displaystyle {\frac {1}{\sigma (\ell _{i}){\sqrt {2\pi }}}}e^{-(f_{i}-\mu (\ell _{i}))^{2}/(2\sigma (\ell _{i})^{2})}\,d\ell _{i}}$

6. Calculate the probability of each class label given the neighborhood defined previously.
   Clique potentials are used to model the social impact in labeling.
7. Iterate over new prior probabilities and redefine clusters such that these probabilities are maximized.
   This is done using a variety of optimization algorithms described below.
8. Stop when probability is maximized and labeling scheme does not change.
   The calculations can be implemented in log likelihood terms as well.

Image segmentation using MRF and expectation–maximization

The expectation–maximization algorithm is utilized to iteratively estimate the a posterior probabilities and distributions of labeling when no training data is available and no estimate of segmentation model can be formed. A general approach is to use histograms to represent the features of an image and proceed as outlined briefly in this three-step algorithm:

1. A random estimate of the model parameters is utilized.

2. E step: Estimate class statistics based on the random segmentation model defined. Using these, compute the conditional probability of belonging to a label given the feature set is calculated using naive Bayes' theorem.

${\displaystyle P(\lambda \mid f_{i})={\frac {P(f_{i}\mid \lambda )P(\lambda )}{\Sigma _{\lambda \in \Lambda }P(f_{i}\mid \lambda )P(\lambda )}}}$

Here ${\displaystyle \lambda \in \Lambda }$, the set of all possible labels.

3. M step: The established relevance of a given feature set to a labeling scheme is now used to compute the a priori estimate of a given label in the second part of the algorithm. Since the actual number of total labels is unknown (from a training data set), a hidden estimate of the number of labels given by the user is utilized in computations.

${\displaystyle P(\lambda )={\frac {\Sigma _{\lambda \in \Lambda }P(\lambda \mid f_{i})}{|\Omega |}}}$

where ${\displaystyle \Omega }$ is the set of all possible features.

Segmentation of color image using HMRF-EM model

The watershed transformation considers the gradient magnitude of an image as a topographic surface. Pixels having the highest gradient magnitude intensities (GMIs) correspond to watershed lines, which represent the region boundaries. Water placed on any pixel enclosed by a common watershed line flows downhill to a common local intensity minimum (LIM). Pixels draining to a common minimum form a catch basin, which represents a segment. .

The central assumption of model-based approaches is that the structures of interest have a tendency towards a particular shape. Therefore, one can seek a probabilistic model that characterizes the shape and its variation. When segmenting an image, constraints can be imposed using this model as a prior.[56] Such a task may involve (i) registration of the training examples to a common pose, (ii) probabilistic representation of the variation of the registered samples, and (iii) statistical inference between the model and the image. Other important methods in the literature for model-based segmentation include active shape models and active appearance models.

Image segmentations are computed at multiple scales in scale space and sometimes propagated from coarse to fine scales; see scale-space segmentation.

Segmentation criteria can be arbitrarily complex and may take into account global as well as local criteria. A common requirement is that each region must be connected in some sense.

In one kind of segmentation, the user outlines the region of interest with the mouse clicks and algorithms are applied so that the path that best fits the edge of the image is shown.

Techniques like SIOX, Livewire, Intelligent Scissors or IT-SNAPS are used in this kind of segmentation. In an alternative kind of semi-automatic segmentation, the algorithms return a spatial-taxon (i.e. foreground, object-group, object or object-part) selected by the user or designated via prior probabilities.[72][73]

Most of the aforementioned segmentation methods are based only on color information of pixels in the image. Humans use much more knowledge when performing image segmentation, but implementing this knowledge would cost considerable human engineering and computational time, and would require a huge domain knowledge database which does not currently exist. Trainable segmentation methods, such as neural network segmentation, overcome these issues by modeling the domain knowledge from a dataset of labeled pixels.

An image segmentation neural network can process small areas of an image to extract simple features such as edges.[74] Another neural network, or any decision-making mechanism, can then combine these features to label the areas of an image accordingly. A type of network designed this way is the Kohonen map.

Pulse-coupled neural networks (PCNNs) are neural models proposed by modeling a cat’s visual cortex and developed for high-performance biomimetic image processing. In 1989, Reinhard Eckhorn introduced a neural model to emulate the mechanism of a cat’s visual cortex. The Eckhorn model provided a simple and effective tool for studying the visual cortex of small mammals, and was soon recognized as having significant application potential in image processing. In 1994, the Eckhorn model was adapted to be an image processing algorithm by John L. Johnson, who termed this algorithm Pulse-Coupled Neural Network.[75] Over the past decade, PCNNs have been utilized for a variety of image processing applications, including: image segmentation, feature generation, face extraction, motion detection, region growing, noise reduction, and so on. A PCNN is a two-dimensional neural network. Each neuron in the network corresponds to one pixel in an input image, receiving its corresponding pixel’s color information (e.g. intensity) as an external stimulus. Each neuron also connects with its neighboring neurons, receiving local stimuli from them. The external and local stimuli are combined in an internal activation system, which accumulates the stimuli until it exceeds a dynamic threshold, resulting in a pulse output. Through iterative computation, PCNN neurons produce temporal series of pulse outputs. The temporal series of pulse outputs contain information of input images and can be utilized for various image processing applications, such as image segmentation and feature generation. Compared with conventional image processing means, PCNNs have several significant merits, including robustness against noise, independence of geometric variations in input patterns, capability of bridging minor intensity variations in input patterns, etc.

U-Net is a convolutional neural network which takes as input an image and outputs a label for each pixel.[76] U-Net initially was developed to detect cell boundaries in biomedical images. U-Net follows classical autoencoder architecture, as such it contains two sub-structures. The encoder structure follows the traditional stack of convolutional and max pooling layers to reduces the receptive field as it goes through the layers. It is used to capture the context in the image. The decoder structure utilizes transposed convolution layers for upsampling so that the end dimensions are close to that of the input image. Skip connections are placed between convolution and transposed convolution layers of the same shape in order to preserve details that would have been lost otherwise.

In addition to pixel-level semantic segmentation tasks which assign a given category to each pixel, modern segmentation applications include instance-level semantic segmentation tasks in which each individual in a given category must be uniquely identified, as well as panoptic segmentation tasks which combines these two tasks to provide a more complete scene segmentation.[77]

Related images such as a photo album or a sequence of video frames often contain semantically similar objects and scenes, therefore it is often beneficial to exploit such correlations.[78] The task of simultaneously segmenting scenes from related images or video frames is termed co-segmentation,[11] which is typically used in human action localization. Unlike conventional bounding box-based object detection, human action localization methods provide finer-grained results, typically per-image segmentation masks delineating the human object of interest and its action category (e.g., Segment-Tube[12]). Techniques such as dynamic Markov Networks, CNN and LSTM are often employed to exploit the inter-frame correlations.

There are many other methods of segmentation like multispectral segmentation or connectivity-based segmentation based on DTI images.[79][80]

Several segmentation benchmarks are available for comparing the performance of segmentation methods with the state-of-the-art segmentation methods on standardized sets:

• Prague On-line Texture Segmentation Benchmark[81]
• The Berkeley Segmentation Dataset and Benchmark[82]

• Object co-segmentation
• Computer vision
• Image-based meshing
• Range image segmentation
• Vector quantization
• Image quantization
• Color quantization
• Object-based image analysis
• List of manual image annotation tools

• Some sample code that performs basic segmentation, by Syed Zainudeen. University Technology of Malaysia.
• Generalized Fast Marching method by Forcadel et al. [2008] for applications in image segmentation.
• Image Processing Research Group An Online Open Image Processing Research Community.
• Segmentation methods in image processing and analysis and Minimizing energy to segment images by Mathworks
• More image segmentation methods with detailed algorithms by Yu-Hsiang Wang (王昱翔), National Taiwan University, Taipei, Taiwan, ROC
• Online demonstration of piecewise linear image segmentation by IPOL Journal