Patent ID: 12209868

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

Embodiments of the invention aim to identify locations at which discrepancies or deviations exist between real world features and digital map data intended to represent those features. The real world features include navigable features (features traversable by a vehicle) such as road segments. Embodiments of the invention aim to automate a process of detecting and identifying such discrepancies to reduce a required intervention of an operator.

FIG.1illustrates a method100according to an embodiment of the invention. The method100, when executed by a processor of a computing device, determines locations at which map data may differ from real world features which the map data is intended to represent. The method determines the locations based upon trace data comprising one or more traces from location-aware mobile devices. Each trace indicates a geographic position of each mobile device against time i.e. traces the path of the device.

A location-aware mobile device, herein referred to simply as a mobile device, is any device capable of determining its geographic location from wirelessly received signals. The received signals may include received GPS signals. The mobile device may be a navigation device such as a portable navigation device (PND), in-vehicle navigation device, mobile phone, portable computing device, vehicle tracking device, and the like. The following description will assume that the mobile device is a navigation device, although it will be realised that embodiments of the invention are not restricted in this respect.

The navigation device is arranged to record a trace of a path or route followed by the navigation device. The navigation device may store the trace in a local memory of the navigation device or may communicate the trace to a server computer, such as via a wireless data connection with the server computer. The trace may be formed from data indicative of a series of geographic locations at which the navigation device is located at periodic intervals. However in other embodiments the trace may be formed by data representing one or more curves indicative of the path of the navigation device. The method100may be used with trace data comprising one or more traces. In some embodiments of the invention the method100is used with a bundle comprising a plurality of traces. The plurality of traces may be received from one or more navigation devices. The method may comprise a step (not shown) of receiving the one or more traces from one or more mobile devices, such as navigation devices.

In step110the one or more traces are allocated to a pixel map.FIG.2illustrates the allocation of a trace210to a pixel map200. The pixel map is a two-dimensional array comprising a plurality of pixels each representative of a geographic area. Each pixel may represent a geographic area of any shape, although in the embodiment shown inFIG.2the pixel map comprises rectangular or square pixels. Rectangular pixels may be the most convenient shape to process by the method100executed by the processor and to store in a memory. The geographic area represented by each pixel may be of any size. The size may be dependent upon an accuracy to which the navigation device providing the probe data may determine its location. The area may be 5 m by 5 m, 3.5 m by 3.5 m or 2 m by 2 m, although it will be realised that these are merely exemplary and, furthermore, in some embodiments the height and width of the area may not be equal.

Each pixel stores a value indicative of a number of times that pixel is crossed by a trace. When the pixel map is initialised each pixel is set to a predetermined value, such as 0. The pixel value is incremented each time the pixel is crossed by a trace. Referring toFIG.2, the value for pixels220and230is incremented, amongst others, to indicate that the trace210crosses those pixels. It will be noted that even in cases where the trace is formed from a plurality of location values each indicative of the location of the navigation device at periodic intervals, should the trace comprise two or more location values within one pixel the value for that pixel is only incremented once to indicate the trace crossing the pixel, rather than once for each location within the pixel area. The pixel map values are incremented to reflect the number of times each of one or more traces crosses each pixel. Thus step110results in pixels which are crossed a greater number of times by traces storing a greater value.

It will be appreciated that, in the real world, most navigation devices will travel routes along roads in a road network. Occasionally, navigation devices will follow routes across other types of navigable location including private areas such as parking lots and the like. However the traces crossing these locations will be expected to be more random i.e. less constrained to following a particular path. Therefore pixels having a higher probability of corresponding to road locations will be expected to store greater values following step110.

Following step110a heat map may be displayed representative of the pixel map as shown inFIG.3. The heat map illustrates the values of the pixel map wherein brighter colours (those usually associated with higher temperatures) represent greater pixel values, i.e. more frequented locations. The axes ofFIG.3indicate a distance in meters from an origin point at a bottom left corner ofFIG.3. It can be appreciated fromFIG.3that most traces follow roads which appear inFIG.3in darker or similar “high temperature” colours whilst less traversed areas are indicated in lighter or similar “low temperature” colours. Based upon the pixel values it is possible to identify candidate locations having a relatively high probability of corresponding to navigable locations such as roadways, as will be described.

A direction map is also produced in step110. The direction map represents, for each pixel traversed by at least one trace, the direction in which the trace(s) traversed the pixel.

A directional histogram is stored for each pixel of the pixel map. In some embodiments a directional histogram may only be stored for each pixel which is traversed by at least one trace i.e. a directional histogram may only be initialised for a pixel once it is traversed by a trace and its corresponding pixel value incremented. In other embodiments a directional histogram may be initialised for each pixel of the pixel map.

The directional histogram comprises a plurality of bins each representative of a direction of trace(s) across the corresponding pixel. Upon initialisation a value corresponding to each bin in the histogram is set to a predetermined value, such as 0. The value is incremented each time a trace traverses the corresponding pixel in that direction. In one embodiment the bins correspond to directions of 0° to 30°; 30° to 60°; . . . 330° to 0°, although it will be realised that these angular divisions are merely exemplary and that other angular divisions may be envisaged.

