Written by Chris Recoskie.
The world is a big place.
One problem that has started to become more and more frequent in today’s “Internet of Things” is that we want to know where exactly in the world our things are. Maybe you’re in the control room of your city’s transit commission and you want to know where all your buses are and whether they’ll reach their next stop on schedule. Maybe you need to provide directions to the nearest restaurant to someone walking down a street using their smart phone to try to find somewhere to eat. Maybe you’re an insurance company and you want to know which of your customers follow the speed limit and which don’t. More and more of our daily lives are becoming increasingly connected, and the natural extension of that is that as things move across the world, we want to know about it and do interesting things with that information.
The interesting commonality between the examples above however is that although we do certainly care about what the object’s raw position is on the Earth’s surface, we care even more about how the object’s location relates to the streets, roads, and highways in our world. Want to estimate when the bus is going to get somewhere? Well you need to know what road it’s on, what the speed limit is, etc. Need directions to somewhere? Well if you’re going to take roads to get there, then you need to know what road you are on, which roads connect to that road, and so on. Need to know if someone speeds a lot? Well then you need to know what road they were driving on so you can relate the vehicle’s speed to the posted speed limit.
Taking a GPS location and determining which road the point is on is called map matching, and this is what the PointMapMatcher operator is for. The following video gives some background.
PointMapMatcher takes in as input information about a network of paths. The network consists of nodes (which are points on the Earth’s surface described by a latitude and longitude), and edges (which are navigable paths between nodes). This network is typically a road network, but it might be anything; waterways, train tracks, hallways at a trade show, etc. As locational data about entities is subsequently input to the PointMapMatcher, it attempts to match those points to the edges on the road network. In other words, assuming that the incoming position data was generated by moving along the edge network, it cleans the data by locking it to the most likely position that is directly on the network.
Along with the PointMapMatcher itself, Streams 4.0.1 provides a composite operator known as OSMPointMapMatcher that is able to read in OpenStreetMap XML map files into the PointMapMatcher and provide matched output corresponding to the contained road map. In the examples shown in this article, this OSMPointMapMatcher is used to plot the data on to a Javascript based map provided by OpenLayers. The green points represent the original points as reported by a smartphone carried inside a vehicle as it drives around on various motorways. In the below screenshot, the red points indicate the points locked to the road network.
The challenge with matching location data to a map, is that our ability to locate objects on the Earth’s surface is imperfect. This can be due to many different factors. GPS devices have only a certain amount of inherent precision to begin with (for consumer devices, the current best you might hope for is 1 metre resolution), but when the GPS satellites overhead are occluded by tall buildings, strong weather, tree cover, etc., that resolution goes down. This means that despite the fact that an entity may have actually been on the road, the data you get may indicate otherwise.
In the example below, the data was recorded on a very rainy, stormy day in an area with a lot of overhead tree cover overhanging the road. You can see that the amount of positional error is relatively high in the wooded area, and once the trees thin out a bit, the error lessens.
Apart from the aforementioned environmental factors, when it comes to mobile devices such as smart phones, the GPS might only have a best-case resolution of 10 metres to begin with, and all those same factors might make it accurate to 20 metres, or 30 metres, or worse. Or, your phone may not have a GPS at all and you may have to rely upon triangulation based on cell phone towers to determine your location.
Sometimes, it’s not always a problem with the reported location. Sometimes the location can be right, but your map is just plain wrong. In the example below, the road actually goes straight (which the GPS data recorded from the vehicle shows), but for some reason the map is incorrect and claims that there is an S bend. It’s no surprise in this case that the reported data doesn’t directly match the map.
All of this can present some significant challenges when matching reported positions to a map, because it is quite frequent that the points do not directly lie on the road. In the following example, there is a divided highway, and the vehicle drove roughly Westbound, but the reported points from the GPS are actually closer in proximity to the Eastbound lanes.
Luckily for us, the PointMapMatcher uses heuristics to determine what the most likely road actually is. When fed with the data from the above example, the PointMapMatcher knows that, based on the history of previously seen points, the vehicle is heading in a direction that generally matches that of the Westbound lanes and generally opposite to that of the Eastbound lanes, so it’s able to tell that the correct thing to do is match the points to the Westbound lanes. Again, in the below screenshot, the red points correspond to the points that the PointMapMatcher has matched to the road network.
Similarly, the PointMapMatcher is able to handle other roads in close proximity in situations like on ramps, and roundabouts.
The PointMapMatcher provides other data besides just the matched latitude and longitude. It can tell you the ID of the edge that it matched (so you can relate the match back to any metadata you might have about the edge, such as speed limit information for a road), the direction of travel along that edge (start point to end point vs. end point to start point), and the distance along the edge relative to the direction of travel that the point lies.
Below you can see an example of the direction of travel information at work. In the example the vehicle drove both directions on the same dead end street. The red points indicate when the vehicle drove from the start point to the end point, and the yellow points indicate when the vehicle drove in the opposite direction. The history of previous points is used to heuristically determine what this direction is.
Example Application Code
So let’s say that you want to write an application that does what the above application does, namely take a map and some data points as input, and plot them on a map. How do you go about it?
Basically what we want to do is read in an OpenStreetMap map for the area we’re interested in, process some incoming entity data with the PointMapMatcher, and plot the resulting points using OpenLayers on the OpenStreetMap map.
Our application graph looks something like this:
For the core part of our application, we use a FileSource operator to read in the CSV file containing the entity data.
(stream<int64 objectId, float64 latitude, float64 longitude, int64 timeStamp>
FileSource_5_out0) as FileSource_5 = FileSource()
{
param
file : getThisToolkitDir() + "/etc/bewdley.csv" ;
format : csv ;
}
This is handed off to a Throttle operator so we can slow the data playback down to the same rate it was recorded at (which is not a requirement, but for our purposes we want to see the data animate as if the vehicle were driving around in real time). The data was recorded at a frequency of one point per second, so the tuple rate on the Throttle operator is set to 1.0 to match that rate.
(stream<int64 objectId, float64 latitude, float64 longitude, int64 timeStamp>
Throttle_32_out0) as Throttle_32 = Throttle(FileSource_5_out0 as inputStream)
{
param
rate : 1.0 ;
}
This data is then sent to the OSMPointMatcher composite operator, which takes care of loading our OpenStreetMap map and does the actual matching.
(stream<int64 matchedEdgeId, float64 latitude, float64 longitude,
float64 distanceOnTrack, boolean directionOfTravel, int64 objectId,
float64 origLatitude, float64 origLongitude> OSMPointMatcher_18_out0) as
OSMPointMatcher_18 = OSMPointMatcher(Throttle_32_out0 as inPort0Alias)
{
param
mapfile : getThisToolkitDir() + "/etc/bewdley.osm" ;
distanceThreshold : 50.0 ;
matchingTimeCutoff : 120000.0 ;
historySize : 5u ;
velocityThreshold : 100.0 ;
}
The distanceThreshold tells operator that we wish to only consider road matches within fifty metres of the original object position. The matchingTimeCutoff indicates the maximum time between successive points (expressed in milliseconds) that is allowed before the point history is disregarded. In our case we are intentionally picking a high threshold so as to not disregard any history. The historySize parameter indicates how large a history of points to use in heuristically determining matches (in our case, five points). The velocityThreshold indicates that if the velocity between successive points is greater than one hundred metres per second, then a point should be disregarded and not matched, because the incoming data would be unrealistic. These values are just examples; in a real application, all of these parameters should be tuned properly to suit your requirements.
In order to display the data on the map, we utilize the MapViewer operator that was highlighted in this article: Visualizing Location Data in Streaming Application. The MapViewer operator uses an embedded Jetty instance to render the incoming points on the OpenStreetMap map using OpenLayers.
() as MapViewer_2 = MapViewer(RedEntities_out0, GreenEntities_out0, YellowEntities_out0)
{
}
Working backwards from the MapViewer, we need to get the data from the OSMPointMatcher into the form we want it in for the MapViewer to display it. We use a Custom operator to do that, which outputs tuples to three different operators… one that makes green points on the map, one that makes yellow points on the map, and one that makes red points on the map. The green points are always sent, as they are the original points recorded from the GPS track, prior to any matching. Red points are sent if the direction of travel is from the start point to the end point of the edge, and yellow points are given if the direction of travel is in the other direction.
(stream<int64 objectId, float64 latitude, float64 longitude> Custom_11_out0 ;
stream<int64 objectId, float64 latitude, float64 longitude> Custom_11_out1 ;
stream<int64 objectId, float64 latitude, float64 longitude> Custom_11_out2)
as Custom_11 = Custom(OSMPointMatcher_18_out0 as inputStream)
{
logic
onTuple inputStream :
{
if(inputStream.directionOfTravel == true)
{
submit({ objectId = inputStream.objectId, latitude =
inputStream.latitude, longitude = inputStream.longitude },
Custom_11_out0) ; // start to end matched points go to red
}
else
{
submit({ objectId = inputStream.objectId, latitude =
inputStream.latitude, longitude = inputStream.longitude },
Custom_11_out2) ; // end to start matched points go to yellow
}
submit({ objectId = inputStream.objectId, latitude = inputStream.origLatitude,
longitude = inputStream.origLongitude }, Custom_11_out1) ; // orig items go to green
}
}
There are three custom operators which in turn handle creating the points of each colour. An interesting thing to note here is that the MapViewer is implemented assuming that it will be displaying only one point per object at a time, so each time it sees a point for an object with a given ID, it erases the old point and draws the new one in its place. Hence, because in our case we want to show the entire history of points for the object (including both the original points and the matched points), we need to trick the MapViewer into thinking that each point it sees is for a new object. Hence, in the code below you will see that each colour of point keeps its own ID counter, which it increments on every tuple submission.
(stream<rstring id, rstring wkt, uint32 updateAction, rstring note,
MARKER_TYPE markerType> RedEntities_out0) as RedEntities = Custom(Custom_11_out0 as inPort0Alias)
{
logic
state :
{
mutable int64 currentId = 100001 ;
}
onTuple inPort0Alias :
{
// convert coordinates to wkt string
mutable rstring wktGeometry = point(longitude, latitude) ;
// submit to MapViewer, set upactionAction to 1 to add point to the map
submit({ id =(rstring) currentId ++, wkt = wktGeometry, updateAction = 1u,
note = "", markerType = RED }, RedEntities_out0) ;
block(0.01) ;
}
}
(stream<rstring id, rstring wkt, uint32 updateAction, rstring note,
MARKER_TYPE markerType> GreenEntities_out0) as GreenEntities = Custom(Custom_11_out1 as inPort0Alias)
{
logic
state :
{
mutable int64 currentId = 1 ;
}
onTuple inPort0Alias :
{
// convert coordinates to wkt string
mutable rstring wktGeometry = point(longitude, latitude) ;
// submit to MapViewer, set upactionAction to 1 to add point to the map
submit({ id =(rstring) currentId ++, wkt = wktGeometry, updateAction = 1u,
note = "", markerType = GREEN }, GreenEntities_out0) ;
block(0.01) ;
}
}
(stream<rstring id, rstring wkt, uint32 updateAction, rstring note,
MARKER_TYPE markerType> YellowEntities_out0) as YellowEntities = Custom(Custom_11_out2 as inPort0Alias)
{
logic
state :
{
mutable int64 currentId = 200001 ;
}
onTuple inPort0Alias :
{
// convert coordinates to wkt string
mutable rstring wktGeometry = point(longitude, latitude) ;
// submit to MapViewer, set upactionAction to 1 to add point to the map
submit({ id =(rstring) currentId ++, wkt = wktGeometry, updateAction = 1u,
note = "", markerType = YELLOW }, YellowEntities_out0) ;
block(0.01) ;
}
}
You can find the example project on GitHub at: PointMapMatcher Sample
Enjoy!
#CloudPakforDataGroup