以下、本発明の実施の形態を図面を参照� ��て説明する。

実施の形態1.
 図1は、本発明の第1の実施の形態の例を示� �ブロック図である。本発明のマップマッチ� �グシステムは、マップマッチング装置101と� �道路データ記憶装置102と、道路データ生成� �置103と、道路ネットワーク記憶装置104とを� �える。

 道路ネットワーク記憶装置104は、道路網� ��データを交差点と交差点間をつなぐ道路の� ��ットワークとして記憶する道路ネットワー� ��記憶手段2を備える。

 道路データ生成装置103は、道路ネットワ� ��ク記憶手段2に記憶されているデータが表す 道路網を複数の領域に分割した場合における 各領域に属する道路のデータを生成する。道 路網が存在する領域全体を分割して得られる 領域をグリッドと記す。道路データ生成装置 103は、各グリッド毎に、グリッドとグリッド に属する道路とを対応付けたデータを生成す る。

 道路データ記憶装置102は、グリッド道路� ��憶手段3を備える。グリッド道路記憶手段3� �、グリッド道路生成手段8によって生成され� ��データ(各グリッド毎にグリッドと道路とを 対応付けたデータ)を記憶する記憶装置であ� �。

 マップマッチング装置101は、イベント収� ��手段1と、高速マップマッチング手段4と、� �ベント道路記憶手段5と、イベント解析手段6 と、解析結果出力手段7とを備える。

 イベント収集手段1は、道路上のプローブ カーからイベントデータを受信する。イベン トデータは、車両の位置および状態を表すデ ータであり、イベントデータを送信する車両 をプローブカーと呼ぶ。プローブカーの数は 複数であり、数万台といった多くのプローブ カーからイベントデータを受信してもよい。 なお、地域毎に設置された基地局が無線通信 ネットワークを介してプローブカーからイベ ントデータを受信し、イベント収集手段1は� �各基地局からイベントデータを受信する。� �のように、イベント収集手段1は、基地局を� ��してプローブカーからイベントデータを受� ��する。以下、プローブカーを単に車両と記� ��。

 基地局や、イベントデータを生成する車� ��の構成は特に限定されない。また、イベン� ��収集手段1、基地局、車両間の通信プロトコ ルも特に限定されない。イベント収集手段1� �、記憶装置を備え、受信したイベントデー� �をその記憶装置に蓄積し、例えば一定時間� �に、蓄積しているイベントデータを発生順� �ソートし高速マップマッチング手段4が備え� ��イベントグリッドマッチ手段401(より具体的 にはイベント記憶手段40101)に記憶させる。イ ベント収集手段1は、イベントグリッドマッ� �手段401に記憶させたイベントデータは、イ� �ント収集手段1自身が備える記憶装置から削� ��する。

 高速マップマッチング手段4は、グリッド 道路記憶手段3に記憶されているグリッドの� �ータを参照して、イベント収集手段1が受信� ��たイベントデータと各道路とを対応付ける� ��ップマッピング処理を行う。

 イベント道路記憶手段5は、高速マップマ ッチング手段4によって対応付けられた道路� �イベントデータとの対応関係を記憶する記� �装置である。イベント解析手段6は、イベン� ��道路記憶手段5に記憶された道路とイベント データとの対応関係と各イベントデータとを 参照して交通状況の解析を行う。イベント解 析手段6が実行可能な解析の例として、例え� �道路の渋滞度の判定が挙げられるが、イベ� �ト解析手段6が実行する解析の種類は特に限� ��されない。解析結果出力手段7は、イベント 解析手段6による解析結果を出力する出力装� �である。例えば、解析結果出力手段7は、解� ��結果を表示するディスプレイ装置である。� ��た、イベント解析手段6は、例えば、プログ ラムに従って動作するCPUによって実現される 。

 図1では、マップマッピングシステムがマ ップマッチング装置101と、道路データ記憶装 置102と、道路データ生成装置103と、道路ネッ トワーク記憶装置104とを備え、それぞれの装 置が上述のように各手段を有する構成例を示 したが、マップマッピングシステムは図1に� �す構成に限定されない。例えば、道路ネッ� �ワーク記憶手段2とグリッド道路記憶手段3と が同一の装置で実現されていてもよい。また 、上述の各手段が全て同一の装置に設けられ る構成であってもよい。この点は、後述する 他の実施の形態でも同様である。

 以下、本発明のマップマッピングシステ� ��の各構成要素およびその動作や、本発明に� ��用される各データについて説明する。

 グリッド道路生成手段8は、道路グリッド 分割手段801と、グリッド道路結合手段802とを 有する。道路グリッド分割手段801は、道路ネ ットワーク記憶手段2に記憶されているデー� �に基づいて、道路網が存在する領域を緯度� �向および経度方法にそれぞれ等間隔に分割� �た各分割領域(グリッド)と道路とを対応付け たデータを生成する。なお、緯度方向の分割 間隔と経度方向の分割間隔とは一致していて も異なっていてもよい。グリッド道路結合手 段802は、道路グリッド分割手段801によって生 成されたデータ(グリッドと道路とを対応付� �たデータ)のうち、互いに隣接するグリッド� ��あってグリッドに対応付けられている道路� ��集合が一致する複数のグリッドが存在して� ��る場合、その複数のグリッドに対して共通� ��グリッドIDを付すことで1つのグリッドとす� ��。また、対応付けられている道路の集合が� ��隣接するいずれのグリッドとも異なってい� ��グリッドに対してもグリッドIDを付す。グ� �ッドIDは、各グリッドを識別するための識別 情報であり、通過するアークの集合が共通で あるグリッドの集合毎に一意に割り当てられ る。このように、対応付けられている道路の 集合が共通である隣接するグリッドの集合、 および対応付けられている道路の集合が隣接 するいずれのグリッドとも異なっているグリ ッドに対してグリッドIDを付すことをグリッ� ��の結合処理と記す。グリッド道路結合手段8 02は、道路と、結合前のグリッドと、結合処� ��後のグリッドとの対応関係をグリッド道路� ��憶手段3に記憶させる。例えば、結合処理前 の各グリッドと結合処理によって付されたグ リッドIDとの対応関係を示す情報と、グリッ� ��IDとそのグリッドIDが示すグリッドに対応す る道路との対応関係を示す情報を作成し、作 成した情報をグリッド道路記憶手段3に記憶� �せる。

 結合処理後では、1つのグリッドIDが割り� ��てられたグリッドを1つのグリッドとして扱 う。従って、隣接する複数のグリッドに1つ� �グリッドが割り当てられた場合、その複数� �グリッドが1つのグリッドとなる。

 なお、道路グリッド分割801は、導出した� ��情報をグリッド道路記憶手段3に記憶させ、 グリッド道路結合手段802は、その情報を読み 込んで結合処理を行い、情報をグリッド道路 記憶手段3に記憶させる。

 道路グリッド分割801およびグリッド道路� ��合手段802は、例えば、プログラムに従って� ��作するCPUによって実現される。例えば、道� ��データ生成装置103は、道路グリッド分割801� ��よびグリッド道路結合手段802の動作をコン� ��ュータに実行させるための道路データ生成� ��ログラムを予め記憶し、道路データ生成装� ��103に設けられるCPUがその道路データ生成プ� ��グラムに従って動作する。

 高速マップマッチング手段4は、イベント グリッドマッチ手段401と、イベント処理優先 度判定手段402と、イベント道路マッチ手段403 とを有する。イベントグリッドマッチ手段401 は、グリッド道路記憶手段3に記憶されてい� �結合処理後のグリッドと、そのグリッドの� �囲で発生したイベントデータとを対応付け� �。イベント処理優先度判定手段402は、結合� �理後のグリッドに対応付けられたイベント� �ータの数が、閾値(以下、最大イベント数と� ��す。)となる値より多ければ、そのイベント データから最大イベント数のイベントデータ を抽出する。また、イベント処理優先度判定 手段402は、結合処理後のグリッドに対応付け られたイベントデータの数が最大イベント数 未満であれば、そのグリッドに対応付けられ たイベントデータを全て抽出する。イベント 処理優先度判定手段402は、この処理を各グリ ッド毎に行う。最大イベント数は、解析精度 の維持とマッチング処理の高速化を両立する ために予め定められた閾値である。イベント 道路マッチ手段403は、イベント処理優先度判 定手段402によって抽出された全てのイベント データについて、イベントデータに対応付け られたグリッド内の道路とイベントデータの 発生位置との距離計算を行い、イベントデー タが生成された道路を特定し、イベントデー タと道路とを対応付ける。

 イベントグリッドマッチ手段401は、例え� ��、記憶装置と、プログラムに従って動作す� ��CPUとによって実現される。イベント処理優� ��度判定手段402およびイベント道路マッチ手� ��403は、プログラムに従って動作するCPUとに� ��って実現される。

 たとえば、マップマッチング装置101は、� ��ベント発生手段1、イベントグリッドマッチ 手段401、イベント処理優先度判定手段402、イ ベント道路マッチ手段403、イベント解析手段 6の動作をコンピュータに実行させるための� �ップマッチングプログラムを予め記憶し、� �ップマッチング装置101に設けられるCPUがそ� �マップマッチングプログラムに従って動作� �る。

 ここで、イベントデータについて説明す� ��。図2は、イベントデータの例を示す説明図 である。図2(a)は、本発明に適用されるイベ� �トデータが必ず含むデータを示している。� �両は、図2(a)に例示するように、少なくとも� ��ベントデータのID、イベントデータの生成� �時、イベントデータ生成時における車両の� �置、速度を含むイベントデータを生成する� �イベントデータのID、生成日時、車両の位置 、速度は、本発明に適用されるイベントデー タに含まれていなければならないデータであ るが、図2(b)に例示するように、方向、ワイ� �ー利用状況、ブレーキ利用情報等の他のデ� �タが含まれていてもよい。

 図2においてT101の符号を付して示したIDは 、個々のイベントデータを識別するための識 別情報である。図2では“E1”というIDを示し� ��いるが、車両は、例えば車両の識別情報と� ��ベントデータの生成時刻とを含む文字列をI Dとする。IDは、複数の車両によって生成され るイベントデータを識別できる情報であれば よい。

 図2に示す日時T102は、イベントデータの� �生日時(すなわち、車両がイベントデータを� ��成した生成日時)である。図2では、日付お� �び時刻で日時T102を表現しているが、日時は� ��の表現形式で表されてもよい。例えば、あ� ��日時からの経過秒などで日時T102が表現され ていてもよい。

 図2に示す位置T103は、イベントデータ生� �時の車両の位置である。図2では、(経度,緯� �)の形式で位置を表現しているが、位置は他� ��形式で表現されてもよい。例えば、ある基� ��点からの距離および角度によって位置が表� ��れてもよい。なお、この場合の角度とは、� ��準点と車両位置を結ぶ線分と、基準点を通� ��する基準軸との角度である。

 図2に示す速度T104は、イベントデータ生� �時の車両の速度である。図2では、時速をキ� ��メートルで表現しているが、他の形式で速� ��が表されていてもよい。例えば、分速をマ� ��ルで表した値を速度としてもよい。

 イベントデータには、少なくともID、日� �、位置および速度が含まれる。イベントデ� �タにさらに他のデータが含まれていてもよ� �。図2(b)は、さらに他のデータを含むイベン� ��データの例を示している。

 図2(b)に示す方向T105は、イベントデータ� �成時の車両の進行方向である。図2(b)では、� ��る基準の方向からの角度で方向を表現して� ��るが、他の形式で方向が表されてもよい。� ��えば、北北東といった表現を用いてもよい� ��

 図2(b)に示すワイパー利用状況T106は、イ� �ントデータ生成時に車両がワイパーを使用� �ているか否かを示すデータである。例えば� �イベントデータ生成時に車両がワイパーを� �用している場合には“1”とし、使用してい� ��い場合には“0”とすればよい。同様に、図 2(b)に示すブレーキ利用状況T107は、イベント� ��ータ生成時に車両がブレーキを使用してい� ��か否かを示すデータである。例えば、イベ� ��トデータ生成時に車両がブレーキを使用し� ��いる場合には“1”とし、使用していない場 合には“0”とすればよい。同様に、イベン� �データ生成時の車両のライトの利用状況が� �ベントデータに含まれていてもよい。

 道路ネットワーク記憶手段2に記憶される 道路網のデータについて説明する。道路ネッ トワーク記憶手段2に記憶される道路網のデ� �タは、交差点(ノード)と、交差点と交差点と を結ぶ道路(アーク)とで表現される。以下に� ��す例では、説明を簡単にするため、道路を� ��始点の交差点から終点の交差点までの直線� ��表現する。カーブしている道路を表現する� ��合には、カーブしている道路の途中で補助� ��してノードを配置し、短いアークを連ねる� ��とで表現することができる。

 道路ネットワーク記憶手段2は、図3に示� �アーク情報テーブルと、図4に示すノード情� ��テーブルを記憶する記憶装置である。この� ��ーク情報テーブルおよびノード情報テーブ� ��により道路網が表現される。

 図3は、アーク情報テーブルを示す。図3� �おいてT201の符号を付して示したアークIDは� �各道路を識別するための識別情報である。� �ークIDは、道路に割り当てた通し番号でよい 。始点T202は、道路の始点となる交差点のIDで あり、終点T203は、道路の終点となる交差点� �IDである。アーク情報テーブルは、このアー クID、始点および終点を対応付けた情報の集� ��である。

 図4は、ノード情報テーブルを示す。図4� �おいてT204の符号を付して示したノードIDは� �各交差点を識別するための識別情報である� �ノードIDは、交差点に割り当てた通し番号で よい。緯度T205は、交差点の緯度であり、経� �T206は、交差点の経度である。ここでは、交� ��点の位置を緯度および経度で表現している� ��、交差点の位置の表現は緯度および経度に� ��定されない。ノード情報テーブルは、ノー� ��IDと、ノードの位置とを対応付けた情報の� �合である。

 なお、アーク情報テーブルにおける始点T 202および終点T203は、ノード情報テーブルに� �まれるノードIDで表される。

 図5は、アーク情報テーブルおよびノード 情報テーブルによって表される道路網の例を 模式的に示す説明図である。図5において、� �分はアークを表し、“a”から始まるラベル� ��アークIDを意味する。また、丸は交差点を� �し、“n”から始まるラベルはノードIDを意� �する。図5に示すノードの位置は、実際の地� ��の交差点と同じ空間的な位置関係を表して� ��るもとのする。

 次に、グリッド道路生成手段8について説明 する。
 道路グリッド分割手段801は、道路ネットワ� ��ク記憶手段2に記憶されているアーク情報テ ーブルおよびノード情報テーブルが表す道路 網の領域を緯度方向および経度方法にそれぞ れ等間隔に分割した各分割領域(グリッド)を� ��出する。道路グリッド分割手段801は、図6は 、分割された道路網を模式的に示す説明図で ある。道路グリッド分割手段801は、緯度方向 の分割範囲にそれぞれ0から順にインデック� �(座標)を割り当てる。同様に、経度方向の分 割範囲にそれぞれ0から順にインデックス(座� ��)を割り当てる。緯度方向のインデックスお よび経度方向のインデックスがいずれも0と� �るグリッドを原点グリッドと記す。図6に示� ��例では、ノードn4を含むグリッド(符号G00を� ��したグリッド)が原点グリッドである。また 、原点グリッドの頂点となる4点のうち、緯� �および経度が最小となる点(図6に示す例では グリッドG00の左下の点)を原点と呼ぶ。以下� �説明では、グリッドをG(経度方向の座標,緯� �方向の座標)と表現する。この表現によれば� ��原点グリッドG00はG(0,0)と表現される。

 道路グリッド分割手段801は、道路網の領� ��を緯度方向および経度方向に等間隔に分割� ��る際、基準となる緯度および経度から等間� ��に分割すればよい。基準となる緯度および� ��度から等間隔に分割することで、各グリッ� ��の頂点の緯度および経度を特定できる。道� ��グリッド分割手段801は、各グリッドを横切� ��ているアークの集合を算出し記憶する。道� ��グリッド分割手段801は、1つのグリッドを横 切るアーク(道路)の集合を以下のように特定� ��る。道路グリッド分割手段801は、緯度およ� ��経度がグリッドの範囲内に収まるノード(交 差点)のノードIDをノード情報テーブル(図4参� ��。)から抽出し、そのノードIDを始点または� ��点とするアークIDをアーク情報テーブル(図3 参照。)から抽出する。抽出されたアークIDの 集合が1つのグリッドを横切るアークの集合� �ある。道路グリッド分割手段801は、グリッ� �を横切るアークの集合を特定する処理を各� �リッド毎に行う。そして、グリッドと、グ� �ッドを通過するアークとの対応関係を記憶� �る。

 以下、アーク等の要素の集合を表す場合� ��括弧内に各要素を並べて、{第一番目の要素 ,第二番目の要素,...}と表現する。図6に示す� �では、グリッドG(2,2)は、3つのアークa4,a5,a6� �含まれている。従って、グリッドG(2,2)を横� �るアークの集合を{a4,a5,a6}を表す。

 図7は、グリッドを横切るアークとして抽 出されたアークの集合をグリッド毎に示した 説明図である。

 グリッド道路結合手段802は、道路グリッ� ��分割手段801によって生成されたグリッドと� ��ークとを対応付けたデータに対して統合処� ��を行う。すなわち、互いに隣接するグリッ� ��であってグリッドに対応付けられているア� ��クの集合が一致する複数のグリッドが存在� ��ている場合、その複数のグリッドに対して1 つのグリッドIDを付す。また、対応付けられ� ��いる道路の集合が、隣接するいずれのグリ� ��ドとも異なっているグリッドに対してもグ� ��ッドIDを付す。

 グリッド道路結合手段802は、1つのグリッ ドに着目し、そのグリッドに隣接するグリッ ドに、着目したグリッドに対応付けられたア ークの集合と同一のアークの集合が対応付け られたグリッドが存在するか否かを判定し、 そのようなグリッドが存在するならば、着目 したグリッドおよび、着目したグリッドに対 応付けられたアークの集合と同一のアークの 集合が対応付けられたグリッドに同一のグリ ッドIDを割り当てる。グリッド道路結合手段8 02は、そのグリッドIDを割り当てたグリッド� �隣接するグリッドに、着目したグリッドに� �応付けられたアークの集合と同一のアーク� �集合が対応付けられたグリッドが存在する� �否かを判定し、そのようなグリッドが存在� �るならば、そのグリッドにも同一のグリッ� �IDを割り当てる。隣接するグリッドに、着目 したグリッドに対応付けられたアークの集合 と同一のアークの集合が対応付けられたグリ ッドが存在しなければ、着目するグリッドを 変更する。また、1つのグリッドに着目し、� �のグリッドに隣接するグリッドに、着目し� �グリッドに対応付けられたアークの集合と� �一のアークの集合が対応付けられたグリッ� �が存在するか否かを判定し、そのようなグ� �ッドが存在しなければ、着目したグリッド� �グリッドIDを割り当て、着目するグリッドを 変更する。グリッドを識別するためにグリッ ドに割り当てるグリッドIDは、例えば通し番� ��でよい。グリッド道路結合手段802は、この� ��理を繰り返し、着目していないグリッドで� ��ってグリッドIDが割り当てられていないグ� �ッドがなくなったならば結合処理を終了す� �。

 図7に示す例では、結合処理前に、G(0,0)か らG(4,5)までの24個が初期のグリッドがあり、� ��リッドに順に着目して処理を行う。グリッ� ��G(0,0)に着目した場合、G(0,0)に隣接するグリ� ��ドは、グリッドG(1,0),G(0,1)である。グリッド G(1,0)に対応するアークの集合は空集合であり 、グリッドG(0,1)に対応するアークの集合は{a3 }である。着目しているグリッドG(0,0)に対応� �るアークの集合は{a3}であるので、グリッドG (0,0),G(0,1)は結合される。すなわち、グリッド G(0,0),G(0,1)に共通のグリッドIDが割り当てられ る。なお、隣接するグリッドに同じアークが 対応付けられていても、アークの集合が異な っていれば結合されない。例えば、図7に示� �グリッドG(0,1),G(0,2)にはいずれもアークa3が� �応付けられているが、アーク集合としては{a 3}と{a2,a3,a4}で異なっているので、グリッドG(0 ,1),G(0,2)は結合されない。

 図8は、図7に例示するグリッドに対して� �結合処理を行った後のグリッドを模式的に� �す説明図である。図8に示す例では、グリッ� ��G(0,0)とグリッド(0,1)が結合したグリッドに� �G4というグリッドIDが割り当てられている。

 グリッド道路結合手段802は、結合処理後� ��、グリッド道路記憶手段3にアーク、結合処 理前のグリッド、結合処理後のグリッドとの 対応関係を記憶させる。本例では、グリッド 道路結合手段802は、図9に例示する配列グリ� �ドテーブルおよび図10に例示するグリッドア ークテーブルをグリッド道路記憶手段3に記� �させる。ただし、図9および図10はグリッド� �路結合手段802がグリッド道路記憶手段3に記� ��させるデータのデータ構造の一例を示した� ��のである。他の構造のデータ、例えば、配� ��グリッドテーブルおよびグリッドアークテ� ��ブルを統合した1つのテーブルをグリッド道 路記憶手段3に記憶させてもよい。

 図9は、配列グリッドテーブルの例を示す 。配列グリッドテーブルは、結合処理前の各 グリッドの緯度方向および経度方向のインデ ックス(座標)と、結合処理において割り当て� ��れたグリッドIDとを対応付けた情報の集合� �ある。図9においてT301の符号を付して示した 配列IDは、結合処理前の各グリッドの緯度方� ��および経度方向のインデックスを表してい� ��。図9に示す例では、(経度方向,緯度方向)と いうフォーマットで処理前の各グリッドの位 置を表している。図9においてT302の符号を付� ��て示したグリッドIDは、結合処理で割り当� �られたグリッドIDである。例えば、図8に示� �ようにグリッドG(0,0),(0,1)に共通のグリッドID “G4”を割り当てている場合、グリッド道路� ��合手段802は、その各グリッドの座標(0,0),(0,1 )それぞれに対してG4を対応付け(図9参照。)、 グリッド道路記憶手段3に記憶させる。グリ� �ド道路結合手段802は、各グリッド毎に、配� �IDとグリッドIDとを対応付けてグリッド道路� ��憶手段3に記憶させる。

 図10は、グリッドアークテーブルの例を� �す。グリッドアークテーブルは、結合処理� �割り当てたグリッドIDと、そのグリッドIDが� ��すグリッドに含まれるアークの集合とを対� ��付けた情報の集合である。図10においてT303� ��符号を付して示したグリッドIDは、結合処� �で割り当てられたグリッドIDである。アーク 集合T304は、グリッドIDによって特定されるグ リッドに対応付けられたアーク集合である。 グリッド道路結合手段802は、グリッドIDと、� ��のグリッドIDによって特定されるグリッド� �対応付けられたアーク集合との組み合わせ� �、グリッドID毎にグリッド道路記憶手段3に� �憶させる。例えば、図8に例示するように、� ��ークa1,a2を含むグリッドG(0,5)にグリッドID“ G1”を割り当てた場合、図10に示す第一レコ� �ドのように、G1と{a1,a2}とを対応付ける。

 次に、イベントグリッドマッチ手段401に� ��いて説明する。図11は、イベントグリッド� �ッチ手段401の構成例を示す説明図である。� �ベントグリッドマッチ手段401は、イベント� �憶手段40101と、処理対象記憶手段40102と、マ� ��チング処理手段40103と、グリッドイベント� �ーブル記憶手段40104とを備える。

 イベント記憶手段40101は、イベント収集� �段1が時間順にソートしたイベントデータを� ��憶するメモリを備え、メモリに記憶された� ��報を順次、処理対象記憶手段40102に記憶さ� �る。イベント記憶手段40101は、一定時間毎に メモリに記憶しているイベントデータを発生 時刻順に順次、処理対象記憶手段40102に記憶� ��せてもよい。また、イベント記憶手段40101� �、メモリに記憶しているイベントデータが� �定数に達したときにそのイベントデータを� �理対象記憶手段40102に記憶させてもよい。イ ベント記憶手段40101は、処理対象記憶手段4010 2に記憶させたデータを、イベント記憶手段40 101が備えるメモリから削除する。ここでは、 一定時間毎あるいは所定数毎にイベント記憶 手段40101に記憶されたイベントデータを処理� ��象記憶手段40102に移動させる場合を例示し� �が、他の態様でイベント記憶手段40101から処 理対象記憶手段40102にイベントデータを移動� ��せてもよい。

 処理対象記憶手段40102は、アークとのマ� �チング処理が行われるイベントデータを記� �する記憶装置である。イベント記憶手段40101 が一旦記憶したイベントデータが、順次、処 理対象記憶手段40102に記憶される。

 マッチング処理手段40103は、処理対象記� �手段40102に記憶された全てのイベントデータ と、結合処理後のグリッドとを対応付ける処 理を行い、イベントデータとグリッドとを対 応付けた情報をグリッドイベントテーブル記 憶手段40104に記憶させる。グリッドイベント� ��ーブル記憶手段40104は、マッチング処理手� �40103によるマッチング処理の結果(イベント� �ータとグリッドとを対応付けた情報の集合� �あるグリッドイベントテーブル)を記憶する� ��

 イベント収集手段1は高速マップマッチン グ手段4とは非同期にイベントデータを受信� �るために、イベント収集手段1よって発生時� ��順にソートされたイベントデータを随時追� ��する記憶手段としてイベント記憶手段40101� �、マッチング処理に用いる記憶手段である� �理対象イベント記憶手段40102とが必要となる 。よって、イベントグリッドマッチ手段401は 、イベント記憶手段40101と処理対象イベント� ��憶手段40102の2重に記憶手段を有する。

 図12は、マッチング手段40103の動作の例を 示すフローチャートである。マッチング手段 40103は、グリッドイベントテーブル記憶手段4 0104に記憶されたグリッドイベントテーブル� �クリアしてから、処理対象記憶手段40102に記 憶された各イベントデータに対して以下の処 理を行う。ここでは、イベントデータにおい て位置T103が緯度および経度で記述されるも� �とする。

 また、図13は、グリッドイベントテーブ� �の例を示す。図13において、T4010401の符号を� ��して示したグリッドIDは、結合処理で割り� �てられたグリッドIDである。イベント集合T40 10402は、グリッドIDに対応付けられるイベン� �データのイベントIDの集合である。

 マッチング手段40103は、イベントデータ� �含まれる位置T103(図2参照。)として記述され� ��緯度および経度から、以下に示す式(1)およ� ��式(2)により、イベントデータの発生位置が� ��度方向および経度方向それぞれにおいてど� ��インデックスに該当するかを判定する(ステ ップS4010301)。

 経度のインデックス=整数化((イベントの� ��度 - 原点の経度)/経度方向のグリッドのサ イズ)                 式(1)

 緯度のインデックス=整数化((イベントの� ��度 - 原点の緯度)/緯度方向のグリッドのサ イズ)                 式(2)

 なお、式(1)および式(2)における整数化と� ��、小数点以下を切り捨てて整数値にする演� ��である。また、式(1)における「イベントの� ��度」とはイベントデータに記述された経度� ��あり、「経度方向のグリッドのサイズ」は� ��路グリッド分割手段801によるグリッド分割� ��おける経度方向の分割間隔である。同様に� ��式(2)における「イベントの緯度」とはイベ� ��トデータに記述された緯度であり、「緯度� ��向のグリッドのサイズ」は道路グリッド分� ��手段801によるグリッド分割における緯度方� ��の分割間隔である。

 マッチング手段40103は、ステップS4010301で 算出した緯度および経度のインデックスを座 標とするグリッドに対応するグリッドIDを、� ��リッド道路記憶手段3に記憶された配列グリ ッドテーブルから特定する(ステップS4010302)� �この結果、イベントデータをグリッドに対� �付けることができる。

 続いて、マッチング手段40103は、ステッ� �S4010302で特定したグリッドIDの値を、グリッ� ��イベントテーブル(図13参照。)のグリッドID� ��ィールドで検索する。検索に成功した場合� ��マッチング手段40103は、グリッドイベント� �ーブルにおいて、検索されたグリッドIDのレ コードのイベント集合に処理対象としている イベントデータのイベントIDを追加する。検� ��に失敗した場合、ステップS4010302で特定し� �グリッドIDと、そのグリッドIDに対応付けた� ��ベントデータのイベントIDの組み合わせを� �グリッドイベントテーブル記憶手段40104に記 憶されているグリッドイベントテーブルに追 加する(ステップS4010303)。マッチング手段40103 は、グリッドイベントテーブルにイベントデ ータのIDを追加した場合、そのIDによって特� �されるイベントデータもあわせてグリッド� �ベントテーブル記憶手段40104に記憶させる。

 次に、イベント処理優先度判定手段402に� ��いて説明する。図14は、イベント処理優先� �判定手段402の動作の例を示すフローチャー� �である。イベント処理優先度判定手段402は� �マッチング手段40103が各イベントデータに対 してステップS4010301~S4010303の処理を行った後� ��図14に示す処理を行う。

 図15は、イベント処理優先度判定手段402� �処理により得られるグリッド優先イベント� �ーブルを示す。グリッド優先イベントテー� �ルは、グリッドイベントテーブルと同様に� �イベントデータとグリッドとを対応付けた� �報の集合である。ただし、グリッド優先イ� �ントテーブルでは、グリッドIDと、選択され た所定数以下のイベントデータが対応付けら れる。ここでは、さらに警告フラグの状態も 対応付けられる場合を例にして説明する。警 告フラグがオフ(本例では“0”とする。)であ るということは、グリッドIDに対応するイベ� ��ト集合から得られる解析結果が信頼できる� ��とを意味する。警告フラグがオン(本例では “1”とする。)であるということは、グリッ� ��IDに対応するイベントデータの数が不足し� �いて、そのイベントデータから得られる解� �結果の信頼性が低いことを意味する。

 イベント処理優先度判定手段402は、まず� ��グリッドイベントテーブル(図13参照。)のグ リッドIDフィールドから全てグリッドID(グリ� ��ドID一覧)を抽出し、抽出したグリッドIDを� �リッド優先イベントテーブルのグリッドIDと して記憶する(ステップS40201)。

 イベント処理優先度判定手段402は、ステ� ��プS40201で抽出したグリッドIDの中に、ステ� �プS40203~S40206の処理を行っていないグリッドI D(ステップS40203で選択されていないグリッドI D)が残っているか否かを判定する(ステップS40 202)。そのようなグリッドIDが残っていれば、 ステップS40203に移行し、残っていなければイ ベント処理優先度判定手段402は処理を終了す る。

 ステップS40203において、イベント処理優� ��度判定手段402は、ステップS40201で抽出した� ��リッドIDであって未だステップS40203で選択� �れていないグリッドIDを1つ選択する。イベ� �ト処理優先度判定手段402は、未選択のグリ� �ドIDの中からランダムにグリッドIDを選択し� ��もよい。また、グリッドイベントテーブル� ��記憶されている順番にグリッドIDを選択し� �もよい。ステップS40203で選択したグリッドID を、以下、注目グリッドIDと称して説明する� ��

 次に、イベント処理優先度判定手段402は� ��注目グリッドIDに対応したイベント集合を� �リッドイベントテーブルから抽出する(ステ� ��プS40204)。

 続いて、イベント処理優先度判定手段402� ��、ステップS40204でグリッドイベントテーブ� ��から抽出したイベント集合に属するイベン� ��データの数が最大イベント数よりも多けれ� ��、そのイベント集合から最大イベント数の� ��ベントデータを選択し、イベント集合に属� ��るイベントデータの数が最大イベント数以� ��であれば、そのイベント集合に属する全て� ��イベントデータを選択する(ステップS40205)� �既に説明したように、最大イベント数は、� �析精度の維持とマッチング処理の高速化を� �立するために予め定められた閾値である。� �析の際にイベントデータ数が多ければ多い� �ど解析精度は向上する。一方、イベントデ� �タ数が多いほど、イベントデータと道路と� �マッチング処理に要する時間がかかってし� �う。しかし、同じ道路を走っている車両の� �ベントデータには類似していることが多い� �そこで、1つのグリッド(結合処理後のグリッ ド)に対応するイベントデータも類似してい� �ことが多いと考えることができ、本発明で� �、1つの注目グリッドIDに対応するイベント� �ータが多く存在する場合には、その中一部� �抽出し、イベントデータが少ない場合には� �てのイベントデータを抽出することとして� �る。最大イベント数は、イベントデータが� �く存在し、その一部を抽出する閾値として� �められている。図15に示す例では、最大イベ ント数を2としているが、最大イベント数は� �ベント解析手段6で行う解析の種類に応じて� ��宜定めておけばよい。例えば、イベント解� ��手段6で渋滞度を算出する場合、最大イベン ト数は10程度が適当である。

 ステップS40204で抽出したイベント集合に� ��するイベントデータの数が最大イベント数� ��りも多い場合、イベント処理優先度判定手� ��402は、そのイベント集合の中から、最大イ� ��ント数のイベントデータを任意に選択すれ� ��よい。

 また、最小イベント数は、注目グリッドI Dに対応するイベントデータの数が不足して� �るか否かを判定するための値である。

 ステップS40205の後、イベント処理優先度� ��定手段402は、ステップS40205で選択したイベ� ��トデータを注目グリッドIDに対応付けてグ� �ッド優先イベントテーブルに追加する。す� �わち、グリッド優先イベントテーブルにお� �る注目グリッドIDに対応させて記憶させる(� �テップS40206)。このとき、イベント処理優先� ��判定手段402は、グリッドイベントテーブル� ��ら抽出したイベント集合に属するイベント� ��ータ数が最小イベント数未満であれば、注� ��グリッドIDに対応する警告フラグをオン(“1 ”)とし、イベントデータ数が最小イベント� �以上であれば警告フラグをオフ(“0”)とす� �。なお、図15では、最小イベント数を1とし� �警告フラグを常時オフとする場合を例示し� �いる。

 次に、イベント道路マッチ手段403につい� ��説明する。図16は、イベント道路マッチ手� �403の動作の例を示すフローチャートである� �イベント道路マッチ手段403は、イベント処� �優先度判定手段402によってグリッド優先イ� �ントテーブル(図15参照。)が生成された後、� ��16に示す処理を行う。イベント道路マッチ� �段403は、グリッド優先イベントテーブル(図1 5参照。)のグリッドIDフィールドから全ての� �リッドID(グリッドID一覧)を抽出して記憶す� �(ステップS40301)。

 イベント道路マッチ手段403は、ステップS 40301で抽出して記憶したグリッドIDの中に、� �テップS40303~S40310の処理を行っていないグリ� ��ドID(ステップS40303で選択されていないグリ� ��ドID)が残っているか否かを判定する(ステッ プS40302)。そのようなグリッドIDが残っていれ ば、ステップS40303に移行し、残っていなけれ ばイベント道路マッチ手段403は処理を終了す る。

 ステップS40303において、イベント道路マ� ��チ手段403は、ステップS40301で抽出して記憶� ��たグリッドIDであって未だステップS40303で� �択されていないグリッドIDを1つ選択する。� �ベント道路マッチ手段403は、未選択のグリ� �ドIDの中からランダムにグリッドIDを選択し� ��もよい。また、グリッド優先イベントテー� ��ルに記憶されている順番にグリッドIDを選� �してもよい。ステップS40303で選択したグリ� �ドIDを、以下、注目グリッドIDと称して説明� ��る。

 次に、イベント道路マッチ手段403は、グ� ��ッド優先イベントテーブル(図15参照。)から 注目グリッドIDに対応したイベント集合を抽� ��する(ステップS40304)。ステップS40304では、� �ベント道路マッチ手段403は、注目グリッドID の値でグリッド優先イベントテーブルのグリ ッドIDフィールドを検索し、検索したグリッ� ��IDフィールドに対応するイベント集合を抽� �する。例えば、注目グリッドIDが“G1”であ� ��とすると、イベント道路マッチ手段403は、� ��15に例示するグリッド優先イベントテーブ� �からイベント集合{E11,E12}を抽出する。なお� �イベント道路マッチ手段403はあらかじめイ� �ント処理優先度判定手段402のグリッド優先� �ベントテーブルへのアクセス方法を知って� �るとする。

 また、イベント道路マッチ手段403は、グ� ��ッドアークテーブル(図10参照。)から注目グ リッドに対応したアーク集合を抽出する(ス� �ップS40305)。ステップS40305では、イベント道� ��マッチ手段403は、注目グリッドIDの値でグ� �ッドアークテーブルのグリッドIDフィールド を検索し、検索したグリッドIDフィールドに� ��応するアーク集合を抽出する。例えば、注� ��グリッドIDが“G1”であるとすると、イベン ト道路マッチ手段403は、図10に例示するグリ� ��ドアークテーブルからアーク集合{a1,a2}を抽 出する。なお、イベント道路マッチ手段403は あらかじめグリッド道路記憶手段3のグリッ� �アークテーブルへのアクセス方法を知って� �るとする。また、図16では、ステップS40304の 後にステップS40305を行う場合を示しているが 、ステップS40304,S40305の実行順序はどちらが� �であってもよい。ステップS40304,S40305の処理� ��いずれも行った後にステップS40306に移行す� ��。

 イベント道路マッチ手段403は、ステップS 40305で抽出したアーク集合の要素素数が1であ るか否かを判定する(ステップS40306)。すなわ� ��、ステップS40305で抽出したアーク集合に属� ��るアークが1つであるか否かを判定する。

 アーク集合の要素が複数である場合、す� ��わちアーク集合に複数のアークがある場合( ステップS40306のno)、イベント道路マッチ手段 403は、ステップS40304で抽出したイベント集合 に属する各イベントデータ毎に、イベントデ ータの発生位置と、ステップS40305で抽出した アーク集合に属する全てのアークとの距離を 計算する(ステップS40307)。例えば、注目グリ� ��ドが“G1”である場合、イベント道路マッ� �手段403は、イベント集合{E11,E12}に属するIDが E11であるイベントデータの発生位置と、アー ク集合{a1,a2}に属する全てのアークa1,a2との距 離を算出する。同様に、IDがE12であるイベン� ��データの発生位置と、アークa1,a2との距離� �算出する。

 イベントデータの発生位置とアークとの� ��離を算出する場合、イベントデータの発生� ��置は1点でありアークは線分であるから、イ ベント道路マッチ手段403は、イベントデータ の発生位置からアークへの垂線を下ろした場 合の垂線の長さを計算すればよい。

 例えば、イベント道路マッチ手段403は、� ��下のようにしてイベントデータの発生位置� ��アークとの距離を計算すればよい。なお、� ��下の計算では経度方向の軸をx軸とし、緯度 方向の軸をy軸として、経度をx座標、緯度をy 座標とする。イベント道路マッチ手段403は、 道路ネットワーク記憶手段2のアーク情報テ� �ブル(図3参照。)にアクセスして、アークの� �点および終点となるノードのノードIDを読み 込む。さらに、イベント道路マッチ手段403は 、道路ネットワーク記憶手段2のノード情報� �ーブル(図4参照。)にアクセスして、アーク� �始点および終点のノードIDに対応付けられた 緯度および経度を読み込む。始点となるノー ドの座標を(x1,y2)とし、終点となるノードの� �標を(x2,y2)とする。x1,x2はノードの経度であ� �、y1,y2はノードの緯度である。この2つのノ� �ドを通過する直線の傾きをmとするとmは以下 の式(3)で求められる。

 m=(y1-y2)/(x1-x2)          式(3)

 また、2つのノードを通過する直線の切片 をnとするとnは以下の式(4)で求められる。

 n=-m・x1+y1                 式(4)

 さらに、イベントデータの発生位置を(x0, y0)とする。x0は、イベントデータに発生位置� ��して記述されている経度であり、y0はイベ� �トデータに発生位置として記述されている� �度である。このとき、イベントデータの発� �位置とアークとの距離をdとする距離dは、上 記の傾きmおよび切片nを用いて、以下の式(5)� ��求められる。

 d=|y0-m・x0-n|/√(1+m2)          式(5)

 よって、イベント道路マッチ手段403は、� ��ークの始点および終点の緯度、経度から式( 3)によってmを算出し、さらに式(4)によってn� �算出し、そのm,nとイベントデータの発生位� �を(x0,y0)から式(5)によって距離dを計算すれば よい。

 イベント道路マッチ手段403は、ステップS 40304で抽出したイベント集合に属する各イベ� ��トデータ毎に、ステップS40307で計算した距� ��が最短となっているアークを特定する(ステ ップS40308)。ステップS40303で、イベントデー� �の発生位置との距離が最短であると判定さ� �たアークを、イベントの関連アークと記す� �ステップS40304で抽出したイベント集合に属� �る各イベントデータ毎に、関連アークを特� �する。関連アークは、イベントデータは発� �した道路を意味する。

 また、ステップS40305で抽出したアーク集� ��の要素が1つである場合、すなわちアーク集 合に1つしかアークがない場合(ステップS40306� ��yes)、イベント道路マッチ手段403は、そのア ークを、ステップS40304で抽出したイベント集 合に属する各イベントデータの関連アークに 決定する(ステップS40309)。

 ステップS40308,ステップS40309の後、イベン ト道路マッチ手段403は、アークイベントテー ブルにイベントデータとアークとの対応関係 を示す情報を追加する(ステップS40310)。図17� �、アークイベントテーブルの例を示す説明� �である。アークイベントテーブルは、アー� �と、そのアークを関連アークとするイベン� �データの集合とを対応付けた情報の集合で� �る。ここでは、さらに警告フラグの状態も� �応付けられる場合を例にして説明する。図17 においてT501の符号を付して示したアークIDは 、ステップS40308またはステップS40309で関連ア ークとされたアークのアークIDである。また� ��イベント集合T502は、アークIDによって特定� ��れるアークを関連アークとするイベントデ� ��タの集合である。

 ステップS40310において、イベント道路マ� ��チ手段403は、ステップS40308またはステップS 40309で関連アークと定めたアークのアークID� �アークイベントテーブルのアークIDフィール ドで検索する。検索に成功した場合、イベン ト道路マッチ手段403は、そのアークを関連ア ークとするイベントデータのIDを、検索され� ��アークIDのレコードのイベント集合に追加� �る。検索に失敗した場合、イベントIDとその イベントデータの関連アークのアークIDとの� ��み合わせを新規にアークイベントテーブル� ��追加する。

 イベント道路マッチ手段403は、アークイ� ��ントテーブルをイベント道路記憶手段5に記 憶させる。ステップS40310でアークイベントテ ーブルに、アークIDや、イベント集合に属す� ��イベントデータのIDを追加する場合、イベ� �ト道路記憶手段5のアークイベントテーブル� ��追加する。イベント道路マッチ手段403は、� ��ークイベントテーブルにイベントデータのI Dを追加した場合、そのIDによって特定される イベントデータもあわせてイベント道路記憶 手段5に記憶させる。

 また、イベント道路マッチ手段403は、ア� ��クIDに対応するイベント集合の中に、グリ� �ド優先イベントテーブルで警告フラグがオ� �(“1”)となっているイベント集合と一致す� �イベント集合が存在する場合、そのアークID に対応する警告フラグをオン(“1”)とする。

 次に、イベント解析手段6について説明す る。イベント道路記憶手段5に記憶されたア� �クイベントテーブルは、道路(アーク)とその 道路で生成されたイベントデータとを対応付 けている。イベント解析手段6は、イベント� �路記憶手段5に記憶されたアークイベントテ� ��ブルを参照し、交通状況に関する解析を行� ��。イベント解析手段6は、イベント道路記憶 手段5に記憶されたアークイベントテーブル� �参照し、アークIDに対応するイベント集合を 抽出し、イベント集合に属するイベントデー タのIDによって特定されるイベントデータを� ��み込み、そのイベントデータを用いて解析� ��行えばよい。

 例えば、道路毎に渋滞度を判定する場合� ��イベント解析手段6は、アークイベントテー ブルのアークID毎にイベントデータを読み込� ��、そのイベントデータに記述された速度の� ��均値を算出し、アークID毎に平均値に応じ� �渋滞度を判定すればよい。例えば、速度の� �囲として、速度0以上V1未満の範囲、V1以上V2� ��満の範囲、V2以上の範囲を定めておき、ア� �クの平均速度が0以上V1未満であれば渋滞度� �大」と判定し、平均速度がV1以上V2未満であ� ��ば渋滞度「中」と判定し、平均速度がV2以� �であれば渋滞度「低」と判定すればよい。� �ベント解析手段6は、アーク毎に速度の平均� ��を算出し、アーク毎に渋滞度を判定する。

 また、イベント解析手段6による解析の他 の態様として、到着時間推定等が挙げられる 。イベント解析手段6は、渋滞度を判定する� �合と同様に、アークID毎にイベントデータに 記述された速度の平均値を算出する。また、 イベント解析手段6は、例えば、マップマッ� �ングシステムの管理者から車両の出発地点� �よび到着地点を指定された場合、その出発� �点から到着地点までのアークの集合を道路� �ットワーク記憶手段2に記憶されたアーク情� ��テーブルおよびノード情報テーブルから探� ��する。イベント解析手段6は、探索したアー クの集合に含まれるアーク毎に、アークの長 さ(各アークの始点および終点間の距離)を算� ��する。このとき、道路ネットワーク記憶手� ��2に記憶されたアーク情報テーブルにアクセ スして各アークIDの始点ととなるノードおよ� ��終点となるノードのノードIDを読み込み、� �路ネットワーク記憶手段2に記憶されたノー� ��情報テーブルにアクセスしてそのノードID� �対応する緯度および経度を読み込む。そし� �、始点となるノードおよび終点となるノー� �の緯度および経度を座標として二点間の距� �を算出すればよい。さらに、イベント解析� �段6は、探索したアークの集合に含まれるア� ��ク毎に、アークの長さを速度の平均値で除� ��することで車両がアークを通過する時間を� ��算し、その通過時間の和を算出する。この� ��が、指定された出発地点から到着地点まで� ��移動時間である。イベント解析手段6は、現 在時刻からこの移動時間を加えた時刻を到着 推定時刻とする。なお、出発地点から到着地 点までのアークの集合を探索する処理は、イ ベント解析手段6以外の装置が実行してもよ� �。

 また、到着時間推定において、アーク毎� ��イベントデータを2クラスにクラスタリング して、最速移動時間および最悪移動時間を算 出して、推定される移動時間に幅を持たせて もよい。イベントデータを2クラスにクラス� �リングする場合、イベント解析手段6は、例� ��ばアーク毎に速度の平均値を算出した後、� ��ベントデータを、平均値より大きい速度が� ��述されたイベントデータのクラスと、平均� ��より小さい速度が記述されたイベントデー� ��のクラスとに分類すればよい。また、K-平� �法でイベントデータを2クラスにクラスタリ� ��グしてもよい。イベント解析手段6は、平均 値より大きい速度が記述された各イベントデ ータにおける速度の平均値を算出し、その平 均値を用いて、上述の場合と同様に出発地点 から到着地点までの移動時間または到着推定 時刻を算出する。この時間が、最速移動時間 である。同様に、イベント解析手段6は、平� �値より小さい速度が記述された各イベント� �ータにおける速度の平均値を算出し、その� �均値を用いて、上述の場合と同様に出発地� �から到着地点までの移動時間または到着推� �時刻を算出する。この時間が、最悪移動時� �である。

 また、イベント解析手段6による他の解析 の態様として、移動時間の変動検出が挙げら れる。イベント解析手段6は、アーク毎に算� �した平均速度を一定時間毎の履歴として記� �装置に記憶する。この一定時間は例えば管� �者によって任意に設定される。例えば、30分 であっても1日であってもよい。イベント解� �手段6は、履歴として記憶した平均速度の平� ��値(履歴平均速度)をアーク毎に算出し、新� �にアーク毎の平均速度を算出した場合、履� �平均速度の差分を計算する。その差分が閾� �よりも大きければ、警告を解析結果出力手� �7に表示させる。

 イベント解析手段6は、解析結果を解析結 果出力手段7に出力させる。例えば、イベン� �解析手段6は、渋滞度の判定を行った場合、� ��図上に道路ネットワークを重ね合わせ、渋� ��度によって道を色分けした画像を解析結果� ��力手段7に表示させる。この表示により、管 理者が解析結果を確認する。また、イベント 解析手段6は、アークイベントテーブル(図17� �照。)において、警告フラグがオン(“1”)と� ��れているアークが存在する場合、そのアー� ��を他のアークと区別して解析結果出力手段7 に表示させる。この表示により、管理者は、 イベントデータ数が少なかったために解析結 果の信頼性が低いアーク(道路)を認識するこ� ��ができる。

 次に、マップマッチングシステム全体の� ��作について説明する。図18は、マップマッ� �ングシステム全体の動作を示す説明図であ� �。マップマッチングシステムは、グリッド� �路記憶手段3にアーク、結合処理前のグリッ� ��、結合処理後のグリッドとの対応関係を記� ��させる処理を実行する(グリッド道路生成ス テップ、ステップS1)。そして、グリッド道路 記憶手段3に記憶された情報を参照して、イ� �ント収集手段1が収集したイベントデータに� ��するマップマッチングを行って解析を行う� ��理を実行する(イベントマップマッチング解 析ステップ、ステップS2)。ステップS1は、ス� ��ップS2の前処理であり、一旦ステップS1を実 行すると、道路ネットワーク記憶手段2が記� �する道路網のデータが変更されない限り、� �度ステップS1を実行する必要はない。

 ステップS1は、グリッド道路生成手段8に� ��って実行される。ステップS2は、イベント� �集手段1、高速マップマッチング手段4、イベ ント道路記憶手段5、イベント解析手段6およ� ��解析結果出力手段7により実行される。前処 理であるステップS1を実行するグリッド道路� ��成手段8はバックエンドである。また、随時 受信するイベントデータに対して処理を行う イベント収集手段1、高速マップマッチング� �段4、イベント道路記憶手段5、イベント解析 手段6および解析結果出力手段7はフロントエ� ��ドである。グリッド道路記憶手段3は、バッ クエンドによって生成された情報を記憶する 。この情報はフロントエンドによって参照さ れる。

 図19は、ステップS1(グリッド道路生成ス� �ップ)の動作を示すフローチャートである。� ��テップS1において、道路グリッド分割手段80 1は、道路ネットワーク記憶手段2に記憶され� ��いるアーク情報テーブルおよびノード情報� ��ーブルが表す道路網の領域を、緯度方向お� ��び経度方法にそれぞれ等間隔に分割した各� ��リッドを導出する(道路グリッド分割ステッ プ、ステップS101)。ステップS101において、道 路グリッド分割手段801は、緯度方向の分割範 囲にそれぞれ0から順にインデックスを割り� �て、同様に、経度方向の分割範囲にそれぞ� �0から順にインデックスを割り当てる。さら� ��、道路グリッド分割手段801は、グリッドを� ��切るアークの集合を特定し、グリッドとア� ��クとを対応付ける。

 ステップS101の後、グリッド道路結合手段 802は、道路グリッド分割手段801によって生成 されたグリッドとアークとを対応付けたデー タに対して統合処理を行う(グリッド道路結� �ステップ、ステップS102)。その後、グリッド 道路結合手段802は、グリッド道路記憶手段3� �アーク、結合処理前のグリッド、結合処理� �のグリッドとの対応関係を記憶させる(グリ� ��ド道路記憶ステップ、ステップS103)。例え� �、グリッド道路結合手段802は、図9に例示す� ��配列グリッドテーブルおよび図10に例示す� �グリッドアークテーブルをグリッド道路記� �手段3に記憶させる。

 上記の道路グリッド分割手段801、グリッ� ��道路結合手段802の動作の詳細については既� ��説明した通りである。

 図20は、ステップS2(イベントマップマッ� �ング解析ステップ)の動作を示すフローチャ� ��トである。ステップS2は、随時受信するイ� �ントデータに対する処理であり、ステップS2 の処理が行われるときには、バックエンドで あるグリッド道路生成手段8は動作せず、フ� �ントエンドのみが動作する。

 ステップS2において、イベント収集手段1� ��、車両が生成したイベントデータを、基地� ��を介して受信する(イベント収集ステップ、 ステップS201)。車両は多数存在し、イベント� ��集手段1は、各車両が送信するイベントデー タを受信する。

 イベントグリッドマッチ手段401は、イベ� ��ト収集手段1が受信したイベントデータと、 結合処理後のグリッドとを対応付け、結合処 理後のグリッド毎に対応するイベントデータ の集合を特定する(イベントグリッドマッチ� �テップ、ステップS202)。すなわち、グリッド イベントテーブル(図13参照。)を導出する。

 続いて、イベント処理優先度判定手段402� ��、結合処理後のグリッドに対応付けられた� ��ベントデータの数が最大イベント数より多� ��れば、そのイベントデータから最大イベン� ��数のイベントデータを抽出し、結合処理後� ��グリッドに対応付けられたイベントデータ� ��数が最大イベント数以下であればそのグリ� ��ドに対応付けられたイベントデータを全て� ��出する(イベントデータ抽出ステップ、ステ ップS203)。

 イベント道路マッチ手段403は、ステップS 203で抽出された全てのイベントデータに対し 、イベントデータに対応付けられたグリッド 内の道路とイベントデータの発生位置との距 離計算を行い、イベントデータがどの道路を 走行している車両で生成されたのかを特定す る(イベント道路マッチステップ、ステップS2 04)。すなわち、アークイベントテーブル(図17 参照。)を導出する。

 続いて、イベント解析手段6は、アークイ ベントテーブルを参照し、道路毎に対応付け られたイベントデータに基づいて、道路の渋 滞度の判定等の解析を行う(イベント解析ス� �ップ、ステップS205)。イベント解析手段6に� �る解析の種類は特に限定されない。

 本発明によれば、道路グリッド分割手段8 01が、道路網が存在する領域を緯度方向およ� ��経度方法にそれぞれ等間隔に分割したグリ� ��ドを導出し、グリッド道路結合手段802が、� ��いに隣接するグリッドであってグリッドに� ��応付けられている道路の集合が一致する複� ��のグリッドに対して同一のグリッドIDを割� �当てる。そして、アークイベントテーブル� �導出する際には、結合処理後のグリッドID毎 に処理を行う。このように結合処理を行うこ とで処理量を少なくすることができ、イベン トデータとアークとを対応付ける処理を高速 に行うことができる。具体的には、グリッド 道路結合手段802が結合処理を行うことで、図 16に示すステップS40302から始まるループ処理� ��繰り返し回数が少なくてすむので、アーク� ��ベントテーブルを導出する処理を高速に行� ��ことができる。

 また、同じ道路を走っている車両のイベ� ��トデータには類似していることが多い。そ� ��ため、グリッド道路結合手段802が結合処理� ��行うことで、道路の集合が一致する範囲を� ��とめ、その範囲に対応するイベントデータ� ��特定すれば、類似するイベントデータを道� ��の集合が一致する範囲に数多く対応付ける� ��とができる。そして、そのようなイベント� ��ータが閾値(最大イベント数)以上存在する� �合には、そのイベントデータの一部を抽出� �て道路との対応付けを行い、その上で解析� �行っても解析精度は維持でき、かつ、処理� �荷を減らして処理の高速化を実現すること� �できる。具体的には、ステップS40307,S40308,S40 309(図16参照。)の処理量を減らして、アーク� �ベントテーブルを導出する処理を高速に行� �ことができる。

 また、本発明では、フロントエンド(イベ ント収集手段1、高速マップマッチング手段4� ��イベント道路記憶手段5、イベント解析手段 6および解析結果出力手段7)は、バックエンド (グリッド道路生成手段8)による前処理とは独 立に動作する。従って、前処理での処理量の 多寡によらず、フロントエンドは上述のよう に高速に処理を行うことができる。

 イベントデータの収集対象とする道路網� ��広げたとしても、また、イベントデータを� ��信する車両の数が増大したとしても、本発� ��は、上記のように高速に処理を行うことが� ��きる。すなわち、本発明は、イベントデー� ��の収集対象とする道路網の広さや車両の数� ��対してスケーラビリティがある。

 また、イベント道路マッチ手段403の処理� ��果を用いた解析目的は限定されないので、� ��用的な解析に利用することができる。

 以上のように本発明によれば、イベント� ��ータと道路とを対応付けたアークイベント� ��ーブルを高速に導出することができる。ま� ��、本発明に適用されるイベントデータは、I D、イベントデータの発生日時、発生位置、� �よび発生時の車両の速度を含んでいるので� �渋滞度の判定、到着時間の推定、移動時間� �変動検出等の多様な解析を行うことができ� �。

 また、本発明では、アークとして道路ネ� ��トワーク記憶手段に記憶させる道路は、主� ��な道路に限定されずに、細かな道路もアー� ��として定めることができる。従って、道路� ��種類を区別することなく、主要な道路だけ� ��なく細かな道路で生成されたイベントデー� ��に対してもアークとの対応付けを行って、� ��析対象とすることができる。

 上記の説明では、結合処理後のグリッド� ��対応付けられたイベントデータの数が最小� ��ベント数未満であれば警告フラグをオンと� ��る処理を行う場合を示したが、グリッドに� ��応付けられたイベントデータの数と最小イ� ��ント数との比較を行わなくてもよい。すな� ��ち、本発明において最小イベント数が定め� ��れていなくてもよい。この場合、警告フラ� ��を用いない。従って、イベント解析手段6が 解析結果出力手段7に解析結果を表示させる� �合、警告フラグに基づいて道路を区別して� �示することはない。

 また、イベントデータに車両の進行方向� ��含まれている場合、イベント道路マッチ手� ��403は、アークイベントテーブルを作成する� ��に、各アークに「上り」および「下り」の� ��性を付加し、イベントデータと、アークの� ��上り」または「下り」のいずれか一方に対� ��付けてもよい。1つのアークに対応付けられ るイベントデータに記述される方向は、互い に逆向きとなる2方向のうちのいずれか一方� �ある。イベントデータに記述されている方� �がその2方向のうちの一方であれば、例えば� ��アークの「上り」に対応付ければよい。ま� ��、その逆方向が記述されたイベントデータ� ��、アークの「下り」に対応付ければよい。� ��21は、各アークの「上り」および「下り」� �属性毎にイベントデータを対応付けたアー� �イベントテーブルの例である。なお、図21で は、警告フラグフィールドを省略している。 また、このようにアークイベントテーブルを 導出する場合、ステップS40205(図14参照。)に� �いて、最大イベント数よりも多くのイベン� �データの中から最大イベント数のイベント� �ータを選択する際に、一方の方向が記述さ� �たイベントデータの数と、その逆方向が記� �されたイベントデータの数ができるだけ近� �なるようにイベントデータを選択すること� �好ましい。あるいは、既に説明した場合と� �様に、任意にイベントデータを選択しても� �い。また、図21に例示するアークイベントデ ータが生成されている場合、イベント解析手 段6は、アークの「上り」と「下り」に関し� �それぞれ別々に解析を行う。

 また、イベントデータにワイパー利用状� ��が含まれている場合、イベント解析手段6は 、道路付近の降雨の有無を判定してもよい。 すなわち、アークIDに対応するイベントデー� ��のうち、ワイパー利用状況において“使用� ��”を意味する記述がされているイベントデ� ��タが所定数以上存在する場合、そのアーク� ��辺では雨が降っていると判定してもよい。

 同様に、イベントデータにブレーキ利用� ��況が含まれている場合、イベント解析手段6 は、ブレーキ利用状況に基づく渋滞度判定を 行ってもよい。すなわち、アークIDに対応す� ��イベントデータのうち、ブレーキ利用状況� ��おいて“使用中”を意味する記述がされて� ��るイベントデータが所定数以上存在する場� ��、そのアークが渋滞中であると判定しても� ��い。また、渋滞中と判定する代わりに、事� ��が発生した可能性があると判定してもよい� ��

実施の形態2.
 図22は、本発明の第2の実施の形態の例を示� ��ブロック図である。第1の実施の形態と同様 の構成部については、図1と同一の符号を付� �説明を省略する。第2の実施の形態のマップ� ��ッピングシステムは、マッチング精度評価� ��段9を有するマッチング精度評価装置105を備 える。マッチング精度評価手段9は、グリッ� �に対応付けられたアークの数に応じて、最� �イベント数および最小イベント数をグリッ� �毎に決定する。

 マッチング精度評価手段9は、例えば、プ ログラムに従って動作するCPUによって実現さ れる。

 また、マッチング精度評価手段9は、マッ プマッチング装置101あるいは道路データ生成 装置103に設けられていてもよい。マッチング 精度評価手段9がマップマッチング装置101に� �けられる場合、マッチング精度評価手段9と� ��速マップマッチング手段4は、マップマッピ ングプログラムに従って動作する同一のCPUに よって実現される。また、道路データ記憶装 置102、道路ネットワーク記憶装置104およびマ ッチング精度評価装置105が同一の装置で実現 されていてもよい。また、各手段が全て同一 の装置に設けられる構成であってもよい。こ のように、第2の実施の形態のマップマッピ� �グシステムの構成は、図22に示す構成に限定 されるわけでない。

 マッチング精度評価手段9は、グリッド道 路結合手段802によってグリッド道路記憶手段 3に記憶されたグリッドアークテーブルを参� �する。そして、マッチング精度評価手段9は� ��グリッドに対応付けられたアークの数に応� ��て最大イベント数および最小イベント数を� ��定する。マッチング精度評価手段9は、この 処理をグリッド毎に行う。

 マッチング精度評価手段9は、グリッドア ークテーブルにおける各グリッドID毎に、ア� ��ク数が多いほど、「最小イベント数」<「 最大イベント数」を満足しつつ、最小イベン ト数および最大イベント数をより大きな値と して決定する。例えば、マッチング精度評価 手段9は、最小イベント数をアークの数と同� �とし、最大イベント数をアークの数の2倍と� ��て定めてもよい。ただし、この最小イベン� ��数および最大イベント数の計算は一例であ� ��、他の計算によってグリッドID毎に最小イ� �ント数および最大イベント数を決定しても� �い。最小イベント数および最大イベント数� �計算は、グリッド(結合処理後のグリッド)に 対応するアーク数が多いほど最小イベント数 および最大イベント数を大きな値に定め、か つ、「最小イベント数」<「最大イベント� �」を満足する計算であればよい。

 マッチング精度評価手段9は、グリッドID� ��に定めた最小イベント数および最大イベン� ��数をグリッドIDに対応付けてグリッド道路� �憶手段3に記憶させる。例えば、グリッドア� ��クテーブルに最小イベント数および最大イ� ��ント数を追加する。図23は、最小イベント� �および最大イベント数を追加したグリッド� �ークテーブルの例を示す。図23に示すグリッ ドIDおよびアーク集合は、第1の実施の形態で 説明したグリッドアークテーブル(図10参照。 )と同様である。精度評価値T305は、最小イベ� ��ト数および最大イベント数を示す。図23で� �、最小イベント数および最大イベント数を� �(最小イベント数,最大イベント数)”という� �ォーマットで記述する場合を例示している� �、最小イベント数および最大イベント数を� �述するフォーマットは、他のフォーマット� �もよい。

 また、イベント処理優先度判定手段402は� ��ステップS40205(図14参照。)の処理を行う前に 、グリッド道路記憶手段3にアクセスして、� �目グリッドIDに対応する最小イベント数およ び最大イベント数を読み込む。そして、その 最大イベント数を用いてステップS40205の処理 を行う。また、イベント処理優先度判定手段 402は、警告フラグをオンとするか否かを、そ の最小イベント数を用いて判定する。

 その他の動作については、第1の実施の形 態と同様である。

 一般に、アークの数が多いほど、解析に� ��要なイベントデータの数が多く必要である� ��考えられる。本実施の形態では、グリッド� ��対応するアーク数が多いほど最小イベント� ��、最大イベント数を大きな値に定めるので� ��より高精度にイベントデータを解析するこ� ��ができる。

