Przetwarzanie OpenStreetMap na systemie wbudowanym #2 - Parsowanie formatu .osm

[kronikary]

Zapraszam Was na kolejną część artykułu w której opiszę co zrobić oraz jak przygotować plik .osm, aby dało się go w łatwy sposób przetworzyć na mikroprocesorze. Wyjaśnię, czym są „map tiles” i jak możemy wykorzystać tą idee na naszym przykładzie. Życzę miłej lektury!

Rozważania

Aby móc wyświetlać mapy na systemie wbudowanym, wpierw postanowiłem to zrobić na komputerze stacjonarnym w języku Python w środowisku PyCharm. W tym celu wyeksportowałem wycinek mapy w formacie .osm oraz napisałem kod, który odczytywał wszystkie koordynaty i informacje na temat dróg i budynków. Następnie na podstawie zdekodowanych danych wyświetlałem w oknie graficznym programu wielolinie lub poligon – zależnie czy była to droga czy budynek. Rezultat nie był zbyt optymistyczny, ponieważ wyświetlenie mapy o rozmiarze 6MB trwało około 7 sekund. 

Renderowanie mapy bezpośrednio z pliku .osm. Objętość pliku .osm około 6MB, objętość renderowanego obszaru około 0,5MB

Dodatkowo ze względu na to, że wykorzystuję The ElementTree XML API, które wpierw samo parsuje interesujący nas plik, a następnie wszystkie potrzebne informacje przechowuje w pamięci RAM, pojawiły się problemy z plikami o większych rozmiarach. W komputerze posiadam 16GB pamięci RAM i odtworzenie pliku .osm o rozmiarze np. 2GB kończyło się zakończeniem procesu działania programu. Nie wspominając o czasie, jaki jest potrzebny na przeskanowanie całego pliku. Dodam że skonfigurowałem PyCharm, aby wykorzystywał jak największą ilość RAMu.

Z czego wynika tak długi czas potrzebny do wyświetlenia mapy? Czas parsowania przedstawionego wycinka mapy to około 5,5 sekundy, więc reszta czasu została poświęcona na wyświetlanie. Co i tak jest za długo, ale zauważyłem, że im więcej obiektów zostanie narysowanych tym czas poświęcony na wyświetlanie się wydłuża. Nie będę się w to zagłębiał, ale prawdopodobnie jest problem z wykorzystywanym wrapperem na tkinter’a. Mimo wszystko nadal zostajemy z czasem ~5 sekund na zdekodowanie mapy o rozmiarze 6MB.

A może to wina mojego algorytmu? Na wstępie oprócz odczytu podstawowych informacji takich jak nagłówek .osm oraz obszar mapy, odczytuję wszystkie współrzędne geograficzne jakie zostały wykorzystane w mapie. Dla każdego punktu alokuje pamięć (tworząc listę) z jego własnym numerem ID oraz informacją o jego koordynatach. Następnie dla tych wszystkich punktów wykonuję normalizację, która ma na celu zamianę współrzędnych geograficznych na wartość piksela XY w oknie graficznym IDE. W ostatnim etapie odczytu z pliku .osm wczytuję elementy typu "ways’" a następnie sprawdzam czy jego tagi odpowiadają moim wymaganiom tzn. czy na przykład jest to droga gruntowa. Jeżeli tak, to odczytuję wszystkie numery ID punktów z jakich składa się ta droga. Ostatni etap przed wyświetleniem to odczyt współrzędnych geograficznych, jakie kryją się pod tymi numerami ID. Jak wspomniałem wcześniej, jeden z pierwszych etapów parsowania mapy polegał na wczytaniu wszystkich "nodes" i ich numerów ID oraz współrzędnych geograficznych. Teraz te dane zostaną wykorzystane, lecz niestety kolejność zapisywania punktów w formacie .osm jest ściśle określona - są one zapisywane z południa na północ. Oznacza to, że kolejność ‘nodes’ jaka została przez nas wcześniej wczytana, zapisana, a następnie znormalizowana nie odpowiada kolejności w jakiej numery ID są podane w ‘ways’.
Przykład:

<node id="1426515186" visible="true" version="4" changeset="44017133" timestamp="2016-11-28T20:06:14Z" user="Władysław Komorek" uid="693154" lat="53.0665968" lon="23.2130973"/>
 <node id="4526908343" visible="true" version="5" changeset="87601291" timestamp="2020-07-06T12:20:13Z" user="rosomak" uid="378154" lat="53.0607610" lon="23.2150026"/>
 <node id="4753707249" visible="true" version="1" changeset="47136367" timestamp="2017-03-24T22:24:22Z" user="Władysław Komorek" uid="693154" lat="53.0610136" lon="23.2147826"/>
 <way id="482328853" visible="true" version="2" changeset="47136367" timestamp="2017-03-24T22:24:27Z" user="Władysław Komorek" uid="693154">
  <nd ref="4526908343"/>
  <nd ref="4753707249"/>
  <nd ref="1426515186"/>
  <tag k="boundary" v="administrative"/>
  <tag k="source" v="PRG"/>
 </way>

Widzimy, że:

• Pierwszy punkt "nd ref"  poprzez indywidualny numer ID odnosi się do drugiego zapisanego "node"
• Drugi punkt "nd ref" poprzez indywidualny numer ID odnosi się do trzeciego zapisanego "node"
• Trzeci punkt "nd ref" poprzez indywidualny numer ID odnosi się do pierwszego zapisanego "node"

