METHOD AND APPARATUS FOR PRODUCING A LANE-ACCURATE ROAD MAP

A method for producing a lane-accurate road map. The method includes providing a digital road-accurate road map, providing a trajectory data record, identifying at least one road with segmenting of the road-accurate road map into at least one road segment, modeling the road segment in a road model, the road model having parameters for describing lanes of the road, random variation of parameter values of at least a part of the parameters of the road model through random selection of a change operation of the road model, and assigning at least a part of the trajectory data of the trajectory data record to the road model with ascertaining of at least one probability value for the road model. Based on the ascertained at least one probability value, optimal parameter values of the road model are ascertained, and based on this a lane-accurate road map is produced.

FIELD

The present invention relates in general to the production of road maps. In particular, the present invention relates to a method and to a data processing device for producing a digital road map that is lane-accurate.

BACKGROUND INFORMATION

In particular with regard to automated and/or autonomous driving of vehicles, in the past, various methods have been developed for producing digital road maps.

In a paper by Uruwaragoda et al., 2013, “Generating Lane Level Road Data from Vehicle Trajectories Using Kernel Density Estimation,” Proceedings of the 16th International IEEE Annual Conference on Intelligent Transportation Systems (ITSC 2013), 201, for example a method is described for estimating a number and a width of lanes on roads. For this purpose, starting from a road-accurate road map, the center line of the road is sectioned at right angles at discrete distances. The points of intersection of each of these perpendiculars with trajectories of vehicles on the road are calculated, and in each case a core density estimation is carried out. In this way, support points along the road are produced that contain information about the number of lanes and a lane width, and that can subsequently be linked.

In a paper by Schroedel et al., “Mining GPS Traces for Map Refinement,” Data Mining and Knowledge Discovery, 2004, 9, information about the number of lanes and a lane width is derived without prior map knowledge, in that an algorithm first divides the trajectories of vehicles into segments and identifies the center line. Along this center line, perpendicular distances to the trajectories of the vehicles are categorized using density estimation methods in order to enable conclusions about the lanes.

In Betaille et al., “Creating Enhanced Maps for Lane-Level Vehicle Navigation,” IEEE Transaction on Intelligent Transportation Systems, 2010, 4, 2010, 10, a modeling-based approach is pursued in which models described by clothoids are adapted to measured trajectory data of vehicles.

SUMMARY

Through specific example embodiments of the present invention, an improved method for producing a more detailed and precise lane-accurate road map, and a corresponding data processing device, can advantageously be provided.

An aspect of the present invention relates to a method for producing and/or generating a lane-accurate road map, in particular a digital lane-accurate road map. The method has the following steps:providing a digital road-accurate road map for describing the course of at least one road;providing a trajectory data record that has a plurality of trajectory data of traffic participants along the at least one road;identifying and/or ascertaining the at least one road, with segmenting, dividing, and/or partitioning the road-accurate road map into at least one road segment;modeling the road segment in at least one road model, the road model having a plurality of parameters for the geometrical and/or topological description of lanes of the road;random varying and/or changing, in particular multiple random varying and/or changing, of parameter values at least of a part of the parameters of the road model, through random selection of a change operation of the road model in order to change parameter values;assigning at least a part of the trajectory data of the trajectory data record to the road model, with ascertaining of at least one probability value for the road model, the probability value correlating with a goodness and/or quality of a mapping, imaging, and/or imitation of the trajectory data by the road model;ascertaining, based on the ascertained at least one probability value, optimal parameter values of at least a part of the parameters of the road model; andproducing a lane-accurate road map based on the optimal parameter values of the road model.

Here and in the following, the “digital road-accurate road map” can designate a road map that contains only information relating to a road course and/or a road, but not containing information regarding individual lanes on the road. For example, the road-accurate road map can have one or more nodes and edges, where an edge can be used to represent a road and/or a road segment and a node can represent an intersection. The road-accurate map can as it were designate a graph with nodes and edges. The edges can be given and/or represented by arrows and the nodes can be given and/or represented by points in the graph and/or in the road-accurate road map.

The term “lane-accurate road map” can designate a digital road map and/or a graph that has information relating to individual lanes. The lane-accurate road map can in particular contain information relating to a geometry of individual lanes, for example relating to a lane width, the number of lanes, a distance between lanes having opposite directions of travel, and/or a curvature of a road and/or of a road segment. These geometrical items of information can be taken into account and/or contained for example in at least a part of the “parameters for geometrical description of lanes of the road.” The “parameters for geometrical description” can include, as it were, parameters for describing the number of lanes, a width of individual lanes, a curvature of a road or of individual lanes, and/or a distance between lanes having opposite directions of travel. In addition, the lane-accurate road map can contain information relating to a topology of the lanes, where the topology can describe a connection path, a connection, and/or a connectivity between individual lanes. This topological information can be taken into account and/or contained for example in at least a part of the “parameters for topological description of lanes of the road.” The “parameters for typological description of lanes of the road” can include parameters for describing a connection path, a connection, a connectivity between individual lanes, a disappearance of individual lanes in the road segment, and/or a producing of an additional lane in the road segment.

The term “trajectory data” can designate geographical coordinates such as GPS coordinates (Global Positioning System) and/or GNSS data (Global Navigation Satellite System) that describe a trajectory, a movement profile, a driving path, and/or a movement of a traffic participant, such as a vehicle, a motorcycle, and/or a pedestrian, along a road and/or at an intersection. The term “trajectory data record” can as it were designate a set of such trajectory data of one or more traffic participants.

In addition, the term “modeling of the road segment in at least one road model” can designate a mapping, an imaging, a copying, and/or an imitation of the road segment in the at least one road model. Here, the road model can designate a mathematical and/or modeling-based abstraction and/or description of the road segment.

