リサンプル長決定方法と装置
線形対象物をリサンプルするサンプリング点間のリサンプル長Lを、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差Erが、予め決めた許容誤差を超えないように設定する。許容誤差を予め定義し、それを超えないようにリサンプル長Lを決定しているので、リサンプル形状は、線形対象物に良く追従する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、道路位置等を表す符号化データを生成するため、デジタル地図の道路等の形状に沿って複数のサンプリング点を設定する場合のサンプリング点間隔(リサンプル長)の決定方法と、それを用いた符号化データ生成方法と、それらの方法を実施する装置に関し、元形状との誤差が少なく、且つ、符号化データのデータ量を増やさないようなリサンプル長の決め方を提案するものである。
【背景技術】
【0002】
従来から、VICS(道路交通情報通信システム)では、デジタル地図データベースを搭載する車両用ナビゲーション装置に対して、FM多重放送やビーコンを通じて、渋滞区間や旅行時間を示す道路交通情報の提供サービスを実施している。車両用ナビゲーション装置は、この道路交通情報を受信して、画面表示する地図に渋滞区間を色付けして表したり、目的地までの所用時間を算出して表示したりしている。
【0003】
このように、道路交通情報を提供する場合には、デジタル地図上の道路の位置情報を伝えることが必要になる。また、現在地及び目的地の情報を受信して、最短時間で目的地まで到達できる推奨経路の情報を提供するサービスや、近年、研究が進められている、走行中の車両(プローブカー)から軌跡情報及び速度情報等を収集する道路交通情報収集システム(プローブ情報収集システム)においても、デジタル地図上の推奨経路や走行軌跡を相手方に正しく伝えることが必要である。
【0004】
これまで、デジタル地図上の道路位置を伝える場合には、一般的に、道路に付されたリンク番号や、交差点などのノードを特定するノード番号が使用されている。しかし、道路網に定義したノード番号やリンク番号は、道路の新設や変更に伴って新しい番号に付け替える必要があり、それに応じて、各社で制作されるデジタル地図データも更新しなければならないため、ノード番号やリンク番号を用いる方式は、メンテナンスに多大な社会的コストが掛かることになる。
【0005】
こうした点を改善するため、特開2003−23357号公報では、ノード番号やリンク番号を用いずに、且つ、少ないデータ量でデジタル地図上の道路位置を伝える方法を提案している。
【0006】
この方法では、伝えようとするデジタル地図上の道路区間に一定距離間隔でサンプリング点を再設定し(これを「等距離リサンプル」と言う)、各サンプリング点の位置データを順番に並べたデータ列に対して圧縮符号化の処理を施し、圧縮符号化したデータを送信する。これを受信した受信側は、サンプリング点の位置データのデータ列を復元し、自己のデジタル地図上に道路形状を再現する。また、必要に応じて、この位置データを使用して、自己のデジタル地図上で位置特定、位置参照を実施し(マップマッチング)道路区間を特定する。
【0007】
位置データのデータ列に対する圧縮符号化は、次に示すように、(1)位置データの単一変数への変換、(2)単一変数で表わした値の統計的に偏りを持つ値への変換、(3)変換した値の可変長符号化、の順に行われる。
(1)位置データの単一変数への変換
図15(a)には、等距離リサンプルで設定した道路区間上のサンプリング点をPJ−1、PJで表している。このサンプリング点(PJ)は、隣接するサンプリング点(PJ−1)からの距離(リサンプル長)Lと角度Θとの2つのディメンジョンで一意に特定することができ、距離を一定(L)とすると、サンプリング点(PJ)は、隣接サンプリング点(PJ−1)からの角度成分Θのみの単一変数で表現することができる。図15(a)では、この角度Θとして、真北(図の上方)の方位を0度とし、時計回りに0〜360度の範囲で大きさを指定する「絶対方位」による角度Θを示している(真北からの絶対方位)。道路区間は、サンプリング点間の一定距離し、及び、始端または終端となるサンプリング点(基準点)の緯度・経度を別に示すことにより、各サンプリング点の角度成分のデータ列により表わすことができる。
(2)単一変数値の統計的に偏りを持つ値への変換
各サンプリング点の単一変数値が、可変長符号化に適した、統計的に偏在する値となるように、図15(b)に示すように、各サンプリング点の角度成分を、隣接するサンプリング点の角度成分との変位差、即ち、「偏角」θjによって表現する。この偏角θjは、
θj=Θj−Θj−1
として算出される。道路が直線的である場合に、各サンプリング点の偏角θは0付近に集中し、統計的に偏りを持つデータとなる。
【0008】
また、サンプリング点の角度成分は、図15(c)に示すように、着目するサンプリング点PJの偏角θjを、それ以前のサンプリング点PJ−1、PJ−2、・・の偏角θj−1、θj−2、・・を用いて予測した当該サンプリング点PJの偏角予測値Sj(統計予測値)との差分値(偏角予測差分値又は偏角予測誤差)Δθjで表わすことにより、統計的に偏りを持つデータに変換する
ことができる。統計予測値Sjは、例えば、
Sj=θj−1
と定義したり、
Sj=(θj−1+θj−2)/2
と定義したりすることができる。偏角予測差分値Δθjは、
Δθj=θj−Sj
として算出される。道路が一定の曲率で湾曲している場合には、各サンプリング点の偏角予測差分値Δθは0付近に集中し、統計的に偏りを持つデータとなる。
【0009】
図15(d)は、直線的な道路区間を偏角θで表示した場合、及び、曲線的な道路区間を偏角予測差分値Δθで表示した場合のデータの発生頻度をグラフ化して示している。θ及びΔθの発生頻度はθ(又はΔθ)=0°に極大が現れ、統計的に偏りを持っている。
(3)可変長符号化
次に、統計的に偏りを持つ値に変換したデータ列の値を可変長符号化する。可変長符号化方法には、固定数値圧縮法(0圧縮等)、シャノン・ファノ符号法、ハフマン符号法、算術符号法、辞書法など多種存在し、いずれの方法を用いてもよい。最も一般的なハフマン符号法を用いる場合では、発生頻度が高いデータに少ないビット数の符号を定義し、発生頻度が低いデータに多いビット数の符号を定義した符号表を用いて、統計的に偏りを持たせたデータ列の値を符号化し、トータルのデータ量を削減する。
【0010】
また、特開2003−23357号公報では、図16に示すように、道路形状の曲率が大きい区間Bでは、等距離リサンプルの距離L2を短く設定し、曲率が小さい、直線的な道路区間Aでは、等距離リサンプルの距離L1を長く設定することを提案している。これは、曲率が大きく、カーブがきつい道路を長い距離でリサンプルすると、特徴的な道路形状を示す位置にサンプリング点を配置することができなくなり、受信側での道路形状の再現性が悪くなり、また、誤マッチングが発生する可能性が高くなるためである。
【0011】
具体的な方法として、各区間jのリサンプル長Ljが取り得る値(量子化リサンプル長)を、例えば、40/80/160/320/640/1280/2560/5120メートルのように予め設定し、区間jの曲率半径ρjを用いて、次式(数1)によりLjを求め、この値に最も近い量子化リサンプル長をリサンプル長Ljとして決定するリサンプル長決定方法が開示されている。
【0012】
Lj=ρj・Kr (Krは固定パラメータ) (数1)
しかし、(数1)を用いるリサンプル長決定方法は、図17に示すように、真円を近似する多角形の辺の長さを求めていることに等しく、真円を近似する多角形の辺数(角数)自体は、曲率半径の大小に関わらず一定である。そのため、図17(a)のように、曲率半径が小さいとき(円が小さいとき)は、円と多角形との間の最大誤差も小さいが、図17(b)に示すように、曲率半径が大きいと、円と多角形との間の最大誤差、即ち、元形状とサンプリング点を繋ぐ近似形状(リサンプル形状)との間の最大誤差が大きくなる、と言う問題点がある。
【0013】
図18には、従来の方法で決定したリサンプル長により道路形状をリサンプルして符号化データを生成した後、この符号化データから再現したリサンプル形状を示している。なだらかに曲がる高速道路のカーブに対して、再現したリサンプル形状の追従性は、良くないことが見て取れる。
【0014】
リサンプル形状の追従性は、(数1)のKrを小さく設定することで改善できるが、その場合は、真円を近似する多角形の辺数(角数)を増やすことに相当し、曲率半径が小さい道路形状に対して、必要以上に細かなリサンプル長を選定することになり、符号化データの圧縮率が落ちるという問題点が生じる。
【0015】
また、図19の(a)、(b)、(c)に示すように、道路が直線的に交差する曲がり角(以下、交差角度の如何に関わらす「V字カーブ」と呼ぶことにする)は、円弧の一部と見なして曲率半径を算出するには無理がある。そのため、従来のリサンプル長決定方法では、V字カーブを示す元形状に対して適切なリサンプル長を設定することができない、と言う問題点がある。
【0016】
本発明は、こうした従来の問題点を解決するものであり、符号化データのデータ量の増大を招かずに、元形状に対する誤差が少ないリサンプル形状を得ることができるリサンプル長の決定方法を提供し、また、それを用いた符号化データ生成方法、及び、それらの方法を実施する装置を提供することを目的としている。
【特許文献1】特開2003−23357号
【発明の開示】
【0017】
本発明のリサンプル長決定方法では、線形対象物をリサンプルするサンプリング点間のリサンプル長を、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、予め決めた許容誤差を超えないように設定している。
【0018】
このように、許容誤差を予め定義し、それを超えないようにリサンプル長を決定しているので、リサンプル形状は、線形対象物に良く追従する。
他の観点から本発明を把握すると、本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、以下の(1)〜(4)のステップを含む。
【0019】
(1)線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップ。
(2)前記判定ステップの結果、線形対象物の形状が円弧の一部に近似すると判断された場合に、線形対象物の曲率半径を算出するステップ。
【0020】
(3)線形対象物の曲率半径ρが所定値以上又は所定値より大きい場合に、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、所定の許容誤差Emaxを超えないようにリサンプル長を設定するステップ。
【0021】
(4)線形対象物の曲率半径ρが所定値以下又は所定値より小さい場合に、線形対象物を曲率半径ρに対応した多角形で近似することでリサンプル長を設定するステップ。
また、本発明のリサンプル長決定方法では、前記(3)の場合に、
√(ρ2−(ρ−Emax)2)
を含む判定式の値に基づいてリサンプル長を決定するようにすることができる。
【0022】
この判定式を使うことで、許容誤差を超えないリサンプル長が決定できる。
また、本発明のリサンプル長決定方法では、前記(4)の場合に、曲率半径ρ、固定パラメータKrを用いたK・ρを含む判定式に基づいてサンプリング長を決定することができる。
【0023】
一方、前記(4)の場合に、ρが小さい程、Emaxも小さくなるように、Emaxをρに応じて変更するようにすることができる。
こうすることで、線形対象物がきつい小さなカーブを示している場合でも、リサンプル形状が元形状に対して大きく歪むことが無くなる。
【0024】
また、本発明のリサンプル長決定方法では、線形対象物の折曲部分が円弧の一部とみなせないとき、この折曲部分との誤差が許容誤差を超えない円の一部で折曲部分を近似した後、前記判定式の値を算出し、算出した値に基づいてリサンプル長を決定する。
【0025】
こうすることで、V字カーブの箇所でも、適切なリサンプル長が決定できる。
また、線状対象形状物の形状が、円弧の一部に近似しない折曲部分を含むと判断された場合に、折曲部分の前後は、偏角の大きさに応じて予め決めたリサンプル長を選出するようにしてもよい。
【0026】
また、線形対象物の形状が円弧の一部に近似するか否か判定するステップを、偏角の大きさ、又は偏角及びノード間の距離の関係を用いて行うようにしてもよい。
また、本発明の符号化データ生成方法では、線形対象物をリサンプルするサンプリング点間のリサンプル長を、前述するいずれかの方法で決定し、線形対象物を、決定したリサンプル長でリサンプルして複数のサンプリング点を設定し、各サンプリング点の位置データを、発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する。
【0027】
こうした方法で、データ量がそれ程多く無く、且つ、元形状に対して誤差が少ない、線形対象物を表す符号化データを得ることができる。
また、本発明には、線形形状をリサンプルするサンプリング点間のリサンプル長を前述するいずれかの方法で決定するリサンプル長決定部を備える装置が含まれる。
【0028】
また、本発明の符号化データ生成装置には、線形形状をリサンプルするサンプリング点間のリサンプル長を前述するいずれかの方法で決定するリサンプル長決定部と、リサンプル長決定部が決定したリサンプル長で線形形状をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部とを設けている。
【0029】
これらの装置では、前述するリサンプル長決定方法や符号化データ生成方法を実施することができる。
また、上述の構成を、プローブカーの走行軌跡を伝えるプローブカー車載機に適用することができる。
【0030】
更に本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムをも含む。当該プログラムは上述の(1)〜(4)のステップをコンピュータに実行させるものである。
【0031】
また、上述した線形対象物の符号化データ生成方法を用いて得られた符号化データを受信する受信部と、当該受信された符号化データを復元する復元部とを備える符号化データ復元装置も本発明に含まれる。
【0032】
本発明のリサンプル長決定方法では、データ量の増大を招くこと無く、元形状に対して誤差が少ないリサンプル形状を齎すリサンプル長を決定することができる。また、V字カーブの箇所にも、適切なリサンプル長を決定することができる。
【図面の簡単な説明】
【0033】
【図1】本発明の第1の実施形態におけるリサンプル長決定方法で着目する道路形状とリサンプル形状との誤差を説明する図である。
【図2】中心線リサンプルを説明する図である。
【図3】本発明の第1の実施形態におけるリサンプル長決定方法の手順を示すフロー図である。
【図4】道路リンクの長さ及び偏角を示す図である。
【図5】曲率の定義を説明する図である。
【図6】本発明の第1の実施形態におけるリサンプル長決定方法で決定したリサンプル長を対象道路の始端から距離で表した図である。
【図7】本発明の第1の実施形態におけるリサンプル長決定方法を実施する情報送信装置の構成を示すブロック図である。
【図8】本発明の第1の実施形態におけるリサンプル長決定方法を実施するプローブカー車載機の構成を示すブロック図である。
【図9】本発明の第2の実施形態におけるリサンプル長決定方法を説明する図である。
【図10】本発明の第2の実施形態におけるリサンプル長決定方法でのV字カーブを近似する円の設定の仕方を説明する図である。
【図11】本発明の第2の実施形態におけるリサンプル長決定方法の手順を示すフロー図である。
【図12】本発明の第2の実施形態におけるV字カーブ判定手順を示すフロー図である。
【図13】(a)はV字カーブ判定手順でV字カーブと判定されるリンク形状を示す図であり、図13(b)はV字カーブ判定手順で非V字カーブと判定されるリンク形状を示す図である。
【図14】デジタル地図上の道路の元形状が円弧に近似している場合のリサンプル長決定方法の適用例を示す図である。
【図15】単一変数値の統計的に偏りを持つ値への変換方法を説明する図である。
【図16】リサンプル長を違えて設定した道路区間を示す図である。
【図17】従来のリサンプル長決定方法の問題点を説明する図である。
【図18】道路形状とリサンプル形状との乖離を示す図である。
【図19】従来のリサンプル長決定方法が適用できないV字カーブを説明する図である。
【発明を実施するための最良の形態】
【0034】
(第1の実施形態)
本発明の第1の実施形態では、線形対象物である、デジタル地図上の道路の元形状が円弧に近似している場合のリサンプル長決定方法について説明する。言い換えると、道路の元形状が、所定の条件下において円弧の一部に近似する、又は円弧の一部とみなせる場合のリサンプル長決定方法について説明する。
【0035】
このリサンプル長決定方法では、サンプリング点を繋ぐ近似形状(リサンプル形状)と道路形状との間の許容誤差Emaxを予め定義する。そして、道路形状の曲率半径が所定値以上又は所定値より大であるとき(即ち、従来の方法を採ると、道路形状とリサンプル形状との誤差が許容誤差Emaxを超える虞があるとき)は、許容誤差Emaxを超えないように、事前に設定された複数の量子化リサンプル長の中から、使用するリサンプル長を決定する。また、道路形状の曲率半径が所定値より小さいまたは所定値以下のときは、従来と同様の方法でリサンプル長を決定する。
【0036】
なお、許容誤差Emaxの決め方の詳細は、特開2002−328033号公報に記載されている。例えば、次のような条件を満たすようにEmaxを設定する。
・対象道路区間の始点、終点近辺では、許容誤差を小さく設定する。
・並走道路が隣接する場合は、許容誤差を小さく設定する。
・インターチェンジ入出路などの交差角度の浅い接続道路が存在する交差点周辺では、許容誤差を小さく設定する。いま、図1に示すように、道路形状を曲率半径ρの真円にモデル化する。この真円上にリサンプル長をLとしてサンプリング点を設定したときのリサンプル形状と道路形状との最大誤差(直線近似誤差)Erは、次式(数2)により算出できる。
【0037】
Er=ρ−√(ρ2−(L/2)2) (数2)
この(数2)をLで展開すると、
L=2√(ρ2−(ρ−Er)2) (数3)
となる。そのため、道路形状とリサンプル形状との誤差が許容誤差Emaxを超えないようにするためには、リサンプル長Lは、次式(数4)の条件を満たせばよい。
【0038】
L≦2√(ρ2−(ρ−Emax)2) (数4)
ただし、ρ≧Emax,Emax>0
尚、この明細書では、「リサンプル形状と線形対象物の誤差」は、図1におけるErをさす。
【0039】
また、図2に示すように、サンプリング点を真円上からずらして設定し、サンプリング点間を繋ぐ直線の左右に真円の線分が同程度分布するようにリサンプルする(「中心線リサンプル」と言う)場合は、リサンプル形状と道路形状との間の誤差成分が、理想的にはリサンプル形状の左右に均等にバラけるので、中心線リサンプルでは、リサンプル長Lは、次式(数5)の条件を満たせばよいことになる。
【0040】
L≦2×2√(ρ2−(ρ−Emax)2) (数5)
ただし、ρ≧Emax,Emax>0
しかし、実際の道路形状の円弧は真円とは異なるため、安全率を見込んで、ρが所定値以上(概ねEmaxの2〜5倍)のときのリサンプル区間長判定値L0を次式(数6)のように設定する。
【0041】
L0=α×2√(ρ2−(ρ−Emax)2) (数6)
ただし、中心線リサンプルを行う場合は、α=1.2〜1.8
中心線リサンプルを行わない場合は、α=0.6〜0.9
そして、(数6)より算出したL0を基に量子化リサンプル長Lnを決定する。上述のリサンプル長の決定方法は、√(ρ2−(ρ−Emax)2)を含む判定式に基づいて行われるということができる。
【0042】
また、ρが前記所定値より小さい又は所定値以下のときは、上述の式によってL0を決定しても、元の形状からの歪み、乖離度合いは大きくなる。従ってこの場合、リサンプル区間長判定値L0を次式(数7)のように設定する。この設定は、形状を曲率半径に対応した多角形で近似することでリサンプル長を設定する。
【0043】
L0=Kr・p (数7)
ただし、Krは固定パラメータ
そして、(数7)より算出したL0を基に量子化リサンプル長Lnを決定する。上述のリサンプル長の決定方法は、Kr・ρを含む判定式に基づいて行われるということができる。
【0044】
これらのリサンプル区間長判定値L0に基づいて量子化リサンプル長Lnを決定することにより、道路形状がなだらかで大きなカーブを示している場合でも、リサンプル形状が道路形状から大きく外れることは無くなり、また、道路形状がきつい小さなカーブを示している場合でも、リサンプル形状が道路形状に対して大きく歪むことが無くなる。
【0045】
従って、受信側では、受信データを復号化して、リサンプル形状を的確に再現することができる。
なお、道路形状の曲率半径ρが所定値より小さい又は所定値以下の場合のリサンプル区間長判定値(数7)を設定する代わりに、許容誤差(Eo)を曲率半径ρの関数として設定し(ρが小さいときにEoも小さくなる)、ρの大きさに関わらず、(数6)のリサンプル区間長判定値を用いて、量子化リサンプル長Lnを決定するようにしても良い。
【0046】
この場合、許容誤差(Eo)を例えば次式(数8)(数9)のように設定する。
Eo=Emax (数8)
ただし、ρが所定値以上のとき(例えば、γ・ρ≧Emax)
Eo=γ・ρ (数9)
ここで、γは1以下の定数(概ね0.2〜0.5)とする。また、(数9)は、Eoがρの単調増加関数であれば、他のものでも良い。本方式は、曲率半径ρが小さい程、許容誤差Emaxも小さくなるように、許容誤差Emaxを曲率半径ρに応じて変更するものである。
【0047】
図3は、(数6)及び(数7)のリサンプル区間長判定値L0を用いて、実際にリサンプル長を設定する手順を示している。
まず、道路形状とリサンプル形状との間の最大許容誤差Emaxを決定する(ステップ1)。次に、デジタル地図データベースから対象道路の道路形状データを取得する(ステップ2)。道路形状データは、図4に示すように、ノード及びリンクのデータを含んでいる。n=2のリンクnから順に着目して(ステップ3)、リンクnの長さSn、及び、隣接リンク(n−1)との偏角θnを用いて、次式(数10)により曲率anを算出する(ステップ4)。
【0048】
an≒θn/Sn (数10)
なお、2次元曲線における曲率は、図5に示すように、曲線上でΔLだけ離れた2点P(L)、P(L+ΔL)での接線の間の角度をΔωとして、Δω/ΔLのΔL→0の極限値dω/dLとして定義され、その逆数ρが点Pでの曲率半径として定義される。(数10)は、ΔLを極限値ではない直線Snで近似し、さらにΔωをθnで近似したものであるが、ここでの目的がリサンプル区間長判定値を算出することであり、厳密性が要求されるものではないため、(数10)により曲率の近似値を算出しても実用上支障がない。
【0049】
次に、次式(数11)により曲率半径ρnを算出する(ステップ5)。
ρn≒1/an (数11)
曲率半径ρnが規定値以上か否かを識別し(ステップ6)、規定値以上であるときは、(数6)を用いて算出したリサンプル区間長判定値に基づいて、リンクnの量子化リサンプル長Lnを決定する(ステップ7)。また、曲率半径ρnが規定値より小さいときは、(数7)を用いて算出したリサンプル区間長判定値に基づいて、リンクnの量子化リサンプル長Lnを決定する(ステップ8)。
【0050】
なお、ステップ8では、Eo=γ・ρ(または、Eoはρの適切な単調増加関数)として、L0=α×2√(ρ2−(ρ−Eo)2)から算出したリサンプル区間長判定値L0に基づいて、リンクnの量子化リサンプル長Lnを決定しても良い。
【0051】
次のリンクに着目して(ステップ10)、ステップ4以降の手順を繰り返し、対象道路の全てのリンクについての処理が終了すると(ステップ9)、隣接リンク間で量子化リサンプル長が同じ場合にリンクを連結し、図6に示すように、対象道路全体のリサンプル長(L2、L4、・・・、L3)を始端からの距離で表現する(ステップ11)。次に、対象道路に対し、このリサンプル長を用いてリサンプル処理を行い、サンプリング点の位置情報を偏角または偏角予測差分値で表し、可変長符号化を行ってデータ圧縮する(ステップ12)。
【0052】
こうした処理により、データ量が少なく、道路の元形状と良く近似した道路位置を表す符号化データを得ることができる。
図7は、交通情報の対象道路を伝えるために、このリサンプル長決定方法を実行する情報送信装置(符号化データ生成装置)20と、提供された交通情報を活用する、車載用ナビゲーション装置やパーソナルコンピュータなどの情報活用装置(符号化データ復元装置)40との構成を示している。情報送信装置20は、渋滞情報や交通事故情報などが入力される事象情報入力部21と、デジタル地図データベースA22から交通情報の対象道路区間の道路形状データを抽出する形状データ抽出部23と、リサンプル形状と元形状データとの間の許容誤差を決定する許容誤差決定部24と、許容誤差に基づいてリサンプル長Lを決定するリサンプル長決定部25と、形状データ抽出部23で抽出された道路形状データをリサンプルしてサンプリング点の位置データ列を生成する形状データリサンプル処理部26と、形状データリサンプル処理部26が生成したデータを圧縮符号化する可変長符号化処理部28と、圧縮符号化された道路形状データを蓄積して外部メディアに蓄積データを提供する圧縮データ蓄積部27と、圧縮符号化された道路形状データを送信する形状データ送信部29とを備えている。
【0053】
一方、情報活用装置40は、提供された道路形状データを受信する形状データ受信部41と、圧縮符号化されているデータを復号する符号化データ復号部42と、リサンプル形状を復元する形状データ復元部43と、デジタル地図データベースB46のデータを用いてマップマッチングを行い、サンプリング点で表された道路区間をデジタル地図上で特定するマップマチング部45と、得られた交通情報を活用する情報活用部44とを備えている。
【0054】
情報送信装置20では、リサンプル長決定部25が、許容誤差決定部24で決定された許容誤差に基づいて、リサンプルにおけるリサンプル長Lを決定する。形状データリサンプル処理部26は、決定されたリサンプル長Lを用いて、形状データ抽出部23が抽出した対象道路の道路形状データをリサンプルする。
【0055】
可変長符号化処理部28は、この道路形状データを可変長符号化する。可変長符号化によりデータ圧縮された道路形状データは、外部メディアに記録されて提供され、あるいは、形状データ送信部29から送信される。
【0056】
この道路形状データを受信した情報活用装置40では、符号化データ復号部42が、圧縮符号化されているデータを復号化し、形状データ復元部43が、サンプリング点の位置情報を復元して、サンプリング点を繋いだリサンプル形状を再現する。このリサンプル形状は、情報活用装置40の表示画面上にデジタル地図と重ねて表示される。
【0057】
また、伝えられた道路区間を正確に特定するために、マップマッチング部45は、サンプリング点の位置データとデジタル地図データベースB46の地図データとのマップマッチングを行い、デジタル地図データベースB46の地図データ上で対象道路を特定する。
【0058】
情報活用部44は、得られた交通情報を、画面に表示したり、経路探索に利用したりして活用する。情報活用装置40は、カーナビ受信機または地図表示端末をも構成し得る。
また、図8は、走行軌跡を伝えるために、このリサンプル長決定方法を実行するプローブカー車載機(符号化データ生成装置)60と、プローブ情報を収集するプローブ情報収集センタ(符号化データ復元装置)50との構成を示している。プローブカー車載機60は、GPSアンテナ73から受信する情報やジャイロ74の検知情報を基に自車位置を判定する自車位置判定部61と、速度を検出するセンサ70と、ハンドル舵角を検出するセンサ71と、横方向の加速度(横G)を検出するセンサ72と、デジタル地図のデータベース69と、リサンプル形状と道路形状との間の許容誤差を決定する許容誤差決定部67と、リサンプルに用いるリサンプル長Lを決定するリサンプル長決定部68と、自車の走行軌跡を蓄積する走行軌跡蓄積部62と、走行軌跡をリサンプルしてサンプリング点の位置データ列を生成する走行軌跡形状リサンプル処理部63と、走行軌跡形状リサンプル処理部63が生成したデータを圧縮符号化する可変長符号化処理部64と、圧縮符号化された走行軌跡形状データを蓄積する圧縮データ蓄積部65と、圧縮符号化された走行軌跡形状データを送信する走行軌跡送信部66とを備えている。
【0059】
一方、プローブ情報収集センタ50は、プローブカー車載機60から提供された走行軌跡形状データを受信する走行軌跡受信部51と、圧縮符号化されている受信データを復号化する符号化データ復号部52と、復号化されたデータから走行軌跡形状を復元する走行軌跡形状復元部53と、プローブカー車載機60から収集した走行軌跡や計測情報を交通情報の生成に活用する走行軌跡計測情報活用部54とを備えている。
【0060】
プローブカー車載機60の走行軌跡蓄積部62には、自車位置判定部61で検出された自車位置が走行軌跡として順次蓄積される。リサンプル長決定部68は、センサ70、71、72で検知された速度、ハンドル舵角、横Gの情報や、デジタル地図データベース69から取得した道路形状から、走行軌跡の曲率の大小を判定し、その曲率の大きさや、許容誤差決定部67で決定された許容誤差に基づいて、リサンプルに使用するリサンプル長Lを決定する。
【0061】
走行軌跡形状リサンプル処理部63は、プローブ情報の送信時期に、走行軌跡蓄積部62に蓄積された走行軌跡データを読み出し、リサンプル長決定部68が決定したリサンプル長を用いて走行軌跡形状をリサンプルする。
【0062】
可変長符号化処理部64は、このデータを可変長符号化して圧縮する。圧縮符号化されたデータは、プローブ情報収集センタ50に送信される。また、このデータは、外部メディアに格納してプローブ情報収集センタ50に提供される場合もある。
【0063】
プローブ情報収集センタ50では、符号化データ復号部52が、プローブカー車載機60から収集したデータを復号化し、走行軌跡形状復元部53が、サンプリング点の位置情報を復元して、走行軌跡のリサンプル形状を再現する。この走行軌跡の情報は、プローブカー車載機60で計測された速度等の計測情報と併せて交通情報の生成に活用される。
【0064】
このように、情報送信装置やプローブカー車載機が、本発明のリサンプル長決定方法を用いて、対象道路や走行軌跡の符号化を行うことにより、この符号化データを受信する情報活用装置やプローブ情報収集センタでは、受信データを復号化して、リサンプル形状を的確に再現することができる。
【0065】
(第2の実施形態)
本発明の第2の実施形態では、道路形状が円弧の一部とみなせないときの例として、V字カーブでのリサンプル長の決定方法について説明する。
【0066】
V字カーブでは、図9に示すように、V字カーブ部分を、それに接する円で近似してリサンプルを行う。円の大きさは、図10に示すように、V字カーブと円との間の最大誤差が、予め設定した許容誤差Emax2を超えないように設定する。
【0067】
円の半径をR、円とV字カーブとの接点P1、P2からV字カーブの交点Pまでの距離をDとすると、
ω=(180−θ)/2
(R+Emax2)2=D2+R2
D・tanω=R
の関係が成立するので、これらの式から、Dは(数12)として、また、Rは(数13)として算出することができる。
【0068】
D=Emax2・[tanω+√{(tanω)2+1}] (数12)
R=D/tanω
=Emax2・[1+(√{(tanω)2+1})/tanω] (数13)
そして、V字カーブをリサンプルする場合は、点Pから距離Dだけ離れた直線上にノードP1、P2を追加し、P1→P→P2間は曲率半径Rの円と見立てて、Rで決定されるリサンプル長Lによってリサンプルを行う。
【0069】
図11のフロー図は、V字カーブでのリサンプル処理手順を示している。
まず、V字カーブの最大許容誤差Emax2を決定する(ステップ21)。次に、デジタル地図データベースから対象道路の道路形状データを取得する(ステップ22)。n=2のリンクnから順に着目して(ステップ23)、リンクn及び隣接リンク(n−1)の情報を取得し(ステップ24)、リンクnと隣接リンク(n−1)とがV字カーブであるか否か判定する(ステップ25)。
【0070】
この判定は、図12に示す手順で行う。即ち、リンク(n−1)とリンクnとの間の偏角θn、及び、リンクnの長さSnを算出し(ステップ41)、θn及びSnを用いて(数10)(数11)により曲率半径ρnを算出する(ステップ42)。
【0071】
次に、定数κを用いて、Sn≦κ・ρnの条件式を満たすかどうかを判定する(ステップ43)。図13(a)に示すように、Snが長いときは、この条件式を満たさない。この場合は、リンク(n−1)→リンクn間が円弧近似の無理なV字カーブと判定する(ステップ45)。また、図13(b)に示すように、Snが短いときは、この条件式を満たす。この場合は、リンク(n−1)→リンクn間が円弧近似の可能な通常のカーブと判定する(ステップ44)。κ=1のとき、Snが、曲率半径ρnの円弧を正六角形以上の角数で近似していれば条件式を満たすことになる。
【0072】
リンク(n−1)→リンクn間がV字カーブである場合は、Emax2の値を基に、(数12)(数13)を用いてD及びRを算出し(ステップ27)、リンク(n−1)とリンクnとの接続点Pから距離Dだけ離れたリンク上にノードP1、P2を追加し、P1→P→P2間の曲率半径をRとする(ステップ27)。
【0073】
そして、第1の実施形態で説明したリサンプル長決定方法を用いて量子化リサンプル長Lnを決定する(ステップ28)。また、ステップ25において、リンク(n−1)→リンクn間がV字カーブで無い場合は、直ぐにステップ28の処理を行う。
【0074】
こうした処理を全てのリンクについて行い、全てのリンクに対する処理が終了すると、第1の実施形態と同様に、隣接リンク間で量子化リサンプル長が同じ場合にリンクを連結し、対象道路全体のリサンプル長を始端からの距離で表現し(ステップ31)、対象道路へのリサンプル処理及び可変長符号化処理を行う(ステップ32)。
【0075】
こうした処理により、V字カーブに対しても適切なリサンプル長を設定することができる。
また、道路形状が、V時カーブの如き円弧の一部に近似しない折曲部分を含む場合、折曲部分の前後は、偏角の大きさに応じて予めリサンプル長を選出するよう設定しておいてもよい。例えば、偏角が26度以上で40度より小さい場合は、リサンプル長は50m、40度以上で60度より小さい場合は30m、60度以上の場合は15m、のように偏角に応じてリサンプル長を設定しておいてもよい。偏角が26度より小さい場合は、第1の実施形態で述べたリサンプル長の決定方法が用いられる。
【0076】
また、道路形状が円弧の一部に近似するか否か判定するに際し、当該道路に予め設定されているノード毎の偏角の大きさ、又は当該偏角の大きさ及びノード間の距離の関係を用いることができる。
【0077】
図14はデジタル地図上の道路の元形状が円弧に近似している場合において、元のデジタル地図の道路上にノードが設定されている状態を示す図である。
上述の通り、円弧とみなせるかみなせないかは、偏角の大きさとノード間距離によって判別することできる。
【0078】
偏角θとノード間距離Lから曲率半径ρを算出し、L<2√(ρ2−(ρ−E)2)ならば、元の対象道路は、交差点やV字カーブではなくスムーズなカーブであったと判別できる。ここで、Eにはデジタル化の入力誤差±5m程度(元の地図をデジタル化した際における標準的な誤差)が入る。
【0079】
図14の内側の円の場合、曲率半径は130mであり、最も長いと思われる線分(ノード間距離)の長さは66mである。地図データのデジタル化の入力誤差E=5mとすると、2√(ρ2−(ρ−E)2)=71mとなる。
【0080】
他のノード間距離はこれより小さいので、よって、この計算方法でほぼ正しいといえる。
また、計算を略して偏角のみでもおおむね判別することもできる。なだらかなカーブをデジタル化したような箇所であれば、偏角は小さいからである。
【0081】
また、図8では、プローブカー車載機60とプローブ情報収集センタ50の組み合わせより、プローブカーシステムが構築され、両者間でプローブカーシステムの情報伝達方法が達成されるが、当該方法は、本発明のリサンプル長決定方法、符号化データ生成方法及び当該符号化データの復号化方法の組み合わせより達成される。
【0082】
更に本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムをも含む。当該プログラムは、線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定する手順と、判定手順の結果、線形対象物の形状が円弧の一部に近似すると判断された場合に、線形対象物の曲率半径を算出する手順と、線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定する手順と、線形対象物の曲率半径が所定値以下又は所定値より小さい場合に、線形対象物を曲率半径に対応した多角形で近似する手順と、をコンピュータに実行させる。
【0083】
このようなプログラムは、情報送信装置20、プローブカー車載機60に、種々の形式で組み込まれる。例えば情報送信装置20、プローブカー車載機60内又はこれらの外部の装置内の所定のメモリにプログラムを記録することができる。また、ハードディスクのような情報記録装置や、CD−ROMやDVD−ROM、メモリカードのような情報記録媒体にプログラムを記録してもよい。また、ネットワーク経由により当該プログラムをダウンロードするようにしてもよい。
【0084】
また、本発明の情報送信装置20と情報活用装置40又はプローブカー車載機60とプローブ情報収集センタ50の組み合わせより、地図データ配信システムが構成される。情報送信装置20とプローブカー車載機60は、符号化データを生成するという観点からエンコーダとして機能し、情報活用装置40とプローブ情報収集センタ50は、符号化データを復元するという観点からデコーダとして機能する。
【0085】
また、符号化データ生成装置である情報送信装置20又はプローブカー車載機60は、情報送信側における実施の形態の例であり、情報を送信する事が出来る装置や端末であればどのような形態のものでもよい。さらに生成した符号化データを媒体に記録して、他の装置に提供することも可能である。また、符号化データ復元装置である情報活用装置40又はプローブ情報収集センタ50も情報受信側における実施の形態の例であり、パーソナルコンピュータ、携帯端末等の情報を活用できる装置であればなんでもよい。もちろん、符号化データの復元が可能な情報収集センターや、センター側の装置でも同様の効果を得ることが出来る。さらに符号化されたデータが記録された媒体等を用いて、復元処理することにより、同様の効果を得ることは言うまでもない。
【0086】
また、本発明の符号化データ生成方法に沿ったアルゴリズム(プログラム)を、地図データ本体に各種地図情報に対応した地図データが記録された記録媒体に記録することができる。これにより、地図データ本体自体を圧縮符号化することが可能となる。
【0087】
尚、上述の実施形態においては、線形対象物が位置参照用の道路形状である例を説明したが、線形対象物は道路形状に限られない。「線形対象物」とは直線、曲線など種々の形態を含む細長い形状のものを総て含み、地図上の線形形状によって表わせる地理情報総てを含み得る。更に、指紋等地図とは関係ないが、線形形状によって表わされるもの総てをも含まれる。
【0088】
本発明を詳細にまた特定の実施態様を参照して説明したが、本発明の精神と範囲を逸脱することなく様々な変更や修正を加えることができることは当業者にとって明らかである。
【0089】
本出願は、2003年10月21日出願の日本特許出願(特願2003−360631)に基づくものであり、その内容はここに参照として取り込まれる。
【産業上の利用可能性】
【0090】
本発明のリサンプル長決定方法及び符号化データ生成方法は、デジタル地図の道路形状や河川、鉄道線路、行政境界線、等高線などの位置情報を表す符号化データを生成・蓄積・保存するときなどに利用することができ、また、デジタル地図以外にも、各種の図形や指紋などの形状を表す符号化データを生成・蓄積・保存するときなどに適用することができる。また、本発明の装置は、その符号化データの生成・蓄積・保存を実行する各種装置に適用することができる。
【技術分野】
【0001】
本発明は、道路位置等を表す符号化データを生成するため、デジタル地図の道路等の形状に沿って複数のサンプリング点を設定する場合のサンプリング点間隔(リサンプル長)の決定方法と、それを用いた符号化データ生成方法と、それらの方法を実施する装置に関し、元形状との誤差が少なく、且つ、符号化データのデータ量を増やさないようなリサンプル長の決め方を提案するものである。
【背景技術】
【0002】
従来から、VICS(道路交通情報通信システム)では、デジタル地図データベースを搭載する車両用ナビゲーション装置に対して、FM多重放送やビーコンを通じて、渋滞区間や旅行時間を示す道路交通情報の提供サービスを実施している。車両用ナビゲーション装置は、この道路交通情報を受信して、画面表示する地図に渋滞区間を色付けして表したり、目的地までの所用時間を算出して表示したりしている。
【0003】
このように、道路交通情報を提供する場合には、デジタル地図上の道路の位置情報を伝えることが必要になる。また、現在地及び目的地の情報を受信して、最短時間で目的地まで到達できる推奨経路の情報を提供するサービスや、近年、研究が進められている、走行中の車両(プローブカー)から軌跡情報及び速度情報等を収集する道路交通情報収集システム(プローブ情報収集システム)においても、デジタル地図上の推奨経路や走行軌跡を相手方に正しく伝えることが必要である。
【0004】
これまで、デジタル地図上の道路位置を伝える場合には、一般的に、道路に付されたリンク番号や、交差点などのノードを特定するノード番号が使用されている。しかし、道路網に定義したノード番号やリンク番号は、道路の新設や変更に伴って新しい番号に付け替える必要があり、それに応じて、各社で制作されるデジタル地図データも更新しなければならないため、ノード番号やリンク番号を用いる方式は、メンテナンスに多大な社会的コストが掛かることになる。
【0005】
こうした点を改善するため、特開2003−23357号公報では、ノード番号やリンク番号を用いずに、且つ、少ないデータ量でデジタル地図上の道路位置を伝える方法を提案している。
【0006】
この方法では、伝えようとするデジタル地図上の道路区間に一定距離間隔でサンプリング点を再設定し(これを「等距離リサンプル」と言う)、各サンプリング点の位置データを順番に並べたデータ列に対して圧縮符号化の処理を施し、圧縮符号化したデータを送信する。これを受信した受信側は、サンプリング点の位置データのデータ列を復元し、自己のデジタル地図上に道路形状を再現する。また、必要に応じて、この位置データを使用して、自己のデジタル地図上で位置特定、位置参照を実施し(マップマッチング)道路区間を特定する。
【0007】
位置データのデータ列に対する圧縮符号化は、次に示すように、(1)位置データの単一変数への変換、(2)単一変数で表わした値の統計的に偏りを持つ値への変換、(3)変換した値の可変長符号化、の順に行われる。
(1)位置データの単一変数への変換
図15(a)には、等距離リサンプルで設定した道路区間上のサンプリング点をPJ−1、PJで表している。このサンプリング点(PJ)は、隣接するサンプリング点(PJ−1)からの距離(リサンプル長)Lと角度Θとの2つのディメンジョンで一意に特定することができ、距離を一定(L)とすると、サンプリング点(PJ)は、隣接サンプリング点(PJ−1)からの角度成分Θのみの単一変数で表現することができる。図15(a)では、この角度Θとして、真北(図の上方)の方位を0度とし、時計回りに0〜360度の範囲で大きさを指定する「絶対方位」による角度Θを示している(真北からの絶対方位)。道路区間は、サンプリング点間の一定距離し、及び、始端または終端となるサンプリング点(基準点)の緯度・経度を別に示すことにより、各サンプリング点の角度成分のデータ列により表わすことができる。
(2)単一変数値の統計的に偏りを持つ値への変換
各サンプリング点の単一変数値が、可変長符号化に適した、統計的に偏在する値となるように、図15(b)に示すように、各サンプリング点の角度成分を、隣接するサンプリング点の角度成分との変位差、即ち、「偏角」θjによって表現する。この偏角θjは、
θj=Θj−Θj−1
として算出される。道路が直線的である場合に、各サンプリング点の偏角θは0付近に集中し、統計的に偏りを持つデータとなる。
【0008】
また、サンプリング点の角度成分は、図15(c)に示すように、着目するサンプリング点PJの偏角θjを、それ以前のサンプリング点PJ−1、PJ−2、・・の偏角θj−1、θj−2、・・を用いて予測した当該サンプリング点PJの偏角予測値Sj(統計予測値)との差分値(偏角予測差分値又は偏角予測誤差)Δθjで表わすことにより、統計的に偏りを持つデータに変換する
ことができる。統計予測値Sjは、例えば、
Sj=θj−1
と定義したり、
Sj=(θj−1+θj−2)/2
と定義したりすることができる。偏角予測差分値Δθjは、
Δθj=θj−Sj
として算出される。道路が一定の曲率で湾曲している場合には、各サンプリング点の偏角予測差分値Δθは0付近に集中し、統計的に偏りを持つデータとなる。
【0009】
図15(d)は、直線的な道路区間を偏角θで表示した場合、及び、曲線的な道路区間を偏角予測差分値Δθで表示した場合のデータの発生頻度をグラフ化して示している。θ及びΔθの発生頻度はθ(又はΔθ)=0°に極大が現れ、統計的に偏りを持っている。
(3)可変長符号化
次に、統計的に偏りを持つ値に変換したデータ列の値を可変長符号化する。可変長符号化方法には、固定数値圧縮法(0圧縮等)、シャノン・ファノ符号法、ハフマン符号法、算術符号法、辞書法など多種存在し、いずれの方法を用いてもよい。最も一般的なハフマン符号法を用いる場合では、発生頻度が高いデータに少ないビット数の符号を定義し、発生頻度が低いデータに多いビット数の符号を定義した符号表を用いて、統計的に偏りを持たせたデータ列の値を符号化し、トータルのデータ量を削減する。
【0010】
また、特開2003−23357号公報では、図16に示すように、道路形状の曲率が大きい区間Bでは、等距離リサンプルの距離L2を短く設定し、曲率が小さい、直線的な道路区間Aでは、等距離リサンプルの距離L1を長く設定することを提案している。これは、曲率が大きく、カーブがきつい道路を長い距離でリサンプルすると、特徴的な道路形状を示す位置にサンプリング点を配置することができなくなり、受信側での道路形状の再現性が悪くなり、また、誤マッチングが発生する可能性が高くなるためである。
【0011】
具体的な方法として、各区間jのリサンプル長Ljが取り得る値(量子化リサンプル長)を、例えば、40/80/160/320/640/1280/2560/5120メートルのように予め設定し、区間jの曲率半径ρjを用いて、次式(数1)によりLjを求め、この値に最も近い量子化リサンプル長をリサンプル長Ljとして決定するリサンプル長決定方法が開示されている。
【0012】
Lj=ρj・Kr (Krは固定パラメータ) (数1)
しかし、(数1)を用いるリサンプル長決定方法は、図17に示すように、真円を近似する多角形の辺の長さを求めていることに等しく、真円を近似する多角形の辺数(角数)自体は、曲率半径の大小に関わらず一定である。そのため、図17(a)のように、曲率半径が小さいとき(円が小さいとき)は、円と多角形との間の最大誤差も小さいが、図17(b)に示すように、曲率半径が大きいと、円と多角形との間の最大誤差、即ち、元形状とサンプリング点を繋ぐ近似形状(リサンプル形状)との間の最大誤差が大きくなる、と言う問題点がある。
【0013】
図18には、従来の方法で決定したリサンプル長により道路形状をリサンプルして符号化データを生成した後、この符号化データから再現したリサンプル形状を示している。なだらかに曲がる高速道路のカーブに対して、再現したリサンプル形状の追従性は、良くないことが見て取れる。
【0014】
リサンプル形状の追従性は、(数1)のKrを小さく設定することで改善できるが、その場合は、真円を近似する多角形の辺数(角数)を増やすことに相当し、曲率半径が小さい道路形状に対して、必要以上に細かなリサンプル長を選定することになり、符号化データの圧縮率が落ちるという問題点が生じる。
【0015】
また、図19の(a)、(b)、(c)に示すように、道路が直線的に交差する曲がり角(以下、交差角度の如何に関わらす「V字カーブ」と呼ぶことにする)は、円弧の一部と見なして曲率半径を算出するには無理がある。そのため、従来のリサンプル長決定方法では、V字カーブを示す元形状に対して適切なリサンプル長を設定することができない、と言う問題点がある。
【0016】
本発明は、こうした従来の問題点を解決するものであり、符号化データのデータ量の増大を招かずに、元形状に対する誤差が少ないリサンプル形状を得ることができるリサンプル長の決定方法を提供し、また、それを用いた符号化データ生成方法、及び、それらの方法を実施する装置を提供することを目的としている。
【特許文献1】特開2003−23357号
【発明の開示】
【0017】
本発明のリサンプル長決定方法では、線形対象物をリサンプルするサンプリング点間のリサンプル長を、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、予め決めた許容誤差を超えないように設定している。
【0018】
このように、許容誤差を予め定義し、それを超えないようにリサンプル長を決定しているので、リサンプル形状は、線形対象物に良く追従する。
他の観点から本発明を把握すると、本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、以下の(1)〜(4)のステップを含む。
【0019】
(1)線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップ。
(2)前記判定ステップの結果、線形対象物の形状が円弧の一部に近似すると判断された場合に、線形対象物の曲率半径を算出するステップ。
【0020】
(3)線形対象物の曲率半径ρが所定値以上又は所定値より大きい場合に、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、所定の許容誤差Emaxを超えないようにリサンプル長を設定するステップ。
【0021】
(4)線形対象物の曲率半径ρが所定値以下又は所定値より小さい場合に、線形対象物を曲率半径ρに対応した多角形で近似することでリサンプル長を設定するステップ。
また、本発明のリサンプル長決定方法では、前記(3)の場合に、
√(ρ2−(ρ−Emax)2)
を含む判定式の値に基づいてリサンプル長を決定するようにすることができる。
【0022】
この判定式を使うことで、許容誤差を超えないリサンプル長が決定できる。
また、本発明のリサンプル長決定方法では、前記(4)の場合に、曲率半径ρ、固定パラメータKrを用いたK・ρを含む判定式に基づいてサンプリング長を決定することができる。
【0023】
一方、前記(4)の場合に、ρが小さい程、Emaxも小さくなるように、Emaxをρに応じて変更するようにすることができる。
こうすることで、線形対象物がきつい小さなカーブを示している場合でも、リサンプル形状が元形状に対して大きく歪むことが無くなる。
【0024】
また、本発明のリサンプル長決定方法では、線形対象物の折曲部分が円弧の一部とみなせないとき、この折曲部分との誤差が許容誤差を超えない円の一部で折曲部分を近似した後、前記判定式の値を算出し、算出した値に基づいてリサンプル長を決定する。
【0025】
こうすることで、V字カーブの箇所でも、適切なリサンプル長が決定できる。
また、線状対象形状物の形状が、円弧の一部に近似しない折曲部分を含むと判断された場合に、折曲部分の前後は、偏角の大きさに応じて予め決めたリサンプル長を選出するようにしてもよい。
【0026】
また、線形対象物の形状が円弧の一部に近似するか否か判定するステップを、偏角の大きさ、又は偏角及びノード間の距離の関係を用いて行うようにしてもよい。
また、本発明の符号化データ生成方法では、線形対象物をリサンプルするサンプリング点間のリサンプル長を、前述するいずれかの方法で決定し、線形対象物を、決定したリサンプル長でリサンプルして複数のサンプリング点を設定し、各サンプリング点の位置データを、発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する。
【0027】
こうした方法で、データ量がそれ程多く無く、且つ、元形状に対して誤差が少ない、線形対象物を表す符号化データを得ることができる。
また、本発明には、線形形状をリサンプルするサンプリング点間のリサンプル長を前述するいずれかの方法で決定するリサンプル長決定部を備える装置が含まれる。
【0028】
また、本発明の符号化データ生成装置には、線形形状をリサンプルするサンプリング点間のリサンプル長を前述するいずれかの方法で決定するリサンプル長決定部と、リサンプル長決定部が決定したリサンプル長で線形形状をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部とを設けている。
【0029】
これらの装置では、前述するリサンプル長決定方法や符号化データ生成方法を実施することができる。
また、上述の構成を、プローブカーの走行軌跡を伝えるプローブカー車載機に適用することができる。
【0030】
更に本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムをも含む。当該プログラムは上述の(1)〜(4)のステップをコンピュータに実行させるものである。
【0031】
また、上述した線形対象物の符号化データ生成方法を用いて得られた符号化データを受信する受信部と、当該受信された符号化データを復元する復元部とを備える符号化データ復元装置も本発明に含まれる。
【0032】
本発明のリサンプル長決定方法では、データ量の増大を招くこと無く、元形状に対して誤差が少ないリサンプル形状を齎すリサンプル長を決定することができる。また、V字カーブの箇所にも、適切なリサンプル長を決定することができる。
【図面の簡単な説明】
【0033】
【図1】本発明の第1の実施形態におけるリサンプル長決定方法で着目する道路形状とリサンプル形状との誤差を説明する図である。
【図2】中心線リサンプルを説明する図である。
【図3】本発明の第1の実施形態におけるリサンプル長決定方法の手順を示すフロー図である。
【図4】道路リンクの長さ及び偏角を示す図である。
【図5】曲率の定義を説明する図である。
【図6】本発明の第1の実施形態におけるリサンプル長決定方法で決定したリサンプル長を対象道路の始端から距離で表した図である。
【図7】本発明の第1の実施形態におけるリサンプル長決定方法を実施する情報送信装置の構成を示すブロック図である。
【図8】本発明の第1の実施形態におけるリサンプル長決定方法を実施するプローブカー車載機の構成を示すブロック図である。
【図9】本発明の第2の実施形態におけるリサンプル長決定方法を説明する図である。
【図10】本発明の第2の実施形態におけるリサンプル長決定方法でのV字カーブを近似する円の設定の仕方を説明する図である。
【図11】本発明の第2の実施形態におけるリサンプル長決定方法の手順を示すフロー図である。
【図12】本発明の第2の実施形態におけるV字カーブ判定手順を示すフロー図である。
【図13】(a)はV字カーブ判定手順でV字カーブと判定されるリンク形状を示す図であり、図13(b)はV字カーブ判定手順で非V字カーブと判定されるリンク形状を示す図である。
【図14】デジタル地図上の道路の元形状が円弧に近似している場合のリサンプル長決定方法の適用例を示す図である。
【図15】単一変数値の統計的に偏りを持つ値への変換方法を説明する図である。
【図16】リサンプル長を違えて設定した道路区間を示す図である。
【図17】従来のリサンプル長決定方法の問題点を説明する図である。
【図18】道路形状とリサンプル形状との乖離を示す図である。
【図19】従来のリサンプル長決定方法が適用できないV字カーブを説明する図である。
【発明を実施するための最良の形態】
【0034】
(第1の実施形態)
本発明の第1の実施形態では、線形対象物である、デジタル地図上の道路の元形状が円弧に近似している場合のリサンプル長決定方法について説明する。言い換えると、道路の元形状が、所定の条件下において円弧の一部に近似する、又は円弧の一部とみなせる場合のリサンプル長決定方法について説明する。
【0035】
このリサンプル長決定方法では、サンプリング点を繋ぐ近似形状(リサンプル形状)と道路形状との間の許容誤差Emaxを予め定義する。そして、道路形状の曲率半径が所定値以上又は所定値より大であるとき(即ち、従来の方法を採ると、道路形状とリサンプル形状との誤差が許容誤差Emaxを超える虞があるとき)は、許容誤差Emaxを超えないように、事前に設定された複数の量子化リサンプル長の中から、使用するリサンプル長を決定する。また、道路形状の曲率半径が所定値より小さいまたは所定値以下のときは、従来と同様の方法でリサンプル長を決定する。
【0036】
なお、許容誤差Emaxの決め方の詳細は、特開2002−328033号公報に記載されている。例えば、次のような条件を満たすようにEmaxを設定する。
・対象道路区間の始点、終点近辺では、許容誤差を小さく設定する。
・並走道路が隣接する場合は、許容誤差を小さく設定する。
・インターチェンジ入出路などの交差角度の浅い接続道路が存在する交差点周辺では、許容誤差を小さく設定する。いま、図1に示すように、道路形状を曲率半径ρの真円にモデル化する。この真円上にリサンプル長をLとしてサンプリング点を設定したときのリサンプル形状と道路形状との最大誤差(直線近似誤差)Erは、次式(数2)により算出できる。
【0037】
Er=ρ−√(ρ2−(L/2)2) (数2)
この(数2)をLで展開すると、
L=2√(ρ2−(ρ−Er)2) (数3)
となる。そのため、道路形状とリサンプル形状との誤差が許容誤差Emaxを超えないようにするためには、リサンプル長Lは、次式(数4)の条件を満たせばよい。
【0038】
L≦2√(ρ2−(ρ−Emax)2) (数4)
ただし、ρ≧Emax,Emax>0
尚、この明細書では、「リサンプル形状と線形対象物の誤差」は、図1におけるErをさす。
【0039】
また、図2に示すように、サンプリング点を真円上からずらして設定し、サンプリング点間を繋ぐ直線の左右に真円の線分が同程度分布するようにリサンプルする(「中心線リサンプル」と言う)場合は、リサンプル形状と道路形状との間の誤差成分が、理想的にはリサンプル形状の左右に均等にバラけるので、中心線リサンプルでは、リサンプル長Lは、次式(数5)の条件を満たせばよいことになる。
【0040】
L≦2×2√(ρ2−(ρ−Emax)2) (数5)
ただし、ρ≧Emax,Emax>0
しかし、実際の道路形状の円弧は真円とは異なるため、安全率を見込んで、ρが所定値以上(概ねEmaxの2〜5倍)のときのリサンプル区間長判定値L0を次式(数6)のように設定する。
【0041】
L0=α×2√(ρ2−(ρ−Emax)2) (数6)
ただし、中心線リサンプルを行う場合は、α=1.2〜1.8
中心線リサンプルを行わない場合は、α=0.6〜0.9
そして、(数6)より算出したL0を基に量子化リサンプル長Lnを決定する。上述のリサンプル長の決定方法は、√(ρ2−(ρ−Emax)2)を含む判定式に基づいて行われるということができる。
【0042】
また、ρが前記所定値より小さい又は所定値以下のときは、上述の式によってL0を決定しても、元の形状からの歪み、乖離度合いは大きくなる。従ってこの場合、リサンプル区間長判定値L0を次式(数7)のように設定する。この設定は、形状を曲率半径に対応した多角形で近似することでリサンプル長を設定する。
【0043】
L0=Kr・p (数7)
ただし、Krは固定パラメータ
そして、(数7)より算出したL0を基に量子化リサンプル長Lnを決定する。上述のリサンプル長の決定方法は、Kr・ρを含む判定式に基づいて行われるということができる。
【0044】
これらのリサンプル区間長判定値L0に基づいて量子化リサンプル長Lnを決定することにより、道路形状がなだらかで大きなカーブを示している場合でも、リサンプル形状が道路形状から大きく外れることは無くなり、また、道路形状がきつい小さなカーブを示している場合でも、リサンプル形状が道路形状に対して大きく歪むことが無くなる。
【0045】
従って、受信側では、受信データを復号化して、リサンプル形状を的確に再現することができる。
なお、道路形状の曲率半径ρが所定値より小さい又は所定値以下の場合のリサンプル区間長判定値(数7)を設定する代わりに、許容誤差(Eo)を曲率半径ρの関数として設定し(ρが小さいときにEoも小さくなる)、ρの大きさに関わらず、(数6)のリサンプル区間長判定値を用いて、量子化リサンプル長Lnを決定するようにしても良い。
【0046】
この場合、許容誤差(Eo)を例えば次式(数8)(数9)のように設定する。
Eo=Emax (数8)
ただし、ρが所定値以上のとき(例えば、γ・ρ≧Emax)
Eo=γ・ρ (数9)
ここで、γは1以下の定数(概ね0.2〜0.5)とする。また、(数9)は、Eoがρの単調増加関数であれば、他のものでも良い。本方式は、曲率半径ρが小さい程、許容誤差Emaxも小さくなるように、許容誤差Emaxを曲率半径ρに応じて変更するものである。
【0047】
図3は、(数6)及び(数7)のリサンプル区間長判定値L0を用いて、実際にリサンプル長を設定する手順を示している。
まず、道路形状とリサンプル形状との間の最大許容誤差Emaxを決定する(ステップ1)。次に、デジタル地図データベースから対象道路の道路形状データを取得する(ステップ2)。道路形状データは、図4に示すように、ノード及びリンクのデータを含んでいる。n=2のリンクnから順に着目して(ステップ3)、リンクnの長さSn、及び、隣接リンク(n−1)との偏角θnを用いて、次式(数10)により曲率anを算出する(ステップ4)。
【0048】
an≒θn/Sn (数10)
なお、2次元曲線における曲率は、図5に示すように、曲線上でΔLだけ離れた2点P(L)、P(L+ΔL)での接線の間の角度をΔωとして、Δω/ΔLのΔL→0の極限値dω/dLとして定義され、その逆数ρが点Pでの曲率半径として定義される。(数10)は、ΔLを極限値ではない直線Snで近似し、さらにΔωをθnで近似したものであるが、ここでの目的がリサンプル区間長判定値を算出することであり、厳密性が要求されるものではないため、(数10)により曲率の近似値を算出しても実用上支障がない。
【0049】
次に、次式(数11)により曲率半径ρnを算出する(ステップ5)。
ρn≒1/an (数11)
曲率半径ρnが規定値以上か否かを識別し(ステップ6)、規定値以上であるときは、(数6)を用いて算出したリサンプル区間長判定値に基づいて、リンクnの量子化リサンプル長Lnを決定する(ステップ7)。また、曲率半径ρnが規定値より小さいときは、(数7)を用いて算出したリサンプル区間長判定値に基づいて、リンクnの量子化リサンプル長Lnを決定する(ステップ8)。
【0050】
なお、ステップ8では、Eo=γ・ρ(または、Eoはρの適切な単調増加関数)として、L0=α×2√(ρ2−(ρ−Eo)2)から算出したリサンプル区間長判定値L0に基づいて、リンクnの量子化リサンプル長Lnを決定しても良い。
【0051】
次のリンクに着目して(ステップ10)、ステップ4以降の手順を繰り返し、対象道路の全てのリンクについての処理が終了すると(ステップ9)、隣接リンク間で量子化リサンプル長が同じ場合にリンクを連結し、図6に示すように、対象道路全体のリサンプル長(L2、L4、・・・、L3)を始端からの距離で表現する(ステップ11)。次に、対象道路に対し、このリサンプル長を用いてリサンプル処理を行い、サンプリング点の位置情報を偏角または偏角予測差分値で表し、可変長符号化を行ってデータ圧縮する(ステップ12)。
【0052】
こうした処理により、データ量が少なく、道路の元形状と良く近似した道路位置を表す符号化データを得ることができる。
図7は、交通情報の対象道路を伝えるために、このリサンプル長決定方法を実行する情報送信装置(符号化データ生成装置)20と、提供された交通情報を活用する、車載用ナビゲーション装置やパーソナルコンピュータなどの情報活用装置(符号化データ復元装置)40との構成を示している。情報送信装置20は、渋滞情報や交通事故情報などが入力される事象情報入力部21と、デジタル地図データベースA22から交通情報の対象道路区間の道路形状データを抽出する形状データ抽出部23と、リサンプル形状と元形状データとの間の許容誤差を決定する許容誤差決定部24と、許容誤差に基づいてリサンプル長Lを決定するリサンプル長決定部25と、形状データ抽出部23で抽出された道路形状データをリサンプルしてサンプリング点の位置データ列を生成する形状データリサンプル処理部26と、形状データリサンプル処理部26が生成したデータを圧縮符号化する可変長符号化処理部28と、圧縮符号化された道路形状データを蓄積して外部メディアに蓄積データを提供する圧縮データ蓄積部27と、圧縮符号化された道路形状データを送信する形状データ送信部29とを備えている。
【0053】
一方、情報活用装置40は、提供された道路形状データを受信する形状データ受信部41と、圧縮符号化されているデータを復号する符号化データ復号部42と、リサンプル形状を復元する形状データ復元部43と、デジタル地図データベースB46のデータを用いてマップマッチングを行い、サンプリング点で表された道路区間をデジタル地図上で特定するマップマチング部45と、得られた交通情報を活用する情報活用部44とを備えている。
【0054】
情報送信装置20では、リサンプル長決定部25が、許容誤差決定部24で決定された許容誤差に基づいて、リサンプルにおけるリサンプル長Lを決定する。形状データリサンプル処理部26は、決定されたリサンプル長Lを用いて、形状データ抽出部23が抽出した対象道路の道路形状データをリサンプルする。
【0055】
可変長符号化処理部28は、この道路形状データを可変長符号化する。可変長符号化によりデータ圧縮された道路形状データは、外部メディアに記録されて提供され、あるいは、形状データ送信部29から送信される。
【0056】
この道路形状データを受信した情報活用装置40では、符号化データ復号部42が、圧縮符号化されているデータを復号化し、形状データ復元部43が、サンプリング点の位置情報を復元して、サンプリング点を繋いだリサンプル形状を再現する。このリサンプル形状は、情報活用装置40の表示画面上にデジタル地図と重ねて表示される。
【0057】
また、伝えられた道路区間を正確に特定するために、マップマッチング部45は、サンプリング点の位置データとデジタル地図データベースB46の地図データとのマップマッチングを行い、デジタル地図データベースB46の地図データ上で対象道路を特定する。
【0058】
情報活用部44は、得られた交通情報を、画面に表示したり、経路探索に利用したりして活用する。情報活用装置40は、カーナビ受信機または地図表示端末をも構成し得る。
また、図8は、走行軌跡を伝えるために、このリサンプル長決定方法を実行するプローブカー車載機(符号化データ生成装置)60と、プローブ情報を収集するプローブ情報収集センタ(符号化データ復元装置)50との構成を示している。プローブカー車載機60は、GPSアンテナ73から受信する情報やジャイロ74の検知情報を基に自車位置を判定する自車位置判定部61と、速度を検出するセンサ70と、ハンドル舵角を検出するセンサ71と、横方向の加速度(横G)を検出するセンサ72と、デジタル地図のデータベース69と、リサンプル形状と道路形状との間の許容誤差を決定する許容誤差決定部67と、リサンプルに用いるリサンプル長Lを決定するリサンプル長決定部68と、自車の走行軌跡を蓄積する走行軌跡蓄積部62と、走行軌跡をリサンプルしてサンプリング点の位置データ列を生成する走行軌跡形状リサンプル処理部63と、走行軌跡形状リサンプル処理部63が生成したデータを圧縮符号化する可変長符号化処理部64と、圧縮符号化された走行軌跡形状データを蓄積する圧縮データ蓄積部65と、圧縮符号化された走行軌跡形状データを送信する走行軌跡送信部66とを備えている。
【0059】
一方、プローブ情報収集センタ50は、プローブカー車載機60から提供された走行軌跡形状データを受信する走行軌跡受信部51と、圧縮符号化されている受信データを復号化する符号化データ復号部52と、復号化されたデータから走行軌跡形状を復元する走行軌跡形状復元部53と、プローブカー車載機60から収集した走行軌跡や計測情報を交通情報の生成に活用する走行軌跡計測情報活用部54とを備えている。
【0060】
プローブカー車載機60の走行軌跡蓄積部62には、自車位置判定部61で検出された自車位置が走行軌跡として順次蓄積される。リサンプル長決定部68は、センサ70、71、72で検知された速度、ハンドル舵角、横Gの情報や、デジタル地図データベース69から取得した道路形状から、走行軌跡の曲率の大小を判定し、その曲率の大きさや、許容誤差決定部67で決定された許容誤差に基づいて、リサンプルに使用するリサンプル長Lを決定する。
【0061】
走行軌跡形状リサンプル処理部63は、プローブ情報の送信時期に、走行軌跡蓄積部62に蓄積された走行軌跡データを読み出し、リサンプル長決定部68が決定したリサンプル長を用いて走行軌跡形状をリサンプルする。
【0062】
可変長符号化処理部64は、このデータを可変長符号化して圧縮する。圧縮符号化されたデータは、プローブ情報収集センタ50に送信される。また、このデータは、外部メディアに格納してプローブ情報収集センタ50に提供される場合もある。
【0063】
プローブ情報収集センタ50では、符号化データ復号部52が、プローブカー車載機60から収集したデータを復号化し、走行軌跡形状復元部53が、サンプリング点の位置情報を復元して、走行軌跡のリサンプル形状を再現する。この走行軌跡の情報は、プローブカー車載機60で計測された速度等の計測情報と併せて交通情報の生成に活用される。
【0064】
このように、情報送信装置やプローブカー車載機が、本発明のリサンプル長決定方法を用いて、対象道路や走行軌跡の符号化を行うことにより、この符号化データを受信する情報活用装置やプローブ情報収集センタでは、受信データを復号化して、リサンプル形状を的確に再現することができる。
【0065】
(第2の実施形態)
本発明の第2の実施形態では、道路形状が円弧の一部とみなせないときの例として、V字カーブでのリサンプル長の決定方法について説明する。
【0066】
V字カーブでは、図9に示すように、V字カーブ部分を、それに接する円で近似してリサンプルを行う。円の大きさは、図10に示すように、V字カーブと円との間の最大誤差が、予め設定した許容誤差Emax2を超えないように設定する。
【0067】
円の半径をR、円とV字カーブとの接点P1、P2からV字カーブの交点Pまでの距離をDとすると、
ω=(180−θ)/2
(R+Emax2)2=D2+R2
D・tanω=R
の関係が成立するので、これらの式から、Dは(数12)として、また、Rは(数13)として算出することができる。
【0068】
D=Emax2・[tanω+√{(tanω)2+1}] (数12)
R=D/tanω
=Emax2・[1+(√{(tanω)2+1})/tanω] (数13)
そして、V字カーブをリサンプルする場合は、点Pから距離Dだけ離れた直線上にノードP1、P2を追加し、P1→P→P2間は曲率半径Rの円と見立てて、Rで決定されるリサンプル長Lによってリサンプルを行う。
【0069】
図11のフロー図は、V字カーブでのリサンプル処理手順を示している。
まず、V字カーブの最大許容誤差Emax2を決定する(ステップ21)。次に、デジタル地図データベースから対象道路の道路形状データを取得する(ステップ22)。n=2のリンクnから順に着目して(ステップ23)、リンクn及び隣接リンク(n−1)の情報を取得し(ステップ24)、リンクnと隣接リンク(n−1)とがV字カーブであるか否か判定する(ステップ25)。
【0070】
この判定は、図12に示す手順で行う。即ち、リンク(n−1)とリンクnとの間の偏角θn、及び、リンクnの長さSnを算出し(ステップ41)、θn及びSnを用いて(数10)(数11)により曲率半径ρnを算出する(ステップ42)。
【0071】
次に、定数κを用いて、Sn≦κ・ρnの条件式を満たすかどうかを判定する(ステップ43)。図13(a)に示すように、Snが長いときは、この条件式を満たさない。この場合は、リンク(n−1)→リンクn間が円弧近似の無理なV字カーブと判定する(ステップ45)。また、図13(b)に示すように、Snが短いときは、この条件式を満たす。この場合は、リンク(n−1)→リンクn間が円弧近似の可能な通常のカーブと判定する(ステップ44)。κ=1のとき、Snが、曲率半径ρnの円弧を正六角形以上の角数で近似していれば条件式を満たすことになる。
【0072】
リンク(n−1)→リンクn間がV字カーブである場合は、Emax2の値を基に、(数12)(数13)を用いてD及びRを算出し(ステップ27)、リンク(n−1)とリンクnとの接続点Pから距離Dだけ離れたリンク上にノードP1、P2を追加し、P1→P→P2間の曲率半径をRとする(ステップ27)。
【0073】
そして、第1の実施形態で説明したリサンプル長決定方法を用いて量子化リサンプル長Lnを決定する(ステップ28)。また、ステップ25において、リンク(n−1)→リンクn間がV字カーブで無い場合は、直ぐにステップ28の処理を行う。
【0074】
こうした処理を全てのリンクについて行い、全てのリンクに対する処理が終了すると、第1の実施形態と同様に、隣接リンク間で量子化リサンプル長が同じ場合にリンクを連結し、対象道路全体のリサンプル長を始端からの距離で表現し(ステップ31)、対象道路へのリサンプル処理及び可変長符号化処理を行う(ステップ32)。
【0075】
こうした処理により、V字カーブに対しても適切なリサンプル長を設定することができる。
また、道路形状が、V時カーブの如き円弧の一部に近似しない折曲部分を含む場合、折曲部分の前後は、偏角の大きさに応じて予めリサンプル長を選出するよう設定しておいてもよい。例えば、偏角が26度以上で40度より小さい場合は、リサンプル長は50m、40度以上で60度より小さい場合は30m、60度以上の場合は15m、のように偏角に応じてリサンプル長を設定しておいてもよい。偏角が26度より小さい場合は、第1の実施形態で述べたリサンプル長の決定方法が用いられる。
【0076】
また、道路形状が円弧の一部に近似するか否か判定するに際し、当該道路に予め設定されているノード毎の偏角の大きさ、又は当該偏角の大きさ及びノード間の距離の関係を用いることができる。
【0077】
図14はデジタル地図上の道路の元形状が円弧に近似している場合において、元のデジタル地図の道路上にノードが設定されている状態を示す図である。
上述の通り、円弧とみなせるかみなせないかは、偏角の大きさとノード間距離によって判別することできる。
【0078】
偏角θとノード間距離Lから曲率半径ρを算出し、L<2√(ρ2−(ρ−E)2)ならば、元の対象道路は、交差点やV字カーブではなくスムーズなカーブであったと判別できる。ここで、Eにはデジタル化の入力誤差±5m程度(元の地図をデジタル化した際における標準的な誤差)が入る。
【0079】
図14の内側の円の場合、曲率半径は130mであり、最も長いと思われる線分(ノード間距離)の長さは66mである。地図データのデジタル化の入力誤差E=5mとすると、2√(ρ2−(ρ−E)2)=71mとなる。
【0080】
他のノード間距離はこれより小さいので、よって、この計算方法でほぼ正しいといえる。
また、計算を略して偏角のみでもおおむね判別することもできる。なだらかなカーブをデジタル化したような箇所であれば、偏角は小さいからである。
【0081】
また、図8では、プローブカー車載機60とプローブ情報収集センタ50の組み合わせより、プローブカーシステムが構築され、両者間でプローブカーシステムの情報伝達方法が達成されるが、当該方法は、本発明のリサンプル長決定方法、符号化データ生成方法及び当該符号化データの復号化方法の組み合わせより達成される。
【0082】
更に本発明は、線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムをも含む。当該プログラムは、線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定する手順と、判定手順の結果、線形対象物の形状が円弧の一部に近似すると判断された場合に、線形対象物の曲率半径を算出する手順と、線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、サンプリング点間を線で繋いだリサンプル形状と線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定する手順と、線形対象物の曲率半径が所定値以下又は所定値より小さい場合に、線形対象物を曲率半径に対応した多角形で近似する手順と、をコンピュータに実行させる。
【0083】
このようなプログラムは、情報送信装置20、プローブカー車載機60に、種々の形式で組み込まれる。例えば情報送信装置20、プローブカー車載機60内又はこれらの外部の装置内の所定のメモリにプログラムを記録することができる。また、ハードディスクのような情報記録装置や、CD−ROMやDVD−ROM、メモリカードのような情報記録媒体にプログラムを記録してもよい。また、ネットワーク経由により当該プログラムをダウンロードするようにしてもよい。
【0084】
また、本発明の情報送信装置20と情報活用装置40又はプローブカー車載機60とプローブ情報収集センタ50の組み合わせより、地図データ配信システムが構成される。情報送信装置20とプローブカー車載機60は、符号化データを生成するという観点からエンコーダとして機能し、情報活用装置40とプローブ情報収集センタ50は、符号化データを復元するという観点からデコーダとして機能する。
【0085】
また、符号化データ生成装置である情報送信装置20又はプローブカー車載機60は、情報送信側における実施の形態の例であり、情報を送信する事が出来る装置や端末であればどのような形態のものでもよい。さらに生成した符号化データを媒体に記録して、他の装置に提供することも可能である。また、符号化データ復元装置である情報活用装置40又はプローブ情報収集センタ50も情報受信側における実施の形態の例であり、パーソナルコンピュータ、携帯端末等の情報を活用できる装置であればなんでもよい。もちろん、符号化データの復元が可能な情報収集センターや、センター側の装置でも同様の効果を得ることが出来る。さらに符号化されたデータが記録された媒体等を用いて、復元処理することにより、同様の効果を得ることは言うまでもない。
【0086】
また、本発明の符号化データ生成方法に沿ったアルゴリズム(プログラム)を、地図データ本体に各種地図情報に対応した地図データが記録された記録媒体に記録することができる。これにより、地図データ本体自体を圧縮符号化することが可能となる。
【0087】
尚、上述の実施形態においては、線形対象物が位置参照用の道路形状である例を説明したが、線形対象物は道路形状に限られない。「線形対象物」とは直線、曲線など種々の形態を含む細長い形状のものを総て含み、地図上の線形形状によって表わせる地理情報総てを含み得る。更に、指紋等地図とは関係ないが、線形形状によって表わされるもの総てをも含まれる。
【0088】
本発明を詳細にまた特定の実施態様を参照して説明したが、本発明の精神と範囲を逸脱することなく様々な変更や修正を加えることができることは当業者にとって明らかである。
【0089】
本出願は、2003年10月21日出願の日本特許出願(特願2003−360631)に基づくものであり、その内容はここに参照として取り込まれる。
【産業上の利用可能性】
【0090】
本発明のリサンプル長決定方法及び符号化データ生成方法は、デジタル地図の道路形状や河川、鉄道線路、行政境界線、等高線などの位置情報を表す符号化データを生成・蓄積・保存するときなどに利用することができ、また、デジタル地図以外にも、各種の図形や指紋などの形状を表す符号化データを生成・蓄積・保存するときなどに適用することができる。また、本発明の装置は、その符号化データの生成・蓄積・保存を実行する各種装置に適用することができる。
【特許請求の範囲】
【請求項1】
線形対象物をリサンプルするサンプリング点間のリサンプル長を、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、予め決めた許容誤差を超えないように設定する、リサンプル長決定方法。
【請求項2】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記形状が前記円弧の一部に近似すると判断された場合に、前記線形対象物の曲率半径を算出するステップと、
前記線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定するステップと、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さい場合に、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップと、を備えるリサンプル長決定方法。
【請求項3】
請求項1又は2記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が所定値以上又は所定値より大きいと判断され、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定するステップにおいて、前記線形対象物の曲率半径をρ、前記許容誤差をEmaxとして、
√(ρ2−(ρ−Emax)2)
を含む判定式の値に基づいて前記リサンプル長を決定する、リサンプル長決定方法。
【請求項4】
請求項2記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さいと判断され、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップにおいて、前記線形対象物の曲率半径ρ、さらに固定パラメータKrを用いた、Kr・ρを含む判定式に基づいて前記サンプリング長を決定する、リサンプル長決定方法。
【請求項5】
請求項2記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さいと判断され、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップにおいて、前記曲率半径が小さい程、前記許容誤差も小さくなるように、前記許容誤差を前記曲率半径に応じて変更する、リサンプル長決定方法。
【請求項6】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記線状対象形状物の形状が、前記円弧の一部に近似しない折曲部分を含むと判断された場合に、、前記折曲部分との誤差が許容誤差を超えない円の一部で前記折曲部分を近似するステップと、
前記判定式の値を算出し、当該算出した値に基づいて前記リサンプル長を決定するステップとを更に備える、リサンプル長決定方法。
【請求項7】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記線状対象形状物の形状が、前記円弧の一部に近似しない折曲部分を含むと判断された場合に、前記折曲部分の前後は、偏角の大きさに応じて予め決めたリサンプル長を選出する、リサンプル長決定方法。
【請求項8】
請求項2ないし7のいずれか1項記載のリサンプル長決定方法であって、
前記線形対象物の形状が円弧の一部に近似するか否か判定するステップが、偏角の大きさ、又は偏角及びノード間の距離の関係を用いて行われる、リサンプル長決定方法。
【請求項9】
請求項1ないし8のいずれか1項に記載された方法により線形対象物のリサンプル長を決定するステップと、
前記線形対象物を、決定したリサンプル長でリサンプルして複数のサンプリング点を設定するステップと、
各サンプリング点の位置データを、発生頻度に偏りを持つ角度成分で表現するステップと、
前記角度成分で表わされた位置データを順番に並べたデータ列に対して可変長符号化を行うステップと、を備える線形対象物の符号化データ生成方法。
【請求項10】
請求項1ないし8のいずれか1項記載のリサンプル長決定方法を用いて、線形対象物をリサンプルするサンプリング点間のリサンプル長を決定するリサンプル長決定部を備える装置。
【請求項11】
線形対象物をリサンプルするサンプリング点間のリサンプル長を請求項1ないし請求項8のいずれか1項記載のリサンプル長決定方法で決定するリサンプル長決定部と、
前記リサンプル長決定部が決定したリサンプル長で前記線形対象物をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、
前記リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部と、を備える符号化データ生成装置。
【請求項12】
プローブカーの走行軌跡を伝えるプローブカー車載機であって、
線形対象物をリサンプルするサンプリング点間のリサンプル長を請求項1ないし請求項8のいずれか1項記載のリサンプル長決定方法で決定するリサンプル長決定部と、
前記リサンプル長決定部が決定したリサンプル長で前記線形対象物をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、
前記リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部と、を備えるプローブカー車載機。
【請求項13】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムであって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定する手順と、
前記判定手順の結果、前記形状が前記円弧の一部に近似すると判断された場合に、前記線形対象物の曲率半径を算出する手順と、
前記線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定する手順と、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さい場合に、前記線形対象物を曲率半径に対応した多角形で近似する手順と、をコンピュータに実行させるプログラム。
【請求項14】
請求項9記載の線形対象物の符号化データ生成方法を用いて得られた符号化データを受信する受信部と、
当該受信された符号化データを復元する復元部と、を備える符号化データ復元装置。
【請求項1】
線形対象物をリサンプルするサンプリング点間のリサンプル長を、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、予め決めた許容誤差を超えないように設定する、リサンプル長決定方法。
【請求項2】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記形状が前記円弧の一部に近似すると判断された場合に、前記線形対象物の曲率半径を算出するステップと、
前記線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定するステップと、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さい場合に、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップと、を備えるリサンプル長決定方法。
【請求項3】
請求項1又は2記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が所定値以上又は所定値より大きいと判断され、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定するステップにおいて、前記線形対象物の曲率半径をρ、前記許容誤差をEmaxとして、
√(ρ2−(ρ−Emax)2)
を含む判定式の値に基づいて前記リサンプル長を決定する、リサンプル長決定方法。
【請求項4】
請求項2記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さいと判断され、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップにおいて、前記線形対象物の曲率半径ρ、さらに固定パラメータKrを用いた、Kr・ρを含む判定式に基づいて前記サンプリング長を決定する、リサンプル長決定方法。
【請求項5】
請求項2記載のリサンプル長決定方法であって、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さいと判断され、前記線形対象物を曲率半径に対応した多角形で近似することでリサンプル長を設定するステップにおいて、前記曲率半径が小さい程、前記許容誤差も小さくなるように、前記許容誤差を前記曲率半径に応じて変更する、リサンプル長決定方法。
【請求項6】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記線状対象形状物の形状が、前記円弧の一部に近似しない折曲部分を含むと判断された場合に、、前記折曲部分との誤差が許容誤差を超えない円の一部で前記折曲部分を近似するステップと、
前記判定式の値を算出し、当該算出した値に基づいて前記リサンプル長を決定するステップとを更に備える、リサンプル長決定方法。
【請求項7】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定方法であって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定するステップと、
前記判定ステップの結果、前記線状対象形状物の形状が、前記円弧の一部に近似しない折曲部分を含むと判断された場合に、前記折曲部分の前後は、偏角の大きさに応じて予め決めたリサンプル長を選出する、リサンプル長決定方法。
【請求項8】
請求項2ないし7のいずれか1項記載のリサンプル長決定方法であって、
前記線形対象物の形状が円弧の一部に近似するか否か判定するステップが、偏角の大きさ、又は偏角及びノード間の距離の関係を用いて行われる、リサンプル長決定方法。
【請求項9】
請求項1ないし8のいずれか1項に記載された方法により線形対象物のリサンプル長を決定するステップと、
前記線形対象物を、決定したリサンプル長でリサンプルして複数のサンプリング点を設定するステップと、
各サンプリング点の位置データを、発生頻度に偏りを持つ角度成分で表現するステップと、
前記角度成分で表わされた位置データを順番に並べたデータ列に対して可変長符号化を行うステップと、を備える線形対象物の符号化データ生成方法。
【請求項10】
請求項1ないし8のいずれか1項記載のリサンプル長決定方法を用いて、線形対象物をリサンプルするサンプリング点間のリサンプル長を決定するリサンプル長決定部を備える装置。
【請求項11】
線形対象物をリサンプルするサンプリング点間のリサンプル長を請求項1ないし請求項8のいずれか1項記載のリサンプル長決定方法で決定するリサンプル長決定部と、
前記リサンプル長決定部が決定したリサンプル長で前記線形対象物をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、
前記リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部と、を備える符号化データ生成装置。
【請求項12】
プローブカーの走行軌跡を伝えるプローブカー車載機であって、
線形対象物をリサンプルするサンプリング点間のリサンプル長を請求項1ないし請求項8のいずれか1項記載のリサンプル長決定方法で決定するリサンプル長決定部と、
前記リサンプル長決定部が決定したリサンプル長で前記線形対象物をリサンプルして複数のサンプリング点を設定するリサンプル処理部と、
前記リサンプル処理部が設定した各サンプリング点の位置データを発生頻度に偏りを持つ角度成分で表し、各サンプリング点の位置データを順番に並べたデータ列に対して可変長符号化を行ってデータを圧縮する可変長符号化処理部と、を備えるプローブカー車載機。
【請求項13】
線形対象物をリサンプルするサンプリング点間のリサンプル長の決定をコンピュータに実行させるためのプログラムであって、
前記線形対象物の形状が、所定の条件下において円弧の一部に近似するか否か判定する手順と、
前記判定手順の結果、前記形状が前記円弧の一部に近似すると判断された場合に、前記線形対象物の曲率半径を算出する手順と、
前記線形対象物の曲率半径が所定値以上又は所定値より大きい場合に、前記サンプリング点間を線で繋いだリサンプル形状と前記線形対象物との誤差が、所定の許容誤差を超えないようにリサンプル長を設定する手順と、
前記線形対象物の曲率半径が前記所定値以下又は所定値より小さい場合に、前記線形対象物を曲率半径に対応した多角形で近似する手順と、をコンピュータに実行させるプログラム。
【請求項14】
請求項9記載の線形対象物の符号化データ生成方法を用いて得られた符号化データを受信する受信部と、
当該受信された符号化データを復元する復元部と、を備える符号化データ復元装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【国際公開番号】WO2005/038752
【国際公開日】平成17年4月28日(2005.4.28)
【発行日】平成19年12月13日(2007.12.13)
【国際特許分類】
【出願番号】特願2005−514826(P2005−514826)
【国際出願番号】PCT/JP2004/015408
【国際出願日】平成16年10月19日(2004.10.19)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.VICS
【出願人】(000005821)松下電器産業株式会社 (73,050)
【Fターム(参考)】
【国際公開日】平成17年4月28日(2005.4.28)
【発行日】平成19年12月13日(2007.12.13)
【国際特許分類】
【国際出願番号】PCT/JP2004/015408
【国際出願日】平成16年10月19日(2004.10.19)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.VICS
【出願人】(000005821)松下電器産業株式会社 (73,050)
【Fターム(参考)】
[ Back to top ]