実施の形態3.
 図24は、本発明の第3の実施の形態の例を示� ��ブロック図である。第1の実施の形態、第2� �実施形態と同様の構成部については、図1、� ��22と同一の符号を付し説明を省略する。た� �し、本実施の形態では、マッチング精度評� �手段9の動作が、第2の実施の形態とは異なる 。なお、マッチング精度評価手段9を備える� �ッチング精度評価装置105は、他の装置とは� �個の装置でなくてもよい。この点は、第2の� ��施の形態と同様である。例えば、マッチン� ��精度評価手段9は、マップマッチング装置101 に設けられていてもよい。この場合、マッチ ング精度評価手段9と高速マップマッチング� �段4は、マップマッピングプログラムに従っ� ��動作する同一のCPUによって実現される。

 本実施の形態のグリッド道路結合手段802� ��、結合処理後のグリッドにおいて、他のグ� ��ッドとの境界となる各辺の両端点の緯度お� ��び経度もグリッドIDとともにグリッドアー� �テーブルに含める。

 本実施の形態のマッチング精度評価手段9 は、グリッド内を通過するアークの長さの総 和に応じて最大イベント数および最小イベン ト数をグリッド毎に決定する。この動作は、 例えば、以下に示すように行えばよい。マッ チング精度評価手段9は、グリッドアークテ� �ブルを参照して、1つのグリッドIDを選択し� �そのグリッドIDに対応する各アークIDを読み� ��む。そして、そのグリッドIDに対応する配� �IDを配列グリッドテーブルから読み込む。さ らに、マッチング精度評価手段9は、グリッ� �IDに対応する各アークの始点または終点とな るノードであって、グリッドIDが示すグリッ� ��内に属するノードを検索する。グリッドID� �対応する各アークの始点または終点となる� �ードは、道路ネットワーク記憶手段2に記憶� ��れるアーク情報テーブル(図3参照。)にアク� ��スして特定する。また、そのノード緯度お� ��び経度は、道路ネットワーク記憶手段2に記 憶されるノード情報テーブル(図4参照。)にア クセスして特定する。

 式(1)、式(2)におけるイベントの経度およ� ��イベントの緯度を、アークの始点または終� ��のノードの緯度、経度に置き換え、式(1)、� ��(2)と同様の計算を行う。この結果得られた� ��経度のインデックスおよび経度のインデッ� ��スの組み合わせが、選択したグリッドIDに� �応する配列IDと一致すれば、そのノードは、 グリッドIDに対応する各アークの始点または� ��点となるノードであって、グリッドIDが示� �グリッド内に属するノードであると判定す� �。

 マッチング精度評価手段9は、検索したノ ードを始点または終点とする各アークの両端 点の緯度および経度と、選択したグリッドID� ��示すグリッドの辺の両端点の緯度および経� ��を用いて、検索したノードから伸びるアー� ��と、選択したグリッドIDが示すグリッドの� �との交点の緯度および経度を求める。図25は 、選択したグリッドIDが示すグリッド内で検� ��したノードおよびそのノードから伸びるア� ��クの例を示す説明図である。図25に示すノ� �ドn2は、グリッドIDに対応する各アークの始� ��または終点となるノードであって、グリッ� ��IDが示すグリッド内に属するノードとして� �索されたノードである。ここでは、グリッ� �IDとしてG1を選択した場合を例示している。� ��ッチング精度評価手段9は、ノードn2を始点� ��たは終点とするアークa1の両端点の緯度お� �び経度を道路ネットワーク記憶手段2から読� ��込む。マッチング精度評価手段9は、グリッ ドIDが示すグリッドの辺g1の両端点の緯度お� �び経度をグリッドアークテーブル読み込み� �アークa1と辺g1の交点の緯度および経度を算� ��する。マッチング精度評価手段9は、アーク a1の両端点の緯度および経度から、アークa1� �含む直線の方程式を計算し、同様に、辺g1の 両端点の緯度および経度から、辺g1を含む直� ��の方程式を計算し、その2直線の交点として 、a1とg1の交点の緯度および経度を計算すれ� �よい。そして、マッチング精度評価手段9は� ��その交点とノードn2との距離p1を計算する。 マッチング精度評価手段9は、n2から伸びる他 のアークa2についても、アークa2および辺g2の 交点とn2との距離p2を求める。このように求� �たノードn2と、ノードn2から伸びるアークと� ��との交点との距離の和を計算することで、� ��リッド内を通過するアークの長さの総和を� ��める。

 マッチング精度評価手段9は、グリッドア ークテーブルを参照して、個々のグリッドID� ��順に選択し、グリッドID毎に上記の処理を� �う。

 マッチング精度評価手段9は、グリッド内 を通過するアークの長さの総和を求めたなら ば、グリッド内のアークの長さの総和に応じ て、最大イベント数および最小イベント数を 決定する。この決定もグリッド毎に行う。

 マッチング精度評価手段9は、グリッド内 を通過するアークの長さの総和が大きいほど 、「最小イベント数」<「最大イベント数� �を満足しつつ、最小イベント数および最大� �ベント数をより大きな値として決定する。� �えば、アークの長さの総和に比例した値と� �て、グリッドID毎に最小イベント数および最 大イベント数を決定してもよい。ただし、こ の最小イベント数および最大イベント数の計 算は一例であり、他の計算によってグリッド ID毎に最小イベント数および最大イベント数� ��決定してもよい。最小イベント数および最� ��イベント数の計算は、グリッド(結合処理後 のグリッド)を通過するアークの長さの総和� �大きいほど、最小イベント数および最大イ� �ント数を大きな値に定め、かつ、「最小イ� �ント数」<「最大イベント数」を満足する� ��算であればよい。

 マッチング精度評価手段9は、第2の実施� �形態と同様に、グリッドアークテーブルに� �小イベント数および最大イベント数を追加� �る。また、イベント処理優先度判定手段402� �動作は、第2の実施の形態と同様である。す� ��わち、ステップS40205(図14参照。)の処理を行 う前に、グリッド道路記憶手段3にアクセス� �て、注目グリッドIDに対応する最小イベント 数および最大イベント数を読み込む。そして 、その最大イベント数を用いてステップS40205 の処理を行う。警告フラグをオンとするか否 かの判定も、その最小イベント数を用いて行 う。

 グリッド内を通過するアークの長さが長� ��ほど、解析に必要なイベントデータの数が� ��く必要であると考えられる。よって、本実� ��の形態では、アークの長さの総和が大きい� ��ど最小イベント数、最大イベント数を大き� ��値に定めるので、より高精度にイベントデ� ��タを解析することができる。

実施の形態4.
 図26は、本発明の第4の実施の形態の例を示� ��ブロック図である。第1の実施の形態、第2� �実施形態と同様の構成部については、図1、� ��22と同一の符号を付し説明を省略する。た� �し、本実施の形態では、マッチング精度評� �手段9の動作が、第2の実施の形態とは異なる 。以下、第4の実施の形態では、イベント解� �手段6が、渋滞度の判定等ように、イベント� ��ータに含まれる速度を用いた解析を行うも� ��とする。

 本実施の形態では、マッチング精度評価� ��段9はマップマッチング装置101に設けられる ことが好ましいが、他の装置に設けられてい てもよい。マッチング精度評価手段9がマッ� �マッチング装置101に設けられる場合、マッ� �ング精度評価手段9と高速マップマッチング� ��段4とイベント分布手段10は、マップマッピ� ��グプログラムに従って動作する同一のCPUに� ��って実現される。

 本実施の形態のマップマッチング装置101� ��、イベント分布手段10を備える。イベント� �布手段10は、イベントグリッドマッチ手段401 が記憶するグリッドイベントテーブルを参照 し、グリッド毎に、グリッドに対応するイベ ントデータに記述された速度のばらつきの度 合いを示す値を計算する。ばらつきを示す値 の例として例えば分散があるが、ばらつきを 示す値として最大値と最小値の差を用いても よい。以下、イベント分布手段10は、グリッ� ��毎に、グリッドに対応するイベントデータ� ��記述された速度の分散を計算する場合を例� ��して説明する。

 例えば、図13に例示するグリッドイベン� �テーブルが生成された場合、イベント分布� �段10は、グリッドID“G1”に対応するIDの集合 {E1,E2,E3,E4,E5}によって特定されるイベントデ� �タの速度の分散を計算する。イベント分布� �段10は、同様に他のグリッドIDに関しても、� ��ベントデータに記述された速度の分散を計� ��する。

 マッチング精度評価手段9は、イベント分 布手段10によって計算されたグリッドID毎の� �散値に応じて、各グリッドID毎の最大イベン ト数および最小イベント数を決定する。マッ チング精度評価手段9は、分散値が大きいほ� �、「最小イベント数」<「最大イベント数� ��を満足しつつ、最小イベント数および最大� ��ベント数をより大きな値として決定する。� ��えば、分散値に比例した値として、グリッ� ��ID毎に最小イベント数および最大イベント� �を決定してもよい。ただし、この最小イベ� �ト数および最大イベント数の計算は一例で� �り、他の計算によってグリッドID毎に最小イ ベント数および最大イベント数を決定しても よい。最小イベント数および最大イベント数 の計算は、分散が大きいほど、最小イベント 数および最大イベント数を大きな値に定め、 かつ、「最小イベント数」<「最大イベン� �数」を満足する計算であればよい。

 マッチング精度評価手段9は、第2の実施� �形態と同様に、グリッドID毎に定めた最小イ ベント数および最大イベント数をグリッドID� ��対応付けてグリッド道路記憶手段3に記憶さ せる。イベント処理優先度判定手段402と同様 に動作する。

 また、上記の説明では、速度の分散を用� ��る場合を例に説明したが、速度と最大値と� ��小値との差のように、速度のばらつき度合� ��を示す値であれば分散以外の値を用いても� ��い。また、ここでは、イベント解析手段6が 速度を用いて解析を行い、速度のばらつき度 合いに応じて最大イベント数および最小イベ ント数を計算する場合を例に説明したが、計 算の対象は速度に限定されず、イベント解析 手段6が解析に用いるデータであればよい。

 解析に用いられる値のばらつきが大きい� ��ど、解析に必要なイベントデータの数が多� ��必要であると考えられる。よって、本実施� ��形態でも、精度の低下を抑えながら高速に� ��ップマッチングを行うことができ、より高� ��度にイベントデータを解析することができ� ��。

実施の形態5.
 図27は、本発明の第5の実施の形態の例を示� ��ブロック図である。第1の実施の形態、第4� �実施形態と同様の構成部については、図1、� ��26と同一の符号を付し説明を省略する。た� �し、本実施の形態では、マッチング精度評� �手段9の動作が、第4の実施の形態とは異なる 。本実施の形態においても、マッチング精度 評価手段9はマップマッチング装置101に設け� �れることが好ましいが、他の装置に設けら� �ていてもよい。マッチング精度評価手段9は� ��ップマッチング装置101に設けられる場合、� ��ッチング精度評価手段9と高速マップマッチ ング手段4と負荷情報記憶手段11は、マップマ ッピングプログラムに従って動作する同一の CPUによって実現される。

 また、本実施の形態では、図23に示すよ� �にグリッドアークテーブルにおいて、グリ� �ドID毎に最小イベント数および最大イベント 数が対応付けられているものとする。

 本実施の形態のマッチング精度評価手段9 は、高速マップマッチング手段4として動作� �るコンピュータの負荷状況に応じて、グリ� �ド毎に定められている最大イベント数を変� �させる。

 本実施の形態のマップマッチング装置101� ��、負荷情報記憶手段11を備える。負荷情報� �憶手段11は、高速マップマッチング手段4と� �て動作するコンピュータ(図27に示す例では� �ップマッチング装置101)の負荷状況を監視す� ��。また、負荷情報記憶手段11は、コンピュ� �タの負荷状況と、単位時間(ここでは1秒とす る。)当たりに解析可能なイベントデータの� �大数との関係を示すイベント処理能力テー� �ルを記憶する。図28は、イベント処理能力テ ーブルの例を示す。単位時間当たり解析可能 なイベントデータの最大数(以下、最大イベ� �ト処理数と記す。)とは、イベント収集手段1 がイベントグリッドマッチ手段401にイベント データ入力してから、イベント解析手段6が� �ベントデータに対する解析結果を解析結果� �力手段7に出力させるまでの動作を単位時間� ��に可能とするイベントデータの最大数であ� ��。

 図27に示す負荷T1101は、高速マップマッチ ング手段4として動作するコンピュータの負� �の段階を示す。図27に示す例では、コンピュ ータの負荷の段階を0以上10未満の値で表して いる。

 図27に示す最大イベント処理数T1102は、1� �当たりに解析可能なイベントデータの最大� �である。図27に示す例では、コンピュータの 負荷が6以上10未満である場合、最大イベント 処理数は3000である。従って、例えば、コン� �ュータの負荷が6.2である場合、1秒当たりに� ��イベント収集手段1がイベントグリッドマッ チ手段401に最大3000個のイベントデータを入� �し、イベント解析手段6がそのイベントデー� ��に対する解析結果を解析結果出力手段7に出 力させることができる。最大イベント処理数 T1102は、負荷が低いほど大きな値で定められ� ��。

 負荷情報記憶手段11は、OSに従って動作す るコンピュータ自身から負荷状況を取得し、 イベント処理能力テーブルを参照して、負荷 状況に応じた最大イベント処理数を特定する 。

 マッチング精度評価手段9は、負荷情報記 憶手段11によって特定された最大イベント処� ��数に応じて、グリッドアークテーブル内の� ��大イベント数を変化させる。例えば、マッ� ��ング精度評価手段9は、負荷情報記憶手段11� ��よって特定された最大イベント処理数を、� ��ークの総数で除算した値を求める。この値� ��、1アーク当たりの最大イベント処理数と記 す。マッチング精度評価手段9は、図23に例示 するグリッドアークテーブルを参照して、グ リッドIDに対応するアークの数と1アーク当た りの最大イベント処理数との積よりも、既に 定められている最大イベント数の方が大きけ れば、その最大イベント数を、算出した積の 値以下の最大の整数に修正する。また、グリ ッドIDに対応するアークの数と、1アーク当た りの最大イベント処理数との積が、予め定め られていた最大イベント数以上であれば、最 大イベント処理数を、予め定められていた最 大イベント数に戻す。

 例えば、コンピュータの負荷が6.2であり� ��イベントグリッドマッチ手段401によって、� ��大イベント処理数が3000であると判定された とする。また、アークの総数が2000本である� �する。マッチング精度評価手段9は、例えば� ��路ネットワーク記憶手段2に記憶されたアー ク情報テーブルにおけるアークIDの数をカウ� ��トしてアークの総数を求めればよい。本例� ��場合、マッチング精度評価手段9は、アーク 当たりの最大イベント処理数を3000/2000=1.5と� �て算出する。

 図29は、グリッドアークテーブルにおけ� �最大イベント数を修正する動作の例を示す� �明図である。上記のように、アーク当たり� �最大イベント処理数が1.5として算出された� �する。マッチング精度評価手段9は、グリッ� ��ID“G1”では、対応するアークがa1,a2の2本で あるので、最大イベント処理数とアーク数2� �の積を求める。この場合、1.5×2=3となる。グ リッドID“G1”に対応する最大イベント数6は� ��算結果“3”よりも大きい。従って、マッチ ング精度評価手段9は、最大イベント数“6”� ��計算結果“3”以下の最大の整数(ここでは3) に変更する(図29に示す第1レコードを参照。)� ��

 マッチング精度評価手段9は、他のグリッ ドIDに関しても同様の処理を行う。

 イベント処理優先度判定手段402は、第2の 実施の形態と同様にグリッドアークテーブル が示す最大イベント数を読み込み、ステップ S40205(図14参照。)の処理を行う。イベント処� �優先度判定手段402の動作は、第2の実施の形� ��と同様である。

 本実施の形態によれば、コンピュータの� ��荷状況に応じてマップマッチングの処理速� ��や解析精度を制御できる。具体的には、コ� ��ピュータの負荷が大きい場合に、ステップS 40205(図14参照。)で選択するイベントデータの 数を減らして、コンピュータの処理負荷を上 げないようにすることができる。また、コン ピュータの負荷が小さい場合には、ステップ S40205で選択するイベントデータの数を減らし て解析精度を上げることができる。

