CN109325156B - Rural road network matching method based on extension line segment - Google Patents

Abstract

Translated fromChinese

本发明公开了一种基于扩展线段的农村道路网匹配方法，采用在参考线段周围构建缓冲区的方法，按长度、距离、角度计算落在缓冲区内的线段与参考线段间的相似性，以此选出候选线段；针对一对多的匹配情况，提出对参考线段与候选线段分别做扩展，再依据长度、距离、形状来计算扩展后线段间的相似性，对相似性较大的线段进行选择后构成新的候选线段；构造一个自适应参数，来表示选择后的新候选线段的个数，通过迭代循环扩展步骤使自适应参数逐渐减少到1，此时即确定了与参考线段正确匹配的线段。

The invention discloses a rural road network matching method based on extended line segments, which adopts a method of constructing a buffer zone around a reference line segment, and calculates the similarity between the line segment falling in the buffer zone and the reference line segment according to the length, distance and angle, so as to calculate the similarity between the line segment and the reference line segment. This selects the candidate line segment; for the one-to-many matching situation, it is proposed to expand the reference line segment and the candidate line segment respectively, and then calculate the similarity between the expanded line segments according to the length, distance, and shape. After selection, a new candidate line segment is formed; an adaptive parameter is constructed to represent the number of new candidate line segments after selection, and the adaptive parameter is gradually reduced to 1 through the iterative circular expansion step, and the correct matching with the reference line segment is determined at this time. line segment.

Description

Rural road network matching method based on extension line segment

Technical Field

The invention relates to the field of remote sensing application, in particular to a rural road network matching method based on an extension line segment.

Background

With the development of the times, the demand of people on geographic data is increasing day by day, and the existing geographic data has the problems of incomplete information or outdated data and the like, and is not enough to meet the demand of people. Therefore, how to efficiently utilize the existing data set to update the data is a problem worthy of research. Data matching is a prerequisite and basis for updating. As for the road network, the road extraction technology based on the remote sensing image can efficiently obtain the latest road network information in real time, and the historical data set can be updated according to the matching of the reference data set and the historical data set.

To date, a great deal of research has been done on road matching, but most of these studies are based on regular, ordered urban roads, and are less likely to be concerned with the messy roads in rural areas.

Disclosure of Invention

The invention aims to overcome the defects of the prior art and provides a rural road network matching method based on an extended line segment.

In order to achieve the purpose, the invention adopts the following technical scheme:

the rural road network matching method based on the extended line segment comprises the following steps:

s1, establishing a buffer area by taking each reference line segment on the reference data set as a center, then calculating all line segments on the target data set falling in the buffer area to obtain the similarity between the reference line segments and the reference line segments, and setting the line segments meeting the threshold requirement as candidate line segments;

s2, performing line segment expansion operation on the reference line segment and all candidate line segments thereof, recalculating the similarity between the expanded reference line segment and the candidate line segments, and selecting the expanded line segment with high similarity as a new candidate line segment of the expanded reference line segment;

s3, constructing a self-adaptive parameter K to control the iteration cycle times, namely selecting the first K line segments with the highest similarity as new candidate line segments each time, and when K is 1, determining the line segment pair which is correctly matched.

Further, the similarity between the segments is calculated by the following formula:

in the formula Sim_len,Sim_dis,Sim_ang,Sim_shapeSimilarity in length, distance, angle, shape, w, respectively, of line segments_len,w_dis,w_ang，w_shapeRespectively their corresponding weights.

Further, the calculation of step S1 is specifically as follows:

s11, the buffer zone construction method is as follows

Constructing a buffer area of a rectangular area around the reference line segment by taking the reference line segment as a central line, wherein the long edge of the rectangle is parallel to the reference line segment, and the length of the rectangle is slightly greater than that of the reference line segment; the wide side of the rectangle is bisected by the reference line segment; calculating the similarity between the line segment on the target data set in the buffer area and the reference line segment according to three geometric attributes of length, distance and angle;

s12 similarity Sim in length between line segment L1 on the target data set and reference line segment L2_lenCalculated by the following formula:

Sim_len＝|L_L1-L_L2|