In the following, the method according to the present invention is summarized. The road-accurate road map can be read for example in a data processing device, from a data storage device of the data processing device. The road-accurate road map can include one or more nodes and/or one or more edges for the geographical description of one or more roads and/or of one or more intersections. The providing of the road-accurate road map can thus include a reading in of the road-accurate road map and/or a reading in of the at least one edge and/or of the at least one node. The road-accurate road map can then be analyzed, for example on the basis of the at least one node and/or the at least one edge, and can be subdivided and/or segmented into at least one road segment. In particular, the road-accurate road map can have a plurality of roads that can each be subdivided into individual road segments, for example based on the nodes and/or edges. In other words, roads and/or the at least one road can be identified based on the nodes and/or edges. Subsequently, each of the identified road segments can be mapped, modeled, imaged, and/or imitated in a separate road model. After this, for each of the road models, each of which can be assigned to a road segment, at least a part of the parameters of the respective road model can be varied and/or changed. In particular, the parameters of each road model can be iteratively varied multiple times, such that parameters of different road models can be varied simultaneously or one after the other in a temporal sequence. The parameter values can be varied independently of the trajectory data. In addition, the trajectory data can be assigned to the respective road models, for example on the basis of geographical coordinates of the trajectory data and/or of the road-accurate road map. Here it can be ascertained which of the trajectory data are located in one of the road segments, so that, based on this, the trajectory data associated with the individual road models can be ascertained. In particular, the step of modeling in the road model can take place before the step of allocating the trajectory data to the road model. Subsequently, it can be checked how well the trajectory data have been imitated and/or imaged by the respective road model; a probability value can be ascertained as a measure of the goodness and/or quality of such a mapping for each of the road models. In the context of the present invention, the probability can as it were designate a measure for a quality and/or goodness of a mapping, imaging, and/or imitation of the trajectory data by the corresponding road model. In particular, for each of the road models a plurality of probability values can be ascertained through multiple independent varying of a part of the parameters of each road model. From the probability values ascertained for each of the road models, at least one probability value can then be selected in each case that is higher or is a highest probability value compared to other probability values of the same road model, and which can thus correspond to an optimal configuration of the associated road model and/or to the optimal parameter values of the associated road model. In addition, in the context of the ascertaining of the highest probability value, the so-called simulated annealing method can be used. This can bring it about that change operations that worsen an agreement between the road model and trajectory data will be accepted less frequently as the time of the optimization process progresses, and/or that the optimization of the road model ends directly in the optimal parameter values of the road model, i.e. the most probable and/or best road model. Finally, in this way the probability values and the parameter values of the individual road models can be iteratively optimized. The optimal parameter values of the individual road models can be selected and/or chosen and can thus represent a lane-accurate road map. In other words, the lane-accurate road map can be given by the optimal parameters of the at least one road model. The method according to the present invention can thus provide that one or more road segments are mapped in one or more road models, and subsequently the optimal parameter values of the one road model or of the road models are ascertained iteratively.

The example method according to the present invention can therefore designate a modeling-based optimization method based on which an accurate topological and geometrical road map of a traveled road network can advantageously be derived and/or ascertained from movement profiles, trajectory data, and/or driving trajectories of one or more traffic participants. In particular, a number, a course, a width, a distance, and/or a connectivity of individual lanes can be determined with a high degree of accuracy. This can take place for straight road segments, curved segments, and/or for intersection segments.

The present invention can in particular be regarded as being based on the findings described below. With the availability of connectivity solutions in many commercially produced vehicles, and/or via smartphone applications, already today innumerable movement profiles and/or trajectory data can be acquired from vehicles and/or traffic participants. This can therefore represent a source of data that can be made available easily, at low cost, and in good time. At the same time, the worldwide mapping of the road network, extensive in its surface coverage and accurate, is becoming more and more important in the context of automatic driving. The method according to the present invention can therefore advantageously enable an accurate mapping of a road network based on an analysis of known movement profiles, trajectory data, and/or driving trajectories, such as of a large fleet of vehicles. For example in comparison with a mapping made by highly specialized measurement vehicles, as is frequently carried out by traditional map producers, the trajectories used for the method according to the present invention can be provided at low cost, easily, and in large quantities, so that a low-cost, rapid, extensive and precise mapping of a road network can be carried out.

According to a specific embodiment, the optimal parameter values are ascertained based on a Monte Carlo method, in particular based on a reversible jump Markov chain Monte Carlo method (RJMCMC). In particular, the random selection of a change operation for the random varying of the parameter values of at least a part of the parameters of the road model can be carried out based on the Monte Carlo method and/or the reversible jump Markov chain Monte Carlo method. Here, all, or at least a part, of the change operations can be assumed to be uniformly distributed, and, based on a random number, one of the change operations can be selected, as if by rolling dice, for the random variation of at least a part of the parameter values. After the random selection of a change operation this change operation can be carried out, and subsequently it can be decided whether the change caused thereby in the parameter values is to be accepted or rejected. In the course of the RJMCMC method, in general input data, such as the trajectory data, can be realized as a realization of a random experiment, a distribution of the input data being implied by the road network taken as a basis, and/or by the road model. The goal of the RJMCMC method can be to reconstruct the unknown distribution, such as the actual road network, on the basis of the road model. Here, the road model and/or the parameter values of the road model can be varied randomly and/or independently of the trajectory data. Subsequently, depending on the ascertained probability value and/or depending on the magnitude of the ascertained probability value, the associated parameter values, or the change of the parameter values, can be rejected or accepted, for example based on a comparison with a threshold value and/or based on an evaluation metric. A simulated annealing method may also be used in the ascertaining of the optimal parameter values.

