CN106447676A - Image segmentation method based on rapid density clustering algorithm - Google Patents

Abstract

An image segmentation method based on a fast density clustering algorithm, comprising the following steps: 1) For a natural image to be processed, firstly perform preprocessing and initialization, including filter noise reduction, grayscale correction, region block and scale scaling etc.; 2) Then calculate the similarity distance between data points on the sub-images that have completed the scale transformation, and obtain the correlation between pixels; 3) Then perform parallel segmentation processing in each sub-image, including density-based clustering The algorithm draws a decision diagram, performs residual analysis based on the decision diagram to determine the cluster center and classifies the remaining points on the original scale subgraph based on the similarity distance comparison; Reclustering results in a segmentation map of the original size. The invention provides an image segmentation method based on a fast density clustering algorithm that can automatically determine the number of segmentation categories, achieve high segmentation accuracy, and is robust to parameters.

Description

A Method of Image Segmentation Based on Fast Density Clustering Algorithm

technical field

The invention belongs to the technical field of image processing, and in particular relates to an image segmentation method.

Background technique

Image segmentation is one of the key technologies of image processing, which is widely used. The main task is to divide the image into several specific and unique regions, which have strong similarities within the regions and strong differences between the regions. At the same time, image segmentation is also an important step in data analysis and understanding of images, and is the key from image processing to image analysis. The existing image segmentation methods are mainly divided into the following categories: boundary-based segmentation methods, region-based segmentation methods, and specific theory-based segmentation methods. After the image segmentation is completed, the extracted objects can be used in image semantic recognition, image search and other fields, so the quality of image segmentation results will directly affect the accuracy of subsequent recognition or search.

Due to the ambiguity and complexity of images, there is currently no general segmentation theory that can be generally applied to the segmentation of various images. Most of the segmentation algorithms that have been proposed are aimed at specific problems, so it is still necessary to continue to explore new segmentation algorithms and methods. Segmentation theory, which is also the purpose of this study. The boundary-based segmentation method is to determine the segmentation boundary by detecting the gray level or the place where the structure has a sudden change, including the commonly used first-order differential operators are Roberts operator, Prewitt operator and Sobel operator, and the second-order differential operator is Laplace operator and Kirsh operator etc. Wang Junmin analyzed the basic principles of Roberts operator, Prewitt operator, Sobel operator, Laplace operator, and LOG operator in "Edge Detection and Application Based on Differential Operators", and summarized the advantages of various operators. shortcoming. Canny proposes a new edge detection method, which is optimal for step-type edges affected by white noise, but there are boundary discontinuities. Miao Jiaqing used the adaptive dictionary learning algorithm to improve the canny operator in "Adaptive Dictionary Improves Canny Operator CT Image Segmentation". Region-based segmentation methods include parallel region segmentation techniques and serial region segmentation techniques. The most typical parallel region segmentation technique is the threshold segmentation method, the key of which is to determine the segmentation threshold, so the global threshold, adaptive threshold, optimal threshold and so on are derived. In "Implementation and Comparison of Several Image Threshold Segmentation Algorithms", Chen Ningning made a comprehensive comparison of commonly used threshold determination methods such as histogram threshold method, iterative method and Otsu method, and Ma Yinghui et al. The traditional gray-level threshold method is applied to color images, and more color information of color images is used to obtain better segmentation results. Region growing method and split-merge method are two typical serial region techniques, which need to design the growth criterion and split-merge criterion, and the processing of the subsequent steps of the split process should be determined according to the results of the historical steps. With the introduction of many new theories and methods in various disciplines, many image segmentation methods combined with some specific theories and methods have emerged, including image segmentation based on genetic algorithms, image segmentation based on artificial neural networks, and image segmentation based on objective function optimization. Image segmentation, image segmentation based on cluster analysis, image segmentation based on MRF, image segmentation based on fuzzy set theory, etc.

With the emergence of various new clustering methods in recent years, many image segmentation methods based on clustering algorithms have been derived. Compared with other specific theoretical segmentation methods, image segmentation methods based on cluster analysis provide an image segmentation method. new ideas. At the same time, recent studies have shown that the comprehensive use of image color information, position information between pixels, texture information of local regions and context information of pixels can greatly improve the segmentation results. The image segmentation method based on the clustering algorithm is also called the feature space clustering method. The key to transforming the image segmentation problem into a clustering problem is to use the feature space points to represent the corresponding pixel points in the image space, according to their aggregation in the feature space As a result, the feature space points are segmented, and then they are mapped to the original image space to obtain the final segmentation result. Classic clustering algorithms include FuzzyC-means, K-means, Ncut, SLIC, Mean-shift, etc. Alex et al. proposed a novel clustering center characterization method, which provides a new idea for the design of clustering algorithms. A series of solutions are proposed for the contradiction between the high time complexity and high space complexity of large data volume and the huge amount of image data.

