JP6595182B2 - マッピング、位置特定、及び姿勢補正のためのシステム及び方法 - Google Patents

Description

（関連出願の相互参照）
本出願は、２０１４年２月８日に出願された米国仮出願第６１／９３７５３３号に対する優先権を主張し、それは参照することにより本明細書に明示的に組み込まれる。

世界中で位置を定めようとする知的エージェント（例えば、車両、ロボット）にとって重要な能力は、その位置を認識することである。一般的に、エージェントは、ローカルセンサー情報及び世界の何らかのモデルのみを与えられて、その位置を決定する。典型的に、その独自のローカルセンサー情報は、その位置についての何らかの測定値を提供するが、この測定値は、しばしば不正確である。カメラを装着した知的車両は、空間中の所定出発点に対して、自分の位置を視覚的走行距離計測を用いて把握することができる。しかしながら、視覚的走行距離計測は、逸脱しがちな姿勢を提供し得る。信頼性の高い視覚的走行距離計測は、車両のより確かな位置推定を可能にする。

一態様によると、マッピング、位置特定、及び姿勢補正のためのコンピュータ実装方法は、移動経路に沿った車両の現在位置及び現在位置に対する移動経路に沿った現在観測可能な目印のセットを決定することを含む。現在観測可能な目印のセットは、撮像デバイスから得られる１つ以上の立体画像から抽出される。本方法は、調査目印データベースに問い合わせて、車両の現在位置に対する調査済み目印のサブセットを特定し、この調査目印データベースが以前に記憶された調査済み目印のセットを含むことと、現在観測可能な目印のセットと調査済みの目印のサブセットとの間における１つ以上の二次元変換推定を決定することとを含む。本方法は、現在観測可能な目印のセットと調査済みの目印のサブセットとの間の距離を最小化する１つ以上の二次元変換推定からの最良の変換推定を特定することと、最良の変換推定に基づいて車両の姿勢を補正することとを含む。

別の態様によると、マッピング、位置特定、及び姿勢補正のためのシステムは、プロセッサと、プロセッサが移動経路に沿った車両の現在位置及び現在位置に対する移動経路に沿った現在観測可能な目印のセットを決定することをもたらす、視覚的走行距離計測モジュールとを含む。現在観測可能な目印のセットは、プロセッサに通信可能に結合される撮像デバイスから得られる、１つ以上の立体画像から抽出される。位置特定モジュールは、プロセッサがプロセッサに通信可能に結合される調査目印データベースに問い合わせて、車両の現在位置に対する調査済み目印のサブセットを取得することをもたらし、この調査目印データベースは、以前に記憶された調査済み目印のセットを含む。姿勢補正モジュールは、プロセッサが現在観測可能な目印のセットと調査済みの目印のサブセットとの間の１つ以上の二次元変換推定サブセットを決定し、１つ以上の二次元変換推定から現在観測可能な目印のセットと調査済みの目印のサブセットとの間の距離を最小化する最良の変換推定を特定し、最良の変換推定に基づいて車両の姿勢を補正することをもたらす。

更なる態様によると、プロセッサにより実行されるとき、マッピング、位置特定、及び姿勢補正のための方法を実行する命令を含み、移動経路に沿った車両の現在位置及び現在位置に対する移動経路に沿った現在観測可能な目印のセットの決定を含む、非一過性コンピュータ可読媒体。現在観測可能な目印のセットは、撮像デバイスから得られる１つ以上の立体画像から抽出される。現在位置を特定する問合せに基づいて調査目印データベースからの調査済み目印のサブセットを受信することを含み、この問合せが調査目印データベースにおいて実行され、この調査目印データベースが以前に記憶された調査済み目印のセットを含み、現在観測可能な目印のセットと調査済み目印のサブセットとの間の１つ以上の二次元変換推定を決定することを含む、方法。現在観測可能な目印のセットと調査済みの目印のサブセットとの間の距離を最小化する１つ以上の二次元変換推定からの最良の変換推定の特定、及び最良の変換推定に基づく車両の姿勢補正を含む、方法。

この開示に特有であると考えられる新規性のある特徴は、添付の請求の範囲に記載されている。以下の記載において、類似の部分には、明細書及び図面の全体にわたって同じ符号がそれぞれ付けられる。図面は、必ずしも一定の比率で描かれているわけではなく、ある特定の図面は、明瞭さ及び簡潔さのために誇張されあるいは一般化された形態で示され得る。しかしながら、開示それ自体並びに好ましい使用の様式、その更なる目的及び利点は、添付の図面と併せて読むときに、添付の例示的実施形態の詳述を参照することにより最も良く理解されることになる。
一態様による、マッピング、位置特定、及び姿勢補正の例示的システムの概略図である。 一態様による、サービスによって提供される調査様式の例示的データフローの概略図である。 一態様による、位置特定様式の例示的データフローの概略図である。 一態様による、図３から継続する位置特定様式の例示的データフローの概略図である。 一態様による、例示的目的、等級、機能、及びファイルのＵＭＬ図である。 一態様による、マッピング、位置特定、及び姿勢補正の例示的方法の工程系統図である。 一態様による、図６の方法の１つ以上の二次元変換を決定する例示的方法の工程系統図である。 一態様による、第１の深さレベルでの最良推定のための１つの分枝因子を用いた例示的グリッド検索の概略図である。 一態様による、図８Ａの第１の深さレベルの後の第２の深さレベルでの最良推定のための１つの分枝因子を用いた例示的グリッド検索の概略図である。 一態様による、図８Ｂの第２の深さレベルの後の第３の深さレベルでの最良推定のための１つの分枝因子を用いた例示的グリッド検索の概略図である。 一態様による、第１の深さレベルでの２つ以上の最良推定のための２つの分枝因子を用いた例示的グリッド検索の概略図である。 一態様による、図８Ｄの第１の深さレベルの後の第２の深さレベルでの２つ以上の最良推定のための２つの分枝因子を用いた例示的グリッド検索の概略図である。 一態様による、図８Ｅの第２の深さレベルの後の第３の深さレベルでの２つ以上の最良推定のための２つの分枝因子を用いた例示的グリッド検索の概略図である。 一態様による、例示的分類リストの概略図である。 一態様による、例示的クラスタのセットの概略図である。 一態様による、姿勢補正適用前の地図の概略図である。 実際の道路に沿って目撃される目印を示す、１０Ａの地図の簡易図である。 車両の視覚的走行距離計測システムによって決定される、移動道路に沿って目撃される目印を示す１０Ａの地図の簡易図である。 車両の視覚的走行距離計測システムによって決定される移動道路に沿って目撃される目印の問合せの結果を示す図１０Ａの地図の図である。 １つ以上の２Ｄ変換を示す図１０Ａの地図の簡易図である。 １０Ａが最良の変換推定を示す場合の地図の簡易図である。 図１０Ａが目印を用いた最良の変換推定を示す場合の地図の簡易図である。 最良の変換推定が車両の現在位置に適用される図１０Ａの地図の図である。

以下は、本願明細書において使用される選択された用語の定義を含む。この定義は、用語の範囲内に該当し、実装に使用され得る、構成要素の様々な実施例及び／又は形態を含む。この実施例は、制限的なものであることを意図していない。更に当業者は本明細書における構成要素が、組み合わせ、省略、又は他の構成要素と組織化若しくは他のアーキテクチャに組織化され得るということを理解するであろう。

「バス」は、本明細書で使用される場合、他のコンピュータ内部又はコンピュータ間の他のコンピュータ構成要素に動作可能に接続される相互接続アーキテクチャを指す。バスは、コンピュータ構成要素の間でデータを伝達し得る。結果的に、バスは他のバスを用いて多様なデバイス、モジュール、論理回路、及び周辺機器と通信することができる。バスは、単一内部バス相互結合アーキテクチャ及び／又は他のバス若しくはメッシュアーキテクチャ（例えば、外部）であり得る。バスは、とりわけ、メモリコントローラ、周辺バス、外部バス、クロスバースイッチ、及び／又はローカルバスであり得る幾つかの実施形態において、バスは、とりわけコントローラエリアネットワーク（ＣＡＮ）、ローカル相互接続ネットワーク（ＬＩＮ）のようなプロトコルを用いて、車両内部の構成要素に相互接続する車両バスであり得る。

「コンピュータ通信」は、本明細書で使用される場合、２つ以上のコンピューティングデバイス（例えば、コンピュータ、ポータブルデバイス、個人用デジタル補助装置、セルラ電話、ネットワーク装置）間における通信を指し、例えば、ネットワーク転送、ファイル転送、アプレット転送、電子メール、ハイパーテキスト転送プロトコル（ＨＴＴＰ）転送等であり得る。コンピュータ通信は、例えば、とりわけ、無線システム（例えば、ＩＥＥＥ ８０２．１１）、イーサネット(登録商標)システム（例えば、ＩＥＥＥ ８０２．３）、トークンリングシステム（例えば、ＩＥＥＥ ８０２．５）、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、ポイントツーポイントシステム、回路交換方式、パケット交換方式にわたって生じ得る。

本明細書で用いられる「ディスク」は、例えば、磁気ディスクドライブ、ソリッドステートディスクドライブ、フロッピー(登録商標)ディスクドライブ、テープドライブ、Ｚｉｐドライブ、フラッシュメモリカード、及び／又はメモリスティックであり得る。更に、ディスクは、ＣＤ−ＲＯＭ（コンパクトディスクＲＯＭ）、ＣＤレコーダブルドライブ（ＣＤ−Ｒドライブ）、ＣＤリライタブルドライブ（ＣＤ−ＲＷドライブ）、及び／又はデジタルビデオＲＯＭドライブ（ＤＶＤ ＲＯＭ）であり得る。このディスクは、コンピューティングデバイスのリソースを制御するあるいは割り当てるオペレーティングシステムを記憶し得る。

