JP2008107828A - デジタルマップにおけるストリートのリアルな高さ表現 - Google Patents

Abstract

【課題】デジタルマップにおいて、ストリートのリアルな高さを表現する方法を提供すること。
【解決手段】デジタルマップのストリートのストリートベクトルを生成する方法であって、地形モデルのデータを読み出すステップと、該地形モデルの該読み出されたデータに含まれる高さ座標を用いて、該ストリートベクトルを初期化するステップと、該ストリートの該初期化されたストリートベクトルに対するコスト関数を計算するステップと、少なくとも一つのストリートベクトルの該高さ座標を変化させることによって、該コスト関数を最小化するステップと、該コスト関数が最小化される該ストリートベクトルを決定するステップとを包含する、方法。
【選択図】図１

Description

（発明の分野）
本発明は、都会および風景を表現するデジタルマップに関し、特に、本発明は、デジタルマップ、例えば、デジタル都市地図およびデジタル道路地図において、ストリートの三次元表現に関する。

（発明の背景）
近年、例えば、都市地図および道路地図のようなデジタルマップが、ますます普及してきた。デジタルマップは、例えば、携帯および車両のナビゲーションシステムにおいて、重要なビルディングブロックを表現する。電子マップは、ストリート、ビル、および河川のような地図作成の特徴物を表現し得、例えば、コンパクトディスクまたはデジタルビデオディスクなどの格納媒体を利用して、この地図作成の特徴物に関連するデータを格納し得る。

最近、デジタルデータベースから局所的な三次元透視図に変換するアルゴリズムを提供された様々なナビゲーションシステムが開発されてきた。この三次元透視図は、概ね、多くのドライバによって、かなり容易に理解される。精緻なシステムは、例えば、交差点の複雑さに応じて、道路に対して可変な角度で車両が近づく交差点を表示することが可能である。

しかしながら、利用可能で公的に提供されたストリートマップのデジタル化によると、今日のデジタルマップは、実質的には二次元表現のストリートネットワーク全体を含むだけである。このようなマップにおいて、ストリートの高さ情報は、空間的深さに対して適切なオーダーによる表示を可能にするために、交差するストリートのベクトルに対する特定のストリートの相対的な高さに関する情報として与えられるのみである。

今日のデジタルマップに含まれるストリートのデジタル表現のストリートベクトルの地形的高さに関するデータは、全く利用可能でない。しかしながら、このようなデータは、ストリートのリアルな表現に対して役立ち、車両ナビゲーションシステムのマップデータベースに格納され、ルート案内に使用されるデジタルマップに関して、特に役立つ。

したがって、ユーザに、より詳細で信頼性のあるマップ情報を提供して、デジタルマップを表示するように構成されるナビゲーションシステムによるルート案内を容易にするために、デジタルストリートマップにおいて、ストリート高さを生成し、インプリメントすることに対するニーズが存在する。

したがって、本発明の目的は、デジタルマップのストリートの高さ情報を含める方法を提供することと、（他のストリート（ベクトル）と比較した一つのストリート（ベクトル）の相対的な高さのみならず）絶対的なストリート高さを示すデジタルマップを提供することである。

（本発明の説明）
上述の目的は、請求項１に記載のデジタルマップ（物理的ストリートのデジタル表現）のストリートのストリートベクトルを生成する方法によって得られ、該方法は、
地形モデルのデータを読み出すステップと、
該地形モデルの該データから読み出された高さ座標を用いて、該ストリートベクトルを初期化するステップと、
該ストリートの該初期化されたストリートベクトルに対するコスト関数を計算するステップと、
少なくとも一つのストリートベクトルの該高さ座標を変化させることによって、該コスト関数を最小化するステップと、
該コスト関数が最小化される該ストリートベクトルを決定するステップと
を包含する。

本出願において、物理的なストリートを表現するデジタルマップにおけるストリートは、ノット（ｋｎｏｔ）と、ノットを接続する多角形エレメントとを備えるものと仮定される。本明細書において、多角形エレメントは、ストリートベクトルと称される。各ストリートベクトルは、起点と終点とを有する。

地形モデルは、三次元モデルであり、例えば、レーザ走査によって得られたデジタルモデルである。非常にバライエティ豊かな地形学的な地形モデルが、公的な機関と、商業プロバイダとによって提供されている。概して、デジタル地形モデルは、規則的に、あるいは不規則に間隔を空けた水平なインターバルで、地面の位置に対する地形の標高からなるデジタルファイルである。デジタル地形は、地形の傾き、傾きの方向、および選択された点と点の間の地形プロファイルを表示する三次元デジタルマップを生成して使用され得る。本発明において使用される地形モデルは、地形モデルに含まれるエレメントの座標、特に高さ座標の情報を備える。

