Algorytmy dopasowywania segmentów

Jakie są najlepsze algorytmy do dopasowania segmentów?

Próbuję dopasować odpowiadające segmenty z dwóch źródeł mapy, jedno mniej dokładne, ale z nazwami segmentów, a drugie bardziej dokładne bez nazw segmentów. Chcę półautomatycznie zastosować nazwy segmentów do dokładniejszej mapy.

Żądany algorytm ma dość niejasny opis, ponieważ „dopasowanie” nie jest dobrze zdefiniowane, a wiele czynników (orientacja, długość względna, odległość) może mieć różną wagę w różnych scenariuszach; Jednak szukam podstawowej wiedzy na temat ogólnych podejść do rozwiązywania tego problemu.

Serdecznie witamy działające implementacje środowiska open source (PostGIS, foremne, ...).

Przykładowe segmenty : patrz opis poniżej zdjęć.

Można zastosować odległość Hausdorffa : pasujące segmenty mogą być segmentami „bliskimi” zgodnie z tą odległością. Obliczanie segmentów jest dość proste.

Darmowa implementacja Java jest dostępna w JTS - patrz Pakiet JTS Distance . Możesz także zajrzeć na JCS Conflation Suite (teraz porzucony, kopia źródeł np. Na https://github.com/oschrenk/jcs ).

Nie wiem, co byłoby „najlepsze”, ponieważ będzie to zależeć od danych szczegółowych Twoich segmentów.

Ogólnie dobrym podejściem jest łączenie segmentów w kluczowe informacje geometryczne . Obejmuje to co najmniej lokalizację środka (x, y), orientację (od 0 do 180 stopni) i długość. Przy zastosowaniu odpowiednich wag i pewnej zmienności orientacji (ponieważ 180 „zawija się” z powrotem do zera), możesz następnie zastosować prawie dowolny algorytm statystycznego grupowania do zbioru wszystkich segmentów. (Średnia K byłaby dobrym rozwiązaniem, ale większość metod hierarchicznych powinna działać dobrze. Takie analizy skupień są zwykle szybkie i łatwe do zastosowania.) Idealnie segmenty będą występować w parach (lub singletonach dla niedopasowanych segmentów), a reszta jest proste.

Jednym ze sposobów rozwiązania problemu z orientacją jest wykonanie kopii oznaczonych segmentów. Dodaj 180 stopni do orientacji pierwszej kopii, jeśli jest mniejsza niż 90, i w przeciwnym razie odejmij 180 stopni od orientacji. To powiększa twój zestaw danych (oczywiście), ale poza tym w żaden sposób nie zmienia algorytmu.

Potrzebne są ciężary, ponieważ różnice we współrzędnych, długościach i orientacjach mogą oznaczać całkiem różne rzeczy dotyczące podobieństwa ich odpowiednich segmentów. W wielu aplikacjach różnice między segmentami wynikają z różnic w lokalizacjach ich punktów końcowych. Jako przybliżone przybliżenie możemy spodziewać się, że typowa zmiana długości segmentów będzie mniej więcej taka sama jak typowa różnica między ich punktami końcowymi. Dlatego wagi powiązane z x, y i długością powinny być mniej więcej takie same. Trudną częścią jest orientacja ważenia, ponieważ orientacji nie można zrównać z odległością, a co gorsza, krótkie segmenty byłyby bardziej źle ustawione niż długie segmenty. Rozważ metodę prób i błędów, która równoważy kilka stopni błędnej orientacji do wielkości typowej przerwy między segmentami, a następnie dostosowuje ją, aż procedura wydaje się działać dobrze. Aby uzyskać wskazówki, pozwólL będzie typową długością segmentu. Zmiana orientacji o niewielki kąt t stopni zmieści odległość w przybliżeniu L / 2 * t / 60 (60 oznacza przybliżoną liczbę stopni na jednym radianie), czyli L / 120 razy t . Sugeruje to rozpoczęcie od ciężarów jednostkowych dla x, y i długości oraz masy L / 120 dla orientacji.

Podsumowując , ta sugestia to:

1. Wykonaj kopie oznaczonych segmentów (zgodnie z opisem w akapicie dotyczącym zmiany orientacji).

2. Przelicz każdy segment na poczwórny (x, y, długość, orientacja L / 120 *), gdzie L jest typową długością segmentu.

3. Wykonaj analizę skupień czwórek. Użyj dobrego pakietu statystycznego ( R jest bezpłatny).

4. Użyj wyników analizy skupień jako tabeli przeglądowej do powiązania oznaczonych segmentów z pobliskimi segmentami nieznakowanymi.

Pracowałem nad projektem o podobnych wymaganiach około 5 lat temu. Polegało to na połączeniu współrzędnych z linii środkowych ulic (ze stosunkowo wysoką precyzją współrzędnych) z łączami sieci ruchu w systemie monitorowania autostrady (HPMS).

W tym czasie FHWA nie zapewniało żadnych narzędzi do tego typu rzeczy. To mogło się zmienić, możesz to sprawdzić. Nawet jeśli nie pracujesz z danymi o autostradzie, narzędzia mogą być nadal odpowiednie.

Napisałem go w ArcGIS, ale algorytm powinien działać w open source, o ile zapewnia możliwości śledzenia podobne do 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

Oto pomysł

Jeśli oderwiesz jeden z linii w celu porównania i przetestujesz, czy punkty wierzchołkowe znajdują się w pewnej odległości od drugiego linii w celu porównania, możesz kontrolować test na wiele sposobów.

te przykłady działają w PostGIS (kto może zgadywać :-))

