# Filter of GPS reciever's errors without filter   with filter  ## Why do you need Mad Location Manager? Are you tired of «extra» kilometers duу to an inaccuracy of GPS-data in taxi applications? Are there regular sharp «jumps» in the Applications for Courier tracking? Do you need precise tracking in an on-demand service?

## What are the features of Mad Location Manager? It reduces the errors in route tracking It allows making motion of the objects on the map It eliminates additional distance when the object is motionless It decreases the noise from Low-class smartphones It excludes sharp «jumps» to the points remote from a real route It filters errors duу to the short-term loss of GPS-signal

## How does it work?

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

Shows where the North is ##### Accelerometer

Is used for acceleration measurement and angle determination  ##### Gyroscope

Allows us to get the current position of the object through the integration of gyroscope readings given the initial object position #### We have an acceleration vector in the “absolute” coordinate system and we can implement Kalman filter ##### Virtual Android sensors

We can use a LINEAR_ACCELERATION sensor for linear accelerations (excluding gravity force) and ROTATION_VECTOR sensor for device orientation ##### 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…      ## 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.

## 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)  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,