Field of the Invention
This invention relates generally to a method for analyzing probe data, and more particularly to a method of matching probe traces to a digital vector map.
Related Art
Roads in reality, like that illustrated in FIG. 1, are used to sustain traffic flow over land. Traffic flow may be either all in one direction, or bi-directional as shown in FIG. 1. Electronic maps (also known as digital maps or digital vector maps) are increasingly used by travelers to assist with various navigation functions, such as to determine the overall position and orientation of the traveler and/or vehicle, find destinations and addresses, calculate optimal routes, and provide real-time driving guidance. A digital map is configured to store a plurality of line segments spatially associated within a coordinate system. Each line segment, like that shown in FIG. 2, is composed of a sequence of edges connected together by shape points.
When associated with a road in reality, the line segment typically represents the road centerline as shown in FIG. 3. Within the digital map, the plurality of line segments are respectively topologically related or unrelated to one another. In general, related line segments adjoin one another so that traffic along the roads in reality is free to pass directly from one line segment to the next. Topologically unrelated line segments, on the other hand, are not directly connected and thus it is generally not possible for traffic along the roads in reality to pass directly between unrelated line segments. For example, FIG. 9 depicts overlapping line segments L1 and L4 that are topologically unrelated. Line segments L1, L2 and L3 on the other hand are topologically related to one another.
Digital maps are expensive to produce and update, since collecting and processing road information is very costly. Once a digital map has been created, it is costly to keep map information up to date, due to road geometry changes over time. Vehicle probe data may be used to hold road networks up-to-date. Vehicle probe data, also known as a probe trace, is a sequence of position data together with a timestamp and maybe additional data like speed, acceleration, heading, accuracy, etc. The individual position data are called trace points. A probe trace usually represents the movement of a car, bicycle, pedestrian, etc. The trace points are usually represented in a two or three dimensional coordinate system. The timestamp can be represented in an implicit way or can be omitted from the probe data. Often equidistant time intervals are used, in which case it is only necessary to store the time of the first trace point. If the time is not of interest the time information is maybe omitted. Thus, in the simplest case, a probe trace contains only the position data. With different approaches it is possible to generate a new network from probe data. New probe data which are available can be used in this manner to easily refine and extend a road network in a digital map system, provided the traces from such data can be suitably matched to a map.
Map matching algorithms are a key technology for digital map producers. They are necessary for nearly all applications of probe data, including attribute mining (e.g., speed profiles), network generation, network refinement and the detection of changes. Moreover map matching algorithms are needed in every navigation device in order to detect its current position on the navigation map. There exist already different map matching methods. One can distinguish on-line and off-line map matching algorithms. For on-line algorithms, only the current and the previous GPS points are available. On the contrary, off-line algorithms can use additionally some or even all future GPS points.
Furthermore one can distinguish between complete and incomplete map matching algorithms. A complete map matching allocates each trace point to any line segment. With this approach it is possible that a trace point is far away from the matched line segment. Therefore one has to assure that the digital vector map is complete. If this is not the case, one has to allow that a trace point is not allocated to a line segment in any case. Algorithms which allow such unmatched points are categorized as incomplete map matching techniques.
For different classes of algorithms, there exists different map matching methods. For the incremental network generation, the Applicant has developed the n-points map matching technique, described more fully in PCT/EP2009/063937, filed 22 Oct. 2009. This technique, known also as the Viae Novae algorithm, works very quickly and in the most cases we get very good results. However on complex crossings or intersections with short intermediate road elements the Viae Novae algorithm is sometimes not able to deliver always the correct result. Therefore a new and improved map matching algorithm is needed. Such an improved algorithm must exhibit a high matching quality, work well with incomplete road networks (e.g., missing roads, missing or wrong topological connections, etc.), and be very robust against GPS traces with insufficient quality (i.e., bad probe data) such as traces with point clouds (FIG. 4), traces with loops (FIG. 5), traces with zig-zags (FIG. 6) and outlier traces (FIG. 7), all of which occur frequently in probe data collections. Furthermore, an improved map matching algorithm must works with uni-directional and bi-directional networks.