(57)【要約】種々の情報内容のデータの圧縮および解凍方法を提供する。データは例えばトポグラフィックノードおよびトポグラフィックエッジまたはその属性値である。圧縮のグレードは情報内容に依存してコンフィグレーション可能である。  圧縮のために属性値が省略されるか、トポグラフィック情報の精度が制限されるか、または圧縮グレードが設定された最大データ量に基づいて制御される。
2005525763.tif 000002
【特許請求の範囲】
【請求項１】
種々の情報内容、例えばトポグラフィックノードおよびトポグラフィックエッジおよびそれらの属性値から成るデータを有しており、
データの情報内容に依存して圧縮グレードをコンフィグレーション可能である、
データストリームのデータの圧縮方法において、
圧縮のために
ａ）設定された属性値、例えばエッジＩＤを省略する手段、
ｂ）トポグラフィック情報またはその座標の精度を制限する手段、
ｃ）最大データ量を設定し、相応に圧縮グレードを制御する手段
のうち少なくとも１つを用いる
ことを特徴とするデータストリームのデータの圧縮方法。
【請求項２】
圧縮をシーケンシャルに行う、つまり圧縮中に部分データセットを最初の生起に続いて順次に記憶し圧縮データ領域へ移す、請求項１記載の方法。
【請求項３】
選択された属性値に対して、例えば伝送のために、例えば対応するデータエレメントが存在しているか否か、または或るデータエレメントがその直前に生じたデータエレメントと同じであるか否か、または或るデータエレメントが先行して伝送されたデータエレメントと同じであるか否かを表すインジケータを割り当てる、請求項１または２記載の方法。
【請求項４】
インジケータ値に依存して、データエレメントを伝送しないか、所定のデータエレメントを伝送するか、または先行のデータエレメントに対する指示をインジケータに続いて伝送する、請求項３記載の方法。
【請求項５】
圧縮すべきノードをシーケンシャルに検査して、
ｉ）現在のノードの属性値を圧縮し、
ｉｉ）現在のノードを次のノードに対する先行ノードとして定義し、
ｉｉｉ）現在のノードから出ている現在のエッジおよびその属性値を圧縮し、
ｉｖ）現在のエッジを次のエッジに対する先行エッジとして定義し、
ｖ）現在のノードから他のエッジが出ているか否かを検査し、その属性値を圧縮するか、または次のエッジに対する第２の先行エッジとして定義する、
請求項１から４までのいずれか１項記載の方法。
【請求項６】
圧縮に対して所定の属性値メモリをバッファメモリとして構成し、データを圧縮データ領域へ移す前に各データエレメントに対して１つまたは複数のインジケータを求め、データエレメントのデータ値に代えて、場合により唯一の先行エレメントに対する指示または任意の他のデータエレメントに対する指示を記憶して圧縮する、請求項１から５までのいずれか１項記載の方法。
【請求項７】
種々の情報内容、例えばトポグラフィックノードおよびトポグラフィックエッジおよびそれらの属性値から成るデータを有している、
データストリームのデータの解凍方法において、
データの情報内容に依存して、圧縮の際に行われた
ａ）設定された属性値、例えばエッジＩＤを省略する手段、
ｂ）トポグラフィック情報またはその座標の精度を制限する手段、
ｃ）最大データ量を設定し、相応に解凍グレードを制御する手段
のうち少なくとも１つを考慮して解凍グレードをコンフィグレーション可能である
ことを特徴とするデータストリームのデータの解凍方法。
【請求項８】
解凍をシーケンシャルに行う、つまり解凍中に部分データセットを最初の生起に続いて順次にテーブルへ入力し解凍する、請求項７記載の方法。
【請求項９】
選択された属性値にインジケータを割り当て、これに応じて解凍の際に、データエレメントが空であって場合によりこれにデフォルト値が割り当てられているか否か、またはすでに圧縮されている先行値であるか否か、またはすでに引き受けられた任意の他の既知の値であるか否かを検査する、請求項７または８記載の方法。
【請求項１０】
圧縮はサービスプロバイダ側で行い、解凍はユーザ側で行う、請求項１から９までのいずれか１項記載の方法。
【請求項１１】
ユーザ、例えばオフボードナビゲーションにおけるルート情報のユーザが圧縮グレードまたは解凍グレードをコンフィグレーションにより設定する、請求項１から１０までのいずれか１項記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
従来技術
本発明はデータストリームのデータの圧縮方法を基礎としている。
【０００２】
独国公開第１０１０６５０２．７号公報にはルートデータの伝送方法が記載されている。ルートデータは経路ポイントデータの形態のノードと、そのあいだに存在するエッジ（経路）と、これらに属する属性値とから成る。個々の経路ポイントは相互に結合されてルートコリドーをなしており、データ容量が最小限まで抑えられている。有利には経路ポイントデータはシーケンシャルに伝送される。
【０００３】
独国公開第１０１０５８９７．７号公報にはナビゲーションデータを端末機と中央局とのあいだで交換する方法が記載されている。ここでは起点と終点とのあいだのルートが部分ルートへセグメント化され、伝送される。この方法にしたがうオフボードナビゲーション装置はルート情報を独立して計算するのではなく、適切な無線インタフェースを介してサーバへ問い合わせる。つまりサーバがルート情報をナビゲーション装置へ伝送するのである。
【０００４】
独国特許第１００１２４４１号公報からナビゲーション装置での目的地入力方法が知られる。処理コストを低減するために、現在地の周囲に存在する目的地名称のみが記録される。さらに目的地名称リストとして目的地が距離に応じて分類される。
【０００５】
本発明の利点
本発明の方法は、種々の情報内容を有するデータストリームのデータの圧縮方法に関する。情報内容は特にトポグラフィックノード（経路ポイント）およびトポグラフィックエッジ（接続経路）およびそれらの属性値から成るルートデータを有している。本発明ではデータの情報内容に依存して圧縮グレードをコンフィグレーション可能である。ここで圧縮に際して、設定された属性値を省略する手段、精度（例えば座標精度）を制限する手段、最大データ量を設定して相応に圧縮グレードを制御する手段のうち少なくとも１つが用いられる。
【０００６】
データの重要度やその情報内容を無視して圧縮を行う周知の圧縮方法とは異なり、本発明ではデータが解釈され、その重要度の知識から特に冗長的な要素が消去される。
【０００７】
付加的なデータフィールドも、例えばルート情報の伝送のために独国公開１０１０６５０２．７号公報の手法にしたがって設定されたデータフォーマットで任意に利用することができる。
【０００８】
本発明の方法はルートデータの圧縮に特に適しているが、他の全てのデータに適用可能である。有利には本発明の方法はグラフ構造のデータ、すなわちトポグラフィックノードおよびトポグラフィックエッジ（例えばマップデータ）を含むＣＡＤデザインのポリゴンから成るデータにも適している。
【０００９】
本発明の圧縮方法は特にオフボードナビゲーション装置に対してサーバ上でサービスプロバイダによって使用され、本発明の解凍方法（データ復号化方法）は特に端末機側またはクライアント側で使用される。
【００１０】
従属請求項には本発明の圧縮方法および解凍方法の有利な実施形態が記載されている。本発明の方法の他の利点を以下に列挙しておく。
１．処理データのサイズが低減され、これにより低いデータレートで伝送媒体を良好に利用することができる。
２．圧縮のアルゴリズムおよび解凍のアルゴリズムの複雑性が低減されるので、小さな作業メモリを備えた軽いプロセッサの端末機にも適している。
３．圧縮プロセスは厳密にシーケンシャルである。つまり圧縮中に既に部分データセットを記憶したり伝送したりできる。
４．圧縮データのシーケンシャルな構造において、部分データセットの解凍を伝送中に行うことができる。
５．頻繁に生じるデータエレメントを備えた完全なテーブルをデータの開始部または終了部に付加しなければならない他の多くの圧縮方法とは異なり、本発明では個々のエレメントが必要な位置のみに挿入され、伝送の時点ではそのつど最大数のデータエレメントが供給される。
【００１１】
図面
図に即して本発明の実施例を説明する。図１にはルートグラフのシーケンシャル処理が示されている。図２にはアソシエイティブメモリを利用した圧縮プロセスのブロック図が示されている。図３には属性値の圧縮方法が示されている。図４にはルートグラフの例が示されている。
【００１２】
実施例の説明
本発明の方法はトポグラフィックルートまたはマップデータが経路ポイント（ノード）および各ノードを接続する路線（エッジ）から成るということを基礎としている。さらにノードおよびそのあいだのエッジはルートデータにおいて有利な起点から目的地へ向かう方向を表す順序を含んでいる。
【００１３】
経路ポイントは一般に
１．座標
２．一義的な識別子（ＩＤ）
などの属性値のうち１つまたは複数のものを有している。
【００１４】
エッジは一般に
１．道路名
２．道路クラス
３．目的地案内の指示（グラフィックおよび／または音響）
４．目的地ノード（経路ポイントの指示）
５．走行時間
６．距離
７．一義的な識別子（ＩＤ）
などの属性値のうち１つまたは複数のものを有している。
【００１５】
使用されるデータフォーマットにおいて、付加的に伝送されるＩＤ、道路名、目的地案内の指示などの大きな冗長性を有する属性値に対してそれぞれ１つずつインジケータを定義する。インジケータは
１．データエレメントが存在しない（またはデフォルト値に等しい）・・・N.V.
２．データエレメントが先行のものと等しい・・・Vorgaenger
３．データエレメントがｘ番目のエレメントに等しい→インデクスｘが続いている・・・Index
４．エレメントのデータ値が続いている・・・Explizit
のうち２つ以上の値を取りうる。
【００１６】
有利には伝送すべき経路ポイントに対するインジケータまたは伝送すべきエッジに対するインジケータが１つのビットフィールドにまとめられる。
【００１７】
圧縮アルゴリズムはシーケンシャルに進行し、特に、存在する全ての経路ポイントを反復的に通る（図１を参照）。
１．開始ステップ１および割り当てステップ（現在地を第１の経路ポイントとする）２の後、現在地の属性値を伝送する（ステップ３）
２．現在地を先行ポイントとしてマークする（ステップ４）
３．現在地から出る全てのエッジを有利にはメインルートから同様に反復的に処理する（ステップ５）
３ｂ．現在のエッジの属性値を伝送する（ステップ６）
３ｂ．現在のエッジを先行エッジとしてマークする（ステップ７）
４．現在地から出るエッジのうち第１のものまたはメインルートを先行エッジとしてマークする（ステップ９）。
【００１８】
ステップ８では現在地がさらなるエッジを有するか否かが検査される。有する場合には現在のエッジとして現在地の次のエッジが選択され、本発明の方法はステップ６へ進行する。
【００１９】
ステップ１０ではさらなるポイントが存在しているか否かが検査される。存在していない場合には本発明の方法は終了する。存在している場合には次のポイントが現在のポイントとして選択され、本発明の方法がステップ３で新たに開始される。
【００２０】
本来の圧縮は属性値の伝送の際に行われる。ここで圧縮アルゴリズムは各属性値ごとにアソシエイティブメモリ２７を駆使する。属性値ごとに、複数のインデクス値を取りうる１つのインジケータが定義されている（図２を参照）。アルゴリズムは各属性値にエレメント番号、すなわちポイントまたはエッジの番号を割り当てるので、この値が最初に生じる。すなわち例えば“Robert-Bosch通り”→５というのは道路名“Robert-Bosch通り”が最初第５のエッジとして生じたことを意味している。アソシエイティブメモリ２７はバッファメモリとして利用され、圧縮中に格納や消去が行われる。これに代えて属性値にメモリ内のエレメント番号を割り当ててもよい。例えば相応の属性値が３番目にメモリへ入力されたのであれば、番号は３となる。圧縮プロセス部２８は直接にアソシエイティブメモリ２７に接続されている。入力データは未圧縮のルートデータであり、出力データは圧縮されたルートデータ３０である。
【００２１】
本来のポイント／エッジ属性値が圧縮データ領域へ移される前に各エレメントごとにインジケータを求め、当該の値に代えて場合により先行エレメントに対する指示または任意の他のエレメントに対する指示のみを伝送する。
【００２２】
経路ポイント／エッジの個々の属性値の詳細な流れが図３に示されている。図３によれば、まず属性値に対するインジケータが定義されているか否かが検査される（ステップ１２）。定義されている場合、当該の属性値が充填されているか否かないしは妥当であるか否かが検査される（ステップ１３）。妥当でない場合にはインジケータはN.V.として定義され、つまり属性値は空のままであることがわかる（ステップ１４）。妥当である場合には現在の属性値が先行エレメントの属性値と等しいか否かが検査される（ステップ１５）。等しい場合には当該のエレメントの属性値は先行エレメントの属性値に等しく定義される（ステップ１６）。等しくない場合には“Index”が現在のインジケータに対する許容値となっているか否かが検査される（ステップ１７）。許容される場合には、相応の属性値がアソシエイティブメモリ内に存在しているか否かが検査される（ステップ１８）。存在している場合には当該のインジケータに対してインデクスが定義される（ステップ１９）。存在していない場合には、属性値またはそのエレメント番号が記憶され（ステップ２０）、圧縮されずに処理を行う“Explizit”として定義される（ステップ２１）。続いてステップ２１，１９，１６，１４の後の３つのケースに対してインジケータがメモリに記憶され（ステップ２２，２３，２４）、そののち属性値が書き込まれるか（ステップ２５）、またはエレメント番号が書き込まれる（ステップ２６）。
【００２３】
解凍は同様にシーケンシャルにデータを読み出す際に行われる。つまり全ての経路ポイントおよびエッジを反復的に読み出し、個々の経路ポイントおよびエッジエレメントをそれぞれ生起順にテーブルに記憶する。解凍グレードはデータの情報内容に依存してコンフィグレーション可能であり、圧縮時に適用された措置を考慮している（上述の説明を参照）。圧縮データからの個々の属性値の読み出しは読み出されたインジケータ値に基づいて進行する。すなわちインジケータはそれぞれ
１）N.V.：属性値が空であるか、デフォルト値が割り当てられている
２）Vorgaenger：当該のエレメントの属性値はテーブルの前の行にセットされた先行エレメントの属性値に等しい
３）Index：インデクスｉが圧縮データから読み出され、属性値はテーブルのｎ番目のエレメントに等しい
４）Explizit：属性値は圧縮されていない状態でデータから読み出される
を意味する。
【００２４】
有利には圧縮アルゴリズムは例えばクライアント側でコンフィグレーションされるので、クライアントが圧縮のタイプおよび／または圧縮グレードを設定できる。これによりデータが節約される。次のようなコンフィグレーション手段を単独で、また任意に組み合わせて利用可能である。すなわち
１）クライアント側で処理できない情報（例えばエッジＩＤなど）の省略
２）例えば解凍データを利用するアプリケーションに不要な精度の設定
３）座標精度
４）圧縮データの最大サイズが設定されておりかつ前述の基準に達した場合の圧縮の遮断
５）最大ｘ ｋＢｙｔｅのデータ量
６）最大ｘ ｍのメインルート長さ
７）最大ｘ ｍｉｎのメインルートの走行時間
などである。
【００２５】
本発明の方法では有利には１つまたは複数のルートデータまたはエッジデータのサイズ低減方法を組み合わせることができる。すなわち
１）座標精度（経路ポイントの分解能）を全般的に制限することにより座標データを低減する。１つの経路ポイントに対して可能なかぎり絶対座標でなく、先行の経路ポイントに対するベクトルとしての相対距離を用いる。
２）頻繁に生じる概念を一義的に使用できるマークによって置換する（例えば“通り”をパラグラフ記号によって置換する）。こうした概念置換は所定のルートデータまたはエッジデータとは無関係に予め定義される。
３）本発明の方法にしたがって低減されたデータをさらに別の一般的な圧縮アルゴリズムによって圧縮する。
【００２６】
続いて具体的な実施例を説明する。
【００２７】
図４にはルートグラフの例が示されている。
１）メインルートはポイントＰ１からエッジＫ１，Ｋ２，Ｋ５を介してポイントＰ６へいたる。３つのエッジの全てが道路名“Robert-Bosch通り”および道路クラス３を有している。
２）ポイントＰ２から別の分岐がエッジＫ３，Ｋ４を介して始まっている。これは“Hildesheim通り”に属し、道路クラス５を有する。
【００２８】
伝送のために道路名について値Explizit，Vorgaenger，Indexを取りうるインジケータが定められる。道路クラスについてはアナログに値Explizit，Vorgaengerを取りうるインジケータが定められる。
【００２９】
圧縮アルゴリズムの実行後、下記のテーブルに示されている伝送または記憶のための値が生じる。わかりやすくするためにここでは伝送または記憶すべきエッジの属性値のみを示してある。
【００３０】
【表１】
2005525763.tif 000003
【図面の簡単な説明】
【００３１】
【図１】ルートグラフのシーケンシャル処理を示すフローチャートである。
【図２】アソシエイティブメモリを利用した圧縮プロセスを示すブロック図である。
【図３】属性値の圧縮方法を示すフローチャートである。
【図４】ルートグラフの例を示す図である。
【図１】
2005525763.tif 000004
【図２】
2005525763.tif 000005
【図３】
2005525763.tif 000006
【図４】
2005525763.tif 000007
【国際調査報告】
2005525763.tif 000008
2005525763.tif 000009
2005525763.tif 000010
2005525763.tif 000011
2005525763.tif 000012
2005525763.tif 000013