Tutaj pojawia się największy problem, ponieważ dla każdego wyświetlanego punktu musimy znaleźć numer ID z "nd ref" we wcześniej utworzonej liście z "node", a następnie odczytać współrzędne geograficzne tego punktu. Oznacza to, skanowanie listy składającej się nie raz z kilku tysięcy punktów. Nie da się ukryć, podczas pisania tego algorytmu nie skupiałem się na wydajności, lecz chciałem poznać problematykę tego zagadnienia, dzięki czemu mogę ją teraz przedstawić.

 

A może jednak da się?

Stwórzmy czysto hipotetyczne założenie, że na promocji kupiliśmy kilka terabajtów pamięci RAM, a i algorytm do pobierania danych o obiektach jest bardziej przemyślany. Nie ma potrzeby skanowania tablicy, odczyt informacji o obiekcie jest szybszy, a wczytanie pliku przez parser XML jest natychmiastowe. Pozostaje ostatnia rzecz do rozważenia, czyli wyświetlanie wycinka mapy. Co jeżeli w pamięci mamy zapisaną mapę świata, a na ekranie chcemy wyświetlić ławkę postawioną na ul. Kazimierza w Łopuchowie? Znamy współrzędne geograficzne tego miejsca, wiec zadanie jest trochę ułatwione. Najprościej jest skanować (wykorzystując jakiś bardziej zaawansowany algorytm, niż linear search) cały plik w poszukiwaniu tych współrzędnych. Zakładając, że czas jaki został poświęcony na to zadanie  jest akceptowalny i znaleźliśmy naszą ławkę to możemy ją wyświetlić na ekranie. Problem pojawia się w momencie, gdy obok ławki istnieją jakieś inne obiekty, które też chcemy wyświetlić np. drogi. No bo po co nam wyświetlać jakiś obiekt bez żadnego punktu odniesienia.

Zacznijmy więc jeszcze raz. Rozpoczynamy skanowanie pliku i trafiliśmy na punkt, który mieści się w obszarze jaki chcemy wyświetlić (1). Teraz, żeby wyświetlić cały obiekt do którego należy ten punkt musimy skanować WSZYSTKIE "ways" i sprawdzać czy przypadkiem nasz punkt nie należy do tego elementu. Przypominam, że każdy taki element może się składać z kilkudziesięciu punktów. No dobrze, ale załóżmy, że wyświetliliśmy ten nieszczęsny obiekt, który okazał się być np. drogą. Możemy skanować nasz plik dalej w poszukiwaniu ławki i obiektów w obszarze, jaki chcemy wyświetlić. Trafiamy na kolejny punkt, który tym razem może, ale nie musi należeć do drogi, którą przed chwilą przecież wyświetliliśmy. W takim wypadku albo ponownie skanujemy wszystkie "ways" albo podczas poprzedniej operacji wyświetlania, możemy alokować pamięć z listą numerów ID, które zostały już „obsłużone” w ramach wyświetlania tegoż obiektu. W pierwszym przypadku nic się nie zmienia, skanujemy "ways" i szukamy, do jakiego obiektu odnosi się znaleziony punkt. Natomiast w drugim przypadku wpierw możemy skanować listę punktów, które zostały obsłużone i sprawdzać czy znaleziony przez nas punkt nie został już obsłużony w ramach wyświetlenia jakiegoś obiektu. Problem pojawi się wraz ze wzrostem ilości wyświetlanych na ekranie obiektów. Lista obsłużonych punktów może urosnąć do takich rozmiarów, że czas parsowania mapy może wzrosnąć diametralnie. Dodatkowo jeżeli znaleziony punkt nie został wyświetlony to skanujemy wszystkie "ways" i kontynuujemy szukanie do jakiego obiektu należy ten punkt. Oznacza to, że wpierw skanowaliśmy dynamicznie alokowaną w pamięci procesora listę obsłużonych punktów, a potem mimo wszystko musimy kontynuować parsowanie mapy w poszukiwaniu w którym "ways" znajduje się nasz punkt. No dramat.

Ten algorytm byłby pewną odwrotnością tego co przedstawiłem w poprzednim rozdziale, ponieważ tutaj skanowanie wykonuje się wyszukując "nodes". Podsumowując ten rozdział, według mnie nie da się bez pewnych modyfikacji wyświetlać mapy w formacie .osm w akceptowalnym czasie, natomiast jeżeli ktoś ma jakiś pomysł to zachęcam do udzielania się w sekcji komentarzy.

W takim razie, o jakich modyfikacjach mówię? Algorytm, który wykorzystałem do wyświetlania mapy w oknie graficznym skanuje wszystkie "ways" a następnie je wyświetla. Jeżeli na przykład jakiś budynek znajduje się poza obszarem jaki chcemy wyświetlić to zostanie on i tak przetworzony. Z tego powodu nie można go wykorzystać do obsługi dużych map, ponieważ nasza omawiana ławka byłaby niczym ziarenko piasku na Saharze. A co gdyby naszą ogromną mapę podzielić na kwadraty?

(1) Obszar ten jest zdefiniowany współrzędnymi geograficznymi i określają one „rogi” wykorzystywanego okna graficznego/wyświetlacza. Przykładowo współrzędne A(53.1025, 23.1318) określają piksel A(0,0), a współrzędne B(53.1137, 23.1440) piksel B(240,320). Dane te są wykorzystywane również podczas normalizacji danych.

 

Map tiles

