Algorithmes pour faire correspondre les segments

Quels sont les meilleurs algorithmes pour faire correspondre les segments?

J'essaie de faire correspondre les segments correspondants de deux sources de carte, une moins précise mais avec des noms de segment et une plus précise sans nom de segment. Je souhaite appliquer semi-automatiquement les noms de segment à la carte plus précise.

L'algorithme demandé a une description assez vague car une "correspondance" n'est pas bien définie et de nombreux facteurs (orientation, longueur relative, distance) peuvent avoir un poids différent dans différents scénarios; Cependant, je suis à la recherche d'une connaissance de base sur les approches générales pour gérer ce problème.

Les implémentations de travail pour un environnement open-source (PostGIS, shapely, ...) sont les bienvenues.

Exemples de segments : Voir la description ci-dessous des images.

La distance de Hausdorff peut être utilisée: les segments correspondants peuvent être des segments «proches» en fonction de cette distance. Il est assez simple de calculer sur des segments.

Une implémentation java gratuite est disponible dans JTS - voir JTS Distance Package . Vous pouvez également consulter la JCS Conflation Suite (désormais abandonnée, copie des sources, par exemple sur https://github.com/oschrenk/jcs ).

Je ne sais pas quel serait le "meilleur", car cela dépendra des particularités de vos segments.

Une bonne approche généralement consiste à hacher les segments en informations géométriques cruciales . Cela comprendrait, au minimum, l'emplacement du centre (x, y), l'orientation (0 à 180 degrés) et la longueur. Avec des pondérations appropriées appliquées et une certaine précision de l'orientation (parce que 180 "revient" à 0), vous pouvez alors appliquer presque n'importe quel algorithme de regroupement statistique à la collection de tous les segments. ( K-means serait une bonne option, mais la plupart des méthodes hiérarchiques devraient bien fonctionner. De telles analyses en grappes ont tendance à être rapides et faciles à appliquer.) Idéalement, les segments se produiront par paires (ou singletons pour les segments sans correspondance) et le reste est facile.

Une façon de résoudre le problème d'orientation consiste à faire une copie des segments étiquetés. Ajoutez 180 degrés à l'orientation de la première copie, si elle est inférieure à 90, et soustrayez sinon 180 degrés de l'orientation. Cela agrandit votre jeu de données (évidemment) mais ne modifie en rien l'algorithme.

Les poids sont nécessaires car les différences de coordonnées, de longueurs et d'orientations peuvent signifier des choses très différentes concernant les similitudes de leurs segments correspondants. Dans de nombreuses applications, les différences entre les segments résultent des différences d'emplacement de leurs points d'extrémité. En tant qu'approximation approximative, nous pouvons nous attendre à ce que la variation typique de la longueur des segments soit à peu près la même que la variation typique entre leurs points d'extrémité. Par conséquent, les poids associés à x, y et à la longueur devraient être à peu près les mêmes. La partie délicate est la pondération de l'orientation, car l'orientation ne peut pas être assimilée à la distance et, pire encore, les segments courts seraient plus susceptibles d'être mal orientés que les segments longs. Envisagez une méthode d'essai et d'erreur qui équivaut à quelques degrés de désorientation par rapport à la taille d'un écart typique entre les segments, puis ajuste cela jusqu'à ce que la procédure semble bien fonctionner. Pour vous guider, laissezL être une longueur de segment typique. Un changement d'orientation d'un petit angle t degrés balaiera une distance d'environ L / 2 * t / 60 (les 60 approchent le nombre de degrés dans un radian), qui est L / 120 fois t . Cela suggère de commencer par des poids unitaires pour x, y et la longueur et un poids de L / 120 pour l'orientation.

En résumé , cette suggestion est la suivante:

1. Faites des copies des segments étiquetés (comme décrit dans le paragraphe sur l'amélioration de l'orientation).

2. Convertissez chaque segment en quadruple (x, y, longueur, orientation L / 120 *) où L est une longueur de segment typique.

3. Effectuez une analyse en grappes des quadruples. Utilisez un bon package statistique ( R est gratuit).

4. Utilisez la sortie d'analyse de cluster comme table de recherche pour associer des segments étiquetés à des segments non étiquetés à proximité.

J'ai travaillé sur un projet avec une exigence similaire il y a environ 5 ans. Il s'agissait de combiner les coordonnées des axes des rues (avec une précision de coordonnées relativement élevée) avec les liaisons du réseau de circulation du système de surveillance des performances routières (HPMS).

À l'époque, la FHWA ne fournissait aucun outil pour faire ce genre de chose. Cela peut avoir changé, vous voudrez peut-être vérifier. Même si vous ne travaillez pas avec des données routières, les outils peuvent toujours être pertinents.

Je l'ai écrit avec ArcGIS, mais l'algorithme devrait fonctionner en open source , tant qu'il fournit des capacités de traçage similaires à ISegmentGraph :

// features is a collection of features with higher geometry
// Links are a collection features with attributes but low res geometry
For each Link in lowResFeatureclass
    point startPoint = SnapToClosestPoint(Link.StartPoint, hiResfeatures);
    if(startPoint == null)
       continue;
    point endPoint = SnapToClosest(Link.EndPoint, hiResfeatures);
    if(endPoint == null)
       continue;
    polyline trace = Trace(hiResfeatures,startPoint,endPoint);
    if(polyline != null)
    {
        // write out a link with high precision polyline
        Write(Link,polyline);
    }
Next Link

Voici une idée

Si vous déchirez l'une des chaînes de lignes pour comparer et tester si les points verticaux sont à une certaine distance de l'autre chaîne pour comparer, vous pouvez contrôler le test de plusieurs façons.

ces exemples fonctionnent dans PostGIS (qui pourrait deviner :-))

