Привет, меня зовут Сергей и я разработчик в команде мобильного бэкенда в компании ATI.SU. Не так давно в мою жизнь пришла задача. В ней нужно было принять координаты от приложения на Android и отобразить их на карте.

В разных приложениях мы каждый день видим красивые маршруты из разряда "где везут мою шаверму" или "как я пробежал по парку маршрут в виде котика", но если просто соединить линиями точки, которые приходят от телефона, то мы увидим что-то вдохновленное произведением Fatboy Slim - Ya Mama. Как превратить исходные данные в красивую картинку, разберемся в статье.

Первая цель, которую мы преследуем — избавиться от визуального шума.

Вторая цель - сократить количество точек, чтобы ускорить время отрисовки самой карты на фронте.

Требования:

• сократить количество точек,

• свести к минимуму количество выбросов,

• допустимы потери точности.

Исходные данные — набор координат от приложения на Android

Как это выглядит сейчас:

Что хотим получить:

Я засучил рукава и кинулся изучать, что же уже реализовано, и что можно добавить.

Примерно в то же время с алиэкспресса приехал станок для заточки ножей с камнями различной зернистости. Оказалось, что у заточки ножа много общего с фильтрацией GPS-координат.

Фильтр точности

Что же можно сделать в начале. Заточку ножа мы начинаем на самом грубом камне. Аналогично поступим с координатами. Так как данные приходят с приложения на Android, мы вместе с координатами получаем параметр accuracy. Согласно спецификации параметр означает, что с вероятностью 68% точка лежит в окружности с радиусом, равном значению accuracy.

Фильтрация по точности позволяет исключить те точки, которые априори считаются выбросами. Тестовый маршрут сократился в 7 раз при значении accuracy 10.

Но все не так просто. Такую точность может выдать далеко не каждое устройство. Поэтому важно подобрать такое значение accuracy, которое позволит отфильтровать данные с высокой погрешностью, но одновременно с этим не отбросит маршруты, полученные с менее точных устройств.

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

Реализация этого фильтра тривиальна и заключается в отсеивании всех точек, точность которых нас не устраивает.

Фильтры скорости

После такой грубой заточки перейдем к тонким настройкам и возьмем следующие камни.

Так как есть данные о времени получения и координаты предыдущих точек, то никто не запретит использовать фильтр по скорости. Остается установить, насколько быстро может передвигаться наш протеже, а все, что выходит за рамки, помечаем как выбросы.

Узнать скорость водителя можно, использовав средства мобильной платформы, либо вычислить на основе полученных GPS данных. Формула расчета скорости известна со школьной программы. Однако, следует учесть, что работая с координатами мы имеем дело не с прямыми, а c дугами на земном сфероиде. Метод расчета расстояния между двумя координатами должен это учитывать.

Формула расчета углового расстояния между объектами для учета небольших расстояний:

Листинг метода расчета расстояния с переменными из формулы:

double rad = 0.0174532925199433; //значение градуса в радианах
double earthRadius = 6376500.0; //усредненное значение радиуса Земли
public double GetDistanceTo(GeoCoordinate from, GeoCoordinate to)
{
  double a1 = from.Latitude * rad; //значение координаты в радианах
  double b1 = from.Longitude * rad;
  double a2 = to.Latitude * rad;
  double b2 = to.Longitude * rad;
  double d3 = Math.Pow(Math.Sin((a2 - a1) / 2.0), 2.0) + Math.Cos(a2) * Math.Cos(a1) * Math.Pow(Math.Sin((b2-b1) / 2.0), 2.0); // угловое расстояние
  return 2.0 * earthRadius * Math.Asin(d3);
}

Остается установить, насколько быстро может передвигаться объект, а все, что выходит за рамки, помечаем как выбросы. Работая исключительно с грузовиками, мы исключаем участки маршрута, на которых автомобиль движется > 150 км/ч. Но этот лимит можно при желании смело уменьшить: если водитель превышает эту скорость, то, вероятнее всего, движется по прямой и при отображении карты такие точки соединятся, образуя прямую на трассе.

Фильтр ускорения

Зная скорость, мы можем посчитать ускорение. Напомню формулу:

Для того чтобы определиться с максимально возможным ускорением объекта, можно обратиться к статистике. В нашем случае, нам следует найти информацию о максимальном ускорении грузовика. Например, КАМАЗ Liebherr разгоняется от 0 до 100 км/ч=27,78 м/с за 10 с. Следовательно, максимально возможное ускорение =2,78 м/c^2. Это слишком большая величина, чтобы откидывать точки реальных пользователей, но для фильтрации грубых выбросов нам этого достаточно.

Сворачивание точек

Зачастую бывает, что в поездке водителю приходится остановиться. В этот момент продолжается сбор координат, и на нефильтрованной карте наблюдается жуткое метание вокруг одной точки.

Такие точки мы можем свернуть в одну. Эмпирическим путем мы пришли к алгоритму, в котором схлопываем все точки, находящиеся в радиусе 5 метров и разбросанные по времени не больше, чем на 60 секунд (помним, что водитель может возвращаться обратно той же дорогой, поэтому важно учитывать время, прошедшее между съемом координат).

Для примера, рассмотрим небольшой маршрут, где водитель вышел из машины и отправился куда-либо пешком.

