Data GPS halus

Saya bekerja dengan data GPS, mendapatkan nilai setiap detik dan menampilkan posisi saat ini di peta. Masalahnya adalah bahwa kadang-kadang (khususnya ketika akurasi rendah) nilainya sangat bervariasi, membuat posisi saat ini untuk "melompat" antara titik-titik yang jauh di peta.

Saya bertanya-tanya tentang beberapa metode yang cukup mudah untuk menghindari ini. Sebagai ide pertama, saya berpikir untuk membuang nilai-nilai dengan akurasi di luar batas tertentu, tetapi saya kira ada beberapa cara lain yang lebih baik untuk dilakukan. Apa cara yang biasa dilakukan oleh program?

Berikut adalah filter Kalman sederhana yang dapat digunakan untuk situasi ini. Itu berasal dari beberapa pekerjaan yang saya lakukan pada perangkat Android.

Teori filter General Kalman adalah semua tentang estimasi untuk vektor, dengan akurasi estimasi diwakili oleh matriks kovarians. Namun, untuk memperkirakan lokasi pada perangkat Android teori umum dikurangi menjadi kasus yang sangat sederhana. Penyedia lokasi Android memberikan lokasi sebagai garis lintang dan bujur, bersama dengan keakuratan yang ditentukan sebagai angka tunggal yang diukur dalam meter. Ini berarti bahwa alih-alih matriks kovarians, akurasi dalam filter Kalman dapat diukur dengan angka tunggal, meskipun lokasi dalam filter Kalman diukur dengan dua angka. Juga fakta bahwa garis lintang, bujur dan meter secara efektif semua unit yang berbeda dapat diabaikan, karena jika Anda memasukkan faktor penskalaan ke dalam filter Kalman untuk mengubahnya semuanya menjadi unit yang sama,

Kode dapat ditingkatkan, karena mengasumsikan bahwa perkiraan terbaik dari lokasi saat ini adalah lokasi terakhir yang diketahui, dan jika seseorang bergerak, mungkin saja menggunakan sensor Android untuk menghasilkan perkiraan yang lebih baik. Kode memiliki satu parameter bebas Q, dinyatakan dalam meter per detik, yang menggambarkan seberapa cepat akurasi meluruh tanpa adanya perkiraan lokasi baru. Parameter Q yang lebih tinggi berarti bahwa akurasi meluruh lebih cepat. Filter Kalman umumnya bekerja lebih baik ketika akurasi meluruh sedikit lebih cepat daripada yang mungkin diharapkan, jadi untuk berjalan-jalan dengan ponsel Android saya menemukan bahwa Q = 3 meter per detik berfungsi dengan baik, meskipun saya biasanya berjalan lebih lambat dari itu. Tetapi jika bepergian dengan mobil cepat, jumlah yang jauh lebih besar harus digunakan.

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

Apa yang Anda cari disebut Filter Kalman . Ini sering digunakan untuk memuluskan data navigasi . Ini tidak selalu sepele, dan ada banyak penyetelan yang dapat Anda lakukan, tetapi ini adalah pendekatan yang sangat standar dan berfungsi dengan baik. Ada perpustakaan KFilter yang tersedia yang merupakan implementasi C ++.

Fallback saya berikutnya akan menjadi kotak paling cocok . Filter Kalman akan memuluskan data dengan mempertimbangkan kecepatan, sedangkan pendekatan kuadrat terkecil hanya akan menggunakan informasi posisi. Namun, jelas lebih mudah untuk diimplementasikan dan dipahami. Sepertinya Perpustakaan Ilmiah GNU mungkin memiliki implementasi ini.

Ini mungkin datang agak terlambat ...

Saya menulis KalmanLocationManager untuk Android ini, yang membungkus dua penyedia lokasi paling umum, Jaringan dan GPS, kalman-filter data, dan memberikan pembaruan ke LocationListener(seperti dua penyedia 'nyata').

Saya menggunakannya sebagian besar untuk "interpolasi" antara pembacaan - untuk menerima pembaruan (prediksi posisi) setiap 100 milis misalnya (bukannya laju gps maksimum satu detik), yang memberi saya frame rate yang lebih baik ketika menjiwai posisi saya.