Contents of the invention

In order to overcome the shortcomings of the existing image segmentation methods based on clustering algorithms, which are sensitive to cluster centers, large parameter dependence, poor adaptability, and the number of segmented clusters cannot be accurately and automatically determined, the present invention provides a method that can automatically determine the segmentation category. An image segmentation method based on fast density clustering algorithm with high segmentation accuracy and robustness to parameters.

The technical solution adopted by the present invention to solve its technical problems is:

A kind of image segmentation method based on fast density clustering algorithm: described method comprises the following steps:

1) Initialization, the process is as follows:

1.1) Firstly, the area division operation is performed. For an image to be processed, it contains pixels of M rows and N columns. After preprocessing, the image is divided into 2 ^W1 × 2 ^W2 sub-images, and the obtained sub-image size for Where Z[f] is the forward rounding function;

1.2) Then perform scale transformation operation on the image, and perform scaling processing on the sub-image after block division, that is, the sub-image with size a*b becomes a ₁ *b ₁ , where a ₁ =a/k _size and b ₁ = b/k _size , k _size >1; in the scaling process, because each pixel contains three pixel values, the method of weak sampling is used for scale transformation, and the number of pixels contained in the image to be processed is reduced While retaining the important clustering information of the original image as much as possible;

2) Calculation of similarity distance based on pixel value and position information, the process is as follows:

2.1) For a natural image I to be processed, which contains M rows and N columns of pixels, let n=M*N, then the pixel data set The feature information that each pixel has in includes the three-color channel component values in the RGB color space, that is, the three pixel values of R, G, and B; , the coordinate value (x, y) in the two-dimensional plane Cartesian coordinate system where the vertical line goes downward to the X axis;

2.2) Let d _p (p1, p2) be the similarity distance between two pixels, the similarity distance calculation formula is as follows:

d _p (p1,p2)=θd _{p_rgb} (p1,p2)+(1-θ)d _{p_xy} (p1,p2) (3)

In formula (1), r1, g1, b1 and r2, g2, b2 respectively represent pixel values of pixel points p1 and p2 in RGB color space, and d _{p_rgb} represents the distance between pixels in this space; formula (2) Among them, x1, y1 and x2, y2 respectively represent the coordinate values of pixel points p1 and p2 in the Cartesian coordinate system, and d _{p_xy} represents the distance between pixels in the coordinate system. In formula (3), θ is the weight factor, Used to adjust the contribution of color distance and position distance to similarity determination;

3) Automatically determine the density clustering of the cluster center, and operate the subgraph, the process is as follows:

3.1) Calculating the similarity distance between image pixels, it is known that there is a duality in the similarity distance between pixels, that is, d _p (p1, p2) = d _p (p2, p1), and d _p (p1, p1) = 0, so the similarity distance is stored as an upper triangular matrix {Dp _ij } whose diagonal data is zero;

3.2) Calculate the density value of each pixel point to obtain the density matrix Calculated as follows:

which function

In formula (4), ρ _i represents the density value of pixel point p _i , and the pixel set of the image The corresponding index set is I _s ={1,2,...,M*N}, d _ij =d _p (pi,pj) represents the similarity distance between two pixels;

3.3) Calculate the distance value of each pixel point to obtain the distance matrix The distance value of each pixel p _i is defined as δ _i , firstly find the pixel point with density higher than p _i , get the set S'={p _j }, and then find the pixel point p in S' with the closest distance to p _{i j} ', then get δ _i =d _p (pi,pj');

3.4) Obtained according to step 3.2) and step 3.3) and Draw a decision-making map to obtain a discrete function δ _i = f(ρ _i ) representing the relationship between pixel density and distance;

3.5) Carry out unary linear fitting by the discrete data points on the ρ-δ relationship diagram to obtain the fitting curve y _δ =kx _ρ +b ₀ and Calculate the residual value of each data point ε _δi ＝y _δi -δ _i and ε _ρi ＝x _ρi -ρ _i , draw the residual histogram ε _δi -h and ε _ρi -h , and use the bell curve for normal fitting Combined to get the variance values σ _δ and σ _ρ , use the λσ principle to determine the singular point outside the confidence interval as the cluster center, denoted as c _δ and c _ρ ;

3.6) Obtain the bivariate discrete function γ=f _γ (ρ,δ) from the decision diagram, and perform the fitting of the binary slope, and obtain the fitting plane as z _γ =b ₁ +b ₂ ρ+b ₃ δ, and calculate each The residual value of the data point ε _γi = y _γi (ρ,δ)-γ _i (ρ,δ), draw the residual histogram ε _γi -h, and also use the bell curve for normal fitting to obtain the variance value σ _γ , use the λσ principle to determine the singular point outside the confidence interval as the cluster center, denoted as c _γ ;

Among them, the function f _γ is a binary function about the variables ρ and δ, corresponding to the coordinate value in the three-dimensional space is (ρ, δ, f _γ ), then the bivariate discrete function is defined as:

