JP2008052282A - マップマッチング方法とそれを実施する装置 - Google Patents

Abstract

【課題】形状データに含まれるノード数が多い場合でも、少ないメモリ使用量で、且つ、高速で、その形状をデジタル地図上に特定できるマップマッチング方法を提供する。
【解決手段】デジタル地図の線形形状の上に並ぶノードの位置情報が配列された形状データを用いて、この線形形状を自己のデジタル地図の地図データに対応付けるマップマッチングにおいて、形状データを複数のブロックに分割し、マップマッチングをブロックの単位で行う。（ａ）６個のノードを含む形状データでは３個の候補点の組み合わせ数が７２９となるが、（ｂ）これを３ブロックに分割すると、候補点の組み合わせ数は２７となり、高速処理が可能であり、メモリ使用量は少なくて済む。
【選択図】図１

Description

本発明は、道路等の形状データからデジタル地図上の形状を特定するマップマッチング方法と、それを実施する装置に関し、その処理に使用するワークメモリのメモリ使用量を抑え、高速での処理を実現するものである。

現在、カーナビゲーション装置などに道路交通情報の提供サービスを実施しているＶＩＣＳ（道路交通情報通信システム）では、道路網に定義したリンク番号を使って道路を特定し、その道路の混雑状況などを表示している。
しかし、道路網に定義したリンク番号は、道路の新設や変更等に伴って新しい番号に付け替える必要があり、それに応じて、各社で制作したデジタル地図データも更新しなければならないため、リンク番号で道路位置を特定する方式は、メンテナンスに多大な社会的コストが掛かることになる。

こうした点を改善するため、下記特許文献１では、共通のリンク番号を用いずに、デジタル地図上の道路位置を伝える方法を提案している。この方法では、送信側が、図１５（ａ）に示すように、送信側のデジタル地図上で伝送しようとする道路区間に複数のノードｐ１、ｐ２、・・ｐＮを設定し、図１５（ｂ）に示すように、この複数のノードｐ１、ｐ２、・・ｐＮの位置データを配列した「道路形状データ」を生成する。そして、この道路区間内の交通状況を基準ノード（例えばｐ１）からの距離で表した交通情報と、この道路形状データとを受信側に伝える。受信側は、道路形状データに含まれる各ノード位置を自己のデジタル地図上に対応付けるマップマッチングを行って道路区間を特定し、その基準ノードからの距離の情報に基づいて交通状況を再現する。

また、下記特許文献２では、この道路形状データを可変長符号化して、データ量を削減する方法を提案している。この方法では、図１６（ａ）に示すように、伝えようとする道路区間上に一定距離間隔ＬでノードＰ_j-1、Ｐ_j・・・を再設定し（これを「等距離リサンプル」と言う）、始端を除く各ノードの位置データを隣接ノードからの偏角θj（図１６
（ｂ））または偏角統計予測値差分Δθj（図１６（ｃ））（ノードの偏角θjをそれ以前のノードの偏角（θj-1、θj-2・・）を用いて予測した予測値と、実際の偏角θjとの差
分）で表わし、これを可変長符号化して、受信側に、その符号化データと、始端の緯度・経度データとを送信する。受信側は、符号化されたデータを復号化して各ノードの位置データを復元し、マップマッチングを行って道路区間を特定する。

また、マップマッチングには、いくつかの方法が知られている。例えば、カーナビゲーション装置が自車位置をデジタル地図上で特定するために使用されているマクロマップマッチングのアルゴリズムは次のようなものである。
（１）図１７（ａ）に示すように、デジタル地図上で、ＧＰＳ受信機によって位置が与えられた点ＷＰ（ウエイポイント）の周辺のリンクを探索し、１番目のＷＰ１を中心とするＡメートル（２５０ｍ程度）四方の中で車両の進行方位との差が±Ｂ°（例えば４５°程度）以内の方位を持つリンクを検出し、このリンクを候補点（×印）に設定する。候補点のリンク数（ｎ）は５〜８個程度とする。図１７（ｂ）では、ＷＰ１の候補点を１−１、１−２、１−３としている。

（２）図１７（ｂ）に示すように、次のＷＰ２を中心とするＡメートル四方の中で車両の進行方位との差が±Ｂ°以内の方位を持つリンクを検出し、ｎ個のリンクを候補点（２−１、２−２、２−３）として設定する。
（３）この処理を最後のＷＰに達するまで繰り返す。
（４）各々の候補点間を道路リンクに沿って接続し、形状パターンを作成する。候補点間が道路に沿って接続しないケース（例えば、ＷＰ３の候補点３−３、３−２は、次のＷＰ４の候補点と道路に沿って接続することができない）では、形状パターンを作成しない。（５）各々の形状パターンと、ＷＰ１、ＷＰ２、‥の形状とを比較し、最も似通った形状パターン、即ち、距離が近く、標準偏差等によって評価したＷＰ１、ＷＰ２、‥の形状とのばらつきが小さいものを一つ選出する。

こうしたマップマッチング方法は、デジタル地図上で道路形状データが表す対象道路を特定する場合にも適用することができ、道路形状データによって位置が与えられる各ノードをＷＰとして、対象道路を求めることができる。
特開２００１−４１７５７号公報 特開２００３−２３３５７号公報