Z pomocą przychodzą nam tak zwane mapy kafelkowe. Polega to na tym, że naszą mapę planety dzielimy na równe części. Taki jeden kafelek może zostać opisany koordynatami, które opisują jaki obszar mapy w nim się znajduje. Przytaczając nasz przykład z ławką, już nie musimy skanować całego pliku mapy w poszukiwaniu punktu, lecz tym razem sprawdzamy (lub wyliczamy, ale o tym w później) w którym kafelku znajduje się nasz punkt. Następnie możemy wyświetlić cały kafelek.

Przykładowy podział mapy na kafelki

To w taki sposób działają mapy na stronie OpenStreetMap. Szybko przesuwając myszką po mapie możemy zaobserwować jak kafelki są wczytywane.

Niestety to rozwiązanie niesie ze sobą pewne wady. Jeżeli w obszarze jaki chcemy wyświetlić znajduje się wiele kafelków to musimy je wszystkie wczytać, aby w całości wypełnić ekran. Jeżeli jakiś kafelek nachodzi na nasz obszar do wyświetlenia, ale również wychodzi poza niego to system spędzi trochę czasu na przetworzenie danych, które i tak nie zmieszczą się na naszym wyświetlaczu.

Podział mapy na kafelki posiadające własny numer ID

Weźmy na przykład powyższą sytuację. Rozjaśniony obszar to zakres mapy jaki chcemy przedstawić na naszym oknie graficznym lub wyświetlaczu. Program rozpozna że do wczytania ma kafelki numer 2,3,6 oraz 7. W każdym z przypadków wychodzą one za interesujący nas obszar, ale mimo wszystko musimy wczytać każdy kafelek, ponieważ jest on częścią rozjaśnionego okienka. Co prawda silnik graficzny uniemożliwi wyświetlenie budynku np. na pikselu (-25, 5205), ale nadal został zmarnowany czas na odczyt i normalizację danych.

Kolejną istotną kwestią map kafelkowych są stopnie powiększenia. Jeżeli mapę polski podzielimy na 4 równe części i będziemy chcieli ponownie wyświetlić naszą ławkę to dużo nam to nie da – pojedynczy kafelek będzie posiadał za dużo informacji, więc nasza ławka będzie małym punktem w gąszczu danych. W takim wypadku najlepiej byłoby jeszcze stworzyć pewne filtry decydujące o tym, jakie rodzaje obiektów mają zostać zapisane na każdy stopień powiększenia. Przeanalizujmy teraz poniższy obrazek:

Podział mapy na 3 stopnie zbliżeń

Możemy zaobserwować 3 przybliżenia. Pierwszy stopień dzieli mapę polski na 4 części i jest narysowany kolorem czarnym. Drugi stopień dzieli mapę polski na 16 części i jest narysowany kolorem zielonym. Trzeci stopień dzieli mapę polski na 64 kafelków i jest oznaczony kolorem niebieskim. Zgodnie z tą zasadą ilość kafelków na każdy stopień można wyrazić wzorem:

gdzie:
            n – stopień zbliżenia

Teraz dla każdego z tych poziomów należałoby zdefiniować jakie informacje mają być w nim zawarte. Dla stopnia n = 1 nie ma sensu w kafelkach zapisywać informacji o pojedynczych obiektach takich jak np. sklepy, ponieważ rozdzielczość ekranu uniemożliwi nam poprawne wyświetlenie takich informacji. Aczkolwiek wszystko zależy od aplikacji, być może ktoś potrzebuje obserwować sklepy na terenie polski wtedy jak najbardziej można takie dane umieścić w kafelkach. Dodatkowo mamy możliwość filtracji dróg, które chcemy wyświetlić. Na największym oddaleniu nie chcielibyśmy obserwować ścieżek rowerowych, czy chodników (chyba, że akurat aplikacja tego wymaga). Wracając do przykładu z naszą ławką powinna ona zostać wyświetlona, dopiero na odpowiednim powiększeniu np. 8. A ile to będzie kafelków mapy na takim powiększeniu? 65 536.
No i tutaj wkracza kolejna potencjalna wada map kafelkowych. Niektóre stopnie mogą współdzielić ze sobą niektóre dane, a im więcej tych stopni tym większa szansa na to. Wyobraźmy sobie taki układ ”filtrów”:

Filtry dla każdego stopnia zbliżenia

To czy jest to rzeczywiście wadą zależy od sposobu kodowania formatu tzn. czy uwzględnia on fakt, że jeden obiekt może być widoczny na kilku stopniach zbliżeń (i kafelków).

Myślę, że po omówieniu powyższych rozdziałów, część z Was domyśliła się do czego zmierza ten artykuł. Chcąc nie chcąc, musimy stworzyć swój własny format kodowania map, który jest "przyjazny" dla mikrokontrolera. Przyjazny w tym przypadku znaczy taki, który nie będzie wymagał czasochłonnego parsowania danych oraz nie będzie potrzebował dużej ilości RAMu.

 

Format .ltd - podejście pierwsze

Dotarliśmy to tego momentu, gdzie mogę zacząć opisywać format, który stworzyłem w celu wykorzystania go przez systemy wbudowane. Podsumujmy co wiemy:

• Nie możemy wykorzystać formatu .osm, ponieważ jego objętość oraz czas potrzebny do przeparsowania danych jest za duży.
• Najlepiej przygotować format w taki sposób, że procesor będzie mógł wczytać wszystkie dane o obiekcie za jednym razem, bez potrzeby szukania gdzie są wszystkie współrzędne geograficzne obiektu. Cały proces parsowania zostanie wykonany przed wgraniem mapy na kartę SD.
• Trzeba wykorzystać idee map kafelkowych, aby w łatwy sposób ustawić filtry oraz przyspieszyć proces odczytu i wyświetlania danych.
• Rozmiar formatu musi być jak najmniejszy, ale trzeba znaleźć kompromis pomiędzy wydajnością, a objętością.

Tworząc format zacząłem od rozważania jak wykorzystać idee map kafelkowych, jednocześnie sprawiając, aby współdzielone filtry stopni nie zajmowały dodatkowego miejsca w formacie. Chodzi o to, że jeśli np. rzeka jest widoczna na stopniu n = 1 jak również n = 4 to oba te stopnie muszą zawierać te same informacje o rzece. Mamy tutaj dwie możliwości – albo wpisać te dane o obiekcie (takie jak rodzaj i wszystkie współrzędne geograficzne) w tych obu stopniach albo stworzyć globalny plik ze spisem wszystkich obiektów, jakie istnieją na całej mapie. Wtedy zamiast kopiowania danych o obiekcie do każdego ze stopnia który wykorzystuje dany filtr, wpisujemy jedynie adres do lokacji w pamięci, gdzie znajduje się początek danych o obiekcie.

Zanim przejdziemy dalej, chciałbym nadmienić, iż opisywany poniżej format okazał się nie najlepszym rozwiązaniem z powodu opisanego na końcu rozdziału. Mimo wszystko postanowiłem go tutaj opisać, bo nadal może zostać wykorzystany w innych projektach.
W następnym rozdziale zostanie już opisany w pełni funkcjonalny format .ltd.

Zgodnie z założeniami, format pliku zawierającego spis wszystkich obiektów został utworzony w następujący sposób:

Format pliku zawierający spis wszystkich obiektów w mapie. W dalszej części artykułu będzie on opisywany jako "plik II"

Widzimy, że pierwszą informacją jaka się pojawia jest jeden bajt informujący o typie obiektu jakie będą następować. Z każdą zmianą typu obiektu bajt ten musi zostać wstawiony. Jeżeli następny wstawiony obiekt jest tego samego typu to bajt ten jest pomijany. Każdy wstawiony obiekt dodatkowo musi posiadać informacje o podtypie lub inaczej rodzaju obiektu. Informacja ta musi zostać zawsze dodana niezależnie czy zmienił się typ obiektu czy też nie. Następną informacją jest ilość punktów, które opisują dany obiekt. Informacja ta jest wykorzystywana przez procesor odczytujący format, aby przed wczytaniem wszystkich punktów zaalokować odpowiednią ilość pamięci. Następnie pojawiają się współrzędne geograficzne punktu w formacie float. Punktów jest tyle ile zostało zadeklarowanych wcześniej. Przykładowy plik może zostać zbudowany w taki sposób:

Przykładowa struktura pliku II w formacie .ltd

Wydaje mi się, że na razie wszystko jest jasne i nie powinno być problemów ze zrozumieniem tematu. Myślę, że możemy teraz przejść do pliku w którym znajdują się wskaźniki na adresy do tych obiektów w pliku II, czyli pliku ze stopniami zbliżenia (plik III).

Format pliku zawierający informacje o obiektach w kafelkach. W dalszej części artykułu będzie on opisywany jako "plik III"

Przede wszystkim w tym pliku znajdują się nie tylko wskaźniki na adresy (podane w bajtach) do obiektów w pliku II, ale również wszystkie stopnie zbliżenia oraz wszystkie kafelki w tych stopniach. Każdy stopień zbliżenia rozpoczyna się jednym bajtem informującym o właśnie jego stopniu. Następnie wszystkie 4 koordynaty o typie danych float określają rozmiar kafelka. Kolejna informacja mówi o ilości obiektów w danym kafelku. Kolejny jeden bajt określa rozmiar wskaźnika na adres obiektu w pliku II. Rozmiar wskaźnika jest poniekąd nazwą potoczną. Chodzi o to, że jeżeli informacja o obiekcie znajduje się na bajcie dajmy na to pięćsetnym to addr_obj_size_n przyjmie wartość 2. Analogicznie, jeżeli jakikolwiek obiekt znajduje się powyżej 65535B to addr_obj_size_n przyjmie wartość 4. Na końcu znajdują się wskaźniki na informacje o obiektach w pliku II, ale z pewną uwagą. Wskaźnik ten jest podawany, jako offset od wskaźnika na typ obiektu. Z tego powodu jest dodawany jeden bajt określający na jaki typ obiektu wskazuje wskaźnik. Dzięki takiemu zabiegowi zyskujemy dodatkową oszczędność na rozmiarze pliku. Przykładowy plik może zostać zbudowany w taki sposób:

Przykładowa struktura pliku III składającego się z dwóch stopni zbliżenia

Dodałem trzecia kolumnę, aby łatwiej było odczytać informacje z tabeli. Możemy zaobserwować, że wpierw pojawia się informacja o stopniu zbliżenia, a następnie po kolei są opisywane kafelki. Gdy wszystkie kafelki zostaną opisane kolejny stopień zbliżenia zostaje wstawiony wraz z jego kafelkami i adresami do obiektów w nim się znajdujących.
Został nam do opisania ostatni plik, który zepnie wszystko w funkcjonalną całość. Opiszę go w dwóch turach.

Format nagłówka pliku I

Pierwsze 4 bajty informują nas o rozszerzeniu pliku. Dane są zapisane jako ASCII. Kolejne 4 bajty zawierają informacje o dacie utworzenia pliku. Następnie dostajemy informacje o tym ile bajtów zajmuje każdy z plików. Informacja ta jest wykorzystywana podczas obliczania offsetów do wskaźników. Kolejne dane służą do określenia rozmiaru całej mapy poprzez podanie współrzędnych geograficznych. Informacja ta w dalszym etapie przyda się do normalizacji współrzędnych geograficznych obiektów. Dalej w postaci jednego bajta przechowywana jest informacja ile stopni zbliżeń obsługuje ta mapa. Następnie zapisane są 32 adresy o rozmiarze 8 bajtów. Adresy te wskazują na typy obiektów w pliku drugim. Wartość 32 nie wzięła się z przypadku, po prostu tyle typów obiektów jest aktualnie w pełni wspieranych przez OSM. Adresy te są wykorzystywane w dalszym etapie, aby odnosić się adresem do informacji o danym obiekcie przez offset do typu obiektu, a nie liczyć od początku pliku. Następnie w pliku znajdują się adresy do informacji o danym poziomie zbliżenia. Dlaczego adres, a nie od razu ciąg z informacjami? Ponieważ długość zawartych informacji o zbliżeniu jest różna dla każdego poziomu zbliżenia. Gdybyśmy nie zastosowali adresowania, to z każdym przełączeniem się pomiędzy zbliżeniem musielibyśmy parsować plik, aby określić gdzie znajduje się zbiór docelowych danych. W takim wypadku wystarczy zaledwie zapisać w pamięci RAM procesora adres do zbioru danych o poziomie zbliżenia i przy jego zmianie skakać wskaźnikiem R/W do docelowego zbioru informacji (wskaźnik R/W określa numer bajtu w otworzonym pliku, od którego rozpocznie się następny zapis/odczyt danych). A jak kodowany ten zbiór informacji?

Format kodowania informacji o poziomach zbliżeń w pliku I

Wpierw w postaci 8 bajtów zostaje zakodowany adres do danego poziomu zbliżenia w pliku III. Następnie 2 bajty informują ile kafelków znajduje się w tym poziomie zbliżenia, a kolejne 2*4 bajty określają rozmiar każdego kafelka jako współrzędne geograficzne . Addr_size działa na podobnej zasadzie jak było to omówione wcześniej, czyli informuje jaki jest rozmiar następujących adresów. Adresy te wskazują na lokalizację kafelków w pliku III, ale uwaga – jako offset od zoom_addr_n. Przykładowy plik I może zostać zbudowany w taki sposób:

 
Przykładowa struktura pliku I składającego się z nagłówka oraz dwóch różnych stopni zbliżenia

Na jakiej zasadzie to działa od strony dekodera? Wpierw wczytywany jest plik I czyli plik nagłówkowy. Sprawdzane jest jego rozszerzenie, a następnie w pamięci RAM zostają zapisane informacje o rozmiarach plików, rozmiarach całej mapy, ilości poziomów zbliżenia, wszystkie adresy do typów obiektów oraz wszystkie adresy do poziomów zbliżeń. Wstępny proces inicjalizacji został zakończony i można rozpocząć wyświetlanie mapy. Teraz, jeżeli procesor chce odczytać wszystkie obiekty na danym poziomie zbliżenia i w danym kafelku to w pierwszej kolejności pobiera wszystkie informacje o danym zbliżeniu. W związku z tym dekoder: 

1. Wykorzystuje zapisany w pamięci adres do zoom_start_n w pliku I i stosuje go do przemieszczenia wskaźnika R/W na odpowiedni bajt.
2. Zapisuje informacje o ilości kafelków dla danego poziomu zbliżenia
3. Zapisuje rozmiar pojedynczego kafelka
4. Zapisuje rozmiar adresów do kafelków

Od tego momentu dekoder ma wszystkie potrzebne informacje do przetwarzania mapy i danych o obiektach. Chcąc wyświetlić wszystkie obiekty z wybranego kafelka dekoder:

1. Pobiera adres map_tile_addr_n
2. Przechodzi do pliku III i przesuwa wskaźnik R/W na bajt zoom_start_n + map_tile_addr_n
3. Jeżeli wszystkie kafelki są tego samego rozmiaru to dodatkowo przesuwa wskaźnik R/W o 16 bajtów, ponieważ nie musimy odczytywać jego współrzędnych geograficznych. Jeżeli kafelki mają różne wymiary to odczytywany jest jego rozmiar poprzez podane koordynaty. Informacja ta jest potrzebna podczas normalizacji danych.
4. Odczytuje ile znajduje się obiektów w danym kafelku oraz rozmiar wskaźnika do adresów w pliku II
5. Odczytuje adres do obiektu (object_addr_n), który znajduje w pliku II
6. Przechodzi do pliku II i przesuwa wskaźnik R/W na object_addr_n + object_type_addr_n
7. Odczytuje rodzaj obiektu i jeżeli jest on wspierany przez dekoder to kontynuuje odczyt. Jeżeli nie to wraca do pliku III i proces powtarza się od punktu 5, wpierw przesuwając wskaźnik R/W o addr_size
8. Odczytuje ilość punktów z jakich składa się obiekt
9. Alokuje odpowiednią ilość bajtów w pamięci wewnętrznej
10. Odczytuje wszystkie punkty, a następnie na ich podstawie rysuje obiekt na wyświetlaczu
11. Po skończonej operacji wyświetlania dekoder przechodzi z powrotem do pliku III i cykl się powtarza od punktu 5, jeżeli zostały jeszcze obiekty do wyświetlenia. Jeżeli był to ostatni obiekt to cykl się kończy

