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

Mission Planner предоставляет два метода добавления меток GPS из полетных логов:

1. События камеры из данных логов хранящихся в памяти контроллераArduPilot может осуществлять спуск затвора камеры во время выполнения запрограммированных полетных заданий используя команды DO_DIGICAM_CONTROL или DO_SET_CAM_TRIGG_DIST. Передаваемые команды сохраняются в логах и могут быть применены для добавления точной информации о координатах конкретного снимка.
2. Временное смещение. Этот метод использует разницу во времени между внутренними часами камеры и системными часами для определения, где был сделан каждый снимок и получения информации GPS. Обычно пользователь должен самостоятельно подобрать приемлемое смещение. Этот метод менее точен и применяется, когда нет соединения между камерой и автопилотом.

Замечание.

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

Добавление координат GPS

Подготовительные действия.

Следующие действия зависят от метода, который вы выбрали — события камеры или временное смещение (CAM Messages или time offset).

События камеры

События камеры записываются в порядке определенным полетным заданием, при выполнении любой из команд управления затвором камеры (CAM_TRIGG_DISTANCE, DO_DIGICAM_CONTROL и др).

• Выберите метод CAM Message.
• Введите значение задержки спуска затвора камеры в миллисекундах, если вы ее знаете. Если не известна, оставьте 0.
• Проверьте, что смещение логов соответствует вашей версии логов. Обычно оно в порядке. Check that Log offsets are correct according to your log version (usually these are OK)
• Введите информацию о поле зрения FOV, если необходимо.
• Поставьте галачку напротив AMSL Alt, если вы хотите использовать абсолютную высоту.
• Нажмите Pre-process

Если подготовка выполнена правильно, вы увидите сообщение Done в конце области рабочих сообщений.

Замечание.

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

Разница во времени.

Совет.

Если вы еще не знаете, есть один полезный способ синхронизировать время камеры и системное время.

Если подготовительные операции пройдут успешно, вы появится сообщение Done.

Замечание

Наиболее частая проблема при использовании данного метода — это неточное значение разницы во времени. Запомните, что предполагаемая разница — это начальная точка всех вычислений.

В случае если утилита не обнаружит фото в логах автопилота — появится предупреждение, как на картинке ниже:

Финальным шагом является «проверка чистоты», а именно проверка предложенного положения фотографий используя кнопку Location Kml. Если предложенное местоположение не верно, добавьте или отнимите несколько секунд из Offset Time и повторите pre-process.

Основная пост обработка.

Дальнейшие действия направлены на проверку предложенного местоположения снимков и записи данных GPS в данные EXIF:

Снимки с метками GPS вы можете найти в папке geotagged внутри исходной папки.

Обзор интерфейса.

Экран утилиты Mission Planner Geo Ref Images показан на рисунке ниже:

Выбор файлов

Расчет разницы во времени и задержка затвора.

Разница во времени вычисляется путем сравнения времени первой фотографии и первого времени GPS в логах автопилота. Как только пользователь нажимает кнопку Estimate Offset, утилита вычислит разницу времени и выведет результат на экран в области служебных сообщений:

Offset Estimation = 1st_Picture_Time - 1st_GPS_Time_Logged

Замечание:

• Если выбран способ события камеры, доступно для редактирования значение задержки затвора Shutter Lag . Заметьте, что данные GPS обновляются с частотой 5Hz (для модуля 3DR GPS), таким образом они записываются каждые 200ms.
• Если задержка затвора меньше чем 100ms, тогда позиция GPS берется из текущего события камеры.
• Если задержка больше 100ms, позиция GPS берется в логах на 200ms раньше.

Коррекции в логах

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

Пример, как найти корректировки в линии события.

Давайте взглянем на формат линии GPS в начале лога:

FMT, 130, 45, GPS, BIHBcLLeeEefI, Status,TimeMS,Week,NSats,HDop,La6t,Lng,RelAlt,Alt,Spd,GCrs,VZ,T

Сначала необходимо найти перовое после слова определяющего единицы измерения.

В нашем случае, слово определяющее еденицу измерения — это BIHBcLLeeEefI. Таким образом первое поле — это Status

