Przygody w programowaniu i rozwoju GPS: samouczek geoprzestrzenny

Wszystko zaczęło się od wycieczki do Zbevnicy ponad 10 lat temu. Miałem ze sobą nowy GPS, a mój znajomy miał GPS podłączony do telefonu z systemem Windows ME. Trasa była świetna, ale kiedy wróciliśmy do naszych samochodów, byliśmy zaskoczeni, widząc, że jeden GPS twierdził, że przeszliśmy 6,2 km, a drugi 6,7 km. Jeden twierdził, że nasz wzrost wysokości (tj. suma wszystkich podjazdów pod górę) wyniósł 300m, podczas gdy drugi podał, że to 500m.

Będąc programistą (a w końcu programistą GIS), problem od razu mnie zaintrygował. Powiedziałem sobie: „ nie powinno to być trudne do naprawienia prostym skryptem”. W końcu ślady GPS to tylko lista krotek w formie (szerokość, długość geograficzna, wysokość) , prawda?

No nie bardzo.

I tak zaczęła się moja wyprawa w fascynujący świat śladów GPS, błędów śledzenia i ogólniej programowania GIS.

Systemy Informacji Geoprzestrzennej (GIS) to ogromna i złożona dziedzina, obejmująca odwzorowanie map i dane geodezyjne)), przetwarzanie danych rastra i vecto oraz teledetekcję. Kompleksowe wprowadzenie do tej dziedziny wykraczałoby daleko poza zakres tego artykułu. A ponieważ skupienie się na konkretnym problemie i tak może być użytecznym sposobem na przedstawienie się w nowej domenie, przedstawię kilka konkretnych wyzwań GIS, z którymi się spotkałem, i kilka możliwych rozwiązań; mianowicie:

• Jak rozpoznawać, rozumieć i programowo poprawiać błędy śledzenia GPS
• Jak obliczyć i uzyskać dodatkowe przydatne informacje ze śladów GPS

Na początek, ślady GPS to nie tylko seria krotek (szerokość, długość geograficzna, wysokość) . Wiele urządzeń obsługujących GPS zapewnia również metadane, takie jak czas, tętno i tak dalej. Niektóre urządzenia GPS dostarczają nawet informacji o dokładności danych; aka, „rozcieńczenie precyzji”. Niestety, większość urządzeń GPS – zwłaszcza tych z niższej półki, które dominują na rynku – nie dostarcza tych informacji i pozostajemy z wyzwaniem samodzielnego wywnioskowania dokładności urządzenia (i najlepiej, jeśli to możliwe, odpowiedniej korekty). ).

Zacznijmy od jednego możliwego algorytmu do wykrywania słabszych urządzeń GPS (jak większość smartfonów), które zazwyczaj mają dane GPS niskiej jakości.

Błędy w elewacji i dziwactwa

Jeśli mieszkasz w niektórych częściach świata, być może zauważyłeś coś dziwnego w dokładności wysokości GPS podczas rejestrowania śladów za pomocą smartfona. Podczas sprawdzania rzędnych są one konsekwentnie rejestrowane jako wyższe lub niższe (o stałą wartość) niż prawa rzędna. Na przykład mieszkam w Višnjan (Chorwacja), a mój Android ciągle mi mówi, że jestem około 35-40 metrów nad rzeczywistą wysokością.

Na przykład, oto wykres wysokości GPS z krótkiej wędrówki, którą odbyłem kilka miesięcy temu:

Warto zwrócić uwagę na dwie rzeczy.

Po pierwsze, „wzgórze” w pierwszej części zarejestrowanych danych GPS zostało całkowicie sfabrykowane przez urządzenie . O ile wykres wydaje się wskazywać, że najwyższy punkt naszej wędrówki znajdował się zaledwie kilkaset metrów od startu, w rzeczywistości było to około 4 km później.

Po drugie, być może ważniejsze (i niewidoczne na wykresie) jest to, że cały wykres jest niedokładny . Wartości wysokości były konsekwentnie zgłaszane jako o około 30-40 metrów wyższe niż w rzeczywistości, co omówimy bardziej szczegółowo w dalszej części tego artykułu.

