道路推定装置
【課題】配信されるコアポイントの情報から、地図データの分割領域においてコアポイントが示す道路に該当するリンクを適切に推定可能な道路推定装置を提供する。
【解決手段】パーセル境界に仮想ＣＰを付与する（Ｓ１１０）。つまり、地図データがパーセルの単位で入力されパーセル境界にノードが設定されることに鑑み、パーセル境界上に、新たなＣＰである仮想ＣＰを生成するのである。具体的には、２つのＣＰが対象パーセルの境界を跨いでいるような場合、属性ＰＤＭの値により与えられる道路形状の頂点と２つのＣＰとを結ぶ２本の線分を算出し、線分の一方と対象パーセルの境界との交点に仮想ＣＰを付与する。その後、仮想ＣＰを含むＣＰの属性を計算／再計算し（Ｓ１２０）、対象パーセル内のＣＰに絞り込んで（Ｓ１３０）、候補リンク検索処理を実行する。
【解決手段】パーセル境界に仮想ＣＰを付与する（Ｓ１１０）。つまり、地図データがパーセルの単位で入力されパーセル境界にノードが設定されることに鑑み、パーセル境界上に、新たなＣＰである仮想ＣＰを生成するのである。具体的には、２つのＣＰが対象パーセルの境界を跨いでいるような場合、属性ＰＤＭの値により与えられる道路形状の頂点と２つのＣＰとを結ぶ２本の線分を算出し、線分の一方と対象パーセルの境界との交点に仮想ＣＰを付与する。その後、仮想ＣＰを含むＣＰの属性を計算／再計算し（Ｓ１２０）、対象パーセル内のＣＰに絞り込んで（Ｓ１３０）、候補リンク検索処理を実行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道路に沿って付与され、当該道路を特定するための属性を有するコアポイントに基づき、当該コアポイントが示す道路に該当する地図上のリンクを抽出する技術に関する。
【背景技術】
【０００２】
従来、交通情報を放送により転送するサービスとして、ＶＩＣＳ（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 ]