最新運転者支援システムのための幾何学形状の作成
【課題】最新運転者支援システム（ＡＤＡＳ）、特に、ＡＤＡＳにおける使用に向けて幾何学形状を作成する技術を提供する。
【解決手段】ＡＤＡＳのための幾何学形状を作成する方法及びシステムを説明する。セグメントのシーケンスであるリンクチェーンが作成される。リンクチェーンは、２Ｄスプラインを作成するために用いられる。リンクチェーン、２Ｄスプライン、及び高度データを用いて３Ｄスプラインが作成される。３Ｄスプライン及び恐らく２Ｄスプラインも、２Ｄポリラインを作成するのに用いることができるベジエ曲線に変換される。ＡＤＡＳアプリケーションは、ベジエ曲線及び２Ｄポリラインを用いてＡＤＡＳ機能を提供することができる。
【解決手段】ＡＤＡＳのための幾何学形状を作成する方法及びシステムを説明する。セグメントのシーケンスであるリンクチェーンが作成される。リンクチェーンは、２Ｄスプラインを作成するために用いられる。リンクチェーン、２Ｄスプライン、及び高度データを用いて３Ｄスプラインが作成される。３Ｄスプライン及び恐らく２Ｄスプラインも、２Ｄポリラインを作成するのに用いることができるベジエ曲線に変換される。ＡＤＡＳアプリケーションは、ベジエ曲線及び２Ｄポリラインを用いてＡＤＡＳ機能を提供することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への参照
本出願は、２００８年１０月１日出願の「最新運転者支援システムのための幾何学形状の作成」という名称の米国特許仮出願第６１／１０１、７５２号の恩典を請求する。米国特許仮出願出願番号第６１／１０１、７５２号の全開示内容は、本明細書に引用によって組み込まれている。
本特許出願は、本明細書に引用によって組み込まれている「最新運転者支援システムアプリケーションのためのベジエ曲線」という名称の同じ日付に出願された現在特許出願中の特許出願出願番号第＿＿＿＿号、代理人整理番号Ｎ０２９５ＵＳに関連している。
本発明は、一般的に、最新運転者支援システム（ＡＤＡＳ）に関し、より具体的には、ＡＤＡＳにおける使用に向けて幾何学形状を作成することに関する。
【背景技術】
【０００２】
ＡＤＡＳは、運転の快適さ、効率、安全性、及び全体的な満足感を改善するために開発されたものである。これらの最新運転者支援システムの例は、適応ヘッドライト照準、適応走行制御、車線逸脱警告及び制御、カーブ警告、速度制限通知、ハザード警告、予測走行制御、適応変速制御、並びにその他を含む。これらの最新運転者支援システムの一部は、車両の現在の状態及び車両の前方にある車道の現在の状態を判断するために車両内の様々なセンサ機構を用いる。これらのセンサ機構は、デジタルビデオカメラ及びＬＩＤＡＲのようなレーダー、赤外線、超音波、及び視覚指向性センサを含むことができる。
【０００３】
一部の最新運転者支援システムはまた、デジタル地図データを用いる。これらのシステムは、時によっては地図援用ＡＤＡＳと呼ばれる。デジタル地図データは、最新運転者支援システムにおいて道路網、道路幾何学形状、道路状態、並びに車両の周囲の道路及び地形に関連する他の項目に関する情報を提供するのに用いることができる。一部のセンサとは異なり、デジタル地図データは、霧、雨、又は雪のような環境の状態による影響を受けない。更に、デジタル地図データは、曲率、断勾配、横傾斜、標識によって示されていない速度制限、及び車線制限などのようなセンサによっては確実には供給することができない有利な情報を提供することができる。更に、デジタル地図データは、車両の前方、曲がり角付近、坂の向こう側、又は障害物の向こう側の道路を判断するために、センサの範囲を十分に超えるか又は運転者の視界さえ超える予測機能を提供することができる。従って、デジタル地図データは、一部の最新運転者支援システムに対して有用な追加物とすることができる。
【０００４】
地図援用最新運転者支援システムは、一般的に、車両内のナビゲーションシステムに付随する地理データベースからのデータを用いる。ナビゲーションシステムのデータベースは、道路及び交差点の場所（高度を含む地理座標）、道路名、道路に沿った速度制限、交差点での右左折制限、道路に沿った住所又は住所範囲、各道路における車線数、車線幅、車線境界線、道路の機能部類、及び中央分離帯の場所などのような地域内の道路網を表すデータを収容する。ナビゲーションシステムのデータベースはまた、水域、公園、行政区域（地方自治体、州、及び国の境界を含む）、及び会社、病院、及び警察署などのような肝心な点の場所のような他の地理的特徴に関する情報を収容することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許仮出願第６１／１０１、７５２号
【特許文献２】米国特許公開第２００６／０１００７８０号
【特許文献３】米国特許第６、４０５、１２８号
【特許文献４】米国特許第７、０８４、８８２号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ナビゲーションシステムのデータベースは、最新運転者支援システムが必要とするものよりも非常に多くのデータを有する。更に、ナビゲーションに向けて設計された地理データベースは、全てのデータを有していない場合があり、及び／又は最新運転者支援システムによって必要とされる精度レベルでデータを有していない場合がある。その結果、特に最新運転者支援システムに向けた地理データベースの設計には何らかの労力が費やされてきた。例えば、米国特許公開第２００６／０１００７８０号は、自動車システム内のセンサデバイスに向けて設計されたデータ記憶フォーマットを有する地理データベースを説明している。しかし、特に最新運転者支援システムに向けて設計された地理データベースには、改善の余地がある。
【課題を解決するための手段】
【０００７】
ＡＤＡＳのための幾何学形状を作成する方法及びシステムを説明する。ソフトウエアルーチンを用いて、道路セグメントのシーケンスであるリンクチェーンが作成される。ソフトウエアルーチンは、関連の機能部類を有する最初の道路セグメントを選択する。各ノードにおいて、ソフトウエアルーチンは、リンクチェーンに追加する次の道路セグメントを選択する。リンクチェーンは、末端ノードを見つけるまで成長し続ける。
リンクチェーンに対して当て嵌めが行われ、２ＤのＢ−スプラインが作成される。２ＤのＢ−スプラインは、不規則性及びアラインメント問題を補正するために操作される。位置、曲率、勾配、及び／又は車両方位を保持するのに必要のない結び目は、記憶要件を最小にするために削除される。
【０００８】
リンクチェーン、最適化された２ＤのＢ−スプライン、及び高度データが用いられて、３Ｄスプラインが作成される。好ましくは、高度データは、車両が道路セグメントによって表される道路上を走行する時に収集されたＧＰＳ／ＩＭＵ記録から得られる。ＧＰＳ高度の不正確性に対処するために、高度データは、交差ノードの位置で補正される。補正された高度データを用いて、リンクチェーンに対して当て嵌めが行われて高度Ｂ−スプラインが作成される。２ＤのＢ−スプラインと高度Ｂ−スプラインは融合され、３ＤのＢ−スプラインが得られる。２ＤのＢ−スプラインと同様に、記憶要件を最小にするために位置、曲率、勾配、及び／又は車両方位を保持するのに必要のない結び目は、３ＤのＢ−スプラインから削除される。
３ＤのＢ−スプライン及び場合によっては２ＤのＢ−スプラインは、ベジエ曲線に変換される。ベジエ曲線は、２Ｄポリラインを効率的に作成して曲率、勾配、及び車両方位を計算するのに用いることができる。ＡＤＡＳアプリケーションは、マップ照合に向けてＡＤＡＳ機能及びポリラインを提供するためにベジエ曲線を用いることができる。
【０００９】
これら並びに他の態様及び利点は、適切な場合は添付図面を参照して以下の詳細説明を読解することにより当業者には明らかになるであろう。更に、この要約は例に過ぎず、特許請求する本発明の範囲を限定する意図はないことを理解されたい。
同様の参照番号が様々な図における同様の要素を指す添付図面の図を併用して現時点で好ましい実施形態を下記に説明する。
【図面の簡単な説明】
【００１０】
【図１】実施例による地図援用ＡＤＡＳアーキテクチャのブロック図である。
【図２】実施例による図１に描かれたプロセッサに利用可能なソフトウエアアプリケーションのブロック図である。
【図３】実施例による図１に描かれた地理データベースからの道路セグメントデータ記録のブロック図である。
【図４】実施例による図３に描かれた道路セグメントデータ記録におけるデータ属性のブロック図である。
【図５】実施例によりＡＤＡＳのための幾何学形状を作成するための流れ図である。
【図６】例示的なベジエ曲線の図である。
【図７】ベジエ曲線から生成された例示的なポリラインの図である。
【図８】実施例によりリンクチェーンを作成するための流れ図である。
【図９】実施例により２ＤのＢ−スプラインを作成するための流れ図である。
【図１０】実施例による不整合Ｂ−スプライン端の図である。
【図１１】実施例による整合Ｂ−スプライン端の図である。
【図１２】実施例により２ＤのＢ−スプラインをリンクチェーンに当て嵌めるための流れ図である。
【図１３】実施例による一般的な四葉のクローバー状ランプにおけるランプスプライン形状の図である。
【図１４】実施例によるランプノードオフセット法の図である。
【図１５】実施例による３ＤのＢ−スプラインを作成するための流れ図である。
【図１６】実施例による標高補正ルーチンの流れ図である。
【発明を実施するための形態】
【００１１】
ＡＤＡＳアーキテクチャ
図１は、地図援用ＡＤＡＳアーキテクチャ１００のブロック図を示している。この例では、地図援用ＡＤＡＳアーキテクチャ１００は、運転者支援アプリケーション１１４、並びに地図及び測位エンジン（ＭＰＥ）１１６を含む。図１では、ＭＰＥ１１６を独立型モジュールとして示しているが、ＭＰＥ１１６は、複数のパッケージに分散させることができ、及び／又はセンサパッケージのような他のデバイスパッケージ内に統合することができることを理解されたい。ＭＰＥ１１６は、プロセッサ１０２、測位システム１０４、地理データベース１０６、通信システム１０８、及び車両内データバスインタフェース１１０を含む。ＭＰＥ１１６はまた、メモリ及び電源のような他のハードウエア、ソフトウエア、及び／又はファームウエアを含むことができる。
【００１２】
プロセッサ１０２は、あらゆる種類のプロセッサ、コントローラ、又は他のコンピュータデバイスとすることができる。例えば、プロセッサ１０２は、デジタル信号プロセッサとすることができる。プロセッサ１０２は、測位システム１０４、地理データベース１０６、通信システム１０８、車両内データバスインタフェース１１０、及びその他の供給源からの入力を受信する。次に、プロセッサ１０２は、一部を図２を参照して説明するアプリケーションソフトウエアプログラム２００を用いてこれらの入力を処理する。
【００１３】
次に、プロセッサ１０２は、車両内データバスインタフェース１１０及びデータバス１１２を通じて運転者支援アプリケーション１１４に出力を供給する。好ましくは、車両内データバスインタフェース１１０及びデータバス１１２は、自動車用途に向けて設計されたコントローラエリアネットワーク（ＣＡＮ）インタフェース及びＣＡＮバスである。運転者支援アプリケーション１１４は、適応ヘッドライト照準、適応走行制御、障害物検出、障害物回避、衝突回避、適応変速制御、及びその他を含むことができる。
【００１４】
測位システム１０４は、ＧＰＳ型技術、推測航法型システム、又はこれらの組合せ、又は当業技術で公知の他のシステムを利用することができる。また、測位システム１０４は、走行距離、速度、方向、及び姿勢などを測定する適切な感知デバイスを含むことができる。例えば、測位システム１０４は、ＧＰＳシステム及びジャイロスコープを含むことができる。測位システム１０４は、プロセッサ１０２に出力信号を供給する。プロセッサ１０２上で作動するアプリケーションソフトウエアプログラム２００の一部は、ＭＰＥ１１６の場所、方向、及び姿勢などを判断するのに測位システム１０４からの出力信号を用いる。
【００１５】
地理データベース１０６は、ＡＤＡＳアプリケーションに向けて設計される。ナビゲーションシステムの地理データベースと同様に、地理データベース１０６は、地理的領域内の道路及び交差点に関するデータを含む。例えば、地理データベース１０６は、各道路セグメント（リンクとも呼ぶ）に対して少なくとも１つのデータベース記録（「エンティティ」又は「エントリ」とも呼ぶ）を含む。道路セグメントがＢ−スプライン曲線又はベジエ曲線で表される時には、道路セグメントデータ記録は、制御点の地理座標（例えば、緯度、経度、及び高度）を与えるデータを含む。道路セグメントの端点（ノードとも呼ぶ）は、最初及び最後の制御点に対応する。更に、道路セグメントデータ記録はまた、Ｂ−スプライン幾何学に関する結び目ベクトルを収容することもできる。
道路セグメントが形状点幾何学形状として表される時には、道路セグメントデータ記録は、表される道路セグメントの端点の地理座標（例えば、緯度、経度、及び高度）を与えるデータを含む。曲線セグメントでは、道路セグメントデータ記録は、ポリラインを特徴付けるのに用いられる形状点の地理座標（例えば、緯度、経度、及び高度）を与えるデータも含む。
【００１６】
道路セグメントデータ記録に対して、図３を参照してより詳しく説明する。
地理データベース１０６は、一般的にナビゲーションシステムの地理データベースに含まれるデータよりも高い品質（すなわち、正確な）データを含むことができる。例えば、道路幾何学形状に関して、地理データベース１０６内のデータは、経度、緯度、及び／又は高度に関してより正確なものとすることができる。また、地理データベース１０６では、トンネルの開始場所及び終了場所をより正確に指定することができる。更に、地理データベース１０６内のデータは、曲率のような導出情報に関してより正確なものとすることができる。
【００１７】
また、地理データベース１０６は、一般的に、ナビゲーションシステムの地理データベースに含まれるデータよりも多くの種類のデータ（例えば、多くの種類の属性）を含むことができる。例えば、地理データベース１０６は、標識及び横断歩道のような道路物体に関するデータを道路セグメントに沿ったこれらの位置、標識物体種類、及び標識テキストを含めて含むことができる。地理データベース１０６内に見られるデータ属性の一部に対して、図４を参照して説明する。
【００１８】
図２は、プロセッサ１０２に対して利用可能なソフトウエアアプリケーション２００の一部を示しているブロック図である。図２に示しているソフトウエアアプリケーション２００は、地図アクセスアプリケーション２０２、地図更新アプリケーション２０４、車両測位アプリケーション２０６、電子視野アプリケーション２０８、及びインタフェースアプリケーション２１０を含む。これは、プロセッサ１０２に対して利用可能な全てのソフトウエアアプリケーション２００の網羅的なリストではないので、図２は、始動ルーチン、及び自己試験診断などを含むことができる他のアプリケーション２１２も示している。
【００１９】
地図アクセスアプリケーション２０２は、物理的記憶媒体上に記憶された地理データベース１０６へのデータアクセスを提供する。地図アクセスアプリケーション２０２は、プロセッサ１０２からデータ要求を受信し、この要求に応じるデータを物理的記憶媒体上で探し出す。好ましくは、地図アクセスアプリケーション２０２は、プロセッサ１０２及び／又はアプリケーション２００による使用に向けて、アプリケーションプログラミングインタフェース（ＡＰＩ）を提供する。
【００２０】
地図更新アプリケーション２０４は、地理データベース１０６に対する更新を容易にする。通信システム１０８は、既存のデータベースに付加的な受信範囲を追加するか、又は既存のパーセルを置換するかのいずれかを行う１つ又はそれよりも多くのパーセルを受信する。パーセルは、物理的記憶媒体上の地理データベース１０６内に地理データを記憶するための記憶単位である。新しいパーセルに対しては、地図更新アプリケーション２０４は、物理的記憶媒体上にこのパーセルを記憶する。既存のパーセルに対しては、地図更新アプリケーション２０４は、物理的記憶媒体上の古いパーセルを新しいパーセルで置換する。
車両測位アプリケーション２０６は、地理データベース１０６内に含まれるデータによって表される道路網に対する車両の位置を判断する。車両測位アプリケーション２０６は、測位システム１０４からの出力を用い、時によってマップ照合アルゴリズムと呼ぶ車両測位アルゴリズムを用いて、この出力を地理データベース１０６内のデータと照合する。
【００２１】
電子視野アプリケーション２０８は、電子的視野を判断する。電子的視野は、電子視野アプリケーション２０８によって判断される範囲の現在の車両位置から前方の道路及び交差点の集合である。この道路及び交差点の集合は、車両が現在の車両位置から辿ることができる潜在的な経路である。電子視野アプリケーション２０８は、１つ又はそれよりも多くのコスト関数を用いて範囲を判断する。コスト関数は、運転者支援アプリケーション１１４の要求に基づいて、車両速度、走行時間、及び運転距離のような様々な要因を考慮に入れることができる。例示的な電子視野アプリケーションは、本出願と同じ出願人に譲渡され、本明細書においてその全内容が引用により組み込まれている米国特許第６、４０５、１２８号に説明されている。
【００２２】
インタフェースアプリケーション２１０は、インタフェース１１０及びバス１１２を通じたＭＰＥ１１６と運転者支援アプリケーション１１４の間の通信を制御する。好ましくは、インタフェースアプリケーション２１０は、車両内の様々な電子デバイス間で通信を行うためのシリアル通信プロトコルであるＣＡＮプロトコルに基づいている。メッセージ及びデータを車両内の１つの電子デバイスから別のものへと送信することができるように、ＣＡＮプロトコルに従って車両内の様々な電子デバイスを単一のシリアルバス（例えば、バス１１２）に結合することができる。ＣＡＮプロトコルは、ＣＡＮフレームが共通ＣＡＮバス上に置かれるメッセージベースのプロトコルである。ＣＡＮバスは、単一のワイヤ又は差動的に駆動されるワイヤ対とすることができる。
【００２３】
図３は、地理データベース１０６からの道路セグメントデータ記録３００のブロック図である。道路セグメントデータ記録３００は、道路の一部分を表すために用いられるデータを含む。これらのデータは、セグメントの端点の緯度、経度、及び高度の座標位置を示すノードデータ３０２、３０４を含む。
また、データは、直線又は曲線セグメントの形状を表すために用いることができる制御点の緯度、経度、及び高度の座標位置を示す制御点データ３０６、３０８を含む。図３には２つの制御点に関するデータを示しているが、セグメントは、１つよりも多くの曲線を含むことができ、制御点数は、セグメント内の曲線の数及び形状に依存するものとすることができることを理解されたい。例えば、各３次ベジエ曲線は、４つの制御点によって表されるが、前のベジエ曲線の最後の制御点は、次のベジエ曲線の最初の制御点と同じである。道路セグメントデータ記録３００は、ベジエ曲線の数を３倍し、１を足した数に等しい数の制御点に関するデータを記憶する。
【００２４】
更に、データは、セグメントに関する属性３１０を含む。セグメントの属性３１０の一部を図４に示す。同様に道路セグメントデータ記録３００は、形状点データのような追加データを含むことができる。
図４は、道路セグメントデータ記録３００におけるデータ属性３１０の一部のブロック図である。図４に示しているデータ属性３１０は、セグメント識別子（ＩＤ）４０２、制御点４０４、走行方向４０６、速度カテゴリ４０８、車線カテゴリ４１０、道路種類４１２、セグメント特性４１４、及び通行特性４１６を含む。これは、道路セグメントデータ記録における全てのデータ属性の網羅的なリストではないので、図４は、他の属性４１８も示している。例えば、セグメントデータ属性４００は、セグメントの端点３０２、３０４に対応するノードＩＤの形態のノードデータ記録への参照子を含むことができる。
セグメントＩＤ４０２は、地理データベース１０６内のデータ記録を識別する。
【００２５】
制御点属性４０４は、曲率及び勾配プロフィールの作成を助ける制御点に関する追加情報を提供するビットフラグを収容する。例えば、制御点属性４０４は、制御点毎にバイトサイズのフラグを含むことができる。フラグ内のビットのうちの１つは、曲率に割り当てられ、一方、ビットのうちの別のものは、勾配に割り当てられる。曲率ビットフラグが１に設定された場合には、制御点は、曲率プロフィールの一部としてマーク付けされる。同様に勾配ビットフラグが１に設定された場合には、制御点は、勾配プロフィールの一部としてマーク付けされる。
【００２６】
走行方向属性４０６は、セグメントにおいて許可される車の流れの方向を表している。例えば、セグメントは、道路網のうちで走行が双方向に許された部分を表すことができる。代替的に、セグメントは、道路網のうちで一方向の走行だけを可能にする部分を表すことができる。走行方向属性４０６は、セグメントが双方向走行又は単方向走行のいずれを可能にするのかを識別し、単方向の場合には、走行方向属性４０６は、許可された走行方向を更に識別する。
【００２７】
速度カテゴリ属性４０８は、掲示又は示唆された速度制限に基づく道路の一般的な速度傾向を表している。速度カテゴリ属性４０８は、速度範囲に関連するデータを含む。例えば、速度カテゴリ属性４０８は、８０ｍｐｈを超える速度に対して整数１、６５ｍｐｈ〜８０ｍｐｈの範囲の速度に対して整数２、５５ｍｐｈ〜６４ｍｐｈの範囲の速度に対して整数３、及び速度範囲が０ｍｐｈを含むまで以降同様に続くデータ表現を含むことができる。
【００２８】
車線カテゴリ属性４１０は、セグメントにおける１つの走行方向の主な車線数を表している。好ましくは、車線カテゴリ属性４１０は、右左折車線を含まない。車線数が各方向において異なる場合には、車線カテゴリ属性４１０は、大きい方の数を表すことができる。
道路種類属性４１２は、道路の種類及び／又はセグメントが表す機能部類を表している。例えば、道路種類属性４１２は、州間高速道路、通行制御高速道路、歩行者通路等に関連付けられたデータを含むことができる。
【００２９】
セグメント特性属性４１４は、様々なセグメント特性を説明するビットフラグを含む。例えば、セグメント特性属性４１４は、セグメントが舗装されているか、ランプであるか、橋であるか、トンネルであるか、及び環状交差点であるかなどを識別することができる。
アクセス特性属性４１６は、セグメントにおいて許可される交通の種類を定めるビットフラグを含む。例えば、アクセス特性属性４１６は、セグメントにおいて自動車、バス、トラック、タクシー、緊急車両、及び歩行者等が許可されているか否かを識別することができる。
【００３０】
ＭＰＥのための幾何学形状の作成
図５は、ＭＰＥ１１６のための幾何学形状を作成する方法５００の流れ図である。ブロック５０３では、方法５００は、並列処理を可能にするために地理データベース５０２をタイルへと再分割する。地理データベース５０２は、地理データベース１０６又は地理データベース１０６内のデータを含む異なるデータベースとすることができる。
これらのタイルは、各タイルがほぼ等量のノード及び形状点を含むように形成される。地図表面は、細かい（約２ｋｍ×２ｋｍ）セルを有する架空の２Ｄ矩形格子によって覆われる。次に、地理データベース５０２内のノード及び形状点を格子上にマップすることによってノード及び形状点の密度が計算される。タイルは、格子セルから組み立てられる。
各タイルがほぼ等しい数のノード及び形状点を有することを保証するために、格子全体は、水平及び垂直の両方の方向の格子線に沿って半分に再帰的に再分割され、２つの分割区分の各々が等しい数の幾何点を含むようにする。この処理は、タイルが、所定の閾値よりも少ない量のノード及び形状点を含むまで続く。各再分割の方向は、タイルのアスペクト比を最小にするように選択される。
【００３１】
ブロック５０４では、方法５００は、地理データベース５０２からのデータを用いて各タイル内でリンクチェーンを作成する。リンクチェーンは、各々が同じ道路種類属性４１２を有するセグメントのシーケンスである。好ましくは、セグメントシーケンスは、可能な限り長く作られる。リンクチェーンは、セグメント境界を横切る滑らかさを保証するＢ−スプライン当て嵌めを実施するのに用いられる。リンクチェーン５０４を作成する処理に対しては、図８に関連してより詳しく説明する。
【００３２】
ブロック５０６では、方法５００は、ブロック５０４で作成されたリンクチェーンを用いて２ＤのＢ−スプラインを作成する。ブロック５０８では、方法５００は、ブロック５０４で作成されたリンクチェーン、ブロック５０６で作成された２ＤのＢ−スプライン、及び高度データ５０７を用いて３ＤのＢ−スプラインを作成する。好ましくは、高度データ５０７は、道路セグメントによって表される道路上を車両が走行する時に収集されるＧＰＳ／ＩＭＵ記録から得られる。しかし、高度データ５０７は、他の供給源及び／又はセンサから得ることができる。２ＤのＢ−スプライン５０６を作成する処理に対しては、図９に関連して説明し、一方、３ＤのＢ−スプライン５０８を作成する処理に対しては、図１５及び図１６に関連して説明する。
【００３３】
スプラインは、曲線区間を表して区間の境界において指定の条件を満たす区分的多項式関数で形成されるあらゆる複合曲線を指す。すなわち、Ｂ−スプラインを含む多くの種類のスプライン曲線が存在する。Ｂ−スプラインは、制御点及び結び目を有する。結び目は、多項式スプライン曲線の個々の多項式曲線セグメントが互いに接合する点である。セグメントは、完全な曲線の滑らかさを生じるように接合される。結び目ベクトルは、スプライン曲線に沿ってセグメントが開始及び終了する点を説明する非減少浮動小数点数の序列リストである。スプラインは、当業技術で公知である。
【００３４】
スプラインを用いると、道路のカーブしている部分を含む地図特徴は、望ましい精度で地理特徴の形状に適合する曲線を生成するように判断された係数を有する多項式によって表される。従って、スプラインは、多項式の係数を指定することにより、基本的道路幾何学形状を説明するための手段である。米国特許第７、０８４、８８２号に説明されているように、スプラインは、ナビゲーションシステムのデータベースにおいて道路セグメントの形状を表すのに用いられている。米国特許第７、０８４、８８２号は、本出願と同じ出願人に譲渡されており、本明細書に引用によって組み込まれている。
【００３５】
ブロック５１０では、２ＤのＢ−スプライン及び３ＤのＢ−スプラインをベジエ曲線に変換することができる。セグメントが高度データを持たない場合には、２ＤのＢ−スプラインは、ベジエ曲線に変換される。しかし、セグメントが高度データを確実に有する場合には、２ＤのＢ−スプラインは、ブロック５０８で３ＤのＢ−スプラインを作成することだけに用いることができる。
３次ベジエ曲線は、２つの端点及び曲線に対する接線に沿って位置決めされたこれらの端点における２つの追加制御点によって定められる。３次ベジエ曲線式は、ベクトル形式で次式のように書くことができる。
【００３６】
【数１】
【００３７】
ここで、Ｐ0、Ｐ1、Ｐ2、及びＰ3は制御点であり、ｔはパラメータである。ベジエ曲線は、公知の方法を用いてＢ−スプライン曲線から導出することができる。
【００３８】
スプライン幾何学は、道路セグメント幾何学形状を表す上では有利であるが、ＭＰＥ１１６におけるＢ−スプラインの使用は、車両測位及び電子視野アプリケーション２０６、２０８における計算要件を増大させる。解析的なＢ−スプライン幾何学は、車両測位アプリケーション２０６によるポリライン表現及び電子視野アプリケーション２０８による電子視野の実時間導出を容易にするためにベジエ表現に変換される。
【００３９】
ブロック５１２では、車両測位アプリケーション２０６が、２Ｄポリライン表現を実時間で導出することができるように、ベジエ曲線は分割される。方法５００は、道路幾何学形状が、弦から最も遠い点が弦線上に投影される時にこの点が弦の内側に収まるようなベジエ曲線を有することを仮定する。ベジエ道路幾何学形状は、図６に示しているように、ベジエ曲線から、この曲線の端点３０２、３０４を結ぶ線（すなわち、制御多角形の基本弦：
【００４０】
【数２】
【００４１】
）までの最も遠い距離（又は複数の距離）にある１つの点６００（又は場合によっては１つよりも多くの点）を識別した後に分割される。図６では、最も遠い距離が、一般的に、曲線の中心にはないことも分る。
【００４２】
最適な再分割点６００は、ベジエ曲線上で制御多角形の基本弦から最も遠い点である。点６００の位置は、点６００におけるベジエ曲線に対する２Ｄの接線Ｂ（ｔ）が弦に対して平行であるという条件から解析的に得られる。
【００４３】
【数３】
【００４４】
上記表現は、パラメータｔに関する２次方程式へと簡略化される。一般的なベジエ曲線では、この２次方程式は、パラメータｔが定められる間隔［０〜１］内に実根を有することができない。しかし、穏やかな挙動を示すベジエ曲線では、２次方程式は［０〜１］間隔内に１つ又は２つの実根を有することになる。２次方程式が２つの実根を有する場合には、２つの再分割点が２つの点でベジエ曲線を分割するように用いられる。点６００が得られた状態で、ベジエ曲線は、デ・カステリョの再分割アルゴリズムを用いて２つに分割される。得られるベジエ曲線は、地理データベース１０６に記憶される。
ブロック５１４では、車両測位アプリケーション２０６は、２Ｄポリライン表現を実時間で導出する。ポリライン表現の例７００を図７に示す。車両測位アプリケーション２０６は、ベジエ曲線の端点７０２を結び、その一方で内部制御点７０４を無視することによってポリライン表現７００を導出する。
【００４５】
リンクチェーンの作成
図８は、リンクチェーンを作成する方法８００の流れ図である。リンクチェーンを作成する方法８００は、ＭＰＥ１１６における使用に向けて地理データベース１０６内にデータを記憶する前に、あらゆるコンピュータ上で実行することができるソフトウエアルーチン（又は複数のソフトウエアルーチン）である。
ブロック８０２では、リンクチェーンルーチン８００は、リンクチェーンを開始するセグメントを選択する。各セグメントは２つのノード（端点とも呼ぶ）を有する。全てのノードが交差点にあるわけではない。例えば、一部のノードは、道路属性の変化を符号化するのに用いられる。
【００４６】
ブロック８０４では、リンクチェーンは、隣接するセグメントを含めることによって両方の方向に成長する。ブロック８０６では、リンクチェーンルーチン８００は、ノードが末端であり、そのノードにおいてその方向にリンクチェーンが終了されるかを判断する。リンクチェーンルーチン８００は、ノードが末端であるかを判断するために規則を用いる。ノードを通じてリンクチェーンを進めるべきか（すなわち、非末端ノード）を判断するための規則は、以下のものを含むことができる。
１．リンクチェーン内の２つの隣接セグメントが、共通ノードを有するべきである。
２．リンクチェーン内のセグメントは、同じ機能部類に属さなければならない。
３．セグメントは、１つのリンクチェーン内だけに含まれるべきである。
４．各セグメントは、リンクチェーン内に含まれるべきである。
５．環状交差点セグメント（すなわち、環状交差点属性４１４に関連付けられたセグメント）を含むリンクチェーンは、通常のセグメントを含んではならない。
６．２つのセグメント間の角度が所定の閾値を超える場合には、これらのセグメントは、リンクチェーンを形成してはならない。この規則は、環状交差点チェーンには適応可能ではない。
７．ノードは、少なくとも２つのリンクに接続する。
末端ノードを識別するための他の規則を用いることもできる。ブロック８０６においてリンクチェーンルーチン８００が末端ノードを識別した場合には、リンクチェーンルーチン８００は、ブロック８１４においてリンクチェーンを成長させるのを終了する。
【００４７】
ブロック８０６においてリンクチェーンルーチン８００が末端ノードを識別しなかった場合には、リンクチェーンルーチン８００は、ブロック８０８でノードを通じる最適経路を判断する。各ノードにおいて、リンクチェーンルーチン８００は、リンクチェーンに追加することができるノードを通じた可能な経路を識別する。
ブロック８１０では、リンクチェーンルーチンは、各識別された可能な経路に対する経路重みを計算する。経路重みは、車線カテゴリ属性４１０、道路種類属性４１２、並びにノードからの経路の角度、及びセグメントによって表される道路上に保護レールが設けられているか否かのような他の属性４１８を用いて判断される。更に、経路重みは、交差点を通じた方向変化量を制限するように判断される。
【００４８】
リンクチェーンを継続するのにどの経路を用いるかを判断する１つの方法は、リンク間角度及びリンク間の車線数差という２つの要因の組合せに基づいている。リンクチェーンが新しいリンクに継続される確率は、次式に従って判断することができる。
【００４９】
【数４】
ここで、
【数５】
及び
【数６】
【００５０】
ここで、角度は、度を単位とするリンク間角度であり、Δ車線＃は、リンク間の車線数差（１０を超えない）である。
２つよりも多くのリンクが交差するあらゆるノードにおいて、規則に準ずるリンクチェーンを形成する可能な方法は、計算された確率に従って比較及び順位付けされ、最適な選択肢が選択される。従って、リンクチェーンの形成は、リンクチェーンが作成される順序には依存しない。
【００５１】
ブロック８１２では、リンクチェーンルーチン８００は、ブロック８１０で計算された経路重みに基づいて、このノードを通じて継続を行うか否かを判断する。リンクチェーンルーチン８００が、このノード通じて進むように判断した場合には、最も高い重みを有する経路が選択され、ブロック８０４でリンクチェーンに追加される。そうでなければ、リンクチェーンルーチン８００は、ブロック８１４でリンクチェーンを成長させるのを終了する。
【００５２】
ブロック８１６では、リンクチェーンルーチン８００は、１つの操作で曲線当て嵌めを行うには長すぎるリンクチェーンを分割する。この判断は、チェーンの長さ（例えば、長さが２５ｋｍを超える）、ノード及び形状点の合計数（例えば、５０００を超える）、及び／又は他の要因に基づいて行うことができる。好ましくは、リンクチェーンルーチン８００は、ポリライン長さの中間部の近くで、リンクチェーンポリラインが可能な限り直線のところでリンクチェーンを分割する。
【００５３】
両方の目的を達成するために、リンクチェーンルーチン８００は、リンクチェーンの中間部の最も近くに位置するノードから開始して両方の方向に検索を開始する。考察対象のあらゆるノードに対して、リンクチェーンルーチン８００は、ノードの周囲に窓を構成し、このノードが比較的直線のセグメント内に位置するかを判断する。リンクチェーンルーチン８００は、内部点を２つの端点で形成されたセグメント上に投影し、点からセグメントまでの距離が閾値を超えず、これらの内部点が、セグメントの内部に投影されることを検証することによってセグメントが直線であるかを判断する。リンクチェーンルーチン８００は、目的を満たすノードを見つけるまで、両方の方向に検索し続ける。リンクチェーンルーチン８００は、分割に適するノードが見つからなかった場合には、直線セグメントの基準を緩和し、再度検索を繰り返す。
【００５４】
２ＤのＢ−スプラインの作成
図９は、リンクチェーンから２ＤのＢ−スプラインを作成する方法９００の流れ図である。方法８００と同様に、２ＤのＢ−スプラインを作成する方法９００は、ＭＰＥ１１６における使用に向けて地理データベース１０６内にデータを記憶する前に、あらゆるコンピュータ上で実行することができるソフトウエアルーチン（又は複数のソフトウエアルーチン）である。
ブロック９０２では、２ＤのＢ−スプラインルーチン９００は、方法８００によって作成されたリンクチェーンを２ＤのＢ−スプラインに当て嵌める。２ＤのＢ−スプラインルーチン９００は、２ＤのＢ−スプラインを単一のリンクチェーンであり、可能な場合はこのチェーンに隣接するリンクチェーンからのデータ点を両方の端に含むリンクチェーンに当て嵌める。隣接するリンクチェーンからのデータ点を含めることにより、２ＤのＢ−スプラインルーチン９００は、連続する曲線当て嵌めを重ね合わせ、それによって曲線当て嵌め間の境界における形状整合性を保証することができる。隣接するリンクチェーンからのデータ点をどの場合に用いるべきかに関する判断は、規則によって制御される。環状交差点は、隣接するリンクチェーンからのデータ点が用いられない場合の例である。隣接するリンクチェーンの重複は、大きい場合がある（一般的に、数キロメートル）。
【００５５】
２Ｄの曲線当て嵌め技術は、指定の曲線当て嵌め許容範囲に基づいて最適な局所曲線堅牢性を反復的に判断する。２ＤのＢ−スプラインルーチン９００は、変分法を用いてスプラインに沿った曲率変化を最小にすることによってスプライン当て嵌めを正則化する。曲線当て嵌めは、次の汎関数を最小にすることによって実行される。
【００５６】
【数７】
【００５７】
式１：曲線当て嵌め最小化汎関数、ここで、ｖj（ｓ）は、反復数［ｊ］において曲線に沿って変化する正則化量を表している。ｖj（ｓ）は、曲線に沿った弧長の関数として連続関数とすることができ、又はスプラインの各曲線セグメントに対する固有値のように離散的に実施することができる。
【００５８】
積分：
【数８】
は、当て嵌められた曲線に沿った曲率変化を表している。曲率変化を最小にする正則化関数は、代替的に、
【数９】
で表すことができる。最小二乗項：
【数１０】
は、当て嵌められた曲線とデータ点の間の偏差を示している。全体として、曲線当て嵌め最小化汎関数は、データ点からの偏差を最小にする一方、基本的道路幾何学形状を取り込むデータ点との対応を保ちながら、曲率が可能な限り小さく変化することを保証する。ブロック９０２におけるリンクチェーンへの２Ｄスプライン当て嵌めに対しては、図１２を参照してより詳細に説明する。
【００５９】
ブロック９０４では、２ＤのＢ−スプラインルーチン９００は、タイル内で不整合なＢ−スプライン端を整合化する。スプライン当て嵌めは重複するが、出会わないＢ−スプライン端１００２、１００４を示している図１０に示しているように、得られるＢ−スプラインの全てがノードにおいて完全に接合するわけではない。図１１に示しているように２つのＢ−スプラインをノード１１００で整合化するためには、これらのＢ−スプライン端が、ＸＹ平面内の共通点において、平滑な接線及び曲率（すなわち、Ｃ２連続性）を有しながら出会うようにこれらの端を整合化するべきである。
【００６０】
Ｂ−スプライン端を整合化するために、２ＤのＢ−スプラインルーチン９００は、パッチＢ−スプラインを用いて２つのＢ−スプライン間の平滑な移行を作成する。２ＤのＢ−スプラインルーチン９００は、不整合Ｂ−スプライン端１００２、１００４の間のパッチＢ−スプライン上に中間点を投影する。２ＤのＢ−スプラインルーチン９００は、パッチＢ−スプラインを分割し、結び目ベクトルを融合してパッチＢ−スプラインの各半分が不整合Ｂ−スプラインに適合するようにする。２ＤのＢ−スプラインルーチン９００は、既存のＢ−スプライン形状を置換するパッチＢ−スプラインに対するパラメータ範囲を判断し、置換領域において再分割されたパッチＢ−スプラインからこれらのＢ−スプラインに制御点を複写する。２ＤのＢ−スプラインルーチン９００は、良好なＢ−スプライン品質（例えば、位置、車両方位、曲率誤差において誤差許容範囲の）を保証しながら、あらゆる不用な結び目（例えば、Ｂ−スプラインを適合化する結び目融合段階に起因する）を削除する。
【００６１】
ブロック９０６では、２ＤのＢ−スプラインルーチン９００は、タイル境界を跨ぐＢ−スプラインを整合化する。タイル間のＢ−スプラインは、ブロック９０４を参照して説明したものと同様の方式で整合化される。この整合化では、第１のＢ−スプラインに対する曲線当て嵌めは、１つのタイル内にあり、第２のＢ−スプラインに対する曲線当て嵌めは、隣接タイル内にあり、パッチＢ−スプラインは、タイル境界を横切って当て嵌めが行われる。タイルを横切ってのＢ−スプライン整合化は、タイル境界において継ぎ目のないＣ２のＢ−スプライン接合部を作り出す。
【００６２】
ブロック９０８では、２ＤのＢ−スプラインルーチン９００は、３つ又はそれよりも多くの道路が出会う交差点におけるＢ−スプライン端を整合化する。各交差点において、２ＤのＢ−スプラインルーチン９００は、自己交差点を含む交差リンクチェーンＢ−スプラインを探し出す。自己交差Ｂ−スプラインを含む２つのＢ−スプラインの交差点を識別する技術は、当業技術で公知である。交差するＢ−スプラインの各々に対して、２ＤのＢ−スプラインルーチン９００は、交差点を十字路Ｂ−スプライン（すなわち、４つのセグメントが単一のノードで出会う）、Ｔ字路、又は複合交差点（すなわち、４つよりも多くのセグメントが単一のノードで出会う）として分類する。２ＤのＢ−スプラインルーチン９００は、これらの道路を表すＢ−スプラインを共通ノードにおいて接合する。
【００６３】
ブロック９１０では、２ＤのＢ−スプラインルーチン９００は、スプラインにおける最適な分割場所を判断する。ノードが交差点ではない場合には、２ＤのＢ−スプラインルーチン９００は、ノードをリンクチェーンのＢ−スプライン上に投影し、分割場所を識別する。ノードが交差点ノードである場合には、２ＤのＢ−スプラインルーチン９００は、ブロック９０８を参照して説明した交差点分類に基づいて最適な分割場所を判断する。
【００６４】
ブロック９１２では、２ＤのＢ−スプラインルーチン９００は、ブロック９１０で判断された分割場所を用いてノードにおいてリンクチェーンのスプラインを分割し、各セグメントに対して１つの個々のＢ−スプラインを形成する。十字路Ｂ−スプラインでは、２ＤのＢ−スプラインルーチン９００は、スプラインをこれらのスプラインが交差する場所で分割し、道路が出会う共通の端点を作成する。
Ｔ字路では、近似Ｂ−スプライン曲線当て嵌め技術の性質に起因して、２つのリンクチェーンＢ−スプラインは、Ｔ字路で交差するか又は交差しない可能性がある。交差するＴ字路リンクチェーンのＢ−スプラインでは、２ＤのＢ−スプラインルーチン９００は、あらゆる重複区間を切り取って廃棄する。非交差のＴ字路では、２ＤのＢ−スプラインルーチン９００は、繋ぐ側の道路に対する終端Ｂ−スプラインを主道路リンクチェーンのＢ−スプラインに延長又は短絡させる（すなわち、曲げる又はシフトする）ことによって交差点の場所を作成する。主道路Ｂ−スプラインは、終端Ｂ−スプラインが延長及び短絡の後に主道路Ｂ−スプラインに接合する場所で分割される。Ｂ−スプラインの形状又は位置を延長及び調節するための技術は当業技術で公知である。
【００６５】
４つよりも多くのセグメントが単一のノードで出会う多重リンク交差点に対して、２ＤのＢ−スプラインルーチン９００は、セグメントが共通ノードで出会うように２Ｄスプライン幾何学形状を調節する。Ｂ−スプラインの局所サポート、及びこれらのＢ−スプラインがアフィン変換に対して不変量であるという事実に起因して、Ｂ−スプラインは、形状及び位置の調節に非常に適するものにされる。Ｂ−スプライン幾何学形状を調節するための技術は、当業技術で公知である。
【００６６】
各多重リンク交差点に対して、２ＤのＢ−スプラインルーチン９００は、交差点ノードの共通の２Ｄの場所を判断する。最適な場所は、交差点幾何学形状、複雑度、及び周囲のリンク接続性に依存する。次に、Ｂ−スプラインの局所的な曲率又は車両方位の品質に影響を与えずにこれらのスプラインを整合化するために、交差点の近くでＢ−スプラインはシフトされるか、又はこれらのスプラインの２Ｄの形状が調節される。調節段階の後に、２ＤのＢ−スプラインルーチン９００は、共通の交差点の場所においてＢ−スプラインを分割する。
【００６７】
ブロック９１４では、２ＤのＢ−スプラインルーチン９００は、２Ｄの曲率情報を２ＤのＢ−スプライン内に符号化する。符号化された曲率情報は、Ｂ−スプラインに沿って、曲率が弧長に対して線形に変化する場所を識別する。Ｂ−スプライン上で符号化された場所の各対の間では、各区間で曲率が弧長に対して線形に変化するので、曲率は、線形「クロソイド」と見なされる。これらのクロソイドの場所は、最初に、弧長の関数としての曲率のグラフであるＢ−スプラインに関する「曲率プロフィール」を作成することによって判断される。次に、曲率プロフィールは、線形曲率区間によって曲率プロフィールを近似するために、ポリラインによって近似される（Ｄｏｕｇｌａｓ−Ｐｅｕｋｅｒアルゴリズムに基づいて）。Ｂ−スプラインに沿ったポリラインの頂点の場所は、これらの場所にタグ付き結び目を挿入することによってＢ−スプライン内に符号化される。
【００６８】
ブロック９１６では、２ＤのＢ−スプラインルーチン９００は、結び目ベクトルを最適化する。ブロック９０２における曲線当て嵌め中に用いられる結び目ベクトルは、結び目数及び結び目の間隔に関して必ずしも最適ではない。結び目ベクトルは、２Ｄの位置、形状、車両方位、及び曲率の品質を維持しながら、物理的記憶媒体上の記憶スペースを最小にするように最適化される。
２ＤのＢ−スプラインルーチン９００は、ブロック９１４で判断された２ＤのＢ−スプラインに沿った対応するクロソイドセグメント（すなわち、線形曲率領域）を識別することによって最適な結び目配置を探し出す。長いクロソイドセグメントは、等しい弧長間隔で結び目を挿入することによって近似することができる。これらの追加結び目は、長いクロソイドセグメントを単一の結び目スパンを用いて正確に表すことができない場所でＢ−スプライン曲線の形状を維持する。
【００６９】
２ＤのＢ−スプラインルーチン９００は、ブロック９１４で曲率を符号化するのに用いられなかったあらゆる結び目、又は元のＢ−スプラインの２Ｄの位置、形状、車両方位、及び曲率の許容範囲にこのＢ−スプラインを保つのに必要とされないあらゆる結び目を削除する。一般的に、最適な結び目間隔は、曲率に反比例する（すなわち、曲率が大きい程、結び目はより近く離間される）。
【００７０】
リンクチェーンへの２Ｄ曲線当て嵌め
図１２は、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００の流れ図である。ブロック１２０２では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、曲線当て嵌め中に撓み及び振動のような曲線形状不規則性を防止する。例示的な防止段階は、直線形状を維持し、撓まない又は振動しないように曲線を拘束するためのリンクチェーンのうちで直線と分類される区間内への「仮想」形状点の挿入を含む。
【００７１】
ブロック１２０４では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ある一定の機能部類のリンクチェーン（例えば、高速道路、主要幹線）又は折り返しリンクチェーンを除く全ての道路に対するリンクチェーン内であらゆる捩れが存在するかを判断する。形状点は、この形状点で出会うリンクセグメントの間の角度が「捩れ」閾値を超えた場合に、「捩れ」として識別される。例えば、捩れ閾値は、３５度に設定することができる。
【００７２】
捩れを表すスプライン曲線では、曲線は、捩れの場所で不連続導関数（すなわち、Ｃ０連続性のみ）を有する。ブロック１２０４においてリンクチェーン内に１つ又はそれよりも多くの捩れが検出された場合には、ブロック１２０６において、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、各リンクの場所においてリンクチェーンを捩れの間の個々の部分リンクチェーンに分割する。リンクチェーン内に捩れが存在しない場合には、ブロック１２１８において、リンクチェーン全体に対して２Ｄスプライン当て嵌めが実施される。
【００７３】
ブロック１２０８では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ブロック９０２を参照して説明した２Ｄ曲線当て嵌め技術を用いて、部分リンクチェーンの各々に対して２ＤのＢ−スプラインで曲線当て嵌めを行う。得られるスプライン曲線は、捩れの場所においてＣ０連続性を有しながら出会う。
ブロック１２１０では、リンクチェーンは、ここでは複数のスプラインによって表されるので、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、部分リンクチェーンを単一のスプラインへと互いに縫合する。個々のＢ−スプライン曲線を単一の連続Ｂ−スプライン曲線へと接合するために、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、３次不均一Ｂ−スプラインが曲線上のこの曲線が捩れる場所（すなわち、この曲線がＣ０連続性のみを有するところ）で結び目多重度３を有するという不均一Ｂ−スプラインの性質を利用する。
【００７４】
Ｂ−スプライン曲線は、一度に１つ追加され、従って、複数のＢ−スプライン曲線を接合することが望ましい場合は、この接合は、最初の曲線に第２の曲線を追加して単一の曲線を形成し、この単一の曲線に対して次の曲線を追加することができ、以降同様に続けることによって達成される。Ｂ−スプライン曲線を接合するための技術は、当業技術で公知である。共通端点を有する２つの不均一３次Ｂ−スプライン曲線は、これらの曲線の制御点配列を連結し、それらの結び目ベクトルを追加することによってＣ０連続性を有しながら接合することができる。
【００７５】
ブロック１２１２では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、Ｂ−スプライン形状不規則性を補正する。Ｂ−スプライン形状不規則性は、撓み及び振動を含むことができるが、ノイズの多い曲率のような他の曲線不規則性が存在する領域を含むことができる。不規則性は、セグメントの曲線を定めるのに不十分な形状点しか用いられない場合、又は道路セグメントが劣悪に配置された形状点しか持たない場合に発生する可能性がある。Ｂ−スプラインが直線ではなく、基本的な道路幾何学形状が仮想形状点を追加した後には直線であることが既知である場合には、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ブロック１２１２において、Ｂ−スプラインを直線化するために制御点を操作することができる。ノイズの多い曲率領域を平滑にするのに同様の技術を用いることができる。
【００７６】
ブロック１２０４に戻ると、リンクチェーンが捩れを持たない場合には、ブロック１２１４において、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、リンクチェーンがあらゆる端にランプを含むかを判断する。リンクチェーンがランプを含む場合には、ブロック１２１６において、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、正しいランプ形状及び曲率を保証するために、端ノード及び形状点のランプオフセットを実施する。図１３に示しているように、ランプが自動車専用道路上に合流するランプ端において正しい方位及び曲率を得るために、スプライン当て嵌めにおいて、ランプリンクチェーンのノード及び形状点に加えて自動車専用道路のノード及び形状点が用いられる。
【００７７】
２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、スプライン当て嵌めに向けて以下の通りにランプを通じる点を編成する。
１．リンクチェーンがランプで始まるのか、又は終わるのかを判断する。
２．ランプリンクチェーンと自動車専用道路との間で共通するノードを識別する。
３．ランプリンクチェーンが一部の自動車専用道路で終わる場合には、自動車専用道路リンクセグメントとランプリンクセグメントの間の角度、及び機能部類に基づいて対応する自動車専用道路を選択する。
４．自動車専用道路リンクセグメントとランプリンクセグメントの間の角度が、閾値（例えば、５０度）を超える場合には、スプラインは、自動車専用道路形状点を通じて当て嵌められない。
５．自動車専用道路リンクセグメントとランプリンクセグメントの間の角度が、閾値（例えば、５０度）よりも小さい場合には、ランプ形状が自動車専用道路形状に追従することを保証するために、自動車専用道路点を編成することによってスプライン当て嵌めは自動車専用道路内に延長される。
６．ランプノード及び場合によっては自動車専用道路点は、図１４に示しているように車線幅に対処するようにオフセットされる。ランプの端ノード及び場合によっては隣接ノード／形状点は、ランプリンクチェーン、及び後のスプラインが、自動車専用道路の中心線への不自然な接続ではなく、ランプから自動車専用道路車線への実際の自動車経路を辿るようにシフトされる。
７．編成されてオフセットされたノード及び形状点にスプラインを当て嵌める。
８．ブロック９１２で自動車専用道路ノードにおいてスプラインを切り取る。
【００７８】
図１４に示しているランプオフセットベクトル１４０２の長さは、既知又は推定の自動車専用道路幅に依存する。推定幅は、自動車専用道路の車線数、自動車専用道路の走行方向制限（すなわち、一方向又は双方向）、及びランプにおける車線数（ランプは常に一方向であると仮定される）に基づいて判断される。ランプスプラインが自動車専用道路の中心線に向って歪むのを回避するために、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ランプの内部形状点及び／又はノードが、オフセットされた自動車専用道路／ランプ共通ノードよりも自動車専用道路の中心線に近くないことを保証する。ランプの内部形状点及び／又はノードの一部が近い場合には、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ランプ／自動車専用道路交差点ノードから分離する自動車専用道路リンクセグメントに対して平行な線であり、交差点ノードをオフセットすることによって生じる想像ノードを通過する線上にランプの内部形状点及び／又はノードを投影する。図１３は、一般的な四葉のクローバー状ランプにおいて得られるランプスプライン形状を示している。
ブロック１２１８では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ブロック９０２を参照して説明したように、リンクチェーンに２ＤのＢ−スプラインを当て嵌める。ブロック１２１２では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、上述のようにＢ−スプライン形状不規則性を補正する。
【００７９】
ブロック１２１４に戻ると、リンクチェーンがランプではない場合には、ブロック１２２０において、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、リンクチェーンが環状交差点であるかを判断する。リンクチェーンが環状交差点である場合には、ブロック１２２２において、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、環状交差点を３周回するようにリンクチェーンを延ばす。環状交差点に対する複数周回のスプライン当て嵌めは、水滴形の環状交差点幾何学形状を防止する。その後、ブロック９１２において、重複環状交差点スプラインの適切な区間が切り取られて、環状交差点に対する個々のスプラインが得られる。
【００８０】
３ＤのＢ−スプラインの作成
図１５は、３ＤのＢ−スプラインを作成する方法１５００の流れ図である。３ＤのＢ−スプラインを作成する方法１５００は、ＭＰＥ１１６における使用に向けて地理データベース１０６内にデータを記憶する前に、あらゆるコンピュータ上で実行することができるソフトウエアルーチン（又は複数のソフトウエアルーチン）である。
３ＤのＢ−スプラインは、２ＤのＢ−スプライン（２ＤのＢ−スプラインルーチン９００を用いて得られる）を１Ｄの標高スプラインと組み合わせることによって作成される。１Ｄの標高スプラインは、車両において収集されたＧＰＳデータにスプラインを当て嵌めることによって作成される。３Ｄスプラインを必要とする道路を収集車両を用いて運転することにより、大量の順次データ点（緯度、経度、高度、車両方位、勾配、及び／又は速度データが関連付けられたもの）がもたらされる。絶対的及び相対的な地理的場所の精度を維持するために、データ点は、ＧＰＳ及び慣性測定ユニット（ＧＰＳ／ＩＭＵ）を用いて収集される。高度点データセットは、あらゆるデータ異常を削除するためにフィルタリング及び調節される。フィルタリングは、給油停車、オフロード運転、及び方向転換操縦等に起因するあらゆる外生データを除去する。次に、データセットは、空間及び時間連続性に基づいて小さいデータセットへとまとめられる。
【００８１】
ブロック１５０２では、記憶及びデータセット間の地理参照を容易にするために、高度点は、既知の幾何学形状の２Ｄ道路中心線のデータベース上にこれらの高度点を投影する（２ＤのＸＹ投影を用いて）ことによって編成される。各点は、特定の道路リンクに割り当てられ、このリンクに沿う特定の距離へとパラメータ化される。この関連付けにより、標高データが道路データベース内の既存の情報を参照することが可能になる。
【００８２】
３ＤのＢ−スプラインルーチン１５００は、既知の道路リンク経路（道路網）に沿って進み、点を各可能なリンク経路上に投影することにより、点から２Ｄリンクへの投影を実施する。可能なリンク経路数は、一方向の走行方向制限及び機能部類レベルのようなデータベース内で符号化された道路制限によって絞り込まれる。ＧＰＳ点記録に対する正しいリンク経路を得るために、単一の正しい経路が見つかるまで複数の経路が試験される。複数の有効な経路が見つかった場合には、元のＧＰＳ経路形状とリンク投影経路形状の間の差に基づいて罰則基準が計算され、最小の合計２Ｄオフセット、角度差、形状差、及び／又は走行距離差を有する経路が正しい道路リンクシーケンスとして選択される。このリンクシーケンスを標高リンクチェーンと呼ぶ。
【００８３】
ブロック１５０４では、３ＤのＢ−スプラインルーチン１５００は、１Ｄの高度Ｂ−スプラインを標高リンクチェーンに沿って高度点に当て嵌める。それによって記憶スペース及びデータベースＩ／Ｏ帯域幅を節約するコンパクトな標高表現が可能になる。ブロック１５０２において得られた高度点は、リンクチェーン順序及び２Ｄの点／リンク投影から見つかるリンクパラメータ距離に基づいて標高リンクチェーンに沿って単調に整列する。投影された標高点の各々までの２Ｄ弧長距離を計算するために、標高リンクチェーンに対してトラバース測定が行われる。このデータ対（リンクチェーン弧長と標高との）は、１Ｄの標高スプラインを計算するためのデータセットを形成する。
【００８４】
３ＤのＢ−スプラインルーチン１５００は、１Ｄの標高スプラインを作成する前に標高リンクチェーンを小さいリンクチェーンに分割する。目標は、各道路リンクに対して個々のスプラインを作成することであるが、リンク境界を跨ぐ平滑な高度Ｂ−スプラインを維持するために、複数のリンクチェーン区間（例えば、１０００メートルまでの）にわたる中間スプラインが生成される。３ＤのＢ−スプラインルーチン１５００は、同様に標高リンクチェーン境界を横切って平滑なスプラインが生成されるように、大きいリンクチェーンに重なっている。
【００８５】
一部の場合には、隣接リンクを跨ぐ単一の標高スプライン当て嵌めは望ましくない。従って、３ＤのＢ−スプラインルーチン１５００は、基本的道路データベース特性及び運転経路に基づいて大きいリンクチェーンを更に分割し、これらのリンクチェーンは、標高が突然の勾配又は標高変化を含む可能性がある場所で分割される。例えば、チェーンは、経路が８０度よりも大きく屈曲する時（例えば、異なる道路に乗る）、及びリンクチェーンがデータ格差を含む場合に分割される。次に、３ＤのＢ−スプラインルーチン１５００は、道路リンクノードの場所で１Ｄ高度Ｂ−スプラインを分割する。
【００８６】
３ＤのＢ−スプラインルーチン１５００は、得られるＢ−スプラインを各スプラインが２Ｄの道路リンク参照情報に連結されるようにデータベースに記憶する。更に、各道路リンクの標高スプラインに対して２つの横断時標高（スプライン開始及び終了点における）が保存される。横断時標高は、スプラインが道路リンクノードを横切る時のスプラインの高度を記憶する。このリンクノードへの参照情報が記憶される。標高スプラインが重複する場合には、単一の道路リンクノードは、複数の横断時標高を含むことになる。この横断時標高データベースは、標高スプラインの可能な交差場所を説明し、３ＤのＢ−スプラインルーチン１５００が、ブロック１５０６において、交差場所及び交差するスプラインの間の高度差を効率的に照会することを可能にする。
【００８７】
ブロック１５０２及び１５０４では、３ＤのＢ−スプラインルーチン１５００は、以前の道路属性把握内容をスプラインに追加することができるように、高度Ｂ−スプラインデータを道路リンク地図データベースに関連付ける。それによって標高データが交差点にあるのか、又はランプ（交差する標高が異なることが許される）上にあるのかを把握するなどの高度Ｂ−スプラインの知的処理が可能になる。従って、より正確な標高に関する解法が可能である。
【００８８】
ブロック１５０６では、３ＤのＢ−スプラインルーチン１５００は、道路網に沿って走行する車両内に設けられたＧＰＳ／ＩＭＵによって収集された高度データを調節する。高度補正ルーチンの例に対して、図１６を参照してより詳しく解説する。ＧＰＳ／ＩＭＵ地理参照機器の精度限界により、収集されたデータ点の絶対高度にある程度のドリフトが導入される可能性がある。その結果、２つの道路が交差する時に、各スプラインは、同じ交差点に対して若干異なる高度を間違って説明する可能性がある。一部のスプライン交差ノードは、異なる高度を有する（別の道路の上方を横断する橋等）。従って、標高補正ルーチンは、３Ｄスプラインが縦断勾配で交差するところを判断する。高度Ｂ−スプラインに関連付けられた道路地図データベース（Ｂ−スプライン道路リンクを参照情報として用いる）を利用することにより、道路リンクがどこで交差するか、これらのリンクが同じ高度でつながっているか、又はリンクが高架通路であるか、又は地下交通路であるかを把握することができる。横断時標高データベースは、この目的のためにブロック１５０４で作成されたものである。
【００８９】
図１６は、標高補正ルーチン１６００の流れ図である。標高補正ルーチン１６００は、標高スプラインのデータベース全体が単一の処理で補正されるように、好ましくは広域操作として実施される。１つの標高データセットを移動することにより、このデータセットが交差する他の標高データセットの当て嵌めが影響を受けるので、広域的解法が望ましい。広域的解法の作業負荷を最小にするために、標高補正ルーチン１６００は、横断時標高（ブロック１５０４で得られた）だけにアクセスする。データは、横断時標高データベースに対して実施される１回のデータベース照会によってアクセス可能である。このアクセスは、標高スプラインが交差するノードを探し出し、スプラインが重複するノードのみが戻される。それによって標高補正ルーチン１６００は、実際の標高スプラインをアクセス又は評価する必要なく、標高差を調べることが可能になる。
【００９０】
標高補正ルーチン１６００は、２つの操作を高度スプラインに適用する。第１に、スプラインが、同じ標高にある共通の道路リンクノードを横断するように、標高が垂直に補正される。第２に、多くの場合に、単一の道路リンクに対して複数の標高スプラインが利用可能である。標高補正ルーチン１６００は、各道路リンクに対して単一の最適な高度スプラインを選択する。この後、選択された最適の高度スプラインは、高度スプライン作成処理の残りの部分に用いられる。
【００９１】
道路リンクノードにおいて標高を整合化するのに、標高は、可能な限り最小限にしか変更されず、データにおける整合性を維持することに重点が置かれる。標高データは、その周囲の時間的に局所的なデータと比較すると非常に正確である。しかし、ドリフトに起因して、絶対標高は、大きい偏差を含む可能性がある。従って、整合化処理は、近接データ（高い相対精度）の使用を最大化し、異なるデータベース（絶対標高依存の）間の切り換えを最小にする。冗長な標高データの平均化は勧められない。代替的に、標高補正ルーチン１６００は、最良のデータセットから単一の最良の標高を選択することによってノードの標高を判断する。理想的には、整合性を維持するために、可能な限り最大の近くの標高ノードに対して同じデータセットが用いられる。
【００９２】
ブロック１６０２では、標高データセットは、これらのデータセットが標高において如何に良好に他の近接データセットの標高と合致するかということ、運転距離、及び運転精度信頼度に基づいて順位付けされる。この順位は、運転行程が、標高補正ルーチン１６００において適用される順序を制御する。この順序は、どの標高が元の標高スプラインから直接に割り当てられるか（「基本ノード」標高と呼ぶ）、及び既存の標高スプラインに当て嵌める上でどの標高が調節されるか（補正標高）を判断する。更に、この順序は、どの標高スプラインが（単一の道路リンクに対して複数のスプラインが利用可能である時に）、ブロック１５０８において最終高度スプラインを生成する時に用いるべきスプラインとして選択されるかを判断する。
【００９３】
ブロック１６０４では、最低信頼度レベルから外れる運転行程が整合化処理から除外される。それによって信頼性の低いデータが、不用な標高オフセットを引き起こすことが防止される。
ブロック１６０６では、標高補正処理を開始するのに最上位の運転行程が選択される。最初の運転行程は、いかなる既存の基本ノードの標高とも重複しないので、最初の運転行程は、標高において調節する必要はない。従って、ブロック１６０８では、標高補正ルーチン１６００は、補正曲線なしに最初の運転行程におけるノードを「基本ノード」として割り当てる。最初の運転行程と交差する以降（ブロック１６１２より）のあらゆるスプラインは、基本ノードと整合化するように変更される。更に、ブロック１６１０では、標高補正ルーチン１６００は、この運転行程からの標高スプラインを関連の２Ｄ道路リンクに対する最適スプラインとして割り当てる。
【００９４】
ブロック１６１２では、標高補正ルーチン１６００は、順位付けされたリストから、前に固定された運転行程の基本ノードと交差する次に最良の運転行程を選択する。ブロック１６１４では、標高補正ルーチン１６００は、標高ノードを検査して、どのノードが、前の運転行程の前に固定されたもの（基本ノード）に対応するかを調べる。運転行程のノードを既存の基本ノードの標高と整合化するために、オフセットが計算される。
【００９５】
運転行程ノードを既存の基本ノードに対して調節するのに加えて、基本ノード間で標高補正が線形に適用される。元の標高データを保持するために、元の標高スプラインを変更する代わりに仮想補正ポリラインが作成される。元の標高スプラインと仮想補正ポリラインの重ね合わせは、正しく整合化された高度スプラインを生じる。仮想ポリラインは、元のスプラインが他方の高度スプラインの基本ノードに当て嵌まるように補正するのに必要な標高オフセットを定める線形形状である。線形補正を用いることにより、標高補正ルーチン１６００が、正確な場所で精密に補正を定める（すなわち、オーバーシュートがない）ことが可能になり、同様に標高補正ルーチン１６００が、大きい２Ｄ距離にわたって補正を線形に分散させることが可能になる。
【００９６】
この処理の恩典は、標高スプラインデータベースが一度もアクセスされず、スプライン形状を読み取り、変更し、及び保存する必要がないことである。この処理は、大きい広域操作であるから、データベースＩ／Ｏ及びＣＰＵ要件の有意な節約が行われる。データベース作動は、最小限のデータセットを読み取ることへと変形され、複数の横断時標高を有するノードのみが考察される。書込み作動は、各運転行程に対して単一の線形補正ポリラインを保存する段階、及び標高スプライン上のステータスフラグ（スプラインが、道路リンクに対する独特な代表として選択されたか否かを示す）を更新する段階という２つの段階へと変形される。
【００９７】
ブロック１６１６では、標高補正ルーチン１６００は、計算された整合化オフセットを表す仮想の線形ポリラインを作成する。仮想ポリライン補正は、運転行程における非基本ノードの補正ノード高度を判断するのに用いられる。ブロック１６１８では、標高補正ルーチン１６００は、補正高度のノードを固定の基本ノードリストに追加する。
各運転行程が適用される時に、運転行程に関連付けられた道路リンクが検査され、これらのリンクに、以前の運転行程からの独特な「最適」高度スプラインが以前に割り当てられているか否かが調べられる。ブロック１６２０では、標高補正ルーチン１６００は、最適のスプラインを持たないリンクに現在の運転行程データセットからの標高スプラインを割り当てる。その結果、標高が固定された運転行程と対応する高度スプラインセットが生じ、この高度スプラインセットは、以降の標高データセットに対する基礎を与える。
【００９８】
ブロック１６２２では、標高補正ルーチン１６００は、検査を行って既存の基本ノードの標高と重複する更に別の運転行程データセットが存在するか否かを調べる。重複データセットが存在する場合には、ブロック１６１２において、標高補正ルーチン１６００は、既存の基本ノードと重複する次に最良の運転行程を選択し、上記処理が繰り返される。重複運転行程を処理し終わると、ブロック１６２４において、標高補正ルーチン１６００は、いずれか残りの未処理運転行程が存在するか否かを検査する。未処理運転行程が残っている場合には、ブロック１６０６において、標高補正ルーチン１６００は、残りの最良の運転行程に対して新しい整合化処理を再開する。
好ましくは、標高補正ルーチン１６００は、運転行程の全てを処理し終わるまで繰り返される。処理の後に、標高補正曲線がデータベースに記憶され、単一で独特な標高スプラインが道路リンクに関連付けられる。
【００９９】
図１５に戻ると、ブロック１５０８において、３ＤのＢ−スプラインルーチン１５００は、方法８００において作成されたリンクチェーンに対して単一の多重リンク高度スプラインを作成する。リンクチェーン内の各リンク（道路セグメント）に対して、前に選択された最適な高度Ｂ−スプライン（ブロック１５０６における）が、例えば、１メートルのＸＹ弧長毎に標高点に変換して戻される。補正ポリラインオフセット（ブロック１５０６）が計算され、各点に追加される。結果は、リンクチェーンのＸＹ弧長によってパラメータ化された高度が整合化された点の集合である。
【０１００】
３ＤのＢ−スプラインルーチン１５００は、新しい高度Ｂ−スプラインを複数のリンクに対して標高がパラメータ化された点のリストに当て嵌める。各連続する曲線当て嵌めは、前の曲線当て嵌めからのスプラインと重複する。重複曲線当て嵌めは、曲線当て嵌めの間の境界における形状整合性を保証する。高度曲線当て嵌め技術は、指定の曲線当て嵌めＺ許容範囲に基づいて最適な結び目ベクトルを再帰的に判断する。指定の高度曲線当て嵌め許容範囲は、高度が急激に変化する時により多くの結び目が存在し、高度が緩慢に変化する時により少ない結び目が存在するように結び目ベクトル間隔を判断するのに用いられる。高度Ｂ−スプラインにおける高度点は、リンクチェーンの弧長によってパラメータ化されているので、高度Ｂ−スプラインは、２ＤのＢ−スプラインに適合する結び目ベクトルパラメータ空間を有し、それによってブロック１５１０において、これらのＢ−スプラインを３ＤのＢ−スプラインへと融合することが可能になる。
【０１０１】
ブロック１５１０では、３ＤのＢ−スプラインルーチン１５００は、方法９００からの２ＤのＢ−スプラインと、ブロック１５０８からの高度Ｂ−スプラインとを融合し、３ＤのＢ−スプラインを得る。３ＤのＢ−スプライン表現は、高度Ｂ−スプラインのＺ成分を２ＤのＢ−スプラインルーチン９００によって作成された２ＤのＢ−スプラインに追加することによって作成される。２ＤのＢ−スプライン及び高度Ｂ−スプラインの両方に対するパラメータ空間は、同じＸＹリンク幾何学形状の弧長によってパラメータ化されているので、これらのＢ−スプラインは、これらの結び目ベクトルを融合することによって融合することができる。
【０１０２】
３ＤのＢ−スプラインルーチン１５００は、両方のＢ−スプラインの最大結び目値によって２ＤのＢ−スプライン及び高度Ｂ−スプラインの各々の結び目ベクトルをスケーリングする。次に、３ＤのＢ−スプラインルーチン１５００は、結び目挿入を用いて２ＤのＢ−スプラインの結び目を高度Ｂ−スプラインの中に挿入し、高度Ｂ−スプラインの元の結び目を２ＤのＢ−スプラインの中に挿入する。その結果、両方のＢ−スプラインが同じ結び目ベクトルを有し、同じパラメータ空間を共有する。
【０１０３】
３ＤのＢ−スプラインルーチン１５００は、以下に示すように、３ＤのＢ−スプラインの制御点のＺ値を高度Ｂ−スプラインのＺ値のものと等しく設定することにより、２ＤのＢ−スプラインから３ＤのＢ−スプラインを作成する。
【０１０４】
【数１１】
【０１０５】
ブロック１５１２では、３ＤのＢ−スプラインルーチン１５００は、３ＤのＢ−スプラインに勾配情報を符号化する。この符号化は、３ＤのＢ−スプライン内に結び目をタグ付けすることによって達成され、これらの結び目は、電子視野アプリケーション２０８のための線形勾配プロフィールを生成するのに用いることができる。高度が急激に変化する時により多数の勾配結び目が存在し、高度が緩慢に変化する時により少数の結び目が存在するように、符号化される結び目ベクトル間隔を判断する上で指定の標高及び勾配許容範囲が用いられる。更に、勾配変曲点が発生する場所により多くの勾配点が追加される。３ＤのＢ−スプラインルーチン１５００は、標高、勾配、及び勾配変化に基づいて、Ｄｏｕｇｌａｓ−Ｐｅｕｋｅｒ線近似解析を用いて符号化された勾配結び目の場所を識別する。この解析は、データ点が線近似の許容範囲に入ると終了する。３ＤのＢ−スプラインルーチン１５００は、高度分布に沿って各Ｄｏｕｇｌａｓ−Ｐｅｕｋｅｒポリライン点に「タグ付き」勾配結び目を挿入する。
【０１０６】
ブロック１５１４では、３ＤのＢ−スプラインルーチン１５００は、ブロック１５１２における結び目挿入を評価することによってサイズを最適化する。得られる結び目挿入は、Ｂ−スプラインの３Ｄ形状を表すのに必要なものよりも多くの結び目を生じる可能性があるから、３ＤのＢ−スプラインルーチン１５００は、勾配プロフィール及び曲率プロフィールを符号化するのに又はＢ−スプライン品質を維持するのに必要ではない結び目を削除する。
【０１０７】
上述の詳細説明が限定的ではなく例示的なものとして捉られること、及び全ての均等物を含む以下の特許請求の範囲が本発明の範囲を定めるように意図されることが理解されることを意図している。これらの特許請求の範囲は、その旨を明記しない限り、説明した順序又は要素に限定されると解釈すべきではない。従って、以下の特許請求の範囲及びその均等物の範囲及び精神に該当する全ての実施形態を本発明として特許請求する。
【符号の説明】
【０１０８】
１００ 地図援用ＡＤＡＳアーキテクチャ
１０６ 地理データベース
１１０ 車両内データバスインタフェース
１１４ 運転者支援アプリケーション
１１６ 地図及び測位エンジン（ＭＰＥ）
【技術分野】
【０００１】
関連出願への参照
本出願は、２００８年１０月１日出願の「最新運転者支援システムのための幾何学形状の作成」という名称の米国特許仮出願第６１／１０１、７５２号の恩典を請求する。米国特許仮出願出願番号第６１／１０１、７５２号の全開示内容は、本明細書に引用によって組み込まれている。
本特許出願は、本明細書に引用によって組み込まれている「最新運転者支援システムアプリケーションのためのベジエ曲線」という名称の同じ日付に出願された現在特許出願中の特許出願出願番号第＿＿＿＿号、代理人整理番号Ｎ０２９５ＵＳに関連している。
本発明は、一般的に、最新運転者支援システム（ＡＤＡＳ）に関し、より具体的には、ＡＤＡＳにおける使用に向けて幾何学形状を作成することに関する。
【背景技術】
【０００２】
ＡＤＡＳは、運転の快適さ、効率、安全性、及び全体的な満足感を改善するために開発されたものである。これらの最新運転者支援システムの例は、適応ヘッドライト照準、適応走行制御、車線逸脱警告及び制御、カーブ警告、速度制限通知、ハザード警告、予測走行制御、適応変速制御、並びにその他を含む。これらの最新運転者支援システムの一部は、車両の現在の状態及び車両の前方にある車道の現在の状態を判断するために車両内の様々なセンサ機構を用いる。これらのセンサ機構は、デジタルビデオカメラ及びＬＩＤＡＲのようなレーダー、赤外線、超音波、及び視覚指向性センサを含むことができる。
【０００３】
一部の最新運転者支援システムはまた、デジタル地図データを用いる。これらのシステムは、時によっては地図援用ＡＤＡＳと呼ばれる。デジタル地図データは、最新運転者支援システムにおいて道路網、道路幾何学形状、道路状態、並びに車両の周囲の道路及び地形に関連する他の項目に関する情報を提供するのに用いることができる。一部のセンサとは異なり、デジタル地図データは、霧、雨、又は雪のような環境の状態による影響を受けない。更に、デジタル地図データは、曲率、断勾配、横傾斜、標識によって示されていない速度制限、及び車線制限などのようなセンサによっては確実には供給することができない有利な情報を提供することができる。更に、デジタル地図データは、車両の前方、曲がり角付近、坂の向こう側、又は障害物の向こう側の道路を判断するために、センサの範囲を十分に超えるか又は運転者の視界さえ超える予測機能を提供することができる。従って、デジタル地図データは、一部の最新運転者支援システムに対して有用な追加物とすることができる。
【０００４】
地図援用最新運転者支援システムは、一般的に、車両内のナビゲーションシステムに付随する地理データベースからのデータを用いる。ナビゲーションシステムのデータベースは、道路及び交差点の場所（高度を含む地理座標）、道路名、道路に沿った速度制限、交差点での右左折制限、道路に沿った住所又は住所範囲、各道路における車線数、車線幅、車線境界線、道路の機能部類、及び中央分離帯の場所などのような地域内の道路網を表すデータを収容する。ナビゲーションシステムのデータベースはまた、水域、公園、行政区域（地方自治体、州、及び国の境界を含む）、及び会社、病院、及び警察署などのような肝心な点の場所のような他の地理的特徴に関する情報を収容することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許仮出願第６１／１０１、７５２号
【特許文献２】米国特許公開第２００６／０１００７８０号
【特許文献３】米国特許第６、４０５、１２８号
【特許文献４】米国特許第７、０８４、８８２号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ナビゲーションシステムのデータベースは、最新運転者支援システムが必要とするものよりも非常に多くのデータを有する。更に、ナビゲーションに向けて設計された地理データベースは、全てのデータを有していない場合があり、及び／又は最新運転者支援システムによって必要とされる精度レベルでデータを有していない場合がある。その結果、特に最新運転者支援システムに向けた地理データベースの設計には何らかの労力が費やされてきた。例えば、米国特許公開第２００６／０１００７８０号は、自動車システム内のセンサデバイスに向けて設計されたデータ記憶フォーマットを有する地理データベースを説明している。しかし、特に最新運転者支援システムに向けて設計された地理データベースには、改善の余地がある。
【課題を解決するための手段】
【０００７】
ＡＤＡＳのための幾何学形状を作成する方法及びシステムを説明する。ソフトウエアルーチンを用いて、道路セグメントのシーケンスであるリンクチェーンが作成される。ソフトウエアルーチンは、関連の機能部類を有する最初の道路セグメントを選択する。各ノードにおいて、ソフトウエアルーチンは、リンクチェーンに追加する次の道路セグメントを選択する。リンクチェーンは、末端ノードを見つけるまで成長し続ける。
リンクチェーンに対して当て嵌めが行われ、２ＤのＢ−スプラインが作成される。２ＤのＢ−スプラインは、不規則性及びアラインメント問題を補正するために操作される。位置、曲率、勾配、及び／又は車両方位を保持するのに必要のない結び目は、記憶要件を最小にするために削除される。
【０００８】
リンクチェーン、最適化された２ＤのＢ−スプライン、及び高度データが用いられて、３Ｄスプラインが作成される。好ましくは、高度データは、車両が道路セグメントによって表される道路上を走行する時に収集されたＧＰＳ／ＩＭＵ記録から得られる。ＧＰＳ高度の不正確性に対処するために、高度データは、交差ノードの位置で補正される。補正された高度データを用いて、リンクチェーンに対して当て嵌めが行われて高度Ｂ−スプラインが作成される。２ＤのＢ−スプラインと高度Ｂ−スプラインは融合され、３ＤのＢ−スプラインが得られる。２ＤのＢ−スプラインと同様に、記憶要件を最小にするために位置、曲率、勾配、及び／又は車両方位を保持するのに必要のない結び目は、３ＤのＢ−スプラインから削除される。
３ＤのＢ−スプライン及び場合によっては２ＤのＢ−スプラインは、ベジエ曲線に変換される。ベジエ曲線は、２Ｄポリラインを効率的に作成して曲率、勾配、及び車両方位を計算するのに用いることができる。ＡＤＡＳアプリケーションは、マップ照合に向けてＡＤＡＳ機能及びポリラインを提供するためにベジエ曲線を用いることができる。
【０００９】
これら並びに他の態様及び利点は、適切な場合は添付図面を参照して以下の詳細説明を読解することにより当業者には明らかになるであろう。更に、この要約は例に過ぎず、特許請求する本発明の範囲を限定する意図はないことを理解されたい。
同様の参照番号が様々な図における同様の要素を指す添付図面の図を併用して現時点で好ましい実施形態を下記に説明する。
【図面の簡単な説明】
【００１０】
【図１】実施例による地図援用ＡＤＡＳアーキテクチャのブロック図である。
【図２】実施例による図１に描かれたプロセッサに利用可能なソフトウエアアプリケーションのブロック図である。
【図３】実施例による図１に描かれた地理データベースからの道路セグメントデータ記録のブロック図である。
【図４】実施例による図３に描かれた道路セグメントデータ記録におけるデータ属性のブロック図である。
【図５】実施例によりＡＤＡＳのための幾何学形状を作成するための流れ図である。
【図６】例示的なベジエ曲線の図である。
【図７】ベジエ曲線から生成された例示的なポリラインの図である。
【図８】実施例によりリンクチェーンを作成するための流れ図である。
【図９】実施例により２ＤのＢ−スプラインを作成するための流れ図である。
【図１０】実施例による不整合Ｂ−スプライン端の図である。
【図１１】実施例による整合Ｂ−スプライン端の図である。
【図１２】実施例により２ＤのＢ−スプラインをリンクチェーンに当て嵌めるための流れ図である。
【図１３】実施例による一般的な四葉のクローバー状ランプにおけるランプスプライン形状の図である。
【図１４】実施例によるランプノードオフセット法の図である。
【図１５】実施例による３ＤのＢ−スプラインを作成するための流れ図である。
【図１６】実施例による標高補正ルーチンの流れ図である。
【発明を実施するための形態】
【００１１】
ＡＤＡＳアーキテクチャ
図１は、地図援用ＡＤＡＳアーキテクチャ１００のブロック図を示している。この例では、地図援用ＡＤＡＳアーキテクチャ１００は、運転者支援アプリケーション１１４、並びに地図及び測位エンジン（ＭＰＥ）１１６を含む。図１では、ＭＰＥ１１６を独立型モジュールとして示しているが、ＭＰＥ１１６は、複数のパッケージに分散させることができ、及び／又はセンサパッケージのような他のデバイスパッケージ内に統合することができることを理解されたい。ＭＰＥ１１６は、プロセッサ１０２、測位システム１０４、地理データベース１０６、通信システム１０８、及び車両内データバスインタフェース１１０を含む。ＭＰＥ１１６はまた、メモリ及び電源のような他のハードウエア、ソフトウエア、及び／又はファームウエアを含むことができる。
【００１２】
プロセッサ１０２は、あらゆる種類のプロセッサ、コントローラ、又は他のコンピュータデバイスとすることができる。例えば、プロセッサ１０２は、デジタル信号プロセッサとすることができる。プロセッサ１０２は、測位システム１０４、地理データベース１０６、通信システム１０８、車両内データバスインタフェース１１０、及びその他の供給源からの入力を受信する。次に、プロセッサ１０２は、一部を図２を参照して説明するアプリケーションソフトウエアプログラム２００を用いてこれらの入力を処理する。
【００１３】
次に、プロセッサ１０２は、車両内データバスインタフェース１１０及びデータバス１１２を通じて運転者支援アプリケーション１１４に出力を供給する。好ましくは、車両内データバスインタフェース１１０及びデータバス１１２は、自動車用途に向けて設計されたコントローラエリアネットワーク（ＣＡＮ）インタフェース及びＣＡＮバスである。運転者支援アプリケーション１１４は、適応ヘッドライト照準、適応走行制御、障害物検出、障害物回避、衝突回避、適応変速制御、及びその他を含むことができる。
【００１４】
測位システム１０４は、ＧＰＳ型技術、推測航法型システム、又はこれらの組合せ、又は当業技術で公知の他のシステムを利用することができる。また、測位システム１０４は、走行距離、速度、方向、及び姿勢などを測定する適切な感知デバイスを含むことができる。例えば、測位システム１０４は、ＧＰＳシステム及びジャイロスコープを含むことができる。測位システム１０４は、プロセッサ１０２に出力信号を供給する。プロセッサ１０２上で作動するアプリケーションソフトウエアプログラム２００の一部は、ＭＰＥ１１６の場所、方向、及び姿勢などを判断するのに測位システム１０４からの出力信号を用いる。
【００１５】
地理データベース１０６は、ＡＤＡＳアプリケーションに向けて設計される。ナビゲーションシステムの地理データベースと同様に、地理データベース１０６は、地理的領域内の道路及び交差点に関するデータを含む。例えば、地理データベース１０６は、各道路セグメント（リンクとも呼ぶ）に対して少なくとも１つのデータベース記録（「エンティティ」又は「エントリ」とも呼ぶ）を含む。道路セグメントがＢ−スプライン曲線又はベジエ曲線で表される時には、道路セグメントデータ記録は、制御点の地理座標（例えば、緯度、経度、及び高度）を与えるデータを含む。道路セグメントの端点（ノードとも呼ぶ）は、最初及び最後の制御点に対応する。更に、道路セグメントデータ記録はまた、Ｂ−スプライン幾何学に関する結び目ベクトルを収容することもできる。
道路セグメントが形状点幾何学形状として表される時には、道路セグメントデータ記録は、表される道路セグメントの端点の地理座標（例えば、緯度、経度、及び高度）を与えるデータを含む。曲線セグメントでは、道路セグメントデータ記録は、ポリラインを特徴付けるのに用いられる形状点の地理座標（例えば、緯度、経度、及び高度）を与えるデータも含む。
【００１６】
道路セグメントデータ記録に対して、図３を参照してより詳しく説明する。
地理データベース１０６は、一般的にナビゲーションシステムの地理データベースに含まれるデータよりも高い品質（すなわち、正確な）データを含むことができる。例えば、道路幾何学形状に関して、地理データベース１０６内のデータは、経度、緯度、及び／又は高度に関してより正確なものとすることができる。また、地理データベース１０６では、トンネルの開始場所及び終了場所をより正確に指定することができる。更に、地理データベース１０６内のデータは、曲率のような導出情報に関してより正確なものとすることができる。
【００１７】
また、地理データベース１０６は、一般的に、ナビゲーションシステムの地理データベースに含まれるデータよりも多くの種類のデータ（例えば、多くの種類の属性）を含むことができる。例えば、地理データベース１０６は、標識及び横断歩道のような道路物体に関するデータを道路セグメントに沿ったこれらの位置、標識物体種類、及び標識テキストを含めて含むことができる。地理データベース１０６内に見られるデータ属性の一部に対して、図４を参照して説明する。
【００１８】
図２は、プロセッサ１０２に対して利用可能なソフトウエアアプリケーション２００の一部を示しているブロック図である。図２に示しているソフトウエアアプリケーション２００は、地図アクセスアプリケーション２０２、地図更新アプリケーション２０４、車両測位アプリケーション２０６、電子視野アプリケーション２０８、及びインタフェースアプリケーション２１０を含む。これは、プロセッサ１０２に対して利用可能な全てのソフトウエアアプリケーション２００の網羅的なリストではないので、図２は、始動ルーチン、及び自己試験診断などを含むことができる他のアプリケーション２１２も示している。
【００１９】
地図アクセスアプリケーション２０２は、物理的記憶媒体上に記憶された地理データベース１０６へのデータアクセスを提供する。地図アクセスアプリケーション２０２は、プロセッサ１０２からデータ要求を受信し、この要求に応じるデータを物理的記憶媒体上で探し出す。好ましくは、地図アクセスアプリケーション２０２は、プロセッサ１０２及び／又はアプリケーション２００による使用に向けて、アプリケーションプログラミングインタフェース（ＡＰＩ）を提供する。
【００２０】
地図更新アプリケーション２０４は、地理データベース１０６に対する更新を容易にする。通信システム１０８は、既存のデータベースに付加的な受信範囲を追加するか、又は既存のパーセルを置換するかのいずれかを行う１つ又はそれよりも多くのパーセルを受信する。パーセルは、物理的記憶媒体上の地理データベース１０６内に地理データを記憶するための記憶単位である。新しいパーセルに対しては、地図更新アプリケーション２０４は、物理的記憶媒体上にこのパーセルを記憶する。既存のパーセルに対しては、地図更新アプリケーション２０４は、物理的記憶媒体上の古いパーセルを新しいパーセルで置換する。
車両測位アプリケーション２０６は、地理データベース１０６内に含まれるデータによって表される道路網に対する車両の位置を判断する。車両測位アプリケーション２０６は、測位システム１０４からの出力を用い、時によってマップ照合アルゴリズムと呼ぶ車両測位アルゴリズムを用いて、この出力を地理データベース１０６内のデータと照合する。
【００２１】
電子視野アプリケーション２０８は、電子的視野を判断する。電子的視野は、電子視野アプリケーション２０８によって判断される範囲の現在の車両位置から前方の道路及び交差点の集合である。この道路及び交差点の集合は、車両が現在の車両位置から辿ることができる潜在的な経路である。電子視野アプリケーション２０８は、１つ又はそれよりも多くのコスト関数を用いて範囲を判断する。コスト関数は、運転者支援アプリケーション１１４の要求に基づいて、車両速度、走行時間、及び運転距離のような様々な要因を考慮に入れることができる。例示的な電子視野アプリケーションは、本出願と同じ出願人に譲渡され、本明細書においてその全内容が引用により組み込まれている米国特許第６、４０５、１２８号に説明されている。
【００２２】
インタフェースアプリケーション２１０は、インタフェース１１０及びバス１１２を通じたＭＰＥ１１６と運転者支援アプリケーション１１４の間の通信を制御する。好ましくは、インタフェースアプリケーション２１０は、車両内の様々な電子デバイス間で通信を行うためのシリアル通信プロトコルであるＣＡＮプロトコルに基づいている。メッセージ及びデータを車両内の１つの電子デバイスから別のものへと送信することができるように、ＣＡＮプロトコルに従って車両内の様々な電子デバイスを単一のシリアルバス（例えば、バス１１２）に結合することができる。ＣＡＮプロトコルは、ＣＡＮフレームが共通ＣＡＮバス上に置かれるメッセージベースのプロトコルである。ＣＡＮバスは、単一のワイヤ又は差動的に駆動されるワイヤ対とすることができる。
【００２３】
図３は、地理データベース１０６からの道路セグメントデータ記録３００のブロック図である。道路セグメントデータ記録３００は、道路の一部分を表すために用いられるデータを含む。これらのデータは、セグメントの端点の緯度、経度、及び高度の座標位置を示すノードデータ３０２、３０４を含む。
また、データは、直線又は曲線セグメントの形状を表すために用いることができる制御点の緯度、経度、及び高度の座標位置を示す制御点データ３０６、３０８を含む。図３には２つの制御点に関するデータを示しているが、セグメントは、１つよりも多くの曲線を含むことができ、制御点数は、セグメント内の曲線の数及び形状に依存するものとすることができることを理解されたい。例えば、各３次ベジエ曲線は、４つの制御点によって表されるが、前のベジエ曲線の最後の制御点は、次のベジエ曲線の最初の制御点と同じである。道路セグメントデータ記録３００は、ベジエ曲線の数を３倍し、１を足した数に等しい数の制御点に関するデータを記憶する。
【００２４】
更に、データは、セグメントに関する属性３１０を含む。セグメントの属性３１０の一部を図４に示す。同様に道路セグメントデータ記録３００は、形状点データのような追加データを含むことができる。
図４は、道路セグメントデータ記録３００におけるデータ属性３１０の一部のブロック図である。図４に示しているデータ属性３１０は、セグメント識別子（ＩＤ）４０２、制御点４０４、走行方向４０６、速度カテゴリ４０８、車線カテゴリ４１０、道路種類４１２、セグメント特性４１４、及び通行特性４１６を含む。これは、道路セグメントデータ記録における全てのデータ属性の網羅的なリストではないので、図４は、他の属性４１８も示している。例えば、セグメントデータ属性４００は、セグメントの端点３０２、３０４に対応するノードＩＤの形態のノードデータ記録への参照子を含むことができる。
セグメントＩＤ４０２は、地理データベース１０６内のデータ記録を識別する。
【００２５】
制御点属性４０４は、曲率及び勾配プロフィールの作成を助ける制御点に関する追加情報を提供するビットフラグを収容する。例えば、制御点属性４０４は、制御点毎にバイトサイズのフラグを含むことができる。フラグ内のビットのうちの１つは、曲率に割り当てられ、一方、ビットのうちの別のものは、勾配に割り当てられる。曲率ビットフラグが１に設定された場合には、制御点は、曲率プロフィールの一部としてマーク付けされる。同様に勾配ビットフラグが１に設定された場合には、制御点は、勾配プロフィールの一部としてマーク付けされる。
【００２６】
走行方向属性４０６は、セグメントにおいて許可される車の流れの方向を表している。例えば、セグメントは、道路網のうちで走行が双方向に許された部分を表すことができる。代替的に、セグメントは、道路網のうちで一方向の走行だけを可能にする部分を表すことができる。走行方向属性４０６は、セグメントが双方向走行又は単方向走行のいずれを可能にするのかを識別し、単方向の場合には、走行方向属性４０６は、許可された走行方向を更に識別する。
【００２７】
速度カテゴリ属性４０８は、掲示又は示唆された速度制限に基づく道路の一般的な速度傾向を表している。速度カテゴリ属性４０８は、速度範囲に関連するデータを含む。例えば、速度カテゴリ属性４０８は、８０ｍｐｈを超える速度に対して整数１、６５ｍｐｈ〜８０ｍｐｈの範囲の速度に対して整数２、５５ｍｐｈ〜６４ｍｐｈの範囲の速度に対して整数３、及び速度範囲が０ｍｐｈを含むまで以降同様に続くデータ表現を含むことができる。
【００２８】
車線カテゴリ属性４１０は、セグメントにおける１つの走行方向の主な車線数を表している。好ましくは、車線カテゴリ属性４１０は、右左折車線を含まない。車線数が各方向において異なる場合には、車線カテゴリ属性４１０は、大きい方の数を表すことができる。
道路種類属性４１２は、道路の種類及び／又はセグメントが表す機能部類を表している。例えば、道路種類属性４１２は、州間高速道路、通行制御高速道路、歩行者通路等に関連付けられたデータを含むことができる。
【００２９】
セグメント特性属性４１４は、様々なセグメント特性を説明するビットフラグを含む。例えば、セグメント特性属性４１４は、セグメントが舗装されているか、ランプであるか、橋であるか、トンネルであるか、及び環状交差点であるかなどを識別することができる。
アクセス特性属性４１６は、セグメントにおいて許可される交通の種類を定めるビットフラグを含む。例えば、アクセス特性属性４１６は、セグメントにおいて自動車、バス、トラック、タクシー、緊急車両、及び歩行者等が許可されているか否かを識別することができる。
【００３０】
ＭＰＥのための幾何学形状の作成
図５は、ＭＰＥ１１６のための幾何学形状を作成する方法５００の流れ図である。ブロック５０３では、方法５００は、並列処理を可能にするために地理データベース５０２をタイルへと再分割する。地理データベース５０２は、地理データベース１０６又は地理データベース１０６内のデータを含む異なるデータベースとすることができる。
これらのタイルは、各タイルがほぼ等量のノード及び形状点を含むように形成される。地図表面は、細かい（約２ｋｍ×２ｋｍ）セルを有する架空の２Ｄ矩形格子によって覆われる。次に、地理データベース５０２内のノード及び形状点を格子上にマップすることによってノード及び形状点の密度が計算される。タイルは、格子セルから組み立てられる。
各タイルがほぼ等しい数のノード及び形状点を有することを保証するために、格子全体は、水平及び垂直の両方の方向の格子線に沿って半分に再帰的に再分割され、２つの分割区分の各々が等しい数の幾何点を含むようにする。この処理は、タイルが、所定の閾値よりも少ない量のノード及び形状点を含むまで続く。各再分割の方向は、タイルのアスペクト比を最小にするように選択される。
【００３１】
ブロック５０４では、方法５００は、地理データベース５０２からのデータを用いて各タイル内でリンクチェーンを作成する。リンクチェーンは、各々が同じ道路種類属性４１２を有するセグメントのシーケンスである。好ましくは、セグメントシーケンスは、可能な限り長く作られる。リンクチェーンは、セグメント境界を横切る滑らかさを保証するＢ−スプライン当て嵌めを実施するのに用いられる。リンクチェーン５０４を作成する処理に対しては、図８に関連してより詳しく説明する。
【００３２】
ブロック５０６では、方法５００は、ブロック５０４で作成されたリンクチェーンを用いて２ＤのＢ−スプラインを作成する。ブロック５０８では、方法５００は、ブロック５０４で作成されたリンクチェーン、ブロック５０６で作成された２ＤのＢ−スプライン、及び高度データ５０７を用いて３ＤのＢ−スプラインを作成する。好ましくは、高度データ５０７は、道路セグメントによって表される道路上を車両が走行する時に収集されるＧＰＳ／ＩＭＵ記録から得られる。しかし、高度データ５０７は、他の供給源及び／又はセンサから得ることができる。２ＤのＢ−スプライン５０６を作成する処理に対しては、図９に関連して説明し、一方、３ＤのＢ−スプライン５０８を作成する処理に対しては、図１５及び図１６に関連して説明する。
【００３３】
スプラインは、曲線区間を表して区間の境界において指定の条件を満たす区分的多項式関数で形成されるあらゆる複合曲線を指す。すなわち、Ｂ−スプラインを含む多くの種類のスプライン曲線が存在する。Ｂ−スプラインは、制御点及び結び目を有する。結び目は、多項式スプライン曲線の個々の多項式曲線セグメントが互いに接合する点である。セグメントは、完全な曲線の滑らかさを生じるように接合される。結び目ベクトルは、スプライン曲線に沿ってセグメントが開始及び終了する点を説明する非減少浮動小数点数の序列リストである。スプラインは、当業技術で公知である。
【００３４】
スプラインを用いると、道路のカーブしている部分を含む地図特徴は、望ましい精度で地理特徴の形状に適合する曲線を生成するように判断された係数を有する多項式によって表される。従って、スプラインは、多項式の係数を指定することにより、基本的道路幾何学形状を説明するための手段である。米国特許第７、０８４、８８２号に説明されているように、スプラインは、ナビゲーションシステムのデータベースにおいて道路セグメントの形状を表すのに用いられている。米国特許第７、０８４、８８２号は、本出願と同じ出願人に譲渡されており、本明細書に引用によって組み込まれている。
【００３５】
ブロック５１０では、２ＤのＢ−スプライン及び３ＤのＢ−スプラインをベジエ曲線に変換することができる。セグメントが高度データを持たない場合には、２ＤのＢ−スプラインは、ベジエ曲線に変換される。しかし、セグメントが高度データを確実に有する場合には、２ＤのＢ−スプラインは、ブロック５０８で３ＤのＢ−スプラインを作成することだけに用いることができる。
３次ベジエ曲線は、２つの端点及び曲線に対する接線に沿って位置決めされたこれらの端点における２つの追加制御点によって定められる。３次ベジエ曲線式は、ベクトル形式で次式のように書くことができる。
【００３６】
【数１】
【００３７】
ここで、Ｐ0、Ｐ1、Ｐ2、及びＰ3は制御点であり、ｔはパラメータである。ベジエ曲線は、公知の方法を用いてＢ−スプライン曲線から導出することができる。
【００３８】
スプライン幾何学は、道路セグメント幾何学形状を表す上では有利であるが、ＭＰＥ１１６におけるＢ−スプラインの使用は、車両測位及び電子視野アプリケーション２０６、２０８における計算要件を増大させる。解析的なＢ−スプライン幾何学は、車両測位アプリケーション２０６によるポリライン表現及び電子視野アプリケーション２０８による電子視野の実時間導出を容易にするためにベジエ表現に変換される。
【００３９】
ブロック５１２では、車両測位アプリケーション２０６が、２Ｄポリライン表現を実時間で導出することができるように、ベジエ曲線は分割される。方法５００は、道路幾何学形状が、弦から最も遠い点が弦線上に投影される時にこの点が弦の内側に収まるようなベジエ曲線を有することを仮定する。ベジエ道路幾何学形状は、図６に示しているように、ベジエ曲線から、この曲線の端点３０２、３０４を結ぶ線（すなわち、制御多角形の基本弦：
【００４０】
【数２】
【００４１】
）までの最も遠い距離（又は複数の距離）にある１つの点６００（又は場合によっては１つよりも多くの点）を識別した後に分割される。図６では、最も遠い距離が、一般的に、曲線の中心にはないことも分る。
【００４２】
最適な再分割点６００は、ベジエ曲線上で制御多角形の基本弦から最も遠い点である。点６００の位置は、点６００におけるベジエ曲線に対する２Ｄの接線Ｂ（ｔ）が弦に対して平行であるという条件から解析的に得られる。
【００４３】
【数３】
【００４４】
上記表現は、パラメータｔに関する２次方程式へと簡略化される。一般的なベジエ曲線では、この２次方程式は、パラメータｔが定められる間隔［０〜１］内に実根を有することができない。しかし、穏やかな挙動を示すベジエ曲線では、２次方程式は［０〜１］間隔内に１つ又は２つの実根を有することになる。２次方程式が２つの実根を有する場合には、２つの再分割点が２つの点でベジエ曲線を分割するように用いられる。点６００が得られた状態で、ベジエ曲線は、デ・カステリョの再分割アルゴリズムを用いて２つに分割される。得られるベジエ曲線は、地理データベース１０６に記憶される。
ブロック５１４では、車両測位アプリケーション２０６は、２Ｄポリライン表現を実時間で導出する。ポリライン表現の例７００を図７に示す。車両測位アプリケーション２０６は、ベジエ曲線の端点７０２を結び、その一方で内部制御点７０４を無視することによってポリライン表現７００を導出する。
【００４５】
リンクチェーンの作成
図８は、リンクチェーンを作成する方法８００の流れ図である。リンクチェーンを作成する方法８００は、ＭＰＥ１１６における使用に向けて地理データベース１０６内にデータを記憶する前に、あらゆるコンピュータ上で実行することができるソフトウエアルーチン（又は複数のソフトウエアルーチン）である。
ブロック８０２では、リンクチェーンルーチン８００は、リンクチェーンを開始するセグメントを選択する。各セグメントは２つのノード（端点とも呼ぶ）を有する。全てのノードが交差点にあるわけではない。例えば、一部のノードは、道路属性の変化を符号化するのに用いられる。
【００４６】
ブロック８０４では、リンクチェーンは、隣接するセグメントを含めることによって両方の方向に成長する。ブロック８０６では、リンクチェーンルーチン８００は、ノードが末端であり、そのノードにおいてその方向にリンクチェーンが終了されるかを判断する。リンクチェーンルーチン８００は、ノードが末端であるかを判断するために規則を用いる。ノードを通じてリンクチェーンを進めるべきか（すなわち、非末端ノード）を判断するための規則は、以下のものを含むことができる。
１．リンクチェーン内の２つの隣接セグメントが、共通ノードを有するべきである。
２．リンクチェーン内のセグメントは、同じ機能部類に属さなければならない。
３．セグメントは、１つのリンクチェーン内だけに含まれるべきである。
４．各セグメントは、リンクチェーン内に含まれるべきである。
５．環状交差点セグメント（すなわち、環状交差点属性４１４に関連付けられたセグメント）を含むリンクチェーンは、通常のセグメントを含んではならない。
６．２つのセグメント間の角度が所定の閾値を超える場合には、これらのセグメントは、リンクチェーンを形成してはならない。この規則は、環状交差点チェーンには適応可能ではない。
７．ノードは、少なくとも２つのリンクに接続する。
末端ノードを識別するための他の規則を用いることもできる。ブロック８０６においてリンクチェーンルーチン８００が末端ノードを識別した場合には、リンクチェーンルーチン８００は、ブロック８１４においてリンクチェーンを成長させるのを終了する。
【００４７】
ブロック８０６においてリンクチェーンルーチン８００が末端ノードを識別しなかった場合には、リンクチェーンルーチン８００は、ブロック８０８でノードを通じる最適経路を判断する。各ノードにおいて、リンクチェーンルーチン８００は、リンクチェーンに追加することができるノードを通じた可能な経路を識別する。
ブロック８１０では、リンクチェーンルーチンは、各識別された可能な経路に対する経路重みを計算する。経路重みは、車線カテゴリ属性４１０、道路種類属性４１２、並びにノードからの経路の角度、及びセグメントによって表される道路上に保護レールが設けられているか否かのような他の属性４１８を用いて判断される。更に、経路重みは、交差点を通じた方向変化量を制限するように判断される。
【００４８】
リンクチェーンを継続するのにどの経路を用いるかを判断する１つの方法は、リンク間角度及びリンク間の車線数差という２つの要因の組合せに基づいている。リンクチェーンが新しいリンクに継続される確率は、次式に従って判断することができる。
【００４９】
【数４】
ここで、
【数５】
及び
【数６】
【００５０】
ここで、角度は、度を単位とするリンク間角度であり、Δ車線＃は、リンク間の車線数差（１０を超えない）である。
２つよりも多くのリンクが交差するあらゆるノードにおいて、規則に準ずるリンクチェーンを形成する可能な方法は、計算された確率に従って比較及び順位付けされ、最適な選択肢が選択される。従って、リンクチェーンの形成は、リンクチェーンが作成される順序には依存しない。
【００５１】
ブロック８１２では、リンクチェーンルーチン８００は、ブロック８１０で計算された経路重みに基づいて、このノードを通じて継続を行うか否かを判断する。リンクチェーンルーチン８００が、このノード通じて進むように判断した場合には、最も高い重みを有する経路が選択され、ブロック８０４でリンクチェーンに追加される。そうでなければ、リンクチェーンルーチン８００は、ブロック８１４でリンクチェーンを成長させるのを終了する。
【００５２】
ブロック８１６では、リンクチェーンルーチン８００は、１つの操作で曲線当て嵌めを行うには長すぎるリンクチェーンを分割する。この判断は、チェーンの長さ（例えば、長さが２５ｋｍを超える）、ノード及び形状点の合計数（例えば、５０００を超える）、及び／又は他の要因に基づいて行うことができる。好ましくは、リンクチェーンルーチン８００は、ポリライン長さの中間部の近くで、リンクチェーンポリラインが可能な限り直線のところでリンクチェーンを分割する。
【００５３】
両方の目的を達成するために、リンクチェーンルーチン８００は、リンクチェーンの中間部の最も近くに位置するノードから開始して両方の方向に検索を開始する。考察対象のあらゆるノードに対して、リンクチェーンルーチン８００は、ノードの周囲に窓を構成し、このノードが比較的直線のセグメント内に位置するかを判断する。リンクチェーンルーチン８００は、内部点を２つの端点で形成されたセグメント上に投影し、点からセグメントまでの距離が閾値を超えず、これらの内部点が、セグメントの内部に投影されることを検証することによってセグメントが直線であるかを判断する。リンクチェーンルーチン８００は、目的を満たすノードを見つけるまで、両方の方向に検索し続ける。リンクチェーンルーチン８００は、分割に適するノードが見つからなかった場合には、直線セグメントの基準を緩和し、再度検索を繰り返す。
【００５４】
２ＤのＢ−スプラインの作成
図９は、リンクチェーンから２ＤのＢ−スプラインを作成する方法９００の流れ図である。方法８００と同様に、２ＤのＢ−スプラインを作成する方法９００は、ＭＰＥ１１６における使用に向けて地理データベース１０６内にデータを記憶する前に、あらゆるコンピュータ上で実行することができるソフトウエアルーチン（又は複数のソフトウエアルーチン）である。
ブロック９０２では、２ＤのＢ−スプラインルーチン９００は、方法８００によって作成されたリンクチェーンを２ＤのＢ−スプラインに当て嵌める。２ＤのＢ−スプラインルーチン９００は、２ＤのＢ−スプラインを単一のリンクチェーンであり、可能な場合はこのチェーンに隣接するリンクチェーンからのデータ点を両方の端に含むリンクチェーンに当て嵌める。隣接するリンクチェーンからのデータ点を含めることにより、２ＤのＢ−スプラインルーチン９００は、連続する曲線当て嵌めを重ね合わせ、それによって曲線当て嵌め間の境界における形状整合性を保証することができる。隣接するリンクチェーンからのデータ点をどの場合に用いるべきかに関する判断は、規則によって制御される。環状交差点は、隣接するリンクチェーンからのデータ点が用いられない場合の例である。隣接するリンクチェーンの重複は、大きい場合がある（一般的に、数キロメートル）。
【００５５】
２Ｄの曲線当て嵌め技術は、指定の曲線当て嵌め許容範囲に基づいて最適な局所曲線堅牢性を反復的に判断する。２ＤのＢ−スプラインルーチン９００は、変分法を用いてスプラインに沿った曲率変化を最小にすることによってスプライン当て嵌めを正則化する。曲線当て嵌めは、次の汎関数を最小にすることによって実行される。
【００５６】
【数７】
【００５７】
式１：曲線当て嵌め最小化汎関数、ここで、ｖj（ｓ）は、反復数［ｊ］において曲線に沿って変化する正則化量を表している。ｖj（ｓ）は、曲線に沿った弧長の関数として連続関数とすることができ、又はスプラインの各曲線セグメントに対する固有値のように離散的に実施することができる。
【００５８】
積分：
【数８】
は、当て嵌められた曲線に沿った曲率変化を表している。曲率変化を最小にする正則化関数は、代替的に、
【数９】
で表すことができる。最小二乗項：
【数１０】
は、当て嵌められた曲線とデータ点の間の偏差を示している。全体として、曲線当て嵌め最小化汎関数は、データ点からの偏差を最小にする一方、基本的道路幾何学形状を取り込むデータ点との対応を保ちながら、曲率が可能な限り小さく変化することを保証する。ブロック９０２におけるリンクチェーンへの２Ｄスプライン当て嵌めに対しては、図１２を参照してより詳細に説明する。
【００５９】
ブロック９０４では、２ＤのＢ−スプラインルーチン９００は、タイル内で不整合なＢ−スプライン端を整合化する。スプライン当て嵌めは重複するが、出会わないＢ−スプライン端１００２、１００４を示している図１０に示しているように、得られるＢ−スプラインの全てがノードにおいて完全に接合するわけではない。図１１に示しているように２つのＢ−スプラインをノード１１００で整合化するためには、これらのＢ−スプライン端が、ＸＹ平面内の共通点において、平滑な接線及び曲率（すなわち、Ｃ２連続性）を有しながら出会うようにこれらの端を整合化するべきである。
【００６０】
Ｂ−スプライン端を整合化するために、２ＤのＢ−スプラインルーチン９００は、パッチＢ−スプラインを用いて２つのＢ−スプライン間の平滑な移行を作成する。２ＤのＢ−スプラインルーチン９００は、不整合Ｂ−スプライン端１００２、１００４の間のパッチＢ−スプライン上に中間点を投影する。２ＤのＢ−スプラインルーチン９００は、パッチＢ−スプラインを分割し、結び目ベクトルを融合してパッチＢ−スプラインの各半分が不整合Ｂ−スプラインに適合するようにする。２ＤのＢ−スプラインルーチン９００は、既存のＢ−スプライン形状を置換するパッチＢ−スプラインに対するパラメータ範囲を判断し、置換領域において再分割されたパッチＢ−スプラインからこれらのＢ−スプラインに制御点を複写する。２ＤのＢ−スプラインルーチン９００は、良好なＢ−スプライン品質（例えば、位置、車両方位、曲率誤差において誤差許容範囲の）を保証しながら、あらゆる不用な結び目（例えば、Ｂ−スプラインを適合化する結び目融合段階に起因する）を削除する。
【００６１】
ブロック９０６では、２ＤのＢ−スプラインルーチン９００は、タイル境界を跨ぐＢ−スプラインを整合化する。タイル間のＢ−スプラインは、ブロック９０４を参照して説明したものと同様の方式で整合化される。この整合化では、第１のＢ−スプラインに対する曲線当て嵌めは、１つのタイル内にあり、第２のＢ−スプラインに対する曲線当て嵌めは、隣接タイル内にあり、パッチＢ−スプラインは、タイル境界を横切って当て嵌めが行われる。タイルを横切ってのＢ−スプライン整合化は、タイル境界において継ぎ目のないＣ２のＢ−スプライン接合部を作り出す。
【００６２】
ブロック９０８では、２ＤのＢ−スプラインルーチン９００は、３つ又はそれよりも多くの道路が出会う交差点におけるＢ−スプライン端を整合化する。各交差点において、２ＤのＢ−スプラインルーチン９００は、自己交差点を含む交差リンクチェーンＢ−スプラインを探し出す。自己交差Ｂ−スプラインを含む２つのＢ−スプラインの交差点を識別する技術は、当業技術で公知である。交差するＢ−スプラインの各々に対して、２ＤのＢ−スプラインルーチン９００は、交差点を十字路Ｂ−スプライン（すなわち、４つのセグメントが単一のノードで出会う）、Ｔ字路、又は複合交差点（すなわち、４つよりも多くのセグメントが単一のノードで出会う）として分類する。２ＤのＢ−スプラインルーチン９００は、これらの道路を表すＢ−スプラインを共通ノードにおいて接合する。
【００６３】
ブロック９１０では、２ＤのＢ−スプラインルーチン９００は、スプラインにおける最適な分割場所を判断する。ノードが交差点ではない場合には、２ＤのＢ−スプラインルーチン９００は、ノードをリンクチェーンのＢ−スプライン上に投影し、分割場所を識別する。ノードが交差点ノードである場合には、２ＤのＢ−スプラインルーチン９００は、ブロック９０８を参照して説明した交差点分類に基づいて最適な分割場所を判断する。
【００６４】
ブロック９１２では、２ＤのＢ−スプラインルーチン９００は、ブロック９１０で判断された分割場所を用いてノードにおいてリンクチェーンのスプラインを分割し、各セグメントに対して１つの個々のＢ−スプラインを形成する。十字路Ｂ−スプラインでは、２ＤのＢ−スプラインルーチン９００は、スプラインをこれらのスプラインが交差する場所で分割し、道路が出会う共通の端点を作成する。
Ｔ字路では、近似Ｂ−スプライン曲線当て嵌め技術の性質に起因して、２つのリンクチェーンＢ−スプラインは、Ｔ字路で交差するか又は交差しない可能性がある。交差するＴ字路リンクチェーンのＢ−スプラインでは、２ＤのＢ−スプラインルーチン９００は、あらゆる重複区間を切り取って廃棄する。非交差のＴ字路では、２ＤのＢ−スプラインルーチン９００は、繋ぐ側の道路に対する終端Ｂ−スプラインを主道路リンクチェーンのＢ−スプラインに延長又は短絡させる（すなわち、曲げる又はシフトする）ことによって交差点の場所を作成する。主道路Ｂ−スプラインは、終端Ｂ−スプラインが延長及び短絡の後に主道路Ｂ−スプラインに接合する場所で分割される。Ｂ−スプラインの形状又は位置を延長及び調節するための技術は当業技術で公知である。
【００６５】
４つよりも多くのセグメントが単一のノードで出会う多重リンク交差点に対して、２ＤのＢ−スプラインルーチン９００は、セグメントが共通ノードで出会うように２Ｄスプライン幾何学形状を調節する。Ｂ−スプラインの局所サポート、及びこれらのＢ−スプラインがアフィン変換に対して不変量であるという事実に起因して、Ｂ−スプラインは、形状及び位置の調節に非常に適するものにされる。Ｂ−スプライン幾何学形状を調節するための技術は、当業技術で公知である。
【００６６】
各多重リンク交差点に対して、２ＤのＢ−スプラインルーチン９００は、交差点ノードの共通の２Ｄの場所を判断する。最適な場所は、交差点幾何学形状、複雑度、及び周囲のリンク接続性に依存する。次に、Ｂ−スプラインの局所的な曲率又は車両方位の品質に影響を与えずにこれらのスプラインを整合化するために、交差点の近くでＢ−スプラインはシフトされるか、又はこれらのスプラインの２Ｄの形状が調節される。調節段階の後に、２ＤのＢ−スプラインルーチン９００は、共通の交差点の場所においてＢ−スプラインを分割する。
【００６７】
ブロック９１４では、２ＤのＢ−スプラインルーチン９００は、２Ｄの曲率情報を２ＤのＢ−スプライン内に符号化する。符号化された曲率情報は、Ｂ−スプラインに沿って、曲率が弧長に対して線形に変化する場所を識別する。Ｂ−スプライン上で符号化された場所の各対の間では、各区間で曲率が弧長に対して線形に変化するので、曲率は、線形「クロソイド」と見なされる。これらのクロソイドの場所は、最初に、弧長の関数としての曲率のグラフであるＢ−スプラインに関する「曲率プロフィール」を作成することによって判断される。次に、曲率プロフィールは、線形曲率区間によって曲率プロフィールを近似するために、ポリラインによって近似される（Ｄｏｕｇｌａｓ−Ｐｅｕｋｅｒアルゴリズムに基づいて）。Ｂ−スプラインに沿ったポリラインの頂点の場所は、これらの場所にタグ付き結び目を挿入することによってＢ−スプライン内に符号化される。
【００６８】
ブロック９１６では、２ＤのＢ−スプラインルーチン９００は、結び目ベクトルを最適化する。ブロック９０２における曲線当て嵌め中に用いられる結び目ベクトルは、結び目数及び結び目の間隔に関して必ずしも最適ではない。結び目ベクトルは、２Ｄの位置、形状、車両方位、及び曲率の品質を維持しながら、物理的記憶媒体上の記憶スペースを最小にするように最適化される。
２ＤのＢ−スプラインルーチン９００は、ブロック９１４で判断された２ＤのＢ−スプラインに沿った対応するクロソイドセグメント（すなわち、線形曲率領域）を識別することによって最適な結び目配置を探し出す。長いクロソイドセグメントは、等しい弧長間隔で結び目を挿入することによって近似することができる。これらの追加結び目は、長いクロソイドセグメントを単一の結び目スパンを用いて正確に表すことができない場所でＢ−スプライン曲線の形状を維持する。
【００６９】
２ＤのＢ−スプラインルーチン９００は、ブロック９１４で曲率を符号化するのに用いられなかったあらゆる結び目、又は元のＢ−スプラインの２Ｄの位置、形状、車両方位、及び曲率の許容範囲にこのＢ−スプラインを保つのに必要とされないあらゆる結び目を削除する。一般的に、最適な結び目間隔は、曲率に反比例する（すなわち、曲率が大きい程、結び目はより近く離間される）。
【００７０】
リンクチェーンへの２Ｄ曲線当て嵌め
図１２は、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００の流れ図である。ブロック１２０２では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、曲線当て嵌め中に撓み及び振動のような曲線形状不規則性を防止する。例示的な防止段階は、直線形状を維持し、撓まない又は振動しないように曲線を拘束するためのリンクチェーンのうちで直線と分類される区間内への「仮想」形状点の挿入を含む。
【００７１】
ブロック１２０４では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ある一定の機能部類のリンクチェーン（例えば、高速道路、主要幹線）又は折り返しリンクチェーンを除く全ての道路に対するリンクチェーン内であらゆる捩れが存在するかを判断する。形状点は、この形状点で出会うリンクセグメントの間の角度が「捩れ」閾値を超えた場合に、「捩れ」として識別される。例えば、捩れ閾値は、３５度に設定することができる。
【００７２】
捩れを表すスプライン曲線では、曲線は、捩れの場所で不連続導関数（すなわち、Ｃ０連続性のみ）を有する。ブロック１２０４においてリンクチェーン内に１つ又はそれよりも多くの捩れが検出された場合には、ブロック１２０６において、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、各リンクの場所においてリンクチェーンを捩れの間の個々の部分リンクチェーンに分割する。リンクチェーン内に捩れが存在しない場合には、ブロック１２１８において、リンクチェーン全体に対して２Ｄスプライン当て嵌めが実施される。
【００７３】
ブロック１２０８では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ブロック９０２を参照して説明した２Ｄ曲線当て嵌め技術を用いて、部分リンクチェーンの各々に対して２ＤのＢ−スプラインで曲線当て嵌めを行う。得られるスプライン曲線は、捩れの場所においてＣ０連続性を有しながら出会う。
ブロック１２１０では、リンクチェーンは、ここでは複数のスプラインによって表されるので、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、部分リンクチェーンを単一のスプラインへと互いに縫合する。個々のＢ−スプライン曲線を単一の連続Ｂ−スプライン曲線へと接合するために、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、３次不均一Ｂ−スプラインが曲線上のこの曲線が捩れる場所（すなわち、この曲線がＣ０連続性のみを有するところ）で結び目多重度３を有するという不均一Ｂ−スプラインの性質を利用する。
【００７４】
Ｂ−スプライン曲線は、一度に１つ追加され、従って、複数のＢ−スプライン曲線を接合することが望ましい場合は、この接合は、最初の曲線に第２の曲線を追加して単一の曲線を形成し、この単一の曲線に対して次の曲線を追加することができ、以降同様に続けることによって達成される。Ｂ−スプライン曲線を接合するための技術は、当業技術で公知である。共通端点を有する２つの不均一３次Ｂ−スプライン曲線は、これらの曲線の制御点配列を連結し、それらの結び目ベクトルを追加することによってＣ０連続性を有しながら接合することができる。
【００７５】
ブロック１２１２では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、Ｂ−スプライン形状不規則性を補正する。Ｂ−スプライン形状不規則性は、撓み及び振動を含むことができるが、ノイズの多い曲率のような他の曲線不規則性が存在する領域を含むことができる。不規則性は、セグメントの曲線を定めるのに不十分な形状点しか用いられない場合、又は道路セグメントが劣悪に配置された形状点しか持たない場合に発生する可能性がある。Ｂ−スプラインが直線ではなく、基本的な道路幾何学形状が仮想形状点を追加した後には直線であることが既知である場合には、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ブロック１２１２において、Ｂ−スプラインを直線化するために制御点を操作することができる。ノイズの多い曲率領域を平滑にするのに同様の技術を用いることができる。
【００７６】
ブロック１２０４に戻ると、リンクチェーンが捩れを持たない場合には、ブロック１２１４において、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、リンクチェーンがあらゆる端にランプを含むかを判断する。リンクチェーンがランプを含む場合には、ブロック１２１６において、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、正しいランプ形状及び曲率を保証するために、端ノード及び形状点のランプオフセットを実施する。図１３に示しているように、ランプが自動車専用道路上に合流するランプ端において正しい方位及び曲率を得るために、スプライン当て嵌めにおいて、ランプリンクチェーンのノード及び形状点に加えて自動車専用道路のノード及び形状点が用いられる。
【００７７】
２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、スプライン当て嵌めに向けて以下の通りにランプを通じる点を編成する。
１．リンクチェーンがランプで始まるのか、又は終わるのかを判断する。
２．ランプリンクチェーンと自動車専用道路との間で共通するノードを識別する。
３．ランプリンクチェーンが一部の自動車専用道路で終わる場合には、自動車専用道路リンクセグメントとランプリンクセグメントの間の角度、及び機能部類に基づいて対応する自動車専用道路を選択する。
４．自動車専用道路リンクセグメントとランプリンクセグメントの間の角度が、閾値（例えば、５０度）を超える場合には、スプラインは、自動車専用道路形状点を通じて当て嵌められない。
５．自動車専用道路リンクセグメントとランプリンクセグメントの間の角度が、閾値（例えば、５０度）よりも小さい場合には、ランプ形状が自動車専用道路形状に追従することを保証するために、自動車専用道路点を編成することによってスプライン当て嵌めは自動車専用道路内に延長される。
６．ランプノード及び場合によっては自動車専用道路点は、図１４に示しているように車線幅に対処するようにオフセットされる。ランプの端ノード及び場合によっては隣接ノード／形状点は、ランプリンクチェーン、及び後のスプラインが、自動車専用道路の中心線への不自然な接続ではなく、ランプから自動車専用道路車線への実際の自動車経路を辿るようにシフトされる。
７．編成されてオフセットされたノード及び形状点にスプラインを当て嵌める。
８．ブロック９１２で自動車専用道路ノードにおいてスプラインを切り取る。
【００７８】
図１４に示しているランプオフセットベクトル１４０２の長さは、既知又は推定の自動車専用道路幅に依存する。推定幅は、自動車専用道路の車線数、自動車専用道路の走行方向制限（すなわち、一方向又は双方向）、及びランプにおける車線数（ランプは常に一方向であると仮定される）に基づいて判断される。ランプスプラインが自動車専用道路の中心線に向って歪むのを回避するために、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ランプの内部形状点及び／又はノードが、オフセットされた自動車専用道路／ランプ共通ノードよりも自動車専用道路の中心線に近くないことを保証する。ランプの内部形状点及び／又はノードの一部が近い場合には、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ランプ／自動車専用道路交差点ノードから分離する自動車専用道路リンクセグメントに対して平行な線であり、交差点ノードをオフセットすることによって生じる想像ノードを通過する線上にランプの内部形状点及び／又はノードを投影する。図１３は、一般的な四葉のクローバー状ランプにおいて得られるランプスプライン形状を示している。
ブロック１２１８では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、ブロック９０２を参照して説明したように、リンクチェーンに２ＤのＢ−スプラインを当て嵌める。ブロック１２１２では、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、上述のようにＢ−スプライン形状不規則性を補正する。
【００７９】
ブロック１２１４に戻ると、リンクチェーンがランプではない場合には、ブロック１２２０において、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、リンクチェーンが環状交差点であるかを判断する。リンクチェーンが環状交差点である場合には、ブロック１２２２において、２ＤのＢ−スプライン曲線当て嵌めルーチン１２００は、環状交差点を３周回するようにリンクチェーンを延ばす。環状交差点に対する複数周回のスプライン当て嵌めは、水滴形の環状交差点幾何学形状を防止する。その後、ブロック９１２において、重複環状交差点スプラインの適切な区間が切り取られて、環状交差点に対する個々のスプラインが得られる。
【００８０】
３ＤのＢ−スプラインの作成
図１５は、３ＤのＢ−スプラインを作成する方法１５００の流れ図である。３ＤのＢ−スプラインを作成する方法１５００は、ＭＰＥ１１６における使用に向けて地理データベース１０６内にデータを記憶する前に、あらゆるコンピュータ上で実行することができるソフトウエアルーチン（又は複数のソフトウエアルーチン）である。
３ＤのＢ−スプラインは、２ＤのＢ−スプライン（２ＤのＢ−スプラインルーチン９００を用いて得られる）を１Ｄの標高スプラインと組み合わせることによって作成される。１Ｄの標高スプラインは、車両において収集されたＧＰＳデータにスプラインを当て嵌めることによって作成される。３Ｄスプラインを必要とする道路を収集車両を用いて運転することにより、大量の順次データ点（緯度、経度、高度、車両方位、勾配、及び／又は速度データが関連付けられたもの）がもたらされる。絶対的及び相対的な地理的場所の精度を維持するために、データ点は、ＧＰＳ及び慣性測定ユニット（ＧＰＳ／ＩＭＵ）を用いて収集される。高度点データセットは、あらゆるデータ異常を削除するためにフィルタリング及び調節される。フィルタリングは、給油停車、オフロード運転、及び方向転換操縦等に起因するあらゆる外生データを除去する。次に、データセットは、空間及び時間連続性に基づいて小さいデータセットへとまとめられる。
【００８１】
ブロック１５０２では、記憶及びデータセット間の地理参照を容易にするために、高度点は、既知の幾何学形状の２Ｄ道路中心線のデータベース上にこれらの高度点を投影する（２ＤのＸＹ投影を用いて）ことによって編成される。各点は、特定の道路リンクに割り当てられ、このリンクに沿う特定の距離へとパラメータ化される。この関連付けにより、標高データが道路データベース内の既存の情報を参照することが可能になる。
【００８２】
３ＤのＢ−スプラインルーチン１５００は、既知の道路リンク経路（道路網）に沿って進み、点を各可能なリンク経路上に投影することにより、点から２Ｄリンクへの投影を実施する。可能なリンク経路数は、一方向の走行方向制限及び機能部類レベルのようなデータベース内で符号化された道路制限によって絞り込まれる。ＧＰＳ点記録に対する正しいリンク経路を得るために、単一の正しい経路が見つかるまで複数の経路が試験される。複数の有効な経路が見つかった場合には、元のＧＰＳ経路形状とリンク投影経路形状の間の差に基づいて罰則基準が計算され、最小の合計２Ｄオフセット、角度差、形状差、及び／又は走行距離差を有する経路が正しい道路リンクシーケンスとして選択される。このリンクシーケンスを標高リンクチェーンと呼ぶ。
【００８３】
ブロック１５０４では、３ＤのＢ−スプラインルーチン１５００は、１Ｄの高度Ｂ−スプラインを標高リンクチェーンに沿って高度点に当て嵌める。それによって記憶スペース及びデータベースＩ／Ｏ帯域幅を節約するコンパクトな標高表現が可能になる。ブロック１５０２において得られた高度点は、リンクチェーン順序及び２Ｄの点／リンク投影から見つかるリンクパラメータ距離に基づいて標高リンクチェーンに沿って単調に整列する。投影された標高点の各々までの２Ｄ弧長距離を計算するために、標高リンクチェーンに対してトラバース測定が行われる。このデータ対（リンクチェーン弧長と標高との）は、１Ｄの標高スプラインを計算するためのデータセットを形成する。
【００８４】
３ＤのＢ−スプラインルーチン１５００は、１Ｄの標高スプラインを作成する前に標高リンクチェーンを小さいリンクチェーンに分割する。目標は、各道路リンクに対して個々のスプラインを作成することであるが、リンク境界を跨ぐ平滑な高度Ｂ−スプラインを維持するために、複数のリンクチェーン区間（例えば、１０００メートルまでの）にわたる中間スプラインが生成される。３ＤのＢ−スプラインルーチン１５００は、同様に標高リンクチェーン境界を横切って平滑なスプラインが生成されるように、大きいリンクチェーンに重なっている。
【００８５】
一部の場合には、隣接リンクを跨ぐ単一の標高スプライン当て嵌めは望ましくない。従って、３ＤのＢ−スプラインルーチン１５００は、基本的道路データベース特性及び運転経路に基づいて大きいリンクチェーンを更に分割し、これらのリンクチェーンは、標高が突然の勾配又は標高変化を含む可能性がある場所で分割される。例えば、チェーンは、経路が８０度よりも大きく屈曲する時（例えば、異なる道路に乗る）、及びリンクチェーンがデータ格差を含む場合に分割される。次に、３ＤのＢ−スプラインルーチン１５００は、道路リンクノードの場所で１Ｄ高度Ｂ−スプラインを分割する。
【００８６】
３ＤのＢ−スプラインルーチン１５００は、得られるＢ−スプラインを各スプラインが２Ｄの道路リンク参照情報に連結されるようにデータベースに記憶する。更に、各道路リンクの標高スプラインに対して２つの横断時標高（スプライン開始及び終了点における）が保存される。横断時標高は、スプラインが道路リンクノードを横切る時のスプラインの高度を記憶する。このリンクノードへの参照情報が記憶される。標高スプラインが重複する場合には、単一の道路リンクノードは、複数の横断時標高を含むことになる。この横断時標高データベースは、標高スプラインの可能な交差場所を説明し、３ＤのＢ−スプラインルーチン１５００が、ブロック１５０６において、交差場所及び交差するスプラインの間の高度差を効率的に照会することを可能にする。
【００８７】
ブロック１５０２及び１５０４では、３ＤのＢ−スプラインルーチン１５００は、以前の道路属性把握内容をスプラインに追加することができるように、高度Ｂ−スプラインデータを道路リンク地図データベースに関連付ける。それによって標高データが交差点にあるのか、又はランプ（交差する標高が異なることが許される）上にあるのかを把握するなどの高度Ｂ−スプラインの知的処理が可能になる。従って、より正確な標高に関する解法が可能である。
【００８８】
ブロック１５０６では、３ＤのＢ−スプラインルーチン１５００は、道路網に沿って走行する車両内に設けられたＧＰＳ／ＩＭＵによって収集された高度データを調節する。高度補正ルーチンの例に対して、図１６を参照してより詳しく解説する。ＧＰＳ／ＩＭＵ地理参照機器の精度限界により、収集されたデータ点の絶対高度にある程度のドリフトが導入される可能性がある。その結果、２つの道路が交差する時に、各スプラインは、同じ交差点に対して若干異なる高度を間違って説明する可能性がある。一部のスプライン交差ノードは、異なる高度を有する（別の道路の上方を横断する橋等）。従って、標高補正ルーチンは、３Ｄスプラインが縦断勾配で交差するところを判断する。高度Ｂ−スプラインに関連付けられた道路地図データベース（Ｂ−スプライン道路リンクを参照情報として用いる）を利用することにより、道路リンクがどこで交差するか、これらのリンクが同じ高度でつながっているか、又はリンクが高架通路であるか、又は地下交通路であるかを把握することができる。横断時標高データベースは、この目的のためにブロック１５０４で作成されたものである。
【００８９】
図１６は、標高補正ルーチン１６００の流れ図である。標高補正ルーチン１６００は、標高スプラインのデータベース全体が単一の処理で補正されるように、好ましくは広域操作として実施される。１つの標高データセットを移動することにより、このデータセットが交差する他の標高データセットの当て嵌めが影響を受けるので、広域的解法が望ましい。広域的解法の作業負荷を最小にするために、標高補正ルーチン１６００は、横断時標高（ブロック１５０４で得られた）だけにアクセスする。データは、横断時標高データベースに対して実施される１回のデータベース照会によってアクセス可能である。このアクセスは、標高スプラインが交差するノードを探し出し、スプラインが重複するノードのみが戻される。それによって標高補正ルーチン１６００は、実際の標高スプラインをアクセス又は評価する必要なく、標高差を調べることが可能になる。
【００９０】
標高補正ルーチン１６００は、２つの操作を高度スプラインに適用する。第１に、スプラインが、同じ標高にある共通の道路リンクノードを横断するように、標高が垂直に補正される。第２に、多くの場合に、単一の道路リンクに対して複数の標高スプラインが利用可能である。標高補正ルーチン１６００は、各道路リンクに対して単一の最適な高度スプラインを選択する。この後、選択された最適の高度スプラインは、高度スプライン作成処理の残りの部分に用いられる。
【００９１】
道路リンクノードにおいて標高を整合化するのに、標高は、可能な限り最小限にしか変更されず、データにおける整合性を維持することに重点が置かれる。標高データは、その周囲の時間的に局所的なデータと比較すると非常に正確である。しかし、ドリフトに起因して、絶対標高は、大きい偏差を含む可能性がある。従って、整合化処理は、近接データ（高い相対精度）の使用を最大化し、異なるデータベース（絶対標高依存の）間の切り換えを最小にする。冗長な標高データの平均化は勧められない。代替的に、標高補正ルーチン１６００は、最良のデータセットから単一の最良の標高を選択することによってノードの標高を判断する。理想的には、整合性を維持するために、可能な限り最大の近くの標高ノードに対して同じデータセットが用いられる。
【００９２】
ブロック１６０２では、標高データセットは、これらのデータセットが標高において如何に良好に他の近接データセットの標高と合致するかということ、運転距離、及び運転精度信頼度に基づいて順位付けされる。この順位は、運転行程が、標高補正ルーチン１６００において適用される順序を制御する。この順序は、どの標高が元の標高スプラインから直接に割り当てられるか（「基本ノード」標高と呼ぶ）、及び既存の標高スプラインに当て嵌める上でどの標高が調節されるか（補正標高）を判断する。更に、この順序は、どの標高スプラインが（単一の道路リンクに対して複数のスプラインが利用可能である時に）、ブロック１５０８において最終高度スプラインを生成する時に用いるべきスプラインとして選択されるかを判断する。
【００９３】
ブロック１６０４では、最低信頼度レベルから外れる運転行程が整合化処理から除外される。それによって信頼性の低いデータが、不用な標高オフセットを引き起こすことが防止される。
ブロック１６０６では、標高補正処理を開始するのに最上位の運転行程が選択される。最初の運転行程は、いかなる既存の基本ノードの標高とも重複しないので、最初の運転行程は、標高において調節する必要はない。従って、ブロック１６０８では、標高補正ルーチン１６００は、補正曲線なしに最初の運転行程におけるノードを「基本ノード」として割り当てる。最初の運転行程と交差する以降（ブロック１６１２より）のあらゆるスプラインは、基本ノードと整合化するように変更される。更に、ブロック１６１０では、標高補正ルーチン１６００は、この運転行程からの標高スプラインを関連の２Ｄ道路リンクに対する最適スプラインとして割り当てる。
【００９４】
ブロック１６１２では、標高補正ルーチン１６００は、順位付けされたリストから、前に固定された運転行程の基本ノードと交差する次に最良の運転行程を選択する。ブロック１６１４では、標高補正ルーチン１６００は、標高ノードを検査して、どのノードが、前の運転行程の前に固定されたもの（基本ノード）に対応するかを調べる。運転行程のノードを既存の基本ノードの標高と整合化するために、オフセットが計算される。
【００９５】
運転行程ノードを既存の基本ノードに対して調節するのに加えて、基本ノード間で標高補正が線形に適用される。元の標高データを保持するために、元の標高スプラインを変更する代わりに仮想補正ポリラインが作成される。元の標高スプラインと仮想補正ポリラインの重ね合わせは、正しく整合化された高度スプラインを生じる。仮想ポリラインは、元のスプラインが他方の高度スプラインの基本ノードに当て嵌まるように補正するのに必要な標高オフセットを定める線形形状である。線形補正を用いることにより、標高補正ルーチン１６００が、正確な場所で精密に補正を定める（すなわち、オーバーシュートがない）ことが可能になり、同様に標高補正ルーチン１６００が、大きい２Ｄ距離にわたって補正を線形に分散させることが可能になる。
【００９６】
この処理の恩典は、標高スプラインデータベースが一度もアクセスされず、スプライン形状を読み取り、変更し、及び保存する必要がないことである。この処理は、大きい広域操作であるから、データベースＩ／Ｏ及びＣＰＵ要件の有意な節約が行われる。データベース作動は、最小限のデータセットを読み取ることへと変形され、複数の横断時標高を有するノードのみが考察される。書込み作動は、各運転行程に対して単一の線形補正ポリラインを保存する段階、及び標高スプライン上のステータスフラグ（スプラインが、道路リンクに対する独特な代表として選択されたか否かを示す）を更新する段階という２つの段階へと変形される。
【００９７】
ブロック１６１６では、標高補正ルーチン１６００は、計算された整合化オフセットを表す仮想の線形ポリラインを作成する。仮想ポリライン補正は、運転行程における非基本ノードの補正ノード高度を判断するのに用いられる。ブロック１６１８では、標高補正ルーチン１６００は、補正高度のノードを固定の基本ノードリストに追加する。
各運転行程が適用される時に、運転行程に関連付けられた道路リンクが検査され、これらのリンクに、以前の運転行程からの独特な「最適」高度スプラインが以前に割り当てられているか否かが調べられる。ブロック１６２０では、標高補正ルーチン１６００は、最適のスプラインを持たないリンクに現在の運転行程データセットからの標高スプラインを割り当てる。その結果、標高が固定された運転行程と対応する高度スプラインセットが生じ、この高度スプラインセットは、以降の標高データセットに対する基礎を与える。
【００９８】
ブロック１６２２では、標高補正ルーチン１６００は、検査を行って既存の基本ノードの標高と重複する更に別の運転行程データセットが存在するか否かを調べる。重複データセットが存在する場合には、ブロック１６１２において、標高補正ルーチン１６００は、既存の基本ノードと重複する次に最良の運転行程を選択し、上記処理が繰り返される。重複運転行程を処理し終わると、ブロック１６２４において、標高補正ルーチン１６００は、いずれか残りの未処理運転行程が存在するか否かを検査する。未処理運転行程が残っている場合には、ブロック１６０６において、標高補正ルーチン１６００は、残りの最良の運転行程に対して新しい整合化処理を再開する。
好ましくは、標高補正ルーチン１６００は、運転行程の全てを処理し終わるまで繰り返される。処理の後に、標高補正曲線がデータベースに記憶され、単一で独特な標高スプラインが道路リンクに関連付けられる。
【００９９】
図１５に戻ると、ブロック１５０８において、３ＤのＢ−スプラインルーチン１５００は、方法８００において作成されたリンクチェーンに対して単一の多重リンク高度スプラインを作成する。リンクチェーン内の各リンク（道路セグメント）に対して、前に選択された最適な高度Ｂ−スプライン（ブロック１５０６における）が、例えば、１メートルのＸＹ弧長毎に標高点に変換して戻される。補正ポリラインオフセット（ブロック１５０６）が計算され、各点に追加される。結果は、リンクチェーンのＸＹ弧長によってパラメータ化された高度が整合化された点の集合である。
【０１００】
３ＤのＢ−スプラインルーチン１５００は、新しい高度Ｂ−スプラインを複数のリンクに対して標高がパラメータ化された点のリストに当て嵌める。各連続する曲線当て嵌めは、前の曲線当て嵌めからのスプラインと重複する。重複曲線当て嵌めは、曲線当て嵌めの間の境界における形状整合性を保証する。高度曲線当て嵌め技術は、指定の曲線当て嵌めＺ許容範囲に基づいて最適な結び目ベクトルを再帰的に判断する。指定の高度曲線当て嵌め許容範囲は、高度が急激に変化する時により多くの結び目が存在し、高度が緩慢に変化する時により少ない結び目が存在するように結び目ベクトル間隔を判断するのに用いられる。高度Ｂ−スプラインにおける高度点は、リンクチェーンの弧長によってパラメータ化されているので、高度Ｂ−スプラインは、２ＤのＢ−スプラインに適合する結び目ベクトルパラメータ空間を有し、それによってブロック１５１０において、これらのＢ−スプラインを３ＤのＢ−スプラインへと融合することが可能になる。
【０１０１】
ブロック１５１０では、３ＤのＢ−スプラインルーチン１５００は、方法９００からの２ＤのＢ−スプラインと、ブロック１５０８からの高度Ｂ−スプラインとを融合し、３ＤのＢ−スプラインを得る。３ＤのＢ−スプライン表現は、高度Ｂ−スプラインのＺ成分を２ＤのＢ−スプラインルーチン９００によって作成された２ＤのＢ−スプラインに追加することによって作成される。２ＤのＢ−スプライン及び高度Ｂ−スプラインの両方に対するパラメータ空間は、同じＸＹリンク幾何学形状の弧長によってパラメータ化されているので、これらのＢ−スプラインは、これらの結び目ベクトルを融合することによって融合することができる。
【０１０２】
３ＤのＢ−スプラインルーチン１５００は、両方のＢ−スプラインの最大結び目値によって２ＤのＢ−スプライン及び高度Ｂ−スプラインの各々の結び目ベクトルをスケーリングする。次に、３ＤのＢ−スプラインルーチン１５００は、結び目挿入を用いて２ＤのＢ−スプラインの結び目を高度Ｂ−スプラインの中に挿入し、高度Ｂ−スプラインの元の結び目を２ＤのＢ−スプラインの中に挿入する。その結果、両方のＢ−スプラインが同じ結び目ベクトルを有し、同じパラメータ空間を共有する。
【０１０３】
３ＤのＢ−スプラインルーチン１５００は、以下に示すように、３ＤのＢ−スプラインの制御点のＺ値を高度Ｂ−スプラインのＺ値のものと等しく設定することにより、２ＤのＢ−スプラインから３ＤのＢ−スプラインを作成する。
【０１０４】
【数１１】
【０１０５】
ブロック１５１２では、３ＤのＢ−スプラインルーチン１５００は、３ＤのＢ−スプラインに勾配情報を符号化する。この符号化は、３ＤのＢ−スプライン内に結び目をタグ付けすることによって達成され、これらの結び目は、電子視野アプリケーション２０８のための線形勾配プロフィールを生成するのに用いることができる。高度が急激に変化する時により多数の勾配結び目が存在し、高度が緩慢に変化する時により少数の結び目が存在するように、符号化される結び目ベクトル間隔を判断する上で指定の標高及び勾配許容範囲が用いられる。更に、勾配変曲点が発生する場所により多くの勾配点が追加される。３ＤのＢ−スプラインルーチン１５００は、標高、勾配、及び勾配変化に基づいて、Ｄｏｕｇｌａｓ−Ｐｅｕｋｅｒ線近似解析を用いて符号化された勾配結び目の場所を識別する。この解析は、データ点が線近似の許容範囲に入ると終了する。３ＤのＢ−スプラインルーチン１５００は、高度分布に沿って各Ｄｏｕｇｌａｓ−Ｐｅｕｋｅｒポリライン点に「タグ付き」勾配結び目を挿入する。
【０１０６】
ブロック１５１４では、３ＤのＢ−スプラインルーチン１５００は、ブロック１５１２における結び目挿入を評価することによってサイズを最適化する。得られる結び目挿入は、Ｂ−スプラインの３Ｄ形状を表すのに必要なものよりも多くの結び目を生じる可能性があるから、３ＤのＢ−スプラインルーチン１５００は、勾配プロフィール及び曲率プロフィールを符号化するのに又はＢ−スプライン品質を維持するのに必要ではない結び目を削除する。
【０１０７】
上述の詳細説明が限定的ではなく例示的なものとして捉られること、及び全ての均等物を含む以下の特許請求の範囲が本発明の範囲を定めるように意図されることが理解されることを意図している。これらの特許請求の範囲は、その旨を明記しない限り、説明した順序又は要素に限定されると解釈すべきではない。従って、以下の特許請求の範囲及びその均等物の範囲及び精神に該当する全ての実施形態を本発明として特許請求する。
【符号の説明】
【０１０８】
１００ 地図援用ＡＤＡＳアーキテクチャ
１０６ 地理データベース
１１０ 車両内データバスインタフェース
１１４ 運転者支援アプリケーション
１１６ 地図及び測位エンジン（ＭＰＥ）
【特許請求の範囲】
【請求項１】
運転者支援アプリケーションのための幾何学形状を作成する方法であって、
道路網の一部分を表す複数のセグメントからリンクチェーンを作成する段階と、
前記リンクチェーンから２ＤのＢ−スプラインを作成する段階と、
前記リンクチェーン、前記２Ｄスプライン、及び高度データから３ＤのＢ−スプラインを作成する段階と、
前記２ＤのＢ−スプライン及び前記３ＤのＢ−スプラインを表すデータをデータベースに記憶する段階と、
を含み、
少なくとも１つの運転者支援アプリケーションが、前記記憶された２ＤのＢ−スプラインデータ及び前記３ＤのＢ−スプラインデータから生成される道路幾何学形状情報を用いる、
ことを特徴とする方法。
【請求項２】
リンクチェーンを作成する段階は、末端ノードに到達するまで両方の方向に該リンクチェーンを成長させる段階を含むことを特徴とする請求項１に記載の方法。
【請求項３】
リンクチェーンを作成する段階は、ノードを通る可能な経路を識別する段階、及び該ノードを通る該可能な経路の１つを選択する段階を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記ノードを通る前記可能な経路の１つを選択する段階は、該可能な経路の各々に対して経路重みを計算する段階を含み、
前記経路重みは、前記ノードを通じた方向変化の量とリンク間の車線数の差とに基づいている、
ことを特徴とする請求項３に記載の方法。
【請求項５】
２ＤのＢ−スプラインを作成する段階は、２ＤのＢ−スプラインをリンクチェーンに当て嵌める段階を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記２ＤのＢ−スプラインを前記リンクチェーンに当て嵌める段階は、該２ＤのＢ−スプラインに沿った曲率の変化を最小にする段階を含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記２ＤのＢ−スプラインを前記リンクチェーンに当て嵌める段階は、該２ＤのＢ−スプラインに沿った最小二乗誤差を最小にする段階を含むことを特徴とする請求項５に記載の方法。
【請求項８】
２ＤのＢ−スプラインを作成する段階は、パッチＢ−スプラインを用いて２ＤのＢ−スプライン端を整合化する段階を含むことを特徴とする請求項１に記載の方法。
【請求項９】
２ＤのＢ−スプラインを作成する段階は、交差点で２ＤのＢ−スプライン端を整合化する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１０】
２ＤのＢ−スプラインを作成する段階は、該２ＤのＢ−スプラインを分割して前記リンクチェーンにおける各セグメントに対応する２ＤのＢ−スプラインを形成する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１１】
２ＤのＢ−スプラインを作成する段階は、曲率情報を該２ＤのＢ−スプライン内に符号化する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１２】
前記高度データは、前記道路網上を走行する収集車両に設置されたＧＰＳ／ＩＭＵデバイスから得られることを特徴とする請求項１に記載の方法。
【請求項１３】
前記高度データは、既知の幾何学的２Ｄ道路中心線の地理データベース上に投影されることを特徴とする請求項１に記載の方法。
【請求項１４】
３ＤのＢ−スプラインを作成する段階は、前記高度データを調節して標高不整合性を補正する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１５】
前記高度データを調節する段階は、標高を垂直に補正する段階、及び各セグメントに対して単一の高度スプラインを選択する段階を含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
３ＤのＢ−スプラインを作成する段階は、前記リンクチェーンに対して高度スプラインを作成する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１７】
３ＤのＢ−スプラインを作成する段階は、前記２ＤのＢ−スプラインを前記高度スプラインと融合する段階を含むことを特徴とする請求項１６に記載の方法。
【請求項１８】
前記２ＤのＢ−スプラインを前記高度スプラインと融合する段階は、該高度スプラインのｚ成分を該２ＤのＢ−スプラインに追加する段階を含むことを特徴とする請求項１７に記載の方法。
【請求項１９】
前記２ＤのＢ−スプラインを前記高度スプラインと融合する段階は、該２ＤのＢ−スプライン及び該高度スプラインの結び目ベクトルを融合する段階を含むことを特徴とする請求項１７に記載の方法。
【請求項２０】
３ＤのＢ−スプラインを作成する段階は、勾配情報を該３ＤのＢ−スプライン内に符号化する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１】
運転者支援アプリケーションのための幾何学形状を作成する方法であって、
道路網の一部分を表す複数のセグメントからリンクチェーンを作成する段階と、
前記リンクチェーンから２ＤのＢ−スプラインを作成する段階と、
前記リンクチェーン、前記２Ｄスプライン、及び高度データから３ＤのＢ−スプラインを作成する段階と、
前記２ＤのＢ−スプライン及び前記３ＤのＢ−スプラインを表すデータをデータベースに記憶する段階と、
を含み、
少なくとも１つの運転者支援アプリケーションが、前記記憶された２ＤのＢ−スプラインデータ及び前記３ＤのＢ−スプラインデータから生成される道路幾何学形状情報を用いる、
ことを特徴とする方法。
【請求項２】
リンクチェーンを作成する段階は、末端ノードに到達するまで両方の方向に該リンクチェーンを成長させる段階を含むことを特徴とする請求項１に記載の方法。
【請求項３】
リンクチェーンを作成する段階は、ノードを通る可能な経路を識別する段階、及び該ノードを通る該可能な経路の１つを選択する段階を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記ノードを通る前記可能な経路の１つを選択する段階は、該可能な経路の各々に対して経路重みを計算する段階を含み、
前記経路重みは、前記ノードを通じた方向変化の量とリンク間の車線数の差とに基づいている、
ことを特徴とする請求項３に記載の方法。
【請求項５】
２ＤのＢ−スプラインを作成する段階は、２ＤのＢ−スプラインをリンクチェーンに当て嵌める段階を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記２ＤのＢ−スプラインを前記リンクチェーンに当て嵌める段階は、該２ＤのＢ−スプラインに沿った曲率の変化を最小にする段階を含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記２ＤのＢ−スプラインを前記リンクチェーンに当て嵌める段階は、該２ＤのＢ−スプラインに沿った最小二乗誤差を最小にする段階を含むことを特徴とする請求項５に記載の方法。
【請求項８】
２ＤのＢ−スプラインを作成する段階は、パッチＢ−スプラインを用いて２ＤのＢ−スプライン端を整合化する段階を含むことを特徴とする請求項１に記載の方法。
【請求項９】
２ＤのＢ−スプラインを作成する段階は、交差点で２ＤのＢ−スプライン端を整合化する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１０】
２ＤのＢ−スプラインを作成する段階は、該２ＤのＢ−スプラインを分割して前記リンクチェーンにおける各セグメントに対応する２ＤのＢ−スプラインを形成する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１１】
２ＤのＢ−スプラインを作成する段階は、曲率情報を該２ＤのＢ−スプライン内に符号化する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１２】
前記高度データは、前記道路網上を走行する収集車両に設置されたＧＰＳ／ＩＭＵデバイスから得られることを特徴とする請求項１に記載の方法。
【請求項１３】
前記高度データは、既知の幾何学的２Ｄ道路中心線の地理データベース上に投影されることを特徴とする請求項１に記載の方法。
【請求項１４】
３ＤのＢ−スプラインを作成する段階は、前記高度データを調節して標高不整合性を補正する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１５】
前記高度データを調節する段階は、標高を垂直に補正する段階、及び各セグメントに対して単一の高度スプラインを選択する段階を含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
３ＤのＢ−スプラインを作成する段階は、前記リンクチェーンに対して高度スプラインを作成する段階を含むことを特徴とする請求項１に記載の方法。
【請求項１７】
３ＤのＢ−スプラインを作成する段階は、前記２ＤのＢ−スプラインを前記高度スプラインと融合する段階を含むことを特徴とする請求項１６に記載の方法。
【請求項１８】
前記２ＤのＢ−スプラインを前記高度スプラインと融合する段階は、該高度スプラインのｚ成分を該２ＤのＢ−スプラインに追加する段階を含むことを特徴とする請求項１７に記載の方法。
【請求項１９】
前記２ＤのＢ−スプラインを前記高度スプラインと融合する段階は、該２ＤのＢ−スプライン及び該高度スプラインの結び目ベクトルを融合する段階を含むことを特徴とする請求項１７に記載の方法。
【請求項２０】
３ＤのＢ−スプラインを作成する段階は、勾配情報を該３ＤのＢ−スプライン内に符号化する段階を含むことを特徴とする請求項１に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１０−８６５４４（Ｐ２０１０−８６５４４Ａ）
【公開日】平成２２年４月１５日（２０１０．４．１５）
【国際特許分類】
【外国語出願】
【出願番号】特願２００９−２４４９０６（Ｐ２００９−２４４９０６）
【出願日】平成２１年１０月１日（２００９．１０．１）
【出願人】（５０８３５１１１８）ナヴテック ノース アメリカ リミテッド ライアビリティ カンパニー (20)
【Ｆターム（参考）】
【公開日】平成２２年４月１５日（２０１０．４．１５）
【国際特許分類】
【出願番号】特願２００９−２４４９０６（Ｐ２００９−２４４９０６）
【出願日】平成２１年１０月１日（２００９．１０．１）
【出願人】（５０８３５１１１８）ナヴテック ノース アメリカ リミテッド ライアビリティ カンパニー (20)
【Ｆターム（参考）】
[ Back to top ]