METHOD AND APPARATUS FOR PRODUCING A LANE-ACCURATE ROAD MAP

Abstract

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.

Claims

1-12. (canceled)

13. A method for producing a lane-accurate road map, the method comprising the following steps: providing a digital road-accurate road map for describing a 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 the at least one road, with segmenting of 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; randomly varying 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 to change parameter values; assigning at least a part of the trajectory data of the trajectory data record to the road model, including ascertaining at least one probability value for the road model, the probability value correlating with a quality of a mapping 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; and producing a lane-accurate road map based on the optimal parameter values of the road model.

14. The method as recited in claim 13, wherein the optimal parameter values are ascertained based on a Monte Carlo method.

15. The method as recited in claim 14, wherein the Monte Carlo method is a reversible jump Markov chain Monte Carlo method.

16. The method as recited in claim 13, wherein: 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; and/or 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, 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 describe a connection between individual lanes within the road segment.

17. The method as recited in claim 13, wherein the modeling of the road segment in the road model includes 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 the road segment into at least one road block and at least one connection block of the road model; modeling a disappearance or a production of a lane within the road segment based on at least one geometrical parameter matrix of the connection block; modeling a connection of individual lanes within the road segment based on at least one topological parameter matrix of the connection block; and 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.

18. The method as recited in claim 13, wherein the digital road-accurate road map has at least one intersection and a plurality of roads connected to the intersection, the method further comprising the following steps: identifying the at least one intersection with segmenting of the road-accurate road map into at least one intersection segment; modeling 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; randomly varying 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 to change parameter values; assigning at least a part of the trajectory data of the trajectory data record to the intersection model, including ascertaining at least one probability value for the intersection model, the probability value correlating with a quality of a mapping of the trajectory data by the intersection model; ascertaining, based on the ascertained at least one probability value, optimal parameter values of at least a part of the parameters of the intersection model; and producing a lane-accurate road map based on the optimal parameter values of the intersection model.

19. The method as recited in claim 18, wherein: the intersection model has an external intersection model for modeling a navigable intersection surface of the intersection, based on a distance parameter and an angle parameter; and/or 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; ascertaining a number of edges, connected to the intersection node, of the road-accurate road map, including ascertaining of a number of roads connected to the intersection; and generating a number of intersection arms that corresponds to the number of roads connected to the intersection, each of the intersection arms being defined by a distance parameter for indicating a distance of a center of the intersection from a limit surface of the intersection along the respective intersection arm, each of the intersection arms being defined by an angle parameter for indicating an angle of rotation between the respective intersection arm and a reference direction.

20. The method as recited in claim 18, wherein: the intersection model had an internal intersection model for modeling, based on a factor matrix of the intersection model, lanes leading into the intersection, lanes leading out from the intersection, and a course of lanes over an intersection surface of the intersection; and/or the step of modeling of the intersection segment in the intersection model includes the following substeps: modeling at least a part of lanes leading into the intersection, at least a part of lanes leading out from the intersection, and a course of at least a part of lanes leading over the intersection surface of the intersection, based on a factor matrix, values of the factor matrix describing a course and a connection of lanes over the intersection surface; and ascertaining values of the factor matrix based on at least a part of the trajectory data of the trajectory data record.

21. The method as recited in claim 13, wherein the road model and/or an intersection model each have a number parameter for describing a number of lanes, a width parameter for describing a width of individual lanes, a curvature parameter for describing a curvature of a road, and a distance parameter for describing a distance between lanes having opposite directions of travel.

22. The method as recited in claim 13, wherein the road model and/or an intersection model include: at least one change operation selected from the list made up of: an insert operation for inserting a connection block into a road block, a fuse operation for fusing two road blocks and a connection block to form a 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 remove 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.

23. The method as recited in claim 13, the method further comprising the following step: rejecting or accepting parameter values varied randomly based on the random selection of a change operation, and/or based on an evaluation metric that describes the quality of the mapping of the trajectory data by the road model and/or based on an intersection model; wherein the evaluation metric has a first term for describing an agreement between the trajectory data and the road model and/or an intersection model; wherein the evaluation metric has a second term for taking into account at least one prespecified characteristic variable of a road geometry, the characteristic variable relating to a lane width and/or a road width.