「データベース」は、本明細書で使用される場合、表、表のセット、データ記憶のセット（例えば、ディスク）、並びに／又はそれらのデータ記憶にアクセスする及び／若しくはデータ記憶を操作する方法を指してもよい。

「メモリ」は、本明細書で使用される場合、揮発性メモリ装置及び／又は不揮発性メモリを含んでもよい。不揮発性メモリは、例えば、ＲＯＭ（読み取り専用メモリ）、ＰＲＯＭ（プログラマブル読み取り専用メモリ）、ＥＰＲＯＭ（消去可能ＰＲＯＭ）、及びＥＥＰＲＯＭ（電気的消去可能ＰＲＯＭ）を含んでもよい。揮発性メモリは、例えば、ＲＡＭ（ランダムアクセスメモリ）、シンクロナスＲＡＭ（ＳＲＡＭ）、ダイナミックＲＡＭ（ＤＲＡＭ）、シンクロナスＤＲＡＭ（ＳＤＲＡＭ）、ダブルデータレートＳＤＲＡＭ（ＤＤＲＳＤＲＡＭ）、ダイレクトＲＡＭバスＲＡＭ（ＤＲＲＡＭ(登録商標)）を含んでもよい。メモリは、コンピューティングデバイスのリソースを制御又は割り当てるオペレーティングシステムを記憶し得る。

「モジュール」は、本明細書で使用される場合、機能（複数可）若しくはアクション（複数可）を実行するため、並びに／又は別のモジュール、方法、及び／若しくはシステムから機能又はアクションをもたらすための、命令、機械の実行における命令、機械の実行におけるハードウェア、ファームウェア、ソフトウェア、及び／又はそれぞれの組み合わせを記憶する、非一過性コンピュータ可読メディアを含むが、これらに限定されない。モジュールはまた、論理回路、ソフトウェア制御マイクロプロセッサ、分離論理回路、アナログ電子回路、デジタル回路、プログラム論理デバイス、実行命令を含むメモリ装置、論理ゲート、ゲートの組み合わせ、及び／又は他の回路構成要素を含んでもよい。複数のモジュールが１つのモジュールへと組み合わせられてもよく、単一のモジュールが複数のモジュールの間で分配されてもよい。

「動作可能な接続」、又は実体が「動作可能に接続された」接続は、信号、物理的通信、及び／又は論理的通信が送信及び／又は受信され得るものである。動作可能な接続は、物理的インターフェイス、データインターフェイス、及び／又は電気的インターフェイスを含んでもよい。

「プロセッサ」は、本明細書で用いられる場合、信号を処理し、一般的な算定及び算術機能を果たす。プロセッサによって処理される信号は、受信、伝送、及び／又は検出され得るデジタル信号、データ信号、コンピュータ命令、プロセッサ命令、メッセージ、ビット、ビットストリーム、又は他の手段を含んでもよい。一般に、プロセッサは、複数、単一、及びマルチコアのプロセッサ及びコプロセッサ、並びに他の複数、単一及びマルチコアのプロセッサ及びコプロセッサのアーキテクチャを含む様々なプロセッサであり得る。プロセッサは様々な機能を実行するための様々なモジュールを含み得る。

「車両」は、本明細書で使用される場合、１人以上の人間の乗員を運ぶことが可能で、任意のエネルギー形態によって動力が提供される、あらゆる移動車両を意味する。用語「車両」は、車、トラック、バン、ミニバン、ＳＵＶ、モータサイクル、スクータ、ボート、個人用船舶、及び航空機を含むが、これらに限定されない。幾つかの場合においては、自動車は１つ以上のエンジンを含む。更に、用語「車両」は１人以上のヒトの乗員を運ぶことが可能であり、完全に又は部分的に電気バッテリによって給電される１つ以上の電気モーターによって給電される電気車両（ＥＶ）を指す。ＥＶは、バッテリ電気自動車（ＢＥＶ）及びプラグインハイブリッド電気自動車（ＰＨＥＶ）を含んでもよい。加えて、用語「車両」は、自律自動車及び／又は任意のエネルギー形態によって給電される自動運転自動車を指すこともできる。自律自動車は、一人以上の人間の乗員を運ぶことも、運ばないこともある。

「車両システム」は、本明細書で使用される場合、車両、運転、及び／又は安全を改良するために使用することができるあらゆる自動又は手動システムを含んでもよいが、これらに限られない。代表的な車両システムは、とりわけ、電気安定性制御システム、アンチロックブレーキシステム、ブレーキ補助システム、自動ブレーキプレフィルシステム、低速追従システム、クルーズ制御システム、衝突警報システム、衝突軽減ブレーキシステム、自動クルーズ制御システム、車線逸脱警報システム、ブラインドスポットインジケータシステム、車線維持支援システム、ナビゲーションシステム、送電システム、ブレーキペダルシステム、電子パワーステアリングシステム、視覚装置（例えば、カメラシステム、近接センサシステム）、気象制御システム、電気プリテンションシステムを含むが、これらに限られない。

Ｉ．システムの概観
一般的に、本明細書において開示されるシステム及び方法は、経路を移動するエージェント（例えば、車両、自律自動車、ロボット、ポータブルデバイスを有するユーザー）の姿勢補正のための立体ベースのマッピング及び位置特定方法を提供する。高密度ステレオ奥行データで構築されるエージェントの環境の小型軽量３Ｄローカルマップ、目印の２つのセット、及び精密化された変換推定を活用することにより、エージェントの経路の姿勢補正は、正確かつ迅速である。２つの操作モード、すなわち、調査モードと位置特定モードを含むものとして本明細書に記載される、方法及びシステム。しかしながら、２つのモードの機能及び構成要素は異なるアーキテクチャへと再組織化され得、及び／又は他のアーキテクチャ、モード、および実施形態において実装され得る。

次に図面を参照すると、提示は１つ以上の例示的実施形態の説明を目的とし、同様の物を制限することを目的とはしないが、図１は、一態様による、マッピング、位置特定、及び姿勢補正の例示的システム１００の概略図を示す。システム１００の構成要素は、他のシステムの構成要素、ハードウェアアーキテクチャ、及び本明細書におけるソフトウェアアーキテクチャと同様、組み合わせ、削除、又は様々な実施形態のための異なるアーキテクチャへと組織化され得る。更に、システム１００及び／又はシステム１００の１つ以上の構成要素は、幾つかの実施形態において、車両（非表示）、１つ以上の車両システム（非表示）、又はポータブルデバイス（非表示）と共に実装され得る。その上、システム１００及び／又はシステム１００の１つ以上の構成要素は、幾つかの実施形態において、本明細書でより詳細に考察されるように、調査モード又は位置特定モードを実行するために使用されることができる。

図１の図示される実施形態において、システム１００は、システム１００の様々な構成要素との処理、通信、及び相互作用を備えるコンピューティングデバイス１０２を含む。一般的に、コンピュータ１０２は、プロセッサ１０４、メモリ１０６、ディスク１０８、位置決定ユニット１１０、及び通信インターフェイス１１２を含み、それぞれはバス１１４によって、コンピュータ通信のために動作可能に接続される。コンピュータ１０２は、とりわけ、車両（非表示）、例えばＥＣＵ、車両ヘッドユニット、及び撮像システムと統合又は結合されることができる。通信インターフェイス１１２は、コンピューティングデバイス１０２の構成要素と、他の構成要素、ネットワーク、及び本明細書で記載されるデータ源との間のデータ入力及び出力を容易にするように、ソフトウェア及びハードウェアを提供する。更に、本明細書におけるシステム及び方法と共により詳細に取り挙げられるように、プロセッサ１０４は、視覚的走行距離計測モジュール１１６、位置特定モジュール１１８及び補正モジュール１２０を含む。

コンピューティングデバイス１０２は、コンピュータ通信のために、撮像デバイス１２２、ネットワーク１２４、及び調査目印データベース１２６（ＤＢ）に動作可能に接続される。撮像デバイス１２２、ネットワーク１２４及び調査目印ＤＢ １２６への接続は、例えば、とりわけ、通信インターフェイス１１２からのネットワーク接続（例えば、有線又は無線）、コンピューティングデバイス１０２に接続されたポータブルデバイス（非表示）からのセルラデータネットワーク、車両から車両へのアドホックネットワーク（非表示）、車載ネットワークを通して、様々な方法で容易にすることができる。

撮像デバイス１２２は、１つ以上のカメラ又は他の撮像デバイス及び他のセンシングデバイスを含んでもよい。例えば、撮像デバイス１２２は、とりわけ、１つ以上のステレオカメラ、三次元カメラ、リモートセンシングデバイス（例えば、ＬＩＤＡＲ、レーザー、センサー）であることができる。一実施形態において、撮像デバイス１２２は、画像風景（例えば、移動経路、車道、車両の周辺環境の風景）の立体画像（例えば、左の画像、右の画像）を得る。ネットワーク１２４は、例えば、データネットワーク、インターネット、ワイドエリアネットワーク又はローカルエリアネットワークである。ネットワーク１２４は、様々なリモートデバイス（例えば、ウェブサーバー、リモートサーバー、アプリケーションサーバー、仲介サーバー、クライアントマシン、他のポータブルデバイス）への通信媒体としての役割を果たす。

図１において、ネットワーク１２４は調査目印ＤＢ １２６を含む。調査目印ＤＢ １２６は、目印の整合及び位置特定のために構築され、本明細書においてより詳細に記述される。調査目印ＤＢ １２６は、以前に記憶された１２８調査目印のセット（例えば、Ｌ_ｉ．．．Ｌ_ｎ）を含んでもよい。更に、調査目印ＤＢ １２６は、記述ファイル１３０及びキーファイル１３２を含んでもよい。キーファイルは、各目印（例えば、Ｌ_ｉ．．．Ｌ_ｎ）の重心位置を含む。記述ファイル１３０は、各目印に関する追加的記憶情報を含む。記述ファイル１３０及びキーファイル１３２は、図５を参照し、本明細書においてより詳細に記載される。

