JPH10124674A - 地図マッチング装置 - Google Patents

Abstract

(57)【要約】 【課題】 読み取り誤差、デジタル化誤差、および道路
の整備量の差によって生じる道路の分岐によるネットワ
ークの変形に対しても安定にマッチングを行なうことが
できる地図マッチング装置を提供すること。 【解決手段】 特徴抽出部１０４、マッチング候補生成
部１０５、類似度計算部１０６、マッチング部１０７、
および微小領域マッチング制御部１０８を設け、地図デ
ータ中の道路の特徴を抽出してマッチングの対象となる
道路の組を探し、また前記マッチングの対象候補のそれ
ぞれについて類似度を計算し、その結果に基づいて道路
の組が同一の道路であるか否かを判断し、さらにマッチ
ングできなかった道路について微小領域毎にマッチング
をやり直すようにしたため、スキャナによる読み取りの
誤差およびデジタル化の際の誤差などに対しても安定に
マッチングを行なうことができる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、スキャナ等で読み込ん
だ後にベクトル化された地図データあるいは航空写真お
よび衛星写真を基にしてベクトル化された地図データを
管理する地図データ管理装置のうち、同一地域の地図の
年度版の更新の際に差分あるいは一致分を検出する必要
があるもの、前記地図データ管理装置が管理する地図デ
ータを基に編集作業を行なって複数の版の地図データが
生成された場合に互いの差分あるいは一致分を検出する
必要があるものに対してマッチングをとる地図マッチン
グ装置に関するものである。

【０００２】

【従来の技術】最近、カーナビゲーションシステムの普
及が進んでいる。カーナビゲーションシステムでは、車
に搭載されたＣＲＴ上に現在地の地図、目的地の地図、
あるいは任意の指定した地点の地図を表示することがで
きる。この地図は車載ナビゲーションシステムのＣＤ−
ＲＯＭ、ハードディスク、またはＩＣカード等に内蔵さ
れているのが一般的である。そしてこの車載ナビゲーシ
ョンシステム用地図は、一般に別の地図データベースか
ら生成される。別の地図データベースとは、例えば
（財）日本デジタル道路地図協会が２５０００分の１の
地形図を基に作成したデジタル道路地図データベースで
ある。このデジタル道路地図 データベースは１年毎に
（財）日本デジタル道路地図協会によって更新されてい
る（以下では年度版更新と呼ぶ）が、ナビゲーションシ
ステムの地図製作者はナビゲーションシステムのユーザ
に、より正確な地図を提供するために随時デジタル道路
地図データベースを補足・修正していく必要がある。こ
のため年度版更新時には、（財）日本デジタル道路地図
協会が提供するデジタル道路地図データベースと、ナビ
ゲーションシステムの地図製作者が補足・修正したデジ
タル道路地図データベースとの間には相違点が生じる。
したがって両者の違いを吸収してより正確な地図を作成
するために両者の地図の対応を取る必要がある。

【０００３】またカーナビゲーションシステムに対する
要求として、従来の２５０００分の１の道路地図だけで
なく、２５００分の１都市計画図に基づいたデジタル道
路地図を利用することによる高精度な位置情報の提供な
らびに高精度な経路案内がある。そのためには、従来の
２５０００分の１の道路地図と２５００分の１の都市計
画図に基づいたデジタル道路地図との対応を取る必要が
ある。

【０００４】このようなデータベース間の道路の対応
を、地図マッチング装置により取るための従来技術とし
ては、例えば特開平７−１２９７４０公報に示されたも
のがある。この従来技術においては、図１７のような構
成の地図マッチング装置を用いて、図１８のような処理
を用いて実現している。図１７および図１８を用いて従
来の地図データのマッチング装置の説明を行なう。図１
７において、２は地図データを記憶しておくためのメモ
リ、３は２に記憶されている地図とは異なる方法で作成
された地図データを記憶しておくためのメモリ、４は２
および３に記憶された地図データを比較するための比較
部、５は比較部４によって対応付けられた道路の対応テ
ーブルを記憶するためのメモリ、および６は比較部４を
制御する制御部である。

【０００５】図１８は前記従来の地図マッチング装置に
おける比較部４の概略動作を説明するための図である。
比較部４は、最初にリンク群を対応付け、次に対応付け
られたリンク群に含まれるノードを対応付け、その後に
対応テーブルを作成する、という処理からなっている。
さらに図１９に示すフローチャートを用いて、リンク群
の対応付けに関する説明を行なう。前記従来技術の実施
例では、２５０００分の１のデジタル道路地図を基にし
た標準データベースと２５００分の１都市計画図を基に
した専用データベースの対応付けという問題になってい
るが、本発明と同値の問題であると考えて差し支えな
い。Ｓ１では対応付けを行なう道路種別を１個だけ選択
する。Ｓ２では標準データベース中の出発点となるノー
ドを１個選択する（ａ１とする）。Ｓ３では専用データ
ベース中において、Ｓ２において選択されたノードと近
いノードを探す（ｂ１とする）。Ｓ４、Ｓ５ではａ１に
接続しているリンク群（ａ１，ａ２，．．．，ａｎとす
る）と、ｂ１に接続しているリンク群とでその方向がほ
ぼ同じ角度であるもの（ｂ１，ｂ２，．．．，ｂｎとす
る）を組で選択する。Ｓ６ではそれらのリンク群の終点
ａｎ，ｂｎの座標値を比較する。その座標値が一致して
いる場合には、Ｓ１０へ進みリンク群を対応させる。不
一致である場合には、Ｓ７においてａｎからリンクｂ
１，ｂ２，．．．，ｂｎまでの垂直距離ｒを計算し、そ
れが予め定めたしきい値より小さい場合にはＳ１０に進
み、大きい場合にはＳ９へ進み対応がつかなかったもの
とする。

【０００６】

【発明が解決しようとする課題】しかし、以上のような
方法では以下のような課題を有していた。２５０００分
の１と２５００分の１の地図のような、縮尺が異なる２
つの地図データの場合、整備されている道路の量（すな
わちリンクの本数）も異なり、２５００分の１地図の方
が充実しているため、２５０００分の１では一本の道路
リンク群として抽出できるものが、２５００分の１では
途中に分岐があったりして１本の道路リンク群として抽
出することはできず短いリンク群になり、その結果リン
ク群の対応付けに失敗する場合が生じる。なお、リンク
が分岐する地点でリンク群を分けない場合には、一般の
道路ネットワークにおいては、同一の道路種別であって
もリンクの分岐および閉路があるために、リンク群とし
て抽出されるリンクの組合せは非常に大きくなり、実際
的なアルゴリズムには適さない方法となる。

