CN114626169B - Traffic network optimization method, device, equipment, readable storage medium and product - Google Patents

Abstract

The present disclosure provides a traffic network optimization method, device, equipment, readable storage medium and product, which relate to the field of data processing, especially to the field of intelligent transportation. The specific implementation scheme is: determine the road network topology map and differential operator corresponding to the target traffic road network in the target area; determine the spatial information and time series information corresponding to each road node according to the traffic element information in the preset area around each road node; divide the road network topology map into multiple local topology maps according to each road node and its corresponding associated nodes; calculate the target continuous data corresponding to the local topology map according to the spatial information, time series information, and differential operator corresponding to the road nodes and associated nodes in the local topology map; optimize the target traffic road network according to the target continuous data. It is capable of converting discrete road network data into continuous road network data, and then it is capable of performing data processing such as feature extraction based on the continuous road network data to achieve optimization operations on the traffic road network.

Description

Traffic network optimization method, device, equipment, readable storage medium and product

Technical Field

The present disclosure relates to intelligent transportation in data processing, and in particular to a transportation network optimization method, device, equipment, readable storage medium and product.

Background Art

The navigation function of map software is mainly based on the satellite positioning information of the Global Navigation Satellite System (GNSS system). However, such a solution faces two challenges: first, the high-rise buildings and viaducts in the urban environment affect the reception of satellite signals by mobile devices, resulting in the satellite positioning point being inconsistent with the actual situation; second, with the construction of urban and rural areas, the road network is changing more frequently, and the number of areas with complex road networks is gradually increasing, and the requirements for positioning accuracy are also increasing.

In order to describe the traffic network, the current processing method generally abstracts all roads in the area into one or several connected continuous vectors according to longitude and latitude and road shapes; then, at the location where the roads converge in reality, the corresponding vectors are connected to form a graph with a topological relationship; finally, according to the longitude and latitude positions, other auxiliary descriptions such as traffic lights, restricted driving and so on are added to obtain a digitized description.

However, when using the above processing method to describe the traffic network, since the roads and other traffic facilities in the digitized road network are discrete data and the data scale is huge, it is difficult to extract sufficient features in large-scale machine learning, and thus it is difficult to improve the accuracy of electronic maps and the efficiency of data processing.

Summary of the invention

The present disclosure provides a traffic network optimization method, device, equipment, readable storage medium and product for converting discrete traffic network data into continuous data.

According to a first aspect of the present disclosure, a traffic network optimization method is provided, comprising:

Determine a road network topology corresponding to a target traffic road network in a target area, and calculate a differential operator corresponding to the road network topology;

Determine spatial information and temporal information corresponding to each road node according to traffic element information in a preset area around each road node, wherein the road node is a node corresponding to a road in the road network topology map;

Dividing the road network topology map into a plurality of local topology maps according to each of the road nodes and associated nodes having a preset connection relationship with the road nodes;

For each local topological graph, according to the spatial information and time series information corresponding to the road nodes and associated nodes in the local topological graph and the differential operator, the target continuous data corresponding to the local topological graph is calculated;

The target traffic network is optimized according to the target continuous data corresponding to the multiple local topological graphs.

According to a second aspect of the present disclosure, a traffic network optimization device is provided, comprising:

A determination module, used to determine a road network topology corresponding to a target traffic road network in a target area, and calculate a differential operator corresponding to the road network topology;

A processing module, for determining spatial information and time sequence information corresponding to each road node according to traffic element information in a preset area around each road node, wherein the road node is a node corresponding to a road in the road network topology map;

A division module, used for dividing the road network topology map into a plurality of local topology maps according to each of the road nodes and associated nodes having a preset connection relationship with the road nodes;

A calculation module, for calculating, for each local topological graph, target continuous data corresponding to the local topological graph according to spatial information and time sequence information corresponding to road nodes and associated nodes in the local topological graph and the differential operator;

The optimization module is used to optimize the target traffic network according to the target continuous data corresponding to the multiple local topological graphs.

According to a third aspect of the present disclosure, there is provided an electronic device, including:

at least one processor; and

a memory communicatively connected to the at least one processor; wherein,

The memory stores instructions that can be executed by the at least one processor, and the instructions are executed by the at least one processor to enable the at least one processor to perform the method described in the first aspect.

According to a fourth aspect of the present disclosure, a non-transitory computer-readable storage medium storing computer instructions is provided, wherein the computer instructions are used to cause the computer to execute the method as described in the first aspect.

According to a fifth aspect of the present disclosure, a computer program product is provided, comprising: a computer program, wherein the computer program is stored in a readable storage medium, at least one processor of an electronic device can read the computer program from the readable storage medium, and the at least one processor executes the computer program so that the electronic device executes the method described in the first aspect.

According to the technology disclosed in the present invention, discrete road network data can be converted into continuous road network data, and then data processing such as feature extraction can be performed based on the continuous road network data to achieve optimization operations on the traffic road network.

It should be understood that the content described in this section is not intended to identify the key or important features of the embodiments of the present disclosure, nor is it intended to limit the scope of the present disclosure. Other features of the present disclosure will become easily understood through the following description.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings are used to better understand the present solution and do not constitute a limitation of the present disclosure.

FIG1 is a schematic diagram of a flow chart of a traffic network optimization method provided in Embodiment 1 of the present disclosure;

FIG2 is a schematic diagram of roads and intersections provided in an embodiment of the present disclosure;

FIG3 is a schematic diagram of the structure of a road network topology diagram provided in an embodiment of the present disclosure;

FIG4 is a schematic diagram of a flow chart of a traffic network optimization method provided in Embodiment 2 of the present disclosure;

FIG5 is a schematic diagram of a flow chart of a traffic network optimization method provided in Embodiment 3 of the present disclosure;

FIG6 is a flow chart of a traffic network optimization method provided in Embodiment 4 of the present disclosure;

FIG7 is a schematic diagram of target continuous data generation provided by an embodiment of the present disclosure;

FIG8 is a schematic diagram of the structure of a traffic network optimization device provided in Embodiment 5 of the present disclosure;

FIG9 is a schematic diagram of the structure of an electronic device provided in Embodiment 6 of the present disclosure.

DETAILED DESCRIPTION

