Konzeption und Implementierung eines Binärformats zur effizienten Übertragung von OpenStreetMap-Daten auf mobile Endgeräte zur dynamischen Generierung individueller Karten


Studienarbeit, 2010

94 Seiten, Note: 1,3


Leseprobe


Inhaltsverzeichnis

1 Einleitung
1.1 OpenStreetMap
1.1.1 Datenformat von OpenStreetMap
1.1.2 Beispiele von XML-Daten
1.1.3 Gerendertes Kartenmaterial
1.2 Ziel dieser Arbeit

2 Vorbereitende Analyse-Skripte
2.1 Zeilenweise Analyse
2.1.1 Stringlange in den Tag-Values
2.1.2 Anzahl Tags, Members und Nds pro Element
2.1.3 Relationen: Typen und Rollen
2.2 Analyse der Tags
2.3 Eintragung in eine MySQL-Datenbank
2.3.1 MySQL-Datenbankschema
2.3.2 Einsatz des Skripts
2.4 Analyse aus der Datenbank
2.4.1 Relative Kodierung gemaB OpenStreetMap-Wiki
2.4.2 Alternative Kodierung mittels Flex-Byte
2.4.3 Gegenuberstellung der Moglichkeiten am Beispiel
2.4.4 Ergebnisse

3 Entwicklung des Binarformats
3.1 Grundliegende Bausteine
3.1.1 Bytereihenfolge von Integer-Daten
3.1.2 Flexibler Integer
3.1.3 Strings
3.1.4 Geographische Koordinaten
3.1.5 Header-Byte
3.2 Element-Header
3.3 Kodierung eines Knoten
3.4 Kodierung eines Wegs
3.5 Kodierung einer Relation
3.6 Kodierung der Tags
3.6.1 Direkte Kodierung in einem Byte
3.6.2 Kodierung des Keys
3.6.3 highway-Tags
3.6.4 amenity-Tags
3.6.5 natural-Tags
3.6.6 Beschrankungstags
3.6.7 railway-Tags
3.6.8 waterway-Tags
3.6.9 power-Tags
3.6.10 boundary-Tags
3.6.11 barrier-Tags
3.6.12 leisure-Tags
3.6.13 shop-Tags
3.6.14 tourism-Tags
3.6.15 cycleway-Tags
3.6.16 man_made-Tags
3.6.17 sport-Tags
3.6.18 Kodierung von allgemeinen Tags
3.6.19 Ignorieren bestimmter Tags
3.7 Beispiele
3.7.1 Beispiel: Kodierung von Knoten
3.7.2 Beispiel: Kodierung eines Wegs
3.7.3 Beispiel: Kodierung einer Relation

4 Implementierung des Binarformats
4.1 Implementierung als Stand-Alone-Anwendung
4.2 Package osm
4.3 Package io
4.4 Package parser
4.4.1 Klasse Parser
4.4.2 Klasse Tools
4.4.3 Klasse EnumParser
4.5 Package parser.enums
4.5.1 Aufzahlungsklasse DirectTag
4.5.2 Aufzahlungsklasse TagKey
4.5.3 Aufzahlungsklasse TagKeyValue
4.5.4 Aufzahlungsklassen RestrictionTagKey und RestrictionTagValue
4.5.5 Klasse RestrictionTag
4.5.6 Aufzahlungsklasse DirectRole
4.5.7 Aufzahlungsklasse RelationType
4.6 Default-Package
4.7 Analyse des eingesparten Datenvolumens
4.7.1 Analyse-Skript
4.7.2 Ergebnisse
4.7.3 Fazit
4.8 Analyse der Laufzeit
4.8.1 Analyse-Skript
4.8.2 Ergebnisse
4.8.3 Fazit

5 Einbettung als Server-Dienst in den ROSE-Server
5.1 Protokoll
5.1.1 Koordinaten
5.1.2 Filtern von Elementtypen
5.1.3 Filtern von Tags
5.1.4 Ausgabe des Ergebnisses
5.1.5 Ausgabe im Fehlerfall
5.2 Implementierung
5.2.1 Klasse OsmBinaryAnfrageController
5.2.2 Klasse OsmBinaryErrorCode

6 Erweiterung des ROSE-Client
6.1 Einschrankungen durch Compiler-Version
6.2 Implementierung des Parsers
6.2.1 Klasse EnumHandler
6.2.2 Package parser.enums
6.2.3 Klasse Tools
6.2.4 Klasse OSMDataInputStream
6.2.5 Klasse OSMTag
6.2.6 Klassen OSMNode, OSMWay, OSMRelation, OSMMember, OSMType
6.2.7 Klassen Parser und OsmBinaryErrorCode
6.3 Aufbau der MapForm im ROSE-Client
6.4 Die Overlay-Klasse GMOOpenStreetMap
6.4.1 Anforderung eines Daten-Updates
6.4.2 Race-Conditions beim asynchronen Daten-Update
6.4.3 Cache
6.4.4 Berechnung des Koordinatenrechtecks
6.4.5 Klasse OpenStreetMapHandler
6.4.6 POIs: Symbole und Symbolzuordnung zu den OpenStreetMap-Tags
6.4.7 StraBen: Zuordnung von Farben zur Hochstgeschwindigkeit
6.5 Einbettung der Overlay-Klasse

7 Zusammenfassung und Ausblick
7.1 Zusammenfassung
7.2 Mogliche Verbesserungsansatze
7.3 Ausblick

A Literaturverzeichnis

