CN116257766B - Multi-index road network matching method based on minimum cost network flow model - Google Patents
Multi-index road network matching method based on minimum cost network flow model Download PDFInfo
- Publication number
- CN116257766B CN116257766B CN202310067584.3A CN202310067584A CN116257766B CN 116257766 B CN116257766 B CN 116257766B CN 202310067584 A CN202310067584 A CN 202310067584A CN 116257766 B CN116257766 B CN 116257766B
- Authority
- CN
- China
- Prior art keywords
- road
- matching
- similarity
- network
- minimum cost
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 40
- 239000013598 vector Substances 0.000 claims description 21
- 230000002457 bidirectional effect Effects 0.000 claims description 7
- 238000012545 processing Methods 0.000 claims description 4
- 230000006870 function Effects 0.000 description 20
- 238000010586 diagram Methods 0.000 description 9
- 238000005457 optimization Methods 0.000 description 9
- 238000004364 calculation method Methods 0.000 description 8
- 230000008569 process Effects 0.000 description 5
- 230000010354 integration Effects 0.000 description 3
- 238000007781 pre-processing Methods 0.000 description 3
- 238000004422 calculation algorithm Methods 0.000 description 2
- 238000006243 chemical reaction Methods 0.000 description 2
- 238000012217 deletion Methods 0.000 description 2
- 230000037430 deletion Effects 0.000 description 2
- 238000002474 experimental method Methods 0.000 description 2
- 238000007429 general method Methods 0.000 description 2
- 241000282376 Panthera tigris Species 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000019771 cognition Effects 0.000 description 1
- 239000002131 composite material Substances 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 238000013500 data storage Methods 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 239000011159 matrix material Substances 0.000 description 1
- 238000005259 measurement Methods 0.000 description 1
- 238000012821 model calculation Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 238000012360 testing method Methods 0.000 description 1
- 230000009466 transformation Effects 0.000 description 1
- 230000000007 visual effect Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/28—Databases characterised by their database models, e.g. relational or object models
- G06F16/284—Relational databases
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/29—Geographical information databases
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Remote Sensing (AREA)
- Traffic Control Systems (AREA)
Abstract
The invention discloses a multi-index road network matching method based on a minimum cost network flow model, which comprises the steps of constructing similarity indexes between any two entities of two road data sets to be matched, wherein the entities refer to road line elements forming a road network in the road data sets; judging potential matching pairs in two road data sets to be matched by using similarity indexes between any two entities; each entity in the two road data sets is expressed as a node in the flow network, all potential matching pairs are expressed as a group of network edges with flow parameters, and a minimum cost network flow model is constructed; and using the similarity index between any two entities as the cost in the objective function, and carrying out minimum cost network flow model matching to realize multi-index road network matching. The similarity index between any two entities is a comprehensive index formed by the distance similarity, the direction similarity and the shape similarity between any two entities according to the proportion. And the accuracy of the matching result is high.
Description
Technical Field
The invention belongs to the field of road network matching, and relates to a multi-index road network matching method based on a minimum cost network flow model.
Background
The map merging is a process of combining two digital maps to generate a third map file superior to the source map, and is mainly divided into two parts, namely map matching and map merging, wherein the difference of the same geographic entity in different data sources in the aspects of scale, structure, geometry, semantics and the like is possible due to different geographic information standards, data processing requirements, acquisition paths and acquisition times, and spatial data matching is needed before merging. Map matching is to calculate the similarity or difference of the same geographic entity in different data sources according to certain geographic entity characteristics, so as to identify the same geographic entity, establish a matching relationship, wherein a road network is a main component of a map, and the matching among multi-source road networks is one of current research hotspots.
In the aspect of strategy selection of road matching, at present, the matching result is mainly obtained by adopting methods such as feature weight combination and threshold selection, probability relaxation method, ant colony algorithm, optimization, morphing transformation, regression model construction, stroke limiting algorithm, map-oriented comprehensive similarity calculation, subjective and objective integrated weighting and the like. The conventional optimization model generally calculates a distance matrix between two road networks as a necessary model parameter, then uses linear problem solvers such as IBM ILOG CPLEX or AMPL to solve an optimal matching result, and finally uses GIS software to analyze the matching result, which is tedious and time-consuming. The network flow-based appreach [ J ]. Transactions in GIS,2019,23 (5) provides a feature matching optimization model based on network flow, which is helpful for overcoming the suboptimal defect of the traditional optimization method, however, the optimization model only uses the distance index in the geometric feature, namely the directed Hausdorff distance, to measure the similarity between matched objects when selecting the similarity index, and the accuracy of the matching result obtained by means of a single similarity index in the matching process is lower.
Disclosure of Invention
The embodiment of the invention aims to provide a multi-index road network matching method based on a minimum cost network flow model, which aims to solve the problem that the accuracy of a matching result obtained by the existing network flow-based characteristic matching optimization model by means of a single similarity index is low.
The technical scheme adopted by the embodiment of the invention is as follows: the multi-index road network matching method based on the minimum cost network flow model comprises the following steps:
constructing similarity indexes between any two entities of two road data sets to be matched, wherein the entities refer to road line elements forming a road network in the road data sets;
judging potential matching pairs in two road data sets to be matched by using similarity indexes between any two entities;
each entity in the two road data sets is expressed as a node in the flow network, all potential matching pairs are expressed as a group of network edges with flow parameters, and a minimum cost network flow model is constructed;
and using the similarity index between any two entities as the cost in the objective function, and carrying out minimum cost network flow model matching to realize multi-index road network matching.
Further, the similarity index between any two entities is a comprehensive index formed by the distance similarity, the direction similarity and the shape similarity between any two entities according to the proportion.
Further, the directional similarity between any two entities, namely road line elements, is calculated according to the following process:
first, the connection line between the start point coordinates and the end point coordinates of two road line elements is regarded as a vector to obtain a vectorSum vector->
Then, calculate the vectorSum vector->After the inverse cosine of the cosine absolute value of the included angle, the direction similarity D of the two road line elements is calculated according to the following formula dir ：
wherein ,for vector->Sum vector->Included angle between->For vector->Sum vector->An inverse cosine of the cosine absolute value of the angle (a), a +.>Is to->Is converted from an arc value to an angle value.
Further, the shape similarity between any two entities, namely road line elements, is calculated according to the following process:
for non-closed road line elements, a closed polygonal plane element, namely a closed curve, is formed by mirror image processing of the connection line of the head and tail points, and then any point P on the road line element (s) Can be expressed as a function of the length s of the curve from this point to the starting point as an argument:
P (s) ＝X (s) +iY (s) ； (9)
wherein ,X(s) Functional expression representing abscissa of moving point on polygon, Y (s) A functional expression representing the ordinate of the moving point on the polygon, i representing the i-th point from the starting point;
the expression of the function developed by the fourier series is:
where s denotes the length of the curve from the point to the starting point being calculated, L is the circumference of a closed curve, n= (0, ±1, ±2 …), the upper limit of n is the maximum order of the fourier series, and the coefficient c of the n-order fourier series n The expression of (2) is:
wherein N represents the number of nodes of a polygon, i.e., a closed curve boundary line, S i For starting point P 0 The curve length to the i-th point P of the closed curve, j is the imaginary unit, X (s) and Y(s) The expression of (2) is:
wherein ,xi Represents the i-th point P of the closed curve i Is y i Represents the i-th point P of the closed curve i Is the ordinate of S i ≤s≤S i+1 ；
Taking c n Is a modulus vector v= (|c) 1 ‖，‖c 2 ‖…‖c i ‖…‖c N II), and normalizing the vector to obtain a Fourier shape descriptor d i ：
Shape similarity D between closed curve a and closed curve b corresponding to two road line elements shape Expressed as:
in the formula ,Δshape A threshold value, d, being the maximum value of the difference between the Fourier shape descriptors of two road line elements a (i is the Fourier shape descriptor of the ith point on the closed curve a, d b (i) Is the fourier shape descriptor of the i-th point on the closed curve b.
Further, the comprehensive index is composed of distance similarity, direction similarity and shape similarity according to the ratio of 6:3:1.
Further, the similarity index between any two entities is used for judging potential matching pairs in the two road data sets to be matched, whether the similarity index between the two entities is larger than a set threshold value or not is judged, and if the similarity index is larger than the set threshold value, the corresponding two entities are the potential matching pairs.
Further, when constructing the minimum cost network flow model, all potential matching pairs are represented as a group of network edges with flow parameters, and a directed graph is obtained by connecting two entities of each potential matching pair of two road data sets by using a directional line, wherein N represents a set of nodes N, and E represents a set of connecting lines between the nodes, namely edges E, and then the objective function of the network flow model G (N, E) is as follows:
Minimize∑ e∈E c e f e ； (1)
wherein ,fe Is the flow value of each edge e, c e Is each flow value f e Is a cost of (2);
the corresponding constraint conditions are:
wherein ,In Is the set of edges e that enter node nClosing, O n Is the set of edges e going out from node n, l e Is the flow value f e Lower bound of u e Is the flow value f e Is a lower bound of (c).
Further, the minimum cost network flow model is a bidirectional network flow model.
Further, a minimum cost network flow model is built in a relational database, and a road network matching result is obtained by means of calculation of a minimum cost network flow calculation function, and the method comprises the following specific operations:
importing a minimum cost network flow resolving function and road data to be matched into a relational database, and converting the imported road data to be matched and the calculated comprehensive similarity value into fields of the following road data table:
(1) A source node corresponding to a fid of one of the two road data tables;
(2) Sink node corresponding to fid of another road data table in the two road data tables;
(3) The capacity of a flow, i.e., the upper bound of the flow value that the directed edge in the minimum cost network flow model allows to pass through;
(4) The lower limit of the flow, i.e. the lower limit of the flow value allowed by the directed edge in the minimum cost network flow model;
(5) Cost, i.e., similarity index between potential matching pairs;
(6) The value of the directed edge passing flow in the minimum cost network flow model is 1 when two entities are matched, otherwise, the value is 0;
(7) The network side, namely a column of fields formed by combining the fields (1) and (2) in the road data table, records the field of the potential matching pairs, intuitively sees all the potential matching pairs, and checks whether the input data are correct or not;
and then, operating a function calling command of the relational database, calling the imported minimum cost network flow resolving function, and performing road network matching.
Further, when the imported minimum cost network flow resolving function is called to carry out road network matching, a matching result is recorded by setting an external key father pointer in a relational database.
The embodiment of the invention has the beneficial effects that: the method is characterized in that a plurality of measurement indexes of distance similarity, direction similarity and shape similarity are comprehensively utilized to jointly calculate an optimal matching result in a minimum cost network flow model, a multi-index matching method based on the minimum cost network flow model is provided, the direction similarity and the shape similarity of road line elements based on Fourier descriptors are respectively used as direction indexes and shape indexes of geometric features, and the distance indexes are used for comprehensively evaluating the similarity between the road line elements, multi-source road network matching is carried out in a relational database PostgreSQL through the minimum cost network flow model, the matching accuracy is remarkably improved, and the problem that the accuracy of the matching result obtained by the existing network flow-based feature matching optimization model by means of a single similarity index is low is effectively solved.
Drawings
In order to more clearly illustrate the embodiments of the invention or the technical solutions in the prior art, the drawings that are required in the embodiments or the description of the prior art will be briefly described, it being obvious that the drawings in the following description are only some embodiments of the invention, and that other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.
Fig. 1 is a schematic diagram of the architecture of a unidirectional network flow model.
Fig. 2 is a schematic diagram of the structure of a bidirectional network flow model.
FIG. 3 is a schematic diagram of setting foreign key parent pointers in a relational database to represent matching relationships.
Fig. 4 is a schematic diagram of setting a bridging table in a relational database to calculate a matching result.
Fig. 5 is a schematic diagram of the difference in included angles between road line elements in different node storage sequences.
Fig. 6 is a schematic diagram of the mirror image operation of the road line elements.
Fig. 7 is a graph of road network data for six experimental areas selected.
Fig. 8 is a graph of the minimum cost network flow model matching results for experimental zone 6 of fig. 7.
Fig. 9 is a diagram of the result of mismatching and missed matching of a single similarity index.
Fig. 10 is a diagram of the result of the correct matching of the integrated similarity index.
Fig. 11 is a diagram of the result of the miss-matching of the single similarity index.
FIG. 12 is a graph of the correct 1:N match results for the integrated similarity index.
Detailed Description
The technical solutions in the embodiments of the present invention will be clearly and completely described in the following in conjunction with the embodiments of the present invention, and it is obvious that the described embodiments are only some embodiments of the present invention, but not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.
Example 1
The embodiment provides a multi-index road network matching method based on a minimum cost network flow model, which constructs a network flow model in a relational database to realize global optimization matching of a road network, and comprises the following steps:
preprocessing road data of two road data sets to be matched, including data deletion, integration, conversion and specification;
constructing similarity indexes between any two entities of two road data sets to be matched, wherein the entities refer to road line elements forming a road network in the road data sets;
judging potential matching pairs in two road data sets to be matched by using similarity indexes between any two entities;
each entity in the two road data sets is expressed as a node in the flow network, all potential matching pairs are expressed as a group of network edges with flow parameters, and a minimum cost network flow model is constructed;
and using the similarity index between any two entities as the cost in the objective function, and carrying out minimum cost network flow model matching to realize multi-index road network matching.
Each entity in the two road data sets is represented as a node in the flow network, if a matching relationship exists between the two entities, the corresponding entities are connected by a line with a direction, a directed graph, namely a network flow model G (N, E), is obtained, N represents a set of nodes N, E represents a set of connecting lines between the nodes, namely an edge E, and at the moment, the objective function of the network flow model is as follows:
wherein ,fe Is the flow value of each edge e, c e Is each flow value f e The objective of objective function (1) is to minimize the total cost of the flow;
the corresponding constraint conditions are:
l e ≤f e ≤u e ，e∈I n ∪O n ，n∈N； (3)
wherein ,In Is the set of edges e into node n, O n Is the set of edges e going out from node n, l e Is the flow value f e Lower bound of u e Is the flow value f e Constraint conditions (2) - (3) ensure that the traffic values of all entering node n and exiting node n are equal, maintaining the overall traffic conservation in the streaming network.
The matching relationship between the same-name roads can be divided into four types, namely 1:0 matching, 1:1 matching, 1:N matching and M:N matching, the unidirectional network flow model is used for solving the problems of 1:0 matching and 1:1 matching, the structure is as shown in figure 1, A2 and A3 are three entities in a road data set A, B1, B2 and B3 are three entities in a road data set B, the three entities form network nodes of the unidirectional network flow model, and when the similarity index between a pair of entities in the road data sets A and B is larger than a set value, a directed edge e is added from the node of the road data set A to the node of the road data set B, so that the pair of entities are potential matching pairs. Has the following componentsThe three numbers on the edge represent the cost between the two entities connected with the three numbers, the lower limit of the flow value and the upper limit of the flow value, the source node S for starting all flows, the sink node T for converging all flows and the balance edge from T to S are added, the-F on the balance edge represents the condition that the cost endowed with a negative value avoids the occurrence of a completely empty matching relationship, M is the total capacity value of the network flow model circulation, and the lower limit of the flow value flowing through the directed edge is 0, the upper limit is 1, so the model total cost minimum sigma is minimized e∈E c e f e The matching result, namely the directed edge set, of each two entities is at most connected by one directed edge, namely either one directed edge, namely the flow value is 1, or no directed edge, namely the flow value is 0, and the unidirectional network flow model is different from the traditional assignment problem in that the unidirectional network flow model does not force that each entity in one road data set must be matched with a certain entity in the other road data set, and the 1:0 matching problem in the actual situation is solved on the basis of realizing 1:1 matching.
The problems of 1:N matching and M:N matching are further solved, a mirror network of the unidirectional network flow model is constructed, and a bidirectional network flow model is formed. As shown in fig. 2, the bidirectional network flow model is composed of a forward network representing a match from the road data set a to the road data set B and a reverse network representing a match from the road data set B to the road data set a, which is also active node T ', sink node S', nodes B '1, B'2, B '3, a'1, a '2, a'3 in the reverse network corresponding to nodes B1, B2, B3, A1, A2, A3 in the forward network. For 1:N matching, there may be a case that multiple entities are matched to a single entity, but the upper bound of the flow value of the edge from each entity to the sink node is still 1, at most, only one edge can be allowed to be connected from the entity to the sink node, and the excessive edge is the remaining edge at the moment, so that an excessive sink node E is set, the remaining edge from each destination node A '1, A'2, A '3, B1, B2 and B3 flows to the excessive sink node E, and the upper bound of the directed edge flowing to the excessive sink node E is M, which indicates that the excessive sink node E allows more than one flow from the destination nodes A'1, A '2, A'3, B1, B2 and B3 to enter, and the excessive sink node E collects the remaining matched edges of 1:N, so that one-to-many matching is realized. The global sink node J is arranged to aggregate all flows from sink nodes T and S 'of the forward and reverse networks and the global source node I is arranged to collect flows from the global sink node J and to direct them to source nodes S and T' of the forward and reverse networks. And the non-negative punishment cost P is arranged on the directed edge from the excess sink node E to the global sink node J, so that one-to-many matching is limited, cliff reduction during one-to-many matching of the total cost is avoided, the forward network and the reverse network are coordinated, and the inconsistent matching problem of the forward network and the reverse network is avoided. The forward and reverse networks form a complete network of interconnections through the global source node I, the global sink node J and the excess sink node E,
specifically, the present embodiment constructs a minimum cost network flow model in a relational database. The association radix (the number of entries in the match table match_table bridged in fig. 4, i.e. the number of columns of the data table) is the number of entities in one surface corresponding to the other surface and inside entity in the relational database, for example, one-to-one (1:1) association means that each entity in one surface is associated with one entity in the other surface at most, and corresponds to the same name entity when the two entities are in a 1:1 matching relationship in the multi-source road network, where the entities refer to road line elements forming the road network in the road dataset. One-to-many association (1:N) refers to the fact that multiple entities in one surface belong to a single entity (parent entity) in another surface, and one-to-many matching is a special case of one-to-many matching due to the lack of uniform specifications between road datasets of a multi-source road network. The many-to-many association (M: N) is actually a two-way one-to-many (1: N) association, and for the matching between road network road data sets, the two ways are mainly implemented in a relational database, firstly, the matching is implemented by setting an external key father pointer, as shown in FIG. 3, A_ #1 and B_ #1 are attribute tables of first regional road network data of a road data set A and a road data set B respectively, in the table A_ #1, fid is a main key of the table A_ #1, and refers to a unique entity in the road data set A; m_fid is the foreign key of table a_1, refers to the only entity in road dataset B that matches the entity corresponding to the primary key fid of table a_1, and fid in table b_1 is the parent key of m_fid in table a_1, i.e. the parent entity of m_fid entity in table a_1 is its entity corresponding to fid in table b_1, e.g. when fid in table a_1 is 19 and m_fid is 56, then the entity of fid in table b_1 is the matching object of the entity of fid in table a_1 is 19, and there is a flow from a19 to B56 in the corresponding network flow model; similarly, fid in Table A_#1 is the parent of m_fid in Table B_1. Secondly, the two tables are associated by establishing a bridging table, namely a matching table, as shown in fig. 4, a new table, namely a matching table, is created by taking the main keys in the table a_ #1 and the table b_ #1 as fields fid1 and fid2, the main key fid of the first behavior table a_ #1 of the matching table is a father key, the main key fid of the second behavior table b_ #1 is a son key, the father key is unique and not repeated, the son key may be repeated, and the table a_ #1 and the table b_ #1 are associated by the matching table, so that matching is realized. When one parent key corresponds to one child key, one parent key corresponds to a plurality of child keys, one-to-many matching is performed, and two-way 1:N matching, namely M:N matching, is formed by combining the table A_1 to the table B_1 matching with the table B_1 to the table A_1 matching. In the embodiment, the parent pointer mode is used for representing the matching relation, the bridging table is used for calculating the matching result and counting the accuracy.
Inputting corresponding fields of a road data table in a relational database, converting the matching problem into a network flow problem, constructing a minimum cost network flow model, and inputting the fields of the road data table, wherein the fields comprise:
(1) A source node (origin) corresponding to a fid of one of the two road data tables;
(2) Sink node (destination) corresponding to the fid of the other of the two road data tables;
(3) Flow capacity (capability), i.e. the flow value f allowed by the directed edge in the minimum cost network flow model e Upper bound u of (2) e ；
(4) Lower bound of flow (lowbound), i.e. the flow value f allowed by the directed edge in the minimum cost network flow model e Lower bound l of (2) e ；
(5) Cost, i.e., the index of difference between potential matched pairs, is the index of similarity between potential matched pairs;
(6) Flow value (flow), the value of the directed edge passing flow in the minimum cost network flow model, the flow value is 1 when two entities are matched (connected through the directed edge), otherwise, the flow value is 0;
(7) The network side (edge_id), namely a column of fields formed by combining the fields (1) and (2) in the road data table, does not participate in the model calculation process, can intuitively see which potential matching pairs exist through the column of fields, records the fid of the potential matching pairs, and checks whether the input data are correct.
And importing a minimum cost network flow resolving function and road data to be matched into a relational database, converting the imported road data to be matched and the calculated comprehensive similarity value into fields (1) - (7) of a road data table to form a corresponding road data table, then operating a calling function command of the database, calling the imported minimum cost network flow resolving function, and resolving the matching relationship of the two corresponding road data tables to realize road network matching.
In some embodiments, the similarity index between any two entities is a comprehensive index formed by the distance similarity, the direction similarity and the shape similarity between any two entities according to a proportion, and through a large number of tests, the matching accuracy is highest when the comprehensive index is formed by the distance similarity, the direction similarity and the shape similarity according to a proportion of 6:3:1.
In order to solve the 1:N and N:1 matching problem, the distance similarity is measured by adopting a directed Hausdorff distance, and the road line element F is a point set p F ＝{p f1 ，p f2 ，…，p fm -and road line element G, i.e. point set p G ＝{p g1 ，p g2 ，…，p gn The directed Hausdorff distance between } is:
wherein m and n are the number of nodes constituting different roads,directed Hausdorff distance for road line elements F to G, +.>For the directed Hausdorff distance of the road line elements G to F, II indicates the point p f and pg The Euclidean distance between two points is min {. The minimum value of the Euclidean distance set between the two points is selected, and max {. The maximum value of the Euclidean distance minimum value set between the road line elements F and G is selected;
distance similarity D between road line elements F to G distance The method comprises the following steps:
distance similarity D between road line elements G to F distance The method comprises the following steps:
in the formula ,Δdistance For the maximum value of the directed Hausdorff distance theory of the road line elements F and G, namely, the radius D of a buffer zone used when the Hausdorff distance between the two road line elements F and G is calculated distance The larger the distance similarity of the road line elements F and G is explained to be higher.
The range of the space direction is 0, 360 DEG]For the direction θ of one road line element, the road line elements θ=0° and θ=180° are different, and the road line element θ of 90 ° is more similar to the road line element θ of 0 ° than θ of 180 °, which is inconsistent with intuitive spatial awareness of people. In this embodiment, the connection line between the start point coordinates and the end point coordinates of two road line elements is regarded as a vector, and the inverse cosine of the absolute value of the cosine of the vector included angle between the two road line elements is calculated as the similarity of the directions of the road line elements, as shown in fig. 5 (a), the vectorSum vector->Respectively is a road line element l 1 (F 1 ，T 1 ) And a road line element l 2 (F 2 ，T 2 ) Abstract vector, vector-> and />Direction similarity D of (2) dir The method comprises the following steps:
wherein ,for vector->Sum vector->Included angle between->For vector->Sum vector->An inverse cosine of the cosine absolute value of the angle (a), a +.>Is to->The calculation result of (2) is converted into an angle value from an radian value, and the direction similarity D dir The larger the angle between two road line elements, the smaller the direction similarity.
Fig. 5 (a) and fig. 5 (b) are two cases of the storage sequence of the road line element nodes, and the calculation of the included angle between the two vectors by the general method may lead to the calculation result of fig. 5 (a) being greatly different from the calculation result of fig. 5 (b), and when the two vectors tend to coincide or be 180 ° in reality, the direction similarity of the two corresponding road line elements is high, because the direction of the single road line element is calculated by taking the coordinates of the first node and the last node, and the data storage sequence of the first node and the last node of the road line element corresponding to the matching road line element in the other road data set may be exactly opposite, and thus the directions of the two calculated road line elements may be in the same direction or in opposite directions, so that the general method may not calculate the direction similarity accurately. Because the absolute value range of the cosine of the included angle of the two vectors is [0,1], and the inverse cosine of the included angle is [0, 90 ° ], the method of the embodiment is adopted to calculate that the direction similarity between the two road line element vectors in fig. 5 (a) and fig. 5 (b) is equal, and the method accords with the visual cognition of space.
The shape similarity of the road line elements is generally calculated by an angle difference integration method, but when the storage sequence of the nodes of the two road line elements is changed, the azimuth angle of the two road line elements is also changed, the calculated integral difference may not be a true value, and for the two same name elements, the two same name elements are influenced by the drawing sequence, the detail degree and the like, and the starting point probability of the two same name elements is not corresponding.
First, for fig. 6 (a)Non-closed road line elements, the line connecting the head and tail points being mirrored to form a closed polygonal plane element, i.e. a closed curve, as shown in FIG. 6 (b), at P 0 As a starting point, any point P on the road line element (s) Can be expressed as a function of the length s of the curve from this point to the starting point as an argument:
P (s) ＝X (s) +iY (s) ； (9)
wherein ,X(s) Functional expression representing abscissa of moving point on polygon, Y (s) The functional expression representing the ordinate of the moving point on the polygon, i representing the i-th point from the starting point. The function is a piecewise function taking twice the perimeter of a road line element as a period, and the expression developed through the Fourier series is as follows:
where s denotes the length of the curve from the point to the starting point being calculated, L is the circumference of a closed curve, n= (0, ±1, ±2 …), the upper limit of n is the maximum order of the fourier series, and the coefficient c of the n-order fourier series n The expression of (2) is:
wherein N represents the number of nodes of a polygon, i.e., a closed curve boundary line, S i For starting point P 0 To the ith point P of the closed curve i Is the imaginary unit, X (s) and Y(s) The expression of (2) is:
wherein ,xi Represents the i-th point P of the closed curve i Is y i Represents the i-th point P of the closed curve i Is the ordinate of S i ≤s≤S i+1 The method comprises the steps of carrying out a first treatment on the surface of the Taking c n Is a modulus vector v= (|c) 1 ‖，‖c 2 ‖…‖c i ‖…‖c N II), and normalizing the vector to obtain a Fourier shape descriptor d i ：
Since the frequency components of the fourier series are orthogonal to each other, and each parameter in the vector has stronger independence, the shape similarity between the closed curve a and the closed curve b corresponding to two road line elements is represented by the euclidean distance between their corresponding normalized fourier descriptors:
in the formula ,Δshape A threshold value, D, being the maximum value of the difference between the Fourier shape descriptors of two road line elements shape The larger indicates the smaller the difference between the two curves, the higher the similarity. d, d a (i) Fourier shape descriptor, d, being the i-th point on closed curve a b (i) Is the fourier shape descriptor of the i-th point on the closed curve b.
Example 2
In this example, six regions of Saint Barbara City, calif., were selected as the experimental regions, road network data were from two open source road data sets of OpenStreetMap (OSM) (https:// planet. Opentreetmap. Org) and TIGER/Line (TGR) (https:// www.census.gov/geograms/mapping-files/time-services/geo/TIGER-geodata base-file. Html), as shown in FIG. 7. The preprocessing of the road data comprises data deletion, integration, conversion and protocol, and the main purpose of the preprocessing is to eliminate or reduce errors and insignificant details and noise in the road network data so as to ensure the correctness, consistency, integrity and reliability of the data and eliminate the inconsistency of topological relation description and definition among different road data sets, thereby enabling direct comparison and matching. In addition, in order to count indexes such as accuracy of a matching result through a relational database, real matching processing needs to be carried out on multi-source road data before experiments, namely, a father key entity of each road data attribute table is established.
The minimum cost network flow calculation function (mincost_circulation) which uses a Lemon C++ solver as expansion is called in a relational database PostgreSQL under a LINUX operation system to calculate, comprehensive indexes consisting of distance similarity, direction similarity and shape similarity in proportion are used as expenses in an objective function to perform bidirectional network flow model matching, the result with the minimum total expenses obtained by calculating the bidirectional network flow model is the optimal road network matching result, the matching result is compared with the matching result with a single index, the accuracy of six experimental areas is improved to a certain extent as shown in a table 1, and the most obvious area is improved by 8.03%.
Table 1 single index and composite index match accuracy contrast
Table 2 experiment area 6 match results statistics table
Fig. 8 is an overview of the results of the experimental zone 6 after the multi-index minimum cost network flow model matching, and fig. 2 is a statistical table of the model matching results of the experimental zone 6, wherein the number of mismatching has been reduced to 0 after the optimal matching, and the final accuracy rate reaches 96.43%.
FIG. 9 is a graph showing the result of performing minimum cost network flow model matching using only the directed Hausdorff distance as a single similarity index for a region, where the road with the OSM data FID of 299 is mismatched to the road with the TGR data FID of 14, and where the road with the OSM data FID of 492 has a problem of mismatching; fig. 10 shows the result of matching the minimum cost network flow model by using comprehensive indexes of distance similarity, direction similarity and shape similarity in the same area, and the problems of mismatching and missed matching of the same-name roads are corrected.
The comparison of fig. 11 and fig. 12 is an example of the comprehensive multi-index method for solving the 1:n matching problem, and when the similarity index is a single index, the road with FID 62 in OSM data cannot be matched with the same-name road, namely, the road with FID 291 in TGR data; the method of the comprehensive index enables roads with FID of 24 and 62 in OSM data to be matched with the same-name roads in TGR data correctly.
According to the multi-index matching method based on the minimum cost network flow model, the problems of sub-optimization in an optimal matching model and frequently missed matching and mismatching of single indexes are effectively solved, real data are utilized for matching statistics, and the result shows that the method has a remarkable improving effect in the aspect of matching accuracy.
The foregoing description is only of the preferred embodiments of the present invention and is not intended to limit the scope of the present invention. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention are included in the protection scope of the present invention.
Claims (9)
1. The multi-index road network matching method based on the minimum cost network flow model is characterized by comprising the following steps of:
constructing similarity indexes between any two entities of two road data sets to be matched, wherein the entities refer to road line elements forming a road network in the road data sets;
judging potential matching pairs in two road data sets to be matched by using similarity indexes between any two entities;
each entity in the two road data sets is expressed as a node in the flow network, all potential matching pairs are expressed as a group of network edges with flow parameters, and a minimum cost network flow model is constructed;
using similarity indexes between any two entities as cost in an objective function, and performing minimum cost network flow model matching to realize multi-index road network matching;
the similarity index between any two entities is a comprehensive index formed by the distance similarity, the direction similarity and the shape similarity between any two entities according to the proportion.
2. The multi-index road network matching method based on the minimum cost network flow model according to claim 1, wherein the directional similarity between any two entities, namely road line elements, is calculated according to the following procedure:
first, the connection line between the start point coordinates and the end point coordinates of two road line elements is regarded as a vector to obtain a vectorSum vector->
Then, calculate the vectorSum vector->After the inverse cosine of the cosine absolute value of the included angle, the direction similarity D of the two road line elements is calculated according to the following formula dir ：
wherein ,to the direction ofQuantity->Sum vector->Included angle between->For vector->Sum vector->An inverse cosine of the cosine absolute value of the angle (a), a +.>Is to->Is converted from an arc value to an angle value.
3. The multi-index road network matching method based on the minimum cost network flow model according to claim 1, wherein the shape similarity between any two entities, namely road line elements, is calculated according to the following procedure:
for non-closed road line elements, a closed polygonal plane element, namely a closed curve, is formed by mirror image processing of the connection line of the head and tail points, and then any point P on the road line element (s) Can be expressed as a function of the length s of the curve from this point to the starting point as an argument:
P (s) ＝X (s) +iY (s)
wherein ,X(s) Functional expression representing abscissa of moving point on polygon, Y (s) Functional expression representing ordinate of moving point on polygon, i representing distanceAn i-th point of the start point;
the expression of the function developed by the fourier series is:
where s denotes the length of the curve from the point to the starting point being calculated, L is the circumference of a closed curve, n=0, ±1, ±2 …, the upper limit of n is the maximum order of the fourier series, and the coefficient c of the n-order fourier series n The expression of (2) is:
wherein N represents the number of nodes of a polygon, i.e., a closed curve boundary line, S i For starting point P 0 The curve length to the i-th point P of the closed curve, j is the imaginary unit, X (s) and Y(s) The expression of (2) is:
wherein ,xi Represents the i-th point P of the closed curve i Is y i Represents the i-th point P of the closed curve i Is the ordinate of S i ≤s≤S i+1 ；
Taking c n Is a modulus vector v= (|c) 1 ‖,‖c 2 ‖…‖c i ‖…‖c N II), and normalizing the vector to obtain a Fourier shape descriptor d i ：
Shape similarity D between closed curve a and closed curve b corresponding to two road line elements shape Expressed as:
in the formula ,Δshape A threshold value, d, being the maximum value of the difference between the Fourier shape descriptors of two road line elements a (i) Fourier shape descriptor, d, being the i-th point on closed curve a b (i) Is the fourier shape descriptor of the i-th point on the closed curve b.
4. The method for matching a multi-index road network based on a minimum cost network flow model according to claim 1, wherein the comprehensive index is composed of distance similarity, direction similarity and shape similarity in a ratio of 6:3:1.
5. The multi-index road network matching method based on the minimum cost network flow model according to any one of claims 1 to 4, wherein the step of determining the potential matching pair in the two road data sets to be matched by using the similarity index between any two entities is to determine whether the similarity index between the two entities is greater than a set threshold, and if so, the corresponding two entities are the potential matching pair.
6. The method for matching multi-index road networks based on the minimum cost network flow model according to any one of claims 1 to 4, wherein when constructing the minimum cost network flow model, all potential matching pairs are represented as a set of network edges with flow parameters, and two entities of each potential matching pair of two road data sets are connected by directional lines, so as to obtain a directed graph, namely a network flow model G (N ', E), wherein N ' represents a set of nodes N, and E represents a set of connecting lines between nodes, namely edges E, and the objective function of the network flow model G (N ', E) is:
Minimize∑ e∈E C e f e ；
wherein ,fe Is the flow value of each edge e, c e Is each flow value f e Is a cost of (2);
the corresponding constraint conditions are:
l e ≤f e ≤u e ,e∈I n ∪O n ,n∈N′；
wherein ,In Is the set of edges e into node n, O n Is the set of edges e going out from node n, l e Is the flow value f e Lower bound of u e Is the flow value f e Is a lower bound of (c).
7. The multi-index road network matching method based on the minimum cost network flow model according to any one of claims 1 to 4, wherein the minimum cost network flow model is a bidirectional network flow model.
8. The multi-index road network matching method based on the minimum cost network flow model according to any one of claims 1 to 4, wherein the minimum cost network flow model is built in a relational database, and the road network matching result is obtained by using a minimum cost network flow solution function, which comprises the following specific operations:
importing a minimum cost network flow resolving function and road data to be matched into a relational database, and converting the imported road data to be matched and the calculated comprehensive similarity value into fields of the following road data table:
(1) A source node corresponding to a fid of one of the two road data tables;
(2) Sink node corresponding to fid of another road data table in the two road data tables;
(3) The capacity of a flow, i.e., the upper bound of the flow value that the directed edge in the minimum cost network flow model allows to pass through;
(4) The lower limit of the flow, i.e. the lower limit of the flow value allowed by the directed edge in the minimum cost network flow model;
(5) Cost, i.e., similarity index between potential matching pairs;
(6) The value of the directed edge passing flow in the minimum cost network flow model is 1 when two entities are matched, otherwise, the value is 0;
(7) The network side, namely a column of fields formed by combining the fields (1) and (2) in the road data table, records the field of the potential matching pairs, intuitively sees all the potential matching pairs, and checks whether the input data are correct or not;
and then, operating a function calling command of the relational database, calling the imported minimum cost network flow resolving function, and performing road network matching.
9. The multi-index road network matching method based on the minimum cost network flow model according to claim 8, wherein when the imported minimum cost network flow resolving function is called to perform road network matching, the matching result is recorded by setting an external key father pointer in the relational database.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310067584.3A CN116257766B (en) | 2023-01-16 | 2023-01-16 | Multi-index road network matching method based on minimum cost network flow model |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310067584.3A CN116257766B (en) | 2023-01-16 | 2023-01-16 | Multi-index road network matching method based on minimum cost network flow model |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN116257766A CN116257766A (en) | 2023-06-13 |
| CN116257766B true CN116257766B (en) | 2023-09-19 |
Family
ID=86683664
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202310067584.3A Active CN116257766B (en) | 2023-01-16 | 2023-01-16 | Multi-index road network matching method based on minimum cost network flow model |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN116257766B (en) |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103699654A (en) * | 2013-12-26 | 2014-04-02 | 武汉大学 | Cross-measuring-scale vector map water network same name target matching method |
| CN109949692A (en) * | 2019-03-27 | 2019-06-28 | 腾讯大地通途（北京）科技有限公司 | Road network method, apparatus, computer equipment and storage medium |
| CN113988184A (en) * | 2021-10-29 | 2022-01-28 | 武汉市测绘研究院 | Vector road data matching and updating method, device and computer equipment |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7657372B2 (en) * | 2002-03-29 | 2010-02-02 | Panasonic Corporation | Map matching method, map matching device, database for shape matching, and shape matching device |
-
2023
- 2023-01-16 CN CN202310067584.3A patent/CN116257766B/en active Active
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103699654A (en) * | 2013-12-26 | 2014-04-02 | 武汉大学 | Cross-measuring-scale vector map water network same name target matching method |
| CN109949692A (en) * | 2019-03-27 | 2019-06-28 | 腾讯大地通途（北京）科技有限公司 | Road network method, apparatus, computer equipment and storage medium |
| CN113988184A (en) * | 2021-10-29 | 2022-01-28 | 武汉市测绘研究院 | Vector road data matching and updating method, device and computer equipment |
Non-Patent Citations (2)
| Title |
|---|
| A Pattern-Based Approach for Matching Nodes in Heterogeneous Urban Road Networks;Bisheng Yang等;Transactions in GIS;第18卷(第5期);第718-739页 * |
| 利用概率松弛法的城市路网自动匹配;张云菲 等;测绘学报;第41卷(第6期);第933-939页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN116257766A (en) | 2023-06-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Carnap | A basic system of inductive logic, part II | |
| CN106203491B (en) | A kind of fusion update method of highway vector data | |
| CN111210621B (en) | Signal green wave coordination route optimization control method and system based on real-time road condition | |
| CN114238542A (en) | Multi-level real-time fusion updating method for multi-source traffic GIS road network | |
| CN101930483A (en) | Method for simplifying numerical map settlement place polygon by utilizing parametric design model | |
| CN108763793A (en) | A kind of Weighted Fuzzy type D-S evidence theory frame | |
| CN105045863A (en) | Method and system used for entity matching | |
| CN105956542B (en) | High-resolution remote sensing image road extraction method based on statistical matching of structural wire harnesses | |
| CN116721001B (en) | Smart city resource management method based on digital twinning | |
| CN116720632B (en) | Engineering construction intelligent management method and system based on GIS and BIM | |
| CN103970651A (en) | Software architecture safety assessment method based on module safety attributes | |
| CN116257766B (en) | Multi-index road network matching method based on minimum cost network flow model | |
| CN106227753A (en) | The method utilizing hand-drawing map search space scene | |
| CN103646118B (en) | Confidence dominance-based rough set analysis model and attribute reduction methods | |
| Goodman | A measure-free approach to conditioning | |
| CN116561264A (en) | Knowledge graph-based intelligent question-answering system construction method | |
| CN117875533B (en) | Mining safety escape path planning method and system | |
| Liu et al. | Notice of Retraction: An Improved High-Density Sub Trajectory Clustering Algorithm | |
| Guo et al. | Combined matching approach of road networks under different scales considering constraints of cartographic generalization | |
| Xu et al. | Correlation coefficients of linguistic interval hesitant fuzzy sets and their application | |
| Devyatkov et al. | Optimal fuzzy aggregation of secondary attributes in recognition problems | |
| Yang et al. | Matching road network combining hierarchical strokes and probabilistic relaxation method | |
| CN115689921A (en) | Correction method for extracting road network topology | |
| Wu et al. | A new Voronoi diagram-based approach for matching multi-scale road networks | |
| Li | Cluster analysis based on HDWA-Kmeans algorithm assisted identification of poor students |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |