GPS TRACE FILTERING

• US 20120016574A1
• Filed: 01/26/2011
• Published: 01/19/2012
• Est. Priority Date: 07/16/2010
• Status: Abandoned Application

• Current Assignee: Blackberry Limited
• Original Assignee: Research In Motion Limited (Blackberry Limited)
• Inventors: Smartt, Brian Eric
• Application Number:
  US13/014,459
• Publication Number:
  US 20120016574A1
• Time in Patent Office: Days
• US Class Current: 701/117
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 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
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/20 Services signaling; Auxiliary data signalling, i.e. transmitting data via a non-traffic channel

Abstract

A mobile device can function as a probe to sense conditions on roads and other areas of interest. A mobile device can have a GPS receiver to receive traces of GPS fixes. In a system with many such probes, it may be desirable to reduce an amount of GPS data reported by each device. To reduce such data reporting, a trace of GPS fixes is approximated by a selection of representative GPS fixes. Examples of how such a selection can be made are disclosed. Parameters and other behaviour by each device functioning as a probe can be set by central controller; for example, probes can be turned on and off, reporting frequencies can be adjusted, and thresholds used in the approximation can be set.

Claims

1. A method, comprising:

obtaining a set of GPS fixes in a mobile device over a pre-determined time interval;

determining a portion of the set of GPS fixes using a piece-wise linear approximation of the set of GPS fixes having an approximation error below a pre-defined error threshold; and

sending, from the mobile device, the determined portion of the set of GPS fixes to represent the set of GPS fixes.

2. The method of claim 1, wherein the pre-determined time interval is set at the mobile device based on information from a server.

3. The method of claim 1, wherein the pre-defined error threshold is set at the mobile device based a type of movement sensed at the mobile device.

4. The method of claim 1, wherein the determined portion of the set of GPS fixes to represent the set of GPS fixes is a piece-wise approximation.

5. The method of claim 1, wherein the determined portion of the set of GPS fixes to represent the set of GPS fixes is a piece-wise polynomial approximation.

6. A tangible computer readable medium storing instructions for configuring a processor to perform a method according to any one of method claims 1-5.

7. A system, comprising:

a plurality of mobile devices, each comprising a network interface and a processor configured to perform a method comprising

access a set of GPS fixes obtained over a pre-determined time interval,

determining a portion of the set of GPS fixes using a piece-wise linear approximation of the set of GPS fixes having an approximation error below a pre-defined error threshold,

sending, from the mobile device, the determined portion of the set of GPS fixes to represent the set of GPS fixes; and

a server coupled to receive the portions of the set of GPS fixes sent by each mobile device, and to send messages to the mobile devices with pre-determined time intervals to be applied by those mobile devices.

8. A method, comprising:

obtaining a trace of GPS fixes in a mobile device;

determining a series of displacements, ordered with respect to time, from the trace of GPS fixes;

determining a piece-wise linear curve that approximates the series of displacements, the piece-wise linear curve defined by a subset of the series of displacements, wherein the members of the subset are selected to conform the piece-wise linear curve to the series within a defined error threshold; and

sending, from the mobile device, a list of GPS fixes identified based on the subset of the series of displacements, as an approximation of the trace of GPS fixes.

9. The method of claim 8, wherein the members of the subset are selected by determining a disparity between a point along the piece-wise linear curve, and a displacement identified along a line extending perpendicular to the piece-wise linear curve at the point, and quantifying the disparity by converting a change in time into a change in displacement according to a determined normalization ratio.

10. The method of claim 9, wherein the determining is performed iteratively, with a largest disparity identified addressed in each iteration.

11. The method of claim 8, wherein the members of the subset are selected by determining a disparity between a point along the piece-wise linear curve, and a displacement identified along a line extending perpendicular to the piece-wise linear curve at the point, and quantifying the disparity by converting a change in displacement into a change in time according to a determined normalization ratio.

12. The method of claim 8, wherein the members of the subset are selected by determining, for each displacement in the series, a disparity between the displacement and the piece-wise linear curve at a time associated with the displacement, and for a largest determined disparity, adding a segment to the piece-wise linear approximation, and a GPS fix associated with that displacement to the list of GPS fixes.

