(57)【要約】      （修正有）【課題】被写体の薄い部分が良好に再現されると共に視体積交差法を適用して得られる３次元形状を大きく崩すことなく被写体の３次元形状を良好に再現する。【解決手段】多視点カメラ画像からシルエット画像を生成する手段２と、生成されたシルエット画像について視体積交差法を適用し、被写体の近似された３次元形状モデルである各種ソリッドモデルを生成する手段３と、カメラ画像間の相互相関値を演算する手段３０と、生成されたソリッドモデルについて相互相関値を用いて最大フロー／最小カットアルゴリズムを適用して被写体の３次元形状モデルを生成する手段４０とを具える。さらに、シルエット画像とソリッドモデルとに基づいてシルエット拘束値を生成する手段１０から出力される値を用いて相互相関値に対して重み付けを行い、重み付けされた相互相関値を用いて最大フロー／最小カット演算を行う。【選択図】図１
2010121945.tif 000002
【特許請求の範囲】
【請求項１】
被写体を複数の角度方向から撮像した多視点カメラ画像から被写体の３次元形状モデルを生成する３次元形状生成装置であって、
多視点カメラ画像からシルエット画像を生成するシルエット画像生成手段と、
生成されたシルエット画像について視体積交差法を適用し、被写体の近似された３次元形状モデルである各種ソリッドモデルを生成するソリッドモデル生成手段と、
前記シルエット画像とソリッドモデルとに基づいてシルエット拘束値を生成するシルエット拘束情報生成手段と、
前記ソリッドモデルを用いて、被写体表面を可視的に撮像したカメラを各頂点毎に特定する可視カメラ情報生成手段と、
前記特定されたカメラにより撮像されたカメラ画像間の相互相関値を演算する相互相関値演算手段と、
前記生成されたシルエット拘束値を用いて、演算された相互相関値について重み付けを行い、重み付けされた相互相関値を出力する手段と、
前記ソリッドモデルについて、表面頂点に対応するノードと、隣接するノード間を接続するエッジとから構成されるグラフを形成し、前記重み付けされた相互相関値を用いて最大フロー／最小カットアルゴリズムを適用して被写体の３次元形状モデルを生成する最大フロー／最小カット演算手段とを具えることを特徴とする３次元形状生成装置。    
【請求項２】
請求項１に記載の３次元形状生成装置において、前記ソリッドモデル生成手段は、シルエット画像に視体積交差法を適用することにより形成される第１のソリッドモデルと、第１のソリッドモデルにエロージョン処理を行うことにより得られる第２のソリッドモデルと、第１のソリッドモデルにダイレーション処理を行うことにより得られる第３のソリッドモデルと、第１のソリッドモデルに適応的エロージョン処理を行うことにより得られる第４のソリッドモデルとを生成し、
前記最大フロー／最小カット演算手段は、第４のソリッドモデルの表面と第３のソリッドモデルの表面との間に形成される領域について最大フロー／最小カットアルゴリズムを適用し、エネルギーの総和が最小となる頂点群を求めて３次元形状モデルを生成することを特徴とする３次元形状生成装置。
【請求項３】
請求項２に記載の３次元形状生成装置において、前記シルエット拘束情報生成手段は、前記第３のソリッドモデルの表面頂点を各シルエット画像上に投影し、被写体シルエットと背景との境界点であるシルエット端を検出し、シルエット端を形成するシルエット画像と関連するカメラの数を用いてシルエット拘束値を生成することを特徴とする３次元形状生成装置。
【請求項４】
請求項２又は３に記載の３次元形状生成装置において、前記相互相関値演算手段は、カメラ画像の輝度信号を用いて相互相関値を計算すると共に、ＲＧＢの各色成分についても相互相関値を計算し、色成分から得た相互相関値を用いて重み付け加算することを特徴とする３次元形状生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、被写体の多視点画像から３次元形状モデルを生成する３次元形状生成装置に関するものである。
【背景技術】
【０００２】
被写体の多視点画像から３次元形状を生成する方法として、視体積交差法により得られる近似形状を初期形状とし、得られた初期形状について補正を行う方法が既知である。補正手法として、複数のステレオ画像対を用いて対応点探索を行う手法（例えば、非特許文献１参照）、あるいは初期形状の表面頂点を複数のカメラ画像に投影し、その対応度に応じて頂点位置を補正する手法（例えば、非特許文献２参照）が知られている。また、別の補正方法として、最大フロー／最小カットアルゴリズムを用いて初期形状を補正する方法が注目されている。最大フロー／最小カットアルゴリズムは、ネットワーク中の離れた２つのノード間の通信容量の最小値を求めることにより最大フローの計算が行われている。このアルゴリズムを画像処理に応用する場合、例えばノードを画素に対応させ、隣接するノード間を接続するエッジを画素間の相関エネルギーなどに置き換えることにより、領域分割処理に応用することができる。このアルゴリズムでは、ノードとエッジにより表されるグラフにおいて、大局的なエネルギーを最小にできることに特徴があり、グラフカットとも称されている。
【０００３】
最大フロー／最小カットアルゴリズムを、多視点画像から３次元形状を生成する画像再生技術に適用する際、３次元座標で規定される被写体の頂点をノードとに対応させ、隣接する頂点間の接続部をエッジに対応させる。各ノードには、カメラ画像間の相互相関値が与えられ、各エッジには両端ノードの相互相関値の平均値が与えられてグラフが形成される。得られたグラフに最大フロー／最小カットアルゴリズムを適用して、被写体の形状が切り出される。しかし、このアルゴリズムは大局的なエネルギーを最小化するので、切り出される形状が小さく縮退する傾向にある。縮退する不具合を解消するためには、なんらかの改良が必要であり、例えば、初期形状の内部にエネルギーの大きなノードを設けて不必要にカットされるのを抑制したり、多視点画像から画像エッジや特徴点等の信頼性の高い形状情報が得られる頂点を拘束条件に用いる方法が提案されている（例えば、非特許文献３及び４参照）。
【非特許文献１】「局所的形状特徴に拘束された３次元形状復元手法とそのリアルタイム動画表示」，映情学誌，Vol.61，No.4，pp.471-481（Apr.2007）
【非特許文献２】「弾性メッシュモデルを用いた多視点画像からの高精度３次元形状復元」，情処学論，Vol.43，No.SIG11（CVIM5），pp.53-63，（2002）
【非特許文献３】「Surface Capture for Performance-Bases Animation」，IEEE Computer Graphics and Applications，Vol.27，No.3，pp.21-31，（2007）
【非特許文献４】「Multi-view stereo volumetric graph-cuts」，IEEE Conference on Computer Vision and Pattern Recognition (CVPR)，2:391-398，(2005)
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、複数のカメラ画像から被写体の３次元形状を生成するに当たり、視体積交差法で得られる初期形状を大きく崩すことなく、３次元形状モデルを安定して生成できる３次元形状生成装置を実現することにある。特に、最大フロー／最小カットアルゴリズムを適用することにより、３次元形状モデルを生成する手法を具体化することにある。この目的を達成するためには、以下の解決すべき課題が想定される。
Ａ．視体積交差法により形成された画像データに最大フロー／最小カットアルゴリズムを適用した場合、例えば被写体が着物を着た人物の場合、着物の袖などの薄い部分が切り離され易い傾向にある。その対策として、視体積交差法により得られる初期形状の内部に、カットされにくい硬い芯となるソリッド部分を設けることが想定される。しかし、硬い芯となるソリッド部分を設けると、カットされるべきエッジがカットされない問題が発生し、芯となるソリッド部分の設定手段を開発する必要がある。
Ｂ．視体積交差法では、原理的に、被写体の凹状形状を正確に再現することができない。他方、滑らかに変化する凸状形状については概ね正確な形状を再現できる。従って、視体積交差法で得られる初期形状に最大フロー／最小カットアルゴリズムを適用する場合、被写体の凹状部分と凸状部分とを判別し、各部位に応じて拘束条件を設定する必要がある。従って、凹凸形状の判別条件と拘束条件の設定手法を開発する必要がある。
Ｃ．最大フロー／最小カットアルゴリズムを適用する際、各頂点毎にカメラ間の相互相関値はエネルギーとしてノードを介してエッジに与えられる。この場合、エッジに与えられる相互相関値を適応的に演算できる演算手段が必要である。また、１つの頂点の相互相関値をカメラの組合せから求める場合、カメラの組合せ毎に得られる相互相関値を適切に統合する手段も必要である。
【０００５】
本発明の目的は、視体積交差法により得られる３次元形状モデルについて最大フロー／最小カットアルゴリズムを適用することにより被写体の３次元形状を生成する３次元形状生成装置において、上述した課題が解決された３次元形状生成装置を実現することにある。
【課題を解決するための手段】
【０００６】
本発明による３次元形状生成装置は、被写体を複数の角度方向から撮像した多視点カメラ画像から被写体の３次元形状モデルを生成する３次元形状生成装置であって、
多視点カメラ画像からシルエット画像を生成するシルエット画像生成手段と、
生成されたシルエット画像について視体積交差法を適用し、被写体の近似された３次元形状モデルであるソリッドモデルを生成するソリッドモデル生成手段と、
前記シルエット画像とソリッドモデルとに基づいてシルエット拘束値を生成するシルエット拘束情報生成手段と、
前記ソリッドモデルを用いて、被写体表面を可視的に撮像したカメラを各頂点毎に特定する頂点可視情報生成手段と、
前記特定されたカメラにより撮像されたカメラ画像間の相互相関値を演算する相互相関値演算手段と、
前記生成されたシルエット拘束値を用いて、演算された相互相関値について重み付けを行い、重み付けされた相互相関値を出力する手段と、
前記ソリッドモデルについて、表面頂点に対応するノードと、隣接するノード間を接続するエッジとから構成されるグラフを形成し、前記重み付けされた相互相関値を用いて最大フロー／最小カットアルゴリズムを適用して被写体の３次元形状モデルを生成する最大フロー／最小カット演算手段とを具えることを特徴とする。  
【０００７】
本発明では、シルエット画像について視体積交差法を適用することにより得られるソリッドモデルをベースとし、当該ソリッドモデルから各種ソリッドモデルを生成し、生成されたソリッドモデルについて最大フロー／最小カットアルゴリズムを適用しているので、最大フロー／最小カットアルゴリズムを適用しても被写体の薄い部分が切り離される不具合が解消され、再現性に優れた３次元形状生成装置が実現される。しかも、シルエット画像について視体積交差法を適用することにより得られる初期形状について、凸状部分の形状が拘束（保持）され凹状部分の形状が強く補正されるように拘束条件を規定し、得られた拘束条件を用いて相互相関値を重み付けしているので、視体積交差法を適用することにより得られる初期形状を大きく崩すことなく、被写体の３次元形状を再現することができる。
【０００８】
本発明による３次元形状生成装置の好適実施例は、ソリッドモデル生成手段は、シルエット画像に視体積交差法を適用することにより形成される第１のソリッドモデルと、第１のソリッドモデルにエロージョン処理を行うことにより得られる第２のソリッドモデルと、第１のソリッドモデルにダイレーション処理を行うことにより得られる第３のソリッドモデルと、第１のソリッドモデルに適応的エロージョン処理を行うことにより得られる第４のソリッドモデルとを生成し、
前記最大フロー／最小カット演算手段は、第３のソリッドモデルと第４のソリッドモデルとの間に位置するカット領域について最大フロー／最小カットアルゴリズムを適用し、エネルギーの総和が最小となる３次元形状モデルを生成することを特徴とする。
【発明の効果】
【０００９】
本発明では、シルエット画像について視体積交差法を適用することにより得られるソリッドモデルをベースとして各種ソリッドモデルを生成すると共に、生成されたソリッドモデルに対してシルエット拘束情報により重み付けされた相互相関値を用いて最大フロー／最小カットアルゴリズムを適用しているので、被写体の薄い部分が良好に再現されると共に視体積交差法を適用して得られる３次元形状を大きく崩すことなく被写体の３次元形状を良好に再現することができる。
【発明を実施するための最良の形態】
【００１０】
本実施例では、３次元世界座標系に頂点空間を設定し、各頂点にカメラ画像から計算した対応度と被写体のシルエットから生成した拘束値とを与えることにより、対応度と拘束値で規定されるエネルギーを頂点毎に設定する。隣り合う頂点の平均エネルギーを頂点間を結ぶエッジのエネルギーとし、その総和が最小となる頂点群を最大フロー／最小カットアルゴリズムを用いて求める。この処理により、求められた頂点群を表面頂点とする３次元形状モデルが生成される。本発明による処理フローは以下のａ〜ｆの処理に大別される。以下において、処理ａ〜ｅの順序にしたがって処理工程を説明する。尚、各カメラの姿勢、位置、焦点距離等のカメラパラメータは既知のものとする。
ａ．各種ソリッドモデルの生成
ｂ．シルエット拘束情報の生成
ｃ．頂点毎の可視カメラ情報の生成
ｄ．頂点毎の対応度情報の生成
ｅ．相互相関値に対する重み付け処理
ｆ．最大フロー／最小カットアルゴリズムによる３次元形状の生成  
【００１１】
図１は本発明による３次元形状生成装置の一例を示す線図である。被写体を取り囲むようにｎ台のカメラを配置し、カメラ１ａ〜１ｎにより被写体を種々の角度方向から撮像し、撮像されたカメラ画像を３次元形状生成装置に供給する。尚、本例では、カメラ画像についてコンピュータによるソフトウェァ処理を行って被写体の３次元形状を再生する。また、本例の実行に先立ち、各カメラの位置、姿勢、焦点距離などのカメラパラメータは計測して、記録されているものとする。
【００１２】
ｎ個のカメラ画像は、シルエット画像生成部２に供給され、ｎ個のシルエット画像が形成される。シルエット画像生成部２では、個々のカメラ画像から被写体以外の背景領域を除去し、被写体領域のみを切り出したシルエット画像を生成する。尚、シルエット画像の生成方法として、被写体が存在するカメラ画像と背景だけの画像との差分をとり、被写体のみを抽出する背景差分法により生成することができ、又はクロマキー法により生成することもできる。
【００１３】
生成されたシルエット画像は、被写体の各種３次元形状モデルであるソリッドモデルを生成するソリッドモデル生成部３に供給する。初めに、シルエット画像は、視体積交差法部４に供給される。視体積交差法部４では、シルエット画像とカメラパラメータとを用い、視体積交差法により被写体の近似的な３次元形状を生成する。視体積交差法により得られた近似的な３次元形状をソリッドモデル１と称することにする。
【００１４】
さらに、ソリッドモデル生成部３は、エロージョン処理部５、ダイレーション処理部６及び適応的エロージョン処理部７を有する。エロージョン処理部５は、視体積交差法により生成された３次元形状モデルであるソリッドモデル１について、モルフォロジ法の一つであるエロージョン処理を適用して、ソリッドモデル１から頂点１個分だけ縮小した３次元形状データ（ソリッドモデル２）を生成する。ダイレーション処理部６は、ソリッドモデル１について、モルフォロジ法の一つであるダイレーション処理を適用して、ソリッドモデル１から頂点１個分だけ拡大された３次元形状データ（ソリッドモデル３）を生成する。
【００１５】
適応的エロージョン処理部７は、ソリッドモデル１について適応的なエロージョン処理を行って、ソリッドモデル１の各部の厚みに応じて縮小した３次元形状データ（ソリッドモデル４）を生成する。この場合、単純にエロージョン処理を行うと、ソリッドモデル１中の薄い部分が欠落する不具合が発生する場合がある。例えば、縮小頂点数をＮ＝２としてエロージョン処理を実施すると、ソリッドモデル１の厚さが（２Ｎ＋１）頂点分以下の部位は欠落してしまう。そこで、本発明では、ソリッドモデル１の各頂点について表面頂点までの距離を計測し、縮小対象となる頂点から頂点がＮ個分だけ内側に位置する領域内における距離の最大値を求め、その最大値をM（整数）で割った数だけエロージョン処理により縮小する。この適用的エロージョン処理の例を図２に示す。図２において、Ｎ＝２、M=２とし、２次元で示す。図２（ａ）は、ソリッドモデル１を２次元的に示す。図２（ｂ）に示すように、各頂点から表面頂点までの距離を計測し、これを距離値Ａとする。次に、同図（ｃ）に示すように、対象頂点の周り（N×M＋１）×（N×M+1）の範囲で、距離Ａの最大値を検出する。次に、同図（ｄ）に示すように、その最大値の１／M（四捨五入）の距離値を計算する。これを距離Ｂとする。頂点毎に構造要素の大きさを（２×距離Ｂ＋１）とし、エロージョン処理を実行する。距離Ｂ＝１の領域では３×３の構造要素を用い、距離Ｂ＝２の領域では５×５の構造要素を用いてエロージョン処理を行う。図２（ｅ）に示すように、適応的エロージョン処理を実行することにより、薄い部分も残り、破線及びドット点で示す頂点がソリッドモデル４となる。このようにして生成された４個のソリッドモデル１〜ソリッドモデル４を用いて被写体の３次元形状を再生する。
尚、ソリッドモデル１〜４は、頂点ごとに「１」又は「０」のいずれかの値をとる２値データである。以下の説明では、「１」が割り振られた頂点が被写体形状を表し、「０」が割り振られた頂点は被写体の外側を表すものとする。
【００１６】
次に、シルエット拘束情報生成処理について説明する。ここで、「シルエット拘束値」とは、視体積交差法により得られる３次元形状について、真の被写体形状に忠実に対応する凸状部分の形状を拘束（保持）するための変数としての意義を有し、凸状部分については拘束値が小さく凹状部分について拘束値が大きくなるように処理する。各カメラ画像から求められたシルエット画像並びにソリッドモデル１及び３をシルエット拘束情報生成部１０に供給する。シルエット拘束情報生成部１０は、シルエット数を計数するシルエット数生成部１１と、得られシルエット数に基づいてシルエット拘束値を生成するシルエット拘束値変換部１２とを有する。
【００１７】
各カメラ画像から得られたシルエット画像並びにソリッドモデル１及び３は、シルエット数生成部１１に入力する。シルエット数生成部１１では、各カメラのシルエット画像にソリッドモデル３の表面頂点を投影し、投影点の近傍にシルエット端が存在するか否かについて、以下の手法を用いて判定する。尚、本明細書において、シルエット端とは、被写体のシルエットと背景との境界点を意味する。
【００１８】
初めに、投影点が背景画素であり、投影点の周りにシルエット画像を構成する画素が少なくとも１画素あれば、当該頂点をシルエット端の頂点であると判定する。例えば、図３に示す例では、頂点Ａはシルエット端と判定され、頂点Ｂはシルエットに該当しない。
【００１９】
上述したシルエット端の検出処理を全てのカメラについて（全てのシルエット画像について）行い、シルエット端と判定されたカメラ数を計数し、計数されたカメラ数をシルエット数と定義する。そして、計数されたシルエット数をシルエット拘束情報としてソリッドモデル３の表面頂点に付与する。生成されたシルエット拘束情報は、後述する相互相関演算３０の重み付け演算部３２に供給され、相互相関値に対する重み付け因子として利用する。
【００２０】
図４は、視体積交差法により生成されたソリッドモデル１の生成状況を示す図である。図４に示すように、被写体の凹部はシルエット数が少なく、凸部はシルエット数が多いことが理解できる。凹状形状の部分では、シルエット数が少なく、シルエットの交差角度も小さい。これに対して、表面形状が滑らかに変化する凸状形状の部分では、シルエット数が多く、その交差角度も大きくなる傾向にある。従って、このような特性を考慮して、シルエット拘束値を決定する。また、図５は、真の被写体形状、ソリッドモデル１及びソリッドモデル３の位置関係を示す図である。
【００２１】
尚、シルエット拘束値を補正する方法として、シルエット数＝２の場合において、２台のカメラから当該頂点に向かうベクトル間の交差角が例えば１２０°以下の場合、シルエット数は０とすることができる。この理由は、被写体表面が滑らかに形状変化するする凸状部分についてだけシルエット情報を与えるためである。図４、図５の頂点Cはシルエット数＝２であるが、交差角が１２０度程度以下であれば、シルエット数は０とする。
【００２２】
シルエット数生成部１１において生成されたシルエット数は、シルエット拘束値変換部１２に供給される。シルエット数は頂点毎に付与されるが、拘束の程度を調整するため、シルエット拘束値変換部において、以下のようなシルエット拘束値に変換する。
Ｔを定数とし、シルエット数を以下のように制御する。
ＩＦ（シルエット数＞Ｔの場合）  Ａ＝Ｔ
ＩＦ（シルエット数＜Ｔの場合）  Ａ＝シルエット数  
すなわち、シルエット数が閾値Ｔを超える場合、シルエット数をＴで頭打ちにする。さらに、シルエット拘束値は以下の式により規定し、正規化する。
シルエット拘束値＝１−Ａ／Ｔ
【００２３】
次に、被写体表面を可視的に撮像しているカメラを特定する可視カメラ情報の生成処理について説明する。後述する相互相関値の演算処理においては、被写体の各頂点を直接すなわち可視的に撮像するカメラから出力されるカメラ画像が必要である。そこで、可視カメラ情報生成部２０において、ソリッドモデル１〜３を用いて各頂点を可視的に撮像しているカメラを以下の手法により特定する。
【００２４】
本例では、ソリッドモデル１が「１」となり、ソリッドモデル２が「０」となる頂点をソリッドモデル１の表面頂点とし、表面頂点を可視的に撮像するカメラを特定する。ある表面頂点からカメラに向かう単位ベクトルを求め、そのベクトルに沿って、表面頂点の位置を頂点間隔ずつ移動させ、移動した位置に別の頂点が存在する場合、当該カメラは当該頂点を直接撮像していない状態にある（不可視）と判定する。一方、３次元頂点空間の端まで移動を繰り返し、別の頂点が存在しない場合、当該カメラは当該頂点を可視的に撮像する状態にある（可視）と判定する。この処理を全てのカメラについて行い、表面頂点を可視的に撮像しているカメラを特定した可視カメラ情報を生成する。この処理により、各表面頂点ごとに可視的に撮像するカメラが特定される。
【００２５】
次に、基準カメラを特定する。表面頂点から特定されたカメラに向かう単一ベクトルと平均方向ベクトルを求め、平均方向ベクトルと各カメラの単位ベクトルとの角度の小さい順に、特定されたカメラ番号を並び替え、可視カメラ情報を生成する。可視カメラ情報において、先頭のカメラを基準カメラとし、それ以外のカメラを参照カメラと称する。この基準カメラ及び参照カメラの特定処理を、図６を参照しながら説明する。図６において、被写体を１０台のカメラＣ１〜Ｃ１０により撮像しているものとする。初めに、表面頂点ＡについてカメラＣ１〜Ｃ１０の方向に移動させ、可視的に撮像しているカメラを特定する。図６に示す場合、表面頂点Ａを直接撮像しているカメラは、Ｃ６、Ｃ７、Ｃ８、及びＣ９である。次に、頂点Ａから各カメラに向かうベクトルと平均方向ベクトルとの内積をそれぞれ計算し、内積値が最大となるカメラを基準カメラに設定する。従って、図６に示す例では、カメラＣ７が基準カメラとなり、残りのカメラＣ６、Ｃ８、及びＣ９は参照カメラとなる。一方、カメラＣ９に向かうベクトルは、平均方向ベクトルに対して９０°を超える角度をなしており、対応度（相互相関）の計算に不適当である。よって、このようなカメラは、角度差に基づく判定により、相互相関値の演算対象から排除する。従って、最終的に、カメラＣ７が基準カメラとなり、カメラＣ６及びＣ８が参照カメラとなる。そして、カメラＣ６〜Ｃ８が相互相関値の演算対象となり、可視カメラ情報として相互相関演算部３０に供給する。
【００２６】
次に、相互相関演算処理について説明する。可視カメラ情報、ソリッドモデル３及び４、及びカメラ画像を相互相関演算部３０に供給する。相互相関演算部３０は、カメラ画像間の相互相関値を計算する相互相関値計算部３１と、計算された相互相関値をシルエット拘束情報で重み付けを行う重み付け演算部３２とを有する。相互相関計算部３１では、ソリッドモデル３の表面頂点及び内部頂点を、可視カメラ情報生成部２０において特定されたカメラのカメラ画像に投影し、投影点近傍においてカメラ画像間の相互相関値を計算し、各頂点の対応度として利用する。
【００２７】
図７は、相互相関値計算用のブロックの構成を示す。画像相関値の計算は、ブロック単位で行い、一例として以下の手順でブロックを構成する。初めに、相互相関値の計算対象となる頂点の世界座標を基準カメラのカメラ座標に変換し、頂点の近傍に一定間隔で、図面上の横方向にＷ個、縦方向にＷ個の仮想頂点からなる平面ブロックを設ける。図７に示すように、仮想頂点ブロックは基準カメラの方向ベクトルに直交する面となる。仮想頂点ブロックを世界座標に変換し、基準カメラＣ７及び参照カメラＣ６及びＣ８上に投影する。この投影により、各カメラ画像上にはＷ×Ｗ個の投影点群が形成されるので、これをブロックとして相互相関値を計算する。
【００２８】
複数の参照カメラが利用可能な場合、各参照カメラと基準カメラとの間相互相関値、あるいは２つの参照カメラ間の相互相関値の平均値をとることができる。平均値を求める際には、単純平均、重み付け平均等の方法を用いることができる。例えば、近接するカメラ間には大きな重み係数を与え、遠く離間するカメラ間には小さな重み係数を与えて平均化してもよい。
【００２９】
相互相関値は、カメラ画像の輝度信号を用いて計算される。一方、輝度信号を用いた相互相関値の計算と共に、ＲＧＢの各色成分についても相互相関値を計算し、色成分から得た相互相関値を用いて重み付け加算することも可能である。
【００３０】
上述した処理を、ソリッドモデル３が「＝１」且つソリッドモデル４が「＝０」となる頂点、すなわちソリッドモデル３の表面とソリッドモデル４の表面とで挟まれた領域内の頂点について行い、頂点毎の相互相関値を計算する。
【００３１】
次に、相互相関値の重み付け処理について説明する。相互相関値計算部３１において計算された相互相関値は、重み付け演算部３２に供給する。重み付け演算部３２には、シルエット拘束情報生成部１０において生成されたシルエット拘束情報も供給される。重み付け演算部３２では、入力した相互相関値に対してシルエット拘束情報で重み付けを行い、重み付けされた相互相関値を最大フロー／最小カット演算部４０に供給する。シルエット拘束情報を用いて重み付けを行うことにより、ソリッドモデル１の凸状部分の形状が拘束され、拘束されない部分の形状については補正が行われる。
【００３２】
次に、最大フロー／最小カット演算による３次元形状モデルの生成処理について説明する。最大フロー／最小カット演算部４０には、重み付けされた相互相関値と共にソリッドモデル３及び４が供給される。最大フロー／最小カット演算部４０は、供給されるソリッドモデル３及び４並びに相互相関値を用いて、頂点に対応するノード及び隣接するノード間を接続するエッジにより構成されるグラフを生成し、生成されたグラフについて最大フロー／最小カットアルゴリズムを適用して３次元形状モデルを生成する。図８は、３次元頂点空間に設定されたグラフの一例を示す。ソリッドモデル４とソリッドモデル３とにより挟まれた領域はカット領域であり、ソリッドモデル３＝が「１」、且つ、ソリッドモデル４が「＝０」により規定される頂点群である。
【００３３】
図８に示すように、ソリッドモデル４の内側及びソリッドモデル３の外側のエッジには大きな重みを与え、それぞれSノード、Tノードに大きな重みのエッジで接続する。図８（ａ）のカット領域にシルエット拘束値で重みづけされた相互相関値より決定されたエッジ重みが与えられている。このように生成したグラフに最大フロー／最小カットアルゴリズムを適用する。このアルゴリズムは通信ネットワーク網のノード間の最大フロー（最大情報伝送量）を計算するアルゴリズムである。本実施例では、エッジ重みを頂点間の通信容量と見なしてSノードからTノードへ最大フローを流す。その際に、エッジ毎にフローの飽和度を調べる。飽和している全てエッジを境界面として、グラフを２つに分割する。２つの領域のうち、Tノードとつながっているノード（頂点）群が３次元形状として切り出される。なお、グラフを２つに分割する境界面はいくつも有るが、上記の境界面のエッジの通信容量の相和が最小となるため、その境界面を最小カットと呼ぶ。
【図面の簡単な説明】
【００３４】
【図１】本発明による３次元形状生成装置の一例を示す線図である。
【図２】ソリッド４を生成する手法の一例を示す図である。
【図３】シルエット端の判定処理を示す図である。
【図４】視体積交差法により生成されたソリッドモデル１の生成状況を示す図である。
【図５】真の被写体形状、ソリッドモデル１及びソリッドモデル３の位置関係を示す図である。
【図６】可視判定処理を説明するための図である。
【図７】相互相関値の計算方法を説明するための図である。
【図８】３次元頂点空間を断面として示す図及び一部を拡大して示す図である。
【符号の説明】
【００３５】
１ａ〜１ｎ  カメラ
２  シルエット画像生成部
３  ソリッドモデル生成部
４  視体積交差法部
５  エロージョン処理部
６  ダイレーション処理部
７  適応エロージョン処理部
１０  シルエット拘束情報生成部
１１  シルエット数生成部
１２  シルエット拘束値変換部
２０  可視情報生成部
３０  相互相関演算部
３１  相互相関計算部
３２  重み付け演算部
４０  最大フロー／最小カット演算部
【図１】
2010121945.tif 000003
【図２】
2010121945.tif 000004
【図３】
2010121945.tif 000005
【図４】
2010121945.tif 000006
【図５】
2010121945.tif 000007
【図６】
2010121945.tif 000008
【図７】
2010121945.tif 000009
【図８】
2010121945.tif 000010