物体姿勢推定方法、物体姿勢推定装置、物体推定姿勢精緻化方法、およびコンピューター可読媒体
【課題】物体を、ロボットの搭載カメラから見える通りのその姿勢にかかわらず認識することができるようにする。
【解決手段】物体を包含する画像を入力し、入力画像の２値マスクを作成、入力画像の２値マスクからシングレットのセットを抽出する。各シングレットは、入力画像内の物体の内側および外側輪郭内にある点を表す、抽出することと、シングレットのセットを連結し、デュプレックス行列として表されるメッシュにし、候補姿勢のセットを作るべく２つのデュプレックス行列を比較するこし、物体姿勢推定値によって、入力画像から物体の姿勢が推定され、次に、物体姿勢推定が記憶される。物体の推定姿勢は、カメラのパラメーターの入力、物体のモデルを物体の仮想画像に投影、初期姿勢パラメーターを新しい姿勢パラメーターに更新、エネルギー関数の最小化によって精緻化される。
【解決手段】物体を包含する画像を入力し、入力画像の２値マスクを作成、入力画像の２値マスクからシングレットのセットを抽出する。各シングレットは、入力画像内の物体の内側および外側輪郭内にある点を表す、抽出することと、シングレットのセットを連結し、デュプレックス行列として表されるメッシュにし、候補姿勢のセットを作るべく２つのデュプレックス行列を比較するこし、物体姿勢推定値によって、入力画像から物体の姿勢が推定され、次に、物体姿勢推定が記憶される。物体の推定姿勢は、カメラのパラメーターの入力、物体のモデルを物体の仮想画像に投影、初期姿勢パラメーターを新しい姿勢パラメーターに更新、エネルギー関数の最小化によって精緻化される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物体の姿勢を推定する物体の物体姿勢推定方法、物体姿勢推定装置、物体推定姿勢精緻化方法、およびコンピューター可読媒体に関する。
【背景技術】
【０００２】
今日の多くの工業環境では、部品の組み立ておよび製造のためにロボットが用いられている。これらのロボットは、それらに視覚を与える１つ以上のカメラ、例えばＣＣＤおよびＣＭＯＳ、を備えている。多くの場合、物体（すなわち部品）は容器に入っている。ロボットは、製品を組み立てるべく物体を拾い上げることができるように、容器内の物体／部品を認識しなければならない。しかし、物体は様々な姿勢（位置、配向、回転）をとり得る。従って、ロボットは部品をその姿勢にかかわらず認識するように訓練されなければならない。
本発明は、ロボットが訓練されて、物体を、ロボットの搭載カメラから見える通りのその姿勢にかかわらず認識することができるよう、２次元画像（例えばカメラ画像）から３次元（ｔｈｒｅｅ−ｄｉｍｅｎｓｉｏｎａｌ、３Ｄ）物体の姿勢を推定することに関する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本技術分野において周知であるように、ロボットは、カメラの画像から物体を特定しようとするソフトウェアを含む。従って、このようなソフトウェアは、ロボットのカメラによって取り込まれた画像と比較するために用いる物体画像のロバスト且つ正確なデータベースを有することが重要である。
【課題を解決するための手段】
【０００４】
本発明の１つの態様は、入力画像から物体の姿勢を推定し、物体姿勢推定を記憶する方法および装置であって、該方法および装置は、物体を包含する画像を入力することと、入力画像の２値マスクを作成することと、入力画像の２値マスクからシングレットのセットを抽出することであって、各シングレットは、入力画像内の物体の内側および外側輪郭内にある点を表す、抽出することと、シングレットのセットを連結して、デュプレックス行列として表されるメッシュにすることと、候補姿勢のセットを作るべく２つのデュプレックス行列を比較することと、物体姿勢推定値を作り、該物体姿勢推定値を記憶することと、を含む、方法および装置である。
【０００５】
本発明の一実施形態では、物体の複数の画像が入力され、各画像は、該複数の画像の互いにおける視像とは異なる、物体の視像を包含する。
１つの態様は、物体の複数の画像の各々における視像を、物体のためのＣＡＤモデルを用いて生成することを含む。
別の態様は、物体の複数の画像の各々における視像を、カメラを備えたロボットを用いて生成することを含む。
【０００６】
本発明のさらなる態様は、入力画像内の物体を検出し、物体のバウンディングボックスを計算することを含む。
別の態様は、物体の内側および外側輪郭を抽出することを含む。
【０００７】
本発明の他の実施形態では、物体姿勢推定値は、該姿勢推定値をエネルギー関数の最適化としてモデル化することによって精緻化される。
１つの態様では、本発明は、エネルギー関数におけるエネルギー値を最小化するべく姿勢推定値を反復的に計算する。
別の態様は、姿勢推定値を反復的に計算するために速度スクリューを計算する。
別の態様は、ＯｐｅｎＧＬ、ＤｉｒｅｃｔＸ、レイトレーシングなど等のレンダリングアプリケーションプログラミングインタフェース（ａｐｐｌｉｃａｔｉｏｎ ｐｒｏｇｒａｍｍｉｎｇ ｉｎｔｅｒｆａｃｅ、ＡＰＩ）を用いて物体のモデル輪郭曲線を仮想画像に投影する。
【０００８】
本発明のさらなる実施形態では、物体姿勢推定値は、推定姿勢をとる物体の画像、物体のモデル、および推定姿勢をとる物体の画像を撮るために用いられるカメラのパラメーターを入力することと、２値マスク画像および画像深さ情報を得るべく、カメラのパラメーターおよび初期姿勢パラメーターを用いて物体のモデルを物体の仮想画像に投影することと、２値マスク画像および画像深さ情報を用いて初期姿勢パラメーターを新しい姿勢パラメーターに更新し、エネルギー関数を最小化するべくまたは反復の最大数に達するまで新しい姿勢パラメーターを反復的に更新することと、によって精緻化される。
【０００９】
本発明の別の態様は、コスト関数を用いて物体の内部および外部の平均値を計算することと、２値マスク画像から物体の輪郭Ｃを計算し、画像深さ情報を用いて３Ｄ輪郭点を計算することと、を含む。
【００１０】
さらなる態様は、輪郭点についての、ｘおよびｙ方向における勾配∇Ｔ（ｘ，ｙ）を計算することと、画像ヤコビ行列を計算することと、ガウス・ニュートン法を用いて勾配流および速度スクリューを計算することと、を含む。
【００１１】
本発明の別の態様は、速度スクリューおよび所与のステップワイズを用いて相対変位を計算することを含む。
【００１２】
添付の図面と併せて以下の記載および請求項を参照することによって、本発明のより完全な理解とともに他の目的および達成が明らかになり理解されるようになる。
【図面の簡単な説明】
【００１３】
【図１】図１は、本発明を利用するための物体処理デバイスおよびシステムの概略的なブロック図である。
【図２】図２は本発明の一般的方法のフローチャートである。
【図３】図３は、図２に示される方法の物体抽出段階のフローチャートである。
【図４】図４はピンホールカメラモデルにおける透視投影を示す。
【図５】図５はＯｐｅｎＧＬ投影および正規化デバイス座標（Ｎｏｒｍａｌｉｚｅｄ Ｄｅｖｉｃｅ Ｃｏｏｒｄｉｎａｔｅ、ＮＤＣ）を示す。
【図６】図６（ａ）ないし（ｄ）は、物体の境界に対する投影モデル曲線の位置の４つのすべてのあり得る場合を示す。
【図７】図７はカメラの運動の合成を示す。
【発明を実施するための形態】
【００１４】
以下の詳細な説明では、例示の目的で本発明の実施形態例を示す添付の図面に言及がなされる。図面において、いくつかの図全体にわたり、同じ符号は実質的に同種の構成要素を示す。これらの実施形態は、当業者が本発明を実施することを可能とするよう、十分詳しく記載されている。他の実施形態が利用されてもよく、構造的、論理的および電気的変更が、本発明の範囲から逸脱することなくなされてもよい。さらに、本発明の種々の実施形態は、異なるものであっても、必ずしも相互排他的であるわけではないことを理解されたい。例えば、１つの実施形態において記載されている特定の特徴、構造、または特性が他の実施形態内に含まれてもよい。従って、以下の詳細な説明は限定の意味で捉えられてはならず、本発明の範囲は、添付の請求項、およびこれらの請求項が権利を与えられる同等物の全範囲によってのみ定義される。
【００１５】
概して、実施形態例は、画像、とりわけ、１つ以上の物体のデジタル画像、を分析するための方法、デバイス、およびコンピューター可読媒体に関する。画像は、２Ｄ画像で表される対応する３Ｄ物体の姿勢（位置および配向）を推定するべく分析される。実施形態例は画像の２値マスクを作成し、２値マスクからシングレットのセットを抽出する。各シングレットは、物体の内側および外側輪郭内にある点を表すことになる。シングレットのセットは連結され、デュプレックス行列として表されるメッシュにされる。２つのデュプレックス行列が比較され、候補姿勢のセットを作る。その後、物体姿勢推定値が作られ、例えばロボットによる部品組み立てのための視覚システムにおける、後の利用のために記憶される。
【００１６】
図１に、物体処理デバイス１００の例の略図が示されている。物体処理デバイス１００は介在インターフェース１０２を介してホストコンピューター１５０とデータを交換する。ホストコンピューター１５０上にはアプリケーションプログラムおよび物体処理デバイスドライバーがアクセスのために記憶されてもよい。アプリケーションプログラムから画像取得コマンドが受信されると、例えば、物体処理デバイスドライバーはコマンドデータの、物体処理デバイス１００に適したフォーマットへの変換を制御し、変換されたコマンドデータを物体処理デバイス１００に送信する。ドライバーは同様に、物体処理デバイス１００から種々の信号およびデータを受信して解釈し、ホストコンピューター１５０を介してユーザーに必要な情報を提供する。
【００１７】
ホストコンピューター１５０によってデータが送信されると、インターフェース１０２はデータを受信し、それを、ＲＡＭ１０４の一部を形成する受信バッファー内に記憶する。ＲＡＭ１０４は、例えばアドレス指定を通じて、多数の区画に分割され、受信バッファーまたは送信バッファー等の各種のバッファー群として割り当てられ得る。デジタル画像データ等のデータも物体処理デバイス１００によって取り込み機構（単数または複数）１１２、フラッシュＥＥＰＲＯＭ１１０、またはＲＯＭ１０８から得られ得る。取り込み機構（単数または複数）１１２は例えばカメラであり、プリンター等のデバイスの製造および／または組み立てにおいて用いられる部品等の１つ以上の物体を撮影することによってデジタル画像を生成することができる。カメラ１１２は、例えばロボット１１６、または人間によって制御され得るか、あるいは例えばコンピューター１５０によって自動制御され得る。次に、物体（単数または複数）のデジタル画像はＲＡＭ１０４の受信バッファーまたは送信バッファー内に記憶され得る。
【００１８】
プロセッサー１０６は、例えばＲＯＭ１０８上またはフラッシュＥＥＰＲＯＭ１１０上に記憶されているコンピューター実行可能命令を用い、例えば方法２００（図２）等の、或る機能または一群の機能を遂行する。方法２００は本願明細書において以下でより詳細に説明される。ＲＡＭ１０４の受信バッファー内のデータがデジタル画像である場合には、例えば、プロセッサー１０６はデジタル画像に対して方法２００の方法手続きを実行し、デジタル画像内の特徴を抽出し、抽出された特徴に基づき画像をさらに解析することができる。次に、画像が、例えばＬＣＤディスプレイ等のディスプレイ１１４上に表示されたり、または例えば、プリンター１６２上での印刷、プロジェクター１６４を用いた投影、またはハードディスク１６０上への記憶のためにホストコンピューター１５０に転送されたりする前に、イメージングパイプラインにおけるさらなる処理がデジタル画像に対して遂行されてもよい。
【００１９】
本願明細書において開示されている方法例２００およびその変形は、非一時的コンピューター可読媒体であって、その上に記憶されたコンピューター実行可能命令またはデータ構造を運ぶまたは有するための媒体を用いて実装され得る。このようなコンピューター可読媒体は、汎用または専用コンピューターのプロセッサーによってアクセスされ得る任意の利用可能な媒体であることができる。例として、ただし限定ではなく、このようなコンピューター可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭまたは他の光ディスクストレージ、磁気ディスクストレージまたは他の磁気記憶デバイス、あるいはコンピューター実行可能命令またはデータ構造の形式でプログラムコードを運ぶまたは記憶するために用いられ得るとともに、汎用または専用コンピューターのプロセッサーによってアクセスされ得る任意の他の媒体を含むことができる。以上のものの組み合わせもコンピューター可読媒体の範囲に含まれるべきである。
【００２０】
コンピューター実行可能命令は、例えば、汎用コンピューターまたは専用コンピューターのプロセッサーに或る機能または一群の機能を遂行させる命令およびデータを含む。本願明細書においては、主題は方法手続きに固有の言葉で記載されているが、添付の請求項において定義される主題は、本願明細書において記載されている特定の手続きに必ずしも限定されるものではないことを理解されたい。むしろ、本願明細書において記載されている特定の手続きは、請求項を実装する形態の例として開示されている。
【００２１】
専用コンピューターの例としては、デジタルカメラ（その例としては、日本、長野県諏訪市大和に本社を置くセイコーエプソン社製のエプソンＲ−Ｄ１デジタルカメラが挙げられるが、それに限定されるものではない）、デジタルカムコーダー、プロジェクター、プリンター、スキャナー、複写機、ポータブルフォトビューアー（その例としてはセイコーエプソン社製のエプソンＰ−３０００もしくはＰ−５０００ポータブルフォトビューアーが挙げられるが、それらに限定されるものではない）、またはポータブルムービープレイヤー、あるいはプリンター／スキャナー／複写機の組み合わせ（その例としてはセイコーエプソン社製のエプソンスタイラスフォトＲＸ５８０、ＲＸ５９５、もしくはＲＸ６８０、エプソンスタイラスＣＸ４４００、ＣＸ７４００、ＣＸ８４００、もしくはＣＸ９４００Ｆａｘ、およびエプソンＡｃｕＬａｓｅｒ（登録商標）ＣＸ１１ＮＦが挙げられるが、それらに限定されるものではない）またはプリンター／スキャナーの組み合わせ（その例としてはすべてセイコーエプソン社製のエプソンＴＭ−Ｊ９０００、ＴＭ−Ｊ９１００、ＴＭ−Ｊ７０００、ＴＭ−Ｊ７１００、およびＴＭ−Ｈ６０００ＩＩＩが挙げられるが、それらに限定されるものではない）またはデジタルカメラ／カムコーダーの組み合わせ等の、それらの何らかの組み合わせ等の画像処理デバイスが挙げられる。
【００２２】
入力画像の仕様
図２を参照すると、方法２００における最初のステップは画像を入力することである（ステップ２１０）。入力画像は、カメラ（取り込み機構）１１２を操作するロボット１１６によって生成され得る。入力画像が１つの物体を包含しているならば、このとき、それは好ましくは画像エリアの少なくとも１０％を占めなければならない。画面内に１つを超える物体があるならば、対象となっている物体は好ましくは画像（画面）内の他のいずれの物体よりも少なくとも２倍は大きくなければならない。入力画像は、例えば、ＲＡＭ１０４またはハードディスク１６０内に記憶されている物体のＣＡＤモデルであることもできる。好ましい実施形態では、以下において記載されるように、物体の複数の画像が入力され、解析される。複数の画像の各々は好ましくは、他の画像の各々に示される視像とは異なる、物体の視像を包含する。これらの複数の画像は、ＣＡＤモデル、および／またはカメラを操作するロボット１１６を用いて生成され得る。
【００２３】
物体位置特定および抽出
本発明の物体位置特定（ステップ２１２）および物体抽出（ステップ２１４）段階は、画像または画面内に存在する物体を検出し、そのバウンディングボックスを計算する。物体抽出段階は物体の内側輪郭および外側輪郭の両方を抽出する。これらのステップ／段階は図３においてより詳細に示される。
【００２４】
一般的に言えば、これらのステップは、無地の背景上に１つ以上の物体を包含する単一チャネル画像３１０（図３）を処理する。これらのステップは基本的に画像内の活動のエリアを発見するものであり、従って、背景内のアーチファクトに敏感であってよい。入力画像内の物体は好ましくは単色であり且つ背景と物体との間の最小限のコントラストを有する。背景の色または異なる物体の色に対する追加の制限はない。物体のうちのあるものは背景よりも暗くてよく、あるものはそれよりも明るくてよい。物体は同様の色を有してもよいしまたは異なる色を有してもよい。
【００２５】
活動計算（図３、ステップ３１２）
活動計算ステップの間、画像３１０はサイズＳｘＳのブロックに分割される。Ｓは画素の数である。例として、Ｓは８である。ただし、特定の環境に従って、異なる値が選択され得る。この設定パラメーターＳは本願明細書においてＡＣＴＩＶＩＴＹ．ＳＣＡＬＥと呼ばれる。次に、本ステップは各ブロックについての標準偏差および平均強度を計算し、２つの行列、標準（ｓｔｄ）および平均（ａｖｅ）、として出力を返す。
【００２６】
活動的エリア選択（ステップ３１４）
本ステップでは、本発明は行列ｓｔｄの要素を閾値と比較し、閾値を超える要素を特定する。閾値は特定の環境のために選択され得る。例えば、これは色の閾値であり得よう。色深度を表すために８ビットが用いられるならば、このとき、閾値は０と２５５との間のどこかに設定されよう。理解されるように、活動的エリア選択ステップは、無地の背景と対照的にカラー物体に対応する画素ブロックを特定する。選択された活動閾値を超えると特定された要素は活動マップに入れられる。
【００２７】
領域解析（ステップ３１６）
領域解析ステップ３１６は、前のステップ３１４において作られた活動マップに対するブロブ解析を遂行する。本ステップにおいて用いられるパラメーターは、ＯＢＪＥＣＴＳ．ＳＩＺＥ．ＭＩＮ（デフォルト値は０．００１）およびＯＢＪＥＣＴＳ．ＳＩＺＥ．ＭＡＸ（デフォルト値は０．１）によって制御されるサイズ、ならびに候補領域の数ＯＢＪＥＣＴＳ．ＣＯＵＮＴ（デフォルト値は８）である。これらの設定パラメーターを画素からブロックに変換するために、サイズ制限はまずＡＣＴＩＶＩＴＹ．ＳＣＡＬＥの２乗で除される。領域解析ステップは各物体のためのバウンディングボックス、ならびにその１次および２次平均および面積を返す。
【００２８】
領域解析ステップの間、各領域はインデックスを与えられる。領域のインデックスは１から始まるが、必ずしも連続したものとなるわけではない。換言すると、サイズ制約に一致しなかった領域に対応する、欠けているインデックス値がある。インデックスマップは、各ブロックに付与されたインデックスを保持する。このマップは境界マップと呼ばれる。境界マップ内の、非ゼロのインデックスが与えられたブロックはいずれも境界ブロックである。残りのブロックは背景であるかまたは物体の内部を表すかのいずれかである。内部ブロックは、本願明細書において後に記載されるステップ３２０において検出される。
【００２９】
閾値計算（ステップ３１８）
閾値計算ステップ３１８は、各領域のための境界ブロックの内容を前景と背景とに分けるための最適閾値を求める。この手順は、領域毎に個別になされる以下の段階を通じて実行される。ここで、Ｉは、領域のための境界ブロックのうちの１つに入るすべての点のセットである。
【００３０】
１．Ｉの内容についての２５６ビンヒストグラムを作る。
２．Ｉの平均としてｔを計算する。
３．ｔの値を用いてＩを閾値処理し、Ｉ+およびＩ-を作る。
４．Ｉ+の平均としてｔ+を計算する。
５．Ｉ-の平均としてｔ-を計算する。
６．（ｔ+＋ｔ-）／２としてｔ*を計算する。
７．ｔとｔ*との間の差が１未満であれば、このときは、ｔを閾値として返し、さもなければ、ｔ＝ｔ*と設定し、３に行く。
本段階において計算された閾値（ＯＳＭＸ＿ＴＨＲＥＳＨＯＬＤ）は後のステップにおいて用いられる。
【００３１】
閾値計算ステップ３１８は、物体は背景よりも暗いのかまたはその逆であるのかも判定する。この判定は、各物体のためのバウンディングボックスの境界にある画素を調べ、閾値を超えるそれらの数を求めることに基づく。この数が、集計された画素の総数の半分を超えるならば、このとき、物体は背景よりも暗いと判定される。この情報ＯＳＭＸ＿ＩＮＶＥＲＳＥは後のステップにおいて用いられる。例えば、ＯＳＭＸ＿ＩＮＶＥＲＳＥは、物体が背景よりも暗ければ１に、明るければ０に設定され得よう。
【００３２】
内部検出（３２０）
内部検出ステップ３２０は境界マップを用い、内部マップを構築する。この手順は、すべてゼロの内部マップより開始し、領域毎に、そのバウンディングボックス内の各ブロックについて以下の操作を遂行する。
１．ブロックが境界マップ内になく且つ、ブロックについての平均が、（ＯＥ＿ＩＮＶＥＲＳＥがどのように設定されているかに依存して）ＯＥ＿ＴＨＲＥＳＨＯＬＤを上回りまたは下回り且つ、このブロックが境界マップ内に少なくとも１つの４連結隣接ブロックを有するならば、このときは、このブロックを内部マップ内に標識する。
【００３３】
境界閉塞（ステップ３２２）
境界マップが内部マップを包囲しないということがあり得る。その結果、次に記載される物体抽出段階の性質により、抽出された物体内に、望ましくない「くぼみ」が出現する場合がある。この問題を解決するために、境界閉塞ステップ３２２は、各領域のバウンディングボックス内で以下の操作を遂行することによって各領域のための境界マップを閉塞する。
１．ブロックが境界マップ内にもまたは内部マップ内にもなく且つ、それが内部マップ内に少なくとも１つの４連結隣接ブロックを有するならば、このときは、このブロックを境界マップ内に標識する。
【００３４】
物体抽出（ステップ３２４）
物体抽出ステップ３２４は、境界マップおよび内部マップに基づき物体を抽出する。この手順は各物体についてそれ自身のバウンディングボックス内で以下の操作を遂行する。
１．このブロックが内部マップ内に標識されているならば、このときは、それに対応するすべての画素を物体に属するものとして設定する。
２．このブロックが境界マップ内に標識されているならば、このときは、ブロックについての平均が、（ＯＥ＿ＩＮＶＥＲＳＥがどのように設定されているかに依存して）ＯＥ＿ＴＨＲＥＳＨＯＬＤを上回るまたは下回るならば、それに対応するすべての画素を物体に属するものとして設定する。
【００３５】
デュプレット作成（図２、ステップ２１６）
デュプレット作成は、実際の画像が用いられる、本発明における最後のステップである。本段階の後では、作業はデュプレット行列ならびに他の特徴点およびベクトルに対してなされる。
【００３６】
デュプレット作成は、以下に各々記載される、輪郭追跡、シングレット検出、およびデュプレット作成の３つのサブブロックを包含する。
【００３７】
輪郭追跡
輪郭追跡は、物体抽出段階によって返されたすべての輪郭を追跡する手順である。本段階において収集される情報はシングレット検出手順において用いられる。本発明においては、特定のアルゴリズムに限定されない任意の周知の輪郭追跡アルゴリズムが用いられ得る。利用されてよい輪郭追跡アルゴリズムの例としては矩形追跡、ムーア近傍、放射状走査が挙げられる。好ましい実施形態では、Ｔｈｅｏ Ｐａｖｌｉｄｉｓのアルゴリズムが用いられる。
【００３８】
シングレット検出
本段階は、特定の環境のために選択され得る２つのパラメーターＴＲＡＣＥ＿ＷＩＮＤＯＷおよびＳＩＮＧＬＥＴ＿ＤＩＳＴＡＮＣＥに依存する。これらの両パラメーターのためのデフォルト値は１２画素である。ＴＲＡＣＥ＿ＷＩＮＤＯＷの２倍よりも長いすべての輪郭について、以下の手順が輪郭上の点毎に実行される。
１．輪郭上の点の周りのＴＲＡＣＥ＿ＷＩＮＤＯＷの点についての平均のＸおよびＹ座標を求める。
２．輪郭上の点を、ＴＲＡＣＥ＿ＷＩＮＤＯＷだけ左および右に離れた２つの点に連結する。
３．２つの角度を求め、それらを入射角度および出射角度と呼ぶ。
４．入射角度および出射角度を表す２つのベクトルの内積を求める。この内積の符号を変更し、それを曲率と呼ぶ。
５．この点がその周りのＳＩＮＧＬＥＴ＿ＤＩＳＴＡＮＣＥの点群内の最大曲率を有するならば、その点をシングレットとして標識する。
６．各シングレットについてのＸおよびＹ座標を、入射および出射角度ならびにそれらに対応する曲率とともに記憶する。
【００３９】
デュプレット作成
デュプレット作成は、検出されたシングレットを組み合わせてデュプレットにする手順である。デュプレットを作成するプロセスは以下のステップを包含する。
１．その（ｉ、ｊ）要素がｉ番目とｊ番目のシングレットの間の距離を包含する行列Ｄを作る。
２．最小閾値未満であるかまたは最大閾値を上回るＤの要素をすべてＮＡＮ（Ｎｏｔ ａ Ｎｕｍｂｅｒ（非数）、初期化されていない変数を示す特定記号）として変更する。最小閾値および最大閾値は、ＤＩＳＴＡＮＣＥ．ＭＩＮ（デフォルト値は０．０１）およびＤＩＳＴＡＮＣＥ．ＭＡＸ（デフォルト値は０．２５）に画像の最小寸法を乗じられたものとしてそれぞれ計算される。
３．すべてゼロのＳｘ１配列を作り、それをｄｅｇと呼ぶ。ｄｅｇ（ｓ）はｓ番目のシングレットに連結されるシングレットの数を包含することになる。
４．ＤがＮＡＮしか包含しなくなるか、またはシングレットのための最大数が指定されている場合には該最大に達するまで、Ｄをスキャンする。
５．Ｄの最小の要素を見いだす。それを（ｓ１，ｓ２）と呼ぶ。ｄｅｇ（ｓ１）およびｄｅｇ（ｓ２）の両方をインクリメントする。ｄｅｇ（ｓ１）またはｄｅｇ（ｓ２）のどちらかが最大度数ＤＥＧＲＥＥ（デフォルトは１０）よりも大きくなれば、このときは、該シングレットに対応する行および列内のすべての要素をＮＡＮとして設定する。例えば、ｄｅｇ（ｓ１）がＤＥＧＲＥＥよりも大きくなれば、このときは、すべてのｓについてＤ（ｓ、ｓ１）およびＤ（ｓ１、ｓ）をＮＡＮに設定する。
６．対（ｓ１、ｓ２）について、それらを一緒に連結する角度ならびにそれらを連結する線の長さを計算し、それらをそれぞれ角度および距離と呼ぶ。両シングレットの一時的複製の入射および出射角度から角度を減じる。これで、デュプレットは＜角度，距離，ｓ１．入射，ｓ１．出射，ｓ２．入射，ｓ２．出射＞として表されることになる。
７．デュプレット行列を返す。
【００４０】
デュプレット比較（図２、ステップ２１８）
デュプレット比較は、２つのデュプレット行列内の項目を比較し、一致のリスト、および従って候補姿勢の第１のリストを作るプロセスである。２つのデュプレット行列はＤ１およびＤ２であるとして、プロセスは以下のように遂行される。
【００４１】
１． Ｄ１内のあらゆるデュプレットｄ１およびＤ２内のｄ２について、これらの条件がすべて満足されているかどうかを判定する。
｜ｄ１．ｓ１．入射−ｄ２．ｓ１．入射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ１．出射−ｄ２．ｓ１．出射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ２．入射−ｄ２．ｓ２．入射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ２．出射−ｄ２．ｓ２．出射｜＜ＴＨＲＥＳＨＯＬＤ
ここで、ＴＨＲＥＳＨＯＬＤは設定変数ＤＵＰＬＥＴＳ．ＴＨＲＥＳＨＯＬＤによって決められる。
これらの条件が満たされれば、このときは、候補姿勢（ｄ１．長さ／ｄ２．長さ，ｄ１．角度−ｄ２．角度）を候補のリストに追加する。さらに、２つのシングレットおよび両デュプレットのＸおよびＹ座標に注目する。この候補を「直」としてタグ付けする。
【００４２】
２． 同様に、これらの条件が満足されるかどうかを判定する。
｜ｄ１．ｓ１．入射−ｄ２．ｓ２．入射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ１．出射−ｄ２．ｓ２．出射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ２．入射−ｄ２．ｓ１．入射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ２．出射−ｄ２．ｓ１．出射｜＜ＴＨＲＥＳＨＯＬＤ
この場合、ｄ１．角度−ｄ２．角度−パイと記録されることになる角度を除き、同様の候補姿勢がリストに追加されることになる。この候補は「逆」としてタグ付けされることになる。
【００４３】
３． 候補のリストを、次に記載されるクラスター化段階に渡す。
候補クラスター化（図２、ステップ２２０）
候補クラスター化は、デュプレット比較を通じて作られた姿勢候補を取り入れ、候補の大きなセットによって各々表される限られた数の姿勢を推定するプロセスである。本手順は、いずれも以下において記載される２つの段階、スケール−角度クラスター化、およびＸ−Ｙクラスター化、を包含する。
【００４４】
スケール−角度クラスター化
本段階の目的は、デュプレット比較を通じて作る候補姿勢に基づき候補（スケール，角度）対のリストを作ることである。
ＳおよびＡは、候補スケールおよび角度を持つ２つの１ｘＮであるとする。スケール−角度クラスター化手順は以下のようになされる。
１．Ｓの値の底ＢＡＳＥの対数を計算することによってＳ＿Ｌを作る。
２．ＡおよびＳ＿Ｌのヒストグラムを独立に作る。各ヒストグラムはＢＩＮＳのビンを包含することになる。Ａについてのヒストグラムは−パイないしパイのレンジに及ぶことになる。Ｓ＿Ｌは、ＳＣＡＬＥ．ＭＩＮおよびＳＣＡＬＥ．ＭＡＸのレンジ内で、どちらも底ＢＡＳＥで解析されることになる。
３．どちらのヒストグラム上の点も、もしそれがその右側のＤの点よりも高く且つその左側のＤの点よりも高いかまたはそれに等しければ、「ピーク」として標識する。
４．各ヒストグラムについてＣ１個の最高ピークを独立に選択する。
５．すべてのスケール候補をすべての角度候補と交差させ、スケール−角度候補のリストを作る。このリストをＸ−Ｙクラスター化段階に渡す。各スケール−角度候補について、この対を生じさせた一致デュプレット内のシングレットの位置も送る。
６．各スケール−角度候補についての信頼性を、それを表すデュプレット一致の対の数を２つのデュプレット行列内のデュプレットの数の最小で除したものとして計算する。
７．スケール−角度候補の数がＣ２を超えるならば、このときは、最高の信頼性を有するＣ２個のものを取る。
【００４５】
Ｘ−Ｙクラスター化
スケール−角度クラスター化段階の出力は（スケール，角度）候補のセットである。Ｘ−Ｙクラスター化段階は、各（スケール，角度）候補について以下のように、候補に平行移動情報を加えるプロセスである。
１．この候補についてのシングレット位置を、軸系の中心が画像の中心に移動するように改変する。このプロセスは２つのデュプレット行列について独立に実行されることになる。
２．クエリシングレット位置を角度によって回転させる。
３．クエリシングレットをスケールによってスケーリングする。
４．クエリと参照との間のシングレット位置についてのＸおよびＹにおける差を独立に求める。これらをｄｘおよびｄｙ配列と呼ぶ。
５．本段階においては、ｄｘ−ｄｙ対は、スケール−角度対に対して実行されるものと同様の２次元クラスター化アルゴリズムを受けることができるか、またはより迅速な演算が続いて行われることができる。
６．ｄｘおよびｄｙの平均を独立に求め、この情報をスケール−角度対に付加し、かくして、姿勢候補（角度，スケール，ｄｘ，ｄｙ，信頼性）を作る。この姿勢候補についての信頼性はスケール−角度対についての信頼性に等しいままとなることになる。
７．設定パラメーターによって要求される場合には、以下において記載されるように、重複調査を遂行する。
８．信頼性の最高値に対応するＣ２個の候補を取り、それらを次の段階に報告する。
【００４６】
重複の考慮
重複の考慮はＯＶＥＲＬＡＰが非負である場合のみ機能する。重複の考慮は以下のようになされる。
１．（角度，スケール，ｄｘ，ｄｙ，信頼性）情報に従い参照バウンディングボックスを変換する。回転され、スケーリングされ、移動されたバウンディングボックスを覆う最小の矩形を見いだす。
２．改変された、参照のバウンディングボックス、およびクエリのバウンディングボックスを両方とも覆う最小の矩形を見いだす。この矩形の面積をＡと呼ぶ。
３．もし、ｍｉｎ（Ａ１，Ａ２）／ＡがＯＶＥＲＬＡＰ未満であれば、この候補を不適当として標識する。ここで、Ａ１およびＡ２は、参照の改変されたバウンディングボックスの面積、およびクエリの面積である。
４．不適当として標識された候補をリストから削除する。
【００４７】
輪郭デュプレットデータベース（図２、２２２）
輪郭デュプレットデータベース（Ｃｏｎｔｏｕｒ−Ｄｕｐｌｅｔｓ Ｄａｔａｂａｓｅ、ＣＤＤＢ）ファイルは、各々仰角および方位角に付随するデュプレット行列のリストを包含する。ＣＤＤＢファイルを生成するために、上述のアルゴリズムは訓練用画像（図２、２２４）に対してデュプレット作成を遂行することになり、次に、結果として生じる、仰角−方位角表示を各々伴うデュプレット行列をＣＤＤＢ２２２内に記憶することになる。これらのサンプルは視像と呼ばれる。
ＣＤＤＢファイルは実際には、訓練用画像に関する詳細を包含するファイルを伴う。これらの詳細は様々な視覚化を作るために必要なものであり、アルゴリズムの通常の演算には必要とされない。
クエリが実行されると、手順はデータベース内の視像毎に繰り返される。アルゴリズムの最終出力は、最高の対応する信頼性値を有する、ＣＤＤＢＣ．ＳＥＡＲＣＨ．ＣＡＮＤＩＤＡＴＥＳ．ＴＯＴＡＬの数の候補である。次に、各候補を作った視像の角度表示が各候補に付加され、かくして姿勢の（仰角、方位角、角度、スケール、ｄｘ、ｄｙ、信頼性）表示を作る。以上に概説された物体検出ステップの結果は、姿勢推定値である、姿勢のこれらの表示であり、メモリー、例えばＲＡＭ１０４またはハードディスク１６０、内に記憶される。これらの姿勢推定値は次に、製品の組み立ての際の物体／部品のロボット認識において用いられ得る。
【００４８】
出力の視覚化
様々な視覚化が作られ得る。これらの視覚化の２つがモデルビューおよびオーバーレイである。モデルビューとは、スケール、角度、および平行移動も反映するように改変された一致訓練用画像の画像である。オーバーレイとは、クエリ画像上のモデルビューのオーバーレイである。
【００４９】
物体モデルの仕様
現在、訓練手順は、様々なパラメーターによって支配される通りの、様々な姿勢をとる対象となっている物体を示す画像を必要とする。これらの画像を作る実用的且つより簡便な方法が、物体の３Ｄ視像を作る３次元視覚化ツールであるサンプルシミュレーター２２８を用いるものである。
【００５０】
設定ユーティリティー（図２、２３０）
上述されたように、本発明の方法の異なる部分は異なる設定パラメーターを用いる。これらのパラメーターのいくつかの例示的な（デフォルト）値が上述の記載において与えられている。しかし、これらの値はユーザーによって特定の環境に合うように設定され得る。設定ユーティリティーは、これらのパラメーターのための適切な値を求め、それにより、ユーザーからの直感的入力を用いるのは最小限にしてそれらを設定する対話型ツールである。
【００５１】
以下のセクションは、特に物体の画像がカメラ画像である場合に物体の姿勢推定値を精緻化する本発明の態様を記載する。
【００５２】
本発明の姿勢精緻化はアラインメント問題としてモデル化される。我々は、対象となっている物体、すなわちロボットが特定し、拾い上げなければならない部品、の３Ｄモデル、および物体を撮像するために用いられるカメラ１１２のカメラパラメーターより開始する。目標は、モデルに対してそれが画像内の対象となっている物体と合致するように適用されるべき３Ｄ（ユークリッド、６自由度（６ ｄｅｇｒｅｅｓ ｏｆ ｆｒｅｅｄｏｍ））変換を見いだすことである。その結果、姿勢精緻化はコスト関数の反復的な最適化問題として実装される。物体前景を負担するコスト以外に、コスト関数は、局所的特徴点または境界特徴点を合わせるまたは一致させる画像一致コストを含んでよい。
【００５３】
アルゴリズムをより良く理解するために、コスト関数および緩和解の定義の前にカメラ投影モデル、ＯｐｅｎＧＬ仮想カメラモデルおよび画像ヤコビ行列が導出される。
【００５４】
カメラ投影モデル
本発明のカメラ投影モデルはピンホールカメラモデルに基づく。ピンホールカメラはカメラ機能の最も単純で理想的なモデルである。それは無限小の穴を有し、そこを通って光が入り、該穴と向かい合うカメラ表面上に倒立像を形成する。図４に示されるように、透視投影は３次元物体の、２次元画像平面上への投影である。実際には、画像の焦点をカメラの焦点面上に合わせるためにレンズを用いなければならない。焦点面は、画像平面に平行である１つの特定の平面である。ピンホールカメラ座標はワールド座標に合わせられるとすると、単純な幾何学は以下を示す。
ここで、（ｘw，ｙw，ｚw）は３Ｄワールド座標における物体の点であり、（ｘim，ｙim）は２Ｄ画像平面座標における点である。
【００５５】
カメラフレーム座標から画素（画像）座標への投影モデルは以下のように導出される。
ここで、Ｆは焦点距離であり、ＳｘおよびＳｙは、焦点にあるセンサー平面から画像または画素座標への、ｘおよびｙ方向におけるスケーリング係数である。ＳｘおよびＳｙスケーリング係数はＣＣＤセンサーのセルの幅および高さ、ならびに分解能に比例する。我々は、モデルスケーリング係数λxおよびλyを得るようにカメラを較正することができる。
ここで、（ｘ0，ｙ0）は画像または画素座標におけるカメラ座標の原点の投影である。
【００５６】
ｕ＝ｘim−ｘ0およびｖ＝ｙim−ｙ0とすると、式（３）は以下のように表され得る。
【００５７】
画像ヤコビ行列
画像ヤコビ行列は、作業空間内の或る物体の速度と、作業空間の観察される画像内で起きる対応する変化との間の関係に基づいて構築されなければならない。
【００５８】
特徴点Ｓの現在の投影は座標ｆ＝（ｕ，ｖ）を有する。画像ヤコビ行列は以下のように算定される。
【００５９】
座標（ｘc，ｙc，ｚc）またはカメラフレームにおける（ｘ，ｙ，ｚ）を有する点Ｐを考える。透視投影を用いると、Ｐの画像平面座標は式（４）によって与えられる。
【００６０】
カメラフレームにおける座標（ｘ，ｙ，ｚ）を有する単一の点についての画像ヤコビアンを構築するために、式は以下のステップで導出される。
【００６１】
ｕおよびｖについての時間導関数を算出する。
式を組み合わせ、代数を解く。
【００６２】
ステップ１、割り算の規則を用いると、
【００６３】
ステップ２、透視投影の式は、以下のようにｘおよびｙのための表現式を与えるように書き直され得る。
【００６４】
【００６５】
ステップ４、式を組み合わせ、次式を得る
これらの式は画像ヤコビ行列形式で書かれることができる。
【００６６】
ＯｐｅｎＧＬ仮想カメラモデル
モデルを画像上に投影するために、本発明は好ましくは、既存のハードウェアを用いて高速レンダリングおよび隠線消去を実行することができるＯｐｅｎＧＬを用いる。加えて、ＯｐｅｎＧＬは各画素における深さ情報を記憶することができる。この情報を用いて、各輪郭点に対応する３Ｄ点は計算される。図５はＯｐｅｎＧＬ投影および正規化デバイス座標（ＮＤＣ）を示す。好ましい実施形態ではＯｐｅｎＧＬが用いられるが、本発明はこのレンダリングアプリケーションプログラミングインタフェース（ＡＰＩ）に限定されるものではなく、ＤｉｒｅｃｔＸ、レイトレーシングなど等の他のレンダリングＡＰＩが利用されてもよい。
【００６７】
透視投影では、角錐台（視点座標）における３Ｄ点は立方体（ＮＤＣ）に写像され、ｘ座標は［ｌ，ｒ］から［−１，１］に、ｙ座標は［ｂ，ｔ］から［−１，１］に、ｚ座標は［ｎ，ｆ］から［−１，１］に写像される。
【００６８】
投影行列は視点座標系における頂点をクリップ座標系に変換する。
【００６９】
スケーリング行列および画素座標計算を適用すれば、ＯｐｅｎＧＬにおける３Ｄ頂点の新しい投影は以下のようになる。
式（３）および（１４）を用いると、ＯｐｅｎＧＬ仮想カメラの、実カメラモデルへの対応を求めることができる。
【００７０】
カメラ座標およびＯｐｅｎＧＬ仮想カメラの視点座標の定義は異なることに留意されたい。その結果、２つの座標の間の対応を導出するには以下の変換が必要となる。
本発明では、ＯｐｅｎＧＬは、モデルを投影するためにのみ用いられる。すべての式はデフォルトでは実カメラモデルを用いて導出される。
【００７１】
２．４ コスト関数
本発明の姿勢精緻化方法はエネルギーベースのコスト関数を最小化する。コスト関数は、３Ｄ姿勢（６ＤｏＦ）を用いるモデル投影が画像内の対象となっている物体と合致するよう、最小値を有するように定義される。
ここで、Ｉ（ｘ，ｙ）は入力画像であり、Ｔ（ｘ，ｙ）は所与の３Ｄ姿勢を有するモデル投影の２値マスク画像である。
【００７２】
２値マスクのＴ（ｘ，ｙ）の画像は所与の３Ｄ姿勢およびカメラパラメーターについてのモデルの投影であり、以下の通りの定義を有する。
ＯｐｅｎＧＬは、物体モデルを２Ｄ仮想画像に投影することによって２値マスク画像の高速レンダリングを実行することができる。
【００７３】
ｕ1およびｕ2は物体マスクの内部および外部の入力画像の平均値であり、以下のように定義される。
【００７４】
投影モデル輪郭曲線Ｃは、画像を物体の「内側」と物体の「外側」とに分けるＴ（ｘ，ｙ）から得られ得る。項Ｆ1は物体の内部のフィッティングエネルギーであり、Ｆ2は物体の外部のフィッティングエネルギーである。
【００７５】
単純な場合のコスト関数の基本的な考え方は以下のように説明される。画像Ｉ（ｘ，ｙ）は、物体および背景についてのｕobjおよびｕbackの個別の値の、おおよそ区分的に一定な強度の２つの領域によって形成されるとする。画像Ｉ（ｘ，ｙ）内の物体の境界はＣ0によって示される。投影モデル輪郭曲線Ｃが画像Ｉ（ｘ，ｙ）内の物体境界Ｃ0と合致するならば、このとき、物体の内部ではｕ1＝ｕobj、物体の外部ではｕ2＝ｕbackを得、その結果、次式を得ることができる。
ｉｎｆ｛Ｆ1（Ｃ）＋Ｆ2（Ｃ）｝≒０≒Ｆ1（Ｃ0）＋Ｆ2（Ｃ0）
【００７６】
この場合、投影モデル輪郭曲線Ｃが画像内の物体境界Ｃ0と合致するとエネルギー関数は最小化されることは明らかである。
【００７７】
これは、図６に示されている通りの単純な場合において理解され得る。同図は投影モデル曲線の位置のあり得る場合をすべて示している。例えば、図６（ａ）のように曲線Ｃが物体の外部にある場合には、Ｆ1（Ｃ）＞０且つＦ2（Ｃ）≒０である。図６（ｂ）のように曲線Ｃが物体の内部にある場合には、このときは、Ｆ1（Ｃ）≒０且つＦ2（Ｃ）＞０である。図６（ｃ）のように曲線Ｃが物体の内部および外部のどちらにもある場合には、このときは、Ｆ1（Ｃ）＞０且つＦ2（Ｃ）＞０である。最後に、図６（ｄ）に示されるようにＣ＝Ｃ0で投影モデル曲線Ｃが物体の境界上にある場合には、Ｆ1（Ｃ）≒０且つＦ2（Ｃ）≒０であり、フィッティングエネルギーは最小化される。
【００７８】
我々のコスト関数の定義に基づき、例えばＲＡＭ１０４またはハードディスク１６０内に記憶されている姿勢推定値は、上述のフィッティング項を最小化するべく更新されることになり、我々は、一致した特徴点または境界特徴からいくつかの他の項または制約を加えることができる。例えば、もし、２Ｄ入力画像ｐj＝（ｐjx，ｐjy）Tと、仮想画像内にπ（Ｐj）＝（ｕj，ｖj）Tとして投影される３Ｄモデル特徴Ｐj＝（Ｘjobj，Ｙjobj、Ｚjobj）との間に一致した特徴点のセット（例えばｊ＝１．．．Ｎ個の一致対）があれば。追加の制約項は以下のように定義されてよい。
ここで、ｗjは特徴一致についての重みであり、それは一致信頼性またはスコアであってよく、π（Ｐj）＝（ｕj，ｖj）Ｔはモデル特徴点の、Ｐi＝（Ｘiobj，Ｙiobj，Ｚiobj）から所与の３Ｄ姿勢を有する画像への投影を示すことである。‖ ‖は画像座標におけるユークリッド距離であってよい。
【００７９】
式（１９）すなわち一致エネルギーの最小化は精緻化のための初期姿勢推定を提供することができる。それは、収束およびロバストネスを向上させることができるように、姿勢精緻化のための制約項として用いられてもよい。
【００８０】
すると、コスト関数は以下のように定義されてよい。
ここで、ηは、ＥcとＥmatchとの間のエネルギーのバランスをとる重み関数である。
我々はＥcおよびＥmatchの両方についての勾配流を導出することになるが、最初の実行では、η＝０として、Ｅcのエネルギーを用いるだけである。
【００８１】
姿勢を反復的に更新するために速度スクリューを計算する
勾配降下法に従い、エネルギーＥは最小値に近づくことが期待される。
【００８２】
姿勢パラメーターｒに関するＥの偏微分は、連鎖法則を用いて算出され得る。
【００８３】
Ｅcの偏微分
まずＥcの偏微分を導出する
第２および第３項については、それらがゼロであることを証明することができる。
２値マスクＴ（ｘ，ｙ）の画像は所与の３Ｄ姿勢およびカメラパラメーターについてのモデルの投影である。
【００８４】
Ｔ（ｘ，ｙ）は、式（１７）において定義される通りの、モデルの投影の２値マスクであるので。境界Ｃ上を除いてＴ（ｘ，ｙ）の勾配はゼロである。
【００８５】
Ｅmatchの偏微分
一致エネルギーは、画像座標における、入力画像内の特徴点と投影仮想画像内の、特徴点との間の距離一致した特徴点を測るコスト関数である。
【００８６】
画像ヤコビ行列の微分ステップと同様に、次式を得ることができる。
【００８７】
部分方程式は画像およびカメラ座標で導出されており、３Ｄ特徴点Ｐj＝（Ｘjobj，Ｙjobj，Ｚjobj）は、部分方程式を計算する際にはカメラ座標に変換されることになることに留意されたい。
【００８８】
エネルギー関数を最小化するためのガウス・ニュートン法
我々の実装では、エネルギー関数を最小化するためにガウス・ニュートン法を用いた。ガウス−ニュートンアルゴリズムは２乗和の最小値を求める。
【００８９】
エネルギーＥcを最小化する
【００９０】
エネルギーＥmatchを最小化する
【００９１】
エネルギーＥ＝Ｅc＋Ｅmatchを最小化する
ｅおよびＪは、ｅc、ηｅmatchならびにＪcおよびηＪmatchをそれぞれ連結することによって得られる。
【００９２】
姿勢パラメーターまたは変換行列を更新する
物体座標からカメラ座標への変換は、変換による表示であってよい。
時刻ｔにおける或る固定フレーム（物体座標）とカメラフレームとの間の相対変位を示すためにｇ（ｔ）＝（Ｒ（ｔ），Ｔ（ｔ））を用いることにする。カメラが時刻ｔ1，ｔ2．．．ｔmにおいてそれぞれロケーションｇ（ｔ1），ｇ（ｔ2）．．．ｇ（ｔm）にあるならば、このとき、同じ点ｐの座標はそれに応じてＸ（ｔi）＝ｇ（ｔi）Ｘ０，ｉ＝１．．．ｍとして与えられる。
【００９３】
図７を参照すると、ｔ2およびｔ1におけるカメラの間の相対運動はｇ（ｔ2，ｔ1）として示されることとなり、このとき、同じ点ｐの座標同士の間には以下の関係がある。
Ｘ（ｔ2）＝ｇ（ｔ2，ｔ1）Ｘ（ｔ1） （３９）
【００９４】
今度は、図７に示される通りの、ｔ＝ｔ3におけるカメラの第３の位置を考える。ｔ3とｔ2とにおけるカメラの間の相対運動はｇ（ｔ3，ｔ2）であり、ｔ3とｔ1とにおけるカメラの間の相対運動はｇ（ｔ3，ｔ1）である。このとき、座標の間には以下の関係がある。
Ｘ（ｔ3）＝ｇ（ｔ3，ｔ2）Ｘ（ｔ2）＝ｇ（ｔ3，ｔ2）ｇ（ｔ2，ｔ1）Ｘ（ｔ1） （４０）
【００９５】
ｔ3およびｔ1における座標の間の直接的関係と比較すると
Ｘ（ｔ3）＝ｇ（ｔ3，ｔ1）Ｘ（ｔ1） （４１）
【００９６】
連続運動のための合成規則が成り立たなければならない。
ｇ（ｔ3，ｔ1）＝ｇ（ｔ3，ｔ2）ｇ（ｔ2，ｔ1） （４２）
【００９７】
合成規則に基づけば、ｇ（ｔn，ｔ1）についての姿勢パラメーターは
ｇ（ｔn，ｔ1）＝ｇ（ｔn，ｔn-1）ｇ（ｔn-1，ｔ1） （４３）
【００９８】
勾配降下法より、反復ｎ−１からｎへの相対変位を得ることができる。その結果、反復ｎのための姿勢パラメーター更新は、ｇ（ｔn，ｔn-1）を計算することによって得られる。
【００９９】
および
【０１００】
【０１０１】
実行
姿勢推定はエネルギー関数の最適化または最小化としてモデル化される。反復的に姿勢更新は計算され、エネルギーを最小化することになる。以下は、上述された方法の例示的な実行である。
ステップ１：画像、モデル、カメラパラメーターを入力する。
ステップ２：初期姿勢パラメーターを得る。
ステップ３：与えられた姿勢パラメーターを用いてＯｐｅｎＧＬによってモデルを仮想画像に投影する。２値マスク画像Ｔ（ｘ，ｙ）および対応する深さ情報／マップが得られる。
ステップ４：姿勢を反復的に更新するために速度スクリューを計算する。（ｉ）式（１８）によって物体の内部および外部の平均値を計算する。（ｉｉ）２値マスクから輪郭Ｃを得、深さ情報を用いて３Ｄ輪郭点を得る。（ｉｉｉ）輪郭点についての、ｘおよびｙ方向における勾配∇Ｔ（ｘ，ｙ）を計算する。（ｉｖ）式（２６）を用いて画像ヤコビ行列を計算する。（ｖ）式（２７）を用いて勾配流を計算し、ガウス・ニュートン法を用いて式（３５）によって制御入力（速度スクリュー）を得る。
ステップ５：式（４５）によって、制御入力（速度スクリュー）および所与のステップサイズを用いて相対変位を計算する。
ステップ６：式（４６）および（４７）によって姿勢パラメーターを更新する。
ステップ７：もし、姿勢パラメーターの変化が非常に小さいか、または最大反復数に達すれば、終了に行き、さもなければステップ３に戻る。
ステップ８：終了。
【０１０２】
本発明はいくつかの特定の実施形態と併せて記載されているが、上述の記載に鑑みれば、多くのさらなる代替、変更および変形が容易に分かることは当業者には明白である。それ故、本願明細書において記載されている本発明はこのような代替、変更、応用および変形をすべて、添付の請求項の精神および範囲内にあってよいものとして含むように意図されている。
【技術分野】
【０００１】
本発明は、物体の姿勢を推定する物体の物体姿勢推定方法、物体姿勢推定装置、物体推定姿勢精緻化方法、およびコンピューター可読媒体に関する。
【背景技術】
【０００２】
今日の多くの工業環境では、部品の組み立ておよび製造のためにロボットが用いられている。これらのロボットは、それらに視覚を与える１つ以上のカメラ、例えばＣＣＤおよびＣＭＯＳ、を備えている。多くの場合、物体（すなわち部品）は容器に入っている。ロボットは、製品を組み立てるべく物体を拾い上げることができるように、容器内の物体／部品を認識しなければならない。しかし、物体は様々な姿勢（位置、配向、回転）をとり得る。従って、ロボットは部品をその姿勢にかかわらず認識するように訓練されなければならない。
本発明は、ロボットが訓練されて、物体を、ロボットの搭載カメラから見える通りのその姿勢にかかわらず認識することができるよう、２次元画像（例えばカメラ画像）から３次元（ｔｈｒｅｅ−ｄｉｍｅｎｓｉｏｎａｌ、３Ｄ）物体の姿勢を推定することに関する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本技術分野において周知であるように、ロボットは、カメラの画像から物体を特定しようとするソフトウェアを含む。従って、このようなソフトウェアは、ロボットのカメラによって取り込まれた画像と比較するために用いる物体画像のロバスト且つ正確なデータベースを有することが重要である。
【課題を解決するための手段】
【０００４】
本発明の１つの態様は、入力画像から物体の姿勢を推定し、物体姿勢推定を記憶する方法および装置であって、該方法および装置は、物体を包含する画像を入力することと、入力画像の２値マスクを作成することと、入力画像の２値マスクからシングレットのセットを抽出することであって、各シングレットは、入力画像内の物体の内側および外側輪郭内にある点を表す、抽出することと、シングレットのセットを連結して、デュプレックス行列として表されるメッシュにすることと、候補姿勢のセットを作るべく２つのデュプレックス行列を比較することと、物体姿勢推定値を作り、該物体姿勢推定値を記憶することと、を含む、方法および装置である。
【０００５】
本発明の一実施形態では、物体の複数の画像が入力され、各画像は、該複数の画像の互いにおける視像とは異なる、物体の視像を包含する。
１つの態様は、物体の複数の画像の各々における視像を、物体のためのＣＡＤモデルを用いて生成することを含む。
別の態様は、物体の複数の画像の各々における視像を、カメラを備えたロボットを用いて生成することを含む。
【０００６】
本発明のさらなる態様は、入力画像内の物体を検出し、物体のバウンディングボックスを計算することを含む。
別の態様は、物体の内側および外側輪郭を抽出することを含む。
【０００７】
本発明の他の実施形態では、物体姿勢推定値は、該姿勢推定値をエネルギー関数の最適化としてモデル化することによって精緻化される。
１つの態様では、本発明は、エネルギー関数におけるエネルギー値を最小化するべく姿勢推定値を反復的に計算する。
別の態様は、姿勢推定値を反復的に計算するために速度スクリューを計算する。
別の態様は、ＯｐｅｎＧＬ、ＤｉｒｅｃｔＸ、レイトレーシングなど等のレンダリングアプリケーションプログラミングインタフェース（ａｐｐｌｉｃａｔｉｏｎ ｐｒｏｇｒａｍｍｉｎｇ ｉｎｔｅｒｆａｃｅ、ＡＰＩ）を用いて物体のモデル輪郭曲線を仮想画像に投影する。
【０００８】
本発明のさらなる実施形態では、物体姿勢推定値は、推定姿勢をとる物体の画像、物体のモデル、および推定姿勢をとる物体の画像を撮るために用いられるカメラのパラメーターを入力することと、２値マスク画像および画像深さ情報を得るべく、カメラのパラメーターおよび初期姿勢パラメーターを用いて物体のモデルを物体の仮想画像に投影することと、２値マスク画像および画像深さ情報を用いて初期姿勢パラメーターを新しい姿勢パラメーターに更新し、エネルギー関数を最小化するべくまたは反復の最大数に達するまで新しい姿勢パラメーターを反復的に更新することと、によって精緻化される。
【０００９】
本発明の別の態様は、コスト関数を用いて物体の内部および外部の平均値を計算することと、２値マスク画像から物体の輪郭Ｃを計算し、画像深さ情報を用いて３Ｄ輪郭点を計算することと、を含む。
【００１０】
さらなる態様は、輪郭点についての、ｘおよびｙ方向における勾配∇Ｔ（ｘ，ｙ）を計算することと、画像ヤコビ行列を計算することと、ガウス・ニュートン法を用いて勾配流および速度スクリューを計算することと、を含む。
【００１１】
本発明の別の態様は、速度スクリューおよび所与のステップワイズを用いて相対変位を計算することを含む。
【００１２】
添付の図面と併せて以下の記載および請求項を参照することによって、本発明のより完全な理解とともに他の目的および達成が明らかになり理解されるようになる。
【図面の簡単な説明】
【００１３】
【図１】図１は、本発明を利用するための物体処理デバイスおよびシステムの概略的なブロック図である。
【図２】図２は本発明の一般的方法のフローチャートである。
【図３】図３は、図２に示される方法の物体抽出段階のフローチャートである。
【図４】図４はピンホールカメラモデルにおける透視投影を示す。
【図５】図５はＯｐｅｎＧＬ投影および正規化デバイス座標（Ｎｏｒｍａｌｉｚｅｄ Ｄｅｖｉｃｅ Ｃｏｏｒｄｉｎａｔｅ、ＮＤＣ）を示す。
【図６】図６（ａ）ないし（ｄ）は、物体の境界に対する投影モデル曲線の位置の４つのすべてのあり得る場合を示す。
【図７】図７はカメラの運動の合成を示す。
【発明を実施するための形態】
【００１４】
以下の詳細な説明では、例示の目的で本発明の実施形態例を示す添付の図面に言及がなされる。図面において、いくつかの図全体にわたり、同じ符号は実質的に同種の構成要素を示す。これらの実施形態は、当業者が本発明を実施することを可能とするよう、十分詳しく記載されている。他の実施形態が利用されてもよく、構造的、論理的および電気的変更が、本発明の範囲から逸脱することなくなされてもよい。さらに、本発明の種々の実施形態は、異なるものであっても、必ずしも相互排他的であるわけではないことを理解されたい。例えば、１つの実施形態において記載されている特定の特徴、構造、または特性が他の実施形態内に含まれてもよい。従って、以下の詳細な説明は限定の意味で捉えられてはならず、本発明の範囲は、添付の請求項、およびこれらの請求項が権利を与えられる同等物の全範囲によってのみ定義される。
【００１５】
概して、実施形態例は、画像、とりわけ、１つ以上の物体のデジタル画像、を分析するための方法、デバイス、およびコンピューター可読媒体に関する。画像は、２Ｄ画像で表される対応する３Ｄ物体の姿勢（位置および配向）を推定するべく分析される。実施形態例は画像の２値マスクを作成し、２値マスクからシングレットのセットを抽出する。各シングレットは、物体の内側および外側輪郭内にある点を表すことになる。シングレットのセットは連結され、デュプレックス行列として表されるメッシュにされる。２つのデュプレックス行列が比較され、候補姿勢のセットを作る。その後、物体姿勢推定値が作られ、例えばロボットによる部品組み立てのための視覚システムにおける、後の利用のために記憶される。
【００１６】
図１に、物体処理デバイス１００の例の略図が示されている。物体処理デバイス１００は介在インターフェース１０２を介してホストコンピューター１５０とデータを交換する。ホストコンピューター１５０上にはアプリケーションプログラムおよび物体処理デバイスドライバーがアクセスのために記憶されてもよい。アプリケーションプログラムから画像取得コマンドが受信されると、例えば、物体処理デバイスドライバーはコマンドデータの、物体処理デバイス１００に適したフォーマットへの変換を制御し、変換されたコマンドデータを物体処理デバイス１００に送信する。ドライバーは同様に、物体処理デバイス１００から種々の信号およびデータを受信して解釈し、ホストコンピューター１５０を介してユーザーに必要な情報を提供する。
【００１７】
ホストコンピューター１５０によってデータが送信されると、インターフェース１０２はデータを受信し、それを、ＲＡＭ１０４の一部を形成する受信バッファー内に記憶する。ＲＡＭ１０４は、例えばアドレス指定を通じて、多数の区画に分割され、受信バッファーまたは送信バッファー等の各種のバッファー群として割り当てられ得る。デジタル画像データ等のデータも物体処理デバイス１００によって取り込み機構（単数または複数）１１２、フラッシュＥＥＰＲＯＭ１１０、またはＲＯＭ１０８から得られ得る。取り込み機構（単数または複数）１１２は例えばカメラであり、プリンター等のデバイスの製造および／または組み立てにおいて用いられる部品等の１つ以上の物体を撮影することによってデジタル画像を生成することができる。カメラ１１２は、例えばロボット１１６、または人間によって制御され得るか、あるいは例えばコンピューター１５０によって自動制御され得る。次に、物体（単数または複数）のデジタル画像はＲＡＭ１０４の受信バッファーまたは送信バッファー内に記憶され得る。
【００１８】
プロセッサー１０６は、例えばＲＯＭ１０８上またはフラッシュＥＥＰＲＯＭ１１０上に記憶されているコンピューター実行可能命令を用い、例えば方法２００（図２）等の、或る機能または一群の機能を遂行する。方法２００は本願明細書において以下でより詳細に説明される。ＲＡＭ１０４の受信バッファー内のデータがデジタル画像である場合には、例えば、プロセッサー１０６はデジタル画像に対して方法２００の方法手続きを実行し、デジタル画像内の特徴を抽出し、抽出された特徴に基づき画像をさらに解析することができる。次に、画像が、例えばＬＣＤディスプレイ等のディスプレイ１１４上に表示されたり、または例えば、プリンター１６２上での印刷、プロジェクター１６４を用いた投影、またはハードディスク１６０上への記憶のためにホストコンピューター１５０に転送されたりする前に、イメージングパイプラインにおけるさらなる処理がデジタル画像に対して遂行されてもよい。
【００１９】
本願明細書において開示されている方法例２００およびその変形は、非一時的コンピューター可読媒体であって、その上に記憶されたコンピューター実行可能命令またはデータ構造を運ぶまたは有するための媒体を用いて実装され得る。このようなコンピューター可読媒体は、汎用または専用コンピューターのプロセッサーによってアクセスされ得る任意の利用可能な媒体であることができる。例として、ただし限定ではなく、このようなコンピューター可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭまたは他の光ディスクストレージ、磁気ディスクストレージまたは他の磁気記憶デバイス、あるいはコンピューター実行可能命令またはデータ構造の形式でプログラムコードを運ぶまたは記憶するために用いられ得るとともに、汎用または専用コンピューターのプロセッサーによってアクセスされ得る任意の他の媒体を含むことができる。以上のものの組み合わせもコンピューター可読媒体の範囲に含まれるべきである。
【００２０】
コンピューター実行可能命令は、例えば、汎用コンピューターまたは専用コンピューターのプロセッサーに或る機能または一群の機能を遂行させる命令およびデータを含む。本願明細書においては、主題は方法手続きに固有の言葉で記載されているが、添付の請求項において定義される主題は、本願明細書において記載されている特定の手続きに必ずしも限定されるものではないことを理解されたい。むしろ、本願明細書において記載されている特定の手続きは、請求項を実装する形態の例として開示されている。
【００２１】
専用コンピューターの例としては、デジタルカメラ（その例としては、日本、長野県諏訪市大和に本社を置くセイコーエプソン社製のエプソンＲ−Ｄ１デジタルカメラが挙げられるが、それに限定されるものではない）、デジタルカムコーダー、プロジェクター、プリンター、スキャナー、複写機、ポータブルフォトビューアー（その例としてはセイコーエプソン社製のエプソンＰ−３０００もしくはＰ−５０００ポータブルフォトビューアーが挙げられるが、それらに限定されるものではない）、またはポータブルムービープレイヤー、あるいはプリンター／スキャナー／複写機の組み合わせ（その例としてはセイコーエプソン社製のエプソンスタイラスフォトＲＸ５８０、ＲＸ５９５、もしくはＲＸ６８０、エプソンスタイラスＣＸ４４００、ＣＸ７４００、ＣＸ８４００、もしくはＣＸ９４００Ｆａｘ、およびエプソンＡｃｕＬａｓｅｒ（登録商標）ＣＸ１１ＮＦが挙げられるが、それらに限定されるものではない）またはプリンター／スキャナーの組み合わせ（その例としてはすべてセイコーエプソン社製のエプソンＴＭ−Ｊ９０００、ＴＭ−Ｊ９１００、ＴＭ−Ｊ７０００、ＴＭ−Ｊ７１００、およびＴＭ−Ｈ６０００ＩＩＩが挙げられるが、それらに限定されるものではない）またはデジタルカメラ／カムコーダーの組み合わせ等の、それらの何らかの組み合わせ等の画像処理デバイスが挙げられる。
【００２２】
入力画像の仕様
図２を参照すると、方法２００における最初のステップは画像を入力することである（ステップ２１０）。入力画像は、カメラ（取り込み機構）１１２を操作するロボット１１６によって生成され得る。入力画像が１つの物体を包含しているならば、このとき、それは好ましくは画像エリアの少なくとも１０％を占めなければならない。画面内に１つを超える物体があるならば、対象となっている物体は好ましくは画像（画面）内の他のいずれの物体よりも少なくとも２倍は大きくなければならない。入力画像は、例えば、ＲＡＭ１０４またはハードディスク１６０内に記憶されている物体のＣＡＤモデルであることもできる。好ましい実施形態では、以下において記載されるように、物体の複数の画像が入力され、解析される。複数の画像の各々は好ましくは、他の画像の各々に示される視像とは異なる、物体の視像を包含する。これらの複数の画像は、ＣＡＤモデル、および／またはカメラを操作するロボット１１６を用いて生成され得る。
【００２３】
物体位置特定および抽出
本発明の物体位置特定（ステップ２１２）および物体抽出（ステップ２１４）段階は、画像または画面内に存在する物体を検出し、そのバウンディングボックスを計算する。物体抽出段階は物体の内側輪郭および外側輪郭の両方を抽出する。これらのステップ／段階は図３においてより詳細に示される。
【００２４】
一般的に言えば、これらのステップは、無地の背景上に１つ以上の物体を包含する単一チャネル画像３１０（図３）を処理する。これらのステップは基本的に画像内の活動のエリアを発見するものであり、従って、背景内のアーチファクトに敏感であってよい。入力画像内の物体は好ましくは単色であり且つ背景と物体との間の最小限のコントラストを有する。背景の色または異なる物体の色に対する追加の制限はない。物体のうちのあるものは背景よりも暗くてよく、あるものはそれよりも明るくてよい。物体は同様の色を有してもよいしまたは異なる色を有してもよい。
【００２５】
活動計算（図３、ステップ３１２）
活動計算ステップの間、画像３１０はサイズＳｘＳのブロックに分割される。Ｓは画素の数である。例として、Ｓは８である。ただし、特定の環境に従って、異なる値が選択され得る。この設定パラメーターＳは本願明細書においてＡＣＴＩＶＩＴＹ．ＳＣＡＬＥと呼ばれる。次に、本ステップは各ブロックについての標準偏差および平均強度を計算し、２つの行列、標準（ｓｔｄ）および平均（ａｖｅ）、として出力を返す。
【００２６】
活動的エリア選択（ステップ３１４）
本ステップでは、本発明は行列ｓｔｄの要素を閾値と比較し、閾値を超える要素を特定する。閾値は特定の環境のために選択され得る。例えば、これは色の閾値であり得よう。色深度を表すために８ビットが用いられるならば、このとき、閾値は０と２５５との間のどこかに設定されよう。理解されるように、活動的エリア選択ステップは、無地の背景と対照的にカラー物体に対応する画素ブロックを特定する。選択された活動閾値を超えると特定された要素は活動マップに入れられる。
【００２７】
領域解析（ステップ３１６）
領域解析ステップ３１６は、前のステップ３１４において作られた活動マップに対するブロブ解析を遂行する。本ステップにおいて用いられるパラメーターは、ＯＢＪＥＣＴＳ．ＳＩＺＥ．ＭＩＮ（デフォルト値は０．００１）およびＯＢＪＥＣＴＳ．ＳＩＺＥ．ＭＡＸ（デフォルト値は０．１）によって制御されるサイズ、ならびに候補領域の数ＯＢＪＥＣＴＳ．ＣＯＵＮＴ（デフォルト値は８）である。これらの設定パラメーターを画素からブロックに変換するために、サイズ制限はまずＡＣＴＩＶＩＴＹ．ＳＣＡＬＥの２乗で除される。領域解析ステップは各物体のためのバウンディングボックス、ならびにその１次および２次平均および面積を返す。
【００２８】
領域解析ステップの間、各領域はインデックスを与えられる。領域のインデックスは１から始まるが、必ずしも連続したものとなるわけではない。換言すると、サイズ制約に一致しなかった領域に対応する、欠けているインデックス値がある。インデックスマップは、各ブロックに付与されたインデックスを保持する。このマップは境界マップと呼ばれる。境界マップ内の、非ゼロのインデックスが与えられたブロックはいずれも境界ブロックである。残りのブロックは背景であるかまたは物体の内部を表すかのいずれかである。内部ブロックは、本願明細書において後に記載されるステップ３２０において検出される。
【００２９】
閾値計算（ステップ３１８）
閾値計算ステップ３１８は、各領域のための境界ブロックの内容を前景と背景とに分けるための最適閾値を求める。この手順は、領域毎に個別になされる以下の段階を通じて実行される。ここで、Ｉは、領域のための境界ブロックのうちの１つに入るすべての点のセットである。
【００３０】
１．Ｉの内容についての２５６ビンヒストグラムを作る。
２．Ｉの平均としてｔを計算する。
３．ｔの値を用いてＩを閾値処理し、Ｉ+およびＩ-を作る。
４．Ｉ+の平均としてｔ+を計算する。
５．Ｉ-の平均としてｔ-を計算する。
６．（ｔ+＋ｔ-）／２としてｔ*を計算する。
７．ｔとｔ*との間の差が１未満であれば、このときは、ｔを閾値として返し、さもなければ、ｔ＝ｔ*と設定し、３に行く。
本段階において計算された閾値（ＯＳＭＸ＿ＴＨＲＥＳＨＯＬＤ）は後のステップにおいて用いられる。
【００３１】
閾値計算ステップ３１８は、物体は背景よりも暗いのかまたはその逆であるのかも判定する。この判定は、各物体のためのバウンディングボックスの境界にある画素を調べ、閾値を超えるそれらの数を求めることに基づく。この数が、集計された画素の総数の半分を超えるならば、このとき、物体は背景よりも暗いと判定される。この情報ＯＳＭＸ＿ＩＮＶＥＲＳＥは後のステップにおいて用いられる。例えば、ＯＳＭＸ＿ＩＮＶＥＲＳＥは、物体が背景よりも暗ければ１に、明るければ０に設定され得よう。
【００３２】
内部検出（３２０）
内部検出ステップ３２０は境界マップを用い、内部マップを構築する。この手順は、すべてゼロの内部マップより開始し、領域毎に、そのバウンディングボックス内の各ブロックについて以下の操作を遂行する。
１．ブロックが境界マップ内になく且つ、ブロックについての平均が、（ＯＥ＿ＩＮＶＥＲＳＥがどのように設定されているかに依存して）ＯＥ＿ＴＨＲＥＳＨＯＬＤを上回りまたは下回り且つ、このブロックが境界マップ内に少なくとも１つの４連結隣接ブロックを有するならば、このときは、このブロックを内部マップ内に標識する。
【００３３】
境界閉塞（ステップ３２２）
境界マップが内部マップを包囲しないということがあり得る。その結果、次に記載される物体抽出段階の性質により、抽出された物体内に、望ましくない「くぼみ」が出現する場合がある。この問題を解決するために、境界閉塞ステップ３２２は、各領域のバウンディングボックス内で以下の操作を遂行することによって各領域のための境界マップを閉塞する。
１．ブロックが境界マップ内にもまたは内部マップ内にもなく且つ、それが内部マップ内に少なくとも１つの４連結隣接ブロックを有するならば、このときは、このブロックを境界マップ内に標識する。
【００３４】
物体抽出（ステップ３２４）
物体抽出ステップ３２４は、境界マップおよび内部マップに基づき物体を抽出する。この手順は各物体についてそれ自身のバウンディングボックス内で以下の操作を遂行する。
１．このブロックが内部マップ内に標識されているならば、このときは、それに対応するすべての画素を物体に属するものとして設定する。
２．このブロックが境界マップ内に標識されているならば、このときは、ブロックについての平均が、（ＯＥ＿ＩＮＶＥＲＳＥがどのように設定されているかに依存して）ＯＥ＿ＴＨＲＥＳＨＯＬＤを上回るまたは下回るならば、それに対応するすべての画素を物体に属するものとして設定する。
【００３５】
デュプレット作成（図２、ステップ２１６）
デュプレット作成は、実際の画像が用いられる、本発明における最後のステップである。本段階の後では、作業はデュプレット行列ならびに他の特徴点およびベクトルに対してなされる。
【００３６】
デュプレット作成は、以下に各々記載される、輪郭追跡、シングレット検出、およびデュプレット作成の３つのサブブロックを包含する。
【００３７】
輪郭追跡
輪郭追跡は、物体抽出段階によって返されたすべての輪郭を追跡する手順である。本段階において収集される情報はシングレット検出手順において用いられる。本発明においては、特定のアルゴリズムに限定されない任意の周知の輪郭追跡アルゴリズムが用いられ得る。利用されてよい輪郭追跡アルゴリズムの例としては矩形追跡、ムーア近傍、放射状走査が挙げられる。好ましい実施形態では、Ｔｈｅｏ Ｐａｖｌｉｄｉｓのアルゴリズムが用いられる。
【００３８】
シングレット検出
本段階は、特定の環境のために選択され得る２つのパラメーターＴＲＡＣＥ＿ＷＩＮＤＯＷおよびＳＩＮＧＬＥＴ＿ＤＩＳＴＡＮＣＥに依存する。これらの両パラメーターのためのデフォルト値は１２画素である。ＴＲＡＣＥ＿ＷＩＮＤＯＷの２倍よりも長いすべての輪郭について、以下の手順が輪郭上の点毎に実行される。
１．輪郭上の点の周りのＴＲＡＣＥ＿ＷＩＮＤＯＷの点についての平均のＸおよびＹ座標を求める。
２．輪郭上の点を、ＴＲＡＣＥ＿ＷＩＮＤＯＷだけ左および右に離れた２つの点に連結する。
３．２つの角度を求め、それらを入射角度および出射角度と呼ぶ。
４．入射角度および出射角度を表す２つのベクトルの内積を求める。この内積の符号を変更し、それを曲率と呼ぶ。
５．この点がその周りのＳＩＮＧＬＥＴ＿ＤＩＳＴＡＮＣＥの点群内の最大曲率を有するならば、その点をシングレットとして標識する。
６．各シングレットについてのＸおよびＹ座標を、入射および出射角度ならびにそれらに対応する曲率とともに記憶する。
【００３９】
デュプレット作成
デュプレット作成は、検出されたシングレットを組み合わせてデュプレットにする手順である。デュプレットを作成するプロセスは以下のステップを包含する。
１．その（ｉ、ｊ）要素がｉ番目とｊ番目のシングレットの間の距離を包含する行列Ｄを作る。
２．最小閾値未満であるかまたは最大閾値を上回るＤの要素をすべてＮＡＮ（Ｎｏｔ ａ Ｎｕｍｂｅｒ（非数）、初期化されていない変数を示す特定記号）として変更する。最小閾値および最大閾値は、ＤＩＳＴＡＮＣＥ．ＭＩＮ（デフォルト値は０．０１）およびＤＩＳＴＡＮＣＥ．ＭＡＸ（デフォルト値は０．２５）に画像の最小寸法を乗じられたものとしてそれぞれ計算される。
３．すべてゼロのＳｘ１配列を作り、それをｄｅｇと呼ぶ。ｄｅｇ（ｓ）はｓ番目のシングレットに連結されるシングレットの数を包含することになる。
４．ＤがＮＡＮしか包含しなくなるか、またはシングレットのための最大数が指定されている場合には該最大に達するまで、Ｄをスキャンする。
５．Ｄの最小の要素を見いだす。それを（ｓ１，ｓ２）と呼ぶ。ｄｅｇ（ｓ１）およびｄｅｇ（ｓ２）の両方をインクリメントする。ｄｅｇ（ｓ１）またはｄｅｇ（ｓ２）のどちらかが最大度数ＤＥＧＲＥＥ（デフォルトは１０）よりも大きくなれば、このときは、該シングレットに対応する行および列内のすべての要素をＮＡＮとして設定する。例えば、ｄｅｇ（ｓ１）がＤＥＧＲＥＥよりも大きくなれば、このときは、すべてのｓについてＤ（ｓ、ｓ１）およびＤ（ｓ１、ｓ）をＮＡＮに設定する。
６．対（ｓ１、ｓ２）について、それらを一緒に連結する角度ならびにそれらを連結する線の長さを計算し、それらをそれぞれ角度および距離と呼ぶ。両シングレットの一時的複製の入射および出射角度から角度を減じる。これで、デュプレットは＜角度，距離，ｓ１．入射，ｓ１．出射，ｓ２．入射，ｓ２．出射＞として表されることになる。
７．デュプレット行列を返す。
【００４０】
デュプレット比較（図２、ステップ２１８）
デュプレット比較は、２つのデュプレット行列内の項目を比較し、一致のリスト、および従って候補姿勢の第１のリストを作るプロセスである。２つのデュプレット行列はＤ１およびＤ２であるとして、プロセスは以下のように遂行される。
【００４１】
１． Ｄ１内のあらゆるデュプレットｄ１およびＤ２内のｄ２について、これらの条件がすべて満足されているかどうかを判定する。
｜ｄ１．ｓ１．入射−ｄ２．ｓ１．入射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ１．出射−ｄ２．ｓ１．出射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ２．入射−ｄ２．ｓ２．入射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ２．出射−ｄ２．ｓ２．出射｜＜ＴＨＲＥＳＨＯＬＤ
ここで、ＴＨＲＥＳＨＯＬＤは設定変数ＤＵＰＬＥＴＳ．ＴＨＲＥＳＨＯＬＤによって決められる。
これらの条件が満たされれば、このときは、候補姿勢（ｄ１．長さ／ｄ２．長さ，ｄ１．角度−ｄ２．角度）を候補のリストに追加する。さらに、２つのシングレットおよび両デュプレットのＸおよびＹ座標に注目する。この候補を「直」としてタグ付けする。
【００４２】
２． 同様に、これらの条件が満足されるかどうかを判定する。
｜ｄ１．ｓ１．入射−ｄ２．ｓ２．入射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ１．出射−ｄ２．ｓ２．出射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ２．入射−ｄ２．ｓ１．入射｜＜ＴＨＲＥＳＨＯＬＤ
｜ｄ１．ｓ２．出射−ｄ２．ｓ１．出射｜＜ＴＨＲＥＳＨＯＬＤ
この場合、ｄ１．角度−ｄ２．角度−パイと記録されることになる角度を除き、同様の候補姿勢がリストに追加されることになる。この候補は「逆」としてタグ付けされることになる。
【００４３】
３． 候補のリストを、次に記載されるクラスター化段階に渡す。
候補クラスター化（図２、ステップ２２０）
候補クラスター化は、デュプレット比較を通じて作られた姿勢候補を取り入れ、候補の大きなセットによって各々表される限られた数の姿勢を推定するプロセスである。本手順は、いずれも以下において記載される２つの段階、スケール−角度クラスター化、およびＸ−Ｙクラスター化、を包含する。
【００４４】
スケール−角度クラスター化
本段階の目的は、デュプレット比較を通じて作る候補姿勢に基づき候補（スケール，角度）対のリストを作ることである。
ＳおよびＡは、候補スケールおよび角度を持つ２つの１ｘＮであるとする。スケール−角度クラスター化手順は以下のようになされる。
１．Ｓの値の底ＢＡＳＥの対数を計算することによってＳ＿Ｌを作る。
２．ＡおよびＳ＿Ｌのヒストグラムを独立に作る。各ヒストグラムはＢＩＮＳのビンを包含することになる。Ａについてのヒストグラムは−パイないしパイのレンジに及ぶことになる。Ｓ＿Ｌは、ＳＣＡＬＥ．ＭＩＮおよびＳＣＡＬＥ．ＭＡＸのレンジ内で、どちらも底ＢＡＳＥで解析されることになる。
３．どちらのヒストグラム上の点も、もしそれがその右側のＤの点よりも高く且つその左側のＤの点よりも高いかまたはそれに等しければ、「ピーク」として標識する。
４．各ヒストグラムについてＣ１個の最高ピークを独立に選択する。
５．すべてのスケール候補をすべての角度候補と交差させ、スケール−角度候補のリストを作る。このリストをＸ−Ｙクラスター化段階に渡す。各スケール−角度候補について、この対を生じさせた一致デュプレット内のシングレットの位置も送る。
６．各スケール−角度候補についての信頼性を、それを表すデュプレット一致の対の数を２つのデュプレット行列内のデュプレットの数の最小で除したものとして計算する。
７．スケール−角度候補の数がＣ２を超えるならば、このときは、最高の信頼性を有するＣ２個のものを取る。
【００４５】
Ｘ−Ｙクラスター化
スケール−角度クラスター化段階の出力は（スケール，角度）候補のセットである。Ｘ−Ｙクラスター化段階は、各（スケール，角度）候補について以下のように、候補に平行移動情報を加えるプロセスである。
１．この候補についてのシングレット位置を、軸系の中心が画像の中心に移動するように改変する。このプロセスは２つのデュプレット行列について独立に実行されることになる。
２．クエリシングレット位置を角度によって回転させる。
３．クエリシングレットをスケールによってスケーリングする。
４．クエリと参照との間のシングレット位置についてのＸおよびＹにおける差を独立に求める。これらをｄｘおよびｄｙ配列と呼ぶ。
５．本段階においては、ｄｘ−ｄｙ対は、スケール−角度対に対して実行されるものと同様の２次元クラスター化アルゴリズムを受けることができるか、またはより迅速な演算が続いて行われることができる。
６．ｄｘおよびｄｙの平均を独立に求め、この情報をスケール−角度対に付加し、かくして、姿勢候補（角度，スケール，ｄｘ，ｄｙ，信頼性）を作る。この姿勢候補についての信頼性はスケール−角度対についての信頼性に等しいままとなることになる。
７．設定パラメーターによって要求される場合には、以下において記載されるように、重複調査を遂行する。
８．信頼性の最高値に対応するＣ２個の候補を取り、それらを次の段階に報告する。
【００４６】
重複の考慮
重複の考慮はＯＶＥＲＬＡＰが非負である場合のみ機能する。重複の考慮は以下のようになされる。
１．（角度，スケール，ｄｘ，ｄｙ，信頼性）情報に従い参照バウンディングボックスを変換する。回転され、スケーリングされ、移動されたバウンディングボックスを覆う最小の矩形を見いだす。
２．改変された、参照のバウンディングボックス、およびクエリのバウンディングボックスを両方とも覆う最小の矩形を見いだす。この矩形の面積をＡと呼ぶ。
３．もし、ｍｉｎ（Ａ１，Ａ２）／ＡがＯＶＥＲＬＡＰ未満であれば、この候補を不適当として標識する。ここで、Ａ１およびＡ２は、参照の改変されたバウンディングボックスの面積、およびクエリの面積である。
４．不適当として標識された候補をリストから削除する。
【００４７】
輪郭デュプレットデータベース（図２、２２２）
輪郭デュプレットデータベース（Ｃｏｎｔｏｕｒ−Ｄｕｐｌｅｔｓ Ｄａｔａｂａｓｅ、ＣＤＤＢ）ファイルは、各々仰角および方位角に付随するデュプレット行列のリストを包含する。ＣＤＤＢファイルを生成するために、上述のアルゴリズムは訓練用画像（図２、２２４）に対してデュプレット作成を遂行することになり、次に、結果として生じる、仰角−方位角表示を各々伴うデュプレット行列をＣＤＤＢ２２２内に記憶することになる。これらのサンプルは視像と呼ばれる。
ＣＤＤＢファイルは実際には、訓練用画像に関する詳細を包含するファイルを伴う。これらの詳細は様々な視覚化を作るために必要なものであり、アルゴリズムの通常の演算には必要とされない。
クエリが実行されると、手順はデータベース内の視像毎に繰り返される。アルゴリズムの最終出力は、最高の対応する信頼性値を有する、ＣＤＤＢＣ．ＳＥＡＲＣＨ．ＣＡＮＤＩＤＡＴＥＳ．ＴＯＴＡＬの数の候補である。次に、各候補を作った視像の角度表示が各候補に付加され、かくして姿勢の（仰角、方位角、角度、スケール、ｄｘ、ｄｙ、信頼性）表示を作る。以上に概説された物体検出ステップの結果は、姿勢推定値である、姿勢のこれらの表示であり、メモリー、例えばＲＡＭ１０４またはハードディスク１６０、内に記憶される。これらの姿勢推定値は次に、製品の組み立ての際の物体／部品のロボット認識において用いられ得る。
【００４８】
出力の視覚化
様々な視覚化が作られ得る。これらの視覚化の２つがモデルビューおよびオーバーレイである。モデルビューとは、スケール、角度、および平行移動も反映するように改変された一致訓練用画像の画像である。オーバーレイとは、クエリ画像上のモデルビューのオーバーレイである。
【００４９】
物体モデルの仕様
現在、訓練手順は、様々なパラメーターによって支配される通りの、様々な姿勢をとる対象となっている物体を示す画像を必要とする。これらの画像を作る実用的且つより簡便な方法が、物体の３Ｄ視像を作る３次元視覚化ツールであるサンプルシミュレーター２２８を用いるものである。
【００５０】
設定ユーティリティー（図２、２３０）
上述されたように、本発明の方法の異なる部分は異なる設定パラメーターを用いる。これらのパラメーターのいくつかの例示的な（デフォルト）値が上述の記載において与えられている。しかし、これらの値はユーザーによって特定の環境に合うように設定され得る。設定ユーティリティーは、これらのパラメーターのための適切な値を求め、それにより、ユーザーからの直感的入力を用いるのは最小限にしてそれらを設定する対話型ツールである。
【００５１】
以下のセクションは、特に物体の画像がカメラ画像である場合に物体の姿勢推定値を精緻化する本発明の態様を記載する。
【００５２】
本発明の姿勢精緻化はアラインメント問題としてモデル化される。我々は、対象となっている物体、すなわちロボットが特定し、拾い上げなければならない部品、の３Ｄモデル、および物体を撮像するために用いられるカメラ１１２のカメラパラメーターより開始する。目標は、モデルに対してそれが画像内の対象となっている物体と合致するように適用されるべき３Ｄ（ユークリッド、６自由度（６ ｄｅｇｒｅｅｓ ｏｆ ｆｒｅｅｄｏｍ））変換を見いだすことである。その結果、姿勢精緻化はコスト関数の反復的な最適化問題として実装される。物体前景を負担するコスト以外に、コスト関数は、局所的特徴点または境界特徴点を合わせるまたは一致させる画像一致コストを含んでよい。
【００５３】
アルゴリズムをより良く理解するために、コスト関数および緩和解の定義の前にカメラ投影モデル、ＯｐｅｎＧＬ仮想カメラモデルおよび画像ヤコビ行列が導出される。
【００５４】
カメラ投影モデル
本発明のカメラ投影モデルはピンホールカメラモデルに基づく。ピンホールカメラはカメラ機能の最も単純で理想的なモデルである。それは無限小の穴を有し、そこを通って光が入り、該穴と向かい合うカメラ表面上に倒立像を形成する。図４に示されるように、透視投影は３次元物体の、２次元画像平面上への投影である。実際には、画像の焦点をカメラの焦点面上に合わせるためにレンズを用いなければならない。焦点面は、画像平面に平行である１つの特定の平面である。ピンホールカメラ座標はワールド座標に合わせられるとすると、単純な幾何学は以下を示す。
ここで、（ｘw，ｙw，ｚw）は３Ｄワールド座標における物体の点であり、（ｘim，ｙim）は２Ｄ画像平面座標における点である。
【００５５】
カメラフレーム座標から画素（画像）座標への投影モデルは以下のように導出される。
ここで、Ｆは焦点距離であり、ＳｘおよびＳｙは、焦点にあるセンサー平面から画像または画素座標への、ｘおよびｙ方向におけるスケーリング係数である。ＳｘおよびＳｙスケーリング係数はＣＣＤセンサーのセルの幅および高さ、ならびに分解能に比例する。我々は、モデルスケーリング係数λxおよびλyを得るようにカメラを較正することができる。
ここで、（ｘ0，ｙ0）は画像または画素座標におけるカメラ座標の原点の投影である。
【００５６】
ｕ＝ｘim−ｘ0およびｖ＝ｙim−ｙ0とすると、式（３）は以下のように表され得る。
【００５７】
画像ヤコビ行列
画像ヤコビ行列は、作業空間内の或る物体の速度と、作業空間の観察される画像内で起きる対応する変化との間の関係に基づいて構築されなければならない。
【００５８】
特徴点Ｓの現在の投影は座標ｆ＝（ｕ，ｖ）を有する。画像ヤコビ行列は以下のように算定される。
【００５９】
座標（ｘc，ｙc，ｚc）またはカメラフレームにおける（ｘ，ｙ，ｚ）を有する点Ｐを考える。透視投影を用いると、Ｐの画像平面座標は式（４）によって与えられる。
【００６０】
カメラフレームにおける座標（ｘ，ｙ，ｚ）を有する単一の点についての画像ヤコビアンを構築するために、式は以下のステップで導出される。
【００６１】
ｕおよびｖについての時間導関数を算出する。
式を組み合わせ、代数を解く。
【００６２】
ステップ１、割り算の規則を用いると、
【００６３】
ステップ２、透視投影の式は、以下のようにｘおよびｙのための表現式を与えるように書き直され得る。
【００６４】
【００６５】
ステップ４、式を組み合わせ、次式を得る
これらの式は画像ヤコビ行列形式で書かれることができる。
【００６６】
ＯｐｅｎＧＬ仮想カメラモデル
モデルを画像上に投影するために、本発明は好ましくは、既存のハードウェアを用いて高速レンダリングおよび隠線消去を実行することができるＯｐｅｎＧＬを用いる。加えて、ＯｐｅｎＧＬは各画素における深さ情報を記憶することができる。この情報を用いて、各輪郭点に対応する３Ｄ点は計算される。図５はＯｐｅｎＧＬ投影および正規化デバイス座標（ＮＤＣ）を示す。好ましい実施形態ではＯｐｅｎＧＬが用いられるが、本発明はこのレンダリングアプリケーションプログラミングインタフェース（ＡＰＩ）に限定されるものではなく、ＤｉｒｅｃｔＸ、レイトレーシングなど等の他のレンダリングＡＰＩが利用されてもよい。
【００６７】
透視投影では、角錐台（視点座標）における３Ｄ点は立方体（ＮＤＣ）に写像され、ｘ座標は［ｌ，ｒ］から［−１，１］に、ｙ座標は［ｂ，ｔ］から［−１，１］に、ｚ座標は［ｎ，ｆ］から［−１，１］に写像される。
【００６８】
投影行列は視点座標系における頂点をクリップ座標系に変換する。
【００６９】
スケーリング行列および画素座標計算を適用すれば、ＯｐｅｎＧＬにおける３Ｄ頂点の新しい投影は以下のようになる。
式（３）および（１４）を用いると、ＯｐｅｎＧＬ仮想カメラの、実カメラモデルへの対応を求めることができる。
【００７０】
カメラ座標およびＯｐｅｎＧＬ仮想カメラの視点座標の定義は異なることに留意されたい。その結果、２つの座標の間の対応を導出するには以下の変換が必要となる。
本発明では、ＯｐｅｎＧＬは、モデルを投影するためにのみ用いられる。すべての式はデフォルトでは実カメラモデルを用いて導出される。
【００７１】
２．４ コスト関数
本発明の姿勢精緻化方法はエネルギーベースのコスト関数を最小化する。コスト関数は、３Ｄ姿勢（６ＤｏＦ）を用いるモデル投影が画像内の対象となっている物体と合致するよう、最小値を有するように定義される。
ここで、Ｉ（ｘ，ｙ）は入力画像であり、Ｔ（ｘ，ｙ）は所与の３Ｄ姿勢を有するモデル投影の２値マスク画像である。
【００７２】
２値マスクのＴ（ｘ，ｙ）の画像は所与の３Ｄ姿勢およびカメラパラメーターについてのモデルの投影であり、以下の通りの定義を有する。
ＯｐｅｎＧＬは、物体モデルを２Ｄ仮想画像に投影することによって２値マスク画像の高速レンダリングを実行することができる。
【００７３】
ｕ1およびｕ2は物体マスクの内部および外部の入力画像の平均値であり、以下のように定義される。
【００７４】
投影モデル輪郭曲線Ｃは、画像を物体の「内側」と物体の「外側」とに分けるＴ（ｘ，ｙ）から得られ得る。項Ｆ1は物体の内部のフィッティングエネルギーであり、Ｆ2は物体の外部のフィッティングエネルギーである。
【００７５】
単純な場合のコスト関数の基本的な考え方は以下のように説明される。画像Ｉ（ｘ，ｙ）は、物体および背景についてのｕobjおよびｕbackの個別の値の、おおよそ区分的に一定な強度の２つの領域によって形成されるとする。画像Ｉ（ｘ，ｙ）内の物体の境界はＣ0によって示される。投影モデル輪郭曲線Ｃが画像Ｉ（ｘ，ｙ）内の物体境界Ｃ0と合致するならば、このとき、物体の内部ではｕ1＝ｕobj、物体の外部ではｕ2＝ｕbackを得、その結果、次式を得ることができる。
ｉｎｆ｛Ｆ1（Ｃ）＋Ｆ2（Ｃ）｝≒０≒Ｆ1（Ｃ0）＋Ｆ2（Ｃ0）
【００７６】
この場合、投影モデル輪郭曲線Ｃが画像内の物体境界Ｃ0と合致するとエネルギー関数は最小化されることは明らかである。
【００７７】
これは、図６に示されている通りの単純な場合において理解され得る。同図は投影モデル曲線の位置のあり得る場合をすべて示している。例えば、図６（ａ）のように曲線Ｃが物体の外部にある場合には、Ｆ1（Ｃ）＞０且つＦ2（Ｃ）≒０である。図６（ｂ）のように曲線Ｃが物体の内部にある場合には、このときは、Ｆ1（Ｃ）≒０且つＦ2（Ｃ）＞０である。図６（ｃ）のように曲線Ｃが物体の内部および外部のどちらにもある場合には、このときは、Ｆ1（Ｃ）＞０且つＦ2（Ｃ）＞０である。最後に、図６（ｄ）に示されるようにＣ＝Ｃ0で投影モデル曲線Ｃが物体の境界上にある場合には、Ｆ1（Ｃ）≒０且つＦ2（Ｃ）≒０であり、フィッティングエネルギーは最小化される。
【００７８】
我々のコスト関数の定義に基づき、例えばＲＡＭ１０４またはハードディスク１６０内に記憶されている姿勢推定値は、上述のフィッティング項を最小化するべく更新されることになり、我々は、一致した特徴点または境界特徴からいくつかの他の項または制約を加えることができる。例えば、もし、２Ｄ入力画像ｐj＝（ｐjx，ｐjy）Tと、仮想画像内にπ（Ｐj）＝（ｕj，ｖj）Tとして投影される３Ｄモデル特徴Ｐj＝（Ｘjobj，Ｙjobj、Ｚjobj）との間に一致した特徴点のセット（例えばｊ＝１．．．Ｎ個の一致対）があれば。追加の制約項は以下のように定義されてよい。
ここで、ｗjは特徴一致についての重みであり、それは一致信頼性またはスコアであってよく、π（Ｐj）＝（ｕj，ｖj）Ｔはモデル特徴点の、Ｐi＝（Ｘiobj，Ｙiobj，Ｚiobj）から所与の３Ｄ姿勢を有する画像への投影を示すことである。‖ ‖は画像座標におけるユークリッド距離であってよい。
【００７９】
式（１９）すなわち一致エネルギーの最小化は精緻化のための初期姿勢推定を提供することができる。それは、収束およびロバストネスを向上させることができるように、姿勢精緻化のための制約項として用いられてもよい。
【００８０】
すると、コスト関数は以下のように定義されてよい。
ここで、ηは、ＥcとＥmatchとの間のエネルギーのバランスをとる重み関数である。
我々はＥcおよびＥmatchの両方についての勾配流を導出することになるが、最初の実行では、η＝０として、Ｅcのエネルギーを用いるだけである。
【００８１】
姿勢を反復的に更新するために速度スクリューを計算する
勾配降下法に従い、エネルギーＥは最小値に近づくことが期待される。
【００８２】
姿勢パラメーターｒに関するＥの偏微分は、連鎖法則を用いて算出され得る。
【００８３】
Ｅcの偏微分
まずＥcの偏微分を導出する
第２および第３項については、それらがゼロであることを証明することができる。
２値マスクＴ（ｘ，ｙ）の画像は所与の３Ｄ姿勢およびカメラパラメーターについてのモデルの投影である。
【００８４】
Ｔ（ｘ，ｙ）は、式（１７）において定義される通りの、モデルの投影の２値マスクであるので。境界Ｃ上を除いてＴ（ｘ，ｙ）の勾配はゼロである。
【００８５】
Ｅmatchの偏微分
一致エネルギーは、画像座標における、入力画像内の特徴点と投影仮想画像内の、特徴点との間の距離一致した特徴点を測るコスト関数である。
【００８６】
画像ヤコビ行列の微分ステップと同様に、次式を得ることができる。
【００８７】
部分方程式は画像およびカメラ座標で導出されており、３Ｄ特徴点Ｐj＝（Ｘjobj，Ｙjobj，Ｚjobj）は、部分方程式を計算する際にはカメラ座標に変換されることになることに留意されたい。
【００８８】
エネルギー関数を最小化するためのガウス・ニュートン法
我々の実装では、エネルギー関数を最小化するためにガウス・ニュートン法を用いた。ガウス−ニュートンアルゴリズムは２乗和の最小値を求める。
【００８９】
エネルギーＥcを最小化する
【００９０】
エネルギーＥmatchを最小化する
【００９１】
エネルギーＥ＝Ｅc＋Ｅmatchを最小化する
ｅおよびＪは、ｅc、ηｅmatchならびにＪcおよびηＪmatchをそれぞれ連結することによって得られる。
【００９２】
姿勢パラメーターまたは変換行列を更新する
物体座標からカメラ座標への変換は、変換による表示であってよい。
時刻ｔにおける或る固定フレーム（物体座標）とカメラフレームとの間の相対変位を示すためにｇ（ｔ）＝（Ｒ（ｔ），Ｔ（ｔ））を用いることにする。カメラが時刻ｔ1，ｔ2．．．ｔmにおいてそれぞれロケーションｇ（ｔ1），ｇ（ｔ2）．．．ｇ（ｔm）にあるならば、このとき、同じ点ｐの座標はそれに応じてＸ（ｔi）＝ｇ（ｔi）Ｘ０，ｉ＝１．．．ｍとして与えられる。
【００９３】
図７を参照すると、ｔ2およびｔ1におけるカメラの間の相対運動はｇ（ｔ2，ｔ1）として示されることとなり、このとき、同じ点ｐの座標同士の間には以下の関係がある。
Ｘ（ｔ2）＝ｇ（ｔ2，ｔ1）Ｘ（ｔ1） （３９）
【００９４】
今度は、図７に示される通りの、ｔ＝ｔ3におけるカメラの第３の位置を考える。ｔ3とｔ2とにおけるカメラの間の相対運動はｇ（ｔ3，ｔ2）であり、ｔ3とｔ1とにおけるカメラの間の相対運動はｇ（ｔ3，ｔ1）である。このとき、座標の間には以下の関係がある。
Ｘ（ｔ3）＝ｇ（ｔ3，ｔ2）Ｘ（ｔ2）＝ｇ（ｔ3，ｔ2）ｇ（ｔ2，ｔ1）Ｘ（ｔ1） （４０）
【００９５】
ｔ3およびｔ1における座標の間の直接的関係と比較すると
Ｘ（ｔ3）＝ｇ（ｔ3，ｔ1）Ｘ（ｔ1） （４１）
【００９６】
連続運動のための合成規則が成り立たなければならない。
ｇ（ｔ3，ｔ1）＝ｇ（ｔ3，ｔ2）ｇ（ｔ2，ｔ1） （４２）
【００９７】
合成規則に基づけば、ｇ（ｔn，ｔ1）についての姿勢パラメーターは
ｇ（ｔn，ｔ1）＝ｇ（ｔn，ｔn-1）ｇ（ｔn-1，ｔ1） （４３）
【００９８】
勾配降下法より、反復ｎ−１からｎへの相対変位を得ることができる。その結果、反復ｎのための姿勢パラメーター更新は、ｇ（ｔn，ｔn-1）を計算することによって得られる。
【００９９】
および
【０１００】
【０１０１】
実行
姿勢推定はエネルギー関数の最適化または最小化としてモデル化される。反復的に姿勢更新は計算され、エネルギーを最小化することになる。以下は、上述された方法の例示的な実行である。
ステップ１：画像、モデル、カメラパラメーターを入力する。
ステップ２：初期姿勢パラメーターを得る。
ステップ３：与えられた姿勢パラメーターを用いてＯｐｅｎＧＬによってモデルを仮想画像に投影する。２値マスク画像Ｔ（ｘ，ｙ）および対応する深さ情報／マップが得られる。
ステップ４：姿勢を反復的に更新するために速度スクリューを計算する。（ｉ）式（１８）によって物体の内部および外部の平均値を計算する。（ｉｉ）２値マスクから輪郭Ｃを得、深さ情報を用いて３Ｄ輪郭点を得る。（ｉｉｉ）輪郭点についての、ｘおよびｙ方向における勾配∇Ｔ（ｘ，ｙ）を計算する。（ｉｖ）式（２６）を用いて画像ヤコビ行列を計算する。（ｖ）式（２７）を用いて勾配流を計算し、ガウス・ニュートン法を用いて式（３５）によって制御入力（速度スクリュー）を得る。
ステップ５：式（４５）によって、制御入力（速度スクリュー）および所与のステップサイズを用いて相対変位を計算する。
ステップ６：式（４６）および（４７）によって姿勢パラメーターを更新する。
ステップ７：もし、姿勢パラメーターの変化が非常に小さいか、または最大反復数に達すれば、終了に行き、さもなければステップ３に戻る。
ステップ８：終了。
【０１０２】
本発明はいくつかの特定の実施形態と併せて記載されているが、上述の記載に鑑みれば、多くのさらなる代替、変更および変形が容易に分かることは当業者には明白である。それ故、本願明細書において記載されている本発明はこのような代替、変更、応用および変形をすべて、添付の請求項の精神および範囲内にあってよいものとして含むように意図されている。
【特許請求の範囲】
【請求項１】
入力画像から物体の姿勢を推定して記憶する物体姿勢推定方法であって、
物体を包含する画像を入力することと、
前記入力画像の２値マスクを作成することと、
前記入力画像の前記２値マスクからシングレットのセットを抽出することであって、各シングレットは、前記入力画像内の前記物体の内側および外側輪郭内にある点を表す、抽出することと、
シングレットの前記セットを連結して、デュプレックス行列として表されるメッシュにすることと、
候補姿勢のセットを作るべく２つのデュプレックス行列を比較することと、
物体姿勢推定値を作り、前記物体姿勢推定値を記憶することと、
を含む、物体姿勢推定方法。
【請求項２】
前記物体の複数の画像を入力することをさらに含み、各画像は、前記複数の画像の互いにおける視像とは異なる、前記物体の視像を包含する、請求項１に記載の物体姿勢推定方法。
【請求項３】
前記物体の前記複数の画像の各々における前記視像を、前記物体のためのＣＡＤモデルを用いて生成することをさらに含む、請求項２に記載の物体姿勢推定方法。
【請求項４】
前記物体の前記複数の画像の各々における前記視像を、カメラを備えたロボットを用いて生成することをさらに含む、請求項２に記載の物体姿勢推定方法。
【請求項５】
前記入力画像内の前記物体を検出し、前記物体のバウンディングボックスを計算することをさらに含む、請求項１に記載の物体姿勢推定方法。
【請求項６】
前記物体の内側および外側輪郭を抽出することをさらに含む、請求項１に記載の物体姿勢推定方法。
【請求項７】
前記姿勢推定値をエネルギー関数の最適化としてモデル化することによって前記物体姿勢推定値を精緻化することをさらに含む、請求項１に記載の物体姿勢推定方法。
【請求項８】
前記エネルギー関数におけるエネルギー値を最小化するべく姿勢推定値を反復的に計算することをさらに含む、請求項７に記載の物体姿勢推定方法。
【請求項９】
前記姿勢推定値を反復的に計算するために速度スクリューを計算することをさらに含む、請求項８に記載の物体姿勢推定方法。
【請求項１０】
レンダリングアプリケーションプログラミングインタフェース（ａｐｐｌｉｃａｔｉｏｎ ｐｒｏｇｒａｍｍｉｎｇ ｉｎｔｅｒｆａｃｅ、ＡＰＩ）を用いて前記物体のモデル輪郭曲線を仮想画像に投影することをさらに含む、請求項７に記載の物体姿勢推定方法。
【請求項１１】
入力画像から物体の姿勢を推定して記憶する物体姿勢推定装置であって、
プロセッサーであって、
物体を包含する入力画像を受信すること、
前記入力画像の２値マスクを作成すること、
前記入力画像の前記２値マスクからシングレットのセットを抽出することであって、各シングレットは、前記入力画像内の前記物体の内側および外側輪郭内にある点を表す、抽出すること、
シングレットの前記セットを連結して、デュプレックス行列として表されるメッシュにすること、
候補姿勢のセットを作るべく２つのデュプレックス行列を比較すること、ならびに
物体姿勢推定値を作ること、
を行うプロセッサーと、
前記物体姿勢推定値を記憶するメモリーと、
を含む、物体姿勢推定装置。
【請求項１２】
前記プロセッサーは前記物体の複数の画像を受信し、各画像は、前記複数の画像の互いにおける視像とは異なる、前記物体の視像を包含する、請求項１１に記載の物体姿勢推定装置。
【請求項１３】
前記物体のためのＣＡＤモデルを記憶するストレージをさらに含み、前記プロセッサーは、前記物体のための前記ＣＡＤモデルを用いて前記物体の前記複数の画像の各々における前記視像を生成する、請求項１２に記載の物体姿勢推定装置。
【請求項１４】
前記物体の前記複数の画像の各々における前記視像を生成するカメラを備えたロボットをさらに含む、請求項１２に記載の物体姿勢推定装置。
【請求項１５】
物体の推定姿勢を精緻化する物体姿勢推定精緻化方法であって、
推定姿勢をとる物体の画像、前記物体のモデル、および前記推定姿勢をとる前記物体の前記画像を撮るために用いられるカメラのパラメーターを入力することと、
２値マスク画像および画像深さ情報を得るべく、前記カメラの前記パラメーターおよび初期姿勢パラメーターを用いて前記物体の前記モデルを前記物体の仮想画像に投影することと、
前記２値マスク画像および画像深さ情報を用いて前記初期姿勢パラメーターを新しい姿勢パラメーターに更新し、エネルギー関数を最小化するべくまたは反復の最大数に達するまで前記新しい姿勢パラメーターを反復的に更新することと、
を含む、物体姿勢推定精緻化方法。
【請求項１６】
コスト関数を用いて前記物体の内部および外部の平均値を計算することと、
前記２値マスク画像から前記物体の輪郭Ｃを計算し、前記画像深さ情報を用いて３Ｄ輪郭点を計算することと、
をさらに含む、請求項１５に記載の物体推定姿勢精緻化方法。
【請求項１７】
前記輪郭点についての、ｘおよびｙ方向における勾配∇Ｔ（ｘ，ｙ）を計算することと、
画像ヤコビ行列を計算することと、
ガウス・ニュートン法を用いて勾配流および速度スクリューを計算することと、
をさらに含む、請求項１６に記載の物体推定姿勢精緻化方法。
【請求項１８】
前記速度スクリューおよび所与のステップワイズを用いて相対変位を計算すること
をさらに含む、請求項１７に記載の物体推定姿勢精緻化方法。
【請求項１９】
前記推定姿勢をとる前記物体の前記画像は、
前記物体を包含する画像を入力することと、
前記入力画像の２値マスクを作成することと、
前記入力画像の前記２値マスクからシングレットのセットを抽出することであって、各シングレットは、前記入力画像内の前記物体の内側および外側輪郭内にある点を表す、抽出することと、
シングレットの前記セットを連結して、デュプレックス行列として表されるメッシュにすることと、
候補姿勢のセットを作るべく２つのデュプレックス行列を比較することと、
物体姿勢推定値を作ることと、
によって形成される、請求項１５に記載の物体推定姿勢精緻化方法。
【請求項２０】
１つ以上の有形の非一時的コンピューター可読媒体であって、プロセッサーによって実行されると請求項１に記載の物体姿勢推定方法に従い入力画像から物体の姿勢を推定するコンピューター可読命令をその上に有する、コンピューター可読媒体。
【請求項１】
入力画像から物体の姿勢を推定して記憶する物体姿勢推定方法であって、
物体を包含する画像を入力することと、
前記入力画像の２値マスクを作成することと、
前記入力画像の前記２値マスクからシングレットのセットを抽出することであって、各シングレットは、前記入力画像内の前記物体の内側および外側輪郭内にある点を表す、抽出することと、
シングレットの前記セットを連結して、デュプレックス行列として表されるメッシュにすることと、
候補姿勢のセットを作るべく２つのデュプレックス行列を比較することと、
物体姿勢推定値を作り、前記物体姿勢推定値を記憶することと、
を含む、物体姿勢推定方法。
【請求項２】
前記物体の複数の画像を入力することをさらに含み、各画像は、前記複数の画像の互いにおける視像とは異なる、前記物体の視像を包含する、請求項１に記載の物体姿勢推定方法。
【請求項３】
前記物体の前記複数の画像の各々における前記視像を、前記物体のためのＣＡＤモデルを用いて生成することをさらに含む、請求項２に記載の物体姿勢推定方法。
【請求項４】
前記物体の前記複数の画像の各々における前記視像を、カメラを備えたロボットを用いて生成することをさらに含む、請求項２に記載の物体姿勢推定方法。
【請求項５】
前記入力画像内の前記物体を検出し、前記物体のバウンディングボックスを計算することをさらに含む、請求項１に記載の物体姿勢推定方法。
【請求項６】
前記物体の内側および外側輪郭を抽出することをさらに含む、請求項１に記載の物体姿勢推定方法。
【請求項７】
前記姿勢推定値をエネルギー関数の最適化としてモデル化することによって前記物体姿勢推定値を精緻化することをさらに含む、請求項１に記載の物体姿勢推定方法。
【請求項８】
前記エネルギー関数におけるエネルギー値を最小化するべく姿勢推定値を反復的に計算することをさらに含む、請求項７に記載の物体姿勢推定方法。
【請求項９】
前記姿勢推定値を反復的に計算するために速度スクリューを計算することをさらに含む、請求項８に記載の物体姿勢推定方法。
【請求項１０】
レンダリングアプリケーションプログラミングインタフェース（ａｐｐｌｉｃａｔｉｏｎ ｐｒｏｇｒａｍｍｉｎｇ ｉｎｔｅｒｆａｃｅ、ＡＰＩ）を用いて前記物体のモデル輪郭曲線を仮想画像に投影することをさらに含む、請求項７に記載の物体姿勢推定方法。
【請求項１１】
入力画像から物体の姿勢を推定して記憶する物体姿勢推定装置であって、
プロセッサーであって、
物体を包含する入力画像を受信すること、
前記入力画像の２値マスクを作成すること、
前記入力画像の前記２値マスクからシングレットのセットを抽出することであって、各シングレットは、前記入力画像内の前記物体の内側および外側輪郭内にある点を表す、抽出すること、
シングレットの前記セットを連結して、デュプレックス行列として表されるメッシュにすること、
候補姿勢のセットを作るべく２つのデュプレックス行列を比較すること、ならびに
物体姿勢推定値を作ること、
を行うプロセッサーと、
前記物体姿勢推定値を記憶するメモリーと、
を含む、物体姿勢推定装置。
【請求項１２】
前記プロセッサーは前記物体の複数の画像を受信し、各画像は、前記複数の画像の互いにおける視像とは異なる、前記物体の視像を包含する、請求項１１に記載の物体姿勢推定装置。
【請求項１３】
前記物体のためのＣＡＤモデルを記憶するストレージをさらに含み、前記プロセッサーは、前記物体のための前記ＣＡＤモデルを用いて前記物体の前記複数の画像の各々における前記視像を生成する、請求項１２に記載の物体姿勢推定装置。
【請求項１４】
前記物体の前記複数の画像の各々における前記視像を生成するカメラを備えたロボットをさらに含む、請求項１２に記載の物体姿勢推定装置。
【請求項１５】
物体の推定姿勢を精緻化する物体姿勢推定精緻化方法であって、
推定姿勢をとる物体の画像、前記物体のモデル、および前記推定姿勢をとる前記物体の前記画像を撮るために用いられるカメラのパラメーターを入力することと、
２値マスク画像および画像深さ情報を得るべく、前記カメラの前記パラメーターおよび初期姿勢パラメーターを用いて前記物体の前記モデルを前記物体の仮想画像に投影することと、
前記２値マスク画像および画像深さ情報を用いて前記初期姿勢パラメーターを新しい姿勢パラメーターに更新し、エネルギー関数を最小化するべくまたは反復の最大数に達するまで前記新しい姿勢パラメーターを反復的に更新することと、
を含む、物体姿勢推定精緻化方法。
【請求項１６】
コスト関数を用いて前記物体の内部および外部の平均値を計算することと、
前記２値マスク画像から前記物体の輪郭Ｃを計算し、前記画像深さ情報を用いて３Ｄ輪郭点を計算することと、
をさらに含む、請求項１５に記載の物体推定姿勢精緻化方法。
【請求項１７】
前記輪郭点についての、ｘおよびｙ方向における勾配∇Ｔ（ｘ，ｙ）を計算することと、
画像ヤコビ行列を計算することと、
ガウス・ニュートン法を用いて勾配流および速度スクリューを計算することと、
をさらに含む、請求項１６に記載の物体推定姿勢精緻化方法。
【請求項１８】
前記速度スクリューおよび所与のステップワイズを用いて相対変位を計算すること
をさらに含む、請求項１７に記載の物体推定姿勢精緻化方法。
【請求項１９】
前記推定姿勢をとる前記物体の前記画像は、
前記物体を包含する画像を入力することと、
前記入力画像の２値マスクを作成することと、
前記入力画像の前記２値マスクからシングレットのセットを抽出することであって、各シングレットは、前記入力画像内の前記物体の内側および外側輪郭内にある点を表す、抽出することと、
シングレットの前記セットを連結して、デュプレックス行列として表されるメッシュにすることと、
候補姿勢のセットを作るべく２つのデュプレックス行列を比較することと、
物体姿勢推定値を作ることと、
によって形成される、請求項１５に記載の物体推定姿勢精緻化方法。
【請求項２０】
１つ以上の有形の非一時的コンピューター可読媒体であって、プロセッサーによって実行されると請求項１に記載の物体姿勢推定方法に従い入力画像から物体の姿勢を推定するコンピューター可読命令をその上に有する、コンピューター可読媒体。
【図１】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【公開番号】特開２０１３−５０９４７（Ｐ２０１３−５０９４７Ａ）
【公開日】平成２５年３月１４日（２０１３．３．１４）
【国際特許分類】
【出願番号】特願２０１２−１６２３７８（Ｐ２０１２−１６２３７８）
【出願日】平成２４年７月２３日（２０１２．７．２３）
【出願人】（０００００２３６９）セイコーエプソン株式会社 (51,324)
【Ｆターム（参考）】
【公開日】平成２５年３月１４日（２０１３．３．１４）
【国際特許分類】
【出願日】平成２４年７月２３日（２０１２．７．２３）
【出願人】（０００００２３６９）セイコーエプソン株式会社 (51,324)
【Ｆターム（参考）】
[ Back to top ]