一般的に、調査目印ＤＢ １２６は、位置決定ユニット、例えば、図１の位置決定ユニット１１０を活用して構築される。位置決定ユニット１１０は、幾つかの実施形態において、例えば全地球測位システム（ＧＰＳ）１３６及び／又は慣性計測装置（ＩＭＵ）１３８を有する、高質位置決定ユニット１４０を含んでもよい。高質位置決定ユニット１４０は、車両の全地球姿勢を決定するための高質で高価なデバイスであることができる。幾つかの実施形態において、高質位置決定ユニット１４０は１０〜１５ｃｍの位置精度を有する。高質位置決定ユニット１４０は、車両の全地球姿勢を得るための調査モードの間に活用される。

別の実施形態において、位置決定ユニット１１０は、例えば、全地球測位システム（ＧＰＳ）１３６、又は二次元（２Ｄ）車両の姿勢を決定する別のタイプのセンサー又は技術を有する、低質位置決定ユニット１４２を含んでもよい。低質位置決定ユニット１４２は車両の全地球姿勢を決定するためのより安いデバイスであることができる。幾つかの実施形態において、低質位置決定ユニット１４２は、標準車両ナビゲーションシステム及び／又はポータブルデバイス内のＧＰＳデバイスである。幾つかの実施形態において、低質位置決定ユニット１４２は、１０〜１５ｍの位置精度を有する。低質位置決定ユニット１４２は、二次元の相対的車両姿勢を得るための位置特定モードの間活用される。

上記のように、位置決定ユニット１１０は、別のデバイス、例えば車両におけるポータブルデバイス（非表示）と結合することができる。更に、位置及び全地球姿勢の情報は、他のデバイス、例えば、視覚走行距離測定システム（例えば、視覚走行距離測定モジュール１１６）から、又は、ネットワーク、例えばネットワーク１２４を通して得ることができる。位置決定ユニット１１０から得られた位置は、調査モード又は位置特定モードの間に用いられ、本明細書でより詳細に記述される。

ＩＩ．調査モード
調査モードの間、目印は車両の現在の移動経路に沿って抽出され、調査目印ＤＢ １２６に保存される。調査モードは、プロバイダ（例えば、第三者）からの提供として又は消費者側（例えば、位置特定されるエージェント）に実装されることができる。調査目印ＤＢ １２６は、位置特定の間に用いられる。調査モードは、図１の調査目印データベース（ＤＢ）１２６を構築するために第三者のサービスによって用いられた調査モードはこれから記述される。簡潔に言えば、調査モード過程の間、ローカル３次元（３Ｄ）地図は、複数のフレームにわたる高密度なステレオ視差画像を組み合わせることによる車両の周辺環境から構築される。対象物（例えば、目印）は地面表面の特定及び除去によりローカル３Ｄ地図から抽出される。これらの対象物及びこれらの対象物に関する情報は、その後、位置特定における更なる使用のためにディスク（例えば、図１の調査目印ＤＢ １２６）に保存される。

図２は、１つの態様に従い、サービスによって提供される調査モードの例示的データフローの概略図である。この実施形態において、調査目印ＤＢは、プロバイダ（例えば、第三者）からのサービスとして構築される。従って、位置特定の間、コンピューティングデバイスはプロバイダからの調査目印ＤＢからのデータにアクセスすることができる。この実施形態において、調査目印ＤＢは、ネットワーク、インターネット、クラウドによって提供されることができ、プロバイダによって維持されることができる。例えば、図１を参照すると、コンピューティングデバイス１０２はネットワーク１２４を通して調査目印ＤＢ １２６にアクセスすることができ、調査目印ＤＢ １２６は第三者のプロバイダによって維持されることができる。図１の構成要素は、図２に図示するデータフローブロックを容易にする及び実行するために用いられることができる。

再度図２を参照すると、立体画像２０２（例えば、図１の撮像デバイス１２２から得られたもの）及び車両の全地球姿勢２０４（例えば位置決定ユニット１１０によって決定されたもの）はローカル三次元（３Ｄ）地図２０６を生成するための入力として用いられる。一実施形態において、調査モードの間、車両の全地球姿勢２０４は、高質位置決定ユニット１４０（例えば、ＧＰＳ １３６、ＩＭＵ １３８）によって決定される。一実施形態において、立体画像２０２はセンサーデータ、例えば撮像デバイス１２２からの、例えばカメラ追跡データ、カメラ軌道データを含んでもよい。ローカル３Ｄ地図２０６は、車両の外部環境の眺望を提供し、車両の中心に置かれる（すなわち車両と共に移動する）。

一実施形態において、ローカル３Ｄ地図２０６は、容積測定及びキーフレームに基づくアプローチを用いて構築される。この実施形態において、立体画像２０２の容積測定表示が生成される。現在のフレームは、フレームと以前のキーフレームとの間における十分なカメラの動きがある場合、キーフレームと指定される。キーフレーム間の相対的姿勢は推定される。一実施形態において、相対的姿勢は、立体画像（例えば、左及び右の画像）におけるハリスコーナー特徴を追跡するためのＫＬＴトラッカーを用いて推定される。特徴は正規化ＳＳＤ（自乗誤差）を用いて左及び右の画像間で整合され、特徴の３Ｄ位置はそれらの不等に基づいて算出される。ＲＡＮＳＡＣに組み込まれる３点アルゴリズムは、異常値を除去し、運動仮説に整合する特徴の一致を発見する。インライアは非インライア最適化を用いて処理され、カメラフレームの高精度の姿勢推定を発見し、新しいインライアのセットを発見する。最後のキーフレームは局所的バンドル調整（ＬＢＡ）モジュール（非表示）を通過し、キーフレームの相対的姿勢推定を改善し、現在のキーフレーム位置の周囲の局所的メートル法地図を確かなものにする。

キーフレーム及びそれらの姿勢は車両の周辺環境のローカル３Ｄ地図２０６を構築するために用いられる。具体的には、ローカル３Ｄ地図２０６を生成するために、それぞれのキーフレームに対して、最初の立体画像２０２とソーベルフィルター画像の加重複合上のＳＡＤブロックマッチングと共にセミグローバル整合アルゴリズムを用いて、変異型高密度ステレオ視差／奥行画像が算出される。更に、スキャンライン最適化は、例えば、算出時間を節約するために８又は１６とは対照的に２方向のみで行われる。

車両の中心に置かれるローカル３Ｄマップ２０６は、単一の対等なフレームに奥行画像を記録するためにキーフレームの姿勢を使用する複数のキーフレームにわたる高密度奥行画像を組み合わせることによって、生成される及び／又は更新される。具体的に、一実施形態において、３Ｄ占有グリッドがローカル３Ｄ地図を構築するために用いられ、画像における犠牲不同値を除去する。複数の奥行画像の組み合わせ及び３Ｄ占有グリッドの使用は、高精度の方法でローカル３Ｄ地図２０６を生成する、異常値及びそれにより欠落した奥行に対処する速くて効果的な方法を提供する。ローカル３Ｄ地図２０６は目印分割及びトラッキング２０８のために活用され、以下で詳細に記載される。

Ａ．目印分割
３Ｄローカル地図２０６は目印分割２１０のために処理され、車両の環境における、地面表面、例えば車道及び歩道、及び抽出対象物（例えば、目印）例えば木及び交通標識を除去する。対象物はフィルターがかけられ、結果として現在観測可能な目印２１２のセットになる。結果として現在観測可能な目印２１２のセットは目印トラッキング２１４のために活用され、時間を通じて目印を追跡する。

目印分割２１０は様々な方法で実行することができる。一実施形態において、地面表面は、土地及び対象物の高さに基づく群を作る領域拡張アルゴリズムを用いて抽出される。この実施形態において、領域拡張アルゴリズムは３Ｄ占有グリッドにおける垂直なボクセル列上で作用し、垂直なボクセル列を地面として又は対象物として分類する。領域拡張アルゴリズムは、地面上にあると思われる車両の現在位置（例えば、車両の全地球姿勢２０４）を使用し、車両によって占有される全ボクセル列を地面として分類する。分類された列は、将来の検証のために、ボクセル列のリストに加えられる。車両によって占有されたそれぞれのボクセル列の高さも又算出される。高さは、車両の下で占有された最も高いボクセルの離散化された高さ、又はそれが不明な場合は、高さは、車両及びカメラ調整情報の既知の寸法を用いた地面の推定される離散化された高さである。

領域拡張アルゴリズムは車両列に隣接するボクセル列を検証し、それらの高さを算出する。具体的には、ボクセル列リストが飛び出し、飛び出した列に隣接する列が検証される。ボクセル列の高さは、その位置の地面の高さ、又は、その場所が対象物によって占有されている場合は、その対象物の高さである。車両の屋根よりも高い張り出しである、張り出している対象物の場合は、地面の高さをボクセル列の高さとして使用する。データを有さない列は、隣接する列の高さを用いてそれらの高さを補填する。

隣接するボクセル列の高さが飛び出した列の閾値内である場合、隣接するボクセル列は地面として分類される。高さが大きく異なる場合はボクセル列は未分類のままとなる。地面として分類されたボクセル列は列リストに加えられ、ボクセル列の隣接部も又検証される。このように進めると、領域拡張アルゴリズムが３Ｄ占有グリッドを通過し、高さの差異に基づいて、ボクセル列の高さ及びボクセル列の分類を算出する。

