puntos - Smooth datos de GPS

mapsource

Question

Estoy trabajando con datos de GPS, obteniendo valores cada segundo y mostrando la posición actual en un mapa. El problema es que a veces (especialmente cuando la precisión es baja) los valores varían mucho, haciendo que la posición actual "salte" entre puntos distantes en el mapa.

Me preguntaba acerca de algún método bastante fácil para evitar esto. Como primera idea, pensé en descartar valores con precisión más allá de cierto umbral, pero creo que hay otras formas mejores de hacerlo. ¿Cuál es la forma habitual en que los programas realizan esto?

Answer 1

Aquí hay un filtro de Kalman simple que podría usarse exactamente para esta situación. Vino de algún trabajo que hice en dispositivos Android.

La teoría general del filtro de Kalman tiene que ver con las estimaciones de los vectores, con la precisión de las estimaciones representadas por las matrices de covarianza. Sin embargo, para estimar la ubicación en dispositivos Android, la teoría general se reduce a un caso muy simple. Los proveedores de ubicación de Android dan la ubicación como una latitud y longitud, junto con una precisión que se especifica como un único número medido en metros. Esto significa que en lugar de una matriz de covarianza, la precisión en el filtro de Kalman se puede medir con un solo número, aunque la ubicación en el filtro de Kalman se mide con dos números. También se puede ignorar el hecho de que la latitud, la longitud y los metros son efectivamente unidades diferentes, porque si se colocan factores de escala en el filtro de Kalman para convertirlos en las mismas unidades, esos factores de escala terminarán anulando al convertir los resultados de vuelta a las unidades originales.

El código podría mejorarse, ya que supone que la mejor estimación de la ubicación actual es la última ubicación conocida, y si alguien se está moviendo, debería ser posible utilizar los sensores de Android para producir una mejor estimación. El código tiene un único parámetro libre Q, expresado en metros por segundo, que describe qué tan rápido decae la precisión en ausencia de nuevas estimaciones de ubicación. Un parámetro Q más alto significa que la precisión decae más rápido. Los filtros de Kalman generalmente funcionan mejor cuando la precisión decae un poco más rápido de lo que cabría esperar, así que para caminar con un teléfono Android me parece que Q = 3 metros por segundo funciona bien, aunque generalmente camino más despacio que eso. Pero si viaja en un automóvil rápido, obviamente se debe usar un número mucho mayor.

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

Answer 2

En cuanto al ajuste de mínimos cuadrados, aquí hay algunas otras cosas para experimentar:

1. El hecho de que encaje en mínimos cuadrados no significa que tenga que ser lineal. Puede ajustar por mínimos cuadrados una curva cuadrática a los datos, entonces esto se ajustaría a un escenario en el que el usuario está acelerando. (Tenga en cuenta que por ajuste de mínimos cuadrados me refiero a usar las coordenadas como la variable dependiente y el tiempo como la variable independiente).

2. También podría intentar ponderar los puntos de datos según la precisión informada. Cuando la precisión es de bajo peso, esos puntos de datos son más bajos.

3. Otra cosa que puede intentar es mostrar un solo punto, si la precisión es baja, mostrar un círculo o algo que indique el rango en el que el usuario podría basarse en la precisión informada. (Esto es lo que hace la aplicación integrada de Google Maps para iPhone).

Answer 3

Esto podría llegar un poco tarde ...

Escribí este KalmanLocationManager para Android, que KalmanLocationManager a los dos proveedores de ubicación más comunes, la red y el GPS, kalman filtra los datos y ofrece actualizaciones a LocationListener (como los dos proveedores "reales").

Lo uso principalmente para "interpolar" entre lecturas, recibir actualizaciones (predicciones de posición) cada 100 mili por ejemplo (en lugar de la tasa máxima de gps de un segundo), lo que me da una mejor velocidad de cuadros al animar mi posición.

En realidad, usa tres filtros kalman, para cada dimensión: latitud, longitud y altitud. Son independientes, de todos modos.

Esto hace que la matriz matemática sea mucho más fácil: en lugar de usar una matriz de transición de estados de 6x6, utilizo 3 matrices 2x2 diferentes. De hecho, en el código, no uso matrices en absoluto. Resolvió todas las ecuaciones y todos los valores son primitivos (doble).

El código fuente está funcionando, y hay una actividad de demostración. Perdón por la falta de Javadoc en algunos lugares, me pondré al día.

Answer 4

Lo que estás buscando se llama filtro de Kalman . Se usa con frecuencia para suavizar los datos de navegación . No es necesariamente trivial, y hay mucho ajuste que puedes hacer, pero es un enfoque muy estándar y funciona bien. Hay una biblioteca de KFilter disponible que es una implementación de C ++.

Mi próxima alternativa sería ajustar los mínimos cuadrados . Un filtro de Kalman suavizará las velocidades de toma de datos en cuenta, mientras que un enfoque de ajuste de mínimos cuadrados solo usará la información de posición. Aún así, es definitivamente más simple de implementar y entender. Parece que la Biblioteca Científica GNU puede tener una implementación de esto.

Answer 5

Mapeado a CoffeeScript si alguien está interesado. ** editar -> disculpa el uso de la red troncal también, pero entiendes la idea.

Modificado ligeramente para aceptar un faro con attribs

{latitude: item.lat, longitud: item.lng, fecha: new Fecha (item.effective_at), accuracy: item.gps_accuracy}

MIN_ACCURACY = 1

# mapped from http://.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]

Answer 6

No debe calcular la velocidad del cambio de posición por tiempo. El GPS puede tener posiciones imprecisas, pero tiene una velocidad precisa (más de 5 km / h). Así que usa la velocidad de la marca de localización GPS. Además, no debes hacer eso por supuesto, aunque funciona la mayoría de las veces.

Las posiciones de GPS, tal como se entregan, ya están filtradas por Kalman, probablemente no puedas mejorar, en el postprocesamiento usualmente no tienes la misma información que el chip GPS.

Puedes suavizarlo, pero esto también introduce errores.

Solo asegúrese de quitar las posiciones cuando el dispositivo se detenga, esto elimina las posiciones de salto, que algunos dispositivos / Configuraciones no eliminan.

Answer 7

También puedes usar una spline. Ingrese los valores que tiene e interpole puntos entre sus puntos conocidos. Vincular esto con un ajuste de mínimos cuadrados, un promedio móvil o un filtro de kalman (como se menciona en otras respuestas) le da la capacidad de calcular los puntos entre los puntos "conocidos".

Ser capaz de interpolar los valores entre tus conocimientos te da una transición suave y razonable / una aproximación razonable de qué datos estarían presentes si tuvieras una fidelidad más alta. http://en.wikipedia.org/wiki/Spline_interpolation

Diferentes splines tienen diferentes características. El que he visto más comúnmente utilizado son las estrías de Akima y Cubic.

Otro algoritmo a considerar es el algoritmo de simplificación de la línea Ramer-Douglas-Peucker, que se utiliza comúnmente en la simplificación de los datos del GPS. ( http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm )

Answer 8

Un método que utiliza menos matemáticas / teoría es muestrear 2, 5, 7 o 10 puntos de datos a la vez y determinar aquellos que son atípicos. Una medida menos precisa de un valor atípico que un filtro de Kalman es usar el siguiente algorithm para tomar todas las distancias entre puntos y tirar la que está más alejada de las otras. Normalmente, esos valores se reemplazan por el valor más cercano al valor periférico que está reemplazando

Por ejemplo

Suavizado en cinco puntos de muestra A, B, C, D, E

ATOTAL = Suma de distancias AB AC AD AE

BTOTAL = Suma de distancias AB BC BD BE

CTOTAL = SUMA de distancias AC BC CD CE

DTOTAL = Suma de distancias DA DB DC DE

ETOTAL = Suma de distancias EA EB EC DE

Si BTOTAL es más grande, reemplazaría el punto B por D si BD = min {AB, BC, BD, BE}

Este alisamiento determina valores atípicos y puede aumentarse utilizando el punto medio de BD en lugar del punto D para suavizar la línea posicional. Su millaje puede variar y existen soluciones matemáticamente más rigurosas.

Answer 9

Usualmente uso los acelerómetros. Un cambio repentino de posición en un corto período implica una gran aceleración. Si esto no se refleja en la telemetría del acelerómetro, es casi seguro que se debe a un cambio en los "tres mejores" satélites utilizados para calcular la posición (a la que me refiero como GPS de teletransportación).

Cuando un activo está en reposo y saltando debido a la teletransportación GPS, si calcula de manera progresiva el centroide, se está intersecando efectivamente un conjunto cada vez más grande de proyectiles, mejorando la precisión.

Para hacer esto cuando el activo no está en reposo, debe estimar su próxima posición y orientación en función de la velocidad, el rumbo y los datos de aceleración lineales y rotacionales (si tiene giroscopios). Esto es más o menos lo que hace el famoso filtro K. Puede obtener todo en hardware por aproximadamente $ 150 en un AHRS que contiene todo menos el módulo GPS, y con un conector para conectar uno. Tiene su propia CPU y filtro de Kalman a bordo; los resultados son estables y bastante buenos La guía inercial es altamente resistente a la trepidación, pero se desplaza con el tiempo. El GPS es propenso a la trepidación, pero no se desplaza con el tiempo, se hicieron prácticamente para compensarse mutuamente.

Answer 10

Volviendo a los filtros de Kalman ... encontré una implementación de C para un filtro de Kalman para datos de GPS aquí: http://github.com/lacker/ikalman Aún no lo he probado, pero parece prometedor.