Systems and methods for using magnetic field readings to refine device location estimates

• US 9,163,943 B1
• Filed: 05/07/2014
• Issued: 10/20/2015
• Est. Priority Date: 12/09/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Miller, Christian
• Primary Examiner(s): ARTHUR JEANGLAUD, GERTRUDE
• Application Number:
  US14/271,830
• Time in Patent Office: 531 Days
• Field of Search: 701/36, 701/300, 701/518, 701/525, 324/202, 324/207.26
• US Class Current: 1/1
• CPC Class Codes: G01B 7/004 for measuring coordinates of points
• CPC Class Codes: G01S 13/00 Systems using the reflection or reradiation of radio waves, e.g. radar systems; Analogous systems using reflection or reradiation of waves whose nature or wavelength is irrelevant or unspecified
• CPC Class Codes: G01S 19/00 Satellite radio beacon positioning systems; Determining position, velocity or attitude using signals transmitted by such systems
• CPC Class Codes: G01S 5/16 using electromagnetic waves other than radio waves
• CPC Class Codes: G01V 3/08 operating with magnetic or electric fields produced or modified by objects or geological structures or by detecting devices with electromagnetic waves G01V3/12

Abstract

Systems and methods for using magnetic field readings to refine device location estimates are provided. As an example, a plurality of magnetic field readings can be collected by a device as it travels along a path. A positioning system (e.g., GPS) or other sensors can be used to provide a coarse location for the device at each reading. A contribution to each of the magnetic field readings by the Earth'"'"'s magnetic field can be removed to obtain a plurality of residual readings and a plurality of regions of interest along the path can be identified based at least in part on the residual readings. The regions of interest can be compared to each other to identify a plurality of correspondences between magnetic field readings or residual readings and the plurality of correspondences can be used to refine the location estimates.

Claims

1. A method for revising location estimates, the method comprising:

obtaining, by one or more computing devices, a plurality of readings of a magnetic field collected by a magnetometer of a device, wherein the plurality of readings are respectively associated with a plurality of location estimates of the device along a location path, wherein each of the one or more computing devices comprises one or more processors;

identifying, by the one or more computing devices, a plurality of regions of interest of the plurality of readings along the location path;

comparing, by the one or more computing devices, each of the plurality of regions of interest of the plurality of readings with at least one other of the plurality of regions of interest to identify a plurality of correspondences; and

revising, by the one or more computing devices, at least one of the plurality of location estimates based at least in part on the plurality of correspondences.

2. The method of claim 1, wherein:

the plurality of readings of the magnetic field are collected by the magnetometer of the device during a single data collection run;

the device travels along the location path during the single data collection run; and

revising, by the one or more computing devices, at least one of the plurality of location estimates based at least in part on the plurality of correspondences comprises closing, by the one or more computing devices, at least one location overlap exhibited by the location path.

3. The method of claim 1, wherein comparing, by the one or more computing devices, each region of interest with at least one other region of interest comprises performing, by the one or more computing devices, a time warping algorithm for each region of interest with respect to the other region of interest to identify the plurality of correspondences.

4. The method of claim 3, wherein performing, by the one or more computing devices, the time warping algorithm for each region of interest with respect to the other region of interest comprises:

determining, by the one or more computing devices, a comparison table by computing a plurality of comparison values according to a comparison function, wherein the plurality of comparison values are respectively computed for a plurality of pairs of readings, and wherein the plurality of pairs of readings comprise each reading from the region of interest paired with each reading from the other region of interest;

determining, by the one or more computing devices, a cost table based at least in part on the comparison table;

determining, by the one or more computing devices, a direction table based at least in part on the cost table; and

identifying, by the one or more computing devices, the plurality of correspondences based at least in part on the direction table.

5. The method of claim 4, wherein the comparison function comprises a weighted sum of a squared difference between a first input reading and a second input reading and a squared distance between a first location estimate and a second location estimate respectively associated with the first input reading and the second input reading.