領域拡張アルゴリズム過程の終了後、全ての分類されたボクセル列は対象物として分類される。例えば、対象物に属するボクセルのリストを生成するために接続された構成要素のアルゴリズムを用いて、対象物に属するすべてのボクセルが抽出される。接続された構成要素のアルゴリズムは、対象物として分類された列の占有されたボクセルを用い、新しい対象物リストを初期化する。接続された構成要素のアルゴリズムは、占有されたボクセルに隣接する同様に占有されたボクセルの全てを特定する。隣接するボクセル列が対象物として分類される場合、それは対象物リストに加えられる。列が地面として分類される場合、ボクセルは、その高さがその列の高さよりも大きい場合（例えば、張り出し対象物であることを示す）に限って、対象物リストに加えられる。接続された構成要素のアルゴリズムは、全ての接続されたボクセルが検証されるまで、新しく加えられたボクセルの隣接部を検証する。対象物は接続された占有されたボクセルのリストである。

対象物は高さ及びサイズに基づいてフィルターをかけられる。対象物が低すぎる場合又は対象物の境界ボックスの断面のサイズが大きすぎる場合、対象物は対象物リストから除去される。高さに基づくフィルタリングは常に観測することが難しい小さい対象物を除去し又は十分な情報を有さない対象物のために除去する。更に、サイズに基づくフィルタリングは、位置特定への使用に容易な小さいベースを有する対象物をもたらす。その上、フィルタリングは、誤った目印を提供することで姿勢補正過程を混乱させ得る、ほとんどの駐車車両を除去する。この対象物の最終セットは、３Ｄローカル地図２０６における、現在観測可能な目印２１２のセットである。現在観測可能な目印２１２のセットは目印のボクセルのリスト及び目印に関連する開始及び終了地点を含んでもよい。現在観測可能な目印２１２のセットは、例えば、メモリ１０６及び／又は図１のディスク１０８に記憶することができる。又は、現在観測可能な目印２１２のセットは、遠隔データベース、例えば、ネットワーク１２４によるアクセスにより記憶することができる。

Ｂ．目印追跡
現在観測可能な目印２１２のセットは、目印追跡２１４過程により、経時的に追跡される。目印追跡２１４は、本明細書に記述される方法及びシステムの調査モード及び位置特定モードにおいて実行される。調査モードにおいて、目印追跡２１４は目印がディスク（例えば調査目印ＤＢ １２６）に書き込まれたトラックを追跡する。位置特定モードにおいて、目印追跡２１４は、ローカル３Ｄ地図２０６のサイズより遠い距離に及ぶ目印のトラックを追跡する。

目印を追跡するために、現在観測可能な目印２１２のセットは、調査目印ＤＢ ２１６における既存の目印のセットと整合される。具体的に、既存の目印のセットは以前に記憶された調査済み目印１２８のセットである。調査目印ＤＢ ２１６におけるそれぞれの目印（例えば、以前に記憶された調査済み目印１２８のセット）は関連情報を含む。例えば、一実施形態において、それぞれの目印は以下の特質（ｉ）ＩＤ、特有の目印ＩＤ、（ｉｉ）更新済み、目印が現在のキーフレームにおいて更新されているか、（ｉｉｉ）ＦＯＶ内、目印がカメラの視界内にあるか、（ｉｖ）外部、目印がローカル３Ｄ地図の外部領域にあるか、（ｖ）保存済み、目印がディスクに保存されているか、を有する。図５は、特質、特質型及び関連機能を含む、例示的目印対象物５０２（例えば以前に記憶された調査済み目印１２８のセット内の目印）のＵＭＬ図である。図５のＵＭＬ図は、本質的に例示的であり、他の特質、特質型、及び機能も又対象物５０２を用いて実装され得るということが理解される。

上記の通り、目印追跡２１４は、現在観測可能な目印２１２のセットと、調査目印ＤＢ ２１６内の以前に記憶された調査済み目印１２８のセットを整合させる。一実施形態において、以前に記憶された調査済み目印１２８のセット内のそれぞれの目印の位置（例えば、Ｌ_ｉ．．．Ｌ_ｎ）は、整合の前に、現在のローカル３Ｄ地図２０６の対等フレームに変換される。整合は、現在観測可能な目印２１２のセット及び以前に記憶された調査済み目印１２８のセットを用いて二部グラフを構築することによって行われることができ、二つの互いに素な集合を形成する。グラフ内のエッジは、現在の目印と既存の目印との間に、２つの目印量が重なり合う場合に、加えられる。具体的に、二部グラフに基づき、２つの目印を含むボクセルのセットが交差する場合、現在観測可能な目印２１２のセットと以前に記憶された調査済み目印１２８のセットとの間の同値類が、それぞれにおける既存及び現在の目印の数に基づいて、特定及び分類される。以前に記憶された調査済み目印１２８のセットは、同値類の型に基づいて更新される。

同値類の型及びそれらの関連した更新がこれから記載される。１つの現在及び１つの既存の同値類において、整合が発見される。従って、既存の目印の特質は以下のように更新される、（ｉ）ＩＤ、変更なし、（ｉｉ）更新済み、現在と既存の目印がそれらのボクセルリスト又はボクセルにおける終了点において異なる場合ＴＲＵＥに設定する（ｉｉｉ）ＦＯＶ内、現在の目印がカメラの視界内にある場合ＴＲＵＥに設定する、（ｉｖ）、外部、現在の目印がローカル３Ｄ地図の外部領域にある場合ＴＲＵＥに設定する、（ｖ）保存済み、既存の目印の値に設定する。

新しい奥行データが入手可能になると生じ得るように、１つの現在及び多数の既存の同値類において、幾つかの既存の目印が単一の現在の目印に統合する。最大の重なり合いを有する既存の目印のボクセル及び点のリストは現在の目印のボクセルリストに更新され、その特質は、上述の１つの現在及び既存の同値類の場合にあるように更新される。既存の目印の残りは消去される。

以前占有されたボクセルが自由空間になる場合又は分割が変更する場合に生じ得るように、多数の現在及び既存の同値類において、幾つかの現在の目印が単一の既存の目印から生じる。この場合において、最大の重なり合いを有する既存の目印のボクセル及び点のリストは現在の目印のボクセルリストに更新され、その特質は、上述の１つの現在及び１つの既存の同値類の場合にあるように更新される。残存する現在の目印には新しい固有の目印ＩＤが与えられ、同様に更新された特質を伴い既存の目印のリストに加えられる。特質、保存済みはＦＡＬＳＥに設定される。

多数の現在及び多数の既存の同値類において、それぞれの現在の目印は最大の重なり合いを有する既存の目印と整合される。そのＩＤが別の既存の目印に与えられていない場合、現在の目印には既存の目印のＩＤがあたえられる。残存する更新は、上述の、１つの現在及び１つの既存の同値類の場合のように、行われる。既存のＩＤが既存の目印に既に与えられている場合、新しい固有のＩＤが現在の目印のために作られる。残存する更新は、上述の、１つの現在及び１つの既存の同値類の場合のように行われるが、しかしながら、特質、保存済みはＦＡＬＳＥに設定される。

１つの現在及びゼロの既存の同値類において、現在の目印は、既存の目印のリストに加えられ、新しい固有のＩＤが与えられる。特質、更新済みは、ＴＲＵＥに設定され、特質、保存済みはＦＡＬＳＥに設定される。残存する更新は、上述の、１つの現在及び１つの既存の同値類の場合のように、行われる。ゼロの現在及び１つの既存の同値類において、既存の目印は、ＦＡＬＳＥに設定される、特質、更新済みを除いて残される。

結果的に、目印分割と追跡２０８の整合過程の最後に、以前に記憶された調査済み目印１２８のセット及びそれらの特質は現在の目印（例えば、現在観測可能な目印２１２のセットから）を用いて更新される。

Ｃ．目印の性質の算出及びディスクへの保存
位置特定は現在観測可能な目印のセットを記憶済みの目印（すなわち、以前に記憶された調査済み目印１２８のセット）に整合させることを含む。整合過程を援助するために、記憶済みの目印の幾つかの性質、例えば、重心、主軸、及び寸法が算出される。性質が算出される前に、目印はローカル３Ｄ占有グリッドよりも精度の高い解像度で形作られ、性質をより正確に算出する。一実施形態において、性質は新しい目印（すなわち、新しいＩＤを有する物）又は特質、更新済みのＴＲＵＥ及び特質、保存済みのＦＡＬＳＥを有する物だけに算出される。

性質を算出するために、一実施形態において、目印は符号付距離場を使用して形作られる。３Ｄ占有グリッドよりも精度の高い解像度を有する新しい３Ｄグリッドは目印を包囲して作られる。目印に関連する開始点に対しては、その終了点に光線が当てられる。終了点を有するボクセルには距離値ゼロが与えられる。光線に沿う及び、開始点と終了点ボクセルとの間のボクセルには、ボクセルが終了点からどれだけ遠いかを測定する、正の距離が与えられる。同様に、終了点ボクセルを超える（開始点から離れる）光線に沿うボクセルには負の距離が与えられる。この過程がそれぞれの開始−終了対に対して実行されるため、ボクセルが幾つかの開始−終了点対間の光線に位置する場合、ボクセルに複数の距離が与えられ得る。

ボクセルにおける距離は、実在の目印表面からのボクセルの距離の複数の推定を提供することができる。距離は実在の目印表面からのボクセルの距離の単一の推定を得るために平均化される。具体的に、一実施形態において、距離は最大値に切り捨てられ、瓶にグループ化され、加重平均が算出される。全てのボクセルを考慮したこれらの平均化された距離は符号付距離場を構成し、目印表面はその零レベルセットとして得られる。それは零に近い符号付距離を有する全てのボクセルが目印表面の構成に用いられるということである。

目印ボクセルが特定されると、ボクセルの座標が、それぞれの目印の以下の性質を算出するために用いられる、（ｉ）重心、全ての表面ボクセルの重心として算出される（ｉｉ）主軸、ボクセルの中心座標上の主要構成要素分析（ＰＣＡ）によって得られる（ｉｉｉ）軸寸法、それぞれの軸の相違に比例し、ＰＣＡの結果としても得られる、（ｉｖ）半径、目印表面へ垂直シリンダを合わせること及びそのシリンダの半径を用いることによって決定される。目印表面を描写するボクセル座標に従うこれらの特質は、目印の記述と見なされる。

