Smooth GPS data

Question

I m working with GPS data  getting values every second and displaying current position on a map  The problem is that sometimes  specially when accuracy is low  the values vary a lot  making the current position to  jump  between distant points in the map   I was wondering about some easy enough method to avoid this  As a first idea  I thought about discarding values with accuracy beyond certain threshold  but I guess there are some other better ways to do  What s the usual way programs perform this

User · Answer

Mapped to CoffeeScript if anyones interested. **edit -> sorry using backbone too, but you get the idea.

Modified slightly to accept a beacon with attribs

{latitude: item.lat,longitude: item.lng,date: new Date(item.effective_at),accuracy: item.gps_accuracy}

MIN_ACCURACY = 1

# mapped from http://stackoverflow.com/questions/1134579/smooth-gps-data

class v.Map.BeaconFilter

  constructor: ->
    _.extend(this, Backbone.Events)

  process: (decay,beacon) ->

    accuracy     = Math.max beacon.accuracy, MIN_ACCURACY

    unless @variance?
      # if variance nil, inititalise some values
      @variance     = accuracy * accuracy
      @timestamp_ms = beacon.date.getTime();
      @lat          = beacon.latitude
      @lng          = beacon.longitude

    else

      @timestamp_ms = beacon.date.getTime() - @timestamp_ms

      if @timestamp_ms > 0
        # time has moved on, so the uncertainty in the current position increases
        @variance += @timestamp_ms * decay * decay / 1000;
        @timestamp_ms = beacon.date.getTime();

      # Kalman gain matrix K = Covarariance * Inverse(Covariance + MeasurementVariance)
      # NB: because K is dimensionless, it doesn't matter that variance has different units to lat and lng
      _k  = @variance / (@variance + accuracy * accuracy)
      @lat = _k * (beacon.latitude  - @lat)
      @lng = _k * (beacon.longitude - @lng)

      @variance = (1 - _k) * @variance

    [@lat,@lng]

User · Answer

Here s a Javascript implementation of  Stochastically s Java implementation for anyone needing it   class GPSKalmanFilter     constructor  decay   3        this decay   decay     this variance   -1     this minAccuracy   1        process  lat  lng  accuracy  timestampInMs        if  accuracy  lt  this minAccuracy  accuracy   this minAccuracy      if  this variance  lt  0          this timestampInMs   timestampInMs       this lat   lat       this lng   lng       this variance   accuracy   accuracy       else         const timeIncMs   timestampInMs - this timestampInMs        if  timeIncMs  gt  0            this variance     timeIncMs   this decay   this decay    1000         this timestampInMs   timestampInMs                const  k   this variance    this variance    accuracy   accuracy         this lat     k    lat - this lat        this lng     k    lng - this lng         this variance    1 -  k    this variance            return  this lng  this lat          Usage example      const kalmanFilter   new GPSKalmanFilter      const updatedCoords           for  let index   0  index  lt  coords length  index            const   lat  lng  accuracy  timestampInMs     coords index        updatedCoords index    kalmanFilter process lat  lng  accuracy  timestampInMs

User · Answer

Going back to the Kalman Filters     I found a C implementation for a Kalman filter for GPS data here  http   github com lacker ikalman I haven t tried it out yet  but it seems promising

User · Answer

You should not calculate speed from position change per time  GPS may have inaccurate positions  but it has accurate speed  above 5km h   So use the speed from GPS location stamp  And further you should not do that with course  although it works most of the times   GPS positions  as delivered  are already Kalman filtered  you probably cannot improve  in postprocessing usually you have not the same information like the GPS chip     You can smooth it  but this also introduces errors   Just make sure that your remove the positions when the device stands still  this removes   jumping positions  that some devices Configurations do not remove

User · Answer

I usually use the accelerometers  A sudden change of position in a short period implies high acceleration  If this is not reflected in accelerometer telemetry it is almost certainly due to a change in the  best three  satellites used to compute position  to which I refer as GPS teleporting     When an asset is at rest and hopping about due to GPS teleporting  if you progressively compute the centroid you are effectively intersecting a larger and larger set of shells  improving precision    To do this when the asset is not at rest you must estimate its likely next position and orientation based on speed  heading and linear and rotational  if you have gyros  acceleration data  This is more or less what the famous K filter does  You can get the whole thing in hardware for about  150 on an AHRS containing everything but the GPS module  and with a jack to connect one  It has its own CPU and Kalman filtering on board  the results are stable and quite good  Inertial guidance is highly resistant to jitter but drifts with time  GPS is prone to jitter but does not drift with time  they were practically made to compensate each other

User · Answer

I have transformed the Java code from  Stochastically to Kotlin  class KalmanLatLong       private val MinAccuracy  Float   1f      private var Q metres per second  Float   0f     private var TimeStamp milliseconds  Long   0     private var lat  Double   0 toDouble       private var lng  Double   0 toDouble       private var variance  Float           0 toFloat      P matrix   Negative means object uninitialised   NB  units irrelevant  as long as same units used throughout      fun KalmanLatLong Q metres per second  Float                this Q metres per second   Q metres per second         variance   -1f            fun get TimeStamp    Long   return TimeStamp milliseconds       fun get lat    Double   return lat       fun get lng    Double   return lng       fun get accuracy    Float   return Math sqrt variance toDouble    toFloat          fun SetState lat  Double  lng  Double  accuracy  Float  TimeStamp milliseconds  Long                this lat   lat         this lng   lng         variance   accuracy   accuracy         this TimeStamp milliseconds   TimeStamp milliseconds                 lt summary gt          Kalman filter processing for lattitude and longitude         https   stackoverflow com questions 1134579 smooth-gps-data 15657798 15657798          lt  summary gt           lt param name  lat measurement degrees  gt new measurement of lattidude lt  param gt           lt param name  lng measurement  gt new measurement of longitude lt  param gt           lt param name  accuracy  gt measurement of 1 standard deviation error in metres lt  param gt           lt param name  TimeStamp milliseconds  gt time of measurement lt  param gt           lt returns gt new state lt  returns gt      fun Process lat measurement  Double  lng measurement  Double  accuracy  Float  TimeStamp milliseconds  Long                var accuracy   accuracy         if  accuracy  lt  MinAccuracy  accuracy   MinAccuracy          if  variance  lt  0                           if variance  lt  0  object is unitialised  so initialise with current values             this TimeStamp milliseconds   TimeStamp milliseconds             lat   lat measurement             lng   lng measurement             variance   accuracy   accuracy                   else                          else apply Kalman filter methodology              val TimeInc milliseconds   TimeStamp milliseconds - this TimeStamp milliseconds              if  TimeInc milliseconds  gt  0                                   time has moved on  so the uncertainty in the current position increases                 variance    TimeInc milliseconds toFloat     Q metres per second   Q metres per second   1000                 this TimeStamp milliseconds   TimeStamp milliseconds                    TO DO  USE VELOCITY INFORMATION HERE TO GET A BETTER ESTIMATE OF CURRENT POSITION                               Kalman gain matrix K   Covarariance   Inverse Covariance   MeasurementVariance                 NB  because K is dimensionless  it doesn t matter that variance has different units to lat and lng             val K   variance    variance   accuracy   accuracy                 apply K             lat    K    lat measurement - lat              lng    K    lng measurement - lng                 new Covarariance  matrix is  IdentityMatrix - K    Covarariance             variance    1 - K    variance

User · Answer

This might come a little late     I wrote this KalmanLocationManager for Android  which wraps the two most common location providers  Network and GPS  kalman-filters the data  and delivers updates to a LocationListener  like the two  real  providers    I use it mostly to  interpolate  between readings - to receive updates  position predictions  every 100 millis for instance  instead of the maximum gps rate of one second   which gives me a better frame rate when animating my position   Actually  it uses three kalman filters  on for each dimension  latitude  longitude and altitude  They re independent  anyway   This makes the matrix math much easier  instead of using one 6x6 state transition matrix  I use 3 different 2x2 matrices  Actually in the code  I don t use matrices at all  Solved all equations and all values are primitives  double    The source code is working  and there s a demo activity  Sorry for the lack of javadoc in some places  I ll catch up

User · Answer

You can also use a spline  Feed in the values you have and interpolate points between your known points  Linking this with a least-squares fit  moving average or kalman filter  as mentioned in other answers  gives you the ability to calculate the points inbetween your  known  points   Being able to interpolate the values between your knowns gives you a nice smooth transition and a  reasonable  approximation of what data would be present if you had a higher-fidelity  http   en wikipedia org wiki Spline interpolation  Different splines have different characteristics  The one s I ve seen most commonly used are Akima and Cubic splines   Another algorithm to consider is the Ramer-Douglas-Peucker line simplification algorithm  it is quite commonly used in the simplification of GPS data   http   en wikipedia org wiki Ramer-Douglas-Peucker algorithm

User · Answer

Here s a simple Kalman filter that could be used for exactly this situation   It came from some work I did on Android devices   General Kalman filter theory is all about estimates for vectors  with the accuracy of the estimates represented by covariance matrices   However  for estimating location on Android devices the general theory reduces to a very simple case    Android location providers give the location as a latitude and longitude  together with an accuracy which is specified as a single number measured in metres   This means that instead of a covariance matrix  the accuracy in the Kalman filter can be measured by a single number  even though the location in the Kalman filter is a measured by two numbers   Also the fact that the latitude  longitude and metres are effectively all different units can be ignored  because if you put scaling factors into the Kalman filter to convert them all into the same units  then those scaling factors end up cancelling out when converting the results back into the original units   The code could be improved  because it assumes that the best estimate of current location is the last known location  and if someone is moving it should be possible to use Android s sensors to produce a better estimate   The code has a single free parameter Q  expressed in metres per second  which describes how quickly the accuracy decays in the absence of any new location estimates   A higher Q parameter means that the accuracy decays faster   Kalman filters generally work better when the accuracy decays a bit quicker than one might expect  so for walking around with an Android phone I find that Q 3 metres per second works fine  even though I generally walk slower than that    But if travelling in a fast car a much larger number should obviously be used   public class KalmanLatLong       private final float MinAccuracy   1       private float Q metres per second          private long TimeStamp milliseconds      private double lat      private double lng      private float variance     P matrix   Negative means object uninitialised   NB  units irrelevant  as long as same units used throughout      public KalmanLatLong float Q metres per second    this Q metres per second   Q metres per second  variance   -1         public long get TimeStamp     return TimeStamp milliseconds        public double get lat     return lat        public double get lng     return lng        public float get accuracy     return  float Math sqrt variance          public void SetState double lat  double lng  float accuracy  long TimeStamp milliseconds            this lat lat  this lng lng  variance   accuracy   accuracy  this TimeStamp milliseconds TimeStamp milliseconds                  lt summary gt          Kalman filter processing for lattitude and longitude          lt  summary gt           lt param name  lat measurement degrees  gt new measurement of lattidude lt  param gt           lt param name  lng measurement  gt new measurement of longitude lt  param gt           lt param name  accuracy  gt measurement of 1 standard deviation error in metres lt  param gt           lt param name  TimeStamp milliseconds  gt time of measurement lt  param gt           lt returns gt new state lt  returns gt      public void Process double lat measurement  double lng measurement  float accuracy  long TimeStamp milliseconds            if  accuracy  lt  MinAccuracy  accuracy   MinAccuracy          if  variance  lt  0                   if variance  lt  0  object is unitialised  so initialise with current values             this TimeStamp milliseconds   TimeStamp milliseconds              lat lat measurement  lng   lng measurement  variance   accuracy accuracy             else                  else apply Kalman filter methodology              long TimeInc milliseconds   TimeStamp milliseconds - this TimeStamp milliseconds              if  TimeInc milliseconds  gt  0                       time has moved on  so the uncertainty in the current position increases                 variance    TimeInc milliseconds   Q metres per second   Q metres per second   1000                  this TimeStamp milliseconds   TimeStamp milliseconds                     TO DO  USE VELOCITY INFORMATION HERE TO GET A BETTER ESTIMATE OF CURRENT POSITION                               Kalman gain matrix K   Covarariance   Inverse Covariance   MeasurementVariance                 NB  because K is dimensionless  it doesn t matter that variance has different units to lat and lng             float K   variance    variance   accuracy   accuracy                  apply K             lat    K    lat measurement - lat               lng    K    lng measurement - lng                  new Covarariance  matrix is  IdentityMatrix - K    Covarariance              variance    1 - K    variance

User · Answer

One method that uses less math theory is to sample 2  5  7  or 10 data points at a time and determine those which are outliers   A less accurate measure of an outlier than a Kalman Filter is to to use the following algorithm to take all pair wise distances between points and throw out the one that is furthest from the the others   Typically those values are replaced with the value closest to the outlying value you are replacing  For example  Smoothing at five sample points A  B  C  D  E  ATOTAL   SUM of distances AB AC AD AE  BTOTAL   SUM of distances AB BC BD BE  CTOTAL   SUM of distances AC BC CD CE  DTOTAL   SUM of distances DA DB DC DE  ETOTAL   SUM of distances EA EB EC DE  If BTOTAL is largest you would replace point B with D if BD   min   AB  BC  BD  BE    This smoothing determines outliers and can be augmented by using the midpoint of BD instead of point D to smooth the positional line   Your mileage may vary and more mathematically rigorous solutions exist

User · Answer

As for least squares fit  here are a couple other things to experiment with    Just because it s least squares fit doesn t mean that it has to be linear  You can least-squares-fit a quadratic curve to the data  then this would fit a scenario in which the user is accelerating   Note that by least squares fit I mean using the coordinates as the dependent variable and time as the independent variable   You could also try weighting the data points based on reported accuracy  When the accuracy is low weight those data points lower  Another thing you might want to try is rather than display a single point  if the accuracy is low display a circle or something indicating the range in which the user could be based on the reported accuracy   This is what the iPhone s built-in Google Maps application does

User · Answer

What you are looking for is called a Kalman Filter  It s frequently used to smooth navigational data  It is not necessarily trivial  and there is a lot of tuning you can do  but it is a very standard approach and works well  There is a KFilter library available which is a C   implementation    My next fallback would be least squares fit  A Kalman filter will smooth the data taking velocities into account  whereas a least squares fit approach will just use positional information  Still  it is definitely simpler to implement and understand  It looks like the GNU Scientific Library may have an implementation of this

[gps] Smooth GPS data

Examples related to gps

Examples related to smoothing