Compressing radio maps

• US 10,151,824 B1
• Filed: 09/29/2017
• Issued: 12/11/2018
• Est. Priority Date: 06/02/2017
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Millman, David Benjamin, Singh, Jasvinder, Holtsberg, Anders M., Tay, Darin
• Primary Examiner(s): Bilgrami, Asghar
• Application Number:
  US15/721,596
• Publication Number:
  US 20180348334A1
• Time in Patent Office: 438 Days
• CPC Class Codes: G01S 5/02527 Detecting or resolving anomalies in the radio frequency fingerprints of the radio-map
• CPC Class Codes: H04W 24/08 Testing, supervising or monitoring using real traffic
• CPC Class Codes: H04W 4/026 using orientation information, e.g. compass
• CPC Class Codes: H04W 48/20 Selecting an access point
• CPC Class Codes: H04W 64/003 locating network equipment

Abstract

Embodiments are disclosed for compressing radio maps of fingerprint-based positioning systems. In an embodiment, a method comprises: receiving access point (AP) data from a plurality of mobile devices operating in a geographic region, the AP data including signal strength measurements of AP signals received at a plurality of reference locations in the geographic region; filtering the AP data to remove outlier AP data; fitting a surface to the AP data; projecting AP data at surface control points onto a two-dimensional image grid; determining a boundary surrounding locations of the AP data at the surface control points; encoding the boundary; encoding the AP data at the surface control points included within the boundary; generating compressed radio maps from the encoded AP data; and responsive to a request from a mobile device operating in the geographic region, sending a data packet including the compressed radio maps to the mobile device.

Claims

1. A method comprising:

receiving, by a computing device, access point (AP) data from a plurality of mobile devices operating in a geographic region, the AP data including signal strength measurements of AP signals received at a plurality of reference locations in the geographic region;

filtering the AP data to remove outlier AP data;

fitting a surface to the AP data;

projecting AP data at surface control points onto a two-dimensional image grid;

determining a boundary surrounding locations of the AP data at the surface control points in the image grid;

encoding the boundary;

encoding the AP data at the surface control points included within the boundary;

generating compressed radio maps from the encoded AP data; and

responsive to a request from a mobile device operating in the geographic region, sending a data packet including the compressed radio maps to the mobile device.

2. The method of claim 1, wherein filtering AP data further comprises:

identifying non-servable APs in the AP data; and

excluding the non-servable APs from further processing.

3. The method of claim 1, wherein filtering AP data further comprises:

clustering the AP data;

identifying outlier AP signal strength measurements based on the clustering; and

excluding outlier AP signal strength measurements from further processing.

4. The method of claim 1, wherein fitting the surface to the AP data further comprises:

using bilinear interpolation to fit the surface to the AP data.

5. The method of claim 1, wherein prior to fitting the surface to the AP data, the AP data is quantized.

6. The method of claim 1, wherein determining the boundary further comprises:

applying contour detection to the projected signal strength measurements at the surface control points; and

encoding the boundary using an encoding process.

7. The method of claim 1, wherein the geographic region is divided into a grid of contiguous cells having a first size and the plurality of reference locations are in a plurality of the contiguous cells.

8. The method of claim 7, further comprising:

adjusting the first cell size to a second cell size based on the AP data.

9. The method of claim 8, wherein adjusting the first cell size to a second cell size further comprises:

(a) fitting the surface to the AP data corresponding to a set of contiguous cells;

(b) for the set of contiguous cells, calculating a joint likelihood of signal strength observations falling between the cells;

(c) determining that the likelihood is less than a threshold;

(d) dividing the set of cells in half; and

repeating steps (a) through (d) until the likelihood is greater than or equal to the threshold.

10. The method of claim 1, wherein the AP data includes AP signal strength measurements and uncertainty values corresponding to the AP signal strength measurements, and the method further comprises:

fitting surfaces to the signal strength measurements and the uncertainty values;

projecting signal strength measurements and uncertainty values at the surface control points onto a two-dimensional image grid;

determining a boundary surrounding locations of the signal strength measurements and corresponding uncertainty values at the surface control points in the image grid;

encoding the boundary;

encoding the signal strength measurements and corresponding uncertainty values at the surface control points that are included within the boundary; and

generating compressed radio maps from the encoded signal strength measurements and corresponding uncertainty values and the encoded boundary.

11. The method of claim 10, wherein the encoding scheme is at least one of predictive differential encoding, run length encoding or Rice encoding.

12. A system comprising:

one or more processors;

memory coupled to the one or more processors and configured to store instructions, which, when executed by the one or more processors, cause the one or more processors to perform operations comprising;

receiving access point (AP) data from a plurality of mobile devices operating in a geographic region, the AP data including signal strength measurements of AP signals received at a plurality of reference locations in the geographic region;

filtering the AP data to remove outlier AP data;

fitting a surface to the AP data;

projecting AP data at surface control points onto a two-dimensional image grid;

determining a boundary surrounding locations of the AP data at the surface control points in the image grid;

encoding the boundary;

encoding the AP data at the surface control points included within the boundary;

generating compressed radio maps from the encoded AP data; and

responsive to a request from a mobile device operating in the geographic region, sending a data packet including the compressed radio maps to the mobile device.

13. The system of claim 12, wherein filtering AP data further comprises:

identifying non-servable APs in the AP data; and

excluding the non-servable APs from further processing.

14. The system of claim 12, wherein filtering AP data further comprises:

clustering the AP data;

identifying outlier AP signal strength measurements based on the clustering; and

excluding outlier AP signal strength measurements from further processing.