According to a specific embodiment, the road model has at least one road block for modeling a number of lanes that is constant at least in a partial area of the road segment. Alternatively or in addition, the road model has at least one connection block for modeling, based on at least one geometrical parameter matrix and at least one topological parameter matrix, of a number of lanes that changes at least in a partial area of the road segment, values of the geometrical parameter matrix describing a change of the number of lanes within the road segment, and values of the topological parameter matrix describing a connection between individual lanes within the road segment. In other words, it can be provided to model each identified road segment using at least one road block and a connection block of the road model. In particular, it can be provided to model each identified road segment through a road block situated between two connection blocks. Through the use of a respective road block in each road segment that models a constant number of lanes, a computing expense can advantageously be reduced. In addition, through the use of at least one connection block per road segment, a flexibility of the road model can be increased, because possible changes in a geometry and/or topology of two adjacent road segments can reliably and comprehensively be modeled and/or taken into account in the connection block. The connection block can have a respective geometrical and a respective topological parameter matrix for each direction of travel of a lane. In other words, the connection block can have two geometrical and two topological parameter matrices for modeling a geometry and/or topology of lanes having different directions of travel.

According to a specific embodiment, the step of modeling the road segment in the road model has the following substeps:parameterizing the road segment in a unit interval, so that each point of the road in the road segment is defined via a parameterization value in the unit interval;segmenting and/or dividing the road segment into at least one road block and at least one connection block of the road model;modeling, imaging, and/or imitating a disappearance or a production of a lane within a road segment, based on at least one geometrical parameter matrix of the connection block;ascertaining values of the geometrical parameter matrix and/or values of the topological parameter matrix based on a random selection of a change operation of the road model.

The step of parameterization can include a step of ascertaining a length and/or a longitudinal extension of the road segment and a step of norming to the ascertained length. In other words, each road segment can be parameterized one-dimensionally, whereby, advantageously, each point of the road segment can be described by a value between zero and one, i.e. by a value of the unit interval.

According to a specific embodiment, the digital road-accurate road map has at least one intersection and a plurality of roads connected to the intersection, the method further having the following steps:identifying the at least one intersection with segmenting and/or division of the road-accurate road map into at least one intersection segment;modeling, mapping, imaging, and/or imitating the intersection segment in at least one intersection model, the intersection model having a plurality of parameters for the geometrical and/or topological description of lanes of the intersection;random varying and/or changing, in particular multiple random varying, of parameter values of at least a part of the parameters of the intersection model, through random selection of a change operation of the intersection model in order to change parameter values;assigning at least a part of the trajectory data of the trajectory data record to the intersection model, with ascertaining of at least one probability value for the intersection model, the probability value correlating with a goodness and/or quality of a mapping of the trajectory data by the intersection model;ascertaining optimal parameter values of at least a part of the parameters of the intersection model, based on the ascertained at least one probability value; andcreating a lane-accurate road map based on the optimal parameter values of the intersection model.

According to the present invention, it can therefore be provided to model each road segment of the road-accurate road map through a road model and each intersection segment through an intersection model. In this way, advantageously the individual properties of intersections and roads are modeled, and computing expense can be reduced. In addition, this can increase the accuracy of the produced lane-accurate road map. Here, an intersection in the road-accurate road map may for example be identified by identifying a node connected to more than two edges.

According to a specific embodiment, the intersection model has an external intersection model for modeling a navigable surface of the intersection, based on a distance parameter (d) and an angle parameter (a). Alternatively or in addition, the step of modeling of the intersection segment in the intersection model includes the following substeps:ascertaining an intersection node in the road-accurate road map, for example based on an ascertaining of a node connected to more than two edges in the road-accurate road map;ascertaining a number of edges, connected to the intersection node, of the road-accurate road map, with ascertaining of a number of roads connected to the intersection, where the number of ascertained edges can correspond to the number of roads connected to the intersection;generating and/or producing a number of intersection arms, corresponding to roads connected to the intersection, each of the intersection arms being defined by a distance parameter (d) indicating a distance of a center of the intersection to a limit surface of the intersection along the respective intersection arm, and each of the intersection arms being defined by an angle parameter (a) indicating an angle of rotation between the respective intersection arm and a reference direction, for example a reference intersection arm.

Through the external intersection model, advantageously a connection cross-section between the intersection arms and the roads connected thereto can be precisely modeled and/or calibrated to one another, for example with regard to the number of lanes, a width of lanes, a distance between lanes having opposite directions of travel, and/or a curvature.

According to a specific embodiment, the intersection model has an internal intersection model for modeling—based on a factor matrix (F) of the intersection model—lanes leading into the intersection, lanes leading out from the intersection, and a course of lanes over a navigable surface of the intersection.

Alternatively or in addition, the step of modeling of the intersection segment in the intersection model has the following substeps:modeling, imaging, mapping, and/or imitating at least a part of lanes leading into the intersection, at least a part of lanes leading out from the intersection, and a curve of at least a part of lanes leading over an intersection surface of the intersection, based on a factor matrix (F), where values of the factor matrix (F) describe a curve and a connection of lanes over the intersection surface; andascertaining values of the factor matrix (F) based on at least a part of the trajectory data of the trajectory data record.

Through the internal intersection model, advantageously every possible connection of individual lanes via the intersection surface can be precisely modeled. In addition, by ascertaining the values of the factor matrix based on the trajectory data, the number of possible connections of the lanes via the intersection, and thus a computing expense, can be reduced, because the trajectory data can always represent actual and realistic connections of the lanes.

According to a specific embodiment, the road model and/or an intersection model each have a number parameter (L) for describing the number of lanes, a width parameter (W) for describing a width of individual lanes, a curvature parameter (C) for describing a curvature of a road, and a distance parameter (G) for describing a distance between lanes having opposite direction of travel. Parameters named above can be parameters of an internal intersection model and/or of an external intersection model of the intersection model. Parameters named above can also be parameters of a road block and/or of a connection block of the road model. The distance between lanes having opposite direction of travel can for example describe a constructive separation between adjacent lanes having opposite directions of travel. Through parameters listed above of the road model and/or of the intersection model, it can advantageously be ensured that roads and/or intersections can be precisely modeled, and that in this way a precise lane-accurate road map can be produced.

