Jump to content

Image segmentation

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Yushkevich (talk | contribs) at 19:40, 12 October 2007 (→Open Source Software). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer vision, segmentation refers to the process of partitioning a digital image into multiple regions (sets of pixels). 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. [1] Image segmentation is typically used to locate objects and boundaries (lines, curves, etc.) in images.

The result of image segmentation is a set of regions that collectively cover the entire image, or a set of contours extracted from the image (see edge detection). Each of the pixels in a region are similar with respect to some characteristic or computed property, such as color, intensity, or texture. Adjacent regions are significantly different with respect to the same characteristic(s).[1]

Some of the practical applications of image segmentation are:

  • Medical Imaging[2]
    • Locate tumors and other pathologies
    • Measure tissue volumes
    • Computer-guided surgery
    • Diagnosis
    • Treatment planning
    • Study of anatomical structure
  • Locate objects in satellite images (roads, forests, etc.)
  • Face recognition
  • Automatic traffic contolling systems
  • Machine vision

Several general-purpose algorithms and techniques have been developed for image segmentation. Since there is no general solution to the image segmentation problem, these techniques often have to be combined with domain knowledge in order to effectively solve an image segmentation problem for a problem domain.

Clustering Methods

K-Means Clustering is an iterative technique that is used to partition an image into K clusters. The basic algorithm is:

  1. Pick K cluster centers, either randomly or based on some heuristic
  2. Assign each pixel in the image to the cluster that minimizes the variance 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 (e.g. no pixels change clusters)

In this case, variance 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.

Histogram-Based Methods

Histogram-based methods are very efficient when 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 is repeated with smaller and smaller clusters until no more clusters are formed.[1][3]

One disadvantage of the histogram-seeking method is that it may be difficult to identify significant peaks and valleys in the image. This may affect the quality and usefulness of the final solution.[1]

Region-Growing Methods

In the region-growing technique, a region is started with a single pixel. Adjacent pixels are recursively examined and added to the region if they are sufficiently similar to the region. If a pixel is too dissimilar to the current region, it is used to start a new region.[1]

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

Graph Partitioning Methods

The “normalized cuts” method was first proposed by Shi and Malik in 1997.[4] In this method, the image being segmented is modelled as a weighted undirected graph. Each pixel is a node in the graph, and an edge is formed between every pair of pixels. The weight of an edge is a measure of the similarity between the pixels. The image is partitioned into disjoint sets (segments) by removing the edges connecting the segments. The optimal partitioning of the graph is the one that minimizes the weights of the edges that were removed (the “cut”). Shi’s algorithm seeks to minimize the “normalized cut”, which is the ratio of the “cut” to all of the edges in the set.

Model based Segmentation

By inner forces (ideal: circle) and forces which are computed from the image data, which pull the model towards the object boundary.

Statistical Models: if the object to be segmented is known beforehand, a statistical model can be used to serve as a template.

Multi-scale Segmentation

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.

Semi-automatic Segmentation

In this 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 Livewire or Intelligent Scissors are used in this kind of segmentation.

Neural Networks Segmentation

That kind of segmentation relays on processing small areas of an image by the neural network or a set of neural networks. After such processing the decision-taking mechanism marks the areas of an image accordingly to the category recognized by the neural network.

Open Source Software

Several open source software packages are available for performing image segmentation

There are also free academic software packages:

See also

References

  1. ^ a b c d e f g Linda G. Shapiro and George C. Stockman (2001): “Computer Vision”, pp 279-325, New Jersey, Prentice-Hall, ISBN 0-13-030796-3
  2. ^ Dzung L. Pham, Chenyang Xu, and Jerry L. Prince (2000): “Current Methods in Medical Image Segmentation”, Annual Review of Biomedical Engineering, volume 2, pp 315-337
  3. ^ Ron Ohlander, Keith Price, and D. Raj Reddy (1978): “Picture Segmentation Using a Recursive Region Splitting Method”, Computer Graphics and Image Processing, volume 8, pp 313-333
  4. ^ Jianbo Shi and Jitendra Malik (1997): "Normalized Cuts and Image Segmentation", IEEE Conference on Computer Vision and Pattern Recognition, pp 731-737
Retrieved from "https://en.wikipedia.org/w/index.php?title=Image_segmentation&oldid=164114854"