(57)【特許請求の範囲】
【請求項１】
対象物体を撮影した画像系列から画像特徴点の追跡行列を生成するステップ、追跡行列を分割して部分的にオーバーラップした複数の部分追跡行列を生成するステップ、部分追跡行列の欠測値を推定して補完した部分計測行列を生成するステップ、部分計測行列から部分点群データ及びカメラ姿勢データを生成するステップ、カメラ姿勢データ及び対象物体の撮影方向に基づいて、部分計測行列から生成された部分点群データに対し凹凸修正を行うステップ、複数の部分計測行列から生成された凹凸修正後の部分点群データを統合するステップからなることを特徴とする３次元形状情報生成方法。
【請求項２】
対象物体を撮影した画像系列から画像特徴点の追跡行列を生成するステップ、追跡行列を分割して部分的にオーバーラップした複数の部分追跡行列を生成するステップ、部分追跡行列の欠測値を推定して補完した部分計測行列を生成するステップ、部分計測行列から部分点群データ及びカメラ姿勢データを生成するステップ、複数の部分計測行列から生成された部分点群データを統合するステップ、カメラ姿勢データに基づいてテクスチャマッピング用画像を選択するステップからなることを特徴とする３次元形状情報生成方法。
【請求項３】
部分追跡行列の生成ステップは追跡行列を整形した後に分割すること特徴とする請求項１又は２記載の３次元形状情報生成方法。
【請求項４】
請求項１、２又は３記載の３次元形状情報生成方法の各処理ステップをコンピュータに実行させるためのプログラムが記録されたことを特徴とするコンピュータ読取可能記録媒体。
【請求項５】
対象物体を撮影した画像系列を入力する手段、入力された画像系列から画像特徴点の追跡行列を生成する手段、追跡行列を分割して部分的にオーバーラップした複数の部分追跡行列を生成する手段、部分追跡行列の欠測値を推定して補完した部分計測行列を生成する手段、部分計測行列から部分点群データ及びカメラ姿勢データを生成する手段、複数の部分計測行列から生成された部分点群データを統合する手段、カメラ姿勢データに基づいて、テクスチャマッピング用画像を選択する手段を具備することを特徴とする３次元形状情報生成装置。
【請求項６】
部分点群データを生成する手段は、カメラ姿勢データ及び対象物体の撮影方向に基づいて、部分点群データに対し凹凸修正を行うことを特徴とする請求項５記載の３次元形状情報生成装置。
【請求項７】
部分追跡行列を生成する手段は、追跡行列を整形した後に分割すること特徴とする請求項５又は６記載の３次元形状情報生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、デジタルビデオカメラなどによって対象物体を撮影した画像系列から対象物体の３次元形状を推定、復元する技術に関する。
【０００２】
【従来の技術】
物体の３次元形状を表す点群データを入力する手法としては、レーザースキャンや人工的なテクスチャを投影するなどの能動的な手法と、カメラだけを利用する受動的な手法とがある。
【０００３】
後者の手法では、カメラで対象物体を撮影した時系列画像の各画像間で画像特徴点の対応付け（追跡）を行い、その結果に基づいて対象物体の形状を表す点群データを計算する。このような手法の一つとして、TomasiとKanadeにより提案された因子分解法がある（ C.Tomasi and T.Kanade,  Shape and Motion from Image Streams under Orthography: A Factorization Method, International Journal of Computer Vision,vol.9,1992, pp.137−154）。ここに述べられている方法は、正射影モデルに基づいて線形定式化を行い、数値計算的に安定な行列の特異値分解を用いるため、他の手法に比べて、解が極めて安定であることが特徴である。
【０００４】
また、定式化の線形性を保ちながら実際のカメラモデルである中心射影により近い擬似中心射影モデルを利用する因子分解法が、PoelmanとKanadeにより提案されている（ C.J.Poelman and T. Kanade, A paraperspective factorization method for shape and motion recovery,  IEEE Transaction on Pattern Analysis and Machine Intelligence,vol.19,no.3, pp.206− 218）。
【０００５】
因子分解法では、画像系列について画像特徴点の追跡を行い、全ての特徴点の全ての画像における位置データを、列を特徴点、行を画像にそれぞれ対応させて並べた追跡行列を構築する。追跡行列の上半分は特徴点のＸ座標、下半分は特徴点のＹ座標である。対象物体を一周するようにカメラで撮影したような場合、対象物体により隠蔽される特徴点があるため、追跡行列には位置データが欠落した要素（欠測値）が含まれるので、欠測値を周囲の位置データから推定して補完する処理を行う。そして、欠測値を補完した後の追跡行列（計測行列）の因子分解によって、対象物体の３次元形状を表す点群データとカメラの姿勢データを同時に生成する。
【０００６】
【発明が解決しようとする課題】
従来、因子分解法では、追跡行列全体を対象として一括処理しているため、追跡行列中の全ての欠測値を推定により補完する必要がある。しかし、対象物体を全周撮影したような場合、追跡行列に含まれるすべての欠測値を十分な精度で推定することは不可能なことが多く、対象物体の全周にわたる点群データを高精度に抽出することは殆ど不可能であった。
【０００７】
また、すべての欠測値の推定に成功したとしても、点群データを得るために長い計算時間を必要とするという問題があった。例えば１０００個の画像特徴点を１００枚の画像にわたって追跡した場合、追跡行列のサイズは２００×１０００となる。物体の全周にわたって高密度な点群データを生成するような実際的な応用を考えた場合、１０００個を越える点群のデータが必要になることが多く、追跡行列のサイズはさらに大きくなる。しかし、因子分解法は計算時間のかかる数値計算の手法であるため、上記のような大きな行列の全体に対し直接的に因子分解法を適用したのでは、莫大な計算時間を必要とし、また処理に大量のメモリを消費してしまう。因みに、特徴点の数が約４００点を越えると、計算時間は追跡行列のサイズの３乗にほぼ比例して増加する。
【０００８】
さらに、因子分解は一意でなく、二通りの解が存在するため、対象物体の表面の凹凸を正しく復元できないことがあるという問題もあった。
【０００９】
よって、本発明の目的は、対象物体を全周撮影した画像系列から対象物体の全周にわたる３次元形状を復元するための点群データを確実に生成できるようにすること、点群データを生成するための計算時間を短縮すること、対象物体の表面の凹凸を正しく復元できるようにすること、点群データから生成したメッシュのテクスチャマッピング用画像を最適選択できるようにすること等である。
【００１０】
【課題を解決するための手段】
前記目的を達成するため、本発明においては、対象物体を撮影した画像系列から生成した追跡行列を分割して、部分的にオーバーラップした複数の部分追跡行列を生成し、これら各部分追跡行列の欠測値を推定補完した部分計測行列を生成し、部分計測行列から部分点群データ及びカメラ姿勢データを生成する。そして、部分計測行列から生成されたカメラ姿勢データ及び対象物体の撮影方向に基づいて、部分計測行列から生成された部分点群データに対し凹凸修正を施し、凹凸修正後の各部分点群データを統合する。また、各部分計測行列から生成された部分点群データを統合し、カメラ姿勢データに基づいて、対象物体の形状復元のためのテクスチャマッピング用画像を自動選択する。
【００１１】
【発明の実施の形態】
以下の説明の理解を容易にするため、本発明において対象物体の全周にわたる点群データを生成する過程の概略を説明する。図１は、その過程を簡略化して示した図である。まず、対象物体を固定した状態でカメラ（デジタルビデオカメラ等）を特定方向に移動させながら、あるいは、カメラを固定した状態で対象物体を特定方向に回転させながら、対象物体の全周撮影を行う。この全周撮影によって得られた時系列画像の特徴点追跡によって、追跡行列を作成する。次に、追跡行列の分割処理を行って、部分的にオーバーラップした複数の部分追跡行列を生成する。次に、各部分追跡行列に対し欠測値の推定補完を行って、欠測値が補完された部分追跡行列（部分計測行列と呼ぶ）を生成し、この部分計測行列に因子分解法を適用することにより、対象物体の部分形状を表す点群データ（部分点群データ）を生成する。最後に、複数の部分計測行列から生成された部分点群データの統合処理を行うことにより、対象物体の全周にわたる形状を表す点群データ（全周点群データ）を生成する。
【００１２】
元の追跡行列に多くの欠測値が含まれていても、また、推定が困難な欠測値が含まれていたとしても、適切な分割処理を行えば、各追跡行列中の欠測値、すなわち各部分点群データの生成に必要な欠測値の推定が可能になる。また、適当な分割処理を行い、各部分追跡行列のサイズを元の追跡行列のサイズに比べ十分に小さくすれば、個々の部分計測行列から部分点群データを生成するための計算時間はもちろんのこと、全周部分点群データを生成するための計算時間を、元の追跡行列全体を対象とした因子分解法に比べ、大幅に短縮できる。
【００１３】
以下、本発明の一実施形態として、上に述べたような全周点群データの自動生成と、この全周点群データにより３次元形状を復元するためのテクスチャマッピング用画像の自動選択を行う３次元形状情報生成システムについて説明する。図２は、この３次元形状情報生成システムの概略構成図である。
【００１４】
図２において、１００は例えばデジタルビデオカメラ等を用いて対象物体を特定の方向に全周撮影した時系列画像を取り込むための画像取り込み装置である。取り込まれた時系列画像データは記憶装置１０１に記憶される。この記憶装置１０１に記憶されている時系列画像データは、画像入力部１０２によって２次元演算部１０３に入力される。この２次元演算部１０３は、入力された時系列画像データの画像特徴点の追跡を行って追跡行列を構築する追跡行列生成部１０４と、生成された追跡行列の分割処理を行って部分的にオーバーラップした複数の部分追跡行列を生成する追跡行列分割部１０５とからなるが、その処理内容の詳細については後述する。２次元演算部１０３の処理結果は３次元演算部１０６に入力される。この３次元演算部１０６は、対象物体の３次元形状を表す点群データの生成とテクスチャマッピング用画像の選択を行うもので、部分３次元データ生成部１０７と部分点群統合部１０８からなるが、その処理内容の詳細は後述する。３次元演算部１０６により生成されたデータは、データ出力部１０９により出力され、記憶装置１１に記憶される。
以下、各部の処理内容について、処理の流れに沿って説明する。
【００１５】
《追跡行列生成部１０３の処理》
図３に、追跡行列生成部１０３の処理フローを示す。まず、ステップ２００において、時系列画像の各フレームにおいて、濃度変化の激しい小画像領域を特徴点として抽出する。この際、濃度変化の激しい特徴点ほど高いランクとなるように、濃度変化の激しさによって特徴点にランク付けをする。そして、抽出した特徴点の中から、ランクの高いものから順に、所定個数の特徴点を選択する。
【００１６】
次に、ステップ２０２において、時系列画像の注目した２フレームに対し、前ステップ２００で選択された特徴点の対応付けを行うことにより、特徴点を追跡する。具体的には、一方のフレーム上の特徴点と他方のフレーム上の特徴点との間でパターンマッチングを行い、パターンが一致すると判断された特徴点を対応付ける。
【００１７】
選択された所定個数の特徴点の一部の特徴点の追跡すなわち対応付けに失敗した場合には（ステップ２０６、ＮＯ）、ステップ２００に戻り、現在の２フレームの未選択の特徴点の中から、追跡を失敗した特徴点に代わる特徴点を選びなおす。この選択は、ランクの高い特徴点を優先して行う。そして、ステップ２０２に戻り、選択しなおした特徴点に関する追跡を行う。
【００１８】
このようにして２フレーム間で所定個数の特徴点の追跡が成功すると（ステップ２０６、ＹＥＳ）、ステップ２０２に戻り、追跡を完了した２フレーム中の時間的に遅い１フレームと、その次の１フレームの２フレームを対象として、再び同様の特徴点追跡を行う。この際、時間的に早い１フレームに関しては、すでに追跡に成功した特徴点をまず選択して追跡を試みる。相前後する２フレームの全ての組に対し、同様の所定個数の特徴点の追跡を行う。
【００１９】
時系列画像の全フレームについて、所定個数の特徴点の追跡に成功すると（ステップ２０４、ＹＥＳ）、ステップ２０８に進み、特徴点追跡によって対応付けられた各特徴点の各フレーム上の位置データを並べた追跡行列を構築する。この追跡行列を保存し（ステップ２１０）、処理を終了する。
【００２０】
《追跡行列分割部１０４の処理》
図４に、追跡行列分割部１０５の処理フローを示す。まずステップ２２２において、追跡行列を取り込み整形処理を施す。追跡行列を分割して複数の部分追跡行列を生成するが、これら部分追跡行列中の欠測値の推定を容易にするため、換言すれば、そのような部分追跡行列を生成するような追跡行列の分割を容易にするために、追跡行列の整形処理を行う。この整形処理は、例えば次のようにして行う。まず、特徴点を連続して追跡できた時間（フレーム）に着目して次の４グループに分ける。
【００２１】
Ａグループ：最初のフレームから最後のフレームまで連続して追跡に成功した特徴点（全フレームにわたって欠測値とならなかった特徴点）。
Ｂグループ：最初のフレームからある途中のフレームまでは連続して追跡できたが、その途中フレームの次フレーム以降は追跡できなくなった特徴点（途中のフレーム以降で、欠測値となった特徴点）。
Ｃグループ：途中のフレームから、あるフレームまでは連続して追跡できるが、その次フレームから最後のフレームまで追跡できなくなった特徴点。
Ｄグループ：途中のフレームから最後のフレームまで連続して追跡できた特徴点。
【００２２】
そして、追跡行列のＡ，Ｂ，Ｃ，Ｄの各グループの特徴点に対応した列を、図５に模式的に示すような順番に並べなおす。これが整形処理である。図５において、網掛け部分は位置データが存在する要素であり、空白部分は位置データが存在しない（欠測値となっている）要素である。なお、追跡行列の上半分には各フレーム上の各特徴点のＸ座標が並び、下半分には各フレーム上の各特徴点のＹ座標が並ぶため、特徴点の個数をＰ、フレーム数をＦとすると、追跡行列は２Ｆ行×Ｐ列の行列となるが、図５ではＸ，Ｙ座標をまとめた形で表現している（以下、同様の表現方法を用いる）。
【００２３】
整形処理が終わると、ステップ２２２に進み、追跡行列の分割処理を行い、部分的にオーバーラップした複数の部分追跡行列を生成する。図６は分割処理によって生成される部分追跡行列の説明図である。図６において、網掛けされた各矩形領域が部分追跡行列を表し、黒ベタ領域が部分追跡行列間のオーバーラップ領域である。
【００２４】
このような分割処理は、以下のような条件に基づいて行われる。
（１）追跡行列の各行及び各列は、少なくとも１つの部分追跡行列の行及び列に対応する。
（２）各部分追跡行列のサイズは６×４以上である。
（３）各部分追跡行列の間に、１×４以上のサイズの行列データをオーバーラップさせる。
（４）各部分追跡行列において、完全な追跡データを持つ特徴点が４点以上、かつ、連続的に３フレーム以上にわたり存在する。
【００２５】
上記条件（１）は、完全な点群データと完全なカメラの姿勢データを得るための条件である。上記条件（２）は因子分解法の必要条件である。上記条件（３）は各部分追跡行列から生成される部分点群データを統合するために必要な、各点群データ間の共通点群データを提供するための条件である。上記条件（４）は各部分追跡行列中の欠測値を推定するための制限である。
【００２６】
分割処理の具体例を次に示す。図７は整形処理後の追跡行列の一例であり、図中の黒部分は追跡データ（特徴点の位置データ）が存在する要素を示し、空白部分は追跡データが欠測値となっている要素を示す。この追跡行列は、例えば、図８に黒ベタの横長矩形領域として示すような７個の部分追跡行列に分割される。ただし、図８においては、簡略化のために、各部分追跡行列のオーバーラップ領域は図示されていない。このような分割により生成される部分追跡行列を、左上のものから右下のものへ順に並べて図９に示す。
【００２７】
このような分割処理によって複数の部分追跡行列が生成されるが、同時に、部分追跡行列間のオーバーラップ領域の点群データが共通点群データとして保存される（ステップ２２６）。
【００２８】
次に、各部分追跡行列に対する欠測値（すなわち隠蔽特徴点）を推定する処理が行われる。すなわち、部分追跡行列を１つ取り込み（ステップ２２８）、その部分追跡行列に欠測値が含まれているか調べる（ステップ２３０）。欠測値が含まれていなければ、ステップ２２８に戻って次の部分追跡行列を取り込む。部分追跡行列に欠測値が含まれているならば、ステップ２３２に進んで欠測値の推定補完処理を行う。このような処理を繰り返し、全ての部分追跡行列に対する欠測値の推定補完が終了したならば（ステップ２３４、ＹＥＳ）、欠測値が推定値で補完された各部分追跡行列、あるいは最初から欠測値が存在しない部分追跡行列ほ、部分計測行列として保存する（ステップ２３６）。
【００２９】
次に、欠測値推定補完処理ステップ２３２の処理内容について説明するが、詳細な説明に先立ち、欠測値推定の基本的な考え方を図１０により説明する。図１０は、特徴点１〜７をフレーム１〜８にわたって追跡して構築される追跡行列の一例を示す。図中、「・」印は特徴点の追跡を成功し、その位置データが得られている要素を示し、「？」印は特徴点の追跡を失敗しその位置データが欠測値となっている要素を示す。このような欠測値の推定には、その欠測値の周りの既知の位置データを利用する。まず、推定対象の欠測値を１つ選択する。そして、選択した欠測値を含む、部分行列（推定行列と呼ぶ）を作成する。この推定行列では、推定対象の要素以外の要素は全て既知である（位置データが得られている）ことが必要である。例えば、図１０において、特徴点６のフレーム５の欠測値を推定対象として選択したとする。この場合、例えば図１０に示した枠の内部に対応した推定行列を作成する。この推定行列から欠測値を推定し、その推定値で該当欠測値を書き換える。次に、例えば、図１０中の特徴点６のフレーム６の欠測値を推定対象に選び、その推定のための推定行列を作成する。例えば、特徴点１〜６、フレーム１〜６に対応する推定行列を作成し、その欠測値を推定し、追跡行列の当該欠測値を推定値で書き換える。次に、例えば、図１０中の特徴点７のフレーム２の欠測値を推定対象に選択し、特徴点１〜７、フレーム２〜６に対応する推定行列を作成し、当該欠測値を推定する。このようにして、欠測値を１つずつ順次推定し、最終的に全ての欠測値を推定値によって補完する。
【００３０】
欠測値推定補完処理ステップ２３２の処理内容の一例を、図１１に示すフローチャートに沿って説明する。推定に用いる推定行列のサイズが大きいほうが推定精度が上がるが、その反面、１つの欠測値の推定のための計算コストが高くなってしまう。そこで、ここに示す処理例では、適当なサイズの推定行列を作り、欠測値の推定を行い、推定を失敗した場合には、推定行列のサイズをある大きさまで少しずつ増大させながら、推定を繰り返す。また、推定行列のサイズを少しずつ増大させながら推定演算を繰り返す処理をスムーズに進めることができるようにするため、ここに示す処理例では、処理過程で前記の整形処理を行う。また、欠測値が残っていて、それ以上は推定行列を構築できなくなった場合には、追跡行列を上下逆さに反転させる処理を行って、推定処理を続行する。
【００３１】
まず、処理対象の部分追跡行列に対し、前述の整形処理を行う（ステップ２５０）。整形後の部分追跡行列において、１つ以上の欠測値のための推定行列を構築可能であるか調べる（ステップ２５２）。可能ならば、注目した欠測値に対する推定行列を作成し（ステップ２５４）、推定演算を行い（ステップ２５６）、推定の成否を調べる（ステップ２５８）。成功した場合には、推定値で欠測値を書き換える。失敗した場合には推定行列のサイズを増加させ（ステップ２６０）、増加後の推定行列のサイズが予め決めた最大サイズ以下であるか調べる（ステップ２６２）。最大サイズ以下であるならば、その増加したサイズの推定行列を作成して推定演算を再度行う（ステップ２５６）。推定が成功するか、推定行列のサイズが最大サイズを越えると、全ての欠測値の推定が完了したか調べる（ステップ２７０）。欠測値が残っていなければ、処理は終了する。欠測値が残っている場合には、ステップ２５０２へ戻り次の欠測値に対する処理を続ける。
【００３２】
欠測値が残っているが、推定行列の構築がもはや不可能になった場合、ステップ２５２よりステップ２６４へ進み、部分追跡行列の上下反転を既に行ったか判定する。反転前ならば、部分追跡行列の上下反転を行い（ステップ２６６）、ステップ２５０へ戻って処理を続ける。部分追跡行列の上下反転後の処理でも欠測値が残っていて、推定行列の構築が不可能となった場合、ステップ２５２からステップ２６４へ、さらにステップ２６８へ進み、部分追跡行列を再び上下反転させて元の行順に戻し、処理を終了する。
【００３３】
なお、このような欠測値の推定は、各部分追跡行列の内部に限って行われる。本発明においては、追跡行列中の欠測値を全て推定する必要はなく、どの部分追跡行列にも含まれない欠測値は推定しない。そのような欠測値が残っていても、最終的に全周点群データを生成できる。
【００３４】
《部分３次元データ生成部１０７の処理》
図１２に、部分３次元データ生成部１０７の処理フローを示す。まず、欠測値推定補完後の部分計測行列を１つ取り込む（ステップ３００）。この部分計測行列に対し因子分解法による３次元データ計算処理を行い（ステップ３０２）、特徴点の３次元座標（部分的な形状を表す部分点群データ）３０４と、特徴点群とカメラとの相対的な３次元運動（カメラ姿勢データ）３０６を求める。前述のように、因子分解は一意ではなく、二通りの解があるため形状の凹凸の区別がつかないという問題がある。そこで、ステップ３１０において、カメラ姿勢データ３０６を対象物体の撮影方向３０８と比較し、一致しない特徴点に関しては部分点群データのｚ軸座標値（奥行き情報）を反転させる操作、すなわち凹凸反転操作を行う。このようにして、凹凸を修正した部分点群データ３１２を求め、これを保存する（ステップ３１２）。また、ステップ３１４において、カメラ姿勢データ３０６に基づいて、部分点群データ３１２のベクトルの平均方向に最も近い撮影方向（カメラの光軸方向）を持つ画像を、その部分点群データで生成したメッシュのテクスチャマッピング用画像として選択し、そのテクスチャ画像のインデックス３１６を保存する。
【００３５】
未処理の部分計測行列が残っているならば（ステップ３１８、ＮＯ）、ステップ３００に戻り、別の部分計測行列に対する処理が行われる。全ての部分計測行列が処理済となるまで（ステップ３１８、ＹＥＳ）、処理が繰り返される。
【００３６】
《部分点群統合部１０８の処理》
図１３に、部分点群統合部１０８の処理フローを示す。まず、ステップ３５０において、隣り合う２つの部分計測行列から生成された部分点群データと、その共通点群データを取り込む。次のステップ３５２において、共通点群データを２つの部分点群データ間の対応付け情報として利用して、２つの部分点群データを回転変換やアフィン変換によって統合する。そして、ステップ３５０に戻り、現在までの統合点群データに隣接する部分点群データと、その共通点群データを取り込み、ステップ３５２でさらに統合する。同様の統合処理を、全ての部分点群データの統合が終わるまで（ステップ３５４、ＹＥＳ）繰り返すことにより、対象物体の全周形状を表す全周点群データを生成し保存し（ステップ３５６）、処理を終了する。この全周点群データは、最終的にテクスチャマッピング画像インデックスと共にデータ出力部１０９により出力され、記憶装置１１０に格納される。
【００３７】
以上説明した一連の処理（又は３次元形状情報生成システムの構成部分の機能）は、例えば、図１４に簡略化して示すようなＣＰＵ４００、メモリ４０１、ハードディスクなどの補助記憶装置４０２、フロッピーディスクなどの記録媒体４０３の読み書きのための媒体ドライブ４０４、外部の入出力機器とのＩ／Ｏインターフェイス４０５などをシステムバス４０６によって接続したようなコンピュータ上でソフトウェアにより実現可能である。そのためのプログラム４０７は、、例えば、それが記録されたフロッピーディスクなどの記録媒体４０３より媒体ドライブ４０４を介して読み込まれて補助記憶装置４０２に一旦格納され、処理実行時にメモリ４０１にロードされる。時系列画像データや撮影方向データなどは、例えば、Ｉ／Ｏインターフェイス４０５を介して取り込まれる。
【００３８】
以上に説明した本発明の処理方法によれば、特徴点数が多い場合でも、従来の追跡行列を一括して処理する因子分解法に比べ、計算時間を大幅に短縮できる。この計算時間の短縮効果を明らかにするため、実験データを図１５に示す。この実験では、サン（ＳＵＮ）社のワークステーションＵＬＴＲＡ６０（ＣＰＵ：ＵｌｔｒａＳＰＡＲＣ＿II，メモリ：３８４ＭＢ）を使用し、ソフトウェアによって処理を実行した。追跡行列の特徴点数は１９２１個である。追跡行列の分割は、部分追跡行列の特徴点数の４分の１の個数の特徴点を共通点群とするように行った。図１５に示す「計算時間」は、ＣＰＵ１００％換算のＣＰＵ時間である。また、「分割数」は追跡行列の分割数（部分追跡行列の個数）であり、分割数＝１は分割を行わない場合、つまり従来の因子分解法による場合に相当する。
「部分点群点数」は各部分追跡行列の特徴点数であり、その右側の括弧内の数字は共通点群数である。「実行時間」は追跡行列の分割から各部分点群データの生成までに要した計算時間（秒）であり、部分点群データの統合処理の時間（非常に短く、ミリ秒オーダーである）は含まれていない。「特異値分解」は特異値分解のための計算時間（秒）であり、その右側の括弧内の数字は特異値分解のための計算時間が「実行時間」に占める割合（％）を示している。因子分解法における計算時間の大半は、特異値分解のための計算時間である。
【００３９】
図１５を見ると時間短縮効果は一目瞭然である。分割数＝１の場合（従来の因子分解法による場合に相当）、２時間以上の計算時間を要するが、分割数＝６の場合には計算時間は約６分まで短縮される。分割数＝２０の場合には計算時間はさらに大幅に短縮され、全周点群データを９０秒程度の短時間で生成できる。
【００４０】
【発明の効果】
以上の説明から明らかなように、本発明によれば、追跡行列の全体を一括して処理したのでは推定が困難な欠測値が追跡行列に含まれている場合にも、対象物体の３次元形状の復元に必要な点群データを確実に生成することができ、したがって、対象物体を全周撮影した画像系列から対象物体の全周にわたる３次元形状を復元するための全周点群データも容易に生成可能である。高密度な点群データを生成するための計算時間を大幅に短縮でき、また、処理に消費されるメモリ量も削減できる。対象物体の形状を、その表面の凹凸も含め正確に復元可能な点群データを生成できる。点群データから生成したメッシュのテクスチャマッピングのための最適な画像を自動的に選択できる、等々の効果を得られる。
【図面の簡単な説明】
【図１】対象物体の全周撮影から全周点群データを生成するまでの過程を簡略化して示す図である。
【図２】本発明による３次元形状情報生成システムの概略構成図である。
【図３】追跡行列生成部の処理フローを示すフローチャートである。
【図４】追跡行列分割部の処理フローを示すフローチャートである。
【図５】追跡行列の整形処理の説明図である。
【図６】追跡行列の部分追跡行列への分割の説明図である。
【図７】整形処理後の追跡行列の一例を示す図である。
【図８】図７に示した追跡行列の部分追跡行列への分割例を示す図である。
【図９】図７に示した追跡行列から生成された７つの部分追跡行列を示す図である。
【図１０】欠測値の推定方法の説明図である。
【図１１】欠測値推定補完処理の一例を示すフローチャートである。
【図１２】部分３次元データ生成部の処理フローを示すフローチャートである。
【図１３】部分点群統合部の処理フローを示すフローチャートである。
【図１４】本発明をソフトウェアで実現するためのコンピュータの一例を示すブロック図である。
【図１５】本発明による計算時間短縮効果を明らかにするための実験データを示す図である。
【符号の説明】
１００  画像取り込み装置
１０１  記憶装置
１０２  画像入力装置
１０３  ２次元演算部
１０４  追跡行列構築部
１０５  追跡行列分割部
１０６  ３次元演算部
１０７  部分３次元データ生成部
１０８  部分点群統合部
１０９  データ出力部
１１０  記憶装置
４０３  記録媒体
【図１】
0003835658.tif 000002
【図２】
0003835658.tif 000003
【図３】
0003835658.tif 000004
【図４】
0003835658.tif 000005
【図５】
0003835658.tif 000006
【図６】
0003835658.tif 000007
【図７】
0003835658.tif 000008
【図８】
0003835658.tif 000009
【図９】
0003835658.tif 000010
【図１０】
0003835658.tif 000011
【図１１】
0003835658.tif 000012
【図１２】
0003835658.tif 000013
【図１３】
0003835658.tif 000014
【図１４】
0003835658.tif 000015
【図１５】
0003835658.tif 000016