本発明の方法に従うと、ストリートのストリートベクトルは、使用される地形モデルから読み出された高さ座標データによって、最初に生成（初期化）される。これは、ストリートのストリートベクトルが、地形モデルで表現された対応するロケーションの高さプロファイルに適合し、同一平面であることを意味する。特に、ストリートベクトルの高さ座標と、地形モデルにおける地形学的なエレメント（例えば、丘および谷）のそれぞれの区間の高さ座標とにおける差がない。地表面（ｓｕｒｆａｃｅ ｐｌａｎｅ）、例えば、に投影されたデカルト平面におけるストリートの二次元座標、特に、東西の座標および南北の座標は、既存の二次元マップデータから読み出され得る。

ストリートベクトルが初期化された後、すなわち、地形モデルに対応する高さ座標を用いて、ストリートベクトルが生成された後、ストリートベクトルに対するコスト関数が、計算される。特に、ストリートベクトルによって構築されるストリート全体に対するコスト関数が、計算され得る。コスト関数は、ストリートベクトルに従う物理的なストリートを建設する実際のコストの見積もりを反映する。コスト関数は、好ましくは、トンネルおよび／または橋梁に対する建設コスト、および／またはストリートベクトルを初期化するために使用された高さ座標（すなわち、ストリートベクトルを初期化するために使用された地形モデルから採られた高さ座標）に対して、ストリート高さを上げるコストおよび／または下げるコストに対する見積もりを含み得る。

詳細には、コスト関数は、トンネルの長さおよび深さ、および／または橋梁の長さおよび高さ、および／または上記決定されたストリートベクトルによる上記ストリートの高さプロファイルと上記地形モデルの対応する高さプロファイルとの差（初期化されたストリートベクトルに対して、この差は、初期化処理の定義によって、ゼロである）によって規定される面積および／または体積に基づいて、計算され得る。

コスト関数は、好ましくは、地理的な現実、例えば、地形モデルによって提供される岩または地下水面に関する情報を考慮し得る。

ストリートベクトルの高さ座標を変化させることによって、コスト関数を最小化することが、本発明の主たる局面である。最初に、１つ以上の初期化されたストリートベクトルの高さ座標が修正される。最小化処理の間に、既に修正されたストリートベクトルの高さ座標が、さらに修正され得る。これらのストリートベクトルは、コスト関数によって表わされるコストが、最小化されるように決定される。このようにして決定されたストリートベクトルは、デジタルマップ内のストリートの表現が、地形学的高さにおいて従来利用できなかった高い精度を有することを可能にする。この方法は、完全に自動的に実行され得るので、精度良い三次元ストリートマップが、効率的かつ経済的に作成され得る。

上記ストリートベクトルの上記高さ座標の変化によって、コスト関数を最小化するステップで、該ストリートベクトルにおいて、別のストリートのストリートベクトルが交差している全交差点の高さ座標は、維持され得る。これによって、特定のストリートに対するコスト関数を、このストリートのストリートベクトルの高さ座標の変化によって最小化することで、後者と交差する別のストリートベクトルのストリートベクトルが修正されることは、避けられる。しかしながら、該交差点の幾分かの変化が、狭い上下限の範囲に入るようにすることは、好ましいことであり得る。

一実施形態に従うと、本明細書に開示されるストリートベクトルを生成する方法は、
ａ）該ストリートベクトルそれぞれの勾配を計算するステップと、
ｂ）該計算された勾配が、所定の下限と上限との間にあるかどうかを決定するステップと、
ｃ）該所定の下限より小さい勾配または該所定の上限より大きい勾配を有する該ストリートベクトルそれぞれの起点および／または終点の高さ座標を修正するステップと、
ｄ）ステップｃ）で修正された高さ座標を用いて、該ストリートベクトルそれぞれの勾配を計算して、該計算された勾配が、所定の下限と上限との間にあるかどうかを決定するステップと、
ｅ）該ストリートベクトルそれぞれの該計算された勾配が、該所定の下限と上限との間に入るまで、上記ステップｃ）〜ｄ）を実行するステップと
をさらに包含し、
上記コスト関数は、該所定の下限と上限との間にある勾配を有するストリートベクトルの該高さ座標のみを変化させることによって最小化される。

