System and method for identifying road features

• US 8,306,777 B2
• Filed: 04/18/2011
• Issued: 11/06/2012
• Est. Priority Date: 10/14/2005
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Dash Navigation (Blackberry Limited)
• Inventors: Smartt, Brian, Weisenfluh, Craig
• Primary Examiner(s): Lau, Tung S
• Application Number:
  US13/089,201
• Publication Number:
  US 20110196611A1
• Time in Patent Office: 568 Days
• Field of Search: 702/167
• US Class Current: 702/167
• CPC Class Codes: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G01C 21/3822 Road feature data, e.g. slope data
• CPC Class Codes: G01C 21/3837 Data obtained from a single source
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G09B 29/003 Maps
• CPC Class Codes: G09B 29/102 using electrical means

Abstract

A system and method identifies road features that may not appear on a map database, such as paths not described as roads on the map database, and whether all the roads at a crossing cross at the same grade level. The system and method may thus be used to identify points of departure from, or points of merging onto, a road described by the map database or a path identified as described herein, but not described by the map database.

Claims

1. A method for identifying departure and merge features of a road, comprising:

in a computer, receiving data sets with a reach set comprising periodic positional fixes along the road;

identifying tuples from the received data sets wherein a tuple identifies a departure point from a first road and a merge point on a second road;

grouping data between the departure point and merge point for each tuple;

selecting a given group from the grouped data and for each selected group perform the following;

selecting data from the selected given group;

forming a trace based on data points from the selected data; and

assigning a quality rating to each trace; and

continue to select given groups until a predefined number of traces are formed.

2. The method of claim 1, wherein in the event a predefined traces are formed,

selecting a primary trace from the plurality of traces based on the quality rating;

identifying a midpoint of each line segment in the primary trace;

constructing a normal axis at each midpoint;

calculating the point on each axis where each of the plurality of traces crosses each axis;

aggregating the crossing points on each axis and calculating a corrected trace point for each axis responsive to the quality rating of at least one of the plurality of traces; and

connecting the corrected trace points to form a correct trace representing the road.

3. The method of claim 2, further comprising selecting a different primary trace from the plurality of traces and repeating the method of claim 2.

4. The method of claim 2, wherein one or more of the plurality of data point sets comprises position fixes obtained at a fixed or variable interval along the first road.

5. The method of claim 2, further comprising comparing the vertical gradient of the first road at or near a position where the first road crosses a second road to determine whether the first and the second roads comprise a grade separated crossing.

6. The method of claim 3, wherein the primary trace is selected responsive to the quality ratings assigned to at least some of the plurality traces.

7. The method of claim 6, wherein the primary trace is selected by identifying one of the plurality of traces that has a quality rating that is not lower than at least one of a remaining of the plurality of traces.

8. The method of claim 1, wherein at least one quality rating is assigned responsive to a number of satellites tracked.

9. The method of claim 1, wherein at least one quality rating is assigned responsive to at least one outage of satellite reception.

10. The method of claim 1, wherein at least one quality rating is assigned responsive to whether the trace behaves in a manner that is physically reasonable for a mode of transportation.

11. The method of claim 1, wherein at least one quality rating is assigned to one trace responsive to at least one of the positional fixes used to construct said trace, and an area identified responsive to a different at least one of the positional fixes used to construct said trace.

12. A non-transitory computer readable medium storing instructions for identifying departure and merge features of a road to execute instructions on a processor to:

receive data sets with a reach set comprising periodic positional fixes along the road;

identify tuples from the received data sets wherein a tuple identifies a departure point from a first road and a merge point on a second road;

group data between the departure point and merge point for each tuple;

select a given group from the grouped data and for each selected group perform the following;

select data from the selected given group;

form a trace based on data points from the selected data; and

assign a quality rating to each trace; and

continue to select given groups until a predefined number of traces are formed.

13. The non-transitory computer readable medium of claim 12 wherein in the event a predefined traces are formed,

select a primary trace from the plurality of traces based on the quality rating;

identify a midpoint of each line segment in the primary trace;

construct a normal axis at each midpoint;

calculate the point on each axis where each of the plurality of traces crosses each axis;

aggregate the crossing points on each axis and calculating a corrected trace point for each axis responsive to the quality rating of at least one of the plurality of traces; and

connect the corrected trace points to form a correct trace representing the road.

14. The non-transitory computer readable medium of claim 13, wherein the instructions for the processor to:

select a different primary trace from the plurality of traces and repeating the instructions of claim 13.

15. The non-transitory computer readable medium of claim 13, wherein one or more of the plurality of data point sets comprises position fixes obtained at a fixed or variable interval along the first road.

16. The non-transitory computer readable medium of claim 13, wherein the instructions for the processor to:

compare the vertical gradient of the first road at or near a position where the first road crosses a second road to determine whether the first and the second roads comprise a grade separated crossing.

17. An electronic device comprising:

a non-transitory memory having instructions stored thereon to;

receive data sets with a reach set comprising periodic positional fixes along the road;

identify tuples from the received data sets wherein a tuple identifies a departure point from a first road and a merge point on a second road;

group data between the departure point and merge point for each tuple;

select a given group from the grouped data and for each selected group perform the following;

select data from the selected given group;

form a trace based on data points from the selected data; and

assign a quality rating to each trace; and

continue to select given groups until a predefined number of traces are formed;

a processor coupled to the non-transitory memory and configured to execute the instructions stored on the non-transitory memory.

18. The electronic device of claim 17 wherein in the event a predefined traces are formed,

select a primary trace from the plurality of traces based on the quality rating;

identify a midpoint of each line segment in the primary trace;

construct a normal axis at each midpoint;

calculate the point on each axis where each of the plurality of traces crosses each axis;

aggregate the crossing points on each axis and calculating a corrected trace point for each axis responsive to the quality rating of at least one of the plurality of traces; and

connect the corrected trace points to form a correct trace representing the road.

19. The electronic of claim 18, wherein memory further includes instruction to:

select a different primary trace from the plurality of traces and repeating the instructions of claim 18.

20. The electronic device of claim 18, wherein one or more of the plurality of data point sets comprises position fixes obtained at a fixed or variable interval along the first road.