According to a specific embodiment, the road model and/or an intersection model has at least one change operation selected from the list made up of: an insertion operation for inserting a connection block into a road block, a fusing operation for fusing two road blocks and a connection block to form one road block, an adaptation operation for adapting a parameterization value for parameterizing a longitudinal extension of a road, an addition operation for adding a lane, a removal operation for removing a lane, a distance adaptation operation for adapting a distance between lanes having opposite directions of travel, a width adaptation operation for adapting a width of a lane, and a curvature adaptation operation for adapting a curvature of a road in the road model, of a road block, and/or of a connection block of the road model. Using change operations listed above, advantageously the parameter values of all and/or at least of a large part of the parameters of the road model and/or of the intersection model can be varied through the random selection of one of the change operations. In addition, the change operations can reliably map all possible and realistic changes in a real road network, which in turn can permit the creation of a precise and realistic lane-accurate road map.

According to a specific embodiment, the method further includes a step of rejecting or accepting parameter values varied randomly based on the random selection of a change operation, based on an evaluation metric that describes the quality of the mapping of the trajectory data by the road model and/or an intersection model. Here the evaluation metric has a first term describing an agreement between the trajectory data and the road model and/or an intersection model. In addition, the evaluation metric has a second term for taking into account at least one prespecified characteristic variable of a road geometry, in particular a characteristic variable relating to a lane width and/or a road width. For example, for a characteristic variable there can be a stochastic specification relating to the values of the characteristic variable, which can predetermine the dimension of the characteristic variable.

For example, a lane width can be defined using a normal distribution, so that a lane width is sought in the vicinity of around 3.25 m. In this way, it can be avoided that lane widths of, e.g., 6 m are examined. Via the evaluation metric, any prior knowledge about a road geometry and/or an intersection geometry can thus advantageously be taken into account. For example, construction standards and/or construction guidelines for road construction can be taken into account in the evaluation metric. In this way, it can in particular be ensured that the method according to the present invention enables the production of realistic lane-accurate road maps. Computing time can also be reduced in this way.

A further aspect of the present invention relates to a data processing device for ascertaining a lane-accurate road map based on a digital road-accurate road map. Here, the data processing device is set up to carry out the method as described above and in the following. The term “set up” can mean that the data processing device for example has a program element that, when executed, for example on a processor of the data processing device, causes the data processing device to carry out the method according to the present invention. For example, the program element can have corresponding software instructions.

All features, steps, functions, and/or characteristics described above and in the following in relation to the method according to the present invention can be features, functions, and/or characteristics of the data processing device as described above and in the following, and vice versa.

According to a specific embodiment, the data processing device has a data storage device for storing a digital road-accurate road map, and a processor. On the data storage device, in addition a program element can be stored that, when executed on the processor, causes the data processing device to carry out the method according to the present invention.

The Figures are schematic and are not to scale. In the Figures, identical, identically functioning, or similar elements have been provided with the same reference characters.

DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS

FIG. 1shows a data processing device10according to an exemplary embodiment of the present invention.

Data processing device10has a data storage device12. In data storage device12, for example a road-accurate road map14can be stored that can have at least one node11(see, e.g.,FIG. 3C and 3D) and/or an edge13(see, e.g.,FIG. 3C and 3D), for describing a course of a road17(seeFIG. 4A) and/or an intersection19(seeFIG. 4A). In particular, road-accurate road map14can have a plurality of nodes11and/or edges13for describing a road network having a plurality of roads17and/or intersections19. In data storage device12, a trajectory data record16can also be stored that can have a plurality of trajectory data27(seeFIG. 3B) from traffic participants.

Alternatively or in addition, data processing device10can have an interface15via which lane-accurate road map14and/or trajectory data record16of data processing device10can be provided. Interface15can for example be realized wirelessly, so that road-accurate road map14and/or trajectory data record16can for example be received wirelessly via WLAN, Bluetooth server, and/or the like, for example from at least one server and/or via a cloud environment.

In addition, data processing device10has at least one processor18. On processor18, a program element, for example stored in data storage device12, can be carried out that instructs data processing device10and/or processor18to carry out the method according to the present invention for producing a lane-accurate road map22as described above and in the following.

Optionally, data processing device10can have an operating element20for inputting an operating input, for example by a user. The operating element can additionally have a display element21for displaying the road-accurate road map14, the lane-accurate road map22, and/or the trajectory data record16.

FIG. 2shows a flow diagram illustrating steps of a method for producing a lane-accurate road map22according to an exemplary embodiment of the present invention.

In a first step S1, a digital road-accurate road map14is provided for describing a course of at least one road17and/or at least one intersection19, for example via data storage unit12and/or via interface15of data processing device10. In particular, road-accurate road map14can have a plurality of roads17and intersections19. In addition, in step S1a trajectory data record16is provided that has a plurality of trajectory data27of traffic participants along the at least one road17and/or the at least one intersection19. Trajectory data record16can also be provided via data storage unit12and/or via interface15of data processing device10.

In a step S2, the at least one road17is identified, with segmenting of the road-accurate road map14into at least one road segment26(seeFIG. 4C). This can take place based on nodes11and/or edges13of road-accurate road map14. Optionally, in step S2at least one intersection can take place by segmenting of road-accurate road map14into at least one intersection segment19a.In particular, in step S2the road-accurate road map14can be subdivided into a plurality of road segments26and a plurality of intersection segments19a.

In a further step S3, the at least one road segment26is modeled in at least one road model28(seeFIG. 5A, 5B). In particular, in step S2all road segments26can each be modeled in a road model28. In addition, in step S3the at least one intersection19can be modeled in an intersection model34(seeFIGS. 6A-6C). In particular, each of the intersections19can be modeled in a separate intersection model34. Each of the road models28and/or each of the intersection models34has a plurality of parameters for the geometrical and/or topological description of lanes23.

In a further step S4, parameter values of at least a part of the parameters of road model28and/or of intersection model34are varied through random selection of a change operation40,41,42,43,44,46,48,50(seeFIG. 7A-7E) of road model28and/or of intersection model34. In particular, in step S4the parameter values of all road models28and of all intersection models34can be varied multiply and iteratively.

In a further step S5, at least a part of the trajectory data27of trajectory data record16is assigned to road model28, with ascertaining of at least one probability value for road model28. In particular, in step S5the trajectory data27can be assigned to each of the road models28, with ascertaining in each case of at least one probability value for each of the road models28. In addition, in step S5the trajectory data27can be assigned to the at least one intersection model34, by ascertaining at least one probability value in step S5the trajectory data27can be assigned to each of the intersection models34by ascertaining in each case at least one probability value for each of the intersection models34. The probability values correlate with the quality of a mapping of the trajectory data27by the respective road model28and/or the respective intersection model34.

In a step S6, based on the ascertained at least one probability value, optimal parameter values are ascertained for at least a part of the parameters of road model28and/or of intersection model34. In particular, optimal parameter values can be ascertained for each of the road models28and/or for each of the intersection models34.

In a step S7, a lane-accurate road map22is produced based on the optimal parameter values of the at least one road model28and/or of the at least one intersection model34. In particular, the lane-accurate road map22can be given by the optimal parameter values of all road models28and/or all intersection models34.

FIGS. 3A through 3Deach illustrate a method for producing a road-accurate road map16. The road-accurate road map16produced in this way can be used as a basis for the production of a lane-accurate road map22. Correspondingly, all the steps described in relation toFIGS. 3A through 3Dcan also be part of the method according to the present invention for producing a lane-accurate road map22.

FIG. 3Aillustrates a trajectory data record16having a plurality of collected trajectory data27and/or trajectories27. In addition,FIG. 3Aillustrates a segmenting and/or division of the trajectory data27into various traffic scenarios and/or segments24a-c.FIG. 3Aschematically shows a first segment24a,which describes a curve, a second segment24b,which describes an intersection, and a third segment that describes a road. Segments24a-care here ascertained as described in the following.

The trajectory data27collected from a fleet of vehicles, for example GNSS trajectories27, can, in any number, describe a likewise arbitrarily large traffic scenario. In order to make it possible to handle the dimension of the data to be evaluated, trajectories27can be partitioned in automated fashion according to a logical system. For this purpose, trajectory data27, which can also be referred to as input data, can be divided into different traffic scenarios24a-cand/or different segments24a-c, where each of the segments24a-ccan describe a straight road, a curve, or an intersection.

In an automated method, each trajectory27can be run through and individual measurement points can be identified as potential curve points based on boundary values in a change of a driving angle and/or of a speed. These points thus lie either on a curve or an intersection, or may have originated from measurement errors. Subsequently, all identified points can be clustered, aggregated, and/or combined via distance boundary values. Starting from a specified quantity of combined points, the cluster is regarded as a curve and/or as an intersection. Based on the found curves and/or intersections, a triangulation can then be done, and then a Delaunay decomposition can be constructed. Each cell of this decomposition can finally describe a separate traffic situation24a-cand/or a segment24a-c. The segments24a-ccan be interpreted as, as it were, cells24a-cof the decomposition.

Based on a set of trajectory data27, such as GNSS trajectory data27, a road-accurate road map14can be produced that can correspond to a graph made up of nodes11and edges13, where nodes11and edges13can represent a center line of the road. As an example, such a road-accurate road map14is illustrated inFIG. 3D.

In order to produce road-accurate road map14, first the input data16,27can be segmented, as described forFIG. 3A. For each cell24a-ca graph can subsequently be initialized that can describe the traffic scenario of the respective segment24a-c, or cell24a-c. The goal here is to enable the models in the cells24a-c, linked by boundary conditions, to be developed individually and subsequently fused to form a graph. As an example, the production of a road-accurate road map14is shown inFIGS. 3B-3Dfor road segment24cfromFIG. 3A. Here,FIG. 3Bshows a cell24c,or segment24c,and vehicle trajectories27.FIG. 3Cshows an initial road map14, andFIG. 3Dshows an optimized road map14. Road maps14ofFIGS. 3C and 3Dcan also be designated cell graph14.

For the initialization, first all cell boundaries25can be intersected with trajectories27in order to ascertain the road centers at the cell edges25, as shown inFIG. 3B. These centers can be plotted in the graphs of the corresponding cells24cas nodes11, as shown inFIG. 3C. In addition, in each cell24cthe focal point of cell24ccan be inserted into the graph as node11, and can be connected by edges13to nodes11, at cell edges25.

In order to link the trajectory data27and the model, or cell graph, an evaluation metric can be introduced that describes how well the models map the data. Here, on the one hand the distance between the models and the trajectory data27, and on the other hand the differences in the direction of travel, can be taken into account. In order to optimize the models and to produce the final road-accurate road map16, as shown inFIG. 3D, a reversible jump Markov chain Monte Carlo (RJMCMC) method can be used. Here, the trajectory data27are regarded as the realization of a random experiment whose distribution is implied by the underlying road network. The goal of the method is to reconstruct the unknown distribution, in this case the road network. Here, the models are varied randomly, independently of trajectory data27, and subsequently a decision can be made as to whether to accept or reject the change based on the evaluation metric. The random variation of the models takes place through the random selection of prescribed change operations. Available for selection are for example a move operation, a producing operation, a removal operation, a dividing operation, and/or a fusing operation. In the move operation, a node11of a cell graph24cis moved in space. The producing operation describes the addition of a new node11in graph24c,and forms a reversible pair of operations together with the remove operation. The fuse operation inserts a node11into an adjacent edge13, so that two edges13situated close to one another are unified in parts. The dividing operation dismantles such a construct, and is thus the opposite of the fuse operation. The presence of reversible pairs can be advantageous for a correct stochastic description of the process. As can be seen from a comparison ofFIGS. 3C and 3D, during the optimization the center node11is removed, because it is not required for the description of road17.