調査モードにおいては、目印の記述は、目印がもはやカメラの視界に無く、目印がローカル３Ｄ地図の外部領域にある場合、ディスク（すなわち、調査目印ＤＢ ２１６）に書き込まれる。換言すれば、目印の記述は、特質、外部がＴＲＵＥであり、特質、視界内及び保存済みがＦＡＬＳＥである場合に、ディスクに書き込まれる。目印がディスクに書き込まれると、特質、保存済みはＴＲＵＥに設定され、目印がディスクに再度書き込まれることはない。一実施形態において、目印の記述は、記述ファイル１３０に書き込まれる。図５は、特質、特質型、及び関連機能を含む、例示的な記述ファイル５０６のＵＭＬ図を図示する。

一実施形態において、目印の記述がディスクに書き込まれる前に、全ての３次元座標が、高質位置決定ユニット１４０（すなわちＧＰＳ １３６及びＩＭＵ １３８、車両の全地球姿勢２０４）から得られる車両の自由度６の姿勢を用い、緯度、経度及び高度に変換される。例えば、

を車両の座標枠における点の位置とする。

を、ＧＰＳ １３６及びＩＭＵ １３８に与えられる通り、車両の緯度、経度、高度、ヨー、ピッチ、及びロールとする。すると、点

のＧＰＳ座標は以下によって推定される、

記述ファイル１３０は、目印の重心の緯度及び経度でタグ付け（例えばプロセッサ１０４によって）される。更に、それぞれの目印の緯度及び経度の図心を含むキーファイル１３２が生成される。このキーファイル１３２は、位置特定モードにあるプロセッサ１０４により、メモリ１０６内に読みとられ、車両の近くの目印を容易に特定し、それらの関連ファイルを素早く読み取ることを可能にする。図５は、特質、特質型及び関連機能を含む、例示的キーファイル５０４のＵＭＬ図を図示する。

上記のように、調査モードはプロバイダ（例えば第三者）からの提供として又は消費者側に実装されることができる。消費者の場合においては、調査モードは、高質ＧＰＳ及びＩＭＵデバイス、例えば、図１の高質位置決定ユニット１４０を有する車両に実装されることができる。結果的に、調査モードは、消費者側で、高質位置決定ユニット１４０を活用し、図２に図示されるものと同様な段階を踏み得る。

ＩＩＩ．位置特定モード
位置特定モードにおいては、車両の位置特定は、車両の経路に姿勢補正を算出及び適用するための目印整合及び目印変換を含む。車両を全地球フレームにおいて位置特定するために、位置特定モードの間観測された目印は調査モードの間ディスクに記憶された目印に整合される。

Ａ．位置特定モードの概観
図３及び４は、１つの態様に従う、位置特定モードの間の例示的データフローの概略図である。図３及び４はこれから図１〜２を参照して詳細に記載される。一実施形態において、視覚的走行距離計測モジュール１１６は、移動経路及び車両の相対的姿勢に対する移動経路に沿った現在観測可能な目印のセットに従い、車両の相対的姿勢を決定する。例えば、図１及び２と共に上述のように、立体画像３０２及び車両の相対的姿勢３０４（例えば視覚的走行距離計測モジュール１１６によって決定される）はローカル３Ｄ地図３０６を生成するために用いられる。ローカル３Ｄ地図３０６は、目印分割３１０（例えば、図２の目印分割２１０と共に上述のように）を用いて処理され、結果として現在観測可能な目印３１２になる。従って、現在観測可能な目印３１２のセットは撮像デバイス１１２から得られた１つ以上の立体画像３０２から抽出される。

次に図４を参照すると、車両の現在位置（例えば現在の弱い全地球姿勢）は、例えば低質位置決定ユニット１４２を用いて、二次元（２Ｄ）車両姿勢３１６として決定することができる。２Ｄの車両の姿勢３１６は少なくとも車両位置の緯度及び経度を提供する。幾つかの実施形態において、２Ｄの車両の姿勢３１６は、約１０ｍの標準偏差を有する車両の位置を提供する。

一実施形態において、目印整合３１８において、調査目印ＤＢ １２６は２Ｄの車両の姿勢３１６で問合せされ、車両の現在位置（すなわち２Ｄの車両の姿勢３１６）に対する調査済み目印３２０のサブセットを特定する。例えば、位置特定モジュール１１８は車両の現在位置を含む問合せを生成することができ、問合せを調査目印ＤＢ １２６で実行し、車両の現在位置に対する調査済み目印３２０のサブセットを取得する。具体的には、一実施形態において、位置特定モジュール１１８は、幾つかの過去のＧＰＳ読み取りにラインを合わせることにより、グローバルＧＰＳフレームにおける車両のおおよその機首方位（ヨー）を推定することができる。一実施形態において、幾つかの過去のＧＰＳ読み取りは低質位置決定ユニット１４２から得ることができ、例えば低質位置決定ユニット１４２のメモリ及び／又はメモリ１０６又はディスク１０８に保存される。

は、それぞれライン適合によって算出された、緯度、経度、及び機首方位を表す符号を有する、車両の現在２Ｄ ＧＰＳ姿勢３１６を図示する。調査モードの間生成されたキーファイル１３２を活用し、調査済み目印３２０のサブセットは車両の現在位置に近いと特定される。記述ファイル１３０からの、調査済み目印３２０のサブセットと関連付けられる情報も読み取られる。記述ファイル１３０からのＧＰＳ座標は、車両の現在２Ｄ姿勢３１６を下記のように用いることにより、車両のフレームに準じてカルテシアン座標に変換される。

ここにおいて

は調査済み目印３２０のサブセットの目印のＧＰＳ座標であり、

は車両の座標フレームにおける調査済み目印３２０のサブセットの目印の位置である。

車両の姿勢に適用させる姿勢補正３２６を算出するために、目印変換３２２において、調査済み目印３２０のサブセットと現在観測可能な目印４０２のセットとの間における、１つ以上の二次元（２Ｄ）変換が推定される。一実施形態において、姿勢補正モジュール１２０は、現在観測可能な目印のセットと調査済み目印のサブセットとの間における１つ以上の二次元変換を決定する。

変換は二次元で推定されるが、しかしながら、他の実施形態において、目印表面を用いることによる三次元変換を推定することができる。２Ｄ変換推定を算出するために、目印の重心及び表面は２Ｄに投影される（例えばｚ座標を除去する）。これらの投影は、目印のセットのレイアウト及び構造を記述する目印シグネチャーとして定義される。目印シグネチャー（非表示）はリアタイムで生成され、迅速で小型軽量な２Ｄ整合を可能にする。

更に、目印変換３２２において、最良の変換推定は１つ以上の２Ｄ変換推定から、下記でより詳細に記述されるクラスタ検索３２４を用いて決定される。具体的には、姿勢補正モジュール１２０は１つ以上の２Ｄ変換推定から最良の変換を特定することができる。幾つかの実施形態において、最良の変換推定は、現在観測可能な目印３１２のセットと調査済み目印３２０のサブセットとの間の距離を最小化する。

１つ以上の２Ｄ変換推定から、

のように最良の変換推定を算出及び推定した後、車両の現在２Ｄ姿勢３１６は補正姿勢を得るために以下のように適応され、

ここにおいて

は車両の最終補正姿勢３２６である。結果的に、高密度立体深さデータでよって構築された車両の環境の小型軽量３Ｄローカル地図を活用することにより、目印の２つのセット及び精密化された変換推定、車両の経路の姿勢補正は正確で速い。

Ｂ．１つ以上の２Ｄ変換推定の決定及び最良の変換推定の特定
上述のように、姿勢補正を算出するために、目印変換３２２において、現在観測可能な目印３１２のセットと調査済み目印３２０のサブセットとの間における１つ以上の二次元（２Ｄ）変換推定が決定される。１つ以上の二次元変換推定は２Ｄ剛体変換である。２Ｄ剛体変換は単一回転及び２Ｄ転換からなる。具体的には、Ｘオフセット、Ｙオフセット及び回転方向における変換。

一般的に、２Ｄ変換推定は、離散有界空間内の深さレベルＮについての１つ以上の変換尺度での１つ以上の２Ｄ変換推定を推定することにより誘導され、深さレベルＮについての１つ以上の最良の変換推定を選択し、その一つ以上の最良の変換推定に基づいて離散有界空間を修正する。この過程は最大深さレベルＮからのそれぞれの深さレベルＮについての離散有界空間内の１つ以上の変換尺度での１つ以上の２Ｄ変換を推定することにより続くことができる。

１つ以上の変換尺度は粗い変換尺度から細かい変換尺度へ向上する。従って、１つ以上の変換尺度は、幾つかの実施形態において、以前の変換尺度よりも詳細度が高い（例えば動作レベルが高い）。例えば、第１の変換尺度では、１つ以上の２Ｄ変換推定は粗い動作（例えば１ｍインクリメント）として始まり得る。第２の変換尺度では、２Ｄ変換推定は、第１の動作尺度の粗い動作よりも細かい動作（例えば１／２ｍインクリメント）である。２つを超える変換尺度が、１つ以上の２Ｄ変換推定を推定するために用いられることができるということが理解される。

目印変換３２２及びクラスタ検索３２４が、これから図８Ａ〜８Ｆを参照して詳細に記述される。図８Ａ、８Ｂ及び８Ｃは、それぞれの深さレベルＮにおいて単一推定（すなわち１の分枝因子）を有する多様な変換尺度における、最良の変換推定のための例示的グリッド及び木検索の概略図であり、最大深さレベルＮは３である（すなわち図８Ａ．Ｎ＝１、図８Ｂ．Ｎ＝２、図８Ｃ．Ｎ＝３）。あらゆる数の分枝因子及び深さレベルが実装され得るということが理解される。次に図８Ａを参照すると、１つ以上の２Ｄ変換推定はグリッド８００によって定義づけられた離散有界空間において推定される。１つ以上の２Ｄ変換推定は１つ以上の変換尺度で推定される。変換尺度は粗い変換尺度から生成された変換尺度へ向上する。一実施形態において、変換尺度は決まった数により、例えば４５度インクリメントにより、及び１メートルインクリメントにおける転換により向上する。