Po pierwsze, jeśli powiemy, że istnieje dopasowanie, jeśli wszystkie punkty wierzchołków w linii w tabeli_1 mają 0,5 metra (jednostki mapy) lub są bliżej linii w tabeli_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;

Następnie możemy powiedzieć, że istnieje dopasowanie, jeśli więcej niż 60% punktów wierzchołków w linii w tabeli_1 znajduje się w odległości od linii w tabeli_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

Lub możemy zaakceptować, że jeden punkt nie jest w zasięgu:

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;

Będziesz także musiał uruchomić zapytanie z table_1 i table_2 w odwróconych rolach.

Nie wiem jak szybko to będzie. ST_Dumppoints jest obecnie funkcją SQL w PostGIS, a nie funkcją C, która sprawia, że ​​jest wolniejsza niż powinna. Ale myślę, że i tak będzie dość szybko.

Indeksy przestrzenne bardzo pomogą ST_Dwithin w skuteczności.

HTH Nicklas

Napisałem kod do obsługi niedopasowanego dopasowywania segmentów linii (i nakładania się na nie) w Boundary Generator. Zapisałem (dość elementarną) matematykę tutaj: http://blog.shoutis.org/2008/10/inside-boundary-generator-computational.html . Kod jest open source i powiązany z tym postem na blogu.

Kod stosuje bardzo proste podejście:

• Test segmentu segmentu, który pokaże, czy dwa segmenty linii zachodzą na siebie w ramach tolerancji kąta i odległości, a także stopień nakładania się.
• Szybki indeks przestrzenny, który eliminuje potrzebę testowania każdego segmentu linii w zbiorze danych względem wszystkich innych segmentów linii w zbiorze danych.

Główną zaletą tego podejścia jest to, że otrzymujesz całkiem precyzyjne pokrętła dla prawidłowego kąta, odległości i długości zakładki; z drugiej strony, nie jest to sposób ogólnego pomiaru podobieństwa dwóch segmentów linii, więc znacznie trudniej jest np. przeprowadzić grupowanie statystyczne w celu ustalenia prawdopodobnych dopasowań - utkniesz z precyzyjnymi pokrętłami.

Uwaga: Zgaduję, że przy wystarczającej liczbie kotletów SQL można wcisnąć test segmentu segmentu w klauzulę WHERE ... :)

Twoje zdrowie!

I zostały wdrożone szorstką prototyp mapy dopasowywania tutaj , co jest względne łatwy w użyciu. Jest oparty na silniku routingu typu open source i napisany w Javie. Zastosowany algorytm opisano tutaj .