(57)【特許請求の範囲】
【請求項１】
カメラの位置特定、および前記カメラが内部を移動して画像を形成する静的環境の３Ｄ再構築を行う方法であって、前記環境が、３Ｄモデルが既知の関心対象物体と、前記物体の外部の未知である環境とを含み、前記方法が、以下のステップ
−ａ／前記環境内での前記カメラの初期姿勢および初期再構築の計算、
−ｂ／前記環境の３Ｄプリミティブと前記画像の２Ｄプリミティブとのマッチングによる各新規画像に対する前記カメラの姿勢の計算、および三角測量による前記環境の３Ｄプリミティブの再構築、
−ｃ／複数の画像にわたり再射影誤差を最小化することによる前記カメラの姿勢および前記３Ｄプリミティブの同時最適化を含み、
前記３Ｄモデルが前記関心対象物体の幾何学的記述であること、前記再射影誤差が２種類の項、即ち前記３Ｄモデルにより制約されるプリミティブに紐付けられた第１の種類の項および前記物体以外の前記環境のプリミティブに紐付けられた第２の種類の項のみを含むこと、および前記最適化ステップがプリミティブを前記環境または前記３Ｄモデルに関連付けるサブステップ
を含むことを特徴とする方法。
【請求項２】
前記最適化ステップが、拒否閾値を示す強靭な推定子を用いて、各種の項の影響を前記拒否閾値の関数として適応制御することにより実行されることを特徴とする、請求項１に記載のカメラの位置特定および前記環境の前記３Ｄ再構築を行う方法。
【請求項３】
前記再射影誤差の各種の項が前記強靭な推定子の前記拒否閾値に紐付けられた拒否閾値に関連付けられていて、前記２個の拒否閾値（ｃ１、ｃ２）が前記３Ｄモデルに基づいて残余に対して推定された前記推定子の前記拒否閾値に等しいことを特徴とする、請求項２に記載のカメラの位置特定および環境の３Ｄ再構築を行う方法。
【請求項４】
前記初期姿勢の計算が、前記物体の前記基準フレームの前記平面の一つに配置されたサイズが既知の目標により半自動的に実行することができ、目標は前記平面の間に配置された３Ｄプリミティブの組であって前記画像内で識別可能であること、および前記初期再構築が前記モデルへの前記２Ｄプリミティブの逆射影により得られることを特徴とする、請求項１〜３のいずれか１項に記載のカメラの位置特定および環境の３Ｄ再構築を行う方法。
【請求項５】
各新規画像に対する前記カメラの姿勢を計算するステップが、前記３Ｄモデルにより制約されるプリミティブ、および前記物体以外の環境のプリミティブに基づいて実行されることを特徴とする、請求項１〜４のいずれか１項に記載のカメラの位置特定および環境の３Ｄ再構築を行う方法。
【請求項６】
前記最適化ステップに続いて、前記プリミティブが前記３Ｄモデルにより制約されない三角測量ステップを実行することを特徴とする、請求項１〜５のいずれか１項に記載のカメラの位置特定および環境の３Ｄ再構築を行う方法。
【請求項７】
前記最適化および／または３Ｄ再構築ステップが、現在画像と最終キー画像との間で合致したプリミティブの個数が最小値より小さい場合に選択されたキー画像に対してのみ実行されることを特徴とする、請求項１〜６のいずれか１項に記載のカメラの位置特定および環境の３Ｄ再構築を行う方法。
【請求項８】
前記最適化ステップが、局所バンドル調整により実行されることを特徴とする、請求項１〜７のいずれか１項に記載のカメラの位置特定および環境の３Ｄ再構築を行う方法。
【請求項９】
前記画像がリアルタイムビデオストリームから、および予め記録されたビデオから得られることを特徴とする、請求項１〜８のいずれか１項に記載のカメラの位置特定および環境の３Ｄ再構築を行う方法。
【請求項１０】
前記関心対象物体が、特定の画像内で視認不可能であるか、または画像毎に変更されていることを特徴とする、請求項１〜９のいずれか１項に記載のカメラの位置特定および環境の３Ｄ再構築を行う方法。
【請求項１１】
前記３Ｄモデルにより制約される前記プリミティブが、前記物体にテクスチャが有るおよび／またはテクスチャが無いのいずれかの関数として選択されることを特徴とする、請求項１〜１０のいずれか１項に記載のカメラの位置特定および環境の３Ｄ再構築を行う方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の分野は、部分的に既知の環境の３Ｄ再構築、および当該環境内で移動しているカメラの視認による位置特定である。「部分的に既知の環境」という表現は、３Ｄ幾何学的モデルが既知である関心対象物体を含む環境を意味し、当該物体の外部環境は未知であるものと理解されたい。
【背景技術】
【０００２】
カメラの軌跡の推定は特に、現実のシーンのデジタル画像の仮想物体をマージする拡張現実アプリケーションで用いられる。単一のカメラを用いる拡張現実システムにおける主な難点は、現実的なマージを得るために如何にして現実のシーン（または現実の環境）と３Ｄ仮想情報の間の３Ｄレジストレーションを可能な限り正確に推定するかである。この３Ｄレジストレーションには、任意の時点でのカメラのポーズ、即ちシーンで固定された基準フレームに対するカメラの位置および向きを決定することを伴う。
【０００３】
３Ｄシーンに対するカメラのポーズの推定は極めて活発な研究テーマである。
【０００４】
特に３Ｄ物体を追跡する既存の方法の大多数は、関心対象物体のシーンの既知の部分、この場合は３Ｄモデル化された部分だけを考慮する。これらの方法のうち、モデルに基づく方法即ち「モデルに基づく追跡」と、学習に基づく方法は区別することができる。
【０００５】
モデルに基づく方法は、カメラにより取得された画像の各々について、射影された３Ｄモデルのエッジと画像内で検出されたエッジとの距離を最小化することによりカメラの６個の姿勢パラメータを計算するものである。そのような方法の一例がＶｉｎｃｅｎｔ  ＬｅｐｔｉｔおよびＰａｓｃａｌ  Ｆｕａが発表した「Ｍｏｎｏｃｕｌａｒ  Ｍｏｄｅｌ−ｂａｓｅｄ  ３ｄ  ｔｒａｃｋｉｎｇ  ｏｆ  ｒｉｇｉｄ  ｏｂｊｅｃｔｓ：Ａ  ｓｕｒｖｅｙ」（ＦＴＣＧＶ，２００５）に記述されている。これらの方法の主な制約は、物体が画像のシーケンス内で常時視認可能な場合にしか機能しない点である。正確な姿勢を得るためには、関心対象物体が画像の主要な部分を占める、換言すれば、カメラに「近い」ことも必要である。更に、確実に３Ｄを追跡できるようにカメラの移動は少なくなければならない。
【０００６】
学習に基づく方法は、物体の測光アスペクト（即ち外観）の学習からなる、いわゆる事前学習フェーズを必要とする。このフェーズは、画像から抽出されたテクスチャ記述子により物体の３Ｄモデルを補足することにある。以下の２種類の学習が可能である。
−数個の視点についてカメラの姿勢を推定するために既知の位置の符号化マーカーを物体の周辺に配置する。符号化マーカー（符号化目標とも称する）とは、画像内で容易に検出されて自身の符号により識別可能な既知のサイズの光学マーカーである。これらの視点の各々について、関心対象の点が画像から抽出されて周辺のテクスチャにより特徴付けられ、次いで、符号化目標によりこれらの視点の各々について既知であるカメラの視点からの単一の射影により物体上で当該関心対象の点に対応する３Ｄ点に直接関連付けられる。一例を、Ｊｕｒｉ  Ｐｌａｔｏｎｏｖ、Ｈａｕｋｅ  Ｈｅｉｂｅｌ、Ｐｅｔｅｒ  Ｍｅｉｅｒ、およびＢｅｒｔ  Ｇｒｏｌｌｍａｎｎによる論文「Ａ  ｍｏｂｉｌｅ  ｍａｒｋｅｒｌｅｓｓ  ＡＲ  ｓｙｓｔｅｍ  ｆｏｒ  ｍａｉｎｔｅｎａｎｃｅ  ａｎｄ  ｒｅｐａｉｒ」（ＩＳＭＡＲ，２００６）に示されている。
−３Ｄ点のクラウドを、ビデオシーケンスのマッチする２Ｄ点により、且つＳｆＭ（「Ｓｔｒｕｃｔｕｒｅ  ｆｒｏｍ  Ｍｏｔｉｏｎ（動きからの構造復元）」の略語）による再構築技術を用いて推定する。次いで、当該３Ｄ点のクラウドをオフライン且つ半自動的に物体の３Ｄモデルに再編成して、画像から抽出された記述子により補足された当該モデルに属する３Ｄ点を得る。当該方法の例を記述したＰ．Ｌｏｔｈｅ、Ｓ．Ｂｏｕｒｇｅｏｉｓ、Ｆ．Ｄｅｋｅｙｓｅｒ、Ｅ．Ｒｏｙｅｒ、およびＭ．Ｄｈｏｍｅの論文「Ｔｏｗａｒｄｓ  ｇｅｏｇｒａｐｈｉｃａｌ  ｒｅｆｅｒｅｎｃｉｎｇ  ｏｆ  ｍｏｎｏｃｕｌａｒ  ｓｌａｍ  ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｕｓｉｎｇ  ３ｄ  ｃｉｔｙ  ｍｏｄｅｌｓ：Ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｒｅａｌ−ｔｉｍｅ  ａｃｃｕｒａｔｅ  ｖｉｓｉｏｎ−ｂａｓｅｄ  ｌｏｃａｌｉｚａｔｉｏｎ」（ＣＶＰＲ，２００９）を引用することができる。学習フェーズが実行されたならば、記述子の尤度基準を用いて、現在画像から抽出された２Ｄ点を当該物体の３Ｄ点に関連付けることにより、オンラインでの姿勢計算が実行される。
【０００７】
これらの方法の二つの主な制約は、一方ではこれらが事前学習フェーズを必要とし、他方では学習フェーズと姿勢計算フェーズとの間での物体の測光外観の変化（すり切れた物体、照明条件の変動）に極めて敏感な点である。更に、これらの方法は、顕著なテクスチャのある物体にしか機能しない。
【０００８】
一般に、物体の既知の部分しか考慮しないこれらの方法の主な制約は、当該物体が画像のシーケンス内で常時視認可能な場合にしか機能しない点である。当該物体が完全に遮蔽されているかまたはカメラの視野から消えた場合、もはやこれらの方法ではカメラの姿勢を計算することができない。
【０００９】
これらの方法はまた、「ジタリング」（１画像毎に計算された姿勢の不安定性に起因する拡張現実における震動）を受けやすく、正確な姿勢推定を得るためには関心対象物体が画像内の多くのスペースを占有する必要がある。実際、カメラの姿勢を推定する際に環境に関する情報は考慮されていない。
【００１０】
他の方法は、全く未知環境内で移動しているカメラを考慮するものである。ＳｆＭ方式またはＳＬＡＭ「Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｌｏｃａｌｉｚａｔｉｏｎ  Ａｎｄ  Ｍａｐｐｉｎｇ（同時位置特定およびマッピング）」方式の方法は、観測されるシーンの幾何学的形状に関する一切の先験的知識無しにカメラの移動を推定する。オフライン、次いでオンラインの方法が提案されてきた。これらの方法は、位置を特定したい観測されたシーンの全体を用いるため極めて安定している。これらの方法は、カメラの軌跡およびシーンの幾何学的形状を逐次的に推定するものである。このため、これらのアルゴリズムは、恐らくは３Ｄ再構築されたシーンの（点、直線区間等の３Ｄプリミティブの疎なクラウドの形式での）により、マルチビュー関係（１個のビューが画像である）を用いてカメラの移動を推定する。カメラおよび再構築された３Ｄシーンの姿勢を同時に精緻化する追加的な最適化ステップが一般に実行される。後者のステップはバンドル調整と称する。ＳＬＡＭ方式のアルゴリズムの主な短所は、時間の経過に伴い誤差の累積し、従って軌道のドリフトの影響を受ける点である。常に高い３Ｄレジストレーション正確性を要するアプリケーションで（例：拡張現実）これらの方法を元々の形式で利用することは従って考慮されていない。また、単眼の場合、再構築は任意のスケールで実行されるが、現実のスケールは、シーンのスケールに関する追加的な情報を加えることでしか知ることができない。再構築はまた、シーンの物体に紐付けられていない任意の基準フレームで実行される。
【００１１】
最後に、より最近では、いくつかの方法がこれらの二つの方法を順次組み合せることを試みている。モデルに基づくアプローチ、次いでＳｆＭ技術を順次用いて部分的に既知の環境内で移動しているカメラの姿勢を推定する方法が提案されている。Ｂｌｅｓｅｒらは「Ｏｎｌｉｎｅ  ｃａｍｅｒａ  ｐｏｓｅ  ｅｓｔｉｍａｔｉｏｎ  ｉｎ  ｐａｒｔｉａｌｌｙ  ｋｎｏｗｎ  ａｎｄ  ｄｙｎａｍｉｃ  ｓｃｅｎｅｓ」（ＩＳＭＡＲ、２００６）で、モデルの幾何学的な制約を利用して基準フレームおよびＳＬＡＭアルゴリズムの再構築のスケールを初期化している。次いで、もはや３Ｄモデルを考慮に入れないＳＬＡＭ方式の「従来型」方法によりカメラの位置を計算する。
【００１２】
初期化を行う間の正確性は、初期化が単一視点でなされるため保証されず、また、当該方法は依然として数値誤差の累積およびスケール係数のドリフトの影響を受ける。先に指摘したように、ＳＬＡＭまたはＳｆＭ方式の方法に基づく位置特定では中期的には正確な位置特定が行えず、また長期的にはドリフト等の問題が生じる。
【００１３】
Ｖ．Ｇａｙ−Ｂｅｌｌｉｌｅ、Ｐ．Ｌｏｔｈｅ、Ｓ．Ｂｏｕｒｇｅｏｉｓ、Ｅ．Ｒｏｙｅｒ、およびＳ．Ｎａｕｄｅｔ−Ｃｏｌｌｅｔｔｅが「Ａｕｇｍｅｎｔｅｄ  Ｒｅａｌｉｔｙ  ｉｎ  Ｌａｒｇｅ  Ｅｎｖｉｒｏｎｍｅｎｔｓ：Ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  Ａｉｄｅｄ  Ｎａｖｉｇａｔｉｏｎ  ｉｎ  Ｕｒｂａｎ  Ｃｏｎｔｅｘｔ」（ＩＳＭＡＲ、２０１０）に記述している方法は、ＳＬＡＭ技術と事前学習を用いる再配置技術を組み合わせるものである。これにより、当該物体がもはやＳＬＡＭにより視認できない場合にカメラの姿勢を計算して、再配置によりドリフトを回避することが可能になる。しかし、この方法は、学習に基づく方法における事前学習フェーズを必要とする。
【００１４】
後者の二つの方法は、モデルの制約、次いで環境の制約を順次用いる。
【００１５】
同様に、環境の制約、次いでモデルの制約を順次用いる方法がＬｏｔｈｅら「Ｒｅａｌ−Ｔｉｍｅ  Ｖｅｈｉｃｌｅ  Ｇｌｏｂａｌ  Ｌｏｃａｌｉｓａｔｉｏｎ  ｗｉｔｈ  ａ  Ｓｉｎｇｌｅ  Ｃａｍｅｒａ  ｉｎ  Ｄｅｎｓｅ  Ｕｒｂａｎ  Ａｒｅａｓ：Ｅｘｐｌｏｉｔａｔｉｏｎ  ｏｆ  Ｃｏａｒｓｅ  ３Ｄ  Ｃｉｔｙ  Ｍｏｄｅｌｓ」（ＣＶＰＲ、２０１０）」に提案されている。この場合、環境の第１の再構築が実行され、次いで第２段階で、厳密な反復最近接点（Ｉｔｅｒａｔｉｖｅ  Ｃｌｏｓｅｓｔ  Ｐｏｉｎｔ（ＩＣＰ））法に基づく処理を用いて、再構築された環境をモデル上に再編成する。これは、可能な場合（即ちモデルが十分な幾何学的制約を与える場合）、モデルの情報だけを用いてカメラの軌跡を再編成するものである。この方法の主な短所は、モデル３Ｄレジストレーションステップにおけるマルチビュー制約を維持するために、当該処理に含まれる全てのカメラに同様の変換を施すが、これは現実には困難な仮定である。また、モデルに基づく方法と同様の短所がある。即ち、関心対象物体が殆どまたは全く観測されない場合に正確性および強靭性を欠く。また、この方法が二つに連続的なステップで実行されるため最適ではなく、各時点での正確且つリアルタイムな位置特定が保証されない。モデルによる修正が後験的ステップでなされるため、現在画像に姿勢の修正を施すには時間遅延が伴うため、当該方法は拡張現実のようなアプリケーションには適していない。
【発明の概要】
【発明が解決しようとする課題】
【００１６】
従って、カメラの位置特定、およびカメラが移動している静的環境内での３Ｄ再構築を、正確性、強靭性、安定性に関する上述の全ての要件を同時に満たし、且つこれをリアルタイムに行う方法に対するニーズが現在もある。
【課題を解決するための手段】
【００１７】
本発明によれば、カメラの位置特定および部分的に既知の環境内における環境の３Ｄ再構築は、ＳＬＡＭ方式のアルゴリズムの最適化フェーズを行う間、部分的に既知の環境の幾何学的制約と、環境の既知および未知な部分のマルチビュー制約を同時に組み合わせる。
【００１８】
カメラの姿勢および環境を構成する再構築された３Ｄプリミティブは、関心対象物体（＝環境内の既知の部分）に属するプリミティブの３Ｄモデルの幾何学的形状により制約される最適化方程式と、環境の未知の部分に属するプリミティブに対する従来の最適化方程式とを組み合せ、且つ２種類の項を有する単一のコスト関数により計算される。
【００１９】
より具体的には、本発明の主題は、カメラの位置特定、および当該カメラが内部を移動して画像を形成する静的環境の３Ｄ再構築を行う方法であって、当該環境が、３Ｄモデルが既知の関心対象物体を含み、本方法は以下のステップを含んでいる。
−ａ／環境内でのカメラの初期姿勢および初期再構築の計算、
−ｂ／環境の３Ｄプリミティブと前記画像の２Ｄプリミティブとのマッチングによる各新規画像に対するカメラの姿勢の計算、および三角測量による環境の３Ｄプリミティブの再構築、
−ｃ／複数の画像にわたり再射影誤差を最小化することによるカメラの姿勢および３Ｄプリミティブの同時最適化。
【００２０】
本発明は、３Ｄモデルが関心対象物体の幾何学的記述であること、再射影誤差が２種類の項、即ち３Ｄモデルにより制約されるプリミティブに紐付けられた第１の種類の項および当該物体以外の環境のプリミティブに紐付けられた第２の種類の項のみを含むこと、および最適化ステップがプリミティブを環境または３Ｄモデルに関連付けるサブステップを含むことを主な特徴とする。
【００２１】
ＳＬＡＭまたはＳｆＭ方式の従来方法と比較して、本方法は、シーン（＝環境）のサイズが巨大（多くの３Ｄプリミティブおよび多くのシーンのビュー）であっても、精緻化の強靭性および環境全体の再構築だけでなくカメラの位置特定の正確性も向上させる。これは、本システムが３Ｄ幾何学的モデルから生じた完全な情報を取り込むという事実による。更に、得られた再構築は原寸大（３Ｄモデルにより得られた）である。
【００２２】
最後に、モデルに基づく追跡方法と比較して、提案する解決策は、シーンの関心対象物体を連続的に観測する必要がないため、より満足できるものである。実際、問題の物体が観測されない場合（または画像の小さい部分しか占有しない場合）であっても、カメラは自身が移動している環境内で常に位置を特定することができる。本方法は従って、部分的または全体的な閉塞に対して完全に強靭である。カメラの位置特定の安定性も向上する。
【００２３】
最後に、２種類の情報を順次用いる方法と比較して、２種類の制約が各時点で同時に生じることが保証される。従ってより強靭な方法でカメラのより正確な位置特定および３Ｄ再構築が行える。
【００２４】
従来技術と比較した本方法との主な相違は以下の通りである。即ち、
−事前学習フェーズを一切必要とせず、
−関心対象物体（既知の３Ｄモデルの）をカメラの軌道全体にわたりカメラの視野に収めておく必要がない、または換言すれば、各画像内で物体が見えている必要がなく、
−閉塞およびカメラ−被写体間の距離の大幅な変動に強靭であり、
−近似的初期姿勢を自然に精緻化することが可能になり、
−環境の３Ｄ再構築の正確性が向上し、
−テクスチャのある、またはテクスチャの無い物体に対して機能し、
−２個の連続的な姿勢の間で高度な安定性を保証し（例えば拡張現実アプリケーションに往々にして有害な震動が無い）、
−環境と物体を同時に再構築することが可能になり、震動および不正確さの影響が回避される。
【００２５】
最後に、極めて正確、強靭、且つ安定な位置特定システムが得られる。
【００２６】
本発明の一特徴によれば、最適化ステップは、拒否閾値を示す強靭な推定子を用いて、各種の項の影響を当該拒否閾値の関数として適応制御することにより実行される。好適には、再射影誤差の各種の項が強靭な推定子の前記拒否閾値に紐付けられた拒否閾値に関連付けられていて、２個の拒否閾値（ｃ１、ｃ２）は３Ｄモデルに基づいて残余に対して推定された推定子の拒否閾値に等しい。これにより、環境のプリミティブに起因するマルチ画像制約を維持しながら、モデルに起因する制約を優先させることが可能になる。
【００２７】
初期姿勢の計算は、物体の基準フレームの複数平面の一つに配置された、マーカーとも称する、サイズが既知の目標により半自動的に実行することができ、目標は当該平面の間に配置された３Ｄプリミティブの組であって当該画像内で識別可能であるため、３個の自由度を固定することが可能になり、初期再構築はモデルへの２Ｄプリミティブの逆射影により得られる。
【００２８】
本発明の一特徴によれば、各新規画像に対するカメラの姿勢を計算するステップは、関心対象物体のプリミティブの３Ｄモデルの制約、および当該物体以外の環境のプリミティブに基づいて実行される。
【００２９】
最適化ステップに続いて、プリミティブが３Ｄモデルにより制約されない三角測量ステップを実行することができる。
【００３０】
最適化および／または再構築ステップは、現在画像と最終キー画像との対をなすプリミティブの個数が最小値より小さい場合に選択されたキー画像に対してのみ実行される点が有利である。
【００３１】
最適化ステップは有利には局所バンドル調整により実行され、リアルタイムな方法を得ることが可能になる。
【００３２】
３Ｄモデルにより制約されるプリミティブは、関心対象物体にテクスチャが有るおよび／またはテクスチャが無いのいずれかに応じて選択される。
【００３３】
本発明の他の特徴および利点は、添付の図面を参照しながら、非限定的な例として与える以下の詳細な説明を精査することにより明らかになろう。
【図面の簡単な説明】
【００３４】
【図１】従来技術によるカメラの位置特定および３Ｄ再構築方法の主なステップを模式的に示す。
【図２】本発明によるカメラの位置特定および３Ｄ再構築方法の主なステップを模式的に示す。
【発明を実施するための形態】
【００３５】
本発明は、シーン内の物体のモデルに関する知識に紐付けられた幾何学的制約を組み込むべく修正されたＳｆＭ方式の方法に依存する。シーンは、環境とも呼ばれ、静的であって、物体はシーン内での位置を変えないが、カメラにより画像シーケンス（ビデオ）が入力される間に、関心対象物体の要素がビデオ中に移動または除去される可能性があるため、物体自体が変形する場合がある。
【００３６】
以下の記述は、カメラの位置特定（軌道の推定）および当該カメラが移動している３Ｄ環境のモデリング（または再構築）を行う際に与えられる。
【００３７】
以下、環境について、その既知部分、即ち物体のモデルと、当該モデルの外部環境である当該環境の未知部分とは線引きされて区別される。
【００３８】
本発明は、ＳｆＭ方法に基づいている。ＳｆＭ方法の原版は、Ｅ．Ｍｏｕｒａｇｎｏｎ、Ｍ．Ｌｈｕｉｌｌｉｅｒ、Ｍ．Ｄｈｏｍｅ、Ｆ．Ｄｅｋｅｙｓｅｒ、およびＰ．Ｓａｙｄにより「Ｒｅａｌ  ｔｉｍｅ  ｌｏｃａｌｉｚａｔｉｏｎ  ａｎｄ  ３ｄ  ｒｅｃｏｎｓｔｒｕｔｉｏｎ」（ＣＶＰＲ、２００６）で提案された、関心対象の点に用いるものと同一であるが、異なる種類のプリミティブにも適用可能である。図１に関して記述する従来のＳｆＭ方法の原版では以下の４個のステップ、即ち初期化（ステップＡ）、位置特定（ステップＢ）、再構築（ステップＤ）、最適化（ステップＥ）を含んでいる。最後の３ステップは順次または並列に実行できることが直ちに理解されよう。
【００３９】
初期化は、観測されたシーンの第１の３Ｄ再構築を実行して、カメラの第１の姿勢（位置および回転）を計算するものである。
【００４０】
位置特定（３Ｄ追跡とも称する）は、既に再構築されているシーンの３Ｄプリミティブと現在画像の２Ｄプリミティブとの相関からカメラの姿勢を計算するものである。
【００４１】
３Ｄ再構築は、３Ｄ三角測量により、特に新規のプリミティブの３Ｄ再構築を可能にすべく、先行画像（２Ｄ追跡）のプリミティブと、現在画像内で検出されたプリミティブとをマッチングするものである。
【００４２】
最適化により、３Ｄ再構築されたシーンおよびカメラの推定された軌跡を精緻化することが可能になる。最適化は、非線形コスト関数、この場合は再射影誤差、の最小化に基づいているため、画像内で再射影された再構築プリミティブを画像内で観測されるプリミティブと最適にマッチさせることが可能になる。多くの方法を用いることができ、そのうち引用可能なものがバンドル調整である。更に、画像内での２Ｄ誤差を最小化することによりエピポーラ幾何学に基づく方法を用いることも可能であり、これにより最初に軌道が最適され、２回目に再構築されたシーンが最適化される。
【００４３】
リアルタイム性能を目的として、３Ｄ再構築および最適化ステップは、全ての画像について実行される訳ではなく、「キー画像」（ステップＣ）と称する特定の画像に対してのみ実行される。これらは、当該画像内で合致したプリミティブの個数と、カメラの姿勢間の相対変位との間のトレードオフを得ることにより、当業者に知られた従来の仕方で選択され、三角測量により実行された３Ｄ再構築を優先させる。これは、現在画像と最終キー画像との間で合致したプリミティブの個数が最小値より低い場合にキー画像を選択することになる。
【００４４】
一般に、この最適化フェーズは、同時に軌道および再構築を最適化することを可能にするバンドル調整により実行される。バンドル調整による最適化は、再射影誤差の和、即ち射影された３Ｄプリミティブと検出された２Ｄプリミティブの距離の和を最小化する。
【００４５】
バンドル調整に基づく最適化フェーズは以下の表記を用いて詳述する。
【００４６】
ベクトルは、統一座標として表される。例えば、ｑ≡（ｘ、ｙ、ｗ）Ｔ、ここにＴは転置、および≡はあるスケール係数の範囲内での等号を示す。精緻化したい再構築されたシーンは、Ｎ個の３Ｄ点
【数１】
0006044005.tif 000002
およびカメラのｍ通りの姿勢
【数２】
0006044005.tif 000003
からなる。姿勢Ｃｋにおけるカメラ内の３Ｄ点Ｑｉの観測をｑｉ，ｋで表記し、観測するカメラの添え字Ｑｉの組をＡｉと表記する。カメラの姿勢Ｃｋに関連付けられた射影行列Ｐｋは
【数３】
0006044005.tif 000004
で与えられ、ここにＫは固有パラメータの行列で（Ｒｋ；ｔｋ）は時点ｋにおけるカメラの姿勢のパラメータである。従来のバンドル調整により、観測されたシーンおよびカメラの姿勢を記述する３Ｄ点を同時に精緻化することが可能になる。これにより、画像内の３Ｄ点の射影とそれらの観測値との距離の２乗和を最小化する。この幾何学的距離を再射影誤差εと称する。最適化したいパラメータは、Ｎ個の３Ｄ点の３個の座標、およびカメラのｍ通りの姿勢の６個の外部パラメータである。パラメータの総数は従って、３Ｎ＋６ｍである。コスト関数は、次式で与えられる。
【数４】
0006044005.tif 000005
ここにｄ２（ｑ、ｑ’）＝｜｜ｑ−ｑ’｜｜２は画像の２点間の距離の２乗である。
【００４７】
本発明によれば、バンドル調整による最適化、初期化、および恐らく位置特定も、関心対象物体の３Ｄモデルの制約を受ける。
【００４８】
最適化は、Ｎ個の最終キー画像の姿勢および観測された３Ｄ点を、Ｍ個の最終キー画像（Ｎ≦Ｍ且つＭは全ての観測と同数であり得る）内のこれらの点の観測値の残余を用いて最適化するものである局所バンドル調整により有利に実行することができる。注目すべきは、大域的バンドル調整に対するメモリへの書き込みを減少させながらリアルタイム方法を得ることである。本方法は、Ｎ＝３で実行できる。
【００４９】
４フェーズの各々に用いるプリミティブは、関心対象の点、直線区間、曲線、平面、または数種類のプリミティブ（例えば、点＋区間）の組合せ等であってよい。
【００５０】
これらのフェーズについて以下に詳述する。
【００５１】
上述のように、３Ｄモデルのこれらの制約は初期化（ステップＡ’）、即ち初期姿勢または初期再構築の計算のいずれかに適用できる。
【００５２】
初期姿勢計算により、物体上の固定された基準フレームに相対的なカメラの位置および向きを計算することが可能になる。多くの方法をこのステップに利用することができる。Ｂｌｅｓｅｒらは「Ｏｎｌｉｎｅ  ｃａｍｅｒａ  ｐｏｓｅ  ｅｓｔｉｍａｔｉｏｎ  ｉｎ  ｐａｒｔｉａｌｌｙ  ｋｎｏｗｎ  ａｎｄ  ｄｙｎａｍｉｃ  ｓｃｅｎｅｓ」（ＩＳＭＡＲ、２００６）において、カメラを動かすことによりユーザーに画像内の物体上の３Ｄモデルを再編成させる半自動方法を提案している。ユーザーは従って、画像内の物体のエッジに基づく精緻化を可能にすべく、姿勢が十分現実に近いことが（自動的に）検出されるまで、６個の自由度を再編成する必要がある。Ｂｌｅｓｅｒらのものに比較的類似しているが、よりユーザーフレンドリーな半自動式の解決策が提案されている。これは、物体の基準フレームの平面の一つにサイズが既知（位置が未知）の標的を配置するものである。目標により推定された３個の自由度（２個の回転自由度および１個の並進自由度）はこのように固定される。ユーザーは次いで、最後の３個の自由度を再編成しなければならない。画像内の物体のエッジに基づく精緻化が次いで実行される。これらの間で位置して画像内で識別可能な３Ｄプリミティブの組を目標と称する。この位置特定および３Ｄ再構築方法が、近似的な初期姿勢（カメラ−被写体間距離の許容度が最大１０％）しか必要としない点に注意されたい。この可能な近似的な初期姿勢でも本方法の強靭性は損なわれない。
【００５３】
プリミティブの第１の３Ｄ再構築は、初期画像内で検出された２Ｄ点を３Ｄモデルへ逆射影することにより実行される。次いでモデルに属する３Ｄ点の組が粗い精度で得られる。逆射影とは、各２Ｄ点について、光線照射（カメラおよび２Ｄ点の光学中心を透過する光線追跡）を実行して、当該光線と３Ｄ物体の表面との交差を計算するものである。
【００５４】
モデルの制約を受ける可能性があるが必然的ではない３Ｄ位置特定フェーズ（ステップＢ’）の場合、合致した３Ｄ／２Ｄプリミティブを用いて各新規画像についてカメラの姿勢が計算される。使用する方法（モデルの制約を受けない）は、Ｅ．Ｍｏｕｒａｇｎｏｎ、Ｍ．Ｌｈｕｉｌｌｉｅｒ、Ｍ．Ｄｈｏｍｅ、Ｆ．Ｄｅｋｅｙｓｅｒ、およびＰ．Ｓａｙｄにより「Ｒｅａｌ  ｔｉｍｅ  ｌｏｃａｌｉｚａｔｉｏｎ  ａｎｄ  ３ｄ  ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ」（ＣＶＰＲ、２００６）に記述されている、関心対象の点に用いるものと同種であるが、異なる種類のプリミティブにも適用可能である。
【００５５】
３Ｄ再構築フェーズは、簡単な三角測量（ステップＤ）により従来方式で実行される。
【００５６】
最適化フェーズ（ステップＥ’）はモデルの制約を受ける。当該ステップは、３Ｄ空間内の現在画像の２Ｄプリミティブの逆射影から始まる。物体に属するプリミティブ（自身の光線が当該物体の表面を横断する）は従って当該物体の環境に属する３Ｄプリミティブとは区別される。
【００５７】
上で見たように、従来のバンドル調整による最適化は、再射影誤差の和、即ち射影された３Ｄプリミティブと検出された２Ｄプリミティブとの距離の２乗和を最小化するものである。本発明によれば、最小化したいコスト関数もまた、これらの再射影誤差（残余）の和であるが、コスト関数は２種類の項からなる。即ち、
−１種類の項は、モデルにより制約されるプリミティブの残余に紐付けられ、
−１種類の項は、モデルの外部環境のプリミティブの残余に紐付けられている。
【００５８】
以下に、物体の３Ｄモデルに起因する追加的な制約を利用する方法をより詳細に述べる。モデルの制約は、考慮するプリミティブに応じて異なって定式化される。その定式化を以下のプリミティブ、即ち関心対象の点および直線区間について詳述する。
【００５９】
マルチビュー関係（即ちマルチ画像）および３Ｄモデルに属する制約を組み合せた２個の非線形コスト関数を提示する。第１の、点に基づくコスト関数は、自身のプリミティブが一般に関心対象の点であるテクスチャのある物体に適用可能である。第２の、エッジに基づくコスト関数は、殆どテクスチャのない物体に適用される。これらには、ピクセルに表れる残余誤差εを最小化するという共通性がある。これらは、テクスチャおよびエッジを示す物体のバンドル調整に一緒に用いることができる。
【００６０】
このコスト関数εは最初に点について考慮される。モデルが物体（平面πの組）の面を記述する三角形の組であると仮定する。主たる発想は、平面πに属する３Ｄ点Ｑｉが２個の自由度しか有していないということである。
【００６１】
カメラの位置およびシーンの３Ｄ構造を最適化すべく、得られたコスト関数は次式の通りである。
【数５】
0006044005.tif 000006
上式において、
【数６】
0006044005.tif 000007
は平面πｉの基準フレームと大域的基準フレームとの間の転送行列であって
【数７】
0006044005.tif 000008
（Ｘπｉ，Ｙπｉ，０，１）Ｔであって（Ｘπｉ，Ｙπｉ）は平面πｉの基準フレーム上でＱｉの座標、
ｃ１，ｃ２は強靭な推定子の拒否閾値、
ρは強靭な推定子関数であってρ（ｒ，ｃ）＝ｒ２／（ｒ２＋ｃ２）、ｒはコスト関数の残余誤差、ｃは推定子の拒否閾値である。
【００６２】
関心対象物体にテクスチャが無い場合は、直線区間に基づくモデルの制約を用いる。物体の幾何学的モデルはこの場合、当該モデルのエッジである。当該モデルは次いでＥ個の区間（中心点
【数８】
0006044005.tif 000009
および方向
【数９】
0006044005.tif 000010
で自動的にサンプリングされて画像に射影される。次いで射影された区間の法線方向ｎｉ，ｋでの最大勾配を前記画像内で求める。カメラＣｋの中心点Ｍｉの射影に関連付けられた最大勾配をｍｉ，ｋと表記し、観測しているカメラの添え字Ｍｉの組をＳｉと表記する。次いで画像に再射影された区間の中心点と、付随する最大勾配との間の距離（ピクセル単位）を用いてカメラの軌跡および未知環境のプリミティブの３Ｄ再構築を制約し、その結果得られるコスト関数は次式の通りである。
【数１０】
0006044005.tif 000011
【００６３】
提案する解決策は、初期３Ｄレジストレーションの不完全さ、およびモデルの幾何学的不完全さ（現実と完全には一致しないモデル）に対して強靭である。現実には、モデルの幾何学的不完全さおよびＳｆＭ方式のアルゴリズムにより生じるドリフトに対する近似初期３Ｄレジストレーションは、最適化プロセスの収束を妨げる恐れがある劣悪なプリミティブモデル関連付けをもたらす可能性がある。これらの異常な関連付けを管理するために、Ｍ推定子により強靭な推定が実行される。例えば、正規化されているという顕著な特徴を有するＧｅｍａｎ−ＭｃＣｌｕｒｅ推定子を用いる。
【００６４】
２目的問題を最小化する際の重大な困難の一つが、各項の影響をどのように制御するかである。これは一般に、試行錯誤的に固定される重み付けパラメータを用いて、またはＭｉｃｈｅｌａ  Ｆａｒｅｎｚｅｎａ、Ａｄｒｉｅｎ  Ｂａｒｔｏｌｉ、およびＹｏｕｃｅｆ  Ｍｅｚｏｕａｒにより「Ｅｆｆｉｃｉｅｎｔ  ｃａｍｅｒａ  ｓｍｏｏｔｈｉｎｇ  ｉｎ  ｓｅｑｕｅｎｔｉａｌ  ｓｔｒｕｃｔｕｒｅ−ｆｒｏｍｍｏｔｉｏｎ  ｕｓｉｎｇ  ａｐｐｒｏｘｉｍａｔｅ  ｃｒｏｓｓ−ｖａｌｉｄａｔｉｏｎ」（ＥＣＣＶ、２００８）に記述されているように相互検証を用いてなされる。より簡単な代替例が提案されている。即ち、通常ＭＡＤ（Ｍｅｄｉａｎ  ｏｆ  Ａｂｓｏｌｕｔｅ  Ｄｅｖｉａｔｉｏｎ）と表記される残余の絶対偏差の中央値により計算された強靭な推定子の拒否閾値を用いて各種の項（群）の影響を直接制御する。試行錯誤的に検証されるこのいわゆる適応的重み付け法の利点は、リアルタイムでの自動重み付けが可能になる点である。例えば、以下の三通りの可能性が考えらえる。
−ｃ１＝ｃｅｎｖｉｒｏｎｍｅｎｔおよびｃ２＝ｃｍｏｄｅｌ、
−ｃ１＝ｃ２＝ｃａｌｌ、
−ｃ１＝ｃ２＝ｃｍｏｄｅｌ、
ｃｍｏｄｅｌはモデルに基づく残余について推定された拒否閾値、
ｃｅｎｖｉｒｏｎｍｅｎｔは環境の未知部分の残余について推定された拒否閾値、
ｃａｌｌは全ての残余について推定された拒否閾値である。
【００６５】
ｃ１＝ｃ２＝ｃａｌｌを仮定することにより、２種類の残余が同じオーダーの大きさを有していると恣意的に考えられる。一方、他の二つのケースでは、モデルに関連付けられた残余が実際にはより高い値を有するという事実が考慮に入れられる。第１のケースでは、環境の既知部分（モデル）と未知部分を同じように考慮する。第３のケースでは、環境の未知部分に関連付けられた制約がいぜんとして検証されていることを保証しながら、最適化を行う間は既知部分（モデル）を優先させる。この第３のケースが好ましい。
【００６６】
従来の最適化と比較して、モデルの制約による最適化は従って追加的なステップを伴う。実際には、モデルの制約を生じるために、プリミティブにモデルが関連付けられていなければならない（選択された制約に応じて２Ｄまたは３Ｄの関連付け）。異なる制約を生成する２種類の関連付けが可能である。即ち、
−３Ｄ−３Ｄ関連付けフェーズ：再構築された３Ｄプリミティブ（３Ｄ点、３Ｄ区間）に平面またはモデルのエッジが関連付けられる。所与のプリミティブについて、モデルの制約が最適化フェーズにおいて関心対象プリミティブおよびカメラの軌道に適用される。当該制約は、自身が関連付けられたモデルの部分に応じて３Ｄプリミティブに割り当てられる自由度の個数に反映させることができる（例：再構築されたがモデルに関連付けられていない３Ｄ点は３個の自由度を有しているのに対し、再構築されてモデルの平面に関連付けられた３Ｄ点は自身が関連付けられた平面内でしか移動できないため２個の自由度を有している。再構築されたがモデルに関連付けられていない３Ｄ区間は少なくとも４個の自由度を有しているのに対し、再構築されてモデルの平面に関連付けられた３Ｄ区間は２個の自由度を有している。再構築されてモデルのエッジに関連付けられた３Ｄ区間は１個の自由度を有している）。
−３Ｄ−２Ｄ関連付けフェーズ：モデル（３Ｄ点、３Ｄ区間）から抽出された３Ｄプリミティブは画像へ再射影されて２Ｄプリミティブ（２Ｄ点、２Ｄ区間、２Ｄエッジ）に関連付けられる。制約は次いで、モデルから抽出された３Ｄ点または区間が０個の自由度を有しているという事実に反映される。これは、最適化フェーズにおけるカメラの軌跡を制約するためにのみ用いられる。
【００６７】
最適化ステップ（Ｅ’）は従って以下のサブステップを含んでいる。
１．プリミティブの環境またはモデルとの関連付け
引用できるプリミティブの例は以下を含んでいる。
ａ．再構築された点のケース：各３Ｄ点Ｑｉ（）の、関連付けられた平面πｉへの射影であって、３Ｄ点に関連付けられた平面は、同じ３Ｄ点に関連付けられた２Ｄ観測により生じる最大光線により横断されている。
ｂ．再構築された区間のケース：各３Ｄ区間の、自身に関連付けられた平面πｉへの射影であって、３Ｄ区間に関連付けられた平面は、同じ３Ｄ区間に関連付けられた２Ｄ観測により生じる最大光線により横断されている。
ｃ．モデルから抽出された３Ｄ点のケース：２Ｄ最適化に含まれる各キー画像内で視認可能な３Ｄ点の射影、およびこれらの画像内で検出された関心対象の点との２Ｄ関連付け。
ｄ．モデルから抽出された３Ｄ区間のケース：２Ｄ最適化に含まれる各キー画像内で視認可能な３Ｄ区間の射影、およびこれらの画像のエッジとの２Ｄ関連付け。
２．推定子の拒否閾値の計算。
３．推定子の誤差εの最適化。
【００６８】
このように提案されたバンドル調整は従って、
−３Ｄモデルにより制約される種類の項（群）を含む２目的関数、および未知環境のプリミティブのマルチビュー制約に用いる種類の項（群）、
−拒否閾値ｃ１およびｃ２によりこれら２種類の項（群）同士の影響の適応的調整に依存する。
【００６９】
本方法により、モデルの不完全さ、物体の局所的変動、または物体の閉塞にも適応させることが可能になる。
【００７０】
例えば、視認される物体が局所的に変更された（例えば、物体の一部の除去により）場合、アルゴリズムは自動的にこの変化に適応する。より正確には、拒否閾値の（自動的に決定される）適応的な制御により、モデルにより当初制約されたプリミティブは、拒否されるかまたは未知環境に属するプリミティブとして識別される（従ってコスト関数の第１項に含まれる）。物体が部分的または完全に隠されている場合でも同じ現象が現れる。
【００７１】
従って、本発明の方法は当然、モデルの不完全さに対して強靭である。関心対象物体の幾何学的モデルが、問題の物体のそれと完全に同一でない場合であっても本方法は機能する。本方法は、シーケンスの最中に物体が僅かに変更されても同様に強靭である。これは、各最適化ステップＥ’でプリミティブとモデルの関連付けを再評価可能にする再構築ステップＤを行う間、プリミティブが強制的にモデルに属させられないという事実による。
【００７２】
同じ原理で、カメラの軌跡だけを最適化して、シーンの幾何学的形状を誘導的に最適化することも可能である。これは、最適化のプリミティブの位置パラメータを除去することにより行える。その利点は、メモリへの書き込みが減ると共に、本方法の収束域が増えることである（最適化すべきパラメータが少ない）。この目的のために、もはやバンドル調整は使用しないが、エピポーラ幾何学に基づく他のコスト関数を用いることができる（例：環境のプリミティブの基本行列、モデルを構成する異なる平面の一つに関連付けられたプリミティブのホモグラフィ）。この場合、シーンの幾何学的形状を取得するためには、カメラの軌跡を精緻化した後で、プリミティブの三角測量を行えば十分であることが認められる。
【００７３】
エピポーラ幾何学的形状は、２個の異なる位置からカメラにより撮像された同一シーンの２個の画像間の幾何学的関係を定義する。これは、基本行列により以下のように３Ｄ点Ｑｉの２個の観測値（ｑｉ，１、ｑｉ，２）を紐付ける。
【数１１】
0006044005.tif 000012
ここにＦは階数２の３×３行列であり、Ｆｊ，ｋは画像ペア（ｊ，ｋ）の間の基本行列を表記する。
【００７４】
この関係は、第１の画像の点ｑｉ，１に対応する第２の画像の任意の点ｑｉ，２が、ｌ＝Ｆｑｉ，１となるようにエピポーラ線ｌに乗っていなければならないことを意味する。
【００７５】
ｄｌ（ｑ，ｌ）を用いて点ｑと線１の間の点−線間距離を示す。
【数１２】
0006044005.tif 000013
ωは統一座標として表されるベクトルｑの最後の要素である。
【００７６】
２個の視認角度を有する幾何学的形状において、同一平面πの２個の画像が射影変換Ｈにより、ｑｉ，１〜Ｈｑｉ，２となるように紐付けられる。
これは、平面に関するエピポーラ幾何学的形状の先の関係に等価である。平面πにより誘導される射影変換Ｈは次式の通りである。
【数１３】
0006044005.tif 000014
ここに、ｎは平面への法線、ｄはＣ１と平面との距離である。
【００７７】
【数１４】
0006044005.tif 000015
を用いてカメラの位置ｊおよびｋから見た平面πｉの観測により誘導される射影変換を示す。
【００７８】
カメラの位置だけを最適化したい場合、得られるコスト関数は次式の通りである。
【数１５】
0006044005.tif 000016
【００７９】
上に示す逆射影誤差の各々は２個の項だけを含んでいる。より一般的には、２種類の項のみを含み、一方は３Ｄモデルにより制約され、他方は未知環境のプリミティブのマルチビュー制約用であり、各々の種類の項自身が多くの項を含んでいてよい。実際、未知環境を２個の部分に分けて、テクスチャのある部分に１項およびテクスチャの無い部分に他の項を用いることが可能である。同じことが、モデルのテクスチャのある、またはテクスチャの無い部分に応じて同じく２個の項を含む環境（モデル）の既知の部分にあてはまる。
【００８０】
多くのアプリケーションが３Ｄ物体の追跡を必要とする。
−現実のシーンに、重ね合わされた仮想情報（カメラからのビデオストリーム、またはユーザーが半透明の眼鏡を用いる場合はユーザーの直接視認に基づく）を追加する拡張現実。拡張現実の概念はまた、先験的に視認できるものではない仮想要素を追加することにより、現実世界に対する知覚を向上させることを意図している。そのアプリケーションは多岐にわたり、ビデオゲーム、映画、テレビ（仮想スタジオ、スポーツの再転送等）、工業（概念、設計、保守、組立、ロボット工学等）、医療等、益々多くの分野に影響を及ぼしつつある。
−ロボット工学分野：視認（自律的ナビゲーション）によるロボットまたは特定の物体の操作を行うロボット化されたアームの誘導またはサーボ制御の関連。
−自動車産業：都市環境内でのナビゲーション支援の関連。
【００８１】
これら全てのアプリケーションのために、コンピュータ視認は従って安価、実用的、且つ非侵入性の解決案を提供する。
【００８２】
カメラは較正され、その固有パラメータ（焦点、画像の中心位置）は既知である。
【００８３】
画像は、リアルタイムストリームから、または事前に録音されたビデオからのものである。
【図１】
0006044005.tif 000017
【図２】
0006044005.tif 000018