Dados de GPS suaves

Estou trabalhando com dados de GPS, obtendo valores a cada segundo e exibindo a posição atual em um mapa. O problema é que às vezes (especialmente quando a precisão é baixa) os valores variam muito, fazendo com que a posição atual “salte” entre pontos distantes no mapa.

Eu estava me perguntando sobre algum método bastante fácil para evitar isso. Como uma primeira ideia, pensei em descartar valores com precisão acima de certo limite, mas acho que há outras maneiras melhores de fazer isso. Qual é a maneira usual de os programas executarem isso?

    O que você está procurando é chamado de Filtro de Kalman . É freqüentemente usado para suavizar dados de navegação . Não é necessariamente trivial, e há muito ajuste que você pode fazer, mas é uma abordagem muito padrão e funciona bem. Existe uma biblioteca do KFilter disponível, que é uma implementação do C ++.

    Meu próximo substituto seria o menor ajuste de quadrados . Um filtro de Kalman suavizará as velocidades de coleta de dados, enquanto uma abordagem de ajuste de mínimos quadrados apenas usará informações posicionais. Ainda assim, é definitivamente mais simples de implementar e entender. Parece que a Biblioteca Científica GNU pode ter uma implementação disso.

    Aqui está um filtro simples de Kalman que pode ser usado exatamente para essa situação. Veio de algum trabalho que fiz em dispositivos Android.

    A teoria geral do filtro de Kalman é toda sobre estimativas para vetores, com a precisão das estimativas representadas por matrizes de covariância. No entanto, para estimar a localização em dispositivos Android, a teoria geral reduz para um caso muito simples. Os provedores de localização do Android fornecem o local como latitude e longitude, junto com uma precisão especificada como um único número medido em metros. Isso significa que, em vez de uma matriz de covariância, a precisão no filtro de Kalman pode ser medida por um único número, mesmo que a localização no filtro de Kalman seja medida por dois números. Além disso, o fato de que latitude, longitude e metros são efetivamente todas as unidades diferentes pode ser ignorado, porque se você colocar os fatores de escala no filtro de Kalman para convertê-los nas mesmas unidades, esses fatores serão cancelados ao converter os resultados. de volta para as unidades originais.

    O código poderia ser melhorado, porque assume que a melhor estimativa da localização atual é a última localização conhecida, e se alguém está se movendo, deve ser possível usar sensores do Android para produzir uma estimativa melhor. O código tem um único parâmetro livre Q, expresso em metros por segundo, que descreve a rapidez com que a precisão decai na ausência de novas estimativas de localização. Um parâmetro Q mais alto significa que a precisão decai mais rapidamente. Os filtros de Kalman geralmente funcionam melhor quando a precisão decai um pouco mais rápido do que se poderia esperar, por isso, para andar com um telefone Android, acho que Q = 3 metros por segundo funciona bem, embora eu ande mais lento do que isso. Mas se viajar em um carro rápido, um número muito maior deve obviamente ser usado.

    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; } ///  /// Kalman filter processing for lattitude and longitude ///  /// new measurement of lattidude /// new measurement of longitude /// measurement of 1 standard deviation error in metres /// time of measurement /// new state 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; } } } 

    Isso pode chegar um pouco tarde …

    Eu escrevi este KalmanLocationManager para Android, que envolve os dois provedores de localização mais comuns, Network e GPS, kalman-filtra os dados e entrega atualizações para um LocationListener (como os dois provedores ‘reais’).

    Eu uso principalmente para “interpolar” entre leituras – para receber atualizações (previsões de posição) a cada 100 milis por exemplo (em vez da taxa máxima de um segundo), o que me dá uma melhor taxa de frameworks ao animar minha posição.

    Na verdade, ele usa três filtros kalman, para cada dimensão: latitude, longitude e altitude. Eles são independentes, de qualquer maneira.

    Isso torna a matemática da matriz muito mais fácil: em vez de usar uma matriz de transição de estado 6×6, eu uso 3 matrizes 2×2 diferentes. Na verdade, no código, não uso matrizes. Resolvido todas as equações e todos os valores são primitivos (double).

    O código-fonte está funcionando e há uma atividade de demonstração. Desculpe pela falta de javadoc em alguns lugares, eu vou alcançá-lo.

    Você não deve calcular a velocidade da mudança de posição por vez. O GPS pode ter posições imprecisas, mas tem velocidade precisa (acima de 5 km / h). Portanto, use a velocidade do carimbo de localização do GPS. E, além disso, você não deve fazer isso com o curso, embora funcione na maioria das vezes.

    Posições GPS, como entregues, já são filtradas por Kalman, você provavelmente não pode melhorar, no pós-processamento, geralmente você não tem as mesmas informações, como o chip GPS.

    Você pode suavizá-lo, mas isso também introduz erros.

    Apenas certifique-se de remover suas posições quando o dispositivo estiver parado, isso remove as posições de salto, que alguns dispositivos / configurações não removem.

    Eu costumo usar os acelerômetros. Uma mudança repentina de posição em um curto período implica alta aceleração. Se isso não for refletido na telemetria do acelerômetro, é quase certamente devido a uma mudança nos “três melhores” satélites usados ​​para calcular a posição (à qual me refiro como teleporte GPS).

    Quando um ativo está em repouso e pulando devido ao teletransporte GPS, se você calcular progressivamente o centróide, estará efetivamente cruzando um conjunto cada vez maior de cascas, melhorando a precisão.

    Para fazer isso, quando o ativo não está em repouso, você deve estimar sua próxima posição e orientação prováveis ​​com base nos dados de aceleração, direção, linear e rotação (se você tiver giroscópios). Isso é mais ou menos o que o famoso filtro K faz. Você pode obter a coisa toda em hardware por cerca de US $ 150 em um AHRS contendo tudo, mas o módulo GPS, e com um conector para conectar um. Tem seu próprio processador e filtragem de Kalman a bordo; os resultados são estáveis ​​e muito bons. A orientação inercial é altamente resistente ao jitter, mas se desvia com o tempo. O GPS é propenso a jitter, mas não se desloca com o tempo, eles foram praticamente feitos para compensar uns aos outros.

    Um método que usa menos matemática / teoria é amostrar 2, 5, 7 ou 10 pontos de dados de cada vez e determinar aqueles que são outliers. Uma medida menos precisa de um outlier do que um Filtro de Kalman é usar o algoritmo a seguir para tomar todas as distâncias entre pares de pontos e eliminar o que estiver mais distante dos outros. Normalmente, esses valores são substituídos pelo valor mais próximo do valor periférico que você está substituindo

    Por exemplo

    Suavização em cinco pontos de amostra A, B, C, D, E

    ATOTAL = SOMA das distâncias AB AC AD AE

    BTOTAL = SOMA das distâncias AB BC BD BE

    CTOTAL = SOMA das distâncias AC BC CD CE

    DTOTAL = SOMA das distâncias DA DB DC DE

    ETOTAL = SOMA das distâncias EA EB EC DE

    Se BTOTAL for maior, você replaceá o ponto B por D se BD = min {AB, BC, BD, BE}

    Essa suavização determina outliers e pode ser aumentada usando o ponto médio de BD em vez do ponto D para suavizar a linha posicional. Sua milhagem pode variar e soluções matematicamente mais rigorosas existem.

    Você também pode usar um spline. Alimente os valores que você tem e interpole pontos entre seus pontos conhecidos. Vincular isso com um ajuste de mínimos quadrados, filtro de média móvel ou kalman (como mencionado em outras respostas) dá a você a capacidade de calcular os pontos entre os seus pontos “conhecidos”.

    Ser capaz de interpolar os valores entre os seus conhecidos dá-lhe uma transição suave e uma / razoável / aproximação de quais dados estariam presentes se você tivesse uma maior fidelidade. http://en.wikipedia.org/wiki/Spline_interpolation

    Splines diferentes possuem características diferentes. Os mais comuns que eu já vi são Akima e splines cúbicos.

    Outro algoritmo a ser considerado é o algoritmo de simplificação de linha Ramer-Douglas-Peucker, bastante comumente utilizado na simplificação de dados de GPS. ( http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm )

    Voltando para os Filtros de Kalman … Eu encontrei uma implementação de C para um filtro de Kalman para dados de GPS aqui: http://github.com/lacker/ikalman Eu não tentei ainda, mas parece promissor.

    Quanto aos mínimos quadrados, aqui estão algumas outras coisas para experimentar:

    1. Só porque é o menor ajuste dos quadrados não significa que ele deva ser linear. Você pode ajustar por quadrados mínimos uma curva quadrática aos dados, então isso se encheckboxria em um cenário no qual o usuário está acelerando. (Observe que, com mínimos quadrados, entendo usar as coordenadas como a variável dependente e o tempo como a variável independente.)

    2. Você também pode tentar ponderar os pontos de dados com base na precisão relatada. Quando a precisão é baixa, os pontos de dados são mais baixos.

    3. Outra coisa que você pode querer tentar é, em vez de exibir um único ponto, se a precisão for baixa, exibir um círculo ou algo indicando o intervalo em que o usuário poderia se basear na precisão relatada. (Isso é o que o aplicativo do Google Maps embutido no iPhone faz.)

    Mapeado para o CoffeeScript se alguém estiver interessado. ** edit -> desculpe usar o backbone também, mas você entendeu.

    Modificado ligeiramente para aceitar um farol com atributos

    {latitude: item.lat, longitude: item.lng, date: nova data (item.effective_at), precisão: 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]