Similarité entre les lignes

Question

J'ai un certain nombre de pistes enregistrées par GPS, qui peuvent être décrites de manière plus formelle comme un nombre de lignes.

Maintenant, certaines des pistes enregistrées peuvent être des enregistrements du même itinéraire, mais à cause des inexactitudes du système GPS, du fait que les enregistrements ont été réalisés à des occasions différentes et qu'ils ont peut-être été enregistrés voyageant à des vitesses différentes, ne correspondra pas parfaitement, mais restera quand même suffisamment proche pour être visualisé sur une carte par un humain afin de déterminer qu'il s'agit en fait du même itinéraire que celui qui a été enregistré.

Je veux trouver un algorithme qui calcule la similarité entre deux lignes. J'ai mis au point des méthodes maison pour le faire, mais j'aimerais savoir s'il s'agit d'un problème qui a déjà de bons algorithmes pour le résoudre.

Comment calculeriez-vous la similarité, étant donné que des moyennes similaires représentent le même chemin sur une carte?

Modifier: Pour ceux qui ne savent pas de quoi je parle, consultez ce lien pour obtenir une définition de la définition d'une chaîne: http://msdn.microsoft.com/en-us/library/bb895372.aspx - Je suis pas poser des questions sur les chaînes de caractères.

Answer 1

Calculez la distance de Fréchet sur chaque paire de pistes. La distance peut être utilisée pour évaluer la similarité de vos traces.

Alerte mathématique: Fréchet a été un pionnier dans le domaine des espace métrique qui correspond à votre problème.

Answer 2

J'ajouterais un tampon autour de la première ligne en fonction de l'erreur probable estimée, puis déterminerais si la deuxième ligne tient entièrement dans le tampon.

Answer 3

Pour déterminer " même itinéraire, " créez l'ensemble minimal de vecteurs de chemin normalisé, calculez les différences de puissance totale et comparez le total à une mesure de qualité.

1. Normaliser les points de cheminement GPS sur la longueur totale du chemin,
2. parcourez ensemble les vecteurs des chemins en créant un nouvel ensemble de vecteurs de chemin pour chaque chemin basé sur le vecteur le plus court à chaque point de cheminement,
3. calcule les différences de puissance totales entre les extrémités de chaque vecteur dans les chemins normalisés pondérant la longueur du vecteur, et
4. comparer à une mesure de qualité.

Réglez visuellement la puissance des différences (à commencer par, par exemple, les différences au carré) et la mesure de la qualité (en pourcentage des différences de puissance totale). Cet algorithme produit une mesure de qualité continue de la correspondance de chemin ainsi qu’un résultat binaire (les chemins sont-ils les mêmes?)

  

Paul Tomblin a déclaré: J'ajouterais un tampon   autour de la première ligne en fonction de la   erreur probable estimée, puis   déterminer si la deuxième ligne correspond   entièrement dans le tampon.

Vous pouvez modifier l'algorithme lors de la comparaison des points d'extrémité de vecteur normalisés. Vous pouvez déterminer si une différence de point de terminaison dépasse une certaine taille (en appliquant l'idée de tampon de Paul) ou peut-être, si les points de terminaison se trouvent en dehors du "tampon", utilisez ce fait pour ignorer cette différence de points de terminaison, permettant ainsi une comparaison en ignorant les déplacements latéraux .

Answer 4

Vous pouvez marcher le long de chaque point (Pa) de LineString A et mesurer la distance entre Pa et le segment de ligne le plus proche de LineString B, en faisant la moyenne de chacune de ces distances.

Ce n'est pas une méthode rapide ou parfaite, mais devrait pouvoir utiliser un nombre utile et est assez rapide à mettre en œuvre.

Les chaînes de lignes commencent-elles et se terminent-elles à des points similaires, ou ont-elles une étendue très différente?

Answer 5

Si vous considérez une chaîne de ligne unique comme une séquence de points [x, y] (ou de points [x, y, z]), vous pouvez calculer la similarité entre chaque paire de chaînes de ligne à l'aide de Algorithme de Needleman-Wunsch . Comme décrit dans l'article de Wikipedia référencé, l'algorithme de Needleman-Wunsch nécessite une "matrice de similarité". qui définit la distance entre une paire de points. Cependant, il serait facile d’utiliser une fonction au lieu d’une matrice. Dans votre cas, vous pouvez simplement utiliser la fonction 2D Distance euclidienne (ou une fonction euclidienne 3D si points ont une altitude) pour indiquer la distance entre chaque paire de points.

Answer 6

En fait, je me range aux côtés de la personne (Aaron F) qui a dit que le problème de la distance de Levenshtein pourrait vous intéresser (et cité ceci ). Sa réponse me semble être la meilleure à ce jour.

Plus précisément, la distance de Levenshtein (également appelée distance d'édition) ne mesure pas strictement la distance caractère par caractère mais vous permet également d'effectuer des insertions et des suppressions. Le meilleur algorithme pour cette mesure de distance peut être calculé en temps quadratique (assez lent si vos chaînes sont longues), mais les biologistes informaticiens ont de très bonnes méthodes heuristiques, qui pourraient vous intéresser par elles-mêmes. Découvrez BLAST et FASTA .

Dans votre problème, il semble que vous ayez affaire à des différences entre des chaînes de nombres et que vous vous souciez de ces chiffres. Si vous donnez plus d'informations, je pourrai peut-être vous indiquer la bonne variante de BLAST / FASTA / etc. Dans tous les cas, vous pourriez envisager d’adapter BLAST et FASTA à vos besoins. Ils sont assez simples.

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