(57)【特許請求の範囲】
【請求項１】
対象物体の３次元形状情報を示す３次元モデルを取得するモデル取得手段と、
前記３次元モデルの位置および姿勢を入力する位置姿勢入力手段と、
前記対象物体の位置および姿勢に基づいて、前記３次元モデルを構成するモデル線分を、当該３次元モデルまでの奥行き情報が各画素に保持された２次元画像上に、投影線分として投影する投影手段と、
前記２次元画像上で投影線分の周辺領域の奥行き情報を参照することにより、前記投影手段により投影された投影線分のうちから、前記対象物体の特徴を示すエッジとなる投影線分を抽出する抽出手段と、
前記３次元モデルを構成する線分から、前記抽出された投影線分に対応するモデル線分以外の線分を削除する削除手段と、
前記削除手段により前記抽出された投影線分に対応するモデル線分以外の線分が削除された後の前記３次元モデルを構成する線分データを出力する出力手段と
を備えることを特徴とする情報処理装置。
【請求項２】
前記抽出手段により抽出された投影線分の３次元位置と、前記奥行き情報が示す位置とを比較して、当該奥行き情報が示す位置よりも奥に存在する投影線分を陰線として、前記抽出手段により抽出された投影線分から除去する除去手段をさらに備えることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記削除手段は、前記投影線分のうち前記２次元画像上で重複する線分を、１つ残して削除することを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
前記削除手段は、
前記投影線分のうち、前記２次元画像上で当該投影線分の１つから所定領域の範囲に存在する投影線分を、前記２次元画像上で重複する投影線分として、１つを残して削除することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記抽出手段は、
前記削除手段により削除された後の投影線分に対して、当該投影線分を構成する点が示す位置から当該線分と直交する方向に所定画素分当該画素の奥行き情報を取得する取得手段と、
前記直交する方向に対する、前記取得手段により取得された奥行き情報の２次微分値を算出する算出手段と、
前記２次微分値の絶対値が閾値以上であるか否か判断する判断手段と、を備え、
前記判断手段により前記２次微分値の絶対値が閾値以上であると判断された場合、当該線分を、前記２次元画像上において前記対象物体の特徴を示すエッジとなる投影線分として抽出することを特徴とする請求項１乃至４の何れか１項に記載の情報処理装置。
【請求項６】
前記線分を示すデータ形式が、当該線分に対応する前記投影線分が等間隔となるように前記線分を分割した分割点の位置情報および当該線分の３次元方向により記述されることを特徴とする請求項１乃至５の何れか１項に記載の情報処理装置。
【請求項７】
前記線分を示すデータ形式が、当該線分を構成する始点および終点の各端点の位置情報により記述されることを特徴とする請求項１乃至６の何れか１項に記載の情報処理装置。
【請求項８】
物体を含む画像を取得する画像取得手段と、
前記物体の概略位置姿勢を取得する概略位置姿勢取得手段と、
請求項１乃至７のいずれか１項に記載の情報処理装置の出力手段により出力された線分データを取得する取得手段と、
前記画像から前記物体の特徴を取得する特徴取得手段と、
前記概略位置姿勢に基づいて、前記線分データと前記特徴とを対応づけることにより、前記物体の位置姿勢を導出する導出手段とを備えることを特徴とする位置姿勢推定装置。
【請求項９】
対象物体の３次元形状情報を示す３次元モデルを構成する線分から２次元画像上で前記対象物体の特徴を示すエッジとして観察される線分を抽出する情報処理方法であって、
位置姿勢入力手段が、対象物体の３次元形状情報を示す保持手段に保持された３次元モデルの位置および姿勢を入力する位置姿勢入力工程と、
投影手段が、前記対象物体の位置および姿勢に基づいて、前記３次元モデルを構成するモデル線分を、当該３次元モデルまでの奥行き情報が各画素に保持された２次元画像上に、投影線分として投影する投影工程と、
抽出手段が、前記２次元画像上で投影線分の周辺領域の奥行き情報を参照することにより、前記投影手段により投影された投影線分のうちから、前記対象物体の特徴を示すエッジとなる投影線分を抽出する抽出工程と、
削除手段が、前記３次元モデルを構成する線分から、前記抽出された投影線分に対応するモデル線分以外の線分を削除する削除工程と、
出力手段が、前記削除工程により前記抽出された投影線分に対応するモデル線分以外の線分が削除された後の前記３次元モデルを構成する線分データを出力する出力工程と
を有することを特徴とする情報処理方法。
【請求項１０】
位置姿勢推定方法であって、
画像取得手段が、物体を含む画像を取得する画像取得工程と、
概略位置姿勢取得手段が、前記物体の概略位置姿勢を取得する概略位置姿勢取得工程と、
取得手段が、請求項９に記載の情報処理方法の出力工程で出力された線分データを取得する取得工程と、
特徴取得手段が、前記画像から前記物体の特徴を取得する特徴取得工程と、
導出手段が、前記概略位置姿勢に基づいて、前記線分データと前記特徴とを対応づけることにより、前記物体の位置姿勢を導出する導出工程と
を有することを特徴とする位置姿勢推定方法。
【請求項１１】
コンピュータを、
対象物体の３次元形状情報を示す３次元モデルを取得するモデル取得手段、
前記３次元モデルの位置および姿勢を入力する位置姿勢入力手段、
前記対象物体の位置および姿勢に基づいて、前記３次元モデルを構成するモデル線分を、当該３次元モデルまでの奥行き情報が各画素に保持された２次元画像上に、投影線分として投影する投影手段、
前記２次元画像上で投影線分の周辺領域の奥行き情報を参照することにより、前記投影手段により投影された投影線分のうちから、前記対象物体の特徴を示すエッジとなる投影線分を抽出する抽出手段、
前記３次元モデルを構成する線分から、前記抽出された投影線分に対応するモデル線分以外の線分を削除する削除手段、
前記削除手段により前記抽出された投影線分に対応するモデル線分以外の線分が削除された後の前記３次元モデルを構成する線分データを出力する出力手段
として機能させるためのプログラム。
【請求項１２】
コンピュータを、
物体を含む画像を取得する画像取得手段、
前記物体の概略位置姿勢を取得する概略位置姿勢取得手段、
請求項１１に記載の出力手段により出力された線分データを取得する取得手段、
前記画像から前記物体の特徴を取得する特徴取得手段、
前記概略位置姿勢に基づいて、前記線分データと前記特徴とを対応づけることにより、前記物体の位置姿勢を導出する導出手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元形状モデルから、画像上でエッジとして観察される３次元ラインを抽出する情報処理装置、情報処理方法、およびプログラムに関する。
【背景技術】
【０００２】
近年のロボット技術の発展とともに、工業製品の組立のようなこれまで人間が行っていた複雑なタスクをロボットが代わりに行うようになりつつある。このようなロボットは、ハンドなどのエンドエフェクタによって部品を把持して組立を行う。ロボットが部品を把持するためには、把持の対象となる部品とロボット（ハンド）との間の相対的な位置及び姿勢を計測する必要がある。位置及び姿勢を計測する方法としては、カメラが撮影する２次元画像上から検出される特徴に対して物体の３次元形状モデルを当てはめる、モデルフィッティングによる計測が一般的である。非特許文献１では、２次元画像上から検出される特徴としてエッジを利用する方法が開示されている。この方法では、物体の形状は３次元ラインの集合によって表される。そして、物体の概略の位置及び姿勢は既知であるとして、画像上で検出されるエッジに３次元ラインの投影像が当てはまるように概略の位置及び姿勢を補正することにより物体の位置及び姿勢を計測する。一般的に、物体の形状を表す３次元ラインとしては、物体の輪郭（ジャンプエッジ）となる３次元ライン用いることが多い。また、物体内部においてルーフエッジとなる３次元ラインを用いることが多い。しかし、輪郭となる３次元ラインは、物体を観察する方向によって変化するため、物体を観察する方向に応じて輪郭となる３次元ラインを抽出する処理が必要になる。
【０００３】
物体の形状を表す３次元形状モデルから輪郭となる３次元ラインを抽出する方法として、３次元形状モデル中の面の法線情報を利用する方法が特許文献１に開示されている。この方法では、３次元形状モデル中の各３次元ラインについて、隣接する２つの面が視点に対して表を向いているか、裏を向いているかを算出し、表裏が異なる場合は輪郭線として判定することで３次元ラインを抽出している。
【０００４】
また、特許文献２で開示されている手法では、３次元形状モデル中の面と面との法線の内積と面間の色の内積を算出して、双方の内積が一定値以下であれば、その面と面との境界となる３次元ラインは、輪郭であると判別している。
【０００５】
また、３次元形状モデルから直接３次元ラインを抽出しない手法として、３次元形状モデルの描画画像から３次元ラインを計算する方法が非特許文献２で開示されている。この方法は、コンピュータグラフィックス（ＣＧ）により３次元形状モデルを描画し、描画の結果として得られるデプスバッファに対して、エッジ検出を行う。デプスバッファとは、視点からモデル上の各点までの奥行き値が格納された画像であり、デプスバッファからエッジを検出することで、奥行きが不連続に変化する領域を算出することが可能である。デプスバッファ上でエッジとして検出された画素の画像座標と奥行き値とから、エッジに対応する３次元ラインのパラメータを算出することで、画像上でエッジとなる３次元ラインを算出する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００２−３１９０３１号公報
【特許文献２】特開平１０−１８８０３０号公報
【特許文献３】特開平１１−２６０８１２号公報
【非特許文献】
【０００７】
【非特許文献１】T. Drummond and R. Cipolla, “Real-time visual tracking of complex structures,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.24, no.7, pp.932-946, 2002.
【非特許文献２】H. Wuest, F. Wientapper, and D. Stricker, “Adaptive Model-based Tracking Using Analysis-by-Synthesis Techniques,“ International Conference on Computer Analysis of Image and Patterns (CAIP), 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１または２で開示されているような、３次元形状モデルから直接３次元ラインを抽出する手法では、３次元形状モデル中で３次元ラインが重複して定義されておらず、形状を表す面と面の間にはクラック（隙間）がないことが前提となっている。しかし、３次元形状モデルがパラメトリック曲面により記述された設計用ＣＡＤデータを三角形メッシュ変換されたモデルである場合などには、３次元曲面またはポリゴンパッチ間の境界曲線または線分が単一のものとして定義されていない。そのため、それぞれの面に属するものとして独立に定義されている場合がある。さらに独立に定義されたライン間にクラックがある場合も多い。その結果、隣り合う面を参照することや、面と面の角度を計算することが出来ず、３次元ラインを正確に抽出すること自体が困難であり、抽出前に重複データを削除する処理が必要となるといった課題がある。
【０００９】
クラックを含む３次元形状モデルへの対応としては、３次元形状モデルのクラックを補間し、クラックのないモデルを一度生成してから３次元ライン抽出を行うという方策が考えられる。
【００１０】
特許文献３では、クラックを含むモデルを簡略化することで、クラックを補間する手法が開示されている。この方法は、メッシュを近似する領域を定め、近似範囲にある頂点をマージし、モデルを簡略化することで、クラックを除去している。しかし、元の形状が簡略化されるため、元の形状データの精度が保存されないという問題がある。また、閾値が不適切に設定された場合は、モデルの精度は著しく損なわれてしまう恐れがある。加えて、モデルのスケールや観察距離、観察方向に応じて、適切な近似範囲の閾値が変化するため、多様な利用シーンに適用することには限界がある。
【００１１】
一方、非特許文献２に示されるような、３次元形状モデルのＣＧ描画結果の画像を利用する方法は、クラックを含むモデルからであっても、正確に輪郭となる３次元ラインを抽出することが可能である。３次元形状モデル中の３次元ラインの画像上への投影像を画素単位で標本化することにより、ほとんどの場合、クラックが画素の範囲に埋もれる。そのため、クラックを含むモデルからでも問題なく輪郭となる３次元ラインを抽出することが可能である。しかし、画像から検出したエッジの２次元座標から３次元ラインのパラメータを算出しているため、描画による標本化誤差の影響によって精度が低下してしまうという問題がある。これは、描画する画像の解像度が低いときには特に顕著になる。３次元形状モデルの精度を損なわないという観点では、３次元形状モデルから直接３次元ラインの情報を抽出する方式が望ましい。
【００１２】
上記の課題に鑑み、本発明は、３次元ラインが画像上でエッジとして観察されるかどうかの判定を適切に行い、且つ３次元ラインのパラメータの精度を落とすことなく、クラックや重複を含む３次元形状モデルからでも３次元ラインを抽出することを目的とする。
【課題を解決するための手段】
【００１３】
上記の目的を達成する本発明に係る情報処理装置は、
対象物体の３次元形状情報を示す３次元モデルを取得するモデル取得手段と、
前記３次元モデルの位置および姿勢を入力する位置姿勢入力手段と、
前記対象物体の位置および姿勢に基づいて、前記３次元モデルを構成するモデル線分を、当該３次元モデルまでの奥行き情報が各画素に保持された２次元画像上に、投影線分として投影する投影手段と、
前記２次元画像上で投影線分の周辺領域の奥行き情報を参照することにより、前記投影手段により投影された投影線分のうちから、前記対象物体の特徴を示すエッジとなる投影線分を抽出する抽出手段と、
前記３次元モデルを構成する線分から、前記抽出された投影線分に対応するモデル線分以外の線分を削除する削除手段と、
前記削除手段により前記抽出された投影線分に対応するモデル線分以外の線分が削除された後の前記３次元モデルを構成する線分データを出力する出力手段と
を備えることを特徴とする。
【発明の効果】
【００１４】
本発明によれば、３次元形状モデルがクラックや重複定義を含んでいても、エッジとして観察される３次元ラインを高精度に抽出することが可能となる。また、３次元ラインの投影像を２次元画像上で標本化することにより、３次元ラインが２次元平面上で重複しないように３次元ラインを抽出することが可能になる。さらに、３次元形状モデルの投影像から、３次元ライン周辺の形状を参照することにより、輪郭またはルーフエッジとなる３次元ラインを判定することが可能になる。
【図面の簡単な説明】
【００１５】
【図１】（ａ）３次元ライン抽出装置１００のハードウェア構成を示す図、（ｂ）３次元ライン抽出装置１００の構成を示す図。
【図２】３次元形状モデル中の線分からの３次元ライン抽出の様子を示す図。
【図３】２次元画面上で重複する３次元ラインを除去する処理を示す図。
【図４】３次元ライン抽出方法の処理手順を示すフローチャート。
【図５】３次元形状モデルから２次元画面上で重複がないように３次元ラインを抽出する処理手順を示すフローチャート。
【図６】３次元ラインのエッジ判定の処理手順を示すフローチャート。
【図７】デプスバッファから距離値を参照することによる、３次元ラインのエッジ判定処理を説明する図。
【発明を実施するための形態】
【００１６】
（第１実施形態）
本実施形態では、本発明に係る情報処理装置を、実写画像に対する３次元モデルフィッティングのための３次元ライン抽出装置として適用した場合について説明する。３次元ライン抽出装置は、対象物体の３次元形状情報を示す３次元モデルを構成する線分から２次元画像上で、対象物体の特徴を示すエッジとして観察される線分を抽出する。
【００１７】
まず、図１（ａ）を参照して、３次元ライン抽出装置１００のハードウェア構成について説明する。ＣＰＵ１は装置全体の動作、具体的には後述の各処理部の動作を制御する。メモリ２は、ＣＰＵ１の動作に用いるプログラムやデータを格納する。バス３は各処理部間でのデータ転送を司る。インタフェース４はバス３と各種装置とのインタフェースである。また、外部記憶装置５は、ＣＰＵ１に読み込むためのプログラムやデータを格納する外部記憶装置である。キーボード６およびマウス７はプログラムを起動したり、プログラムの動作を指定したりするための入力装置を構成する。表示部８はプロセスの動作結果を表示する。
【００１８】
図１（ｂ）を参照して、観察対象物体の形状を表す３次元モデルデータ１０から、エッジとして観察される３次元ラインの抽出を行う３次元ライン抽出装置１００の構成について説明する。３次元ライン抽出装置１００は、３次元モデル保存部１０１と、観察方向入力部１０２と、３次元ライン抽出部１０３と、モデル描画部と１０４、サンプリング部１０５と、エッジ判定部１０６とを備える。
【００１９】
３次元ライン抽出装置１００は、３次元モデル保存部１０１に保存されている観察対象物体の形状を表す３次元モデルデータ１０から、画像上でエッジとして観察される３次元ラインを抽出する。抽出された３次元ラインは、位置姿勢推定装置１１に入力され、物体の位置姿勢推定処理に利用される。
【００２０】
次に、３次元ライン抽出装置１００を構成する各処理部について説明する。
【００２１】
３次元モデル保存部１０１は、３次元モデルデータ１０を保存する。３次元モデル保存部１０１は、３次元ライン抽出部１０３およびモデル描画部１０４に接続されている。３次元モデルデータ１０は、３次元ラインを抽出する対象となる、物体の形状を表すモデルである。３次元モデルデータ１０は、例えば、複数の面の情報によって構成されるメッシュモデルとして記述されてもよいし、ＮＵＲＢＳなどのパラメトリック表現により形状が記述されてもよい。この３次元モデルデータ１０は、対象物体の形状を表す幾何情報を含む限り、いずれの方式で表現されてもよい。本実施形態では、面と、面を定義する点および線分とによって構成されるメッシュモデルを３次元モデルデータ１０として利用する。
【００２２】
観察方向入力部１０２は、３次元モデルデータ１０の観察方向を入力する。ここで、観察方向とは、３次元モデルを観察する視点に対する３次元形状モデルの位置及び姿勢のことをいう。観察方向入力部１０２により位置姿勢入力が行われる。本実施形態では、位置姿勢推定装置１１は時間軸方向に連続して計測を行うものとして、前回（前時刻）の位置姿勢推定装置１１による計測値を、次回の３次元モデルデータ１０の位置及び姿勢として用いる。
【００２３】
３次元ライン抽出部１０３は、３次元モデルデータ１０から、３次元ラインを抽出する。３次元ラインとは、３次元空間中における位置および方向によって記述される直線情報を表す。本実施形態では、３次元ラインとして、位置および方向によって記述される長さのない局所的な直線を抽出する。３次元ラインの表現形式としては、位置および方向を記述できる幾何情報であればよい。通過位置と方向によってラインを表しても、パラメトリックデータとして表してもよい。
【００２４】
図２に示すように、メッシュモデルから３次元ラインを抽出する処理では、メッシュモデルを構成する線分の投影像を２次元画像上で一定の間隔で分割し、各分割点に位置および方向を割り当てることで局所的な直線を抽出する。また、パラメトリック表現により形状が記述されているモデルを用いる場合は、パラメトリック曲線を分割することで３次元ラインを抽出してもよい。３次元ライン抽出の詳細な処理方法については、後述する。
【００２５】
モデル描画部１０４は、３次元モデルデータ１０のＣＧ描画処理を行う。３次元描画部において描画に利用するグラフィックライブラリは、例えば、ＯｐｅｎＧＬやＤｉｒｅｃｔＸなどの広く利用されているグラフィックライブラリでも、独自に開発したグラフィックライブラリでもよい。３次元モデル保存部１０１に保存されたモデル形式を２次元画像上に投影することができる限り、いずれの方式を用いてもよい。本実施形態ではグラフィックライブラリとしてＯｐｅｎＧＬを利用する。
【００２６】
サンプリング部１０５は、３次元ライン抽出部１０３により抽出された３次元ラインから、他の３次元ラインの投影像と２次元画像上で近接しないように３次元ラインを選出する。３次元形状モデル中に頂点や辺の重複、またはクラックが存在すると、図３（ａ）に示すように、３次元形状モデルから抽出した３次元ラインにも重複が発生する。そこで、図３（ｂ）に示すように、３次元ラインの重複フラグマップを作成して、着目する３次元ラインの近傍に他の３次元ラインが存在するかどうかをチェックする。そして、近傍の範囲で唯一となるように３次元ラインを選択することで、２次元画面上で重複することなく３次元ラインを抽出する。３次元ライン抽出の詳細な処理方法については、後述する。
【００２７】
エッジ判定部１０６は、サンプリング部１０５で選出された３次元ラインの中から、エッジとして観察される３次元ラインをさらに選出する。ここで、エッジとなる３次元ラインとは、図７に示すように、３次元ライン周辺の形状がステップ状に不連続に変化する部分やルーフ状に不連続に変化する部分の３次元ラインのことを指す。エッジ判定の詳細な処理については、後述する。
【００２８】
次に、図４を参照して、本実施形態における３次元ライン抽出方法の処理手順を示すフローチャートについて説明する。
【００２９】
まず、ステップＳ４０１において、初期化が実行される。観察方向入力部１０２は、３次元モデル保存部１０１に保存された３次元モデルデータ１０を観察する方向を３次元ライン抽出装置１００に入力する。前述したように、本実施形態では、観察方向入力部１０２は、位置姿勢推定装置１１から３次元モデルを観察する位置及び姿勢を取得する。また、モデル描画部１０４の処理において、描画処理に利用するカメラ内部パラメータ(焦点距離および主点位置)も必要となるため、観察方向と一緒にカメラ内部パラメータを位置姿勢推定装置１１から取得する。これによりステップＳ４０１の初期化が終了する。そして、ステップＳ４０２の処理に進む。
【００３０】
ステップＳ４０２において、３次元ライン抽出部１０３は、３次元モデルデータ１０から、モデル中の各面を構成する線分データを投影・分割することにより、３次元ラインを抽出する。具体的には、まず、ステップＳ４０１で取得された３次元モデルデータ１０を観察する視点の位置及び姿勢とカメラ内部パラメータとを用いて、３次元モデル中の線分データを全て画像上へ投影し、２次元画像上の投影線分を算出する。線分の投影像は画像上でも線分となる。
【００３１】
次に、図２で説明したように、この投影線分が画像上で等間隔になるように、３次元モデル中の線分データを分割し、各分割点に対して３次元ラインのパラメータを割り当てることによって、３次元ラインを抽出する。３次元ラインは、位置の３次元座標および分割元の線分の３次元方向を保持する。投影結果の２次元座標および投影線分の２次元方向をさらに保持してもよい。このように、線分を示すデータ形式が、当該線分に対応する投影線分が等間隔となるように線分を分割した分割点の位置情報および当該線分の３次元方向により記述される。
【００３２】
３次元モデル中の全ての線分データから３次元ラインを抽出し終え、抽出結果を３次元ラインリストとして保存したら、ステップＳ４０２の処理を終了する。そして、ステップＳ４０３の処理に進む。ステップＳ４０３において、モデル描画部１０４は、ステップＳ４０１で取得された３次元モデルデータ１０を観察する視点の位置および姿勢と、カメラ内部パラメータとを用いて、３次元モデルデータ１０のＣＧ描画を行う。ここで、ＣＧ描画処理は、ステップＳ４０１で取得された物体の位置および姿勢と、カメラ内部パラメータとに基づいて、３次元形状モデルの面情報を２次元画像上に投影し、画像として出力する処理である。このとき、視点からモデルまでの距離の最大値および最小値を設定しておき、その範囲外のモデルの描画は行わないことにより、描画処理の計算コストが低減する。この処理はクリッピングと呼ばれ、一般的に行われている処理である。３次元モデルデータ１０のＣＧ描画により、３次元モデルデータ１０までの奥行き値が格納されたデプスバッファが２次元画像から生成される。３次元モデルデータ１０のＣＧ描画が終わったら、ステップＳ４０３の処理を終了する。そして、ステップＳ４０４の処理に進む。
【００３３】
すなわち、対象物体の位置および姿勢に基づいて、３次元モデルを構成する線分および面を、３次元モデルまでの奥行き情報が各画素に保持された２次元画像上に、投影線分および投影面として投影する。
【００３４】
ステップＳ４０４において、サンプリング部１０５は、ステップＳ４０２で抽出された３次元ラインリストから、２次元画面上で重複が起こらないように、３次元ラインをサンプリングする。このサンプリング処理について図５を参照して説明する。
【００３５】
図５は、本実施形態に係る３次元ラインのサンプリング方法の処理手順を示すフローチャートである。本処理は、ステップＳ４０２で抽出された３次元ライン単位で行われる。
【００３６】
まず、ステップＳ５０１において、１つの３次元ラインが選択され、その３次元ラインが３次元モデルの表面にあるか、または３次元モデルの面の裏に隠れているかが特定される。ステップＳ４０２で抽出された３次元ラインリストの中には、３次元モデルの面によって隠れる３次元ラインも含まれる。そこで、３次元ラインの３次元座標と、ステップＳ４０３で算出されたデプスバッファの値とを比較し、３次元ラインがデプスバッファよりも奥にある（陰線）か否かが特定される。抽出された線分の３次元位置と、奥行き情報が示す位置とを比較して、奥行き情報が示す位置よりも奥に存在する線分を陰線として除去する。
【００３７】
次に、ステップＳ５０２において、３次元ラインがステップＳ５０１で３次元モデルの面の裏に隠れると特定されたか否かが判定される。３次元モデルの面の裏に隠れると特定された場合は（ステップＳ５０２；ＹＥＳ）、ステップＳ５０５に進む。そしてステップＳ５０５において、その３次元ラインを３次元ラインリストから除去する。３次元ラインが３次元モデルの表面にあると特定された場合は（ステップＳ５０２；ＮＯ）、ステップＳ５０３に進む。
【００３８】
ステップＳ５０３において、３次元ラインの重複をチェックする。３次元ラインの重複判定には、着目する３次元ラインの近傍に他の３次元ラインが存在するかどうかをチェックするための重複フラグマップを利用する。重複フラグマップとは、３次元ラインが存在する場所は真を示すフラグを、存在しない場所には偽を示すフラグを格納したマップである。重複フラグマップは、あらかじめ偽のフラグで初期化しておく。そして３次元ラインの２次元座標に応じて重複フラグマップを参照・更新することにより、着目する３次元ラインの２次元座標近傍に他の３次元ラインがあるかどうかが判別される。
【００３９】
次に、ステップＳ５０４において、ステップＳ５０３で近傍に他の３次元ラインがあると判定された場合は（ステップＳ５０４；ＹＥＳ）、ステップＳ５０５に進む。ステップＳ５０５において、その３次元ラインを３次元ラインリストから除去する。近傍に他の３次元ラインがないと判定された場合は（ステップＳ５０４；ＮＯ）、重複フラグマップを参照し、その３次元ラインの２次元座標位置に真のフラグを格納して、ステップＳ５０６に進む。３次元ラインを３次元ラインリストから除去する処理は、例えば、選択された線分に対応する投影線分のうち、２次元画像上で当該投影線分の１つから所定領域の範囲に存在する投影線分を、２次元画像上で重複する線分として、１つを残して削除する処理である。
【００４０】
ステップＳ５０６において、３次元ラインリスト中の全ての３次元ラインが処理されたか否かが判定される。まだ処理していない３次元ラインがあれば（ステップＳ５０６；ＮＯ）、ステップＳ５０１戻る。一方、次の３次元ラインの処理を行い、全ての３次元ラインの処理が終了していれば（ステップＳ５０６；ＹＥＳ）、図４のステップＳ４０４の処理を終了する。そして、ステップＳ４０５に進む。
【００４１】
ステップＳ４０５において、エッジ判定部１０６は、ステップＳ４０４で選択された３次元ラインリストの中から、エッジとなる３次元ラインをさらに選択する。具体的には、まず、３次元ラインリストから除去する処理が実行された後の線分に対して、当該線分を構成する点が示す位置から当該線分と直交する方向に所定画素分当該画素の奥行き情報を取得する。そして、その直交する方向に対する奥行き情報の２次微分値を算出する。この２次微分値の絶対値が閾値以上であるか否か判断する。２次微分値の絶対値が閾値以上であると判断された場合、当該線分を、２次元画像上において対象物体の特徴を示すエッジとなる線分として抽出する。
【００４２】
図６を参照して、このステップＳ４０５に係る３次元ラインのエッジ選択方法の詳細な処理手順を説明する。
【００４３】
まず、ステップＳ６０１において、ステップＳ４０４で選出された３次元ラインリストのうちの１つに着目して、３次元ライン周辺領域の奥行き値情報を、ステップＳ４０３で得られたデプスバッファから取得する。奥行き値情報としては、図７（ａ）（ｂ）に示されるように、３次元ラインの投影位置の距離値と、投影されたラインの法線方向±２ピクセル位置の距離値を取得する。サンプリングする距離値の数や間隔は、モデルの詳細度や描画解像度に応じて調整してもよい。
【００４４】
次に、ステップＳ６０２において、図７（ｃ）に示されるように、３次元ライン周辺領域の距離値に対して２次微分値を算出する。次に、ステップＳ６０３において、算出された距離値の２次微分値を利用して、エッジ判定を行う。算出された距離値の２次微分値の絶対値が閾値以下であるか否かが判定される。２次微分値の絶対値が閾値よりも大きい場合は（ステップＳ６０３；ＮＯ）、距離値が不連続に変化する境界部分、すなわちエッジとなる３次元ラインであると判定されたことになるため、ステップＳ６０５に進む。一方、２次微分値の絶対値が閾値以下である場合は（ステップＳ６０３；ＮＯ）、エッジではないと判定されたことになるため、ステップＳ６０４に進む。
【００４５】
ステップＳ６０４において、エッジでないと判定された３次元ラインを、３次元ラインリストから除去する。ステップＳ６０５において、以上の処理が３次元ラインリスト中の全ての３次元ラインに対して行われたか否かが判定される。全ての３次元ラインに対して処理が行われていない場合（ステップＳ６０５；ＮＯ）、ステップＳ６０１に戻る。一方、全ての３次元ラインに対して処理が行われている場合（ステップＳ６０５；ＹＥＳ）、処理を終了する。
【００４６】
以上の処理により、３次元モデルデータ１０から、エッジとなる３次元ラインリストが抽出される。結果として得られた３次元ラインリストは位置姿勢推定装置１１に出力され、モデルフィッティング処理に用いられる。モデルフィッティング処理は、例えば非特許文献１に開示される方法によって行うことができる。すなわち、まず、３次元ライン抽出装置１００から出力された３次元ラインを、物体の概略の位置および姿勢に基づいてモデルフィッティング対象の物体が撮像された２次元画像上に投影する。そして、投影像近傍から１次元エッジ検出を行い、各３次元ラインと対応する画像上のエッジを検出する。次に、３次元ラインと画像上のエッジとの対応に基づいて、非線形最適化計算によって繰り返し位置及び姿勢を補正することにより、対象物体の位置及び姿勢の算出を行うことができる。
【００４７】
以上述べたように、本実施形態では、２次元画面上で重複がないように３次元ラインを３次元モデルから抽出し、且つデプスバッファを利用して３次元ラインのエッジ判定を行うことにより、３次元形状モデルのクラックや頂点の重複に対処可能となる。また、３次元ラインの座標は、３次元形状モデルの座標から直接算出することにより、元の３次元形状モデルの精度を保持したまま、エッジとなる３次元ラインを抽出することが可能となる。
【００４８】
（第２実施形態）
第１実施形態では、ステップＳ４０５において、３次元ライン周辺のデプスバッファの距離値の２次微分値を算出することにより、３次元ラインの輪郭判定を行っていた。しかし、３次元ラインの輪郭判定は、これに限るものでなく、例えば、デプスバッファ全体からエッジ検出を行って生成されたエッジ画像を利用してもよい。具体的には、ステップＳ４０３において、３次元形状モデルのＣＧ描画によりデプスバッファを取得した後、デプスバッファ全体に対してエッジ検出処理を行う。エッジ検出処理は、例えば公知の手法であるＣａｎｎｙのエッジ検出器を用いる。そして、ステップＳ４０５のエッジ判定処理では、３次元ラインの２次元位置に対応するデプスバッファのエッジ検出結果を参照し、デプスバッファ上でエッジになっている場合は、その３次元ラインをエッジと判定する。なお、３次元ラインのエッジ判定は、以上に挙げた方法に限るものでなく、３次元ライン周辺の形状の不連続性に基づいて判定処理を行う限り、いずれの手法を用いてもよい。
【００４９】
（第３実施形態）
第１実施形態では、ステップＳ４０４において、２次元画面上の重複フラグマップを作成することで、２次元画面上での３次元ラインの重複を除去していた。しかし、３次元ラインの重複除去は、これに限るものでなく、例えば、３次元ライン間の２次元距離を計算して判定してもよい。具体的には、既に確定した３次元ラインの投影像と、着目する３次元ラインの投影像との間の２次元距離を算出し、閾値以下の近傍に他の３次元ラインがある場合には、着目する３次元ラインを３次元ラインリストから除去する処理である。また、３次元ライン間の近傍探索処理は、基本的に全探索になるため、ｋ‐ｄツリーを利用して３次元ラインのデータ構造を保持して、探索の効率化を図ってもよい。以上に示すように、２次元画面上で３次元ラインの近傍を判定することが出来る限り、いずれの手法でもよく、手法の選択に特に制限はない。
【００５０】
（第４実施形態）
第１実施形態では、３次元ラインは、長さのない局所ラインデータとして処理・出力を行っていた。しかし、３次元ラインのデータ形式は、これに限るものでなく、始点と終点の端点によって記述されるような、有限の長さをもつ線分データとして扱ってもよい。例えば、線分を示すデータ形式が、当該線分を構成する始点および終点の各端点の位置情報により記述される構成とすればよい。具体的には、ステップＳ４０２において、３次元モデルデータ１０から抽出された長さのない局所的な直線データではなく、３次元モデルデータ１０を構成する各線分そのものを３次元ラインとして登録する。ただし、このときにステップＳ４０２の処理と同様の手法により各線分から分割した局所線分のデータも保持してもよい。以降の処理は、第１実施形態と同様に、線分から分割された局所線分データごとに処理を行う。そして、ステップＳ４０５の処理が終了した時点で、エッジでないと判定された局所線分データを含む３次元ラインは削除し、エッジとなる３次元ラインのみを位置姿勢推定装置１１に出力する。以上に示すように、３次元ラインとして取り扱うラインデータは、輪郭またはルーフエッジとして観察される３次元的直線を記述可能であって、位置姿勢推定装置１１が対応できる形式であれば、いずれの形式でもよい。
【００５１】
（第５実施形態）
第１実施形態では、観察方向に応じた輪郭となる３次元ラインを位置姿勢推定装置１１にランタイムで出力していた。しかし、予め様々な方向から観察した３次元ラインのデータを作成しておき、位置姿勢推定装置１１に出力してもよい。具体的には対象物体を取り囲むＧｅｏｄｅｓｉｃ Ｄｏｍｅを、半径を変えて複数設定し、対象物体の観察方向および観察距離を、Ｇｅｏｄｅｓｉｃ Ｄｏｍｅ上で均等になるように設定する。そして、各Ｇｅｏｄｅｓｉｃ Ｄｏｍｅの各点に相当する位置及び姿勢を観察視点として、エッジとなる３次元ラインの抽出を行い、対象物体の観察方向と観察距離の情報とともに３次元ラインのデータを保存する。位置姿勢推定装置１１は、方向別の３次元ラインデータから、前時刻の対象物体の位置姿勢に最も近い３次元ラインのデータを選択して、位置姿勢推定に用いる。この方式は、ランタイムに３次元ラインを選出する方式と比較して、保持するデータ量が増える代わりに、ランライム時の計算量が削減される特徴がある。これら方式の選択は、利用シーンに応じて選択すればよい。
【００５２】
（第６実施形態）
第１実施形態では、３次元モデルデータ１０は、点、面、および線分により構成されたメッシュデータであった。しかし、３次元モデルデータ１０のデータ形式は、これに限るものではなく、例えば、ＮＵＲＢＳ曲面などで表現されるパラメトリックモデルでもよい。この場合、ステップＳ４０２において、パラメトリックモデルから３次元線分を算出する処理が必要となる。この処理は、例えば、パラメトリックモデルの法線マップからエッジ検出を行い、法線が急激に変化する部分の座標と方向を抽出することにより、３次元線分を算出する処理である。以上に示すように、３次元モデルデータ１０として取り扱うデータ形式は、対象物体の形状を表現できる限り、いずれの形式でもよい。
【００５３】
（その他の実施形態）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
0005620741.tif 000002
【図２】
0005620741.tif 000003
【図３】
0005620741.tif 000004
【図４】
0005620741.tif 000005
【図５】
0005620741.tif 000006
【図６】
0005620741.tif 000007
【図７】
0005620741.tif 000008