Отсюда получаем:

TimeMS = 2 Week = 3 Lat = 6 ...

Угол зрения и эталон высоты.

Здесь пользователь может указать угол зрения (FOV) и информацию об ориентации. Информация будет вставлена в результирующие файлы, но не будет храниться в данных EXIF.

Галочка AMSL Alt позволяет выбрать либо AGL Altitude (Высота над уровнем земли) или AMSL Altitude (Высота над уровнем моря).

Кнопки операций

• Pre-process — при нажатии этой кнопки программа будет пытаться получить и вычислить позиции снимков.
• Location Kml — после нажатия этой кнопки утилита откроет программу Google Earth и покажет положение фото на карте для проверки положения.
• GeoTag Images — если предыдущие шаги завершились успешно, нажатие данной кнопки запишит данные GPS в EXIF метки каждой фотографии.

Заказать создание ортофотопланов и 3D моделей местности, а также проведение фотограмметрии можно на нашем сайте

Идея записывать вместе с каждой фотографией координаты точки, в которой они сделаны, возникла еще на заре цифровой фотографии и была почти сразу реализована. Сегодня эта идея пришла в массы и обросла множеством сервисов. С самого начала возникла и сегодня продолжается реализация идеи на аппаратном уровне, когда GPS приемник прямо связывается с камерой, либо он в нее встроен, либо подсоединен к ней через последовательный порт, либо установлен на камеру и получает сигнал о том, что сделан снимок, от синхроконтакта вспышки. Sony выпустила также устройство GPS-CS1, которое записывает просто координаты каждые 15 с, а потом они синхронизуются по времени со сделанными снимками, и информация о координатах записывается в файле. Учитывая, что сегодня и GPS приемники, и камеры стали весьма распространенными и в повседневной жизни, возможно, вам и не придется покупать дополнительное устройство, можно воспользоваться уже имеющимся у вас GPS приемником и камерой, остается только привязать данные о координатах к конкретным снимкам. Раньше было существенное ограничение, связанное с тем, что память GPS навигатора переполнялась, и приходилось каждый день скачивать информацию в компьютер. Если вы снимали редко, а GPS использовался в навигации, то вполне вероятно, что, приехав из похода, вы сможете извлечь информацию только о последнем дне. Сейчас, когда у GPS навигаторов появилась возможность записывать пройденные пути на карты памяти, вопрос ее нехватки практически полностью снят. В Интернете можно найти несколько десятков программ, предназначенных для привязки фотографий к координатам. Более менее полный список можно найти и . Среди них есть и коммерческие, но большинство бесплатные и даже с открытыми исходными кодами. Я попытался попробовать многие их них, однако если по каким-то причинам программа сразу не начинала работать корректно, то я не пытался разобраться, а сразу переходил к следующей. Поэтому весьма вероятно, что среди тех программ, которые я отбраковал, есть и достойные, которые на другой конфигурации оборудования начнут работать сразу и без проблем. Коммерческие программы я тоже не рассматривал, поскольку их демонстрационные версии вносят умышленную ошибку около километра, и мне показалось неразумным тратить на них время при наличии большого количества открытых программ.

Кроме того, число рассматриваемых программ сократилось, поскольку у меня были достаточно специфические дополнительные требования. А именно: для записи координат использовался навигатор Etrex Venture Cx , который сохраняет данные о координатах в формате GPX (GPS Exchange Format). Формат стандартный, но выясняется, что фирма Garmin и некоторые создатели программ этот стандарт понимают по-разному. К счастью, есть универсальные программы, преобразующие один формат в другой. И среди них я бы выделил . В частности, в этой программе можно попросить преобразовать формат GPX, взятый из навигатора Garmin, в тот же самый формат, но результат этого преобразования будут понимать уже все программы.