13. The method of claim 8, wherein the members of the subset are selected by recursively determining a largest disparity between the series of displacements and each piece of the piece-wise linear curve, and responsively adding a piece to the piece-wise linear curve and a GPS fix associated with the displacement having the largest disparity to the list of GPS fixes.

14. A mobile device, comprising:

a wireless network interface;

a memory; and

a processor coupled with the memory and with the wireless network interface, the processor configured to

obtain a trace of GPS fixes from the memory;

determine a series of displacements, ordered with respect to time, from the trace of GPS fixes;

determine a piece-wise linear curve that approximates the series of displacements, the piece-wise linear curve defined by a subset of the series of displacements, wherein the members of the subset are selected to conform the piece-wise linear curve to the series within a defined error threshold; and

send, over the wireless network interface, a list of GPS fixes identified based on the subset of the series of displacements, as an approximation of the trace of GPS fixes.

15. The mobile device of claim 14, wherein the members of the subset are selected by determining a disparity between a point along the piece-wise linear curve, and a displacement identified along a line extending perpendicular to the piece-wise linear curve at the point, and quantifying the disparity by converting a change in time into a change in displacement according to a determined normalization ratio.

16. The mobile device of claim 15, wherein the determining is performed iteratively, with a largest disparity identified addressed in each iteration.

17. The mobile device of claim 14, wherein the members of the subset are selected by determining a disparity between a point along the piece-wise linear curve, and a displacement identified along a line extending perpendicular to the piece-wise linear curve at the point, and quantifying the disparity by converting a change in displacement into a change in time according to a determined normalization ratio.

18. The mobile device of claim 14, wherein the members of the subset are selected by determining, for each displacement in the series, a disparity between the displacement and the piece-wise linear curve at a time associated with the displacement, and for a largest determined disparity, adding a segment to the piece-wise linear approximation, and a GPS fix associated with that displacement to the list of GPS fixes.

19. The mobile device of claim 14, wherein the members of the subset are selected by recursively determining a largest disparity between the series of displacements and each piece of the piece-wise linear curve, and responsively adding a piece to the piece-wise linear curve and a GPS fix associated with the displacement having the largest disparity to the list of GPS fixes.

20. A computer readable medium storing instructions for configuring a process to perform a method in a mobile device, comprising:

obtaining a trace of GPS fixes in a mobile device;

determining a series of displacements, ordered with respect to time, from the trace of GPS fixes;

determining a piece-wise linear curve that approximates the series of displacements, the piece-wise linear curve defined by a subset of the series of displacements, wherein the members of the subset are selected to conform the piece-wise linear curve to the series within a defined error threshold; and

sending, from the mobile device, a list of GPS fixes identified based on the subset of the series of displacements, as an approximation of the trace of GPS fixes.

21. The computer readable medium of claim 20, wherein the members of the subset are selected by determining a disparity between a point along the piece-wise linear curve, and a displacement identified along a line extending perpendicular to the piece-wise linear curve at the point, and quantifying the disparity by converting a change in time into a change in displacement according to a determined normalization ratio.

22. The computer readable medium of claim 21, wherein the determining is performed iteratively, with a largest disparity identified addressed in each iteration.

23. The computer readable medium of claim 20, wherein the members of the subset are selected by determining a disparity between a point along the piece-wise linear curve, and a displacement identified along a line extending perpendicular to the piece-wise linear curve at the point, and quantifying the disparity by converting a change in displacement into a change in time according to a determined normalization ratio.

24. The computer readable medium of claim 20, wherein the members of the subset are selected by determining, for each displacement in the series, a disparity between the displacement and the piece-wise linear curve at a time associated with the displacement, and for a largest determined disparity, adding a segment to the piece-wise linear approximation, and a GPS fix associated with that displacement to the list of GPS fixes.

25. The computer readable medium of claim 20, wherein the members of the subset are selected by recursively determining, a largest disparity between the series of displacements and each piece of the piece-wise linear curve, and responsively adding a piece to the piece-wise linear curve and a GPS fix associated with the displacement having the largest disparity to the list of GPS fixes.