(57)【特許請求の範囲】
【請求項１】
対象物体を撮影した画像系列を入力データとして、対象物体の特徴点を追跡することにより追跡行列を作成するステップ、追跡行列の欠測値を、追跡行列の部分行列である推定行列を用いて推定し、欠測値を推定値で置き換えるステップ、この欠測値推定ステップを終了した追跡行列から計測行列を作成するステップ、及び、計測行列を対象物体の形状と運動をそれぞれ表す３次元データに変換するステップからなり、前記欠測値推定ステップにおいて推定行列のサイズを徐々に増大させながら欠測値の推定を繰り返すことを特徴とする３次元形状抽出方法。
【請求項２】
欠測値推定ステップにおいて、追跡行列を参照して特徴点をその追跡状況に応じて複数のグループに分類し、追跡行列に対し特徴点を所定のグループ順に並べ直す整形処理を施すことを特徴とする請求項１記載の３次元形状抽出方法。
【請求項３】
欠測値推定ステップにおいて、追跡行列に推定値で置き換えられていない欠測値が残っているが、そのいずれの欠測値に関しても推定行列の構築が不可能になった場合に、追跡行列の上下を反転して、追跡行列の整形処理と欠測値を推定する処理を継続することを特徴とする請求項２記載の３次元形状抽出方法。
【請求項４】
対象物体は所定方向に回転させつつ撮影され、計測行列より変換された３次元データにより表される対象物体の特徴点の運動方向と、前記撮影中の対象物体の回転方向とを比較し、この比較が不一致となった特徴点について凹凸を反転させるための操作を３次元データに施すステップをさらに含むことを特徴とする請求項１、２又は３記載の３次元形状抽出方法。
【請求項５】
対象物体を撮影した画像系列を入力する手段、入力された画像系列において対象物体の特徴点を追跡することにより追跡行列を作成する手段、追跡行列の欠測値を追跡行列の部分行列である推定行列を用いて推定する処理を、推定行列のサイズを徐々に増大させながら繰り返して欠測値を推定値で置き換える手段、この欠測値推定手段により処理後の追跡行列から計測行列を作成する手段、及び、計測行列を対象物体の形状と運動をそれぞれ表す３次元データに変換する手段からなることを特徴とする３次元形状抽出装置。
【請求項６】
対象物体を撮影した画像系列を入力する手段、入力された画像系列において対象物体の特徴点を追跡することにより追跡行列を作成する手段、追跡行列を参照して特徴点をその追跡状況に応じて複数のグループに分類し、追跡行列の特徴点を所定のグループ順に並べ換える整形処理を行った後、追跡行列の部分行列である推定行列を用いて追跡行列の欠測値を推定する処理を推定行列のサイズを徐々に増大させながら繰り返して欠測値を推定値で置き換える手段、この欠測値推定手段により処理後の追跡行列から計測行列を構築する手段、及び、計測行列を対象物体の形状と運動をそれぞれ表す３次元データに変換する手段からなることを特徴とする３次元形状抽出装置。
【請求項７】
欠測値推定手段において、追跡行列に推定値で置き換えられていない欠測値が残っているが、そのいずれの欠測値に関しても推定行列の構築が不可能になった場合に、追跡行列の上下を反転してから、追跡行列の整形処理と欠測値の推定処理を継続することを特徴とする請求項６記載の３次元形状抽出装置。
【請求項８】
対象物体は所定方向に回転させつつ撮影され、計測行列より変換された３次元データにより表される対象物体の特徴点の運動方向と、前記撮影中の対象物体の回転方向とを比較し、この比較が不一致となった特徴点について凹凸を反転させる操作を３次元データに施す手段をさらに有することを特徴とする請求項５，６又は７記載の３次元形状抽出装置。
【請求項９】
対象物体を撮影した画像系列を入力するステップ、入力された画像系列において対象物体の特徴点を追跡することにより追跡行列を作成するステップ、追跡行列の欠測値を追跡行列の部分行列である推定行列を用いて推定する処理を推定行列のサイズを徐々に増大させながら繰り返して欠測値を推定値で置き換えるステップ、この欠測値推定ステップにより処理後の追跡行列から計測行列を作成するステップ、及び、計測行列を対象物体の形状と運動をそれぞれ表す３次元データに変換するステップをコンピュータに実行させるプログラムが記録されたことを特徴とするコンピュータ読み取り可能記録媒体。
【請求項１０】
対象物体を撮影した画像系列において対象物体の特徴点を追跡することにより追跡行列を作成するステップ、追跡行列を参照して特徴点をその追跡状況に応じて複数のグループに分類し、追跡行列の特徴点を所定のグループ順に並べ換える整形処理を行った後、追跡行列の部分行列である推定行列を用いて追跡行列の欠測値を推定する処理を推定行列のサイズを徐々に増大させながら繰り返して欠測値を推定値で置き換えるステップ、この欠測値推定ステップを終了した追跡行列から計測行列を構築するステップ、及び、計測行列を対象物体の形状と運動をそれぞれ表す３次元データに変換するステップをコンピュータに実行させるプログラムが記録されたことを特徴とするコンピュータ読み取り可能記録媒体。
【請求項１１】
欠測値推定ステップにおいて、追跡行列に推定値で置き換えられていない欠測値が残っているが、そのいずれの欠測値に関しても推定行列の構築が不可能になった場合に、追跡行列の上下を反転してから、追跡行列の整形処理と欠測値の推定処理を継続することを特徴とする請求項１０記載のコンピュータ読み取り可能記録媒体。
【請求項１２】
対象物体は所定方向に回転させつつ撮影され、プログラムは、計測行列より変換された３次元データにより表される対象物体の特徴点の運動方向と、前記撮影中の対象物体の回転方向とを比較し、この比較が不一致となった特徴点については凹凸を反転させる操作を３次元データに施すステップをさらにコンピュータに実行させるものであることを特徴とする請求項９，１０又は１１記載のコンピュータ読み取り可能記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、デジタルビデオカメラなどによって対象物体を撮影した動画像などの画像系列から、対象物体の３次元形状を抽出、復元する技術に関する。
【０００２】
【従来の技術】
デジタルビデオカメラやデジタルスチルカメラのようなデジタルメディアによって取り込んだ動画像や静止画像の系列から、対象物体の３次元形状を推定する技術は、コンピュータヴィジョンの研究分野における重要な課題の一つである。また、その応用分野、例えばロボットヴィジョン、自動走行車、ビデオカメラを使った３次元形状入力、画像符号化、３次元モデリングなどでも大きな関心が持たれている。
【０００３】
時系列の２次元動画像からの３次元情報の抽出問題において、いわゆる「運動からの構造推定（Structure From Motion）」という方法では、運動(Motion)→距離(Depth)→形状(Shape)という手順にしたがって、まずカメラの運動を求め、次に物体上の特徴点のカメラ中心からの距離を求めることにより、形状を推定するのが普通である。しかし、時系列動画像では、各フレーム間での対応点の動きが小さいので、運動を平行運動か回転運動かによって特定するのは不可能に近い。結局、求められた奥行き(Depth)の解が不可能になり、形状情報の復元が上手くいかない。逆に時系列のサンプリング間隔を大きくとった場合、すなわち、各フレーム間の対応点の動きが大きい場合には、特徴点の対応付けの信頼性が低下してしまう。
【０００４】
奥行きを計算せずに動きと形状を同時に計算することによって解を安定させる方法として、TomasiとKanadeにより提案された「因子分解法(factorization)」がある（ C.Tomasi and T.Kanade,「Shape and motion from image stream
under orthography: A factorization method」, International Journal of
Computer Vision,vol.9,1992,pp.137−154）。この方法は、正射影モデルに基づいて線形定式化を行い、数値計算的に安定な行列の特異値分解を用いるため、他の手法に比べて、解が極めて安定であることが特徴である。
【０００５】
さらに、定式化の線形性を保ちながら実際のカメラモデルである中心射影により近い擬似中心射影(paraperspective)モデルを利用する因子分解法が、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）。
【０００６】
ここで、この擬似中心射影モデルと、それを利用する因子分解法について説明する。
【０００７】
まず擬似中心射影モデルについて述べる。このモデルは、中心射影のスケーリング効果（近くの物体が遠くの物体より大きく見えること）と、位置効果（画像の端に写っている物体が、投影中心の近くにある物体と違った角度で見える）を考慮しながら、正射影モデルの持つ線形性を保持している。擬似中心射影モデルによる物体の画像面への投影は、次のようなステップによって行われる。
（１）物体の重心を通り、画像面に平行な平面（仮想平面）を定義する。
（２）カメラ中心と物体の重心を結ぶ直線の方向に沿って、物体上の点を仮想平面に投影する。
（３）中心射影によって、その仮想平面上の点を画像面に投影する。
【０００８】
この操作を図１によって具体的に説明する。図１において、１はカメラ中心、２はカメラ中心１から焦点距離だけ離れた画像面である。Ｃは、カメラにより撮影された物体の特徴点（その一部が■マークで代表して表されている）の集合の重心（物体の重心）である。３は重心Ｃを通り画像面２に平行な仮想平面である。ワールド座標系の原点を重心Ｃに採り、特徴点ｐのワールド座標系での３次元座標をｓp∈Ｒ3とする。
【０００９】
時系列画像中のある画像フレームｆに関し、ワールド座標系でのカメラ中心１の座標をｔf、画像面２の２次元ローカル座標系の基底ベクトルをｉf，ｊf∈Ｒ3（ただし、‖ｉf‖＝‖ｊf‖＝１，ｉf×ｊf＝０）、カメラの光軸方向をｋf＝ｉf×ｊf∈Ｒ3とする。画像フレームｆにおいて、画像面２と、ベクトルｋfの交点Ｏfを原点に採り、単位直交ベクトルの組（ｉf，ｊf）により、２次元ローカル座標系Σf＝（Ｏf；ｉf，ｊf）を定義する。
【００１０】
擬似中心射影では、前述のように、特徴点ｐの画像面２への投影は次の２ステップで行われる。第１のステップで、特徴点ｐを仮想平面３に投影するが、この投影はカメラ中心１から重心Ｃに向かう直線と平行に行う。そして第２のステップで、仮想平面３に投影された点を画像面２に中心射影する。特徴点ｐの画像面２への投影点のΣf＝（Ｏf；ｉf，ｊf）での座標を（ｕfp，ｖfp）とする。ただし、カメラの焦点距離は１とする。この（ｕfp，ｖfp）は、次のように表現される。
【００１１】
【数１】
0003711203.tif 000002
ただし、
【００１２】
【数２】
0003711203.tif 000003
ここで、ｚfはカメラ中心１から仮想平面３までの距離、（ｘp，ｙp）は物体の重心Ｃ（ワールド座標系の原点）の中心射影による画像面２への投影である。また、（Ｕfp，Ｖfp）は特徴点ｐを画像面２へ中心射影したときの投影点の座標であり、次式により表される。
【００１３】
【数３】
0003711203.tif 000004
この（Ｕfp，Ｖfp）をｚfの周りでテーラー展開することにより、擬似中心射影モデルは、中心射影を
【００１４】
【数４】
0003711203.tif 000005
の仮定のもとで近似（一次近似）したものであることが分かる。
【００１５】
次に、因子分解法について説明する。因子分解法においては、Ｆ枚の画像フレームにわたってＰ個の特徴点を追跡し、その結果として、投影点の画像面Σf＝（Ｏf；ｉf，ｊf）上での２次元ローカル座標（ｕfp，ｖfp），ｆ＝1,2,...,F；ｐ＝1,2,...,Pを（５）式のよう並べた２Ｆ×Ｐの行列Ｗ（「追跡行列」と呼ぶ）を定義する。
【００１６】
【数５】
0003711203.tif 000006
この追跡行列の上半分は特徴点のｘ座標値ｕfpを表し、下半分は特徴点のｙ座標値ｖfpを表す。追跡行列の各列は一つの特徴点に対する追跡結果、各行は単一フレーム内の全特徴点のｘ座標値又はｙ座標値に対応する。
【００１７】
次に、各フレーム毎に全特徴点のｘ座標値の平均値ｘfとｙ座標値の平均値ｙf
【００１８】
【数６】
0003711203.tif 000007
を求める。そして、追跡行列の各要素からｘf，ｙfを差し引いた行列Ｗ*（「計測行列」と呼ぶ）を作る。
【００１９】
【数７】
0003711203.tif 000008
この計測行列は、フレーム数Ｆと特徴点数Ｐをいくら増やしても階数が高々３であるので、次のように分解できる。
【００２０】
【数８】
0003711203.tif 000009
これを前記（１）式と照らし合わせると、２Ｆ×３の行列Ｒはカメラの姿勢ベクトル｛（ｍf，ｎf）：ｆ＝1,2,...,F｝を、３×Ｐの行列Ｓは特徴点の位置ベクトル｛ｓp：ｐ＝1,2,...,P｝を、それぞれ並べた行列であることがわかる。
【００２１】
一般的には、計測行列にノイズが含まれるため、行列の階数が３であるとは限らないが、その場合でも、特異値分解を用いて大きな３つの特異値だけを保つように分解すると、二乗誤差の最小化の意味での最適分解が得られる。擬似中心射影モデルの場合も同様に、計測行列をカメラ姿勢行列と特徴点形状行列とに分解できる。このような計測行列に対する分解法を「因子分解法」と呼ぶ。
【００２２】
計測行列に対する因子分解の基本アルゴリズムについて説明する。計測行列の因子分解には、行列の特異値分解の手法が用いられる。すなわち、特異値分解を用いて、計測行列は次のように３つの行列の積に分解できる。
【００２３】
【数９】
0003711203.tif 000010
ただし、Ｕは２Ｆ×Ｐの直交行列、Σは計測行列の特異値（σ1,σ2,...,σP）からなるＰ×Ｐの対角行列、ＶはＰ×Ｐの直交行列である。もし、計測行列の階数が３であれば、σ4以降の特異値は０に近い、小さな値になる。ここで、σ4以降を０であるとして計測行列を分解すると、
【００２４】
【数１０】
0003711203.tif 000011
となる。そこで、
【００２５】
【数１１】
0003711203.tif 000012
とおけば、一つの分解
【００２６】
【数１２】
0003711203.tif 000013
が得られる。しかし、（１２）式の分解は一意ではない。実際、任意の正則行列Ｑにより、
【００２７】
【数１３】
0003711203.tif 000014
のように、無数の解が存在する。そこで、次のような拘束条件を導入し、この拘束条件を満たすＱを求める。
【００２８】
【数１４】
0003711203.tif 000015
【００２９】
【数１５】
0003711203.tif 000016
【００３０】
【数１６】
0003711203.tif 000017
そして、このＱを使って
【００３１】
【数１７】
0003711203.tif 000018
とおけば、
【００３２】
【数１８】
0003711203.tif 000019
に一意に分解できる。Ｒは２Ｆ×３の行列でカメラの姿勢を示す。Ｓは３×Ｐの行列で各特徴点の３次元座標値を示す。詳細は前述のPoelmanとKanadeの文献に譲るが、行列Ｒすなわち｛（ｍf,ｎf）：ｆ＝1,2,...,F｝と、（６）式で計算される（ｘf，ｙf）とから、カメラ方向｛（ｉf,ｊf,ｋf）：ｆ＝1,2,...,F｝を求めることができる。次に、（１４）式からｚfを、（２）式からカメラの位置ｔfを計算できる。
【００３３】
【発明が解決しようとする課題】
正射影モデル、擬似中心射影モデルのいずれを利用するにしても、因子分解法においては、選ばれたすべての特徴点が、一連の画像フレームにわたって追跡できることを前提としている。すなわち、最初の画像フレームで見えている特徴点が途中で隠れて見えなくなったり、途中の画像フレームで新しい特徴点が導入されたりしないことを仮定している。しかしながら、カメラが物体の周りを一回りするような状況では、最初の画像フレームで見えている特徴点の一部は途中で物体に遮蔽されてしまうので、そのような仮定は、長時間にわたって撮影された動画像などでは当てはまらない。その結果、追跡行列にかなりの数の欠測値ができてしまうため、推定によって欠測値を補完する必要がある。
【００３４】
また、因子分解は一意でなく、二通りの解が存在する。すなわち対象物体の表面の凹凸が区別できない。
【００３５】
よって、本発明の一般的な目的は、動画像や連続した静止画像系列から作成される追跡行列に欠測値が生じる場合にも、対象物体の３次元形状の高精度な抽出を可能にすることである。本発明のより具体的な目的の一つは、追跡行列中の欠測値の効率的な推定を可能にすることであり、もう一つの目的は、対象物体の３次元形状を表面の凹凸も含め正確に抽出可能にすることである。以上の目的、及びその他の目的は、以下の説明から明らかになろう。
【００３６】
【課題を解決するための手段】
請求項１乃至４の各項記載の発明によれば、改良された３次元形状抽出方法が提供される。この３次元形状抽出方法は、対象物体を撮影した画像系列を入力データとして、対象物体の特徴点を追跡することにより追跡行列を作成するステップ、追跡行列の欠測値を、追跡行列の部分行列である推定行列を用いて推定し、欠測値を推定値で置き換えるステップ、この欠測値推定ステップを終了した追跡行列から計測行列を作成するステップ、及び、計測行列を対象物体の形状と運動をそれぞれ表す３次元データに変換するステップからなり、前記欠測値推定ステップにおいて推定行列のサイズを徐々に増大させながら欠測値の推定を繰り返すことを特徴とする。請求項２記載の発明の特徴は、前記欠測値推定ステップにおいて、追跡行列を参照して特徴点をその追跡状況に応じて複数のグループに分類し、追跡行列に対し特徴点を所定のグループ順に並べ直す整形処理を施すことである。請求項３記載の発明の特徴は、前記欠測値推定ステップにおいて、追跡行列に推定値で置き換えられていない欠測値が残っているが、そのいずれの欠測値に関しても推定行列の構築が不可能になった場合に、追跡行列の上下を反転してから追跡行列の整形処理と欠測値を推定する処理を継続することである。請求項４記載の発明の特徴は、対象物体を所定方向に回転させつつ撮影し、計測行列より変換された３次元データにより表される対象物体の特徴点の運動方向と、前記撮影中の対象物体の回転方向とを比較し、この比較が不一致となった特徴点について凹凸を反転させる操作を３次元データに施すステップを追加することである。
【００３７】
請求項５、６、７又は８記載の発明によれば、改良された３次元形状抽出装置が提供される。
請求項５記載の発明に係る３次元形状値抽出装置は、対象物体を撮影した画像系列を入力する手段、入力された画像系列において対象物体の特徴点を追跡することにより追跡行列を作成する手段、追跡行列の欠測値を追跡行列の部分行列である推定行列を用いて推定する処理を、推定行列のサイズを徐々に増大させながら繰り返して欠測値を推定値で置き換える手段、この欠測値推定手段により処理後の追跡行列から計測行列を作成する手段、及び、計測行列を対象物体の形状と運動をそれぞれ表す３次元データに変換する手段からなることを特徴とする。
請求項６記載の発明に係る３次元形状抽出装置は、対象物体を撮影した画像系列を入力する手段、入力された画像系列において対象物体の特徴点を追跡することにより追跡行列を作成する手段、追跡行列を参照して特徴点をその追跡状況に応じて複数のグループに分類し、追跡行列の特徴点を所定のグループ順に並べ換える整形処理を行った後、追跡行列の部分行列である推定行列を用いて追跡行列の欠測値を推定する処理を推定行列のサイズを徐々に増大させながら繰り返して欠測値を推定値で置き換える手段、この欠測値推定手段により処理後の追跡行列から計測行列を構築する手段、及び、計測行列を対象物体の形状と運動をそれぞれ表す３次元データに変換する手段からなることを特徴とする。
請求項７記載の発明に係る３次元形状抽出装置は、請求項６記載の発明に係る３次元形状抽出装置であって、欠測値推定手段において、追跡行列に推定値で置き換えられていない欠測値が残っているが、そのいずれの欠測値に関しても推定行列の構築が不可能になった場合に、追跡行列の上下を反転してから、追跡行列の整形処理と欠測値を推定する処理を継続することを特徴とする。
請求項８記載の発明に係る３次元形状抽出装置は、請求項５，６又は７記載の発明に係る３次元形状抽出装置であって、対象物体は所定方向に回転させつつ撮影され、計測行列より変換された３次元データにより表される対象物体の特徴点の運動方向と、前記撮影中の対象物体の回転方向とを比較し、この比較が不一致となった特徴点について凹凸を反転させる操作を３次元データに施す手段をさらに有することを特徴とする。
【００３８】
【発明の実施の形態】
以下、本発明の一実施形態として、カメラによって物体を撮影した動画像又は一連の静止画像から、因子分解法により物体の３次元形状を高精度に抽出するための３次元形状抽出システムについて説明する。なお、カメラモデルとして前述の擬似中心射影モデルを仮定する。
【００３９】
図２は、この３次元形状抽出システムの一例の構成図である。図２において、１００は回転台であり、その上に対象物体１０２が載置される。回転台１００の外周部上面に、所定間隔で複数のマークＭが設けられている。１０４は回転台１００の回転駆動機構であり、駆動部１０６によって駆動される。１０８はデジタルビデオカメラであり、回転台１００を所定方向に所定速度で回転させた状態で、回転台１００上の対象物体１０２を連続的に撮影し、画像ストリームを出力する。なお、撮影中に回転台１００上のマークＭがカメラ１０８の視野に入るように、回転台１００とカメラ１０８の位置関係が決められる。
【００４０】
デジタルビデオカメラ１０８から出力される画像ストリームを基に対象物体の３次元形状を抽出するための処理系は、画像入力部１１０、２次元演算部１１２、及び３次元演算部１１４から構成され、パソコン１１６と協働して作用する。デジタルビデオカメラ１０８から出力される画像ストリームは画像入力部１１０に入力される。画像入力部１１０は、画像ストリームから静止画像の集合を作成し、それをパソコン１１６のメモリ上に書き込む。２次元演算部１１２は、パソコン１１６のメモリ上の静止画像集合を基に、因子分解のための計測行列を構築し、それをパソコン１１６のメモリに書き込む。３次元演算部１１４は、計測行列から対象物体の３次元形状を抽出する。抽出された３次元形状のデータはパソコン１１６のメモリに書き込まれる。好ましくは、パソコン１１６において、３次元形状データより３次元形状が復元されてディスプレイ画面に表示され、形状抽出の結果を確認可能とされる。
【００４１】
駆動部１０６から回転台１００の回転方向を示す回転方向データが出される。この回転方向データは、３次元演算部１１４に入力される。また、２次元演算部１１２において、回転台１００の回転方向を特徴点追跡に利用する場合には、２次元演算部１１２にも回転方向データが入力される。パソコン１１６は、前述のように処理の中間データと最終結果データを記憶するためのメモリを提供するほか、駆動部１０６や３次元形状抽出処理系（１１０，１１２，１１４）の動作制御を行う。画像入力部１１０、２次元演算部１１２、３次元演算部１１４の全部又は一部を、パソコン１１６のハードウェア上でソフトウェアにより実現してもよい。
【００４２】
画像入力部１１０の処理内容を説明する。図３はその処理フローを示すフローチャートである。画像入力部１１０は、デジタルビデオカメラ１０８より出力される画像ストリームを取り込む（ステップ３００）。取り込んだ画像ストリームの各フレームを、必要に応じて適当な静止画像のフォーマットに変換し（ステップ３０２）、得られた静止画像フレームの時系列をパソコン１１６のメモリに書き込む（ステップ３０４）。
【００４３】
２次元演算部１１２の処理内容を説明する。図４は、その処理フローを示すフローチャートである。図示のように、２次元演算部１１２は、まずパソコン１１６のメモリより画像フレームを取り込み、濃度変化の激しい小画像領域を対象物体の特徴点として抽出する（ステップ４００）。この際、好ましくは、濃度変化の激しさにより特徴点にランク付けする。すなわち、濃度変化が激しい特徴点ほど高いランクを付ける。
【００４４】
次に、２次元演算部１１２は、相前後するフレームの特徴点を対応付けることにより、特徴点を追跡する（ステップ４０２）。前ステップで特徴点のランク付けが行われた場合には、ランクの高い特徴点から優先して一定個数の特徴点を選んで追跡を行う。特徴点の追跡を行う場合、現フレーム上の特徴点と次フレーム上の特徴点との間でパターン・マッチングを行い、パターンが一致すると判断される特徴点を対応付けることになるが、類似したパターンが多数存在する場合は、特徴点の対応付け、すなわち追跡を誤る可能性がある。
【００４５】
このような追跡誤りを減らすため、好ましくは、駆動部１０６から入力された回転方向データによって示される回転台１００の回転方向を、特徴点追跡の制限条件として利用し、その回転方向と、対応付けた特徴点の移動方向とが矛盾する場合には、その追跡結果は誤っている可能性が高いので、その追跡結果を捨てる。その特徴点に関して、次フレームで他に対応する適当な特徴点が見つからなければ、その位置座標は欠測値となる。さらに追跡誤りを減らすため、好ましくは、回転台１００の外周部に設けられたマークＭのパターンを利用する。すなわち、特徴点の位置座標を（ｘ，ｙ）とし（ただし、ｘは水平方向、ｙは垂直方向の座標）、現フレームと次フレームにおいて、マークＭのパターン（マークパターンと呼ぶ）の中で、対応付けた特徴点のｙ座標と一番近いｙ座標を持つマークパターンを対応マークパターンとして選ぶ。そして、対応付けた特徴点の運動ベクトルの方向が対応マークパターンの運動ベクトルの方向と逆であるか、又は、特徴点の運動ベクトルの大きさと対応マークパターンの運動ベクトルの大きさとの差が所定の閾値を越えた場合は、追跡が失敗したと判断し、その追跡結果を捨てる。
【００４６】
次に、２次元演算部１１２は、前ステップの追跡結果に基づいて、前記（５）式に示した２Ｆ×Ｐの追跡行列を作成する（ステップ４０４）。この追跡行列のデータはパソコン１１６のメモリに書き込まれる。なお、ステップ４００，４０２で得られたデータもパソコン１１６のメモリに一時的に記憶される。
【００４７】
前述のように、対象物体それ自体による特徴点の隠蔽、あるいは撮影時の照明の変動や追跡の失敗などによって、追跡行列には特徴点の位置座標が欠落した要素（欠測値）が含まれているのが一般的である。２次元演算部１１２は、次に、そのような特徴点の欠測値の推定を行う（ステップ４０６）。そして、欠測値が補われた追跡行列に基づいて前記（７）式に示した計測行列を作成する（ステップ４０８）。計測行列はパソコン１１６のメモリに保存される。
【００４８】
次に、ステップ４０６の欠測値推定処理について説明する。具体的な処理内容の説明に先立ち、欠測値推定の基本的な考え方を説明する。
【００４９】
図５は、特徴点１〜７をフレーム１〜８にわたって追跡した結果の例である。図中、「・」印は特徴点の追跡を成功し、その位置座標が得られていることを示し、「？」印は特徴点の追跡を失敗しその位置座標が欠測値となっていることを示す。このような欠測値が計測行列に残っていると、そのままでは因子分解法に利用できないため、欠測値を推定して補完する必要がある。欠測値の推定には、その欠測値の周りの既知の位置座標を利用する。まず、推定対象の欠測値を１つ選択する。そして、選択した欠測値を含む、追跡行列の部分行列（推定行列と呼ぶ）を作成する。この推定行列では、推定対象の要素以外の要素は全て既知である（位置座標が得られている）ことが必要である。
【００５０】
例えば、図５において、特徴点６のフレーム５の欠測値を推定対象として選択したとする。この場合、例えば図５に示した枠の内部に対応した推定行列を作成する。この推定行列から欠測値を推定し、その推定値で追跡行列の該当欠測値を書き換える。次に、例えば、図５中の特徴点６のフレーム６の欠測値を推定対象に選び、その推定のための推定行列を作成する。例えば、特徴点１〜６、フレーム１〜６に対応する推定行列を作成し、その欠測値を推定し、追跡行列の当該欠測値を推定値で書き換える。次に、例えば図５中の特徴点７のフレーム２の欠測値を推定対象に選択し、例えば、特徴点１〜７、フレーム２〜６に対応する推定行列を作成し、当該欠測値を推定する。このようにして、欠測値を１つずつ順次推定し、最終的に追跡行列中の全ての欠測値を補完する。
【００５１】
ここで、推定行列から欠測値を推定する方法として、「行拡張」と呼ばれる方法と、「列拡張」と呼ばれる方法を説明する。次式に示すような推定行列を考える。ただし、ｕfp，ｖfpが推定対象の欠測値である。
【００５２】
【数１９】
0003711203.tif 000020
まず、行拡張法について説明する。（１９）式の推定行列の欠測値所在の行を抜いた部分行列を作る。そして、この部分行列を因子分解法で次のように分解する。
【００５３】
【数２０】
0003711203.tif 000021
Ｍ2mx3は２ｍ枚のフレームにおけるカメラの姿勢を表す行列、Ｓ3x(n+1)は
（n+1）個の特徴点における３次元座標を表す行列である。第（m+1)フレームにおける第(n+1)特徴点（ｕfp，ｖfp）は、次の方程式組を満たすことが分かる。
【００５４】
【数２１】
0003711203.tif 000022
（２１）式と（２２）式には、それぞれ４つの未知数（ｕfp，ｍfT）と
（ｖfp，ｎfT）があるので、これらの未知数を解くために、既知特徴点の数（＝n+1)は最低４、すなわちｎは３以上であることが分かる。しかし、ノイズなどの影響を考慮し、既知特徴点の数を４以上にして、言い換えれば、（２１）式と（２２）式を優決定系（over constrained）の最小二乗解で解くのが適当である。
【００５５】
まず、（２１）式を次のように展開する。
【００５６】
【数２２】
0003711203.tif 000023
（22.n+1）以外を次のように整理する。
【００５７】
【数２３】
0003711203.tif 000024
（２３）式から、ｍfが求められる。そして（22.n+1）式に代入し、
【００５８】
【数２４】
0003711203.tif 000025
のように、座標値ｕfpを求める。同じように、ｕfp が求められる。
【００５９】
【数２５】
0003711203.tif 000026
次に、列拡張法について説明する。行拡張法と逆に、（１９）式の推定行列から欠測値所在の列を抜いた部分行列を作る。この部分行列を因子分解法で、次のように分解する。
【００６０】
【数２６】
0003711203.tif 000027
Ｍ2(m+1)x3は２(m+1)のフレームにおけるカメラの姿勢を表す行列、Ｓ'3xnはｎ個の特徴点における３次元座標を表す行列である。第(m+1)フレームにおける第(n+1)特徴点（ｕfp，ｖfp）は次の２式を満たすことが分かる。
【００６１】
【数２７】
0003711203.tif 000028
（２６）式はｎ個までの特徴点に対し成立するが（２７）式と（２８）式は
(n+1)個までの特徴点に対し成立する。すなわち、Ｓ1'＋Ｓ2'＋...＋Ｓn'＝０に対し、Ｓ1＋Ｓ2＋...＋Ｓn＋Ｓn+1＝０でなければならない。ここで、
Ｓn+1＝−ｎＣとすると、
【００６２】
【数２８】
0003711203.tif 000029
である。すなわち、
【００６３】
【数２９】
0003711203.tif 000030
なお、（２７）式と（２８）式のｘfとｙfは次のように修正しなければならない。
【００６４】
【数３０】
0003711203.tif 000031
（３０）式と（３１）式を（２７）式と（２８）式に代入すると
【００６５】
【数３１】
0003711203.tif 000032
が得られる。この（３２）式から、Ｓp、そしてｕfp，ｖfpが求められる。
【００６６】
さて、推定に用いる推定行列のサイズが大きいほうが推定精度が上がるが、その反面、１つの欠測値の推定のための計算コストが高くなってしまう。そこで、本発明においては、前述のように、適当なサイズの推定行列を作り、欠測値の推定を行い、推定を失敗した場合には、推定行列のサイズをある大きさまで少しずつ増大させながら、推定を繰り返す。また、推定行列のサイズを少しずつ増大させながら推定演算を繰り返す処理をスムーズに進めることができるようにするため、本発明においては、推定処理の過程で追跡行列の「整形処理」を行う。また、欠測値が残っていて、それ以上は推定行列を構築できなくなった場合に、追跡行列を上下逆さに反転させる処理を行って、推定処理を続行する。
【００６７】
このように、本発明にあっては、推定行列のサイズを徐々に増大させながら欠測値の推定を行うことにより、欠測値推定の計算コストの増大を抑えることができ、また、追跡行列の整形処理さらには追跡行列の上下反転により、そのような欠測値推定をスムーズに行い、従来よりも効率よく、より多くの欠測値を的確に推定することができる。したがって、追跡行列中に多くの欠測値がある場合にも精度のよい３次元形状抽出が可能になる。
【００６８】
ここで、追跡行列の「整形処理」と「上下反転」について説明する。図６は、ある画像ストリームの追跡行列を示す。図中、網掛け部分は特徴点の位置座標が存在することを示し、空白部分は特徴点の位置座標が存在しない（欠測値となっている）ことを示す。この追跡行列を観察すると、特徴点は追跡状況によってグループ分けできることに気付く。
【００６９】
本発明によれば、例えば、特徴点の連続して存在する（追跡できた）時間（フレーム）によって、特徴点を次の４つのグループに分ける。
Ａグループ：最初のフレームから最後のフレームまで連続して存在する（全フレームにわたって追跡に成功した）特徴点、
Ｂグループ：最初のフレームでは存在するが、途中のフレームから消えてしまう（途中で追跡に失敗した）特徴点、
Ｃグループ：途中のフレームで出現するが、しばらくたって消える特徴点、
Ｄグループ：途中のフレームで出現して、最後のフレームまで連続して存在する特徴点。
そして、追跡行列のＡグループからＤグループの特徴点に対応した列を図７に示すような順番に並べ直す。これが整形処理である。図７において、網掛けした部分は位置座標（計測値）が存在する要素であり、空白部分は位置座標が存在しない（欠測値となっている）要素である。
【００７０】
このように整形した追跡行列を用いて、欠測値に対する推定を行う。推定は１回で成功するとは限らないので、推定が成功しない場合には、推定行列のサイズを、所定の最大サイズまで、少しずつ大きくしながら推定を繰り返す。欠測値の推定を成功した場合には、その欠測値を推定値で書き換え、それを初めから存在する位置座標として扱い、追跡行列の整形処理をやり直す。
【００７１】
要約すると、追跡行列の整形処理、推定行列の構築、推定演算の手順を停止条件を満たすまで、推定行列のサイズを少しずつ増加させながら繰り返す。この停止条件とは、具体的には、全ての欠測値を推定できたこと、又は、推定できない欠測値が残っているが、それ以上は推定行列を構築できないことである。そして、このような推定手順が終わっても欠測値が残っている場合は、追跡行列を上下反転させてから、同様の推定手順を繰り返す。
【００７２】
以上に説明した２次元演算部１１２における欠測値推定処理のフローの一例を図８に示し、説明する。まず、パソコン１１６のメモリから追跡行列を取り込む（ステップ５００）。この追跡行列に対し、前述の整形処理を行う（ステップ５０２）。整形後の追跡行列において、１つ以上の欠測値のための推定行列を構築可能であるか調べる（ステップ５０４）。可能ならば、注目した欠測値に対する推定行列を作成し（ステップ５０６）、推定演算を行い（ステップ５０８）、推定の成否を調べる（ステップ５１０）。成功した場合には、推定値で欠測値を書き換える。失敗した場合には推定行列のサイズを増加させ（ステップ５１２）、増加後の推定行列のサイズが予め決めた最大サイズ以下であるか調べる（ステップ５１４）。最大サイズ以下であるならば、その増加したサイズの推定行列を作成して推定演算を再度行う（ステップ５０８）。推定が成功するか、推定行列のサイズが最大サイズを越えると、全ての欠測値の推定が完了したか調べる（ステップ５１６）。欠測値が残っていなければ、処理は終了する。追跡行列はパソコン１１６のメモリに保存される。
【００７３】
推定値が残っている場合には、ステップ５０２へ戻り次の欠測値に対する処理を続ける。
【００７４】
欠測値が残っているが、推定行列の構築が不可能になった場合、ステップ５０４よりステップ５１８へ進み、追跡行列の上下反転を既に行ったか判定する。反転前ならば、追跡行列の上下反転を行い（ステップ５２０）、ステップ５０２へ戻って処理を続ける。追跡行列の上下反転後の処理でも欠測値が残っていて、推定行列の構築が不可能となった場合、ステップ５０４からステップ５１８へ、さらにステップ５２２へ進み、追跡行列を再び上下反転させて元の行順に戻し、処理を終了する。追跡行列はパソコン１１６のメモリに保存される。
【００７５】
ここで、推定行列の構築に関してさらに説明する。推定行列は、線形近似射影モデルの仮定条件を良く満たす特徴点の計測値（位置座標）を集めて構築するのが、推定精度を上げるために好ましい。すなわち、前述のように、擬似中心射影モデルは、中心射影モデルにおける、カメラの光学中心から対象物体の重心までの距離の周りで展開し、一次近似をとったモデルであり、次の２式の近似条件を仮定している。
【００７６】
【数３２】
0003711203.tif 000033
【００７７】
【数３３】
0003711203.tif 000034
（３４）式は撮影距離ｚfに比べて対象物体のサイズが十分に小さいという仮定を、（３３）式は各特徴点のカメラの光軸への投影量が非常に小さいという仮定をそれぞれ表している。各特徴点がモデルの仮想平面上にあれば、擬似中心射影が中心射影に一致すると言える。したがって、（３３）式は推定行列の構築条件を示唆している。しかし、仮想平面が常にカメラの画像面に平行であるため、カメラ運動が平行移動である場合以外は、各フレームにおけるカメラの姿勢は異なる。カメラの運動が激しい場合、（３３）式の仮定を満たすことは難しい。ただし、ビデオカメラで撮った動画像の場合、連続するフレーム間のカメラの姿勢変換は小さいため、局所的に集中している特徴点の集合は（３３）式の仮定を満たすと考えてよい。したがつて、追跡行列から推定行列を構築する際に、まず追跡を失敗し欠測値となっている特徴点（欠測特徴点）と最も近い特徴点を選択して推定行列を構築する。ただし、欠測特徴点の位置すなわち推定対象の欠測値が未知という問題がある。そこで、隣り合うフレーム間では特徴点の運動が平行運動であると仮定し、欠測値の代わりに、欠測特徴点の直前のフレームにある計測値（「仮定計測値」と呼ぶ）を利用する。すなわち、仮定計測値と最も距離が小さい計測値を選択して推定行列を構築する。この方法は、フレーム間の特徴点の運動が小さい動画像の場合に適する。
【００７８】
次に、３次元演算部１１４における処理内容を説明する。図９は、その処理フローを示すフローチャートである。
【００７９】
まず、３次元演算部１１４は、パソコン１１６のメモリより、２次元演算部１１２によって作成された計測行列を取り込む（ステップ６００）。次に、この計測行列に対し前述の因子分解法を適用し（ステップ６０２）、対象物体の特徴点の３次元座標（形状データ）６１１と、特徴点群とカメラとの相対的な３次元運動（運動データ）６１０を求める。
【００８０】
因子分解は一意ではなく、二通りの解があり、形状の凹凸の区別がつかないという問題がある。そこで本発明では、形状の凹凸判断を行って必要な凹凸の修正を行い（ステップ６０４）、凹凸が正確な形状データ６０６を得る。
【００８１】
ステップ６０４の内容を図１０に示す。すなわち、３次元（運動／形状）データ６１０，６１１と、駆動部１０６から入力された回転方向データ６１２とを比較し、回転台１００の回転方向と対象物体上の特徴点の運動方向との一致を調べる（ステップ７０２）。運動方向が一致する特徴点に関する形状データはそのまま正確なものとして出力する（ステップ７０６）。しかし、運動方向が一致しない特徴点の形状データについては、ｚ軸に対して反転し、すなわち凹凸反転操作を行い(ステップ７０４）、反転したものを正確な形状データとして出力する（ステップ７０６）。
【００８２】
このように、本発明によれば、撮影中の対象物体の回転の方向と、計測行列から得られた３次元データにより表される特徴点の運動方向とが不一致の場合に凹凸反転操作を行うことにより、対象物体の表面の凹凸も含めた正確な形状抽出が可能である。
【００８３】
図２に示した画像入力部１１０、２次元演算部１１２及び３次元演算部１１４の機能、あるいは図３、図４、図８、図９及び図１０に関連して説明した処理内容を、パソコン１１６又は別のパソコンその他のコンピュータを利用し、ソフトウェアにより実現することもできる。例えば、図１１に略示するようなＣＰＵ８００、メモリ８０１、ハードディスクなどの補助記憶装置８０２、フロッピーディスクなどの記録媒体８０４の読み書きのためのドライブ８０３、外部の入力機器との入力インターフェイス８０５及び出力インターフェイス８０６などをシステムバス８０７によって接続したようなコンピュータを利用できる。そして、図３、図４、図８、図９及び図１０に関連して説明した処理内容を実行させるためのプログラム８１０はメモリ８０１上に置かれてＣＰＵ８００によって実行される。このプログラム８１０は、例えば、それが記録されたフロッピーディスクなどの記録媒体８０４からドライブ８０３を介してメモり８０１にロードされ、あるいは補助記憶装置８０２に一旦格納され処理実行時にメモリ８０１にロードされる。カメラ１０８から出力される画像ストリームや駆動部１０６より出力される回転方向データは、例えば入力インターフェイス８０５を介して取り込まれる。最終的な形状データは、例えば、補助記憶装置８０２に保存されたり、ドライブ８０３を介してフロッピーディスクなどに書き出される。
【００８４】
【発明の効果】
以上の説明から明らかなように、本発明によれば、推定行列のサイズを徐々に増大させながら欠測値の推定を行うことにより、欠測値推定の計算コストの増大を抑えることができ、また、追跡行列の整形処理さらには追跡行列の上下反転により、そのような欠測値推定をスムーズに行い、従来よりも効率よく、より多くの欠測値を的確に推定することができる。したがって、追跡行列中に多くの欠測値がある場合にも精度のよい３次元形状抽出が可能になる。また、撮影中の対象物体の回転の方向と、計測行列から得られた３次元データにより表される特徴点の運動方向とが不一致の場合に凹凸反転を行うことにより、対象物体の表面の凹凸も正確に抽出可能である。
【図面の簡単な説明】
【図１】擬似中心射影モデルの説明図である。
【図２】本発明による３次元形状抽出システムの構成図である。
【図３】画像入力部の処理フローを示すフローチャートである。
【図４】２次元演算部の処理フローを示すフローチャートである。
【図５】追跡行列の欠測値の推定方法の説明図である。
【図６】追跡行列の一例を示す図である。
【図７】追跡行列の整列処理の説明図である。
【図８】欠測値推定処理フローの一例を示すフローチャートである。
【図９】３次元演算部の処理フローを示すフローチャートである。
【図１０】形状凹凸判断／推定処理を示すフローチャートである。
【図１１】本発明をソフトウェアで実現するために利用するコンピュータの一例を示すブロック図である。
【符号の説明】
１００  回転台
１０２  対象物体
１０４  回転駆動機構
１０６  駆動部
１０８  デジタルビデオカメラ
１１０  画像入力部
１１２  ２次元演算部
１１４  ３次元演算部
１１６  パソコン
【図１】
0003711203.tif 000035
【図２】
0003711203.tif 000036
【図３】
0003711203.tif 000037
【図４】
0003711203.tif 000038
【図５】
0003711203.tif 000039
【図６】
0003711203.tif 000040
【図７】
0003711203.tif 000041
【図８】
0003711203.tif 000042
【図９】
0003711203.tif 000043
【図１０】
0003711203.tif 000044
【図１１】
0003711203.tif 000045