(57)【要約】【課題】可変分解能を用いて、そして、特に、表示される物理的地形のデジタル表現を高品質に維持しながら、外部および内部のメモリスペースを節約するために、比較的少ないデータを用いて、地形モデルを生成するための方法を提供すること。【解決手段】物理的地形のデジタル表現を生成するための方法であって、ラスタポイントを含むデジタル地形モデルのデータを読み取るステップであって、該ラスタポイントは、該ラスタポイントの高さ値を示す高さ座標を含む座標を有する、ステップと、該デジタル地形モデルの隣接するラスタポイントの該高さ値の間の差を決定するステップと、少なくとも１つの隣接するラスタポイントの該高さ値と、少なくとも所定の閾値だけ異なる高さ値を有するこれらのラスタポイントのみを格納するステップと、該格納されたラスタポイントを補間する三次元Ｂスプライン表面を計算するステップとを包含する、方法。【選択図】図３
2008140391.tif 000002
【特許請求の範囲】
【請求項１】
物理的地形のデジタル表現を生成するための方法であって、
ラスタポイントを含むデジタル地形モデルのデータを読み取るステップであって、該ラスタポイントは、該ラスタポイントの高さ値を示す高さ座標を含む座標を有する、ステップと、
該デジタル地形モデルの隣接するラスタポイントの該高さ値の間の差を決定するステップと、
少なくとも１つの隣接するラスタポイントの該高さ値と、少なくとも所定の閾値だけ異なる高さ値を有するようなラスタポイントのみを格納するステップと、
該格納されたラスタポイントを補間する三次元Ｂスプライン表面を計算するステップと
を包含する、方法。
【請求項２】
前記Ｂスプライン表面は、一様な二次Ｂスプライン表面、または一様な三次Ｂスプライン表面である、請求項１に記載の方法。
【請求項３】
前記Ｂスプライン表面は、非一様な有理Ｂスプライン表面である、請求項１に記載の方法。
【請求項４】
前記提供されたデジタル地形モデルの前記ラスタポイントの最も低い高さ値が、格納され、基準値として採用され、
少なくとも１つの隣接するラスタポイントの該高さ値と、少なくとも前記所定の閾値だけ異なる高さ値を有する該格納されたラスタポイントの該高さ値は、該基準値との差として格納される、請求項１〜請求項３のいずれか１項に記載の方法。
【請求項５】
前記三次元Ｂスプライン表面は、前記格納されたラスタポイントから該Ｂスプライン表面上の該格納されたラスタポイントの対応する点へのユークリッド距離の二乗が、最小化されるように計算される、請求項１〜請求項４のいずれか１項に記載の方法。
【請求項６】
物理的地形のデジタル表現を表示するための方法であって、
請求項１〜請求項５のいずれか１項に記載の物理的地形のデジタル表現を生成するための方法の前記ステップと、
さらに、前記計算された三次元Ｂスプライン表面を格納および／または表示するステップと
を包含する、方法。
【請求項７】
請求項１〜請求項６のいずれか１項に記載の方法の前記ステップを実行するためのコンピュータ実行可能な命令を有する１つ以上のコンピュータ読み取り可能な媒体を備える、コンピュータプログラム製品。
【請求項８】
デジタル地形モデルのラスタポイントのサブセットを格納するデータベースであって、該格納されたラスタポイントの全ては、隣接するラスタポイントの高さ値と、所定の限界より大きな値だけ異なる該高さ値を有する、データベースと、
ラスタポイント間のノットの分解能を選択するように構成されている選択手段と、
三次元Ｂスプライン表面を、該ラスタポイント間の該選択されたノットの分解能を用いて、該格納されたラスタポイントの補間によって計算して、表示ユニットを提供するように構成されている計算手段、および／または該三次元Ｂスプライン表面を有する該三次元Ｂスプライン表面を格納するように構成される格納手段と、
該計算手段によって提供される該三次元Ｂスプライン表面を表示するように、および／または該格納手段に格納されている該三次元Ｂスプライン表面を表示するように構成されている表示ユニットと
を備える、デジタルマップ表示手段。
【請求項９】
前記三次元Ｂスプライン表面は、二次または三次の一様なＢスプライン表面、あるいは非一様な有理Ｂスプライン表面である、請求項８に記載のデジタルマップ表示手段。
【請求項１０】
請求項８または請求項９に記載のデジタルマップ表示手段を備える、車両用ナビゲーションシステム、特に、自動車用ナビゲーションシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
（発明の分野）
本発明は、例えば、デジタルマップの生成のために使用されるような三次元地形モデルに関する。特に、本発明は、湾曲した表面エリアに基づいて構築される地形モデルに関する。
【背景技術】
【０００２】
（発明の背景）
近年、例えば、都市地図および道路地図のようなデジタルマップが、ますます普及してきた。デジタルマップは、例えば、ハンドヘルドおよび車両のナビゲーションシステムにおいて、重要な建築物のブロックを表現する。電子マップは、街路、ビル、および河川のような地図作成の特徴物を表現し得、例えば、コンパクトディスクまたはデジタル多用途ディスクなどの格納媒体を利用して、この地図作成の特徴物に関連するデータを格納し得る。
【０００３】
デジタルマップは、デジタル地形モデルによって生成され得る。非常に多様な富んだ地形学的な地形モデルが、公的機関および民間提供者によって提供されている。原則的に、デジタル地形モデルは、規則的または不規則的に間隔の空いた水平間隔で、地面の位置に対する地形の標高からなるデジタルファイルである。デジタル地形製品は、地形の傾斜、傾斜の方向、および選択された地点間の地形プロファイルを表示する三次元デジタルマップの生成に使用され得る。
【０００４】
通常、三次元地形モデルは、航空機搭載レーザ走査によって得られる。レーザ走査システムは、範囲測定手段と方向測定手段との組み合わせを備える。標的点の位置を決定するために、距離に加え、水平および垂直の方向が決定されなくてはならない。したがって、放射されたレーザビームは、偏向されなくてはならない。通常、レーザビームを変位させる方法は、２つある。例えば、ステッピングモータによって、走査ユニット全体が回転されるか、あるいはレーザビームが回転ミラーによって変位されるかのいずれかである。放射された／受けられたレーザビームの垂直および水平の角度の記録によって、要求される方向の計算が可能になる。範囲測定と方向測定との組み合わせによって、標的点の位置が提供される。
【０００５】
上述のデータ獲得方法によって、レーザ走査によって得られた地形モデルは、様々な分解能を用い、ラスタベースで提供される。現在の利用可能な最高の分解能によって、約２５メートルのデータ点の間隔を有するランドスケープのデジタル表現が可能である。
【０００６】
データグリッド点は、典型的には、個々の頂点（ｖｅｒｔｅｘ）によって表される。頂点は、特定のロケーションを有する三次元空間の点であり、このロケーションは、通常、そのｘ座標、ｙ座標、およびｚ座標によって与えられる。多角形モデリングにおける基本的な構造は、一緒に採用された２つの頂点が、ラインの終端を規定するために使用され得、３つの頂点が、平面三角形を規定するために使用され得る。データグリッド点を表す頂点と頂点との間の接続は、多角形によって得られる。
【０００７】
したがって、当該分野で結果として得られる地形モデルの品質は、利用可能な分解能に依存する。さらに、計算リソース、特に、メモリ要件に対する要求もまた、データの分解能に依存する。このことは、例えば、通常、幾分制約されたコンピュータリソースを提供されている車両ナビゲーションシステムのような内蔵されたシステムにとって、深刻な問題を提起する。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
したがって、本発明の目的は、可変分解能を用いて、そして、特に、表示される物理的地形のデジタル表現を高品質に維持しながら、外部および内部のメモリスペースを節約するために、比較的少ないデータを用いて、地形モデルを生成するための方法を提供することである。
【課題を解決するための手段】
【０００９】
（本発明の説明）
上述の目的は、請求項１に記載の物理的地形のデジタル表現を生成するための方法によって得られ、該方法は、
ラスタポイントを含むデジタル地形モデルのデータを読み取るステップであって、該ラスタポイントは、該ラスタポイントの高さ値を示す高さ座標を含む座標を有する、ステップと、
該デジタル地形モデルの隣接するラスタポイントの該高さ値の間の差を決定するステップと、
少なくとも１つの隣接するラスタポイントの該高さ値と、少なくとも所定の閾値だけ異なる高さ値を有するラスタポイントのみを格納するステップと、
該格納されたラスタポイントを補間する三次元Ｂスプライン表面を計算するステップと
を包含する。
【００１０】
地形モデルは、三次元モデルであり、例えば、レーザ走査によって得られたランドスケープのデジタルモデルである。非常に多様な地形学的な地形モデルが、公的機関および民間提供者によって提供されている。原則的に、デジタル地形モデルは、規則的または不規則的に間隔を空けた水平間隔で、地面の位置に対する地形の標高からなるデジタルファイルである。用語「物理的地形」はまた、本明細書で使用される場合、都市エリア、都市、村などの三次元地形を含む。地形モデルに含まれるラスタポイントは、三次元座標の値を有する（実際、ラスタポイントは、座標の値によって特徴付けられ、あるいは規定され得る）。本発明の方法に従うと、提供された地形モデルのラスタポイントの座標が、読み取られる。
【００１１】
用語「スプライン」は、多項式によって区分的に規定される関数を示す。所与の次数、平滑さ、および領域区画の全てのスプライン関数は、その同じ次数および平滑さのＢスプライン（ベーススプライン）の線形結合として表現され得る。Ｂスプラインは、周知の（Ｃｏｘ）ｄｅ  Ｂｏｏｒアルゴリズムによって評価され得る。ｍ−１個のノットｔｉ、ｉ＝０、・・、ｍの所与の非減少数列に対して、次数ｎのＢスプラインは、
【００１２】
【数１】
2008140391.tif 000003
から構成されるパラメトリックな曲線である。ここで、Ｐｉは、制御点であり、ｂｉ，ｎは、帰納によって規定される基底関数
【００１３】
【数２】
2008140391.tif 000004
である。
【００１４】
この曲線は、基底関数の全てが同じ符号（通常は、正が選択される）を有するという条件で、この曲線の制御点の凸包に完全に含まれる。ノットが等距離にあるとき、該Ｂスプラインは、一様なＢスプラインと称される。基底関数ｂｉ，ｎは、制御点Ｐｉが曲線にどれだけ強く影響を及ぼしているかを決定する。提供されたデジタル地形モデルのラスタポイントのサブセットを形成する格納されたラスタポイントは、制御点Ｐｉとして直接使用され得る。代替として、これらのラスタポイントから三次元Ｂスプライン表面（パッチ）の対応する点への距離は、最小化され得る（下記参照）。
【００１５】
ノットの数がＢスプラインの次数に等しいとき、Ｂスプラインは、ベジェ曲線を表す。本発明の方法で使用され得るＢスプラインの例は、ｂｉ，０として選択されたｂｉ，ｎを用いた一定のＢスプライン（最もシンプルなスプライン）と、
【００１６】
【数３】
2008140391.tif 000005
を用いた線形Ｂスプラインとを含む。
【００１７】
一定のＢスプラインおよび線形のＢスプラインは、幾分かシンプルであるのに対し、より満足いく補間は、一様な二次Ｂスプラインおよび一様な三次Ｂスプラインによって得られ得る。一様な二次Ｂスプラインは、曲線Ｃのｉ＋１番目のセグメントに対する行列形式で、
【００１８】
【数４】
2008140391.tif 000006
によって計算され、一様な三次Ｂスプラインは、
【００１９】
【数５】
2008140391.tif 000007
によって計算される。
【００２０】
本発明に従って使用されるＢスプライン表面は、ブレンディング関数
【００２１】
【数６】
2008140391.tif 000008
を用いて、Ｂスプラインのメッシュをブレンディングすることによって生成され得る。ここで、Ｐｊ，ｋは、空間におけるノットのロケーションである。Ｂスプライン表面はまた、移動の間に形状を変化し得る移動Ｂスプラインの曲線によって横切られる表面エリアとして解釈され得る。Ｂスプラインの凸包の特性はまた、Ｂスプライン表面に対しても保持する。
【００２２】
格納されたラスタポイント（すなわち、その座標）を補間するための三次元Ｂスプライン表面（パッチ）を生成することによって、データの格納能力および実際のプロセッサの負荷に従って、物理的地形の表示されるデジタル表現の可変の分解能が達成され得、適合され得る。物理的地形のデジタル表現の表示の分解能は、入力データに依存せず、任意に選択され得る。相対的に低い分解能に対してさえも、幾分か精度の良い地形のモデリングが可能となる。
【００２３】
物理的地形のデジタル表現に対する表面の計算は、高速表示を保証するために、十分迅速に実行され得る。特に、Ｂスプラインの利用は、一つ以上の制御点の操作によって、Ｂスプライン表面に含まれる曲線の局所的な挙動の変化を可能にする。Ｂスプライン表面を使用することのさらなる利点は、より丸みを帯びた地形プロファイルが、標準的な多角形を利用するのに比べて、デジタルに表現され得るという事実にある。
【００２４】
上述された方法の実施形態に従うと、計算されたＢスプライン表面は、一様な二次Ｂスプライン表面または一様な三次Ｂスプライン表面であり、すなわち、それぞれ一様な二次Ｂスプラインまたは一様な三次Ｂスプラインに基づく表面である（対応する基底関数に対しては、上記を参照）。一様な二次Ｂスプライン表面と一様な三次Ｂスプライン表面との双方に対して、ブレンディング関数が、容易に事前に計算され得るだけでなく、双方の種類の表面は、数値的に安定した方法で計算され得る。三次元バージョンの計算は、二次元バージョンの計算よりも動力の高いコンピュータリソースが要求される一方で、三次元バージョンの計算は、通常は、より精度良く物理的地形を表現するものと考えられる。
【００２５】
一様なＢスプライン（Ｂスプライン表面）の代わりに、非一様なＢスプラインも使用され得る。特に、Ｂスプライン表面は、非一様な有理Ｂスプライン表面（ＮＵＲＢＳ）であり得、例えば、三次ＮＵＲＢＳまたは四次ＮＵＲＢＳのようなＮＵＲＢＳであり得る。ＮＵＲＢＳの特徴的な性質は、各制御点が追加の重みを与えられることである。したがって、ＮＵＲＢＳは、四次元空間における曲線を表す。なぜなら、制御点は、四つ目の座標として、追加の重みを有するからである。
【００２６】
ＮＵＲＢＳの利点は、アフィン変換および透視変換の下で不変であることと、特に、非常に多様な形状に合致する高い柔軟性を提供することとを含む。さらに、Ｂスプライン表面を格納するとき、メモリ消費を最小にするのに役立つ。実際、非常に複雑な形状が、非常に小さなデータで表現され得る。さらに、これらの非常に複雑な形状は、当該分野で公知の数値的に安定で精度良いアルゴリズムによって、非常に高速で計算され得る。
【００２７】
本明細書で開示される物理的地形のデジタル表現を生成するための方法の実施形態に従うと、上記提供されたデジタル地形モデルの上記ラスタポイントの最も低い高さ値が、格納され、基準値として採用され、少なくとも１つの隣接するラスタポイントの上記高さ値と、少なくとも上記所定の閾値だけ異なる高さ値を有する該格納されたラスタポイントの該高さ値は、該基準値との差として格納される。これにより、格納スペースが、節約され得、補間するＢスプライン表面の効率的な計算が、支援され得る。
【００２８】
上記三次元Ｂスプライン表面は、前記格納されたラスタポイントから該Ｂスプライン表面上で該格納されたラスタポイントの対応する点へのユークリッド距離の二乗が、最小化されるように計算され得る。例えば、高さｈｊ，ｋを有するラスタポイントｐｊ，ｋに対して、Ｂスプライン表面Ｑ（ｓ，ｔ）は、条件
【００２９】
【数７】
2008140391.tif 000009
を満たすように計算され得る。
【００３０】
このような最小二乗法のアプローチは、ノットまたは制御点でラスタポイントを必ずしも識別することなしに、物理的地形のデジタル表現の精度を向上し得る。
【００３１】
本発明はまた、物理的地形のデジタル表現を表示するための方法を提供し、該方法は、上述の請求項のいずれか１項に記載の物理的地形のデジタル表現を生成するための方法の上記ステップと、また、上記計算された三次元Ｂスプライン表面を格納および／または表示するステップとを包含する。この物理的地形のデジタル表現は、三次元マップの形式で表示され得る。表示されているデジタル二次元マップの上に少なくとも部分的にオーバーレイされている追加の表示層上に物理的地形のデジタル表現を表示することもまた、企図される。
【００３２】
さらに、コンピュータプログラム製品が提供され、該コンピュータプログラム製品は、上述の方法の例のうちの一例の上記ステップを実行するためのコンピュータ実行可能な命令を有する１つ以上のコンピュータ読み取り可能な媒体を備える。
【００３３】
本発明は、さらに、請求項８に記載のデジタルマップ表示手段を提供し、該デジタルマップ表示手段は、
デジタル地形モデルに含まれるラスタポイントのサブセットを格納するデータベースであって、該格納されたラスタポイントの全ては、隣接するラスタポイントの高さ値と、所定の限界より大きな値だけ異なる該高さ値を有する、すなわち、所定の範囲内において同様の高さ値を有するラスタポイントは、データベース内に格納されない、データベースと、
ラスタポイント間のノットの分解能を選択するように構成されている選択手段と、
三次元Ｂスプライン表面を、該ラスタポイント間の該選択されたノットの分解能を用いる該格納されたラスタポイントの補間によって計算して、表示ユニットを提供するように構成されている計算手段、および／または該三次元Ｂスプライン表面を有する該三次元Ｂスプライン表面を格納するように構成されている格納手段と、
該計算手段によって提供される該三次元Ｂスプライン表面を表示するように、および／または該格納手段に格納される該三次元Ｂスプライン表面を表示するように構成されている表示ユニットと
を備える。
【００３４】
上記三次元Ｂスプライン表面は、二次または三次の一様なＢスプライン表面、あるいは非一様な有理Ｂスプライン表面であり得る。このデジタルマップ表示手段はまた、二次元マップ上に、三次元Ｂスプライン表面を重ね合わせるための切り替え手段、あるいは三次元Ｂスプライン表面と二次元マップとの表示の切り替えを行う切り替え手段を備え得る。したがって、このデジタルマップ表示手段は、自動的に、あるいはオペレータによって選択され得る可変分解能で、隣接するラスタポイントの高さ値と、所定の限界より大きな値だけ異なる高さ値を有する、ラスタポイントのみを用いて、Ｂスプライン表面を計算するように構成される。
【００３５】
このようなデジタルマップ表示手段は、車両ナビゲーションシステムにおいて、有利に使用され得る。したがって、上述のデジタルマップ表示手段を備える車両用ナビゲーションシステム、特に、自動車用ナビゲーションシステムが提供さる。
【００３６】
本発明の追加の特徴および利点は、図面を参照して記載される。説明において、本発明の好ましい実施形態を例示することを意図される添付図面に対して参照がなされる。このような実施形態が、本発明の完全な範囲を表わしていないことが、理解される。
【００３７】
本発明は、さらに、以下の手段を提供する。
【００３８】
（項目１）
物理的地形のデジタル表現を生成するための方法であって、
ラスタポイントを含むデジタル地形モデルのデータを読み取るステップであって、該ラスタポイントは、該ラスタポイントの高さ値を示す高さ座標を含む座標を有する、ステップと、
該デジタル地形モデルの隣接するラスタポイントの該高さ値の間の差を決定するステップと、
少なくとも１つの隣接するラスタポイントの該高さ値と、少なくとも所定の閾値だけ異なる高さ値を有するようなラスタポイントのみを格納するステップと、
該格納されたラスタポイントを補間する三次元Ｂスプライン表面を計算するステップと
を包含する、方法。
【００３９】
（項目２）
上記Ｂスプライン表面は、一様な二次Ｂスプライン表面、または一様な三次Ｂスプライン表面である、項目１に記載の方法。
【００４０】
（項目３）
上記Ｂスプライン表面は、非一様な有理Ｂスプライン表面である、項目１に記載の方法。
【００４１】
（項目４）
上記提供されたデジタル地形モデルの上記ラスタポイントの最も低い高さ値が、格納され、基準値として採用され、
少なくとも１つの隣接するラスタポイントの該高さ値と、少なくとも上記所定の閾値だけ異なる高さ値を有する該格納されたラスタポイントの該高さ値は、該基準値との差として格納される、項目１〜項目３のいずれか１項に記載の方法。
【００４２】
（項目５）
上記三次元Ｂスプライン表面は、上記格納されたラスタポイントから該Ｂスプライン表面上の該格納されたラスタポイントの対応する点へのユークリッド距離の二乗が、最小化されるように計算される、項目１〜項目４のいずれか１項に記載の方法。
【００４３】
（項目６）
物理的地形のデジタル表現を表示するための方法であって、
項目１〜項目５のいずれか１項に記載の物理的地形のデジタル表現を生成するための方法の上記ステップと、
さらに、上記計算された三次元Ｂスプライン表面を格納および／または表示するステップと
を包含する、方法。
【００４４】
（項目７）
項目１〜項目６のいずれか１項に記載の方法の上記ステップを実行するためのコンピュータ実行可能な命令を有する１つ以上のコンピュータ読み取り可能な媒体を備える、コンピュータプログラム製品。
【００４５】
（項目８）
デジタル地形モデルのラスタポイントのサブセットを格納するデータベースであって、該格納されたラスタポイントの全ては、隣接するラスタポイントの高さ値と、所定の限界より大きな値だけ異なる該高さ値を有する、データベースと、
ラスタポイント間のノットの分解能を選択するように構成されている選択手段と、
三次元Ｂスプライン表面を、該ラスタポイント間の該選択されたノットの分解能を用いて、該格納されたラスタポイントの補間によって計算して、表示ユニットを提供するように構成されている計算手段、および／または該三次元Ｂスプライン表面を有する該三次元Ｂスプライン表面を格納するように構成される格納手段と、
該計算手段によって提供される該三次元Ｂスプライン表面を表示するように、および／または該格納手段に格納されている該三次元Ｂスプライン表面を表示するように構成されている表示ユニットと
を備える、デジタルマップ表示手段。
【００４６】
（項目９）
上記三次元Ｂスプライン表面は、二次または三次の一様なＢスプライン表面、あるいは非一様な有理Ｂスプライン表面である、項目８に記載のデジタルマップ表示手段。
【００４７】
（項目１０）
項目８または項目９に記載のデジタルマップ表示手段を備える、車両用ナビゲーションシステム、特に、自動車用ナビゲーションシステム。
【００４８】
（摘要）
本発明は、物理的地形のデジタル表現を生成する方法に関し、該方法は、ラスタポイントを含むデジタル地形モデルのデータを読み取るステップであって、該ラスタポイントは、該ラスタポイントの高さ値を示す高さ座標を含む座標を有する、ステップと、該デジタル地形モデルの隣接するラスタポイントの該高さ値の間の差を決定するステップと、少なくとも１つの隣接するラスタポイントの該高さ値と、少なくとも所定の閾値だけ異なる高さ値を有するようなラスタポイントのみを格納するステップと、該格納されたラスタポイントを補間する三次元Ｂスプライン表面を計算するステップとを包含する。
【発明を実施するための最良の形態】
【００４９】
Ｂスプラインは、本発明で使用されるＢスプライン表面の基本的なコンポーネントである。図１は、４つの制御点を有する一様なＢスプラインの例を示す。ＢスプラインおよびＢスプライン表面によって規定される曲線は、それぞれ
【００５０】
【数８】
2008140391.tif 000010
であり、制御点によって、局所的に制御される。１２の制御点を有する曲線を示す図１ｂから容易に理解され得るように、各制御点は、その制御点に最も近い曲線の部分に影響を及ぼすが、遠くに離れた曲線の部分には、ほとんど、あるいは全く影響を及ぼさない。図１ｂに示される曲線は、制御点Ｐ（７）の位置によってのみ、互いに異なる。制御点の接続もまた、例示的な目的のために、図１ｂに示される。図１ａおよび図１ｂに示される曲線の形状は、曲線を含む平面内の制御点の位置によって決定される（厳密に言えば、制御点の座標と、各制御点に与えられる追加の重みとによって与えられる数学的四次元空間からの投影、上記参照）。
【００５１】
図２は、５×５の制御点によって規定される制御グリッドを有するＢスプライン表面の例である。制御グリッドは、制御点を接続する線（制御多角形として公知）の視覚化を表す。各制御点は、基底関数ｂｊ，ｐ（ｓ）およびｂｋ，ｑ（ｔ）によって重みを与えられる。パラメータｓおよびｔは、それぞれ値ｓ１、ｓ２、・・、ｓｌおよび値ｔ１、ｔ２、・・、ｔｍを有する離散パラメータである。物理的地形の三次元デジタル表現を生成するための方法の例に従うと、空間分解能、それぞれｓｊ＋１−ｓｊ＝（ｊ＝０、・・、ｌ−１）およびｔｉ＋１−ｔｉ＝（ｉ＝０、・・、ｍ−１）は、デジタル表現の所望の精度または利用可能なコンピュータリソースに従って、選択され得る。
【００５２】
図３は、物理的地形の三次元デジタル表現を生成するための、本明細書で開示される方法の基本的なステップを示す。地形モデルは、公の提供者によって提供される様々なデジタルモデルから選択され得る。デジタル地形モデル、例えば、レーザ走査されたデジタル地形モデルは、地方自治体および連邦政府によって、ならびに、例えば、米国商務省および対応する欧州行政・政府機関などによって提供される。
【００５３】
最初に、利用可能なデジタル地形モデルからデータが読み取られる（１）。データは、特に、デジタル地形モデルのラスタポイント（グリッドポイント）の三次元座標の値を備える。
【００５４】
読み取られたデータは、提供された地形モデルによって既にモデル化された物理的地形の信頼性あるデジタル表現のために必要なラスタポイントの数を適度に減らすために、統計的な解析を受ける。本例に従うと、提供されたモデルにおける最も低い点と最も高い点との間の高さの差（すなわち、それぞれの高さ座標の値の差）が、決定される。さらに、最も低い点は、基準点として選択され、その基準点に対する高さ値が、格納される。その他の全ての点の高さ値は、この最も低いラスタポイントとの正の差として表され得る。最も低いラスタポイントは、ゼロの高さに規格化され得る。
【００５５】
次のステップとして、表現されるべき地形の高さプロファイルの高さの差のために適切なラスタポイントが、決定される。これは、所定の限界内で、等しい高さ値または類似の高さ値を有する隣接するラスタポイントに対して、これらのラスタポイントのうちの一つのみが格納されることを意味する。これにより、これらの点のうちの一つのみの高さ値が格納される。
【００５６】
上記所定の限界は、例えば、一定の実数によって、あるいはそれぞれの高さ値の差の幾分かの割合によって、あるいは最も低いラスタポイントと最も高いラスタポイント（すなわち、それぞれ最も低い高さ値を有するラスタポイントと最も高い高さ値とを有するラスタポイント）との間の差の幾分かの割合によって、あるいは最も低いラスタポイントまたは最も高いラスタポイントの高さ値の幾分かの割合によって与えられ得る。
【００５７】
例えば、ラスタポイントｒｕ，ｖ、ｒｕ＋１，ｖ、ｒｕ＋２，ｖ、ｒｕ＋３，ｖ（ここで、下付きｕおよびｖは、平面座標、例えば、地理的な経度および緯度を表す）での高さ値が、所定の限界より小さい幾らかの値だけ異なる場合、これらのラスタポイントのうちの一つ、例えば、ｒｕ，ｖのみ、および、これにより、これらの高さ値のうちの一つが格納される。したがって、物理的地形の高さプロファイルの正確なモデル化に適切なラスタポイントのみが、格納され（３）、したがって、格納能力に対する要求は、元々提供されたデジタル地形モデルに比べて、著しく削減され得る。
【００５８】
Ｂスプライン表面によって、格納されたラスタポイントを補間する（４）ための座標は、格納された高さ値から得られる。計算されたＢスプライン表面は、引き続く表示のために格納され得、計算された後、また、即座に表示され得る（５）。
【００５９】
行列表示において、Ｂスプライン表面は、制御点の行列Ｇに対して、
【００６０】
【数９】
2008140391.tif 000011
によって計算され得る。ここで、ベクトル
【００６１】
【数１０】
2008140391.tif 000012
は、データ点の補間のための位置を示し、例えば、三次補間に対して、
【００６２】
【数１１】
2008140391.tif 000013
である。Ｍは、Ｂスプラインを基底とする補間によって与えられ、例えば、三次補間に対して、
【００６３】
【数１２】
2008140391.tif 000014
である。
【００６４】
三次元Ｂスプライン表面（パッチ）の分解能ｓｊ＋１−ｓｊ（ｊ＝０、・・、ｌ−１）およびｔｉ＋１−ｔｉ（ｉ＝０、・・、ｍ−１）は、それぞれ、オペレータによって、手動で選択され得る。例えば、利用可能なコンピュータリソース、あるいはモデル化されるべき物理的地形の種類に対して、自動的に分解能を調整することもまた、好まれ得る。
【図面の簡単な説明】
【００６５】
【図１ａ】図１ａは、４つの制御点による有理Ｂスプラインの操作を示す。
【図１ｂ】図１ｂは、１２の制御点によって決定された有理Ｂスプラインの曲線上の制御点の局所的な影響を示す。
【図２】図２は、５×５の制御点からなるＢスプライン表面および制御グリッドに対する例を示す。
【図３】図３は、物理的地形のデジタル表現を生成するための本発明の方法の例の基本的なステップを示す流れ図である。
【符号の説明】
【００６６】
Ｐ（０）〜Ｐ（１１）  制御点
【図１ａ】
2008140391.tif 000015
【図１ｂ】
2008140391.tif 000016
【図２】
2008140391.tif 000017
【図３】
2008140391.tif 000018