Abbildungsverzeichnis

Abbildung 1: Google Earth - Ansicht der Nurnberger Altstadt mit POIs

Abbildung 2: Mapnik-Karte

Abbildung 3: Osmarender-Karte

Abbildung 4: CycleMap-Karte

Abbildung 5: Hiking-Karte

Abbildung 6: OPNV-Karte

Abbildung 7: Reit- und Wanderkarte

Abbildung 8: gerendertes Multi-Polygon

Abbildung 9: Ansicht der Testergebnisse im Browser

Abbildung 10: Ausschnitt aus dem OpenStreetMap-Symbolsatz classic

Abbildung 11: Ausschnitt aus dem OpenStreetMap-Symbolsatz square

Abbildung 12: Schematischer Aufbau: OpenStreetMap-Kacheln und Overlays

Abbildung 13: Koordinaten in der Mitte einer Kachel

Abbildung 14: Koordinaten in der oberen linken Ecke der Kachel

Abbildung 15: Koordinaten in der oberen rechten Ecke der Kachel

Abbildung 16: Koordinaten in der unteren linken Ecke der Kachel

Abbildung 17: Koordinaten in der unteren rechten Ecke der Kachel

Abbildung 18: erweitertes Koordinatenrechteck

Abbildung 19: unknown-Symbol

Abbildung 20: Sequenzdiagramm MapForm

Abbildung 21: ROSE-Client vorher

Abbildung 22: ROSE-Client mit OpenStreetMap-Binardaten

Abbildung 23: ROSE-Client vorher (Google-Satellitenansicht)

Abbildung 24: ROSE-Client mit OpenStreetMap-Binardaten (Google- Satellitenansicht)

Tabelle 1: Stringlange in den Tag-Values

Tabelle 2: Tags pro Element in europe.osm

Tabelle 3: Knoten pro Weg in europe.osm

Tabelle 4: Mitglieder pro Relation in europe.osm

Tabelle 5: Haufigst vorkommende Typen von Relationen

Tabelle 6: Haufigst vorkommende Rollen in Relationen

Tabelle 7: Haufigst vorkommende (Key, Value)-Kombinationen bei Tags

Tabelle 8: Vergleich zwischen relativer Kodierung und der Flex-Byte-Kodierung

Tabelle 9: Flexibler Integer

Tabelle 10: Header-Byte

Tabelle 11: Element-Header

Tabelle 12: Kodierung eines Knoten

Tabelle 13: Flex-Byte

Tabelle 14: Kodierung eines Wegs

Tabelle 15: Typen von Relationen

Tabelle 16: Direkte Kodierung von Rollen

Tabelle 17: Kodierung einer Relation

Tabelle 18: Kodierung von Relationsmitgliedern

Tabelle 19: Direkte Tags in einem Byte kodiert

Tabelle 20: Direkte Kodierung des Keys

Tabelle 21: Kodierung von highway-Tags

Tabelle 22: Kodierung von amenity-Tags

Tabelle 23: Kodierung von natural-Tags

Tabelle 24: Kodierung von Beschrankungen

Tabelle 25: Kodierung von railway-Tags

Tabelle 27: Kodierung von power-Tags

Tabelle 28: Kodierung von boundary-Tags

Tabelle 29: Kodierung von barrier-Tags

Tabelle 30: Kodierung von leisure-Tags

Tabelle 31: Kodierung von shop-Tags

Tabelle 32: Kodierung von tourism-Tags

Tabelle 33: Kodierung von cycleway-Tags

Tabelle 34: Kodierung von man_made-Tags

Tabelle 35: Kodierung von sport-Tags

Tabelle 36: Flex-Byte im Detail

Tabelle 37: Ersparnis an Datenvolumen

Tabelle 38: Laufzeit

Tabelle 39: Bitmaske zur Filterung von Elementen

Tabelle 40: Ausgabe im Fehlerfall

Tabelle 41: Farbbelegungen fur StraBen gemaB Hochstgeschwindigkeit

1 Einleitung

Navigation und Karten haben in den letzten Jahren zunehmend an Bedeutung gewon- nen. Wahrend anfanglich nur StraBenkarten und Routenplanung verfugbar waren, gibt es heute Programme wie Google Earth, die eine interaktive Ansicht der Erde dar- stellen und dem Benutzer die Moglichkeit geben, beliebige Ebenen wie z. B. Geschafte, Restaurants, Tankstellen und andere sogenannte Points of Interest (kurz POI) einzu- blenden [GoogleEarth].

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Google Earth - Ansicht der Nurnberger Altstadt mit POIs

Das Problem bei solchen Diensten, wie hier am Beispiel Google, besteht darin, dass die Karten und Daten nur kommerziell nutzbar sind und somit nicht fur neue Anwen- dungen zur Verfugung stehen [GoogleTerms]. Eine freie Alternative ist erforderlich.

1.1 OpenStreetMap

Die OpenStreetMap ist eine freie Geo-Datenbank, die im August 2004 von Steve Coast initiiert wurde [OsmFacts]. Der Open-Source-Gedanke tragt dazu bei, dass das Pro- jekt sehr schnell viele Mitglieder und Helfer gefunden hat. Zu Beginn des Jahres 2008 waren 20.000 Mitglieder registriert, zu Beginn von 2009 bereits uber 80.000. Aktuell, zu Beginn von 2010, sind es mehr als 200.000 [OsmStats].

