Method and systems for deducing road geometry and connectivity

• US 8,566,021 B2
• Filed: 08/31/2012
• Issued: 10/22/2013
• Est. Priority Date: 11/30/2004
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Dash Navigation (Blackberry Limited)
• Inventors: Smartt, Brian
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): PECHE, JORGE O
• Application Number:
  US13/601,502
• Publication Number:
  US 20130060465A1
• Time in Patent Office: 417 Days
• Field of Search: 701/55, 701/56, 701/409, 701/450, 701/455, 701/461, 701/468, 701/532, 340/995.11, 340/995.12, 340/995.14, 340/995.15, 340/995.19, 340/286.14, 340/539.2, 342/191, 342/25, 342/357.13, 342/64, 345/584, 345/587, 353/11, 353/5, 382/113, 382/285, 405/69, 434/147, 434/150, 434/153, 711/206, 711/723
• US Class Current: 701/409
• 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
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G08G 1/01 Detecting movement of traffic to be counted or controlled G08G1/07 - G08G1/14 take precedence
• CPC Class Codes: G08G 1/20 Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles

Abstract

Methods and systems for generating, deriving, and enhancing drivable road databases are provided. A baseline road in a road network is defined and position and/or trajectory data collected by vehicles traveling the baseline road are compiled and compared to a representation of the baseline road in an existing database. Identity and/or other property information about the road are assigned form the existing database to the new database.

Claims

1. A computer-implemented method for generating an improved database representing a road network by replacing an original representation of a baseline road in the database with new data having a greater accuracy than the original representation, comprising the steps of:

identifying, by a computer, a baseline road in the road network;

collecting, by the computer, the new data from one or more vehicles traveling a route, on the baseline road;

dividing, by the computer, the routes into one or more route segments;

assigning, by the computer, a segment type to each route segment, wherein all available directions of travel between at least one alternate road and the baseline road collectively are traveled by at least one of the one or more vehicles;

processing, by the computer, the collected data for each route segment; and

replacing, by the computer, an original representation of a baseline road in the database with the processed, collected data having a greater accuracy than the original representation.

2. The computer-implemented method of claim 1, wherein the assigning further comprises discretizing the route data to each of the route segments according to a measure of flow.

3. The computer-implemented method of claim 1, further comprising the computer:

correlating data collected on an assigned off-baseline segment to an assigned off-baseline road, the off-baseline road being represented by an unrefined data set in the database;

gauging a measure of “

fit”

between a subset of collected data and the unrefined data set; and

adjusting the unrefined data set to incorporate information provided by the collected data.

4. The computer-implemented method of claim 1, further comprising assigning, by the computer, one or more of identities and/or properties from the existing database to each road segment in the improved database.

5. The computer-implemented method of claim 1, further comprising identifying, by the computer, a point of convergence to or divergence from the baseline road as a connector segment.

6. The computer-implemented method of claim 5, wherein each connector segment is identified as one of an on-ramp and off-ramp.

7. The computer-implemented method of claim 6, further comprising assigning, by the computer, a name for each connector segment.

8. The computer-implemented method of claim 5, wherein each connector segment includes a start point and an end point.

9. The computer-implemented method of claim 1, wherein the collecting the new data further comprises receiving the new data from a Global Positioning System (GPS) transceiver associated with a vehicle.

10. The computer-implemented method of claim 1, further comprising replacing, by the computer, small segments by absorbing the small segment into an adjacent segment in the event the small segment is deemed meaningless.

11. The computer-implemented method of claim 1, wherein the original database includes data from a Topologically Integrated Geographic Encoding and Referencing (TIGER) database.

12. The computer-implemented method of claim 1, wherein data points are collected using a determination method that uses periodic sampling.

13. A computer implemented method for generating an improved database representing a road network, comprising:

recording, by a computer, a plurality of vehicle position data points from one or more vehicles traveling on a baseline road, such that data points for all of the available directions of travel between at least one alternate road and the baseline road are traveled by at least one of the one or more vehicles and recorded as data points;

compiling, by the computer, the vehicle position data;

connecting, by the computer, the recorded data points to form a semi-continuous trace of the geometric shape of the baseline road in the improved database;

identifying, by the computer, a correspondence between the semi-continuous trace and a representation of the baseline road in an existing database that comprises road identities and/or properties;

identifying, by the computer, a point of convergence to or divergence from the baseline road as a connector segment; and

assigning and saving, by the computer, one or more of the identities and/or properties from the representation of the baseline road in the existing database to the baseline road representation in the improved database responsive to the identifying the correspondence.

14. The computer-implemented method of claim 13, wherein each connector segment is identified as one of an on-ramp and off-ramp.

15. The computer-implemented method of claim 14, further comprising, by the computer, assigning a name for each connector segment.

16. The computer-implemented method of claim 13, wherein each connector segment includes a start point and an end point.

17. The computer-implemented method of claim 13, wherein the data points are determined by a position determination method that uses periodic sampling.

18. The computer-implemented method of claim 17, wherein the position determination method comprises the step of determining the vehicle position with a global positioning system (GPS) transceiver.

19. The computer-implemented method of claim 13, wherein the existing database includes data from a Topologically Integrated Geographic Encoding and Referencing (TIGER) database.

20. The computer-implemented method of claim 13, further comprising assigning, by the computer, a trust value to the semi-continuous trace and assigning a trust value to the representation of the baseline road in an existing database.

21. The computer-implemented method of claim 20, further comprising replacing, by the computer, the representation of the baseline in the existing database with the corresponding trace in the event the assigned trust value of the trace has a higher value than the assigned trust value of the representation of the baseline road in the existing database.