CN104537635A - Simplification algorithm for land cover vector data for maintaining topology - Google Patents

Abstract

The invention provides a simplification algorithm for land cover vector data for maintaining topology. During land cover/utilization application, in the processes of forming land blocks by adopting a remote sensing image segmentation method and judging the attributes of the land blocks, vector polygons are strictly in accordance with the trends of pixels of segmented images; most vector polygons are in right-angular shapes or sawtooth shapes; the data volume is large; simplification is needed; and the topology relationship between every two vector polygons is strictly maintained. According to the algorithm, firstly, contiguous polygons of the vector polygons are traversed, and feature points of the contiguous polygons are recorded; the vector polygons are decomposed into arc segments formed by contiguous feature points; then, an arc segment simplification algorithm is called for simplifying the arc segments; and finally, the corresponding simplified arc segments are recombined into the vector polygons, and the vector polygon simplification process is completed. The simplification algorithm has the advantages that the requirements of vector polygon simplification in the land cover/utilization process can be efficiently met, and meanwhile, the simplification algorithm can be widely applied to other application and requirements of row vector polygon simplification for maintaining the topology relationship.

Description

A SIMPLIFICATION ALGORITHM FOR LAND COVER VECTOR DATA PRESERVING TOPOLOGY

technical field

The present invention relates to the simplified algorithm of vector block data in land cover/utilization in the field of remote sensing and geographic information system. Specifically, in the application of geographic information system and remote sensing land, it is necessary to realize the land topological structure under the premise of maintaining the land topology. The simplification algorithm of block boundary segmentation results, the present invention can be applied to simplification of large or complex vector plot boundary data, so as to realize the simplification of data volume under the premise of maintaining the topological relationship of plots.

Background technique

When conducting land cover and land use surveys, it needs to be realized based on the interpretation process of remote sensing images. Remote sensing images with high spatial resolution (hereinafter referred to as high resolution) can more clearly and accurately distinguish the boundaries of different land parcels on the surface. Therefore, it is more and more widely used in land cover/use applications. Due to the large amount of high-resolution image data, it is generally necessary to segment remote sensing images to form plots, and then determine the types of plots for all plots that constitute the area (can assist multi-period long-term image Spectrum of ground objects and prior knowledge formed), realize the type judgment of each land parcel and process it into the final land cover/use thematic data. In this process, because the result of the block segmentation corresponding to the high-resolution image is particularly complicated, a large number of vector boundaries corresponding to the image pixels are retained, which need to be simplified, otherwise the data will seriously affect the subsequent data processing and processing. analyze. The vector data simplification algorithm here needs to keep its original topological structure, because in the land cover/utilization, it is necessary to ensure that each land unit has a certain cover/utilization attribute, and there must be no overlap between land units, so the conventional vector Feature reduction algorithms cannot meet this demand. Relevant references include: Liu Yashu, Yan Hanbing, Fan Yougui. Polygon Simplification Algorithms and Comparison. Computer Engineering. 2009 35(23): 227-229; Zhou Shilin; Tang Xiaoan; Chen Min; Hao Jianxin; Sun Maoyin. Based on polygon vertex normal vector Mesh model simplification algorithm. Chinese Journal of Image and Graphics. 2002 7(6): 601-605; Yu Mingyue, Wang Wei'an. Polygon shape simplification and its quality evaluation. Surveying and Spatial Geographic Information. 2011 34(6): 152- 156; Yanwu Li, Xuekang Chen, Lanxi Wang, Lei Guo, Yajuan Li. Molecular flow transmission probabilities of any regular polygon tubes. 2013 92: 81-84; Robert H. Ericksen. A polygon chaining algorithm to a simplify. Comparing Environment and Urban Systems.1984 9(4):237-245; Tomoki Nakamigawa.A generalization of diagonal flips in a convex polygon.Theoretical Computer Science.2000 235(2):271-282;

In terms of simplification of vector polygons, there are not many patents that can be found at present, such as: Beijing NavInfo Technology Co., Ltd.'s patent "Method and device for automatic simplification of shape points of polygonal surface elements in electronic maps" (application number: CN201010223958, publication number: CN102314798B); Ningbo University applied for a patent "a method for simplifying polygonal models of images" (application number: CN201110279661, publication number: CN102346913A). However, none of these patents provides a more detailed solution for the simplification strategy of vector polygon data, and there are few related discussions.

Contents of the invention

