(57)【要約】【課題】動画像中の被写体の概略形状情報から、時間方向に滑らかで、かつ、精度の良い形状情報を得る。【解決手段】入力された動画像及び概略形状を表すマスクデータを時間方向に連結して３次元時空間画像とする３次元化部１０２と、マスクデータにチャイルドボックスを設定するチャイルドボックス設定部１０３と、各チャイルドボックスに対応する画像上の領域と相似する画像用ペアレントボックスを探索する画像用ペアレントボックス探索部１０４と、各画像用ペアレントボックスに対応するマスクデータ上の領域及び各チャイルドボックスを用いてマスクデータを修正するマスク修正部１０５とを備える。【選択図】  図１
2004240913.tif 000002
【特許請求の範囲】
【請求項１】
３次元画像を入力する画像入力部と、
前記３次元画像中で物体が占める概略の領域を表す３次元形状データを入力する形状入力部と、
前記３次元形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記形状データの修正処理の単位となる３次元領域であるチャイルドボックスを複数設定するチャイルドボックス設定部と、
前記３次元画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元画像中の領域である画像用ペアレントボックスを探索する画像用ペアレントボックス探索部と、
前記３次元形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので修正する形状データ修正部と、
修正した３次元形状データを出力する出力部と、
を備える物体形状算出装置。
【請求項２】
動画像を入力する画像入力部と、
動画像の各フレームにおいて物体が占める概略の領域を表す２次元形状データを入力する形状入力部と、
前記動画像及び前記２次元形状データとそれぞれを時間方向に連結し、３次元時空間画像及び３次元時空間形状データにする、３次元化部と、
前記３次元時空間形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記３次元時空間形状データの修正処理の単位となる領域であるチャイルドボックスを複数設定するチャイルドボックス設定部と、
前記３次元時空間画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元時空間画像中の領域である画像用ペアレントボックスを探索する画像用ペアレントボックス探索部と、
前記３次元時空間形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元時空間形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので修正する形状データ修正部と、
修正した３次元時空間形状データを出力する出力部と、
を備える物体形状算出装置。
【請求項３】
３次元画像データを入力する画像入力ステップと、
前記３次元画像において物体が占める概略の領域を表す３次元形状データを入力する形状入力ステップと、
前記３次元形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記３次元形状データの修正処理の単位となる領域であるチャイルドボックスを複数設定するチャイルドボックス設定ステップと、
前記３次元画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元画像中の領域である、画像用ペアレントボックスを探索する画像用ペアレントボックス探索ステップと、
前記３次元形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので置き換える置換ステップと、
前記３次元形状データを出力する出力ステップと、
を備える物体形状算出方法。
【請求項４】
動画像を入力する画像入力ステップと、
前記動画像の各フレームにおいて物体が占める概略の領域を表す時系列２次元形状データを入力する形状入力ステップと、
前記動画像の各フレームを時間方向に連結して３次元時空間画像を生成するとともに、前記時系列２次元形状データを時間方向に連結して３次元時空間形状データを生成する３次元化ステップと、
前記３次元時空間形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記３次元時空間形状データの修正処理の単位となる領域であるチャイルドボックスを複数設定するチャイルドボックス設定ステップと、
前記３次元時空間画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元時空間画像中の領域である、画像用ペアレントボックスを探索する画像用ペアレントボックス探索ステップと、
前記３次元時空間形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元時空間形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので置き換える置換ステップと、
前記３次元時空間形状データを時系列的な２次元形状データにする２次元化ステップと、
前記時系列的な２次元形状データを出力する出力ステップと、
を備える物体形状算出方法。
【請求項５】
前記置換ステップを複数回反復することを特徴とする請求項４記載の物体形状算出方法。
【請求項６】
前記チャイルドボックス設定ステップと、前記ペアレントボックス探索ステップと、前記置換ステップとを、
チャイルドボックスの大きさを小さくしながら複数回反復して実行することを特徴とする請求項４記載の物体形状算出方法。
【請求項７】
前記画像入力ステップでは、
前記動画像の各フレームの端から外側に所定の範囲にわたって、前記端の画素のデータをコピーするとともに、
前記動画像の先頭のフレームを所定の枚数、前記動画像の先頭に付加し、
前記動画像の終端のフレームを所定の枚数、前記動画像の終端に付加することを特徴とする請求項４記載の物体形状算出方法。
【請求項８】
前記形状入力ステップでは、
前記時系列２次元形状データの端から外側に所定の範囲にわたって、前記端の画素のデータをコピーするとともに、
前記動画像の先頭フレームに対応する前記時系列２次元形状データを所定の枚数、前記時系列２次元形状データの先頭に付加し、
前記動画像の終端フレームに対応する前記時系列２次元形状データを所定の枚数、前記時系列２次元形状データの終端に付加することを特徴とする請求項４記載の物体形状算出方法。
【請求項９】
前記３次元化ステップでは、動画像の一部区間に注目して、注目する区間の範囲を変えながら、当該区間の動画像を用いて３次元時空間画像を生成するとともに、当該区間に対応する時系列２次元形状データから３次元時空間形状データを生成し、
生成した３次元時空間画像と３次元時空間形状データとの組のそれぞれに対して、前記チャイルドボックス設定ステップ、前記ペアレントボックス探索ステップ、前記置換ステップ、２次元化ステップ及び出力ステップを実行する請求項４記載の物体形状算出方法。
【請求項１０】
請求項９記載の物体形状算出方法であって、
前記区間の範囲を変える際は、直前に設定した範囲と少なくとも一部が重複するようにすることを特徴とする請求項９記載の物体形状算出方法。
【請求項１１】
前記チャイルドボックス設定ステップでは、以前に設定されたチャイルドボックスについてはその設定をそのまま用いることを特徴とする請求項１０記載の物体形状算出方法。
【請求項１２】
前記３次元化ステップでは、あるフレームに対応する時系列２次元形状データが存在しない場合は、既知の２次元形状データから予測した当該フレームの２次元形状データを用いて３次元時空間形状データを生成することを特徴とする請求項９記載の物体形状算出方法。
【請求項１３】
コンピュータに、
３次元画像データを入力する画像入力ステップと、
前記３次元画像において物体が占める概略の領域を表す３次元形状データを入力する形状入力ステップと、
前記３次元形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記３次元形状データの修正処理の単位となる領域であるチャイルドボックスを複数設定するチャイルドボックス設定ステップと、
前記３次元画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元画像中の領域である、画像用ペアレントボックスを探索する画像用ペアレントボックス探索ステップと、
前記３次元形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので置き換える置換ステップと、
前記３次元形状データを出力する出力ステップと、
を実行させるための物体形状算出プログラム。
【請求項１４】
コンピュータに、
動画像を入力する画像入力ステップと、
前記動画像の各フレームにおいて物体が占める概略の領域を表す時系列２次元形状データを入力する形状入力ステップと、
前記動画像の各フレームを時間方向に連結して３次元時空間画像を生成するとともに、前記時系列２次元形状データを時間方向に連結して３次元時空間形状データを生成する３次元化ステップと、
前記３次元時空間形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記３次元時空間形状データの修正処理の単位となる領域であるチャイルドボックスを複数設定するチャイルドボックス設定ステップと、
前記３次元時空間画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元時空間画像中の領域である、画像用ペアレントボックスを探索する画像用ペアレントボックス探索ステップと、
前記３次元時空間形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元時空間形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので置き換える置換ステップと、
前記３次元時空間形状データを時系列的な２次元形状データにする２次元化ステップと、
前記時系列的な２次元形状データを出力する出力ステップと、
を実行させるための物体形状算出プログラム。
【請求項１５】
コンピュータを、
３次元画像を入力する画像入力手段、
前記３次元画像中で物体が占める概略の領域を表す３次元形状データを入力する形状入力手段、
前記３次元形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記形状データの修正処理の単位となる３次元領域であるチャイルドボックスを複数設定するチャイルドボックス設定手段、
前記３次元画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元画像中の領域である画像用ペアレントボックスを探索する画像用ペアレントボックス探索手段、
前記３次元形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので修正する形状データ修正手段、並びに、
修正した３次元形状データを出力する出力手段、
として機能させる物体形状算出プログラム。
【請求項１６】
コンピュータを、
動画像を入力する画像入力手段、
動画像の各フレームにおいて物体が占める概略の領域を表す２次元形状データを入力する形状入力手段、
前記動画像及び前記２次元形状データとそれぞれを時間方向に連結し、３次元時空間画像及び３次元時空間形状データにする、３次元化手段、
前記３次元時空間形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記３次元時空間形状データの修正処理の単位となる領域であるチャイルドボックスを複数設定するチャイルドボックス設定手段、
前記３次元時空間画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元時空間画像中の領域である画像用ペアレントボックスを探索する画像用ペアレントボックス探索手段、
前記３次元時空間形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元時空間形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので修正する形状データ修正手段、
修正した３次元時空間形状データを出力する出力手段、
として機能させる物体形状算出プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、動画像中に映っている所望の物体の形状を求める装置、方法並びにプログラムに関する。
【０００２】
【従来の技術】
物体と背景とが混在する画像から、ある特定の物体（被写体）のみが写っている領域を抽出する物体領域抽出技術は、静止画のみならず動画像の加工及び編集にも用いられる。例えば、動画像中に映っている人物を抽出し、別の背景に合成する等の利用法がある。
【０００３】
画像から被写体が写っている領域を抽出する際には、予め調べておいた被写体と背景との境界（被写体の形状）を用いて、画像中において被写体が存在する領域の画素を抽出する。従って、被写体の形状を高い精度で取得することが重要である。
【０００４】
従来、画像中の被写体の形状を高い精度で取得する技術の１つに次のようなものがある。まず、被写体のおおまかな形状を与える（例えば、被写体の形状を手動で入力する）。そして、被写体の境界部分のもつ自己相似性を利用し、与えられた形状の補正を行うことにより、精度の高い形状を求めるというものである（例えば、特許文献１）。
【０００５】
【特許文献１】
特開２０００−８２１４５公報
【０００６】
【発明が解決しようとする課題】
特許文献１に示された手法では、被写体の形状補正を動画像のフレームごとに独立して行っている。すなわち、特許文献１の手法では、２次元で形状補正を行い、フレーム間における形状の相関を考慮していないため、時間方向に関して滑らかでない形状が得られることがある。
【０００７】
時間方向に関して滑らかでない形状を用いて動画像から被写体を抽出すると、再生の際に被写体の一部あるいは全部がちらついて見えるという問題が起こることがある。
【０００８】
そこで、本発明では、動画像中の対象となる被写体の概略形状から、時間方向に対しても滑らかであり、かつ、高精度な形状を求めるための装置および方法を提供することを目的とする。
【０００９】
【課題を解決するための手段】
上記課題を解決するために、本発明の物体形状算出装置は、３次元画像を入力する画像入力部と、前記３次元画像中で物体が占める概略の領域を表す３次元形状データを入力する形状入力部と、前記３次元形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記形状データの修正処理の単位となる３次元領域であるチャイルドボックスを複数設定するチャイルドボックス設定部と、前記３次元画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元画像中の領域である画像用ペアレントボックスを探索する画像用ペアレントボックス探索部と、前記３次元形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので修正する形状データ修正部と、修正した３次元形状データを出力する出力部とを備える。
【００１０】
本発明の物体形状算出方法は、３次元画像データを入力する画像入力ステップと、前記３次元画像において物体が占める概略の領域を表す３次元形状データを入力する形状入力ステップと、前記３次元形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記３次元形状データの修正処理の単位となる領域であるチャイルドボックスを複数設定するチャイルドボックス設定ステップと、前記３次元画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元画像中の領域である、画像用ペアレントボックスを探索する画像用ペアレントボックス探索ステップと、前記３次元形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので置き換える置換ステップと、前記３次元形状データを出力する出力ステップとを備える。
【００１１】
本発明の物体形状算出プログラムは、コンピュータに、３次元画像データを入力する画像入力ステップと、前記３次元画像において物体が占める概略の領域を表す３次元形状データを入力する形状入力ステップと、前記３次元形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記３次元形状データの修正処理の単位となる領域であるチャイルドボックスを複数設定するチャイルドボックス設定ステップと、前記３次元画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元画像中の領域である、画像用ペアレントボックスを探索する画像用ペアレントボックス探索ステップと、前記３次元形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので置き換える置換ステップと、前記３次元形状データを出力する出力ステップとを実行させる。
【００１２】
また、本発明の物体形状算出プログラムは、コンピュータを、３次元画像を入力する画像入力手段、前記３次元画像中で物体が占める概略の領域を表す３次元形状データを入力する形状入力手段、前記３次元形状データを用いて、前記物体と前記物体以外の背景との境界面に沿って、前記形状データの修正処理の単位となる３次元領域であるチャイルドボックスを複数設定するチャイルドボックス設定手段、前記３次元画像中で前記チャイルドボックスと同じ位置にある領域の画素情報と相似し、前記チャイルドボックスより体積の大きい前記３次元画像中の領域である画像用ペアレントボックスを探索する画像用ペアレントボックス探索手段、前記３次元形状データ中で前記チャイルドボックスが示す領域の形状データを、前記３次元形状データ中で前記画像用ペアレントボックスと同じ位置にある領域の形状データを前記チャイルドボックスの大きさに縮小したもので修正する形状データ修正手段、並びに、修正した３次元形状データを出力する出力手段として機能させる。
【００１３】
【発明の実施の形態】
（第１の実施形態）以下、図面を参照して本発明の第１の実施形態について説明する。
【００１４】
（概要）本実施形態の物体形状算出装置は、動画像内における所望の物体についての形状を求めるのに好適な装置である。
【００１５】
本装置は、形状を求めたい物体（被写体）が写っている動画像と、この動画像の全フレームにおける被写体の概略形状データとを入力として受ける。そして、動画像を用いて概略形状データを修正して高精度な形状データを算出して出力する。
【００１６】
本装置では、概略形状データはビットマップとする。例えば、被写体に相当する画素は１、被写体でない（例えば背景）画素は０という画素値を持った画像である。本装置では動画像の各フレームの画素数と、各フレームの概略形状データの画素数とは等しいものとする。
【００１７】
尚、概略形状データの画素数は画像の画素数と一致していなくても良い。例えば、概略形状データの縦横の画素数を画像の縦横の画素数よりも多く（例えば縦横それぞれ２倍）すれば、形状算出処理の高精度化が期待できる。一方、概略形状データの縦横の画素数を画像の縦横の画素数よりも少なく（例えば縦横それぞれ半分）すれば、形状算出処理の高速化が期待できる。
【００１８】
本装置では、動画像を、各フレームを時間方向に重ねた３次元時空間画像として扱う。すると、被写体はフレームの縦横に加えて時間方向にも広がる３次元物体となる（以下、３Ｄ物体）。各フレームの概略形状データも同様にして時系列的に積み上げて、３次元物体の概略形状データとして扱う（以下、３Ｄ概略形状データ）。
【００１９】
本装置では、３次元画像における３Ｄ物体の表面の自己相似性を利用して、３Ｄ概略形状データを修正することにより、時間方向に関しても滑らかな形状を求める。３次元画像とは、３方向の広がりを持つ画像のことである。例えば（縦、横、奥行き）の３方向の広がりを持つ画像である。（縦、横、時間）の３方向の広がりを持つ３次元時空間画像も３次元画像の一種である。
【００２０】
具体的には次のような処理を行う。まず、３Ｄ概略形状データにおいて、物体と非物体（背景）との境界面に直方体状の領域を複数設定する。これらの直方体状の領域それぞれをチャイルドボックスと呼ぶ。チャイルドボックスを設定する際には、内部に境界面が含まれるようにする。
【００２１】
次に、３次元画像において、３Ｄ概略形状データで設定した各チャイルドボックスと同じ位置にある領域に注目する。これらの領域を「画像用チャイルドボックス」と呼ぶ。
【００２２】
そして、３次元画像において、各画像用チャイルドボックスについて、各画像用チャイルドボックスより体積が大きくて、かつ、内部に含まれる画素情報が各画像用チャイルドボックスと最も相似する直方体状領域である画像用ペアレントボックスを求める。
【００２３】
異なる大きさの２つの領域が「相似する」とは、２つの領域の大きさを揃えた時に、内部に含まれる画素情報の相関が高くなる、ことを意味する。
【００２４】
従って、最も相似する画像用ペアレントボックスを求めるには、例えば、複数の画像用ペアレントボックス候補領域について、各候補領域の大きさを画像用チャイルドボックスの大きさに縮小した上で、画像用チャイルドボックスとの相関を求め、最も相関が高い候補領域を画像用ペアレントボックスとして選択すれば良い。相関については、内部に含まれる画素値の類似度で判定する。
【００２５】
最後に、３Ｄ概略形状データにおいて、３次元画像で探索した各画像用ペアレントボックスと同じ位置にある領域に注目する。これらの領域を「ペアレントボックス」と呼ぶ。そして、３Ｄ概略形状データにおいて、各チャイルドボックスを、それぞれに対応するペアレントボックスをチャイルドボックスのサイズに縮小したもので置換する。置換により３Ｄ概略形状データの境界面が３Ｄ物体の表面に近づく。修正後の３Ｄ概略形状データを３Ｄ形状データと呼ぶ。
【００２６】
前述したように、３Ｄ概略形状データは各フレームの概略形状データを時系列的に積み上げたものである。従って、３Ｄ形状データを時系列的に切り出すことで、各フレームにおける被写体の形状データを得ることができる。
【００２７】
（構成）以下、図面を参照して本実施形態の物体形状算出装置の構成を説明する。
【００２８】
本装置は、以下の構成を備える。
・被写体が写っている動画像の全フレームの画像と、被写体の概略形状を表す全フレーム分のマスクデータとを入力する入力部１０１。
・動画像の全フレーム及び全フレーム分のマスクデータのそれぞれを、時間方向に連結し、３次元時空間画像及び３次元マスクデータを生成する３次元化部１０２。
【００２９】
・３次元マスクデータにおいて、被写体とそれ以外（以下、背景）との境界面に沿って、チャイルドボックスと呼ばれる直方体状領域を設定するマスク用チャイルドボックス設定部１０３。
・３次元時空間画像において、３次元マスクデータで設定したチャイルドボックスと同じ位置にある領域である、画像用チャイルドボックスに注目し、各画像用チャイルドボックスより体積が大きくて、かつ、内部に含まれる画素情報が各画像用チャイルドボックスと最も相似する直方体状領域である画像用ペアレントボックスを探索する画像用ペアレントボックス探索部１０４。
【００３０】
・３次元マスクデータにおいて、３次元時空間画像で探索した画像用ペアレントボックスと同じ位置にある領域である、ペアレントボックスに注目し、３次元マスクデータにおいて、各チャイルドボックスそれぞれを、それぞれに対応するペアレントボックスをチャイルドボックスと同じ大きさに縮小したもので置換して３次元マスクデータを修正するマスク修正部１０５。
・修正された３次元マスクデータを時系列的に並んだデータに戻す２次元化部１０６。
・２次元化されたマスクデータを出力するマスク出力部１０７。
【００３１】
以下、各部について説明する。
【００３２】
（入力部１０１）入力部１０１では、被写体が写っている動画像の全フレームと被写体の概略形状を表すマスクデータの全フレーム分とを入力する。マスクデータは、被写体が存在する領域と存在しない領域とが識別可能であれば、どのように与えても良い。本実施形態では人間が手動で描いた概略形状を用いる。
【００３３】
（３次元化部１０２）３次元化部１０２では、動画像の全フレームと全マスクデータとをそれぞれ時間方向に連結して、それぞれ３次元時空間画像（３Ｄ画像）及び３次元時空間マスクデータ（３Ｄマスクデータ）を生成する。「（時間方向に）連結する」とは、各フレームの２次元画像を時間方向に厚さ△ｔを持った３次元時空間画像とみなして、時間方向に時間順に繋げていくことを意味する。
【００３４】
図２は連結する様子を説明する図である。フレーム２０１−１〜２０１−５には、動いている被写体２０３が写っている。また、各フレームには概略形状２０２が与えられている。尚、図２では説明を簡単にするために概略形状２０２と被写体２０３とが同一画像上にあるように表現してあるが、実際は別々のデータとして存在する。
【００３５】
フレーム２０１−１〜２０１−５の被写体２０３だけを抜き出して表現したのが被写体２０４である。被写体２０４は時間とともに動いているので、フレーム２０１−１〜２０１−５を時間方向に連結して３次元時空間画像にすると、３次元物体画像２０５のように曲がった筒状の３次元画像として表現される（動いていなければ、真っ直ぐな筒状になる）。尚、図２では被写体２０４は画面内で横方向に動いていない（縦方向のみに動いている）ので、３次元物体画像２０５も縦方向（垂直方向）にのみ曲がっている。
【００３６】
概略形状２０２についても同様で、連結を行うと、物体が存在する領域は筒状の３次元画像として表現される。
【００３７】
（チャイルドボックス設定部１０３）マスク用チャイルドボックス設定部１０３では、３Ｄマスクデータにおける被写体と背景との境界面に沿ってチャイルドボックスと呼ばれる直方体状の関心領域を設定する。チャイルドボックス内に境界面が入るように設定を行う。望ましくは、境界面がチャイルドボックスの重心あるいはその近傍を通るようにすると良い。
【００３８】
図３（Ａ）及び（Ｂ）はチャイルドボックスを設定する様子を説明する図である。この図は説明を簡単にするために、３Ｄマスクデータの一部分を時間方向に垂直な面に沿って切り出して表現している。図３（Ａ）に示すように、３Ｄマスクデータ３０１の境界面に沿ってチャイルドボックス３０２を設定する。この時、チャイルドボックスの重心が境界面を通るようにすると良い。そして、図３（Ｂ）に示すように、３Ｄマスクデータ３０１の境界面を埋め尽くすようにチャイルドボックス３０２を複数設定する。
【００３９】
（画像用ペアレントボックス探索部１０４）画像用ペアレントボックス探索部１０４では、３Ｄ画像において、３Ｄマスクデータで設定した各チャイルドボックスと同じ位置にある領域に注目する。これらの領域を画像用チャイルドボックスと呼ぶ。そして、各画像用チャイルドボックスについて、各画像用チャイルドボックスと最も相似する領域であり、かつ、各画像用チャイルドボックスより体積が大きい直方体状の領域である画像用ペアレントボックスの探索を行う。
【００４０】
前述したように、探索にあたっては複数の画像用ペアレントボックス候補領域のうち、画像用チャイルドボックスと最も相似する候補領域を画像用ペアレントボックスとする。具体的には、画像用ペアレントボックス候補領域と画像用チャイルドボックスとの間で内部に含まれる画素の類似度を計算することにより行う。類似度の計算は、例えば、画像用チャイルドボックスを画像用ペアレントボックスの大きさに引き伸ばした上で、画素値の差分絶対値和（ＳＡＤ）若しくは差分２乗和（ＳＳＤ）を求めれば良い。あるいは各候補領域を画像用チャイルドボックスの大きさに縮小して画素値のＳＡＤ若しくはＳＳＤを求めても良い。
【００４１】
画像用ペアレントボックス候補は、画像用チャイルドボックスの重心を中心とする所定の範囲内（例えば１０画素×１０画素×１０画素）に重心を持つものを用いる。
【００４２】
（マスク修正部１０５）マスク修正部１０５では、３Ｄマスクデータにおいて、３Ｄ画像で探索した各画像用ペアレントボックスと同じ位置にある領域に注目する。これらの領域をペアレントボックスと呼ぶ。そして、各ペアレントボックスと各チャイルドボックスとを用いて、３Ｄマスクデータの修正を行う。
【００４３】
図４（Ａ）〜（Ｄ）はマスクデータの修正を説明する図である。尚、説明を簡単にするために図面は２次元で表現してある。
【００４４】
図４（Ａ）は３Ｄマスクデータ４００上にペアレントボックス４０１とチャイルドボックス４０２との設定が終わった段階である。これから３Ｄマスクデータ４００の境界面４０３を修正していく。ここでは仮想的に被写体と背景との真の境界面４０４も表示してある。
【００４５】
ペアレントボックス４０１を設定する位置は、３Ｄ画像においてチャイルドボックス４０２との相似性が最高になる位置になっている。３Ｄ画像における相似性が高いということは、真の境界面４０４に関して相似性が高いことになる。従って、ペアレントボックス４０１とチャイルドボックス４０２とでは、真の境界面４０４の部分がほぼ一致するようになっている。
【００４６】
３Ｄマスクデータ４００の修正は次のように行う。まず、３Ｄマスクデータ４００から、ペアレントボックス４０１で指定される領域を抽出する。図４（Ｂ）はペアレントボックス４０１で指定される領域のみを示した図である。
【００４７】
次に、抽出した領域をチャイルドボックス４０２と同じ大きさに縮小して、置換ボックス４０５を生成する。図４（Ｃ）は置換ボックス４０５を示した図である。
【００４８】
そして、３Ｄマスクデータ４００において、チャイルドボックス４０２で示される領域の画素を置換ボックス４０５の画素で置換する。図４（Ｄ）は置換を行った後の３Ｄマスクデータ４００を示す図である。置換を行うことにより、境界面４０３は真の境界面４０４に接近する。
【００４９】
３Ｄマスクデータに設定した全てのチャイルドボックスに関して、上述した修正を行う。
【００５０】
（２次元化部１０６）２次元化部１０６は、修正した３Ｄマスクデータを時間方向に△ｔ間隔で切り出し、２次元のマスクデータとする。
【００５１】
（マスクデータ出力部１０７）マスクデータ出力部１０７は、２次元のマスクデータを出力する。
【００５２】
（実現手段）本実施形態の物体形状算出装置は、コンピュータで動作させるプログラムとして実現される。すなわち、コンピュータに上述の各部の機能を実現させる物体形状算出プログラムである。尚、本装置の一部あるいは全部を半導体集積回路等のハードウエアとして実現しても良い。
【００５３】
図５は、本実施形態の物体形状算出プログラムを動作させるコンピュータの一例を示す図である。
【００５４】
このコンピュータは中央演算処理装置５０１と、本テクスチャ圧縮プログラム及び処理途中のデータの一時記憶を行うメモリ５０２と、本テクスチャ圧縮プログラム、圧縮前のデータや圧縮後のデータを格納する磁気ディスクドライブ５０３と、光ディスクドライブ５０４を備える。
【００５５】
また、ＬＣＤやＣＲＴ等の表示装置５０８と、表示装置５０８に画像信号を出力するインターフェースである画像出力部５０５と、キーボードやマウス等の入力装置５０９と、入力装置５０９からの入力信号を受けるインターフェースである入力受け付け部５０６とを備える。
【００５６】
また、この他に、外部装置との接続インターフェース（例えばＵＳＢ、ネットワークインターフェースなど）である出入力部５０７を備える。
【００５７】
本実施形態の物体形状算出プログラムは予め磁気ディスクドライブ５０２に格納しておく。そして、物体形状算出する際に、磁気ディスクドライブ５０３から読み出されてメモリ３０２に格納され、中央演算処理装置５０１において実行される。
【００５８】
実行結果として生成されるマスクデータは磁気ディスクドライブ５０３に格納する。また、物体形状算出の過程において、利用者に処理状況等の情報を提示したり、あるいは何らかの入力を促すためのＧＵＩを適宜画像出力部５０５を介して表示装置５０８に表示させる。
【００５９】
尚、物体形状算出の結果生じるマスクデータは、磁気ディスクドライブ５０３に格納するだけでなく、プロセス間通信の機能（共有メモリ、パイプ等）を用いて、マスクデータを必要とする他のプログラムに出力しても良い。
【００６０】
また、本実施形態では、物体形状算出プログラムは、コンピュータで動作しているＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）と協働して動作する。
【００６１】
（動作）以下、図面を参照しながら本実施形態の動作を説明する。図６は本実施形態の物体形状算出装置の動作を説明する図である。
【００６２】
（ステップ６０１）被写体が写っている動画像Ｉ＝｛Ｉ１、Ｉ２・・・Ｉｎ｝と、被写体の概略形状のマスクデータＲ＝｛Ｒ１、Ｒ２・・・Ｒｎ｝とを入力する。そして、入力された動画像及び概略形状マスクデータを１フレームずつ順次蓄積する。尚、Ｉｋ及びＲｋは、それぞれ１フレーム分のデータを表す。
【００６３】
（ステップ６０２）動画像の各フレームＩｋと各フレームの概略形状マスクデータＲｋとのそれぞれを時間方向について連結して、それぞれ３次元時空間画像Ｉ（３Ｄ画像Ｉ）、３次元時空間マスクデータＲ（３ＤマスクデータＲ）を生成する。
【００６４】
（ステップ６０３）３ＤマスクデータＲにおいて、被写体と背景との境界面に沿ってチャイルドボックスＣ＝｛ｃ（１）、ｃ（２）・・・ｃ（Ｎ）｝を設定する。３Ｄ画像Ｉにおいて、各チャイルドボックスＣ（ｉ）と同じ位置にある領域にも注目し、これらをチャイルドボックスＣ’＝｛ｃ’（１）、ｃ’（２）・・・ｃ’（Ｎ）｝と呼ぶ。
【００６５】
本実施形態では各チャイルドボックスｃ（ｉ）及びｃ’（ｉ）の形状を直方体とし、大きさは縦（３Ｄマスクデータの空間方向の一方）に８画素、横（３Ｄマスクデータの空間方向の他方）に８画素、奥行き（３Ｄマスクデータの時間方向）に４画素としておく。ただし、形状及び大きさはこれ以外のものでも良い。例えば一辺が８画素の立方体でも良い。
【００６６】
各チャイルドボックスｃ（ｉ）及びｃ’（ｉ）は、それぞれの重心が境界面を通るように設定する。また、チャイルドボックスＣは境界面を埋め尽くすように多数設定する。
【００６７】
（ステップ６０４）３Ｄ画像Ｉにおいて、ペアレントボックスＰ’＝｛ｐ’（１）、ｐ’（２）・・・ｐ’（Ｎ）｝を探索して設定する。また、３Ｄマスクデータにおいて、各ペアレントボックスｐ’（ｉ）と同じ位置にある領域にも注目し、これらをペアレントボックスＰ＝｛ｐ（１）、ｐ（２）・・・ｐ（Ｎ）｝と呼ぶ。
【００６８】
３Ｄ画像Ｉにおいて、各チャイルドボックスｃ’（ｉ）のペアレントボックスｐ’（ｉ）を探索する。探索は、各チャイルドボックスｃ’（ｉ）の重心を中心とする所定の範囲内（例えば１０画素×１０画素×１０画素の範囲）で行う。この範囲内に重心を持つペアレントボックスｐ’（ｉ）の候補とチャイルドボックスｃ’（ｉ）との間での相似性を求め、最も相似する候補をペアレントボックスｐ’（ｉ）とする。
【００６９】
相似性の算出は、ペアレントボックスｐ’（ｉ）の候補とチャイルドボックスｃ’（ｉ）との間で内部に含まれる画素の類似度を計算することにより行う。類似度の計算は、例えば、チャイルドボックスｃ’（ｉ）をペアレントボックスｐ’（ｉ）の大きさに拡大した上で、画素値の差分絶対値和（ＳＡＤ）を求めれば良い。
【００７０】
別の類似度の計算としては、絶対値差分和に限らず、画素値の差分２乗和（ＳＳＤ）を用いても良い。いわゆるブロックマッチングを３次元的に行うので、ブロックマッチングにおいて類似度や相関を求める手法を応用することができる。
【００７１】
ペアレントボックスＰ’とチャイルドボックスＣ’との関係は、ペアレントボックスＰ’の方がチャイルドボックスＣ’よりも体積が大きいことを除いて自由である。チャイルドボックスＣ’の３辺を均等な倍率で拡大したものでなくても良い。本実施形態ではペアレントボックスＰは全て（１６画素×１６画素×８画素）とする。ペアレントボックスＰとチャイルドボックスＣの関係もまた同様である。
【００７２】
例えば、チャイルドボックスＣ’が（８画素×８画素×８画素）の立方体であった時に、ペアレントボックスＰ’が（１２画素×１６画素×２４画素）の直方体であっても良い。あるいは、チャイルドボックスＣが（８画素×８画素×４画素）の直方体であった時に、ペアレントボックスＰが（１２画素×１２画素×４画素）の直方体であっても良い。
【００７３】
（ステップ６０５）３ＤマスクデータＲにおいて、各チャイルドボックスｃ（ｉ）と、これに対応するペアレントボックスｐ（ｉ）とを用いて３ＤマスクデータＲの修正を行う。
【００７４】
まず、３ＤマスクデータＲから各チャイルドボックスｃ（ｉ）に対応するペアレントボックスｐ（ｉ）が示す領域の画素情報を抽出する。次に、抽出した画素情報をチャイルドボックスと同じ大きさに縮小した置換ボックスＲ’を生成する。そして、３Ｄマスクデータにおいてチャイルドボックスが示す領域の画素情報を置換ボックスＲ’の画素情報で置き換えて修正する。
【００７５】
尚、置き換え処理は１回でも良いが、複数回行うとよりマスクデータを修正する効果が高くなる。
【００７６】
置き換え処理を１回行うことにより、真の境界面と３ＤマスクデータＲにおける境界面との誤差は、各チャイルドボックスｃ（ｉ）の大きさに対する、それぞれに対応するペアレントボックスｐ（ｉ）の大きさの比率の逆数倍になる。
【００７７】
誤差が収束するのに必要な置き換え回数、すなわち誤差が１画素以下となる条件は、各チャイルドボックスｃ（ｉ）と対応するペアレントボックスｐ（ｉ）との大きさの比率によって変わる。
【００７８】
各チャイルドボックスｃ（ｉ）の最大の辺の長さをＬとすると、置き換え処理後に残る誤差は、Ｌ／２に各チャイルドボックスｃ（ｉ）に対する、それぞれに対応するペアレントボックスｐ（ｉ）との大きさの比率の逆数を、置き換え処理を行った回数だけ乗じた値になる。この残る誤差が１未満になった時点で収束したとみなせる。
【００７９】
上述したように、本実施形態では各チャイルドボックスｃ（ｉ）は直方体で縦・横・時間方向にそれぞれ８画素・８画素・４画素の大きさであり、対応するペアレントボックスが直方体で縦・横・時間方向にそれぞれ１６画素・１６画素・８画素の大きさであるから、上述の残る誤差が１未満になるには、３回の置き換え処理が必要であることになる。
【００８０】
本実施形態では、上述した残る誤差を収束させるという観点から本ステップの処理を３回繰り返すこととする。
【００８１】
（ステップ６０６）修正後の３ＤマスクデータＲからマスクデータＲｋを切り出して出力する。
【００８２】
ステップ６０２におけるマスクデータの連結処理と、反対の処理を行う。ステップ６０２では２次元のマスクデータを時間方向に連結したが、このステップでは時間方向に関して分離して２次元のマスクデータとする。
【００８３】
（本実施形態の効果）以上、本実施形態の物体形状算出装置ならば、時間方向についても形状算出を行っているので、動画像として再生した時に従来よりもちらつきを抑制された形状情報を得ることができる。
【００８４】
（第１の変形例）各チャイルドボックスｃ（ｉ）の大きさが大きくなるほど、１度に３ＤマスクデータＲを修正できる範囲が広くなるが、修正の精度は悪くなるという問題がある。
【００８５】
そこで、ステップ６０３〜ステップ６０５の処理を、大きいｃ（ｉ）及びｃ’（ｉ）で実施してから、より小さなｃ（ｉ）及びｃ’（ｉ）で実施し、さらに小さなｃ（ｉ）及びｃ’（ｉ）で実施するということを適宜繰り返せば、より広い範囲に対し効率良く高い精度で３ＤマスクデータＲを修正することができる。
【００８６】
例えば、最初はｃ（ｉ）及びｃ’（ｉ）の大きさを（８画素×８画素×８画素）で実施し、２回目は（４画素×４画素×４画素）で行うことが考えられる。あるいは（１６画素×１６画素×４画素）→（８画素×８画素×４画素）→（４画素×４画素×４画素）で行っても良い。
【００８７】
（第２の変形例）ステップ６０５の処理を複数回行って修正効果を高める旨を説明したが、ステップ６０３からステップ６０５までの処理を複数回（例えば２〜３回）繰り返しても良い。すなわち、チャイルドボックスＣの設定位置を変えて３ＤマスクデータＲの修正を行うということである。
【００８８】
特に、設定されたチャイルドボックスＣの一部（または全部）が真の境界面から外れている場合に有効である。繰り返し時にチャイルドボックスＣを再設定することで、チャイルドボックスＣが真の境界面を通るように設定される可能性が高くなるからである。
【００８９】
（第３の変形例）これまでは、動画像の各フレームを時間方向に連結した３次元時空間画像を扱ってきたが、より一般的に３次元画像を扱うことができる。つまり、今までは（Ｘ方向、Ｙ方向、時間方向）という３次元時空間であったが、（Ｘ方向、Ｙ方向、Ｚ方向）という３次元空間でも物体形状の算出を行える。
【００９０】
３次元画像としては、例えばＣＴやＭＲＩで取得した３次元物体のある方向に対する断面画像の集合を用いても良い。すなわち、入力部１０１で断面画像の集合とマスクデータとを入力し、３次元化部１０２で断面画像を断面に垂直な方向に連結して３次元画像を生成する。
【００９１】
（第４の変形例）ステップ６０４でペアレントボックスＰ’を探索する処理を高速に行うために、３Ｄ画像Ｉを、（ペアレントボックスの大きさ）／（チャイルドボックスの大きさ）倍に拡大した画像を用意しておいても良い。
【００９２】
ステップ６０４では各チャイルドボックスｃ’（ｉ）が示す領域を拡大してペアレントボックス候補が示す領域と比較していたが、これとは逆にペアレントボックス候補が示す領域を各チャイルドボックスｃ’（ｉ）のサイズに縮小して比較しても良い。この場合、３Ｄ画像Ｉを（チャイルドボックスの大きさ）／（ペアレントボックスの大きさ）倍に縮小した画像を用意しておいても良い。
【００９３】
（第５の変形例）概略形状データはベクトル情報であっても良い。すなわち、概略形状データは各フレームにおける被写体の形状を表す線分の集合であっても良い。
【００９４】
この場合、ステップ６０５における置換処理のたびに線分の集合を構成する要素を更新していく。
【００９５】
（第２の実施形態）以下、本発明の第２の実施形態について説明する。基本的な構成は第１の実施形態と同様である。
【００９６】
上述のステップ６０４においてペアレントボックスＰ’を探索する際に、３Ｄ画像Ｉの端の部分において３次元画像の外側を参照したくなることがある。このようなことは、例えば動画像の各フレームの端の方に被写体が写っている場合に起こり易い。
【００９７】
３Ｄ画像Ｉの外側への参照が起こらないように探索範囲を制限することも可能であるが、このような制限を課すとペアレントボックスＰ’とチャイルドボックスＣ’との相似性が低くなり、境界面の精度が悪くなることがある。
【００９８】
特に３次元時空間画像では、開始数フレーム及び終端数フレームの形状が不自然なものになるため、その影響が大きい。
【００９９】
そこで、３Ｄ画像Ｉの各方向について外側に拡張する。拡張した部分の画素については、最も近い端の画素をコピーするパディング処理を行うことにより補う。また、３次元マスクデータＲについても同様にパディング処理を行う。そして、パディング処理を行ってからペアレントボックスＰの探索を行う。
【０１００】
「最も近い端の画素をコピーする」とは、例えば、時間ｔ＝０が始点で時間ｔ＝１００が終点の時空間画像において、時間ｔ＝−１の位置に時間ｔ＝０と同じ画像をコピーする処理のことである。
【０１０１】
尚、本実施形態は３次元時空間画像に限らず、一般的な３次元画像においても適用可能である。
【０１０２】
このように、パディングを行った３次元画像及び３次元マスクデータを利用することにより、３次元マスクデータをより精度良く修正して、より正確な物体の形状を求めることができる。
【０１０３】
（第３の実施形態）以下、本発明の第３の実施形態について説明する。
【０１０４】
（概要）これまでは、動画像全体を一度に扱って被写体の形状を求めていた。本実施形態では動画像の数フレーム単位で逐次的に被写体の形状を求めていく。
【０１０５】
これにより、一度に扱うデータ量を減らすことができる。例えば非常に長い時間にわたる動画像を、少ないメモリの計算機で処理するのに有用である。
【０１０６】
図７は、本実施形態における処理の概要を説明する図である。図７は、動画像における被写体７０１のみを時間順に並べた図である。被写体７０１は動いているので、時間の経過とともに位置がずれている。
【０１０７】
本実施形態では、まず動画像の数フレーム分について形状を求める（第１の処理）。それから、次の数フレームに関して形状を求める（第２の処理）。このような動作を繰り返して（第３の処理、第４の処理・・・）、最終的に動画像全体にわたって、被写体の形状を求める。
【０１０８】
（動作）図８は本実施形態の物体形状算出装置の動作を説明する図である。以下の説明では一度にｎフレームずつ扱うものとしている。
【０１０９】
（ステップ８０１）動画像のうち、形状算出処理対象となるｎフレームの先頭位置の初期値を設定する。本実施形態では、第１フレームから処理を行っていく。
【０１１０】
（ステップ８０２）動画像のうち、形状算出処理対象となるｎフレーム分の画像及びマスクデータをメモリ上に読み込む。
【０１１１】
ｎフレーム分の画像を３Ｄ画像Ｉとして扱う。また、ｎフレーム分のマスクデータを３ＤマスクデータＲとして扱う。
【０１１２】
（ステップ８０３）第１の実施形態と同様にして、３ＤマスクデータＲと３Ｄ画像Ｉに対して、チャイルドボックスＣ、Ｃ’を設定する。
【０１１３】
（ステップ８０４）第１の実施形態と同様にして、３Ｄ画像Ｉにおいて、各チャイルドボックスＣ’に対応するペアレントボックスＰ’を探索する。探索したペアレントボックスＰ’と同位置にある３ＤマスクデータＲ上の領域をペアレントボックスＰとする。
【０１１４】
（ステップ８０５）第１の実施形態と同様にして、３ＤマスクデータＲにおいて、チャイルドボックスＣの画素情報をペアレントボックスＰを縮小したもので置換し、３ＤマスクデータＲの修正を行う。
【０１１５】
（ステップ８０６）３ＤマスクデータＲをフレーム単位に分割して出力する。
【０１１６】
（ステップ８０７）形状算出処理対象となるｎフレームの先頭位置をシフトする。
【０１１７】
（ステップ８０８）最終フレームまで形状算出処理が完了した場合は終了する。未完了の場合は次のｎフレームについてステップ８０２から処理を行う。
【０１１８】
（変形例）ここでは、先頭フレームから時間軸の順方向に対して処理を行う例を示したが、順序はこれに限定されず、例えば逆方向であっても良い。
【０１１９】
また、入力されている動画像及びマスクデータは、パディングしてあっても良い。
【０１２０】
また、ステップ８０３からステップ８０５の処理を、チャイルドボックスＣのサイズを変えながら複数回繰り返しても良い。例えば、最初は大きいチャイルドボックスで処理を行い、チャイルドボックスを小さくしながら繰り返すと良い。
【０１２１】
上述の説明では、ステップ８０２からステップ８０５の処理では、形状算出処理対象フレームが重複するため、同じフレームに対して何度も行うことになる。そこで、ステップ８０５で一度修正したマスクデータに対して、さらに修正を行うことになっても構わない。すなわち、ステップ８０２で読み込むマスクデータは、前にステップ８０５で修正済みのものであっても構わない。マスクデータの精度を向上させる効果が期待できる。
【０１２２】
また、形状算出処理対象フレームが重複するため、同じフレームのマスクデータの修正を何度も行うことになるので、前に配置したチャイルドボックスＣ及びペアレントボックスＰをそのまま用いても良い。このようにすると処理速度の面で有利であるし、３Ｄマスクデータの時間方向の滑らかさの点でも有利である。
【０１２３】
（本実施形態の効果）本実施形態ならば、動画像全体を一度に扱う必要がないので、少ないメモリでも形状算出処理を行うことができる。
【０１２４】
また、逐次的な処理方式なので、リアルタイムに入力される画像に対して、例えばフレーム間差分に基づく方法で被写体の初期形状を与え、その形状を修正しながら、被写体を切り出して出力するというリアルタイム処理に応用できる。
【０１２５】
（第４の実施形態）以下、本発明の第４の実施形態について説明する。
【０１２６】
ここでは、第３の実施形態で説明したマスクデータの逐次的に修正する手法と、第２の実施形態で説明したマスクデータ・画像に対してパディングを行ってから処理を行う手法とを組み合わせた実施形態について説明する。
【０１２７】
（動作）図９は本実施形態における処理の流れを説明する図である。
【０１２８】
（ステップ９０１）まず、動画像、マスクデータ及びボックス設定済みフラグをそれぞれ格納するためのキュー（先入れ先出し）バッファを初期化する。さらに、チャイルドボックスの座標とペアレントボックスの座標とを格納するためのバッファも初期化する。
【０１２９】
本実施形態では動画像、マスクデータ及びボックス設定済みフラグを格納するキューバッファのサイズは、１０フレーム分のデータを格納できるサイズとする。キューバッファのサイズは使用可能なメモリの大きさに応じて適宜変更してよい。
【０１３０】
ボックス設定済みフラグとは、マスクデータのどの部分にチャイルドボックスを設定されているかを確認するためのものである。マスクデータと同じデータ量のキューバッファで、マスクデータにチャイルドボックスを設定したら、それに対応するボックス設定済みフラグの領域のフラグを立てる。
【０１３１】
動画像のキューバッファ及びマスクデータのキューバッファの初期化では、先頭フレームの画像データ及びマスクデータで埋め尽くす処理を行う。これは、先頭フレーム以前における時間方向のパディングを行ったのと等価になる。
【０１３２】
ボックス設定済みフラグのキューバッファは初期化でクリアしておく。また、チャイルドボックスの座標及びペアレントボックスの座標を格納するバッファも初期化でクリアしておく。
【０１３３】
（ステップ９０２）キューバッファに読み込むフレームの番号ｋを初期化する。ここでは先頭フレームから読み込むので番号ｋに１をセットしておく。
【０１３４】
（ステップ９０３）動画像のキューバッファ及びマスクデータのキューバッファに、ｋ番目のフレームの画像及びマスクデータを読み込む。
【０１３５】
もしｋの値が最終フレームの番号を超えている場合は、最終フレームのデータをコピーする。これは、最終フレーム以降における時間方向のパディングを行うのと等価になる。
【０１３６】
（ステップ９０４）フレームｋに対応するマスクデータの被写体と背景との境界面付近にチャイルドボックスが設定されているかを調べ、設定されていない場合はチャイルドボックスを設定する。
【０１３７】
ボックス設定済みフラグのキューバッファにおいて境界面付近に対応する領域のフラグを調べる。フラグがクリアされていれば、チャイルドボックスが未設定である。
【０１３８】
チャイルドボックスが未設定ならば、マスクデータ及び動画像のキューバッファにおいて、チャイルドボックスを以下の条件を満たすように設定する。
・チャイルドボックスの重心がフレームｋの時間方向の中心付近を通る
・チャイルドボックスの重心が境界面の近傍を通る
チャイルドボックスを設定したら、ボックス設定済みフラグのキューバッファにおいて対応する領域のフラグをセットする。
【０１３９】
（ステップ９０５）ステップ９０４で新たに追加されたチャイルドボックスの各々に対し、対応するペアレントボックスの探索を行う。
【０１４０】
（ステップ９０６）全てのチャイルドボックスと、それぞれに対応するペアレントボックスとを用いてマスクデータの修正を行う。
【０１４１】
（ステップ９０７）キューから１フレーム分のマスクデータを取り出す。これは修正後のマスクデータであり、被写体の形状を精度良く表すものである。
【０１４２】
（ステップ９０８）次のフレームに注目するために、ｋに１を加算する。動画像のキューから１フレーム分のデータを削除する。また、削除されたフレームへの参照を含むチャイルドボックス及びペアレントボックスの座標をバッファから削除する。
【０１４３】
（ステップ９０９）処理終了条件の判定を行う。処理終了の条件は、例えば、「ステップ９０７で最終フレームのマスクデータを出力すること」である。この条件は、ｋの値が最後のフレーム番号＋キューバッファに格納可能なフレーム数より大きくなったか否かで判定すればよい。
【０１４４】
（第５の実施形態）以下、本発明の第５の実施形態について説明する。
【０１４５】
（概要）第３の実施形態、第４の実施形態では、全てのフレームについて予め概略形状のマスクデータを与えていた。これに対して、本実施形態は、先頭のフレームについてのみ概略形状のマスクデータを与えるだけで、全体のマスクデータを求めることができるというものである。
【０１４６】
（動作）図１０は、本実施形態の物体形状算出装置の処理の流れを説明する図である。
【０１４７】
（ステップ１００１）まず、動画像、マスクデータ及びボックス設定済みフラグをそれぞれ格納するためのキュー（先入れ先出し）バッファを初期化する。さらに、チャイルドボックスの座標とペアレントボックスの座標とを格納するためのバッファも初期化する。
【０１４８】
本実施形態では動画像、マスクデータ及びボックス設定済みフラグを格納するキューバッファのサイズは、１０フレーム分のデータを格納できるサイズとする。キューバッファのサイズは使用可能なメモリの大きさに応じて適宜変更してよい。
【０１４９】
動画像のキューバッファ及びマスクデータのキューバッファには、先頭フレームの画像データ及びマスクデータで埋め尽くす処理を行っておく。また、ボックス設定済みフラグのキューバッファはクリアしておく。そして、チャイルドボックスの座標及びペアレントボックスの座標を格納するバッファもクリアしておく。
【０１５０】
（ステップ１００２）キューバッファに読み込むフレームの番号ｋを初期化する。ここでは先頭フレームから読み込むので番号ｋに１をセットしておく。
【０１５１】
（ステップ１００３）動画像のキューバッファに、ｋ番目のフレームの画像を読み込む。
【０１５２】
もしｋの値が最終フレームの番号を超えている場合は、最終フレームのデータをコピーする。
【０１５３】
（ステップ１００４）マスクデータのキューバッファに、ｋ番目のフレームのマスクデータを設定する。
【０１５４】
ｋ番目のフレームに関するマスクデータを予測してキューバッファに設定する。予測は、ｋ番目以前で時間的に直近のフレーム（多くの場合はｋ−１番目のフレーム）のマスクデータをコピーすることで行う。
【０１５５】
尚、ｋ番目のフレームのマスクデータが既に存在する場合、例えば概略形状として与えられている場合等、はそれを用いても良い。
【０１５６】
（ステップ１００５）フレームｋに対応するマスクデータの被写体と背景との境界面付近にチャイルドボックスが設定されているかを調べ、設定されていない場合はチャイルドボックスを設定する。
【０１５７】
（ステップ１００６）ステップ１００５で新たに追加されたチャイルドボックスの各々に対し、対応するペアレントボックスの探索を行う。
【０１５８】
（ステップ１００７）全てのチャイルドボックスと、それぞれに対応するペアレントボックスとを用いてマスクデータの修正を行う。
【０１５９】
（ステップ１００８）キューから１フレーム分のマスクデータを取り出す。これは修正後のマスクデータであり、被写体の形状を精度良く表すものである。
【０１６０】
（ステップ１００９）次のフレームに注目するために、ｋに１を加算する。動画像のキューから１フレーム分のデータを削除する。また、削除されたフレームへの参照を含むチャイルドボックス及びペアレントボックスの座標をバッファから削除する。
【０１６１】
（ステップ１０１０）処理終了条件の判定を行う。終了していない場合はステップ１００３へ戻る。
【０１６２】
【発明の効果】
以上のように、本発明によれば、動画像中の対象となる被写体の概略形状情報から、時間方向に滑らかでかつ精度の高い形状情報を得ることが可能となる。
【図面の簡単な説明】
【図１】第１の実施形態の物体形状算出装置の構成を説明する図。
【図２】動画像を３次元時空間画像として扱う様子。
【図３】（Ａ）被写体と背景との境界面にチャイルドボックスｃ（ｉ）を設定する様子を説明する図。（Ｂ）境界面を埋め尽くすようにチャイルドボックスｃ（ｉ）を設定する様子を説明する図。
【図４】（Ａ）修正前のマスクデータを説明する図。（Ｂ）マスクデータにおいてペアレントボックスが示す領域を表示した図。（Ｃ）ペアレントボックスが示す領域の画素をチャイルドボックスの大きさに縮小したものを示した図。（Ｄ）修正後のマスクデータを説明する図。
【図５】第１の実施形態の物体形状算出装置を実現するプログラムを動作させるコンピュータの構成を説明する図。
【図６】第１の実施形態の物体形状算出装置の動作を説明する流れ図。
【図７】第３の実施形態における処理の概要を説明する図。
【図８】第３の実施形態における処理の流れを説明する図。
【図９】第４の実施形態における処理の流れを説明する図。
【図１０】第５の実施形態における処理の流れを説明する図。
【符号の説明】
１０１  入力部
１０２  ３次元化部
１０３  チャイルドボックス設定部
１０４  画像用ペアレントボックス探索部
１０５  マスク修正部
１０６  ２次元化部
１０７  マスク出力部
【図１】
2004240913.tif 000003
【図２】
2004240913.tif 000004
【図３】
2004240913.tif 000005
【図４】
2004240913.tif 000006
【図５】
2004240913.tif 000007
【図６】
2004240913.tif 000008
【図７】
2004240913.tif 000009
【図８】
2004240913.tif 000010
【図９】
2004240913.tif 000011
【図１０】
2004240913.tif 000012