Thus for each pixel in the pixel map200shown inFIG.2a value indicates the number of times the pixel is traversed by a trace and, for at least the pixels traversed once by one or more traces, a directional histogram stores data indicative of the direction of the trace traversing the pixel.

In step120candidate locations in the probe data having a high probability of corresponding to navigable features such as roadways are identified. In one embodiment, the candidate locations are identified by determining pixels corresponding to local maxima of traversal frequency in the trace data. In other words, pixels are identified which are most crossed in the trace data. The coordinates (xcent, ycent) of the local maxima in the pixel map may be determined as:

xcent=∑i⁢xi⁢vi∑i⁢vi⁢ycent=∑i⁢yi⁢vi∑i⁢vi
wherein xi, yiare the coordinates of the centre of mass of a pixel with a higher value than its adjacent pixels and v, is the value of the pixel.

The local maxima correspond to centroids which are pixel locations along roadway axles, or locations generally central along roads i.e. corresponding to a generally longitudinal axis of the road. Thus the centroids have a highest probability of corresponding to a spatial location of a road in the road network.FIG.4illustrates centroids identified from the pixel map illustrated inFIG.3.

In step130the centroids identified in step120are classified. That is, in step130the centroids are assigned to one or more of a plurality of classifications. The classifications indicate a type of navigable feature based upon the direction map produced in step120.

In order to classify the centroids, firstly in some embodiments of step130, the directional histograms are normalised. The directional histograms may be normalised such that a sum of values in all bins of each directional histogram is uniform.

The directional histograms are transformed into rotation invariant representations. The rotation invariant histogram is obtained by circularly shifting bin values of each directional histogram. The bins values may be shifted such that a predetermined bin, such as the first bin, contains a greatest value. These steps may be explained with reference to a histogram h comprising12bins:h=[0, 0, 0, 93, 0, 0, 26, 0, 0, 5, 0, 32]Normalised histogram→h′=[0, 0, 0, 0.596, 0, 0, 0.167, 0, 0, 0.032, 0, 0.205]Rotation invariant histogram→h″=[0.596, 0, 0, 0.167, 0, 0, 0.032, 0, 0.205, 0, 0, 0]

The conversion to the rotation invariant histogram allows a comparison between directional histograms to be made. By comparing the rotation invariant histograms they may be assigned to one of the plurality of categories. In some embodiments the histograms are classified by a stochastic model, such a Bayesian network which is trained to distinguish between histograms of the various categories. Other models may be useful such as decision tree classifiers, rule-based classifiers, neural networks, support vector machines and naive Bayes classifiers.

The categories relate to a type of navigable area which each centroid represents. In some embodiments, the classifications correspond to 1-way (unidirectional), 2-way (bi-directional), junction and clutter. A 1-way histogram typically has a large value (close to 1) for the first bin in the rotation invariant representation, with other bin values substantially 0. A 2-way histogram typically has values around 0.5 for bins1and7(in a12bin histogram, otherwise approximately half-way i.e. opposite bin1). A junction histogram has a pattern to the bin values. Typically the pattern comprises more than 2 substantially non-zero bin values. For example, a four way junction may be represented by a histogram having bin values of substantially 0.25 at 90° intervals, although other arrangements of junction can be envisaged having different intersection angles. In some embodiments more than one category may be provided for different types or angular arrangement of junctions. A clutter histogram represents an area having unstructured or undirected traffic flow, such as a car park and may have non-zero values in all bins, or substantially a majority of bins.

Prior to being used to classify the histogram, such a model is trained using the method700depicted in the flowchart ofFIG.7. In the method, a training set having a plurality of histograms is obtained (step710), each histogram having an associated category. Thus a learning algorithm may train the model to associate an input histogram with the appropriate classification based upon the training set (step720). The associated category is indicative of the histogram being representative of, for example, a 1-way road, a 2-way road, a junction and a clutter location. When trained, the performance of the model may be verified by using a verification set of histograms without associated categories being provided to the model, although the category of each histogram is known for comparison against the category assigned by the model. The model may be re-trained, if necessary, or to introduce additional categories i.e. representative of new junction layouts etc.

FIG.5illustrates classified centroids representing an area in the city of Flanders. The centroids marked510represent exemplary 1-way centroids510. The centroids marked520represent exemplary 2-way centroids. The centroid marked530is an example of an intersection centroid. The centroid marked540is an example of a clutter centroid.