6. The method of claim 4, wherein determining, by the one or more computing devices, the cost table based at least in part on the comparison table comprises:

computing, by the one or more computing devices, a first, second, and third cost value for each of the plurality of pairs of readings; and

respectively selecting, by the one or more computing devices, the minimum of the first, second, and third cost values for each of the plurality of pairs of readings as the final cost value for such pair of readings;

wherein each pair of readings comprises a first paired reading that is included in the region of interest and a second paired reading that is included in the other region of interest;

wherein the first cost value for each pair of readings comprises the sum of a skipcost value and the final cost value associated with the second paired reading and a first neighbor reading, wherein the first neighbor reading for each pair of readings comprises the previous sequential reading with respect to the first paired reading in the region of interest;

wherein the third cost value for each pair of readings comprises the sum of the skipcost value and the final cost value associated with the first paired reading and a second neighbor reading, wherein the second neighbor reading for each pair of readings is the previous sequential reading with respect to the second paired reading in the other region of interest;

wherein the second cost value for each pair of readings comprises the sum of the comparison value associated with such pair of readings and the final cost value associated with the first and second neighbor readings; and

wherein the skipcost value comprises a constant value.

7. The method of claim 6, wherein determining, by the one or more computing devices, the direction table based at least in part on the cost table comprises:

respectively selecting, by the one or more computing devices for each of the plurality of pairs of readings, a leftwards step value if the first cost value was selected as the final cost value for such pair of readings;

respectively selecting, by the one or more computing devices for each of the plurality of pairs of readings, a diagonal step value if the second cost value was selected as the final cost value for such pair of readings; and

respectively selecting, by the one or more computing devices for each of the plurality of pairs of readings, a downwards step value if the third cost value was selected as the final cost value for such pair of readings.

8. The method of claim 7, wherein identifying, by the one or more computing devices, the plurality of correspondences based at least in part on the direction table comprises:

determining, by the one or more computing devices, an alignment by traversing the direction table according to the directional step values; and

identifying, by the one or more computing devices, one of the plurality of correspondences at each instance in which the alignment travels according to a diagonal step value and the comparison value for the pair of readings that provide the diagonal step value is less than the skipcost value.

9. The method of claim 1, wherein:

each region of interest comprises selected of the plurality of readings; and

comparing, by the one or more computing devices, each region of interest with at least one other region of interest comprises, for each region of interest;

performing, by the one or more computing devices, a time warping algorithm for the region of interest with respect to the at least one other region of interest;

respectively rotating, by the one or more computing devices, the plurality of readings included in the region of interest about a vertical axis by one-hundred and eighty degrees; and

after respectively rotating the plurality of readings, performing, by the one or more computing devices, the time warping algorithm for the rotated region of interest with respect to the at least one other region of interest.

10. A system for revising location estimates, comprising:

one or more computing devices; and

at least one memory storing instructions that, when executed by the one or more computing devices, cause the one or more computing devices to perform operations, the operations comprising;

obtaining a plurality of magnetic field readings, wherein the plurality of magnetic field readings are respectively associated with a plurality of location estimates along a location path and a plurality of orientations;

identifying a first region of interest along the location path by respectively selecting a first plurality of the magnetic field readings surrounding a first location estimate;

identifying a second region of interest along the location path by respectively selecting a second plurality of the magnetic field readings surrounding a second location estimate; and

identifying a plurality of correspondences by performing a time warping algorithm to compare the first region of interest with the second region of interest.

11. The system of claim 10, wherein:

the plurality of magnetic field readings are collected by a magnetometer of a device during a single data collection run;

the device travels along the location path during the single data collection run; and

the at least one memory stores further instructions that, when executed by the one or more computing devices, cause the one or more computing devices to perform further operations, the further operations comprising closing at least one location overlap exhibited by the location path based at least in part on the plurality of correspondences.

12. The system of claim 10, wherein:

the first plurality of the magnetic field readings included in the first region of interest comprises a first number (N) of magnetic field readings;

