ＧＰＳ軌跡を用いた付加的マップ生成、改良および拡張
ＧＰＳ使用可能なナビゲーション装置によって記録される統計的に関連する量のプローブデータから、既存ネットワークを改良および拡張し、新しいネットワークを生成する方法。新しいプローブデータは既存のデジタルベクトルマップとマッチングされ、次にそのデータは、加重平均技術を使用して既存ネットワークへ結合される。新しい道路が検出されると、適切なジャンクション地点が既存ネットワーク要素から作られる。計算速度を向上し、データストレージ要求を低減するために、更新されたネットワークデータは単純化される。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００９年１０月２２に出願された国際出願番号PCT/EP2009/063938の国際段階であり米国を指定している。本願の全内容はここに参照により組み込まれている。
【０００２】
本発明は、一般にプローブデータを使用してデジタルベクトルマップを更新および拡張する方法に関し、特に、１以上のパーソナルナビゲーション装置によって生成されたＧＰＳ座標を使用してデジタル車歩道マップを改良する方法に関する。
【背景技術】
【０００３】
ナビゲーションシステム、（デジタルマップとしても知られている）電子マップ、および地理的位置決め装置が、移動者および／または車両の総合的な位置および方位を判定する、目的地および住所を見つける、最適ルートを計算する、およびリアルタイムでの運転ガイダンスを提供する等の、様々なナビゲーション機能を補助するために移動者によってますます使用されている。一般に、ナビゲーションシステムは、ストリートのネットワークを、各ストリートまたは経路の中央に沿って走るセンターラインを含む一連の線分として表現する小型ディスプレイ・スクリーンまたはグラフィカル・ユーザ・インタフェースを含む。移動者は、その場合一般にそのセンターラインに近接して、あるいはセンターラインに関してデジタルマップ上に配置されうる。
【０００４】
道路情報を示し、処理するには非常に費用を要するので、デジタルマップを生成および更新するには費用がかかる。方法を調査したり、あるいは衛星画像をデジタル化したりすることは、デジタルマップを作成するために一般的に採用される技術である。さらにその上、デジタルマップは、欠陥のある、あるいは不正確な入力源、または不備のある推論方式が原因で、不正確性またはシステマチック誤差を含む可能性が高い。ひとたびデジタルマップが作成されると、道路配置は時間とともに変化するので、マップ情報を最新に保つには費用を要する。世界のいくつかの地域では、デジタルマップは全く利用不可能である。
【０００５】
図１Ａ―図１Ｃは、道路形式でデジタルベクトルマップを描写している。図１Ａは、主要な高速道路または運転ルートを表している。図１Ｂは、図１Ａの主要な高速道路に加えて、周辺（第２の）道路の相互接続ネットワークを描写している。図１Ｃは、図１Ｂの全ての情報と共に、第３のストリートおよび路地の拡張ネットワークを描写している。これらの図を参照することによって理解されるように、デジタルマップを生成するために費用および努力が必要なのと併せて、既存の車道マップまたはネットワークが、所与の領域内の全ての車道または経路の描写において不完全であることが事実であるかもしれない。さらにその上、車道および経路を含んでもよいがこれらに限定されないネットワークの発展性が原因で、時間と共に変化が起こるかもしれず、既存のデジタルマップは現状をもはや正確に表現していないかもしれない。
【０００６】
図２において、デジタルベクトルマップは、ジャンクションＪおよび線分Ｗ１、…、Ｗ９を含む。それらは共に、いくつかの追加プロパティを有するグラフを構成する。ジャンクションＪはノード（節点）であり、線分Ｗはグラフのエッジである。グラフは単方向マップ向けであり、双方向マップ向けではない。全ての線分Ｗは２つのジャンクションＪを接続する。それどころか、各ジャンクションＪにおいて、ちょうど１つあるいは少なくとも３つの線分Ｗが合流する（例外的な場合のみ、１つのジャンクションで２つの線分が合流するだろう）。ジャンクションＪおよび線分Ｗは通常、例えば重み値、寸法（measure）および方角（heading）等を含むいくつかの属性と関連付けられている。線分Ｗの配置は、（多角形曲線、多角形経路、または区分線形曲線とも呼ばれる）多角形チェーンとしてしばしば記述される。あるいは、スプライン曲線、円形セグメントまたはクロイド曲線等の他の曲線も使用できる。しかしながら、各曲線は、多角形チェーンにより十分正確に近似されうるので、通常は多角形チェーンが使用される。多角形チェーンの頂点すなわち節点は、曲線の形状を規定するので、形状地点（ＳＰ）と呼ばれる。もちろん、例えば属性が変化した場合などの適切な状況下では、ジャンクションＪに対する形状地点ＳＰを変更することが可能である。
【０００７】
図２は、デジタルベクトルマップの一部のセクションを説明しており、この場合、双方向交通をサポートする双方向車道である。幹線車道が１０で示されており、幹線車道１０から全体として垂直に延びる支線（分岐）道路が１２で示されている。例えば、あるクラスタリング技術を使用してマップを徐々に学習する目的で、一体型ＧＰＳ機能を有する低コスト位置決めシステムおよび携帯用装置および携帯電話から、プローブデータ入力を取得することが既知である。処理されるべき入力は、ほとんど全てのＧＰＳ装置によってサポートされている標準ＡＳＣＩＩストリームの形式で記録されたＧＰＳ軌跡から成る。出力は、移動時間情報付きの節点およびエッジ（端）を有する有向グラフの形式での道路マップである。ナビゲーション装置を装着して幹線車道１０および支線道路１２のジャンクションを移動する移動者は、従って、規則正しい距離で作成された節点を有する、図４に示されるマップのような軌跡マップを作成してもよい。節点およびエッジは、デジタルベクトルマップテーブルまたはデータベースに格納される。付加的アプローチを表すこの技術を通じて、道路配置が推定され、収集されたデータ地点がフィルタリングアルゴリズムおよび分割アルゴリズムによって改良されうる。この技術に関するより完全な議論のために、“Incremental Map Generaltion with GPS Traces（ＧＰＳ軌跡を用いた付加的マップ生成）” Briintrup, R., Edelkamp, S., Jabbar, S., Scholz, B., Proc. 8th Int. IEEE Conf. on Intelligent Transportation Systems, Vienna, Austria, 2005, Pages 413-418.への参照がなされる。
【０００８】
Tele Atlas B.V.のH.-U. OttoおよびO. Schmelzleによって開発された別の技術は、局所アプローチに基づいて、プローブデータから新しい道路ネットワークを生成する。このアプローチは、各軌跡をたどり、個別の軌跡地点付近のバッファを検証して線分（ラインセグメント）を構築する技術に基づいている。新しいネットワーク要素、例えば車道および歩道が、バッファ内部のデータ地点の分布および関連するベクトル方向に依存して生成される。ＧＰＳ軌跡または他のプローブデータを使用して新しいマップを生成する際にこの技術は役立つ一方、既存のネットワークを改良することには十分適していない。
【０００９】
したがって、既存ネットワークを改良し、およびデジタルマップ作成の実施等に際して採用される新しいネットワーク要素を生成するために、ＧＰＳ使用可能なナビゲーション装置からのデータ等のプローブデータを受信する方法を改良する必要がある。
【発明の概要】
【００１０】
本発明は、様々な先行技術の欠点および欠陥を克服するものである。プローブデータからの任意のタイプの軌跡、最も好適にはＧＰＳ軌跡、を使用してデジタルベクトルマップを生成し、改良し、および拡張する方法を提供する。前記方法は、座標系と空間的に関連付けられた複数の線分を格納するように構成されたデジタルベクトルマップを提供する工程と、前記デジタルベクトルマップの各線分と重み値とを関連付ける工程と、複数の連続して送信されたプローブデータ点から少なくとも１つのＧＰＳ軌跡を収集する工程と、マップマッチング基準を構築する工程と、前記マップマッチング基準を使用して、前記ＧＰＳ軌跡に沿った各プローブデータ点を、前記デジタルベクトルマップの前記線分と比較する工程と、を備える。前記方法は、前記マップマッチング基準を満たす前記ＧＰＳ軌跡に沿った各プローブデータ点を“マッチする”と指定し、一方、前記マップマッチング基準を満たさない前記ＧＰＳ軌跡に沿った各プローブデータ点を“マッチしない”と指定する工程と、マッチしたプローブデータ点を含む前記ＧＰＳ軌跡の部分を、前記デジタルベクトルマップの（あるなら）それぞれの線分と関連付ける工程と、前記線分の前記重み値を使用して、前記それぞれの線分と、対応するマッチしたプローブデータ点を含む前記ＧＰＳ軌跡の任意の部分との間の中央線を計算する工程と、前記中央線を通じて前記線分を置換する工程と、マッチしなかったプローブデータ点を含む前記ＧＰＳ軌跡の前記部分で前記デジタルベクトルマップの新しい線分を作成する工程と、を備えることを特徴とする。
【００１１】
前記マップマッチング基準は、様々な適切な方法で構築されうる。１つの方法によれば、各プローブデータ点と前記デジタルベクトルマップにおける線分とのオフセット距離が計算される。所定の最大オフセット値も構築され、前記最大オフセット値よりも小さいと算出されたオフセット距離を有するプローブデータ点が、マッチしたプローブデータ点として指定される。反対に、前記最大オフセット値よりも大きいと算出されたオフセット距離を有するプローブデータ点は、マッチしなかったプローブデータ点として指定される。
【００１２】
この方法によって、道路マップ、自転車マップおよび歩道マップ等に使用されるマップ等の既存のデジタルベクトルマップは、収集されたプローブデータを使用して改良されうる。品質が改良されたデジタルベクトルマップは、デジタルベクトルマップにおいて支線道路（branch）、結合地点（merge）、および交差点をより正確に検出するために使用されることができ、単方向ネットワークおよび双方向ネットワークの両方を生成するために使用されてもよく、および、大規模ネットワークエリアに対して大量のプローブデータを計算する場合実質的な効率向上をもたらす。さらにその上、本発明の全体概念は、車道マップおよび歩道マップだけではなく、任意のデジタルベクトルマップを改良するために使用されうる。座標系と空間的に関連付けられうる、例えば、回路図、結線図（schematic）、および他のグラフィック描写が、本発明の技術の利益を享受する。
【図面の簡単な説明】
【００１３】
【図１Ａ】、
【図１Ｂ】、
【図１Ｃ】図１Ａ−１Ｃは、デジタルベクトルマップの１つの形式の表現として車道ネットワークを表現しており、図１Ａは幹線道路を示し、図１Ｂは相互接続ネットワークを示し、および図１Ｃはストリートネットワークを示す。
【図２】図２は、ジャンクション、線分、および形状地点を示す、支線道路によりジャンクションにおいて交差される幹線道路を有する道路マップのデジタルベクトルマップの単純化された表現である。
【図３】図３は、主題の方法の外観を描写する概略図であり、複数のＧＰＳ使用可能なナビゲーション装置からプローブデータが収集され、テーブルに格納され、および、デジタルベクトルマップを改良および／または拡張するために予め存在するデジタルベクトルマップにおける線分とマッチングされる。
【図４】図４は、プローブデータ点から生じる軌跡線が、デジタルベクトルマップにおける予め存在する要素と共に座標系に最初に設定される方法の説明図である。
【図５】図５は、図４のような図であるが、寸法（measure）の算出、および、デジタルベクトルマップにおける線分と収集されたデータ地点との間のオフセット距離の算出を描写している。
【図６】図６は、図５の拡大図であり、新しいジャンクションがデジタルベクトルマップへ挿入されてもよい任意分割地点を描写する。
【図７】図７は、図６における外接エリアの拡大図であり、線分を分割するために新しいジャンクションを計算する工程に関連する。
【図８】図８は、本発明の技術を使用して更新されたデジタルベクトルマップを描写する。
【発明を実施するための形態】
【００１４】
図面を参照する際、同じ数字は、いくつかの図面を通じて同一のまたは対応する部分を示しており、主題となる発明は図３において概略的に描写される。ここで、複数のプローブ１４が、TomTom NV (www.tomtom.com)によって製造された装置等のＧＰＳ使用可能なパーソナルナビゲーション装置として描写されている。しかしながら、携帯用装置、携帯電話、ＰＤＡ等を含む、ＧＰＳ機能を有するあらゆる適切な装置がプローブデータ点を生成するために使用されてもよい。プローブデータ点は、収集されて、プローブデータテーブル１６あるいは他の適切なデータベースまたは保存場所に格納される。既存のデジタルベクトルマップ、この例では予め作成されたデジタルマップは、テーブル１８に含まれる。もちろん、デジタルベクトルマップ１８は、データベースあるいは他の適切な形式で存在しうる。初期ステップとして、テーブル１６における概略プローブデータから軌跡線が生成される。ステップ２０において、新しい線がプローブデータテーブルから選択される。ステップ２２において、選択された線は、デジタルベクトルマップとマッチングされる。このステップの間、以下でより詳細に記述されるようなマップマッチング方法を使用して、軌跡線の各地点がネットワーク要素と関連付けられるだろう。そのマッチング方法で任意のネットワーク要素を軌跡線と関連付けることが可能ではないなら、プローブデータ点は“マッチしない”としてマークされる。全ての他のプローブデータ点は、この方法で既存ネットワークとマッチングされることを試みられる。データ地点が既存ネットワークの任意の要素とマッチしていない軌跡線分については、これらは、ネットワーク要素から分割され、新しいジャンクションまたは既存のジャンクションによって挿入され、あるいは接続されなければならない。これはステップ２４において起こる。場合によっては、既知あるいは予め存在するジャンクションを使用することが合理的である。ジャンクションは、車道ネットワークアプリケーションにおいて交差点と称されてもよい。時々、既存のジャンクションは正確な位置になく、必要に応じて除去されるだろう。いくつかの例では、以下に記述される技術に従って、新しいジャンクションが作成される必要があるだろう。
【００１５】
マッチングのステップおよびジャンクションのステップ２２、２４が完了すると、ステップ２６において、軌跡線分は関連するネットワーク要素と結合（統合、マージ）される。このことは以下でより詳細に記述されており、結合アルゴリズムおよび方法論が利用される。最後に、ステップ１８においてネットワークテーブルを更新する前に、形状地点の数を低減するためにネットワーク要素を単純化することが可能である。この任意の単純化ステップは機能ブロック２８に示されており、既知のダグラス・ポーカーのアルゴリズムの適用を含む、様々な技術を通じて達成されうる。
【００１６】
図４を参照すると、デジタルベクトルマップの単純化表現が３０において全体として示されている。デジタルベクトルマップ３０は、車道、歩道等のデジタルマップを表してもよい。デジタルベクトルマップ３０は、Ｎ１、Ｎ２、Ｎ３、…、Ｎ８とラベル付けされた共通節点によって端点間が接続された複数の線分によって表現されている。したがって、デジタルベクトルマップ３０は、この例では、周知の通り、各線分がジオコード情報によってマップの座標系と（座標系内で）関連付けられているデジタルマップとして存在する。ここで図４においても、全体として３２において示されている軌跡線が存在する。軌跡線３２は、図３に関連して上述したように、プローブ１４からの無線信号または他の無線技術によって生成された複数のプローブデータ点Ｐ１、Ｐ２、Ｐ３、…、Ｐ８によって生成される。有向性は、軌跡線３２上でデータ地点Ｐ１−Ｐ８を相互接続するベクトルによって表現される。本発明の方法は、軌跡線３２のどの部分がデジタルベクトルマップ３０とマッチされるべきか、軌跡線３２のどの部分がデジタルベクトルマップ３０に従前に含まれていなかった拡張（すなわち新しい）マップデータを表すのか、および、軌跡線３２の拡張部分とデジタルベクトルマップ３０との間のどこに具体的にジャンクション地点が構築されるべきかを判定することによって、デジタルベクトルマップ３０を改良することに適している。
【００１７】
図５を参照すると、オフセットおよび寸法の割り当て値と一緒に、デジタルベクトルマップ３０および軌跡線３２が示されている。オフセットは、軌跡線３２上のプローブデータ点からデジタルベクトルマップ３０までの最短距離として規定されている。軌跡線３２のデータ地点Ｐ１、Ｐ２、Ｐ３、Ｐ４およびＰ５のオフセットは、図５において両端同形の矢印で描写されている。寸法は、ネットワーク要素の第１の地点（デジタルベクトルマップ３０における節点Ｎ１）から、ネットワーク要素３０への軌跡地点の正射影までの長さである。換言すれば、寸法は、特定のプローブデータ点のオフセット測定が行われる地点に至るまでのデジタルベクトルマップ３０の線分に沿った長さである。図５においては、寸法線（dimension line）３４が、軌跡線３２におけるデータ地点Ｐ５に対する寸法を表している。射影地点すなわちデジタルベクトルマップ３０の線分に沿ってオフセット測定が行われる地点は概して唯一のものではないので、寸法も概して唯一のものではない。この場合では、いくつかの射影地点の１つを選択することも必要であるかもしれない。軌跡線ｐの地点ｐｉをネットワーク要素ｗとマッチングさせるために、以下の条件が順守されなければならない。
ａ．ｗに対するｐｉのオフセットは、所定の最大オフセット値よりも小さくなければならない。
ｂ．所定の最大オフセット値よりも小さいｗに対するオフセットを有する少なくともｎ個の接続地点ｐｋ、…、ｐｋ＋ｎ−１（ｋ≦ｉ＜ｋ＋ｎ）が存在しており、ここでｎは２以上の固定数である。
ｃ．地点ｐｊおよびｐｌのネットワーク要素ｗに対する寸法ｍ（ｐｊ，ｗ）、ｍ（ｐｌ，ｗ）について、ｋ≦ｊ＜ｌ＜ｋ＋ｎならｍ（ｐｊ，ｗ）≦ｍ（ｐｌ，ｗ）。
【００１８】
したがって、デジタルベクトルマップ３０における二以上の要素がこれらの条件を満たす可能性がある。例えば、デジタルベクトルマップ３０は、相互に非常に近接しているデジタルベクトルマップ要素を含んでもよく、軌跡線３２におけるデータ地点は両者に近接している。軌跡線３２をデジタルマップとマッチングするために、軌跡線３２とマッチするより良いネットワーク要素を識別するための戦略が必要とされる。１つの戦略例として、上記条件を満たす一連の接続地点における第１の地点の最小オフセットを有するネットワーク要素が使用されてもよい。双方向マップのマッチングの場合、上記の条件（ｃ．）を修正する必要があるかもしれない。
【００１９】
軌跡線３２のデータ地点Ｐ１、Ｐ２、Ｐ３、Ｐ４およびＰ５について、これらは線分とマッチングされる。しかしながら、データ地点Ｐ６、Ｐ７およびＰ８は、これらの地点のオフセットは所定の最大オフセット値よりも長いのでマッチングされない。予め構築された任意の条件または仕様に従って、所定の最大オフセット値が選択されうる。任意の所与の状況で最良のネットワーク要素を選択するために様々な技術が採用されてもよい。１つの可能性のある戦略は、ヒステリシス効果のようなものを実施することであってもよい。別の可能性は、隣接する従前の軌跡地点への方向、すなわち方角（heading）を使用することである。後者の有向戦略を使用すると、ｎ＝１を設定することが可能である。もちろん、両方の戦略（ヒステリシスおよび方角）を一緒に使用することも可能である。
【００２０】
上述のマップマッチング技術を通じて、軌跡線３２は、同様にマッチしたネットワーク要素を有するいくつかのセグメントまたは枝（データ地点Ｐ１−Ｐ５）、あるいは、任意のネットワーク要素とマッチしないいくつかのセグメントまたは枝（データ地点Ｐ６−Ｐ８）に分割されてもよい。これに対して、マッチしたネットワーク要素３０は、軌跡線３２とマッチしない２つのセグメントに至るまで、軌跡線３２とマッチした１つのセグメントにされる。目的は、線分の関連する部分で、軌跡線３２のマッチしたセグメントを結合（統合、マージ）することである。あるいは前記別の方法では、目的は、以下に詳細に記述されるように、計算された中央線を通るネットワーク要素３０を置換または再配置することである。それ故、デジタルベクトルマップ３０における線分から、軌跡線データ地点Ｐ６−Ｐ８によって表現されるような新しいまたは拡張されたネットワークの部分を増殖させるために、デジタルベクトルマップ３０における線分が分割されるべきである位置を判定する必要がある。この地点において、新しいジャンクションが挿入されるだろう。
【００２１】
分割地点すなわちジャンクションを判定するための様々な方法または技術が存在する。ジャンクションを発見するための１つの単純な技術は、ネットワーク要素３０とマッチした軌跡線３２の最後の地点を使用することである。図６または図７の例では、軌跡線３２に沿ったプローブデータ点Ｐ５が、ネットワーク要素３０とマッチした最後の地点である。この地点は、ネットワーク要素３０上の最近接地点へ射影される。ジャンクション地点“ｒ”は、ネットワーク要素３０に沿って存在する射影地点と、プローブデータ点Ｐ５との間での加重平均として算出される。重みは、軌跡線３２とデジタルベクトルマップ３０における線分との両方について設定される。
【００２２】
重みは、線分ｗのジャンクションＪ、すなわちネットワーク要素３０のジャンクションＮ１およびＮ８についても設定されうる。ジャンクションＪに重みを割り当てることは、アルゴリズムがジャンクションＪを計算あるいは移動することをより容易に可能にする。しかしながら、これは、特定の重みがジャンクションと関連付けられていない主題となるアルゴリズムの現在のバージョン等の任意の特徴である。ジャンクションの重みが所望される場合、ジャンクションの重みは、隣接線分ｗの重みから計算され、あるいは別個の重み割り当て技術から計算されうる。さらにその上、線分ｗの重みのより微細なセグメンテーションを使用することが可能である。そのような状況においては、線分ｗの種々の部分と種々の重みとを関連付けることは役立つことかもしれない。例えば、重みを、線分ｗにおける個々の形状地点ＳＰと関連付けることができる。重みを、線分の一部と関連付けるための別の可能性は、寸法範囲と一緒に重み値のリストを、各線分ｗと関連付けることである。もちろん、多くの他のバリエーションも可能である。単純化のため、軌跡線３２の重みは１に設定されてもよい。ネットワーク要素３０の重みは、様々な方法で構築されてもよいが、ここではデジタルベクトルマップ要素３０が作成された従前の軌跡の数として設定される。これらの例では、デジタルベクトルマップ３０は２つの前の軌跡線イベントから作成されたことが想定される。結果として、この例ではデジタルベクトルマップ３０の重みは２である。例えば、デジタルベクトルマップ３０が１５または２０または２５の前の軌跡線の結果であるなら、デジタルベクトルマップ３０の重みは１５または２０または２５に設定される。分割地点ｒが構築される平均は、図７に示されるように算出されてもよく、文字ｘはデジタルベクトルマップ３０の線重みを表している。この例では、デジタルベクトルマップ３０の線重みは２に等しく、地点ｒは、デジタルベクトルマップ３０からオフセット距離の３分の１（すなわち、１／（２＋１））距離を空けて配置される。換言すれば、プローブデータ点Ｐ５は、ネットワーク要素３０とマッチした軌跡線３２の最後の地点であり、加重平均の算出により新しいジャンクション地点すなわち節点ｒが、元のネットワーク要素３０から１／３の距離に配置される。
【００２３】
さらに図６を参照すると、地点ｒは、ジャンクション地点、すなわち軌跡線３２のマッチしないデータ地点Ｐ６、Ｐ７およびＰ８がデジタルベクトルマップ３０と交差する地点、の良い選択であるかもしれない。しかしながら、ジャンクション地点ｒを特定するための上述の技術は、全ての状況あるいは全てのタイプの適用に適していないかもしれない。代替技術は、最も大きな寸法を有する、および所定の最大オフセット値よりも小さい軌跡線に沿って最後にマッチした地点（この例ではＰ５）に対するオフセットを有する、デジタルベクトルマップ３０に沿った地点を探索することである。この地点の寸法が、射影地点（すなわち、オフセット寸法がデジタルベクトルマップ３０に接触する地点）の寸法よりも大きいなら、この分割地点すなわちジャンクション地点を計算するために、より大きなこの地点（Ｎ６）を使用することが好適かもしれない。図６において、Ｐ５に対する地点Ｎ６のオフセットが所定の最大オフセット値よりも小さいことが想定されるなら、これはデータ地点Ｎ５というよりもむしろネットワークデータ地点Ｎ６である。この場合、新しいジャンクション地点“ｓ”が、地点の加重平均および軌跡線３２への射影と同様の方法で計算されうる。このことは、図６において地点ｓを新しいジャンクションと称することによって説明されている。それ故、所定の最大オフセット値に依存して、種々の分割地点すなわちジャンクション地点が算出されてもよい。
【００２４】
しかしながら、事実上、多くの異なる場合を考慮する必要があるかもしれない。例えば、反対に連続する地点があるかもしれず、あるいは軌跡線３２の端点またはネットワーク要素３０の端点があるかもしれない。場合によっては、計算されたジャンクション付近の予め存在するジャンクションを使用することが可能である。正確なジャンクション地点を計算することは、デジタルベクトルマップ３０が更新されるにつれて当該デジタルベクトルマップ３０へ大きな影響を及ぼすだろう。当業者は、ジャンクション地点の作成、修正、または選択と関連して多くの変形が実施されうることを理解するだろう。軌跡線３２および／またはネットワーク要素３０の重要なエリアにおいては追加のプローブデータ点を挿入することが、いくつかの状況下では望ましいかもしれない。あるいは、ジャンクション地点は、純粋に数学的な算出あるいは主観的な標準を使用して、あるいは追加的参照データを参照することによって、プローブデータ点に全く依存することなく計算されうる。
【００２５】
ジャンクション地点が特定されると、デジタルベクトルマップ３０を正式に分割する必要がある。このことは、図８に示されるように、推定ジャンクション地点を、線分における実際の節点として選ぶことによって達成されてもよい。図８において、デジタルベクトルマップ３０のマッチしない部分は、データ地点Ｐ６、Ｐ７およびＰ８からなる。したがって、デジタルベクトルマップ３０は新しいジャンクション地点ｓで分割されている。軌跡線３２のマッチしない部分は、容易にネットワークへ追加される。地点Ｎ７から新しいジャンクション地点ｓまでネットワーク要素３０を接続することのみ必要である。
【００２６】
更新動作を完了する前に、線分３０は、計算された中央線へ置換あるいは再配置される。すなわち、軌跡線３２のマッチした部分と、デジタルベクトルマップ３０との間の中央線を作成することによって、軌跡線３２はデジタルベクトルマップ３０と結合（統合、マージ）される。新しい中央線を計算するために、軌跡線３２のマッチした各データ地点（すなわち、データ地点Ｐ１、Ｐ２、Ｐ３、Ｐ４およびＰ５）は、上述のオフセット距離方法論を使用して、デジタルベクトルマップ３０へ射影される。そのような各オフセット距離について、図７に関連して上述した方法の後に、２つの地点間で加重平均が計算される。同様に、軌跡線３２の重みは、１に設定されてもよく、その一方デジタルベクトルマップ３０の重みは、それが作成された前の軌跡の数である。それ故、地点Ｐ５の結合は新しいデータ地点ｒに帰結し、それは中央線の節点になる。さらなるデータ地点を取得し、それによってネットワークデータの正確性を強調するために、デジタルベクトルマップ３０からマッチングした地点（すなわち、Ｎ２、Ｎ３、Ｎ４、およびＮ５）が、図８に示されるような類似の正射影を使用して軌跡線３２とマッチングされる。それぞれのオフセットに沿って配置された節点地点によって表現されるように、これらのオフセットについても加重平均が計算される。
【００２７】
これらの新しく計算された全ての平均地点は、ともに中央線を有する線分として接続される。計算された中央線の重みは、前のデジタルベクトルマップ３０および軌跡線３２の重みの合計であり、継続する例では３である。従って、次にプローブデータ点が更新されたデジタルベクトルマップとマッチされるときは、それは破線３６によって表され、線重みは３であろう。このステップの後、更新されたネットワーク要素３６は、テーブル１８における従前のデジタルベクトルマップ３０を、その節点地点および計算された重みで置換する。それ故、各マッチした軌跡線３２で、更新されたネットワーク要素線３６はますます多くのデータ地点すなわち節点を含む。従って、配置を単純化することを通じてこれらのデータ地点のいくつかを除去することは役立つことかもしれない。そうした目的のために、かねて定評のあるダグラス・ポーカーのアルゴリズムが使用されてもよい。
【００２８】
当業者は、この技術の様々な改良および拡張を想像してもよい。例えば、これらの技術を用いて、平均速度、道路分類、高度、傾斜の値等のいくつかの道路属性の計算を具体化することが予測できる。例えば、高度の計算は、通常の二次元マップへの追加属性、または追加の次元として単純に理解されうる。後者の場合、マップ全体は三次元マップとして考えられうる。ネットワーク全体の生成および改良のプロセスが、この三次元マップに適用されうる。三次元軌跡を三次元マップとマッチングする際、三次元中央線等が計算されうる。もちろん、全ての軌跡地点について、および予め存在するマップについても、高度値が利用可能であると想定しなければならない。不完全なデータでも属性を計算することが可能なので、これは最初のケースでは必要ではない。さらにその上、生成された配置およびいくつかの属性のために信頼モデルが開発されうる。交差路および分岐路でのターン行動の検出は、当該ターン行動を表現するための適切なデータモデリングに関連して実施されうる。さらにその上、一時停止標識および信号が推定あるいは検出されうる。これらの技術の適切な拡張により、双方向ネットワークが生成されうる。これらの技術によって、過負荷なデータ記憶やデータ処理資源なしに、古いデータから生成されたネットワーク要素が最新な状態に保たれうる。
【００２９】
前述の発明は関連する法的基準に従って記述されており、それ故、当該記述は実際限定的ではなく例示的なものである。開示された実施形態への変形および修正が当業者にとって明らかになってもよく、本発明の範囲内であってもよい。したがって、本発明に与えられる法的保護の範囲は、以下の特許請求の範囲によってのみ規定されるものである。
【技術分野】
【０００１】
本出願は、２００９年１０月２２に出願された国際出願番号PCT/EP2009/063938の国際段階であり米国を指定している。本願の全内容はここに参照により組み込まれている。
【０００２】
本発明は、一般にプローブデータを使用してデジタルベクトルマップを更新および拡張する方法に関し、特に、１以上のパーソナルナビゲーション装置によって生成されたＧＰＳ座標を使用してデジタル車歩道マップを改良する方法に関する。
【背景技術】
【０００３】
ナビゲーションシステム、（デジタルマップとしても知られている）電子マップ、および地理的位置決め装置が、移動者および／または車両の総合的な位置および方位を判定する、目的地および住所を見つける、最適ルートを計算する、およびリアルタイムでの運転ガイダンスを提供する等の、様々なナビゲーション機能を補助するために移動者によってますます使用されている。一般に、ナビゲーションシステムは、ストリートのネットワークを、各ストリートまたは経路の中央に沿って走るセンターラインを含む一連の線分として表現する小型ディスプレイ・スクリーンまたはグラフィカル・ユーザ・インタフェースを含む。移動者は、その場合一般にそのセンターラインに近接して、あるいはセンターラインに関してデジタルマップ上に配置されうる。
【０００４】
道路情報を示し、処理するには非常に費用を要するので、デジタルマップを生成および更新するには費用がかかる。方法を調査したり、あるいは衛星画像をデジタル化したりすることは、デジタルマップを作成するために一般的に採用される技術である。さらにその上、デジタルマップは、欠陥のある、あるいは不正確な入力源、または不備のある推論方式が原因で、不正確性またはシステマチック誤差を含む可能性が高い。ひとたびデジタルマップが作成されると、道路配置は時間とともに変化するので、マップ情報を最新に保つには費用を要する。世界のいくつかの地域では、デジタルマップは全く利用不可能である。
【０００５】
図１Ａ―図１Ｃは、道路形式でデジタルベクトルマップを描写している。図１Ａは、主要な高速道路または運転ルートを表している。図１Ｂは、図１Ａの主要な高速道路に加えて、周辺（第２の）道路の相互接続ネットワークを描写している。図１Ｃは、図１Ｂの全ての情報と共に、第３のストリートおよび路地の拡張ネットワークを描写している。これらの図を参照することによって理解されるように、デジタルマップを生成するために費用および努力が必要なのと併せて、既存の車道マップまたはネットワークが、所与の領域内の全ての車道または経路の描写において不完全であることが事実であるかもしれない。さらにその上、車道および経路を含んでもよいがこれらに限定されないネットワークの発展性が原因で、時間と共に変化が起こるかもしれず、既存のデジタルマップは現状をもはや正確に表現していないかもしれない。
【０００６】
図２において、デジタルベクトルマップは、ジャンクションＪおよび線分Ｗ１、…、Ｗ９を含む。それらは共に、いくつかの追加プロパティを有するグラフを構成する。ジャンクションＪはノード（節点）であり、線分Ｗはグラフのエッジである。グラフは単方向マップ向けであり、双方向マップ向けではない。全ての線分Ｗは２つのジャンクションＪを接続する。それどころか、各ジャンクションＪにおいて、ちょうど１つあるいは少なくとも３つの線分Ｗが合流する（例外的な場合のみ、１つのジャンクションで２つの線分が合流するだろう）。ジャンクションＪおよび線分Ｗは通常、例えば重み値、寸法（measure）および方角（heading）等を含むいくつかの属性と関連付けられている。線分Ｗの配置は、（多角形曲線、多角形経路、または区分線形曲線とも呼ばれる）多角形チェーンとしてしばしば記述される。あるいは、スプライン曲線、円形セグメントまたはクロイド曲線等の他の曲線も使用できる。しかしながら、各曲線は、多角形チェーンにより十分正確に近似されうるので、通常は多角形チェーンが使用される。多角形チェーンの頂点すなわち節点は、曲線の形状を規定するので、形状地点（ＳＰ）と呼ばれる。もちろん、例えば属性が変化した場合などの適切な状況下では、ジャンクションＪに対する形状地点ＳＰを変更することが可能である。
【０００７】
図２は、デジタルベクトルマップの一部のセクションを説明しており、この場合、双方向交通をサポートする双方向車道である。幹線車道が１０で示されており、幹線車道１０から全体として垂直に延びる支線（分岐）道路が１２で示されている。例えば、あるクラスタリング技術を使用してマップを徐々に学習する目的で、一体型ＧＰＳ機能を有する低コスト位置決めシステムおよび携帯用装置および携帯電話から、プローブデータ入力を取得することが既知である。処理されるべき入力は、ほとんど全てのＧＰＳ装置によってサポートされている標準ＡＳＣＩＩストリームの形式で記録されたＧＰＳ軌跡から成る。出力は、移動時間情報付きの節点およびエッジ（端）を有する有向グラフの形式での道路マップである。ナビゲーション装置を装着して幹線車道１０および支線道路１２のジャンクションを移動する移動者は、従って、規則正しい距離で作成された節点を有する、図４に示されるマップのような軌跡マップを作成してもよい。節点およびエッジは、デジタルベクトルマップテーブルまたはデータベースに格納される。付加的アプローチを表すこの技術を通じて、道路配置が推定され、収集されたデータ地点がフィルタリングアルゴリズムおよび分割アルゴリズムによって改良されうる。この技術に関するより完全な議論のために、“Incremental Map Generaltion with GPS Traces（ＧＰＳ軌跡を用いた付加的マップ生成）” Briintrup, R., Edelkamp, S., Jabbar, S., Scholz, B., Proc. 8th Int. IEEE Conf. on Intelligent Transportation Systems, Vienna, Austria, 2005, Pages 413-418.への参照がなされる。
【０００８】
Tele Atlas B.V.のH.-U. OttoおよびO. Schmelzleによって開発された別の技術は、局所アプローチに基づいて、プローブデータから新しい道路ネットワークを生成する。このアプローチは、各軌跡をたどり、個別の軌跡地点付近のバッファを検証して線分（ラインセグメント）を構築する技術に基づいている。新しいネットワーク要素、例えば車道および歩道が、バッファ内部のデータ地点の分布および関連するベクトル方向に依存して生成される。ＧＰＳ軌跡または他のプローブデータを使用して新しいマップを生成する際にこの技術は役立つ一方、既存のネットワークを改良することには十分適していない。
【０００９】
したがって、既存ネットワークを改良し、およびデジタルマップ作成の実施等に際して採用される新しいネットワーク要素を生成するために、ＧＰＳ使用可能なナビゲーション装置からのデータ等のプローブデータを受信する方法を改良する必要がある。
【発明の概要】
【００１０】
本発明は、様々な先行技術の欠点および欠陥を克服するものである。プローブデータからの任意のタイプの軌跡、最も好適にはＧＰＳ軌跡、を使用してデジタルベクトルマップを生成し、改良し、および拡張する方法を提供する。前記方法は、座標系と空間的に関連付けられた複数の線分を格納するように構成されたデジタルベクトルマップを提供する工程と、前記デジタルベクトルマップの各線分と重み値とを関連付ける工程と、複数の連続して送信されたプローブデータ点から少なくとも１つのＧＰＳ軌跡を収集する工程と、マップマッチング基準を構築する工程と、前記マップマッチング基準を使用して、前記ＧＰＳ軌跡に沿った各プローブデータ点を、前記デジタルベクトルマップの前記線分と比較する工程と、を備える。前記方法は、前記マップマッチング基準を満たす前記ＧＰＳ軌跡に沿った各プローブデータ点を“マッチする”と指定し、一方、前記マップマッチング基準を満たさない前記ＧＰＳ軌跡に沿った各プローブデータ点を“マッチしない”と指定する工程と、マッチしたプローブデータ点を含む前記ＧＰＳ軌跡の部分を、前記デジタルベクトルマップの（あるなら）それぞれの線分と関連付ける工程と、前記線分の前記重み値を使用して、前記それぞれの線分と、対応するマッチしたプローブデータ点を含む前記ＧＰＳ軌跡の任意の部分との間の中央線を計算する工程と、前記中央線を通じて前記線分を置換する工程と、マッチしなかったプローブデータ点を含む前記ＧＰＳ軌跡の前記部分で前記デジタルベクトルマップの新しい線分を作成する工程と、を備えることを特徴とする。
【００１１】
前記マップマッチング基準は、様々な適切な方法で構築されうる。１つの方法によれば、各プローブデータ点と前記デジタルベクトルマップにおける線分とのオフセット距離が計算される。所定の最大オフセット値も構築され、前記最大オフセット値よりも小さいと算出されたオフセット距離を有するプローブデータ点が、マッチしたプローブデータ点として指定される。反対に、前記最大オフセット値よりも大きいと算出されたオフセット距離を有するプローブデータ点は、マッチしなかったプローブデータ点として指定される。
【００１２】
この方法によって、道路マップ、自転車マップおよび歩道マップ等に使用されるマップ等の既存のデジタルベクトルマップは、収集されたプローブデータを使用して改良されうる。品質が改良されたデジタルベクトルマップは、デジタルベクトルマップにおいて支線道路（branch）、結合地点（merge）、および交差点をより正確に検出するために使用されることができ、単方向ネットワークおよび双方向ネットワークの両方を生成するために使用されてもよく、および、大規模ネットワークエリアに対して大量のプローブデータを計算する場合実質的な効率向上をもたらす。さらにその上、本発明の全体概念は、車道マップおよび歩道マップだけではなく、任意のデジタルベクトルマップを改良するために使用されうる。座標系と空間的に関連付けられうる、例えば、回路図、結線図（schematic）、および他のグラフィック描写が、本発明の技術の利益を享受する。
【図面の簡単な説明】
【００１３】
【図１Ａ】、
【図１Ｂ】、
【図１Ｃ】図１Ａ−１Ｃは、デジタルベクトルマップの１つの形式の表現として車道ネットワークを表現しており、図１Ａは幹線道路を示し、図１Ｂは相互接続ネットワークを示し、および図１Ｃはストリートネットワークを示す。
【図２】図２は、ジャンクション、線分、および形状地点を示す、支線道路によりジャンクションにおいて交差される幹線道路を有する道路マップのデジタルベクトルマップの単純化された表現である。
【図３】図３は、主題の方法の外観を描写する概略図であり、複数のＧＰＳ使用可能なナビゲーション装置からプローブデータが収集され、テーブルに格納され、および、デジタルベクトルマップを改良および／または拡張するために予め存在するデジタルベクトルマップにおける線分とマッチングされる。
【図４】図４は、プローブデータ点から生じる軌跡線が、デジタルベクトルマップにおける予め存在する要素と共に座標系に最初に設定される方法の説明図である。
【図５】図５は、図４のような図であるが、寸法（measure）の算出、および、デジタルベクトルマップにおける線分と収集されたデータ地点との間のオフセット距離の算出を描写している。
【図６】図６は、図５の拡大図であり、新しいジャンクションがデジタルベクトルマップへ挿入されてもよい任意分割地点を描写する。
【図７】図７は、図６における外接エリアの拡大図であり、線分を分割するために新しいジャンクションを計算する工程に関連する。
【図８】図８は、本発明の技術を使用して更新されたデジタルベクトルマップを描写する。
【発明を実施するための形態】
【００１４】
図面を参照する際、同じ数字は、いくつかの図面を通じて同一のまたは対応する部分を示しており、主題となる発明は図３において概略的に描写される。ここで、複数のプローブ１４が、TomTom NV (www.tomtom.com)によって製造された装置等のＧＰＳ使用可能なパーソナルナビゲーション装置として描写されている。しかしながら、携帯用装置、携帯電話、ＰＤＡ等を含む、ＧＰＳ機能を有するあらゆる適切な装置がプローブデータ点を生成するために使用されてもよい。プローブデータ点は、収集されて、プローブデータテーブル１６あるいは他の適切なデータベースまたは保存場所に格納される。既存のデジタルベクトルマップ、この例では予め作成されたデジタルマップは、テーブル１８に含まれる。もちろん、デジタルベクトルマップ１８は、データベースあるいは他の適切な形式で存在しうる。初期ステップとして、テーブル１６における概略プローブデータから軌跡線が生成される。ステップ２０において、新しい線がプローブデータテーブルから選択される。ステップ２２において、選択された線は、デジタルベクトルマップとマッチングされる。このステップの間、以下でより詳細に記述されるようなマップマッチング方法を使用して、軌跡線の各地点がネットワーク要素と関連付けられるだろう。そのマッチング方法で任意のネットワーク要素を軌跡線と関連付けることが可能ではないなら、プローブデータ点は“マッチしない”としてマークされる。全ての他のプローブデータ点は、この方法で既存ネットワークとマッチングされることを試みられる。データ地点が既存ネットワークの任意の要素とマッチしていない軌跡線分については、これらは、ネットワーク要素から分割され、新しいジャンクションまたは既存のジャンクションによって挿入され、あるいは接続されなければならない。これはステップ２４において起こる。場合によっては、既知あるいは予め存在するジャンクションを使用することが合理的である。ジャンクションは、車道ネットワークアプリケーションにおいて交差点と称されてもよい。時々、既存のジャンクションは正確な位置になく、必要に応じて除去されるだろう。いくつかの例では、以下に記述される技術に従って、新しいジャンクションが作成される必要があるだろう。
【００１５】
マッチングのステップおよびジャンクションのステップ２２、２４が完了すると、ステップ２６において、軌跡線分は関連するネットワーク要素と結合（統合、マージ）される。このことは以下でより詳細に記述されており、結合アルゴリズムおよび方法論が利用される。最後に、ステップ１８においてネットワークテーブルを更新する前に、形状地点の数を低減するためにネットワーク要素を単純化することが可能である。この任意の単純化ステップは機能ブロック２８に示されており、既知のダグラス・ポーカーのアルゴリズムの適用を含む、様々な技術を通じて達成されうる。
【００１６】
図４を参照すると、デジタルベクトルマップの単純化表現が３０において全体として示されている。デジタルベクトルマップ３０は、車道、歩道等のデジタルマップを表してもよい。デジタルベクトルマップ３０は、Ｎ１、Ｎ２、Ｎ３、…、Ｎ８とラベル付けされた共通節点によって端点間が接続された複数の線分によって表現されている。したがって、デジタルベクトルマップ３０は、この例では、周知の通り、各線分がジオコード情報によってマップの座標系と（座標系内で）関連付けられているデジタルマップとして存在する。ここで図４においても、全体として３２において示されている軌跡線が存在する。軌跡線３２は、図３に関連して上述したように、プローブ１４からの無線信号または他の無線技術によって生成された複数のプローブデータ点Ｐ１、Ｐ２、Ｐ３、…、Ｐ８によって生成される。有向性は、軌跡線３２上でデータ地点Ｐ１−Ｐ８を相互接続するベクトルによって表現される。本発明の方法は、軌跡線３２のどの部分がデジタルベクトルマップ３０とマッチされるべきか、軌跡線３２のどの部分がデジタルベクトルマップ３０に従前に含まれていなかった拡張（すなわち新しい）マップデータを表すのか、および、軌跡線３２の拡張部分とデジタルベクトルマップ３０との間のどこに具体的にジャンクション地点が構築されるべきかを判定することによって、デジタルベクトルマップ３０を改良することに適している。
【００１７】
図５を参照すると、オフセットおよび寸法の割り当て値と一緒に、デジタルベクトルマップ３０および軌跡線３２が示されている。オフセットは、軌跡線３２上のプローブデータ点からデジタルベクトルマップ３０までの最短距離として規定されている。軌跡線３２のデータ地点Ｐ１、Ｐ２、Ｐ３、Ｐ４およびＰ５のオフセットは、図５において両端同形の矢印で描写されている。寸法は、ネットワーク要素の第１の地点（デジタルベクトルマップ３０における節点Ｎ１）から、ネットワーク要素３０への軌跡地点の正射影までの長さである。換言すれば、寸法は、特定のプローブデータ点のオフセット測定が行われる地点に至るまでのデジタルベクトルマップ３０の線分に沿った長さである。図５においては、寸法線（dimension line）３４が、軌跡線３２におけるデータ地点Ｐ５に対する寸法を表している。射影地点すなわちデジタルベクトルマップ３０の線分に沿ってオフセット測定が行われる地点は概して唯一のものではないので、寸法も概して唯一のものではない。この場合では、いくつかの射影地点の１つを選択することも必要であるかもしれない。軌跡線ｐの地点ｐｉをネットワーク要素ｗとマッチングさせるために、以下の条件が順守されなければならない。
ａ．ｗに対するｐｉのオフセットは、所定の最大オフセット値よりも小さくなければならない。
ｂ．所定の最大オフセット値よりも小さいｗに対するオフセットを有する少なくともｎ個の接続地点ｐｋ、…、ｐｋ＋ｎ−１（ｋ≦ｉ＜ｋ＋ｎ）が存在しており、ここでｎは２以上の固定数である。
ｃ．地点ｐｊおよびｐｌのネットワーク要素ｗに対する寸法ｍ（ｐｊ，ｗ）、ｍ（ｐｌ，ｗ）について、ｋ≦ｊ＜ｌ＜ｋ＋ｎならｍ（ｐｊ，ｗ）≦ｍ（ｐｌ，ｗ）。
【００１８】
したがって、デジタルベクトルマップ３０における二以上の要素がこれらの条件を満たす可能性がある。例えば、デジタルベクトルマップ３０は、相互に非常に近接しているデジタルベクトルマップ要素を含んでもよく、軌跡線３２におけるデータ地点は両者に近接している。軌跡線３２をデジタルマップとマッチングするために、軌跡線３２とマッチするより良いネットワーク要素を識別するための戦略が必要とされる。１つの戦略例として、上記条件を満たす一連の接続地点における第１の地点の最小オフセットを有するネットワーク要素が使用されてもよい。双方向マップのマッチングの場合、上記の条件（ｃ．）を修正する必要があるかもしれない。
【００１９】
軌跡線３２のデータ地点Ｐ１、Ｐ２、Ｐ３、Ｐ４およびＰ５について、これらは線分とマッチングされる。しかしながら、データ地点Ｐ６、Ｐ７およびＰ８は、これらの地点のオフセットは所定の最大オフセット値よりも長いのでマッチングされない。予め構築された任意の条件または仕様に従って、所定の最大オフセット値が選択されうる。任意の所与の状況で最良のネットワーク要素を選択するために様々な技術が採用されてもよい。１つの可能性のある戦略は、ヒステリシス効果のようなものを実施することであってもよい。別の可能性は、隣接する従前の軌跡地点への方向、すなわち方角（heading）を使用することである。後者の有向戦略を使用すると、ｎ＝１を設定することが可能である。もちろん、両方の戦略（ヒステリシスおよび方角）を一緒に使用することも可能である。
【００２０】
上述のマップマッチング技術を通じて、軌跡線３２は、同様にマッチしたネットワーク要素を有するいくつかのセグメントまたは枝（データ地点Ｐ１−Ｐ５）、あるいは、任意のネットワーク要素とマッチしないいくつかのセグメントまたは枝（データ地点Ｐ６−Ｐ８）に分割されてもよい。これに対して、マッチしたネットワーク要素３０は、軌跡線３２とマッチしない２つのセグメントに至るまで、軌跡線３２とマッチした１つのセグメントにされる。目的は、線分の関連する部分で、軌跡線３２のマッチしたセグメントを結合（統合、マージ）することである。あるいは前記別の方法では、目的は、以下に詳細に記述されるように、計算された中央線を通るネットワーク要素３０を置換または再配置することである。それ故、デジタルベクトルマップ３０における線分から、軌跡線データ地点Ｐ６−Ｐ８によって表現されるような新しいまたは拡張されたネットワークの部分を増殖させるために、デジタルベクトルマップ３０における線分が分割されるべきである位置を判定する必要がある。この地点において、新しいジャンクションが挿入されるだろう。
【００２１】
分割地点すなわちジャンクションを判定するための様々な方法または技術が存在する。ジャンクションを発見するための１つの単純な技術は、ネットワーク要素３０とマッチした軌跡線３２の最後の地点を使用することである。図６または図７の例では、軌跡線３２に沿ったプローブデータ点Ｐ５が、ネットワーク要素３０とマッチした最後の地点である。この地点は、ネットワーク要素３０上の最近接地点へ射影される。ジャンクション地点“ｒ”は、ネットワーク要素３０に沿って存在する射影地点と、プローブデータ点Ｐ５との間での加重平均として算出される。重みは、軌跡線３２とデジタルベクトルマップ３０における線分との両方について設定される。
【００２２】
重みは、線分ｗのジャンクションＪ、すなわちネットワーク要素３０のジャンクションＮ１およびＮ８についても設定されうる。ジャンクションＪに重みを割り当てることは、アルゴリズムがジャンクションＪを計算あるいは移動することをより容易に可能にする。しかしながら、これは、特定の重みがジャンクションと関連付けられていない主題となるアルゴリズムの現在のバージョン等の任意の特徴である。ジャンクションの重みが所望される場合、ジャンクションの重みは、隣接線分ｗの重みから計算され、あるいは別個の重み割り当て技術から計算されうる。さらにその上、線分ｗの重みのより微細なセグメンテーションを使用することが可能である。そのような状況においては、線分ｗの種々の部分と種々の重みとを関連付けることは役立つことかもしれない。例えば、重みを、線分ｗにおける個々の形状地点ＳＰと関連付けることができる。重みを、線分の一部と関連付けるための別の可能性は、寸法範囲と一緒に重み値のリストを、各線分ｗと関連付けることである。もちろん、多くの他のバリエーションも可能である。単純化のため、軌跡線３２の重みは１に設定されてもよい。ネットワーク要素３０の重みは、様々な方法で構築されてもよいが、ここではデジタルベクトルマップ要素３０が作成された従前の軌跡の数として設定される。これらの例では、デジタルベクトルマップ３０は２つの前の軌跡線イベントから作成されたことが想定される。結果として、この例ではデジタルベクトルマップ３０の重みは２である。例えば、デジタルベクトルマップ３０が１５または２０または２５の前の軌跡線の結果であるなら、デジタルベクトルマップ３０の重みは１５または２０または２５に設定される。分割地点ｒが構築される平均は、図７に示されるように算出されてもよく、文字ｘはデジタルベクトルマップ３０の線重みを表している。この例では、デジタルベクトルマップ３０の線重みは２に等しく、地点ｒは、デジタルベクトルマップ３０からオフセット距離の３分の１（すなわち、１／（２＋１））距離を空けて配置される。換言すれば、プローブデータ点Ｐ５は、ネットワーク要素３０とマッチした軌跡線３２の最後の地点であり、加重平均の算出により新しいジャンクション地点すなわち節点ｒが、元のネットワーク要素３０から１／３の距離に配置される。
【００２３】
さらに図６を参照すると、地点ｒは、ジャンクション地点、すなわち軌跡線３２のマッチしないデータ地点Ｐ６、Ｐ７およびＰ８がデジタルベクトルマップ３０と交差する地点、の良い選択であるかもしれない。しかしながら、ジャンクション地点ｒを特定するための上述の技術は、全ての状況あるいは全てのタイプの適用に適していないかもしれない。代替技術は、最も大きな寸法を有する、および所定の最大オフセット値よりも小さい軌跡線に沿って最後にマッチした地点（この例ではＰ５）に対するオフセットを有する、デジタルベクトルマップ３０に沿った地点を探索することである。この地点の寸法が、射影地点（すなわち、オフセット寸法がデジタルベクトルマップ３０に接触する地点）の寸法よりも大きいなら、この分割地点すなわちジャンクション地点を計算するために、より大きなこの地点（Ｎ６）を使用することが好適かもしれない。図６において、Ｐ５に対する地点Ｎ６のオフセットが所定の最大オフセット値よりも小さいことが想定されるなら、これはデータ地点Ｎ５というよりもむしろネットワークデータ地点Ｎ６である。この場合、新しいジャンクション地点“ｓ”が、地点の加重平均および軌跡線３２への射影と同様の方法で計算されうる。このことは、図６において地点ｓを新しいジャンクションと称することによって説明されている。それ故、所定の最大オフセット値に依存して、種々の分割地点すなわちジャンクション地点が算出されてもよい。
【００２４】
しかしながら、事実上、多くの異なる場合を考慮する必要があるかもしれない。例えば、反対に連続する地点があるかもしれず、あるいは軌跡線３２の端点またはネットワーク要素３０の端点があるかもしれない。場合によっては、計算されたジャンクション付近の予め存在するジャンクションを使用することが可能である。正確なジャンクション地点を計算することは、デジタルベクトルマップ３０が更新されるにつれて当該デジタルベクトルマップ３０へ大きな影響を及ぼすだろう。当業者は、ジャンクション地点の作成、修正、または選択と関連して多くの変形が実施されうることを理解するだろう。軌跡線３２および／またはネットワーク要素３０の重要なエリアにおいては追加のプローブデータ点を挿入することが、いくつかの状況下では望ましいかもしれない。あるいは、ジャンクション地点は、純粋に数学的な算出あるいは主観的な標準を使用して、あるいは追加的参照データを参照することによって、プローブデータ点に全く依存することなく計算されうる。
【００２５】
ジャンクション地点が特定されると、デジタルベクトルマップ３０を正式に分割する必要がある。このことは、図８に示されるように、推定ジャンクション地点を、線分における実際の節点として選ぶことによって達成されてもよい。図８において、デジタルベクトルマップ３０のマッチしない部分は、データ地点Ｐ６、Ｐ７およびＰ８からなる。したがって、デジタルベクトルマップ３０は新しいジャンクション地点ｓで分割されている。軌跡線３２のマッチしない部分は、容易にネットワークへ追加される。地点Ｎ７から新しいジャンクション地点ｓまでネットワーク要素３０を接続することのみ必要である。
【００２６】
更新動作を完了する前に、線分３０は、計算された中央線へ置換あるいは再配置される。すなわち、軌跡線３２のマッチした部分と、デジタルベクトルマップ３０との間の中央線を作成することによって、軌跡線３２はデジタルベクトルマップ３０と結合（統合、マージ）される。新しい中央線を計算するために、軌跡線３２のマッチした各データ地点（すなわち、データ地点Ｐ１、Ｐ２、Ｐ３、Ｐ４およびＰ５）は、上述のオフセット距離方法論を使用して、デジタルベクトルマップ３０へ射影される。そのような各オフセット距離について、図７に関連して上述した方法の後に、２つの地点間で加重平均が計算される。同様に、軌跡線３２の重みは、１に設定されてもよく、その一方デジタルベクトルマップ３０の重みは、それが作成された前の軌跡の数である。それ故、地点Ｐ５の結合は新しいデータ地点ｒに帰結し、それは中央線の節点になる。さらなるデータ地点を取得し、それによってネットワークデータの正確性を強調するために、デジタルベクトルマップ３０からマッチングした地点（すなわち、Ｎ２、Ｎ３、Ｎ４、およびＮ５）が、図８に示されるような類似の正射影を使用して軌跡線３２とマッチングされる。それぞれのオフセットに沿って配置された節点地点によって表現されるように、これらのオフセットについても加重平均が計算される。
【００２７】
これらの新しく計算された全ての平均地点は、ともに中央線を有する線分として接続される。計算された中央線の重みは、前のデジタルベクトルマップ３０および軌跡線３２の重みの合計であり、継続する例では３である。従って、次にプローブデータ点が更新されたデジタルベクトルマップとマッチされるときは、それは破線３６によって表され、線重みは３であろう。このステップの後、更新されたネットワーク要素３６は、テーブル１８における従前のデジタルベクトルマップ３０を、その節点地点および計算された重みで置換する。それ故、各マッチした軌跡線３２で、更新されたネットワーク要素線３６はますます多くのデータ地点すなわち節点を含む。従って、配置を単純化することを通じてこれらのデータ地点のいくつかを除去することは役立つことかもしれない。そうした目的のために、かねて定評のあるダグラス・ポーカーのアルゴリズムが使用されてもよい。
【００２８】
当業者は、この技術の様々な改良および拡張を想像してもよい。例えば、これらの技術を用いて、平均速度、道路分類、高度、傾斜の値等のいくつかの道路属性の計算を具体化することが予測できる。例えば、高度の計算は、通常の二次元マップへの追加属性、または追加の次元として単純に理解されうる。後者の場合、マップ全体は三次元マップとして考えられうる。ネットワーク全体の生成および改良のプロセスが、この三次元マップに適用されうる。三次元軌跡を三次元マップとマッチングする際、三次元中央線等が計算されうる。もちろん、全ての軌跡地点について、および予め存在するマップについても、高度値が利用可能であると想定しなければならない。不完全なデータでも属性を計算することが可能なので、これは最初のケースでは必要ではない。さらにその上、生成された配置およびいくつかの属性のために信頼モデルが開発されうる。交差路および分岐路でのターン行動の検出は、当該ターン行動を表現するための適切なデータモデリングに関連して実施されうる。さらにその上、一時停止標識および信号が推定あるいは検出されうる。これらの技術の適切な拡張により、双方向ネットワークが生成されうる。これらの技術によって、過負荷なデータ記憶やデータ処理資源なしに、古いデータから生成されたネットワーク要素が最新な状態に保たれうる。
【００２９】
前述の発明は関連する法的基準に従って記述されており、それ故、当該記述は実際限定的ではなく例示的なものである。開示された実施形態への変形および修正が当業者にとって明らかになってもよく、本発明の範囲内であってもよい。したがって、本発明に与えられる法的保護の範囲は、以下の特許請求の範囲によってのみ規定されるものである。
【特許請求の範囲】
【請求項１】
プローブデータからの軌跡を使用してデジタルベクトルマップを生成し、改良し、および拡張する方法であって、
座標系と空間的に関連付けられた複数の線分を格納するように構成されたデジタルベクトルマップを提供する工程と、
前記デジタルベクトルマップの各線分と、重み値とを関連付ける工程と、
複数の連続して送信されたプローブデータ点から少なくとも１つの軌跡を収集する工程と、
マップマッチング基準を構築する工程と、
前記マップマッチング基準を使用して、前記軌跡に沿った各プローブデータ点を、前記デジタルベクトルマップの少なくとも１つの線分と比較する工程と、
前記マップマッチング基準を満たす前記軌跡に沿った各プローブデータ点を“マッチする”と指定し、一方、前記マップマッチング基準を満たさない前記軌跡に沿った各プローブデータ点を“マッチしない”と指定する工程と、
マッチしたプローブデータ点を含む前記軌跡の部分を、前記デジタルベクトルマップの少なくとも１つの線分と関連付ける工程と、
前記線分の前記重み値を使用して、前記それぞれの線分と、マッチしたプローブデータ点を含む前記軌跡の前記部分との間の中央線を計算する工程と、
前記中央線を通じて前記線分を置換する工程と、
を備えることを特徴とする方法。
【請求項２】
プローブデータからのＧＰＳ軌跡を使用してデジタルベクトルマップを生成し、改良し、および拡張する方法であって、
座標系と空間的に関連付けられた複数の線分を格納するように構成されたデジタルベクトルマップを提供する工程と、
前記デジタルベクトルマップの各線分と、重み値とを関連付ける工程と、
複数の連続して送信されたプローブデータ点から少なくとも１つのＧＰＳ軌跡を収集する工程と、
マップマッチング基準を構築する工程と、
前記マップマッチング基準を使用して、前記ＧＰＳ軌跡に沿った各プローブデータ点を、前記デジタルベクトルマップの少なくとも１つの線分と比較する工程と、
前記マップマッチング基準を満たす前記ＧＰＳ軌跡に沿った各プローブデータ点を“マッチする”と指定し、一方、前記マップマッチング基準を満たさない前記ＧＰＳ軌跡に沿った各プローブデータ点を“マッチしない”と指定する工程と、
マッチしたプローブデータ点を含む前記ＧＰＳ軌跡の部分を、前記デジタルベクトルマップのそれぞれの線分と関連付ける工程と、
前記線分の前記重み値を使用して、前記それぞれの線分と、マッチしたプローブデータ点を含む前記ＧＰＳ軌跡の前記部分との間の中央線を計算する工程と、
前記中央線を通じて前記線分を置換する工程と、
マッチしなかったプローブデータ点を含む前記ＧＰＳ軌跡の前記部分で前記デジタルベクトルマップの新しい線分を作成する工程と、
を備えることを特徴とする方法。
【請求項３】
前記デジタルベクトルマップは、前記少なくとも１つのＧＰＳ軌跡から新しいデジタルベクトルマップを生成するために、前記収集する工程より前に従前の線分を含んでいないことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記デジタルベクトルマップは、少なくとも１つの従前の線分を含んでおり、
前記新しい線分が前記デジタルベクトルマップの従前の線分に連結するジャンクションを計算する工程をさらに備えることを特徴とする請求項１乃至３の何れか１項に記載の方法。
【請求項５】
前記デジタルベクトルマップは、少なくとも１つの従前のジャンクションを含んでおり、
ジャンクションを計算する前記工程は、前記計算された新しいジャンクション近くの前記デジタルベクトルマップの従前のジャンクションを選ぶ工程を含むことを特徴とする請求項１乃至４の何れか１項に記載の方法。
【請求項６】
前記デジタルベクトルマップは、重み値を有する少なくとも１つの従前のジャンクションを含んでおり、
前記デジタルベクトルマップを改良するために、前記従前のジャンクションの前記重み値を使用して、前記計算されたジャンクションと前記デジタルベクトルマップの前記従前のジャンクションとを結合する工程をさらに含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記計算されたジャンクションに隣接する従前の線分を分割する工程をさらに含むことを特徴とする請求項４乃至６の何れか１項に記載の方法。
【請求項８】
ジャンクションとの線分の位相接続を作成する工程をさらに含むことを特徴とする請求項１乃至７の何れか１項に記載の方法。
【請求項９】
前記更新されたデジタルベクトルマップを単純化する工程をさらに含むことを特徴とする請求項１乃至８の何れか１項に記載の方法。
【請求項１０】
前記更新されたデジタルベクトルマップを単純化する工程は、ダグラス・ポーカーのアルゴリズムを適用する工程を含むことを特徴とする請求項１乃至９の何れか１項に記載の方法。
【請求項１１】
前記デジタルベクトルマップは、単方向ネットワークであることを特徴とする請求項１乃至１０の何れか１項に記載の方法。
【請求項１２】
前記デジタルベクトルマップは、双方向ネットワークであることを特徴とする請求項１乃至１０の何れか１項に記載の方法。
【請求項１３】
前記更新されたデジタルベクトルマップの属性を計算する工程をさらに含むことを特徴とする請求項１乃至１２の何れか１項に記載の方法。
【請求項１４】
属性を計算する前記工程は、前記線分の道路クラスを計算する工程をさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１５】
後処理操作において所定の閾値を下回る重み値を有する線分を前記デジタルベクトルマップから除去する工程をさらに含むことを特徴とする請求項１乃至１４の何れか１項に記載の方法。
【請求項１】
プローブデータからの軌跡を使用してデジタルベクトルマップを生成し、改良し、および拡張する方法であって、
座標系と空間的に関連付けられた複数の線分を格納するように構成されたデジタルベクトルマップを提供する工程と、
前記デジタルベクトルマップの各線分と、重み値とを関連付ける工程と、
複数の連続して送信されたプローブデータ点から少なくとも１つの軌跡を収集する工程と、
マップマッチング基準を構築する工程と、
前記マップマッチング基準を使用して、前記軌跡に沿った各プローブデータ点を、前記デジタルベクトルマップの少なくとも１つの線分と比較する工程と、
前記マップマッチング基準を満たす前記軌跡に沿った各プローブデータ点を“マッチする”と指定し、一方、前記マップマッチング基準を満たさない前記軌跡に沿った各プローブデータ点を“マッチしない”と指定する工程と、
マッチしたプローブデータ点を含む前記軌跡の部分を、前記デジタルベクトルマップの少なくとも１つの線分と関連付ける工程と、
前記線分の前記重み値を使用して、前記それぞれの線分と、マッチしたプローブデータ点を含む前記軌跡の前記部分との間の中央線を計算する工程と、
前記中央線を通じて前記線分を置換する工程と、
を備えることを特徴とする方法。
【請求項２】
プローブデータからのＧＰＳ軌跡を使用してデジタルベクトルマップを生成し、改良し、および拡張する方法であって、
座標系と空間的に関連付けられた複数の線分を格納するように構成されたデジタルベクトルマップを提供する工程と、
前記デジタルベクトルマップの各線分と、重み値とを関連付ける工程と、
複数の連続して送信されたプローブデータ点から少なくとも１つのＧＰＳ軌跡を収集する工程と、
マップマッチング基準を構築する工程と、
前記マップマッチング基準を使用して、前記ＧＰＳ軌跡に沿った各プローブデータ点を、前記デジタルベクトルマップの少なくとも１つの線分と比較する工程と、
前記マップマッチング基準を満たす前記ＧＰＳ軌跡に沿った各プローブデータ点を“マッチする”と指定し、一方、前記マップマッチング基準を満たさない前記ＧＰＳ軌跡に沿った各プローブデータ点を“マッチしない”と指定する工程と、
マッチしたプローブデータ点を含む前記ＧＰＳ軌跡の部分を、前記デジタルベクトルマップのそれぞれの線分と関連付ける工程と、
前記線分の前記重み値を使用して、前記それぞれの線分と、マッチしたプローブデータ点を含む前記ＧＰＳ軌跡の前記部分との間の中央線を計算する工程と、
前記中央線を通じて前記線分を置換する工程と、
マッチしなかったプローブデータ点を含む前記ＧＰＳ軌跡の前記部分で前記デジタルベクトルマップの新しい線分を作成する工程と、
を備えることを特徴とする方法。
【請求項３】
前記デジタルベクトルマップは、前記少なくとも１つのＧＰＳ軌跡から新しいデジタルベクトルマップを生成するために、前記収集する工程より前に従前の線分を含んでいないことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記デジタルベクトルマップは、少なくとも１つの従前の線分を含んでおり、
前記新しい線分が前記デジタルベクトルマップの従前の線分に連結するジャンクションを計算する工程をさらに備えることを特徴とする請求項１乃至３の何れか１項に記載の方法。
【請求項５】
前記デジタルベクトルマップは、少なくとも１つの従前のジャンクションを含んでおり、
ジャンクションを計算する前記工程は、前記計算された新しいジャンクション近くの前記デジタルベクトルマップの従前のジャンクションを選ぶ工程を含むことを特徴とする請求項１乃至４の何れか１項に記載の方法。
【請求項６】
前記デジタルベクトルマップは、重み値を有する少なくとも１つの従前のジャンクションを含んでおり、
前記デジタルベクトルマップを改良するために、前記従前のジャンクションの前記重み値を使用して、前記計算されたジャンクションと前記デジタルベクトルマップの前記従前のジャンクションとを結合する工程をさらに含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記計算されたジャンクションに隣接する従前の線分を分割する工程をさらに含むことを特徴とする請求項４乃至６の何れか１項に記載の方法。
【請求項８】
ジャンクションとの線分の位相接続を作成する工程をさらに含むことを特徴とする請求項１乃至７の何れか１項に記載の方法。
【請求項９】
前記更新されたデジタルベクトルマップを単純化する工程をさらに含むことを特徴とする請求項１乃至８の何れか１項に記載の方法。
【請求項１０】
前記更新されたデジタルベクトルマップを単純化する工程は、ダグラス・ポーカーのアルゴリズムを適用する工程を含むことを特徴とする請求項１乃至９の何れか１項に記載の方法。
【請求項１１】
前記デジタルベクトルマップは、単方向ネットワークであることを特徴とする請求項１乃至１０の何れか１項に記載の方法。
【請求項１２】
前記デジタルベクトルマップは、双方向ネットワークであることを特徴とする請求項１乃至１０の何れか１項に記載の方法。
【請求項１３】
前記更新されたデジタルベクトルマップの属性を計算する工程をさらに含むことを特徴とする請求項１乃至１２の何れか１項に記載の方法。
【請求項１４】
属性を計算する前記工程は、前記線分の道路クラスを計算する工程をさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１５】
後処理操作において所定の閾値を下回る重み値を有する線分を前記デジタルベクトルマップから除去する工程をさらに含むことを特徴とする請求項１乃至１４の何れか１項に記載の方法。
【図１Ａ】
【図１Ｂ】
【図１Ｃ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１Ｂ】
【図１Ｃ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公表番号】特表２０１３−５０８６９２（Ｐ２０１３−５０８６９２Ａ）
【公表日】平成２５年３月７日（２０１３．３．７）
【国際特許分類】
【出願番号】特願２０１２−５３４５５１（Ｐ２０１２−５３４５５１）
【出願日】平成２１年１０月２２日（２００９．１０．２２）
【国際出願番号】ＰＣＴ／ＥＰ２００９／０６３９３８
【国際公開番号】ＷＯ２０１１／０４７７２９
【国際公開日】平成２３年４月２８日（２０１１．４．２８）
【出願人】（５１２１０６６７６）トムトム ジャーマニー ゲーエムベーハー ウント コー． カーゲー (3)
【氏名又は名称原語表記】ＴＯＭＴＯＭ ＧＥＲＭＡＮＹ ＧＭＢＨ ＆ ＣＯ． ＫＧ
【住所又は居所原語表記】Ａｍ Ｎｅｕｅｎ Ｈｏｒｉｚｏｎｔ １ Ｄ−３１１７７ Ｈａｒｓｕｍ Ｇｅｒｍａｎｙ
【Ｆターム（参考）】
【公表日】平成２５年３月７日（２０１３．３．７）
【国際特許分類】
【出願日】平成２１年１０月２２日（２００９．１０．２２）
【国際出願番号】ＰＣＴ／ＥＰ２００９／０６３９３８
【国際公開番号】ＷＯ２０１１／０４７７２９
【国際公開日】平成２３年４月２８日（２０１１．４．２８）
【出願人】（５１２１０６６７６）トムトム ジャーマニー ゲーエムベーハー ウント コー． カーゲー (3)
【氏名又は名称原語表記】ＴＯＭＴＯＭ ＧＥＲＭＡＮＹ ＧＭＢＨ ＆ ＣＯ． ＫＧ
【住所又は居所原語表記】Ａｍ Ｎｅｕｅｎ Ｈｏｒｉｚｏｎｔ １ Ｄ−３１１７７ Ｈａｒｓｕｍ Ｇｅｒｍａｎｙ
【Ｆターム（参考）】
[ Back to top ]