Filter of GPS reciever's errors

without filter

Without filterWithout filter

with filter

With filterWithout filter

Why do you need Mad Location Manager?

Taxi

Are you tired of «extra» kilometers duу to an inaccuracy of GPS-data in taxi applications?

Delivery

Are there regular sharp «jumps» in the Applications for Courier tracking?

On demand

Do you need precise tracking in an on-demand service?

The solution is Mad Location Manager

What are the features of Mad Location Manager?

Route errors

It reduces the errors in route tracking

Static route

It allows making motion of the objects on the map

Zigzag route

It eliminates additional distance when the object is motionless

Smoth route

It decreases the noise from Low-class smartphones

Noise route

It excludes sharp «jumps» to the points remote from a real route

No gps

It filters errors duу to the short-term loss of GPS-signal

In addition, it solves the other tasks related to the delivery and tracking of the objects moving on the map

How does it work?

To implement the system we need data from the following three sensors:

Magnetometer
Magnetometer

Shows where the North is

Accelerometer
Accelerometer

Is used for acceleration measurement and angle determination

Phone blue
Gyroscope
Gyroscope

Allows us to get the current position of the object through the integration of gyroscope readings given the initial object position

The simplest and the most convenient are virtual Android sensors

We have an acceleration vector in the “absolute” coordinate system and we can implement Kalman filter

And dat
Virtual Android sensors

We can use a LINEAR_ACCELERATION sensor for linear accelerations (excluding gravity force) and ROTATION_VECTOR sensor for device orientation

Kalman
Kalman filter

We determine the state vector of the system, the transition matrix, the control vector, and other components of the Kalman filter. Then define the covariance noise matrix of the process and measurement noise. In this form, it is relatively easy to implement the filter

To make the long story short…

Accelerometer
Gyroscope
Magnetometer
And dat
Kalman
Kalman

Filter parameters

Now we have to determine the types of matrixes

System state vector

State-transition model

Control-input mode

Control Vector

Observation model

Perform several operations with matrices

The observation model maps the true state space into the observed space. In our case, it equals to identity matrix as we can get everything from a GPS receiver (speed and coordinates) and don’t need to convert it. If the receiver can’t get information about speed then an observation model changes to this:

pic. 1

The second one shows the better result with a short-term loss of the GPS signal because the state vector is not affected by the last speed received from a receiver.

pic.2 Covariance noise measurement matrix

If a receiver doesn’t provide information about speed. Otherwise:

pic. 3

These values could be received in different ways. You can parse NMEA message and use HDOP value. Also, you can use Location class getAccuracy() method. We should know the direction to get speed to in our coordinate system. For this, we can use either course component from NMEA message or getBearing() method from Location class.

pic. 4 Process noise covariance matrix

Over time the positioning error due to the integration of accelerometer readings will increase. Therefore, we have to take GPS-coordinate as the result instead of accelerometer reading. Dt is the period between 2 update steps (obtaining of GPS-coordinates) in Kalman filter.

To make Kalman filter work, we have to bring all the data to the single coordinate system.

GeoHash

The algorithm for converting two coordinates of the form 42.8795949 (longitude), 74.5998444 (latitude) into one string

In this project, it is used to solve 2 problems. First, it is necessary to somehow merge the nearby points to reduce the flow of redundant information. To do this, you can select a radius and merge all the points that fall into the circle with this radius. But how to choose the radius and center of this circle? Calculating the distance in spherical coordinates is a costly operation, so a GeoHash function is used to “join” fast coordinates. This function produces a hash as a string, the length of which is determined by the user and affects the encoding accuracy. The longer the hash length is, the smaller the region is and the greater accuracy of the coordinates is in one region. The maximum possible length of a GeoHash string is 12 characters. A very good result for our task shows hash with 7 and 8 precision.

Another application of this function

Another way to use this function is “jumps” filtering. We will assume that if the GPS receiver has given out more than 3 (user-defined count) coordinates with one hash, then this point is correct and it should be taken into account. If less — then, probably, this is some random value that does not need to be taken into account.

A route without the implementation of the GeoHash-based filter

A route with GeoHash-based filter. The length of the string (accuracy) is 8. The minimum number of points with one geohash is 2

A route with GeoHash-based filter. The length of the string (accuracy) is 7. The minimum number of points with one geohash is 3

Examples above illustrate that GeoHash filter allows to significantly reduce the number of processing coordinates. It may be crucial if coordinates are planned to be processed by the server or to save the routes in the database.

Result, conclusion and further improvements

As a result, we wrote an Android module and a C library that implements all of the above filters. Visually routes became smoothed and calculation error was reduced.

Red points are GPS coordinate. Blue points — filtered values.

Green line shows GPS data with significant nose. Red one - filtered data (firstly, by Kalman filter, than by filter based on GeoHash)

Without filter

Two algorithms were used to calculate the distance. One of them is the Vincenti algorithm. It is used inside of the distanceBetween() method of the Location class. The second method: https://en.wikipedia.org/wiki/Great-circle_distance (section with the haversine formula). Tests show that the results are almost the same, while the second option requires fewer resources. Yet, there are high chances that at greater distances the error will be greater. Within the city, both algorithms will operate the same way.

Use and develop

The solution if licensed by MIT. Therefore, do not Forget about the copyrights and authorship

© Mad Devs,