Accurate and «pure» Data from GPS-receivers
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?
The solution is Mad Location Manager
What are the features of Mad Location Manager?
It reduces the errors in route tracking
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
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
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
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
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.
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.
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.
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
All the magic happened
thanks to Mad Devs
To express gratitude or to get consultation or assistance in the system implementation write to team@maddevs.io 