Второе требование состояло в том, что мне хотелось сразу привязать фотографии в формате RAW, чтобы все полученные из исходных фотографии были уже с помеченными координатами, и не надо было бы снова определять координаты по времени, когда сделан снимок. Потому что с временем, как оказалось, существует довольно много проблем. И если их еще умножить тем, что преобразованные файлы сделаны и обработаны в разное время, и исходная информация времен снимка может быть потеряна или через некоторое время вы не сможете вспомнить, в каком часовом поясе вы снимали. Многие из рассмотренных мной программ имеют довольно изощренные настройки для коррекции возможных проблем с установкой времен. Тем не менее, лучше сразу настроить навигатор и камеру таким образом, чтобы этих проблем не возникало. У моего навигатора есть возможность выбрать способ записи трека - автоматический или через заданный интервал времени. В автоматическом режиме, если вы быстро перемещаетесь, то точек пишется много, если же стоите на месте, то они вообще не пишутся. Это позволяет получить запись пути одинаково качественно, передвигаетесь ли вы пешком, или едете на машине. Однако если вы долго снимаете с одной точки, то может создаться ситуация, когда в момент съемки GPS навигатор не записал координаты, поскольку они не отличались от записанных полчаса назад. Во многих программах можно задать интервал времени, в котором координаты считаются совпадающими со сделанным снимком. Однако отсутствие информации может означать не только то, что вы не перемещались, но и то, что сигнал от спутника был потерян. В этом случае, если интервал достаточно большой, то снимку могут быть приписаны координаты, существенно отличающиеся от истинных. Поэтому я рекомендую установить запись по времени с интервалом в 10 с. Если вы снимаете не из окна автобуса, то точность будет более чем достаточна.

Следующая глобальная проблема - это какое время устанавливать в камере. Если вы путешествуете, или делаете снимки осенью или весной, когда могут перевести время, то устанавливать в камере местное время мне кажется плохой идеей, тем более, что идея местного времени сегодня полностью дискредитирована. Солнце в зените над моим домом в Москве летом в 13 часов 15 минут. Сегодня средства транспорта позволяют перемещаться на многие тысячи километров, и разумнее использовать единое мировое время, а не объяснять, по какому времени и с учетом какого временного периода вы договаривались о встрече. Навигатор ведет протокол по времени UTC (Coordinated Universal Time). Поэтому это же время имеет смысл и выставить на камере и никогда не менять вне зависимости от переездов или времени года. Учитывая, что я записываю координаты с интервалом в 10 с, я предпочитаю называть это время по старинке GMT (Greenvich Meridium Time). Этот вариант более информативен, поскольку означает, что отсчет ведется от местного времени на меридиане Гринвича и при заданной мной точности не отличается от UTC. Зная свои собственные координаты и это время, вы всегда легко можете вычислить, когда же у вас солнце будет в наивысшей точке, то есть местный полдень. Вся эта информация для фотографа отнюдь не бесполезная, поскольку позволяет представить, откуда и куда будет падать свет в предполагаемой точке съемки. Все беды от наук, поэтому, вероятно, люди, обозвавшие утро полднем, стремились побыстрее отправить всех, кто учил в школе географию, в сумасшедший дом.

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

GPicSync

Для начальной пакетной обработки снятых фотографий я выбрал программу .

Спартанский графический интерфейс, работа только с папками, просмотр только JPEG, но свою задачу она выполняет и достаточно быстро. Отмечу, что есть довольно много программ, работающих из командной строки, которые могут поспорить с данной по аскетизму, но я не люблю работать с клавиатурой:-) Программа использует и . Распространяется по лицензии GPL. Есть версии для Windows и Linux. Поддерживается русский язык.

Работает она сразу с папками, позволяет пакетно преобразовывать сразу много фотографий, работает с RAW, понимает файлы GPX от Garmin, записывает координаты в EXIF , позволяет добавлять автоматически в ключевые слова IPTC ближайшие географические названия, которые она берет из баз данных в Интернете. Кроме того, что она записывает информацию о координатах в файлы фотографий, она также создает файл в формате KML или KMZ.

KML (Keyhole Markup Language - язык разметки Keyhole) - язык разметки на основе XML, служащий для представления трехмерных геопространственных данных в программе Google Earth, которая носила название «Keyhole» до её приобретения компанией Google. KMZ являются результатом сжатия KML-файлов ZIP-способом. Подробнее см .

Программа Google Earth распространяется бесплатно .

