Карта соответствия ссылок и идей? [закрыто]

44

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

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

введите описание изображения здесь

Однако из-за недостаточной точности GPS иногда отображаемое положение перепрыгивает с сегмента на другой и может время от времени предоставлять некоторое несовместимое отображаемое положение.

Мой текущий алгоритм очень прост: из чистой позиции GPS я получаю ближайший сегмент и решаю, что сопоставленная сопоставленная позиция находится на этом. Я знаю, что это может быть действительно улучшено.

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

Я ищу любую ссылку и / или программное обеспечение с открытым исходным кодом?

yonel
источник
4
Вы можете добавить круг - Google использует прием в ячейке и создает светло-синий круг, чтобы показать ваше приблизительное местоположение. Ваше приложение выглядит хорошо, хорошая работа. Если у вас есть векторные данные, вы можете привязать их к ближайшей линии от вашей точки GPS - см. Сообщение Пола Рамси blog.cleverelephant.ca/2008/04/snapping-points-in-postgis.html
Mapperz
4
Ключевое слово, которое вы ищете, - Map Matching. Большой предмет.
Уффе Кусгаард
1
Аффе прав, сопоставление карт. Проверьте этот документ для нескольких подходов: cens.ucla.edu/~mhr/cs219/maps/white00.pdf
lexicore
Благодарность! lexicore, бумага отправляется на мой принтер, когда я набираю это. Время получить обзор. Спасибо за ссылку.
13
Я бы улучшил Алгоритм, также пытаясь привязаться к реальной дороге, а не только к вершинам.
Девдатта Тенгше

Ответы:

11

Проецирование точек на линию, как вы уже делаете, возможно сделать непосредственно в PostGIS. Я писал об этом некоторое время назад, здесь

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

  1. Построить линейную линию из точек
  2. Попробуйте предложенные решения в Алгоритмах для сопоставления сегментов, чтобы соответствовать всей линии, а не просто точка за точкой
Никлас Авен
источник
Спасибо за ваш ответ. Проекция в порядке: я уже делаю это (не через ST_Closest, потому что он не доступен в пространственном пространстве, которое я использую, но это нормально). Я также просто смотрел на вопрос, который вы упомянули, и узнал о существовании этой «дистанции Хаусдорфа», на которую, возможно, будет интересно взглянуть.
Йонель
10

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

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

Для дальнейшего чтения я предлагаю следующее:

Девдатта Тенгше
источник
Да, я также читал и начал играть с реализацией простого алгоритма, который я могу расширить. До сих пор я загрузил некоторые данные из OSM, и я играю над тем, как лучше всего хранить (и получать к ним доступ) для своих целей. Это интересная тема, я думаю. :) Я обновлю этот вопрос, как только у меня будет что-то, что работает. Также спасибо за ссылки!
scrrr
Я был бы осторожен с использованием весов: «Таким образом, вероятность совпадения точки с шоссе будет выше, чем при сопоставлении боковой линии». ... Это зависит от входных данных и может пойти не так.
Подземье
@Devdatta, я получаю 404 по второй ссылке. Вместо того, чтобы просто отредактировать его, у вас есть альтернативная ссылка?
Чау
У меня нет ссылки на бесплатный доступ к этой статье. Но если вы находитесь в академической обстановке. Статья должна быть доступна после быстрого поиска
Devdatta Tengshe
@Chau: я нашел PDF по адресу: researchgate.net/profile/Alain_Kornhauser/publication/…
Девдатта Тенгше
7

Отвечая на мой вопрос!

1- Хороший .pdf, который я только что нашел об этой теме:

http://safari.ce.sharif.edu/file/2011-06-06/259/2009_An%20off-line%20map-matching%20algorithm%20for%20incomplete%20map%20databases.pdf

это также связано с реализацией сопоставителя карт с открытым исходным кодом на C ++, описанной в документе: http://eden.dei.uc.pt/~camara/files/mgemma.zip
(это автономный сопоставитель карт, насколько я понимаю, что он вычисляет сопоставленные положения карты с ВСЕМ путем в качестве входных данных и не может сделать это на лету для каждой позиции).

