(57)【要約】道路形状をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表した各ノードの位置情報を配列して偏角のデータ列を生成し、前記偏角を、予測値との差分を示す予測差分値に変換して、予測差分値のデータ列を可変長符号化する符号化データの生成方法において、偏角を予測差分値に変換したときの予測差分値のデータ列を評価し、評価結果に基づいて、予測値を算出する予測式を複数の予測式φ＝１、φ＝２、φ＝３、φ＝４の中から適応的に選択する。予測値を算出する予測式を道路形状Ａ、Ｂ、Ｃ、Ｄに応じて適応的に選択することで、データ圧縮の効果が向上する。【特許請求の範囲】
【請求項１】
線形対象物を符号化して得られる符号化データの生成方法であって、
（１）前記線形対象物をリサンプルして複数のノードを設定するステップと、
（２）一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成するステップと、
（３）前記偏角のデータ列に基づき、前記各ノードの位置データの予測値を算出するための複数の予測式を用意するステップと、
（４）当該複数の予測式のうち、所定の予測式を用いて前記予測値を算出するステップと、
（５）前記偏角のデータ列を、前記算出された予測値との差分を示す予測差分値のデータ列に変換するステップと、
（６）前記予測差分値のデータ列を可変長符号化して前記符号化データを得るステップと、を備える符号化データ生成方法。
【請求項２】
請求項１に記載の符号化データ生成方法であって、
前記（５）のステップにより、前記複数の予測式の各々について、前記複数の予測式の各々に対応した複数の前記予測差分値のデータ列を取得するステップと、
前記複数の予測差分値のデータ列を評価するステップと、
前記評価ステップの評価結果に基づき、前記（４）のステップにおける前記所定の予測式を、前記複数の予測式の中から選択するステップと、を更に備える符号化データ生成方法。
【請求項３】
請求項１又は２に記載の符号化データ生成方法であって、
前記複数の予測式は、０を予測値とする予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項４】
請求項１又は２に記載の符号化データ生成方法であって、
前記複数の予測式は、着目する偏角に先行する少なくとも一つの偏角をパラメータとして用いた関数によって構成された予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項５】
請求項４に記載の符号化データ生成方法であって、
前記関数によって構成された予測式は、前記着目する偏角の一つ前の偏角を予測値とする予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項６】
請求項４に記載の符号化データ生成方法であって、
前記関数によって構成された予測式は、前記着目する偏角に先行する複数の偏角の平均または加重平均を予測値とする予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項７】
請求項４に記載の符号化データ生成方法であって、
前記関数によって構成された予測式は、前記着目する偏角の一つ前のノードの偏角の正負を逆にした角度を予測値とする予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項８】
請求項２に記載の符号化データ生成方法であって、
前記（５）のステップにおいて、前記線形対象物の一部区間に対応する偏角のデータ列が前記予測差分値のデータ列に変換され、当該予測差分値のデータ列に対する評価結果に基づいて、前記一部区間に対応する偏角を予測差分値に変換する予測式を選択する、符号化データ生成方法。
【請求項９】
請求項８に記載の符号化データ生成方法であって、
前記偏角のデータ列を、偏角の状態遷移のパターンに対応したブロックに区分し、前記ブロック毎に、偏角を予測差分値に変換する予測式を選択する、請求項７に記載の符号化データ生成方法。
【請求項１０】
請求項８に記載の符号化データ生成方法であって、
前記偏角のデータ列を、所定数の偏角のデータを含むブロックに区分し、前記ブロック毎に、偏角を予測差分値に変換する予測式を選択する、符号化データ生成方法。
【請求項１１】
請求項８に記載の符号化データ生成方法であって、
前記偏角のデータ列を、前記（１）のステップにおけるリサンプルのリサンプル長の変更点に合わせてブロックに区分し、前記ブロック毎に、偏角を予測差分値に変換する予測式を選択する、符号化データ生成方法。
【請求項１２】
請求項８に記載の符号化データ生成方法であって、
着目する偏角に先行する所定数の偏角の予測差分値のデータ列に対する評価結果に応じて、前記着目する偏角を予測差分値に変換する予測式を選択する、符号化データ生成方法。
【請求項１３】
請求項１２に記載の符号化データ生成方法であって、
前記複数の選択式を用いて、前記所定数の偏角を複数の予測差分値のデータ列に変換し、所定の選択式に基づく予測差分値のデータ列に対する評価結果が所定の要件を満たす場合のみ、現在使用されている予測式を前記所定の予測式に変更したうえで、前記着目する偏角を予測差分値に変換する、符号化データ生成方法。
【請求項１４】
請求項８ないし１１に記載の符号化データ生成方法であって、
着目する偏角またはブロックにおいて、前後の偏角またはブロックでの予測式の選択状況を参考にして予測式を選択する、符号化データ生成方法。
【請求項１５】
請求項１４に記載の符号化データ生成方法であって、
着目する偏角またはブロックにおいて、前後の偏角またはブロックで採用する予測式とは異なる予測式を選出する場合、前記着目する偏角またはブロックでの予測差分値列の評価基準である評価値に対しペナルティ値を加算する、符号化データ生成方法。
【請求項１６】
請求項１５に記載の符号化データ生成方法であって、
各予測式の発生頻度に応じて前記ペナルティ値を設定する、符号化データ生成方法。
【請求項１７】
請求項２ないし１６のいずれか１項に記載の符号化データ生成方法であって、
前記予測差分値のデータ列の評価を、前記データ列に含まれる０の数によって行い、最も０の数が多くなる予測式を選択する、符号化データ生成方法。
【請求項１８】
請求項２ないし１６のいずれか１項に記載の符号化データ生成方法であって、
前記予測差分値のデータ列の評価を、前記データ列に含まれる予測差分値の統計値によって行い、前記統計値の結果に基づき予測式を選択する、符号化データ生成方法。
【請求項１９】
請求項１８に記載の符号化データ生成方法であって、
前記統計値は、前記予測差分値の分散及び標準偏差の少なくともいずれか一つである、符号化データ生成方法。
【請求項２０】
請求項２ないし１６のいずれか１項に記載の符号化データ生成方法であって、
前記予測差分値ごとの評価値をあらかじめ設定し、前記予測差分値のデータ列の評価を、前記データ列に含まれた予測差分値の評価値の合計値によって行う、符号化データ生成方法。
【請求項２１】
請求項２０に記載の符号化データ生成方法であって、
前記予測差分値の発生頻度が前記評価値であり、前記合計値が最も大きい予測式を選択する、符号化データ生成方法。
【請求項２２】
請求項２０に記載の符号化データ生成方法であって、
前記予測差分値の符号長が前記評価値であり、前記合計値が最も小さい予測式を選択する、符号化データ生成方法。
【請求項２３】
線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成する形状データリサンプル処理部と、
前記偏角のデータ列を、前記各ノードの位置データを予測するための予測値との差分を示す予測差分値に変換したときの前記予測差分値のデータ列を評価し、評価結果に基づいて、前記予測値を算出する予測式を複数の予測式の中から選択する予測式決定部と、
前記形状データリサンプル処理部が生成した前記偏角のデータ列に含まれる偏角を、前記予測式決定部が決定した予測式を用いて算出した予測値との予測差分値に変換して、前記予測差分値のデータ列を可変長符号化する可変長符号化処理部と、を備える符号化データ生成装置。
【請求項２４】
線形対象物の位置情報を表す可変長符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する符号化データ復号部と、
復号化された前記形状データから、前記予測値の算出に用いた予測式を決定する予測式判定部と、
前記予測式判定部が決定した予測式を用いて予測値を算出し、前記符号化データ復号部が復号化した前記予測差分値のデータ列から、前記線形対象物のノードの位置情報を再現する形状データ復元部と、を備える符号化データ復元装置。
【請求項２５】
線形対象物を符号化して得られる符号化データの生成をコンピュータに実行させるためのプログラムであって、当該プログラムは、
線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成する手順と、
前記偏角のデータ列を、前記各ノードの位置データの予測値との差分を示す予測差分値に変換したときの前記予測差分値のデータ列を評価する手順と、
評価結果に基づいて、前記予測値を算出する予測式を複数の予測式の中から選択する手順と、
前記偏角のデータ列に含まれる偏角を、前記決定された予測式を用いて算出した予測値との予測差分値に変換して、前記予測差分値のデータ列を可変長符号化する手順と、を前記コンピュータに実行させるプログラム。
【請求項２６】
線形対象物を表わす符号化データの復号化をコンピュータに実行させるためのプログラムであって、当該プログラムは、
線形対象物の位置情報を表す可変長符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する手順と、
復号化された前記形状データから、前記予測値の算出に用いた予測式を決定する手順と、
前記決定された予測式を用いて予測値を算出し、前記復号化された前記予測差分値のデータ列から、前記線形対象物のノードの位置情報を再現する手順と、を前記コンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、デジタル地図の道路位置等を表す符号化データの生成方法と、その符号化データの生成及び復号化を行う装置に関し、符号化データのデータ量の削減を図るものである。
【背景技術】
【０００２】  従来から、ＶＩＣＳ（道路交通情報通信システム）では、デジタル地図データベースを搭載する車両用ナビゲーション装置に対して、ＦＭ多重放送やビーコンを通じて、渋滞区間や旅行時間を示す道路交通情報の提供サービスを実施している。車両用ナビゲーション装置は、この道路交通情報を受信して、画面表示する地図に渋滞区間を色付けして表したり、目的地までの所用時間を算出して表示したりしている。【０００３】  このように、道路交通情報を提供する場合には、デジタル地図上の道路の位置情報を伝えることが必要になる。また、現在地及び目的地の情報を受信して、最短時間で目的地まで到達できる推奨経路の情報を提供するサービスや、近年、研究が進められている、走行中の車両（プローブカー）から軌跡情報及び速度情報等を収集する道路交通情報収集システム（プローブ情報収集システム）においても、デジタル地図上の推奨経路や走行軌跡を相手方に正しく伝えることが必要である。【０００４】  これまで、デジタル地図上の道路位置を伝える場合には、一般的に、道路に付されたリンク番号や、交差点などのノードを特定するノード番号が使用されている。しかし、道路網に定義したノード番号やリンク番号は、道路の新設や変更に伴って新しい番号に付け替える必要があり、それに応じて、各社で制作されるデジタル地図データも更新しなければならないため、ノード番号やリンク番号を用いる方式は、メンテナンスに多大な社会的コストが掛かることになる。【０００５】  こうした点を改善するため、特開２００３−２３３５７号公報では、ノード番号やリンク番号を用いずに、且つ、少ないデータ量でデジタル地図上の道路位置を伝える方法を提案している。【０００６】  この方法では、伝えようとするデジタル地図上の道路区間に一定距離間隔でサンプリング点を再設定し（これを「等距離リサンプル」と言う）、各サンプリング点の位置データを順番に並べたデータ列に対して圧縮符号化の処理を施し、圧縮符号化したデータを送信する。これを受信した受信側は、サンプリング点の位置データのデータ列を復元し、自己のデジタル地図上に道路形状を再現する。また、必要に応じて、この位置データを使用して、自己のデジタル地図上で位置特定、位置参照を実施し（マップマッチング）、道路区間を特定する。【０００７】  位置データのデータ列に対する圧縮符号化は、次に示すように、（１）位置データの単一変数への変換、（２）単一変数で表わした値の統計的に偏りを持つ値への変換、（３）変換した値の可変長符号化、の順に行われる。
（１）位置データの単一変数への変換
図２６（ａ）には、等距離リサンプルで設定した道路区間上のサンプリング点をＰＪ−１、ＰＪで表している。このサンプリング点（ＰＪ）は、隣接するサンプリング点（ＰＪ−１）からの距離（リサンプル長）Ｌと角度Θとの２つのディメンジョンで一意に特定することができ、距離を一定（Ｌ）とすると、サンプリング点（ＰＪ）は、隣接サンプリング点（ＰＪ−１）からの角度成分Θのみの単一変数で表現することができる。図２６（ａ）では、この角度Θとして、真北（図の上方）の方位を０度とし、時計回りに０〜３６０度の範囲で大きさを指定する「絶対方位」による角度Θを示している（真北からの絶対方位）。この角度Θは、ＰＪ−１、ＰＪのｘｙ座標（緯度・経度）を（ｘｊ−１，ｙｊ−１）、（ｘｊ，ｙｊ）とするとき、次式により算出することができる。【０００８】      Θｊ−１＝ｔａｎ−１｛（ｘｊ−ｘｊ−１）／（ｙｊ−ｙｊ−１）｝
従って、道路区間は、サンプリング点間の一定距離Ｌ、及び、始端または終端となるサンプリング点（基準点）の緯度・経度を別に示すことにより、各サンプリング点の角度成分のデータ列により表わすことができる。
（２）単一変数値の統計的に偏りを持つ値への変換
各サンプリング点の単一変数値が、可変長符号化に適した、統計的に偏在する値となるように、図２６（ｂ）に示すように、各サンプリング点の角度成分を、隣接するサンプリング点の角度成分との変位差、即ち、「偏角」θｊによって表現する。この偏角θｊは、
θｊ＝Θｊ−Θｊ−１
として算出される。道路が直線的である場合に、各サンプリング点の偏角θは０付近に集中し、統計的に偏りを持つデータとなる。【０００９】  また、サンプリング点の角度成分は、図２６（ｃ）に示すように、着目するサンプリング点ＰＪの偏角θｊを、それ以前のサンプリング点ＰＪ−１、ＰＪ−２、・・の偏角θｊ−１、θｊ−２、・・を用いて予測した当該サンプリング点ＰＪの予測値Ｓｊとの差分値（予測差分値又は予測誤差）Δθｊで表わすことにより、統計的に偏りを持つデータに変換することができる。予測値Ｓｊは、例えば、
Ｓｊ＝θｊ−１
と定義したり、
Ｓｊ＝（θｊ−１＋θｊ−２）／２
と定義したりすることができる。予測差分値Δθｊは、
Δθｊ＝θｊ−Ｓｊ
として算出される。道路が一定の曲率で湾曲している場合には、各サンプリング点の予測差分値Δθは０付近に集中し、統計的に偏りを持つデータとなる。【００１０】  図２６（ｄ）は、直線的な道路区間を偏角θで表示した場合、及び、曲線的な道路区間を予測差分値Δθで表示した場合のデータの発生頻度をグラフ化して示している。θ及びΔθの発生頻度はθ（又はΔθ）＝０°に極大が現れ、統計的に偏りを持っている。
（３）可変長符号化
次に、統計的に偏りを持つ値に変換したデータ列の値を可変長符号化する。可変長符号化方法には、固定数値圧縮法（０圧縮等）、シャノン・ファノ符号法、ハフマン符号法、算術符号法、辞書法など多種存在し、いずれの方法を用いてもよい。【００１１】  ここでは、最も一般的なハフマン符号法を用いる場合について説明する。
この可変長符号化では、発生頻度が高いデータを少ないビット数で符号化し、発生頻度が低いデータを多いビット数で符号化して、トータルのデータ量を削減する。このデータと符号との関係は、符号表で定義する。【００１２】  いま、１°単位で表わした道路区間のサンプリング点におけるΔθの並びが
“０＿０＿−２＿０＿０＿＋１＿０＿０＿−１＿０＿＋５＿０＿０＿０＿＋１＿０”
であるとする。このデータ列を符号化するために、可変長符号化とランレングス符号化（連長符号化）とを組み合わせた図２７に示す符号表を用いる場合について説明する。この符号表では、最小角度分解能（δ）を３°に設定しており、−１°〜＋１°の範囲にあるΔθの代表角度を０°として符号「０」で表し、０°が５個連続するときは符号「１００」で表わし、０°が１０個連続するときは符号「１１０１」で表わすことを規定している。また、±２°〜４°の範囲にあるΔθの代表角度は±３°として、符号「１１１０」に、＋のときは付加ビット「０」を、−のときは付加ビット「１」を加えて表し、±５°〜７°の範囲にあるΔθの代表角度は±６°として、符号「１１１１００」に正負を示す付加ビットを加えて表し、また、±８°〜１０°の範囲にあるΔθの代表角度は±９°として、符号「１１１１０１」に正負を示す付加ビットを加えて表わすことを規定している。【００１３】  そのため、前記データ列は、次のように符号化される。
“０＿０＿１１１０１＿１００＿０＿０＿１１１１０００＿１００”
→“００１１１０１１００００１１１１０００１００”
このデータを受信した受信側は、符号化で使用されたものと同一の符号表を用いてΔθのデータ列を復元し、送信側と逆の処理を行って、サンプリング点の位置データを再現する。【００１４】  このように、データを符号化することにより、符号化データのデータ量の削減が可能である。
また、前記特開２００３−２３３５７号公報では、図２８に示すように、道路形状の曲率が大きい区間Ｂでは、等距離リサンプルの距離Ｌ２を短く設定し、曲率が小さい、直線的な道路区間Ａでは、等距離リサンプルの距離Ｌ１を長く設定することを提案している。これは、曲率が大きく、カーブがきつい道路を長い距離でリサンプルすると、特徴的な道路形状を示す位置にサンプリング点を配置することができなくなり、受信側での道路形状の再現性が悪くなり、また、誤マッチングが発生する可能性が高くなるためである。【００１５】  そのため、各区間ｊのリサンプル長Ｌｊが取り得る値（量子化リサンプル長）を、例えば、４０／８０／１６０／３２０／６４０／１２８０／２５６０／５１２０メートルのように予め設定し、区間ｊの曲率半径ρｊを用いて、次式によりＬｊを求め、この値に最も近い量子化リサンプル長をリサンプル長Ｌｊとして決定している。【００１６】    Ｌｊ＝ρｊ・Ｋｒ（Ｋｒは固定パラメータ）
前記特開２００３−２３３５７号公報の方法を、次の３つの予測式を用いて試行を行った。【００１７】    予測式１：Ｓｊ＝０：偏角をそのまま利用（実質的には、予測を行わない）
予測式２：Ｓｊ＝θｊ−１：前ノードの偏角を利用
予測式３：Ｓｊ＝（θｊ−１＋θｊ−２）／２：前及び前々ノードの偏角平          均値を利用
結果は、平均的には予測式１の圧縮効率が高かったものの、対象道路を個別にみた場合、予測式２または予測式３の圧縮効率が高いものも存在した。【００１８】  具体的には、高速道路など、長くなだらかなカーブを多く含む形状の道路では、予測式２または予測式３が適しているケースが多く、また、一般道では、予測式１が適しているケースが多かった。【００１９】  また同種の予測式である、予測式２と予測式３を比較した場合は、若干、予測式３の方が圧縮効率で勝るケースが多かった。
本発明は、効率的にデータを圧縮して、デジタル地図の道路形状等の符号化データを生成する符号化データ生成方法を提供し、また、その符号化データの生成や符号化データの復号化を行う装置を提供することを目的としている。
【特許文献１】特開２００３−２３３５７号
【発明の開示】
【００２０】  上述の点を考察した結果、以下の結果が導かれた。
・高速道路などの「なだらかなカーブ」部分は、比較的小さな曲率が長距離にわたって、ほぼ一定となる。このため、ある微小区間に着目すると、該当箇所の曲率は、上流側の区間の曲率から非常に容易に予測できる。以上より、前または前々ノードの偏角をもちいて該当区間の偏角を予測する、予測式２または予測式３が適している。
・特に予測式３は、上流側の前および前々区間の平均曲率を用いた予測であり、区間毎の曲率誤差が平滑化される。よって、上記のような「長距離わたるなだらかなカーブ」においては、高精度な予測が可能となる。
・しかしながら、カーブ区間が比較的短い場合、予測式３は、予測式２と比較し、上流側のより長い区間の影響を受けることから、カーブの開始・終了箇所周辺（＝曲率が変更する箇所周辺）での予測が外れやすい。この影響を受け、カーブ区間が比較的短い場合には、予測式２の方が予測式３に勝るケースもある。
・一方、一般道路では、交差点部等で直角に曲がったり、カーブが存在しても比較的大きな曲率が短距離のみであるケースが多い。これはすなわち、ある微小区間の曲率を、上流側の前区間の曲率から予測しにくく、また予測をしたとしても外れやすい、ということである。このような場合には、実質的には予測を行わない、予測式１（偏角をそのまま用いる）が適している。
【００２１】  前記の試行結果から、道路全体を見渡すと、全般的には、予測式１（予測を行わず、偏角をそのまま用いる）の効率が良いものの、個別の道路または道路区間に着目した場合は、予測式２または予測式３（上流側の曲率から該当地点の曲率を予測する）が適した箇所も混在している、ということが分かった。
【００２２】  上記の点を踏まえ、本発明では、線形形状を備えた線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表した各ノードの位置情報を配列して偏角のデータ列を生成し、前記偏角を予測値との差分を示す予測差分値に変換して、予測差分値のデータ列を可変長符号化する符号化データの生成方法において、予測値を算出する予測式を複数の予測式の中から選択するようにしている。
【００２３】  このように、予測値を算出する予測式を動的に選択することによって、データ圧縮の効果を高めることができる。特に上記構成において、偏角を予測差分値に変換したときの予測差分値のデータ列を評価し、当該評価結果に基づいて予測式が選択される。
【００２４】  上述の符号化データ生成方法は以下の（１）〜（６）のステップを備え得る。
（１）線形対象物をリサンプルして複数のノードを設定するステップ。
（２）一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成するステップ。
【００２５】  （３）偏角のデータ列に基づき、各ノードの位置データの予測値を算出するための複数の予測式を用意するステップ。
（４）当該複数の予測式のうち、所定の予測式を用いて予測値を算出するステップ。
【００２６】  （５）偏角のデータ列を、算出された予測値との差分を示す予測差分値のデータ列に変換するステップ。
（６）予測差分値のデータ列を可変長符号化して前記符号化データを得るステップ。
【００２７】  更に上述（５）のステップにより、複数の予測式の各々について、複数の予測式の各々に対応した複数の前記予測差分値のデータ列を取得するステップと、複数の予測差分値のデータ列を評価するステップと、当該評価ステップの評価結果に基づき、上述（４）のステップにおける所定の予測式を、複数の予測式の中から選択するステップと、を更に設けることができる。
【００２８】  また、本発明の符号化データ生成方法では、複数の予測式の中に、０を予測値とする予測式を含めている。
通常は、この予測式を用いて効果的なデータ圧縮が得られる。
【００２９】  上述の複数の予測式には、着目する偏角に先行する少なくとも一つの偏角をパラメータとして用いた関数によって構成された予測式が少なくとも一つ含まれ得る。
また、本発明の符号化データ生成方法では、複数の予測式の中に、一つ前のノードの偏角を予測値とする予測式を含めている。
【００３０】  緩やかなカーブ周辺でこの予測式を用いると、効果的なデータ圧縮が得られる。
また、本発明の符号化データ生成方法では、複数の予測式の中に、先行する複数の偏角の平均又は加重平均を予測値とする予測式を含めている。
【００３１】  緩やかなカーブ周辺でこの予測式を用いると、効果的なデータ圧縮が得られる。
また、本発明の符号化データ生成方法では、複数の予測式の中に、一つ前のノードの偏角の正負を逆にした角度を予測値とする予測式を含めている。
【００３２】  リサンプル形状がジグザグにトレースした場合は、この予測式を用いることにより、効果的なデータ圧縮が得られる。
また、本発明の符号化データ生成方法では、偏角のデータ列に含まれる全ての偏角を予測差分値に変換して予測差分値のデータ列を評価し、評価結果に基づいて、全ての偏角を予測差分値に変換する予測式を選択するようにしている。
【００３３】  線形対象物の形状データ単位で予測式を動的に変えて、データ圧縮効果を高めることができる。
また、本発明の符号化データ生成方法では、線形対象物の一部区間に対応する偏角のデータ列に含まれる偏角を予測差分値に変換して予測差分値のデータ列を評価し、評価結果に基づいて、前記一部の区間に対応する偏角を予測差分値に変換する予測式を選択するようにしている。
【００３４】  線形対象物の形状データの途中で予測式を動的に変えて、データ圧縮効果をさらに高めることができる。
また、本発明の符号化データ生成方法では、偏角のデータ列を、偏角の状態遷移のパターンによって区分し、前記パターンの単位で、偏角を予測差分値に変換する予測式を選択するようにしている。
【００３５】  この方式を採る場合は、各パターンに適した予測式を選択することができる。
また、本発明の符号化データ生成方法では、偏角のデータ列を、所定数のデータを含むブロックに区分し、前記ブロックの単位で、偏角を予測差分値に変換する予測式を選択するようにしている。
【００３６】  この方式を採る場合は、符号化データ中に、選択した予測式が一定個数単位に出現するため、符号化データへのマーカーコードの挿入が不要になる。
また、本発明の符号化データ生成方法では、偏角のデータ列を、リサンプルのリサンプル長の変更点に合わせてブロックに区切り、このブロックの単位で、偏角を予測差分値に変換する予測式を選択するようにしている。
【００３７】  リサンプル長の変更点では形状データの特徴が変化するケースが多い。そのため、この方式を採る場合は、形状データの特徴に合った予測式の選択ができる。
また、本発明の符号化データ生成方法では、偏角のデータ列の着目する偏角に先行する所定数の偏角の予測差分値のデータ列に対する評価結果に応じて、着目する偏角を予測差分値に変換する予測式を選択するようにしている。
【００３８】  この方式は、エンコード側・デコード側の双方が、プログラムでルール化することにより実現できる。
ここで、複数の選択式を用いて、所定数の偏角を複数の予測差分値のデータ列に変換し、所定の選択式に基づく予測差分値のデータ列に対する評価結果が所定の要件を満たす場合のみ、現在使用されている予測式を所定の予測式に変更したうえで、着目する偏角を予測差分値に変換するようにしてもよい。
【００３９】  また、着目する偏角またはブロックにおいて、前後の偏角またはブロックでの予測式の選択状況を参考にして予測式を選択するようにしてもよい。
また、着目する偏角またはブロックにおいて、前後の偏角またはブロックで採用する予測式とは異なる予測式を選出する場合、着目する偏角またはブロックでの予測差分値列の評価基準である評価値に対しペナルティ値を加算するようにしてもよい。各予測式の発生頻度に応じてこのペナルティ値を設定することができる。
【００４０】  また、本発明の符号化データ生成方法では、予測差分値のデータ列の評価を、データ列に含まれる０の数によって行い、最も０の数が多くなる予測式を選択するようにしている。
【００４１】  そのため、データが０に集中し、可変長符号化によるデータ圧縮効果が向上する。
また、本発明の符号化データ生成方法では、予測差分値のデータ列の評価を、データ列に含まれる予測差分値の統計値（分散、標準偏差等）によって行い、分散または標準偏差が最も小さくなる予測式を選択するようにしている。
【００４２】  そのため、データが統計的に偏り、可変長符号化によるデータ圧縮効果が向上する。
また、本発明の符号化データ生成方法では、予測差分値ごとの評価値を、予測差分値の出現頻度に応じてあらかじめ設定し、予測差分値のデータ列の評価を、データ列に含まれた予測差分値の評価値の合計値によって行うようにしている。
【００４３】  予測差分値の発生頻度を評価値とするときは、合計値が最も大きい予測式を選択する。
また、予測差分値の符号長を評価値とするときは、合計値が最も小さい予測式を選択する。
【００４４】  また、本発明では、符号化データ生成装置に、線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表した各ノードの位置情報を配列して偏角のデータ列を生成する形状データリサンプル処理部と、このデータ列の偏角を、予測値との差分を示す予測差分値に変換したときの予測差分値のデータ列を評価し、評価結果に基づいて、予測値を算出する予測式を複数の予測式の中から選択する予測式決定部と、形状データリサンプル処理部が生成したデータ列に含まれる偏角を、予測式決定部が決定した予測式を用いて算出した予測値との予測差分値に変換して、その予測差分値のデータ列を可変長符号化する可変長符号化処理部とを設けている。
【００４５】  この装置では、前述する符号化データ生成方法を実施して符号化データのデータ量を効率的に圧縮することができる。
また、本発明では、符号化データ復元装置に、線形対象物の位置情報を表す、可変長符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する符号化データ復号部と、復号化された形状データの情報から、予測値の算出に用いた予測式を決定する予測式判定部と、予測式判定部が決定した予測式を用いて予測値を算出し、符号化データ復号部が復号化した予測差分値のデータ列から、線形対象物のノードの位置情報を再現する形状データ復元部とを設けている。
【００４６】  この装置では、線形対象物の位置情報の符号化データから、線形対象物の位置情報を再現することができる。
更に本発明は、線形対象物を符号化して得られる符号化データの生成をコンピュータに実行させるためのプログラムをも含み、当該プログラムは、線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成する手順と、偏角のデータ列を、各ノードの位置データの予測値との差分を示す予測差分値に変換したときの予測差分値のデータ列を評価する手順と、評価結果に基づいて、予測値を算出する予測式を複数の予測式の中から選択する手順と、形状データリサンプル処理部が生成した偏角のデータ列に含まれる偏角を、前記決定された予測式を用いて算出した予測値との予測差分値に変換して、予測差分値のデータ列を可変長符号化する手順と、を前記コンピュータに実行させる。
【００４７】  更に本発明は、線形対象物を表わす符号化データの復号化をコンピュータに実行させるためのプログラムをも含み、当該プログラムは、線形対象物の位置情報を表す可変長符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する手順と、復号化された形状データから、予測値の算出に用いた予測式を決定する手順と、決定された予測式を用いて予測値を算出し、復号化された予測差分値のデータ列から、線形対象物のノードの位置情報を再現する手順と、を前記コンピュータに実行させる。本発明の符号化データ生成方法は、符号化データの生成に当たって、効果的にデータを圧縮することができる。
【００４８】  また、本発明の装置は、この符号化データ生成方法を実施して、線形対象物の形状データを、効果的にデータを圧縮して符号化することができ、また、この符号化データから元の形状データを復元することができる。
【図面の簡単な説明】
【００４９】
【図１】本発明の実施形態における符号化データ生成方法を模式的に説明する図である。
【図２】道路形状データの偏角列を示す図である。
【図３】ジグザグ現象を説明する図である。
【図４】本発明の実施形態における対象道路単位選択方式での符号化データ生成方法の手順を示すフロー図である。
【図５】本発明の実施形態における符号化データ生成方法でのリサンプル及び偏角列生成手順を示すフロー図である。
【図６】本発明の実施形態における符号化データ生成方法での評価値算出手順を示すフロー図である。
【図７】発生頻度を記載したハフマンテーブルの例である。
【図８】本発明の実施形態における対象道路単位選択方式で生成した符号化データのデータ構成例である。
【図９】本発明の実施形態における対象道路単位選択方式で生成した符号化データの復号手順を示すフロー図である。
【図１０】本発明の実施形態におけるパターン単位選択方式での符号化データ生成方法の手順を示すフロー図である。
【図１１】本発明の実施形態におけるパターン単位選択方式で生成した符号化データのデータ構成例である。
【図１２】本発明の実施形態におけるパターン単位選択方式で生成した符号化データの復号手順を示すフロー図である。
【図１３】本発明の実施形態におけるブロック単位選択方式での符号化データ生成方法の手順を示すフロー図である。
【図１４】本発明の実施形態におけるブロック単位選択方式で生成した符号化データのデータ構成例である。
【図１５】本発明の実施形態におけるブロック単位選択方式で生成した符号化データの復号手順を示すフロー図である。
【図１６】は本発明の実施形態におけるリサンプル長連動方式での符号化データ生成方法の手順を示すフロー図である。
【図１７】本発明の実施形態におけるリサンプル長連動方式で生成した符号化データのデータ構成例である。
【図１８】本発明の実施形態におけるリサンプル長連動方式で生成した符号化データの復号手順を示すフロー図である。
【図１９】本発明の実施形態における逐次選択方式での符号化データ生成方法の手順を示すフロー図である。
【図２０】本発明の実施形態における逐次選択方式で生成した符号化データのデータ構成例である。
【図２１】本発明の実施形態における逐次選択方式で生成した符号化データの復号手順を示すフロー図である。
【図２２】予測式によって得られた評価値と、予測式の変更に伴う変更ペナルティの総合評価方法を示す図である。
【図２３】予測式の変更に伴う変更ペナルティを動的に変動させる方法を示す図である。
【図２４】本発明の実施形態における情報送信装置及び情報活用装置の構成を示すブロック図である。
【図２５】本発明の実施形態におけるプローブカー車載機及びプローブ情報収集センタの構成を示すブロック図である。
【図２６】位置データを統計的に偏りを持つデータに変換する方法を説明する図である。
【図２７】可変長符号化に用いる符号表を示す図である。
【図２８】道路形状の曲率によるリサンプル長の変更を説明する図である。
【発明を実施するための最良の形態】
【００５０】  本発明の実施形態における符号化データ生成方法では、線形対象物の一例であるデジタル地図の道路形状を符号化して符号化データを生成するため、大別して、
（ａ）道路の曲率半径に応じたリサンプル長での道路形状のリサンプル
（ｂ）サンプリング点（ノード）における位置データの偏角θへの変換
（ｃ）偏角θで表した位置データの統計的に偏りを持つ値への変換
（ｄ）変換した値の可変長符号化
の順序で符号化データを生成する。【００５１】  （ａ）の道路形状のリサンプルは、特開２００３−２３３５７号公報に記載されている方法で行い、線形対象物をリサンプルして複数のノードを設定する。また、（ｂ）の偏角θへの変換は、特開２００３−２３３５７号公報に記載されている方法で、各ノードの位置データを角度成分で表した後、この角度成分を偏角θに変換する。図２（ａ）、（ｂ）、（ｃ）は、対象道路Ａ、Ｂ、Ｃの形状データの各ノードにおける位置データを偏角θで表した（偏角の）データ列（以下、「偏角列」と言う）を示している。各行は１０個のデータから成り、そのデータ番号を左端に表示している。偏角列の中の＜＞で囲んだ数字は、リサンプル長の量子化コードを示すリサンプル長変更コードであり、その右に続く数値は、そのコードのリサンプル長でリサンプルして得られた各ノードの位置データを偏角θ（ｄｅｇ）で表したものである。各ノードの位置データが一つ前のノードからの偏角で表わされ、集まって偏角のデータ列が生成される。【００５２】  （ｃ）における位置データの統計的に偏りを持つ値への変換は、位置データの値を予測する予測値Ｓｊの算出式（予測式）を適応的に用いてＳｊを算出し、偏角列の偏角θを予測値Ｓｊとの差分値（予側差分値）に変換する処理である。【００５３】  （ｄ）の可変長符号化は、予測差分値列に変換した形状データの予測差分値（予測誤差）を可変長符号化する処理であり、特開２００３−２３３５７号公報に記載されている方法で行う。【００５４】  従って、この符号化データ生成方法は、（ｃ）の位置データの変換処理に特徴を有している。
（ｃ）の位置データの変換処理では、予測値Ｓｊを予測するため、次の４つの予測式（φ＝１、φ＝２、φ＝３、φ＝４）のいずれかを使用する。これらの式は前もって用意されており、所定のメモリなどに記録されている。
・φ＝１；予測式Ｓｊ＝０
即ち、各ノードｊの位置データを偏角θｊで表し、予測値は０である。
・φ＝２；予測式Ｓｊ＝θｊ−１
即ち、各ノードｊの位置データを（θｊ−θｊ−１）で表す。
・φ＝３；予測式Ｓｊ＝（θｊ−１＋θｊ−２）／２
即ち、各ノードｊの位置データを｛θｊ−（θｊ−１＋θｊ−２）／２｝で表す。
・φ＝４；予測式Ｓｊ＝−θｊ−１
即ち、各ノードｊの位置データを（θｊ＋θｊ−１）で表す。【００５５】  φ＝２またはφ＝３は、図２の偏角列において、下線を引いたカーブ箇所の位置データを変換するときに用いると圧縮効率が高い。
φ＝２、φ＝３、φ＝４は、着目する偏角に先行する少なくとも一つの偏角をパラメータとして用いた関数によって構成されるものである。【００５６】  また、φ＝２は、着目する偏角の一つ前の偏角を予測値としている。
また、φ＝３は、前記着目する偏角に先行する二つの偏角の平均を予測値としている。しかし、先行する偏角の個数は任意であり、（ａθｊ−１＋ｂθｊ−２）／（ａ＋ｂ）の如き加重平均を予測値としてもよい（ａ、ｂは０より大きい実数）。【００５７】  また、φ＝４は、着目する偏角の一つ前のノードの偏角の正負を逆にした角度を予測値としている。
また、図３に示すように、道路形状（点線）の折り曲がり箇所で、リサンプル形状（実線）がジグザグ状を呈する場合があり、φ＝４は、こうした箇所の位置データを変換するときに用いると圧縮効率が高い。このジグザグ現象は、リサンプル時の角度分解能δを設定して道路形状をトレースすると、利用できる角度に限りがあるため、必然的に発生する（角度の量子化に伴う必然性）。図２（ａ）の偏角列において、ジグザグ現象が発生している箇所の位置データを斜体文字で表示している。【００５８】  また、φ＝１は、道路形状が直線に近い場合（カーブがあってもすぐ終わる場合や、ほぼ直線でたまに角度を修正するような場合を含む）に圧縮効率が高く、通常の道路形状の位置データを変換するときには、このφ＝１を使用する。【００５９】  偏角θの変換処理に使用する予測値Ｓｊの予測式は、道路形状に応じて動的に選択する。予測式の選択には、
（１）対象道路ごとに予測式を動的に選択する方式（「対象道路単位選択方式」と呼ぶ）
（２）対象道路の偏角列のパターンを検出し、そのパターン単位に予測式を選択する方式（「パターン単位選択方式」と呼ぶ）
（３）対象道路の偏角列を一定データ数のブロックに分け、ブロック単位に予測式を選択する方式（「ブロック単位選択方式」と呼ぶ）
（４）対象道路の偏角列中でリサンプル長変更コードが変わるごとに予測式を選択する方式（「リサンプル長連動方式」と呼ぶ）
（５）対象道路の偏角列中で着目する位置データの上流側Ｎ個の位置データにおける状況から、プログラム規則に従って予測式を選択する方式（「逐次選択方式」と呼ぶ）
等の方式が考えられる。どの方式を用いるかは、予め送信側と受信側で決めておく必要がある。【００６０】  図１は、リサンプル長連動方式で選択される予測式と道路形状との関係を模式的に示している。道路形状を点線で示し、リサンプル形状を実線で示し、リサンプル長の変更箇所を＜Ｍ１＞、＜Ｍ２＞、＜Ｍ３＞で示している。道路形状が直線的である範囲Ａではφ＝１が選択され、ジグザグ現象が発生する範囲Ｂではφ＝４が選択され、カーブしている範囲Ｃではφ＝２またはφ＝３が選択され、また、そのいずれとも特定できない道路形状の範囲Ｄではφ＝１が選択される。【００６１】  次に、各方式での処理について詳しく説明する。
（１）対象道路単位選択方式
図４のフロー図は、対象道路単位選択方式での処理手順を示している。デジタル地図データベースから対象道路の形状データを取得し（ステップ１）、リサンプルで生成したノードの位置データを偏角θで表し、偏角列を生成する（ステップ２）。【００６２】  ステップ２の処理は、詳しくは図５に示す手順で行う。即ち、各リサンプル長の各偏角における角度分解能δを予め決定し（ステップ２１）、また、対象道路の形状データを曲率関数に変換して（ステップ２２）、曲率から各区間のリサンプル長Ｌを決定する（ステップ２３）。次いで、対象道路を、リサンプル長Ｌ、及び、偏角に応じた角度分解能δの代表角度によってリサンプルし（ステップ２４）、対象道路の形状データを、リサンプル区間長変更コードと偏角量子化値とを羅列した偏角列に変換する（ステップ２５）。【００６３】  偏角列の生成が終了すると、対象道路の偏角列全体に対し、予測式φ＝１、φ＝２、φ＝３及びφ＝４を適用して、偏角列の偏角θを予測値Ｓｊとの差分値（予測差分値）に変換し、どの予測式が最適であるかを評価する（ステップ３）。ステップ３の処理は、詳しくは図６に示す手順で行う。即ち、評価対象の偏角列（対象道路単位選択方式の場合は対象道路の偏角列全体）を取得し（ステップ３１）、予測式をφ＝１から順に用いて（ステップ３２）、各々の予測式で予測値Ｓｊを算出し、偏角列の偏角θを予測差分値（＝Δθｊ＝θｊ−Ｓｊ）で表した予測差分値列に変換し（ステップ３３）、この偏角列の評価値を算出する（ステップ３４）。【００６４】  評価値の算出は、次の（ｉ）〜（ｉｉｉ）のように行う。
（ｉ）予測差分値列に含まれる０の数を評価値として、０が多い予測差分値列程、高い評価を与える（最も０を多く含む予測式を選択する）。
（ｉｉ）予測差分値列に含まれるデータの統計値（例えば分散、標準偏差等）の計算値を評価値として、分散または標準偏差が小さい予測差分値列程、高い評価を与える。
（ｉｉｉ）予測差分値列に現れるデータに、あらかじめ出現頻度に応じた得点を設定し、評価対象の予測差分値列に現れるデータの得点を加算した累積値を評価値として、この累積値に応じた評価を与える。図７のハフマンテーブルでは、各角度の発生頻度（または発生確率）が記述され、発生頻度が高い角度程、短い符号が割り当てられている。評価対象の予測差分値列に現れる角度に応じて、このテーブルの該当する発生頻度の値を加算する場合は、その累積値を評価値として、累積値が高い予測差分値列程、高い評価を与える。また、評価対象の予測差分値列に現れる角度に応じて、その角度の符号長を加算する場合は、その累積値を評価値として、累積値が小さい予測差分値列程、高い評価を与える。なお、こうした出現頻度に対応する得点表をあらかじめ持つことにより、ハフマン符号化以外の可変長符号化を行う場合にも、（ｉｉｉ）による評価が可能である。【００６５】  全ての予測式を用いてステップ３３、ステップ３４の処理を行い、それが終了すると（ステップ３５、３６）、最も評価値の良い予測式を決定する（ステップ３７）。すなわち、予測式φ＝１、φ＝２、φ＝３及びφ＝４の各々について、対応する予測差分値のデータ列が生成され、これらのデータ列が評価される。【００６６】  こうして最も評価値の良い予測式を選出して、偏角列の偏角θを、その予測式で算出した予測値との予測差分値に変換し（ステップ４）、予測差分値列に変換した形状データ全体を可変長符号化圧縮する（ステップ５）。得られた符号化データに、使用した予測式を定義付ける（ステップ６）。【００６７】  図８は、対象道路単位選択方式により生成した符号化データのデータ構成を示している。ここでは、対象道路の形状データ本体の前に、使用した予測式を表すデータが挿入されている。【００６８】  また、図９のフロー図は、この符号化データから対象道路の形状データを再現する手順を示している。符号化データから可変長復号化処理した形状データを取り出し（ステップ４１）、ヘッダを参照して予測式を決定し（ステップ４２）、その予測式に従って、形状データから読み取った角度データを偏角に変換し（ステップ４３）、対象道路の形状データを再現する（ステップ４４）。
（２）パターン単位選択方式
図１０のフロー図は、パターン単位選択方式での処理手順を示している。形状データの取得（ステップ５１）や、リサンプル及び偏角列変換処理（ステップ５２）の手順は、対象道路単位選択方式での処理手順（図４、図５）と同じである。【００６９】  得られた偏角列をスキャンし、同一正負符号の非０のデータがＰ個以上連続する、φ＝２またはφ＝３を適用すべき曲線パターン（図２の下線部分）や、絶対値が同一値で正負符号が交互に反転するデータがＱ個以上連続する、φ＝４を適用すべきジグザグパターン（図２（ａ）の斜字部分）を抽出し、偏角列のデータを、各パターン別のグループ、何れのパターンにも属さない、φ＝１を適用すべきグループに分け（ステップ５３）、グループ単位に最も評価値が良い予測式を選出して、偏角列を予測差分値列に変換する（ステップ５４）。このとき、グループに対応する最良の予測式が一意に決まらない場合は、図６の手順により、そのグループの偏角列に複数の予測式を適用し、最も評価値の良い予測式を決定する。【００７０】  次に、予測差分値列に変換した形状データ全体を可変長符号化圧縮し（ステップ５５）、得られた符号化データに、使用した予測式をグループ単位で定義付ける（ステップ５６）。【００７１】  本実施形態では、偏角の状態遷移のパターンに対応したブロック（グループ）に、偏角のデータ列を区分している。そしてブロック毎に最適な予測式が選択される。
図１１は、パターン単位選択方式により生成した符号化データのデータ構成を示している。ここでは、対象道路の形状データ本体の前に、最初のグループで使用した予測式を表す予測式初期値が挿入され、以降の各グループの位置データに先行して、予測式の挿入を示す予測式マーカと、そのグループで使用した予測式の予測式番号とが挿入されている。【００７２】  また、図１２のフロー図は、この符号化データから対象道路の形状データを再現する手順（符号化データの復号化方法）を示している。この符号化データから可変長復号化処理した形状データを取り出し（ステップ６１）、その形状データから読み取る角度データの番号を初期値に設定し、また、最初に使用する予測式を予測式初期値で表された予測式に設定し（ステップ６２）、形状データから該当する角度データを読み取り（ステップ６３）、その角度データの前に予測式変更コードが挿入されているか否かを識別する（ステップ６４）。予測式変更コードが挿入されていなければ、設定した予測式をそのまま使用して（ステップ６６）、その予測式に従って、角度データを偏角に変換する（ステップ６７）。また、予測式変更コードが挿入されていれば、予測式を、そのコードで指定された新たな予測式に変更し（ステップ６５）、その予測式に従って、角度データを偏角に変換する（ステップ６７）。こうした処理を角度データの全てについて行い（ステップ６８、ステップ６９）、対象道路の形状データを再現する（ステップ７０）。【００７３】  本方式では、線形対象物（道路形状）全体ではなく、その一部区間に対応する偏角のデータ列が予測差分値のデータ列に変換され、予測差分値のデータ列に対する評価結果に基づいて、当該一部区間に対応する偏角を予測差分値に変換する最適な予測式が選択されるものである。この思想は、以下の（３）〜（５）の方式でも共通して採用されている。
（３）ブロック単位選択方式
図１３のフロー図は、ブロック単位選択方式での処理手順を示している。形状データの取得（ステップ７１）や、リサンプル及び偏角列変換処理（ステップ７２）の手順は、対象道路単位選択方式での処理手順（図４、図５）と同じである。【００７４】  例えば、図２に示す偏角列の１行、１０データを１ブロックとして、このブロック単位の偏角列に対し、予測式φ＝１、φ＝２、φ＝３及びφ＝４を適用して、偏角列の偏角θを予測差分値に変換し、どの予測式が最適であるかを評価する（ステップ７３）。評価の仕方は、対象道路単位選択方式の場合（図６）と同じである。ブロック単位に最も評価値が良い予測式を選出して、偏角列を予測差分値列に変換し（ステップ７４）、予測差分値列に変換した形状データ全体を可変長符号化圧縮し（ステップ７５）、得られた符号化データに、使用した予測式をブロック単位で定義付ける（ステップ７６）。【００７５】  図１４は、ブロック単位選択方式により生成した符号化データのデータ構成を示している。ここでは、対象道路の形状データ本体の前に、最初のブロックで使用した予測式を表す予測式初期値が挿入され、以降の各ブロックの位置データに先行して予測式番号が挿入されている。なお、予測式番号の挿入位置は、ブロックに含まれるデータ数により自動的に決まるので、予測式マーカの挿入は不要である。【００７６】  また、図１５のフロー図は、この符号化データから対象道路の形状データを再現する手順を示している。この符号化データから可変長復号化処理した形状データを取り出し（ステップ８１）、その形状データから読み取るブロックの番号を初期値に設定し、また、最初に使用する予測式を予測式初期値で表された予測式に設定し（ステップ８２）、形状データから該当するブロックの角度データを読み取り（ステップ８３）、そのブロックに定義された予測式に従って、角度データを偏角に変換する（ステップ８４）。こうした処理をブロックの全てについて行い（ステップ８５、ステップ８６）、対象道路の形状データを再現する（ステップ８７）。【００７７】  本実施形態では、１ブロックに含まれる偏角のデータの所定数は１０としたが、この数は任意に変更することができる。
（４）リサンプル長連動方式
図１６のフロー図は、リサンプル長連動方式での処理手順を示している。形状データの取得（ステップ９１）や、リサンプル及び偏角列変換処理（ステップ９２）の手順は、対象道路単位選択方式での処理手順（図４、図５）と同じである。【００７８】  図２に示す偏角列において、同一リサンプル長でリサンプルされた、リサンプル長変更コードと次のリサンプル長変更コードとの間（二つのリサンプルのリサンプル長の変更点）に在る角度データをブロック（＜＞で囲まれた数字ごとのブロック）とし、このブロック単位の偏角列に対し、予測式φ＝１、φ＝２、φ＝３及びφ＝４を適用して、偏角列の偏角θを予測差分値に変換し、どの予測式が最適であるかを評価する（ステップ９３）。評価の仕方は、対象道路単位選択方式の場合（図６）と同じである。ブロック単位に最も評価値が良い予測式を選出して、偏角列を予測差分値列に変換し（ステップ９４）、予測差分値列に変換した形状データ全体を可変長符号化圧縮し（ステップ９５）、得られた符号化データに、使用した予測式をブロック単位で定義付ける（ステップ９６）。【００７９】  図１７は、リサンプル長連動方式により生成した符号化データのデータ構成を示している。ここでは、対象道路の形状データ本体の前に、最初のブロックで使用した予測式を表す予測式初期値が挿入され、以降の各ブロックで使用した予測式の予測式番号は、同一リサンプル長でリサンプルされた角度データの開始位置に挿入される区間長マーカに続く区間長情報の中で規定されている。【００８０】  また、図１８のフロー図は、この符号化データから対象道路の形状データを再現する手順を示している。この符号化データから可変長復号化処理した形状データを取り出し（ステップ１０１）、その形状データから読み取る同一リサンプル長のブロックの番号を初期値に設定し（ステップ１０２）、リサンプル長が同一のブロックに含まれる全ての角度データ、及び、リサンプル長変更コードに付随している予測式を取得し（ステップ１０３）、予測式に従って、ブロック内の角度データを偏角に変換する（ステップ１０４）。こうした処理をリサンプル長が同一のブロックの全てについて行い（ステップ１０５、ステップ１０６）、対象道路の形状データを再現する（ステップ１０７）。
（５）逐次選択方式
図１９のフロー図は、逐次選択方式での処理手順を示している。形状データの取得（ステップ１１１）や、リサンプル及び偏角列変換処理（ステップ１１２）の手順は、対象道路単位選択方式での処理手順（図４、図５）と同じである。【００８１】  偏角列から抽出する角度データの番号を初期値に設定し、また、最初に使用する予測式をφ＝１に設定する（ステップ１１３）。偏角列から該当する角度データ及びその上流側の所定数たるＰ個のサンプルを抽出し（ステップ１１４）、抽出したデータから成る偏角列に対し、予測式φ＝１、φ＝２、φ＝３及びφ＝４を適用して、偏角列の偏角θを予測差分値に変換し、最も評価値が良い予測式φｎｅｗを選出する（ステップ１１５）。評価の仕方は、対象道路単位選択方式の場合（図６）と同じである。【００８２】  この評価結果を踏まえ、予測式の変更条件に照らして、設定済みの予測式を変更する必要があるか否かを判定する（ステップ１１６）。すなわち、本方式においては、符号化の対象となっている位置データの上流の形状を参照しつつ、当該位置データに使用される最適な予測式を変更すべきか否かが判断される。【００８３】  この変更条件として、例えば、次の（ｉ）または（ｉｉ）のような条件を設定する。
（ｉ）現在使用している予測式φと予測式φｎｅｗとの間で評価値差Δが所定値より大きい場合は予測式を変更する。
（ｉｉ）現在使用している予測式φよりも予測式φｎｅｗの方に高い評価が与えられる状態がＱ回以上続いた場合は予測式を変更する。【００８４】  この変更条件を満たしていなければ、設定済みの予測式をそのまま使用して（ステップ１１８）、角度データを予測差分値に変換する（ステップ１１９）。また、変更条件を満たしている場合は、予測式を予測式φｎｅｗに変更して（ステップ１１７）、角度データを予測差分値に変換する（ステップ１１９）。こうした処理を全ての角度データに対して行い（ステップ１２０、ステップ１２１）、予測差分値列に変換した形状データ全体を可変長符号化圧縮する（ステップ１２２）。【００８５】  この予測式変更の規則は、この符号化処理を規定するプログラムの中でルール化されている。
本実施形態では、着目する偏角に先行する所定数（Ｐ）の偏角の予測差分値のデータ列に対する評価結果に応じて、着目する偏角を予測差分値に変換する予測式が選択される。さらに、この評価結果が所定の要件を満たす場合のみ、現在使用されている予測式を所定の予測式に変更するように構成している。【００８６】  図２０は、逐次選択方式により生成した符号化データのデータ構成を示している。この符号化データには、予測式を指定する情報が含まれていないため、データ量も少ないものとなっている。デコードの際に使用する予測式は、この符号化データのデコードを規定するプログラムのルールに基づいて選択される。【００８７】  図２１のフロー図は、この符号化データから対象道路の形状データを再現する手順を示している。この符号化データから可変長復号化処理した形状データを取り出し（ステップ１３１）、その形状データから読み取る角度データの番号を初期値に設定し、また、最初に使用する予測式をφ＝１に設定する（ステップ１３２）。形状データから該当する角度データ及びその上流側Ｐ個のサンプルを読み取り（ステップ１３３）、読み取ったデータから成る偏角列に対し、予測式φ＝１、φ＝２、φ＝３及びφ＝４を適用して、偏角列の偏角θを予測差分値に変換し、最も評価値が良い予測式φｎｅｗを選出する（ステップ１３４）。次に、この評価結果を踏まえ、予測式の変更条件に照らして、設定済みの予測式を変更する必要があるか否かを判定する（ステップ１３５）。変更条件を満たしていなければ、設定済みの予測式をそのまま使用し（ステップ１３７）、その予測式に従って、角度データを偏角に変換する（ステップ１３８）。また、変更条件を満たしている場合は、予測式を予測式φｎｅｗに変更し（ステップ１３６）、その予測式に従って、角度データを偏角に変換する（ステップ１３８）。こうした処理を全ての角度データに行い（ステップ１３９、ステップ１４０）、対象道路の形状データを再現する（ステップ１４１）。【００８８】  このように、道路形状の符号化データを生成する場合に、位置データを予測差分値に変換するための予測値の算出に使用する予測式を、道路ごとに、あるいは、道路の部分ごとに、適応的に選択することにより、符号化データのデータ量を効率的に圧縮することができる。【００８９】  ところで、上述の（１）〜（４）各々の方式において、１つの形状データにおいて、予測式を変更する場合、「予測式の変更を明示し、予測式ＩＤを指定する」という情報をデータに盛り込むことが必要となる。これは、データ量増加の１要因となり得る。さらに、「その道路区間全般では、概して予測式１が良いが、瞬間的に他の予測式が良い」場合など、頻繁に予測式を変えるのもあまり望ましくはない。少なくとも予測式を変更する場合は、「新たな予測式によって得られるデータ量削減効果」が「予測式の変更に伴うロス」を上回る必要があることが望ましい。【００９０】  そこで、「各予測式によって得られた評価値」に対し、「変更ペナルティ」を加算し、その総合評価によって「予測式を変更するか否か」を決定することが考えられる。言い換えると、予測式変更に対してヒステリシスを持たせることが考えられる。【００９１】  図��２は予測式によって得られた評価値と、予測式の変更に伴う変更ペナルティの総合評価方法を示す図である。
図２２（ａ）では、予測式を変更した方がデータ量が削減され、データ送信の効率が向上するので、予測式を変更する。一方、図２２（ｂ）では、変更しない方が送信効率がよいため、予測式は変更しない。【００９２】  また、データを区分けするブロックや偏角が増加すると、「どういう組合せが最も効率がよいのか？」という組合せ最適化問題が発生する。ブロックや偏角が増加するにつれ、最適解を簡便に、早く見つけるのは難しくなる。【００９３】  そこで、準最適解をすばやく見つけるための方法として、以下の２つの方式が考えられる。
（ｉ）発生頻度が高い予測式には、変更ペナルティを相対的に小さくし、発生頻度が低い予測式には、変更ペナルティを大きくする。発生頻度が低い予測式を採用した場合、次ブロックで他の予測式に変わる可能性が大きいので、発生頻度が低い予測式への変更を抑制する。【００９４】  （ｉｉ）普通は、一方向に順に処理していくので、着目するブロックの上流側の実績から下流側の状況を推定し、変更ペナルティを動的に変えていく。
さらに、圧縮率によって、最適な予測式の発生頻度が変わるものと考えられる。例えば、圧縮率を上げると偏角の規則性が無くなり、φ＝１が最適な式になる傾向がある。また、逆に圧縮率を下げると偏角の規則性が強まり、φ＝２や、φ＝３が最適な式になる傾向がある。【００９５】  よって、（ｉ）の場合、「形状データ全体に対して各予測式の評価値を一旦算出し、その評価値に応じて変更ペナルティを決定する」ような方法が良いと考えられる。
図２３は予測式の変更に伴う変更ペナルティを動的に変動させる方法を示す図である。【００９６】  図２４は、交通情報の対象道路を伝えるために、この符号化データ生成方法を実行する情報送信装置（符号化データ生成装置）２０と、提供された交通情報を活用する、車載用ナビゲーション装置やパーソナルコンピュータなどの情報活用装置（符号化データ復元装置）４０との構成を示している。情報送信装置２０は、渋滞情報や交通事故情報などが入力される事象情報入力部２１と、デジタル地図データベースＡ２２から交通情報の対象道路区間の道路形状データを抽出する形状データ抽出部２３と、形状データ抽出部２３で抽出された道路形状データをリサンプルしてノード位置データの偏角列を生成する形状データリサンプル処理部２６と、偏角列を予測差分値列に変換するための予測式を決定する予測式決定部２５と、予測式決定部２５が決定した予測式を用いて形状データの偏角を予測差分値に変換し、圧縮符号化する可変長符号化処理部２８と、圧縮符号化された道路形状データを蓄積して外部メディアに蓄積データを提供する圧縮データ蓄積部２７と、圧縮符号化された道路形状データを送信する形状データ送信部２９とを備えている。【００９７】  一方、情報活用装置４０は、提供された道路形状データを受信する形状データ受信部４１と、圧縮符号化されているデータを復号する符号化データ復号部４２と、予測差分値への変換時に使用された予測式を識別する予測式判定部４７と、予測式判定部４７が識別した予測式を用いて形状データを復元する形状データ復元部４３と、デジタル地図データベースＢ４６のデータを用いてマップマッチングを行い、ノード点で表された道路区間をデジタル地図上で特定するマップマチング部４５と、得られた情報を活用する情報活用部４４とを備えている。【００９８】  情報送信装置２０では、形状データ抽出部２３が対象道路の道路形状データを抽出し、形状データリサンプル処理部２６が、この道路形状データをリサンプルして、道路形状データの偏角列を生成する。予測式決定部２５は、前述する「対象道路単位選択方式」「パターン単位選択方式」「ブロック単位選択方式」「リサンプル長連動方式」あるいは「逐次選択方式」により、偏角列を予測差分値列に変換するための予測式を決定する。可変長符号化処理部２８は、予測式決定部２５が決定した予測式で予測値を算出し、偏角列の偏角から予測値を減じて予測差分値列を生成し、これを可変長符号化する。【００９９】  可変長符号化でデータ圧縮された道路形状データは、外部メディアに記録されて提供され、あるいは、形状データ送信部２９から送信される。
この道路形状データを受信した情報活用装置４０では、符号化データ復号部４２が、圧縮符号化されているデータを復号化する。予測式判定部４７は、復号化されたデータから、偏角をデコードするための予測式を識別し、形状データ復元部４３は、この予測式を用いて偏角列を再生し、偏角を緯度・経度データに変換して道路形状データを再現する。再現されたノードを繋ぐリサンプル形状は、情報活用装置４０の表示画面上にデジタル地図と重ねて表示される。【０１００】  また、この道路区間を正確に特定するために、マップマッチング部４５は、再現されたノード点の位置データとデジタル地図データベースＢ４６の地図データとのマップマッチングを行い、デジタル地図データ上で対象道路を特定する。情報活用装置４０は、カーナビ受信機または地図表示端末をも構成し得る。【０１０１】  また、図２５は、走行軌跡を伝えるために、この符号化データ生成方法を実行するプローブカー車載機（符号化データ生成装置）６０と、プローブ情報を収集するプローブ情報収集センタ（符号化データ復元装置）５０との構成を示している。プローブカー車載機６０は、ＧＰＳアンテナ７３から受信する情報やジャイロ７４の検知情報を基に自車位置を判定する自車位置判定部６１と、デジタル地図のデータベース６９と、自車の走行軌跡を蓄積する走行軌跡蓄積部６２と、走行軌跡をリサンプルしてノード位置データの偏角列を生成する走行軌跡形状リサンプル処理部６３と、偏角列を予測差分値列に変換するための予測式を決定する予測式決定部６８と、予測式決定部６８が決定した予測式を用いて走行軌跡形状データの偏角を予測差分値に変換し、圧縮符号化する可変長符号化処理部６４と、圧縮符号化された走行軌跡形状データを蓄積する圧縮データ蓄積部６５と、圧縮符号化された走行軌跡形状データを送信する走行軌跡送信部６６とを備えている。【０１０２】  一方、プローブ情報収集センタ５０は、プローブカー車載機６０から提供された走行軌跡形状データを受信する走行軌跡受信部５１と、圧縮符号化されている受信データを復号化する符号化データ復号部５２と、予測差分値への変換時に使用された予測式を識別する予測式判定部５５と、予測式判定部５５が識別した予測式を用いて走行軌跡形状を復元する走行軌跡形状復元部５３と、プローブカー車載機６０から収集した走行軌跡や計測情報を交通情報の生成に活用する走行軌跡計測情報活用部５４とを備えている。【０１０３】  プローブカー車載機６０の走行軌跡蓄積部６２には、自車位置判定部６１で検出された自車位置が走行軌跡として順次蓄積される。走行軌跡形状リサンプル処理部６３は、走行軌跡蓄積部６２に蓄積された走行軌跡データを読み出し、走行軌跡をリサンプルして、走行軌跡形状データの偏角列を生成する。予測式決定部６８は、前述する「対象道路単位選択方式」「パターン単位選択方式」「ブロック単位選択方式」「リサンプル長連動方式」あるいは「逐次選択方式」により、偏角列を予測差分値列に変換するための予測式を決定する。可変長符号化処理部６４は、予測式決定部６８が決定した予測式で予測値を算出し、偏角列の偏角から予測値を減じて予測差分値列を生成し、これを可変長符号化する。圧縮符号化���れたデータは、プローブ情報の送信時期に、プローブ情報収集センタ５０に送信される。また、このデータは、外部メディアに格納してプローブ情報収集センタ５０に提供される場合もある。【０１０４】  プローブ情報収集センタ５０では、符号化データ復号部５２が、プローブカー車載機６０から収集したデータを復号化する。予測式判定部５５は、復号化されたデータから、偏角をデコードするための予測式を識別し、走行軌跡形状復元部５３は、この予測式を用いて偏角列を再生し、偏角を緯度・経度データに変換して走行軌跡データを再現する。この走行軌跡の情報は、プローブカー車載機６０で計測された速度等の計測情報と併せて交通情報の生成に活用される。【０１０５】  このように、情報送信装置やプローブカー車載機は、本発明の符号化データ生成方法を用いて、対象道路や走行軌跡の符号化データを生成することにより、データ量を効率的に圧縮することができる。【０１０６】  プローブカー車載機６０とプローブ情報収集センタ５０の組み合わせより、プローブカーシステムが構築され、両者間でプローブカーシステムの情報伝達方法が達成されるが、当該方法は、本発明の符号化データの生成方法及び当該符号化データの復号化方法の組み合わせより達成される。【０１０７】  なお、上述では、符号化データ生成装置が、情報送信センタである情報送信装置２０又プローブカー車載機６０である例を示したが、これらは情報送信側における実施形態の例であり、情報を送信する事が出来る装置や端末であればどのような形態のものでもよい。さらに生成した符号化データを媒体に記録して、他の装置に提供することも可能である。また、符号化データ復元装置である情報活用装置４０やプローブ情報収集センタ５０もあくまで例であり、パーソナルコンピュータ、携帯端末等の情報を活用できる装置であればなんでもよい。もちろん、符号化データの復元が可能な情報収集センターや、センター側の装置でも同様の効果を得ることが出来る。さらに符号化されたデータが記録された媒体等を用いて、復元処理することにより、同様の効果を得ることは言うまでもない。【０１０８】  また、本発明は、線形対象物を符号化して得られる符号化データの生成をコンピュータに実行させるためのプログラムをも含み、当該プログラムは、線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成する手順と、偏角のデータ列を、各ノードの位置データを予測するための予測値との差分を示す予測差分値に変換したときの予測差分値のデータ列を評価する手順と、評価結果に基づいて、予測値を算出する予測式を複数の予測式の中から選択する手順と、形状データリサンプル処理部が生成した偏角のデータ列に含まれる偏角を、前記決定された予測式を用いて算出した予測値との予測差分値に変換して、予測差分値のデータ列を可変長符号化する手順と、を前記コンピュータに実行させる。このようなプログラムは、情報送信装置２０、プローブカー車載機６０に、種々の形式で組み込まれる。例えば情報送信装置２０、プローブカー車載機６０内又はこれらの外部の装置内の所定のメモリにプログラムを記録することができる。また、ハードディスクのような情報記録装置や、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ、メモリカードのような情報記録媒体にプログラムを記録してもよい。また、ネットワーク経由により当該プログラムをダウンロードするようにしてもよい。【０１０９】  更に本発明は、線形対象物を表わす符号化データの復号化をコンピュータに実行させるためのプログラムをも含み、当該プログラムは、線形対象物の位置情報を表す可変長符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する手順と、復号化された形状データから、予測値の算出に用いた予測式を決定する手順と、決定された予測式を用いて予測値を算出し、復号化された予測差分値のデータ列から、線形対象物のノードの位置情報を再現する手順と、を前記コンピュータに実行させる。【０１１０】  このようなプログラムも、情報活用装置４０、プローブ情報収集センタ５０に、種々の形式で組み込まれる。例えば情報活用装置４０、プローブ情報収集センタ５０内又はこれらの外部の装置内の所定のメモリにプログラムを記録することができる。また、ハードディスクのような情報記録装置や、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ、メモリカードのような情報記録媒体にプログラムを記録してもよい。また、ネットワーク経由により当該プログラムをダウンロードするようにしてもよい。【０１１１】  また、本発明の情報送信装置２０と情報活用装置４０又はプローブカー車載機６０とプローブ情報収集センタ５０の組み合わせより、地図データ配信システムが構成される。
また、本発明の符号化データ生成方法に沿ったアルゴリズム（プログラム）を、地図データ本体に各種地図情報に対応した地図データが記録された記録媒体に記録することができる。これにより、地図データ本体自体を圧縮符号化することが可能となる。【０１１２】  尚、上述の実施形態においては、線形対象物が位置参照用の道路形状である例を説明したが、線形対象物は道路形状に限られない。「線形対象物」とは直線、曲線など種々の形態を含む細長い形状のものを総て含み、地図上の線形形状によって表わせる地理情報総てを含み得る。更に、指紋等地図とは関係ないが、線形形状によって表わされるもの総てをも含まれる。【０１１３】  また、本発明を詳細にまた特定の実施態様を参照して説明したが、本発明の精神と範囲を逸脱することなく様々な変更や修正を加えることができることは当業者にとって明らかである。【０１１４】  本出願は、２００３年１０月１７日出願の日本特許出願（特願２００３−３５７７３０）に基づくものであり、その内容はここに参照として取り込まれる。
【産業上の利用可能性】
【０１１５】  本発明の符号化データ生成方法は、デジタル地図の道路形状や河川、鉄道線路、行政境界線、等高線などの位置情報を表す符号化データを生成して、伝送・蓄積・保存するときなどに利用することができ、また、デジタル地図以外に、各種の図形や指紋などの線形対象物を表す符号化データを生成して、伝送・蓄積・保存するときなどにも適用することができる。
【図１】
2005039058.tif 000002
【図２】
2005039058.tif 000003
【図３】
2005039058.tif 000004
【図４】
2005039058.tif 000005
【図５】
2005039058.tif 000006
【図６】
2005039058.tif 000007
【図７】
2005039058.tif 000008
【図８】
2005039058.tif 000009
【図９】
2005039058.tif 000010
【図１０】
2005039058.tif 000011
【図１１】
2005039058.tif 000012
【図１２】
2005039058.tif 000013
【図１３】
2005039058.tif 000014
【図１４】
2005039058.tif 000015
【図１５】
2005039058.tif 000016
【図１６】
2005039058.tif 000017
【図１７】
2005039058.tif 000018
【図１８】
2005039058.tif 000019
【図１９】
2005039058.tif 000020
【図２０】
2005039058.tif 000021
【図２１】
2005039058.tif 000022
【図２２】
2005039058.tif 000023
【図２３】
2005039058.tif 000024
【図２４】
2005039058.tif 000025
【図２５】
2005039058.tif 000026
【図２６】
2005039058.tif 000027
【図２７】
2005039058.tif 000028
【図２８】
2005039058.tif 000029
【手続補正書】
【提出日】平成18年3月22日(2006.3.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
線形対象物を符号化して得られる符号化データの生成方法であって、
（１）前記線形対象物をリサンプルして複数のノードを設定するステップと、
（２）一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成するステップと、
（３）前記偏角のデータ列に基づき、前記各ノードの位置データの予測値を算出するための複数の予測式を用意するステップと、
（４）当該複数の予測式のうち、所定の予測式を用いて前記予測値を算出するステップと、
（５）前記偏角のデータ列を、前記算出された予測値との差分を示す予測差分値のデータ列に変換するステップと、
（６）前記予測差分値のデータ列を可変長符号化して前記符号化データを得るステップと、を備える符号化データ生成方法。
【請求項２】
請求項１に記載の符号化データ生成方法であって、
前記（５）のステップにより、前記複数の予測式の各々について、前記複数の予測式の各々に対応した複数の前記予測差分値のデータ列を取得するステップと、
前記複数の予測差分値のデータ列を評価するステップと、
前記評価ステップの評価結果に基づき、前記（４）のステップにおける前記所定の予測式を、前記複数の予測式の中から選択するステップと、を更に備える符号化データ生成方法。
【請求項３】
請求項１又は２に記載の符号化データ生成方法であって、
前記複数の予測式は、０を予測値とする予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項４】
請求項１又は２に記載の符号化データ生成方法であって、
前記複数の予測式は、着目する偏角に先行する少なくとも一つの偏角をパラメータとして用いた関数によって構成された予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項５】
請求項４に記載の符号化データ生成方法であって、
前記関数によって構成された予測式は、前記着目する偏角の一つ前の偏角を予測値とする予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項６】
請求項４に記載の符号化データ生成方法であって、
前記関数によって構成された予測式は、前記着目する偏角に先行する複数の偏角の平均または加重平均を予測値とする予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項７】
請求項４に記載の符号化データ生成方法であって、
前記関数によって構成された予測式は、前記着目する偏角の一つ前のノードの偏角の正負を逆にした角度を予測値とする予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項８】
請求項２に記載の符号化データ生成方法であって、
前記（５）のステップにおいて、前記線形対象物の一部区間に対応する偏角のデータ列が前記予測差分値のデータ列に変換され、当該予測差分値のデータ列に対する評価結果に基づいて、前記一部区間に対応する偏角を予測差分値に変換する予測式を選択する、符号化データ生成方法。
【請求項９】
請求項８に記載の符号化データ生成方法であって、
前記偏角のデータ列を、偏角の状態遷移のパターンに対応したブロックに区分し、前記ブロック毎に、偏角を予測差分値に変換する予測式を選択する、符号化データ生成方法。
【請求項１０】
請求項８に記載の符号化データ生成方法であって、
前記偏角のデータ列を、所定数の偏角のデータを含むブロックに区分し、前記ブロック毎に、偏角を予測差分値に変換する予測式を選択する、符号化データ生成方法。
【請求項１１】
請求項８に記載の符号化データ生成方法であって、
前記偏角のデータ列を、前記（１）のステップにおけるリサンプルのリサンプル長の変更点に合わせてブロックに区分し、前記ブロック毎に、偏角を予測差分値に変換する予測式を選択する、符号化データ生成方法。
【請求項１２】
請求項８に記載の符号化データ生成方法であって、
着目する偏角に先行する所定数の偏角の予測差分値のデータ列に対する評価結果に応じて、前記着目する偏角を予測差分値に変換する予測式を選択する、符号化データ生成方法。
【請求項１３】
請求項１２に記載の符号化データ生成方法であって、
前記複数の選択式を用いて、前記所定数の偏角を複数の予測差分値のデータ列に変換し、所定の選択式に基づく予測差分値のデータ列に対する評価結果が所定の要件を満たす場合のみ、現在使用されている予測式を前記所定の予測式に変更したうえで、前記着目する偏角を予測差分値に変換する、符号化データ生成方法。
【請求項１４】
請求項８ないし１１に記載の符号化データ生成方法であって、
着目する偏角またはブロックにおいて、前後の偏角またはブロックでの予測式の選択状況を参考にして予測式を選択する、符号化データ生成方法。
【請求項１５】
請求項１４に記載の符号化データ生成方法であって、
着目する偏角またはブロックにおいて、前後の偏角またはブロックで採用する予測式とは異なる予測式を選出する場合、前記着目する偏角またはブロックでの予測差分値列の評価基準である評価値に対しペナルティ値を加算する、符号化データ生成方法。
【請求項１６】
請求項１５に記載の符号化データ生成方法であって、
各予測式の発生頻度に応じて前記ペナルティ値を設定する、符号化データ生成方法。
【請求項１７】
請求項２ないし１６のいずれか１項に記載の符号化データ生成方法であって、
前記予測差分値のデータ列の評価を、前記データ列に含まれる０の数によって行い、最も０の数が多くなる予測式を選択する、符号化データ生成方法。
【請求項１８】
請求項２ないし１６のいずれか１項に記載の符号化データ生成方法であって、
前記予測差分値のデータ列の評価を、前記データ列に含まれる予測差分値の統計値によって行い、前記統計値の結果に基づき予測式を選択する、符号化データ生成方法。
【請求項１９】
請求項１８に記載の符号化データ生成方法であって、
前記統計値は、前記予測差分値の分散及び標準偏差の少なくともいずれか一つである、符号化データ生成方法。
【請求項２０】
請求項２ないし１６のいずれか１項に記載の符号化データ生成方法であって、
前記予測差分値ごとの評価値をあらかじめ設定し、前記予測差分値のデータ列の評価を、前記データ列に含まれた予測差分値の評価値の合計値によって行う、符号化データ生成方法。
【請求項２１】
請求項２０に記載の符号化データ生成方法であって、
前記予測差分値の発生頻度が前記評価値であり、前記合計値が最も大きい予測式を選択する、符号化データ生成方法。
【請求項２２】
請求項２０に記載の符号化データ生成方法であって、
前記予測差分値の符号長が前記評価値であり、前記合計値が最も小さい予測式を選択する、符号化データ生成方法。
【請求項２３】
線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成する形状データリサンプル処理部と、
前記偏角のデータ列を、前記各ノードの位置データを予測するための予測値との差分を示す予測差分値に変換したときの前記予測差分値のデータ列を評価し、評価結果に基づいて、前記予測値を算出する予測式を複数の予測式の中から選択する予測式決定部と、
前記形状データリサンプル処理部が生成した前記偏角のデータ列に含まれる偏角を、前記予測式決定部が決定した予測式を用いて算出した予測値との予測差分値に変換して、前記予測差分値のデータ列を可変長符号化する可変長符号化処理部と、を備える符号化データ生成装置。
【請求項２４】
線形対象物の位置情報を表す可変長符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する符号化データ復号部と、
復号化された前記形状データから、前記予測値の算出に用いた予測式を決定する予測式判定部と、
前記予測式判定部が決定した予測式を用いて予測値を算出し、前記符号化データ復号部が復号化した前記予測差分値のデータ列から、前記線形対象物のノードの位置情報を再現する形状データ復元部と、を備える符号化データ復元装置。
【請求項２５】
線形対象物を符号化して得られる符号化データの生成をコンピュータに実行させるためのプログラムであって、当該プログラムは、
線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成する手順と、
前記偏角のデータ列を、前記各ノードの位置データの予測値との差分を示す予測差分値に変換したときの前記予測差分値のデータ列を評価する手順と、
評価結果に基づいて、前記予測値を算出する予測式を複数の予測式の中から選択する手順と、
前記偏角のデータ列に含まれる偏角を、前記決定された予測式を用いて算出した予測値との予測差分値に変換して、前記予測差分値のデータ列を可変長符号化する手順と、を前記コンピュータに実行させるプログラム。
【請求項２６】
線形対象物を表わす符号化データの復号化をコンピュータに実行させるためのプログラムであって、当該プログラムは、
線形対象物の位置情報を表す可変長符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する手順と、
復号化された前記形状データから、前記予測値の算出に用いた予測式を決定する手順と、
前記決定された予測式を用いて予測値を算出し、前記復号化された前記予測差分値のデータ列から、前記線形対象物のノードの位置情報を再現する手順と、を前記コンピュータに実行させるプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル地図の道路位置等を表す符号化データの生成方法と、その符号化データの生成及び復号化を行う装置に関し、符号化データのデータ量の削減を図るものである。
【背景技術】
【０００２】
従来から、ＶＩＣＳ（道路交通情報通信システム）では、デジタル地図データベースを搭載する車両用ナビゲーション装置に対して、ＦＭ多重放送やビーコンを通じて、渋滞区間や旅行時間を示す道路交通情報の提供サービスを実施している。車両用ナビゲーション装置は、この道路交通情報を受信して、画面表示する地図に渋滞区間を色付けして表したり、目的地までの所用時間を算出して表示したりしている。
【０００３】
このように、道路交通情報を提供する場合には、デジタル地図上の道路の位置情報を伝えることが必要になる。また、現在地及び目的地の情報を受信して、最短時間で目的地まで到達できる推奨経路の情報を提供するサービスや、近年、研究が進められている、走行中の車両（プローブカー）から軌跡情報及び速度情報等を収集する道路交通情報収集システム（プローブ情報収集システム）においても、デジタル地図上の推奨経路や走行軌跡を相手方に正しく伝えることが必要である。
【０００４】
これまで、デジタル地図上の道路位置を伝える場合には、一般的に、道路に付されたリンク番号や、交差点などのノードを特定するノード番号が使用されている。しかし、道路網に定義したノード番号やリンク番号は、道路の新設や変更に伴って新しい番号に付け替える必要があり、それに応じて、各社で制作されるデジタル地図データも更新しなければならないため、ノード番号やリンク番号を用いる方式は、メンテナンスに多大な社会的コストが掛かることになる。
【０００５】
こうした点を改善するため、特開２００３−２３３５７号公報では、ノード番号やリンク番号を用いずに、且つ、少ないデータ量でデジタル地図上の道路位置を伝える方法を提案している。
【０００６】
この方法では、伝えようとするデジタル地図上の道路区間に一定距離間隔でサンプリング点を再設定し（これを「等距離リサンプル」と言う）、各サンプリング点の位置データを順番に並べたデータ列に対して圧縮符号化の処理を施し、圧縮符号化したデータを送信する。これを受信した受信側は、サンプリング点の位置データのデータ列を復元し、自己のデジタル地図上に道路形状を再現する。また、必要に応じて、この位置データを使用して、自己のデジタル地図上で位置特定、位置参照を実施し（マップマッチング）、道路区間を特定する。
【０００７】
位置データのデータ列に対する圧縮符号化は、次に示すように、（１）位置データの単一変数への変換、（２）単一変数で表わした値の統計的に偏りを持つ値への変換、（３）変換した値の可変長符号化、の順に行われる。
【０００８】
（１）位置データの単一変数への変換
図２６（ａ）には、等距離リサンプルで設定した道路区間上のサンプリング点をＰJ-1、ＰJで表している。このサンプリング点（ＰJ）は、隣接するサンプリング点（ＰJ-1）からの距離（リサンプル長）Ｌと角度Θとの２つのディメンジョンで一意に特定することができ、距離を一定（Ｌ）とすると、サンプリング点（ＰJ）は、隣接サンプリング点（ＰJ-1）からの角度成分Θのみの単一変数で表現することができる。図２６（ａ）では、この角度Θとして、真北（図の上方）の方位を０度とし、時計回りに０〜３６０度の範囲で大きさを指定する「絶対方位」による角度Θを示している（真北からの絶対方位）。この角度Θは、ＰJ-1、ＰJのｘｙ座標（緯度・経度）を（ｘj-1，ｙj-1）、（ｘj，ｙj）とするとき、次式により算出することができる。
【０００９】
Θj-1 ＝ tan-1｛（ｘj − ｘj-1）／（ｙj − ｙj-1）｝
従って、道路区間は、サンプリング点間の一定距離Ｌ、及び、始端または終端となるサンプリング点（基準点）の緯度・経度を別に示すことにより、各サンプリング点の角度成分のデータ列により表わすことができる。
【００１０】
（２）単一変数値の統計的に偏りを持つ値への変換
各サンプリング点の単一変数値が、可変長符号化に適した、統計的に偏在する値となるように、図２６（ｂ）に示すように、各サンプリング点の角度成分を、隣接するサンプリング点の角度成分との変位差、即ち、「偏角」θjによって表現する。この偏角θjは、
θj ＝ Θj − Θj-1
として算出される。道路が直線的である場合に、各サンプリング点の偏角θは０付近に集中し、統計的に偏りを持つデータとなる。
【００１１】
また、サンプリング点の角度成分は、図２６（ｃ）に示すように、着目するサンプリング点ＰJの偏角θjを、それ以前のサンプリング点ＰJ-1、ＰJ-2、・・の偏角θj-1、θj-2、・・を用いて予測した当該サンプリング点ＰJの予測値Ｓjとの差分値（予測差分値又は予測誤差）Δθjで表わすことにより、統計的に偏りを持つデータに変換することができる。予測値Ｓjは、例えば、
Ｓj ＝ θj-1
と定義したり、
Ｓj ＝（θj-1 ＋ θj-2）／２
と定義したりすることができる。予測差分値Δθjは、
Δθj ＝ θj − Ｓj
として算出される。道路が一定の曲率で湾曲している場合には、各サンプリング点の予測差分値Δθは０付近に集中し、統計的に偏りを持つデータとなる。
【００１２】
図２６（ｄ）は、直線的な道路区間を偏角θで表示した場合、及び、曲線的な道路区間を予測差分値Δθで表示した場合のデータの発生頻度をグラフ化して示している。θ及びΔθの発生頻度はθ（又はΔθ）＝０°に極大が現れ、統計的に偏りを持っている。
【００１３】
（３）可変長符号化
次に、統計的に偏りを持つ値に変換したデータ列の値を可変長符号化する。可変長符号化方法には、固定数値圧縮法（０圧縮等）、シャノン・ファノ符号法、ハフマン符号法、算術符号法、辞書法など多種存在し、いずれの方法を用いてもよい。
【００１４】
ここでは、最も一般的なハフマン符号法を用いる場合について説明する。
この可変長符号化では、発生頻度が高いデータを少ないビット数で符号化し、発生頻度が低いデータを多いビット数で符号化して、トータルのデータ量を削減する。このデータと符号との関係は、符号表で定義する。
【００１５】
いま、１°単位で表わした道路区間のサンプリング点におけるΔθの並びが
"0_0_-2_0_0_+1_0_0_-1_0_+5_0_0_0_+1_0"
であるとする。このデータ列を符号化するために、可変長符号化とランレングス符号化（連長符号化）とを組み合わせた図２７に示す符号表を用いる場合について説明する。この符号表では、最小角度分解能（δ）を３°に設定しており、−１°〜＋１°の範囲にあるΔθの代表角度を０°として符号「０」で表し、０°が５個連続するときは符号「１００」で表わし、０°が１０個連続するときは符号「１１０１」で表わすことを規定している。また、±２°〜４°の範囲にあるΔθの代表角度は±３°として、符号「１１１０」に、＋のときは付加ビット「０」を、−のときは付加ビット「１」を加えて表し、±５°〜７°の範囲にあるΔθの代表角度は±６°として、符号「１１１１００」に正負を示す付加ビットを加えて表し、また、±８°〜１０°の範囲にあるΔθの代表角度は±９°として、符号「１１１１０１」に正負を示す付加ビットを加えて表わすことを規定している。
【００１６】
そのため、前記データ列は、次のように符号化される。
"0_0_11101_100_0_0_1111000_100"
→"0011101100001111000100"
このデータを受信した受信側は、符号化で使用されたものと同一の符号表を用いてΔθのデータ列を復元し、送信側と逆の処理を行って、サンプリング点の位置データを再現する。
【００１７】
このように、データを符号化することにより、符号化データのデータ量の削減が可能である。
また、前記特開２００３−２３３５７号公報では、図２８に示すように、道路形状の曲率が大きい区間Ｂでは、等距離リサンプルの距離Ｌ２を短く設定し、曲率が小さい、直線的な道路区間Ａでは、等距離リサンプルの距離Ｌ１を長く設定することを提案している。これは、曲率が大きく、カーブがきつい道路を長い距離でリサンプルすると、特徴的な道路形状を示す位置にサンプリング点を配置することができなくなり、受信側での道路形状の再現性が悪くなり、また、誤マッチングが発生する可能性が高くなるためである。
【００１８】
そのため、各区間ｊのリサンプル長Ｌjが取り得る値（量子化リサンプル長）を、例えば、４０／８０／１６０／３２０／６４０／１２８０／２５６０／５１２０メートルのように予め設定し、区間ｊの曲率半径ρjを用いて、次式によりＬjを求め、この値に最も近い量子化リサンプル長をリサンプル長Ｌjとして決定している。
【００１９】
Ｌj＝ρj・Ｋr （Ｋrは固定パラメータ）
【特許文献１】特開２００３−２３３５７号
【発明の開示】
【発明が解決しようとする課題】
【００２０】
前記特開２００３−２３３５７号公報の方法を、次の３つの予測式を用いて試行を行った。
【００２１】
予測式１：Ｓj ＝０：  偏角をそのまま利用(実質的には、予測を行わない)
予測式２：Ｓj ＝θj-1：  前ノードの偏角を利用
予測式３：Ｓj ＝（θj-1 ＋ θj-2）／２：  前及び前々ノードの偏角平均値を利用
結果は、平均的には予測式１の圧縮効率が高かったものの、対象道路を個別にみた場合、予測式２または予測式３の圧縮効率が高いものも存在した。
【００２２】
具体的には、高速道路など、長くなだらかなカーブを多く含む形状の道路では、予測式２または予測式３が適しているケースが多く、また、一般道では、予測式１が適しているケースが多かった。
【００２３】
また同種の予測式である、予測式２と予測式３を比較した場合は、若干、予測式３の方が圧縮効率で勝るケースが多かった。
【００２４】
本発明は、効率的にデータを圧縮して、デジタル地図の道路形状等の符号化データを生成する符号化データ生成方法を提供し、また、その符号化データの生成や符号化データの復号化を行う装置を提供することを目的としている。
【課題を解決するための手段】
【００２５】
上述の点を考察した結果、以下の結果が導かれた。
【００２６】
・高速道路などの「なだらかなカーブ」部分は、比較的小さな曲率が長距離にわたって、ほぼ一定となる。このため、ある微小区間に着目すると、該当箇所の曲率は、上流側の区間の曲率から非常に容易に予測できる。以上より、前または前々ノードの偏角をもちいて該当区間の偏角を予測する、予測式２または予測式３が適している。
【００２７】
・特に予測式３は、上流側の前および前々区間の平均曲率を用いた予測であり、区間毎の曲率誤差が平滑化される。よって、上記のような「長距離わたるなだらかなカーブ」においては、高精度な予測が可能となる。
【００２８】
・しかしながら、カーブ区間が比較的短い場合、予測式３は、予測式２と比較し、上流側のより長い区間の影響を受けることから、カーブの開始・終了箇所周辺（＝曲率が変更する箇所周辺）での予測が外れやすい。この影響を受け、カーブ区間が比較的短い場合には、予測式２の方が予測式３に勝るケースもある。
【００２９】
・一方、一般道路では、交差点部等で直角に曲がったり、カーブが存在しても比較的大きな曲率が短距離のみであるケースが多い。これはすなわち、ある微小区間の曲率を、上流側の前区間の曲率から予測しにくく、また予測をしたとしても外れやすい、ということである。このような場合には、実質的には予測を行わない、予測式１（偏角をそのまま用いる）が適している。
【００３０】
前記の試行結果から、道路全体を見渡すと、全般的には、予測式１（予測を行わず、偏角をそのまま用いる）の効率が良いものの、個別の道路または道路区間に着目した場合は、予測式２または予測式３（上流側の曲率から該当地点の曲率を予測する）が適した箇所も混在している、ということが分かった。
【００３１】
上記の点を踏まえ、本発明では、線形形状を備えた線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表した各ノードの位置情報を配列して偏角のデータ列を生成し、前記偏角を予測値との差分を示す予測差分値に変換して、予測差分値のデータ列を可変長符号化する符号化データの生成方法において、予測値を算出する予測式を複数の予測式の中から選択するようにしている。
【００３２】
このように、予測値を算出する予測式を動的に選択することによって、データ圧縮の効果を高めることができる。特に上記構成において、偏角を予測差分値に変換したときの予測差分値のデータ列を評価し、当該評価結果に基づいて予測式が選択される。
【００３３】
上述の符号化データ生成方法は以下の（１）〜（６）のステップを備え得る。
（１）線形対象物をリサンプルして複数のノードを設定するステップ。
（２）一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成するステップ。
（３）偏角のデータ列に基づき、各ノードの位置データの予測値を算出するための複数の予測式を用意するステップ。
（４）当該複数の予測式のうち、所定の予測式を用いて予測値を算出するステップ。
（５）偏角のデータ列を、算出された予測値との差分を示す予測差分値のデータ列に変換するステップ。
（６）予測差分値のデータ列を可変長符号化して前記符号化データを得るステップ。
【００３４】
更に上述（５）のステップにより、複数の予測式の各々について、複数の予測式の各々に対応した複数の前記予測差分値のデータ列を取得するステップと、複数の予測差分値のデータ列を評価するステップと、当該評価ステップの評価結果に基づき、上述（４）のステップにおける所定の予測式を、複数の予測式の中から選択するステップと、を更に設けることができる。
【００３５】
また、本発明の符号化データ生成方法では、複数の予測式の中に、０を予測値とする予測式を含めている。
通常は、この予測式を用いて効果的なデータ圧縮が得られる。
【００３６】
上述の複数の予測式には、着目する偏角に先行する少なくとも一つの偏角をパラメータとして用いた関数によって構成された予測式が少なくとも一つ含まれ得る。
また、本発明の符号化データ生成方法では、複数の予測式の中に、一つ前のノードの偏角を予測値とする予測式を含めている。
【００３７】
緩やかなカーブ周辺でこの予測式を用いると、効果的なデータ圧縮が得られる。
また、本発明の符号化データ生成方法では、複数の予測式の中に、先行する複数の偏角の平均又は加重平均を予測値とする予測式を含めている。
【００３８】
緩やかなカーブ周辺でこの予測式を用いると、効果的なデータ圧縮が得られる。
また、本発明の符号化データ生成方法では、複数の予測式の中に、一つ前のノードの偏角の正負を逆にした角度を予測値とする予測式を含めている。
【００３９】
リサンプル形状がジグザグにトレースした場合は、この予測式を用いることにより、効果的なデータ圧縮が得られる。
また、本発明の符号化データ生成方法では、偏角のデータ列に含まれる全ての偏角を予測差分値に変換して予測差分値のデータ列を評価し、評価結果に基づいて、全ての偏角を予測差分値に変換する予測式を選択するようにしている。
【００４０】
線形対象物の形状データ単位で予測式を動的に変えて、データ圧縮効果を高めることができる。
また、本発明の符号化データ生成方法では、線形対象物の一部区間に対応する偏角のデータ列に含まれる偏角を予測差分値に変換して予測差分値のデータ列を評価し、評価結果に基づいて、前記一部の区間に対応する偏角を予測差分値に変換する予測式を選択するようにしている。
【００４１】
線形対象物の形状データの途中で予測式を動的に変えて、データ圧縮効果をさらに高めることができる。
また、本発明の符号化データ生成方法では、偏角のデータ列を、偏角の状態遷移のパターンによって区分し、前記パターンの単位で、偏角を予測差分値に変換する予測式を選択するようにしている。
【００４２】
この方式を採る場合は、各パターンに適した予測式を選択することができる。
また、本発明の符号化データ生成方法では、偏角のデータ列を、所定数のデータを含むブロックに区分し、前記ブロックの単位で、偏角を予測差分値に変換する予測式を選択するようにしている。
【００４３】
この方式を採る場合は、符号化データ中に、選択した予測式が一定個数単位に出現するため、符号化データへのマーカーコードの挿入が不要になる。
また、本発明の符号化データ生成方法では、偏角のデータ列を、リサンプルのリサンプル長の変更点に合わせてブロックに区切り、このブロックの単位で、偏角を予測差分値に変換する予測式を選択するようにしている。
【００４４】
リサンプル長の変更点では形状データの特徴が変化するケースが多い。そのため、この方式を採る場合は、形状データの特徴に合った予測式の選択ができる。
また、本発明の符号化データ生成方法では、偏角のデータ列の着目する偏角に先行する所定数の偏角の予測差分値のデータ列に対する評価結果に応じて、着目する偏角を予測差分値に変換する予測式を選択するようにしている。
【００４５】
この方式は、エンコード側・デコード側の双方が、プログラムでルール化することにより実現できる。
ここで、複数の選択式を用いて、所定数の偏角を複数の予測差分値のデータ列に変換し、所定の選択式に基づく予測差分値のデータ列に対する評価結果が所定の要件を満たす場合のみ、現在使用されている予測式を所定の予測式に変更したうえで、着目する偏角を予測差分値に変換するようにしてもよい。
【００４６】
また、着目する偏角またはブロックにおいて、前後の偏角またはブロックでの予測式の選択状況を参考にして予測式を選択するようにしてもよい。
また、着目する偏角またはブロックにおいて、前後の偏角またはブロックで採用する予測式とは異なる予測式を選出する場合、着目する偏角またはブロックでの予測差分値列の評価基準である評価値に対しペナルティ値を加算するようにしてもよい。各予測式の発生頻度に応じてこのペナルティ値を設定することができる。
【００４７】
また、本発明の符号化データ生成方法では、予測差分値のデータ列の評価を、データ列に含まれる０の数によって行い、最も０の数が多くなる予測式を選択するようにしている。
【００４８】
そのため、データが０に集中し、可変長符号化によるデータ圧縮効果が向上する。
また、本発明の符号化データ生成方法では、予測差分値のデータ列の評価を、データ列に含まれる予測差分値の統計値（分散、標準偏差等）によって行い、分散または標準偏差が最も小さくなる予測式を選択するようにしている。
【００４９】
そのため、データが統計的に偏り、可変長符号化によるデータ圧縮効果が向上する。
また、本発明の符号化データ生成方法では、予測差分値ごとの評価値を、予測差分値の出現頻度に応じてあらかじめ設定し、予測差分値のデータ列の評価を、データ列に含まれた予測差分値の評価値の合計値によって行うようにしている。
【００５０】
予測差分値の発生頻度を評価値とするときは、合計値が最も大きい予測式を選択する。
また、予測差分値の符号長を評価値とするときは、合計値が最も小さい予測式を選択する。
【００５１】
また、本発明では、符号化データ生成装置に、線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表した各ノードの位置情報を配列して偏角のデータ列を生成する形状データリサンプル処理部と、このデータ列の偏角を、予測値との差分を示す予測差分値に変換したときの予測差分値のデータ列を評価し、評価結果に基づいて、予測値を算出する予測式を複数の予測式の中から選択する予測式決定部と、形状データリサンプル処理部が生成したデータ列に含まれる偏角を、予測式決定部が決定した予測式を用いて算出した予測値との予測差分値に変換して、その予測差分値のデータ列を可変長符号化する可変長符号化処理部とを設けている。
【００５２】
この装置では、前述する符号化データ生成方法を実施して符号化データのデータ量を効率的に圧縮することができる。
また、本発明では、符号化データ復元装置に、線形対象物の位置情報を表す、可変長符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する符号化データ復号部と、復号化された形状データの情報から、予測値の算出に用いた予測式を決定する予測式判定部と、予測式判定部が決定した予測式を用いて予測値を算出し、符号化データ復号部が復号化した予測差分値のデータ列から、線形対象物のノードの位置情報を再現する形状データ復元部とを設けている。
【００５３】
この装置では、線形対象物の位置情報の符号化データから、線形対象物の位置情報を再現することができる。
更に本発明は、線形対象物を符号化して得られる符号化データの生成をコンピュータに実行させるためのプログラムをも含み、当該プログラムは、線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成する手順と、偏角のデータ列を、各ノードの位置データの予測値との差分を示す予測差分値に変換したときの予測差分値のデータ列を評価する手順と、評価結果に基づいて、予測値を算出する予測式を複数の予測式の中から選択する手順と、形状データリサンプル処理部が生成した偏角のデータ列に含まれる偏角を、前記決定された予測式を用いて算出した予測値との予測差分値に変換して、予測差分値のデータ列を可変長符号化する手順と、を前記コンピュータに実行させる。
【００５４】
更に本発明は、線形対象物を表わす符号化データの復号化をコンピュータに実行させるためのプログラムをも含み、当該プログラムは、線形対象物の位置情報を表す可変長符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する手順と、復号化された形状データから、予測値の算出に用いた予測式を決定する手順と、決定された予測式を用いて予測値を算出し、復号化された予測差分値のデータ列から、線形対象物のノードの位置情報を再現する手順と、を前記コンピュータに実行させる。  本発明の符号化データ生成方法は、符号化データの生成に当たって、効果的にデータを圧縮することができる。
【００５５】
また、本発明の装置は、この符号化データ生成方法を実施して、線形対象物の形状データを、効果的にデータを圧縮して符号化することができ、また、この符号化データから元の形状データを復元することができる。
【発明の効果】
【００５６】
本発明の符号化データ生成方法は、デジタル地図の道路形状や河川、鉄道線路、行政境界線、等高線などの位置情報を表す符号化データを生成して、伝送・蓄積・保存するときなどに利用することができ、また、デジタル地図以外に、各種の図形や指紋などの線形対象物を表す符号化データを生成して、伝送・蓄積・保存するときなどにも適用することができる。
【発明を実施するための最良の形態】
【００５７】
本発明の実施形態における符号化データ生成方法では、線形対象物の一例であるデジタル地図の道路形状を符号化して符号化データを生成するため、大別して、
（ａ）道路の曲率半径に応じたリサンプル長での道路形状のリサンプル
（ｂ）サンプリング点（ノード）における位置データの偏角θへの変換
（ｃ）偏角θで表した位置データの統計的に偏りを持つ値への変換
（ｄ）変換した値の可変長符号化
の順序で符号化データを生成する。
【００５８】
（ａ）の道路形状のリサンプルは、特開２００３−２３３５７号公報に記載されている方法で行い、線形対象物をリサンプルして複数のノードを設定する。また、（ｂ）の偏角θへの変換は、特開２００３−２３３５７号公報に記載されている方法で、各ノードの位置データを角度成分で表した後、この角度成分を偏角θに変換する。図２（ａ）、（ｂ）、（ｃ）は、対象道路Ａ、Ｂ、Ｃの形状データの各ノードにおける位置データを偏角θで表した（偏角の）データ列（以下、「偏角列」と言う）を示している。各行は１０個のデータから成り、そのデータ番号を左端に表示している。偏角列の中の＜＞で囲んだ数字は、リサンプル長の量子化コードを示すリサンプル長変更コードであり、その右に続く数値は、そのコードのリサンプル長でリサンプルして得られた各ノードの位置データを偏角θ（ｄｅｇ）で表したものである。各ノードの位置データが一つ前のノードからの偏角で表わされ、集まって偏角のデータ列が生成される。
【００５９】
（ｃ）における位置データの統計的に偏りを持つ値への変換は、位置データの値を予測する予測値Ｓjの算出式（予測式）を適応的に用いてＳjを算出し、偏角列の偏角θを予測値Ｓjとの差分値（予側差分値）に変換する処理である。
【００６０】
（ｄ）の可変長符号化は、予測差分値列に変換した形状データの予測差分値（予測誤差）を可変長符号化する処理であり、特開２００３−２３３５７号公報に記載されている方法で行う。
【００６１】
従って、この符号化データ生成方法は、（ｃ）の位置データの変換処理に特徴を有している。
（ｃ）の位置データの変換処理では、予測値Ｓjを予測するため、次の４つの予測式（φ＝１、φ＝２、φ＝３、φ＝４）のいずれかを使用する。これらの式は前もって用意されており、所定のメモリなどに記録されている。
・φ＝１；予測式Ｓj ＝ ０
即ち、各ノードjの位置データを偏角θjで表し、予測値は０である。
・φ＝２；予測式Ｓj ＝ θj-1
即ち、各ノードjの位置データを（θj − θj-1）で表す。
・φ＝３；予測式Ｓj ＝（θj-1 ＋ θj-2）／２
即ち、各ノードjの位置データを｛θj −（θj-1 ＋ θj-2）／２｝で表す。
・φ＝４；予測式Ｓj ＝−θj-1
即ち、各ノードjの位置データを（θj ＋ θj-1）で表す。
【００６２】
φ＝２またはφ＝３は、図２の偏角列において、下線を引いたカーブ箇所の位置データを変換するときに用いると圧縮効率が高い。
φ＝２、φ＝３、φ＝４は、着目する偏角に先行する少なくとも一つの偏角をパラメータとして用いた関数によって構成されるものである。
【００６３】
また、φ＝２は、着目する偏角の一つ前の偏角を予測値としている。
また、φ＝３は、前記着目する偏角に先行する二つの偏角の平均を予測値としている。しかし、先行する偏角の個数は任意であり、（ａθj-1 ＋ｂ θj-2）／（ａ＋ｂ）の如き加重平均を予測値としてもよい（ａ、ｂは０より大きい実数）。
【００６４】
また、φ＝４は、着目する偏角の一つ前のノードの偏角の正負を逆にした角度を予測値としている。
また、図３に示すように、道路形状（点線）の折り曲がり箇所で、リサンプル形状（実線）がジグザグ状を呈する場合があり、φ＝４は、こうした箇所の位置データを変換するときに用いると圧縮効率が高い。このジグザグ現象は、リサンプル時の角度分解能δを設定して道路形状をトレースすると、利用できる角度に限りがあるため、必然的に発生する(角度の量子化に伴う必然性)。図２（ａ）の偏角列において、ジグザグ現象が発生している箇所の位置データを斜体文字で表示している。
【００６５】
また、φ＝１は、道路形状が直線に近い場合（カーブがあってもすぐ終わる場合や、ほぼ直線でたまに角度を修正するような場合を含む）に圧縮効率が高く、通常の道路形状の位置データを変換するときには、このφ＝１を使用する。
【００６６】
偏角θの変換処理に使用する予測値Ｓjの予測式は、道路形状に応じて動的に選択する。予測式の選択には、
（１）対象道路ごとに予測式を動的に選択する方式（「対象道路単位選択方式」と呼ぶ）
（２）対象道路の偏角列のパターンを検出し、そのパターン単位に予測式を選択する方式（「パターン単位選択方式」と呼ぶ）
（３）対象道路の偏角列を一定データ数のブロックに分け、ブロック単位に予測式を選択する方式（「ブロック単位選択方式」と呼ぶ）
（４）対象道路の偏角列中でリサンプル長変更コードが変わるごとに予測式を選択する方式（「リサンプル長連動方式」と呼ぶ）
（５）対象道路の偏角列中で着目する位置データの上流側Ｎ個の位置データにおける状況から、プログラム規則に従って予測式を選択する方式（「逐次選択方式」と呼ぶ）
等の方式が考えられる。どの方式を用いるかは、予め送信側と受信側で決めておく必要がある。
【００６７】
図１は、リサンプル長連動方式で選択される予測式と道路形状との関係を模式的に示している。道路形状を点線で示し、リサンプル形状を実線で示し、リサンプル長の変更箇所を＜Ｍ１＞、＜Ｍ２＞、＜Ｍ３＞で示している。道路形状が直線的である範囲Ａではφ＝１が選択され、ジグザグ現象が発生する範囲Ｂではφ＝４が選択され、カーブしている範囲Ｃではφ＝２またはφ＝３が選択され、また、そのいずれとも特定できない道路形状の範囲Ｄではφ＝１が選択される。
【００６８】
次に、各方式での処理について詳しく説明する。
（１）対象道路単位選択方式
図４のフロー図は、対象道路単位選択方式での処理手順を示している。デジタル地図データベースから対象道路の形状データを取得し（ステップ１）、リサンプルで生成したノードの位置データを偏角θで表し、偏角列を生成する（ステップ２）。
【００６９】
ステップ２の処理は、詳しくは図５に示す手順で行う。即ち、各リサンプル長の各偏角における角度分解能δを予め決定し（ステップ２１）、また、対象道路の形状データを曲率関数に変換して（ステップ２２）、曲率から各区間のリサンプル長Ｌを決定する（ステップ２３）。次いで、対象道路を、リサンプル長Ｌ、及び、偏角に応じた角度分解能δの代表角度によってリサンプルし（ステップ２４）、対象道路の形状データを、リサンプル区間長変更コードと偏角量子化値とを羅列した偏角列に変換する（ステップ２５）。
【００７０】
偏角列の生成が終了すると、対象道路の偏角列全体に対し、予測式φ＝１、φ＝２、φ＝３及びφ＝４を適用して、偏角列の偏角θを予測値Ｓjとの差分値（予測差分値）に変換し、どの予測式が最適であるかを評価する（ステップ３）。  ステップ３の処理は、詳しくは図６に示す手順で行う。即ち、評価対象の偏角列（対象道路単位選択方式の場合は対象道路の偏角列全体）を取得し（ステップ３１）、予測式をφ＝１から順に用いて（ステップ３２）、各々の予測式で予測値Ｓjを算出し、偏角列の偏角θを予測差分値（＝Δθj ＝ θj − Ｓj）で表した予測差分値列に変換し（ステップ３３）、この偏角列の評価値を算出する（ステップ３４）。
【００７１】
評価値の算出は、次の（ｉ）〜（ｉｉｉ）のように行う。
（ｉ）予測差分値列に含まれる０の数を評価値として、０が多い予測差分値列程、高い評価を与える（最も０を多く含む予測式を選択する）。
（ｉｉ）予測差分値列に含まれるデータの統計値（例えば分散、標準偏差等）の計算値を評価値として、分散または標準偏差が小さい予測差分値列程、高い評価を与える。
（ｉｉｉ）予測差分値列に現れるデータに、あらかじめ出現頻度に応じた得点を設定し、評価対象の予測差分値列に現れるデータの得点を加算した累積値を評価値として、この累積値に応じた評価を与える。図７のハフマンテーブルでは、各角度の発生頻度（または発生確率）が記述され、発生頻度が高い角度程、短い符号が割り当てられている。評価対象の予測差分値列に現れる角度に応じて、このテーブルの該当する発生頻度の値を加算する場合は、その累積値を評価値として、累積値が高い予測差分値列程、高い評価を与える。また、評価対象の予測差分値列に現れる角度に応じて、その角度の符号長を加算する場合は、その累積値を評価値として、累積値が小さい予測差分値列程、高い評価を与える。なお、こうした出現頻度に対応する得点表をあらかじめ持つことにより、ハフマン符号化以外の可変長符号化を行う場合にも、（ｉｉｉ）による評価が可能である。
【００７２】
全ての予測式を用いてステップ３３、ステップ３４の処理を行い、それが終了すると（ステップ３５、３６）、最も評価値の良い予測式を決定する（ステップ３７）。すなわち、予測式φ＝１、φ＝２、φ＝３及びφ＝４の各々について、対応する予測差分値のデータ列が生成され、これらのデータ列が評価される。
【００７３】
こうして最も評価値の良い予測式を選出して、偏角列の偏角θを、その予測式で算出した予測値との予測差分値に変換し（ステップ４）、予測差分値列に変換した形状データ全体を可変長符号化圧縮する（ステップ５）。得られた符号化データに、使用した予測式を定義付ける（ステップ６）。
【００７４】
図８は、対象道路単位選択方式により生成した符号化データのデータ構成を示している。ここでは、対象道路の形状データ本体の前に、使用した予測式を表すデータが挿入されている。
【００７５】
また、図９のフロー図は、この符号化データから対象道路の形状データを再現する手順を示している。符号化データから可変長復号化処理した形状データを取り出し（ステップ４１）、ヘッダを参照して予測式を決定し（ステップ４２）、その予測式に従って、形状データから読み取った角度データを偏角に変換し（ステップ４３）、対象道路の形状データを再現する（ステップ４４）。
【００７６】
（２）パターン単位選択方式
図１０のフロー図は、パターン単位選択方式での処理手順を示している。形状データの取得（ステップ５１）や、リサンプル及び偏角列変換処理（ステップ５２）の手順は、対象道路単位選択方式での処理手順（図４、図５）と同じである。
【００７７】
得られた偏角列をスキャンし、同一正負符号の非０のデータがＰ個以上連続する、φ＝２またはφ＝３を適用すべき曲線パターン（図２の下線部分）や、絶対値が同一値で正負符号が交互に反転するデータがＱ個以上連続する、φ＝４を適用すべきジグザグパターン（図２（ａ）の斜字部分）を抽出し、偏角列のデータを、各パターン別のグループ、何れのパターンにも属さない、φ＝１を適用すべきグループに分け（ステップ５３）、グループ単位に最も評価値が良い予測式を選出して、偏角列を予測差分値列に変換する（ステップ５４）。このとき、グループに対応する最良の予測式が一意に決まらない場合は、図６の手順により、そのグループの偏角列に複数の予測式を適用し、最も評価値の良い予測式を決定する。
【００７８】
次に、予測差分値列に変換した形状データ全体を可変長符号化圧縮し（ステップ５５）、得られた符号化データに、使用した予測式をグループ単位で定義付ける（ステップ５６）。
【００７９】
本実施形態では、偏角の状態遷移のパターンに対応したブロック（グループ）に、偏角のデータ列を区分している。そしてブロック毎に最適な予測式が選択される。
図１１は、パターン単位選択方式により生成した符号化データのデータ構成を示している。ここでは、対象道路の形状データ本体の前に、最初のグループで使用した予測式を表す予測式初期値が挿入され、以降の各グループの位置データに先行して、予測式の挿入を示す予測式マーカと、そのグループで使用した予測式の予測式番号とが挿入されている。
【００８０】
また、図１２のフロー図は、この符号化データから対象道路の形状データを再現する手順（符号化データの復号化方法）を示している。この符号化データから可変長復号化処理した形状データを取り出し（ステップ６１）、その形状データから読み取る角度データの番号を初期値に設定し、また、最初に使用する予測式を予測式初期値で表された予測式に設定し（ステップ６２）、形状データから該当する角度データを読み取り（ステップ６３）、その角度データの前に予測式変更コードが挿入されているか否かを識別する（ステップ６４）。予測式変更コードが挿入されていなければ、設定した予測式をそのまま使用して（ステップ６６）、その予測式に従って、角度データを偏角に変換する（ステップ６７）。また、予測式変更コードが挿入されていれば、予測式を、そのコードで指定された新たな予測式に変更し（ステップ６５）、その予測式に従って、角度データを偏角に変換する（ステップ６７）。こうした処理を角度データの全てについて行い（ステップ６８、ステップ６９）、対象道路の形状データを再現する（ステップ７０）。
【００８１】
本方式では、線形対象物（道路形状）全体ではなく、その一部区間に対応する偏角のデータ列が予測差分値のデータ列に変換され、予測差分値のデータ列に対する評価結果に基づいて、当該一部区間に対応する偏角を予測差分値に変換する最適な予測式が選択されるものである。この思想は、以下の（３）〜（５）の方式でも共通して採用されている。
【００８２】
（３）ブロック単位選択方式
図１３のフロー図は、ブロック単位選択方式での処理手順を示している。形状データの取得（ステップ７１）や、リサンプル及び偏角列変換処理（ステップ７２）の手順は、対象道路単位選択方式での処理手順（図４、図５）と同じである。
【００８３】
例えば、図２に示す偏角列の１行、１０データを１ブロックとして、このブロック単位の偏角列に対し、予測式φ＝１、φ＝２、φ＝３及びφ＝４を適用して、偏角列の偏角θを予測差分値に変換し、どの予測式が最適であるかを評価する（ステップ７３）。評価の仕方は、対象道路単位選択方式の場合（図６）と同じである。ブロック単位に最も評価値が良い予測式を選出して、偏角列を予測差分値列に変換し（ステップ７４）、予測差分値列に変換した形状データ全体を可変長符号化圧縮し（ステップ７５）、得られた符号化データに、使用した予測式をブロック単位で定義付ける（ステップ７６）。
【００８４】
図１４は、ブロック単位選択方式により生成した符号化データのデータ構成を示している。ここでは、対象道路の形状データ本体の前に、最初のブロックで使用した予測式を表す予測式初期値が挿入され、以降の各ブロックの位置データに先行して予測式番号が挿入されている。なお、予測式番号の挿入位置は、ブロックに含まれるデータ数により自動的に決まるので、予測式マーカの挿入は不要である。
【００８５】
また、図１５のフロー図は、この符号化データから対象道路の形状データを再現する手順を示している。この符号化データから可変長復号化処理した形状データを取り出し（ステップ８１）、その形状データから読み取るブロックの番号を初期値に設定し、また、最初に使用する予測式を予測式初期値で表された予測式に設定し（ステップ８２）、形状データから該当するブロックの角度データを読み取り（ステップ８３）、そのブロックに定義された予測式に従って、角度データを偏角に変換する（ステップ８４）。こうした処理をブロックの全てについて行い（ステップ８５、ステップ８６）、対象道路の形状データを再現する（ステップ８７）。
【００８６】
本実施形態では、１ブロックに含まれる偏角のデータの所定数は１０としたが、この数は任意に変更することができる。
【００８７】
（４）リサンプル長連動方式
図１６のフロー図は、リサンプル長連動方式での処理手順を示している。形状データの取得（ステップ９１）や、リサンプル及び偏角列変換処理（ステップ９２）の手順は、対象道路単位選択方式での処理手順（図４、図５）と同じである。
【００８８】
図２に示す偏角列において、同一リサンプル長でリサンプルされた、リサンプル長変更コードと次のリサンプル長変更コードとの間（二つのリサンプルのリサンプル長の変更点）に在る角度データをブロック（＜＞で囲まれた数字ごとのブロック）とし、このブロック単位の偏角列に対し、予測式φ＝１、φ＝２、φ＝３及びφ＝４を適用して、偏角列の偏角θを予測差分値に変換し、どの予測式が最適であるかを評価する（ステップ９３）。評価の仕方は、対象道路単位選択方式の場合（図６）と同じである。ブロック単位に最も評価値が良い予測式を選出して、偏角列を予測差分値列に変換し（ステップ９４）、予測差分値列に変換した形状データ全体を可変長符号化圧縮し（ステップ９５）、得られた符号化データに、使用した予測式をブロック単位で定義付ける（ステップ９６）。
【００８９】
図１７は、リサンプル長連動方式により生成した符号化データのデータ構成を示している。ここでは、対象道路の形状データ本体の前に、最初のブロックで使用した予測式を表す予測式初期値が挿入され、以降の各ブロックで使用した予測式の予測式番号は、同一リサンプル長でリサンプルされた角度データの開始位置に挿入される区間長マーカに続く区間長情報の中で規定されている。
【００９０】
また、図１８のフロー図は、この符号化データから対象道路の形状データを再現する手順を示している。この符号化データから可変長復号化処理した形状データを取り出し（ステップ１０１）、その形状データから読み取る同一リサンプル長のブロックの番号を初期値に設定し（ステップ１０２）、リサンプル長が同一のブロックに含まれる全ての角度データ、及び、リサンプル長変更コードに付随している予測式を取得し（ステップ１０３）、予測式に従って、ブロック内の角度データを偏角に変換する（ステップ１０４）。こうした処理をリサンプル長が同一のブロックの全てについて行い（ステップ１０５、ステップ１０６）、対象道路の形状データを再現する（ステップ１０７）。
【００９１】
（５）逐次選択方式
図１９のフロー図は、逐次選択方式での処理手順を示している。形状データの取得（ステップ１１１）や、リサンプル及び偏角列変換処理（ステップ１１２）の手順は、対象道路単位選択方式での処理手順（図４、図５）と同じである。
【００９２】
偏角列から抽出する角度データの番号を初期値に設定し、また、最初に使用する予測式をφ＝１に設定する（ステップ１１３）。偏角列から該当する角度データ及びその上流側の所定数たるＰ個のサンプルを抽出し（ステップ１１４）、抽出したデータから成る偏角列に対し、予測式φ＝１、φ＝２、φ＝３及びφ＝４を適用して、偏角列の偏角θを予測差分値に変換し、最も評価値が良い予測式φｎｅｗを選出する（ステップ１１５）。評価の仕方は、対象道路単位選択方式の場合（図６）と同じである。
【００９３】
この評価結果を踏まえ、予測式の変更条件に照らして、設定済みの予測式を変更する必要があるか否かを判定する（ステップ１１６）。すなわち、本方式においては、符号化の対象となっている位置データの上流の形状を参照しつつ、当該位置データに使用される最適な予測式を変更すべきか否かが判断される。
【００９４】
この変更条件として、例えば、次の（ｉ）または（ｉｉ）のような条件を設定する。
（ｉ）現在使用している予測式φと予測式φｎｅｗとの間で評価値差Δが所定値より大きい場合は予測式を変更する。
（ｉｉ）現在使用している予測式φよりも予測式φｎｅｗの方に高い評価が与えられる状態がＱ回以上続いた場合は予測式を変更する。
【００９５】
この変更条件を満たしていなければ、設定済みの予測式をそのまま使用して（ステップ１１８）、角度データを予測差分値に変換する（ステップ１１９）。また、変更条件を満たしている場合は、予測式を予測式φｎｅｗに変更して（ステップ１１７）、角度データを予測差分値に変換する（ステップ１１９）。こうした処理を全ての角度データに対して行い（ステップ１２０、ステップ１２１）、予測差分値列に変換した形状データ全体を可変長符号化圧縮する（ステップ１２２）。
【００９６】
この予測式変更の規則は、この符号化処理を規定するプログラムの中でルール化されている。
本実施形態では、着目する偏角に先行する所定数（Ｐ）の偏角の予測差分値のデータ列に対する評価結果に応じて、着目する偏角を予測差分値に変換する予測式が選択される。さらに、この評価結果が所定の要件を満たす場合のみ、現在使用されている予測式を所定の予測式に変更するように構成している。
【００９７】
図２０は、逐次選択方式により生成した符号化データのデータ構成を示している。この符号化データには、予測式を指定する情報が含まれていないため、データ量も少ないものとなっている。デコードの際に使用する予測式は、この符号化データのデコードを規定するプログラムのルールに基づいて選択される。
【００９８】
図２１のフロー図は、この符号化データから対象道路の形状データを再現する手順を示している。この符号化データから可変長復号化処理した形状データを取り出し（ステップ１３１）、その形状データから読み取る角度データの番号を初期値に設定し、また、最初に使用する予測式をφ＝１に設定する（ステップ１３２）。形状データから該当する角度データ及びその上流側Ｐ個のサンプルを読み取り（ステップ１３３）、読み取ったデータから成る偏角列に対し、予測式φ＝１、φ＝２、φ＝３及びφ＝４を適用して、偏角列の偏角θを予測差分値に変換し、最も評価値が良い予測式φｎｅｗを選出する（ステップ１３４）。次に、この評価結果を踏まえ、予測式の変更条件に照らして、設定済みの予測式を変更する必要があるか否かを判定する（ステップ１３５）。変更条件を満たしていなければ、設定済みの予測式をそのまま使用し（ステップ１３７）、その予測式に従って、角度データを偏角に変換する（ステップ１３８）。また、変更条件を満たしている場合は、予測式を予測式φｎｅｗに変更し（ステップ１３６）、その予測式に従って、角度データを偏角に変換する（ステップ１３８）。こうした処理を全ての角度データに行い（ステップ１３９、ステップ１４０）、対象道路の形状データを再現する（ステップ１４１）。
【００９９】
このように、道路形状の符号化データを生成する場合に、位置データを予測差分値に変換するための予測値の算出に使用する予測式を、道路ごとに、あるいは、道路の部分ごとに、適応的に選択することにより、符号化データのデータ量を効率的に圧縮することができる。
【０１００】
ところで、上述の（１）〜(４)各々の方式において、１つの形状データにおいて、予測式を変更する場合、「予測式の変更を明示し、予測式ＩＤを指定する」という情報をデータに盛り込むことが必要となる。これは、データ量増加の１要因となり得る。さらに、「その道路区間全般では、概して予測式１が良いが、瞬間的に他の予測式が良い」場合など、頻繁に予測式を変えるのもあまり望ましくはない。少なくとも予測式を変更する場合は、「新たな予測式によって得られるデータ量削減効果」が「予測式の変更に伴うロス」を上回る必要があることが望ましい。
【０１０１】
そこで、「各予測式によって得られた評価値」に対し、「変更ペナルティ」を加算し、その総合評価によって「予測式を変更するか否か」を決定することが考えられる。言い換えると、予測式変更に対してヒステリシスを持たせることが考えられる。
【０１０２】
図２２は予測式によって得られた評価値と、予測式の変更に伴う変更ペナルティの総合評価方法を示す図である。
図２２（ａ）では、予測式を変更した方がデータ量が削減され、データ送信の効率が向上するので、予測式を変更する。一方、図２２（ｂ）では、変更しない方が送信効率がよいため、予測式は変更しない。
【０１０３】
また、データを区分けするブロックや偏角が増加すると、「どういう組合せが最も効率がよいのか？」という組合せ最適化問題が発生する。ブロックや偏角が増加するにつれ、最適解を簡便に、早く見つけるのは難しくなる。
【０１０４】
そこで、準最適解をすばやく見つけるための方法として、以下の２つの方式が考えられる。
（ｉ）発生頻度が高い予測式には、変更ペナルティを相対的に小さくし、発生頻度が低い予測式には、変更ペナルティを大きくする。発生頻度が低い予測式を採用した場合、次ブロックで他の予測式に変わる可能性が大きいので、発生頻度が低い予測式への変更を抑制する。
【０１０５】
（ｉｉ）普通は、一方向に順に処理していくので、着目するブロックの上流側の実績から下流側の状況を推定し、変更ペナルティを動的に変えていく。
さらに、圧縮率によって、最適な予測式の発生頻度が変わるものと考えられる。例えば、圧縮率を上げると偏角の規則性が無くなり、φ＝１が最適な式になる傾向がある。また、逆に圧縮率を下げると偏角の規則性が強まり、φ＝２や、φ＝３が最適な式になる傾向がある。
【０１０６】
よって、（ｉ）の場合、「形状データ全体に対して各予測式の評価値を一旦算出し、その評価値に応じて変更ペナルティを決定する」ような方法が良いと考えられる。
図２３は予測式の変更に伴う変更ペナルティを動的に変動させる方法を示す図である。
【０１０７】
図２４は、交通情報の対象道路を伝えるために、この符号化データ生成方法を実行する情報送信装置（符号化データ生成装置）２０と、提供された交通情報を活用する、車載用ナビゲーション装置やパーソナルコンピュータなどの情報活用装置（符号化データ復元装置）４０との構成を示している。情報送信装置２０は、渋滞情報や交通事故情報などが入力される事象情報入力部２１と、デジタル地図データベースＡ２２から交通情報の対象道路区間の道路形状データを抽出する形状データ抽出部２３と、形状データ抽出部２３で抽出された道路形状データをリサンプルしてノード位置データの偏角列を生成する形状データリサンプル処理部２６と、偏角列を予測差分値列に変換するための予測式を決定する予測式決定部２５と、予測式決定部２５が決定した予測式を用いて形状データの偏角を予測差分値に変換し、圧縮符号化する可変長符号化処理部２８と、圧縮符号化された道路形状データを蓄積して外部メディアに蓄積データを提供する圧縮データ蓄積部２７と、圧縮符号化された道路形状データを送信する形状データ送信部２９とを備えている。
【０１０８】
一方、情報活用装置４０は、提供された道路形状データを受信する形状データ受信部４１と、圧縮符号化されているデータを復号する符号化データ復号部４２と、予測差分値への変換時に使用された予測式を識別する予測式判定部４７と、予測式判定部４７が識別した予測式を用いて形状データを復元する形状データ復元部４３と、デジタル地図データベースＢ４６のデータを用いてマップマッチングを行い、ノード点で表された道路区間をデジタル地図上で特定するマップマチング部４５と、得られた情報を活用する情報活用部４４とを備えている。
【０１０９】
情報送信装置２０では、形状データ抽出部２３が対象道路の道路形状データを抽出し、形状データリサンプル処理部２６が、この道路形状データをリサンプルして、道路形状データの偏角列を生成する。予測式決定部２５は、前述する「対象道路単位選択方式」「パターン単位選択方式」「ブロック単位選択方式」「リサンプル長連動方式」あるいは「逐次選択方式」により、偏角列を予測差分値列に変換するための予測式を決定する。可変長符号化処理部２８は、予測式決定部２５が決定した予測式で予測値を算出し、偏角列の偏角から予測値を減じて予測差分値列を生成し、これを可変長符号化する。
【０１１０】
可変長符号化でデータ圧縮された道路形状データは、外部メディアに記録されて提供され、あるいは、形状データ送信部２９から送信される。
この道路形状データを受信した情報活用装置４０では、符号化データ復号部４２が、圧縮符号化されているデータを復号化する。予測式判定部４７は、復号化されたデータから、偏角をデコードするための予測式を識別し、形状データ復元部４３は、この予測式を用いて偏角列を再生し、偏角を緯度・経度データに変換して道路形状データを再現する。再現されたノードを繋ぐリサンプル形状は、情報活用装置４０の表示画面上にデジタル地図と重ねて表示される。
【０１１１】
また、この道路区間を正確に特定するために、マップマッチング部４５は、再現されたノード点の位置データとデジタル地図データベースＢ４６の地図データとのマップマッチングを行い、デジタル地図データ上で対象道路を特定する。情報活用装置４０は、カーナビ受信機または地図表示端末をも構成し得る。
【０１１２】
また、図２５は、走行軌跡を伝えるために、この符号化データ生成方法を実行するプローブカー車載機（符号化データ生成装置）６０と、プローブ情報を収集するプローブ情報収集センタ（符号化データ復元装置）５０との構成を示している。プローブカー車載機６０は、ＧＰＳアンテナ７３から受信する情報やジャイロ７４の検知情報を基に自車位置を判定する自車位置判定部６１と、デジタル地図のデータベース６９と、自車の走行軌跡を蓄積する走行軌跡蓄積部６２と、走行軌跡をリサンプルしてノード位置データの偏角列を生成する走行軌跡形状リサンプル処理部６３と、偏角列を予測差分値列に変換するための予測式を決定する予測式決定部６８と、予測式決定部６８が決定した予測式を用いて走行軌跡形状データの偏角を予測差分値に変換し、圧縮符号化する可変長符号化処理部６４と、圧縮符号化された走行軌跡形状データを蓄積する圧縮データ蓄積部６５と、圧縮符号化された走行軌跡形状データを送信する走行軌跡送信部６６とを備えている。
【０１１３】
一方、プローブ情報収集センタ５０は、プローブカー車載機６０から提供された走行軌跡形状データを受信する走行軌跡受信部５１と、圧縮符号化されている受信データを復号化する符号化データ復号部５２と、予測差分値への変換時に使用された予測式を識別する予測式判定部５５と、予測式判定部５５が識別した予測式を用いて走行軌跡形状を復元する走行軌跡形状復元部５３と、プローブカー車載機６０から収集した走行軌跡や計測情報を交通情報の生成に活用する走行軌跡計測情報活用部５４とを備えている。
【０１１４】
プローブカー車載機６０の走行軌跡蓄積部６２には、自車位置判定部６１で検出された自車位置が走行軌跡として順次蓄積される。走行軌跡形状リサンプル処理部６３は、走行軌跡蓄積部６２に蓄積された走行軌跡データを読み出し、走行軌跡をリサンプルして、走行軌跡形状データの偏角列を生成する。予測式決定部６８は、前述する「対象道路単位選択方式」「パターン単位選択方式」「ブロック単位選択方式」「リサンプル長連動方式」あるいは「逐次選択方式」により、偏角列を予測差分値列に変換するための予測式を決定する。可変長符号化処理部６４は、予測式決定部６８が決定した予測式で予測値を算出し、偏角列の偏角から予測値を減じて予測差分値列を生成し、これを可変長符号化する。圧縮符号化されたデータは、プローブ情報の送信時期に、プローブ情報収集センタ５０に送信される。また、このデータは、外部メディアに格納してプローブ情報収集センタ５０に提供される場合もある。
【０１１５】
プローブ情報収集センタ５０では、符号化データ復号部５２が、プローブカー車載機６０から収集したデータを復号化する。予測式判定部５５は、復号化されたデータから、偏角をデコードするための予測式を識別し、走行軌跡形状復元部５３は、この予測式を用いて偏角列を再生し、偏角を緯度・経度データに変換して走行軌跡データを再現する。この走行軌跡の情報は、プローブカー車載機６０で計測された速度等の計測情報と併せて交通情報の生成に活用される。
【０１１６】
このように、情報送信装置やプローブカー車載機は、本発明の符号化データ生成方法を用いて、対象道路や走行軌跡の符号化データを生成することにより、データ量を効率的に圧縮することができる。
【０１１７】
プローブカー車載機６０とプローブ情報収集センタ５０の組み合わせより、プローブカーシステムが構築され、両者間でプローブカーシステムの情報伝達方法が達成されるが、当該方法は、本発明の符号化データの生成方法及び当該符号化データの復号化方法の組み合わせより達成される。
【０１１８】
なお、上述では、符号化データ生成装置が、情報送信センタである情報送信装置２０又プローブカー車載機６０である例を示したが、これらは情報送信側における実施形態の例であり、情報を送信する事が出来る装置や端末であればどのような形態のものでもよい。さらに生成した符号化データを媒体に記録して、他の装置に提供することも可能である。また、符号化データ復元装置である情報活用装置４０やプローブ情報収集センタ５０もあくまで例であり、パーソナルコンピュータ、携帯端末等の情報を活用できる装置であればなんでもよい。もちろん、符号化データの復元が可能な情報収集センターや、センター側の装置でも同様の効果を得ることが出来る。さらに符号化されたデータが記録された媒体等を用いて、復元処理することにより、同様の効果を得ることは言うまでもない。
【０１１９】
また、本発明は、線形対象物を符号化して得られる符号化データの生成をコンピュータに実行させるためのプログラムをも含み、当該プログラムは、線形対象物をリサンプルして複数のノードを設定し、一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成する手順と、偏角のデータ列を、各ノードの位置データを予測するための予測値との差分を示す予測差分値に変換したときの予測差分値のデータ列を評価する手順と、評価結果に基づいて、予測値を算出する予測式を複数の予測式の中から選択する手順と、形状データリサンプル処理部が生成した偏角のデータ列に含まれる偏角を、前記決定された予測式を用いて算出した予測値との予測差分値に変換して、予測差分値のデータ列を可変長符号化する手順と、を前記コンピュータに実行させる。このようなプログラムは、情報送信装置２０、プローブカー車載機６０に、種々の形式で組み込まれる。例えば情報送信装置２０、プローブカー車載機６０内又はこれらの外部の装置内の所定のメモリにプログラムを記録することができる。また、ハードディスクのような情報記録装置や、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ、メモリカードのような情報記録媒体にプログラムを記録してもよい。また、ネットワーク経由により当該プログラムをダウンロードするようにしてもよい。
【０１２０】
更に本発明は、線形対象物を表わす符号化データの復号化をコンピュータに実行させるためのプログラムをも含み、当該プログラムは、線形対象物の位置情報を表す可変長符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する手順と、復号化された形状データから、予測値の算出に用いた予測式を決定する手順と、決定された予測式を用いて予測値を算出し、復号化された予測差分値のデータ列から、線形対象物のノードの位置情報を再現する手順と、を前記コンピュータに実行させる。
【０１２１】
このようなプログラムも、情報活用装置４０、プローブ情報収集センタ５０に、種々の形式で組み込まれる。例えば情報活用装置４０、プローブ情報収集センタ５０内又はこれらの外部の装置内の所定のメモリにプログラムを記録することができる。また、ハードディスクのような情報記録装置や、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ、メモリカードのような情報記録媒体にプログラムを記録してもよい。また、ネットワーク経由により当該プログラムをダウンロードするようにしてもよい。
【０１２２】
また、本発明の情報送信装置２０と情報活用装置４０又はプローブカー車載機６０とプローブ情報収集センタ５０の組み合わせより、地図データ配信システムが構成される。
また、本発明の符号化データ生成方法に沿ったアルゴリズム（プログラム）を、地図データ本体に各種地図情報に対応した地図データが記録された記録媒体に記録することができる。これにより、地図データ本体自体を圧縮符号化することが可能となる。
【０１２３】
尚、上述の実施形態においては、線形対象物が位置参照用の道路形状である例を説明したが、線形対象物は道路形状に限られない。「線形対象物」とは直線、曲線など種々の形態を含む細長い形状のものを総て含み、地図上の線形形状によって表わせる地理情報総てを含み得る。更に、指紋等地図とは関係ないが、線形形状によって表わされるもの総てをも含まれる。
【０１２４】
また、本発明を詳細にまた特定の実施態様を参照して説明したが、本発明の精神と範囲を逸脱することなく様々な変更や修正を加えることができることは当業者にとって明らかである。
【０１２５】
本出願は、２００３年１０月１７日出願の日本特許出願（特願２００３−３５７７３０）に基づくものであり、その内容はここに参照として取り込まれる。
【産業上の利用可能性】
【０１２６】
本発明の符号化データ生成方法は、デジタル地図の道路形状や河川、鉄道線路、行政境界線、等高線などの位置情報を表す符号化データを生成して、伝送・蓄積・保存するときなどに利用することができ、また、デジタル地図以外に、各種の図形や指紋などの線形対象物を表す符号化データを生成して、伝送・蓄積・保存するときなどにも適用することができる。
【図面の簡単な説明】
【０１２７】
【図１】本発明の実施形態における符号化データ生成方法を模式的に説明する図である。
【図２】道路形状データの偏角列を示す図である。
【図３】ジグザグ現象を説明する図である。
【図４】本発明の実施形態における対象道路単位選択方式での符号化データ生成方法の手順を示すフロー図である。
【図５】本発明の実施形態における符号化データ生成方法でのリサンプル及び偏角列生成手順を示すフロー図である。
【図６】本発明の実施形態における符号化データ生成方法での評価値算出手順を示すフロー図である。
【図７】発生頻度を記載したハフマンテーブルの例である。
【図８】本発明の実施形態における対象道路単位選択方式で生成した符号化データのデータ構成例である。
【図９】本発明の実施形態における対象道路単位選択方式で生成した符号化データの復号手順を示すフロー図である。
【図１０】本発明の実施形態におけるパターン単位選択方式での符号化データ生成方法の手順を示すフロー図である。
【図１１】本発明の実施形態におけるパターン単位選択方式で生成した符号化データのデータ構成例である。
【図１２】本発明の実施形態におけるパターン単位選択方式で生成した符号化データの復号手順を示すフロー図である。
【図１３】本発明の実施形態におけるブロック単位選択方式での符号化データ生成方法の手順を示すフロー図である。
【図１４】本発明の実施形態におけるブロック単位選択方式で生成した符号化データのデータ構成例である。
【図１５】本発明の実施形態におけるブロック単位選択方式で生成した符号化データの復号手順を示すフロー図である。
【図１６】は本発明の実施形態におけるリサンプル長連動方式での符号化データ生成方法の手順を示すフロー図である。
【図１７】本発明の実施形態におけるリサンプル長連動方式で生成した符号化データのデータ構成例である。
【図１８】本発明の実施形態におけるリサンプル長連動方式で生成した符号化データの復号手順を示すフロー図である。
【図１９】本発明の実施形態における逐次選択方式での符号化データ生成方法の手順を示すフロー図である。
【図２０】本発明の実施形態における逐次選択方式で生成した符号化データのデータ構成例である。
【図２１】本発明の実施形態における逐次選択方式で生成した符号化データの復号手順を示すフロー図である。
【図２２】予測式によって得られた評価値と、予測式の変更に伴う変更ペナルティの総合評価方法を示す図である。
【図２３】予測式の変更に伴う変更ペナルティを動的に変動させる方法を示す図である。
【図２４】本発明の実施形態における情報送信装置及び情報活用装置の構成を示すブロック図である。
【図２５】本発明の実施形態におけるプローブカー車載機及びプローブ情報収集センタの構成を示すブロック図である。
【図２６】位置データを統計的に偏りを持つデータに変換する方法を説明する図である。
【図２７】可変長符号化に用いる符号表を示す図である。
【図２８】道路形状の曲率によるリサンプル長の変更を説明する図である。
【符号の説明】
【０１２８】
２０  情報送信装置（符号化データ生成装置）
２１  事象情報入力部
２２  デジタル地図データベースＡ
２３  形状データ抽出部
２５  予測式決定部
２６  形状データリサンプル処理部
２７  圧縮データ蓄積部
２８  可変長符号化処理部
２９  形状データ送信部
４０  情報活用装置（符号化データ復元装置）
４１  形状データ受信部４１
４２  符号化データ復号部
４３  形状データ復元部
４４  情報活用部
４５  マップマッチング部
４６  デジタル地図データベースＢ
４７  予測式判定部
５０  プローブ情報収集センタ（符号化データ復元装置）
５１  走行軌跡受信部
５２  符号化データ復号部
５３  走行軌跡形状復元部
５４  走行軌跡計測情報活用部
５５  予測式判定部
６０  プローブカー車載機（符号化データ生成装置）
６１  自車位置判定部
６２  走行軌跡蓄積部
６３  走行軌跡形状リサンプル処理部
６４  可変長符号化処理部
６５  圧縮データ蓄積部
６６  走行軌跡送信部
６８  予測式決定部
６９  デジタル地図データベース
７３  ＧＰＳアンテナ
７４  ジャイロ
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2005039058.tif 000030
【図２】
2005039058.tif 000031
【図３】
2005039058.tif 000032
【図４】
2005039058.tif 000033
【図５】
2005039058.tif 000034
【図６】
2005039058.tif 000035
【図７】
2005039058.tif 000036
【図８】
2005039058.tif 000037
【図９】
2005039058.tif 000038
【図１０】
2005039058.tif 000039
【図１１】
2005039058.tif 000040
【図１２】
2005039058.tif 000041
【図１３】
2005039058.tif 000042
【図１４】
2005039058.tif 000043
【図１５】
2005039058.tif 000044
【図１６】
2005039058.tif 000045
【図１７】
2005039058.tif 000046
【図１８】
2005039058.tif 000047
【図１９】
2005039058.tif 000048
【図２０】
2005039058.tif 000049
【図２１】
2005039058.tif 000050
【図２２】
2005039058.tif 000051
【図２３】
2005039058.tif 000052
【図２４】
2005039058.tif 000053
【図２５】
2005039058.tif 000054
【図２６】
2005039058.tif 000055
【図２７】
2005039058.tif 000056
【図２８】
2005039058.tif 000057
【手続補正書】
【提出日】平成19年10月15日(2007.10.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
線形対象物を符号化して得られる符号化データの生成方法であって、
（１）前記線形対象物を一定の距離でサンプリングしたノード列に設定するステップと、
（２）一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成するステップと、
（３）前記偏角のデータ列に基づき、前記各ノードの位置データの予測値を算出するための複数の予測式から選択された予測式を用いて前記予測値を算出するステップと、
（４）前記偏角のデータ列を、前記算出された予測値との差分を示す予測差分値のデータ列に変換するステップと、
（５）前記予測差分値のデータ列を符号化して前記符号化データを得るステップと、を備える符号化データ生成方法。
【請求項２】
請求項１に記載の符号化データ生成方法であって、
前記（４）のステップにより、前記複数の予測式の各々について、前記複数の予測式の各々に対応した複数の前記予測差分値のデータ列を取得するステップと、
前記複数の予測差分値のデータ列を評価するステップと、
前記評価ステップの評価結果に基づき、前記（３）のステップにおける前記所定の予測式を、前記複数の予測式の中から選択するステップと、を更に備える符号化データ生成方法。
【請求項３】
請求項１又は２に記載の符号化データ生成方法であって、
前記複数の予測式は、０を予測値とする予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項４】
請求項１又は２に記載の符号化データ生成方法であって、
前記複数の予測式は、着目する偏角に先行する少なくとも一つの偏角をパラメータとして用いた関数によって構成された予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項５】
請求項４に記載の符号化データ生成方法であって、
前記関数によって構成された予測式は、前記着目する偏角の一つ前の偏角を予測値とする予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項６】
請求項４に記載の符号化データ生成方法であって、
前記関数によって構成された予測式は、前記着目する偏角に先行する複数の偏角の平均または加重平均を予測値とする予測式を少なくとも一つ含む、符号化データ生成方法。
【請求項７】
請求項２に記載の符号化データ生成方法であって、
前記（４）のステップにおいて、前記線形対象物の一部区間に対応する偏角のデータ列が前記予測差分値のデータ列に変換され、当該予測差分値のデータ列に対する評価結果に基づいて、前記一部区間に対応する偏角を予測差分値に変換する予測式を選択する、符号化データ生成方法。
【請求項８】
線形対象物を一定の距離でサンプリングしたノード列に設定し、一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成する形状データサンプリング処理部と、
前記偏角のデータ列に基づき、前記各ノードの位置データの予測値を算出するための複数の予測式から選択された予測式を用いて前記予測値を算出する予測式決定部と、
前記形状データサンプリング処理部が生成した前記偏角のデータ列に含まれる偏角を、前記予測式決定部が決定した予測式を用いて算出した予測値との予測差分値に変換して、前記予測差分値のデータ列を符号化する符号化処理部と、
を備える符号化データ生成装置。
【請求項９】
線形対象物の位置情報を表す符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する符号化データ復号部と、
復号化された前記形状データから、前記予測値の算出に用いた予測式を決定する予測式判定部と、
前記予測式判定部が決定した予測式を用いて予測値を算出し、前記符号化データ復号部が復号化した前記予測差分値のデータ列から、前記線形対象物のノードの位置情報を再現する形状データ復元部と、
を備える符号化データ復元装置。
【請求項１０】
線形対象物を符号化して得られる符号化データの生成をコンピュータに実行させるためのプログラムであって、当該プログラムは、
前記線形対象物を一定の距離でサンプリングしたノード列に設定する手順と、
一つ前のノードからの偏角で表された各ノードの位置データを配列して偏角のデータ列を生成する手順と、
前記偏角のデータ列に基づき、前記各ノードの位置データの予測値を算出するための複数の予測式から選択された予測式を用いて前記予測値を算出する手順と、
前記偏角のデータ列を、前記算出された予測値との差分を示す予測差分値のデータ列に変換する手順と、
前記予測差分値のデータ列を符号化して前記符号化データを得る手順と、
を前記コンピュータに実行させるプログラム。
【請求項１１】
線形対象物を表わす符号化データの復号化をコンピュータに実行させるためのプログラムであって、当該プログラムは、
線形対象物の位置情報を表す符号化された符号化データを復号化して、偏角と予測値との差分を示す予測差分値のデータ列が含まれた形状データを再生する手順と、
復号化された前記形状データから、前記予測値の算出に用いた予測式を決定する手順と、
前記決定された予測式を用いて予測値を算出し、前記復号化された前記予測差分値のデータ列から、前記線形対象物のノードの位置情報を再現する手順と、
を前記コンピュータに実行させるプログラム。
【請求項１２】
緯度経度座標列で表された線形対象物を符号化する方法であって、
前記緯度経度座標列で表された線形対象物を等距離Ｌにサンプリングして、角度（Θ）のデータで表すステップと、
前記角度（Θ）のデータ列を隣り合うサンプリング点との方位差で表した偏角（Φ）のデータ列に変換し、前記偏角（Φ）のデータ列を予測角差分値(ΔΦ)のデータ列に変換するステップと、
前記予測角差分値(ΔΦ)のデータ列をＶＬＣ符号化するステップと、を備え、
偏角（Φ）の値は、上流側の偏角（Φ）を用いた予測式によって予測された予測値であり、前記予測角差分値(ΔΦ)は前記予測式によって予測された予測値（Ｓj）と実際の偏角との差分値である、方法。
【請求項１３】
緯度経度座標列で表された線形対象物を符号化する装置であって、
前記緯度経度座標列で表された線形対象物を等距離Ｌにサンプリングして、角度（Θ）のデータで表す手段と、
前記角度（Θ）のデータ列を隣り合うサンプリング点との方位差で表した偏角（Φ）のデータ列に変換し、前記偏角（Φ）のデータ列を予測角差分値(ΔΦ)のデータ列に変換する手段と、
前記予測角差分値(ΔΦ)のデータ列をＶＬＣ符号化する手段と、を備え、
偏角（Φ）の値は、上流側の偏角（Φ）を用いた予測式によって予測された予測値であり、前記予測角差分値(ΔΦ)は前記予測式によって予測された予測値（Ｓj）と実際の偏角との差分値である、生成装置。
【請求項１４】
請求項１２記載の方法で符号化されたデータを緯度経度座標列で表されたデータに復元する符号化データ復元方法。
【請求項１５】
請求項１３記載の生成装置で符号化されたデータを緯度経度座標列で表されたデータに復元する符号化データ復元装置。
【国際調査報告】
2005039058.tif 000058
2005039058.tif 000059
2005039058.tif 000060
2005039058.tif 000061