DE10221774A1

DE10221774A1 - Verfahren zum Komprimieren und Dekomprimieren von Daten eines Datenstromes

Info

Publication number: DE10221774A1
Application number: DE10221774A
Authority: DE
Inventors: Arne Friedrichs; Gerd Draeger; Stefan Goss
Original assignee: Robert Bosch GmbH
Current assignee: Robert Bosch GmbH
Priority date: 2002-05-15
Filing date: 2002-05-15
Publication date: 2003-11-27
Also published as: WO2003098151A1; JP2005525763A; EP1514077A1

Abstract

Bei einem Verfahren zum Komprimieren bzw. Dekomprimieren von Daten unterschiedlichen Informationsgehalts, z. B. topografischen Knoten und Kanten sowie deren Attribute, wird der Komprimierungsgrad in Abhängigkeit des Informationsgehaltes konfigurierbar ausgebildet. DOLLAR A Zur Komprimierung werden Attribute weggelassen, die Genauigkeit der topografischen Information begrenzt oder anhand einer vorgegebenen maximalen Datenmenge der Komprimierungsgrad gesteuert.

Description

Stand der Technik

Die Erfindung geht aus von einem Verfahren zum Komprimieren von Daten eines Datenstromes.
In der DE 101 06 502.7 wird ein Verfahren zum Übertragen von Routendaten beschrieben. Die Routendaten umfassen Knoten in Form von Wegepunktdaten mit dazwischen liegenden Kanten (Wegen) sowie zugehörige Attribute. Die einzelnen Wegepunkte eines Routenkorridors sind so miteinander verknüpft, dass ein möglichst geringes Datenvolumen erzeugt wird. Vorzugsweise werden die Wegepunktdaten sequentiell übertragen.
In der DE 101 05 897.7 ist ein Verfahren zum Austausch von Navigationsdaten zwischen einem Endgerät und einer Zentrale beschrieben mit einer Segmentierung und einer Übertragung von Teilrouten zwischen einem Start- und Zielpunkt. Offboard- Navigationsgeräte nach diesem Verfahren berechnen Routeninformationen nicht autark, sondern fragen diese über eine geeignete (Funk)-Schnittstelle von einem Server an, der sie dann zum Navigationsgerät überträgt.
Aus der DE 100 12 441 C2 ist ein Verfahren zur Zieleingabe an einem Navigationsgerät bekannt. Zur Reduzierung des Verarbeitungsaufwandes werden dort nur solche Zielnamen aufgenommen, die im Umkreis des aktuellen Standortes liegen. Außerdem werden in einer Zielnamenliste die Ziele nach der Entfernung sortiert.

Vorteile der Erfindung

Beim Verfahren nach der Erfindung werden Daten eines Datenstromes unterschiedlichen Informationsgehaltes, insbesondere Routendaten die aus topografischen Knoten (Wegepunkten) und Kanten (Verbindungswegen) sowie deren Attributen (Straßennamen, Straßenklassen, usw.) bestehen, komprimiert, wobei der Komprimierungsgrad in Abhängigkeit des Informationsgehaltes der Daten konfigurierbar ausgebildet ist und wobei die Komprimierung dadurch erfolgt, dass vorgegebene Attribute weggelassen werden, die Genauigkeit begrenzt wird, z. B. hinsichtlich der Koordinatengenauigkeit, oder eine maximale Datenmenge vorgegeben wird mit entsprechender Steuerung des Komprimierungsgrades.
Im Gegensatz zu bekannten Komprimierungsverfahren, bei denen Daten ungeachtet ihrer Bedeutung bzw. ihres Informationsgehaltes komprimiert werden, werden bei der Erfindung die Daten interpretiert und durch Kenntnis ihrer Bedeutung insbesondere redundante Elemente eliminiert.
Optionale Datenfelder, beispielsweise in einem vorgegebenen Datenformat zur Übertragung von Routeninformationen gemäß der DE 101 06 502.7, können optimal genutzt werden.
Das Verfahren nach der Erfindung eignet sich vorteilhaft für die Komprimierung von Routendaten, kann aber auf allen möglichen Daten angewandt werden, vorzugsweise auf Daten, die in ihrer Struktur aus Graphen bestehen, also aus Polygonzügen mit topografischen Knoten und Kanten, z. B. Kartendaten, CAD-Zeichnungen.
Das erfindungsgemäße Verfahren zur Komprimierung wird insbesondere für Offboard- Navigationssysteme vorzugsweise auf einem Server bei einem Diensteanbieter eingesetzt, das Dekomprimieren bzw. Entschlüsseln der Daten vorzugsweise auf der Endgeräte-Seite bzw. beim Client.
In den Unteransprüchen sind vorteilhafte Weiterbildungen des erfindungsgemäßen Verfahrens zum Komprimieren bzw. zum Dekomprimieren aufgezeigt. Weitere Vorteile des Verfahrens sind insbesondere in folgenden Punkten zu sehen:

1. Die Größenreduktion der verarbeiteten Daten, wodurch Übertragungsmedien mit geringen Datenraten gut genutzt werden können.
2. Die geringe Komplexität des Komprimierungs- bzw. Dekomprimierungsalgorithmus, so dass sich dieses Verfahren z. B. auch für prozessorschwache Endgeräte mit wenig Arbeitsspeicher eignet.
3. Das Komprimierungsverfahren kann streng sequentiell ausgestaltet sein, das heißt bereits während der Komprimierung können Teildatensätze gespeichert bzw. übertragen werden.
4. Bei einem sequentiellen Aufbau der komprimierten Daten wird eine Dekomprimierung bereits auf Teildatensätzen noch während der Übertragung ermöglicht.
5. Da nicht wie bei vielen anderen Komprimierungsverfahren eine komplette Tabelle mit häufig vorkommenden Datenelementen am Anfang oder am Ende der Daten stehen muss, sondern die einzelnen Elemente an der Stelle eingefügt sind, wo sie erstmalig benötigt werden, ist zu jedem Zeitpunkt der Übertragung eine maximale Anzahl Datenelemente verfügbar.

Zeichnungen

Anhand der Zeichnungen werden Ausführungsbeispiele der Erfindung erläutert. Es zeigen
Fig. 1 eine sequentielle Abarbeitung eines Routengraphen,
Fig. 2 ein Blockschaltbild eines Komprimierungsprozesses unter Nutzung eines Assoziativspeichers,
Fig. 3 die Komprimierung eines Attributwertes,
Fig. 4 ein Beispiel für eine Routengraphen.

Beschreibung von Ausführungsbeispielen

Das Verfahren nach der Erfindung geht davon aus, dass topografische Routen- bzw. Kartendaten aus Wegepunkten (Knoten) und Straßenzügen (Kanten) bestehen, die als gerichtete Verbindungen zwischen den Knoten erzeugt wurden. Weiterhin unterliegen die Knoten und damit die Kanten einer Reihenfolge, die bei Routendaten vorteilhafter Weise vom Startpunkt in Richtung Ziel besteht.
Wegepunkte besitzen im allgemeinen ein oder mehrer der folgenden Attribute:

- Koordinaten
- Eindeutige Kennung (ID)

Kanten besitzen im allgemeinen ein oder mehrere der folgenden Attribute:

- Straßenname
- Straßenklasse
- Zielführungsanweisung (grafisch und/oder akustisch)
- Zielknoten (Verweis auf Wegpunkt)
- Fahrdauer
- Weglänge
- Eindeutige Kennung (ID)

In dem verwendeten Datenformat wird für geeignete dieser Attribute das heißt diejenigen, die optional übertragen werden, z. B. IDs bzw. diejenigen, die eine große Redundanz aufweisen, z. B. Straßennamen und Zielführungsanweisungen jeweils ein Indikator definiert, der zwei oder mehrere der folgenden Werte annehmen kann:

- Datenelement ist nicht vorhanden (bzw. gleich Default-Wert) (N.V.)
- Datenelement ist gleich dem des Vorgängers (Vorgänger)
- Datenelement ist gleich dem des x-ten Elements → Index x folgt (Index)
- Datenwert des Elementes folgt (Explizit).

Vorteilhafter Weise werden die Indikatoren für je einen zu übertragenden Wegpunkt/eine zu übertragende Kante zu einem Bitfeld zusammengefasst.
Der Komprimierungsalgorithmus geht nun sequentiell und insbesondere iterativ alle vorhandenen Wegepunkte durch, vgl. Fig. 1:

1. Übertragen der Punktattribute eines aktuellen Punktes (Ablaufpunkt 3) nach dem Start 1 und der Zuordnung 2 (aktueller Punkt gleich erster Wegepunkt)
2. Merken des aktuellen Punktes als Vorgängerpunkt (Ablaufpunkt 4)
3. Iterativ über alle vom aktuellen Punkt ausgehenden Kanten, vorzugsweise beginnend bei der Hauptroute (Ablaufpunkt 5)
- 1. Übertragen der Kantenattribute der aktuellen Kante (Ablaufpunkt 6)
- 2. Merken der aktuellen Kanten der als Vorgängerkante (Ablaufpunkt 7)
4. Vorzugsweise Merken der ersten vom aktuellen Punkt ausgehenden Kante (Hauptroute) als Vorgängerkante (Ablaufpunkt 9).

