Field of the Invention

The present invention is concerned primarily with a method of improving the quality of a location reference, such being a means of representing a point, line, path or space in the real world and capable of being decoded against a digital map in order that the location can be identified.

As a l luded to a bove, the term "location" as used herei nafter is to considered as encompassing a variety of different physical, real-world features such as a point location on the surface of the earth, a continuous path or route, or a contiguous chain of such, of navigable thoroughfares existing on earth, or an area or region on earth capable of being defined by two (in the case of a rectangular, square or circular area), or more parameters. More succinctly, a location is a simple or compound geographical object. However, this invention is most applicable to an efficient, machine-readable representation of a path through a network of roads or other navigable thoroughfares, or a particular position along a path through the network of roads or other navigable thoroughfares, represented by a digital map.

Background to the Invention

Geocoding is a known technique whereby a human referencing system for physical locations, such as a street address, country and/or postcode is converted into associated geographic coordinates, e.g. latitude and longitude. Various different geocoding systems currently exist and rely, at least to some extent, on a geographic information system (GIS) in which the street network is already mapped within the geographic coordinate space. Reverse geocoding is the inverse process.

Any modern digital map (or mathematical graph, as they are sometimes known) can be considered as a GIS, and in a most simple form is effectively a database consisting of a plurality of tables defining firstly nodes (which can be considered as points or zero- dimensional objects) most commonly representative of road intersections, and secondly lines between those nodes representing the roads between those intersections. In more detailed digital maps, lines may be divided into segments defined by a start node and end node, which may be the same in the case of a segment of zero length or a looped segment (in which case the segment has a non-zero length), but are more commonly separate. Nodes may be considered real or "valid" when they represent a road intersection at which a minimum of 3 lines or segments intersect, whereas "artificial" or "avoidable" nodes are those which are provided as anchors for segments not being defined at one or both ends by a real node. These artificial nodes are useful in digital maps to provide, among other things, shape information for a particular stretch of road.

In this manner, nodes, lines and segments can be used as a means of completely describing a road network, and each element in the database is further defined by various attributes which are again represented by data in the tables of the database, e.g. each node will typically have latitude and longitude attributes to define its real-world position. The complete "graph" of the road network is described by thousands or millions of nodes and segments to cover an area of spanning one or more countries, or part thereof.

Although practically all modern digital maps involve a structured definition of nodes and segments, the actual manner in which this is effected between digital map providers varies enormously. For instance, each map vendor (and possibly each map version) may use unique I Ds for each map element, whether node or segment. Therefore, even simple geocoding and reverse geocoding is possible only with some knowledge of the underlying structure of the database in which the requisite digital map is embodied. More simply, a query designed to extract a street address from one digital map database based on latitude and longitude will not necessarily work on another - it may need re-casting as appropriate for the particular digital map database in question. This can also be true for different versions of a digital map provided by the same vendor.

One particular attribute often included in digital map databases is a Traffic Message Channel (TMC) location table reference. TMC is a technology for delivering traffic and travel information to vehicle users, and more particularly to navigation systems (either portable or integrated) present within those vehicles and which include some form of digital map. A TMC message consists of an event code (which need not be traffic-specific, although these are most common) and a location code, often consisting of an ordered list of location references by mea ns of which the location of the traffic event can be determined in the digital map and thus represented graphically on the screen of the navigation system or considered for dynamic rerouting around traffic incidents. A number of pre-defined nodes in the digital map are assigned a TMC location reference which is determined with reference to a limited location table. The location table consists of 2 ¹⁶ (65536) location references corresponding to a similar number of physical or real world locations, usually road intersections, also identifiable in the digital map.

A fundamental limitation of TMC is that only a fixed number of location references are available, and therefore typically only motorways and major highways (or intersections thereon) in each country offering TMC can be referenced. As it is becoming possible to identify traffic build up on secondary and urban roads using GSM and GPS probe data (e.g. vehicles users increasingly possess either a mobile phone or a connected satellite navigation devices useful as probes), a more expansive referencing system is required.

One attempt to overcome some of the drawbacks of TMC location references or map- specific references is the Dynamic Location Referencing project, also known as AGORA-C

(published in 2008 as ISO 17572-1 and -3). Although a complete description of the AGORA-