この道路形状データは、ノード数が多いほど、可変長符号化によるデータ圧縮の効率が向上する。しかし、マップマッチングでは、ＷＰの数をＭ個、各ＷＰ当たりの候補点の平均個数をＮ個とすると、前記（４）の段階で得られる形状パターンが、Ｎ^M個の組み合わ
せとなるため、ノード数（＝ＷＰ数）が多いと、処理量が膨大になり、長い処理時間が掛かることになる。また、対象道路の距離が長いと、地図データを展開するために多くのメモリ量を持つワークメモリが必要になる。

本発明は、こうした従来の問題点を解決するものであり、形状データに含まれるノード数が多い場合でも、少ないメモリ使用量で、且つ、高速で、その形状をデジタル地図上に特定することができるマップマッチング方法を提供し、また、その方法を実施する装置を提供することを目的としている。

本発明では、デジタル地図の線形形状の上に並ぶノードの位置情報が配列された形状データを受信して、この線形形状を受信側のデジタル地図の地図データに対応付けるマップマッチングにおいて、受信した形状データを受信装置側で編集加工した後、マップマッチングを行うようにしている。
そのため、受信側では、受信した形状データを編集加工することにより、少ないメモリ使用量で、且つ、高速で、その形状をデジタル地図上に特定することが可能になる。

また、本発明では、形状データを複数のブロックに分割し、マップマッチングをブロックの単位で行うようにしている。
そのため、生成される形状パターンの数が減り、高速処理が可能になる。また、メモリ使用量は少なくて済む。

また、本発明では、形状データを一定距離で切断してブロックを生成するようにしている。
また、この場合、この一定距離を、地図データの最小ユニットの一辺の長さ以下に設定するようにしている。
こうすることで、最大でも４枚分のユニットの地図データをメモリに展開するだけでマップマッチングが実施できる。

また、線形形状が道路形状である場合に、一定距離での切断箇所を、道路種別の変更点に一致させるようにしている。
こうすることで、後述する「階層型マップマッチング」の動作効率が上がる。

また、本発明では、形状データを、線形形状を表示する地図データのユニットの一辺の長さを単位に切断して前記ブロックを生成するようにしている。
こうすることで、形状データを無駄に細かくすること無く、効率的に切断できる。

また、この場合、形状データの切断箇所を、ユニットの境界に合わせるようにしている。
こうすることで、使用するユニットの枚数を減らすことができる。

また、本発明では、形状データを、一定のノード数で切断して前記ブロックを生成するようにしている。
こうすることで、ノードが局所的に密集している場合でも、生成される形状パターンの数を減らすことができ、総合的な処理量を削減できる。

また、本発明では、線形形状が交通情報の対象道路の道路形状である場合に、形状データを、交通情報の分割単位に合わせて切断して前記ブロックを生成するようにしている。
こうすることで、交通情報と対象道路との整合性が取りやすい。

また、本発明では、形状データから誤マッチングを生じさせないノードを間引き、マップマッチングを、ノードを間引いた形状データを用いて行うようにしている。
ノード数が減れば、生成される形状パターンの数が減り、高速処理が可能になる。

また、この場合、間引きの対象となるノードを、そのノードと隣接ノードとの距離及び偏角、並びに、そのノードの周辺における線形形状の密度を考慮して選択するようにしている。
こうすることで、誤マッチングを生じさせないノードが選択できる。

また、本発明では、ノードの位置情報に対応する地図データの位置からそのノードの候補点を検索する角度範囲を、線形形状の曲がり具合に応じて適応的に設定するようにしている。
こうすることで、線形形状の曲がり具合が大きければ、角度範囲を拡げて、真の線形形状が候補から漏れないようにし、線形形状の曲がり具合が小さければ、角度範囲を狭めて、候補点が徒に増えないようにすることができる。

また、この場合、角度範囲を、ノードの前後または前方における所定距離区間の線形形状の曲がり具合と、その所定距離区間の線形形状の密度とを考慮して設定するようにしている。
こうすることで、角度範囲を適応的に設定できる。

また、本発明では、線形形状の既にマップマッチングが終了した部分のマップマッチング結果を参照して、線形形状の残る部分のマップマッチングにおけるパラメータを適応的に変更するようにしている。
こうすることで、既にマップマッチングが終了した区間の線形形状の誤差状況から、平均的な誤差発生状況を学習し、その学習結果に基づいて、以降の区間でのマップマッチングにおける候補点検索範囲や候補点検索方位範囲を適応的に設定することができる。

また、本発明では、情報処理装置に、デジタル地図の線形形状の上に並ぶノードの位置情報が配列された形状データを取得する形状データ取得手段と、形状データを複数のブロックに分割する形状データ切断手段と、このブロックから、誤マッチングを生じさせないノードを間引くノード間引き処理手段と、このブロックに含まれたノードの候補点を検索するための検索範囲を適応的に設定し、自己のデジタル地図の地図データ上でその検索範囲に含まれるノードの候補点を設定する候補点検索方位範囲決定手段と、設定された候補点を基に、線形形状に対応する形状を地図データ上で特定するマップマッチング処理手段とを設けている。
この装置は、多くのメモリを使わずに、高速でマップマッチングを行うことが可能である。

本発明のマップマッチング方法は、多くのメモリ量を使わずに、高速でマップマッチング処理を行うことができ、省メモリ及び高速化を実現できる。
また、このマップマッチング方法を実施する本発明の装置は、少容量のメモリを用いて構成することができ、それにも関わらず、高速での処理が可能である。