Beim Ablaufpunkt 8 wird untersucht, ob der aktuelle Punkt weitere Kanten hat. Falls ja, wird als aktuelle Kante die nächste Kante des aktuellen Punktes gewählt und das Verfahren bei Ablaufpunkt 6 fortgesetzt.
Beim Ablaufpunkt 10 wird überprüft, ob weitere Punkte vorhanden sind. Ist dies nicht der Fall, wird der Ablauf beendet. Andernfalls wird der nächste Punkt als aktueller Punkt definiert und der Ablauf bei Ablaufpunkt 3 erneut fortgesetzt.
Die eigentliche Komprimierung geschieht bei der Übertragung der Attribute. Hierzu verfügt der Komprimierungsalgorithmus für jedes Attribut, für das ein Indikator definiert ist, der den Wert Index annehmen kann über einen Assoziativspeicher 27 (Fig. 2). Der Algorithmus weist jedem Attributwert die Nummer des Elements (Punkt/Kante) zu, bei dem dieser Wert zuerst vorkommt. Also z. B. "Robert-Bosch-Straße" → 5 was bedeutet, dass der Straßenname "Robert-Bosch-Straße" an der 5. Kante zuerst vorgekommen ist. Der Attributivspeicher 27 wird als Zwischenspeicher genutzt, während der Komprimierung angelegt und hinterher wieder gelöscht. Alternativ kann den Attributwerten auch die Elementnummer im Speicher zugeordnet werden, also z. B. 3, wenn der entsprechende Attributwert als drittes in den Speicher eingefügt wurde. Der Komprimierungsprozess 28 ist direkt mit dem Assoziativspeicher 27 verknüpft. Die Eingangsdaten sind die unkomprimierten Routendaten und die Ausgangsdaten die komprimierten Routendaten 30.
Bevor die eigentlichen Punkt-/Kantenattributwerte in den komprimierten Datenbereich übertragen werden, wird für jedes Element der Indikator bestimmt, um dann anstatt des Wertes gegebenenfalls nur noch einen Verweis auf das Vorgängerelement oder einen Verweis auf ein beliebiges anderes Element zu übertragen.
Den detaillierten Ablauf für jedes einzelne Attribut eines Wegepunktes/einer Kante beschreibt Fig. 3. Gemäß Fig. 3 wird zuerst geprüft, ob ein Indikator für ein Attribut definiert ist (Ablaufpunkt 12). Falls ja, wird überprüft, ob der Attributwert gefüllt bzw. gültig ist (Ablaufpunkt 13). Wenn nicht, wird ein Indikator als N.V. definiert, das heißt der Attributwert bleibt leer (Ablaufpunkt 14). Andernfalls wird geprüft, ob der aktuelle Attributwert gleich dem des Vorgängerelements ist (Ablaufpunkt 15). Ist dies der Fall, wird der Attributwert dieses Elements gleich dem Vorgängerelements definiert (Ablaufpunkt 16). Ansonsten wird geprüft, ob ein "Index" als zulässiger Wert für einen aktuellen Indikator vorgesehen ist (Ablaufpunkt 17). Ist dies der Fall, wird geprüft, ob der entsprechende Attributwert im Assoziativspeicher vorhanden ist (Ablaufpunkt 18). Im positiven Fall wird zum Indikator ein Index definiert (Ablaufpunkt 19). Im negativen Fall wird der Attributwert bzw. seine Elementnummer gespeichert (Ablaufpunkt 20). Der Indikator wird als "Explizit" definiert, das heißt unkomprimiert verarbeitet (Ablaufpunkt 21). Anschließend werden die Indikatoren für die drei Fälle nach den Ablaufpunkten 21, 19 und 14 in den Speicher geschrieben (Ablaufpunkte 22, 23 und 24) und nachfolgend der Attributwert geschrieben (Ablaufpunkt 25) bzw. die Elementnummer (Ablaufpunkt 26).
Die Dekomprimierung geht beim Lesen in derselben Reihenfolge sequentiell durch die Daten, das heißt iterativ über alle Wegpunkte und Kanten und speichert die einzelnen Wegpunkt- und Kantenelemente in jeweils einer Tabelle in der Reihenfolge des Auftretens. Der Dekomprimierungsgrad ist in Abhängigkeit des Informationsgehaltes der Daten konfigurierbar ausgebildet unter Berücksichtigung der bei der Komprimierung getroffenen Maßnahmen (siehe dortige Beschreibung). Beim Lesen der einzelnen Attributwerte aus den komprimierten Daten wird anhand der gelesenen Indikatorwerte folgendermaßen vorgegangen:
Indikator ist gleich