Если вы хотите в походных условиях (без быстрого интернета) сориентироваться, где же вы сделали снимки, их надо нанести на какую-нибудь карту, которая сохранена у вас в ноутбуке. Для этого можно воспользоваться вышеупомянутой программой GPS Babel и преобразовать в формат WPT для просмотра в программе или снова в формат GPX, но уже с включенными в него путевыми точками, отмечающими сделанные снимки, для просмотра в программе , т. е. нанести фотографии на ту самую карту, по которой вы ориентировались, когда пользовались своим GPS навигатором.

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

Эта программа написана на Java и, как следствие, одинаково легко запускается без переустановки и под Windows, и под Linux. Кроме того, она распространяется по лицензии GNU General Public License. Программа может все: работать с RAW файлами; просматривать их; записывать координаты в EXIF; просматривать положение фотографий на спутниковых снимках через программу Google Earth; добавлять географические названия в ключевые слова, пользуясь информацией с сайта . Чтобы добиться такой универсальности, программа использует внешние модули сторонних разработчиков, которые надо устанавливать отдельно: , .

Программа позволяет экспортировать фотографии не только в Google Earth, но и, не устанавливая дополнительных программ, контролировать положение точки съемки через .

Из минусов этой программы надо отметить, что она очень медленная, т. е. на подготовку просмотра фотографии в формате RAW может уйти около минуты, и без конвертации не понимает файлы Garmin. Программа используется для связи с GPS приемником а для конвертации файлов ее надо запускать отдельно. Некоторые географические названия могут быть вставлены кириллицей, что можно было бы только приветствовать, но некоторые программы просмотра отказываются работать с такими файлами:-(

Программа очень часто обновляется, так что есть надежда, что она будет совершенствоваться:-)

COPIKS PhotoMapper

Если работать только с файлами в формате JPEG и только под Windows, то неплохим выбором будет программа .

Она же весьма эффективно справляется с задачей упаковки ранее привязанных к координатам фотографий в формат KMZ. Можно посмотреть, как это выглядит, скачав файл в 500 КБ.

Locr GPS Photo

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

Удобна она и тем, что позволяет накладывать фотографии на космические снимки и карты, предоставленные разными компаниями. Можно выбирать между Google, Microsoft и YAHOO.

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

Удобным дополнением оказалась программа , которая позволяет редактировать координаты вручную, находить точку съемки в программе Google Earth по данным, записанным в EXIF, а также проводить обратную операцию - записывать координаты найденной на космическом снимке точки съемки в EXIF.

За последний год идея получила бурную поддержку в массах, и скоро любую точку земной поверхности можно будет увидеть не только из космоса, но и с уровня земли. Включив в Google Earth слой «География в интернете/Panoramio», вы увидите, что земля буквально усыпана пометками точек съемки, щелкнув по которым, можно увидеть фотографию.

" и зачем вообще она нужна?

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

Возьмём три примера.

1. Топографическая советская километровка (L-37-140) . ()

На этой карте сохранено зарамочное оформление. т.е. нам известны:

Координаты углов:

Система координат

Проекция

2. Есть топографическая карта, но поля обрезаны. Однако, сохранилась километровая сетка или рудименты (перекрестья) от неё.

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

Теперь нам важно определить прямоугольные координаты четырёх пересечений сетки. Для этого берём любую другую доступную нам карту на данный район с сеткой, пускай даже двухкилометровку. Привязываем её. Заходим в ози, меню - настройки - вкладка "Карты" - справа система координат - выбираем в выпадающем списке "пользовательская " - щелкаем на треугольник справа и вбиваем настройки такие же как указано . Теперь при наведении курсора мыши к перекрестью километровой сетки мы видим заветные цифры, которые нужно ввести в поле "пользовательские" при привязке нашей карты. Скорее всего подвести курсор точно к перекрестью не получится - не беда! Мы знаем, что прямоугольные координаты перекрестьев кратны 1000 - т.к. сетка километровая, т.е. можем смело округлять.

Повторяем хотя бы на четырёх максимально удалённых друг от друга пересеченьях.

3. Есть карта (в том числе старинная) - сетки нет ни километровой, ни градусной, либо она явно не совпадает с общепринятой или есть серьёзные сомнения в их достоверности или сетка есть, параметры датума и проекции неизвестны. В общем-то ЛЮБАЯ карта, хоть с пачки беломора.

