(57)【要約】線形対象物をリサンプルするサンプリング点間のリサンプル長Ｌを、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差Ｅｒが、予め決めた許容誤差を超えないように設定する。許容誤差を予め定義し、それを超えないようにリサンプル長Ｌを決定しているので、リサンプル形状は、線形対象物に良く追従する。
2005038752.tif 000002
【特許請求の範囲】
【請求項１】
線形対象物をリサンプルするサンプリング点間のリサンプル長を、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、予め決めた許容誤差を超えないように設定する、リサンプル長決定方法。
【請求項２】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記形状が前記円弧の一部に近似すると判断された場合に、前記線形対象物の曲率半径を算出するステップと、
前記線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定するステップと、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さい場合に、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップと、を備えるリサンプル長決定方法。
【請求項３】
請求項１又は２記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が所定値以上又は所定値より大きいと判断され、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定するステップにおいて、前記線形対象物の曲率半径をρ、前記許容誤差をＥｍａｘとして、
√（ρ２−（ρ−Ｅｍａｘ）２）
を含む判定式の値に基づいて前記リサンプル長を決定する、リサンプル長決定方法。
【請求項４】
請求項２記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さいと判断され、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップにおいて、前記線形対象物の曲率半径ρ、さらに固定パラメータＫｒを用いた、Ｋｒ・ρを含む判定式に基づいて前記サンプリング長を決定する、リサンプル長決定方法。
【請求項５】
請求項２記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さいと判断され、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップにおいて、前記曲率半径が小さい程、前記許容誤差も小さくなるように、前記許容誤差を前記曲率半径に応じて変更する、リサンプル長決定方法。
【請求項６】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記線状対象形状物の形状が、前記円弧の一部に近似しない折曲部分を含むと判断された場合に、、前記折曲部分との誤差が許容誤差を超えない円の一部で前記折曲部分を近似するステップと、
前記判定式の値を算出し、当該算出した値に基づいて前記リサンプル長を決定するステップとを更に備える、リサンプル長決定方法。
【請求項７】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記線状対象形状物の形状が、前記円弧の一部に近似しない折曲部分を含むと判断された場合に、前記折曲部分の前後は、偏角の大きさに応じて予め決めたリサンプル長を選出する、リサンプル長決定方法。
【請求項８】
請求項２ないし７のいずれか１項記載のリサンプル長決定方法であって、
前記線形対象物の形状が円弧の一部に近似するか否か判定するステップが、偏角の大きさ、又は偏角及びノード間の距離の関係を用いて行われる、リサンプル長決定方法。
【請求項９】
請求項１ないし８のいずれか１項に記載された方法により線形対象物のリサンプル長を決定するステップと、
前記線形対象物を、決定したリサンプル長でリサンプルして複数のサンプリング点を設定するステップと、
各サンプリング点の位置データを、発生頻度に偏りを持つ角度成分で表現するステップと、
前記角度成分で表わされた位置データを順番に並べたデータ列に対して可変長符号化を行うステップと、を備える線形対象物の符号化データ生成方法。
【請求項１０】
請求項１ないし８のいずれか１項記載のリサンプル長決定方法を用いて、線形対象物をリサンプルするサンプリング点間のリサンプル長を決定するリサンプル長決定部を備える装置。
【請求項１１】
線形対象物をリサンプルするサンプリング点間のリサンプル長を請求項１ないし請求項８のいずれか１項記載のリサンプル長決定方法で決定するリサンプル長決定部と、
前記リサンプル長決定部が決定したリサンプル長で前記線形対象物をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、
前記リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部と、を備える符号化データ生成装置。
【請求項１２】
プローブカーの走行軌跡を伝えるプローブカー車載機であって、
線形対象物をリサンプルするサンプリング点間のリサンプル長を請求項１ないし請求項８のいずれか１項記載のリサンプル長決定方法で決定するリサンプル長決定部と、
前記リサンプル長決定部が決定したリサンプル長で前記線形対象物をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、
前記リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部と、を備えるプローブカー車載機。
【請求項１３】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムであって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定する手順と、
前記判定手順の結果、前記形状が前記円弧の一部に近似すると判断された場合に、前記線形対象物の曲率半径を算出する手順と、
前記線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定する手順と、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さい場合に、前記線形対象物を曲率半径に対応した多角形で近似する手順と、をコンピュータに実行させるプログラム。
【請求項１４】
請求項９記載の線形対象物の符号化データ生成方法を用いて得られた符号化データを受信する受信部と、
当該受信された符号化データを復元する復元部と、を備える符号化データ復元装置。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、道路位置等を表す符号化データを生成するため、デジタル地図の道路等の形状に沿って複数のサンプリング点を設定する場合のサンプリング点間隔（リサンプル長）の決定方法と、それを用いた符号化データ生成方法と、それらの方法を実施する装置に関し、元形状との誤差が少なく、且つ、符号化データのデータ量を増やさないようなリサンプル長の決め方を提案するものである。
【背景技術】
【０００２】  従来から、ＶＩＣＳ（道路交通情報通信システム）では、デジタル地図データベースを搭載する車両用ナビゲーション装置に対して、ＦＭ多重放送やビーコンを通じて、渋滞区間や旅行時間を示す道路交通情報の提供サービスを実施している。車両用ナビゲーション装置は、この道路交通情報を受信して、画面表示する地図に渋滞区間を色付けして表したり、目的地までの所用時間を算出して表示したりしている。【０００３】  このように、道路交通情報を提供する場合には、デジタル地図上の道路の位置情報を伝えることが必要になる。また、現在地及び目的地の情報を受信して、最短時間で目的地まで到達できる推奨経路の情報を提供するサービスや、近年、研究が進められている、走行中の車両（プローブカー）から軌跡情報及び速度情報等を収集する道路交通情報収集システム（プローブ情報収集システム）においても、デジタル地図上の推奨経路や走行軌跡を相手方に正しく伝えることが必要である。【０００４】  これまで、デジタル地図上の道路位置を伝える場合には、一般的に、道路に付されたリンク番号や、交差点などのノードを特定するノード番号が使用されている。しかし、道路網に定義したノード番号やリンク番号は、道路の新設や変更に伴って新しい番号に付け替える必要があり、それに応じて、各社で制作されるデジタル地図データも更新しなければならないため、ノード番号やリンク番号を用いる方式は、メンテナンスに多大な社会的コストが掛かることになる。【０００５】  こうした点を改善するため、特開２００３−２３３５７号公報では、ノード番号やリンク番号を用いずに、且つ、少ないデータ量でデジタル地図上の道路位置を伝える方法を提案している。【０００６】  この方法では、伝えようとするデジタル地図上の道路区間に一定距離間隔でサンプリング点を再設定し（これを「等距離リサンプル」と言う）、各サンプリング点の位置データを順番に並べたデータ列に対して圧縮符号化の処理を施し、圧縮符号化したデータを送信する。これを受信した受信側は、サンプリング点の位置データのデータ列を復元し、自己のデジタル地図上に道路形状を再現する。また、必要に応じて、この位置データを使用して、自己のデジタル地図上で位置特定、位置参照を実施し（マップマッチング）道路区間を特定する。【０００７】  位置データのデータ列に対する圧縮符号化は、次に示すように、（１）位置データの単一変数への変換、（２）単一変数で表わした値の統計的に偏りを持つ値への変換、（３）変換した値の可変長符号化、の順に行われる。
（１）位置データの単一変数への変換
図１５（ａ）には、等距離リサンプルで設定した道路区間上のサンプリング点をＰＪ−１、ＰＪで表している。このサンプリング点（ＰＪ）は、隣接するサンプリング点（ＰＪ−１）からの距離（リサンプル長）Ｌと角度Θとの２つのディメンジョンで一意に特定することができ、距離を一定（Ｌ）とすると、サンプリング点（ＰＪ）は、隣接サンプリング点（ＰＪ−１）からの角度成分Θのみの単一変数で表現することができる。図１５（ａ）では、この角度Θとして、真北（図の上方）の方位を０度とし、時計回りに０〜３６０度の範囲で大きさを指定する「絶対方位」による角度Θを示している（真北からの絶対方位）。道路区間は、サンプリング点間の一定距離し、及び、始端または終端となるサンプリング点（基準点）の緯度・経度を別に示すことにより、各サンプリング点の角度成分のデータ列により表わすことができる。
（２）単一変数値の統計的に偏りを持つ値への変換
各サンプリング点の単一変数値が、可変長符号化に適した、統計的に偏在する値となるように、図１５（ｂ）に示すように、各サンプリング点の角度成分を、隣接するサンプリング点の角度成分との変位差、即ち、「偏角」θｊによって表現する。この偏角θｊは、
θｊ＝Θｊ−Θｊ−１
として算出される。道路が直線的である場合に、各サンプリング点の偏角θは０付近に集中し、統計的に偏りを持つデータとなる。【０００８】  また、サンプリング点の角度成分は、図１５（ｃ）に示すように、着目するサンプリング点ＰＪの偏角θｊを、それ以前のサンプリング点ＰＪ−１、ＰＪ−２、・・の偏角θｊ−１、θｊ−２、・・を用いて予測した当該サンプリング点ＰＪの偏角予測値Ｓｊ（統計予測値）との差分値（偏角予測差分値又は偏角予測誤差）Δθｊで表わすことにより、統計的に偏りを持つデータに変換する
ことができる。統計予測値Ｓｊは、例えば、
Ｓｊ＝θｊ−１
と定義したり、
Ｓｊ＝（θｊ−１＋θｊ−２）／２
と定義したりすることができる。偏角予測差分値Δθｊは、
Δθｊ＝θｊ−Ｓｊ
として算出される。道路が一定の曲率で湾曲している場合には、各サンプリング点の偏角予測差分値Δθは０付近に集中し、統計的に偏りを持つデータとなる。【０００９】  図１５（ｄ）は、直線的な道路区間を偏角θで表示した場合、及び、曲線的な道路区間を偏角予測差分値Δθで表示した場合のデータの発生頻度をグラフ化して示している。θ及びΔθの発生頻度はθ（又はΔθ）＝０°に極大が現れ、統計的に偏りを持っている。
（３）可変長符号化
次に、統計的に偏りを持つ値に変換したデータ列の値を可変長符号化する。可変長符号化方法には、固定数値圧縮法（０圧縮等）、シャノン・ファノ符号法、ハフマン符号法、算術符号法、辞書法など多種存在し、いずれの方法を用いてもよい。最も一般的なハフマン符号法を用いる場合では、発生頻度が高いデータに少ないビット数の符号を定義し、発生頻度が低いデータに多いビット数の符号を定義した符号表を用いて、統計的に偏りを持たせたデータ列の値を符号化し、トータルのデータ量を削減する。【００１０】  また、特開２００３−２３３５７号公報では、図１６に示すように、道路形状の曲率が大きい区間Ｂでは、等距離リサンプルの距離Ｌ２を短く設定し、曲率が小さい、直線的な道路区間Ａでは、等距離リサンプルの距離Ｌ１を長く設定することを提案している。これは、曲率が大きく、カーブがきつい道路を長い距離でリサンプルすると、特徴的な道路形状を示す位置にサンプリング点を配置することができなくなり、受信側での道路形状の再現性が悪くなり、また、誤マッチングが発生する可能性が高くなるためである。【００１１】  具体的な方法として、各区間ｊのリサンプル長Ｌｊが取り得る値（量子化リサンプル長）を、例えば、４０／８０／１６０／３２０／６４０／１２８０／２５６０／５１２０メートルのように予め設定し、区間ｊの曲率半径ρｊを用いて、次式（数１）によりＬｊを求め、この値に最も近い量子化リサンプル長をリサンプル長Ｌｊとして決定するリサンプル長決定方法が開示されている。【００１２】    Ｌｊ＝ρｊ・Ｋｒ  （Ｋｒは固定パラメータ）          （数１）
しかし、（数１）を用いるリサンプル長決定方法は、図１７に示すように、真円を近似する多角形の辺の長さを求めていることに等しく、真円を近似する多角形の辺数（角数）自体は、曲率半径の大小に関わらず一定である。そのため、図１７（ａ）のように、曲率半径が小さいとき（円が小さいとき）は、円と多角形との間の最大誤差も小さいが、図１７（ｂ）に示すように、曲率半径が大きいと、円と多角形との間の最大誤差、即ち、元形状とサンプリング点を繋ぐ近似形状（リサンプル形状）との間の最大誤差が大きくなる、と言う問題点がある。【００１３】  図１８には、従来の方法で決定したリサンプル長により道路形状をリサンプルして符号化データを生成した後、この符号化データから再現したリサンプル形状を示している。なだらかに曲がる高速道路のカーブに対して、再現したリサンプル形状の追従性は、良くないことが見て取れる。【００１４】  リサンプル形状の追従性は、（数１）のＫｒを小さく設定することで改善できるが、その場合は、真円を近似する多角形の辺数（角数）を増やすことに相当し、曲率半径が小さい道路形状に対して、必要以上に細かなリサンプル長を選定することになり、符号化データの圧縮率が落ちるという問題点が生じる。【００１５】  また、図１９の（ａ）、（ｂ）、（ｃ）に示すように、道路が直線的に交差する曲がり角（以下、交差角度の如何に関わらす「Ｖ字カーブ」と呼ぶことにする）は、円弧の一部と見なして曲率半径を算出するには無理がある。そのため、従来のリサンプル長決定方法では、Ｖ字カーブを示す元形状に対して適切なリサンプル長を設定することができない、と言う問題点がある。【００１６】  本発明は、こうした従来の問題点を解決するものであり、符号化データのデータ量の増大を招かずに、元形状に対する誤差が少ないリサンプル形状を得ることができるリサンプル長の決定方法を提供し、また、それを用いた符号化データ生成方法、及び、それらの方法を実施する装置を提供することを目的としている。
【特許文献１】特開２００３−２３３５７号
【発明の開示】
【００１７】  本発明のリサンプル長決定方法では、線形対象物をリサンプルするサンプリング点間のリサンプル長を、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、予め決めた許容誤差を超えないように設定している。
【００１８】  このように、許容誤差を予め定義し、それを超えないようにリサンプル長を決定しているので、リサンプル形状は、線形対象物に良く追従する。
他の観点から本発明を把握すると、本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、以下の（１）〜（４）のステップを含む。
【００１９】  （１）線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップ。
（２）前記判定ステップの結果、線形対象物の形状が円弧の一部に近似すると判断された場合に、線形対象物の曲率半径を算出するステップ。
【００２０】  （３）線形対象物の曲率半径ρが所定値以上又は所定値より大きい場合に、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、所定の許容誤差Ｅｍａｘを超えないようにリサンプル長を設定するステップ。
【００２１】  （４）線形対象物の曲率半径ρが所定値以下又は所定値より小さい場合に、線形対象物を曲率半径ρに対応した多角形で近似することでリサンプル長を設定するステップ。
また、本発明のリサンプル長決定方法では、前記（３）の場合に、
√（ρ２−（ρ−Ｅｍａｘ）２）
を含む判定式の値に基づいてリサンプル長を決定するようにすることができる。
【００２２】  この判定式を使うことで、許容誤差を超えないリサンプル長が決定できる。
また、本発明のリサンプル長決定方法では、前記（４）の場合に、曲率半径ρ、固定パラメータＫｒを用いたＫ・ρを含む判定式に基づいてサンプリング長を決定することができる。
【００２３】  一方、前記（４）の場合に、ρが小さい程、Ｅｍａｘも小さくなるように、Ｅｍａｘをρに応じて変更するようにすることができる。
こうすることで、線形対象物がきつい小さなカーブを示している場合でも、リサンプル形状が元形状に対して大きく歪むことが無くなる。
【００２４】  また、本発明のリサンプル長決定方法では、線形対象物の折曲部分が円弧の一部とみなせないとき、この折曲部分との誤差が許容誤差を超えない円の一部で折曲部分を近似した後、前記判定式の値を算出し、算出した値に基づいてリサンプル長を決定する。
【００２５】  こうすることで、Ｖ字カーブの箇所でも、適切なリサンプル長が決定できる。
また、線状対象形状物の形状が、円弧の一部に近似しない折曲部分を含むと判断された場合に、折曲部分の前後は、偏角の大きさに応じて予め決めたリサンプル長を選出するようにしてもよい。
【００２６】  また、線形対象物の形状が円弧の一部に近似するか否か判定するステップを、偏角の大きさ、又は偏角及びノード間の距離の関係を用いて行うようにしてもよい。
また、本発明の符号化データ生成方法では、線形対象物をリサンプルするサンプリング点間のリサンプル長を、前述するいずれかの方法で決定し、線形対象物を、決定したリサンプル長でリサンプルして複数のサンプリング点を設定し、各サンプリング点の位置データを、発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する。
【００２７】  こうした方法で、データ量がそれ程多く無く、且つ、元形状に対して誤差が少ない、線形対象物を表す符号化データを得ることができる。
また、本発明には、線形形状をリサンプルするサンプリング点間のリサンプル長を前述するいずれかの方法で決定するリサンプル長決定部を備える装置が含まれる。
【００２８】  また、本発明の符号化データ生成装置には、線形形状をリサンプルするサンプリング点間のリサンプル長を前述するいずれかの方法で決定するリサンプル長決定部と、リサンプル長決定部が決定したリサンプル長で線形形状をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部とを設けている。
【００２９】  これらの装置では、前述するリサンプル長決定方法や符号化データ生成方法を実施することができる。
また、上述の構成を、プローブカーの走行軌跡を伝えるプローブカー車載機に適用することができる。
【００３０】  更に本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムをも含む。当該プログラムは上述の（１）〜（４）のステップをコンピュータに実行させるものである。
【００３１】  また、上述した線形対象物の符号化データ生成方法を用いて得られた符号化データを受信する受信部と、当該受信された符号化データを復元する復元部とを備える符号化データ復元装置も本発明に含まれる。
【００３２】  本発明のリサンプル長決定方法では、データ量の増大を招くこと無く、元形状に対して誤差が少ないリサンプル形状を齎すリサンプル長を決定することができる。また、Ｖ字カーブの箇所にも、適切なリサンプル長を決定することができる。
【図面の簡単な説明】
【００３３】
【図１】本発明の第１の実施形態におけるリサンプル長決定方法で着目する道路形状とリサンプル形状との誤差を説明する図である。
【図２】中心線リサンプルを説明する図である。
【図３】本発明の第１の実施形態におけるリサンプル長決定方法の手順を示すフロー図である。
【図４】道路リンクの長さ及び偏角を示す図である。
【図５】曲率の定義を説明する図である。
【図６】本発明の第１の実施形態におけるリサンプル長決定方法で決定したリサンプル長を対象道路の始端から距離で表した図である。
【図７】本発明の第１の実施形態におけるリサンプル長決定方法を実施する情報送信装置の構成を示すブロック図である。
【図８】本発明の第１の実施形態におけるリサンプル長決定方法を実施するプローブカー車載機の構成を示すブロック図である。
【図９】本発明の第２の実施形態におけるリサンプル長決定方法を説明する図である。
【図１０】本発明の第２の実施形態におけるリサンプル長決定方法でのＶ字カーブを近似する円の設定の仕方を説明する図である。
【図１１】本発明の第２の実施形態におけるリサンプル長決定方法の手順を示すフロー図である。
【図１２】本発明の第２の実施形態におけるＶ字カーブ判定手順を示すフロー図である。
【図１３】（ａ）はＶ字カーブ判定手順でＶ字カーブと判定されるリンク形状を示す図であり、図１３（ｂ）はＶ字カーブ判定手順で非Ｖ字カーブと判定されるリンク形状を示す図である。
【図１４】デジタル地図上の道路の元形状が円弧に近似している場合のリサンプル長決定方法の適用例を示す図である。
【図１５】単一変数値の統計的に偏りを持つ値への変換方法を説明する図である。
【図１６】リサンプル長を違えて設定した道路区間を示す図である。
【図１７】従来のリサンプル長決定方法の問題点を説明する図である。
【図１８】道路形状とリサンプル形状との乖離を示す図である。
【図１９】従来のリサンプル長決定方法が適用できないＶ字カーブを説明する図である。
【発明を実施するための最良の形態】
【００３４】  （第１の実施形態）
本発明の第１の実施形態では、線形対象物である、デジタル地図上の道路の元形状が円弧に近似している場合のリサンプル長決定方法について説明する。言い換えると、道路の元形状が、所定の条件下において円弧の一部に近似する、又は円弧の一部とみなせる場合のリサンプル長決定方法について説明する。【００３５】  このリサンプル長決定方法では、サンプリング点を繋ぐ近似形状（リサンプル形状）と道路形状との間の許容誤差Ｅｍａｘを予め定義する。そして、道路形状の曲率半径が所定値以上又は所定値より大であるとき（即ち、従来の方法を採ると、道路形状とリサンプル形状との誤差が許容誤差Ｅｍａｘを超える虞があるとき）は、許容誤差Ｅｍａｘを超えないように、事前に設定された複数の量子化リサンプル長の中から、使用するリサンプル長を決定する。また、道路形状の曲率半径が所定値より小さいまたは所定値以下のときは、従来と同様の方法でリサンプル長を決定する。【００３６】  なお、許容誤差Ｅｍａｘの決め方の詳細は、特開２００２−３２８０３３号公報に記載されている。例えば、次のような条件を満たすようにＥｍａｘを設定する。
・対象道路区間の始点、終点近辺では、許容誤差を小さく設定する。
・並走道路が隣接する場合は、許容誤差を小さく設定する。
・インターチェンジ入出路などの交差角度の浅い接続道路が存在する交差点周辺では、許容誤差を小さく設定する。いま、図１に示すように、道路形状を曲率半径ρの真円にモデル化する。この真円上にリサンプル長をＬとしてサンプリング点を設定したときのリサンプル形状と道路形状との最大誤差（直線近似誤差）Ｅｒは、次式（数２）により算出できる。【００３７】    Ｅｒ＝ρ−√（ρ２−（Ｌ／２）２）                  （数２）
この（数２）をＬで展開すると、
Ｌ＝２√（ρ２−（ρ−Ｅｒ）２）                    （数３）
となる。そのため、道路形状とリサンプル形状との誤差が許容誤差Ｅｍａｘを超えないようにするためには、リサンプル長Ｌは、次式（数４）の条件を満たせばよい。【００３８】    Ｌ≦２√（ρ２−（ρ−Ｅｍａｘ）２）                （数４）
ただし、ρ≧Ｅｍａｘ，Ｅｍａｘ＞０
尚、この明細書では、「リサンプル形状と線形対象物の誤差」は、図１におけるＥｒをさす。【００３９】  また、図２に示すように、サンプリング点を真円上からずらして設定し、サンプリング点間を繋ぐ直線の左右に真円の線分が同程度分布するようにリサンプルする（「中心線リサンプル」と言う）場合は、リサンプル形状と道路形状との間の誤差成分が、理想的にはリサンプル形状の左右に均等にバラけるので、中心線リサンプルでは、リサンプル長Ｌは、次式（数５）の条件を満たせばよいことになる。【００４０】    Ｌ≦２×２√（ρ２−（ρ−Ｅｍａｘ）２）            （数５）
ただし、ρ≧Ｅｍａｘ，Ｅｍａｘ＞０
しかし、実際の道路形状の円弧は真円とは異なるため、安全率を見込んで、ρが所定値以上（概ねＥｍａｘの２〜５倍）のときのリサンプル区間長判定値Ｌ０を次式（数６）のように設定する。【００４１】    Ｌ０＝α×２√（ρ２−（ρ−Ｅｍａｘ）２）              （数６）
ただし、中心線リサンプルを行う場合は、α＝１．２〜１．８
中心線リサンプルを行わない場合は、α＝０．６〜０．９
そして、（数６）より算出したＬ０を基に量子化リサンプル長Ｌｎを決定する。上述のリサンプル長の決定方法は、√（ρ２−（ρ−Ｅｍａｘ）２）を含む判定式に基づいて行われるということができる。【００４２】  また、ρが前記所定値より小さい又は所定値以下のときは、上述の式によってＬ０を決定しても、元の形状からの歪み、乖離度合いは大きくなる。従ってこの場合、リサンプル区間長判定値Ｌ０を次式（数７）のように設定する。この設定は、形状を曲率半径に対応した多角形で近似することでリサンプル長を設定する。【００４３】    Ｌ０＝Ｋｒ・ｐ                                （数７）
ただし、Ｋｒは固定パラメータ
そして、（数７）より算出したＬ０を基に量子化リサンプル長Ｌｎを決定する。上述のリサンプル長の決定方法は、Ｋｒ・ρを含む判定式に基づいて行われるということができる。【００４４】  これらのリサンプル区間長判定値Ｌ０に基づいて量子化リサンプル長Ｌｎを決定することにより、道路形状がなだらかで大きなカーブを示している場合でも、リサンプル形状が道路形状から大きく外れることは無くなり、また、道路形状がきつい小さなカーブを示している場合でも、リサンプル形状が道路形状に対して大きく歪むことが無くなる。【００４５】  従って、受信側では、受信データを復号化して、リサンプル形状を的確に再現することができる。
なお、道路形状の曲率半径ρが所定値より小さい又は所定値以下の場合のリサンプル区間長判定値（数７）を設定する代わりに、許容誤差（Ｅｏ）を曲率半径ρの関数として設定し（ρが小さいときにＥｏも小さくなる）、ρの大きさに関わらず、（数６）のリサンプル区間長判定値を用いて、量子化リサンプル長Ｌｎを決定するようにしても良い。【００４６】  この場合、許容誤差（Ｅｏ）を例えば次式（数８）（数９）のように設定する。
Ｅｏ＝Ｅｍａｘ                                  （数８）
ただし、ρが所定値以上のとき（例えば、γ・ρ≧Ｅｍａｘ）
Ｅｏ＝γ・ρ                                      （数９）
ここで、γは１以下の定数（概ね０．２〜０．５）とする。また、（数９）は、Ｅｏがρの単調増加関数であれば、他のものでも良い。本方式は、曲率半径ρが小さい程、許容誤差Ｅｍａｘも小さくなるように、許容誤差Ｅｍａｘを曲率半径ρに応じて変更するものである。【００４７】  図３は、（数６）及び（数７）のリサンプル区間長判定値Ｌ０を用いて、実際にリサンプル長を設定する手順を示している。
まず、道路形状とリサンプル形状との間の最大許容誤差Ｅｍａｘを決定する（ステップ１）。次に、デジタル地図データベースから対象道路の道路形状データを取得する（ステップ２）。道路形状データは、図４に示すように、ノード及びリンクのデータを含んでいる。ｎ＝２のリンクｎから順に着目して（ステップ３）、リンクｎの長さＳｎ、及び、隣接リンク（ｎ−１）との偏角θｎを用いて、次式（数１０）により曲率ａｎを算出する（ステップ４）。【００４８】    ａｎ≒θｎ／Ｓｎ                            （数１０）
なお、２次元曲線における曲率は、図５に示すように、曲線上でΔＬだけ離れた２点Ｐ（Ｌ）、Ｐ（Ｌ＋ΔＬ）での接線の間の角度をΔωとして、Δω／ΔＬのΔＬ→０の極限値ｄω／ｄＬとして定義され、その逆数ρが点Ｐでの曲率半径として定義される。（数１０）は、ΔＬを極限値ではない直線Ｓｎで近似し、さらにΔωをθｎで近似したものであるが、ここでの目的がリサンプル区間長判定値を算出することであり、厳密性が要求されるものではないため、（数１０）により曲率の近似値を算出しても実用上支障がない。【００４９】  次に、次式（数１１）により曲率半径ρｎを算出する（ステップ５）。
ρｎ≒１／ａｎ                                （数１１）
曲率半径ρｎが規定値以上か否かを識別し（ステップ６）、規定値以上であるときは、（数６）を用いて算出したリサンプル区間長判定値に基づいて、リンクｎの量子化リサンプル長Ｌｎを決定する（ステップ７）。また、曲率半径ρｎが規定値より小さいときは、（数７）を用いて算出したリサンプル区間長判定値に基づいて、リンクｎの量子化リサンプル長Ｌｎを決定する（ステップ８）。【００５０】  なお、ステップ８では、Ｅｏ＝γ・ρ（または、Ｅｏはρの適切な単調増加関数）として、Ｌ０＝α×２√（ρ２−（ρ−Ｅｏ）２）から算出したリサンプル区間長判定値Ｌ０に基づいて、リンクｎの量子化リサンプル長Ｌｎを決定しても良い。【００５１】  次のリンクに着目して（ステップ１０）、ステップ４以降の手順を繰り返し、対象道路の全てのリンクについての処理が終了すると（ステップ９）、隣接リンク間で量子化リサンプル長が同じ場合にリンクを連結し、図６に示すように、対象道路全体のリサンプル長（Ｌ２、Ｌ４、・・・、Ｌ３）を始端からの距離で表現する（ステップ１１）。次に、対象道路に対し、このリサンプル長を用いてリサンプル処理を行い、サンプリング点の位置情報を偏角または偏角予測差分値で表し、可変長符号化を行ってデータ圧縮する（ステップ１２）。【００５２】  こうした処理により、データ量が少なく、道路の元形状と良く近似した道路位置を表す符号化データを得ることができる。
図７は、交通情報の対象道路を伝えるために、このリサンプル長決定方法を実行する情報送信装置（符号化データ生成装置）２０と、提供された交通情報を活用する、車載用ナビゲーション装置やパーソナルコンピュータなどの情報活用装置（符号化データ復元装置）４０との構成を示している。情報送信装置２０は、渋滞情報や交通事故情報などが入力される事象情報入力部２１と、デジタル地図データベースＡ２２から交通情報の対象道路区間の道路形状データを抽出する形状データ抽出部２３と、リサンプル形状と元形状データとの間の許容誤差を決定する許容誤差決定部２４と、許容誤差に基づいてリサンプル長Ｌを決定するリサンプル長決定部２５と、形状データ抽出部２３で抽出された道路形状データをリサンプルしてサンプリング点の位置データ列を生成する形状データリサンプル処理部２６と、形状データリサンプル処理部２６が生成したデータを圧縮符号化する可変長符号化処理部２８と、圧縮符号化された道路形状データを蓄積して外部メディアに蓄積データを提供する圧縮データ蓄積部２７と、圧縮符号化された道路形状データを送信する形状データ送信部２９とを備えている。【００５３】  一方、情報活用装置４０は、提供された道路形状データを受信する形状データ受信部４１と、圧縮符号化されているデータを復号する符号化データ復号部４２と、リサンプル形状を復元する形状データ復元部４３と、デジタル地図データベースＢ４６のデータを用いてマップマッチングを行い、サンプリング点で表された道路区間をデジタル地図上で特定するマップマチング部４５と、得られた交通情報を活用する情報活用部４４とを備えている。【００５４】  情報送信装置２０では、リサンプル長決定部２５が、許容誤差決定部２４で決定された許容誤差に基づいて、リサンプルにおけるリサンプル長Ｌを決定する。形状データリサンプル処理部２６は、決定されたリサンプル長Ｌを用いて、形状データ抽出部２３が抽出した対象道路の道路形状データをリサンプルする。【００５５】  可変長符号化処理部２８は、この道路形状データを可変長符号化する。可変長符号化によりデータ圧縮された道路形状データは、外部メディアに記録されて提供され、あるいは、形状データ送信部２９から送信される。【００５６】  この道路形状データを受信した情報活用装置４０では、符号化データ復号部４２が、圧縮符号化されているデータを復号化し、形状データ復元部４３が、サンプリング点の位置情報を復元して、サンプリング点を繋いだリサンプル形状を再現する。このリサンプル形状は、情報活用装置４０の表示画面上にデジタル地図と重ねて表示される。【００５７】  また、伝えられた道路区間を正確に特定するために、マップマッチング部４５は、サンプリング点の位置データとデジタル地図データベースＢ４６の地図データとのマップマッチングを行い、デジタル地図データベースＢ４６の地図データ上で対象道路を特定する。【００５８】  情報活用部４４は、得られた交通情報を、画面に表示したり、経路探索に利用したりして活用する。情報活用装置４０は、カーナビ受信機または地図表示端末をも構成し得る。
また、図８は、走行軌跡を伝えるために、このリサンプル長決定方法を実行するプローブカー車載機（符号化データ生成装置）６０と、プローブ情報を収集するプローブ情報収集センタ（符号化データ復元装置）５０との構成を示している。プローブカー車載機６０は、ＧＰＳアンテナ７３から受信する情報やジャイロ７４の検知情報を基に自車位置を判定する自車位置判定部６１と、速度を検出するセンサ７０と、ハンドル舵角を検出するセンサ７１と、横方向の加速度（横Ｇ）を検出するセンサ７２と、デジタル地図のデータベース６９と、リサンプル形状と道路形状との間の許容誤差を決定する許容誤差決定部６７と、リサンプルに用いるリサンプル長Ｌを決定するリサンプル長決定部６８と、自車の走行軌跡を蓄積する走行軌跡蓄積部６２と、走行軌跡をリサンプルしてサンプリング点の位置データ列を生成する走行軌跡形状リサンプル処理部６３と、走行軌跡形状リサンプル処理部６３が生成したデータを圧縮符号化する可変長符号化処理部６４と、圧縮符号化された走行軌跡形状データを蓄積する圧縮データ蓄積部６５と、圧縮符号化された走行軌跡形状データを送信する走行軌跡送信部６６とを備えている。【００５９】  一方、プローブ情報収集センタ５０は、プローブカー車載機６０から提供された走行軌跡形状データを受信する走行軌跡受信部５１と、圧縮符号化されている受信データを復号化する符号化データ復号部５２と、復号化されたデータから走行軌跡形状を復元する走行軌跡形状復元部５３と、プローブカー車載機６０から収集した走行軌跡や計測情報を交通情報の生成に活用する走行軌跡計測情報活用部５４とを備えている。【００６０】  プローブカー車載機６０の走行軌跡蓄積部６２には、自車位置判定部６１で検出された自車位置が走行軌跡として順次蓄積される。リサンプル長決定部６８は、センサ７０、７１、７２で検知された速度、ハンドル舵角、横Ｇの情報や、デジタル地図データベース６９から取得した道路形状から、走行軌跡の曲率の大小を判定し、その曲率の大きさや、許容誤差決定部６７で決定された許容誤差に基づいて、リサンプルに使用するリサンプル長Ｌを決定する。【００６１】  走行軌跡形状リサンプル処理部６３は、プローブ情報の送信時期に、走行軌跡蓄積部６２に蓄積された走行軌跡データを読み出し、リサンプル長決定部６８が決定したリサンプル長を用いて走行軌跡形状をリサンプルする。【００６２】  可変長符号化処理部６４は、このデータを可変長符号化して圧縮する。圧縮符号化されたデータは、プローブ情報収集センタ５０に送信される。また、このデータは、外部メディアに格納してプローブ情報収集センタ５０に提供される場合もある。【００６３】  プローブ情報収集センタ５０では、符号化データ復号部５２が、プローブカー車載機６０から収集したデータを復号化し、走行軌跡形状復元部５３が、サンプリング点の位置情報を復元して、走行軌跡のリサンプル形状を再現する。この走行軌跡の情報は、プローブカー車載機６０で計測された速度等の計測情報と併せて交通情報の生成に活用される。【００６４】  このように、情報送信装置やプローブカー車載機が、本発明のリサンプル長決定方法を用いて、対象道路や走行軌跡の符号化を行うことにより、この符号化データを受信する情報活用装置やプローブ情報収集センタでは、受信データを復号化して、リサンプル形状を的確に再現することができる。【００６５】  （第２の実施形態）
本発明の第２の実施形態では、道路形状が円弧の一部とみなせないときの例として、Ｖ字カーブでのリサンプル長の決定方法について説明する。【００６６】  Ｖ字カーブでは、図９に示すように、Ｖ字カーブ部分を、それに接する円で近似してリサンプルを行う。円の大きさは、図１０に示すように、Ｖ字カーブと円との間の最大誤差が、予め設定した許容誤差Ｅｍａｘ２を超えないように設定する。【００６７】  円の半径をＲ、円とＶ字カーブとの接点Ｐ１、Ｐ２からＶ字カーブの交点Ｐまでの距離をＤとすると、
ω＝（１８０−θ）／２
（Ｒ＋Ｅｍａｘ２）２＝Ｄ２＋Ｒ２
Ｄ・ｔａｎω＝Ｒ
の関係が成立するので、これらの式から、Ｄは（数１２）として、また、Ｒは（数１３）として算出することができる。【００６８】  Ｄ＝Ｅｍａｘ２・［ｔａｎω＋√｛（ｔａｎω）２＋１｝］          （数１２）
Ｒ＝Ｄ／ｔａｎω
＝Ｅｍａｘ２・［１＋（√｛（ｔａｎω）２＋１｝）／ｔａｎω］  （数１３）
そして、Ｖ字カーブをリサンプルする場合は、点Ｐから距離Ｄだけ離れた直線上にノードＰ１、Ｐ２を追加し、Ｐ１→Ｐ→Ｐ２間は曲率半径Ｒの円と見立てて、Ｒで決定されるリサンプル長Ｌによってリサンプルを行う。【００６９】  図１１のフロー図は、Ｖ字カーブでのリサンプル処理手順を示している。
まず、Ｖ字カーブの最大許容誤差Ｅｍａｘ２を決定する（ステップ２１）。次に、デジタル地図データベースから対象道路の道路形状データを取得する（ステップ２２）。ｎ＝２のリンクｎから順に着目して（ステップ２３）、リンクｎ及び隣接リンク（ｎ−１）の情報を取得し（ステップ２４）、リンクｎと隣接リンク（ｎ−１）とがＶ字カーブであるか否か判定する（ステップ２５）。【００７０】  この判定は、図１２に示す手順で行う。即ち、リンク（ｎ−１）とリンクｎとの間の偏角θｎ、及び、リンクｎの長さＳｎを算出し（ステップ４１）、θｎ及びＳｎを用いて（数１０）（数１１）により曲率半径ρｎを算出する（ステップ４２）。【００７１】  次に、定数κを用いて、Ｓｎ≦κ・ρｎの条件式を満たすかどうかを判定する（ステップ４３）。図１３（ａ）に示すように、Ｓｎが長いときは、この条件式を満たさない。この場合は、リンク（ｎ−１）→リンクｎ間が円弧近似の無理なＶ字カーブと判定する（ステップ４５）。また、図１３（ｂ）に示すように、Ｓｎが短いときは、この条件式を満たす。この場合は、リンク（ｎ−１）→リンクｎ間が円弧近似の可能な通常のカーブと判定する（ステップ４４）。κ＝１のとき、Ｓｎが、曲率半径ρｎの円弧を正六角形以上の角数で近似していれば条件式を満たすことになる。【００７２】  リンク（ｎ−１）→リンクｎ間がＶ字カーブである場合は、Ｅｍａｘ２の値を基に、（数１２）（数１３）を用いてＤ及びＲを算出し（ステップ２７）、リンク（ｎ−１）とリンクｎとの接続点Ｐから距離Ｄだけ離れたリンク上にノードＰ１、Ｐ２を追加し、Ｐ１→Ｐ→Ｐ２間の曲率半径をＲとする（ステップ２７）。【００７３】  そして、第１の実施形態で説明したリサンプル長決定方法を用いて量子化リサンプル長Ｌｎを決定する（ステップ２８）。また、ステップ２５において、リンク（ｎ−１）→リンクｎ間がＶ字カーブで無い場合は、直ぐにステップ２８の処理を行う。【００７４】  こうした処理を全てのリンクについて行い、全てのリンクに対する処理が終了すると、第１の実施形態と同様に、隣接リンク間で量子化リサンプル長が同じ場合にリンクを連結し、対象道路全体のリサンプル長を始端からの距離で表現し（ステップ３１）、対象道路へのリサンプル処理及び可変長符号化処理を行う（ステップ３２）。【００７５】  こうした処理により、Ｖ字カーブに対しても適切なリサンプル長を設定することができる。
また、道路形状が、Ｖ時カーブの如き円弧の一部に近似しない折曲部分を含む場合、折曲部分の前後は、偏角の大きさに応じて予めリサンプル長を選出するよう設定しておいてもよい。例えば、偏角が２６度以上で４０度より小さい場合は、リサンプル長は５０ｍ、４０度以上で６０度より小さい場合は３０ｍ、６０度以上の場合は１５ｍ、のように偏角に応じてリサンプル長を設定しておいてもよい。偏角が２６度より小さい場合は、第１の実施形態で述べたリサンプル長の決定方法が用いられる。【００７６】  また、道路形状が円弧の一部に近似するか否か判定するに際し、当該道路に予め設定されているノード毎の偏角の大きさ、又は当該偏角の大きさ及びノード間の距離の関係を用いることができる。【００７７】  図１４はデジタル地図上の道路の元形状が円弧に近似している場合において、元のデジタル地図の道路上にノードが設定されている状態を示す図である。
上述の通り、円弧とみなせるかみなせないかは、偏角の大きさとノード間距離によって判別することできる。【００７８】  偏角θとノード間距離Ｌから曲率半径ρを算出し、Ｌ＜２√（ρ２−（ρ−Ｅ）２）ならば、元の対象道路は、交差点やＶ字カーブではなくスムーズなカーブであったと判別できる。ここで、Ｅにはデジタル化の入力誤差±５ｍ程度（元の地図をデジタル化した際における標準的な誤差）が入る。【００７９】  図１４の内側の円の場合、曲率半径は１３０ｍであり、最も長いと思われる線分（ノード間距離）の長さは６６ｍである。地図データのデジタル化の入力誤差Ｅ＝５ｍとすると、２√（ρ２−（ρ−Ｅ）２）＝７１ｍとなる。【００８０】  他のノード間距離はこれより小さいので、よって、この計算方法でほぼ正しいといえる。
また、計算を略して偏角のみでもおおむね判別することもできる。なだらかなカーブをデジタル化したような箇所であれば、偏角は小さいからである。【００８１】  また、図８では、プローブカー車載機６０とプローブ情報収集センタ５０の組み合わせより、プローブカーシステムが構築され、両者間でプローブカーシステムの情報伝達方法が達成されるが、当該方法は、本発明のリサンプル長決定方法、符号化データ生成方法及び当該符号化データの復号化方法の組み合わせより達成される。【００８２】  更に本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムをも含む。当該プログラムは、線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定する手順と、判定手順の結果、線形対象物の形状が円弧の一部に近似すると判断された場合に、線形対象物の曲率半径を算出する手順と、線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定する手順と、線形対象物の曲率半径が所定値以下又は所定値より小さい場合に、線形対象物を曲率半径に対応した多角形で近似する手順と、をコンピュータに実行させる。【００８３】  このようなプログラムは、情報送信装置２０、プローブカー車載機６０に、種々の形式で組み込まれる。例えば情報送信装置２０、プローブカー車載機６０内又はこれらの外部の装置内の所定のメモリにプログラムを記録することができる。また、ハードディスクのような情報記録装置や、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ、メモリカードのような情報記録媒体にプログラムを記録してもよい。また、ネットワーク経由により当該プログラムをダウンロードするようにしてもよい。【００８４】  また、本発明の情報送信装置２０と情報活用装置４０又はプローブカー車載機６０とプローブ情報収集センタ５０の組み合わせより、地図データ配信システムが構成される。情報送信装置２０とプローブカー車載機６０は、符号化データを生成するという観点からエンコーダとして機能し、情報活用装置４０とプローブ情報収集センタ５０は、符号化データを復元するという観点からデコーダとして機能する。【００８５】  また、符号化データ生成装置である情報送信装置２０又はプローブカー車載機６０は、情報送信側における実施の形態の例であり、情報を送信する事が出来る装置や端末であればどのような形態のものでもよい。さらに生成した符号化データを媒体に記録して、他の装置に提供することも可能である。また、符号化データ復元装置である情報活用装置４０又はプローブ情報収集センタ５０も情報受信側における実施の形態の例であり、パーソナルコンピュータ、携帯端末等の情報を活用できる装置であればなんでもよい。もちろん、符号化データの復元が可能な情報収集センターや、センター側の装置でも同様の効果を得ることが出来る。さらに符号化されたデータが記録された媒体等を用いて、復元処理することにより、同様の効果を得ることは言うまでもない。【００８６】  また、本発明の符号化データ生成方法に沿ったアルゴリズム（プログラム）を、地図データ本体に各種地図情報に対応した地図データが記録された記録媒体に記録することができる。これにより、地図データ本体自体を圧縮符号化することが可能となる。【００８７】  尚、上述の実施形態においては、線形対象物が位置参照用の道路形状である例を説明したが、線形対象物は道路形状に限られない。「線形対象物」とは直線、曲線など種々の形態を含む細長い形状のものを総て含み、地図上の線形形状によって表わせる地理情報総てを含み得る。更に、指紋等地図とは関係ないが、線形形状によって表わされるもの総てをも含まれる。【００８８】  本発明を詳細にまた特定の実施態様を参照して説明したが、本発明の精神と範囲を逸脱することなく様々な変更や修正を加えることができることは当業者にとって明らかである。【００８９】  本出願は、２００３年１０月２１日出願の日本特許出願（特願２００３−３６０６３１）に基づくものであり、その内容はここに参照として取り込まれる。
【産業上の利用可能性】
【００９０】  本発明のリサンプル長決定方法及び符号化データ生成方法は、デジタル地図の道路形状や河川、鉄道線路、行政境界線、等高線などの位置情報を表す符号化データを生成・蓄積・保存するときなどに利用することができ、また、デジタル地図以外にも、各種の図形や指紋などの形状を表す符号化データを生成・蓄積・保存するときなどに適用することができる。また、本発明の装置は、その符号化データの生成・蓄積・保存を実行する各種装置に適用することができる。
【図１】
2005038752.tif 000003
【図２】
2005038752.tif 000004
【図３】
2005038752.tif 000005
【図４】
2005038752.tif 000006
【図５】
2005038752.tif 000007
【図６】
2005038752.tif 000008
【図７】
2005038752.tif 000009
【図８】
2005038752.tif 000010
【図９】
2005038752.tif 000011
【図１０】
2005038752.tif 000012
【図１１】
2005038752.tif 000013
【図１２】
2005038752.tif 000014
【図１３】
2005038752.tif 000015
【図１４】
2005038752.tif 000016
【図１５】
2005038752.tif 000017
【図１６】
2005038752.tif 000018
【図１７】
2005038752.tif 000019
【図１８】
2005038752.tif 000020
【図１９】
2005038752.tif 000021
【手続補正書】
【提出日】平成18年3月22日(2006.3.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
線形対象物をリサンプルするサンプリング点間のリサンプル長を、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、予め決めた許容誤差を超えないように設定する、リサンプル長決定方法。
【請求項２】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記形状が前記円弧の一部に近似すると判断された場合に、前記線形対象物の曲率半径を算出するステップと、
前記線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定するステップと、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さい場合に、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップと、
を備えるリサンプル長決定方法。
【請求項３】
請求項１又は２記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が所定値以上又は所定値より大きいと判断され、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定するステップにおいて、前記線形対象物の曲率半径をρ、前記許容誤差をＥｍａｘとして、
√（ρ2−（ρ−Ｅｍａｘ）2）
を含む判定式の値に基づいて前記リサンプル長を決定する、リサンプル長決定方法。
【請求項４】
請求項２記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さいと判断され、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップにおいて、前記線形対象物の曲率半径ρ、さらに固定パラメータＫｒを用いた、Ｋｒ・ρを含む判定式に基づいて前記サンプリング長を決定する、リサンプル長決定方法。
【請求項５】
請求項２記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さいと判断され、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップにおいて、前記曲率半径が小さい程、前記許容誤差も小さくなるように、前記許容誤差を前記曲率半径に応じて変更する、リサンプル長決定方法。
【請求項６】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記線状対象形状物の形状が、前記円弧の一部に近似しない折曲部分を含むと判断された場合に、前記折曲部分との誤差が許容誤差を超えない円の一部で前記折曲部分を近似するステップと、
前記判定式の値を算出し、当該算出した値に基づいて前記リサンプル長を決定するステップと、
を備えるリサンプル長決定方法。
【請求項７】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記線状対象形状物の形状が、前記円弧の一部に近似しない折曲部分を含むと判断された場合に、前記折曲部分の前後は、偏角の大きさに応じて予め決めたリサンプル長を選出する、リサンプル長決定方法。
【請求項８】
請求項２ないし７のいずれか１項記載のリサンプル長決定方法であって、
前記線形対象物の形状が円弧の一部に近似するか否か判定するステップが、偏角の大きさ、又は偏角及びノード間の距離の関係を用いて行われる、リサンプル長決定方法。
【請求項９】
請求項１ないし８のいずれか１項に記載された方法により線形対象物のリサンプル長を決定するステップと、
前記線形対象物を、決定したリサンプル長でリサンプルして複数のサンプリング点を設定するステップと、
各サンプリング点の位置データを、発生頻度に偏りを持つ角度成分で表現するステップと、
前記角度成分で表わされた位置データを順番に並べたデータ列に対して可変長符号化を行うステップと、を備える線形対象物の符号化データ生成方法。
【請求項１０】
請求項１ないし８のいずれか１項記載のリサンプル長決定方法を用いて、線形対象物をリサンプルするサンプリング点間のリサンプル長を決定するリサンプル長決定部を備える装置。
【請求項１１】
線形対象物をリサンプルするサンプリング点間のリサンプル長を請求項１ないし請求項８のいずれか１項記載のリサンプル長決定方法で決定するリサンプル長決定部と、
前記リサンプル長決定部が決定したリサンプル長で前記線形対象物をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、
前記リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部と、を備える符号化データ生成装置。
【請求項１２】
プローブカーの走行軌跡を伝えるプローブカー車載機であって、
線形対象物をリサンプルするサンプリング点間のリサンプル長を請求項１ないし請求項８のいずれか１項記載のリサンプル長決定方法で決定するリサンプル長決定部と、
前記リサンプル長決定部が決定したリサンプル長で前記線形対象物をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、
前記リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部と、を備えるプローブカー車載機。
【請求項１３】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムであって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定する手順と、
前記判定手順の結果、前記形状が前記円弧の一部に近似すると判断された場合に、前記線形対象物の曲率半径を算出する手順と、
前記線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定する手順と、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さい場合に、前記線形対象物を曲率半径に対応した多角形で近似する手順と、をコンピュータに実行させるプログラム。
【請求項１４】
請求項９記載の線形対象物の符号化データ生成方法を用いて得られた符号化データを受信する受信部と、
当該受信された符号化データを復元する復元部と、を備える符号化データ復元装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道路位置等を表す符号化データを生成するため、デジタル地図の道路等の形状に沿って複数のサンプリング点を設定する場合のサンプリング点間隔（リサンプル長）の決定方法と、それを用いた符号化データ生成方法と、それらの方法を実施する装置に関し、元形状との誤差が少なく、且つ、符号化データのデータ量を増やさないようなリサンプル長の決め方を提案するものである。
【背景技術】
【０００２】
従来から、ＶＩＣＳ（道路交通情報通信システム）では、デジタル地図データベースを搭載する車両用ナビゲーション装置に対して、ＦＭ多重放送やビーコンを通じて、渋滞区間や旅行時間を示す道路交通情報の提供サービスを実施している。車両用ナビゲーション装置は、この道路交通情報を受信して、画面表示する地図に渋滞区間を色付けして表したり、目的地までの所用時間を算出して表示したりしている。
【０００３】
このように、道路交通情報を提供する場合には、デジタル地図上の道路の位置情報を伝えることが必要になる。また、現在地及び目的地の情報を受信して、最短時間で目的地まで到達できる推奨経路の情報を提供するサービスや、近年、研究が進められている、走行中の車両（プローブカー）から軌跡情報及び速度情報等を収集する道路交通情報収集システム（プローブ情報収集システム）においても、デジタル地図上の推奨経路や走行軌跡を相手方に正しく伝えることが必要である。
【０００４】
これまで、デジタル地図上の道路位置を伝える場合には、一般的に、道路に付されたリンク番号や、交差点などのノードを特定するノード番号が使用されている。しかし、道路網に定義したノード番号やリンク番号は、道路の新設や変更に伴って新しい番号に付け替える必要があり、それに応じて、各社で制作されるデジタル地図データも更新しなければならないため、ノード番号やリンク番号を用いる方式は、メンテナンスに多大な社会的コストが掛かることになる。
【０００５】
こうした点を改善するため、特開２００３−２３３５７号公報では、ノード番号やリンク番号を用いずに、且つ、少ないデータ量でデジタル地図上の道路位置を伝える方法を提案している。
【０００６】
この方法では、伝えようとするデジタル地図上の道路区間に一定距離間隔でサンプリング点を再設定し（これを「等距離リサンプル」と言う）、各サンプリング点の位置データを順番に並べたデータ列に対して圧縮符号化の処理を施し、圧縮符号化したデータを送信する。これを受信した受信側は、サンプリング点の位置データのデータ列を復元し、自己のデジタル地図上に道路形状を再現する。また、必要に応じて、この位置データを使用して、自己のデジタル地図上で位置特定、位置参照を実施し（マップマッチング）道路区間を特定する。
【０００７】
位置データのデータ列に対する圧縮符号化は、次に示すように、（１）位置データの単一変数への変換、（２）単一変数で表わした値の統計的に偏りを持つ値への変換、（３）変換した値の可変長符号化、の順に行われる。
【０００８】
（１）位置データの単一変数への変換
図１５（ａ）には、等距離リサンプルで設定した道路区間上のサンプリング点をＰJ-1、ＰJで表している。このサンプリング点（Ｐ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
として算出される。道路が一定の曲率で湾曲している場合には、各サンプリング点の偏角予測差分値Δθは０付近に集中し、統計的に偏りを持つデータとなる。
【００１１】
図１５（ｄ）は、直線的な道路区間を偏角θで表示した場合、及び、曲線的な道路区間を偏角予測差分値Δθで表示した場合のデータの発生頻度をグラフ化して示している。θ及びΔθの発生頻度はθ（又はΔθ）＝０°に極大が現れ、統計的に偏りを持っている。
【００１２】
（３）可変長符号化
次に、統計的に偏りを持つ値に変換したデータ列の値を可変長符号化する。可変長符号化方法には、固定数値圧縮法（０圧縮等）、シャノン・ファノ符号法、ハフマン符号法、算術符号法、辞書法など多種存在し、いずれの方法を用いてもよい。最も一般的なハフマン符号法を用いる場合では、発生頻度が高いデータに少ないビット数の符号を定義し、発生頻度が低いデータに多いビット数の符号を定義した符号表を用いて、統計的に偏りを持たせたデータ列の値を符号化し、トータルのデータ量を削減する。
【００１３】
また、特開２００３−２３３５７号公報では、図１６に示すように、道路形状の曲率が大きい区間Ｂでは、等距離リサンプルの距離Ｌ２を短く設定し、曲率が小さい、直線的な道路区間Ａでは、等距離リサンプルの距離Ｌ１を長く設定することを提案している。これは、曲率が大きく、カーブがきつい道路を長い距離でリサンプルすると、特徴的な道路形状を示す位置にサンプリング点を配置することができなくなり、受信側での道路形状の再現性が悪くなり、また、誤マッチングが発生する可能性が高くなるためである。
【００１４】
具体的な方法として、各区間ｊのリサンプル長Ｌjが取り得る値（量子化リサンプル長）を、例えば、４０／８０／１６０／３２０／６４０／１２８０／２５６０／５１２０メートルのように予め設定し、区間ｊの曲率半径ρjを用いて、次式（数１）によりＬjを求め、この値に最も近い量子化リサンプル長をリサンプル長Ｌjとして決定するリサンプル長決定方法が開示されている。
【００１５】
Ｌj＝ρj・Ｋr （Ｋrは固定パラメータ）                （数１）
【特許文献１】特開２００３−２３３５７号
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかし、（数１）を用いるリサンプル長決定方法は、図１７に示すように、真円を近似する多角形の辺の長さを求めていることに等しく、真円を近似する多角形の辺数（角数）自体は、曲率半径の大小に関わらず一定である。そのため、図１７（ａ）のように、曲率半径が小さいとき（円が小さいとき）は、円と多角形との間の最大誤差も小さいが、図１７（ｂ）に示すように、曲率半径が大きいと、円と多角形との間の最大誤差、即ち、元形状とサンプリング点を繋ぐ近似形状（リサンプル形状）との間の最大誤差が大きくなる、と言う問題点がある。
【００１７】
図１８には、従来の方法で決定したリサンプル長により道路形状をリサンプルして符号化データを生成した後、この符号化データから再現したリサンプル形状を示している。なだらかに曲がる高速道路のカーブに対して、再現したリサンプル形状の追従性は、良くないことが見て取れる。
【００１８】
リサンプル形状の追従性は、（数１）のＫrを小さく設定することで改善できるが、その場合は、真円を近似する多角形の辺数（角数）を増やすことに相当し、曲率半径が小さい道路形状に対して、必要以上に細かなリサンプル長を選定することになり、符号化データの圧縮率が落ちるという問題点が生じる。
【００１９】
また、図１９の（ａ）、（ｂ）、（ｃ）に示すように、道路が直線的に交差する曲がり角（以下、交差角度の如何に関わらす「Ｖ字カーブ」と呼ぶことにする）は、円弧の一部と見なして曲率半径を算出するには無理がある。そのため、従来のリサンプル長決定方法では、Ｖ字カーブを示す元形状に対して適切なリサンプル長を設定することができない、と言う問題点がある。
【００２０】
本発明は、こうした従来の問題点を解決するものであり、符号化データのデータ量の増大を招かずに、元形状に対する誤差が少ないリサンプル形状を得ることができるリサンプル長の決定方法を提供し、また、それを用いた符号化データ生成方法、及び、それらの方法を実施する装置を提供することを目的としている。
【課題を解決するための手段】
【００２１】
本発明のリサンプル長決定方法では、線形対象物をリサンプルするサンプリング点間のリサンプル長を、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、予め決めた許容誤差を超えないように設定している。
【００２２】
このように、許容誤差を予め定義し、それを超えないようにリサンプル長を決定しているので、リサンプル形状は、線形対象物に良く追従する。
他の観点から本発明を把握すると、本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、以下の（１）〜（４）のステップを含む。
【００２３】
（１）線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップ。
（２）前記判定ステップの結果、線形対象物の形状が円弧の一部に近似すると判断された場合に、線形対象物の曲率半径を算出するステップ。
（３）線形対象物の曲率半径ρが所定値以上又は所定値より大きい場合に、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、所定の許容誤差Ｅｍａｘを超えないようにリサンプル長を設定するステップ。
（４）線形対象物の曲率半径ρが所定値以下又は所定値より小さい場合に、線形対象物を曲率半径ρに対応した多角形で近似することでリサンプル長を設定するステップ。
【００２４】
また、本発明のリサンプル長決定方法では、前記（３）の場合に、
√（ρ2−（ρ−Ｅｍａｘ）2）
を含む判定式の値に基づいてリサンプル長を決定するようにすることができる。
【００２５】
この判定式を使うことで、許容誤差を超えないリサンプル長が決定できる。
また、本発明のリサンプル長決定方法では、前記（４）の場合に、曲率半径ρ、固定パラメータＫｒを用いたＫ・ρを含む判定式に基づいてサンプリング長を決定することができる。
【００２６】
一方、前記（４）の場合に、ρが小さい程、Ｅｍａｘも小さくなるように、Ｅｍａｘをρに応じて変更するようにすることができる。
こうすることで、線形対象物がきつい小さなカーブを示している場合でも、リサンプル形状が元形状に対して大きく歪むことが無くなる。
【００２７】
また、本発明のリサンプル長決定方法では、線形対象物の折曲部分が円弧の一部とみなせないとき、この折曲部分との誤差が許容誤差を超えない円の一部で折曲部分を近似した後、前記判定式の値を算出し、算出した値に基づいてリサンプル長を決定する。
【００２８】
こうすることで、Ｖ字カーブの箇所でも、適切なリサンプル長が決定できる。
また、線状対象形状物の形状が、円弧の一部に近似しない折曲部分を含むと判断された場合に、折曲部分の前後は、偏角の大きさに応じて予め決めたリサンプル長を選出するようにしてもよい。
【００２９】
また、線形対象物の形状が円弧の一部に近似するか否か判定するステップを、偏角の大きさ、又は偏角及びノード間の距離の関係を用いて行うようにしてもよい。
また、本発明の符号化データ生成方法では、線形対象物をリサンプルするサンプリング点間のリサンプル長を、前述するいずれかの方法で決定し、線形対象物を、決定したリサンプル長でリサンプルして複数のサンプリング点を設定し、各サンプリング点の位置データを、発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する。
【００３０】
こうした方法で、データ量がそれ程多く無く、且つ、元形状に対して誤差が少ない、線形対象物を表す符号化データを得ることができる。
また、本発明には、線形形状をリサンプルするサンプリング点間のリサンプル長を前述するいずれかの方法で決定するリサンプル長決定部を備える装置が含まれる。
【００３１】
また、本発明の符号化データ生成装置には、線形形状をリサンプルするサンプリング点間のリサンプル長を前述するいずれかの方法で決定するリサンプル長決定部と、リサンプル長決定部が決定したリサンプル長で線形形状をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部とを設けている。
【００３２】
これらの装置では、前述するリサンプル長決定方法や符号化データ生成方法を実施することができる。
また、上述の構成を、プローブカーの走行軌跡を伝えるプローブカー車載機に適用することができる。
【００３３】
更に本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムをも含む。当該プログラムは上述の（１）〜（４）のステップをコンピュータに実行させるものである。
【００３４】
また、上述した線形対象物の符号化データ生成方法を用いて得られた符号化データを受信する受信部と、当該受信された符号化データを復元する復元部とを備える符号化データ復元装置も本発明に含まれる。
【発明の効果】
【００３５】
本発明のリサンプル長決定方法では、データ量の増大を招くこと無く、元形状に対して誤差が少ないリサンプル形状を齎すリサンプル長を決定することができる。また、Ｖ字カーブの箇所にも、適切なリサンプル長を決定することができる。
【発明を実施するための最良の形態】
【００３６】
（第１の実施形態）
本発明の第１の実施形態では、線形対象物である、デジタル地図上の道路の元形状が円弧に近似している場合のリサンプル長決定方法について説明する。言い換えると、道路の元形状が、所定の条件下において円弧の一部に近似する、又は円弧の一部とみなせる場合のリサンプル長決定方法について説明する。
【００３７】
このリサンプル長決定方法では、サンプリング点を繋ぐ近似形状（リサンプル形状）と道路形状との間の許容誤差Ｅｍａｘを予め定義する。そして、道路形状の曲率半径が所定値以上又は所定値より大であるとき（即ち、従来の方法を採ると、道路形状とリサンプル形状との誤差が許容誤差Ｅｍａｘを超える虞があるとき）は、許容誤差Ｅｍａｘを超えないように、事前に設定された複数の量子化リサンプル長の中から、使用するリサンプル長を決定する。また、道路形状の曲率半径が所定値より小さいまたは所定値以下のときは、従来と同様の方法でリサンプル長を決定する。
【００３８】
なお、許容誤差Ｅｍａｘの決め方の詳細は、特開２００２−３２８０３３号公報に記載されている。例えば、次のような条件を満たすようにＥｍａｘを設定する。
・対象道路区間の始点、終点近辺では、許容誤差を小さく設定する。
・並走道路が隣接する場合は、許容誤差を小さく設定する。
・インターチェンジ入出路などの交差角度の浅い接続道路が存在する交差点周辺では、許容誤差を小さく設定する。  いま、図１に示すように、道路形状を曲率半径ρの真円にモデル化する。この真円上にリサンプル長をＬとしてサンプリング点を設定したときのリサンプル形状と道路形状との最大誤差（直線近似誤差）Ｅｒは、次式（数２）により算出できる。
【００３９】
Ｅｒ＝ρ−√（ρ2−（Ｌ/２）2）                        （数２）
この（数２）をＬで展開すると、
Ｌ ＝２√（ρ2−（ρ−Ｅｒ）2）                        （数３）
となる。そのため、道路形状とリサンプル形状との誤差が許容誤差Ｅｍａｘを超えないようにするためには、リサンプル長Ｌは、次式（数４）の条件を満たせばよい。
【００４０】
Ｌ≦２√（ρ2−（ρ−Ｅｍａｘ）2）                      （数４）
ただし、ρ≧Ｅｍａｘ，Ｅｍａｘ＞０
尚、この明細書では、「リサンプル形状と線形対象物の誤差」は、図１におけるＥｒをさす。
【００４１】
また、図２に示すように、サンプリング点を真円上からずらして設定し、サンプリング点間を繋ぐ直線の左右に真円の線分が同程度分布するようにリサンプルする（「中心線リサンプル」と言う）場合は、リサンプル形状と道路形状との間の誤差成分が、理想的にはリサンプル形状の左右に均等にバラけるので、中心線リサンプルでは、リサンプル長Ｌは、次式（数５）の条件を満たせばよいことになる。
【００４２】
Ｌ≦２×２√（ρ2−（ρ−Ｅｍａｘ）2）                  （数５）
ただし、ρ≧Ｅｍａｘ，Ｅｍａｘ＞０
しかし、実際の道路形状の円弧は真円とは異なるため、安全率を見込んで、ρが所定値以上（概ねＥｍａｘの２〜５倍）のときのリサンプル区間長判定値Ｌ0を次式（数６）のように設定する。
【００４３】
Ｌ0＝α×２√（ρ2−（ρ−Ｅｍａｘ）2）                  （数６）
ただし、中心線リサンプルを行う場合は、α＝１．２〜１．８
中心線リサンプルを行わない場合は、α＝０．６〜０．９
そして、（数６）より算出したＬ0を基に量子化リサンプル長Ｌｎを決定する。上述のリサンプル長の決定方法は、√（ρ2−（ρ−Ｅｍａｘ）2）を含む判定式に基づいて行われるということができる。
【００４４】
また、ρが前記所定値より小さい又は所定値以下のときは、上述の式によってＬ0を決定しても、元の形状からの歪み、乖離度合いは大きくなる。従ってこの場合、リサンプル区間長判定値Ｌ0を次式（数７）のように設定する。この設定は、形状を曲率半径に対応した多角形で近似することでリサンプル長を設定する。
【００４５】
Ｌ0＝Ｋｒ・ρ                                          （数７）
ただし、Ｋrは固定パラメータ
そして、（数７）より算出したＬ0を基に量子化リサンプル長Ｌｎを決定する。上述のリサンプル長の決定方法は、Ｋｒ・ρを含む判定式に基づいて行われるということができる。
【００４６】
これらのリサンプル区間長判定値Ｌ0に基づいて量子化リサンプル長Ｌｎを決定することにより、道路形状がなだらかで大きなカーブを示している場合でも、リサンプル形状が道路形状から大きく外れることは無くなり、また、道路形状がきつい小さなカーブを示している場合でも、リサンプル形状が道路形状に対して大きく歪むことが無くなる。
【００４７】
従って、受信側では、受信データを復号化して、リサンプル形状を的確に再現することができる。
なお、道路形状の曲率半径ρが所定値より小さい又は所定値以下の場合のリサンプル区間長判定値（数７）を設定する代わりに、許容誤差（Ｅｏ）を曲率半径ρの関数として設定し（ρが小さいときにＥｏも小さくなる）、ρの大きさに関わらず、（数６）のリサンプル区間長判定値を用いて、量子化リサンプル長Ｌｎを決定するようにしても良い。
【００４８】
この場合、許容誤差（Ｅｏ）を例えば次式（数８）（数９）のように設定する。
Ｅｏ＝Ｅｍａｘ                                          （数８）
ただし、ρが所定値以上のとき（例えば、γ・ρ≧Ｅｍａｘ）
Ｅｏ＝γ・ρ                                            （数９）
ここで、γは１以下の定数（概ね０．２〜０．５）とする。また、（数９）は、Ｅｏがρの単調増加関数であれば、他のものでも良い。本方式は、曲率半径ρが小さい程、許容誤差Ｅｍａｘも小さくなるように、許容誤差Ｅｍａｘを曲率半径ρに応じて変更するものである。
【００４９】
図３は、（数６）及び（数７）のリサンプル区間長判定値Ｌ0を用いて、実際にリサンプル長を設定する手順を示している。
まず、道路形状とリサンプル形状との間の最大許容誤差Ｅｍａｘを決定する（ステップ１）。次に、デジタル地図データベースから対象道路の道路形状データを取得する（ステップ２）。道路形状データは、図４に示すように、ノード及びリンクのデータを含んでいる。ｎ＝２のリンクｎから順に着目して（ステップ３）、リンクｎの長さＳｎ、及び、隣接リンク（ｎ−１）との偏角θｎを用いて、次式（数１０）により曲率ａｎを算出する（ステップ４）。
【００５０】
ａｎ≒θｎ／Ｓｎ                                          （数１０）
なお、２次元曲線における曲率は、図５に示すように、曲線上でΔＬだけ離れた２点Ｐ（Ｌ）、Ｐ（Ｌ＋ΔＬ）での接線の間の角度をΔωとして、Δω/ΔＬのΔＬ→０の極限値dω/ｄＬとして定義され、その逆数ρが点Ｐでの曲率半径として定義される。（数１０）は、ΔＬを極限値ではない直線Ｓｎで近似し、さらにΔωをθｎで近似したものであるが、ここでの目的がリサンプル区間長判定値を算出することであり、厳密性が要求されるものではないため、（数１０）により曲率の近似値を算出しても実用上支障がない。
【００５１】
次に、次式（数１１）により曲率半径ρｎを算出する（ステップ５）。
ρｎ≒１／ａｎ                                            （数１１）
曲率半径ρｎが規定値以上か否かを識別し（ステップ６）、規定値以上であるときは、（数６）を用いて算出したリサンプル区間長判定値に基づいて、リンクｎの量子化リサンプル長Ｌｎを決定する（ステップ７）。また、曲率半径ρｎが規定値より小さいときは、（数７）を用いて算出したリサンプル区間長判定値に基づいて、リンクｎの量子化リサンプル長Ｌｎを決定する（ステップ８）。
【００５２】
なお、ステップ８では、Ｅｏ＝γ・ρ（または、Ｅｏはρの適切な単調増加関数）として、Ｌ0＝α×２√（ρ2−（ρ−Ｅｏ）2）から算出したリサンプル区間長判定値Ｌ0に基づいて、リンクｎの量子化リサンプル長Ｌｎを決定しても良い。
【００５３】
次のリンクに着目して（ステップ１０）、ステップ４以降の手順を繰り返し、対象道路の全てのリンクについての処理が終了すると（ステップ９）、隣接リンク間で量子化リサンプル長が同じ場合にリンクを連結し、図６に示すように、対象道路全体のリサンプル長（Ｌ２、Ｌ４、・・・、Ｌ３）を始端からの距離で表現する（ステップ１１）。次に、対象道路に対し、このリサンプル長を用いてリサンプル処理を行い、サンプリング点の位置情報を偏角または偏角予測差分値で表し、可変長符号化を行ってデータ圧縮する（ステップ１２）。
【００５４】
こうした処理により、データ量が少なく、道路の元形状と良く近似した道路位置を表す符号化データを得ることができる。
図７は、交通情報の対象道路を伝えるために、このリサンプル長決定方法を実行する情報送信装置（符号化データ生成装置）２０と、提供された交通情報を活用する、車載用ナビゲーション装置やパーソナルコンピュータなどの情報活用装置（符号化データ復元装置）４０との構成を示している。情報送信装置２０は、渋滞情報や交通事故情報などが入力される事象情報入力部２１と、デジタル地図データベースＡ２２から交通情報の対象道路区間の道路形状データを抽出する形状データ抽出部２３と、リサンプル形状と元形状データとの間の許容誤差を決定する許容誤差決定部２４と、許容誤差に基づいてリサンプル長Ｌを決定するリサンプル長決定部２５と、形状データ抽出部２３で抽出された道路形状データをリサンプルしてサンプリング点の位置データ列を生成する形状データリサンプル処理部２６と、形状データリサンプル処理部２６が生成したデータを圧縮符号化する可変長符号化処理部２８と、圧縮符号化された道路形状データを蓄積して外部メディアに蓄積データを提供する圧縮データ蓄積部２７と、圧縮符号化された道路形状データを送信する形状データ送信部２９とを備えている。
【００５５】
一方、情報活用装置４０は、提供された道路形状データを受信する形状データ受信部４１と、圧縮符号化されているデータを復号する符号化データ復号部４２と、リサンプル形状を復元する形状データ復元部４３と、デジタル地図データベースＢ４６のデータを用いてマップマッチングを行い、サンプリング点で表された道路区間をデジタル地図上で特定するマップマチング部４５と、得られた交通情報を活用する情報活用部４４とを備えている。
【００５６】
情報送信装置２０では、リサンプル長決定部２５が、許容誤差決定部２４で決定された許容誤差に基づいて、リサンプルにおけるリサンプル長Ｌを決定する。形状データリサンプル処理部２６は、決定されたリサンプル長Ｌを用いて、形状データ抽出部２３が抽出した対象道路の道路形状データをリサンプルする。
【００５７】
可変長符号化処理部２８は、この道路形状データを可変長符号化する。可変長符号化によりデータ圧縮された道路形状データは、外部メディアに記録されて提供され、あるいは、形状データ送信部２９から送信される。
【００５８】
この道路形状データを受信した情報活用装置４０では、符号化データ復号部４２が、圧縮符号化されているデータを復号化し、形状データ復元部４３が、サンプリング点の位置情報を復元して、サンプリング点を繋いだリサンプル形状を再現する。このリサンプル形状は、情報活用装置４０の表示画面上にデジタル地図と重ねて表示される。
【００５９】
また、伝えられた道路区間を正確に特定するために、マップマッチング部４５は、サンプリング点の位置データとデジタル地図データベースＢ４６の地図データとのマップマッチングを行い、デジタル地図データベースＢ４６の地図データ上で対象道路を特定する。
【００６０】
情報活用部４４は、得られた交通情報を、画面に表示したり、経路探索に利用したりして活用する。情報活用装置４０は、カーナビ受信機または地図表示端末をも構成し得る。
また、図８は、走行軌跡を伝えるために、このリサンプル長決定方法を実行するプローブカー車載機（符号化データ生成装置）６０と、プローブ情報を収集するプローブ情報収集センタ（符号化データ復元装置）５０との構成を示している。プローブカー車載機６０は、ＧＰＳアンテナ７３から受信する情報やジャイロ７４の検知情報を基に自車位置を判定する自車位置判定部６１と、速度を検出するセンサ７０と、ハンドル舵角を検出するセンサ７１と、横方向の加速度（横Ｇ）を検出するセンサ７２と、デジタル地図のデータベース６９と、リサンプル形状と道路形状との間の許容誤差を決定する許容誤差決定部６７と、リサンプルに用いるリサンプル長Ｌを決定するリサンプル長決定部６８と、自車の走行軌跡を蓄積する走行軌跡蓄積部６２と、走行軌跡をリサンプルしてサンプリング点の位置データ列を生成する走行軌跡形状リサンプル処理部６３と、走行軌跡形状リサンプル処理部６３が生成したデータを圧縮符号化する可変長符号化処理部６４と、圧縮符号化された走行軌跡形状データを蓄積する圧縮データ蓄積部６５と、圧縮符号化された走行軌跡形状データを送信する走行軌跡送信部６６とを備えている。
【００６１】
一方、プローブ情報収集センタ５０は、プローブカー車載機６０から提供された走行軌跡形状データを受信する走行軌跡受信部５１と、圧縮符号化されている受信データを復号化する符号化データ復号部５２と、復号化されたデータから走行軌跡形状を復元する走行軌跡形状復元部５３と、プローブカー車載機６０から収集した走行軌跡や計測情報を交通情報の生成に活用する走行軌跡計測情報活用部５４とを備えている。
【００６２】
プローブカー車載機６０の走行軌跡蓄積部６２には、自車位置判定部６１で検出された自車位置が走行軌跡として順次蓄積される。リサンプル長決定部６８は、センサ７０、７１、７２で検知された速度、ハンドル舵角、横Ｇの情報や、デジタル地図データベース６９から取得した道路形状から、走行軌跡の曲率の大小を判定し、その曲率の大きさや、許容誤差決定部６７で決定された許容誤差に基づいて、リサンプルに使用するリサンプル長Ｌを決定する。
【００６３】
走行軌跡形状リサンプル処理部６３は、プローブ情報の送信時期に、走行軌跡蓄積部６２に蓄積された走行軌跡データを読み出し、リサンプル長決定部６８が決定したリサンプル長を用いて走行軌跡形状をリサンプルする。
【００６４】
可変長符号化処理部６４は、このデータを可変長符号化して圧縮する。圧縮符号化されたデータは、プローブ情報収集センタ５０に送信される。また、このデータは、外部メディアに格納してプローブ情報収集センタ５０に提供される場合もある。
【００６５】
プローブ情報収集センタ５０では、符号化データ復号部５２が、プローブカー車載機６０から収集したデータを復号化し、走行軌跡形状復元部５３が、サンプリング点の位置情報を復元して、走行軌跡のリサンプル形状を再現する。この走行軌跡の情報は、プローブカー車載機６０で計測された速度等の計測情報と併せて交通情報の生成に活用される。
【００６６】
このように、情報送信装置やプローブカー車載機が、本発明のリサンプル長決定方法を用いて、対象道路や走行軌跡の符号化を行うことにより、この符号化データを受信する情報活用装置やプローブ情報収集センタでは、受信データを復号化して、リサンプル形状を的確に再現することができる。
【００６７】
（第２の実施形態）
本発明の第２の実施形態では、道路形状が円弧の一部とみなせないときの例として、Ｖ字カーブでのリサンプル長の決定方法について説明する。
【００６８】
Ｖ字カーブでは、図９に示すように、Ｖ字カーブ部分を、それに接する円で近似してリサンプルを行う。円の大きさは、図１０に示すように、Ｖ字カーブと円との間の最大誤差が、予め設定した許容誤差Ｅｍａｘ２を超えないように設定する。
【００６９】
円の半径をＲ、円とＶ字カーブとの接点Ｐ１、Ｐ２からＶ字カーブの交点Ｐまでの距離をＤとすると、
ω＝（１８０−θ）／２
（Ｒ＋Ｅｍａｘ２）2＝Ｄ2＋Ｒ2
Ｄ・ｔａｎω＝Ｒ
の関係が成立するので、これらの式から、Ｄは（数１２）として、また、Ｒは（数１３）として算出することができる。
【００７０】
Ｄ＝Ｅｍａｘ２・［ｔａｎω＋√｛（ｔａｎω）2＋１｝］          （数１２）
Ｒ＝Ｄ／ｔａｎω
＝Ｅｍａｘ２・［１＋（√｛（ｔａｎω）2＋１｝）／ｔａｎω］  （数１３）
そして、Ｖ字カーブをリサンプルする場合は、点Ｐから距離Ｄだけ離れた直線上にノードＰ１、Ｐ２を追加し、Ｐ１→Ｐ→Ｐ２間は曲率半径Ｒの円と見立てて、Ｒで決定されるリサンプル長Ｌによってリサンプルを行う。
【００７１】
図１１のフロー図は、Ｖ字カーブでのリサンプル処理手順を示している。
まず、Ｖ字カーブの最大許容誤差Ｅｍａｘ２を決定する（ステップ２１）。次に、デジタル地図データベースから対象道路の道路形状データを取得する（ステップ２２）。ｎ＝２のリンクｎから順に着目して（ステップ２３）、リンクｎ及び隣接リンク（ｎ−１）の情報を取得し（ステップ２４）、リンクｎと隣接リンク（ｎ−１）とがＶ字カーブであるか否か判定する（ステップ２５）。
【００７２】
この判定は、図１２に示す手順で行う。即ち、リンク（ｎ−１）とリンクｎとの間の偏角θｎ、及び、リンクｎの長さＳｎを算出し（ステップ４１）、θｎ及びＳｎを用いて（数１０）（数１１）により曲率半径ρｎを算出する（ステップ４２）。
【００７３】
次に、定数κを用いて、Ｓｎ≦κ・ρｎの条件式を満たすかどうかを判定する（ステップ４３）。図１３（ａ）に示すように、Ｓｎが長いときは、この条件式を満たさない。この場合は、リンク（ｎ−１）→リンクｎ間が円弧近似の無理なＶ字カーブと判定する（ステップ４５）。また、図１３（ｂ）に示すように、Ｓｎが短いときは、この条件式を満たす。この場合は、リンク（ｎ−１）→リンクｎ間が円弧近似の可能な通常のカーブと判定する（ステップ４４）。κ＝１のとき、Ｓｎが、曲率半径ρｎの円弧を正六角形以上の角数で近似していれば条件式を満たすことになる。
【００７４】
リンク（ｎ−１）→リンクｎ間がＶ字カーブである場合は、Ｅｍａｘ２の値を基に、（数１２）（数１３）を用いてＤ及びＲを算出し（ステップ２７）、リンク（ｎ−１）とリンクｎとの接続点Ｐから距離Ｄだけ離れたリンク上にノードＰ１、Ｐ２を追加し、Ｐ１→Ｐ→Ｐ２間の曲率半径をＲとする（ステップ２７）。
【００７５】
そして、第１の実施形態で説明したリサンプル長決定方法を用いて量子化リサンプル長Ｌｎを決定する（ステップ２８）。また、ステップ２５において、リンク（ｎ−１）→リンクｎ間がＶ字カーブで無い場合は、直ぐにステップ２８の処理を行う。
【００７６】
こうした処理を全てのリンクについて行い、全てのリンクに対する処理が終了すると、第１の実施形態と同様に、隣接リンク間で量子化リサンプル長が同じ場合にリンクを連結し、対象道路全体のリサンプル長を始端からの距離で表現し（ステップ３１）、対象道路へのリサンプル処理及び可変長符号化処理を行う（ステップ３２）。
【００７７】
こうした処理により、Ｖ字カーブに対しても適切なリサンプル長を設定することができる。
また、道路形状が、Ｖ時カーブの如き円弧の一部に近似しない折曲部分を含む場合、折曲部分の前後は、偏角の大きさに応じて予めリサンプル長を選出するよう設定しておいてもよい。例えば、偏角が２６度以上で４０度より小さい場合は、リサンプル長は５０ｍ、４０度以上で６０度より小さい場合は３０ｍ、６０度以上の場合は１５ｍ、のように偏角に応じてリサンプル長を設定しておいてもよい。偏角が２６度より小さい場合は、第１の実施形態で述べたリサンプル長の決定方法が用いられる。
【００７８】
また、道路形状が円弧の一部に近似するか否か判定するに際し、当該道路に予め設定されているノード毎の偏角の大きさ、又は当該偏角の大きさ及びノード間の距離の関係を用いることができる。
【００７９】
図１４はデジタル地図上の道路の元形状が円弧に近似している場合において、元のデジタル地図の道路上にノードが設定されている状態を示す図である。
上述の通り、円弧とみなせるかみなせないかは、偏角の大きさとノード間距離によって判別することできる。
【００８０】
偏角θとノード間距離Ｌから曲率半径ρを算出し、 Ｌ＜２√（ρ2−（ρ−Ｅ）2）  ならば、元の対象道路は、交差点やＶ字カーブではなくスムーズなカーブであったと判別できる。ここで、Ｅにはデジタル化の入力誤差±５ｍ程度（元の地図をデジタル化した際における標準的な誤差）が入る。
【００８１】
図１４の内側の円の場合、曲率半径は１３０ｍであり、最も長いと思われる線分（ノード間距離）の長さは６６ｍである。地図データのデジタル化の入力誤差Ｅ＝５ｍとすると、２√（ρ2−（ρ−Ｅ）2）＝７１ｍとなる。
【００８２】
他のノード間距離はこれより小さいので、よって、この計算方法でほぼ正しいといえる。
また、計算を略して偏角のみでもおおむね判別することもできる。なだらかなカーブをデジタル化したような箇所であれば、偏角は小さいからである。
【００８３】
また、図８では、プローブカー車載機６０とプローブ情報収集センタ５０の組み合わせより、プローブカーシステムが構築され、両者間でプローブカーシステムの情報伝達方法が達成されるが、当該方法は、本発明のリサンプル長決定方法、符号化データ生成方法及び当該符号化データの復号化方法の組み合わせより達成される。
【００８４】
更に本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムをも含む。当該プログラムは、線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定する手順と、判定手順の結果、線形対象物の形状が円弧の一部に近似すると判断された場合に、線形対象物の曲率半径を算出する手順と、線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定する手順と、線形対象物の曲率半径が所定値以下又は所定値より小さい場合に、線形対象物を曲率半径に対応した多角形で近似する手順と、をコンピュータに実行させる。
【００８５】
このようなプログラムは、情報送信装置２０、プローブカー車載機６０に、種々の形式で組み込まれる。例えば情報送信装置２０、プローブカー車載機６０内又はこれらの外部の装置内の所定のメモリにプログラムを記録することができる。また、ハードディスクのような情報記録装置や、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ、メモリカードのような情報記録媒体にプログラムを記録してもよい。また、ネットワーク経由により当該プログラムをダウンロードするようにしてもよい。
【００８６】
また、本発明の情報送信装置２０と情報活用装置４０又はプローブカー車載機６０とプローブ情報収集センタ５０の組み合わせより、地図データ配信システムが構成される。情報送信装置２０とプローブカー車載機６０は、符号化データを生成するという観点からエンコーダとして機能し、情報活用装置４０とプローブ情報収集センタ５０は、符号化データを復元するという観点からデコーダとして機能する。
【００８７】
また、符号化データ生成装置である情報送信装置２０又はプローブカー車載機６０は、情報送信側における実施の形態の例であり、情報を送信する事が出来る装置や端末であればどのような形態のものでもよい。さらに生成した符号化データを媒体に記録して、他の装置に提供することも可能である。また、符号化データ復元装置である情報活用装置４０又はプローブ情報収集センタ５０も情報受信側における実施の形態の例であり、パーソナルコンピュータ、携帯端末等の情報を活用できる装置であればなんでもよい。もちろん、符号化データの復元が可能な情報収集センターや、センター側の装置でも同様の効果を得ることが出来る。さらに符号化されたデータが記録された媒体等を用いて、復元処理することにより、同様の効果を得ることは言うまでもない。
【００８８】
また、本発明の符号化データ生成方法に沿ったアルゴリズム（プログラム）を、地図データ本体に各種地図情報に対応した地図データが記録された記録媒体に記録することができる。これにより、地図データ本体自体を圧縮符号化することが可能となる。
【００８９】
尚、上述の実施形態においては、線形対象物が位置参照用の道路形状である例を説明したが、線形対象物は道路形状に限られない。「線形対象物」とは直線、曲線など種々の形態を含む細長い形状のものを総て含み、地図上の線形形状によって表わせる地理情報総てを含み得る。更に、指紋等地図とは関係ないが、線形形状によって表わされるもの総てをも含まれる。
【００９０】
本発明を詳細にまた特定の実施態様を参照して説明したが、本発明の精神と範囲を逸脱することなく様々な変更や修正を加えることができることは当業者にとって明らかである。
【００９１】
本出願は、２００３年１０月２１日出願の日本特許出願（特願２００３−３６０６３１）に基づくものであり、その内容はここに参照として取り込まれる。
【産業上の利用可能性】
【００９２】
本発明のリサンプル長決定方法及び符号化データ生成方法は、デジタル地図の道路形状や河川、鉄道線路、行政境界線、等高線などの位置情報を表す符号化データを生成・蓄積・保存するときなどに利用することができ、また、デジタル地図以外にも、各種の図形や指紋などの形状を表す符号化データを生成・蓄積・保存するときなどに適用することができる。また、本発明の装置は、その符号化データの生成・蓄積・保存を実行する各種装置に適用することができる。
【図面の簡単な説明】
【００９３】
【図１】本発明の第１の実施形態におけるリサンプル長決定方法で着目する道路形状とリサンプル形状との誤差を説明する図である。
【図２】中心線リサンプルを説明する図である。
【図３】本発明の第１の実施形態におけるリサンプル長決定方法の手順を示すフロー図である。
【図４】道路リンクの長さ及び偏角を示す図である。
【図５】曲率の定義を説明する図である。
【図６】本発明の第１の実施形態におけるリサンプル長決定方法で決定したリサンプル長を対象道路の始端から距離で表した図である。
【図７】本発明の第１の実施形態におけるリサンプル長決定方法を実施する情報送信装置の構成を示すブロック図である。
【図８】本発明の第１の実施形態におけるリサンプル長決定方法を実施するプローブカー車載機の構成を示すブロック図である。
【図９】本発明の第２の実施形態におけるリサンプル長決定方法を説明する図である。
【図１０】本発明の第２の実施形態におけるリサンプル長決定方法でのＶ字カーブを近似する円の設定の仕方を説明する図である。
【図１１】本発明の第２の実施形態におけるリサンプル長決定方法の手順を示すフロー図である。
【図１２】本発明の第２の実施形態におけるＶ字カーブ判定手順を示すフロー図である。
【図１３】（ａ）はＶ字カーブ判定手順でＶ字カーブと判定されるリンク形状を示す図であり、図１３（ｂ）はＶ字カーブ判定手順で非Ｖ字カーブと判定されるリンク形状を示す図である。
【図１４】デジタル地図上の道路の元形状が円弧に近似している場合のリサンプル長決定方法の適用例を示す図である。
【図１５】単一変数値の統計的に偏りを持つ値への変換方法を説明する図である。
【図１６】リサンプル長を違えて設定した道路区間を示す図である。
【図１７】従来のリサンプル長決定方法の問題点を説明する図である。
【図１８】道路形状とリサンプル形状との乖離を示す図である。
【図１９】従来のリサンプル長決定方法が適用できないＶ字カーブを説明する図である。
【符号の説明】
【００９４】
２０  情報送信装置（符号化データ生成装置）
２１  事象情報入力部
２２  デジタル地図データベースＡ
２３  形状データ抽出部
２４  許容誤差決定部
２５  リサンプル長決定部
２６  形状データリサンプル処理部
２７  圧縮データ蓄積部
２８  可変長符号化処理部
２９  形状データ送信部
４０  情報活用装置（符号化データ復元装置）
４１  形状データ受信部
４２  符号化データ復号部
４３  形状データ復元部
４４  情報活用部
４５  マップマッチング部
４６  デジタル地図データベースＢ
５０  プローブ情報収集センタ
５１  走行軌跡受信部
５２  符号化データ復号部
５３  走行軌跡形状復元部
５４  走行軌跡計測情報活用部
６０  プローブカー車載機（符号化データ生成装置）
６１  自車位置判定部
６２  走行軌跡蓄積部
６３  走行軌跡形状リサンプル処理部
６４  可変長符号化処理部
６５  圧縮データ蓄積部
６６  走行軌跡送信部
６７  許容誤差決定部
６８  リサンプル長決定部
６９  デジタル地図データベース
７０  センサ
７１  センサ
７２  センサ
７３  ＧＰＳアンテナ
７４  ジャイロ
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2005038752.tif 000022
【図２】
2005038752.tif 000023
【図３】
2005038752.tif 000024
【図４】
2005038752.tif 000025
【図５】
2005038752.tif 000026
【図６】
2005038752.tif 000027
【図７】
2005038752.tif 000028
【図８】
2005038752.tif 000029
【図９】
2005038752.tif 000030
【図１０】
2005038752.tif 000031
【図１１】
2005038752.tif 000032
【図１２】
2005038752.tif 000033
【図１３】
2005038752.tif 000034
【図１４】
2005038752.tif 000035
【図１５】
2005038752.tif 000036
【図１６】
2005038752.tif 000037
【図１７】
2005038752.tif 000038
【図１８】
2005038752.tif 000039
【図１９】
2005038752.tif 000040
【手続補正書】
【提出日】平成19年10月15日(2007.10.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
線形対象物におけるサンプリング点間のサンプリング長決定方法であって、
前記線形対象物の形状が、所定の条件において円弧の一部に近似するか否か判定するステップと、
前記形状が前記円弧の一部に近似すると判断された場合に、前記線形対象物の曲率半径を算出するステップと、
前記線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、前記サンプリング点間を線で繋いだ形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにサンプリング長を設定するステップと、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さい場合に、前記線形対象物を曲率半径に対応した多角形で近似することでサンプリング長を設定するステップと、
を備えるサンプリング長決定方法。
【請求項２】
請求項１記載のサンプリング長決定方法であって、
前記線形対象物の曲率半径が所定値以上又は所定値より大きいと判断され、前記サンプリング点間を線で繋いだ形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにサンプリング長を設定するステップにおいて、前記線形対象物の曲率半径をρ、前記許容誤差をＥｍａｘとして、
√（ρ2−（ρ−Ｅｍａｘ）2）
を含む判定式の値に基づいて前記サンプリング長を決定する、サンプリング長決定方法。
【請求項３】
請求項２記載のサンプリング長決定方法であって、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さいと判断され、前記線形対象物を曲率半径に対応した多角形で近似することでサンプリング長を設定するステップにおいて、前記曲率半径が小さい程、前記許容誤差も小さくなるように、前記許容誤差を前記曲率半径に応じて変更する、サンプリング長決定方法。
【請求項４】
線形対象物におけるサンプリング点間のサンプリング長決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記線状対象物の形状が、前記円弧の一部に近似しない折曲部分を含むと判断された場合に、前記折曲部分の前後は、偏角の大きさに応じて予め決めたサンプリング長を選出する、サンプリング長決定方法。
【請求項５】
請求項１ないし４のいずれか１項に記載された方法により線形対象物のサンプリング長を決定するステップと、
前記線形対象物を、前記決定したサンプリング長でサンプリング点を設定するステップと、
各サンプリング点の位置データを、特定の値に偏りを持つ角度成分で表現するステップと、
前記角度成分で表わされたデータ列に対して符号化を行うステップと、を備える線形対象物の符号化データ生成方法。
【請求項６】
請求項１ないし４のいずれか１項記載のサンプリング長決定方法を用いて、線形対象物におけるサンプリング点間のサンプリング長を決定するサンプリング長決定部を備える装置。
【請求項７】
線形対象物におけるサンプリング長を請求項１ないし請求項４のいずれか１項記載のサンプリング長決定方法で決定するサンプリング長決定部と、
前記サンプリング長決定部が決定したサンプリング長でサンプリング点を設定するサンプリング処理部と、
前記サンプリング処理部が設定した各サンプリング点の位置データを特定の値に集中する特性を持つ角度成分で表し、各サンプリング点の位置データ列に対して符号化を行ってデータを圧縮する符号化処理部と、を備える符号化データ生成装置。
【請求項８】
車両の走行軌跡を伝える車載機であって、
線形対象物におけるサンプリング長を請求項１ないし請求項４のいずれか１項記載のサンプリング長決定方法で決定するサンプリング長決定部と、
前記サンプリング長決定部が決定したサンプリング長でサンプリング点を設定するサンプリング処理部と、
前記サンプリング処理部が設定した各サンプリング点の位置データを特定の値に集中する特性を持つ角度成分で表し、各サンプリング点の位置データ列に対して符号化を行ってデータを圧縮する符号化処理部と、を備える車載機。
【請求項９】
線形対象物におけるサンプリング点間のサンプリング長の決定をコンピュータに実行させる為のプログラムであって、
前記線形対象物の形状が、所定の条件において円弧の一部に近似するか否か判定する手順と、
前記形状が前記円弧の一部に近似すると判断された場合に、前記線形対象物の曲率半径を算出する手順と、
前記線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、前記サンプリング点間を線で繋いだ形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにサンプリング長を設定する手順と、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さい場合に、前記線形対象物を曲率半径に対応した多角形で近似することでサンプリング長を設定する手順と、をコンピュータに実行させるプログラム。
【請求項１０】
請求項５記載の線形対象物の符号化データ生成方法を用いて得られた符号化データを受信する受信部と、
当該受信された符号化データを復元する復元部と、を備える符号化データ復元装置。
【国際調査報告】
2005038752.tif 000041
2005038752.tif 000042