Управление базой данных карт - Map database management

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

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

Содержание картографической базы данных

Рисунок 1: Объекты и их соответствующие атрибуты в базе данных карт

Карты хранятся в виде графиков или двумерных массивов объектов с атрибутами местоположения и категории, где некоторые общие категории включают парки, дороги, города и т.п.

База данных карт представляет дорожную сеть вместе с соответствующими объектами. Поставщики карт могут выбирать различные модели дорожной сети в качестве основы для создания базы данных. Обычно такая модель содержит основные элементы (узлы, звенья и области) дорожной сети и свойства этих элементов (координаты местоположения, форма, адреса, класс дороги, диапазон скоростей и т. Д.). Основные элементы называются функциями, а свойства - атрибутами. Также включена другая информация, связанная с дорожной сетью, включая достопримечательности, формы зданий и политические границы. Это схематично показано на соседнем изображении. Файлы географических данных (GDF) - это стандартизированное описание такой модели.

Каждый узел на графике карты представляет собой точку на поверхности Земли и представлен парой координат долготы ( долгота ) и широты ( широта ). Каждая ссылка представляет собой участок дороги между двумя узлами и представлена ​​отрезком линии (соответствующим прямому участку дороги) или кривой, имеющей форму, которая обычно описывается промежуточными точками (называемыми точками формы) вдоль ссылки. Однако кривые также могут быть представлены комбинацией центроида (точки или узла) с радиусом и полярными координатами для определения границ кривой. Точки формы представлены долгосрочными координатами, как и узлы, но точки формы не служат для соединения связей, как узлы. Области - это двухмерные фигуры, которые представляют такие объекты, как парки, города, кварталы и определяются их границами. Обычно они образуются замкнутым многоугольником , то есть формами, которые указывают на то, что объект на карте должен иметь близкую границу, то есть первый многоугольник должен быть таким же, как последний многоугольник. (Например, чтобы нанести квадратный объект на карту, используйте многоугольники 1,2,3,4,1.)

Еще одна точка для проверки данных - точка в многоугольнике , которая помогает находить точки, лежащие вне многоугольника. Например, для определенных долготных координат в городе, если точка пересекает многоугольник в нечетном числе, то она находится внутри многоугольника и является допустимой точкой; в противном случае он находится за пределами многоугольника и недействителен.

Формат обмена

Поставщики карт обычно собирают, объединяют и предоставляют данные в четко определенном и задокументированном формате файла, который специально предназначен для обмена информацией, например, Navteq использует стандартный формат обмена (SIF) и GDF , а Tele Atlas использует частную форму GDF. Обычно он представлен в виде обычного текста ( ASCII ), состоящего из полей, которые легко анализируются и интерпретируются различными сторонами, которые будут его обрабатывать. Переносимый формат позволяет легко выполнять добавления, удаления и изменения с помощью простых программ редактирования текста.

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


тип1, метка, узел1, z1, узел2, z2, класс, количество точек формы, количество полос, скорость


где type1 определяет это как тип записи ссылки, а метка служит идентификатором, чтобы отличить эту ссылку от всех остальных. Z1 и z2 поля определяют вертикальное разделение этой ссылки от других , разделяющих соответствующих узлов node1 и node2 . Таким образом, эстакада к ссылке, например, может быть представлена ​​как не подключенная к этой ссылке. Другие типы записей используются для представления адресной информации, точек формы для ссылки, городов и штатов, достопримечательностей (POI) и т. Д.

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

Формат времени выполнения

Форматы времени выполнения обычно являются проприетарными, что предотвращает взаимодействие карт между различными навигационными системами. Однако новая инициатива под названием « Стандарт навигационных данных» (NDS) представляет собой отраслевую группу производителей автомобилей, поставщиков навигационных систем и поставщиков картографических данных, целью которой является стандартизация формата данных, используемых в автомобильных навигационных системах. Участвующие компании включают TomTom , BMW , Volkswagen , Daimler , Renault , ADIT, Alpine Electronics , Navigon , Bosch , DENSO , Mitsubishi , Harman Becker, Panasonic , PTV, Continental AG , Navteq и Zenrin .

