地図データベース管理

マップ データベース管理システムは、ナビゲーション アプリケーション用の空間情報を保存および呼び出すように設計されたソフトウェア プログラムであり、地理情報システムの一種です。特に自動車アプリケーションでは、位置特定とナビゲーションに広く使用されています。さらに、位置情報サービス、アクティブ セーフティ機能、先進運転支援システムなどの新興分野で、ますます重要な役割を果たしています。これらの機能に共通するのは、道路網を記述する情報を含む車載マップ データベースが必要であることです。

マップ データベースを適切に設計すると、大量の地理データの迅速なインデックス作成と検索が可能になります。

地図はグラフとして、または場所とカテゴリの属性を持つオブジェクトの 2 次元配列として保存されます。一般的なカテゴリには、公園、道​​路、都市などがあります。

地図データベースは、道路網とそれに関連する地物を表します。地図提供者は、データベースを作成するための基礎として、道路網のさまざまなモデルを選択できます。通常、このようなモデルは、道路網の基本要素 (ノード、リンク、エリア) とそれらの要素のプロパティ (位置座標、形状、住所、道路クラス、速度範囲など) で構成されます。基本要素は地物と呼ばれ、プロパティは属性と呼ばれます。道路網に関連するその他の情報も含まれており、関心のあるポイント、建物の形状、政治的境界などが含まれます。これは、隣の画像に模式的に示されています。地理データ ファイル(GDF) ^[1]は、このようなモデルの標準化された記述です。

マップ グラフ内の各ノードは、地球の表面のポイントの位置を表し、経度(lon) と緯度(lat) の座標のペアで表されます。各リンクは、2 つのノード間の道路の区間を表し、線分 (道路の直線部分に相当) またはリンクに沿った中間ポイント (シェイプ ポイントと呼ばれる) によって一般的に記述される形状を持つ曲線で表されます。ただし、曲線は、曲線の境界を定義するために、重心 (ポイントまたはノード)、半径、極座標の組み合わせで表すこともできます。シェイプ ポイントはノードと同様に経度緯度座標で表されますが、シェイプ ポイントはノードのようにリンクを接続する目的には使用されません。エリアは、公園、都市、ブロックなどを表す 2 次元の形状で、境界によって定義されます。これらは通常、閉じた多角形によって形成されます。これは、マップ上のオブジェクトが近い境界を持つ必要があることを示す形状であり、最初の頂点が最後の頂点と同じである必要があります。 (例えば、地図上に正方形のオブジェクトをプロットする場合、ポリゴンの頂点には 1、2、3、4、1 の順に番号が付けられます)

データの検証のもう 1 つのポイントは、ポリゴン内のポイントです。これは、ポリゴンの外側にあるポイントを見つけるのに役立ちます。たとえば、都市内の特定の経度と緯度の座標の場合、ポイントがポリゴンと奇数で交差している場合は、ポリゴンの内側にあり、有効なポイントです。そうでない場合は、ポリゴンの外側にあり、無効です。

地図プロバ​​イダーは一般的に、情報交換を目的とした明確に定義され文書化されたファイル形式でデータを収集、集約、提供します。たとえば、Navteqは標準交換形式（SIF）^[2]とGDFを使用し、Tele Atlasは独自の形式のGDFを使用しています。^[3] これは通常、さまざまな関係者が簡単に解析および解釈できるフィールドで構成されるプレーンテキスト形式（ASCII）です。ポータブル形式であるため、追加、削除、変更を簡単なテキスト編集プログラムで簡単に実行できます。

さまざまなタイプのデータを表すために、少数のレコード タイプが使用されます。各レコード タイプは、固定長またはコンマなどの句読点文字で区切られたフィールドのシーケンスで構成されます。たとえば、リンク エンティティは次の形式のレコードで表すことができます。

type1 はこれをリンク レコード タイプとして定義し、ラベルは、このリンクを他のすべてのリンクと区別するための識別子として機能します。z1 フィールドとz2フィールドは、対応するノードnode1とnode2を共有する他のリンクからのこのリンクの垂直方向の分離を決定します。したがって、たとえば、リンクへの高架は、そのリンクに接続されていないものとして表すことができます。その他のレコード タイプは、住所情報、リンクの形状ポイント、都市と州、興味のあるポイント (POI) などを表すために使用されます。

