Mapa de enlaces e ideas? [cerrado]

44

Estoy usando OpenStreetMap y su red vial vectorial y me gustaría implementar un algoritmo de correspondencia de mapas.

Actualmente, para cada posición GPS, puedo recuperar el segmento de carretera más cercano y calcular la proyección de esta posición a ese segmento, como en esta imagen (el pin rojo es la posición GPS pura, en azul el segmento mapeado y en verde el posición mapeada):

ingrese la descripción de la imagen aquí

Sin embargo, debido a la falta de precisión del GPS, a veces la posición asignada salta de un segmento a otro y puede proporcionar alguna posición asignada inconsistente de vez en cuando.

Mi algoritmo actual es muy básico: desde la posición GPS pura, obtengo el segmento más cercano y decido que la posición asignada asignada está en este. Sé que esto se puede mejorar realmente.

Me imagino que tomar en cuenta la dirección del vehículo mejorará la correspondencia del mapa, pero ¿conoce algún otro enfoque que me permita mejorar mi correspondencia de mapas?

Busco algún enlace y / o software de código abierto?

yonel
fuente
44
podría agregar un círculo: Google usa la recepción celular y crea un círculo azul claro para mostrar su ubicación aproximada. Tu aplicación se ve bien, buen trabajo. Si tiene los datos vectoriales, puede ajustar a la línea más cercana desde su punto GPS - vea la publicación de Paul Ramsey blog.cleverelephant.ca/2008/04/snapping-points-in-postgis.html
Mapperz
44
La palabra clave que está buscando es Map Matching. Gran tema.
Uffe Kousgaard
1
Uffe tiene razón, correspondencia de mapas. Consulte este documento para conocer algunos enfoques: cens.ucla.edu/~mhr/cs219/maps/white00.pdf
lexicore
¡Gracias! lexicore, el papel se envía a mi impresora mientras escribo esto. Es hora de obtener una visión general. Gracias por el enlace.
scrrr
Mejoraría el Algoritmo, al intentar también ajustar el camino real, en lugar de solo los vértices.
Devdatta Tengshe

Respuestas:

11

La proyección de puntos en la línea como ya lo está haciendo es posible hacerlo directamente en PostGIS. Escribí sobre hace algún tiempo, aquí

Pero para resolver su problema cuando los puntos están más cerca del segmento incorrecto que el segmento correcto, quizás este sea un posible enfoque.

  1. Construye una cadena lineal de los puntos
  2. Pruebe las soluciones sugeridas en Algoritmos para que los segmentos coincidan con la línea completa en lugar de solo punto por punto
Nicklas Avén
fuente
Gracias por su respuesta. La proyección está bien: ya lo estoy haciendo (no a través de ST_Closest porque no está disponible en espacial que estoy usando, pero está bien). También estaba mirando la pregunta que mencionó y aprendí sobre la existencia de esta "distancia de Hausdorff" que puede ser interesante de ver.
yonel
10

Después de leer su pregunta y las diversas respuestas, me interesé en este problema. Después de leer un poco sobre algoritmos de correspondencia de mapas, he entendido lo siguiente:

  • Para hacer coincidir la ubicación gps con la carretera, necesita los datos reales de la carretera en formato vectorial
  • Ayudará si tiene pesos diferentes para caminos diferentes. Por lo tanto, las posibilidades de que un punto coincida con una carretera serán mayores, que coincidir con una línea lateral.
  • Necesitas tomar el historial y la velocidad de la lectura gps. Por ejemplo, si el punto gps ha coincidido con el carril lateral durante mucho tiempo, debe tenerlo en cuenta y no hacerlo coincidir directamente con la carretera. -La coincidencia real se realiza utilizando una variedad de técnicas estadísticas.

Para leer más, sugiero lo siguiente:

Devdatta Tengshe
fuente
Sí, también estaba leyendo y comencé a jugar con la implementación de un algoritmo simple que puedo ampliar. Hasta ahora he descargado algunos datos de OSM y estoy jugando con la mejor manera de almacenarlos (y acceder a ellos) para mis propósitos. Es un tema interesante, creo. :) Actualizaré esta pregunta una vez que tenga algo que funcione. Además, gracias por los enlaces!
scrrr
Sería cuidadoso con el uso de pesas "Entonces, las posibilidades de que un punto coincida con una carretera serán mayores, que con una línea lateral". ... Eso depende de los datos de entrada y podría salir muy mal.
oscuro
@Devdatta, obtengo un 404 en el segundo enlace. En lugar de que solo lo edite, ¿tiene un enlace alternativo?
Chau
No tengo un enlace de acceso gratuito a ese artículo. Pero si estás en una configuración académica. El artículo debería estar disponible después de una búsqueda rápida
Devdatta Tengshe
@Chau: Encontré el PDF en: researchgate.net/profile/Alain_Kornhauser/publication/…
Devdatta Tengshe
7

¡Respondiendo a mi propia pregunta!

1- Un buen .pdf que acabo de encontrar sobre este tema:

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

que también se vincula a una implementación de código abierto en C ++ del mapa de correspondencia descrito en el documento: http://eden.dei.uc.pt/~camara/files/mgemma.zip
(este es un mapa de correspondencia fuera de línea, entiendo que calcula las posiciones coincidentes del mapa con la ruta ENTERA como entrada y no puede hacerlo sobre la marcha para cada posición).