In formula (5), take the logarithmic value of the product of the density value and the distance value as the function value; add 1 so that the formula still holds true when the density is zero, that is, no point falls within the d _c radius; Represents the cumulative sum of the density values corresponding to the original image p _i point and its four neighbors, a total of five pixel points, and increases the weight value of the density component to determine the cluster center;

3.7) Take the union of the cluster centers determined by step 3.5) and step 3.6) to obtain the final cluster center of the image c _δργ = c _δ ∪c _ρ ∪c _γ is a set containing n elements, and then according to the nearest neighbor In principle, classify the remaining pixels and fill the homogeneous area with the pixel values of the cluster center points;

3.8) Repeat steps 3.1) to 3.7) for each sub-image, then merge the sub-images to obtain an intermediate result image;

4) Secondary re-clustering, the process is as follows:

4.1) Scale the intermediate result map obtained in step 3.8) to the required scale, use the color distance d _{p_rgb} (p1, p2) as the similarity measure of re-clustering, and calculate and Draw the ρ-δ relationship diagram to obtain the discrete function δ _i =f(ρ _i );

4.2) Calculate the bivariate discrete function γ=f _γ (ρ, δ) from the relationship of δ _i = f(ρ _i ) obtained in step 4.1), perform the fitting of the binary slope, and calculate the residual value ε _γi of each data point =y _γi (ρ,δ)-γ _i (ρ,δ), draw the residual histogram ε _γi -h, also use the bell curve for normal fitting, get the variance value σ _γ , use the λσ principle to determine the The singular point outside the confidence interval is used as the cluster center, denoted as c _γ ;

4.3) Scale playback the clustering center c _γ obtained in step 4.2) in the spatial domain to obtain the clustering center of the intermediate result image of the original size, classify the remaining pixels according to the nearest neighbor principle, and use the clustering center’s Pixel values fill homogeneous areas.

Further, in the step 3.2), d _c is a positive real number, which is used to describe the circle with the pixel p _i as the center and d _c as the radius, and the density value ρ _i is the number of pixels falling inside the circle ; Take 2% of the similarity distance between the pixel point p _max at the maximum sum of the pixel value accumulation of each channel under the color space and the pixel point p _min at the minimum sum of pixel value accumulation of each channel as the d _c value, and the calculation formula is as follows:

In formula (6), Indicates that if there are multiple pixels in an image, the cumulative sum of pixel values in the color space is equal to the maximum or minimum, then take the average, that is

Further, in the step 3.7), the finally obtained cluster center c _δργ is obtained by taking the union of the cluster centers c _δ , c _ρ , and c _γ obtained from the cubic regression analysis, and the clustering segmentation results are displayed in the graph When , the pixel value of the cluster center obtained in the case of over-segmentation is used to fill the cluster area.

Furthermore, in the step 4.2), the judgment basis for the automatic determination of the cluster centers of the secondary re-clustering no longer uses the union of c _δ , c _ρ , and c _γ , and only performs histogram analysis on the γ value.

The technical idea of the present invention is: the image segmentation method based on the fast density clustering algorithm can automatically determine the number of segmentation categories in the segmentation of natural images, and realize image segmentation with high segmentation accuracy and robustness to parameters. For a natural image to be processed that contains M rows and N columns of pixels, firstly perform preprocessing, including filter denoising, grayscale correction, etc.; then divide the image into blocks to obtain equal-sized subimages; The rapidity of the algorithm, while comprehensively considering the time complexity and the integrity of the clustering information, each sub-graph is scaled in equal proportions to obtain the scale-transformed sub-graph; then the data points of the scale-transformed sub-graph are Calculate the similarity distance between pixels to obtain the correlation between pixels; then perform parallel segmentation processing in each sub-image, including drawing a decision graph based on the density clustering algorithm, and determine the cluster center and Based on the similarity distance comparison, the remaining points on the original scale sub-images are classified; then the sub-images after segmentation are merged and re-clustered to obtain the segmentation result image of the original size. The fusion of images includes fusion of adjacent areas on the division line in the sub-image and fusion of adjacent areas on the boundary line of the sub-image block, thereby obtaining an intermediate result image. Finally, the intermediate results of the rough fusion are re-clustered twice, and the non-adjacent homogeneous regions are merged to obtain the final result map.

The beneficial effects of the present invention are mainly manifested in that the number of image segmentation categories can be automatically determined, the accuracy of the final segmentation result is high, and the problem of parameter sensitivity in the image segmentation process is reduced. Experimental results on real images show that the algorithm has good applicability and precision, can effectively segment images adaptively, and achieve better segmentation results.

Description of drawings

Figure 1 is a flow chart of scaling an image.

Figure 2 is a schematic diagram of a digital storage model for natural images.