【０００７】本発明は前記問題点に鑑みてなされたもの
で、その目的は、２個のノードで接続されるリンクを線
分で近似し、その特徴量を抽出して作成する特徴空間中
において近傍に存在する２個の点をマッチングの候補と
して生成し、それらの類似度を計算し、さらにマッチン
グに失敗した道路に関しては再度微小領域でマッチング
を行なうことで、スキャナによる読み取りの誤差、デジ
タル化の際の誤差、および道路の整備量の差によって生
じる道路の分岐によるネットワークの変形に対しても安
定にマッチングを行なうことができる地図マッチング装
置を提供することである。

【０００８】また、本発明の別の目的は、道路の属性お
よび識別子が一致するという条件によってマッチングの
候補を減らし、これによって探索空間を小さくして効率
の良いマッチングを行なうことができる地図マッチング
装置を提供することである。

【０００９】

【課題を解決するための手段】本発明は、地図マッチン
グ装置として、ノードとリンクによって道路を表現する
地図データを格納する地図データ格納装置と、前記地図
データ格納装置に格納された任意の地図を指定するため
の地図データ指定部と、前記地図データ格納装置に格納
された地図データを読み出す地図データ読み出し部と、
前記地図データ読み出し部によって読み出された地図デ
ータ中の道路の特徴を抽出する特徴抽出部と、前記特徴
抽出部によって抽出された道路の特徴を用いて地図デー
タ中からマッチングの対象となる道路の組を探すマッチ
ング候補生成部と、前記マッチング候補生成部によって
生成された前記マッチングの対象候補のそれぞれについ
て類似度を計算する類似度計算部と、前記類似度計算部
に よって計算された類似度に基づいて道路の組が同一
の道路であるか否かを判断するマッチング部と、マッチ
ングできなかった道路についてのみ微小領域毎にマッチ
ングをやり直す微小領域マッチング制御部と、地図デー
タの前処理を行なう前処理部とを設けたものである。

【００１０】本発明は上記構成により、前記地図データ
格納装置に２種類以上の異なる地図データを格納してお
き、格納されている任意の２種類の地図データの中のそ
れぞれから同一地域を表す任意の１枚づつ合計２枚の地
図をマッチングすべき地図として地図データ指定部を用
いて指定する。そして、当該地図に含まれる道路を互い
にマッチングを行なう場合に、前記特徴抽出部におい
て、当該地図に含まれるすべての道路のリンクについて
各々のリンクを構成する両端のノードを結ぶ線分を当該
リンクの近似とする。また、当該地図毎に予め定めた座
標原点から当該リンクの近似線分もしくはその線分の延
長上に下ろした垂線が当該地図毎に予め定めた座標軸と
なす角度を第１の特徴として抽出し、前記座標原点から
当該リンクの近似線分もしくはその線分の延長上に下ろ
した垂線の足までの距離を第２の特徴として抽出し、前
記マッチング候補生成部において前記第１および第２の
特徴を角度−距離空間に特徴点としてマッピングを行な
う。また、当該マッチングの対象となっている２枚の地
図のそれぞれから抽出された特徴点の組のうち、前記角
度−距離空間において予め定めた大きさの近傍に入る特
徴点の集合をマッチングの対象として生成する。そし
て、前記類似度計算部において、当該対象集合に含まれ
るそれぞれの特徴点の組に関して特徴を計算する元とな
った前記道路のリンクの線分近似を用いて、２本の近似
線分のそれぞれの２個の端点からもう一方の近似線分も
しくは近似線分の延長上に垂線を下ろし、それぞれの垂
線の長さ、垂線の足の位置から線分の端点までの長さを
用いて類似度を計算する。さらに、この計算によって得
られた類似度を用いて前記マッチング部において道路の
マッチングを判定し、マッチングに失敗した道路につい
ては前記微小領域マッチング制御部によって道路を微小
領域に分割し、前記特徴抽出部、前記マッチング候補生
成部、前記類似度計算部、および前記マッチング部の処
理を再度行なう。また、前記地図データ管理装置中に格
納されているマッチング対象となる２枚の地図データに
関して、道路のリンクが少なくとも１種類以上の互いに
共通な属性を持ち、かつそれぞれリンクの前記共通な種
類の属性に値がつけられている場合に、当該地図に含ま
れる前記道路のリンクにつけられた前記共通な種類の属
性の値が一致するものをマッチングの候補として生成
し、地図マッチングを行なう。さらに、前記道路のノー
ドのそれぞれに一意に識別子がつけられ、さらに前記道
路のリンクのそれぞれが当該リンクの両端のノードの前
記識別子によって識別可能となる地図データが格納され
ている場合に、当該マッチング対象地図に含まれる前記
道路のリンクの識別子を用いて同一であると判定する。
これによって、地図から前記リンクの識別子が一致した
道路のリンクを取り除いて地図マッチングを行なうこと
で、スキャナによる読み取りの誤差およびデジタル化の
際の誤差などに対しても安定にマッチングを行ない、か
つマッチングの候補を減らすことによって探索空間を小
さくして効率的にマッチングを行なうことができる。

【００１１】

【発明の実施の形態】本発明の請求項１記載の発明は、
ノードとリンクによって道路を表現する地図データを格
納する地図データ格納装置と、前記地図データ格納装置
に格納された任意の地図を指定するための地図データ指
定部と、前記地図データ格納装置に格納された地図デー
タを読み出す地図データ読み出し部と、前記地図データ
読み出し部によって読み出された地図データ中の道路の
特徴を抽出する特徴抽出部と、前記特徴抽出部によって
抽出された道路の特徴を用いて地図データ中からマッチ
ングの対象となる道路の組を探すマッチング候補生成部
と、前記マッチング候補生成部によって生成された前記
マッチングの対象候補のそれぞれについて類似度を計算
する類似度計算部と、前記類似度計算部によって計算さ
れた類似度に基づいて道路の組が同一の道路であるか否
かを判断するマッチング部と、マッチングできなかった
道路について微小領域毎にマッチングをやり直す微小領
域マッチング制御部と、地図データの前処理を行なう前
処理部とを備えた構成にしたものであり、スキャナによ
る読み取りの誤差およびデジタル化の際の誤差などに対
しても安定にマッチングを行なうという作用を有する。