Wydawać by się mogło, że ta metoda kodowania formatu ma same plusy. Mały rozmiar pliku, współdzielenie obiektów między poziomami zbliżeń oraz mały footprint. Niestety podczas pierwszych testów życie zweryfikowało moje zamiary. Wyświetlanie mapy trwało bardzo długo. Obszar 0.2km­­2 renderował się około 2 sekund, a na największych oddaleniach czas przetwarzania dochodził do 10 sekund. Moje pierwsze obawy były o wydajność procesora, lecz im bardziej zagłębiałem się w problem zacząłem obserwować, że to nie to. Po kilku testach doszedłem do sedna problemu, który trawił mój projekt od środka. Problemem okazały się zbyt częste przesunięcia wskaźnika R/W (prawdopodobnie o rozmiar partycji). Skok wskaźnika R/W pomiędzy obiektami w pliku II wprowadzał opóźnienie równe 4ms. W pojedynczym kafelku może być kilkaset obiektów, a bardzo często trzeba odczytać kilka kafelków. Musiałem zrezygnować z tego formatu i utworzyć inny, unikając skoków wskaźnika R/W. Mimo wszystko w załączniku znajduje się kod do kodera.

Format .ltd – podejście drugie (i ostatnie)

Tym razem do założeń musimy dodać kwestię unikania skoków wskaźnika R/W. Co to oznacza w praktyce? Niestety nie będziemy mogli w formacie współdzielić informacji o obiektach pomiędzy poziomami zbliżeń. Po wejściu w kafelek zamiast przejścia do pliku  II i przesuwania wskaźnika R/W, będziemy musieli od razu odczytywać informacje o obiektach w nim się znajdującym . To z kolei oznacza, że informacje o obiektach, które występują na kilku poziomach zbliżeń zostaną tak naprawdę powielone, przez co rozmiar formatu się zwiększy. Na tym etapie projektu nie jest to diametralna wada, ale nadal istotna i warta zapamiętania, aby w przyszłości rozwiązać ten problem.
W takim wypadku ubywa nam plik II zawierający informacje o wszystkich obiektach, ponieważ te będą przechowywane bezpośrednio w kafelkach. Tym razem format pliku I, który będziemy zapisywać z rozszerzeniem .hdr został uproszczony i wygląda następująco:

Format pliku I, który będziemy traktować jako nagłówek mapy. Plik jest zapisywany w rozszerzeniu .hdr

Decyzja o takim uproszczeniu pliku wynika  z możliwości zmniejszenia footprintu jaki jest potrzebny do obsługi formatu. Po prostu po inicjalizacji, plik I może zostać zamknięty i zapomniany, dlatego informacje potrzebne do jego otworzenia będą przechowywane lokalnie. A co się znajduje w tym pliku? Jego rozmiar jest stały, więc zawsze wygląda tak samo, jedynie dane w nim zawarte ulegają zmianie. Pierwsze 4 bajty tak jak poprzednio opisują rozszerzenie w kodzie ASCII. Kolejne 4 bajty to data kodowania mapy,  a następnie widzimy 13 bajtów, które odnoszą się do nazwy mapy. Następne 16 bajtów opisują rozmiar całej mapy poprzez współrzędne geograficzne. Ostatnią informacją jest ilość stopni zbliżeń, jakie zostały utworzone dla tej mapy. I tyle. Wypadałoby jeszcze zawrzeć informacje, jakie stopnie zbliżeń zostały przypisane tej mapie, ale to pozostawiam do dalszego rozwoju. Wynika to z tego, że ilość poziomów zbliżeń zależy od rozmiaru mapy, więc w przyszłych rozważaniach powinno to być liczone automatycznie. Na ten moment w koderze stopnie zbliżeń powinniśmy zdefiniować sami.

Przejdźmy zatem do drugiego formatu plików (a zarazem ostatniego). Specjalnie napisałem plików, a nie pojedynczego pliku, ponieważ może ich być kilka. Te pliki po prostu zawierają wszystkie informacje na temat danego stopnia zbliżenia jak również dane o kafelkach i znajdujących się w nich obiektach. Pliki te są tworzone pod nazwą zgodnie z formą:

<x>_<n>.ltd

gdzie:
            x – nazwa mapy
            n – stopień zbliżenia

Ponownie omawianie formatu podzielę na dwie części. Wpierw nagłówek pliku II:

Nagłówek pliku II, który zawiera informacje tylko o danym stopniu zbliżenia oraz wskaźniki do kafelków

Jak możemy zauważyć, nagłówek ten nie różni się znacznie od nagłówka opisującego poziom zbliżenia w poprzednim rozdziale (w pliku I). Ponownie tutaj jest przechowywana informacja o poziomie zbliżenia, ilości kafelków, ich rozmiar oraz adresy na każdy z kafelków. Jedyna różnica to pierwsze 13 bajtów, które opisują nazwę, do której mapy się odnosi ten plik. Dekoder zanim rozpocznie dekodowanie danych wpierw powinien upewnić się, że rzeczywiście odnosi się do odpowiedniego stopnia zbliżenia oraz odpowiedniej mapy.

Kontynuując, kolejne dane w tym pliku są kodowane zgodnie z poniższym formatem:

Format kodowania informacji o pojedynczym kafelku w pliku II