（第１の実施形態）
本発明の実施形態におけるマップマッチング方法では、道路形状データを受信した受信側が、少ないメモリ使用量で、且つ、短時間でマップマッチングができるように、道路形状データを編集加工し、この加工処理を施した道路形状データを用いてマップマッチングを実行する。受信側は、マップマッチングにおけるメモリ使用量を抑制し、処理時間を短縮するため、
（１）道路形状データの分割
（２）道路形状データからのノードの間引き
（３）候補点検索範囲の適応的設定
の各処理を実行する。各処理の概略について説明する。

（１）道路形状データの分割
圧縮効率を上げるために多数のノードが含まれている長い道路形状データを、受信側の都合に合わせて適宜切断し、分割した道路形状データ（「道路形状データブロック」と呼ぶ）の単位でマップマッチングを行う。

例えば、図１（ａ）に示すように、６個のノードを含む道路形状データをそのままマップマッチングすると、各ＷＰ当たりの候補点の平均個数が３個の場合、形状パターンの組み合わせ数は、３⁶＝７２９個であるが、図１（ｂ）に示すように、この道路形状データ
を２個のノードを含む３個の道路形状データブロックに分割してマップマッチングを行うと、形状パターンの組み合わせ数は、３×３²＝２７個となり、処理量が減少する。
また、図２に模式的に示すように、道路形状データを切断して、道路形状データブロックを個別にマップマッチングした方が使用メモリ量は少なくて済む。一般に、マップマッチングに必要なメモリ量は、道路形状データの長さの２乗に比例して増える。例えば、道路形状データの最大長が１０ｋｍのとき、１０ｋｍ四方（１００平方ｋｍ）分の地図データを展開するメモリサイズが必要となるが、道路形状データの最大長が１ｋｍのときは、１ｋｍ四方（１平方ｋｍ）のメモリで済むことになる。

（２）道路形状データからのノードの間引き
一般に、ノードが密に設定されているほど、マップマッチングの精度は上がるが、その分、ＷＰ数が増えるため、形状パターンの組み合わせ数が指数的に増加し、処理性能を劣化させる。マップマッチング精度を落とす恐れが少ないノードを選択して間引くことにより、処理時間の短縮、及び、ワークメモリ使用量の削減を図ることができる。

（３）候補点検索範囲の適応的設定
従来のマップマッチング方法では、ＷＰの候補点を抽出する際、車両の進行方位との角度差が±Ｂ°以内であることを候補点の条件にしており、この±Ｂ°を不変値（あらかじめ決められた値）としている。Ｂの値、即ち、検索方位に関する候補点検索範囲（「候補点検索方位範囲」）が小さいほど、ＷＰ候補点数が少なくなり、処理性能は向上するが、「真の道路」上に候補点が乗らない可能性が発生し、誤マッチングの可能性が高くなる。一方、Ｂの値を大きくすると精度は上がるが、候補点数が増え、処理性能が劣化する。

カーナビゲーション装置のマップマッチングでは、「これから進む道路」はどうなるか分からないが、道路形状データによるマップマッチングでは、あらかじめ進む道が明示されているため、着目しているＷＰの前後または前方の所定距離（地図誤差は最大１００ｍ程度あるので、１００〜２００ｍ程度）を見通して、カーブ状況を観察し、直線が続く場合は、Ｂの値を１０°まで絞り、大きなカーブがある場合は、６０°まで広げる、と言うように候補点検索方位範囲を可変にすることができる。
このように候補点検索範囲を適応的に可変にすることで、「真の道路」となる可能性が極めて低い道路を効率的に候補から除外することができ、マップマッチングの処理性能を高め、計算用のワークメモリ使用量を削減することができる。

図３には、このマップマッチング方法を実施するマップマッチング型情報処理装置１０の構成を示している。
この情報処理装置１０は、情報提供装置から交通情報と対象道路の道路形状データとを受信し、マップマッチングを実施して対象道路を特定する、カーナビゲーション装置、ＰＣ、ＰＤＡ、携帯電話等の情報端末であり、あるいは、プローブカー車載機から計測情報（交通情報）と走行軌跡を示す道路形状データとを受信し、マップマッチングを実施して走行軌跡を特定するプローブ情報収集センタ（情報収集配信センタ）等である。

この情報処理装置１０は、デジタル地図データベース１７と、情報送信装置から道路形状データ及び交通情報を受信する形状データ・交通情報受信部１１と、符号化されているデータを復号化する符号化データ復号部１２と、道路形状データを復元する形状データ復元部１３と、「道路形状データの分割」処理を行う形状データ切断部１４と、分割された道路形状データブロックと整合が取れるように交通情報を編集する交通情報編集部１９と、「道路形状データからのノード間引き」処理を行うノード間引き処理部１５と、「候補点検索範囲の適応的設定」処理を行い、ノードの候補点を設定する候補点検索範囲決定部１６と、ノード候補点を繋ぐ形状パターンを生成し、評価して、道路形状データブロックのそれぞれに対応する道路区間（「対象道路ブロック」と呼ぶ）を特定する形状パターン生成・評価部１８と、各対象道路ブロックが連続するように各対象道路ブロックの端部を補正し、各対象道路ブロックの交通情報を再現する切断形状補正・交通情報重畳部２０と、再現された交通情報を活用する情報活用部２１とを備えている。

この情報処理装置１０の形状データ・交通情報受信部１１で受信された道路形状データと交通情報とは、符号化データ復号部１２で復号化され、ノードの位置データ列から成る道路形状データが形状データ復元部１３で復元される。

（ａ）形状データ切断部１４の道路形状データの分割処理
形状データ切断部１４は、復元された道路形状データを、次の（ａ−１）〜（ａ−６）いずれかの方法で切断する。
（ａ−１）道路形状データを、あらかじめ決めた固定距離で（または、固定距離以下となるように等分に）切る。
デジタル地図データベース１７に格納されている地図データは、図４に示すように、通常、概ね１０ｋｍ×１０ｋｍ（正確なサイズは、場所により異なる）の２次メッシュをベースに４分割（長さ１／２）、１６分割（１／４）、６４分割（１／８）されたユニットで構成されており、各ユニットのデータ量が略同レベルになるように、各地のユニットが設定されている。最も小さい６４分割サイズのユニットは、約１．２５ｋｍ四方の大きさである。
そのため、道路形状データを固定距離で切断する場合は、固定距離の長さを約１ｋｍに設定する。こうすることで、分割した道路形状データブロックのマップマッチングは、最大でも４枚分のユニットの地図データを用いるだけで可能になる。

この模様を図５に示している。ここでは、ユニットサイズの一辺を１ｋｍとし、道路形状データの長さを３．２ｋｍとしている。道路形状データをこのままの長さでマップマッチングする場合は、図５（ａ）に示すように、最悪で４×４枚のユニットデータが展開できるメモリを準備する必要がある。これに対して、道路形状データを切断点で切断し、１ｋｍの長さにすると、図５（ｂ）に示すように、２×２枚のユニットデータを展開するメモリ量で対応できる。

（ａ−２）道路形状データを固定距離（または固定距離以下）で切断する場合に、道路種別の変化点を切断点に設定する。
本発明者は、先に、「階層型マップマッチング」と言うマップマッチング方法を提案している。この方法では、道路種別を参考に地図データを階層化し、上位の階層は幹線道路のみを含み、階層が下がるに連れて、新たな道路種別の道路が順次追加された階層型の地図データを用いてマップマッチングを行う。この方法では、可能な限り上位の階層の地図データを用いてマップマッチングを行うことにより、処理時間を短縮できる。

この（ａ−２）により道路形状データを切断する場合は、階層型マップマッチングにおいて、使用する階層の地図データが特定されるため、階層型マップマッチングの動作効率が向上する。なお、切断点とすべき道路種別の変化点は、階層型の地図データにおいて階層を区別している道路種別に対応させた方が効率的である。

（ａ−３）道路形状データを、該当箇所周辺部のユニットサイズに合わせて切断する。
道路形状データが６４分割サイズのユニットのエリアにおける道路を表している場合は、６４分割サイズの一辺の長さ（約１ｋｍ）の単位で道路形状データを切断し、１６分割サイズのユニットのエリアにおける道路を表している場合は、１６分割サイズの一辺の長さ（２．５ｋｍ）の単位で道路形状データを切断する。そのため、デジタル地図データベース１７の地図データを参照して、道路形状データの両端、または中点の緯度・経度から、当該道路形状データが収まるエリアのユニットサイズを求め、切断の単位長さを決定する。

（ａ−４）道路形状データを、ユニットの境界に合わせて切断する。
道路形状データを、その箇所のユニットサイズに合わせて切断する際に、そのユニットの境界（左右・上下）の緯度・経度をデジタル地図データベース１７から求め、この境界線沿いに（または境界を参考にして）道路形状データを切断する。こうすることで、デジタル地図データベース１７から読み出すユニットの数を減らすことができ、ユニットデータを展開するメモリ量を減少させることができる。

（ａ−５）道路形状データを一定のノード数の単位に切断する。
都市部の密集地の道路や山間部の峠道などでは、沢山のノードが局部的に密集しているケースがある。この場合、道路形状データを固定距離で切断すると、一部の道路形状データブロックに多数のノードが含まれる可能性が生じる。

マップマッチングの処理性能は、処理アルゴリズム上、距離もさることながらノード数にも大きく依存し、道路形状データブロックが多数のノードを含む場合は、そのブロックの処理量が膨大になり、全体の処理量を押し上げる結果になる。このため、多数のノードを含む道路形状データブロックが出現しないように、一定ノード数単位に道路形状データを切断して各道路形状データブロックのノード数を均一化した方が、図１で示した形状パターンの組み合わせ数を減らすことができ、トータルの処理時間を短縮できる。

（ａ−６）道路形状データを、交通情報の分割単位に合わせて切断する。
情報送信装置が、交通情報の対象道路を単位長さに切断し、その単位に区分した交通情報を符号化して送信して来る場合は、道路形状データを交通情報の分割位置に合わせて切断する。
道路形状データを切断する際に問題となるのは、道路形状データに紐付けされた交通情報との対応である。つまり、道路形状データブロックと対応するように、適切に交通情報も再編集する必要がある。交通情報は、情報送信装置の地図データを基準に対象道路に位置付けられて作成されているため、これを単に距離で切断すると、マップマッチング後の対象道路ブロックの道なり距離とずれる可能性がある。情報送信装置が交通情報を単位長さに区分して送信して来る場合は、道路形状データを交通情報の分割位置に合わせて切断することにより、交通情報との対応が余計な計算なしに非常にとりやすくなる。

（ｂ）ノード間引き処理部１５のノード間引き処理
ノード間引き処理部１５は、道路形状データブロックに含まれるノードを間引く処理を行う。
ノードを間引く際の基本的な考え方は、次の（ｂ−１）（ｂ−２）（ｂ−３）の通りである。
（ｂ−１）ノードの偏角の値が、ある一定値以下であれば間引く。
（ｂ−２）ノード間距離が、ある一定値以下であれば間引く。
（ｂ−３）周辺部の道路密度を考慮し、道路密度が高いときは、誤マッチングを生じないようにノードの間引きは控える。道路密度が低いときは、誤マッチングの恐れが少ないためノードを間引く。

ノードの間引き処理を実行する際は、これらの考え方を組み合わせた間引き条件を設定し、その条件に照らして、ノードを間引くか否かを決める。
例えば、間引き条件は、次のように設定する。
“周辺道路密度Ｐ１のとき、（１）ノードの偏角の絶対値がα１未満、且つ、（２）ノード間隔がβ１未満、であればノードを間引く”
なお、周辺道路密度Ｐ１は、対象ノード周辺の単位面積当たりの道路延長を示す値（ランク分けした値）である。また、このＰ１は、対象ノードが存在するユニットのサイズを示す値（ランク分けした値）でもある。つまり、道路密度によりユニットサイズが違うので、ユニットサイズをチェックすると周辺道路密度が推定できる。

図６の地図において、Ａの付近（本線）の道路形状データとＢの付近（連絡路）の道路形状データとを比べると、周辺道路密度Ｐ１やノード間距離に関しては、双方で大きな違いは無いが、Ａの付近のノードは偏角が小さく、Ｂの付近のノードは偏角が大きい。そのため、Ａの付近のノードは、間引くことができるが、Ｂの付近のノードは、間引きの条件に合致しない。Ｂ付近のノードを間引くと本線側に誤マッチングする可能性がある。

図７は、道路形状データに含まれるノードが間引かれていく様子を、段階を追って示している。
ノード１は、始端のため残す（ａ）。ノード２は、偏角が一定値α１以上あるため残す（α１：概ね１°〜２°）（ｂ）。ノード３は、偏角が一定値α１以内、且つ、ノード間隔がβ１以内のため削除する（ｃ）。ノード４は、偏角がα１以内であるが、ノード間隔がβ１以上のため残す（ｃ）。ノード５は、偏角が一定値α１以内、且つ、ノード間隔がβ１以内のため削除する（ｄ）。ノード６は、偏角が一定値α１以上あるため残す（ｅ）。ノード７は、終端のため残す（ｅ）。

図８は、このノード間引き処理部１５の処理フローを示している。
間引き対象の道路形状データブロックを取得し（ステップ１）、ノード番号ｎ＝１のノードから順に（ステップ２）、ノードｎの情報を取得し（ステップ３）、間引いても差し支え無いノードか否かを判定する（ステップ４）。

間引きが差し支える、間引きが不可能なノードには、次のようなものがある。
・始終端
・ブロックコードや、イベント発生位置など、マップマッチングに使用する形状以外の目的のための位置を明示したノード（イベント発生点、属性変化点、ブロック化の端点位置など）

間引いても差し支えないノードの場合は、ノードの緯度・経度から周辺道路密度Ｐ１を算出し、間引きパラメータα１、β１を決定する（ステップ５）。
次いで、ノード（ｎ−１）→ノードｎ間の偏角絶対値αと、ノード間距離βとを算出し（ステップ６）、α＜α１、且つ、β＜β１であるか否かを判定し（ステップ７）、Ｙｅｓであれば、そのノードｎを間引く（ステップ８）。Ｎｏであれば間引かない。こうした処理を全てのノードについて逐次行う（ステップ９、ステップ１０）。

（ｃ）候補点検索範囲決定部１６の候補点検索範囲の適応的設定処理
候補点検索範囲決定部１６は、ノード間引き処理部１５が間引き処理した道路形状データブロックに対して、マップマッチングにおける候補点検索範囲を適応的に決定し、その検索範囲からノードの候補点を検索し、設定する。
候補点検索範囲決定部１６が候補点検索方位範囲を決定する際の基本的な考え方は、次の（ｃ−１）または（ｃ−２）と、（ｃ−３）とである。
（ｃ−１）着目するノードの前後数十〜数百ｍの道路形状データの状況（曲がり具合）を見て、当該ノードの候補点検索方位範囲を決定する。
（ｃ−２）着目するノードの今後マップマッチングしていく方向の道路形状データの曲がり具合を見て、当該ノードの候補点検索方位範囲を決定する。
（ｃ−３）道路密度を考慮する。

図９は、候補点検索範囲決定部１６の処理フローを示している。
候補点設定対象の道路形状データブロックを取得し（ステップ１１）、ノード番号ｎ＝１のノードから順に（ステップ１２）、ノードｎの前後であらかじめ決めた固定区間長内に存在する各ノードの情報を取得し（ステップ１３）、それらの各ノードと隣接ノードとの間の偏角絶対値を算出し、この偏角絶対値の統計値（最大値・平均値等）を算出する（ステップ１４）。ノードｎ周辺の道路密度も考慮して、候補点検索時の方位範囲Ｂを、例えば、次式、
Ｂ＝統計値×τ＋γ （τ、γは、道路密度に応じて決めたパラメータ）
によって決定する（ステップ１５）。

次に、デジタル地図データベース１７の地図上で、ノードｎの位置の周辺Ａメートル内に存在し、且つ、ノードｎの位置から“ノードｎの方位±Ｂ°”の方位範囲内に存在するリンクに候補点を設定する（ステップ１６）。こうした処理を全てのノードについて行う（ステップ１７、ステップ１８）。

こうした手順で候補点検索方位範囲を決定することにより、図１０に示すように、ＷＰ３、ＷＰ４、ＷＰ５の場合は、その前後にカーブが存在するため、候補点検索方位範囲が広く設定され、「真の道路」上に間違いなく候補点が設定される。また、ＷＰ６、ＷＰ７の場合は、Ｂの値が小さくなるため、（６−２）（７−２）が候補から外れ、後続する形成パターン生成処理が効率化できる。

形状パターン生成・評価部１８は、候補点検索範囲決定部１６が設定した候補点間を道路リンクに沿って接続し、道路形状パターンを作成する。デジタル地図上で候補点間が道路に沿って接続していないケースでは、道路形状パターンを作成しない。次いで、各々の道路形状パターンと、ノード１（ＷＰ１）、ノード２（ＷＰ２）、‥の形状とを比較し、最も似通った道路形状パターン、即ち、距離が近く、標準偏差等によって評価したＷＰ１、ＷＰ２、‥の形状とのばらつきが小さいものを一つ選出する。

こうして、道路形状データブロックのマップマッチングにより、対象道路ブロックが特定される。
切断形状補正・交通情報重畳部２０は、対象道路ブロックが隣の対象道路ブロックと接続するように、各対象道路ブロックの端における“ずれ”を補正する。

一方、交通情報編集部１９は、形状データ切断部１４から道路形状データの切断単位の情報を取得して、受信した交通情報を、各道路形状データブロックと整合が取れるように編集する。
切断形状補正・交通情報重畳部２０は、交通情報編集部１９がブロック単位に編集した交通情報を取得して、端点を補正した対象道路ブロックに重畳し、ブロック単位の交通情報を再現する。

図１１のフロー図は、交通情報の再現に至る手順を示している。
データを受信すると（ステップ２１）、形状データ切断部１４が、道路形状データの切断単位を決定し（ステップ２２）、道路形状データを道路形状データブロックに切断する。交通情報編集部１９は、各々の道路形状データブロックと整合が取れるように交通情報を編集する（ステップ２３）。なお、道路形状データが前述する（ａ−６）（道路形状データを、交通情報の分割単位に合わせて切断する）の方式で切断される場合は、交通情報の編集は必要がない。

ノード間引き処理部１５、候補点検索範囲決定部１６、及び、形状パターン生成・評価部１８は、ブロック番号ｎ＝１の道路形状データブロックから順に、前述する処理を行い、マップマッチングを実施して、道路形状データブロックｎの対象道路ブロックｎを特定する（ステップ２５）。全ての道路形状データブロックに対してステップ２５の処理が終了すると（ステップ２６、ステップ２７）、切断形状補正・交通情報重畳部２０は、各対象道路ブロックの端点の接続性をチェックし（ステップ２８）、対象道路ブロック端点に“ずれ”がある場合は、補正処理を行う（ステップ２９）。

図１２は、対象道路ブロック端点のずれに対する補正処理を模式的に示している。道路形状データブロックを個別にマップマッチングし（ａ）、対象道路ブロックの端点にずれがある場合は（ｂ）、双方の対象道路ブロックにおける端点の中点を、対象道路ブロックの端点として設定する（ｃ）。

この補正処理は、道路形状データブロックＮの始端側のマップマッチング後の緯度・経度を（Ｘ１,Ｙ１）、道路形状データブロック（Ｎ＋１）の終端側のマップマッチング後
の緯度・経度を（Ｘ２,Ｙ２）とするとき、Ｘ＝（Ｘ１+Ｘ２）/２、Ｙ＝（Ｙ１+Ｙ２）/
２と最も近い道路上の地点Ｘ’,Ｙ’を対象道路ブロックの端点とする処理である。
切断形状補正・交通情報重畳部２０は、端点を補正した各対象道路ブロックに対して、交通情報編集部１９が編集した交通情報を重畳して、ブロック単位の交通情報を再現する（ステップ３０）。

このように、道路形状データのマップマッチングに際して、
（１）道路形状データの分割
（２）道路形状データからのノードの間引き
（３）候補点検索範囲の適応的設定
を行うことにより、処理効率が向上し、処理時間が短縮され、また、使用メモリ量が少なくて済む。

ここでは、道路形状データのマップマッチングに当たり、前記（１）、（２）、（３）の全てを実施する場合について説明したが、このうちの一つ、あるいは、二つを実施するだけでも、処理効率の向上、処理時間の短縮、及び、使用メモリ量の減少が実現できることは明らかである。

（第２の実施形態）
本発明の第２の実施形態では、図３の情報処理装置１０の候補点検索範囲決定部１６で行われる候補点検索範囲の適応的設定処理に関する他の方法について説明する。
受信側が送信側から送られた道路形状データを用いてマップマッチングを行い、自己のデジタル地図上で道路区間を特定する場合は、送信側が道路形状データの作成に用いたデジタル地図データと受信側がマップマッチングに用いたデジタル地図データとが似通っていれば、ＷＰとそれから特定される対象道路（「真の道路」）上の候補点との差異は小さくなり、似通っていなければ、この差異は大きくなる。

ＷＰと「真の道路」上の候補点との差異は、送信側及び受信側の双方の地図における縮尺差（１／２５，０００、１／１０，０００、１／２，５００等）や地図作成者の作成ルールの違いによるところが大きい。例えば、Ａ社の１／２，５００地図から生成した道路形状データをＢ社の１／２，５００地図にマップマッチングする場合は、ＷＰと「真の道路」上の候補点との誤差が場所によらず数ｍであり、Ａ社の１／２５，０００地図から生成した道路形状データをＢ社の１／２，５００地図にマップマッチングする場合は、数十ｍの誤差が発生する。
そのため、受信側では、送信側の地図データの状況（縮尺や地図作成ルール等）に応じて、マップマッチングにおける候補点検索範囲を変えることができる筈である。

一般に受信側では、送信側の地図データの状況を知るよしも無いが、道路形状データを分割してマップマッチングする場合は、既にマップマッチングが成功した区間の、道路形状データと特定道路との間の誤差状況から、平均的な誤差発生状況を学習し、その学習結果に基づいて、以降の区間でのマップマッチングにおける候補点検索範囲を適応的に設定することが可能になる。

図１３は、この模様を模式的に示している。図１３（ａ）に示すように、道路形状データの分割区間１に対しては、あらかじめ決めたデフォルトサイズの候補点検索範囲に含まれる候補点を検索し、「真の道路」を特定する。分割区間１のマップマッチングが終了すると、図１３（ｂ）に示すように、「真の道路」上の各ノード（ノードＡ、ノードＢ）におけるＷＰとの誤差距離を算出し、平均・最大・最小誤差距離等を算出する。道路形状データの分割区間２に対しては、図１３（ｃ）に示すように、分割区間１での平均・最大・最小誤差距離等を基に、候補点検索範囲を調整し最適化する。

このように、道路形状データの一部分における誤差発生状況から、道路形状データのその他の部分における誤差発生状況を推定して候補点検索範囲を設定することにより、「送受信間の地図差異が小さいほど、マップマッチングの処理時間は短くなり、大きいほど処理時間は長くなる。」という、理にかなった動作が適応的に実現できる。

なお、図１３では、候補点検索範囲を矩形で表示しているが、候補点検索の角度範囲を示す候補点検索方位範囲を決定する場合も同様であり、ここで言う候補点検索範囲には候補点検索方位範囲も当然含まれる。

図１４は、候補点検索範囲決定部１６が、道路形状データの一部分における誤差発生状況から、道路形状データのその他の部分における誤差発生状況を推定して候補点検索範囲を適応的に設定する場合の処理フローを示している。
候補点検索範囲の設定に関する各種パラメータ（ＷＰからの距離、τ、γ等）を初期値にリセットし（ステップ３１）、最初（Ｍ＝１）の道路形状データＭに着目して（ステップ３２）、道路形状データＭを分割し（ステップ３３）、その最初（Ｍｎ＝Ｍ１）の道路形状データブロックＭｎを対象として（ステップ３４）、そのブロックＭｎの道路形状データを取得し（ステップ３５）、マップマッチングを行い（ステップ３６）、マップマッチングが成功したか否かを判定する（ステップ３７）。適切な候補点が得られず、マップマッチングに失敗したときは、検索範囲が拡がるようにパラメータを変更し（ステップ３８）、マップマッチングをやり直す。

マップマッチングに成功したときは（ステップ３７でＹｅｓの場合）、道路形状データとそれを用いて特定した道路との誤差を算出し（ステップ３９）、誤差の状況からパラメータを更新する（ステップ４０）。

例えば、各ＷＰの誤差（ＷＰと「真の道路」上の候補点との距離）をＤｉとするとき、候補点検索範囲を規定するＷＰからの距離を、次のように設定する。
・Ｄｉにおける最大誤差ＤｍａｘのＰ倍に設定する。
・Ｄｉの平均Ｄａｖｅｒａｇｅ＋２σに設定する（母数全体の９８％が候補点検索範囲に入る水準）。
・Ｄａｖｅｒａｇｅ＋Ｐ・σに設定する（Ｐは、母数全体のＮ％が候補点検索範囲に入るように調整する定数）。

道路形状データＭの次の道路形状データブロックに対しては、更新したパラメータを用いてステップ３５〜４０の処理を行い、こうした手順を道路形状データＭの全ての道路形状データブロックＭｎに対して繰り返す（ステップ４１、４２）。道路形状データＭの全ての道路形状データブロックＭｎに対する処理が終了したときは、次回以降のマップマッチング用パラメータを更新して（ステップ４３）、次の道路形状データを対象としてステップ３３〜４３の処理を行い、こうした手順を道路形状データＭの全てに対して繰り返す（ステップ４４、４５）。

こうした手順で、道路形状データの一部分の誤差発生状況に基づいて、道路形状データのその他の部分での候補点検索範囲を適応的に設定することができる。
なお、地図間の距離誤差の発生状況は、高速道路か否か、本線か連絡路か等々の道路属性により変わるケースが多いため、候補点検索範囲のパラメータ調整は、道路属性等の分類単位に行うという方法も考えられる。