【００１２】本発明の請求項２記載の発明は、ノードと
リンクによって道路を表現する地図データを格納する地
図データ格納装置と、前記地図データ格納装置に格納さ
れた任意の地図を指定するための地図データ指定部と、
前記地図データ格納装置に格納された地図データを読み
出す地図データ読み出し部と、前記地図データ読み出し
部によって読み出された地図データ中の道路の特徴を抽
出する特徴抽出部と、前記特徴抽出部によって抽出され
た道路の特徴を用いて地図データ中からマッチングの対
象となる道路の組を探すマッチング候補生成部と、前記
マッチング候補生成部によって生成された前記マッチン
グの対象候補のそれぞれについて類似度を計算する類似
度計算部と、前記類似度計算部によって計算された類似
度に基づいて道路の組が同一の道路であるか否かを判断
するマッチング部と、マッチングできなかった道路につ
いてのみ微小領域毎にマッチングをやり直す微小領域マ
ッチング制御部とを具備する構成としたものであり、地
図データ格納装置に２種類以上の異なる地図データを格
納しておき、格納されている任意の２種類の地図データ
の中のそれぞれから同一地域を表す任意の１枚づつ合計
２枚の地図をマッチングすべき地図として地図データ指
定部を用いて指定し、当該地図に含まれる道路を互いに
マッチングを行なう場合に、前記特徴抽出部において、
当該地図に含まれるすべての道路のリンクについて各々
のリンクを構成する両端のノードを結ぶ線分を当該リン
クの近似とし、当該地図毎に予め定めた座標原点から当
該リンクの近似線分もしくはその線分の延長上に下ろし
た垂線が当該地図毎に予め定めた座標軸となす角度を第
１の特徴として抽出し、前記座標原点から当該リンクの
近似線分もしくはその線分の延長上に下ろした垂線の足
までの距離を第２の特徴として抽出し、前記マッチング
候補生成部において前記第１および第２の特徴を角度−
距離空間に特徴点としてマッピングを行ない、当該マッ
チングの対象となっている２枚の地図のそれぞれから抽
出された特徴点の組のうち、前記角度−距離空間におい
て予め定めた大きさの近傍に入る特徴点の集合をマッチ
ングの対象として生成し、前記類似度計算部において、
当該対象集合に含まれるそれぞれの特徴点の組に関して
特徴を計算する元となった前記道路のリンクの線分近似
を用いて、２本の近似線分のそれぞれの２個の端点から
もう一方の近似線分もしくは近似線分の延長上に垂線を
下ろし、それぞれの垂線の長さ、垂線の足の位置から線
分の端点までの長さを用いて類似度を計算し、前記類似
度を用いて前記マッチング部において道路のマッチング
を判定し、マッチングに失敗した道路については前記微
小領域マッチング制御部によって道路を微小領域に分割
し、前記特徴抽出部、前記マッチング候補生成部、前記
類似度計算部、および前記マッチング部の処理を再度行
なうことにより、スキャナによる読み取りの誤差および
デジタル化の際の誤差などに対しても安定にマッチング
を行なうという作用を有する。

【００１３】本発明の請求項３記載の発明は、請求項１
または２記載の地図マッチング装置において、地図デー
タ読み出し部によって読み出された地図データの前処理
を行なう前処理部を備えたものであり、探索空間を小さ
くして効率的にマッチングを行なうことができるという
作用を有する。

【００１４】本発明の請求項４記載の発明は、請求項２
記載の地図マッチング装置において、前記地図データ管
理装置中に格納されているマッチング対象となる２枚の
地図データに関して、道路のリンクが少なくとも１種類
以上の互いに共通な属性を持ち、かつそれぞれリンクの
前記共通な種類の属性に値がつけられている場合につい
て、前記マッチング候補生成部において、マッチングの
対象となっている２枚の地図のそれぞれから抽出された
特徴点の組のうち、前記角度−距離空間において予め定
めた大きさの近傍に入る特徴点の集合をマッチングの対
象とする候補生成方法に加えて、当該地図に含まれる前
記道路のリンクにつけられた前記共通な種類の属性の値
が一致するものをマッチングの候補として生成し、地図
マッチングを行なうようにしたものであり、マッチング
の候補を減らし、探索空間を小さくして効率的にマッチ
ングを行なうことができるという作用を有する。

【００１５】本発明の請求項５記載の発明は、請求項３
記載の地図マッチング装置において、前記道路のノード
のそれぞれに一意に識別子がつけられ、さらに前記道路
のリンクのそれぞれが当該リンクの両端のノードの前記
識別子によって識別可能となる地図データが格納されて
いる前記地図データ格納装置と、前記マッチングの対象
となっている２枚の地図に対して、当該地図に含まれる
前記道路のリンクの識別子を用いて同一であると判定す
ることによって、地図から前記リンクの識別子が一致し
た道路のリンクを取り除く前処理部とを具備し、前記地
図データに対する編集操作によって異なる版の地図が１
個以上作成された場合に、マッチングの対象となってい
る版が異なる地図のそれぞれからリンク番号を取り除い
て地図マッチングを行なうようにしたものであり、マッ
チングの候補を減らし、探索空間を小さくして効率的に
マッチングを行なうことができるという作用を有する。

【００１６】以下、本発明の各実施の形態を図面を参照
して説明する。図１は本発明の各実施の形態に係る地図
マッチング装置が組み込まれる地図管理装置の構成を示
すブロック図である。そして、図１中の全体を囲む枠１
１０は上記地図管理装置の全体構成を示し、また点線で
囲まれた部分１００は本発明の第１および第２の実施の
形態における地図マッチング装置の全体構成を示すブロ
ック図である。