C location referencing approach is beyond the scope of this application, the fundamentals of the approach are that a location reference can be completely specified by a set of location points, specified by coordinate pairs of latitude and longitude and ordered in a list, each point complying with various rules but most importantly being consecutive in terms of the location being referenced and the previous point in the list, i.e. successive points form a next-point-relationship. As with other location referencing systems, each point is provided with a number of attributes which assist in better defining that point, but specific to the AGORA-C method is the identification of each point as one of a location point, an intersection point, a routing point, or some combination of these three. Each point along the location at which the road section signature changes is represented by an intersection point, so locations being paths over a road network and which pass through intersections without any road section signature change need not be referenced by an intersection point. For example, if a location includes a section of motorway which includes junctions that are not relevant as far as the location is concerned, then there is no need to include intersection points for such junctions.

As may be understood by those skilled in the art, the AGORA-C location referencing method does require an underlying digital map, but the overriding aim of AGORA-C in general is that a location reference specified and encoded against a first underlying digital map should be capable of being decoded and identified successfully on a second, different digital map, regardless of whether this second map is merely a different version of an essentially similar digital map, or an entirely different digital map produced by a different digital map vendor. In this regard, AGORA-C is considered to be, at least to a certain extent, map-agnostic.

Within the field of modern location referencing, techniques other than simple TMC and complex AGORA-C a re bei ng proposed . Although AGORA-C has been standardised internationally, and is anticipated to be adopted by public authorities and governmental organizations as their preferred method of specifying locations within road networks, it is not considered to be a particularly efficient location referencing technique in terms of the number of data bytes required to completely specify a location, and indeed it is prone to inaccuracies. Other leading digital ma p vendors, such as Navteq I nc., a nd leadi ng navigation device manufacturers, such as TomTom International BV, may have have developed or may be developing and implementing alterative location referencing techniques. The TomTom location referencing technique is made available as an open standard known as OpenLR™. Nevertheless, as these companies obtain map content and map-specific data (e.g. traffic information) from public authorities, and furthermore deliver time- and location-specific content to devices, inevitably some conversion between location referencing formats may be required. It is at this point that the quality of the location reference, i.e. how accurately the original physical location as identified on a first "encoder-side" digital map is reconstructed on a second "decoder-side" digital map after decoding the location reference, becomes important.

Such accuracy may be a persistent factor regardless of whether an AGORA-C location reference is used, or whether another standard or proprietary technique is used, because all such techniques do depend to a certain extent on the underlying digital map used in the encoding process, and to what extent the decoder-side digital map is different. To illustrate this point, any location referencing technique should be capable of decoding the reference so as to identify exactly the same physical location as that originally encoded when an identical digital map is used in the encoder and decoder. The simplest form of a location reference is a simple complete list of nodes (i.e. every node along the path of the location) specified by unique IDs. In this case, and as both encoder-side and decoder-side digital maps are identical and contain all the same nodes and segments, the location cannot be imprecisely recreated. However, the very fact that a digita l ma p ca n only eve r be representative of an ever-changing road network at a specific point in time renders them perennially out of date and prone to error, and of course where two different digital maps are used, nodes present in one digital map may not be present in another, and vice-versa. The same may be true for road segments. In the latter case, even when a location is completely specified by all the relevant nodes present in the encoder-side digital map, there are decoding difficulties when a location reference point has no corresponding node in the decoder-side digital map.

Therefore, although simple conversion of location references from one type to another has been proposed, systematic errors may be introduced into the locations and their references with each conversion, particularly if different digital maps or map versions are used in the repeated decoding/encoding processes. Indeed, this problem may exist in merely decoding a location reference against one particular digital map, and then re- encoding the derived location against the same digital map and using the same location referencing technique, when the digital map used in the original encoding process was different. It is therefore an object of this invention to provide a method of converting between location references without significant loss of quality, or i n a particular embodiment, improving or at least maintaining the quality of locations encoded and/or decoded using a particular location referencing technique. It is a further object of the invention to mitigate the reduction in quality of location references arising from systematic encoding/decoding errors across multiple different digital maps or versions thereof.

Summary of the Invention

According to the present invention, there is provided a method of decoding a location reference, such having been originally encoded using a first location referencing technique in which a first underlying digital map was used, characterised in that the method includes the steps of i. decoding the location reference using at least one of the first and a second digital map to successfully resolve a first location, ii. decoding the location reference using at least one further digital map not being the first or second digital map to successfully resolve at least one further, second location iii. comparing said first and second locations for identity, and in the event they are not identical but have a similarity greater than or equal to an arbitrary similarity threshold, iv. combining the first and second locations using an averaging technique resulting in a third location, and re-encoding said third location using the first or other location referencing technique and any of the first, second or further digital maps.

Preferably, at least one of the first and other location referencing technique is AGORA-C.

Preferably, both the first and other location referencing techniques are AGORA-C.

Preferably, at least one of the first and other location referencing technique is the OpenLR™ location referencing technique. Most preferably, the first location referencing technique is AGORA-C, and the method uses the OpenLR™ location referencing technique such that the method acts as a conversion between the two location referencing techniques and results in a location reference which is improved as compared to the original location reference, in terms of accuracy and reliability.

Further preferably, the method includes a further step of including a quality indicator, based primarily on the degree to which the first and second locations are similar, as part of the location reference which results from the re-encoding of the third location.

In a most preferred embodiment, in the event that:

- one of the first location and second location cannot be successfully resolved, or

- the first and second locations are successfully resolved but are not sufficiently similar, the method includes the further step of selecting that one of the first and second locations for re-encoding, being that one which has been successfully resolved or which has the greatest chance of representing the correct location in terms of the digital map most likely to be used by the ultimate recipient of the re-encoded location reference.

In a further preferred embodiment, the first location reference may be encoded using the low resolution TMC location referencing technique, and the subsequent re-encoding may involve one of the greater resolution location referencing techniques. I n such case, particularly as TMC codes may be differently applied in different digital maps and by different digital map vendors, the present invention provides a useful means of improving the accuracy thereof. In the event that TMC codes are not present in one of the first and second digital maps, then the process may act as a useful means of conversion between between basic TMC location references and one of the more complex location referencing techniques.

In a preferred embodiment, the third location, resulting from the averaging of the first and second locations in accordance with the invention, may additionally be compared against the first, second and/or further digital maps to improve consistency and/or accuracy thereof prior to re-encoding. Furthermore, the resulting re-encoded third location may fed back into the method to yet further improve accuracy, and/or to check the reliability of the method.

Most preferably, the method is implemented as a web service, or integrated within a larger computer program application. Moreover, the present invention is to be considered as covering the implementation of the method in a computer operating under the control of a com puter progra m by which the method steps a re effected. A recording medi um embodying such computer program is also to be considered as covered hereby.

Accordingly, the present invention provides a means of improving the quality of location references, and additionally a means of converting between different location referencing types reliably and accurately. Furthermore, given the flexibility of the invention as regards different location reference types, location-specific content (e.g. traffic event broadcasts, interruptions in or changes to road and other communication links, weather information etc.) from a wide variety of providers, whether from or to the public or private sectors, can be reliably and accurately distributed. The invention also has the advantage that a location referenci ng technique may be chosen for i nformation distribution which is more economical than AGORA-C in terms of use of bandwidth, processing power, efficiency for particular types of maps and in terms of technology license costs, and in this case, not only are distributed location references more capable of being reliably decoded, but the requirement for already congested wireless bandwidth can be reduced.

A further advantage of the invention is the facility for private companies, such as applicant herefor, to receive location-specific content from public authorities and private sector entities alike, and to quickly convert the location references used for such content to a different location referencing standard or their own, proprietary solution. The invention is especially advantageous to Applicant herefor as a producer and vendor of digital maps, because of the variety of digital maps and/or versions thereof available. Indeed, it is considered that the invention need not be limited to the use of only 2 or three digital maps or versions thereof during the conversion process. A plurality of decoding steps may occur to result in first, second and further locations, all of which may then be compared and combined before being re-encoded such that the resulting location reference has the greatest chance of being accurately and reliably encoded on most if not all of the digital maps currently and previously produced by the entity performing the conversion. In the case of Applicant herefor, whose maps are in use in many tens if not hundreds of millions of devices around the world, the invention may be of particular benefit. Furthermore, although not its primary aim, the invention allows for selective delivery of location referenced content depending on target platform, in particular the digital map in use therein.

In the case where location-specific content is ultimately to be distributed to users or devices not in possession of a digital map of the same type or version as that offered by the entity performing the conversion or the optimization of the original location reference, then in any event there is a stronger likelihood of successful decoding, particularly if the third party digital map is one of those used during the optimization process of comparison of multiple locations and their combination and/or averaging.

Other features and advantages of the invention are described hereinafter and additionally in the claims appended hereto.

Brief Description of the Drawing(s)

Figure 1 provides a schematic illustration of the process according to the present invention, and Figure 2 provides a schematic illustration of a modified embodiment of the process of the present invention.

