(57)【要約】【課題】  圧縮符号化の技術を利用してデジタル地図の位置情報を少ないデータ量で符号化する方法を提供する。【解決手段】  デジタル地図上の形状ベクトルを表すデータを符号化する符号化方法において、前記形状ベクトルを表すノード列や形状を表す位置情報を、算術加工を施して統計的な偏りを持つデータで表し、統計的な偏りを持たせたデータを符号化してデータ量を削減する。デジタル地図のベクトル形状を伝達する場合の伝送データ量を大幅に減らすことができる。【選択図】図１
2004354396.tif 000002
【特許請求の範囲】
【請求項１】
デジタル地図上の形状ベクトルを表すデータを符号化する符号化方法において、
前記形状ベクトルを表すノード列の個々のノードの位置情報に算術加工を施して、前記位置情報を統計的に偏りを持つデータに変換し、前記データを符号化してデータ量を削減することを特徴とする形状ベクトルデータの符号化方法。
【請求項２】
前記ノードの位置情報を、隣接するノードからの距離、及び、隣接するノードから延びる直線の角度の情報で表現し、前記距離または角度を統計的に偏りを持つデータで表して、前記データを符号化することを特徴とする請求項１に記載の形状ベクトルデータの符号化方法。
【請求項３】
前記ノードの位置情報を統計予測値との差分データに変換し、前記差分データを符号化することを特徴とする請求項１または２に記載の形状ベクトルデータの符号化方法。
【請求項４】
前記角度の情報を偏角で表し、前記偏角を符号化することを特徴とする請求項２または３に記載の形状ベクトルデータの符号化方法。
【請求項５】
前記角度の情報を偏角の統計予測値に対する差分で表し、前記差分を符号化することを特徴とする請求項２または３に記載の形状ベクトルデータの符号化方法。
【請求項６】
前記距離の情報を距離の統計予測値に対する差分で表し、前記差分を符号化することを特徴とする請求項２または３に記載の形状ベクトルデータの符号化方法。
【請求項７】
前記形状ベクトルの所定区間内で、前記ノードの位置情報のうち、少なくとも１つの要素が一定の値を取るように、前記ノードをリサンプルすることを特徴とする請求項１から６のいずれかに記載の形状ベクトルデータの符号化方法。
【請求項８】
隣接するノードからの距離が等間隔となる位置に前記ノードをリサンプルし、前記ノードの位置情報を角度情報のみで表現することを特徴とする請求項７に記載の形状ベクトルデータの符号化方法。
【請求項９】
隣接するノードから延びる直線の偏角が一定の角度を取る位置に前記ノードをリサンプルし、前記ノードの位置情報を距離情報のみで表現することを特徴とする請求項７に記載の形状ベクトルデータの符号化方法。
【請求項１０】
前記形状ベクトルを複数の区間に分割し、各区間ごとに前記一定の値を設定することを特徴とする請求項７から９のいずれかに記載の形状ベクトルの符号化方法。
【請求項１１】
前記各区間ごとに一定のリサンプル区間長を設定し、前記リサンプル区間長の間隔で前記ノードをリサンプルすることを特徴とする請求項１０に記載の形状ベクトルの符号化方法。
【請求項１２】
デジタル地図の前記形状ベクトルに含まれるノードまたは補間点の位置情報に算術加工を施して、前記位置情報を統計的に偏りを持つデータに変換することを特徴とする請求項１から６のいずれかに記載の形状ベクトルの符号化方法。
【請求項１３】
前記形状ベクトルを近似するスプライン関数の節点列の情報に算術加工を施して、統計的に偏りを持つデータに変換することを特徴とする請求項１に記載の形状ベクトルの符号化方法。
【請求項１４】
前記データを可変長符号化してデータ量を削減することを特徴とする請求項１から１３のいずれかに記載の形状ベクトルデータの符号化方法。
【請求項１５】
前記データをランレングス符号化してデータ量を削減することを特徴とする請求項１から１４のいずれかに記載の形状ベクトルデータの符号化方法。
【請求項１６】
前記リサンプル区間長を、前記形状ベクトルの曲率の大小に応じて設定することを特徴とする請求項１１に記載の形状ベクトルデータの符号化方法。
【請求項１７】
前記形状ベクトルの許容誤差を算出し、前記許容誤差を超えない範囲で、前記データを符号化したときの量子化桁数を減らすことを特徴とする請求項１に記載の形状ベクトルデータの符号化方法。
【請求項１８】
前記形状ベクトルを円弧及び直線で近似し、近似した円弧または直線の区間ごとに前記リサンプル区間長を設定することを特徴とする請求項１６に記載の形状ベクトルデータの符号化方法。
【請求項１９】
送信側が、デジタル地図上の形状ベクトルを表す形状データを送信し、受信側が、受信した形状データを基にマップマッチングを行って自己のデジタル地図上での前記形状ベクトルを特定するデジタル地図の位置情報伝達方法において、
送信側は、請求項１から１８のいずれかに記載の符号化方法で符号化した形状ベクトルデータを送信し、受信側は、受信したデータを復号して形状を再現し、再現した形状に対応する形状ベクトルをマップマッチングで特定することを特徴とする位置情報伝達方法。
【請求項２０】
送信側は、符号化に用いた符号表を、送信するデータに含めて送信し、受信側は、受信した前記符号表を用いて形状を再現することを特徴とする請求項１９に記載の位置情報伝送方法。
【請求項２１】
送信側は、受信側で誤マッチングが発生しない範囲で前記リサンプル区間長を設定することを特徴とする請求項１９に記載の位置情報伝達方法。
【請求項２２】
送信側は、受信側で誤マッチングが発生しない範囲で前記量子化桁数を減らすことを特徴とする請求項１９に記載の位置情報伝達方法。
【請求項２３】
送信側は、受信側で誤マッチングが発生しない範囲で前記形状ベクトルを円弧及び直線で近似することを特徴とする請求項１９に記載の位置情報伝達方法。
【請求項２４】
送信側は、符号化に用いる符号表を予め作成して保持し、前記符号表を用いて前記形状ベクトルの符号化を行うことを特徴とする請求項１９に記載の位置情報伝達方法。
【請求項２５】
送信側は、前記符号表を用いて符号化した前記形状ベクトルのデータを予め保持し、送信するデータを、前記保持するデータの中から選択することを特徴とする請求項２４に記載の位置情報伝達方法。
【請求項２６】
送信側が、符号化した前記形状ベクトルデータとして、デジタル地図上のポリゴンの形状を表すデータを送信することを特徴とする請求項１９に記載の位置情報伝達方法。
【請求項２７】
受信側に、マップマッチングで形状を特定するためのデジタル地図上の形状ベクトルを表す形状データを送信する送信装置において、
デジタル地図上の形状ベクトルを表すノード列の個々のノードの位置情報に算術加工を施して、前記位置情報を統計的に偏りを持つデータに変換し、前記データの出現分布に基づいて前記データの符号化に用いる符号表を生成する符号表算出手段と、
受信側に伝達する形状ベクトルの個々のノードの位置情報を、前記符号表を用いて符号化し、受信側に送る形状データを生成する位置情報変換手段とを備えることを特徴とする送信装置。
【請求項２８】
受信側に、マップマッチングで形状を特定するためのデジタル地図上の形状ベクトルを表す形状データを送信する送信装置において、
受信側に伝達する形状ベクトルの個々のノードの位置情報を、他の装置で生成された符号表を用いて符号化し、受信側に送る形状データを生成する位置情報変換手段を備えることを特徴とする送信装置。
【請求項２９】
送信側からデジタル地図上の形状ベクトルを表す形状データを受信し、マップマッチングを行って自己のデジタル地図上で前記形状ベクトルを特定する受信装置において、
符号化された受信データを復号化して、デジタル地図上の位置情報で表した形状データを再現する符号データ復号化手段と、
再現した前記形状データを用いてマップマッチングを行い、自己のデジタル地
図上での前記形状ベクトルを特定するマップマッチング手段とを備えることを特徴とする受信装置。
【請求項３０】
受信側に、マップマッチングで形状を特定するためのデジタル地図上の形状ベクトルを表す形状データを送信する送信装置のプログラムであって、
コンピュータに、
デジタル地図上の形状ベクトルを固定長でリサンプルしてノードを設定する手順と、
前記ノードの位置データに算術加工を施して統計的に偏りを持つデータに変換する手順と、
前記統計的に偏りを持つデータの出現分布に基づいて前記データの符号化に用いる符号表を生成する手順とを実行させるためのプログラム。
【請求項３１】
受信側に、マップマッチングで形状を特定するためのデジタル地図上の形状ベクトルを表す形状データを送信する送信装置のプログラムであって、
コンピュータに、
前記形状ベクトルを固定長でリサンプルしてノードを設定する手順と、
前記ノードの位置データに算術加工を施して統計的に偏りを持つデータに変換する手順と、
前記統計的に偏りを持つデータを符号表を参照して符号表現に変換する手順とを実行させるためのプログラム。
【請求項３２】
送信側からデジタル地図上の形状ベクトルを表す形状データを受信し、マップマッチングを行って自己のデジタル地図上で前記形状ベクトルを特定する受信装置のプログラムであって、
コンピュータに、
符号化された受信データを符号表を参照して復号化する手順と、
復号化したデータからデジタル地図上の位置情報で表した形状データを再現する手順と、
再現した前記形状データを用いてマップマッチングを行い自己のデジタル地図上での前記形状ベクトルを特定する手順とを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル地図の位置情報を伝達する方法と、伝達するデータ量を圧縮して符号化する符号化方法と、その装置に関し、特に、圧縮符号化の技術を用いてデータ量を削減するものである。
【背景技術】
【０００２】
従来、デジタル地図データベースを搭載するナビゲーション車載機などに交通情報を提供する場合には、送り手側と受け手側とが制作元の異なるデジタル地図を保持しているときでもデジタル地図上の位置が正確に伝わるように、道路をリンク番号で、また、その道路に存在する交差点などのノードをノード番号で特定し、そのノードから何メートル、と云う表現方法で道路上の地点を伝えている。しかし、道路網に定義したノード番号やリンク番号は、道路の新設や変更に伴って新しい番号に付け替える必要があり、また、それに応じて、制作元の各社のデジタル地図データも更新しなければならないため、ノード番号やリンク番号を用いる方式は、そのメンテナンスに多大な社会的コストが掛かることになる。
【０００３】
こうした点を改善するため、本発明の発明者等は、特願平１１−２１４０６８号や特願平１１−２４２１６６号で、次のようなデジタル地図の位置情報伝達方法を提案している。この方法では、情報提供側は、渋滞や事故などの事象が発生した道路位置を伝えるとき、その事象位置を含む所定長の道路区間の道路形状を、その道路上に配列するノード及び補間点（道路の曲線を近似する折れ線の頂点。この明細書では、特に断らない限り、補間点を含めて「ノード」と呼ぶことにする）の座標列から成る「道路形状データ」と、この道路形状データで表した道路区間内の相対的な位置により事象位置を表す「事象位置データ」とを受信側に伝達し、これらの情報を受信した側では、道路形状データを用いてマップマッチングを行い、自己のデジタル地図上での道路区間を特定し、事象位置データを用いてこの道路区間内の事象発生位置を特定する。  図３６（ａ）には「道路形状データ」を、また、図３６（ｂ）には「事象位置データ」を例示している。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、この「道路形状データ」と「事象位置データ」とを用いてデジタル地図の位置情報を伝達する方法では、道路形状を特定する道路形状データのデータ量が多くなり、データ伝送量が増えると云う問題点がある。
【０００５】
この道路形状データのデータ量を減らす方法として、本発明の発明者等は道路形状をスプライン関数で近似する方法を特願平２００１−１２１２７号で提案しているが、この位置情報伝達方法の定着を図るためには、データ量の削減をさらに進めることが必要である。
【０００６】
本発明は、こうした課題に応えるものであり、圧縮符号化の技術を利用してデジタル地図の位置情報を少ないデータ量で伝達する位置情報伝達方法と、データ量を減らすための符号化方法と、その方法を実施する装置とを提供することを目的としている。
【課題を解決するための手段】
【０００７】
そこで、本発明では、デジタル地図上の形状ベクトルを表すデータを符号化する符号化方法において、前記形状ベクトルを表すノード列の個々のノードの位置情報に算術加工を施して、前記位置情報を統計的に偏りを持つデータに変換し、前記データを符号化してデータ量を削減している。
【０００８】
また、送信側が、デジタル地図上の形状ベクトルを表す形状データを送信し、受信側が、受信した形状データをもとにマップマッチングを行って自己のデジタル地図上での前記形状ベクトルを特定するデジタル地図の位置情報伝達方法において、送信側は、前記符号化方法で符号化した形状ベクトルデータを送信し、受信側は、受信したデータを復号して形状を再現し、再現した形状に対応する形状ベクトルをマップマッチングで特定するように構成している。
【０００９】
また、受信側にデジタル地図上の形状ベクトルを表す形状データを送信する送信装置に、デジタル地図上の形状ベクトルを表すノード列の個々のノードの位置情報に算術加工を施して、前記位置情報を統計的に偏りを持つデータに変換し、前記データの出現分布に基づいて前記データの符号化に用いる符号表を生成する符号表算出手段と、受信側に伝達する形状ベクトルの個々のノードの位置情報を、前記符号表を用いて符号化し、受信側に送る形状データを生成する位置情報変換手段とを設けている。
【００１０】
また、送信側からデジタル地図上の形状ベクトルを表す符号化したデータを受信する受信装置に、符号化された受信データを復号化し、デジタル地図上の位置情報で表した形状データを再現する符号データ復号化手段と、再現された形状データを用いてマップマッチングを行い自己のデジタル地図上での前記形状ベクトルを特定するマップマッチング手段とを設けている。
【発明の効果】
【００１１】
そのため、デジタル地図における形状ベクトルのデータ量を効率的に圧縮することができ、デジタル地図の形状ベクトルを伝達する場合の伝送データ量を大幅に減らすことができる。受信側では、受信データから形状データを復元し、マップマッチングを実施することにより、伝送された形状ベクトルを正確に特定することができる。
【発明を実施するための最良の形態】
【００１２】
（第１の実施形態）
第１の実施形態では、可変長符号化によりデータを圧縮する方法について説明する。
【００１３】
本発明におけるデジタル地図の位置情報伝達方法では、まず、道路形状を、統計的に偏りを持つ形状データで表現する。これは、形状データを圧縮符号化したときに、圧縮率が高くなるようにするためである。
【００１４】
道路形状をその道路上に配列する座標点で表す場合、図３４に示すように、各座標点（ＰJ）の位置は、隣接する座標点（ＰJ-1）からの距離と角度との２つのディメンジョンにより一意に特定することができる。この角度として、図３４では、真北（図の上方）の方位を０度とし、時計回りに０〜３６０度の範囲で大きさを指定する「絶対方位」による角度Θjを示している。このように、座標点を距離と絶対方位とを用いて表すことを全曲率関数表現と云う。
【００１５】
座標点ＰJ-1、ＰJ、ＰJ+1のｘｙ座標をそれぞれ（ｘj-1，ｙj-1）、（ｘj，ｙj）、（ｘj+1，ｙj+1）とするとき、距離Ｌj（座標点ＰJ、ＰJ+1間の距離）及び絶対角度Θj（座標点ＰJから座標点ＰJ+1に向かう直線の絶対方位）は、次式により算出することができる。
Ｌj  ＝√｛（ｘj+1−ｘj）2＋（ｙj+1−ｙj）2｝
Θj  ＝tan-1｛（ｘj+1−ｘj）／（ｙj+1−ｙj）｝
【００１６】
ところで、道路形状の上に、隣接する座標点からの距離が一定（＝Ｌ）となるように新たな座標点を設定し直した（リサンプルした）場合には、共通するＬの情報の他に、それらの個々の座標点に関して、角度Θjの情報（即ち、１ディメンジョンの情報）を伝えるだけで、受信側では座標点の位置を特定することが可能になり、伝送データ量の削減を図ることができる。
【００１７】
図３５（ａ）は、道路上の隣接する座標点からの距離が一定（＝Ｌ）となる位置に座標点をリサンプルした場合の各座標点（ＰJ）における絶対方位Θjを示している。各座標点を絶対方位Θjで表した場合には、図３５（ａ’）に図示するように、各座標点を示す角度情報Θjの発生頻度に統計的な偏りは現れない。
【００１８】
しかし、各座標点の角度は、図３５（ｂ）に示すように、絶対方位の変位差、即ち、「偏角」θjによって表すこともできる。この偏角θjは、
θj＝Θj−Θj-1
として算出される。各座標点を偏角θjで表した場合、直線的な道路が多い地域では、図３５（ｂ’）に図示するように、各座標点を示す角度情報θjの発生頻度は、θ＝０°に極大が現れる。
【００１９】
また、各座標点の角度は、図３５（ｃ）に示すように、偏角θjと偏角統計予測値Ｓj（偏角で表した予測値）との差分Δθjにより表すこともできる。偏角統計予測値Ｓjとは、着目する座標点ＰJの偏角θjを、それ以前のＰJ-1までの座標点の偏角を用いて推定した値である。例えば、偏角統計予測値Ｓjは、
Ｓj＝θj-1
と定義したり、
Ｓj＝（θj-1＋θj-2）／２
と定義することができる。また、過去ｎ個の座標点の偏角の加重平均をＳjとして定義しても良い。偏角の予測値差分Δθjは、
Δθj＝θj−Ｓj
として算出される。
【００２０】
道路形状は、直線や緩やかに曲がる曲線が殆どであるため、座標点間の距離Ｌを一定に設定した場合、偏角の予測値差分Δθjは０°付近に集中し、図３５（ｃ’）に図示するように、各座標点を示す角度情報Δθjの発生頻度は、θ＝０°を中心に強い偏りを見せる。
【００２１】
そこで、ここでは、統計的に偏りを持つ形状データを得るために、図１に示すように、道路形状（元の形状）を一定の距離を持つリサンプル区間長Ｌで等間隔にサンプリングし、サンプリング点（ノード）ＰJの位置データを、偏角θjの予測値差分Δθj（＝θj−Ｓj）で表すことにする。なお、ここで言う距離は、実世界に展開したときの実際の距離でも良いし、予め決めた正規化座標での単位で表現された長さでも構わない。
【００２２】
いま、偏角統計予測値Ｓjを、
Ｓj＝（θj-1＋θj-2）／２
と定義することにする。道路形状は殆どの場合なだらかに曲がるため、
θj≒（θj-1＋θj-2）／２＝Ｓj
となり、Δθjは０を中心に極狭い範囲に分布すると考えられる。
【００２３】
このΔθjは、理論上、−３６０°〜＋３６０°の値を取り得る。そのためΔθjを１°分解能で表現するには、正負を表す１ｂｉｔと３６０の数値を表す９ｂｉｔとを加えた１０ｂｉｔが必要であるが、±０°近辺の角度を１０ｂｉｔより小さい値で符号化し、±０°から離れたところの角度に１０ｂｉｔより大きな値を割り振ることにより、Δθjの符号化に使用する平均ｂｉｔ数を１０ｂｉｔより少なくすることができ、形状データをトータルとして短いデータ量で表現することが可能になる。
【００２４】
図２は、このΔθに対して符号化の符号を割り当てた符号表を例示している。Δθ＝０の場合は０に符号化する。Δθ＝＋１の場合は、符号１００に＋を表す付加ビット０を加えて１０００と符号化する。Δθ＝−１の場合は、符号１００に−を表す付加ビット１を加えて１００１と符号化する。
【００２５】
図１により可変長符号化を説明する。ノード数が６（＝始端＋５ノード）の場合、通常の符号化では、初期値角度（１０ｂｉｔ）の他に５×１０ｂｉｔ＝５０ｂｉｔの固定長のデータ量が必要である。これに対して、図２の符号表を用いた符号化の場合では、Δθjの値として０が３回、±２°以内が２回あったとすると、初期値角度（１０ｂｉｔ）の他に３×１ｂｉｔ＋２×４ｂｉｔ＝１１ｂｉｔで表現できる。このデータが“０，０，＋１，−２，０”であったとすると、符号化により“００１０００１０１１０”と表現される。
【００２６】
受信側は、形状データとともに送られて来る（あるいは予め保持している）符号表を参照し、順番にΔθの値を当てはめることによりΔθjの各々の値を得ることができる。そして、初期値から順次積算していくことにより、各座標点における偏角θjの値を一意に確定できる。
【００２７】
この符号表の作成は、各座標点ＰJでのΔθjの角度を算出し、その角度の発生頻度を調べ、発生頻度に応じて良く知られたハフマン木等を用いて構築する。
【００２８】
このように、形状データに算術加工を施して統計的な偏りを持たせた後、可変長符号化することにより、形状データのデータ量を削減することができる。
【００２９】
また、ここでは、リサンプルしたノード位置を、隣接するノードの距離と偏角とで表しているが、リサンプル区間長Ｌで等間隔にサンプリングしたノード位置を相対緯度経度座標（Δｘj，Δｙj）で表現することも可能である。この場合、統計値Ｓjを例えばＳjx＝Δｘj-1，Ｓjy＝Δｙj-1と定義して、
Δｘj＝Ｓjx＋δｘj＝Δｘj-1＋δｘj
Δｙj＝Ｓjy＋δｙj＝Δｙj-1＋δｙj
と表し、δｘj及びδｙjを可変長符号化し、形状データとして伝送する。
【００３０】
（第２の実施形態）
第２の実施形態では、ランレングス法を用いてデータを圧縮する方法について説明する。
【００３１】
第１の実施形態の例において、Δθjを符号化して形状データを表す場合、直線道路や、同一曲率で曲がる道路では、“０”が連続する。このような場合、“０００００‥”と表現するよりも、“０が２０回”と表現する方がデータの圧縮率が高くなる。ここでは、こうしたランレングス符号化を行い、データを圧縮する。
【００３２】
図３は、ランレングスの符号表であり、例えば、同じ数が５回続く場合（ランレングスが５の場合）は“１０１”で表示することを定義している。図４は、図２と同じΔθの符号表である。データの並びは、例えば、ランレングス→Δθ→ランレングス→Δθ→‥と決めておく。Δθが
“0,0,0,0,0,-2,-2,0,+3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1‥”
と続くときは、ランレングス法により、
“101・0_0・1011_0・1011_0・0_0・11000_1101・0_0・1001‥”
→“10100101101011000110001101001001‥”（３２ｂｉｔ）
と表現される。
一方、ランレングス表現をしない場合は、
“000001011101101100000000000000000001001‥”（３８ｂｉｔ）となる。
【００３３】
また、図３及び図４の符号表を、特に効果的なものだけに絞り、図５のように１つの符号表に纏めることもできる。図５では、Δθ＝０の場合のみ、ランレングスを定義している。図５の符号表を用いると、
“0,0,0,0,0,-2,-2,0,+3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1‥”
は、
“100・11101・11101・0・111100・1100・11011‥”
→“10011101111010111100110011011‥”  （２９ｂｉｔ）
と表せる。
【００３４】
ちなみに、１ノード１０ｂｉｔの固定長の表現方法と比較すると、１０ｂｉｔ×２５ノード＝２５０ｂｉｔとなり、この例では２９÷２５０＝１２％に圧縮されることが分かる。
【００３５】
（第３の実施形態）
第３の実施形態では、本発明の位置情報伝達方法を実施する装置について説明する。
【００３６】
図６は、この装置の一例として、他の装置30との間で道路上の事象発生情報を交換する位置情報送受信装置を示している。この装置は、道路形状データの圧縮符号化に用いる符号表をオフラインで生成するオフライン処理部20と、オフライン処理部20で生成された符号表データを用いて交通情報を伝えるオンライン処理部10とから成り、オフライン処理部20は、デジタル地図データベース22と、過去の交通情報を記憶する記憶部21と、圧縮符号化に用いる符号表データを生成する符号表算出部23と、生成された符号表データを蓄積する符号表データベース24とを備えている。
【００３７】
一方、オンライン処理部10は、他の装置30の位置情報送信部16から圧縮符号化された「道路形状データ」と「事象位置データ」とを受信する位置情報受信部17と、圧縮符号化されているデータを解凍（復号化）する符号データ解凍部18と、デジタル地図データを蓄積するデジタル地図データベース13と、解凍された道路形状データと事象位置データとを用いてマップマッチングを行い、自己のデジタル地図上での事象位置を特定するマップマッチング部14と、地図上に事象位置を重畳して表示するデジタル地図表示部12と、発生した事象情報を入力する事象情報入力部11と、事象位置を含む対象道路区間を決定し、事象位置を対象道路区間の相対位置で表す「事象位置データ」を生成し、対象道路区間の形状データを符号表データ24を用いて圧縮符号化して「道路形状データ」を生成する位置情報変換部15と、生成された「道路形状データ」と「事象位置データ」とを他の装置30の位置情報受信部17に送信する位置情報送信部16とを備えている。
【００３８】
図７のフロー図は、この装置の動作手順を示している。オフライン処理部20では、符号表算出部23が、図７（ａ）に示すように、
ステップ１：過去の交通情報21を参照し、
ステップ２：交通情報の対象道路区間を選出する。
ステップ３：対象道路区間の形状データを固定長Ｌでリサンプルし、ノードを設定する。
【００３９】
ステップ４：ノードの位置データを全曲率関数表現に変換し、
ステップ５：統計値算出式に従い、各区間／各ノードのΔθを算出する。
ステップ６：次に、Δθの出現分布を計算する。
ステップ７：次に、同一値の連続分布を計算する。
ステップ８：Δθの出現分布及び同一値の連続分布を基に符号表を作成し、
ステップ９：完成した符号表を符号表データベース24に格納する。
【００４０】
この処理手順は、オフライン処理部20のコンピュータを符号表算出部23として機能させるためのプログラムによって規定される。
【００４１】
また、オンライン処理部10では、位置情報変換部15が、図７（ｂ）に示すように、
ステップ10：事象情報入力部11から交通情報を受信すると、
ステップ11：交通事象の発生位置を含む対象道路区間を選出する。
ステップ12：対象道路区間の形状データを固定長Ｌでリサンプルしノードを設定する。
【００４２】
ステップ13：ノードの位置データを全曲率関数表現に変換し、
ステップ14：統計値算出式に従い、各区間／各ノードのΔθを算出する。
ステップ15：前記対象道路区間を対象として作成された符号表（または前記対象道路区間に形状が近似している道路を対象として作成され符号表）の符号表データ24を参照し、形状データを符号表現に変換する。
ステップ16：対象道路区間の相対情報で表した事象位置のデータとともに符号化した対象道路区間の形状データを送信する。
【００４３】
この処理手順は、オンライン処理部10のコンピュータを位置情報変換部15として機能させるためのプログラムによって規定される。
【００４４】
図８は、送信される道路形状データ（図８（ａ））と事象位置データ（図８（ｂ））とを示している。道路形状データには、符号表データ、リサンプルした区間長Ｌのデータ、及び圧縮符号化した形状データが含まれている。
【００４５】
図９は、このデータを受信した受信側の処理手順を示している。
ステップ20：位置情報受信部17が位置情報を受信すると、
ステップ21：符号データ解凍部18は、受信データに含まれる符号表を参照して符号表現されているデータを復元し、形状データを全曲率関数に変換する。
ステップ22：次いで、緯度経度座標で表した形状データを再現する。
ステップ23：マップマッチング部14は、再現された形状と自己のデジタル地図の道路形状とのマップマッチングを実行して対象道路区間を特定し、また、事象位置データから、この対象道路区間内の交通事象発生位置を特定する。
ステップ24：デジタル地図表示部12は、地図上に交通情報を重畳表示する。
【００４６】
この処理手順は、オンライン処理部10のコンピュータを、符号データ解凍部18及びマップマッチング部14として機能させるためのプログラムによって規定される。
【００４７】
なお、ここでは、圧縮符号化に用いた符号表を送信データに含めて送信しているが、送信及び受信側が予め同じ符号表を持つことによって、送信データに符号表を含めることが不要になる。
【００４８】
また、ここでは、オンライン処理部10が圧縮符号化した形状データを得るために、オフライン処理部20で作成された符号表データ24を利用する例について説明したが、オフライン処理部20において、対象地域の各道路形状を圧縮符号化して、符号表現した各道路区間の形状データを予め保持し、オンライン処理部10は、交通事象の発生情報を取得したとき、オフライン処理部20に保持された形状データの中から、交通事象発生位置を含む道路区間の符号化された道路形状データを選択し、交通事象発生位置を前記道路区間の相対位置で表した交通情報を生成して、選択した符号化された道路形状データと、生成した交通情報とを受信側に伝送するようにしても良い。
【００４９】
この場合、オフライン処理部20は、ステップ２〜ステップ９の手順により、符号化の対象となる道路区間の形状データを固定長Ｌでリサンプルし、各ノードにおけるΔθを算出し、Δθの出現分布に基づいて符号表を作成する。次いで、作成した符号表を用いて、リサンプルした各座標点のΔθを符号表現に変換し、圧縮符号化した形状データを作成してデータベースに蓄積する。この処理を対象地域の各道路区間に対して繰り返し実施することにより、対象地域に含まれる各道路区間の圧縮符号化した形状データを保持することができる。
【００５０】
このように、オフラインで実施した道路形状に対する固定長Ｌでのリサンプル結果を、オンライン処理において利用することも可能である。
【００５１】
（第４の実施形態）
第４の実施形態では、不可逆圧縮法を導入して道路形状データを高圧縮する方法について説明する。
【００５２】
音声データや画像データの伝送では、圧縮率の向上を図るため、感覚（視覚／聴覚）上、気にならない範囲でサンプリング点を減らしたり、計測情報の量子化桁数を減らしたり、あるいは、圧縮率が高まるように計測情報を改ざんする処理が行われている。これらの処理を実施した場合、受信側では元のデータを完全に復元することはできないが、多少データが変わっても支障がない場合には、このような不可逆圧縮処理を導入することによって、データを大幅に圧縮することが可能になる。
【００５３】
本発明の位置情報伝達方法では、受信側がマップマッチングを実施して道路形状を特定するため、対象道路区間の始点や終点、及び誤マッチングが発生しやすい箇所では、正確に形状を伝える必要があるが、それ以外の箇所では、伝える形状が多少曖昧であっても、受信側では本来の位置を特定することができる。そのため、本発明の位置情報伝達方法においても、不可逆圧縮の手法を導入して伝送データの圧縮率を高めることが可能である。
【００５４】
そこで、この実施形態の圧縮方法では、次の方法でデータの圧縮率を高めている。
（１）誤マッチングが発生しない範囲で、標本化点を減らす。曲率が大きい、カーブがきつい道路では、マッチング点が道路上から外れ、誤マッチングが発生する可能性がある。そのため、図１０に示すように、曲率の大小を目安にサンプリング区間長Ｌを設定する。
（２）誤マッチングが発生しない範囲で、Δθを表現する量子化桁数を減らす。例えば、最小分解能を２°に設定し、この単位でΔθを量子化する。この場合、再現したノード位置が真値を中心に左右にブレるため、再現形状は当然いびつになる。そのため、受信側では、再現形状を平滑化する補間処理を行う。
（３）道路形状を円弧及び直線で近似する。偏角統計予測値Ｓjを基準にした差分表現で値に偏りを持たせて圧縮符号化する場合には、弧または直線で表現された、曲率が同一の道路区間では、その偏りが０に集中するため、統計的な偏りがさらに大きくなり、圧縮効率が飛躍的に上がる。従って、道路形状を円弧及び直線で近似することにより、圧縮率が飛躍的に向上する。また、ランレングス符号化による効果も上がる。
【００５５】
この（１）（２）（３）の方法は、単独で実施しても良いし、複数を組み合わせて実施しても良い。ここでは、この（１）（２）及び（３）の方法を適用して圧縮符号化を行う具体例について説明する。
【００５６】
道路形状の円弧及び直線近似は、全曲率関数で表現した道路形状を直線近似することにより行うことができる。図１のように、道路上の点ＰJを全曲率関数で表現した道路形状は、図１１に示すように、縦軸をθ（＝Σθj）、横軸をＬ（＝ΣＬi（但し、ここではＬi一定としている））とする座標系において実線の曲線として表示される。道路形状を円弧及び直線で近似することは、この曲線を点線で示す直線（θ＝ａＬ＋ｂ）で近似することである。この座標系上で傾き＝０の直線（θ＝ｂ）は、直線状の道路形状を表し、傾き≠０の直線（θ＝ａＬ＋ｂ）は円弧状の道路形状を表している。
【００５７】
この近似に際して、本発明者等が別途提案（特願平２００１−１２９６６５号、特願平２００１−１３２６１１号）している方法により、道路区間に沿って許容誤差を決定する。この方法では、許容誤差として、距離に関する誤差（距離誤差）の許容量（許容距離誤差）と、方位に関する誤差（方位誤差）の許容量（許容方位誤差）とを、道路形状に含まれる各ノードまたはリンクの単位で、次の条件を満たすように設定している。
（１）対象道路区間の始点、終点近辺では、許容距離誤差を小さく設定する。
（２）並走道路が隣接する場合は、許容距離誤差を小さく設定する。
（３）インターチェンジ入出路などの交差角度の浅い接続道路が存在する交差点周辺では、許容距離誤差を小さく設定する。
（４）許容方位誤差は、周辺道路からの距離が近い程、小さく設定する。
（５）曲率が大きい道路形状の箇所では、方位誤差の乖離が大きくなる可能性が高いため、許容方位誤差を小さく設定する。
【００５８】
また、各ノードにおける許容誤差の大きさは、対象道路区間の左右で別々に設定する。前記提案では、ノード単位で許容誤差を定量的に求める計算方法を具体的に示している。
【００５９】
道路区間に沿って許容誤差を決定すると、その許容誤差の範囲に入るように道路形状を円弧及び直線で近似し、図１２に示すように、道路形状を円弧または直線で表される各区間に分割する。
【００６０】
次に、各区間のそれぞれのリサンプル区間長を決定する。リサンプル区間長は、各区間ごとに、各区間ｊの曲率ａjに応じて次式により決定する。
Ｌj＝Ｋ×１／｜ａj｜
（Ｋは予め決めた定数）
【００６１】
また、このＬjの値は量子化しても良い。量子化によりＬjが取り得る値を、例えば、４０／８０／１６０／３２０／６４０／１２８０／２５６０／５１２０メートルの８つの値のいずれかとすると、Ｌjの値は３ｂｉｔに符号化して伝達することができる。
【００６２】
このとき、隣接する区間の間でリサンプル区間長Ｌjが変動しない方が圧縮効果を高めることができる。図１３は、リサンプル区間長の変動ふらつきを抑えるため、曲率にあまり変化が無い場合に、区間長が連続するように区間長を決定する決定手順を示している。区間の１番から順番に（ステップ30）、各区間ｊの曲率ａjからリサンプル区間長算出値Ｄjを求め（ステップ31）、隣接する区間のリサンプル区間長算出値Ｄj-1との変化率Ｈj（＝｜Ｄj−Ｄj-1｜／Ｄj）を求め（ステップ32）、また、隣接区間のリサンプル区間長Ｌj-1との比率Ｉj（＝Ｄj／
Ｌj-1）を求める（ステップ33）。そして、リサンプル区間長算出値の変化率Ｈjと予め決めた定数Ｈaとを比較し、また、隣接区間のリサンプル区間長Ｌj-1との比率Ｉjと、予め決めた値Ｉa1、Ｉa2とを比較し、率ＨjがＨa以下であり、且つ、ＩjがＩa1とＩa2との間にあるときは、リサンプル区間長Ｌjを隣接区間のリサンプル区間長Ｌj-1と同じ長さに設定する（ステップ35）。ここで、リサンプル区間長算出値Ｄjを隣接区間のリサンプル区間長Ｌj-1と比較しているのは、リサンプル区間長算出値Ｄjの変化率Ｈjが小さいためにリサンプル区間長を同じ値に設定し続けることにより、リサンプル区間長算出値Ｄjとリサンプル区間長Ｌjとの乖離が生じるのを防ぐためである。
【００６３】
ステップ34において、否であるときは、Ｄjの範囲と区間長との関係を設定した図１３の下表に基づいて、Ｄjの値から区間長Ｌjを決定する（ステップ36）。これを全ての区間について実行する（ステップ37、38）。
Ｈaは概ね０．２程度の値に、また、Ｉa1は０．７程度、Ｉa2は２．０程度の値に設定する。
【００６４】
次に、図１４に示すように、各区間ｎをリサンプル区間長Ｌnで等間隔にサンプリングしてノードＰJを求め、ＰJの偏角θjと偏角統計予測値Ｓjとの予測値差分Δθj（＝θj−Ｓj）の量子化値を算出する。ここでは、偏角統計予測値Ｓjとして、先行するノードの偏角θj-1を用いることとする（Ｓj＝θj-1）。
【００６５】
また、Δθjの量子化値は、Δθjの最小分解能をδ°（最小分解能＝δ）として、その値を求める。
【００６６】
このとき、Δθjをδの単位で設定するため、先行するノードＰJから距離Ｌnと角度情報Δθjとに基づいて再現したノードＰJ+1は元の道路形状（あるいは近似した形状）の上に位置するとは限らない。図１５に示すように、ＰJから次のノードＰJ+1を求めるとき、Δθjの量子化値の取り方によりノードＰJ+1の候補点が幾つか現れる。この候補点の中から、許容誤差の範囲内で、できるだけΔθの値が連続して０となるように次のノードＰJ+1を選出する。また、こうしたノード選出を続けることにより、選出されたノード位置と真値（元の道路形状上の点）との誤差が許容誤差の限度近くまで拡大した場合は、この誤差を縮める方向にノードを選出して行く必要があるが、この場合もΔθが連続して０となるようにノードの選出を行う。
【００６７】
図１６は、１つのノードＰJ+1に関する複数の候補点ＰJ+1（ｉ）の中から１つの候補点を選出するための手順を示している。
ステップ40：ＰJから距離Ｌn、Δθ＝δ・ｉの位置に候補点ＰJ+1（ｉ）を設定する。ここで、ｉはΔθの量子化値であり、−ｍ，‥，−１，０，１，‥，ｍから成る、０を中心とする２ｍ＋１個の正負の整数とする。
ステップ41：各候補点ＰJ+1（ｉ）から元の道路形状の最近接点までの距離Ｄi、及び、その最近接点の切片方位と候補点ＰJ+1（ｉ）の切片方位との誤差ΔΘiを算出する。
【００６８】
ステップ42：各候補点ＰJ+1（ｉ）に対する評価値εiを次式により算出する。
εi＝α・（δ・｜ｉ｜）＋β・Ｄi＋γ・｜ΔΘi｜＋Ψ
α、β、γ：予め決めた係数
Ψ：許容誤差範囲を超えた場合に課すペナルティ値
ステップ43：最も小さいεiを持つ候補点ＰJ+1（ｉ）をノードＰJ+1として採用する。
この評価値εiは、Ｄi及びΔΘiが拡大してペナルティ値Ψが加算されるまでは、ｉ＝０の場合に最小となる。従って、Δθが０となるように候補点が採用される。
【００６９】
また、区間ｎの区間長Ｄnの端数分については、以下のように処理する。
Ｌn＜Ｌn+1の時：区間ｎを距離Ｌnでリサンプルし、区間ｎの残り（端数分）                  がＬnより短くなった場合は、この端数分と区間ｎ＋１の一部とを合わせた距離がＬnとなるようにＬnで区間ｎ＋１内までをリサンプルし、区間ｎ＋１のこの点以降をＬn+1でリサンプルする。
Ｌn＞Ｌn+1の時：区間ｎを距離Ｌnでリサンプルし、区間ｎの端数分がＬnより                短くなった場合は、区間ｎのこの点から区間ｎ＋１に渡ってＬn+1でリサンプルする。  このように、短い区間長でリサンプルする分には、精度の低下を来さない。
【００７０】
なお、Δθの最小分解能δ°を大きくした場合は、角度の表現桁数は減るが、円弧の形状追随性は悪くなり、Δθ＝０となる確率が低下し、符号化圧縮効果は落ちる。逆に、δ°を小さくした場合は、角度の表現桁数は大きくなるが、円弧の形状追随性は良くなり、Δθ＝０となる確率が上がり、符号化圧縮効果も上がる。また、ランレングス圧縮効果も上がる。こうした点を考慮して、実際に使用するΔθの最小分解能δ°を決める必要がある。
【００７１】
次に、この場合のデータの符号化について説明する。該当するノードの予測値差分Δθは、Δθ＝０を中心にデータ長が短くなるように符号化する。ランレングスは、連続するデータの大部分がΔθ＝０のデータであるため、Δθ＝０のランレングスについて符号化する。
【００７２】
また、リサンプル区間長の変更点を表す区間長変更コードを設定する。この区間長変更コードには、特殊符号を割り当て、この特殊符号の直後の固定ビット（３ビット程度）で区間長を定義する。
【００７３】
また、各区間の基準点ノードの識別コードを表す基準点設定コードを設定する。基準点設定コードには特殊符号を割り当て、この特殊符号の直後の固定ビット（６ビット等）を基準ノード番号とし、この基準ノード番号の後に出現した座標を基準ノードと定義する（付加ビットなしで、予めノード番号初期値を定めておき、このコードを発見する都度、＋１するノード番号体系でも良い）。また、データの終わりを表すＥＯＤ（End of Data）コードとして特殊符号を割り当てる。この符号を以て形状データ列表現の終わりとする。図１７には、この符号化に用いる符号表を例示している。
【００７４】
また、図１８（ａ）には、オフラインでこの符号表を作成するまでの手順を示し、図１８（ｂ）には、符号表を用いてオンラインで交通情報を送信するまでの手順を示している。図１８（ａ）において、
ステップ50：過去の交通情報を参照し、
ステップ51：交通情報の対象道路区間を選出する。
ステップ52：対象道路区間に沿って許容誤差範囲を算出する。
【００７５】
ステップ53：対象道路区間のノードを全曲率関数表現に変換し、
ステップ54：対象道路区間の形状ベクトルを円弧及び直線に近似する。
ステップ55：円弧または直線に近似した各区間ｎのリサンプル長Ｌnを決定する。
ステップ56：対象道路区間の形状データをＬｎで量子化リサンプルし、ノードを設定する。
ステップ57：統計値算出式に従い、各区間／各ノードのΔθを算出する。
ステップ58：Δθの出現分布を計算する。
ステップ59：同一値の連続分布を計算する。
ステップ60：Δθの出現分布及び同一値の連続分布を基に符号表を作成し、
ステップ61：完成した符号表を符号表データベース24に格納する。
【００７６】
また、図１８（ｂ）のオンライン処理は次のようになる。
ステップ62：事象情報入力部11から交通情報を受信すると、
ステップ63：交通事象の発生位置を含む対象道路区間を選出する。
ステップ64：対象道路区間に沿って許容誤差範囲を算出する。
ステップ65：対象道路区間のノードを全曲率関数表現に変換し、
ステップ66：対象道路区間の形状ベクトルを円弧及び直線に近似する。
ステップ67：円弧または直線に近似した各区間ｎのリサンプル長Ｌnを決定する。
【００７７】
ステップ68：対象道路区間の形状データをＬｎで量子化リサンプルし、ノードを設定する。
ステップ69：統計値算出式に従い、各区間／各ノードのΔθを算出する。
ステップ70：符号表を参照し、形状データを符号表現に変換する。
ステップ71：交通情報とともに符号化した対象道路区間の形状データを送信する。
【００７８】
なお、ここでは、オンライン処理において、オフライン処理で作成した符号表データのみを利用する例について説明したが、第３の実施形態で説明したように、オフライン処理により、対象地域の各道路形状を符号表現した各道路区間の形状データを予め生成して蓄積し、オンライン処理では、交通事象の発生情報が入力すると、オフライン処理で生成した形状データの中から、交通事象発生位置を含む道路区間の符号化された道路形状データを選択し、交通事象の発生位置を前記道路区間の相対位置で表した交通情報を生成して、選択した符号化された道路形状データと、生成した交通情報とを受信側に伝送するようにしても良い。このように、オフラインで実施した道路形状に対する固定長Ｌでのリサンプル結果を、オンライン処理においても利用することができる。
【００７９】
図１９は、送信される道路形状データを示している。このデータには、符号表データ及び符号化された形状データを含み、符号化された形状データとしてΔθ、各区間の基準ノード、サンプル区間長などのデータを含んでいる。
【００８０】
図２０は、送受信間で交換されるデータを模式的に示している。送信側では、図２０（ａ）に示すように、道路形状を表すために量子化リサンプル後のノード位置を算出し、図２０（ｂ）に示すように、このノード位置を表すデータが受信側に送信される。受信側では、図２０（ｃ）に示すように、受信データを平滑化して形状を再現する。この場合、Ｂスプライン（ベジエスプライン／ベジエ曲線等の補間曲線でも可）等での補間または平滑化関数による平滑化を行う。また、生成した各補間点の切片方位も平均的に配分する。
【００８１】
図２１は、受信側の手順を示している。
ステップ80：位置情報を受信すると、
ステップ81：符号表を参照し、符号表現の形状データを全曲率関数に変換する。
ステップ82：次いで、緯度経度座標に変換し、平滑化・補間処理を行い、形状データを再現する。
ステップ83：基準ノード位置を取得し、
ステップ84：マップマッチングを行い、対象道路区間を特定し、
ステップ85：交通情報を再現する。
【００８２】
このように、この実施形態で説明した不可逆圧縮の方法を用いて形状データを高圧縮することにより伝送データ量を大幅に削減することができる。
【００８３】
なお、全曲率関数表現した形状データの円弧・直線近似は、ここで説明したように事前に形状を近似する以外に、量子化リサンプルと同時に行うことも可能である。
【００８４】
また、ここで説明したリサンプル区間長の決定ロジックや量子化リサンプルの決定手順は、形状データを円弧近似しない場合にも適用できる。
【００８５】
（第５の実施形態）
第５の実施形態では、座標点のリサンプルを行わずに、道路形状データを符号化する方法について説明する。
【００８６】
先に図３４を用いて説明したように、道路上に配列する座標点（ＰJ）は、隣接する座標点（ＰJ-1）からの距離と角度との２つのディメンジョンにより一意に特定することができる。第１〜第４の実施形態では、この内、距離が一定となるように座標点位置をリサンプルし、角度のみを符号化して伝送データ量の削減を図っている。しかし、この場合、リサンプルの処理が必要になる。
【００８７】
これに対して、デジタル地図の道路形状に含まれるノードや補間点をそのまま座標点に用いて道路形状データを符号化する場合には、リサンプルの処理が不要になる。ただ、この場合には、ノードや補間点間の距離が一定していないため、角度と距離とを符号化することが必要になる。
【００８８】
図２２は、角度及び距離の両方を符号化する方法について示している。角度の符号化に関しては、第１の実施形態と同じであり、各ノード（補間点を含む）ＰJの角度情報を、偏角θjと偏角統計予測値Ｓjとの差分である予測値差分Δθjで表し、Δθjを例えば１°単位（２°単位等、他の分解能でも良い）で量子化し、量子化したΔθjの大きさの発生頻度に基づいてΔθの符号表を作成する。このとき、偏角統計予測値Ｓjは、例えば、Ｓj＝θj-1、あるいは、Ｓj＝（θj-1＋θj-2）／２として定義する。
【００８９】
図２３（ｂ）は、こうして作成したΔθの符号表の一例を示している。この表は、第１の実施形態の符号表（図２）と変わりがない。このΔθの符号表を用いて各ノードの角度情報（Δθj）を可変長符号化する。
【００９０】
一方、距離の符号化は、次のように行う。まず、各ノードＰJの距離情報を、隣接ノードＰJ+1までの距離Ｌjと距離統計予測値Ｔjとの差分である予測値差分ΔＬj（＝Ｌj−Ｔj）で表し、ΔＬjを例えば１０ｍ単位（５０ｍ単位、１００ｍ単位等、他の分解能でも良い）で量子化する。このとき距離統計予測値Ｔjは、例えば、Ｔj＝Ｌj-1、あるいは、Ｔj＝（Ｌj-1＋Ｌj-2）／２として定義する。
【００９１】
次いで、量子化したΔＬjの大きさの発生頻度に基づいてΔＬの符号表を作成する。図２３（ａ）は、こうして作成したΔＬの符号表の一例を示している。この符号表の付加ビットは、ΔＬの正負を表すために付加されるビットであり、ΔＬ≠０のとき、ΔＬが正であれば０、ΔＬが負であれば１が付加される。従って、Ｔj＝Ｌj-1と定義した場合、
ＬjがＬj-1より長い（Ｌj−Ｌj-1＞０）ときは０
ＬjがＬj-1より短い（Ｌj−Ｌj-1＜０）ときは１
を付加する。
【００９２】
このΔＬの符号表を用いて各ノードの距離情報（ΔＬj）を可変長符号化する。距離及び角度を符号化する際のデータの並びは、ΔＬj→Δθj→ΔＬj+1→Δθj+1→‥のように予め順序を決めておく。いま、ΔＬ−Δθの並びが
“0・0_0・0_0・-2_+2・-2_0・+3_-5・0_0・0_0・+6"
であるとき、このデータ列は、図２３（ａ）（ｂ）の符号表を用いて次のように可変長符号化される。
“0・0_0・0_0・1011_1010・1011_0・11000_11101・0_0・0_0・111100"
→“00000101110101011011000111010000111100”（３８ｂｉｔ）
これを、距離成分を８ｂｉｔ、角度成分を１０ビットの固定長で表したとすると、（８ｂｉｔ＋１０ｂｉｔ）×８ノード＝１４４ビットが必要であり、可変長符号化によってデータ量を２６％に圧縮することができる。
【００９３】
図２４（ａ）は、これらの符号表をオフラインで作成するときの処理手順を示している。まず、過去の交通情報を参照して（ステップ90）、交通情報の対象道路区間を選出する（ステップ91）。対象道路区間に含まれるノードの位置データを全曲率関数表現に変換し（ステップ92）、統計値算出式に従い、各区間の各ノードのΔＬj及びΔθjを算出する（ステップ93）。次に、ΔＬj及びΔθjの出現分布を計算し（ステップ94）、ΔＬjの出現分布を基にΔＬの符号表を作成し、また、Δθjの出現分布を基にΔθの符号表を作成する（ステップ95、96）。
【００９４】
また、図２４（ｂ）は、交通情報を伝達するために、作成された符号表を用いて道路形状データを符号化する際の処理手順を示している。交通情報を受信すると（ステップ97）、交通事象の発生位置を含む対象道路区間を選出する（ステップ98）。対象道路区間に含まれるノードの位置データを全曲率関数表現に変換し（ステップ99）、統計値算出式に従い、各区間の各ノードのΔＬj及びΔθjを算出する（ステップ100）。次に、前記対象道路区間を対象として作成された符号表（または前記対象道路区間に形状が近似している道路を対象として作成され符号表）の符号表データを参照し、各ノードのΔＬj及びΔθjを符号表現に変換する（ステップ101）。対象道路区間の相対情報で表した事象位置のデータとともに符号化した対象道路区間の形状データを送信する（ステップ102）。
【００９５】
図２５は、送信される道路形状データ（図２５（ａ））と事象位置データ（図２５（ｂ））とを示している。道路形状データには、符号表データ、符号表現される区間（ノードｐ１〜ｐ２）の始端ノードｐ１の絶対座標、ノードｐ１の絶対方位、ノードｐ１から次のノードまでの距離Ｌ、及び、ノードｐ１〜ｐ２間の符号化データ（ΔＬj及びΔθjを符号化したビット列）が含まれている。
【００９６】
このデータを受信した受信側では、図９の処理フローと同様に、符号表現されているデータを、符号表を参照して全曲率関数に変換し、道路形状データを再現する。次いで、再現された形状と自己のデジタル地図の道路形状とのマップマッチングを実行して対象道路区間を特定し、事象位置データから、この対象道路区間内の交通事象発生位置を特定する。
【００９７】
このように、この実施形態の方法では、座標点のリサンプルは行わずに、座標点を特定する角度と距離とのデータを共に可変長符号化して、道路形状データの伝送データ量を削減することができる。
【００９８】
（第６の実施形態）
第６の実施形態では、道路上で角度成分が一定となるように座標点位置をリサンプルし、距離成分のみを符号化する方法について説明する。
【００９９】
先に図３４を用いて説明したように、道路上に配列する座標点（ＰJ）は、隣接する座標点（ＰJ-1）からの距離と角度との２つのディメンジョンにより一意に特定することができる。第１〜第４の実施形態では、この２つのディメンジョンの内、距離が一定となるように座標点位置をリサンプルすることにより、角度のみを符号化して伝送データ量の削減を図っているが、第６の実施形態では、逆に、角度が一定となるように座標点位置をリサンプルし、距離のみの符号化により伝送データ量の削減を図る。
【０１００】
図２６は、角度情報を固定し（偏角θ＝一定）、距離情報を符号化する場合のリサンプル座標点を示している。この形状データのリサンプル処理は次のように行う。
（１）道路形状の上を始端ノードＰ0から終端ノードに向かってトレースし、偏角があらかじめ決めた角度θ（または−θ）に達した位置に次のノードＰ1を設定する。
（２）但し、（１）でトレースしている際、偏角がθ（または−θ）に達する前に、始端ノードＰ0からの距離が予め決めた距離Ｌmaxに達したときは、その位置に次のノードＰ1を設定する。
（３）前記（１）または（２）で決定したノードＰ1を始端として、前記（１）及び（２）の規則を適用して次のノードＰ2を決定し、それを順次繰り返して、Ｐ3、‥、ＰJ、‥を決定する。
【０１０１】
リサンプルした各ノードＰJにおける距離情報は、隣接ノードＰJ+1までの距離Ｌjと距離統計予測値Ｔjとの差分である予測値差分ΔＬj（＝Ｌj−Ｔj）で表し、ΔＬjを例えば１０ｍ単位（５０ｍ単位、１００ｍ単位等、他の分解能でも良い）で量子化する。このとき距離統計予測値Ｔjは、例えば、Ｔj＝Ｌj-1、あるいは、Ｔj＝（Ｌj-1＋Ｌj-2）／２として定義する。次いで、量子化したΔＬjの大きさの発生頻度に基づいてΔＬの符号表を作成する。このとき、ΔＬjの連続分布を計算し、ランレングス符号化を組み入れた符号表を作成しても良い。
【０１０２】
こうして作成したΔＬの符号表の一例を図２７に示している。この符号表では、ΔＬ＝０のとき、偏角θの正負を表すための１ビット（θが正であれば０、負であれば１）を付加ビットとして符号に付加することを規定し、また、ΔＬ≠０のとき、偏角θの正負を表すための１ビットと、ΔＬの正負を表すための１ビット（ΔＬが正であれば０、負であれば１）との合計２ビットを符号に付加ビットとして付加することを規定している。従って、Ｔj＝Ｌj-1と定義した場合では、
ΔＬ≠０のとき、
ＬjがＬj-1より長い（Ｌj−Ｌj-1＞０）ときは、ΔＬの正負を表す付加ビットとして０
ＬjがＬj-1より短い（Ｌj−Ｌj-1＜０）ときは、ΔＬの正負を表す付加ビットとして１が付加され、また、
Ｐj-1→Ｐjの方位がＰj-2→Ｐj-1の方位の左側にあるとき（左曲がり）は、θの正負を表す付加ビットとして０
Ｐj-1→Ｐjの方位がＰj-2→Ｐj-1の方位の右側にあるとき（右曲がり）は、θの正負を表す付加ビットとして１が付加される。
【０１０３】
なお、第４の実施形態では、距離成分が一定となるように座標点をリサンプルする場合に、区間によって距離成分（リサンプル区間長）を変更する例について説明したが、同様に、角度成分が一定となるようにリサンプルする場合でも、θの値を区間によって切り替えることも可能である。この場合、符号変換した形状データ列上では、第４の実施形態と同様に、特殊コードを使って各区間のθの値を識別できるようにする。
【０１０４】
図２８（ａ）は、この符号表をオフラインで作成するときの処理手順を示し、また、図２８（ｂ）は、作成された符号表を用いて道路形状データを符号化し、交通情報を伝達する際の処理手順を示している。これらの手順は、第３の実施形態で説明した手順（図７）と比べて、対象道路区間の形状データを、固定長Ｌでリサンプルする代わりに固定角θ（または−θ）でリサンプルしている点（ステップ112、ステップ121）、リサンプルした各ノードのΔθを算出する代わりにΔＬを算出している点（ステップ114、ステップ123）、及び、Δθの分布に基づいてΔθの符号表を作成する代わりに、ΔＬの分布に基づいてΔＬの符号表を作成している点（ステップ115、ステップ117）で相違しているが、その他の手順は同じである。
【０１０５】
また、図２９は、送信される道路形状データを示している。この道路形状データは、第３の実施形態で説明した道路形状データ（図８（ａ））と比べて、サンプル区間長Ｌの代わりにサンプル角度θの情報が含まれ、また、符号化データとして、Δθjを符号化したビット列の代わりにΔＬjを符号化したビット列が含まれている点で相違しているが、その他の点については同じである。
【０１０６】
このデータを受信した受信側では、図９の処理フローと同様に、符号表現されているデータを、符号表を参照して全曲率関数に変換し、道路形状データを再現する。次いで、再現された形状と自己のデジタル地図の道路形状とのマップマッチングを実行して対象道路区間を特定し、事象位置データから、この対象道路区間内の交通事象発生位置を特定する。
【０１０７】
このように、この実施形態の方法では、道路上で角度成分が一定となるように座標点位置をリサンプルし、距離成分のみを可変長符号化して、道路形状データの伝送データ量を削減することができる。
【０１０８】
（第７の実施形態）
第７の実施形態の符号化方法では、道路形状を統計的に偏りを持つ形状データに変換するために、角度情報の表現方法として、偏角による表現または予測値差分による表現のいずれかを選択できるようにしている。
【０１０９】
先に図３５を用いて説明したように、座標点の角度情報は、偏角θjでの表現（図３５（ｂ）（ｂ’））、及び、偏角θjの予測値差分Δθjでの表現（図３５（ｃ）（ｃ’））のいずれを採用した場合でも、道路形状データを統計的に偏りを持つデータに変換することができる。
【０１１０】
この統計的な偏りは、それが大きい程、可変長符号化によるデータ量削減の効果が高い。座標点の角度情報を偏角θjで表現する場合と偏角θjの予測値差分Δθjで表現する場合とを比較すると、一般的には、後者の方が統計的な偏りは大きい。
【０１１１】
しかし、図３０に示すように、カーブとカーブとの間にしばらく直線が続くような道路40の場合には、偏角の予測値差分Δθjで表現すると、
0,‥,0,θ1,-θ1,0,‥,0,θ2,-θ2,0,‥
となるが、偏角θで表現すると、
0,‥,0,θ1,0,0,‥,0,θ2,0,0,‥
となり、座標点の角度情報を偏角θjで表現した方が、予測値差分Δθjで表現するよりも、統計的な偏りを持たせることができる。このように、道路形状によっては、一定距離Ｌでリサンプルした座標点の角度情報を偏角θjで表現した方が、可変長符号化に適する場合が有る。
【０１１２】
この実施形態の方法では、道路形状を偏角θで表現して可変長符号化した時のデータサイズと、偏角の予測値差分Δθで表現して可変長符号化した時のデータサイズとを比較し、データサイズの小さい方の符号化データを伝送するようにしている。
【０１１３】
そこで、まず、道路形状を偏角θjで表現して可変長符号化するための偏角θ符号表と、道路形状を偏角θjの予測値差分Δθjで表現して可変長符号化するためのΔθ符号表とを作成する。
【０１１４】
図３１（ａ）は偏角θ符号表の作成手順を示し、図３１（ｂ）はΔθ符号表の作成手順を示している。図３１（ｂ）の手順は、第３の実施形態における手順（図７（ａ））と同じである。また、図３１（ａ）の手順は、図３１（ｂ）の手順中のΔθが偏角θに代わっている点だけが違っている。
【０１１５】
図３２は、オフラインで作成されたこれらの符号表を用いて、道路形状データを符号化し、交通情報を伝達する際の処理手順を示している。
ステップ130：交通情報を受信すると、
ステップ131：交通事象の発生位置を含む対象道路区間を選出し、
ステップ132：対象道路区間の道路形状データを固定長Ｌでリサンプルしてノードを設定し、
ステップ133：設定したノードの位置データを全曲率関数表現に変換する。
【０１１６】
ステップ134：次に、θの符号表を参照して、θの符号データを作成し、データサイズ（Ａ）を算出する。
ステップ135：次に、Δθの符号表を参照して、Δθの符号データを作成し、データサイズ（Ｂ）を算出する。
ステップ136：データサイズ（Ａ）とデータサイズ（Ｂ）とを比較して、データサイズが小さい方の角度表現を採用し、送信する形状データに、採用した角度表現を表す「角度表現識別フラグ」の値と、採用した角度表現での「符号化データ」とをセットする。
ステップ137：対象道路区間の相対情報で表した事象位置のデータとともに符
号化した対象道路区間の形状データを送信する。
【０１１７】
図３３は、送信される道路形状データを示している。この道路形状データには、採用した角度表現を表す「角度表現識別フラグ」（偏角θによる表現を採用したときは０、予測値差分Δθによる表現を採用したときは１）の情報、及び、採用した角度表現での「符号化データ」の情報を含んでいる。
【０１１８】
このデータを受信した受信側では、「角度表現識別フラグ」が指定する情報に基づいて、符号表現されている「符号化データ」から、符号表を参照して、θまたはΔθを復元し、各ノードの位置データを全曲率関数に変換する。その後の処理は、第３の実施形態等と同じであり、道路形状データを再現して、再現した形状と自己のデジタル地図の道路形状とのマップマッチングを実行して対象道路区間を特定し、事象位置データから、この対象道路区間内の交通事象発生位置を特定する。
【０１１９】
このように、この実施形態の方法では、角度情報の表現方法として、偏角による表現または予測値差分による表現のいずれかを選択することにより、伝送データ量の一層の削減を図ることができる。
【０１２０】
なお、本発明による符号化方法は、地図データ本体の圧縮にも適用が可能である。また、地図データのインターネット上のやり取り（例、ベクトル地図を使ったクライアント・サーバ型地図表示システム）や地図データ配信サービスなどにも適用できる。
【０１２１】
また、車両の車載機から緊急通報やフローティングカーデータ（ＦＣＤ）のために、センターに走行軌跡データを送信する場合にも、この符号化方法を用いてデータを圧縮することが可能である。
【０１２２】
また、ベクトル形状をスプライン圧縮方式で圧縮し、各節点列のデータとして伝送する場合にも、本発明の符号化方法を適用して、節点列の表現を符号表を用いてデータ圧縮することが可能である。
【０１２３】
また、本発明による符号化方法は、デジタル地図上の領域（ポリゴン）の形状データを伝達する場合にも適用することができる。例えば、ポリゴンを指定してその領域の天気予報を伝える場合では、ポリゴン形状の境界線の形状データを伝達することにより、受信側では、ポリゴンを特定することができる。この境界線の形状データを伝達する場合、本発明の符号化方法を適用して伝送データ量を圧縮することができる。このとき、天気予報の適用領域のようにポリゴン形状を精密に特定する必要がない場合には、受信側では、デジタル地図上の形状とのマッチング処理を省略することができる。
【０１２４】
例示した符号表は、あくまで例であり、最適なものとは言えない。実際には、変数（θj、Δθj、Ｌjなど）の分布を調査し、ハフマン木などを用いて符号表を作成する必要がある。
【０１２５】
符号化技術には、固定文字圧縮法、ランレングス法、シャノン・ファノ符号法、ハフマン符号法、適応型ハフマン符号法、算術符号法、辞書法（ＬＨＡ法）等多種存在し、本発明において、これらの符号化方法を用いることも可能である。また、ここでは、符号表をオフラインで生成する場合について説明したが、適応型ハフマン符号法や算術符号法を用いることによりオンラインでの符号化が可能になる。
【産業上の利用可能性】
【０１２６】
以上の説明から明らかなように、本発明の符号化方法では、デジタル地図におけるベクトル形状のデータ量を効率的に圧縮することができる。そのため、本発明の位置情報伝達方法及び装置では、デジタル地図のベクトル形状を伝達する場合の伝送データ量を大幅に減らすことができる。受信側では、受信データから形状データを復元し、マップマッチングを実施することにより、伝送されたベクトル形状を正確に特定することができる。
【図面の簡単な説明】
【０１２７】
【図１】第１の実施形態の符号化方法を適用する場合のリサンプルされたノードを示す図、
【図２】第１の実施形態の符号化方法での符号表を示す図、
【図３】第２の実施形態の符号化方法で用いるランレングス符号表を示す図、
【図４】第２の実施形態の符号化方法で用いるΔθの符号表を示す図、
【図５】第２の実施形態の符号化方法で用いるランレングスを考慮したΔθの符号表を示す図、
【図６】第３の実施形態の位置情報伝達方法を実施する装置の構成を示すブロック図、
【図７】第３の実施形態の符号化方法での符号表作成手順（ａ）と形状データ作成処理手順（ｂ）とを示すフロー図、
【図８】第３の実施形態の位置情報伝達方法での送信データの構成を示す図、
【図９】第３の実施形態の位置情報伝達方法での受信側の処理手順を示すフロー図、
【図１０】第４の実施形態の符号化方法でのサンプル区間長と形状データの曲率との関係を示す図、
【図１１】第４の実施形態の符号化方法での円弧・直線近似を説明する図、
【図１２】第４の実施形態の符号化方法での区分された区間を示す図、
【図１３】第４の実施形態の符号化方法でのリサンプル区間長の決定方法を示すフロー図、
【図１４】第４の実施形態の符号化方法での量子化リサンプルを説明する図、
【図１５】第４の実施形態の符号化方法での次ノードの候補点を説明する図、
【図１６】第４の実施形態の符号化方法での次ノード決定手順を示すフロー図、
【図１７】第４の実施形態の符号化方法での符号表を示す図、
【図１８】第４の実施形態の符号化方法での符号表作成手順（ａ）と形状データ作成処理手順（ｂ）とを示すフロー図、
【図１９】第４の実施形態の位置情報伝達方法での送信データの構成を示す図、
【図２０】第４の実施形態の符号化方法でのデータの伝送を模式的に示す図、
【図２１】第４の実施形態の位置情報伝達方法での受信側の処理手順を示すフロー図、
【図２２】第５の実施形態の符号化方法を適用する場合のノード位置、距離及び角度情報を示す図、
【図２３】第５の実施形態の符号化方法で用いる符号表を示す図、
【図２４】第５の実施形態の符号化方法での符号表作成手順（ａ）と形状データ作成処理手順（ｂ）とを示すフロー図、
【図２５】第５の実施形態の位置情報伝達方法での送信データの構成を示す図、
【図２６】第６の実施形態の符号化方法を適用する場合のノード位置、距離及び角度情報を示す図、
【図２７】第６の実施形態の符号化方法で用いる符号表を示す図、
【図２８】第６の実施形態の符号化方法での符号表作成手順（ａ）と形状データ作成処理手順（ｂ）とを示すフロー図、
【図２９】第６の実施形態の位置情報伝達方法での送信データの構成を示す図、
【図３０】第７の実施形態の符号化方法を適用するのに適する道路形状を示す図、
【図３１】第７の実施形態の符号化方法でのθ符号表の作成手順（ａ）と、Δθ符号表の作成手順（ｂ）とを示すフロー図、
【図３２】第７の実施形態の符号化方法での形状データ作成処理手順を示すフロー図、
【図３３】第７の実施形態の位置情報伝達方法での送信データの構成を示す図、
【図３４】座標点を特定する距離及び角度について説明する図、
【図３５】（ａ）（ａ'）形状データの全曲率関数表現を示す図、  （ｂ）（ｂ'）形状データの偏角表現を示す図、  （ｃ）（ｃ'）形状データの偏角の予測値差分表現を示す図、
【図３６】従来の位置情報伝達方法でのデータ構成を示す図である。
【符号の説明】
【０１２８】
10、30  オンライン処理部
11  事象情報入力部
12  デジタル地図表示部
13、22  デジタル地図データベース
14  マップマッチング部
15  位置情報変換部
16  位置情報送信部
17  位置情報受信部
18  符号データ解凍部
20  オフライン処理部
21  過去の交通情報
23  符号表算出部
24  符号表データ
40  道路
【図１】
2004354396.tif 000003
【図２】
2004354396.tif 000004
【図３】
2004354396.tif 000005
【図４】
2004354396.tif 000006
【図５】
2004354396.tif 000007
【図６】
2004354396.tif 000008
【図７】
2004354396.tif 000009
【図８】
2004354396.tif 000010
【図９】
2004354396.tif 000011
【図１０】
2004354396.tif 000012
【図１１】
2004354396.tif 000013
【図１２】
2004354396.tif 000014
【図１３】
2004354396.tif 000015
【図１４】
2004354396.tif 000016
【図１５】
2004354396.tif 000017
【図１６】
2004354396.tif 000018
【図１７】
2004354396.tif 000019
【図１８】
2004354396.tif 000020
【図１９】
2004354396.tif 000021
【図２０】
2004354396.tif 000022
【図２１】
2004354396.tif 000023
【図２２】
2004354396.tif 000024
【図２３】
2004354396.tif 000025
【図２４】
2004354396.tif 000026
【図２５】
2004354396.tif 000027
【図２６】
2004354396.tif 000028
【図２７】
2004354396.tif 000029
【図２８】
2004354396.tif 000030
【図２９】
2004354396.tif 000031
【図３０】
2004354396.tif 000032
【図３１】
2004354396.tif 000033
【図３２】
2004354396.tif 000034
【図３３】
2004354396.tif 000035
【図３４】
2004354396.tif 000036
【図３５】
2004354396.tif 000037
【図３６】
2004354396.tif 000038