道路推定装置
【課題】 配信されるコアポイントの情報から、車載機側に用意される地図データ上で該当するリンクを適切に抽出し、コアポイントが示す道路を推定する道路推定装置を提供する。
【解決手段】 候補リンク検索処理において、ＣＰ（コアポイント）の情報を取得し（Ｓ２１０）、検索範囲を境界が垂直又は水平の線分で構成される多角形として決定する（Ｓ２２０）。最初に、検索範囲のパーセルを取得して（Ｓ２３０）、パーセル単位でリンク列を選定する（Ｓ２４０）。その後、検索範囲に少なくとも一部が含まれるリンクを抽出し（Ｓ２５０）、属性ＲＤ及びＣＰからリンクまでの距離に基づいて、リンクを絞り込む（Ｓ２６０，Ｓ２７０）。
【解決手段】 候補リンク検索処理において、ＣＰ（コアポイント）の情報を取得し（Ｓ２１０）、検索範囲を境界が垂直又は水平の線分で構成される多角形として決定する（Ｓ２２０）。最初に、検索範囲のパーセルを取得して（Ｓ２３０）、パーセル単位でリンク列を選定する（Ｓ２４０）。その後、検索範囲に少なくとも一部が含まれるリンクを抽出し（Ｓ２５０）、属性ＲＤ及びＣＰからリンクまでの距離に基づいて、リンクを絞り込む（Ｓ２６０，Ｓ２７０）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道路に沿って付与され、当該道路を特定するための属性を有するコアポイントに基づき、当該コアポイントが示す道路に該当する地図上のリンクを抽出する技術に関する。
【背景技術】
【０００２】
従来、交通情報を放送により転送するサービスとして、ＶＩＣＳ（Vehicle Information and Communication System）が知られている。このサービスは、ＶＩＣＳセンターの持つ道路の渋滞情報などの交通情報を車両に送信し、車両側で地図データを検索して該当する道路を特定し、当該道路の表示態様を、受信した交通情報に応じて変更し、ユーザに提供するものである。これにより、ユーザは、渋滞情報などの交通情報をリアルタイムに把握することができる。
【０００３】
ところで、車載機側の地図データのフォーマットでは、例えば道路がリンクで表現される。ここで、上述のＶＩＣＳセンターからは、道路を特定するＶＩＣＳリンクと呼ばれる情報が送信される。このＶＩＣＳリンクには、様々な交通情報や表示態様の変更指示情報が付与されている。そこで、車載機側では、ＶＩＣＳリンクと地図データにおけるリンクとを照合するための位置参照テーブルを持っており、このテーブルに基づき、ＶＩＣＳリンクに対応するリンクを検索する。つまり、ＶＩＣＳでは、位置参照テーブルが必須となっている（例えば、特許文献１，２参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−２７５７７７号公報（図３）
【特許文献２】特開２００９−２７０９５３号公報（図２，図３１）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、ＶＩＣＳ以外のサービスとして、ＴＰＥＧ（Transport Protocol Expert Group ）により送信される交通情報のデータを車両などの端末側で活用することが検討されている。しかし、ＴＰＥＧにより送信されるデータフォーマット等では、例えばＤＬＲデータの形式で位置情報が示される。この位置情報は、位置座標を有すると共に道路を特定するための属性を有するコアポイントで構成される。コアポイントは、通常、道路に沿って並ぶ複数個の配列として配信される。このようなコアポイントによって位置情報を示すようにすれば、地図データを作成するメーカの違いや地図データのフォーマット、バージョンに依存する位置参照テーブルが不要になる。すなわち、車載機側の地図データに依存せず、地図データ上で道路（リンク）を特定することが可能となる。
【０００６】
その反面、コアポイントに基づいて道路を特定するための種々の処理が必要になってくる。例えば、上述したように地図データにもいろんな種類があるため、必ずしもコアポイントは地図データの道路上に存在しない。そのため、コアポイントが示す道路に該当するリンクを地図上で特定する処理が必要となってくる。
【０００７】
しかしながら、コアポイント周辺のリンクを候補として抽出する際、抽出するリンク数が多くなれば抽出処理に要する時間が長くなる虞がある。また、抽出するリンク数が少なくなればコアポイントが示す道路に該当するリンクが候補から外れる虞がある。
【０００８】
本発明は、上述した問題を解決するためになされたものであり、配信されるコアポイントの情報から、車載機側に用意される地図データ上で該当するリンクを適切に抽出し、コアポイントが示す道路を推定する道路推定装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した目的を達成するためになされた請求項１に記載の道路推定装置は、道路に沿って付与され当該道路を特定するための属性を有するコアポイントに基づき、当該コアポイントが示す前記道路に該当する地図上のリンクを抽出することで道路を推定するものである。なお、コアポイントは配列として複数送信されるのが一般的であるが、コアポイントが一つだけ送信される場合も含む。
【００１０】
本装置では、地図データ入力手段が、地図データを入力する。地図データは、コアポイントの有する属性に応じた属性を有するリンクで構成される。
また、検索範囲設定手段が、コアポイントを基準にして検索範囲を設定する。この検索範囲が、後述するようにリンク抽出の範囲となるものである。「コアポイントを基準」にする場合、例えばコアポイントを中心とした検索範囲を設定することが考えられる。コアポイントを中心とすれば、妥当な検索範囲が設定されるためである。ただし、必ずしもコアポイントを中心とする必要はなく、中心から外れた位置にコアポイントが位置するような検索範囲を設定してもよい。
【００１１】
このとき、リンク抽出手段によって、地図データ入力手段にて入力された地図データを構成するリンクのうちで、検索範囲に含まれるリンクが抽出される。そして、抽出されたリンクの有する属性とコアポイントの有する属性とに基づき、コアポイントが示す道路を推定する。
【００１２】
つまり、コアポイントで示される道路に該当するリンクを抽出するにあたり、コアポイント周辺のリンクを抽出するのであるが、このときコアポイントを基準とする検索範囲を設定することにより、妥当な距離にあるリンクを抽出するのである。これにより、抽出するリンク数が多くなりすぎて抽出処理に要する時間が長くなったり、また、抽出するリンク数が少なすぎてコアポイントが指し示す道路に該当するリンクが候補から外れたりすることを抑制できる。その結果、配信されるコアポイントの情報から、車載機側に用意される地図データ上で該当するリンクを適切に抽出し、コアポイントが示す道路を推定することができる。
【００１３】
なお、「検索範囲に含まれるリンク」は、検索範囲に完全に含まれるリンクをいうものとすることが考えられる。ただし、コアポイントが指し示す道路に該当するリンクが候補から外れるという事態を極力なくすという観点からは、検索範囲を比較的大きく設定する必要が生じる。この場合、抽出処理に要する時間が長くなることが懸念される。
【００１４】
そこで、請求項２に示すように、リンク抽出手段が、地図データを構成するリンクのうちで、検索範囲に少なくとも一部が含まれるリンクを抽出することとしてもよい。このようにすれば、比較的小さな検索範囲を設定することができ、抽出処理に要する時間を短くできると共に、コアポイントが指し示す道路に該当するリンクが候補から外れるという事態を極力なくすことができる。
【００１５】
なお、当初からリンク単位での抽出を行うと、リンクの数が多くなってしまい、抽出処理に要する時間が長くなる虞がある。そこで、リンク抽出手段によるリンクの抽出に先立って、リンク列を選定するようにしてもよい。「リンク列」とは、同一の道路区分となっている一連のリンク群をいう。例えば請求項３に示すように、リンク列選定手段が、検索範囲に基づき、地図データ入力手段にて入力された地図データのリンクの配列であるリンク列を選定する。このとき、リンク抽出手段は、リンク列選定手段にて選定されたリンク列を構成するリンクの中から検索範囲に含まれるリンクを抽出する。このように最初にリンク列を選定すれば、リンク単位での処理を減らすことができ、抽出処理に要する時間を短縮することができる。
【００１６】
また、リンク列の選定にあたって当該リンク列が検索範囲に含まれるか否かを判断するようにしてもよいが、処理が煩雑になる虞がある。そこで、請求項４に示すように、分割領域特定手段が検索範囲に少なくとも一部が含まれる分割領域である検索対象分割領域を特定するようにし、リンク列選定手段によって、検索対象分割領域に少なくとも一部が含まれるリンク列が選定されるようにするとよい。つまり、ここでは、リンク列が分割領域の単位で選定されるのである。このようにすれば、リンクの抽出に先立つリンク列の選定を迅速に行うことができる。
【００１７】
このようにリンク列を抽出する際、請求項５に示すように、検索対象分割領域に一部が含まれるリンク列から、コアポイントの有する非形状系の属性である道路のクラスを示す道路区分（属性ＦＣ）、道路の種別を示す物理道路タイプ（属性ＦＷ）、及び、道路番号又は道路名称を示す道路固有情報（属性ＲＤ）の少なくともいずれかが一致するリンク列を選定することが考えられる。このとき、請求項６に示すように、検索範囲に含まれるか否かの判断に先立って、コアポイントの有する非形状系の属性によってリンク列を絞り込むようにするとよい。このようにすれば、リンクの抽出に先立つリンク列の選定をより一層迅速に行うことができる。なお、コアポイントの属性ＲＤの値は、道路番号が存在すれば道路番号となっており、存在しなければ道路名称（道路の公式名の最大５文字）となっている。
【００１８】
ところで、上述したようにコアポイントを基準として検索範囲を設定する際、コアポイントから等距離にある範囲を設定することが好ましい。したがって、コアポイントを中心とする円を検索範囲とすることが考えられる。しかし、検索範囲を円とした場合、境界などの算出処理が煩雑になり、検索範囲に含まれるか否かの判断が複雑になる。
【００１９】
そこで、請求項７に示すように、その境界が垂直又は水平の線分で構成される多角形を検索範囲として設定するようにするとよい。例えば、図１３（ａ）に示すごとくである。
図１３（ａ）に示すように十字形と正方形とを合成した検索範囲を設定すれば、コアポイントから妥当な距離にあるリンクを抽出でき、しかも、境界などの算出処理が煩雑にならず、検索範囲に含まれるか否かの判断が容易になる。もちろん、図１３（ａ）に示した形状には限定されず、さらに境界を構成する線分が多い多角形の検索範囲を設定してもよいし、正方形や長方形などの検索範囲を設定するようにしてもよい。
【００２０】
なお、リンク抽出手段がリンクを抽出する際、コアポイントが交差点を示すものであるか否かによって、比較的容易にリンクを抽出することができる。
具体的には、請求項８に示すように、リンク抽出手段は、コアポイントが道路の交差点を示すものである場合、交差点を端点とするリンクであって、当該端点が検索範囲に含まれるリンクを抽出することが例示される。通常の地図データでは、リンクの端点が交差点となる。例えばリンクの端点にノードを有する地図データでは、交差点に対してノードが設定されるという具合である。したがって、コアポイントが交差点を示すものであれば、リンクの端点と対応付けられる。したがって、交差点を端点とし当該端点が検索範囲に含まれるリンクを抽出することが考えられる。このようにすれば、妥当なリンクを抽出できる可能性が高くなる。
【００２１】
一方、請求項９に示すように、リンク抽出手段は、コアポイントが道路の交差点を示すものでない場合、リンクの端点が検索範囲に含まれない場合であっても、リンクの一部が検索範囲に含まれていれば、当該リンクを抽出することが例示される。例えばリンクに形状補間点が設定されることを前提とし、形状補間点が検索範囲にあれば、そのリンクを抽出することが考えられる。また、形状補間点がない場合、端点を結ぶリンクの一部が検索範囲に含まれていれば、そのリンクを抽出することが考えられる。このようにすれば、妥当なリンクを抽出できる可能性が高くなる。
【００２２】
また、リンク抽出手段がリンクを抽出する際、その前提として仮想コアポイントを付与する構成であれば、比較的容易にリンクを抽出することができる。
具体的には、請求項１０に示すように、地図データ入力手段が、分割領域の単位で、分割領域の境界に端点を有するリンクで構成される地図データを入力する。このとき、コアポイントに基づき、分割領域の境界に新たなコアポイントである仮想コアポイントを付与することを前提に、リンク抽出手段は、コアポイントが仮想コアポイントである場合、分割領域の境界に端点を有するリンクであって、当該端点が検索範囲に含まれるリンクを抽出することが考えられる。通常の地図データでは、分割領域の境界にリンクの端点が設定される。例えばリンクの端点にノードを有する地図データでは、分割領域の境界にノードが設定されるという具合である。したがって、コアポイントが仮想コアポイントであれば、分割領域境界のどこかにあるリンクの端点と対応付けられる。したがって、交差点を端点とし当該端点が検索範囲に含まれるリンクを抽出することが考えられる。このようにすれば、妥当なリンクを抽出できる可能性が高くなる。
【００２３】
一方、請求項１１に示すように、リンク抽出手段は、コアポイントが仮想コアポイントでない場合、リンクの端点が検索範囲に含まれない場合であっても、リンクの一部が検索範囲に含まれていれば、当該リンクを抽出することが例示される。例えばリンクに形状補間点が設定されることを前提とし、形状補間点が検索範囲にあれば、そのリンクを抽出することが考えられる。また、形状補間点がない場合、端点を結ぶリンクの一部が検索範囲に含まれていれば、そのリンクを抽出することが考えられる。このようにすれば、妥当なリンクを抽出できる可能性が高くなる。
【００２４】
ところで、検索範囲の全てのリンクを抽出しようとした場合、リンクの数が多くなってしまう虞がある。
そこで、例えば請求項１２に示すように、リンク抽出手段は、コアポイントの非形状系の属性である道路番号又は道路名称を示す道路固有情報（属性ＲＤ）に基づき、検索範囲に基づいて抽出されるリンクを絞り込むようにしてもよい。
【００２５】
上述したように、コアポイントの属性ＲＤの値は、道路番号が存在すれば道路番号となっており、存在しなければ道路名称（道路の公式名の最大５文字）となっている。したがって、この属性ＲＤの値によって、リンクを絞り込むようにしてもよい。このようにすれば、妥当なリンクを抽出できる可能性が高くなる。
【００２６】
また、例えば請求項１３に示すように、リンク抽出手段は、コアポイントまでの距離に基づき、検索範囲に基づいて抽出したリンクを絞り込むようにしてもよい。例えばコアポイントからリンクに下ろした垂線の長さによって、所定本数（例えば、１０本）のリンクに絞り込むことが考えられる。このようにすれば、適切にリンクを絞り込むことができ、妥当なリンクを抽出できる可能性が高くなる。
【図面の簡単な説明】
【００２７】
【図１】ナビゲーション装置の構成を示すブロック図である。
【図２】制御回路の動作を示す機能ブロック図である。
【図３】マッチング処理を示すフローチャートである。
【図４】変換後のＣＰの属性を示す説明図である。
【図５】属性ＦＣの値と内容とを示す説明図である。
【図６】属性ＦＷの値と内容とを示す説明図である。
【図７】属性ＩＴの値と内容とを示す説明図である。
【図８】マッチング処理における変換処理を示すフローチャートである。
【図９】対象パーセルに跨ってＣＰが存在することを示す説明図である。
【図１０】仮想ＣＰの付与及びパーセル境界における処理を示す説明図である。
【図１１】属性ＰＣＩの計算ルールを示す説明図である。
【図１２】マッチング処理における候補リンク検索処理を示すフローチャートである。
【図１３】対象ＣＰに対する検索範囲及びパーセル取得を示す説明図である。
【図１４】候補リンク検索処理でのリンク列選定処理を示すフローチャートである。
【図１５】検索範囲に対するリンク列の抽出を示す説明図である。
【図１６】マッチング処理における候補選定処理を示すフローチャートである。
【図１７】候補選定処理での非形状系属性の一致判定を示すフローチャートである。
【図１８】候補選定処理での形状系属性の一致判定を示すフローチャートである。
【図１９】属性ＢＲに基づく一致判定を示す説明図である。
【図２０】形状系属性の一致判定における属性ＰＣＩでの一致判定を示すフローチャートである。
【図２１】属性ＣＡ及び属性ＤＣＡに基づく一致判定を示す説明図である。
【図２２】マッチング処理における道路マッチング処理を示すフローチャートである。
【図２３】道路探索の省略方法を示す説明図である。
【図２４】道路探索の省略方法を示す説明図である。
【図２５】道路探索の中止方法を示す説明図である。
【図２６】道路マッチング処理での候補選定を示すフローチャートである。
【図２７】属性ＣＡ及び属性ＤＣＡに基づく道路選定を示す説明図である。
【図２８】属性ＢＲ及び属性ＤＭＢに基づく道路選定を示す説明図である。
【図２９】属性ＰＤに基づく道路長の算出を示す説明図である。
【図３０】属性ＰＤに基づく道路選定を示す説明図である。
【図３１】属性ＰＤＭに基づく道路選定を示す説明図である。
【図３２】道路の決定方法を示す説明図である。
【発明を実施するための形態】
【００２８】
以下に本発明の実施例について、図面と共に説明する。
＜１．ナビゲーション装置の構成＞
最初にナビゲーション装置の構成を図１に基づいて説明する。図１に示すナビゲーション装置１０が「道路推定装置」として機能し、具体的には、ＴＰＥＧ（Transport Protocol Expert Group ）データを受信し、データ中の位置情報から道路のマッチングを行い、位置情報と共に送信される交通情報を道路に対応させて表示する。
【００２９】
図１に示すナビゲーション装置１０は、受信装置１１、位置検出装置１２、地図データ入力装置１３、操作デバイス１４、音声出力デバイス１５、表示デバイス１６、及び、制御回路１７を備えている。
【００３０】
受信装置１１は、センタ２０からＴＰＥＧデータを受信するためのものである。ナビゲーション装置１０では、制御回路１７にて選局を行うことにより、受信装置１１を介してＴＰＥＧデータを取得する。
【００３１】
位置検出装置１２は、ナビゲーション装置１０を搭載した車両の現在位置を検出するためのものであり、例えば、周知のジャイロスコープ、距離センサ及びＧＰＳ受信機等を有している。
【００３２】
地図データ入力装置１３は、地図データが格納された記録媒体（具体的にはハードディスクやＤＶＤ）を有するものであり、この記録媒体に格納された地図データを制御回路１７に入力可能に構成されている。なお、地図データ入力装置１３は、地図データを記憶保持するハードディスク装置に加えてＤＶＤドライブを備えた構成にすることができる。このように地図データ入力装置１３を構成すれば、ナビゲーション装置１０は、ＤＶＤメディアを通じてオプション販売される地図データの追加データを、ハードディスク装置にインストール可能な構成にすることができる。なお、地図データは、パーセルと呼ばれる単位で管理され、パーセル単位でキャッシュされる。
【００３３】
操作デバイス１４は、ユーザからの指示を制御回路１７に入力するためのものであり、表示デバイス１６に配置されたタッチパネルや、ナビゲーション装置１０の本体表面やリモートコントローラに設けられた操作スイッチ群等により構成される。この操作デバイス１４を通じて、ユーザは、地図の縮尺変更やスクロール等の操作や目的地設定などナビゲーション装置１０のあらゆる操作を行うことが可能である。
【００３４】
また、音声出力デバイス１５は、スピーカ等から構成され、制御回路１７からの信号を受けてユーザへの案内音声等を出力するものである。この他、表示デバイス１６は、フルカラー表示が可能なものであり、この表示デバイス１６には、受信装置１１を介して取得されるＴＰＥＧデータに基づく交通情報が、地図データ入力装置１３より入力された地図データに基づく地図画像に重ねて表示される。
【００３５】
また、制御回路１７は、周知のマイクロコンピュータと同様の構成となっており、内部にＣＰＵ１７ａ、ＲＯＭ１７ｂ、ＲＡＭ１７ｃ、Ｉ／Ｏ及びこれらの構成を接続するバスラインなどを備える。そして、ＣＰＵ１７ａは、ＲＯＭ１７ｂに記憶されているプログラムに従って、種々の処理を行う。例えば、受信装置１１を介して受信されるＴＰＥＧデータにはＤＬＲ（Dynamic Location Referencing）データとしての位置情報が含まれる。したがって、制御回路１７は、この位置情報を基に、地図データ側で該当する道路（リンク）を推定する。
＜２．制御回路の機能＞
次に、ＴＰＥＧデータの処理に関する制御回路１７の機能を、図２に基づいて説明する。図２は、制御回路１７の機能を模式的に示す説明図である。
【００３６】
制御回路１７の機能は、選局ブロック１７１、アプリケーションブロック１７２、ＤＬＲライブラリブロック１７３、及び、描画ブロック１７４に分けられる。
選局ブロック１７１は、上述した受信装置１１を介し、ＴＰＥＧデータを受信するブロックである。つまり、選局ブロック１７１が、上述した選局機能を有している。受信されるＴＰＥＧデータは、選局ブロック１７１からアプリケーションブロック１７２へ渡される。
【００３７】
アプリケーションブロック１７２は、アプリケーションプログラムの機能として実現される。アプリケーションプログラムは、ＲＯＭ１７ｂに記憶されており、ＣＰＵ１７ａによって実行される。
【００３８】
アプリケーションブロック１７２は、選局ブロック１７１から受け渡されるＴＰＥＧデータを管理し、新たなＴＰＥＧデータが受信されると、ＴＰＥＧデータの更新を行う。また、アプリケーションブロック１７２は、画面に表示される表示対象のパーセル（以下「対象パーセル」という）を特定するための情報を有している。表示画面は、縮尺によって１つの対象パーセルで構成されることもあるし、複数（例えば９つ）の対象パーセルで構成されることもある。アプリケーションブロック１７２は、対象パーセルの情報、及び、ＴＰＥＧデータの位置情報を「対象データ」としてＤＬＲライブラリブロック１７３へ渡す。
【００３９】
ＤＬＲライブラリブロック１７３は、ＤＬＲライブラリプログラムの機能として実現される。ＤＬＲライブラリプログラムは、アプリケーションプログラムと同様、ＲＯＭ１７ｂに記憶されており、ＣＰＵ１７ａによって実行される。
【００４０】
ＤＬＲライブラリブロック１７３は、後述するマッチング処理を実行する。マッチング処理は、ＴＰＥＧデータの位置情報に基づき、地図データ入力装置１３から入力される地図データでの該当する道路（リンク）を推定するものである。このようなマッチング処理に先立ち、ＤＬＲライブラリ１７３は、アプリケーションブロック１７２からの要請により、地図データ入力装置１３から地図データをＲＡＭ１７ｃに読み込む。マッチング処理の結果は、ＤＬＲライブラリ１７３により、マッチング結果としてアプリケーションブロック１７２へ出力される。
【００４１】
アプリケーションブロック１７２は、マッチング結果を管理する。そして、描画ブロック１７４によって、マッチング結果に基づく地図更新が行われる。これにより、上述したように、ＴＰＥＧデータに基づく交通情報が、地図データ入力装置１３より入力された地図データに基づく地図画像に重ねて表示される。
＜３．マッチング処理＞
本実施例は、ＤＬＲライブラリブロック１７３によるマッチング処理に特徴を有している。そこで、次にマッチング処理について説明する。図３は、マッチング処理を示すフローチャートである。
【００４２】
最初のＳ１００では、変換処理を行う。この変換処理は、ＴＰＥＧデータのＤＬＲとしての位置情報（バイナリデータ）を、中間データに変換するものである。ＴＰＥＧデータの位置情報には離散的な地点が主として用いられることは既に述べたが、これらの離散的な地点は、コアポイント（以下「ＣＰ」という）と呼ばれる。そして、ＣＰは、様々な属性を有している。そこで、ここでは、道路推定に必要な属性を取り出して、中間データを作成する。
＜３．１ 変換後のＣＰの属性＞
中間データへの変換後のＣＰが有する属性を図４に示す。通常、複数個のＣＰがＴＰＥＧデータの位置情報として送信される。したがって、ＣＰは配列して管理される。もちろん、一つだけのＣＰから位置を推定することも可能であり、ＣＰが一つだけ送信される場合を排除する趣旨ではない。
【００４３】
ＣＰは、基本的な属性として、図４に示すように、緯度、経度、ＩＰフラグ、仮想ＣＰフラグを有している。緯度は、ＣＰの緯度座標であり、経度は、ＣＰの経度座標である。また、ＩＰフラグは、ＣＰが交差点か否かを示すフラグである。ＣＰが交差点を示す場合には「１」がセットされ、それ以外の場合には「０」がセットされる。さらにまた、仮想ＣＰフラグは、ＣＰが仮想ＣＰか否かを示すフラグである。ＣＰが仮想ＣＰである場合には「１」がセットされ、それ以外の場合には「０」がセットされる。なお、仮想ＣＰについては後述する。
【００４４】
また、ＣＰは、ＣＰ間を繋ぐ道路に関し、種々の属性を有している。これらの属性には、道路形状に関わる形状系の属性と、道路形状に関わらない非形状系の属性とがある。まずは、非形状系の属性を説明する。
＜３．１．１ 非形状系の属性＞
属性ＦＣは、道路区分を示すものである。図５に一例を示すように、道路のクラスは、「０」〜「９」の１０段階で示される。「０」が「Main road 」であり、「１」が「First class road」であり、「２」が「Second class road 」である。以下同様に、「９」の「Ninth class road」までランク付けされている。例えば、「Main road 」は国や首都に接続されている道路であり、「first class road 」は主要都市間を結ぶ国道であるという具合に、ランク付けされている。
【００４５】
属性ＦＷは、物理道路タイプを示すものである。図６に一例を示すように、物理道路タイプは、「０」〜「１２」の１３種類に分けられている。図６を見ると、「不明確」の場合は「０」であり、「高速道路」は「１」であり、「複数車道（高速道路以外）」は「２」であり、「単一車道」は「３」であり、「ロータリー」は「４」であり、「トラフィックスクエア」は「５」であり、「取り囲まれた交通エリア」は「６」であり、「バイパス」は「７」であり、「支線道路」は「８」であり、「駐車場入口又は出口」は「９」であり、「サービスエリア入口又は出口」は「１０」であり、「歩行者地帯」は「１１」であり、「通路」は「１２」である。
【００４６】
属性ＲＤは、道路番号（例えば国道「１」号などの国道番号）が存在すれば、その道路番号がＲＤ値となる。また、道路番号が存在しない場合、道路名称がＲＤ値となる。道路名称は、公式名の最大５文字となっている（図４参照）。
【００４７】
属性ＩＴは、交差点の分類を示す（図４参照）。図７に一例を示すように、交差点の分類は、「０」〜「６」の７種類に分けられている。図７を見ると、「未定義」の場合は「０」であり、「高速又は制限された道路のインターチェンジ」は「１」であり、「ロータリー」は「２」であり、「１，２以外の複雑な交差点」は「３」であり、「単純な交差点」は「４」であり、「トラフィックスクエア」は「５」であり、「２価の交差点（道路番号や道路名称が切り替わる交差点）」は「６」である。
【００４８】
属性ＲＤＩは、交差点の名称を示す（図４参照）。
属性ＤＤは、許可された合法の運転方向を示す（図４参照）。例えば、「未定義」は「０」となっており、「順方向」が「１」となっており、同様に、「逆方向」が「２」、「両方向」が「３」となっているという具合である。なお、属性ＡＦＲは、属性ＤＤが参照可能であるか否かを示すフラグである。属性ＤＤが「０」〜「３」の値を持っている場合に属性ＡＦＲは「１」にセットされ、属性ＤＤが値を持っていない場合には、参照不可として「０」がセットされる。
＜３．１．２ 形状系の属性＞
次に形状系の属性を説明する。
【００４９】
属性ＢＲは、次のＣＰへの位置的な角度を示す（図４参照）。上述したように、通常、複数個のＣＰが配列として管理される。ＢＲ値は、真北を基準とする時計回りの角度である。
【００５０】
属性ＤＭＢは、次のＣＰへの直線距離を示す（図４参照）。属性ＢＲと同様、通常、次のＣＰが存在するため、次のＣＰへの直線距離がＤＭＢ値となっている。
属性ＣＡは、脇道に対する角度を示す。脇道とは、道路番号が付加されないようなマイナーな道路である。脇道がある場合、属性ＢＲの角度を基準に時計回りを「正」とし、反時計回りを「負」とする角度がＣＡ値として設定される。属性ＤＣＡは、脇道に対する接続距離を示す。
【００５１】
すなわち、ＣＰからのベクトルを考えた場合、属性ＣＡがベクトルの方向を示し、属性ＤＣＡがベクトルの大きさを示すことになる。したがって、属性ＣＡ及び属性ＤＣＡによって、位置座標が決定される。この位置座標が脇道の存在する地点を示すこととなる。
【００５２】
属性ＰＣＩは、同一方向において複数の車道が存在する場合、いずれの車道が選択されるかを示す（図４参照）。この属性ＰＣＩには、車道数及び、対象道路が当該車道のうちの何番目かを示すシーケンス番号が含まれる。
【００５３】
属性ＰＤＭは、次のＣＰまでを結ぶ直線からの対象道路の離間距離を示す（図４参照）。この離間距離には、対象道路までの最大距離が設定される。
属性ＰＤは、次に属性ＰＤを含むＣＰまでの対象道路に沿った道なりの運転距離を示す（図４参照）。
【００５４】
以上、中間データへの変換後のＣＰの有する属性について説明したが、このようなＣＰに対しての変換に伴い、仮想ＣＰの付与、ＣＰの属性値の再計算が実行される。具体的な手順は、図８に示すごとくである。
＜４．マッチング処理の詳細（前半）＞
図８中のＳ１１０では、対象パーセルの境界に仮想ＣＰを付与する。図９は、ＣＰによって表される道路形状を便宜的に二点鎖線で示す説明図である。もちろん、このような道路形状を推定し、地図データのリンク列で示される道路とのマッチングを行うことが終局的な目標である。したがって、図９中に二点鎖線で示す道路形状は、便宜的なものであり、実際の道路形状を示すものではない。ここで重要なのは、図９に示すように、ＣＰの配列が対象パーセルだけでなくその周囲のパーセルにも跨ることがある、ということである。このような場合に、対象パーセルの境界に仮想ＣＰを付与する。
【００５５】
具体的には、図１０（ａ）に示すように、２つのＣＰ（ａ），ＣＰ（ｂ）が対象パーセルの境界を跨いでいるような場合、属性ＰＤＭの値により与えられる道路形状の頂点ＶとＣＰ（ａ），ＣＰ（ｂ）とを結ぶ線分を算出し、線分の一方と対象パーセルの境界との交点に仮想ＣＰを付与する。なお、以下、複数のＣＰを区別するために記号ａ，ｂ，ｃ，・・・を用い、ＣＰ（ａ），ＣＰ（ｂ），ＣＰ（ｃ）と示す。
＜４．１ 属性の再計算＞
次のＳ１２０では、ＣＰの属性を再計算する。仮想ＣＰを付与することで、終端側のＣＰ（図１０（ａ）ではＣＰ（ｂ））は、後述するように、処理対象のＣＰから外される。そこで、始端側のＣＰ（図１０（ａ）ではＣＰ（ａ））及び仮想ＣＰの属性を再計算する。再計算される属性は、属性ＢＲ、属性ＤＭＢ、属性ＰＣＩ、属性ＣＡ、属性ＤＣＡ、属性ＰＤＭ、及び、属性ＰＤである。
【００５６】
属性ＢＲ及び属性ＤＭＢは、次のＣＰへの角度及び直線距離である（図４参照）。したがって、新たに付与した仮想ＣＰを含め、次のＣＰへの角度及び直線距離を計算して設定する。
【００５７】
属性ＣＡ及び属性ＤＣＡについては、始端側のＣＰ（図１０（ａ）ではＣＰ（ａ））での再計算は行わない。また、仮想ＣＰには、無効値を設定する。属性ＣＡ及び属性ＤＣＡは、脇道に関するものであり、仮想ＣＰには脇道の情報が妥当しないためである。
【００５８】
属性ＰＣＩは、並行する車道数に関するものである（図４参照）。したがって、始端側のＣＰ（図１０（ａ）ではＣＰ（ａ））での再計算は行わない。仮想ＣＰには、始端側及び終端側（図１０（ａ）ではＣＰ（ａ），ＣＰ（ｂ））に設定されているＰＣＩに従った値を設定する。
【００５９】
仮想ＣＰに対する属性ＰＣＩの具体的な計算ルールを図１１に示す。始端側のＣＰ及び終端側のＣＰがいずれも属性ＰＣＩを保持する場合、両ＣＰでの属性ＰＣＩが一致する場合には、仮想ＣＰに対し、両ＣＰと同一の値を設定する。一方、両ＣＰでの属性ＰＣＩが不一致である場合、仮想ＣＰに対し無効値を設定する。
【００６０】
また、始端側のＣＰ及び終端側のＣＰのいずれか一方が属性ＰＣＩを保持する場合、仮想ＣＰが、属性ＰＣＩを保持するＣＰの近傍にある場合には、そのＣＰと同一の値を設定する。一方、仮想ＣＰが属性ＰＣＩを保持するＣＰの近傍にない場合には、無効値を設定する。なお、近傍とは、例えば、属性ＰＣＩを保持するＣＰから仮想ＣＰまでの直線距離が始端側のＣＰと終端側のＣＰとの直線距離の１０％以下である場合をいう。
【００６１】
さらにまた、始端側のＣＰ及び終端側のＣＰのいずれも属性ＰＣＩを保持していない場合、仮想ＣＰに対し無効値を設定する。
属性ＰＤＭは、次のＣＰまでを結ぶ直線からの道路の離間距離である（図４参照）。この属性ＰＤＭについては、仮想ＣＰを付与する前の値に補正値を乗じて、設定する。具体的には、仮想ＣＰの配置位置割合を算出し、次の式で補正値を計算する。
【００６２】
（ｉ）配置位置割合が５０％未満のとき
補正値＝０．６×配置位置割合／１００・・・式１
（ｉｉ）配置位置割合が５０％以上のとき
補正値＝１．４×配置位置割合／１００−０．４・・・式２
ここで、配置位置割合は、次の式で計算される。
【００６３】
始端側のＣＰの属性ＰＤＭを再計算するときの配置位置割合は、
始端側ＣＰと仮想ＣＰとの直線距離／始端側ＣＰから終端側ＣＰまでの直線距離合計
・・・式３
となる。
【００６４】
また、仮想ＣＰの属性ＰＤＭを再計算するときの配置位置割合は、
仮想ＣＰと終端側ＣＰとの直線距離／始端側ＣＰから終端側ＣＰまでの直線距離合計
・・・式４
となる。
【００６５】
なお、直線距離合計は、始端側ＣＰから終端側ＣＰまでの仮想ＣＰを経由した場合の直線距離の合計であり、始端側ＣＰと仮想ＣＰとの直線距離及び仮想ＣＰと終端側ＣＰとの直線距離の合計となる。
【００６６】
属性ＰＤは、属性ＰＤを有する次のＣＰまでの運転距離であり（図４参照）、必ずしもＣＰに付与される属性ではない。そのため、パーセル境界を跨ぐ２つのＣＰが属性ＰＤを持たない場合がある。そこで、属性ＰＤを持つＣＰのうちで仮想ＣＰに最も近いＣＰを用いて再計算を行う。なお、属性ＰＤを有するＣＰが存在しない場合、属性ＰＤの再計算は行わない。
【００６７】
具体的には、ＣＰが有する属性ＰＤの値を、仮想ＣＰまでの直線距離に応じて按分する。すなわち、ＣＰの属性ＰＤの値は、ＣＰの元の属性値ＰＤの値に、上記式３の配置位置割合を乗じて求める。また、仮想ＣＰの属性ＰＤの値は、始点ＣＰの元の属性値ＰＤの値に、上記式４の配置位置割合を乗じて求める。
＜４．２ ＣＰの絞り込み＞
ここで図８の説明に戻り、Ｓ１３０では、対象パーセル内のＣＰに絞り込む。この処理は、対象パーセル内のＣＰだけ（仮想ＣＰを含む）を処理対象とするものである。ＣＰの配列は対象パーセルの境界を越えて続いていくことが考えられるが、アプリケーションで表示対象としている対象パーセルについてのみマッチングを行えば十分だからである。
＜４．２．１ 仮想ＣＰを付与しない方法＞
なお、本実施例では仮想ＣＰを付与することにより対象パーセルの境界にＣＰが存在するものとして当該仮想ＣＰまでを処理対象としているが、ＤＬＲデータとして引き渡される本来のＣＰを対象パーセルの終端ＣＰとして処理を行うようにしてもよい。
【００６８】
例えば、図１０（ｂ）に示すように対象パーセルの境界をＣＰが跨いでいる場合、対象パーセル内のＣＰ（ａ）を終端ＣＰとしてもよい。又は、対象パーセル外の最初に現れるＣＰ（ｂ）を終端ＣＰとしてもよい。ただし、ＣＰ（ａ），ＣＰ（ｂ）が対象パーセルの境界から離れて存在する場合があるため、例えばＣＰ（ａ），ＣＰ（ｂ）の対象パーセルの境界からの離れ具合に応じて、いずれのＣＰを終端ＣＰとするかを判断するようにしてもよい。
【００６９】
一例として、図１０（ｂ）に示すように、２つのＣＰ（ａ），ＣＰ（ｂ）を結ぶ直線と対象パーセルの境界との交点Ｋを算出し、交点Ｋまでの直線距離Ａ，Ｂで離れ具合を測ることが考えられる。
【００７０】
このとき、通常は対象パーセルの外側にあるＣＰ（ｂ）を終端ＣＰとし、直線距離Ｂが所定値以上となった場合に、対象パーセルの内側にあるＣＰ（ａ）を終端ＣＰとすることが例示される。このときは、通常、ＣＰ（ｂ）までが処理対象となるため、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報を十分に表示することができる。また、例えばＣＰ（ｂ）が高速道路を示すような場合、ＣＰ（ｂ）が対象パーセルの境界から極端に離れてしまう場合、ＣＰ（ａ）までが処理対象となるため、処理に要する時間が長くなることを抑制できる。
【００７１】
あるいは、通常は対象パーセルの内側にあるＣＰ（ａ）を終端ＣＰとし、直線距離Ａが所定値以上となった場合に、対象パーセルの外側にあるＣＰ（ｂ）を終端ＣＰとすることが例示される。このときは、通常、ＣＰ（ａ）までが処理対象となるため、処理に要する時間を極力短くすることができる。また、例えばＣＰ（ａ）が対象パーセルの境界から極端に離れてしまう場合、ＣＰ（ｂ）までが処理対象となるため、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報の表示が不十分になることを抑制できる。
【００７２】
またあるいは、直線距離Ａ，Ｂを比較し、直線距離Ａが直線距離Ｂよりも小さい場合に対象パーセルの内側にあるＣＰ（ａ）を終端ＣＰとし、一方、直線距離Ｂが直線距離Ａよりも小さい場合に対象パーセルの外側にあるＣＰ（ｂ）を終端ＣＰとすることが例示される。このときは、直線距離に応じて終端ＣＰが決定されるため、ＣＰ（ｂ）までが処理対象となる場合には、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報を十分に表示することができる。一方、ＣＰ（ａ）までが処理対象となる場合には、処理に要する時間を極力短くすることができる。
【００７３】
いずれにしても、仮想ＣＰを付与する構成に比べ、仮想ＣＰの付与に関する処理に要する時間が短縮される点、また、仮想ＣＰの付与に伴う属性の再計算の処理に要する時間が短縮される点で有利である。
＜４．２．２ 属性の引き継ぎ＞
ところで、図８中のＳ１３０では、処理対象のＣＰを決定するに伴い、属性の引き継ぎ処理も行われる。
【００７４】
ＤＬＲデータとしてのＣＰでは、交差点を示すＣＰ（ＩＰフラグがセットされているＣＰ）だけが各種の属性を有している。そこで、このようなＣＰが有する非形状系の属性を、交差点間に存在するＣＰへ引き継ぐ。これにより、後述する処理で都度、非形状系の属性を取得する手間を省くことができる。具体的に引き継がれる属性は、属性ＦＣ、属性ＦＷ、属性ＲＤ、属性ＤＤ、及び、属性ＡＦＲである。
【００７５】
以上説明した変換処理により、中間データに変換されたＣＰの配列が作成されることになる。つまり、この段階で、ＣＰは、図４に示した各種の属性を有するものとなっている。一方で、地図データを構成するノード及びリンクの少なくともいずれかが、ＣＰの属性に対応する属性を有している。そこで、各種属性を比較することで、終局的にＣＰにより示される道路を推定する。
＜５．マッチング処理の詳細（後半）＞
図３のマッチング処理の説明に戻り、Ｓ２００では、候補リンク検索処理を実行する。候補リンク検索処理は、候補となるリンク列を検索し、その後、リンク単位で絞り込みを行うものである。次のＳ３００では、候補選定処理を実行する。候補選定処理は、Ｓ２００にて絞り込まれたリンクを、さらに絞り込むものである。続くＳ４００では、道路マッチング処理を実行する。道路マッチング処理は、ＣＰ間を繋ぐリンクを推定するものである。これらＳ２００〜Ｓ４００の処理は、図８中のＳ１３０で絞り込まれる各ＣＰを対象ＣＰとしてＣＰの数だけ繰り返し実行される。
【００７６】
そこで、以下では、これらの処理を詳細に説明する。Ｓ２００の候補リンク検索処理の一例を図１２に示す。
最初のＳ２１０では、対象ＣＰの情報が取得される。この処理は、ＣＰの種類、緯度、経度を取得するものである。ＣＰの種類は、交差点を示すＣＰ、仮想ＣＰ、その他のＣＰの区別である。
【００７７】
続くＳ２２０では、検索範囲を設定する。この処理は、対象ＣＰを中心とするリンクの検索範囲を設定するものである。この検索範囲は特に、図１３（ａ）に破線で示すように、その境界が垂直又は水平の線分で構成される多角形として設定される。本実施例では、正方形と当該正方形の一辺よりも長い十字形状とを合成したような範囲として設定されている。
【００７８】
次のＳ２３０では、検索範囲にあるパーセルを取得する。この処理は、ノード及びリンクがパーセル単位で管理されているため、リンク列の選定を行うにあたり、検索範囲に係るパーセルを全て取得するものである。例えば図１３（ｂ）に示すように、検索範囲に応じて３つのパーセルＰ１，Ｐ２，Ｐ３が取得されるという具合である。
【００７９】
続くＳ２４０では、リンク列選定処理を実行する。このリンク列選定処理では、非形状系の属性により、リンクがリンク列単位で検索される。なお、「リンク列」とは、高速道路、一般道路などの道路区分が同一となっている一連のリンク群である。ここでは、Ｓ２３０にて取得されたパーセルに一部が含まれるリンク列が検索対象となる。つまり、この段階では、検索範囲にあるかの判定をせず、最初に属性でリンク列を絞り込むのである。
＜５．１ リンク列選定処理＞
ここで、リンク列選定処理について詳細に説明する。リンク列選定処理の一例を図１４に示す。このリンク列選定処理では、非形状系の属性である属性ＦＣ、属性ＦＷ、属性ＲＤにより、リンク列単位での抽出が行われる。
【００８０】
最初のＳ２４１では、属性ＦＣが一致するリンク列に絞り込む。属性ＦＣは、上述したように道路区分を示す属性である（図５参照）。ここでは、リンク列を構成するリンクに付与されている道路区分と対象ＣＰの属性ＦＣとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で道路区分が変わることがある。したがって、リンク列を構成する全てのリンクの道路区分が属性ＦＣに一致する場合に、当該リンク列を候補リンク列とする。
【００８１】
次のＳ２４２では、属性ＦＷが一致するリンク列に絞り込む。属性ＦＷは、上述したように、物理道路タイプを示す属性である（図６参照）。ここでは、リンク列を構成するリンクに付与されている物理道路タイプと対象ＣＰの属性ＦＷとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で物理道路タイプが変わることがある。したがって、リンク列を構成する全てのリンクの物理道路タイプが属性ＦＷに一致する場合に、当該リンク列を候補リンク列とする。
【００８２】
続くＳ２４３では、属性ＲＤが一致するリンク列に絞り込む。属性ＲＤは、上述したように、道路番号又は道路名称を示す属性である（図４参照）。ここでは、属性ＲＤが道路番号を示す場合に限り、道路番号による一致を判断する。すなわち、リンク列を構成するリンクに付与されている道路番号と対象ＣＰの属性ＲＤとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で道路番号が変わることがある。したがって、リンク列を構成する全てのリンクの道路番号が属性ＲＤに一致する場合に、当該リンク列を候補リンク列とする。
【００８３】
このようなリンク列選定処理により、非形状系属性で絞り込まれたリンク列が候補リンク列として残ることになる。
＜５．２ リンクの抽出＞
図１２のＳ２５０では、対象ＣＰを中心とする検索範囲に一部が含まれるリンクを抽出する。Ｓ２４０のリンク列選定にてリンク列が選定されるため、ここでは、選定されたリンク列を構成するリンクのうち検索範囲に一部が含まれるリンクを抽出する。
【００８４】
ここで「検索範囲に一部が含まれるリンク」について説明する。以下では特に、ノードが交差点に対して通常付与されること、ノードがパーセルの境界に付与されること、必要に応じてノード間に形状補間点が設定されること、を前提として説明を続ける。
＜５．２．１ 対象ＣＰが交差点の場合＞
対象ＣＰが交差点を示す場合は、ノードを意識した処理を行う。すなわち、対象ＣＰが交差点を示す場合は、対象ＣＰがノードと対応付けられるためである。したがって、この場合、リンクを構成する２つのノードのうちのいずれかが検索範囲に含まれているリンクを「検索範囲に一部が含まれるリンク」とする。
【００８５】
例えば図１５（ａ）に示す対象ＣＰが交差点を示すものとする。この場合、検索範囲に含まれるノードＡ，Ｂ，Ｃは、対象ＣＰと対応付けられる。そのため、ノードＡ，Ｂ，Ｃが端点の一方となっているリンクＬ１，Ｌ２，Ｌ３，Ｌ４，Ｌ５が「検索範囲に一部が含まれるリンク」となる。
【００８６】
ただし、地図データは、その縮尺に応じたレベル（以下「パーセルレベル」という）を有している。このパーセルレベルは、ユーザによる縮尺の切り替えによって切り替わるため、リンクの抽出は、全てのパーセルレベルで行われる。パーセルレベルは、下位レベルから順に、ＬＶ０→ＬＶ２→ＬＶ４→ＬＶ６→ＬＶ８→ＬＶ１０などとして設定される。そして、上位レベルになるほど、交差点や道路が間引かれる。
【００８７】
ＣＰは、最も下位のパーセルレベルであるＬＶ０に相当するデータとなっている。したがって、ＬＶ２よりも上位のパーセルレベルでは、必ずしも交差点に対応するノードが存在するとは限らない。そこで、ＬＶ２よりも上位のパーセルレベルでの抽出処理では、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。「一定条件を満たす場合」については、後述する。
＜５．２．２ 対象ＣＰが仮想ＣＰである場合＞
対象ＣＰが仮想ＣＰである場合も、ノードを意識した処理を行う。地図データの仕様では、パーセル境界には必ずノードが設定される。したがって、対象ＣＰが仮想ＣＰである場合、当該仮想ＣＰは、パーセル境界に付与されるものであるため、同一のパーセル境界に存在するノードがあれば、そのノードと対応付けられる。
【００８８】
そこで、リンクを構成するノードのいずれかがパーセル境界に存在する場合、このパーセル境界に存在するノードが検索範囲に含まれるときは、そのリンクを「検索範囲に一部が含まれるリンク」とする。
【００８９】
例えば、図１５（ｂ）に示す対象ＣＰが仮想ＣＰを示すものとし、ノードＤがパーセル境界に存在するノードだとすると、ノードＤを端点とするリンクＬ６，Ｌ８が「検索範囲に一部が含まれるリンク」となる。
＜５．２．３ 対象ＣＰが交差点でも仮想ＣＰでもない場合＞
この場合、対象ＣＰがノードと対応付けられるか否かは分からないため、ノードを意識することなく、リンクの抽出を行う。つまり、対象ＣＰが交差点でも仮想ＣＰでもない場合は、リンクを構成する少なくともいずれかのノードが検索範囲に含まれている場合の他に、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。この場合のリンクの抽出は、全てのパーセルレベルで同様に行われる。
＜５．２．４ 一定条件を満たす場合＞
「一定条件を満たす場合」とは、次の２つの場合をいう。一つは、ノード間に形状補間点が設定されている場合、当該形状補間点を結んだ線分の一部が検索範囲に含まれている場合である。例えば図１５（ｃ）に示すリンクＬ９は、その形状補間点（小さな黒丸）を結ぶ線分の一部が検索範囲に含まれているため、ノードＥ，Ｆが検索範囲に含まれていないが「検索範囲に一部が含まれるリンク」となる。一方、リンクＬ１０は、その形状補間点を結ぶ線分の一部が検索範囲に含まれていないため、「検索範囲に一部が含まれるリンク」にならない。もう一つは、ノード間に形状補間点が設定されていない場合、２つのノードを結ぶ線分の一部が検索範囲に含まれている場合である。例えば、図１５（ｄ）に示すリンクＬ１１は、２つのノードＧ，Ｈを結ぶ線分の一部が検索範囲に含まれているため、「検索範囲に一部が含まれるリンク」となる。
＜５．２．５ その他＞
図１２の説明に戻り、続くＳ２６０では、検索範囲に一部が含まれるリンクのうちで属性ＲＤが一致するリンクに絞り込む。属性ＲＤが道路番号を示す場合は図１４中のＳ２４３にて判断するため、ここでは属性ＲＤが道路名称である場合に、当該道路名称による一致を判断する。なお、道路名称は最大５文字となっているため、属性ＲＤの値としての文字列がリンクに付与される道路名称に含まれるか否かを判断する。
【００９０】
次のＳ２７０では、リンクの数が「１０」本以内に収まるように絞り込む。具体的には、Ｓ２６０までの絞り込みによってリンクの数が「１０」本を越えている場合、対象ＣＰに近いものから順に「１０」本のリンクを選択する。対象ＣＰに近いか否かは、対象ＣＰから各リンクへ例えば垂線を下ろすなどして距離を求めることによって判断する。
＜５．３ 候補選定処理＞
次に、図３中のＳ３００の候補選定処理について説明する。候補選定処理は、リンク、ノード単位の候補選定を行うものである。候補選定処理の一例を図１６に示した。
【００９１】
最初のＳ３１０では、非形状系属性の一致判定を行う。詳細については後述するが、ここでは、Ｓ２００で抽出されたリンク又は当該リンクを構成するノードに対し、属性ＦＣ、属性ＦＷ、属性ＩＴ、属性ＲＤＩ、属性ＤＤ及び属性ＡＦＲを用いた一致判定を行う。なお、属性ＦＣ及び属性ＦＷは、リンク列を絞り込む際に利用しているため（図１４中のＳ２４１，Ｓ２４２）重複した処理となっているが、確実をきすために再度行うものである。また、ここでの一致判定は、確実を期すため、属性ＩＴ、属性ＲＤＩ、属性ＤＤ及び属性ＡＦＲなどを用いた細かい一致判定となっている。
【００９２】
続くＳ３２０では、形状系属性の一致判定を行う。詳細については後述するが、ここでは、図３中のＳ２００で抽出されたリンク又は当該リンクを構成するノードに対し、属性ＢＲ、属性ＰＣＩ、属性ＣＡ及び属性ＤＣＡを用いた一致判定を行う。
【００９３】
次のＳ３３０では、非形状系属性での判定結果を基に候補となるリンクを絞り込む。具体的には、Ｓ３１０での非形状系属性による一致判定の結果、各属性との一致数が多いリンクを、候補リンクとする。
【００９４】
続くＳ３３０では、形状系属性での判定結果で候補となるリンクを絞り込む。具体的には、Ｓ３２０での形状系属性による一致判定の結果、各属性との一致数が多いリンクを、候補リンクとする。
＜５．３．１ 非形状系属性の一致判定＞
ここで、Ｓ３１０の非形状系属性の一致判定の詳細を説明する。非形状系属性の一致判定の一例を図１７に示す。
【００９５】
最初のＳ３１１では、属性ＦＣでの一致判定を行う。属性ＦＣは、上述したように道路区分を示す属性である（図５参照）。ここでは、判定対象のリンクに付与されている道路区分と対象ＣＰの属性ＦＣとの一致を判定する。
【００９６】
続くＳ３１２では、属性ＦＷでの一致判定を行う。属性ＦＷは、上述したように、物理道路タイプを示す属性である（図６参照）。ここでは、判定対象のリンクに付与されている物理道路タイプと対象ＣＰの属性ＦＷとの一致を判定する。
【００９７】
次のＳ３１３では、属性ＩＴでの一致判定を行う。属性ＩＴは、上述したように、交差点の分類を示す属性である（図７参照）。したがって、対象ＣＰが交差点を示すものである場合にのみ、この一致判定が行われる。
【００９８】
なお、属性ＩＴに相当する属性は、ノード及びリンクの少なくともいずれか一方が有している。そこで、ノードが交差点の分類を示す交差点分類情報を持っている場合、対象ＣＰに対応するノードの交差点分類情報と対象ＣＰの属性ＩＴとの一致を判定する。また、リンクが交差点の分類を示す交差点分類情報を持っている場合、対象ＣＰに対応するノードに接続するリンクの交差点分類情報と対象ＣＰの属性ＩＴとの一致を判定する。後者では、２つのノードの交差点分類情報をリンクが持っていることがあるため、いずれかの交差点分類情報と属性ＩＴとの一致を判定する。
【００９９】
続くＳ３１４では、属性ＲＤＩでの一致判定を行う。属性ＲＤＩは、上述したように、交差点の名称を示すものである（図４参照）。したがって、対象ＣＰが交差点を示すものである場合にのみ、この一致判定が行われる。ここでは、対象ＣＰに対応するノードの交差点名称と対象ＣＰの属性ＲＤＩとの一致を判定する。なお、この判定は、属性ＲＤＩの値である文字列がノードの交差点名称に含まれるか否かで行われる。
【０１００】
次のＳ３１５では、属性ＤＤ及び属性ＡＦＲでの一致判定を行う。属性ＤＤは許可された合法の運転方向を示すものであり、属性ＡＦＲは、属性ＤＤが参照可能であるか否かを示すフラグである（図４参照）。ここでは、判定対象のリンクの属性（一方通行コード）と対象ＣＰの属性ＤＤとを比較して判定する。なお、属性ＡＦＲが「１」としてセットされており属性ＤＤが有効である場合であって属性ＤＤが「０」（未定義）でない場合を除いて、判定を行う。ところで、属性ＤＤが示すのはある交通情報に対する道路の通行可能方向であり、リンクの有する一方通行コードとの比較では、両者の順逆方向までは判断できない。したがって、ここでは通行方向の一致を判断するわけではなく、片側通行の道路か両側通行の道路かを判定することにとどまる。
＜５．３．２ 形状系属性の一致判定＞
続けて、Ｓ３２０の形状系属性の一致判定の詳細を説明する。形状系属性の一致判定の一例を図１８に示す。
【０１０１】
最初のＳ３２１では、属性ＢＲでの一致判定を行う。属性ＢＲは、上述したように、次のＣＰへの位置的な角度を示すものである（図４参照）。一方、リンクは、法定上の走行方向を属性として有している。そこで、ここでは、リンクの走行方向が対象ＣＰの属性ＢＲに基づく方向と大きく異なっている場合に、不一致の判定を行う。例えば、リンクの走行方向を示すベクトルと、次のＣＰへ向かう属性ＢＲに基づくベクトルとのなす角度が所定角度（例えば９０度）以上となる場合に、不一致と判定することが考えられる。なお、リンクが双方向に走行可能となっている場合、走行方向を示す２つのベクトルで判定する。
【０１０２】
例えば、図１９（ａ）では、リンクＬ１，Ｌ２，Ｌ３の走行方向を示すベクトルＶＬ１，ＶＬ２１，ＶＬ２２，ＶＬ３と属性ＢＲに基づくベクトルＶＢとのなす角度で判定を行うという具合である。ここでは両ベクトルのなす角度が９０度以上となる場合に、不一致と判定するものとする。なお、リンクＬ２は、双方向に走行可能となっており、走行方向を示す２つのベクトルＶＬ２１，ＶＬ２２で判定される。
【０１０３】
ここでベクトルＶＢとベクトルＶＬ１とのなす角度は、１８０度に近いものとなっており、９０度以上であるため、リンクＬ１は、「不一致」と判定される。また、ベクトルＶＬ２２とベクトルＶＢとがなす角度は９０度以上となるが、ベクトルＶＬ２１とベクトルＶＢとがなす角度が９０度よりも小さいため、リンクＬ２は「一致」と判定される。さらにまた、ベクトルＶＬ３とベクトルＶＢとがなす角度は９０度よりも小さいため、リンクＬ３は「一致」と判定される。
【０１０４】
つまり、９０度以上となる場合を不一致とする場合は、図１９（ｂ）に示すように、属性ＢＲに基づくベクトルＶＢに対し、リンクの走行方向がベクトルＶ１，Ｖ２で示される場合には「一致」と判定され、ベクトルＶ３，Ｖ４で示される場合には「不一致」と判定される。
【０１０５】
図１８中のＳ３２２では、属性ＰＣＩでの一致判定を行う。属性ＰＣＩは、上述したように、同一方向において複数の車道が存在する場合、いずれの車道が選択されているかを示すものである（図４参照）。
【０１０６】
属性ＰＣＩには、車道数及びその車道の中のいずれの車道かを示すシーケンス番号が含まれる。ただし、この属性で一致を判定しようとする場合、並走するリンクを残らず特定する必要がある。
【０１０７】
そこで、図２０に示すように、最初のＳ３２３では、対象ＣＰを中心とした検索エリアを設定する。この検索エリアは、対象ＣＰを中心とした円の内部とすることが考えられる。例えば、所定距離（例えば１５０ｍ）を半径とする円の内部を検索エリアにするという具合である。なお、ＰＣＩ属性の一つとして検索エリアのデフォルト値が設定されることがあるため、その場合は、デフォルト値に所定距離（例えば１５０ｍ）を加えた値を半径とする円の内部を検索エリアとすることが考えられる。
【０１０８】
続くＳ３２４では、検索エリア内のリンクを抽出する。ここでは、属性ＰＣＩの一つにインジケータタイプがあるため、このインジケータタイプに基づき、緯度方向あるいは経度方向の仮想直線を引き、この仮想直線と交差するリンクを抽出する。
【０１０９】
次のＳ３２５では、抽出したリンクの数と車道数とが一致するか否かを判断する。ここで車道数が一致すると判断された場合（Ｓ３２５：ＹＥＳ）、Ｓ３２６にてシーケンス番号でリンクを特定し、当該リンクが判定対象のリンクと一致するか否かを判定して、属性ＰＣＩでの一致判定を終了する。一方、車道数が一致しないと判断された場合、Ｓ３２６の処理を実行せず、属性ＰＣＩでの一致判定を終了する。これは、車道数が一致しない場合、誤判定となる虞があるからである。
【０１１０】
図１８に戻り、Ｓ３２７では、属性ＣＡ及び属性ＤＣＡでの一致判定を行う。属性ＣＡは脇道に対する角度を示すものであり、属性ＤＣＡは脇道に対する接続距離を示すものである（図４参照）。ここでは、最初に、脇道の方向を検出する。具体的には、図２１（ａ）に示すように、属性ＣＡが負値である場合、次のＣＰへ向かう方向（属性ＢＲに基づく方向）に対し、左側に脇道があると判断する。一方、図２１（ｂ）に示すように、属性ＣＡが正値である場合、次のＣＰへ向かう方向（属性ＢＲに基づく方向）に対し、右側に脇道があると判断する。なお、属性ＣＡが「０」である場合、脇道の方向が特定できないため、一致判定を行わない。次に、判定対象のリンクとそのリンクの脇道との位置関係から属性ＣＡ及び属性ＤＣＡでの一致判定を行う。
【０１１１】
以上説明してきたＳ３００の候補選定処理によって、各ＣＰに対し、その周辺に、候補となるリンクが選定される。これらのリンクを繋ぐリンク、すなわちＣＰ間を繋ぐリンクを推定する処理が、図３中の道路マッチング処理（Ｓ４００）である。
＜５．４ 道路マッチング処理＞
次に、Ｓ４００の道路マッチング処理について説明する。道路マッチング処理の一例を図２２に示す。道路マッチング処理では、２つのＣＰを対象ＣＰとし、始端側に位置するＣＰを始端側ＣＰ、終端側に位置するＣＰを終端側ＣＰとして処理を行う。
＜５．４．１ 道路探索＞
最初のＳ４１０では、始端候補リンクから終端候補リンクを繋ぐ道路を探索する。始端候補リンクは、始端側ＣＰに対し抽出されたリンクである。また、終端候補リンクは、終端側ＣＰに対し抽出されたリンクである。ここでは、始端候補リンクと終端候補リンクとを結ぶ全ての道路を探索する。例えば、図２３に示すように、始端側ＣＰをＣＰ（ａ）とし、終端側ＣＰをＣＰ（ｂ）とし、ＣＰ（ａ）に対し抽出されたリンクをＳＬとし、ＣＰ（ｂ）に対し抽出されたリンクをＧＬとする。このとき、始端候補リンクＳＬと終端候補リンクＧＬとの間の道路を探索する場合、リンクＳＬを構成する２つのノードＳＮ１，ＳＮ２とリンクＧＬを構成する２つのノードＧＮ１，ＧＮ２との全ての組み合わせを考える。具体的には、ＳＮ１→ＧＮ１、ＳＮ１→ＧＮ２、ＳＮ２→ＧＮ１、ＳＮ２→ＧＮ２を結ぶ道路を探索する。
【０１１２】
次のＳ４２０では、道路単位候補選定を実行する。この処理は、各種の形状系属性を基に、Ｓ４１０にて探索された道路のうちで候補となる道路を判定するものである。続くＳ４３０では、Ｓ４２０における判定結果に基づき、道路を絞り込む。
【０１１３】
次のＳ４４０では、道路が一意に決定されたか否かを判断する。ここで道路が一意に決定された場合（Ｓ４４０でＹＥＳ）、Ｓ４５０にてマッチング結果を出力し、その後、道路マッチング処理を終了する。一方、道路が一意に決定されない場合（Ｓ４４０でＮＯ）、Ｓ４５０の処理を実行せず、道路マッチング処理を終了する。
＜５．４．２ 道路探索の省略＞
なお、このような道路マッチング処理（Ｓ４１０〜Ｓ４４０）がペアとなる２つの対象ＣＰに対して繰り返されるのであるが、上述のＳ４１０では、先の道路マッチング処理の結果を用いて探索する道路を省略する場合がある。
【０１１４】
例えば、図２３（ｂ）に示すように、ＣＰ（ａ）−ＣＰ（ｂ）間の道路マッチング処理の結果、リンクＳＬ→ＣＬ→ＧＬ１という道路が一意に決定されたものとする。このときは、ＣＰ（ｂ）から次のＣＰへの道路マッチング処理を行う場合、リンクＧＬ１からの道路を探索する。すなわち、候補リンクにリンクＧＬ２があっても、リンクＧＬ２からの道路探索を省略する。
【０１１５】
また、ＣＰの種類によっても、道路探索を省略する。
ＣＰ（ｂ）が交差点である場合、例えば図２３（ｃ）に示すように、交差点を示すノードＧＮ２と対応するため、リンクＧＬについては、一方のノードＧＮ１に接続される道路を探索する。すなわち、ＳＮ１→ＧＮ１、ＳＮ２→ＧＮ１を結ぶ道路を探索する。
【０１１６】
ＣＰ（ｂ）が仮想ＣＰである場合、例えば図２３（ｄ）に示すノードＧＮ２が対象パーセルの境界に位置するノードであれば、このノードが道路の始端又は終端となる。そこで、この場合も、リンクＧＬについては、一方のノードＧＮ１に接続される道路を探索する。すなわち、ＳＮ１→ＧＮ１、ＳＮ２→ＧＮ１を結ぶ道路を探索する。
【０１１７】
さらにまた、一度探索した道路を再び探索しないようにして道路探索に要する時間を短縮することが考えられる。
例えば図２４（ａ）に実線で示すノードＮ１→Ｎ２→Ｎ３→Ｎ４という探索を最初に行ったものとする。このとき、ノードＮ１からの道路探索を２度目に行う場合、ノードＮ１→Ｎ５→Ｎ２という道路探索は行うが、ノードＮ２から先の探索は既に行っているため、ノードＮ２から先の探索は行わない。
【０１１８】
また、ノードからリンクが分岐する場合、リンクに優先順位をつけて道路探索を行う。例えば、あるノードから道路探索を行う場合、対象ＣＰを結ぶ方向を基準にして、ノードに接続されるリンクの基準方向からの角度を求め、所定角度以内にあるリンクのみを道路探索の対象とする。図２４（ｂ）では、ノードＮ１からの道路探索を行うのであるが、ＣＰ（ａ）からＣＰ（ｂ）へ向かう方向を基準にして、ノードＮ１に接続されるリンクＬ１，Ｌ２，Ｌ３の基準方向からの角度ａ１，ａ２，ａ３を求める。ここで角度ａ１，ａ２が所定角度以内にあるとすると、リンクＬ１，Ｌ２を道路探索の対象とする。一方、角度ａ３が所定角度を越えている場合、リンクＬ３を道路探索の対象から外す。
【０１１９】
さらにまた、ノードからの探索を行う場合、そのノードまでのリンクの道路種別と同じ道路種別のリンクを道路探索の対象とする。例えば図２４（ｃ）では、ＣＰ（ｂ）からＣＰ（ｃ）への道路を、ノードＮ１から探索する。ここで、ＣＰ（ａ）−ＣＰ（ｂ）間の道路がリンクＬ１として確定されているものとする。このとき、リンクＬ１の道路種別が「国道」であるため、ノードＮ１からの道路探索にあたり、道路種別が「国道」であるリンクＬ２を道路探索の対象にする。道路種別が「県道」であるリンクＬ３は、道路探索の対象から外す。
＜５．４．３ 道路探索の中止＞
ところで、Ｓ４１０における道路探索が所定時間以内に終了するとは限らない。そこで、道路探索を途中で中止するようにしてもよい。
【０１２０】
例えば属性ＰＤを利用することが考えられる。図２５（ａ）では、ＣＰ（ａ）及びＣＰ（ｂ）のいずれもが属性ＰＤを有しているものとする。このとき、ノードＮ１からノードＮ２への道路を探索する際、形状補間点Ｋ１，Ｋ２，Ｋ３，Ｋ４，・・・での累積距離を算出するようにする。そして、この累積距離が、ＰＤ値から一定値以上大きくなった場合、道路探索を中止する。
【０１２１】
また例えば属性ＰＤＭを利用することが考えられる。図２５（ｂ）に示すように、ＣＰ（ａ）−ＣＰ（ｂ）間の直線距離とＰＤＭ値とを用い、破線で示すようなコ字状の距離を算出しておく。このとき、ノードＮ１からノードＮ２への道路を探索する際、形状補間点Ｋ１，Ｋ２，Ｋ３，Ｋ４，・・・での累積距離を算出するようにする。そして、この累積距離が、破線で示される距離よりも一定値以上大きくなった場合に、道路探索を中止する。
【０１２２】
例えば通過するノードの数を利用することが考えられる。図２５（ｃ）に示すように、ノードＮ１からノードＮ２への道路を探索する際、通過するノードＮ３，Ｎ４，Ｎ５，Ｎ６の個数を数えるようにする。そして、ノードの数が一定値以上となった場合に、道路探索を中止する。
【０１２３】
また例えばＣＰが交差点であることを利用することが考えられる。図２５（ｄ）では、ＣＰ（ａ）及びＣＰ（ｂ）のいずれもが交差点であるとする。このとき、ノードＮ１，Ｎ２が交差点であれば、ノードＮ１，Ｎ２がそれぞれＣＰ（ａ），ＣＰ（ｂ）に対応するものとなるため、ノードＮ１，Ｎ２間の直線距離を予め算出しておく。そして、ノードＮ１からノードＮ２への道路を探索する際、通過するノードＮ３，Ｎ４，Ｎ５，Ｎ６までの累積距離を算出して、この累積距離が、予め算出したノードＮ１，Ｎ２間の直線距離よりも一定値以上大きくなった場合、道路探索を中止する。
【０１２４】
ここでは４つの手法を説明したが、いずれの手法によっても、間違っていると思われる道路の探索が途中で打ち切られるため、処理負荷が軽減される。
＜５．４．４ 道路単位候補選定＞
ここで、図２２中の道路単位候補選定について説明する。道路単位候補選定の一例を図２６に示す。道路単位候補選定は、ＣＰ間で抽出された道路の単位で、「ＯＫ」又は「ＮＧ」判定を行うものである。
【０１２５】
最初のＳ４２１では、属性ＣＡ／ＤＣＡで判定する。上述したように、属性ＣＡは脇道に対する角度を示すものであり、属性ＤＣＡは脇道に対する接続距離を示すものである（図４参照）。ここでは、探索された道路の中で、属性ＣＡ及び属性ＤＣＡによって特定されるリンクを、脇道であるとして、このリンクを含む道路に対しＮＧ判定を行うものである。具体的には、図２７（ａ）に示すように、属性ＣＡ及び属性ＤＣＡが示す位置座標の周囲（破線で示す範囲）にリンクがあれば、当該リンクを含む道路を「ＮＧ」と判定する。例えば図２７（ｂ）には、ＣＰ間を繋ぐ道路として道路１及び道路２が示されているが、属性ＣＡ及び属性ＤＣＡから脇道と判定されたリンクを含む道路１は「ＮＧ」と判定されることになる。
【０１２６】
図２６中のＳ４２２では、属性ＢＲ／ＤＭＢで判定する。上述したように、属性ＢＲは次のＣＰへの角度を示すものであり、属性ＤＭＢは次のＣＰまでの直線距離を示すものである（図４参照）。ＣＰが示すデータとナビゲーション装置１０の地図データとの間にずれがある場合、この属性ＢＲ／ＤＭＢを利用することで、より確からしい道路を特定することができる。そこで、図２８に示すように、ＣＰ（ｂ）−ＣＰ（ｃ）間の道路の判定を、ＣＰ（ｂ）の一つ前のＣＰ（ａ）の属性ＢＲ及び属性ＤＭＢを用いて行う。具体的には、属性ＢＲ及び属性ＤＭＢから特定される位置座標の周囲（記号Ｈの破線で示す範囲）のリンクＬを含む道路は「ＯＫ」と判定する。なお、ＣＰ（ｂ）−ＣＰ（ｃ）間の道路の判定であるため、リンクＬを構成するノード又は形状補間点が所定範囲に入ることを条件とする。例えば、所定範囲は、ＣＰ（ｂ）とＣＰ（ｃ）とを結ぶ線分と属性ＰＤＭとから設定される矩形（図中に二点鎖線で示した）の内側とすることが考えられる。もちろん、所定範囲は、このような矩形に限られず、ＣＰ（ｂ）及びＣＰ（ｃ）を通る楕円の内側などとしてもよい。
【０１２７】
次のＳ４２３では、属性ＰＤで判定する。上述したように、属性ＰＤは、属性ＰＤを有する次のＣＰまでの運転距離である（図４参照）。したがって、探索された道路の運転距離によって、当該道路が候補となり得るか否かを判定する。
【０１２８】
具体的には、図２９に示すように、ＣＰ（ａ）−ＣＰ（ｂ）間の運転距離を算出する場合、各ＣＰがノードに対応するとは限らないため、ＣＰ（ａ）からリンクＬ１への垂線を下ろし、また、ＣＰ（ｂ）からリンクＬ３への垂線を下ろして、それぞれの交点をＭ，Ｎとする。そして、交点Ｍから交点Ｎまでの運転距離を算出する。
【０１２９】
なお、交点Ｍから直後のノードまでの運転距離は、この運転距離のリンクＬ１における割合を算出することで求める。ここで、交点Ｍから直後のノードまでがリンクＬ１のｍ（％）である場合、リンクＬ１の運転距離に（ｍ／１００）を乗じて、交点Ｍから直後のノードまでの運転距離を算出する。
【０１３０】
同様に、交点Ｎから直前のノードまでの運転距離は、この運転距離のリンクＬ３における割合を算出することで求める。ここで、交点Ｎから直前のノードまでの距離がリンクＬ１の距離のｎ（％）である場合、リンクＬ３の運転距離に（ｎ／１００）を乗じて、交点Ｎから直前のノードまでの運転距離を算出する。
【０１３１】
ところで、全てのＣＰが属性ＰＤを有しているとは限らない。したがって、ＣＰ（ａ）が属性ＰＤを有しているがＣＰ（ｂ）が属性ＰＤを有していない場合、図３０（ａ）に示すように、道路の候補判定は行わず、そのまま道路を保持する。次に、図３０（ｂ）に示すＣＰ（ｃ）が属性ＰＤを有しているとすると、ＣＰ（ａ）−ＣＰ（ｃ）間で属性ＰＤに基づく道路判定を行う。すなわち、道路Ｌ１→Ｌ２→Ｌ３→Ｌ５→Ｌ６→Ｌ１０と、道路Ｌ１→Ｌ４→Ｌ５→Ｌ６→Ｌ１０と、道路Ｌ１→Ｌ２→Ｌ３→Ｌ５→Ｌ７→Ｌ８→Ｌ９→Ｌ１０と、道路Ｌ１→Ｌ４→Ｌ５→Ｌ７→Ｌ８→Ｌ９→Ｌ１０と、を候補にして、ＮＧ判定を行う。これにより、図３０（ｃ）に示すように道路Ｌ１→Ｌ２→Ｌ３→Ｌ５→Ｌ６→Ｌ１０という道路が残った場合、ＣＰ（ａ）−ＣＰ（ｂ）間の道路Ｌ４、及び、ＣＰ（ｂ）−ＣＰ（ｃ）間の道路Ｌ７→Ｌ８→Ｌ９は、「ＮＧ」と判定されることになる。
【０１３２】
続くＳ４２４では、属性ＰＤＭで判定する。上述したように、属性ＰＤＭは、次のＣＰまでを結ぶ直線からの道路の離間距離を示す（図４参照）。この処理では、属性ＰＤＭに基づき道なりの運転距離を求め、探索された道路が候補となるか否かを判定する。
【０１３３】
具体的には、属性ＰＤＭに基づく道なりの運転距離を次の式により算出する。
ＰＤＭ運転距離＝ＣＰ間の直線距離を直径とする円周の半分×補正値・・・式５
ここで補正値は、属性ＰＤＭの値とＣＰ間の直線距離の半分との比率からテーブルによって確定する。例えば、図３１（ａ）に示すようにＣＰ（ａ）−ＣＰ（ｂ）間の直線距離の半分をｒとすると、図３１（ｂ）に示すテーブルによって、属性ＰＤＭの値と距離ｒとの比率（ＰＤＭ／ｒ）から補正値を求める。なお、図３１（ｂ）に示したテーブルは、一部を抜粋したものである。
【０１３４】
そして、候補となっている道路の道なりの運転距離を道路運転距離とすると、道路運転距離が次の式を満たす場合に、その道路を「ＯＫ」と判定する。
ＰＤＭ運転距離×０．５＜道路運転距離＜ＰＤＭ運転距離×１．５・・・式６
＜５．４．５ マッチング結果の出力＞
そして、上述したように、これらの判定結果によって道路を絞り込み（図２２中のＳ４３０）、道路が一意に決定されると（Ｓ４４０でＹＥＳ）、Ｓ４５０にてマッチング結果を出力する。マッチング結果は、一意に特定された道路を構成する全リンクのリンクＩＤ、始点オフセット距離、終点オフセット距離などで構成される。なお、始点オフセット距離は、道路の始点となるリンクのどの位置からがマッチングの開始位置かを示す距離である。同様に、終点オフセット距離は、道路の終点となるリンクのどの位置までがマッチングの終了位置かを示す距離である。
＜５．４．６ 道路の決定について＞
なお、通常、道路が一意に決定されないと（Ｓ４４０でＮＯ）、道路マッチング失敗となって、マッチング結果が出力されないことになる。ただし、次のような場合には、道路が一意に決定されたものとする。
【０１３５】
例えば、図３２（ａ）では、ＣＰ（ａ）からＣＰ（ｂ）への道路を探索した結果、ノードＮ１→Ｎ４→Ｎ５→Ｎ２→Ｎ３という道路、及び、ノードＮ１→Ｎ４→Ｎ５→Ｎ２という道路の２つが残ったものとする。このとき、太線で示した道路（ノードＮ１→Ｎ４→Ｎ５→Ｎ２）は、両方の道路に包含されているため、この道路を一意に決定された道路とする。
【０１３６】
また例えば、図３２（ｂ）では、ＣＰ（ａ）からＣＰ（ｂ）への道路を探索した結果、ノードＮ１→Ｎ４→Ｎ５→Ｎ２→Ｎ３という道路、及び、ノードＮ１→Ｎ４→Ｎ６→Ｎ５→Ｎ２→Ｎ３という道路の２つが残ったものとする。このとき、太線で示した道路（ノードＮ１→Ｎ４,Ｎ５→Ｎ２→Ｎ３）は、両方の道路に包含されているため、この分断された２つの道路を一意に決定された道路とする。
【０１３７】
あるいは、図３２（ｂ）に示すような例で、道なりの道路を一意に決定された道路とすることが考えられる。「道なり」とは、図３２（ｃ）に示すように、リンク同士のなす角度（例えば記号ａで示す角度）が所定角度（例えば１５度）以下である場合をいう。
＜６．効果＞
以上詳述したように、本実施例では、図１２に示した候補リンク検索処理において、検索範囲を決定し（Ｓ２２０）、ＣＰを中心とする検索範囲のリンクを抽出する（Ｓ２５０）。つまり、ＣＰで示される道路を推定するにあたり、ＣＰ周辺のリンクを抽出するのであるが、このときＣＰを基準とする検索範囲を設定することにより、妥当な距離にあるリンクを抽出するのである。これにより、ＣＰに対応する適切なリンクを抽出できる可能性が高くなり、ＴＰＥＧデータに含まれる位置情報から、車載機側に用意される地図データ上での道路を適切に推定することができる。
【０１３８】
また、本実施例では、検索範囲が、図１３（ａ）に破線で示したように、その境界が垂直又は水平の線分で構成される多角形として設定される。本実施例では、正方形と当該正方形の一辺よりも長い十字形状とを合成したような範囲として設定されている。これにより、ＣＰから妥当な距離にあるリンクを抽出でき、しかも、境界などの算出処理が煩雑にならず、検索範囲に含まれるか否かの判断が容易になる。
【０１３９】
さらにまた、本実施例では、検索範囲のリンクを抽出する際（図１２中のＳ２５０）、対象ＣＰが交差点である場合は、交差点を示すノードにＣＰが対応付けられる可能性が高いため、リンクを構成する２つのノードのうちのいずれかが検索範囲に含まれているリンクを抽出する（図１５（ａ）参照）。また、対象ＣＰが仮想ＣＰである場合、パーセル境界には必ずノードが設定されるため、パーセル境界に存在するノードが検索範囲に含まれるときは、そのリンクを抽出する（図１５（ｂ）参照）。さらにまた、対象ＣＰが交差点でも仮想ＣＰでもない場合は、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。なお、対象ＣＰが交差点である場合は必ずしもノードに対応付けられるとは限らないため、このときも、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。一定条件を満たす場合とは、形状補間点を結んだ線分の一部が検索範囲に含まれている場合（図１５（ｃ）参照）、及び、２つのノードを結ぶ線分の一部が検索範囲に含まれている場合である（図１５（ｄ）参照）。このように、ＣＰとノードとの対応関係の有無によってリンクの抽出方法を異ならせるため、妥当なリンクを抽出できる可能性が高くなる。
【０１４０】
また、本実施例では、検索範囲に一部が含まれるリンクのうちで属性ＲＤが一致するリンクに絞り込む（図１２中のＳ２６０）。さらにまた、ＣＰからリンクまでの距離に基づいて、リンクの数が「１０」本以内に収まるように絞り込む（Ｓ２７０）。これにより、抽出されるリンクを適切に絞り込むことができ、妥当なリンクを抽出できる可能性が高くなる。
【０１４１】
さらにまた、本実施例では、検索範囲が決定された後（図１２中のＳ２２０）、リンクの抽出（Ｓ２５０）に先立って、検索範囲のパーセルを取得し（Ｓ２３０）、このパーセル単位でリンク列を選定する（Ｓ２４０）。このように最初にリンク列を選定するため、リンク単位の抽出処理を減らすことができ、抽出処理に要する時間を短縮することができる。また、検索範囲によらずパーセル単位でリンク列を選定するため、リンクの抽出に先立つリンク列の選定を迅速に行うことができる。しかも、リンク列の選定では、非形状系の属性である属性ＦＣ、属性ＦＷ、及び、属性ＲＤでの絞り込みを行う（図１４中のＳ２４１〜Ｓ２４３）。つまり、リンク列を選定するにあたり、検索範囲に含まれるか否かを判断するよりも先に、コアポイントの非形状系の属性によってリンク列を絞り込むのである。これにより、リンクの抽出に先立つリンク列の選定をより一層迅速に行うことができる。
【０１４２】
なお、本実施例におけるナビゲーション装置１０が「道路推定装置」に相当し、地図データ入力装置１３が「地図データ入力手段」に相当し、制御回路１７のＣＰＵ１７ａが「検索範囲設定手段」、「リンク抽出手段」、「リンク列選定手段」及び「パーセル取得手段」に相当する。
【０１４３】
そして、図１２中のＳ２２０の処理が「検索範囲設定手段」の機能としての処理に相当し、Ｓ２５０〜Ｓ２７０の処理が「リンク抽出手段」の機能としての処理に相当し、Ｓ２４０の処理（図１４中のＳ２４１〜Ｓ２４３）が「リンク列選定手段」の機能としての処理に相当し、Ｓ２３０の処理が「パーセル取得手段」の機能としての処理に相当する。
【０１４４】
以上、本発明は、上述した実施例に何ら限定されるものではなく、その要旨を逸脱しない範囲において種々なる形態で実施することができる。
（イ）上記実施形態では、検索範囲として図１３（ａ）に示した多角形を採用している。これに対し、処理負荷などを考えないのであれば、例えばＣＰを中心とする円を検索範囲として設定することも考えられる。また、処理負荷を考えてその境界が垂直又は水平の線分で構成される多角形として検索範囲を設定する場合、例えば図１３（ａ）に示したものよりも境界を構成する線分の多い多角形を採用してもよい。また、単純な正方形や長方形を採用してもよい。
【０１４５】
（ロ）上記実施形態では、図１４中のＳ２４３でリンク列を絞り込むときに「道路番号」（属性ＲＤ）を用い、図１２中のＳ２６０でリンクを絞り込むときに「道路名称」（属性ＲＤ）を用いているが、道路番号、道路名称のいずれを用いるかは特に限定されるものではない。また、他の属性を用いてリンク列やリンクを絞り込むようにしてもよい。
【符号の説明】
【０１４６】
１０：ナビゲーション装置
１１：受信装置
１２：位置検出装置
１３：地図データ入力装置
１４：操作デバイス
１５：音声出力デバイス
１６：表示デバイス
１７：制御回路
１７ａ：ＣＰＵ
１７ｂ：ＲＯＭ
１７ｃ：ＲＡＭ
２０：センタ
１７１：選局ブロック
１７２：アプリケーションブロック
１７３：ＤＬＲライブラリブロック
１７４：描画ブロック
【技術分野】
【０００１】
本発明は、道路に沿って付与され、当該道路を特定するための属性を有するコアポイントに基づき、当該コアポイントが示す道路に該当する地図上のリンクを抽出する技術に関する。
【背景技術】
【０００２】
従来、交通情報を放送により転送するサービスとして、ＶＩＣＳ（Vehicle Information and Communication System）が知られている。このサービスは、ＶＩＣＳセンターの持つ道路の渋滞情報などの交通情報を車両に送信し、車両側で地図データを検索して該当する道路を特定し、当該道路の表示態様を、受信した交通情報に応じて変更し、ユーザに提供するものである。これにより、ユーザは、渋滞情報などの交通情報をリアルタイムに把握することができる。
【０００３】
ところで、車載機側の地図データのフォーマットでは、例えば道路がリンクで表現される。ここで、上述のＶＩＣＳセンターからは、道路を特定するＶＩＣＳリンクと呼ばれる情報が送信される。このＶＩＣＳリンクには、様々な交通情報や表示態様の変更指示情報が付与されている。そこで、車載機側では、ＶＩＣＳリンクと地図データにおけるリンクとを照合するための位置参照テーブルを持っており、このテーブルに基づき、ＶＩＣＳリンクに対応するリンクを検索する。つまり、ＶＩＣＳでは、位置参照テーブルが必須となっている（例えば、特許文献１，２参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−２７５７７７号公報（図３）
【特許文献２】特開２００９−２７０９５３号公報（図２，図３１）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、ＶＩＣＳ以外のサービスとして、ＴＰＥＧ（Transport Protocol Expert Group ）により送信される交通情報のデータを車両などの端末側で活用することが検討されている。しかし、ＴＰＥＧにより送信されるデータフォーマット等では、例えばＤＬＲデータの形式で位置情報が示される。この位置情報は、位置座標を有すると共に道路を特定するための属性を有するコアポイントで構成される。コアポイントは、通常、道路に沿って並ぶ複数個の配列として配信される。このようなコアポイントによって位置情報を示すようにすれば、地図データを作成するメーカの違いや地図データのフォーマット、バージョンに依存する位置参照テーブルが不要になる。すなわち、車載機側の地図データに依存せず、地図データ上で道路（リンク）を特定することが可能となる。
【０００６】
その反面、コアポイントに基づいて道路を特定するための種々の処理が必要になってくる。例えば、上述したように地図データにもいろんな種類があるため、必ずしもコアポイントは地図データの道路上に存在しない。そのため、コアポイントが示す道路に該当するリンクを地図上で特定する処理が必要となってくる。
【０００７】
しかしながら、コアポイント周辺のリンクを候補として抽出する際、抽出するリンク数が多くなれば抽出処理に要する時間が長くなる虞がある。また、抽出するリンク数が少なくなればコアポイントが示す道路に該当するリンクが候補から外れる虞がある。
【０００８】
本発明は、上述した問題を解決するためになされたものであり、配信されるコアポイントの情報から、車載機側に用意される地図データ上で該当するリンクを適切に抽出し、コアポイントが示す道路を推定する道路推定装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した目的を達成するためになされた請求項１に記載の道路推定装置は、道路に沿って付与され当該道路を特定するための属性を有するコアポイントに基づき、当該コアポイントが示す前記道路に該当する地図上のリンクを抽出することで道路を推定するものである。なお、コアポイントは配列として複数送信されるのが一般的であるが、コアポイントが一つだけ送信される場合も含む。
【００１０】
本装置では、地図データ入力手段が、地図データを入力する。地図データは、コアポイントの有する属性に応じた属性を有するリンクで構成される。
また、検索範囲設定手段が、コアポイントを基準にして検索範囲を設定する。この検索範囲が、後述するようにリンク抽出の範囲となるものである。「コアポイントを基準」にする場合、例えばコアポイントを中心とした検索範囲を設定することが考えられる。コアポイントを中心とすれば、妥当な検索範囲が設定されるためである。ただし、必ずしもコアポイントを中心とする必要はなく、中心から外れた位置にコアポイントが位置するような検索範囲を設定してもよい。
【００１１】
このとき、リンク抽出手段によって、地図データ入力手段にて入力された地図データを構成するリンクのうちで、検索範囲に含まれるリンクが抽出される。そして、抽出されたリンクの有する属性とコアポイントの有する属性とに基づき、コアポイントが示す道路を推定する。
【００１２】
つまり、コアポイントで示される道路に該当するリンクを抽出するにあたり、コアポイント周辺のリンクを抽出するのであるが、このときコアポイントを基準とする検索範囲を設定することにより、妥当な距離にあるリンクを抽出するのである。これにより、抽出するリンク数が多くなりすぎて抽出処理に要する時間が長くなったり、また、抽出するリンク数が少なすぎてコアポイントが指し示す道路に該当するリンクが候補から外れたりすることを抑制できる。その結果、配信されるコアポイントの情報から、車載機側に用意される地図データ上で該当するリンクを適切に抽出し、コアポイントが示す道路を推定することができる。
【００１３】
なお、「検索範囲に含まれるリンク」は、検索範囲に完全に含まれるリンクをいうものとすることが考えられる。ただし、コアポイントが指し示す道路に該当するリンクが候補から外れるという事態を極力なくすという観点からは、検索範囲を比較的大きく設定する必要が生じる。この場合、抽出処理に要する時間が長くなることが懸念される。
【００１４】
そこで、請求項２に示すように、リンク抽出手段が、地図データを構成するリンクのうちで、検索範囲に少なくとも一部が含まれるリンクを抽出することとしてもよい。このようにすれば、比較的小さな検索範囲を設定することができ、抽出処理に要する時間を短くできると共に、コアポイントが指し示す道路に該当するリンクが候補から外れるという事態を極力なくすことができる。
【００１５】
なお、当初からリンク単位での抽出を行うと、リンクの数が多くなってしまい、抽出処理に要する時間が長くなる虞がある。そこで、リンク抽出手段によるリンクの抽出に先立って、リンク列を選定するようにしてもよい。「リンク列」とは、同一の道路区分となっている一連のリンク群をいう。例えば請求項３に示すように、リンク列選定手段が、検索範囲に基づき、地図データ入力手段にて入力された地図データのリンクの配列であるリンク列を選定する。このとき、リンク抽出手段は、リンク列選定手段にて選定されたリンク列を構成するリンクの中から検索範囲に含まれるリンクを抽出する。このように最初にリンク列を選定すれば、リンク単位での処理を減らすことができ、抽出処理に要する時間を短縮することができる。
【００１６】
また、リンク列の選定にあたって当該リンク列が検索範囲に含まれるか否かを判断するようにしてもよいが、処理が煩雑になる虞がある。そこで、請求項４に示すように、分割領域特定手段が検索範囲に少なくとも一部が含まれる分割領域である検索対象分割領域を特定するようにし、リンク列選定手段によって、検索対象分割領域に少なくとも一部が含まれるリンク列が選定されるようにするとよい。つまり、ここでは、リンク列が分割領域の単位で選定されるのである。このようにすれば、リンクの抽出に先立つリンク列の選定を迅速に行うことができる。
【００１７】
このようにリンク列を抽出する際、請求項５に示すように、検索対象分割領域に一部が含まれるリンク列から、コアポイントの有する非形状系の属性である道路のクラスを示す道路区分（属性ＦＣ）、道路の種別を示す物理道路タイプ（属性ＦＷ）、及び、道路番号又は道路名称を示す道路固有情報（属性ＲＤ）の少なくともいずれかが一致するリンク列を選定することが考えられる。このとき、請求項６に示すように、検索範囲に含まれるか否かの判断に先立って、コアポイントの有する非形状系の属性によってリンク列を絞り込むようにするとよい。このようにすれば、リンクの抽出に先立つリンク列の選定をより一層迅速に行うことができる。なお、コアポイントの属性ＲＤの値は、道路番号が存在すれば道路番号となっており、存在しなければ道路名称（道路の公式名の最大５文字）となっている。
【００１８】
ところで、上述したようにコアポイントを基準として検索範囲を設定する際、コアポイントから等距離にある範囲を設定することが好ましい。したがって、コアポイントを中心とする円を検索範囲とすることが考えられる。しかし、検索範囲を円とした場合、境界などの算出処理が煩雑になり、検索範囲に含まれるか否かの判断が複雑になる。
【００１９】
そこで、請求項７に示すように、その境界が垂直又は水平の線分で構成される多角形を検索範囲として設定するようにするとよい。例えば、図１３（ａ）に示すごとくである。
図１３（ａ）に示すように十字形と正方形とを合成した検索範囲を設定すれば、コアポイントから妥当な距離にあるリンクを抽出でき、しかも、境界などの算出処理が煩雑にならず、検索範囲に含まれるか否かの判断が容易になる。もちろん、図１３（ａ）に示した形状には限定されず、さらに境界を構成する線分が多い多角形の検索範囲を設定してもよいし、正方形や長方形などの検索範囲を設定するようにしてもよい。
【００２０】
なお、リンク抽出手段がリンクを抽出する際、コアポイントが交差点を示すものであるか否かによって、比較的容易にリンクを抽出することができる。
具体的には、請求項８に示すように、リンク抽出手段は、コアポイントが道路の交差点を示すものである場合、交差点を端点とするリンクであって、当該端点が検索範囲に含まれるリンクを抽出することが例示される。通常の地図データでは、リンクの端点が交差点となる。例えばリンクの端点にノードを有する地図データでは、交差点に対してノードが設定されるという具合である。したがって、コアポイントが交差点を示すものであれば、リンクの端点と対応付けられる。したがって、交差点を端点とし当該端点が検索範囲に含まれるリンクを抽出することが考えられる。このようにすれば、妥当なリンクを抽出できる可能性が高くなる。
【００２１】
一方、請求項９に示すように、リンク抽出手段は、コアポイントが道路の交差点を示すものでない場合、リンクの端点が検索範囲に含まれない場合であっても、リンクの一部が検索範囲に含まれていれば、当該リンクを抽出することが例示される。例えばリンクに形状補間点が設定されることを前提とし、形状補間点が検索範囲にあれば、そのリンクを抽出することが考えられる。また、形状補間点がない場合、端点を結ぶリンクの一部が検索範囲に含まれていれば、そのリンクを抽出することが考えられる。このようにすれば、妥当なリンクを抽出できる可能性が高くなる。
【００２２】
また、リンク抽出手段がリンクを抽出する際、その前提として仮想コアポイントを付与する構成であれば、比較的容易にリンクを抽出することができる。
具体的には、請求項１０に示すように、地図データ入力手段が、分割領域の単位で、分割領域の境界に端点を有するリンクで構成される地図データを入力する。このとき、コアポイントに基づき、分割領域の境界に新たなコアポイントである仮想コアポイントを付与することを前提に、リンク抽出手段は、コアポイントが仮想コアポイントである場合、分割領域の境界に端点を有するリンクであって、当該端点が検索範囲に含まれるリンクを抽出することが考えられる。通常の地図データでは、分割領域の境界にリンクの端点が設定される。例えばリンクの端点にノードを有する地図データでは、分割領域の境界にノードが設定されるという具合である。したがって、コアポイントが仮想コアポイントであれば、分割領域境界のどこかにあるリンクの端点と対応付けられる。したがって、交差点を端点とし当該端点が検索範囲に含まれるリンクを抽出することが考えられる。このようにすれば、妥当なリンクを抽出できる可能性が高くなる。
【００２３】
一方、請求項１１に示すように、リンク抽出手段は、コアポイントが仮想コアポイントでない場合、リンクの端点が検索範囲に含まれない場合であっても、リンクの一部が検索範囲に含まれていれば、当該リンクを抽出することが例示される。例えばリンクに形状補間点が設定されることを前提とし、形状補間点が検索範囲にあれば、そのリンクを抽出することが考えられる。また、形状補間点がない場合、端点を結ぶリンクの一部が検索範囲に含まれていれば、そのリンクを抽出することが考えられる。このようにすれば、妥当なリンクを抽出できる可能性が高くなる。
【００２４】
ところで、検索範囲の全てのリンクを抽出しようとした場合、リンクの数が多くなってしまう虞がある。
そこで、例えば請求項１２に示すように、リンク抽出手段は、コアポイントの非形状系の属性である道路番号又は道路名称を示す道路固有情報（属性ＲＤ）に基づき、検索範囲に基づいて抽出されるリンクを絞り込むようにしてもよい。
【００２５】
上述したように、コアポイントの属性ＲＤの値は、道路番号が存在すれば道路番号となっており、存在しなければ道路名称（道路の公式名の最大５文字）となっている。したがって、この属性ＲＤの値によって、リンクを絞り込むようにしてもよい。このようにすれば、妥当なリンクを抽出できる可能性が高くなる。
【００２６】
また、例えば請求項１３に示すように、リンク抽出手段は、コアポイントまでの距離に基づき、検索範囲に基づいて抽出したリンクを絞り込むようにしてもよい。例えばコアポイントからリンクに下ろした垂線の長さによって、所定本数（例えば、１０本）のリンクに絞り込むことが考えられる。このようにすれば、適切にリンクを絞り込むことができ、妥当なリンクを抽出できる可能性が高くなる。
【図面の簡単な説明】
【００２７】
【図１】ナビゲーション装置の構成を示すブロック図である。
【図２】制御回路の動作を示す機能ブロック図である。
【図３】マッチング処理を示すフローチャートである。
【図４】変換後のＣＰの属性を示す説明図である。
【図５】属性ＦＣの値と内容とを示す説明図である。
【図６】属性ＦＷの値と内容とを示す説明図である。
【図７】属性ＩＴの値と内容とを示す説明図である。
【図８】マッチング処理における変換処理を示すフローチャートである。
【図９】対象パーセルに跨ってＣＰが存在することを示す説明図である。
【図１０】仮想ＣＰの付与及びパーセル境界における処理を示す説明図である。
【図１１】属性ＰＣＩの計算ルールを示す説明図である。
【図１２】マッチング処理における候補リンク検索処理を示すフローチャートである。
【図１３】対象ＣＰに対する検索範囲及びパーセル取得を示す説明図である。
【図１４】候補リンク検索処理でのリンク列選定処理を示すフローチャートである。
【図１５】検索範囲に対するリンク列の抽出を示す説明図である。
【図１６】マッチング処理における候補選定処理を示すフローチャートである。
【図１７】候補選定処理での非形状系属性の一致判定を示すフローチャートである。
【図１８】候補選定処理での形状系属性の一致判定を示すフローチャートである。
【図１９】属性ＢＲに基づく一致判定を示す説明図である。
【図２０】形状系属性の一致判定における属性ＰＣＩでの一致判定を示すフローチャートである。
【図２１】属性ＣＡ及び属性ＤＣＡに基づく一致判定を示す説明図である。
【図２２】マッチング処理における道路マッチング処理を示すフローチャートである。
【図２３】道路探索の省略方法を示す説明図である。
【図２４】道路探索の省略方法を示す説明図である。
【図２５】道路探索の中止方法を示す説明図である。
【図２６】道路マッチング処理での候補選定を示すフローチャートである。
【図２７】属性ＣＡ及び属性ＤＣＡに基づく道路選定を示す説明図である。
【図２８】属性ＢＲ及び属性ＤＭＢに基づく道路選定を示す説明図である。
【図２９】属性ＰＤに基づく道路長の算出を示す説明図である。
【図３０】属性ＰＤに基づく道路選定を示す説明図である。
【図３１】属性ＰＤＭに基づく道路選定を示す説明図である。
【図３２】道路の決定方法を示す説明図である。
【発明を実施するための形態】
【００２８】
以下に本発明の実施例について、図面と共に説明する。
＜１．ナビゲーション装置の構成＞
最初にナビゲーション装置の構成を図１に基づいて説明する。図１に示すナビゲーション装置１０が「道路推定装置」として機能し、具体的には、ＴＰＥＧ（Transport Protocol Expert Group ）データを受信し、データ中の位置情報から道路のマッチングを行い、位置情報と共に送信される交通情報を道路に対応させて表示する。
【００２９】
図１に示すナビゲーション装置１０は、受信装置１１、位置検出装置１２、地図データ入力装置１３、操作デバイス１４、音声出力デバイス１５、表示デバイス１６、及び、制御回路１７を備えている。
【００３０】
受信装置１１は、センタ２０からＴＰＥＧデータを受信するためのものである。ナビゲーション装置１０では、制御回路１７にて選局を行うことにより、受信装置１１を介してＴＰＥＧデータを取得する。
【００３１】
位置検出装置１２は、ナビゲーション装置１０を搭載した車両の現在位置を検出するためのものであり、例えば、周知のジャイロスコープ、距離センサ及びＧＰＳ受信機等を有している。
【００３２】
地図データ入力装置１３は、地図データが格納された記録媒体（具体的にはハードディスクやＤＶＤ）を有するものであり、この記録媒体に格納された地図データを制御回路１７に入力可能に構成されている。なお、地図データ入力装置１３は、地図データを記憶保持するハードディスク装置に加えてＤＶＤドライブを備えた構成にすることができる。このように地図データ入力装置１３を構成すれば、ナビゲーション装置１０は、ＤＶＤメディアを通じてオプション販売される地図データの追加データを、ハードディスク装置にインストール可能な構成にすることができる。なお、地図データは、パーセルと呼ばれる単位で管理され、パーセル単位でキャッシュされる。
【００３３】
操作デバイス１４は、ユーザからの指示を制御回路１７に入力するためのものであり、表示デバイス１６に配置されたタッチパネルや、ナビゲーション装置１０の本体表面やリモートコントローラに設けられた操作スイッチ群等により構成される。この操作デバイス１４を通じて、ユーザは、地図の縮尺変更やスクロール等の操作や目的地設定などナビゲーション装置１０のあらゆる操作を行うことが可能である。
【００３４】
また、音声出力デバイス１５は、スピーカ等から構成され、制御回路１７からの信号を受けてユーザへの案内音声等を出力するものである。この他、表示デバイス１６は、フルカラー表示が可能なものであり、この表示デバイス１６には、受信装置１１を介して取得されるＴＰＥＧデータに基づく交通情報が、地図データ入力装置１３より入力された地図データに基づく地図画像に重ねて表示される。
【００３５】
また、制御回路１７は、周知のマイクロコンピュータと同様の構成となっており、内部にＣＰＵ１７ａ、ＲＯＭ１７ｂ、ＲＡＭ１７ｃ、Ｉ／Ｏ及びこれらの構成を接続するバスラインなどを備える。そして、ＣＰＵ１７ａは、ＲＯＭ１７ｂに記憶されているプログラムに従って、種々の処理を行う。例えば、受信装置１１を介して受信されるＴＰＥＧデータにはＤＬＲ（Dynamic Location Referencing）データとしての位置情報が含まれる。したがって、制御回路１７は、この位置情報を基に、地図データ側で該当する道路（リンク）を推定する。
＜２．制御回路の機能＞
次に、ＴＰＥＧデータの処理に関する制御回路１７の機能を、図２に基づいて説明する。図２は、制御回路１７の機能を模式的に示す説明図である。
【００３６】
制御回路１７の機能は、選局ブロック１７１、アプリケーションブロック１７２、ＤＬＲライブラリブロック１７３、及び、描画ブロック１７４に分けられる。
選局ブロック１７１は、上述した受信装置１１を介し、ＴＰＥＧデータを受信するブロックである。つまり、選局ブロック１７１が、上述した選局機能を有している。受信されるＴＰＥＧデータは、選局ブロック１７１からアプリケーションブロック１７２へ渡される。
【００３７】
アプリケーションブロック１７２は、アプリケーションプログラムの機能として実現される。アプリケーションプログラムは、ＲＯＭ１７ｂに記憶されており、ＣＰＵ１７ａによって実行される。
【００３８】
アプリケーションブロック１７２は、選局ブロック１７１から受け渡されるＴＰＥＧデータを管理し、新たなＴＰＥＧデータが受信されると、ＴＰＥＧデータの更新を行う。また、アプリケーションブロック１７２は、画面に表示される表示対象のパーセル（以下「対象パーセル」という）を特定するための情報を有している。表示画面は、縮尺によって１つの対象パーセルで構成されることもあるし、複数（例えば９つ）の対象パーセルで構成されることもある。アプリケーションブロック１７２は、対象パーセルの情報、及び、ＴＰＥＧデータの位置情報を「対象データ」としてＤＬＲライブラリブロック１７３へ渡す。
【００３９】
ＤＬＲライブラリブロック１７３は、ＤＬＲライブラリプログラムの機能として実現される。ＤＬＲライブラリプログラムは、アプリケーションプログラムと同様、ＲＯＭ１７ｂに記憶されており、ＣＰＵ１７ａによって実行される。
【００４０】
ＤＬＲライブラリブロック１７３は、後述するマッチング処理を実行する。マッチング処理は、ＴＰＥＧデータの位置情報に基づき、地図データ入力装置１３から入力される地図データでの該当する道路（リンク）を推定するものである。このようなマッチング処理に先立ち、ＤＬＲライブラリ１７３は、アプリケーションブロック１７２からの要請により、地図データ入力装置１３から地図データをＲＡＭ１７ｃに読み込む。マッチング処理の結果は、ＤＬＲライブラリ１７３により、マッチング結果としてアプリケーションブロック１７２へ出力される。
【００４１】
アプリケーションブロック１７２は、マッチング結果を管理する。そして、描画ブロック１７４によって、マッチング結果に基づく地図更新が行われる。これにより、上述したように、ＴＰＥＧデータに基づく交通情報が、地図データ入力装置１３より入力された地図データに基づく地図画像に重ねて表示される。
＜３．マッチング処理＞
本実施例は、ＤＬＲライブラリブロック１７３によるマッチング処理に特徴を有している。そこで、次にマッチング処理について説明する。図３は、マッチング処理を示すフローチャートである。
【００４２】
最初のＳ１００では、変換処理を行う。この変換処理は、ＴＰＥＧデータのＤＬＲとしての位置情報（バイナリデータ）を、中間データに変換するものである。ＴＰＥＧデータの位置情報には離散的な地点が主として用いられることは既に述べたが、これらの離散的な地点は、コアポイント（以下「ＣＰ」という）と呼ばれる。そして、ＣＰは、様々な属性を有している。そこで、ここでは、道路推定に必要な属性を取り出して、中間データを作成する。
＜３．１ 変換後のＣＰの属性＞
中間データへの変換後のＣＰが有する属性を図４に示す。通常、複数個のＣＰがＴＰＥＧデータの位置情報として送信される。したがって、ＣＰは配列して管理される。もちろん、一つだけのＣＰから位置を推定することも可能であり、ＣＰが一つだけ送信される場合を排除する趣旨ではない。
【００４３】
ＣＰは、基本的な属性として、図４に示すように、緯度、経度、ＩＰフラグ、仮想ＣＰフラグを有している。緯度は、ＣＰの緯度座標であり、経度は、ＣＰの経度座標である。また、ＩＰフラグは、ＣＰが交差点か否かを示すフラグである。ＣＰが交差点を示す場合には「１」がセットされ、それ以外の場合には「０」がセットされる。さらにまた、仮想ＣＰフラグは、ＣＰが仮想ＣＰか否かを示すフラグである。ＣＰが仮想ＣＰである場合には「１」がセットされ、それ以外の場合には「０」がセットされる。なお、仮想ＣＰについては後述する。
【００４４】
また、ＣＰは、ＣＰ間を繋ぐ道路に関し、種々の属性を有している。これらの属性には、道路形状に関わる形状系の属性と、道路形状に関わらない非形状系の属性とがある。まずは、非形状系の属性を説明する。
＜３．１．１ 非形状系の属性＞
属性ＦＣは、道路区分を示すものである。図５に一例を示すように、道路のクラスは、「０」〜「９」の１０段階で示される。「０」が「Main road 」であり、「１」が「First class road」であり、「２」が「Second class road 」である。以下同様に、「９」の「Ninth class road」までランク付けされている。例えば、「Main road 」は国や首都に接続されている道路であり、「first class road 」は主要都市間を結ぶ国道であるという具合に、ランク付けされている。
【００４５】
属性ＦＷは、物理道路タイプを示すものである。図６に一例を示すように、物理道路タイプは、「０」〜「１２」の１３種類に分けられている。図６を見ると、「不明確」の場合は「０」であり、「高速道路」は「１」であり、「複数車道（高速道路以外）」は「２」であり、「単一車道」は「３」であり、「ロータリー」は「４」であり、「トラフィックスクエア」は「５」であり、「取り囲まれた交通エリア」は「６」であり、「バイパス」は「７」であり、「支線道路」は「８」であり、「駐車場入口又は出口」は「９」であり、「サービスエリア入口又は出口」は「１０」であり、「歩行者地帯」は「１１」であり、「通路」は「１２」である。
【００４６】
属性ＲＤは、道路番号（例えば国道「１」号などの国道番号）が存在すれば、その道路番号がＲＤ値となる。また、道路番号が存在しない場合、道路名称がＲＤ値となる。道路名称は、公式名の最大５文字となっている（図４参照）。
【００４７】
属性ＩＴは、交差点の分類を示す（図４参照）。図７に一例を示すように、交差点の分類は、「０」〜「６」の７種類に分けられている。図７を見ると、「未定義」の場合は「０」であり、「高速又は制限された道路のインターチェンジ」は「１」であり、「ロータリー」は「２」であり、「１，２以外の複雑な交差点」は「３」であり、「単純な交差点」は「４」であり、「トラフィックスクエア」は「５」であり、「２価の交差点（道路番号や道路名称が切り替わる交差点）」は「６」である。
【００４８】
属性ＲＤＩは、交差点の名称を示す（図４参照）。
属性ＤＤは、許可された合法の運転方向を示す（図４参照）。例えば、「未定義」は「０」となっており、「順方向」が「１」となっており、同様に、「逆方向」が「２」、「両方向」が「３」となっているという具合である。なお、属性ＡＦＲは、属性ＤＤが参照可能であるか否かを示すフラグである。属性ＤＤが「０」〜「３」の値を持っている場合に属性ＡＦＲは「１」にセットされ、属性ＤＤが値を持っていない場合には、参照不可として「０」がセットされる。
＜３．１．２ 形状系の属性＞
次に形状系の属性を説明する。
【００４９】
属性ＢＲは、次のＣＰへの位置的な角度を示す（図４参照）。上述したように、通常、複数個のＣＰが配列として管理される。ＢＲ値は、真北を基準とする時計回りの角度である。
【００５０】
属性ＤＭＢは、次のＣＰへの直線距離を示す（図４参照）。属性ＢＲと同様、通常、次のＣＰが存在するため、次のＣＰへの直線距離がＤＭＢ値となっている。
属性ＣＡは、脇道に対する角度を示す。脇道とは、道路番号が付加されないようなマイナーな道路である。脇道がある場合、属性ＢＲの角度を基準に時計回りを「正」とし、反時計回りを「負」とする角度がＣＡ値として設定される。属性ＤＣＡは、脇道に対する接続距離を示す。
【００５１】
すなわち、ＣＰからのベクトルを考えた場合、属性ＣＡがベクトルの方向を示し、属性ＤＣＡがベクトルの大きさを示すことになる。したがって、属性ＣＡ及び属性ＤＣＡによって、位置座標が決定される。この位置座標が脇道の存在する地点を示すこととなる。
【００５２】
属性ＰＣＩは、同一方向において複数の車道が存在する場合、いずれの車道が選択されるかを示す（図４参照）。この属性ＰＣＩには、車道数及び、対象道路が当該車道のうちの何番目かを示すシーケンス番号が含まれる。
【００５３】
属性ＰＤＭは、次のＣＰまでを結ぶ直線からの対象道路の離間距離を示す（図４参照）。この離間距離には、対象道路までの最大距離が設定される。
属性ＰＤは、次に属性ＰＤを含むＣＰまでの対象道路に沿った道なりの運転距離を示す（図４参照）。
【００５４】
以上、中間データへの変換後のＣＰの有する属性について説明したが、このようなＣＰに対しての変換に伴い、仮想ＣＰの付与、ＣＰの属性値の再計算が実行される。具体的な手順は、図８に示すごとくである。
＜４．マッチング処理の詳細（前半）＞
図８中のＳ１１０では、対象パーセルの境界に仮想ＣＰを付与する。図９は、ＣＰによって表される道路形状を便宜的に二点鎖線で示す説明図である。もちろん、このような道路形状を推定し、地図データのリンク列で示される道路とのマッチングを行うことが終局的な目標である。したがって、図９中に二点鎖線で示す道路形状は、便宜的なものであり、実際の道路形状を示すものではない。ここで重要なのは、図９に示すように、ＣＰの配列が対象パーセルだけでなくその周囲のパーセルにも跨ることがある、ということである。このような場合に、対象パーセルの境界に仮想ＣＰを付与する。
【００５５】
具体的には、図１０（ａ）に示すように、２つのＣＰ（ａ），ＣＰ（ｂ）が対象パーセルの境界を跨いでいるような場合、属性ＰＤＭの値により与えられる道路形状の頂点ＶとＣＰ（ａ），ＣＰ（ｂ）とを結ぶ線分を算出し、線分の一方と対象パーセルの境界との交点に仮想ＣＰを付与する。なお、以下、複数のＣＰを区別するために記号ａ，ｂ，ｃ，・・・を用い、ＣＰ（ａ），ＣＰ（ｂ），ＣＰ（ｃ）と示す。
＜４．１ 属性の再計算＞
次のＳ１２０では、ＣＰの属性を再計算する。仮想ＣＰを付与することで、終端側のＣＰ（図１０（ａ）ではＣＰ（ｂ））は、後述するように、処理対象のＣＰから外される。そこで、始端側のＣＰ（図１０（ａ）ではＣＰ（ａ））及び仮想ＣＰの属性を再計算する。再計算される属性は、属性ＢＲ、属性ＤＭＢ、属性ＰＣＩ、属性ＣＡ、属性ＤＣＡ、属性ＰＤＭ、及び、属性ＰＤである。
【００５６】
属性ＢＲ及び属性ＤＭＢは、次のＣＰへの角度及び直線距離である（図４参照）。したがって、新たに付与した仮想ＣＰを含め、次のＣＰへの角度及び直線距離を計算して設定する。
【００５７】
属性ＣＡ及び属性ＤＣＡについては、始端側のＣＰ（図１０（ａ）ではＣＰ（ａ））での再計算は行わない。また、仮想ＣＰには、無効値を設定する。属性ＣＡ及び属性ＤＣＡは、脇道に関するものであり、仮想ＣＰには脇道の情報が妥当しないためである。
【００５８】
属性ＰＣＩは、並行する車道数に関するものである（図４参照）。したがって、始端側のＣＰ（図１０（ａ）ではＣＰ（ａ））での再計算は行わない。仮想ＣＰには、始端側及び終端側（図１０（ａ）ではＣＰ（ａ），ＣＰ（ｂ））に設定されているＰＣＩに従った値を設定する。
【００５９】
仮想ＣＰに対する属性ＰＣＩの具体的な計算ルールを図１１に示す。始端側のＣＰ及び終端側のＣＰがいずれも属性ＰＣＩを保持する場合、両ＣＰでの属性ＰＣＩが一致する場合には、仮想ＣＰに対し、両ＣＰと同一の値を設定する。一方、両ＣＰでの属性ＰＣＩが不一致である場合、仮想ＣＰに対し無効値を設定する。
【００６０】
また、始端側のＣＰ及び終端側のＣＰのいずれか一方が属性ＰＣＩを保持する場合、仮想ＣＰが、属性ＰＣＩを保持するＣＰの近傍にある場合には、そのＣＰと同一の値を設定する。一方、仮想ＣＰが属性ＰＣＩを保持するＣＰの近傍にない場合には、無効値を設定する。なお、近傍とは、例えば、属性ＰＣＩを保持するＣＰから仮想ＣＰまでの直線距離が始端側のＣＰと終端側のＣＰとの直線距離の１０％以下である場合をいう。
【００６１】
さらにまた、始端側のＣＰ及び終端側のＣＰのいずれも属性ＰＣＩを保持していない場合、仮想ＣＰに対し無効値を設定する。
属性ＰＤＭは、次のＣＰまでを結ぶ直線からの道路の離間距離である（図４参照）。この属性ＰＤＭについては、仮想ＣＰを付与する前の値に補正値を乗じて、設定する。具体的には、仮想ＣＰの配置位置割合を算出し、次の式で補正値を計算する。
【００６２】
（ｉ）配置位置割合が５０％未満のとき
補正値＝０．６×配置位置割合／１００・・・式１
（ｉｉ）配置位置割合が５０％以上のとき
補正値＝１．４×配置位置割合／１００−０．４・・・式２
ここで、配置位置割合は、次の式で計算される。
【００６３】
始端側のＣＰの属性ＰＤＭを再計算するときの配置位置割合は、
始端側ＣＰと仮想ＣＰとの直線距離／始端側ＣＰから終端側ＣＰまでの直線距離合計
・・・式３
となる。
【００６４】
また、仮想ＣＰの属性ＰＤＭを再計算するときの配置位置割合は、
仮想ＣＰと終端側ＣＰとの直線距離／始端側ＣＰから終端側ＣＰまでの直線距離合計
・・・式４
となる。
【００６５】
なお、直線距離合計は、始端側ＣＰから終端側ＣＰまでの仮想ＣＰを経由した場合の直線距離の合計であり、始端側ＣＰと仮想ＣＰとの直線距離及び仮想ＣＰと終端側ＣＰとの直線距離の合計となる。
【００６６】
属性ＰＤは、属性ＰＤを有する次のＣＰまでの運転距離であり（図４参照）、必ずしもＣＰに付与される属性ではない。そのため、パーセル境界を跨ぐ２つのＣＰが属性ＰＤを持たない場合がある。そこで、属性ＰＤを持つＣＰのうちで仮想ＣＰに最も近いＣＰを用いて再計算を行う。なお、属性ＰＤを有するＣＰが存在しない場合、属性ＰＤの再計算は行わない。
【００６７】
具体的には、ＣＰが有する属性ＰＤの値を、仮想ＣＰまでの直線距離に応じて按分する。すなわち、ＣＰの属性ＰＤの値は、ＣＰの元の属性値ＰＤの値に、上記式３の配置位置割合を乗じて求める。また、仮想ＣＰの属性ＰＤの値は、始点ＣＰの元の属性値ＰＤの値に、上記式４の配置位置割合を乗じて求める。
＜４．２ ＣＰの絞り込み＞
ここで図８の説明に戻り、Ｓ１３０では、対象パーセル内のＣＰに絞り込む。この処理は、対象パーセル内のＣＰだけ（仮想ＣＰを含む）を処理対象とするものである。ＣＰの配列は対象パーセルの境界を越えて続いていくことが考えられるが、アプリケーションで表示対象としている対象パーセルについてのみマッチングを行えば十分だからである。
＜４．２．１ 仮想ＣＰを付与しない方法＞
なお、本実施例では仮想ＣＰを付与することにより対象パーセルの境界にＣＰが存在するものとして当該仮想ＣＰまでを処理対象としているが、ＤＬＲデータとして引き渡される本来のＣＰを対象パーセルの終端ＣＰとして処理を行うようにしてもよい。
【００６８】
例えば、図１０（ｂ）に示すように対象パーセルの境界をＣＰが跨いでいる場合、対象パーセル内のＣＰ（ａ）を終端ＣＰとしてもよい。又は、対象パーセル外の最初に現れるＣＰ（ｂ）を終端ＣＰとしてもよい。ただし、ＣＰ（ａ），ＣＰ（ｂ）が対象パーセルの境界から離れて存在する場合があるため、例えばＣＰ（ａ），ＣＰ（ｂ）の対象パーセルの境界からの離れ具合に応じて、いずれのＣＰを終端ＣＰとするかを判断するようにしてもよい。
【００６９】
一例として、図１０（ｂ）に示すように、２つのＣＰ（ａ），ＣＰ（ｂ）を結ぶ直線と対象パーセルの境界との交点Ｋを算出し、交点Ｋまでの直線距離Ａ，Ｂで離れ具合を測ることが考えられる。
【００７０】
このとき、通常は対象パーセルの外側にあるＣＰ（ｂ）を終端ＣＰとし、直線距離Ｂが所定値以上となった場合に、対象パーセルの内側にあるＣＰ（ａ）を終端ＣＰとすることが例示される。このときは、通常、ＣＰ（ｂ）までが処理対象となるため、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報を十分に表示することができる。また、例えばＣＰ（ｂ）が高速道路を示すような場合、ＣＰ（ｂ）が対象パーセルの境界から極端に離れてしまう場合、ＣＰ（ａ）までが処理対象となるため、処理に要する時間が長くなることを抑制できる。
【００７１】
あるいは、通常は対象パーセルの内側にあるＣＰ（ａ）を終端ＣＰとし、直線距離Ａが所定値以上となった場合に、対象パーセルの外側にあるＣＰ（ｂ）を終端ＣＰとすることが例示される。このときは、通常、ＣＰ（ａ）までが処理対象となるため、処理に要する時間を極力短くすることができる。また、例えばＣＰ（ａ）が対象パーセルの境界から極端に離れてしまう場合、ＣＰ（ｂ）までが処理対象となるため、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報の表示が不十分になることを抑制できる。
【００７２】
またあるいは、直線距離Ａ，Ｂを比較し、直線距離Ａが直線距離Ｂよりも小さい場合に対象パーセルの内側にあるＣＰ（ａ）を終端ＣＰとし、一方、直線距離Ｂが直線距離Ａよりも小さい場合に対象パーセルの外側にあるＣＰ（ｂ）を終端ＣＰとすることが例示される。このときは、直線距離に応じて終端ＣＰが決定されるため、ＣＰ（ｂ）までが処理対象となる場合には、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報を十分に表示することができる。一方、ＣＰ（ａ）までが処理対象となる場合には、処理に要する時間を極力短くすることができる。
【００７３】
いずれにしても、仮想ＣＰを付与する構成に比べ、仮想ＣＰの付与に関する処理に要する時間が短縮される点、また、仮想ＣＰの付与に伴う属性の再計算の処理に要する時間が短縮される点で有利である。
＜４．２．２ 属性の引き継ぎ＞
ところで、図８中のＳ１３０では、処理対象のＣＰを決定するに伴い、属性の引き継ぎ処理も行われる。
【００７４】
ＤＬＲデータとしてのＣＰでは、交差点を示すＣＰ（ＩＰフラグがセットされているＣＰ）だけが各種の属性を有している。そこで、このようなＣＰが有する非形状系の属性を、交差点間に存在するＣＰへ引き継ぐ。これにより、後述する処理で都度、非形状系の属性を取得する手間を省くことができる。具体的に引き継がれる属性は、属性ＦＣ、属性ＦＷ、属性ＲＤ、属性ＤＤ、及び、属性ＡＦＲである。
【００７５】
以上説明した変換処理により、中間データに変換されたＣＰの配列が作成されることになる。つまり、この段階で、ＣＰは、図４に示した各種の属性を有するものとなっている。一方で、地図データを構成するノード及びリンクの少なくともいずれかが、ＣＰの属性に対応する属性を有している。そこで、各種属性を比較することで、終局的にＣＰにより示される道路を推定する。
＜５．マッチング処理の詳細（後半）＞
図３のマッチング処理の説明に戻り、Ｓ２００では、候補リンク検索処理を実行する。候補リンク検索処理は、候補となるリンク列を検索し、その後、リンク単位で絞り込みを行うものである。次のＳ３００では、候補選定処理を実行する。候補選定処理は、Ｓ２００にて絞り込まれたリンクを、さらに絞り込むものである。続くＳ４００では、道路マッチング処理を実行する。道路マッチング処理は、ＣＰ間を繋ぐリンクを推定するものである。これらＳ２００〜Ｓ４００の処理は、図８中のＳ１３０で絞り込まれる各ＣＰを対象ＣＰとしてＣＰの数だけ繰り返し実行される。
【００７６】
そこで、以下では、これらの処理を詳細に説明する。Ｓ２００の候補リンク検索処理の一例を図１２に示す。
最初のＳ２１０では、対象ＣＰの情報が取得される。この処理は、ＣＰの種類、緯度、経度を取得するものである。ＣＰの種類は、交差点を示すＣＰ、仮想ＣＰ、その他のＣＰの区別である。
【００７７】
続くＳ２２０では、検索範囲を設定する。この処理は、対象ＣＰを中心とするリンクの検索範囲を設定するものである。この検索範囲は特に、図１３（ａ）に破線で示すように、その境界が垂直又は水平の線分で構成される多角形として設定される。本実施例では、正方形と当該正方形の一辺よりも長い十字形状とを合成したような範囲として設定されている。
【００７８】
次のＳ２３０では、検索範囲にあるパーセルを取得する。この処理は、ノード及びリンクがパーセル単位で管理されているため、リンク列の選定を行うにあたり、検索範囲に係るパーセルを全て取得するものである。例えば図１３（ｂ）に示すように、検索範囲に応じて３つのパーセルＰ１，Ｐ２，Ｐ３が取得されるという具合である。
【００７９】
続くＳ２４０では、リンク列選定処理を実行する。このリンク列選定処理では、非形状系の属性により、リンクがリンク列単位で検索される。なお、「リンク列」とは、高速道路、一般道路などの道路区分が同一となっている一連のリンク群である。ここでは、Ｓ２３０にて取得されたパーセルに一部が含まれるリンク列が検索対象となる。つまり、この段階では、検索範囲にあるかの判定をせず、最初に属性でリンク列を絞り込むのである。
＜５．１ リンク列選定処理＞
ここで、リンク列選定処理について詳細に説明する。リンク列選定処理の一例を図１４に示す。このリンク列選定処理では、非形状系の属性である属性ＦＣ、属性ＦＷ、属性ＲＤにより、リンク列単位での抽出が行われる。
【００８０】
最初のＳ２４１では、属性ＦＣが一致するリンク列に絞り込む。属性ＦＣは、上述したように道路区分を示す属性である（図５参照）。ここでは、リンク列を構成するリンクに付与されている道路区分と対象ＣＰの属性ＦＣとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で道路区分が変わることがある。したがって、リンク列を構成する全てのリンクの道路区分が属性ＦＣに一致する場合に、当該リンク列を候補リンク列とする。
【００８１】
次のＳ２４２では、属性ＦＷが一致するリンク列に絞り込む。属性ＦＷは、上述したように、物理道路タイプを示す属性である（図６参照）。ここでは、リンク列を構成するリンクに付与されている物理道路タイプと対象ＣＰの属性ＦＷとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で物理道路タイプが変わることがある。したがって、リンク列を構成する全てのリンクの物理道路タイプが属性ＦＷに一致する場合に、当該リンク列を候補リンク列とする。
【００８２】
続くＳ２４３では、属性ＲＤが一致するリンク列に絞り込む。属性ＲＤは、上述したように、道路番号又は道路名称を示す属性である（図４参照）。ここでは、属性ＲＤが道路番号を示す場合に限り、道路番号による一致を判断する。すなわち、リンク列を構成するリンクに付与されている道路番号と対象ＣＰの属性ＲＤとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で道路番号が変わることがある。したがって、リンク列を構成する全てのリンクの道路番号が属性ＲＤに一致する場合に、当該リンク列を候補リンク列とする。
【００８３】
このようなリンク列選定処理により、非形状系属性で絞り込まれたリンク列が候補リンク列として残ることになる。
＜５．２ リンクの抽出＞
図１２のＳ２５０では、対象ＣＰを中心とする検索範囲に一部が含まれるリンクを抽出する。Ｓ２４０のリンク列選定にてリンク列が選定されるため、ここでは、選定されたリンク列を構成するリンクのうち検索範囲に一部が含まれるリンクを抽出する。
【００８４】
ここで「検索範囲に一部が含まれるリンク」について説明する。以下では特に、ノードが交差点に対して通常付与されること、ノードがパーセルの境界に付与されること、必要に応じてノード間に形状補間点が設定されること、を前提として説明を続ける。
＜５．２．１ 対象ＣＰが交差点の場合＞
対象ＣＰが交差点を示す場合は、ノードを意識した処理を行う。すなわち、対象ＣＰが交差点を示す場合は、対象ＣＰがノードと対応付けられるためである。したがって、この場合、リンクを構成する２つのノードのうちのいずれかが検索範囲に含まれているリンクを「検索範囲に一部が含まれるリンク」とする。
【００８５】
例えば図１５（ａ）に示す対象ＣＰが交差点を示すものとする。この場合、検索範囲に含まれるノードＡ，Ｂ，Ｃは、対象ＣＰと対応付けられる。そのため、ノードＡ，Ｂ，Ｃが端点の一方となっているリンクＬ１，Ｌ２，Ｌ３，Ｌ４，Ｌ５が「検索範囲に一部が含まれるリンク」となる。
【００８６】
ただし、地図データは、その縮尺に応じたレベル（以下「パーセルレベル」という）を有している。このパーセルレベルは、ユーザによる縮尺の切り替えによって切り替わるため、リンクの抽出は、全てのパーセルレベルで行われる。パーセルレベルは、下位レベルから順に、ＬＶ０→ＬＶ２→ＬＶ４→ＬＶ６→ＬＶ８→ＬＶ１０などとして設定される。そして、上位レベルになるほど、交差点や道路が間引かれる。
【００８７】
ＣＰは、最も下位のパーセルレベルであるＬＶ０に相当するデータとなっている。したがって、ＬＶ２よりも上位のパーセルレベルでは、必ずしも交差点に対応するノードが存在するとは限らない。そこで、ＬＶ２よりも上位のパーセルレベルでの抽出処理では、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。「一定条件を満たす場合」については、後述する。
＜５．２．２ 対象ＣＰが仮想ＣＰである場合＞
対象ＣＰが仮想ＣＰである場合も、ノードを意識した処理を行う。地図データの仕様では、パーセル境界には必ずノードが設定される。したがって、対象ＣＰが仮想ＣＰである場合、当該仮想ＣＰは、パーセル境界に付与されるものであるため、同一のパーセル境界に存在するノードがあれば、そのノードと対応付けられる。
【００８８】
そこで、リンクを構成するノードのいずれかがパーセル境界に存在する場合、このパーセル境界に存在するノードが検索範囲に含まれるときは、そのリンクを「検索範囲に一部が含まれるリンク」とする。
【００８９】
例えば、図１５（ｂ）に示す対象ＣＰが仮想ＣＰを示すものとし、ノードＤがパーセル境界に存在するノードだとすると、ノードＤを端点とするリンクＬ６，Ｌ８が「検索範囲に一部が含まれるリンク」となる。
＜５．２．３ 対象ＣＰが交差点でも仮想ＣＰでもない場合＞
この場合、対象ＣＰがノードと対応付けられるか否かは分からないため、ノードを意識することなく、リンクの抽出を行う。つまり、対象ＣＰが交差点でも仮想ＣＰでもない場合は、リンクを構成する少なくともいずれかのノードが検索範囲に含まれている場合の他に、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。この場合のリンクの抽出は、全てのパーセルレベルで同様に行われる。
＜５．２．４ 一定条件を満たす場合＞
「一定条件を満たす場合」とは、次の２つの場合をいう。一つは、ノード間に形状補間点が設定されている場合、当該形状補間点を結んだ線分の一部が検索範囲に含まれている場合である。例えば図１５（ｃ）に示すリンクＬ９は、その形状補間点（小さな黒丸）を結ぶ線分の一部が検索範囲に含まれているため、ノードＥ，Ｆが検索範囲に含まれていないが「検索範囲に一部が含まれるリンク」となる。一方、リンクＬ１０は、その形状補間点を結ぶ線分の一部が検索範囲に含まれていないため、「検索範囲に一部が含まれるリンク」にならない。もう一つは、ノード間に形状補間点が設定されていない場合、２つのノードを結ぶ線分の一部が検索範囲に含まれている場合である。例えば、図１５（ｄ）に示すリンクＬ１１は、２つのノードＧ，Ｈを結ぶ線分の一部が検索範囲に含まれているため、「検索範囲に一部が含まれるリンク」となる。
＜５．２．５ その他＞
図１２の説明に戻り、続くＳ２６０では、検索範囲に一部が含まれるリンクのうちで属性ＲＤが一致するリンクに絞り込む。属性ＲＤが道路番号を示す場合は図１４中のＳ２４３にて判断するため、ここでは属性ＲＤが道路名称である場合に、当該道路名称による一致を判断する。なお、道路名称は最大５文字となっているため、属性ＲＤの値としての文字列がリンクに付与される道路名称に含まれるか否かを判断する。
【００９０】
次のＳ２７０では、リンクの数が「１０」本以内に収まるように絞り込む。具体的には、Ｓ２６０までの絞り込みによってリンクの数が「１０」本を越えている場合、対象ＣＰに近いものから順に「１０」本のリンクを選択する。対象ＣＰに近いか否かは、対象ＣＰから各リンクへ例えば垂線を下ろすなどして距離を求めることによって判断する。
＜５．３ 候補選定処理＞
次に、図３中のＳ３００の候補選定処理について説明する。候補選定処理は、リンク、ノード単位の候補選定を行うものである。候補選定処理の一例を図１６に示した。
【００９１】
最初のＳ３１０では、非形状系属性の一致判定を行う。詳細については後述するが、ここでは、Ｓ２００で抽出されたリンク又は当該リンクを構成するノードに対し、属性ＦＣ、属性ＦＷ、属性ＩＴ、属性ＲＤＩ、属性ＤＤ及び属性ＡＦＲを用いた一致判定を行う。なお、属性ＦＣ及び属性ＦＷは、リンク列を絞り込む際に利用しているため（図１４中のＳ２４１，Ｓ２４２）重複した処理となっているが、確実をきすために再度行うものである。また、ここでの一致判定は、確実を期すため、属性ＩＴ、属性ＲＤＩ、属性ＤＤ及び属性ＡＦＲなどを用いた細かい一致判定となっている。
【００９２】
続くＳ３２０では、形状系属性の一致判定を行う。詳細については後述するが、ここでは、図３中のＳ２００で抽出されたリンク又は当該リンクを構成するノードに対し、属性ＢＲ、属性ＰＣＩ、属性ＣＡ及び属性ＤＣＡを用いた一致判定を行う。
【００９３】
次のＳ３３０では、非形状系属性での判定結果を基に候補となるリンクを絞り込む。具体的には、Ｓ３１０での非形状系属性による一致判定の結果、各属性との一致数が多いリンクを、候補リンクとする。
【００９４】
続くＳ３３０では、形状系属性での判定結果で候補となるリンクを絞り込む。具体的には、Ｓ３２０での形状系属性による一致判定の結果、各属性との一致数が多いリンクを、候補リンクとする。
＜５．３．１ 非形状系属性の一致判定＞
ここで、Ｓ３１０の非形状系属性の一致判定の詳細を説明する。非形状系属性の一致判定の一例を図１７に示す。
【００９５】
最初のＳ３１１では、属性ＦＣでの一致判定を行う。属性ＦＣは、上述したように道路区分を示す属性である（図５参照）。ここでは、判定対象のリンクに付与されている道路区分と対象ＣＰの属性ＦＣとの一致を判定する。
【００９６】
続くＳ３１２では、属性ＦＷでの一致判定を行う。属性ＦＷは、上述したように、物理道路タイプを示す属性である（図６参照）。ここでは、判定対象のリンクに付与されている物理道路タイプと対象ＣＰの属性ＦＷとの一致を判定する。
【００９７】
次のＳ３１３では、属性ＩＴでの一致判定を行う。属性ＩＴは、上述したように、交差点の分類を示す属性である（図７参照）。したがって、対象ＣＰが交差点を示すものである場合にのみ、この一致判定が行われる。
【００９８】
なお、属性ＩＴに相当する属性は、ノード及びリンクの少なくともいずれか一方が有している。そこで、ノードが交差点の分類を示す交差点分類情報を持っている場合、対象ＣＰに対応するノードの交差点分類情報と対象ＣＰの属性ＩＴとの一致を判定する。また、リンクが交差点の分類を示す交差点分類情報を持っている場合、対象ＣＰに対応するノードに接続するリンクの交差点分類情報と対象ＣＰの属性ＩＴとの一致を判定する。後者では、２つのノードの交差点分類情報をリンクが持っていることがあるため、いずれかの交差点分類情報と属性ＩＴとの一致を判定する。
【００９９】
続くＳ３１４では、属性ＲＤＩでの一致判定を行う。属性ＲＤＩは、上述したように、交差点の名称を示すものである（図４参照）。したがって、対象ＣＰが交差点を示すものである場合にのみ、この一致判定が行われる。ここでは、対象ＣＰに対応するノードの交差点名称と対象ＣＰの属性ＲＤＩとの一致を判定する。なお、この判定は、属性ＲＤＩの値である文字列がノードの交差点名称に含まれるか否かで行われる。
【０１００】
次のＳ３１５では、属性ＤＤ及び属性ＡＦＲでの一致判定を行う。属性ＤＤは許可された合法の運転方向を示すものであり、属性ＡＦＲは、属性ＤＤが参照可能であるか否かを示すフラグである（図４参照）。ここでは、判定対象のリンクの属性（一方通行コード）と対象ＣＰの属性ＤＤとを比較して判定する。なお、属性ＡＦＲが「１」としてセットされており属性ＤＤが有効である場合であって属性ＤＤが「０」（未定義）でない場合を除いて、判定を行う。ところで、属性ＤＤが示すのはある交通情報に対する道路の通行可能方向であり、リンクの有する一方通行コードとの比較では、両者の順逆方向までは判断できない。したがって、ここでは通行方向の一致を判断するわけではなく、片側通行の道路か両側通行の道路かを判定することにとどまる。
＜５．３．２ 形状系属性の一致判定＞
続けて、Ｓ３２０の形状系属性の一致判定の詳細を説明する。形状系属性の一致判定の一例を図１８に示す。
【０１０１】
最初のＳ３２１では、属性ＢＲでの一致判定を行う。属性ＢＲは、上述したように、次のＣＰへの位置的な角度を示すものである（図４参照）。一方、リンクは、法定上の走行方向を属性として有している。そこで、ここでは、リンクの走行方向が対象ＣＰの属性ＢＲに基づく方向と大きく異なっている場合に、不一致の判定を行う。例えば、リンクの走行方向を示すベクトルと、次のＣＰへ向かう属性ＢＲに基づくベクトルとのなす角度が所定角度（例えば９０度）以上となる場合に、不一致と判定することが考えられる。なお、リンクが双方向に走行可能となっている場合、走行方向を示す２つのベクトルで判定する。
【０１０２】
例えば、図１９（ａ）では、リンクＬ１，Ｌ２，Ｌ３の走行方向を示すベクトルＶＬ１，ＶＬ２１，ＶＬ２２，ＶＬ３と属性ＢＲに基づくベクトルＶＢとのなす角度で判定を行うという具合である。ここでは両ベクトルのなす角度が９０度以上となる場合に、不一致と判定するものとする。なお、リンクＬ２は、双方向に走行可能となっており、走行方向を示す２つのベクトルＶＬ２１，ＶＬ２２で判定される。
【０１０３】
ここでベクトルＶＢとベクトルＶＬ１とのなす角度は、１８０度に近いものとなっており、９０度以上であるため、リンクＬ１は、「不一致」と判定される。また、ベクトルＶＬ２２とベクトルＶＢとがなす角度は９０度以上となるが、ベクトルＶＬ２１とベクトルＶＢとがなす角度が９０度よりも小さいため、リンクＬ２は「一致」と判定される。さらにまた、ベクトルＶＬ３とベクトルＶＢとがなす角度は９０度よりも小さいため、リンクＬ３は「一致」と判定される。
【０１０４】
つまり、９０度以上となる場合を不一致とする場合は、図１９（ｂ）に示すように、属性ＢＲに基づくベクトルＶＢに対し、リンクの走行方向がベクトルＶ１，Ｖ２で示される場合には「一致」と判定され、ベクトルＶ３，Ｖ４で示される場合には「不一致」と判定される。
【０１０５】
図１８中のＳ３２２では、属性ＰＣＩでの一致判定を行う。属性ＰＣＩは、上述したように、同一方向において複数の車道が存在する場合、いずれの車道が選択されているかを示すものである（図４参照）。
【０１０６】
属性ＰＣＩには、車道数及びその車道の中のいずれの車道かを示すシーケンス番号が含まれる。ただし、この属性で一致を判定しようとする場合、並走するリンクを残らず特定する必要がある。
【０１０７】
そこで、図２０に示すように、最初のＳ３２３では、対象ＣＰを中心とした検索エリアを設定する。この検索エリアは、対象ＣＰを中心とした円の内部とすることが考えられる。例えば、所定距離（例えば１５０ｍ）を半径とする円の内部を検索エリアにするという具合である。なお、ＰＣＩ属性の一つとして検索エリアのデフォルト値が設定されることがあるため、その場合は、デフォルト値に所定距離（例えば１５０ｍ）を加えた値を半径とする円の内部を検索エリアとすることが考えられる。
【０１０８】
続くＳ３２４では、検索エリア内のリンクを抽出する。ここでは、属性ＰＣＩの一つにインジケータタイプがあるため、このインジケータタイプに基づき、緯度方向あるいは経度方向の仮想直線を引き、この仮想直線と交差するリンクを抽出する。
【０１０９】
次のＳ３２５では、抽出したリンクの数と車道数とが一致するか否かを判断する。ここで車道数が一致すると判断された場合（Ｓ３２５：ＹＥＳ）、Ｓ３２６にてシーケンス番号でリンクを特定し、当該リンクが判定対象のリンクと一致するか否かを判定して、属性ＰＣＩでの一致判定を終了する。一方、車道数が一致しないと判断された場合、Ｓ３２６の処理を実行せず、属性ＰＣＩでの一致判定を終了する。これは、車道数が一致しない場合、誤判定となる虞があるからである。
【０１１０】
図１８に戻り、Ｓ３２７では、属性ＣＡ及び属性ＤＣＡでの一致判定を行う。属性ＣＡは脇道に対する角度を示すものであり、属性ＤＣＡは脇道に対する接続距離を示すものである（図４参照）。ここでは、最初に、脇道の方向を検出する。具体的には、図２１（ａ）に示すように、属性ＣＡが負値である場合、次のＣＰへ向かう方向（属性ＢＲに基づく方向）に対し、左側に脇道があると判断する。一方、図２１（ｂ）に示すように、属性ＣＡが正値である場合、次のＣＰへ向かう方向（属性ＢＲに基づく方向）に対し、右側に脇道があると判断する。なお、属性ＣＡが「０」である場合、脇道の方向が特定できないため、一致判定を行わない。次に、判定対象のリンクとそのリンクの脇道との位置関係から属性ＣＡ及び属性ＤＣＡでの一致判定を行う。
【０１１１】
以上説明してきたＳ３００の候補選定処理によって、各ＣＰに対し、その周辺に、候補となるリンクが選定される。これらのリンクを繋ぐリンク、すなわちＣＰ間を繋ぐリンクを推定する処理が、図３中の道路マッチング処理（Ｓ４００）である。
＜５．４ 道路マッチング処理＞
次に、Ｓ４００の道路マッチング処理について説明する。道路マッチング処理の一例を図２２に示す。道路マッチング処理では、２つのＣＰを対象ＣＰとし、始端側に位置するＣＰを始端側ＣＰ、終端側に位置するＣＰを終端側ＣＰとして処理を行う。
＜５．４．１ 道路探索＞
最初のＳ４１０では、始端候補リンクから終端候補リンクを繋ぐ道路を探索する。始端候補リンクは、始端側ＣＰに対し抽出されたリンクである。また、終端候補リンクは、終端側ＣＰに対し抽出されたリンクである。ここでは、始端候補リンクと終端候補リンクとを結ぶ全ての道路を探索する。例えば、図２３に示すように、始端側ＣＰをＣＰ（ａ）とし、終端側ＣＰをＣＰ（ｂ）とし、ＣＰ（ａ）に対し抽出されたリンクをＳＬとし、ＣＰ（ｂ）に対し抽出されたリンクをＧＬとする。このとき、始端候補リンクＳＬと終端候補リンクＧＬとの間の道路を探索する場合、リンクＳＬを構成する２つのノードＳＮ１，ＳＮ２とリンクＧＬを構成する２つのノードＧＮ１，ＧＮ２との全ての組み合わせを考える。具体的には、ＳＮ１→ＧＮ１、ＳＮ１→ＧＮ２、ＳＮ２→ＧＮ１、ＳＮ２→ＧＮ２を結ぶ道路を探索する。
【０１１２】
次のＳ４２０では、道路単位候補選定を実行する。この処理は、各種の形状系属性を基に、Ｓ４１０にて探索された道路のうちで候補となる道路を判定するものである。続くＳ４３０では、Ｓ４２０における判定結果に基づき、道路を絞り込む。
【０１１３】
次のＳ４４０では、道路が一意に決定されたか否かを判断する。ここで道路が一意に決定された場合（Ｓ４４０でＹＥＳ）、Ｓ４５０にてマッチング結果を出力し、その後、道路マッチング処理を終了する。一方、道路が一意に決定されない場合（Ｓ４４０でＮＯ）、Ｓ４５０の処理を実行せず、道路マッチング処理を終了する。
＜５．４．２ 道路探索の省略＞
なお、このような道路マッチング処理（Ｓ４１０〜Ｓ４４０）がペアとなる２つの対象ＣＰに対して繰り返されるのであるが、上述のＳ４１０では、先の道路マッチング処理の結果を用いて探索する道路を省略する場合がある。
【０１１４】
例えば、図２３（ｂ）に示すように、ＣＰ（ａ）−ＣＰ（ｂ）間の道路マッチング処理の結果、リンクＳＬ→ＣＬ→ＧＬ１という道路が一意に決定されたものとする。このときは、ＣＰ（ｂ）から次のＣＰへの道路マッチング処理を行う場合、リンクＧＬ１からの道路を探索する。すなわち、候補リンクにリンクＧＬ２があっても、リンクＧＬ２からの道路探索を省略する。
【０１１５】
また、ＣＰの種類によっても、道路探索を省略する。
ＣＰ（ｂ）が交差点である場合、例えば図２３（ｃ）に示すように、交差点を示すノードＧＮ２と対応するため、リンクＧＬについては、一方のノードＧＮ１に接続される道路を探索する。すなわち、ＳＮ１→ＧＮ１、ＳＮ２→ＧＮ１を結ぶ道路を探索する。
【０１１６】
ＣＰ（ｂ）が仮想ＣＰである場合、例えば図２３（ｄ）に示すノードＧＮ２が対象パーセルの境界に位置するノードであれば、このノードが道路の始端又は終端となる。そこで、この場合も、リンクＧＬについては、一方のノードＧＮ１に接続される道路を探索する。すなわち、ＳＮ１→ＧＮ１、ＳＮ２→ＧＮ１を結ぶ道路を探索する。
【０１１７】
さらにまた、一度探索した道路を再び探索しないようにして道路探索に要する時間を短縮することが考えられる。
例えば図２４（ａ）に実線で示すノードＮ１→Ｎ２→Ｎ３→Ｎ４という探索を最初に行ったものとする。このとき、ノードＮ１からの道路探索を２度目に行う場合、ノードＮ１→Ｎ５→Ｎ２という道路探索は行うが、ノードＮ２から先の探索は既に行っているため、ノードＮ２から先の探索は行わない。
【０１１８】
また、ノードからリンクが分岐する場合、リンクに優先順位をつけて道路探索を行う。例えば、あるノードから道路探索を行う場合、対象ＣＰを結ぶ方向を基準にして、ノードに接続されるリンクの基準方向からの角度を求め、所定角度以内にあるリンクのみを道路探索の対象とする。図２４（ｂ）では、ノードＮ１からの道路探索を行うのであるが、ＣＰ（ａ）からＣＰ（ｂ）へ向かう方向を基準にして、ノードＮ１に接続されるリンクＬ１，Ｌ２，Ｌ３の基準方向からの角度ａ１，ａ２，ａ３を求める。ここで角度ａ１，ａ２が所定角度以内にあるとすると、リンクＬ１，Ｌ２を道路探索の対象とする。一方、角度ａ３が所定角度を越えている場合、リンクＬ３を道路探索の対象から外す。
【０１１９】
さらにまた、ノードからの探索を行う場合、そのノードまでのリンクの道路種別と同じ道路種別のリンクを道路探索の対象とする。例えば図２４（ｃ）では、ＣＰ（ｂ）からＣＰ（ｃ）への道路を、ノードＮ１から探索する。ここで、ＣＰ（ａ）−ＣＰ（ｂ）間の道路がリンクＬ１として確定されているものとする。このとき、リンクＬ１の道路種別が「国道」であるため、ノードＮ１からの道路探索にあたり、道路種別が「国道」であるリンクＬ２を道路探索の対象にする。道路種別が「県道」であるリンクＬ３は、道路探索の対象から外す。
＜５．４．３ 道路探索の中止＞
ところで、Ｓ４１０における道路探索が所定時間以内に終了するとは限らない。そこで、道路探索を途中で中止するようにしてもよい。
【０１２０】
例えば属性ＰＤを利用することが考えられる。図２５（ａ）では、ＣＰ（ａ）及びＣＰ（ｂ）のいずれもが属性ＰＤを有しているものとする。このとき、ノードＮ１からノードＮ２への道路を探索する際、形状補間点Ｋ１，Ｋ２，Ｋ３，Ｋ４，・・・での累積距離を算出するようにする。そして、この累積距離が、ＰＤ値から一定値以上大きくなった場合、道路探索を中止する。
【０１２１】
また例えば属性ＰＤＭを利用することが考えられる。図２５（ｂ）に示すように、ＣＰ（ａ）−ＣＰ（ｂ）間の直線距離とＰＤＭ値とを用い、破線で示すようなコ字状の距離を算出しておく。このとき、ノードＮ１からノードＮ２への道路を探索する際、形状補間点Ｋ１，Ｋ２，Ｋ３，Ｋ４，・・・での累積距離を算出するようにする。そして、この累積距離が、破線で示される距離よりも一定値以上大きくなった場合に、道路探索を中止する。
【０１２２】
例えば通過するノードの数を利用することが考えられる。図２５（ｃ）に示すように、ノードＮ１からノードＮ２への道路を探索する際、通過するノードＮ３，Ｎ４，Ｎ５，Ｎ６の個数を数えるようにする。そして、ノードの数が一定値以上となった場合に、道路探索を中止する。
【０１２３】
また例えばＣＰが交差点であることを利用することが考えられる。図２５（ｄ）では、ＣＰ（ａ）及びＣＰ（ｂ）のいずれもが交差点であるとする。このとき、ノードＮ１，Ｎ２が交差点であれば、ノードＮ１，Ｎ２がそれぞれＣＰ（ａ），ＣＰ（ｂ）に対応するものとなるため、ノードＮ１，Ｎ２間の直線距離を予め算出しておく。そして、ノードＮ１からノードＮ２への道路を探索する際、通過するノードＮ３，Ｎ４，Ｎ５，Ｎ６までの累積距離を算出して、この累積距離が、予め算出したノードＮ１，Ｎ２間の直線距離よりも一定値以上大きくなった場合、道路探索を中止する。
【０１２４】
ここでは４つの手法を説明したが、いずれの手法によっても、間違っていると思われる道路の探索が途中で打ち切られるため、処理負荷が軽減される。
＜５．４．４ 道路単位候補選定＞
ここで、図２２中の道路単位候補選定について説明する。道路単位候補選定の一例を図２６に示す。道路単位候補選定は、ＣＰ間で抽出された道路の単位で、「ＯＫ」又は「ＮＧ」判定を行うものである。
【０１２５】
最初のＳ４２１では、属性ＣＡ／ＤＣＡで判定する。上述したように、属性ＣＡは脇道に対する角度を示すものであり、属性ＤＣＡは脇道に対する接続距離を示すものである（図４参照）。ここでは、探索された道路の中で、属性ＣＡ及び属性ＤＣＡによって特定されるリンクを、脇道であるとして、このリンクを含む道路に対しＮＧ判定を行うものである。具体的には、図２７（ａ）に示すように、属性ＣＡ及び属性ＤＣＡが示す位置座標の周囲（破線で示す範囲）にリンクがあれば、当該リンクを含む道路を「ＮＧ」と判定する。例えば図２７（ｂ）には、ＣＰ間を繋ぐ道路として道路１及び道路２が示されているが、属性ＣＡ及び属性ＤＣＡから脇道と判定されたリンクを含む道路１は「ＮＧ」と判定されることになる。
【０１２６】
図２６中のＳ４２２では、属性ＢＲ／ＤＭＢで判定する。上述したように、属性ＢＲは次のＣＰへの角度を示すものであり、属性ＤＭＢは次のＣＰまでの直線距離を示すものである（図４参照）。ＣＰが示すデータとナビゲーション装置１０の地図データとの間にずれがある場合、この属性ＢＲ／ＤＭＢを利用することで、より確からしい道路を特定することができる。そこで、図２８に示すように、ＣＰ（ｂ）−ＣＰ（ｃ）間の道路の判定を、ＣＰ（ｂ）の一つ前のＣＰ（ａ）の属性ＢＲ及び属性ＤＭＢを用いて行う。具体的には、属性ＢＲ及び属性ＤＭＢから特定される位置座標の周囲（記号Ｈの破線で示す範囲）のリンクＬを含む道路は「ＯＫ」と判定する。なお、ＣＰ（ｂ）−ＣＰ（ｃ）間の道路の判定であるため、リンクＬを構成するノード又は形状補間点が所定範囲に入ることを条件とする。例えば、所定範囲は、ＣＰ（ｂ）とＣＰ（ｃ）とを結ぶ線分と属性ＰＤＭとから設定される矩形（図中に二点鎖線で示した）の内側とすることが考えられる。もちろん、所定範囲は、このような矩形に限られず、ＣＰ（ｂ）及びＣＰ（ｃ）を通る楕円の内側などとしてもよい。
【０１２７】
次のＳ４２３では、属性ＰＤで判定する。上述したように、属性ＰＤは、属性ＰＤを有する次のＣＰまでの運転距離である（図４参照）。したがって、探索された道路の運転距離によって、当該道路が候補となり得るか否かを判定する。
【０１２８】
具体的には、図２９に示すように、ＣＰ（ａ）−ＣＰ（ｂ）間の運転距離を算出する場合、各ＣＰがノードに対応するとは限らないため、ＣＰ（ａ）からリンクＬ１への垂線を下ろし、また、ＣＰ（ｂ）からリンクＬ３への垂線を下ろして、それぞれの交点をＭ，Ｎとする。そして、交点Ｍから交点Ｎまでの運転距離を算出する。
【０１２９】
なお、交点Ｍから直後のノードまでの運転距離は、この運転距離のリンクＬ１における割合を算出することで求める。ここで、交点Ｍから直後のノードまでがリンクＬ１のｍ（％）である場合、リンクＬ１の運転距離に（ｍ／１００）を乗じて、交点Ｍから直後のノードまでの運転距離を算出する。
【０１３０】
同様に、交点Ｎから直前のノードまでの運転距離は、この運転距離のリンクＬ３における割合を算出することで求める。ここで、交点Ｎから直前のノードまでの距離がリンクＬ１の距離のｎ（％）である場合、リンクＬ３の運転距離に（ｎ／１００）を乗じて、交点Ｎから直前のノードまでの運転距離を算出する。
【０１３１】
ところで、全てのＣＰが属性ＰＤを有しているとは限らない。したがって、ＣＰ（ａ）が属性ＰＤを有しているがＣＰ（ｂ）が属性ＰＤを有していない場合、図３０（ａ）に示すように、道路の候補判定は行わず、そのまま道路を保持する。次に、図３０（ｂ）に示すＣＰ（ｃ）が属性ＰＤを有しているとすると、ＣＰ（ａ）−ＣＰ（ｃ）間で属性ＰＤに基づく道路判定を行う。すなわち、道路Ｌ１→Ｌ２→Ｌ３→Ｌ５→Ｌ６→Ｌ１０と、道路Ｌ１→Ｌ４→Ｌ５→Ｌ６→Ｌ１０と、道路Ｌ１→Ｌ２→Ｌ３→Ｌ５→Ｌ７→Ｌ８→Ｌ９→Ｌ１０と、道路Ｌ１→Ｌ４→Ｌ５→Ｌ７→Ｌ８→Ｌ９→Ｌ１０と、を候補にして、ＮＧ判定を行う。これにより、図３０（ｃ）に示すように道路Ｌ１→Ｌ２→Ｌ３→Ｌ５→Ｌ６→Ｌ１０という道路が残った場合、ＣＰ（ａ）−ＣＰ（ｂ）間の道路Ｌ４、及び、ＣＰ（ｂ）−ＣＰ（ｃ）間の道路Ｌ７→Ｌ８→Ｌ９は、「ＮＧ」と判定されることになる。
【０１３２】
続くＳ４２４では、属性ＰＤＭで判定する。上述したように、属性ＰＤＭは、次のＣＰまでを結ぶ直線からの道路の離間距離を示す（図４参照）。この処理では、属性ＰＤＭに基づき道なりの運転距離を求め、探索された道路が候補となるか否かを判定する。
【０１３３】
具体的には、属性ＰＤＭに基づく道なりの運転距離を次の式により算出する。
ＰＤＭ運転距離＝ＣＰ間の直線距離を直径とする円周の半分×補正値・・・式５
ここで補正値は、属性ＰＤＭの値とＣＰ間の直線距離の半分との比率からテーブルによって確定する。例えば、図３１（ａ）に示すようにＣＰ（ａ）−ＣＰ（ｂ）間の直線距離の半分をｒとすると、図３１（ｂ）に示すテーブルによって、属性ＰＤＭの値と距離ｒとの比率（ＰＤＭ／ｒ）から補正値を求める。なお、図３１（ｂ）に示したテーブルは、一部を抜粋したものである。
【０１３４】
そして、候補となっている道路の道なりの運転距離を道路運転距離とすると、道路運転距離が次の式を満たす場合に、その道路を「ＯＫ」と判定する。
ＰＤＭ運転距離×０．５＜道路運転距離＜ＰＤＭ運転距離×１．５・・・式６
＜５．４．５ マッチング結果の出力＞
そして、上述したように、これらの判定結果によって道路を絞り込み（図２２中のＳ４３０）、道路が一意に決定されると（Ｓ４４０でＹＥＳ）、Ｓ４５０にてマッチング結果を出力する。マッチング結果は、一意に特定された道路を構成する全リンクのリンクＩＤ、始点オフセット距離、終点オフセット距離などで構成される。なお、始点オフセット距離は、道路の始点となるリンクのどの位置からがマッチングの開始位置かを示す距離である。同様に、終点オフセット距離は、道路の終点となるリンクのどの位置までがマッチングの終了位置かを示す距離である。
＜５．４．６ 道路の決定について＞
なお、通常、道路が一意に決定されないと（Ｓ４４０でＮＯ）、道路マッチング失敗となって、マッチング結果が出力されないことになる。ただし、次のような場合には、道路が一意に決定されたものとする。
【０１３５】
例えば、図３２（ａ）では、ＣＰ（ａ）からＣＰ（ｂ）への道路を探索した結果、ノードＮ１→Ｎ４→Ｎ５→Ｎ２→Ｎ３という道路、及び、ノードＮ１→Ｎ４→Ｎ５→Ｎ２という道路の２つが残ったものとする。このとき、太線で示した道路（ノードＮ１→Ｎ４→Ｎ５→Ｎ２）は、両方の道路に包含されているため、この道路を一意に決定された道路とする。
【０１３６】
また例えば、図３２（ｂ）では、ＣＰ（ａ）からＣＰ（ｂ）への道路を探索した結果、ノードＮ１→Ｎ４→Ｎ５→Ｎ２→Ｎ３という道路、及び、ノードＮ１→Ｎ４→Ｎ６→Ｎ５→Ｎ２→Ｎ３という道路の２つが残ったものとする。このとき、太線で示した道路（ノードＮ１→Ｎ４,Ｎ５→Ｎ２→Ｎ３）は、両方の道路に包含されているため、この分断された２つの道路を一意に決定された道路とする。
【０１３７】
あるいは、図３２（ｂ）に示すような例で、道なりの道路を一意に決定された道路とすることが考えられる。「道なり」とは、図３２（ｃ）に示すように、リンク同士のなす角度（例えば記号ａで示す角度）が所定角度（例えば１５度）以下である場合をいう。
＜６．効果＞
以上詳述したように、本実施例では、図１２に示した候補リンク検索処理において、検索範囲を決定し（Ｓ２２０）、ＣＰを中心とする検索範囲のリンクを抽出する（Ｓ２５０）。つまり、ＣＰで示される道路を推定するにあたり、ＣＰ周辺のリンクを抽出するのであるが、このときＣＰを基準とする検索範囲を設定することにより、妥当な距離にあるリンクを抽出するのである。これにより、ＣＰに対応する適切なリンクを抽出できる可能性が高くなり、ＴＰＥＧデータに含まれる位置情報から、車載機側に用意される地図データ上での道路を適切に推定することができる。
【０１３８】
また、本実施例では、検索範囲が、図１３（ａ）に破線で示したように、その境界が垂直又は水平の線分で構成される多角形として設定される。本実施例では、正方形と当該正方形の一辺よりも長い十字形状とを合成したような範囲として設定されている。これにより、ＣＰから妥当な距離にあるリンクを抽出でき、しかも、境界などの算出処理が煩雑にならず、検索範囲に含まれるか否かの判断が容易になる。
【０１３９】
さらにまた、本実施例では、検索範囲のリンクを抽出する際（図１２中のＳ２５０）、対象ＣＰが交差点である場合は、交差点を示すノードにＣＰが対応付けられる可能性が高いため、リンクを構成する２つのノードのうちのいずれかが検索範囲に含まれているリンクを抽出する（図１５（ａ）参照）。また、対象ＣＰが仮想ＣＰである場合、パーセル境界には必ずノードが設定されるため、パーセル境界に存在するノードが検索範囲に含まれるときは、そのリンクを抽出する（図１５（ｂ）参照）。さらにまた、対象ＣＰが交差点でも仮想ＣＰでもない場合は、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。なお、対象ＣＰが交差点である場合は必ずしもノードに対応付けられるとは限らないため、このときも、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。一定条件を満たす場合とは、形状補間点を結んだ線分の一部が検索範囲に含まれている場合（図１５（ｃ）参照）、及び、２つのノードを結ぶ線分の一部が検索範囲に含まれている場合である（図１５（ｄ）参照）。このように、ＣＰとノードとの対応関係の有無によってリンクの抽出方法を異ならせるため、妥当なリンクを抽出できる可能性が高くなる。
【０１４０】
また、本実施例では、検索範囲に一部が含まれるリンクのうちで属性ＲＤが一致するリンクに絞り込む（図１２中のＳ２６０）。さらにまた、ＣＰからリンクまでの距離に基づいて、リンクの数が「１０」本以内に収まるように絞り込む（Ｓ２７０）。これにより、抽出されるリンクを適切に絞り込むことができ、妥当なリンクを抽出できる可能性が高くなる。
【０１４１】
さらにまた、本実施例では、検索範囲が決定された後（図１２中のＳ２２０）、リンクの抽出（Ｓ２５０）に先立って、検索範囲のパーセルを取得し（Ｓ２３０）、このパーセル単位でリンク列を選定する（Ｓ２４０）。このように最初にリンク列を選定するため、リンク単位の抽出処理を減らすことができ、抽出処理に要する時間を短縮することができる。また、検索範囲によらずパーセル単位でリンク列を選定するため、リンクの抽出に先立つリンク列の選定を迅速に行うことができる。しかも、リンク列の選定では、非形状系の属性である属性ＦＣ、属性ＦＷ、及び、属性ＲＤでの絞り込みを行う（図１４中のＳ２４１〜Ｓ２４３）。つまり、リンク列を選定するにあたり、検索範囲に含まれるか否かを判断するよりも先に、コアポイントの非形状系の属性によってリンク列を絞り込むのである。これにより、リンクの抽出に先立つリンク列の選定をより一層迅速に行うことができる。
【０１４２】
なお、本実施例におけるナビゲーション装置１０が「道路推定装置」に相当し、地図データ入力装置１３が「地図データ入力手段」に相当し、制御回路１７のＣＰＵ１７ａが「検索範囲設定手段」、「リンク抽出手段」、「リンク列選定手段」及び「パーセル取得手段」に相当する。
【０１４３】
そして、図１２中のＳ２２０の処理が「検索範囲設定手段」の機能としての処理に相当し、Ｓ２５０〜Ｓ２７０の処理が「リンク抽出手段」の機能としての処理に相当し、Ｓ２４０の処理（図１４中のＳ２４１〜Ｓ２４３）が「リンク列選定手段」の機能としての処理に相当し、Ｓ２３０の処理が「パーセル取得手段」の機能としての処理に相当する。
【０１４４】
以上、本発明は、上述した実施例に何ら限定されるものではなく、その要旨を逸脱しない範囲において種々なる形態で実施することができる。
（イ）上記実施形態では、検索範囲として図１３（ａ）に示した多角形を採用している。これに対し、処理負荷などを考えないのであれば、例えばＣＰを中心とする円を検索範囲として設定することも考えられる。また、処理負荷を考えてその境界が垂直又は水平の線分で構成される多角形として検索範囲を設定する場合、例えば図１３（ａ）に示したものよりも境界を構成する線分の多い多角形を採用してもよい。また、単純な正方形や長方形を採用してもよい。
【０１４５】
（ロ）上記実施形態では、図１４中のＳ２４３でリンク列を絞り込むときに「道路番号」（属性ＲＤ）を用い、図１２中のＳ２６０でリンクを絞り込むときに「道路名称」（属性ＲＤ）を用いているが、道路番号、道路名称のいずれを用いるかは特に限定されるものではない。また、他の属性を用いてリンク列やリンクを絞り込むようにしてもよい。
【符号の説明】
【０１４６】
１０：ナビゲーション装置
１１：受信装置
１２：位置検出装置
１３：地図データ入力装置
１４：操作デバイス
１５：音声出力デバイス
１６：表示デバイス
１７：制御回路
１７ａ：ＣＰＵ
１７ｂ：ＲＯＭ
１７ｃ：ＲＡＭ
２０：センタ
１７１：選局ブロック
１７２：アプリケーションブロック
１７３：ＤＬＲライブラリブロック
１７４：描画ブロック
【特許請求の範囲】
【請求項１】
道路に沿って付与され当該道路を特定するための属性を有するコアポイントのデータを外部から受信し、当該コアポイントが示す前記道路に該当する地図上のリンクを抽出することで前記道路を推定する道路推定装置であって、
前記コアポイントの有する属性に応じた属性を有するリンクで構成される地図データを入力する地図データ入力手段と、
前記コアポイントを基準にして検索範囲を設定する検索範囲設定手段と、
前記地図データ入力手段にて入力された地図データを構成するリンクのうちで、前記検索範囲に含まれるリンクを抽出するリンク抽出手段と、を備え、
前記リンク抽出手段にて抽出されたリンクの有する属性と前記コアポイントの有する属性とに基づき、前記コアポイントの示す前記道路を推定すること
を特徴とする道路推定装置。
【請求項２】
請求項１に記載の道路推定装置において、
前記リンク抽出手段は、前記地図データを構成するリンクのうちで、前記検索範囲に少なくとも一部が含まれるリンクを抽出すること
を特徴とする道路推定装置。
【請求項３】
請求項１又は２に記載の道路推定装置において、
前記検索範囲に基づき、前記地図データ入力手段にて入力された地図データのリンクの配列であるリンク列を選定するリンク列選定手段を備えおり、
前記リンク抽出手段は、前記リンク列選定手段にて選定されたリンク列を構成するリンクの中から前記検索範囲に含まれるリンクを抽出すること
を特徴とする道路推定装置。
【請求項４】
請求項３に記載の道路推定装置において、
前記地図データ入力手段は、地図データを複数エリアに分割した分割領域の単位で前記地図データを入力し、
前記検索範囲に少なくとも一部が含まれる分割領域である検索対象分割領域を特定する分割領域特定手段を備え、
前記リンク列選定手段は、前記分割領域特定手段にて特定された前記検索対象分割領域に少なくとも一部が含まれるリンク列を選定すること
を特徴とする道路推定装置。
【請求項５】
請求項４に記載の道路推定装置において、
前記リンク列選定手段は、前記検索対象分割領域に一部が含まれるリンク列から、前記コアポイントの有する非形状系の属性である道路のクラスを示す道路区分（属性ＦＣ）、道路の種別を示す物理道路タイプ（属性ＦＷ）、及び、道路番号又は道路名称を示す道路固有情報（属性ＲＤ）の少なくともいずれかが一致するリンク列に絞り込むこと
を特徴とする道路推定装置。
【請求項６】
請求項５に記載の道路推定装置において、
前記リンク列選定手段は、前記検索範囲に含まれるか否かの判断に先立って、前記コアポイントの有する非形状系の属性によってリンク列を絞り込むこと
を特徴とする道路推定装置。
【請求項７】
請求項１〜６の何れか一項に記載の道路推定装置において、
前記検索範囲設定手段は、その境界が垂直又は水平の線分で構成される多角形を前記検索範囲として設定すること
を特徴とする道路推定装置。
【請求項８】
請求項１〜７の何れか一項に記載の道路推定装置において、
前記リンク抽出手段は、前記コアポイントが道路の交差点を示すものである場合、交差点を端点とするリンクであって、当該端点が前記検索範囲に含まれるリンクを抽出すること
を特徴とする道路推定装置。
【請求項９】
請求項８に記載の道路推定装置において、
前記リンク抽出手段は、前記コアポイントが道路の交差点を示すものでない場合、前記リンクの端点が前記検索範囲に含まれない場合であっても、リンクの一部が前記検索範囲に含まれていれば当該リンクを抽出すること
を特徴とする道路推定装置。
【請求項１０】
請求項１〜９の何れか一項に記載の道路推定装置において、
前記地図データ入力手段は、地図データを複数エリアに分割した分割領域の単位で、前記分割領域の境界に端点を有するリンクで構成される地図データを入力し、
外部より受信したコアポイントが前記分割領域を跨いで点在する場合、前記地図データ入力手段が入力した地図データにおいて、当該分割領域の境界に新たなコアポイントである仮想コアポイントを生成するように構成されており、
前記リンク抽出手段は、前記コアポイントが前記仮想コアポイントである場合、前記分割領域の境界に端点を有するリンクであって、当該端点が前記検索範囲に含まれるリンクを抽出すること
を特徴とする道路推定装置。
【請求項１１】
請求項１０に記載の道路推定装置において、
前記リンク抽出手段は、前記コアポイントが前記仮想コアポイントでない場合、前記リンクの端点が前記検索範囲に含まれない場合であっても、リンクの一部が前記検索範囲に含まれていれば当該リンクを抽出すること
を特徴とする道路推定装置。
【請求項１２】
請求項１〜１１の何れか一項に記載の道路推定装置において、
前記リンク抽出手段は、前記コアポイントの非形状系の属性である道路番号又は道路名称を示す道路固有情報（属性ＲＤ）に基づき、前記検索範囲に基づいて抽出したリンクを絞り込むこと
を特徴とする道路推定装置。
【請求項１３】
請求項１〜１２の何れか一項に記載の道路推定装置において、
前記リンク抽出手段は、前記コアポイントまでの距離に基づき、前記検索範囲に基づいて抽出したリンクを絞り込むこと
を特徴とする道路推定装置。
【請求項１】
道路に沿って付与され当該道路を特定するための属性を有するコアポイントのデータを外部から受信し、当該コアポイントが示す前記道路に該当する地図上のリンクを抽出することで前記道路を推定する道路推定装置であって、
前記コアポイントの有する属性に応じた属性を有するリンクで構成される地図データを入力する地図データ入力手段と、
前記コアポイントを基準にして検索範囲を設定する検索範囲設定手段と、
前記地図データ入力手段にて入力された地図データを構成するリンクのうちで、前記検索範囲に含まれるリンクを抽出するリンク抽出手段と、を備え、
前記リンク抽出手段にて抽出されたリンクの有する属性と前記コアポイントの有する属性とに基づき、前記コアポイントの示す前記道路を推定すること
を特徴とする道路推定装置。
【請求項２】
請求項１に記載の道路推定装置において、
前記リンク抽出手段は、前記地図データを構成するリンクのうちで、前記検索範囲に少なくとも一部が含まれるリンクを抽出すること
を特徴とする道路推定装置。
【請求項３】
請求項１又は２に記載の道路推定装置において、
前記検索範囲に基づき、前記地図データ入力手段にて入力された地図データのリンクの配列であるリンク列を選定するリンク列選定手段を備えおり、
前記リンク抽出手段は、前記リンク列選定手段にて選定されたリンク列を構成するリンクの中から前記検索範囲に含まれるリンクを抽出すること
を特徴とする道路推定装置。
【請求項４】
請求項３に記載の道路推定装置において、
前記地図データ入力手段は、地図データを複数エリアに分割した分割領域の単位で前記地図データを入力し、
前記検索範囲に少なくとも一部が含まれる分割領域である検索対象分割領域を特定する分割領域特定手段を備え、
前記リンク列選定手段は、前記分割領域特定手段にて特定された前記検索対象分割領域に少なくとも一部が含まれるリンク列を選定すること
を特徴とする道路推定装置。
【請求項５】
請求項４に記載の道路推定装置において、
前記リンク列選定手段は、前記検索対象分割領域に一部が含まれるリンク列から、前記コアポイントの有する非形状系の属性である道路のクラスを示す道路区分（属性ＦＣ）、道路の種別を示す物理道路タイプ（属性ＦＷ）、及び、道路番号又は道路名称を示す道路固有情報（属性ＲＤ）の少なくともいずれかが一致するリンク列に絞り込むこと
を特徴とする道路推定装置。
【請求項６】
請求項５に記載の道路推定装置において、
前記リンク列選定手段は、前記検索範囲に含まれるか否かの判断に先立って、前記コアポイントの有する非形状系の属性によってリンク列を絞り込むこと
を特徴とする道路推定装置。
【請求項７】
請求項１〜６の何れか一項に記載の道路推定装置において、
前記検索範囲設定手段は、その境界が垂直又は水平の線分で構成される多角形を前記検索範囲として設定すること
を特徴とする道路推定装置。
【請求項８】
請求項１〜７の何れか一項に記載の道路推定装置において、
前記リンク抽出手段は、前記コアポイントが道路の交差点を示すものである場合、交差点を端点とするリンクであって、当該端点が前記検索範囲に含まれるリンクを抽出すること
を特徴とする道路推定装置。
【請求項９】
請求項８に記載の道路推定装置において、
前記リンク抽出手段は、前記コアポイントが道路の交差点を示すものでない場合、前記リンクの端点が前記検索範囲に含まれない場合であっても、リンクの一部が前記検索範囲に含まれていれば当該リンクを抽出すること
を特徴とする道路推定装置。
【請求項１０】
請求項１〜９の何れか一項に記載の道路推定装置において、
前記地図データ入力手段は、地図データを複数エリアに分割した分割領域の単位で、前記分割領域の境界に端点を有するリンクで構成される地図データを入力し、
外部より受信したコアポイントが前記分割領域を跨いで点在する場合、前記地図データ入力手段が入力した地図データにおいて、当該分割領域の境界に新たなコアポイントである仮想コアポイントを生成するように構成されており、
前記リンク抽出手段は、前記コアポイントが前記仮想コアポイントである場合、前記分割領域の境界に端点を有するリンクであって、当該端点が前記検索範囲に含まれるリンクを抽出すること
を特徴とする道路推定装置。
【請求項１１】
請求項１０に記載の道路推定装置において、
前記リンク抽出手段は、前記コアポイントが前記仮想コアポイントでない場合、前記リンクの端点が前記検索範囲に含まれない場合であっても、リンクの一部が前記検索範囲に含まれていれば当該リンクを抽出すること
を特徴とする道路推定装置。
【請求項１２】
請求項１〜１１の何れか一項に記載の道路推定装置において、
前記リンク抽出手段は、前記コアポイントの非形状系の属性である道路番号又は道路名称を示す道路固有情報（属性ＲＤ）に基づき、前記検索範囲に基づいて抽出したリンクを絞り込むこと
を特徴とする道路推定装置。
【請求項１３】
請求項１〜１２の何れか一項に記載の道路推定装置において、
前記リンク抽出手段は、前記コアポイントまでの距離に基づき、前記検索範囲に基づいて抽出したリンクを絞り込むこと
を特徴とする道路推定装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【公開番号】特開２０１２−１１２７７３（Ｐ２０１２−１１２７７３Ａ）
【公開日】平成２４年６月１４日（２０１２．６．１４）
【国際特許分類】
【出願番号】特願２０１０−２６１３８７（Ｐ２０１０−２６１３８７）
【出願日】平成２２年１１月２４日（２０１０．１１．２４）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
【公開日】平成２４年６月１４日（２０１２．６．１４）
【国際特許分類】
【出願日】平成２２年１１月２４日（２０１０．１１．２４）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
[ Back to top ]