The following is a description of exemplary embodiments of the present disclosure in conjunction with the accompanying drawings, including various details of the embodiments of the present disclosure to facilitate understanding, which should be considered as merely exemplary. Therefore, it should be recognized by those of ordinary skill in the art that various changes and modifications may be made to the embodiments described herein without departing from the scope and spirit of the present disclosure. Similarly, for the sake of clarity and conciseness, descriptions of well-known functions and structures are omitted in the following description.

With the development of economy and the progress of society, the current number of private cars in my country and the willingness of residents to travel by car are increasing year by year. Correspondingly, the greatly increased travel demand has also put forward richer and higher standards for map navigation functions. In practical applications, the navigation function of map software is mainly based on the satellite positioning information of the GNSS system. However, such a solution faces two challenges: First, the high-rise buildings and viaducts in the urban environment affect the reception of satellite signals by mobile devices, resulting in the satellite positioning point not being consistent with the actual situation; second, with the construction of urban and rural areas, the changes in the road network are becoming more and more frequent, and the areas with complex road networks are gradually increasing, and the requirements for positioning accuracy are also increasing.

In the prior art, when describing a traffic network, all roads in the area are generally abstracted into one or several connected continuous vectors according to longitude and latitude and road shape; then, at the location where the roads converge in reality, the corresponding vectors are connected to form a graph with a topological relationship; finally, according to the longitude and latitude positions, other auxiliary descriptions such as traffic lights and restricted driving are added to obtain a digitized description of the traffic network. However, when the above method is used to describe the traffic network, since the roads and other traffic facilities in the digitized network are all discrete data, the data scale is huge. Therefore, it is difficult to extract enough features in large-scale machine learning, and accordingly, it increases the difficulty of adapting personalized navigation strategies to local conditions.

In the process of solving the above technical problems, the inventors found through research that in order to realize the extraction operation of road network data features in large-scale machine learning, the discrete data can be converted into continuous data. Specifically, the road network topology corresponding to the target traffic road network in the target area can be determined, and the differential operator corresponding to the road network topology can be calculated. The spatial information and time series information corresponding to each road node are calculated respectively, and the road network topology is divided to obtain multiple local topology maps. Therefore, for each local topology map, the target continuous data can be calculated based on the spatial information and time series information and the differential operator.

The present disclosure provides a traffic network optimization method, device, equipment, readable storage medium and product, which are applied to intelligent transportation in data processing, can convert discrete data into continuous data, and then can perform feature extraction and subsequent road network optimization operations based on the continuous data.

FIG1 is a flow chart of a traffic network optimization method provided in Embodiment 1 of the present disclosure. As shown in FIG1 , the method includes:

Step 101: determine a road network topology map corresponding to a target traffic road network in a target area, and calculate a differential operator corresponding to the road network topology map.

The execution subject of this embodiment is a traffic network optimization device, which can be coupled to a server, and the server can be connected to the terminal device and the database for communication.

In this embodiment, in order to realize the optimization operation of the traffic road network of the target area, the technician can send an optimization request through the terminal device, wherein the optimization request can include the identification information of the target area. Accordingly, the traffic road network optimization device can determine the road network topology map corresponding to the target traffic road network of the target area according to the identification information of the target area, wherein the road network topology map includes the topological relationship composed of roads and intersections. Furthermore, the differential operator corresponding to the road network topology map can be calculated, so that the continuous processing of discrete data can be realized based on the differential operator later.

Step 102: Determine the spatial information and time sequence information corresponding to each road node according to the traffic element information in the preset area around each road node, wherein the road node is a node corresponding to the road in the road network topology map.

In this embodiment, for each road node in the road network topology map, the spatial information and time series information corresponding to the road node can be obtained based on the traffic element information in the preset area around the road node, wherein the road node is the node corresponding to the road in the road network topology map.

Optionally, the traffic element information includes but is not limited to the road network shape and traffic setting location information in the preset area around the road node, so that the spatial information corresponding to the road node can be calculated based on the traffic element information. The traffic element information includes but is not limited to the trajectory information in the preset area around the road node, and the time series information in the preset area around the road node can be calculated based on the trajectory information.

Step 103: Divide the road network topology map into a plurality of local topology maps according to each of the road nodes and associated nodes having a preset connection relationship with the road nodes.

In this embodiment, for each road node in the road network topology, the associated nodes in the road network topology that have the above-mentioned preset connection relationship with the road node can be determined according to the preset connection relationship, and the road node and the associated nodes corresponding to the road node are determined as a local topology map. Thus, the road network topology map can be divided into multiple local topology maps. Among them, the preset connection relationship can be the number of edges between the road node and the associated node. For example, the preset connection relationship can be to determine the node that has two edges with the road node as the associated node.

Step 104: For each local topology map, the target continuous data corresponding to the local topology map is calculated according to the spatial information and time series information corresponding to the road nodes and associated nodes in the local topology map and the differential operator.

In this embodiment, after dividing the road network topology map into at least one local topology map, for each local topology map, the local road network discretized data corresponding to the local topology map can be processed continuously based on the spatial information and time series information corresponding to the road nodes and spatial nodes in the local topology map and the differential operator corresponding to the road network topology map to obtain the target continuous data corresponding to the local topology map.

Step 105: Optimize the target traffic network according to the target continuous data corresponding to the multiple local topological maps.

In this embodiment, after the calculation of the target continuous data corresponding to all the local topological maps is completed, the continuous data corresponding to the road network topological map can be obtained. By converting the discretized road network data into continuous data, the feature extraction operation can be performed based on the continuous data. Therefore, the target traffic road network can be optimized according to the target continuous data corresponding to the multiple local topological maps.

The traffic network optimization method provided in this embodiment determines the road network topology corresponding to the target traffic road network in the target area and calculates the differential operator corresponding to the road network topology. The spatial information and time series information corresponding to each road node are calculated respectively, and the road network topology is divided to obtain multiple local topology maps. Therefore, for each local topology map, the target continuous data can be calculated based on the spatial information, time series information, and the differential operator. Therefore, the feature extraction operation can be performed based on the continuous data, and the target continuous data can be processed differently based on different business needs.

Further, based on the first embodiment, step 101 includes:

Get the target traffic road network corresponding to the target area.

According to the roads and intersections in the target traffic network, a road network topology map corresponding to the target traffic network is determined.

