(57)【要約】【課題】移動体のための３次元ビジュアルナビゲーションにおいて、どのような視点からも高度なディテールで移動体観察者の周囲環境をリアルにレンダリングし、さらにルートガイダンスや表示されるオブジェクトに適したリファレンス情報などのようなナビゲーション支援も提供する。【解決手段】移動体の瞬時のポジションを計算するロケーション計算ユニットと、計算された瞬時のポジションからビュー円錐台を決定するビューポイントコントロールユニットと、決定されたビュー円錐台に対応づけられた地理オブジェクトデータを取得するために地理データベースと共働し、取得した地理オブジェクトデータを編成するシーングラフを生成するシーングラフマネージャと、このシーングラフをリアルタイムにグラフィックでレンダリングするシーングラフレンダラとが設けられている。【選択図】図３
2004213663.tif 000002
【特許請求の範囲】
【請求項１】
階層データ構造において、
システムのメタデータを格納するリソースインデックスフォーマットと、システムの実際のデータを格納するディテールレベルフォーマットとを有しており、前記実際のデータは要求に応じてロードされることを特徴とする階層データ構造。
【請求項２】
前記システムには移動ナビゲーションシステムが含まれる、請求項１記載の階層データ構造。
【請求項３】
前記リソースインデックスフォーマットには階層型で配置されたシステムのポジション情報が含まれている、請求項１記載の階層データ構造。
【請求項４】
前記リソースインデックスフォーマットにはタイルと境界ボックスの情報から成るシーケンスが含まれている、請求項１記載の階層データ構造。
【請求項５】
前記ディテールレベルフォーマットには、多数のディテールレベルのリソースオブジェクトフィーチャと該リソースオブジェクトフィーチャを指すポインタが含まれている、請求項１記載の階層データ構造。
【請求項６】
前記実際のデータはリソースオブジェクトフィーチャのアクセスを最適化するよう配置されている、請求項５記載の階層データ構造。
【請求項７】
ナビゲーションシステムにおいて、
少なくとも１つのリソースオブジェクトと、
システムおよび該少なくとも１つのリソースオブジェクトのポジションに対応づけられたメタデータが設けられており、該メタデータは階層状に配置されており、
前記少なくとも１つのリソースオブジェクトに対応づけられた実際のデータが設けられていることを特徴とする、
ナビゲーションシステム。
【請求項８】
前記のメタデータと実際のデータは別個に配置されている、請求項７記載のナビゲーションシステム。
【請求項９】
前記メタデータはリソースインデックスフォーマットで配置されており、前記実際のデータはディテールレベルフォーマットで配置されている、請求項８記載のナビゲーションシステム。
【請求項１０】
前記ディテールレベルフォーマットには少なくとも１つのリソースオブジェクトのフィーチャが複数のディテールレベルで含まれている、請求項９記載のナビゲーションシステム。
【請求項１１】
ナビゲーションシステムにおいて、
少なくとも１つのリソースオブジェクトと、
システムの各部分間の階層関係ならびに該システムと少なくとも１つのリソースオブジェクトとの間の階層関係を記述するメタデータと、
少なくとも１つのリソースオブジェクトを記述する実際のデータが設けられており、
前記のメタデータと実際のデータは別個に配置されていることを特徴とする、
ナビゲーションシステム。
【請求項１２】
ビュー円錐台に対応づけられたタイルの識別情報をアクセスする方法において、
ＲＩＦデータ構造フォーマットに従いタイル識別情報を階層的に編成するステップと、
タイル識別情報に対して、ビュー円錐台に対応づけられたロケーションパラメータを含む問い合わせを出すステップと、
該ロケーションパラメータにマッチしたタイル識別情報を見つけるためにＲＩＦデータ構造をサーチするステップと、
見つけ出されたタイル識別情報にアクセスするステップとを有することを特徴とする方法。
【請求項１３】
ＲＩＦデータ構造はファイルロケーションフィールド、境界ボックスフィールド、タイルフィールドおよび複数の子フィールドを含む、請求項１２記載の方法。
【請求項１４】
前記複数の子フィールドは再帰的であり、各子はそれぞれさらに別の境界ボックスフィールド、さらに別のタイルフィールドおよびさらに別の複数の子フィールドを含む、請求項１３記載の方法。
【請求項１５】
ビュー円錐台に対応づけられたタイルのイメージデータをアクセスする方法において、
ＲＩＦデータ構造フォーマットに従いタイル識別情報を階層的に編成するステップと、
ビュー円錐台に対応づけられているロケーションパラメータを使用して前記タイル識別情報を取得するステップと、
該タイル識別情報をＬＯＤファイルに対するインデックスとして使用するステップとを有しており、該ＬＯＤファイルはタイルイメージデータの格納ロケーションを表すことを特徴とする方法。
【請求項１６】
前記ＬＯＤファイルは複数のレベルフィールドと複数のタイルフィールドとタイルデータフィールドとフィーチャデータフィールドを含む、請求項１５記載の方法。
【請求項１７】
前記タイル識別情報は前記タイルデータフィールドのサブフィールドであり、前記タイルデータフィールドはタイルイメージデータを有するフィーチャデータフィールドに対するポインタを含んでいる、請求項１６記載の方法。
【請求項１８】
前記ＬＯＤファイルのタイルデータフィールドはイメージ分解能レベルを表すディテールレベルを含む、請求項１６記載の方法。
【請求項１９】
前記イメージデータは、衛星イメージと建物構造とディジタルエレベーションモデルとロードマップデータベースのうちの少なくとも１つを含む、請求項１５記載の方法。
【請求項２０】
前記タイルイメージデータは、第１の分解能をもつ第１のイメージと第２の分解能をもつ第２のイメージを有する、請求項１５記載の方法。
【請求項２１】
前記タイルイメージデータの第１および第２の分解能に対し第１および第２の混合係数を割り当てるステップと、
前記第１のイメージと第２のイメージをそれらの個々の第１および第２の混合係数によって乗算した結果の重みづけられた和を計算するステップと、
第１および第２のイメージの重みづけられた和に基づきマルチ分解能イメージを生成するステップとを有する、
請求項２０記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はナビゲーションシステムに関する。さらに詳しくは本発明は、移動体ナビゲーションのために地理的に参照されるデータを視覚的に表示するためのシステムおよび方法に関する。これにはグラフィックランドマークオブジェクトを要求に応じてロードする階層的方法と、局所的な地理的周囲環境をいっそう効率的かついっそう精密に描画するためのマルチ分解能イメージ合成方法に関する。
【背景技術】
【０００２】
定位置の観察者の視野で（観察者により選択されたある特定の視点から）局所的な地理的環境の外観を精密に視覚的にレンダリングするためにコンピュータグラフィックソフトウェアを使用すること自体そもそも難しい課題であり、その理由は観察者の視点に応じてシーンを再構成する問題に加えて、あるシーンの様々な構造やグラフィックスのディテールを精確にシミュレートするのが難しいからである。それにもかかわらず、現在開発中の最新のビジュアルナビゲーションシステムはグラフィックソフトウェアに対しさらにいっそう高い要求を課している。その目的は、ナビゲート支援として用いるために移動中の観察者の視覚的な周囲環境を精確にシミュレートすることである。たとえば車両内のドライバなどのような移動中の観察者の局所的な地理的周囲環境をリアルタイムで描画するレンダリングソフトウェアを使用することが、定位置の観察者の周囲環境のレンダリングよりもはるかに難しいのは明らかである。その理由は、観察者のロケーションが変わるとその視野範囲内の地理上のオブジェクトおよびそれらのオブジェクトの外観が変化し、それによって連続的に更新を行うメカニズムが必要になるからであり、このメカニズムによって新たなグラフィックオブジェクト（局所的な「関心地点 point of interest」）、構造、特徴、視界ならびにその他のリファレンスデータをただちにダウンロードして精確にレンダリングし、ナビゲートされる局所的な周囲環境に関する情報を提供できるようにする必要がある。
【０００３】
現在一般にいくつかのビジュアルナビゲーションシステムによればユーザの入力をベースとしたリアルな周囲環境を３次元で視覚化しているけれども、それらのシステムは移動体のナビゲーションをサポートしておらず、したがってナビゲーション支援用のルートガイドアプリケーションを提供していないし、あるいはレンダリング可能な視点または表示可能なグラフィカルな特徴項目の点に関して制限されている。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
したがって本発明の課題は、自動車ナビゲーションシステムまたはパーソナルディジタルアシスタント（ＰＤＡ）などのようなモバイルユニットのためのビジュアライゼーションシステムにおいて、どのような視点からも高度なディテールで移動体観察者の周囲環境をリアルにレンダリングし、さらにルートガイダンスや表示されるオブジェクトに適したリファレンス情報などのようなナビゲーション支援も提供することにある。
【課題を解決するための手段】
【０００５】
上記の課題を解決するため本発明によれば、移動ユニットのために３次元ビジュアルナビゲーションを行うシステムが提供される。このシステムには、移動ユニットの瞬時のポジションを計算するロケーション計算ユニットと、移動ユニットの瞬時のポジションに基づきビュー円錐台を決定するビューポイントコントロールユニットと、少なくとも１つの地理データベースと共働するシーングラフマネージャと、シーングラフを３次元描画としてリアルタイムにグラフィックでレンダリングするシーングラフレンダラとが含まれている。この場合、シーングラフマネージャはビュー円錐台に対応づけられたグラフィックオブジェクトデータを少なくとも１つの地理データベースから取得し、取得した地理オブジェクトデータを編成するシーングラフを生成する。
【発明を実施するための最良の形態】
【０００６】
描画のリアリズムを高めるため、本発明によればビュー円錐台に適した種々の分解能のイメージを混合する方法が提供され、これによって結果として得られる描写において滑らかでなく急峻な変化が生じるのが抑えられ、さもなければこのような変化は移動ユニットが描画された地理エリアに向かって近づいたり、あるいはそこから遠のいたりしたときに引き起こされてしまう。
【０００７】
これに加えてナビゲーションのビジュアライゼーションの効率を高めるため本発明によればさらに、地理的なランドマークオブジェクトまたはＰＯＩ（Points of Interest 関心地点）に関する情報の格納およびランタイムアクセスのためのデータ構造も記述される。このデータ構造により、ビュー円錐台および／またはユーザリクエストに基づいてオブジェクトを要求に応じてロードすることができる。さらにこのデータ構造によってロード時間、所要メモリ、処理要求ならびにディスプレイレンダリングリソースを最小限に抑えることができ、このことは移動ユニットのユーザに見えるおよび／または関心のあるオブジェクトだけをシステムが要求に応じてダイナミックにロードできるようにしたことによって達成される。
【実施例】
【０００８】
本発明によるシステムにより、移動体のナビゲーション、オリエンテーションならびにリファレンスのため地理エリアを任意の視点から３次元グラフィックスでビジュアライゼーションするシーケンスが生成される。グラフィックビジュアライゼーションまたはレンダリングには、局所的な地理情報を得ることのできるあらゆる形式の表現を含めることができる。そのようなデータには（以下のものに制約されるわけではないが）衛星や空中からのビューイメージまたは地上におけるビューイメージ、ディジタルロードマップ、建物の幾何学的モデル、風景の構造的記述を含めることができるし、さらにはガソリンスタンドやホテルなどのような描写周囲環境における特徴項目や建物を記述するあらゆる種類の識別情報、あるいは交通情報や天候条件ならびに日照時間などのようなダイナミックなデータを含めることもできる。
【０００９】
図１ａおよび図１ｂには、局所的な周囲環境の変化をレンダリングするために情報パラメータをどのように使用するのかが観察者の視点（配向ないしはオリエンテーション）とともに示されている。図１ａの場合、「北」に向いた観察者５はビジョンＡの２次元フィールドをもっており、これはオブジェクト７，８，９を含むほぼ円錐形のエリアである。ビジョンＡのフィールドにより３次元の「ビュー円錐台」が決定され、これには観察者が知覚可能な３次元スペースがすべて含まれている。ビュー円錐台１５内の各オブジェクトは、遠近法ないしは透視画法とヒューマンビジョンとグラフィック描画の周知の規則に従い（平面Ａ′−Ａ″で表された）２次元ビュー上に投影される。観察者５が小さい角度で「西」に向きを変えたとき観察者のビュー水平線によって、ビジョンＡフィールドの一部分とオーバラップした新たなビジョンＢフィールドが取り囲まれ、変更されたビュー円錐台１６が定義される。新たなビュー円錐台１６には新たなオブジェクト１０が含まれている一方、オブジェクト７は新たなビュー円錐台の外側にあり、もはや見えない。
【００１０】
したがって観察者の向きが変わったときにその周囲環境を適切にレンダリングするために、レンダリングシステムは以前にはレンダリングされていなかった（オブジェクト１０に関する）新たなデータを取得してレンダリングする必要があり、さらに以前には取得されておりレンダリングされていた（オブジェクト７に関する）データを除く必要がある。このようにしてシステムは連続的な流れの中で、新たな情報をダウンロードし「古い」データを取り除くことになる。地理的グラフィックデータ量は一般に、たいていのビジュアルナビゲーションシステム用のオンボードメモリリソースの容量をはるかに上まわるので、オフボードデータベースリソースへ高速かつ効率的にアクセスできるようにすることがシステムにとって不可欠であり、そのようにすることで非常に広範囲にわたって観察者の見たものとできるかぎり整合する連続的なシーケンスをリアルタイムにレンダリングするために、新たなデータを即座にダウンロードすることができるようになる。高度なリアリズムを達成するためにビジュアライゼーションシステムは毎秒６０回に及ぶ更新レートでビジュアライゼーションをアップデートし、これは人間の目にシームレスかつ即座に現れる変更を生成するのにほぼ十分である。
【００１１】
図２ａ、図２ｂ、図２ｃには、観察者が描写されたルートに沿って移動したときの大都市の周囲環境に対する３つのシーケンシャルな３次元のレンダリングが示されており、これには本発明によるビジュアルナビゲーションシステムが観察者の動きをどのように考慮するのか、それに従いビジュアライゼーションをどのように更新するのかが示されている。図２ａには、緑色の三角形で表されたモバイルユニット２００のロケーションをベースとしたある大都市エリアの１シーンの俯瞰図レンダリング "helicopter" view rendering が描かれている。図示されているように自動車に組み込み可能なモバイルユニットは、道路２０１に沿って前景の（左側に示された）建物２０３，２０４と（右側に示された）建物２０５との間を移動して橋に近づいていく。この描写には、この橋を"James Monroe"橋と同定するリファレンステキストも含まれている。複数の橋を含む背景セクション２０７は橋２１５の遠端に位置している。地理上の北の方角を指す黄色い三角形のコンパスが、モバイルユニット２００の真上の最上部に示されている。さらに事前に選択された目的地までの提案ルートが青い曲線２１０として表されている。
【００１２】
モバイルユニット２００は提案ルート２１０に沿って橋２１５に向かって前進し、図２ｂに表されているように局所的な周囲環境のグラフィックレンダリングが僅かに変化している。この図からわかるようにモバイルユニット２００の描出は前進しており、背景セクション２０７が僅かに大きくなっていて、建物２０３〜２０５も遠近法ないしは透視画法の規則に応じて比例して拡大している。図２Ｃに示されているようにモバイルユニットはさらに橋２１５に向かって前進し、前景２０３〜２０５と背景２０７の建物はさらに拡大している。これに加えて建物２０５の一部分は以前は視野から隠されていたけれどもいまや姿を現し、建物２０３は姿を消し、このようにして観察者がルート２１０に沿って前進したときに見えるであろうものがシミュレートされる。
【００１３】
図３には、本発明の実施形態による先進的な３次元ビジュアライゼーションのためのナビゲーションシステムのブロック図が示されている。ナビゲーションシステム２５には、モバイルユニットと同じ場所に配置されたオンボードコンポーネント３０と、地理データベース（"geo-database"）６１，６２などのように遠隔配置されたオフボードコンポーネントの双方が含まれている。なお、地理データベース６１，６２は２つの別個のユニットとして描かれているけれども、それらが同じ場所または別の場所に配置されナビゲーションシステムのオンボードコンポーネント３０からアクセス可能な任意の個数のデータベースを表すものであるのは自明である。地理データベース６１，６２には様々な地理エリアに関する大量のデーが含まれており、これにはマップ情報、地理的および構造的なグラフィック情報ならびに識別情報が含まれている。ただしこれに対する代案として地理データベース各々に、他のデータベースに物理的に格納されているグラフィック情報に関する参照またはメタデータだけを含めるようにしてもよい。このようにすればある特定のデータベースをその他のデータベースをアクセスするためのディレクトリサーバとして機能させることができ、ある特定の地理エリア内に位置する所定のタイプのオブジェクトたとえばレストランなどのような情報を提供するために、効率的な問い合わせを行うことができるようになる。次に、データに対する能率的なアクセスのために地理データベースのメタデータを使用することについて詳しく説明する。
【００１４】
ビジュアルナビゲーションシステム２５にはロケーション計算ユニット３５が含まれており、これはローカルメモリに格納され（観察者のポジションにあるものとする）モバイルユニットのマイクロプロセッサ上で実行されるプログラムとしてインプリメントすることができる。ロケーション計算ユニット３５はポジションセンサ４０から入力を受け取り、それらの入力情報に基づきデカルト座標（ｘ，ｙ，ｚ）空間内でモバイルユニットの瞬時のポジション（座標）を計算する。１つの実施形態によればポジションセンサ４０には、「絶対的」ポジション情報を供給するＧＰＳ受信機と、直線加速度と角速度を供給する慣性センサの双方が含まれており、直線加速度と加速度からは積分により「相対的」ポジション情報を計算することができる。これに対する代案としてまたはこれに加えて、ポジションセンサ４０に車輪速度センサなどのような走行距離センサを設けてもよい。回転運動に応答する適切な慣性センサを装備すれば、ロケーション計算ユニットは瞬時の配向を計算することもできる。
【００１５】
ロケーション計算ユニット３５はモバイルユニットの計算されたポジション（および場合によっては配向）をビューポイントコントロールユニット４５へ供給し、このユニットはポジション情報と配向情報を使用してレンダリングすべきビュー円錐台の境界を決定する。ビューポイントコントロールユニット４５はユーザ入力モジュール５０およびルート計算モジュール５２の作用を受け、そこから入力を受け取り、これによって機能強化が得られる。たとえばキーパッドやボタンコントロールなどのユーザ入力モジュール５０を介して、ビジュアライゼーションシステムのユーザはビューモードを変更してズームイン／ズームアウトすることができるし、あるいは観察ピッチ角度を変更することができる。これに加えてユーザは、ビジュアライゼーションのための様々なロケーションと配向パラメータを指定する目的で、ユーザ入力５０をロケーション計算ユニット３５に対し優先させることができる。
【００１６】
また、ユーザはユーザ入力５０を介して観察ビューポイントモードを選択することもできる。１つのモードの場合、レンダリングされるビューポイントによりヘリコプタービュー helicopter view すなわち俯瞰を表すことができ、このビューはヘリコプターが自動車を追跡するようなやり方で、まえもって決められた所定の距離と角度でモバイルユニットのロケーションを追従する。別のモードの場合にはビューポイントにより、バーチャルシーンが観察者の眺めるシーンと整合するようモバイルユニットのポジションおよび機首方位をそのまま反映することができる。この場合、選択されたモードによってビューポイントコントロールユニット４５により計算されたビュー円錐台に作用が及ぼされる。
【００１７】
（図示されているように）ルート計算モジュール５２がシステムにインストールされていれば、選択されたルートに沿って判断ポイント（交差点など）のようなルート情報を与えることができる。ユーザ入力５０を介してプレビューモードが選択されると、ルート計算モジュール５２からビューポイントコントロールユニット４５への判定ポイント情報の伝送によって、接近する判定ポイントへ向かうビューポイントをトリガすることができ、そのようにすれば接近するルートセクションのビジュアライゼーションが、移動ユニットがそのセクションに到着する前にプレビューとしてユーザに表示されるようになる。
【００１８】
ビューポイントコントロールユニット４５が現在選択中のビューモードに従いビュー円錐台を決定した後、ビュー円錐台座標がシーングラフマネージャモジュール５５に供給され、これによってデータストレージオブジェクトが作られてアクセスが行われる。シーングラフマネージャモジュール５５は、「シーングラフ」と呼ばれる現在のシーンに描かれるべきオブジェクトのすべての構造化された記述を保持する。シーングラフマネージャ５５は、ビューコントロールユニット４５から受け取ったビュー円錐台に基づき関心地理エリアを決定し、その後、この地理エリア内に位置するオブジェクトについて地理データベース６１，６２に問い合わせる。新たなオブジェクトがシーングラフに組み込まれる一方、関心地理エリア内にもはや位置していないオブジェクトはシーングラフから取り除かれる。ユーザ入力モジュール５０を介して入力されるユーザ入力を、シーングラフマネージャ５５がシーングラフ中に含んでいるオブジェクトのタイプをフィルタリングしたり選択したりするために使用することができる。たとえばユーザは、レストランだけしか描写されないように指定することができる。このときシーングラフマネージャは問い合わせを行い、その判定基準にマッチするオブジェクトをシーングラフに加える。これに加えてシーングラフには、移動ユニット自身を表すオブジェクトが連続的に含まれる。
【００１９】
ロード時間、所要メモリ、処理要求ならびにリソースをレンダリングする表示を最小限に抑える目的でシーングラフマネージャ５５は要求に応じて、ユーザが見ることのできるおよび／またはユーザに関心のあるデータストレージオブジェクトのみを、および固有のディテールレベルに関連するデータストレージオブジェクトのみを、地理データベース６１，６２からダイナミックにロードすることができる。この情報を得るために地理データベース６，６２に問い合わせを行う目的で、シーングラフマネージャ５５はオブジェクトデータのオンデマンドロードのための階層的方法を採用しており、これは効率的なアクセスができるようオブジェクトデータを編成するために特別に定義されたデータ構造を使用する。
【００２０】
本発明の１つの実施形態によれば、ランドマークオブジェクトをオンデマンドでロードするためのガイドとして２つのデータ構造を使用することができる。１つめのデータ構造はリソースインデックスファイル Resource Index Fileあるいは略してＲＩＦファイルと呼ばれ、これにはランドマークオブジェクトのメタデータ "meta-data" を格納することができる。２つめのデータ構造はディテールレベルファイル Level of Detail File あるいは略してＬＯＤファイルと呼ばれ、これにはランドマークオブジェクトに関する「実際のデータ」を多数のディテールレベルで格納することができる。ＲＩＦファイルおよび／またはＬＯＤファイルを、たとえば記憶媒体および／またはコンピュータメモリに記憶させることができる。
【００２１】
ＲＩＦファイルに格納されているメタデータは、特定のビューポイントにおいてどのリソースを見えるようにするかの決定ならびにそのディテールレベルの決定にあたりシーングラフマネージャを支援することができる。メタデータのサイズを実際のデータに比べて小さくすることができる。したがってメタデータを実際のデータから分離することにより、所要メモリ、プロセス要求ならびにアプリケーションの最初のスタートアップ時間を著しく減らすことができる。なぜならば実際のデータをそれが要求されるまでロードする必要がないからである。たとえばナビゲーションシステムの初期化フェーズ中にＲＩＦファイルを読み込んで、どのリソースをシステムメモリにロードする必要があるのかを、実際のデータをロードすることなく決定できる。ランタイム中、シーングラフマネージャはＲＩＦファイルに格納されている情報に基づきＬＯＤファイルを介して実際のデータにアクセスすることができる（つまりＲＩＦファイルに格納されているメタデータは、実際のデータのどの部分をシステムメモリにロードすべきであるかのディレクトリとして用いることができる）。
【００２２】
ＬＯＤファイルに格納されている実際のデータによれば、多様な分解能でシステムのリソースに関する情報を表すことができる。一般に実際のデータをリーフノードとして階層ツリー構造の中間レベルではないレベルにおいてしか格納できない慣用のシステムとは異なり、ＬＯＤファイルによれば中間ノードにもデータを格納することができる。このようにして階層ツリー構造によれば、所定のビューポイントコンフィギュレーションにおいて特定の分解能に関して要求されたデータをいっそう選択的にロードできることから、マルチ分解能情報をアクセスするためにいっそう適した構成が得られる。たとえば１００００ｆｔのビューポイントにおける１００ｍの分解能構造を１ｍの分解能よりもいっそう迅速に選択することができる。その理由は、データの構成ゆえに不必要な移動を回避できるからである。このように階層ツリー構造のすべてのレベルの中に分散するようデータを配置させることにより、要求された分解能に対しいっそう好適かつ効率的なデータアクセスを達成することができる。
【００２３】
図４ａにはランドマークオブジェクト１０１〜１０５の抽象表現が示されており、これは破線１１０により区切られた２次元のエリア内に地理的に分散されている。この境界内のエリアには座標Ｘ，Ｙ，Ｘ′，Ｙ′が引かれている。詳しく説明すると、座標ＸとＹは互いに交差して境界内エリア１１０は４つの象限に分けられており、つまり第１象限Ｉ、第２象限ＩＩ、第３象限ＩＩＩ、第４象限ＩＶに分けられている。座標Ｘ′，Ｙ′は座標Ｘ，Ｙと交差しており、これにより４つの象限のうちの２つが分割されて部分象限が形成されている。たとえば座標Ｙ′は座標Ｘと交差して、象限ＩＩＩが部分象限ＩＩＩ１と部分象限ＩＩＩ２に分割されている。座標Ｘ′は座標Ｙと交差して、象限ＩＶが部分象限ＩＶ１と部分象限ＩＶ２に分割されている。
【００２４】
境界内エリア１１０を象限Ｉ〜ＩＶと部分象限ＩＩＩ１，ＩＩＩ２，ＩＶ１，ＩＶ２に分割することで、ランドマークオブジェクト１０１〜１０５のロケーションをいっそう精密に記述できるようになる。図４ａに示されているように、ランドマーク（地理）オブジェクト１０１は第１象限Ｉ内に配置されており、ランドマークオブジェクト１０２は部分象限ＩＩＩ２に、ランドマークオブジェクト１０３は部分象限ＩＩＩ１に、ランドマークオブジェクト１０４は部分象限ＩＶ２に配置され、さらにランドマークオブジェクト１０５は部分象限ＩＶ１に配置されている。
【００２５】
ランドマークオブジェクト１０１〜１０５のロケーションの記述は、１つの「ルートノード」と複数の「ブランチノード」ならびに「リーフ」をもつ「ツリー」構造として表すことができる。ブランチノードは境界内エリア１１０の空間的分割を表すことができ、リーフはランドマークオブジェクト１０１〜１０５を表すことができる。殊にブランチノードとリーフを階層的に配置することができ、つまりブランチノードをルートノードまたは他のブランチノードの「子」として配置することができ、リーフをブランチノードの「子」として配置することができる。
【００２６】
図４ｂにはツリー構造１５０の１つの実施形態が示されており、これによれば境界エリア１１０の空間的分割も境界内エリア１１０におけるランドマークオブジェクト１０１〜１０５のロケーションも表される。ツリー構造１５０には、ルートノード１４０と４つのブランチノード１４１〜１４４と５つのランドマークオブジェクト１０１〜１０５が含まれている。これらルートノード１４０とブランチノード１４１〜１４４と５つのランドマークオブジェクトは階層状に配置されている。詳しくはルートノード１４０はツリー構造１５０の「ベース」または「ルート」の部分に配置され、ブランチノード１４１〜１４４はルートノード１４０の「子」として、さらに５つのランドマークオブジェクト１０１〜１０５は「リーフ」として配置されている。これに加えて５つのランドマークオブジェクト１０１〜１０５はブランチノード１４１〜１４４の「子」として配置されている。たとえばランドマークオブジェクト１０１はブランチノード１４２の子として配置されており、ランドマークオブジェクト１０３と１０２はブランチノード１４４の子として配置され、さらにランドマークオブジェクト１０４と１０５はブランチノード１４１の子として配置されている。
【００２７】
このようのツリー構造１５０の階層構成によって、たとえばナビゲーションシステムにおいて役立たせることのできるデータ構造を作るための適切な枠組みを提供することができる。殊にツリー構造１５０の階層構成は簡単に生成し解釈し進路決定できる。さらにツリー構造１５０の階層構成によって「クイックリジェクション」テストを実行できるようになり、その際、ツリーにおいてあるブランチノードのところにあるランドマークがナビゲーションのビュー円錐台の外側になったならば、そのブランチノードを「摘み取る」ことができる。たとえばナビゲーションシステムのユーザが第１象限Ｉに位置すると思われるならば、ランドマークオブジェクト１０１がユーザビュー円錐台の中にあると推定できる一方、ランドマークオブジェクト１０２〜１０５はユーザのビュー円錐台の外側にあると推定できる。このようにして、第１象限Ｉに関連づけられたブランチノードすなわちブランチノード１４２をロードすることができるのに対し、他のブランチノードすなわちブランチノード１４１，１４３，１４４は「摘み取る」ことができ、そのあとで訪れる必要がなくなる。したがってツリー構造１５０の階層構成により、要求があったときに実際のデータ（ランドマークオブジェクトまたは関心地点 Points of Interest POI）を目下のビューまたはユーザのリクエストに応じてロードできるようになる。
【００２８】
本発明の１つの実施形態によれば、ツリー構造１５０の各ノードはシステムの地理エリアに関する情報を提供することができる。たとえばツリー構造１５０の各ノードを「境界ボックス」"bounding box"（すなわち境界内エリア、象限、部分象限等）に関連づけることができ、これらを１つまたは複数の「タイル」により分割することができる。ここで１つのタイルは、１つの境界ボックス内の特定のロケーションに対するフィーチャおよび関連データのセットを含む論理単位である。フィーチャにはたとえば道路標識、ビルディングあるいは空中写真などを含めることができる。また、関連データにはタイル内の各フィーチャの記述を含めることができる（たとえばビルディングの多角形の個数、各多角形の面の個数ならびにそれらのｘ、ｙ、ｚ座標など）。
【００２９】
図５ａには、境界ボックスとタイルとの間の「ネストされた」関係が示されている。図５ａには、ナビゲーションシステムの地理的に区切られた２次元エリアの抽象表現２５０の一例が描かれており、これによれば境界ボックスとタイルとの間のネストされた関係が描かれている。境界ボックス１によりシステム全体における北、南、東、西の境界が定義されている。この場合、境界ボックス１がその中に境界ボックス２〜６が含まれるよう分割され、さらに各境界ボックスには１つまたは複数のタイル境界ボックスが含まれている。たとえば境界ボックス２にはタイルボックス２が含まれており、境界ボックス３にはタイルボックス３が含まれており、境界ボックス４にはタイルボックス４が含まれており、境界ボックス５にはタイルボックス５とタイルボックス６が含まれており、さらに境界ボックス６にはタイルボックス７が含まれている。
【００３０】
図５ｂには、図５ａにおけるネストされた境界ボックスの関係を表す階層ツリー構造２６０が示されている。ツリー構造２６０にはノードＮ１〜Ｎ６が含まれており、各ノードには固有の境界ボックス１〜６が対応づけられている。たとえばノードＮ１には境界ボックス１が対応づけられており、ノードＮ２には境界ボックス２が、ノードＮ３には境界ボックス３が、ノードＮ４には境界ボックス４が、ノードＮ５には境界ボックス５が、さらにノードＮ６には境界ボックス６がそれぞれ対応づけられている。ノードＮ１〜Ｎ６は階層構造で配置されており、これによって境界ボックス１〜６のネストされた関係が表されている。たとえばノードＮ１はツリー構造２６０のベースまたはルートのところに配置されており、これは対応づけられた境界ボックス１がナビゲーションシステムの地理エリア全体を取り囲んでいることを表している。さらにノードＮ２，Ｎ４，Ｎ５，Ｎ６はルートノードＮ１の「子」として配置されており、このことで対応づけられている境界ボックス２，４，５，６が境界ボックス１内に位置することが表されている。さらにノードＮ３はノードＮ２の子として配置されており、このことで対応づけられている境界ボックス３が境界ボックス２の中に位置することが表されている。
【００３１】
ノードＮ１〜Ｎ６各々は１つまたは複数の配属されたタイルＴＩＬＥ１〜ＴＩＬＥ７を有しており、これは配属された境界ボックスＴＩＬＥ Ｂｂｏｘ１〜ＴＩＬＥ Ｂｂｏｘ７のネストされた関係を表している。たとえばＴＩＬＥ１はノードＮ１に配属されており、これは配属されたＴＩＬＥ Ｂｂｏｘ１が境界ボックス１内に位置していることを表しており、ＴＩＬＥ２はノードＮ２に配属されており、これは配属されたＴＩＬＥ Ｂｂｏｘ２が境界ボックス２内に位置していることを表しており、ＴＩＬＥ３はノードＮ３に配属されており、これは配属されたＴＩＬＥ Ｂｂｏｘ３が境界ボックス３内に位置していることを表しており、さらにＴＩＬＥ４はノードＮ４に配属されており、これは配属されたＴＩＬＥ Ｂｂｏｘ４が境界ボックス境界ボックス４内に位置していることを表し、ＴＩＬＥ５とＴＩＬＥ６はノードＮ５に配属されており、これは配属されたＴＩＬＥ Ｂｂｏｘ５とＴＩＬＥ Ｂｂｏｘ６が境界ボックス５内に位置している子を表し、ＴＩＬＥ７はＮ６に配属されており、これはＴＩＬＥ Ｂｂｏｘ７が境界ボックス６内に位置していることを表している。
【００３２】
タイルに関するフィーチャセットならびに関連づけられたデータすなわちタイルデータは、タイルのディメンションおよび／またはツリー構造の親子関係を表すデータとは別個に保有しておくことができる。このようにフィーチャ関連のデータ（実際のデータ）を階層的なデータ（メタデータ）と分離することで、パフォーマンス全体にわたり改善がなされる。殊にこの分離によって、ユーザが見ることのできる空間内における拒否／受諾を迅速に行えるようになる。たとえばタイルに関連づけられたメタデータが東西南北の境界を規定する４つの番号によって指定される境界ボックスを含んでいるならば、交差またはオーバラップをただちに判定することができる。このようにして、含まれている可能性のあるフィーチャ各々を調べることなくタイルを受諾または拒絶することができる。したがってタイルのフィーチャがナビゲーションのビジョンにおいてフィールド内にあるのかフィールド外にあるのかを判定する目的で、それらのフィーチャを調べる必要がない。さらに実際のデータの変更がメタデータのインデックス化に影響を及ぼす可能性もない。それというのも実際のフィーチャデータはメタデータとは無関係だからである。
【００３３】
本発明の１つの実施形態によれば、メタデータと実際のデータの分離を２つのデータ構造すなわちリソースインデックスファイル Resource Index File (RIF) とディテールレベルファイル Level of Detail (LOD) File によってインプリメントすることができる。
【００３４】
次のテーブル１はＲＩＦファイルのフォーマット例を表している：
【００３５】
【表１】
2004213663.tif 000003
【００３６】
テーブル１に示されているように、ＲＩＦには［ＵＲＬ」フィールドと「ディメンション」フィールドと「Ｂｂｏｘ」フィールドと「タイル」フィールドと「Ｎ子」フィールドを含めることができる。ＵＲＬフィールドはＲＩＦファイルのロケーションを定義する文字列であり、このファイルはローカルファイルまたはリモートオブジェクトとすることができる。ディメンションフィールドは、２次元ロードマップを表す「２」であるかまたは３次元ロードマップを表す「３」とすることができる。Ｂｂｏｘフィールドには浮動小数点数のリストが含まれており、これによって配属されたノードについて境界ボックスの各ディメンションにおける上方境界と下方境界が定義される。タイルフィールドは１つの数字およびそれに続く一連の組から成り、この数字は配属されたノードに関するタイルの量を表し、一連の組には各タイルについての「タイルＩＤ」と「Ｂｂｏｘ」が含まれている（したがって境界ボックスは個々のタイルベースで定義される）。Ｎ子フィールドは１つの数字およびそれに続く一連の組から成り、この数字は配属されたノードに関連づけられた子の量を表し、一連の組にはＢｂｏｘフィールド、タイルフィールド、Ｎ子フィールドが含まれていて、これにより子それぞれの境界ボックス、配属されたタイルおよび子の数が再帰的に定義される。
【００３７】
図６ａには、記憶媒体または記憶装置内のＲＩＦファイルの物理的レイアウトが例示されている。ＲＩＦファイル３００は一連の隣り合うバイトとして格納することができ、これはテーブル１に定義されているような構造に従い解釈することができる。たとえばＵＲＬフィールド３０１は記憶装置の最初の部分を占有し、ディメンションフィールド３０２は記憶装置の次の部分を占有し、これに続いて境界ボックスフィールド３０３、複数のタイルフィールド３０４、タイルのＩＤ／境界ボックスのペアのシーケンス３０５、さらには複数の子と境界ボックスとタイルフィールド３０６から成る再帰的なシーケンスがおかれる。
【００３８】
図６ｂには、図５ｂの階層ツリー構造２６０に従ったＲＩＦファイルの内容３５０が例示されている。さらに詳しく説明するとこの内容３５０によって以下のことが指定される。すなわちＲＩＦファイルは /bosch/resources/tiles のところにおかれていること、ナビゲーションシステムの境界ボックスは地理的なエリアを２次元で記述すること、ルートノードには境界ボックス１が対応づけられており、この境界ボックスはタイルＩＤ １をもちタイルＢｂｏｘ１の配属された１つのタイルを含んでいること（＃タイル＝１）、ルートノードに４つの子が含まれていること（＃子＝４）、ルートノードの第１の子には境界ボックス２が対応づけられており、これはタイルＩＤ ２をもちタイルＢｂｏｘ２の配属された１つのタイルを含んでいること（＃タイル＝１）、ルートノードの第１の子は１つの子を含んでおり（＃子＝１）、これには境界ボックス３が対応づけられており、これはタイルＩＤ ３をもちタイルＢｂｏｘ３の配属されている１つのタイルを含んでいること（＃タイル＝１）、ルートノードの第１の子における子はさらに子をもっていないこと（＃子＝０）、ルートノードの第２の子には境界ボックス４が対応づけられており、これはタイルＩＤ＝４をもちタイルＢｂｏｘ４の配属された１つのタイルを含んでいること（＃タイル＝１）、ルートノードの第２の子はさらに子をもっていないこと（＃子＝０）、ルートノードの第３の子には境界ボックス５が対応づけられており、この境界ボックスはそれぞれタイルＩＤ ５とタイルＩＤ ６をもちタイルボックスＢｂｏｘ５とタイルボックスＢｂｏｘ６の配属された２つのタイル（＃タイル＝２）を含んでいる。ルートノードの第３の子はさらに子を有していないこと（＃子＝０）、ルートノードの第４の子には境界ボックス６が対応づけられており、これはタイルＩＤ＝７をもちタイルＢｂｏｘ７の配属された１つのタイルを含むこと（＃タイル＝１）、さらにルートノードの第８の子はさらに子をもっていないこと（＃子＝０）が指定される。
【００３９】
ディテールレベル（Level Of Detail, LOD）ファイルには、レベルの総数およびタイルの総数ならびに実際のデータをＲＩＦファイル内の参照として定義可能なその他のデータに関する情報が格納されている。以下のテーブル２には、ディテールレベル（ＬＯＤ）ファイルのフォーマットの一例が記述されている。
【００４０】
【表２】
2004213663.tif 000004
【００４１】
テーブル２に示されているように、ＬＯＤファイルは「Ｎレベル」フィールド、「Ｎタイル」フィールド、「タイルデータ」フィールド、「フィーチャデータ」フィールドを含むことができる。Ｎレベルフィールドは、階層におけるレベルの総数を表す整数である。Ｎタイルフィールドは階層におけるタイルの総数を表す整数である。タイルデータフィールドは個別タイルデータのロケーションを格納する一連の組であって、各組にはフィーチャデータフィールド内の格納ロケーションを表すファイルポインタフィールドと、対応づけられたタイルのディテールレベルを表すディテールレベルフィールドと、対応づけられたタイルのタイル識別子とが含まれている。フィーチャデータフィールドはフィーチャの数およびそれに続いて個別フィーチャデータを定義する配列であって、個別フィーチャデータにはフィーチャＩＤ、複数の浮動小数点で表されるフィーチャサイズならびに実際のデータが含まれている。
【００４２】
図７ａには、記憶媒体または記憶装置内のＬＯＤファイルの物理的なレイアウトが例示されている。ＬＯＤファイル４００は互いに隣り合うバイトのシーケンスとして格納することができ、これはテーブル２で定義されているような構造に従い解釈することができる。たとえばＮレベルフィールド４０１は記憶装置の最初の部分を占有しており、Ｎタイルフィールド４０２は記憶装置の次の部分を占有しており、これに続いてタイルデータＴＤおよびフィーチャデータＦＤがおかれている。タイルデータＴＤにはフィーチャデータＦＤを指し示すファイルポインタフィールド（たとえばファイルポインタフィールド４０３およびファイルポインタフィールド４３０）が含まれており、これによって特定のタイルに対応づけられた特定のフィーチャに対しいっそう高速にアクセスできるようになる。
【００４３】
図７ｂには、図５ｂの階層ツリー構造２６０のタイル１〜タイル７に応じたＬＯＤファイルの内容４５０が例示されている。さらに詳しくいえば内容４５０によって以下のことが指定される。すなわちツリーデータ構造は３つのレベルをもつこと（Ｎレベル＝３）、ツリー構造には全部で７つのタイルが含まれること（Ｎタイル＝７）、タイルＩＤ＝１をもつ１番目のタイルはレベル＝０で現れ、ファイルポインタ１を介して第１のフィーチャリストＦ１を指すこと、タイルＩＤ＝２をもつ第２のタイルはレベル＝１で現れ、ファイルポインタ２を介してフィーチャリストＦ２を指すこと、タイルＩＤ＝３をもつ３番目のタイルはレベル＝２で現れ、ファイルポインタ３を介してフィーチャリストＦ３を指すこと、タイルＩＤ＝４をもつ４番目のタイルはレベル＝１で現れ、ファイルポインタ４を介してフィーチャリストＦ４を指すこと、タイルＩＤ＝５をもつ５番目のタイルはレベル＝１で現れ、ファイルポインタ５を介してフィーチャリストＦ５を指すこと、タイルＩＤ＝６をもつ６番目のタイルはレベル＝１で現れ、ファイルポインタ７を介してフィーチャリストＦ７を指すことが指定される。
【００４４】
ＲＩＦファイルとＬＯＤファイルのフレームワークによってパフォーマンスを改善することができる。地理データベースまたは記憶媒体から移動ユニットのローカルメモリリソースたとえばグラフィックメモリなどへのデータのスワップイン／スワップアウトを実行するために、効率的なページングメカニズムをサポートすることができる。これによりナビゲーションシステムにより要求される計算の複雑さを最小限に抑えることができる。たとえばＲＩＦファイルの階層データ構造を移動するために０（ｌｏｇＮ）の計算ステップしか必要としなくてもよく、ここでＮはノード数であり、また、実際のデータを取得するためには０（１）しか必要としなくてよく、その理由はデータ構造に対応づけられたタイルデータに実際のランドマークオブジェクトの情報をただちに位置特定するためのファイルポインタが格納されているからである。たとえば典型的な都市描写を６つのディテールレベルをもつものとして格納することができ、各レベルには４つのタイルと４つの子が含まれ、各タイルには平均５０個のフィーチャ（たとえば建物構造など）が含まれている。したがってこのような描写のために、１３６５個のタイル（４０＋４１＋４２＋４３＋４４＋４５＝１３６５）と６８２５０個のフィーチャ（５０×１３６５＝６８２５０）が必要とされる。しかし実際のデータ（すなわちフィーチャデータ）の取得には、６つのレベルの移動およびその後に少数のポインタのリダイレクトしか必要としなくてよい。
【００４５】
ＲＩＦファイルとＬＯＤファイルのフレームワークによって高速な初期化時間も得られるようになる。その理由は、アプリケーション始動時にすべてのデータをメモリにダウンロードする必要がないからであり、これによりユーザに対するレスポンス時間が低減される。ＲＩＦファイルとＬＯＤファイルのフレームワークによりメモリ使用量も低減することができ、その理由はユーザに見える領域だけしかロードする必要がないからである。したがって実際のメモリ使用量を、システムリソースを食い潰すことなくユーザの見える領域により要求されるフィーチャのみの格納に適合するよう低減することができる。さらにＲＩＦファイルとＬＯＤファイルの使用によって前処理要求も低減することができる。その理由はタイル内のリソースだけを処理すればよく、これによりレンダリングのために他のデバイスにデータを送信する前にデータを前処理する必要性が低減されるからである。データ使用量の低減によって処理時間も同様に高速化することができる。これに加えてＲＩＦファイルとＬＯＤファイルの使用によって、ナビゲーションシステムのディスプレイパフォーマンスも改善することができる。それというのも、ナビゲーションシステムの埋め込み型グラフィックスプロセッサの計算／レンダリング能力は制約されている可能性があるからである。ＲＩＦおよびＬＯＤファイルのフレームワークを同様に他のデータ形式や他のシステムにも適用することができる。たとえばＲＩＦファイルおよびＬＯＤファイルのフレームワークを、実際に必要とされるときにナビゲーションシステムのランドマークオブジェクトのようなリソースをダウンロード／伝送することのできる他のストリーミングプロトコルに適用することができる。
【００４６】
１つの例示的な方法によれば、システム初期化時間にＲＩＦファイルがシーングラフマネージャにより読み出され、これによりツリー階層フォーマットでランタイムデータ構造が生成されて、ナビゲーションシステムのランタイムオペレーション中にメタデータをアクセスすることができる。ＲＩＦファイルは全体が読み込まれず、システムの次元（２または３）を記述するフィールドと、ＲＩＦのツリーデータ構造のレベル数により記述されたシステムのディレールレベルだけが読み込まれる。この場合、ランタイムツリーデータ構造のノードを作成し、対応づけられた境界ボックスまたは配属されたタイルがない状態で初期化される。
【００４７】
ユーザがシステムを操作するとき、適切な情報をＲＩＦファイルから取り出すことにより必要とされるならば、ランタイムツリーデータ構造内のノードをダイナミックに加えることができる。１つのノードが加えられると、配属されている何らかのタイルに応じた実際のデータをＬＯＤファイルからフェッチすることができる。たとえばタイルＩＤによってタイルデータに対するインデックスが提供され、さらに対応するファイルポインタによってフィーチャデータに対するアクセスが提供される。これに加えてユーザが異なる可視領域に移動してビュー円錐台が変化した後、不必要なファイルとフィーチャデータを破棄することができ、それによってシステムリソースが解放される。
【００４８】
フィーチャデータがアクセスされると、（図３に示した）ナビゲーションシステムの別のコンポーネントすなわちシーングラフレンダリングモジュール６０がただちにすべてのオブジェクトを、それらの地理的および外観の情報に基づきシーングラフにおいて表示する。１つの特有のインプリメンテーションによれば、オブジェクトの幾何学的形状を三角形または多角形などのような一連の「基本」要素に分解することができる。これらの基本要素を、当業者に周知の３次元グラフィックスアルゴリズムのライブラリを装備したグラフィックスエンジンを使用してレンダリングすることができる。Microsoft Windows（登録商標）2000, NT, MacOS 9, Linux などのようなオペレーティングシステムに含まれるOpenGL (Open Graphics Library) などのようなソフトウェアライブラリを使用して、グラフィックスエンジンをインプリメントすることができる。択一的に、グラフィックスレンダリングモジュール６０のグラフィックスエンジンを、様々なメーカからグラフィックカードの形態で入手可能な３Ｄアクセラレーションハードウェアを使用してインプリメントすることができる。
【００４９】
シーングラフレンダリングモジュールにより、マルチ分解能イメージ合成を使用するという本発明の別のアスペクトを実現することもでき、これはローカルメモリにおけるイメージの常駐量ならびにイメージのレンダリングに使用される計算リソースの量を減らすのに役立つ。付加的にマルチ分解能合成により、観察者がビジョンのあるフィールド部分に近づいて移動したりあるいはそこにズームインしたとき、粗い分解能構造イメージから微細な分解能構造イメージへの移行において知覚される分解能のジャンプが最小化されることでビジュアライゼーションが改善される。
【００５０】
図８Ａ，図８Ｂ，図８Ｃ，図８Ｄには、沿岸エリアのグレースケールイメージの空中からの構造ビューを使用して、混合されたマルチ分解能イメージが種々の空間分解能で示されている。図８Ａには、２桁のマーク（‘０１）で識別された粗い分解能のイメージと、４桁のマーク（‘０１３１）で識別された微細な高分解能のイメージの構造の混合について示されている。図示されているように、高分解能イメージに対する識別子（‘０１３１）の方が粗いイメージに対する相応の識別子（‘０１）よりもずっと小さく現れており、このことは微細な分解能イメージは粗いイメージよりも小さいエリアに関係し粗いイメージエリアの断片部分しか占有していないことを表している。
【００５１】
（図８Ｂに示されているように）観察者がズームインし、沿岸線のいっそう小さいエリアを観察するとき、粗いイメージは徐々にフェードアウトしていき、高レベルイメージがマーク‘０１３１をもつビジョンのフィールドを完全にカバーし、いっそう大きくかつシャープにフォーカシングされる。図８Ｃに示されているようにさらにズームインしていくと、‘０１３１マークは徐々にフェードアウトしていく一方、次に高い分解能レベル（‘０１３１３１）のマークが道路６０１ａ，６０１ｂなどのようなエリアの詳細フィーチャとともに徐々に現れるように示されるようになる。図８Ｄには最高分解能（最も細かいディテール）の構造が示されており、ビジョンのフィールドにおいてマーク‘０１３１３１が優位を占めている。このようにして、いっそう高い分解能イメージが徐々にフォーカスされていく一方、粗いイメージは消えていき、これによりスムーズな移行が得られ、このような移行はリアルに見える。
【００５２】
図９には、本発明のナビゲーションシステムにより実行されるマルチ分解能イメージ合成方法に関する１つの実施形態のフローチャートが示されている。まずはじめにシステムは観察者ビューパラメータ（７０１）を決定し、これには観察者のロケーション、注視方向ならびに場合によっては他の計算上の制約条件が含まれており、このような制約条件によって上述のようなビューポイントコントロールとロケーション計算モジュールを使用した表示結果に作用が及ぼされる。ついで観察者のビジョンフィールドに対応するビュー円錐台が配向および観察者のロケーションから決定され（７０２）、この配向と観察者のロケーションによって観察者が見ることのできる空間がいっしょに定義される。上述のようにビュー円錐台に基づきシーングラフマネージャはどのイメージタイルを見ることができるかを識別し（７０３）、シーングラフを生成し、ビュー円錐台の外側のタイルを破棄する。
【００５３】
各タイルが格納されているデータセットの階層的特性ゆえに、ビュー円錐台または地理エリア（２次元の境界ボックス）内の可視タイルには、粗いレベルから微細なレベルまで異なる分解能でイメージの多様なバージョンを含めることができる。イメージデータベースから境界ボックスに対応づけられたタイルのグループをプレロードしておくことで、シーングラフマネージャは混合のため種々異なる様々な分解能でイメージを手元に保持している。このような制限されたイメージのグループを高速アクセスのためにローカルメモリ内に保持しておくことはローカルメモリリソースの能力を超えるものではなく、それというのも境界ボックスに対応づけられていないもっと大きい格納イメージセットはダウンロードされず、メモリリソースまたは計算リソースを消費しないからである。
【００５４】
次に、分解能レベルと各イメージタイルまでの距離に基づき伝達関数を適用することで混合係数が決定され（７０４）、これによって境界ボックス内の各イメージタイルが結果として生じる混合されたイメージにどのように寄与するのかが設定される。次に、各分解能レベルについて混合係数を決定する様子について例示する。地理的関心地点に対する階層オブジェクトデータ構造には、ある特定のオブジェクト（またはある特定の地理エリア）について３つの構造分解能レベルが含まれており、ここでレベル０は最も粗いレベルを表し、レベル１は中間レベルを、さらにレベル２は最高分解能レベルを表す。
【００５５】
図１０には、３つの分解能レベルの各々に使用される混合係数が距離の関数のグラフとして示されている。注目対象オブジェクトからの距離が大きいとき（ｚ０）、分解能レベル０の混合係数は最大であるのに対しレベル１とレベル２の混合係数は０であり、このことはレベル０の構造だけが注目対象イメージのレンダリングに使用されることを表す。観察者が距離ｚ０から距離ｚ１へオブジェクト／エリアに近づくよう移動すると、分解能レベル０の混合係数は減少し分解能レベル１の混合係数は増加して、混合された注目対象イメージが生じる。観察者がいっそう近づいて距離ｚ２に向かって移動していくと、分解能レベル２の混合係数が最大レベルに向かって徐々に増加していき、分解能レベル１の混合係数は距離ｚ１と距離ｚ２の間においてある距離のところで最大レベルに達した後で徐々に減少していき、分解能レベル０の混合係数は０まで減少する。図示されているように、異なる３つの分解能レベルに対する個々の混合係数が徐々に変化することによって、すべての分解能レベルにわたりすべての距離において分解能の連続性が得られるようになる。
【００５６】
各レベルの混合係数を使用して構造およびイメージをレンダリングするために、各分解能レベルについてそれぞれの混合係数により１回、各グラフィックエリアが多数のパスでレンダリングされる。結果として生じる混合が各ロケーション（ｉ）において計算され（７０５）、これは分解能レベル（ｘ）でのロケーション（ｉ）のピクセルｐ（ｉ，ｘ）をその分解能レベルの混合係数ｂ（ｘ）で乗算した結果の和ｐ（ｉ）として計算される。ｎ個の分解能レベルについて計算は以下の通りとなる：
p(i) = b(0)*p(i,o) + b(1)*p(i,1) + ... + b(n)*p(i,n)
混合されたマルチ分解能イメージの生成によって、写真から得られたリアルな構造をもつ３次元シミュレーションについて道路マップおよび衛星イメージが提供され、これは慣用のビジュアルナビゲーションシステムにおいて提示されるような人工的なポリゴンによる近似に頼るものではない。これに加えてマルチパスレンダリングによって、粗いレベルから微細なレベルに移行したときにいっそう高いディテールレベルが突然現れたことに起因して視覚効果に及ぼされる妨害が最小限に抑えられる。さらに本発明による方法を、上述の構造イメージを格納するための階層フォーマットと関連させて効率的に実行することができる。さらにたとえばイメージディテールのダイナミックな合成を行うことができ、その際、オリジナルの衛星イメージ／ロードマップイメージをタイルに分割し、構造タイルをビュー円錐台内でユーザに見せるか否かに従い要求に応じてそれらをロードすることによって、計算リソースの能力を超えることがない。
【００５７】
これまでの記載において、本発明の方法ならびにシステムをいくつかの実施例を参照しながら説明してきたが、本発明はそれらに限定されるものではない。むしろ当業者であれば本発明による方法ならびに装置の基本原理において変形が可能であることは自明であり、そのような変形や変更および／または補足は以下の特許請求において規定される本発明の枠内に含まれるものである。
【図面の簡単な説明】
【００５８】
【図１ａ】第１の配向による観察者のビュー円錐台を示す図である。
【図１ｂ】図１ａに示した状態から僅かに配向を変化させたビュー円錐台を示す図である。
【図２ａ】本発明により提供される移動ユニットの現在のロケーションに従い都市環境を俯瞰図として３次元レンダリングした様子を示す図である。
【図２ｂ】移動ユニットが図示されているルートに沿って所定の距離だけ移動した後の図２ａの周囲環境を俯瞰図として３次元レンダリングした様子を示す図である。
【図２ｃ】移動ユニットが図示のルートに沿ってさらに移動した後の図２ａおよび図２ｂの周囲環境を俯瞰図として３次元レンダリングした様子を示す図である。
【図３】本発明の１つの実施例によるビジュアルナビゲーションシステムを示す図である。
【図４ａ】２次元エリア内に地理的に散りばめられたランドマークオブジェクトの抽象表現を示す図である。
【図４ｂ】図４ａの区切られたエリアの空間的分割と区切られたエリア内のランドマークオブジェクトを表すツリー構造を示す図である。
【図５ａ】境界ボックスとタイルとの間のネストされた関係を示すナビゲーションシステムの地理的に区切られた２次元エリアの抽象表現例を示す図である。
【図５ｂ】図５ａのネストされた境界ボックスの関係を表す階層ツリー構造を示す図である。
【図６ａ】本発明の１つの実施形態に従って記憶媒体またはメモリ内のリソースインデックスファイル（ＲＩＦ）の物理的なレイアウトを例示した図である。
【図６ｂ】図５ｂの階層ツリー構造に対応するＲＩＦファイルの内容を例示する図である。
【図７ａ】本発明の実施形態に従い記憶媒体またはメモリ内のディテールレベル（Level of Details, LOD）ファイルの物理的なレイアウトを例示した図である。
【図７ｂ】図５ｂの階層ツリー構造におけるタイルＴＩＬＥ１〜ＴＩＬＥ７に対応するディテールレベル（ＬＯＤ）ファイルの内容を例示した図である。
【図８ａ】最も遠い距離から見ているように表現した本発明による第１の混合マルチ分解能イメージを示す図である。
【図８ｂ】図８ａよりは短い距離から見ているように表現した本発明による第２の混合マルチ分解能イメージを示す図である。
【図８ｃ】図８ｂよりさらに短い距離から見ているように表現した本発明による第３の混合マルチ分解能イメージを示す図である。
【図８ｄ】最も近い距離から見ているように表現した本発明による第４の混合マルチ分解能イメージを示す図である。
【図９】本発明のナビゲーションシステムにより実行されるマルチ分解能イメージ合成のための方法に関する１つの実施形態を示すフローチャートである。
【図１０】３つの分解能レベルの各々について用いられる混合係数を距離の関数として示すグラフである。
【符号の説明】
【００５９】
５  観察者
７，８，９  オブジェクト
３０  オンボードコンポーネント
３５  ロケーション計算ユニット
４０  ポジションセンサ
４５  ビューポイントコントロールユニット
５０  ユーザ入力モジュール
５２  ルート計算モジュール
５５  シーングラフマネージャ
６０  シーングラフレンダラ
６１，６２  地理データベース
【図１ａ】
2004213663.tif 000005
【図１ｂ】
2004213663.tif 000006
【図３】
2004213663.tif 000007
【図５ａ】
2004213663.tif 000008
【図５ｂ】
2004213663.tif 000009
【図６ａ】
2004213663.tif 000010
【図６ｂ】
2004213663.tif 000011
【図７ａ】
2004213663.tif 000012
【図７ｂ】
2004213663.tif 000013
【図９】
2004213663.tif 000014
【図１０】
2004213663.tif 000015
【図２ａ】
2004213663.tif 000016
【図２ｂ】
2004213663.tif 000017
【図２ｃ】
2004213663.tif 000018
【図４ａ】
2004213663.tif 000019
【図４ｂ】
2004213663.tif 000020
【図８ａ】
2004213663.tif 000021
【図８ｂ】
2004213663.tif 000022
【図８ｃ】
2004213663.tif 000023
【図８ｄ】
2004213663.tif 000024