Наш пользователь благополучно перешел проспект Ленина и некоторое время стоял на месте. Если отсеять все его точки, когда он крутился вокруг одной точки, то получим следующую картину. Из 100 точек оригинального маршрута осталось 42.

Но открытым остается вопрос, что же его завело в прокуратуру?

Медианный фильтр

И вот приближаемся к финишным заточкам. Точки, которые остались после предыдущих фильтраций, сглаживаем, применив медианный фильтр.

К достоинствам медианного фильтра относится то, что он довольно прост в реализации и хорошо нивелирует единичные выбросы.

Однако не стоит забывать и о недостатках медианного фильтра. Так, резкие изменения направления движения могут оказаться сглаженными.

Принцип медианного фильтра:

1. выбираем размер отрезка, который будем наполнять полученными значениями;

2. заполняем этот отрезок значениями широты и долготы, полученных координат;

3. сортируем значения для широты и долготы;

4. для каждого нового значения координаты мы ищем медиану по значению составляющих координаты относительно соседей;

5. смещаем значения в отрезке путем добавления следующей координаты.

Возьмем часть предыдущего маршрута и применим медианный фильтр.

Легко заметить, то в нашем случае фильтр сглаживает полученные значения. Если провести аналогию с заточкой, то медианный фильтр — мусат, которым выправляют заточку лезвия ножа.

Теперь заметно, что в прокуратуру наблюдаемый не заходил. Можно только за него порадоваться.

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

Самым известным алгоритмом фильтрации координат является фильтр Калмана. Этому фильтру уже посвящен сайт. Про него регулярно выходят статьи. Так что не будем вдаваться в подробности и вспомним основные принципы.

Алгоритм работает в два этапа:

• прогнозирование — просчитываются переменные состояния и неопределенности;

• коррекция — полученные результаты уточняются благодаря спрогнозированным результатам.

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

Однако на некоторых Android-устройствах координаты уже обрабатываются этим фильтром, так что применения фильтра Калмана можно заменить фильтрацией выбросов и сжатием точек простоя.

Алгоритм Рамера — Дугласа — Пекера

На случай если у вас уже есть завершенный маршрут и вы хотите сократить в нем количество точек, то можно воспользоваться реализацией алгоритма Рамера-Дугласа-Пекера. Смысл его сводится к тому, что по заданной кривой мы строим прямую, аппроксимирующую данную, с меньшим количеством точек, учитывая значение точности.

Выглядит это примерно вот так:

Так как конечный маршрут не известен, то в нашем случае применение данного алгоритма не целесообразно, но возможно для вашего проекта это именно то, чего вам не хватало.

function DouglasPeucker(PointList[], epsilon)
        // проводим прямую между границами отрезка
        //ищем все значения перпендикуляров от точек до прямой
    dmax = 0
    index = 0
    end = length(PointList)
    for i = 2 to (end - 1) {
        d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end])) 
        if (d > dmax) {
            index = i
            dmax = d
        }
    }
    
ResultList[] = empty;
//если точка, максимально удаленная от перпендикуляра, больше значения точности
    //рекурсивно вызываем функцию на 2 образовавшихся отрезках
if (dmax >= epsilon) {
    recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
    recResults2[] = DouglasPeucker(PointList[index...end], epsilon)

    //составляем результат
    ResultList[] = {recResults1[1...length(recResults1) - 1], recResults2[1...length(recResults2)]}
} else {
    ResultList[] = {PointList[1], PointList[end]}
}
return ResultList[]

end

Финальный этап

Настало время проверять заточку нашего ножа. В теории он должен резать волос вдоль, как в лучших японских фильмах.

В итоге имеем фильтрованный маршрут. Количество точек сократилось с 5000 до 932.

Применив описанные методы, получили требуемый результат. Сократили количество точек маршрута, убрали выраженные шумы. Конечно мы потеряли в точности отображения маршрута, но по текущим требованиям данные допуски являются нормальными.

Вывод

Применив простой набор фильтров, получилось сократить количество данных для передачи и улучшить визуальное качество маршрута.

Но все ли так хорошо?

К сожалению, даже если вы успешно заточили один нож, то это не значит, что остальные заточатся с тем же успехом.

Описанные в статье фильтры и их параметры подходят для решения наших задач, но в иных случаях могут совсем ломать ваш маршрут или не давать ощутимых результатов. При выборе фильтра требуется понимать, что нужно получить в итоге, и подбирать параметры в зависимости от ваших задач. Кому-то достаточно картошку порезать, а кому-то нарезать дорогущего лосося.

Но если вы еще не определились с задачами, то почему бы и не начать с этих фильтров?

Список источников.

https://ru.wikipedia.org/wiki/Медианный_фильтр

https://habr.com/ru/post/166693/

https://habr.com/ru/post/140274/

https://gist.github.com/glebov21/011f338e037124553217abfda531d1e7

https://www.researchgate.net/publication/332726900_A_Fast_Trajectory_Filtering_Method_for_Massive_GPS_Data_Based_on_Neighboring_Points

https://www.sciencedirect.com/science/article/pii/S1877050916304872

https://www.kalmanfilter.net/default.aspx

https://en.wikipedia.org/wiki/Ramer–Douglas–Peucker_algorithm

https://www.youtube.com/watch?v=EOoSJPuD-dc