In this embodiment, after determining the target area to be processed, the target traffic road network corresponding to the target area can be obtained, and the target traffic road network includes multiple roads and intersections between the roads. Therefore, according to the roads and intersections in the target traffic road network, the road network topology corresponding to the target traffic road network can be determined, and the road network topology includes the topological relationship composed of roads and intersections.

FIG. 2 is a schematic diagram of roads and intersections provided in an embodiment of the present disclosure. As shown in FIG. 2 , there is an intersection 23 between a road 21 and a road 22 .

The traffic network optimization method provided in this embodiment determines the road network topology map corresponding to the target traffic network according to the roads and intersections in the target traffic network, so that the discrete data can be converted into continuous data based on the road network topology map.

Further, based on the first embodiment, the step of determining a road network topology map corresponding to the target traffic road network according to the roads and intersections in the target traffic road network includes:

The roads in the target traffic network are regarded as road nodes, and the intersection points between any two roads are regarded as edges.

A road network topology map corresponding to the target traffic road network is generated according to the road nodes and edges.

In this embodiment, for each road in the target traffic network, the road can be determined as a road node, and the intersection between any two roads can be used as the edge between the two road nodes. Based on the road nodes and the edges between the road nodes, the topological relationship between the roads and the intersections is determined, and a road network topology map corresponding to the target traffic network is generated.

FIG3 is a schematic diagram of the structure of a road network topology diagram provided by an embodiment of the present disclosure. As shown in FIG3 , a road may be used as a road node 31 , and an intersection point between any two road nodes 31 may be used as an edge 32 .

The traffic network optimization method provided in this embodiment determines the road as a road node and the intersection between any two roads to generate a road network topology map corresponding to the target traffic network. Thus, the road network topology map can accurately express the topological relationship between the roads and the intersections, thereby improving the accuracy of subsequent data processing.

Further, based on the first embodiment, step 105 includes:

A road network optimization request is obtained, wherein the road network optimization request includes optimization requirements.

According to the road network optimization request, a network model corresponding to the optimization requirement is used to process the target continuous data corresponding to the multiple local topology maps.

In this embodiment, after the target continuous data is generated according to the target traffic network, a feature extraction operation can be performed based on the target continuous data, and then the target continuous data can be processed differently based on different business needs. Specifically, the user can initiate a road network optimization request according to different business needs. Accordingly, the traffic network optimization device can obtain the road network optimization request, wherein the road network optimization request includes the optimization requirement. According to the optimization request, the target continuous data corresponding to the multiple local topology maps are processed using a network model corresponding to the optimization requirement.

For example, business requirements include but are not limited to trajectory matching, traffic prediction, and positioning drift area identification. If the current business requirement is to predict traffic conditions, the target continuous data corresponding to the multiple local topological maps can be input into a preset traffic prediction model for prediction operations. Alternatively, the target continuous data corresponding to the multiple local topological maps can be input into a preset trajectory matching model for trajectory matching operations.

The traffic network optimization method provided in this embodiment can improve the applicability of the target continuous data and make it suitable for various scenarios by inputting the target continuous data corresponding to multiple local topology maps into different network models for data processing according to different business needs.

Further, based on the first embodiment, after step 104, the following steps are further included:

A preset clustering algorithm is used to perform a clustering operation on the target continuous data corresponding to the local topological map.

In practical applications, there are large differences between traffic elements in different regions, but after the discrete road network data is processed continuously, reduced in dimension, and expressed abstractly, it may have the same continuous data. Therefore, in order to improve the efficiency of subsequent processing of road network data, reduce data redundancy, and avoid repeated processing, after completing the processing of the target continuous data corresponding to the local topology map, a preset clustering algorithm can be used to perform clustering operations on the target continuous data corresponding to the local topology map. Among them, the preset clustering algorithm can specifically be a K-means algorithm. Alternatively, it can be any clustering algorithm, and the present disclosure does not limit this.

The traffic network optimization method provided in this embodiment can reduce data redundancy and improve the processing efficiency of subsequent road network data by clustering the target continuous data corresponding to the local topology map.

FIG4 is a flow chart of a traffic network optimization method provided in the second embodiment of the present disclosure. The differential operator is a Laplace operator. Based on the first embodiment, as shown in FIG4 , step 101 includes:

Step 401: for each road node in the road network topology graph, determine the number of edges pointing to the road node, and determine the number of edges as the in-degree of the road node.

Step 402: Generate an in-degree matrix corresponding to the road network topology graph according to the in-degrees of all road nodes in the road network topology graph.

Step 403: for each edge in the road network topology graph, determine the traffic flow and/or importance of the intersection corresponding to the edge, and determine the weight of the edge according to the traffic flow and/or importance.

Step 404: Generate a weight matrix corresponding to the road network topology graph according to the weights corresponding to all the edges in the road network topology graph.

Step 405: Calculate the Laplace matrix corresponding to the road network topology graph according to the in-degree matrix and the weight matrix.

In this embodiment, the differential operator may be a Laplace operator. In order to calculate the Laplace operator, it is first necessary to calculate the in-degree matrix and the weight matrix corresponding to the road network topology. The in-degree may be the number of edges pointing to the road node, and the weight may be the flow and importance of the road.

Specifically, for each road node in the road network topology graph, determine the number of edges pointing to the road node, and determine the number of edges as the in-degree of the road node. For example, a road node corresponds to two edges, that is, the road corresponds to two intersections, and it can be determined that the in-degree corresponding to the road node is 2. According to the in-degrees of all road nodes in the road network topology graph, the in-degree matrix corresponding to the road network topology graph is generated. According to the weights corresponding to all edges in the road network topology graph, the weight matrix corresponding to the road network topology graph is generated. The Laplace matrix corresponding to the road network topology graph is calculated based on the in-degree matrix and the weight matrix. After obtaining the in-degree matrix and the weight matrix, the Laplace matrix corresponding to the road network topology graph can be determined by matrix calculation of the in-degree matrix and the weight matrix.

The traffic network optimization method provided in this embodiment calculates the in-degree matrix and the weight matrix corresponding to the road network topology map, so that the Laplace matrix corresponding to the road network topology map can be accurately determined through matrix calculation of the in-degree matrix and the weight matrix, thereby providing a basis for subsequent data processing.

Further, based on any of the above embodiments, step 405 includes:

Matrix subtraction is performed on the in-degree matrix and the weight matrix to obtain a Laplace matrix corresponding to the road network topology graph.

