Classifying entities in digital maps using discrete non-trace positioning data

Patent metadata

Field	Value
Publication number	US-11255678-B2
Application number	US-201615159124-A
Country	US
Kind code	B2
Filing date	May 19, 2016
Priority date	May 19, 2016
Publication date	Feb 22, 2022
Grant date	Feb 22, 2022

Abstract

Systems, methods, and software are disclosed herein for enhancing entity classification operations for digital maps. In an implementation, an entity classification system associates tiles in a grid overlaying a map with discrete positioning records produced by devices operating in areas represented in the map. For each tile in an area of interest in the grid, the system produces a scalar description based on a subset of the discrete positioning records associated with the tile. The system then performs a binary classification of each tile as a type of entity (e.g. a road, business, or residence) based on the scalar description of the tile and the scalar descriptions of other tiles in the area of interest.

First claim

The invention claimed is:

1. A method, performed by a processor of a classification system, for automatically identifying roads in digital maps comprising:
receiving, from mobile devices, discrete positioning records to be stored in a database;
associating the discrete positioning records, obtained from the database, produced by the mobile devices, with tiles in a grid, including associating at least one discrete positioning record produced by a first mobile device of the mobile devices and at least one discrete positioning record produced by a second mobile device of the mobile devices;
producing, for at least an area of interest in the grid, feature vectors for each tile of the tiles in the area of interest based on a subset of the discrete positioning records, the subset including the at least one discrete positioning record produced by the first mobile device and the at least one discrete positioning record produced by the second mobile device;
for a tile of the tiles in the area of interest, performing a binary classification of the tile as a road based at least in part on a feature vector produced for the tile and other feature vectors produced for other tiles in the area of interest; and
generating a map update based on the binary classification indicating that the tile is a road.

2. The method of claim 1 wherein producing the feature vectors comprises:
deriving features from data included in the discrete positioning records; and
constructing the feature vector from the features.

3. The method of claim 1 further comprising submitting the feature vectors as an input to an anomaly detection classifier that processes a historical model of the area of interest and the feature vectors to detect changes in patterns of the tiles.

4. The method of claim 1 wherein the other tiles comprise a subset of the tiles in the area of interest that surround the tile in the grid.

5. The method of claim 4 wherein the feature vector for the tile comprises statistics on the subset of the discrete positioning records.

6. The method of claim 5 wherein the statistics comprise a quantity of records, a mean speed, a variance of speed, a mean heading, a variance of heading, and a covariance of each of the statistics.

7. The method of claim 6 wherein the discrete positioning records comprise non-trace Global Positioning System (GPS) records.

8. A computing apparatus comprising:
one or more computer readable storage media;
a processing system of a classification system operatively coupled with the one or more computer readable storage media; and
program instructions stored on the one or more computer readable storage media for automatically identifying roads in digital maps that, when executed by the processing system, direct the processing system to at least:
receive, from mobile devices, discrete positioning records to be stored in a database;
associate the discrete positioning records, obtained from the database, produced by the mobile devices, with tiles in a grid, including associating at least one discrete positioning record produced by a first mobile device of the mobile devices and at least one discrete positioning record produced by a second mobile device of the mobile devices;
produce, for at least an area of interest in the grid, feature vectors for each tile of the tiles in the area of interest based on a subset of the discrete positioning records, the subset including the at least one discrete positioning record produced by the first mobile device and the at least one discrete positioning record produced by the second mobile device;
for a tile of the tiles in the area of interest, perform a binary classification of the tile as a road based at least in part on a feature vector produced for the tile and other feature vectors produced for other tiles in the area of interest; and
generate a map update based on the binary classification indicating that the tile is a road.

9. The computing apparatus of claim 8 wherein, to produce the feature vectors, the program instructions direct the processing system to:
derive features from data included in the discrete positioning records; and construct the feature vector from the features.

10. The computing apparatus of claim 9 wherein the program instructions direct the processing system to submit the feature vectors as an input to an anomaly detection classifier.

11. The computing apparatus of claim 8 wherein the other tiles comprise a subset of the tiles in the area of interest that surround the tile in the grid.

12. The computing apparatus of claim 11 wherein the feature vector for the tile comprises statistics on the subset of the discrete positioning records.

13. The computing apparatus of claim 12 wherein the statistics comprise a quantity of records, a mean speed, a variance of speed, a mean heading, and a variance of heading.

14. The computing apparatus of claim 13 wherein the discrete positioning records comprise non-trace Global Positioning System (GPS) records.

15. A method for automatically identifying map features in digital maps comprising:
via one or more processors of a classification system:
receiving, from mobile devices, discrete positioning records to be stored in a database;
associating the discrete positioning records, obtained from the database, produced by the mobile devices, with tiles in a grid, including associating at least one discrete positioning record produced by a first mobile device of the mobile devices and at least one discrete positioning record produced by a second mobile device of the mobile devices;
producing, for at least an area of the interest in the grid, feature vectors for each tile of the tiles in the area of interest based on a subset of the discrete positioning records, the subset including the at least one discrete positioning record produced by the first mobile device and the at least one discrete positioning record produced by the second mobile device;
for a tile of the tiles in the area of interest, classifying the tile as one of a plurality of possible map features based at least in part on a feature vector produced for the tile and other feature vectors produced for other tiles in the area of interest; and
generating a map update based on the binary classification indicating that the tile is one of the plurality of possible map features.

16. The method of claim 15 wherein producing the feature vectors comprises:
deriving features from data included in the discrete positioning records; and
constructing the feature vector from the features.

17. The method of claim 15 wherein the plurality of possible map features comprises a road, a business, and a residence.

18. The method of claim 17 wherein the feature vector for the tile comprises statistics on the subset of the discrete positioning records.

19. The method of claim 18 wherein the statistics comprise a quantity of records, a mean speed, a variance of speed, a mean heading, and a variance of heading.

20. The method of claim 15 wherein the discrete positioning records comprise non-trace Global Positioning System (GPS) records.

21. The method of claim 1 , wherein the feature vector is a set of numerical descriptors that represent the tile.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Racz David L

Classifications

• G06F16/29 Primary

  Geographical information databases · CPC title

• G01S19/13

  Receivers · CPC title

• G01C21/32 Primary

  Structuring or formatting of map data · CPC title

• G01C21/3815

  Road data · CPC title

• G01C21/3881 Primary

  Tile-based structures · CPC title