Сопоставление карт
Сопоставление карт — это проблема сопоставления записанных географических координат с логической моделью реального мира, обычно с использованием той или иной формы географической информационной системы . Самый распространенный подход заключается в том, чтобы взять записанные последовательные точки местоположения (например, по данным GPS ) и связать их с ребрами существующего графа улиц (сети), обычно в виде отсортированного списка, представляющего путешествие пользователя или транспортного средства. Сопоставление наблюдений с логической моделью таким образом находит применение в спутниковой навигации , GPS-отслеживании грузов и транспортном машиностроении .
Алгоритмы сопоставления карт можно разделить на алгоритмы реального времени и автономные. Алгоритмы реального времени связывают положение во время процесса записи с дорожной сетью. Автономные алгоритмы используются после записи данных и затем сопоставляются с дорожной сетью. [1] Приложения реального времени могут рассчитывать только на основе точек до заданного времени (в отличие от точек всего путешествия), но предназначены для использования в «живых» средах. Это приводит к компромиссу между производительностью и точностью. Автономные приложения могут учитывать все точки зрения и поэтому допускают снижение производительности в пользу точности. Однако дефекты низкой точности можно уменьшить за счет интеграции пространственно-временной близости и улучшенных алгоритмов взвешенного круга. [2]
Примеры и варианты использования
[ редактировать ]Применение алгоритмов сопоставления карт варьируется от непосредственного и практического, например, приложений, предназначенных для сопровождения путешественников, до аналитического, например, создания подробных входных данных для моделей анализа дорожного движения и тому подобного.
Вероятно, наиболее распространенное использование сопоставления карт — это когда у путешественника есть мобильный компьютер, указывающий ему или ей направление через уличную сеть. Чтобы давать точные указания, устройство должно точно знать, где в уличной сети находится пользователь. Однако определение местоположения по GPS имеет ошибку позиционирования, поэтому выбор ближайшего сегмента улицы и прокладывание маршрута оттуда, скорее всего, не сработает. Вместо этого история местоположений, сообщаемая GPS, может использоваться для угадывания вероятного маршрута и более точного определения текущего местоположения.
Другие применения, более аналитические по своей природе, включают:
- извлечение информации о дорожном движении из GPS-треков транспортных средств
- связывание атрибутов, сообщаемых пользователем, с улицей
- автоматически определять ограничения поворота на основе анализа нескольких GPS-треков
Есть и другие примеры [3] и эта тема все еще находится в стадии активных исследований и разработок. [4] [5] [6] [7]
Подходы
[ редактировать ]Геометрический подход
[ редактировать ]Самый ранний подход к решению проблемы сопоставления карт, основанный на сходстве кривой точек и кривой дороги. [8]
Топологический подход
[ редактировать ]Сопоставление топологических карт выравнивает точки GPS с дорожной сетью, учитывая связность и взаимосвязи между сегментами дорог. Он учитывает структуру сети, ограничения пути и последовательность точек GPS, чтобы обеспечить точное и реалистичное сопоставление маршрутов, особенно в сложных средах.
Расширенный подход
[ редактировать ]Усовершенствованные алгоритмы сопоставления карт, в том числе основанные на нечеткой логике, скрытых моделях Маркова (HMM) и фильтрах Калмана, значительно повышают точность оценки местоположения точек GPS. Однако достижение такого уровня точности часто требует значительного времени обработки. [9]
Скрытые марковские модели
[ редактировать ]Сопоставление карт описывается как скрытая марковская модель , где вероятность выброса представляет собой уверенность в принадлежности точки одному сегменту, а вероятность перехода представлена как возможность перемещения точки из одного сегмента в другой в течение заданного времени. [10] [11]
Выполнение
[ редактировать ]Сопоставление карт реализовано в различных программах, [12] [13] включая с открытым исходным кодом механизмы маршрутизации GraphHopper и Open Source Routing Machine . [14] Он также включен во множество проприетарных программ и приложений для картографирования/маршрутизации.
Ссылки
[ редактировать ]- ^ ПЕРЕЙРА, Франсиско Камара; КОСТА, Хьюго; Перейра, Нуну Мартиньо (11 сентября 2009 г.). «Алгоритм сопоставления автономных карт для неполных картографических баз данных» . Европейский обзор транспортных исследований . 1 (3): 107–124. Бибкод : 2009ETRR....1..107P . дои : 10.1007/s12544-009-0013-6 . hdl : 10316/102766 . S2CID 56046090 . Проверено 23 ноября 2014 г.
- ^ Тэн, Вэньсинь; Ван, Яньхуэй (8 июля 2019 г.). «Сопоставление карт в реальном времени: новый алгоритм, объединяющий пространственно-временную близость и улучшенный взвешенный круг» . Открытые геолого-геофизические исследования . 11 (1): 288–297. Бибкод : 2019OGeo...11...23T . дои : 10.1515/geo-2019-0023 .
- ^ Бракацулас, Сотирис; Пфозер, Дитер; Венк, Карола и Салас, Рэндалл (2 сентября 2005 г.). «О сопоставлении данных отслеживания транспортных средств с картой» (PowerPoint) . Учеб. Конференция ВЛДБ 2005.
- ^ Инь Лу; Юй Чжэн; Син Вэй Ван и Ян Хуан (4 ноября 2009 г.). карт для GPS-траекторий с низкой частотой дискретизации» . Сопоставление «
- ^ Маршал; Хакни; Аксхаузен (июль 2004 г.). «Эффективное сопоставление карт с большими наборами данных GPS - Тесты эксперимента по мониторингу скорости в Цюрихе» (PDF) .
- ^ Шюсслер; Аксхаузен (октябрь 2009 г.). «Сопоставление карт GPS-треков в навигационных сетях высокого разрешения с использованием метода множественных гипотез (MHT)» (PDF) . [ постоянная мертвая ссылка ]
- ^ Уиллард (октябрь 2013 г.). «GPS-слежение на дорогах и бездорожье в реальном времени». arXiv : 1303.1883 [ стат.AP ].
- ^ Бернштейн, Дэвид; Корнхаузер, Ален (1 августа 1996 г.). Технологический институт Нью-Джерси (ред.). «Введение в сопоставление карт для персональных навигационных помощников» .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Джафарлу, Мину; Надери, Хасан (2022). «Улучшение метода сопоставления карт на основе нечеткой логики с обнаружением точки остановки траектории». arXiv : 2208.02881 [ cs.LG ].
- ^ Ньюсон, Пол; Крамм, Джон (ноябрь 2009 г.). «Сопоставление скрытых карт Маркова через шум и разреженность» . I17-я Международная конференция ACM SIGSPATIAL по достижениям в области географических информационных систем (ACM SIGSPATIAL GIS 2009) .
- ^ Ло, Ан; Чен, Шэнхуа; Xv, Бин (ноябрь 2017 г.). «Усовершенствованный алгоритм сопоставления карт со скрытой марковской моделью для позиционирования мобильного телефона» . Международный геоинформационный журнал ISPRS . 6 (11): 327. Бибкод : 2017IJGI....6..327L . дои : 10.3390/ijgi6110327 . ISSN 2220-9964 .
- ^ «Отслеживание карты» . Проверено 14 марта 2018 г.
- ^ "инструменты открытого отслеживания" . Гитхаб . 16 марта 2020 г.
- ^ «Реализация сопоставления карт в Java» . Гитхаб . 30 апреля 2020 г.