OpenStreetMap eignet sich auf Grund der liberalen Lizenzbedingungen fur den wis- senschaftlichen Einsatz. Die Creative Commons Attribution-Share-Alike-2.0-Lizenz [CCSA] erlaubt die kostenlose Nutzung der Daten, solange kenntlich gemacht wird, woher die Daten stammen, d. h. OpenStreetMap explizit genannt wird, und unter wel- cher Lizenz sie stehen.

1.1.1 Datenformat von OpenStreetMap

Daten von der OpenStreetMap werden in Form des sogenannten Planet-File auf http://planet.openstreetmap.org/ zur Verfugung gestellt. Dies ist eine bzip2-kompri- mierte XML-Datei [XML] mit allen Geo-Daten der Erde. Im Juni 2009 umfasste das Planet-File uber 160 GiB, dass mittels bzip2 auf 6,1 GiB reduziert wurde [OsmPla- net]. Am 31. Oktober 2009 betrug die DateigroBe der komprimierten Datei bereits 7,3 GiB [OsmPlanetDownload].

Fur kleine Rechtecke auf der Erde - wenn maximal 50.000 Elemente darin enthalten sind - kann mittels einer API auch nur ein Ausschnitt abgerufen werden [OsmApi]. Dieses Verfahren eignet sich allerdings nur bedingt, da mit zunehmender Datenmen- ge v. a. in den GroBstadten das Rechteck immer kleiner sein muss, um keine Fehler- meldung auszulosen.

Die geographischen Informationen werden in drei primitiven Datentypen erfasst, die auf je ein XML-Element abgebildet sind [OSM]. Jedes XML-Element enthalt in den Attributen eine - jeweils fur den Datentypen - eindeutige ID, sowie Informationen wer wann zuletzt eine Anderung durchgefuhrt hat.

Es gibt die folgenden Primitiven (in der Arbeit nachfolgend Elemente oder Elementtypen genannt):

- Ein Knoten (Node) entspricht einem Punkt auf der Erde. Er enthalt auBer sei­ner - fur alle Knoten - eindeutigen ID ein Koordinatenpaar aus geographischer Lange (Longitude) und geographischer Breite (Latitude).
- Ein Weg (Way) ist ein gerichteter Streckenzug aus Knoten. Mittels der IDs der Knoten (Nds) werden Strecken gebildet, die z. B. StraBen, Bahnlinien und Flus- se darstellen [OSM].

Stimmen die IDs des ersten und letzten Streckenpunktes uberein, so wird eine Flache (Area) aufgespannt. Damit werden z. B. Gebaude, Wald- oder Agrarfla- chen und Grenzlinien modelliert [OSM].

- Eine Relation (auch Beziehung) kann zwischen mehreren Knoten, Wegen oder auch anderen Relationen bestehen. Die an der Relation teilnehmenden Elemen­te werden Mitglieder (Members) genannt. Jedem Mitglied wird eine Rolle (Role) zugeordnet, die es in der Relation spielt. Z. B. werden die Haltestellen und Rou- tenverlauf einer Buslinie zusammengefasst oder mehrere Flachen zu komple- xen Polygonen zusammengeschlossen.

Fur alle drei Elemente konnen zusatzlich Tags angegeben werden. Dies sind Paare aus Name (Key) und Wert (Value), die fur zusatzliche Informationen genutzt werden. Es gibt zwar im Wiki der OpenStreetMap eine Auflistung von Tags, die benutzt wer­den sollten [OsmFeatures], grundsatzlich sind aber keine Einschrankungen gesetzt, fur welche Informationen Tags eingesetzt werden konnen.

Im Folgenden werden Tags kurz in der Form Name=Wert geschrieben.

1.1.2 Beispiele von XML-Daten

Um sich ein Bild machen zu konnen, hier einige Beispiele:

Abbildung in dieser Leseprobe nicht enthalten

Dieses Tag definiert einen Knoten an der angegebenen Position 49,4317501°N, 11,0018765°O. In den Tags des Knoten sind zusatzlich die Informationen zu finden, dass sich dort eine uberdachte Bushaltestelle befindet, die von der VAG betrieben wird und dort die Linien 67 und N8 bedienen.

Abbildung in dieser Leseprobe nicht enthalten

Die ersten drei XML-Elemente legen drei Knoten fest. Hier sind keine weiteren Infor­mationen hinterlegt. Der nachfolgende Weg benutzt diese Knoten dann, um eine as- phaltierte StraBe namens Neumuhlweg zu beschreiben. Die StraBe fuhrt durch ein Wohngebiet, maximal darf mit 30 km/h gefahren werden und es ist eine Sackgasse.

Abbildung in dieser Leseprobe nicht enthalten

Hier werden vier Wege in Beziehung gesetzt. Die besagten Wege werden von der Bus- Linie 67 befahren, die von der VAG eingesetzt wird. Der Tarifverbund heiBt VGN.

1.1.3 Gerendertes Kartenmaterial

Die XML-Daten sind fur den Benutzer eher unhandlich, deshalb werden die Daten von Karten-Render-Programmen zu Bildern verarbeitet. OpenStreetMap setzt zwei ver- schiedene Programme (Osmarender und Mapnik) ein, die das Planet-File rendern und in einer Google-Maps-ahnlichen Oberflache fur den Benutzer in einem Internet-Brow­ser zuganglich machen [OsmSlippyMap].

