Tiling of map data

• US 8,849,308 B2
• Filed: 11/21/2012
• Issued: 09/30/2014
• Est. Priority Date: 11/21/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Marti, Lukas M., Mayor, Robert, Ma, Shannon M.
• Primary Examiner(s): Siddiqui, Kashif
• Application Number:
  US13/683,401
• Publication Number:
  US 20140141803A1
• Time in Patent Office: 678 Days
• Field of Search: 4554141-4144, 4554561-457
• US Class Current: 455/456.2
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/383 Indoor data
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G01S 5/02525 Gathering the radio frequency fingerprints
• CPC Class Codes: G01S 5/02528 Simulating radio frequency fingerprints
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings
• CPC Class Codes: H04W 4/80 Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication

Abstract

A mobile device can send a request to a server having a plurality of tiles of location data associated with a venue, each tile having location data associated with a portion of the venue, the request including data representing an estimated location of the mobile device. The mobile device can receive a first tile of location data sent from the server, the first tile being associated with a first portion of the venue that includes the estimated location. The mobile device can receive a first sensor reading and determine a first location of the mobile device at the venue using the first sensor reading and the first tile of location data. The mobile device may receive a second tile of location data sent from the server, the second tile being associated with a second portion of the venue. The mobile device may receive a second sensor reading and determine a second location of the mobile device at the venue using the second sensor reading and the second tile of location data.

Claims

1. A computer-implemented method, comprising:

sending, from a mobile device, a request to a server having a plurality of tiles of location data associated with a venue, the venue comprising a space accessible by a movable body carrying the mobile device and one or more constraints of movement of the movable body, each tile having location data associated with a portion of the venue, the request including data representing an estimated location of the mobile device;

receiving, at the mobile device, a first tile of location data sent from the server, the first tile being associated with a first portion of the venue that includes the estimated location;

receiving a first sensor reading from a sensor of the mobile device;

determining a first location of the mobile device at the venue using the first sensor reading and the first tile of location data;

receiving, at the mobile device, a second tile of location data sent from the server, the second tile being associated with a second portion of the venue;

receiving a second sensor reading from the sensor; and

determining a second location of the mobile device at the venue using the second sensor reading and the second tile of location data.

2. The method of claim 1 in which the location data in each tile include local coordinates that use a local reference point in the region associated with the tile, the tile including information indicating an offset of the local reference point relative to a global reference point of the venue.

3. The method of claim 2, comprising converting coordinates of the location data of the first tile to generate global location data that use the global reference point of the venue as reference.

4. The method of claim 3 in which determining the location of the mobile device comprises determining the location of the mobile device using the global location data.

5. The method of claim 2, comprising converting coordinates of the location data of two or more tiles to generate global location data that use the global reference point of the venue as reference, and merging the global location data from the two or more tiles.

6. The method of claim 1 in which each tile comprises at least one of location fingerprint data, data on pathways, or data on the one or more constraints of movement of the movable body.

7. The method of claim 1 in which the location data in each tile comprises at least one of location fingerprint data, data on pathways, and data on the one or more constraints of movement of the pedestrian, and

determining the first location of the mobile device comprises

generating an observation based on the sensor reading and the location fingerprint data, and

implementing a location estimator using a state space model to determine the first location based on the observation, the data on pathways, and the data on the one or more constraints.

8. The method of claim 1, comprising sending from the mobile device a request to the server to request the second tile upon detecting that the mobile device is moving out of the first portion of the venue associated with the first tile, or upon detecting that the mobile device is moving toward the second portion of the venue associated with the second tile.

9. A computer-implemented method, comprising:

receiving, at a mobile device, a subset of tiles selected from a plurality of tiles of location data from a server, the plurality of tiles being associated with a venue comprising a space accessible by a pedestrian and one or more constraints of movement of the pedestrian, each tile having location data associated with a portion of the venue;

determining a location estimate of the mobile device using the locally stored subset of tile or tiles of location data and a reading from a sensor of the mobile device;

updating the locally stored subset of tile or tiles by downloading a new tile from the server, the new tile selected based on the location estimate; and

determining an updated location estimate of the mobile device using the updated locally stored subset of tile or tiles of location data and an updated reading from the sensor of the mobile device.

10. The method of claim 9 in which the location data in each tile include coordinates that use a local reference point associated with the tile, the tile including information indicating an offset of the local reference point relative to a global reference point of the venue.

11. The method of claim 10, comprising converting coordinates of the location data of the locally stored tile to generate converted location data that use the global reference point of the venue as reference.

12. The method of claim 11 in which determining the location estimate of the mobile device comprises determining the location estimate of the mobile device using the converted location data and the sensor reading.

13. The method of claim 10, comprising converting coordinates of the location data of two or more tiles to generate converted location data that use the global reference point of the venue as reference, and merging the converted location data from the two or more tiles.