Figure 3 is a flow chart of finding the cluster centers by unary linear fitting of the _subgraphs according to the _ρ - _δ relationship. Find the cluster centers c _ρ .

Fig. 4 is a flow chart of finding the cluster center c _γ by binary slope fitting using the γ=f _γ (ρ, δ) function.

Fig. 5 is a flow chart of automatically determining the final cluster center.

Fig. 6 is a flowchart of an image segmentation method based on a fast density clustering algorithm.

detailed description

The present invention will be further described below in conjunction with the accompanying drawings.

With reference to Fig. 1～Fig. 6, a kind of image segmentation method based on fast density clustering algorithm comprises the following steps:

1) Initialization. In order to speed up the processing speed of the algorithm and reduce the processing time, this paper mainly reduces the size of the image through the combined effect of regional block and scale transformation, and at the same time can retain the most important information for cluster center search. The process is as follows :

1.1) Firstly, the area division operation is carried out. For an image to be processed, which contains pixels in M rows and N columns, after preprocessing such as noise reduction filtering, the image is divided into 2 ^W1 × 2 ^W2 sub-images, and the obtained The size of the subplot is Where Z[f] is the forward rounding function;

1.2) In order to further reduce the number of pixels contained in the image to be processed, the sub-image after the block is completed is scaled, that is, the sub-image with a size of a*b is changed to a ₁ *b ₁ , where a ₁ =a /k _size and b ₁ =b/k _size , k _size >1. In the scaling process, because each pixel contains three pixel values, the method of weak sampling is used for scale transformation, and the important clustering information of the original image is preserved as much as possible while reducing the number of pixels to be processed.

The specific scaling algorithm flow is shown in Figure 1, where the function of the imresize(I,[a1,b1]) function is to transform the scale of the image I into a1*b1 by using Gaussian blur and then downsampling. Through regional block and scale transformation, the amount of data to be processed can be reduced to an acceptable range, thereby speeding up the processing speed.

2) Calculation of similarity distance based on pixel value and position information, the process is as follows:

2.1) For a natural image I to be processed, which contains M rows and N columns of pixels, let n=M*N, then the pixel data set The characteristic information that each pixel has in includes the three-color channel component values under the RGB color space, that is, the three pixel values of R (red), G (green), and B (blue); and in the upper left corner of the image is the coordinate value (x, y) in the two-dimensional plane Cartesian coordinate system where the origin of coordinates, the horizontal line to the right is the Y axis, and the vertical line is downward to the X axis. Then define the representation of each pixel on the image as p _i (r _i , g _i , b _i , _xi , y _i ), as shown in Figure 2, which is the digital storage model of two pixels in a natural image.

2.2) When determining the similarity distance, Euclidean distance is used for calculation, p1 and p2 represent two different pixel points, then the color difference and position difference between two pixel points can be expressed as follows by color distance and position distance :

In the formula (1), r1, g1, b1 and r2, g2, b2 respectively represent the pixel values of the pixel points p1 and p2 in the RGB color space, and d _{p_rgb} represents the distance between pixels in the space; in the formula (2) x1, y1 and x2, y2 respectively represent the coordinate values of pixel points p1 and p2 in the Cartesian coordinate system, and d _{p_xy} represents the distance between pixels in the coordinate system. The dimensions of the pixel value and the coordinate value are different, so the two types of information are internally normalized in the formula, and an excellent result with unified weight is obtained. Because each pixel value of the image processed later in this paper is stored in 8-bit binary, 2 ⁸ -1 is used as the reference value when normalizing the pixel value. M and N represent the size of the input image with N pixels per row and M pixels per column.

2.3) Finally, calculate the similarity distance d _p (p1,p2) between two pixels. The larger the distance value, the greater the difference and the lower the similarity. The formula for calculating the similarity distance is as follows:

d _p (p1,p2)=θd _{p_rgb} (p1,p2)+(1-θ)d _{p_xy} (p1,p2) (3)

In formula (3), θ is a weighting factor, which is used to adjust the contribution of color distance and position distance to similarity determination.

The similarity distance is not only used for cluster analysis. After the cluster center is determined, it is also necessary to determine its attribution according to the similarity distance from each pixel point to the cluster center. After all the pixel points are classified, the segmentation result is obtained. The location information is added to the calculation of the similarity distance, and the interaction between the pixels that are far away from each other in the spatial position is weak. In the image data set When the amount of data is small, it will lead to the problem that the edge of the segmentation block is not smooth enough, and it does not meet the friendly relationship in visual interaction. In order to solve this problem, the color space conversion of the obtained segmentation results is performed, from RGB to HSV color space, and then the median filter is performed on the V channel information representing the brightness under the HSV model, and then the HSV is converted to the RGB model again Output and get a visually friendly segmentation result map.

3) Automatically determine the density clustering of the cluster center, and operate the subgraph, the process is as follows:

Definition 1 Suppose that for an image I containing n pixels, it corresponds to two one-dimensional data matrices, represents the density matrix, Represents a distance matrix, the size of which is 1 row and n columns. The mapping relationship between the data in the i-th column of the density matrix or distance matrix and the pixels in Mx rows and Nx columns in the original image is as follows:

i=N(Mx-1)+Nx (7)

3.1) Calculating the similarity distance between image pixels, it is known that there is a duality in the similarity distance between pixels, that is, d _p (p1, p2) = d _p (p2, p1), and d _p (p1, p1) = 0, so the similarity distance is stored as an upper triangular matrix {Dp _ij } whose diagonal data is zero;

3.2) Calculate the density value of each pixel point to obtain the density matrix Calculated as follows:

which function

In formula (4), ρ _i represents the density value of pixel point p _i , and the pixel set of the image The corresponding index set is I _s ={1,2,...,M*N}, d _ij =d _p (pi,pj) represents the similarity distance between two pixels;

In order to reduce the space complexity during operation, at the cost of increasing a certain time complexity, the present invention adopts an improved density matrix calculation method, and the specific density matrix algorithm steps are as follows:

3.2.1) Input a digital image I containing M rows and N columns of pixels and the search radius d _c , set the initial value of the cycle, i1=j1=1, i2=j2=1, i=1, and allocate the storage of the density matrix space, recorded as n=M*N, the initial value is set to 0;

3.2.2) Calculate the similarity distance between pixel point (i1, j1) and point (i2, j2) in the image, which is recorded as d _p (p _{(i1, j1)} ,p _{(i2, j2)} ), if d _p ( p _(i1,j1) ,p _(i2,j2) )>d _c , then ρ _i =ρ _i +0, otherwise ρ _i =ρ _i +1;

3.2.3) j2=j2+1, if j2≤N, return to step 3.2.2), otherwise set j2=1, execute step 3.2.4);

3.2.4) i2=i2+1, if i2≤M, then return to step 3.2.2), otherwise make i2=1, execute step 3.2.5);

3.2.5) j1=j1+1, i=i+1, if j1≤N, return to step 3.2.2), otherwise set j1=1, execute step 3.2.6);

3.2.6) i1=i1+1, if i1≤M, return to step 3.2.2), otherwise set i1=1, execute step 3.2.7);

3.2.7) Output the final density matrix

In the above algorithm, {Dp _ij } is not stored in advance and then determined Instead, when calculating the density value of each pixel point, the similarity distance between the pixel point and other n-1 pixel points is calculated in advance. After the density calculation of the point is completed, the similarity distance will be stored. Space release, which greatly reduces the memory consumption at runtime.

3.3) Calculate the distance value of each pixel point to obtain the distance matrix The distance value of each pixel p _i is defined as δ _i , firstly find the pixel point with density higher than p _i , get the set S'={p _j }, and then find the pixel point p in S' with the closest distance to p _{i j} ', then get δ _i =d _p (pi,pj'), the specific distance matrix algorithm is as follows:

3.3.1) Sort the density matrix in step 3.2) from large to small to obtain an ordered new density matrix At the same time, the index array is calculated according to the mapping relationship of definition 1 save the new density matrix The mapping relationship with the position between each pixel point of the original image, set the initial value of the cycle i1=j1=1, ind1=1;

3.3.2) Calculate the distance between the pixel point p _ρ'1 corresponding to the maximum density ρ'1 and the rest of the pixels, the calculation formula is δ_temp( ₁ ,ind)=d _p (p _(i1,j1) ,p _{ρ' 1} );

3.3.3) j1=j1+1, ind1=ind1+1, if j1≤N, return to step 3.3.2), otherwise set j1=1, execute step 3.3.4);

3.3.4) i1=i1+1, if i1≤M, return to step 3.3.2), otherwise set i1=1, execute step 3.3.5);

3.3.5) Find the maximum value of δ_temp(1, ind) as the similarity distance value of the pixel with the highest density, that is, δ' ₁ =MAX{δ_temp(1,i)|i∈(1,n)};

3.3.6) Set the loop initial value i1=2, i2=1;

3.3.7) Calculate the remaining pixels The distance value to the pixel point whose density is larger than this point, the calculation formula is δ_temp(1,i2)=d _p (p _ρ'i1 ,p _ρ'i2 );

3.3.8) i2=i2+1, if i2≤i1-1, return to step 3.3.7), otherwise take the minimum value as the similarity distance value, that is, δ' _i1 =MIN{δ_temp(1,i)| i∈(1,i2)}, execute step 3.3.9);

3.3.9) i1=i1+1, if i1≤M*N, return to step 3.3.7), otherwise execute step 3.3.10);

3.3.10) indexed by Will Maps to the original density matrix The distance storage unit corresponding to the position output distance matrix

3.4) Obtained according to step 3.2) and step 3.3) and Draw a decision-making map to obtain a discrete function δ _i = f(ρ _i ) representing the relationship between pixel density and distance;

3.5) Carry out unary linear fitting by the discrete data points on the ρ-δ relationship diagram to obtain the fitting curve y _δ =kx _ρ +b ₀ and Calculate the residual value of each data point ε _δi ＝y _δi -δ _i and ε _ρi ＝x _ρi -ρ _i , draw the residual histogram ε _δi -h and ε _ρi -h , and use the bell curve for normal fitting Combined to get the variance values σ _δ and σ _ρ , use the λσ principle to determine the singular point outside the confidence interval as the cluster center, denoted as c _δ and c _ρ , the algorithm flow chart is shown in Figure 3;

Definition 2 Let the function f _γ be a binary function about the variables ρ and δ, corresponding to the coordinate value in the three-dimensional space is (ρ, δ, f _γ ), then the bivariate discrete function is defined as:

In the formula (5), the logarithm of the product of the density value and the distance value is taken as the function value; adding 1 is to make the formula still hold when the density is zero, that is, when no point falls within the d _c radius, and has no actual physical meaning ;There is context information between the pixels of the image, and the corresponding density matrix also contains context information, so Indicates the cumulative sum of the density values corresponding to the original image point p _i and its four neighbors, a total of five pixel points, and increases the weight value of the density component to determine the cluster center.

3.6) According to the bivariate discrete function γ=f _γ (ρ, δ) in definition 2, the fitting of the binary inclined plane is carried out, and the fitting plane is obtained as z _γ =b ₁ +b ₂ ρ+b ₃ δ, and the calculation The residual value of each data point ε _γi = y _γi (ρ,δ)-γ _i (ρ,δ), draw the residual histogram ε _γi -h, and also use the bell curve for normal fitting to obtain the variance value σ _γ , using the λσ principle to determine the singular point outside the confidence interval as the cluster center, denoted as c _γ , the algorithm flow chart is shown in Figure 4;

3.7) Take the union of the cluster centers determined by step 3.5) and step 3.6) to obtain the final cluster center of the image c _δργ = c _δ ∪c _ρ ∪c _γ is a set containing n elements, and then according to the nearest neighbor In principle, the remaining pixels are classified, and the algorithm flow chart is shown in Figure 5;

The final clustering center c _δργ is obtained by taking the union of the clustering centers c _δ , c _ρ , and c _γ obtained from the cubic regression analysis, which is very easy to cause over-segmentation, that is, the image will be divided into many small areas in the end. Although the segmentation result obtained in this way has a high similarity within the region, that is, there is a strong internal interaction, but the difference between regions is not high, which is not the clustering result we hoped for. This requires fusion processing in subsequent steps to re-merge different regions with high similarity. In order to facilitate fusion processing, when displaying the result map of cluster segmentation, the pixel value of the cluster center obtained in the case of over-segmentation is used to fill the cluster area, and at the same time, it can have a more friendly visual effect.

3.8) Repeat steps 3.1) to 3.7) for each sub-image to obtain a segmentation result image of each sub-image, and then merge the segmentation result images of each sub-image to obtain an intermediate result image.

4) Secondary re-clustering, the process is as follows:

4.1) Scale the intermediate result graph obtained in step 3.8) to the required scale according to the scaling method in Figure 1, use d _{p_rgb} (p1, p2) as the similarity measure index, and calculate according to the density matrix algorithm and the distance matrix algorithm and Draw the ρ-δ relationship diagram to obtain the discrete function δ _i =f(ρ _i );

Because in the intermediate result map after the first clustering, the detailed information contained in the original image has been completely covered, so the contradiction between information integrity and algorithm complexity is no longer so sharp in the second re-clustering, and there is no need to re-cluster After the area is divided into blocks, just scale the image to the required scale. In the second re-clustering, the similarity measure used is d _{p_rgb} (p1, p2), because after d _p (p1, p2) adds the coordinate value representing the position information, the distant pixel points in the spatial domain The interaction force between becomes weaker, and the purpose of secondary re-clustering is to merge non-adjacent homogeneous regions, so only the color distance d _{p_rgb} (p1,p2) is used;

4.2) Calculate the bivariate discrete function γ=f _γ (ρ, δ) from the relationship of δ _i = f(ρ _i ) obtained in step 4.1), perform the fitting of the binary slope, and calculate the residual value ε of each data point _γi = y _γi (ρ,δ)-γ _i (ρ,δ), draw the residual histogram ε _γi -h, use the bell curve for normal fitting, get the variance value σ _γ , use the λσ principle to determine the The singular point outside the confidence interval is used as the cluster center, denoted as c _γ ;

4.3) Play back the position of the cluster center in step 4.2) in the spatial domain to obtain the cluster center in the original size of the intermediate result map, classify the remaining pixels, and fill the same space with the pixel value of the cluster center. quality area. The secondary re-clustering algorithm is as follows:

4.3.1) Input the intermediate result image I_temp and the search radius d _c including M rows and N columns of pixels;

4.3.2) Scale I_temp according to the scaling rules to obtain I_temp';

4.3.3) First calculate the density matrix of I_temp' according to the density matrix algorithm, calculate the distance matrix of I_temp' according to the distance matrix algorithm, then calculate the γ value according to Definition 2, and perform histogram analysis to automatically determine the singular point as the cluster center, and finally set The position of the cluster center is scaled back to obtain the position of the cluster center under the original scale. At this time, d _{p_rgb} (p1, p2) is used as the similarity measure index for the calculation;

4.3.4) Classify according to the principle of the closest distance, that is, the principle of maximum similarity, classify the rest of the pixels of I_temp into the clusters closest to itself, obtain the result of secondary re-clustering, and output the final result map I_result.

Claims (4)

1. a kind of image segmentation method based on fast density clustering algorithm, it is characterized in that: described method comprises the following steps: 1) Initialization, the process is as follows: 1.1) Firstly, the area division operation is performed. For an image to be processed, it contains pixels of M rows and N columns. After preprocessing, the image is divided into 2 ^W1 × 2 ^W2 sub-images, and the obtained sub-image size for Where Z[f] is the forward rounding function; 1.2) Then perform scale transformation operation on the image, and perform scaling processing on the sub-image after block division, that is, the sub-image with size a*b becomes a ₁ *b ₁ , where a ₁ =a/k _size and b ₁ = b/k _size , k _size >1; in the scaling process, because each pixel contains three pixel values, the method of weak sampling is used for scale transformation, and the number of pixels contained in the image to be processed is reduced While retaining the important clustering information of the original image as much as possible; 2) Calculation of similarity distance based on pixel value and position information, the process is as follows: 2.1) For a natural image I to be processed, which contains M rows and N columns of pixels, let n=M*N, then the pixel data set The feature information that each pixel has in includes the three-color channel component values in the RGB color space, that is, the three pixel values of R, G, and B; , the coordinate value (x, y) in the two-dimensional plane Cartesian coordinate system where the vertical line goes downward to the X axis; 2.2) Let d _p (p1, p2) be the similarity distance between two pixels, the similarity distance calculation formula is as follows: $\begin{array}{cc}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; r</span>}\mathrm{<span\; class="notranslate">\; g</span>}\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; p</span>}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; p</span>}\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\sqrt{{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; r</span>}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; r</span>}\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; 255</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; g</span>}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; g</span>}\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; 255</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; b</span>}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; b</span>}\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; 255</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}& <span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>\\ {\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; x</span>}\mathrm{<span\; class="notranslate">\; the\; y</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; p</span>}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; p</span>}\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\sqrt{{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; x</span>}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; x</span>}\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; the\; y</span>}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}& <span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>\end{array}$ d _p (p1,p2)=θd _{p_rgb} (p1,p2)+(1-θ)d _{p_xy} (p1,p2) (3) In formula (1), r1, g1, b1 and r2, g2, b2 respectively represent pixel values of pixel points p1 and p2 in RGB color space, and d _{p_rgb} represents the distance between pixels in this space; formula (2) Among them, x1, y1 and x2, y2 respectively represent the coordinate values of pixel points p1 and p2 in the Cartesian coordinate system, d _{p_xy} represents the distance between pixels in the coordinate system; in formula (3), θ is the weight factor, Used to adjust the contribution of color distance and position distance to similarity determination; 3) Automatically determine the density clustering of the cluster center, and operate the subgraph, the process is as follows: 3.1) Calculating the similarity distance between image pixels, it is known that there is a duality in the similarity distance between pixels, that is, d _p (p1, p2) = d _p (p2, p1), and d _p (p1, p1) = 0, so the similarity distance is stored as an upper triangular matrix {Dp _ij } whose diagonal data is zero; 3.2) Calculate the density value of each pixel point to obtain the density matrix Calculated as follows: which function In formula (4), ρ _i represents the density value of pixel point p _i , and the pixel set of the image The corresponding index set is I _s ={1,2,...,M*N}, d _ij =d _p (pi,pj) represents the similarity distance between two pixels; 3.3) Calculate the distance value of each pixel point to obtain the distance matrix The distance value of each pixel p _i is defined as δ _i , firstly find the pixel point with density higher than p _i , get the set S'={p _j }, and then find the pixel point p in S' with the closest distance to p _{i j} ', then get δ _i =d _p (pi,pj'); 3.4) Obtained according to step 3.2) and step 3.3) and Draw a decision-making map to obtain a discrete function δ _i = f(ρ _i ) representing the relationship between pixel density and distance; 3.5) Carry out unary linear fitting by the discrete data points on the ρ-δ relationship diagram to obtain the fitting curve y _δ =kx _ρ +b ₀ and Calculate the residual value of each data point ε _δi ＝y _δi -δ _i and ε _ρi ＝x _ρi -ρ _i , draw the residual histogram ε _δi -h and ε _ρi -h , and use the bell curve for normal fitting Combined to get the variance values σ _δ and σ _ρ , use the λσ principle to determine the singular point outside the confidence interval as the cluster center, denoted as c _δ and c _ρ ; 3.6) Obtain the bivariate discrete function γ=f _γ (ρ,δ) from the decision diagram, and perform the fitting of the binary slope, and obtain the fitting plane as z _γ =b ₁ +b ₂ ρ+b ₃ δ, and calculate each The residual value of the data point ε _γi = y _γi (ρ,δ)-γ _i (ρ,δ), draw the residual histogram ε _γi -h, and also use the bell curve for normal fitting to obtain the variance value σ _γ , use the λσ principle to determine the singular point outside the confidence interval as the cluster center, denoted as c _γ ; Among them, the function f _γ is a binary function about the variables ρ and δ, corresponding to the coordinate value in the three-dimensional space is (ρ, δ, f _γ ), then the bivariate discrete function is defined as: ${\mathrm{<span\; class="notranslate">\; \&gamma;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{<span\; class="notranslate">\; |</span>}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&Element;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; \&gamma;</span>}\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&rho;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; \&delta;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; o</span>}\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span><span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; p</span>}\mathrm{<span\; class="notranslate">\; o</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; 5</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; \&rho;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; p</span>}\mathrm{<span\; class="notranslate">\; o</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; \&delta;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>$ In formula (5), take the logarithmic value of the product of the density value and the distance value as the function value; add 1 so that the formula still holds true when the density is zero, that is, no point falls within the d _c radius; Represents the cumulative sum of the density values corresponding to the original image p _i point and its four neighbors, a total of five pixel points, and increases the weight value of the density component to determine the cluster center; 3.7) Take the union of the cluster centers determined by step 3.5) and step 3.6) to obtain the final cluster center of the image c _δργ = c _δ ∪c _ρ ∪c _γ is a set containing n elements, and then according to the nearest neighbor In principle, classify the remaining pixels and fill the homogeneous area with the pixel values of the cluster center points; 3.8) Repeat steps 3.1) to 3.7) for each sub-image, then merge the sub-images to obtain an intermediate result image; 4) Secondary re-clustering, the process is as follows: 4.1) Scale the intermediate result map obtained in step 3.8) to the required scale, use the color distance d _{p_rgb} (p1, p2) as the similarity measure of re-clustering, and calculate and Draw the ρ-δ relationship diagram to obtain the discrete function δ _i =f(ρ _i ); 4.2) Calculate the bivariate discrete function γ=f _γ (ρ, δ) from the relationship of δ _i = f(ρ _i ) obtained in step 4.1), perform the fitting of the binary slope, and calculate the residual value ε _γi of each data point =y _γi (ρ,δ)-γ _i (ρ,δ), draw the residual histogram ε _γi -h, also use the bell curve for normal fitting, get the variance value σ _γ , use the λσ principle to determine the The singular point outside the confidence interval is used as the cluster center, denoted as c _γ ; 4.3) Scale playback the clustering center c _γ obtained in step 4.2) in the spatial domain to obtain the clustering center of the intermediate result image of the original size, classify the remaining pixels according to the nearest neighbor principle, and use the clustering center’s Pixel values fill homogeneous areas. 2. the image segmentation method based on fast density clustering algorithm as claimed in claim 1, is characterized in that: in described step 3.2), d _c is a positive real number, is used to describe taking pixel point _p as the center of circle, d _c is the circumference of the radius, and the density value ρ _i is the number of pixels falling inside the circumference; the pixel p _max at the maximum sum of the pixel values of each channel in the color space and the pixel value at the minimum sum of the pixel values of each channel 2% of the similarity distance between pixel points p _min is taken as the d _c value, and the calculation formula is as follows: ${\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0.02</span>}<span\; class="notranslate">\; *</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; (</span>{\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; a</span>}\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; ,</span>{\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; )</span>$ In formula (6), Indicates that if there are multiple pixels in an image, the cumulative sum of pixel values in the color space is equal to the maximum or minimum, then take the average, that is 3. the image segmentation method based on fast density clustering algorithm as claimed in claim 1 or 2, is characterized in that: in described step 3.7), the clustering center c _δργ that finally obtains is the cluster that obtains by cubic regression analysis Centers c _δ , c _ρ , and c _γ are obtained by taking the union. When displaying the result map of cluster segmentation, use the pixel value of the cluster center obtained in the case of over-segmentation to fill the cluster area. 4. the image segmentation method based on fast density clustering algorithm as claimed in claim 1 or 2, is characterized in that: in described step 4.2), the judgment basis that the cluster center of secondary re-clustering determines automatically no longer uses The union of c _δ , c _ρ , and c _γ only performs histogram analysis on the γ value.