(57)【要約】  道路網の第１のデジタル地図からの所定のルート区域を道路網の第２のデジタル地図の中で位置特定するための方法を開示する。本発明は、前記ルート区域を白黒又はカラーの道路区域像として解釈し、ただし、前記道路区域像において道路は区別可能なグレー値又は色値により識別可能であり、前記道路区域像における階段状の激しいグレー値又は色値の遷移を軟らかいグレー値又は色値の変化に変え、このぼかされた道路区域像を所定の変換を用いて変換し、第２の道路区域像を第２の地図において所定のルート区域の想定される近傍に配置し、第２の道路区域像における階段状の激しいグレー値又は色値の遷移を軟らかいグレー値又は色値の変化に変え、このぼかされた道路区域像を所定の変換を用いて変換し、変換係数を互いに比較し、変換係数の評価から第２の地図における所定のルート区域の場所的な位置を求める。本方法を実行するためのシステムも開示される。
2009518721.tif 000002
【特許請求の範囲】
【請求項１】
道路網の第１のデジタル地図からの所定のルート区域を道路網の第２のデジタル地図の中で位置特定するための方法において、前記ルート区域を白黒又はカラーの道路区域像として解釈し、ただし、前記道路区域像において道路は区別可能なグレー値又は色値により識別可能であり、前記道路区域像における階段状の激しいグレー値又は色値の遷移を軟らかいグレー値又は色値の変化に変え、このぼかされた道路区域像を所定の変換を用いて変換し、第２の道路区域像を第２の地図において所定のルート区域の想定される近傍に配置し、第２の道路区域像における階段状の激しいグレー値又は色値の遷移を軟らかいグレー値又は色値の変化に変え、このぼかされた道路区域像を所定の変換を用いて変換し、変換係数を互いに比較し、変換係数の評価から第２の地図における所定のルート区域の場所的な位置を求めることを特徴とする方法。
【請求項２】
道路を起点としてぼかしを行う際には、道路周辺の画素のグレー値又は色値を点ごとに道路のグレー値又は色値に適合させる、請求項１記載の方法。
【請求項３】
道路の間にあるオープンスペースを起点としてぼかしを行う際には、道路周辺の画素のグレー値又は色値を点ごとに前記オープンスペースのグレー値又は色値に適合させる、請求項１記載の方法。
【請求項４】
前記適合の際、グレー値又は色値の影響が所定の減衰関数に従って単調に減少するようにする、請求項２又は３記載の方法。
【請求項５】
位置忠実な変換の係数を計算する、請求項１から４のいずれか１項記載の方法。
【請求項６】
ウェーブレット変換のウェーブレット係数を計算する、請求項５記載の方法。
【請求項７】
ハールウェーブレットを用いる、請求項６記載の方法。
【請求項８】
変換係数の比較の際に複数の行列の比較が行い、その際に、行列の差を計算し、絶対値で所定の限界値を下回る行列要素を数える、請求項１から７のいずれか１項記載の方法。
【請求項９】
変換係数の比較の際に複数の行列の比較が行い、その際に、行列の差を計算し、行列の差のノルムを求める、請求項１から７のいずれか１項記載の方法。
【請求項１０】
変換係数を複数の分解段階を経て計算する、請求項１から９のいずれか１項記載の方法。
【請求項１１】
位置特定を上位の分解段階において開始する、請求項１０記載の方法。
【請求項１２】
変換係数の評価から、さらに、第２の地図の中で所定のルート区域に生じたずれ、ねじれ及び／又は歪みを求める、請求項１から１１のいずれか１項記載の方法。
【請求項１３】
道路網の第１のデジタル地図からの所定のルート区域を道路網の第２のデジタル地図の中で位置特定する請求項１から１２のいずれか１項記載の方法を実行するためのデジタル地図用のデータメモリ（２，６）を備えたシステム（１，５）において、該システム（１，５）は、前記地図のルート区域を白黒又はカラーの道路区域像として解釈し、ただし、前記道路区域像において道路は区別可能なグレー値又は色値により識別可能であり、前記道路区域像において階段状の激しいグレー値又は色値の遷移を軟らかいグレー値又は色値の変化に変え、このぼかされた道路区域像を所定の変換を用いて変換し、第２の道路区域像を第２の地図において所定のルート区域の想定される近傍に配置し、第２の道路区域像における階段状の激しいグレー値又は色値の遷移を軟らかいグレー値又は色値の変化に変え、このぼかされた道路区域像を所定の変換を用いて変換し、変換係数を互いに比較し、変換係数の評価から第２の地図における所定のルート区域の場所的な位置を求めるように形成されている、ことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、交通網の第１のデジタル地図からの所定のルート区域を交通網の第２のデジタル地図内で位置特定するための方法及びシステムに関する。
【０００２】
交通状況の改善は久しく跨道標識橋と方向標識の形態で公共の交通誘導により追求されてきた。このような交通誘導はふつう代替ルートの少なさから同様に少ない目的地に限定されてしまう。できだけ早く目的地に着きたいという個々人の要望の他に、例えば地方自治体にとっては、負の影響をできるだけ小さくとどめるべく交通の流れを導くことも関心事である。この場合、個々の最適ルートに対する要望と集合的な交通整理の目標とが一つにまとまらなければならない。
【０００３】
上記問題の１つの側面として、ロケーションとも呼ばれる、注意及び障害の場所の記述がある。一般的な用語法では、ロケーション、ドイツ語で言えば場所とは、所在位置、すなわち、道路網内のある特定の位置を記述するものである。したがって、ロケーションに基づいたサービスとは、ユーザの所在位置を取り入れたサービスである。しかし、ロケーションはドイツ語における所在位置の概念のようにつねに点ベースである必要はない。したがって、ロケーションは道路網においても広がりを持っていてよい、例えば、所定の道路区域であってよい。
【０００４】
今日慣用の動的ナビゲーションでは、ナビゲーションシステムは、現在の交通状況に関する受信した交通データに基づいて、既に計算したルートを検査するか、場合によっては、交通状況の変化を考慮してルートを再計算する。通常、交通データは位置の特定ができるようにロケーションに、すなわち、道路網内の所定のルート区域に割り当てられている。そこで、ナビゲーションシステムは、受信した交通メッセージをルート計算の際に考慮することができるようにするため、使用する地図内でこの所定のルート区域を一意的に特定しなければならない。この位置特定は参照とも呼ばれる。
【０００５】
ロケーションの参照は、広がりを有することもあるこの場所を未知のデジタル地図にもはめ込むことができるように、この場所を正確に記述しなければならない。それは、言い換えれば、特殊な地図特徴に拠らず、標準的な符号化規則を用いて、道路網又は道路網の一部におけるロケーションを記述する方法である。地図は現実をデジタルに解釈したものである。解釈のプロセスは標準化されていないが、同じような方法で行われる。その他の相違点に関しては、この方法はほとんど影響を受けない。
【０００６】
なお、ロケーションの参照は必ずしも新しいものでなくてよい。郵便番地は参照の非常に古い手段である。郵便番地は、番号の付された高権的に定められた地域と、全国的に一意の地名と、土地台帳で定められた街路名と、家屋番号とに分かれている。例えば街路名を知らない場合など、記入項目に関する情報が不足していると、参照先をデジタル地図内に探し当てる可能性が非常に乏しくなる。
【０００７】
地理参照では、座標を使用することが多い。その場合、点ははめ込みのために重ねて配置される。しかし、座標とユークリッド距離は種々のロケーションの間の実際の網距離を示すものではない。それゆえ、幾何学的には隣接している点が交通網内の自然の障壁によって互いに遠く隔たっていることもあり得る。送信者と受信者の間の座標の僅かなずれが解釈の際に大きな誤差を生じることもあり得る。
【０００８】
車両ナビゲーションのための基礎として、ナビゲーションシステムは道路網のデジタル地図にアクセスする。ただし、これらの地図は標準化されていないため、地図の製造元が異なると、デジタル地図情報が異なっていたり、座標がずれていたりすることがある。これらの相違は、標準化された曲率半径や交差点表示などの現実の様々な解釈によって生じるのではなく、道路網の連続的な時間的展開プロセスによって生じるものである。
【０００９】
様々な共同プロジェクトで、ロケーションの参照に関する提案が全ヨーロッパ的に行われてきた。これらの提案は本願においても基礎として用いられる。例えば、プロジェクトＡＧＯＲＡは、ロケーション参照の符号化法と、ロケーション参照を望ましくは地図に依存させないための詳細なルールを提示している。
【００１０】
EP 1 122 518 A1では、交通路網を直線状のオブジェクトとして格納したデータベースを用いて、直線状の地理オブジェクトを復号する方法が開示されている。この方法によれば、復号すべきオブジェクトと交通路網のオブジェクトの点の集合がそれぞれ形成され、点集合相互の複数の相対位置について、前記点集合のうちの１つに関して、この点集合の点であって且つこの点集合の少なくとも１つの点の所定距離内にある点の数が求められ、この数が最大となる相対位置にある復号すべきオブジェクトがこのオブジェクトと相関する交通路網の一部の出力により復号される。
【００１１】
さらにEP 1 225 552 B1では、全体として地理的なコンテキストにおいてロケーションを参照する方法が開示されている。この方法では、サービスプロバイダにより提供された２つの連続する回転ポイントの間の第１の道路区域に関連して、第１の道路区域の全体又は一部に対する択一肢である第２の道路区域の各々に、前記全体又は一部の重み付けされた距離よりも格段に大きな重み付けされた距離が割り当てられる。ただし、サービスプロバイダにより提供された２つの連続する回転ポイントの間の距離は最小の重み付けされた距離である。
【００１２】
従来から公知のこれらの方法は程度の差はあれ大体直接的に利用できる情報に適用されるものであり、それゆえに、特に情報が不足している場合、例えば道路区域が欠けている場合には誤りの生じる可能性がある。
【００１３】
本発明の課題は、以上のことを背景として、地図中のルート区域の位置特定を改善し、基礎となる地図データの不正確さに対するロバストネスを高めることである。その際、実行とメモリ消費とに関して効率的でなければならない。
【００１４】
この課題は請求項１に記載の特徴を備えた方法と請求項１３に記載の特徴を備えたシステムにより解決される。
【００１５】
本発明によれば、冒頭で述べたような方法とシステムにおいて、ルート区域は白黒又はカラーの道路区域像として解釈され、道路は区別可能なグレー値又は色値によって識別可能である。道路区域像において、階段状の激しいグレー値又は色値の遷移が軟らかいグレー値又は色値の変化に変えられ、ぼかされた道路区域像は所定の変換を用いて変換される。第２の道路区域像は第２の地図において所定のルート区域の想定される近傍に配置される。第２の道路区域像における階段状の激しいグレー値又は色値の遷移は軟らかいグレー値又は色値の変化に変えられ、ぼかされた道路区域像が所定の変換を用いて変換される。次に、変換係数が互いに比較され、変換係数の評価から第２の地図における所定のルート区域の場所的な位置が求められる。
【００１６】
なお、それぞれ１つのデジタル地図にアクセスする２つのシステムが相互に通信し合う場合、つねに両方のシステムがそれぞれの地図の道路区域に関して変換を行うのか、又は、２つのシステムのうちの一方が両方の地図区域に関して変換を行って、その後、変換係数を評価しながら比較するのかは定まっていない。
【００１７】
道路網は実質的に直線状のオブジェクトから構成されている。なお、これらのオブジェクトはふつう多角形の列としてデジタル地図に格納されている。本発明によれば、この直線表現は点で形成された像として解釈される。この道路区域像において、道路はその間にあるオープンスペースから様々な色調によって区別可能である。例えば、道路を黒に、オープンスペースを白に表示するようにしてよい。
【００１８】
ところで、この像表示は行列を用いて容易に記述に書き換えることが可能である。なお、この行列において、個々の行列要素の数値は所定の色又は所定のグレー値ないし色値に対応している。これにより、適切なアルゴリズムによって変更及び解釈の可能な地図情報の表示が可能となる。
【００１９】
本発明に従って行われるぼかしは、道路区域像を細かく、例えば点ごとに変位させるのに比べて、後で行われる所定の変換を安定化させる。さらに、道路網の２つのデジタル地図の間の僅かな相違の影響も低減する。
【００２０】
有利には、道路を起点としてぼかしを行う際、道路周辺の画素のグレー値又は色値は点ごとに道路のグレー値又は色値に適合させられる。あるいは、オープンスペースを起点としてぼかしを行う際に、道路周辺の画素のグレー値又は色値が点ごとにオープンスペースのグレー値又は色値に適合させられる。道路を黒にし、オープンスペースを元の白にする色選択をした場合、道路周辺はグレースケール像に変わる。
【００２１】
適合の際、グレー値又は色値の影響は所定の減衰関数に従って単調に減少することが好ましい。この減衰関数は、線形関数、双曲関数、指数関数、多項式関数もしくは対数関数、又は、上に挙げた関数の任意の組合せとしての関数としてよい。
【００２２】
本発明による方法において、位置忠実な変換の係数を計算すると有利である。それにより、変換された像又は変換されたデータにも位置情報が保持される。考察している地図区域の左上の領域に道路区域があるならば、左上の領域にある変換された像もこの道路区域に関する情報を含むことになる。
【００２３】
本発明による方法の１つの実施形態では、好ましくはウェーブレット変換のウェーブレット係数が計算される。次のように定義されるハールウェーブレットを使用することが特に好ましい。
【００２４】
【数１】
2009518721.tif 000003
【００２５】
有利には、変換係数の比較の際に、複数の行列の比較が行われる。その際、行列の差が計算され、続いて、絶対値で所定の限界値を下回る行列要素がカウントされる。カウントした数は評価の品質の目安であり、行列の差の最小値はルート区域の位置特定に使用される。
【００２６】
代替的には、変換係数の比較の際に複数の行列の比較を行い、その際に、行列の差を計算し、続いて、行列の差のノルムを求め、このノルムを品質の評価に使用する。この場合も、位置特定は行列の差の最小値を用いて行われる。ここで、ノルムとは行列の大きさを表す関数として理解されるべきものである。これに関して、スペクトルノルム、無限ノルム又は１-ノルムの形式を採用することも可能である。
【００２７】
変換係数は好ましくは複数の分解段階を経て計算され、位置特定は特に好ましくは上位の分解段階から開始される。これにより、探索半径を下位の分解段階に縮小することが可能となる。上位の分解段階は画素データ量の低減を特徴としており、例えば使用するウェーブレット関数の位置忠実性により、位置のぼかしが増しても位置特定可能である。こうすることで、計算ステップの数がより少なくなるため、より速く結果が得られる。
【００２８】
変換係数の評価から、さらに、第２の地図の中で所定のルート区域に生じたずれ、ねじれ及び／又は歪みを求めることができると有利である。これにより、使用されるデジタル地図の偏差に対するロバストネスが増す。
【００２９】
以下では、本発明による方法を添付した図面を参照して例示的に詳しく説明する。
【００３０】
図１は、互いに比較される２つのシステムとそのデジタル地図の概略図であり、
図２は、道路網の１つの区域を示しており、
図３は、エンコーダ側の道路網の１つの区域を示しており、
図４ａ−ｄは、それぞれデコーダ側の道路網の１つの区域を示している。
【００３１】
図１には、データメモリ２に格納された道路網のデジタル地図を備えた送信機システム１が概略的に示されている。参照番号３で表されたある特定のルート区域ないし道路区域は、送信機システム１において適切な方法でデータ伝送向けに符号化される。符号化された地図情報は次に伝送経路４を介して受信機システム５に伝送される。
【００３２】
受信機システム５のデータメモリ６に格納されている第２のデジタル地図では、ルート区域３に対応するルート区域７が位置特定されなければならない。符号化と復号のためには、道路区域３及び７内の道路の幾何学データだけが使用される。
【００３３】
図１に示されている構成は原則的に本発明による方法を実行する２つの択一肢を許容する。２つのバリエーションのうちの一方では、エンコーダ側で、つまり送信機システム１によって、相応する道路区域像をぼかし、行列の形で伝送する。その後、行列にウェーブレット変換が施される。
【００３４】
変換の際に生じる複数の係数行列は伝送経路４を介してデコーダ側ないし受信機システム５に伝送される。デコーダ側でも同様に、探索すべきルート区域７に対応するであろう道路区域像を同じ方法で処理する。
【００３５】
第２のバリエーションでは、エンコーダ側は変換を行わず、ルート区域の幾何学的情報を伝送する。この場合、デコーダ側で、両方の地図表示のためにウェーブレット変換が行われる。第２のバリエーションでは、伝送すべきデータの量は複数の係数行列を伝送する第１のバリエーションの場合よりも明らかに少なくなり得る。ただし、全計算コストがデコーダ側にかかることが欠点である。
【００３６】
次に、両方のバリエーションにおいて、それぞれの係数行列が相互に比較される。基準オブジェクトに対する探索オブジェクトの可能な位置が複数である場合、基準オブジェクトのウェーブレット変換値に対する探索オブジェクトのウェーブレット変換値の類似性を求める数値が求められる。復号されるべきオブジェクトは、このようにして求めた類似性が十分に大きな規定の品質に達している位置で、探し当てられたと判定される。
【００３７】
図２には、道路網９のある１つの区域８が示されている。個々の道路９は黒線で表示されている。黒で表示された道路９の間のスペースないしオープンスペース１０は白の面である。図２から明らかなように、オープンスペース１０から道路９への突然の移行は白から黒への色変化によって認識される。
【００３８】
本発明によれば、この移行の第１段階において、ルートは不鮮明にされる、又はぼかされる。これにより、道路９は黒のままであるのに対して、オープンスペース１０は道路９を起点として最も近い道路９から離れれば離れるほど明るくなる色付けを受ける。このようにして、各画素に色又はグレースケール値が対応付けられる。地図区域８は、各行列要素が画素に対応し、行列要素の数値がグレー値又は色値に相当するｎ×ｍ行列として解釈される。
【００３９】
この行列にはハール関数を用いたウェーブレット変換が施される。これにより、相応する係数行列は水平、垂直及び対角ウェーブレット係数を得る。これらの係数行列の数値は、表示の更新の際に、これらの数値に対応するグレー値又は色値によって、道路が尾根に相応するような山岳地形として道路区域８の表示を生成する。
【００４０】
ウェーブレット変換からは、水平ウェーブレット係数、垂直ウェーブレット係数及び対角ウェーブレット係数が得られる。水平ウェーブレット係数の山岳地形ないし等高線が水平方向に走る道路の成分を強調する一方で、垂直方向に走る道路の情報はほとんど消えてしまう。同様に、強調の異なる別の等高線によれば、垂直又は対角ウェーブレット係数の表示がもたらされる。
【００４１】
図３には、エンコーダ側の地図区域１１が示されている。この地図区域１１は部分的に図２の地図区域８と一致している。図３では、ロータリー１２の周りの領域が反転して表示されている。この領域がデコーダ側でロケーションとして探し出さなければならないものである。
【００４２】
図４ａ−ｄでは、探し出すべき図３のロータリー１２がデコーダ側の４つの異なる地図表示にそれぞれ示されている。図４ａの表示では、ロータリー１３は図３の反転した区域と完全に一致している。図４ｂの地図表示では、ロータリー１４において、１つの進入路だけが失われている。図４ｃの表示では、ロータリー１５の進入路が図３のロータリー１２とは異なって表示されており、その一方で、図１４ｄの表示では、ロータリー１６に１つの進入路だけがあるだけであり、残りの５つの進入路は完全に失われている。
【００４３】
本発明による方法を使用すれば、地図区域４ａはもちろん探索すべきロケーションとして認識される。しかし、図４ｂ及び４ｃの相違点のある表示も大した困難もなく探索すべきロケーションとして識別される。
【００４４】
図３のロケーションが図４ｄの要素として探し出される確率は、とりわけ、近傍に似たような道路形状が、例えばさらに別のロータリーが、存在しているか否かに依存する。表現に信頼性が欠けていれば、そのことは、最大値が周囲の地域からそれほど急激に突出しておらず、また高さの面でも、他の任意の探索位置に比べてそれほど際だって高くないことから察知される。しかし、それでも、本発明による方法は地図表示の相違点に対して十分にロバストであるので、図４ｂもしくは４ｃのルート又はロータリー１４ないし１５は問題なく図３の探索すべき道路区域又はロータリーとして位置特定され、表現に信頼性が欠けている場合には、不正確な表現を識別することもできることが認められる。
【図面の簡単な説明】
【００４５】
【図１】互いに比較される２つのシステムとそのデジタル地図の概略図である。
【図２】道路網の１つの区域を示す。
【図３】エンコーダ側の道路網の１つの区域を示す。
【図４】それぞれデコーダ側の道路網の１つの区域を示す。
【図１】
2009518721.tif 000004
【図２】
2009518721.tif 000005
【図３】
2009518721.tif 000006
【図４ａ】
2009518721.tif 000007
【図４ｂ】
2009518721.tif 000008
【図４ｃ】
2009518721.tif 000009
【図４ｄ】
2009518721.tif 000010
【国際調査報告】
2009518721.tif 000011
2009518721.tif 000012
2009518721.tif 000013
2009518721.tif 000014
2009518721.tif 000015
2009518721.tif 000016