To są rzeczy, które mogą się zdarzyć z tanimi urządzeniami GPS. A kiedy wykryjemy, że ślad zawiera te błędy, możemy wywnioskować, że urządzenie jest prawdopodobnie niskiej jakości GPS, w związku z czym można spodziewać się również innych błędów – nie tylko błędów wysokości – które są wspólne dla takich urządzeń.

Błędy podniesienia startu

Zasadniczo urządzenia GPS wykorzystują dwie techniki do określania wysokości: „wysokość GPS” (zgłaszana do urządzenia przez system satelitarny GPS) i „wysokość barometryczna” (obliczana przez urządzenie na podstawie odczytów ciśnienia barometrycznego). Żaden nie jest doskonały.

Wartości wysokości GPS mogą mieć wiele drobnych błędów (zwykle w zakresie +/- 10m), co może być szczególnie problematyczne, jeśli później zdecydujemy się na obliczenie skumulowanego przyrostu wysokości. Z drugiej strony wysokość barometryczna jest wrażliwa nie tylko na wysokość, ale także na warunki pogodowe, które mogą wprowadzić własny zestaw niedokładności.

Niektóre urządzenia stosują zatem podejście hybrydowe, wykorzystując odczyty barometryczne do rejestrowania wysokości, ale wykorzystując odczyty GPS, aby pomóc (ponownej) skalibrować te wartości, pomóc w uwzględnieniu zmian pogody (ciśnienia) i tak dalej. Dzięki takim urządzeniom, podczas uruchamiania śladu, wysokość barometryczna może być całkowicie błędna, ale później poprzez rekalibrację z coraz większą ilością danych satelitarnych GPS, dane o wysokości stają się bardziej wiarygodne. Dlatego często zdarza się, że takie urządzenia napotykają błąd uruchamiania „fałszywego wzgórza”, który zaobserwowaliśmy wcześniej na naszym wykresie wysokości.

Bieżące niedokładności wysokości GPS

Aby wyjaśnić stały błąd w raportowaniu wysokości, musimy wrócić do geografii naszej szkoły podstawowej. Nauczyciele geografii zwykle wyjaśniają, że Ziemia nie jest kulą, ale elipsoidą. Gdyby to rzeczywiście było prawdą, wysokość byłaby łatwa do obliczenia matematycznego. Ale nie jest. Ziemia jest nieregularna; w rzeczywistości jest bardziej jak ziemniak przypominający elipsoidę niż idealną elipsoidę, co oznacza, że ​​do rozwoju GIS potrzebujesz szczegółowego zestawu danych wysokości dla prawie każdego punktu na Ziemi. W geodezji ta elipsoida odniesienia (znana również jako odniesienie) jest matematycznie zdefiniowaną powierzchnią, która przybliża geoidę, „prawdziwszą” figurę Ziemi.

Co więcej, ważne jest, aby zdać sobie sprawę, że nawet te dane są jedynie przybliżeniami rzeczywistego kształtu powierzchni Ziemi. Niektóre działają lepiej w niektórych częściach świata, a inne działają lepiej w innych. Jako przykład, poniższy obraz (wygenerowany przy użyciu mojej biblioteki Ruby) pokazuje, jak Ziemia różni się od jednego z najczęściej używanych modeli elipsoidalnych (odniesienie WGS84). Czarne części reprezentują części Ziemi powyżej, a białe części Ziemi poniżej, idealną elipsoidę (kontury kontynentu i wyspy pokazane na czerwono).

Widać, że Indie znajdują się poniżej elipsoidy WGS84, a południowa część to absolutne minimum (prawie -100 metrów!), a Europa jest nad nią.

Ponieważ urządzenia GPS niskiej jakości nie wykorzystują żadnych takich danych, tak naprawdę obliczają wysokość, zakładając idealną elipsoidę. Stąd ich konsekwentna nieścisłość.

Wykrywanie i korygowanie błędów wysokości GPS

