Image segmentation

Image threshold segmentation is a traditional and most commonly used image segmentation method. It has become the most basic and most widely used segmentation technology in image segmentation because of its simple implementation, small calculation amount, and relatively stable performance. It is particularly suitable for images where the target and background occupy different gray-scale ranges. It can not only greatly compress the amount of data, but also greatly simplify the analysis and processing steps. Therefore, in many cases, it is a necessary image preprocessing process before image analysis, feature extraction and pattern recognition.

The purpose of image thresholding is to divide the pixel set according to the gray level. Each obtained subset forms a region corresponding to the real scene, and each region has consistent attributes. Neighboring regions do not share this consistent property. Such division can be achieved by selecting one or more thresholds starting from the gray level.

The basic principle is: by setting different feature thresholds, image pixels are divided into several categories.

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

Let the original image be f(x, y), find the feature value T in f(x, y) according to certain criteria, and divide the image into two parts. The divided image is:

p>

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

The threshold segmentation method is actually the following transformation from the input image f to the output image g:

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

It can be seen that the key to the threshold segmentation algorithm is to determine the threshold. If an appropriate threshold can be determined, the image can be accurately segmented. After the threshold is determined, the threshold is compared with the gray value of the pixel one by one, and pixel segmentation can be performed on each pixel in parallel, and the segmentation result is directly given to the image area.

The advantages of threshold segmentation are simple calculation, high computational efficiency and fast speed. There are various threshold processing techniques, including global threshold, adaptive threshold, optimal threshold, etc.

For threshold processing technology, please refer to:

Region segmentation means that the image is divided into different regions according to the similarity criterion, which mainly includes several types such as region growth, region splitting and merging, and watershed.

Region growing is an image segmentation method of serial region segmentation. Region growing means starting from a certain pixel and gradually adding neighboring pixels according to certain criteria. When certain conditions are met, region growing terminates. The quality of regional growth depends on 1. The selection of the initial point (seed point). 2. Growth criteria. 3. Termination conditions. Region growing starts from a certain pixel or certain pixels, and finally obtains the entire region, thereby achieving target extraction.

The basic idea of ??region growing is to gather pixels with similar properties to form a region. Specifically, first find a seed pixel for each area that needs to be segmented as the starting point for growth, and then identify pixels in the neighborhood around the seed pixel that have the same or similar properties as the seed pixel (determined based on some predetermined growth or similarity criterion) Merged into the area where the seed pixel is located. Treat these new pixels as new seed pixels and continue the above process until no more pixels that meet the conditions can be included. Such an area has grown.

Region growing requires selecting a group of seed pixels that can correctly represent the desired area, determining the similarity criteria during the growth process, and formulating conditions or criteria to stop the growth. Similarity criteria can be characteristics such as grayscale, color, texture, gradient, etc. The selected seed pixel can be a single pixel or a small area containing several pixels. Most region growing criteria use local properties of the image. Growth criteria can be developed based on different principles, and using different growth criteria can affect the process of area growth.

Figure 1 is an example of regional growth.

Region growing is an ancient image segmentation method. The earliest region growing image segmentation method was proposed by Levine et al.

This method generally has two methods. One is to first give a small block or seed area (seed point) within the target object to be segmented in the image, and then continuously divide the surrounding pixels into a certain amount based on the seed area. The rules are added to it to achieve the purpose of finally combining all the pixels representing the object into one area; the other is to first divide the image into many small areas with strong consistency, such as small areas with the same pixel gray value in the area. Then fuse small areas into large areas 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 shortcomings of the region growing method are It often results in over-segmentation, that is, dividing the image into too many regions

The steps to implement region growing are as follows:

The basic idea of ??the region splitting and merging algorithm is to first determine a splitting and merging criterion. , which is a measure of regional feature consistency. When the features of a certain area in the image are inconsistent, the area is split into four equal sub-regions. When the adjacent sub-regions meet the consistency characteristics, they are combined into one large area. , until all regions no longer meet the conditions for splitting and merging. When the split is no longer possible, the split ends. Then it will look for similar features in adjacent areas. If so, it will merge the similar areas, and finally achieve the function of segmentation. To a certain extent, the region growing and region splitting and merging algorithms are similar, and they promote each other and complement each other. To the extreme, region splitting is divided into single pixels, and then merged according to certain measurement criteria. To a certain extent, it can be considered as a single pixel. Point region growing method. Compared with the method of region splitting and merging, region growing saves the splitting process. The method of region splitting and merging can perform similar merging on the basis of a larger similar region, while region growing can only grow (merge) starting from a single pixel. .