Mittlerweile gibt es eine groBe Vielfalt von weiteren Projekten, die die OpenStreet- Map-Daten verwenden und jeweils andere Details verwenden, um Karten zu erzeu- gen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Mapnik-Karte Quelle: www.openstreetmap.org

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Osmarender-Karte Quelle: www.openstreetmap.org

Nachfolgend sind mehrere verschiedene Darstellungen der Nurnberger Innenstadt ge- zeigt:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: CycleMap-Karte Quelle: www.openstreetmap.org

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Hiking-Karte

Abbildung in dieser Leseprobe nicht enthalten

Quelle: www.openstreetmap.org

Abbildung 6: ÖPNV-Karte Quelle: www.öpnvkarte.de

Abbildung 7: Reit- und Wanderkarte Quelle: topo.geofabrik.de

Wie zu sehen ist, k5nnen die Karten komplett unterschiedlich aussehen, je nachdem, welche Elemente dargestellt werden und welche nicht.

1.2 Ziel dieser Arbeit

Das XML-Format [XML] ist unn5tig aufgeblaht, wie aus den Beispielen ersichtlich ist. Leerzeichen und Zeilenumbruche sind nicht notwendig. Auch Attribute, welcher User wann zuletzt eine Anderung vorgenommen hat, ist fur die meisten Anwendungen nicht von Relevanz.

Im Rahmen dieser Arbeit soll ein Binarformat entwickelt werden, um Bandbreite bei der Ubermittlung der Geo-Informationen einzusparen. Das Format soll speziell fur das am Lehrstuhl entwickelte ROSE-Projekt [Rose] optimiert werden. AnschlieBend soll die Effizienz des neuen Formats analysiert werden.

Es soll ein ROSE-Server-Dienst implementiert werden, der XML-Daten von Open- StreetMap mittels der API abruft und in das neu entwickelte Format umwandelt. Ein geeignetes Protokoll wird dem Server die gewunschten Koordinaten mitteilen und wel­che Informationen der Client zusatzlich ben5tigt.

Im Rahmen der FuBgangernavigation [RoseTransport] liegt das Interesse besonders auf POIs wie Telefonzellen, Gebaude, Ausflugsziele, Postamter, Briefkasten, um nur ein paar Beispiele zu nennen.

Zum Schluss soll der ROSE-Client dahingehend erweitert werden, dass er die aktuel- len GPS-Koordinaten des Mobilgerats an den neuen Dienst auf dem Server sendet und eine dynamische Karte auf dem Display rendert.

2 Vorbereitende Analyse-Skripte

Das in dieser Arbeit zu entwickelnde Binarformat wird sich vom Grundaufbau stark an dem Entwurf, der im OpenStreetMap-Wiki zu finden ist [OsmBinaryFormat], ori- entieren. Dieses wird verbessert und die Zuordnung der OpenStreetMap-Tags auf Bi- nardaten gezielt darauf optimiert, dass Informationen uber StraBen oder fur FuBgan- ger relevante POIs weniger Speicher benotigen als andere Informationen.

Um das zu entwickelnde Format optimal zu gestalten, werden vorab einige statisti- sche Betrachtungen gemacht.

Da das Planet-File fur diesen Zweck zu groB ist und die Laufzeit fur die eingesetzten Skripts zu lang ist, werden nur kleinere Teile des Planeten (Kontinente, Staaten oder Bundeslander) untersucht. GEOFABRIK bietet derartige Bruchteile des groBen Plan­et-Files zum Download an [GeoFabrik]. Im Folgenden wird auf diese Daten Bezug ge- nommen.

2.1 Zeilenweise Analyse

Mittels des PHP-Skripts analyse.php wurden Datensatze unterschiedlicher GroBe statistisch ausgewertet. Es wurden Datensatze von Bayern, Deutschland und Europa verwendet.

analyse.php liest zeilenweise eine .osm-Datei ein und sammelt in einem assoziativen Array alle fur diese Arbeit relevanten Fakten. Die OpenStreetMap-Dateien sind viele Gigabytes groB, weswegen SimpleXML leider nicht zum Einsatz kommen kann, da hier die komplette Eingabedatei in den Arbeitsspeicher passen musste [PHP]. Es wur- de deshalb eine Losung mittels regularer Ausdrucke (RegExp) entwickelt.

Als Ausgabedateien legt analyse.php zwei Dateien an:

- result.txt — Das assoziative Array wird dort mittels print_r() hineinge- schrieben
- result_serialized.txt — Das assoziative Array wird mittels PHP serialisiert und in diese Datei gespeichert. Dies hat den Zweck, dass das Ergebnisarray per Skript wieder in Array-Form hergestellt und weiterverarbeitet werden kann.

Es wird davon ausgegangen, dass die Daten von Europa reprasentativ sind und fur die anderen Erdregionen ahnliche Ergebnisse liefern wurde. Von einer aufwandigen Ana­lyse des uber 160 GiB groBen Planet-Files wird deshalb abgesehen.

2.1.1 Stringlange in den Tag-Values

Es ist wichtig zu wissen, welche Lange Strings in den OpenStreetMap-Tags aufwei- sen. Das Analyse-Skript hat hierbei untersucht, wie viele Strings bestimmte Langen uberschreiten. Besonders interessant: Wie viele Strings passen in 27 bzw. 28 Bytes? Wie viele Strings benotigen mehr als 28 Bytes Speicher? Grund fur diese Uberlegung ist es, herauszufinden, ob die Stringlange in einem oder in zwei Bytes kodiert werden muss.

