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

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.

TECHNICAL BACKGROUND

Digital maps have become indispensable tools of modern life that allow people to quickly and easily navigate to their destination, find places of interest, and otherwise explore their surroundings. While sometimes taken for granted, a great deal of advanced technology and manual effort are required to construct, curate, and maintain maps over time.

Specially equipped vehicles are utilized in some situations to travel the roads while recording street details. However, it is difficult to keep up with road changes just by driving every street, in addition to being a time consuming and expensive endeavor. Aerial imagery is utilized in other situations, but also has limits with respect to staying current and capturing the direction, speed, controls, and restrictions of a road.

Global Positioning System (GPS) traces have been used to overcome the challenges mentioned above, but come with limitations of their own. For example, multiple GPS points are needed to build a given trace, which limits the anonymity of such traces. The lack of anonymity influences users to limit their availability, which in turn reduces their effectiveness as a resource for inferring the presence roads and their details in a map.

OVERVIEW

Technology is disclosed herein that improves the creation, curating, and maintenance of 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. Then, the system 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.

TECHNICAL DISCLOSURE

Classification technology is disclosed herein that allows entities in digital maps, such as roads, business, and residences, to be identified from discrete positioning data. In some examples, the data include anonymous, non-trace Global Positioning Satellite (GPS) data collected from devices operating in areas represented in the maps. WiFi data, cellular information, and other such data may also be utilized in some examples. The devices may include, for example, mobile phones, dedicated location devices, equipment embedded in automobiles, or any other device capable of reporting positioning data.

An entity classification system utilizes a tile-based approach to identify entities in the maps, such as roads, businesses, and residences. The tile-based approach considers a map in terms of a grid on the map, defined in terms of longitude and latitude. The discrete positioning data may be plotted on the map such that each data point can be represented visually within a given tile. The tile-based approach then calls for analyzing a scalar description of each tile that is produced from the discrete positioning data associated with each tile. The scalar description of other tiles associated with a given tile are also considered in the analysis.

A binary classification is then performed for each tile based on the scalar descriptions of the tile and the other tiles associated with it. For instance, the entity classification system classifies a tile as belonging to a road (or not), a business (or not), or a residence (or not). A second layer of classification may also be performed to determine sub-characteristics of a given tile. Other characteristics of a tile that it may be possible to classify include the geometry and connectivity of roads, the direction of travel, speed limits, turn restrictions, traffic patterns, elevations, and the popularity of prominence of places.

In some implementations, the scalar description of a tile is a feature vector that is provided as input to a classifier model. The classifier model may be trained using machine learning techniques to recognize a road, a business, a residence, or the like. The feature vector itself may be generated from features derived from the discrete positioning data associated with a given tile. For example, the features may indicate various statistics on a given tile, such as the quantity of positioning records per tile, the average speed reported for each tile, the variance of speed, a mean heading, and a variance of heading for a tile. It may be appreciated that a feature in the context of machine learning technology is an individual measurable property of a phenomenon being observed, the aforementioned statistics being exemplary of such features.

The feature vectors may also be utilized in the context of anomaly detection to discover changes in maps after they have been classified. For instance, the feature vectors may be input to an anomaly detection algorithm to detect road closures, land closures, unusual traffic patterns, new businesses, business closures, and trending places. In one scenario, new data is aggregated in and compared to a historical model of a given area at various resolutions (venue size, neighborhood size, city size, etc.). Areas with the greatest differences between the historical model and the new data are identified using any of a variety of anomaly detection techniques, such as Cosine similarity, Jaccard similarity, and Gaussian discriminate analysis. The areas that differ greater than a threshold amount are flagged for new classification analysis.

