(57)【要約】  同時位置決め及びマッピング（ＳＬＡＭ）は、従来のシステムを止めてしまう外観変化があっても、多重視野特徴記述子を用いてロバストに位置を決めることができる。ＳＬＡＭアルゴリズムは、核主成分分析（ＫＰＣＡ）を用いて異なる視野からシーンに関する特徴記述子を生成する。ＳＬＡＭモジュールが広いベースライン変化の後に続けて認識画像の入力を受ける場合には、ＳＬＡＭモジュールは、特徴記述子を参照してマップ作成及び／又は位置決めを継続することができる。外観変化は、例えば、明るさの変化、部分的な隠れ、スケールの変化、向きの変化、距離の変化、歪み等から生じる。外観変化の後、動作由来構造モジュールは、特徴記述子を用いて自身を再設定し、拡張カルマンフィルタを用いてマップ作成を継続する。総合的な特徴記述子のデータベースの利用を通じて、ＳＬＡＭモジュールは、外観変化があっても、位置推定を改良することができる。
2007535765.tif 000002
【特許請求の範囲】
【請求項１】
広いベースラインをマッチングする方法であって、
連続する画像が漸増的な変化を有する画像シーケンスの入力を受けるステップと、
漸増的な変化に基づくトレーニング特徴記述子を生成するステップと、
前記トレーニング特徴記述子と前記画像シーケンスから得られる位置情報とを用いて前記画像特徴記述子により捕らえられたシーンのマップを生成するステップと、
前記画像シーケンスから、少なくとも最後の画像に関連する外観変化を含む認識画像の入力を受けるステップと、
前記認識画像から認識特徴記述子を抽出するステップと、
前記認識特徴記述子を前記トレーニング特徴記述子にマッチングし、前記マップ内に位置を決めるステップと、
を含むことを特徴とする方法。
【請求項２】
前記トレーニング特徴記述子を生成するステップが、
前記画像シーケンスから得られる複数の追跡点から追跡特徴を選択するステップと、
前記追跡点を前記画像シーケンス上にマッチングするステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記トレーニング特徴記述子を生成するステップが、
アフィン不変追跡部を用いて前記追跡特徴を選択するステップ
を含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記トレーニング特徴記述子を生成するステップが、
近似核主成分分析を用いて前記追跡特徴から前記追跡特徴記述子を作成するステップ
を含むことを特徴とする請求項２に記載の方法。
【請求項５】
前記マップを生成するステップが、
拡張カルマンフィルタを用いて三次元マップを生成するステップ
を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記トレーニング特徴記述子を記憶するステップ
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記認識特徴記述子を前記トレーニング特徴記述子にマッチングするステップが、
広いベースライン一致を通じて、前記認識特徴記述子を前記トレーニング特徴記述子にマッチングするステップ
を含むことを特徴とする請求項１に記載の方法。
【請求項８】
前記画像シーケンスの連続するメンバは、短いベースライン視点変化を示すことを特徴とする請求項１に記載の方法。
【請求項９】
前記認識特徴記述子を前記トレーニング特徴記述子にマッチングするステップが、
前記認識特徴記述子を前記トレーニング特徴記述子上に射影するステップと、
射影距離を算出するステップと、
前記射影距離が閾値未満であるか否かを判定するステップと、
を含むことを特徴とする請求項１に記載の方法。
【請求項１０】
初期位置と移動距離とに基づいて現在の位置を推定するステップと、
前記トレーニング特徴記述子と前記認識特徴記述子との間の差分に基づいてドリフトに対して前記推定を調節するステップと、
を含むことを特徴とする請求項１に記載の方法。
【請求項１１】
前記外観変化は、視点の変化、明るさの変化、スケールの変化、形状の変化及び隠れを含むグループのうちの少なくとも一つを含むことを特徴とする請求項１に記載の方法。
【請求項１２】
初期位置の入力を受けるステップ
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項１３】
前記シーンのマップを更新するステップ
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項１４】
同時位置決め及びマッピング方法であって、
連続する画像が漸増的なベースライン変化を有する画像シーケンスの入力を受けるステップと、
核主成分分析（ＫＰＣＡ）を用いて、前記ベースライン変化に基づくトレーニング特徴記述子を生成するステップと、
拡張カルマンフィルタと前記トレーニング特徴記述子と前記画像シーケンスから得られる位置情報とを用いて前記画像特徴記述子により捕らえられたシーンの三次元マップを生成するステップと、
前記画像シーケンスから、少なくとも最後の画像に関連して広いベースライン外観変化を含む認識画像の入力を受けるステップと、
前記認識画像から認識特徴記述子を抽出するステップと、
前記認識特徴記述子を前記トレーニング特徴記述子にマッチングするステップと、
前記マップ内に位置を決めるステップと、
を含むことを特徴とする方法。
【請求項１５】
広いベースラインをマッチングするシステムであって、
連続する画像が漸増的なベースライン変化を有する画像シーケンス内を追跡する追跡手段と、
認識画像の入力を受ける受信手段と、
前記追跡手段に連結され、前記漸増的なベースライン変化に基づくトレーニング特徴記述子を生成する記述手段と、
前記追跡手段に連結され、認識特徴記述子を前記トレーニング特徴記述子にマッチングするマッチング手段と、
前記追跡手段及び前記マッチング手段に連結され、前記画像シーケンスと、前記トレーニング特徴記述子を含む前記マップと、前記画像シーケンスから得られ、前記認識画像内の外観変化に関連する位置情報とにより捕らえられたシーンのマップを生成する、前記認識画像からシーンをマッピングするマッピング手段と、
前記マッピング手段及び前記マッチング手段に連結され、前記認識画像内の外観変化に応じて前記マップ内に位置を決める位置決め手段と、
を備えることを特徴とするシステム。
【請求項１６】
前記追跡手段は、前記画像シーケンスからの複数の追跡位置に基づいて追跡特徴を選択し、一以上の前記画像シーケンス間の追跡点をマッチングすることを特徴とする請求項１５に記載のシステム。
【請求項１７】
前記追跡手段は、アフィン不変追跡部を用いて前記追跡特徴を選択することを特徴とする請求項１６に記載のシステム。
【請求項１８】
前記記述手段は、近似核主成分分析を用いて疎データを有する前記トレーニング特徴記述子を生成することを特徴とする請求項１５に記載のシステム。
【請求項１９】
前記マッピング手段は、拡張カルマンフィルタを用いて三次元マップを生成することを特徴とする請求項１５に記載のシステム。
【請求項２０】
前記記述手段は、前記トレーニング特徴記述子を記憶する請求項１５に記載のシステム。
【請求項２１】
前記マッチング手段は、広いベースライン一致を通じて、前記認識特徴記述子を前記トレーニング特徴記述子にマッチングすることを特徴とする請求項１５に記載のシステム。
【請求項２２】
一の画像は、前の画像に対する短いベースライン視点変化を含むことを特徴とする請求項１５に記載のシステム。
【請求項２３】
前記マッチング手段は、前記認識特徴記述子を前記トレーニング特徴記述子上に射影し、射影距離を算出し、前記射影距離が閾値未満であるか否かを判定することを特徴とする請求項１５に記載のシステム。
【請求項２４】
前記位置決め手段は、初期位置と移動距離とに基づいて現在の位置を推定し、前記トレーニング特徴記述子と前記認識特徴記述子との間の差分に基づいてドリフトに対して前記推定を調節することを特徴とする請求項１５に記載のシステム。
【請求項２５】
前記外観変化は、視点の変化、明るさの変化、スケールの変化、形状の変化及び隠れを含むグループのうちの少なくとも一つを含むことを特徴とする請求項１５に記載のシステム。
【請求項２６】
前記位置決め手段は、初期位置の入力を受けることを特徴とする請求項１５に記載のシステム。
【請求項２７】
広いベースラインをマッチングする方法のために具現化されるコンピュータプログラム命令及びデータを有するコンピュータ読取可能な媒体を含むコンピュータプログラム製品であって、前記方法が、
連続する画像が漸増的な変化を有する画像シーケンスの入力を受けるステップと、
漸増的な変化に基づくトレーニング特徴記述子を生成するステップと、
前記トレーニング特徴記述子と前記画像シーケンスから得られる位置情報とを用いて前記画像特徴記述子により捕らえられたシーンのマップを生成するステップと、
前記画像シーケンスから、少なくとも最後の画像に関連して外観変化を含む認識画像の入力を受けるステップと、
前記認識画像から認識特徴記述子を抽出するステップと、
前記認識特徴記述子を前記トレーニング特徴記述子にマッチングし、前記マップ内に位置を決めるステップと、
を含むことを特徴とするコンピュータプログラム製品。
【請求項２８】
前記トレーニング特徴記述子を生成するステップが、
前記画像シーケンスから得られる複数の追跡点から追跡特徴を選択するステップと、
前記追跡点を前記画像シーケンス上にマッチングするステップと、
をさらに含むことを特徴とする請求項２７に記載のコンピュータプログラム製品。
【請求項２９】
前記トレーニング特徴記述子を生成するステップが、
アフィン不変追跡部を用いて前記追跡特徴を選択するステップ
を含むことを特徴とする請求項２８に記載のコンピュータプログラム製品。
【請求項３０】
前記トレーニング特徴記述子を生成するステップが、
近似核主成分分析を用いて前記追跡特徴から前記追跡特徴記述子を作成するステップ
を含むことを特徴とする請求項２７に記載のコンピュータプログラム製品。
【請求項３１】
前記マップを生成するステップが、
拡張カルマンフィルタを用いて三次元マップを生成するステップ
を含むことを特徴とする請求項２７に記載のコンピュータプログラム製品。
【請求項３２】
前記トレーニング特徴記述子を記憶するステップ
をさらに含むことを特徴とする請求項２７に記載のコンピュータプログラム製品。
【請求項３３】
前記認識特徴記述子を前記トレーニング特徴記述子にマッチングするステップが、
広いベースライン一致を通じて、前記認識特徴記述子を前記トレーニング特徴記述子にマッチングするステップ
を含むことを特徴とする請求項２７に記載のコンピュータプログラム製品。
【請求項３４】
前記画像シーケンスの連続するメンバは、短いベースライン視点変化を示すことを特徴とする請求項２７に記載のコンピュータプログラム製品。
【請求項３５】
前記認識特徴記述子を前記トレーニング特徴記述子にマッチングするステップが、
前記認識特徴記述子を前記トレーニング特徴記述子上に射影するステップと、
射影距離を算出するステップと、
前記射影距離が閾値未満であるか否かを判定するステップと、
を含むことを特徴とする請求項２７に記載のコンピュータプログラム製品。
【請求項３６】
初期位置と移動距離とに基づいて現在の位置を推定するステップと、
前記トレーニング特徴記述子と前記認識特徴記述子との間の差分に基づいてドリフトに対して前記推定を調節するステップと、
を含むことを特徴とする請求項２７に記載のコンピュータプログラム製品。
【請求項３７】
前記外観変化は、視点の変化、明るさの変化、スケールの変化、形状の変化及び隠れを含むグループのうちの少なくとも一つを含むことを特徴とする請求項２７に記載のコンピュータプログラム製品。
【請求項３８】
初期位置の入力を受けるステップ
をさらに含むことを特徴とする請求項２７に記載のコンピュータプログラム製品。
【請求項３９】
前記シーンのマップを更新するステップ
をさらに含むことを特徴とする請求項２７に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、合衆国法典（ＵＳＣ）第３５編１１９条（ｅ）の下、米国仮特許出願第６０／５６５，９９１号「多重視野特徴記述子を用いた同時位置決め及びマッピング」、及び、米国特許出願第１１／０２１，６７２号「多重視野特徴記述子を用いた同時位置決め及びマッピング」に基づいて優先権を主張するものであり、参照により本明細書中に組み込むものとする。
【０００２】
本発明は、一般的に画像処理に関し、より詳細には、外観変化の後に、続けてマップを生成してマップ内に位置を決定するためにビデオストリームからシーンの多重視野特徴記述子を生成することに関する。
【背景技術】
【０００３】
コンピュータビジョンは、無数の新たな可能性を提供するコンピュータ知能における偉大な一歩である。例えば、ロボット又は他の移動車両に取り付けられてその現在位置を決定するコンピュータの能力によって、ロボットは、その環境と自律的に相互作用することができる。動作中に位置を更新するため、いくつかのコンピュータは、ロボットが既知の位置からどれだけ遠くどの方向に移動したかを測定するために走行距離計測技術を用いる。しかし、このような技術は、障害物のない移動及び経時的に有意な移動を通じてのみ有効である。「連れ去られた」ロボットは、その新たな位置についての情報がないまま、ある位置から他へ移動する。ロボットが走行距離情報なしで自身を再設定することはできないので、もはや正確な位置決めを提供することはできない。したがって、いくつかのコンピュータは、トレーニングデータから新たな位置を認識して位置を推定するために画像処理技術を用いる。
【０００４】
問題なことに、従来の画像処理技術は、トレーニングデータを集めるためにシーンの単一視野を用いている。より詳細には、これらの従来のシステムは、認識中のパターンマッチングのための情報を集めるためにトレーニング中の三次元（３−Ｄ）シーンの二次元（２−Ｄ）画像を用いている。しかし、３−Ｄシーンは、画像が取得された視点、明るさ、隠れ等の様々な因子によって２−Ｄ画像では様々な外観を有する。したがって、一つの外観を有するシーンのトレーニングデータを用いた従来の技術は、外観変化を通じて同一シーンを認識する点で困難性を有している。ある程度のばらつきを許容するシステムであっても、小さいベースライン変化の許容に限定され、大きいベースライン変化に対しては役に立たない。一般的に、小さいベースライン変化は、小さい角度のオフセット又はわずかに異なるスケール等のわずかな変化であり、大きいベースライン変化は、極端な場合には、１８０度変化又はサイズの倍化である。
【０００５】
残念なことに、従来の画像処理技術は、正確な位置情報なしでは同時位置決め及びマップ作成（ＳＬＡＭ）等のアプリケーションを支援することができない。ロボットは、環境内の自身の位置を決定している間に未知の環境のマップを作成するためにＳＬＡＭを実行する。位置データが入手不可能な場合には、ロボットは、ナビゲーション等の位置に依存した双方向性又は自律した行動を実行することができない。さらに、ロボットは、環境の統一されたマップを作成し続けることができない。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
それゆえ、ＳＬＡＭ等のアプリケーションにおける認識のために多重視野特徴記述子を用いたロバストな画像処理技術が必要とされている。さらに、システムは、ＳＬＡＭ動作中にすでに入手されたビデオデータを用いて疎データから特徴記述子を生成すべきである。
【課題を解決するための手段】
【０００７】
本発明は、多重視野特徴記述子を用いた同時位置決め及びマッピング（ＳＬＡＭ）のためのシステム、方法及びコンピュータ製品を用いてこれらの必要性を満たす。本システムは、従来技術のシステムを止めてしまう外観変化があっても、ＳＬＡＭ動作を実行し続ける。したがって、このシステムは、トレーニングのための位置決め及び／又はマッピング中に既に入手されたデータを用いて必要な特徴記述子を効率的に作成することができる。
【０００８】
一実施形態において、ＳＬＡＭモジュールは、未知の環境内のマップを作成するためにカメラからビデオストリームの入力を受け、同時に、マップ内における現在位置の追跡を継続する。ビデオストリームに基づいて、ＳＬＡＭモジュールは、異なる視野からシーンに関する特徴記述子を生成する。特徴記述子は、追跡点の小さいベースライン変化の集合からの情報、カメラ動作に起因する変化又はオブジェクトの外観の変化を含む。
【０００９】
ＳＬＡＭモジュールが広いベースライン変化の後に続けて認識画像の入力を受ける場合には、ＳＬＡＭモジュールは、特徴記述子からの一致を参照し、マップ作成及び／又は位置決めを継続することができる。これらの外観変化は、例えば、明るさ、スケールの変化、向きの変化、距離の変化、部分的な隠れ、形状変化（例えば、歪み）等から生じる。一例において、広いベースライン変化に達する程度にある位置から他の位置へ手動で移動された「連れ去られた」ロボットは、特徴記述子からその新たな位置を生成することができる。
【００１０】
ＳＬＡＭモジュールは、まず、特徴記述子を作成しなければならない。一実施形態において、ＳＬＡＭモジュールの特徴追跡モジュールは、ビデオストリームの個別の画像内のどの点を追跡するかを決定する。特徴追跡モジュールは、追跡された点に基づいて画像パッチを生成する。その特徴は、個別の画像間の小さいベースライン変化を有するので、特徴追跡モジュールは、外観変化があっても、追跡された点に確実に対応することができる。このことの説明は、J. Shi and C. Tomasi, "Good Features to Track," IEEE CVPR, 1994に開示されている。さらに他の実施形態において、ＳＬＡＭモジュールの特徴記述モジュールは、これらの追跡された点の多重視野画像記述を含む特徴記述子を生成する。ビデオストリーム内の小さいベースライン変化は、それぞれ例えば核主成分分析（ＫＰＣＡ）を用いて単一の特徴記述子に追加されてより情報量の多い表現を産み出す。一実施形態は、近似ＫＰＣＡを用いて効率的に特徴記述子を作成し、計算の複雑さを低減し、より疎なデータを出力することができる。このことの説明は、J. Meltzer, M. H. Yang, R. Gupta and S. Soatto, "Multiple View Feature Descriptors from Image Sequences via Kernel Principal Component Analysis," European Conference on Computer Vision (ECCV), May 11-14, 2004, Prague, Czech Republicに開示されている。
【００１１】
ＳＬＡＭモジュールは、特徴記述子を用いて、マッピングして自身を位置決めする。一実施形態において、動作由来構造モジュールは、例えば拡張カルマンフィルタを用いてビデオストリームの二次元（２−Ｄ）画像から三次元（３−Ｄ）マップを作成する。このことの説明は、A. Chiuso, P. Favaro, H. Jin and S. Soatto, "Structure from Motion Causally Integrated over Time," IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 24, No 4, April 2002に開示されている。外観変化の後、動作由来構造モジュールは、自身の位置を再設定するために特徴記述子を用いてマップ作成を継続する。他の実施形態において、動作由来構造モジュールは、特徴記述子を位置推定のための一般的な目印として用いる。総合的な特徴記述子のデータベースを有することにより、動作由来構造モジュールは、外観変化があっても、特徴記述子の既知の位置に基づいて自身の位置推定を調節することができる。
【００１２】
この要約及び以下の詳細な説明に記載された特徴及び利点は、全てを包括するものではなく、より詳細には、多くの追加的な特徴及び利点が、以下の図面、明細書及び特許請求の範囲を考慮することにより、当業者にとって明らかになるであろう。さらに、明細書に用いられている言語は、読みやすさ及び説明を目的として選択されており、発明の主題を線引き又は制限するために選択されたものではなく、このような発明の主題を決定するためには特許請求の範囲を用いる必要があることに留意されたい。
【発明を実施するための最良の形態】
【００１３】
多重視野特徴記述子を用いた同時位置決め及びマッピング（ＳＬＡＭ）のためのシステム、方法及びコンピュータ製品が開示される。システムのいくつかの実施形態が図１，２に説明されており、そのシステム内で行われる方法のいくつかの実施形態が図３〜５に説明されている。付随する説明は、多くの特定の細部とともに完全な説明を提供するためのものである。もちろん、画像処理及びＳＬＡＭの分野では、本発明に説明される特徴の様々な変化が可能である。当業者は、以下に説明されるいくつかの特定の細部なしでも本発明が実施可能であること、及び、本発明の多くの変形及び実施形態は本発明の教示及び精神を満たしつつ実施可能であることを確実に理解するであろう。したがって、本発明は、以下に記載される特定の実施に限定されたものとして理解されてはならず、以下の特許請求の範囲により理解されるべきである。
【００１４】
本発明の処理、特徴又は機能は、以下に記載される好適なコンピュータ機器内で実行するプログラム命令により実行されることが可能である。プログラム命令は、コンピュータ読取可能な媒体上で、半導体機器内で又は公共ネットワークを介して配信可能である。プログラム命令は、ソースコード、オブジェクトコード又はスクリプトのような好適な形態とすることができる。
【００１５】
図１は、本発明の一実施形態に係るＳＬＡＭシステム１００を説明するための図である。システム１００は、例えば、移動ロボット、自動車、自律装置、パーソナルコンピュータ又はコンピュータ環境を備えている。移動ロボットの例において、システム１００は、未知の環境を移動すると同時にそのマップ内における現在位置を追跡し続けることによってマップを作成することにより、自身をトレーニングすることができる。「連れ去られた」ロボットは、ロボットがある位置から他へ移動したときに発生する。この場合には、システム１００は、トレーニングから特徴記述子を用いてその新たな位置を決定し、マップ作成を続けることができる。システム１００は、バスに結合された処理装置、記憶装置、データ記憶装置等の従来の計算要素を備えている。一実施形態において、計算要素は、限定的な処理及び／又は記憶リソースを有する。
【００１６】
図１のシステム１００の例において、カメラ１０５は、その周囲のビデオストリームの入力を受ける。カメラ１０５は、単眼又はステレオ視野を提供することができる。カメラ１０５は、例えば、ロボットの眼、照合用カメラ、監視カメラ又は画像シーケンスを生成可能なカメラである。ビデオストリームは、画像処理間の記憶のための入出力バッファ１１０に入力される。入出力バッファ１１０は、ＲＡＭ、ハードドライブ、フラッシュメモリ等の記憶装置又はその一部である。ＳＬＡＭモジュール１２０は、システム１００の位置を決定するための位置決め及び／又はシーンの三次元（３−Ｄ）モデルを作成するためのマップ作成を実行する。特定のアプリケーションに応じて、位置ロジック１３０は、位置に基づく決定を行う。例えば、位置ロジック１３０は、システム１００が障害物に近づくのに応じて動作を止めたり、双方向的な及び／又は自律した動作を実行したりすることができる。
【００１７】
一実施形態において、ＳＬＡＭモジュール１２０は、入力されたビデオストリーム内の複数の画像に基づいて画像のシーンに関する多重視野特徴記述子を生成する（図５（ａ）参照）。特徴記述子は、カメラモーションから生じる追跡される点の小さいベースライン変化の集合及び／又はオブジェクトの外観の変化を含む。ＳＬＡＭモジュール１２０が大きなベースラインの変化の後に順次認識画像の入力を受けるときには（図５（ｂ）参照）、ＳＬＡＭモジュール１２０は、特徴記述子を参照してその位置を決定してマップ作成を継続することができる。対照的に、単一視野記述子を用いた従来の技術は、２０度より大きい又は小さい視野方向の変化等の変動により新たな記述子を生成しなければならない。したがって、これらのシステムは、同等又はより大きい変動の後には同一のシーンを認識することはできない。
【００１８】
図２は、本発明の一実施形態に係るＳＬＡＭモジュールを説明するためのブロック図である。ＳＬＡＭモジュール１２０は、位置決め及びマップ作成間にすでに入手可能なデータから特徴記述子を効率的に生成する。従来の技術のようにこのデータを捨てる代わりに、ＳＬＡＭモジュール１２０は、追加の視野を用いて特徴記述子を継続的に増やすことにより、システム１００の性能を改善する。
【００１９】
一実施形態において、ＳＬＡＭモジュール１２０内の特徴追跡モジュール２１０は、ビデオストリームの個別の画像内のどの点を追跡するかを決定する。特徴追跡モジュール２１０は、追跡された点に基づいて画像パッチを生成する。特徴は、個別の画像間の小さいベースライン変化を有するので、特徴追跡モジュール２１０は、追跡された点を確実に関連付けることができる。一般的に、小さいベースラインの変化は、小さい角度のオフセット又はわずかに異なるスケール等のわずかな変化であり、大きいベースラインの変化は、小さいベースラインの変化を超えたところから１８０度までの角度変化の範囲である。特徴追跡モジュール２１０は、Ｓｈｉ−Ｔｏｍａｓｉ追跡部、Ｌｕｃａｓ−Ｋａｎａｄｅ追跡部等の並進不変追跡部、他の候補点を推定する一致特徴選択及び追跡部等のアフィン不変追跡部である。Ｓｈｉ−Ｔｏｍａｓｉ追跡部に関する言及は前記されており、Ｌｕｃａｓ−Ｋａｎａｄｅ追跡部の議論は、C. Tomasi, T. Kanade,“Detection and tracking of point features”,Tech. Rept. CMU-CS-91132. Pittsburgh: Carnegie Mellon U. School of Computer Science, 1991に見られ、参照によりその全体が本明細書に組み込まれる。一実施形態において、特徴追跡モジュール２１０を用いるよりも、ＳＬＡＭモジュール１２０が走行距離計測法等の他の手法を用いて画像を分析する。
【００２０】
他の実施形態において、ＳＬＡＭ１２０内の特徴記述モジュール２２０は、追跡された点の多重視野特徴記述を含む特徴記述子を生成及び／又は増やす。特徴記述モジュール２２０は、既存の記述子に対して新たな画像内の画像パッチをマッチングする。小さいベースラインの変化は、それぞれ単一の特徴記述子に付け加えられて、例えば、高次元空間におけるカーネル主成分分析（ＫＰＣＡ）を用いてより情報量の多い表現を生成することができる。一般的に、ＫＰＣＡは、非線形特徴抽出を提供するＰＣＡのカーネル化されたバージョンである。分類器又は線形関数が、入力空間から特徴空間Ｆにマッピングされたデータに適用可能である。
【００２１】
一実施形態において、動作由来構造モジュール２３０は、例えば、拡張カルマンフィルタを用いてビデオストリームの２−Ｄ画像から３−Ｄマップを作成する。マップ作成は、特徴記述子に関する位置情報を含む。外観変化後には、動作由来構造モジュール２３０は、特徴記述子を用いて自身の位置を再設定し、マップ作成を続ける。他の実施形態において、動作由来構造モジュール２３０は、特徴記述子を推定位置に関する一般的な目印として用いる。総合的な特徴記述子のデータベースを有することにより、動作由来構造モジュール２３０は、外観変化があっても特徴記述子の既知の位置に基づいて自身の位置推定を調節することができる。いくつかの実施形態はＳＬＡＭに関して構成されたシステム１００における使用のために記載されているが、他の実施形態は位置決め及びマップ作成を非同時に実行し、又は、ＳＬＡＭ動作の一部であり、又は、他の位置に基づくアプリケーションであることに留意されたい。
【００２２】
図３は、本発明の一実施形態に係るＳＬＡＭの方法３００を説明するためのフローチャートである。ハイレベルでは、システム１００は、二つのモード：トレーニング３１０，３２０及びテスト３４０，３５０を実行することが望ましい。トレーニングモード中に、システム１００は、位置決め及びマップ形成のためのデータを集め、そのデータを用いて一番目のビデオストリームから特徴記述子を生成し、テストモード中に、システム１００は、第一のビデオストリームと特徴記述子から与えられた画像との間の一致を見つけ出し、システム１００が位置決め及びマップ作成を続けることができるようにする（例えば、後記する図５（ａ）と図５（ｂ）との間）。しかし、システム１００はトレーニング段階から取得されたデータの代わりに用いる、テストのための既存のデータを備えることも可能であることに留意されたい。一実施形態において、位置ロジック１３０は、前記した位置に応答して追加の動作セットを実行する。
【００２３】
入出力バッファ２１０は、カメラ１０５から入力されたビデオストリームを受信する（３１０）。一実施形態において、システム１００は、ビデオストリームに前処理を施して、サイズ、色、又は他の処理に有益な特徴を調節する。ビデオストリームは、システム１００の周囲のシーンを捕らえた画像のシーケンスを含む。一実施形態において、カメラ１０５は可動であるか、又は可動な台に設置されている。結果として、画像は、動作と一致する、スケール、向きのような漸増する変化量を有する。さらに、フレームは、明るさ、隠れ、歪み又は動作以外の他の外観変化の変化量により変化可能である。好ましくは、ビデオストリーム率は（例えば、３０フィート／秒（ｆｐｓ）又は６０ｆｐｓ）、うまく追跡を行うのに十分な小ささであるフレーム内変化量を含む。ビデオストリームの解像度は、処理能力又は所望のシステム性能に応じて変化可能である。
【００２４】
ＳＬＡＭモジュール１２０は、ビデオストリームにマッチングする小さいベースラインを用いて多重視野から特徴記述子を生成する（３２０）。図４の詳細フローチャートは、本発明の一実施形態に係る、小さいベースラインを用いて特徴記述子を生成する方法（３２０）を説明している。一般的に、特徴記述子モジュール２２０は、既存の特徴記述子にマッチングするための画像から特徴を抽出する。
【００２５】
図４において、特徴追跡モジュール２１０は、入力されたビデオストリームから特徴を追跡する（４１０）。単一の画像において、特徴追跡モジュール２１０は、画像のスケール空間内で極値を探索することにより確実に検出可能であり、隣接画像と比較して局所的な点の対応関係を求めることが可能な画像位置を求めることができる。例えば、スケール不変特徴変換は、一次元スケール空間内のスケールを超える極値を探索する等方性ガウススケール空間を考慮する。ガウスの微分方程式は、スケール空間錐内の隣接する滑らかなガウシアン画像の差分をとることにより算出される。極値は、一旦、スケール空間錐の近傍の極大及び極小を求めることにより位置付けられると、安定性のためにフィルタリングされ、基準となる向き、スケール及びローカルウィンドウの勾配の向きから得られる記述子が指定される。
【００２６】
特徴追跡モジュール２１０は、以下に説明する各特徴のトレーニングシーケンス又は近似ＫＰＣＡから得られる低減されたトレーニングセット上の核（例えば、ガウス核）を用いてＫＰＣＡを実行する（４２０）。一実施形態において、特徴記述モジュール２２０は、ＫＰＣＡを用いることにより、非線形マップによる入力Φ：ＲＮ→Ｆに対し、高次元空間の特徴記述子Ｆを生成する。ｙ∈ＲＮが画像パッチにベクトル化される場合には、Ｙ∈ＦはＦにマッピングされた画像パッチである。
【００２７】
【数１】
2007535765.tif 000003
と仮定すると、Ｆに関する共分散行列は、
【数２】
2007535765.tif 000004
である。ここで、Ｍは、画像パッチの数である。そして、Ｃ’は、特徴空間Ｆ内の射影標本である。Ｃ’を対角化することにより、核主成分（ＫＰＣ）の基底が求められる。近似核関数＜Φ（ｘ），Φ（ｙ）＞，ｘ，ｙ∈ＲＮを用いると、高次元空間Ｆの内積を算出する必要がない。ＫＰＣは、入力（画像パッチ）ｙ、核ｋ及び線形係数βに関して、暗示的に
【数３】
2007535765.tif 000005
として表される。
【００２８】
したがって、ＫＰＣＡは、非線形多様体から生成されたデータ点に関して好適に実行されず、エッジ又は曲線のピクセル間の非線形関係を含む高次の統計を無視するというＰＣＡの欠点を克服している。
【００２９】
特徴追跡モジュール２１０は、各特徴の元の基底から画像パッチの近似値を求める（４３０）。一実施形態において、近似ＫＰＣＡは、コンパクトな表現を生じるので、算出の複雑さを低減させるという利点を有する。分類を実行するために入力されたベクトル（画像パッチ）の全てを記憶するよりも寧ろ、ＫＰＣＡは、高次元空間のコンパクトな表現のための拡張係数及び核関数とともに固定された数の画像パッチを生成する。空間Ｆ内のベクトルΨが与えられると、システムは、近似値
【数４】
2007535765.tif 000006
を求める。ΨとそのΦ（ｚ）への射影差要素との間の距離を最小化すること、すなわち、換言すると
【数５】
2007535765.tif 000007
を最大化することが十分条件である。このことは、
【数６】
2007535765.tif 000008
を用いた反復手法で選択されたガウス核を完成させることができる。特徴追跡モジュール１２０は、高次元空間の元の基底の最小残余推定値を導き出す近似パッチを求めることにより各特徴に関する近似基底を形成する。続いて、特徴記述モジュール２２０は、近似画像パッチを既存の特徴記述子にマッチングさせる（４４０）。見本画像ｙから得られるパッチと、学習された記述子基底Ψｉとが与えられると、距離測定値
【数７】
2007535765.tif 000009
が閾値未満である場合に、システムは、マッチングしていると判定することができる。この式は内積に関してのみ記載されているので、核関数は、マッチングスコアを算出するために利用可能である。このように、特徴記述モジュール２２０は、間接的にモデルに由来する不変性よりも、ビデオストリームのデータから直接的に画像の多様性を学習する。
【００３０】
図３を再び参照すると、普通の動作下では、システム１００は、トレーニング段階によってマップ作成を継続する。しかし、ある場合には、シーンは、外観変化を経験する（３３０）。「連れ去られた」ロボットの例では、ロボットが新たな位置に移動されると、オブジェクトはスケール又は向きの変化（軸回転）を経験する。例えば、カメラ１０５は、半分の距離で、立方体の左側面を視てから立方体の右側面を視るまで移動することができる。図５（ａ）〜（ｂ）の説明は、小さいベースライン変化を経験する特徴５１０を含むビデオストリームの例を示す。ＫＰＣＡ５２０を用いて、特徴記述子５３０は、前記したように小さいベースライン変化から作成される。しかし、認識画像５４０は、広いベースライン変化の後、同一の特徴を示す。他の例において、移動するオブジェクトは、オブジェクトを隠したり、部分的にブロックしたりする。さらに他の例において、部屋のライトの点灯／消灯は、オブジェクトの明るさを変化させる。さらに他の例において、オブジェクト自身が歪みにより変化する。一実施形態において、広いベースライン外観変化は、特徴追跡モジュール２１０が所望の点を追跡するのを邪魔するのに十分な大きさの変化を含む（例えば、２０度の視野角度の変化）。
【００３１】
外観変化は、画像の領域（視点の変化及び／又はシーンのデフォルメによる形状歪み）及びその範囲（明るさの変化、均等拡散反射からの偏差）の両方に影響する。特徴は、画像の統計量であり、Φ：Ｉ→Ｒｋは、対応処理を容易にする。特徴統計量は、妨害因子（例えば、画像ノイズ）に対して不変であることが望ましい。このことは、Vladimir N. Vapnik, Statistical Learning Theory, Chapter 6, John Wiley and Sons, 1998に開示されており、これを本明細書に組み込むものとする。すなわち、外観のとりうる変化（例えば、異なる明るさ条件下、視野角度、デフォルメ等）に対応するために、単一ではなく多くのトレーニング画像のセットを含むことが問題である。これは、均等なシーンであっても、不変の単一視野統計では不可能である。一連の平面パッチは、拡散及び鏡面反射モジュールに従う放射輝度密度をサポートする。対応する視野の集団のランクは、均等アルベド又は光源の反射を見るのに十分小さいパッチに関して制限される。このことは、Computer Vision: A Modern Approach, by David Forsyth and Jean Ponce, Prentice Hall, 2003に開示されており、これを本明細書に組み込むものとする。多重視野記述子は、画像のデフォルメされたバージョンの好適な内積におけるランク制約により表現可能である。
【００３２】
図３を再び参照すると、テスト段階において、ＳＬＡＭモジュール１２０は、認識画像の入力を受ける（３４０）。認識画像は、先行ビデオストリームに対応する広いベースライン変化に達する外観変化を含む。
【００３３】
特徴記述モジュール２２０は、認識画像上を既存の特徴記述子に対してベースラインマッチングを行う（３５０）。このために、特徴追跡モジュール２１０は、前記した方法を用いて初期特徴を求める。アフィン追跡において、特徴記述モジュール２２０は、各候補点の近傍におけるアフィンワープを実行し、この点を取り囲むパッチとトレーニング段階で記憶された記述子との間の相違の最小化を図る。閾値距離未満の画像パッチは、マッチングの候補として選択される。広いベースライン一致の候補のセットが与えられると、システムは、カメラの現在座標をトレーニング段階で用いられる元の参照フレームの座標にマッピングするリジッドな変換を描写する原理又は本質的な基盤を見出す標準技術を用いて位置決めすることができる。このことは、P.H.S. Torr and A. Zisserman. MLESAC: A New Robust Estimator with Application to Estimating Image Geometry, Journal of Computer Vision and Image Understanding, 2000に開示されており、これを本明細書に組み込むものとする。
【００３４】
前記した説明は、好適な実施形態を実施するために収録されたものであり、本発明の範囲を限定するものではない。本発明の範囲は、以下の特許請求の範囲によってのみ限定される。
【図面の簡単な説明】
【００３５】
【図１】本発明の一実施形態に係る、同時位置決め及びマッピング（ＳＬＡＭ）を説明するブロック図である。
【図２】本発明の一実施形態に係るＳＬＡＭモジュールを説明するブロック図である。
【図３】本発明の一実施形態に係るＳＬＡＭの方法を説明するフローチャートである。
【図４】本発明の一実施形態に係る特徴記述子を生成する方法を説明するフローチャートである。
【図５】小さいベースライン変化と広いベースライン変化との両方を含むビデオストリームの例を説明する図である。
【図１】
2007535765.tif 000010
【図２】
2007535765.tif 000011
【図３】
2007535765.tif 000012
【図４】
2007535765.tif 000013
【図５】
2007535765.tif 000014