例示の実施例として、１つ以上の２Ｄ変換推定は第１の変換尺度で、例えば粗い動作を用いて、推定されることができる。例えば、粗い動作は、４５度インクリメントでの回転及び１メートルインクリメントでの転換を含んでもよい。別の例では、１つ以上の２Ｄ変換推定は、第２の変換尺度で推定されることができる。第２の変換尺度は、例えば、第１の変換尺度よりも、細かい尺度又は細かい動作である。従って、例えば、第２の変換尺度での１つ以上の２Ｄ変換は２５度インクリメントでの回転及び１／２メートルインクリメントでの転換を含んでもよい。

それぞれの深さレベルＮにおいて、最良の変換推定が決定される。一実施形態において、変換スコア及び／又は変換コストは、１つ以上の２Ｄ変換推定のそれぞれに対して決定される。一実施形態において、スコア及び／又はコストは、２Ｄ変換適用後の、現在観測可能な目印３１２のセットと調査済み目印３２０のサブセットとの間の距離の測定に基づく。例えば、一実施形態において、２Ｄ変換適用後の現在観測可能な目印３１２のセットと調査済み目印３２０のサブセットとが近いほど（すなわち、目印間の最小化された距離、重心間の最小化された距離）、変換推定は良くコスト及び／又はスコアは低い。例えば、零のスコア又はコストは完璧な変換となる。

別の実施形態において、距離の測定は一組の距離に適応されるいかなるノルムでも良い。例えば、一実施形態において、スコア及び／又はコストは、２Ｄ変換適用後の現在観測可能な目印３１２のセットと調査済み目印３２０のサブセットとの間の平均２乗誤差の平方根に基づき決定される。結果的に、それぞれの２Ｄ変換推定に対して、スコアが決定され、２Ｄ変換推定にあたえられる。

結果的に、深さレベルＫにおける最良の変換推定は、１つ以上の２Ｄ変換推定のそれぞれに関連する変換コストに基づいて決定されることができる。一実施形態において、離散有界空間は深さレベルＫにおける最良の変換推定に基づいて修正される。再び図８Ａを参照すると、最良推定８０２はグリッド８００の区域８０４において選択される。従って、図８Ｂにおいて、区域８０４は１つ以上の２Ｄ変換推定を決定するための離散有界空間になる。

図８Ａの記述と同様に、図８Ｂにおける１つ以上の２Ｄ変換は深さレベルＫ＋＋（２）における１つ以上の変換尺度で推定される。深さレベルＫ＋＋（２）Ｋにおける最良の変換推定は１つ以上の２Ｄ変換推定のそれぞれに関連する変換コストに基づいて決定される。一実施形態において、離散有界空間は深さレベルＫ＋＋（２）Ｋにおける最良の変換推定に基づいて修正される。

図８Ｂにおいて、最良推定８０６は離散有界空間８０４において選択される。結果的に、離散有界空間は最良推定８０６の周囲の区域８１０に再定義される。従って、図８Ｃにおいては、１つ以上の２Ｄ変換推定は区域８１０（すなわち、再定義された離散有界空間）に限定される。図８Ｃにおける１つ以上の２Ｄ変換は深さレベルＫ＋＋（３）における１つ以上の変換尺度で推定される。深さレベルＫ＋＋（３）における最良の変換推定は、１つ以上の２Ｄ変換推定のそれぞれに関連する変換コストに基づいて決定されることができる。図８Ｃにおいては、最良推定８１２は区域８１０（例えば離散有界空間）において選択される。

上述の過程は深さレベルＫ及び／又は２Ｄ変換推定の数を前もって決定するために繰り返される。更に、過程は１つを超える最良の変換推定に対して実行されることができる。例えば、図８Ａ，８Ｂ及び８Ｃは、図８Ｄ，８Ｅ及び８Ｆに図示される単一推定ではなく、１つを超える推定を有する多様なレベル（例えば、１つを超える分枝因子）での最良の変換推定のための例示的グリッド検索の概略図である。

一実施形態において、最良の変換推定がそれぞれの深さレベルＮから最大深さレベルＮまでにおいて決定されると、それぞれの深さレベルＮについての最良の変換推定を含み、それぞれの深さレベルＮについての最良の変換推定に対して決定される変換コストに基づいて分類される、分類リストが生成される従って、３つの最大深さレベルＮ及び１つの分枝因子を有する図８Ａ，８Ｂ及び８Ｃを参照すると、分類リストは、それぞれの深さレベルに対して１つの、３つの最良の変換推定を含み得る。換言すると、求められた最良の変換推定は、最大深さレベルＫを乗じる分枝因子Ｎを含む。３つの最大深さレベルＮ及び２つの分枝因子を有する図８Ｄ，８Ｅ及び８Ｆを参照すると、分類リストは、それぞれの深さレベルＮに対して２つの、９つの最良の変換推定を含み得る。

図９Ａは、それぞれの深さレベルＮに対する最良の変換推定で生成された例示的分類リスト９００を図示する。図９Ａにおいて、分類リスト９００の第１の列は深さレベルＮについての最良推定を特定し、第２の列は深さレベルＮに対する最良推定に関連する変換コストを特定する。図９Ａにおける最大深さレベルは１つの分枝因子を伴う６であるが、しかしながら、あらゆる最大深さレベル又はあらゆる数の分枝因子が実装され得るということが理解される。図９Ａにおいて、最良の変換推定は最低変換コストから最高変換コストへと分類される。

一実施形態において、分類リストにおけるそれぞれの最良の変換推定に隣接する最良の変換推定と比較される。これは最低変換コストから最高変換コストまで繰り返されることによって達成されることができる。変換コスト間で有意差（例えば、誤差＞所定の数）が決定されると、最良の変換推定を含むクラスタが生成される。換言すると、スコアに有意差（例えば２つのスコアが５０％異なる）があるとき、新しいクラスタが指定される。

再び図９Ａを参照すると、Ｂ_Ｎ１はＢ_Ｎ５と比較され、Ｂ_Ｎ３はＢ_Ｎ６と比較され、分類リストの最後に到達するまで同様に続く。１つの例示の実施例においては、所定の差は５に設定される。従って、図９Ａにおいては、最良の変換推定と隣接する変換推定との間の差が５を超えるとき、クラスタが生成される。例示の実施例として、Ｂ_Ｎ３はＢ_Ｎ６と比較される（すなわち、２０−６＝１４）。Ｂ_Ｎ３とＢ_Ｎ６との間の差が１４であるため、Ｂ_Ｎ３とＢ_Ｎ６との間にクラスタ分割が挿入される。従って、第１のクラスタはＢ_Ｎ１、Ｂ_Ｎ５及びＢ_Ｎ３を含む。別のクラスタ分割が決定されていないと仮定すると、第２のクラスタはＢ_Ｎ６、Ｂ_Ｎ３及びＢ_Ｎ４を含む。

図９Ｂは、１つの態様に従う、例示的クラスタのセットの概略図である。例えば、クラスタ９０２，９０４及び９０６はそれぞれ、上述の繰り返し比較に基づく複数の２Ｄ変換推定を含む。図９Ａの例及び図９Ｂの表を参照すると、第１のクラスタはクラスタ９０２であり得、第２のクラスタはクラスタ９０４であり得る。

一実施形態において、クラスタはその最良推定に基づくスコアを与えられる。一実施形態において、最良の推定は、最低スコアを有する物である。再び図９Ａの例を参照すると、第１のクラスタにおいて２が最低変換スコアであるため、第１のクラスタはＢ_Ｎ１に関連するスコアを与えられる。同様に、第２のクラスタは、第２のクラスタにおいて２０が最低変換スコアであるため、Ｂ_Ｎ６に関連するスコアを与えられる。図９Ｂを参照すると、それぞれのクラスタ９０２、９０４及び９０６は、そのクラスタにおける複数の２Ｄ変換の最良推定に基づくスコアを与えられる。

結果的に、一実施形態において、姿勢補正は、それぞれのクラスタによって決定された最良の変換推定に基づいて適応される。従って、最良の変換推定（例えば、最良クラスタ変換推定）はそれぞれのクラスタの最良の変換推定に基づいて選択される。この最良クラスタ変換推定は車両に姿勢補正を適用するために使用することができる。例示の実施例としては、クラスタＡにおける最良推定がクラスタＢにおける最良推定よりも良い（例えば、低い）とき、クラスタＡはクラスタＢよりも良い。従って、図９Ａの例を参照すると、第１のクラスタの最良の変換推定が２であり、第２のクラスタの最良の変換推定が２０であるよりも低いため、最良クラスタ変換推定は２であり、この変換推定は車両の姿勢補正に適応されることができる。

Ｃ．マッピング、位置特定、及び姿勢補正の方法
上述した、図１〜５に図示されるシステム１００はこれから図６の方法を参照し記述される。上述の図１〜５におけるシステム及び構成要素は図６の方法で同様に実装され得るということが理解される。図６の方法は、１つの態様に従う、マッピング、位置特定、及び姿勢補正の例示的方法を図示する。ブロック６０２において、本方法は移動経路に沿った車両の現在位置及び現在位置に対する移動経路に沿った現在観測可能な目印のセットの決定を含む。現在観測可能な目印のセットは、撮像デバイスから得られる１つ以上の立体画像から抽出される。例えば、図１の位置決定ユニット１１０、具体的に低質位置決定ユニット１４２は、移動経路に沿った車両の現在位置を得ることができる。車両の現在位置は２次元（２Ｄ）車両の姿勢（例えば、少なくとも車両の位置の緯度及び経度）であることができる。現在観測可能な目印のセットは、例えば視覚的走行距離計測モジュール１１６によって、現在観測可能な目印のセットを撮像デバイス１２２及び３Ｄローカル地図から１つ以上の立体画像から抽出することにより図３と共に上述のように決定される。

