Геоинформационные системы постепенно входят в повседневный быт.

Большинство мобильных устройств снабжены GPS/ГЛОНАСС-приёмниками. Это позволяет разработчикам получать записи пути своих пользователей (треки). Треки можно использовать для решения целого ряда задач — от навигации по карте и информирования о местоположении друзей до построения пробок и предсказания дорожной ситуации.

К сожалению, без дополнительной обработки трек пользователя малоинформативен, поэтому требуется этап связи внешних данных и внутренней карты приложения. Для этого существуют специальные алгоритмы привязки данных (map matching algorithms).

Эта статья посвящена алгоритму привязки трека к дорожному графу и результатам его применения в проекте Карты@­mail.ru.

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

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

Рассмотрим самый простой вариант: направленный граф, у которого узлы — это перекрёстки, а рёбра — это дороги. Такое упрощение затрудняет проверку правил дорожного движения, но облегчает дальнейшие расчёты. Дороги с движением в обе стороны в подобном графе будут представлены парой рёбер. Ребро является неделимой единицей пути. Однако ребро — это математическое представление дороги. Реальное расположение дороги на карте (набор точек-координат дороги) будет определяться отдельным свойством этого ребра графа, которое назовём геометрией дороги.
Трек представляет собой упорядоченную последовательность точек, содержащих некоторую погрешность. Из-за этой погрешности точка практически никогда не будет лежать на ребре графа, к которому необходимо привязаться. По закону подлости для GPS-данных погрешность позиционирования меньше в чистом поле, чем в центре города. Другими словами, пришедшая точка может попасть на соседнее ребро.

Так выглядит одна Московская развязка глазами карт:

А вот так по ней, по версии навигаторов, едут наши пользователи:

Процесс привязки трека

Для привязки точки трека к графу в самом простом случае необходимо найти рёбра с минимальным расстоянием от ребра до точки. К сожалению, на практике (особенно в центре города) привязанный таким образом маршрут может оказаться набором несвязанных между собой рёбер. Для того чтобы улучшить качество привязки, будем считать, что трек — это упорядоченное целенаправленное движение пользователя по геометриям рёбер графа. То есть весь маршрут проходит по связанным друг с другом рёбрам. При этом на каждое ребро маршрута может приходиться как несколько точек трека, так и ни одной.

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

Существует множество факторов, которые при этом можно использовать:

1. Расстояние от точки до геометрии ребра графа. Оценивает как кратчайшее расстояние, так и вероятность того, что приёмник мог допустить такую ошибку.
2. Совпадение направлений движения. Оценивает угол между вектором движения транспортного средства и направлением участка геометрии ребра, к которому привязывается точка. (Данная мера устойчива к систематической погрешности GPS-приёмника, но подвержена случайной).
3. Изменение направления движения транспортного средства. Вероятность того, что автомобиль свернёт с главной дороги, в общем случае меньше, чем вероятность того, что он продолжит движение по ней (так минимизируется количество манёвров).
4. Физическая возможность перехода с одного ребра на другое (достижимость ребра). Адекватность скорости, с которой должен был двигаться автомобиль, чтобы совершить этот переход.

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

Для привязки треков в этой статье используем оценочную формулу для инкрементального алгоритма привязки данных (на основе работы S. Barcatsoulas [2]).

Эта формула включает две основных составляющих: и .

Составляющая учитывает взвешенное расстояние от точки трека до ребра и рассчитывается по формуле:

, где
— это коэффициенты масштабирования, а — это расстояние от точки p_i до геометрии ребра c_j.

Составляющая учитывает угол между направлением геометрии ребра и направлением трека:

, где
и — это коэффициенты масштабирования, а cos(α_i,j ) — это угол между геометрией i-того ребра графа и направлением движения по ребру трека
и — это параметры, влияющие на значимость составляющих. Для алгоритма важны значения этих параметров относительно друг друга — это определяет, какой из факторов будет иметь больший вес при сравнении.

Параметры и влияют на чувствительность к изменению описываемого фактора.

После расчёта составляющих итоговая метрика рассчитывается как:

Чем большее число получилось в итоге, тем лучше совпадение участка трека и ребра.

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

1. Выбрать все рёбра графа с геометрией, пересекающей дельта окрестность первой точки трека;
2. Оценить все выбранные рёбра с помощью формулы;
3. Выбрать ребро с наибольшей оценкой. Сделать его текущим и добавить его к готовому маршруту;
4. Если ближайшая к точке трека точка на геометрии ребра находится не на конце ребра, то выбрать следующую точку трека. (Если больше точек нет, то привязка закончена);
5. Выбрать все исходящие из текущего рёбра графа и текущее ребро;
6. Перейти к 2;

Стратегия учёта последующих точек

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

Немного про производительность

Задача привязки одного трека не является невероятно затратной, но на практике редко кто когда-либо привязывает пару треков. Как правило, необходимо успевать привязывать тысячи точек в секунду. Поэтому приходится искать компромисс между скоростью обработки и точностью привязки трека. В выбранном алгоритме на производительность влияет количество оцениваемых рёбер для каждой точки трека и глубина оценки точек «из будущего». Как показала практика, для принятия правильного решения о поведении на перекрёстках в большинстве случаев достаточно учитывать 2-3 последующие точки трека.

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

Итоги

Внедрение алгоритма привязки позволило проекту Карты@­Mail.ru не только начать работу с данными мобильных пользователей, но и быстро согласовывать собственные данные с произвольными системами. Использование новой подсистемы привязки позволяет в течение минуты на одном сервере пересчитывать на свой граф треки, суммарно содержащие до 55 тысяч точек. Благодаря этому отображение данных пользователям происходит максимально быстро. Алгоритм показывает качественную привязку даже при одной точке трека на три ребра внутреннего графа. Однако наибольшая эффективность описанного алгоритма достигается во время привязки длинных треков с одной-двумя точками на каждое ребро графа.

Литература по теме

1. “Map Matching. An Introduction” Prof. David Bernstein, James Madison university.
2. “On Map-Matching Vehicle tracking Data” Sotiris Bracatsoulas, Dieter Pfoser Randall Salas Carola Wank VLDB’05
3. “Approximate Map Matching with respect to the Frechet Distance” Daniel Chen, Anne Driemel, Leonidas J. Guibas, Andy Nguyen, Carola Wenk. Stanford. 2011