マップ データベースの交換形式は、実行時にナビゲーション ユニットが使用できるように適切に構成されていません。レコードは任意の順序になっているため検索が難しく、道路名や座標値などのデータはレコード間で繰り返されます。そのため、データベースの内容は、実行時の操作に適したバイナリ形式に再編成されます。

ランタイムフォーマットは通常、独自のものであるため、異なるナビゲーションシステム間での地図の相互運用ができません。しかし、Navigation Data Standard (NDS)と呼ばれる新しいイニシアチブは、自動車メーカー、ナビゲーションシステムサプライヤー、地図データサプライヤーの業界グループであり、カーナビゲーションシステムで使用されるデータフォーマットの標準化を目的としています。^[4] 参加している企業には、TomTom、BMW、フォルクスワーゲン、ダイムラー、ルノー、ADIT、アルパインエレクトロニクス、ナビゴン、ボッシュ、デンソー、三菱、ハーマンベッカー、パナソニック、PTV、コンチネンタルAG、ナブテック、ゼンリンなどがあります。

データベースはナビゲーションプロバイダー^{[5] [6] [7]}によって、少なくとも以下の5つのステップを含むコンパイルプロセスを通じて再編成されます。

1. ネットワークの一貫性を確認します。たとえば、リンクで接続する必要があるすべてのノード ペアにそのようなリンクがあること、また逆に、接続すべきでないすべてのノード ペアに接続リンクがないことを確認します。
2. すべてのエンティティに識別子 (ID) を体系的に割り当てます。
3. エンティティに複数のインデックス セットを適用して、期待どおりにデータベースを検索できるようにします。
4. データ項目 (通り名、座標など) の複数の出現をインデックスで置き換え、各項目の単一のコピーを含むテーブルに格納します。
5. 他の圧縮技術を適用して、データベースの全体的なサイズを縮小します。

ステップ 1 の整合性チェックは、通常、非常にインタラクティブで反復的なプロセスであり、完了するまでに数週間かかる場合があります。この間に、不一致を検出し、調査し、解決する必要があります。

ステップ 2 では、各タイプのエンティティが検出されるたびに、ID が順番に割り当てられるのが一般的です。入力データベースをあるバージョンから別のバージョンに変更すると、すべてのエンティティへの ID の割り当てに影響します。そのため、バージョン間での割り当ての継続性はほとんど期待できません。

ステップ 3 では、適用された各インデックスによって、特定の方法でデータベースをすばやく検索できます。リンクに適用された 1 つのインデックス セットは、リンクの通り名のアルファベット順に並べ替えることができます。リンクに適用された別のインデックス セットは、ルート プランニングを容易にするために、リンクが接続されているノードに従って並べ替えることができます。ノードに適用されたさらに別のインデックス セットは、道路沿いの出現順序に従って並べ替えることができます。これらのケースでは、網羅的な検索の代わりにバイナリ検索を実行でき、検索プロセスを単純なテーブル検索に置き換えることができる場合もあります。

ほとんどのナビゲーション機能では、車両に最新の地図データベースが搭載されていることが重要であり、特にアクティブセーフティに関連する機能では、それが不可欠です。一般的な戦略は、無線チャネルを介して更新情報が利用可能になるとすぐに車両に転送することです。無線チャネルは、Wi-Fiや携帯電話などの双方向のもの、衛星ラジオ、FM サブキャリア、ATSCデータキャストなどのブロードキャストのもの、またはその両方の組み合わせの場合があります。いずれにしても、新しいデータベース全体を送信して既存のバージョンを置き換えることは、サイズが数ギガバイトになる可能性が高いため、非現実的または非常に非効率的です。

代わりに、既存のデータベースに加えられた変更に関連する情報だけを転送することが望ましいです。大きな問題は、マップ データベースのコンテンツに変更を加えると、通常、コンパイル プロセス中に割り当てられたすべてのエンティティ ID とインデックスが変更されることです。これらの新しい ID とインデックスはコンパイルされたデータベース全体に浸透するため、増分コレクションはデータベースの大部分を構成する可能性があります。この困難を克服するために、1) オンボード コンパイラ、2) ルックアサイド ストア、3) 地理タイルという 3 つのアプローチが採用されています。