24. A data processing device for ascertaining a lane-accurate road map based on a digital road-accurate road map, the data processing device being configured to: provide a digital road-accurate road map for describing a course of at least one road; provide a trajectory data record that has a plurality of trajectory data of traffic participants along the at least one road; identify the at least one road, with segmenting of the road-accurate road map into at least one road segment; model 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; randomly vary 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 to change parameter values; assign at least a part of the trajectory data of the trajectory data record to the road model, including ascertaining at least one probability value for the road model, the probability value correlating with a quality of a mapping of the trajectory data by the road model; ascertain, based on the ascertained at least one probability value, optimal parameter values of at least a part of the parameters of the road model; and produce a lane-accurate road map based on the optimal parameter values of the road model.

25. The data processing device as recited in claim 24, wherein the data processing device has a data storage device for storing the digital road-accurate road map and a processor.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0056] Below, exemplary embodiments of the present invention are described in detail with reference to the Figures.

[0057] FIG. 1 shows a data processing device according to an exemplary embodiment of the present invention.

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

[0059] FIGS. 3A through 3D each illustrate a method for producing a road-accurate road map.

[0060] FIGS. 4A through 4C each illustrate steps of a method for producing a lane-accurate road map according to an exemplary embodiment of the present invention.

[0061] FIGS. 5A through 5C each illustrate a road model according to an exemplary embodiment of the present invention.

[0062] FIGS. 6A through 6D each illustrate an intersection model according to an exemplary embodiment of the present invention.

[0063] FIGS. 7A through 7E each illustrate change operations according to an exemplary embodiment of the present invention.

[0064] FIGS. 8A and 8B each illustrate an application of an evaluation metric according to an exemplary embodiment of the present invention.

[0065] 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

[0066] FIG. 1 shows a data processing device 10 according to an exemplary embodiment of the present invention.

[0067] Data processing device 10 has a data storage device 12. In data storage device 12, for example a road-accurate road map 14 can be stored that can have at least one node 11 (see, e.g., FIG. 3C and 3D) and/or an edge 13 (see, e.g., FIG. 3C and 3D), for describing a course of a road 17 (see FIG. 4A) and/or an intersection 19 (see FIG. 4A). In particular, road-accurate road map 14 can have a plurality of nodes 11 and/or edges 13 for describing a road network having a plurality of roads 17 and/or intersections 19. In data storage device 12, a trajectory data record 16 can also be stored that can have a plurality of trajectory data 27 (see FIG. 3B) from traffic participants.

[0068] Alternatively or in addition, data processing device 10 can have an interface 15 via which lane-accurate road map 14 and/or trajectory data record 16 of data processing device 10 can be provided. Interface 15 can for example be realized wirelessly, so that road-accurate road map 14 and/or trajectory data record 16 can 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.

[0069] In addition, data processing device 10 has at least one processor 18. On processor 18, a program element, for example stored in data storage device 12, can be carried out that instructs data processing device 10 and/or processor 18 to carry out the method according to the present invention for producing a lane-accurate road map 22 as described above and in the following.

[0070] Optionally, data processing device 10 can have an operating element 20 for inputting an operating input, for example by a user. The operating element can additionally have a display element 21 for displaying the road-accurate road map 14, the lane-accurate road map 22, and/or the trajectory data record 16.

[0071] FIG. 2 shows a flow diagram illustrating steps of a method for producing a lane-accurate road map 22 according to an exemplary embodiment of the present invention.

[0072] In a first step S1, a digital road-accurate road map 14 is provided for describing a course of at least one road 17 and/or at least one intersection 19, for example via data storage unit 12 and/or via interface 15 of data processing device 10. In particular, road-accurate road map 14 can have a plurality of roads 17 and intersections 19. In addition, in step S1 a trajectory data record 16 is provided that has a plurality of trajectory data 27 of traffic participants along the at least one road 17 and/or the at least one intersection 19. Trajectory data record 16 can also be provided via data storage unit 12 and/or via interface 15 of data processing device 10.

[0073] In a step S2, the at least one road 17 is identified, with segmenting of the road-accurate road map 14 into at least one road segment 26 (see FIG. 4C). This can take place based on nodes 11 and/or edges 13 of road-accurate road map 14. Optionally, in step S2 at least one intersection can take place by segmenting of road-accurate road map 14 into at least one intersection segment 19a. In particular, in step S2 the road-accurate road map 14 can be subdivided into a plurality of road segments 26 and a plurality of intersection segments 19a.

[0074] In a further step S3, the at least one road segment 26 is modeled in at least one road model 28 (see FIG. 5A, 5B). In particular, in step S2 all road segments 26 can each be modeled in a road model 28. In addition, in step S3 the at least one intersection 19 can be modeled in an intersection model 34 (see FIGS. 6A-6C). In particular, each of the intersections 19 can be modeled in a separate intersection model 34. Each of the road models 28 and/or each of the intersection models 34 has a plurality of parameters for the geometrical and/or topological description of lanes 23.