In the aggregate, the classification of tiles using the tile-based approach described above allows roads and other map entities to be discovered from discrete, anonymous positioning data. Various technical effects of the technology is the reduction of manual effort that is otherwise required by prior art classification processes. Non-trace data is effectively anonymous and is easier to process relative to trace data because the non-trace data can be treated independently. In addition, new roads, changes in roads, and other physical variations that arise in areas covered by a map can be discovered and mapped more easily, without requiring physical roads to be driven or aerial photographs to be taken, both of which are resource intensive endeavors.

FIG. 1illustrates an operational architecture100in an implementation of enhanced classification technology. Operational architecture100includes entity classification system101, which employs classification process200in the context of classifying entities in digital maps. GPS records103are provided as input to entity classification system101, as are training records105. Entity classification system101outputs a map121that has been updated via classification process200. Entity classification system101and classification process200may be implemented using any suitable computing system or systems (physical and/or virtual), of which computing system701inFIG. 7is representative.

GPS records103are representative of discrete positioning records that may be reported by mobile phones, global positioning devices, embedded automobile equipment, or any other suitable devices capable of reporting such information. Device111and device113, and record112and record114, are representative of such devices and records respectively.

Referring parenthetically to the steps inFIG. 2, in operation entity classification system101associates GPS records with the tiles in a grid125overlaid with respect to a map being updated, produced from scratch, or otherwise processed (step201). The GPS records may be visualized as points123on the map121.

The number of records associated with a given tile may vary, as well as the size of the tile itself. For example, the number of records could be varied by changing the size of the historical window for positioning data for a given tile. A one-month window would result in one set of data, while a three-month window would result in more data, and so on. How far back to include positioning data could be varied based on a desired level of precision, a desired level of speed, or some other configurable setting.

The size of an area on the ground corresponding to a tile can also be varied and may depend on the granularity of a map. For example, a tile could be set to correspond to a 3-meter by 3-meter area on the ground. Adjusting the tile-to-ground correspondence could be performed to increase precision, increase speed, or achieve some other performance goal.

Next, entity classification system101produces a scalar description of each tile in the map121from the GPS records associated with each tile (step203). The scalar description may include, for example, the quantity of records associated with a tile, the average position of the tiles, the average speed of the tiles, the average heading, and the average accuracy.

Entity classification system101then performs a binary classification of a tile as a road or some other type of entity using the scalar description of the tile and the scalar description of other tiles as input (Step205). In a brief example, the scalar description of the tile and that of the other tiles may be compared to scalar descriptions of labeled tiles for which an entity classification is already know.

FIG. 3illustrates an operational scenario300in another example of the features and functionality of an entity classification system. In operational scenario300, a map301includes a visualization303of a set of discrete positioning points. The points may be derived from anonymous, non-trace GPS records and are plotted in the map301per their latitude and longitude.

An area of interest305may be selected in the map301for classification analysis. A zoomed-in view306of the area of interest305includes a grid overlaid with respect to the area of interest. The grid includes tiles defined in terms of a-i on the x-axis and 1-7 on the y-axis. The entity classification system produces a scalar description of each tile in the area of interest305. The difference in the scalar descriptions is represented visually by different fill patterns in the tiles.

Each tile may be classified based on its scalar description and at least one other scalar description for at least one other tile. In this example, the other tiles surrounding a given tile may be used to classify the tile. For instance, if tile f4is being classified, then its scalar description and the scalar descriptions for tiles e3-5, f3, f5, and g3-5would be considered. If tile e3is being classified, then its scalar description and the scalar descriptions for tiles d2-4, e2, e4, and f2-f4would service as input to the classifier.

Once the entities in a map have been identified and/or updated, a visualization of the entities can be produced. In this simplified example, visualization307represents the roads that may have been identified by the entity classification system from the anonymous, non-trace GPS data. It may be appreciated that the data points in tiles c2and f6were not classified as roads and, as such, no road is present in that space in visualization307.