別の実施形態に従うと、本明細書に開示されるストリートベクトルを生成する方法は、
ａ）該ストリートベクトルのサブセットの全体勾配、または上記ストリートの全ストリートベクトルの全体勾配を計算するステップと、
ｂ）該計算された全体勾配が、所定の下限と上限との間にあるかどうかを決定するステップと、
ｃ）該計算された全体勾配が、該所定の下限を下回る場合、あるいは該所定の上限を超える場合、該全体勾配が計算された該ストリートベクトルのうちの少なくとも一つのストリートベクトルの起点および／または終点の高さ座標を修正するステップと、
ｄ）該全体勾配が、該所定の下限と上限との間に入るまで、上記ステップａ）〜ｃ）を実行するステップと
をさらに包含し、
上記コスト関数は、該所定の下限と上限との間にある該全体勾配に対するストリートベクトルの該高さ座標のみを変化させることによって最小化される。

ストリートベクトルのサブセットは、２つの交差点の間のストリートベクトルからなり得る。全体勾配は、個々のストリートベクトルの勾配から計算され、ストリートまたはストリートセグメントの妥当な高さプロファイルを推測するのに、別のより有効な手段を代表する。

勾配の計算を含む２つの実施形態の上述のステップａ）〜ｅ）は、コスト関数の最小化が、初期化されたストリートベクトルと、（修正された高さ座標によって）既に修正されたストリートベクトルとを変化させることによって実行される前に、実行され得ることは留意される。

勾配（傾き）を決定することと、所定の範囲外の勾配を示す上記ストリートベクトルそれぞれの起点および／または終点を変化させることとによって、妥当性チェックが実行される。これは、地形モデルが、地形の強度な局所的変化、例えば、デジタル化された離散地形モデルの隣接点の高さ（標高）における著しい離散ジャンプを示す場合、特に有効である。この妥当性チェックは、都市領域に対しても、ビルのサイズが地表高度に追加されるとき、重要である。

上記所定の下限より小さい計算された勾配、あるいは上記所定の上限より大きい計算された勾配を有する上記ストリートベクトルそれぞれの上記起点および／または上記終点の上記高さ座標は、所定の値、例えば、用いられた離散座標の値のうちの一つで、特に、インクリメントまたはデクリメントされ得る。

本発明に従って、生成されるストリートベクトルに対するデジタルマップの上記ストリートのストリートクラスは、決定され得、上記下限および上記上限は、該決定されたストリートクラスに基づいて、事前に決定され得る。ストリートクラスの典型的な例は、主要道路、脇道、国の高速道路、田舎道などである。異なるクラスに対して、許容可能な勾配に対する有利に異なる上下限が、選択される。クラスは、ストリートベクトルを生成するために提供され、使用された二次元マップのデータに基づいて決定され得る（上記参照）。

上記ストリートクラスの決定は、特に、考慮されるストリートがクロソイドモデルに従って建設されているかどうかを決定するステップを包含し得る。クロソイドモデルに従って建設されたストリートは、１つ以上の特定のクラスに分類され得る。対象のストリートが属するクラスの決定は、そのストリートが、クロソイドモデルに従って建設されているか否かの解析に基づいて実行され得る。

「クロソイドモデル」という用語によって、曲線のパラメータと、クロソイドによって建設される曲線のパラメータ、すなわち、弧の長さ、半径、正接角、クロソイドパラメータ、および曲率と互いの一意的な関数的依存性とが、理解されるべきである。より具体的には、クロソイドは、クロソイドのサブクラスを表現する幾何学的曲線であり、曲率Ｃによって特徴付けられ、この曲率Ｃは、弧の長さＬに比例する、すなわちＣ＝Ｌ／Ａ^２である。ここで、Ａは、クロソイドパラメータと一般に称される。

十分に設計され、建設された道路は、クロソイドモデルに従うので、クロソイドによる実際の道路およびストリートの数値モデル化およびデジタル表現によって、曲線パラメータ、特に、車両によって通過されるべきカーブの曲率に関する信頼性ある正確な情報を入手することが可能になる。さらに、クロソイドモデルに従って建設されるストリートの勾配は、明確な上下限の範囲に入ることが期待される。例えば、ドイツにおいては、１９８４年から、主要道路は、クロソイドによって設計され、建設されることになっている。

本発明はまた、コンピュータプログラム製品も提供し、該コンピュータプログラム製品は、上述されたような本発明の方法の実施形態のステップを実行するコンピュータ実行可能な命令を有する１つ以上のコンピュータ読み取り可能な媒体を備える。

上述の目的はまた、デジタルストリートマップによっても得られ、該デジタルストリートマップは、
ストリートベクトルを備えるストリートの少なくとも一つの三次元デジタル表現を備え、
該ストリートベクトルは、コスト関数が最小化されるような高さ座標を含むことを特徴とする。

上記コスト関数は、上述の例のうちの一つに従って計算され得る（詳細については、以下の実施形態の詳細な説明も参照）。特に、該コスト関数は、トンネルの長さおよび深さ、および／または橋梁の長さおよび高さ、および／または上記決定されたストリートベクトルによる上記ストリートの高さプロファイルと地形モデルの対応する高さプロファイルとの差によって規定される面積および／または体積に基づいて計算され得る。該地形モデルは、請求項１１に記載のデジタルマップに対するストリートベクトルを生成する処理の間に、該コスト関数を最小化するために、修正された初期ストリートベクトルを決定するために使用されたものである。したがって、該デジタルマップのストリート（物理的なストリートの表現）は、コスト最小化の特徴（ｆｅａｔｕｒｅ）によって、特徴付けられる。

上記デジタルマップの実施形態に従うと、上記少なくとも一つのストリートの２つの（他のストリートのストリートベクトルと交差する）交差点の間の各区間は、所定の下限と上限との間にある勾配を有するか、および／または該少なくとも一つのストリート全体が、所定の下限と上限との間にある全体勾配を有するか、および／または上記ストリートベクトルのそれぞれが、所定の下限と上限との間にある勾配を有する。

さらに、上述の所定の下限と上限とは、上記少なくとも一つのストリートが属するストリートクラスに基づいて、および／または該少なくとも一つのストリートがクロソイドモデル（上記参照）に従って建設されているかどうかの決定に基づいて決定される。クロソイドモデルに従って建設されたストリートは、とりわけ、例えば、主要道路および脇道のストリートクラスを表現し得る。

上述のデジタルマップは、特に、ナビゲーションに使用されるデジタルストリートマップであり得る。したがって、このデジタルマップは、車両ナビゲーションシステムのマップデータベースに格納され得る。本発明はまた、ナビゲーションシステム、特に、車両ナビゲーションシステムを提供し、該ナビゲーションシステムは、上述の例の一つに従うデジタルマップを格納するマップデータベースを備える。

本発明の追加の特徴および利点は、図面を参照して記載される。説明において、本発明の好ましい実施形態を例示することを意図される添付図面に対して参照がなされる。このような実施形態が、本発明の全ての範囲を表わしていないことは、理解されるべきである。

本発明は、さらに、以下の手段を提供する。

（項目１）
デジタルマップのストリートのストリートベクトルを生成する方法であって、
地形モデルのデータを読み出すステップと、
該地形モデルの該読み出されたデータに含まれる高さ座標を用いて該ストリートベクトルを初期化するステップと、
該ストリートの該初期化されたストリートベクトルに対するコスト関数を計算するステップと、
少なくとも一つのストリートベクトルの該高さ座標を変化させることによって、該コスト関数を最小化するステップと、
該コスト関数が最小化される該ストリートベクトルを決定するステップと
を包含する、方法。

（項目２）
上記コスト関数を最小化する上記ステップの間、上記ストリートベクトルにおいて、他のストリートのストリートベクトルが交差している全交差点の上記高さ座標を維持するステップをさらに包含する、項目１に記載の方法。

（項目３）
ａ）上記ストリートベクトルのそれぞれの勾配を計算するステップと、
ｂ）該計算された勾配が、所定の下限と上限との間にあるかどうかを決定するステップと、
ｃ）該所定の下限より小さい勾配または該所定の上限より大きい勾配を有する該ストリートベクトルそれぞれの起点および／または終点の高さ座標を修正するステップと、
ｄ）ステップｃ）で修正された高さ座標を用いて、該ストリートベクトルのそれぞれの勾配を計算して、該計算された勾配が、所定の下限と上限との間にあるかどうかを決定するステップと、
ｅ）該ストリートベクトルそれぞれの該計算された勾配が、該所定の下限と上限との間に入るまで、上記ステップｃ）〜ｄ）を実行するステップと
をさらに包含し、
上記コスト関数は、該所定の下限と上限との間にある該勾配を有するストリートベクトルの該高さ座標のみを変化させることによって最小化される、項目１または項目２に記載の方法。