[0075] In a further step S4, parameter values of at least a part of the parameters of road model 28 and/or of intersection model 34 are varied through random selection of a change operation 40, 41, 42, 43, 44, 46, 48, 50 (see FIG. 7A-7E) of road model 28 and/or of intersection model 34. In particular, in step S4 the parameter values of all road models 28 and of all intersection models 34 can be varied multiply and iteratively.

[0076] In a further step S5, at least a part of the trajectory data 27 of trajectory data record 16 is assigned to road model 28, with ascertaining of at least one probability value for road model 28. In particular, in step S5 the trajectory data 27 can be assigned to each of the road models 28, with ascertaining in each case of at least one probability value for each of the road models 28. In addition, in step S5 the trajectory data 27 can be assigned to the at least one intersection model 34, by ascertaining at least one probability value in step S5 the trajectory data 27 can be assigned to each of the intersection models 34 by ascertaining in each case at least one probability value for each of the intersection models 34. The probability values correlate with the quality of a mapping of the trajectory data 27 by the respective road model 28 and/or the respective intersection model 34.

[0077] 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 model 28 and/or of intersection model 34. In particular, optimal parameter values can be ascertained for each of the road models 28 and/or for each of the intersection models 34.

[0078] In a step S7, a lane-accurate road map 22 is produced based on the optimal parameter values of the at least one road model 28 and/or of the at least one intersection model 34. In particular, the lane-accurate road map 22 can be given by the optimal parameter values of all road models 28 and/or all intersection models 34.

[0079] FIGS. 3A through 3D each illustrate a method for producing a road-accurate road map 16. The road-accurate road map 16 produced in this way can be used as a basis for the production of a lane-accurate road map 22. Correspondingly, all the steps described in relation to FIGS. 3A through 3D can also be part of the method according to the present invention for producing a lane-accurate road map 22.

[0080] FIG. 3A illustrates a trajectory data record 16 having a plurality of collected trajectory data 27 and/or trajectories 27. In addition, FIG. 3A illustrates a segmenting and/or division of the trajectory data 27 into various traffic scenarios and/or segments 24a-c. FIG. 3A schematically shows a first segment 24a, which describes a curve, a second segment 24b, which describes an intersection, and a third segment that describes a road. Segments 24a-c are here ascertained as described in the following.

[0081] The trajectory data 27 collected from a fleet of vehicles, for example GNSS trajectories 27, 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, trajectories 27 can be partitioned in automated fashion according to a logical system. For this purpose, trajectory data 27, which can also be referred to as input data, can be divided into different traffic scenarios 24a-c and/or different segments 24a-c, where each of the segments 24a-c can describe a straight road, a curve, or an intersection.

[0082] In an automated method, each trajectory 27 can 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 situation 24a-c and/or a segment 24a-c. The segments 24a-c can be interpreted as, as it were, cells 24a-c of the decomposition.

[0083] Based on a set of trajectory data 27, such as GNSS trajectory data 27, a road-accurate road map 14 can be produced that can correspond to a graph made up of nodes 11 and edges 13, where nodes 11 and edges 13 can represent a center line of the road. As an example, such a road-accurate road map 14 is illustrated in FIG. 3D.

[0084] In order to produce road-accurate road map 14, first the input data 16, 27 can be segmented, as described for FIG. 3A. For each cell 24a-c a graph can subsequently be initialized that can describe the traffic scenario of the respective segment 24a-c, or cell 24a-c. The goal here is to enable the models in the cells 24a-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 map 14 is shown in FIGS. 3B-3D for road segment 24c from FIG. 3A. Here, FIG. 3B shows a cell 24c, or segment 24c, and vehicle trajectories 27. FIG. 3C shows an initial road map 14, and FIG. 3D shows an optimized road map 14. Road maps 14 of FIGS. 3C and 3D can also be designated cell graph 14.

[0085] For the initialization, first all cell boundaries 25 can be intersected with trajectories 27 in order to ascertain the road centers at the cell edges 25, as shown in FIG. 3B. These centers can be plotted in the graphs of the corresponding cells 24c as nodes 11, as shown in FIG. 3C. In addition, in each cell 24c the focal point of cell 24c can be inserted into the graph as node 11, and can be connected by edges 13 to nodes 11, at cell edges 25.