In this embodiment, after obtaining the in-degree matrix D and the weight matrix W, a matrix subtraction operation can be performed on the in-degree matrix and the weight matrix to obtain the Laplace matrix L corresponding to the road network topology graph. Specifically, the calculation of the Laplace matrix L can be implemented by the formula L=D-W.

The traffic network optimization method provided in this embodiment can accurately calculate the Laplace matrix corresponding to the road network topology map by performing matrix subtraction operations on the in-degree matrix and the weight matrix, thereby providing a basis for subsequent data processing.

FIG5 is a flow chart of a traffic network optimization method provided in Embodiment 3 of the present disclosure. Based on any of the above embodiments, as shown in FIG5 , step 103 includes:

Step 501: Obtain a road network division request, wherein the road network division request includes the preset connection relationship, and the preset connection relationship includes the number of edges between the associated node and the road node.

Step 502: According to the road network division request, for each road node, determine in the road network topology map an associated node that has a preset connection relationship with the road node.

Step 503: For each road node, determine the road node and the associated nodes corresponding to the road node as the local topology graph.

In this embodiment, the preset relationship may specifically be the number of edges between the associated node and the road node. Therefore, the traffic network optimization may obtain a road network division request, wherein the road network division request includes the number of edges between the associated node and the road node.

According to the road network division request, for each road node, an associated node that meets a preset connection relationship with the road node is determined in the road network topology map. For example, the preset connection relationship may be to determine a node that has two edges with the road node as an associated node. For each road node, the road node and the associated nodes corresponding to the road node are determined as a local topology map, so that the network topology map can be divided into multiple local topology maps.

The preset connection relationship can be switched according to different requirements, and the present disclosure does not impose any limitation on this.

The traffic network optimization method provided in this embodiment obtains a road network division request, and according to the road network division request, determines, for each road node, an associated node that has a preset connection relationship with the road node in the road network topology map, so that different division operations can be performed on the network topology structure according to different business needs, and is suitable for different application scenarios.

Further, based on any of the above embodiments, the traffic element information includes the road network structure, traffic facilities and trajectory information in a preset area around the road node; step 102 includes:

The road network structure and traffic facilities in a preset area around the road node are determined as the spatial information corresponding to the road node.

The trajectory information in a preset area around the road node is obtained at a preset time interval, and the trajectory information is plotted on the road network topology map in chronological order to obtain the timing information corresponding to the road node.

In this embodiment, the traffic element information may specifically include the road network structure, traffic facilities and trajectory information in the preset area around the road node. For each road node, the road network structure and traffic facilities in the preset area around the road node may be determined as the spatial information corresponding to the road node. The spatial information is generally static information corresponding to the road node, which can characterize whether the road network around the road is complex and can distinguish different roads. For example, the road network around the main road is more complex, while the road network around the suburban road is simpler.

For each road node, the trajectory information in the preset area around the road node can be obtained at a preset time interval, and the trajectory information can be plotted on the road network topology map in chronological order to obtain the time series information corresponding to the road node. The time series information is generally dynamic information corresponding to the road node, which can characterize the behavior of vehicles in the preset area around the road, such as whether the traffic volume in the preset area around the road is relatively large.

The traffic network optimization method provided in this embodiment can accurately determine the static information and dynamic information corresponding to the road nodes by respectively determining the spatial information and temporal information corresponding to the road nodes according to the traffic element information, thereby providing a basis for the subsequent processing of the road network data.

FIG6 is a flow chart of a traffic network optimization method provided in a fourth embodiment of the present disclosure. Based on any of the above embodiments, as shown in FIG6 , step 104 includes:

Step 601: For each local topology graph, calculate the spatial continuous data corresponding to the local topology graph according to the spatial information corresponding to the road nodes and associated nodes in the local topology graph and the differential operator.

Step 602: For each local topology graph, calculate the time series continuous data corresponding to the local topology graph according to the time series information corresponding to the road nodes and associated nodes in the local topology graph and the differential operator.

Step 603: Calculate target continuous data corresponding to the local topology map according to the spatial continuous data and the temporal continuous data.

In this embodiment, after the spatial information and the temporal information corresponding to the road nodes are respectively determined, the spatial continuous data and the temporal continuous data can be calculated based on the spatial information and the temporal information respectively.

Specifically, for each local topology map, the spatial continuous data corresponding to the local topology map is calculated according to the spatial information and Laplace operator corresponding to the road nodes and associated nodes in the local topology map. For each local topology map, the temporal continuous data corresponding to the local topology map is calculated according to the temporal information and Laplace operator corresponding to the road nodes and associated nodes in the local topology map. Then, the target continuous data corresponding to the local topology map can be calculated according to the spatial continuous data and the temporal continuous data.

The traffic network optimization method provided in this embodiment realizes the calculation of spatial continuous data and temporal continuous data based on spatial information and temporal information respectively, thereby being able to convert discretized data into target continuous data, and further realizing feature extraction operations on traffic network data.

Further, based on any of the above embodiments, step 603 includes:

The spatially continuous data and the temporally continuous data are adjusted according to a preset data format to obtain the spatially continuous data and the temporally continuous data having the same data format.

A data fusion operation is performed on the spatial continuous data and the temporal continuous data having the same data format to obtain fused continuous data.

The target continuous data is determined according to the fused continuous data.

In this embodiment, since there may be differences in data formats between spatial continuous data and temporal continuous data, data calculation cannot be performed directly. Therefore, in order to realize operations such as data fusion of spatial continuous data and temporal continuous data, a data format can be pre-set, and the spatial continuous data and temporal continuous data can be adjusted according to the preset data format to obtain spatial continuous data and temporal continuous data with the same data format. Specifically, a spatial convolutional neural network model and a temporal convolutional neural network model can be set respectively, and the spatial continuous data can be adjusted according to the preset data format by the spatial convolutional neural network model, and the temporal continuous data can be adjusted according to the preset data format by the temporal convolutional neural network model, so as to obtain spatial continuous data and temporal continuous data with the same data format.

When the spatial continuous data and the temporal continuous data have the same data format, they can be fused and the target continuous data can be determined based on the fused continuous data.