Detailed Description of the Invention. Referring to Figure 1, there is shown a schematic flowchart, indicated generally at 100, illustrating one embodiment of the invention in which a location reference LocRefl at 102, being any one of a number of modern location references such as AGORA-C, OpenLR™ or other third party location reference, is received at a decoder 104. It is to be mentioned that the location reference 102 may be merely part of a larger information broadcast or feed and is merely a means of providing a generally map-agnostic definition of a location which is ultimately representative of a real-world point, space or route - the additional information, for example being an event, situation or circumstance prevailing at, along or within said location, e.g. traffic congestion, weather conditions, road closures or restrictions, may additionally be encoded in the transmission. This invention is however concerned merely with the resolution of the location reference itself. Additionally, the invention is not concerned with the means of transmission of the information, and indeed this may be achieved by any of a number of known techniques, e.g. wirelessly over Wi-Fi, WLAN, or any of the known mobile telecommunications standards or other wired or wireless means of digital delivery (e.g. digital broadcast, internet).

Regardless of how the information is received, and of course it is to be borne in mind that the present invention relates to a means of improving location references in general and therefore decoder 104 may typically be implemented as pa rt of a la rger bul k data processing routine, it is necessary for said decoder 104 to refer to at least two different digital maps MAPI, MAP2 indicated 106, 108, although it is possible third and further digital maps (not shown) may additionally be used. The digital maps 106, 108 may be entirely different in that they originate from different map vendors, or they may be different versions of one map produced by a single map vendor, but in any event, decoder 104 attempts resolution of the location reference 102 using both maps separately, and therefore two results, LOCATIONl 110, LOCATION2 112 inevitably arise, notwithstanding that one such result, or possibly both, may be a resolution failure indication.

Regardless of the results, both LOCATIONl and LOCATION2 are received in a further processing module 114 whose operation is dependent to a certain extent on the contents of each of LOCATIONl and LOCATION2. In the event that both LOCATIONl and LOCATION2 are successfully resolved but different locations in that they do not represent a unique location in the real world, and for such determination, module 114 may also have reference to MAPI and MAP2 or indeed some other reference map (not shown), then the module performs an averaging or other suitable adjustment technique on both received locations which results in a third location LOCATION3 116 which is considered to be improved as regards the two resolved location on which it is based.

As part of the averaging technique performed by module 114, in embodiments, there may additionally be included some measure of quality O applicable to the resulting location LOCATION3. Such measure may be based on a number of different possible factors, including the extent to which LOCATIONl and LOCATION2 are similar, how simple those locations are (e.g. a simple point location, or a short stretch of motorway without junctions would be considered relatively simple) and thus how likely it is that they are capable of being successfully decoded regardless of the digital map used during that decoding.

I n a further em bodiment, it is possible that module 114 a lso includes a preference indicator PrefMAP, which depends at least to a certain extent on the relative success of the resolutions of LOCATIONl and/or LOCATION2. For example, most modern location referencing techniques include, as part of their data specifications, a number of variables by which the relative accuracy of the location might be determined. It is considered that such might be used to determine a preference indicator indicative of either which of MAPI and MAP2 would be more suitable for decoding any subsequently encoded representation of the combined location LOCATION3. Alternatively, in the event that either of LOCATIONl and LOCATION2 merely provide an indication of failure as regards resolution of LocRefl against MAPI or MAP2 respectively, then such preference indicator would naturally indicate which of the two maps was used to achieve successful resolution, or possibly an indication of the digital map vendor who produced the particular map useful for successful resolution of the original location reference LocRefl.

As can be appreciated from the above, the module 114 may have a variety of different functions, but in essence, its primary function is one of comparison of the received data comprised in LOCATIONl and LOCATION2, and then of performing a further operation being one or more of averaging two locations to provide an improved location in LOCATION3, measuring and/or calculating a quality or map preference and applying the result as a qualifier as part of or as an adjunct to the location LOCATION3, and of course possibly returning a FAIL indication 118 in the event that the originally encoded location cannot be resolved against either MAPI or MAP2.

As a final step in the process according to the invention, LOCATION3 is delivered to a location referencing encoder engine 120, which attempts to re-encode the location represented by LOCATION3 using either of MAPI and MAP2, or possibly a third (not shown) map, and according to one of any of the known or available location referencing techniques. It is worth mentioning that the technique used in encoder 120 need not be the same as that used in decoder 104, depending on the desired ultimate purpose for the location so encoded. For exa mple, in the context of part of the present Applicant's business, Governmental and Public Authority data regarding the condition of parts of the road network may be received encoded using the AGORA-C technique, but the ultimate destination for such information may be Personal Navigations Devices (PNDs) of the type sold by TomTom International BV and within which digital maps produced by Applicant are commonly installed. In such case, the desired location referencing technique may be that promoted by TomTom, i.e. OpenLR™. Regardless of the technique used, the result is an encoded location reference LocRef2, indicated at 124.

It is to be understood that although LocRef2 is considered as improved compared to the original LocRefl, it is possible that LocRefl and LocRef2 may usefully coexist and be used comparatively or in conjunction in certain applications, and it is not necessary to discard LocRefl after LocRef2 is produced. In the case where LocRefl 102 is in the form of a simple TMC code or collection of such codes, the method of the invention is capable of acting as a means of converting such simple codes into more precise location references using more modern, and higher resolution techniques in the re-encoding step 120 as previously mentioned. Nevertheless, the principles of the invention regarding averaging, or in the case that either of MAPI 106 and MAP2 108 do not contain TMC codes, then the PrefMAP indicator might usefully indicate which of those digital maps includes such codes. Referring briefly to Figure 2 which illustrates essentially the same process as that in Figure 1, it is to be noted that digital maps MAPI 210 and MAP2 212 may be referred to by either or both of the averaging module 214 (as shown at 202, 206) and the resulting location LOCATION3 216 (as shown at 204, 208). In particular, the check of LOCATION3 216 against MAPI 210 and MAP2 212 provide an additional consistency check that such location is real and referenceable against these two digital maps.

Of course, the invention has application in a wide variety of different environments. For example, with a road network infrastructure, certain countries employ are considering employing Direct Short Range Communication (DSRC) roadside equipment for transmitting and receiving location-specific information. The decoding/re-encoding technique might usefully be used in such equipment, particularly where in-vehicle equipment from which information is transmitted uses a different standard or proprietary location referencing technique. The delivery of information from the road network infrastructure or public authorities in general might also usefully be transmitted to vehicle device through such equipment.

The method of the invention may usefully be implemented as a web service, for instance on a computer server accessible over the internet. In such embodiments, the encoded LocRefl may be transmitted from a remote terminal or device, processed by the web service executing on the server, and then the resulting LocRef2 may be returned to the said remote device. The method might also usefully be implemented as part of a larger service application, in a general computer program.

Additionally, broadcasters of road network information using radio or other wireless technologies might usefully employ the invention to deliver more accurate location- specific information. If data with AGORA-C encoded location references are broadcasted, currently only devices that possess an AGORA-C decoder would be capable of decoding such data. To provide the user community at large with data, an industrial converter is required, but in order for successful deliver, some quality control or validation if the conversion process is required, and in this regard, the present invention provides a useful solution. Effectively, location-specific can now be delivered at a higher quality and accuracy than was formerly available through basic AGORA-C alone.

Additionally if an open source location reference technique such as OpenLR™ is used, such being continually enhanced on the basis of new experiences with new implementations and requirements, then consequently different implementations and/or versions are likely to become available in the marketplace. The present invention can easily be adapted to use differrent versions of the location referencing technique . It is also possible that either of the decoder 104 and encoder 120 might employ slightly different versions of any desired location referencing technique. For instance, while use of the fully specified AGORA-C technique may be preferred, there are some assumptions, reductions or perhaps different interpretations of the completely specified standard, readily identifiable by those skilled in the art, which can be made to reduce the processing steps involved in either decoding or encoding, and therefore speed up these processes. Accordingly, either or both of encoder 104 and decoder 124 may employ and location referencing technique, whether completely or partially, as desired. In a most preferred embodiment, LocRefl 102 may be delivered to different and separate decoders (not shown) employing differrent versions of the same location referencing technique, and which both produce, depending on the number of digital maps against which decoding is performed, at least two pairs of locations. All of these locations might then be subsequently be delivered to the averaging module for further processing and analysis.

A further useful implementation of the present invention might involve statistical analysis of a large number of location referenced encoded messages, e.g. AGORA-C messages generated in vehicle to vehicle safety systems might be compared with messages in other formats for identity, and statistically significant messages may then be converted to another format. The on-the-fly validation of newly encoded messages is here extremely important as such systems could be used in systems that interact with the driving task and thus affect road safety.