（項目４）
ａ）上記ストリートベクトルのサブセットの全体勾配、または全ストリートベクトルの全体勾配を計算するステップと、
ｂ）該計算された全体勾配が、所定の下限と上限との間にあるかどうかを決定するステップと、
ｃ）該計算された全体勾配が、該所定の下限を下回る場合、あるいは該所定の上限を超える場合、該全体勾配が計算された該ストリートベクトルのうちの少なくとも一つのストリートベクトルの起点および／または終点の高さ座標を修正するステップと、
ｄ）該全体勾配が、該所定の下限と上限との間に入るまで、上記ステップａ）〜ｃ）を実行するステップと
をさらに包含し、
上記コスト関数は、該所定の下限と上限との間にある該全体勾配に対するストリートベクトルの該高さ座標のみを変化させることによって最小化される、項目１または項目２に記載の方法。

（項目５）
上記所定の下限より小さい計算された勾配、あるいは上記所定の上限より大きい計算された勾配を有する上記ストリートベクトルそれぞれの上記起点および／または上記終点の上記高さ座標は、所定の値によって、インクリメントまたはデクリメントされる、項目３または項目４に記載の方法。

（項目６）
上記ストリートのストリートクラスが、決定され、上記下限および上記上限は、該決定されたストリートクラスに基づいて、事前に決定される、項目３または項目４に記載の方法。

（項目７）
上記ストリートクラスを決定するステップは、上記ストリートがクロソイドモデルに従って建設されているかどうかを決定するステップを包含する、項目６に記載の方法。

（項目８）
上記コスト関数は、トンネルおよび／または橋梁に対するコスト、および／または上記ストリートベクトルを初期化するために使用された高さ座標に対して、ストリート高さを上げるコストおよび／または下げるコストを備える、項目１〜項目７のいずれか１項に記載の方法。

（項目９）
上記コスト関数は、トンネルの長さおよび深さ、および／または橋梁の長さおよび高さ、および／または上記決定されたストリートベクトルによる上記ストリートの高さプロファイルと上記地形モデルの対応する高さプロファイルとの差によって規定される面積および／または体積に基づいて計算される、項目８に記載の方法。

（項目１０）
上記項目１〜項目９のいずれか１項に記載の方法の上記ステップを実行するコンピュータで実行可能な命令を有する１つ以上のコンピュータ読み取り可能な媒体を備える、コンピュータプログラム製品。

（項目１１）
ストリートベクトルを備えるストリートの少なくとも一つの三次元デジタル表現を備える、デジタルストリートマップであって、
該ストリートベクトルが、コスト関数が最小化されるような高さ座標を含むことを特徴とする、
デジタルストリートマップ。

（項目１２）
上記コスト関数は、トンネルの長さおよび深さによる寄与、および／または橋梁の長さおよび高さによる寄与、および／または上記ストリートの高さプロファイルと地形モデルの対応する高さプロファイルとの差によって規定される面積および／または体積による寄与を含む、項目１１に記載のデジタルマップ。

（項目１３）
上記少なくとも一つのストリートの２つの交差点の間の各区間が、所定の下限と上限との間にある勾配を有するか、および／または該少なくとも一つのストリート全体が、所定の下限と上限との間にある全体勾配を有するか、および／または上記ストリートベクトルのそれぞれが、所定の下限と上限との間にある勾配を有する、項目１１または項目１２に記載のデジタルマップ。

（項目１４）
上記ストリートは、ストリートクラスに分類され、上記所定の下限と上限とは、上記少なくとも一つのストリートが属するストリートクラスに基づいて、および／または該少なくとも一つのストリートがクロソイドモデルに従って建設されているかどうかの決定に基づいて決定される、項目１３に記載のデジタルマップ。

（項目１５）
マップデータベースを備えるナビゲーションシステム、特に、車両ナビゲーションシステムであって、該マップデータベースは、項目１１〜項目１４のいずれか１項に記載のデジタルマップを備える、ナビゲーションシステム。