[0086] In order to link the trajectory data 27 and 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 data 27, 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 map 16, as shown in FIG. 3D, a reversible jump Markov chain Monte Carlo (RJMCMC) method can be used. Here, the trajectory data 27 are 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 data 27, 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 node 11 of a cell graph 24c is moved in space. The producing operation describes the addition of a new node 11 in graph 24c, and forms a reversible pair of operations together with the remove operation. The fuse operation inserts a node 11 into an adjacent edge 13, so that two edges 13 situated 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 of FIGS. 3C and 3D, during the optimization the center node 11 is removed, because it is not required for the description of road 17.

[0087] FIGS. 4A through 4C each illustrate steps of a method for producing a lane-accurate road map 22 according to an exemplary embodiment of the present invention. Specifically, in FIG. 4A a road-accurate road map 14 is shown. FIG. 4B illustrates a parameterization, and FIG. 4C illustrates a segmenting of road 17 of road map 14. In addition, FIGS. 5A through 5C each show a road model 28 according to an exemplary embodiment of the present invention. Specifically, FIG. 5A shows a connection block 30 of road model 28, FIG. 5B shows a road block 32 of road model 28, and FIG. 5C shows geometrical and topological parameter matrices of connection block 30 of FIG. 5A.

[0088] FIG. 4A shows a road-accurate graph 14 and/or a road-accurate road map 14, describing a road 17 and, at each of the ends, an intersection 19, using nodes 11 and edges 13. In order to transfer road 17 into a lane-accurate road map 22, road 17 is first parameterized one-dimensionally. In this way, as is shown in FIG. 4B, each point p of road 17 can be described via a value p[0; 1] of the unit interval.

[0089] Based on this parameterization, road segments 26 can be defined, as shown in FIG. 4C. In other words, road 17 is divided into one or more road segments 26 that can be identified for example based on nodes 11 and/or edges 13.

[0090] The segmenting of road 17 into road segments 26 can make it possible to describe traffic situations at the lane level in road model 28, as is illustrated in FIGS. 5A through 5C. Here, driving on a constant number of lanes 23 is distinguished from the widening or narrowing of road 17 by a lane 23.

[0091] A general road block 32, as shown in FIG. 5B, can have a number parameter L for describing the number of lanes 23, a width parameter W for describing a width of individual lanes 23, a curvature parameter C for describing a curvature of a road 17, and a distance parameter G for describing a distance between adjacent lanes 23 having opposite directions of travel. Road block 28 can also have a type parameter T for describing a type of a roadway marking for each lane 23. Parameter G can be a size of a constructive separation between the lanes 23 traveling in opposite directions.

[0092] A general road block 32 can thus be defined by the variable

B=(L,W,T,G,C).

[0093] A road 17 is thus defined as a set .sub.s of m road segments 26 and their parameterization values P, which describe the longitudinal extension on road 17, according to FIGS. 4A through 4C:

.sub.s=({P.sub.1, . . . ,P.sub.m+1},{B.sub.1, . . . ,B.sub.m})

[0094] In order to represent a curved road segment 26, all connections of lanes 23 on road segment 26 can be described by cubic Hermite polynomials. In this way, it is possible for a road segment 26 not 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 model 28.

[0095] A general road block 32, also designated B, in the following, can be specified through further limitations or supplementations. A road block 32, as shown in FIG. 5B, contains the limitation that the number L of lanes 23 in the respective road segment 26 remains constant. In this way, a segment of road can be mapped on which only the inherent properties change, such as lane width W. In FIG. 5B, lanes 23 are 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.

[0096] A connection block 30, also designated B.sub.c, in the following, as shown in FIG. 5A, describes a traffic situation in which the number L of lanes 23 changes, and in which a combination or splitting of lanes 23 can therefore be modeled. Therefore, connection block 30 is supplemented, relative to road block 32, through a connection permutation R=(R.sub.GR, R.sub.TR, R.sub.GL, R.sub.TL), which both geometrically describes which lane 23 disappears, or is produced, and also topologically defines which lanes 23 are connected. As shown in FIG. 5C, for each direction of travel an individual geometrical parameter matrix R.sub.GR, R.sub.GL, and a topological parameter matrix R.sub.TR, R.sub.TL, are indicated. An existing item of information, or connectedness, of lanes 23 is illustrated in binary fashion by a one, and non-connectedness is illustrated by a zero, as shown in FIG. 5C. Also, in FIGS. 5A and 5C lanes 23 are identified with characteristic values 1, 2, +1, +2, where the sign indicates a direction of travel and the lanes 23 of each direction of travel are numbered with progressive natural numbers 1, 2. For example, in the situation shown in FIG. 5A it 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 block 30 can therefore be defined as

