Map matching and industrial GPS raw data processing / Bright Box Blog

svva April 24, 2018 at 16:43

Map matching and industrial GPS raw data processing

Any measuring device, whether analog or digital, shows the result with a certain error and noise. The error of the GPS sensor is determined by the error of the sensor itself and such factors as: landscape, speed, number and position of satellites.

In our application, we provide the user with the opportunity to view in detail the routes of his trips. And if you display raw, unfiltered data, it turns out that the route passes not along the road, but through buildings or by water, some points of the route are far removed from neighboring ones or even pieces of the route are missing.

I think it’s no secret to anyone that there are solutions on the market that provide Map matching service. It performs coordinate processing and, as a result, produces coordinates attached to the road. However, no service will understand the specifics of your data, and the result of processing raw data may not be the best. In this regard, we developed a solution that made it possible to filter and superimpose data from sensors on roads.

Input data

At the beginning of development, the OBD dongle was transmitting telematics data to the server in the form of points, each of which had the following parameters:

Coordinates received from GPS sensor;
Speed received from the car;
Engine turns received from the car;
The time of a particular point.

Points were transmitted according to the following algorithm - once every 3 seconds or every 20 meters. Note that the transfer algorithm is not ideal, but within the framework of a specific problem, we decided not to change it, because it is obvious that if you transfer points using a more advanced algorithm, then the result will only improve. The dongle also collected data such as: heading (motion vector) and dilution of precision (roughly speaking, GPS accuracy), but this data was not transmitted to the server.

Algorithm

The algorithm that we used can be divided into two parts:

Data filtering;
Map matching;
Partial processing.

Filtration

No one knows the specifics of your data better than yourself. We decided to use our knowledge and do data filtering on the side of our own service. Let's look at a simple example of a route:

The graph shows the speed of the car received by the dongle from the car, and the speed calculated from GPS. As you can see, there are a lot of outliers on the graph - both up and down. Standard filtering algorithms immediately come to mind: Kalman filter, alpha-beta filter. We took up them first. However, such filters have not shown their best side. There were several reasons for this: the low frequency and absolute heterogeneity of the data (it is difficult to choose a single modified algorithm with a suitable error), the presence of transformations of the incoming data was unacceptable. A much simpler linear filter of speed showed itself much better during testing. The essence of the algorithm is very simple: for all neighboring points, we calculate the GPS speed and compare it with the speed received from the car, and if the differences are higher than the permissible error,

Here is the pseudo code:

`for i in range (1, len (data)):
   velocity_gps = calc_dist (data [i - 1] .lat, data [i - 1] .lon, data [i] .lat, data [i] .lon) / (data [i] - data [i - 1])
   velocity_vehicle = (data [i - 1] .speed + data [i] .speed) / 2
   relative_error = abs (velocity_gps - velocity_vehicle) / (velocity_vehicle)
   if relative_error> 1.5:
      data.remove (data [i]) `

As a result of filtering, we obtain data without emissions, while the points still do not lie on the road. However, before the Map matching procedure, we should also thin out our data, since it makes no sense to transfer 10 points lying on one straight line, when two points are enough to determine the straight line. Nevertheless, one should not be too careful with filtering, because the Map matching service can consider our data noise. To remove excess points, we used the Ramer-Douglas-Peucker algorithm, or rather, its slightly modified version.

For a time-ordered pack of points, we calculate the distance for all points to the arc connecting the first and last points of the pack. If the distance from each point is less than a certain value of E, then we return only the starting and ending points of the packet. Otherwise, we divide the pack into two, the division occurs at a point as far as possible from the arc, and then repeat the procedure.

Map matching

Due to the fact that the maps for our mobile applications and portals are provided by the Mapbox service, it was decided to use their Map matching service. But we immediately faced a limitation of 100 points in the request. Even taking into account filtering and reducing the number of points by the RDP algorithm, the average number on our routes is 250 points. Accordingly, we need to process with batch (batch), plus everything lapped, because in some cases, processing errors will occur with simple batching. The batching algorithm is as follows:

N is the number of points for overlapping processing;
Cut the route into batches with a size of not more than 100-N;

Then we process the first batch;
We take the last N points of processed data and the second batch;
Continue to the last batch;

The final result consists of Processed1, Processed2, Processed3, Processed4.

The next problem we encountered was determining the accuracy of the data. The Mapbox API requires you to specify the accuracy of the transmitted data, although this parameter is specified as optional in the document. And if you don’t pass it, it will be set from the default value. The parameter responsible for accuracy is gps_precision. Here's what the documentation says about it:

An integer in meters indicating the assumed precision of the used tracking device. Use higher numbers (5-10) for noisy traces and lower numbers (1-3) for clean traces. The default value is 4.

However, we did not transmit this data from the dongle at the time of developing the service. Due to the rare frequency of data, it was not possible to use noise level determination algorithms. Thus, we processed a certain number of routes and tried to find the most suitable parameters. But how to choose the best parameter for 1000 routes? Manually doing this is impractical. It turned out that this process can be automated due to the specifics of the results with an unsuccessfully selected parameter. If you select a parameter value that is too low, pieces of the route may disappear, and if you overestimate the parameter, extra loops will appear.

To identify such cases, the DTW algorithm is well suited . As a result of processing 1000 routes and comparing the results using the DTW algorithm, it became clear that the best results are obtained with precision values of 3, 6, 10 (in different cases).
As a result, in the absence of GPS data on accuracy, we started processing in parallel with three different gps_precision (3,6,10), and then chose the best one. It was also planned to add sending a dilution parameter from the dongle, which would greatly improve the quality of the service.

Partial processing

End points of routes are often in places where the road is not indicated on the map (parking lots, paths between houses, etc.). Map matching algorithms in such situations do not work very well, and I would like to indicate as accurately as possible where the user left his car. To solve this problem, we began to produce a cycle of processing not the entire route, but only internal points: we discard the beginning and end of the route, then we add the beginning and end of the original route to the processed data. The beginning and the end are defined as follows: we take 5% of the route or part before the speed of the car becomes more than 10 km / h.

Final result

In the end, I would like to demonstrate the result of route processing. As a result, the routes pass almost everywhere along the roads, loud noises disappeared, the missing pieces of the routes were restored (riding on a ring or bridge).