База данных реорганизуется поставщиком навигации посредством процесса компиляции, который включает как минимум следующие пять шагов:

  1. Проверьте целостность сети. Например, убедитесь, что все пары узлов, которые должны быть соединены ссылкой, имеют такую ​​ссылку, и наоборот, все пары узлов, которые не должны быть соединены, не имеют соединительной ссылки.
  2. Систематически присваивайте идентификаторы (ID) всем объектам.
  3. Примените несколько наборов индексов к объектам, чтобы упростить поиск в базе данных ожидаемыми способами.
  4. Замените несколько экземпляров элементов данных (названия улиц, координаты и т. Д.) Индексами в таблицах, содержащих по одной копии каждого такого элемента.
  5. Примените другие методы сжатия, чтобы уменьшить общий размер базы данных.

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

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

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

Инкрементное обновление

Для большинства навигационных функций важно иметь в автомобиле актуальную базу данных карт, а для некоторых функций это важно, особенно тех, которые связаны с активной безопасностью. Распространенной стратегией является передача обновленной информации в автомобиль всякий раз, когда она становится доступной по беспроводному каналу. Беспроводной канал может быть двунаправленным, например Wi-Fi и сотовый телефон, широковещательный , например спутниковое радио, поднесущая FM или передача данных ATSC , или их комбинация. В любом случае было бы непрактично или крайне неэффективно передавать всю новую базу данных для замены существующей версии, поскольку она, вероятно, будет иметь размер в несколько гигабайт.

Вместо этого желательно передавать только ту информацию, которая связана с изменениями, внесенными в существующую базу данных. Основная трудность заключается в том, что любое изменение содержимого базы данных карт обычно вызывает изменения всех присвоенных идентификаторов объектов и всех присвоенных индексов в процессе компиляции. Эти новые идентификаторы и индексы пронизывают всю скомпилированную базу данных, так что любой набор приращений, вероятно, будет составлять большую часть базы данных. Чтобы преодолеть эту трудность, были предприняты три подхода, а именно: 1) встроенный компилятор 2) временное хранилище 3) географические плитки.

Встроенный компилятор

В этом случае основные изменения, внесенные в формат обмена базой данных, передаются на автомобиль. Такие изменения представлены в транзакционной форме, состоящей из добавлений , удалений и замен . Эти изменения применяются к существующей бортовой базе данных в формате обмена. Формат обмена для встроенной базы данных может быть сохранен отдельно или сгенерирован по мере необходимости путем «декомпиляции» формата времени выполнения. Затем объединенная база данных компилируется, что включает в себя присвоение идентификаторов и применение индексов.

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

Смотровой магазин

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

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

Географические плитки

При таком подходе база данных карты разбивается на относительно небольшие прямоугольные области (плитки), которые разбивают карту на мозаику. Размер плитки - порядка 1 км по стороне. Эти плитки компилируются отдельно, так что все идентификаторы и индексы обусловлены конкретной плиткой, к которой они применяются. Плитки, которые изменились из-за изменений базового объекта или атрибута в базе данных, передаются в транспортное средство, где они заменяют соответствующую существующую плитку.

Замена плиток значительно проще, чем сборка на борту или использование стороннего магазина. Однако это может быть неэффективным для передачи. Локальное изменение сущностей и атрибутов, независимо от степени, требует передачи всего содержащего тайла. Кроме того, существуют краевые эффекты, при которых изменение объекта внутри одной плитки влияет на объекты в соседних плитках. Вполне возможно, что небольшое количество изменений сущностей потребует передачи почти всех тайлов, что противоречит цели инкрементных обновлений. Эти проблемы можно решить, выбрав размер плитки и частоту обновления.

Прикрепление вспомогательных данных

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

Справочные таблицы для конкретных функций

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

Рисунок 2: Расположение TMC в Метро Детройт

