(57)【要約】【課題】撮影対象表面の正確な形状を表わす点及びテクスチャに沿う点で構成されるポリゴンとして撮影対象の３次元形状を復元する。【解決手段】視体積交差法によって生成された撮影対象のポリゴンの表面に対して前記撮影対象の多視点画像の各画像から前記撮影対象のテクスチャに基づき算出された特徴点が追加された後に前記特徴点に基づき前記ポリゴンを修正する。前記ポリゴン修正の過程は３次元形状復元装置１のポリゴン修正部６によって実行される。ポリゴン修正部６は、前記ポリゴンの修正にあたり、前記ポリゴンに追加された特徴点とその周囲の点を含む点群を３次元候補点群とし、この３次元候補点群の各点と前記算出された特徴点とのパターンマッチングによって３次元候補点を抽出した後に、この抽出した３次元候補点に近づくように前記ポリゴン上の特徴点とその近傍の点を移動させる。【選択図】図１
2009294956.tif 000002
【特許請求の範囲】
【請求項１】
視体積交差法によって生成された撮影対象のポリゴンの表面に対して前記撮影対象の多視点画像の各画像から前記撮影対象のテクスチャに基づき算出された特徴点が追加された後に前記特徴点に基づきポリゴン修正手段によって前記ポリゴンを修正する過程を有する撮影対象の３次元形状復元方法であって、
前記ポリゴン修正の過程は、前記ポリゴンに追加された特徴点とその周囲の点を含む点群を３次元候補点群とし、この３次元候補点群の各点と前記算出された特徴点とのパターンマッチングによって３次元候補点を抽出した後に、この抽出した３次元候補点に近づくように前記ポリゴン上の特徴点とその近傍の点を移動させる過程を有すること
を特徴とする３次元形状復元方法。
【請求項２】
前記ポリゴン修正の過程は、
前記ポリゴンの表面に追加された特徴点を含む撮影視線上に前記テクスチャに基づく３次元候補点群を統計的な仮説形成法によって仮説生成するステップと、
前記作成した３次元候補点群を前記撮影対象の他の撮影画像上に複数の２次元候補点として投影するステップと、
前記算出された特徴点の近傍画素と前記他の撮影画像上に投影された複数の２次元候補点の近傍画素とのパターンマッチングにより類似度の最も高い２次元候補点を抽出するステップと、
前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に、前記ポリゴンの表面に追加された特徴点に対して前記引力場に基づく前記特徴点の修正力を設定するステップと、
前記設定された特徴点の修正力によって前記特徴点を前記３次元候補点の方向に移動させるステップと
を有することを特徴とする請求項１に記載の３次元形状復元方法。
【請求項３】
前記ポリゴン修正の過程は、
前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に、前記ポリゴン上の特徴点の近傍の点であって前記２次元候補点と前記３次元候補点とを通過する前記他の撮影画像の撮影視線と前記ポリゴンとの交点に対して前記引力場に基づく前記交点の修正力を設定するステップと、
前記設定された交点の修正力により前記交点を前記３次元候補点の方向に移動させるステップを
さらに有すること
を特徴とする請求項２に記載の３次元形状復元方法。
【請求項４】
前記ポリゴン修正の過程は、
前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に、前記ポリゴン上の特徴点と交点との近傍点に対して前記引力場に基づく前記近傍点の修正力を設定するステップと、
前記設定された近傍点の修正力により前記近傍点を前記３次元候補点の方向に移動させるステップを
さらに有すること
を特徴とする請求項２または３に記載の３次元形状復元方法。
【請求項５】
撮影対象の多視点画像を取得する入力画像取得手段と、
視体積交差法によって前記撮影対象のポリゴンを作成するポリゴン生成手段と、
前記取得された多視点画像の各画像から前記撮影対象のテクスチャに基づく特徴点を算出する表面特徴抽出手段と、
前記算出された特徴点を前記ポリゴンの表面に投射し、この投射した位置に前記特徴点を追加する特徴点追加処理手段と、
前記作成されたポリゴンを前記算出された特徴点に基づき修正するポリゴン修正手段と
を備え、
前記ポリゴン修正手段は、前記ポリゴンに追加された特徴点とその周囲の点を含む点群を３次元候補点群とし、この３次元候補点群の各点と前記算出された特徴点とのパターンマッチングによって３次元候補点を抽出した後に、この抽出した３次元候補点に近づくように前記ポリゴン上の特徴点とその近傍の点を移動させることにより前記ポリゴンを修正すること
を特徴とする３次元形状復元装置。
【請求項６】
前記ポリゴン修正手段は、
前記ポリゴンの表面に追加された特徴点を含む撮影視線上に前記テクスチャに基づく３次元候補点群を統計的な仮説形成法によって仮説作成する３次元候補点群作成手段と、
前記作成された３次元候補点群を前記撮影対象の他の撮影画像上に複数の２次元候補点として投影する候補点投影手段と、
前記算出された特徴点の近傍画素と前記他の撮影画像上に投影された複数の２次元候補点の近傍画素とのパターンマッチングにより類似度の最も高い２次元候補点を抽出する特徴点評価手段と、
前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に前記ポリゴンの表面に追加された特徴点に対して前記引力場に基づく前記特徴点の修正力を設定する修正力設定手段と、
前記設定された特徴点の修正力によって前記特徴点を前記３次元候補点の方向に移動させるポリゴン最適化手段と
を備えることを特徴とする請求項５に記載の３次元形状復元装置。
【請求項７】
前記修正力設定手段は、前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に、前記ポリゴン上の特徴点の近傍の点であって前記２次元候補点と前記３次元候補点とを通過する前記他の撮影画像の撮影視線と前記ポリゴンとの交点に対して前記引力場に基づく前記交点の修正力を設定し、
前記ポリゴン最適化手段は、前記設定された交点の修正力により前記交点を前記３次元候補点の方向に移動させること
を特徴とする請求項６に記載の３次元形状復元装置。
【請求項８】
前記修正力設定手段は、前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に前記ポリゴン上の特徴点と交点との近傍点に対して前記引力場に基づく前記近傍点の修正力を設定し、
前記ポリゴン最適化手段は、前記設定された近傍点の修正力により前記近傍点を前記３次元候補点の方向に移動させること
を特徴とする請求項６または７に記載の３次元形状復元装置。
【請求項９】
請求項５から８のいずれか１項に記載の３次元形状復元装置を構成する各手段としてコンピュータを機能させることを特徴とするプログラム。
【請求項１０】
請求項９に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は多視点マルチカメラを用いてカメラ画像から被写体の３次元形状を復元する技術に関する。
【背景技術】
【０００２】
撮影対象の３次元表面の幾何構造を記述する技術は、３次元計測や、ＣＧ作成の分野で多くの研究が行われている。表面の幾何構造を記述する技術は、３次元計測や、ＣＧ作成の分野で多くの研究が行われている。幾何構造の記述にはポリゴン表現がよく用いられている。
【０００３】
ポリゴンは対象の表面形状を現しているが、ポリゴンの面が表面に一致していることに加え、ポリゴンの頂点やエッジの位置が対象の表面テクスチャの特徴点やエッジと一致している場合、すなわち、対象表面のテクスチャに沿うポリゴンを計算することはさまざまなメリットがある。
【０００４】
例えば、ポリゴンが表面テクスチャの特徴と一致していれば、ポリゴンの面毎に色や反射特性などを解析することや、色や反射特性を修正することが容易となり、解析やレンダリングがしやすくなる。
【０００５】
実世界の対象からこのようなテクスチャに沿うポリゴンを獲得するためには、まず３次元形状を復元し、次に復元した形状がテクスチャに沿うように修正するのが一般的である。
【０００６】
３次元形状を復元する方法としては、視体積交差法が知られている。図６（ａ）〜図６（ｃ）は視体積交差法の原理を説明した斜視図である。
【０００７】
図６（ａ）に示されたＯは撮影対象、ＰＡはカメラの投影中心、ＳＰはカメラの撮像面、ＤＡはカメラの撮像面ＳＰ上で求められた２次元シルエットである。
【０００８】
図６（ｂ）に示されたＶＡは視体積（Ｖｉｓｕａｌ Ｃｏｎｅ）と呼ばれ、カメラの投影中心ＰＡから２次元シルエットＤＡの輪郭上の各点を通すように３次元空間中に広がる錐体であり、この場合、視体積ＰＡと２次元シルエットＤＡを用いて構成されている。Ｆ１、Ｆ２は視体積を構成する面（Ｆａｃｅ）と呼ばれ、それぞれＶｉｓｕａｌ Ｃｏｎｅのある一面を示す。
【０００９】
図６（ｃ）に示された視体積ＶＡ，ＶＢは２つのカメラすなわち投影中心ＰＡ，ＰＢから得られたＶｉｓｕａｌ Ｃｏｎｅである。ＶＨは視体積の交差領域（ＶＨ：Ｖｉｓｕａｌ Ｈｕｌｌ）である。複数のＶｉｓｕａｌ Ｃｏｎｅ（視体積ＶＡ、視体積ＶＢ）の交差領域を求めることによって得られたものが対象の３次元形状となっている。
【００１０】
視体積交差法は複数のカメラから得られた画像を用いてカメラの共通視野内の対象を復元する方法である。具体的には視体積の交差領域をボクセル投影によって復元する方法や投影した視体積の面同士の幾何計算によって前記交差領域を算出する方法がある。
【００１１】
例えば非特許文献１に記載の復元方法はボクセル投影を用いた方法である。この方法は復元範囲となる３次元空間の各ボクセルを全てのカメラの画像面に投影して評価することで、ボクセル内に対象があるか否かを決定する方法を用いて対象の視体積の交差を点群で復元する。この方法では対象の形状を数ｍｍ〜数ｃｍの均一な密度で復元する方法を用いており、視体積の交差は膨大な数の点で表現される。ポリゴンを得るためには、点群−ポリゴン変数処理によって点群をポリゴンへ変換する。点群−ポリゴン変換処理としては例えば離散マーチングキューブ法が用いられている。
【００１２】
元の点群が膨大な数の点で表現されているため変換したポリゴンも膨大な数の点数で表現される密なメッシュとなる。
【００１３】
また、非特許文献２に記載の復元方法はＰＶＨ（ｐｏｌｙｈｅｄｒａｌ ｖｉｓｕａｌ ｈｕｌｌｓ）法と呼ばれる方法である。この方法は、視体積を２次元の原画像面に投影し、２次元画像上で視体積の交差面を計算して、それを視体積に逆投影することで、視体積の交差をポリゴンで復元する。この方法では疎な点数で表現される粗いポリゴンが得られる。
【非特許文献１】延原章平，和田俊和，松山隆司，”弾性メッシュモデルを用いた多視点画像からの高精度３次元形状復元”，情報処理学会ＣＶＩＭ研究会論文誌，Ｖｏｌ．４３，ＳＩＧ１１（ＣＶＩＭ５），ｐｐ．５３−６３，２００２
【非特許文献２】Ｍａｔｕｓｉｋ，Ｗ．，Ｃ．Ｂｕｅｈｌｅｒ，ａｎｄ Ｌ．ＭｃＭｉｌｌａｎ，”Ｐｏｌｙｈｅｄｒａｌ Ｖｉｓｕａｌ Ｈｕｌｌｓ ｆｏｒ Ｒｅａｌ−Ｔｉｍｅ Ｒｅｎｄｅｒｉｎｇ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｔｗｅｌｆｔｈ Ｅｕｒｏｇｒａｐｈｉｃｓ Ｗｏｒｋｓｈｏｐ ｏｎ Ｒｅｎｄｅｒｉｎｇ，Ｌｏｎｄｏｎ，Ｅｎｇｌａｎｄ，Ｊｕｎｅ ２００１，ｐｐ．１１５−１２６．
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、上記いずれの復元方法では、視体積の交差領域は、多くの場合、原理上凹の面を復元できないことと、カメラ台数に応じた概形であることから、実際の対象の表面からずれた位置にあり、対象の形状を正確に表すことができない。すなわち、視体積を構成する３次元点は、実際の対象の表面からはずれていることと、テクスチャと無関係であるという２つの問題がある。
【課題を解決するための手段】
【００１５】
そこで、前記課題を解決するための３次元形状復元方法とその装置、プログラム及び記録媒体は、ポリゴン面上にテクスチャと関連する特徴点を追加し、この特徴点に基づきポリゴンを修正する。
【００１６】
すなわち、請求項１の３次元形状復元方法は、視体積交差法によって生成された撮影対象のポリゴンの表面に対して前記撮影対象の多視点画像の各画像から前記撮影対象のテクスチャに基づき算出された特徴点が追加された後に前記特徴点に基づきポリゴン修正手段によって前記ポリゴンを修正する過程を有する撮影対象の３次元形状復元方法であって、前記ポリゴン修正の過程は、前記ポリゴンに追加された特徴点とその周囲の点を含む点群を３次元候補点群とし、この３次元候補点群の各点と前記算出された特徴点とのパターンマッチングによって３次元候補点を抽出した後に、この抽出した３次元候補点に近づくように前記ポリゴン上の特徴点とその近傍の点を移動させる過程を有する。
【００１７】
請求項２の３次元形状復元方法は、請求項１の３次元形状復元方法において、前記ポリゴン修正の過程は、前記ポリゴンの表面に追加された特徴点を含む撮影視線上に前記テクスチャに基づく３次元候補点群を統計的な仮説形成法によって仮説生成するステップと、前記作成した３次元候補点群を前記撮影対象の他の撮影画像上に複数の２次元候補点として投影するステップと、前記算出された特徴点の近傍画素と前記他の撮影画像上に投影された複数の２次元候補点の近傍画素とのパターンマッチングにより類似度の最も高い２次元候補点を抽出するステップと、前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に、前記ポリゴンの表面に追加された特徴点に対して前記引力場に基づく前記特徴点の修正力を設定するステップと、前記設定された特徴点の修正力によって前記特徴点を前記３次元候補点の方向に移動させるステップを有する。
【００１８】
請求項３の３次元形状復元方法は、請求項２の３次元形状復元方法において、前記ポリゴン修正の過程は、前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に、前記ポリゴン上の特徴点の近傍の点であって前記２次元候補点と前記３次元候補点とを通過する前記他の撮影画像の撮影視線と前記ポリゴンとの交点に対して前記引力場に基づく前記交点の修正力を設定するステップと、前記設定された交点の修正力により前記交点を前記３次元候補点の方向に移動させるステップをさらに有する。
【００１９】
請求項４の３次元形状復元方法は、請求項２または３の３次元形状復元方法において、前記ポリゴン修正の過程は、前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に、前記ポリゴン上の特徴点と交点との近傍点に対して前記引力場に基づく前記近傍点の修正力を設定するステップと、前記設定された近傍点の修正力により前記近傍点を前記３次元候補点の方向に移動させるステップをさらに有する。
【００２０】
請求項５の３次元形状復元装置は、撮影対象の多視点画像を取得する入力画像取得手段と、視体積交差法によって前記撮影対象のポリゴンを作成するポリゴン生成手段と、前記取得された多視点画像の各画像から前記撮影対象のテクスチャに基づく特徴点を算出する表面特徴抽出手段と、前記算出された特徴点を前記ポリゴンの表面に投射し、この投射した位置に前記特徴点を追加する特徴点追加処理手段と、前記作成されたポリゴンを前記算出された特徴点に基づき修正するポリゴン修正手段とを備え、前記ポリゴン修正手段は、前記ポリゴンに追加された特徴点とその周囲の点を含む点群を３次元候補点群とし、この３次元候補点群の各点と前記算出された特徴点とのパターンマッチングによって３次元候補点を抽出した後に、この抽出した３次元候補点に近づくように前記ポリゴン上の特徴点とその近傍の点を移動させることにより前記ポリゴンを修正する。
【００２１】
請求項６の３次元形状復元装置は、請求項５の３次元形状復元装置において、前記ポリゴン修正手段は、前記ポリゴンの表面に追加された特徴点を含む撮影視線上に前記テクスチャに基づく３次元候補点群を統計的な仮説形成法によって仮説作成する３次元候補点群作成手段と、前記作成された３次元候補点群を前記撮影対象の他の撮影画像上に複数の２次元候補点として投影する候補点投影手段と、前記算出された特徴点の近傍画素と前記他の撮影画像上に投影された複数の２次元候補点の近傍画素とのパターンマッチングにより類似度の最も高い２次元候補点を抽出する特徴点評価手段と、前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に前記ポリゴンの表面に追加された特徴点に対して前記引力場に基づく前記特徴点の修正力を設定する修正力設定手段と、前記設定された特徴点の修正力によって前記特徴点を前記３次元候補点の方向に移動させるポリゴン最適化手段とを備える。
【００２２】
請求項７の３次元形状復元装置は、請求項６の３次元形状復元装置において、前記修正力設定手段は、前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に、前記ポリゴン上の特徴点の近傍の点であって前記２次元候補点と前記３次元候補点とを通過する前記他の撮影画像の撮影視線と前記ポリゴンとの交点に対して前記引力場に基づく前記交点の修正力を設定し、前記ポリゴン最適化手段は、前記設定された交点の修正力により前記交点を前記３次元候補点の方向に移動させる。
【００２３】
請求項８の３次元形状復元装置は、請求項６または７の３次元形状復元装置において、前記修正力設定手段は、前記抽出された２次元候補点に対応した前記３次元候補点群中の３次元候補点に引力場を設定した後に前記ポリゴン上の特徴点と交点との近傍点に対して前記引力場に基づく前記近傍点の修正力を設定し、前記ポリゴン最適化手段は、前記設定された近傍点の修正力により前記近傍点を前記３次元候補点の方向に移動させる。
【００２４】
請求項９のプログラムは、請求項５から８のいずれかの３次元形状復元装置を構成する各手段としてコンピュータを機能させるプログラムである。
【００２５】
請求項１０の記録媒体は、請求項９のプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００２６】
したがって、以上の発明によれば、撮影対象の表面の正確な形状を表わす点及びテクスチャに沿う点で構成されるポリゴンとして撮影対象の３次元形状を復元することができる。
【発明を実施するための最良の形態】
【００２７】
図１は発明の実施形態に係る３次元形状復元装置１の概略構成図である。
【００２８】
３次元形状復元装置１は入力画像取得部２とポリゴン生成部３と表面特徴抽出部４と特徴点追加処理部５とポリゴン修正部６を備える。
【００２９】
３次元形状復元装置１は通常のコンピュータの構成要素、例えばＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｏｒ Ｕｎｉｔ）、メモリ（ＲＡＭ）、ハードディスクドライブ装置、通信デバイスなどのハートウェア資源を備え、このハードウェア資源とインストール済みのソフトウェアとの協働によって前記各機能ブロック２〜６に係る処理が実行される。そして、この処理によって得られた画像はディスプイ（表示装置）にて表示できるようになっている。
【００３０】
入力画像取得部２は多視点撮影された撮影対象の画像を入力画像取得処理により取得する。前記入力画像取得処理はカメラまたはハードディスクなどの記憶媒体から前記画像を読み込む処理である。前記多視点撮影された画像は全てのカメラにおいて対象が含まれる共有視野を持つように配置されたカメラ（多視点マルチカメラ）で撮影したものとする。前記画像は同期撮影により獲得されたものであることが望ましい。尚、入力画像取得部２は前記通信デバイスなどで実現してもよい。
【００３１】
ポリゴン生成部３は入力画像取得部２で取得された画像を前記ＰＨＶ法により処理することにより撮影対象のポリゴン形状を計算する。ＰＶＨ法は原理上高速なポリゴン計算が可能であるが、前記ボクセル投影を用いる方法と点群−ポリゴン変換を用いて対象のポリゴン形状の算出を行なってもよい。
【００３２】
表面特徴抽出部４は入力画像取得部２で取得された画像から表面特徴抽出処理によって前記画像に含まれる対象のテクスチャ上の特徴を抽出する。表面特徴抽出処理は前記画像に対してコーナー検出法によって特徴点を計算する。前記コーナー検出法は既知の方法を適用すればよい。その他、特徴点抽出方法やエッジ抽出方法など画像処理技術で一般的に広く用いられている既知の抽出法を用いてもよい。
【００３３】
特徴点追加処理部５はポリゴン生成部３で生成したポリゴンの表面に対して表面特徴抽出部４で算出した特徴点を特徴点追加処理によって追加する。特徴点追加処理は表面特徴抽出部４で算出した特徴点をポリゴン生成部３で生成したポリゴンの表面に投影することで３次元特徴点を追加したポリゴンを得る。ここで、投影された３次元特徴点を含めたポリゴンを計算するために、投影された３次元特徴点に基づきポリゴンを分割してもよい。ポリゴン面の分割は三角形分割の方法として知られるドロネー分割を用いる。その他、一般的な幾何計算で用いられる多角形分割方法を用いてもよい。
【００３４】
ポリゴン修正部６は特徴点追加処理部５で３次元特徴点が追加されたポリゴンを修正処理することで撮影対象のテクスチャに沿い且つより正確な形状になるようにポリゴンを修正する。具体的には、前記ポリゴンに追加された３次元特徴点とその周囲の点を含む点群を３次元候補点群とし、この３次元候補点群の各点と前記算出された特徴点とのパターンマッチングによって３次元候補点を抽出している。そして、この抽出した３次元候補点に近づくように前記ポリゴン上の３次元特徴点とその近傍の点を移動させることにより前記ポリゴンを修正する。
【００３５】
図２はポリゴン修正部６の概略構成を示したブロック図である。ポリゴン修正部６は３次元候補点群作成部１１と候補点投影部１２と特徴点評価部１３と修正力設定部１４とポリゴン最適化部１５を備える。
【００３６】
３次元候補点群作成部１１は、特徴点追加処理部５によりポリゴンに追加された特徴点（３次元特徴点）の周囲に一般的な確率統計に基づく仮説生成方法を用いて複数の３次元候補点から成る３次元候補点群を生成する。例えば、表面特徴抽出部４で算出した特徴点を投影した際のカメラの視線上に視線と特徴点を拘束条件として一定範囲内にランダムに候補点を生成するなどの方法を採ることができる。
【００３７】
候補点投影部１２は、３次元候補点群作成部１１で生成された３次元候補点群を投影計算によって他のスクリーン（撮像面）に投影することにより、前記ポリゴンの生成に供されている各スクリーン上に前記３次元候補点に対応した２次元候補点群を算出する。
【００３８】
特徴点評価部１３は、候補点投影部１２によって算出された２次元候補点群の近傍画素をスクリーン上で探索し、パターンマッチングにより特徴点追加元の近傍画素との類似度を計算し、類似度を比較することにより類似度の高い点を抽出する。
【００３９】
修正力設定部１４は、特徴点評価部１３によって計算された類似度に基づき抽出された３次元候補点に引力場を設定し、Ｖｉｓｕａｌ Ｈｕｌｌ上における３次元候補点またはその近傍点について、この候補点またはその近傍点に向かって動く修正力を設定する。修正力のベクトルの大きさはＶｉｓｕａｌ Ｈｕｌｌ上の近傍点から３次元候補点までの距離に応じた値によって定まる。また、複数の候補点からの修正力がある場合は、それらの修正力を加算する。
【００４０】
ポリゴン最適化部１５は、修正力設定部１４によって設定した修正力に従って、Ｖｉｓｕａｌ Ｈｕｌｌを構成する各ポリゴン上の点（例えば前記追加された特徴点またはこの近傍の頂点若しくはこれらの近傍点）の位置を移動させることにより、最適化されたポリゴンを算出する。
【００４１】
前記点の移動距離は修正力のベクトルの大きさに応じて決定する。ここで、移動した点が別の面と衝突するかどうかの判定を行い衝突する場合は、移動をしないか移動距離を衝突しない範囲にとどまるように短くすることで、特定の点が別の面にめり込むなどの不整合を回避する。移動に従って極めて距離の近くなった隣接点については、点を統合してポリゴンを再構成してもよい。
【００４２】
この処理は，終了条件を満たすまで反復計算してもよい。終了条件は、指定回数まで繰り返し、あるいは、反復計算によるポリゴン頂点の位置変化が一定値以下というような収束条件を用いればよい。終了判定は終了条件を満たすかどうか判定することで実現できる。
【００４３】
図３及び図４を参照しながらポリゴン修正の具体的な手順について説明する。
【００４４】
図３（ａ）は特徴点ＦＰ２Ｄと３次元候補点群ＣＰと２次元候補点ＭＦＰ２Ｄの位置関係の説明図である。図３（ａ）に示された符号について説明する。
【００４５】
Ｏは撮影対象、ＶＰ１、ＶＰ２は多視点マルチカメラのうち隣接したカメラの投影中心、Ｓ１、Ｓ２は前記隣接した二つのカメラの撮像面（以下、スクリーンと称する）である。ＶＨは撮影対象Ｏの視体積の一部を示している。ＶＨＰは前記視体積の一部ＶＨを表わすポリゴン上の点であり、この時点においては撮影対象Ｏの表面上のテクスチャ特徴点とは無関係の点である。
【００４６】
ＦＰ２Ｄは、前記特徴抽出処理によって算出された特徴点であり、図示された事例ではスクリーンＳ１上で得られた撮影対象Ｏの画像上の特徴点である。
【００４７】
ＶＲ１は投影中心ＶＰ１から特徴点ＦＰ２Ｄを通る視線である。ＦＰ３Ｄは、前記特徴点追加処理によって前記視体積の一部ＶＨ上に追加された３次元特徴点である。この３次元特徴点は、視線ＶＲ１と前記視体積の一部ＶＨとの交点を計算することで得られる３次元点である。
【００４８】
ＣＰは、対象表面の正確な形状を表わす点且つテクスチャに沿う点の候補点群であり、３次元特徴点ＦＰ３Ｄと視線ＶＲ１を基準に生成した３次元候補点群である。３次元候補点群ＣＰの生成は、前述のように３次元特徴点ＦＰ３Ｄと視線ＶＲ１を拘束条件として用いて一般的な確率統計に基づく仮説生成方法を用いることができる。例えばパーティクルフィルタなどを用いてもよい。
【００４９】
ＰＣＰは、３次元候補点群ＣＰをスクリーンＳ１に隣接したスクリーンＳ２に係る投影中心ＶＰ２に向かって投影して得られたスクリーンＳ２上の２次元候補点群である。
【００５０】
ＭＦＰ２Ｄは、スクリーンＳ２上に得られた撮影対象Ｏの画像上において特徴点ＦＰ２Ｄと２次元候補点群ＰＣＰとの関係性を評価し最も一致する点を求めることで得られる２次元候補点である。２次元候補点ＭＦＰ２Ｄは一般的なパターンマッチングの方法、最適化アルゴリズムを用いて求めることできる。スクリーンＳ２上に求められた撮影対象Ｏの画像上で、候補点群ＰＣＰの各点の近傍画素を走査してマッチングをとってもよいし、予めスクリーンＳ２上で計算しておいた撮影対象Ｏの特徴点とマッチングをとってもよい。
【００５１】
ＭＦＰ３Ｄは、撮影中心ＶＰ２と２次元候補点ＭＦＰ２Ｄを通る視線と前記視体積の一部ＶＨの交点を計算することで得られる３次元点である。
【００５２】
ＴＰは、前記パターンマッチングの結果、真値となった点であり、２次元候補点ＭＦＰ２Ｄに対応した３次元候補点群ＣＰのうちの３次元候補点である。ＴＰは対象表面の正確な形状を表わす点且つテクスチャに沿う点である。
【００５３】
図３（ｂ）は修正力Ｆ１、Ｆ２、Ｆ３による３次元特徴点ＦＰ３Ｄ、交点ＭＦＰ３Ｄ、視体積の一部ＶＨ上の点（ポリゴン上の点）ＶＨＰの修正の説明図である。図３（ｂ）に示された符号について説明する。
【００５４】
ＶＲ２はカメラの投影中心ＶＰ２からスクリーンＳ２を介して３次元点ＭＦＰ３Ｄを通る視線である。また、同図には視体積の一部ＶＨ上の各点が３次元候補点ＴＰに近づくように修正する力を各点が示されている。３次元候補点ＴＰを基準とし３次元特徴点ＦＰ３Ｄ、交点ＭＦＰ３Ｄ及びその近傍の点（例えば点ＶＨＰ）について修正力を生成するとＦ１〜Ｆ３で示した修正力が得られる。修正力Ｆ１は３次元特徴点ＦＰ３Ｄから３次元候補点ＴＰの方向へ働く力である。修正力Ｆ２は３次元点ＭＦＰ３Ｄから３次元候補点ＴＰ方向へ働く力である。修正力Ｆ３は点ＶＨＰから点ＴＰの方向へ働く力である。
【００５５】
図４はポリゴン修正部６によって実行されるポリゴン修正処理の過程における３次元候補点の作成とその評価の手順を説明したフローチャートである。図３を参照しながら前記フローチャートについて説明する。
【００５６】
Ｓ２１：ポリゴン修正部６が特徴点追加処理部５にてＶｉｓｕａｌ Ｈｕｌｌ上に追加された全ての特徴点について修正の処理を順次行う命令を受ける。
【００５７】
Ｓ２２：前述の３次元候補点群作成部１１の機能に対応したステップである。すなわち、特徴点を投影した際の視線上に３次元候補点群を生成する処理である。例えば図３（ａ）を参照すると、視線ＶＲ１とスクリーンＳ１上の特徴点ＦＰ２Ｄを拘束条件として、一般的な確率統計に基づく仮説生成方法を用いて３次元特徴点ＦＰ３Ｄ特徴点の周囲に３次元候補点群ＣＰを生成する。
【００５８】
Ｓ２３：特徴点追加元のスクリーンを除く全てのスクリーンに繰り返しを行う処理である。図３（ａ）の事例ではＶｉｓｕａｌ Ｈｕｌｌの形成に供されているスクリーンＳ１（３次元特徴点ＦＰ３Ｄ追加元）以外の全てのスクリーンに係る撮影視線及び特徴点を拘束条件としてＳ２２と同様に３次元候補点群を順次生成する。
【００５９】
Ｓ２４：前述の候補点投影部１２の機能に対応した処理ステップである。候補点群ＣＰをスクリーンＳ２に投影することで、スクリーンＳ２上に２次元候補点群ＰＣＰを得る。
【００６０】
Ｓ２５〜Ｓ２８は前述の特徴点評価部１３の機能に対応した処理である。
【００６１】
Ｓ２５：前記投影された２次元候補点群の近傍画素をスクリーン上で探索し、３次元特徴点追加元の近傍画素との類似度をパターンマッチング法によって計算する。図３（ａ）の事例では、投影された２次元候補点群ＰＣＰの近傍画素をスクリーンＳ２上で探索し、３次元特徴点ＦＰ３Ｄ追加元であるスクリーンＳ１上の特徴点ＦＰ２Ｄの近傍画素との類似度をパターンマッチング法によって計算する。
【００６２】
Ｓ２６：撮影対象（図３の事例では撮影対象Ｏ）を撮影に供されている全てのカメラのスクリーン上の２次元候補点群について順次パターンマッチング処理の終了が判定する処理が実行される。
【００６３】
Ｓ２７：投影された２次元候補点群についてＳ２５で求めた類似度が閾値を越える点があるかどうか判定する。図３（ａ）の事例ではスクリーンＳ１上の特徴点ＦＰ２Ｄの近傍画素とスクリーンＳ２上の２次元候補点群ＰＣＰの近傍画素との類似度が閾値を越える点があるかどうかが判定される。そして、判定結果が真（ＹＥＳ）の場合はＳ２８へ進む。一方、判定結果が偽（ＮＯ）の場合はＳ２９へ進む。尚、前記閾値はユーザによって任意に設定される。
【００６４】
Ｓ２８：前記類似度の評価を行う。図３（ａ）の事例では投影された２次元候補点群ＰＣＰのうち類似度が閾値を越える点を比較し、類似度の最も高い点を算出する。
【００６５】
Ｓ２９：Ｖｉｓｕａｌ Ｈｕｌｌ上に追加された全ての特徴点とＶｉｓｕａｌ Ｈｕｌｌの形成に供されている全てのスクリーン上の２次元候補点群の近傍画素との類似度の評価が実行されたことが判定される。
【００６６】
図５はＳ２１〜Ｓ２９によって計算された前記類似度の高い候補点を用いてポリゴンを修正する具体的な手順を説明したフローチャートである。
【００６７】
Ｓ３１：Ｓ２１〜Ｓ２９の過程で計算された前記類似度の高い候補点を用いてＶｉｓｕａｌ Ｈｕｌｌを構成する全てのポリゴン頂点の修正を順次実行する命令を修正力設定部１４が受ける。
【００６８】
Ｓ３２：修正力設定部１４が前述の機能原理によってポリゴン上の頂点に修正力を設定する。図３（ｂ）の事例では３次元特徴点ＦＰ３Ｄ、交点ＭＦＰ３Ｄ及びその近傍の点ＶＨＰに対してそれぞれ修正力Ｆ１、Ｆ２、Ｆ３が設定される。
【００６９】
Ｓ３３：Ｖｉｓｕａｌ Ｈｕｌｌを構成する全てのポリゴン頂点についてＳ３２と同様の方法で修正力が順次設定される処理が実行され、その処理の終了が判定される。
【００７０】
Ｓ３４：ポリゴン最適化部１５が前述の機能原理によって全てのポリゴン頂点の位置を移動させる。すなわち、Ｓ３２、Ｓ３３の過程で設定された修正力によって前記ポリゴン頂点の位置を移動させる。
【００７１】
Ｓ３５：ポリゴン最適化部１５が前記の機能によってポリゴン修正計算の終了判定（ＹＥＳ，ＮＯ）を行う。すなわち、修正力が設定された全てのポリゴン頂点について修正が終了されたことの判定が行われる。そして、全てのポリゴン頂点の終了が判定される（ＹＥＳ）までＳ３１〜Ｓ３５のステップを繰り返す。
【００７２】
以上のように対象のＶｉｓｕａｌ Ｈｕｌｌを構成するポリゴン頂点を対象表面の正確な形状を表わす点且つテクスチャに沿う点となるように修正されたポリゴンが得られる。尚、以上の処理はディスプレイに表示させながら行ってもよい。
【００７３】
以上の説明から明らかなように３次元形状復元装置１によれば視体積交差法で得られたポリゴンをステレオマッチング法による撮影対象表面の推定位置へ近づける修正を行うことで従来法に比べて凹面の復元ができ、撮影対象の形状を正確に得ることができる。また、ポリゴンの修正においてはテクスチャを使用した特徴点を基にポリゴンの頂点を移動しているので、テクスチャとして矛盾のない撮影対象の形状を得ることができる。
【００７４】
本発明は、上記の実施形態に限定されるものでなく、３次元形状復元装置１を構成する入力画像取得部２、ポリゴン生成部３、表面特徴抽出部４、特徴点追加処理部５及びポリゴン修正部６（３次元候補点群作成部１１、候補点投影部１２、特徴点評価部１３、修正力設定部１４、ポリゴン最適化部１５）としてコンピュータを機能させるプログラムの態様としてもよい。前記プログラムはコンピュータ読み取り可能な既知の記録媒体に格納して提供またはネットワークを通じて提供することもできる。
【図面の簡単な説明】
【００７５】
【図１】発明の実施形態に係る３次元形状復元装置の概略構成図。
【図２】発明の実施形態に係るポリゴン修正部の概略構成を示したブロック図。
【図３】（ａ）特徴点ＦＰ２Ｄと３次元候補点群ＣＰと２次元候補点ＭＦＰ２Ｄの位置関係の説明図、（ｂ）修正力Ｆ１、Ｆ２、Ｆ３による３次元特徴点ＦＰ３Ｄ、交点ＭＦＰ３Ｄ、視体積の一部ＶＨ上の点（ポリゴン上の点）ＶＨＰの修正の説明図。
【図４】発明の実施形態に係るポリゴン修正処理にあたり３次元候補点の作成とその評価の手順を説明したフローチャート。
【図５】発明の実施形態に係るポリゴン修正処理の手順を説明したフローチャート。
【図６】（ａ）カメラの投影中心ＰＡとカメラの撮像面ＳＰと撮影対象Ｏとの位置関係を示した斜視図、（ｂ）カメラの投影中心ＰＡとカメラの撮像面ＳＰと撮影対象Ｏとによって形成された視体積（Ｖｉｓｕａｌ Ｃｏｎｅ）の斜視図、（ｃ）視体積ＶＡと視体積ＶＢとの交差領域（Ｖｉｓｕａｌ Ｈｕｌｌ）の斜視図。
【符号の説明】
【００７６】
１…３次元形状復元装置
２…入力画像取得部（入力画像取得手段）
３…ポリゴン生成部（ポリゴン生成手段）
４…表面特徴抽出部（表面特徴抽出手段）
５…特徴点追加処理部（特徴点追加処理手段）
６…ポリゴン修正部（ポリゴン修正手段）
１１…３次元候補点群作成部（３次元候補点群作成手段）
１２…候補点投影部（候補点投影手段）
１３…特徴点評価部（特徴点評価手段）
１４…修正力設定部（修正力設定手段）
１５…ポリゴン最適化部（ポリゴン最適化手段）
Ｏ…撮影対象
ＶＰ１、ＶＰ２…投影中心
Ｓ１、Ｓ２…スクリーン（撮像面）
ＶＨ…撮影対象Ｏの視体積の一部
ＦＰ２Ｄ…撮影対象ＯのスクリーンＳ１上の特徴点
ＦＰ３Ｄ…視体積の一部ＶＨ上に追加された３次元特徴点
ＶＲ１…特徴点ＦＰ２Ｄを通る投影中心ＶＰ１からの視線
ＣＰ…３次元候補点群
ＰＣＰ…３次元候補点群ＣＰに基づくスクリーンＳ２上の２次元候補点群
ＭＦＰ２Ｄ…２次元候補点群ＰＣＰから抽出された２次元候補点
ＴＰ…２次元候補点ＭＦＰ２Ｄに対応した３次元候補点群ＣＰ中の３次元候補点
ＶＲ２…２次元候補点ＭＦＰ２Ｄと３次元候補点ＴＰとを通過する投影中心ＶＰ２からの視線
ＭＦＰ３Ｄ…視線ＶＲ２と視体積の一部ＶＨの交点（３次元点）
ＶＨＰ…３次元特徴点ＦＰ３Ｄ及び交点ＭＦＰ３Ｄに近傍する視体積の一部ＶＨ上の点
Ｆ１…３次元特徴点ＦＰ３Ｄから３次元候補点ＴＰの方向へ働く修正力
Ｆ２…交点ＭＦＰ３Ｄから３次元候補点ＴＰ方向へ働く修正力
Ｆ３…点ＶＨＰから点ＴＰの方向へ働く修正力
【図１】
2009294956.tif 000003
【図２】
2009294956.tif 000004
【図３】
2009294956.tif 000005
【図４】
2009294956.tif 000006
【図５】
2009294956.tif 000007
【図６】
2009294956.tif 000008