14. The method of claim 9 in which the location data in each tile comprises at least one of location fingerprint data, data on pathways, or data on the one or more constraints of movement of the pedestrian.

15. The method of claim 9, comprising continuously updating the tiles locally stored at the mobile device so that as the mobile device moves to various regions in the venue, the mobile device maintains a tile that is associated with a region that includes the location estimate of the mobile device and at least one additional tile.

16. The method of claim 9 in which the location data in each tile comprises at least one of location fingerprint data, data on pathways, and data on the one or more constraints of movement of the pedestrian, and

determining the location estimate of the mobile device comprises

generating an observation based on the sensor reading and the location fingerprint data, and

implementing a location estimator using a state space model to determine the first location based on the observation, the data on pathways, and the data on the one or more constraints.

17. A computer-implemented method, comprising:

determining, at a mobile device, a first estimated location of the mobile device;

downloading a first tile of map data from a server based on the first estimated location, the first tile representing a first region that includes the first estimated location;

converting coordinates of the map data in the first tile according to a reference coordinate system to generate first converted map data;

determining a second estimated location of the mobile device using the first converted map data;

downloading a second tile of map data from the server based on the second estimated location, the second tile representing a second region that includes the second estimated location;

converting coordinates of the map data in the second tile according to the reference coordinate system to generate second converted map data; and

determining a third estimated location of the mobile device using the second converted map data.

18. The method of claim 17 in which the location data in each tile comprises at least one of location fingerprint data, data on pathways, and data on the one or more constraints of movement of the pedestrian, and

determining the second estimated location of the mobile device comprises

generating an observation based on a sensor reading and the location fingerprint data, and

implementing a location estimator using a state space model to determine the second estimated location based on the observation, the data on pathways, and the data on the one or more constraints.

19. A mobile device comprising:

a sensor to sense an environment variable;

a storage configured to locally store a subset of a plurality of tiles associated with a venue, the venue comprising a space accessible by a movable body carrying the mobile device and one or more constraints of movement of the movable body, each tile having location data associated with a portion of the venue; and

a processor configured to

determine a location estimate of the mobile device using the locally stored subset of tile or tiles of location data and a reading from the sensor, and

update the locally stored subset of tile or tiles based on the location estimate of the mobile device by downloading a new tile of location data from a server that stores the plurality of tiles associated with the venue.

20. The mobile device of claim 19 in which the location data in each tile comprises at least one of location fingerprint data, data on pathways, or data on the one or more constraints of movement of the movable body.

21. The mobile device of claim 20 in which the location data in each tile comprises location fingerprint data, data on pathways, and data on the one or more constraints of movement of the movable body, and the processor is configured to

generate an observation based on the sensor reading and the fingerprint data, and

implement a location estimator using a state space model for determining the location estimate based on the observation, the data on pathways, and the data on the one or more constraints.

22. The mobile device of claim 19 in which the location data in each tile comprises location fingerprint data that includes multi-dimensional data having an environment variable dimension and a location dimension, wherein:

the environment variable dimension of the location fingerprint data corresponds to the one or more environment variables;

the location dimension of the location fingerprint data corresponds to coordinates of the one or more locations; and

one or more values in the location fingerprint data at a given location and given environment variable corresponds to a probability distribution that includes an expected value and a variance of the environment variable at the given location.

23. The mobile device of claim 19 in which the venue comprises multiple floors, and the plurality of tiles comprise a first tile associated with a first floor and a second tile associated with a second floor.

24. An apparatus comprising:

a computer storage medium storing instructions that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising;

receive a subset of tiles selected from a plurality of tiles of location data from a server, the plurality of tiles being associated with a venue comprising a space accessible by a movable body and one or more constraints of movement of the movable body, each tile having location data associated with a portion of the venue, the mobile device locally storing a subset of tile or tiles less than all the tiles associated with the venue;

determine a location estimate of the mobile device using the locally stored subset of tile or tiles of location data and a reading from a sensor of the mobile device;

update the locally stored subset of tile or tiles by downloading a new tile from the server, the new tile selected based on the location estimate; and

determine an updated location estimate of the mobile device using the updated locally stored subset of tile or tiles of location data and an updated reading from the sensor of the mobile device.

25. The apparatus of claim 24 in which the location data in each tile include coordinates that use a local reference point associated with the tile, the tile including information indicating an offset of the local reference point relative to a global reference point of the venue, and

the computer storage medium further stores instructions that cause the data processing apparatus to convert coordinates of the location data of the locally stored tile to generate converted location data that use the global reference point of the venue as reference, and

wherein determine the location estimate of the mobile device comprises determine the location estimate of the mobile device using the converted location data and the sensor reading.