次にブロック６０４を参照すると、本方法は調査目印ＤＢへの問合せを含み、車両の現在位置に対する調査済み目印のサブセットを特定する。例えば、一実施形態において、位置特定モジュール１１８は調査目印ＤＢ １２６への問合せを生成し、送信（及び／又は実行）する。問合せは車両の現在位置を含んでもよい。調査目印ＤＢ １２６は以前に記憶された調査済み目印のセット（例えば、図４の以前に記憶された調査済み目印４１７のセット）を含む。

一実施形態において、問合せを受信及び実行後、調査目印ＤＢ １２６は位置特定モジュール１１８、車両の現在位置に対する調査済み目印のサブセットに戻る。調査目印ＤＢ １２６は、一実施形態において、記述ファイルから読み取ったデータを用いて問合せを実行することができる。記述ファイルは以前に記憶された調査済み目印のセット内のそれぞれの目印の座標を含んでもよい。従って、それぞれの目印の座標は車両の現在位置と比較され、調査済み目印のサブセットを決定する。結果的に、調査済みの目印のサブセットは、調査目印ＤＢ ４１６に記憶された車両の現在位置に近い目印を含む。幾つかの実施形態において、位置特定モジュール１１８は調査目印ＤＢ ４１６から記述ファイルを読み取り、位置特定モジュール１１８で問合せを実行することができるということが理解される。

ブロック６０６で、本方法は、現在観測可能な目印のセットと調査済み目印のサブセットとの間において１つ以上の二次元変換推定を決定することを含む。１つ以上の二次元変換推定の決定は以下で図７と共により詳細に記述される。一実施形態において、姿勢補正モジュール１２０は、現在観測可能な目印のセットと調査済み目印のサブセットとの間における１つ以上の二次元変換を決定する。

更に、一実施形態において、ブロック６０８での方法は現在観測可能な目印のセットのそれぞれの目印の重心の決定を含む。調査済み目印のサブセットは、上述のように、調査済み目印のサブセット内のそれぞれの目印の重心も含む。例えば、上述のように、記述ファイル１３０及び／又はキーファイル１３２は調査済み目印のサブセット内のそれぞれの目印の重心の情報（例えば位置）を含んでもよい。

結果的に、一実施形態において、１つ以上の二次元変換推定の決定は、調査済み目印のサブセットのそれぞれの目印の重心及び現在観測可能な目印のセットのそれぞれの目印の重心を二次元に投影することを含む。例えば、上述のように、一実施形態において、目印の重心及び表面は例えばｚ座標を除去することにより２Ｄに投影される。これらの投影は目印セットのレイアウト及び構造を描写する目印シグネチャーとして定義されることができる。

ブロック６０８において、本方法は、１つ以上の二次元変換推定から最良の変換推定を特定することを含む。一実施形態において、最良の変換推定は現在観測可能な目印のセットと調査済み目印のサブセットとの間の距離を最小化する。別の実施形態において、最良の変換推定は現在観測可能な目印のセットと調査済み目印のサブセットとの間の対応する重心の距離を最小化する。

ブロック６１０で、本方法は、最良の変換推定に基づく車両の姿勢補正を含む。例えば、等式（３）と共に上述のように、最良の変換推定は車両現在位置、例えばブロック６０２で決定された移動経路に沿った車両の現在位置、に適用される。幾つかの実施形態において、車両の現在位置は２Ｄ姿勢である。図１のシステム１００においては、姿勢補正モジュール１２０は、最良の変換推定に基づいて車両の姿勢を補正する。

１つ以上の二次元変換推定の決定及び最良の変換推定の特定は、図７を参照し、これから詳細に記述される。図７は、１つの態様に従う、図６の１つ以上の二次元変換を決定するための例示的な方法の工程系統図である。図７は図１〜５の構成要素及び機能を参照し、記述される。

ブロック７０２で、及び上述のように、本方法は１つ以上の２Ｄ変換推定の決定を含む。一実施形態において、プロセッサ１０４は図６の方法における深さレベルＮのそれぞれの反復に対するカウンタｉを維持する。結果的に、ブロック７０２で、本方法はカウンタｉをインクリメントすることを含んでもよい。一実施形態において、１つ以上の二次元変換推定の決定は、深さＮにおける離散有界空間における、現在観測可能な目印のセットと調査済み目印のサブセットとの間の１つ以上の変換尺度での１つ以上の二次元変換推定を含む。図８Ａ〜８Ｆと共に上述のように、１つ以上の変換尺度は粗い変換尺度から細かい変換尺度へと向上する。

別の実施形態において、１つ以上の二次元変換推定の決定は、離散有界空間における、現在観測可能な目印のセットと調査済み目印のサブセットとの間の第１の変換尺度での１つ以上の二次元変換推定の決定を含む。第１の変換尺度は、上述のように、粗い尺度変換であることができる。更に、この実施形態において、１つ以上の二次元変換推定の決定は、離散有界空間における、現在観測可能な目印のセットと調査済み目印のサブセットとの間の第２の変換尺度での１つ以上の二次元変換推定の決定を含む。第２の変換尺度は以前の尺度（例えば第一の変換尺度）よりも詳細度の高い変換尺度である。

ブロック７０４で、本方法は深さレベルＫでの、１つ以上の２Ｄ変換推定のそれぞれに対する変換コストの決定を含む。更に、最良の変換推定は、深さレベルＫでの１つ以上の２Ｄ変換推定のそれぞれの変換コストに基づいて決定されることができる。上述のように、最良の変換推定は、一実施形態において、最低変換コストを有する２Ｄ変換推定であることができる。ブロック７０６で、離散有界検索空間は最良の変換推定の周囲の区域に修正される。幾つかの実施形態において、ブロック７０８で、ｉが深さレベルの最大数Ｋと同等かどうかが決定される。否の場合、本方法はブロック７０２に戻り、１つ以上の変換尺度での１つ以上の２Ｄ変換が次の深さレベルＫで決定される。

ブロック７０８での決定が可の場合、本方法はブロック７０９に進む。ブロック７０９で、本方法は、それぞれの深さレベルＮでの１つ以上の二次元変換推定の変換コストに基づくそれぞれの深さレベルでの最良の変換推定の分類リストを生成することを含む。図９Ａと共に上述のように、分類リストは最低から最高変換スコアへと分類されることができる。

分類リストは１つ以上のクラスタを決定するために繰り返される。具体的に、本方法は分類リスト内のそれぞれの最良の変換推定と分類リストの隣接する最良の変換推定との比較に基づく最良の変換推定の１つ以上のクラスタの決定を含む。より具体的には、ブロック７１０で、分類リスト内のそれぞれの最良の変換推定において、最良の変換推定が隣接する最良の変換推定と比較される（例えば、スコアｓはスコアｓ＋＋と比較される）。

ブロック７１２で、最良の変換推定と隣接する最良の変換推定の間の差が有意差（例えば差＞所定の数）であるかどうかが決定される。換言すれば、変換コストにおいて有意差があるとき（例えば２つの変換コストが５０％異なるとき）、新しいクラスタが指定される。従って、ブロック７１２での決定が可の場合、新しいクラスタがブロック７１４で生成される。幾つかの実施形態において、ブロック７１２で、クラスタの数を維持するためにプロセッサ１０４によってカウンタｃが維持される。ブロック７１２での決定が否の場合、本方法はブロック７１６へ続く。ブロック７１６は、分類リストの最後が到達されているかどうかが決定される。ブロック７１６での決定が否の場合、本方法はブロック７１０で分類リスト内で反復する。ブロック７１６での決定が可の場合、本方法は、ブロック７２０へと続く。

ブロック７２０で、本方法は、１つ以上のクラスタのそれぞれの最良の変換推定に基づく最良クラスタ変換推定を含む。図９Ａ及び９Ｂと共に上述されるように、クラスタは、その最良の推定に基づいてスコアを割り当てる。一実施形態において、最良の推定は、最低スコアを有するものである。従って、最良の変換推定（例えば、最良クラスタ変換推定）はそれぞれのクラスタの最良の変換推定に基づいて選択される。この最良クラスタ変換推定は車両に姿勢補正を適用するために使用することができる。例示の実施例としては、クラスタＡにおける最良推定がクラスタＢにおける最良推定よりも良い（例えば、低い）とき、クラスタＡはクラスタＢよりも良い。結果的に、最良クラスタ変換推定に基づいて、ブロック７１８で姿勢補正が適用される。

ＩＶ．例示的例
車両におけるマッピング、位置特定、及び姿勢補正のためのシステム及び方法を実装する例示的例がこれから記述される。図１０Ａは姿勢補正適用前の地図１０００の概略図である。ライン１００２は車両の視覚的走行距離計測システム、例えば視覚的走行距離計測モジュール１１６によって決定される移動経路を図示する。ライン１００４は実際に車両によって運転された移動経路（すなわち実際の経路）を図示する。上述のマッピング、位置特定、及び姿勢補正のための方法及びシステムを活用し、移動経路１００２及び移動経路１００４は車両の正確な移動経路を決定するために照合される。

図１０Ｂは図１０Ａの地図１０００の詳細図であり、実際の移動経路、ライン１００４に従い目撃された目印１００６を図示する。これらの目印１００６は現在観測可能な目印のセットである。図１０Ｃは図１０Ａの地図１０００の詳細図であり、視覚的走行距離計測システムによって決定された移動経路、ライン１００２に従い目撃された目印１００８を図示する。

図１１は地図１０００の図を図示し、車両の現在位置に対する調査済み目印のサブセットを特定するために調査目印データベース（例えば調査目印データベース１２６）において実行された問合せの結果を図示する。問合せの結果、調査済み目印のサブセットのそれぞれは図１１における角の丸い四角形で表される。

