Gerenciamento de banco de dados de mapas - Map database management

Os sistemas de gerenciamento de banco de dados de mapas são programas de software projetados para armazenar e recuperar informações espaciais de maneira eficiente. Eles são amplamente utilizados em localização e navegação, especialmente em aplicações automotivas. Além disso, eles estão desempenhando um papel cada vez mais importante nas áreas emergentes de serviços baseados em localização , funções de segurança ativa e sistemas avançados de assistência ao motorista . Comum a essas funções é o requisito de um banco de dados de mapas a bordo que contenha informações que descrevam a rede rodoviária.

Quando bem projetado, um banco de dados de mapas permite a rápida indexação e pesquisa de uma grande quantidade de dados geográficos.

Conteúdo de um banco de dados de mapas

Figura 1: Características e seus respectivos atributos em um banco de dados de mapas

Os mapas são armazenados como gráficos ou matrizes bidimensionais de objetos com atributos de localização e categoria, onde algumas categorias comuns incluem parques, estradas, cidades e semelhantes.

Um banco de dados de mapas representa uma rede de estradas junto com os recursos associados. Os fornecedores de mapas podem escolher vários modelos de uma rede rodoviária como base para formular um banco de dados. Normalmente, esse modelo compreende elementos básicos (nós, links e áreas) da rede rodoviária e propriedades desses elementos (coordenadas de localização, forma, endereços, classe de estrada, faixa de velocidade, etc.). Os elementos básicos são chamados de recursos e as propriedades, de atributos. Outras informações associadas à rede rodoviária também estão incluídas, incluindo pontos de interesse, formas de construção e fronteiras políticas. Isso é mostrado esquematicamente na imagem adjacente. Arquivos de dados geográficos (GDF) são uma descrição padronizada de tal modelo.

Cada nó em um gráfico de mapa representa uma localização de ponto da superfície da Terra e é representado por um par de coordenadas de longitude (lon) e latitude (lat). Cada link representa um trecho de estrada entre dois nós e é representado por um segmento de linha (correspondendo a uma seção reta da estrada) ou uma curva com uma forma que é geralmente descrita por pontos intermediários (chamados de pontos de forma) ao longo do link. No entanto, as curvas também podem ser representadas por uma combinação de centróide (ponto ou nó), com um raio e coordenadas polares para definir os limites da curva. Os pontos de forma são representados por coordenadas lon-lat assim como os nós, mas os pontos de forma não servem ao propósito de conectar elos, como os nós. As áreas são formas bidimensionais que representam coisas como parques, cidades, quarteirões e são definidas por seus limites. Eles geralmente são formados por um polígono fechado , que são formas que indicam que um objeto sobre um mapa deve ter um limite próximo, o que significa que o primeiro polígono deve ser igual ao último polígono. (Por exemplo, para plotar um objeto quadrado em um mapa, os polígonos são 1,2,3,4,1.)

Outro ponto de validação de dados é o ponto no polígono , que ajuda a encontrar pontos fora de um polígono. Por exemplo, para uma determinada coordenada lon-lat em uma cidade, se o ponto está cruzando o polígono em um número ímpar, então ele está dentro do polígono e é um ponto válido; caso contrário, está fora do polígono e é inválido.

Formato de intercâmbio

Os provedores de mapas geralmente coletam, agregam e fornecem dados em um formato de arquivo bem definido e documentado que se destina especificamente ao intercâmbio de informações, por exemplo, Navteq usa Standard Interchange Format (SIF) e GDF , enquanto a Tele Atlas usa uma forma proprietária de GDF. Geralmente está em formato de texto simples ( ASCII ), consistindo em campos que são facilmente analisados ​​e interpretados pelas várias partes que irão lidar com ele. O formato portátil permite que adições, exclusões e modificações sejam prontamente realizadas por programas simples de edição de texto.

Um pequeno número de tipos de registro é usado para representar os vários tipos de dados. Cada tipo de registro consiste em uma sequência de campos, que são de comprimento fixo ou delimitados por um caractere de pontuação, como uma vírgula. Por exemplo, uma entidade de link pode ser representada por um registro do formulário:

onde type1 define isso como um tipo de registro de link e o rótulo serve como um identificador para distinguir esse link de todos os outros. Os campos z1 e z2 determinam a separação vertical deste link de outros que compartilham os nós correspondentes node1 e node2 . Assim, um viaduto para um link, por exemplo, pode ser representado como não conectado a esse link. Outros tipos de registro são usados ​​para representar informações de endereço, pontos de forma para um link, cidades e estados, pontos de interesse (POIs), etc.