【００１７】（実施の形態１）以下、本発明の第１の実
施の形態について詳細に説明する。図１において、符号
１０１はノードとリンクによって道路を表現する地図デ
ータを格納する地図データ格納装置であり、１種類以上
の地図データをそれぞれ１枚以上格納することが可能で
ある。１０２は地図データ指定部であり、地図データ格
納装置１０１に格納されている任意の地図データを指定
する。１０３は地図データ読み出し部であり、地図デー
タ指定部１０２によって指定された任意の地図データを
読み出す。１０４は特徴抽出部であり、地図データ読み
出し部１０３によって読み出された地図データの道路の
特徴を抽出する。１０５はマッチング候補生成部であ
り、特徴抽出部１０３によって抽出された道路の特徴を
用いてマッチングの対象となる道路の組を候補として選
び、候補の集合を作成する。１０６は類似度計算部であ
り、マッチング候補生成部１０５によって生成されたマ
ッチングの候補の集合の一つ一つに対して、類似度を計
算する。１０７はマッチング部であり、類似度計算部１
０６によって計算された類似度に基づいて、マッチング
候補生成部１０５が生成した道路の組がマッチングして
いるかを決定する。

【００１８】図２は本発明が取り扱う地図データの例で
ある。図２において□印の地点が道路のノードであり、
２個のノードを接続する線分の集まりが道路のリンクで
ある。○及び×印はリンクの形状を表現するための補間
点である。地図データ格納装置１０１は、このような地
図データを格納する。地図データは道路がノードとリン
クによって表現されているのであれば、縮尺、格納フォ
ーマット、およびデータ整備の状況が異なっていても良
いことは言うまでもない。また格納単位は、その地図デ
ータが表す位置が判るのであれば、図葉単位あるいは図
葉をいくつかの断片に分割した単位であっても良いこと
は言うまでもない。

【００１９】かかる構成を有する地図マッチング装置１
００による地図マッチング動作について説明する。図３
は本実施の形態に係る地図マッチング装置の動作を説明
するフロー図である。この地図マッチング装置の処理動
作が開始されると、地図データ指定部１０２は、地図デ
ータ格納装置１０１に格納された地図データの中から、
同一地域を表現する２枚の地図を指定する（ステップＳ
Ｔ１）。この地図の指定に関しては、キーボードから地
図データのファイル名等を入力する、メニューなどの一
覧表示から選択する、および地図データファイルの名称
あるいは地図データに格納されている地域を示すデータ
をプログラムで読み取ることで自動的に選択する等、種
々の方法によって指定することができることは言うまで
もない。地図データ読み出し部１０３は、地図データ指
定部１０２によって指定された２枚の地図を読み出し
て、特徴抽出部１０４に渡す。

【００２０】特徴抽出部１０４は、「投影法の統一」、
「座標系の統一」「リンクの線分近似」の３段階の処理
を行なう。まず上記読み出した２枚の地図の投影法が異
なっているか否かをチェックし（ステップＳＴ２）、地
図データ読み出し部１０３によって読み出された２枚の
地図の投影法が異なっている場合は投影法の統一の処理
を行なう（ステップＳＴ３）。投影法の統一は２枚の地
図のうちの一方に合わせても良いし、どちらとも異なる
別の投影法に合わせても良いことは言うまでもない。次
に、上記投影法の統一がとられた後は、２枚の地図の座
標系が異なっているか否かをチェックし（ステップＳＴ
４）、座標系が異なっている場合は座標系の統一の処理
が行なわれる（ステップ５）。この座標系の統一処理も
２枚の地図のうちの一方に合わせても良いし、どちらと
も異なる別の座標系に合わせても良いことは言うまでも
ない。なおステップＳＴ２において２枚の地図間ではじ
めから投影法が一致していた場合はステップＳＴ３の投
影法の統一処理は行なわずにステップＳＴ４の処理へ移
行する。同じく、ス テップＳＴ４において２枚の地図
間ではじめから座標系が一致していた場合はステップＳ
Ｔ５の座標系の統一処理は行なわずに次のステップＳＴ
６の処理へ移行する。本実施の形態の説明においては、
簡単のために直交座標系で横軸をＸ軸、縦軸をＹ軸と
し、マッチング対象の２枚の地図が表現する地域の中
で、Ｘ軸方向の最小地点およびＹ軸方向の最小地点を原
点とする。

【００２１】ここで、図４および図５を用いて特徴抽出
部１０４の処理動作内容をさらに説明する。図４におけ
るノードＡ１とノードＡ２を接続するリンク（Ａ１−Ａ
２）について説明する。リンクＡ１−Ａ２はノードＡ１
と補間点ａ１、ａ２、ａ３、ａ４、ａ５、ａ６、ａ７お
よびノードＡ２を結ぶ線分によって構成されている。こ
のように補間点によってリンクの形状が表現できるので
あるが、微小線分Ａ１−ａ１を表現する線分の方程式を
考えると、紙地図自体の誤差およびデジタル化誤差等に
よって安定した方程式を求めることは困難である。一方
ノードＡ１とノードＡ２を結ぶ線分の方程式を考える
と、微小線分Ａ１−ａ１と比較して、距離が長いために
相対的な誤差が減っていると考えられる。そこで本発明
では図４の破線で示したように、リンクを表現するため
にノードＡ１−Ａ２を直接結ぶ線分を作成しこれを近似
線分として使用する（ステップＳＴ６）。

【００２２】次に近似線分Ａ１−Ａ２の特徴抽出につい
て図５を用いて説明する。図５はＸＹ直交座標系中にお
いた近似線分Ａ１−Ａ２である。原点Ｏから近似線分Ａ
１−Ａ２またはその延長上に垂線を下ろしその足をＲと
する。線分ＯＲがＸ軸となす角度θとする。ここではＸ
軸正方向を０として反時計回り方向を正方向とする。ま
た線分ＯＲの長さをρとする。点Ａ１、Ａ２を結ぶ直線
の方程式は、θおよびρを用いることで、 Ｘｃｏｓθ＋Ｙｓｉｎθ＝ρ と表現される。直線の方程式はａ，ｂを係数として、 Ｙ＝ａＸ＋ｂ （ただしＹ軸に平行な直線は除く）としても表現可能で
あるが、２本の直線の方程式の係数ａ、ｂが互いに近い
ことに直観的な物理的意味を見い出しにくい。一方θ，
ρによる表現では、２本の直線のθが近いことは直線の
傾きが近いことを意味し、ρが近いことは原点から直線
までの距離が近いことを意味する。このように特徴抽出
部１０４は、２本の道路を誤差に対して安定した方程式
で表現するために、リンクのノードを結ぶ線分を近似と
して使用し、また線分が載る直線の方程式として物理的
な距離の近さを表現できるθ、ρを特徴として抽出す
る。

