(57)【要約】      （修正有）【課題】シーンのレンジ画像に対する３Ｄモデルの形状マッチングに基づく、手動での初期化を用いない自動姿勢推定の方法及びシステムを提供する。【解決手段】入力物体を含むシーンに関して取得される入力レンジ画像を参照物体の一組の参照レンジ画像の各々と比較することによって物体の姿勢を求め、各参照レンジ画像が関連する異なる姿勢を有し、参照物体は入力物体に類似するようにする。次に、入力レンジ画像に最も良く一致する参照レンジ画像に関連する姿勢が入力物体の姿勢として選択される。【選択図】図１
2008269572.tif 000002
【特許請求の範囲】
【請求項１】
レンジ画像から物体の姿勢を求める方法であって、
入力物体を含むシーンに関して取得される入力レンジ画像を参照物体の複数の参照レンジ画像の各々と比較するステップであって、各参照レンジ画像が関連する異なる姿勢を有し、前記参照物体は前記入力物体に類似するものと、
前記入力レンジ画像に最も良く一致する前記参照レンジ画像の関連する前記姿勢を前記シーン中の前記入力物体の前記姿勢として選択するステップと、
を含むレンジ画像から物体の姿勢を求める方法。
【請求項２】
参照物体をスキャンして、該参照物体の３Ｄモデルを構築するステップと、
前記３Ｄモデルを複数の異なる姿勢に関してレンダリングして、一組の参照レンジ画像を作成するステップと、
をさらに含む請求項１に記載の方法。
【請求項３】
シーンをスキャンして、レンジ値を有する入力物体のスキャンを取得するステップと、
前記スキャンを平滑化して、平滑化スキャンを作成するステップと、
前記平滑化スキャン中のエッジを検出して、距離場入力画像を作成するステップと、
前記距離場入力画像を前記スキャンの前記レンジ値と結合して入力レンジ画像を作成するステップと、
をさらに含む請求項１に記載の方法。
【請求項４】
最も良く一致する参照レンジ画像が滑降シンプレックス法を用いて選択される請求項１に記載の方法。
【請求項５】
参照レンジ画像Ｒと入力レンジ画像Ｉとの間の比較に、誤差関数：
【数１】
2008269572.tif 000015
但し、カバー誤差はεcover(ｕ，ｖ，ｘ，ｙ)、レンジ誤差はεrange(ｕ，ｖ，ｘ，ｙ，ｚ)、(ｕ，ｖ)は入力レンジ画像の画素の座標、(ｘ，ｙ，ｚ)は一組の参照レンジ画像の画素の座標、λは重み、Ｎcover及びＮrangeは正規化係数、
を用いる請求項１に記載の方法。
【請求項６】
ユークリッド距離変換(ＥＤＴ)のための入力レンジ画像の画素(ｕ，ｖ)と参照レンジ画像の画素(ｘ，ｙ，ｚ)とのカバー誤差が、
【数２】
2008269572.tif 000016
である請求項５に記載の方法。
【請求項７】
カバー誤差は、入力レンジ画像中の入力物体と参照画像中の参照物体の輪郭が一致した場合に最小となる請求項５に記載の方法。
【請求項８】
カバー誤差の正規化係数が
【数３】
2008269572.tif 000017
である請求項５に記載の方法。
【請求項９】
レンジ誤差が
【数４】
2008269572.tif 000018
である請求項５に記載の方法。
【請求項１０】
レンジ誤差は、参照レンジ画像Ｒ及び入力レンジ画像Ｉ中の重なる全ての画素の値を比較したものである請求項９に記載の方法。
【請求項１１】
レンジ誤差の正規化係数が
【数５】
2008269572.tif 000019
である請求項５に記載の方法。
【請求項１２】
最良の一致は誤差関数
【数６】
2008269572.tif 000020
但し、Ｒは回転角(θ，φ，σ)でレンダリングされる前記３Ｄモデルの前記参照レンジ画像、
を最小化し、Step1は平行移動値(ｘ，ｙ，ｚ)に対して滑降シンプレックス法を用いて各参照レンジ画像と入力レンジ画像との間の誤差を求め、Step2は大域誤差の最も低い参照レンジ画像Ｒの関連する姿勢を選択する請求項５に記載の方法。
【請求項１３】
誤差関数のパラメータは、参照物体及び入力物体の重心にそれぞれ対応する参照レンジ画像Ｒ及び入力レンジ画像Ｉ中の画素を見付けることによって最小化される請求項１２に記載の方法。
【請求項１４】
シーンは複数の物体を含み、
シーン中の最も近い物体を入力物体として選択するステップをさらに含む請求項１に記載の方法。
【請求項１５】
ユークリッド距離変換が各入力レンジ画像に適用される請求項１に記載の方法。
【請求項１６】
比較するステップはグラフィック処理装置において行われる請求項１に記載の方法。
【請求項１７】
複数の参照レンジ画像がグラフィック処理装置の複数のシェーダプロセッサにおいて並列で入力レンジ画像と比較される請求項１に記載の方法。
【請求項１８】
レンジ画像から物体の姿勢を求めるシステムであって、
入力物体を含むシーンの入力レンジ画像を取得する手段と、
前記取得する手段に接続され、前記入力レンジ画像を参照物体の複数の参照レンジ画像の各々と比較する手段であって、各参照レンジ画像が関連する異なる姿勢を有し、前記参照物体は前記入力物体に類似し、
前記入力レンジ画像に最も良く一致する前記参照レンジ画像の関連する姿勢をシーン中の前記入力物体の姿勢として選択する手段と、
を備えるレンジ画像から物体の姿勢を求めるシステム。
【請求項１９】
入力レンジ画像及び複数の参照レンジ画像に対して並列動作するように構成されるグラフィック処理装置の複数のシェーダプロセッサをさらに備える請求項１８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはコンピュータビジョンに関し、特に物体に関して取得される画像から物体の姿勢を求めることに関する。
【背景技術】
【０００２】
コンピュータビジョン用途の共通のタスクは、シーンに関して取得される画像から物体の姿勢を推定することである。本明細書中において、姿勢は物体の６ＤＯＦの位置及び向きとして定義される。クラッタ(例えば、望ましくない物体及びノイズ、並びに例えば複数の重なった物体による遮蔽)を含むシーン中の姿勢の推定は、極めて困難であり得る。さらに、２Ｄの画像及びビデオにおける姿勢推定は、照明、影、及び特徴の欠如(例えばテクスチャのない物体)の影響を受けやすい。
【０００３】
各画素が物体までの距離の推定値を含むレンジ画像からの姿勢の推定には、これらの制限がない。レンジ画像は、レーザレンジスキャナ等のアクティブライトシステム、又はアクティブライトステレオ法により取得することができる。レンジ画像はレンジマップと呼ばれることが多い。以下、これら２つの用語は同義である。
【０００４】
物体の３Ｄモデルが利用可能である場合、物体の３Ｄモデルをシーンの画像又はレンジ画像とマッチングするモデルベースの技法を用いることができる。モデルベースの姿勢推定は、物体認識、物体追跡、ロボットナビゲーション、及び動き検出等の多くの用途で用いられている。
【０００５】
姿勢推定における主な課題は、部分遮蔽、雑然としたシーン、及び大きな姿勢変化に対して不変であることである。２Ｄの画像及びビデオのための方法は一般に、外観に依存すると共に、照明、影、及びスケールの影響を受けやすいため、これらの課題を克服しない。最も成功を収めた試みとして、全体的な外観に基づく方法、及び局所的な２Ｄ特徴に基づく方法がある。残念ながら、これらの方法は通常、物体構造の局所的な変化を明示的にモデル化しないため、多数の訓練例を必要とする。
【０００６】
３Ｄスキャナのコストの低下のために、３Ｄモデルを用いるモデルベースの面マッチング技法が一般的になった。一方法は、視点の一貫性制約を用いて、視点独立画像特徴群と物体モデルとの間の対応関係を確立する(D. Lowe著「視点の一貫性制約(The viewpoint consistency constraint)」(International Journal of Computer Vision, volume 1, pages 57-72, 1987))。幾何学形状のみに基づいて３Ｄモデルを位置合わせする最も一般的な方法は、幾何学的記述子を用いることにより最近改良された逐次最近点(ＩＣＰ)法である(N. Gelfand、N. Mitra、L. Guibas、及びH. Pottmann著「ロバストな大域的整合(Robust global registration)」(Proceeding Eurographics Symposium on Geometry Processing, 2005))。しかし、これらの方法は、初期の姿勢推定値が必要な細かい整合の問題にしか対処しない。
【０００７】
幾何学的ハッシングは、マッチング時間がビュー数に影響を受けないため、多視点対応及び物体姿勢を確立する効率的な方法である。しかし、ハッシュテーブルの構築には時間がかかり、マッチングプロセスは画像解像度及び表面サンプリングの影響を受けやすい。
【０００８】
別の方法は、主曲率を計算することによって、曲率特徴を用いて３Ｄ特徴すなわち形状記述子をレンジ画像にマッチングする(Dorai他著「Ｃｏｓｍｏｓ−３Ｄ自由形物体の表現法(Cosmos - a representation scheme for 3d free-form objects)」(PAMI, 19(10):1115-1130, 1997))。この方法は、表面が平滑且つ２階微分可能であり、よってノイズに敏感である必要がある。さらに、遮蔽された物体は処理することができない。
【０００９】
別の方法は、「スピンイメージ」表面シグネチャを用いて、表面をヒストグラムにイメージングする(A. Johnson及びM. Hebert著「雑然とした３Ｄシーンにおける効率的な物体認識のためのスピンイメージの使用(Using spin images for efficient object recognition in cluttered 3d scenes)」(PAMI, 21(5):433-449, 1999))。この方法は、雑然としたシーン及び遮蔽された物体に良好な結果をもたらす。しかし、Johnson他の方法は時間がかかり、画像解像度に影響を受けやすく、曖昧な一致を生じる場合がある。
【００１０】
別の方法は、複数の不規則なレンジ画像からテンソルと呼ばれる多次元テーブル表現を構築し、ハッシュテーブルベースの投票法を用いてテンソルをシーン中の物体にマッチングする。この方法は、物体認識及び画像の分割に用いられている(A. Mian、M. Bennamoun、及びR. Owens著「雑然としたシーンにおける３次元モデルベースの物体の認識及び分割(Three-dimensional model-based object recognition and segmentation in cluttered scenes)」(PAMI, 28(12):1584-1601, 2006))。しかし、この方法は、精密な幾何形状を必要とし、数分のランタイムがあるため、リアルタイム用途には不適である。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
物体の姿勢(位置及び向き)の推定は、多くのコンピュータビジョン用途における共通のタスクである。多くの方法が知られているが、ほとんどの方法は、手動での初期化を必要とし、照明の変化、外観の変化、及び部分遮蔽に対するロバスト性に欠ける。
【課題を解決するための手段】
【００１２】
本発明の実施の形態は、シーンのレンジ画像に対する３Ｄモデルの形状マッチングに基づく、手動での初期化を用いない自動姿勢推定の方法及びシステムを提供する。本方法は誤差関数を含み、入力レンジ画像を様々な姿勢の物体の３Ｄモデルの所定の参照レンジ画像と比較する。本方法は、グラフィックスハードウェアのデータ並列処理機能を用いて、多くのレンジ画像の誤差関数を並列で評価及び最小化する。
【発明の効果】
【００１３】
本発明の方法は、ＧＰＵの並列性を利用したレンジ画像から物体の姿勢を求める。本発明では、複雑なシーン中の物体を見付け、初期推定値を用いずに物体の姿勢を正確に推定することができる。本発明の方法は、全ての参照レンジ画像の誤差を計算してから姿勢判定に最良のものを選択するため、極小値に影響されない。
【発明を実施するための最良の形態】
【００１４】
方法及びシステムの概要
図１は、本発明の一実施の形態による、対象の関心のある入力物体１１０の姿勢をレンジ画像１４１から求める方法及びシステム１００を示す。本方法は完全にグラフィック処理装置(ＧＰＵ)１０４上で動作する。ＧＰＵでの大量データ並列処理は、本方法を、より複雑なＣＰＵベースの方法よりも遥かに単純に、より効率的にする。本方法は全自動であり、初期の姿勢推定値を一切必要としない。数千の参照画像を比較しても、姿勢の判定にかかる時間は約１秒である。したがって、本方法はリアルタイム用途に適している。
【００１５】
姿勢は、他の用途、例えば、物体を機械操作するロボット用途に用いることができる。
【００１６】
前処理
前処理中に、対象の関心のある参照物体１０１をスキャンして(１１０ａ)、参照物体の詳細な３Ｄモデル１１１を構築する(１１５ａ)。参照物体１０１は入力物体１１０に類似している。モデル１１１は他の手段、例えばＣＡＤシステムでも構築することができる。モデルは、頂点のポリゴンメッシュの形式とすることができる。モデル１１１をいくつかの異なる姿勢でレンダリングし(１２０)、一組の参照レンジ画像１２１を作成する。実際には、数千の参照画像を用いることができる。各画像は６４×６４画素である。一組の参照レンジ画像１２１はＧＰＵ１０４のメモリ１０６に記憶することができる。これらのステップを１度だけ行う。
【００１７】
エッジ検出及びユークリッド距離変換(ＥＤＴ)も参照レンジ画像１２１に適用することができる。ＥＤＴは以下でより詳細に説明する。この結果、本発明のレンジ画像は符号付距離場として表現される。
【００１８】
オンライン処理
オンラインでの姿勢推定中に、入力物体１１０及びおそらくは他の既知又は未知の物体を含むシーン１０２をスキャンして(１３０)、３Ｄスキャン１３１を生成する。本発明では、アクティブライト法、例えばレーザレンジスキャナ１１５を用いる。次に、メディアンフィルタを３Ｄスキャンに適用すると共に、エッジ検出を平滑化画像に適用し、距離場を求めて、入力レンジ画像１４１を作成する。なお、スキャンデータは略平滑であるため、詳細スキャンに対して平滑化を行う必要はない。
【００１９】
入力レンジ画像１４１を一組の参照レンジ画像１２１と比較して(１４０)、シーン１０２中の物体１１０の姿勢１０３を求める。一実施の形態では、ＧＰＵ１０４での滑降シンプレックス法の並列実施を用いる。
【００２０】
タスクは、対毎の比較の誤差最小化を用いて、参照レンジ画像１２１と入力レンジ画像１４１との間の最良一致を見付けることである。最も良く一致する参照レンジ画像及びこの参照レンジ画像を入力レンジ画像１４１に対して平行移動したものにより、入力物体１１０の姿勢
【００２１】
【数１】
2008269572.tif 000003
【００２２】
１０３の本発明の６ＤＯＦ推定が得られる。
【００２３】
レンジ値及びユークリッド距離画像を用いる新規の誤差関数を説明すると、グレイスケール値又はカラー値が利用可能であれば、輝度勾配又は色勾配も誤差関数において考慮することができる。誤差関数は画素毎に評価することができるため、ＧＰＵ１０４のシェーダプロセッサ１０５における効率的な処理に適している。
【００２４】
従来、シェーダは多くの場合、コンピュータグラフィックス用途及びコンピュータゲームにおいて、ポリゴンモデル、例えば頂点の三角形メッシュ、テクスチャ、及び照明構成からグラフィック画像を作成するために用いられてきた。フラグメントシェーダは通常、ユーザプログラマブルなＧＰＵコードを複数の画素に対して並列実行する。
【００２５】
対照的に、本発明のパラレルシェーダ１０５は、レンジ画像１４１から物体の姿勢を求める。姿勢の誤差を効率的に最小化するため、本発明は、完全にＧＰＵ１０４上で実行される新規のデータ並列版の滑降シンプレックス法を提供する。従来のシンプレックス法は、J. A. Nelder及びR. Mead著「関数の最小化のためのシンプレックス法(A simplex procedure for function minimization)」(The Computer Journal, 7(4):308-313, 1965)(参照により本明細書中に援用される)に記載されている。本発明では、この手順を適合させて、ＧＰＵのシェーダプロセッサにおいて複数の画素に対して並列実行する。
【００２６】
本発明の実施の形態は、入力レンジ画像に対する２つの参照レンジ画像の位置合わせをＧＰＵで比較するための単純な画素メトリックと、画像の符号付ユークリッド距離変換をＧＰＵで求める方法と、ＧＰＵでの滑降シンプレックス法のデータ並列実施と、初期推定値を必要とせず、完全にＧＰＵ１０４上で実行されるレンジ画像のモデルベースの姿勢推定の効率的な実施とを提供する。
【００２７】
レンジ画像処理
以下に説明するレンジ画像処理ステップは、参照レンジ画像の作成中に行うこともできる。シーンの入力３Ｄスキャン１３１及び参照物体１０１の３Ｄモデル１１１から始める。レンジスキャナ１１５を用いる。シーン１０２のスキャンに用いられるスキャナは、詳細スキャンの取得に用いられるスキャナよりも分解能が遥かに低くてもよいことに留意すべきである。
【００２８】
両スキャンを、入力レンジ画像１４１及び参照レンジ画像１２１内にそれぞれ直交投影する。これらの直交投影の視点に同じものを選択し、視錐台及び画像解像度を同一にする。
【００２９】
スキャナの物理単位(例えばｍｍ)間のスケールファクタは３Ｄモデル１１１の単位距離まで分かっている。この情報は、スキャナ製造業者から容易に入手可能である。その結果、参照物体１０１のサイズは入力レンジ画像１４１の物体１１０のサイズと同じになる。この方法はスケール差を気にしない。
【００３０】
図２は３Ｄスキャン１３１を示す。スキャンは、フラグメントシェーダとして実装される３×３マスクを有するメディアンフィルタを適用することによって平滑化される。フラグメントシェーダは、複数の画素に対してＧＰＵ１０４上で並列実行されるユーザプログラマブルなＧＰＵコードである。図３は平滑化画像を示す。
【００３１】
２回目のＧＰＵレンダリングパスでは、ヒューリスティックを用いて、平滑化画像の隣接画素のレンジ値を比較することにより物体エッジを検出する。レンジ差が画像幅の４％を超える場合、画素はエッジとしてマーキングされる。考え得るエッジとして検出された画素は、連続処理のためにバイナリビットによりマーキングされる。エッジ画像を図４に示す。
【００３２】
ユークリッド距離変換(ＥＤＴ)
次に、符号付ユークリッド距離変換(ＥＤＴ)１５０をエッジ画像に適用する。この変換は各画素に、その画素から最も近いエッジ画素までの符号付距離を割り当てる。本発明の一実施の形態において、この距離はユークリッド距離である。ＥＤＴは、探索を参照物体及び入力物体の輪郭(エッジ)に制約することにより、最良一致の参照画像を探索する助けとなる。
【００３３】
これにより、図５に示すような距離場画像が作成される。距離場画像において、物体内部の画素は正の距離を有し、物体外の画素は負の距離を有し、エッジ画素はゼロの距離を有する。上述のように、参照レンジ画像１２１は距離場の形式でもある。すなわち、距離場は、画像の平面(ｘ，ｙ)の範囲(ｚ)を示す。
【００３４】
２つのＲＧＢＡのカラーテクスチャを用いてレンダリング元及びレンダリング先としての役割をそれぞれ連続的に切り替える従来の「ピンポン」レンダリングを用いてＥＤＴを行う。本発明のＧＰＵ実装では、各カラーチャネルに３２ビットの浮動小数点形式を用いる。最初の２つのチャネルの値は、それまでに見付かった最も近いエッジ画素のユークリッド座標を表し、３番目のチャネルはその符号付距離を記憶し、４番目のチャネルはエッジ画素が既に見付かったかどうかを示す。
【００３５】
次に、距離場をスキャンのレンジ値と結合して、入力レンジ画像１４１を作成する。
【００３６】
図６は、本発明のＥＤＴ法の疑似コードを示す。パラメータｍは繰り返し数を決める。距離値は、背景(ｂ)画素、すなわち、レンジ値＝０である画素に関して−(ｍ＋１)に初期化され、前景(ｆ)画素、すなわち、レンジ値ｎｏ＝０)である画素に関してｍ＋１に初期化され、全てのエッジ(ｅ)画素に関して０に初期化される。最初の２つのカラーチャネルは、画素(ｐ)の(ｘ，ｙ)座標に初期化される。繰り返し毎に、各画素の距離値をその８連結の近傍画素の値と比較する。
【００３７】
近傍画素ｎに記憶されている現画素ｐからエッジ画素ｅまでの距離が画素ｐに保存されている値よりも小さい場合、画素ｐの距離値及び座標を更新する。この情報をステップ毎に画像全体に繰り返し伝搬する。図７は初期化ステップを示し、図８〜図１０は次の３回の繰り返しを示す。繰り返し数ｍは任意の画素から最も近いエッジまでの最大距離に対応する。完全な収束のためには、ｍに画像幅の半分を選択する。しかし、処理時間を低減するために、各画素から物体エッジまでの距離は通常遥かに小さいという事実を利用する。本発明の方法は、正確な距離場を必要とせず、近似で十分である。経験的に、本発明で使用する６４×６４の画像にはｍ＝７で十分であることが分かる。
【００３８】
誤差関数
参照レンジ画像Ｒ１２１のうちの１つと入力レンジ画像Ｉ１４１とを比較するために使用する誤差関数は
【００３９】
【数２】
2008269572.tif 000004
【００４０】
であり、ここで、カバー誤差はεcover(ｕ，ｖ，ｘ，ｙ)であり、レンジ誤差はrange(ｕ，ｖ，ｘ，ｙ，ｚ)である(詳細は以下を参照)。これらの誤差項は、入力レンジ画像の座標(ｕ，ｖ)にある画素毎に評価される(以下を参照)。参照レンジ画像Ｒ１２１の画素の平行移動値(ｘ，ｙ，ｚ)は、入力レンジ画像Ｉ１４１に対するその位置を決める。関数は、重みλを用い、全ての画像画素(ｕ，ｖ)にわたって総和される(例えばλ＝１０)。標準化係数Ｎcover及びＮrangeは、誤差を物体及び画像サイズから独立させる。誤差は、画像Ｒが入力画像Ｉ中のおそらく部分遮蔽された物体と位置合わせされる場合に最小となる。
【００４１】
カバー誤差
入力レンジ画像ＥＤＴＩ１４１の画素(ｕ，ｖ)と、参照レンジ画像ＥＤＴＲ１２１の画素とのカバー誤差を(ｘ，ｙ)だけ平行移動すると次のようになる。
【００４２】
【数３】
2008269572.tif 000005
【００４３】
このカバー誤差は、画像Ｉ及び画像Ｒ中の物体の輪郭が一致する場合に最小となる。なお、正のレンジ値を有する参照レンジ画像Ｒ中の非背景画素のみを検討する。
【００４４】
カバー誤差正規化係数は次式のように書き表される。
【００４５】
【数４】
2008269572.tif 000006
【００４６】
レンジ誤差項
レンジ誤差は、レンジ画像ＥＤＴＩ及びＥＤＴＲ中の重なる全ての画素のレンジ値を比較するため、次式のようになる。
【００４７】
【数５】
2008269572.tif 000007
【００４８】
なお、参照レンジ画像ＥＤＴＲは(ｘ，ｙ)だけ平行移動され、ｚが参照レンジ画像Ｒの全てのレンジ値に加算される。
【００４９】
レンジ誤差の正規化係数は次式のように表される。
【００５０】
【数６】
2008269572.tif 000008
【００５１】
ＧＰＵでの実装
式(１)の誤算関数は完全にＧＰＵ１０４上で計算される。フラグメントシェーダ１０５を用いると、画素毎の比較は特に低解像度画像の場合に非常に高速である。第１のステップにおいて、入力レンジ画像Ｉ及び参照レンジ画像ＲをＧＰＵのメモリ１０６に記憶する。フラグメントシェーダ１０５は画素毎に誤差項εcover(ｕ，ｖ，ｘ，ｙ)及びεrange(ｕ，ｖ，ｘ，ｙ，ｚ)を求める。
【００５２】
式(３)及び式(５)の正規化係数にそれぞれ用いられる２つのバイナリビットｎcover及びｎrangeは、誤差値が計算されたことを示す。全ての値をＧＰＵのテクスチャマップＳの３２ビットカラーチャネルに記憶する。
【００５３】
第２のステップにおいて、誤差値をテクスチャマップＳの全ての画素にわたって総和し、最終誤差を計算する。この総計は、最適化の繰り返し毎に行われる。本発明では、この手順をＧＰＵ上で、テクスチャマップＳと一時テクスチャＴとの間のピンポンレンダリングを用いて実施した。
【００５４】
ステップサイズｓ＝１から始めて、テクスチャＳをテクスチャＴにレンダリングすることによって、画素(ｕ，ｖ)の１つのカラーチャネルは画素(ｕ，ｖ)、(ｕ＋ｓ，ｖ)、(ｕ＋ｓ，ｖ＋ｓ)、(ｕ，ｖ＋ｓ)の値の総和を記憶する。次に、図１１の(ａ)〜(ｃ)に示すように、ｓを繰り返し毎に２倍し、ＳとＴとを入れ替える。繰り返しｋ毎に、現画素(点描)２０４の情報を、距離ｓ＝２ｋにある左上(縦線)２０１、右上(横線)２０２、及び右(斜め線)２０３の近傍画素から収集する。誤差関数の最終結果をｓ＝ｌｏｇ(ｌ)ステップ２１０後に画素(０，０)２０４に記憶する。ここで、ｌは画素数で表される画像幅である。この手順は、本発明の正方形画像に関して非常に効率的である。
【００５５】
並列最適化フレームワーク
誤差最適化の目標は、入力レンジ画像と参照レンジ画像との間の誤差を大域的に最小化する姿勢パラメータ
【００５６】
【数７】
2008269572.tif 000009
【００５７】
を求めることである。したがって、以下の６ＤＯＦ最適化問題を解いている。
【００５８】
【数８】
2008269572.tif 000010
【００５９】
ここで、Ｒは、回転角(θ，φ，σ)でレンダリングされる３Ｄモデルの参照レンジ画像である。ステップ１(step1)は、平行移動値(ｘ，ｙ，ｚ)に対して滑降シンプレックス法を用いて各参照レンジ画像と入力レンジ画像との間の誤差を求める(Nelder他を参照)。ステップ２(step2)は、大域誤差の最も低い参照レンジ画像Ｒの関連する姿勢を選択する。その結果、シーン１０２中の入力物体１１０の推定姿勢
【００６０】
【数９】
2008269572.tif 000011
【００６１】
１０３が得られる。
【００６２】
図１２に示すように、前処理中に、１つの大きなテクスチャである参照テクスチャ行列１４００を求めて、全ての参照レンジ画像を記憶する。参照レンジ画像の数は、本発明の姿勢推定方法の精度及び速度に影響を与える。記憶する参照レンジ画像の数が多くなるほど、本発明の角度姿勢推定値は正確になり、方法は遅くなる。記憶できる参照画像の数は、テクスチャメモリのサイズにも依存する。
【００６３】
この問題に対処するために、貪欲なシンプレックス法を用いる。正規直交投影を用いて物体をレンダリングし、ｚバッファを参照レンジ画像として記憶する。次に、物体を少しずつ、例えば５度ずつ、(θ，φ，σ)だけ回転させる。新たな参照レンジ画像毎に、全ての以前に記憶された参照レンジ画像に対して、式(１)に従って誤差を計算する。誤差がユーザ定義の閾値よりも大きい場合、このレンジ画像を参照テクスチャ行列に追加する。参照レンジ画像を置き換えるのではなく追加するだけなので、シンプレックス法を閾値を徐々に大きくしながら、全てのレンジ画像を参照テクスチャ行列に当てはめられるまで数回実行するだけでよい。動的計画法を用いることにより性能を高めることもできる。
【００６４】
初期パラメータ
滑降シンプレックス法を収束させるための滑降ステップの繰り返し数は、適切な初期パラメータを選択することによって劇的に低減することができる。シンプレックス法は結果的に極小値となることがあるため、図１３及び図１４に示すように、物体の重心に対応する画像Ｒ及び画像Ｉ中の画素１５０１及び画素１６０１をそれぞれ見付けることによって初期パラメータ(ｘ０，ｙ０，ｚ０)を推定する。
【００６５】
入力画像Ｉが複数の物体を含む場合、スキャナに最も近い物体、すなわち、ｚ値の最も大きい画像を選択する。以下のヒューリスティック法を用いる。レンジ画像毎に、重心(ｕ，ｖ)を最初の画素に初期化し、全ての画素(ｒ，ｓ)にわたって繰り返す。次式が成り立つ場合、(ｕ，ｖ)を新たな画素位置(ｒ，ｓ)に更新する。
【００６６】
【数１０】
2008269572.tif 000012
【００６７】
ＥＤＴ項は結果を通常、物体の中心にし、ｚ項は結果をスキャナの最も近くにする。すると、初期平行移動パラメータは次のようになる。
【００６８】
【数１１】
2008269572.tif 000013
【００６９】
レンジ画像を位置合わせすることによってパラメータの初期推定値を求める場合、滑降シンプレックス法は約３０回〜４０回の繰り返しで収束する。重心を見付けた場合、繰り返し数は２分の１に減る。
【００７０】
ＧＰＵでのデータ並列滑降シンプレックス
滑降シンプレックス法をＧＰＵ１０４に並列化するために、付加的なスキャンライン１４０１を参照テクスチャ行列１４００の各参照レンジ画像に追加する(図１２を参照)。これらのスキャンラインを用いて、滑降シンプレックスアルゴリズムのパラメータ及び誤差値を異なるカラーチャネルに記憶する。
【００７１】
シンプレックスの頂点を(ｘ０，ｙ０，ｚ０)、(ｘ０＋ｄ，ｙ０，ｚ０)、(ｘ０，ｙ０＋ｄ，ｚ０)及び(ｘ０，ｙ０，ｚ０＋ｄ)に初期化する。ここで、ｘ０、ｙ０及びｚ０は上述した初期パラメータである。本発明では、最適なステップサイズｄの値は画素数で表される画像幅の５％であると経験的に判断する。
【００７２】
最適化法は、６４×６４の画像上の９６個のシェーダプロセッサにおいて並列動作する３つのフラグメントシェーダプログラムを用いて実施される。Nelder他に記載されるように、第１のシェーダは実際の滑降シンプレックスアルゴリズムを実施する。第２のシェーダは式(３)及び式(４)の誤差項を計算し、第３のシェーダは最終的な誤差値を計算する。このループを滑降シンプレックスアルゴリズムの新たな繰り返し毎に実行する。最後に、全ての参照レンジ画像の一番上のスキャンラインをＣＰＵにより読み出す。誤差の最も少ない参照レンジ画像の姿勢パラメータ
【００７３】
【数１２】
2008269572.tif 000014
【００７４】
が物体の姿勢１０３となる。
【００７５】
本発明を好ましい実施の形態の例として説明してきたが、本発明の精神及び範囲内で様々な他の適応形態及び修正形態を実施できることが理解される。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲に入るような変形形態及び修正形態を全て網羅することである。
【図面の簡単な説明】
【００７６】
【図１】本発明の一実施の形態による、レンジ画像から物体の姿勢を求める方法のフロー図である。
【図２】本発明の一実施の形態による３Ｄスキャン画像である。
【図３】本発明の一実施の形態による平滑化したスキャン画像である。
【図４】本発明の一実施の形態によるエッジ画像である。
【図５】本発明の一実施の形態による距離場画像である。
【図６】本発明の一実施の形態による拡張距離変換の疑似コードのブロック図である。
【図７】本発明の一実施の形態による１回目の繰り返しの距離場のブロック図である。
【図８】本発明の一実施の形態による２回目の繰り返しの距離場のブロック図である。
【図９】本発明の一実施の形態による３回目の繰り返しの距離場のブロック図である。
【図１０】本発明の一実施の形態による４回目の繰り返しの距離場のブロック図である。
【図１１】本発明の一実施の形態による誤差値を求める繰り返し毎のブロック図である。
【図１２】本発明の一実施の形態による、参照レンジ画像を記憶する行列のブロック図である。
【図１３】本発明の一実施の形態による参照レンジ画像である。
【図１４】本発明の一実施の形態による入力レンジ画像である。
【図１】
2008269572.tif 000021
【図２】
2008269572.tif 000022
【図３】
2008269572.tif 000023
【図４】
2008269572.tif 000024
【図５】
2008269572.tif 000025
【図６】
2008269572.tif 000026
【図７】
2008269572.tif 000027
【図８】
2008269572.tif 000028
【図９】
2008269572.tif 000029
【図１０】
2008269572.tif 000030
【図１１】
2008269572.tif 000031
【図１２】
2008269572.tif 000032
【図１３】
2008269572.tif 000033
【図１４】
2008269572.tif 000034
【外国語明細書】
2008269572.tif 000035
2008269572.tif 000036
2008269572.tif 000037
2008269572.tif 000038
2008269572.tif 000039
2008269572.tif 000040
2008269572.tif 000041
2008269572.tif 000042
2008269572.tif 000043
2008269572.tif 000044
2008269572.tif 000045
2008269572.tif 000046
2008269572.tif 000047
2008269572.tif 000048
2008269572.tif 000049
2008269572.tif 000050
2008269572.tif 000051
2008269572.tif 000052
2008269572.tif 000053
2008269572.tif 000054
2008269572.tif 000055
2008269572.tif 000056
2008269572.tif 000057
2008269572.tif 000058
2008269572.tif 000059
2008269572.tif 000060
2008269572.tif 000061
2008269572.tif 000062
2008269572.tif 000063
2008269572.tif 000064
2008269572.tif 000065
2008269572.tif 000066