Similitud entre cadenas de líneas

Question

Tengo un número de pistas grabadas por un GPS, que más formalmente se puede describir como un número de cadenas de líneas.

Ahora, algunas de las pistas grabadas pueden ser grabaciones de la misma ruta, pero debido a inaccesidades en el sistema GPS, el hecho de que las grabaciones se hicieron en ocasiones separadas y que podrían haberse grabado viajando a diferentes velocidades, no coincidirán perfectamente, pero aún se ven lo suficientemente cerca cuando un humano lo ve en un mapa para determinar que en realidad es la misma ruta que se ha registrado.

Quiero encontrar un algoritmo que calcule la similitud entre dos cadenas de líneas. He creado algunos métodos propios para hacer esto, pero me gustaría saber si este es un problema que ya tiene buenos algoritmos para resolverlo.

¿Cómo calculo la similitud, dado que medios similares representan la misma ruta en un mapa?

Editar: Para aquellos seguro de lo que estoy hablando, por favor vaya a este enlace para una definición de lo que es una cadena de líneas: http://msdn.microsoft.com/en-us/library/bb895372.aspx - estoy no preguntar sobre cadenas de caracteres.

Answer 1

Calcule el Fréchet distance en cada par de pistas. La distancia se puede usar para medir la similitud de tus pistas.

Alerta matemática: Fréchet fue un pionero en el campo de metric space que es relevante para su problema.

Answer 2

Agregaría un buffer alrededor de la primera línea basado en el error probable estimado, y luego determinaría si la segunda línea encaja completamente dentro del buffer.

Answer 3

Para determinar "la misma ruta", cree el conjunto mínimo de vectores de ruta normalizados, calcule las diferencias de potencia total y compare el total con una medida de calidad.

1. Normalizar los puntos GPS sobre la longitud total de la ruta,
2. caminan los vectores de los caminos juntos, creando un nuevo conjunto de vectores de trayectoria para cada trayecto basado en el vector más corto en cada punto de referencia,
3. calcular el las diferencias de potencia total entre los puntos finales de cada vector en la ponderación de trayectos normalizados para la longitud del vector, y
4. comparar con una medida de calidad.

Ajuste la potencia de las diferencias (comenzando con, por ejemplo, las diferencias al cuadrado) y la medida de calidad (es decir, como un porcentaje de las diferencias de potencia total) visualmente. Este algoritmo produce una medida continua de la calidad del partido ruta, así como un resultado binario (¿Son los caminos de la misma?)

Paul Tomblin dijo: Yo añadiría un buffer alrededor de la primera línea de base en el estimado error probable, y luego determina si la segunda línea se ajusta completamente a dentro del buffer.

Puede modificar el algoritmo a medida que se comparan los puntos finales vectoriales normalizados. Podrías determinar si alguna diferencia de punto final estaba por encima de cierto tamaño (implementando la idea de buffer de Paul) o quizás, si los puntos finales estaban fuera del "buffer", usa ese hecho para ignorar esa diferencia de punto final, permitiendo una comparación ignorando viajes laterales.

Answer 4

De hecho estoy del lado de la persona (Aaron F) que dijo que podría estar interesado en el problema de distancia de Levenshtein (y citó this). Su respuesta me parece ser la mejor hasta ahora.

Más específicamente, la distancia de Levenshtein (también llamada distancia de edición) no mide estrictamente la distancia de carácter por carácter, sino que también le permite realizar inserciones y eliminaciones. El mejor algoritmo para esta medida de distancia se puede calcular en tiempo cuadrático (bastante lento si sus cadenas son largas), pero los biólogos computacionales tienen una heurística bastante buena para esto, que podría interesarle por sí solo. Consulte BLAST y FASTA.

En su problema, parece que se trata de diferencias entre series de números, y le importan los números. Si proporciona más información, es posible que pueda dirigirlo a la variante correcta de BLAST/FASTA/etc para sus propósitos. En cualquier caso, puede considerar adaptar BLAST y FASTA para sus necesidades. Son bastante simples.

1: http://en.wikipedia.org/wiki/Levenshtein_distance, http://www.nist.gov/dads/HTML/Levenshtein.html

Answer 5

Se puede caminar a lo largo de cada punto (Pa) de LineString A y medir la distancia desde Pa a la línea del segmento más próximo de LineString B, promediando cada una de estas distancias.

Este no es un método rápido o perfecto, pero debería ser capaz de dar un número útil y es bastante rápido de implementar.

¿Las cadenas de líneas comienzan y terminan en puntos similares, o son de extensiones muy diferentes?

Answer 6

Si considera que una cadena de una sola línea es una secuencia de puntos [x, y] (o [x, y, z]), puede calcular la similitud entre cada par de cadenas de líneas utilizando el algoritmo Needleman-Wunsch . Como se describe en el artículo de Wikipedia al que se hace referencia, el algoritmo Needleman-Wunsch requiere una "matriz de similitud" que define la distancia entre un par de puntos. Sin embargo, sería fácil usar una función en lugar de una matriz. En su caso, podría simplemente usar la función 2D Euclidean distance (o una función Euclidiana 3D si sus puntos tienen elevación) para proporcionar la distancia entre cada par de puntos.