W tworzeniu aplikacji GPS wykrycie, że urządzenie, które zarejestrowało nasz ślad, zawiera tego typu błędy, można przeprowadzić przy użyciu zestawu danych Earth Gravitational Model EGM2008, czasami nazywanego również zestawem danych „geoid undulacje”. Dzięki EGM2008 możemy przybliżyć różnicę między rzeczywistą powierzchnią ziemi a idealną elipsoidą.

Ale żeby wiedzieć, czy nasz ślad GPS ma ten błąd, potrzebujemy jeszcze jednej rzeczy – rzeczywistej wysokości. Publiczną bazą danych, która może być pomocna w tym celu, jest Shuttle Radar Topography Mission (SRTM). SRTM to baza danych oparta na rastrze, która dostarcza wartości wysokości w rozdzielczości mniej więcej co 30 m (na równiku) dla USA i co 90 m dla reszty świata. Na przykład podczas obliczania wartości SRTM dla punktów na powyższej ścieżce pojawia się inny wykres (niebieska linia):

Niewielką irytacją są tutaj szorstkie krawędzie wykresu, ale można to łatwo wygładzić. Zwróć uwagę, że wygładzając tracimy niewielką (jeśli w ogóle) precyzję, ponieważ sam SRTM zapewnia tylko dyskretne punkty w równoodległych pozycjach, między którymi musimy interpolować w każdym przypadku. Oto wersja poprzedniego wykresu z nałożoną czerwoną linią przedstawiającą wygładzone dane SRTM:

Wszystko to można łatwo zrobić, nawiasem mówiąc, za pomocą moich bibliotek GPS Python:

• srtm.py: parser Pythona dla danych wysokościowych misji radarowej wahadłowej (SRTM)
• gpxpy: prosta biblioteka Pythona do parsowania i manipulowania plikami GPX (GPX, GPS Exchange Format, to lekki format danych XML dla danych GPS)

Dla użytkowników Rubiego dostępna jest również moja biblioteka parsera Geoelevations.rb dla fal SRTM i EGM2008.

Po wykryciu tych anomalii, w zależności od rodzaju oprogramowania, z którym pracujemy, możemy albo (a) samodzielnie poprawić błędy, albo (b) po prostu poinformować użytkownika, że ​​wykryto nieścisłości w danych wysokości.

Ponadto, ponieważ istnieją różne algorytmy, których można użyć do programowego korygowania tych błędów wysokości GPS, możemy dać użytkownikowi możliwość wyboru algorytmu do zastosowania (np. czy użytkownik chce, abyśmy po prostu używali wygładzonych danych SRTM „tak jak jest” lub czy użytkownik chce, abyśmy korzystali z danych SRTM, aby pomóc skorygować wzniesienia zgłaszane przez urządzenie).

Wygładzanie toru i usuwanie wartości odstających

Gdyby piłkarz nosił urządzenie GPS i nagrywał mecz, wynikowy tor byłby bałaganem. Boisko byłoby gęsto wypełnione torem składającym się z wielu ostrych zakrętów, przyspieszeń i spowolnień.

Na szczęście większość przypadków, w których ludzie używają GPS, nie będzie przebiegać tak samo – linie GPS (i przyspieszenia) będą stosunkowo gładkie. W takich przypadkach można założyć, że błędne punkty na naszej ścieżce są spowodowane błędami, a takie wartości odstające można rozsądnie usunąć za pomocą funkcji wygładzania.

Jako programista GIS, wygładzanie jest najczęściej osiągane przez iterację punktów i zmianę współrzędnych na podstawie wartości sąsiednich współrzędnych. Na przykład możemy zmienić każdą szerokość i długość geograficzną za pomocą algorytmu takiego jak:

 points[n].latitude = points[n-1].latitude * 0.3 + points[n].latitude * .4 + points[n+1].latitude * .3 points[n].longitude = points[n-1].longitude * 0.3 + points[n].longitude * .4 + points[n+1].longitude * .3

Im większy współczynnik, tym większy wpływ odpowiedniego sąsiedniego punktu na zmodyfikowane położenie bieżącego punktu. Współczynniki, których używam w tym przykładzie (0,3, 0,4, 0,3) są nieco arbitralne, ale w większości przypadków chcesz, aby ich suma była równa 1,0. (Bardziej wyrafinowanym podejściem byłoby na przykład użycie odległości między punktami, a następnie im bliżej punktu, tym większy odpowiadający mu współczynnik.)