実施の形態6.
 図30は、本発明の第6の実施の形態の例を示� ��ブロック図である。第1の実施の形態、第4� �実施形態と同様の構成部については、図1、� ��26と同一の符号を付し説明を省略する。た� �し、本実施の形態では、マッチング精度評� �手段9の動作が、第4の実施の形態とは異なる 。本実施の形態においても、マッチング精度 評価手段9はマップマッチング装置101に設け� �れることが好ましいが、他の装置に設けら� �ていてもよい。マッチング精度評価手段9が� ��ップマッチング装置101に設けられる場合、� ��ッチング精度評価手段9と高速マップマッチ ング手段4と処理遅延監視手段12は、マップマ ッピングプログラムに従って動作する同一の CPUによって実現される。

 また、本実施の形態でも、第5の実施の形 態と同様に、図23に示すようにグリッドアー� ��テーブルにおいて、グリッドID毎に最小イ� �ント数および最大イベント数が対応付けら� �ているものとする。

 本実施の形態のマッチング精度評価手段9 は、イベント収集手段1がイベント記憶手段40 101に記憶させたイベントデータの数(換言す� �ば、イベント収集手段1が受信したイベント� ��ータの数)が増加しているか減少しているか によって、グリッド毎に定められている最大 イベント数、最小イベント数を変化させる。

 本実施の形態のマップマッチング装置101� ��、処理遅延監視手段12を備える。処理遅延� �視手段12は、イベント記憶手段40101に記憶さ� ��ているイベントデータの総数を定期的にカ� ��ントし、イベント記憶手段40101に記憶され� �いるイベントデータの総数が増加傾向にあ� �のか減少傾向にあるのかを判定する。処理� �延監視手段12は、一定期間毎にイベントデー タの数をカウントし、カウント結果から1つ� �のカウント結果を減じた差分が正であるこ� �が連続している場合に増加傾向であると判� �し、その差分が負であることが連続してい� �場合に減少傾向であると判定する。例えば� �処理遅延監視手段12は、イベント記憶手段401 01に記憶されているイベントデータの総数を1 分単位にカウントして記憶するとともに、過 去10分間のカウント結果をそれぞれ参照する� ��処理遅延監視手段12は、過去10分間分のそれ ぞれのカウント結果から、その1つ前のカウ� �ト結果を減算した差分をそれぞれ求める。� �の差分が全て正であれば、イベント記憶手� �40101に記憶されているイベントデータの総数 が増加傾向であると判定する。また、この差 分が全て負であれば、イベント記憶手段40101� ��記憶されているイベントデータの総数が減� ��傾向であると判定する。ただし、ここで示� ��た判定は例示であり、処理遅延監視手段12� �他の態様で増加傾向か減少傾向かを判定し� �もよい。例えば、より細かく加減の傾向を� �ベル分けしてもよい。

 図31は、マッチング精度評価手段9が、イ� ��ントデータの加減の傾向に応じて最大イベ� ��ト数と最小イベント数を変化させる動作の� ��を示す説明図である。マッチング精度評価� ��段9は、ベント記憶手段40101に記憶されてい� ��イベントデータの数が増加傾向であると判� ��された場合、各グリッドIDに対応する各最� �イベント数を減少させる。このとき、各グ� �ッドIDに対応する各最小イベント数もあわせ て変化させてもよい。また、マッチング精度 評価手段9は、ベント記憶手段40101に記憶され ているイベントデータの数が減少傾向である と判定された場合、各グリッドIDに対応する� ��最小イベント数を増加させる。このとき、� ��グリッドIDに対応する各最大イベント数も� �わせて変化させてもよい。

 図31に示す第1レコードを例に説明すると� ��イベントデータ数が増加傾向にある場合、� ��大イベント数を減少させて、精度評価値を( 2,6)から(2,5)に変化させている。また、イベン トデータ数が減少傾向にある場合、最小イベ ント数を増加させて、精度評価値を(2,6)から( 3,6)に変化させている。

 イベント処理優先度判定手段402の動作は� ��第2の実施の形態と同様である。

 第6の実施の形態によれば、イベント収集 手段1がイベント記憶手段40101に機多くさせる イベントデータ数の増減に応じて、解析精度 を制御することができる。

 既に説明したように、本発明において最� ��イベント数が定められていなくてもよい。� ��の場合、第2から第6までの各実施の形態で� �、最大イベント数のみを制御すればよい。

 また、第2、第3、第4、第6の各実施の形態 では、最小イベント数および最大イベント数 を変化させ、第5の実施の形態では、最大イ� �ント数のみ変化させている。本発明のマッ� �マッピングシステムは、イベントデータ等� �状況に応じて、最小イベント数のみを変化� �せてもよい。

 上述した本発明の実施の形態によれば、� ��リッド道路結合手段が、互いに隣接してい� ��対応付けられているアークの集合が一致す� ��複数のグリッドに対して共通のアークIDを� �り当て、対応付けられているアークの集合� �隣接するいずれのグリッドとも異なるグリ� �ドに対してアークIDを割り当て、道路グリッ ド分割手段によって導出されたグリッドの範 囲とグリッドIDとグリッドを通過するアーク� ��の関係を示す情報を記憶装置に記憶させ、� ��ベントデータ選択手段が、イベントデータ� ��対応付けられたグリッドID毎に、対応付け� �れたイベントデータの数が閾値よりも多け� �ばその閾値の数のイベントデータを選択し� �対応付けられたイベントデータの数が閾値� �下であれば対応付けられたイベントデータ� �全て選択する。従って、イベントID毎に行う 処理の処理量を削減し、また、イベントデー タ毎に行われるイベント道路マッチ手段の処 理量を削減することができる。よって、処理 を高速化することができる。

 また、同じ道路を走っている車両のイベ� ��トデータには類似していることが多いので� ��グリッドIDに対応付けられたイベントデー� �の中から閾値の数のイベントデータを選択� �たとしても、解析の精度を維持することが� �きる。従って、大量の車両からイベントデ� �タが送信される場合であっても、マップマ� �チング結果に基づく解析の精度を落とさな� �ようにしつつ高速にマップマッチングを行� �ことができる。また、イベント道路マッチ� �段によってアークが特定されたイベントデ� �タとそのアークとの対応関係を示す情報の� �用目的は限定されないので、種々の解析に� �用的に利用することができる。

 以上好ましい実施の形態(及び実施例)を� �照して本願発明を説明したが、本願発明は� �記実施の形態(及び実施例)に限定されるもの でない。本願発明の構成や詳細には、本願発 明のスコープ内で当業者が理解し得る様々な 変更をすることができる。

 この出願は、2007年3月27日に出願された日 本出願特願2007-082632を基礎とする優先権を主� ��し、その開示の全てをここに取り込む。