Dane w powyższej tabeli opisują pełne informacje o pojedynczym kafelku. Pierwsze 16 bajtów jest przeznaczone na opisanie rozmiaru pojedynczego kafelka poprzez współrzędne geograficzne. Następnie 2 bajty opisują ile znajduje się wszystkich typów obiektów w tym kafelku. Kolejne dane będą już dotyczyły konkretnego typu obiektu oraz obiektów, jakie będą następowały. Pod bajtem nazwanym „object_type” kryje się informacja o typie obiektu np. droga. Następnie „objects_qnty” określa ile poniżej znajduje się tychże obiektów. Kolejna informacja „subobject_type” mówi nam o tym jaki to jest rodzaj obiektu. Po odczytaniu tych informacji możemy zdekodować, że na przykład następujące informacje będą dotyczyły:

• Drogi - typ obiektu
• Gruntowej - rodzaj obiektu
• 52 - ilość dróg w tym kafelku

Dalej podawane są już współrzędne geograficzne dla tego obiektu, a o ich ilości decyduje „point_qnty”. Jeżeli przykładowo w kafelku znajduje się wiele typów obiektów (np. drogi, lasy, budynki) to każdy kolejny obiekt jest dodawany zaczynając od „object_type”. Dzięki takiej budowie formatu można w prosty sposób utworzyć warstwy obiektów i zdecydować, co ma być wyświetlane pierwsze. Z reguły pierwszym typem obiektów jaki chcemy wyświetlić są te opisywane przez OSM jako „natural” w skład której wchodzą np. pola. Następną warstwą może być np. droga. Gdybyśmy zamienili warstwy i wpierw wyświetlali drogę (która akurat przechodzi przez pole), a następnie pola to drogi byłby niewidoczne, ponieważ zostałyby przykryte przez poligon typu „natural”. Przykładowy plik z dwoma kafelkami, typami obiektów oraz ich rodzajami może wyglądać następująco:

Przykładowa struktura pliku II, który zawiera wszystkie informacje o jednym poziomie zbliżenia

Każdy kafelek rozpoczyna się dwoma bajtami danych „all_objects_type”. To właśnie do tego bajtu wskazują adresy, które kryją się pod „map_tile_addr_n”. Jest to pierwsza informacja o kafelku jaką dekoder odczyta. Może się pojawić pytanie, w jakim celu podawane są współrzędne geograficzne kafelka (obszar zaznaczony na niebiesko), skoro nie są one wczytywane. Jest to informacja dodatkowa i może zostać wykorzystana, gdy kafelki nie są jednakowych wymiarów.

Prześledźmy po kolei jak dekoder może odczytać dane o wszystkich obiektach w pierwszym kafelku.

1. Wpierw rozpoczynamy proces inicjalizacji poprzez sprawdzenie czy wybrany plik jest zgodny z nazwą mapy jaką teraz obsługujemy. Jeśli jest to kontynuujemy proces odczytywania danych
2. Odczytujemy jaki to jest poziom zbliżenia
3. Odczytujemy ile jest kafelków w tym poziomie zbliżenia oraz rozmiar pojedynczego
4. Odczytujemy „addr_obj_size” i przesuwamy wskaźnik R/w o
                                                                                                                    addr = n * addr_obj_size
   gdzie:
              n  - interesujący nas kafelek
   W naszym przypadku wskaźnik R/W powędruje na „map_tile_addr_0”.
5. Odczytujemy adres, przesuwamy wskaźnik R/W na zdekodowaną wartość i już znajdujemy się w kafelku
6. Rozpoczynamy dekodowanie pojedynczego kafelka. Odczytujemy „all_objects_type”, które w tym przypadku będzie wynosiło 2
7. Odczytujemy bajt „object_type”, który mówi nam o typie obiektów jakie będą następowały. Otrzymana wartość jest liczbowa i wynosi np. 5. Na potrzeby wyjaśnienia możemy założyć, że 5 odpowiada obiektom typu droga, a 29 obiektom typu budynek
8. Pozostała nam ostatnia wartość do odczytania czyli „objects_qnty”, która w tym przypadku będzie wynosiła 2. Po tym wszystkim dotarliśmy do miejsca, gdzie rozpoczyna się opisywanie obiektów
9. Rozpoczynamy dekodowanie pierwszego obiektu typu: droga. Odczytujemy jaki to jest rodzaj drogi np. leśna
10. Odczytujemy z ilu współrzędnych geograficznych jest ona zbudowana
11. Alokujemy odpowiednią ilość w pamięci RAM i odczytujemy jednym ciągiem wszystkie współrzędne geograficzne
12. Następnie, odczytana przez nas wcześniej informacja „objects_qnty” wynosi 2, a my dopiero odczytaliśmy jeden obiekt. Musimy kontynuować dekodowanie obiektów. Ponownie odczytujemy rodzaj obiektu i wykonujemy kroki 10 - 11
13. Po tej operacji wartość odczytanych obiektów jest równa wartości „objects_qnty”. Wiemy jednak, że w tym kafelku znajdują się dwa typy obiektów – mówi nam o tym zdekodowana wartość „all_objects_type”. Musimy kontynuować odczyt poprzez powtórzenie kroków 7-11. Powiedzmy, że tym razem odczytana wartość „object_type” wynosi 29, a jak wiemy określa to typ obiektu jako budynek. Jednak w tym przypadku „objects_qnty” będzie równy 1, ponieważ w tym kafelku jest tylko jeden obiekt typu budynek. Następnie „subobject_type” określi jaki to jest rodzaj budynku np. wielorodzinny
14. Po wczytaniu wszystkich punktów (dla obiektu: budynek wielorodzinny są to dwie współrzędne geograficzne) wartość odczytanych typów obiektów będzie równa „all_objects_type”. Również dla obu typów obiektów „objects_qnty” będzie równe ilości obiektów do odczytania w kafelku. Oznacza to, że odczytaliśmy wszystkie dane zawarte w wybranym kafelku
15. Proces dekodowania zakończony        