In Tabelle 1 sind die Ergebnisse fur die Stringlangen der Tag-Values aufgelistet: Mehr als 99,5% aller Value-Strings der Tags sind kurzer als 64 Zeichen. Der Anteil an Tags mit einer Value-Stringlange von mehr 128 liegt bei weniger als 0,001%.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Stringlange in den Tag-Values

Neben der Stringlangen aller Tags wurden zusatzlich noch die durchschnittlichen Stringlangen nur bestimmter Tags untersucht. Diese Tags sind

- name
- Tags, die auf _name enden
- Tags, die mit addr: beginnen

Von diesen Tags war eventuell zu erwarten, dass die Value-Strings langer als andere sind. Es wurden aber keine auffalligen Anomalien in den Stringlangen der Values ge- funden, sodass die Ergebnisse fur diese Arbeit nicht von Belang sind.

2.1.2 Anzahl Tags, Members und Nds pro Element

Elemente haben bestimmte Unterelemente:

- Knoten, Wege und Relationen konnen ein oder mehrere Tags enthalten.
- Wege enthalten eine Liste von mehreren Knoten-IDs.
- Relationen enthalten eine Liste von mehreren Mitgliedern.

Fur die Kodierung aller Elemente wird spater erst ubertragen, wie viele Unterelemen­te folgen.

Das Analyse-Skript zahlt wahrend der zeilenweisen Bearbeitung der XML-Datei mit, indem mit Offnen eines <node>-, <way>- oder <relation>-Tags der Tag-Name gespei- chert wird und die Zahler auf 0 gesetzt werden. Bei <tag>-, <nd>- oder <member>-Tags werden die Zahler inkrementiert. Bei den schlieBenden </node>-, </way>- oder </relation>-Tags wird dann die Anzahl der Unterelemente, sowie Durchschnitts-,

Maximal- und Minimalwerte, erfasst. Wie bei den Stringlangen ist das Augenmerk wieder auf den Bit-Grenzen.

Anders als bei den Stringlangen werden fur die Tag-Anzahl zwei Werte reserviert. Es ist einerseits moglich, dass ein Element keine Tags enthalt. Andererseits wird ein Wert dafur verwendet, um anzuzeigen, dass viel mehr Tags vorliegen und die Anzahl extra kodiert werden muss. Es werden daher die Grenzen 6 (23-2), 14 (24-2) und 30 (25­2) verwendet.

Die Ergebnisse fur die Tag-Anzahl sind in Tabelle 2 zu finden:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Tags pro Element in europe.osm

Fur die Anzahl von Knoten pro Weg werden die Grenzen 127 und 255 untersucht, was 7 oder 8 Bits entspricht. Zwar sollte ein Weg immer aus mindestens 2 Knoten beste- hen, doch die Analyse hat gezeigt, dass es auch Wege mit nur einem Knoten gab. Vor- sichtshalber werden deshalb Werte fur 0 Knoten und 1 Knoten freigehalten.

Die Ergebnisse fur die Knoten-Anzahl pro Weg sind in Tabelle 3 zu linden:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3: Knoten pro Weg in europe.osm

Fur die Anzahl von Mitgliedern pro Relation werden analog zu den Knoten pro Weg die Grenzen 127 und 255 untersucht.

Die Ergebnisse fur die Mitglieder-Anzahl sind in Tabelle 4 zu linden:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4: Mitglieder pro Relation in europe.osm

2.1.3 Relationen: Typen und Rollen

Die meisten Relationen haben mittels eines Tags einen Typ zugeordnet, jedes Mitglied hat eine Rolle. Um spater eine effiziente Zuordnung realisieren zu konnen, wird ana- lysiert, welche Werte am haufigsten auftreten.

Fur den Typ einer Relation wird abgefangen, wenn in einem <relation>-Element ein Tag mit dem Namen type auftritt und der Wert gespeichert. Fur die Rolle eines Mit- glieds wird das XML-Attribut role analysiert und gezahlt.

Die Ergebnisse dieser Analysen sind in den Tabellen 5 und 6 zu finden:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 5: Haufigst vorkommende Typen von Relationen

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 6: Haufigst vorkommende Rollen in Relationen

2.2 Analyse der Tags

analyse.php erzeugt eine Auflistung der gebrauchlichsten Tags. Es wurde eine Liste in Anlehnung an die dokumentierten Tags aus dem OpenStreetMap-Wiki [OsmFeatu- res] erstellt und nach Key-String gruppiert die gefundenen Values gezahlt.

Viele Tags haben zu bestimmten Key-Strings eine Auswahl an festen Value-Strings. Im Rahmen der Skript-Auswertung wurden von allen Tags, die in Europa verwendet wurden, die (Key, Value)-Paare gezahlt und absteigend sortiert.

Um die Auftrittshaufigkeiten aller Tags miteinander vergleichen zu konnen, liest das PHP-Skript tags2csv.php die serialisierte Ausgabe von analyse.php ein, verwirft die Gruppierung und gibt Key, Value und Anzahl der Vorkommen dieses Tags durch einen Delimiter getrennt in eine Textdatei.

Diese CSV-Datei kann dann mittels Tabellenkalkulationsprogrammen weiter ausge- wertet werden.

Tabelle 7 zeigt die haufigsten (Key, Value)-Kombinationen der in Europa verwendeten Tags.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 7: Haufigst vorkommende (Key, Value)-Kombinationen bei Tags

Es ist wunschenswert, haufig vorkommende Kombinationen mit wenigen Bits zu ko- dieren, wahrend im Gegensatz dazu bei seltenen Kombinationen der Speicherbedarf groBer sein kann.