Широко используемым примером является стандарт TMC для таблиц кодов местоположения для ссылки на данные трафика. TMC, что означает канал сообщений о дорожном движении , является частью системы радиоданных (RDS), которая реализована как модуляция поднесущей коммерческого сигнала FM-вещания. Таблицы TMC в первую очередь предоставляют ссылки на точечные местоположения вдоль основных дорог, соответствующих пересечениям с другими дорогами. Запись в таблице определяет местоположение точки, используя как контекстную информацию (например, регион, дорогу и участок дороги, название перекрестка), так и приблизительные координаты долготы / широты.

Идентификаторы, присвоенные записям в таблице, представляют собой 16-разрядные целые числа и, следовательно, имеют диапазон 65536 значений. Этого слишком мало, чтобы охватить весь мир, поэтому для каждой страны или региона страны составляются отдельные таблицы. Для данного столичного региона включены только перекрестки вдоль автомагистралей, магистралей и некоторых основных дорог. Это показано на следующем рисунке для района метро Детройта. Покрытие предназначено для предоставления консультативной информации о дорожном движении на дорогах с интенсивным движением. С другой стороны, планирование маршрута на основе трафика требует покрытия всех или почти всех основных дорог и, следовательно, не поддерживается в достаточной степени таблицами кодов местоположения TMC в том виде, в каком они сформулированы в настоящее время.

Общие ссылки

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

Европейский консорциум ActMAP

Европейский консорциум под названием ActMAP (Actualize Map) (по их словам) «разрабатывает стандартизированные механизмы для обновления содержимого существующей базы данных карт и обеспечения динамического присоединения информации к цифровой автомобильной карте». Консорциум ActMAP включает ERTICO (координатор), BMW, CRF Fiat Research Center, DaimlerChrysler, Navigon, Navteq, Tele Atlas и Siemens VDO Automotive. Они завершили большую часть своей работы и опубликовали ряд отчетов, которые были представлены комитету ISO TC204 WG3 для стандартизации. Их отчеты служат хорошей отправной точкой и ориентиром для работы над этим проектом. Важная проблема, на которую обращаются их отчеты, связана со сложностью множества поставщиков карт, использующих собственные форматы, в сочетании с множеством поставщиков данных и множеством версий автомобильных карт. Они решают эту проблему, используя открытый промежуточный формат карты, выраженный с помощью XML и основанный на концепциях стандарта ISO GDF 4.0. Все изменения в базе данных поставщика сначала преобразуются в этот промежуточный формат, сохраняются на сервере, а затем преобразуются в каждый формат, используемый в отдельных автомобилях. Они предполагают, что у каждого автомобиля есть «базовая» карта от поставщика карты, и что эта базовая линия определяет ссылочные идентификаторы (например, идентификатор сегмента карты) для большинства функций, подлежащих обновлению. Для объектов без идентификатора ссылки в базовой линии они предлагают использовать «общую» ссылку, которая обнаруживается эвристически с использованием сопоставления карт, как описано в предлагаемом стандарте под названием AGORA.

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

Смотрите также

Рекомендации

  1. ^ ISO 14825, Интеллектуальные транспортные системы - Файлы географических данных (GDF) - Общая спецификация данных, первое издание 2004 г., Швейцария, http://www.iso.org
  2. ^ Стандартный формат обмена (SIF), Navteq, Чикаго, Иллинойс, http://www.navteq.com/
  3. ^ GDF ASCII Sequential, Tele Atlas, «Архивная копия» . Архивировано из оригинала на 2008-08-27 . Проверено 1 октября 2007 .CS1 maint: заархивированная копия как заголовок ( ссылка )
  4. ^ «Стандарт навигационных данных» . НСР эВ Источник 2015-02-13 . Внешняя ссылка в |publisher=( помощь )
  5. ^ Navigon, http://www.navigon.com
  6. ^ Айсин, http://www.aisin.com/
  7. ^ Denso, http://www.denso-europe.com/Navigation--1002010000000001.aspx
  8. ^ ISO 14819, подготовленный ISO / TC 204 «Интеллектуальные транспортные услуги», http://www.iso.org
  9. ^ ActMAP, Ertico, http://www.ertico.com/en/subprojects/actmap/objectives__approach/objectives__approach.htm. Архивировано 7 апреля 2007 г.на Wayback Machine.