(57)【要約】【課題】マップマッチングの対象道路に該当する頻度に偏りを有する道路網に対して、高速処理できるマップマッチング方法を提供する。【解決手段】道路網データから抽出された一部の道路網データを用いてマップマッチングを行い、対象道路の候補道路Ｒを取得する。この一部の道路網データに含まれていない、候補道路Ｒに並走する類似形状の道路ｒが存在するときは、道路網データで規定された、候補道路Ｒが関係する判定距離Ｄ／２と、マップマッチングでのウエイポイント（黒丸）から候補道路Ｒまでの差分距離とを比較して、候補道路Ｒを対象道路とすべきか否かを判定する。多くの場合、優先順位の高い一部の道路網データを用いたマップマッチングで対象道路を特定することが可能でる。また、候補道路Ｒと形状が類似する道路ｒが、下位層の道路網に存在する場合でも、判定距離を用いて、候補道路Ｒの採用の是非を迅速に判断できる。【選択図】      図１
2004264203.tif 000002
【特許請求の範囲】
【請求項１】
道路網データから抽出された一部の道路網データを用いてマップマッチングを行い、対象道路の候補道路を取得する処理と、前記一部の道路網データに含まれていない、前記候補道路に並走する類似形状の並走類似形状道路が存在するときに、前記一部の道路網データで規定された、前記候補道路が関係する判定距離と、前記マップマッチングでのウエイポイントから前記候補道路までの差分距離とを比較して、前記候補道路を対象道路とすべきか否かを判定する処理とを行うことを特徴とするマップマッチング方法。
【請求項２】
前記判定距離を、前記一部の道路網データに含まれる個々のリンクに対して、前記リンクと前記並走類似形状道路との間の距離に基づいて規定することを特徴とする請求項１に記載のマップマッチング方法。
【請求項３】
前記判定距離を、前記リンクと前記並走類似形状道路との間の距離の１／２に設定し、前記差分距離が、前記判定距離より小さいときにのみ、前記候補道路を対象道路と判定することを特徴とする請求項２に記載のマップマッチング方法。
【請求項４】
前記判定距離を、前記一部の道路網データに含まれる複数の道路に対して一様に規定することを特徴とする請求項１に記載のマップマッチング方法。
【請求項５】
前記マップマッチングでの各ウエイポイントから前記候補道路までの差分距離の最大値が、前記判定距離より小さいときにのみ、前記候補道路を対象道路と判定することを特徴とする請求項４に記載のマップマッチング方法。
【請求項６】
前記一部の道路網データを複数の区画に分割し、同一の区画に含まれる道路に対して、前記判定距離を一様に規定することを特徴とする請求項４に記載のマップマッチング方法。
【請求項７】
前記一部の道路網データを複数の区画に分割し、同一の区画に含まれる同一の道路種別の道路に対して、前記判定距離を一様に規定することを特徴とする請求項４に記載のマップマッチング方法。
【請求項８】
前記道路網データは、複数の階層に階層化されており、前記一部の道路網データは、下位の階層の道路網から抽出された道路網で成り立つ上位の階層の道路網データであることを特徴とする請求項１から請求項７のいずれかに記載のマップマッチング方法。
【請求項９】
前記道路網データは、異なる重みが付されている道路網の集合から成る一枚の地図の道路網データであり、前記一部の道路網データは、前記一枚の地図の道路網データから抽出された、重みが比較的大きい道路網データであることを特徴とする請求項１から請求項７のいずれかに記載のマップマッチング方法。
【請求項１０】
複数の階層の道路網に階層化され、上位の階層の道路網がそれより下位の階層の道路網から抽出された道路網で成り立ち、上位の階層の道路網には、当該階層の道路網を対象道路として採用するか否かを判定するための判定距離が規定されているマップマッチング用の道路網データと、
対象道路の形状を表す形状ベクトルを含むデータを受信するデータ受信部と、
前記道路網データを用いて前記形状ベクトルのマップマッチングを行い、前記対象道路を特定するマップマッチング部と
を備え、前記マップマッチング部は、可能な限り上位の階層の前記道路網データを用いてマップマッチングを行うことにより対象道路の候補道路を取得し、下位の階層の道路網に前記候補道路と並走する類似形状の並走類似形状道路が存在するときに、前記判定距離と、前記マップマッチングでのウエイポイントから前記候補道路までの差分距離とを比較して、前記候補道路を対象道路とすべきか否かを判定することを特徴とする受信装置。
【請求項１１】
前記道路網データの上位の階層の道路網に含まれる個々のリンクに対して、前記リンクと前記並走類似形状道路との間の距離が前記判定距離として規定され、前記マップマッチング部は、前記差分距離が、前記判定距離の１／２より小さいときにのみ、前記候補道路を対象道路と判定することを特徴とする請求項１０に記載の受信装置。
【請求項１２】
前記道路網データの上位の階層の道路網に含まれる複数の道路に対して、前記判定距離が一様に規定され、前記マップマッチング部は、前記マップマッチングでの各ウエイポイントから前記候補道路までの差分距離の最大値が、前記判定距離より小さいときにのみ、前記候補道路を対象道路と判定することを特徴とする請求項１０に記載の受信装置。
【請求項１３】
前記上位の階層の道路網が複数の区画に分割され、同一の区画に含まれる道路に対して、前記判定距離が一様に規定されていることを特徴とする請求項１２に記載の受信装置。
【請求項１４】
前記上位の階層の道路網が複数の区画に分割され、同一の区画に含まれる同一の道路種別の道路に対して、前記判定距離が一様に規定されていることを特徴とする請求項１２に記載の受信装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マップマッチングの方法と、それを実施する装置に関し、特に、高速でのマップマッチングを可能にするものである。
【０００２】
【従来の技術】
従来、カーナビゲーション装置は、例えば、下記特許文献１に記載されているように、地図データを保持し、カーナビゲーション装置が搭載された車両の走行位置を地図データ上で特定するために、例えば１秒間隔でマップマッチングを実施している。この地図データには、道幅３．３ｍ以上の道路の全てが含まれており、この中から、自車位置周辺の限られたエリア（通常、数百ｍ四方程度）の地図データを対象としてマップマッチングを行い、自車位置に相当する地図上の地点を求めている。
【０００３】
マップマッチングには、いくつかの方法が知られている。例えば、マクロマップマッチングのアルゴリズムは次のようなものである。
▲１▼図１８（ａ）に示すように、ＧＰＳ受信機で求めた車両位置をＷＰ（ウエイポイント）として、ＷＰの周辺のリンクを探索し、１番目のＷＰ１を中心とするＡメートル（２５０ｍ程度）四方の中で車両の進行方位との差が±Ｂ°（例えば４５°程度）以内の方位を持つリンクを検出し、このリンクを候補点（×印）に設定する。候補点のリンク数（ｎ）は５〜８個程度とする。図１８（ｂ）では、ＷＰ１の候補点を１−１、１−２、１−３としている。
【０００４】
▲２▼図１８（ｂ）に示すように、次のＷＰ２を中心とするＡメートル四方の中で車両の進行方位との差が±Ｂ°以内の方位を持つリンクを検出し、ｎ個のリンクを候補点（２−１、２−２、２−３）として設定する。
▲３▼この処理を最後のＷＰに達するまで繰り返す。
▲４▼各々の候補点間を道路リンクに沿って接続し、形状パターンを作成する。候補点間が道路に沿って接続しないケース（例えば、ＷＰ３の候補点３−３、３−２は、次のＷＰ４の候補点と道路に沿って接続することができない）では、形状パターンを作成しない。
▲５▼各々の形状パターンと、ＷＰ１、ＷＰ２、‥の形状とを比較し、最も似通った形状パターン、即ち、距離が近く、標準偏差等によって評価したＷＰ１、ＷＰ２、‥の形状とのばらつきが小さいものを最終的に一つ選出する。
この▲４▼で得られる形状パターンは、ＷＰの数がＭ個で、各ＷＰ当たりの候補点が平均Ｎ個得られたとするとＮＭ個の組み合わせとなり、通常、数千〜数万の数となる。▲５▼では、このＮＭ個の組み合わせの中から一つを選択する。
【０００５】
また、マップマッチングは、下記特許文献２に記載されたデジタル地図上の位置情報伝達方法でも使用される。この方法では、送信側が、道路区間を伝えるために、図１９に示すように、その道路区間に設定した複数のノードの位置データ列を伝送し、受信側は、自己の地図データを用いたマップマッチングで各ノード位置を特定して道路区間を識別する。
【０００６】
【特許文献１】
特開平７−２６０４９９号公報
【０００７】
【特許文献２】
特開平２００１−６６１４６号公報
【０００８】
【発明が解決しようとする課題】
前述するデジタル地図の位置情報伝達方法は、例えば、道路交通情報を提供するときに、その道路交通情報の対象道路区間を知らせるために使用することができる。また、走行車両（プローブカー）が走行中に計測した計測情報と走行軌跡とをセンターに伝えて、センターが、受信した計測情報を交通情報の作成に活用するプローブカーシステムでは、プローブカーが走行軌跡を知らせるために使用することができる。
【０００９】
こうした使用法の場合、道路網の中で位置情報伝達の対象となる道路には偏りがあり、対象となる機会が極めて多い道路と、対象となる機会が極めて少ない道路とが存在する。混雑状況を示す交通情報は、一部の主要道路については頻繁に提供されるが、細街路に関する情報は少ない。また、プローブカーがセンターに走行軌跡を伝える道路の割合も、交通量が多い幹線道路では高く、交通量が少ない道路では低くなる。
しかし、このデジタル地図の位置情報伝達方法において、従来のマップマッチング方法を用いると、ＷＰとなる各ノードの周辺に多くの候補点が発生し、マップマッチング処理時間が長くなるという問題点がある。
【００１０】
本発明は、こうした従来の問題点を解決するものであり、マップマッチングの対象道路に該当する頻度に偏りを有する道路網に対して、高速で処理ができるマップマッチング方法を提供し、また、その方法を実施する装置を提供することを目的としている。
【００１１】
【課題を解決するための手段】
そこで、本発明のマップマッチング方法では、道路網データから抽出された一部の道路網データを用いてマップマッチングを行い、対象道路の候補道路を取得する処理と、前記一部の道路網データに含まれていない、候補道路に並走する類似形状の並走類似形状道路が存在するときに、前記一部の道路網データで規定された、候補道路が関係する判定距離と、マップマッチングでのウエイポイントから候補道路までの差分距離とを比較して、候補道路を対象道路とすべきか否かを判定する処理とを行うようにしている。
そのため、多くの場合、優先順位の高い道路、重みが大きい道路、あるいは、最上位階層の道路網など、一部の道路網データを用いたマップマッチングで対象道路を特定することが可能であり、マップマッチングの高速化を図ることができる。また、上位階層のマップマッチングで得られた候補道路と形状が類似する並走類似形状道路が、低い階層の道路網に存在する場合でも、判定距離を用いて、候補道路の採用の是非を迅速に判断することができる。
【００１２】
また、本発明の受信装置は、複数の階層の道路網に階層化され、上位の階層の道路網がそれより下位の階層の道路網から抽出された道路網で成り立ち、上位の階層の道路網には、当該階層の道路網を対象道路として採用するか否かを判定するための判定距離が規定されているマップマッチング用の道路網データと、対象道路の形状を表す形状ベクトルを含むデータを受信するデータ受信部と、道路網データを用いてこの形状ベクトルのマップマッチングを行い、対象道路を特定するマップマッチング部とを設け、マップマッチング部が、可能な限り上位の階層の道路網データを用いてマップマッチングを行うことにより対象道路の候補道路を取得し、下位の階層の道路網にこの候補道路と並走する類似形状の並走類似形状道路が存在するときに、判定距離と、マップマッチングでのウエイポイントから候補道路までの差分距離とを比較して、候補道路を対象道路とすべきか否かを判定するように構成している。
そのため、マップマッチングを高速で実施することができる。
【００１３】
【発明の実施の形態】
まず、本発明のマップマッチング方法の基本概念について説明する。
マップマッチングを実施する受信側装置は、図１１に示すようなデジタル地図データを保持している。この地図データには、ヘッダで規定された区画内のノード及びリンクの情報が記述され、ノード情報には、ノード数、各ノードのノード番号、各ノードのノード属性情報、各ノードの緯度経度、及び各ノードに接続する接続ノードと接続リンクとの情報が含まれ、また、リンク情報には、リンク数、リンク番号、リンクの道路種別等を表す属性情報、リンクの形状を規定する補間点の数、及び各補間点の緯度経度の情報が含まれている。
なお、ノード番号、リンク番号及び補間点は、この地図データの制作者が独自に設定したものであり、他の制作者によって制作された地図データとの間では共通性が無い。
【００１４】
受信側装置は、この地図データから、マップマッチング用の階層構造の道路ネットワークデータを作成する。
図１０は、この階層構造の道路ネットワークデータの概念を示している。ここでは、３層の階層構造の例を示している。また、図１２は、各階層の道路ネットワークデータの例を示している。図１０（ｃ）は、階層構造の最下位層の道路ネットワークデータであり、これには全道路網のデータが含まれる。この最下位層の道路ネットワークデータの例を図１２（ｃ）に示している。これは図１１と同様の地図データである。図１０（ｂ）は、道幅が５．５ｍ以上の道路のみを含む中位層の道路ネットワークデータであり、この道路ネットワークデータを図１２（ｂ）に示している。図１０（ａ）は、主要地方道以上の幹線道路のみを含む最上位層の道路ネットワークデータであり、この道路ネットワークデータを図１２（ａ）に示している。
【００１５】
上位層、中位層及び下位層の各道路ネットワークデータにおいて、ノード数、リンク数及び補間点数は、上位層になるほど多く間引かれる。ノード番号は、最下位層で付番した番号が、上位の層の該当するノードの番号としてそのまま使用される。リンク番号は、全層にわたって重複しないように、各層のリンクにユニークな番号を付与することが好ましい。
なお、ここでは３層の階層構造について示したが、階層の数は３以外であっても良い。
【００１６】
図１３は、この階層構造の道路ネットワークデータを保持する受信側装置１０と、受信側装置１０に交通情報や計測情報などの事象情報、及び、その事象情報の対象道路区間を示す形状ベクトルデータを提供する送信側装置３０との構成を模式的に示している。交通情報提供システムでは、送信側装置３０がセンターであり、受信側装置１０がカーナビ車載機などである。また、プローブカーシステムでは、送信側装置３０がプローブカー車載機であり、受信側装置１０がプローブカーから情報を収集するセンターである。
【００１７】
送信側装置３０は、事象情報を蓄積する蓄積部３４と、事象情報の対象道路を示す形状ベクトルデータを生成する形状ベクトルデータ生成部３３と、この形状ベクトルデータ及び事象情報データから、事象情報の対象道路区間を形状ベクトルデータ列で表した形状ベクトル表現事象情報を生成する形状ベクトル表現事象情報生成部３２と、このデータを送信するデータ送信部３１とを備えている。
一方、受信側装置１０は、データを受信するデータ受信部１１と、受信データを蓄積する形状ベクトル表現事象情報データベース１２と、階層構造の道路ネットワークデータ１４と、階層構造の道路ネットワークデータ１４を用いたマップマッチングで対象道路を特定するマップマッチング部１３と、デジタル地図Ｂのデータベース１６と、事象情報を表示したり活用したりする事象情報活用部１５とを備えている。
【００１８】
なお、マップマッチング部１３は、受信側装置１０のコンピュータに、コンピュータプログラムで規定した処理を行わせることにより実現できる。
交通情報提供システムの場合では、送信側装置３０であるセンターが、保有するデジタル地図データベースのデータを用いて、事象情報（交通情報）の対象道路区間を示す形状ベクトルデータを生成し、事象情報と共に送信する。図１４には、送信側装置３０が送信するデータ（形状ベクトル表現事象情報）の一例を示している。
【００１９】
また、プローブカーシステムの場合には、送信側装置３０であるプローブカー車載機が、ＧＰＳ等により現在位置を検出しながら走行し、一定距離ごとの位置検出地点（ノード）における位置データ、あるいは、この位置データを基に、保有するデジタル地図データを用いて特定した位置データを形状ベクトルデータとして、計測情報（速度などの事象情報）と共に送信する。図１５には、プローブカー車載機が送信するデータ（形状ベクトル表現事象情報）の一例を示している（ここでは、形状ベクトルデータ及び計測データを符号化して送信する場合を示している）。
【００２０】
一方、受信側装置１０は、デジタル地図データベースＢ１５のデータを用いて階層構造の道路ネットワークデータ１４を予め生成し、保持している。
受信側装置１０は、形状ベクトル表現事象情報を受信すると（それが符号化されている場合は復号化した後）、対象道路区間を特定するために、上位層の道路ネットワークデータを用いて、形状ベクトルデータに含まれるノードをＷＰとしてマップマッチングを行う。マップマッチングの処理自体は、マクロマップマッチングなど、従来から知られている方法を使用する。
【００２１】
上位の層程、道路ネットワークが疎であるため、ＷＰ周辺の候補点が少なく、マップマッチングの処理を高速化できる。
もしも、上位層の道路ネットワークデータで道路の特定ができない場合（例えば候補点が設定できない場合）には、下位の道路ネットワークを用いてマップマッチングをやり直す。
また、上位層の道路ネットワークデータを用いたマップマッチングで対象道路が特定できた場合でも、下位層の道路ネットワークデータに並走する道路が存在する場合には、上位層のマップマッチングだけで対象道路を決めてしまうと、誤マッチングの可能性がある。ここでは、上位層の道路と並走する、下位層にだけ存在する道路を「並走類似形状道路」と呼ぶことにする。
【００２２】
例えば、図１６において、太実線及び太鎖線が主要地方道であり、点線が都道府県道であり、これらの線の間に存在する道路が５．５ｍ未満の生活道路であるとすると、最上位層の道路ネットワークデータには太実線及び太鎖線のみが含まれ、点線は、中位層及び最下位層の道路ネットワークデータに含まれ、生活道路は最下位層の道路ネットワークデータにのみ含まれる。
この最上位層の道路ネットワークデータを用いたマップマッチングで太鎖線が特定できた場合、中位層及び最下位層の道路ネットワークデータを用いてマップマッチングを行ったとしても、太鎖線に代わる道路は特定されない。
【００２３】
しかし、最上位層の道路ネットワークデータを用いたマップマッチングで太実線が特定できた場合では、中位層の道路ネットワークデータを用いてマップマッチングを行うと点線が特定され、また、最下位層の道路ネットワークデータを用いてマップマッチングを行うと、太実線や点線と並走する生活道路が特定される可能性がある。つまり、最上位層の道路ネットワークデータを用いたマップマッチングで特定された太実線を対象道路と決めつけることは誤マッチングの可能性がある。
【００２４】
そこで、上位層でのマップマッチングで特定した道路の周辺に誤マッチングしそうな並走類似形状道路が存在するか否かを判定し、並走類似形状道路が存在しない場合には、上位層の道路ネットワークデータを用いて特定した道路を対象道路と決定する。
また、上位層でのマップマッチングで特定した道路の周辺に並走類似形状道路が存在する場合には、対象道路が並走類似形状道路で無いことを確認し、その確認が取れたときは、上位層でのマップマッチングで特定した道路を対象道路と決定し、その確認が取れないときは、下位の道路ネットワークを用いてマップマッチングをやり直す。
【００２５】
マップマッチングのやり直しは、図１７に示すように、スタート地点からマップマッチングを続けて来て、上位層の道路ネットワーク（ａ）では、道路が特定できなくなったときに、上位層（ａ）及び下位層（ｂ）に共通して存在するノード（層間連絡ノード）Ｐｃまで引き返して、下位層の道路ネットワーク（ｂ）に移行し、この層間連絡ノードＰｃより先の道路を下位層のネットワークデータ（ｂ）を用いたマップマッチングで特定するようにしても良い。
【００２６】
図１７では、道路ネットワークデータの階層構造が上位層（ａ）及び下位層（ｂ）の二層から成り、また、形状ベクトルを下流から上流に向かってＰｓ→Ｐａ→Ｐｂ→Ｐｃ→Ｐｄ→Ｐｅの順でマップマッチングする場合を示している。下位層（ｂ）でのマップマッチングに連続して成功（即ち、候補点の探索に成功）し、Ｐｓ→Ｐａ→Ｐｂを特定すると、上位層（ａ）に移行し、Ｐｃ→Ｐｄ→Ｐｅのマップマッチングを上位層（ａ）で行っている。しかし、Ｐｅのマップマッチングに失敗した（即ち、候補点探索に失敗、あるいは、並走類似形状道路を対象道路から除外できない）ため、層間連絡ノードＰｃの位置まで戻って下位層（ｂ）に移行し、Ｐｄ→Ｐｅのマップマッチングを下位層（ｂ）で行っている。図１７（ｃ）には、マップマッチングの結果をまとめて示している。
【００２７】
このように、上位層の道路ネットワークデータでのマップマッチングに失敗して、下位層の道路ネットワークデータによるマップマッチングをやり直す場合には、始めから下位層だけを用いて処理する場合に比べて、処理効率が低下する可能性もあるが、しかし、上位層でマッチングに成功し、且つ、並走類似形状道路が存在しない場合には、処理が一瞬で終わる。そのため、数十〜数百のマップマッチング処理のトータル性能では、階層構造の道路ネットワークデータから上位層のデータを優先して用いてマップマッチングを行う方が処理効率において勝ることになる。
【００２８】
また、階層構造の道路ネットワークデータを用いるマップマッチングでは、並走類似形状道路が存在する場合に、対象道路が並走類似形状道路で無いかどうかの判定（並走路判定）を短時間で行うことができるならば、処理効率をさらに高めることができる。
以下、並走路判定処理の効率化を図る方法について詳しく説明する。
【００２９】
（第１の実施形態）
本発明の第１の実施形態におけるマップマッチング方法では、並走類似形状道路が存在する場合に、上位層の道路ネットワークデータに、リンク情報として、並走類似形状道路までの距離のデータを含める。
図２には、リンクの並走類似形状属性として、並走類似形状道路の本数と、各並走類似形状道路までの距離の情報とを含めた上位層のマップマッチング用道路ネットワークデータを示している。
【００３０】
この場合の並走路判定処理は、次のように行う。
図１に示すように、上位層の道路ネットワークデータを用いてマップマッチングを実施した場合に、ＷＰ（黒丸）から上位層道路Ｒまでの距離が、上位層道路Ｒから最寄りの並走類似形状道路ｒまでの距離Ｄの１／２より小さければ、上位層道路Ｒを対象道路と決定する。また、ＷＰから上位層道路Ｒまでの距離がＤ／２より大きければ、並走類似形状道路ｒが対象道路である可能性を否定できないと見て、下位層の道路ネットワークデータを用いたマップマッチングに移行する。
【００３１】
この上位層におけるリンクの並走類似形状属性は次のように求める。
▲１▼図３に示すように、上位層道路Ｒ１上に、例えば固定ピッチで（あるいは上位層道路Ｒ１の補間点及び補間点間の中点に）判定ポイントＰ（ｊ）を設定する。
▲２▼次に、各Ｐ（ｊ）について、上位層道路Ｒ１の進行方向の右側及び左側に並走類似形状道路ｒｎが存在するか否かを判定し、存在する場合には、Ｐ（ｊ）から並走類似形状道路ｒｎまでの距離を求める。具体的には、Ｐ（ｊ）から最も近い道路ｒｎ上の点をＰｎ（ｊ’）とするとき、Ｐ（ｊ）とＰｎ（ｊ’）との距離Ｌｎ（ｊ）が規定値より小さく、且つ、Ｐ（ｊ）での絶対角度θ（ｊ）とＰｎ（ｊ’）での絶対角度θｎ（ｊ’）との差分（｜θｎ（ｊ’）−θ（ｊ）｜）が規定値より小さいときに、道路ｒｎを並走類似形状道路と判定し、Ｌｎ（ｊ）をＰ（ｊ）から並走類似形状道路ｒｎまでの距離とする。
▲３▼次に、隣り合う判定ポイントＰ（ｊ）、Ｐ（ｊ＋１）において、共に並走類似形状道路ｒｎが存在し、距離Ｌ（ｊ）、Ｌ（ｊ＋１）が同じであるときは、Ｐ（ｊ）とＰ（ｊ＋１）とをリンクとして接続する。
▲４▼前記▲３▼以外は、判定ポイントでリンクを区切り、ノードを設定する。
【００３２】
図４（ａ）、（ｂ）には、この手順で設定した上位層道路Ｒのノード（黒丸）と並走類似形状道路ｒとの関係を示している。上位層道路Ｒの白丸はリンクとして接続された判定ポイントを示している。
▲５▼並走類似形状道路ｒｎに対向するリンクについて、左側・右側の各並走類似形状道路ｒｎまでの平均距離Ｄを求め、道路ネットワークデータの並走類似形状属性として設定する。
▲６▼並走類似形状道路の変化点に対向するリンク（図４（ａ）、（ｂ）において中括弧で囲んだリンク）については、並走路判定に際して、前後のリンクを参照するように指定するフラグを並走類似形状属性として設定する（あるいは、前後のリンクの平均距離Ｄを共に記載する）。
【００３３】
図５のフロー図には、この階層構造の道路ネットワークデータを用いてマップマッチングを行う手順について示している。
可能な限り上位の層の道路ネットワークデータを用いてマップマッチングを行い、道路を特定する（ステップ１）。この道路を上位層特定道路と呼ぶことにする。次に、１番目のＷＰに着目して（ステップ２）、ＷＰを上位層特定道路に移動したときの移動量を算出する（ステップ３）。ＷＰを移動した上位層特定道路のリンクにおける道路ネットワークデータの付帯情報（並走類似形状属性）を参照し、並走類似形状道路が存在するか否かを判定する（ステップ４）。この付帯情報から右側の並走類似形状道路までの距離Ｄを求め（ステップ５）、ステップ３で求めたＷＰの移動量がＤ／２より小さいか否かを判定する（ステップ６）。ＷＰの移動量がＤ／２より小さければ、付帯情報から左側の並走類似形状道路までの距離Ｄを求め（ステップ７）、ステップ３で求めたＷＰの移動量がＤ／２より小さいか否かを判定する（ステップ８）。ＷＰの移動量がＤ／２より小さければ、上位層特定道路を対象道路と決定する（ステップ９）。
また、ステップ６及びステップ８において、ＷＰの移動量がＤ／２より大きいときは、下位層に移行してマップマッチングをやり直す（ステップ１０）。
こうした処理を全てのＷＰに着目して実行し、全てのＷＰについての処理が完了すればマップマッチングを終了する（ステップ１１）。
【００３４】
このように、このマップマッチング方法では、上位層道路のリンクに並走類似形状道路までの距離Ｄの情報を持たせているため、この距離と、ＷＰから上位層道路までの距離と対比することにより、並走路判定を短時間で済ませることができる。
なお、ここでは、ＷＰから上位層特定道路までの移動量と距離Ｄの１／２とを比較する場合について説明したが、この移動量を距離Ｄの１／２より小さい値、例えば、距離Ｄの１／３と比較して、移動量の方が小さいときにだけ、上位層特定道路を対象道路と決定するようにしても良い。
【００３５】
（第２の実施形態）
本発明の第２の実施形態におけるマップマッチング方法では、ＷＰから上位層特定道路までの移動量と比較する距離（この距離を「判定距離」と呼ぶことにする）を、地図の同一区画に含まれる複数の道路に対して一様に定めている。並走路判定処理では、移動量が判定距離以下であれば、上位層特定道路を対象道路と決定し、移動量が判定距離より大きければ、下位層でのマップマッチングのやり直しを決定する。
【００３６】
同一区画に含まれる複数の道路に対して一様に判定距離を定めることは、次のような事情から可能である。
送信側装置が、Ａ社製のデジタル地図データＡに基づいて対象道路区間の形状ベクトルデータを生成し、一方、この形状ベクトルデータを受信した受信側装置が、Ｂ社製のデジタル地図データＢを用いてマップマッチングを行い、対象道路区間を特定する場合では、デジタル地図データＡとデジタル地図データＢとの間に誤差があるために、並走路判定処理が必要になる。
【００３７】
しかし、図６は、二つのメーカで作成された銀座付近の地図を重畳して表示したものであるが、双方の地図のずれは、隣接する並走路間の距離Ｄの１／２より遥かに小さい。従って、第１の実施形態で示すようにリンク単位で並走類似形状道路までの距離を設定しなくても、この区画に含まれる全ての道路に対して、各メーカで作成された地図間の最大ずれを多少上回る判定距離を一様に設定すれば、並走路判定処理において、この判定距離と、ＷＰから上位層特定道路までの移動量とを比較して、上位層特定道路を対象道路として良いかどうかが判定できることになる。
【００３８】
ただ、各メーカで作成される地図は、格子状道路が存在する都市部に関しては相対的に精度が高く、従って各メーカの地図間のずれは小さいが、山間部では、このずれが大きくなる傾向にある。
そのため、区画単位で判定距離を設定する場合は、例えば、図７に示すように、地図を適宜区画し、その区画ごとに判定距離を設定する必要がある。区画単位は、市、町、村、丁目などの行政界単位でも良く、また、任意の矩形単位でも良い。
また、道路種別や道路属性によってずれが異なる場合がある。例えば、高速道路は、一般道の上に設けられている場合、１／２５０００の地図上では、一般道と重ならないように、大きくずらして表示されることがある。こうした事情を考慮して、区画に含まれる道路の判定距離を、道路種別や道路属性ごとに設定するようにしても良い。
図８には、区画単位の判定距離（ＷＰ移動距離判定用データ）の情報を含めたマップマッチング用道路ネットワークデータを示している。
【００３９】
また、図９のフロー図には、この階層構造の道路ネットワークデータを用いてマップマッチングを行う手順について示している。
可能な限り上位の層の道路ネットワークデータを用いてマップマッチングを行い、道路を特定する（ステップ２１）。この上位層の道路ネットワークデータから、該当する区画のＷＰ移動距離判定用データＤを取得する（ステップ２２）。また、各ＷＰを上位層特定道路に移動したときの最大の移動量を算出し（ステップ２３）、ＷＰの最大移動量とＷＰ移動距離判定用データＤとを比較する（ステップ２４）。ＷＰの最大移動量がＤより小さければ、上位層特定道路を対象道路と決定する（ステップ２５）。ＷＰの最大移動量がＤ以上であれば下位層に移行してマップマッチングをやり直す（ステップ２６）。
【００４０】
この方法で用いる階層構造の道路ネットワークデータは、第１の実施形態（図２）と比べて、データ量が少なくて済む。また、上位層道路のリンクは並走類似形状道路の影響を受けずに設定することができる。
また、この方法での並走路判定処理は、道路ネットワークデータからリンクごとのＷＰ移動距離判定用データを取得する必要が無いため、短時間で終えることができる。そのため、下位層に移行する回数が増えても、トータルでは、処理効率を上げることができる。
【００４１】
なお、各実施形態では、階層構造の道路ネットワークデータを用いてマップマッチングを行う場合について説明したが、異なる重みが付されている道路網の集合から成る一枚の地図の道路網データを用いて、始めに、重みが比較的大きい道路網と、対象道路の形状を表す形状ベクトルとのマッチングを取り、重みが比較的大きい道路網でのマップマッチングに失敗したとき（即ち、候補点探索に失敗したとき、あるいは、低い重みの並走類似形状道路を対象道路から除外できないとき）に、前記道路網に重みがより小さい道路網を加えた道路網と前記形状ベクトルとのマッチングを取ることにより、前記対象道路を特定するようにしてもよい。この場合でも、道路網のリンクごとに設定された判定距離、あるいは、道路網の区画ごとに設定された判定距離に基づいて、並走路判定処理を行うことにより、マップマッチング処理を高速化できる。
【００４２】
【発明の効果】
以上の説明から明らかなように、本発明のマップマッチング方法では、対象道路に該当する頻度が偏っている道路網の中から、対象道路を迅速に特定することが可能である。
また、本発明の装置は、このマップマッチング方法を実施して、対象道路を迅速に特定することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態におけるマップマッチング方法での並走路判定処理を模式的に説明する図
【図２】本発明の第１の実施形態におけるマップマッチング用道路ネットワークデータを示す図
【図３】本発明の第１の実施形態におけるマップマッチング用道路ネットワークデータの並走類似形状属性情報の生成方法について説明する図
【図４】本発明の第１の実施形態におけるマップマッチング用道路ネットワークデータのリンクと並走類似形状道路との関係を説明する図
【図５】本発明の第１の実施形態におけるマップマッチング方法を示すフロー図
【図６】本発明の第２の実施形態におけるマップマッチング方法について説明する図
【図７】本発明の第２の実施形態におけるマップマッチング方法で一様な判定距離を設定する区画について示す図
【図８】本発明の第２の実施形態におけるマップマッチング用道路ネットワークデータを示す図
【図９】本発明の第２の実施形態におけるマップマッチング方法を示すフロー図
【図１０】本発明の実施形態における階層構造のマップマッチング用道路ネットワークデータを模式的に示す図
【図１１】元の道路ネットワークデータを示す図
【図１２】元の道路ネットワークデータから生成した階層構造のマップマッチング用道路ネットワークデータを示す図
【図１３】本発明の実施形態におけるマップマッチング方法を実施する送信側装置と受信側装置とを示すブロック図
【図１４】送信側装置が送信するデータの一例を示す図
【図１５】送信側装置が送信するデータの他の例を示す図
【図１６】並走類似形状道路について説明する図
【図１７】本発明の実施形態におけるマップマッチング方法で階層間を移行してマップマッチングを続ける場合の処理を模式的に示す図
【図１８】従来のマップマッチング方法を示す説明図
【図１９】道路形状を示す形状ベクトルデータ列を示す図
【符号の説明】
１０  受信側装置
１１  データ受信部
１２  形状ベクトル表現事象情報データベース
１３  マップマッチング部
１４  階層構造道路ネットワークデータ
１５  事象情報活用部
１６  デジタル地図データベース
３０  送信側装置
３１  データ送信部
３２  形状ベクトル表現事象情報生成部
３３  形状ベクトルデータ生成部
３６  事象情報蓄積部
【図１】
2004264203.tif 000003
【図２】
2004264203.tif 000004
【図３】
2004264203.tif 000005
【図４】
2004264203.tif 000006
【図５】
2004264203.tif 000007
【図６】
2004264203.tif 000008
【図７】
2004264203.tif 000009
【図８】
2004264203.tif 000010
【図９】
2004264203.tif 000011
【図１０】
2004264203.tif 000012
【図１１】
2004264203.tif 000013
【図１２】
2004264203.tif 000014
【図１３】
2004264203.tif 000015
【図１４】
2004264203.tif 000016
【図１５】
2004264203.tif 000017
【図１６】
2004264203.tif 000018
【図１７】
2004264203.tif 000019
【図１８】
2004264203.tif 000020
【図１９】
2004264203.tif 000021