2.3 Eintragung in eine MySQL-Datenbank

Im Hinblick auf die Kodierung von Wegen ist es interessant zu wissen, wie groB die Differenz der beiden geographischen Koordinaten (im folgenden Koordinaten-Abstand genannt) zweier Knoten in einem Weg ist.

Problem hierbei ist, dass die Knoten im Weg nur mittels ihrer ID referenziert werden. Um die geographischen Koordinaten der Punkte zu erhalten, mussen alle Knoten im Speicher gehalten werden, was angesichts der DateigroBen nicht moglich ist.

2.3.1 MySQL-Datenbankschema

Es wurde deshalb eine MySQL-Datenbank zu Hilfe genommen und ein Datenbank- schema entwickelt, welches OpenStreetMap-Daten ohne Verlust speichern kann.

Knoten, Wege und Relationen werden in separate Datenbank-Relationen gespeichert. Ihre ID wird als Primarschlussel verwendet.

Abbildung in dieser Leseprobe nicht enthalten

Tags fur alle drei Elementtypen werden zusammen in eine Relation gespeichert. Das Attribut type bestimmt, welcher Typ von Element vorliegt, da die ID nicht uber alle drei Elementtypen eindeutig ist.

Es wurde ein Index auf Typ und ID gesetzt, um schnell bestimmte Tags zu einem Ele­ment lesen zu konnen.

Abbildung in dieser Leseprobe nicht enthalten

Fur die Wege gibt es eine Relation way_nodes, die die Zuordnung der <nd>-Elemente ubernimmt. Ein zusatzliches Attribut sorting sorgt dafur, dass die Reihenfolge, die fur einen Streckenzug unabdingbar ist, erhalten bleibt, indem sorting pro Knoten in einem Weg um eins inkrementiert wird.

Es wurde ein Index fur (way_id, ref) gesetzt, der spater gleich doppelt zum Einsatz kommen kann [MySQLIndex]:

- MySQL optimiert den Zugriff, wenn beide Schlusselattribute AND-verknupft in einer WHERE-Klausel verwendet werden.
- Zusatzlich wird fur einen Zugriff auf den ersten Teil des Schlussels, der ID des Weges, optimiert, der schnelles Lesen eines Weges mit einer bestimmten ID er- laubt.

Abbildung in dieser Leseprobe nicht enthalten

Fur die Mitglieder einer Relation gibt es die Datenbank-Relation relation_members, die zusatzlich zu Typ und ID des Mitglieds ein Attribut role enthalt, um die Rolle, die das Mitglied in der Relation spielt, speichert.

Abbildung in dieser Leseprobe nicht enthalten

2.3.2 Einsatz des Skripts

Das PHP-Skript osm2sql.php erzeugt aus einer angegebenen OpenStreetMap-Datei die SQL-Statements, um das in Kapitel 2.3.1 erklarte Datenbankschema anzulegen und die Daten anschlieBend dort einzufugen.

Wird statt einer Ausgabedatei das Schlusselwort STDOUT verwendet, so werden die SQL-Statements auf der Konsole ausgegeben. Dies kann dazu verwendet werden, um mittels einer Pipe die Ausgabe direkt in die Datenbank zu leiten.

Ein Beispiel:

sia1muen@kubuntu:~/osm$ php osm2sq1.php bayern.osm STDOUT | mysql -u root --password=root osm_bayern osm2sql.php erzeugt aus bayern.osm die notigen SQL-Statements und schickt sie an den MySQL-Befehlszeileninterpreter, der die Anweisungen in der Datenbank osm_bayern ausfuhrt. Nach Abschluss dieser Befehlszeile befinden sich alle Daten aus der OpenStreetMap-Datei in der Datenbank und konnen analysiert werden.

2.4 Analyse aus der Datenbank

Zur Analyse wird das PHP-Skript dbanalyse.php verwendet. Es richtet sein Augen- merk ausschlieBlich auf die Wege und die Koordinaten-Abstande der Knoten, aus de- nen die Wege bestehen.

Vor der Analyse wurden mehrere Moglichkeiten in Betracht gezogen, wie die konkrete Kodierung der Wege in der fertigen Anwendung aussehen konnte. Unabdingbar ist es, nicht jede Koordinate einzeln zu senden, da ein Koordinatenpaar zweimal 4 Bytes, also gesamt 8 Bytes pro Knoten auf dem Weg belegt. Dieser Speicherbedarf muss ver- mindert werden.

2.4.1 Relative Kodierung gemaB OpenStreetMap-Wiki

Die Idee aus dem OpenStreetMap-Wiki ist es, nur die Koordinaten des ersten Knotens vollstandig zu ubertragen, danach nur den relativen Abstand zum Nachfolgeknoten zu senden [OsmBinaryFormat].

Ein Mangel an dieser Umsetzung ist, wenn ein Weg viele Knoten enthalt, die groBe Abstande zwischeneinander haben, so mussen sogenannte Dummy-Knoten (fake nodes) eingefugt werden. Bei der Berechnung dieser Dummy-Knoten kommt es zusatz- lich zu rundungsbedingten Knicken auf dem Weg, wie ein Beispiel spater zeigen wird.

Das vorgeschlagene Format arbeitet nur mit einer Genauigkeit von 6 Nachkommastel- len auf den geographischen Koordinaten, weswegen Dummy-Knoten erst bei einem Koordinaten-Abstand von mehr als 0,032767° eingefugt werden mussen.