（摘要）
本発明は、デジタルマップのストリートのストリートベクトルを生成する方法に関し、該方法は、地形モデルのデータを読み出すステップと、該地形モデルの該データから読み出された高さ座標を用いて、該ストリートベクトルを初期化するステップと、該ストリートの該初期化されたストリートベクトルに対するコスト関数を計算するステップと、少なくとも一つのストリートベクトルの該高さ座標を変化させることによって、該コスト関数を最小化するステップと、該コスト関数が最小化される該ストリートベクトルを決定するステップとを包含する。該方法はまた、デジタルマップにも関し、該デジタルマップは、ストリートベクトルを備えるストリートの少なくとも一つの三次元デジタル表現を備え、該ストリートベクトルは、コスト関数が最小化されるような高さ座標を含む。

図１は、本発明の実施例に従うデジタルマップ内に含まれるストリートのストリート高さプロファイルを示す。ストリートは、ストリートベクトルによって構築され、ストリートベクトルは、交差点（異なるストリートのストリートベクトルが交差する点）の間で多角形を形成する。実線１は、地形モデルに基づいて、ストリートベクトルを初期化することによって与えられたままでのストリート高さプロファイルを表現する（図１において、個々のストリートベクトルは、区別されない）。地形モデルのデータが、読み出され、それに従った高さ座標（ｚ）座標が、初期ストリートベクトルに対して使用される。

地形モデルは、公的なプロバイダによって提供される様々なデジタルモデルから選択され得る。デジタル地形モデル、例えば、レーザスキャンされたデジタル地形モデルは、地方政府および連邦政府によって、また米国商務省および対応する欧州政府機関などによって提供される。

初期ストリートベクトルは、コスト関数の計算によって、本発明に従って修正される。本実施例において、ストリートは、山間エリアに位置する。したがって、橋梁およびトンネルの建設コストが、見積もられる。コストは、特に、橋梁の長さおよび高さと、トンネルの長さおよび深さとによって与えられる。実際の道路建設は、建設コストを考慮に入れて、実行されることが期待される。したがって、実際のストリート高さプロファイルは、トンネルおよび橋梁に対するコストを見積もることによって、得られ得る。

本実施例において、図１に示されるストリート区間を表現する全てのストリートベクトルに対する全体コスト関数が、最小化される。全体コスト関数Ｃは、特に、Ｎ個の橋梁

およびＭ個のトンネル

に対する建設コストに対する計算を含む。ここで、実際には、これらのコストは、関連コストであることが期待される。したがって、最小化されるべきコスト関数は、

として計算され得る。ここで、Ｌ_Ｂ，ｉ、およびＬ_Ｔ，ｊは、ｉ番目の橋梁およびｊ番目のトンネルの長さをそれぞれ示し、ＨＰ_Ｂ，ｉ、ＨＰ_Ｔ，ｊ、およびＨＰ_ＴＭは、橋梁、トンネル、および使用される地形モデルの高さプロファイル関数（ｚ（ｘ，ｙ））をそれぞれ示す。トンネルおよび橋梁によってカバーされる面積エレメントｄｘｄｙを有する表面積にわたって、積分が行われる。

本実施例において、Ｃの最小化は、図１に破線の二重線で示される２つのトンネルと、実線の二重線で示される１つの橋梁によって、地形モデルとは異なるストリートベクトルに対して得られる。したがって、デジタルマップに含まれるストリート区間は、トンネル２と橋梁３とを含む。実際、現実のストリートが、主として、コストの考慮に基づいて建設される場合、コスト関数Ｃの最小化によって得られたストリートベクトルによって与えられるデジタルストリートは、当該分野で利用可能でなかった非常に高い精度を有する物理的なストリートの高さプロファイルのリアルな表現を提供する。

図２は、デジタルマップのストリートのストリートベクトルを生成するために、開示された方法の一実施例を説明する流れ図を示す。データは、地形モデルから読み出される１０。データは、特に、高さ座標を含み、高さ座標は、地形モデルから採られた高さ座標を用いて、ストリートベクトルを生成することによって、ストリートベクトルを初期化するために使用される１１。

コスト関数は、物理的ストリートの所望のデジタル表現を構成するストリートベクトルに対して計算される。上述されたような橋梁およびトンネルに対する建設コストに関する情報に加え、本実施例に従うコスト関数は、地形モデルによって与えられる表面からストリート表面までの距離によって与えられる寄与

も含む。ここで、ＨＰ_{Ｓｔｒｅｅｔ}は、ストリートの高さプロファイルを示す。この寄与は、地表から掘削された量、あるいは地表に盛られた量を推測する。

