Mapować pasujące linki i pomysły? [Zamknięte]

Korzystam z OpenStreetMap i jego wektorowej sieci dróg i chciałbym zaimplementować algorytm dopasowywania map.

Obecnie jestem w stanie, dla każdej pozycji GPS, pobrać najbliższy odcinek drogi i obliczyć rzut tej pozycji na ten odcinek, jak na tym zdjęciu (czerwona pinezka to czysta pozycja GPS, na niebiesko segment mapowany, a na zielono zmapowana pozycja):

Jednak z powodu braku dokładności GPS czasami odwzorowana pozycja przeskakuje z segmentu na inny i może od czasu do czasu zapewniać niespójną pozycję mapowaną.

Mój obecny algorytm jest bardzo prosty: z czystej pozycji GPS uzyskuję najbliższy segment i decyduję, że mapowana dopasowana pozycja znajduje się na tym. Wiem, że można to naprawdę poprawić.

Mogę sobie wyobrazić, że wzięcie pod uwagę kierunku pojazdu poprawi dopasowanie mapy, ale czy znasz jakieś inne podejście, które pozwoliłoby mi ulepszyć dopasowywanie map?

Poszukuję linku i / lub oprogramowania typu open source?

Rzutowanie punktów na linię, jak już robisz, jest możliwe bezpośrednio w PostGIS. O czym pisałem jakiś czas temu, tutaj

Ale aby rozwiązać problem, gdy punkty znajdują się bliżej niewłaściwego segmentu niż prawego segmentu, może to być możliwe podejście.

1. Zbuduj linię punktów
2. Wypróbuj sugerowane rozwiązania w Algorytmach dotyczące dopasowywania segmentów w celu dopasowania całej linii zamiast tylko punkt po punkcie

Po przeczytaniu twojego pytania i różnych odpowiedzi zainteresowałem się tym problemem. Po przeczytaniu algorytmów dopasowywania mapy zrozumiałem, co następuje:

• Aby dopasować lokalizację GPS do drogi, potrzebujesz rzeczywistych danych o drodze w formacie wektorowym
• Pomoże to, jeśli masz różne ciężary dla różnych dróg. Zatem szanse na dopasowanie punktu do autostrady będą wyższe, niż przy dopasowaniu linii bocznej.
• Musisz wziąć historię i szybkość odczytu GPS. Na przykład, jeśli punkt GPS od dłuższego czasu dopasowuje się do bocznego pasa, należy wziąć to pod uwagę i nie dopasowywać go bezpośrednio do autostrady. - Rzeczywiste dopasowanie odbywa się przy użyciu różnych technik statystycznych.

Do dalszej lektury proponuję:

• Dopasowywanie map dla trajektorii GPS o niskiej częstotliwości próbkowania
• Niektóre algorytmy dopasowywania map dla osobistych asystentów nawigacji
• Trzyetapowa metoda dopasowania mapy ogólnej w środowisku GIS: perspektywa badania podróży / transportu

Odpowiadając na moje własne pytanie!

1- Miły .pdf Właśnie znalazłem na ten temat:

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

który również prowadzi do implementacji mechanizmu dopasowywania map C ++ w otwartym kodzie źródłowym opisanego w dokumencie: http://eden.dei.uc.pt/~camara/files/mgemma.zip
(ten jest trybem dopasowywania map offline, rozumiem że oblicza dopasowane pozycje mapy ze ścieżką CAŁĄ jako dane wejściowe i nie może tego robić w locie dla każdej pozycji).

2 - Właśnie przeczytałem ten dogłębnie i moim zdaniem jest naprawdę dobry: https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/4860/1/velaga.pdf „Rozwijanie ulepszony algorytm mapowania topologicznego opartego na wadze dla inteligentnych systemów transportowych ”
Algorytm jest jasno objaśniony, a wartości dostosowania ciężaru podano również w dokumencie.

Dużo pracy nad dopasowywaniem map znajduje się w tym dokumencie, aby uzyskać krótką ankietę na temat dość niedawnych prac (sprzed 2007 r.). Niedawno podejścia oparte na ukrytych modelach Markowa wydają się działać całkiem dobrze w normalnych okolicznościach. Na przykład sprawdź ten artykuł z 2009 roku. Pomysł i model są dość proste i nie powinny sprawiać zbyt dużych problemów we wdrażaniu, nawet jeśli nie znasz HMM (w takim przypadku nie panikuj, jest ich mnóstwo z tutoriali i wprowadzeń online)

