Mapear links e idéias correspondentes? [fechadas]

44

Estou usando o OpenStreetMap e sua rede de estradas vetorial e gostaria de implementar um algoritmo de correspondência de mapas.

Atualmente, sou capaz, para cada posição GPS, de recuperar o segmento de estrada mais próximo e calcular a projeção dessa posição para esse segmento, como nesta imagem (o pino vermelho é a posição pura do GPS, em azul o segmento mapeado e em verde o posição mapeada):

insira a descrição da imagem aqui

No entanto, devido à falta de precisão do GPS, algumas vezes a posição mapeada salta de segmento para outro e pode fornecer alguma posição mapeada inconsistente de tempos em tempos.

Meu algoritmo atual é muito básico: da posição pura do GPS, pego o segmento mais próximo e decido que a posição correspondente mapeada está nesse. Eu sei que isso pode ser realmente melhorado.

Eu posso imaginar que levar em conta a direção do veículo melhorará a correspondência do mapa, mas você conhece alguma outra abordagem que me permita melhorar meu correspondente do mapa?

Eu procuro qualquer link e / ou software de código aberto?

yonel
fonte
4
você pode adicionar um círculo - o Google usa a recepção de células e cria um círculo azul claro para mostrar sua localização aproximada. Seu aplicativo parece bom, bom trabalho. Se você possui os dados vetoriais, pode ajustar para a linha mais próxima do seu ponto de GPS - veja post de Paul Ramsey blog.cleverelephant.ca/2008/04/snapping-points-in-postgis.html
Mapperz
4
A palavra-chave que você está procurando é Correspondência de mapas. Grande assunto.
Uffe Kousgaard 18/04
11
Uffe está certo, corresponde ao mapa. Verifique este documento para algumas abordagens: cens.ucla.edu/~mhr/cs219/maps/white00.pdf
lexicore
Obrigado! Lexicore, o papel está sendo enviado para minha impressora enquanto digito isso. Hora de obter uma visão geral. Obrigado pelo link.
scrrr
Eu melhoraria o algoritmo, tentando também pegar a estrada real, em vez de apenas os vértices.
Devdatta Tengshe

Respostas:

11

A projeção de pontos na linha como você já está fazendo é possível diretamente no PostGIS. Eu escrevi sobre há algum tempo atrás, aqui

Mas, para resolver seu problema quando os pontos estiverem mais próximos do segmento errado do que o segmento certo, talvez essa seja uma abordagem possível.

  1. Construa uma cadeia de linhas dos pontos
  2. Experimente as soluções sugeridas em Algoritmos para combinar segmentos para coincidir com a linha inteira, em vez de apenas ponto a ponto
Nicklas Avén
fonte
Obrigado pela sua resposta. A projeção está boa: já estou fazendo isso (não via ST_Closest porque não está disponível no espaço que estou usando, mas tudo bem). Eu também estava apenas olhando para a pergunta que você mencionou e aprendeu sobre a existência dessa "distância Hausdorff" que pode ser interessante de se ver.
yonel
10

Depois de ler sua pergunta e as várias respostas, fiquei interessado neste problema. Depois de ler um pouco os algoritmos de correspondência de mapas, entendi o seguinte:

  • Para corresponder o local do GPS à estrada, você precisa dos dados reais da estrada em formato vetorial
  • Ajudará se você tiver pesos diferentes para estradas diferentes. Portanto, as chances de um ponto coincidir com uma rodovia serão maiores e, em seguida, coincidir com uma linha lateral.
  • Você precisa levar o histórico e a velocidade da leitura dos gps. Por exemplo, se o ponto gps estiver correspondendo à faixa lateral por um longo tempo, você deve levar isso em conta e não corresponder diretamente à rodovia. -A correspondência real é feita usando uma variedade de técnicas estatísticas.

Para leituras adicionais, sugiro o seguinte:

Devdatta Tengshe
fonte
Sim, eu também estava lendo e comecei a brincar com a implementação de um algoritmo simples que eu posso expandir. Até agora, baixei alguns dados do OSM e estou brincando com a melhor maneira de armazená-los (e acessá-los) para meus propósitos. É um tópico interessante, eu acho. :) Atualizarei esta pergunta assim que tiver algo que funcione. Além disso, obrigado pelos links!
precisa
Eu tomaria cuidado ao usar pesos "Portanto, as chances de um ponto coincidir com uma rodovia serão maiores, do que com uma linha lateral". ... Isso depende dos dados de entrada e pode dar muito errado.
Subterrâneo
@ Devdatta, recebo um 404 no segundo link. Em vez de eu apenas editá-lo, você tem um link alternativo?
Chau
Não tenho um link de acesso gratuito a esse artigo. Mas se você estiver em uma configuração acadêmica. O artigo deve estar disponível após uma busca rápida
Devdatta Tengshe
@Chau: Encontrei o PDF em: researchgate.net/profile/Alain_Kornhauser/publication/…
Devdatta Tengshe
7

Respondendo à minha própria pergunta!

1- Um bom .pdf que acabei de encontrar sobre esse assunto:

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

que também está vinculado a uma implementação de código-fonte aberto em C ++ do correspondente de mapa descrito no documento: http://eden.dei.uc.pt/~camara/files/mgemma.zip
(este é um correspondente de mapa offline, meu entendimento é que calcule as posições correspondentes do mapa com o caminho INTEIRO como entrada e não possa fazê-lo rapidamente para cada posição).