Im Rahmen dieser Arbeit wird angestrebt, eine vollstandige Abbildung (mit Ausnah- me von Versionen und Userdaten) der OpenStreetMap-Daten zu erreichen. Deswegen ware es auch wunschenswert, alle 7 zur Verfugung gestellten Nachkommastellen auf den Koordinaten zu erhalten und im Binarformat zu kodieren.

2.4.2 Alternative Kodierung mittels Flex-Byte

Werden alle 7 Nachkommastellen verwendet, so treten Dummy-Knoten zehnmal haufiger auf, da die Differenz zwischen zwei Koordinaten nur noch 0,0032767° betra- gen darf, ohne dass Dummy-Knoten erforderlich werden.

Als Alternativ-Idee wurde sich ein sogenanntes Flex-Byte uberlegt. Es handelt sich hierbei um ein Byte, welches alle 4 Knoten wiederholt wird und das angibt, ob eine Koordinate relativ (d. h. der Abstand zur vorhergehenden Koordinate mit 16 Bits) oder absolut (als vollstandiger Integer mit 32 Bits) kodiert wird.

Vorteil dieser Variante ist, dass fur den Fall, dass zwei Koordinaten einen sehr groBen Koordinaten-Abstand haben, mittels eines Bits angegeben werden kann, dass die Ko­ordinate absolut kodiert wird. Samtliche Dummy-Knoten entfallen in diesem Fall. Es treten keine rundungsbedingten Verfalschungen an den Koordinaten auf.

Nachteil besteht daran, dass unabhangig davon, ob relative Koordinaten oder absolute Koordinaten gunstiger sind, immer pro 4 Knoten ein zusatzliches Byte fur das Flex- Byte spendiert werden muss. Ist die Anzahl der Knoten abzuglich 1 nicht ganzzahlig durch 4 teilbar, so wird zusatzlich Speicher verschwendet, da die restlichen Bits im Flex-Byte dann ohne Bedeutung sind.

2.4.3 Gegenuberstellung der Moglichkeiten am Beispiel

Um beide Moglichkeiten besser darzustellen, wird im Folgenden ein Beispiel vorge- stellt. Angenommen, ein Weg bestunde aus den Knoten

- (42,3455323° ; 54,5432345°)
- (42,3455413° ; 54,5431496°)
- (42,3495890° ; 54,5430994°)
- (42,3460162° ; 54,5385961°)
- (42,3460253° ; 54,5386512°)

Fur beide Varianten wird versucht, alle 7 Dezimalstellen zu erhalten. Die Koordina- ten werden deshalb mit 10.000.000 multipliziert.

- (423.455.323 ; 545.432.345)
- (423.455.413 ; 545.431.496)
- (423.495.890 ; 545.430.994)
- (423.460.162 ; 545.385.961)
- (423.460.253 ; 545.386.512)

Zuerst das Verfahren, welches Dummy-Knoten benutzt. Hierbei ist die Differenz zur vorherigen Koordinate entscheidend.

- (423.455.323 ; 545.432.345)
- ( +90 ; -849)
- ( +40.477 ; -502)
- ( -35.728 ; -45.033)
- ( +91 ; +551)

Hervorgehoben sind die Differenzen, die groBer als 32.767 oder kleiner als -32.768 sind. An diesen Stellen mussen Dummy-Knoten eingefugt werden, um die Abstande in 16 Bits zu kodieren. AuBerdem mussen Koordinaten angepasst werden, sodass die Dummy-Knoten auf dem Pfad sitzen (durch Fettdruck hervorgehoben).

- (423.455.323 ; 545.432.345)
- ( +90 ; -849)
- ( +32.767 ; -406)
- ( +7.710 ; -96)
- ( -25.997 ; -32.768)
- ( -9.731 ; -12.265)
- ( +91 ; +551)

Abbildung in dieser Leseprobe nicht enthalten

Um den Dummy-Knoten auf den Weg zu setzen, muss das Verhaltnis von Langen- zu Breiten-Koordinate bestimmt werden. Durch die Rundung auf eine Ganzzahl entste- hen pro Dummy-Knoten minimale Knicke auf dem Weg. Dies wird deutlich, wenn man die Verhaltnisse vergleicht (hier am Beispiel des ersten Dummy-Knotens).

Es ergeben sich fur das Verfahren aus Kapitel 2.4.1 ein Gesamtspeicherbedarf von 2x 8 Bytes (erster Knoten), 4x 4 Bytes (regulare Knoten), 2x 4 Bytes (zusatzliche Dummy- Knoten), d. h. gesamt 40 Bytes.

Nun das Alternativverfahren mittels des Flex-Bytes. Statt fur die drei Koordinaten, deren Differenzen nicht in 16 Bits kodiert werden konnen, wird mittels des Flex-Bytes festgelegt, dass diese drei Koordinaten absolut kodiert werden sollen.

- (423.455.323 ; 545.432.345)
- Flex-Byte: (relativ, relativ, absolut, relativ, absolut, absolut, relativ, relativ)
- ( +90 ; -849)
- (423.495.890 ; -502)
- (423.460.162 ; 545.385.961)
- ( +91 ; +551)

Es ergeben sich fur das Verfahren aus Kapitel 2.4.2 ein Gesamtspeicherbedarf von 2x 8 Bytes (erster Knoten), 5x 2 Bytes (relative Koordinaten), 3x 4 Bytes (absolute Koor­dinaten) und einem zusatzlichen Byte (Flex-Byte), d. h. gesamt 39 Bytes.