in the formula L_LiIs the length of the line segment Li, n is the total number of nodes in the line segment Li,

and

is the j-th node P in the line segment_jThe abscissa and ordinate of (a);

similarity in distance Sim of the line segment L1 on the target data set and the reference line segment L2_disCalculated by the following formula:

in the formula L_a,L_bAre respectively line segments L₁,L₂Any one fragment of above, | | P_a-L_bI represents a line segment L₁A certain node P on_aTo L_bPerpendicular distance, | | P_b-L_aI then represents the line segment L₂A certain node P on_bTo L_aThe vertical distance of (d);

angular similarity Sim of line segment L1 on the target data set and reference line segment L2_angCalculated by the following formula:

in the formula

Are respectively line segments L₁And a line segment L₂The expression is the inner product operation of the vector, |, is the modulus of the vector.

Further, the calculation of step S2 is specifically as follows:

respectively extending the end points of the reference line segment and all the candidate line segments outwards by a line segment unit to form a new line segment; and calculating new similarity of the formed new line segments according to three characteristics of length, distance and shape, and finally selecting the first K corresponding line segments from high to low according to the similarity as new candidate line segments of the extended reference line segment.

Further, the similarity Sim in shape of the line segment L1 on the expanded target data set and the reference line segment L2_shapeThe method comprises the following steps:

s211, setting a new complex network, and analyzing the shape of a curve; firstly, connecting all nodes on a curve pairwise to form a nondirectional fully-connected network with a weight value, wherein the weight value is a value obtained by normalizing the distance between the two nodes; then a threshold value R is given₁If the weight of the edge in the network is less than or equal to the threshold R₁The edge is retained, otherwise the edge is deleted, and the resulting new network is called the threshold R₁A complex network of lower;

s212, constructing a shape descriptor sigma according to the complex networks obtained under different thresholds; as shown below

σ＝[K_a(1)，K_m(1)，K_a(2)，K_m(2)，…，K_a(M),K_m(M)]

In the formula K_a(j) Represents a threshold value R_jAverage value of degrees of all nodes in the complex network under, K_m(j) Represents the maximum value of the degrees of all nodes in the network;

s213, line segment L₁And a line segment L₂Similarity in shape Sim_shapeThe definition is as follows:

where M represents the total number of thresholds.

Further, step S3 specifically includes the following steps:

s31, constructing a self-adaptive parameter K to represent the number of new candidate line segments to be selected; setting the well-ordered similarity sequence { Sim_i,1,Sim_i,2,…,Sim_i,m}，Sim_i,1≥Sim_i,2≥…≥Sim_i,mWhere Sim_i,jIndicating the extended reference line segment L_iAnd the extended candidate line segment L_jSimilarity between them; let j accumulate from 1, when it first encounters Sim_i,j-Sim_i,j+1≥T_sWhen the accumulation stops, the value of j is the value of K needed, where T_sIs an empirical threshold;

and S32, when the value of K is more than 1, the current candidate line segment is more than one, which does not accord with the requirement of accurate matching, and the candidate line segment needs to be further expanded until only one correct matching which accords with the requirement is found.

After the technical scheme is adopted, the corresponding candidate line segments can be selected from the reference line segments in a buffer area constructing mode, the searching space is greatly reduced, a line segment expanding mode is introduced on the basis, the topological connection relation between the line segments and the peripheral line segments is considered, the correct matching pairs are more accurately determined by combining context information, and finally, the whole matching efficiency is improved in a self-adaptive parameter constructing mode.

Drawings

FIG. 1 is a flow chart of the rural road network matching method based on extended line segments of the present invention;

FIG. 2 is a road matching effect diagram of the rural road network matching method based on extended line segments according to the present invention;

fig. 3 is a road matching local amplification effect diagram of the rural road network matching method based on the extended line segment according to the present invention, wherein fig. 3a is an amplification result of the wire frame No. 1 on the left side of fig. 2, and fig. 3b is an amplification result of the wire frame No. 2 in the middle of fig. 2.

Detailed Description

In order to make the objects, technical solutions and advantages of the present invention more apparent, the present invention is described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are merely illustrative of the invention and are not intended to limit the invention.