FIG. 4illustrates a GPS record400that could service as the basis for producing scalar descriptions of tiles. GPS record400indicates positioning information, such as time, latitude and longitude, X and Y coordinates, altitude, speed, heading, and accuracy, among other information. Such information can be aggregated for each tile in a map and processed to produce the scalar description of the tile. For instance, tens, hundreds, thousands, or even more individual records could be associated with a given tile. The scalar description of the tile may then be derived from an analysis of all of the records for the tile. Average speed, averaged heading, variances, and other information could be calculated from all of the tiles and used to describe the tile.

In some implementations, the scalar description for a tile is a feature vector and each value in the feature vector may be considered a feature of the tile. The feature vector may then serve as input to a classifier(s) engine that is capable of ascertaining whether or not the tile is part of a road, a business, a residence, or some other type of map entity.

Machine learning techniques may be employed to train the classifier engine, using mapping information for which the entities in a map are known. A machine algorithm(s) produces a model or models from the training data that may then be applied to classify (or re-classify) entities in maps.

FIG. 5illustrates a classification process500that may be employed by an entity classification system in an implementation. The entity classification system first discretizes sensor data (step501). The sensor data is then aggregated (step503), meaning that individual data points may be associated with a specific tile in a map. Each tile in a grid defining a map will thus have a set of discrete positioning records of points associated with it. Features are calculated from the sensor data for each tile and are used to construct the feature vectors that service as input to classifier models (step505).

In the meantime, training data is labeled (step507) and used to train the classifier models (step509). For instance, feature vectors are produced for tiles for which the entity type of the tile is known. The known feature vectors then become part of a model that is used to evaluated unknown tiles. The unknown tiles are thus classified (511) by a classification engine in view of the classification models built from the training data (513). The newly-identified tiles may also serve as training data in some implementation.

Once the tiles in an area of interest have been classified, a map or maps may be updated to reflect the type of each of the tiles. For instance, a tile may be classified as a road and its description updated in a mapping database. Eventually, the updated map is used by people on the ground to navigate, find places of interest, and so on.

FIG. 6illustrates another classification process600in an implementation. In operation, an entity classification system receives uploads of raw records602. The raw records may be, for example, anonymous, non-trace GPS data produced over time by GPS devices deployed in smart phones, personal GPS devices, cars, and the like.

The raw records602are cleaned (step603) to produce clean records604, which are then published daily in XML (step605). The daily XML records606are provided as input to a GPS extraction function (step607), which extracts specific pieces of data from the daily XML records606to produce discretized streams of data608. Other protocols in place of or in addition to XML may be used.

The discretized streams of data are aggregated (step609) on a per-tile basis with respect to the map or maps that cover the areas specific to a given record. Aggregated tiles610are produced in this step, which provide the input to a smoothing step (step611). The smoothing produces smoothed tiles612, which are the input to several next steps.

In one path, neighbor tiles are joined to each other (step613) and feature vectors615are produced. The feature vectors615are input to a training step and an anomaly detection step.

Referring back to the smoothed tiles612, they are used to generate *.ply files (step621). The *.ply files623are provided as input to be viewed in a polygon viewer. The smoothed tiles612are also processed to generate a bitmap (step631). The bitmaps633can be viewed in a bitmap viewer (step635). These steps are optional and may be useful for demonstration and debugging purposes.

In some implementations, the smoothed tiles612are also used to join roads (step641), in which case the smoothed tiles612become labeled tiles643. The labeled tiles643are processed to produced training data (step645). Training data647is submitted as input to machine learning systems to train classifier models (step649).

The classifier models may include a road classifier651, an attribute classifier653, a business classifier655, and a residence classifier657. Other classifiers in addition to or in place of those included herein are possible. The classifiers are applied to the data to classify the entities within a map as a road, attribute, business, or residence, for example (step661). The classifications663are then used to produce map updates685.

In addition to being provided as input to classify entities, the feature vectors615are also provided as input update the classifier models (step671) and as input to detect anomalies (step675). The historical models673can be processed against the feature vectors615to detect changes681over time and to detect errors677. Anomaly detection can be provided as input to a moderation process683that may provide a moderating influence on the map updates685driven by the classifications663.