この場合、データベースの交換形式に加えられた基本的な変更が車両に送信されます。このような変更は、追加、削除、および置換で構成されるトランザクション形式で表されます。これらの変更は、交換形式の既存のオンボード データベースに適用されます。オンボード データベースの交換形式は、個別に保存することも、必要に応じてランタイム形式を「逆コンパイル」して生成することもできます。その後、結合されたデータベースがコンパイルされ、ID の割り当てとインデックスの適用が行われます。

このオンボード コンパイルは、計算負荷が高く、かなりのメモリを必要とする可能性があります。ただし、整合性チェックと解決はすでに実行されているため、オフボード コンパイルのように対話型で反復的である必要はありません。さらに、オンボード コンパイルはバックグラウンドで実行できるため、計算時間は重要ではありません。

この場合、基本的な変更も車両に送信されますが、ルックアサイド ストアと呼ばれる別のメモリ ロケーションに配置されます。変更もトランザクション形式で表されますが、必ずしも交換形式またはランタイム形式である必要はなく、任意の便利な形式で表示できます。ナビゲーション ユニットの動作中、メイン データベースにアクセスするたびに、ルックアサイド ストアが検索されます。アクセスされたデータに関連するトランザクション (変更) が適用されます。

もちろん、ルックアサイド ストアを調べてデータベース アクセスごとに変更を適用する必要性により、ナビゲーション アルゴリズムが複雑になり、計算時間が長くなります。ただし、これによりオンボード コンパイラが不要になります。

このアプローチでは、マップ データベースは、マップをモザイク状に分割する比較的小さな長方形の領域 (タイル) に分割されます。タイルのサイズは、1 辺が 1 km 程度です。これらのタイルは個別にコンパイルされるため、すべての ID とインデックスは、適用される特定のタイルに応じて調整されます。データベースの基本エンティティまたは属性の変更によって変更されたタイルは車両に送信され、対応する既存のタイルと置き換えられます。

タイルの置き換えは、オンボード コンパイルやルックアサイド ストアの使用よりもかなり簡単です。ただし、転送には効率的ではない可能性があります。エンティティと属性に対するローカル変更は、その範囲に関係なく、そのエンティティと属性を含むタイル全体の転送が必要です。さらに、1 つのタイル内のエンティティの変更が隣接するタイルのエンティティに影響を及ぼすエッジ効果があります。少数のエンティティ変更でほぼすべてのタイルの転送が必要になる可能性は十分にあり、増分更新の目的が達成されません。これらの問題は、タイルのサイズと更新頻度を選択することで解決できます。

アクティブ セーフティ、ドライバー アシスタンス、位置情報サービスなどのさまざまなナビゲーション機能には、マップ データベースの一部とは見なされないデータが必要であり、マップ プロバイダー以外のベンダーから提供される可能性があります。このようなデータは、メイン データベースのエンティティおよび属性と相互参照する必要があります。ただし、補助データは必ずしもメイン データベースとコンパイルされるわけではないため、相互参照を確立するには、補助データの添付と呼ばれる別の手段が必要です。一般的な 2 つの方法は、機能固有の参照テーブルと汎用参照です。

機能固有の参照テーブルは、参加しているサプライヤが作成したマップ データベースに機能固有のデータを添付する手段を提供します。このようなテーブルは、ロケーション ベースのサービス、アクティブ セーフティ、または高度なドライバー アシスタンスを含む特定の機能または機能クラスをサポートするために共同で作成されます。通常、テーブルは、特定のタイプのマップ要素 (リンク、交差点、興味のある場所など) のリストと、識別属性 (通りの名前、経度/緯度座標など) で構成されます。さらに、テーブル内の各エントリには、一意の識別子が割り当てられます。テーブル内のエントリのセットは、通常、すべての関係者の合意によって選択されます。実際問題として、結果は、マップ データベースで使用可能な特定のタイプの要素の小さなサブセットを表し、アプリケーション領域にとってより重要な要素で構成されます。テーブルが作成された後、テーブル エントリに対応するマップ データベース内の要素を決定して相互参照するのは、参加している各サプライヤのタスクです。

広く使用されている例としては、交通データを参照するための位置コードテーブル用のTMC標準があります。TMCはTraffic Message Channelの略で、^[8]ラジオデータシステム（RDS）の一部であり、商用FM放送信号のサブキャリア変調として実装されています。TMCテーブルは主に、他の道路との交差点に対応する主要道路沿いのポイント位置への参照を提供します。テーブルエントリは、コンテキスト情報（地域、道路と道路区間、交差点の名前など）とおおよその経度/緯度座標の両方を使用してポイント位置を識別します。