FIG7 is a schematic diagram of target continuous data generation provided by an embodiment of the present disclosure. As shown in FIG7 , the spatial continuous data 72 can be adjusted according to a preset data format by a preset spatial convolutional neural network model 71, and the temporal continuous data 74 can be adjusted according to a preset data format by a preset temporal convolutional neural network model 73. Spatial continuous data and temporal continuous data with the same data format are obtained. Data fusion operation is performed on the spatial continuous data and temporal continuous data with the same data format to obtain fused continuous data 75.

The traffic network optimization method provided in this embodiment obtains spatial continuous data and temporal continuous data with the same data format by adjusting the spatial continuous data and temporal continuous data respectively according to the preset data format, thereby realizing the format adjustment operation of the spatial continuous data and the temporal continuous data, and further realizing the data fusion operation of the spatial continuous data and the temporal continuous data to obtain the fused continuous data.

Further, based on any of the above embodiments, after step 101, the method further includes:

For each road in the target traffic network, attribute information corresponding to the road is obtained, wherein the attribute information includes one or more of the width, length, number of lanes, functional level, and traffic conditions of the road.

The road feature vector corresponding to the target traffic road network is determined according to the attribute information corresponding to each road.

The determining the target continuous data according to the fused continuous data includes:

A data splicing operation is performed on the fused continuous data and the road feature vector to obtain the target continuous data.

In this embodiment, after completing the data fusion operation of spatial continuous data and temporal continuous data, the fused continuous data can be further spliced with the attribute information corresponding to the road. Specifically, for each road in the target traffic network, the attribute information corresponding to the road is obtained, wherein the attribute information includes one or more of the width, length, number of lanes, functional level, and traffic conditions of the road. The fused continuous data and the road feature vector are spliced to obtain the target continuous data. In this way, the static, dynamic information and attribute information of the road nodes can be comprehensively considered to improve the comprehensiveness and accuracy of the generated target continuous data.

FIG8 is a schematic diagram of the structure of a traffic network optimization device provided in the fifth embodiment of the present disclosure. As shown in FIG8, the device includes: a determination module 81, a processing module 82, a division module 83, a calculation module 84, and an optimization module 85. Among them, the determination module 81 is used to determine the road network topology map corresponding to the target traffic road network in the target area, and calculate the differential operator corresponding to the road network topology map. The processing module 82 is used to determine the spatial information and time sequence information corresponding to each road node according to the traffic element information in the preset area around each road node. The road node is a node corresponding to the road in the road network topology map. The division module 83 is used to divide the road network topology map into multiple local topology maps according to each road node and the associated node having a preset connection relationship with the road node. The calculation module 84 is used to calculate the target continuous data corresponding to the local topology map according to the spatial information and time sequence information corresponding to the road node and the associated node in the local topology map and the differential operator for each local topology map. The optimization module 85 is used to optimize the target traffic road network according to the target continuous data corresponding to the multiple local topology maps.

Further, based on the fifth embodiment, the determination module includes: a road network acquisition unit and a topology map determination unit. The road network acquisition unit is used to acquire the target traffic road network corresponding to the target area. The topology map determination unit is used to determine the road network topology map corresponding to the target traffic road network according to the roads and intersections in the target traffic road network.

Further, based on the fifth embodiment, the topology map determining unit includes: a conversion subunit and a generation subunit, wherein the conversion subunit is used to use roads in the target traffic road network as road nodes and the intersection between any two roads as edges. The generation subunit is used to generate a road network topology map corresponding to the target traffic road network according to the road nodes and edges.

Further, based on the fifth embodiment, the optimization module includes: a request acquisition unit and an optimization unit. The request acquisition unit is used to acquire a road network optimization request, wherein the road network optimization request includes an optimization requirement, and the optimization unit is used to process the target continuous data corresponding to the multiple local topology graphs according to the road network optimization request using a network model corresponding to the optimization requirement.

Furthermore, based on the fifth embodiment, the device further includes: a clustering module, which is used to perform clustering operations on the target continuous data corresponding to the local topology map using a preset clustering algorithm.

Further, on the basis of the fifth embodiment, the differential operator is a Laplace operator, and the determination module includes: an in-degree determination unit, an in-degree matrix generation unit, a weight determination unit, a weight matrix generation unit, and a matrix calculation unit. Among them, the in-degree determination unit is used to determine the number of edges pointing to each road node in the road network topology map, and determine the number of edges as the in-degree of the road node. The in-degree matrix generation unit is used to generate the in-degree matrix corresponding to the road network topology map according to the in-degrees of all road nodes in the road network topology map. The weight determination unit is used to determine the traffic flow and/or importance of the intersection corresponding to each edge in the road network topology map, and determine the weight of the edge according to the traffic flow and/or importance. The weight matrix generation unit is used to generate the weight matrix corresponding to the road network topology map according to the weights corresponding to all edges in the road network topology map. The matrix calculation unit is used to calculate the Laplace matrix corresponding to the road network topology map according to the in-degree matrix and the weight matrix.

Further, based on any of the above embodiments, the matrix calculation unit includes: a matrix processing subunit, which is used to perform matrix subtraction on the in-degree matrix and the weight matrix to obtain a Laplace matrix corresponding to the road network topology graph.

Further, based on any of the above embodiments, the division module includes: an acquisition unit, a node determination unit and a local topology map unit. The acquisition unit is used to obtain a road network division request, wherein the road network division request includes the preset connection relationship, and the preset connection relationship includes the number of edges between the associated node and the road node. The node determination unit is used to determine, for each road node, the associated node that meets the preset connection relationship with the road node in the road network topology map according to the road network division request. The local topology map unit is used to determine, for each road node, the road node and the associated node corresponding to the road node as the local topology map.

Further, on the basis of any of the above embodiments, the traffic element information includes the road network structure, traffic facilities and trajectory information in the preset area around the road node; the processing module includes: a spatial information determination unit and a time sequence information determination unit. The spatial information determination unit is used to determine the road network structure and traffic facilities in the preset area around the road node as the spatial information corresponding to the road node. The time sequence information determination unit is used to obtain the trajectory information in the preset area around the road node at a preset time interval, draw the trajectory information on the road network topology map in time sequence, and obtain the time sequence information corresponding to the road node.