2- Então, acabei de ler este em profundidade e, na minha opinião, é realmente bom: https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/4860/1/velaga.pdf "Developing um algoritmo de MapMatching topológico baseado em peso aprimorado para sistemas de transporte inteligentes "
O algoritmo é explicado claramente e os valores de ajuste de peso também são fornecidos no documento.

yonel
fonte
4

Há muito trabalho sobre correspondência de mapas; veja este documento para uma breve pesquisa de alguns trabalhos bastante recentes (antes de 2007). Mais recentemente, abordagens baseadas em modelos ocultos de Markov parecem ter um desempenho muito bom em circunstâncias normais. Por exemplo, confira este artigo de 2009. A idéia e o modelo são bastante simples e não devem lhe dar muito trabalho para implementar, mesmo que você não esteja familiarizado com os HMMs (nesse caso, não entre em pânico, há muitos de tutoriais e apresentações on-line)

usuario
fonte
11
Acabei de perceber que o Projeto Barefoot que mencionei na minha resposta é baseado no artigo que o @Nick recomenda.
nik
4

O método também é chamado de "combinação de vetores". Existe uma página Wiki dedicada ( http://wiki.openstreetmap.org/wiki/Conflation ), que fornece uma visão geral e lista pacotes de software (código-fonte aberto) para executar a combinação de vetores de estradas, como "plugin de conflação JOSM", "fusão do Potlatch 2" ferramenta "," RoadMatcher "(para OpenJUMP) e outros.

markusN
fonte
11
Eu sempre pensei que a fusão é algo que você faz com duas camadas de linha, em vez de combinar pontos em linhas. É realmente o mesmo?
Subterrâneo
4

Para algoritmos de correspondência de mapa, isso depende se você precisa de processamento em tempo real ou offline. No caso posterior, algos de ponta podem processar ~ 1000 pontos por segundo. Os requisitos de memória dependem da cobertura, é claro. Conseguimos reduzir a rede rodoviária OSM do planeta em aproximadamente 16 Gb para esse fim.

Além disso, você precisa distinguir a correspondência de mapa da inferência de caminho : estes são dois processos separados, dependendo se você possui dados de alta ou baixa frequência. Quando você tem relativamente poucos pontos (por exemplo, 1 dado a cada quilômetro no contexto urbano), é uma inferência de caminho, pois geralmente há alguma suposição a ser feita para adivinhar para onde o dispositivo está viajando. A inferência de caminho geralmente é mais difícil, mas está obtendo menos problemas com dispositivos modernos / preço de aquisição de dados.

Você pode verificar meu perfil em busca de uma API que faça a correspondência de mapas diretamente no OSM: ela usa correspondência topológica e funciona bem com dados flutuantes de carros, por exemplo.

Fabrice Marchal
fonte
Você pode expandir os algoritmos que está usando? E como a redução do tamanho da rede rodoviária ajuda?
Devdatta Tengshe
Menos cobertura = rede menor para guardar na memória. Isso acelera um pouco a computação. Referências: trb.metapress.com/content/p31485vw72645686
Fabrice Marchal
3

O Strava Slide descreve como os dados cumulativos da via em uma rede de estradas podem se comportar como "vales" e como a rota proposta "se encaixaria" como se fosse um cordão de contas.

heltonbiker
fonte
2

Depois de testar a maioria dos frameworks mencionados, encontrei o Barefoot e posso realmente recomendá-lo. Ele usa modelos markov ocultos como uma abordagem probabilística de correspondência de mapas (detalhes em seu artigo "Colocando o carro no mapa" ) e é implementado em Java. É de código aberto e desenvolvido ativamente pelo departamento CarIT da BMW.

nik
fonte
2

O assunto é chamado de correspondência de mapa. Mas como uma primeira aproximação muito boa, provavelmente é boa o suficiente apenas procurar os pontos mais próximos para cada ponto de GPS (sem correções adivinhando o caminho correto).

Meu projeto de código aberto chamado graphhopper não é algo que funciona para iOS ( atualização : agora também funciona no iOS), nem possui um aplicativo Android totalmente funcional para o que você deseja. Mas você pode usar a versão do servidor para criar um aplicativo iOS ou usar a demonstração offline do Android como um começo. Soltei o algoritmo de correspondência de mapas aqui , apenas um protótipo bruto, mas funciona surpreendentemente bem.

Karussell
fonte
1

Tente adquirir alguns bons dados de teste. Use um GPS de registro de rastreamento com maior precisão adicional, além dos pontos de registro no dispositivo de destino. Isso identificará erros no GPS e nos dados OSM subjacentes. Conhecer limites sensatos facilitará muito o design do algoritmo.

Matthew Snape
fonte
1

Se você pode obter dados de estradas para sua região, pode estar interessado em Snap automático em massa com o FOSS

Dependendo se você deseja plotar dados em tempo real ou se está planejando realizar algum pós-processamento no seu PC posteriormente, o GRASS pode ser útil.

Michal Zimmermann
fonte
1

Eu encontrei uma API que pode apenas fazer o trabalho sem ter que passar pelo esforço de desenvolver uma solução própria imediatamente.

Eles usam dados OSM para fazer a correspondência de mapas. Eles também têm uma página de demonstração que permite o upload de arquivos GPX para ver como isso pode funcionar para você.

Arthur McFlint
fonte
-1

Você não precisa melhorar necessariamente a qualidade dos seus dados. O uso de um algoritmo topológico com uma rede de estradas na memória melhorará consideravelmente sua correspondência. Verifique as referências: http://trb.metapress.com/content/p31485vw72645686

Fabrice Marchal
fonte