【００２３】特徴抽出部１０４はすべてのリンクに関し
て、それぞれのリンクの両端のノードのＸＹ座標値と線
分Ａ１−Ａ２を表現するθ、ρ値を計算して地図毎の特
徴集合に保存する（ステップＳＴ７）。図６の地図Ａと
地図Ｂは同じ地域を表す地図であり、説明の簡略化のた
めにほとんどの道路を省略している。地図Ａと地図Ｂと
では、紙地図を読み込む際のスキャナの特性或いはデジ
タル化する際の誤差によってずれが生じている。マッチ
ング候補生成部１０５は、地図毎の特徴集合からそれぞ
れ１個づつの要素を取り出して角度−距離空間としての
θ−ρ空間で近いものの組を作成してマッチング候補の
集合に入れる（ステップＳＴ８）。θ−ρ空間で近いも
のとは、角度と距離の差が設定値より小さいということ
を意味する。図７はこのθ−ρ空間で近いものというこ
とを説明する図であり、地図Ａ中および地図Ｂ中のすべ
ての道路をθ−ρ空間にマッピングした図である。図６
中における地図Ａ中のリンクＡ１−Ａ２の特徴量（θ
１，ρ１）および地図Ｂ中のリンクＢ１−Ｂ２の特徴量
（θ２，ρ２）を図７にマッピングするとＬ１、Ｌ２と
なり、θ−ρ空間では近い位置にある地図Ａ、地図Ｂの
リンクの組をマッチングの候補として生成し、各ノード
のＸＹ座標値とともに次の類似度計算部１０６に渡す。
ここでＬａ−Ｌｂ間の距離は、例えばユークリッド距離
であるが、（θａ，ρａ）および（θｂ，ρｂ）から計
算できるものであれば拘らないことは言うまでもない。

【００２４】類似度計算部１０６は、マッチング候補の
集合に入っている地図Ａ、地図Ｂのリンクの組を１個づ
つ取り出して（ステップＳＴ９）、なくなるまで以下の
ステップの処理を繰り返す。すなわち、それぞれの組の
類似度を計算する。図８は類似度の計算方法を表す図で
ある。この図において、マッチング対象である２枚の地
図をそれぞれ地図Ａ、地図Ｂとし、マッチング候補の道
路の組として地図Ａからは近似線分Ａ１−Ａ２が選ば
れ、また地図Ｂからは近似線分Ｂ１−Ｂ２が選ばれたも
のとする。２本の近似線分それぞれについて、その線分
の端点（すなわちノード）からもう一方の線分または線
分の延長上に垂線を下ろす（ステップＳＴ１０）。図８
では、ノードＡ１から線分Ｂ１−Ｂ２側へ下ろした垂線
をＡ１−Ｂａ１、ノードＡ２から線分Ｂ１−Ｂ２側へ下
ろした垂線をＡ２−Ｂａ２、ノードＢ１から線分Ａ１−
Ａ２側へ下ろした垂線をＢ１−Ａｂ１、およびノードＢ
２から線分Ａ１−Ａ２側へ下ろした垂線をＢ２−Ａｂ２
としている。次に、上のようにして求めた垂線につい
て、それぞれの垂線の長さ、近似線分の端点から垂線の
足までの距離を求め類似度を計算する（ステップＳＴ１
１）。すなわち、線分Ａ１−Ａ２の長さ、および線分Ｂ
１−Ｂ２の長さをそれぞれＬａ，Ｌｂとする。Ａ１−Ａ
ｂ１の長さをＥａ、Ａｂ１−Ａ２の長さをＭａ、Ｂ１−
Ｂａ２の長さをＭｂ、およびＢａ２−Ｂ２の長さをＥｂ
とする。また垂線Ａ１−Ｂａ１、Ａｂ１−Ｂ１、Ａ２−
Ｂａ２、およびＡｂ２−Ｂ２の長さをそれぞれＤａ１−
ｂ、Ｄｂ１−ａ、Ｄａ２−ｂ、Ｄｂ２−ａとする。Ｍ
ａ、Ｍｂはそれぞれ線分Ａ１−Ａ２が線分Ｂ１−Ｂ２と
一致した長さ、および線分Ｂ１−Ｂ２が線分Ａ１−Ａ２
と一致した長さとする。またＥａ，Ｅｂはそれぞれ線分
Ａ１−Ａ２が線分Ｂ１−Ｂ２と一致しなかった長さ、線
分Ｂ１−Ｂ２が線分Ａ１−Ａ２と一致しなかった長さと
する。

【００２５】図９は別の候補の場合の類似度の計算を説
明する図である。この場合には、図８における一致した
長さを表すＭａおよびＭｂがＭａ＝Ｍｂ＝０である。ま
た不一致である長さを表すＥａ、ＥｂについてはＥａ＝
Ｌａ、Ｅｂ＝Ｌｂである。垂線の長さに関しては図８と
同じである。図１０はさらに別の候補に関する類似度計
算を説明する図である。線分Ａ１−Ａ２に関しては、線
分Ｂ１−Ｂ２と一致した長さはＭａ、不一致である長さ
が（Ｅａ１＋Ｅａ２）となる。また線分Ｂ１−Ｂ２に関
しては、線分Ａ１−Ａ２と一致した長さがＭｂ＝Ｌｂで
あり、不一致の長さがＥｂ＝０である。垂線の長さに関
しては図８と同じである。類似度計算部１０６は、マッ
チングの候補のすべてについて、それぞれの線分の長さ
Ｌ、一致度Ｍ、不一致度Ｅ、距離Ｄを計算してマッチン
グ部１０７に送る。