the second plurality of the magnetic field readings included in the second region of interest comprises a second number (M) of magnetic field, readings; and

identifying the plurality of correspondences by performing the time warping algorithm to compare the first region of interest with the second region of interest comprises determining a comparison table holding a comparison value (COMPARE(i, j)) according to a comparison function for each of a plurality of pairs of magnetic field readings (1≦

i≦

N, 1≦

j≦

M), such that the comparison table is of size N times M.

13. The system of claim 12, wherein identifying the plurality of correspondences by performing the time warping algorithm to compare the first region of interest with the second region of interest further comprises determining a cost table based at least in part on the comparison table by computing a cost value (COST(i, j)) for each of the plurality of pairs of magnetic field readings.

14. The system of claim 13, wherein the cost value for each of pair of magnetic field readings (1≦

i≦

N, 1≦

j≦

M) comprises the minimum of a C1 value, a C2 value, or a C3 value, and wherein;

C1(i,j)=COST(i−

1,j)+SKIPCOST;

C2(i,j)=COST(i−

1,j−

1)+COMPARE(i,j);

C3(i,j)=COST(i,j−

1)+SKIPCOST; and

SKIPCOST comprises an adjustable constant value.

15. The system of claim 14, wherein identifying the plurality of correspondences by performing the time warping algorithm to compare the first region of interest with the second region of interest further comprises determining a direction table based at least in part on the cost table by selecting a direction value (DIR(i, j)) for each of the plurality of pairs of magnetic field readings (1≦

i≦

N, 1≦

j≦

M), wherein;

DIR(i,j)=(−

1,0) if COST(i,j)=C1(i,j);

DIR(i,j)=(−

1,−

1) if COST(i,j)=C2(i,j);

DIR(i,j)=(0,−

1) if COST(i,j)=C3(i,j).

16. The system of claim 15, wherein identifying the plurality of correspondences by performing the time warping algorithm to compare the first region of interest with the second region of interest further comprises:

determining an alignment by beginning at (N, M) of the direction table and traversing the direction table according to the direction values; and

identifying one of the plurality of correspondences for each of the plurality of pairs of magnetic field readings that are traversed by the alignment, for which the corresponding direction value equals (−

1, −

1), and for which the corresponding comparison value is less than SKIPCOST.

17. The system of claim 12, wherein the comparison function comprises a weighted sum of a squared difference between a first input magnetic field reading and a second input magnetic field reading and a squared distance between a first location estimate and a second location estimate respectively associated with the first and second input magnetic field readings.

18. A non-transitory computer-readable medium storing instructions that, when executed by one or more computing devices, cause the one or more computing devices to perform operations, the operations comprising:

obtaining a plurality of magnetic field readings along a device location path;

identifying a plurality of regions of interest along the location path within the plurality of magnetic field readings;

comparing each magnetic field reading within each of the plurality of regions of interest to each magnetic field reading within at least one other of the plurality of regions of interest to identify a plurality of correspondences, wherein each of the plurality of correspondences matches one of the plurality of magnetic field readings to another one of the plurality of magnetic field readings.

19. The non-transitory computer-readable medium of claim 18, wherein:

comparing each magnetic field reading within each of the plurality of regions of interest to each magnetic field reading within at least one other of the plurality of regions of interest to identify the plurality of correspondences comprises computing a comparison score for each magnetic field reading within each of the plurality of regions of interest with respect to each magnetic field reading within at least one other of the plurality of regions of interest according to a comparison function; and

the comparison function comprises a weighted sum of a squared difference between two input magnetic field readings, a squared distance between two location estimates respectively associated with the two input magnetic field readings, and a squared difference between two headings respectively associated with the two input magnetic field readings.

20. The non-transitory computer-readable medium of claim 19, wherein comparing each magnetic field reading within each of the plurality of regions of interest to each magnetic field reading within at least one other of the plurality of regions of interest to identify a plurality of correspondences further comprises identifying a plurality of pairs of magnetic field readings respectively having a comparison score that is less than a threshold value.