B.sub.c=(BR).

[0097] In addition to these limitations of road model 30, it can in addition be provided that a connection block 30 is situated between two road blocks 32, in order to compensate, if needed, the differences between road blocks 32 (e.g. with regard to number of lanes L). If no changes are necessary, connection block 30 can be a special case of a road block 32.

[0098] FIGS. 6A through 6D each illustrate an intersection model 34 according to an exemplary embodiment of the present invention. Specifically, FIGS. 6A and 6B show an external intersection model 36 of intersection model 34, FIG. 6C shows an internal intersection model 38 of intersection model 34, and FIG. 6D shows a factor matrix F of the internal intersection model of FIG. 6C.

[0099] In the previous representation of a road map 14, as shown for example in FIG. 4A, an intersection 19 was represented by a node 11 that is connected to more than two edges 13. For the lane-accurate mapping and/or modeling of an intersection 19, both geometrical information about an intersection surface 37 and/or a navigable surface 37, or intersection surface 37, and also topological information about the connectivity of the incoming and outgoing lanes 23 and their path over intersection surface 37 are required. For this purpose, road-accurate road map 14 is first segmented into at least one intersection segment 19a, and/or an intersection segment 19a is identified in road-accurate road map 14. Intersection segment 19a is then modeled in an internal intersection model 38 and an external intersection model 36, as is explained in more detail below.

[0100] Intersection model 34, in the following also designated .sub.c, is made up of two different individual models. In FIGS. 6A and 6B, an external intersection model 36, in the following also designated .sub.c,o, is shown. For the initialization, nodes 11 of road-accurate road map 14 are examined, and intersection nodes 35 are identified on the basis of the connected edges 13. Because a large intersection 19 in road-accurate road map 14 can be described by a plurality of nodes 11, if necessary a plurality of nodes 11 can be combined with the aid of a distance value d.sub.cr. External intersection model 36 can be produced at the center of the involved nodes 11. On the basis of the identified intersection nodes 35, the information can be gained directly as to how many roads 17 are connected to intersection 19. For each road 17, an intersection arm A1-A4 is produced. Each intersection arm A1-A4 has a distance parameter d that describes the distance from the center to the beginning of intersection surface 37 in 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 road 17 into intersection surface 37 is defined for each intersection arm A1-A4.

[0101] The internal intersection model 38, also designated .sub.c,i in the following, is illustrated in FIGS. 6C and 6D. Internal intersection model 38 describes the connectivity of lanes 23. Each intersection arm A1-A4 here has the same information as a general road block 32 of road model 28, thereby defining the geometry of the connected roads 17. Between each incoming and outgoing lane 23 there 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 surface 37. Parameter C is stored in factor matrix F, as is shown in FIG. 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 surface 37 are 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 in FIG. 6D. In addition, lanes 23 of individual intersection arms A1-A4 in FIG. 6D are progressively numbered with natural numbers.

[0102] In the following, details are described of the road model 28 described in the preceding Figures, in particular FIGS. 4A through 6D, of intersection model 32, and the method according to the present invention for producing lane-accurate road map 22.

[0103] For the initialization of models 28, 34, road-accurate road map 14 is divided into roads 17 and intersections 19. At each intersection 19, an initial intersection model 35 is produced having an arm distance of d.sub.init=25 m, where the number of connected roads 17, and thus the angle parameters a of intersection arms A1-A4, are determined from road map 14. Subsequently, road models 28 between intersections 19 are generated, where a road 17 is described in the graph by a chain {v.sub.x, . . . , v.sub.y}. In the lane-accurate road model 28, a connection block 30 is produced at each node 11, and between them a road block 32 is produced. Each road 17 begins and ends with a connection block 30 that can, if necessary, correct the differences between the adjoining road block 32 and the intersection connection. Each road 17 is initialized as having two lanes, with one lane 23 per direction of travel. The totality of the a road models 28 and b intersection models 34 is designated in the following as ={.sub.s.sup.1, . . . , .sub.s.sup.a.sub.c.sup.1, . . . , .sub.c.sup.b}.

[0104] The initialized models 28, 34, represent the current configuration of the overall model. The parameters of these models are the described properties or parameters of road blocks 32, of connection blocks 30, of internal intersection models 36, and of external intersection models 38. 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 models 28, 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 model 28, 30, 32, 34, 36, 38.