15. The system of claim 12, wherein fitting the surface to the AP data further comprises:

using bilinear interpolation to fit the surface to the AP data.

16. The system of claim 12, wherein prior to fitting the surface to the AP data, the AP data is quantized.

17. The system of claim 12, wherein determining the boundary further comprises:

applying contour detection to the projected signal strength measurements at the surface control points; and

encoding the boundary using an encoding process.

18. The system of claim 12, wherein the geographic region is divided into a grid of contiguous cells having a first size and the plurality of reference locations are in a plurality of the contiguous cells.

19. The system of claim 18, wherein the operations further comprise:

adjusting the first cell size to a second cell size based on the AP data.

20. The system of claim 19, wherein adjusting the first cell size to a second cell size further comprises:

(a) fitting the surface to the AP data corresponding to a set of contiguous cells;

(b) for the set of contiguous cells, calculating a joint likelihood of signal strength observations falling between the cells;

(c) determining that the likelihood is less than a threshold;

(d) dividing the set of cells in half; and

repeating steps (a) through (d) until the likelihood is greater than or equal to the threshold.

21. The system of claim 12, wherein the AP data includes AP signal strength measurements and uncertainty values corresponding to the AP signal strength measurements, and the operations further comprise:

fitting surfaces to the signal strength measurements and the uncertainty values;

projecting signal strength measurements and uncertainty values at the surface control points onto a two-dimensional image grid;

determining a boundary surrounding locations of the signal strength measurements and corresponding uncertainty values at the surface control points in the image grid;

encoding the boundary;

encoding the signal strength measurements and corresponding uncertainty values at the surface control points that are included within the boundary; and

generating compressed radio maps from the encoded signal strength measurements and corresponding uncertainty values and the encoded boundary.

22. The system of claim 21, wherein the encoding scheme is at least one of predictive differential encoding, run length encoding or Rice encoding.

23. A method comprising:

receiving, by a computing device, access point (AP) data from a plurality of mobile devices operating in a geographic region, the AP data including signal strength measurements of AP signals received at a plurality of reference locations in the geographic region;

fitting a surface to the AP data;

projecting AP data at surface control points onto a two-dimensional image grid;

determining a boundary surrounding locations of the AP data at the surface control points in the image grid;

encoding the AP data at the surface control points included within the boundary;

generating compressed radio maps from the encoded AP data; and

responsive to a request from a mobile device operating in the geographic region, sending a data packet including the compressed radio maps to the mobile device.

24. The method of claim 23, further comprising:

identifying non-servable APs in the AP data and excluding the non-servable APs from further processing.

25. The method of claim 23, wherein filtering AP data further comprises:

clustering the AP data;

identifying outlier AP signal strength measurements based on the clustering; and

excluding outlier AP signal strength measurements from further processing.

26. The method of claim 23, wherein fitting the surface to the AP data further comprises:

using bilinear interpolation to fit the surface to the AP data.

27. The method of claim 23, wherein prior to fitting the surface to the AP data, the AP data is quantized.

28. The method of claim 23, wherein the AP data includes AP signal strength measurements and uncertainty values corresponding to the AP signal strength measurements, and the method further comprises:

fitting surfaces to the signal strength measurements and the uncertainty values;

projecting signal strength measurements and uncertainty values at the surface control points onto a two-dimensional image grid;

determining a boundary surrounding locations of the signal strength measurements and corresponding uncertainty values at the surface control points in the image grid;

encoding the boundary;

encoding the signal strength measurements and corresponding uncertainty values at the surface control points that are included within the boundary; and

generating compressed radio maps from the encoded signal strength measurements and corresponding uncertainty values and the encoded boundary.

29. A system comprising:

one or more processors;

memory coupled to the one or more processors and configured to store instructions that when executed by the one or more processors, cause the one or more processors to perform operations comprising;

receiving access point (AP) data from a plurality of mobile devices operating in a geographic region, the AP data including signal strength measurements of AP signals received at a plurality of reference locations in the geographic region;

fitting a surface to the AP data;

projecting AP data at surface control points onto a two-dimensional image grid;

determining a boundary surrounding locations of the AP data at the surface control points in the image grid;

encoding the AP data at the surface control points included within the boundary;

generating compressed radio maps from the encoded AP data; and

responsive to a request from a mobile device operating in the geographic region, sending a data packet including the compressed radio maps to the mobile device.

30. The system of claim 29, the operations further comprising:

identifying non-servable APs in the AP data; and

excluding the non-servable APs from further processing.

31. The system of claim 29, the operations further comprising:

clustering the AP data;

identifying outlier AP signal strength measurements based on the clustering; and

excluding outlier AP signal strength measurements from further processing.

32. The system of claim 29, wherein fitting the surface to the AP data further comprises:

using bilinear interpolation to fit the surface to the AP data.

33. The system of claim 29, wherein prior to fitting the surface to the AP data, the AP data is quantized.

34. The system of claim 29, wherein the AP data includes AP signal strength measurements and uncertainty values corresponding to the AP signal strength measurements, and the operations further comprise:

fitting surfaces to the signal strength measurements and the uncertainty values;

projecting signal strength measurements and uncertainty values at the surface control points onto a two-dimensional image grid;

determining a boundary surrounding locations of the signal strength measurements and corresponding uncertainty values at the surface control points in the image grid;

encoding the boundary;

encoding the signal strength measurements and corresponding uncertainty values at the surface control points that are included within the boundary; and

generating compressed radio maps from the encoded signal strength measurements and corresponding uncertainty values and the encoded boundary.