位置を表す符号化データから位置を解決する方法
本発明は、エンコーダのデジタル地図におけるノードを表す複数の位置参照点であって、エンコーダの地図においてこれらのノードから出るか又はこれらのノードへ入る特定のライン又はセグメントを表す属性をそれぞれが有する複数の位置参照点の順序リストから位置を解決する方法を提供する。本方法は、(i)各位置参照点について、第2デジタル地図内に存在する少なくとも1つの候補ノードを識別するとともに、第2デジタル地図に存在し、候補ノードから出るか又は候補ノードへ入る少なくとも1つの候補ライン又は候補セグメントを当該位置参照点の利用可能な属性を用いて識別する工程と、(ii)第2デジタル地図において、‐少なくとも1つの候補ノードのうちの少なくとも1つ、及び当該ノードから出るか当該ノードへ入る対応する候補ライン又は候補セグメントと、‐リストに現われる次の位置参照点についての少なくとも1つの候補ノード、及び当該候補ノードから出るか又は当該候補ノードへ入る対応する候補ライン又は候補セグメントとの間の経路探索を実行し、候補ノード間で決定された経路の一部を形成する各ライン又はセグメントを第2デジタル地図から抽出する工程と、(iii)リストに現われる最後の位置参照点に到達するまで、位置参照点の連続したペアのそれぞれについて工程(ii)を繰り返す工程とを有する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は1つ以上の所定の形式に従って符号化されたデータにより表される位置を解決する方法に関し、より具体的には復号処理の間に用いられる特定のデジタル地図に依存せず且つそれにもかかわらず当初に符号化された位置に等しくなるように、テレアトラスB.V.およびナビテック・インクにより生成され販売されるようなデジタル地図内の位置を正確に決定するための方法に関する。これに関して、本方法は地図アグノスティックであるとみなされうるが、復号されたデータを位置へ解決することとは対照的に、復号を生じる方法は、選択された所定の形式に不可避的に依存するだろう。
【0002】
デジタル・マッピングの文脈における「位置(location)」という用語は様々な相異なる任意の物理的な現実世界の特徴(例えば、地表上の点位置、連続したパスまたは経路、またはこれらの連続したチェーン、地球上に存在するナビゲート可能な通路、または長方形、正方形、または円形の領域の場合に2個以上のパラメータにより規定可能な地球上の領域または地域)を意味しうるが、本発明はデジタル地図に表される道路ネットワークまたはその他のナビゲート可能な通路を通じたパスの符号化データ表現におおよそ適用可能である。
【背景技術】
【0003】
「効率的な位置参照方法」という名称で同日に出願された本出願人による相補的な出願において、全体のバイト長が関連する限りにおいて最適であると考えられるだけでなく、地図アグノスティックである考えられるように、機械で読み取り可能な位置の表現を提供するための技術が説明される。
【0004】
道路ネットワークのいかなる近年のデジタル地図(または時々知られるように数学的グラフ)は、その最も単純な形式において、最も一般的には道路の交差点を現す(点または0次元オブジェクトとみなしうる)ノードを最初に規定し、交差点間の道路を表すノード間のラインを2番目に規定する複数のテーブルから構成されるデータベースである。より詳細なデジタル地図では、ラインは開始ノードおよび終了ノードにより定義されるセグメントに分割されてもよい。開始ノードと終了ノードとは、セグメント長がゼロのセグメントの場合に同一でありうるが、一般的には別々である。3つ以上のラインまたはセグメントが交わる道路交差点を表す場合に本明細書でノードは実在または「有効(valid)」であるとみなされうるが、「人工的(artificial)」または「回避可能な(avoidable)」ノードは一方または両方の端が実在ノードで定義されないセグメントに対してアンカーとして提供されるノードである。とりわけ道路の特定の範囲についての形状情報またはこの道路の何らかの特性、例えば制限速度が変わる道路に沿った場所を識別する手段を提供するためにこれらの人工ノードはデジタル地図において有用である。
【0005】
事実上すべての近年のデジタル地図、ノード、およびセグメント(および/またはライン)はさらに、データベースのテーブル内のデータによりやはり表される様々な属性により定義される。例えば、各ノードは典型的に現実世界の位置を規定するための緯度属性および経度属性を有するだろう。道路ネットワークの完全な「グラフ」は1つ以上の国またはその一部に及ぶ領域を覆うために何百万ものノードおよびセグメントにより表現される。
【0006】
位置(すなわち、道路ネットワークを通るパス)を効率的に参照または表現する手段を案出する文脈において、位置の一部を形成するデジタル地図内のすべてのノード(および/または、セグメント、場合によってはそれらの属性)の順序リストを単に提供することは非常に非効率なだけでなく、このような参照方法は、例えば位置参照が送信された移動体装置において後で生じる任意の被参照の間に全く同一のデジタル地図が使用されることを余儀なくさせる。なぜなら、ノード、セグメント、ライン、およびそれらの属性は事実上、特定の地図ベンダにより作成された地図の特定のバージョンで一意に規定されているからである。特定のノードについての経度および位置のような基本的な属性でされ、相異なるデジタル地図間で異なりうるだろう。
【0007】
デジタル地図にしばしば提供される1つの特定の属性は交通メッセージ・チャネル(TMC)位置テーブル参照である。TMCは交通および移動の情報を乗り物のユーザ、より具体的にはこれらの乗り物内に存在し、何らかのデジタル地図の形式を含む(ポータブルまたは搭載型の)ナビゲーション・システムへ配信するための技術である。TMCメッセージは、(交通固有である必要はないが、これらが最も一般的である)イベント・コードおよび位置コードで構成され、位置コードはしばしば位置参照情報の順序リストで構成され、順序リストを用いて交通イベントの位置がデジタル地図において決定され、よってナビゲーション・システムの画面に図示されうる。ほとんどの商業的に利用可能なデジタル地図内の複数の事前定義されたノードが、限られた位置テーブルを参照して決定されるTMC位置参照情報に割り当てられる。通常は道路交差点であり、デジタル地図で識別可能であるおおよそ同数の物理的または現実世界の位置に対応する216(65536)個の位置参照情報から位置テーブルは構成される。
【0008】
37ビットほどの短さでありえ、従って放送データのために利用可能な帯域にあまり影響を与えない点でTMCメッセージは非常に効率的であるが、固定数の位置参照情報だけが利用可能であり、従って典型的に、TMCを提供する各国内の自動車道路または主要高速道路(もしくはその交差点)だけが参照されうる。TMC位置参照情報にはその他に様々な不利益が存在する。例えば、TMC位置テーブルは、
‐国家機関または国内政府を通じてしばしば維持され、
‐伝統的に非常に長い更新間隔で変更されがちであり、
‐一部の市場において、存在しないか、商業的にのみ利用可能である。
当然のことながら、TMC位置参照情報の復号は、関連する正しいノードおよびセグメントの即時の識別を結果として生じる各TMC位置コードについての単純なクエリがデジタル地図において実行されうる(各地図プロバイダは精度を保障する地図生成処理の一部としてTMC位置コードを含めるだろう)という点で本質的に単純であり、よって位置は即時に解決されうるだろう。しかしながら、GSMおよびGPSのプローブ・データを用いて二次的および都市部の道路に交通集積を識別することが可能になってきている(例えば乗り物のユーザはプローブとして使用可能な移動体電話または衛星接続ナビゲーション装置をますます所有する)ため、分解能に関連する限りにおいてTMC位置コードは全く不適切である。
【0009】
TMC位置参照情報または地図固有の参照情報の制限の一部を克服するための1つの試みは(ISO17572−1、2、3のもとで標準化過程にある)AGORA−Cとしても知られる動的位置参照プロジェクトである。AGORA−C位置参照アプローチの完全な説明は本出願の範囲外であるが、本アプローチの基本は、緯度および経度の座標ペアにより特定され、リスト内に順序付けされた位置点(location point)の集合により位置参照情報が完全に特定されえ、各点は様々なルールに従うが、最も重要なものとして、参照されている位置とリスト内の直前の点とが、すなわち連続した点が次点関係を形成するという点で各点が連続することである。他の位置参照システムと同様に、各点には複数の属性が提供され、属性はその点をよりよく定義することに役立つが、AGORA−C方法に特有なものとして各点を、位置点、交差点、経由点、およびこれら3つの何らかの組み合わせの1つとして識別することである。道路区間署名が変わる位置に沿った各点は交差点により表され、よって位置は道路ネットワーク上の経路であり、任意の道路区間署名の変更が交差点により参照される必要なく、交差点を通る。例えば、位置が関連する限りにおいて関係しない接点を含む自動車道路の区間を位置が含むならば、このような接点について交差点を含む必要はない。AGORA−C符号化方法における初期段階の1つは、道路区間署名の変更が発生する位置に沿って最初と最後との交差点の間のすべての介在する交差点を決定することである。
【0010】
すべてのこれらの点が点のテーブルへ追加され、最終的にAGORA−C位置参照情報の一部を形成する。このテーブル内に、やはり所定のルールに従って少なくとも2つの経由点も識別されている。デコーダにおいて曖昧さを残さずに正しい位置を決定するために交差点だけでは不十分である場合に経由点が提供され、経由点は個別の点として追加されるか、または必要な経由点が既存の交差点に一致する場合に後者に関する単純な属性変更がもたらされる。
【0011】
この参照アプローチは地理的情報システム内に存在する任意の位置を正確かつ反復して符号化し復号することが可能であるという点で包括的であるが、このシステムは所定の側面では過剰であり場合によっては冗長であり、多くの効率的な符号化および復号システムが可能であると信じられる。例えば、参照方法がいかなる事前の編集作業から独立であり地図から独立であったとしても、平均的なAGORA−Cメッセージのサイズは位置参照情報ごとに30バイトを優に上回る。パーソナル・ナビゲーション装置、PDA、モバイル、または車載ナビゲーション・システムのような一般的に位置参照情報を復号しうる装置の観点で、高速な復号を可能にし、それによって表される位置の最終的な解決を可能にするために受信メッセージができるだけ短いことが望まれる。
【発明の概要】
【発明が解決しようとする課題】
【0012】
従って、本発明の1つの目的は主に、構造化データ、典型的には必要な処理の観点で経済的であり、用いられるデジタル地図に関わらず受信データの相対的な簡潔さにもよらず正しい位置を再作成する観点で非常に高い成功率を達成する物理データ形式の仕様に従って位置を表す位置参照点の順序リストの符号化の結果として生じる2進数データのパケットで表される位置を解決する方法を提供することである。
【課題を解決するための手段】
【0013】
本発明によれば、エンコーダのデジタル地図におけるノードを表す複数の位置参照点であって、前記エンコーダの地図においてこれらのノードから出るか又はこれらのノードへ入る特定のライン又はセグメントを表す属性をそれぞれが有する複数の位置参照点の順序リストから位置を解決する方法であって、
(i)各位置参照点について、第2デジタル地図内に存在する少なくとも1つの候補ノードを識別するとともに、前記第2デジタル地図に存在し、前記候補ノードから出るか又は前記候補ノードへ入る少なくとも1つの候補ライン又は候補セグメントを当該位置参照点の利用可能な属性を用いて識別する工程と、
(ii)前記第2デジタル地図において、
‐前記少なくとも1つの候補ノードのうちの少なくとも1つ、及び当該ノードから出るか当該ノードへ入る対応する候補ライン又は候補セグメントと、
‐前記リストに現われる次の位置参照点についての少なくとも1つの候補ノード、及び当該候補ノードから出るか又は当該候補ノードへ入る対応する候補ライン又は候補セグメントと
の間の経路探索を実行し、前記候補ノード間で決定された前記経路の一部を形成する各ライン又はセグメントを前記第2デジタル地図から抽出する工程と、
(iii)前記リストに現われる最後の位置参照点に到達するまで、位置参照点の連続したペアのそれぞれについて工程(ii)を繰り返す工程と
を有することを特徴とする方法が提供される。
【0014】
好適には、経路探索は最短パス経路探索であるか、または経路探索への入力として用いられる開始点と終了点との間の距離に基本的に関連する要素を含む。従って、ダイクストラ・アルゴリズムまたはA*のような様々な種類の経路探索が考えられうる。
【0015】
好適には、前記経路探索は連続した候補ノードのそれぞれのペアに作用し、ノードのペアのうちの前側のノードに対応するライン又はセグメントが、当該経路探索の結果として生じる経路の一部を形成することを保証する手段を含む。
【0016】
好適には、前記識別される候補ノードは、現実世界の交差点を表す実在のノードであり、従って候補ノードはすべての可能性において前記第2デジタル地図に現れるだろう。
【0017】
好適には、前記第2デジタル地図から各ライン又はセグメントを抽出する前記工程は、前記抽出されたライン又はセグメントのそれぞれを位置パス・リストに記憶することによって強化される。さらに、連続した経路探索のそれぞれについてこのように作成された各位置パス・リストは好適には最終ステップで連結されるか、これに代えて後続の経路探索について抽出されたラインまたはセグメントのそれぞれが既存の位置パス・リストに付加され、最終的な結果は同じであり、すなわち位置を完全に識別する手段を提供することである。
【0018】
好適には、位置参照点について2つ以上の候補ノードが識別される場合に、本方法は前記識別された候補ノードを1つ以上の規定の評価基準に従って評定し、それによって最も見込みを有する候補ノードを識別するか候補ノードのランキングを提供するステップをさらに含む。また、好適には、前記第2デジタル地図に存在する2つ以上の候補ラインまたは候補セグメントが候補ノードまたは最も可能性のあるノードについて識別される場合に、本方法は最も見込みを有する候補ラインまたは候補セグメントの識別情報を結果として生じるこれらの候補ラインまたは候補セグメントを同様に評定するか、候補ラインまたは候補セグメントのランキングを提供することを含む。
【0019】
好適な実施形態において、候補ノードと候補ラインまたは候補セグメントとのうちの一方または両方を評定するステップは、評定関数を適用することによって実現される。好適には、評定関数は、候補ノード評定部分と候補ラインまたはセグメント評定部分とを含む。
【0020】
非常に好適には、前記評定関数の前記候補ノード評定部分は、位置参照点又はその絶対座標と、前記第2デジタル地図に現われ前記第2デジタル地図から抽出された前記候補ノード又はその絶対座標との間の表現又は計算された距離に関する依存性を含む。
【0021】
非常に好適には、前記評定関数の前記候補ライン又は候補セグメント評定部分は、前記エンコーダの地図に現われるライン又はセグメントの属性と、位置の解決に用いられる前記第2デジタル地図に現われるこれらの属性との間の類似性を評価する手段を含む。
【0022】
さらに好適には、本方法は、‐前記第2デジタル地図内で連続した候補ノード間のパスのそれぞれについてパス長の値を前記第2デジタル地図から決定する工程であって、前記パスは前記連続した候補ノード間の前記経路探索の結果として確立される、工程と、
‐そのように決定された前記パス長の値を、前記経路探索で用いられる2つの位置参照点のうちの前側の位置参照点のDNP属性に対して比較する工程と、
‐前記パス長の値と前記DNP属性との間の不一致が大きすぎる場合に、パス長の値とDNP属性との間の前記不一致の低減を試みるために位置参照点の連続した各ペアの一方又は両方の位置参照点についての代替の候補ノードと候補ラインとの少なくとも一方を用いて前記経路探索を繰り返すか、若しくはエラーを報告する工程と
をさらに有する。
【0023】
さらに好適には、本方法は、最初の位置参照点及び最後の位置参照点に関連する可能性のある任意のオフセット値を、前記第2デジタル地図に存在するライン又はセグメントの結果のリスト内にあり、完全で連続した位置の表現を提供する最初のライン及び最後のラインに適用する工程をさらに有する。
【0024】
本発明の第2側面では、上述の方法をコンピュータに実行させるコンピュータ・プログラム・コード手段を備えるコンピュータ・プログラムが提供される。さらなる側面では、コンピュータで読み取り可能な記憶媒体に具現化されたこのようなコンピュータ・プログラムが提供される。
【0025】
本発明の第3側面では、場合によってはハンドヘルドであり、パーソナル・ナビゲーション装置(PND)、携帯情報端末(PDA)、移動体電話、およびプロセッサと、前記プログラムを最低限備えることができ、デジタル地図を含む記憶装置と、情報出力のための手段とを含み、上述のコンピュータ・プログラムを実行できる事実上任意のコンピューティング装置のうちの1つであるコンピューティング装置が提供される。ほとんどの実施形態では、情報出力のための手段は前記デジタル地図の図示的表現を表示できる表示スクリーンで構成されるだろう。好適な実施形態では、解決された位置又はその一部は、それが関連する前記デジタル地図の関連部分に重畳され、上乗せされ、並置され、又は連結されて表示される。代替の実施形態では、コンピューティング装置は唯一のものとして又は追加としてオーディオ情報出力手段を含みうる。
【0026】
本発明は、相対的に少ない位置参照点とそれらの対応する属性とのみを用いて、場合によっては非常に長い位置を解決できるという点で既知の技術に対して優れた利点を提供する。本発明はほとんどの近年のデジタル地図は事実上すべての道路交差点を含み、それらのノードを提供するという事実を利用するため、これらの基本的要素から、候補ノードと候補ラインまたは候補セグメントとは任意の近年のデジタル地図を参照して識別されうる。さらに、デジタル地図の大多数はまた、このような交差点間の道路の形式およびクラスについての少なくとも一部の基本属性を含む。解決処理において用いられる第2デジタル地図にこのようなものが現れるなら、属性の比較を行って、第2デジタル地図において識別された1つのラインまたはセグメントが別のものよりも適切であるかどうかに関する判断を行うことが可能である。最後に、本発明は第2デジタル地図内の候補ラインをさらによりよく識別し、多くの候補ラインが識別される場合にそれらをランク付けする手段を提供するために方位計算を利用する。
【0027】
方位属性はエンコーダ側と解決方法の間との両方で計算される属性であり、デジタル地図の一部を一般に形成するものではないことが言及されるべきである。しかしながら、それは正確に計算されえ、正確な識別および/または候補ラインの評定に非常に有用であることがわかる。
【0028】
また、最短パス経路探索は、実装し実行するために利用可能であり周知であり高速である最も単純な経路探索アルゴリズムの1つであるため有用である。さらに有用な利点は、エンコーダで採用される経路探索アルゴリズムが位置の後送信の解決の間に用いられるものと必ずしも同じである必要がないことである。例えば、エンコーダ側でA*を実装し、デコーダ側でダイクストラ・アルゴリズムを実装することが可能である。これら両方のアルゴリズムは主に開始点と終了点との間の距離パラメータに主に基づくため、これらは同じ経路を結果として生じるだろう。A*の場合に、A*アルゴリズムのヒューリスティック要素が所定の要件を満たす必要があるだろうが、すべての実際の場合において、これは任意のイベントにおいてこの場合であるだろうことが言及されるべきである。従って、本発明では、最短パスが発見されることだけが要求される。実在の道路ネットワークにおいて、最短パスは通常は一意であるが、2つ以上の最短パス経路が識別されうる人工的なグリッドまたは都市内の矩形道路レイアウトに沿った経路のような例外的な環境を想像できるだろう。
【0029】
本発明の更なる利点は添付の図面を参照しつつ例示として説明される本発明の以下の個別の実施形態から明らかになるだろう。
【図面の簡単な説明】
【0030】
【図1】本発明の方法の概要フローチャートを示す。
【図2】図2〜図5はノードおよびセグメントを含む第1デジタル地図の概要表現を提供する。図2は例示のネットワークを説明する図である。
【図3】当該ネットワーク内で符号化が望まれる位置パスを説明する図である。
【図4】当該位置を部分的に含む延長されたパスの開始ノードと終了ノードとの間の最短パスを説明する図である。
【図5】当該位置を完全に参照するために必要となる位置参照点を説明する図である。
【図6】図6〜図11はノードおよびセグメントを含む第2デジタル地図の概要表現を提供する。図6は図2のネットワークを説明する図であるが、第2デジタル地図に現れるノードおよびセグメントにより表される。
【図7】第2デジタル地図内に識別される候補ノードを説明する図である。
【図8】第2デジタル地図内に識別される候補ラインを説明する図である。
【図9】位置が完全に参照される最も見込みを有する候補ラインを説明する図である。
【図10】最も見込みを有するラインの間でアルゴリズム的に決定された最短パスを示す図である。
【図11】解決された位置を示す図である。
【図12】図12〜図20は以下に説明される論理データ形式および物理データ形式の文脈で有用である様々な図式説明を提供する。特に図12は位置参照点(LRP)の必要となる連続した連結を示す。
【図13】後続LRPに関して1つのLRPについてどのように方位が計算されるかを説明する図である。
【図14】どのように方位が変わるかを示す図である。
【図15】どのように「次の点への距離」属性がLRPについて決定されうるかを示し、当該属性が関連するLRPはどれかをさらに示す図である。
【図16】オフセットの使用を説明する図である。
【図17】LRPに属性が提供される方法を示す図である。
【図18】、
【図19】位置参照情報の決定の間に回避されるノードを説明する図である。
【図20】どのようにLRPについての方位値が円の32個に分離したセクタの1つに収まるかを説明する図である。
【発明を実施するための形態】
【0031】
本発明の以下の説明はセグメントの観点で提供されるが、本発明は道路ネットワークを通る連続したパスをともに表すラインやラインとセグメントとの組み合わせに等しく適用されうることが理解されるだろう。
【0032】
位置参照情報が符号化される方法の簡潔な説明と符号化処理に用いられる特定の論理データ形式および物理データ形式を最初に提供することが本発明の文脈において有用である。後者は本明細書の補遺として提供され、以下の説明を通じてこの補遺への参照がなされる。
【0033】
まず図2〜図5を参照しつつ、第1の(エンコーダの)地図が図2に示され、15個のノードと23個のライン(双方向のラインは2度数える)とで構成される。ノードは1から15まで番号付けされる。必要なライン属性が形式<FRC>、<FOW>、<メートル単位の長さ>を用いてすべてのラインのそばに示される。FRCは「機能的道路クラス」の略語であり、FOWは「道路種別」の略語であり、これらの両方は以下の補遺により詳細に説明される。矢印は各ラインについての取り得る運転方向を示す。
【0034】
図3において、符号化される位置が太線で示される。位置はノード(3)から始まり、続いてノード(5)、(7)、(10)、(11)、(13)、(14)を通り、ノード(15)で終わる。エンコーダの地図におけるその全長は685メートルである。符号化の間に用いられるラインの順序リストとマップとはエンコーダへの入力としての機能を果たす。
【0035】
符号化:
符号化処理の最初のステップで、位置はまず有効性についてチェックされる。位置は連結され運転可能であり、位置に沿った機能的道路クラスは0と7との間であるため、この位置は有効であるとみなされる。地図データ内のターン制限が使用可能であるか否かに関するチェックを含むことが符号化処理において可能であるが、このステップは簡略化のためにここでは省略される。
【0036】
エンコーダの2番目のステップは、ある所定のデータ形式ルールに従って位置の開始ノードおよび終了ノードが実在ノードであるかをチェックすることである。終了ノード(15)は1つの内向きラインのみを有するので有効である。また、開始ノード(3)は2つの付帯するラインを有するが、ここでは1つは外向きラインであり、1つは内向きラインである。従って、このノードは有効でなく、エンコーダは位置の外側の実在ノードを検索する。エンコーダは実在ノードとしてノード(1)を発見し、位置を一意に拡張するだろう。ノード(1)は位置参照情報のための新たな開始ノードとして選択され、150メートルの正オフセットが存在するだろう。位置参照パスの全長は結果として835メートルになる。
【0037】
エンコーダの3番目のステップは位置の開始ライン(ノード(1)とノード(3)との間のライン)と終了ライン(ノード(14)とノード(15)との間のライン)との間の最短パスの計算を続いて行う。結果の最短パスは図4に太線で概要が説明される。最短パスは725メートルの長さを有する。
【0038】
符号化処理の次(4番目)のステップは、計算された最短パスにより位置が覆われるかどうかをチェックすることである。この場合は覆われておらず、ノード(10)の後に逸脱が存在することが判定されるだろう。
【0039】
本出願人による同日の関連出願に概要が説明された原理に従って、エンコーダはノード(10)からノード(11)へのラインが新たな中間位置参照点になると決定するだろう。経路探索の間にノード(10)をスキップできないためノード(10)は実在ノードであり、このラインへの最短経路は位置の対応する部分を完全に覆う。この最初の最短パス計算の後に覆われる位置の長さは561メートルである。
【0040】
次の符号化ステップは位置の残り部分(ノード(10)からノード(11)、(13)、(14)を経由してノード(15)まで)について最短パスを決定するために経路計算を準備する。従って、最短パス計算は(10)から(11)へのラインで始まり、(14)から(15)へのラインで終わるだろう。
【0041】
エンコーダは上述のステップ3へ戻り、(10)と(15)との間の最短パス(長さ:274メートル)を決定し、上述のステップ4は、現段階で計算された最短パスにより位置が完全に覆われたことを返す。
【0042】
次のステップとして、位置参照パスは2つの最短パスで構成され、位置参照点の順序リストがここで形成されるだろう。図5は位置参照点として選択されたラインが太く示される。1番目の位置参照点はノード(1)からノード(3)へのラインを指し示し、位置参照パスの開始を示す。2番目の位置参照点はノード(10)からノード(11)へのラインを指し示し、このラインは位置からの逸脱を回避するために必要であった。最後の位置参照点はノード(14)からノード(15)へのラインを指し示し、位置参照パスの終了を示す。
【0043】
(任意の途中の有効性チェックを除いて)最後のステップはLRPの順序リストを2進数位置参照情報へ変換することであり、出願人により規定された論理データ形式と物理データ形式との両方について補遺に提供された説明は読者の理解を助けるだろう。補遺に提供される説明と特定の形式に関して提供される詳細とは単に例として提供され、当業者は他の形式を取りうることを理解するだろうことが強調されるべきである。
【0044】
ここで本発明に戻り、最終的に送信される物理データは上記で識別された3つの位置参照点の2進数表現であり、適切なラインを識別できるように属性データを含む。本発明の基本原理の1つは、エンコーダとデコーダとで用いられるデジタル地図は異なるだろう可能性が大きいということである。当然のことながら、これらは同一であるかも知れず、この場合に候補ノードのラインがより正確且つ高速に識別されるために、位置は若干高速に解決されるかもしれないが、いずれの場合であっても本発明の方法はなおも適用されるはずである。
【0045】
図6を参照して、図2に示されるものと同じ部分の道路ネットワークの表現を示すが、異なる第2デジタル地図に従う。2つの図の比較により、ノードとラインとの両方の個数および場所に実質的な相違が存在することがすぐに識別されるだろう。
【0046】
本発明の1つの実施形態に従う処理の概要フローチャート100を示す図1を再び参照して、処理の最初のステップ102は、以前の符号化処理の結果として生じ、物理データ形式に従って構造化された入来する又は無線送信(最も一般的に移動体装置の場合)される2進数データ(もしくはXMLまたはその他の機械で読み取り可能な表現)を復号することである。この2進数データの復号は本発明に不可欠な要素ではなく、位置参照点のリストから位置を解決するために適用される。2進数データの復号は必須の位置参照点を識別するための単なる手段である。
【0047】
ステップ104で、有効性チェックが実行される。この初期ステップでの失敗は手続きを終了する結果となり、124で示されるようにエラーを報告する結果となる。符号化処理および物理形式への縮小は不可逆処理であり、従って2進数データから抽出される情報は、2進数ストリームを作成する前のものほど正確ではないだろう。方位および次の点への距離(DNP)について区間を使用したせいで、正確な値を抽出できず、従って正確な値を含む小区間に精度が制限される。
【0048】
例示の2進数データから抽出される情報が表1、2、3に示され(、さらにそれぞれ図1のステップ106、108、110で参照され)る。
【0049】
【0050】
【0051】
【0052】
この情報は図6に示されるデコーダの地図上の位置を解決するために十分である。この地図は17個のノードと26個のライン(双方向のラインは2度数える)とで構成される。混乱を避けるために、デコーダの地図で参照されるすべてのノードに「X」を前置きする。
【0053】
この地図はいくつかの点でエンコーダの地図(図2参照)とは異なる。一部の長さの値が異なり(例えば、ノードX(3)からX(5)へのライン)、一部の機能的道路クラス値が変更され(例えば、ノードX(3)からX(5)へのライン)、2つの新たなノードX(16)、X(17)が存在し、これらの新たなノードを接続する追加のラインも存在する。デコーダの課題はこの異なる地図で位置を解決することである。
【0054】
データの有効性を検証し、図1のステップ112に示されるように復号された位置参照点(LRP)のリストおよびその属性を提供した後に、デコーダはまずステップ114で各LRPについての候補ノードを決定するためにリスト内の各LRPを処理し始める。(総括的に116で示されるように)LRP座標を用い、デコーダのデジタル地図118に現われる最も近いノード(群)を識別することによって極めて単純に実行されるこの処理の結果として、各LRPについての候補ノードのリストが提供される。120で示されるように、LRPからの距離が所定の閾値よりも大きな地図ノードが排除されうる。図7は、位置参照点の座標の近くに位置する候補ノード(太線の丸)を示す。(上記の表1、2内の)位置参照点1、2について、この例では、1つだけの候補ノードが存在するが、最後の位置参照点について、2つの候補ノードX(16)、X(17)が可能である。
【0055】
また、LRPおよびそれらの属性の処理の一部として、各位置参照点についての候補ラインも識別される。図8の太線はこの例についての候補ラインである。最初のLRPは候補点X(1)により表され、次いでこれは2つの外向きラインを候補として有し、候補点X(10)を有する2番目のLRPは3つの外向きラインを候補として有し、最後の位置参照点は2つの内向きライン(各候補ノードX(15)X、(16)について1つずつ)を有する。114で実行される処理がいずれかのLRPについての候補ラインの識別に失敗したならば、122、124で示されるように処理は失敗しなければならない。処理が完了すると、126で各LRPについての候補ノードおよび候補ラインのリスト(群)が提供される。
【0056】
本発明の1つの実施形態において、特に2つ以上の候補ノードおよび/または2つ以上の候補ラインが各LRPについて識別される場合に、好適には候補を評定またはランク付けする何らかの手段が必要となる。従って、候補ノードのリストと候補ラインのリストとのうち少なくとも一方(好適には両方)に対して、位置参照点の属性を遵守して、評定関数128が適用される。一般に、評定関数の重要な側面は、この適用が、1つ以上の評価基準に従って、候補ノードと候補ラインとのうちの一方または好適には両方のランキングを結果として生じることである。評定関数について多くの相異なる数学的および/または統計的基盤が存在することを当業者は理解し、従って本出願の文脈ではノードに固有の評定関数またはその一部が、復号されたLRPの物理的または地理的場所への候補の距離の何らかの尺度を含んでもよく、候補ラインに固有の評定関数またはその一部が、識別された候補ラインの種類と復号データにおいて表現された種類との間の相関、および場合によってはこの候補の方位と識別されたラインを評定する何らかの手段を含むことを説明すれば十分である。
【0057】
評定関数が適用されると、最も有望な候補が図1のステップ130で識別され、これは図9に説明されるネットワークに見て取れる。特に、最も有望なラインは、ノードX(1)とノードX(3)との間のものと、ノードX(10)とノードX(11)との間のものと、ノードX(14)とノードX(15)との間のものとである。これらのラインは解決処理のステップ132で以下の最短パス計算のために用いられるだろう。
【0058】
最初のLRPと2番目のLRPとで始まる連続したLRPのペアのそれぞれについて最短パス計算が実行され、図1の矢印134で示されるように、この最短パス・アルゴリズムは上記の最も有望な候補ノードおよび候補ラインを用いてデジタル地図118を通る経路を決定し、結果として最終的に図10に示される経路を識別する。このように判定された各最短パスは、当該パスの開始ノードと終了ノードとの間のパス長の値を決定し、次いでこの値を矢印138で示されるように、各LRPについてデータで特定された利用可能なDNP属性と比較することによって、ステップ136で有効性が検証されうる。(ノードX(1)からノードX(10)への)最初の最短パスの長さは557メートルであり、この値は上記の表2に見られる最初のLRPのDNP区間(527.4メートル〜586.0メートル)を満たす。(ノードX(10)からノードX(15)への)2番目の最短パスの長さは277メートルであり、この値も2番目のLRPのDNP区間(234.4メートル〜293.0メートル)を満たす。従って、最短パスは有効性が検証され、デコーダは失敗しない代わりに処理はステップ140、142へ進み、連結された形式、すなわち完全パスに現われるすべてのラインの順序リストを最初に提供し、最後に矢印144で概要が示されるように読み出されたオフセットに従って、ステップ142で連結された最短パスをトリミングする。この例では、正オフセットのみが提供され、従って図11に明示されるように、最短パスはその開始においてトリミングされる。正オフセットの区間(上記の表3、117.2メートル〜175.8メートル)を満たす唯一のノードはノードX(3)である。
【0059】
上記から見て取れるように、本発明は受信した符号化データから位置を解決するための高信頼で効率的な方法を提供する。
【0060】
特定の論理データ形式および物理データ形式が以下に例として提供される。以下の補遺がこれらの形式について取り得る多くの特定の定義のただ1つを提供することを読者は認識するべきである。
【0061】
補遺A
論理データ形式および物理データ形式の仕様
以下の表は本明細書において位置参照情報の文脈で用いられる一般用語および略語を説明する。
【0062】
【0063】
1.データ形式
位置参照情報はデジタル地図の指定された部分または一連の地理的場所の表現である。この表現のために、位置参照点(LRP、1.1.1参照)のモデルを用いる。
【0064】
ライン位置についての位置参照情報は少なくとも2つのLRPを含むがLRPの最大数は規定されない。位置参照パスはLRPにより表現されるデジタル地図内のパスであり、LRPの連続したペアのそれぞれの間の最短パス計算により発見されうる。
【0065】
1.1 論理データ形式の仕様
論理データ形式はMapLoc(商標)標準に従って位置参照情報についての論理モデルを表現する。
【0066】
1.1.1.位置参照点(LRP)
位置参照情報の基盤は一連の位置参照点(LRP)である。このようなLRPはWGS84の経度値および緯度値で特定された座標ペアと、付加的ないくつかの属性とを含む。
【0067】
座標ペア(1.1.3.1参照)は地図/ネットワーク内の地理的位置を表し、LRPについて必須である。座標ペアはネットワーク内の「実在(real)」ノードに属する。
【0068】
属性(セクション1.1.3.2〜1.1.3.6参照)は、座標ペアにより表現されるノードにラインが付帯する、ネットワーク内のラインの値を表す。この文脈では、ノードに関して内向きラインと外向きラインとのどちらを属性が指すかは規定されない。これはセクション1.2で特定される。
【0069】
1.1.2.LRPのトポロジー連結
図12を参照して、位置参照点はトポロジーの順序で、すなわち連続したLRPの「次の点(next point)」関係で記憶されるものとする。この順序の最後の点はこの関係における次の点を有しないだろう。
【0070】
図12はこの関係の例を示す。LRPはA1、B1、およびC1によって示され、黒線矢印は位置参照パスにおけるA1からC1への点の順序を示す。この例では、LRP A1は次の点としてB1を有し、B1は次の点としてC1を有し、C1は次の点を有しないだろう。
【0071】
1.1.3.LRPのコンポーネント
このセクションは位置参照点のコンポーネントを説明する。
【0072】
1.1.3.1 座標ペア
座標ペアはWGS84の経度(lon)の値と緯度(lat)の値とのペアを意味する。この座標ペアはデジタル地図における幾何的な点を特定する。lon値およびlat値はデカミクロンの分解能(10-5、すなわち小数点5位)で記憶される。
【0073】
略語:COORD タイプ:(浮動小数,浮動小数)
【0074】
1.1.3.2 機能的道路クラス
機能的道路クラス(FRC)は道路の重要度に基づく道路分類である。FRC属性の取りうる値が表A2に示される。これら8個の位置参照値よりも多くのFRC値が定義されるならば、適切なマッピングが行われる必要があるか、または重要性の低いクラスが無視される必要がある。
【0075】
【0076】
略語:FRC タイプ:整数
【0077】
1.1.3.3 道路種別(Form of way)
道路種別(FOW)は物理的道路タイプを表現する。FOW属性の取りうる値が表A3に示される。
【0078】
【0079】
略語:FOW タイプ:整数
【0080】
1.1.3.4 方位
方位(BEAR)は、真北と、LRPの座標およびLRP属性により定義されるラインに沿ってBEARDISTである座標により定義されるラインとの間の角度を表現する。ライン長がBEARDISTよりも短いならば、(BEARDISTに関わらず)ラインの反対側の点が使用される。方位は角度単位で測定され、(北から時計回りに測定され)常に正である。パラメータであるBEARDISTは表A4に定義される。
【0081】
略語:BEAR タイプ:整数
【0082】
【0083】
図13は方位計算のための第2点がどのように決定されるかを示す。この図はBEARDISTよりも長いA2からB2へのラインを示す。このラインの斜線部分はBEARDISTメートルちょうどの長さであり、その結果としてB′で印が付けられた点はA2からB2へのラインに沿って移動して、A2からBEARDISTメートル離れている。A2からB′への直線が方位値の計算のために以下で検討される。ラインの反対側のノード(この場合、これはB2であるだろう)が用いられる場合に計算されるだろう角度はこれとは異なる。
【0084】
図14は方位値を計算する2つの例を示す。1つはA3からB3までであり、1つはA3からC3までである2つのラインが存在する。両方のラインについて、弧は北に対する角度を示す。
【0085】
1.1.3.5 次のLRPへの距離
このDNPフィールドはLRPのトポロジー連結における次のLRPへの距離を表現する。距離はメートル単位で測定され、位置参照パスに沿って計算される。最後のLRPは距離値としてゼロを有するだろう。
【0086】
略語:DNP タイプ:整数
【0087】
図15は距離の計算と割り当てとの例を示す。3つのLRPがA4からB4を越えてC4まで一列に存在する。従って、位置参照パスに沿ったA4とB4との距離はA4に割り当てられるだろう。LRP B4はB4とC4との間の距離を保持し、LRP C4は距離値としてゼロを有するだろう。
【0088】
1.1.3.6 次のLRPへの最低FRC
最低FRC(LFRCNP)は2つの連続したLRPの間の位置参照パスに現れる最低のFRC値である。最高のFRC値は0であり、取りうる最低のFRC値は7の値を有する。
【0089】
略語:LFRCNP タイプ:整数
【0090】
1.1.4.オフセット
オフセットは位置参照パスをその開始および終了において縮小するために用いられる。位置参照パスに沿った新たな場所は、位置の実際の開始および実際の終了を示す。
【0091】
1.1.4.1 正オフセット
正オフセット(POFF)は位置参照情報の開始点と所望の位置の開始点との位置参照パスに沿った距離である。値はメートル単位で測定される。図16は正オフセットおよび負オフセットの計算の例を示す。線は位置参照パスを示し、ハッチングは所望の位置を示す。
【0092】
略語:POFF タイプ:整数
【0093】
1.1.4.2 負オフセット
負オフセット(NOFF)は所望の位置の終了点と位置参照情報の終了点との位置参照パスに沿った距離である。値はメートル単位で測定される(図16を再び参照)。
【0094】
略語:NOFF タイプ:整数
【0095】
1.2 関連属性‐LRP
すべての属性はLRPにリンクされる。(最後のLRPを除く)すべてのLRPについて、属性はLRP座標におけるノードの外向きラインを表す。最後のLRPの属性はLRP座標におけるノードの内向きを対象とする。
【0096】
図17はLRPと属性との間の関連の例を示す。ラインは位置参照パスを示し、ノードA5、B5、およびC5がLRPである。開始ノードおよび終了ノードがLRPでないライン(列の3番目のライン)も存在することに留意されたい。このラインは、LRP B5とLRP C5との間の最短パスにより覆われるため、参照される必要はない。
【0097】
LRP A5およびLRP B5は外向きラインを対象とし、最後のLRP C5は内向きラインを対象とする。
【0098】
1.3 データ形式のルール
これらのルールはこの仕様に従う位置参照情報についての追加の規則を表現する。これらのルールは符号化処理および復号処理を単純化し、結果の精度を高めるために用いられる。
【0099】
ルール1 2つの位置参照点の間の最大距離は15kmを超えないものとする。距離は位置参照パスに沿って測定される。位置参照情報についてこの条件が満たされないならば、十分な数の追加のLRPが挿入されるものとする。
【0100】
2つの連続した位置参照点の間の最大距離は最短パス計算を速めるために制限される。なぜなら、経路アルゴリズムがネットワーク全体を考慮に入れなければならない場合に、1つの長い経路よりも複数の短い経路の方が速く計算されうるからである。本制限はまた、許容精度でコンパクトな2進数形式を形成する機会を提供する。
【0101】
ルール2 すべての長さは整数値である。浮動小数値が利用可能ならば、整数表現を得るためにこれらの値を丸める。
【0102】
様々な地図は長さの値を様々な形式で且つ様々な精度で記憶するかも知れず、すべてに対する統一の基盤は整数値を使用することである。また、浮動小数値を用いるよりも2進数形式の整数値を送信する方がコンパクトである。
【0103】
ルール3 2つのLRPが必須であり、中間LRPの個数は制限されない。
【0104】
ライン位置参照情報は位置の開始および終了を示す少なくとも2つの位置参照点を常に有していなければならない。(異なる地図に関して)デコーダに問題が発生するかもしれない危機的状況をエンコーダが検出するならば、位置参照情報は追加の中間LRPで強化されうる。
【0105】
ルール4 LRPの座標は実在ネットワーク・ノード上に選択されるものとする。
【0106】
これらの実在ネットワーク・ノードは現実世界の接点であるべきで、これらの接点はライン上のどこかの場所よりも高い確率で異なる地図で発見されうることが期待される。さらに、経路検索の間に容易にスキップされうるノードは回避されるものとする。これらの回避可能なノードにおいて、経路から逸脱する可能性はない。
【0107】
1つの内向きラインおよび1つの外向きラインのみを有するノードは、これらのノードが接点に関連せず(図18参照)、経路探索の間にスキップされうるために、回避されるものとする。2つの内向きラインおよび2つの外向きラインを有し、2つの隣接ノードのみが存在するノードは同様に回避されるものとする(図19参照)。
【0108】
これらのノードの1つがLRPについて選択されると、このLRPは適切なノードを見つけるために位置参照パスに沿ってシフトされるべきである。これは、所望のパスを逸脱することなくこのような回避可能なノードを経路計算がスキップするために行われうる。
【0109】
位置の開始または終了が回避可能なノード上に配置されるならば、エンコーダは位置を一意に拡張すべきであり、位置の外側の適切なノードを見つけるべきである。この拡張は位置へ入り込むべきではない。なぜなら、これは位置を縮小するだろうからである。
【0110】
1.3.1.データ形式ルールの概要
以下の表はデータ形式ルールを要約する。
【0111】
【0112】
1.4 2進数表現
物理データ形式は上述の論理データ形式についてのバイト指向のストリーム形式を表現する。これはセクション1.1の論理データ形式において表現されたコンポーネントを用いる。
【0113】
1.4.1.データ・タイプ
物理データ形式は以下のデータ・タイプを用いる。表はすべての利用可能なデータ・タイプの概要を与え、名前、タイプ、および各データ・タイプの指定サイズを特定する。以下のセクションでは、データ・タイプ名は各データ・コンポーネントについてサイズおよびタイプを示すために用いられる。
【0114】
【0115】
負の整数値が2つのコンポーネント形式で記憶される。
【0116】
1.4.2.座標(COORD)
地図内の各点はWGS84座標で表された「経度」(lon)と「緯度」(lat)との座標ペアで構成される。北方向および東方向は(経度、緯度それぞれ)正の値で表される。lot値およびlat値はデカミクロンの分解能(10-5、小数点第5位)で記憶される。
【0117】
座標値は整数値として送信されるだろう。これらの値は24ビット整数表現を算出する式E1を用いて生成されるだろう。分解能パラメータは24に設定される。この変換は最大で約2.4メートルの誤差を生じる。逆変換は式E2で表現される。両方の式は、負の値について−1、正の値について1、その他について0である符号関数を利用する。
【0118】
【0119】
【0120】
物理形式は絶対座標形式と相対座標形式とを利用する。絶対形式は地理的場所の指定された値を表し、相対値は先行する座標に対するオフセット座標である。
【0121】
1.4.2.1 絶対形式
絶対形式は24ビット分解能における地理的場所を表現する。表A7は絶対形式に用いられるデータ・タイプを示す。
【0122】
【0123】
1.4.2.2 相対形式
相対形式は2つの連続した座標間の差を表現するために用いられる。差は式E3に示されるように各値(lon/lat)別々に計算される。現在の値および前の値は緯度値(経度値)を角度単位で表す。これら2つの値の差は整数値へ変化させるために100000倍される。
【0124】
【0125】
表A8は16ビット表現を用いて取りうる最大距離を示す。この図はlon=5°、lat=52°(オランダ内の場所)における固定の座標について計算される。
【0126】
【0127】
表A9は2バイト・オフセットについてのデータ・タイプを示す。
【0128】
【0129】
1.4.3.属性値
属性の2進数形式がこのセクションで続く。
【0130】
1.4.3.1 機能的道路クラス(FRC)
機能的道路クラス(FRC)は論理形式で説明されたように8個の相異なる値を保持しうる。これらの8個の値は表A10で示される3ビットとマッピングとにより表される。
【0131】
【0132】
1.4.3.2 道路種別(FOW)
道路種別(FOW)は論理形式において説明されたように8個の相異なる値を保持しうる。これらの8個の値は表A11で示される3ビットとマッピングとにより表される。
【0133】
【0134】
1.4.3.3 方位(BEAR)
方位は論理形式において説明されたように道路と真北との間の角度を表現する。物理データ形式は32個のセクタを定義し、各セクタは円のうち11.25°をカバーする。これらの32個のセクタは5ビットで表される。表A12は方位属性についてのデータ・タイプを示し、表A13はセクタから具体的な値へのマッピングを示す。
【0135】
【0136】
【0137】
式E4は方位値の計算の概要を説明し、図20はセクタの図示による概要を提供する。
【0138】
【0139】
1.4.3.4 次のLRPへの距離(DNP)
DNP属性は論理形式において説明されたように位置参照パスに沿った2つの連続したLRP間の距離を測定する。
【0140】
物理データ形式は8ビット表現を定義し、表A14はDNPについて用いられるデータ・タイプを示す。この表現は255個の間隔を定義し、データ形式ルールのルール1(2つの連続したLRP間の最大長は15000mに制限される)と組み合わせて各間隔は58.6メートルの長さを有するだろう。
【0141】
【0142】
式E5はどのようにDNP値を計算できるかを示す。
【0143】
【0144】
1.4.3.5 次の点への最低FRC(LFRCNP)
次の点への最低FRCは次のLRPへの位置参照パスに用いられる最低の機能的道路クラスを示す。この情報は復号の間にスキャンされる必要のある道路クラスの個数を制限するために用いられうる。データ・タイプの定義については表A15を参照されたい。
【0145】
【0146】
1.4.4.位置参照情報ヘッダ
位置参照情報ヘッダは参照情報に関する一般的な情報を含む。
【0147】
1.4.4.1 バーション(VER)
バーションは位置参照情報についての複数の物理的なデータ・フォーマットを区別するために用いられる。バージョン番号は3ビットで表され、データ・タイプは表A16に示される。
【0148】
【0149】
1.4.4.2 属性フラグ(AF)
属性フラグは各LRPへ付加された属性が存在するか否かを示す。属性が付加されていない場合にAF値は0となり、従って位置参照情報は座標だけで構成される。それ以外の場合、値は1となり各LRPへ属性が付加されることを示す。AFについてのデータ・タイプは表A17、A18に示される。
【0150】
【0151】
【0152】
1.4.4.3 領域フラグ(ArF)
領域フラグは位置参照情報が領域を記載するか否かを示す。このフラグが設定されるならば、位置は結合しているものとし、以下の表A19、A20に見られるように領域を表現する。
【0153】
【0154】
【0155】
1.4.5.オフセット
オフセットはネットワーク内のノードへ結び付けられたものよりも正確に位置の開始および終了を位置付けるために用いられる。論理形式は、1つは位置の開始において、もう1つは位置の終了において2つのオフセットを定義し、両方のオフセットは位置のラインに沿って作用し、メートル単位で測定される。オフセット値は必須ではなく、オフセット値がないことは0メートルのオフセットを意味する。また、オフセットは属性が含められたライン位置についてのみ有効である。
【0156】
1.4.5.1 オフセット・フラグ
オフセット・フラグはデータが特定のオフセット情報を含むかどうかを示す。物理データ形式は2つの相異なるオフセット値に対応する2つのフラグを扱う。正オフセット・フラグ(PoffF)と負オフセット・フラグ(NoffF)とが表A21、A22に表現される。
【0157】
【0158】
【0159】
1.4.5.2 オフセット値
オフセット値(正および負、POFFおよびNOFF)は位置参照パスの開始(終了)と位置の「実在の(real)」開始(終了)との間の距離を示す。
【0160】
物理データ形式は各オフセット値について8ビット表現を定義する。表A23はPOFFおよびNOFFについて用いられるデータ・タイプを示す。この表現は各間隔の長さが58.6メートルである256個の間隔を定義することを可能にする。オフセットについての間隔番号の計算は式E6に概要が説明される。
【0161】
【0162】
【0163】
1.5 物理データ形式の仕様
このセクションはバイト・ストリーム内のデータ・フィールドの構成を表現する。バイト指向のストリームを有し、バイトごとに8ビットを使用できると想定する。
【0164】
1.5.1.概要
2進数形式の主な構造は、ヘッダ、先頭LRP、後続LRP、末尾LRP、およびオフセットである。ヘッダ、先頭LRP、および末尾LRPは必須であり、後続LRPの個数は制限されない。末尾LRPは相異なる情報レベルに起因して独自の構造を有する。オフセットはオプションであり、その存在は末尾LRPの属性内のフラグにより示されるだろう。
【0165】
表A24は主な構造の概要を与える。ストリームは左から右へ読み取ることができ、それにより最初に受信されるバイトは状態バイトであるだろう。各座標について、最初に受信される値は経度値であり、緯度値がそれに続くだろう。
【0166】
LRPの個数に依存するメッセージ・サイズの計算は以下のセクション1.6に見られうる。
【0167】
【0168】
1.5.2 状態バイト
状態バイトはすべての位置参照情報について1回送信され、領域フラグ(ArF、セクション1.4.4.3)、属性フラグ(AF、セクション1.4.4.2)、およびバージョン情報(VER、セクション1.4.4.1)を含む。ビット7、6、5は将来の使用のために予約(RFU)され、0であるものとする。表A25は状態バイトの各ビットの用途の概要を与える。
【0169】
【0170】
形式のこの特定のバージョンでは、属性が各LRPへ付加され、領域は表現されない。「現在のバージョン」が2であるならば、状態バイトは表A26に示される値を有するだろう。
【0171】
【0172】
1.5.3.先頭LRPの座標
先頭LRPの座標は絶対形式(セクション1.4.2.1参照)で送信され、従って各値(lotおよびlat)は3バイトを用いるだろう。表A27は経度値および緯度値についてのバイト順を示す。
【0173】
【0174】
1.5.4.後続LRPの座標
後続LRPおよび末尾LRPの座標は相対形式(セクション1.4.2.2参照)で送信され、従って各値(lotおよびlat)は2バイトを用いるだろう。表A28は経度値および緯度値についてのバイト順を示す。
【0175】
【0176】
1.5.5.属性
属性は各LRPへ付加される。位置参照情報におけるLRPの場所に依存して相異なる4種類の属性が存在する。
【0177】
1.5.5.1 第1属性バイト(属性1)
第1属性バイトは属性FRC(セクション1.4.3.1参照)とFOW(セクション1.4.3.2参照)とを含み、2ビットが将来の使用のために予約される。表A29は各ビットの用途を示す。
【0178】
【0179】
1.5.5.2 第2属性バイト(属性2)
第2属性バイトは属性LFRCNP(セクション1.4.3.5)と属性BEAR(セクション1.4.3.3参照)とを含む。表A30は各ビットの用途を示す。LFRCNP情報が利用可能でないため、この属性は末尾LRPに対して有効でない。
【0180】
【0181】
1.5.5.3 第3属性バイト(属性3)
第3属性バイトは表A31に示されるように属性DNP(セクション1.4.3.4参照)を含む。DNP情報が利用可能でないため、この属性は末尾LRPに対して有効でない。
【0182】
【0183】
1.5.5.4 第4属性バイト(属性4)
属性4はBEAR情報、正および負のオフセット・フラグ(セクション1.4.5.1参照)、ならびに将来の使用のために予約された1ビットを含む。表A32に示されるように、この属性は末尾LRPについて用いられる。
【0184】
【0185】
1.5.6 オフセット
正オフセット(POFF)および負オフセット(NOFF)は、属性4内の対応するフラグがそれらの存在を示す場合にのみ含まれる。オフセット値を含まないことは0メートルのオフセット値を示す。オフセット値はセクション1.4.5に従って計算され、これらのオフセットのビット用途は表A33、A34に示される。
【0186】
【0187】
【0188】
1.6 メッセージ・サイズの計算
位置参照情報のメッセージ・サイズは位置参照情報に含まれるLRPの個数に依存する。位置参照情報には少なくとも2つのLRPが含まれるべきである。また、状態情報を伴うヘッダが必須である。以下の計算と表A35とはLRPの個数に依存するメッセージ・サイズを示す。
・ヘッダ
1バイト状態
合計:1バイト
・先頭LRP
6バイトCOORD(lon/latのそれぞれについて3バイト)
3バイト属性
合計:9バイト
・後続LRP
4バイトCOORD(lon/latのそれぞれについて2バイト)
3バイト属性
合計:7バイト
・末尾LRP
4バイトCOORD(lon/latのそれぞれについて2バイト)
2バイト属性
合計:6バイト
・オフセット(含まれる場合)
1バイト正オフセット(含まれる場合)
1バイト負オフセット(含まれる場合)
合計:0〜2バイト
【0189】
【0190】
上記の形式が用いられる方法の特定の例が、図2〜図5を参照して上述された位置参照情報を参照して以下に提供される。これらの図では3つの位置参照点(ノード(1)、(10)、(15)およびライン(1)〜(3)、(10)〜(11)、(14)〜(15))が位置を正確に表現するために識別される。位置参照情報は3つの位置参照点で構成され、以下の表A36はノード(1)、(10)、(15)についての座標を示す。これらのノードは位置参照点に対応するノードである。2進数形式の準備において、この表はまた、相対座標を示す。ノード(1)は位置参照点1に対応し、絶対形式の座標を有するだろう。位置参照点2に対応するノード(10)は位置参照点1に対する相対座標を有するだろう。位置参照点3に対応するノード(15)も相対座標を有するだろうが、ここでは位置参照点2を参照する。
【0191】
【0192】
相対経度および相対緯度は上記の式E3に従って計算される。符号化処理のステップ2で計算されるオフセットが表A37に示される。2進数データにおいて、正オフセットのみが現れるだろう。なぜなら、負オフセットは0であり、オフセットがない場合は0として扱われるだろうからである。
【0193】
【0194】
以下の表A38は基底のデジタル地図から計算を通じて各位置参照点についての関連データを収集する。これは機能的道路クラス、道路種別、および対応するラインの方位を含む。2つの連続した位置参照点間のパスに関して必要な情報(最低機能的道路クラスと次の位置参照点への距離)も示される。
【0195】
【0196】
BEAR属性、LFRCNP属性、およびDNP属性は上述のように決定される。以下の表は2進数データを作成するためのすべての関連情報を保持する。以下の表は物理データ形式に従って2進数データの概要を説明する。
・状態タイプ:表A39を参照。
・LRP1: 表A40〜A44を参照。
・LRP2: 表A45〜A49を参照。
・LRP3: 表A50〜A53を参照。
・オフセット:表A54を参照。
【0197】
【0198】
【0199】
【0200】
【0201】
【0202】
【0203】
【0204】
【0205】
【0206】
【0207】
【0208】
【0209】
【0210】
【0211】
【0212】
【0213】
完全な2進数データストリームは24バイトの長さを有し、以下のもので構成される(左から右へ、そして上から下へのバイトとして並ぶ)。
【0214】
【技術分野】
【0001】
本発明は1つ以上の所定の形式に従って符号化されたデータにより表される位置を解決する方法に関し、より具体的には復号処理の間に用いられる特定のデジタル地図に依存せず且つそれにもかかわらず当初に符号化された位置に等しくなるように、テレアトラスB.V.およびナビテック・インクにより生成され販売されるようなデジタル地図内の位置を正確に決定するための方法に関する。これに関して、本方法は地図アグノスティックであるとみなされうるが、復号されたデータを位置へ解決することとは対照的に、復号を生じる方法は、選択された所定の形式に不可避的に依存するだろう。
【0002】
デジタル・マッピングの文脈における「位置(location)」という用語は様々な相異なる任意の物理的な現実世界の特徴(例えば、地表上の点位置、連続したパスまたは経路、またはこれらの連続したチェーン、地球上に存在するナビゲート可能な通路、または長方形、正方形、または円形の領域の場合に2個以上のパラメータにより規定可能な地球上の領域または地域)を意味しうるが、本発明はデジタル地図に表される道路ネットワークまたはその他のナビゲート可能な通路を通じたパスの符号化データ表現におおよそ適用可能である。
【背景技術】
【0003】
「効率的な位置参照方法」という名称で同日に出願された本出願人による相補的な出願において、全体のバイト長が関連する限りにおいて最適であると考えられるだけでなく、地図アグノスティックである考えられるように、機械で読み取り可能な位置の表現を提供するための技術が説明される。
【0004】
道路ネットワークのいかなる近年のデジタル地図(または時々知られるように数学的グラフ)は、その最も単純な形式において、最も一般的には道路の交差点を現す(点または0次元オブジェクトとみなしうる)ノードを最初に規定し、交差点間の道路を表すノード間のラインを2番目に規定する複数のテーブルから構成されるデータベースである。より詳細なデジタル地図では、ラインは開始ノードおよび終了ノードにより定義されるセグメントに分割されてもよい。開始ノードと終了ノードとは、セグメント長がゼロのセグメントの場合に同一でありうるが、一般的には別々である。3つ以上のラインまたはセグメントが交わる道路交差点を表す場合に本明細書でノードは実在または「有効(valid)」であるとみなされうるが、「人工的(artificial)」または「回避可能な(avoidable)」ノードは一方または両方の端が実在ノードで定義されないセグメントに対してアンカーとして提供されるノードである。とりわけ道路の特定の範囲についての形状情報またはこの道路の何らかの特性、例えば制限速度が変わる道路に沿った場所を識別する手段を提供するためにこれらの人工ノードはデジタル地図において有用である。
【0005】
事実上すべての近年のデジタル地図、ノード、およびセグメント(および/またはライン)はさらに、データベースのテーブル内のデータによりやはり表される様々な属性により定義される。例えば、各ノードは典型的に現実世界の位置を規定するための緯度属性および経度属性を有するだろう。道路ネットワークの完全な「グラフ」は1つ以上の国またはその一部に及ぶ領域を覆うために何百万ものノードおよびセグメントにより表現される。
【0006】
位置(すなわち、道路ネットワークを通るパス)を効率的に参照または表現する手段を案出する文脈において、位置の一部を形成するデジタル地図内のすべてのノード(および/または、セグメント、場合によってはそれらの属性)の順序リストを単に提供することは非常に非効率なだけでなく、このような参照方法は、例えば位置参照が送信された移動体装置において後で生じる任意の被参照の間に全く同一のデジタル地図が使用されることを余儀なくさせる。なぜなら、ノード、セグメント、ライン、およびそれらの属性は事実上、特定の地図ベンダにより作成された地図の特定のバージョンで一意に規定されているからである。特定のノードについての経度および位置のような基本的な属性でされ、相異なるデジタル地図間で異なりうるだろう。
【0007】
デジタル地図にしばしば提供される1つの特定の属性は交通メッセージ・チャネル(TMC)位置テーブル参照である。TMCは交通および移動の情報を乗り物のユーザ、より具体的にはこれらの乗り物内に存在し、何らかのデジタル地図の形式を含む(ポータブルまたは搭載型の)ナビゲーション・システムへ配信するための技術である。TMCメッセージは、(交通固有である必要はないが、これらが最も一般的である)イベント・コードおよび位置コードで構成され、位置コードはしばしば位置参照情報の順序リストで構成され、順序リストを用いて交通イベントの位置がデジタル地図において決定され、よってナビゲーション・システムの画面に図示されうる。ほとんどの商業的に利用可能なデジタル地図内の複数の事前定義されたノードが、限られた位置テーブルを参照して決定されるTMC位置参照情報に割り当てられる。通常は道路交差点であり、デジタル地図で識別可能であるおおよそ同数の物理的または現実世界の位置に対応する216(65536)個の位置参照情報から位置テーブルは構成される。
【0008】
37ビットほどの短さでありえ、従って放送データのために利用可能な帯域にあまり影響を与えない点でTMCメッセージは非常に効率的であるが、固定数の位置参照情報だけが利用可能であり、従って典型的に、TMCを提供する各国内の自動車道路または主要高速道路(もしくはその交差点)だけが参照されうる。TMC位置参照情報にはその他に様々な不利益が存在する。例えば、TMC位置テーブルは、
‐国家機関または国内政府を通じてしばしば維持され、
‐伝統的に非常に長い更新間隔で変更されがちであり、
‐一部の市場において、存在しないか、商業的にのみ利用可能である。
当然のことながら、TMC位置参照情報の復号は、関連する正しいノードおよびセグメントの即時の識別を結果として生じる各TMC位置コードについての単純なクエリがデジタル地図において実行されうる(各地図プロバイダは精度を保障する地図生成処理の一部としてTMC位置コードを含めるだろう)という点で本質的に単純であり、よって位置は即時に解決されうるだろう。しかしながら、GSMおよびGPSのプローブ・データを用いて二次的および都市部の道路に交通集積を識別することが可能になってきている(例えば乗り物のユーザはプローブとして使用可能な移動体電話または衛星接続ナビゲーション装置をますます所有する)ため、分解能に関連する限りにおいてTMC位置コードは全く不適切である。
【0009】
TMC位置参照情報または地図固有の参照情報の制限の一部を克服するための1つの試みは(ISO17572−1、2、3のもとで標準化過程にある)AGORA−Cとしても知られる動的位置参照プロジェクトである。AGORA−C位置参照アプローチの完全な説明は本出願の範囲外であるが、本アプローチの基本は、緯度および経度の座標ペアにより特定され、リスト内に順序付けされた位置点(location point)の集合により位置参照情報が完全に特定されえ、各点は様々なルールに従うが、最も重要なものとして、参照されている位置とリスト内の直前の点とが、すなわち連続した点が次点関係を形成するという点で各点が連続することである。他の位置参照システムと同様に、各点には複数の属性が提供され、属性はその点をよりよく定義することに役立つが、AGORA−C方法に特有なものとして各点を、位置点、交差点、経由点、およびこれら3つの何らかの組み合わせの1つとして識別することである。道路区間署名が変わる位置に沿った各点は交差点により表され、よって位置は道路ネットワーク上の経路であり、任意の道路区間署名の変更が交差点により参照される必要なく、交差点を通る。例えば、位置が関連する限りにおいて関係しない接点を含む自動車道路の区間を位置が含むならば、このような接点について交差点を含む必要はない。AGORA−C符号化方法における初期段階の1つは、道路区間署名の変更が発生する位置に沿って最初と最後との交差点の間のすべての介在する交差点を決定することである。
【0010】
すべてのこれらの点が点のテーブルへ追加され、最終的にAGORA−C位置参照情報の一部を形成する。このテーブル内に、やはり所定のルールに従って少なくとも2つの経由点も識別されている。デコーダにおいて曖昧さを残さずに正しい位置を決定するために交差点だけでは不十分である場合に経由点が提供され、経由点は個別の点として追加されるか、または必要な経由点が既存の交差点に一致する場合に後者に関する単純な属性変更がもたらされる。
【0011】
この参照アプローチは地理的情報システム内に存在する任意の位置を正確かつ反復して符号化し復号することが可能であるという点で包括的であるが、このシステムは所定の側面では過剰であり場合によっては冗長であり、多くの効率的な符号化および復号システムが可能であると信じられる。例えば、参照方法がいかなる事前の編集作業から独立であり地図から独立であったとしても、平均的なAGORA−Cメッセージのサイズは位置参照情報ごとに30バイトを優に上回る。パーソナル・ナビゲーション装置、PDA、モバイル、または車載ナビゲーション・システムのような一般的に位置参照情報を復号しうる装置の観点で、高速な復号を可能にし、それによって表される位置の最終的な解決を可能にするために受信メッセージができるだけ短いことが望まれる。
【発明の概要】
【発明が解決しようとする課題】
【0012】
従って、本発明の1つの目的は主に、構造化データ、典型的には必要な処理の観点で経済的であり、用いられるデジタル地図に関わらず受信データの相対的な簡潔さにもよらず正しい位置を再作成する観点で非常に高い成功率を達成する物理データ形式の仕様に従って位置を表す位置参照点の順序リストの符号化の結果として生じる2進数データのパケットで表される位置を解決する方法を提供することである。
【課題を解決するための手段】
【0013】
本発明によれば、エンコーダのデジタル地図におけるノードを表す複数の位置参照点であって、前記エンコーダの地図においてこれらのノードから出るか又はこれらのノードへ入る特定のライン又はセグメントを表す属性をそれぞれが有する複数の位置参照点の順序リストから位置を解決する方法であって、
(i)各位置参照点について、第2デジタル地図内に存在する少なくとも1つの候補ノードを識別するとともに、前記第2デジタル地図に存在し、前記候補ノードから出るか又は前記候補ノードへ入る少なくとも1つの候補ライン又は候補セグメントを当該位置参照点の利用可能な属性を用いて識別する工程と、
(ii)前記第2デジタル地図において、
‐前記少なくとも1つの候補ノードのうちの少なくとも1つ、及び当該ノードから出るか当該ノードへ入る対応する候補ライン又は候補セグメントと、
‐前記リストに現われる次の位置参照点についての少なくとも1つの候補ノード、及び当該候補ノードから出るか又は当該候補ノードへ入る対応する候補ライン又は候補セグメントと
の間の経路探索を実行し、前記候補ノード間で決定された前記経路の一部を形成する各ライン又はセグメントを前記第2デジタル地図から抽出する工程と、
(iii)前記リストに現われる最後の位置参照点に到達するまで、位置参照点の連続したペアのそれぞれについて工程(ii)を繰り返す工程と
を有することを特徴とする方法が提供される。
【0014】
好適には、経路探索は最短パス経路探索であるか、または経路探索への入力として用いられる開始点と終了点との間の距離に基本的に関連する要素を含む。従って、ダイクストラ・アルゴリズムまたはA*のような様々な種類の経路探索が考えられうる。
【0015】
好適には、前記経路探索は連続した候補ノードのそれぞれのペアに作用し、ノードのペアのうちの前側のノードに対応するライン又はセグメントが、当該経路探索の結果として生じる経路の一部を形成することを保証する手段を含む。
【0016】
好適には、前記識別される候補ノードは、現実世界の交差点を表す実在のノードであり、従って候補ノードはすべての可能性において前記第2デジタル地図に現れるだろう。
【0017】
好適には、前記第2デジタル地図から各ライン又はセグメントを抽出する前記工程は、前記抽出されたライン又はセグメントのそれぞれを位置パス・リストに記憶することによって強化される。さらに、連続した経路探索のそれぞれについてこのように作成された各位置パス・リストは好適には最終ステップで連結されるか、これに代えて後続の経路探索について抽出されたラインまたはセグメントのそれぞれが既存の位置パス・リストに付加され、最終的な結果は同じであり、すなわち位置を完全に識別する手段を提供することである。
【0018】
好適には、位置参照点について2つ以上の候補ノードが識別される場合に、本方法は前記識別された候補ノードを1つ以上の規定の評価基準に従って評定し、それによって最も見込みを有する候補ノードを識別するか候補ノードのランキングを提供するステップをさらに含む。また、好適には、前記第2デジタル地図に存在する2つ以上の候補ラインまたは候補セグメントが候補ノードまたは最も可能性のあるノードについて識別される場合に、本方法は最も見込みを有する候補ラインまたは候補セグメントの識別情報を結果として生じるこれらの候補ラインまたは候補セグメントを同様に評定するか、候補ラインまたは候補セグメントのランキングを提供することを含む。
【0019】
好適な実施形態において、候補ノードと候補ラインまたは候補セグメントとのうちの一方または両方を評定するステップは、評定関数を適用することによって実現される。好適には、評定関数は、候補ノード評定部分と候補ラインまたはセグメント評定部分とを含む。
【0020】
非常に好適には、前記評定関数の前記候補ノード評定部分は、位置参照点又はその絶対座標と、前記第2デジタル地図に現われ前記第2デジタル地図から抽出された前記候補ノード又はその絶対座標との間の表現又は計算された距離に関する依存性を含む。
【0021】
非常に好適には、前記評定関数の前記候補ライン又は候補セグメント評定部分は、前記エンコーダの地図に現われるライン又はセグメントの属性と、位置の解決に用いられる前記第2デジタル地図に現われるこれらの属性との間の類似性を評価する手段を含む。
【0022】
さらに好適には、本方法は、‐前記第2デジタル地図内で連続した候補ノード間のパスのそれぞれについてパス長の値を前記第2デジタル地図から決定する工程であって、前記パスは前記連続した候補ノード間の前記経路探索の結果として確立される、工程と、
‐そのように決定された前記パス長の値を、前記経路探索で用いられる2つの位置参照点のうちの前側の位置参照点のDNP属性に対して比較する工程と、
‐前記パス長の値と前記DNP属性との間の不一致が大きすぎる場合に、パス長の値とDNP属性との間の前記不一致の低減を試みるために位置参照点の連続した各ペアの一方又は両方の位置参照点についての代替の候補ノードと候補ラインとの少なくとも一方を用いて前記経路探索を繰り返すか、若しくはエラーを報告する工程と
をさらに有する。
【0023】
さらに好適には、本方法は、最初の位置参照点及び最後の位置参照点に関連する可能性のある任意のオフセット値を、前記第2デジタル地図に存在するライン又はセグメントの結果のリスト内にあり、完全で連続した位置の表現を提供する最初のライン及び最後のラインに適用する工程をさらに有する。
【0024】
本発明の第2側面では、上述の方法をコンピュータに実行させるコンピュータ・プログラム・コード手段を備えるコンピュータ・プログラムが提供される。さらなる側面では、コンピュータで読み取り可能な記憶媒体に具現化されたこのようなコンピュータ・プログラムが提供される。
【0025】
本発明の第3側面では、場合によってはハンドヘルドであり、パーソナル・ナビゲーション装置(PND)、携帯情報端末(PDA)、移動体電話、およびプロセッサと、前記プログラムを最低限備えることができ、デジタル地図を含む記憶装置と、情報出力のための手段とを含み、上述のコンピュータ・プログラムを実行できる事実上任意のコンピューティング装置のうちの1つであるコンピューティング装置が提供される。ほとんどの実施形態では、情報出力のための手段は前記デジタル地図の図示的表現を表示できる表示スクリーンで構成されるだろう。好適な実施形態では、解決された位置又はその一部は、それが関連する前記デジタル地図の関連部分に重畳され、上乗せされ、並置され、又は連結されて表示される。代替の実施形態では、コンピューティング装置は唯一のものとして又は追加としてオーディオ情報出力手段を含みうる。
【0026】
本発明は、相対的に少ない位置参照点とそれらの対応する属性とのみを用いて、場合によっては非常に長い位置を解決できるという点で既知の技術に対して優れた利点を提供する。本発明はほとんどの近年のデジタル地図は事実上すべての道路交差点を含み、それらのノードを提供するという事実を利用するため、これらの基本的要素から、候補ノードと候補ラインまたは候補セグメントとは任意の近年のデジタル地図を参照して識別されうる。さらに、デジタル地図の大多数はまた、このような交差点間の道路の形式およびクラスについての少なくとも一部の基本属性を含む。解決処理において用いられる第2デジタル地図にこのようなものが現れるなら、属性の比較を行って、第2デジタル地図において識別された1つのラインまたはセグメントが別のものよりも適切であるかどうかに関する判断を行うことが可能である。最後に、本発明は第2デジタル地図内の候補ラインをさらによりよく識別し、多くの候補ラインが識別される場合にそれらをランク付けする手段を提供するために方位計算を利用する。
【0027】
方位属性はエンコーダ側と解決方法の間との両方で計算される属性であり、デジタル地図の一部を一般に形成するものではないことが言及されるべきである。しかしながら、それは正確に計算されえ、正確な識別および/または候補ラインの評定に非常に有用であることがわかる。
【0028】
また、最短パス経路探索は、実装し実行するために利用可能であり周知であり高速である最も単純な経路探索アルゴリズムの1つであるため有用である。さらに有用な利点は、エンコーダで採用される経路探索アルゴリズムが位置の後送信の解決の間に用いられるものと必ずしも同じである必要がないことである。例えば、エンコーダ側でA*を実装し、デコーダ側でダイクストラ・アルゴリズムを実装することが可能である。これら両方のアルゴリズムは主に開始点と終了点との間の距離パラメータに主に基づくため、これらは同じ経路を結果として生じるだろう。A*の場合に、A*アルゴリズムのヒューリスティック要素が所定の要件を満たす必要があるだろうが、すべての実際の場合において、これは任意のイベントにおいてこの場合であるだろうことが言及されるべきである。従って、本発明では、最短パスが発見されることだけが要求される。実在の道路ネットワークにおいて、最短パスは通常は一意であるが、2つ以上の最短パス経路が識別されうる人工的なグリッドまたは都市内の矩形道路レイアウトに沿った経路のような例外的な環境を想像できるだろう。
【0029】
本発明の更なる利点は添付の図面を参照しつつ例示として説明される本発明の以下の個別の実施形態から明らかになるだろう。
【図面の簡単な説明】
【0030】
【図1】本発明の方法の概要フローチャートを示す。
【図2】図2〜図5はノードおよびセグメントを含む第1デジタル地図の概要表現を提供する。図2は例示のネットワークを説明する図である。
【図3】当該ネットワーク内で符号化が望まれる位置パスを説明する図である。
【図4】当該位置を部分的に含む延長されたパスの開始ノードと終了ノードとの間の最短パスを説明する図である。
【図5】当該位置を完全に参照するために必要となる位置参照点を説明する図である。
【図6】図6〜図11はノードおよびセグメントを含む第2デジタル地図の概要表現を提供する。図6は図2のネットワークを説明する図であるが、第2デジタル地図に現れるノードおよびセグメントにより表される。
【図7】第2デジタル地図内に識別される候補ノードを説明する図である。
【図8】第2デジタル地図内に識別される候補ラインを説明する図である。
【図9】位置が完全に参照される最も見込みを有する候補ラインを説明する図である。
【図10】最も見込みを有するラインの間でアルゴリズム的に決定された最短パスを示す図である。
【図11】解決された位置を示す図である。
【図12】図12〜図20は以下に説明される論理データ形式および物理データ形式の文脈で有用である様々な図式説明を提供する。特に図12は位置参照点(LRP)の必要となる連続した連結を示す。
【図13】後続LRPに関して1つのLRPについてどのように方位が計算されるかを説明する図である。
【図14】どのように方位が変わるかを示す図である。
【図15】どのように「次の点への距離」属性がLRPについて決定されうるかを示し、当該属性が関連するLRPはどれかをさらに示す図である。
【図16】オフセットの使用を説明する図である。
【図17】LRPに属性が提供される方法を示す図である。
【図18】、
【図19】位置参照情報の決定の間に回避されるノードを説明する図である。
【図20】どのようにLRPについての方位値が円の32個に分離したセクタの1つに収まるかを説明する図である。
【発明を実施するための形態】
【0031】
本発明の以下の説明はセグメントの観点で提供されるが、本発明は道路ネットワークを通る連続したパスをともに表すラインやラインとセグメントとの組み合わせに等しく適用されうることが理解されるだろう。
【0032】
位置参照情報が符号化される方法の簡潔な説明と符号化処理に用いられる特定の論理データ形式および物理データ形式を最初に提供することが本発明の文脈において有用である。後者は本明細書の補遺として提供され、以下の説明を通じてこの補遺への参照がなされる。
【0033】
まず図2〜図5を参照しつつ、第1の(エンコーダの)地図が図2に示され、15個のノードと23個のライン(双方向のラインは2度数える)とで構成される。ノードは1から15まで番号付けされる。必要なライン属性が形式<FRC>、<FOW>、<メートル単位の長さ>を用いてすべてのラインのそばに示される。FRCは「機能的道路クラス」の略語であり、FOWは「道路種別」の略語であり、これらの両方は以下の補遺により詳細に説明される。矢印は各ラインについての取り得る運転方向を示す。
【0034】
図3において、符号化される位置が太線で示される。位置はノード(3)から始まり、続いてノード(5)、(7)、(10)、(11)、(13)、(14)を通り、ノード(15)で終わる。エンコーダの地図におけるその全長は685メートルである。符号化の間に用いられるラインの順序リストとマップとはエンコーダへの入力としての機能を果たす。
【0035】
符号化:
符号化処理の最初のステップで、位置はまず有効性についてチェックされる。位置は連結され運転可能であり、位置に沿った機能的道路クラスは0と7との間であるため、この位置は有効であるとみなされる。地図データ内のターン制限が使用可能であるか否かに関するチェックを含むことが符号化処理において可能であるが、このステップは簡略化のためにここでは省略される。
【0036】
エンコーダの2番目のステップは、ある所定のデータ形式ルールに従って位置の開始ノードおよび終了ノードが実在ノードであるかをチェックすることである。終了ノード(15)は1つの内向きラインのみを有するので有効である。また、開始ノード(3)は2つの付帯するラインを有するが、ここでは1つは外向きラインであり、1つは内向きラインである。従って、このノードは有効でなく、エンコーダは位置の外側の実在ノードを検索する。エンコーダは実在ノードとしてノード(1)を発見し、位置を一意に拡張するだろう。ノード(1)は位置参照情報のための新たな開始ノードとして選択され、150メートルの正オフセットが存在するだろう。位置参照パスの全長は結果として835メートルになる。
【0037】
エンコーダの3番目のステップは位置の開始ライン(ノード(1)とノード(3)との間のライン)と終了ライン(ノード(14)とノード(15)との間のライン)との間の最短パスの計算を続いて行う。結果の最短パスは図4に太線で概要が説明される。最短パスは725メートルの長さを有する。
【0038】
符号化処理の次(4番目)のステップは、計算された最短パスにより位置が覆われるかどうかをチェックすることである。この場合は覆われておらず、ノード(10)の後に逸脱が存在することが判定されるだろう。
【0039】
本出願人による同日の関連出願に概要が説明された原理に従って、エンコーダはノード(10)からノード(11)へのラインが新たな中間位置参照点になると決定するだろう。経路探索の間にノード(10)をスキップできないためノード(10)は実在ノードであり、このラインへの最短経路は位置の対応する部分を完全に覆う。この最初の最短パス計算の後に覆われる位置の長さは561メートルである。
【0040】
次の符号化ステップは位置の残り部分(ノード(10)からノード(11)、(13)、(14)を経由してノード(15)まで)について最短パスを決定するために経路計算を準備する。従って、最短パス計算は(10)から(11)へのラインで始まり、(14)から(15)へのラインで終わるだろう。
【0041】
エンコーダは上述のステップ3へ戻り、(10)と(15)との間の最短パス(長さ:274メートル)を決定し、上述のステップ4は、現段階で計算された最短パスにより位置が完全に覆われたことを返す。
【0042】
次のステップとして、位置参照パスは2つの最短パスで構成され、位置参照点の順序リストがここで形成されるだろう。図5は位置参照点として選択されたラインが太く示される。1番目の位置参照点はノード(1)からノード(3)へのラインを指し示し、位置参照パスの開始を示す。2番目の位置参照点はノード(10)からノード(11)へのラインを指し示し、このラインは位置からの逸脱を回避するために必要であった。最後の位置参照点はノード(14)からノード(15)へのラインを指し示し、位置参照パスの終了を示す。
【0043】
(任意の途中の有効性チェックを除いて)最後のステップはLRPの順序リストを2進数位置参照情報へ変換することであり、出願人により規定された論理データ形式と物理データ形式との両方について補遺に提供された説明は読者の理解を助けるだろう。補遺に提供される説明と特定の形式に関して提供される詳細とは単に例として提供され、当業者は他の形式を取りうることを理解するだろうことが強調されるべきである。
【0044】
ここで本発明に戻り、最終的に送信される物理データは上記で識別された3つの位置参照点の2進数表現であり、適切なラインを識別できるように属性データを含む。本発明の基本原理の1つは、エンコーダとデコーダとで用いられるデジタル地図は異なるだろう可能性が大きいということである。当然のことながら、これらは同一であるかも知れず、この場合に候補ノードのラインがより正確且つ高速に識別されるために、位置は若干高速に解決されるかもしれないが、いずれの場合であっても本発明の方法はなおも適用されるはずである。
【0045】
図6を参照して、図2に示されるものと同じ部分の道路ネットワークの表現を示すが、異なる第2デジタル地図に従う。2つの図の比較により、ノードとラインとの両方の個数および場所に実質的な相違が存在することがすぐに識別されるだろう。
【0046】
本発明の1つの実施形態に従う処理の概要フローチャート100を示す図1を再び参照して、処理の最初のステップ102は、以前の符号化処理の結果として生じ、物理データ形式に従って構造化された入来する又は無線送信(最も一般的に移動体装置の場合)される2進数データ(もしくはXMLまたはその他の機械で読み取り可能な表現)を復号することである。この2進数データの復号は本発明に不可欠な要素ではなく、位置参照点のリストから位置を解決するために適用される。2進数データの復号は必須の位置参照点を識別するための単なる手段である。
【0047】
ステップ104で、有効性チェックが実行される。この初期ステップでの失敗は手続きを終了する結果となり、124で示されるようにエラーを報告する結果となる。符号化処理および物理形式への縮小は不可逆処理であり、従って2進数データから抽出される情報は、2進数ストリームを作成する前のものほど正確ではないだろう。方位および次の点への距離(DNP)について区間を使用したせいで、正確な値を抽出できず、従って正確な値を含む小区間に精度が制限される。
【0048】
例示の2進数データから抽出される情報が表1、2、3に示され(、さらにそれぞれ図1のステップ106、108、110で参照され)る。
【0049】
【0050】
【0051】
【0052】
この情報は図6に示されるデコーダの地図上の位置を解決するために十分である。この地図は17個のノードと26個のライン(双方向のラインは2度数える)とで構成される。混乱を避けるために、デコーダの地図で参照されるすべてのノードに「X」を前置きする。
【0053】
この地図はいくつかの点でエンコーダの地図(図2参照)とは異なる。一部の長さの値が異なり(例えば、ノードX(3)からX(5)へのライン)、一部の機能的道路クラス値が変更され(例えば、ノードX(3)からX(5)へのライン)、2つの新たなノードX(16)、X(17)が存在し、これらの新たなノードを接続する追加のラインも存在する。デコーダの課題はこの異なる地図で位置を解決することである。
【0054】
データの有効性を検証し、図1のステップ112に示されるように復号された位置参照点(LRP)のリストおよびその属性を提供した後に、デコーダはまずステップ114で各LRPについての候補ノードを決定するためにリスト内の各LRPを処理し始める。(総括的に116で示されるように)LRP座標を用い、デコーダのデジタル地図118に現われる最も近いノード(群)を識別することによって極めて単純に実行されるこの処理の結果として、各LRPについての候補ノードのリストが提供される。120で示されるように、LRPからの距離が所定の閾値よりも大きな地図ノードが排除されうる。図7は、位置参照点の座標の近くに位置する候補ノード(太線の丸)を示す。(上記の表1、2内の)位置参照点1、2について、この例では、1つだけの候補ノードが存在するが、最後の位置参照点について、2つの候補ノードX(16)、X(17)が可能である。
【0055】
また、LRPおよびそれらの属性の処理の一部として、各位置参照点についての候補ラインも識別される。図8の太線はこの例についての候補ラインである。最初のLRPは候補点X(1)により表され、次いでこれは2つの外向きラインを候補として有し、候補点X(10)を有する2番目のLRPは3つの外向きラインを候補として有し、最後の位置参照点は2つの内向きライン(各候補ノードX(15)X、(16)について1つずつ)を有する。114で実行される処理がいずれかのLRPについての候補ラインの識別に失敗したならば、122、124で示されるように処理は失敗しなければならない。処理が完了すると、126で各LRPについての候補ノードおよび候補ラインのリスト(群)が提供される。
【0056】
本発明の1つの実施形態において、特に2つ以上の候補ノードおよび/または2つ以上の候補ラインが各LRPについて識別される場合に、好適には候補を評定またはランク付けする何らかの手段が必要となる。従って、候補ノードのリストと候補ラインのリストとのうち少なくとも一方(好適には両方)に対して、位置参照点の属性を遵守して、評定関数128が適用される。一般に、評定関数の重要な側面は、この適用が、1つ以上の評価基準に従って、候補ノードと候補ラインとのうちの一方または好適には両方のランキングを結果として生じることである。評定関数について多くの相異なる数学的および/または統計的基盤が存在することを当業者は理解し、従って本出願の文脈ではノードに固有の評定関数またはその一部が、復号されたLRPの物理的または地理的場所への候補の距離の何らかの尺度を含んでもよく、候補ラインに固有の評定関数またはその一部が、識別された候補ラインの種類と復号データにおいて表現された種類との間の相関、および場合によってはこの候補の方位と識別されたラインを評定する何らかの手段を含むことを説明すれば十分である。
【0057】
評定関数が適用されると、最も有望な候補が図1のステップ130で識別され、これは図9に説明されるネットワークに見て取れる。特に、最も有望なラインは、ノードX(1)とノードX(3)との間のものと、ノードX(10)とノードX(11)との間のものと、ノードX(14)とノードX(15)との間のものとである。これらのラインは解決処理のステップ132で以下の最短パス計算のために用いられるだろう。
【0058】
最初のLRPと2番目のLRPとで始まる連続したLRPのペアのそれぞれについて最短パス計算が実行され、図1の矢印134で示されるように、この最短パス・アルゴリズムは上記の最も有望な候補ノードおよび候補ラインを用いてデジタル地図118を通る経路を決定し、結果として最終的に図10に示される経路を識別する。このように判定された各最短パスは、当該パスの開始ノードと終了ノードとの間のパス長の値を決定し、次いでこの値を矢印138で示されるように、各LRPについてデータで特定された利用可能なDNP属性と比較することによって、ステップ136で有効性が検証されうる。(ノードX(1)からノードX(10)への)最初の最短パスの長さは557メートルであり、この値は上記の表2に見られる最初のLRPのDNP区間(527.4メートル〜586.0メートル)を満たす。(ノードX(10)からノードX(15)への)2番目の最短パスの長さは277メートルであり、この値も2番目のLRPのDNP区間(234.4メートル〜293.0メートル)を満たす。従って、最短パスは有効性が検証され、デコーダは失敗しない代わりに処理はステップ140、142へ進み、連結された形式、すなわち完全パスに現われるすべてのラインの順序リストを最初に提供し、最後に矢印144で概要が示されるように読み出されたオフセットに従って、ステップ142で連結された最短パスをトリミングする。この例では、正オフセットのみが提供され、従って図11に明示されるように、最短パスはその開始においてトリミングされる。正オフセットの区間(上記の表3、117.2メートル〜175.8メートル)を満たす唯一のノードはノードX(3)である。
【0059】
上記から見て取れるように、本発明は受信した符号化データから位置を解決するための高信頼で効率的な方法を提供する。
【0060】
特定の論理データ形式および物理データ形式が以下に例として提供される。以下の補遺がこれらの形式について取り得る多くの特定の定義のただ1つを提供することを読者は認識するべきである。
【0061】
補遺A
論理データ形式および物理データ形式の仕様
以下の表は本明細書において位置参照情報の文脈で用いられる一般用語および略語を説明する。
【0062】
【0063】
1.データ形式
位置参照情報はデジタル地図の指定された部分または一連の地理的場所の表現である。この表現のために、位置参照点(LRP、1.1.1参照)のモデルを用いる。
【0064】
ライン位置についての位置参照情報は少なくとも2つのLRPを含むがLRPの最大数は規定されない。位置参照パスはLRPにより表現されるデジタル地図内のパスであり、LRPの連続したペアのそれぞれの間の最短パス計算により発見されうる。
【0065】
1.1 論理データ形式の仕様
論理データ形式はMapLoc(商標)標準に従って位置参照情報についての論理モデルを表現する。
【0066】
1.1.1.位置参照点(LRP)
位置参照情報の基盤は一連の位置参照点(LRP)である。このようなLRPはWGS84の経度値および緯度値で特定された座標ペアと、付加的ないくつかの属性とを含む。
【0067】
座標ペア(1.1.3.1参照)は地図/ネットワーク内の地理的位置を表し、LRPについて必須である。座標ペアはネットワーク内の「実在(real)」ノードに属する。
【0068】
属性(セクション1.1.3.2〜1.1.3.6参照)は、座標ペアにより表現されるノードにラインが付帯する、ネットワーク内のラインの値を表す。この文脈では、ノードに関して内向きラインと外向きラインとのどちらを属性が指すかは規定されない。これはセクション1.2で特定される。
【0069】
1.1.2.LRPのトポロジー連結
図12を参照して、位置参照点はトポロジーの順序で、すなわち連続したLRPの「次の点(next point)」関係で記憶されるものとする。この順序の最後の点はこの関係における次の点を有しないだろう。
【0070】
図12はこの関係の例を示す。LRPはA1、B1、およびC1によって示され、黒線矢印は位置参照パスにおけるA1からC1への点の順序を示す。この例では、LRP A1は次の点としてB1を有し、B1は次の点としてC1を有し、C1は次の点を有しないだろう。
【0071】
1.1.3.LRPのコンポーネント
このセクションは位置参照点のコンポーネントを説明する。
【0072】
1.1.3.1 座標ペア
座標ペアはWGS84の経度(lon)の値と緯度(lat)の値とのペアを意味する。この座標ペアはデジタル地図における幾何的な点を特定する。lon値およびlat値はデカミクロンの分解能(10-5、すなわち小数点5位)で記憶される。
【0073】
略語:COORD タイプ:(浮動小数,浮動小数)
【0074】
1.1.3.2 機能的道路クラス
機能的道路クラス(FRC)は道路の重要度に基づく道路分類である。FRC属性の取りうる値が表A2に示される。これら8個の位置参照値よりも多くのFRC値が定義されるならば、適切なマッピングが行われる必要があるか、または重要性の低いクラスが無視される必要がある。
【0075】
【0076】
略語:FRC タイプ:整数
【0077】
1.1.3.3 道路種別(Form of way)
道路種別(FOW)は物理的道路タイプを表現する。FOW属性の取りうる値が表A3に示される。
【0078】
【0079】
略語:FOW タイプ:整数
【0080】
1.1.3.4 方位
方位(BEAR)は、真北と、LRPの座標およびLRP属性により定義されるラインに沿ってBEARDISTである座標により定義されるラインとの間の角度を表現する。ライン長がBEARDISTよりも短いならば、(BEARDISTに関わらず)ラインの反対側の点が使用される。方位は角度単位で測定され、(北から時計回りに測定され)常に正である。パラメータであるBEARDISTは表A4に定義される。
【0081】
略語:BEAR タイプ:整数
【0082】
【0083】
図13は方位計算のための第2点がどのように決定されるかを示す。この図はBEARDISTよりも長いA2からB2へのラインを示す。このラインの斜線部分はBEARDISTメートルちょうどの長さであり、その結果としてB′で印が付けられた点はA2からB2へのラインに沿って移動して、A2からBEARDISTメートル離れている。A2からB′への直線が方位値の計算のために以下で検討される。ラインの反対側のノード(この場合、これはB2であるだろう)が用いられる場合に計算されるだろう角度はこれとは異なる。
【0084】
図14は方位値を計算する2つの例を示す。1つはA3からB3までであり、1つはA3からC3までである2つのラインが存在する。両方のラインについて、弧は北に対する角度を示す。
【0085】
1.1.3.5 次のLRPへの距離
このDNPフィールドはLRPのトポロジー連結における次のLRPへの距離を表現する。距離はメートル単位で測定され、位置参照パスに沿って計算される。最後のLRPは距離値としてゼロを有するだろう。
【0086】
略語:DNP タイプ:整数
【0087】
図15は距離の計算と割り当てとの例を示す。3つのLRPがA4からB4を越えてC4まで一列に存在する。従って、位置参照パスに沿ったA4とB4との距離はA4に割り当てられるだろう。LRP B4はB4とC4との間の距離を保持し、LRP C4は距離値としてゼロを有するだろう。
【0088】
1.1.3.6 次のLRPへの最低FRC
最低FRC(LFRCNP)は2つの連続したLRPの間の位置参照パスに現れる最低のFRC値である。最高のFRC値は0であり、取りうる最低のFRC値は7の値を有する。
【0089】
略語:LFRCNP タイプ:整数
【0090】
1.1.4.オフセット
オフセットは位置参照パスをその開始および終了において縮小するために用いられる。位置参照パスに沿った新たな場所は、位置の実際の開始および実際の終了を示す。
【0091】
1.1.4.1 正オフセット
正オフセット(POFF)は位置参照情報の開始点と所望の位置の開始点との位置参照パスに沿った距離である。値はメートル単位で測定される。図16は正オフセットおよび負オフセットの計算の例を示す。線は位置参照パスを示し、ハッチングは所望の位置を示す。
【0092】
略語:POFF タイプ:整数
【0093】
1.1.4.2 負オフセット
負オフセット(NOFF)は所望の位置の終了点と位置参照情報の終了点との位置参照パスに沿った距離である。値はメートル単位で測定される(図16を再び参照)。
【0094】
略語:NOFF タイプ:整数
【0095】
1.2 関連属性‐LRP
すべての属性はLRPにリンクされる。(最後のLRPを除く)すべてのLRPについて、属性はLRP座標におけるノードの外向きラインを表す。最後のLRPの属性はLRP座標におけるノードの内向きを対象とする。
【0096】
図17はLRPと属性との間の関連の例を示す。ラインは位置参照パスを示し、ノードA5、B5、およびC5がLRPである。開始ノードおよび終了ノードがLRPでないライン(列の3番目のライン)も存在することに留意されたい。このラインは、LRP B5とLRP C5との間の最短パスにより覆われるため、参照される必要はない。
【0097】
LRP A5およびLRP B5は外向きラインを対象とし、最後のLRP C5は内向きラインを対象とする。
【0098】
1.3 データ形式のルール
これらのルールはこの仕様に従う位置参照情報についての追加の規則を表現する。これらのルールは符号化処理および復号処理を単純化し、結果の精度を高めるために用いられる。
【0099】
ルール1 2つの位置参照点の間の最大距離は15kmを超えないものとする。距離は位置参照パスに沿って測定される。位置参照情報についてこの条件が満たされないならば、十分な数の追加のLRPが挿入されるものとする。
【0100】
2つの連続した位置参照点の間の最大距離は最短パス計算を速めるために制限される。なぜなら、経路アルゴリズムがネットワーク全体を考慮に入れなければならない場合に、1つの長い経路よりも複数の短い経路の方が速く計算されうるからである。本制限はまた、許容精度でコンパクトな2進数形式を形成する機会を提供する。
【0101】
ルール2 すべての長さは整数値である。浮動小数値が利用可能ならば、整数表現を得るためにこれらの値を丸める。
【0102】
様々な地図は長さの値を様々な形式で且つ様々な精度で記憶するかも知れず、すべてに対する統一の基盤は整数値を使用することである。また、浮動小数値を用いるよりも2進数形式の整数値を送信する方がコンパクトである。
【0103】
ルール3 2つのLRPが必須であり、中間LRPの個数は制限されない。
【0104】
ライン位置参照情報は位置の開始および終了を示す少なくとも2つの位置参照点を常に有していなければならない。(異なる地図に関して)デコーダに問題が発生するかもしれない危機的状況をエンコーダが検出するならば、位置参照情報は追加の中間LRPで強化されうる。
【0105】
ルール4 LRPの座標は実在ネットワーク・ノード上に選択されるものとする。
【0106】
これらの実在ネットワーク・ノードは現実世界の接点であるべきで、これらの接点はライン上のどこかの場所よりも高い確率で異なる地図で発見されうることが期待される。さらに、経路検索の間に容易にスキップされうるノードは回避されるものとする。これらの回避可能なノードにおいて、経路から逸脱する可能性はない。
【0107】
1つの内向きラインおよび1つの外向きラインのみを有するノードは、これらのノードが接点に関連せず(図18参照)、経路探索の間にスキップされうるために、回避されるものとする。2つの内向きラインおよび2つの外向きラインを有し、2つの隣接ノードのみが存在するノードは同様に回避されるものとする(図19参照)。
【0108】
これらのノードの1つがLRPについて選択されると、このLRPは適切なノードを見つけるために位置参照パスに沿ってシフトされるべきである。これは、所望のパスを逸脱することなくこのような回避可能なノードを経路計算がスキップするために行われうる。
【0109】
位置の開始または終了が回避可能なノード上に配置されるならば、エンコーダは位置を一意に拡張すべきであり、位置の外側の適切なノードを見つけるべきである。この拡張は位置へ入り込むべきではない。なぜなら、これは位置を縮小するだろうからである。
【0110】
1.3.1.データ形式ルールの概要
以下の表はデータ形式ルールを要約する。
【0111】
【0112】
1.4 2進数表現
物理データ形式は上述の論理データ形式についてのバイト指向のストリーム形式を表現する。これはセクション1.1の論理データ形式において表現されたコンポーネントを用いる。
【0113】
1.4.1.データ・タイプ
物理データ形式は以下のデータ・タイプを用いる。表はすべての利用可能なデータ・タイプの概要を与え、名前、タイプ、および各データ・タイプの指定サイズを特定する。以下のセクションでは、データ・タイプ名は各データ・コンポーネントについてサイズおよびタイプを示すために用いられる。
【0114】
【0115】
負の整数値が2つのコンポーネント形式で記憶される。
【0116】
1.4.2.座標(COORD)
地図内の各点はWGS84座標で表された「経度」(lon)と「緯度」(lat)との座標ペアで構成される。北方向および東方向は(経度、緯度それぞれ)正の値で表される。lot値およびlat値はデカミクロンの分解能(10-5、小数点第5位)で記憶される。
【0117】
座標値は整数値として送信されるだろう。これらの値は24ビット整数表現を算出する式E1を用いて生成されるだろう。分解能パラメータは24に設定される。この変換は最大で約2.4メートルの誤差を生じる。逆変換は式E2で表現される。両方の式は、負の値について−1、正の値について1、その他について0である符号関数を利用する。
【0118】
【0119】
【0120】
物理形式は絶対座標形式と相対座標形式とを利用する。絶対形式は地理的場所の指定された値を表し、相対値は先行する座標に対するオフセット座標である。
【0121】
1.4.2.1 絶対形式
絶対形式は24ビット分解能における地理的場所を表現する。表A7は絶対形式に用いられるデータ・タイプを示す。
【0122】
【0123】
1.4.2.2 相対形式
相対形式は2つの連続した座標間の差を表現するために用いられる。差は式E3に示されるように各値(lon/lat)別々に計算される。現在の値および前の値は緯度値(経度値)を角度単位で表す。これら2つの値の差は整数値へ変化させるために100000倍される。
【0124】
【0125】
表A8は16ビット表現を用いて取りうる最大距離を示す。この図はlon=5°、lat=52°(オランダ内の場所)における固定の座標について計算される。
【0126】
【0127】
表A9は2バイト・オフセットについてのデータ・タイプを示す。
【0128】
【0129】
1.4.3.属性値
属性の2進数形式がこのセクションで続く。
【0130】
1.4.3.1 機能的道路クラス(FRC)
機能的道路クラス(FRC)は論理形式で説明されたように8個の相異なる値を保持しうる。これらの8個の値は表A10で示される3ビットとマッピングとにより表される。
【0131】
【0132】
1.4.3.2 道路種別(FOW)
道路種別(FOW)は論理形式において説明されたように8個の相異なる値を保持しうる。これらの8個の値は表A11で示される3ビットとマッピングとにより表される。
【0133】
【0134】
1.4.3.3 方位(BEAR)
方位は論理形式において説明されたように道路と真北との間の角度を表現する。物理データ形式は32個のセクタを定義し、各セクタは円のうち11.25°をカバーする。これらの32個のセクタは5ビットで表される。表A12は方位属性についてのデータ・タイプを示し、表A13はセクタから具体的な値へのマッピングを示す。
【0135】
【0136】
【0137】
式E4は方位値の計算の概要を説明し、図20はセクタの図示による概要を提供する。
【0138】
【0139】
1.4.3.4 次のLRPへの距離(DNP)
DNP属性は論理形式において説明されたように位置参照パスに沿った2つの連続したLRP間の距離を測定する。
【0140】
物理データ形式は8ビット表現を定義し、表A14はDNPについて用いられるデータ・タイプを示す。この表現は255個の間隔を定義し、データ形式ルールのルール1(2つの連続したLRP間の最大長は15000mに制限される)と組み合わせて各間隔は58.6メートルの長さを有するだろう。
【0141】
【0142】
式E5はどのようにDNP値を計算できるかを示す。
【0143】
【0144】
1.4.3.5 次の点への最低FRC(LFRCNP)
次の点への最低FRCは次のLRPへの位置参照パスに用いられる最低の機能的道路クラスを示す。この情報は復号の間にスキャンされる必要のある道路クラスの個数を制限するために用いられうる。データ・タイプの定義については表A15を参照されたい。
【0145】
【0146】
1.4.4.位置参照情報ヘッダ
位置参照情報ヘッダは参照情報に関する一般的な情報を含む。
【0147】
1.4.4.1 バーション(VER)
バーションは位置参照情報についての複数の物理的なデータ・フォーマットを区別するために用いられる。バージョン番号は3ビットで表され、データ・タイプは表A16に示される。
【0148】
【0149】
1.4.4.2 属性フラグ(AF)
属性フラグは各LRPへ付加された属性が存在するか否かを示す。属性が付加されていない場合にAF値は0となり、従って位置参照情報は座標だけで構成される。それ以外の場合、値は1となり各LRPへ属性が付加されることを示す。AFについてのデータ・タイプは表A17、A18に示される。
【0150】
【0151】
【0152】
1.4.4.3 領域フラグ(ArF)
領域フラグは位置参照情報が領域を記載するか否かを示す。このフラグが設定されるならば、位置は結合しているものとし、以下の表A19、A20に見られるように領域を表現する。
【0153】
【0154】
【0155】
1.4.5.オフセット
オフセットはネットワーク内のノードへ結び付けられたものよりも正確に位置の開始および終了を位置付けるために用いられる。論理形式は、1つは位置の開始において、もう1つは位置の終了において2つのオフセットを定義し、両方のオフセットは位置のラインに沿って作用し、メートル単位で測定される。オフセット値は必須ではなく、オフセット値がないことは0メートルのオフセットを意味する。また、オフセットは属性が含められたライン位置についてのみ有効である。
【0156】
1.4.5.1 オフセット・フラグ
オフセット・フラグはデータが特定のオフセット情報を含むかどうかを示す。物理データ形式は2つの相異なるオフセット値に対応する2つのフラグを扱う。正オフセット・フラグ(PoffF)と負オフセット・フラグ(NoffF)とが表A21、A22に表現される。
【0157】
【0158】
【0159】
1.4.5.2 オフセット値
オフセット値(正および負、POFFおよびNOFF)は位置参照パスの開始(終了)と位置の「実在の(real)」開始(終了)との間の距離を示す。
【0160】
物理データ形式は各オフセット値について8ビット表現を定義する。表A23はPOFFおよびNOFFについて用いられるデータ・タイプを示す。この表現は各間隔の長さが58.6メートルである256個の間隔を定義することを可能にする。オフセットについての間隔番号の計算は式E6に概要が説明される。
【0161】
【0162】
【0163】
1.5 物理データ形式の仕様
このセクションはバイト・ストリーム内のデータ・フィールドの構成を表現する。バイト指向のストリームを有し、バイトごとに8ビットを使用できると想定する。
【0164】
1.5.1.概要
2進数形式の主な構造は、ヘッダ、先頭LRP、後続LRP、末尾LRP、およびオフセットである。ヘッダ、先頭LRP、および末尾LRPは必須であり、後続LRPの個数は制限されない。末尾LRPは相異なる情報レベルに起因して独自の構造を有する。オフセットはオプションであり、その存在は末尾LRPの属性内のフラグにより示されるだろう。
【0165】
表A24は主な構造の概要を与える。ストリームは左から右へ読み取ることができ、それにより最初に受信されるバイトは状態バイトであるだろう。各座標について、最初に受信される値は経度値であり、緯度値がそれに続くだろう。
【0166】
LRPの個数に依存するメッセージ・サイズの計算は以下のセクション1.6に見られうる。
【0167】
【0168】
1.5.2 状態バイト
状態バイトはすべての位置参照情報について1回送信され、領域フラグ(ArF、セクション1.4.4.3)、属性フラグ(AF、セクション1.4.4.2)、およびバージョン情報(VER、セクション1.4.4.1)を含む。ビット7、6、5は将来の使用のために予約(RFU)され、0であるものとする。表A25は状態バイトの各ビットの用途の概要を与える。
【0169】
【0170】
形式のこの特定のバージョンでは、属性が各LRPへ付加され、領域は表現されない。「現在のバージョン」が2であるならば、状態バイトは表A26に示される値を有するだろう。
【0171】
【0172】
1.5.3.先頭LRPの座標
先頭LRPの座標は絶対形式(セクション1.4.2.1参照)で送信され、従って各値(lotおよびlat)は3バイトを用いるだろう。表A27は経度値および緯度値についてのバイト順を示す。
【0173】
【0174】
1.5.4.後続LRPの座標
後続LRPおよび末尾LRPの座標は相対形式(セクション1.4.2.2参照)で送信され、従って各値(lotおよびlat)は2バイトを用いるだろう。表A28は経度値および緯度値についてのバイト順を示す。
【0175】
【0176】
1.5.5.属性
属性は各LRPへ付加される。位置参照情報におけるLRPの場所に依存して相異なる4種類の属性が存在する。
【0177】
1.5.5.1 第1属性バイト(属性1)
第1属性バイトは属性FRC(セクション1.4.3.1参照)とFOW(セクション1.4.3.2参照)とを含み、2ビットが将来の使用のために予約される。表A29は各ビットの用途を示す。
【0178】
【0179】
1.5.5.2 第2属性バイト(属性2)
第2属性バイトは属性LFRCNP(セクション1.4.3.5)と属性BEAR(セクション1.4.3.3参照)とを含む。表A30は各ビットの用途を示す。LFRCNP情報が利用可能でないため、この属性は末尾LRPに対して有効でない。
【0180】
【0181】
1.5.5.3 第3属性バイト(属性3)
第3属性バイトは表A31に示されるように属性DNP(セクション1.4.3.4参照)を含む。DNP情報が利用可能でないため、この属性は末尾LRPに対して有効でない。
【0182】
【0183】
1.5.5.4 第4属性バイト(属性4)
属性4はBEAR情報、正および負のオフセット・フラグ(セクション1.4.5.1参照)、ならびに将来の使用のために予約された1ビットを含む。表A32に示されるように、この属性は末尾LRPについて用いられる。
【0184】
【0185】
1.5.6 オフセット
正オフセット(POFF)および負オフセット(NOFF)は、属性4内の対応するフラグがそれらの存在を示す場合にのみ含まれる。オフセット値を含まないことは0メートルのオフセット値を示す。オフセット値はセクション1.4.5に従って計算され、これらのオフセットのビット用途は表A33、A34に示される。
【0186】
【0187】
【0188】
1.6 メッセージ・サイズの計算
位置参照情報のメッセージ・サイズは位置参照情報に含まれるLRPの個数に依存する。位置参照情報には少なくとも2つのLRPが含まれるべきである。また、状態情報を伴うヘッダが必須である。以下の計算と表A35とはLRPの個数に依存するメッセージ・サイズを示す。
・ヘッダ
1バイト状態
合計:1バイト
・先頭LRP
6バイトCOORD(lon/latのそれぞれについて3バイト)
3バイト属性
合計:9バイト
・後続LRP
4バイトCOORD(lon/latのそれぞれについて2バイト)
3バイト属性
合計:7バイト
・末尾LRP
4バイトCOORD(lon/latのそれぞれについて2バイト)
2バイト属性
合計:6バイト
・オフセット(含まれる場合)
1バイト正オフセット(含まれる場合)
1バイト負オフセット(含まれる場合)
合計:0〜2バイト
【0189】
【0190】
上記の形式が用いられる方法の特定の例が、図2〜図5を参照して上述された位置参照情報を参照して以下に提供される。これらの図では3つの位置参照点(ノード(1)、(10)、(15)およびライン(1)〜(3)、(10)〜(11)、(14)〜(15))が位置を正確に表現するために識別される。位置参照情報は3つの位置参照点で構成され、以下の表A36はノード(1)、(10)、(15)についての座標を示す。これらのノードは位置参照点に対応するノードである。2進数形式の準備において、この表はまた、相対座標を示す。ノード(1)は位置参照点1に対応し、絶対形式の座標を有するだろう。位置参照点2に対応するノード(10)は位置参照点1に対する相対座標を有するだろう。位置参照点3に対応するノード(15)も相対座標を有するだろうが、ここでは位置参照点2を参照する。
【0191】
【0192】
相対経度および相対緯度は上記の式E3に従って計算される。符号化処理のステップ2で計算されるオフセットが表A37に示される。2進数データにおいて、正オフセットのみが現れるだろう。なぜなら、負オフセットは0であり、オフセットがない場合は0として扱われるだろうからである。
【0193】
【0194】
以下の表A38は基底のデジタル地図から計算を通じて各位置参照点についての関連データを収集する。これは機能的道路クラス、道路種別、および対応するラインの方位を含む。2つの連続した位置参照点間のパスに関して必要な情報(最低機能的道路クラスと次の位置参照点への距離)も示される。
【0195】
【0196】
BEAR属性、LFRCNP属性、およびDNP属性は上述のように決定される。以下の表は2進数データを作成するためのすべての関連情報を保持する。以下の表は物理データ形式に従って2進数データの概要を説明する。
・状態タイプ:表A39を参照。
・LRP1: 表A40〜A44を参照。
・LRP2: 表A45〜A49を参照。
・LRP3: 表A50〜A53を参照。
・オフセット:表A54を参照。
【0197】
【0198】
【0199】
【0200】
【0201】
【0202】
【0203】
【0204】
【0205】
【0206】
【0207】
【0208】
【0209】
【0210】
【0211】
【0212】
【0213】
完全な2進数データストリームは24バイトの長さを有し、以下のもので構成される(左から右へ、そして上から下へのバイトとして並ぶ)。
【0214】
【特許請求の範囲】
【請求項1】
エンコーダのデジタル地図におけるノードを表す複数の位置参照点であって、前記エンコーダの地図においてこれらのノードから出るか又はこれらのノードへ入る特定のライン又はセグメントを表す属性をそれぞれが有する複数の位置参照点の順序リストから位置を解決する方法であって、
(i)各位置参照点について、第2デジタル地図内に存在する少なくとも1つの候補ノードを識別するとともに、前記第2デジタル地図に存在し、前記候補ノードから出るか又は前記候補ノードへ入る少なくとも1つの候補ライン又は候補セグメントを当該位置参照点の利用可能な属性を用いて識別する工程と、
(ii)前記第2デジタル地図において、
‐前記少なくとも1つの候補ノードのうちの少なくとも1つ、及び当該ノードから出るか当該ノードへ入る対応する候補ライン又は候補セグメントと、
‐前記リストに現われる次の位置参照点についての少なくとも1つの候補ノード、及び当該候補ノードから出るか又は当該候補ノードへ入る対応する候補ライン又は候補セグメントと
の間の経路探索を実行し、前記候補ノード間で決定された前記経路の一部を形成する各ライン又はセグメントを前記第2デジタル地図から抽出する工程と、
(iii)前記リストに現われる最後の位置参照点に到達するまで、位置参照点の連続したペアのそれぞれについて工程(ii)を繰り返す工程と
を有することを特徴とする方法。
【請求項2】
前記経路探索は最短パス経路探索であることを特徴とする請求項1に記載の方法。
【請求項3】
前記経路探索は連続した候補ノードのそれぞれのペアに作用することを特徴とする請求項1又は2に記載の方法。
【請求項4】
前記経路探索は、ノードのペアのうちの前側のノードに対応するライン又はセグメントが、当該経路探索の結果として生じる経路の一部を形成することを保証する手段を含むことを特徴とする請求項1乃至3の何れか1項に記載の方法。
【請求項5】
前記識別される候補ノードは、現実世界の交差点を表す実在のノードであることを特徴とする請求項1乃至4の何れか1項に記載の方法。
【請求項6】
前記第2デジタル地図から各ライン又はセグメントを抽出する前記工程は、前記抽出されたライン又はセグメントのそれぞれを位置パス・リストに記憶することによって強化されることを特徴とする請求項1乃至5の何れか1項に記載の方法。
【請求項7】
連続する経路探索のそれぞれについて作成された位置パス・リストのそれぞれが連結されることを特徴とする請求項6に記載の方法。
【請求項8】
後続する経路探索の間に抽出されるライン又はセグメントが既存の位置パス・リストへ付加されることを特徴とする請求項6に記載の方法。
【請求項9】
位置参照点について2つ以上の候補ノードが識別される場合に、1つ以上の所定の評価基準に従って前記識別された候補ノードを評定する工程をさらに有することを特徴とする請求項1乃至8の何れか1項に記載の方法。
【請求項10】
前記第2デジタル地図に存在する2つ以上の候補ライン又は候補セグメントが識別される場合に、1つ以上の所定の評価基準に従って最も見込みを有する候補ライン又は候補セグメントを識別するために候補ライン又は候補セグメントを評定する工程をさらに有することを特徴とする請求項1乃至9の何れか1項に記載の方法。
【請求項11】
前記評定する工程は評定関数を用いて実現されることを特徴とする請求項9又は10に記載の方法。
【請求項12】
前記評定関数は候補ノード評定部分と、候補ライン又は候補セグメント評定部分とを含むことを特徴とする請求項11に記載の方法。
【請求項13】
前記評定関数の前記候補ノード評定部分は、位置参照点又はその絶対座標と、前記第2デジタル地図に現われ前記第2デジタル地図から抽出された前記候補ノード又はその絶対座標との間の表現又は計算された距離に関する依存性を含むことを特徴とする請求項12に記載の方法。
【請求項14】
前記評定関数の前記候補ライン又は候補セグメント評定部分は、前記エンコーダの地図に現われるライン又はセグメントの属性と、位置の解決に用いられる前記第2デジタル地図に現われるこれらの属性との間の類似性を評価する手段を含むことを特徴とする請求項12に記載の方法。
【請求項15】
‐前記第2デジタル地図内で連続した候補ノード間のパスのそれぞれについてパス長の値を前記第2デジタル地図から決定する工程であって、前記パスは前記連続した候補ノード間の前記経路探索の結果として確立される、工程と、
‐そのように決定された前記パス長の値を、前記経路探索で用いられる2つの位置参照点のうちの前側の位置参照点のDNP属性に対して比較する工程と、
‐前記パス長の値と前記DNP属性との間の不一致が大きすぎる場合に、パス長の値とDNP属性との間の前記不一致の低減を試みるために位置参照点の連続した各ペアの一方又は両方の位置参照点についての代替の候補ノードと候補ラインとの少なくとも一方を用いて前記経路探索を繰り返すか、若しくはエラーを報告する工程と
をさらに有することを特徴とする請求項1乃至14の何れか1項に記載の方法。
【請求項16】
最初の位置参照点及び最後の位置参照点に関連する可能性のある任意のオフセット値を、前記第2デジタル地図における前記経路探索の結果として前記第2デジタル地図から抽出された最初のライン及び最後のラインに適用する工程をさらに有することを特徴とする請求項1乃至15の何れか1項に記載の方法。
【請求項17】
請求項1乃至16の何れか1項に記載の方法をコンピュータに実行させるコンピュータ・プログラム・コード手段を備えることを特徴とするコンピュータ・プログラム。
【請求項18】
コンピュータで読み取り可能な記憶媒体に具現化されたことを特徴とする請求項19に記載のコンピュータ・プログラム。
【請求項19】
プロセッサと、
請求項18又は19に記載のコンピュータ・プログラムを備えることができ、当該コンピュータ・プログラムのための実行環境を提供する記憶装置と、
同一又は異なる記憶装置に記憶される可能性があるデジタル地図であるプログラム・リソースと、
情報出力手段と
を備えることを特徴とするコンピューティング装置。
【請求項20】
前記情報出力手段は、可聴出力、印刷された出力、又は前記デジタル地図の図示的表現を表示可能な表示スクリーン上に表示可能な出力のうちの少なくとも1つを提供することを特徴とする請求項19に記載のコンピューティング装置。
【請求項21】
解決された位置又はその一部は、それが関連する前記デジタル地図の関連部分に重畳され、上乗せされ、並置され、又は連結されて表示されることを特徴とする請求項20に記載のコンピューティング装置。
【請求項1】
エンコーダのデジタル地図におけるノードを表す複数の位置参照点であって、前記エンコーダの地図においてこれらのノードから出るか又はこれらのノードへ入る特定のライン又はセグメントを表す属性をそれぞれが有する複数の位置参照点の順序リストから位置を解決する方法であって、
(i)各位置参照点について、第2デジタル地図内に存在する少なくとも1つの候補ノードを識別するとともに、前記第2デジタル地図に存在し、前記候補ノードから出るか又は前記候補ノードへ入る少なくとも1つの候補ライン又は候補セグメントを当該位置参照点の利用可能な属性を用いて識別する工程と、
(ii)前記第2デジタル地図において、
‐前記少なくとも1つの候補ノードのうちの少なくとも1つ、及び当該ノードから出るか当該ノードへ入る対応する候補ライン又は候補セグメントと、
‐前記リストに現われる次の位置参照点についての少なくとも1つの候補ノード、及び当該候補ノードから出るか又は当該候補ノードへ入る対応する候補ライン又は候補セグメントと
の間の経路探索を実行し、前記候補ノード間で決定された前記経路の一部を形成する各ライン又はセグメントを前記第2デジタル地図から抽出する工程と、
(iii)前記リストに現われる最後の位置参照点に到達するまで、位置参照点の連続したペアのそれぞれについて工程(ii)を繰り返す工程と
を有することを特徴とする方法。
【請求項2】
前記経路探索は最短パス経路探索であることを特徴とする請求項1に記載の方法。
【請求項3】
前記経路探索は連続した候補ノードのそれぞれのペアに作用することを特徴とする請求項1又は2に記載の方法。
【請求項4】
前記経路探索は、ノードのペアのうちの前側のノードに対応するライン又はセグメントが、当該経路探索の結果として生じる経路の一部を形成することを保証する手段を含むことを特徴とする請求項1乃至3の何れか1項に記載の方法。
【請求項5】
前記識別される候補ノードは、現実世界の交差点を表す実在のノードであることを特徴とする請求項1乃至4の何れか1項に記載の方法。
【請求項6】
前記第2デジタル地図から各ライン又はセグメントを抽出する前記工程は、前記抽出されたライン又はセグメントのそれぞれを位置パス・リストに記憶することによって強化されることを特徴とする請求項1乃至5の何れか1項に記載の方法。
【請求項7】
連続する経路探索のそれぞれについて作成された位置パス・リストのそれぞれが連結されることを特徴とする請求項6に記載の方法。
【請求項8】
後続する経路探索の間に抽出されるライン又はセグメントが既存の位置パス・リストへ付加されることを特徴とする請求項6に記載の方法。
【請求項9】
位置参照点について2つ以上の候補ノードが識別される場合に、1つ以上の所定の評価基準に従って前記識別された候補ノードを評定する工程をさらに有することを特徴とする請求項1乃至8の何れか1項に記載の方法。
【請求項10】
前記第2デジタル地図に存在する2つ以上の候補ライン又は候補セグメントが識別される場合に、1つ以上の所定の評価基準に従って最も見込みを有する候補ライン又は候補セグメントを識別するために候補ライン又は候補セグメントを評定する工程をさらに有することを特徴とする請求項1乃至9の何れか1項に記載の方法。
【請求項11】
前記評定する工程は評定関数を用いて実現されることを特徴とする請求項9又は10に記載の方法。
【請求項12】
前記評定関数は候補ノード評定部分と、候補ライン又は候補セグメント評定部分とを含むことを特徴とする請求項11に記載の方法。
【請求項13】
前記評定関数の前記候補ノード評定部分は、位置参照点又はその絶対座標と、前記第2デジタル地図に現われ前記第2デジタル地図から抽出された前記候補ノード又はその絶対座標との間の表現又は計算された距離に関する依存性を含むことを特徴とする請求項12に記載の方法。
【請求項14】
前記評定関数の前記候補ライン又は候補セグメント評定部分は、前記エンコーダの地図に現われるライン又はセグメントの属性と、位置の解決に用いられる前記第2デジタル地図に現われるこれらの属性との間の類似性を評価する手段を含むことを特徴とする請求項12に記載の方法。
【請求項15】
‐前記第2デジタル地図内で連続した候補ノード間のパスのそれぞれについてパス長の値を前記第2デジタル地図から決定する工程であって、前記パスは前記連続した候補ノード間の前記経路探索の結果として確立される、工程と、
‐そのように決定された前記パス長の値を、前記経路探索で用いられる2つの位置参照点のうちの前側の位置参照点のDNP属性に対して比較する工程と、
‐前記パス長の値と前記DNP属性との間の不一致が大きすぎる場合に、パス長の値とDNP属性との間の前記不一致の低減を試みるために位置参照点の連続した各ペアの一方又は両方の位置参照点についての代替の候補ノードと候補ラインとの少なくとも一方を用いて前記経路探索を繰り返すか、若しくはエラーを報告する工程と
をさらに有することを特徴とする請求項1乃至14の何れか1項に記載の方法。
【請求項16】
最初の位置参照点及び最後の位置参照点に関連する可能性のある任意のオフセット値を、前記第2デジタル地図における前記経路探索の結果として前記第2デジタル地図から抽出された最初のライン及び最後のラインに適用する工程をさらに有することを特徴とする請求項1乃至15の何れか1項に記載の方法。
【請求項17】
請求項1乃至16の何れか1項に記載の方法をコンピュータに実行させるコンピュータ・プログラム・コード手段を備えることを特徴とするコンピュータ・プログラム。
【請求項18】
コンピュータで読み取り可能な記憶媒体に具現化されたことを特徴とする請求項19に記載のコンピュータ・プログラム。
【請求項19】
プロセッサと、
請求項18又は19に記載のコンピュータ・プログラムを備えることができ、当該コンピュータ・プログラムのための実行環境を提供する記憶装置と、
同一又は異なる記憶装置に記憶される可能性があるデジタル地図であるプログラム・リソースと、
情報出力手段と
を備えることを特徴とするコンピューティング装置。
【請求項20】
前記情報出力手段は、可聴出力、印刷された出力、又は前記デジタル地図の図示的表現を表示可能な表示スクリーン上に表示可能な出力のうちの少なくとも1つを提供することを特徴とする請求項19に記載のコンピューティング装置。
【請求項21】
解決された位置又はその一部は、それが関連する前記デジタル地図の関連部分に重畳され、上乗せされ、並置され、又は連結されて表示されることを特徴とする請求項20に記載のコンピューティング装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【公表番号】特表2011−526696(P2011−526696A)
【公表日】平成23年10月13日(2011.10.13)
【国際特許分類】
【出願番号】特願2011−515416(P2011−515416)
【出願日】平成21年6月29日(2009.6.29)
【国際出願番号】PCT/EP2009/058130
【国際公開番号】WO2010/000706
【国際公開日】平成22年1月7日(2010.1.7)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.GSM
【出願人】(307043223)トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【Fターム(参考)】
【公表日】平成23年10月13日(2011.10.13)
【国際特許分類】
【出願日】平成21年6月29日(2009.6.29)
【国際出願番号】PCT/EP2009/058130
【国際公開番号】WO2010/000706
【国際公開日】平成22年1月7日(2010.1.7)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.GSM
【出願人】(307043223)トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【Fターム(参考)】
[ Back to top ]