Fig. 1 shows a flow chart of the present invention, which mainly includes the following steps:

s1, establishing a buffer area by taking each reference line segment on the reference data set as a center, and then calculating the similarity between the reference line segment and all line segments falling on the target data set in the buffer area, wherein all the line segments meeting the threshold requirement are regarded as candidate line segments;

s2, performing line segment expansion operation on the reference line segment and all candidate line segments thereof, recalculating the similarity among the expanded line segments, and selecting the expanded line segment with high similarity as a new candidate line segment of the expanded reference line segment;

s3, constructing an adaptive parameter K to control the number of iterative cycles, namely, selecting the first K line segments with the highest similarity as new candidate line segments each time, and finding a line segment pair which is correctly matched when K is 1.

Wherein, step S1 is specifically as follows:

s11, the buffer zone construction method is as follows

Constructing a buffer area of a rectangular area around the reference line segment by taking the reference line segment as a central line, wherein the long edge of the rectangle is parallel to the reference line segment, and the length of the rectangle is slightly greater than that of the reference line segment; the wide side of the rectangle is bisected by the reference line segment; and calculating the similarity between the line segment falling on the target data set in the buffer area and the reference line segment according to three geometric attributes of length, distance and angle.

S12, similarity between segments is calculated by the following formula

In the formula Sim_len,Sim_dis,Sim_ang,Sim_shapeRespectively, the similarity of the line segments in length, distance, angle, shape, where and hereinafter a line segment includes a line segment consisting of polylines after expansion, w_len,w_dis,w_ang，w_shapeTheir respective weights;

line segment L₁And a line segment L₂Similarity in length Sim_lenCalculated by the following formula:

Sim_len＝|L_L1-L_L2|

in the formula L_LiIs the length of the line segment Li, n is the total number of nodes in the line segment Li,

and

is the j-th node P in the line segment_jThe abscissa and ordinate of (a);

line segment L₁And a line segment L₂Similarity in distance Sim_disCalculated by the following formula:

in the formula L_a,L_bAre respectively line segments L₁,L₂Any one fragment of above, | | P_a-L_bI represents a line segment L₁A certain node P on_aTo L_bPerpendicular distance, | | P_b-L_aI then represents the line segment L₂A certain node P on_bTo L_aThe vertical distance of (d);

line segment L₁And a line segment L₂Similarity in angle Sim_angCalculated by the following formula:

in the formula

Are respectively line segments L₁And a line segment L₂The expression is the inner product operation of the vector, |, is the modulus of the vector.

On the basis of the candidate line segment obtained in step S1, step S2 is performed to obtain a new candidate line segment, which specifically includes:

respectively extending the end points of the reference line segment and all the candidate line segments outwards by a line segment unit to form a new line segment; and calculating new similarity of the formed new line segments according to three characteristics of length, distance and shape, and finally selecting the first K corresponding line segments from high to low according to the similarity as new candidate line segments of the extended reference line segment.

Shape similarity is defined as follows:

a new definition of a complex network is introduced to analyze the shape of a curve (formed by a plurality of broken line segments). Firstly, all nodes on the curve are connected pairwise to formAnd a completely connected network with undirected weight value, wherein the weight value is the value after the distance normalization of the two nodes. For example, assuming a total of n nodes on a curve, a fully connected network has

An edge. Then, a threshold value R is given_lIf the weight of the edge in the network is less than or equal to the threshold R_lThe edge is retained, otherwise the edge is deleted, and the resulting new network is called the threshold R₁The following complex network.

Next, a shape descriptor σ is constructed from the complex network obtained under different thresholds. In particular, a sequence of thresholds R of equal difference values is selected₁,R₂,…,R_MWherein 0 is less than or equal to R₁≤R_M≤1，R_j+1-R_jC is a constant. From this sequence of thresholds, M complex networks result. Then, from these M complex networks, a shape descriptor σ is constructed, as shown below

σ＝[K_a(1)，K_m(1)，K_a(2)，K_m(2)，…，K_a(M),K_m(M)]