FIG. 7illustrates computing system701, which is representative of any system or collection of systems in which the various applications, services, scenarios, and processes disclosed herein may be implemented. Examples of computing system701include, but are not limited to, server computers, rack servers, desktop computers, or any other type of computing system suitable for carrying out the classification operations described herein. Such systems may employ one or more virtual machines, containers, or any other type of virtual computing resource in the context of classifying map entities.

Computing system701may be implemented as a single apparatus, system, or device or may be implemented in a distributed manner as multiple apparatuses, systems, or devices. Computing system701includes, but is not limited to, processing system702, storage system703, software705, communication interface system707, and user interface system709. Processing system702is operatively coupled with storage system703, communication interface system707, and user interface system709.

Processing system702loads and executes software705from storage system703. Software705includes classification process706which is representative of the processes discussed with respect to the precedingFIGS. 1-6, including classification processes200,500, and600. When executed by processing system702to enhance classification operations, software705directs processing system702to operate as described herein for at least the various processes, operational scenarios, and sequences discussed in the foregoing implementations. Computing system701may optionally include additional devices, features, or functionality not discussed for purposes of brevity.

Referring still toFIG. 7, processing system702may comprise a micro-processor and other circuitry that retrieves and executes software705from storage system703. Processing system702may be implemented within a single processing device, but may also be distributed across multiple processing devices or sub-systems that cooperate in executing program instructions. Examples of processing system702include general purpose central processing units, application specific processors, and logic devices, as well as any other type of processing device, combinations, or variations thereof.

In addition to computer readable storage media, in some implementations storage system703may also include computer readable communication media over which at least some of software705may be communicated internally or externally. Storage system703may be implemented as a single storage device, but may also be implemented across multiple storage devices or sub-systems co-located or distributed relative to each other. Storage system703may comprise additional elements, such as a controller, capable of communicating with processing system702or possibly other systems.

Software705may be implemented in program instructions and among other functions may, when executed by processing system702, direct processing system702to operate as described with respect to the various operational scenarios, sequences, and processes illustrated herein. For example, software705may include program instructions for implementing enhanced entity classification for digital maps.

In general, software705may, when loaded into processing system702and executed, transform a suitable apparatus, system, or device (of which computing system701is representative) overall from a general-purpose computing system into a special-purpose computing system customized to enhance entity classification operations. Indeed, encoding software705on storage system703may transform the physical structure of storage system703. The specific transformation of the physical structure may depend on various factors in different implementations of this description. Examples of such factors may include, but are not limited to, the technology used to implement the storage media of storage system703and whether the computer-storage media are characterized as primary or secondary storage, as well as other factors.

User interface system709may include a keyboard, a mouse, a voice input device, a touch input device for receiving a touch gesture from a user, a motion input device for detecting non-touch gestures and other motions by a user, and other comparable input devices and associated processing elements capable of receiving user input from a user. Output devices such as a display, speakers, haptic devices, and other types of output devices may also be included in user interface system709. In some cases, the input and output devices may be combined in a single device, such as a display capable of displaying images and receiving touch gestures. The aforementioned user input and output devices are well known in the art and need not be discussed at length here.

User interface system709may also include associated user interface software executable by processing system702in support of the various user input and output devices discussed above. Separately or in conjunction with each other and other hardware and software elements, the user interface software and user interface devices may support a graphical user interface, a natural user interface, or any other type of user interface.

Communication between computing system701and other computing systems (not shown), may occur over a communication network or networks and in accordance with various communication protocols, combinations of protocols, or variations thereof. Examples include intranets, internets, the Internet, local area networks, wide area networks, wireless networks, wired networks, virtual networks, software defined networks, data center buses, computing backplanes, or any other type of network, combination of network, or variation thereof. The aforementioned communication networks and protocols are well known and need not be discussed at length here. In any of the aforementioned examples in which data, content, or any other type of information is exchanged, the exchange of information may occur in accordance with any of a variety of well-known data transfer protocols.