It is an object of the present invention to provide a simplified algorithm for topologically preserving land cover vector data. In the process of land cover/use, a series of plot units formed based on high-resolution remote sensing image segmentation have very complex boundary characteristics, and these boundaries are often obtained by tracing the direction of remote sensing image pixels, especially With the improvement of the spatial resolution of remote sensing images, this phenomenon is more obvious, resulting in a huge amount of vector polygon data obtained by segmentation and bringing great difficulties to subsequent processing. The present invention is mainly aimed at this problem. solve.

The idea of the present invention is: in applications such as land cover/use investigation based on high-resolution remote sensing images, it is necessary to firstly use a certain image segmentation method to segment remote sensing images, and the method can choose watershed segmentation, multi-resolution segmentation, mean Drift segmentation, etc., to form a series of plot vector units (objects) corresponding to the image. These vector polygons are disjoint and their union equals the total area of the imagery. Since these vector polygons are mainly based on the feature attributes (such as spectral features, texture features, shape features, etc.) It is formed by tracking pixels, so its characteristic is that each side of the vector polygon is along the boundary of the pixel, resulting in a particularly complex vector polygon. If it is not simplified, it will seriously affect the subsequent vector data processing and calculation. The principle of simplification is not to have too much influence on the plots formed after the division, and to maintain the basic topological structure of each plot, that is, there cannot be any intersection between the plots, and no gaps between the plots can be formed. Gaps, therefore, preserve the topology of the segmented plots is a prerequisite for vector simplification.

In order to maintain the topological adjacency relationship between different plots, the idea of the present invention is to first find all adjacent polygons of any polygon, then confirm all the feature points of the polygon through these adjacent polygons, and decompose the polygon into a number of feature points. Line segment, and then use a certain algorithm to simplify the line segment. The feature point here is the key point to ensure the topological structure between polygons, and is the intersection point with the boundary of the area data and the intersection point of any three adjacent polygons. For the simplification algorithm of line segments, vertex deletion method, edge contraction algorithm, etc. can be applied. For specific implementation, Douglas Peuker algorithm, cohen-sutherland algorithm, Voronoi simplification algorithm, polygon vertex deletion method, etc. can be applied.

Technical scheme of the present invention provides a kind of simplified algorithm of the land cover vector data that keeps topology, it is characterized in that comprising following implementation steps:

1), open the vector data to be simplified, construct the data structure, and establish the topological structure of all polygons that make up the land cover, and record the adjacent polygons of each polygon;

2), on the basis of recording the adjacent polygons of each polygon in step 1, the feature points of each polygon are calculated by the adjacency relationship of the adjacent polygons of each polygon, and the corresponding relationship between polygons and feature points is established;

3), for the original point set order of each polygon, the feature points calculated in step 2 are rearranged and sorted to form a feature point set consistent with the original order;

4), using the sequential feature points formed in step 3 to split the polygon into several line segments, and record the corresponding relationship between the polygon and the line segments, and each line segment retains the original point set of the polygon;

5), using a certain line segment simplification algorithm to simplify all line segments in step 4;

6) According to the relationship between the polygon and the line segment recorded in step 4, the resulting line segment after the simplification in step 5 is reorganized in the original order to form a simplified polygon.

The above-mentioned implementation steps are characterized in that:

In step 1), it is necessary to first construct a data structure for storing and recording all adjacent polygons of the land cover/utilization polygon, which can be implemented by borrowing the function SetSpatialFilterRect() of OGR.

Step 2) is to traverse the adjacent polygons of the polygon on the basis of step 1, calculate the common side between the adjacent polygons of each polygon, and then obtain the feature points of the polygon according to the adjacent relationship of the polygons.

Step 3) is traversing all the polygons, sorting the polygon feature points in step 2 according to the order of corresponding points, so as to determine a plurality of feature points constituting the polygon.

Step 4) is to decompose the corresponding vector polygon into several directed line segments based on the feature points in step 3, and these directed line segments are the basic units constituting the vector polygon.

Step 5) is to use the vector line segment simplification algorithm in this paper to simplify the line segment formed in step 4. Here, a data structure needs to be constructed to record the line segment before simplification and the result after simplification. For the subsequent line segment that needs to be simplified, need First, traverse through this data structure to see if the vector line segment has been simplified. If it has been simplified, it can be directly taken out from the data structure.

Step 6) is to reassemble the line segment simplification result of step 5 according to the sequence of line segments recorded in step 4 to form the corresponding vector polygon simplification result.