In the formula K_a(j) Represents a threshold value R_jAverage value of degrees of all nodes in the complex network under, K_m(j) Representing the maximum value of degrees for all nodes in the network. Therefore, line segment L₁And a line segment L₂Similarity in shape Sim_shapeThe following can be defined:

where M represents the total number of thresholds.

On the basis of obtaining a new candidate line segment in step S2, an adaptive parameter is used to obtain an accurate matching result, which specifically includes the following steps:

an adaptive parameter K is constructed to indicate the number of new candidate segments to be selected. Suppose now thatWith well-ordered similarity sequences { Sim_i,1,Sim_i,2,…,Sim_i,m}，Sim_i,1≥Sim_i,2≥…≥Sim_i,mWhere Sim_i,jIndicating the extended reference line segment L_iAnd the extended candidate line segment L_jThe similarity between them. Let j accumulate from 1, when it first encounters Sim_i,j-Sim_i,j+1≥T_sWhen the accumulation stops, the value of j is the value of K needed, where T_sIs an empirical threshold.

If the value of K is more than 1, the current candidate line segment is more than one, which does not meet the requirement of accurate matching, so the candidate line segment needs to be further expanded until only one correct matching meeting the requirement is found.

Fig. 2 is a diagram illustrating the road matching effect of the present invention applied to high-resolution satellite images. The target data set of the invention is a road network extracted from an image shot by a Pleiades-1A satellite, the resolution of the image is 0.5m, and the size of the image is 28648 multiplied by 37929 pixels; the reference data set is a road network formed by historical vehicle tracks provided by a Chinese traffic communication center. Fig. 2 is a graph of the effect of matching a part of the area of the whole road network, wherein fig. 2a is a target data set and fig. 2b is a reference data set.

Fig. 3 is an enlarged view of the matching effect within the two rectangular boxes in fig. 2. Fig. 3(a) corresponds to the enlargement of the frame No. 1 on the left in fig. 2, and fig. 3(b) corresponds to the enlargement of the frame No. 2 in the middle in fig. 2. In fig. 3,line 1 represents the reference data set, while for the target data setline 2 represents the correctly matched road segments,line 3 represents the unmatched road segments, andline 4 represents the incorrectly matched road segments.

The following table shows the data statistics of the road matching results:

the literature on relevant road matching algorithms is as follows:

[1]MengZhang and LiqiuMeng,“Delimited stroke oriented algorithm-working principle and implementation for the matching of road networks,”Geographic Information Sciences,vol.14,no.1,pp.44–53,2008.

due to the fact that rural roads are relatively cluttered, some small and remote roads are missed from the historical reference data set, and the matching rate of the algorithm is not high and is only 74.73%. However, the accuracy of the algorithm reaches 87.24%, which is much higher than the accuracy of 83.41% in the document [1], which proves that the accuracy of the rural road matching using the method is greatly improved.

The above is only a preferred embodiment of the present invention, but the scope of the present invention is not limited thereto, and any changes or substitutions that can be easily conceived by those skilled in the art within the technical scope of the present invention are also within the scope of the present invention; therefore, the protection scope of the present invention shall be subject to the protection scope of the claims.

Claims (6)

1. A rural road network matching method based on an extended line segment is characterized by comprising the following steps:

s1, establishing a buffer area by taking each reference line segment on the reference data set as a center, then calculating all line segments on the target data set falling in the buffer area to obtain the similarity between the reference line segments and the reference line segments, and setting the line segments meeting the threshold requirement as candidate line segments;

s2, performing line segment expansion operation on the reference line segment and all candidate line segments thereof, recalculating the similarity between the expanded reference line segment and the candidate line segments, and selecting the expanded line segment with high similarity as a new candidate line segment of the expanded reference line segment;

s3, constructing a self-adaptive parameter K to control the iteration cycle times, namely selecting the first K line segments with the highest similarity as new candidate line segments each time, and when K is 1, determining the line segment pair which is correctly matched;

the method for constructing the buffer area in step S1 is as follows:

constructing a buffer area of a rectangular area around the reference line segment by taking the reference line segment as a central line, wherein the long side of the rectangle is parallel to the reference line segment, and the length of the rectangle is greater than that of the reference line segment; the wide side of the rectangle is bisected by the reference line segment; and calculating the similarity between the line segment falling on the target data set in the buffer area and the reference line segment according to three geometric attributes of length, distance and angle.

2. The method for rural road network matching based on extended line segments according to claim 1, wherein the similarity between the line segments is calculated by the following formula:

in the formula Sim_len，Sim_dis，Sim_ang，Sim_shapeSimilarity in length, distance, angle, shape, w, respectively, of line segments_len，w_dis，w_ang，w_shapeRespectively their corresponding weights.

3. The method for rural road network matching based on extended line segments of claim 2, wherein the similarity Sim in length between the line segment L1 on the target data set and the reference line segment L2 in step S1_lenCalculated by the following formula:

Sim_len＝|L_L1-L_L2|

in the formula L_LiIs the length of the line segment Li, n is the total number of nodes in the line segment Li,

and

is the j-th node P in the line segment_jThe abscissa and ordinate of (a);

similarity in distance Sim of the line segment L1 on the target data set and the reference line segment L2_disCalculated by the following formula:

in the formula L_a，L_bAre respectively line segments L₁，L₂Any one fragment of above, | | P_a-L_bI represents a line segment L₁A certain node P on_aTo L_bPerpendicular distance, | | P_b-L_aI then represents the line segment L₂A certain node P on_bTo L_aThe vertical distance of (d);

angular similarity Sim of line segment L1 on the target data set and reference line segment L2_angCalculated by the following formula:

in the formula

Are respectively line segments L₁And a line segment L₂The expression is the inner product operation of the vector, |, is the modulus of the vector.

4. The method for matching a rural road network based on extended line segments according to claim 3, wherein the calculation of step S2 is as follows:

respectively extending the end points of the reference line segment and all the candidate line segments outwards by a line segment unit to form a new line segment; and calculating new similarity of the formed new line segments according to three characteristics of length, distance and shape, and finally selecting the first K corresponding line segments from high to low according to the similarity as new candidate line segments of the extended reference line segment.

5. The method for rural road network matching based on expanded line segments of claim 4, wherein the similarity Sim in shape between the line segment L1 on the expanded target data set and the reference line segment L2 is_shapeThe method comprises the following steps:

s211, setting a new complex network, and analyzing the shape of a curve; firstly, connecting all nodes on a curve pairwise to form a nondirectional fully-connected network with a weight value, wherein the weight value is a value obtained by normalizing the distance between the two nodes; then a threshold value R is given₁If the weight of the edge in the network is less than or equal to the threshold R₁The edge is retained, otherwise the edge is deleted, and the resulting new network is called the threshold R₁A complex network of lower;

s212, constructing a shape descriptor sigma according to the complex networks obtained under different thresholds; as shown below

σ＝[K_a(1)，K_m(1)，K_a(2)，K_m(2)，…，K_a(M)，K_m(M)]

In the formula K_a(j) Represents a threshold value R_jAverage value of degrees of all nodes in the complex network under, K_m(j) Represents the maximum value of the degrees of all nodes in the network;

s213, line segment L₁And a line segment L₂Similarity in shape Sim_shapeThe definition is as follows:

where M represents the total number of thresholds.

6. The method for matching a rural road network based on extended line segments according to claim 1, wherein step S3 specifically comprises the following steps:

s31, constructing a self-adaptive parameter K to represent the number of new candidate line segments to be selected; setting the well-ordered similarity sequence { Sim_i，1，Sim_i，2，…，Sim_i，m}，Sim_i，1≥Sim_i，2≥…≥Sim_i，mWhere Sim_i，jIndicating the extended reference line segment L_iAnd the extended candidate line segment L_jSimilarity between them; let j accumulate from 1, when it first encounters Sim_i，j-Sim_i，j+1≥T_sWhen the accumulation stops, the value of j is the value of K needed, where T_sIs an empirical threshold;

and S32, when the value of K is more than 1, the current candidate line segment is more than one, which does not accord with the requirement of accurate matching, and the candidate line segment needs to be further expanded until only one correct matching which accords with the requirement is found.

Images