An algorithm that repeatedly splits and aggregates to satisfy constraints.

Let R represent the entire image area and select a predicate P. One way to segment R is to repeatedly divide the segmented result image into four regions again until P(Ri)=TRUE for any region Ri. Here we start with the whole image. If P(R)=FALSE, the image is divided into 4 areas. For any region if the value of P is FALSE. Just divide each of these 4 areas into 4 areas again, and so on. This particular partitioning technique is most conveniently represented in the form of a so-called quadtree (that is, each non-leaf node has exactly 4 subtrees), such as the tree illustrated in Figure 10.42. Note that the root of the tree corresponds to the entire image, and each node corresponds to a divided subpart. At this time, only R4 has been further subdivided.

If only splitting is used, the final partition may contain adjacent regions of the same nature. This deficiency can be corrected by performing splitting while also allowing region aggregation. That is to say, two adjacent regions Rj and Rk can be aggregated only when 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:

Several variations can be made on the basic ideas described above. For example, one possible variation is to start by splitting the image into a set of image tiles. Each block is then further split as described above, but the aggregation operation starts with the restriction that only 4 blocks can be merged into a group. These four blocks are the descendants of the nodes in the quadtree representation and all satisfy the predicate P. When no more such aggregations can be performed, the process terminates with the last region aggregation that satisfies step 2. In this case, the aggregated regions may vary in size. The main advantage of this approach is that the same quadtree is used for both splitting and aggregation, until the last step of aggregation.

The watershed segmentation method is a mathematical morphological segmentation method based on topology theory. Its basic idea is to regard the image as a topological topography in geodesy. The gray value of each pixel in the image is Representing the altitude of the point, each local minimum and its affected area are called catchment basins, and the boundaries of the catchment basins form a watershed. The concept and formation of watersheds can be illustrated by simulating the immersion process.

On the surface of each local minimum, a small hole is pierced, and then the entire model is slowly immersed in the water. As the immersion deepens, the influence domain of each local minimum slowly expands outward, and in the two water collections Constructing a dam at the confluence of basins forms a watershed.

The calculation process of watershed is an iterative labeling process. The more classic calculation method of watershed was proposed by L. Vincent. In this algorithm, the watershed calculation is divided into two steps, one is the sorting process and the other is the flooding process. First, the gray level of each pixel is sorted from low to high, and then in the process of submerging from low to high, the influence domain of each local minimum value at h-order height is processed using a first-in-first-out (FIFO) structure. Judgment and labeling.

What is obtained by watershed transformation is the catchment basin image of the input image. The boundary points between the catchment basins are the watersheds. Obviously, the watershed represents the maximum value point of the input image. Therefore, in order to obtain the edge information of the image, the gradient image is usually used as the input image, that is, the watershed algorithm has a good response to weak edges. Noise in the image and subtle grayscale changes on the surface of the object will all cause The phenomenon of over-segmentation. But at the same time, it should be noted that the watershed algorithm has a good response to weak edges and is guaranteed to have closed continuous edges. In addition, the closed catchment basin obtained by the watershed algorithm provides the possibility to analyze the regional characteristics of the image.

In order to eliminate excessive segmentation caused by the watershed algorithm, two processing methods can usually be adopted. One is to use prior knowledge to remove irrelevant edge information. The second is to modify the gradient function so that the water collection basin only responds to the target you want to detect.

In order to reduce the over-segmentation caused by the watershed algorithm, the gradient function is usually modified. A simple method is to threshold the gradient image to eliminate the over-segmentation caused by small changes in grayscale. That is,

The program can use a method: limit the gradient image with a threshold to eliminate over-segmentation caused by small changes in gray value, obtain an appropriate amount of areas, and then adjust the gray levels of edge points in these areas. Sort from low to high, and then implement the flooding process from low to high. The gradient image is calculated using the Sobel operator. When thresholding gradient images, selecting an appropriate threshold has a great impact on the final segmented image. Therefore, the selection of threshold is a key to the quality of image segmentation. Disadvantages: The actual image may contain weak edges, and the numerical difference in grayscale changes is not particularly obvious. Selecting a threshold that is too large may eliminate these weak edges.