[0105] FIGS. 7A through 7E each illustrate change operations 40, 41, 42, 43, 44, 46, 48, 50 according to an exemplary embodiment of the present invention. Specifically, FIG. 7A illustrates, at the left, an insert operation 40 for inserting a connection block 30 into a road block 32, and a fuse operation 41 for fusing two road blocks 32 and a connection block 30 to form a road block 32, as a reversible change operation 41 to insert operation 40. In addition, at the right FIG. 7A illustrates an adaptation operation 42 for adapting a parameterization value for parameterizing a longitudinal extension of a road 17. FIG. 7B illustrates an addition operation 43 for adding a lane 23 and a removal operation 44 for removing a lane 23. In addition, FIG. 7C shows a distance adaptation operation 46 for adapting a distance G between lanes 23 having opposite directions of travel, FIG. 7D shows a width adaptation operation 48 for adapting a width W of a lane 23, and FIG. 7E shows a curve adaptation operation 50 for adapting a curvature C of a road 17.

[0106] With regard to a road model 28, the change operations 40, 41, 42, 43, 44, 46, 48, 50 are further divided into two classes. Insertion operation 40, fusing operation 41, and adaptation operation 42, as shown in FIG. 7A, change road model 28 at the block level; i.e. the individual properties are not changed, but rather only the number of road blocks 32 and connection block 30, and their spatial extension, are changed. In addition operation 43, an existing road block 32 is divided into two road blocks 32 and one connection block 30. Remove operation 44 correspondingly connects such a constellation, and forms with addition operation 43 a reversible pair whose selection probabilities can be selected such that the expanded detailed balance condition is met. Adaptation operation 42 changes the limits of a road block 32 and/or connection block 30 with regard to the parameterization of road model 28. Addition operation 43, remove operation 44, distance adaptation operation 46, width adaptation operation 48, and curvature adaptation operation 50 change the properties or parameter values of a road block 32.

[0107] The parameter values of a road block 30 cannot be changed actively, but only passively. They adapt their parameters to the adjoining road blocks 32. The addition operation 43 for adding a lane 23, and a remove operation 44, likewise form a reversible pair, while the three adjustment operations 42, 46, 50 merely change the values of the parameters.

[0108] In order not to prefer any of the change operations 40, 41, 42, 43, 44, 46, 48, 50 in the random variation of parameter values of road model 28 and/or of intersection model 34, or to select each of the change operations 40, 41, 42, 43, 44, 46, 48, 50 with equal probability, the selection probabilities .sub.40, .sub.41, .sub.42, .sub.43,.sub.44, .sub.46, .sub.48, .sub.50 of all change operations 40, 41, 42, 43, 44, 46, 48, 50 are assumed to be identical:

.sub.40=.sub.41=.sub.42=.sub.43=.sub.44=.sub.46=.sub.48=.sub.50, where

.sub.=1

[0109] In the following, the individual change operations 40, 41, 42, 43, 44, 46, 48, 50 are considered in more detail.

[0110] The transition from the representation at top in FIG. 7A to the representation at left in FIG. 7A takes place via insertion operation 40. The longitudinal extension of road block 32 to be divided, B.sub.s is defined via the parameterization P of road model .sub.s with the values (p.sub.s, p.sub.e)P, with the parameterized length p.sub.1=p.sub.ep.sub.s. For the division, two new values u.sub.1,u.sub.2[0,p.sub.l]

[0111] on this length are required, with u.sub.1<u.sub.2:

.sub.40(P,u.sub.1, u.sub.2)=(P,p.sub.s+u.sub.1p.sub.s+u.sub.2),

with P={p.sub.1, . . . ,p.sub.s,p.sub.s+u.sub.1,p.sub.s+u.sub.2,p.sub.e, . . . ,p.sub.m+1},

u.sub.1,u.sub.2q.sub.40(s.sup.(n+1)|s.sup.(n))=U(0,p.sub.i)

[0112] The probability of acceptance is determined as:

[00001]$A_{40}\left(s^{}{s}^{\left(n\right)},\stackrel{.fwdarw.}{u}\right)=\min .Math.\left\{1,\frac{\left(s^{}\right)}{.Math..Math.\left(s^{\left(n\right)}\right)}.Math.\frac{.Math.\left({}_{40}\right)}{p_l^2}\right\}.$

[0113] The Jacobi matrix of the transformation is

[00002]$.Math.\left({}_{40}\right)=\left(\begin{array}{ccc}1& 0& 0\\ \frac{\left(p_s+u_1\right)}{P}& 1& 0\\ \frac{\left(p_s+u_2\right)}{P}& 0& 1\end{array}\right)$

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