Открваем её в любом удобном графическом редакторе.

Определяем на какую местность эта карта.

В ози открываем любые (максимально подробные) карты на эту же местность. Находим одинаковые объекты - в порядке уменьшения точности: церкви, отметки высот, ж/ д мосты, пересечения дорог (в т.ч. улиц), слияния рек. Ставим в ози "точки " на этих объектах. Необходимо найти не менее 4-х и не более 9 таких объектов.

Нажимаем меню "файл - загрузить и откалибровать карту" - выбираем нашу карту.

Проекцию ставим latitude\longitude, систему координат - WGS84.

Переходим на вкладку "точка 1", отмечаем на карте нужный объект и нажимаем на кнопку "ПТ" (или "WP") - выбираем из списка соответствующую точку и нажимаем "использовать точку" (use wp). Переходим на следующую вкладку и повторяем со всем списком.

Сохраняем полученный map файл.

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

Вы можете заказать

В разделе "GPS" - "GPS координаты" вы можете отслеживать все местоположения телефона за выбранный период времени: сутки, неделю, месяц или любой другой период, а также установить интервал между временем фиксации gps координат телефона. Все эти координаты отмечаются прямо на карте и соединяются линиями для визуального удобства при просмотре отчетов.

В разделе "Список GPS координат" отображаются координаты (широта, долгота и время) за все время. Справа в каждой строчке есть "Зеленая кнопка", при нажатии на которую откроется карта Google Maps c координатами местоположения телефона.

Вы также можете экспортировать список gps координат в файл CSV, PDF или Excel, сохранить на компьютер и распечатать, если это необходимо.

Отличная функция для родителей! Вы можете задать gps-зону, за которую телефон не должен выходить или, наоборот, в которую не должен входить. Например, вы можете задать gps координаты школы, в которой учится ваш ребенок, установить тип привязки "снаружи" и задать радиус gps привязки (например, 5 километров). Если телефон ребенка окажется за пределами вашего установленного ограничения, например, ребенок куда-то поедет или пойдет прогуливать занятия, вы получите email сообщение с оповещением об этом!

Аналогично, и обратное действие, вы можете установить gps-зону (тип привязки "внутри"), при посещении которой, вы получите email уведомление.

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

Местонахождение телефона по вышкам оператора

Бывают ситуации, когда GPS выключен в телефоне или абонент находится не в зоне покрытия GPS (редко, но бывает). В этом случае немного спасает информация о местонахождении телефона по вышкам оператора сотовой связи.

В разделе "GPS" - "Вышки (БС)" отображается следующая информация:
IMSI - международный идентификатор абонента мобильной сети. IMSI служит для уникальной идентификации абонента сотовой связи в пределах всего мира. По IMSI можно определить в какой стране и у какого оператора зарегистрирован абонент - есть несколько онлайн сервисов, например, www.numberingplans.com;
ID вышки - у каждой базовой станции оператора сотовой связи есть свой ID номер;
Имя оператора и код страны телефона абонента.

Если вы нажмете на "Зеленую кнопку" определения местоположения по вышке на карте, то скорее всего увидите следующее сообщение: GPS координаты БС не найдены.

В России, СНГ и многих других странах мира нет общей базы базовых станций с gps координатами! Так что эта функция в основном работает, если телефон был на территории США или некоторых стран Европы.

В разделе "GPS" - "Wi-Fi точки доступа" отображаются все wifi сети, которые использовались на телефоне (статус connected) или были обнаружены в зоне действия подключенной wifi сети.

Если вы нажмете на "Зеленую кнопку" определения местоположения по wifi на карте, то скорее всего увидите следующее сообщение: Невозможно определить GPS координаты запрошенной Wi-Fi точки доступа.

Единая база общественных wifi точек и их gps покрытие пока существует только в США и ряде стран центральной Европы. Если телефон находился на территории этих стран, то можете попробовать определить координаты.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Где
- это коэффициенты масштабирования, а - это расстояние от точки 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

Лев Драгунов, программист Карты@­Mail.ru