O formato de intercâmbio para um banco de dados de mapa não está bem organizado para uso por uma unidade de navegação durante o tempo de execução. Os registros estão em uma ordem arbitrária e, portanto, são difíceis de pesquisar e os dados, como nomes de ruas e valores de coordenadas, são repetidos de registro para registro. Consequentemente, o conteúdo do banco de dados é reorganizado em um formato binário mais adequado para operação em tempo de execução.

Formato de tempo de execução

Os formatos de tempo de execução são normalmente proprietários, evitando a interoperação de mapas entre diferentes sistemas de navegação. No entanto, uma nova iniciativa chamada Navigation Data Standard (NDS) é um agrupamento da indústria de fabricantes de automóveis, fornecedores de sistemas de navegação e fornecedores de dados de mapas, cujo objetivo é a padronização do formato de dados usado em sistemas de navegação automotiva. As empresas envolvidas incluem TomTom , BMW , Volkswagen , Daimler , Renault , ADIT, Alpine Electronics , Navigon , Bosch , DENSO , Mitsubishi , Harman Becker, Panasonic , PTV, Continental AG , Navteq e Zenrin .

O banco de dados é reorganizado por um provedor de navegação por meio de um processo de compilação que inclui pelo menos as cinco etapas a seguir:

1. Verifique a consistência da rede. Por exemplo, certifique-se de que todos os pares de nós que devem ser conectados por um link tenham esse link e, inversamente, todos os pares de nós que não devem ser conectados não tenham um link de conexão.
2. Atribua identificadores (IDs) a todas as entidades de maneira sistemática.
3. Aplique vários conjuntos de índices a entidades para facilitar a pesquisa no banco de dados das maneiras esperadas.
4. Substitua várias ocorrências de itens de dados (nomes de ruas, coordenadas, etc.) por índices em tabelas contendo uma única cópia de cada um desses itens.
5. Aplique outras técnicas de compactação para reduzir o tamanho geral do banco de dados.

A verificação de consistência da etapa 1 geralmente é um processo muito interativo e iterativo que pode levar semanas para ser concluído. Durante esse tempo, as discrepâncias precisam ser detectadas, investigadas e resolvidas.

Na etapa 2, os IDs são geralmente atribuídos sequencialmente conforme as entidades de cada tipo são encontradas. Quaisquer alterações feitas no banco de dados de entrada de uma versão para outra afetarão a atribuição de IDs a todas as entidades. Conseqüentemente, há pouca expectativa de continuidade na atribuição entre as versões.

Na etapa 3, cada índice aplicado permite que o banco de dados seja pesquisado rapidamente de uma maneira específica. Um conjunto de índices aplicado aos links pode ser classificado pela ordem alfabética dos nomes das ruas dos links. Outro conjunto de índices aplicado aos links pode ser classificado de acordo com os nós aos quais eles estão conectados para facilitar o planejamento da rota. Ainda outro conjunto de índices aplicado a nós pode ser classificado de acordo com sua ordem de aparecimento ao longo de uma estrada. Em alguns desses casos, uma pesquisa binária pode ser realizada em vez de uma pesquisa exaustiva e, em alguns casos, um processo de pesquisa pode ser substituído por uma consulta de tabela simples.

Atualização incremental

Para a maioria das funções de navegação, é importante ter no veículo um banco de dados de mapas atualizado, e para algumas funções é fundamental, especialmente aquelas relacionadas à segurança ativa. Uma estratégia comum é transferir informações de atualização para o veículo sempre que estiverem disponíveis em um canal sem fio. O canal sem fio pode ser bidirecional, como Wi-Fi e telefone celular, transmissão , como rádio por satélite, subportadora FM ou datacasting de ATSC , ou uma combinação de ambos. Em qualquer caso, seria impraticável ou extremamente ineficiente transmitir todo o novo banco de dados para substituir uma versão existente, uma vez que é provável que tenha vários gigabytes de tamanho.

Em vez disso, é desejável transferir apenas as informações relacionadas às alterações feitas no banco de dados existente. Uma grande dificuldade é que qualquer mudança feita no conteúdo de um banco de dados de mapas geralmente causa mudanças em todos os IDs de entidade atribuídos e todos os índices atribuídos durante o processo de compilação. Esses novos IDs e índices permeiam todo o banco de dados compilado, de modo que qualquer coleção de incrementos provavelmente constituirá a maior parte do banco de dados. Para superar essa dificuldade, três abordagens foram adotadas, que são resumidamente 1) compilador integrado 2) loja visual 3) blocos geográficos.

Compilador integrado

Nesse caso, as alterações básicas feitas no formato de intercâmbio do banco de dados são transmitidas ao veículo. Essas alterações são representadas na forma transacional, consistindo em adições , exclusões e substituições . Essas mudanças são aplicadas ao banco de dados integrado existente no formato de intercâmbio. O formato de intercâmbio para o banco de dados integrado pode ser armazenado separadamente ou gerado conforme necessário “descompilando” o formato de tempo de execução. O banco de dados combinado é então compilado, o que envolve a atribuição de IDs e a aplicação de índices.