[0114] Fusing operation 41 can be regarded as the converse case. The constellation of road block 32, connection block 30, road block 32 is combined, and for the transformation no new components are required, but rather are calculated. The constellation is defined in the parameterization P of road model 28, by the sequence {p.sub.a, p.sub.b, p.sub.c, p.sub.d}. The acceptance probability is:

A.sub.41(s|s.sup.(n))=A.sub.41(s.sup.(n)|s,{right arrow over (u)}).sup.1,

with u.sub.1=p.sub.bp.sub.a,u.sub.2=p.sub.cp.sub.a.

[0115] Adaptation operation 42 describes, as transition between the upper representation in FIG. 7A and the representation at right in FIG. 7A, the change of one of the two parameterization values of a road block 32. Here, the parameter can be changed by a maximum of half the parameterized length p.sub.1 of road block 32. In order not to prefer a direction of movement, the search function is realized as a random movement:

[00003]$.Math..Math.p{q}_{42}\left(s^{\left(n+1\right)}{s}^{\left(n\right)}\right)=U\left(-\frac{p_l}{2},\frac{p_l}{2}\right).$

[0116] In order to insert a new lane width addition operation 43, as shown in FIG. 7B, road model 28 is supplemented by a new lane width of a lane 23. 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 road 17. For the transformation there follows:

.sub.43(W,u)=(W,u)

uq.sub.43(s.sup.(n+1)|s.sup.(n))=N(.sub.43,.sub.add.sup.2).

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

[00004]$A_{43}\left(s^{}{s}^{\left(n\right)},u\right)=\min .Math.\left\{1,\frac{\left(s^{}\right)}{.Math..Math.\left(s^{\left(n\right)}\right)}.Math.\frac{.Math..Math.\left({}_{43}\right).Math.}{\sqrt{2.Math..Math.{}_{43}^2}}.Math.e^{-\frac{{\left(u-u_{43}\right)}^2}{2.Math..Math.{}_{43}^2}}\right\}.$

[0118] The acceptance probability for the opposite, removal operation 44 is calculated correspondingly, where the component u is the lane width of lane 23 to be removed:

A.sub.44(s|s.sup.(n))=A.sub.44(s.sup.(n)|s,u).sup.1.

[0119] The three change operations 46, 48, 50 shown in FIGS. 7C, 7D, 7E change the existing parameter values of road model 28 and of the intersection model. Therefore, the corresponding search functions are realized as an equal distribution:

gq.sub.46(s.sup.(n+1)|s.sup.(n))=U(0,.sub.46)

wq.sub.48(s.sup.(n+1)|s.sup.(n))=U(0,.sub.48)

cq.sub.50(s.sup.(n+1)|s.sup.(n))=U(0,.sub.50)

[0120] Because intersection model 34 is made up of internal intersection model 36 and external intersection model 38, there are different change operations for each submodel 36, 38. As shown in FIGS. 6A and 6B, the two parameters distance d and angle a influence the form of external intersection model 36. The number of intersection arms A1-A4 is already extracted from road map 14 in 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 model 36. 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:

dq.sub.d(s.sup.(n+1)|s.sup.(n))=U(0,.sub.d)

q.sub.a(s.sup.(n+1)|s.sup.(n))=U(0,.sub.a)

[0121] In internal intersection model 38, each intersection arm A1-A4 has a connection cross-section that has the same properties as a road block 32. Because a connection block 30 is connected to each intersection arm A1-A4, this block reacts to the changes in intersection arm A1-A4 exactly as it does to changes in a road block 32. Therefore, the change operations for varying the connection properties are identical to the already defined operations of a road block 32. In other words, the internal intersection model 38 has the above-described change operations 40, 41, 42, 43, 44, 46, 48, 50. The influencing of the factor matrix F from FIG. 6D is not done through an RJMCMC operation.

[0122] FIGS. 8A and 8B each illustrate an application of an evaluation metric according to an exemplary embodiment of the present invention.

[0123] For the evaluations, on the one hand a measure is taken into account concerning the agreement between road model 28 and/or intersection model 34 and the trajectory data 27, in a first term .sub.d.sup.l, and on the other hand previous knowledge about the models 28, 34 is taken into account in a second term .sub.p.sup.l. In the following, these measures are presented.

[0124] In the first step, the vehicle trajectories 27 are mapped onto lanes 23. For this purpose, first each center line of each road segment 26 and of each intersection 19 is transferred into a graph, the center line being discretized in small steps with nodes 11 and edges 13. Each graph is subsequently optimized to a minimum number of nodes 11, using the Douglas-Peucker algorithm. Subsequently, these graphs are fused to form an overall representation G.

