Location Referencing: OpenLR™

Provide geospatial traffic information in a dynamic way

Photo by Robin Pierre on Unsplash

After having introduced the challenge of location referencing in its general form in a previous post and detailed the case of pre-coded locations too, I will describe this time the more general and modern approach for providing geospatial traffic information. The mobility is by definition a fully dynamic system, so it is natural to think about a dynamic way for providing detailed and updated traffic information. Dynamic Location Referencing (DLR) schema are conceived to be map-agnostic, i.e. the sender of the traffic information and the receiver should not have the same digital map, and any pre-coded location table too, but they have to exchange information between them. There are several types of DLR algorithms, here the most famous ones:

• OpenLR™
• TPEG-Loc
• AGORA-C
• ULR
• GIMME

I will describe the father of all of them: the OpenLR™ methodology. This choice is based not only on historical reasons, but also because such technology is open source and royalty free, allowing its wide usage in industrial sectors.

OpenLR™ is an open source project launched by Tom Tom International B.V. and it is an open standard owned by the OpenLR Association. Everyone may contribute to its further development; the source code repository is here on GitHub and, being a Java library, it can be used in any Java software. But if you need just the docoder capability and you are for example creating a prototype, or validating the decoding itself, you can easier use the python library. For a detailed description of the standard refer to the White Paper provided by the OpenLR™ Association.

Keep in mind that OpenLR™ was designed to be not only map-agnostic, but also communication channel indipendent, and capable to minimize the bandwidth for data communication. This last requirement within the possible differences between the two maps makes the reliability of the location referencing operation not equal to 100%; errors can happen and discovering them may be difficult. Depending on the application sector, the expected minimum quality levels can vary, and in particular defining as quality parameters the Topological Correctness (TP) and the Geometric Accuracy (GA), the minimum expected thesholds are TP > 80% and GA < 50 meters. While the Topological Correctness aims to identify the same path of the two maps in term of direction and equal routing streets sequence, the Geometry Accuracy aims to identify as precisely as possible the exact positions of the locations. If we are working with an informative system it is expected to have TP > 90% and GA < 20 m; while working with warning applications TP > 95% and GA <10 m; and finally for control applications the expected accuracies are TP > 99% and GA < 5 m. Another quality criteria used to judge the location referencing is the capability of the decoder to correctly identify impossible matchings; this situation can happen for example when there is a strong difference between the two maps such that some streets are totally missing into one of the two maps, or when the representation of the physical network is too much different like it happens for roundabouts and complex intersections. Anyhow a critical point of such DLR operations is the automatic assessment of the quality of the results, and the above mentioned thresholds are verified by manual inspection. It is clear that such an approach is unfeasible to follow for realtime systems where potentially there is a continous stream of data to be referenced via the DLR methodology.

Basic idea

Let’s introduce now some concepts that are useful for high level understanding.

OpenLR™ describes a method and a format for encoding, transmitting and decoding (map-independent) references of locations. Locations are objects in a digital map, like points, paths and areas. The method makes it possible to encode a location in a map, send it to a system having another (possibly different) map and find the location back in this receiving map. The format to transmit such location reference is compact so that it can be used in systems having bandwidth restrictions. OpenLR™ can handle locations which are bound to the road network but also locations which can be everywhere on earth. The main idea of OpenLR™ is to describe a location with an ordered set of location reference points (LRPs). This set of LRPs uniquely identifies the location in a digital map and is called the location reference. Every single LRP specifies a position or a line in a digital map.

The main idea for locations which are bound to the road network is covering the location with a concatenation of (several) shortest-paths. The concatenation of such shortest-paths shall cover the location completely. Each shortest-path is specified by information about its start line and its end line. This information is combined in the location reference points (LRPs). The LRPs are ordered from the start of the location to the end of the location and the shortest-path between two subsequent LRPs covers a part of the location. The concatenation of all these shortest-paths covers the location completely and this path is called the location reference path. The location reference path may be longer than the original location and offsets trim this path down to the size of the location path.

The role of the OpenLR™ encoder is to determine the number and the positions of the location reference points to describe the location uniquely. The role of the OpenLR™ decoder is to resolve the received location reference points to a location in its own map.

The physical format for transmitting location references is also described in the OpenLR™ standard. A binary format (encoded in Base64) is compact and can be used for the transmission of location reference data where the data size is important to be small. An XML format can be used if the need of having a compact format is less important and the existing environment for data transmission may already be based on XML.

Location Types

OpenLR™ supports several types of locations:

• Line
• Geo-Coordinate
• Point-Along-Line
• Poi-With-Access-Point
• Circle
• Rectangle
• Grid
• Polygon
• Closed-Line

I will mainly describe the most used and common one, i.e. the Line Location. But in the following picture you can see a sketch of all of them.

Requirements

The digital map used for encoding and decoding and the location itself must fulfill some requirements in order to guarantee acceptable results for the OpenLR™ method.

For the map we have the following requirements:

• Coordinates must be in WGS84 reference system
• Coordinate accuracy should have at least 5 decimal digits for a degree
• Lengths must be in meters
• Lines should have a real geometry
• Every line should have a Functional Road Class (FRC) value indicating its importance in the network
• Every line should have a Form Of Way (FOW) value indicating its physical properties

Keep in mind that at least two out of three information of the map must be available among: geometry, FRC and FOW, with the geometry more important than the FRC which is more important of the FOW in granting a better decoding.

For what concern the requirements of the locations, I will focus only on the Line one, for which is asked:

• Line locations must be connected
• A line location is represented by an ordered list of line elements
• Offesets are positive values and their sum must be at most equal to the total length of the location

Logical Data Format

For conceptually understanding the OpenLR™ locations, I will describe the logical data format, having in mind that OpenLR™ uses as lego brick what it calls the “Location Reference Point” (LRP). A LRP determines a position in a digital map thanks to some building blocks which are used to compose the LRP itself; here a description of such building blocks:

• COORD: a Coordinate pair of longitude and latitude
• FRC: the Functional Road Class of a line based on the importance of the road it represents. OpenLR™ defines the following 8 values (therefore it is important in the decoding application to properly map these values to those of your map)

• FOW: the Form Of Way describes the physical road type of a line. As for the FRC it is important to have a proper mapping between the values defined by OpenLR™ and listed in the table below, and the value identified in our map.

• BEAR: the Bearing describes the angle between the true North and a line which is defined by the coordinate of the LRP and the coordinate of a point which is BEARDIST along the line defined by the LRP. If the line length is less than BEARDIST the opposite point of the line is used. The bearing is a positive number expressed in degree, clockwise from North.

The BEAR is the green angle measured clockwise with respect to North, between the North direction (dashed red line) and the vector (red arrow) from the LRP and the point along the line at a distance from LRP equal to BEARDIST (highlighted red arc)

• DNP: the Distance to Next Point field describes the distance to the next LRP in the topological connection of the LRPs. The distance is measured in meters and is calculated along the location reference path between two subsequent LR-points. The last LRP has the distance value 0.
• LFRCNP: the Lowest FRC to the Next Point is the lowest FRC value which appears in the location reference path between two consecutive LR-points.
• POFF: the Positive Offset is the difference of the start point of the location and the start point of the desired location along the location reference path. The value is measured in meters. (It is optional)
• NOFF: the Negative Offset is the difference of the end point of the desired location and the end point of the location reference path. (It is optional)

All such attributes create a LRP, and if it is bound to the road network all attributes are linked to this LR-point. For all LR-points (except the last LR-point) the attributes describe an outgoing line of the node at the LR-point coordinate which belongs to the location. The attributes of the last LR-point direct to an incoming line of the node at the LR-point coordinate which belongs to the location.

For the case of Line Location, we are focusing on, there are three different types of location reference points. The “First LRP” describes the start line of the line location. The “Last LRP” refers to the end line of the location. Both types are mandatory for a line location. An “Intermediate LRP” is added to the list of location reference points if the encoder decides to mark additional lines along the location path. These additional LRPs act as a guide for the decoder to reconstruct the location.

Line Location defined as a sequence of LRPs. POFF and NOFF are optional and used to improve the precision.

OpenLR™ defines also some rules for having properly defined locations, like:

• The maximum distance between two cinsecutive LRPs is 15 Km
• Road length values are reported as integer values
• LRPs shall preferably be placed on valid network nodes
• Offsets must refer to the first two (last two) LRPs

Line Location Encoding/Decoding

I would like now to close the post giving you a feeling of the operations performed to encode a line location and to decode it.

Encoding

Given a line location on the encoding map, i.e. a sequence of connected links on the map of the encoder, the idea to create a proper OpenLR encoding is to apply a shortest path search between the first valid node and the last one (making sure that all the rules previously mentioned are fulfilled). If the resulting path cover exactly all the links of the given location, the procedure stops and creates LRPs packaged into the proper physiscal format (binary or XML). But if the shortest path deviates from the given location, the first deviation point is identified, a new intermediate LRP is created and a new shortest path is done. Such procedure is recursively repeated until the location is fully covered by the shortest paths.

Decoding

Given an encoded OpenLR location, the decoders first of all identifies the nodes of the decoding map which best match the LRPs of the encoded location from a geographical point of view. To each LRP can be associated more than one nodes. After such operation, the decoder selects for each encoded LRP the best link of the decoding map associated to the previously identified nodes on the basis of a scoring function that takes into account both the properties of the LRP and the ones of the decoding map. Once the links are found, for each couple of subsequent links a shortest path is performed and all the results are properly chained providing the decoded location.

As you can imagine from the rough description of the encoding and decoding processes the probability to have a perfect match between the location described on the encoding map and the location identified on the decoding map is not one. The map differences and the fact of using a ranking criteria that can fail, make impossible to have a perfect match, even when the map is the same! The objective of the decoding application is to find a set of parameters of the decoding procedure that maximize the good matches, but here there is the highest cost in setup such process because doing the evaluation manually is unfeasible and an automatic procedure must be used. Anyhow the benefits of using a Dynamic Location Reference system are big compared to the drawbacks just highlighted; it is important only to be aware of the limitations of the methodology and to do not ask for 100% accuracy.