Фильтр ошибок GPS датчиков

без фильтра

с фильтром

Fork me on Github

или

Документация и Теория

Зачем нужен фильтр?

Устали от «лишних» километров из за GPS в приложении такси?

Постоянные «скачки» GPS в приложении для учета передвижения курьеров?

Есть потребность в точном трекинге в любом on-demand сервисе?

Решение - Mad Location Manager

Fork me on Github

Что умеет Mad Location Manager?

Уменьшает ошибки трекинга маршрута

Исключает резкие «скачки» координат в точки, удаленные от реального маршрута

Позволяет сделать плавным движение объектов на карте

Уменьшает шумы с датчиков телефонов низкого класса

Фильтрует ошибки при кратковременной потере GPS сигнала

И другие задачи, связанные с доставкой и трекингом движущихся объектов на карте

Как работает?

Как работает?

Для реализации задачи нам необходимы данные с трех датчиков:

Магнитометр

Этот датчик помогает определить, где север

Акселерометр

Используется для определения ускорения тела и угла наклона

Гироскоп

Позволяет найти текущее положение объекта, зная начальное положение устройства и проинтегрировав показания гироскопа

Самым простым и удобным оказались виртуальные датчики Android

У нас есть вектор ускорения в «абсолютной» системе координат поэтому можно приступать к реализации фильтра Калмана

Виртуальные датчики Android

Чтобы определить ускорение, можно воспользоваться датчиком LINEAR_ACCELEROMETER, который выдает ускорения относительно осей телефона. Для определения ориентации в пространстве можно использовать ROTATION_VECTOR

Фильтр Калмана

Определяем вектор состояния системы, матрицу перехода, управляющий вектор и прочие компоненты фильтра Калмана. Определяем ковариационные матрицы шума процесса и шума измерений. В такой форме довольно легко расширить фильтр

А если коротко…

Параметры фильтра

Определяемся с типами матриц

Вектор состояния системы

Матрица эволюции системы

Матрица управления

Вектор управления

Матрица измерений равна единичной матрице

Реализовываем несколько операций с матрицами

Матрица измерений равна единичной матрице, если GPS -приемник предоставляет информацию о скорости. Если же GPS-приемник предоставляет только координаты, то матрица примет такой вид:

рис. 1

Второй вариант показывает лучший результат при кратковременной потере GPS сигнала, потому что на вектор состояния не влияет последняя полученная от приёмника скорость.

рис. 2 Ковариационная матрица шума измерений

Если GPS приемник не предоставляет информацию о скорости объекта. В противном случае:

рис. 3

Можно распарсить NMEA сообщение и использовать компонент HDOP, можно использовать класс Location и метод getAccuracy(). Чтобы получить скорость в нашей системе координат необходимо получить направление. Это либо компонент course в NMEA сообщении, либо bearing из объекта Location.

Рис. 4 Ковариационная матрица шума процесса

Из-за интегрирования показаний акселерометра ошибка позиционирования, связанная с акселерометром, будет увеличиваться с течением времени. Соответственно, мы должны будем меньше полагаться на данные акселерометра и, в конечном итоге, должны будем принять координату от GPS приемника, а не от акселерометра. Dt — время между двумя шагами update (между получением GPS координат) фильтра Калмана.

Чтобы фильтр Калмана работал, нужно привести все данные к единой системе координат.

GeoHash

Алгоритм для преобразования двух координат вида 42.8795949 (долгота), 74.5998444 (широта) в одну строку

В данном проекте используется для решения двух проблем. Во-первых, необходимо как-то объединить находящиеся рядом точки, чтоб снизить поток избыточной информации. Для этого можно выбрать какой-нибудь радиус и объединять все точки, попадающие в окружность с этим радиусом. Но как выбрать радиус и центр этой окружности? Вычисление расстояния в сферических координатах — дорогостоящая операция, поэтому была использована geohash функция, которая позволяет очень быстро определить, относятся ли точки к одной области или нет. Эта функция выдает хэш в виде строки, длина которой определяется пользователем и влияет на точность кодирования. Чем больше длина хэша, тем меньше область и больше точность координат в одной области. Максимальная возможная длина геохэш-строки — 12 символов. Очень хороший результат показывает длина хэша 7 или 8 символов.

Ещё одно применение этой функции

Определение и фильтрация «скачков». Мы будем считать, что если GPS приемник выдал подряд больше трех (параметр задается пользователем) координат с одним хэшем, то эта точка правильная и её нужно учитывать. Если же меньше — то, вероятно, это какое-то случайное значение, которое не нужно учитывать.

Маршрут без применения фильтра, основанного на GeoHash

Маршрут с применением фильтра на основе GeoHash. Длина строки (precision) — 8. Минимальное количество точек с одним геохэшем — 2

Маршрут с применением фильтра на основе GeoHash. Длина строки (precision) — 7. Минимальное количество точек с одним геохэшем — 3

Как видно из приведенных примеров, GeoHash фильтр позволяет значительно сократить количество обрабатываемых точек. Это может быть критичным, если координаты обрабатываются сервером или если планируется сохранять маршруты в базе данных.

Результат работы, вывод и дальнейшие улучшения

В результате был написан Android модуль и библиотека на C, реализующие все вышеперечисленный фильтры. Визуально тракетории стали более сглаженными и исчезло накручивание дистанции при отсутствии движения. Как следствие — улучшился подсчет пройденной дистанции.

Красные точки — координаты GPS, а синие — результат работы фильтра. Как видно была небольшая потеря связи с GPS, но траектория успешно восстановлена

Зелёная линия - сильно зашумленные данные GPS. Красный - результат фильтрации (сначала Калман, затем на основе GeoHash).

Для подсчета дистанции использовались два алгоритма. Один из них — алгоритм Винченти. Он используется внутри метода distanceBetween() класса Location. Второй метод: https://en.wikipedia.org/wiki/Great-circle_distance (раздел с haversine формулой). Тесты показывают, что результат почти не отличается. Притом, второй вариант затрачивает намного меньше ресурсов. Однако есть подозрение, что на больших дистанциях погрешность будет больше. Тем не менее, в пределах города второй алгоритм показывает такой же результат, как и первый.