METHOD, DEVICE AND SYSTEM FOR MODELING A ROAD NETWORK GRAPH

• US 20090138188A1
• Filed: 07/22/2005
• Published: 05/28/2009
• Est. Priority Date: 07/22/2005
• Status: Abandoned Application

• Current Assignee: Telargo Incorporated (The Descartes Systems Group Incorporated)
• Original Assignee: Telargo Incorporated (The Descartes Systems Group Incorporated)
• Inventors: Pavlic, Bogdan, Kores, Andrej, Pecar, Martin, Novak, Tajet
• Application Number:
  US11/996,462
• Publication Number:
  US 20090138188A1
• Time in Patent Office: Days
• US Class Current: 701/117
• CPC Class Codes: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles

Abstract

There is provided a method, device and system for modeling a road network graph, comprising the steps of receiving information data from a plurality of vehicles, said information data comprising at least positional data, and modeling said road network graph in accordance with said received data.

Claims

1. Method for modeling a road network graph, comprising the steps of:

receiving information data from a plurality of vehicles, said information data comprising at least positional data of said vehicles, and

modeling the road network graph in accordance with the received data.

2. Method according to claim 1, the information data further comprising at least one of vehicle type, vehicle speed, or acceleration of the plurality of vehicles.

3. Method according to claim 1, further comprising the step of:

calculating a road network geometry, topology and traffic statistics in an automatic manner.

4. Method according to claim 1, wherein an automatic merging of road network graphs is carried out.

5. Method according to claim 1, wherein an automatic profiling of road network graph by using the information data is carried out.

6. Method according to claim 1, wherein a verification is carried by inspecting the graph by vehicles which inspect the road network graph at the site.

7. Method according to claim 1, wherein the road network graph is used for an optimization step during verifying the road network graph.

8. Method according to claim 1, wherein the modeling is based on mathematical techniques for processing curves, arcs, polynomials or the like performed on the data.

9. Method according to claim 1, wherein the modeling is based on Bezier curve techniques.

10. Method according to claim 1, wherein the mathematical techniques are based on averaging of curves.

11. Method according to claim 8, further comprising extending curve lengths to a desired predefined length.

12. Method according to claim 11, further comprising fitting the curve to an ordered set of points, said curve corresponding to the trajectory of a certain vehicle.

13. Method according to claim 12, further comprising computing the similarity of a certain pair of the curves.

14. Method according to claim 13, further comprising performing a similarity detection step for finding similar subsections of a certain pair of the curves.

15. Method according to claim 1, wherein transmitting of information relating the network graph to at least one vehicle of said plurality of vehicles is provided.

16. Method according to claim 1, wherein compression of the information data regarding the plurality of vehicles is carried out.

17. Method according to claim 16, wherein the compression comprises Bezier curve fitting.

18. Method according to claim 1, wherein the received information data represent a trajectory of at least one vehicle from the plurality of

vehicles, wherein each trajectory may be described by Bezier curves, the method further comprising:

averaging trajectories associated with the at least one vehicle.

19. Method according to claim 1, further comprising the steps of:

calculating a first approximation of the road network graph on the basis of the received information data;

profiling of roads and junctions within the first approximation resulting in a profiled road network graph; and

—

performing a verification of the profiled network.

20. Method according to claim 19, wherein the calculating is based on at least one of Bezier curves techniques or on mathematical techniques for processing curves, arcs, polynomials or the like, performed on the data.

21. Method according to claim 19, further comprising the steps of:

detecting changes of an existing road network graph on the basis of the received information data;

storing the changes; and

—

implementing the changes in the existing road network graph.

22. Method according to claim 21, wherein the implementing is based on statistical information.

23. Method according to claim 21, further comprising transmitting of information relating the network graph to at least one vehicle of the plurality of vehicles.

24. Method according to claim 16, further comprising:

—

performing the compression step of the information data selectively within the modeling entity or within said plurality of vehicles or within both the modeling entity and the plurality of vehicles.

25. Method according to claim 1, further comprising the step of:

—

storing the information data.

26. Method according to claim 3, wherein said calculation is based on digital computing techniques for computing of fixed-point values.

27. Method according to claim 1, wherein the information data comprises measurement data, and further comprising normalizing the measurement data according to predetermined threshold values.

28. Method according to claim 25, wherein the storing is provided after execution of a compression algorithm, a hashing algorithm, an encrypting algorithm or the like.

29. Method according to claim 3, further comprising detecting existence of a multipath phenomenon/effect and in this case assigning less weight to the received information during said calculation step.

30. Method according to claim 1, further comprising measuring at least one of road dimensions or proportions by means of a position information providing entity within the plurality of vehicles.

31. Method according to claim 30, wherein the position information providing entity is a GPS transceiver within each vehicle.

32. Method according to claim 31, wherein the GPS transceiver is coupled with a gyroscope or the like.

33. Method according to claim 1, wherein curve similarity is employed for determining of the position of a the vehicle on the road network graph.

34. A computer program product, comprising program code sections for carrying out the operations of anyone of the preceding claims, when said program is run on a processor-based device, a terminal device, a network device, a portable terminal, a consumer electronic device, or a mobile communication enabled terminal.

35. A computer program product, comprising program code sections stored on a machine-readable medium for carrying out the operations of anyone of the preceding claims, when said program product is run on a processor-based device, a terminal device, a network device, a portable terminal, a consumer electronic device, or a mobile communication enabled terminal.

36. A software tool, comprising program portions for carrying out the operations of any one of the preceding claims, when said program is implemented in a computer program for being executed on a processor-based device, a terminal device, a network device, a portable terminal, a consumer electronic device, or a mobile communication enabled terminal.

37. A computer data signal embodied in a carrier wave and representing instructions, which when executed by a processor cause the operations of claim 1 to be carried out.

38. Server device for modeling a road network graph, comprising:

a component for receiving information data from a plurality of vehicles, said information data comprising at least positional data of said vehicles; and

a component for modeling said road network graph in accordance with said received data.

39. Server according to claim 38, further comprising:

—

a component for calculating a first approximation of said road network graph;

a component for profiling of roads and junctions within said first approximation

resulting in a profiled road network graph; and

a component for performing a verification of said profiled network.

40. Server according to claim 38, further comprising:

—

a component for detecting changes of said road network graph on the basis of said received information;

a component for storing said changes; and

a component for including said changes in said road network graph.

41. Server according to claim 38, further comprising:

a component for analyzing said road network graph on the basis of said received information; and

a component for reporting analysis results to a third party.

42. Server according to claim 38, further comprising:

a component for performing a compression step of said information selectively within said modeling entity.

43. Server according to claim 38, further comprising:

—

a component for storing at least said information raw data received from said plurality of vehicles, attributes associated with said raw data, road network graph and the like.

44. Server according to claim 38, further comprising:

—

a component for detecting existence of a multipath phenomenon/effect; and

further a component for assigning less weight to said received information.

45. Server according to claim 38, further comprising a component for measuring of road dimensions by means of a position information providing entity within said plurality of vehicles.

46. Server according to claim 38, wherein said received information represents a trajectory of at least one vehicle from said plurality of vehicles, wherein each trajectory is described by said mathematical techniques, said server further comprising:

a component for averaging trajectories associated with said at least one vehicle.

47. Server according to claim 46, wherein said mathematical techniques correspond to at least one of the Bezier curves, arcs, polynomials or the like.

48. System for modeling a road network graph, comprising a plurality of server devices according to claim 38 and a plurality of information data providing vehicles.