Oto przykład toru z wieloma przypadkowymi błędami:

Zwróć uwagę, że trasa nie podąża dobrze ścieżką, ma wiele ostrych i poszarpanych zakrętów, a czasami całkowicie zbacza z oczekiwanej ścieżki.

Po kilku „wygładzających” iteracjach ten sam utwór jest przekształcany w:

Chociaż jest to o wiele lepsze, nadal jest wprawdzie niedoskonałe. Zwróć uwagę, że nadal są miejsca (szczególnie w pobliżu środka ścieżki), w których trasa nadal zbacza z drogi.

Są inne rzeczy, których możesz spróbować. W niektórych regionach i dla niektórych aplikacji GPS można również użyć danych OpenStreetMap (OSM), aby spróbować odgadnąć właściwą ścieżkę, a następnie „przyciągnąć” punkty do nowej linii. Chociaż często może to być pomocne, może być również niedoskonałe, na przykład w przypadkach, gdy dane OSM zawierają dwie równoległe linie (na przykład autostradę i pobliską drogę) lub wiele bliskich ścieżek.

W takich przypadkach możliwym rozwiązaniem byłaby próba wykrycia rodzaju aktywności za pomocą niektórych technik omówionych w dalszej części tego artykułu. Jeśli na przykład wywnioskujemy, że trasa była szlakiem turystycznym i mamy możliwość zatrzaśnięcia się na autostradzie lub pobliskiej ścieżce, możemy śmiało założyć, że wędrówka przebiegała wzdłuż ścieżki, a nie autostrady.

Należy również zauważyć, że chociaż ten przykład demonstruje wygładzanie współrzędnych powierzchni (tj. długości/szerokości geograficznej), wygładzanie może być równie ważną techniką eliminowania aberracji w danych wysokościowych lub danych czasowych, a nawet w danych dotyczących tętna i rytmu rowerowego.

Przykłady dodatkowych korzyści i zastosowań wygładzania mogą obejmować:

• Obliczanie całkowitego przyrostu wysokości. Aby obliczyć całkowity przyrost wysokości na torze, nie wystarczy po prostu zsumować wszystkie małe „skoki” pod górę, ponieważ często zawierają one małe błędy. Wygładzanie wysokości przed wykonaniem sumy może często pomóc złagodzić ten problem.
• Usuwanie wartości odstających. Po „wygładzeniu” punkty, które są zbyt daleko od toru, można łatwiej wykryć. Często można wówczas założyć, że są to wartości odstające, a użytkownik może zostać poproszony o pytanie, czy należy je usunąć.

Istnieje jeden rodzaj problemu, w którym ten algorytm nie działa: w niektórych przypadkach GPS zarejestruje gładką ścieżkę, ale ścieżka zostanie „przesunięta” o stałą różnicę w pewnym kierunku. W takich przypadkach wygładzanie może dodatkowo wygładzić linię, ale nie naprawi tego błędu przesunięcia.

Dodatkowym, mniej oczywistym, ale znaczącym problemem związanym z uproszczoną techniką wygładzania, którą opisaliśmy, jest to, że transformacja modyfikuje wszystkie (lub prawie wszystkie) punkty na ścieżce, nawet te, które mogą nie być błędne. Chociaż to prostsze podejście wydaje się być rozsądnym rozwiązaniem dla przeciętnego użytkownika GPS, bardziej wyrafinowane algorytmy wygładzania są z pewnością możliwe do zastosowania w programowaniu GIS. W niektórych przypadkach może być nawet lepiej po prostu usunąć wartości odstające bez wykonywania żadnego wygładzania, w zależności od użytkownika, urządzenia i aplikacji.

Wykrywanie maksymalnej prędkości

Wykrycie maksymalnej prędkości toru jest dość proste, jeśli mamy współrzędne i znaczniki czasu wszystkich punktów na trasie. Wystarczy obliczyć prędkości między punktami i znaleźć najwyższą wartość. Wydaje się proste.