FIGS. 4A through 4Ceach illustrate steps of a method for producing a lane-accurate road map22according to an exemplary embodiment of the present invention. Specifically, inFIG. 4Aa road-accurate road map14is shown.FIG. 4Billustrates a parameterization, andFIG. 4Cillustrates a segmenting of road17of road map14. In addition,FIGS. 5A through 5Ceach show a road model28according to an exemplary embodiment of the present invention. Specifically,FIG. 5Ashows a connection block30of road model28,FIG. 5Bshows a road block32of road model28, andFIG. 5Cshows geometrical and topological parameter matrices of connection block30ofFIG. 5A.

FIG. 4Ashows a road-accurate graph14and/or a road-accurate road map14, describing a road17and, at each of the ends, an intersection19, using nodes11and edges13. In order to transfer road17into a lane-accurate road map22, road17is first parameterized one-dimensionally. In this way, as is shown inFIG. 4B, each point p of road17can be described via a value p∈[0; 1] of the unit interval.

Based on this parameterization, road segments26can be defined, as shown inFIG. 4C. In other words, road17is divided into one or more road segments26that can be identified for example based on nodes11and/or edges13.

The segmenting of road17into road segments26can make it possible to describe traffic situations at the lane level in road model28, as is illustrated inFIGS. 5A through 5C. Here, driving on a constant number of lanes23is distinguished from the widening or narrowing of road17by a lane23.

A general road block32, as shown inFIG. 5B, can have a number parameter L for describing the number of lanes23, a width parameter W for describing a width of individual lanes23, a curvature parameter C for describing a curvature of a road17, and a distance parameter G for describing a distance between adjacent lanes23having opposite directions of travel. Road block28can also have a type parameter T for describing a type of a roadway marking for each lane23. Parameter G can be a size of a constructive separation between the lanes23traveling in opposite directions.

A general road block32can thus be defined by the variable

A road17is thus defined as a set ξsof m road segments26and their parameterization values P, which describe the longitudinal extension on road17, according toFIGS. 4A through 4C:

In order to represent a curved road segment26, all connections of lanes23on road segment26can be described by cubic Hermite polynomials. In this way, it is possible for a road segment26not only to have a constant curvature, but also to assume any course, where only the boundary conditions of continuity and differentiability are maintained in order to produce a realistic roadway course. The boundary conditions are introduced by specifying the connection points and the slope, or the slope vector, at the connection points. In order to influence the course of the polynomials, the magnitude of the slope vectors is accessible, or integrated, as parameter C in road model28.

A general road block32, also designated B, in the following, can be specified through further limitations or supplementations. A road block32, as shown inFIG. 5B, contains the limitation that the number L of lanes23in the respective road segment26remains constant. In this way, a segment of road can be mapped on which only the inherent properties change, such as lane width W. InFIG. 5B, lanes23are identified with characteristic values −1, −2, +1, +2, where the sign indicates a direction of travel and the lanes in each direction of travel are numbered by progressive natural numbers 1, 2.

A connection block30, also designated Bc, in the following, as shown inFIG. 5A, describes a traffic situation in which the number L of lanes23changes, and in which a combination or splitting of lanes23can therefore be modeled. Therefore, connection block30is supplemented, relative to road block32, through a connection permutation R=(RGR, RTR, RGL, RTL), which both geometrically describes which lane23disappears, or is produced, and also topologically defines which lanes23are connected. As shown inFIG. 5C, for each direction of travel an individual geometrical parameter matrix RGR, RGL, and a topological parameter matrix RTR, RTL, are indicated. An existing item of information, or connectedness, of lanes23is illustrated in binary fashion by a one, and non-connectedness is illustrated by a zero, as shown inFIG. 5C. Also, inFIGS. 5A and 5Clanes23are identified with characteristic values −1, −2, +1, +2, where the sign indicates a direction of travel and the lanes23of each direction of travel are numbered with progressive natural numbers 1, 2. For example, in the situation shown inFIG. 5Ait is topologically possible on the left side to change from the lane −1 to the new lane −2, or to remain in the present lane. This topological information is not synonymous with a simple lane change maneuver, which can be implied by the type of roadway marking. A connection block30can therefore be defined as

In addition to these limitations of road model30, it can in addition be provided that a connection block30is situated between two road blocks32, in order to compensate, if needed, the differences between road blocks32(e.g. with regard to number of lanes L). If no changes are necessary, connection block30can be a special case of a road block32.

FIGS. 6A through 6Deach illustrate an intersection model34according to an exemplary embodiment of the present invention. Specifically,FIGS. 6A and 6Bshow an external intersection model36of intersection model34,FIG. 6Cshows an internal intersection model38of intersection model34, andFIG. 6Dshows a factor matrix F of the internal intersection model ofFIG. 6C.

In the previous representation of a road map14, as shown for example inFIG. 4A, an intersection19was represented by a node11that is connected to more than two edges13. For the lane-accurate mapping and/or modeling of an intersection19, both geometrical information about an intersection surface37and/or a navigable surface37, or intersection surface37, and also topological information about the connectivity of the incoming and outgoing lanes23and their path over intersection surface37are required. For this purpose, road-accurate road map14is first segmented into at least one intersection segment19a,and/or an intersection segment19ais identified in road-accurate road map14. Intersection segment19ais then modeled in an internal intersection model38and an external intersection model36, as is explained in more detail below.

Intersection model34, in the following also designated ξc, is made up of two different individual models. InFIGS. 6A and 6B, an external intersection model36, in the following also designated ξc,o, is shown. For the initialization, nodes11of road-accurate road map14are examined, and intersection nodes35are identified on the basis of the connected edges13. Because a large intersection19in road-accurate road map14can be described by a plurality of nodes11, if necessary a plurality of nodes11can be combined with the aid of a distance value dcr. External intersection model36can be produced at the center of the involved nodes11. On the basis of the identified intersection nodes35, the information can be gained directly as to how many roads17are connected to intersection19. For each road17, an intersection arm A1-A4is produced. Each intersection arm A1-A4has a distance parameter d that describes the distance from the center to the beginning of intersection surface37in relation to this intersection arm A1-A4, and defines an angle parameter a that defines an angle of rotation relative to a reference direction, for example east. Through these two parameters d, a, a transition point from road17into intersection surface37is defined for each intersection arm A1-A4.