これらのストリートベクトルは、コスト関数が最小化されるデジタルマップに含まれるべきストリートに対して決定される１３。引き続き、ストリートのリアルな三次元コースの表示を可能にするために、所望のストリートを構成する決定されたストリートベクトルが、格納され、デジタルマップに挿入される。

図３は、デジタルマップのストリートのストリートベクトルを生成するために、開示された方法の別の実施例を説明する流れ図を示す。利用可能な地形モデルのデータに基づいて、ストリートベクトルは、再び初期化される２０。これは、ストリートベクトルが、地形モデルに適合し、同一平面である（ストリートベクトルと地形モデルの高さレベルとの間に高さの差がない）ことを意味する。

次いで、全ストリートベクトルの勾配が、計算される２１。本例において、個々のストリートベクトルは、高さ座標ｚ＝ｓｘ＋ｇを有する線形関数によって表わされる。ここで、ｘは、平面座標、ｓは、傾き、ｇは、定数である。勾配の計算は、傾きｓを決定することによって実行される。傾きは、ｘに対してｚの微分を数値的に実行することによって決定され得る。

各ストリートベクトルに対して、決定された勾配は、所定の下限および上限と比較される。これらの上下限は、異なるクラスのストリートに対して、異なるように選択される。例えば、上下限は、主要道路、脇道、高速道路などのクラスに対して選択される。さらに、ストリートは、クロソイドモデル（上述の議論参照）に従って建設される道路と、その方法で建設されなかった道路とに分類され得る。

ストリートベクトルの計算された勾配の一部について、勾配に対する上下限が、守られない場合、これらのストリートベクトルは、個々のストリートベクトルの起点および／または終点の高さ座標の値を、何らかの所定の値によってインクリメントまたはデクリメントすることによって修正される２２。この値は、修正されるべきストリートベクトルの起点の高さ座標の値と、このストリートベクトルの終点の高さ座標の値との間の差のある割合として、与えられ得る。

起点／終点をインクリメント／デクリメントすることによって、個々のストリートベクトルを修正した後に、勾配は、再計算され、再び、その勾配が、上限を超えているか否か、あるいは下限を下回るか否かがチェックされる。勾配の値が、依然として、所定の許容範囲内にない場合、起点／終点の修正は、所定の上下限が守られるまで、繰り返される。

次いで、所定の許容差内の勾配を有するストリートベクトルによって与えられるストリートのコース全体が計算される。コストの計算は、特に、トンネルおよび橋梁の建設コストの計算を含む２３。ストリートベクトルの高さ座標を変化させることによって、コストは最小化される２４。これらのストリートベクトルは、全体コストが最小化されるために、デジタルマップの物理的ストリートを表現するように決定される。

図１は、トンネルおよび橋梁に対するコストを含むコスト関数を最小化することによって、本発明の実施例に従って生成されたストリートプロファイルを示す。 図２は、本発明の実施例に従って、最小化されたコスト関数に基づいて、デジタルマップ内にストリートを挿入することを説明する流れ図を示す。 図３は、本発明の実施例に従って、最小化されたコスト関数とストリートベクトルの勾配の計算とに基づくストリートベクトルの決定を説明する流れ図を示す。

符号の説明

１ ストリート高さプロファイル
２ トンネル
３ 橋梁

Claims (15)

1. デジタルマップのストリートのストリートベクトルを生成する方法であって、
   地形モデルのデータを読み出すステップと、
   該地形モデルの該読み出されたデータに含まれる高さ座標を用いて該ストリートベクトルを初期化するステップと、
   該ストリートの該初期化されたストリートベクトルに対するコスト関数を計算するステップと、
   少なくとも一つのストリートベクトルの該高さ座標を変化させることによって、該コスト関数を最小化するステップと、
   該コスト関数が最小化される該ストリートベクトルを決定するステップと
   を包含する、方法。
2. 前記コスト関数を最小化する前記ステップの間、前記ストリートベクトルにおいて、他のストリートのストリートベクトルが交差している全交差点の前記高さ座標を維持するステップをさらに包含する、請求項１に記載の方法。
3. ａ）前記ストリートベクトルのそれぞれの勾配を計算するステップと、
   ｂ）該計算された勾配が、所定の下限と上限との間にあるかどうかを決定するステップと、
   ｃ）該所定の下限より小さい勾配または該所定の上限より大きい勾配を有する該ストリートベクトルそれぞれの起点および／または終点の高さ座標を修正するステップと、
   ｄ）ステップｃ）で修正された高さ座標を用いて、該ストリートベクトルのそれぞれの勾配を計算して、該計算された勾配が、所定の下限と上限との間にあるかどうかを決定するステップと、
   ｅ）該ストリートベクトルそれぞれの該計算された勾配が、該所定の下限と上限との間に入るまで、上記ステップｃ）〜ｄ）を実行するステップと
   をさらに包含し、
   前記コスト関数は、該所定の下限と上限との間にある該勾配を有するストリートベクトルの該高さ座標のみを変化させることによって最小化される、請求項１または請求項２に記載の方法。
4. ａ）前記ストリートベクトルのサブセットの全体勾配、または全ストリートベクトルの全体勾配を計算するステップと、
   ｂ）該計算された全体勾配が、所定の下限と上限との間にあるかどうかを決定するステップと、
   ｃ）該計算された全体勾配が、該所定の下限を下回る場合、あるいは該所定の上限を超える場合、該全体勾配が計算された該ストリートベクトルのうちの少なくとも一つのストリートベクトルの起点および／または終点の高さ座標を修正するステップと、
   ｄ）該全体勾配が、該所定の下限と上限との間に入るまで、上記ステップａ）〜ｃ）を実行するステップと
   をさらに包含し、
   前記コスト関数は、該所定の下限と上限との間にある該全体勾配に対するストリートベクトルの該高さ座標のみを変化させることによって最小化される、請求項１または請求項２に記載の方法。
5. 前記所定の下限より小さい計算された勾配、あるいは前記所定の上限より大きい計算された勾配を有する前記ストリートベクトルそれぞれの前記起点および／または前記終点の前記高さ座標は、所定の値によって、インクリメントまたはデクリメントされる、請求項３または請求項４に記載の方法。
6. 前記ストリートのストリートクラスが、決定され、前記下限および前記上限は、該決定されたストリートクラスに基づいて、事前に決定される、請求項３または請求項４に記載の方法。
7. 前記ストリートクラスを決定するステップは、前記ストリートがクロソイドモデルに従って建設されているかどうかを決定するステップを包含する、請求項６に記載の方法。
8. 前記コスト関数は、トンネルおよび／または橋梁に対するコスト、および／または前記ストリートベクトルを初期化するために使用された高さ座標に対して、ストリート高さを上げるコストおよび／または下げるコストを備える、請求項１〜請求項７のいずれか１項に記載の方法。
9. 前記コスト関数は、トンネルの長さおよび深さ、および／または橋梁の長さおよび高さ、および／または前記決定されたストリートベクトルによる前記ストリートの高さプロファイルと前記地形モデルの対応する高さプロファイルとの差によって規定される面積および／または体積に基づいて計算される、請求項８に記載の方法。
10. 前記請求項１〜請求項９のいずれか１項に記載の方法の前記ステップを実行するコンピュータで実行可能な命令を有する１つ以上のコンピュータ読み取り可能な媒体を備える、コンピュータプログラム製品。
11. ストリートベクトルを備えるストリートの少なくとも一つの三次元デジタル表現を備える、デジタルストリートマップであって、
    該ストリートベクトルが、コスト関数が最小化されるような高さ座標を含むことを特徴とする、
    デジタルストリートマップ。
12. 前記コスト関数は、トンネルの長さおよび深さによる寄与、および／または橋梁の長さおよび高さによる寄与、および／または前記ストリートの高さプロファイルと地形モデルの対応する高さプロファイルとの差によって規定される面積および／または体積による寄与を含む、請求項１１に記載のデジタルマップ。
13. 前記少なくとも一つのストリートの２つの交差点の間の各区間が、所定の下限と上限との間にある勾配を有するか、および／または該少なくとも一つのストリート全体が、所定の下限と上限との間にある全体勾配を有するか、および／または前記ストリートベクトルのそれぞれが、所定の下限と上限との間にある勾配を有する、請求項１１または請求項１２に記載のデジタルマップ。
14. 前記ストリートは、ストリートクラスに分類され、前記所定の下限と上限とは、前記少なくとも一つのストリートが属するストリートクラスに基づいて、および／または該少なくとも一つのストリートがクロソイドモデルに従って建設されているかどうかの決定に基づいて決定される、請求項１３に記載のデジタルマップ。
15. マップデータベースを備えるナビゲーションシステム、特に、車両ナビゲーションシステムであって、該マップデータベースは、請求項１１〜請求項１４のいずれか１項に記載のデジタルマップを備える、ナビゲーションシステム。

Images