図１２Ａは、現在観測可能な目印１００６のセット（すなわち、図１０Ｂから）と調査済み目印のサブセット（例えば角の丸い四角形で表される）との間における１つ以上の２Ｄ変換の決定の例示の実施例である。図１２Ｂにおいて、最良の変換推定１０１４が選択される。図１２Ｃにおいて、図１０Ａの地図１０００に関して最良の変換推定が図示される。図１３において、最良の変換推定が車両の現在位置に適用され、新しい経路１０１２をもたらす。

本明細書内で記述される実施例は、非一過性コンピュータ可読メモリ媒体記憶コンピュータ実行可能命令との関連で記述及び実装され得る。非一過性コンピュータ可読メモリ媒体は、コンピュータメモリ媒体及び通信媒体を含む。例えば、フラッシュメモリドライブ、デジタル多用途ディスク（ＤＶＤ）、コンパクトディスク（ＣＤ）、フロッピー(登録商標)ディスク及びテープカセットである。非一過性コンピュータ可読メモリ媒体は、揮発性及び不揮発性、取り外し可能及び非取り外し可能な、情報記憶のためのあらゆる方法又は技術に実装される媒体、例えばコンピュータ可読命令、データ構造、モジュール、又は他のデータを含み得る。非一過性コンピュータ可読メモリ媒体は一過性及び伝搬されたデータ信号を排除する。

上で開示される種々の実装例、並びに他の特性及び機能、又はその代替案若しくは変形は、多くの他の異なるシステム又は適用に望ましく組み合わせられ得ることが理解されよう。又、種々の現在予期されていない、若しくは予想されていない代替案、修正、変形、又は改善が、後に当業者によって行われてもよく、それらも、以下の特許請求の範囲によって包含されるよう意図される。

１００ システム
１０２ コンピューティングデバイス
１０４ プロセッサ
１０６ メモリ
１０８ ディスク
１１０ 位置決定ユニット
１１２ 通信インターフェイス
１１４ バス
１１６ 視覚的走行距離計測モジュール
１１８ 位置特定モジュール
１２０ 姿勢補正モジュール

Claims (17)

1. 地図生成、位置特定、及び姿勢補正のためのコンピュータ実装方法であって、前記コンピュータに搭載されたプロセッサが、
   移動経路に沿った車両の現在位置及び前記現在位置に対して移動経路に沿った現在観測可能な目印のセットを決定する工程であって、前記現在観測可能な目印のセットが、撮像デバイスから得られた１つ以上の立体画像から抽出される、工程と、
   調査目印データベースに問い合わせて、前記車両の前記現在位置に対して調査済み目印のサブセットを特定する工程であって、前記調査目印データベースが、以前に記憶された調査済み目印のセットを含み、前記調査済み目印のサブセットは、前記以前に記憶された調査済み目印のセットの一部分である、工程と、
   前記現在観測可能な目印のセットのそれぞれの目印の重心を決定する工程であって、前記調査済み目印のサブセットが、前記調査済み目印のサブセットにおけるそれぞれの目印の重心を含む、工程と、
   前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間における１つ以上の二次元変換推定を決定する工程と、
   前記１つ以上の二次元変換推定から、前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間の距離を最小化する最良の変換推定を特定する工程と、
   前記最良の変換推定に基づいて前記車両の姿勢を補正する工程と、を実行する、コンピュータ実装方法。
2. １つ以上の二次元変換推定を決定する工程が、前記調査済み目印のサブセットのそれぞれの目印の重心及び前記現在観測可能な目印のセットのそれぞれの目印の重心を二次元に投影する工程を含む、請求項１に記載のコンピュータ実装方法。
3. 前記最良の変換推定が、前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間の対応する重心の距離を最小化する、請求項２に記載のコンピュータ実装方法。
4. 前記１つ以上の二次元変換推定を決定する工程が、深さレベルＮについての離散有界空間における、前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間の１つ以上の変換尺度での１つ以上の二次元変換推定を決定する工程を含む、請求項１に記載のコンピュータ実装方法。
5. 前記１つ以上の変換尺度が、粗い変換尺度から細かい変換尺度へと向上する、請求項４に記載のコンピュータ実装方法。
6. 前記プロセッサが、それぞれの深さレベルＮにおける１つ以上の二次元変換推定の変換コストに基づいてそれぞれの深さレベルＮにおいて最良の変換推定の分類リストを生成する工程をさらに実行する、請求項４に記載のコンピュータ実装方法。
7. 前記プロセッサが、前記分類リスト内のそれぞれの最良の変換推定と前記分類リスト内の隣接する最良の変換推定との比較に基づいて最良の変換推定の１つ以上のクラスタを決定する工程をさらに実行する、請求項６に記載のコンピュータ実装方法。
8. 前記プロセッサが、前記１つ以上のクラスタのそれぞれの前記最良の変換推定に基づいて最良クラスタ変換推定を決定する工程をさらに実行し、前記車両の姿勢を補正する工程が、前記最良クラスタ変換推定に基づく、請求項７に記載のコンピュータ実装方法。
9. 前記プロセッサが、前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間の１つ以上の変換尺度での１つ以上の二次元変換推定を決定する工程と、前記１つ以上の二次元変換推定のそれぞれの変換コストに基づいて１つ以上のクラスタを決定する工程と、前記１つ以上のクラスタから最良の変換推定を特定する工程と、をさらに実行する、請求項１に記載のコンピュータ実装方法。
10. 地図生成、位置特定、及び姿勢補正のためのシステムであって、
    プロセッサと、
    前記プロセッサが、移動経路に沿った車両の現在位置及び前記現在位置に対する移動経路に沿った現在観測可能な目印のセットを決定することをもたらし、前記現在観測可能な目印のセットが、前記プロセッサと通信可能に結合された撮像デバイスから得られた１つ以上の立体画像から抽出される、視覚的走行距離計測モジュールと、
    前記プロセッサが、前記プロセッサと通信可能に結合された調査目印データベースに問い合わせて、前記車両の前記現在位置に対する調査済み目印のサブセットを取得することをもたらし、前記調査目印データベースが、以前に記憶された調査済み目印のセットを含み、前記調査済み目印のサブセットは、前記以前に記憶された調査済み目印のセットの一部分である、位置特定モジュールと、
    前記プロセッサが、前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間の１つ以上の二次元変換推定を決定し、前記１つ以上の二次元変換推定から前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間の距離を最小化する最良の変換推定を特定し、前記最良の変換推定に基づいて前記車両の姿勢を補正することをもたらす、姿勢補正モジュールと、を含み、
    前記位置特定モジュールが、前記現在観測可能な目印のセットのそれぞれの目印の重心を決定し、前記調査済み目印のサブセットが前記調査済み目印のサブセットにおけるそれぞれの目印の重心を含む、
    システム。
11. 前記姿勢補正モジュールが、前記最良の変換推定を、前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間の対応する重心の距離を最小化する変換推定として特定する、請求項１０に記載のシステム。
12. 前記姿勢補正モジュールが、１つ以上の変換尺度での二次元尺度変換に基づいて前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間の変換推定のセットを決定し、前記１つ以上の変換尺度が、粗い変換尺度から細かい変換尺度へと向上する、請求項１０に記載のシステム。
13. 前記姿勢補正モジュールが、最良の変換推定の分類リストを生成し、前記変換推定のセットが、それぞれの推定の変換コストに基づいて、最良の変換推定の１つ以上のクラスタを決定する工程が、前記分類リストにおけるそれぞれの最良の変換推定と前記分類リストにおける隣接する最良の変換推定との比較に基づく、請求項１２に記載のシステム。
14. 前記姿勢補正モジュールが、前記１つ以上のクラスタのそれぞれの最良の変換推定に基づいて最良クラスタ変換推定を決定し、前記最良クラスタ変換推定に基づいて前記車両の姿勢を補正する、請求項１３に記載のシステム。
15. 非一過性コンピュータ可読記録媒体であって、
    プロセッサにより実行されたとき、地図生成、位置特定、及び姿勢補正のための方法を実行する、命令を含み、前記方法が、
    移動経路に沿った車両の現在位置及び前記現在位置に対する前記移動経路に沿った現在観測可能な目印のセットを決定する工程であって、前記現在観測可能な目印のセットが、撮像デバイスから得られた１つ以上の立体画像から抽出される、工程と、
    前記現在位置を特定する問合せに基づいて調査目印データベースから調査済み目印のサブセットを受信する工程であって、前記問合せが、前記調査目印データベースで実行され、前記調査目印データベースが、以前に記憶された調査済み目印のセットを含み、前記調査済み目印のサブセットは、前記以前に記憶された調査済み目印のセットの一部分である、工程と、
    前記現在観測可能な目印のセットのそれぞれの目印の重心を決定する工程であって、前記調査済み目印のサブセットが、前記調査済み目印のサブセットにおけるそれぞれの目印の重心を含む、工程と、
    前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間における１つ以上の二次元変換推定を決定する工程と、
    前記１つ以上の二次元変換推定から、前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間の距離を最小化する最良の変換推定を特定する工程と、
    前記最良の変換推定に基づいて前記車両の姿勢を補正する工程と、を含む、非一過性コンピュータ可読記録媒体。
16. 前記最良の変換推定が、前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間の対応する重心の距離を最小化する、請求項１５に記載の非一過性コンピュータ可読記録媒体。
17. 前記現在観測可能な目印のセットと前記調査済み目印のサブセットとの間の１つ以上の二次元変換推定が、１つ以上の深さレベルにおける１つ以上の変換尺度での１つ以上の二次元変換推定を決定する工程と、前記１つ以上の変換推定のそれぞれの変換コストに基づいて最良の変換推定を決定する工程と、を含む、請求項１５に記載の非一過性コンピュータ可読記録媒体。

Images