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

• US 8,781,739 B1
• Filed: 12/09/2013
• Issued: 07/15/2014
• Est. Priority Date: 12/09/2013
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Miller, Christian
• Primary Examiner(s): ARTHUR JEANGLAUD, GERTRUDE
• Application Number:
  US14/101,137
• Time in Patent Office: 218 Days
• Field of Search: 701/36, 701/300, 701/518, 701/525, 701/534, 324/207.26, 324/326, 324/202, 342/459, 702/152
• US Class Current: 701/518
• 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;

obtaining, by the one or more computing devices, a plurality of residual readings by respectively removing a plurality of Earth magnetic field contributions from the plurality of readings, wherein the plurality of Earth magnetic field contributions are respectively based at least in part on the plurality of location estimates and a magnetic field model;

identifying, by the one or more computing devices, a plurality of regions of interest based at least in part on the plurality of residual readings;

comparing, by the one or more computing devices, each region of interest with at least one other region 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 a 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 path.

3. The method of claim 1, wherein:

the plurality of readings respectively comprise a plurality of three-dimensional magnetic field vectors;

the plurality of three-dimensional magnetic field vectors are respectively associated with a plurality of orientations of the device;

the plurality of Earth magnetic field contributions respectively comprise a plurality of three-dimensional Earth-field vectors; and

obtaining, by the one or more computing devices the plurality of residual readings by respectively removing a plurality of Earth magnetic field contributions from the plurality of readings comprises;

respectively rotating, by the one or more computing devices, the plurality of three-dimensional magnetic field vectors from a device coordinate frame to a global coordinate frame based at least in part on the respective plurality of orientations of the device; and

obtaining, by the one or more computing devices, the plurality of residual readings by respectively subtracting the plurality of Earth-field vectors from the plurality of rotated three-dimensional magnetic field vectors.

4. 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 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 by performing operations comprising;

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. The method of claim 1, wherein:

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

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 by performing operations comprising;

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 residual readings, and wherein the plurality of pairs of residual readings comprise each residual reading included in the region of interest paired with each residual reading included in 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.

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

12. The method of claim 11, wherein comparing, by the one or more computing devices, each region of interest with at least one other region of interest further comprises:

negating, by the one or more computing devices, the heading associated with each of the plurality of residual readings included in the region of interest; and

after negating the plurality of headings, performing, by the one or more computing devices, the time warping algorithm for the region of interest with respect to the other region of interest.

13. The method of claim 10, 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 residual 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 residual readings as the final cost value for such pair of residual readings;

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

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

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

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

wherein the skipcost value comprises a constant value;

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 residual readings, a leftwards step value if the first cost value was selected as the final cost value for such pair of residual readings;

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

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

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 residual readings that provide the diagonal step value is less than the skipcost value.

14. 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 and a plurality of orientations;

obtaining a plurality of residual readings by respectively removing from the plurality of magnetic field readings a plurality of estimated amounts of magnetism respectively contributed to the plurality of magnetic field readings by the magnetic field of the Earth, wherein the plurality of estimated amounts of magnetism are determined based at least in part on the plurality of location estimates respectively associated with the plurality of magnetic field readings;

identifying at least a first residual reading and a second residual reading of the plurality of residual readings that have a magnitude greater than a threshold value;

identifying a first region of interest by respectively selecting a first plurality of the magnetic field readings surrounding a first location estimate associated with the first residual reading;

identifying a second region of interest by respectively selecting a second plurality of the magnetic field readings surrounding a second location estimate associated with the second residual reading; 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.

15. The system of claim 14, 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 a 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 path based at least in part on the plurality of correspondences.

16. The system of claim 14, 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 performing operations, the operations comprising;

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;

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, 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;

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);

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 16, 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 disturbance samples;

identifying a plurality of regions of interest within the plurality of magnetic field disturbance samples;

comparing each magnetic field disturbance sample within each of the plurality of regions of interest to each magnetic field disturbance sample 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 disturbance samples to another one of the plurality of magnetic field disturbance samples.

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

comparing each magnetic field disturbance sample within each of the plurality of regions of interest to each magnetic field disturbance sample 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 disturbance sample within each of the plurality of regions of interest with respect to each magnetic field disturbance sample 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 disturbance samples, a squared distance between two location estimates respectively associated with the two input magnetic field disturbance samples, and a squared difference between two headings respectively associated with the two input magnetic field disturbance samples.

20. The non-transitory computer-readable medium of claim 19, wherein comparing each magnetic field disturbance sample within each of the plurality of regions of interest to each magnetic field disturbance sample 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 disturbance samples respectively having a comparison score that is less than a threshold value.