(57)【要約】【課題】交差点等が頻出する都市部の道路を表示するカーナビゲーションシステムにおける道路データ等のベクトルデータの圧縮率を向上する。【解決手段】道路データを構成するベクトルデータ列が圧縮装置１００に入力される。データ圧縮装置１００のベクトル変換部１３０では、入力データであるＸＹ座標の列に対して差分をとり、得られＸ座標およびＹ座標の差分データを所定のビット数毎に組み合わせて複数桁のバイト列を生成する。生成された複数桁のバイト列の各桁に対して、複数の圧縮部１５０で個別に圧縮を施し圧縮データを生成する。また、データ伸張装置２００に入力された圧縮データから、データ圧縮装置１００と逆の手順によりＸＹ座標の列が復元される。【選択図】図１
2009055308.tif 000002
【特許請求の範囲】
【請求項１】
圧縮されたデータを伸張するベクトルデータ伸張装置であって、
圧縮データを読み込むデータ入力部と、
前記圧縮データを伸張して伸張データを出力する所定数の伸張部と、
所定数の前記伸張部が出力する前記伸張データ各々を複数の成分に分割し、分割した前記伸張データを成分毎に結合することによりベクトルデータを復元するベクトル逆変換部と、
復元された前記ベクトルデータを出力するデータ出力部と
を備えたベクトルデータ伸張装置。
【請求項２】
請求項１記載のベクトルデータ伸張装置であって、
前記ベクトルデータはＸＹ座標データを含むデータであり、
前記ベクトル逆変換部で、前記伸張データ各々を分割する前記成分は、Ｘ方向成分およびＹ方向成分であり、
前記ベクトル逆変換部は、分割した前記伸張データをＸＹ方向成分毎に結合することにより前記ベクトルデータを復元する
ベクトルデータ伸張装置。
【請求項３】
請求項１記載のベクトルデータ伸張装置であって、
前記ベクトル逆変換部は、分割した前記伸張データを成分毎に結合して得た結合データを、直前のデータに対する差分値として扱い、前記結合データと前記直前のデータを加算して前記データ出力部に出力する
ベクトルデータ伸張装置。
【請求項４】
請求項２記載のベクトルデータ伸張装置であって、
前記ベクトル逆変換部は、分割した前記伸張データを前記ＸＹ方向成分毎に結合して得た結合データを、直前のデータに対する差分値として扱い、前記結合データと前記直前のデータを加算して前記データ出力部に出力する
ベクトルデータ伸張装置。
【請求項５】
請求項２記載のベクトルデータ伸張装置であって、
前記ベクトルデータは地図データである
ベクトルデータ伸張装置。
【請求項６】
請求項４記載のベクトルデータ伸張装置であって、
前記ベクトルデータは地図データであり、前記座標データは道路上の座標を示す
ベクトルデータ伸張装置。
【請求項７】
請求項１記載のベクトルデータ伸張装置であって、
前記データ入力部は、前記ベクトルデータの復元に用いる設定情報を読み込むと共に、
前記設定情報を所定数の前記伸張部に設定するパラメータ設定部を更に有する
ベクトルデータ伸張装置。
【請求項８】
ベクトルデータを圧縮するベクトルデータ圧縮装置であって、
複数の要素データからなる前記ベクトルデータを入力するデータ入力部と、
複数の前記要素データ各々を所定の桁数で分割し、分割した前記要素データの同位桁を組み合わせることにより複数の結合データを生成するベクトル変換部と、
複数の前記結合データ各々を圧縮処理して圧縮データを生成する複数の圧縮部と、
複数の前記圧縮部が生成した前記圧縮データを出力するデータ出力部と
を有するベクトルデータ圧縮装置。
【請求項９】
請求項８記載のベクトルデータ圧縮装置であって、
前記データ入力部に入力される前記ベクトルデータの複数の前記要素データは、ＸＹ座標におけるＸ方向データおよびＹ方向データであり、
前記ベクトル変換部は、前記Ｘ方向データおよび前記Ｙ方向データを一定ビット数毎に分割し、分割した前記Ｘ方向データおよび前記Ｙ方向データのビット位置が同一であるものを組み合わせて複数の前記結合データを生成する
ベクトルデータ圧縮装置。
【請求項１０】
請求項８記載のベクトルデータ圧縮装置であって、
前記ベクトル変換部は、複数の前記結合データ各々について、直前のデータに対する差分データを算出し、前記差分データを複数の前記圧縮部に出力する
ベクトルデータ圧縮装置。
【請求項１１】
請求項９記載のベクトルデータ圧縮装置であって、
前記ベクトル変換部は、分割した前記Ｘ方向データおよび前記Ｙ方向データのビット位置が同一であるものを組み合わせることにより得た複数の前記結合データ各々について、直前のデータに対する差分データを算出し、前記差分データを複数の前記圧縮部に出力する
ベクトルデータ圧縮装置。
【請求項１２】
請求項９記載のベクトルデータ圧縮装置であって、
前記データ入力部に入力される前記ベクトルデータは地図データであり、前記Ｘ方向データおよび前記Ｙ方向データは、道路上のＸＹ座標を示す
ベクトルデータ圧縮装置。
【請求項１３】
請求項１１記載のベクトルデータ圧縮装置であって、
前記データ入力部に入力される前記ベクトルデータは地図データであり、前記Ｘ方向データおよび前記Ｙ方向データは、道路上のＸＹ座標を示す
ベクトルデータ圧縮装置。
【請求項１４】
請求項８記載のベクトルデータ圧縮装置であって、
前記所定の桁数を含む前記ベクトルデータの圧縮に関する設定情報を入力するパラメータ入力部を更に有する
ベクトルデータ圧縮装置。
【請求項１５】
請求項８記載のベクトルデータ圧縮装置であって、
複数の前記圧縮部における圧縮処理は、適応型算術符号である
ベクトルデータ圧縮装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はベクトルデータを圧縮・伸張する技術に関するものである。
【背景技術】
【０００２】
カーナビゲーションシステム（以下、カーナビとする）は、地図データを加工してユーザに交通案内情報を提供するものである。この地図データの記録手段として従来はＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）を使用していたが、近年はＤＶＤよりも大容量、かつ高速なＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）等、カーナビ内部の記録装置を使用する製品が主流になりつつある。
【０００３】
ＨＤＤ型のカーナビでは、道路や建物の建設・撤去等により地図データが古くなった場合、ユーザに適切な交通情報を提供するため、カーナビ内部のデータを最新のものに更新する必要がある。従来のＤＶＤ型のカーナビの場合、地図データを記録しているＤＶＤをユーザへ販売し、ユーザが古いディスクと交換することによって容易に更新することができる。これに対してＨＤＤ型のカーナビの場合、ユーザがＨＤＤ自体の交換を行うことは困難であるため、通常は何らかの手段により地図データをＨＤＤにコピーしなければならない。このコピーを行う手段として、地図データを記録しているＤＶＤをカーナビに挿入してＨＤＤへコピーする方式が一般的である。
【０００４】
このとき、更新する必要がある地図データが巨大であるため、単純にデータをＤＶＤに記録すると、ＤＶＤの枚数の増加、および更新所要時間の増加をもたらす。そのため、ＤＶＤに記録する地図データを圧縮することにより、ＤＶＤ枚数や更新所要時間を短縮することが望まれている。こうした背景により、地図データを圧縮する手段として以下の技術が提案されている。
【０００５】
まず、一般的な圧縮技術として、非特許文献１に記載のＧＺＩＰ等の汎用のデータ圧縮技術がある。これらの技術は、一般的にデータサイズが小さくなるため有効である一方、入力データに依存しない汎用の圧縮技術であるため、地図データに特化したアプローチによってさらにデータサイズを削減する技術が提案されている。
【０００６】
例えば特許文献１に記載の技術は、道路を構成する曲線を、一定距離の線分の集合として近似し、隣接する線分の間の偏角の列で道路を表現する。このように表現することによって、道路を構成するＸＹ座標のデータ列は、偏角という１つのパラメータの列として表すことができ、データサイズを大幅に削減することができる。
【０００７】
また、地図データに特化した別の圧縮方式として、特許文献２に記載の技術がある。この技術は、道路データを構成するベクトルデータを、隣り合うベクトルデータの差によって表記するものである。このように表記することにより、例えば道路が直線に近い形状の場合、隣り合うベクトルデータの差はＸ方向およびＹ方向ともにゼロに近づくため、単純にベクトルデータを記載するよりも少ない桁数で表記することができ、データサイズを削減することが可能となる。
【０００８】
以上に示した技術を利用することによって、カーナビのＨＤＤを書き換える際のデータサイズを削減することが可能となり、必要ＤＶＤ枚数の削減や、更新所要時間の短縮が実現される。
【０００９】
【非特許文献１】Ｐ．Ｄｅｕｔｓｃｈ，ＧＺＩＰ  ｆｉｌｅ  ｆｏｒｍａｔ  ｓｐｅｃｉｆｉｃａｔｉｏｎ  ｖｅｒｓｉｏｎ  ４．３，ＲＦＣ１９５２，１９９６年５月
【特許文献１】特開２００３−２３３５７号公報
【特許文献２】特開２００４−３４８５６４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記の特許文献１および２に記載の技術には、以下の課題があると考えられる。
【００１１】
まず、特許文献１に記載の技術は、道路を一定サイズの線分で近似して圧縮するものであるため、圧縮後のデータから元の地図データを正確に復元することは不可能である。すなわち、特許文献１に記載の技術は、いわゆる非可逆圧縮と呼ばれる技術に分類される。非可逆圧縮技術は、元データを正確に復元する必要性がない用途には非常に有効である一方、カーナビの地図データなど、データの完全性が強く求められる用途には向かない。
【００１２】
次に、特許文献２に記載の技術は、データの可逆性の観点では問題はないが、この技術が有効であるケースは、道路が緩やかな直線道路である場合に限定されるという問題がある。すなわち、例えば都市部の地図のように交差点が多数あり、道路の右折・左折が頻繁に出現する場合、隣接するベクトルデータの差が必ずしもゼロに近づくとは限らず、むしろベクトルデータの差が大きな値となることにより、かえってサイズの増加を招く可能性がある。
以上の点に鑑み、本発明は、ベクトルデータの圧縮において、ベクトルデータの可逆性を有しつつ、右折・左折等の直線ではないベクトルデータ列が出現する都市部の地図データなどに対して有効なベクトルデータ圧縮、伸張装置を提供することを課題とする。
【課題を解決するための手段】
【００１３】
上記の課題を解決するため、本発明は、道路データ等を構成するベクトルデータ列の出現頻度を確率的に表現してデータ圧縮を行う。一般的な地図上の道路では、あるベクトルデータが存在する場合、隣接する次のベクトルの方向・サイズには確率的な偏りがある。すなわち、直線道路を構成するベクトルデータ列の場合、隣接するベクトルはほぼ同じ方向を指し、交差点を含むベクトルデータ列では、隣接するベクトルの方向はほぼ直角に曲がり、緩やかなカーブを構成するベクトルデータ列では、ベクトルの方向は一定の曲率で曲がっていく。本発明のデータ圧縮装置およびデータ伸張装置は、こうした地図データ特有の確率的な偏りを利用して地図データを圧縮するものである。
【００１４】
このような確率的な偏りを利用して圧縮を行うため、本発明は、ベクトルデータを圧縮するベクトルデータ圧縮装置であって、複数の要素データからなるベクトルデータを入力するデータ入力部と、これら複数の要素データの各々を所定の桁数で分割し、分割された要素データの同位桁を組み合わせることにより複数個のデータを生成するベクトル変換部と、これら複数個のデータの各々に対して圧縮処理を行うことにより圧縮データを生成する複数の圧縮部と、得られた圧縮データを出力するデータ出力部とを備えているベクトルデータ圧縮装置を提供するものである。
【００１５】
また本発明は、圧縮されたベクトルデータを伸張するベクトルデータ伸張装置であって、圧縮データを読み込むデータ入力部と、この圧縮データを伸張する所定の個数の伸張部と、所定の個数の伸張データの各々を複数成分に分割して、分割されたデータを成分毎に結合することによりベクトルデータを復元するベクトル逆変換部と、復元されたデータを出力するデータ出力部とを備えているベクトルデータ伸張装置を提供するものである。
【発明の効果】
【００１６】
本発明により、ベクトルデータを可逆的、且つ高い圧縮率で圧縮し、伸張することが可能となる。
【発明を実施するための最良の形態】
【００１７】
以下、図面を用いて本発明の実施の形態を説明する。
【実施例１】
【００１８】
以下、図１から図８を用いて、第一の実施例の地図データ更新システムについて説明する。本実施例は、ＨＤＤ更新用の地図データを圧縮してＤＶＤに記録し、この圧縮されたデータを記録しているＤＶＤを用いてカーナビのＨＤＤを書き換える更新システムについてのものである。
【００１９】
図１は、地図データ更新システムの全体構成図を示したものである。本システムは、データ圧縮装置１００、データ伸張装置２００、および更新用ＤＶＤ３００から構成される。
【００２０】
データ圧縮装置１００は、後述する制御データ３２１と座標データ３２２からなる更新データ３２０を記録しているデータ記録部１１０、データ記録部１１０から更新データ３２０を読み込み、制御データ３２１はデータ出力部１７０へ、座標データ３２２はベクトル変換部１３０へそれぞれ出力するデータ入力部１２０、読み込まれた座標データ３２２を後述の手順に従って４バイトのベクトルデータに変換するベクトル変換部１３０、変換されたベクトルデータ４バイトの各々の桁毎に出現頻度を記録する頻度表記録部１４０、頻度表記録部１４０を参照してベクトルデータ４バイトの各々の桁毎に出現率を取得・更新する圧縮部１５０、圧縮部１５０が出力する出現率をもとに圧縮データを生成する符号化部１６０、制御データ３２１と生成された圧縮データを更新用ＤＶＤ３００に記録するデータ出力部１７０、および圧縮方式のパラメータを入力するパラメータ入力部１８０から構成される。なお、このデータ圧縮装置１００は、記憶部であるデータ記録部１１０と頻度表記録部１４０、入出力部であるデータ入力部１２０、データ出力部１７０、パラメータ入力部１８０を除くベクトル変換部１３０、圧縮部１５０、符号化部１６０については、以下に詳述する機能をハードウェア、或いはプログラムによるソフトウェアどちらで構成しても良い。ソフトウェア処理の場合、データ圧縮装置１００は、プログラムを実行する処理部としての中央処理部（ＣＰＵ）をその内部に設置することは言うまでもない。なお、次に説明するデータ伸張装置２００についても同様である。
【００２１】
データ伸張装置２００は、更新用ＤＶＤ３００から制御データ３２１と圧縮データを読み込み、制御データ３２１はデータ出力部２６０へ、圧縮データは復号化部２２０へそれぞれ出力するデータ入力部２１０、読み込まれた圧縮データをもとに４個の出現率を復号する復号化部２２０、復号された４個の出現率をもとに頻度表記録部２４０を参照してベクトルデータ４バイトを取得し、頻度表記録部２４０を更新する伸張部２３０、ベクトルデータ４バイトの各々の桁毎に出現頻度を記録する頻度表記録部２４０、ベクトルデータ４バイトを座標データ３２２に変換するベクトル逆変換部２５０、制御データ３２１および座標データ３２２からなる更新データを出力するデータ出力部２６０、出力された更新データを記録しているデータ記録部２７０、および伸張方式のパラメータを設定するパラメータ設定部２８０から構成される。
【００２２】
更新用ＤＶＤ３００は、一般のＤＶＤであり、前記の更新データが記録されている。なお、本実施例においてデータ圧縮装置とデータ伸張装置間で更新データを伝送する手段はＤＶＤに限るものではなく、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）に代表されるネットワーク通信技術や、例えば、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）に代表されるバス通信技術等を用いても構わない。
【００２３】
図２は、本実施例のシステムの動作説明を行うための、地図の例を示したものである。図に示す地図３１０には、黒丸で示す５つの交差点Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５と、線分で示す道路が記載されている。また、各交差点のＸＹ座標は（２０２３、１０１２）、（２５４５、１９４７）、（２９８７、２９９８）、（３４１５、１７０３）、（３８７２、２７６７）である。
【００２４】
図３は、本実施例の地図データ更新システムが扱う、更新データ３２０の構成を示したものである。更新データ３２０は、制御データ３２１および座標データ３２２から構成される。座標データ３２２は、図２に示したような交差点等のノードの座標を記載するものであり、Ｘ座標３２３、Ｙ座標３２４の列からなる。制御データ３２１は、座標以外のデータ、すなわちノード間の接続や、交通規制情報等を記録している。なお、制御データ３２１は、本実施例の圧縮対象データではないため説明を省略する。
【００２５】
以下、データ圧縮、伸張装置におけるデータ圧縮および伸張処理の手順に従って説明する。なお、以降の説明では次の関数を使用する。まず、関数「ＲＯＴＬ」は、第一引数の値を、第二引数が示すビット数だけ左シフトするシフト演算関数を示す。関数「ＲＯＴＲ」は、第一引数の値を、第二引数が示すビット数だけ右シフトするシフト演算関数を示す。関数「ＡＮＤ」は、二つの引数の論理積演算を示す。関数「ＯＲ」は、二つの引数の論理和演算を示す。また、説明の便宜上、データの値はＢＣＤ（Ｂｉｎａｒｙ−Ｃｏｄｅｄ  Ｄｅｃｉｍａｌ、二進化十進コード）によって示すが、一般の１６進数や１０進数でも構わない。
【００２６】
図４は、データ入力部１２０から入力される座標データを、ベクトル変換部１３０において４バイトのベクトルデータに変換する処理のフローチャートを示したものである。なお、この処理の例を図５に記載する。図５は、座標データの並びに応じた３つの例を示したものであり、上から、座標データがＰ１、Ｐ２、Ｐ３の順に並んでいる例（直線）、Ｐ１、Ｐ２、Ｐ４の順に並んでいる例（右折１）、Ｐ２、Ｐ３、Ｐ５の順に並んでいる例（右折２）である。
【００２７】
図４を用いて、ベクトル変換部１３０の処理を説明する。まず、ＸＹ座標データ１組に対して、直前に入力されたＸＹ座標データとの差分ｄＸおよびｄＹを計算する（ステップＳ１３１）。なお、ステップ１３１におけるＰｒｅｖＸおよびＰｒｅｖＹは、直前に入力された座標を記録している変数である。次に、ｎ＝３からｎ＝０まで、合計４回の繰り返し処理を行う（ステップＳ１３２およびステップＳ１３５、Ｓ１３６）。この繰り返し処理の内部では、まずｄＸおよびｄＹの下位４ビットを組み合わせて、８ビットのデータを作成してＶ［ｎ］に格納する（ステップＳ１３３）。次に、ｄＸおよびｄＹを各々４ビットずつ右シフトし、結果をｄＸおよびｄＹに格納する（ステップＳ１３４）。この処理を４回繰り返したのち、入力されたＸ座標、Ｙ座標をそれぞれＰｒｅｖＸ、ＰｒｅｖＹに格納して終了する（ステップＳ１３７）。
【００２８】
以上の処理の例を、図５を用いて説明する。座標データがＰ１、Ｐ２、Ｐ３と並んでいるとき、まずＰ２とＰ１の差分を計算する。この結果、ｄＸは０５２２、ｄＹは０９３５となる。計算されたｄＸ、ｄＹを、４ビット単位で分割し、４ビットずつ組み合わせることにより、４つの１バイトデータからなる４バイトのデータ００、５９、２３、２５が生成される。次に、Ｐ３とＰ２の差分を計算し、４ビット単位で組み合わせることにより、４バイトのデータ００、５９、４５、２１が生成される。座標データがＰ１、Ｐ２、Ｐ４と並んでいる場合の例、およびＰ２、Ｐ３、Ｐ５と並んでいる場合の例も同様である。
【００２９】
以上の変換の結果、直線の場合は、Ｐ２−Ｐ１およびＰ３−Ｐ２のどちらの結果も、生成される４バイトデータの１バイト目は００となり、２バイト目は５９となる。また、右折の場合は、Ｐ４−Ｐ２およびＰ５−Ｐ３のどちらの結果も、生成される４バイトデータの１バイト目は０９となり、２バイト目は８２となる。この例は、生成される４バイトデータの各桁において、データの出現率に偏りがあることを示している。すなわち、適当な圧縮技術により、入力データの出現率の偏りを利用してデータを圧縮することが可能となる。
【００３０】
図６および図７は、本実施例における圧縮部１５０および符号化部１６０による圧縮処理の一具体例を示したものである。なお、図６および図７に記載する圧縮処理は、適応型算術符号と呼ばれる公知の圧縮技術であるが、本実施例は、特定の圧縮技術に依存するものではなく、任意の圧縮技術を利用して構わない。ただ、図５に示すような都市部の道路地図データのように、入力データの出現率に偏りがある場合は、適応型算術符号の圧縮効率は向上する。図６および図７に示す適応型算術符号は、入力データ列を、０から１の間の特定区間に１対１に関連付け、この関連付けられた区間内の特定の値を、入力データに対する圧縮データとして扱う方式である。以下、この処理の概要を説明する。
【００３１】
まず、図６は、１バイトの入力値を与えられた時の、図１の圧縮部１５０の処理の概念図を示したものである。圧縮部１５０は、頻度表記録部１４０に記録されている出現頻度表１４１を参照して、入力値に対応する確率区間を検索する（ステップＳ１５１）。たとえば、入力値が５８である場合、５８に対応する確率区間は０．２１以上０．６４未満である。確率区間を検索した後、出現頻度表１４１を更新し、入力値５８の出現率を上げる（ステップＳ１５２）。ステップＳ１５１において検索された確率区間は、圧縮部１５０から符号化部１６０へ入力される。
【００３２】
図７は、符号化部１６０への入力データ列が５８、５８、８２、５９、５９であるときの、適応型算術符号による符号化部１６０の処理の概念図を示したものである。まず、最初の入力である５８に対して、確率区間０．２１以上０．６４未満が選択される。そして、次の入力である５８に対して、同区間内において、確率区間０．２１以上０．６４未満（なお実際は、この確率区間は、上述した図６における修正ステップＳ１５２により少し拡大しているが、便宜上同一区間として説明する）が選択される。すなわち、０．３００３以上０．４８５２未満となる。このように符号化処理を繰り返すことによって、最後のデータである５９が入力された際の確率区間が０．４１７３２５以上０．４１７３２７未満となった場合、この区間内の特定の値、例えば０．４１７３２５を圧縮データとする。
【００３３】
このようにして符号化部１６０で生成された圧縮データは、制御データ３２１と合わせて、データ出力部１７０により更新用ＤＶＤ３００に記録される。
【００３４】
以上が、データ圧縮装置１００による、更新用ＤＶＤ３００の作成処理である。次に、データ伸張装置２００による、更新用ＤＶＤ３００に格納されている圧縮データの伸張処理を説明する。
【００３５】
図１のデータ伸張装置２００では、まず、データ入力部２１０が更新用ＤＶＤ３００に格納されている制御データ３２１および圧縮データを読み込み、制御データ３２１はデータ出力部２６０へ、圧縮データは復号化部２２０へ出力する。復号化部２２０および伸張部２３０における復号処理は、図７に記載した符号化処理と同様である。すなわち、圧縮データが０．４１７３２５である場合、この値は０．２１以上０．６４未満であるため、頻度表記録部２４０を参照することにより最初のデータが５８であることがわかる。同様に、確率区間を計算していくことにより、データ圧縮装置１００で圧縮処理したデータ列５８、５８、８２、５９、５９を復号できる。このようにして復号されたデータ列は、ベクトル逆変換部２５０により、ＸＹ座標データに変換される。
【００３６】
図８は、ベクトル逆変換部２５０の処理を示すフローチャートである。ベクトル逆変換部２５０は、まず、変数ｄＸおよびｄＹを初期化する（ステップＳ２５１）。次に、ｎ＝０からｎ＝３までの４回の繰り返し処理を行う（ステップＳ２５２、Ｓ２５５、Ｓ２５６）。繰り返し処理の内部では、まず、伸張部２３０の出力である８ビットデータＶ［ｎ］の上位４ビットをｄＸの下位４ビットに、Ｖ［ｎ］の下位４ビットをｄＹの下位４ビットにセットする（ステップＳ２５３）。次に、ｄＸおよびｄＹを、それぞれ４ビットずつ左へシフトする（ステップＳ２５４）。４回の繰り返し処理が終わったのち、得られたｄＸおよびｄＹを、直前のＸＹ座標であるＰｒｅｖＸおよびＰｒｅｖＹに加算して、ＸＹ座標を取得する（ステップＳ２５７）。最後に、計算されたＸＹ座標をＰｒｅｖＸおよびＰｒｅｖＹに記録して終了する（ステップＳ２５８）。
【００３７】
以上の処理を行うことにより、圧縮データは、元の座標データ３２２に伸張される。データ出力部２６０は、伸張された座標データ３２２、および制御データ３２１を、データ記録部２７０に記録する。
【００３８】
なお、以上の処理において、データの圧縮率をより高めるため、ベクトルデータ圧縮装置１００におけるベクトル変換部１３０、圧縮部１５０の動作、およびベクトルデータ伸張装置２００におけるベクトル逆変換部２５０、伸張部２３０の動作を設定可能とする構成にしても構わない。この実現手段の例を以下に示す。
【００３９】
図９は、本実施例のベクトルデータ圧縮装置１００におけるパラメータ入力部１８０が表示するパラメータ入力画面１８１の例を示したものである。パラメータ入力画面１８１には、データフォーマット入力欄１８２、ベクトルデータフォーマット入力欄１８３、圧縮レベル入力欄１８４が存在する。データフォーマット入力欄１８２には、入力データをいかなる桁数で分割するかを指定する。図９に示す例では、設定情報の先頭の文字列は「Ｘ１：４」で始まっており、これは「４ビットをＸ１という変数で扱う」という意味である。続く文字列も同様の意味である。次の、ベクトルデータフォーマット入力欄１８３には、データフォーマット入力欄１８２で指定されたフォーマットをどのように変換するかを指定する。図９に示す例では、「Ｘ１，Ｙ１，・・・」となっており、これは「変数Ｘ１、Ｙ１、・・・の順に並び替える」という意味である。最後の圧縮レベル入力欄１８４には、圧縮部１５０および伸張部２３０が参照する圧縮レベルを指定する。図９に示す例は、４個の圧縮部１５０および伸張部２３０における圧縮レベルを、それぞれ「６，６，３，１」とすることを意味する。
【００４０】
以上のように設定した後、ＯＫボタン１８５を押下することにより、設定情報がベクトル変換部１３０、および圧縮部１５０に設定され、データ出力部１７０を介して、制御データ３２１および座標データ３２２とともに更新用ＤＶＤ３００に記録される。設定情報が更新用ＤＶＤ３００に記録されている場合、データ伸張装置２００では、データ入力部２１０が設定情報を読み込み、パラメータ設定部２８０に出力する。パラメータ設定部２８０では、取得した設定情報をベクトル逆変換部２５０および伸張部２３０に設定する。この設定を行った後に、データ入力部２１０は制御データ３２１および座標データ３２２を読み込み、データ伸張処理を行う。
【００４１】
これらの処理によって、データの圧縮率をより高めることが可能となる。上述したベクトルデータ圧縮装置およびベクトルデータ伸張装置を提供することにより、更新データを交差点・直線等の地図の特徴を踏まえて圧縮し、この圧縮データを含む更新データによってデータ伸張装置２００内のデータを更新することが可能となる。
【００４２】
以上、図面を用いて詳述してきた本発明は、交差点等が頻出する都市部の地図データ等のベクトルデータにおいて、高い圧縮率で圧縮することができ、カーナビにおける地図更新、各種ＧＩＳ（Ｇｅｏｇｒａｐｈｉｃ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｙｓｔｅｍ、地理情報システム）、ネットワーク通信による地図データの配信等に利用可能である。なお、本発明は、地図のベクトルデータに限るものではなく、三次元ポリゴンデータ等の圧縮にも応用できる。
【００４３】
尚、平面（２次元）地図であれば、Ｘ方向ベクトルおよびＹ方向ベクトルの代わりに、Ｌ方向ベクトルとΘ回転ベクトルを用いてもよい。また、３次元地図であれば、Ｘ方向ベクトル、Ｙ方向ベクトルに加え、Ｚ方向ベクトルを用いてもよい。
【図面の簡単な説明】
【００４４】
【図１】第一の実施例の地図データ更新システムの全体構成図。
【図２】第一の実施例の交差点を含む地図データの例を示す図。
【図３】第一の実施例の更新用データの一例を示す構成図。
【図４】第一の実施例のベクトル符号化部の処理を示すフローチャート図。
【図５】第一の実施例のべクトル符号化部の処理の概要を示す説明図。
【図６】第一の実施例の算術符号による圧縮および伸張の処理を示す説明図。
【図７】第一の実施例の算術符号による符号化を示す説明図。
【図８】第一の実施例のベクトル逆変換部の処理を示すフローチャート図。
【図９】第一の実施例のパラメータ入力画面の例を示す図。
【符号の説明】
【００４５】
１００…データ圧縮装置、１３０…ベクトル変換部、１５０…圧縮部、１６０…符号化部、２００…データ伸張装置、２２０…復号化部、２３０…伸張部、２５０…ベクトル逆変換部、３００…更新用ＤＶＤ。
【図１】
2009055308.tif 000003
【図２】
2009055308.tif 000004
【図３】
2009055308.tif 000005
【図４】
2009055308.tif 000006
【図５】
2009055308.tif 000007
【図６】
2009055308.tif 000008
【図７】
2009055308.tif 000009
【図８】
2009055308.tif 000010
【図９】
2009055308.tif 000011