Données GPS lisses

ce que vous recherchez s'appelle un filtre de Kalman . Il est fréquemment utilisé pour données de navigation lisses . Il n'est pas forcément triviale, et il y a beaucoup de réglage, vous pouvez le faire, mais c'est une approche standard et fonctionne bien. Il existe une bibliothèque KFilter disponible qui est une implémentation C++.

Ma prochaine de secours serait moindres carrés ajustement . Kalman le filtre adoucira les données en tenant compte des vitesses, alors qu'une approche par moindres carrés n'utilisera que des informations de position. Pourtant, il est certainement plus simple à mettre en œuvre et à comprendre. Il semble que la bibliothèque scientifique GNU puisse avoir une implémentation de ceci.

voici un filtre Kalman simple qui pourrait être utilisé pour exactement cette situation. Ça vient d'un travail que j'ai fait sur des appareils Android.

Générale filtre de Kalman théorie est tout au sujet des estimations pour les vecteurs, avec la précision des estimations représentés par des matrices de covariance. Cependant, pour estimer l'emplacement sur les appareils Android la théorie générale se réduit à un cas très simple. Les fournisseurs d'emplacement Android donnent l'emplacement comme une latitude et une longitude, ainsi que une précision qui est spécifiée comme un nombre unique mesuré en mètres. Cela signifie qu'au lieu d'une matrice de covariance, la précision dans le filtre de Kalman peut être mesurée par un seul nombre, même si l'emplacement dans le filtre de Kalman est une mesurée par deux nombres. Aussi le fait que la latitude, la longitude et les mètres sont effectivement toutes les différentes unités peut être ignoré, parce que si vous mettez des facteurs d'échelle dans le filtre de Kalman pour les convertir tous en les mêmes unités, puis ces facteurs d'échelle finir par annuler lors de la conversion des résultats en unités originales.

Le code pourrait être améliorée, car elle suppose que la meilleure estimation de l'emplacement actuel est le dernier emplacement connu, et si quelqu'un se déplace, il devrait être possible d'utiliser Android capteurs pour produire une meilleure estimation. Le code a un seul paramètre libre Q, exprimé en mètres par seconde, qui décrit la vitesse à laquelle la précision décroît en l'absence de toute nouvelle estimation de localisation. Un un paramètre Q plus élevé signifie que la précision décroît plus rapidement. Les filtres Kalman fonctionnent généralement mieux lorsque la précision décroît un peu plus vite qu'on pourrait s'y attendre, donc pour marcher avec un téléphone Android je trouve que Q=3 mètres par seconde fonctionne bien, même si je marche généralement plus lentement que cela. Mais si vous voyagez dans une voiture rapide, un plus grand nombre doit évidemment être utilisé.

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;
    }

    /// <summary>
    /// Kalman filter processing for lattitude and longitude
    /// </summary>
    /// <param name="lat_measurement_degrees">new measurement of lattidude</param>
    /// <param name="lng_measurement">new measurement of longitude</param>
    /// <param name="accuracy">measurement of 1 standard deviation error in metres</param>
    /// <param name="TimeStamp_milliseconds">time of measurement</param>
    /// <returns>new state</returns>
    public void Process(double lat_measurement, double lng_measurement, float accuracy, long TimeStamp_milliseconds) {
        if (accuracy < MinAccuracy) accuracy = MinAccuracy;
        if (variance < 0) {
            // if variance < 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 > 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;
        }
    }
}

ça pourrait arriver un peu tard...

j'ai écrit ce KalmanLocationManager pour Android, qui enveloppe les deux fournisseurs de localisation les plus communs, le réseau et le GPS, kalman-filtres les données, et fournit des mises à jour à un LocationListener (comme les deux 'real' fournisseurs).

Je l'utilise principalement pour "interpoler" entre les lectures - pour recevoir des mises à jour (prédictions de position) tous les 100 millis par exemple (au lieu de la vitesse maximale gps d'une seconde), ce qui me donne un meilleur cadence lors de l'animation de ma position.

en fait, il utilise trois filtres kalman, on pour chaque dimension: latitude, longitude et altitude. Ils sont indépendants, de toute façon.

cela rend le calcul matriciel beaucoup plus facile: au lieu d'utiliser une matrice de transition d'état 6x6, j'utilise 3 matrices 2x2 différentes. En fait, dans le code, je n'utilise pas de matrices. Résolu toutes les équations et toutes les valeurs sont primitives (double).

le code source fonctionne, et il y a une activité de démonstration. Désolé pour le manque de javadoc dans certains endroits, je vais rattraper.

vous ne devez pas calculer la vitesse à partir du changement de position par fois. Le GPS peut avoir des positions inexactes, mais il a une vitesse précise (au-dessus de 5km/h). Utilisez la vitesse indiquée par le GPS. Et de plus, vous ne devriez pas faire cela avec cours, bien que cela fonctionne la plupart du temps.

les positions GPS, à la livraison, sont déjà de Kalman filtrée, vous ne pourrez probablement pas s'améliorer, en post-traitement habituellement, vous n'avez pas les mêmes informations, comme la puce GPS.

vous pouvez lisser, mais cela introduit aussi des erreurs.

assurez-vous juste que vous supprimez les positions lorsque le périphérique est immobile, cela supprime les positions de saut, que certains périphériques/Configurations ne suppriment pas.

j'utilise habituellement les accéléromètres. Un changement soudain de position en peu de temps implique une forte accélération. Si cela ne se reflète pas dans la télémétrie de l'accéléromètre, c'est presque certainement dû à un changement dans les "trois meilleurs" satellites utilisés pour calculer la position (que j'appelle le téléport GPS).

quand un atout est au repos et sautillant en raison de la téléportation GPS, si vous calculez progressivement le centroid vous coupez effectivement un plus grand et plus grand jeu de coquilles, amélioration de la précision.

pour ce faire lorsque le bien n'est pas au repos, vous devez estimer sa position et son orientation probables en fonction de la vitesse, du cap et des données d'accélération linéaire et rotationnelle (si vous avez des gyroscopes). C'est plus ou moins ce que fait le fameux K filter. Vous pouvez obtenir le tout en matériel pour environ 150 $sur un AHRS contenant tout sauf le module GPS, et avec un jack pour connecter un. Il dispose de son propre CPU et de filtrage Kalman à bord; le les résultats sont stables et assez bon. Le guidage inertiel est très résistant aux secousses, mais dérive avec le temps. Le GPS est enclin à jitter mais ne dérive pas avec le temps, ils ont été pratiquement faits pour se compenser mutuellement.

une méthode qui utilise moins de mathématiques/théorie est d'échantillonner 2, 5, 7, ou 10 points de données à la fois et de déterminer ceux qui sont aberrants. Une mesure moins précise d'une valeur aberrante qu'un filtre de Kalman consiste à utiliser l'algorithme suivant pour prendre toutes les distances par paire entre les points et jeter celui qui est le plus éloigné des autres. En général, ces valeurs sont remplacées par la valeur la plus proche de la valeur périphérique que vous remplacez

Par exemple

lissage en cinq points d'échantillonnage A, B, C, D, E

ATOTAL = somme des distances AB AC AD AE

BTOTAL = somme des distances AB BC BD BE

CTOTAL = somme des distances AC BC CD CE

DTOTAL = somme des distances DA DB DC de

ETOTAL = somme des distances EA EB EC de

si BTOTAL est le plus grand, vous remplacerez le point B par D si BD = min { AB, BC, BD, BE}

ce lissage détermine les valeurs aberrantes et peut être augmenté en utilisant le point médian de BD au lieu du point D pour lisser la ligne de position. Votre kilométrage peut varier et des solutions plus mathématiquement rigoureuses existent.

Vous pouvez également utiliser une spline. Alimentez les valeurs que vous avez et interpolez les points entre vos points connus. Le fait de lier cela avec un ajustement par les moindres carrés, une moyenne mobile ou un filtre de kalman (comme mentionné dans d'autres réponses) vous donne la possibilité de calculer les points entre vos points "connus".

être en mesure d'interpoler les valeurs entre vos knowns vous donne une transition en douceur et a /raisonnable/ approximation de ce que les données seraient présents si vous aviez un haute fidélité. http://en.wikipedia.org/wiki/Spline_interpolation

différentes cannelures ont des caractéristiques différentes. Celui que J'ai vu le plus couramment utilisé sont Akima et splines cubiques.

un autre algorithme à considérer est L'algorithme de simplification de la ligne Ramer-Douglas-Peucker, il est assez couramment utilisé dans la simplification des données GPS. ( http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm )

retour aux filtres Kalman ... J'ai trouvé une implémentation C pour un filtre Kalman pour les données GPS ici: http://github.com/lacker/ikalman Je n'ai pas encore essayé, mais ça semble prometteur.

comme pour les moindres carrés, voici un couple d'autres choses à expérimenter avec:

1. ce n'est pas parce que c'est un ajustement des moindres carrés que cela veut dire qu'il doit être linéaire. Vous pouvez ajuster une courbe quadratique aux données par la méthode des moindres carrés, puis cela correspondrait à un scénario dans lequel l'utilisateur accélère. (Notez que par les moindres carrés, je veux dire en utilisant les coordonnées comme variable dépendante et le temps comme variable indépendante.)

2. vous pouvez également essayer de pondérer les points de données en fonction de l'exactitude déclarée. Lorsque la précision est faible poids ces points de données plus faible.

3. une Autre chose que vous pourriez vouloir essayer est plutôt que d'afficher un point, si la précision est faible afficher un cercle ou quelque chose indiquant la zone dans laquelle l'utilisateur pourrait être basé sur la précision. (C'est ce que fait L'application Google Maps intégrée à L'iPhone.)

en Coffee-script si quelqu'un est intéressé. ** edit -> désolé d'utiliser l'épine dorsale aussi, mais vous obtenez l'idée.

modifié légèrement pour accepter une balise avec attributions

{latitude: élément.latitude,longitude: élément.le gnl,date: de nouvelles Date(item.effective_at),précision: l'élément.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]