テーブル内のエントリに割り当てられる識別子は 16 ビットの整数であるため、範囲は 65536 の値になります。これは世界をカバーするには少なすぎるため、国ごと、または国内の各地域ごとに個別のテーブルが作成されます。特定の大都市圏では、フリーウェイ、幹線道路、および一部の主要道路に沿った交差点のみが含まれます。これは、次のデトロイト大都市圏の図に示されています。この範囲は、使用頻度の高い道路の交通アドバイス情報を提供することを目的としています。一方、交通量に基づくルート プランニングでは、主要道路のすべてまたはほとんどをカバーする必要があるため、現在作成されている TMC ロケーション コード テーブルでは十分にサポートされていません。

汎用参照とは、マップ マッチングの形式で参照情報を検出することにより、任意のマップ データベースにデータを添付する試みです。機能固有のデータ項目は、特定のマップ データベース内の対応するマップ要素に近似している可能性が高いポイント、リンク、エリアなどの要素に割り当てられます。マップ データベースの検索は、最適なものを求めて行われます。検索プロセスを強化するために、各要素に隣接する要素が戦略的に追加され、それぞれの場合に正しいソリューションが確実に見つかるようになります。たとえば、マップ要素が 2 つの交差点を接続するリンクである場合、検索のために 1 つまたは両方の交差点を追加できます。うまくいけば、これにより誤った一致が発生する可能性が低くなります。この手順は非常にヒューリスティックですが、Agora と呼ばれる提案された標準では、追加する隣接する要素を選択するための戦略が概説されています。

^{ActMAP (Actualize Map) [9]}と呼ばれるヨーロッパのコンソーシアムは、(彼らの言葉によれば)「既存の地図データベース コンテンツを更新し、車載デジタル地図に情報を動的に添付できるようにする標準化されたメカニズムを開発しています」。ActMAP コンソーシアムは、ERTICO (コーディネーター)、BMW、CRF Fiat Research Centre、DaimlerChrysler、Navigon、Navteq、Tele Atlas、および Siemens VDO Automotive で構成されています。彼らは作業のほとんどを終え、いくつかのレポートを公開し、標準化のためにISO委員会 TC204 WG3 に提出しました。彼らのレポートは、このプロジェクトの作業の良い出発点および参考資料として役立ちます。彼らのレポートが取り上げる重要な問題は、複数の地図サプライヤが独自のフォーマットを使用し、複数のデータ サプライヤと車載地図の複数のバージョンが組み合わさった複雑さに対処することです。彼らはこれを、 XMLで表現され、ISO 標準GDF 4.0の概念に基づいたオープンな中間マップ フォーマットを使用して解決しています。サプライヤのデータベースへのすべての変更は、まずこの中間形式に変換され、サーバーに保存され、その後、個々の車両内で使用される各形式に変換されます。各車両にはマップ サプライヤからの「ベースライン」マップがあり、このベースラインは更新されるほとんどのフィーチャの参照識別子 (マップ セグメント ID など) を定義していると想定されています。ベースラインに参照識別子がないフィーチャについては、AGORA と呼ばれる提案された標準で説明されているように、マップ マッチングを使用してヒューリスティックに検出される「汎用」参照を使用することを提案しています。

ActMAP で直接対処されていない大きな問題は、サプライヤのマップ データベースの新しいバージョンごとに、すべての参照 ID がコンパイル プロセスによって再割り当てされるのが通常で、これにより以前のバージョンの ID との対応が失われることです。これにより、増分更新を使用して以前のバージョンからマップ データベースの新しいバージョンを生成する機能が著しく妨げられます。ActMAP で解決されていないもう 1 つの問題は、道路セグメントのサブセクション (カーブ、丘、操縦レーンなど) を参照して特徴付け、更新できないことです。

• 自動車ナビゲーションシステム
• 最短経路問題、地図データベースからナビゲーション ルートを取得するために使用される問題とアルゴリズムのクラス。
• 地理データベース
• 地理情報システム
• 全地球航法衛星システム
• インテリジェント交通システム
• 地図
• ナブテック
• 興味のある場所
• オブジェクトリレーショナルデータベース
• オープン地理空間コンソーシアム
• ロボットマッピング
• テレアトラス
• テレマティクス