Los sistemas de administración de bases de datos de mapas son programas de software diseñados para almacenar y recuperar información espacial de manera eficiente. Se utilizan ampliamente en localización y navegación, especialmente en aplicaciones de automoción. Además, están desempeñando un papel cada vez más importante en las áreas emergentes de servicios basados en la ubicación , funciones de seguridad activa y sistemas avanzados de asistencia al conductor . Común a estas funciones es el requisito de una base de datos de mapas a bordo que contenga información que describa la red de carreteras.
Cuando está bien diseñada, una base de datos de mapas permite la indexación y búsqueda rápidas de una gran cantidad de datos geográficos.
Contenido de una base de datos de mapas
Los mapas se almacenan como gráficos o matrices bidimensionales de objetos con atributos de ubicación y categoría, donde algunas categorías comunes incluyen parques, carreteras, ciudades y similares.
Una base de datos de mapas representa una red de carreteras junto con las características asociadas. Los proveedores de mapas pueden elegir varios modelos de una red de carreteras como base para formular una base de datos. Por lo general, dicho modelo comprende elementos básicos (nodos, enlaces y áreas) de la red de carreteras y las propiedades de esos elementos (coordenadas de ubicación, forma, direcciones, clase de carretera, rango de velocidad, etc.). Los elementos básicos se conocen como características y las propiedades como atributos. También se incluye otra información asociada con la red de carreteras, incluidos puntos de interés, formas de edificios y límites políticos. Esto se muestra esquemáticamente en la imagen adyacente. Archivos de datos geográficos (GDF) [1] es una descripción estandarizada de dicho modelo.
Cada nodo dentro de un gráfico de mapa representa la ubicación de un punto de la superficie de la Tierra y está representado por un par de coordenadas de longitud (lon) y latitud (lat). Cada enlace representa un tramo de carretera entre dos nodos y está representado por un segmento de línea (correspondiente a una sección recta de carretera) o una curva que tiene una forma que generalmente se describe mediante puntos intermedios (llamados puntos de forma) a lo largo del enlace. Sin embargo, las curvas también se pueden representar mediante una combinación de centroide (punto o nodo), con un radio y coordenadas polares para definir los límites de la curva. Los puntos de forma están representados por coordenadas lon-lat al igual que los nodos, pero los puntos de forma no sirven para conectar enlaces, como lo hacen los nodos. Las áreas son formas bidimensionales que representan cosas como parques, ciudades, bloques y están definidas por sus límites. Estos generalmente están formados por un polígono cerrado , que son formas que indican que un objeto sobre un mapa debe tener un límite cercano, lo que significa que el primer polígono debe ser el mismo que el último polígono. (Por ejemplo, para trazar un objeto cuadrado en un mapa, los polígonos son 1, 2, 3, 4, 1).
Otro punto para la validación de los datos es el punto en el polígono , que ayuda a encontrar puntos que se encuentran fuera de un polígono. Por ejemplo, para unas coordenadas particulares de latitud y longitud en una ciudad, si el punto se cruza con el polígono en un número impar, entonces está dentro del polígono y es un punto válido; de lo contrario, está fuera del polígono y no es válido.
Formato de intercambio
Los proveedores de mapas generalmente recopilan, agregan y suministran datos en un formato de archivo bien definido y documentado que está específicamente diseñado para el intercambio de información, por ejemplo, Navteq usa el formato de intercambio estándar (SIF) [2] y GDF , mientras que Tele Atlas usa una forma patentada de GDF . [3] Por lo general, está en formato de texto sin formato ( ASCII ) y consta de campos que las distintas partes que lo manejarán pueden analizar e interpretar fácilmente. El formato portátil permite que las adiciones, eliminaciones y modificaciones se realicen fácilmente mediante simples programas de edición de texto.
Se utiliza una pequeña cantidad de tipos de registros para representar los distintos tipos de datos. Cada tipo de registro consta de una secuencia de campos, que tienen una longitud fija o están delimitados por un carácter de puntuación, como una coma. Por ejemplo, una entidad de enlace podría estar representada por un registro de la forma:
donde type1 define esto como un tipo de registro de enlace y la etiqueta sirve como identificador para distinguir este enlace de todos los demás. Los campos z1 y z2 determinan la separación vertical de este enlace de otros que comparten los nodos correspondientes nodo1 y nodo2 . Así, un paso elevado a un enlace, por ejemplo, puede representarse como no conectado a ese enlace. Otros tipos de registros se utilizan para representar información de direcciones, puntos de forma para un enlace, ciudades y estados, puntos de interés (PDI), etc.
El formato de intercambio de una base de datos de mapas no está bien organizado para que lo utilice una unidad de navegación durante el tiempo de ejecución. Los registros están en un orden arbitrario y, por lo tanto, es difícil buscarlos y los datos, como los nombres de las calles y los valores de coordenadas, se repiten de un registro a otro. En consecuencia, el contenido de la base de datos se reorganiza en una forma binaria más adecuada para la operación en tiempo de ejecución.
Formato de tiempo de ejecución
Los formatos en tiempo de ejecución suelen ser propietarios, lo que impide la interoperación de mapas entre diferentes sistemas de navegación. Sin embargo, una nueva iniciativa llamada Navigation Data Standard (NDS) es una agrupación industrial de fabricantes de automóviles, proveedores de sistemas de navegación y proveedores de datos de mapas cuyo objetivo es la estandarización del formato de datos utilizado en los sistemas de navegación para automóviles. [4] Las empresas involucradas incluyen TomTom , BMW , Volkswagen , Daimler , Renault , ADIT, Alpine Electronics , Navigon , Bosch , DENSO , Mitsubishi , Harman Becker, Panasonic , PTV, Continental AG , Navteq y Zenrin .
La base de datos es reorganizada por un proveedor de navegación [5] [6] [7] a través de un proceso de compilación que incluye al menos los siguientes cinco pasos:
- Compruebe la coherencia de la red. Por ejemplo, asegúrese de que todos los pares de nodos que deberían estar conectados por un enlace tengan dicho enlace y, a la inversa, todos los pares de nodos que no deberían estar conectados no tengan un enlace de conexión.
- Asignar identificadores (ID) a todas las entidades de manera sistemática.
- Aplique múltiples conjuntos de índices a las entidades para facilitar la búsqueda en la base de datos de las formas esperadas.
- Reemplace múltiples ocurrencias de elementos de datos (nombres de calles, coordenadas, etc.) por índices en tablas que contienen una sola copia de cada elemento.
- Aplique otras técnicas de compresión para reducir el tamaño total de la base de datos.
La verificación de coherencia del paso 1 suele ser un proceso muy interactivo e iterativo que puede tardar semanas en completarse. Durante este tiempo, las discrepancias deben detectarse, investigarse y resolverse.
En el paso 2, los ID se asignan generalmente de forma secuencial a medida que se encuentran las entidades de cada tipo. Cualquier cambio realizado en la base de datos de entrada de una versión a otra afectará la asignación de ID a todas las entidades. En consecuencia, hay poca expectativa de continuidad en la asignación entre versiones.
En el paso 3, cada índice aplicado permite buscar rápidamente en la base de datos de una manera específica. Un conjunto de índices aplicado a los enlaces se puede clasificar por orden alfabético de los nombres de las calles de los enlaces. Otro conjunto de índices aplicado a los enlaces se puede clasificar según los nodos a los que están conectados para facilitar la planificación de rutas. Otro conjunto de índices aplicado a los nodos se puede clasificar de acuerdo con su orden de aparición a lo largo de una carretera. En algunos de estos casos, se puede realizar una búsqueda binaria en lugar de una búsqueda exhaustiva y, en algunos casos, se puede reemplazar un proceso de búsqueda con una simple búsqueda en una tabla.
Actualización incremental
Para la mayoría de las funciones de navegación es importante tener en el vehículo una base de datos de mapas actualizada, y para algunas funciones es fundamental, especialmente las relacionadas con la seguridad activa. Una estrategia común es transferir información actualizada al vehículo siempre que esté disponible a través de un canal inalámbrico. El canal inalámbrico puede ser bidireccional, como Wi-Fi y teléfono celular, transmisión , como radio satelital, subportadora de FM o transmisión de datos ATSC , o una combinación de ambos. En cualquier caso, sería poco práctico o extremadamente ineficaz transmitir toda la nueva base de datos para reemplazar una versión existente, ya que es probable que tenga un tamaño de varios gigabytes.
En su lugar, es deseable transferir solo la información relacionada con los cambios realizados en la base de datos existente. Una dificultad importante es que cualquier cambio realizado en el contenido de una base de datos de mapas generalmente provoca cambios en todos los ID de entidad asignados y todos los índices asignados durante el proceso de compilación. Estos nuevos ID e índices impregnan toda la base de datos compilada, por lo que cualquier colección de incrementos probablemente constituirá la mayor parte de la base de datos. Para superar esta dificultad, se han adoptado tres enfoques, que son brevemente: 1) compilador integrado 2) tienda independiente 3) mosaicos geográficos.
Compilador incorporado
En este caso, los cambios básicos realizados en el formato de intercambio de la base de datos se transmiten al vehículo. Dichos cambios se representan en forma transaccional que consiste en adiciones , eliminaciones y reemplazos . Estos cambios se aplican a la base de datos integrada existente en formato de intercambio. El formato de intercambio para la base de datos incorporada podría almacenarse por separado o generarse según sea necesario "descompilando" el formato de tiempo de ejecución. Luego se compila la base de datos combinada, lo que implica asignar ID y aplicar índices.
Esta compilación incorporada probablemente será computacionalmente intensiva y requerirá una cantidad considerable de memoria. Sin embargo, no es necesario que sea interactivo e iterativo como lo hace la compilación externa, ya que ya se habrán realizado comprobaciones de coherencia y resolución. Además, la compilación integrada se puede realizar en segundo plano, por lo que el tiempo de cálculo no es crítico.
Tienda de look-side
En este caso, los cambios básicos también se transmiten al vehículo, pero se colocan en una ubicación de memoria separada llamada tienda de apartados . Los cambios también se representan en forma transaccional, pero pueden aparecer en cualquier formato conveniente, que no es necesariamente intercambio o tiempo de ejecución. Durante el funcionamiento de la unidad de navegación, se busca en el almacén de búsqueda cada vez que se accede a la base de datos principal. A continuación, se aplican todas las transacciones (cambios) que pertenecen a los datos a los que se accede.
La necesidad de examinar el almacén de búsqueda y aplicar cambios para cada acceso a la base de datos, por supuesto, complica los algoritmos de navegación y alarga su tiempo de cálculo. Sin embargo, esto evita la necesidad de un compilador integrado.
Azulejos geográficos
En este enfoque, la base de datos del mapa se divide en regiones rectangulares relativamente pequeñas (mosaicos) que forman teselas en el mapa. El tamaño de la baldosa es del orden de 1 km de lado. Estos mosaicos se compilan por separado, de modo que todos los ID e índices están condicionados por el mosaico particular al que se aplican. Los mosaicos que han cambiado debido a cambios de entidad o atributos básicos en la base de datos se transmiten al vehículo, donde reemplazan el mosaico existente correspondiente.
Reemplazar mosaicos es considerablemente más simple que la compilación a bordo o el empleo de una tienda independiente. Sin embargo, puede que no sea eficaz para la transmisión. Un cambio local en entidades y atributos, independientemente de la extensión, requiere la transmisión de todo el mosaico contenedor. Además, hay efectos de borde en los que un cambio en una entidad dentro de un mosaico afecta a las entidades en mosaicos vecinos. Es muy posible que una pequeña cantidad de cambios de entidad requiera la transmisión de casi todos los mosaicos, frustrando así el propósito de las actualizaciones incrementales. Estos problemas se pueden solucionar seleccionando el tamaño del mosaico y la frecuencia de actualización.
Adjuntar datos auxiliares
Varias funciones de navegación, que implican seguridad activa, asistencia al conductor y servicios basados en la ubicación, requieren datos que no se consideran parte de una base de datos de mapas y probablemente sean suministrados por un proveedor que no sea el proveedor de mapas. Estos datos deben tener una referencia cruzada con las entidades y atributos de la base de datos principal. Sin embargo, dado que los datos auxiliares no se compilan necesariamente con la base de datos principal, se necesitan otros medios para establecer referencias cruzadas, lo que se conoce como adjuntar los datos auxiliares. Dos enfoques comunes son las tablas de referencia específicas de la función y las referencias genéricas.
Tablas de referencia específicas de la función
Las tablas de referencia de funciones específicas proporcionan un medio para adjuntar datos específicos de funciones a una base de datos de mapas producida por cualquier proveedor participante. Dicha tabla se produce en colaboración para respaldar una función o clase de funciones específicas que involucran servicio basado en la ubicación, seguridad activa o asistencia avanzada al conductor. Por lo general, consistirá en una lista de elementos del mapa de un tipo específico (por ejemplo, enlaces, intersecciones, ubicaciones de puntos de interés, etc.) junto con atributos de identificación (por ejemplo, nombres de calles, coordenadas de longitud / latitud, etc.). Además, a cada entrada de la tabla se le asigna un identificador único. El conjunto de entradas en una tabla se selecciona generalmente, por consenso de todas las partes interesadas. En la práctica, el resultado representará un pequeño subconjunto de los elementos del tipo dado que están disponibles en las bases de datos de mapas y consistirá en aquellos que son más importantes para el área de aplicación. Después de formular una tabla, es tarea de cada proveedor participante determinar y hacer una referencia cruzada de los elementos en su base de datos de mapas que corresponden a las entradas de la tabla.
Un ejemplo ampliamente utilizado es el estándar TMC para tablas de códigos de ubicación para referenciar datos de tráfico. TMC, que significa Traffic Message Channel , [8] es parte del Sistema de datos de radio (RDS), que se implementa como una modulación de subportadora de una señal de transmisión de FM comercial. Las tablas TMC proporcionan principalmente referencias a ubicaciones de puntos a lo largo de las carreteras principales correspondientes a las intersecciones con otras carreteras. Una entrada de tabla identifica la ubicación de un punto utilizando tanto información contextual (como región, camino y sección de camino, nombre de la intersección) como coordenadas aproximadas de longitud / latitud.
Los identificadores asignados a las entradas de una tabla son números enteros de 16 bits y, por lo tanto, tienen un rango de 65536 valores. Esto es muy poco para cubrir el mundo, por lo que se formulan tablas separadas para cada país o región de un país. Para una región metropolitana determinada, solo se incluyen las intersecciones a lo largo de autopistas, arterias y algunas carreteras principales. Esto se ilustra en la siguiente figura para el área metropolitana de Detroit. La cobertura está destinada a proporcionar información de advertencia de tráfico en carreteras de alto uso. La planificación de rutas basada en el tráfico, por otro lado, requiere la cobertura de todas o casi todas las carreteras principales y, por lo tanto, no está respaldada adecuadamente por las tablas de códigos de ubicación de TMC tal como están formuladas actualmente.
Referencia genérica
La referencia genérica es un intento de adjuntar datos a cualquier base de datos de mapas descubriendo información de referencia a través de una forma de comparación de mapas. Los elementos de datos específicos de la función se asignan a elementos, como puntos, enlaces o áreas, que probablemente solo se aproximan a los elementos del mapa correspondientes en una base de datos de mapas específica. Se realiza una búsqueda en la base de datos de mapas para obtener el mejor ajuste. Para mejorar el proceso de búsqueda, los elementos vecinos se añaden estratégicamente a cada elemento dado para ayudar a garantizar que se encuentre la solución correcta en cada caso. Por ejemplo, si el elemento del mapa es un vínculo que conecta dos intersecciones, entonces una o ambas calles transversales podrían agregarse por el bien de la búsqueda. Con suerte, esto hace que una coincidencia incorrecta sea poco probable. Aunque el procedimiento es bastante heurístico, un estándar propuesto llamado Agora describe la estrategia para elegir elementos vecinos para agregar.
Consorcio europeo ActMAP
Un consorcio europeo llamado ActMAP (Actualize Map) [9] está (en sus palabras) "desarrollando mecanismos estandarizados para actualizar el contenido de la base de datos de mapas existente y permitir la conexión dinámica de información al mapa digital del vehículo". El consorcio ActMAP está formado por ERTICO (coordinador), BMW, CRF Fiat Research Center, DaimlerChrysler, Navigon, Navteq, Tele Atlas y Siemens VDO Automotive. Han terminado la mayor parte de su trabajo y han publicado una serie de informes, que se enviaron al comité ISO TC204 WG3 para su estandarización. Sus informes sirven como un buen punto de partida y referencia para el trabajo de este proyecto. Un tema importante que abordan sus informes es lidiar con la complejidad de múltiples proveedores de mapas, utilizando formatos propietarios, junto con múltiples proveedores de datos y múltiples versiones de mapas en vehículos. Lo resuelven utilizando un formato de mapa intermedio abierto expresado en XML y basado en los conceptos del estándar ISO GDF 4.0. Todas las modificaciones a la base de datos de un proveedor se convierten primero a este formato intermedio, se almacenan en un servidor y luego se convierten a cada formato utilizado en vehículos individuales. Asumen que cada automóvil tiene un mapa de "línea de base" de un proveedor de mapas y que esta línea de base define identificadores de referencia (por ejemplo, ID de segmento de mapa) para la mayoría de las características que se actualizarán. Para las características sin un identificador de referencia en la línea de base, proponen el uso de una referencia "genérica" que se descubre heurísticamente usando la correspondencia de mapas como se describe en un estándar propuesto llamado AGORA
Un problema importante no abordado directamente por ActMAP es que para cada nueva versión de la base de datos de mapas de un proveedor, todos los ID de referencia suelen reasignarse mediante un proceso de compilación, que destruye cualquier correspondencia con los ID de versiones anteriores. Esto interfiere seriamente con la capacidad de utilizar actualizaciones incrementales para generar una nueva versión de una base de datos de mapas a partir de una versión anterior. Otro problema no resuelto por ActMAP es la incapacidad de referenciar y caracterizar subsecciones de segmentos de carreteras (por ejemplo, curvas, colinas, carriles de maniobra, etc.) para actualizarlos.
Ver también
- Sistema de navegación automotriz
- Problema de ruta más corta , clase de problemas y algoritmos empleados para obtener una ruta de navegación a partir de una base de datos de mapas.
- Base de datos geográfica
- Sistema de información geográfica
- Sistema global de navegación por satélite
- Sistema de transporte inteligente
- Mapa
- Navteq
- Punto de interés
- Base de datos relacional de objetos
- Consorcio Geoespacial Abierto
- Mapeo robótico
- Tele Atlas
- Telemática
Referencias
- ^ ISO 14825, Sistemas de transporte inteligentes - Archivos de datos geográficos (GDF) - Especificación general de datos, primera edición 2004, Suiza, http://www.iso.org
- ^ Formato de intercambio estándar (SIF), Navteq, Chicago, Ill, http://www.navteq.com/
- ^ GDF ASCII Sequential, Tele Atlas, "Copia archivada" . Archivado desde el original el 27 de agosto de 2008 . Consultado el 1 de octubre de 2007 .CS1 maint: copia archivada como título ( enlace )
- ^ "Estándar de datos de navegación" . NDS eV Consultado el 13 de febrero de 2015 . Enlace externo en
|publisher=
( ayuda ) - ^ Navigon, http://www.navigon.com
- ^ Aisin, http://www.aisin.com/
- ^ Denso, http://www.denso-europe.com/Navigation--1002010000000001.aspx
- ^ ISO 14819, preparado por ISO / TC 204 "Servicios de transporte inteligente", http://www.iso.org
- ^ ActMAP, Ertico, http://www.ertico.com/en/subprojects/actmap/objectives__approach/objectives__approach.htm Archivado 2007-04-07 en Wayback Machine