Certain inventive aspects may be appreciated from the foregoing disclosure, of which the following are various examples.

A method for automatically identifying roads in digital maps comprising: associating tiles in a grid overlaying a map with discrete positioning records produced by mobile devices operating in areas represented in the map; producing a scalar description of each tile in an area of interest in the grid based on a subset of the discrete positioning records associated with the tile; and for each of the tiles in the area of interest, performing a binary classification of the tile as a road based at least in part on the scalar description produced for the tile and other scalar descriptions produced for other tiles in the area of interest.

The method of Example 1 wherein the scalar description of each of the tiles in the area of interest comprises a feature vector having features and wherein producing the scalar description comprises: deriving the features from data included in the discrete positioning records; and constructing the feature vector from the features.

The method of Examples 1-2 wherein performing the binary classification of the tile comprises submitting the feature vector for the tile and other feature vectors for the other tiles as input to a binary classifier.

The method of Examples 1-3 wherein the other tiles comprise a subset of the tiles in the area that surround the tile in the grid.

The method of Examples 1-4 wherein the scalar description for the tile comprises statistics on the subset of the discrete positioning records associated with the tile.

The method of Examples 1-5 wherein the statistics comprise a quantity of records, a mean speed, a variance of speed, a mean heading, and a variance of heading.

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

A computing apparatus comprising: one or more computer readable storage media; a processing 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: associate tiles in a grid overlaying a map with discrete positioning records produced by mobile devices operating in areas represented in the map; produce a scalar description of each tile in an area of interest in the grid based on a subset of the discrete positioning records associated with the tile; and for each of the tiles in the area of interest, perform a binary classification of the tile as a road based at least in part on the scalar description produced for the tile and other scalar descriptions produced for other tiles in the area of interest.

The computing apparatus of Example 8 wherein the scalar description of each of the tiles in the area of interest comprises a feature vector having features and wherein, to produce the scalar description, the program instructions direct the processing system to: derive the features from data included in the discrete positioning records; and construct the feature vector from the features.

The computing apparatus of Examples 8-9 wherein, to perform the binary classification of the tile, the program instructions direct the processing system to submit the feature vector for the tile and other feature vectors for the other tiles as input to a binary classifier.

The computing apparatus of Examples 8-10 wherein the other tiles comprise a subset of the tiles in the area that surround the tile in the grid.

The computing apparatus of Examples 8-11 wherein the scalar description for the tile comprises statistics on the subset of the discrete positioning records associated with the tile.

The computing apparatus of Examples 8-12 wherein the statistics comprise a quantity of records, a mean speed, a variance of speed, a mean heading, and a variance of heading.

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

A method for automatically identifying map features in digital maps comprising: associating tiles in a grid overlaying a map with discrete positioning records produced by mobile devices operating in areas represented in the map; producing a scalar description of each tile in an area of interest in the grid based on a subset of the discrete positioning records associated with the tile; and for each of the tiles in the area of interest, classifying the tile as a one of a plurality of possible map features based at least in part on the scalar description produced for the tile and other scalar descriptions produced for other tiles in the area of interest.

The method of Example 15 wherein the scalar description of each of the tiles in the area of interest comprises a feature vector having features and wherein producing the scalar description comprises: deriving the features from data included in the discrete positioning records; and constructing the feature vector from the features.

The method of Examples 15-16 wherein the plurality of possible map features comprises a road, a business, and a residence.

The method of Examples 15-17 wherein the scalar description for the tile comprises statistics on the subset of the discrete positioning records associated with the tile.

The method of Examples 15-18 wherein the statistics comprise a quantity of records, a mean speed, a variance of speed, a mean heading, and a variance of heading.

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