Essa compilação integrada provavelmente exigirá muito do computador e exigirá uma quantidade considerável de memória. No entanto, não precisa ser interativo e iterativo como a compilação externa, uma vez que as verificações de consistência e a resolução já terão sido feitas. Além disso, a compilação a bordo pode ser feita em segundo plano, portanto o tempo de computação não é crítico.

Loja à parte

Nesse caso, as mudanças básicas também são transmitidas ao veículo, mas são colocadas em um local de memória separado, chamado de armazenamento visual . As alterações também são representadas na forma transacional, mas podem aparecer em qualquer formato conveniente, que não é necessariamente intercâmbio ou tempo de execução. Durante a operação da unidade de navegação, a loja visual é pesquisada cada vez que o banco de dados principal é acessado. Quaisquer transações (mudanças) que pertencem aos dados acessados ​​são então aplicadas.

A necessidade de examinar o armazenamento remoto e aplicar alterações para cada acesso ao banco de dados complica os algoritmos de navegação e aumenta seu tempo de computação. No entanto, isso evita a necessidade de um compilador integrado.

Ladrilhos geográficos

Nesta abordagem, o banco de dados do mapa é dividido em regiões retangulares relativamente pequenas (blocos) que formam o mosaico do mapa. O tamanho do ladrilho é da ordem de 1 km de lado. Esses blocos são compilados separadamente, de modo que todos os IDs e índices são condicionados pelo bloco específico ao qual se aplicam. Os ladrilhos que foram alterados devido a alterações básicas de entidade ou atributo na base de dados são transmitidos ao veículo, onde substituem o ladrilho existente correspondente.

Substituir ladrilhos é consideravelmente mais simples do que compilar a bordo ou empregar uma loja aparente. No entanto, pode não ser eficiente para transmissão. Uma mudança local para entidades e atributos, independentemente da extensão, requer a transmissão de todo o ladrilho que o contém. Além disso, existem efeitos de borda nos quais uma mudança em uma entidade em um bloco afeta as entidades nos blocos vizinhos. É bem possível que um pequeno número de alterações de entidade exija a transmissão de quase todos os tiles, anulando assim o propósito de atualizações incrementais. Esses problemas podem ser resolvidos selecionando o tamanho do bloco e a frequência de atualização.

Anexando dados auxiliares

Várias funções de navegação, envolvendo segurança ativa, assistência ao motorista e serviços baseados em localização, requerem dados que não são considerados parte de um banco de dados de mapas e provavelmente são fornecidos por um fornecedor diferente do provedor do mapa. Esses dados precisam ser cruzados com as entidades e atributos do banco de dados principal. No entanto, uma vez que os dados auxiliares não são necessariamente compilados com o banco de dados principal, algum outro meio é necessário para estabelecer referências cruzadas, o que é conhecido como anexar os dados auxiliares. Duas abordagens comuns são tabelas de referência de função específica e referência genérica.

Tabelas de referência específicas de função

As tabelas de referência específicas da função fornecem um meio para anexar dados específicos da função a uma base de dados de mapa produzida por qualquer fornecedor participante. Essa tabela é produzida de forma colaborativa para oferecer suporte a uma função específica ou classe de funções envolvendo serviço baseado em localização, segurança ativa ou assistência avançada ao motorista. Geralmente consiste em uma lista de elementos de mapa de um tipo específico (por exemplo, links, interseções, locais de pontos de interesse, etc.) junto com os atributos de identificação (por exemplo, nomes de ruas, coordenadas de longitude / latitude, etc.). Além disso, cada entrada na tabela recebe um identificador exclusivo. O conjunto de entradas em uma tabela geralmente é selecionado, por consenso de todas as partes interessadas. Na prática, o resultado representará um pequeno subconjunto dos elementos de um determinado tipo que estão disponíveis nos bancos de dados de mapas e consistirá naqueles que são mais importantes para a área de aplicação. Depois que uma tabela é formulada, é tarefa de cada fornecedor participante determinar e fazer referência cruzada dos elementos em seu banco de dados de mapas que correspondem às entradas da tabela.

Figura 2: localizações TMC no Metro Detroit

Um exemplo amplamente usado é o padrão TMC para tabelas de códigos de localização para fazer referência a dados de tráfego. TMC, que significa Traffic Message Channel , faz parte do Radio Data System (RDS), que é implementado como uma modulação de subportadora de um sinal de transmissão FM comercial. As tabelas TMC fornecem principalmente referências para pontos de localização ao longo das estradas principais correspondentes a interseções com outras estradas. Uma entrada na tabela identifica a localização de um ponto usando informações contextuais (como região, estrada e seção da estrada, nome da interseção) e coordenadas aproximadas de longitude / latitude.