Compared with the prior art, the present invention has the following characteristics: the present invention achieves the purpose of vector polygon simplification by querying the feature points of the area vector polygon, and then simplifying the line segments constructed by these feature points respectively, so that the vector polygon can be kept well The polygonal topological structure is well adapted to the requirements of strictly manipulating the topological structure of area vector polygons in applications such as land cover/utilization. At the same time, applying a more mature line segment simplification algorithm and constructing a better data structure can also improve and increase the efficiency compared with the existing technology.

Description of drawings

Figure 1 is a schematic flow chart of the topology-preserving vector polygon simplification method

Figure 2 is a schematic diagram of land cover vector polygons formed after high-resolution image segmentation

Figure 3 is a simplified rendering of the vector polygon in Figure 2 based on ArcGIS

Figure 4 is a schematic diagram of the effect on the feature points of the vector polygon

Figure 5 is the result of simplification based on the premise of retaining the feature points in Figure 4

Figure 6 is a schematic diagram of the line segment simplification algorithm based on the principle of the Douglas peucker algorithm

Figure 7 is a schematic diagram of land cover/use to be simplified

Figure 8 is a schematic diagram of the effect of simplifying the vector polygon in Figure 6 with a parameter of 500

Figure 9 is a schematic diagram of the effect of simplifying the vector polygon in Figure 6 with a parameter of 5000

Figure 10 is a schematic diagram of the effect of simplifying the vector polygon in Figure 6 with a parameter of 50000

Detailed ways

Fig. 1 illustrates the main realization idea of the present invention. In the simplification process of the vector polygons of land cover/utilization, it is the most important to keep the topological structure of each vector polygon, and it is also the most lacking in the prior art scheme. The solution idea of the present invention is to first find these vector polygons The feature points ensure the stability of these feature points in the process of vector simplification, thus ensuring the topology among vector polygons. In the process of finding the feature point of the vector polygon, the definition of the feature point of the present invention is as follows: the point intersecting the boundary in the vector polygon, and the intersection point of any three vector polygons. In order to find the feature points of the vector polygon, the flow process of the present invention is as follows: first traverse the adjacent polygons of each polygon, calculate and record the feature points of each polygon, and adjust the corresponding feature points according to the point order of the vector polygon, and based on these features Decompose the vector polygon into multiple line segments, then use the line segment simplification algorithm of the present invention to simplify the corresponding line segments, and then reassemble the corresponding line segments to form simplified vector polygons to complete the simplification process.

The specific implementation process is as follows: first, overload OGRPoint, and add its functions for judging equality and inequality, similar to the following:

At the same time, define the data structure of the simplified line segment, so that the data structure can record the point string before simplification and the point string after simplification, similar to the following:

Finally, a function for judging whether the two point strings are the same needs to be given. Here, it is necessary to return the comparison of the number of points of the two point strings, the judgment of positive equality and inverse equality, similar to the following process:

After the above data structures and basic functions are defined, vector polygons can be simplified according to the implementation process of the present invention. Fig. 2 shows a segmentation result based on high-resolution remote sensing images, and Fig. 3 is the simplified result of the vector polygon realized by using ArcGIS in Fig. 2. It can be seen from Fig. 3 that there are some "gaps" in each vector polygon after simplification, that is, the topological structure between each vector polygon is destroyed, which makes the attribute duplication or missing in some places in the land cover/utilization, which is is incorrect, so the topological relationship of vector polygons must be strictly preserved.

Fig. 4 illustrates a schematic diagram of a feature point search method for a vector polygon to be simplified. Among them, the green points such as A, B, C, D, E, F, G are the points intersecting with the boundary, which are recorded as I-type feature points; points a, b, c, d,...etc. is the intersection point of any adjacent three vector polygons, and is recorded as a type II feature point. Therefore, the traversal strategy of these feature points is as follows:

First, it is necessary to traverse and find the adjacent polygons of all polygons to find the above points a, b, c..., the method is as follows (pseudo code):

After this step, the adjacent polygons of any vector polygon can be traversed and stored in the pFeatureIPFID data structure.

Secondly, traverse the polygon and get type II feature points, the method is similar to the following:

After this step, all the feature points of the constructed vector polygon can be traversed, as shown in Figure 4, the vector polygon ① consists of three I-type feature points (points A, B, E) and one II-type feature point (point a ), the vector polygon ② consists of 2 type I feature points (points B, C) and 3 type II features (points a, b, c).