Metoda ta nazywana jest także „konflacją wektorów”. Istnieje dedykowana strona Wiki ( http://wiki.openstreetmap.org/wiki/Conflation ), która daje ogólny przegląd i zawiera listę pakietów oprogramowania (Open Source) do przeprowadzania łączenia wektorów dróg, takich jak „wtyczka JOSM”, łączenie „Potlatch 2” tool ”,„ RoadMatcher ”(dla OpenJUMP) i inne.

W przypadku algorytmów dopasowania mapy zależy, czy potrzebujesz przetwarzania w czasie rzeczywistym, czy offline. W drugim przypadku najnowocześniejsze algorytmy mogą przetwarzać ~ 1000 punktów na sekundę. Wymagania dotyczące pamięci zależą od zasięgu kursu. W tym celu udało nam się wycisnąć sieć drogową OSM planety na około 16 Gb.

Ponadto należy odróżnić dopasowanie mapy od wnioskowania o ścieżce : są to dwa osobne procesy, w zależności od tego, czy masz dane o wysokiej, czy niskiej częstotliwości. Gdy masz względnie niewiele punktów (np. 1 dane na kilometr w kontekście miejskim), następuje wnioskowanie o ścieżce, ponieważ zwykle można zgadywać, gdzie podróżuje urządzenie. Wnioskowanie ścieżki jest zwykle trudniejsze, ale staje się mniejszym problemem w przypadku nowoczesnych urządzeń / ceny akwizycji danych.

Możesz sprawdzić mój profil pod kątem interfejsu API, który wykonuje dopasowanie map bezpośrednio w OSM: używa dopasowania topologicznego i działa dobrze na przykład z pływającymi danymi samochodu.

Slajd Strava opisuje, w jaki sposób skumulowane dane śladu w sieci drogowej mogą zachowywać się jak „doliny” i jak proponowana trasa „wpasuje się”, jakby to był ciąg paciorków.

Po przetestowaniu większości wyżej wymienionych frameworków znalazłem Barefoota i naprawdę mogę go polecić. Wykorzystuje ukryte modele markowa jako probabilistyczne podejście do mapowania (szczegóły w artykule „Umieszczenie samochodu na mapie” ) i jest zaimplementowany w Javie. Jest to oprogramowanie typu open source i aktywnie rozwijane przez dział CarIT BMW.

Temat nazywa się dopasowywaniem map. Ale jako pierwsze bardzo dobre przybliżenie, prawdopodobnie wystarczy po prostu wyszukać najbliższe punkty dla każdego punktu GPS (bez żadnych poprawnych poprawnych trafień).

Mój projekt Open Source o nazwie graphhopper nie jest czymś, co działa na iOS ( aktualizacja : teraz działa również na iOS), ani nie ma w pełni funkcjonalnej aplikacji na Androida do tego, czego chcesz. Ale możesz użyć wersji serwerowej, aby zbudować aplikację na iOS lub użyć demonstracji offline Androida na początek. Udostępniłem tutaj algorytm dopasowywania map , tylko szorstki prototyp, ale działa zaskakująco dobrze.

Spróbuj zdobyć dobre dane testowe. Użyj dodatkowego GPS śledzenia o wyższej dokładności, oprócz rejestrowania punktów na urządzeniu docelowym. Pozwoli to zidentyfikować błędy w GPS i danych OSM. Znajomość rozsądnych progów znacznie ułatwi zaprojektowanie algorytmu.

Jeśli możesz uzyskać dane o drogach dla swojego regionu, być może zainteresuje Cię automatyczne przyciąganie zbiorcze za pomocą FOSS

W zależności od tego, czy chcesz drukować dane w czasie rzeczywistym, czy planujesz później wykonać przetwarzanie końcowe na komputerze, GRASS może ci pomóc.

Znalazłem interfejs API, który może po prostu wykonać zadanie bez konieczności natychmiastowego opracowania własnego rozwiązania.

Używają danych OSM do dopasowywania map. Mają także stronę demonstracyjną, która pozwala przesłać pliki GPX, aby zobaczyć, jak dobrze może to dla Ciebie działać.

Nie musisz koniecznie poprawiać jakości swoich danych. Zastosowanie algorytmu topologicznego z siecią dróg w pamięci znacznie poprawi dopasowanie. Sprawdź odniesienia: http://trb.metapress.com/content/p31485vw72645686