In diesem Beispiel wurde mit dem Flex-Byte-Verfahren ein Byte Speicher eingespart. Es wird hierbei auch deutlich, dass bei diesem Verfahren absolute und relative Kodie- rung auch mitten in einem Knoten gewechselt werden konnen.

2.4.4 Ergebnisse

Ob das Flex-Verfahren wie im obigen Beispiel immer weniger Speicherbedarf hat, hat das PHP-Skript dbanalyse.php analysiert, indem alle Wege aus der Datenbank gele- sen wurden, beide Verfahren angewandt worden sind und der Speicherbedarf gezahlt wurde.

Auf Grund der groBen Datenmenge war es leider nur moglich, die Region Mittelfran- ken und das Bundesland Bayern zu analysieren. Ein groBerer Datensatz hatte zu viel Zeit benotigt, um rechtzeitig Ergebnisse zu liefern.

Tabelle 8 zeigt die Ergebnisse:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 8: Vergleich zwischen relativer Kodierung und der Flex-Byte-Kodierung

Es ist zu sehen, dass im Mittel die Flex-Byte-Losung geringfugig bessere Ergebnisse liefert, als die Variante mit den Dummy-Knoten.

Grund hierfur ist, dass bei einigen Wegen sehr groBe Abstande vorliegen und viele Dummy-Knoten eingefugt werden mussen. Das Flex-Byte-Verfahren spart an dieser Stelle Speicher ein, indem nur sehr wenige Koordinaten absolut kodiert werden und der Rest speicherplatzeffizient relativ kodiert wird.

Zudem kommt es beim Flex-Byte-Verfahren zu keiner Verfalschung der Wege, wie sie bei dem Dummy-Knoten-Verfahren auftreten wurde.

3 Entwicklung des Binarformats

3.1 Grundliegende Bausteine

Zu Beginn werden einige Grundbausteine definiert, die in der weiteren Beschreibung des Binarformats verwendet werden.

3.1.1 Bytereihenfolge von Integer-Daten

Integer, die mehr als ein Byte groB sind, werden mit Big-Endian-Bytereihenfolge ko- diert. Dies hat den Vorteil, dass die Java-Klassen java.io.DataOutputStream und j ava. io. DataInputStream verwendet werden konnen.

3.1.2 Flexibler Integer

Es werden spater mehrfach Integer benotigt werden, von welchen davon auszugehen ist, dass sie in den meisten Fallen einen Wert kleiner als 256 haben, also in ein Byte passen wurden.

Um allerdings auch Werte groBer oder gleich 256 zu erlauben, wird ein Datentyp defi- niert, der Werte von 0 bis 32.767 unterstutzt. Dieser Datentyp wird im Folgenden flexibler Integer genannt. Tabelle 9 erklart die Kodierung:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 9: Flexibler Integer

Vorteil dieser Kodierung ist es, dass flexibel zwischen der 1-Byte- und der 2-Byte-Va- riante gewechselt werden kann. So wird in den meisten Fallen der Integer mit nur ei- nem Byte ubertragen, obwohl die Moglichkeit bestunde, eine groBere Zahl zu verwen- den.

Der entsprechende Nachteil ist, dass Zahlen im Bereich zwischen 128 und 255 zwar theoretisch in einem Byte kodiert werden konnten, trotzdem aber zwei Bytes verbrau- chen.

Beim Lesen eines solchen flexiblen Integers ist das Bit 7 des ersten Bytes ausschlag- gebend, ob noch ein zweites Byte folgt. Ist Bit 7 gesetzt, muss ein weiteres Byte gele- sen werden und der Integer aus beiden Bytes zusammengesetzt werden. Ist Bit 7 nicht gesetzt, so ist der Wert des Integers kleiner als 128 und es folgt kein weiteres Byte.

Da das Bit 7 des ersten Bytes als "Folgt ein zweites Byte?"-Flag verbraucht wird, ste- hen somit nur 15 Bits gesamt zur Verfugung, was einen Wertebereich von 0 bis 32.767 aufspannt.

[...]

Ende der Leseprobe aus 94 Seiten

Details

Titel
Konzeption und Implementierung eines Binärformats zur effizienten Übertragung von OpenStreetMap-Daten auf mobile Endgeräte zur dynamischen Generierung individueller Karten
Hochschule
Friedrich-Alexander-Universität Erlangen-Nürnberg  (Department Informatik)
Note
1,3
Autor
Jahr
2010
Seiten
94
Katalognummer
V157527
ISBN (eBook)
9783640755394
ISBN (Buch)
9783640755462
Dateigröße
18463 KB
Sprache
Deutsch
Schlagworte
OpenStreetMap, Binärformat, Kodierung, OpenStreetMap-Daten, Geo-Daten, individuelle Karten, mobile Endgeräte
Arbeit zitieren
Alexander Münch (Autor:in), 2010, Konzeption und Implementierung eines Binärformats zur effizienten Übertragung von OpenStreetMap-Daten auf mobile Endgeräte zur dynamischen Generierung individueller Karten, München, GRIN Verlag, https://www.grin.com/document/157527

Kommentare

  • Noch keine Kommentare.
Blick ins Buch
Titel: Konzeption und Implementierung eines Binärformats zur effizienten Übertragung von OpenStreetMap-Daten auf mobile Endgeräte zur dynamischen Generierung individueller Karten



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden