"道路に沿って付与され当該道路を特定するための属性を有する複数のコアポイントのデータを外部から受信し、当該コアポイントが示す前記道路に該当する地図上のリンクを抽出することで前記道路を推定する道路推定装置であって、前記コアポイントの有する属性に応じた属性を有するリンクで構成される地図データを入力する地図データ入力手段と、前記リンクの有する属性と前記コアポイントの有する属性とに基づき、前記地図データから前記コアポイントが示す前記道路の候補となるリンクを前記各コアポイントに対応させて抽出するリンク抽出手段と、前記コアポイントの配列から隣り合うコアポイントを始端側コアポイント及び終端側コアポイントとして抽出し、前記リンク抽出手段にて前記始端側コアポイント及び前記終端側コアポイントに対応させそれぞれ抽出された始端候補リンク及び終端候補リンクを接続する道路に該当するリンクを探索する道路探索処理を実行し、前記探索されたリンクに基づき、前記始端側コアポイントから前記終端側コアポイントへ到る地図上の道路を推定する道路推定手段と、を備えていることを特徴とする道路推定装置。請求項1に記載の道路推定装置において、前記道路推定手段は、前記道路探索処理にて探索された前記リンクの中で候補となるリンクを、前記コアポイントの属性に基づき選定する候補選定処理を実行して、前記始端側コアポイントから前記終端側コアポイントへ到る地図上の道路を推定することを特徴とする道路推定装置。請求項2に記載の道路推定装置において、前記道路推定手段は、前記コアポイントのうち始端側のコアポイントの属性に基づき、前記候補選定処理を実行することを特徴とする道路推定装置。請求項2又は3に記載の道路推定装置において、前記道路推定手段は、前記候補選定処理にて、前記コアポイントの属性のうちで道路形状に関わる属性である形状系の属性に基づき、前記リンクを選定することを特徴とする道路推定装置。請求項4に記載の道路推定装置において、前記道路推定手段は、前記候補選定処理にて、脇道への角度及び当該脇道への接続距離を示す脇道情報属性CA及び属性DCA、次のコアポイントへの位置的な角度及び接続距離を示す角度距離情報属性BR及び属性DMB、コアポイント間の運転距離を示す運転距離情報属性PD、及び、次のコアポイントまでを結ぶ直線からの道路の離間距離を示す離間距離情報属性PDMの少なくともいずれかに基づき、前記道路を選定することを特徴とする道路推定装置。請求項1~5の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記道路探索処理にて、前記始端候補リンクの両端点から前記終端候補リンクの両端点までの全ての組み合わせの中で前記リンクを探索することを特徴とする道路推定装置。請求項1~6の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記道路探索処理にて、前回の処理で決定された前記終端候補リンクがある場合、当該終端候補リンクを前記始端候補リンクとして前記リンクを探索することにより、前記道路探索の一部を省略することを特徴とする道路推定装置。請求項1~7の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記道路探索処理にて、前記始端側コアポイントが前記始端候補リンクの一方の端点に対応付け可能な場合は当該始端候補リンクのいずれか一方の端点を始点とし、前記終端側コアポイントが前記終端候補リンクの一方の端点に対応付け可能な場合は当該終端候補リンクのいずれか一方の端点を終点として前記リンクを探索することにより、前記道路探索の一部を省略することを特徴とする道路推定装置。請求項1~8の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記道路探索処理にて、前記始端候補リンクから前記終端候補リンクまでの前記リンクを探索する場合、過去の探索結果を利用することにより、前記道路探索の一部を省略することを特徴とする道路推定装置。請求項1~8の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記道路探索処理にて、前記始端側コアポイントから前記終端側コアポイントへ向かう方向に基づき前記リンクを探索することにより、前記道路探索の一部を省略することを特徴とする道路推定装置。請求項1~10の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記道路探索処理にて、前回の処理で推定された道路を構成する前記終端候補リンクの道路区分情報に基づき前記リンクを探索することにより、前記道路探索の一部を省略することを特徴とする道路推定装置。請求項1~11の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記道路探索処理にて、前記コアポイントの属性として前記始端側コアポイントから前記終端側コアポイントまでの運転距離が分かっている場合、探索の途中で前記リンクの距離が前記運転距離に基づく所定値を上回ると、前記道路探索を中止することを特徴とする道路推定装置。請求項1~12の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記道路探索処理にて、前記コアポイントの属性として前記始端側コアポイントと前記終端側コアポイントとを結ぶ直線からの道路の離間距離が分かっている場合、探索の途中で前記リンクの距離が前記離間距離に基づく所定値を上回ると、前記道路探索を中止することを特徴とする道路推定装置。請求項1~13の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記道路探索処理にて、前記道路の探索途中で当該道路を構成するリンク数相当値を計数し、探索の途中で前記リンク数相当値が所定値を上回ると、前記道路探索を中止することを特徴とする道路推定装置。請求項1~14の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記道路探索処理にて、前記始端側コアポイントに対応付け可能な前記始端候補リンクの端点及び前記終端側コアポイントに対応付け可能な前記終端候補リンクの端点がある場合、探索の途中で前記リンクの距離が前記端点間の距離に基づく所定値を上回ると、前記道路探索を中止することを特徴とする道路推定装置。請求項1~15の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記始端候補リンク、前記リンク及び前記終端候補リンクからなる道路が複数存在する場合、当該複数の道路に共通する部分があれば、当該共通する部分を前記始端側コアポイントから前記終端側コアポイントへ到る地図上の道路として推定することを特徴とする道路推定装置。請求項1~16の何れか一項に記載の道路推定装置において、前記道路推定手段は、前記始端候補リンク、前記リンク及び前記終端候補リンクからなる道路が複数存在する場合、当該複数の道路の共通する部分から道路が分岐している場合、前記分岐している道路のうちで道なりの道路を前記始端側コアポイントから前記終端側コアポイントへ到る地図上の道路として推定することを特徴とする道路推定装置。ところで、VICS以外のサービスとして、TPEGTransportProtocolExpertGroupにより送信される交通情報のデータを車両などの端末側で活用することが検討されている。しかし、TPEGにより送信されるデータフォーマット等では、例えばDLRデータの形式で位置情報が示される。この位置情報は、位置座標を有すると共に道路を特定するための属性を有するコアポイントで構成される。コアポイントは、通常、道路に沿って並ぶ複数個の配列として配信される。このようなコアポイントによって位置情報を示すようにすれば、地図データを作成するメーカの違いや地図データのフォーマット、バージョンに依存する位置参照テーブルが不要になる。すなわち、車載機側の地図データに依存せず、地図データ上で道路リンクを特定することが可能となる。その反面、コアポイントに基づいて道路を特定するための種々の処理が必要になってくる。例えば、上述したように地図データにもいろんな種類があるため、必ずしもコアポイントは地図データの道路上に存在しない。そのため、コアポイントが示す道路に該当するリンクを地図上で特定する処理が必要となってくる。ここで、コアポイントの代表している道路を推定するにはその候補となる地図データ上のリンクを抽出する必要があり、まずは、コアポイントの近傍にあるリンクを抽出することが考えられる。しかしながら、コアポイントは離散的な配列であるため、コアポイントの近傍にあるリンクのみでは連続した道路を表現することが出来ない。つまり、コアポイントの代表している道路を推定するには、コアポイントの近傍にあるリンクを抽出した後、当該リンク同士を結びつける道路リンクを、如何にして抽出するかが重要になってくる。本発明は、上述した問題を解決するためになされたものであり、配信されるコアポイントの情報から、コアポイントに対応する地図データ上のリンクを抽出した後、当該リンクを結びつける道路を適切に抽出し、コアポイントが示す道路を推定する道路推定装置を提供することを目的とする。上述した目的を達成するためになされた請求項1に記載の道路推定装置は、道路に沿って付与され当該道路を特定するための属性を有する複数のコアポイントのデータを外部から受信し、当該コアポイントが示す道路に該当する地図上のリンクを抽出することで道路を推定するものである。本装置では、地図データ入力手段が、地図データを入力する。地図データは、コアポイントの有する属性に応じた属性を有するリンクで構成される。また、リンク抽出手段が、リンクの有する属性とコアポイントの有する属性とに基づき、地図データからコアポイントが示す道路の候補となるリンクを各コアポイントに対応させて抽出する。このようにして各コアポイントに対応するリンクが抽出された後、道路推定手段が、道路探索処理を実行する。道路探索処理では、コアポイントの配列から隣り合うコアポイントが始端側コアポイント及び終端側コアポイントとして抽出される。そして、始端側コアポイント及び終端側コアポイントに対応させてそれぞれ抽出された始端候補リンク及び終端候補リンクを接続する道路に該当するリンクが、探索される。探索されたリンクに基づき、道路推定手段は、始端側コアポイントから終端側コアポイントへ到る地図上の道路を推定する。なお、複数個のコアポイントが配信されることを前提とし、始端側コアポイント及び終端側コアポイントのペアに対し処理が行われると、次に、前回の終端側コアポイントを始端側コアポイントとする新たなペアに対し再び処理が行われる。このようにすれば、配信されるコアポイントの情報から、コアポイントに対応する地図データ上のリンクを抽出した後、当該リンクを結びつける道路を適切に抽出することができる。なお、探索されるリンクが多くなる場合には特に、請求項2に示すように、道路推定手段が、候補選定処理を実行して、始端側コアポイントから終端側コアポイントへ到る地図上の道路を推定する構成とすることが好ましい。候補選定処理では、道路探索処理にて探索されたリンクの中で候補となるリンクがコアポイントの属性に基づき選定される。このようにすれば、探索されたリンクがさらに絞り込まれることとなり、コアポイントに対応する地図データ上のリンクを抽出した後、当該リンクを結びつける道路を適切に抽出することができる。このとき、請求項3に示すように、道路推定手段は、コアポイントのうち、始端側のコアポイントの属性に基づき、候補選定処理を実行するようにしてもよい。道路区分や形状の変化は、始端側から終端側へと道路に沿って発生するためである。このように始端側コアポイントの属性を優先して絞り込みに使用することで、隣接するコアポイント間で、万一道路区分や形状の変化があったとしても計算量、処理時間等を節約できる。また、このような候補選定処理では、請求項4に示すように、コアポイントの属性のうちで道路形状に関わる属性である形状系の属性に基づき、リンクを選定することが考えられる。このようにすれば、比較的簡単に道路を選定することができる。具体的には、請求項5に示すように、道路推定手段は、候補選定処理にて、脇道への角度及び当該脇道への接続距離を示す脇道情報属性CA及び属性DCA、次のコアポイントへの位置的な角度及び接続距離を示す角度距離情報属性BR及び属性DMB、コアポイント間の運転距離を示す運転距離情報属性PD、及び、次のコアポイントまでを結ぶ直線からの道路の離間距離を示す離間距離情報属性PDMの少なくともいずれかに基づき、道路を選定することが考えられる。これらの属性を用いることで、比較的簡単に道路を選定することが可能となる。ところで、道路探索処理により始端候補リンクから終端候補リンクへの道路が探索されるのであるが、探索すべきリンクをもらさず探索することが必要である。そこで、請求項6に示すように、道路推定手段は、道路探索処理にて、始端候補リンクの両端点から終端候補リンクの両端点までの全ての組み合わせの中でリンクを探索する構成とすることが考えられる。ここでいう端点は、地図データによってはノードとして定義されるものである以下でも同様。例えば、図23aに示すように、始端側コアポイントをCPaとし、終端側コアポイントをCPbとし、CPaに対し抽出されたリンクをSLとし、CPbに対し抽出されたリンクをGLとする。このとき、始端候補リンクSLと終端候補リンクGLとの間の道路を探索する場合、リンクSLを構成する2つのノードSN1,SN2とリンクGLを構成する2つのノードGN1,GN2との全ての組み合わせを考える。具体的には、SN1→GN1、SN1→GN2、SN2→GN1、SN2→GN2を結ぶ道路を探索する。このようにすれば、探索すべきリンクをもらさず探索することが可能となる。ただし、始端候補リンクや終端候補リンクが複数本ある場合など、道路探索処理に要する時間が長くなる虞がある。そこで、道路探索処理におけるリンク探索の一部を省略する構成が種々考えられる。例えば、請求項7に示すように、道路推定手段は、道路探索処理にて、前回の処理で推定された道路を構成する終端候補リンクがある場合、当該終端候補リンクを始端候補リンクとしてリンクを探索することにより、リンク探索の一部を省略するようにしてもよい。一例として図23bに示すように、CPa-CPb間の道路推定の結果、リンクSL→CL→GL1という道路が推定されたものとする。このときは、CPbから次のCPへの道路推定を行う場合、リンクGL1からの道路を探索する。すなわち、候補リンクにリンクGL2があっても、リンクGL2からの道路探索を省略する。このようにすれば、道路探索処理に要する時間を短くすることができる。また例えば、請求項8に示すように、道路推定手段は、道路探索処理にて、始端側コアポイントが始端候補リンクの一方の端点に対応付け可能な場合は当該始端候補リンクのいずれか一方の端点を始点とし、終端側コアポイントが終端候補リンクの一方の端点に対応付可能な場合は当該終端候補リンクのいずれか一方の端点を終点としてリンクを探索することにより、道路探索の一部を省略するようにしてもよい。対応付け可能な場合とは、コアポイントとリンクあるいは端点としてのノードとが同一の属性値を持っている場合をいう。一例として図23cに示すように、CPbが交差点である場合、交差点を示すノードGN2に対応付け可能であるため、リンクGLについては、一方のノードGN1に接続されるリンクだけを探索するという具合である。このようにすれば、道路探索処理に要する時間を短くすることができる。例えば、請求項9に示すように、道路推定手段は、道路探索処理にて、始端候補リンクから終端候補リンクまでのリンクを探索する場合、過去の探索結果を利用することにより、道路探索の一部を省略することとしてもよい。道路の探索は、例えば、リンクの端点として定義されるノードから順に接続されるリンクを探索することにより行われる。一例として図24aに実線で示すノードN1→N2→N3→N4という探索を最初に行ったものとする。このとき、ノードN1からの道路探索を2度目に行う場合、ノードN1→N5→N2という道路探索は行うが、ノードN2から先の探索は既に行っているため、ノードN2から先の探索は行わない。このようにすれば、道路探索処理に要する時間を短くすることができる。また例えば、請求項10に示すように、道路推定手段は、道路探索処理にて、始端側コアポイントから終端側コアポイントへ向かう方向に基づきリンクを探索することにより、道路探索の一部を省略することとしてもよい。例えば、始端側コアポイントから終端側コアポイントへ向かう方向と探索しようとするリンクとのなす角が所定角度以上になった場合には、当該リンクを含むリンクの探索を省略するという具合である。一例として図24bに示すように、CPaからCPbへ向かう方向を基準にして、ノードN1に接続されるリンクL1,L2,L3のうち角度a3が所定角度を越えている場合リンクL3については、道路探索の対象から外す。このようにすれば、道路探索処理に要する時間を短くすることができる。例えば、請求項11に示すように、道路推定手段は、道路探索処理にて、前回の処理で決定された終端候補リンクの道路区分情報に基づきリンクを探索することにより、道路探索の一部を省略することとしてもよい。リンクが道路区分情報を有していることを前提に、道路区分が同一のリンクを探索するのである。一例として図24cでは、CPbからCPcへの道路を、ノードN1から探索する。ここで、CPa-CPb間の道路がリンクL1として確定されているものとする。このとき、リンクL1の道路種別が国道であるため、ノードN1からの道路探索にあたり、道路種別が国道であるリンクL2を道路探索の対象にする。道路種別が県道であるリンクL3は、道路探索の対象から外す。このようにすれば、道路探索処理に要する時間を短くすることができる。ところで、道路探索処理によって道路を探索する場合、明らかに不適切なリンクを探索すると、道路探索処理に要する時間が長くなる虞がある。そこで、所定条件の下で道路の探索を中止する構成が考えられる。例えば、請求項12に示すように、道路推定手段は、道路探索処理にて、コアポイントの属性として始端側コアポイントから終端側コアポイントまでの運転距離が分かっている場合、探索の途中でリンクの距離が運転距離に基づく所定値を上回ると、道路探索を中止することが考えられる。コアポイント間の運転距離は、属性PDを利用することで取得可能である。一例として図25aでは、CPa及びCPbのいずれもが属性PDを有しているものとする。このとき、ノードN1からノードN2への道路を探索する際、形状補間点K1,K2,K3,K4,での累積距離を算出するようにする。そして、この累積距離が、PD値から一定値以上大きくなった場合、道路探索を中止する。このようにすれば、明らかに不適切なリンクを探索する可能性が小さくなり、道路探索処理に要する時間を削減することができる。また例えば、請求項13に示すように、道路推定手段は、道路探索処理にて、コアポイントの属性として始端側コアポイントと終端側コアポイントとを結ぶ直線からの道路の離間距離が分かっている場合、探索の途中でリンクの距離が離間距離に基づく所定値を上回ると、道路探索を中止することが考えられる。始端側コアポイントと終端側コアポイントとを結ぶ直線からの道路の離間距離は、属性PDMを用いることで取得可能である。一例として図25bに示すように、CPa-CPb間の直線距離とPDM値とを用い、破線で示すようなコ字状の距離を算出しておく。このとき、ノードN1からノードN2への道路を探索する際、形状補間点K1,K2,K3,K4,での累積距離を算出するようにする。そして、この累積距離が、破線で示される距離よりも一定値以上大きくなった場合に、道路探索を中止する。このようにすれば、明らかに不適切なリンクを探索する可能性が小さくなり、道路探索処理に要する時間を削減することができる。例えば、請求項14に示すように、道路推定手段は、道路探索処理にて、道路の探索途中で当該道路を構成するリンク数相当値を計数し、探索の途中でリンク数相当値が所定値を上回ると、道路探索を中止することが考えられる。ここでリンク数相当値は、リンクの数そのものであってもよいし、リンクを構成する端点例えばノードの数であってもよい。一例として図25cに示すように、ノードN1からノードN2への道路を探索する際、通過するノードN3,N4,N5,N6の個数を数えるようにする。そして、ノードの数が一定値以上となった場合に、道路探索を中止する。このようにすれば、明らかに不適切なリンクを探索する可能性が小さくなり、道路探索処理に要する時間を削減することができる。また例えば、請求項15に示すように、道路推定手段は、道路探索処理にて、始端側コアポイントに対応付け可能な始端候補リンクの端点及び終端側コアポイントに対応付け可能な終端候補リンクの端点がある場合、探索の途中でリンクの距離が端点間の距離に基づく所定値を上回ると、道路の探索を中止することが考えられる。ここで対応付け可能な場合とは、上述したように、コアポイントとリンクあるいは端点としてのノードとが同一の属性値を持っている場合をいう。一例として図25dでは、CPa及びCPbのいずれもが交差点であるとする。このとき、ノードN1,N2が交差点であれば、ノードN1,N2がそれぞれCPa,CPbに対応付け可能であるため、ノードN1,N2間の直線距離を予め算出しておく。そして、ノードN1からノードN2への道路を探索する際、通過するノードN3,N4,N5,N6までの累積距離を算出して、この累積距離が、予め算出したノードN1,N2間の直線距離よりも一定値以上大きくなった場合、道路探索を中止する。このようにすれば、明らかに不適切なリンクを探索する可能性が小さくなり、道路探索処理に要する時間を削減することができる。なお、道路推定手段が道路に基づき始端側コアポイントから終端側コアポイントへ到る地図上の道路を推定する際、道路が複数ある場合には、例えば次のようにして推定することが考えられる。例えば、請求項16に示すように、道路推定手段は、始端候補リンク、リンク及び終端候補リンクからなる道路が複数存在する場合、当該複数の道路に共通する部分があれば、当該共通する部分を、始端側コアポイントから終端側コアポイントへ到る地図上の道路として推定することが考えられる。共通する部分は、コアポイントが示す道路である蓋然性が高いためである。一例として図32bでは、CPaからCPbへの道路を探索した結果、ノードN1→N4→N5→N2→N3という道路、及び、ノードN1→N4→N6→N5→N2→N3という道路の2つが残ったものとする。このとき、太線で示した道路ノードN1→N4N5→N2→N3は、両方の道路に包含されている共通の部分であるため、この分断された2つの道路を、始端側コアポイントから終端側コアポイントへ到る地図上の道路として推定する。このようにすれば、地図上の道路を適切に推定することができる。また例えば、請求項17に示すように、道路推定手段は、始端候補リンク、リンク及び終端候補リンクからなる道路が複数存在する場合、当該複数の道路の共通する部分から道路が分岐している場合、分岐している道路のうちで道なりの道路を、始端側コアポイントから終端側コアポイントへ到る地図上の道路として推定することが考えられる。道なりの道路は、コアポイントが示す道路である蓋然性が高いためである。一例として図32bに示した例では、道なりの道路N1→N4→N5→N2→N3という道路を、始端側コアポイントから終端側コアポイントへ到る地図上の道路として推定する。道なりとは、図32cに示すように、リンク同士のなす角度例えば記号aで示す角度が所定角度例えば15度以下である場合をいう。このようにすれば、地図上の道路を適切に推定することができる。以下に本発明の実施例について、図面と共に説明する。<1.ナビゲーション装置の構成>最初にナビゲーション装置の構成を図1に基づいて説明する。図1に示すナビゲーション装置10が道路推定装置として機能し、具体的には、TPEGTransportProtocolExpertGroupデータを受信し、データ中の位置情報から道路のマッチングを行い、位置情報と共に送信される交通情報を道路に対応させて表示する。図1に示すナビゲーション装置10は、受信装置11、位置検出装置12、地図データ入力装置13、操作デバイス14、音声出力デバイス15、表示デバイス16、及び、制御回路17を備えている。受信装置11は、センタ20からTPEGデータを受信するためのものである。ナビゲーション装置10では、制御回路17にて選局を行うことにより、受信装置11を介してTPEGデータを取得する。位置検出装置12は、ナビゲーション装置10を搭載した車両の現在位置を検出するためのものであり、例えば、周知のジャイロスコープ、距離センサ及びGPS受信機等を有している。地図データ入力装置13は、地図データが格納された記録媒体具体的にはハードディスクやDVDを有するものであり、この記録媒体に格納された地図データを制御回路17に入力可能に構成されている。なお、地図データ入力装置13は、地図データを記憶保持するハードディスク装置に加えてDVDドライブを備えた構成にすることができる。このように地図データ入力装置13を構成すれば、ナビゲーション装置10は、DVDメディアを通じてオプション販売される地図データの追加データを、ハードディスク装置にインストール可能な構成にすることができる。なお、地図データは、パーセルと呼ばれる単位で管理され、パーセル単位でキャッシュされる。操作デバイス14は、ユーザからの指示を制御回路17に入力するためのものであり、表示デバイス16に配置されたタッチパネルや、ナビゲーション装置10の本体表面やリモートコントローラに設けられた操作スイッチ群等により構成される。この操作デバイス14を通じて、ユーザは、地図の縮尺変更やスクロール等の操作や目的地設定などナビゲーション装置10のあらゆる操作を行うことが可能である。また、音声出力デバイス15は、スピーカ等から構成され、制御回路17からの信号を受けてユーザへの案内音声等を出力するものである。この他、表示デバイス16は、フルカラー表示が可能なものであり、この表示デバイス16には、受信装置11を介して取得されるTPEGデータに基づく交通情報が、地図データ入力装置13より入力された地図データに基づく地図画像に重ねて表示される。また、制御回路17は、周知のマイクロコンピュータと同様の構成となっており、内部にCPU17a、ROM17b、RAM17c、I/O及びこれらの構成を接続するバスラインなどを備える。そして、CPU17aは、ROM17bに記憶されているプログラムに従って、種々の処理を行う。例えば、受信装置11を介して受信されるTPEGデータにはDLRDynamicLocationReferencingデータとしての位置情報が含まれる。したがって、制御回路17は、この位置情報を基に、地図データ側で該当する道路を推定する。<2.制御回路の機能>次に、TPEGデータの処理に関する制御回路17の機能を、図2に基づいて説明する。図2は、制御回路17の機能を模式的に示す説明図である。制御回路17の機能は、選局ブロック171、アプリケーションブロック172、DLRライブラリブロック173、及び、描画ブロック174に分けられる。選局ブロック171は、上述した受信装置11を介し、TPEGデータを受信するブロックである。つまり、選局ブロック171が、上述した選局機能を有している。受信されるTPEGデータは、選局ブロック171からアプリケーションブロック172へ渡される。アプリケーションブロック172は、アプリケーションプログラムの機能として実現される。アプリケーションプログラムは、ROM17bに記憶されており、CPU17aによって実行される。アプリケーションブロック172は、選局ブロック171から受け渡されるTPEGデータを管理し、新たなTPEGデータが受信されると、TPEGデータの更新を行う。また、アプリケーションブロック172は、画面に表示される表示対象のパーセル以下対象パーセルというを特定するための情報を有している。表示画面は、縮尺によって1つの対象パーセルで構成されることもあるし、複数例えば9つの対象パーセルで構成されることもある。アプリケーションブロック172は、対象パーセルの情報、及び、TPEGデータの位置情報を対象データとしてDLRライブラリブロック173へ渡す。DLRライブラリブロック173は、DLRライブラリプログラムの機能として実現される。DLRライブラリプログラムは、アプリケーションプログラムと同様、ROM17bに記憶されており、CPU17aによって実行される。DLRライブラリブロック173は、後述するマッチング処理を実行する。マッチング処理は、TPEGデータの位置情報に基づき、地図データ入力装置13から入力される地図データでの該当する道路リンクを推定するものである。このようなマッチング処理に先立ち、DLRライブラリ173は、アプリケーションブロック172からの要請により、地図データ入力装置13から地図データをRAM17cに読み込む。マッチング処理の結果は、DLRライブラリ173により、マッチング結果としてアプリケーションブロック172へ出力される。アプリケーションブロック172は、マッチング結果を管理する。そして、描画ブロック174によって、マッチング結果に基づく地図更新が行われる。これにより、上述したように、TPEGデータに基づく交通情報が、地図データ入力装置13より入力された地図データに基づく地図画像に重ねて表示される。<3.マッチング処理>本実施例は、DLRライブラリブロック173によるマッチング処理に特徴を有している。そこで、次にマッチング処理について説明する。図3は、マッチング処理を示すフローチャートである。最初のS100では、変換処理を行う。この変換処理は、TPEGデータのDLRとしての位置情報バイナリデータを、中間データに変換するものである。TPEGデータの位置情報には離散的な地点が主として用いられることは既に述べたが、これらの離散的な地点は、コアポイント以下CPというと呼ばれる。そして、CPは、様々な属性を有している。そこで、ここでは、道路推定に必要な属性を取り出して、中間データを作成する。<3.1変換後のCPの属性>中間データへの変換後のCPが有する属性を図4に示す。通常、複数個のCPがTPEGデータの位置情報として送信される。したがって、CPは配列して管理される。もちろん、一つだけのCPから位置を推定することも可能であり、CPが一つだけ送信される場合を排除する趣旨ではない。CPは、基本的な属性として、図4に示すように、緯度、経度、IPフラグ、仮想CPフラグを有している。緯度は、CPの緯度座標であり、経度は、CPの経度座標である。また、IPフラグは、CPが交差点か否かを示すフラグである。CPが交差点を示す場合には1がセットされ、それ以外の場合には0がセットされる。さらにまた、仮想CPフラグは、CPが仮想CPか否かを示すフラグである。CPが仮想CPである場合には1がセットされ、それ以外の場合には0がセットされる。なお、仮想CPについては後述する。また、CPは、CP間を繋ぐ道路に関し、種々の属性を有している。これらの属性には、道路形状に関わる形状系の属性と、道路形状に関わらない非形状系の属性とがある。まずは、非形状系の属性を説明する。<3.1.1非形状系の属性>属性FCは、道路区分を示すものである。図5に一例を示すように、道路のクラスは、0~9の10段階で示される。0がMainroadであり、1がFirstclassroadであり、2がSecondclassroadである。以下同様に、9のNinthclassroadまでランク付けされている。例えば、Mainroadは国や首都に接続されている道路であり、firstclassroadは主要都市間を結ぶ国道であるという具合に、ランク付けされている。属性FWは、物理道路タイプを示すものである。図6に一例を示すように、物理道路タイプは、0~12の13種類に分けられている。図6を見ると、不明確の場合は0であり、高速道路は1であり、複数車道高速道路以外は2であり、単一車道は3であり、ロータリーは4であり、トラフィックスクエアは5であり、取り囲まれた交通エリアは6であり、バイパスは7であり、支線道路は8であり、駐車場入口又は出口は9であり、サービスエリア入口又は出口は10であり、歩行者地帯は11であり、通路は12である。属性RDは、道路番号例えば国道1号などの国道番号が存在すれば、その道路番号がRD値となる。また、道路番号が存在しない場合、道路名称がRD値となる。道路名称は、公式名の最大5文字となっている図4参照。属性ITは、交差点の分類を示す図4参照。図7に一例を示すように、交差点の分類は、0~6の7種類に分けられている。図7を見ると、未定義の場合は0であり、高速又は制限された道路のインターチェンジは1であり、ロータリーは2であり、1,2以外の複雑な交差点は3であり、単純な交差点は4であり、トラフィックスクエアは5であり、2価の交差点道路番号や道路名称が切り替わる交差点は6である。属性RDIは、交差点の名称を示す図4参照。属性DDは、許可された合法の運転方向を示す図4参照。例えば、未定義は0となっており、順方向が1となっており、同様に、逆方向が2、両方向が3となっているという具合である。なお、属性AFRは、属性DDが参照可能であるか否かを示すフラグである。属性DDが0~3の値を持っている場合に属性AFRは1にセットされ、属性DDが値を持っていない場合には、参照不可として0がセットされる。<3.1.2形状系の属性>次に形状系の属性を説明する。属性BRは、次のCPへの位置的な角度を示す図4参照。上述したように、通常、複数個のCPが配列として管理される。BR値は、真北を基準とする時計回りの角度である。属性DMBは、次のCPへの直線距離を示す図4参照。属性BRと同様、通常、次のCPが存在するため、次のCPへの直線距離がDMB値となっている。属性CAは、脇道に対する角度を示す。脇道とは、道路番号が付加されないようなマイナーな道路である。脇道がある場合、属性BRの角度を基準に時計回りを正とし、反時計回りを負とする角度がCA値として設定される。属性DCAは、脇道に対する接続距離を示す。すなわち、CPからのベクトルを考えた場合、属性CAがベクトルの方向を示し、属性DCAがベクトルの大きさを示すことになる。したがって、属性CA及び属性DCAによって、位置座標が決定される。この位置座標が脇道の存在する地点を示すこととなる。属性PCIは、同一方向において複数の車道が存在する場合、いずれの車道が選択されるかを示す図4参照。この属性PCIには、車道数及び、対象道路が当該車道のうちの何番目かを示すシーケンス番号が含まれる。属性PDMは、次のCPまでを結ぶ直線からの対象道路の離間距離を示す図4参照。この離間距離には、対象道路までの最大距離が設定される。属性PDは、次に属性PDを含むCPまでの対象道路に沿った道なりの運転距離を示す図4参照。以上、中間データへの変換後のCPの有する属性について説明したが、このようなCPに対しての変換に伴い、仮想CPの付与、CPの属性値の再計算が実行される。具体的な手順は、図8に示すごとくである。<4.マッチング処理の詳細前半>図8中のS110では、対象パーセルの境界に仮想CPを付与する。図9は、CPによって表される道路形状を便宜的に二点鎖線で示す説明図である。もちろん、このような道路形状を推定し、地図データのリンク列で示される道路とのマッチングを行うことが終局的な目標である。したがって、図9中に二点鎖線で示す道路形状は、便宜的なものであり、実際の道路形状を示すものではない。ここで重要なのは、図9に示すように、CPの配列が対象パーセルだけでなくその周囲のパーセルにも跨ることがある、ということである。このような場合に、対象パーセルの境界に仮想CPを付与する。具体的には、図10aに示すように、2つのCPa,CPbが対象パーセルの境界を跨いでいるような場合、属性PDMの値により与えられる道路形状の頂点VとCPa,CPbとを結ぶ線分を算出し、線分の一方と対象パーセルの境界との交点に仮想CPを付与する。なお、以下、複数のCPを区別するために記号a,b,c,を用い、CPa,CPb,CPcと示す。<4.1属性の再計算>次のS120では、CPの属性を再計算する。仮想CPを付与することで、終端側のCP図10aではCPbは、後述するように、処理対象のCPから外される。そこで、始端側のCP図10aではCPa及び仮想CPの属性を再計算する。再計算される属性は、属性BR、属性DMB、属性PCI、属性CA、属性DCA、属性PDM、及び、属性PDである。属性BR及び属性DMBは、次のCPへの角度及び直線距離である図4参照。したがって、新たに付与した仮想CPを含め、次のCPへの角度及び直線距離を計算して設定する。属性CA及び属性DCAについては、始端側のCP図10aではCPaでの再計算は行わない。また、仮想CPには、無効値を設定する。属性CA及び属性DCAは、脇道に関するものであり、仮想CPには脇道の情報が妥当しないためである。属性PCIは、並行する車道数に関するものである図4参照。したがって、始端側のCP図10aではCPaでの再計算は行わない。仮想CPには、始端側及び終端側図10aではCPa,CPbに設定されているPCIに従った値を設定する。仮想CPに対する属性PCIの具体的な計算ルールを図11に示す。始端側のCP及び終端側のCPがいずれも属性PCIを保持する場合、両CPでの属性PCIが一致する場合には、仮想CPに対し、両CPと同一の値を設定する。一方、両CPでの属性PCIが不一致である場合、仮想CPに対し無効値を設定する。また、始端側のCP及び終端側のCPのいずれか一方が属性PCIを保持する場合、仮想CPが、属性PCIを保持するCPの近傍にある場合には、そのCPと同一の値を設定する。一方、仮想CPが属性PCIを保持するCPの近傍にない場合には、無効値を設定する。なお、近傍とは、例えば、属性PCIを保持するCPから仮想CPまでの直線距離が始端側のCPと終端側のCPとの直線距離の10以下である場合をいう。さらにまた、始端側のCP及び終端側のCPのいずれも属性PCIを保持していない場合、仮想CPに対し無効値を設定する。属性PDMは、次のCPまでを結ぶ直線からの道路の離間距離である図4参照。この属性PDMについては、仮想CPを付与する前の値に補正値を乗じて、設定する。具体的には、仮想CPの配置位置割合を算出し、次の式で補正値を計算する。i配置位置割合が50未満のとき補正値=0.6×配置位置割合/100式1ii配置位置割合が50以上のとき補正値=1.4×配置位置割合/100-0.4式2ここで、配置位置割合は、次の式で計算される。始端側のCPの属性PDMを再計算するときの配置位置割合は、始端側CPと仮想CPとの直線距離/始端側CPから終端側CPまでの直線距離合計式3となる。また、仮想CPの属性PDMを再計算するときの配置位置割合は、仮想CPと終端側CPとの直線距離/始端側CPから終端側CPまでの直線距離合計式4となる。なお、直線距離合計は、始端側CPから終端側CPまでの仮想CPを経由した場合の直線距離の合計であり、始端側CPと仮想CPとの直線距離及び仮想CPと終端側CPとの直線距離の合計となる。属性PDは、属性PDを有する次のCPまでの運転距離であり図4参照、必ずしもCPに付与される属性ではない。そのため、パーセル境界を跨ぐ2つのCPが属性PDを持たない場合がある。そこで、属性PDを持つCPのうちで仮想CPに最も近いCPを用いて再計算を行う。なお、属性PDを有するCPが存在しない場合、属性PDの再計算は行わない。具体的には、CPが有する属性PDの値を、仮想CPまでの直線距離に応じて按分する。すなわち、CPの属性PDの値は、CPの元の属性値PDの値に、上記式3の配置位置割合を乗じて求める。また、仮想CPの属性PDの値は、始点CPの元の属性値PDの値に、上記式4の配置位置割合を乗じて求める。<4.2CPの絞り込み>ここで図8の説明に戻り、S130では、対象パーセル内のCPに絞り込む。この処理は、対象パーセル内のCPだけ仮想CPを含むを処理対象とするものである。CPの配列は対象パーセルの境界を越えて続いていくことが考えられるが、アプリケーションで表示対象としている対象パーセルについてのみマッチングを行えば十分だからである。<4.2.1仮想CPを付与しない方法>なお、本実施例では仮想CPを付与することにより対象パーセルの境界にCPが存在するものとして当該仮想CPまでを処理対象としているが、DLRデータとして引き渡される本来のCPを対象パーセルの終端CPとして処理を行うようにしてもよい。例えば、図10bに示すように対象パーセルの境界をCPが跨いでいる場合、対象パーセル内のCPaを終端CPとしてもよい。又は、対象パーセル外の最初に現れるCPbを終端CPとしてもよい。ただし、CPa,CPbが対象パーセルの境界から離れて存在する場合があるため、例えばCPa,CPbの対象パーセルの境界からの離れ具合に応じて、いずれのCPを終端CPとするかを判断するようにしてもよい。一例として、図10bに示すように、2つのCPa,CPbを結ぶ直線と対象パーセルの境界との交点Kを算出し、交点Kまでの直線距離A,Bで離れ具合を測ることが考えられる。このとき、通常は対象パーセルの外側にあるCPbを終端CPとし、直線距離Bが所定値以上となった場合に、対象パーセルの内側にあるCPaを終端CPとすることが例示される。このときは、通常、CPbまでが処理対象となるため、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報を十分に表示することができる。また、例えばCPbが高速道路を示すような場合、CPbが対象パーセルの境界から極端に離れてしまう場合、CPaまでが処理対象となるため、処理に要する時間が長くなることを抑制できる。あるいは、通常は対象パーセルの内側にあるCPaを終端CPとし、直線距離Aが所定値以上となった場合に、対象パーセルの外側にあるCPbを終端CPとすることが例示される。このときは、通常、CPaまでが処理対象となるため、処理に要する時間を極力短くすることができる。また、例えばCPaが対象パーセルの境界から極端に離れてしまう場合、CPbまでが処理対象となるため、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報の表示が不十分になることを抑制できる。またあるいは、直線距離A,Bを比較し、直線距離Aが直線距離Bよりも小さい場合に対象パーセルの内側にあるCPaを終端CPとし、一方、直線距離Bが直線距離Aよりも小さい場合に対象パーセルの外側にあるCPbを終端CPとすることが例示される。このときは、直線距離に応じて終端CPが決定されるため、CPbまでが処理対象となる場合には、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報を十分に表示することができる。一方、CPaまでが処理対象となる場合には、処理に要する時間を極力短くすることができる。いずれにしても、仮想CPを付与する構成に比べ、仮想CPの付与に関する処理に要する時間が短縮される点、また、仮想CPの付与に伴う属性の再計算の処理に要する時間が短縮される点で有利である。<4.2.2属性の引き継ぎ>ところで、図8中のS130では、処理対象のCPを決定するに伴い、属性の引き継ぎ処理も行われる。DLRデータとしてのCPでは、交差点を示すCPIPフラグがセットされているCPだけが各種の属性を有している。そこで、このようなCPが有する非形状系の属性を、交差点間に存在するCPへ引き継ぐ。これにより、後述する処理で都度、非形状系の属性を取得する手間を省くことができる。具体的に引き継がれる属性は、属性FC、属性FW、属性RD、属性DD、及び、属性AFRである。以上説明した変換処理により、中間データに変換されたCPの配列が作成されることになる。つまり、この段階で、CPは、図4に示した各種の属性を有するものとなっている。一方で、地図データを構成するノード及びリンクの少なくともいずれかが、CPの属性に対応する属性を有している。そこで、各種属性を比較することで、終局的にCPにより示される道路を推定する。<5.マッチング処理の詳細後半>図3のマッチング処理の説明に戻り、S200では、候補リンク検索処理を実行する。候補リンク検索処理は、候補となるリンク列を検索し、その後、リンク単位で絞り込みを行うものである。次のS300では、候補選定処理を実行する。候補選定処理は、S200にて絞り込まれたリンクを、さらに絞り込むものである。続くS400では、道路マッチング処理を実行する。道路マッチング処理は、CP間を繋ぐリンクを推定するものである。これらS200~S400の処理は、図8中のS130で絞り込まれる各CPを対象CPとしてCPの数だけ繰り返し実行される。そこで、以下では、これらの処理を詳細に説明する。S200の候補リンク検索処理の一例を図12に示す。最初のS210では、対象CPの情報が取得される。この処理は、CPの種類、緯度、経度を取得するものである。CPの種類は、交差点を示すCP、仮想CP、その他のCPの区別である。続くS220では、検索範囲を設定する。この処理は、対象CPを中心とするリンクの検索範囲を設定するものである。この検索範囲は特に、図13aに破線で示すように、その境界が垂直又は水平の線分で構成される多角形として設定される。本実施例では、正方形と当該正方形の一辺よりも長い十字形状とを合成したような範囲として設定されている。次のS230では、検索範囲にあるパーセルを取得する。この処理は、ノード及びリンクがパーセル単位で管理されているため、リンク列の選定を行うにあたり、検索範囲に係るパーセルを全て取得するものである。例えば図13bに示すように、検索範囲に応じて3つのパーセルP1,P2,P3が取得されるという具合である。続くS240では、リンク列選定処理を実行する。このリンク列選定処理では、非形状系の属性により、リンクがリンク列単位で検索される。なお、リンク列とは、高速道路、一般道路などの道路区分が同一となっている一連のリンク群である。ここでは、S230にて取得されたパーセルに一部が含まれるリンク列が検索対象となる。つまり、この段階では、検索範囲にあるかの判定をせず、最初に属性でリンク列を絞り込むのである。<5.1リンク列選定処理>ここで、リンク列選定処理について詳細に説明する。リンク列選定処理の一例を図14に示す。このリンク列選定処理では、非形状系の属性である属性FC、属性FW、属性RDにより、リンク列単位での抽出が行われる。最初のS241では、属性FCが一致するリンク列に絞り込む。属性FCは、上述したように道路区分を示す属性である図5参照。ここでは、リンク列を構成するリンクに付与されている道路区分と対象CPの属性FCとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で道路区分が変わることがある。したがって、リンク列を構成する全てのリンクの道路区分が属性FCに一致する場合に、当該リンク列を候補リンク列とする。次のS242では、属性FWが一致するリンク列に絞り込む。属性FWは、上述したように、物理道路タイプを示す属性である図6参照。ここでは、リンク列を構成するリンクに付与されている物理道路タイプと対象CPの属性FWとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で物理道路タイプが変わることがある。したがって、リンク列を構成する全てのリンクの物理道路タイプが属性FWに一致する場合に、当該リンク列を候補リンク列とする。続くS243では、属性RDが一致するリンク列に絞り込む。属性RDは、上述したように、道路番号又は道路名称を示す属性である図4参照。ここでは、属性RDが道路番号を示す場合に限り、道路番号による一致を判断する。すなわち、リンク列を構成するリンクに付与されている道路番号と対象CPの属性RDとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で道路番号が変わることがある。したがって、リンク列を構成する全てのリンクの道路番号が属性RDに一致する場合に、当該リンク列を候補リンク列とする。このようなリンク列選定処理により、非形状系属性で絞り込まれたリンク列が候補リンク列として残ることになる。<5.2リンクの抽出>図12のS250では、対象CPを中心とする検索範囲に一部が含まれるリンクを抽出する。S240のリンク列選定にてリンク列が選定されるため、ここでは、選定されたリンク列を構成するリンクのうち検索範囲に一部が含まれるリンクを抽出する。ここで検索範囲に一部が含まれるリンクについて説明する。以下では特に、ノードが交差点に対して通常付与されること、ノードがパーセルの境界に付与されること、必要に応じてノード間に形状補間点が設定されること、を前提として説明を続ける。<5.2.1対象CPが交差点の場合>対象CPが交差点を示す場合は、ノードを意識した処理を行う。すなわち、対象CPが交差点を示す場合は、対象CPがノードと対応付けられるためである。したがって、この場合、リンクを構成する2つのノードのうちのいずれかが検索範囲に含まれているリンクを検索範囲に一部が含まれるリンクとする。例えば図15aに示す対象CPが交差点を示すものとする。この場合、検索範囲に含まれるノードA,B,Cは、対象CPと対応付けられる。そのため、ノードA,B,Cが端点の一方となっているリンクL1,L2,L3,L4,L5が検索範囲に一部が含まれるリンクとなる。ただし、地図データは、その縮尺に応じたレベル以下パーセルレベルというを有している。このパーセルレベルは、ユーザによる縮尺の切り替えによって切り替わるため、リンクの抽出は、全てのパーセルレベルで行われる。パーセルレベルは、下位レベルから順に、LV0→LV2→LV4→LV6→LV8→LV10などとして設定される。そして、上位レベルになるほど、交差点や道路が間引かれる。CPは、最も下位のパーセルレベルであるLV0に相当するデータとなっている。したがって、LV2よりも上位のパーセルレベルでは、必ずしも交差点に対応するノードが存在するとは限らない。そこで、LV2よりも上位のパーセルレベルでの抽出処理では、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。一定条件を満たす場合については、後述する。<5.2.2対象CPが仮想CPである場合>対象CPが仮想CPである場合も、ノードを意識した処理を行う。地図データの仕様では、パーセル境界には必ずノードが設定される。したがって、対象CPが仮想CPである場合、当該仮想CPは、パーセル境界に付与されるものであるため、同一のパーセル境界に存在するノードがあれば、そのノードと対応付けられる。そこで、リンクを構成するノードのいずれかがパーセル境界に存在する場合、このパーセル境界に存在するノードが検索範囲に含まれるときは、そのリンクを検索範囲に一部が含まれるリンクとする。例えば、図15bに示す対象CPが仮想CPを示すものとし、ノードDがパーセル境界に存在するノードだとすると、ノードDを端点とするリンクL6,L8が検索範囲に一部が含まれるリンクとなる。<5.2.3対象CPが交差点でも仮想CPでもない場合>この場合、対象CPがノードと対応付けられるか否かは分からないため、ノードを意識することなく、リンクの抽出を行う。つまり、対象CPが交差点でも仮想CPでもない場合は、リンクを構成する少なくともいずれかのノードが検索範囲に含まれている場合の他に、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。この場合のリンクの抽出は、全てのパーセルレベルで同様に行われる。<5.2.4一定条件を満たす場合>一定条件を満たす場合とは、次の2つの場合をいう。一つは、ノード間に形状補間点が設定されている場合、当該形状補間点を結んだ線分の一部が検索範囲に含まれている場合である。例えば図15cに示すリンクL9は、その形状補間点小さな黒丸を結ぶ線分の一部が検索範囲に含まれているため、ノードE,Fが検索範囲に含まれていないが検索範囲に一部が含まれるリンクとなる。一方、リンクL10は、その形状補間点を結ぶ線分の一部が検索範囲に含まれていないため、検索範囲に一部が含まれるリンクにならない。もう一つは、ノード間に形状補間点が設定されていない場合、2つのノードを結ぶ線分の一部が検索範囲に含まれている場合である。例えば、図15dに示すリンクL11は、2つのノードG,Hを結ぶ線分の一部が検索範囲に含まれているため、検索範囲に一部が含まれるリンクとなる。<5.2.5その他>図12の説明に戻り、続くS260では、検索範囲に一部が含まれるリンクのうちで属性RDが一致するリンクに絞り込む。属性RDが道路番号を示す場合は図14中のS243にて判断するため、ここでは属性RDが道路名称である場合に、当該道路名称による一致を判断する。なお、道路名称は最大5文字となっているため、属性RDの値としての文字列がリンクに付与される道路名称に含まれるか否かを判断する。次のS270では、リンクの数が10本以内に収まるように絞り込む。具体的には、S260までの絞り込みによってリンクの数が10本を越えている場合、対象CPに近いものから順に10本のリンクを選択する。対象CPに近いか否かは、対象CPから各リンクへ例えば垂線を下ろすなどして距離を求めることによって判断する。<5.3候補選定処理>次に、図3中のS300の候補選定処理について説明する。候補選定処理は、リンク、ノード単位の候補選定を行うものである。候補選定処理の一例を図16に示した。最初のS310では、非形状系属性の一致判定を行う。詳細については後述するが、ここでは、S200で抽出されたリンク又は当該リンクを構成するノードに対し、属性FC、属性FW、属性IT、属性RDI、属性DD及び属性AFRを用いた一致判定を行う。なお、属性FC及び属性FWは、リンク列を絞り込む際に利用しているため図14中のS241,S242重複した処理となっているが、確実をきすために再度行うものである。また、ここでの一致判定は、確実を期すため、属性IT、属性RDI、属性DD及び属性AFRなどを用いた細かい一致判定となっている。次のS320では、非形状系属性での判定結果を基に候補となるリンクを絞り込む。具体的には、S310での非形状系属性による一致判定の結果、各属性との一致数が多いリンクを、候補リンクとする。続くS330では、形状系属性の一致判定を行う。詳細については後述するが、ここでは、S320にて候補リンクとされたリンク又は当該リンクを構成するノードに対してのみ、属性BR、属性PCI、属性CA及び属性DCAを用いた一致判定を行う。続くS340では、形状系属性での判定結果で候補となるリンクを絞り込む。具体的には、S330での形状系属性による一致判定の結果、各属性との一致数が多いリンクを、候補リンクとする。<5.3.1非形状系属性の一致判定>ここで、S310の非形状系属性の一致判定の詳細を説明する。非形状系属性の一致判定の一例を図17に示す。最初のS311では、属性FCでの一致判定を行う。属性FCは、上述したように道路区分を示す属性である図5参照。ここでは、判定対象のリンクに付与されている道路区分と対象CPの属性FCとの一致を判定する。続くS312では、属性FWでの一致判定を行う。属性FWは、上述したように、物理道路タイプを示す属性である図6参照。ここでは、判定対象のリンクに付与されている物理道路タイプと対象CPの属性FWとの一致を判定する。次のS313では、属性ITでの一致判定を行う。属性ITは、上述したように、交差点の分類を示す属性である図7参照。したがって、対象CPが交差点を示すものである場合にのみ、この一致判定が行われる。なお、属性ITに相当する属性は、ノード及びリンクの少なくともいずれか一方が有している。そこで、ノードが交差点の分類を示す交差点分類情報を持っている場合、対象CPに対応するノードの交差点分類情報と対象CPの属性ITとの一致を判定する。また、リンクが交差点の分類を示す交差点分類情報を持っている場合、対象CPに対応するノードに接続するリンクの交差点分類情報と対象CPの属性ITとの一致を判定する。後者では、2つのノードの交差点分類情報をリンクが持っていることがあるため、いずれかの交差点分類情報と属性ITとの一致を判定する。続くS314では、属性RDIでの一致判定を行う。属性RDIは、上述したように、交差点の名称を示すものである図4参照。したがって、対象CPが交差点を示すものである場合にのみ、この一致判定が行われる。ここでは、対象CPに対応するノードの交差点名称と対象CPの属性RDIとの一致を判定する。なお、この判定は、属性RDIの値である文字列がノードの交差点名称に含まれるか否かで行われる。次のS315では、属性DD及び属性AFRでの一致判定を行う。属性DDは許可された合法の運転方向を示すものであり、属性AFRは、属性DDが参照可能であるか否かを示すフラグである図4参照。ここでは、判定対象のリンクの属性一方通行コードと対象CPの属性DDとを比較して判定する。なお、属性AFRが1としてセットされており属性DDが有効である場合であって属性DDが0未定義でない場合を除いて、判定を行う。ところで、属性DDが示すのはある交通情報に対する道路の通行可能方向であり、リンクの有する一方通行コードとの比較では、両者の順逆方向までは判断できない。したがって、ここでは通行方向の一致を判断するわけではなく、片側通行の道路か両側通行の道路かを判定することにとどまる。<5.3.2形状系属性の一致判定>続けて、S330の形状系属性の一致判定の詳細を説明する。形状系属性の一致判定の一例を図18に示す。最初のS331では、属性BRでの一致判定を行う。属性BRは、上述したように、次のCPへの位置的な角度を示すものである図4参照。一方、リンクは、法定上の走行方向を属性として有している。そこで、ここでは、リンクの走行方向が対象CPの属性BRに基づく方向と大きく異なっている場合に、不一致の判定を行う。例えば、リンクの走行方向を示すベクトルと、次のCPへ向かう属性BRに基づくベクトルとのなす角度が所定角度例えば90度以上となる場合に、不一致と判定することが考えられる。なお、リンクが双方向に走行可能となっている場合、走行方向を示す2つのベクトルで判定する。例えば、図19aでは、リンクL1,L2,L3の走行方向を示すベクトルVL1,VL21,VL22,VL3と属性BRに基づくベクトルVBとのなす角度で判定を行うという具合である。ここでは両ベクトルのなす角度が90度以上となる場合に、不一致と判定するものとする。なお、リンクL2は、双方向に走行可能となっており、走行方向を示す2つのベクトルVL21,VL22で判定される。ここでベクトルVBとベクトルVL1とのなす角度は、180度に近いものとなっており、90度以上であるため、リンクL1は、不一致と判定される。また、ベクトルVL22とベクトルVBとがなす角度は90度以上となるが、ベクトルVL21とベクトルVBとがなす角度が90度よりも小さいため、リンクL2は一致と判定される。さらにまた、ベクトルVL3とベクトルVBとがなす角度は90度よりも小さいため、リンクL3は一致と判定される。つまり、90度以上となる場合を不一致とする場合は、図19bに示すように、属性BRに基づくベクトルVBに対し、リンクの走行方向がベクトルV1,V2で示される場合には一致と判定され、ベクトルV3,V4で示される場合には不一致と判定される。図18中のS332では、属性PCIでの一致判定を行う。属性PCIは、上述したように、同一方向において複数の車道が存在する場合、いずれの車道が選択されているかを示すものである図4参照。属性PCIには、車道数及びその車道の中のいずれの車道かを示すシーケンス番号が含まれる。ただし、この属性で一致を判定しようとする場合、並走するリンクを残らず特定する必要がある。そこで、図20に示すように、最初のS333では、対象CPを中心とした検索エリアを設定する。この検索エリアは、対象CPを中心とした円の内部とすることが考えられる。例えば、所定距離例えば150mを半径とする円の内部を検索エリアにするという具合である。なお、PCI属性の一つとして検索エリアのデフォルト値が設定されることがあるため、その場合は、デフォルト値に所定距離例えば150mを加えた値を半径とする円の内部を検索エリアとすることが考えられる。続くS334では、検索エリア内のリンクを抽出する。ここでは、属性PCIの一つにインジケータタイプがあるため、このインジケータタイプに基づき、緯度方向あるいは経度方向の仮想直線を引き、この仮想直線と交差するリンクを抽出する。次のS335では、抽出したリンクの数と車道数とが一致するか否かを判断する。ここで車道数が一致すると判断された場合S335でYES、S336にてシーケンス番号でリンクを特定し、当該リンクが判定対象のリンクと一致するか否かを判定して、属性PCIでの一致判定を終了する。一方、車道数が一致しないと判断された場合S335でNO、S336の処理を実行せず、属性PCIでの一致判定を終了する。これは、車道数が一致しない場合、誤判定となる虞があるからである。図18に戻り、S337では、属性CA及び属性DCAでの一致判定を行う。属性CAは脇道に対する角度を示すものであり、属性DCAは脇道に対する接続距離を示すものである図4参照。ここでは、最初に、脇道の方向を検出する。具体的には、図21aに示すように、属性CAが負値である場合、次のCPへ向かう方向属性BRに基づく方向に対し、左側に脇道があると判断する。一方、図21bに示すように、属性CAが正値である場合、次のCPへ向かう方向属性BRに基づく方向に対し、右側に脇道があると判断する。なお、属性CAが0である場合、脇道の方向が特定できないため、一致判定を行わない。次に、判定対象のリンクとそのリンクの脇道との位置関係から属性CA及び属性DCAでの一致判定を行う。以上説明してきたS300の候補選定処理によって、各CPに対し、その周辺に、候補となるリンクが選定される。これらのリンクを繋ぐリンク、すなわちCP間を繋ぐリンクを推定する処理が、図3中の道路マッチング処理S400である。<5.4道路マッチング処理>次に、S400の道路マッチング処理について説明する。道路マッチング処理の一例を図22に示す。道路マッチング処理では、2つのCPを対象CPとし、始端側に位置するCPを始端側CP、終端側に位置するCPを終端側CPとして処理を行う。<5.4.1道路探索>最初のS410では、始端候補リンクから終端候補リンクを繋ぐ道路を探索する。始端候補リンクは、始端側CPに対し抽出されたリンクである。また、終端候補リンクは、終端側CPに対し抽出されたリンクである。ここでは、始端候補リンクと終端候補リンクとを結ぶ全ての道路を探索する。例えば、図23aに示すように、始端側CPをCPaとし、終端側CPをCPbとし、CPaに対し抽出されたリンクをSLとし、CPbに対し抽出されたリンクをGLとする。このとき、始端候補リンクSLと終端候補リンクGLとの間の道路を探索する場合、リンクSLを構成する2つのノードSN1,SN2とリンクGLを構成する2つのノードGN1,GN2との全ての組み合わせを考える。具体的には、SN1→GN1、SN1→GN2、SN2→GN1、SN2→GN2を結ぶ道路を探索する。次のS420では、道路単位候補選定を実行する。この処理は、各種の形状系属性を基に、S410にて探索された道路のうちで候補となる道路を判定するものである。続くS430では、S420における判定結果に基づき、道路を絞り込む。次のS440では、道路が一意に決定されたか否かを判断する。ここで道路が一意に決定された場合S440でYES、S450にてマッチング結果を出力し、その後、道路マッチング処理を終了する。一方、道路が一意に決定されない場合S440でNO、S450の処理を実行せず、道路マッチング処理を終了する。<5.4.2道路探索の省略>なお、このような道路マッチング処理S410~S440がペアとなる2つの対象CPに対して繰り返されるのであるが、上述のS410では、先の道路マッチング処理の結果を用いて探索する道路を省略する場合がある。例えば、図23bに示すように、CPa-CPb間の道路マッチング処理の結果、リンクSL→CL→GL1という道路が一意に決定されたものとする。このときは、CPbから次のCPへの道路マッチング処理を行う場合、リンクGL1からの道路を探索する。すなわち、候補リンクにリンクGL2があっても、リンクGL2からの道路探索を省略する。また、CPの種類によっても、道路探索を省略する。CPbが交差点である場合、例えば図23cに示すように、交差点を示すノードGN2と対応するため、リンクGLについては、一方のノードGN1に接続される道路を探索する。すなわち、SN1→GN1、SN2→GN1を結ぶ道路を探索する。CPbが仮想CPである場合、例えば図23dに示すノードGN2が対象パーセルの境界に位置するノードであれば、このノードが道路の始端又は終端となる。そこで、この場合も、リンクGLについては、一方のノードGN1に接続される道路を探索する。すなわち、SN1→GN1、SN2→GN1を結ぶ道路を探索する。さらにまた、一度探索した道路を再び探索しないようにして道路探索に要する時間を短縮することが考えられる。例えば図24aに実線で示すノードN1→N2→N3→N4という探索を最初に行ったものとする。このとき、ノードN1からの道路探索を2度目に行う場合、ノードN1→N5→N2という道路探索は行うが、ノードN2から先の探索は既に行っているため、ノードN2から先の探索は行わない。また、ノードからリンクが分岐する場合、リンクに優先順位をつけて道路探索を行う。例えば、あるノードから道路探索を行う場合、対象CPを結ぶ方向を基準にして、ノードに接続されるリンクの基準方向からの角度を求め、所定角度以内にあるリンクのみを道路探索の対象とする。図24bでは、ノードN1からの道路探索を行うのであるが、CPaからCPbへ向かう方向を基準にして、ノードN1に接続されるリンクL1,L2,L3の基準方向からの角度a1,a2,a3を求める。ここで角度a1,a2が所定角度以内にあるとすると、リンクL1,L2を道路探索の対象とする。一方、角度a3が所定角度を越えている場合、リンクL3を道路探索の対象から外す。さらにまた、ノードからの探索を行う場合、そのノードまでのリンクの道路種別と同じ道路種別のリンクを道路探索の対象とする。例えば図24cでは、CPbからCPcへの道路を、ノードN1から探索する。ここで、CPa-CPb間の道路がリンクL1として確定されているものとする。このとき、リンクL1の道路種別が国道であるため、ノードN1からの道路探索にあたり、道路種別が国道であるリンクL2を道路探索の対象にする。道路種別が県道であるリンクL3は、道路探索の対象から外す。<5.4.3道路探索の中止>ところで、S410における道路探索が所定時間以内に終了するとは限らない。そこで、道路探索を途中で中止するようにしてもよい。例えば属性PDを利用することが考えられる。図25aでは、CPa及びCPbのいずれもが属性PDを有しているものとする。このとき、ノードN1からノードN2への道路を探索する際、形状補間点K1,K2,K3,K4,での累積距離を算出するようにする。そして、この累積距離が、PD値から一定値以上大きくなった場合、道路探索を中止する。また例えば属性PDMを利用することが考えられる。図25bに示すように、CPa-CPb間の直線距離とPDM値とを用い、破線で示すようなコ字状の距離を算出しておく。このとき、ノードN1からノードN2への道路を探索する際、形状補間点K1,K2,K3,K4,での累積距離を算出するようにする。そして、この累積距離が、破線で示される距離よりも一定値以上大きくなった場合に、道路探索を中止する。例えば通過するノードの数を利用することが考えられる。図25cに示すように、ノードN1からノードN2への道路を探索する際、通過するノードN3,N4,N5,N6の個数を数えるようにする。そして、ノードの数が一定値以上となった場合に、道路探索を中止する。また例えばCPが交差点であることを利用することが考えられる。図25dでは、CPa及びCPbのいずれもが交差点であるとする。このとき、ノードN1,N2が交差点であれば、ノードN1,N2がそれぞれCPa,CPbに対応するものとなるため、ノードN1,N2間の直線距離を予め算出しておく。そして、ノードN1からノードN2への道路を探索する際、通過するノードN3,N4,N5,N6までの累積距離を算出して、この累積距離が、予め算出したノードN1,N2間の直線距離よりも一定値以上大きくなった場合、道路探索を中止する。ここでは4つの手法を説明したが、いずれの手法によっても、間違っていると思われる道路の探索が途中で打ち切られるため、処理負荷が軽減される。<5.4.4道路単位候補選定>ここで、図22中の道路単位候補選定について説明する。道路単位候補選定の一例を図26に示す。道路単位候補選定は、CP間で抽出された道路の単位で、OK又はNG判定を行うものである。最初のS421では、属性CA/DCAで判定する。上述したように、属性CAは脇道に対する角度を示すものであり、属性DCAは脇道に対する接続距離を示すものである図4参照。ここでは、探索された道路の中で、属性CA及び属性DCAによって特定されるリンクを、脇道であるとして、このリンクを含む道路に対しNG判定を行うものである。具体的には、図27aに示すように、属性CA及び属性DCAが示す位置座標の周囲破線で示す範囲にリンクがあれば、当該リンクを含む道路をNGと判定する。例えば図27bには、CP間を繋ぐ道路として道路1及び道路2が示されているが、属性CA及び属性DCAから脇道と判定されたリンクを含む道路1はNGと判定されることになる。図26中のS422では、属性BR/DMBで判定する。上述したように、属性BRは次のCPへの角度を示すものであり、属性DMBは次のCPまでの直線距離を示すものである図4参照。CPが示すデータとナビゲーション装置10の地図データとの間にずれがある場合、この属性BR/DMBを利用することで、より確からしい道路を特定することができる。そこで、図28に示すように、CPb-CPc間の道路の判定を、CPbの一つ前のCPaの属性BR及び属性DMBを用いて行う。具体的には、属性BR及び属性DMBから特定される位置座標の周囲記号Hの破線で示す範囲のリンクLを含む道路はOKと判定する。なお、CPb-CPc間の道路の判定であるため、リンクLを構成するノード又は形状補間点が所定範囲に入ることを条件とする。例えば、所定範囲は、CPbとCPcとを結ぶ線分と属性PDMとから設定される矩形図中に二点鎖線で示したの内側とすることが考えられる。もちろん、所定範囲は、このような矩形に限られず、CPb及びCPcを通る楕円の内側などとしてもよい。次のS423では、属性PDで判定する。上述したように、属性PDは、属性PDを有する次のCPまでの運転距離である図4参照。したがって、探索された道路の運転距離によって、当該道路が候補となり得るか否かを判定する。具体的には、図29に示すように、CPa-CPb間の運転距離を算出する場合、各CPがノードに対応するとは限らないため、CPaからリンクL1への垂線を下ろし、また、CPbからリンクL3への垂線を下ろして、それぞれの交点をM,Nとする。そして、交点Mから交点Nまでの運転距離を算出する。なお、交点Mから直後のノードまでの運転距離は、この運転距離のリンクL1における割合を算出することで求める。ここで、交点Mから直後のノードまでがリンクL1のmである場合、リンクL1の運転距離にm/100を乗じて、交点Mから直後のノードまでの運転距離を算出する。同様に、交点Nから直前のノードまでの運転距離は、この運転距離のリンクL3における割合を算出することで求める。ここで、交点Nから直前のノードまでの距離がリンクL1の距離のnである場合、リンクL3の運転距離にn/100を乗じて、交点Nから直前のノードまでの運転距離を算出する。ところで、全てのCPが属性PDを有しているとは限らない。したがって、CPaが属性PDを有しているがCPbが属性PDを有していない場合、図30aに示すように、道路の候補判定は行わず、そのまま道路を保持する。次に、図30bに示すCPcが属性PDを有しているとすると、CPa-CPc間で属性PDに基づく道路判定を行う。すなわち、道路L1→L2→L3→L5→L6→L10と、道路L1→L4→L5→L6→L10と、道路L1→L2→L3→L5→L7→L8→L9→L10と、道路L1→L4→L5→L7→L8→L9→L10と、を候補にして、NG判定を行う。これにより、図30cに示すように道路L1→L2→L3→L5→L6→L10という道路が残った場合、CPa-CPb間の道路L4、及び、CPb-CPc間の道路L7→L8→L9は、NGと判定されることになる。続くS424では、属性PDMで判定する。上述したように、属性PDMは、次のCPまでを結ぶ直線からの道路の離間距離を示す図4参照。この処理では、属性PDMに基づき道なりの運転距離を求め、探索された道路が候補となるか否かを判定する。具体的には、属性PDMに基づく道なりの運転距離を次の式により算出する。PDM運転距離=CP間の直線距離を直径とする円周の半分×補正値式5ここで補正値は、属性PDMの値とCP間の直線距離の半分との比率からテーブルによって確定する。例えば、図31aに示すようにCPa-CPb間の直線距離の半分をrとすると、図31bに示すテーブルによって、属性PDMの値と距離rとの比率PDM/rから補正値を求める。なお、図31bに示したテーブルは、一部を抜粋したものである。そして、候補となっている道路の道なりの運転距離を道路運転距離とすると、道路運転距離が次の式を満たす場合に、その道路をOKと判定する。PDM運転距離×0.5<道路運転距離<PDM運転距離×1.5式6<5.4.5マッチング結果の出力>そして、上述したように、これらの判定結果によって道路を絞り込み図22中のS430、道路が一意に決定されるとS440でYES、S450にてマッチング結果を出力する。マッチング結果は、一意に特定された道路を構成する全リンクのリンクID、始点オフセット距離、終点オフセット距離などで構成される。なお、始点オフセット距離は、道路の始点となるリンクのどの位置からがマッチングの開始位置かを示す距離である。同様に、終点オフセット距離は、道路の終点となるリンクのどの位置までがマッチングの終了位置かを示す距離である。<5.4.6道路の決定について>なお、通常、道路が一意に決定されないとS440でNO、道路マッチング失敗となって、マッチング結果が出力されないことになる。ただし、次のような場合には、道路が一意に決定されたものとする。例えば、図32aでは、CPaからCPbへの道路を探索した結果、ノードN1→N4→N5→N2→N3という道路、及び、ノードN1→N4→N5→N2という道路の2つが残ったものとする。このとき、太線で示した道路ノードN1→N4→N5→N2は、両方の道路に包含されているため、この道路を一意に決定された道路とする。また例えば、図32bでは、CPaからCPbへの道路を探索した結果、ノードN1→N4→N5→N2→N3という道路、及び、ノードN1→N4→N6→N5→N2→N3という道路の2つが残ったものとする。このとき、太線で示した道路ノードN1→N4N5→N2→N3は、両方の道路に包含されているため、この分断された2つの道路を一意に決定された道路とする。あるいは、図32bに示すような例で、道なりの道路を一意に決定された道路とすることが考えられる。道なりとは、図32cに示すように、リンク同士のなす角度例えば記号aで示す角度が所定角度例えば15度以下である場合をいう。<6.効果>以上詳述したように本実施形態では、図22に示した道路マッチング処理にて、始端候補リンクと終端候補リンクとを繋ぐ道路を探索しS410、探索された道路に対し道路単位の候補選定を行いS420、判定結果で絞り込みを行う430。そして、道路が一意に決定された場合S440:YES、マッチング結果を出力するS450。これにより、コアポイントに対応する地図データ上のリンクを抽出した後、当該リンクを結びつける道路を適切に抽出することができる。また、本実施形態では、道路単位の候補選定を行うのであるが図22中のS420、図26に示したように、コアポイントの属性のうちで道路形状に関わる属性である形状系の属性に基づき、道路を選定する。具体的には、属性CA/DCAで判定しS421、属性BR/DMBで判定しS422、属性PDで判定しS423、属性PDMS424で判定する。これにより、比較的簡単に道路を選定することが可能となる。さらにまた、本実施形態では、S410における道路の探索に際し、基本的には、始端候補リンクの両端点から終端候補リンクの両端点までの全ての組み合わせの中で道路を探索する。例えば図23aに示したように、始端側コアポイントをCPaとし、終端側コアポイントをCPbとし、CPaに対し抽出されたリンクをSLとし、CPbに対し抽出されたリンクをGLとする。このとき、始端候補リンクSLと終端候補リンクGLとの間の道路を探索する場合、リンクSLを構成する2つのノードSN1,SN2とリンクGLを構成する2つのノードGN1,GN2との全ての組み合わせを考える。具体的には、SN1→GN1、SN1→GN2、SN2→GN1、SN2→GN2を結ぶ道路を探索する。これにより、探索すべきリンクをもらさず探索することが可能となる。ただし、始端候補リンクや終端候補リンクが複数本ある場合など、S410の道路探索に要する時間が長くなる虞がある。そこで、本実施形態では、図23bに示したように、CPa-CPb間の道路推定の結果、リンクSL→CL→GL1という道路が推定されたものとする。このときは、CPbから次のCPへの道路推定を行う場合、リンクGL1からの道路を探索する。すなわち、候補リンクにリンクGL2があっても、リンクGL2からの道路探索を省略する。これにより、道路探索処理に要する時間を短くすることができる。また、本実施形態では、図23cに示したように、CPbが交差点である場合、交差点を示すノードGN2に対応付け可能であるため、リンクGLについては、一方のノードGN1に接続されるリンクだけを探索する。また、図23dに示したように、CPbが仮想CPである場合、パーセル境界上のノードGN2に対応付け可能であるため、リンクGLについては、一方のノードGN1に接続されるリンクだけを探索する。これにより、S410の道路探索に要する時間を短くすることができる。さらにまた、本実施形態では、図24aに示したように、ノードN1→N2→N3→N4という探索を最初に行ったものとし、ノードN1からの道路探索を2度目に行う場合、ノードN1→N5→N2という道路探索は行うが、ノードN2から先の探索は既に行っているため、ノードN2から先の探索は行わない。これにより、S410の道路探索に要する時間を短くすることができる。また、本実施形態では、図24bに示したように、CPaからCPbへ向かう方向を基準にして、ノードN1に接続されるリンクL1,L2,L3のうち角度a3が所定角度を越えている場合L3については、道路探索の対象から外す。これにより、S410の道路探索に要する時間を短くすることができる。さらにまた、本実施形態では、図24cに示したように、リンクL1の道路種別が国道であるため、ノードN1からの道路探索にあたり、道路種別が国道であるリンクL2を道路探索の対象にする。道路種別が県道であるリンクL3は、道路探索の対象から外す。これにより、S410の道路探索に要する時間を短くすることができる。ところで、S410にて道路を探索する場合、明らかに不適切なリンクを探索すると、処理に要する時間が長くなる虞がある。そこで、本実施形態では、図25aに示したようにCPa及びCPbのいずれもが属性PDを有している場合に、ノードN1からノードN2への道路を探索する際、形状補間点K1,K2,K3,K4,での累積距離を算出するようにする。そして、この累積距離が、PD値から一定値以上大きくなった場合、道路探索を中止する。これにより、明らかに不適切なリンクを探索する可能性が小さくなり、S410の道路探索に要する時間を削減することができる。また、本実施形態では、図25bに示したように、CPa-CPb間の直線距離とPDM値とを用い、破線で示すようなコ字状の距離を算出しておく。このとき、ノードN1からノードN2への道路を探索する際、形状補間点K1,K2,K3,K4,での累積距離を算出するようにする。そして、この累積距離が、破線で示される距離よりも一定値以上大きくなった場合に、道路探索を中止する。これにより、明らかに不適切なリンクを探索する可能性が小さくなり、S410の道路探索に要する時間を削減することができる。さらにまた、本実施形態では、図25cに示すように、ノードN1からノードN2への道路を探索する際、通過するノードN3,N4,N5,N6の個数を数えるようにする。そして、ノードの数が一定値以上となった場合に、道路探索を中止する。これにより、明らかに不適切なリンクを探索する可能性が小さくなり、S410の道路探索に要する時間を削減することができる。また、本実施形態では、図25dに示したようにCPa及びCPbのいずれもが交差点である場合、ノードN1,N2が交差点であれば、ノードN1,N2がそれぞれCPa,CPbに対応付け可能であるため、ノードN1,N2間の直線距離を予め算出しておく。そして、ノードN1からノードN2への道路を探索する際、通過するノードN3,N4,N5,N6までの累積距離を算出して、この累積距離が、予め算出したノードN1,N2間の直線距離よりも一定値以上大きくなった場合、道路探索を中止する。これにより、明らかに不適切なリンクを探索する可能性が小さくなり、S410の道路探索に要する時間を削減することができる。なお、始端側コアポイントから終端側コアポイントへ到る地図上の道路を推定する際、道路が一意に決定されない場合が生じ得る。そこで、本実施形態では、図32aに示したように、CPaからCPbへの道路を探索した結果、ノードN1→N4→N5→N2→N3という道路、及び、ノードN1→N4→N5→N2という道路の2つが残った場合、太線で示した道路ノードN1→N4→N5→N2は両方の道路に包含されている共通の部分であるため、この道路を一意に決定された道路とする。同様に、図32bでは、CPaからCPbへの道路を探索した結果、ノードN1→N4→N5→N2→N3という道路、及び、ノードN1→N4→N6→N5→N2→N3という道路の2つが残ったものとする。このとき、太線で示した道路ノードN1→N4N5→N2→N3は、両方の道路に包含されている共通の部分であるため、この分断された2つの道路を、一意に決定された道路とする。これにより、地図上の道路を適切に推定することができる。なお、本実施例におけるナビゲーション装置10が道路推定装置に相当し、地図データ入力装置13が地図データ入力手段に相当し、制御回路17のCPU17aがリンク抽出手段及び道路推定手段に相当する。また、図22の道路マッチング処理が道路推定手段の機能としての処理に相当し、図22中のS410の処理が道路探索処理に相当し、S420の処理が候補選定処理に相当する。以上、本発明は、上述した実施形態に何ら限定されるものではなく、その要旨を逸脱しない範囲において種々なる形態で実施可能である。例えば、図32bに示した例では、道なりの道路N1→N4→N5→N2→N3という道路を、始端側コアポイントから終端側コアポイントへ到る地図上の道路として推定するようにしてもよい。道なりとは、図32cに示すように、リンク同士のなす角度例えば記号aで示す角度が所定角度例えば15度以下である場合をいう。このようにすれば、地図上の道路を適切に推定することができる。また例えば、道路マッチング処理図22中のS410~S450において、始端側候補リンクと、終端側候補リンクを接続するリンクを探索する際、属性情報を使用する場合は、始端側コアポイントの属性情報を優先的に使用するようにしてもよい。これは道路区分や形状の変化が始端側から終端側へと道路に沿って発生することを考慮している。このように始端側コアポイントの属性を優先して絞り込みに使用することで、隣接するコアポイント間で、万一道路区分や形状の変化があったとしても計算量、処理時間等を削減できる。"