METHODS AND APPARATUS FOR ROUTE COMPARISON

• US 20150369615A1
• Filed: 12/31/2013
• Published: 12/24/2015
• Est. Priority Date: 12/31/2012
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom Development Germany GmbH (TomTom NV)
• Inventors: Dzyuba, Tetyana
• Granted Patent: US 9,778,047 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/32 Structuring or formatting of map data

Abstract

Embodiments of the present invention provide a computer implemented method of route comparison, comprising receiving data indicative of first and second routes between a start location and a destination location wherein the first and second routes are generated using digital map data, determining nodes of the first and second routes having a minimum coupling distance, wherein the minimum coupling distance is determined based upon nodes of the first and second routes constrained to within a predetermined distance of a current node of each route, and determining a similarity index for the first and second routes based upon the minimum coupling distance and a threshold data coupling distance.

Claims

1. A computer implemented method of route comparison, comprising:

receiving, by the computer, data indicative of first and second routes between a start location and a destination location wherein the first and second routes are generated using digital map data;

determining, by the computer, nodes of the first and second routes having a minimum coupling distance, wherein the minimum coupling distance is determined based upon nodes of the first and second routes constrained to within a predetermined distance of a current node of each route; and

determining, by the computer, a similarity index for the first and second routes based upon the minimum coupling distance and a threshold coupling distance.

2. The method of claim 1, wherein the nodes having the minimum coupling distance are determined based upon the current node of each route and a predetermined number of further nodes of the route.

3. The method of claim 2, wherein the nodes having the minimum coupling distance are determined based upon the current node of each route and one further node of the route.

4. The method of claim 1, wherein the nodes having the minimum coupling distance are determined by calculating a coupling distance between the nodes of the first and second routes within the predetermined distance of the current node.

5. The method of claim 1, wherein the nodes having the minimum coupling distance are determined without calculating a coupling distance between all combinations of nodes of the first and second routes.

6. The method of claim 1, wherein the nodes having the minimum coupling are determined by calculating a coupling distance between only a subset of combinations of nodes of the first and second routes.

7. The method of claim 1, wherein determining nodes having the minimum coupling distance comprises selecting a node of each route from amongst the nodes within the predetermined distance of the current node of each route.

8. The method of claim 1, wherein the determining the similarity index for the first and second routes comprises comparing the coupling distance of each pair of nodes against the threshold coupling distance.

10. The method of claim 8, wherein the similarity index indicates a percentage of nodes within the threshold coupling distance.

11. The method of claim 1, wherein the first route is generated using a first map database and the second route is generated using a second map database.

13. The method of claim 1, comprising interpolating the data indicative of the first and second routes such that each route comprises a node at least every predetermined distance.

23. A non-transitory computer-readable medium comprising computer readable instructions which, when executed on a computer, is arranged to perform the method of claim 1.

24. The method of claim 1 further comprising validating at least one map update on a digital map using the similarity index.

9. (canceled)

12. (canceled)

14. A computing device comprising:

a memory storing data indicative of first and second routes between a start location and a destination location wherein the first and second routes are generated using digital map data; and

a processor arranged to execute a route comparison module by determining nodes of the first and second routes having a minimum coupling distance, wherein the minimum coupling distance is determined based upon nodes of the first and second routes constrained to within a predetermined distance of a current node of each route, and to determining a similarity index for the first and second routes based upon the minimum coupling distance and a threshold coupling distance.

15. The computing device of claim 14, wherein the route comparison module is arranged to determine the nodes having the minimum coupling distance based upon the current node of each route and a predetermined number of further nodes of the route.

16. The computing device of claim 14, wherein the route comparison module is arranged to determine the nodes having the minimum coupling distance based upon the current node of each route and one further node of the route.

17. The computing device of claim 14, wherein the route comparison module is arranged to determine the nodes having the minimum coupling distance by calculating a coupling distance between the nodes of the first and second routes within the predetermined distance of the current node.

18. The computing device of claim 14, wherein the route comparison module is arranged to determine the nodes having the minimum coupling distance without calculating a coupling distance between all combinations of nodes of the first and second routes.

19. The computing device of claim 14, wherein the route comparison module is arranged to determine nodes having the minimum coupling distance by calculating a coupling distance between only a subset of combinations of nodes of the first and second routes.

20. The computing device of claim 14, wherein the route comparison module is arranged to determine nodes having the minimum coupling distance by selecting a node of each route from amongst the nodes within the predetermined distance of the current node of each route.

21. (canceled)

22. (canceled)