Podsumowanie

W tej części artykułu opisałem problematykę związaną z dekodowaniem formatu .osm. Jak zostało to opisane, nie możemy wykorzystać "surowego" pliku .osm, ponieważ czas na jego parsowanie jest zbyt długi nawet na bardzo wydajnym systemie. Aby móc wyświetlać mapy na systemie wbudowanym, trzeba było stworzyć format map, który jest bardziej przyjazny dla mikrokontrolera. Przedstawione formaty, zostały stworzone na cel projektu do wyświetlania pozycji GPS. Wiem, że niektóre kwestie zawarte w formacie mogą wprowadzać w zakłopotanie, dlatego zachęcam do zadawania pytań w sekcji komentarzy.
Myślę, że teraz mogę zdradzić rąbek tajemnicy następnej części artykułu i odpowiedzieć na pytanie czy rzeczywiście tak stworzony format jest szybszy. Odpowiedź brzmi tak! W poprzednim podejściu wyświetlenie obszaru 0,2km2 trwało około dwóch sekund. Tym razem zajmuje to około 150ms!

W następnej części artykułu zajmiemy się tworzeniem kodera przedstawionego formatu .ltd.

Spis treści:

1. Przetwarzanie OpenStreetMap na systemie wbudowanym #1 - Format .osm
2. Przetwarzanie OpenStreetMap na systemie wbudowanym #2 - Parsowanie formatu .osm
3. Przetwarzanie OpenStreetMap na systemie wbudowanym #3 - Kodowanie formatu .ltd
4. Przetwarzanie OpenStreetMap na systemie wbudowanym #4 - Dekodowanie formatu .ltd

[Treker (Damian Szymański)]

@kronikary artykuł został właśnie zaakceptowany i jest już dostępny publicznie

[Leander]

Na programowaniu się nie znam, ale na OSM tak, więc pozwolę sobie na komentarz :).

Format danych warto dostosować do zastosowania. Kafelki są gotową wizualizacją, czyli rastrem tego, co można podejrzeć na stronie OSM. Plik osm (GML) natomiast jest plikiem (w praktyce) wektorowym (co pokazałeś w pierwszej części artykułu) i bazodanowym, pozbawionym wizualizacji - to są surowe, ale OBIEKTOWE dane. Jeśli potrzebujemy np. mapy jako statycznego podkładu do aplikacji wyświetlającej położenie użytkownika, to format osm jest często złym pomysłem (choć jest lżejszy niż kafelki). Jeśli potrzebujemy możliwości kliknięcia w dom czy drogę, albo własnej symbolizacji (kolor, symbol) na bazie atrybutów obiektu - wtedy jak najbardziej.

Niestety OSM nie wystawia serwera usługi WMS/WMTS, co jest - wg mnie - wygodniejszym i bardziej klarownym rozwiązaniem pobierania kafelków.

[kronikary]

@Leander Jakiś czas temu zastanawiałem czy kafelki pobierane z serwera są danymi wektorowymi czy rastrowymi (o czym wspomniałem w części IV). Dziękuję za odpowiedź, bo rozwiałeś mi tę wątpliwość. Odnośnie zaprezentowanego formatu - zdecydowałem się na dane wektorowe przede wszystkim z powodu właśnie rozmiarów kafelków rastrowych oraz urządzenia w którym wykorzystuje format. Lecz tak jak mówisz, wszystko zależy od aplikacji.

Edytowano Marzec 31, 2021 przez kronikary

[Leander]

Kafelki - jeśli widzisz dokładnie to, co widać na stronie (w serwisie mapowym), to są to rastry generowane z kompozycji mapowej. Wygenerowanie tego typu wizualizacji w locie z danych wektorowych (które są tylko geometrią) to dodatkowe zadanie (w niektórych narzędziach są wtyczki, które robią ładną mapę z chociażby danych BDOT10k - polska baza państwowa). Wspomniany WMS ma fajną cechę, bo dane na serwerze mogą być wektorem, użytkownik dostaje je zrastrowane, ale jest możliwość odpytania serwera o dane z bazy na podstawie współrzędnych z rastra. Czyli dostaję obrazek, klikam w punkt i mam pełną tabelę atrybutów, bo odpytuję bazę za pośrednictwem rastra (widać to dobrze w narzędziu identyfikacji na geoportalu). W kafelkach działa to inaczej (nie licząc kafelków w usłudze WMTS). Tu jest o "tilesach" z OSM: https://wiki.openstreetmap.org/wiki/Tiles Z tego, co widzę, to często jest png.

Edytowano Kwiecień 1, 2021 przez Leander

[Marcin648]

Wydaje mi się że zasadne było by trzymać przetworzony OSM w postaci binarnej, a całość wrzucić do Quadtree aby szybko filtrować obiekty z danego obszaru.
A przynajmniej ja tak bym do tego podszedł

 

[kronikary]

@Marcin648 Właściwie to tak jest to zrobione - każdy kafelek jest dzielony na 4 mniejsze