OpenStreetMap ist ein Open-Source-Projekt mit dem Ziel, jedermann freie Geo-Informationen zur Verfügung zu stellen. Mit den Daten können beliebige Karten generiert werden, z. B. Straßenkarten, Stadtpläne, Wanderkarten, Karten mit dem Netz der öffentlichen Verkehrsmittel. In den Daten sind unter anderem POIs (Points of Interest, z. dt. interessante Orte) enthalten, was es ermöglicht, z. B. Museen, Bibliotheken, Läden und sogar Ampeln in Karten darzustellen oder in Navigationssystemen zu verarbeiten.
Im Rahmen der Studienarbeit soll eine Möglichkeit geschaffen werden, Daten von OpenStreetMap, die nativ im XML-Format geliefert werden, in ein Binärformat umzuwandeln, wodurch der Datenverkehr im Vergleich zu anderen Formaten wie XML gesenkt werden soll.
Das neue Format ist mit bereits vorhandenen Formaten zur Übertragung von Karten zu vergleichen. Besonders für mobile Geräte dürfte ein Binärformat von Vorteil sein, weil hier langsamere Übertragungsraten ein Problem darstellen.
Die Formatumwandlung soll mittels eines zusätzlichen Dienstes für den ROSE-Server geschehen, der zu einem gegebenen Rechteck auf der Erde (mittels Längen- und Breitengrad) die XML-Daten von der OpenStreetMap-API lädt, in das noch zu konzeptionierende Format umwandelt und die Binärdaten schließlich an den Client schickt.
Der ROSE-Client soll um die Funktionalität erweitert werden, die Binärdaten um die aktuelle GPS-Position des Mobilgeräts vom Server mittels eines geeigneten Protokolls abzufragen, um dynamisch eine Karte auf dem Mobilgerät zu generieren.
OpenStreetMap stellt zwar vorgerenderte Karten in Form von PNG-Grafiken zur Verfügung, diese haben allerdings feste Detaileinstellungen, was dem Nutzer nicht ermöglicht, zu wählen, welche Informationen er angezeigt haben möchte und welche nicht.
Das Protokoll zwischen Server und Client soll entsprechend ausgerüstet werden, sodass nur vom Nutzer ausgewählte Kartenfeatures (z. B. Fußwege, Bushaltestellen, Einkaufsmöglichkeiten, Abfalleimer, Telefonzellen) vom Server bezogen und schlussendlich auch auf dem Display angezeigt werden.
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 seiner - 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 Elemente 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 werden 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 Informationen 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-Browser 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 welche 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 Planet-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 Analyse 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 Unterelemente 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 (252) 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 Element 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 Koordinate 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 Koordinaten) 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.
[...]
- Quote paper
- Alexander Münch (Author), 2010, Konzeption und Implementierung eines Binärformats zur effizienten Übertragung von OpenStreetMap-Daten auf mobile Endgeräte zur dynamischen Generierung individueller Karten, Munich, GRIN Verlag, https://www.grin.com/document/157527
-
-
-
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X.