CN102103744A - Image segmentation method based on minimum spanning trees and statistical learning theory - Google Patents

Abstract

The present invention proposes an image segmentation method based on the minimum spanning tree and statistical learning theory. On the basis of constructing the image graph model, a bottom-up (merging) strategy is adopted, and the minimum spanning tree algorithm is designed based on statistical learning according to the present invention. Theoretical merging criteria to construct procedures for generating multiple minimum spanning trees. While satisfying the global optimum, the segmentation method can effectively utilize the regional statistical characteristics, and is suitable for various high-resolution image segmentation; it has good anti-noise performance, and can also obtain better segmentation results for textured areas. Get good region boundaries.

Description

Image Segmentation Method Based on Minimum Spanning Tree and Statistical Learning Theory

technical field

The method belongs to the technical field of image processing and pattern recognition, and in particular relates to a new object-oriented image segmentation method based on minimum spanning tree optimization theory and statistical learning theory.

Background technique

High-spatial-resolution remote sensing images provide us with high-precision spatial geometric information, rich texture information, and multi-spectral information of the ground landscape, making traditional pixel-based remote sensing image classification methods inapplicable, thus making high-resolution remote sensing image processing more difficult. Challenged with the detail provided by imagery. For this reason, Baatz and Schape pointed out in [1] in 1999 that important semantic interpretation needs to be represented by meaningful objects and the relationship between objects in images rather than by pixels. The target recognition and classification method of high-resolution remote sensing images of objects, that is, firstly segment the images to generate object regions, and use a layered network to describe the objects, and then perform target recognition with objects as units. Blaschke and Strobl in [1] raised the question of "what's wrong with the pixels?", pointing out that the traditional pixel-based multidimensional feature space classification does not make use of spatial information, especially for high-resolution where adjacent pixels may belong to the same land cover type For imagery, segmentation-based classification outperforms traditional per-pixel approaches in many cases. New classifiers based on the object's spectrum, shape, texture, spatial relationship, and further reasoning on human knowledge proved to be very useful in the high-spatial-resolution domain, which conforms to the laws of human recognition of objects, improving classification accuracy and detail. The rapid development of the object-based research field has led to the emergence of an object-based image analysis (Object-Based Image Analysis, OBIA) sub-discipline in the field of geographic information science, which specializes in the automatic segmentation of remote sensing images into meaningful objects. , spectral and temporal scales to evaluate their characteristics to generate new geographic information in GIS data format [2]. Object-oriented image segmentation is one of the main methods to obtain objects. Object-oriented target recognition technology is to identify targets by combining information such as spectrum, geometry, texture, and spatial neighborhood relations of objects. It is found from theory and practical applications that The quality of object segmentation directly affects the effect and accuracy of image classification and recognition, because it is directly related to whether the geometric information and structural information of objects in the image can be accurately and effectively extracted. Therefore, object-oriented high-resolution remote sensing image segmentation has become a remote sensing The key and foundation of image processing, the research of object-oriented segmentation method has also become one of the hotspots and difficulties of high spatial resolution.

Image segmentation is already a classic topic in image processing and computer vision, from the early segmentation of single target and background to multi-target segmentation; from pixel-level segmentation to object-level segmentation, from uncertain target segmentation to definite target segmentation, researchers based on A large number of segmentation algorithms are required. The basic strategy of image segmentation is based on two basic properties of pixel gray values: discontinuity and similarity. Pixels inside regions generally have some similarity, while there generally are some discontinuities at the boundaries between regions. Therefore, segmentation algorithms can be divided into boundary-based algorithms that utilize discontinuity between regions and region-based algorithms that utilize intra-region similarity.

With the development of image segmentation technology, people's research on image segmentation has changed from the initial simple threshold segmentation, edge detection and region extraction to the introduction of new concepts and new methods into the field of image segmentation, and attaches great importance to the effectiveness of multiple segmentation algorithms. combined. Through the comprehensive use of two or more methods, it is possible to partially overcome the problem that a single image segmentation algorithm is difficult to achieve satisfactory segmentation results for general images, and what kind of combination method can reflect the advantages of various methods and make up for it. Their respective deficiencies and achieving good expected results are still one of the main issues that people pay attention to. After the 1980s, more and more scholars began to apply fuzzy theory, Markov model, genetic algorithm theory, fractal theory and wavelet theory to the research of image segmentation, and made great progress. However, due to the complexity and diversity of image types, although people have conducted extensive and in-depth research, there is no general image segmentation theory proposed at present, and the existing algorithms have their own limitations. Therefore, exploring new segmentation theories and segmentation algorithms is of great significance for image processing and analysis

http://www.tu-dresden.de/ioer/statisch/segmentation-evaluation/index.html is a website dedicated to the evaluation of remote sensing image segmentation software. The website briefly introduces various object-oriented high-resolution remote sensing Image segmentation software methods and performance, showing the segmentation results of each software on high-resolution urban and suburban images. At present, the main software displayed are as follows: BerkeleyImgSeg, Definens Developer, CAEASR, Data Dissection Tool, Edge Detection and Image SegmentationON (EDISON) System, ENVI Feature Extraction, Extended Watershed EWS (Multi-channel watershed transformation), InfoPack, MinimumEntropy Approach, Image Segmentation for Erdas Imagine, Imagine WS for Erdas Imagine, PABAT 0.32, RHSEG, SCRM, SegSAR, HaIcon Seg, the segmentation method used by each software is introduced as follows:

Definens Developer and BerkeleyImgSeg are two object-oriented segmentation and classification software currently launched in the field of remote sensing. The ideas of these two segmentation software are the same, and their segmentation ideas are derived from literature [3]. Considering the weight of multi-band spectral characteristics and regional shape characteristics, it realizes multi-scale and multi-level image segmentation. The upper layer object is the combination of its lower layer objects, and the image is described layer by layer. The segmentation results of each layer have their own statistics. Spectrum, texture, shape, topological features of objects, and attribute information of the relationship between upper and lower objects. The statistical results can be used for further image classification and analysis.

CAEASR and InfoPack are based on the literature [4], assuming that there are r regions in the image that obey the Gamma distribution, by defining a cost function, and using the Simulated Annealing (SA) method to complete image segmentation. The simulated annealing method is a general probability algorithm invented by S.Kirkpatrick, C.D.Gelatt and M.P.Vecchi in 1983. It is a general optimization algorithm used to find the optimal solution of a proposition in a large search space. Widely used in optimal control, machine learning, neural network and other optimization problems, the algorithm starts with an arbitrary point in the search space, selects a "neighbor" at each step, and then calculates the distance from the current position to the "neighbor". probability.

Data Dissection Tool uses the Super Paramagnetic Clustering algorithm (Super Paramagnetic Clustering, SPC) proposed in [5] to realize image segmentation and analysis. The superparamagnetic clustering method is a brand-new idea, which introduces the idea of physics into the information field, and regards the thermodynamic aggregation motion of the non-uniform Potts model as data clustering, that is, within a certain temperature range, the data In the superparamagnetic phase, the correlation between data points is then used to cluster. The algorithm is not strongly dependent on various parameters, and is mainly used for clustering, image analysis, and statistical physics.

Edge Detection and Image SegmentationON (EDISON) System is based on the Mean shift algorithm proposed in the literature [6] to complete the segmentation of color images. The concept of Mean Shift was first proposed by Fukunaga et al. in [7] about the probability density gradient function Estimation is a non-parametric feature space analysis technique. The algorithm is an iterative process, that is, first calculate the offset mean of the current point, move the point to its offset mean, and then use this as a new starting point to continue moving , until certain conditions are met. The Mean Shift algorithm is essentially an adaptive gradient ascending search peak method. Mean Shift is mainly used in three aspects of clustering, mode detection and optimization, and has been widely used in computer vision and image processing clustering.

ENVI Feature Extraction introduces the λ parameter to control the segmentation scale based on the literature [8] and the Mumford-Shah model, and realizes rapid multi-scale segmentation of images by means of region growth [9].

EWS is based on the multi-channel extended watershed transform segmentation method proposed in [10]. Minimum Entropy Approach uses Triangulation, Image segmentation for Erdas Imagine, Imagine WS for Erdas Imagine, and PABAT32 all use region growth methods. PABAT32 considers the uncertainty of remote sensing images in segmentation according to literature [11]; RHSEG uses hierarchical regions Growth (Hierarchical region growing, [12]); SCRM uses a combination of watershed and region growing (Watershed and region growing, [13]), SegSAR, HaIcon Seg combines edge and region segmentation (Hybrid edge/region oriented).

Summarizing these methods, it can be found that object-oriented image segmentation algorithms mainly focus on region growth and watershed, while introducing simulated annealing, Mean Shift, superparamagnetic clustering algorithm, Mumford-Shah, and multi-scale segmentation that integrates region and edge characteristics. This shows that segmentation algorithms such as region growth, splitting and merging, hierarchical clustering, and watershed combined with other criteria are the main methods currently used to achieve object-oriented multi-scale segmentation of high-resolution remote sensing images. Most of the literature focuses on the new Theory is added to the setting and optimization of segmentation criteria to achieve multi-scale image segmentation.

In the segmentation algorithm based on region growth, the selection of seed points and the setting of merging criteria are the key steps that affect the segmentation effect. The seed point should be selected in the center of the homogeneous area as the best, and the selection and acquisition of the homogeneous center as the seed point It is very difficult, and how to make full use of the multi-spectral, shape, texture and other characteristics of the image is also the method that needs to be considered in the segmentation criteria. The watershed segmentation algorithm is also a widely used object-oriented image segmentation algorithm, but its disadvantage is that it is prone to over-segmentation. Therefore, many scholars have studied and proposed methods to solve this problem, such as preprocessing the gradient image to reduce noise, merging over-segmented regions, and thresholding the gradient of the input image.

Background technology cited documents:

1. Blaschke, T. and J. Strobl, What's wrong with pixels? Some recent developments interfacing remote sensing and GIS. GIS-Zeitschrift für Geoinformationssysteme, 2001.14(6): p.12-17.

2. Blaschke, T., S. Lang, and G.J. Hay, eds. Object-Based Image Analysis: Spatial Concepts for Knowledge-Driven Remote Sensing Applications. Lecture Notes in Geoinformation and Cartography, ed. W. Cartwright, G. Gartner, L .Meng, et al.2008, Springer-Verlag Berlin Heidelberg.

Multiresolution Segmentation：an optimization approach for high quality multi-scaleimage segmentation in Strobl，J.，Blaschke，T.，Griesebner，G.(eds)，Angewandte GeographischeInformationsverarbeitung XII.2000.Wichmann，Heidelberg.3. Baatz, M. and A.

Multiresolution Segmentation: an optimization approach for high quality multi-scale image segmentation in Strobl, J., Blaschke, T., Griesebner, G. (eds), Angewandte Geographische Informationsverarbeitung XII.2000.Wichmann, Heidelberg.

4. Cook, R., I. McConnell, D. Stewart, and C. J. Oliver. Segmentation and simulated annealing. in Microwave Sensing and Synthetic Aperture Radar 1996. Taormina, Italy SPIE.

Cluster update algorithm and recognition.Physical Review E，2000.62(2)：p.Rl461-R1464.5. Ferber, Cvand F.

Cluster update algorithm and recognition. Physical Review E, 2000.62(2): p.Rl461-R1464.

6. Comaniciu, D. and P. Meer, Mean shift: a robust approach toward feature space analysis. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2002.24(5): p.603-619.

7. Fukunaga, K. and L.D. Hostetler, The estimation of the gradient of a density function, with applications in pattern recognition. Information Theory, IEEE Transactions on, 1975.21(1): p.32-40.

8. Koepfler, G., C.Lopez, and J.M.Morel, A multiscale algorithm for image segmentation by variational method. SIAM Journal on Numerical Analysis 1994.31(1): p.282-299.

9.Robinson, D.J., N.J.Redding, and D.J.Crisp.Implementation of a fast algorithm for segmenting SAR imagery.[Technical Report(Defence Science and Technology Organization(Australia))]2002-01.

10. Li, P. and X. Xiao, Multispectral image segmentation by a multichannel watershed-based approach. International Journal of Remote Sensing, 2007.28(19): p.4429-4452.

11. Lucieer, A., Uncertainties in Segmentation and their Visualization. October 2004, Utrecht University and International Institute for Geo-Information Science and Earth Observation (ITC).

12. Tilton, J.C.Analysis of hierarchically related image segmentations.in Proc IEEE Workshop on Advances in Techniques for Analysis of Remotely Sensed Data.2003.

13.Castilla, G., G.J.Hay, and J.R.Ruiz-Gallardo, Size-constrained region merging (SCRM): an automated delineation tool for assisted photo interpretation. Photogrammetric Engineering and Remote Sensing, 2008.74(4): p.409-419.

Contents of the invention

In view of the above-mentioned difficulties and problems, the present invention adopts a kind of image segmentation based on minimum spanning tree theory and proposes a segmentation criterion based on statistical learning theory design, realizes object-oriented image segmentation, avoids the problem of seed point selection in region growth, and It effectively solves the over-segmentation problem.

The image segmentation method based on minimum spanning tree and statistical learning theory provided by the present invention comprises the following steps:

Step 1. The image is represented by a simple graph model. Each vertex of the simple graph model corresponds to a pixel of the image. Every two adjacent vertices are connected by an edge. The edge weight of each edge is the two pixels connected by the edge. The difference between the two pixels corresponding to the vertex;

Step 2. Set the region merging criterion based on the statistical learning theory, and set the segmentation parameters;

Step 3: Carry out image segmentation based on the minimum spanning tree for the simple graph model obtained in step 1. When segmenting, start from the edge with the smallest weight in the simple graph model and merge it according to the region merging criterion until the edge with the largest weight. A spanning tree represents a connected region.

Moreover, the calculation method of the edge weight in step 1 is that the difference between the two pixels corresponding to the two vertices is calculated by using the band weighted squared distance sum.

Moreover, the specific implementation method of setting the region merging criterion based on the statistical learning theory in step 2 is to use the image segmentation process as a learning process, and the learning process is to regard the image segmentation as a regression estimation problem; according to the statistical learning theory The β-uniformly stable learning algorithm based on empirical risk minimization sets the regional merging criterion, and transforms the empirical risk minimization problem into a probability problem. The loss function in statistical learning corresponds to the edge weight calculation method in step 1.

Moreover, the segmentation parameter in step 2 includes a segmentation scale parameter, and the size of the region obtained by image segmentation in step 3 is affected by setting the value of the segmentation scale parameter. The segmentation scale parameter is set according to the maximum edge weight allowed by the area.

Moreover, the segmentation parameters in step 2 include the minimum area parameter, and by setting the value of the minimum area parameter, it is prevented from generating an too small area during image segmentation in step 3.

Moreover, the image segmentation based on the minimum spanning tree described in step 3 is realized by using the Kruskal minimum spanning tree algorithm.

In the present invention, the image is represented by a graph model, and the problem of finding homogeneous regions in image segmentation is transformed into a minimum spanning tree problem, and the image segmentation process is regarded as a learning process; the Kruskal minimum spanning tree algorithm is adopted, combined with its algorithm characteristics, The edge weight function corresponds to the loss function, and the statistical learning theory is integrated into the minimum spanning tree image segmentation. While satisfying the global optimum, the segmentation method can effectively utilize the regional statistical characteristics, and is suitable for various high-resolution image segmentation; it has good anti-noise performance, and can also obtain better segmentation results for textured areas. Get good region boundaries.

Description of drawings

Figure 1 is a schematic diagram of a simple graph model based on top-down minimum spanning tree segmentation results, where Figure 1a is the gray value of a 5*5 image, Figure 1b is the representation of the graphical model corresponding to Figure 1a, and Figure 1c is The minimum spanning tree in Figure 1b, and Figure 1d is the segmentation result of Figure 1c.

Fig. 2 is a schematic diagram of the threshold affecting the segmentation result, wherein Fig. 2a is the segmentation result obtained when the threshold value is larger, and Fig. 2b is the segmentation result obtained when the threshold value is smaller.

FIG. 3 is a schematic diagram of threshold variation rules according to an embodiment of the present invention.

Detailed ways

The technical solution of the present invention will be described in detail in conjunction with the accompanying drawings and the embodiments of the present invention. The implementation process of the embodiment is as follows:

Step 1. The image is represented by a simple graph model. Each vertex of the simple graph model corresponds to a pixel of the image. Every two adjacent vertices are connected by an edge. The edge weight of each edge is the two pixels connected by the edge. The difference between the two pixels corresponding to the vertex.

The simple graph model is one of the existing pyramid models. The edge weight in the simple graph model is the weight of each edge, and the embodiment adopts the band weighted square distance sum to calculate the weight. The specific calculation method is the prior art, and will not be described in detail in the present invention.

Step 2: Set the region merging criterion based on the statistical learning theory, and set the segmentation parameters.

The embodiment sets the region merging criterion based on the statistical learning theory. The specific implementation method is to use the image segmentation process as a learning process, and the learning process is to regard the image segmentation as a regression estimation problem; according to the empirical risk minimization in the statistical learning theory The β-consistently stable learning algorithm sets the regional merging criterion, and transforms the empirical risk minimization problem into a probability problem. The loss function in statistical learning corresponds to the edge weight calculation method in step 1.

According to Bousquet and Elisseeff's b-consistent stability algorithm for changing an element and the generalization error bound derived from McDiarmid's inequality, according to the idea of statistical learning theory, after derivation, the following criteria are designed:

Among them, S ₁ and S ₂ represent the current two regions, n ₁ and n ₂ represent the number of pixels (number of vertices) in regions S ₁ and S ₂ , n represents the current edge, and w _n is merged according to the edge weight from small to large The current edge in the process, which connects the two regions denoted by S ₁ and S ₂ , && means simultaneous satisfaction. If P(S ₁ , S ₂ ) is TRUE then merge regions S ₁ and S ₂ , if P(S ₁ , S ₂ ) is FALSE then do not merge.

计算)。沿纵轴方向，是M由小到大取不同值30、40、50、80、100、120时的变化曲线；沿横轴方向，是面积增大时的阈值变化趋势。n_i是区域i的像素数，其值随合并过程动态变化；概率δ是在0和1之间的一个小值，它的变化对阈值影响不大，具有微调作用，根据概率理论和前面的分析，我们通常设其值为0.1；M是损失上界，它对应于边权的上确界，我们可以根据最大边权值(区域内最大差异)来选择它的值。The criterion is controlled by three parameters (n _i , δ, M) to control the threshold, and it is precisely the parameter that controls the segmentation scale. As shown in Figure 3, take δ=0.1 (marked as delta=0.1 in the figure), the abscissa is _ni (region size), and the ordinate is th (this threshold passes

calculate). Along the vertical axis, it is the change curve when M takes different values of 30, 40, 50, 80, 100, and 120 from small to large; along the horizontal axis, it is the threshold value change trend when the area increases. n _i is the number of pixels in area i, and its value changes dynamically with the merging process; the probability δ is a small value between 0 and 1, and its change has little effect on the threshold, which has a fine-tuning effect. According to the probability theory and the previous Analysis, we usually set its value to 0.1; M is the upper bound of the loss, which corresponds to the supremum of the edge weight, and we can choose its value according to the maximum edge weight (the largest difference in the region).

In this embodiment, δ is fixed at 0.1, and _ni changes automatically with the merging process. Therefore, only M is used as a parameter to control the segmentation scale. By setting different segmentation scale parameters, the segmentation results of images at different scales can be obtained . The threshold value obtained by the large M value is large, and the generalization error allowed is large, that is, the internal variation of the region is allowed to be large, so as to obtain a large-scale segmentation result.

During specific implementation, other region merging criteria based on statistical learning theory may also be used, such as a design criterion based on statistical learning theory based on the characteristics of all pixels in a region.

In the setting of segmentation parameters, in order to avoid generating too small areas during segmentation, the present invention proposes that the segmentation parameters include a parameter for controlling the size of the minimum area. When the area of a certain area is smaller than the minimum area size parameter during segmentation, the processing that can be performed is: start again in the order of edge weights from small to large, if the two areas connected by the current edge do not belong to the same area, and the If one of the two regions connected by an edge is smaller than the specified minimum region area, the two regions are merged. By re-starting from the minimum weight edge in the simple graph model and growing according to the region merging criterion until the maximum weight edge, this ensures the maximum similarity between the merged regions.

Step 3: Carry out image segmentation based on the minimum spanning tree for the simple graph model obtained in step 1. When segmenting, start from the edge with the smallest weight in the simple graph model and merge it according to the region merging criterion until the edge with the largest weight. A spanning tree represents a connected region.

The minimum spanning tree problem is described as finding the minimum spanning tree with edge weights. For image segmentation, the problem of finding the connected region with the smallest difference can be transformed into the minimum spanning tree problem. Therefore, after step 1 realizes that the relationship between the pixels represented by the image is represented by a simple graph model, the image segmentation of the simple graph model obtained in step 1 can be performed based on the minimum spanning tree, see Figure 1, where Figure 1a is a 5*5 The gray value of the image, Figure 1b is the graphical model representation corresponding to Figure 1a, Figure 1c is the minimum spanning tree of Figure 1b, and Figure 1d is the segmentation result of Figure 1c. The segmentation scale parameter set in step 2 affects the segmentation result, see Figure 2, Figure 2a shows the segmentation result obtained when the threshold value is larger, and Figure 2b shows the segmentation result obtained when the threshold value is smaller. The image segmentation based on the minimum spanning tree mainly has two strategies of splitting the minimum spanning tree from the top and merging from the bottom to generate multiple minimum spanning trees. The embodiment adopts the Kruska1 minimum spanning tree algorithm and bottom-up merging strategy to realize the image segmentation based on the minimum spanning tree. The specific algorithm and strategy are prior art, and will not be described in detail in the present invention.

Claims (7)

1. based on the image segmentation method of minimum spanning tree and statistical learning theory, it is characterized in that: comprise the following steps, Step 1. The image is represented by a simple graph model. Each vertex of the simple graph model corresponds to a pixel of the image. Every two adjacent vertices are connected by an edge. The edge weight of each edge is the two pixels connected by the edge. The difference between the two pixels corresponding to the vertex; Step 2. Set the region merging criterion based on the statistical learning theory, and set the segmentation parameters; Step 3: Carry out image segmentation based on the minimum spanning tree for the simple graph model obtained in step 1. When segmenting, start from the edge with the smallest weight in the simple graph model and merge it according to the region merging criterion until the edge with the largest weight. A spanning tree represents a connected region. 2. The image segmentation method according to claim 1, characterized in that: in the step 1, the edge weight is calculated in such a way that the difference between the two pixels corresponding to the two vertices is calculated by using the band weighted squared distance sum. 3. The image segmentation method according to claim 2, characterized in that: in the step 2, based on the statistical learning theory, the specific implementation of the regional merging criterion is set as, the image segmentation process is used as a learning process, and the learning process is to use the image Segmentation is regarded as a regression estimation problem; according to the uniform and stable learning algorithm based on empirical risk minimization in statistical learning theory, the regional merging criterion is set, and the empirical risk minimization problem is transformed into a probability problem. The loss function in statistical learning is the same as The calculation method of the edge weight in step 1 is corresponding. 4. The image segmentation method according to claim 1, characterized in that: the segmentation parameter in step 2 includes a segmentation scale parameter, and the size of the region obtained by image segmentation in step 3 is affected by setting the value of the segmentation scale parameter. 5. The image segmentation method according to claim 4, characterized in that: the segmentation scale parameter is set according to the maximum edge weight allowed by the area. 6. The image segmentation method according to claim 1, characterized in that: the segmentation parameter in step 2 includes a minimum area parameter, by setting the value of the minimum area parameter to prevent generation of too small area during image segmentation in step 3. 7. The image segmentation method according to claim 1, characterized in that: the image segmentation based on the minimum spanning tree described in step 3 is realized by using the Kruskal minimum spanning tree algorithm.

Images