Methods of pre-processing probe data

• US 9,097,542 B2
• Filed: 06/10/2010
• Issued: 08/04/2015
• Est. Priority Date: 08/03/2009
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: Tomtom North America Incorporated (TomTom NV)
• Inventors: Morlock, Clayton Richard, Kenyon, Shaundrea Margaret Newman
• Primary Examiner(s): Kiswanto, Nicholas
• Application Number:
  US13/388,743
• Publication Number:
  US 20120259547A1
• Time in Patent Office: 1,881 Days
• Field of Search: 701/533
• US Class Current: 1/1
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• 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: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring

Abstract

Methods of pre-processing probe trace data include examining a sequential dataset for a route of travel between two points, identifying at least one anomaly in the sequential dataset, identifying at least one datum of the sequential dataset occupying a sequential position adjacent to the identified at least one anomaly, and inserting at least one non-anomalous datum to occupy a sequential position of the identified at least one anomaly in the sequential dataset, the at least one non-anomalous datum being determined based on one of extrapolation, smoothing and interpolation of the at least one datum.

Claims

1. A method of pre-processing probe data, the method comprising:

examining a sequential dataset for a route of travel between two points;

identifying at least one anomaly in the sequential dataset;

identifying at least a first and a second datum of the sequential dataset wherein said first datum occupies a sequential position adjacent to the identified at least one anomaly; and

inserting at least one non-anomalous datum to occupy a sequential position of the identified at least one anomaly in the sequential dataset, the at least one non-anomalous datum being determined based on one of extrapolation, smoothing and interpolation of the at least first and second datum, wherein the at least one non-anomalous datum is further determined based on at least one inference derived from at least one characteristic of the route, the at least one characteristic of the route being information other than vehicular data corresponding to the route of travel between the two points.

2. The method of claim 1, wherein the inserting the at least one non-anomalous datum comprises determining a first trajectory of at least one vehicle based on data of the sequential dataset which occupies a sequential position prior to the identified at least one anomaly;

determining a second trajectory of the at least one vehicle based on data of the sequential dataset which occupies a sequential position after the identified at least one anomaly; and

determining whether or not a correlation exists between the first and second trajectories.

3. The method of claim 2, further comprising:

inserting, for correlating trajectories, the at least one non-anomalous datum to occupy a sequential position of the at least one anomaly in the sequential dataset.

4. The method of claim 1, wherein the at least one non-anomalous datum includes a plurality of regularly spaced non-anomalous data.

5. The method of claim 1, wherein the at least one non-anomalous datum is further determined based on at least one inference derived from vehicular data.

6. The method of claim 5, wherein the vehicular data includes, for positions along the route, at least one of an average speed of vehicles, a frequency of vehicle stoppages, a frequency of vehicles changing direction, a frequency of vehicles changing lanes, and a frequency of vehicular accidents.

7. The method of claim 5, wherein the at least one inference is at least one of a maximum and minimum curvature of a portion of the route corresponding to the at least one anomaly.

8. The method of claim 1, wherein the at least one characteristic of the route includes at least one of a curvature of the route, a location of at least one intersection along the route, whether the route is a detour, whether the route is a highway, a change in elevation of the route, locations of stops along the route, whether the route is under construction, the presence of a structure near the route, and the presence of a structure over the route.

9. A method as claimed in claim 1, wherein the identifying of the at least one anomaly includes identifying at least one of at least one error or at least one drop-out in the sequential dataset.

10. The method of claim 9, wherein the identifying of the at least one error includes identifying at least one of data representing a rapid change in a curvature of the route, data representing erratic shifts in elevation of the route, satellite usage error, and changes in the sequential dataset from a historical sequential dataset.

11. The method of claim 10, wherein the satellite usage error includes at least one of a lack of a fix on a prescribed number of satellites, insufficient spread in satellite locations of used satellites, and use of at least one low angle satellite.

12. The method of claim 9, wherein the at least one drop-out includes one of a missing measurement for a time period of a periodic measurement and a missing measurement for a position along the route.

13. The method of claim 9, wherein the identifying of the at least one error includes correlating a known location of at least one obstruction to a portion of the route corresponding to the anomaly.

14. The method of claim 13, wherein the at least one obstruction includes at least one of a bridge, a tunnel wall, a dense stand of trees, and a tall building.

15. The method of claim 9, wherein the at least one non-anomalous datum is further based on a statistical analysis of the at least one error.

16. The method of claim 1, wherein the route is a series of positional datums recorded by at least one navigation device.

17. A method of pre-processing probe data, the method comprising:

examining a plurality of sequential location measurements for a route of travel between two points;

fitting a best fit mathematical curve to the plurality of sequential location measurements;

identifying at least one anomaly by identifying at least one of the plurality of sequential location measurements that does not fall near the best fit mathematical curve within a statistical threshold, the identifying based at least in part on at least one inference derived from at least one characteristic of the route, the at least one characteristic of the route being information other than vehicular data corresponding to the route of travel between the two points;

removing the identified at least one anomaly; and

inserting sequential location data corresponding to the best fit mathematical curve in place of the anomaly.

18. A non-transitory computer readable medium having computer readable instructions stored thereon, which when executed on a processor cause the processor to perform a method comprising:

examining a sequential dataset for a route of travel between two points;

identifying at least one anomaly in the sequential dataset;

identifying at least a first and a second datum of the sequential dataset wherein said first datum occupies a sequential position adjacent to the identified at least one anomaly; and

inserting at least one non-anomalous datum to occupy a sequential position of the identified at least one anomaly in the sequential dataset, the at least one non-anomalous datum being determined based on one of extrapolation, smoothing and interpolation of the at least first and second datum, wherein the at least one non-anomalous datum is further determined based on at least one inference derived from at least one characteristic of the route, the at least one characteristic of the route being information other than vehicular data corresponding to the route of travel between the two points.

19. A map comprising features based on data identified using a method comprising:

examining a sequential dataset for a route of travel between two points;

identifying at least one anomaly in the sequential dataset;

identifying at least a first and a second datum of the sequential dataset wherein said first datum occupies a sequential position adjacent to the identified at least one anomaly; and

inserting at least one non-anomalous datum to occupy a sequential position of the identified at least one anomaly in the sequential dataset, the at least one non-anomalous datum being determined based on one of extrapolation, smoothing and interpolation of the at least first and second datum, wherein the at least one non-anomalous datum is further determined based on at least one inference derived from at least one characteristic of the route, the at least one characteristic of the route being information other than vehicular data corresponding to the route of travel between the two points.

20. An electronic device comprising a map stored in a memory in the electronic device, the map comprising features based on data identified using a method comprising:

examining a sequential dataset for a route of travel between two points;

identifying at least one anomaly in the sequential dataset;

identifying at least a first and a second datum of the sequential dataset wherein said first datum occupies a sequential position adjacent to the identified at least one anomaly; and

inserting at least one non-anomalous datum to occupy a sequential position of the identified at least one anomaly in the sequential dataset, the at least one non-anomalous datum being determined based on one of extrapolation, smoothing and interpolation of the at least first and second datum, wherein the at least one non-anomalous datum is further determined based on at least one inference derived from at least one characteristic of the route, the at least one characteristic of the route being information other than vehicular data corresponding to the route of travel between the two points.