Pamiętaj jednak, że mamy do czynienia z tanimi urządzeniami GPS i nie w pełni ufamy danym, co może mieć istotne konsekwencje dla naszych obliczeń. Jeśli urządzenie rejestruje lokalizację co 5 metrów i w pewnym momencie popełni błąd, przesuwając punkt o 10 metrów, to ta część toru może wydawać się 3x szybsza niż była!

Jednym z powszechnych podejść w świecie programistów GIS jest wyodrębnienie wszystkich prędkości między punktami, a następnie usunięcie górnych 5% (tj. użycie 95. percentyla) w nadziei, że wyeliminowane 5% stanowi większość błędów. Ale jest to wprawdzie nienaukowe i nie zapewnia prawidłowych wyników. Eksperymentując z tą techniką, wypróbowałem różne wartości dla percentyli i stwierdziłem, że niektóre działały dobrze dla jednego urządzenia GPS, inne działały dobrze dla innych. Niektóre sprawdzają się podczas wędrówek, a inne do jazdy na rowerze. Ale w większości przypadków wyniki po prostu nie wydawały mi się odpowiednie.

Po wypróbowaniu wielu algorytmów, to, co zadziałało, było dla mnie proste: dodać kolejny filtr, aby usunąć ekstrema, nie tylko według prędkości, ale także odległości, w następujący sposób:

1. Sortuj punkty według odległości między sąsiadami i usuń górne 5%.
2. (Opcjonalnie:) Wygładź ścieżkę (w poziomie i/lub w pionie).
3. Sortuj punkty według prędkości między sąsiadami i usuń górne 5%.

Z mojego doświadczenia ten algorytm daje dość wiarygodne wyniki, nawet dla śladów z tanich urządzeń GPS z przypadkowymi błędami.

Wydedukowanie rodzaju działalności

W wielu przypadkach do określenia rodzaju aktywności wystarcza średnia prędkość. Jeśli średnia prędkość wynosi na przykład 5 km/h, prawdopodobnie jest to trasa piesza/piesza, natomiast jeśli średnia prędkość wynosi 30 km/h, prawdopodobnie jest to trasa rowerowa i tak dalej.

Ale jeśli średnia prędkość wynosi 12 km/h, nie możesz być pewien, czy użytkownik jeździł na rowerze górskim, czy biegał. W takich przypadkach maksymalna prędkość może czasami pomóc w rozróżnieniu tych dwóch rodzajów aktywności. W szczególności możemy wykorzystać fakt, że biegacze rzadko osiągają prędkość ponad dwukrotnie wyższą niż średnia, podczas gdy rowerzyści robią to regularnie (np. podczas zjazdów niezbyt wymagającą ścieżką).

W związku z tym tor o średniej prędkości 12 km/h i maksymalnej 18 km/h został prawdopodobnie zarejestrowany podczas biegu, podczas gdy tor ze średnią prędkością 12 km/h i maksymalną prędkością 30 km/h został prawdopodobnie zarejestrowany podczas jazdy na rowerze górskim. (Oczywiście musimy być pewni, że nasza obliczona prędkość maksymalna jest prawidłowa, aby to działało niezawodnie.)

Procent widocznego nieba: sprytny serwer proxy do wykrywania błędów GPS

Dokładność każdego pomiaru GPS (tj. szerokość, długość i wysokość) w dużej mierze zależy od liczby satelitów, które były widoczne w momencie rejestracji. Jeśli więc moglibyśmy w jakiś sposób określić, ile satelitów było „widocznych” w czasie każdego nagrania, moglibyśmy użyć tego jako sposobu na przybliżenie dokładności tego nagrania. Gdybyśmy w jakiś sposób wiedzieli, na przykład, że wszystkie potrzebne satelity GPS są widoczne, moglibyśmy założyć wysoki stopień dokładności odpowiednich danych GPS. I odwrotnie, gdybyśmy w jakiś sposób wiedzieli, że nie widać satelitów GPS, moglibyśmy założyć, że dane są podatne na błędy.

