The image segmentation problem is concerned with partitioning an image into multiple regions according to some homogeneity criterion. This article is primarily concerned with graph theoretic approaches to image segmentation.

Applications of Image Segmentation

• Image Compression
  • Segment the image into homogeneous components, and use the most suitable compression algorithm for each component to improve compression.
• Medical Diagnosis
  • Automatic segmentation of MRI images for identification of cancerous regions.
• Mapping and Measurement
  • Automatic analysis of remote sensing data from satellites to identify and measure regions of interest.

Graph theoretic formulation

The set of points in an arbitrary feature space can be represented as a weighted undirected complete graph G = (V, E), where the nodes of the graph are the points in the feature space. The weight of an edge is a function of the similarity between the nodes and . In this context, we can formulate the image segmentation problem as a graph partitioning problem that asks for a partition of the vertex set , where, according to some measure, the vertices in any set have high similarity, and the vertices in two different sets have low similarity.

Normalized Cuts

Let G = (V, E) be a weighted graph. Let and be two subsets of vertices.

Let:







In the normalized cuts approach, for any cut in , measures the similarity between different parts, and measures the total similarity of vertices in the same part.

Since , a cut that minimizes also maximizes .

Computing a cut that minimizes is an NP-hard

NP-hard

NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

 problem. However, we can find in polynomial time a cut of small normalized weight using spectral techniques

Spectral graph theory

In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix....

.

The Ncut Algorithm

Let:



Also, let D be an diagonal matrix with on the diagonal, and let be an symmetrical matrix with .

After some algebraic manipulations, we get:



subject to the constraints:

• , for some constant
• 

Minimizing subject to the constraints above is NP-hard

NP-hard

NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

. To make the problem tractable, we relax the constraints on , and allow it to take real values. The relaxed problem can be solved by solving the generalized eigenvalue problem for the second smallest generalized eigenvalue.

The partitioning algorithm:

1. Given a set of features, set up a weighted graph , compute the weight of each edge, and summarize the information in and .
2. Solve for eigenvectors with the smallest eigenvalues.
3. Use the eigenvector with the smallest eigenvalue to bipartition the graph (e.g. grouping according to sign).
4. Decide if the current partition should be subdivided.
5. Recursively partition the segmented parts, if necessary.

Limitations

Solving a standard eigenvalue problem for all eigenvectors (using the QR algorithm

QR algorithm

In numerical linear algebra, the QR algorithm is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR transformation was developed in the late 1950s by John G.F. Francis and by Vera N. Kublanovskaya , working independently...

, for instance) takes time. This is impractical for image segmentation applications where is the number of pixels in the image.

OBJ CUT

OBJ CUT is an efficient method that automatically segments an object. The OBJ CUT method is a generic method, and therefore it is applicable to any object category model.
Given an image D containing an instance of a known object category, e.g. cows, the OBJ CUT algorithm computes a segmentation of the object, that is, it infers a set of labels m.

Let m be a set of binary labels, and let be a shape parameter( is a shape prior on the labels from a Layered Pictorial Structure (LPS) model). We define an energy function as follows.

(1)

The term is called a unary term, and the term is called a pairwise term.
An unary term consists of the likelihood based on color, and the unary potential based on the distance from . A pairwise term consists of a prior and a contrast term .

The best labeling minimizes , where is the weight of the parameter .

(2)

The OBJ CUT algorithm

1. Given an image D, an object category is chosen, e.g. cows or horses.
2. The corresponding LPS model is matched to D to obtain the samples
3. The objective function given by equation (2) is determined by computing and using
4. The objective function is minimized using a single MINCUT
   Max-flow min-cut theorem
   In optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the minimum capacity which when removed in a specific way from the network causes the situation that no flow can pass from the source to the...
   
    operation to obtain the segmentation m.

Other approaches

• Jigsaw approach
• Image parsing
• Interleaved segmentation
• LOCUS
• LayoutCRF
• Minimum Spanning Tree-based segmentation
  Minimum spanning tree-based segmentation
  -Image segmentation introduction:Image segmentation 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...