Premièrement, si nous disons qu'il existe une correspondance si tous les points de sommet d'une chaîne de lignes dans le tableau_1 sont de 0,5 mètre (unités de carte) ou plus proches d'une chaîne de lignes dans la table_2:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points,
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(*)=num_of_points;

Ensuite, nous pouvons dire qu'il existe une correspondance si plus de 60% des vertex_points dans une chaîne de lignes dans le tableau_1 sont à distance d'une chaîne de caractères dans la table_2

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)/num_of_points::float > 0.6

Ou nous pouvons accepter qu'un point n'est pas dans la plage:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)-num_of_points <= 1;

Vous devrez également exécuter la requête avec table_1 et table_2 dans des rôles inversés.

Je ne sais pas à quelle vitesse ça va être. ST_Dumppoints est actuellement une fonction sql dans PostGIS et non une fonction C, ce qui la rend plus lente qu'elle ne devrait l'être. Mais je pense que ce sera assez rapide de toute façon.

Les index spatiaux aideront beaucoup ST_Dwithin à être efficaces.

HTH Nicklas

J'ai écrit du code pour gérer la correspondance des segments de ligne bâclée (et les chevaucher) dans Boundary Generator. J'ai écrit les mathématiques (assez élémentaires) derrière cela ici: http://blog.shoutis.org/2008/10/inside-boundary-generator-computational.html . Le code est open source et lié à partir de ce billet de blog.

Le code suit une approche vraiment simple:

• Un test segment-segment qui vous dira si deux segments de ligne se chevauchent dans les tolérances d'angle et de distance données, et la quantité de chevauchement.
• Un index spatial quick'n'dirty qui élimine la nécessité de tester chaque segment de ligne de l'ensemble de données par rapport à tous les autres segments de ligne de l'ensemble de données.

Le principal avantage de cette approche est que vous obtenez des boutons bien précis pour un angle, des distances et une longueur de chevauchement valides; à la baisse, ce n'est pas un moyen de mesurer généralement la similitude de deux segments de ligne, il est donc beaucoup plus difficile, par exemple, de faire un regroupement statistique pour déterminer les correspondances probables - vous êtes coincé avec les boutons précis.

Remarque: je suppose qu'avec suffisamment de côtelettes SQL, vous pouvez entasser le test segment-segment dans une clause WHERE ... :)

À votre santé!

J'ai implémenté un prototype approximatif de correspondance de carte ici , qui est relativement facile à utiliser. Il est basé sur le moteur de routage open source et écrit en Java. L'algorithme utilisé est décrit ici .