Ale zanim będziesz zbyt podekscytowany, rozważ złożoność próby rozwiązania takiego problemu GIS. Przede wszystkim musisz wiedzieć, z jakimi systemami satelitarnymi GPS Twoje urządzenie może się komunikować. Jest oryginalny globalny system pozycjonowania z siedzibą w USA, europejski Gallileo i rosyjski system GLONASS. Niektóre urządzenia współpracują ze wszystkimi tymi typami satelitów, ale wiele nie. Wiele urządzeń nie zgłasza nawet używanych systemów.

Istnieje jednak sprytny sposób na obejście tej złożoności i uzyskanie zgrubnego przybliżenia liczby widocznych satelitów: użyj procentu widocznego nieba jako przybliżenia liczby widocznych satelitów . Mniej widoczne niebo oznacza, że ​​nasz GPS może „widzieć” (lub być widzianym) przez mniejszą liczbę satelitów. Ale jak możemy obliczyć procent widocznego nieba w dowolnym punkcie na Ziemi? Rozwiązanie jest w rzeczywistości dość proste: możemy obliczyć linię horyzontu wokół nas, korzystając z danych SRTM omówionych wcześniej.

Na przykład, to jest horyzont, jeśli jesteś w dolinie poniżej Triglav (najwyższy szczyt Słowenii), jak obliczono za pomocą SRTM:

(Dla zainteresowanych, mój kod do stworzenia tego obrazu można znaleźć tutaj.)

Ten obraz składa się w zasadzie z warstw równoodległych wykresów wysokości, widzianych z centralnego punktu. Im ciemniejszy obszar niebieski, tym bardziej odległa warstwa elewacji; im jaśniejszy obszar niebieski, tym bliżej warstwy elewacji. Najwyższe narysowane punkty reprezentują linię horyzontu. Jeśli satelita GPS znajduje się poniżej tej linii na niebie, nasze urządzenie prawdopodobnie go nie widzi (lub nie może być widziane). (Pamiętaj jednak, że chociaż obraz jest rysowany jako spłaszczony prostokąt, w rzeczywistości do prawidłowego obliczenia obszaru poniżej horyzontu potrzebna jest podstawowa znajomość geometrii sferycznej).

Inną rzeczą, o której należy pamiętać, jest to, że nie jest to srebrna kula do wykrywania błędów elewacji GPS. Po pierwsze, większość części Ziemi nie jest górzysta, a nawet jeśli tak jest, w naszej psychologii przecenianie wysokości; rzeczywisty procent widocznego nieba przekracza 75% w zdecydowanej większości zamieszkałych regionów . Niemniej jednak ta metoda może być pomocna w niektórych sytuacjach, takich jak wędrówki górskie, gdzie możesz przejść od głębokiego kanionu (ze słabym odbiorem GPS) do przebywania na grzbiecie górskim (gdzie odbiór satelitarny jest prawdopodobnie znacznie lepszy). Chociaż ta metoda nie jest bezwzględną miarą liczby błędów na ścieżce, może być przydatnym wskaźnikiem tego, które części ścieżki mogą być bardziej podatne na błędy niż inne.

Zakończyć

Omówiliśmy niektóre z najczęstszych rodzajów błędów śledzenia GPS, których można się spodziewać w przypadku słabszych urządzeń GPS. Zapewniliśmy zrozumienie, co je powoduje, a także niektóre techniki programowania GIS, aby je poprawić.

W niektórych przypadkach możemy z dużym prawdopodobieństwem poprawić tor. W innych przypadkach możemy przynajmniej ostrzec użytkownika o fragmentach ścieżki, które wydają się wątpliwe. W przypadkach, w których nie mamy pewności, zawsze istnieje możliwość umożliwienia użytkownikowi samodzielnego naprawienia śladu za pomocą zdjęć lotniczych i map. Nasze probabilistyczne domysły mogą pomóc wyróżnić te fragmenty toru, w których wykryliśmy większe prawdopodobieństwo błędów.

W wielu przypadkach opisane przez nas techniki mogą być zadowalającym „rozwiązaniem 80%”, zapewniając użytkownikom słabszych urządzeń GPS rozsądny poziom automatycznej poprawy dokładności ich śladów GPS.