[00005]${}_d\left(e_n,t_n\right)=p\left(t_n{e}_n\right)=p\left(d_n\right)=\frac{1}{\sqrt{2.Math..Math.{}_t^2}}.Math.e^{-\frac{1}{2}.Math.{\left(\frac{d_n}{{}_t}\right)}^2}$

[0125] In the next step, for each trajectory 27 a hidden Markov model (HMM) is produced that has as hidden states the edges 13 of 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 lane 23:

[00006]${}_{}\left(\left(e_n\right),\left(t_n\right)\right)=p\left(\left(t_n\right)\left(e_n\right)\right)=p\left({}_n\right)=\frac{1}{\sqrt{2.Math..Math.{}_{}^2}}.Math.e^{-\frac{1}{2}.Math.{\left(\frac{{}_n}{{}_{}}\right)}^2}.$

[0126] As evaluation measure, the Euclidean distance Y.sub.d between the trajectory and the lane according to FIG. 8A, as well as the enclosed driving angle Y.sub. according to FIG. 8B are evaluated. In addition, a boundary value for the minimum number of transits is introduced. Y.sub.f describes 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:

[00007]${}_d^l=\underset{tT}{.Math.}.Math..Math.\underset{nm}{.Math.}.Math.\left[\log .Math..Math.\left({}_d\left(G\left(t_n\right),t_n\right)\right)+\log \left({}_{}\left(\left(G\left(t_n\right)\right),t_n\right)\right)\right]+\underset{}{.Math.}.Math.\log .Math..Math.\left({}_f\left(,T\right)\right).Math..Math..Math.G\left(t_n\right)=\arg .Math..Math.\underset{\stackrel{\_}{e}G}{\max }.Math.p\left(\stackrel{\_}{e}{t}_n\right)=e_n$

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

[00008]${}_f\left(,T\right)=\{\begin{array}{cc}1,& \mathrm{if}.Math..Math.\underset{xL\left(\right)}{.Math.}.Math..Math.x.Math..Math.T>\\ 0,& \mathrm{otherwise}\end{array}$

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.

[0128] In .sub.p.sup.l, previous knowledge about lane-accurate models 28, 34 is taken into account. In order to keep the road segments and intersections 19 realistic, 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:

.sub.p.sup.l=.sub.p,lanewidth.sup.l+.sub.p,roadsegmentlength.sup.l

[0129] 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.

[00009]${}_{p,\mathrm{lanewidth}}^l=\log \left(\frac{1}{\sqrt{2.Math..Math.{}_{l.Math..Math.w}^2}}.Math.e^{-\frac{{\left(w-{}_{\mathrm{lw}}\right)}^2}{{}_{l.Math..Math.w}^2}}\right)$

[0130] In this method, overfitting would arise from a stringing together of very short road segments 26. 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:

[00010]${}_{p,\mathrm{roadsegmentlength}}^l=\log .Math.\{\begin{array}{cc}1,& \mathrm{if}.Math..Math.\mathrm{roadsegmentlength}>\\ 0,& \mathrm{otherwise}\end{array}$

[0131] After all road models 28 and intersection models 35 have been initialized, the method can be varied using the defined RJMCMC change operations 40, 41, 42, 43, 44, 46, 48, 50. For this purpose, a target function

=.sub.d.sup.l+(1).sub.p.sup.l

[0132] is ascertained that determines both the agreement between the trajectory data 27 and the models 28, 34 in .sub.d.sup.l and also existing knowledge concerning developments that are to be avoided and that are to be reinforced of models 28, 34 in .sub.p.sup.l, where [0; 1] determines the ratio between the data knowledge and the model knowledge.

[0133] 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 operations 40, 41, 42, 43, 44, 46, 48, 50 may be available; rather, it is possible for only distance adaptation operation 46 of road model 28 or intersection model 34 to 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 lanes 23 for a constructive separation. The warm-up phase can make it possible to achieve a better initial estimation of the separation in very few iterations.

[0134] 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:

.sup.1/t.sup.SA.sup.(n).sup.()

where the function t.sub.SA.sup.(n)() for each cell represents a cooling function with

[00011]$\underset{n->}{\lim }.Math.t_{\mathrm{SA}}^{\left(n\right)}\left(\right)=0$

[0135] 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:

t.sub.SA.sup.(n)()=e.sup.n[0; 1],

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

[00012]$=-\frac{10.Math..Math.\log \left(\mathrm{eps}\right)}{s}$

[0136] 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.