Sebenarnya, ia menggunakan tiga filter kalman, aktif untuk setiap dimensi: lintang, bujur dan ketinggian. Lagipula mereka mandiri.

Ini membuat matematika matriks jauh lebih mudah: daripada menggunakan satu matriks transisi keadaan 6x6, saya menggunakan 3 matriks 2x2 berbeda. Sebenarnya dalam kode, saya tidak menggunakan matriks sama sekali. Memecahkan semua persamaan dan semua nilai adalah primitif (ganda).

Kode sumber berfungsi, dan ada aktivitas demo. Maaf karena kurangnya javadoc di beberapa tempat, saya akan menyusul.

Anda tidak harus menghitung kecepatan dari perubahan posisi per waktu. GPS mungkin memiliki posisi yang tidak akurat, tetapi memiliki kecepatan yang akurat (di atas 5km / jam). Jadi gunakan kecepatan dari cap lokasi GPS. Dan lebih jauh Anda tidak harus melakukannya dengan tentu saja, meskipun itu berfungsi sebagian besar waktu.

Posisi GPS, seperti yang disampaikan, sudah difilter Kalman, Anda mungkin tidak dapat meningkatkan, dalam postprocessing biasanya Anda tidak memiliki informasi yang sama seperti chip GPS.

Anda dapat memuluskannya, tetapi ini juga menimbulkan kesalahan.

Pastikan bahwa Anda menghapus posisi ketika perangkat diam, ini menghapus posisi melompat, bahwa beberapa perangkat / Konfigurasi tidak menghapus.

Saya biasanya menggunakan accelerometer. Perubahan posisi yang tiba-tiba dalam waktu singkat menyiratkan akselerasi tinggi. Jika ini tidak tercermin dalam telemetri accelerometer, hampir pasti karena perubahan pada satelit "tiga terbaik" yang digunakan untuk menghitung posisi (yang saya sebut sebagai teleportasi GPS).

Ketika sebuah aset dalam keadaan diam dan melompat-lompat karena GPS teleporting, jika Anda secara progresif menghitung centroid Anda secara efektif memotong set kerang yang lebih besar dan lebih besar, meningkatkan presisi.

Untuk melakukan ini ketika aset tidak diam, Anda harus memperkirakan kemungkinan posisi dan orientasi berikutnya berdasarkan kecepatan, heading, linier, dan data percepatan rotasi (jika Anda memiliki gyro). Ini kurang lebih apa yang dilakukan oleh filter K yang terkenal. Anda bisa mendapatkan semuanya dalam perangkat keras untuk sekitar $ 150 pada AHRS yang mengandung segalanya kecuali modul GPS, dan dengan jack untuk menghubungkan satu. Ini memiliki CPU dan Kalman filtering on board; hasilnya stabil dan cukup baik. Bimbingan inersia sangat tahan terhadap jitter tetapi hanyut dengan waktu. GPS rentan terhadap jitter tetapi tidak melayang dengan waktu, mereka praktis dibuat untuk saling mengimbangi.

Salah satu metode yang menggunakan lebih sedikit matematika / teori adalah untuk sampel 2, 5, 7, atau 10 titik data sekaligus dan menentukan yang outlier. Ukuran outlier yang kurang akurat dibandingkan dengan Kalman Filter adalah menggunakan algoritma berikut untuk mengambil semua jarak pasangan yang bijaksana antara titik dan membuang yang paling jauh dari yang lain. Biasanya nilai-nilai itu diganti dengan nilai yang paling dekat dengan nilai outlying yang Anda ganti

Sebagai contoh

Menghaluskan pada lima titik sampel A, B, C, D, E

ATOTAL = SUM jarak AB AC AD AE

BTOTAL = SUM jarak AB BC BD BE

CTOTAL = SUM jarak AC BC CD CE

DTOTAL = SUM jarak DA DB DC DE

ETOTAL = SUM jarak EA EB EC DE

Jika BTOTAL adalah terbesar, Anda akan mengganti titik B dengan D jika BD = min {AB, BC, BD, BE}

Smoothing ini menentukan outlier dan dapat ditambah dengan menggunakan titik tengah BD bukan titik D untuk menghaluskan garis posisi. Jarak tempuh Anda dapat bervariasi dan ada lebih banyak solusi yang ketat secara matematis.

Untuk kotak yang paling pas, berikut adalah beberapa hal lain yang dapat Anda coba:

1. Hanya karena kuadratnya paling sesuai tidak berarti bahwa itu harus linier. Anda paling tidak bisa-kuadrat-cocok kurva kuadrat ke data, maka ini akan cocok dengan skenario di mana pengguna mempercepat. (Perhatikan bahwa dengan kuadrat terkecil yang saya maksud menggunakan koordinat sebagai variabel dependen dan waktu sebagai variabel independen.)

2. Anda juga dapat mencoba menimbang titik data berdasarkan akurasi yang dilaporkan. Ketika akurasinya rendah, titik-titik data tersebut lebih rendah.

3. Hal lain yang mungkin ingin Anda coba daripada menampilkan satu titik, jika akurasinya rendah, tampilkan lingkaran atau sesuatu yang menunjukkan kisaran di mana pengguna dapat didasarkan pada akurasi yang dilaporkan. (Inilah yang dilakukan aplikasi Google Maps bawaan iPhone.)

Anda juga dapat menggunakan spline. Masukkan nilai-nilai yang Anda miliki dan sisipkan poin di antara poin yang diketahui. Menghubungkan ini dengan fit-kuadrat, rata-rata bergerak atau filter kalman (seperti yang disebutkan dalam jawaban lain) memberi Anda kemampuan untuk menghitung poin di antara poin "diketahui" Anda.

Mampu menginterpolasi nilai-nilai antara yang diketahui memberi Anda transisi yang bagus dan / masuk akal / perkiraan data apa yang akan hadir jika Anda memiliki kesetiaan yang lebih tinggi. http://en.wikipedia.org/wiki/Spline_interpolation

Splines yang berbeda memiliki karakteristik yang berbeda. Yang saya lihat paling umum digunakan adalah Akima dan Cubic splines.

Algoritme lain yang perlu dipertimbangkan adalah algoritma penyederhanaan garis Ramer-Douglas-Peucker, cukup umum digunakan dalam penyederhanaan data GPS. ( http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm )

Kembali ke Filter Kalman ... Saya menemukan implementasi C untuk filter Kalman untuk data GPS di sini: http://github.com/lacker/ikalman Saya belum mencobanya, tetapi tampaknya menjanjikan.

Dipetakan ke CoffeeScript jika ada yang tertarik. ** sunting -> maaf menggunakan backbone juga, tetapi Anda mendapatkan idenya.

Dimodifikasi sedikit untuk menerima suar dengan attrib

{latitude: item.lat, bujur: item.lng, tanggal: Tanggal baru (item.effective_at), akurasi: 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]

Saya telah mengubah kode Java dari @Stochastically ke 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
    }

    /// <summary>
    /// Kalman filter processing for lattitude and longitude
    /// /programming/1134579/smooth-gps-data/15657798#15657798
    /// </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>
    fun Process(lat_measurement: Double, lng_measurement: Double, accuracy: Float, TimeStamp_milliseconds: Long)
    {
        var accuracy = accuracy
        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

            val 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.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
        }
    }
}

Berikut ini adalah implementasi Javascript dari implementasi Java @ Stochastically untuk siapa pun yang membutuhkannya:

class GPSKalmanFilter {
  constructor (decay = 3) {
    this.decay = decay
    this.variance = -1
    this.minAccuracy = 1
  }

  process (lat, lng, accuracy, timestampInMs) {
    if (accuracy < this.minAccuracy) accuracy = this.minAccuracy

    if (this.variance < 0) {
      this.timestampInMs = timestampInMs
      this.lat = lat
      this.lng = lng
      this.variance = accuracy * accuracy
    } else {
      const timeIncMs = timestampInMs - this.timestampInMs

      if (timeIncMs > 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]
  }
}

Contoh penggunaan:

   const kalmanFilter = new GPSKalmanFilter()
   const updatedCoords = []

    for (let index = 0; index < coords.length; index++) {
      const { lat, lng, accuracy, timestampInMs } = coords[index]
      updatedCoords[index] = kalmanFilter.process(lat, lng, accuracy, timestampInMs)
    }