効率的な位置参照方法
道路ネットワーク内の連続したパスを符号化する効率的な方法が記載される。理想的には、パスはデジタル地図に完全に表されるとともに、デジタル地図内に存在して連続に順序付けされたラインとセグメントとのうちの少なくとも一方のパス・リストとして表現可能である。本方法は、(i)‐パス・リストに最初に現われるライン又はセグメントか、若しくは最初のライン又はセグメントの開始ノードが人工的である場合に、実在の開始ノードを有するデジタル地図に現われ、場合によっては他の人工ノードを介して最初のライン又はセグメントに直接につながる最初のライン又はセグメントと、‐パス・リストに同様に現われる最も直近に識別された逸脱ライン又は逸脱セグメントとのうちの１つである開始場所を経路探索リストに記憶する工程と、(ii)開始場所を含み、開始場所の開始ノードからパス・リスト内の最後のライン又はセグメントの終点ノードへのデジタル地図内のパスを決定する工程であって、パスはアルゴリズムに従って決定される、工程と、(iii)そのように決定された最短パスを識別のためにパス・リストに対して比較し、識別できない場合に、パス・リストの一部であり、デジタル地図内の交差点を表す開始ノードを有するものの、パス・リストに最初に現われるライン又はセグメントではない少なくとも１つの逸脱ライン又は逸脱セグメントを識別し、このような逸脱ライン又は逸脱セグメントがパス・リストに現われる最後のライン又はセグメントの終了ノードで終わらない場合に、逸脱ライン又は逸脱セグメントを用いて工程(i)を繰り返す工程と、(iv)パス・リスト内の最後のライン又はセグメントが既に記憶されていない場合に経路探索リストに記憶する工程とを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は効率的な地図アグノスティックでオンザフライの位置参照方法に関する。特に本方法は、テレアトラスＢ．Ｖ．およびナビテック・インクのような会社により製造され販売されるようなデジタル地図を前提条件として含んでいるが、使用されるデジタル地図の特定のバージョンまたはタイプは結果として生じる物理位置の符号化表現に対して基本的に重要でないという点で最終的に地図アグノスティックである位置符号化方法に具現化される。
【０００２】
明確性の理由で、本明細書で用いられる「位置（location）」という用語は、地表上のポイント位置、連続したパスまたは経路、またはこれらの連続したチェーンのような、地球上に存在するナビゲート可能な通路、または２個（長方形、正方形、または円形の領域の場合）またはより多いパラメータにより規定可能な地球上の領域または地域に関する様々な相異なる物理的な現実世界の特徴を包含するものとみなされる。より簡潔に、位置は単一または複合された地理的オブジェクトである。しかしながら、本発明は道路ネットワークを通るパスまたはデジタル地図に表されるその他のナビゲート可能な通路に関する効率的な、機械で読み取り可能な表現に主に適用される。
【背景技術】
【０００３】
ジオコーディングは、ストリート・アドレス、国、および／または郵便番号のような物理位置についての人間用参照システムを例えば緯度および経度のような関連する地理的座標に変換する既知の技術である。現在のところ様々な相異なるジオコーディング・システムが存在し、地理的座標空間にストリート・ネットワークがすでにマッピングされている地理的情報システム（ＧＩＳ）に少なくとも何らかの範囲で依存する。逆ジオコーディングは反対の処理である。
【０００４】
いかなる近年のデジタル地図（または時々知られるように数学的グラフ）もＧＩＳとしてみなすことができ、最も単純な形式では事実上、最も一般的には道路の交差点を現す（点または０次元オブジェクトとみなしうる）ノードを最初に規定し、交差点間の道路を表すノード間のラインを２番目に規定する複数のテーブルから構成されるデータベースである。より詳細なデジタル地図では、ラインは開始ノードおよび終了ノードにより定義されるセグメントに分割されてもよい。開始ノードと終了ノードとは、セグメント長がゼロのセグメントまたはループ状のセグメント（この場合にセグメントは非ゼロ長を有する）の場合に同一でありうるが、一般的には別々である。３つ以上のラインまたはセグメントが交わる道路交差点を表す場合に本明細書でノードは実在または「有効（valid）」であるとみなされうるが、「人工的（artificial）」または「回避可能な（avoidable）」ノードは一方または両方の端が実在ノードで定義されないセグメントに対してアンカーとして提供されるノードである。とりわけ道路の特定の範囲について形状情報を提供するためにこれらの人工ノードはデジタル地図において有用である。
【０００５】
このように、ノード、ライン、およびセグメントは道路ネットワークを完全に表現するために用いられてもよく、データベース内の各要素はさらに、データベースのテーブル内のデータによりやはり表される様々な属性により定義される。例えば、各ノードは典型的に現実世界の位置を規定するための緯度属性および経度属性を有するだろう。道路ネットワークの完全な「グラフ」は１つ以上の国またはその一部に及ぶ領域を覆うために何百万ものノードおよびセグメントにより表現される。
【０００６】
実際上、近年のすべてのデジタル地図がノードおよびセグメントの構造的定義を含んでいるが、これを達成する実際の方式はデジタル地図の提供者間で極めて多様である。例えば、各地図ベンダ（および場合によっては地図の各バーション）はノードであろうとセグメントであろうと、各地図要素に一意のＩＤを用いうる。従って、単純なジオコーディングおよび逆ジオコーディングでさえ、前提のデジタル地図が具現化されるデータベースの基底構造の何らかの知識を有する場合にのみ可能である。より単純な例では、緯度および経度に基づいて１つのデジタル地図データベースからストリート・アドレスを抽出するように設計されたクエリは別のものでは必ずしも動作しないだろう。対象の特定のデジタル地図データベースについて適切なように作り直す必要がありうる。これはまた、同じベンダにより提供されるデジタル地図の相異なるバージョンについても成り立ちうる。
【０００７】
デジタル地図データベースにしばしば含まれる１つの特定の属性は交通メッセージ・チャネル（ＴＭＣ）位置テーブル参照である。ＴＭＣは交通および移動の情報を乗り物のユーザ、より具体的にはこれらの乗り物内に存在し、何らかのデジタル地図の形式を含む（ポータブルまたは搭載型の）ナビゲーション・システムへ配信するための技術である。ＴＭＣメッセージは、（交通固有である必要はないが、これらが最も一般的である）イベント・コードおよび位置コードで構成され、位置コードはしばしば位置参照情報の順序リストで構成され、順序リストを用いて交通イベントの位置がデジタル地図において決定され、よってナビゲーション・システムの画面に図示されうる。デジタル地図内の複数の事前定義されたノードが、限られた位置テーブルを参照して決定されるＴＭＣ位置参照情報に割り当てられる。通常は道路交差点であり、デジタル地図で識別可能であるおおよそ同数の物理的または現実世界の位置に対応する２16（６５５３６）個の位置参照情報から位置テーブルは構成される。
【０００８】
３７ビットほどの短さでありえ、従って放送データのために利用可能な帯域にあまり影響を与えない点でＴＭＣメッセージは非常に効率的であるが、固定数の位置参照情報だけが利用可能であり、従って典型的に、ＴＭＣを提供する各国内の自動車道路または主要高速道路（もしくはその交差点）だけが参照されうる。ＴＭＣ位置参照情報にはその他に様々な不利益が存在する。例えば、ＴＭＣ位置テーブルは、
‐国家機関または国内政府を通じてしばしば維持され、
‐伝統的に非常に長い更新間隔で変更されがちであり、
‐一部の市場において、存在しないか、商業的にのみ利用可能である。
ＧＳＭおよびＧＰＳのプローブ・データを用いて二次的および都市部の道路に交通集積を識別することが可能になってきている（例えば乗り物のユーザはプローブとして使用可能な移動体電話または衛星接続ナビゲーション装置をますます所有する）ため、より発展的な参照システムが必要になる。
【０００９】
ＴＭＣ位置参照情報または地図固有の参照情報の欠点の一部を克服するための１つの試みは（ＩＳＯ１７５７２−１、２、３のもとで標準化過程にある）ＡＧＯＲＡ−Ｃとしても知られる動的位置参照プロジェクトである。ＡＧＯＲＡ−Ｃ位置参照アプローチの完全な説明は本出願の範囲外であるが、本アプローチの基本は、緯度および経度の座標ペアにより特定され、リスト内に順序付けされた位置点（location point）の集合により位置参照情報が完全に特定されえ、各点は様々なルールに従うが、最も重要なものとして、参照されている位置とリスト内の直前の点とが、すなわち連続した点が次点関係を形成するという点で各点が連続することである。他の位置参照システムと同様に、各点には複数の属性が提供され、属性はその点をよりよく定義することに役立つが、ＡＧＯＲＡ−Ｃ方法に特有なものとして各点を、位置点、交差点、経由点、およびこれら３つの何らかの組み合わせの１つとして識別することである。道路区間署名が変わる位置に沿った各点は交差点により表され、よって位置は道路ネットワーク上の経路であり、任意の道路区間署名の変更が交差点により参照される必要なく、交差点を通る。例えば、位置が関連する限りにおいて関係しない接点を含む自動車道路の区間を位置が含むならば、このような接点について交差点を含む必要はない。
【００１０】
ＡＧＯＲＡ−Ｃ符号化方法における初期段階の１つは、道路区間署名の変更が発生する位置に沿って最初と最後との交差点の間のすべての介在する交差点を決定することである。これらの点が点のテーブルへ追加され、最終的にＡＧＯＲＡ−Ｃ位置参照情報の一部を形成する。このテーブル内に、やはり所定のルールに従って少なくとも２つの経由点も識別されている。経由点は、経路計算によって（復号動作において）位置を再構築するために用いられる点であり、属性を保有する経由点を有する道路セグメントが所定の長さよりも長い場合にのみ提供される。ＡＧＯＲＡ−Ｃ標準に従う符号化処理の間、最初に識別された経由点から最後に識別された経由点までの経路を計算するために中間経由点が必要になるかについて判定がなされる。この判定は、重み付き最短パス・アルゴリズムを用いてなされる。すなわち追加の経由点が必要であると判定されたならば、これらはまた既存の交差点のテーブルに追加されるが、これは以前に識別された交差点にこのような点が一致しないような場合にだけである。この後者の場合に、既存の交差点が経由点としても識別されることを保証するために単純な属性変更が必要となる。ほとんどの場合において追加の経由点が必要にならないかもしれないが、位置が最初に特定された既存の交差点数を減らすのとは対照的に、ＡＧＯＲＡ−Ｃに適用される重み付き最短パス・アルゴリズムの影響は必要な点数を場合によっては増やすことがあることが注目されるべきである。
【００１１】
この参照アプローチは地理的情報システム内に存在する任意の位置を正確かつ反復して符号化し復号することが可能であるという点で包括的であるが、このシステムは所定の側面では過剰であり場合によっては冗長であり、多くの効率的な符号化システムが可能であると信じられる。例えば、参照方法がいかなる事前の編集作業から独立であり地図から独立であったとしても、平均的なＡＧＯＲＡ−Ｃメッセージのサイズは位置参照情報ごとに３０バイトを優に上回り、これは非常に混雑した輸送頻度とそれに関連付けられた次第に制限された帯域幅、特にこのような情報が送信されることが望まれうる移動体／無線装置に関する帯域幅との近年の風潮において禁止されないにしろ問題となりうる。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従って、本発明の目的は、
‐精度に関して著しく妥協することなくＡＧＯＲＡ−Ｃよりも効率的であり、
‐放送データについて利用可能な帯域幅に不利ではなく、
‐参照情報の作成の際に用いられる基底のデジタル地図における違い（またはそのバージョン間の違い）を説明でき、
‐ＴＭＣ位置参照システムの完全な代替になることができ、
‐デジタル地図が利用可能な任意の国の都市道路および下位レベルの道路を含む道路ネットワーク全体に対処でき、
‐定期的な保守を必要としない
位置参照情報のための効率的且つコンパクトな形式を提供することである。
【課題を解決するための手段】
【００１３】
道路ネットワーク内の連続したパスを符号化する方法であって、前記パスはデジタル地図に完全に表されるとともに、前記デジタル地図内に存在して連続に順序付けされたラインとセグメントとのうちの少なくとも一方のパス・リストとして表現可能であり、前記方法は、(i)‐前記パス・リストに最初に現われるライン又はセグメントか、若しくは前記最初のライン又はセグメントの開始ノードが人工的である場合に、実在の開始ノードを有する前記デジタル地図に現われ、場合によっては他の人工ノードを介して前記最初のライン又はセグメントに直接につながる最初のライン又はセグメントと、‐前記パス・リストに同様に現われる最も直近に識別された逸脱ライン又は逸脱セグメントとのうちの１つである開始場所を経路探索リストに記憶する工程と、(ii)前記開始場所を含み、前記開始場所の開始ノードから前記パス・リスト内の最後のライン又はセグメントの終点ノードへの前記デジタル地図内のパスを決定する工程であって、前記パスはアルゴリズムに従って決定される、工程と、(iii)そのように決定された最短パスを識別のために前記パス・リストに対して比較し、識別できない場合に、前記パス・リストの一部であり、前記デジタル地図内の交差点を表す開始ノードを有するものの、前記パス・リストに最初に現われるライン又はセグメントではない少なくとも１つの逸脱ライン又は逸脱セグメントを識別し、このような逸脱ライン又は逸脱セグメントが前記パス・リストに現われる最後のライン又はセグメントの終了ノードで終わらない場合に、前記逸脱ライン又は逸脱セグメントを用いて工程(i)を繰り返す工程と、(iv)前記パス・リスト内の最後のライン又はセグメントが既に記憶されていない場合に前記経路探索リストに記憶する工程とを有することを特徴とする方法が提供される。
【００１４】
好適には、開始場所と終了ノードとの間のパスを決定するために用いられるアルゴリズムは最短パス・アルゴリズムであるが、対応する逆アルゴリズムを用いてそのように決定されたパスを復号できるという点で可逆であるという前提で、他のアルゴリズムがまた採用されてもよい。
【００１５】
好適には、本方法は、最終の連結、変換、転置、及び結果として後述の位置参照点の有効な順序リスト又はその機械で読み取り可能な表現を生じる有効性動作のうちの少なくとも１つを行うことを含む。
【００１６】
本発明の第２側面では、コンピュータに上述の方法を実行させるためのコンピュータ・プログラム・コードを備えるコンピュータ・プログラムが提供される。さらに別の側面では、コンピュータで読み取り可能な記憶媒体に具現化されたこのようなコンピュータ・プログラムが提供される。
【００１７】
好適には、参照されることが望まれる連続したパスの始点および／または終点がデジタル地図の実在のノードに一致しない場合に、予備的有効性チェックは、連続パスの開始点及び終了点がデジタル地図内に現われる実在のノードに一致するようにこれらの点を延長し、連続したパスが実際に開始又は終了する前述の実在のノードの前後の距離を表すオフセットを記憶することを含む。
【００１８】
さらに好適には、連続パスの符号化はさらに、符号化に成功した各連続したパスをデータベースに記憶し、符号化が望まれる後続の連続したパスのそれぞれについて後続の連続したパス又はその一部がすでに符号化されているかを確立するために前記データベースへ問い合わせることによって改良される。さらに、後続の連続したパスが、それよりも大きなすでに符号化された連続パスの一部を形成する場合に、前記データベースを用いることで符号化処理に更なる効率化が実現されうる。さらにどの符号化が失敗したか、およびこのような連続したパスと同一またはその一部を形成する後続の連続パスを符号化する試行の十分に前に停止される符号化処理について、連続したパスを前記データベースに記憶することも可能でありうる。
【００１９】
本発明のその他の特徴が以下に説明され、添付の特許請求の範囲にさらに説明される。
【００２０】
位置参照情報を生成するＡＧＯＲＡ−Ｃ方法に比べて、本方法は実際に単純な最短パス・アルゴリズムを用いて位置に現われる位置参照点の必要な個数を低減しようと試みる。上述のように、ＡＧＯＲＡ−Ｃアプローチは、すでに包括的なリストにおいてどこに追加の経由点を挿入すべきかを決定するために重み付き最短パスを用いる。さらに、この重み付き最短パス・アルゴリズムは主として、より多くの幹線高速道路に並行して位置しうる、より低いクラスの道路に関する短い迂回路を避けるために採用される。
【００２１】
本発明は、非常に特定の状況に対するものとは対照的なより汎用に採用される単純なアルゴリズムが遥かに単純で、それ故（符号化時間の観点で）高速なアプローチを結果として生じることを実現する。結果として生じる位置参照情報は、連続したパスを完全に参照するために必要となる位置参照点の個数の観点で遥かにより効率的である。特に、本発明から生じる位置参照情報はセグメントおよび／またはラインの既存の完全なリストから導出されるが、本方法の出力はそのように参照される連続したパスが続いて復号動作において再構築されうる極小の点のリストを提供することであるため、それとはほとんど類似性を有しない。
【００２２】
例えば、デジタルにマッピングされた道路ネットワーク内の多くの連続したノード、セグメント、またはラインにより最初に表される数キロメートルの連続したパスは、前述のデジタル地図で表されるような道路ネットワーク上の当該パスの開始点と終了点とが実際にその全長にわたって連続パスに一致するならば、２つの位置参照点だけで表されうる。しかしながら、本発明は、好適には位置参照点間の１５ｋｍの制限の任意の強制を考慮しない。
【００２３】
本発明でさらに実現されることは、位置、交差点、および／または経由点のリストにより連続したパスを最初に表現するＡＧＯＲＡ−Ｃ方法とは対照的に、セグメントまたはラインのリストから最初に開始することによって、位置参照点へのこのようなリストのアルゴリズム的な低減の間に有用な効率性が達成されうる。
【００２４】
本発明の符号化方法を用いた実験は、典型的に利用可能な交通供給について約１８バイトの平均メッセージ・サイズが道路ネットワーク内の幅広く異なる位置または連続したパスについて一貫して達成可能であることを示した。３０バイト以上であるＡＧＯＲＡ−Ｃ位置参照メッセージに比較して、これは著しい低減を表す。
【００２５】
このような低減はネットワークを通る部分最短パスの合計または連結の観点で位置を参照することだけでなく、位置参照情報の一部を形成する各位置参照点について必要となる属性データを低減したことの結果として達成されうる。この低減は本発明に採用される物理データ形式および論理データ形式の以下の説明において明らかになるだろう。
【図面の簡単な説明】
【００２６】
【図１】符号化方法の概略図によるフローチャートを示す。
【図２】符号化方法の一部として最初に実行される有効性チェックの図式フローチャートを示す。
【図３】最短パス経路探索機能を含む符号化方法の反復部分の図式フローチャートを示す。
【図４】より詳細に最短パス経路探索機能の図式フローチャートを示す。
【図５】符号化が望まれる位置が最短パス経路探索により現在覆われているかどうかを判定することに含まれる手続きの図式フローチャートを示す。
【図６】、
【図７】、
【図８】図５に説明される手続きで場所が現在覆われていることをチェックすることにおいて生じる相異なる可能性を図的に説明する。
【図９】図９〜図１２はノードおよびセグメントを含むデジタル地図の図式表現を提供する。特に、図９は例示のネットワークを説明する。
【図１０】当該ネットワーク内で符号化が望まれる位置パスを説明する。
【図１１】当該位置を含む延長されたパスの開始ノードと終了ノードとの間の最短パスを説明する。
【図１２】当該位置を完全に参照するために必要となる位置参照点を説明する。
【図１３】図１３〜図２１は以下に説明される論理データ形式の文脈で有用である様々な図式説明を提供する。特に図１３は位置参照点（ＬＲＰ）の必要となる連続した連結を示す。
【図１４】１つのＬＲＰについてどのように方位が計算されるかを説明する図である。
【図１５】どのように方位が正の意味においてのみ変わりうるかを示す図である。
【図１６】どのように「次の点への距離」属性がＬＲＰについて決定されうるかを示し、当該属性が関連するＬＲＰはどれかをさらに示す図である。
【図１７】オフセットの使用を説明する図である。
【図１８】ＬＲＰに属性が提供される方法を示す図である。
【図１９】、
【図２０】位置参照情報の決定の間に回避されるノードを説明する図である。
【図２１】どのようにＬＲＰについての方位値が円の３２個に分離したセクタの１つに収まるかを説明する図である。
【発明を実施するための形態】
【００２７】
本発明の特定の実施形態が以下に添付の図面をしつつ、例示の方法により説明される。
【００２８】
本発明の以下の説明はセグメントの観点で提供されるが、本発明は道路ネットワークを通る連続したパスをともに表すラインやラインとセグメントとの組み合わせに等しく適用されうることが理解されるだろう。
【００２９】
まず図１を参照して、上述のように、本発明に従って以前に符号化が成功した完全な位置参照情報をデータベースに記憶することが可能であり、従って図１のステップ１０で、符号化が望まれる位置がすでに符号化されているかどうかを確立するためにこのようなデータベースがチェックされる。すでに符号化されているならば、更なる処理はなされずに、以前に符号化された位置がデータベースから読み出されうる。
【００３０】
データベース内に位置が存在しないならば、後述される所定の基準を位置が満たすかどうかを判定するために位置とそれを構成するセグメントとに関して有効性チェック１４が行われ、位置が有効であることを前提とすると、位置参照情報がステップ１６で作成される。有効性チェックまたはこの特定の位置についての位置参照情報の作成が失敗したならば、ステップ１８に示されるように、このような失敗も前述のデータベースに記憶されうる。
【００３１】
処理の最終ステップとして、１６で作成された位置参照情報がさらにステップ２０で有効性がチェックされる。ステップ２２は、１つの表現から別の表現への変換を表す点で例示的である。最終的に、（１つ以上の中間形式を含みうる）変換処理は、後述されるような物理データ形式で規定されるような、無線で送信可能であり機械で読み取り可能な２進数表現を結果として生じる。この形式は、エンコーダとデコーダとの間で情報を転送する際に有用なＸＭＬや事実上任意のその他のマークアップ表現または機械で読み取り可能な表現のような別の形式を取りうる。本発明は説明される特定の形式に制限されるとみなされるべきではない。その後、位置の完全で正確で正しい表現がステップ２４に示されるように前述のデータベースに記憶される。
【００３２】
図２を参照して、図１の１４で説明される「位置チェック」の有効性チェックがさらに説明される。すでに符号化された位置のデータベースに記憶されていないすべての位置は更なる処理の前に有効性についてチェックされる必要がある。最初のステップとして、３０で、連結性チェックが実行される。連結性のチェックは、連結していない２つ以上の相異なる部分に、入力された位置が分割されていないことを保証する。連結した部分のそれぞれは個別に処理される必要があり、それ自体で符号化される１つの位置を表す。１つの連結した部分のみで位置が構成される場合にこのチェックは通過される。
【００３３】
ステップ３２で、機能的道路クラス・チェックが実行される。このチェックは、最初の位置の一部を形成するセグメントのすべてが基底のデジタル地図において定義される最低機能的道路クラスを満たすことを保証する。機能的道路クラス（ＦＲＣ）は地図データ内のラインまたはセグメントの一般的な属性であり、特定のタイプの道路の相対的な重要度を示す属性である。０〜７の機能的道路クラスだけを含むことの任意の決定がなされている。なぜなら、これは任意のナビゲート不能な道路、交通イベントがほとんど生じないだろう非常に低いカテゴリの道路を効率的に排除するからである。
【００３４】
１つの実施形態では、エンコーダは位置がターン制限により影響を受けるかどうかをチェックすることが可能でありうる。可能であるならば、３４で示されるように途中にターン制限が存在するかどうかを位置は段階的に検査される。セグメントからセグメントへのすべてのターンが有効である必要がある。有効でないならば、３９で例外がスローされ、位置は符号化されないだろう。ターン制限チェックは使用可能である必要がないことを言及する価値があり、本方法は膨大な大多数の位置について位置の符号化に成功し続けるだろう。しかしながら、説明されたようなターン制限チェックを使用可能にすることは、符号化の成功を保証するための付加的な手段として単に動作する。
【００３５】
位置の有効性チェックの最終ステップとして、位置の最初のセグメントの開始ノードおよび位置の最後のセグメントの終了ノードが実在ノードであるか、それとは反対に人工的または回避可能なノードであるかに関して判定される。更に説明するために、ほとんどのインスタンスにおけるセグメントは人工的構造であり、地図ベンダによって任意に定義される傾向がある。それにもかかわらず、これらは、特定の道路部分に沿った何らかの任意の点で交通イベントが始まる現実世界の道路部分での交通イベントを表現することに関してラインと比べて遥かに優れた分解能を提供する。自動車道路または主要高速道路の文脈において、かなりの距離（例えば１５ｋｍ以上）離れて位置する（実在ノードで表される）２つの交差点の間の何らかの点で交通イベントが生じてもよく、従って交通状況が存在する正確な点は実在ノードよりも人工ノードの近くに遥かになりやすい。しかしながら、デコーダの地図にそのような人工ノードを有する確率は極めて小さく、よって、これらの人工ノードは回避されるべきである。これは、位置をその開始および終了において基底のデジタル地図に現れる実在ノードへ一意に延長することによってなされ、オフセット距離値はこのようなノードへの属性として提供され、その結果として交通（またはその他の）イベントの正確な場所、すなわち符号化される位置の正しい開始が正しく参照されうる。従って、位置を完全に覆うパスとオフセットとを用いて位置が正確に表現されうる。位置を覆い且つより長いパスを有することで、位置参照パスを再使用して、オフセットだけを更新することが可能になりえ、これは帯域幅および時間を節約するだろう。
【００３６】
従って、開始ノードが人工的でないならば、延長は存在しないだろう。それ以外の場合に、人工的な開始ノードを有する最初のセグメントへの内向きセグメントがステップ３６で新たな開始セグメントとして選択される。新たな開始セグメントの開始ノードも人工的または回避可能であるならば、適切な開始ノードが識別されるまで手続きが繰り返される。
【００３７】
２番目のステップ３８は位置の終了を延長しようとする。これは、最後のセグメントの終了ノードが評価されることを除いて開始セグメントに対するものと全く同じ方法で行われ、外向き道路セグメントに対して探索がなされる。これら２つのステップのいずれかにおいて人工ノードを延長できず且つ実在ノードが見つからなかった場合に、復号側で一致することを期待して人工ノードを用いて本方法で続けることが可能である。従って、本方法はなおも有効であるが、信頼性レベルは低くなる。
【００３８】
図３を参照して、図１の位置参照情報作成ステップ１６の説明が提供される。上述の有効性処理の後に、一連の有効なセグメントが提供され、これは後述の論理データ形式で定義されるオブジェクトのツリーとして位置参照情報へ変換されることが望まれる。
【００３９】
本発明に従う位置参照情報の生成における最初のステップ４０は、経路探索が開始されるべき最初のセグメントを識別することである。
【００４０】
その後に、ステップ４２で最初のセグメントと中間セグメントまたは逸脱セグメントとの何れかを用いて経路探索が実行される。経路探索は位置の最初の（または中間の）セグメントと最後のセグメントとの間の最短パス経路の計算である。経路探索の詳細は図４を参照してより詳細に説明される。
【００４１】
経路探索は開始セグメントと宛先セグメントとの間の最短パスを計算する。この計算は反復して行われ、ステップ５０での初期化の後に、ステップ５２、５４、５６、５８を含むメイン・ループが最短パスを計算するだろう。最短経路パスは（図５を参照して以下により詳細に説明される）ステップ５６で反復ごとにチェックされ、位置がなおも、計算された最短パス木の一部であるかどうかを確立する。もはや位置が最短パス木により覆われないならば、経路計算は停止し、ステップ６０において部分経路（いままで覆われた位置の部分）と、経路探索を一意にし、その後に続けることができる中間位置参照点として用いられるべきセグメントとを返す。この中間セグメントは図３におけるステップ４４で識別され、１つ以上の更なる経路探索が行われる新たな開始セグメントとして経路探索アルゴリズムへ返される。
【００４２】
理想的に経路探索は上述のように延長されていない位置の部分に焦点をあてるだろう。なぜなら、このパスからの逸脱は起こりえないために位置の延長部分は経路計算に影響を有しないからである。拡張は後のステップで位置参照情報へ追加されてもよい。
【００４３】
ステップ５０で、経路探索が初期化され、すべてのデータ構造がリセットされる。ステップ５２で、判定点５３において、経路探索が続けられるべきか停止されうるかに関してチェックされる。探索は以下の場合に停止されうる。
‐開始セグメントと宛先セグメントとの間の最短パスが見つかった場合。この場合に６２で示されるように最短パス経路が生成されうる。
‐これ以上処理するセグメントが存在しない場合。これは６４で示されるように、開始セグメントと宛先セグメントとの間に経路が存在しないことを意味する。
‐中間セグメントが識別された場合。
すべての実際の場合において、経路は常に存在するはすである。なぜなら、パスそのものは有効であり、このような経路を形成するからである。しかし、このチェックはすべての経路探索アルゴリズムに対して強制的である。探索が完了しない場合に、ステップ５４で、「次のラインを取得」手続きは、しばしば「オープン・リスト」と呼ばれる２つの関連するノード間の最短パスの一部を形成するすべてのラインのリストから最良のラインをフェッチする。最短パス・アルゴリズムの結果として、ラインへの最短パスが、ステップ５４で読み出されたオープン・リスト内に存在するものから位置の一部を形成するラインの入口で終了する。従って、「位置被覆チェック」ステップ５６は図５を参照して更に詳細に概要が説明されるが、簡潔にはこのステップは経路計算の間にこの条件が満たされるかどうかをチェックする。経路計算の間のチェックは、すべての固定セグメント（セグメントへの最短パスが最終的に決定された場合にセグメントは固定される）が位置の一部をも形成するかどうかが調査されるだろうことを意味する。現在検討中のセグメントが、参照されることが望まれる位置の一部を形成する場合に、位置の開始部分が現在の最短パス木に完全に含まれることを確立するためのチェックが行われる。これは、最後の位置セグメントへの計算された最短パスが位置そのものである必要があることを意味する。任意の逸脱に遭遇した場合に、経路計算は停止され、ステップ６０で部分経路が生成され、図３に説明される経路探索処理へ戻される。この図のステップ４４では、基底のデジタル地図において中間セグメントが識別され、この中間セグメントを開始点として用いて経路探索が再開される。
【００４４】
最短パス計算において現れた逸脱の特性に依存して、中間セグメントを正しく特定して参照するための様々な相異なる可能性が存在し、これらすべては図５〜図８を参照して説明される。
【００４５】
こうして今までに決定された最短パスの一致をチェックするために、経路探索の間に位置上に発見された最後のセグメントが（図５において７０で示される）経路探索リストに記憶され、その結果として、最後に記憶されたセグメントに連続した後続セグメントだけが、または少なくとも終了ノードと開始ノードとがそれぞれ一致するものだけを検討できるため、どのセグメントが次に来るべきかを容易に決定できる。最短パスに含まれるこれらのセグメントを最短パス経路探索が参照情報から効率的に排除すること、すなわちそれらが参照情報の一部を形成する必要がないことは位置参照情報長の経済性についての基本である。従って、判定点７２、７４において、最短パス経路リストの一部を形成する最も直近のセグメントが、符号化される位置に存在または一致し、
‐最短パス上で次に予想されるセグメント、および
‐前述の最短パス上で直前のセグメント
を参照するために最短パス・リストで理想的に用いられるポインタの観点で最短パスが関連する限りにおいて正しく参照されることのチェックが行われる。位置パス上にもあるこれらのポインタ参照セグメント両方を前提とすると、位置は最短パスにより正確に覆われるとみなされ、経路探索を継続できる。
【００４６】
しかし当然のことながら、より短い逸脱が不可避的に発見され、すべての取り得る逸脱の種類が図５のフローチャートの様々な分岐および図６〜図８の簡略化された線図で網羅される。最も単純には、位置パス上のセグメントが現在分析されているが、このセグメントが最短経路リストの関連する限りにおいて次に予想されるセグメントと食い違う場合に逸脱が発見される。最短経路リストの次に予測されるセグメントが位置パス・リストの次のセグメントに一致するが、最短パス・リストのこのセグメントへの先行ポインタが位置を指し示さない場合にも逸脱が発見される。このことは、先行ポインタが位置に関して発見された最後のポインタに等しくなければならないことを意味する。どちらの場合とも、適切な中間物を識別する必要がある。以下のステップはこの中間物を決定し、特殊な場合に２つの中間物を加える必要がある。適切な中間物の発見に関する主な焦点は交差点の一部である開始ノードを有するセグメントを用いることである。
【００４７】
まず図５、図６を参照して、７６で示されるように、すべての場合において逸脱の開始を発見する必要がある。図６は最短経路リストの一部として記憶され、また当初の位置パス・リストの一部を形成する最後のセグメントの前で逸脱が始まる最も単純な場合を説明する。説明される位置パス全体はセグメントＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、およびＧにより表される。そして、今まで確実に位置に一致すると判定された最短パスは図で太字にされたセグメントＡ、Ｄにより表される。最短パス探索の進行として、特に開始セグメントＡとセグメントＥの終了ノードとの間として、より短い逸脱Ｈが発見される。（最も一般的な場合であるだろう）このような場合に、位置上に現われ、逸脱が始まる開始ノードを有するセグメントを発見することが理想的には望まれる。このような場合に、セグメントＣが適切な中間物として含まれることが要求される。なぜなら、これは復号処理で実行される任意の最短パス・アルゴリズムで位置が追従されることを保証するからである。この探索はこの参照を満たすセグメントについての位置パス・リストを通じて再帰され、これは図５の７８、７９で参照される。図６に示される単純なパスの観点では起こりえないが、このようなセグメントが発見されない場合がある。この場合に、最短経路リストに最後に記憶されたセグメントは８０で説明されるように中間物として用いられうる。なぜなら、最後に記憶されたセグメントを自身の開始として用いる最短パス関数はその前から始まる如何なる逸脱も決して識別しないからである。
【００４８】
代替の実施形態では、図７で強調されるように、経路探索リストに記憶された最後のセグメントＥの終了の後に逸脱が始まる。この場合に、ＡからＥへの最短パスは既知であり、ＡからＥまでのセグメントだけが記憶されている。セグメントＡからセグメントＦの終了ノードまでの最短パスは実際にはＡとＩとだけによって参照される。ＩはＦを含む位置からの逸脱であり、最後に記憶されたセグメントＥの終了の後に発生する。この場合に、セグメントＦへの先行ポインタが実際には位置上のセグメント、この場合にＥを指し示すことを前提すると、図５の８２で示されるように、中間物はこのセグメントＦから生成されうる。このチェックは８４で示される。
【００４９】
セグメントＫがセグメントＪを参照する場合のような、最短経路探索の一部として記憶される最後のセグメントの後の発生する逸脱が位置の一部を形成しないセグメントを実際に参照する図８の例外的な場合では、最初のステップとして、（前述された８２のように）第１中間セグメントＥが生成され、第２中間セグメントＤも記憶される。なぜなら、これは位置パス上で発生し、より短いパス・セグメントＪが始まる交差点から始まる最後のセグメントだからである。これらのステップは図５の８６、８８として総括的に示され、記憶された位置参照情報は最終的にセグメントＪ、Ｋの両方を回避しなければならないため、これらのステップは必須である。
【００５０】
最後に図３を参照して、位置パス・リスト全体の処理が完了すると、識別されたすべての部分最短パスがステップ４６で結合される。位置の被覆は、最初の経路計算が中間セグメントを決定した場合にいくつかの部分経路で構成されうる。この中間セグメントは、経路探索が位置の完全な被覆となるように導くために位置参照情報の付加情報として機能する。経路探索が位置の終了に到達すると、すべての計算された部分経路が結合されて、位置を完全に覆うパスを形成する。１つの実施形態ではこのステップはまた、図２に説明されたステップ３６、３８で計算されたような位置の開始および終了における拡張を付加しうる。最初の位置参照点および最後の位置参照点が調整され、当初位置の相対位置を表す新たなオフセットが計算される。
【００５１】
本発明を用いて位置を符号化する方法のよりよい理解を提供するために、図９〜１２を参照して更なる特定の例が提供される。
【００５２】
エンコーダの地図が図９に示され、１５個のノードと２３個のライン（双方向のラインは２度数える）とで構成される。ノードは１から１５まで番号付けされる。必要なライン属性が形式＜ＦＲＣ＞、＜ＦＯＷ＞、＜メートル単位の長さ＞を用いてすべてのラインのそばに示される。ＦＲＣは「機能的道路クラス」の略語であり、ＦＯＷは「道路種別」の略語であり、これらの両方は以下により詳細に説明される。矢印は各ラインについての取り得る運転方向を示す。
【００５３】
図１０において、符号化される位置が太線で示される。位置はノード(3)から始まり、続いてノード(5)、(7)、(10)、(11)、(13)、(14)を通り、ノード(15)で終わる。エンコーダの地図におけるその全長は６８５メートルである。符号化の間に用いられるラインの順序リストとマップとはエンコーダへの入力としての機能を果たす。
【００５４】
符号化：
符号化処理の最初のステップで、位置はまず有効性についてチェックされる。位置は連結され運転可能であり、位置に沿った機能的道路クラスは０と７との間であるため、この位置は有効である。ターン制限はマップ・データに含まれず、従ってエンコーダはこのチェックを無視しうる。
【００５５】
エンコーダの２番目のステップは、ある所定のデータ形式ルールに従って位置の開始ノードおよび終了ノードが実在ノードであるかをチェックすることである。終了ノード(15)は１つの内向きラインのみを有するので有効である。また、開始ノード(3)は２つの付帯するラインを有するが、ここでは１つは外向きラインであり、１つは内向きラインである。従って、このノードは有効でなく、エンコーダは位置の外側の実在ノードを検索する。エンコーダは実在ノードとしてノード(1)を発見し、位置を一意に拡張するだろう。ノード(1)は位置参照情報のための新たな開始ノードとして選択され、１５０メートルの正オフセットが存在するだろう。位置参照パスの全長は結果として８３５メートルになる。
【００５６】
エンコーダの３番目のステップは位置の開始ライン（この場合に、ノード(1)とノード(3)との間のラインである。しかしながら、一般の使用法で、最短パスは延長なしに計算されうる。）と終了ライン（ノード(14)とノード(15)との間のライン）との間の最短パスの計算を続いて行う。結果の最短パスは図１１に太線で概要が説明される。最短パスは７２５メートルの長さを有する。
【００５７】
符号化処理の次（４番目）のステップは、計算された最短パスにより位置が覆われるかどうかをチェックすることである。この場合は覆われておらず、ノード(10)の後に逸脱が存在することが判定されるだろう。
【００５８】
上述の原理に従って、エンコーダはノード(10)からノード(11)へのラインが新たな中間位置参照点になると決定するだろう。経路探索の間にノード(10)をスキップできないためノード(10)は実在ノードであり、このラインへの最短経路は位置の対応する部分を完全に覆う。この最初の最短パス計算の後に覆われる位置の長さは５６１メートルである。
【００５９】
次の符号化ステップは位置の残り部分（ノード(10)からノード(11)、(13)、(14)を経由してノード(15)まで）について最短パスを決定するために経路計算を準備する。従って、最短パス計算は(10)から(11)へのラインで始まり、(14)から(15)へのラインで終わるだろう。
【００６０】
エンコーダは上述のステップ３へ戻り、(10)と(15)との間の最短パス（長さ：２７４メートル）を決定し、上述のステップ４は、現段階で計算された最短パスにより位置が完全に覆われたことを返す。
【００６１】
次のステップとして、位置参照パスは２つの最短パスで構成され、位置参照点の順序リストがここで形成されるだろう。図１２は位置参照点として選択されたラインが太く示される。１番目の位置参照点はノード(1)からノード(3)へのラインを指し示し、位置参照パスの開始を示す。２番目の位置参照点はノード(10)からノード(11)へのラインを指し示し、このラインは位置からの逸脱を回避するために必要であった。最後の位置参照点はノード(14)からノード(15)へのラインを指し示し、位置参照パスの終了を示す。
【００６２】
最後から２番目のステップは位置参照情報の有効性のチェックである。２つの連続した位置参照点間のすべての長さは最大距離よりも短いため、位置参照情報は有効であると確認される。
【００６３】
最後のステップはＬＲＰの順序リストを２進数位置参照情報へ変換することであり、出願人により規定された論理データ形式と物理データ形式との両方の以下の説明はこれがどのように実現されるかの理解を助けるだろう。特定の形式の詳細を提供する以下の詳細な説明は単に例として提供され、当業者は他の形式を取りうることを理解するだろうことが強調されるべきである。
【００６４】
論理データ形式および物理データ形式の仕様
以下の表は本明細書において位置参照情報の文脈で用いられる一般用語および略語を説明する。
【００６５】
【００６６】
１．データ形式
位置参照情報はデジタル地図の指定された部分または一連の地理的場所の表現である。この表現のために、位置参照点（ＬＲＰ、１．１．１参照）のモデルを用いる。
【００６７】
ライン位置についての位置参照情報は少なくとも２つのＬＲＰを含むがＬＲＰの最大数は規定されない。位置参照パスはＬＲＰにより表現されるデジタル地図内のパスであり、ＬＲＰの連続したペアのそれぞれの間の最短パス計算により発見されうる。
【００６８】
１．１ 論理データ形式の仕様
論理データ形式はＭａｐＬｏｃ（商標）標準に従って位置参照情報についての論理モデルを表現する。
【００６９】
１．１．１．位置参照点（ＬＲＰ）
位置参照情報の基盤は一連の位置参照点（ＬＲＰ）である。このようなＬＲＰはＷＧＳ８４の経度値および緯度値で特定された座標ペアと、付加的ないくつかの属性とを含む。
【００７０】
座標ペア（１．１．３．１参照）は地図／ネットワーク内の地理的位置を表し、ＬＲＰについて必須である。座標ペアはネットワーク内の「実在（real）」ノードに属する。
【００７１】
属性（セクション１．１．３．２〜１．１．３．６参照）は、座標ペアにより表現されるノードにラインが付帯する、ネットワーク内のラインの値を表す。この文脈では、ノードに関して内向きラインと外向きラインとのどちらを属性が指すかは規定されない。これはセクション１．２で特定される。
【００７２】
１．１．２．ＬＲＰのトポロジー連結
図１３を参照して、位置参照点はトポロジーの順序で、すなわち連続したＬＲＰの「次の点（next point）」関係で記憶されるものとする。この順序の最後の点はこの関係における次の点を有しないだろう。
【００７３】
図１３はこの関係の例を示す。ＬＲＰはＡ１、Ｂ１、およびＣ１によって示され、黒線矢印は位置参照パスにおけるＡ１からＣ１への点の順序を示す。この例では、ＬＲＰ Ａ１は次の点としてＢ１を有し、Ｂ１は次の点としてＣ１を有し、Ｃ１は次の点を有しないだろう。
【００７４】
１．１．３．ＬＲＰのコンポーネント
このセクションは位置参照点のコンポーネントを説明する。
【００７５】
１．１．３．１ 座標ペア
座標ペアはＷＧＳ８４の経度（ｌｏｎ）の値と緯度（ｌａｔ）の値とのペアを意味する。この座標ペアはデジタル地図における幾何的な点を特定する。ｌｏｎ値およびｌａｔ値はデカミクロンの分解能（１０-5、すなわち小数点５位）で記憶される。
【００７６】
略語：ＣＯＯＲＤ タイプ：（浮動小数，浮動小数）
【００７７】
１．１．３．２ 機能的道路クラス
機能的道路クラス（ＦＲＣ）は道路の重要度に基づく道路分類である。ＦＲＣ属性の取りうる値が表Ａ２に示される。これら８個の位置参照値よりも多くのＦＲＣ値が定義されるならば、適切なマッピングが行われる必要があるか、または重要性の低いクラスが無視される必要がある。
【００７８】
【００７９】
略語：ＦＲＣ タイプ：整数
【００８０】
１．１．３．３ 道路種別（Form of way）
道路種別（ＦＯＷ）は物理的道路タイプを表現する。ＦＯＷ属性の取りうる値が表Ａ３に示される。
【００８１】
【００８２】
略語：ＦＯＷ タイプ：整数
【００８３】
１．１．３．４ 方位
方位（ＢＥＡＲ）は、真北と、ＬＲＰの座標およびＬＲＰ属性により定義されるラインに沿ってＢＥＡＲＤＩＳＴである座標により定義されるラインとの間の角度を表現する。ライン長がＢＥＡＲＤＩＳＴよりも短いならば、（ＢＥＡＲＤＩＳＴに関わらず）ラインの反対側の点が使用される。方位は角度単位で測定され、（北から時計回りに測定され）常に正である。パラメータであるＢＥＡＲＤＩＳＴは表Ａ４に定義される。
【００８４】
略語：ＢＥＡＲ タイプ：整数
【００８５】
【００８６】
図１４は方位計算のための第２点がどのように決定されるかを示す。この図はＢＥＡＲＤＩＳＴよりも長いＡ２からＢ２へのラインを示す。このラインの斜線部分はＢＥＡＲＤＩＳＴメートルちょうどの長さであり、その結果としてＢ′で印が付けられた点はＡ２からＢ２へのラインに沿って移動して、Ａ２からＢＥＡＲＤＩＳＴメートル離れている。Ａ２からＢ′への直線が方位値の計算のために以下で検討される。ラインの反対側のノード（この場合、これはＢ２であるだろう）が用いられる場合に計算されるだろう角度はこれとは異なる。
【００８７】
図１５は方位値を計算する２つの例を示す。１つはＡ３からＢ３までであり、１つはＡ３からＣ３までである２つのラインが存在する。両方のラインについて、弧は北に対する角度を示す。
【００８８】
１．１．３．５ 次のＬＲＰへの距離
このＤＮＰフィールドはＬＲＰのトポロジー連結における次のＬＲＰへの距離を表現する。距離はメートル単位で測定され、位置参照パスに沿って計算される。最後のＬＲＰは距離値としてゼロを有するだろう。
【００８９】
略語：ＤＮＰ タイプ：整数
【００９０】
図１６は距離の計算と割り当てとの例を示す。３つのＬＲＰがＡ４からＢ４を越えてＣ４まで一列に存在する。従って、位置参照パスに沿ったＡ４とＢ４との距離はＡ４に割り当てられるだろう。ＬＲＰ Ｂ４はＢ４とＣ４との間の距離を保持し、ＬＲＰ Ｃ４は距離値としてゼロを有するだろう。
【００９１】
１．１．３．６ 次のＬＲＰへの最低ＦＲＣ
最低ＦＲＣ（ＬＦＲＣＮＰ）は２つの連続したＬＲＰの間の位置参照パスに現れる最低のＦＲＣ値である。最高のＦＲＣ値は０であり、取りうる最低のＦＲＣ値は７の値を有する。
【００９２】
略語：ＬＦＲＣＮＰ タイプ：整数
【００９３】
１．１．４．オフセット
オフセットは位置参照パスをその開始および終了において縮小するために用いられる。位置参照パスに沿った新たな場所は、位置の実際の開始および実際の終了を示す。
【００９４】
１．１．４．１ 正オフセット
正オフセット（ＰＯＦＦ）は位置参照情報の開始点と所望の位置の開始点との位置参照パスに沿った距離である。値はメートル単位で測定される。図１７は正オフセットおよび負オフセットの計算の例を示す。線は位置参照パスを示し、ハッチングは所望の位置を示す。
【００９５】
略語：ＰＯＦＦ タイプ：整数
【００９６】
１．１．４．２ 負オフセット
負オフセット（ＮＯＦＦ）は所望の位置の終了点と位置参照情報の終了点との位置参照パスに沿った距離である。値はメートル単位で測定される（図１７を再び参照）。
【００９７】
略語：ＮＯＦＦ タイプ：整数
【００９８】
１．２ 関連属性‐ＬＲＰ
すべての属性はＬＲＰにリンクされる。（最後のＬＲＰを除く）すべてのＬＲＰについて、属性はＬＲＰ座標におけるノードの外向きラインを表す。最後のＬＲＰの属性はＬＲＰ座標におけるノードの内向きを対象とする。
【００９９】
図１８はＬＲＰと属性との間の関連の例を示す。ラインは位置参照パスを示し、ノードＡ５、Ｂ５、およびＣ５がＬＲＰである。開始ノードおよび終了ノードがＬＲＰでないライン（列の３番目のライン）も存在することに留意されたい。このラインは、ＬＲＰ Ｂ５とＬＲＰ Ｃ５との間の最短パスにより覆われるため、参照される必要はない。
【０１００】
ＬＲＰ Ａ５およびＬＲＰ Ｂ５は外向きラインを対象とし、最後のＬＲＰ Ｃ５は内向きラインを対象とする。
【０１０１】
１．３ データ形式のルール
これらのルールはこの仕様に従う位置参照情報についての追加の規則を表現する。これらのルールは符号化処理および復号処理を単純化し、結果の精度を高めるために用いられる。
【０１０２】
ルール１ ２つの位置参照点の間の最大距離は１５ｋｍを超えないものとする。距離は位置参照パスに沿って測定される。位置参照情報についてこの条件が満たされないならば、十分な数の追加のＬＲＰが挿入されるものとする。
【０１０３】
２つの連続した位置参照点の間の最大距離は最短パス計算を速めるために制限される。なぜなら、経路アルゴリズムがネットワーク全体を考慮に入れなければならない場合に、１つの長い経路よりも複数の短い経路の方が速く計算されうるからである。本制限はまた、許容精度でコンパクトな２進数形式を形成する機会を提供する。
【０１０４】
ルール２ すべての長さは整数値である。浮動小数値が利用可能ならば、整数表現を得るためにこれらの値を丸める。
【０１０５】
様々な地図は長さの値を様々な形式で且つ様々な精度で記憶するかも知れず、すべてに対する統一の基盤は整数値を使用することである。また、浮動小数値を用いるよりも２進数形式の整数値を送信する方がコンパクトである。
【０１０６】
ルール３ ２つのＬＲＰが必須であり、中間ＬＲＰの個数は制限されない。
【０１０７】
ライン位置参照情報は位置の開始および終了を示す少なくとも２つの位置参照点を常に有していなければならない。（異なる地図に関して）デコーダに問題が発生するかもしれない危機的状況をエンコーダが検出するならば、位置参照情報は追加の中間ＬＲＰで強化されうる。
【０１０８】
ルール４ ＬＲＰの座標は実在ネットワーク・ノード上に選択されるものとする。
【０１０９】
これらの実在ネットワーク・ノードは現実世界の接点であるべきで、これらの接点はライン上のどこかの場所よりも高い確率で異なる地図で発見されうることが期待される。さらに、経路検索の間に容易にスキップされうるノードは回避されるものとする。これらの回避可能なノードにおいて、経路から逸脱する可能性はない。
【０１１０】
１つの内向きラインおよび１つの外向きラインのみを有するノードは、これらのノードが接点に関連せず（図１９参照）、経路探索の間にスキップされうるために、回避されるものとする。２つの内向きラインおよび２つの外向きラインを有し、２つの隣接ノードのみが存在するノードは同様に回避されるものとする（図２０参照）。
【０１１１】
これらのノードの１つがＬＲＰについて選択されると、このＬＲＰは適切なノードを見つけるために位置参照パスに沿ってシフトされるべきである。これは、所望のパスを逸脱することなくこのような回避可能なノードを経路計算がスキップするために行われうる。
【０１１２】
位置の開始または終了が回避可能なノード上に配置されるならば、エンコーダは位置を一意に拡張すべきであり、位置の外側の適切なノードを見つけるべきである。この拡張は位置へ入り込むべきではない。なぜなら、これは位置を縮小するだろうからである。
【０１１３】
１．３．１．データ形式ルールの概要
以下の表Ａ５はデータ形式ルールを要約する。
【０１１４】
【０１１５】
１．４ ２進数表現
物理データ形式は上述の論理データ形式についてのバイト指向のストリーム形式を表現する。これはセクション１．１の論理データ形式において表現されたコンポーネントを用いる。
【０１１６】
１．４．１．データ・タイプ
物理データ形式は以下のデータ・タイプを用いる。表Ａ６はすべての利用可能なデータ・タイプの概要を与え、名前、タイプ、および各データ・タイプの指定サイズを特定する。以下のセクションでは、データ・タイプ名は各データ・コンポーネントについてサイズおよびタイプを示すために用いられる。
【０１１７】
【０１１８】
負の整数値が２つのコンポーネント形式で記憶される。
【０１１９】
１．４．２．座標（ＣＯＯＲＤ）
地図内の各点はＷＧＳ８４座標で表された「経度」（ｌｏｎ）と「緯度」（ｌａｔ）との座標ペアで構成される。北方向および東方向は（経度、緯度それぞれ）正の値で表される。ｌｏｔ値およびｌａｔ値はデカミクロンの分解能（１０-5、小数点第５位）で記憶される。
【０１２０】
座標値は整数値として送信されるだろう。これらの値は２４ビット整数表現を算出する式Ｅ１を用いて生成されるだろう。分解能パラメータは２４に設定される。この変換は最大で約２．４メートルの誤差を生じる。逆変換は式Ｅ２で表現される。両方の式は、負の値について−１、正の値について１、その他について０である符号関数を利用する。
【０１２１】
【０１２２】
【０１２３】
物理形式は絶対座標形式と相対座標形式とを利用する。絶対形式は地理的場所の指定された値を表し、相対値は先行する座標に対するオフセット座標である。
【０１２４】
１．４．２．１ 絶対形式
絶対形式は２４ビット分解能における地理的場所を表現する。表Ａ７は絶対形式に用いられるデータ・タイプを示す。
【０１２５】
【０１２６】
１．４．２．２ 相対形式
相対形式は２つの連続した座標間の差を表現するために用いられる。差は式Ｅ３に示されるように各値（ｌｏｎ／ｌａｔ）別々に計算される。現在の値および前の値は緯度値（経度値）を角度単位で表す。これら２つの値の差は整数値へ変化させるために１０００００倍される。
【０１２７】
【０１２８】
表Ａ８は１６ビット表現を用いて取りうる最大距離を示す。この図はｌｏｎ＝５°、ｌａｔ＝５２°（オランダ内の場所）における固定の座標について計算される。
【０１２９】
【０１３０】
表Ａ９は２バイト・オフセットについてのデータ・タイプを示す。
【０１３１】
【０１３２】
１．４．３．属性値
属性の２進数形式がこのセクションで続く。
【０１３３】
１．４．３．１ 機能的道路クラス（ＦＲＣ）
機能的道路クラス（ＦＲＣ）は論理形式で説明されたように８個の相異なる値を保持しうる。これらの８個の値は表Ａ１０で示される３ビットとマッピングとにより表される。
【０１３４】
【０１３５】
１．４．３．２ 道路種別（ＦＯＷ）
道路種別（ＦＯＷ）は論理形式において説明されたように８個の相異なる値を保持しうる。これらの８個の値は表Ａ１１で示される３ビットとマッピングとにより表される。
【０１３６】
【０１３７】
１．４．３．３ 方位（ＢＥＡＲ）
方位は論理形式において説明されたように道路と真北との間の角度を表現する。物理データ形式は３２個のセクタを定義し、各セクタは円のうち１１．２５°をカバーする。これらの３２個のセクタは５ビットで表される。表Ａ１２は方位属性についてのデータ・タイプを示し、表Ａ１３はセクタから具体的な値へのマッピングを示す。
【０１３８】
【０１３９】
【０１４０】
式Ｅ４は方位値の計算の概要を説明し、図２１はセクタの図示による概要を提供する。
【０１４１】
【０１４２】
１．４．３．４ 次のＬＲＰへの距離（ＤＮＰ）
ＤＮＰ属性は論理形式において説明されたように位置参照パスに沿った２つの連続したＬＲＰ間の距離を測定する。
【０１４３】
物理データ形式は８ビット表現を定義し、表Ａ１４はＤＮＰについて用いられるデータ・タイプを示す。この表現は２５５個の間隔を定義し、データ形式ルールのルール１（２つの連続したＬＲＰ間の最大長は１５０００ｍに制限される）と組み合わせて各間隔は５８．６メートルの長さを有するだろう。
【０１４４】
【０１４５】
式Ｅ５はどのようにＤＮＰ値を計算できるかを示す。
【０１４６】
【０１４７】
１．４．３．５ 次の点への最低ＦＲＣ（ＬＦＲＣＮＰ）
次の点への最低ＦＲＣは次のＬＲＰへの位置参照パスに用いられる最低の機能的道路クラスを示す。この情報は復号の間にスキャンされる必要のある道路クラスの個数を制限するために用いられうる。データ・タイプの定義については表Ａ１５を参照されたい。
【０１４８】
【０１４９】
１．４．４．位置参照情報ヘッダ
位置参照情報ヘッダは参照情報に関する一般的な情報を含む。
【０１５０】
１．４．４．１ バーション（ＶＥＲ）
バーションは位置参照情報についての複数の物理的なデータ・フォーマットを区別するために用いられる。バージョン番号は３ビットで表され、データ・タイプは表Ａ１６に示される。
【０１５１】
【０１５２】
１．４．４．２ 属性フラグ（ＡＦ）
属性フラグは各ＬＲＰへ付加された属性が存在するか否かを示す。属性が付加されていない場合にＡＦ値は０となり、従って位置参照情報は座標だけで構成される。それ以外の場合、値は１となり各ＬＲＰへ属性が付加されることを示す。ＡＦについてのデータ・タイプは表Ａ１７、Ａ１８に示される。
【０１５３】
【０１５４】
【０１５５】
１．４．４．３ 領域フラグ（ＡｒＦ）
領域フラグは位置参照情報が領域を記載するか否かを示す。このフラグが設定されるならば、位置は結合しているものとし、以下の表Ａ１９、Ａ２０に見られるように領域を表現する。
【０１５６】
【０１５７】
【０１５８】
１．４．５．オフセット
オフセットはネットワーク内のノードへ結び付けられたものよりも正確に位置の開始および終了を位置付けるために用いられる。論理形式は、１つは位置の開始において、もう１つは位置の終了において２つのオフセットを定義し、両方のオフセットは位置のラインに沿って作用し、メートル単位で測定される。オフセット値は必須ではなく、オフセット値がないことは０メートルのオフセットを意味する。また、オフセットは属性が含められたライン位置についてのみ有効である。
【０１５９】
１．４．５．１ オフセット・フラグ
オフセット・フラグはデータが特定のオフセット情報を含むかどうかを示す。物理データ形式は２つの相異なるオフセット値に対応する２つのフラグを扱う。正オフセット・フラグ（ＰｏｆｆＦ）と負オフセット・フラグ（ＮｏｆｆＦ）とが表Ａ２１、Ａ２２に表現される。
【０１６０】
【０１６１】
【０１６２】
１．４．５．２ オフセット値
オフセット値（正および負、ＰＯＦＦおよびＮＯＦＦ）は位置参照パスの開始（終了）と位置の「実在の（real）」開始（終了）との間の距離を示す。
【０１６３】
物理データ形式は各オフセット値について８ビット表現を定義する。表Ａ２３はＰＯＦＦおよびＮＯＦＦについて用いられるデータ・タイプを示す。この表現は各間隔の長さが５８．６メートルである２５６個の間隔を定義することを可能にする。オフセットについての間隔番号の計算は式Ｅ６に概要が説明される。
【０１６４】
【０１６５】
【０１６６】
１．５ 物理データ形式の仕様
このセクションはバイト・ストリーム内のデータ・フィールドの構成を表現する。バイト指向のストリームを有し、バイトごとに８ビットを使用できると想定する。
【０１６７】
１．５．１．概要
２進数形式の主な構造は、ヘッダ、先頭ＬＲＰ、後続ＬＲＰ、末尾ＬＲＰ、およびオフセットである。ヘッダ、先頭ＬＲＰ、および末尾ＬＲＰは必須であり、後続ＬＲＰの個数は制限されない。末尾ＬＲＰは相異なる情報レベルに起因して独自の構造を有する。オフセットはオプションであり、その存在は末尾ＬＲＰの属性内のフラグにより示されるだろう。
【０１６８】
表Ａ２４は主な構造の概要を与える。ストリームは左から右へ読み取ることができ、それにより最初に受信されるバイトは状態バイトであるだろう。各座標について、最初に受信される値は経度値であり、緯度値がそれに続くだろう。
【０１６９】
ＬＲＰの個数に依存するメッセージ・サイズの計算は以下のセクション１．６に見られうる。
【０１７０】
【０１７１】
１．５．２ 状態バイト
状態バイトはすべての位置参照情報について１回送信され、領域フラグ（ＡｒＦ、セクション１．４．４．３）、属性フラグ（ＡＦ、セクション１．４．４．２）、およびバージョン情報（ＶＥＲ、セクション１．４．４．１）を含む。ビット７、６、５は将来の使用のために予約（ＲＦＵ）され、０であるものとする。表Ａ２５は状態バイトの各ビットの用途の概要を与える。
【０１７２】
【０１７３】
形式のこの特定のバージョンでは、属性が各ＬＲＰへ付加され、領域は表現されない。「現在のバージョン」が２であるならば、状態バイトは表Ａ２６に示される値を有するだろう。
【０１７４】
【０１７５】
１．５．３．先頭ＬＲＰの座標
先頭ＬＲＰの座標は絶対形式（セクション１．４．２．１参照）で送信され、従って各値（ｌｏｔおよびｌａｔ）は３バイトを用いるだろう。表Ａ２７は経度値および緯度値についてのバイト順を示す。
【０１７６】
【０１７７】
１．５．４．後続ＬＲＰの座標
後続ＬＲＰおよび末尾ＬＲＰの座標は相対形式（セクション１．４．２．２参照）で送信され、従って各値（ｌｏｔおよびｌａｔ）は２バイトを用いるだろう。表Ａ２８は経度値および緯度値についてのバイト順を示す。
【０１７８】
【０１７９】
１．５．５．属性
属性は各ＬＲＰへ付加される。位置参照情報におけるＬＲＰの場所に依存して相異なる４種類の属性が存在する。
【０１８０】
１．５．５．１ 第１属性バイト（属性１）
第１属性バイトは属性ＦＲＣ（セクション１．４．３．１参照）とＦＯＷ（セクション１．４．３．２参照）とを含み、２ビットが将来の使用のために予約される。表Ａ２９は各ビットの用途を示す。
【０１８１】
【０１８２】
１．５．５．２ 第２属性バイト（属性２）
第２属性バイトは属性ＬＦＲＣＮＰ（セクション１．４．３．５）と属性ＢＥＡＲ（セクション１．４．３．３参照）とを含む。表Ａ３０は各ビットの用途を示す。ＬＦＲＣＮＰ情報が利用可能でないため、この属性は末尾ＬＲＰに対して有効でない。
【０１８３】
【０１８４】
１．５．５．３ 第３属性バイト（属性３）
第３属性バイトは表Ａ３１に示されるように属性ＤＮＰ（セクション１．４．３．４参照）を含む。ＤＮＰ情報が利用可能でないため、この属性は末尾ＬＲＰに対して有効でない。
【０１８５】
【０１８６】
１．５．５．４ 第４属性バイト（属性４）
属性４はＢＥＡＲ情報、正および負のオフセット・フラグ（セクション１．４．５．１参照）、ならびに将来の使用のために予約された１ビットを含む。表Ａ３２に示されるように、この属性は末尾ＬＲＰについて用いられる。
【０１８７】
【０１８８】
１．５．６ オフセット
正オフセット（ＰＯＦＦ）および負オフセット（ＮＯＦＦ）は、属性４内の対応するフラグがそれらの存在を示す場合にのみ含まれる。オフセット値を含まないことは０メートルのオフセット値を示す。オフセット値はセクション１．４．５に従って計算され、これらのオフセットのビット用途は表Ａ３３、Ａ３４に示される。
【０１８９】
【０１９０】
【０１９１】
１．６ メッセージ・サイズの計算
位置参照情報のメッセージ・サイズは位置参照情報に含まれるＬＲＰの個数に依存する。位置参照情報には少なくとも２つのＬＲＰが含まれるべきである。また、状態情報を伴うヘッダが必須である。以下の計算と表Ａ３５とはＬＲＰの個数に依存するメッセージ・サイズを示す。
・ヘッダ
１バイト状態
合計：１バイト
・先頭ＬＲＰ
６バイトＣＯＯＲＤ（ｌｏｎ／ｌａｔのそれぞれについて３バイト）
３バイト属性
合計：９バイト
・後続ＬＲＰ
４バイトＣＯＯＲＤ（ｌｏｎ／ｌａｔのそれぞれについて２バイト）
３バイト属性
合計：７バイト
・末尾ＬＲＰ
４バイトＣＯＯＲＤ（ｌｏｎ／ｌａｔのそれぞれについて２バイト）
２バイト属性
合計：６バイト
・オフセット（含まれる場合）
１バイト正オフセット（含まれる場合）
１バイト負オフセット（含まれる場合）
合計：０〜２バイト
【０１９２】
【０１９３】
上記の形式が用いられる方法の特定の例が、図９〜図１２を参照して上述された位置参照情報を参照して以下に提供される。これらの図では３つの位置参照点（ノード(1)、(10)、(15)およびライン(1)〜(3)、(10)〜(11)、(14)〜(15)）が位置を正確に表現するために識別される。位置参照情報は３つの位置参照点で構成され、以下の表Ａ３６はノード(1)、(10)、(15)についての座標を示す。これらのノードは位置参照点に対応するノードである。２進数形式の準備において、この表はまた、相対座標を示す。ノード(1)は位置参照点１に対応し、絶対形式の座標を有するだろう。位置参照点２に対応するノード(10)は位置参照点１に対する相対座標を有するだろう。位置参照点３に対応するノード(15)も相対座標を有するだろうが、ここでは位置参照点２を参照する。
【０１９４】
【０１９５】
相対経度および相対緯度は上記の式Ｅ３に従って計算される。符号化処理のステップ２で計算されるオフセットが表Ａ３７に示される。２進数データにおいて、正オフセットのみが現れるだろう。なぜなら、負オフセットは０であり、オフセットがない場合は０として扱われるだろうからである。
【０１９６】
【０１９７】
以下の表Ａ３８は基底のデジタル地図から計算を通じて各位置参照点についての関連データを収集する。これは機能的道路クラス、道路種別、および対応するラインの方位を含む。２つの連続した位置参照点間のパスに関して必要な情報（最低機能的道路クラスと次の位置参照点への距離）も示される。
【０１９８】
【０１９９】
ＢＥＡＲ属性、ＬＦＲＣＮＰ属性、およびＤＮＰ属性は上述のように決定される。以下の表は２進数データを作成するためのすべての関連情報を保持する。以下の表は物理データ形式に従って２進数データの概要を説明する。
・状態タイプ：表Ａ３９を参照。
・ＬＲＰ１： 表Ａ４０〜Ａ４４を参照。
・ＬＲＰ２： 表Ａ４５〜Ａ４９を参照。
・ＬＲＰ３： 表Ａ５０〜Ａ５３を参照。
・オフセット：表Ａ５４を参照。
【０２００】
【０２０１】
【０２０２】
【０２０３】
【０２０４】
【０２０５】
【０２０６】
【０２０７】
【０２０８】
【０２０９】
【０２１０】
【０２１１】
【０２１２】
【０２１３】
【０２１４】
【０２１５】
【０２１６】
完全な２進数データストリームは２４バイトの長さを有し、以下のもので構成される（左から右へ、そして上から下へのバイトとして並ぶ）。
【０２１７】
【技術分野】
【０００１】
本発明は効率的な地図アグノスティックでオンザフライの位置参照方法に関する。特に本方法は、テレアトラスＢ．Ｖ．およびナビテック・インクのような会社により製造され販売されるようなデジタル地図を前提条件として含んでいるが、使用されるデジタル地図の特定のバージョンまたはタイプは結果として生じる物理位置の符号化表現に対して基本的に重要でないという点で最終的に地図アグノスティックである位置符号化方法に具現化される。
【０００２】
明確性の理由で、本明細書で用いられる「位置（location）」という用語は、地表上のポイント位置、連続したパスまたは経路、またはこれらの連続したチェーンのような、地球上に存在するナビゲート可能な通路、または２個（長方形、正方形、または円形の領域の場合）またはより多いパラメータにより規定可能な地球上の領域または地域に関する様々な相異なる物理的な現実世界の特徴を包含するものとみなされる。より簡潔に、位置は単一または複合された地理的オブジェクトである。しかしながら、本発明は道路ネットワークを通るパスまたはデジタル地図に表されるその他のナビゲート可能な通路に関する効率的な、機械で読み取り可能な表現に主に適用される。
【背景技術】
【０００３】
ジオコーディングは、ストリート・アドレス、国、および／または郵便番号のような物理位置についての人間用参照システムを例えば緯度および経度のような関連する地理的座標に変換する既知の技術である。現在のところ様々な相異なるジオコーディング・システムが存在し、地理的座標空間にストリート・ネットワークがすでにマッピングされている地理的情報システム（ＧＩＳ）に少なくとも何らかの範囲で依存する。逆ジオコーディングは反対の処理である。
【０００４】
いかなる近年のデジタル地図（または時々知られるように数学的グラフ）もＧＩＳとしてみなすことができ、最も単純な形式では事実上、最も一般的には道路の交差点を現す（点または０次元オブジェクトとみなしうる）ノードを最初に規定し、交差点間の道路を表すノード間のラインを２番目に規定する複数のテーブルから構成されるデータベースである。より詳細なデジタル地図では、ラインは開始ノードおよび終了ノードにより定義されるセグメントに分割されてもよい。開始ノードと終了ノードとは、セグメント長がゼロのセグメントまたはループ状のセグメント（この場合にセグメントは非ゼロ長を有する）の場合に同一でありうるが、一般的には別々である。３つ以上のラインまたはセグメントが交わる道路交差点を表す場合に本明細書でノードは実在または「有効（valid）」であるとみなされうるが、「人工的（artificial）」または「回避可能な（avoidable）」ノードは一方または両方の端が実在ノードで定義されないセグメントに対してアンカーとして提供されるノードである。とりわけ道路の特定の範囲について形状情報を提供するためにこれらの人工ノードはデジタル地図において有用である。
【０００５】
このように、ノード、ライン、およびセグメントは道路ネットワークを完全に表現するために用いられてもよく、データベース内の各要素はさらに、データベースのテーブル内のデータによりやはり表される様々な属性により定義される。例えば、各ノードは典型的に現実世界の位置を規定するための緯度属性および経度属性を有するだろう。道路ネットワークの完全な「グラフ」は１つ以上の国またはその一部に及ぶ領域を覆うために何百万ものノードおよびセグメントにより表現される。
【０００６】
実際上、近年のすべてのデジタル地図がノードおよびセグメントの構造的定義を含んでいるが、これを達成する実際の方式はデジタル地図の提供者間で極めて多様である。例えば、各地図ベンダ（および場合によっては地図の各バーション）はノードであろうとセグメントであろうと、各地図要素に一意のＩＤを用いうる。従って、単純なジオコーディングおよび逆ジオコーディングでさえ、前提のデジタル地図が具現化されるデータベースの基底構造の何らかの知識を有する場合にのみ可能である。より単純な例では、緯度および経度に基づいて１つのデジタル地図データベースからストリート・アドレスを抽出するように設計されたクエリは別のものでは必ずしも動作しないだろう。対象の特定のデジタル地図データベースについて適切なように作り直す必要がありうる。これはまた、同じベンダにより提供されるデジタル地図の相異なるバージョンについても成り立ちうる。
【０００７】
デジタル地図データベースにしばしば含まれる１つの特定の属性は交通メッセージ・チャネル（ＴＭＣ）位置テーブル参照である。ＴＭＣは交通および移動の情報を乗り物のユーザ、より具体的にはこれらの乗り物内に存在し、何らかのデジタル地図の形式を含む（ポータブルまたは搭載型の）ナビゲーション・システムへ配信するための技術である。ＴＭＣメッセージは、（交通固有である必要はないが、これらが最も一般的である）イベント・コードおよび位置コードで構成され、位置コードはしばしば位置参照情報の順序リストで構成され、順序リストを用いて交通イベントの位置がデジタル地図において決定され、よってナビゲーション・システムの画面に図示されうる。デジタル地図内の複数の事前定義されたノードが、限られた位置テーブルを参照して決定されるＴＭＣ位置参照情報に割り当てられる。通常は道路交差点であり、デジタル地図で識別可能であるおおよそ同数の物理的または現実世界の位置に対応する２16（６５５３６）個の位置参照情報から位置テーブルは構成される。
【０００８】
３７ビットほどの短さでありえ、従って放送データのために利用可能な帯域にあまり影響を与えない点でＴＭＣメッセージは非常に効率的であるが、固定数の位置参照情報だけが利用可能であり、従って典型的に、ＴＭＣを提供する各国内の自動車道路または主要高速道路（もしくはその交差点）だけが参照されうる。ＴＭＣ位置参照情報にはその他に様々な不利益が存在する。例えば、ＴＭＣ位置テーブルは、
‐国家機関または国内政府を通じてしばしば維持され、
‐伝統的に非常に長い更新間隔で変更されがちであり、
‐一部の市場において、存在しないか、商業的にのみ利用可能である。
ＧＳＭおよびＧＰＳのプローブ・データを用いて二次的および都市部の道路に交通集積を識別することが可能になってきている（例えば乗り物のユーザはプローブとして使用可能な移動体電話または衛星接続ナビゲーション装置をますます所有する）ため、より発展的な参照システムが必要になる。
【０００９】
ＴＭＣ位置参照情報または地図固有の参照情報の欠点の一部を克服するための１つの試みは（ＩＳＯ１７５７２−１、２、３のもとで標準化過程にある）ＡＧＯＲＡ−Ｃとしても知られる動的位置参照プロジェクトである。ＡＧＯＲＡ−Ｃ位置参照アプローチの完全な説明は本出願の範囲外であるが、本アプローチの基本は、緯度および経度の座標ペアにより特定され、リスト内に順序付けされた位置点（location point）の集合により位置参照情報が完全に特定されえ、各点は様々なルールに従うが、最も重要なものとして、参照されている位置とリスト内の直前の点とが、すなわち連続した点が次点関係を形成するという点で各点が連続することである。他の位置参照システムと同様に、各点には複数の属性が提供され、属性はその点をよりよく定義することに役立つが、ＡＧＯＲＡ−Ｃ方法に特有なものとして各点を、位置点、交差点、経由点、およびこれら３つの何らかの組み合わせの１つとして識別することである。道路区間署名が変わる位置に沿った各点は交差点により表され、よって位置は道路ネットワーク上の経路であり、任意の道路区間署名の変更が交差点により参照される必要なく、交差点を通る。例えば、位置が関連する限りにおいて関係しない接点を含む自動車道路の区間を位置が含むならば、このような接点について交差点を含む必要はない。
【００１０】
ＡＧＯＲＡ−Ｃ符号化方法における初期段階の１つは、道路区間署名の変更が発生する位置に沿って最初と最後との交差点の間のすべての介在する交差点を決定することである。これらの点が点のテーブルへ追加され、最終的にＡＧＯＲＡ−Ｃ位置参照情報の一部を形成する。このテーブル内に、やはり所定のルールに従って少なくとも２つの経由点も識別されている。経由点は、経路計算によって（復号動作において）位置を再構築するために用いられる点であり、属性を保有する経由点を有する道路セグメントが所定の長さよりも長い場合にのみ提供される。ＡＧＯＲＡ−Ｃ標準に従う符号化処理の間、最初に識別された経由点から最後に識別された経由点までの経路を計算するために中間経由点が必要になるかについて判定がなされる。この判定は、重み付き最短パス・アルゴリズムを用いてなされる。すなわち追加の経由点が必要であると判定されたならば、これらはまた既存の交差点のテーブルに追加されるが、これは以前に識別された交差点にこのような点が一致しないような場合にだけである。この後者の場合に、既存の交差点が経由点としても識別されることを保証するために単純な属性変更が必要となる。ほとんどの場合において追加の経由点が必要にならないかもしれないが、位置が最初に特定された既存の交差点数を減らすのとは対照的に、ＡＧＯＲＡ−Ｃに適用される重み付き最短パス・アルゴリズムの影響は必要な点数を場合によっては増やすことがあることが注目されるべきである。
【００１１】
この参照アプローチは地理的情報システム内に存在する任意の位置を正確かつ反復して符号化し復号することが可能であるという点で包括的であるが、このシステムは所定の側面では過剰であり場合によっては冗長であり、多くの効率的な符号化システムが可能であると信じられる。例えば、参照方法がいかなる事前の編集作業から独立であり地図から独立であったとしても、平均的なＡＧＯＲＡ−Ｃメッセージのサイズは位置参照情報ごとに３０バイトを優に上回り、これは非常に混雑した輸送頻度とそれに関連付けられた次第に制限された帯域幅、特にこのような情報が送信されることが望まれうる移動体／無線装置に関する帯域幅との近年の風潮において禁止されないにしろ問題となりうる。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従って、本発明の目的は、
‐精度に関して著しく妥協することなくＡＧＯＲＡ−Ｃよりも効率的であり、
‐放送データについて利用可能な帯域幅に不利ではなく、
‐参照情報の作成の際に用いられる基底のデジタル地図における違い（またはそのバージョン間の違い）を説明でき、
‐ＴＭＣ位置参照システムの完全な代替になることができ、
‐デジタル地図が利用可能な任意の国の都市道路および下位レベルの道路を含む道路ネットワーク全体に対処でき、
‐定期的な保守を必要としない
位置参照情報のための効率的且つコンパクトな形式を提供することである。
【課題を解決するための手段】
【００１３】
道路ネットワーク内の連続したパスを符号化する方法であって、前記パスはデジタル地図に完全に表されるとともに、前記デジタル地図内に存在して連続に順序付けされたラインとセグメントとのうちの少なくとも一方のパス・リストとして表現可能であり、前記方法は、(i)‐前記パス・リストに最初に現われるライン又はセグメントか、若しくは前記最初のライン又はセグメントの開始ノードが人工的である場合に、実在の開始ノードを有する前記デジタル地図に現われ、場合によっては他の人工ノードを介して前記最初のライン又はセグメントに直接につながる最初のライン又はセグメントと、‐前記パス・リストに同様に現われる最も直近に識別された逸脱ライン又は逸脱セグメントとのうちの１つである開始場所を経路探索リストに記憶する工程と、(ii)前記開始場所を含み、前記開始場所の開始ノードから前記パス・リスト内の最後のライン又はセグメントの終点ノードへの前記デジタル地図内のパスを決定する工程であって、前記パスはアルゴリズムに従って決定される、工程と、(iii)そのように決定された最短パスを識別のために前記パス・リストに対して比較し、識別できない場合に、前記パス・リストの一部であり、前記デジタル地図内の交差点を表す開始ノードを有するものの、前記パス・リストに最初に現われるライン又はセグメントではない少なくとも１つの逸脱ライン又は逸脱セグメントを識別し、このような逸脱ライン又は逸脱セグメントが前記パス・リストに現われる最後のライン又はセグメントの終了ノードで終わらない場合に、前記逸脱ライン又は逸脱セグメントを用いて工程(i)を繰り返す工程と、(iv)前記パス・リスト内の最後のライン又はセグメントが既に記憶されていない場合に前記経路探索リストに記憶する工程とを有することを特徴とする方法が提供される。
【００１４】
好適には、開始場所と終了ノードとの間のパスを決定するために用いられるアルゴリズムは最短パス・アルゴリズムであるが、対応する逆アルゴリズムを用いてそのように決定されたパスを復号できるという点で可逆であるという前提で、他のアルゴリズムがまた採用されてもよい。
【００１５】
好適には、本方法は、最終の連結、変換、転置、及び結果として後述の位置参照点の有効な順序リスト又はその機械で読み取り可能な表現を生じる有効性動作のうちの少なくとも１つを行うことを含む。
【００１６】
本発明の第２側面では、コンピュータに上述の方法を実行させるためのコンピュータ・プログラム・コードを備えるコンピュータ・プログラムが提供される。さらに別の側面では、コンピュータで読み取り可能な記憶媒体に具現化されたこのようなコンピュータ・プログラムが提供される。
【００１７】
好適には、参照されることが望まれる連続したパスの始点および／または終点がデジタル地図の実在のノードに一致しない場合に、予備的有効性チェックは、連続パスの開始点及び終了点がデジタル地図内に現われる実在のノードに一致するようにこれらの点を延長し、連続したパスが実際に開始又は終了する前述の実在のノードの前後の距離を表すオフセットを記憶することを含む。
【００１８】
さらに好適には、連続パスの符号化はさらに、符号化に成功した各連続したパスをデータベースに記憶し、符号化が望まれる後続の連続したパスのそれぞれについて後続の連続したパス又はその一部がすでに符号化されているかを確立するために前記データベースへ問い合わせることによって改良される。さらに、後続の連続したパスが、それよりも大きなすでに符号化された連続パスの一部を形成する場合に、前記データベースを用いることで符号化処理に更なる効率化が実現されうる。さらにどの符号化が失敗したか、およびこのような連続したパスと同一またはその一部を形成する後続の連続パスを符号化する試行の十分に前に停止される符号化処理について、連続したパスを前記データベースに記憶することも可能でありうる。
【００１９】
本発明のその他の特徴が以下に説明され、添付の特許請求の範囲にさらに説明される。
【００２０】
位置参照情報を生成するＡＧＯＲＡ−Ｃ方法に比べて、本方法は実際に単純な最短パス・アルゴリズムを用いて位置に現われる位置参照点の必要な個数を低減しようと試みる。上述のように、ＡＧＯＲＡ−Ｃアプローチは、すでに包括的なリストにおいてどこに追加の経由点を挿入すべきかを決定するために重み付き最短パスを用いる。さらに、この重み付き最短パス・アルゴリズムは主として、より多くの幹線高速道路に並行して位置しうる、より低いクラスの道路に関する短い迂回路を避けるために採用される。
【００２１】
本発明は、非常に特定の状況に対するものとは対照的なより汎用に採用される単純なアルゴリズムが遥かに単純で、それ故（符号化時間の観点で）高速なアプローチを結果として生じることを実現する。結果として生じる位置参照情報は、連続したパスを完全に参照するために必要となる位置参照点の個数の観点で遥かにより効率的である。特に、本発明から生じる位置参照情報はセグメントおよび／またはラインの既存の完全なリストから導出されるが、本方法の出力はそのように参照される連続したパスが続いて復号動作において再構築されうる極小の点のリストを提供することであるため、それとはほとんど類似性を有しない。
【００２２】
例えば、デジタルにマッピングされた道路ネットワーク内の多くの連続したノード、セグメント、またはラインにより最初に表される数キロメートルの連続したパスは、前述のデジタル地図で表されるような道路ネットワーク上の当該パスの開始点と終了点とが実際にその全長にわたって連続パスに一致するならば、２つの位置参照点だけで表されうる。しかしながら、本発明は、好適には位置参照点間の１５ｋｍの制限の任意の強制を考慮しない。
【００２３】
本発明でさらに実現されることは、位置、交差点、および／または経由点のリストにより連続したパスを最初に表現するＡＧＯＲＡ−Ｃ方法とは対照的に、セグメントまたはラインのリストから最初に開始することによって、位置参照点へのこのようなリストのアルゴリズム的な低減の間に有用な効率性が達成されうる。
【００２４】
本発明の符号化方法を用いた実験は、典型的に利用可能な交通供給について約１８バイトの平均メッセージ・サイズが道路ネットワーク内の幅広く異なる位置または連続したパスについて一貫して達成可能であることを示した。３０バイト以上であるＡＧＯＲＡ−Ｃ位置参照メッセージに比較して、これは著しい低減を表す。
【００２５】
このような低減はネットワークを通る部分最短パスの合計または連結の観点で位置を参照することだけでなく、位置参照情報の一部を形成する各位置参照点について必要となる属性データを低減したことの結果として達成されうる。この低減は本発明に採用される物理データ形式および論理データ形式の以下の説明において明らかになるだろう。
【図面の簡単な説明】
【００２６】
【図１】符号化方法の概略図によるフローチャートを示す。
【図２】符号化方法の一部として最初に実行される有効性チェックの図式フローチャートを示す。
【図３】最短パス経路探索機能を含む符号化方法の反復部分の図式フローチャートを示す。
【図４】より詳細に最短パス経路探索機能の図式フローチャートを示す。
【図５】符号化が望まれる位置が最短パス経路探索により現在覆われているかどうかを判定することに含まれる手続きの図式フローチャートを示す。
【図６】、
【図７】、
【図８】図５に説明される手続きで場所が現在覆われていることをチェックすることにおいて生じる相異なる可能性を図的に説明する。
【図９】図９〜図１２はノードおよびセグメントを含むデジタル地図の図式表現を提供する。特に、図９は例示のネットワークを説明する。
【図１０】当該ネットワーク内で符号化が望まれる位置パスを説明する。
【図１１】当該位置を含む延長されたパスの開始ノードと終了ノードとの間の最短パスを説明する。
【図１２】当該位置を完全に参照するために必要となる位置参照点を説明する。
【図１３】図１３〜図２１は以下に説明される論理データ形式の文脈で有用である様々な図式説明を提供する。特に図１３は位置参照点（ＬＲＰ）の必要となる連続した連結を示す。
【図１４】１つのＬＲＰについてどのように方位が計算されるかを説明する図である。
【図１５】どのように方位が正の意味においてのみ変わりうるかを示す図である。
【図１６】どのように「次の点への距離」属性がＬＲＰについて決定されうるかを示し、当該属性が関連するＬＲＰはどれかをさらに示す図である。
【図１７】オフセットの使用を説明する図である。
【図１８】ＬＲＰに属性が提供される方法を示す図である。
【図１９】、
【図２０】位置参照情報の決定の間に回避されるノードを説明する図である。
【図２１】どのようにＬＲＰについての方位値が円の３２個に分離したセクタの１つに収まるかを説明する図である。
【発明を実施するための形態】
【００２７】
本発明の特定の実施形態が以下に添付の図面をしつつ、例示の方法により説明される。
【００２８】
本発明の以下の説明はセグメントの観点で提供されるが、本発明は道路ネットワークを通る連続したパスをともに表すラインやラインとセグメントとの組み合わせに等しく適用されうることが理解されるだろう。
【００２９】
まず図１を参照して、上述のように、本発明に従って以前に符号化が成功した完全な位置参照情報をデータベースに記憶することが可能であり、従って図１のステップ１０で、符号化が望まれる位置がすでに符号化されているかどうかを確立するためにこのようなデータベースがチェックされる。すでに符号化されているならば、更なる処理はなされずに、以前に符号化された位置がデータベースから読み出されうる。
【００３０】
データベース内に位置が存在しないならば、後述される所定の基準を位置が満たすかどうかを判定するために位置とそれを構成するセグメントとに関して有効性チェック１４が行われ、位置が有効であることを前提とすると、位置参照情報がステップ１６で作成される。有効性チェックまたはこの特定の位置についての位置参照情報の作成が失敗したならば、ステップ１８に示されるように、このような失敗も前述のデータベースに記憶されうる。
【００３１】
処理の最終ステップとして、１６で作成された位置参照情報がさらにステップ２０で有効性がチェックされる。ステップ２２は、１つの表現から別の表現への変換を表す点で例示的である。最終的に、（１つ以上の中間形式を含みうる）変換処理は、後述されるような物理データ形式で規定されるような、無線で送信可能であり機械で読み取り可能な２進数表現を結果として生じる。この形式は、エンコーダとデコーダとの間で情報を転送する際に有用なＸＭＬや事実上任意のその他のマークアップ表現または機械で読み取り可能な表現のような別の形式を取りうる。本発明は説明される特定の形式に制限されるとみなされるべきではない。その後、位置の完全で正確で正しい表現がステップ２４に示されるように前述のデータベースに記憶される。
【００３２】
図２を参照して、図１の１４で説明される「位置チェック」の有効性チェックがさらに説明される。すでに符号化された位置のデータベースに記憶されていないすべての位置は更なる処理の前に有効性についてチェックされる必要がある。最初のステップとして、３０で、連結性チェックが実行される。連結性のチェックは、連結していない２つ以上の相異なる部分に、入力された位置が分割されていないことを保証する。連結した部分のそれぞれは個別に処理される必要があり、それ自体で符号化される１つの位置を表す。１つの連結した部分のみで位置が構成される場合にこのチェックは通過される。
【００３３】
ステップ３２で、機能的道路クラス・チェックが実行される。このチェックは、最初の位置の一部を形成するセグメントのすべてが基底のデジタル地図において定義される最低機能的道路クラスを満たすことを保証する。機能的道路クラス（ＦＲＣ）は地図データ内のラインまたはセグメントの一般的な属性であり、特定のタイプの道路の相対的な重要度を示す属性である。０〜７の機能的道路クラスだけを含むことの任意の決定がなされている。なぜなら、これは任意のナビゲート不能な道路、交通イベントがほとんど生じないだろう非常に低いカテゴリの道路を効率的に排除するからである。
【００３４】
１つの実施形態では、エンコーダは位置がターン制限により影響を受けるかどうかをチェックすることが可能でありうる。可能であるならば、３４で示されるように途中にターン制限が存在するかどうかを位置は段階的に検査される。セグメントからセグメントへのすべてのターンが有効である必要がある。有効でないならば、３９で例外がスローされ、位置は符号化されないだろう。ターン制限チェックは使用可能である必要がないことを言及する価値があり、本方法は膨大な大多数の位置について位置の符号化に成功し続けるだろう。しかしながら、説明されたようなターン制限チェックを使用可能にすることは、符号化の成功を保証するための付加的な手段として単に動作する。
【００３５】
位置の有効性チェックの最終ステップとして、位置の最初のセグメントの開始ノードおよび位置の最後のセグメントの終了ノードが実在ノードであるか、それとは反対に人工的または回避可能なノードであるかに関して判定される。更に説明するために、ほとんどのインスタンスにおけるセグメントは人工的構造であり、地図ベンダによって任意に定義される傾向がある。それにもかかわらず、これらは、特定の道路部分に沿った何らかの任意の点で交通イベントが始まる現実世界の道路部分での交通イベントを表現することに関してラインと比べて遥かに優れた分解能を提供する。自動車道路または主要高速道路の文脈において、かなりの距離（例えば１５ｋｍ以上）離れて位置する（実在ノードで表される）２つの交差点の間の何らかの点で交通イベントが生じてもよく、従って交通状況が存在する正確な点は実在ノードよりも人工ノードの近くに遥かになりやすい。しかしながら、デコーダの地図にそのような人工ノードを有する確率は極めて小さく、よって、これらの人工ノードは回避されるべきである。これは、位置をその開始および終了において基底のデジタル地図に現れる実在ノードへ一意に延長することによってなされ、オフセット距離値はこのようなノードへの属性として提供され、その結果として交通（またはその他の）イベントの正確な場所、すなわち符号化される位置の正しい開始が正しく参照されうる。従って、位置を完全に覆うパスとオフセットとを用いて位置が正確に表現されうる。位置を覆い且つより長いパスを有することで、位置参照パスを再使用して、オフセットだけを更新することが可能になりえ、これは帯域幅および時間を節約するだろう。
【００３６】
従って、開始ノードが人工的でないならば、延長は存在しないだろう。それ以外の場合に、人工的な開始ノードを有する最初のセグメントへの内向きセグメントがステップ３６で新たな開始セグメントとして選択される。新たな開始セグメントの開始ノードも人工的または回避可能であるならば、適切な開始ノードが識別されるまで手続きが繰り返される。
【００３７】
２番目のステップ３８は位置の終了を延長しようとする。これは、最後のセグメントの終了ノードが評価されることを除いて開始セグメントに対するものと全く同じ方法で行われ、外向き道路セグメントに対して探索がなされる。これら２つのステップのいずれかにおいて人工ノードを延長できず且つ実在ノードが見つからなかった場合に、復号側で一致することを期待して人工ノードを用いて本方法で続けることが可能である。従って、本方法はなおも有効であるが、信頼性レベルは低くなる。
【００３８】
図３を参照して、図１の位置参照情報作成ステップ１６の説明が提供される。上述の有効性処理の後に、一連の有効なセグメントが提供され、これは後述の論理データ形式で定義されるオブジェクトのツリーとして位置参照情報へ変換されることが望まれる。
【００３９】
本発明に従う位置参照情報の生成における最初のステップ４０は、経路探索が開始されるべき最初のセグメントを識別することである。
【００４０】
その後に、ステップ４２で最初のセグメントと中間セグメントまたは逸脱セグメントとの何れかを用いて経路探索が実行される。経路探索は位置の最初の（または中間の）セグメントと最後のセグメントとの間の最短パス経路の計算である。経路探索の詳細は図４を参照してより詳細に説明される。
【００４１】
経路探索は開始セグメントと宛先セグメントとの間の最短パスを計算する。この計算は反復して行われ、ステップ５０での初期化の後に、ステップ５２、５４、５６、５８を含むメイン・ループが最短パスを計算するだろう。最短経路パスは（図５を参照して以下により詳細に説明される）ステップ５６で反復ごとにチェックされ、位置がなおも、計算された最短パス木の一部であるかどうかを確立する。もはや位置が最短パス木により覆われないならば、経路計算は停止し、ステップ６０において部分経路（いままで覆われた位置の部分）と、経路探索を一意にし、その後に続けることができる中間位置参照点として用いられるべきセグメントとを返す。この中間セグメントは図３におけるステップ４４で識別され、１つ以上の更なる経路探索が行われる新たな開始セグメントとして経路探索アルゴリズムへ返される。
【００４２】
理想的に経路探索は上述のように延長されていない位置の部分に焦点をあてるだろう。なぜなら、このパスからの逸脱は起こりえないために位置の延長部分は経路計算に影響を有しないからである。拡張は後のステップで位置参照情報へ追加されてもよい。
【００４３】
ステップ５０で、経路探索が初期化され、すべてのデータ構造がリセットされる。ステップ５２で、判定点５３において、経路探索が続けられるべきか停止されうるかに関してチェックされる。探索は以下の場合に停止されうる。
‐開始セグメントと宛先セグメントとの間の最短パスが見つかった場合。この場合に６２で示されるように最短パス経路が生成されうる。
‐これ以上処理するセグメントが存在しない場合。これは６４で示されるように、開始セグメントと宛先セグメントとの間に経路が存在しないことを意味する。
‐中間セグメントが識別された場合。
すべての実際の場合において、経路は常に存在するはすである。なぜなら、パスそのものは有効であり、このような経路を形成するからである。しかし、このチェックはすべての経路探索アルゴリズムに対して強制的である。探索が完了しない場合に、ステップ５４で、「次のラインを取得」手続きは、しばしば「オープン・リスト」と呼ばれる２つの関連するノード間の最短パスの一部を形成するすべてのラインのリストから最良のラインをフェッチする。最短パス・アルゴリズムの結果として、ラインへの最短パスが、ステップ５４で読み出されたオープン・リスト内に存在するものから位置の一部を形成するラインの入口で終了する。従って、「位置被覆チェック」ステップ５６は図５を参照して更に詳細に概要が説明されるが、簡潔にはこのステップは経路計算の間にこの条件が満たされるかどうかをチェックする。経路計算の間のチェックは、すべての固定セグメント（セグメントへの最短パスが最終的に決定された場合にセグメントは固定される）が位置の一部をも形成するかどうかが調査されるだろうことを意味する。現在検討中のセグメントが、参照されることが望まれる位置の一部を形成する場合に、位置の開始部分が現在の最短パス木に完全に含まれることを確立するためのチェックが行われる。これは、最後の位置セグメントへの計算された最短パスが位置そのものである必要があることを意味する。任意の逸脱に遭遇した場合に、経路計算は停止され、ステップ６０で部分経路が生成され、図３に説明される経路探索処理へ戻される。この図のステップ４４では、基底のデジタル地図において中間セグメントが識別され、この中間セグメントを開始点として用いて経路探索が再開される。
【００４４】
最短パス計算において現れた逸脱の特性に依存して、中間セグメントを正しく特定して参照するための様々な相異なる可能性が存在し、これらすべては図５〜図８を参照して説明される。
【００４５】
こうして今までに決定された最短パスの一致をチェックするために、経路探索の間に位置上に発見された最後のセグメントが（図５において７０で示される）経路探索リストに記憶され、その結果として、最後に記憶されたセグメントに連続した後続セグメントだけが、または少なくとも終了ノードと開始ノードとがそれぞれ一致するものだけを検討できるため、どのセグメントが次に来るべきかを容易に決定できる。最短パスに含まれるこれらのセグメントを最短パス経路探索が参照情報から効率的に排除すること、すなわちそれらが参照情報の一部を形成する必要がないことは位置参照情報長の経済性についての基本である。従って、判定点７２、７４において、最短パス経路リストの一部を形成する最も直近のセグメントが、符号化される位置に存在または一致し、
‐最短パス上で次に予想されるセグメント、および
‐前述の最短パス上で直前のセグメント
を参照するために最短パス・リストで理想的に用いられるポインタの観点で最短パスが関連する限りにおいて正しく参照されることのチェックが行われる。位置パス上にもあるこれらのポインタ参照セグメント両方を前提とすると、位置は最短パスにより正確に覆われるとみなされ、経路探索を継続できる。
【００４６】
しかし当然のことながら、より短い逸脱が不可避的に発見され、すべての取り得る逸脱の種類が図５のフローチャートの様々な分岐および図６〜図８の簡略化された線図で網羅される。最も単純には、位置パス上のセグメントが現在分析されているが、このセグメントが最短経路リストの関連する限りにおいて次に予想されるセグメントと食い違う場合に逸脱が発見される。最短経路リストの次に予測されるセグメントが位置パス・リストの次のセグメントに一致するが、最短パス・リストのこのセグメントへの先行ポインタが位置を指し示さない場合にも逸脱が発見される。このことは、先行ポインタが位置に関して発見された最後のポインタに等しくなければならないことを意味する。どちらの場合とも、適切な中間物を識別する必要がある。以下のステップはこの中間物を決定し、特殊な場合に２つの中間物を加える必要がある。適切な中間物の発見に関する主な焦点は交差点の一部である開始ノードを有するセグメントを用いることである。
【００４７】
まず図５、図６を参照して、７６で示されるように、すべての場合において逸脱の開始を発見する必要がある。図６は最短経路リストの一部として記憶され、また当初の位置パス・リストの一部を形成する最後のセグメントの前で逸脱が始まる最も単純な場合を説明する。説明される位置パス全体はセグメントＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、およびＧにより表される。そして、今まで確実に位置に一致すると判定された最短パスは図で太字にされたセグメントＡ、Ｄにより表される。最短パス探索の進行として、特に開始セグメントＡとセグメントＥの終了ノードとの間として、より短い逸脱Ｈが発見される。（最も一般的な場合であるだろう）このような場合に、位置上に現われ、逸脱が始まる開始ノードを有するセグメントを発見することが理想的には望まれる。このような場合に、セグメントＣが適切な中間物として含まれることが要求される。なぜなら、これは復号処理で実行される任意の最短パス・アルゴリズムで位置が追従されることを保証するからである。この探索はこの参照を満たすセグメントについての位置パス・リストを通じて再帰され、これは図５の７８、７９で参照される。図６に示される単純なパスの観点では起こりえないが、このようなセグメントが発見されない場合がある。この場合に、最短経路リストに最後に記憶されたセグメントは８０で説明されるように中間物として用いられうる。なぜなら、最後に記憶されたセグメントを自身の開始として用いる最短パス関数はその前から始まる如何なる逸脱も決して識別しないからである。
【００４８】
代替の実施形態では、図７で強調されるように、経路探索リストに記憶された最後のセグメントＥの終了の後に逸脱が始まる。この場合に、ＡからＥへの最短パスは既知であり、ＡからＥまでのセグメントだけが記憶されている。セグメントＡからセグメントＦの終了ノードまでの最短パスは実際にはＡとＩとだけによって参照される。ＩはＦを含む位置からの逸脱であり、最後に記憶されたセグメントＥの終了の後に発生する。この場合に、セグメントＦへの先行ポインタが実際には位置上のセグメント、この場合にＥを指し示すことを前提すると、図５の８２で示されるように、中間物はこのセグメントＦから生成されうる。このチェックは８４で示される。
【００４９】
セグメントＫがセグメントＪを参照する場合のような、最短経路探索の一部として記憶される最後のセグメントの後の発生する逸脱が位置の一部を形成しないセグメントを実際に参照する図８の例外的な場合では、最初のステップとして、（前述された８２のように）第１中間セグメントＥが生成され、第２中間セグメントＤも記憶される。なぜなら、これは位置パス上で発生し、より短いパス・セグメントＪが始まる交差点から始まる最後のセグメントだからである。これらのステップは図５の８６、８８として総括的に示され、記憶された位置参照情報は最終的にセグメントＪ、Ｋの両方を回避しなければならないため、これらのステップは必須である。
【００５０】
最後に図３を参照して、位置パス・リスト全体の処理が完了すると、識別されたすべての部分最短パスがステップ４６で結合される。位置の被覆は、最初の経路計算が中間セグメントを決定した場合にいくつかの部分経路で構成されうる。この中間セグメントは、経路探索が位置の完全な被覆となるように導くために位置参照情報の付加情報として機能する。経路探索が位置の終了に到達すると、すべての計算された部分経路が結合されて、位置を完全に覆うパスを形成する。１つの実施形態ではこのステップはまた、図２に説明されたステップ３６、３８で計算されたような位置の開始および終了における拡張を付加しうる。最初の位置参照点および最後の位置参照点が調整され、当初位置の相対位置を表す新たなオフセットが計算される。
【００５１】
本発明を用いて位置を符号化する方法のよりよい理解を提供するために、図９〜１２を参照して更なる特定の例が提供される。
【００５２】
エンコーダの地図が図９に示され、１５個のノードと２３個のライン（双方向のラインは２度数える）とで構成される。ノードは１から１５まで番号付けされる。必要なライン属性が形式＜ＦＲＣ＞、＜ＦＯＷ＞、＜メートル単位の長さ＞を用いてすべてのラインのそばに示される。ＦＲＣは「機能的道路クラス」の略語であり、ＦＯＷは「道路種別」の略語であり、これらの両方は以下により詳細に説明される。矢印は各ラインについての取り得る運転方向を示す。
【００５３】
図１０において、符号化される位置が太線で示される。位置はノード(3)から始まり、続いてノード(5)、(7)、(10)、(11)、(13)、(14)を通り、ノード(15)で終わる。エンコーダの地図におけるその全長は６８５メートルである。符号化の間に用いられるラインの順序リストとマップとはエンコーダへの入力としての機能を果たす。
【００５４】
符号化：
符号化処理の最初のステップで、位置はまず有効性についてチェックされる。位置は連結され運転可能であり、位置に沿った機能的道路クラスは０と７との間であるため、この位置は有効である。ターン制限はマップ・データに含まれず、従ってエンコーダはこのチェックを無視しうる。
【００５５】
エンコーダの２番目のステップは、ある所定のデータ形式ルールに従って位置の開始ノードおよび終了ノードが実在ノードであるかをチェックすることである。終了ノード(15)は１つの内向きラインのみを有するので有効である。また、開始ノード(3)は２つの付帯するラインを有するが、ここでは１つは外向きラインであり、１つは内向きラインである。従って、このノードは有効でなく、エンコーダは位置の外側の実在ノードを検索する。エンコーダは実在ノードとしてノード(1)を発見し、位置を一意に拡張するだろう。ノード(1)は位置参照情報のための新たな開始ノードとして選択され、１５０メートルの正オフセットが存在するだろう。位置参照パスの全長は結果として８３５メートルになる。
【００５６】
エンコーダの３番目のステップは位置の開始ライン（この場合に、ノード(1)とノード(3)との間のラインである。しかしながら、一般の使用法で、最短パスは延長なしに計算されうる。）と終了ライン（ノード(14)とノード(15)との間のライン）との間の最短パスの計算を続いて行う。結果の最短パスは図１１に太線で概要が説明される。最短パスは７２５メートルの長さを有する。
【００５７】
符号化処理の次（４番目）のステップは、計算された最短パスにより位置が覆われるかどうかをチェックすることである。この場合は覆われておらず、ノード(10)の後に逸脱が存在することが判定されるだろう。
【００５８】
上述の原理に従って、エンコーダはノード(10)からノード(11)へのラインが新たな中間位置参照点になると決定するだろう。経路探索の間にノード(10)をスキップできないためノード(10)は実在ノードであり、このラインへの最短経路は位置の対応する部分を完全に覆う。この最初の最短パス計算の後に覆われる位置の長さは５６１メートルである。
【００５９】
次の符号化ステップは位置の残り部分（ノード(10)からノード(11)、(13)、(14)を経由してノード(15)まで）について最短パスを決定するために経路計算を準備する。従って、最短パス計算は(10)から(11)へのラインで始まり、(14)から(15)へのラインで終わるだろう。
【００６０】
エンコーダは上述のステップ３へ戻り、(10)と(15)との間の最短パス（長さ：２７４メートル）を決定し、上述のステップ４は、現段階で計算された最短パスにより位置が完全に覆われたことを返す。
【００６１】
次のステップとして、位置参照パスは２つの最短パスで構成され、位置参照点の順序リストがここで形成されるだろう。図１２は位置参照点として選択されたラインが太く示される。１番目の位置参照点はノード(1)からノード(3)へのラインを指し示し、位置参照パスの開始を示す。２番目の位置参照点はノード(10)からノード(11)へのラインを指し示し、このラインは位置からの逸脱を回避するために必要であった。最後の位置参照点はノード(14)からノード(15)へのラインを指し示し、位置参照パスの終了を示す。
【００６２】
最後から２番目のステップは位置参照情報の有効性のチェックである。２つの連続した位置参照点間のすべての長さは最大距離よりも短いため、位置参照情報は有効であると確認される。
【００６３】
最後のステップはＬＲＰの順序リストを２進数位置参照情報へ変換することであり、出願人により規定された論理データ形式と物理データ形式との両方の以下の説明はこれがどのように実現されるかの理解を助けるだろう。特定の形式の詳細を提供する以下の詳細な説明は単に例として提供され、当業者は他の形式を取りうることを理解するだろうことが強調されるべきである。
【００６４】
論理データ形式および物理データ形式の仕様
以下の表は本明細書において位置参照情報の文脈で用いられる一般用語および略語を説明する。
【００６５】
【００６６】
１．データ形式
位置参照情報はデジタル地図の指定された部分または一連の地理的場所の表現である。この表現のために、位置参照点（ＬＲＰ、１．１．１参照）のモデルを用いる。
【００６７】
ライン位置についての位置参照情報は少なくとも２つのＬＲＰを含むがＬＲＰの最大数は規定されない。位置参照パスはＬＲＰにより表現されるデジタル地図内のパスであり、ＬＲＰの連続したペアのそれぞれの間の最短パス計算により発見されうる。
【００６８】
１．１ 論理データ形式の仕様
論理データ形式はＭａｐＬｏｃ（商標）標準に従って位置参照情報についての論理モデルを表現する。
【００６９】
１．１．１．位置参照点（ＬＲＰ）
位置参照情報の基盤は一連の位置参照点（ＬＲＰ）である。このようなＬＲＰはＷＧＳ８４の経度値および緯度値で特定された座標ペアと、付加的ないくつかの属性とを含む。
【００７０】
座標ペア（１．１．３．１参照）は地図／ネットワーク内の地理的位置を表し、ＬＲＰについて必須である。座標ペアはネットワーク内の「実在（real）」ノードに属する。
【００７１】
属性（セクション１．１．３．２〜１．１．３．６参照）は、座標ペアにより表現されるノードにラインが付帯する、ネットワーク内のラインの値を表す。この文脈では、ノードに関して内向きラインと外向きラインとのどちらを属性が指すかは規定されない。これはセクション１．２で特定される。
【００７２】
１．１．２．ＬＲＰのトポロジー連結
図１３を参照して、位置参照点はトポロジーの順序で、すなわち連続したＬＲＰの「次の点（next point）」関係で記憶されるものとする。この順序の最後の点はこの関係における次の点を有しないだろう。
【００７３】
図１３はこの関係の例を示す。ＬＲＰはＡ１、Ｂ１、およびＣ１によって示され、黒線矢印は位置参照パスにおけるＡ１からＣ１への点の順序を示す。この例では、ＬＲＰ Ａ１は次の点としてＢ１を有し、Ｂ１は次の点としてＣ１を有し、Ｃ１は次の点を有しないだろう。
【００７４】
１．１．３．ＬＲＰのコンポーネント
このセクションは位置参照点のコンポーネントを説明する。
【００７５】
１．１．３．１ 座標ペア
座標ペアはＷＧＳ８４の経度（ｌｏｎ）の値と緯度（ｌａｔ）の値とのペアを意味する。この座標ペアはデジタル地図における幾何的な点を特定する。ｌｏｎ値およびｌａｔ値はデカミクロンの分解能（１０-5、すなわち小数点５位）で記憶される。
【００７６】
略語：ＣＯＯＲＤ タイプ：（浮動小数，浮動小数）
【００７７】
１．１．３．２ 機能的道路クラス
機能的道路クラス（ＦＲＣ）は道路の重要度に基づく道路分類である。ＦＲＣ属性の取りうる値が表Ａ２に示される。これら８個の位置参照値よりも多くのＦＲＣ値が定義されるならば、適切なマッピングが行われる必要があるか、または重要性の低いクラスが無視される必要がある。
【００７８】
【００７９】
略語：ＦＲＣ タイプ：整数
【００８０】
１．１．３．３ 道路種別（Form of way）
道路種別（ＦＯＷ）は物理的道路タイプを表現する。ＦＯＷ属性の取りうる値が表Ａ３に示される。
【００８１】
【００８２】
略語：ＦＯＷ タイプ：整数
【００８３】
１．１．３．４ 方位
方位（ＢＥＡＲ）は、真北と、ＬＲＰの座標およびＬＲＰ属性により定義されるラインに沿ってＢＥＡＲＤＩＳＴである座標により定義されるラインとの間の角度を表現する。ライン長がＢＥＡＲＤＩＳＴよりも短いならば、（ＢＥＡＲＤＩＳＴに関わらず）ラインの反対側の点が使用される。方位は角度単位で測定され、（北から時計回りに測定され）常に正である。パラメータであるＢＥＡＲＤＩＳＴは表Ａ４に定義される。
【００８４】
略語：ＢＥＡＲ タイプ：整数
【００８５】
【００８６】
図１４は方位計算のための第２点がどのように決定されるかを示す。この図はＢＥＡＲＤＩＳＴよりも長いＡ２からＢ２へのラインを示す。このラインの斜線部分はＢＥＡＲＤＩＳＴメートルちょうどの長さであり、その結果としてＢ′で印が付けられた点はＡ２からＢ２へのラインに沿って移動して、Ａ２からＢＥＡＲＤＩＳＴメートル離れている。Ａ２からＢ′への直線が方位値の計算のために以下で検討される。ラインの反対側のノード（この場合、これはＢ２であるだろう）が用いられる場合に計算されるだろう角度はこれとは異なる。
【００８７】
図１５は方位値を計算する２つの例を示す。１つはＡ３からＢ３までであり、１つはＡ３からＣ３までである２つのラインが存在する。両方のラインについて、弧は北に対する角度を示す。
【００８８】
１．１．３．５ 次のＬＲＰへの距離
このＤＮＰフィールドはＬＲＰのトポロジー連結における次のＬＲＰへの距離を表現する。距離はメートル単位で測定され、位置参照パスに沿って計算される。最後のＬＲＰは距離値としてゼロを有するだろう。
【００８９】
略語：ＤＮＰ タイプ：整数
【００９０】
図１６は距離の計算と割り当てとの例を示す。３つのＬＲＰがＡ４からＢ４を越えてＣ４まで一列に存在する。従って、位置参照パスに沿ったＡ４とＢ４との距離はＡ４に割り当てられるだろう。ＬＲＰ Ｂ４はＢ４とＣ４との間の距離を保持し、ＬＲＰ Ｃ４は距離値としてゼロを有するだろう。
【００９１】
１．１．３．６ 次のＬＲＰへの最低ＦＲＣ
最低ＦＲＣ（ＬＦＲＣＮＰ）は２つの連続したＬＲＰの間の位置参照パスに現れる最低のＦＲＣ値である。最高のＦＲＣ値は０であり、取りうる最低のＦＲＣ値は７の値を有する。
【００９２】
略語：ＬＦＲＣＮＰ タイプ：整数
【００９３】
１．１．４．オフセット
オフセットは位置参照パスをその開始および終了において縮小するために用いられる。位置参照パスに沿った新たな場所は、位置の実際の開始および実際の終了を示す。
【００９４】
１．１．４．１ 正オフセット
正オフセット（ＰＯＦＦ）は位置参照情報の開始点と所望の位置の開始点との位置参照パスに沿った距離である。値はメートル単位で測定される。図１７は正オフセットおよび負オフセットの計算の例を示す。線は位置参照パスを示し、ハッチングは所望の位置を示す。
【００９５】
略語：ＰＯＦＦ タイプ：整数
【００９６】
１．１．４．２ 負オフセット
負オフセット（ＮＯＦＦ）は所望の位置の終了点と位置参照情報の終了点との位置参照パスに沿った距離である。値はメートル単位で測定される（図１７を再び参照）。
【００９７】
略語：ＮＯＦＦ タイプ：整数
【００９８】
１．２ 関連属性‐ＬＲＰ
すべての属性はＬＲＰにリンクされる。（最後のＬＲＰを除く）すべてのＬＲＰについて、属性はＬＲＰ座標におけるノードの外向きラインを表す。最後のＬＲＰの属性はＬＲＰ座標におけるノードの内向きを対象とする。
【００９９】
図１８はＬＲＰと属性との間の関連の例を示す。ラインは位置参照パスを示し、ノードＡ５、Ｂ５、およびＣ５がＬＲＰである。開始ノードおよび終了ノードがＬＲＰでないライン（列の３番目のライン）も存在することに留意されたい。このラインは、ＬＲＰ Ｂ５とＬＲＰ Ｃ５との間の最短パスにより覆われるため、参照される必要はない。
【０１００】
ＬＲＰ Ａ５およびＬＲＰ Ｂ５は外向きラインを対象とし、最後のＬＲＰ Ｃ５は内向きラインを対象とする。
【０１０１】
１．３ データ形式のルール
これらのルールはこの仕様に従う位置参照情報についての追加の規則を表現する。これらのルールは符号化処理および復号処理を単純化し、結果の精度を高めるために用いられる。
【０１０２】
ルール１ ２つの位置参照点の間の最大距離は１５ｋｍを超えないものとする。距離は位置参照パスに沿って測定される。位置参照情報についてこの条件が満たされないならば、十分な数の追加のＬＲＰが挿入されるものとする。
【０１０３】
２つの連続した位置参照点の間の最大距離は最短パス計算を速めるために制限される。なぜなら、経路アルゴリズムがネットワーク全体を考慮に入れなければならない場合に、１つの長い経路よりも複数の短い経路の方が速く計算されうるからである。本制限はまた、許容精度でコンパクトな２進数形式を形成する機会を提供する。
【０１０４】
ルール２ すべての長さは整数値である。浮動小数値が利用可能ならば、整数表現を得るためにこれらの値を丸める。
【０１０５】
様々な地図は長さの値を様々な形式で且つ様々な精度で記憶するかも知れず、すべてに対する統一の基盤は整数値を使用することである。また、浮動小数値を用いるよりも２進数形式の整数値を送信する方がコンパクトである。
【０１０６】
ルール３ ２つのＬＲＰが必須であり、中間ＬＲＰの個数は制限されない。
【０１０７】
ライン位置参照情報は位置の開始および終了を示す少なくとも２つの位置参照点を常に有していなければならない。（異なる地図に関して）デコーダに問題が発生するかもしれない危機的状況をエンコーダが検出するならば、位置参照情報は追加の中間ＬＲＰで強化されうる。
【０１０８】
ルール４ ＬＲＰの座標は実在ネットワーク・ノード上に選択されるものとする。
【０１０９】
これらの実在ネットワーク・ノードは現実世界の接点であるべきで、これらの接点はライン上のどこかの場所よりも高い確率で異なる地図で発見されうることが期待される。さらに、経路検索の間に容易にスキップされうるノードは回避されるものとする。これらの回避可能なノードにおいて、経路から逸脱する可能性はない。
【０１１０】
１つの内向きラインおよび１つの外向きラインのみを有するノードは、これらのノードが接点に関連せず（図１９参照）、経路探索の間にスキップされうるために、回避されるものとする。２つの内向きラインおよび２つの外向きラインを有し、２つの隣接ノードのみが存在するノードは同様に回避されるものとする（図２０参照）。
【０１１１】
これらのノードの１つがＬＲＰについて選択されると、このＬＲＰは適切なノードを見つけるために位置参照パスに沿ってシフトされるべきである。これは、所望のパスを逸脱することなくこのような回避可能なノードを経路計算がスキップするために行われうる。
【０１１２】
位置の開始または終了が回避可能なノード上に配置されるならば、エンコーダは位置を一意に拡張すべきであり、位置の外側の適切なノードを見つけるべきである。この拡張は位置へ入り込むべきではない。なぜなら、これは位置を縮小するだろうからである。
【０１１３】
１．３．１．データ形式ルールの概要
以下の表Ａ５はデータ形式ルールを要約する。
【０１１４】
【０１１５】
１．４ ２進数表現
物理データ形式は上述の論理データ形式についてのバイト指向のストリーム形式を表現する。これはセクション１．１の論理データ形式において表現されたコンポーネントを用いる。
【０１１６】
１．４．１．データ・タイプ
物理データ形式は以下のデータ・タイプを用いる。表Ａ６はすべての利用可能なデータ・タイプの概要を与え、名前、タイプ、および各データ・タイプの指定サイズを特定する。以下のセクションでは、データ・タイプ名は各データ・コンポーネントについてサイズおよびタイプを示すために用いられる。
【０１１７】
【０１１８】
負の整数値が２つのコンポーネント形式で記憶される。
【０１１９】
１．４．２．座標（ＣＯＯＲＤ）
地図内の各点はＷＧＳ８４座標で表された「経度」（ｌｏｎ）と「緯度」（ｌａｔ）との座標ペアで構成される。北方向および東方向は（経度、緯度それぞれ）正の値で表される。ｌｏｔ値およびｌａｔ値はデカミクロンの分解能（１０-5、小数点第５位）で記憶される。
【０１２０】
座標値は整数値として送信されるだろう。これらの値は２４ビット整数表現を算出する式Ｅ１を用いて生成されるだろう。分解能パラメータは２４に設定される。この変換は最大で約２．４メートルの誤差を生じる。逆変換は式Ｅ２で表現される。両方の式は、負の値について−１、正の値について１、その他について０である符号関数を利用する。
【０１２１】
【０１２２】
【０１２３】
物理形式は絶対座標形式と相対座標形式とを利用する。絶対形式は地理的場所の指定された値を表し、相対値は先行する座標に対するオフセット座標である。
【０１２４】
１．４．２．１ 絶対形式
絶対形式は２４ビット分解能における地理的場所を表現する。表Ａ７は絶対形式に用いられるデータ・タイプを示す。
【０１２５】
【０１２６】
１．４．２．２ 相対形式
相対形式は２つの連続した座標間の差を表現するために用いられる。差は式Ｅ３に示されるように各値（ｌｏｎ／ｌａｔ）別々に計算される。現在の値および前の値は緯度値（経度値）を角度単位で表す。これら２つの値の差は整数値へ変化させるために１０００００倍される。
【０１２７】
【０１２８】
表Ａ８は１６ビット表現を用いて取りうる最大距離を示す。この図はｌｏｎ＝５°、ｌａｔ＝５２°（オランダ内の場所）における固定の座標について計算される。
【０１２９】
【０１３０】
表Ａ９は２バイト・オフセットについてのデータ・タイプを示す。
【０１３１】
【０１３２】
１．４．３．属性値
属性の２進数形式がこのセクションで続く。
【０１３３】
１．４．３．１ 機能的道路クラス（ＦＲＣ）
機能的道路クラス（ＦＲＣ）は論理形式で説明されたように８個の相異なる値を保持しうる。これらの８個の値は表Ａ１０で示される３ビットとマッピングとにより表される。
【０１３４】
【０１３５】
１．４．３．２ 道路種別（ＦＯＷ）
道路種別（ＦＯＷ）は論理形式において説明されたように８個の相異なる値を保持しうる。これらの８個の値は表Ａ１１で示される３ビットとマッピングとにより表される。
【０１３６】
【０１３７】
１．４．３．３ 方位（ＢＥＡＲ）
方位は論理形式において説明されたように道路と真北との間の角度を表現する。物理データ形式は３２個のセクタを定義し、各セクタは円のうち１１．２５°をカバーする。これらの３２個のセクタは５ビットで表される。表Ａ１２は方位属性についてのデータ・タイプを示し、表Ａ１３はセクタから具体的な値へのマッピングを示す。
【０１３８】
【０１３９】
【０１４０】
式Ｅ４は方位値の計算の概要を説明し、図２１はセクタの図示による概要を提供する。
【０１４１】
【０１４２】
１．４．３．４ 次のＬＲＰへの距離（ＤＮＰ）
ＤＮＰ属性は論理形式において説明されたように位置参照パスに沿った２つの連続したＬＲＰ間の距離を測定する。
【０１４３】
物理データ形式は８ビット表現を定義し、表Ａ１４はＤＮＰについて用いられるデータ・タイプを示す。この表現は２５５個の間隔を定義し、データ形式ルールのルール１（２つの連続したＬＲＰ間の最大長は１５０００ｍに制限される）と組み合わせて各間隔は５８．６メートルの長さを有するだろう。
【０１４４】
【０１４５】
式Ｅ５はどのようにＤＮＰ値を計算できるかを示す。
【０１４６】
【０１４７】
１．４．３．５ 次の点への最低ＦＲＣ（ＬＦＲＣＮＰ）
次の点への最低ＦＲＣは次のＬＲＰへの位置参照パスに用いられる最低の機能的道路クラスを示す。この情報は復号の間にスキャンされる必要のある道路クラスの個数を制限するために用いられうる。データ・タイプの定義については表Ａ１５を参照されたい。
【０１４８】
【０１４９】
１．４．４．位置参照情報ヘッダ
位置参照情報ヘッダは参照情報に関する一般的な情報を含む。
【０１５０】
１．４．４．１ バーション（ＶＥＲ）
バーションは位置参照情報についての複数の物理的なデータ・フォーマットを区別するために用いられる。バージョン番号は３ビットで表され、データ・タイプは表Ａ１６に示される。
【０１５１】
【０１５２】
１．４．４．２ 属性フラグ（ＡＦ）
属性フラグは各ＬＲＰへ付加された属性が存在するか否かを示す。属性が付加されていない場合にＡＦ値は０となり、従って位置参照情報は座標だけで構成される。それ以外の場合、値は１となり各ＬＲＰへ属性が付加されることを示す。ＡＦについてのデータ・タイプは表Ａ１７、Ａ１８に示される。
【０１５３】
【０１５４】
【０１５５】
１．４．４．３ 領域フラグ（ＡｒＦ）
領域フラグは位置参照情報が領域を記載するか否かを示す。このフラグが設定されるならば、位置は結合しているものとし、以下の表Ａ１９、Ａ２０に見られるように領域を表現する。
【０１５６】
【０１５７】
【０１５８】
１．４．５．オフセット
オフセットはネットワーク内のノードへ結び付けられたものよりも正確に位置の開始および終了を位置付けるために用いられる。論理形式は、１つは位置の開始において、もう１つは位置の終了において２つのオフセットを定義し、両方のオフセットは位置のラインに沿って作用し、メートル単位で測定される。オフセット値は必須ではなく、オフセット値がないことは０メートルのオフセットを意味する。また、オフセットは属性が含められたライン位置についてのみ有効である。
【０１５９】
１．４．５．１ オフセット・フラグ
オフセット・フラグはデータが特定のオフセット情報を含むかどうかを示す。物理データ形式は２つの相異なるオフセット値に対応する２つのフラグを扱う。正オフセット・フラグ（ＰｏｆｆＦ）と負オフセット・フラグ（ＮｏｆｆＦ）とが表Ａ２１、Ａ２２に表現される。
【０１６０】
【０１６１】
【０１６２】
１．４．５．２ オフセット値
オフセット値（正および負、ＰＯＦＦおよびＮＯＦＦ）は位置参照パスの開始（終了）と位置の「実在の（real）」開始（終了）との間の距離を示す。
【０１６３】
物理データ形式は各オフセット値について８ビット表現を定義する。表Ａ２３はＰＯＦＦおよびＮＯＦＦについて用いられるデータ・タイプを示す。この表現は各間隔の長さが５８．６メートルである２５６個の間隔を定義することを可能にする。オフセットについての間隔番号の計算は式Ｅ６に概要が説明される。
【０１６４】
【０１６５】
【０１６６】
１．５ 物理データ形式の仕様
このセクションはバイト・ストリーム内のデータ・フィールドの構成を表現する。バイト指向のストリームを有し、バイトごとに８ビットを使用できると想定する。
【０１６７】
１．５．１．概要
２進数形式の主な構造は、ヘッダ、先頭ＬＲＰ、後続ＬＲＰ、末尾ＬＲＰ、およびオフセットである。ヘッダ、先頭ＬＲＰ、および末尾ＬＲＰは必須であり、後続ＬＲＰの個数は制限されない。末尾ＬＲＰは相異なる情報レベルに起因して独自の構造を有する。オフセットはオプションであり、その存在は末尾ＬＲＰの属性内のフラグにより示されるだろう。
【０１６８】
表Ａ２４は主な構造の概要を与える。ストリームは左から右へ読み取ることができ、それにより最初に受信されるバイトは状態バイトであるだろう。各座標について、最初に受信される値は経度値であり、緯度値がそれに続くだろう。
【０１６９】
ＬＲＰの個数に依存するメッセージ・サイズの計算は以下のセクション１．６に見られうる。
【０１７０】
【０１７１】
１．５．２ 状態バイト
状態バイトはすべての位置参照情報について１回送信され、領域フラグ（ＡｒＦ、セクション１．４．４．３）、属性フラグ（ＡＦ、セクション１．４．４．２）、およびバージョン情報（ＶＥＲ、セクション１．４．４．１）を含む。ビット７、６、５は将来の使用のために予約（ＲＦＵ）され、０であるものとする。表Ａ２５は状態バイトの各ビットの用途の概要を与える。
【０１７２】
【０１７３】
形式のこの特定のバージョンでは、属性が各ＬＲＰへ付加され、領域は表現されない。「現在のバージョン」が２であるならば、状態バイトは表Ａ２６に示される値を有するだろう。
【０１７４】
【０１７５】
１．５．３．先頭ＬＲＰの座標
先頭ＬＲＰの座標は絶対形式（セクション１．４．２．１参照）で送信され、従って各値（ｌｏｔおよびｌａｔ）は３バイトを用いるだろう。表Ａ２７は経度値および緯度値についてのバイト順を示す。
【０１７６】
【０１７７】
１．５．４．後続ＬＲＰの座標
後続ＬＲＰおよび末尾ＬＲＰの座標は相対形式（セクション１．４．２．２参照）で送信され、従って各値（ｌｏｔおよびｌａｔ）は２バイトを用いるだろう。表Ａ２８は経度値および緯度値についてのバイト順を示す。
【０１７８】
【０１７９】
１．５．５．属性
属性は各ＬＲＰへ付加される。位置参照情報におけるＬＲＰの場所に依存して相異なる４種類の属性が存在する。
【０１８０】
１．５．５．１ 第１属性バイト（属性１）
第１属性バイトは属性ＦＲＣ（セクション１．４．３．１参照）とＦＯＷ（セクション１．４．３．２参照）とを含み、２ビットが将来の使用のために予約される。表Ａ２９は各ビットの用途を示す。
【０１８１】
【０１８２】
１．５．５．２ 第２属性バイト（属性２）
第２属性バイトは属性ＬＦＲＣＮＰ（セクション１．４．３．５）と属性ＢＥＡＲ（セクション１．４．３．３参照）とを含む。表Ａ３０は各ビットの用途を示す。ＬＦＲＣＮＰ情報が利用可能でないため、この属性は末尾ＬＲＰに対して有効でない。
【０１８３】
【０１８４】
１．５．５．３ 第３属性バイト（属性３）
第３属性バイトは表Ａ３１に示されるように属性ＤＮＰ（セクション１．４．３．４参照）を含む。ＤＮＰ情報が利用可能でないため、この属性は末尾ＬＲＰに対して有効でない。
【０１８５】
【０１８６】
１．５．５．４ 第４属性バイト（属性４）
属性４はＢＥＡＲ情報、正および負のオフセット・フラグ（セクション１．４．５．１参照）、ならびに将来の使用のために予約された１ビットを含む。表Ａ３２に示されるように、この属性は末尾ＬＲＰについて用いられる。
【０１８７】
【０１８８】
１．５．６ オフセット
正オフセット（ＰＯＦＦ）および負オフセット（ＮＯＦＦ）は、属性４内の対応するフラグがそれらの存在を示す場合にのみ含まれる。オフセット値を含まないことは０メートルのオフセット値を示す。オフセット値はセクション１．４．５に従って計算され、これらのオフセットのビット用途は表Ａ３３、Ａ３４に示される。
【０１８９】
【０１９０】
【０１９１】
１．６ メッセージ・サイズの計算
位置参照情報のメッセージ・サイズは位置参照情報に含まれるＬＲＰの個数に依存する。位置参照情報には少なくとも２つのＬＲＰが含まれるべきである。また、状態情報を伴うヘッダが必須である。以下の計算と表Ａ３５とはＬＲＰの個数に依存するメッセージ・サイズを示す。
・ヘッダ
１バイト状態
合計：１バイト
・先頭ＬＲＰ
６バイトＣＯＯＲＤ（ｌｏｎ／ｌａｔのそれぞれについて３バイト）
３バイト属性
合計：９バイト
・後続ＬＲＰ
４バイトＣＯＯＲＤ（ｌｏｎ／ｌａｔのそれぞれについて２バイト）
３バイト属性
合計：７バイト
・末尾ＬＲＰ
４バイトＣＯＯＲＤ（ｌｏｎ／ｌａｔのそれぞれについて２バイト）
２バイト属性
合計：６バイト
・オフセット（含まれる場合）
１バイト正オフセット（含まれる場合）
１バイト負オフセット（含まれる場合）
合計：０〜２バイト
【０１９２】
【０１９３】
上記の形式が用いられる方法の特定の例が、図９〜図１２を参照して上述された位置参照情報を参照して以下に提供される。これらの図では３つの位置参照点（ノード(1)、(10)、(15)およびライン(1)〜(3)、(10)〜(11)、(14)〜(15)）が位置を正確に表現するために識別される。位置参照情報は３つの位置参照点で構成され、以下の表Ａ３６はノード(1)、(10)、(15)についての座標を示す。これらのノードは位置参照点に対応するノードである。２進数形式の準備において、この表はまた、相対座標を示す。ノード(1)は位置参照点１に対応し、絶対形式の座標を有するだろう。位置参照点２に対応するノード(10)は位置参照点１に対する相対座標を有するだろう。位置参照点３に対応するノード(15)も相対座標を有するだろうが、ここでは位置参照点２を参照する。
【０１９４】
【０１９５】
相対経度および相対緯度は上記の式Ｅ３に従って計算される。符号化処理のステップ２で計算されるオフセットが表Ａ３７に示される。２進数データにおいて、正オフセットのみが現れるだろう。なぜなら、負オフセットは０であり、オフセットがない場合は０として扱われるだろうからである。
【０１９６】
【０１９７】
以下の表Ａ３８は基底のデジタル地図から計算を通じて各位置参照点についての関連データを収集する。これは機能的道路クラス、道路種別、および対応するラインの方位を含む。２つの連続した位置参照点間のパスに関して必要な情報（最低機能的道路クラスと次の位置参照点への距離）も示される。
【０１９８】
【０１９９】
ＢＥＡＲ属性、ＬＦＲＣＮＰ属性、およびＤＮＰ属性は上述のように決定される。以下の表は２進数データを作成するためのすべての関連情報を保持する。以下の表は物理データ形式に従って２進数データの概要を説明する。
・状態タイプ：表Ａ３９を参照。
・ＬＲＰ１： 表Ａ４０〜Ａ４４を参照。
・ＬＲＰ２： 表Ａ４５〜Ａ４９を参照。
・ＬＲＰ３： 表Ａ５０〜Ａ５３を参照。
・オフセット：表Ａ５４を参照。
【０２００】
【０２０１】
【０２０２】
【０２０３】
【０２０４】
【０２０５】
【０２０６】
【０２０７】
【０２０８】
【０２０９】
【０２１０】
【０２１１】
【０２１２】
【０２１３】
【０２１４】
【０２１５】
【０２１６】
完全な２進数データストリームは２４バイトの長さを有し、以下のもので構成される（左から右へ、そして上から下へのバイトとして並ぶ）。
【０２１７】
【特許請求の範囲】
【請求項１】
道路ネットワーク内の連続したパスを符号化する方法であって、前記パスはデジタル地図に完全に表されるとともに、前記デジタル地図内に存在して連続に順序付けされたラインとセグメントとのうちの少なくとも一方のパス・リストとして表現可能であり、前記方法は、
(i)‐前記パス・リストに最初に現われるライン又はセグメントか、若しくは前記最初のライン又はセグメントの開始ノードが人工的である場合に、実在の開始ノードを有する前記デジタル地図に現われ、場合によっては他の人工ノードを介して前記最初のライン又はセグメントに直接につながる最初のライン又はセグメントと、
‐前記パス・リストに同様に現われる最も直近に識別された逸脱ライン又は逸脱セグメントと
のうちの１つである開始場所を経路探索リストに記憶する工程と、
(ii)前記開始場所を含み、前記開始場所の開始ノードから前記パス・リスト内の最後のライン又はセグメントの終点ノードへの前記デジタル地図内のパスを決定する工程であって、前記パスはアルゴリズムに従って決定される、工程と、
(iii)そのように決定された最短パスを識別のために前記パス・リストに対して比較し、識別できない場合に、前記パス・リストの一部であり、前記デジタル地図内の交差点を表す開始ノードを有するものの、前記パス・リストに最初に現われるライン又はセグメントではない少なくとも１つの逸脱ライン又は逸脱セグメントを識別し、このような逸脱ライン又は逸脱セグメントが前記パス・リストに現われる最後のライン又はセグメントの終了ノードで終わらない場合に、前記逸脱ライン又は逸脱セグメントを用いて工程(i)を繰り返す工程と、
(iv)前記パス・リスト内の最後のライン又はセグメントが既に記憶されていない場合に前記経路探索リストに記憶する工程と
を有することを特徴とする方法。
【請求項２】
前記パスの決定に用いられる前記アルゴリズムは最短パス・アルゴリズムであることを特徴とする請求項１に記載の方法。
【請求項３】
前記工程(iii)において、前記逸脱ライン又は逸脱セグメントが前記パス・リストに現われる最後のライン又はセグメントの終了ノードで終わり、且つ前記最短パスにおける最後のライン又はセグメントの先行物が前記パス・リストに現われる最後から２番目のライン又はセグメントに一致しない場合に、第２の逸脱ライン又は逸脱セグメントが、交差点に一致する前記パス・リストに現われる最後のノードから広がるライン又はセグメントとして例外的に識別されることを特徴とする請求項１に記載の方法。
【請求項４】
結果として生じる経路探索リストを２進数又はＸＭＬのようなマークアップ言語で表現される機械で読み取り可能な形式に変換する工程をさらに有することを特徴とする請求項１乃至３の何れか１項に記載の方法。
【請求項５】
連結、変換、転置、及び結果として位置参照点の有効な順序リスト又はその機械で読み取り可能な表現を生じる有効性チェックのうちの少なくとも１つを行う工程をさらに有することを特徴とする請求項１乃至４の何れか１項に記載の方法。
【請求項６】
前記連続したパスを表す前記パス・リスト内の各項目を有効性について分析し、関連する観点で前記パス・リストが有効でない場合に、例外を提起する予備的工程をさらに含むことを特徴とする請求項１乃至５の何れか１項に記載の方法。
【請求項７】
前記有効性チェックは、前記パス・リスト内の最初に記述されたライン又はセグメントの開始ノードと、前記パス・リスト内の最後に記述されたものの終了ノードとのうちの一方又は両方が前記デジタル地図内の実在のノードに一致するかを確立するためのチェックを含み、一致しない場合に、予備的有効性チェックは適切な実在のノードを識別し、それに従って前記パス・リストに追加のライン又はセグメントを含めることによって前記連続したパスを延長し、前記実在のノードと人工ノードとの間の距離を表すオフセットを記憶することを含むことを特徴とする請求項５又は６に記載の方法。
【請求項８】
連続した位置参照点の間に最大距離に関する制約を課す工程をさらに有することを特徴とする請求項１乃至７の何れか１項に記載の方法。
【請求項９】
そのように課される前記最大距離は１５ｋｍであることを特徴とする請求項８に記載の方法。
【請求項１０】
エンコーダにおいて、ターン制限チェック・オプションが使用可能であるかを判定し、使用可能である場合に、前記デジタル地図に識別され、位置を毀損又は危険にさらすか若しくはナビゲートを不能にする可能性のあるターン制限について、符号化が望まれる前記位置を評価し、このようなものが識別される場合に、エラーを返す工程をさらに有することを特徴とする請求項１乃至９の何れか１項に記載の方法。
【請求項１１】
コンピュータに請求項１乃至１０の何れか１項に記載の方法を実行させるためのコンピュータ・プログラム・コードを備えるコンピュータ・プログラム。
【請求項１２】
コンピュータで読み取り可能な記憶媒体に具現化された請求項１１に記載のコンピュータ・プログラム。
【請求項１３】
連続したパス位置を符号化するためのシステムであって、
請求項１乃至１０の何れか１項に記載の方法を実行するエンコーダと、
事前に符号化された位置と、これらの位置を符号化するための以前の試行結果とを記憶するためのデータベースと
を備え、
符号化される位置を受信すると、前記システムは位置又はその一部が前記データベースにすでに記憶されている位置の一部を形成する又は当該位置に等しいかどうかを確立するために前記データベースに問い合わせ、符号化がすでに発行されている場合に以前に符号化された位置又はその一部を返し、若しくはこれに代えて前記連続したパス位置を前記エンコーダへ渡し、この出力は前記連続したパス位置とともに前記データベースに記憶された任意のイベントに含まれることを特徴とするシステム。
【請求項１】
道路ネットワーク内の連続したパスを符号化する方法であって、前記パスはデジタル地図に完全に表されるとともに、前記デジタル地図内に存在して連続に順序付けされたラインとセグメントとのうちの少なくとも一方のパス・リストとして表現可能であり、前記方法は、
(i)‐前記パス・リストに最初に現われるライン又はセグメントか、若しくは前記最初のライン又はセグメントの開始ノードが人工的である場合に、実在の開始ノードを有する前記デジタル地図に現われ、場合によっては他の人工ノードを介して前記最初のライン又はセグメントに直接につながる最初のライン又はセグメントと、
‐前記パス・リストに同様に現われる最も直近に識別された逸脱ライン又は逸脱セグメントと
のうちの１つである開始場所を経路探索リストに記憶する工程と、
(ii)前記開始場所を含み、前記開始場所の開始ノードから前記パス・リスト内の最後のライン又はセグメントの終点ノードへの前記デジタル地図内のパスを決定する工程であって、前記パスはアルゴリズムに従って決定される、工程と、
(iii)そのように決定された最短パスを識別のために前記パス・リストに対して比較し、識別できない場合に、前記パス・リストの一部であり、前記デジタル地図内の交差点を表す開始ノードを有するものの、前記パス・リストに最初に現われるライン又はセグメントではない少なくとも１つの逸脱ライン又は逸脱セグメントを識別し、このような逸脱ライン又は逸脱セグメントが前記パス・リストに現われる最後のライン又はセグメントの終了ノードで終わらない場合に、前記逸脱ライン又は逸脱セグメントを用いて工程(i)を繰り返す工程と、
(iv)前記パス・リスト内の最後のライン又はセグメントが既に記憶されていない場合に前記経路探索リストに記憶する工程と
を有することを特徴とする方法。
【請求項２】
前記パスの決定に用いられる前記アルゴリズムは最短パス・アルゴリズムであることを特徴とする請求項１に記載の方法。
【請求項３】
前記工程(iii)において、前記逸脱ライン又は逸脱セグメントが前記パス・リストに現われる最後のライン又はセグメントの終了ノードで終わり、且つ前記最短パスにおける最後のライン又はセグメントの先行物が前記パス・リストに現われる最後から２番目のライン又はセグメントに一致しない場合に、第２の逸脱ライン又は逸脱セグメントが、交差点に一致する前記パス・リストに現われる最後のノードから広がるライン又はセグメントとして例外的に識別されることを特徴とする請求項１に記載の方法。
【請求項４】
結果として生じる経路探索リストを２進数又はＸＭＬのようなマークアップ言語で表現される機械で読み取り可能な形式に変換する工程をさらに有することを特徴とする請求項１乃至３の何れか１項に記載の方法。
【請求項５】
連結、変換、転置、及び結果として位置参照点の有効な順序リスト又はその機械で読み取り可能な表現を生じる有効性チェックのうちの少なくとも１つを行う工程をさらに有することを特徴とする請求項１乃至４の何れか１項に記載の方法。
【請求項６】
前記連続したパスを表す前記パス・リスト内の各項目を有効性について分析し、関連する観点で前記パス・リストが有効でない場合に、例外を提起する予備的工程をさらに含むことを特徴とする請求項１乃至５の何れか１項に記載の方法。
【請求項７】
前記有効性チェックは、前記パス・リスト内の最初に記述されたライン又はセグメントの開始ノードと、前記パス・リスト内の最後に記述されたものの終了ノードとのうちの一方又は両方が前記デジタル地図内の実在のノードに一致するかを確立するためのチェックを含み、一致しない場合に、予備的有効性チェックは適切な実在のノードを識別し、それに従って前記パス・リストに追加のライン又はセグメントを含めることによって前記連続したパスを延長し、前記実在のノードと人工ノードとの間の距離を表すオフセットを記憶することを含むことを特徴とする請求項５又は６に記載の方法。
【請求項８】
連続した位置参照点の間に最大距離に関する制約を課す工程をさらに有することを特徴とする請求項１乃至７の何れか１項に記載の方法。
【請求項９】
そのように課される前記最大距離は１５ｋｍであることを特徴とする請求項８に記載の方法。
【請求項１０】
エンコーダにおいて、ターン制限チェック・オプションが使用可能であるかを判定し、使用可能である場合に、前記デジタル地図に識別され、位置を毀損又は危険にさらすか若しくはナビゲートを不能にする可能性のあるターン制限について、符号化が望まれる前記位置を評価し、このようなものが識別される場合に、エラーを返す工程をさらに有することを特徴とする請求項１乃至９の何れか１項に記載の方法。
【請求項１１】
コンピュータに請求項１乃至１０の何れか１項に記載の方法を実行させるためのコンピュータ・プログラム・コードを備えるコンピュータ・プログラム。
【請求項１２】
コンピュータで読み取り可能な記憶媒体に具現化された請求項１１に記載のコンピュータ・プログラム。
【請求項１３】
連続したパス位置を符号化するためのシステムであって、
請求項１乃至１０の何れか１項に記載の方法を実行するエンコーダと、
事前に符号化された位置と、これらの位置を符号化するための以前の試行結果とを記憶するためのデータベースと
を備え、
符号化される位置を受信すると、前記システムは位置又はその一部が前記データベースにすでに記憶されている位置の一部を形成する又は当該位置に等しいかどうかを確立するために前記データベースに問い合わせ、符号化がすでに発行されている場合に以前に符号化された位置又はその一部を返し、若しくはこれに代えて前記連続したパス位置を前記エンコーダへ渡し、この出力は前記連続したパス位置とともに前記データベースに記憶された任意のイベントに含まれることを特徴とするシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公表番号】特表２０１１−５２６６７９（Ｐ２０１１−５２６６７９Ａ）
【公表日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願番号】特願２０１１−５１５４１７（Ｐ２０１１−５１５４１７）
【出願日】平成２１年６月２９日（２００９．６．２９）
【国際出願番号】ＰＣＴ／ＥＰ２００９／０５８１３１
【国際公開番号】ＷＯ２０１０／０００７０７
【国際公開日】平成２２年１月７日（２０１０．１．７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
【出願人】（３０７０４３２２３）トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【Ｆターム（参考）】
【公表日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願日】平成２１年６月２９日（２００９．６．２９）
【国際出願番号】ＰＣＴ／ＥＰ２００９／０５８１３１
【国際公開番号】ＷＯ２０１０／０００７０７
【国際公開日】平成２２年１月７日（２０１０．１．７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
【出願人】（３０７０４３２２３）トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【Ｆターム（参考）】
[ Back to top ]