Further, based on any of the above embodiments, the calculation module includes: a spatial continuous data calculation unit, a temporal continuous data calculation unit and a temporal continuous data calculation unit. The spatial continuous data calculation unit is used to calculate, for each local topology map, the spatial continuous data corresponding to the local topology map according to the spatial information corresponding to the road nodes and associated nodes in the local topology map and the differential operator. The temporal continuous data calculation unit is used to calculate, for each local topology map, the temporal continuous data corresponding to the local topology map according to the temporal information corresponding to the road nodes and associated nodes in the local topology map and the differential operator. The temporal continuous data calculation unit is used to calculate the target continuous data corresponding to the local topology map according to the spatial continuous data and the temporal continuous data.

Further, based on any of the above embodiments, the time series continuous data calculation unit includes: an adjustment subunit, a fusion subunit and a determination subunit. Among them, the adjustment subunit is used to perform adjustment operations on the spatial continuous data and the time series continuous data respectively according to a preset data format to obtain the spatial continuous data and the time series continuous data with the same data format. The fusion subunit is used to perform data fusion operations on the spatial continuous data and the time series continuous data with the same data format to obtain fused continuous data. The determination subunit is used to determine the target continuous data based on the fused continuous data.

Furthermore, on the basis of any of the above embodiments, the device further includes: an attribute information determination module and a vector determination module. The attribute information determination module is used to obtain the attribute information corresponding to each road in the target traffic network, wherein the attribute information includes one or more of the width, length, number of lanes, functional level, and traffic conditions of the road. The vector determination module is used to determine the road feature vector corresponding to the target traffic network according to the attribute information corresponding to each road. The determination subunit is used to perform data splicing operations on the fused continuous data and the road feature vector to obtain the target continuous data.

According to an embodiment of the present disclosure, the present disclosure also provides an electronic device, a readable storage medium, and a computer program product.

According to an embodiment of the present disclosure, the present disclosure also provides a computer program product, which includes: a computer program, the computer program is stored in a readable storage medium, at least one processor of an electronic device can read the computer program from the readable storage medium, and at least one processor executes the computer program so that the electronic device executes the solution provided by any of the above embodiments.

FIG9 is a schematic diagram of the structure of an electronic device provided in Embodiment 6 of the present disclosure. The electronic device is intended to represent various forms of digital computers, such as laptop computers, desktop computers, workstations, personal digital assistants, servers, blade servers, mainframe computers, and other suitable computers. The electronic device may also represent various forms of mobile devices, such as personal digital processing, cellular phones, smart phones, wearable devices, and other similar computing devices. The components shown herein, their connections and relationships, and their functions are merely examples and are not intended to limit the implementation of the present disclosure described and/or required herein.

As shown in Figure 9, the device 900 includes a computing unit 901, which can perform various appropriate actions and processes according to a computer program stored in a read-only memory (ROM) 902 or a computer program loaded from a storage unit 908 into a random access memory (RAM) 903. In the RAM 903, various programs and data required for the operation of the device 900 can also be stored. The computing unit 901, the ROM 902, and the RAM 903 are connected to each other via a bus 904. An input/output (I/O) interface 905 is also connected to the bus 904.

A number of components in the device 900 are connected to the I/O interface 905, including: an input unit 906, such as a keyboard, a mouse, etc.; an output unit 907, such as various types of displays, speakers, etc.; a storage unit 908, such as a disk, an optical disk, etc.; and a communication unit 909, such as a network card, a modem, a wireless communication transceiver, etc. The communication unit 909 allows the device 900 to exchange information/data with other devices through a computer network such as the Internet and/or various telecommunication networks.

The computing unit 901 may be a variety of general and/or special processing components with processing and computing capabilities. Some examples of the computing unit 901 include, but are not limited to, a central processing unit (CPU), a graphics processing unit (GPU), various dedicated artificial intelligence (AI) computing chips, various computing units running machine learning model algorithms, digital signal processors (DSPs), and any appropriate processors, controllers, microcontrollers, etc. The computing unit 901 performs the various methods and processes described above, such as the traffic network optimization method. For example, in some embodiments, the traffic network optimization method may be implemented as a computer software program, which is tangibly contained in a machine-readable medium, such as a storage unit 908. In some embodiments, part or all of the computer program may be loaded and/or installed on the device 900 via the ROM 902 and/or the communication unit 909. When the computer program is loaded into the RAM 903 and executed by the computing unit 901, one or more steps of the traffic network optimization method described above may be performed. Alternatively, in other embodiments, the computing unit 901 may be configured to perform the traffic network optimization method in any other appropriate manner (e.g., by means of firmware).

Various implementations of the systems and techniques described above herein can be implemented in digital electronic circuit systems, integrated circuit systems, field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), application specific standard products (ASSPs), systems on chips (SOCs), complex programmable logic devices (CPLDs), computer hardware, firmware, software, and/or combinations thereof. These various implementations can include: being implemented in one or more computer programs that can be executed and/or interpreted on a programmable system including at least one programmable processor, which can be a special purpose or general purpose programmable processor that can receive data and instructions from a storage system, at least one input device, and at least one output device, and transmit data and instructions to the storage system, the at least one input device, and the at least one output device.

The program code for implementing the method of the present disclosure may be written in any combination of one or more programming languages. These program codes may be provided to a processor or controller of a general-purpose computer, a special-purpose computer, or other programmable data processing device, so that the program code, when executed by the processor or controller, implements the functions/operations specified in the flow chart and/or block diagram. The program code may be executed entirely on the machine, partially on the machine, partially on the machine and partially on a remote machine as a stand-alone software package, or entirely on a remote machine or server.

In the context of the present disclosure, a machine-readable medium may be a tangible medium that may contain or store a program for use by or in conjunction with an instruction execution system, device, or equipment. A machine-readable medium may be a machine-readable signal medium or a machine-readable storage medium. A machine-readable medium may include, but is not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, device, or equipment, or any suitable combination of the foregoing. A more specific example of a machine-readable storage medium may include an electrical connection based on one or more lines, a portable computer disk, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), an optical fiber, a portable compact disk read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing.

To provide interaction with a user, the systems and techniques described herein can be implemented on a computer having: a display device (e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor) for displaying information to the user; and a keyboard and pointing device (e.g., a mouse or trackball) through which the user can provide input to the computer. Other types of devices can also be used to provide interaction with the user; for example, the feedback provided to the user can be any form of sensory feedback (e.g., visual feedback, auditory feedback, or tactile feedback); and input from the user can be received in any form (including acoustic input, voice input, or tactile input).