2- Entonces, acabo de leer esto en profundidad y es realmente bueno en mi opinión: https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/4860/1/velaga.pdf "En desarrollo un algoritmo de mapeo topológico basado en peso mejorado para sistemas de transporte inteligentes "
El algoritmo se explica claramente y los valores de ajuste de peso también se proporcionan en el documento.

yonel
fuente
4

Hay mucho trabajo sobre correspondencia de mapas. Vea este documento para una breve encuesta de algunos trabajos bastante recientes (antes de 2007). Más recientemente, los enfoques basados ​​en modelos ocultos de Markov parecen funcionar bastante bien en circunstancias normales. Por ejemplo, consulte este documento de 2009. La idea y el modelo son bastante simples y no deberían darle muchos problemas para implementar, incluso si no está familiarizado con los HMM (en cuyo caso, no se asuste, hay muchos de tutoriales e introducciones en línea)

Mella
fuente
1
Me acabo de dar cuenta de que el Proyecto Descalzo que mencioné en mi respuesta se basa en el documento que @Nick recomienda.
nik
4

El método también se llama "fusión de vectores". Hay una página Wiki dedicada ( http://wiki.openstreetmap.org/wiki/Conflation ) que ofrece una descripción general y listas de paquetes de software (Open Source) para realizar la combinación de vectores de carreteras como "JOSM conflation plugin", "Potlatch 2 merging herramienta "," RoadMatcher "(para OpenJUMP) y otros.

markusN
fuente
1
Siempre pensé que la combinación es algo que haces con dos capas de línea en lugar de unir puntos en líneas. ¿Es realmente lo mismo?
oscuro
4

Para los algoritmos de correspondencia de mapas, depende si necesita un procesamiento en tiempo real o fuera de línea. En el último caso, los algos de última generación pueden procesar ~ 1000 puntos por segundo. Los requisitos de memoria dependen de la cobertura, por supuesto. Hemos logrado exprimir la red de carreteras OSM del planeta en aproximadamente 16 Gb para ese propósito.

Además, debe distinguir la coincidencia de mapas de la inferencia de ruta : estos son dos procesos separados dependiendo de si tiene datos de alta o baja frecuencia. Cuando tiene relativamente pocos puntos (p. Ej., 1 dato por kilómetro en el contexto urbano), es inferencia de ruta, ya que generalmente se debe hacer una suposición para adivinar dónde viaja el dispositivo. La inferencia de ruta suele ser más difícil, pero cada vez tiene menos problemas con los dispositivos modernos / precio de adquisición de datos.

Puede verificar mi perfil para una API que hace correspondencias de mapas directamente en OSM: utiliza coincidencias topológicas y funciona bien con datos flotantes de automóviles, por ejemplo.

Fabrice Marchal
fuente
¿Puedes ampliar los algoritmos que estás usando? ¿Y cómo ayuda la disminución del tamaño de la red vial?
Devdatta Tengshe
Menos cobertura = red más pequeña para mantener en la memoria. Eso acelera un poco la computación. Referencias: trb.metapress.com/content/p31485vw72645686
Fabrice Marchal
3

Strava Slide describe cómo los datos de seguimiento acumulados en una red de carreteras pueden comportarse como "valles", y cómo la ruta propuesta "encajaría" como si fuera una cadena de cuentas.

heltonbiker
fuente
2

Después de probar la mayoría de los frameworks mencionados anteriormente, encontré Barefoot y realmente puedo recomendarlo. Utiliza modelos ocultos de Markov como un enfoque probabilístico de correspondencia de mapas (detalles en su documento "Poner el automóvil en el mapa" ) y se implementa en Java. Es de código abierto y está activamente desarrollado por el Departamento de CarIT de BMW.

nik
fuente
2

El tema se llama correspondencia de mapas. Pero como primera aproximación muy buena, probablemente sea lo suficientemente bueno como para buscar los puntos más cercanos para cada punto gps (sin ninguna corrección que adivine la forma correcta).

Mi proyecto de código abierto llamado graphhopper no es algo que funcione para iOS ( actualización : ahora también funciona en iOS), ni tiene una aplicación de Android totalmente funcional para lo que quieres. Pero podría usar la versión del servidor para crear una aplicación de iOS o usar la demostración de Android sin conexión como un comienzo. He lanzado el algoritmo de correspondencia de mapas aquí , solo un prototipo aproximado, pero funciona sorprendentemente bien.

Karussell
fuente
1

Intente y obtenga algunos buenos datos de prueba. Utilice un GPS de registro de seguimiento de mayor precisión adicional, además de los puntos de registro en su dispositivo objetivo. Esto identificará errores en el GPS y en los datos OSM subyacentes. Conocer umbrales sensibles hará que sea mucho más fácil diseñar el algoritmo.

Matthew Snape
fuente
1

Si puede obtener datos de carreteras para su región, podría estar interesado en el ajuste automático masivo con FOSS

Dependiendo de si desea trazar datos en tiempo real, o si planea realizar un procesamiento posterior en su PC después, GRASS podría ser de ayuda.

Michal Zimmermann
fuente
-1

No necesita mejorar necesariamente la calidad de sus datos. El uso de un algoritmo topológico con una red de carreteras en memoria mejorará considerablemente su correspondencia. Verifique las referencias: http://trb.metapress.com/content/p31485vw72645686

Fabrice Marchal
fuente