Image Segmentation

Image thresholding segmentation is a traditional and most commonly used image segmentation method, because of its simple implementation, small amount of computation, more stable performance and become the most basic and widely used segmentation techniques in image segmentation. It is especially suitable for images in which the target and background occupy different gray level ranges. It can not only greatly compress the amount of data, but also greatly simplifies the analysis and processing steps, so in many cases, it is the necessary image pre-processing process before image analysis, feature extraction and pattern recognition.

The purpose of image thresholding is to perform a division of the set of pixels according to the gray level, with each resulting subset forming a region corresponding to the real scene, with consistent properties within each region and no such consistent properties in neighboring regions. Such a division can be achieved by selecting one or more thresholds from the gray level.

The basic principle is that by setting different feature thresholds, the image pixel points are divided into several classes.

Commonly used features include: grayscale or color features directly from the original image; features obtained by transforming the original grayscale or color values.

Let the original image as f(x, y), according to certain criteria f(x, y) to find the eigenvalues T, the image will be split into two parts, after the segmentation of the image is:

If you take: b0 = 0 (black), b1 = 1 (white), that is, we usually call the image binarization.

Threshold segmentation method is actually the input image f to the output image g of the following transformation:

Where T is the threshold value, for the object of the image element g(i,j)=1, for the background of the image element g(i,j)=0.

It can be seen that the threshold segmentation algorithm is the key to determining the threshold value, if you can determine a suitable threshold can be accurate to the image segmentation. After the threshold is determined, the threshold is compared with the gray value of the pixel one by one, and the pixel segmentation can be carried out in parallel for each pixel, and the result of the segmentation directly gives the image region.

The advantages of threshold segmentation are computational simplicity, higher arithmetic efficiency, and speed. There are various thresholding techniques, including global thresholding, adaptive thresholding, optimal thresholding, and so on.

Thresholding techniques:

Region segmentation is the division of an image into different regions according to the similarity criterion, which mainly includes region growing, region splitting and merging, and watershed and other types.

Region growing is an image segmentation method of serial region segmentation. Region growing refers to starting from a pixel and gradually adding neighboring pixels according to certain criteria, and when certain conditions are met, region growing is terminated. The goodness of region growing is determined by 1. the selection of the initial point (seed point). 2. the growth criteria. 3. the termination conditions. Region growing starts from a certain pixel point or certain pixel points and finally gets the whole region, thus realizing the extraction of the target.

The basic idea of region growing is to assemble pixels with similar properties to form a region. Specifically, for each region to be segmented, find a seed pixel as the starting point for growth, and then merge the pixels in the neighborhood around the seed pixel that have the same or similar properties as the seed pixel (according to some pre-determined growth or similarity criterion) into the region where the seed pixel is located. The above process is continued by treating these new pixels as new seed pixels until no more pixels satisfying the conditions can be included. Thus a region is grown.

Region growing involves selecting a set of seed pixels that correctly represent the desired region, determining a similarity criterion for the growing process, and developing conditions or criteria to stop the growth. The similarity criterion can be characteristics such as gray level, color, texture, gradient, etc. The selected seed pixels can be a single pixel or a small region containing several pixels. Most of the region growth criteria use localized properties of the image. Growth criteria can be developed based on different principles, and using different growth criteria affects the process of region growing.

Figure 1 shows an example of region growth.

Region growing is an old method of image segmentation, the earliest region growing image segmentation method was proposed by Levine et al. The method generally has two ways, one is first given a small piece of the image to be segmented within the target object or seed region (seed point), and then in the seed region on the basis of its surrounding pixel points constantly to join them in a certain rule, to achieve the final will represent the object of all the pixels combined into a region of the purpose; the other is to first split the image into a lot of consistency is stronger. The other is to first segment the image into many small regions with strong consistency, such as regions with the same gray value of the pixels, and then merge the small regions into a large region according to certain rules to achieve the purpose of segmenting the image. Typical region growing methods such as the region growing method based on the facet model proposed by T. C. Pong et al. The inherent disadvantage of the region growing method is that it often results in over-segmentation, i.e., the image is segmented into too many regions

The steps of region growing are as follows:

Region growing The steps are as follows:

The basic idea of the region splitting and merging algorithm is to determine a criterion for splitting and merging, i.e., the consistency of the regional features, when the features of a certain region in the image are inconsistent, the region will be split into four equal sub-regions, and when the neighboring sub-regions meet the consistency of the characteristics of the region, then they will be synthesized into a large region, until all the regions no longer satisfy the splitting and merging conditions. Until all regions no longer meet the conditions for splitting and merging. When splitting to the situation that can no longer be divided, the split ends, and then it will find out if there are any similar features in the neighboring regions, and if there are, it will merge the similar regions, and finally achieve the role of segmentation. To a certain extent, region growing and region splitting and merging algorithms have similarities and differences, and promote each other to complement each other, region splitting to the extreme is split into a single pixel, and then merged in accordance with certain measurement guidelines, to a certain extent, can be considered as a single-pixel region growing method. Region growing saves the splitting process over the region splitting and merging method, which allows for similar merging on top of a larger one similar region, whereas region growing can only grow (merge) from a single pixel point.

An algorithm that repeatedly performs splitting and aggregation to satisfy constraints.

Let R denote the whole image region and choose a predicate P. One way to segment R is to iteratively divide the resultant image obtained from the segmentation into four regions again until, for any region Ri, there is P(Ri) = TRUE. here from the whole image. If P(R)=FALSE, the image is partitioned into four regions. For any region if the value of P is FALSE. each of these 4 regions is again divided into 4 regions respectively and so on and so forth. This particular segmentation technique is most conveniently represented in the form of a so-called quadtree (that is, each non-leaf node has exactly 4 subtrees), as is the case with the tree illustrated in Figure 10.42. Note that the root of the tree corresponds to the whole image, and each node corresponds to a subpart of the division. At this point, only R4 undergoes further subdividing.

If only splitting is used, the final partition may contain neighboring regions with the same properties. This shortcoming can be corrected by performing splitting while also allowing region aggregation. That is, two neighboring regions Rj and Rk can be aggregated only if P(Rj ∪ Rk) = TRUE.

The previous discussion can be summarized as the following process. At each step of the iterative operation, we need to do:

There are several variations that can be made to the basic idea described earlier. For example, one possible variation is to start by splitting the image into a set of image blocks. The above splitting is then further performed for each block, but the aggregation operation starts with the restriction that only 4 blocks can be merged into a group. These 4 blocks are descendants of the nodes in the quadtree representation and all satisfy the predicate P. When no further such aggregation can be performed, the process terminates with the final aggregation of regions that satisfies step 2. In this case, the aggregated regions may be of different sizes. The main advantage of this approach is that for both splitting and aggregation the same quadtree is used until the final step of aggregation.

Watershed segmentation method, is a segmentation method based on topological theory of mathematical morphology, the basic idea is to consider the image as a geodesic topological landscape, the gray value of the pixel at each point in the image represents the elevation of the point, each local minima and its influence region is called a catchment basin, and the boundary of the catchment basin forms a watershed. The concept and formation of watersheds can be illustrated by simulating the immersion process. On the surface of each local minima, a small hole is pierced, and then the whole model is slowly immersed into the water. With the deepening of the immersion, the domain of influence of each local minima is slowly extended outward, and a dam is constructed at the confluence of the two catchment basins, i.e., the formation of the watershed.

The watershed calculation process is an iterative labeling process. A more classical calculation method for watersheds was proposed by L. Vincent. In this algorithm, the watershed calculation is divided into two steps, a sorting process and a flooding process. First, the gray level of each pixel is sorted from low to high, and then in the process of realizing the flooding process from low to high, the domain of influence of each local minima in the h-order height is judged and labeled using the first-in-first-out (FIFO) structure.

The Watershed Transform obtains the catch basin image of the input image, and the boundary point between the catch basins, i.e., the watershed. Obviously, the watershed represents the input image extreme value point. Therefore, in order to get the edge information of the image, the gradient image is usually used as the input image, i.e.

The watershed algorithm has a good response to weak edges, and noise in the image, and subtle gray scale changes on the surface of the object, will produce over-segmentation. But at the same time, it should be seen that the watershed algorithm has a good response to weak edges, is obtained closed continuous edges are guaranteed. In addition, the closed catchment basin obtained by the watershed algorithm provides the possibility to analyze the regional characteristics of the image.

To eliminate the over-segmentation produced by the watershed algorithm, two processing methods can usually be used, one is to remove irrelevant edge information using a priori knowledge. The second is to modify the gradient function so that the catchment basin responds only to the target it wants to detect.

To reduce the over-segmentation produced by the watershed algorithm, the gradient function is usually modified, and a simple way to do this is to threshold the gradient image to eliminate the over-segmentation produced by small changes in the gray scale. That is