In step140, centroids are connected to adjacent or spatially close centroids based upon one or more characteristics. The characteristics in one embodiment comprise the directional histograms associated with each centroid. Centroids having similar characteristics are connected in step140. The similarity of centroids may be expressed by a metric. The metric may take into account the fact that adjacent bins in the directional histograms are more indicative of similarity than distant bins. For example, that bins such as bin11and bin0(in a12bin histogram) are neighbouring bins, whereas bin0and bin6are opposite. Therefore the metric indicates the angular proximity of bins and similarity between directional histograms. Such a metric is used in the area of written text (character) recognition and has been applied by the present inventor to comparison of rotational histograms in the area of road network analysis. Further details are available in the publicationDistance between histograms of angular measurements and its application to handwritten character similarity, Sung-Hyuk Cha; Srihari, S. N.; 2000 (ISBN: 0-7695-0750-6).

In step150the centroids are compared against digital map data representative of an area for which the trace data was obtained. The map data indicates, amongst other things, the road network in the area. As a result of the comparison any discrepancies or deviations between the map data and the real world may be identified in step160.

Step150comprises, in some embodiments, a first part in which centroids are identified which do not correspond to a location of a road in the map data. In some embodiments, the digital map data is scaled to match a scale of the pixel map in order to enable a comparison between the centroids and the map data. A location of each centroid is then compared against the map data to determine if a road exists at that geographic location. If no road exists at that location, or at a location within a predetermined distance of the centroid, then the centroid is marked or flagged for further analysis. If there is a road at the geographic location of the centroid then the centroid may be discarded, i.e. eliminated from further analysis. In other embodiments, all centroids are marked for further analysis, i.e. including those which correspond to the location of roads in the map data. This allows centroids corresponding to roads in the map data to be further analysed to detect changed road properties, such as a road having changed from 1-way to 2-way.

Marked or flagged centroids are analysed to determine whether they relate to a deviation from the map data i.e. a location at which the map data is potentially incorrect. In the second part of step160the marked centroids are analysed to determine with a greater degree of confidence whether they correspond to such a deviation.

In embodiments of the invention, a marked centroid is determined to correspond to a deviation from the map data based upon its classification and connections.

As explained above, centroids may be classified and the classification of a marked centroid c may be indicated as L. In some embodiments, as noted above, the classifications L may be 1-way, 2-5 way, intersection or clutter, although it will be realised that these are merely exemplary. The connections of the marked centroid c may be identified as {c1. . . ck} with corresponding classifications of {L1. . . Lk}.

A function F may be arranged to output true or false to indicate whether the marked centroid c corresponds to a change from the map data based upon the classification of the marked centroid and its connections as:
F(L,{c1. . . ck},{L1. . . Lk})
For example, a marked centroid having no connections or being connected to only clutter centroids may be rejected. That is, the marked centroid may be determined not to represent a deviation or real-world change from the map data. This determination may be made on the basis that the classification and connections of the marked centroid do not indicate with significant reliability that the real world road network has changed from the map data. However, a marked centroid having a predetermined classification connected to a plurality of centroids of the same classification, e.g. a centroid classified as 1-way connected to four other similarly classified centroids, may be identified as a real-world change. As such the function F outputs true to indicate the determination of the marked centroid as a deviation from the map data. The function may be a heuristic function or be a trained model.

FIG.6illustrates centroids determined to correspond to deviations and not to correspond to deviations. First and second pluralities of centroids610,620are identified to correspond to a change from the map data whereas a third plurality of centroids630(and others not specifically indicated inFIG.6) are identified not to correspond to changes from the map data.

It will be appreciated that embodiments of the present invention assist in detecting deviations of map data and the real world represented by the map data.

It will be appreciated that embodiments of the present invention can be realised in the form of hardware, software or a combination of hardware and software. Any such software may be stored in the form of volatile or non-volatile storage such as, for example, a storage device like a ROM, whether erasable or rewritable or not, or in the form of memory such as, for example, RAM, memory chips, device or integrated circuits or on an optically or magnetically readable medium such as, for example, a CD, DVD, magnetic disk or magnetic tape. It will be appreciated that the storage devices and storage media are embodiments of machine-readable storage that are suitable for storing a program or programs that, when executed, implement embodiments of the present invention. Accordingly, embodiments provide a program comprising code for implementing a system or method as claimed in any preceding claim and a machine readable storage storing such a program. Still further, embodiments of the present invention may be conveyed electronically via any medium such as a communication signal carried over a wired or wireless connection and embodiments suitably encompass the same.

All of the features disclosed in this specification (including any accompanying claims, abstract and drawings), and/or all of the steps of any method or process so disclosed, may be combined in any combination, except combinations where at least some of such features and/or steps are mutually exclusive.

Each feature disclosed in this specification (including any accompanying claims, abstract and drawings), may be replaced by alternative features serving the same, equivalent or similar purpose, unless expressly stated otherwise. Thus, unless expressly stated otherwise, each feature disclosed is one example only of a generic series of equivalent or similar features.

The invention is not restricted to the details of any foregoing embodiments. The invention extends to any novel one, or any novel combination, of the features disclosed in this specification (including any accompanying claims, abstract and drawings), or to any novel one, or any novel combination, of the steps of any method or process so disclosed. The claims should not be construed to cover merely the foregoing embodiments, but also any embodiments which fall within the scope of the claims.