Image segmentation

The segmentation is a branch of digital image processing and computer vision. The generation of the content of connected regions by grouping neighboring pixels or voxels corresponding to a certain homogeneity criterion is referred to as segmentation.

• 6.1 image processing programs
• 6.2 image editing programs
• 6.3 handwriting recognition and special software

classification

Segmentation is the process of machine vision usually the first step of image analysis and comes after the image preprocessing. The flow is therefore

Scene → Picture → Record → Preprocessing Segmentation Feature Extraction → → Classification → statement

Properties

One speaks of a complete segmentation, if each pixel is assigned to at least one segment. For a free of covering segmentation, each pixel is associated with at most one segment. For a complete and free of covering segmentation, each pixel is thus assigned to exactly one segment. A segmentation is called connected if each segment forms a contiguous area.

Method

There are known many methods for automatic segmentation. Basically, they are often divided into pixel-, edge - and region- based techniques. Additionally, a distinction is model-based method in which starting from a specific shape of the objects, and texture-based method in which a homogeneous inner structure of the objects is taken into account.

The boundaries between the methods are often blurred. Also, one may combine various methods, in order to achieve better results.

Of course you can also in a non-automatic method to perform the segmentation, that is, a man takes the division before. Since the automatic methods are far from perfect, there is also the possibility for semi-automatic processing.

Pixel-oriented method

Make pixel -oriented method for each individual pixel to decide whether it belongs to a particular segment or not. This decision may - but need not - be affected by the environment. Point -based methods are usually easy to calculate and so quickly, deliver, per se, but initially not contiguous segments. From segmentation occurs when individual objects are countable on a binarized image. Each segmented object is then, for example, described by a run-length encoding of the binarized pixels. Binarization is the precursor of a segmentation.

The most widely used threshold method is certainly the threshold method. This method is based on a threshold that is best determined on a histogram.

In the figure, the background is brighter than the black object. In the simplified case, the threshold of binarization results from the average of the darkest and brightest gray value in the image. The segmentation is often the precursor of a classification.

Edges oriented methods

In these processes is searched in the image object edges or transitions. Many algorithms do not yet provide closed edge features, these need to be combined with other methods, so that they include objects. Actually edges are always between the pixel regions of an image. The results of an algorithm can polygons (or lines or curves in special cases ) be, but some operations return the edges as different colored pixels. The OpenCV software each segmented object is described by an enclosing polygon. Segmentation can also be used to divide an image into a foreground layer and a background layer.

With methods such as the Sobel operator and the Laplace operator, and a gradient can be found to an edge corresponding pixels. However, these are usually initially loose and must be completed with edge tracking algorithms. A popular method for generating a coherent object silhouette edges, or at least of trains from the edge pixels is the live -wire method of E. Mortensen, WA Barrett and JK Udupa. The idea can be spoken clearly compared with a navigation system, which determines an optimal path from start to destination. Optimal means in the context of the segmentation, that the path between the start and finish always leads on the strongest edge pixels. The optimal routing is then a standard problem in computer science and can for example be achieved by a breadth-first search.

A very well known method is the watershed transformation, which works on grayscale images and always closed edges trains supplies. Other methods are parallel and sequential edge extraction, optimal edge search, Felzenszwalb - Huttenlocher algorithm, Active Shape Models and Snakes.

Region -based method

The region- based procedures consider point sets as a whole and thereby try to find related objects. Are frequently used methods such as region growing, region splitting, Pyramid Linking and Split and Merge.

Mathematically sophisticated can not be understood as a matrix of pixels, but as a continuous function of the image in the color space mapping, for example, the unit square ( example: on a grayscale image ).

Energy methods assign each possible segmentation of the image to a real energy value and are looking for a minimum of this energy functional. This case, a segmentation of an image with areas of uniform (often constant ) is understood color intensity between regions separated a lot. It can be used depending on the application field different energies. Most enter:

• The difference between the original image and segmentation, for example,
• A measure of the length of the edge between each segmentation regions, for example, the two-dimensional Hausdorff dimension than the length of the edge segmentation.
• When the segmentation regions need not have constant intensity: A measure of intensity differences, such as.

Possible solution method are then:

• Graph cut method, who stem from the continuous model, although a discrete algorithm shown
• Variational methods that achieve a descent of the energy function as a solution of a partial differential equation.

The former are present for smaller images in real time (30 fps) feasible, but offer maximum pixel accuracy. The variation approach, however, also allows sub-pixel accuracy. This is extremely helpful, which always produce jaggies at discrete method especially at diagonal edges. There are currently researching methods to solve the variational problems on the processors of graphics cards ( Graphic Processing Unit, GPU). It can be predicted speed advantages of a factor of 5 to 40, whereby the variation approaches would be much faster.

Continuous methods are explored with visible success only since about 2002 and are therefore not to be found in end-user software.

Model-based methods

Here, a model of the objects sought will be used. This may concern, for example the shape. So you use prior knowledge of the image with a. A known method is the Hough transformation, with which one can combine points to lines or circles, by depicting them in a parameter space. It continues to find statistical models and segmentation via templates ( template matching ) use. In the latter method in the image templates are searched for the given.

Texture -based method

Some image objects do not have a uniform color, but a uniform texture. For example, an object may have grooves, which appear as alternating strips of dark and light color in photography. Thus, these objects are not broken down into many small objects on the basis of texture, to use approaches that we have tried to address this problem. These processes are partly in the border area for classification or permit simultaneous segmentation and classification.

• Cooccurrence matrices ( Haralick matrices )
• Texture energy measures (Texture Energy Measure)
• Lauflängenmatrizen ( run-length matrix )
• Fractal dimensions and dimensions
• Markov Random Fields and Gibbs potentials
• Structural approaches
• Signal theory concepts

Problems

Often the quality of the segmentation is not optimal. In these cases, one can select a better method, or one can optimize the results by connecting a pre-processing (including preprocessing ) or a post-processing. Both can either automatically ( if you have already identified the problems of the process) as well as made ​​by hand.

A problem with many segmentation algorithms is the susceptibility for changing illumination within the image. This can lead to only one part of the image is segmented correctly, but in the other parts of the image segmentation is unusable. Brightness differences can be compensated with a pre-processing, for example by applying a shading correction.

Common problems include, for example, over-segmentation (too many segments) and sub- segmentation ( too few segments). This can be countered by enriching the method to knowledge of data to be processed, in the simplest case, you can specify the expected number of segments. In addition, you can insert a subsequent classification step to combine the same classified segments. Of course, the segments can also be combined by hand.

Many of the algorithms ( thresholding, watershed transformation ) only work on single-channel grayscale images. In the processing of multichannel images (eg color images ) information remains unused. It requires more processing steps to combine several single channel segmentations.

Applications

Segmentation is often the first step of image analysis for subsequent processing of the data, such as a classification.

The applications for such a method are many. The most common automatic segmentation in medicine are currently being applied, for example, in computed tomography or magnetic resonance imaging. Also in the spatial data processing segmentations are used, for example, satellite images or aerial photographs (see Remote Sensing ) segmented into geometrical data. Also, for automatic optical quality control of workpieces ( for example: Is the hole in the right place? ) Is used segmentation. Also segmentation for optical character recognition (OCR ) is used to separate by binarization of the scanned image signature from the background. Another issue is the facial recognition.

Software

Image processing programs

Image processing programs provide segmentation algorithms and ' higher ' image processing algorithms based on different segmentation algorithms. With these programs, you can, for example, in a robotic application can determine positions of objects (see image processing ).

Image editing programs

Many image editing programs such as the free GIMP and the free IrfanView offer simple segmentation algorithms, such as after thresholding or edge detection with Sobel or Laplace operators.

Handwriting recognition and special software

Writing recognition programs can be used as a first step, a segmentation to separate the writing from the background.

With the special software for segmentation of images also medicine and Geoinformatics are frequent target applications.