↑ arvau

Wikipedia / Segmentation-based object categorization

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 applying graph partitioning via minimum cut or maximum cut. Segmentation-based object categorization can be viewed as a specific case of spectral clustering applied 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.

Transportation

  • Partition a transportation network makes it possible to identify regions characterized by homogeneous traffic states.

Segmentation using normalized cuts

Graph theoretic formulation

have low similarity.

Normalized cuts

Let G = (V, E, w be two subsets of vertices.

Let:

In the normalized cuts approach, measures the total similarity of vertices in the same part.

.

is an NP-hard using spectral techniques.

The ncut algorithm

Let:

Also, let D diagonal matrix symmetric matrix.

After some algebraic manipulations, we get:

subject to the constraints:

subject to the constraints above is NP-hard for the second smallest generalized eigenvalue.

The partitioning algorithm:

  1. .

  2. for eigenvectors with the second smallest eigenvalues.

  3. Use the eigenvector with the second 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.

Computational Complexity

Solving a standard eigenvalue problem for all eigenvectors (using the QR algorithm is the number of pixels in the image.

Since only one eigenvector, corresponding to the second smallest generalized eigenvalue, is used by the uncut algorithm, efficiency can be dramatically improved if the solve of the corresponding eigenvalue problem is performed in a matrix-free fashion, i.e., without explicitly manipulating with or even computing the matrix W, as, e.g., in the Lanczos algorithm. Matrix-free methods time.

For high-resolution images, the second eigenvalue is often ill-conditioned, leading to slow convergence of iterative eigenvalue solvers, such as the Lanczos algorithm. Preconditioning is a key technology accelerating the convergence, e.g., in the matrix-free LOBPCG components.

Software Implementations

scikit-learn uses LOBPCG from SciPy with algebraic multigrid preconditioning for solving the eigenvalue problem for the graph Laplacian to perform image segmentation via spectral graph partitioning as first proposed in and actually tested in and.

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

is a shape prior on the labels from a layered pictorial structure is defined as follows.

  1. (1)

.

.

  1. (2)

Algorithm

  1. Given an image D, an object category is chosen, e.g. cows or horses.

  2. The objective function is minimized using a single MINCUT operation to obtain the segmentation m.

Other approaches

References