(57)【特許請求の範囲】
【請求項１】
シーンにおける物体の姿勢を求めるための方法であって、プロセッサによって実行され、
仮想カメラを用いて前記物体のモデルの仮想画像の集合をレンダリングするステップであって、各前記仮想画像の集合は、前記モデルの異なる既知の姿勢についてのものであり、前記モデルは、仮想光源の集合によって照明され、特定の既知の姿勢について特定の集合における仮想光源毎に１つの仮想画像がある、レンダリングするステップと、
各前記仮想画像から仮想奥行きエッジマップを作成するステップと、
各奥行きエッジマップの集合をデータベースに格納すると共に、各該奥行きエッジマップの集合を対応する既知の姿勢と関連付けるステップと、
実カメラを用いて前記シーンにおける前記物体の実画像の集合を取得するステップであって、前記物体は、未知の姿勢を有し、前記物体は、実光源の集合によって照明され、実光源毎に１つの実画像がある、取得するステップと、
前記実画像毎に実奥行きエッジマップを作成するステップと、
コスト関数を用いて前記実奥行きエッジマップを各前記仮想画像の集合の前記仮想奥行きエッジマップと照合するステップであって、前記未知の姿勢に最も一致する前記既知の姿勢を求め、該照合は、前記奥行きエッジマップにおける画素の位置及び配向に基づく、照合するステップと
を含み、
環境光を用いて前記シーンの環境画像を取得するステップ、及び
各前記実画像から前記環境画像を差し引くステップ、
をさらに含む、方法。
【請求項２】
前記実カメラ及び前記仮想カメラは従来のものであり、前記実画像及び前記仮想画像の前記エッジは、姿勢の推定に用いられる、請求項１に記載の方法。
【請求項３】
さまざまな物体のための格納されたクエリエッジテンプレートのデータベースからの画像における物体の検出及び位置特定に用いられる、請求項２に記載の方法。
【請求項４】
前記カメラは、前記物体を操作するためのロボットアーム上に配置される、請求項１に記載の方法。
【請求項５】
前記モデルは、コンピュータ支援設計モデルである、請求項１に記載の方法。
【請求項６】
前記モデルは、前記物体の取り得る姿勢のエッジの集合である、請求項１に記載の方法。
【請求項７】
異なる物体の複数のモデルが同時に格納される、請求項１に記載の方法。
【請求項８】
前記照合は、方向性面取りマッチングを用いて大まかな姿勢を求めると共に、該大まかな姿勢を精緻化するためのオプションの手順を用いる、請求項１に記載の方法。
【請求項９】
比画像を求めるために、各前記実画像を最大輝度画像で割ることであって、前記照合は、該比画像に基づく、割ること、
をさらに含む、請求項１に記載の方法。
【請求項１０】
各前記仮想画像及び各前記実画像を離散的な配向チャネルに量子化することであって、前記コスト関数は、該配向チャネル全体でマッチングスコアを合計する、量子化すること、
をさらに含む、請求項１に記載の方法。
【請求項１１】
前記実画像及び前記仮想画像から得られるエッジは、離散的な配向チャネルに分割され、前記コスト関数は、該配向チャネル全体でマッチングスコアを合計する、請求項２に記載の方法。
【請求項１２】
前記コスト関数は、
【数１】
0005455873.tif 000040
であり、Ｕ＝｛ｕｉ｝は、前記仮想エッジマップにおける仮想画素であり、Ｖ＝｛ｖｊ｝は、前記実画像エッジマップにおける実画素であり、φは、各前記画素の配向であり、λは、重み係数であり、ｎ＝｜Ｕ｜である、請求項１１に記載の方法。
【請求項１３】
前記方向φは、πを法として計算され、配向誤差が、２つの方向間の最小円形差を与える、請求項１２に記載の方法。
【請求項１４】
前記仮想画像及び前記実画像内の画素を線分で表現すること、及び
前記仮想画像及び前記実画像の前記線分を位置合わせすること
をさらに含む、請求項１に記載の方法。
【請求項１５】
所与の位置の前記コスト関数は、３Ｄ距離変換及び方向性積分画像を用いてエッジ点の数の部分線形時間において計算される、請求項１２又は１４に記載の方法。
【請求項１６】
前記エッジは、従来のカメラ及びＣａｎｎｙエッジ検出を用いて計算することができる、請求項１に記載の方法。
【請求項１７】
手書きの物体又は典型的な物体のギャラリーが、画像において、前記コスト関数及び高速マッチングアルゴリズムを用いて検出及び位置特定される、請求項１に記載の方法。
【請求項１８】
剛体物体又は変形可能な物体の姿勢が例示画像又は例示形状のギャラリーを用いて推定される、請求項１７に記載の方法。
【請求項１９】
人体の姿勢の推定に適用される、請求項１に記載の方法。
【請求項２０】
画像における物体の検出及び位置特定に適用される、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、物体の姿勢を求めることに関し、特に、通常のカメラ又はマルチフラッシュカメラのいずれかによって取得される画像内のエッジに基づいて姿勢を求めることに関する。
【背景技術】
【０００２】
コンピュータビジョンシステムは、ロボットを用いた自動製造等の多くの用途で使用されている。ほとんどのロボットは、制限及び制約のある環境でしか動作することができない。例えば、組立ラインの部品は、ロボットが把持及び操作できるように、決まった姿勢で置かれなければならない。本明細書中で使用されるように、物体の姿勢は、平行移動及び回転による３Ｄ位置及び３Ｄ配向として定義される。
【０００３】
３Ｄモデルと２Ｄ画像との対応を用いて物体の姿勢を求める方法が既知である。残念ながら、これらの方法は、光沢のある表面又はテクスチャのない表面を有する物体には上手く機能しない。雑然としたシーン、例えば複数の物体が積み重なった置き場に複数の同一物体が置かれている場合は、特に厳しい状況となる。
【０００４】
面取りマッチングを使用すると、物体の輪郭を用いて姿勢を特定し求めることができる。しかしながら、撮像された輪郭が部分的に遮蔽されていたり、雑然とした背景の中にある場合、従来の方法では失敗してしまう。エッジ配向を用いて、雑然とした背景における面取りマッチングを改善することができる。既存の面取りマッチングアルゴリズムにおいて計算複雑性が最良のものは、輪郭点の数の一次式である。
【０００５】
アクティブ照明パターンは、雑然としたシーンの中の特徴を正確に抽出することによって、コンピュータビジョンの方法にとって大きな力になることができる。このような方法の例として、構造化照明パターンを投影することによる奥行き推定がある。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の実施の形態は、物体の２Ｄ又は３Ｄ姿勢を求めるための方法及びシステムを提供する。
【課題を解決するための手段】
【０００７】
オフライン段階中に、本方法は、コンピュータ支援設計（ＣＡＤ）モデルであってもよいモデルから得た物体の方向性特徴の集合を用いて物体をモデリングする。仮想カメラ及びレンダリングエンジンを用いて、物体の取り得る姿勢毎に仮想画像の集合を生成する。仮想画像及び関連する姿勢は、後のオンライン段階中の比較のためにデータベースに格納される。
【０００８】
オンライン段階中に、さまざまな任意の姿勢の１つ又は複数の物体を含むシーンの実画像の集合を実カメラによって取得する。この実カメラは、通常のカメラ又はマルチフラッシュカメラとすることができる。例えば、シーンは、物体を含む部品置き場を含む。その場合、例示的な用途において、物体は、それらの姿勢に応じて置き場からロボットアームによって、さらなる組み立てのためにピッキングされることができる。本方法は、取得画像からのエッジをデータベースに格納されたエッジと照合する必要のある多くの他のコンピュータビジョンアプリケーションにも用いることができることが理解される。このような用途の例として、エッジを用いた物体の検出及び位置特定がある。
【０００９】
画像は、通常のカメラ又はマルチフラッシュカメラのいずれかから取得することができる。画像が通常のカメラにより取得される場合、Ｃａｎｎｙエッジのような輝度エッジ検出器が用いられる。検出されたＣａｎｎｙエッジ及びその配向を用いて、さまざまな姿勢の物体の実画像及び仮想画像の照合を行う。マルチフラッシュカメラの場合、シーンは、実カメラのレンズの周囲に円形に配置された点光源及び環境照明によって照明される。照明毎に画像を取得する。光源の変化によってシーンに投じられる影は、シーンにおける奥行きの不連続性に関する情報を符号化する。検出された奥行きエッジとそれらの配向を用いて、仮想画像と実画像との照合を行い、物体の姿勢を求める。
【００１０】
本方法は、複数の物体が置き場内に置かれ、各物体を置き場から１つずつピッキングする必要があるロボットアプリケーションで特に有用である。本方法は、あまりテクスチャがなく雑然としたシーンに埋没した鏡面反射する物体に用いることができる。
【００１１】
本方法は、各エッジ画素の位置及び局所的配向の両方を尊重する新規のコスト関数を用いる。このコスト関数は、従来の面取りコスト関数よりも遥かに優れており、従来の方法では信頼性がないひどく雑然としたシーンでも正確な照合ができる。本発明は、部分線形時間手順を提供し、３Ｄ距離変換及び積分画像からの技法を用いてコスト関数を計算する。
【００１２】
本発明者らはまた、マルチビューに基づく姿勢の精緻化手順を提供し、推定した姿勢を改良する。本発明者らは、産業用ロボットアーム用の手順を実行し、最小限のテクスチャを有するさまざまな部品に関してそれぞれ、約１ｍｍの位置推定精度及び約２度の角度推定精度を得た。
【００１３】
コスト関数及び部分線形時間マッチングアルゴリズムは、（追加光源のない）通常のカメラ設定でも、画像内の物体を検出及び位置特定するために用いることができる。画像内のエッジは、Ｃａｎｎｙエッジ検出器等の標準的なエッジ検出アルゴリズムを用いて検出することができる。入力は、画像内で位置特定される物体のギャラリーである。このアルゴリズムは、ギャラリー物体のエッジを新たな観測画像と照合することによって、シーンにおける物体を位置特定する。マッチングコストが所与の位置についてユーザの定めた閾値よりも小さければ物体が検出される。
【発明の効果】
【００１４】
本発明は、通常のカメラ及び輝度エッジ又はマルチフラッシュカメラ（ＭＦＣ）及び奥行きエッジを用いた物体の検出、位置特定及び姿勢推定のための方法及びシステムを提供する。本発明ではこの問題を、物体の３Ｄ  ＣＡＤモデルを用いてオフラインで計算されるレンダリングされた輝度／奥行きエッジに対して１つ又は複数の通常／ＭＦＣ画像内で得られた輝度／奥行きエッジ間の一致を見つける問題として定式化し直す。
【００１５】
本発明では、従来の面取りコストよりも遥かに優れた新規のコスト関数を導入し、部分線形時間マルチビューに基づく姿勢推定及び精緻化手順を開発した。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態による物体の姿勢を求めるためのシステムの概略図である。
【図２】本発明の実施形態による物体の姿勢を求めるための方法の流れ図である。
【図３】本発明の実施形態による物体のＣＡＤモデルをレンダリングするための２球面上のサンプル回転角の概略図である。
【図４】線分としてモデリングされた画素の概略図である。
【図５】本発明によるマッチングコストを計算するための３次元距離変換及び積分画像表現の概略図である。
【発明を実施するための形態】
【００１７】
概観
図１及び図２に示すように、本発明の実施形態は、３Ｄ物体の姿勢を求めるためのシステム及び方法を提供する。用途の一例では、マルチフラッシュカメラ（ＭＦＣ）１１０をロボットアーム１２０上に配置する（参照により本明細書中に援用される米国特許第７，２０６，４４９号「Detecting silhouette edges in images」を参照）。カメラは、複数の物体１４０を含むシーン１３０の画像を取得することができる。カメラ及びロボットアームは、姿勢を求めるための方法１５０のステップを行うプロセッサ１６０の入出力インターフェースに接続することができる。
【００１８】
別の例では、通常のカメラがロボットアーム上に配置される。カメラは、複数の物体を含むシーンの画像を取得する。カメラ及びロボットアームは、姿勢を求めるための方法１５０のステップを行うプロセッサ１６０の入出力インターフェースに接続することができる。
【００１９】
さらに別の例では、画像内の検出する必要がある物体のエッジのデータベースを格納する。テスト画像が得られると、テスト画像内のエッジがまずＣａｎｎｙエッジ検出器を用いて計算される。次に、画像内の物体を検出し位置特定するために、本明細書中に記載される方法を用いて、このエッジ画像を物体のエッジのデータベースと照合する。
【００２０】
以下では最初の用途を詳細に説明するが、他の例もカバーするものとする。
【００２１】
オフライン処理
図２に示すように、オフラインの前処理段階２１０中に、コンピュータ支援設計（ＣＡＤ）モデル２１２を用いて、シーンにおける物体の取り得る姿勢毎に仮想奥行きエッジマップをレンダリングし（２１１）、データベース内に仮想姿勢テンプレート画像２１３を作成する。
【００２２】
オンライン処理
システムのオンライン動作中に、ＭＦＣは、８個の異なるフラッシュを用いて、シーンの実画像の集合、および、シーンが環境照明によって照明されているときの画像を、取得する（２２０）。
【００２３】
それらの画像から奥行きエッジマップが求められる（２３０）。面取りマッチングを用いて仮想姿勢テンプレート画像２１３が実エッジマップと照合され（２４０）、大まかな姿勢が求められる。
【００２４】
大まかな姿勢が、オンラインレンダリング（２５５）を用いて繰り返し精緻化される（２５０）。姿勢が求められると、ロボットアーム１２０は、何らかの動作を実行する（２６０）、例えば、物体１４０のうちの１つを操作することができる。
【００２５】
ＭＦＣは、アクティブ照明をベースとした、例えば、レンズの周囲に配置された８個の点光源を含むカメラである。ＭＦＣは、照明源の位置の変化により生じる影の変化を利用して、テクスチャのない物体又は鏡面反射する物体のような難しい物体に対しても奥行きエッジを与える。カメラの周囲の異なるＬＥＤが発光すると、物体が投じる影の位置は変化する。１つのフラッシュの影になっているが、他のフラッシュの影にはなっていない物体の画素は、輝度を大きく変化させる。この影の画素の輝度の変化を用いて、ビューに依存する奥行きエッジを検出し抽出することができる。
【００２６】
比画像
まず、ＭＦＣ画像によって取得された画像の集合から、環境照明のみで取得された画像を差し引き、画像Ｉｉを得る。これらの画像Ｉｉの中から、各画素位置における最大輝度値を見つけ出し、この最大輝度値を用いて最大照明画像を作成する。
Ｉｍａｘ（ｘ，ｙ）＝ｍａｘｉＩｉ（ｘ，ｙ）
【００２７】
次に、比画像をＲＩｉ＝Ｉｉ／Ｉｍａｘとして計算する。理想的には、影の領域の画素の比の値は、環境光源からの照明の寄与が除かれているため、ゼロとなるはずである。これに対し、影でない領域の画素の比の値は、該領域がすべてのフラッシュによって照明されているため、１に近くなるはずである。影の領域の画素と影の領域にない画素との間の遷移点が常に奥行きエッジとなる。各比画像に対し、この影の画素から影でない画素への遷移、すなわち０から１への遷移を検出するように設計されたＳｏｂｅｌフィルタを適用する。
【００２８】
物体検出
次に、本発明によるＭＦＣによって取得された奥行きエッジを用いて雑然としたシーンにおける物体を検出し位置特定するための方法を詳細に説明する。一般性を失うことなく、本方法を単一の物体に適用した場合を説明する。しかしながら、この仮定は説明を簡略化するためのものに過ぎない。実際には、本方法は複数の物体の姿勢を同時に位置特定し推定することができる。同様に、本方法は、ＭＦＣから取得された奥行きエッジに適用した場合について説明されるが、一般性を失うことなく、同方法は、従来のカメラから得られたテクスチャエッジにも適用されてもよい。
【００２９】
データベースの生成
物体のＣＡＤモデル２１２が与えられると、ソフトウェアでＭＦＣをシミュレートすることによって、奥行きエッジテンプレート２１３のデータベースを生成する（２１０）。シミュレーションでは、実ＭＦＣの内部パラメータを有する仮想カメラを原点に置き、光軸をワールド座標系のｚ軸に合わせる。８個の仮想フラッシュを、ｘｙ平面上の、原点を中心とし、カメラとＬＥＤ照明源との間の実基線に等しい半径を有する円上に等間隔に置く。
【００３０】
次に、物体のＣＡＤモデルを、ｚ軸上の、仮想カメラから距離ｔｚだけ離れた位置に置く。仮想フラッシュを１つずつ点灯し、投じた影を含む物体の８個のレンダリングを取得する。シーンの中の奥行きエッジを上述のように検出する（２１１）。
【００３１】
図３に示すように、さまざまな姿勢について、３Ｄ空間に埋め込まれた球体３０１の２Ｄ表面上の回転角θｘ及びθｙを均等にサンプリングする。テンプレートデータベースは、物体３０２のサンプリングされた回転に対して物体のＣＡＤモデルをレンダリングすることによって生成される。
【００３２】
任意の３Ｄ回転は、３つの直交軸を中心とする一連の３つの要素回転に分解することができる。これらの軸のうちの１つ目をカメラの光軸に合わせ、この軸を中心とする回転を面内回転θｚと呼ぶ。他の２つの軸はカメラの光軸に垂直な平面上にあり、これらの２つの軸を中心とする回転を面外回転θｘ及びθｙと呼ぶ。面内回転は観測画像を面内回転させるのに対し、面外回転の効果は物体の３Ｄ構造に依存する。この区別のため、物体の面外回転のみをデータベースに含める。図３に示すように２球面Ｓ２上で均等にｋ個の面外回転（θｘ及びθｙ）３０３をサンプリングし、これらの回転のそれぞれについて奥行きエッジテンプレート２１３を生成する。
【００３３】
方向性面取りマッチング
テンプレートマッチング２４０中に、データベース、及び仮想テンプレート２１３の奥行きエッジを実ＭＦＣ画像から得られた奥行きエッジに合わせる最適な２Ｄユークリッド変換ｓ∈ＳＥ（２）を探索する。２Ｄユークリッド変換は３つのパラメータで
【００３４】
【数１】
0005455873.tif 000002
【００３５】
として表され、ここで、
【００３６】
【数２】
0005455873.tif 000003
【００３７】
はｘ軸に沿った画像平面の平行移動であり
【００３８】
【数３】
0005455873.tif 000004
【００３９】
はｙ軸に沿った画像平面の平行移動であり、θｚは面内回転角である。
【００４０】
画素に与えられる回転は次のように表される。
【００４１】
【数４】
0005455873.tif 000005
【００４２】
面取りマッチングは、２つのエッジマップ間の最良の位置合わせを見つけるための技法である。Ｕ＝｛ｕｉ｝を仮想画像エッジマップの集合とし、Ｖ＝｛ｖｊ｝を実画像エッジマップの集合とする。Ｕ及びＶの間の面取り距離は、各画素ｕｉと、Ｖにおける該画素に最も近いエッジ画素との間の距離の平均により、次のように与えられる。
【００４３】
【数５】
0005455873.tif 000006
【００４４】
ここで、ｎ＝｜Ｕ｜である。
【００４５】
すると、２つのエッジマップ間の最良の位置合わせパラメータ
【００４６】
【数６】
0005455873.tif 000007
【００４７】
は次式によって与えられる。
【００４８】
【数７】
0005455873.tif 000008
【００４９】
面取りマッチングは、背景が雑然としていると信頼性が低くなる。精度を高めるために、面取りマッチングは、エッジ配向情報をマッチングコストに含めることができる。仮想画像エッジ及び実画像エッジは、離散的な配向チャネル（orientation channel）に量子化され、チャネル全体で個々のマッチングスコアが合計される。
【００５０】
これにより雑然としたシーンの問題は軽減されるが、コスト関数は依然として、配向チャネルの数に対して非常に敏感であり、チャネル境界において不連続になる。面取り距離には、仮想エッジと、実画像における該仮想エッジに最も近いエッジ画素との間の配向の平均差によって与えられる配向の不一致に関する追加コストを付加することができる。
【００５１】
配向の不一致の明示的な定式化の代わりに、方向性エッジ画素をマッチングするためにＲ３における画素までの面取り距離を一般化する。各エッジ画素ｘに方向項φ（ｘ）を付加すると、方向性面取りマッチング（ＤＣＭ）スコアは次のように表される。
【００５２】
【数８】
0005455873.tif 000009
【００５３】
ここで、λは重み係数である。
【００５４】
方向φ（ｘ）はπを法として計算され、配向誤差は、２方向間の最小円形差（circular difference）を次のように与える。
【００５５】
【数９】
0005455873.tif 000010
【００５６】
Ｖにおける最も近い画素がまず所与の仮想画素ｕについて位置特定され、コスト関数にそれらの配向の差が付加される。したがって、本発明のコスト関数は、位置誤差項及び配向誤差項の和を共に最小化する。
【００５７】
本発明のマッチングコストが、仮想テンプレートのエッジの両平行移動
【００５８】
【数１０】
0005455873.tif 000011
【００５９】
及び回転θｚの区分的に滑らかな関数であることは容易に検証することができる。したがって、本発明のマッチングは、エッジの欠落と小さな位置ずれのある雑然としたシーンにおける精度が、従来技術のマッチングよりも高い。
【００６０】
本発明者らの知る限りにおいて、従来の面取りマッチング手順の計算複雑性は、方向性項がない場合でも仮想テンプレートのエッジ画素数の一次式である。本発明は利点として、３Ｄ面取りマッチングスコアの正確な計算のために部分線形時間の手順を提供する。
【００６１】
探索の最適化
式（３）における探索は、データベースに格納されたｋ個のテンプレートのそれぞれについて平面ユークリッド変換
【００６２】
【数１１】
0005455873.tif 000012
【００６３】
の３つのパラメータにわたる最適化を必要とする。６４０×４８０の実画像及びｋ＝３００個のエッジテンプレートのデータベースの場合、総当たり探索は、式（４）のコスト関数の１０１０回を超える評価を必要とする。
【００６４】
したがって、本発明では探索の最適化を２段階で行う。すなわち、まず、部分線形時間の手順を用いてマッチングスコアを計算する。次に、仮想画像及び実画像の主な直線を位置合わせすることにより、３次元の探索問題を１次元のクエリ（queries）に変更する。
【００６５】
線形表現
シーンのエッジマップは非構造化バイナリパターンになっていない。その代わり、物体の輪郭は一定の連続性の制約に従い、さまざまな長さ、配向及び平行移動の線分をつなぐことによって保持される。エッジ画像（図４Ａを参照）内の画素をｍ個の線分の集まり（図４Ｂを参照）として表現する。位数がｎである画素の集合と比較して、この線形表現はより簡潔である。エッジマップを格納するにはＯ（ｍ）のメモリがあればよく、ここで、ｍ＜＜ｎである。
【００６６】
ランダムサンプルコンセンサス（ＲＡＮＳＡＣ）手順の変形を用いて、エッジマップの線形表現を計算する。この手順はまず、画素及びそれらの方向の小部分集合を選択することによってさまざまな直線を仮定する。直線のサポートは、小さな残差内で直線の式を満たし連続的な構造を形成する画素の集合によって与えられる。
【００６７】
サポートの最も大きな線分を保持し、サポートが数画素よりも小さくなるまで縮小集合を用いて手順を繰り返す。この手順は、一定の構造及びサポートを有する画素のみを保持するため、ノイズはフィルタリングされる。また、直線当てはめ手順により復元された方向は、画像勾配等の局所演算子と比べてより正確である。上述したＲＡＮＳＡＣに基づく方法に代えて、任意の適切な直線当てはめ技法を用いることもできる。
【００６８】
図４Ａは、図４Ｂに示すような３００個の線分を用いてモデリングされた１１５４２画素の集合を示す。
【００６９】
３次元距離変換
式（４）で与えられるマッチングスコアは、仮想テンプレートのエッジ画素毎に、位置項及び配向項全体で最小コストの一致を見つけることを必要とする。したがって、総当たり手順の計算複雑性はテンプレート画素数及び実画像のエッジ画素数の二次式である。
【００７０】
図５に要約して示すように、本発明は、３次元距離変換表現（ＤＴ３）を与えて線形時間におけるマッチングコストを計算する。この表現は、１番目の次元及び２番目の次元が画像平面上の位置であり、３番目の次元が量子化されたエッジ配向である３次元画像テンソルである。
【００７１】
本発明では、エッジ配向を３番目の次元として用いる。エッジ配向５１０は、Ｎ個の離散値５２０、ｘ軸、ｙ軸、及びエッジ配向
【００７２】
【数１２】
0005455873.tif 000013
【００７３】
に量子化される。これが２次元の画素座標と共に３Ｄ格子画素集合５３０を形成する。量子化によりエッジ配向の精度がいくらか低下する。しかし、姿勢マッチングの部分は最初の大まかな姿勢推定値を得る手段に過ぎないため、深刻なものではない。線分の正確な配向は、姿勢の精緻化の際に用いられる。
【００７４】
詳細には、エッジ配向は、［０  π]の範囲内でｑ個の離散的な配向チャネル
【００７５】
【数１３】
0005455873.tif 000014
【００７６】
に均等に量子化される。テンソルの各要素は、位置及び配向の結合空間におけるエッジ画素までの最小距離を次のように符号化する。
【００７７】
【数１４】
0005455873.tif 000015
【００７８】
ここで、
【００７９】
【数１５】
0005455873.tif 000016
【００８０】
は配向空間において
【００８１】
【数１６】
0005455873.tif 000017
【００８２】
のφ（ｘ）に最も近い量子化レベルである。
【００８３】
ＤＴ３テンソルは、画像全体のＯ（ｑ）回のパスで計算することができる。式（６）は次のように書き直すことができる。
【００８４】
【数１７】
0005455873.tif 000018
【００８５】
ここで、
【００８６】
【数１８】
0005455873.tif 000019
【００８７】
はＶにおいて配向が
【００８８】
【数１９】
0005455873.tif 000020
【００８９】
であるエッジ画素の２次元距離変換である。初めに、従来の手順５４０を用いてｑ個の２次元距離変換を計算する。次に、位置毎に別々に、配向コストに関して２番目の動的問題を解く（５５０）ことによって、式（７）のＤＴ３ｖテンソルを計算する。
【００９０】
３Ｄ距離変換表現ＤＴ３Ｖを用いて、任意のテンプレートＵの方向性面取りマッチングスコアを次のように計算することができる。
【００９１】
【数２０】
0005455873.tif 000021
【００９２】
距離変換の積分
ＬＵ＝｛ｌ［ｓｊ，ｅｊ］｝ｊ＝１．．．ｍをテンプレートのエッジ画素Ｕの線形表現とする。ここで、ｓｊは第ｊの直線の開始位置であり、ｅｊは第ｊの直線の終了位置である。表記を簡略化するために、直線をインデックスｌｊのみで呼ぶ場合がある。線分はｑ個の離散的なチャネル
【００９３】
【数２１】
0005455873.tif 000022
【００９４】
においてのみ方向を有するものと仮定し、線形表現を計算する際はこれを徹底する。線分上のすべての画素を、直線
【００９５】
【数２２】
0005455873.tif 000023
【００９６】
の方向である同一の配向と関連付ける。したがって、方向性面取りマッチングスコアは次のようになる。
【００９７】
【数２３】
0005455873.tif 000024
【００９８】
この式では、方向が
【００９９】
【数２４】
0005455873.tif 000025
【０１００】
５６０である線分の画素を合計するために、ＤＴ３Ｖテンソルの第ｉの配向チャネルのみを評価する。
【０１０１】
積分画像は、画素の領域合計の高速計算のために用いられる中間画像表現である（参照により本明細書中に援用される米国特許第７，４５４，０５８号「Method of extracting and searching integral histograms of data samples」を参照）。本発明では、積分距離変換表現（ＩＤＴ３ｖ）のテンソルを与えて、Ｏ（１）回の演算における任意の線分全体のコストの合計を評価する。配向チャネルｉ毎に、
【０１０２】
【数２５】
0005455873.tif 000026
【０１０３】
５６０に沿って１方向性積分を計算する。
【０１０４】
ｘ０を、画像境界と、ｘを通り方向が
【０１０５】
【数２６】
0005455873.tif 000027
【０１０６】
である直線との交点とする。ＩＤＴ３Ｖテンソルの各成分は次式によって与えられる。
【０１０７】
【数２７】
0005455873.tif 000028
【０１０８】
ＩＤＴ３Ｖテンソルは、ＤＴ３Ｖテンソル全体の１回のパスで求めることができる。この表現を用いて、任意のテンプレートＵの方向性面取りマッチングスコアを、
【０１０９】
【数２８】
0005455873.tif 000029
【０１１０】
によりＯ（ｍ）回の演算で計算することができる。
【０１１１】
ｍ＜＜ｎであるため、マッチングの計算複雑性はテンプレート画素数ｎの一次式以下である。
【０１１２】
Ｏ（ｍ）の複雑性は計算回数の上限である。姿勢の推定のために、最良の仮説のみを保持したい。テンプレートの直線をそのサポートに対して順序付け、サポートが最大である直線から合計を開始する。コストが現在の最良の仮説よりも高い場合、この仮説は合計中に排除される。線分のサポートは指数関数的減衰を示すため、大部分の仮説では、数回の算術演算しか行われない。
【０１１３】
１次元探索
平面ユークリッド変換の３つのパラメータにわたる最適な姿勢の探索は計算集約的であり、リアルタイムアプリケーションでの実用には向かない。線形表現は、探索空間の大きさを縮小する効率的な方法を提供する。観測によると、テンプレート画像及び実画像の線分は、テンプレートの姿勢の実際の推定値とほぼ完璧に合わせられる。また、この手順はサポートの大きい線分ほど有利であるため、直線当てはめ中、テンプレート画像及び実画像の主な直線が非常に高い信頼度で検出される。
【０１１４】
本発明では、テンプレート線分及び実線分をそれらのサポートに基づいて順序付け、数本の主な直線のみを保持して探索を導く。テンプレートを初めに回転及び平行移動して、テンプレートの仮想線分を実画像の線分の方向に合わせ、該仮想線分の終了画素が実線分の開始画素に一致するようにする。
【０１１５】
次に、テンプレートを実線分の方向に沿って平行移動し、２つの線分が重なる位置のみにおいてコスト関数を評価する。この手順は、３次元探索を数方向のみに沿った１次元探索に変える。探索時間は、画像の大きさに対して不変であり、仮想画像及び実画像の直線数とそれらの長さの関数に過ぎない。
【０１１６】
姿勢の精緻化
姿勢の精緻化は任意の（optional）ステップであり、姿勢の推定以外の用途には適用されないことを明示しておかねばならない。上述したコンピュータビジョン用途では、姿勢の精緻化ステップはない。
【０１１７】
最小コストテンプレート及びその面内変換パラメータ
【０１１８】
【数２９】
0005455873.tif 000030
【０１１９】
は、物体の３Ｄ姿勢の大まかな推定値を与える。θｘ，θｙを面外回転角とし、ｔｚをカメラからの距離として、仮想画像のレンダリングに用いる。カメラ較正行列Ｋを用いて面内平行移動パラメータを３Ｄに逆射影し、３つのオイラー角（θｘ，θｙ，θｚ）及び３Ｄ平行移動ベクトル（ｔｘ，ｔｙ，ｔｚ）Ｔにより物体の最初の３Ｄ姿勢ｐ０を得る。
【０１２０】
３Ｄ姿勢ｐは次のように行列として書き表すこともできる。
【０１２１】
【数３０】
0005455873.tif 000031
【０１２２】
ここで、Ｒｐはｘ−ｙ−ｚ軸を中心とする一連の３回の回転
【０１２３】
【数３１】
0005455873.tif 000032
【０１２４】
によって計算される３×３直交行列であり、ｔｐは３次元平行移動ベクトルである。
【０１２５】
最初の姿勢推定値の精度は、データベース内に含められる面外回転の離散集合によって制限される。この姿勢推定値を精緻化する連続的な最適化方法を説明する。提案する方法は、反復最近点（ＩＣＰ）及びガウス・ニュートン最適化の組み合わせである。
【０１２６】
単一ビューからの３次元姿勢推定は不良設定問題である。姿勢推定における不確定性を最小化するために、２つのビューによる手法を用いる。この手法では、ロボットアームを第２の位置へ移動させて、シーンをＭＦＣで再び撮像する。２つのビューにおいて検出されたエッジ画素は２つの集合により次のように与えられる。
【０１２７】
【数３２】
0005455873.tif 000033
【０１２８】
Ｍ（ｊ）∈ＳＥ（３），ｊ∈｛１，２｝を、ワールド座標系における２つのカメラの位置を決める３Ｄ剛体運動行列とし、Ｐ＝（Ｋ  ０）を３×４射影行列とする。最適化手順は、検出された画素ｖ（ｊ）ｉと３Ｄ  ＣＡＤモデルの対応する３Ｄ画素
【０１２９】
【数３３】
0005455873.tif 000034
【０１３０】
との間の射影誤差の２乗和を両方のビューにおいて同時に最小化する。
【０１３１】
【数３４】
0005455873.tif 000035
【０１３２】
３Ｄ画素
【０１３３】
【数３５】
0005455873.tif 000036
【０１３４】
の射影は同次座標で表され、この式において、それらの画素が２Ｄ座標に変換されているものと仮定する。本発明では、画像平面上の最も近い画素の割り当てにより３Ｄ−２Ｄ画素の対応を見つける。この２つのカメラの設定をシミュレートし、現在の姿勢推定値ｐに対して３Ｄ  ＣＡＤモデルをレンダリングする。Ｕ（ｊ）＝｛ｕ（ｊ）ｉ｝、ｊ∈｛１，２｝を２つの合成ビュー内の検出されたエッジ画素の集合とし、
【０１３５】
【数３６】
0005455873.tif 000037
【０１３６】
を３Ｄ  ＣＡＤモデルの対応する画素集合とする。Ｕ（ｊ）の画素毎に、方向性マッチングスコア
【０１３７】
【数３７】
0005455873.tif 000038
【０１３８】
に関してＶ（ｊ）において最も近い画素を探索し、画素の対応
【０１３９】
【数３８】
0005455873.tif 000039
【０１４０】
を確立する。
【０１４１】
式（１３）で与えられる最小２乗誤差の非線形関数は、ガウス・ニュートン法を用いて最小化される。最初の姿勢推定値ｐ０から始めて、反復ｐｔ＋１＝ｐｔ＋Δｐにより推定値を改良する。更新ベクトルΔｐは、標準方程式（ＪＴｅＪｅ）Δｐ＝ＪＴｅεの解によって与えられ、ここで、εは式（１３）において合計された誤差項の各々のＮ次元ベクトルであり、Ｊｅはｐｔにおいて評価したｐに対するεのＮ×６ヤコビアン行列である。
【０１４２】
対応問題及び最小化問題を収束するまで反復して解く。マッチング手順により与えられる最初の姿勢推定値は通常、真の解に近いため、一般的に収束には５回〜１０回の反復で十分である。
【０１４３】
本発明を、好ましい実施形態の例として説明してきたが、本発明の精神及び範囲内で他のさまざまな適合及び変更を行えることが理解されるべきである。したがって、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することが、添付の特許請求の範囲の目的である。
【図１】
0005455873.tif 000041
【図２】
0005455873.tif 000042
【図３】
0005455873.tif 000043
【図４】
0005455873.tif 000044
【図５】
0005455873.tif 000045