Управление картографической базой данных

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

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

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

Основная статья: Модель данных (ГИС)

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

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

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

Каждый узел в графе карты представляет собой точку на поверхности Земли и представлен парой координат долготы (lon) и широты (lat). Каждое звено представляет собой участок дороги между двумя узлами и представляет собой сегмент линии (соответствующий прямому участку дороги) или кривую, имеющую форму, которая обычно описывается промежуточными точками (называемыми точками формы) вдоль звена. Однако кривые также могут быть представлены комбинацией центроида (точки или узла) с радиусом и полярных координат для определения границ кривой. Точки формы представлены долгосрочными координатами, как и узлы, но точки формы не служат для соединения связей, как узлы. Области — это двумерные фигуры, которые представляют собой парки, города, кварталы и определяются их границами. Обычно они образуются в виде замкнутого многоугольника — фигуры, которая указывает на то, что объект на карте должен иметь тесную границу, то есть первая вершина должна совпадать с последней вершиной. (Например, чтобы нанести на карту квадратный объект, вершины многоугольника пронумерованы 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-битные целые числа и, следовательно, имеют диапазон 65 536 значений. Этого слишком мало, чтобы охватить весь мир, поэтому для каждой страны или региона страны составляются отдельные таблицы. Для данного мегаполиса включены только перекрестки автомагистралей, магистралей и некоторых основных дорог. Это показано на следующем рисунке для района метро Детройта. Покрытие предназначено для предоставления консультативной информации о дорожном движении на дорогах с интенсивным использованием. С другой стороны, планирование маршрутов с учетом трафика требует охвата всех или почти всех основных дорог и, следовательно, не поддерживается должным образом таблицами кодов местоположения TMC в их нынешнем виде.

Общие ссылки

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

Европейский ActMAP

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

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

См. также

• Автомобильная навигационная система
• Задача о кратчайшем пути , класс задач и алгоритмы, используемые для получения навигационного маршрута из базы данных карт.
• Географическая база данных
• Географическая информационная система
• Глобальная навигационная спутниковая система
• Интеллектуальная транспортная система
• Карта
• Навтек
• Достопримечательность
• Объектно-реляционная база данных
• Открытый геопространственный консорциум
• Роботизированное картографирование
• Теле Атлас
• Телематика