- N.V.: Attributwert bleibt leer, bzw. bekommt Defaultwert zugewiesen
- Vorgänger: Attributwert dieses Elements wird gleich dem des Elements eine Zeile vorher in der Tabelle gesetzt
- Index: Index i wird aus den komprimierten Daten gelesen und der Attributwert wird gleich dem des n-ten Elementeintrags in der Tabelle gesetzt
- Explizit: Attributwert wird unkomprimiert aus den Daten gelesen.

In vorteilhafter Weise kann der Komprimierungsalgorithmus, z. B. von einem Client, konfiguriert werden, so dass (vom Client) die Art der Komprimierung und/oder der Komprimierungsgrad vorgegeben werden, wodurch Daten eingespart werden können. Folgende Konfigurationsmöglichkeiten sind einzeln oder in Kombination möglich:

- Weglassen von Informationen, die z. B. (vom Client) nicht verarbeitet werden können, z. B. Kanten IDs
- Vorgabe von Genauigkeiten, die z. B. für eine Applikation, die die dekomprimierten Daten nutzt, nicht benötigt werden, z. B.:
- Koordinatengenauigkeit
- Vorgabe einer maximalen Größe der komprimierten Daten, wodurch der Komprimieralgorithmus die Kompression bei Erreichen des vorgeschriebenen Kriteriums abbricht, z. B.
- max × kByte Datenmenge
- max × Meter Länge der Hauptroute
- max × Minuten Fahrtzeit der Hauptroute
- . . .

Das Verfahren nach der Erfindung kann vorteilhafter Weise in einem oder mehreren der folgenden Verfahren zur Größenreduktion der Routen-/Kartendaten kombiniert werden:

- Verringerung der Koordinatendaten dadurch, dass die Koordinatengenauigkeit (Auflösung der Wegepunkte) generell eingeschränkt wird und weiterhin, sofern möglich, für einen Wegpunkt nicht seine absoluten Koordinaten sondern seine relative Entfernung als Vektor zum zuvor übertragenen Wegpunkt übertragen/gespeichert wird
- Ersetzen von häufig vorkommenden Begriffen durch nicht anderweitig verwendete Sonderzeichen, z. B. "Straße" durch "Paragraphzeichen". Diese Begriffsersetzung ist unabhängig von bestimmten Routen-/Kartendaten und wird vorab definiert
- Weiteres Komprimieren der nach diesem Verfahren reduzierten Daten durch einen anderen allgemeinen Komprimierungsalgorithmus

Nachfolgend wird ein konkretes Ausführungsbeispiel beschrieben.
In Fig. 4 ist exemplarisch ein Routengraph dargestellt:

- Die Hauptroute verläuft vom Punkt P1 über die Kanten K1, K2 und K5 zu Punkt P6. Alle drei Kanten haben den Straßennamen "Robert-Bosch-Straße" und die Straßenklasse 3.
- An Punkt P2 beginnt ein Abzweig über die Kanten K3, K4, die zur Hildesheimer Straße gehören und der Straßenklasse 5 zugeordnet sind.

Für die Übertragung wird für die Straßennamen ein Indikator vereinbart, der die Werte Explizit, Vorgänger und Index annehmen kann. Für die Straßenklasse analog ein Indikator mit den möglichen Werten Explizit und Vorgänger.
Nach Durchlaufen des Komprimieralgorithmus ergeben sich die in der folgenden Tabelle dargestellten Werte für die Übertragung/Speicherung. Der Einfachheit halber sind hier nur die zu übertragenden/speichernden Attribute der Kanten dargestellt.

Claims

1. Verfahren zum Komprimieren von Daten eines Datenstromes unterschiedlichen Informationsgehaltes, insbesondere Daten, die aus topografischen Knoten und Kanten sowie deren Attributen bestehen, wobei der Komprimierungsgrad in Abhängigkeit des Informationsgehaltes der Daten konfigurierbar ausgebildet ist und wobei zur Komprimierung mindestens eine der nachfolgenden Maßnahmen angewendet wird:

- Weglassen vorgegebener Attribute, z. B. Kantenidentifikationen,

- Begrenzen der Genauigkeit der topografischen Information, z. B. deren Koordinatengenauigkeit,

- Vorgeben einer maximalen Datenmenge und entsprechender Steuerung des Komprimierungsgrades.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Komprimierung sequentiell durchgeführt wird, das heißt während der Komprimierung Teildatensätze in der Reihenfolge ihres erstmaligen Auftretens gespeichert und in den komprimierten Datenbereich übertragen werden.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass ausgewählten Attributen, insbesondere für die Übertragung, ein Indikator zugewiesen wird zur Kennzeichnung, ob insbesondere ein Datenelement hierzu vorhanden ist, ob das Datenelement gleich dem unmittelbar vorhergehenden Datenelement ist oder ob das Datenelement gleich einem früher übertragenen Datenelement ist.

4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, dass in Abhängigkeit des Indikatorwertes kein Datenelement, ein Datenelement oder ein Verweis auf ein früheres Datenelement dem Indikator nachfolgend übertragen wird.

5. Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass zur Komprimierung vorhandene Knoten sequentiell überprüft werden, um

- die Attribute des aktuellen Knotens zu komprimieren,

- einen aktuellen Knoten als Vorgängerknoten für einen nachfolgenden Knoten zu definieren,

- die von einem aktuellen Knoten ausgehende aktuelle Kante und deren Attribute zu komprimieren,

- die aktuelle Kante als Vorgängerkante für eine nachfolgende Kante zu definieren,

- zu überprüfen, ob von einem aktuellen Knoten weitere Kanten ausgehen und deren Attribute zu komprimieren bzw. sie als weitere Vorgängerkante für eine weitere nachfolgende Kante zu definieren.

6. Verfahren nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, dass für die Komprimierung ein Attributspeicher als Zwischenspeicher bereitgestellt wird, um vor der Übertragung der Daten in den komprimierten Datenbereich für ein Datenelement ein/den Indikator zu bestimmen, damit anstatt des Datenwertes des Datenelements gegebenenfalls nur noch ein Verweis auf ein Vorgängerelement oder ein Verweis auf ein beliebiges anderes Datenelement gespeichert bzw. komprimiert werden muss.

7. Verfahren zum Dekomprimieren von Daten eines Datenstromes unterschiedlichen Informationsgehaltes, insbesondere Daten, die aus topografischen Knoten und Kanten sowie deren Attributen bestehen, wobei der Dekomprimierungsgrad in Abhängigkeit des Informationsgehaltes der Daten konfigurierbar ausgebildet ist unter Berücksichtigung von bei der Komprimierung getroffener Maßnahmen wie:

- Weglassen vorgegebener Attribute, z. B. Kantenidentifikationen,

- Begrenzen der Genauigkeit der topografischen Information, z. B. der Koordinatengenauigkeit,

- Vorgeben einer maximalen Datenmenge und entsprechender Steuerung des Dekomprimierungsgrades.

8. Verfahren nach Anspruch 7, dadurch gekennzeichnet, dass die Dekomprimierung sequentiell durchgeführt wird, das heißt während der Dekomprimierung Teildatensätze in der Reihenfolge ihres erstmaligen Auftretens in einer Tabelle eingetragen und anschließend dekomprimiert werden.

9. Verfahren nach einem der Ansprüche 7 oder 8, dadurch gekennzeichnet, dass ausgewählte Attribute, denen Indikatoren zugeordnet sind, bei der Dekomprimierung daraufhin untersucht werden, ob Datenelemente leer sind und ihnen gegebenenfalls ein Defaultwert zuzuordnen ist, es sich um einen bereits komprimierten Vorgängerwert handelt oder einen beliebigen anderen bereits bekannten Wert, der übernommen werden kann.

10. Verfahren nach einem der Ansprüche 1 bis 6 und einem der Ansprüche 7 bis 9, dadurch gekennzeichnet, dass die Komprimierung bei einem Diensteanbieter und die Dekomprimierung bei einem Dienstenutzer vorgenommen wird.

11. Verfahren nach einem der Ansprüche 1 bis 10, dadurch gekennzeichnet, dass der Komprimierungs- bzw. Dekomprimierungsgrad von einem Dienstenutzer, z. B. dem Nutzer von Routeninformationen bei der Offboard-Navigation durch Konfigurierung vorgegeben wird.