【００２６】図１１、図１２、および図１３はさらに別
の候補の類似度計算を説明するための図である。図１１
において、地図Ｂ中のノードＢ２、Ｂ３は地図Ａ中のノ
ードＡ２に対応するものであるが、ノード付近のリンク
の形状をより正確に表現したためにクランク状になって
いる。また図１２において、地図Ｂ中のリンクＢ１−Ｂ
２は地図Ａ中のリンクＡ１−Ａ２に対応するものである
が、地図Ｂ中ではリンクＢ３−Ｃが追加されたためにリ
ンクＢ１−Ｂ２はリンクＢ１−Ｂ３とリンクＢ３−Ｂ２
に分割されている。図１１および図１２に示したリンク
の場合でも、マッチング候補生成部１０４によってθ−
ρ空間では近傍にマッピングされ、類似度計算部１０５
によって処理される。

【００２７】類似度計算部１０５では、リンクＡ１−Ａ
２とリンクＢ１−Ｂ３との間の類似度およびリンクＡ１
−Ａ２とリンクＢ３−Ｂ２との間の類似度が計算され
る。そして最終的には図１３に示すように、リンクＡ１
−Ａ２がリンクＢ１−Ｂ３およびリンクＢ３−Ｂ２と一
致した長さＭａ、リンクＢ１−Ｂ３がリンクＡ１−Ａ２
と一致した長さＭｂ１、およびリンクＢ３−Ｂ２がリン
クＡ１−Ａ２と一致した長さＭｂ２、リンクＡ１−Ａ２
の不一致部分の長さＥａ、リンクＢ３−Ｂａ２の不一致
部分の長さＥｂ２、およびリンク間の距離Ｄａ１−ｂ、
Ｄｂ１−ａ、Ｄｂ３−ａ、Ｄａ２−ｂ、およびＤｂ２−
ａが計算される。

【００２８】マッチング部１０７は、類似度計算部１０
６において計算された類似度を用いて、マッチングの候
補である２本の道路の組がマッチングしているかを決定
する。マッチングの決定のための計算は、類似度計算部
１０６において計算された前記線分の長さＬ、一致度
Ｍ、不一致度Ｅ、距離Ｄの値、および別途定めたしきい
値あるいは定数値を使用して得られる数式、条件式、論
理式およびそれらの式の組合せならば何でも良いことは
言うまでもない。すなわち、類似度計算部１０６におい
て計算された類似度があらかじめ定めたしきい値を満た
しているか否かをチェックする（ステップＳＴ１２）。
例えば図８の場合についてみると、 （Ｍａ÷Ｌａ≧０．９ ＡＮＤ Ｍｂ÷Ｌｂ≧０．９
ＡＮＤ Ｄａ１−ｂ≦１０ ＡＮＤ Ｄｂ１−ａ≦１０ ＡＮＤ
Ｄｂ２−ａ≦１０ ＡＮＤ Ｄａ２−ｂ≦１０） が成立する時、マッチングしているものとする。

【００２９】そして、ステップＳＴ１２において類似度
があらかじめ定めたしきい値を満たしている場合はその
組はマッチングしていると判断されマッチング成功リス
トに入れる（ステップＳＴ１３）。他方、類似度があら
かじめ定めたしきい値を満たしていない場合はその組は
マッチング不成功と判断されマッチング不成功のデータ
のリストに入れる（ステップＳＴ１４）。次にマッチン
グ候補の集合が空か否かをチェックし（ステップＳＴ１
５）、マッチング候補の集合が空でなければステップＳ
Ｔ９の処理に戻る。

【００３０】他方、マッチング候補の集合が空である場
合は、微小領域マッチング制御部１０８は、前記マッチ
ング部１０７によってマッチングできなかった道路のみ
を再度マッチングする。このとき微小領域マッチング制
御部１０８は、マッチング不成功リストに入れられた組
をそのリストから１個づつ取り出してそのデータのリス
トが空か否かをチェックし（ステップＳＴ１６）、空で
あれば一連の地図マッチング処理動作を終了する。他
方、マッチングに不成功のデータのリウトが空でないと
判断された場合は微小マッチングの処理を行なう（ス
テップＳＴ１７）。

【００３１】図１４は、この微小マッチングの処理に際
しての、微小領域マッチング制御部の動作を説明する図
である。図１４に示した事例は図１２に示した事例と類
似した場合であるが、リンクＡ１−Ａ２の本来の形状が
近似線分と大きく異なっている場合に、リンクＢ３−Ｃ
が追加されたものである。この場合には、特徴抽出部１
０４が地図Ａ中の近似線分Ａ１−Ａ２から抽出する特徴
（θａ，ρａ）と、特徴抽出部１０４が地図Ｂ中の近似
線分Ｂ１−Ｂ３および近似線分Ｂ３−Ｂ２から抽出する
特徴（θｂ１，ρｂ１）および（θｂ２，ρｂ２）
は、マッチング候補生成部１０５によってθ−ρ空間に
マッピングされた際に大きく離れてしまいマッチングの
候補とされない場合が多い。微小領域マッチング制御部
１０８は、このような道路に対して「補間点単位の微小
リンク表 現」を行なった後に再度特徴抽出部１０４以
下の処理を適用する。図１５は図１４における道路の補
間点を表現したものである。微小領域マッチング制御部
１０８は、図１５の補間点をすべてノードと見なすこと
によって、図１６に示すように、地図Ａからは微小リン
クＡ１−ａ１、ａ１−ａ２、ａ２−ａ３、ａ３−ａ４、
ａ４−Ａ２を取り出し、地図Ｂからは微小リンクＢ１−
ｂ１、ｂ１−ｂ２、ｂ２−Ｂ３、Ｂ３−ｂ３、ｂ３−ｂ
４、ｂ４−Ｂ２を取り出し、これらを特徴抽出部１０４
に渡して再度同様の処理を行なう。

【００３２】（実施の形態２）次に、本発明の第２の実
施の形態について詳細な説明する。地図データ格納装置
１０１に格納されているマッチングの対象となる２枚の
地図データにおいて、両者の地図中の道路に共通な種類
の属性がつけられており、かつその属性値の一致・不一
致が比較可能である場合には、マッチング候補生成部１
０５においてθ−ρ空間の近傍にあって、かつ前記属性
の属性値が一致するもののみをマッチング候補として生
成する。本実施の形態で使用している道路の属性には、
道路種別、リンク種別である。道路種別の属性値には、
高速自動車国道、都市高速道路、国道、主要地方道路
（都道府県道）、主要地方道路（指定都市道）、一般都
道府県道、指定市の一般市道、その他（５．５ｍ以上道
路）、その他（３．０ｍ以上５．５ｍ未満道路）、およ
び未調査がある。本実施の形態で使用しているリンク種
別の属性値には、本線（上下線非分離）リンク、本線
（上下線分離）リンク、連結路（本線間の渡り線）リン
ク、交差点内リンク、連結路（ランプ）リンク、本線と
同一路線の側道リンク、サービスエリア等側道リンク、
自転車道等リンク、および未調査である。マッチング候
補生成部１０５以外の動作は第１の実施の形態と同じで
ある。