The systems and techniques described herein may be implemented in a computing system that includes back-end components (e.g., as a data server), or a computing system that includes middleware components (e.g., an application server), or a computing system that includes front-end components (e.g., a user computer with a graphical user interface or a web browser through which a user can interact with implementations of the systems and techniques described herein), or a computing system that includes any combination of such back-end components, middleware components, or front-end components. The components of the system may be interconnected by any form or medium of digital data communication (e.g., a communications network). Examples of communications networks include: a local area network (LAN), a wide area network (WAN), and the Internet.

A computer system may include a client and a server. The client and the server are generally remote from each other and usually interact through a communication network. The relationship between the client and the server is generated by computer programs running on the corresponding computers and having a client-server relationship with each other. The server may be a cloud server, also known as a cloud computing server or cloud host, which is a host product in the cloud computing service system to solve the defects of difficult management and weak business scalability in traditional physical hosts and VPS services ("Virtual Private Server", or "VPS" for short). The server may also be a server of a distributed system, or a server combined with a blockchain.

It should be understood that the various forms of processes shown above can be used to reorder, add or delete steps. For example, the steps recorded in this disclosure can be executed in parallel, sequentially or in different orders, as long as the desired results of the technical solutions disclosed in this disclosure can be achieved, and this document does not limit this.

The above specific implementations do not constitute a limitation on the protection scope of the present disclosure. It should be understood by those skilled in the art that various modifications, combinations, sub-combinations and substitutions can be made according to design requirements and other factors. Any modification, equivalent substitution and improvement made within the spirit and principle of the present disclosure shall be included in the protection scope of the present disclosure.

Claims (21)

1. A traffic road network optimization method, comprising:

Determining a road network topological graph corresponding to a target traffic road network in a target area, and calculating a differential operator corresponding to the road network topological graph;

Determining space information and time sequence information corresponding to each road node according to traffic element information in a preset area around each road node, wherein the road node is a node corresponding to a road in the road network topological graph;

Dividing the road network topology map into a plurality of local topology maps according to each road node and the associated node with a preset connection relation with the road node;

aiming at each local topological graph, calculating target continuous data corresponding to the local topological graph according to space information and time sequence information corresponding to road nodes and associated nodes in the local topological graph and the differential operator;

Optimizing the target traffic network according to the target continuous data corresponding to the plurality of local topological graphs;

the determining the road network topology map corresponding to the target traffic road network in the target area comprises the following steps:

acquiring a target traffic network corresponding to a target area;

taking a road in a target traffic road network as a road node and taking a junction point between any two roads as an edge; generating a road network topological graph corresponding to the target traffic road network according to the road nodes and edges;

the differential operator is a laplace operator, and the calculating the differential operator corresponding to the road network topological graph includes:

Determining the number of edges pointing to the road nodes for each road node in the road network topological graph, and determining the number of the edges as the degree of entrance of the road nodes; generating an entry matrix corresponding to the road network topological graph according to the entries of all road nodes in the road network topological graph;

Determining traffic flow and/or importance of a junction corresponding to each edge in the road network topological graph, and determining the weight of the edge according to the traffic flow and/or importance; generating a weight matrix corresponding to the road network topological graph according to weights corresponding to all edges in the road network topological graph;

and calculating a Laplacian matrix corresponding to the road network topological graph according to the degree matrix and the weight matrix.

2. The method of claim 1, wherein the calculating the laplace matrix corresponding to the road network topology according to the occupancy matrix and the weight matrix comprises:

And performing matrix subtraction on the input degree matrix and the weight matrix to obtain a Laplacian matrix corresponding to the road network topological graph.

3. The method according to claim 1 or 2, wherein the dividing the road network topology map into a plurality of local topology maps according to each of the road nodes and associated nodes having a preset connection relationship with the road nodes comprises:

obtaining a road network division request, wherein the road network division request comprises the preset connection relation, and the preset connection relation comprises the number of edges between the association node and the road node;

determining associated nodes which accord with a preset connection relation with the road nodes in the road network topological graph aiming at each road node according to the road network division request;

and determining the road nodes and the associated nodes corresponding to the road nodes as the local topological graph for each road node.

4. The method according to claim 1 or 2, wherein the traffic element information includes road network structure, traffic facilities, and trajectory information within a preset area around the road node;

The determining the spatial information and the time sequence information corresponding to each road node according to the traffic element information in the preset area around each road node comprises the following steps:

Determining a road network structure and traffic facilities in a preset area around the road node as space information corresponding to the road node;

And acquiring track information in a preset area around the road node according to a preset time interval, and drawing the track information on the road network topological graph according to a time sequence to acquire time sequence information corresponding to the road node.

5. The method according to claim 1 or 2, wherein for each local topological graph, calculating the target continuous data corresponding to the local topological graph according to the spatial information and the time-sequence information corresponding to the road nodes and the associated nodes in the local topological graph and the differential operator, comprises:

For each local topological graph, calculating the space continuous data corresponding to the local topological graph according to the space information corresponding to the road nodes and the associated nodes in the local topological graph and the differential operator;

for each local topological graph, calculating time sequence continuous data corresponding to the local topological graph according to time sequence information corresponding to road nodes and associated nodes in the local topological graph and the differential operator;

And calculating target continuous data corresponding to the local topological graph according to the space continuous data and the time sequence continuous data.

6. The method of claim 5, wherein the calculating the target continuous data corresponding to the local topological graph according to the spatially continuous data and the time-series continuous data comprises:

Respectively adjusting the space continuous data and the time sequence continuous data according to a preset data format to obtain the space continuous data and the time sequence continuous data with the same data format;

Performing data fusion operation on the space continuous data and the time sequence continuous data with the same data format to obtain fused continuous data;

And determining the target continuous data according to the fused continuous data.

7. The method of claim 6, further comprising, after the determining the road network topology map corresponding to the target traffic road network in the target area:

Acquiring attribute information corresponding to each road in the target traffic road network, wherein the attribute information comprises one or more of width, length, lane number, function level and traffic condition of the road;

Determining a road feature vector corresponding to the target traffic road network according to the attribute information corresponding to each road;

the determining the target continuous data according to the fused continuous data comprises the following steps:

and performing data splicing operation on the fused continuous data and the road feature vector to obtain the target continuous data.

8. The method according to any one of claims 1-2 and 6-7, wherein the optimizing the target traffic network according to the target continuous data corresponding to the plurality of local topological graphs includes:

Obtaining a road network optimization request, wherein the road network optimization request comprises an optimization requirement;

and according to the road network optimization request, adopting a network model corresponding to the optimization requirement to process the target continuous data corresponding to the plurality of partial topological graphs.

9. The method according to any one of claims 1-2 and 6-7, further comprising, after calculating the target continuous data corresponding to the local topology map:

And clustering the continuous target data corresponding to the local topological graph by adopting a preset clustering algorithm.

10. A traffic road network optimization device, comprising:

the determining module is used for determining a road network topological graph corresponding to the target traffic road network in the target area and calculating a differential operator corresponding to the road network topological graph;

The processing module is used for determining space information and time sequence information corresponding to each road node according to traffic element information in a preset area around each road node, wherein the road nodes are nodes corresponding to roads in the road network topological graph;

The dividing module is used for dividing the road network topological graph into a plurality of partial topological graphs according to each road node and the associated node which has a preset connection relation with the road node;

The calculation module is used for calculating target continuous data corresponding to each local topological graph according to the space information and the time sequence information corresponding to the road nodes and the associated nodes in the local topological graph and the differential operator;

the optimization module is used for performing optimization operation on the target traffic network according to the target continuous data corresponding to the plurality of partial topological graphs;

Wherein the determining module comprises:

the road network acquisition unit is used for acquiring a target traffic road network corresponding to the target area;

The topological graph determining unit is used for determining a road network topological graph corresponding to the target traffic road network according to the roads and the junction points in the target traffic road network;

wherein the topology map determining unit includes:

The conversion subunit is used for taking the road in the target traffic road network as a road node and taking the intersection point between any two roads as an edge;

The generation subunit is used for generating a road network topological graph corresponding to the target traffic road network according to the road nodes and the edges;

Wherein the differential operator is a laplace operator, and the determining module includes:

the system comprises an ingress determining unit, a determining unit and a processing unit, wherein the ingress determining unit is used for determining the number of edges pointing to each road node in the road network topological graph and determining the number of edges as the ingress of the road node;

the system comprises an input degree matrix generation unit, a control unit and a control unit, wherein the input degree matrix generation unit is used for generating an input degree matrix corresponding to the road network topological graph according to the input degree of all road nodes in the road network topological graph;

The weight determining unit is used for determining the traffic flow and/or the importance of the intersection point corresponding to each side in the road network topological graph, and determining the weight of the side according to the traffic flow and/or the importance;

The weight matrix generation unit is used for generating a weight matrix corresponding to the road network topological graph according to weights corresponding to all edges in the road network topological graph;

and the matrix calculation unit is used for calculating the Laplace matrix corresponding to the road network topological graph according to the input degree matrix and the weight matrix.

11. The apparatus of claim 10, wherein the matrix calculation unit comprises:

and the matrix processing subunit is used for performing matrix subtraction on the input degree matrix and the weight matrix to obtain a Laplacian matrix corresponding to the road network topological graph.

12. The apparatus of claim 10 or 11, wherein the partitioning module comprises:

The road network dividing request comprises the preset connection relation, wherein the preset connection relation comprises the number of edges between the association node and the road node;

the node determining unit is used for determining association nodes which accord with a preset connection relation with the road nodes in the road network topological graph aiming at each road node according to the road network dividing request;

and the local topological graph unit is used for determining the road nodes and the associated nodes corresponding to the road nodes as the local topological graph for each road node.

13. The apparatus according to claim 10 or 11, wherein the traffic element information includes road network structure, traffic facilities, and trajectory information within a preset area around the road node;

the processing module comprises:

The space information determining unit is used for determining a road network structure and traffic facilities in a preset area around the road node as space information corresponding to the road node;

The time sequence information determining unit is used for obtaining track information in a preset area around the road node according to a preset time interval, and drawing the track information on the road network topological graph according to a time sequence to obtain the time sequence information corresponding to the road node.

14. The apparatus of claim 10 or 11, the computing module comprising:

the space continuous data calculation unit is used for calculating space continuous data corresponding to each local topological graph according to the space information corresponding to the road nodes and the associated nodes in the local topological graph and the differential operator;

the time sequence continuous data calculation unit is used for calculating time sequence continuous data corresponding to each local topological graph according to the time sequence information corresponding to the road nodes and the associated nodes in the local topological graph and the differential operator;

And the time sequence continuous data calculation unit is used for calculating target continuous data corresponding to the local topological graph according to the space continuous data and the time sequence continuous data.

15. The apparatus of claim 14, wherein the time-series continuous data calculation unit comprises:

The adjusting subunit is used for respectively adjusting the space continuous data and the time sequence continuous data according to a preset data format to obtain the space continuous data and the time sequence continuous data with the same data format;

the fusion subunit is used for carrying out data fusion operation on the space continuous data and the time sequence continuous data with the same data format to obtain fused continuous data;

and the determining subunit is used for determining the target continuous data according to the fused continuous data.

16. The apparatus of claim 15, the apparatus further comprising:

the attribute information determining module is used for acquiring attribute information corresponding to each road in the target traffic network, wherein the attribute information comprises one or more of width, length, number of lanes, function grade and traffic condition of the road;

The vector determining module is used for determining a road feature vector corresponding to the target traffic road network according to the attribute information corresponding to each road;

The determining subunit is configured to:

and performing data splicing operation on the fused continuous data and the road feature vector to obtain the target continuous data.

17. The apparatus of any of claims 10-11, 15-16, wherein the optimization module comprises:

the request acquisition unit is used for acquiring a road network optimization request, wherein the road network optimization request comprises an optimization requirement;

and the optimizing unit is used for carrying out data processing on the target continuous data corresponding to the plurality of partial topological graphs by adopting a network model corresponding to the optimizing requirement according to the road network optimizing request.

18. The apparatus of any one of claims 10-11, 15-16, further comprising:

and the clustering module is used for clustering the continuous target data corresponding to the local topological graph by adopting a preset clustering algorithm.

19. An electronic device, comprising:

At least one processor; and

A memory communicatively coupled to the at least one processor; wherein,

The memory stores instructions executable by the at least one processor to enable the at least one processor to perform the method of any one of claims 1-9.

20. A non-transitory computer readable storage medium storing computer instructions for causing the computer to perform the method of any one of claims 1-9.

21. A computer program product comprising a computer program which, when executed by a processor, implements the steps of the method of any of claims 1-9.