Map matching и обработка сырых данных GPS в промышленных масштабах

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


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



    Думаю, ни для кого не секрет, что на рынке есть решения, которые предоставляют сервис Map matching. Он выполняет обработку координат и в результате выдает координаты, привязанные к дороге. Однако, ни один сервис не будет понимать специфику ваших данных, а результат обработки сырых данных может быть не самым лучшим. В связи с этим нами было разработано решение, которое позволило максимально отфильтровать и наложить на дороги данные с датчиков.


    Входные данные


    На момент начала разработки OBD-донгл передавал на сервер телематические данные в виде точек, у каждой из которых были следующие параметры:


    • Координаты, полученные с GPS сенсора;
    • Скорость, полученная от автомобиля;
    • Обороты двигателя, полученные от автомобиля;
    • Время конкретной точки.

    Точки передавались по следующему алгоритму – раз в 3 секунды или каждые 20 метров. Отметим, что алгоритм передачи не идеальный, но в рамках конкретной проблемы мы решили его не менять, т.к. очевидно, что если передавать точки по более совершенному алгоритму, то результат работы только улучшится. Также донгл собирал такие данные как: heading (вектор движения) и dilution of precision (грубо говоря, точность GPS), однако на сервер эти данные не передавались.


    Алгоритм


    Алгоритм, который мы применяли, можно разделить на две части:


    • Фильтрация данных;
    • Map matching;
    • Частичная обработка.

    Фильтрация


    Никто не знает специфику ваших данных лучше, чем вы сами. Мы решили воспользоваться нашими знаниями и сделать фильтрацию данных на стороне собственного сервиса. Давайте рассмотрим простой пример маршрута:



    На графике отображены скорость машины, полученная донглом от автомобиля, и скорость, подсчитанная из GPS. Как видно, на графике есть много выбросов — как в большую, так и в меньшую стороны. Сразу на ум приходят стандартные алгоритмы фильтрации: фильтр Калмана, alpha-beta filter. За них мы и взялись в первую очередь. Однако, подобные фильтры показали себя не с лучшей стороны. На то было несколько причин: низкая частота и абсолютная разнородность данных (сложно подобрать единый модифицированный алгоритм с подходящей погрешностью), наличие трансформаций входящих данных было неприемлемо. Куда лучше в ходе тестирования себя показал очень простой линейный фильтр скорости. Суть алгоритма очень проста: для всех соседних точек вычисляем скорость по GPS и сравниваем с скоростью, полученной от автомобиля, и если отличия выше, чем допустимая погрешность, то выкидываем одну из точек.


    Вот псевдокод:


    `for i in range(1, len(data)):
       velocity_gps = calc_dist(data[i - 1].lat, data[i - 1].lon, data[i].lat, data[i].lon) / (data[i] - data[i - 1])
       velocity_vehicle = (data[i - 1].speed + data[i].speed) / 2
       relative_error = abs(velocity_gps - velocity_vehicle) / (velocity_vehicle)
       if relative_error > 1.5:
          data.remove(data[i])`

    В результате фильтрации, получаем данные без выбросов, при этом, точки по-прежнему не ложатся на дорогу. Однако перед процедурой Map matching стоит еще проредить наши данные, т.к. нет смысла передавать 10 точек, лежащих на одной прямой, когда для определения прямой достаточно двух точек. Тем не менее не надо усердствовать с фильтрацией, ибо сервис Map matching может посчитать наши данные шумом. Для удаления лишних точек мы пользовались алгоритмом Ramer-Douglas-Peucker, а точнее его немного модифицированной версией.



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


    Map matching


    Ввиду того, что карты для наших мобильных приложений и порталов предоставлены сервисом Mapbox, было решено пользоваться их сервисом Map matching. Но мы сразу столкнулись с ограничением — 100 точек в запросе. Даже с учетом фильтрации и уменьшения числа точек алгоритмом RDP среднее число на наших маршрутах получается — 250 точек. Соответственно, нам нужно обрабатывать батчами (batch), плюс ко всему внахлест, т.к. в некоторых случаях при простом батчинге будут происходить ошибки обработки. Алгоритм батчинга следующий:


    • N — число точек для обработки внахлест;
    • Нарезаем роут на батчи размером не более 100-N;


    • Затем обрабатываем первый батч;
    • Берем последние N точек обработанных данных и второй батч;
    • Продолжаем до последнего батча;


    • Конечный результат состоит из Processed1, Processed2, Processed3, Processed4.


    Следующей проблемой, с которой мы столкнулись, было определение точности данных. API Mapbox требует указывать точность передаваемых данных, несмотря на то, что в документе этот параметр указан как опциональный. И если его не передавать, он будет выставляться из дефолтного значения. Параметр, отвечающий за точность — gps_precision. Вот что говорится о нем в документации:


    An integer in meters indicating the assumed precision of the used tracking device. Use higher numbers (5-10) for noisy traces and lower numbers (1-3) for clean traces. The default value is 4.


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



    Для выявления подобных случаев хорошо подходит алгоритм DTW. В результате обработки 1000 маршрутов и сравнения результатов работы с помощью алгоритма DTW, стало ясно, что лучшие результаты получаются с значениями precision 3, 6, 10 (в разных случаях).
    В итоге, в отсутствии данных с GPS о точности, мы запустили обработку параллельно с тремя различными gps_precision (3,6,10), а затем выбрали лучший из них. Также было запланировано добавление отправки с донгла параметра dilution, что позволило сильно улучшить качество работы сервиса.


    Частичная обработка


    Конечные точки маршрутов часто бывают в местах, где дорога на карте не обозначена (парковки, пути между домами и т.д.). Алгоритмы Map matching в таких ситуациях работают не очень хорошо, и хотелось бы максимально точно указывать, где пользователь оставил свое авто. Для решения этой проблемы мы стали производить цикл обработки не всего маршрута, а только внутренних точек: отбрасываем начало и конец маршрута, затем к обработанным данным добавляем начало и конец оригинального маршрута. Начало и конец определяем следующим образом: берем 5% маршрута либо часть до того, как скорость авто станет больше 10км/ч.


    Конечный результат


    В конце хотелось бы продемонстрировать результат процессинга маршрутов. В результате маршруты проходят почти везде по дорогам, сильные шумы исчезли, пропущенные куски маршрутов были восстановлены (езда по кольцу или мосту).




    Автор: Кирилл Кульченков, kulchenkov32, Senior Software Developer, Bright Box.

    • +20
    • 5.6k
    • 6
    Bright Box
    0.00
    Company
    Share post

    Comments 6

      0
      XIII район Будапешта — ооочень густо застроенная местность, покрытие GPS неравномерное. Хороший результат для таких условий!
        0
        Тут стоит упомянуть, что за API Mapbox стоит опенсорсный движок OSRM, в котором можно в конфигурации выключить ограничение в 100 точек, если не полениться развернуть его на своём сервере.

        Кстати, год назад ваш подход бы совсем не работал — изменение, которое позволяет передавать в OSRM трек одиночный, в котором есть неравномерные провалы во времени (а у вас они есть, вы ведь используете двумерное упрощение Дугласа-Пойкера вместо фильтрации), закоммитил хабраюзер Gard github.com/Project-OSRM/osrm-backend/pull/3815

        С погрешностью всё довольно просто — она внутри преобразуется в радиус поиска дороги-кандидата, больше значение gps_precision — медленнее обработка, но более разнообразные варианты могут быть восстановлены. В коде радиус просто множится на три, и если этого значения нет совсем, его можно прикинуть по карте — взять типичное расстояние между двумя параллельными дорогами в вашей местности и поделить его на три. Ребята из lyft нашли регрессией более оптимальную формулу для нахождения радиуса, по своим данным — github.com/Project-OSRM/osrm-backend/pull/3184 — но оказалось, что с такой формулой перестаёт работать мапматчинг у тех, кто не озаботился передачей настоящего значения accuracy и придумывает его сам, как у вас.

        Так и живём.
          0
          Привет. Действительно на версии 4 и меньше прогон данных через Rpd мог ухудшить результат, мы в тот момент добавляли точки на полученные отрезки для создания равномерных данных.
          С выбором точности все сильно упрощается, когда есть DOP или HDOP плюс информация о модуле GPS(какой именно установлен модуль) достаточно для определения радиуса поиска.
          По поводу 100 точек все сложно, Mapbox отказывается снимать ограничение, а свои сервера для этих задач держать нам не то чтобы выгодно.
            0
            DOP уже достаточно давно неактуален как значение, android и ios склонили рынок к тому, что теперь сами чипы прямо в NMEA-потоке репортят accuracy именно в том виде, в котором ожидает OSRM — как минимум на подопытном MTK в составе ZTE мы это наблюдали.

            Решали ли вы, и решили ли, проблему систематической погрешности в gps, когда приёмник репортит координаты с отличной относительной, но ужасной абсолютной погрешностью? У нас в данных довольно частая история — трек идеально повторяет контуры дороги, но в пятистах метрах от неё, за пределами всех радиусов для мап-матчинга.

            А вы живёте на Free Tier в Mapbox, или у вас почти нет трафика? Для коммерческих клиентов они не стесняются делать кастомные решения.
              0
              DOP уже достаточно давно неактуален как значение, android и ios склонили рынок к тому, что теперь сами чипы прямо в NMEA-потоке репортят accuracy именно в том виде, в котором ожидает OSRM — как минимум на подопытном MTK в составе ZTE мы это наблюдали.

              У нас координаты берутся не с телефона, а блочка(донгла), который вставляется в автомобиль, есть устройства, которые уже несколько лет установлены, соответсвено прошивка модема в них не позволяет достать подобные данные.
              Решали ли вы, и решили ли, проблему систематической погрешности в gps, когда приёмник репортит координаты с отличной относительной, но ужасной абсолютной погрешностью? У нас в данных довольно частая история — трек идеально повторяет контуры дороги, но в пятистах метрах от неё, за пределами всех радиусов для мап-матчинга.

              Мы подобную проблему пока не решали. У нас достаточно интересная специфика GPS-треков. Большенство из них короткие(100-500 точек, точка +- раз в 3 сек), плюс после маршрута GPS выключается(экономия энергии), т.е. 1 маршрут обычнро проходит на одной пачке спутников и поиск происходит в начале поездки. Погрешностей как у вас в 500 метров мы не наблюдаем, максимум несколько метров.
              А вы живёте на Free Tier в Mapbox, или у вас почти нет трафика? Для коммерческих клиентов они не стесняются делать кастомные решения.

              У нас с ними контракт и большое количество запросов, почему они уперлись в 100 точек, я не знаю.
          +1
          Погрешность GPS сенсора определяется погрешностью самого датчика и такими факторами как: ландшафт, скорость движения, количество и положение спутников.

          Ну если лень почитать даже википедию, то придется объяснять на уровне детского сада. И так, погрешности делятся на шумовые и систематику. Шумовые — это те самые случайные погрешности, которые вы фильтруете.

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

          Систематика эфемерид GPS иная — скачок в момент смены эфемерид и нарастающая в течении 2 часов систематика.

          Ну и так далее и так далее…

          А вывод прост. После вычищения шума стоит выделить соседние точки, проанализировать
          систематическое смещение куска и свинуть точки с его учетом. При этом короткая систематика (менее 15 минут) всего одна — многолучевой прием. Все остальные систематики длинные.

          Only users with full accounts can post comments. Log in, please.