(57)【要約】【課題】最新運転者支援システム（ＡＤＡＳ）、特に、ＡＤＡＳアプリケーションに車両測位、曲率、勾配、及び車両方位情報を提供するのにベジエ曲線を用いる技術を提供する。【解決手段】最新運転者支援システム（ＡＤＡＳ）アプリケーションにデータを提供するために車両測位アプリケーション及び電子視野アプリケーションにおいてベジエ曲線を用いる方法及びシステムを開示する。ベジエ曲線は、Ｂ−スプラインから得られる。得られたベジエ曲線は、車両測位アプリケーションがポリライン表現を実時間で導出することを可能にするような方式で再分割される。車両測位アプリケーションは、ベジエ及びポリライン幾何学形状を用いて、ＡＤＡＳアプリケーションに車両位置近似を提供する。電子視野アプリケーションは、ベジエ曲線を用いてＡＤＡＳアプリケーションに曲率プロフィール、勾配プロフィール、及び車両方位プロフィールを提供する。【選択図】図１
2010086543.tif 000002
【特許請求の範囲】
【請求項１】
運転者支援アプリケーションによる使用に向けて車両位置の近似を生成する方法であって、
道路のポリライン表現上で車両位置に最も近い点を判断するためにマップ照合解析を実施する段階と、
前記ポリライン上で前記車両に前記最も近い点に対応するベジエ曲線を地理データベース内で識別する段階と、
前記車両位置の近似を得るために前記最も近い点を前記識別されたベジエ曲線上に投影する段階と、
前記車両位置の前記近似を少なくとも１つの運転者支援アプリケーションに提供する段階と、
を含むことを特徴とする方法。
【請求項２】
前記車両位置を取り囲む地理的区域内の道路網を表す道路セグメントに関連付けられたＢ−スプライン道路幾何学形状を取得する段階と、
前記Ｂ−スプライン道路幾何学形状をベジエ曲線に変換する段階と、
制御多角形基本弦から最も遠い距離に位置する前記ベジエ曲線上の点で該ベジエ曲線を分割する段階と、
前記分割されたベジエ曲線を前記地理データベースに記憶する段階と、
を更に含むことを特徴とする請求項１に記載の方法。
【請求項３】
運転者支援アプリケーションによる使用に向けて曲率プロフィールを生成する方法であって、
少なくとも１つの道路セグメントを表すＢ−スプライン道路幾何学形状から曲率情報を取得する段階と、
前記Ｂ−スプライン道路幾何学形状をベジエ曲線に変換する段階と、
前記ベジエ曲線に対する弧長を計算する段階と、
少なくとも１つの運転者支援アプリケーションによる使用に向けて、前記曲率情報及び前記計算された弧長を用いて曲率プロフィールを表示する段階と、
を含むことを特徴とする方法。
【請求項４】
曲率情報を取得する段階は、
曲率及び弧長を取得するために前記Ｂ−スプライン道路幾何学形状をサンプリングする段階と、
前記得られた曲率及び弧長をグラフにする段階と、
前記グラフにされた曲率及び弧長のポリライン近似を計算する段階と、
前記ポリライン近似の頂点に対応する結び目を前記Ｂ−スプライン道路幾何学形状に挿入する段階と、
を含む、
ことを特徴とする請求項３に記載の方法。
【請求項５】
前記挿入された結び目を結び目曲率フラグに関連付ける段階を更に含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記Ｂ−スプライン道路幾何学形状をベジエ曲線に変換する段階は、前記結び目曲率フラグを制御点曲率フラグに変換する段階を含むことを特徴とする請求項５に記載の方法。
【請求項７】
運転者支援アプリケーションによって用いることができる勾配プロフィールを生成する方法であって、
少なくとも１つの道路セグメントを表すＢ−スプライン道路幾何学形状から勾配情報を取得する段階と、
前記Ｂ−スプライン道路幾何学形状をベジエ曲線に変換する段階と、
前記ベジエ曲線に対する弧長を計算する段階と、
少なくとも１つの運転者支援アプリケーションによる使用に向けて、前記勾配情報及び前記計算された弧長を用いて勾配プロフィールを表示する段階と、
を含むことを特徴とする方法。
【請求項８】
勾配情報を取得する段階は、
勾配及び弧長を取得するために前記Ｂ−スプライン道路幾何学形状をサンプリングする段階と、
前記得られた勾配及び弧長をグラフにする段階と、
前記グラフにされた勾配及び弧長のポリライン近似を計算する段階と、
前記ポリライン近似の頂点に対応する結び目を前記Ｂ−スプライン道路幾何学形状に挿入する段階と、
を含む、
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記挿入された結び目を結び目勾配フラグに関連付ける段階を更に含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記Ｂ−スプライン道路幾何学形状をベジエ曲線に変換する段階は、前記結び目勾配フラグを制御点勾配フラグに変換する段階を含むことを特徴とする請求項９に記載の方法。
【請求項１１】
運転者支援アプリケーションによる使用に向けて放物線上の３つの点によって定められる放物車両方位プロフィール曲線を生成する方法であって、
ベジエ曲線の２つの端点を特定する段階と、
前記２つの端点からの車両方位角を計算する段階と、
前記ベジエ曲線上で車両方位角点をサンプリングし、最小二乗当て嵌め技術を用いて放物車両方位プロフィール曲線を該サンプリングされた車両方位角点に当て嵌めることにより、第３の点を判断する段階と、
前記ベジエ曲線の前記２つの端点及び前記第３の点を少なくとも１つの運転者支援アプリケーションに提供する段階と、
を含むことを特徴とする方法。
【請求項１２】
前記３つの点は、車両方位角及び運転距離の関数として定められることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記車両方位角は、度の単位で計算され、北から時計回り方向に測定されることを特徴とする請求項１２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への参照
本出願は、２００８年１０月１日出願の「最新運転者支援システムアプリケーションのためのベジエ曲線」という名称の米国特許仮出願第６１／１０１、７５８号の恩典を請求する。米国特許仮出願出願番号第６１／１０１、７５８号の全開示内容は、本明細書に引用によって組み込まれている。
本特許出願は、本明細書に引用によって組み込まれている「最新運転者支援システムのための幾何学形状の作成」という名称の同じ日付に出願された現在特許出願中の特許出願出願番号第＿＿＿＿号、代理人整理番号Ｎ０２９６ＵＳに関連している。
本発明は、一般的に、最新運転者支援システム（ＡＤＡＳ）に関し、より具体的には、ＡＤＡＳアプリケーションに車両測位、曲率、勾配、及び車両方位情報を提供するのにベジエ曲線を用いることに関する。
【背景技術】
【０００２】
ＡＤＡＳは、運転の快適さ、効率、安全性、及び全体的な満足感を改善するために開発されたものである。これらの最新運転者支援システムの例は、適応ヘッドライト照準、適応走行制御、車線逸脱警告及び制御、カーブ警告、速度制限通知、ハザード警告、予測走行制御、適応変速制御、並びにその他を含む。これらの最新運転者支援システムの一部は、車両の現在の状態及び車両の前方にある車道の現在の状態を判断するために車両内の様々なセンサ機構を用いる。これらのセンサ機構は、デジタルビデオカメラ及びＬＩＤＡＲのようなレーダー、赤外線、超音波、及び視覚指向性センサを含むことができる。
【０００３】
一部の最新運転者支援システムはまた、デジタル地図データを用いる。これらのシステムは、時によっては地図援用ＡＤＡＳと呼ばれる。デジタル地図データは、最新運転者支援システムにおいて道路網、道路幾何学形状、道路状態、並びに車両の周囲の道路及び地形に関連する他の項目に関する情報を提供するのに用いることができる。一部のセンサとは異なり、デジタル地図データは、霧、雨、又は雪のような環境の状態による影響を受けない。更に、デジタル地図データは、曲率、断勾配、横傾斜、標識によって示されていない速度制限、及び車線制限などのようなセンサによっては確実には供給することができない有利な情報を提供することができる。更に、デジタル地図データは、車両の前方、曲がり角付近、坂の向こう側、又は障害物の向こう側の道路を判断するために、センサの範囲を十分に超えるか又は運転者の視界さえ超える予測機能を提供することができる。従って、デジタル地図データは、一部の最新運転者支援システムに対して有用な追加物とすることができる。
【０００４】
地図援用最新運転者支援システムは、一般的に、車両内のナビゲーションシステムに付随する地理データベースからのデータを用いる。ナビゲーションシステムのデータベースは、道路及び交差点の場所（高度を含む地理座標）、道路名、道路に沿った速度制限、交差点での右左折制限、道路に沿った住所又は住所範囲、各道路における車線数、車線幅、車線境界線、道路の機能部類、及び中央分離帯の場所などのような地域内の道路網を表すデータを収容する。ナビゲーションシステムのデータベースはまた、水域、公園、行政区域（地方自治体、州、及び国の境界を含む）、及び会社、病院、及び警察署などのような肝心な点の場所のような他の地理的特徴に関する情報を収容することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許仮出願第６１／１０１、７５８号
【特許文献２】米国特許公開第２００６／０１００７８０号
【特許文献３】米国特許第６、４０５、１２８号
【特許文献４】米国特許第７、０８４、８８２号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ナビゲーションシステムのデータベースは、最新運転者支援システムが必要とするものよりも非常に多くのデータを有する。更に、ナビゲーションに向けて設計された地理データベースは、全てのデータを有していない場合があり、及び／又は最新運転者支援システムによって必要とされる精度レベルでデータを有していない場合がある。その結果、特に最新運転者支援システムに向けた地理データベースの設計には何らかの労力が費やされてきた。例えば、米国特許公開第２００６／０１００７８０号は、自動車システム内のセンサデバイスに向けて設計されたデータ記憶フォーマットを有する地理データベースを説明している。しかし、特に最新運転者支援システムに向けて設計された地理データベースには、改善の余地がある。
【課題を解決するための手段】
【０００７】
ＡＤＡＳアプリケーションにデータを提供するために車両測位アプリケーション及び電子視野アプリケーションにおいてベジエ曲線を用いる方法及びシステムを開示する。ベジエ曲線は、Ｂ−スプラインから得られる。得られたベジエ曲線は、車両測位アプリケーションがポリライン表現を実時間で導出することを可能にするような方式で再分割される。車両測位アプリケーションは、ベジエ及びポリライン幾何学形状を用いて、ＡＤＡＳアプリケーションに車両位置近似を提供する。電子視野アプリケーションは、ベジエ曲線を用いて、ＡＤＡＳアプリケーションに曲率プロフィール、勾配プロフィール、及び車両方位プロフィールを提供する。
【０００８】
これら並びに他の態様及び利点は、適切な場合は添付図面を参照して以下の詳細説明を読解することにより当業者には明らかになるであろう。更に、この要約は例に過ぎず、特許請求する本発明の範囲を限定する意図はないことを理解されたい。
同様の参照番号が様々な図における同様の要素を指す添付図面の図を併用して現時点で好ましい実施形態を下記に説明する。
【図面の簡単な説明】
【０００９】
【図１】実施例による地図援用ＡＤＡＳアーキテクチャのブロック図である。
【図２】実施例による図１に描かれたプロセッサに利用可能なソフトウエアアプリケーションのブロック図である。
【図３】実施例による図１に描かれた地理データベースからの道路セグメントデータ記録のブロック図である。
【図４】実施例による図３に描かれた道路セグメントデータ記録におけるデータ属性のブロック図である。
【図５】実施例によりＡＤＡＳのための幾何学形状を作成するための流れ図である。
【図６】例示的なベジエ曲線の図である。
【図７】ベジエ曲線から生成された例示的なポリラインの図である。
【図８】実施例による二重道路幾何学形状表現を用いた車両測位のための流れ図である。
【図９】実施例により曲率プロフィール及び勾配プロフィールを生成するための流れ図である。
【図１０】実施例による道路のセグメントに対応するＢ−スプライン及び関連の車両方位プロフィールの図である。
【発明を実施するための形態】
【００１０】
ＡＤＡＳアーキテクチャ
図１は、地図援用ＡＤＡＳアーキテクチャ１００のブロック図を示している。この例では、地図援用ＡＤＡＳアーキテクチャ１００は、運転者支援アプリケーション１１４、並びに地図及び測位エンジン（ＭＰＥ）１１６を含む。図１では、ＭＰＥ１１６を独立型モジュールとして示しているが、ＭＰＥ１１６は、複数のパッケージに分散させることができ、及び／又はセンサパッケージのような他のデバイスパッケージ内に統合することができることを理解されたい。ＭＰＥ１１６は、プロセッサ１０２、測位システム１０４、地理データベース１０６、通信システム１０８、及び車両内データバスインタフェース１１０を含む。ＭＰＥ１１６はまた、メモリ及び電源のような他のハードウエア、ソフトウエア、及び／又はファームウエアを含むことができる。
【００１１】
プロセッサ１０２は、あらゆる種類のプロセッサ、コントローラ、又は他のコンピュータデバイスとすることができる。例えば、プロセッサ１０２は、デジタル信号プロセッサとすることができる。プロセッサ１０２は、測位システム１０４、地理データベース１０６、通信システム１０８、車両内データバスインタフェース１１０、及びその他の供給源からの入力を受信する。次に、プロセッサ１０２は、一部を図２を参照して説明するアプリケーションソフトウエアプログラム２００を用いてこれらの入力を処理する。
【００１２】
次に、プロセッサ１０２は、車両内データバスインタフェース１１０及びデータバス１１２を通じて運転者支援アプリケーション１１４に出力を供給する。好ましくは、車両内データバスインタフェース１１０及びデータバス１１２は、自動車用途に向けて設計されたコントローラエリアネットワーク（ＣＡＮ）インタフェース及びＣＡＮバスである。運転者支援アプリケーション１１４は、適応ヘッドライト照準、適応走行制御、障害物検出、障害物回避、衝突回避、適応変速制御、及びその他を含むことができる。
【００１３】
測位システム１０４は、ＧＰＳ型技術、推測航法型システム、又はこれらの組合せ、又は当業技術で公知の他のシステムを利用することができる。また、測位システム１０４は、走行距離、速度、方向、及び姿勢などを測定する適切な感知デバイスを含むことができる。例えば、測位システム１０４は、ＧＰＳシステム及びジャイロスコープを含むことができる。測位システム１０４は、プロセッサ１０２に出力信号を供給する。プロセッサ１０２上で作動するアプリケーションソフトウエアプログラム２００の一部は、ＭＰＥ１１６の場所、方向、及び姿勢などを判断するのに測位システム１０４からの出力信号を用いる。
【００１４】
地理データベース１０６は、ＡＤＡＳアプリケーションに向けて設計される。ナビゲーションシステムの地理データベースと同様に、地理データベース１０６は、地理的領域内の道路及び交差点に関するデータを含む。例えば、地理データベース１０６は、各道路セグメント（リンクとも呼ぶ）に対して少なくとも１つのデータベース記録（「エンティティ」又は「エントリ」とも呼ぶ）を含む。道路セグメントがＢ−スプライン曲線又はベジエ曲線で表される時には、道路セグメントデータ記録は、制御点の地理座標（例えば、緯度、経度、及び高度）を与えるデータを含む。道路セグメントの端点（ノードとも呼ぶ）は、最初及び最後の制御点に対応する。更に、道路セグメントデータ記録はまた、Ｂ−スプライン幾何学に関する結び目ベクトルを収容することもできる。
道路セグメントが形状点幾何学形状として表される時には、道路セグメントデータ記録は、表される道路セグメントの端点の地理座標（例えば、緯度、経度、及び高度）を与えるデータを含む。曲線セグメントでは、道路セグメントデータ記録は、ポリラインを特徴付けるのに用いられる形状点の地理座標（例えば、緯度、経度、及び高度）を与えるデータも含む。
【００１５】
道路セグメントデータ記録に対して、図３を参照してより詳しく説明する。
地理データベース１０６は、一般的にナビゲーションシステムの地理データベースに含まれるデータよりも高い品質（すなわち、正確な）データを含むことができる。例えば、道路幾何学形状に関して、地理データベース１０６内のデータは、経度、緯度、及び／又は高度に関してより正確なものとすることができる。また、地理データベース１０６では、トンネルの開始場所及び終了場所をより正確に指定することができる。更に、地理データベース１０６内のデータは、曲率のような導出情報に関してより正確なものとすることができる。
【００１６】
また、地理データベース１０６は、一般的に、ナビゲーションシステムの地理データベースに含まれるデータよりも多くの種類のデータ（例えば、多くの種類の属性）を含むことができる。例えば、地理データベース１０６は、標識及び横断歩道のような道路物体に関するデータを道路セグメントに沿ったこれらの位置、標識物体種類、及び標識テキストを含めて含むことができる。地理データベース１０６内に見られるデータ属性の一部に対して、図４を参照して説明する。
【００１７】
図２は、プロセッサ１０２に対して利用可能なソフトウエアアプリケーション２００の一部を示しているブロック図である。図２に示しているソフトウエアアプリケーション２００は、地図アクセスアプリケーション２０２、地図更新アプリケーション２０４、車両測位アプリケーション２０６、電子視野アプリケーション２０８、及びインタフェースアプリケーション２１０を含む。これは、プロセッサ１０２に対して利用可能な全てのソフトウエアアプリケーション２００の網羅的なリストではないので、図２は、始動ルーチン、及び自己試験診断などを含むことができる他のアプリケーション２１２も示している。
【００１８】
地図アクセスアプリケーション２０２は、物理的記憶媒体上に記憶された地理データベース１０６へのデータアクセスを提供する。地図アクセスアプリケーション２０２は、プロセッサ１０２からデータ要求を受信し、この要求に応じるデータを物理的記憶媒体上で探し出す。好ましくは、地図アクセスアプリケーション２０２は、プロセッサ１０２及び／又はアプリケーション２００による使用に向けて、アプリケーションプログラミングインタフェース（ＡＰＩ）を提供する。
【００１９】
地図更新アプリケーション２０４は、地理データベース１０６に対する更新を容易にする。通信システム１０８は、既存のデータベースに付加的な受信範囲を追加するか、又は既存のパーセルを置換するかのいずれかを行う１つ又はそれよりも多くのパーセルを受信する。パーセルは、物理的記憶媒体上の地理データベース１０６内に地理データを記憶するための記憶単位である。新しいパーセルに対しては、地図更新アプリケーション２０４は、物理的記憶媒体上にこのパーセルを記憶する。既存のパーセルに対しては、地図更新アプリケーション２０４は、物理的記憶媒体上の古いパーセルを新しいパーセルで置換する。
車両測位アプリケーション２０６は、地理データベース１０６内に含まれるデータによって表される道路網に対する車両の位置を判断する。車両測位アプリケーション２０６は、測位システム１０４からの出力を用い、時によってマップ照合アルゴリズムと呼ぶ車両測位アルゴリズムを用いて、この出力を地理データベース１０６内のデータと照合する。
【００２０】
電子視野アプリケーション２０８は、電子的視野を判断する。電子的視野は、電子視野アプリケーション２０８によって判断される範囲の現在の車両位置から前方の道路及び交差点の集合である。この道路及び交差点の集合は、車両が現在の車両位置から辿ることができる潜在的な経路である。電子視野アプリケーション２０８は、１つ又はそれよりも多くのコスト関数を用いて範囲を判断する。コスト関数は、運転者支援アプリケーション１１４の要求に基づいて、車両速度、走行時間、及び運転距離のような様々な要因を考慮に入れることができる。例示的な電子視野アプリケーションは、本出願と同じ出願人に譲渡され、本明細書においてその全内容が引用により組み込まれている米国特許第６、４０５、１２８号に説明されている。
【００２１】
インタフェースアプリケーション２１０は、インタフェース１１０及びバス１１２を通じたＭＰＥ１１６と運転者支援アプリケーション１１４の間の通信を制御する。好ましくは、インタフェースアプリケーション２１０は、車両内の様々な電子デバイス間で通信を行うためのシリアル通信プロトコルであるＣＡＮプロトコルに基づいている。メッセージ及びデータを車両内の１つの電子デバイスから別のものへと送信することができるように、ＣＡＮプロトコルに従って車両内の様々な電子デバイスを単一のシリアルバス（例えば、バス１１２）に結合することができる。ＣＡＮプロトコルは、ＣＡＮフレームが共通ＣＡＮバス上に置かれるメッセージベースのプロトコルである。ＣＡＮバスは、単一のワイヤ又は差動的に駆動されるワイヤ対とすることができる。
【００２２】
図３は、地理データベース１０６からの道路セグメントデータ記録３００のブロック図である。道路セグメントデータ記録３００は、道路の一部分を表すために用いられるデータを含む。これらのデータは、セグメントの端点の緯度、経度、及び高度の座標位置を示すノードデータ３０２、３０４を含む。
また、データは、直線又は曲線セグメントの形状を表すために用いることができる制御点の緯度、経度、及び高度の座標位置を示す制御点データ３０６、３０８を含む。図３には２つの制御点に関するデータを示しているが、セグメントは、１つよりも多くの曲線を含むことができ、制御点数は、セグメント内の曲線の数及び形状に依存するものとすることができることを理解されたい。例えば、各３次ベジエ曲線は、４つの制御点によって表されるが、前のベジエ曲線の最後の制御点は、次のベジエ曲線の最初の制御点と同じである。道路セグメントデータ記録３００は、ベジエ曲線の数を３倍し、１を足した数に等しい数の制御点に関するデータを記憶する。
【００２３】
更に、データは、セグメントに関する属性３１０を含む。セグメントの属性３１０の一部を図４に示す。同様に道路セグメントデータ記録３００は、形状点データのような追加データを含むことができる。
図４は、道路セグメントデータ記録３００におけるデータ属性３１０の一部のブロック図である。図４に示しているデータ属性３１０は、セグメント識別子（ＩＤ）４０２、制御点４０４、走行方向４０６、速度カテゴリ４０８、車線カテゴリ４１０、道路種類４１２、セグメント特性４１４、及び通行特性４１６を含む。これは、道路セグメントデータ記録における全てのデータ属性の網羅的なリストではないので、図４は、他の属性４１８も示している。例えば、セグメントデータ属性４００は、セグメントの端点３０２、３０４に対応するノードＩＤの形態のノードデータ記録への参照子を含むことができる。
セグメントＩＤ４０２は、地理データベース１０６内のデータ記録を識別する。
【００２４】
制御点属性４０４は、図９を参照して説明するように、曲率及び勾配プロフィールの作成を助ける制御点に関する追加情報を提供するビットフラグを収容する。例えば、制御点属性４０４は、制御点毎にバイトサイズのフラグを含むことができる。フラグ内のビットのうちの１つは、曲率に割り当てられ、一方、ビットのうちの別のものは、勾配に割り当てられる。曲率ビットフラグが１に設定された場合には、制御点は、曲率プロフィールの一部としてマーク付けされる。同様に勾配ビットフラグが１に設定された場合には、制御点は、勾配プロフィールの一部としてマーク付けされる。
【００２５】
走行方向属性４０６は、セグメントにおいて許可される車の流れの方向を表している。例えば、セグメントは、道路網のうちで走行が双方向に許された部分を表すことができる。代替的に、セグメントは、道路網のうちで一方向の走行だけを可能にする部分を表すことができる。走行方向属性４０６は、セグメントが双方向走行又は単方向走行のいずれを可能にするのかを識別し、単方向の場合には、走行方向属性４０６は、許可された走行方向を更に識別する。
【００２６】
速度カテゴリ属性４０８は、掲示又は示唆された速度制限に基づく道路の一般的な速度傾向を表している。速度カテゴリ属性４０８は、速度範囲に関連するデータを含む。例えば、速度カテゴリ属性４０８は、８０ｍｐｈを超える速度に対して整数１、６５ｍｐｈ〜８０ｍｐｈの範囲の速度に対して整数２、５５ｍｐｈ〜６４ｍｐｈの範囲の速度に対して整数３、及び速度範囲が０ｍｐｈを含むまで以降同様に続くデータ表現を含むことができる。
【００２７】
車線カテゴリ属性４１０は、セグメントにおける１つの走行方向の主な車線数を表している。好ましくは、車線カテゴリ属性４１０は、右左折車線を含まない。車線数が各方向において異なる場合には、車線カテゴリ属性４１０は、大きい方の数を表すことができる。
道路種類属性４１２は、道路の種類及び／又はセグメントが表す機能部類を表している。例えば、道路種類属性４１２は、州間高速道路、通行制御高速道路、歩行者通路等に関連付けられたデータを含むことができる。
【００２８】
セグメント特性属性４１４は、様々なセグメント特性を説明するビットフラグを含む。例えば、セグメント特性属性４１４は、セグメントが舗装されているか、ランプであるか、橋であるか、トンネルであるか、及び環状交差点であるかなどを識別することができる。
アクセス特性属性４１６は、セグメントにおいて許可される交通の種類を定めるビットフラグを含む。例えば、アクセス特性属性４１６は、セグメントにおいて自動車、バス、トラック、タクシー、緊急車両、及び歩行者等が許可されているか否かを識別することができる。
【００２９】
ＭＰＥのための幾何学形状の作成
図５は、ＭＰＥ１１６のための幾何学形状を作成する方法５００の流れ図である。ブロック５０３では、方法５００は、並列処理を可能にするために地理データベース５０２をタイルへと再分割する。地理データベース５０２は、地理データベース１０６又は地理データベース１０６内のデータを含む異なるデータベースとすることができる。
これらのタイルは、各タイルがほぼ等量のノード及び形状点を含むように形成される。地図表面は、細かい（約２ｋｍ×２ｋｍ）セルを有する架空の２Ｄ矩形格子によって覆われる。次に、地理データベース５０２内のノード及び形状点を格子上にマップすることによってノード及び形状点の密度が計算される。タイルは、格子セルから組み立てられる。
各タイルがほぼ等しい数のノード及び形状点を有することを保証するために、格子全体は、水平及び垂直の両方の方向の格子線に沿って半分に再帰的に再分割され、２つの分割区分の各々が等しい数の幾何点を含むようにする。この処理は、タイルが、所定の閾値よりも少ない量のノード及び形状点を含むまで続く。各再分割の方向は、タイルのアスペクト比を最小にするように選択される。
【００３０】
ブロック５０４では、方法５００は、地理データベース５０２からのデータを用いて各タイル内でリンクチェーンを作成する。リンクチェーンは、各々が同じ道路種類属性４１２を有するセグメントのシーケンスである。リンクチェーンは、ソフトウエアルーチンを用いて作成される。ソフトウエアルーチンは、関連の機能部類を有する第１のセグメントを選択する。各ノードにおいて、ソフトウエアルーチンは、リンクチェーンに追加される次のセグメントを選択する。好ましくは、セグメントシーケンスは、可能な限り長く作られる。リンクチェーンは、セグメント境界を横切っての滑らかさを保証するＢ−スプライン当て嵌めを実施するのに用いられる。
【００３１】
ブロック５０６では、方法５００は、ブロック５０４で作成されたリンクチェーンを用いて２ＤのＢ−スプラインを作成する。ブロック５０８では、方法５００は、ブロック５０４で作成されたリンクチェーン、ブロック５０６で作成された２ＤのＢ−スプライン、及び高度データ５０７を用いて３ＤのＢ−スプラインを作成する。スプラインは、曲線区間を表し、区間の境界において指定の条件を満たす区分的多項式関数で形成されるあらゆる複合曲線を指す。従って、Ｂ−スプラインを含む多くの種類のスプライン曲線が存在する。Ｂ−スプラインは、制御点及び結び目を有する。結び目は、多項式スプライン曲線の個々の多項式曲線セグメントが互いに接合する点である。セグメントは、完全な曲線の滑らかさを生じるように接合される。結び目ベクトルは、スプライン曲線に沿ってセグメントが開始及び終了する点を説明する非減少浮動小数点数の序列リストである。スプラインは、当業技術で公知である。
【００３２】
スプラインを用いると、道路のカーブしている部分を含む地図特徴は、望ましい精度で地理特徴の形状に適合する曲線を生成するように判断された係数を有する多項式によって表される。従って、スプラインは、多項式の係数を指定することにより、基本的道路幾何学形状を説明するための手段である。米国特許第７、０８４、８８２号に説明されているように、スプラインは、ナビゲーションシステムのデータベースにおいて道路セグメントの形状を表すのに用いられている。米国特許第７、０８４、８８２号は、本出願と同じ出願人に譲渡されており、本明細書に引用によって組み込まれている。
リンクチェーンに対して当て嵌めが行われ、２ＤのＢ−スプラインが作成される。不規則性及びアラインメント問題を補正するために、２ＤのＢ−スプラインは操作される。記憶要件を最小にするために、曲率を符号化するか又は位置、曲率、勾配、及び／又は車両方位を保持するのに必要のない結び目は削除される。
【００３３】
最適化された２ＤのＢ−スプライン及び高度データ５０７が用いられ、３Ｄのスプラインが作成される。好ましくは、高度データ５０７は、道路セグメントによって表される道路上を車両が走行する時に収集されるＧＰＳ／ＩＭＵ記録から得られるが、高度データ５０７は、他の供給源及び／又はセンサから得ることができる。ＧＰＳの高度の不正確性に対処するために、高度データ５０７は、交差ノードにおいて線形に補正される。補正高度データを用いてリンクチェーンに対して当て嵌めが行われ、高度Ｂ−スプラインが作成される。
２ＤのＢ−スプラインと高度Ｂ−スプラインとは融合され、３ＤのＢ−スプラインが得られる。２ＤのＢ−スプラインと同様に、記憶要件を最小にするために、曲率及び勾配を符号化するか又は位置、曲率、勾配、及び／又は車両方位を保持するのに必要のない結び目は、３ＤのＢ−スプラインから削除される。
【００３４】
ブロック５１０では、２ＤのＢ−スプライン及び３ＤのＢ−スプラインをベジエ曲線に変換することができる。セグメントが高度データを持たない場合には、２ＤのＢ−スプラインは、ベジエ曲線に変換される。しかし、セグメントが高度データを確実に有する場合には、２ＤのＢ−スプラインは、ブロック５０８で３ＤのＢ−スプラインを作成することだけに用いることができる。
３次ベジエ曲線は、２つの端点及び曲線に対する接線に沿って位置決めされたこれらの端点における２つの追加制御点によって定められる。３次ベジエ曲線式は、ベクトル形式で次式のように書くことができる。
【００３５】
【数１】
2010086543.tif 000003
【００３６】
ここで、Ｐ0、Ｐ1、Ｐ2、及びＰ3は制御点であり、ｔはパラメータである。ベジエ曲線は、公知の方法を用いてＢ−スプライン曲線から導出することができる。
【００３７】
スプライン幾何学は、道路セグメント幾何学形状を表す上では有利であるが、ＭＰＥ１１６におけるＢ−スプラインの使用は、車両測位及び電子視野アプリケーション２０６、２０８における計算要件を増大させる。解析的なＢ−スプライン幾何学は、車両測位アプリケーション２０６によるポリライン表現及び電子視野アプリケーション２０８による電子視野の実時間導出を容易にするためにベジエ表現に変換される。
【００３８】
ブロック５１２では、車両測位アプリケーション２０６が、ポリライン表現を実時間で導出することができるように、ベジエ道路幾何学形状は分割される。方法５００は、道路幾何学形状が、弦から最も遠い点が弦線上に投影される時にこの点が弦の内側に収まるようなベジエ曲線を有することを仮定する。ベジエ道路幾何学形状は、図６に示しているように、ベジエ曲線から、この曲線の端点３０２、３０４を結ぶ線（すなわち、制御多角形の基本弦：
【００３９】
【数２】
2010086543.tif 000004
【００４０】
）までの最も遠い距離（又は複数の距離）にある１つの点６００（又は場合によっては１つよりも多くの点）を識別した後に分割される。図６では、最も遠い距離が、一般的に、曲線の中心にはないことも分る。
【００４１】
最適な再分割点６００は、ベジエ曲線上で制御多角形の基本弦から最も遠い点である。点６００の位置は、点６００における２Ｄベジエ曲線に対する接線Ｂ（ｔ）が弦に対して平行であるという条件から解析的に得られる。
【００４２】
【数３】
2010086543.tif 000005
【００４３】
上記表現は、パラメータｔに関する２次方程式へと簡略化される。一般的なベジエ曲線では、この２次方程式は、パラメータｔが定められる間隔［０〜１］内に実根を有することができない。しかし、穏やかな挙動を示すベジエ曲線では、２次方程式は［０〜１］間隔内に１つ又は２つの実根を有することになる。２次方程式が２つの実根を有する場合には、２つの再分割点が２つの点でベジエ曲線を分割するように用いられる。点６００が得られた状態で、ベジエ曲線は、デ・カステリョの再分割アルゴリズムを用いて２つのベジエ曲線に分割される。得られるベジエ曲線は、地理データベース１０６に記憶される。
ブロック５１４では、車両測位アプリケーション２０６は、ポリライン表現を実時間で導出する。ポリライン表現の例７００を図７に示す。車両測位アプリケーション２０６は、ベジエ曲線の端点７０２を結び、その一方で内部制御点７０４を無視することによってポリライン表現７００を導出する。
【００４４】
車両位置の判断するためのベジエ道路幾何学形状の使用
図８は、二重道路幾何学形状表現を用いた車両測位の方法８００のための流れ図を示している。二重道路幾何学形状表現は、ブロック５１２で得られたベジエ幾何学形状及びブロック５１４で得られたポリライン幾何学形状を含む。車両測位アプリケーション２０６は、ＭＰＥ１１６の操作中に方法８００を実施する。特に、車両測位アプリケーション２０６は、ブロック５１４においてポリライン幾何学形状を特定した後に方法８００を実施する。
【００４５】
ブロック８０２では、車両測位アプリケーション２０６は、ブロック５１４で判断されたポリライン表現上で車両に最も近い点を判断するために、マップ照合解析を実施する。マップ照合解析は、従来の車両測位アルゴリズムを用いて実施することができる。
ブロック８０４では、車両測位アプリケーション２０６は、ブロック８０２で見つかったポリライン上の点からの適切なベジエ曲線を特定する。車両測位アプリケーション２０６は、オンザフライでルックアップテーブルを計算し、ベジエ曲線を計算されたポリラインと関連付ける。対応するベジエ曲線を特定するのに、ポリラインに沿った長さがルックアップテーブル内に用いられる。
【００４６】
ブロック８０６では、車両測位アプリケーション２０６は、ブロック８０２で識別されたマップ照合点をブロック８０４で識別されたベジエ曲線上に投影する。車両測位アプリケーション２０６は、ニュートン法と二分法との組合せを用いて３次方程式を数値的に解くことによってベジエ曲線上での車両位置の近似を得る。
車両測位アプリケーション２０６は、ベジエ曲線上での車両位置を近似するので、この処理は、正確な車両位置を識別しようと試みる処理から簡素化されている。ＭＰＥ１１６は、例えば、ナビゲーションシステムよりも低いコンピュータ機能しか持たない可能性が高いので、ＭＰＥ１１６に対してこの簡素化は有利である。車両測位アプリケーション２０６は、インタフェースアプリケーション２１０、車両内データバスインタフェース１１０、及びデータバス１１２を通じて、運転者支援アプリケーション１１４の１つ又はそれよりも多くに車両位置の近似を提供する。
【００４７】
曲率及び勾配プロフィールを導出するためのベジエ道路幾何学形状の使用
図９は、曲率プロフィール及び勾配プロフィールを生成する方法９００の流れ図である。得られるセグメントにおける曲率プロフィール及び勾配プロフィールは、区分的線形フォーマットを有することができる。ブロック９０２〜ブロック９０４は、地理データベース１０６をロードする前に発生する前処理段階を示している。これらの段階の結果、データは、電子視野アプリケーション２０８による使用に向けて地理データベース１０６に記憶される。ブロック９０６〜ブロック９０８は、ＭＰＥ１１６が作動している時に発生する処理を示している。
【００４８】
ブロック９０２では、方法９００は、Ｂ−スプラインから曲率及び勾配情報を得る。曲率情報は、Ｂ−スプラインに沿ってサンプルを取り、各サンプル点において２Ｄ（すなわち、水平）曲率及び弧長を計算することによって得ることができる。測定された曲率及び弧長はグラフにされる（例えば、曲率をｙ軸に沿って、弧長をｘ軸に沿って）。方法９００は、ポリライン近似が望ましい許容範囲に入るまで、プロットに対する再帰的な再分割を用いるＤｏｕｇｌａｓ−Ｐｅｕｃｋｅｒ線簡素化技術を適用する。これらのポリラインは、弧長及び曲率の座標（すなわち、（ｌ、ｋ））を有する。勾配情報は、同様の方法で得ることができる。
【００４９】
ブロック９０４では、方法９００は、区分的線形近似の頂点をベジエ制御点に符号化する。方法９００は、ポリラインの頂点に対応するＢ−スプライン上の点を識別する。方法９００は、識別された点において結び目をＢ−スプライン内に挿入する。挿入された結び目には、曲率結び目又は勾配結び目としてタグ／フラグ付けが行われる。追加結び目を挿入した後に、方法９００は、元のＢ−スプラインの２Ｄ／３Ｄ位置、形状、車両方位、勾配、及び曲率からの閾値許容範囲にＢ−スプラインを保つのに必要ではない元のタグなし結び目をＢ−スプラインからできるだけ多く削除する。次に、得られるＢ−スプラインは、ベジエ曲線へと変換される。更に、曲率結び目及び勾配結び目をマーク付けするＢ−スプライン結び目フラグは、ベジエ曲線制御点フラグ４０４へと変換される。
【００５０】
ブロック９０６では、電子視野プログラム２０８は、電子視野内のベジエ曲線に対する弧長を計算する。好ましくは、電子視野プログラム２０８は、弧長を推定するのにガウス求積を用いる。弧長を計算するために４つの内部点においてベジエ曲線導関数を評価することは、十分に良好な近似である。
ブロック９０８では、電子視野プログラム２０８は、ブロック９０２で得られてブロック９０４で符号化された曲率及びブロック９０６で計算された弧長を用いて曲率プロフィール（曲率対弧長）を表示する。同様に、電子視野プログラム２０８は、ブロック９０２で得られてブロック９０４で符号化された勾配及びブロック９０６で計算された弧長を用いて勾配プロフィール（勾配対弧長）を表示する。
【００５１】
電子視野アプリケーション２０８は、インタフェースアプリケーション２１０、車両内データバスインタフェース１１０、及びデータバス１１２を通じて、運転者支援アプリケーション１１４の１つ又はそれよりも多くに曲率プロフィール及び／又は勾配プロフィールを提供する。好ましくは、電子視野アプリケーション２０８は、プロフィールを１対の値（すなわち、弧長と曲率、又は弧長と勾配）、又は運転された長さにおいてプロフィールが連続的ではない場合は、２対の値として提供する。提供される対の数は、運転者支援アプリケーション１１４の要求に対して十分でなければならないが、データバス１１２上の通信を劣化される程に多過ぎてはならない。
【００５２】
車両方位プロフィールを導出するためのベジエ道路幾何学形状の使用
図１０は、道路セグメントに対応するＢ−スプライン１０００及び関連の車両方位プロフィールのプロット１００２を示している。プロット１００２における線１００４は、実際の車両方位を表しており、プロット１００２における点１００６は、下記に説明する区分的放物近似である。
車両方位は、車両が道路上を走行する時に多くの場合に変化する車両が向いている方向である。車両方位プロフィールのプロット１００２は、車両が道路上を走行する時に車両の方位が方位計の示度に対して如何に変化するかを示している。この例における方位計の示度は、北が０°（及び３６０°）、東が９０°、南が１８０°、及び西が２７０°にあることに基づいている。
【００５３】
一般的に、電子視野アプリケーション２０８は、各ベジエ曲線に対して３点の組として実時間で区分的放物車両方位プロフィールプロット１００２を表示する。これら３点は、２つの端点３０２、３０４における車両方位角、及び電子視野アプリケーション２０８が計算する中間車両方位角点１００６を含む。
中間車両方位角点１００６を計算するために、好ましくは、電子視野アプリケーション２０８は、ベジエ曲線上で車両方位角点をサンプリングし（例えば、４つの車両方位角点）、最小二乗解析を実施して、放物曲線をサンプリングされた車両方位角点に当て嵌める。中間車両方位角点１００６は、ベジエ曲線上でサンプリングされた４つの車両方位角点に対する最小二乗当て嵌めによって導出された、得られる最良の当て嵌め放物曲線からの中間点ｌ1＝ｌ0＋０．５＊（ｌ2−ｌ0）において計算される。これら３点を用いて、電子視野アプリケーション２０８は、運転された長さの関数として車両方位プロフィールを計算する。電子視野プログラム２０８は、インタフェースアプリケーション２１０、車両内データバスインタフェース１１０、及びデータバス１１２を通じて、運転者支援アプリケーション１１４の１つ又はそれよりも多くに車両方位プロフィールを提供する。
【００５４】
より具体的には、車両方位角ｈは、セグメントに沿った運転距離ｌの関数として表示される。車両方位は、道路に沿って平滑に変化する関数であるから、車両方位は、区分的線形近似ではなく、区分的放物プロフィールによって最も良好に表される。車両方位角は、度を単位として計算され、北から時計回りの方向に測定される。車両方位角値は、０°から３６０°の範囲で表示される。車両方位角は周期的な関数であるから、リンクが厳密に北を向く時に放物セグメント内での０°から３６０°への移行を回避するために、付加的な点が車両方位プロフィール内に挿入される。
【００５５】
放物線は３点で定められる。各放物セグメントは、ベジエ曲線の端における方位の値を内挿する。上述のように、ｈプロフィールの内部点を最も良好に近似する放物線を導出するのに、最小二乗当て嵌め技術が用いられる。この放物線上でパラメータ値ｔ＝０．５で評価される点は、ベジエ曲線に対して表示される第３の車両方位プロフィール点を成す。放物セグメントｈ＝ｈ（ｌ）の最小二乗当て嵌め判断の詳細を以下の通りに提供する。
【００５６】
ｈ0＝ｈ（ｌ0）をベジエ曲線の左端ｔ＝０における車両方位角値とし、ｈ2＝ｈ（ｌ2）をベジエ曲線の右端ｔ＝１における車両方位角値とする。車両方位角対運転距離を近似する放物線の方程式は、次式のように書くことができる。
【００５７】
【数４】
2010086543.tif 000006
ここで、ａ、ｂ、及びｃは、未知のスカラー係数である。係数ａ及びｃは、境界条件を用いて省くことができ、次式が得られる。
【００５８】
【数５】
2010086543.tif 000007
ここで、Δｈ＝ｈ2−ｈ0、Δｌ＝ｌ2−ｌ0である。
残りのスカラー係数ｂは、実際の車両方位プロフィール上でサンプリングされた値と上述の近似放物線との間の距離の二乗の総和を最小にすることによって導出される。
【００５９】
【数６】
2010086543.tif 000008
ここで、
【数７】
2010086543.tif 000009
は、サンプリングされた車両方位値である。上述の式をｂに関して微分し、導関数をゼロにすることにより、残りの係数ｂに対して次式が得られる。
【００６０】
【数８】
2010086543.tif 000010
ここで、ｌiは、車両方位値：
【数９】
2010086543.tif 000011
がサンプリングされたスプラインに沿った運転距離の値である。
λiがベジエ曲線の開始点からの距離である場合に、代入λ＝ｌ−ｌ0を導入すると、係数ｂに関するより簡単な式が得られる。
【００６１】
【数１０】
2010086543.tif 000012
【００６２】
残りの係数ｂが上述の式から求められた後に、放物近似のための残りの第３の点が、λ＝Δｌ／２において以下の通りに求められる。
【数１１】
2010086543.tif 000013
【００６３】
車両方位角は、接線ベクトルＶx、Ｖyのｘ及びｙ成分から以下の通り得ることができる。
【数１２】
2010086543.tif 000014
ここで、ａｔａｎ２（）は、標準のＣライブラリ関数である。接線ベクトル成分Ｖx、Ｖy、又はベジエ曲線の１次導関数は、いくつかの方法で値を求めることができる。例えば、ベジエ曲線の端における１次導関数は、以下の通り得ることができる。
【数１３】
2010086543.tif 000015
【００６４】
ここで、Ｐ0、Ｐ1、Ｐ2、及びＰ3は、ベジエ曲線の４つの制御点である。別の例として、内部点における１次導関数は、累乗基底形式での方程式を用いて値を求めることができ、係数は、他の目的における頻繁な使用に向けてキャッシュに入れられる。電子視野アプリケーション２０８は、広域車両方位プロフィールの放物セグメントを定める３つの点（ｌ．0、ｈ．0）、（ｌ．1、ｈ．1）、（ｌ．2、ｈ．2）を運転者支援アプリケーション１１４の１つ又はそれよりも多くに提供する。
【００６５】
上述の詳細説明が限定的ではなく例示的なものとして捉られること、及び全ての均等物を含む以下の特許請求の範囲が本発明の範囲を定めるように意図されることが理解されることを意図している。これらの特許請求の範囲は、その旨を明記しない限り、説明した順序又は要素に限定されると解釈すべきではない。従って、以下の特許請求の範囲及びその均等物の範囲及び精神に該当する全ての実施形態を本発明として特許請求する。
【符号の説明】
【００６６】
１００  地図援用ＡＤＡＳアーキテクチャ
１０６  地理データベース
１１０  車両内データバスインタフェース
１１４  運転者支援アプリケーション
１１６  地図及び測位エンジン（ＭＰＥ）
【図１】
2010086543.tif 000016
【図２】
2010086543.tif 000017
【図３】
2010086543.tif 000018
【図４】
2010086543.tif 000019
【図５】
2010086543.tif 000020
【図６】
2010086543.tif 000021
【図７】
2010086543.tif 000022
【図８】
2010086543.tif 000023
【図９】
2010086543.tif 000024
【図１０】
2010086543.tif 000025
【外国語明細書】
2010086543.tif 000026
2010086543.tif 000027
2010086543.tif 000028
2010086543.tif 000029
2010086543.tif 000030
2010086543.tif 000031
2010086543.tif 000032
2010086543.tif 000033
2010086543.tif 000034
2010086543.tif 000035
2010086543.tif 000036
2010086543.tif 000037
2010086543.tif 000038
2010086543.tif 000039
2010086543.tif 000040
2010086543.tif 000041
2010086543.tif 000042
2010086543.tif 000043
2010086543.tif 000044
2010086543.tif 000045
2010086543.tif 000046
2010086543.tif 000047
2010086543.tif 000048
2010086543.tif 000049
2010086543.tif 000050
2010086543.tif 000051
2010086543.tif 000052
2010086543.tif 000053
2010086543.tif 000054
2010086543.tif 000055
2010086543.tif 000056
2010086543.tif 000057
2010086543.tif 000058
2010086543.tif 000059
2010086543.tif 000060
2010086543.tif 000061
2010086543.tif 000062
2010086543.tif 000063