program can be used method: thresholding the gradient image to achieve the elimination of over-segmentation produced by small changes in gray values, to obtain the appropriate amount of regions, and then the gray level of the edge points of these regions are sorted from low to high, and then in the process of flooding from low to high to achieve flooding, the gradient image is obtained with the calculation of the Sobel operator. When thresholding the gradient image, selecting the appropriate threshold value has a great impact on the final segmented image, so the selection of the threshold value is a key to the effectiveness of image segmentation. Disadvantages: the actual image may contain weak edges, the difference in the value of the gray scale change is not particularly obvious, the selection of the threshold value is too large may eliminate these weak edges.

Reference article:

An important way of image segmentation is through edge detection, which is the detection of places where the gray level or structure has an abrupt change, indicating where one region ends and another begins. Such discontinuities are called edges. Different images have different shades of gray, and there is usually a distinct edge at the boundary, which can be used to segment the image using this feature.

The gray values of the pixels at the edges in an image are discontinuous, and this discontinuity can be detected by taking derivatives. For step-like edges, the location corresponds to the extreme point of the first-order derivative and to the point past zero of the second-order derivative (zero crossing point). Therefore, differential operators are commonly used for edge detection. Commonly used first-order differential operators are Roberts operator, Prewitt operator and Sobel operator, and second-order differential operators are Laplace operator and Kirsh operator. In practice various differential operators are commonly represented by small region templates and differential operations are realized using templates and image convolution. These operators are sensitive to noise and are only suitable for less complex images with less noise.

Since the edge and noise are both gray-scale discontinuous points, in the frequency domain are high-frequency components, it is difficult to overcome the effect of noise by directly using differential operations. Therefore, before detecting edges with differential operators, the image should be smoothed and filtered.LoG operator and Canny operator are second-order and first-order differential operators with smoothing function, edge detection effect is better,

In the edge detection algorithm, the first three steps are used very commonly. This is because in most occasions, it is only necessary for the edge detector to point out that the edge appears in the vicinity of a pixel point in the image, and it is not necessary to point out the exact location or direction of the edge. Edge detection error is usually referred to as edge misclassification error, i.e., false edges are recognized as edges and retained, while true edges are recognized as false edges and removed. Edge estimation error is a probabilistic statistical model that describes the position and orientation error of an edge. We distinguish between edge detection error and edge estimation error because they are computed in completely different ways and their error models are completely different.

Roberts' operator: accurate edge localization, but sensitive to noise. It is suitable for image segmentation with obvious edges and less noise.Roberts edge detection operator is a kind of local difference operator to find the edge of the operator, Robert operator image processing results after the edge is not very smooth. After analysis, because the Robert operator usually produces a wider response in the region near the edge of the image, so the edge image detected using the above operators often need to do refinement processing, edge localization accuracy is not very high.

Prewitt operator: noise suppression, the principle of noise suppression is through pixel averaging, but pixel averaging is equivalent to low-pass filtering of the image, so the Prewitt operator is not as good as Roberts operator for edge localization.

Sobel operator : Sobel operator and Prewitt operator are both weighted average, but Sobel operator that the neighborhood of the pixel on the current pixel is not equal to the impact of the pixel, so pixels with different distances from the pixel with different values of weights, the results of the operator has a different impact. In general, the farther the distance, the less influence it produces.

Isotropic Sobel operator: A weighted average operator, where the weights are inversely proportional to the distance between the neighboring point and the center point, and the gradient magnitude is the same when detecting edges in different directions, which is commonly referred to as isotropic.

In edge detection, a commonly used template is the Sobel operator, there are two Sobel operators, one for detecting horizontal edges; the other for detecting vertical flat edges. horizontal edges. The isotropic Sobel operator has more accurate position weighting coefficients than the normal Sobel operator, and the magnitude of the gradient is the same when detecting edges in different directions. Due to the special characteristics of building images, we can find that the operation on the gradient direction is not required to deal with the contours of this type of image, so the program does not give the processing method of isotropic Sobel operator.

In 1971, R. Kirsch [34] proposed a new method for the Kirsch operator that detects the direction of edges: it uses eight templates to determine the value of the gradient magnitude and the direction of the gradient.

Each point in the image is convolved with 8 masks, each responding maximally to a particular edge direction. The maximum of all 8 directions is used as the output of the edge magnitude image. The ordinal number of the maximum response mask constitutes the encoding of the edge direction.

The value of the gradient magnitude for the Kirsch operator is given by:

Comparison of different detection operators:

References:

Article cited in Wooden Night Trace

Edited by Lornatang

Calibrated by Lornatang