2- Затем я только что подробно прочитал этот вопрос, и он, на мой взгляд, действительно хорош: https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/4860/1/velaga.pdf "Разработка Усовершенствованный основанный на весе топологический алгоритм MapMatching для интеллектуальных транспортных систем "
Алгоритм четко объяснен, а значения регулировки веса также приведены в документе.

yonel
источник
4

Существует много работы по сопоставлению карт, см. Эту статью для краткого обзора некоторых довольно недавних работ (до 2007 года). Совсем недавно подходы, основанные на скрытых марковских моделях, по-видимому, работали достаточно хорошо в нормальных условиях Например, ознакомьтесь с этой статьей за 2009 год. Идея и модель довольно просты и не должны доставлять вам особых хлопот, даже если вы не знакомы с HMM (в этом случае, не паникуйте, есть много из учебников и внедрения в Интернете)

Ник
источник
1
Только что понял, что босой -проект, который я упомянул в своем ответе, основан на статье, которую рекомендует @Nick.
Ник
4

Этот метод также называется «векторное слияние». Существует специальная вики-страница ( http://wiki.openstreetmap.org/wiki/Conflation ), которая содержит общий обзор и список пакетов программного обеспечения (с открытым исходным кодом) для выполнения дорожной векторной сопоставления, таких как «JOSM-плагин для сопоставления», «объединение Potlatch 2». tool »,« RoadMatcher »(для OpenJUMP) и другие.

markusN
источник
1
Я всегда думал, что слияние - это то, что вы делаете с двумя линейными слоями вместо совмещения точек на линиях. Это действительно то же самое?
Подземье
4

Для алгоритмов сопоставления карт это зависит от того, нужна ли вам обработка в реальном времени или в автономном режиме. В последнем случае современные алгоритмы могут обрабатывать ~ 1000 точек в секунду. Требования к памяти, конечно, зависят от покрытия. Для этого нам удалось сжать дорожную сеть OSM планеты примерно на 16 Гб.

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

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

Фабрис Маршал
источник
Можете ли вы расширить алгоритмы, которые вы используете? И как помогает уменьшение размера дорожной сети?
Девдатта Тенгше
Меньшее покрытие = меньшая сеть для хранения в памяти. Это немного ускоряет вычисления. Ссылки: trb.metapress.com/content/p31485vw72645686
Фабрис Маршал
3

Strava Slide описывает, как кумулятивные данные трека по дорожной сети могут вести себя как «долины», и как предлагаемый маршрут «встанет на свои места», как будто это была бусинка.

heltonbiker
источник
2

После тестирования большинства ранее упомянутых фреймворков я нашел Barefoot и могу порекомендовать его. Он использует скрытые марковские модели в качестве вероятностного подхода к сопоставлению карт (подробности в статье «Поместить автомобиль на карту» ) и реализован на Java. Он с открытым исходным кодом и активно разрабатывается отделом CarIT BMW.

Nik
источник
2

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

Мой проект с открытым исходным кодом, называемый graphhopper, - это не то, что работает для iOS ( обновление : теперь оно работает и на iOS), и при этом у него нет полнофункционального Android-приложения для того, что вы хотите. Но вы можете использовать версию сервера для создания приложения для iOS или использовать автономную демонстрацию Android для начала. Я выпустил здесь алгоритм сопоставления карт , просто грубый прототип, но он работает на удивление хорошо.

Karussell
источник
1

Попробуйте получить хорошие тестовые данные. Используйте дополнительную более высокую точность GPS-трекинга, помимо регистрации точек на целевом устройстве. Это позволит определить ошибки в GPS и в данных OSM. Знание разумных порогов значительно облегчит разработку алгоритма.

Мэтью Снейп
источник
1

Если вы можете получить данные о дорогах для своего региона, возможно, вас заинтересует Автоматическая групповая привязка с помощью FOSS

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

Михал Циммерманн
источник
1

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

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

Артур МакФлинт
источник
-1

Вам не нужно обязательно улучшать качество ваших данных. Использование топологического алгоритма с дорожной сетью в памяти значительно улучшит ваше соответствие. Проверьте ссылки: http://trb.metapress.com/content/p31485vw72645686

Фабрис Маршал
источник