【００３３】（実施の形態３）次に第３の実施の形態に
ついて詳細な説明をする。図１中の全体を囲む枠１１０
は本発明の第３の実施の形態における地図管理装置の全
体構成を示すブロック図である。地図データ格納装置１
０１に格納されているマッチングの対象となる２枚の地
図データにおいて、両者の地図の中の道路のノードの識
別子が一致している場合について考える。前処理部１０
９において、マッチングの対象として指定された２枚の
地図のそれぞれについて、その地図に含まれるすべての
道路のリンクの両端のノードの識別子が、もう一方の地
図に含まれるリンクの両端のノードの識別子と一致した
場合に、その一致したリンクを両方の地図からあらかじ
め取り除いて特徴抽出部１０４に渡す。前処理部１０９
が付け加わったことおよび地図データ読み出し部１０１
が読み出した地図データを前処理部１０９に渡すこと以
外の動作は第１の実施の形態と同じである。

【００３４】

【発明の効果】以上説明したように、本発明は、特徴抽
出部、マッチング候補生成部、類似度計算部、マッチン
グ部、および微小領域マッチング制御部を設け、地図デ
ータ中の道路の特徴を抽出してマッチングの対象となる
道路の組を探し、また前記マッチングの対象候補のそれ
ぞれについて類似度を計算し、その結果に基づいて道路
の組が同一の道路であるか否かを判断し、さらにマッチ
ングできなかった道路について微小領域毎にマッチング
をやり直すようにしたため、スキャナによる読み取りの
誤差およびデジタル化の際の誤差などに対しても安定に
マッチングを行なうことができる。

【００３５】また、マッチング候補生成動作において、
マッチングの対象となっている２枚の地図のそれぞれか
ら抽出された特徴点の組のうち、前記角度−距離空間に
おいて予め定めた大きさの近傍に入る特徴点の集合をマ
ッチングの対象とする候補生成方法に加えて、当該地図
に含まれる前記道路のリンクにつけられた前記共通な種
類の属性の値が一致するものをマッチングの候補として
生成し、地図マッチングを行なうようにしたことによ
り、マッチングの候補を減らし、探索空間を小さくして
効率的にマッチングを行なうことができる。

【００３６】さらに、道路のノードのそれぞれに一意に
識別子を付け、さらに前記道路のリンクのそれぞれが当
該リンクの両端のノードの前記識別子によって識別可能
となる地図データを地図データ格納装置に格納し、前記
マッチングの対象となっている２枚の地図に対して、当
該地図に含まれる前記道路のリンクの識別子を用いて同
一であると判定することによって、地図から前記リンク
の識別子が一致した道路のリンクを前処理部によって取
り除き、前記地図データに対する編集操作によって異な
る版の地図が１個以上作成された場合に、マッチングの
対象となっている版が異なる地図のそれぞれからリンク
番号を取り除いて地図マッチングを行なうようにしたた
め、マッチングの候補を減らし、探索空間を小さくして
効率的にマッチングを行なうことができるという効果が
得られる。

【図面の簡単な説明】

【図１】本発明の各実施の形態に係る地図マッチング装
置およびこれが組み込まれる地図管理装置の構成を示す
ブロック図

【図２】本発明の第１の実施の形態による地図マッチン
グ装置で使用されるノードとリンクによって道路を構成
する地図データの実例図

【図３】前記実施の形態による地図マッチング装置によ
る地図マッチング処理動作を説明するフロー図

【図４】前記実施の形態における特徴抽出部による道路
のリンクの近似方法を説明するための地図の概念図

【図５】前記実施の形態において特徴抽出部が抽出する
道路のリンクの特徴として、図４におけるＸＹ直交座標
系中の近似線分Ａ１−Ａ２の特徴抽出について説明する
ための概念図

【図６】前記実施の形態において同一地域を表す２枚の
異なる地図Ａ、Ｂのそれぞれから抽出される特徴或いは
ずれを示すための地図の概念図

【図７】前記実施の形態においてマッチング候補生成部
によって特徴が特徴空間にマッピングされることを示す
概念図

【図８】前記実施の形態において類似度計算部によって
計算される類似度の計算方法の一例を説明するための概
念図

【図９】前記実施の形態において類似度計算部によって
計算される類似度の計算方法の他の例を説明するための
概念図

【図１０】前記実施の形態において類似度計算部によっ
て計算される類似度の計算方法のさらに他の例を説明す
るための概念図

【図１１】前記実施の形態において一方の地図中の１本
のリンクが他方の地図中で正確に表現したため複数のリ
ンクに対応している状態を示すための地図の概念図

【図１２】前記実施の形態において一方の地図中の１本
のリンクが他方の地図中では他のリンクの追加によりリ
ンクの分割が生じた状態を示すための地図の概念図

【図１３】前記実施の形態において図１１に示す地図に
対する類似度計算部による類似度計算の結果を説明する
ための概念図

【図１４】前記実施の形態において微小マッチングの処
理を行なう場合の処理内容を説明する図

【図１５】前記実施の形態において微小マッチング処理
に際してマッチングの候補とされない道路に対して補間
点単位の微小リンク表現を行なった場合の補間点を表現
した図

【図１６】前記実施の形態において図１５に示す補間点
単位の微小リンク表現を行なった場合の微小リンクの取
り出し処理を説明する図

【図１７】従来技術の地図マッチング装置の構成を示す
ブロック図

【図１８】従来の地図マッチング装置の処理動作を説明
するための処理手順説明図

【図１９】従来の地図マッチング装置の処理動作を説明
するためのフロー図

【符号の説明】

１００ 地図マッチング装置 １０１ 地図データ格納装置 １０２ 地図データ指定部 １０３ 地図データ読み出し部 １０４ 特徴抽出部 １０５ マッチング候補生成部 １０６ 類似度計算部 １０７ マッチング部 １０８ 微小領域マッチング制御部 １０９ 前処理部 １１０ 地図管理装置

Claims (5)

【特許請求の範囲】
1. 【請求項１】 ノードとリンクによって道路を表現する
   地図データを格納する地図データ格納装置と、前記地図
   データ格納装置に格納された任意の地図を指定するため
   の地図データ指定部と、前記地図データ格納装置に格納
   された地図データを読み出す地図データ読み出し部と、
   前記地図データ読み出し部によって読み出された地図デ
   ータ中の道路の特徴を抽出する特徴抽出部と、前記特徴
   抽出部によって抽出された道路の特徴を用いて地図デー
   タ中からマッチングの対象となる道路の組を探すマッチ
   ング候補生成部と、前記マッチング候補生成部によって
   生成された前記マッチングの対象候補のそれぞれについ
   て類似度を計算する類似度計算部と、前記類似度計算部
   によって計算された類似度に基づいて道路の組が同一の
   道路であるか否かを判断するマッチング部と、マッチン
   グできなかった道路について微小領域毎にマッチングを
   やり直す微小領域マッチング制御部とを備えた地図マッ
   チング装置。
2. 【請求項２】 ノードとリンクによって道路を表現する
   地図データを格納する地図データ格納装置と、前記地図
   データ格納装置に格納された任意の地図を指定するため
   の地図データ指定部と、前記地図データ格納装置に格納
   された地図データを読み出す地図データ読み出し部と、
   前記地図データ読み出し部によって読み出された地図デ
   ータ中の道路の特徴を抽出する特徴抽出部と、前記特徴
   抽出部によって抽出された道路の特徴を用いて地図デー
   タ中からマッチングの対象となる道路の組を探すマッチ
   ング候補生成部と、前記マッチング候補生成部によって
   生成された前記マッチングの対象候補のそれぞれについ
   て類似度を計算する類似度計算部と、前記類似度計算部
   によって計算された類似度に基づいて道路の組が同一の
   道路であるか否かを判断するマッチング部と、マッチン
   グできなかった道路についてのみ微小領域毎にマッチン
   グをやり直す微小領域マッチング制御部とを具備する地
   図マッチング装置において、前記地図データ格納装置に
   ２種類以上の異なる地図データを格納しておき、格納さ
   れている任意の２種類の地図データの中のそれぞれから
   同一地域を表す任意の１枚づつ合計２枚の地図をマッチ
   ングすべき地図として地図データ指定部を用いて指定
   し、当該地図に含まれる道路を互いにマッチングを行な
   う場合に、前記特徴抽出部において、当該地図に含まれ
   るすべての道路のリンクについて各々のリンクを構成す
   る両端のノードを結ぶ線分を当該リンクの近似とし、当
   該地図毎に予め定めた座標原点から当該リンクの近似線
   分もしくはその線分の延長上に下ろした垂線が当該地図
   毎に予め定めた座標軸となす角度を第１の特徴として抽
   出し、前記座標原点から当該リンクの近似線分もしくは
   その線分の延長上に下ろした垂線の足までの距離を第２
   の特徴として抽出し、前記マッチング候補生成部におい
   て前記第１および第２の特徴を角度−距離空間に特徴点
   としてマッピングを行ない、当該マッチングの対象とな
   っている２枚の地図のそれぞれから抽出された特徴点の
   組のうち、前記角度−距離空間において予め定めた大き
   さの近傍に入る特徴点の集合をマッチングの対象として
   生成し、前記類似度計算部において、当該対象集合に含
   まれるそれぞれの特徴点の組に関して特徴を計算する元
   となった前記道路のリンクの線分近似を用いて、２本の
   近似線分のそれぞれの２個の端点からもう一方の近似線
   分もしくは近似線分の延長上に垂線を下ろし、それぞれ
   の垂線の長さ、垂線の足の位置から線分の端点までの長
   さを用いて類似度を計算し、前記類似度を用いて前記マ
   ッチング部において道路のマッチングを判定し、マッチ
   ングに失敗した道路については前記微小領域マッチング
   制御部によって道路を微小領域に分割し、前記特徴抽出
   部、前記マッチング候補生成部、前記類似度計算部、お
   よび前記マッチング部の処理を再度行なう地図マッチン
   グ装置。
3. 【請求項３】 地図データ読み出し部によって読み出さ
   れた地図データの前処理を行なう前処理部を備えた請求
   項１または２記載の地図マッチング装置。
4. 【請求項４】 前記地図データ管理装置中に格納されて
   いるマッチング対象となる２枚の地図データに関して、
   道路のリンクが少なくとも１種類以上の互いに共通な属
   性を持ち、かつそれぞれリンクの前記共通な種類の属性
   に値がつけられている場合については、前記マッチング
   候補生成部において、マッチングの対象となっている２
   枚の地図のそれぞれから抽出された特徴点の組のうち、
   前記角度−距離空間において予め定めた大きさの近傍に
   入る特徴点の集合をマッチングの対象とする候補生成方
   法に加えて、当該地図に含まれる前記道路のリンクにつ
   けられた前記共通な種類の属性の値が一致するものをマ
   ッチングの候補として生成し、地図マッチングを行なう
   ことを特徴とする請求項２記載の地図マッチング装置。
5. 【請求項５】 前記道路のノードのそれぞれに一意に識
   別子がつけられ、さらに前記道路のリンクのそれぞれが
   当該リンクの両端のノードの前記識別子によって識別可
   能となる地図データが格納されている前記地図データ格
   納装置と、前記マッチングの対象となっている２枚の地
   図に対して、当該地図に含まれる前記道路のリンクの識
   別子を用いて同一であると判定することによって、地図
   から前記リンクの識別子が一致した道路のリンクを取り
   除く前処理部とを具備し、前記地図データに対する編集
   操作によって異なる版の地図が１個以上作成された場合
   に、マッチングの対象となっている版が異なる地図のそ
   れぞれからリンク番号を取り除いて地図マッチングを行
   なうことを特徴とする請求項３記載の地図マッチング装
   置。