GRAPH BASED TOPOLOGICAL MAP MATCHING

• US 20140132608A1
• Filed: 12/31/2010
• Published: 05/15/2014
• Est. Priority Date: 12/31/2010
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: TomTom Germany Gmbh & Co. Kg. (TomTom NV)
• Inventors: Mund, Heiko, Scharmann, Hannes
• Granted Patent: US 10,614,600 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

An improved method for matching traces derived from probe data to one or more line segments in a digital vector map. Points in a probe trace are provisionally matched one-by-one to line segments in the digital vector map to identify all possible matching candidates. A graph of the matching candidates is created having one or more paths. The graph has a plurality of sequential levels corresponding to the points in the probe trace. Each matching candidate is assigned to a level of the graph corresponding with trace point to which it relates. Edges are established between matching candidates in adjacent levels provided they are topologically related to one another. The graph is simplified and scored. The best paths deliver the matching results. The invention allows use of graph theoretic methods to find the best path through the graph, which in turn represents an efficient map matching algorithm. The concepts of this invention may be used in conjunction with longitudinal distance as matching criterion.

Claims

1. A method for matching traces derived from probe data to one or more line segments in a digital map, said digital map configured to store a plurality of line segments spatially associated within a coordinate system, the method comprising:

providing at least one probe trace having a plurality of spatially associated trace points located within the coordinate system of the digital map;

determining a matching candidate for each line segment within a specified distance of each trace point;

generating a graph with the matching candidates as nodes; and

selecting at least one path of matching candidates of the graph as a match result.

2. The method of claim 1, wherein two nodes of the graph are connected with an edge if a local topological connection exists between both matching candidates in the digital map.

3. The method of claim 1, wherein the graph has a plurality of sequential levels, each level corresponding to a probe trace point with adjacent trace points corresponding to adjacent levels in the graph.

4. The method of claim 1, further including scoring the graph.

5. The method of claim 4, wherein said scoring step includes establishing scoring

criteria based on at least one of the number of connected matching candidates in a path and the mean distance.

6. The method of claim 4, wherein the graph has a top and a bottom, and wherein said scoring step includes scoring from the graph top to the graph bottom.

7. The method of claim 4, wherein said scoring step includes removing connections with a smaller score to simplify the graph.

8. The method of claim 1, wherein the graph includes a plurality of paths, each path having respective end nodes, said step of selecting at least one path including selecting the path with the best end node score.

9. The method of claim 1, further including the step of simplifying the graph.

10. The method of claim 9, wherein said simplifying step includes removing at least one node having the same level like any node of a previously selected path from the graph.

11. The method of claim 9, wherein said simplifying step includes removing nodes with a distance between the matching candidate and the corresponding trace point greater than a predefined maximal distance.

12. The method of claim 9, wherein said simplifying step includes removing a node if an angle between the headings of the trace point and the line at the matching candidate is larger than a predefined angle limit.

13. The method of claim 9, wherein said simplifying step includes applying a hysteresis algorithm.

14. The method of claim 9, further including rescoring the path following said simplifying step.

15. The method of claim 1, further including the step of cloning a partial graph.