The internal intersection model38, also designated ξc,iin the following, is illustrated inFIGS. 6C and 6D. Internal intersection model38describes the connectivity of lanes23. Each intersection arm A1-A4here has the same information as a general road block32of road model28, thereby defining the geometry of the connected roads17. Between each incoming and outgoing lane23there can be a connection whose course can be described by a cubic Hermite polynomial. Thus, each connection is influenced by a parameter C, which can specify the course over intersection surface37. Parameter C is stored in factor matrix F, as is shown inFIG. 6D, where a value of zero indicates that the connection does not exist. Through the identification of the external lane courses, in addition the limits of intersection surface37are defined. Here, factor matrix F can have a line and a column for each direction of travel and each intersection arm A1-A4. For clarity, different directions of travel are illustrated by different signs of the indices inFIG. 6D. In addition, lanes23of individual intersection arms A1-A4inFIG. 6Dare progressively numbered with natural numbers.

In the following, details are described of the road model28described in the preceding Figures, in particularFIGS. 4A through 6D, of intersection model32, and the method according to the present invention for producing lane-accurate road map22.

For the initialization of models28,34, road-accurate road map14is divided into roads17and intersections19. At each intersection19, an initial intersection model35is produced having an arm distance of dinit=25 m, where the number of connected roads17, and thus the angle parameters a of intersection arms A1-A4, are determined from road map14. Subsequently, road models28between intersections19are generated, where a road17is described in the graph by a chain {vx, . . . , vy}. In the lane-accurate road model28, a connection block30is produced at each node11, and between them a road block32is produced. Each road17begins and ends with a connection block30that can, if necessary, correct the differences between the adjoining road block32and the intersection connection. Each road17is initialized as having two lanes, with one lane23per direction of travel. The totality of the a road models28and b intersection models34is designated in the following as Φ={ξs1, . . . , ξsaξc1, . . . , ξcb}.

The initialized models28,34, Φ represent the current configuration of the overall model. The parameters of these models are the described properties or parameters of road blocks32, of connection blocks30, of internal intersection models36, and of external intersection models38. These are to be varied using an RJMCMC method; therefore, in the following the possible change operations and the corresponding transition kernels are introduced. For all models28,30,32,34,36,38, on the one hand there are change operations that influence only the values of the existing parameters, and on the other hand there are change operations that modify the dimension of a model28,30,32,34,36,38.

FIGS. 7A through 7Eeach illustrate change operations40,41,42,43,44,46,48,50according to an exemplary embodiment of the present invention. Specifically,FIG. 7Aillustrates, at the left, an insert operation40for inserting a connection block30into a road block32, and a fuse operation41for fusing two road blocks32and a connection block30to form a road block32, as a reversible change operation41to insert operation40. In addition, at the rightFIG. 7Aillustrates an adaptation operation42for adapting a parameterization value for parameterizing a longitudinal extension of a road17.FIG. 7Billustrates an addition operation43for adding a lane23and a removal operation44for removing a lane23. In addition,FIG. 7Cshows a distance adaptation operation46for adapting a distance G between lanes23having opposite directions of travel,FIG. 7Dshows a width adaptation operation48for adapting a width W of a lane23, andFIG. 7Eshows a curve adaptation operation50for adapting a curvature C of a road17.

With regard to a road model28, the change operations40,41,42,43,44,46,48,50are further divided into two classes. Insertion operation40, fusing operation41, and adaptation operation42, as shown inFIG. 7A, change road model28at the block level; i.e. the individual properties are not changed, but rather only the number of road blocks32and connection block30, and their spatial extension, are changed. In addition operation43, an existing road block32is divided into two road blocks32and one connection block30. Remove operation44correspondingly connects such a constellation, and forms with addition operation43a reversible pair whose selection probabilities can be selected such that the expanded detailed balance condition is met. Adaptation operation42changes the limits of a road block32and/or connection block30with regard to the parameterization of road model28. Addition operation43, remove operation44, distance adaptation operation46, width adaptation operation48, and curvature adaptation operation50change the properties or parameter values of a road block32.

The parameter values of a road block30cannot be changed actively, but only passively. They adapt their parameters to the adjoining road blocks32. The addition operation43for adding a lane23, and a remove operation44, likewise form a reversible pair, while the three adjustment operations42,46,50merely change the values of the parameters.

In order not to prefer any of the change operations40,41,42,43,44,46,48,50in the random variation of parameter values of road model28and/or of intersection model34, or to select each of the change operations40,41,42,43,44,46,48,50with equal probability, the selection probabilities ω40, ω41, ω42, ω43,ω44, ω46, ω48, ω50of all change operations40,41,42,43,44,46,48,50are assumed to be identical:

In the following, the individual change operations40,41,42,43,44,46,48,50are considered in more detail.

The transition from the representation at top inFIG. 7Ato the representation at left inFIG. 7Atakes place via insertion operation40. The longitudinal extension of road block32to be divided, Bsis defined via the parameterization P of road model ξswith the values (ps, pe)∈P, with the parameterized length p1=pe−ps. For the division, two new values u1,u2∈[0,pl]

on this length are required, with u1<u2:

The probability of acceptance is determined as:

The Jacobi matrix of the transformation is

having a determinant of 1, because the matrix is triangular.

Fusing operation41can be regarded as the converse case. The constellation of road block32, connection block30, road block32is combined, and for the transformation no new components are required, but rather are calculated. The constellation is defined in the parameterization P of road model28, by the sequence {pa, pb, pc, pd}. The acceptance probability is:

Adaptation operation42describes, as transition between the upper representation inFIG. 7Aand the representation at right inFIG. 7A, the change of one of the two parameterization values of a road block32. Here, the parameter can be changed by a maximum of half the parameterized length p1of road block32. In order not to prefer a direction of movement, the search function is realized as a random movement:

In order to insert a new lane width addition operation43, as shown inFIG. 7B, road model28is supplemented by a new lane width of a lane23. The new lane width is drawn from a normal distribution whose expected value and variance result from road construction specifications. These can be determined in the context of the scenario or type of road17. For the transformation there follows:

The determinant of the Jacobi matrix is 1 and the acceptance probability results as:

The acceptance probability for the opposite, removal operation44is calculated correspondingly, where the component u is the lane width of lane23to be removed:

The three change operations46,48,50shown inFIGS. 7C, 7D, 7Echange the existing parameter values of road model28and of the intersection model. Therefore, the corresponding search functions are realized as an equal distribution:

Because intersection model34is made up of internal intersection model36and external intersection model38, there are different change operations for each submodel36,38. As shown inFIGS. 6A and 6B, the two parameters distance d and angle a influence the form of external intersection model36. The number of intersection arms A1-A4is already extracted from road map14in the initialization process, and is not changed again. Thus, two change operations are defined that change the two parameters d, a, but not the dimension of external intersection model36. In other words, the external intersection model can have a distance parameter change operation and an angle parameter change operation. Therefore, search functions are realized as a uniform distribution:

In internal intersection model38, each intersection arm A1-A4has a connection cross-section that has the same properties as a road block32. Because a connection block30is connected to each intersection arm A1-A4, this block reacts to the changes in intersection arm A1-A4exactly as it does to changes in a road block32. Therefore, the change operations for varying the connection properties are identical to the already defined operations of a road block32. In other words, the internal intersection model38has the above-described change operations40,41,42,43,44,46,48,50. The influencing of the factor matrix F fromFIG. 6Dis not done through an RJMCMC operation.

FIGS. 8A and 8Beach illustrate an application of an evaluation metric according to an exemplary embodiment of the present invention.

For the evaluations, on the one hand a measure is taken into account concerning the agreement between road model28and/or intersection model34and the trajectory data27, in a first term πdl, and on the other hand previous knowledge about the models28,34is taken into account in a second term πpl. In the following, these measures are presented.

In the first step, the vehicle trajectories27are mapped onto lanes23. For this purpose, first each center line of each road segment26and of each intersection19is transferred into a graph, the center line being discretized in small steps with nodes11and edges13. Each graph is subsequently optimized to a minimum number of nodes11, using the Douglas-Peucker algorithm. Subsequently, these graphs are fused to form an overall representation G.

In the next step, for each trajectory27a hidden Markov model (HMM) is produced that has as hidden states the edges13of the generated graph G and has as emitted observations the trajectory points. The HMM is solved using the Viterbi algorithm and yields the most probable allocation of each measurement point to a lane23:

As evaluation measure, the Euclidean distance Ydbetween the trajectory and the lane according toFIG. 8A, as well as the enclosed driving angle Yαaccording toFIG. 8Bare evaluated. In addition, a boundary value for the minimum number of transits is introduced. Yfdescribes a jump function that has the effect that lanes having too few transits are rated as unreliable and the configuration is rejected. In general, the definition of the function is a function of the overall number of transits, and may be realized such that a particular value is evaluated as the normal number, and a deviation from this results in rejection. The first term of the evaluation metric is thus given by:

The jump function for taking into account the transits is defined as:

where L(ξ) describes the lanes of the model, xT describes the number of trajectories mapped onto the xth lane, and η describes the minimum number of transits to be reached.

In πpl, previous knowledge about lane-accurate models28,34is taken into account. In order to keep the road segments and intersections19realistic, regularization terms are introduced that influence the development of the properties. Here, the width of a lane and the length of a block are regulated:

With regard to lane width w, a normal distribution is assumed whose parameters are to be selected in the context of the scenario. Characteristic variables for different scenarios can be taken from various guidelines for road construction.

In this method, overfitting would arise from a stringing together of very short road segments26. In order to counteract this, a minimum length for a road segment is introduced, realized by the regulation with the aid of a jump function:

After all road models28and intersection models35have been initialized, the method can be varied using the defined RJMCMC change operations40,41,42,43,44,46,48,50. For this purpose, a target function

is ascertained that determines both the agreement between the trajectory data27and the models28,34in πdland also existing knowledge concerning developments that are to be avoided and that are to be reinforced of models28,34in πpl, where δ∈[0; 1] determines the ratio between the data knowledge and the model knowledge.

A corresponding algorithm for carrying out the method according to the present invention can be divided into a warm-up phase and a main phase. In the warm-up phase, for example not all change operations40,41,42,43,44,46,48,50may be available; rather, it is possible for only distance adaptation operation46of road model28or intersection model34to be used. The problem that this measure addresses occurs when there are roads having a large constructive separation: given an equally justified selection of the operations and an initial model not having the constructive separation, the method can quickly produce a model having a large number of lanes. It then takes many iterations to exchange the superfluous lanes23for a constructive separation. The warm-up phase can make it possible to achieve a better initial estimation of the separation in very few iterations.

In addition, the so-called simulated annealing method can be used, whose purpose is to influence the above-described target function as a function of the run time:

where the function tSA(n)(ξ) for each cell represents a cooling function with

As a result, the formation of the Markov chain can concentrate on better-evaluated regions of the target function. In practice, this means that change operations that make the evaluation worse as the runtime progresses are more rarely accepted. The value of the cooling function decreases as soon as a proposed change operation is rejected. The cooling function is an exponentially decreasing function:

where the parameter λ is selected such that a specified number of steps s are required to reach a temperature eps≈0. For this purpose, the function is transformed into a calculating rule as a function of the number of steps:

In addition, it is to be noted that “including” does not exclude any other elements, and “a” or “one” does not exclude a plurality. In addition, it is to be noted that features that have been described with reference to one of the above exemplary embodiments can also be used in combination with other features of other exemplary embodiments described above. Reference characters in the claims are not to be regarded as limiting.