Os identificadores atribuídos às entradas em uma tabela são inteiros de 16 bits e, portanto, têm um intervalo de 65536 valores. É muito pouco para cobrir o mundo, então tabelas separadas são formuladas para cada país ou região de um país. Para uma determinada região metropolitana, apenas cruzamentos ao longo de rodovias, vias arteriais e algumas estradas principais são incluídos. Isso é ilustrado na figura a seguir para a área metropolitana de Detroit. A cobertura destina-se a fornecer informações de aviso de tráfego em estradas de alta circulação. O planejamento de rotas com base no tráfego, por outro lado, requer cobertura de todas ou quase todas as estradas principais e, portanto, não é adequadamente suportado pelas tabelas de códigos de localização TMC conforme são formuladas atualmente.

Referência genérica

A referência genérica é uma tentativa de anexar dados a qualquer banco de dados de mapas, descobrindo informações de referência por meio de uma forma de correspondência de mapas. Os itens de dados específicos da função são atribuídos a elementos, como pontos, links ou áreas, que provavelmente apenas se aproximam dos elementos de mapa correspondentes em um banco de dados de mapa específico. Uma pesquisa no banco de dados do mapa é feita para o melhor ajuste. Para melhorar o processo de pesquisa, elementos vizinhos são estrategicamente anexados a cada elemento dado para ajudar a garantir que a solução correta seja encontrada em cada caso. Por exemplo, se o elemento do mapa for um link que conecta duas interseções, uma ou ambas as ruas transversais podem ser anexadas para fins de pesquisa. Felizmente, isso torna improvável uma correspondência incorreta. Embora o procedimento seja bastante heurístico, um padrão proposto chamado Agora descreve a estratégia para escolher elementos vizinhos para anexar.

Consórcio europeu ActMAP

Um consórcio europeu denominado ActMAP (Actualize Map) está (nas suas palavras) "a desenvolver mecanismos normalizados para actualizar o conteúdo da base de dados de mapas existente e permitir a anexação dinâmica de informações ao mapa digital de bordo". O consórcio ActMAP é composto por ERTICO (coordenador), BMW, CRF Fiat Research Center, DaimlerChrysler, Navigon, Navteq, Tele Atlas e Siemens VDO Automotive. Eles concluíram a maior parte de seu trabalho e publicaram diversos relatórios, os quais foram submetidos ao comitê ISO TC204 WG3 para padronização. Seus relatórios servem como um bom ponto de partida e referência para o trabalho deste projeto. Uma questão importante que seus relatórios abordam é lidar com a complexidade de vários fornecedores de mapas, usando formatos proprietários, juntamente com vários fornecedores de dados e várias versões de mapas nos veículos. Eles resolvem isso usando um formato de mapa intermediário aberto expresso com XML e baseado nos conceitos do padrão ISO GDF 4.0. Todas as modificações no banco de dados de um fornecedor são primeiro convertidas para este formato intermediário, armazenadas em um servidor e então convertidas para cada formato usado em veículos individuais. Eles assumem que cada carro tem um mapa de "linha de base" de um fornecedor de mapas e que essa linha de base define identificadores de referência (por exemplo, ID de segmento de mapa) para a maioria dos recursos a serem atualizados. Para recursos sem identificador de referência na linha de base, eles propõem o uso de uma referência "genérica" ​​que é descoberta heuristicamente usando correspondência de mapa, conforme descrito por um padrão proposto chamado AGORA

Uma questão importante não abordada diretamente pelo ActMAP é que para cada nova versão do banco de dados de mapa de um fornecedor, todos os IDs de referência são geralmente reatribuídos por um processo de compilação, que destrói qualquer correspondência com IDs de versões anteriores. Isso interfere seriamente na capacidade de usar atualizações incrementais para gerar uma nova versão de um banco de dados de mapas a partir de uma versão anterior. Outro problema não resolvido pelo ActMAP é a incapacidade de referenciar e caracterizar subseções de segmentos de estradas (por exemplo, curvas, morros, faixas de manobra, etc.) para atualizá-los.

Veja também

• Sistema de navegação automotivo
• Problema do caminho mais curto , classe de problemas e algoritmos empregados para obter uma rota de navegação de um banco de dados de mapas.
• Banco de dados geográfico
• Sistema de Informações Geográficas
• Sistema Global de Navegação por Satélite
• Sistema de transporte inteligente
• Mapa
• Navteq
• Ponto de interesse
• Banco de dados objeto-relacional
• Open Geospatial Consortium
• Mapeamento robótico
• Tele Atlas
• Telemática

Referências