Reference article:

An important way of image segmentation is through edge detection, that is, detecting where there is a mutation in the gray level or structure, indicating the end of one area and the end of another. Where the zone begins. This discontinuity is called an edge. Different images have different grayscales, and there are generally obvious edges at the boundaries. This feature can be used to segment the image.

The gray value of pixels at the edges in the image is discontinuous. This discontinuity can be detected by taking the derivative. For a step-shaped edge, its position corresponds to the extreme point of the first-order derivative and the zero-crossing point (zero-crossing point) of the second-order derivative. Therefore, differential operators are commonly used for edge detection. Commonly used first-order differential operators include Roberts operator, Prewitt operator and Sobel operator, and second-order differential operators include Laplace operator and Kirsh operator. In practice, various differential operators are often represented by small area templates, and differential operations are implemented using templates and image convolution. These operators are sensitive to noise and are only suitable for images with less noise and less complexity.

Since edges and noise are both gray discontinuous points and high-frequency components in the frequency domain, it is difficult to overcome the influence of noise by directly using differential operations. Therefore, the image must be smoothed and filtered before using differential operators to detect edges. The LoG operator and the Canny operator are second-order and first-order differential operators with smoothing functions and have good edge detection effects.

In edge detection algorithms, the first three steps are very commonly used.

This is because in most cases, the edge detector is only needed to point out that the edge appears near a certain pixel in the image, but there is no need to point out the precise position or direction of the edge. Edge detection error usually refers to edge misclassification error, that is, false edges are distinguished as edges and retained, while true edges are distinguished as false edges and removed. The edge estimation error uses a probabilistic statistical model to describe the edge position and direction errors. We distinguish edge detection error from edge estimation error because their calculation methods are completely different and their error models are also completely different.

Roberts operator: accurate edge positioning, but sensitive to noise. Suitable for image segmentation with obvious edges and less noise. Roberts edge detection operator is an operator that uses local difference operators to find edges. The edges of the image processed by Robert operator are not very smooth. After analysis, since the Robert operator usually produces a wider response in the area near the edge of the image, the edge image detected by the above operator often needs to be refined, and the accuracy of edge positioning is not very high.

Prewitt operator: It has a suppressive effect on noise. The principle of suppressing noise is through pixel averaging, but pixel averaging is equivalent to low-pass filtering of the image, so the Prewitt operator is not as good at positioning edges as the Roberts operator. .

Sobel operator: The Sobel operator and the Prewitt operator are both weighted averages, but the Sobel operator believes that the impact of neighborhood pixels on the current pixel is not equivalent, so pixels with different distances have Different weights have different effects on the operator results. Generally speaking, the farther the distance, the smaller the impact.

Isotropic Sobel operator: Weighted average operator, the weight is inversely proportional to the distance between the adjacent point and the center point. When detecting edges along different directions, the gradient amplitude is consistent, which is commonly referred to as isotropy.

In edge detection, a commonly used template is the Sobel operator. There are two Sobel operators, one is to detect horizontal edges; the other is to detect vertical flat edges. Another form of the Sobel operator is the isotropic Sobel (Isotropic Sobel) operator. There are also two operators, one that detects horizontal edges and the other that detects vertical flat edges. Compared with the ordinary Sobel operator, the isotropic Sobel operator has a more accurate position weighting coefficient, and the magnitude of the gradient is consistent when detecting edges in different directions. Due to the particularity of building images, we can find that when processing the outline of this type of image, there is no need to operate on the gradient direction, so the program does not provide a processing method for the isotropic Sobel operator.

In 1971, R. Kirsch [34] proposed a new Kirsch operator method that can detect edge directions: it uses 8 templates to determine the gradient amplitude value and the direction of the gradient.

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

The gradient amplitude value of the Kirsch operator uses the following formula:

Comparison of different detection operators:

Reference article:

Article Quoted from Mu Yesu

Editing Lornatang

Calibrating Lornatang