(57)【特許請求の範囲】
【請求項１】
画像列から物体の面情報を含んだ３次元形状モデルを生成する３次元形状モデル生成システムにおいて、
該画像列から、画像エッジ点と対応づけて３次元復元した該物体の３次元エッジ点の各々について、該対応する画像エッジ点が現れる部分画像列を抽出する部分画像列抽出手段と、
該部分画像列抽出手段からの部分画像列の各画像上で、対応する３次元エッジ点を有する前記画像エッジ点のある点から直線を伸ばし、最初に当たった画像エッジ点との間に線分を張り、該画像エッジ点が対応する３次元エッジ点を有していれば該線分を２次元面素線分とし、最終的に各２次元面素線分に対応する３次元面素線分を生成する３次元面素線分生成手段と、
該３次元面素線分の集合を前記物体の面を構成するボクセル表現に変換するボクセル表現変換手段とを備え、
物体の面情報を含んだ３次元形状モデルを出力することを特徴とする３次元形状モデル生成システム。
【請求項２】
画像列から処理すべき画像を１枚ずつ入力し、該画像列から物体の面情報を含んだ３次元形状モデルを生成する３次元形状モデル生成システムにおいて、
現在画像と以前の画像とから、画像エッジ点と該物体の３次元エッジ点とを対応付けして３次元復元する３次元エッジ点復元手段と、
該３次元エッジ点復元手段で復元した３次元エッジ点の各々について、該３次元エッジ点が初めて復元されたならば、該３次元エッジ点に対応する画像エッジ点が初めて抽出された画像から現在画像までの各画像において、該３次元エッジ点と対応する画像エッジ点と、他の３次元エッジ点に対応する画像エッジ点との間に２次元線分を張り、該３次元エッジ点が初めて復元されたのでなければ、現在画像において、該３次元エッジ点と対応する画像エッジ点と他の３次元エッジ点に対応する画像エッジ点との間に２次元線分を張って、該２次元線分に対応する３次元面素線分の集合を生成する３次元面素線分生成手段と、
該３次元面素線分の集合を前記物体の面を構成するボクセル表現に変換するボクセル表現変換手段とを備え、
順次画像列の画像を処理して、物体の面情報を含んだ３次元形状モデルを出力することを特徴とする３次元形状モデル生成システム。
【請求項３】
前記３次元面素線分生成手段は、前記３次元面素線分生成手段により生成された３次元面素線分から、可視性制約に反する３次元面素線分を排除する可視性制約判定手段を有し、
該可視性制約判定手段は、３次元面素線分に対応する２次元面素線分が存在する各画像上で、生成した３次元面素線分に対応する２次元面素線分上の各画素に対して、画像エッジ点があるかを調べ、あった場合は、その画像エッジ点の対応する３次元エッジ点のカメラから見た奥行が該３次元面素線分より大きい場合は、該３次元面素線分を排除することを特徴とする請求項１または２に記載の３次元形状モデル生成システム。
【請求項４】
前記ボクセル表現変換手段は、３次元空間を微小立方体の集合で表し、
前記３次元エッジ点集合の各３次元線分から所定の間隔で３次元点をサンプリングし、
該３次元点に位置が最も近い微小立方体を求めて、該微小立方体に該３次元点を登録して、
該３次元点の個数が所定の閾値以上の微小立方体だけを残して前記物体の３次元形状とする
ことを特徴とする請求項１〜３のいずれかに記載の３次元形状モデル生成システム。
【請求項５】
コンピュータ・システムを、
画像列から、画像エッジ点と対応づけて３次元復元した該物体の３次元エッジ点の各々について、対応する画像エッジ点が現れる部分画像列を抽出する部分画像列抽出手段と、
該部分画像列抽出手段からの部分画像列の各画像上で、対応する３次元エッジ点を有する前記画像エッジ点のある点と、エッジ法線の方向の他の画像エッジ点との間に線分を張り、該画像エッジ点が対応する３次元エッジ点を有していれば該線分を２次元面素線分とし、最終的に各２次元面素線分に対応する３次元面素線分を生成する３次元面素線分生成手段と、
該３次元面素線分の集合を前記物体の面を構成するボクセル表現に変換するボクセル表現変換手段として機能させ、
画像列から物体の面情報を含んだ３次元形状モデルを生成する３次元形状モデル生成システムとして動作させることを特徴とするコンピュータ・プログラム。
【請求項６】
コンピュータ・システムを、
現在画像と以前の画像とから、画像エッジ点と該物体の３次元エッジ点とを対応付けて３次元復元する３次元エッジ点復元手段と、
該３次元エッジ点復元手段で復元した３次元エッジ点の各々について、該３次元エッジ点が初めて復元されたならば、該３次元エッジ点に対応する画像エッジ点が初めて抽出された画像から現在画像までの各画像において、該３次元エッジ点と対応する画像エッジ点と、他の３次元エッジ点に対応する画像エッジ点との間に２次元線分を張り、該３次元エッジ点が初めて復元されたのでなければ、現在画像において、該３次元エッジ点と対応する画像エッジ点と他の３次元エッジ点に対応する画像エッジ点との間に２次元線分を張って、該２次元線分に対応する３次元面素線分の集合を生成する３次元面素線分生成手段と、
該３次元面素線分の集合を前記物体の面を構成するボクセル表現に変換するボクセル表現変換手段として機能させ、
順次画像列の画像を処理して、物体の面情報を含んだ３次元形状モデルを出力する３次元形状モデル生成システムとして動作させることを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像入力装置(カメラ)を移動しながら撮影した画像列から物体の面情報を含んだ３次元形状モデルを生成するシステムに関する。
【背景技術】
【０００２】
カメラ画像列とそれらを撮影したときのカメラ姿勢列とから物体の面情報を含んだ密な３次元形状モデルを生成する方法として、従来、相関ステレオ法、スペースカービング法、パッチ補間法が提案されている。
相関ステレオ法では、たとえば、非特許文献１で述べられているように、２枚の画像間で対応づけした画像点の３次元復元像を三角測量の原理で求める。画像点の対応づけを行うために、各画像点の類似度を、その周辺画像の正規化相関から計算する。
非特許文献２で提案されたスペースカービング法は、物体をボクセルと呼ばれる微小立方体の集合で表し、各カメラ姿勢で撮影した画像に整合するようにボクセル集合を削ることで物体の３次元形状を生成する。具体的には、与えられたカメラ姿勢にしたがって、ボクセルを各画像に投影し、その投影点の色が画像間で大きく食い違えば、そのボクセルは矛盾しているとして削除する。これを各ボクセルについて繰り返すことで、すべての画像での見え方に矛盾しない物体形状モデルを作ることができる。
【０００３】
パッチ補間法は、まず、画像から抽出した顕著な特徴点を用いて物体の疎な３次元形状
を復元し、次に、その特徴点を頂点とする多角形パッチによって物体の面を補間することで、物体の３次元形状を生成するものである。多くの場合、三角形パッチが用いられる。この方法では、本来は平面がない部分に偽のパッチが張られることがあるため、非特許文献３で述べられているように、可視性制約(visibility constraint) と呼ばれる制約を用いて、偽のパッチを除去することが行われる。
【０００４】
【非特許文献１】徐剛:”写真から作る３次元CG, 5.3 節”，pp.53-58，近代科学社, 2001
【非特許文献２】K. Kutulakos and S. Seitz: ”A theory of shape by space carving,”Proceedings of International Conference on Computer Vision, pp. 307-314, 1999
【非特許文献３】A. Manessis, A. Hilton, P. Palmer, P. McLauchlan, and X. Shen:”Reconstruction of Scene Models from Sparse 3D Structure,” Proceedings of Computer Vision and Pattern Recognition, pp. 666-671, 2000
【非特許文献４】友納: ”画像列からの密な物体モデル生成のためのエッジの３次元復元”,第23 回日本ロボット学会学術講演会予稿集，講演番号3B11，2005 年9 月
【非特許文献５】友納:”基線長選択機能を備えた形状復元に基づく単眼カメラ画像列からの３次元マップの構築”第１０回ロボティクスシンポジア予稿集, pp.159-164, 2005
【非特許文献６】J. Canny: ”A Computational Approach to Edge Detection,” IEEETransaction on Pattern Recognition and Machine Intelligence, Vol. 8, No. 6, pp.679-698 (1986)
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来の相関ステレオ法は、表面に模様や凹凸を多くもつ物体には有効であるが、模様の少ない物体にはうまく作用しないという問題がある。たとえば、家具、壁、床などの物体は、模様が少ない広い平面で構成されることが多い。このような平面上の点に対しては、正規化相関などの指標で計算した類似度はほとんど同じ値になってしまう。このため、画像間で点の対応づけができなくなり、３次元復元が得られなくなる。
【０００６】
また、スペースカービング法は、画像点の明示的な対応づけがいらないという利点があるが、物体の色と背景の色が似ている場合にうまく作用しないという問題がある。各画像での色や輝度に不整合が生じた場合にボクセルを削除するため、不整合の度合いが小さいと、うまくボクセルを削ることができなくなる。また、広い平面をうまく削るには、その平面と背景をよく比較するために、その平面とほぼ平行なカメラ視線が必要であり、画像
撮影においてカメラを広範囲に動かさなければならないという問題もある。
【０００７】
パッチ補間法は、これらの問題には対処できるが、顕著な特徴点が少数しか得られないと、1 つのパッチが複数の面にまたがって生成されることが多くなり、正確な形状が得られなくなるという問題ある。
たとえば、図１（ａ）に示すような２つの矩形平面で構成された物体を考える。特徴点抽出処理において、顕著な特徴点がすべて得られた場合は、図１（ｂ）のハッチングで示したようなパッチが張られるが、たとえば、頂点Ｃが検出できなかったとすると、図１（ｃ）のハッチングで示したようなパッチが張られてしまう。このうち、パッチＡＤＥは可視性制約で削除可能であるが、その場合でも、パッチが張られない大きな空白部分が残る。さらに、面の形状が円のように明確な特徴点を持たない場合は、パッチを張ることができないという問題もある。
本発明は、これらの問題に対処するために、画像エッジ点をもとに面を補間することで、面情報を含んだ密な３次元形状モデルを生成することを目的とする。
【課題を解決するための手段】
【０００８】
上述の本発明の目的を達成するために、本発明は、画像列から物体の面情報を含んだ３次元形状モデルを生成する３次元形状モデル生成システムにおいて、該画像列から画像エッジ点と対応づけて３次元復元した該物体の３次元エッジ点の各々について、該対応する画像エッジ点が現れる部分画像列を抽出する部分画像列抽出手段と、該部分画像列抽出手段からの部分画像列の各画像上で、対応する３次元エッジ点を有する前記画像エッジ点のある点から直線を伸ばし、最初に当たった画像エッジ点との間に線分を張り、該画像エッジ点が対応する３次元エッジ点を有していれば該線分を２次元面素線分とし、最終的に各２次元面素線分に対応する３次元面素線分を生成する３次元面素線分生成手段と、該３次元面素線分の集合を前記物体の面を構成するボクセル表現に変換するボクセル表現変換手段とを備え、物体の面情報を含んだ３次元形状モデルを出力することを特徴とする。
【０００９】
また、本発明は、画像列から処理すべき画像を１枚ずつ入力し、該画像列から物体の面情報を含んだ３次元形状モデルを生成する３次元形状モデル生成システムにおいて、現在画像と以前の画像とから、画像エッジ点と該物体の３次元エッジ点とを対応づけして３次元復元する３次元エッジ点復元手段と、該３次元エッジ点復元手段で復元した３次元エッジ点の各々について、該３次元エッジ点が初めて復元されたならば、該３次元エッジ点に対応する画像エッジ点が初めて抽出された画像から現在画像までの各画像において、該３次元エッジ点と対応する画像エッジ点と、他の３次元エッジ点に対応する画像エッジ点との間に２次元線分を張り、該３次元エッジ点が初めて復元されたのでなければ、現在画像において、該３次元エッジ点と対応する画像エッジ点と他の３次元エッジ点に対応する画像エッジ点との間に２次元線分を張って、該２次元線分に対応する３次元面素線分の集合を生成する３次元面素線分生成手段と、該３次元面素線分の集合を前記物体の面を構成するボクセル表現に変換するボクセル表現変換手段とを備え、順次画像列の画像を処理して、物体の面情報を含んだ３次元形状モデルを出力することを特徴とする。
前記３次元面素線分生成手段は、前記３次元面素線分生成手段により生成された３次元面素線分から、可視性制約に反する３次元面素線分を排除する可視性制約判定手段を有し、該可視性制約判定手段は、３次元面素線分に対応する２次元面素線分が存在する各画像上で、生成した３次元面素線分に対応する２次元面素線分上の各画素に対して、画像エッジ点があるかを調べ、あった場合は、その画像エッジ点の対応する３次元エッジ点のカメラから見た奥行が該３次元面素線分より大きい場合は、該３次元面素線分を排除するとよい。
【００１０】
上述の３次元形状モデル生成システムにおいて、前記ボクセル表現変換手段は、３次元空間を微小立方体の集合で表し、前記３次元エッジ点集合の各３次元線分から所定の間隔で３次元点をサンプリングし、該３次元点に位置が最も近い微小立方体を求めて、該微小立方体に該３次元点を登録して、該３次元点の個数が所定の閾値以上の微小立方体だけを残して前記物体の３次元形状とするとよい。
また、上述の各手段をコンピュータ・システムに機能させて、画像列から物体の面情報を含んだ３次元形状モデルを生成する３次元形状モデル生成システムとして動作させることを特徴とするコンピュータ・プログラムも本発明である。
【発明の効果】
【００１１】
本発明によれば、多数のエッジ点をつないだ線分を用いるので、物体表面上に模様が無くても面情報の復元が安定してできるという効果がある。また、一部のエッジ点が隠れても、他のエッジ点でカバーできるため、面情報の復元が安定してできるという効果がある。また、面の境界線が曲線を含んでいても、正しく形状を復元できるという効果がある。
【発明を実施するための最良の形態】
【００１２】
＜概要＞
本発明では、カメラ画像列からカメラ運動と物体の３次元エッジが復元されているとし、それらを入力として、面情報を含んだ物体の３次元形状モデルを生成する。
カメラ運動と３次元エッジの復元には、種々の方法が考えられるが、たとえば、非特許文献４，５の方法がある。非特許文献４，５の方法では、単眼カメラ画像列に対して、少数の一意性の高い特徴点を画像間で追跡し、因子分解法と逆投影誤差最小化を用いて、カメラ運動を推定する。そして、このカメラ運動を用いて画像間でエッジ点の対応づけを行い、三角測量の原理を用いて３次元復元を行い、３次元エッジ点を求める。
【００１３】
本発明による３次元形状モデル生成システムは、前記問題に対処するため、エッジ点を結ぶ線分の集合で面を復元する。ここでは、この線分を面素線分と呼ぶ。
たとえば、図２に示すように、相対する２本のエッジの間に面素線分を張りつめ、そのエッジで構成される面を覆う。図２（ａ）では、エッジ点Ｐｉから放射状に相対するエッジに面素線分Ｓｉｊを並べて、面Ａの一部を覆っている。この処理をエッジ上の各点について行うことで、面全体を覆う。
この方法では、物体面が曲線をもっていても、その面が平面である限りは、図２ （ｂ）の円筒の上面のように面が正しく復元される。その面が曲面の場合でも、その境界エッジが明確であり、かつ、曲面の曲率が小さければ、図２（ｂ）の円筒の側面のように、よい近似が得られる。曲面の場合は、三角形パッチよりも、面素線分の方が曲面の隅々まで隙間なく覆うことが可能であるという利点がある。
なお、ここでは３次元の面素線分の例を示したが、後述するように、実際の処理では２次元の面素線分を生成した後、３次元に復元するという処理を行う。
【００１４】
しかしながら、このようにして生成した面素線分は、あくまで仮説であり、そこが実際に面領域かどうかは１枚の画像からでは判定できない。そこで、入力画像列の各画像で矛盾が生じないかどうかを調べ、矛盾が生じる面素線分は除去するようにする。具体的には、３次元の面素線分を各画像に投影した際に、その投影像上に画像エッジ点が存在し、かつ、その画像エッジ点に対応する３次元エッジ点のカメラからの奥行が面素線分よりも遠い場合には矛盾が生じていると判定する(例えば図７参照：後で説明)。もし、この面素線分が正しいならば、そこに物体面があることになり、その面素線分よりもカメラから遠いエッジ点は、物体面に遮られて画像に写らないはずである。エッジ点が画像上で見えているということは、この面素線分が偽であるという証拠になる。この制約は可視性制約と呼ばれ、上述のパッチ補間法などでも利用されている。このように、可視性制約を利用すれば、偽の面素線分を除去し、与えられた画像列に矛盾しない物体の面情報を得ることができる。
最後に、多数の面素線分は互いに重複する部分が多いため、ボクセル表現に変換して、
全体のデータ量を減らす。
【００１５】
以上述べたように、エッジ点をつないだ面素線分を用いて面を復元する点が本発明の特徴である。これにより、発明の効果で述べたような効果が得られる。また、パッチ補間法では、なるべく均等なパッチを生成するために、ドロネー分割などの手法が必要であるが、面素線分はエッジ点をつなぐだけでよいので、非常に簡単な処理で生成できるという利点もある。
【００１６】
本発明の３次元形状モデル生成システムは、一括処理と逐次処理の２つの処理形態をもつ。一括処理は、画像列から生成した３次元エッジモデルを入力して、面情報を一括で生成するものである。逐次処理は、画像列を入力して３次元エッジモデルを逐次的に生成しながら、同時に面情報も逐次的に生成するものである。
【００１７】
＜構成要素の説明＞
まず、図３を用いて、本発明で用いる物体モデルの構成例を説明する。
本発明の３次元形状モデル生成システムで作成される物体モデルのデータの構成例は、図３（ａ）に示すように、物体モデル名、３次元エッジモデル、画像情報列、および、ボクセル集合から構成される。物体モデル名はオペレータが物体に与えるもので、通常は対象物体に即した名前をつける。３次元エッジモデルは、画像列から復元した３次元エッジ点Ｐｉの集合である。画像情報列は、入力画像列から抽出された画像情報の列である。
画像情報は、図３（ｂ）に示すように、画像ＩＤ、カメラ姿勢、画像エッジ点集合から構成される。画像ＩＤは、対象とする画像を一意に示すＩＤである。カメラ姿勢は、この画像を撮影したときのカメラの姿勢であり、ある３次元座標系内の位置と方向を表す６個の変数からなる。座標系は任意でよいが、通常は、画像列の最初の画像を撮影したカメラ姿勢を原点にして設定される。画像エッジ点集合は、この画像から抽出された画像エッジ点情報の集合である。
【００１８】
画像エッジ点情報は、図３（ｃ）に示すように、エッジ点ＩＤ、画像ＩＤ、画像内での位置と方向から構成される。エッジ点ＩＤはエッジ点を一意に示すＩＤであり、各画像に現れる同一のエッジ点はすべて同じエッジ点ＩＤを持つ。また、対応する３次元エッジ点も同じエッジ点ＩＤを持つ。画像ＩＤは、この画像エッジ点が属する画像を示す画像ＩＤである。位置は、非特許文献６で提案されたＣａｎｎｙオペレータなどのエッジ抽出オペレータで求める。方向はその位置での画像の微分方向であり、やはりエッジ抽出オペレータにより求められる。
【００１９】
３次元エッジ点情報は、図３（ｄ）に示すように、エッジ点ＩＤ、復元開始画像ＩＤ、３次元空間での位置から構成される。エッジ点ＩＤは、この３次元エッジ点を一意に示すＩＤであり、対応する画像エッジ点と同一のものである。復元開始画像ＩＤは、この３次元エッジ点が最初に復元された画像を示す画像ＩＤである。
【００２０】
＜一括処理の手順＞
図４にしたがい、本発明の３次元形状モデル生成システムの一括処理の一実施例を説明する。入力は、画像列、カメラ運動、３次元エッジ点集合Ｇである。一括処理では、ボクセル集合以外の情報は入力として与えられることになる。なお、画像列から３次元エッジ点の集合を作成することは、例えば、前述の非特許文献４，５に記載のように求めることができる。本発明は、これらの情報を用いて面素線分を作り、それから物体モデルのボクセル集合を生成するものである。
ここでのエッジ点の呼び方を次のように定める。あらかじめ、３次元エッジ点、および、それと対応する各画像上の画像エッジ点には、すべて同一の識別子（エッジＩＤ）を割り当てておくとする。したがって、３次元エッジ点をｑというエッジＩＤで表し、また、ある画像上で対応する画像エッジ点もｑというエッジＩＤで呼ぶ。
まず、３次元エッジ点集合Ｇからエッジ点ｑを１個取り出す（Ｓ１０２）。ステップＳ１０４において、同一の識別子を有するエッジ点ｑが現れる部分画像列Ｕを求める。部分画像列Ｕは、エッジ点ｑが最初に抽出された画像から最後に抽出された画像までの部分画像列である。
次に、ステップＳ１０６において、Ｕに含まれる各画像に対して、エッジ点ｑから出る面素線分を集め、面素線分集合Ｈに登録する。その方法は後述する。
【００２１】
ステップＳ１０８において、Ｈから面素線分ｈを取り出し、エッジ点ｑが現れる全画像で、面素線分ｈが可視性制約を満たすか調べる（ステップＳ１１０）。その方法は後述する。面素線分ｈが可視性制約を満たせば（Ｓ１１０でＹｅｓ）、ステップＳ１１２において、面素線分ｈを面素線分リストＬに登録する。面素線分ｈが可視性制約を満たされなければ（Ｓ１１０でＮｏ）、何もしない。
次に、ステップＳ１１４において、面素線分集合Ｈの中に、処理をまだ施していない面素線分があれば（Ｓ１１４でＮｏ）、ステップＳ１０８に戻る。全面素線分について処理していれば（Ｓ１１４でＹｅｓ）、ステップＳ１１６に移る。
次に、ステップＳ１１６において、３次元エッジ点集合Ｇに未処理のエッジ点が残っているか調べる。残っていれば（Ｓ１１６でＮｏ）、ステップＳ１０２に戻る。残っていなければ（Ｓ１１６でＹｅｓ）、ステップＳ１１８において、面素線分リストＬの各面素線分をボクセル表現に変換する。その方法は後述する。
【００２２】
＜逐次処理の手順＞
図５にしたがい、本発明の３次元形状モデル生成システムの逐次処理の一実施例を説明する。入力は、画像列内の一枚の画像（現在画像と呼ぶ）である。以下で説明する逐次処理では、ボクセル集合以外の情報はステップＳ２０１等で生成される。本発明は、これらの情報を用いて面素線分を作り、それから物体モデルのボクセル集合を生成するものである。
【００２３】
まず、ステップＳ２０１において、現在画像とこれまでの画像から、現在画像に現れる
エッジ点および現在画像を撮影したカメラ姿勢を復元する。この復元処理には、たとえば、非特許文献４，５で提案された方法を用いる。復元された３次元エッジ点の集合をＧとする。次に、ステップＳ２０２において、３次元エッジ点集合Ｇからエッジ点ｑを１個取り出す。次に、ステップＳ２０３において、同一の識別子を有するエッジ点ｑが現在画像で初めて復元されたエッジ点かどうかを調べる。エッジ点ｑが初めて復元された場合（Ｓ２０３でＹｅｓ）は、ステップＳ２０４で、エッジ点ｑが初めて抽出された画像から現在画像までの各画像で、エッジ点ｑから出る面素線分を作り、集合Ｈ（ｑ）に格納する。エッジ点ｑが初めて復元されたのではない場合は（Ｓ２０３でＮｏ）、ステップＳ２０５において、現在画像でエッジ点ｑから出る面素線分を作り、集合Ｈ（ｑ）に追加する。
【００２４】
次に、ステップＳ２０６において、集合Ｈ（ｑ）から面素線分ｈを１個取り出す。次に、ステップＳ２０７において、エッジ点ｑが現れる全画像で、面素線分ｈが可視性制約を満たすか調べる。面素線分ｈが可視性制約を満たさなければ（Ｓ２０７でＮｏ）、ステップＳ２０８において、面素成分ｈを集合Ｈ（ｑ）から削除する。面素成分ｈが可視性制約を満たせば（Ｓ２０７でＹｅｓ）、何もしないでステップＳ２０９に移る。
次に、ステップＳ２０９において、集合Ｈ（ｑ）の中にステップＳ２０６からステップＳ２０８までの処理をまだ施していない面素線分があれば（Ｓ２０９でＮｏ）、ステップＳ２０６に戻る。全面素線分について処理していれば（Ｓ２０９でＹｅｓ）、ステップＳ２１０に移る。次に、ステップＳ２１０において、３次元エッジ点集合Ｇに未処理のエッジ点が残っているか調べる。残っていれば（Ｓ２１０でＮｏ）、ステップＳ２０２に戻る。残っていなければ（Ｓ２１０でＹｅｓ）、ステップＳ２１１において、各エッジ点ｑの面素線分Ｈ（ｑ）をボクセル表現に変換する。
この処理を画像列内の各画像に繰り返し適用することで、逐次的に面情報を生成することができる。この一連の処理の間、面素線分集合Ｈ（ｑ）は保持しておく。すなわち、現画像の処理で用いたＨ（ｑ）を次画像の処理に引き継いで用いる。これにより、Ｈ（ｑ）の中の偽面素線分を可視性制約によって徐々に削除していくことができる。
【００２５】
ステップＳ２０４で、エッジ点ｑが初めて抽出された画像まで遡るのは、次の理由による。エッジ点ｑは、その復元誤差が充分に小さくなってから、集合Ｇに登録される。復元誤差を小さくするには、充分な基線長（カメラ間距離）が必要である。そのため、エッジ点ｑが最初に復元される画像は、一般に、エッジ点ｑが最初に現れる画像よりも後に撮影されたものになる。一方、エッジ点ｑから出る面素線分の可視性制約の判定は、エッジ点ｑが現れるすべての画像で行う必要がある。
そのため、ステップＳ２０４でエッジ点ｑが抽出された最初の画像まで遡り、そこから現在画像までの部分画像列で可視性制約の判定を行う。ｑが初めて復元されたときにこの処理を一回行えば、次からは、ステップＳ２０５のように、現在画像での面素線分だけをＨ（ｑ）に追加していけばよい。
【００２６】
＜面素線分の生成（Ｓ１０６，Ｓ２０４参照）＞
図６を用いて、面素線分を生成する処理（Ｓ１０６，Ｓ２０４）を説明する。まず、３次元空間では、図６（ａ）のように、３次元エッジ点ＰｉとＰｊをつないで面素線分Ｓｉｊを作る。各３次元エッジ点についてこのような面素線分の集合を作り、面を覆うことで、面情報を含んだ３次元形状モデルを生成することができる。
ところが、すべての３次元エッジ点の組に対して上記処理を施すと、膨大な数の面素
線分が生成されてしまう。１つの物体モデルは、通常、数千個から数万個のエッジ点で
構成されるが、エッジ点の組はその二乗になるため、膨大な個数になる。しかも、その
大部分は可視性制約によって削除されてしまうので、効率が非常に悪い。
そこで、３次元エッジ点を直接つなぐのではなく、図６（ｂ）のように、画像エッジ点
をつなぐようにする。図６（ｂ）は、エッジ点ＰｉとＰｊをつないだ３次元面素線分Ｓｉｊに対応する、画像エッジ点ｐｉとｐｊをつないだ２次元面素線分ｓｉｊを示している。
画像エッジ点ｐｉからの面素線分の生成は次のように行う。対応する３次元エッジ点をもつ画像エッジ点の集合をＥｃと記す。画像エッジ点ｐｉ∈Ｅｃから出る線分を次のように生成する。まず、微分画像からｐｉにおけるエッジ法線ｎｉの方向ｄを求め、ｐｉから方向ｄ＋ａに直線を伸ばして、他の画像エッジとの最初の交点ｐｊを求める。そして、画像エッジ点ｐｊがＥｃに属するならば、ｐｉとｐｊをつないだ面素線分ｓｉｊを生成する。ｐｊがＥｃに属さないならば、ｐｊの３次元復元がないので何もしない。
この処理を、ｐｉから伸ばす直線の方向を［−ａ０，ａ０］の範囲内で変化させながら繰り返す。反対方向−（ｄ＋ａ）にも同様の処理を行う。
最後に、各ｓｉｊに対する３次元面素線分Ｓｉｊを生成する。
【００２７】
＜可視性制約の判定＞
図７を用いて、可視性制約を説明する。
上述のように生成した面素線分の中には、本来は平面がない領域に張られた偽線分が含まれる可能性がある。これに対処するために、可視性制約を用いる。可視性制約とは、画像に写っている点とカメラ中心とを結ぶ３次元線分上には、不透明な物体は存在しないという制約である。
図７の例では、３次元点Ｐが画像上で画像エッジ点ｐとして見えているので、カメラ中心ＣとＰを結んだ３次元線分上には、不透明な物体は存在しないはずである。したがって、図７に描かれているｐｉとｐｊの間に張った面素線分ｓｉｊは偽線分である。なぜなら、ｓｉｊに対応する３次元線分がＣとＰを結んだ３次元線分上と交点Ｂで交わっており、しかも、ＢがＰよりもＣに近いため、可視性制約に反するからである。
【００２８】
画像エッジ点ｐｉとｐｊをつないだ面素線分ｓｉｊに対する可視性制約は次のように調べる。
面素成分ｓｉｊに対応する３次元面素線分をＳｉｊとする。画像エッジ点ｐｉからｐｊまでの面素線分ｓｉｊ上の各画素に対して、その位置に画像エッジ点があるかどうかを調べる。もしあれば、その画像エッジ点ｐが３次元復元されているかどうかを調べる。画像エッジ点ｐが３次元復元されていれば、その３次元エッジ点Ｐのカメラから見た奥行がＳｉｊの奥行よりも大きい場合に、面素線分ｓｉｊは偽線分と判定する。ここで、３次元面素線分Ｓｉｊの奥行は、カメラ中心ＣとＰを結ぶ直線と３次元面素成分Ｓｉｊの交点Ｂの奥行で定義する。ｐが３次元復元されていなければ何もしない。
【００２９】
＜ボクセル表現への変換＞
多くの面素線分は重複しているため、面素線分の集合で平面を構成すると冗長性が高
くなる。これに対処するため、面素線分をボクセル表現に変換する。ボクセルは微小な
立方体であり、その集合で物体を近似的に表す。ボクセルのサイズは、物体を必要な精
度で表現できる程度に小さく設定する。
まず、３次元空間をボクセル集合で分割して表す。そして、３次元面素線分から適当な間隔で３次元点Ｐをサンプリングしてボクセル集合に登録する。
具体的には、Ｐの位置に最も近い中心点をもつボクセルを求め、そのボクセルのスコアを１つ増やす。これをすべての３次元面素線分について繰り返す。そして、スコアが所定の閾値以上のボクセルだけを残す。こうすると、３次元面素線分が存在する領域のボクセルだけが残るので、物体の面情報をボクセルの集合で表すことができる。また、近くに重複して存在する面素線分上の点は１個のボクセルに統合されるので、データ量を大幅に削減することができる。
【００３０】
＜動作例＞
本発明による３次元形状モデルの生成例を図８に示す。図８−１（ａ）〜（ｄ）は、復元に用いた３０枚の画像列の一部である。図８−２（ａ）〜（ｃ）は、これらの画像から復元した３次元エッジ点群である。図８−３（ａ）〜（ｃ）は、本発明の方法により生成した面情報を含んだ３次元形状モデルである。机の上面など、比較的大きくて模様のない平面がうまく復元されていることがわかる。
他の３次元形状モデルの生成例を図９に示す。図９−１（ａ）〜（ｃ）は、復元に用いた３０枚の画像列の一部である。図９−２（ａ）〜（ｃ）は、本発明の方法により生成した面情報を含んだ３次元形状モデルである。円形の椅子がうまく復元されていることがわかる。
【００３１】
本発明は、例えば、ロボットや移動体の環境認識に用いる物体の形状モデルの生成、あるいは、ＣＡＤ、コンピュータグラフィクス、人工現実感などで用いる物体の形状モデルの生成などに利用することができる。
【図面の簡単な説明】
【００３２】
【図１】パッチ補間法の動作例を示す図である。
【図２】面素線分による形状モデル生成の概念を説明する図である。
【図３】本発明の構成要素の一例を説明する図である。
【図４】本発明の３次元形状モデル生成システムの一括処理の一実施例を示すフローチャートである。
【図５】本発明の３次元形状モデル生成システムの逐次処理の一実施例を示すフローチャートである。
【図６】面素線分の生成処理を示す図である。
【図７】可視性制約の例を示す図である。
【図８−１】本発明による３次元形状モデル生成結果の一例を示し、復元に用いた画像列の一部を示す図である。
【図８−２】本発明による３次元形状モデル生成結果の一例を示し、復元した３次元エッジ点群を示す図である。
【図８−３】本発明による３次元形状モデル生成結果の一例を示し、生成した３次元形状モデルを示す図である。
【図９−１】本発明による３次元形状モデル生成結果の他の例を示し、復元に用いた画像列を示す図である。
【図９−２】本発明による３次元形状モデル生成結果の他の例を示し、生成した３次元形状モデルを示す図である。
【図１】
0004714050.tif 000002
【図２】
0004714050.tif 000003
【図３】
0004714050.tif 000004
【図４】
0004714050.tif 000005
【図５】
0004714050.tif 000006
【図６】
0004714050.tif 000007
【図７】
0004714050.tif 000008
【図８−２】
0004714050.tif 000009
【図８−１】
0004714050.tif 000010
【図８−３】
0004714050.tif 000011
【図９−１】
0004714050.tif 000012
【図９−２】
0004714050.tif 000013