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):
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?
Respostas:
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.
fonte
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 leituras adicionais, sugiro o seguinte:
fonte
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.
fonte
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)
fonte
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.
fonte
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.
fonte
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.
fonte
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.
fonte
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.
fonte
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.
fonte
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.
fonte
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ê.
fonte
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
fonte