また、地図間での角度誤差の発生状況は、偏角の大きさにより大きく変わるため、道路形状データの偏角絶対値の分類（１０°以内、１０〜４５°、４５°以上等）単位に候補点検索範囲のパラメータ調整を行うという方法も考えられる。

なお、各実施形態では、道路形状データをマップマッチングする場合について説明したが、本発明のマップマッチング方法は、道路だけで無く、鉄道、水路、等高線、行政境界等の形状データを用いて、それらの線形形状をデジタル地図上に対応付けるマップマッチングにも適用できる。

本発明のマップマッチング方法は、マップマッチングに際して、省メモリや処理の高速化が必要な全ての分野で利用することができ、例えば、交通情報提供システムやプローブ情報の収集システム、鉄道・水路・等高線・行政境界等の地図データを提供するシステムなどで、幅広く利用することができる。
また、本発明の装置は、交通情報を受信して再現するカーナビゲーション装置、ＰＣ、ＰＤＡ、携帯電話等の情報端末、あるいは、プローブカー情報を収集するプローブ情報収集センタ等、マップマッチングを実施する多くの装置に適用することができる。

本発明の第１の実施形態におけるマップマッチング方法での道路形状データの分割処理を説明する図 本発明の第１の実施形態における道路形状データの分割処理で使用メモリ量が少なくなる状況を説明する図 本発明の第１の実施形態におけるマップマッチング方法を実施する装置の構成を示すブロック図 地図データのユニットを示す図 本発明の第１の実施形態における道路形状データの分割処理によりユニットの使用枚数が減る理由を説明する図 道路形状データを表示した地図の例 本発明の第１の実施形態におけるマップマッチング方法でのノードの間引き処理を説明する図 本発明の第１の実施形態におけるノードの間引き処理手順を示すフロー図 本発明の実施形態における候補点検索方位範囲の適応的設定手順を示すフロー図 本発明の第１の実施形態における候補点検索方位範囲の適応的設定で得られる候補点を説明する図 本発明の第１の実施形態におけるマップマッチング方法で交通情報との整合を取る手順を示すフロー図 本発明の第１の実施形態におけるマップマッチング方法での対象道路ブロックの端点の補正処理を示す図 本発明の第２の実施形態における候補点検索範囲の適応的設定方法を模式的に説明する図 本発明の第２の実施形態における候補点検索範囲の適応的設定手順を示すフロー図 道路形状データを説明する図 道路形状データの符号化のための処理を説明する図 従来のマップマッチング方法を示す図

符号の説明

１０ マップマッチング型情報処理装置
１１ 形状データ・交通情報受信部
１２ 符号化データ復号部
１３ 形状データ復元部
１４ 形状データ切断部
１５ ノード間引き処理部
１６ 候補点検索範囲決定部
１７ デジタル地図データベース
１８ 形状パターン生成・評価部
１９ 交通情報編集部
２０ 切断形状補正・交通情報重畳部
２１ 情報活用部

Claims (5)

1. 情報受信装置が、情報送信装置から対象道路区間におけるノードの位置データ列によって表される道路形状データを受信して、デジタル地図上に前記道路形状データに対応する対象道路区間を特定する方法であって、
   前記情報受信装置の受信部が、前記ノードの位置データ列によって表される道路形状データを受信するステップと、
   前記情報受信装置の形状データ切断部が、前記受信した道路形状データを所定の条件で切断して、前記切断した各々のノードの位置データ列からなる道路形状データをブロック化するステップと、
   前記情報受信装置のマップマッチング処理部が、前記ブロック化した道路形状データ毎に、当該ノードの位置データと前記デジタル地図上の位置データとのマッチング処理をおこなって道路区間を特定するステップと、
   前記情報受信装置の候補点検索範囲決定部が、前記マップマッチング処理部によるマッチング処理において、ブロック化された道路形状データのノードに対する前記デジタル地図上の候補点を検索する範囲を、ブロック化された道路形状データに対応する道路区間の曲がり具合に応じて設定するステップと、
   を備える方法。
2. 請求項１記載の方法であって、
   前記候補点検策範囲決定部は、ブロック化された道路形状データの単位面積当たりの道路延長を示す値をも考慮して、前記デジタル地図上の候補点を検索する範囲を決定する方法。
3. 請求項１記載の方法であって、
   前記候補点検策範囲決定部は、ブロック化された道路形状データの隣接するノード間の偏角絶対値を算出して、前記デジタル地図上の候補点を検索する範囲を決定する方法。
4. 情報送信装置から対象道路区間におけるノードの位置データ列によって表される道路形状データを受信して、デジタル地図上に前記道路形状データに対応する対象道路区間を特定する情報受信装置であって、
   前記ノードの位置データ列によって表される道路形状データを受信する受信部と、
   前記受信した道路形状データを所定の条件で切断して、前記切断した各々のノードの位置データ列からなる道路形状データをブロック化する形状データ切断部と、
   前記ブロック化した道路形状データ毎に、当該ノードの位置データと前記デジタル地図上の位置データとのマッチング処理をおこなって道路区間を特定するマップマッチング処理部と、
   前記マップマッチング処理部によるマッチング処理において、ブロック化された道路形状データのノードに対する前記デジタル地図上の候補点を検索する範囲を、ブロック化された道路形状データに対応する道路区間の曲がり具合に応じて設定する候補点検索範囲決定部と、
   を備える情報受信装置。
5. 請求項４記載の情報受信装置に、前記道路形状データを送信する情報送信装置。