Third, the order of the above feature points pFeatureMainPoints needs to be adjusted correctly according to the order of the midpoints of the vector polygon. The method is similar to the following:

Fourth, the points that have been adjusted in the order in the third step are formed into line segments one by one, and these line segments constitute the sides of the vector polygon in sequence, and then call the line segment simplification algorithm to simplify the corresponding line segments, the method is as follows:

Finally, the regenerated results are formed to generate corresponding files, and the results are added to the newly generated result files. Fig. 5 shows the simplified results of Fig. 4. Comparing Fig. 4 and Fig. 5, it can be seen that type I feature points such as points A, B, ..., and type II feature points such as points a, b, c, ... etc. The "key points" that are not simplified, that is, the topological relationships of vector polygons are preserved. At the same time, due to the definition of the data structure pSimplifyResult, the line segment between two adjacent feature points has not been simplified twice, and there is no gap similar to Figure 3 due to multiple simplifications resulting in different results.

Among them, for the line segment simplification algorithm, a variety of vector line segment simplification algorithms have been developed. Here, the widely used Douglas Peucker algorithm can be used. The implementation steps are as follows (see Figure 6):

a. First determine the shortest threshold ε;

b. First connect the first and last vertices and form a line segment (in the figure ), and then calculate the distance from other points to this line segment. If the distance between a certain point and this line segment is greater than the threshold ε, then add this point to the list of required points, and at the same time, this line segment is decomposed into two corresponding line segments, as shown in the figure For point C in 6, the distance CH>ε, so point C is added to the list of final results, and the Decomposed into and

c. Repeat step b, gradually judge the decomposed line segment and add the required point sequence, and delete the unnecessary point until the distance between all points and the corresponding line segment is less than the threshold ε.

Similarly, for the land cover/utilization plot data (vector polygon) shown in Figure 7, the corresponding vector polygon maintains a good topological relationship, and Figure 8 is a schematic diagram of the effect of using parameter 500 to simplify the vector polygon in Figure 7, and Figure 9 It is a schematic diagram of the effect of simplification of the vector polygon in Figure 7 with a parameter of 5000, and Figure 10 is a schematic diagram of the effect of simplification of the vector polygon of Figure 7 with a parameter of 50000. From Figure 8 to Figure 10, the feature points shown in Figure 4 are maintained in the simplified results of different parameters, that is, the topological relationship; at the same time, due to the different parameters, the degree of simplification in Figure 8 is appropriate, and the degree of simplification in Figure 9 is It is larger, and Figure 10 is more simplified, and the similarity between the original vector polygon and the original vector polygon is even greater while the amount of vector polygon data is reduced.

The example of the present invention is realized on the PC platform, and experiments prove that the present invention can better realize the requirement of vector polygon simplification under the premise of maintaining the spatial topological relationship of land cover/utilization. The method mentioned in the present invention can be widely used in other applications such as simplification of vector polygonal data that need to maintain topology.

Claims (3)

1. keep a shortcut calculation for the windy and sandy soil vector data of topology, it is characterized in that comprising following step:

Step 1, opens and treats Predigest vector data, builds data structure, and sets up all polygonal topological structure forming windy and sandy soil, and records each polygonal adjacent polygon;

Step 2, records each polygon in step 1 and adjoins on polygonal basis, calculates each polygonal unique point, and set up the corresponding relation of polygon and unique point by each polygonal adjacent polygonal syntople;

Step 3, carries out rearranging for the unique point of each polygonal original point set order to calculating in step 2 and sorts, forming the feature point set consistent with original order;

Step 4, polygon splits by the ordinal characteristics point adopting step 3 to be formed becomes some line segments, and records the corresponding relation of polygon and line segment, and each line segment retains polygonal original point set;

Step 5, adopts certain line segment shortcut calculation to simplify all line segments in step 4;

Step 6, re-starts tissue by the result line segment after step 5 simplifies by the relation of polygon and the line segment of record in step 4 by original order, forms the polygon after simplification.

2. polygon splits by the ordinal characteristics point according to step 4 in claim 1 becomes some line segments, it is characterized in that: based on adjacent unique point, vector polygon is split into line segment, again these line segments are simplified, effectively can keep the topological adjacency relation between each vector polygon.

3. the line segment shortcut calculation according to step 5 in claim 1, it is characterized in that: select different line segment shortcut calculations according to actual conditions demand, as Douglas Peuker algorithm, cohen-sutherland algorithm, Voronoi shortcut calculation, polygon vertex elimination method etc.