動画像処理方法、動画像処理装置及び動画像処理プログラム
【課題】動画像をベクトルデータで表現する。
【解決手段】動画像データの開始フレーム画像内の類似した色値を持つ閉領域を四角形の曲面パッチに分割し、曲面パッチの頂点、制御点を動画像データのフレームを参照して時系列順に追跡し、頂点、制御点の時間軸方向の軌跡をパラメトリック曲線で近似し、パラメトリック曲線の頂点および制御点に対応する色値を動画像データのフレーム画像から取得して、パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力する。これにより、動画像データをベクトルデータで表現することが可能となる。
【解決手段】動画像データの開始フレーム画像内の類似した色値を持つ閉領域を四角形の曲面パッチに分割し、曲面パッチの頂点、制御点を動画像データのフレームを参照して時系列順に追跡し、頂点、制御点の時間軸方向の軌跡をパラメトリック曲線で近似し、パラメトリック曲線の頂点および制御点に対応する色値を動画像データのフレーム画像から取得して、パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力する。これにより、動画像データをベクトルデータで表現することが可能となる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像をベクトルデータで表現する技術に関する。
【背景技術】
【０００２】
デジタルカメラやビデオカメラ等で撮影された画像は、一般に、ビットマップ形式で保存されて利用されることが多い。ビットマップ形式では、画像を画素に分割し、画像を様々な色の画素の集合として取り扱うため写実性に優れている。しかしながら、画像に写されているオブジェクト単位で編集することは容易ではなく、画像を拡大表示した際に、画質が劣化するという問題がある。図形をベースとするベクトル形式のデータは、ベクトルデータが関数的な数値で表され、オブジェクト自体が数式に基づいて描画されるため、オブジェクト単位での編集が容易であり、拡大表示しても一定の画質が保持される。なお、オブジェクトとは、画像内に撮影された意味のあるまとまりを意味し、例えば、人物、頭部、机、車両などの像に代表される。
【０００３】
このような背景のもと、ビットマップ形式の画像をベクトル形式のデータに変換する手法が提案されている（非特許文献１−３参照）。これらの手法は、できるだけ元のビットマップ形式の画像が持つ画質（写実性）を損なわないようにして、できるだけ少ない数の図形要素を持つベクトル形式のデータに変換することを特徴としている。具体的には、ビットマップ形式の画像内のオブジェクトを閉領域とみなし、閉領域の輪郭及び内部を類似した色値を持つ領域毎に「辺がパラメトリック曲線で構成される三角形」や「辺がパラメトリック曲線で構成される四角形」などのパラメトリック曲面パッチに分割して、閉領域の輪郭をパラメトリック曲線で近似するとともに、パラメトリック曲面パッチの内部の色を補間して生成する。以降ではパラメトリック曲面パッチを「三角形パッチ」、「四角形パッチ」、「曲面パッチ」、あるいは単に「パッチ」と称することもある。
【０００４】
図１３に、ビットマップ形式の画像をベクトル形式のデータに変換する様子を示す。図１３（ａ）は、各画素がそれぞれ色値を持っているビットマップ形式の画像を示す。図１３（ｂ）は、四角形パッチで近似した例を示し、図１３（ｃ）は三角形パッチで近似した例を示す。このとき、四角形パッチや三角形パッチは幾何学的には画像面に垂直な方向の高さを持つことができるが、この「高さ」に相当する値を「色値」として表現することで、パッチ内部の色を補間することができる。非特許文献３においては、領域の輪郭のみにパラメトリック曲線を用い、内部の色の補間は薄板スプライン（Ｔｈｉｎ Ｐｌａｔｅ Ｓｐｌｉｎｅ）補間を用いている。
【０００５】
ここで、四角形パッチ、三角形パッチの例について説明する。
【０００６】
双３次ベジエ四角形パッチは、３次元空間に格子状に配置された４×４の制御点の座標値Ｐij(i=0,1,2,3; j=0,1,2,3)を用いて、４頂点Ｐ00，Ｐ03，Ｐ30，Ｐ33で囲まれた領域内部の点Ｐを次式（１）と表す。
【数１】
【０００７】
Ｂi3（ｕ），Ｂj3（ｖ）はそれぞれ３次の Bernstein 基底関数である。ｕ，ｖ（０≦ｕ≦１，０≦ｖ≦１）はパラメトリック空間のパラメータである。
【０００８】
パラメータｓに対する１変数３次の Bernstein 基底関数は次式（２）となる。
【数２】
【０００９】
すなわち、四角形を構成する４つの頂点を含む１６個の制御点の３次元座標値を用いて、四角形を構成する４つの頂点を通過する曲面を構成することができる。パラメータｕ，ｖについて３次であるが、それぞれ次数がひとつ増えると制御点がひとつ増える。
【００１０】
また、双３次ベジエ三角形パッチは、３つの頂点と、それぞれの辺を構成するベジエ曲線の制御点が２つずつと、三角形パッチ内部にある制御点が１つの合計１０個の制御点Ｐijk（i=0,1,2,3; j=0,1,2,3; k=0,1,2,3; i+j+k=3）を用いて次式（３）と表すことができる。
【数３】
【００１１】
Ｂijk3（ｕ，ｖ）は２変数の３次 Bernstein 基底関数である。ｕ，ｖ（０≦ｕ≦１，０≦ｖ≦１）はパラメトリック空間のパラメータである。
【００１２】
パラメータｕ，ｖに対する２変数３次 Bernstein 基底関数は次式（４）となる。
【数４】
【００１３】
一方、コンピュータグラフィクスによって表現された３次元物体の形状を変形させることを目的としてパラメトリック立体が提案されている。３次元物体をパラメトリック立体で覆い、３次元物体を構成する各点の座標値をパラメトリック立体を生成するパラメータに対応付け、パラメトリック立体の制御点を変形させることで、３次元物体の形状もそれに応じて変形させる技術である。例えば、非特許文献４では、パラメトリック立体として、立体の各辺や面がベジエ曲線やベジエパッチで表されるベジエ立体を用いている。
【００１４】
３次ベジエ立体は、３次元空間に立体格子状に配置された４×４×４の制御点の座標値Ｐijk(i=0,1,2,3; j=0,1,2,3; k=0,1,2,3)とパラメータｕ，ｖ，ｗを用いて、立体内部の点Ｐを次式（５）と表すことができる。
【数５】
【００１５】
Ｂi3（ｕ），Ｂj3（ｖ），Ｂk3（ｗ）は、それぞれ式（２）で表される３次の Bernstein 基底関数である。ｕ，ｖ，ｗ（０≦ｕ≦１，０≦ｖ≦１，０≦ｗ≦１）はパラメトリック空間のパラメータである。
【００１６】
同様に、式（３）で表されるベジエ三角パッチを底面とみなし、面が曲面で構成される三角柱を１０×４の制御点の座標値Ｐijk,m(i=0,1,2,3; j=0,1,2,3; k=0,1,2,3; m=0,1,2,3; i+j+k=3)とパラメータｕ，ｖ，ｗを用いて、立体内部の点Ｐを次式（６）と表すことができる。
【数６】
【００１７】
Ｂm3（ｗ）は式（２）で表される１変数３次 Bernstein 基底関数、Ｂijk3（ｕ，ｖ）は式（４）で表される２変数３次 Bernstein 基底関数である。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特許第４１８９２７６号公報
【特許文献２】特許第２８３４７９０号公報
【非特許文献】
【００１９】
【非特許文献１】Brian Price and William Barrett,“Object-Based Vectorization for Interactive Image Editing”, Visual Computer, 22, 2006年8月, p.661-670
【非特許文献２】Yu-Kun Lai, Shi-Min Hu and Ralph R. Martin,“Automatic and Topology-Preserving Gradient Mesh Generation for Image Vectorization”, ACM Transactions on Graphics, Vol. 28, No. 3(SIGGRAPH 2009), 2009年8月, Article 85:1-8
【非特許文献３】Tian Xia, Binbin Liao, Yizhou Yu,“Patch-based Image Vectorization with Aut omatic Curvilinear Feature Alignment”, ACM Transactions on Graphics, Vol. 28, No. 5(SIGGRAPH Asia 2009), 2009年12月, Article 115:1-10
【非特許文献４】Thomas W. Sederberg and Scott R. Parry,“Free-Form Deformation of Solid Geometric Models”, Computer Graphics, Vol. 20, No. 4(Proceedings of SIGGRAPH 1986), 1986年, p.151-160
【非特許文献５】Jue Wang, Yingqing Xu, Heugn-Yeung Shum and Michael F. Cohen,“Video tooning”, ACM Transactions on Graphics, Vol. 23, No. 3(SIGGRAPH 2004), 2004年8月, p.574-583
【発明の概要】
【発明が解決しようとする課題】
【００２０】
動画像のベクトルデータについては、例えば、円や四角形などの図形要素の運動を、時間軸方向に沿った軌跡や運動方程式で表現すること、すなわち、アニメーションとして表現することが考えられる。しかしながら、ビデオカメラ等で撮影された実写動画像をこのようなアニメーションとして表現することは容易ではない。被写体となるオブジェクトは形状の変化を伴ったり隠蔽されたりして、動画像に撮影されている全ての被写体の形状と運動とを数式として復元することが困難だからである。
【００２１】
これに対し、動画像内のオブジェクトではなく画素に着目し、初期フレームの全ての画素の色情報と、その画素の時間変化を直線近似する手法が開示されている。例えば、特許文献１には、初期フレームと終了フレームの対応する画素を直線で結んで途中の任意の時刻での画像を生成する手法が開示されている。特許文献２には、静止剛体を等速直線運動するカメラで撮影した動画像を対象に、先頭フレームの画素を以降のフレームにわたって追跡し、直線で近似する手法が開示されている。
【００２２】
しかしながら、これらの手法では被写体が動いたり変形する場合への適用が困難であるという問題がある。被写体が動いたり変形したりする動画像に対し、非特許文献５では、画素や被写体の境界を滑らかな曲線で近似し、さらに時間軸方向にも滑らかにつなぎ、イラスト調の画像を生成する手法が開示されているが、もとの画像を写実的に再構成することは困難である。
【００２３】
本発明は、上記に鑑みてなされたものであり、動画像をベクトルデータで表現することを目的とする。
【課題を解決するための手段】
【００２４】
第１の本発明に係る動画像処理装置は、動画像データを読み込み蓄積手段に蓄積する読込手段と、前記蓄積手段から前記動画像データの指定されたフレーム画像を読み出し、当該フレーム画像内の類似した色値を持つ閉領域を曲面パッチに分割し、曲面パッチの辺の端を頂点として頂点リストに登録し、その辺を構成するための点を制御点として制御点リストに登録するベクトル化手段と、前記動画像データから時系列順にフレーム画像を読み出し、前記曲面パッチ毎に、読み出したフレーム画像から前記頂点リストに登録された頂点に対応する対応点を検出してそのフレーム画像における頂点として頂点リストに登録する頂点追跡手段と、時系列順に読み出したフレーム画像毎に、前記曲面パッチそれぞれについて、前記頂点リストに登録された頂点を前記曲面パッチの辺の端としたときに前記曲面パッチの辺を構成するための制御点の位置を、その頂点の位置関係に基づいて推定してそのフレーム画像における制御点として制御点リストに登録する制御点追跡手段と、前記頂点リストおよび前記制御点リストを参照し、前記ベクトル化手段により登録された頂点および制御点それぞれの時間軸方向の軌跡をパラメトリック曲線で近似する曲線近似手段と、前記曲線近似手段が近似したパラメトリック曲線の頂点および制御点に対応する色値を前記動画像データのフレーム画像から取得する色値取得手段と、前記パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力する出力手段と、を有することを特徴とする。
【００２５】
第２の本発明に係る動画像処理方法は、読込手段による、動画像データを読み込み蓄積手段に蓄積するステップと、ベクトル化手段による、前記蓄積手段から前記動画像データの指定されたフレーム画像を読み出し、当該フレーム画像内の類似した色値を持つ閉領域を曲面パッチに分割し、曲面パッチの辺の端を頂点として頂点リストに登録し、その辺を構成するための点を制御点として制御点リストに登録するステップと、頂点追跡手段による、前記動画像データから時系列順にフレーム画像を読み出し、前記曲面パッチ毎に、読み出したフレーム画像から前記頂点リストに登録された頂点に対応する対応点を検出してそのフレーム画像における頂点として頂点リストに登録するステップと、制御点追跡手段による、時系列順に読み出したフレーム画像毎に、前記曲面パッチそれぞれについて、前記頂点リストに登録された頂点を前記曲面パッチの辺の端としたときに前記曲面パッチの辺を構成するための制御点の位置を、その頂点の位置関係に基づいて推定してそのフレーム画像における制御点として制御点リストに登録するステップと、曲線近似手段による、前記頂点リストおよび前記制御点リストを参照し、前記ベクトル化手段により登録された頂点および制御点それぞれの時間軸方向の軌跡をパラメトリック曲線で近似するステップと、色値取得手段による、前記曲線近似手段が近似したパラメトリック曲線の頂点および制御点に対応する色値を前記動画像データのフレーム画像から取得するステップと、出力手段による、前記パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力するステップと、を有することを特徴とする。
【００２６】
第３の本発明に係る動画像処理プログラムは、上記動画像処理装置としてコンピュータを機能させることを特徴とする。
【発明の効果】
【００２７】
本発明によれば、動画像をベクトルデータで表現することができる。
【図面の簡単な説明】
【００２８】
【図１】本実施の形態における動画像処理装置の構成を示す機能ブロック図である。
【図２】開始フレーム画像の静止画像をベクトル化する処理の流れを示すフローチャートである。
【図３】ベクトル化したデータの時間軸方向の軌跡を追跡する処理の流れを示すフローチャートである。
【図４】ベクトル化したデータの動きをパラメトリック立体で表す処理の流れを示すフローチャートである。
【図５】頂点を追跡する様子を示す図である。
【図６】頂点と制御点の位置関係の変化を示す図である。
【図７】制御点の評価を説明する図である。
【図８】四角形ベジエパッチを時間軸方向に追跡したベジエ６面体の例を示す図である。
【図９】三角形ベジエパッチを時間軸方向に追跡したベシエ三角柱の例を示す図である。
【図１０】ベジエ曲線の分割を説明する図である。
【図１１】パッチの辺を色々な方法で近似した際のパッチの辺と制御点の位置を示す図である。
【図１２】色値を補間する様子を示す図である。
【図１３】ビットマップ形式の画像をベクトル形式のデータに変換する様子を示す図である。
【発明を実施するための形態】
【００２９】
以下、本発明の実施の形態について図面を用いて説明する。
【００３０】
図１は、本実施の形態における動画像処理装置の構成を示す機能ブロック図である。同図に示す動画像処理装置は、動画像読込部１１、静止画像ベクトル化部１２、頂点追跡部１３、制御点追跡部１４、パラメトリック立体化部１５、色値取得部１６、出力部１７、および蓄積部１８を備える。動画像処理装置が備える各部は、演算処理装置、記憶装置等を備えたコンピュータにより構成して、各部の処理がプログラムによって実行されるものとしてもよい。このプログラムは動画像処理装置が備える記憶装置に記憶されており、磁気ディスク、光ディスク、半導体メモリ等の記録媒体に記録することも、ネットワークを通して提供することも可能である。以下、各部について説明する。
【００３１】
動画像読込部１１は、動画像ファイルを読み込み動画像データを蓄積部１８に蓄積する。
【００３２】
静止画像ベクトル化部１２は、蓄積部１８から動画像データの開始フレーム画像を読み出して、開始フレーム画像内の類似した色値を持つ閉領域を三角形あるいは四角形の曲面パッチに分割し、閉領域の輪郭をパラメトリック曲線で近似する。分割した曲面パッチをパッチリストに、曲面パッチの辺の両端を頂点、曲面パッチの辺を構成するために必要な点を制御点として、頂点リスト、制御点リストに登録する。
【００３３】
頂点追跡部１３は、データリスト処理部１３１、頂点追跡判定部１３２、時間長判定部１３３を備え、蓄積部１８に蓄積された動画像データから時系列順にフレーム画像を読み出して、フレーム画像内の閉領域の角などの特徴点を頂点に対応する対応点として検出し、検出した対応点を対応する頂点に関連付けて対応点リストに登録する。データリスト処理部１３１は対応点をフレーム画像から対応点を検出し、頂点追跡判定部１３２は対応点が見つかったか否か判定して対応点の存在を示す存在フラグを設定するとともに、対応点が見つからない場合は、前フレームを参照し、対応点を決定する、あるいは、対応点が消失したと判定する。時間長判定部１３３は、対応点が消失した場合、その対応点を有する曲面パッチの持続時間を設定するとともにパッチリストから削除する。パッチリストから削除された曲面パッチについては以降のフレームで処理しない。
【００３４】
制御点追跡部１４は、一次結合近似部１４１、制御点評価補正部１４２を備え、前のフレームにおける頂点（対応点）、制御点間の位置関係と、頂点追跡部１３が現在処理対象のフレームから検出した対応点の位置関係から、各パッチの辺を構成するために必要な制御点の位置を求めて制御点リストに登録する。一次結合近似部１４１は、前のフレームにおける頂点と制御点の位置関係を一次結合で表して結合係数を求め、頂点追跡部１３が検出した対応点と求めた結合係数により制御点の位置を推定する。制御点評価補正部１４２は、一次結合近似部１４１が推定した制御点により構成される曲面パッチの辺とフレーム画像から抽出したエッジを構成する点との距離に基づいて制御点の位置を補正する。
【００３５】
パラメトリック立体化部１５は、曲線近似部１５１、誤差評価分割部１５２を備え、頂点追跡部１３、制御点追跡部１４が求めた頂点、制御点を時間軸方向に追跡して動画像をパラメトリック立体で表現する。曲線近似部１５１は、頂点、制御点の時間軸方向の軌跡をベジエ曲線で近似する。誤差評価分割部１５２は、曲線近似部１５１が近似した曲線と近似対象の頂点、制御点の対応点列との最大距離を評価し、最大距離が所定の閾値よりも大きい場合は近似した曲線を分割する。なお、本実施の形態におけるパラメトリック立体は、底面がパラメトリック曲面パッチである多角形であり、側面がパラメトリック曲面パッチである四角形から構成される立体を指す。
【００３６】
色値取得部１６は、生成したパラメトリック立体の頂点、制御点の色値を動画像データのフレーム画像から取得する。フレーム画像から色値が直接取得できない制御点については、取得できる色値を補間して決定する。
【００３７】
出力部１７は、全てのパラメトリック立体について、頂点、制御点の時空間座標値、その座標値における色値（ｘ，ｙ，ｔ，ｃ）のデータをファイルとして出力する。
【００３８】
次に、本実施の形態における動画像処理装置の処理の流れについて説明する。
【００３９】
図２〜４は、本実施の形態における動画像処理装置の処理の流れを示すフローチャートである。図２に示す処理で開始フレーム画像の静止画像をベクトル化し、図３に示す処理でベクトル化したデータの時間軸方向の軌跡を追跡し、図４に示す処理でベクトル化したデータの動きをパラメトリック立体で表している。以下、図２に示す処理から順に説明する。
【００４０】
まず、図２に示す静止画像のベクトル化処理について説明する。
【００４１】
動画像読込部１１が、動画像ファイルを読み込んで動画像データを蓄積部１８に蓄積する（ステップＳ１０１）。このときに、利用者からベクトル化の対象とする時間的範囲（開始フレームと終了フレーム）の指定を受け付けてもよい（ステップＳ１０２）。
【００４２】
続いて、静止画像ベクトル化部１２が、蓄積部１８から動画像データの開始フレーム画像を読み出し、開始フレーム画像のベクトル化を実施する（ステップＳ１０３）。開始フレーム画像はビットマップ形式の画像であり、ビットマップ形式の画像のベクトル化は、非特許文献１，２，ないし３に記載された手法、あるいは他の手法を用いることができる。開始フレーム画像のベクトル化の際に、利用者からベクトル化の対象とする被写体の指定を受け付けてもよい（ステップＳ１０４）。
【００４３】
静止画像ベクトル化部１２により、開始フレーム画像内の閉領域が三角形あるいは四角形の曲面パッチにより分割され、曲面パッチの辺で被写体オブジェクトの輪郭が良好に近似される。ベクトル化により、画像を四角形ベジエパッチで近似する場合は、ひとつのパッチあたり、４個の頂点と１２個の制御点が生成される。画像を三角形ベジエパッチで近似する場合は、ひとつのパッチあたり、３個の頂点と７個の制御点が生成される。なお、本実施の形態では、曲面の「高さ」に相当する変数を、「色値」に置き換えている。カラー画像の場合、例えばＲＧＢ表示系であれば、Ｒ（赤）、Ｇ（緑）、Ｂ（青）の各色ごとに曲面パッチを生成してもよい。ここでは、色成分の数や表示系については言及しないが、応用する状況に応じてカラー画像もグレー画像も用いることができる。
【００４４】
生成された各曲面パッチの頂点、制御点の各リストは蓄積部１８に蓄積される（ステップＳ１０５）。このとき、各頂点がどの曲面パッチに属するかを記憶させる。例えば、曲面パッチ、頂点それぞれに識別子を付与し、曲面パッチを指定するとその曲面パッチを構成する頂点の識別子を取得でき、または、頂点を指定するとその頂点を含む曲面パッチ（ひとつではない場合もある）の識別子を取得できるようにしておく。同様に、頂点と制御点も関連付けておく。
【００４５】
次に、図３に示す、ベクトル化したデータの時間軸方向の軌跡を追跡する処理について説明する。
【００４６】
データリスト処理部１３１は、動画像ファイルの次フレーム画像を蓄積部１８から読み出し、読み出したフレーム画像における各曲面パッチの各頂点に対応する対応点を検出する（ステップＳ２０１）。また、各曲面パッチに対して読み出したフレーム画像のフレーム番号あるいは持続時間を付与する。曲面パッチの辺はフレーム画像の閉領域のエッジを近似しており、曲面パッチの頂点は曲面パッチの辺（曲線）の両端であるので、各頂点は、フレーム画像内の閉領域の角などの特徴点となり、検出しやすい。そこで、データリスト処理部１３１は、読み出したフレーム画像の閉領域の角を頂点の対応点として検出する。
【００４７】
図５は、頂点を追跡する様子を示す図である。フレームＴ１→Ｔ２→Ｔ３→Ｔ４と変化するものとする。同図では、わかりやすくするため、曲面パッチの辺も記載している。同図の頂点Ｐ１，Ｐ２，Ｐ３で構成される三角形パッチにおいて、フレームＴ２では、頂点Ｐ１，Ｐ２，Ｐ３の対応点が見つかっており、フレームＴ３では、頂点Ｐ２または頂点Ｐ３の対応点が見つからず、フレームＴ４では、再び頂点Ｐ１，Ｐ２，Ｐ３の対応点が見つかっている。
【００４８】
フレーム画像を読み出して対応点を検出した後、各曲面パッチについて、以下に示す頂点の追跡処理を行う。
【００４９】
頂点追跡判定部１３２は、曲面パッチから１つの頂点を選択し、その頂点の対応点が存在するか否か判定する（ステップＳ２０２）。
【００５０】
対応点が存在する場合は、その頂点に対する対応点として対応点リストに座標値を追加し、頂点に対応する対応点の存在を示す存在フラグをオンとする（ステップＳ２０３）。
【００５１】
曲面パッチのすべての頂点について対応点の存在を判定する処理が終了した場合は次の曲面パッチについての処理へ進み、曲面パッチ内にまだ処理していない頂点が存在する場合はステップＳ２０２に戻る（ステップＳ２０４）。なお、隣接する曲面パッチでは頂点を共有しているため、すでに対応点が存在していることが明らかな頂点については処理済みとする。
【００５２】
一方、対応点が存在しない場合は、前フレームではその頂点の対応点が存在していたか否か判定する（ステップＳ２０５）。頂点に対応する存在フラグを評価することで対応点が存在していたか否か判定できる。
【００５３】
前フレームで対応点が存在していた場合は、頂点を含む曲面パッチの前フレームにおける面積を計算し（ステップＳ２０６）、計算した面積が所定の閾値より大きいか否か判定する（ステップＳ２０７）。本実施の形態では、曲面パッチの面積として、図５の点線で示される各頂点Ｐ１，Ｐ２，Ｐ３を結んだ三角形の面積を計算する。
【００５４】
計算した面積が所定の閾値よりも大きい場合は、頂点に対応する対応点として前フレームにおける対応点の座標値を現在処理対象のフレームの対応点として対応点リストに追加する（ステップＳ２０８）。
【００５５】
計算した面積が所定の閾値以下の場合は、現在のフレームで曲面パッチが消失したと判定する。消失した曲面パッチについては、パッチリストから削除し、時間長判定部１３３が、消失した曲面パッチは、開始フレームから前フレームまで持続したとし、フレーム数あるいはフレーム番号をその曲面パッチのデータとして付与し、以降のフレームではその曲面パッチについての処理を行わない（ステップＳ２０９）。
【００５６】
一方、ステップＳ２０５において前フレームにも対応点が存在していなかった、つまり、２フレーム連続で対応点が存在していなかったと判定された頂点を含む曲面パッチも消失したと判定する。時間長判定部１３３は、消失した曲面パッチは、２つ前のフレームまで持続したとし、フレーム数あるいはフレーム番号をその曲面パッチのデータとして付与する。なお、本実施の形態では、２フレーム続けて対応点が見つからない場合に曲面パッチが消失したと判定しているが、このフレーム数は２に限るものではない。
【００５７】
図５に示す例では、フレームＴ３において、頂点Ｐ１，Ｐ２の対応点は見つかったが、頂点Ｐ３の対応点が見つかっていないので、フレームＴ２における三角形Ｐ１／Ｐ２／Ｐ３の面積を計算して、頂点Ｐ３の追跡処理を続行するか否か判定する。計算した面積が所定の閾値より大きければ、フレームＴ２の頂点Ｐ３の対応点の座標値をフレームＴ３における頂点Ｐ３の対応点（Ｐ３’）として対応点リストに追加する。同図に示す例では、フレームＴ４において頂点Ｐ３の対応点が見つかったので、フレームＴ３の頂点Ｐ３の対応点をＰ３’とみなしてフレームＴ４以降も頂点Ｐ３の追跡処理を行う。なお、フレームＴ４においても頂点Ｐ３の対応点が見つからなかった場合は、フレームＴ３において頂点Ｐ１，Ｐ２，Ｐ３で構成される曲面パッチは消失したと判定される。
【００５８】
以上ステップＳ２０２からステップＳ２０９までの処理を全ての曲面パッチについて行う。まだ処理していない曲面パッチが存在する場合はステップＳ２０２に戻り（ステップＳ２１０）、その曲面パッチの各頂点について処理を行う。
【００５９】
全ての曲面パッチについて頂点の追跡処理が終了したら、制御点追跡部１４が、各曲面パッチの辺の曲線を生成するための制御点の追跡処理を行う。３次ベジエ曲線においては、１つの曲線セグメントを生成するために２つの端点と２つの制御点が必要となる。２つの端点は、曲面パッチの２つの頂点に該当する。また、３次ベジエ曲線において一般に生成される曲線は制御点を通過しないため、制御点はフレーム画像内の閉領域のエッジやコーナーなどの特徴点となるとは限らない。
【００６０】
各フレームごとに被写体オブジェクトのエッジを抽出し、エッジを近似するベジエ曲線を生成するように制御点を決定する方法もあるが、本実施の形態では、フレーム間で曲面パッチの辺を形成する頂点（端点）と制御点の相互の位置関係が大きく変化しないと仮定し、前フレームにおける各頂点と各制御点の位置関係と現在のフレームの各頂点の位置関係に基づいて制御点を推定する。
【００６１】
まず、一次結合近似部１４１が、ある頂点に対する制御点の位置ベクトルをある頂点に対する曲面パッチの辺を構成する２つの頂点の位置ベクトルの一次結合で表す（ステップＳ２１１）。具体的には、次式（７）に示すように、前フレームにおける、頂点Ｐ１，Ｐ２を結ぶ曲線の制御点Ｃ１，Ｃ２それぞれを、その曲線を構成しない同じ曲面パッチの別の頂点Ｐ３対する頂点Ｐ１，Ｐ２の位置ベクトルで表す。
【数７】
【００６２】
図６に示すように、現在のフレームにおいても前フレームにおける頂点と制御点の位置関係が大きく変化しないと仮定し、式（７）の一次結合係数ａ，ｂ，ｃ，ｄが保存されるとして、次式（８）に示すように、一次結合係数ａ，ｂ，ｃ，ｄを用いて、現在のフレームにおける制御点Ｃ１’，Ｃ２’それぞれを頂点Ｐ３’に対する頂点Ｐ１’，Ｐ２’の位置ベクトルで表す。
【数８】
【００６３】
なお、パッチ形状が四角形の場合は、辺を構成する頂点以外に２つの頂点が存在するが、いずれか一方を位置ベクトルの始点と定めればよい。
【００６４】
続いて、制御点評価補正部１４２が、頂点Ｐ１’，Ｐ２’と制御点Ｃ１’，Ｃ２’で生成されるベジエ曲線と、現在処理対象のフレーム画像内の閉領域のエッジとの差分を評価して制御点Ｃ１’，Ｃ２’の位置を補正する（ステップＳ２１２）。エッジを構成する画素とベジエ曲線との差分を計算すると計算量が多くなるため、本実施の形態では、エッジ上の２点とベジエ曲線との距離で評価する。
【００６５】
具体的には、図７に示すように、制御点Ｃ１’とベジエ曲線との距離が最小となるベジエ曲線上の点をＢ１、直線Ｃ１’Ｂ１とエッジとの交点をＥ１として、点Ｂ１，Ｅ１間の距離が所定の閾値よりも小さければ制御点Ｃ１’の位置を補正せず、点Ｂ１，Ｅ１間の距離が所定の閾値以上で、点Ｃ１’，Ｂ１間の距離≦点Ｃ１’，Ｅ１間の距離であれば、制御点Ｃ１’を点Ｃ１’から点Ｂ１の方向に所定の距離移動させて新たな制御点Ｃ１’とし、点Ｃ１’，Ｂ１間の距離≧点Ｃ１’，Ｅ１間の距離であれば、制御点Ｃ１’を点Ｂ１から点Ｃ１’の方向に所定の距離移動させて新たな制御点Ｃ１’とする。制御点Ｃ１’を移動させる距離は、例えば、点Ｃ１’Ｂ１間の距離に適当な実数（例えば、０．５）を乗じた値とする。制御点Ｃ２’についても同様の処理を行い、頂点Ｐ１’，Ｐ２’と新たな制御点Ｃ１’，Ｃ２’で生成されるベジエ曲線について、点Ｂ１，Ｅ１間、点Ｂ２，Ｅ２間の距離が所定の閾値よりも小さくなるまで上記の補正処理を繰り返す。
【００６６】
任意の点とベジエ曲線との最短距離を計算し、最短距離となるベジエ曲線上の点を求める方法は、例えば、Philip J. Schneider,“Solving the Nearest-point-on-curve Problem”, Graphics Gems, Morgan Kaufmann Publishers（参考文献１）や Philip J. Schneider,“An Algorithm for Automatically Fitting Digitized Curves”, Graphics Gems, Morgan Kaufmann Publishers（参考文献２）に解説されている。
【００６７】
以上の制御点の追跡処理を全ての制御点について行う（ステップＳ２１３）。なお、三角形ベジエパッチの場合はさらに三角形内部にひとつの制御点があり、四角形ベシエパッチの場合は内部に４つの制御点がある。これらの制御点は、上記ステップＳ２１１の一次結合係数の保存のみで評価してもよい。
【００６８】
すべての制御点の追跡処理が終了したら、ステップＳ２０１に戻り次のフレーム画像を読み込んでそのフレーム画像の頂点、制御点を求め、全フレームについて処理が終了した場合、あるいは、全ての曲面パッチが消失した場合は、ベクトル化したデータの動きをパラメトリック立体で表現する処理に進む（ステップＳ２１４）。
【００６９】
次に、図４に示す、ベクトル化したデータの動きをパラメトリック立体で表現する処理について説明する。図４に示す処理では、頂点、制御点の時間軸方向の軌跡をベジエ曲線で近似し、その結果生成される制御点を用いてパラメトリック立体を生成する。
【００７０】
曲線近似部１５１は、各曲面パッチについて、曲面パッチを構成する全ての頂点、制御点の時間軸方向の軌跡をベジエ曲線で近似する（ステップＳ３０１）。例えば、参考文献２で解説されている手法により、３次の区分的ベジエ曲線により近似する。
【００７１】
図８に、四角形ベジエパッチを時間軸方向に追跡したベジエ６面体の例を示す。図８（ａ）は、頂点追跡部１３で追跡した頂点の時間軸方向の軌跡を図示した図であり、図８（ｂ）は、図８（ａ）の軌跡を近似するベジエ曲線を構成する制御点を図示した図である。図８（ｃ）には、図８（ａ）に示すベジエ立体における各パラメータの定義域を示している。また、同様に、図９に、三角形ベジエパッチを時間軸方向に追跡したベシエ三角柱の例を示しておく。
【００７２】
頂点、制御点の軌跡を近似したベジエ曲線の開始フレーム、終了フレームにおける端（頂点、制御点）は、（ｘ，ｙ，ｔ）空間において同じｔを持つ。軌跡を近似したベジエ曲線を構成する各曲面パッチの頂点、制御点のうち、時間軸方向の添字が等しいもの、例えば、図８（ｂ）におけるＰｉｊ１となる１６点は、（ｘ，ｙ，ｔ）空間において同じｔを持つとよい。同様に、Ｐｉｊ２となる１６点についても同じｔを持つと良い。また、図８（ｂ）におけるＰｉｊｋ，１となる１０点、およびＰｉｊｋ，２となる１０点も（ｘ，ｙ，ｔ）空間においてそれぞれ同じｔを持つと良い。これにより、図８，９に示すパラメトリック立体において、パラメータ（ｕ，ｖ，ｗ）のｗの値を一つ決めると、ｔが一意に決まり、あとの計算処理が容易になる。
【００７３】
続いて、誤差評価分割部１５２が、頂点、制御点の時間軸方向の軌跡を近似した曲線と近似対象の頂点、制御点の対応点列との最大距離を評価する（ステップＳ３０２）。そして、ひとつの曲面パッチを構成する頂点、制御点の時間軸方向の軌跡を近似した曲線のうち、もっとも誤差が大きいものを選び、その誤差と所定の閾値と比較する（ステップＳ３０３）。
【００７４】
最大誤差が所定の閾値よりも大きい場合、誤差評価分割部１５２は、もっとも誤差が大きい曲線を分割する（ステップＳ３０４）。曲線の分割方法は、２次元平面上の曲線について、参考文献２に記載されている。３次元曲線についても本質的に同様の処理で実現できる。図１０に２次元平面上のベジエ曲線を分割する例を示す。例えば、図１０の点線で示す頂点Ｐ１から頂点Ｐ２までの追跡点列を図１０の実線で示すベジエ曲線で近似しようとしても誤差が大きくなる場合、追跡点列とベジエ曲線の距離が最も大きくなる点Ｐ１２を分割点として選び、新たに分割点の前後それぞれにおいてベジエ曲線で近似する。図１０に示すように、ベジエ曲線を分割した場合、ベジエ曲線上の分割点が新たな頂点Ｐ１２となり、頂点Ｐ１，Ｐ１２を結ぶベジエ曲線の２つの制御点Ｃ１１，Ｃ１２、頂点Ｐ１２，Ｐ２を結ぶベジエ曲線の２つの制御点Ｃ２１，Ｃ２２が新たに追加される。
【００７５】
さらに、同じ曲面パッチを構成する他の頂点、制御点の時間軸方向の軌跡を近似した曲線も分割し（ステップＳ３０５）、分割で生じた新たな立体に対応する曲面パッチをパッチリストに追加する（ステップＳ３０６）。他の曲線を分割する際には、ステップＳ３０４で曲線の分割に用いたパラメータ値Ｗに対応する時間変数Ｔを求め、時間変数Ｔに相当するパラメータ値で分割する。この分割処理は、図７（ａ），８（ａ）で示した立体を時間軸に垂直な面で切断することに相当する。なお、隣接するパッチにおいて、頂点、制御点を共有する場合もあるが、片方のパッチでは分割が行われ、他方のパッチでは分割が行われないという場合も生じる。
【００７６】
一方、最大誤差が所定の閾値以下の場合は、色値取得部１６が、パッチを時間軸方向に追跡して生成されたベジエ立体の頂点、制御点の色値を確定させる（ステップＳ３０７）。具体的には、パッチの開始フレーム、終了フレームにおける色値は、パッチの各頂点、制御点の座標値における色値をそのフレームから取得することで得られる。制御点がパッチの内部にある場合は、該当座標値の色値を用い、制御点がパッチの外部にある場合は、適当な初期値、例えば、制御点に最も近いパッチの辺上の点の色値を与える。あるいは、数式（５），（６）で時間変数ｔを初期値または終了値に固定した際のＰ（ｕ，ｖ，ｗ）の各画素位置に該当する値を計算し、色値の最大誤差が所定の値より小さくなるように色値を変化させながら非線形最小二乗法、例えば、Ｌｅｖｅｎｂｅｒｇ−Ｍａｒｑｕａｒｄｔ法を用いて色値を求めてもよい。このとき、計算を容易化するために、オブジェクトの境界となるパッチの辺は曲線で表し、オブジェクトの内部は辺が線分となる三角形で表現してもよい。例えば、開始フレームや終了フレームにおいて、図１１（ａ）では全ての辺が曲線から構成されるパッチを用いて近似し、図１１（ｂ）ではオブジェクトの輪郭のみを曲線で表し、内部の辺は線分となるパッチを用いて近似し、図１１（ｃ）ではオブジェクトの輪郭も含めて全ての辺が線分となるパッチを用いて近似している。辺が線分で構成される三角形では、制御点は辺上にあるため、辺を３分割する点を制御点とみなしてその座標値での色値を用いる。図１１（ａ）のように辺が曲線で構成されるパッチを用いる場合でも、図１１（ｃ）のように頂点を結んだ線分を３分割する点の位置の色値を用いてもよい。また、頂点の色値を初期値として非線形最小二乗法で反復計算して求めてもよい。
【００７７】
パッチの開始フレーム、終了フレーム以外の制御点の色値、および、分割された場合の頂点、制御点の色値については、対応する頂点、制御点の開始フレームにおける色値を用いてもよいし、図１２に示すように補間してもよい。図１２に示す例では、分割をした際の時間変数Ｔの前後のフレームをＴｆ，Ｔｂ（Ｔｆ＜Ｔｂ）として、Ｔｆでの色値をＣｆ、Ｔｂでの色値をＣｂとおき、Ｔにおける色値Ｃ（Ｔ）を次式（９）で補間する。
【００７８】
Ｃ（Ｔ）＝（（Ｔ−Ｔｂ）Ｃｆ ＋ （Ｔｆ−Ｔ）Ｃｂ）／Ｔｂ−Ｔｆ （９）
以上ステップＳ３０１からステップＳ３０７までの処理を全てのパッチについて行う。まだ処理していないパッチが存在する場合はステップＳ３０１に戻り（ステップＳ３０８）、そのパッチの動きをパラメトリック立体で表現する。
【００７９】
全てのパッチについて、頂点、制御点の時空間座標値およびその座標値における色値（ｘ，ｙ，ｔ，ｃ）を決定し、データをファイルとして出力する（Ｓ３０９）。出力するデータは、パッチ毎に、パッチＩＤ、パッチの開始時刻、パッチの終了時刻、ベジエ三角柱の場合は４０個の頂点および制御点のｘ座標値、ｙ座標値、ｔ座標値、色値を有している。ベジエ６面体を利用する場合は６４個の頂点および制御点のデータとなる。
【００８０】
次に、出力されたベクトルデータから動画像を生成する手順について説明する。
【００８１】
座標（ｘ，ｙ）を指定し、ベクトルデータがベジエ６面体の場合は式（５）、ベジエ三角形の場合は式（６）を用いて、時空間座標値（ｘ，ｙ，ｔ）となるパラメータ（ｕ，ｖ，ｗ）を Newton-Raphson を用いて求め、パラメータ（ｕ，ｖ，ｗ）を用いて式（５）または式（６）に代入し、（ｘ，ｙ，ｔ）における色値を計算する。座標値（ｘ，ｙ）をディジタル画像における画素の中心位置、ｔをディジタル画像のおけるフレーム位置と解釈すれば、ベクトルデータからディジタル動画像を生成することが可能となる。
【００８２】
以上説明したように、本実施の形態によれば、動画像データの開始フレーム画像内の類似した色値を持つ閉領域を四角形の曲面パッチに分割し、曲面パッチの頂点、制御点を動画像データのフレームを参照して時系列順に追跡し、頂点、制御点の時間軸方向の軌跡をパラメトリック曲線で近似し、パラメトリック曲線の頂点および制御点に対応する色値を動画像データのフレーム画像から取得して、パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力することにより、動画像データをベクトルデータで表現することが可能となり、より少ないデータ量で、拡大縮小しても画質を損なわず表現することができる。また、オブジェクトあるいはパッチレベルでの内容の編集や修正を行うことができる。
【００８３】
なお、本実施の形態では、パラメトリック曲線や曲面、立体において、ベジエ曲線、ベジエ曲面、ベジエ立体を念頭に説明したが、本質的にはどのようなパラメトリック曲線／曲面／立体を用いてもよい。例えば、有理ベジエ立体やＢスプライン立体としても適用可能である。また、従来手法においては、パラメトリック曲面パッチの次数として３次で表現されることが多い。これについても、本質的には２次以上であれば次数はいくつでもよいが、処理の容易さから次数３のものが用いられることが多い。
【符号の説明】
【００８４】
１１…動画像読込部
１２…静止画像ベクトル化部
１３…頂点追跡部
１３１…データリスト処理部
１３２…頂点追跡判定部
１３３…時間長判定部
１４…制御点追跡部
１４１…一次結合近似部
１４２…制御点評価補正部
１５…パラメトリック立体化部
１５１…曲線近似部
１５２…誤差評価分割部
１６…色値取得部
１７…出力部
１８…蓄積部
【技術分野】
【０００１】
本発明は、動画像をベクトルデータで表現する技術に関する。
【背景技術】
【０００２】
デジタルカメラやビデオカメラ等で撮影された画像は、一般に、ビットマップ形式で保存されて利用されることが多い。ビットマップ形式では、画像を画素に分割し、画像を様々な色の画素の集合として取り扱うため写実性に優れている。しかしながら、画像に写されているオブジェクト単位で編集することは容易ではなく、画像を拡大表示した際に、画質が劣化するという問題がある。図形をベースとするベクトル形式のデータは、ベクトルデータが関数的な数値で表され、オブジェクト自体が数式に基づいて描画されるため、オブジェクト単位での編集が容易であり、拡大表示しても一定の画質が保持される。なお、オブジェクトとは、画像内に撮影された意味のあるまとまりを意味し、例えば、人物、頭部、机、車両などの像に代表される。
【０００３】
このような背景のもと、ビットマップ形式の画像をベクトル形式のデータに変換する手法が提案されている（非特許文献１−３参照）。これらの手法は、できるだけ元のビットマップ形式の画像が持つ画質（写実性）を損なわないようにして、できるだけ少ない数の図形要素を持つベクトル形式のデータに変換することを特徴としている。具体的には、ビットマップ形式の画像内のオブジェクトを閉領域とみなし、閉領域の輪郭及び内部を類似した色値を持つ領域毎に「辺がパラメトリック曲線で構成される三角形」や「辺がパラメトリック曲線で構成される四角形」などのパラメトリック曲面パッチに分割して、閉領域の輪郭をパラメトリック曲線で近似するとともに、パラメトリック曲面パッチの内部の色を補間して生成する。以降ではパラメトリック曲面パッチを「三角形パッチ」、「四角形パッチ」、「曲面パッチ」、あるいは単に「パッチ」と称することもある。
【０００４】
図１３に、ビットマップ形式の画像をベクトル形式のデータに変換する様子を示す。図１３（ａ）は、各画素がそれぞれ色値を持っているビットマップ形式の画像を示す。図１３（ｂ）は、四角形パッチで近似した例を示し、図１３（ｃ）は三角形パッチで近似した例を示す。このとき、四角形パッチや三角形パッチは幾何学的には画像面に垂直な方向の高さを持つことができるが、この「高さ」に相当する値を「色値」として表現することで、パッチ内部の色を補間することができる。非特許文献３においては、領域の輪郭のみにパラメトリック曲線を用い、内部の色の補間は薄板スプライン（Ｔｈｉｎ Ｐｌａｔｅ Ｓｐｌｉｎｅ）補間を用いている。
【０００５】
ここで、四角形パッチ、三角形パッチの例について説明する。
【０００６】
双３次ベジエ四角形パッチは、３次元空間に格子状に配置された４×４の制御点の座標値Ｐij(i=0,1,2,3; j=0,1,2,3)を用いて、４頂点Ｐ00，Ｐ03，Ｐ30，Ｐ33で囲まれた領域内部の点Ｐを次式（１）と表す。
【数１】
【０００７】
Ｂi3（ｕ），Ｂj3（ｖ）はそれぞれ３次の Bernstein 基底関数である。ｕ，ｖ（０≦ｕ≦１，０≦ｖ≦１）はパラメトリック空間のパラメータである。
【０００８】
パラメータｓに対する１変数３次の Bernstein 基底関数は次式（２）となる。
【数２】
【０００９】
すなわち、四角形を構成する４つの頂点を含む１６個の制御点の３次元座標値を用いて、四角形を構成する４つの頂点を通過する曲面を構成することができる。パラメータｕ，ｖについて３次であるが、それぞれ次数がひとつ増えると制御点がひとつ増える。
【００１０】
また、双３次ベジエ三角形パッチは、３つの頂点と、それぞれの辺を構成するベジエ曲線の制御点が２つずつと、三角形パッチ内部にある制御点が１つの合計１０個の制御点Ｐijk（i=0,1,2,3; j=0,1,2,3; k=0,1,2,3; i+j+k=3）を用いて次式（３）と表すことができる。
【数３】
【００１１】
Ｂijk3（ｕ，ｖ）は２変数の３次 Bernstein 基底関数である。ｕ，ｖ（０≦ｕ≦１，０≦ｖ≦１）はパラメトリック空間のパラメータである。
【００１２】
パラメータｕ，ｖに対する２変数３次 Bernstein 基底関数は次式（４）となる。
【数４】
【００１３】
一方、コンピュータグラフィクスによって表現された３次元物体の形状を変形させることを目的としてパラメトリック立体が提案されている。３次元物体をパラメトリック立体で覆い、３次元物体を構成する各点の座標値をパラメトリック立体を生成するパラメータに対応付け、パラメトリック立体の制御点を変形させることで、３次元物体の形状もそれに応じて変形させる技術である。例えば、非特許文献４では、パラメトリック立体として、立体の各辺や面がベジエ曲線やベジエパッチで表されるベジエ立体を用いている。
【００１４】
３次ベジエ立体は、３次元空間に立体格子状に配置された４×４×４の制御点の座標値Ｐijk(i=0,1,2,3; j=0,1,2,3; k=0,1,2,3)とパラメータｕ，ｖ，ｗを用いて、立体内部の点Ｐを次式（５）と表すことができる。
【数５】
【００１５】
Ｂi3（ｕ），Ｂj3（ｖ），Ｂk3（ｗ）は、それぞれ式（２）で表される３次の Bernstein 基底関数である。ｕ，ｖ，ｗ（０≦ｕ≦１，０≦ｖ≦１，０≦ｗ≦１）はパラメトリック空間のパラメータである。
【００１６】
同様に、式（３）で表されるベジエ三角パッチを底面とみなし、面が曲面で構成される三角柱を１０×４の制御点の座標値Ｐijk,m(i=0,1,2,3; j=0,1,2,3; k=0,1,2,3; m=0,1,2,3; i+j+k=3)とパラメータｕ，ｖ，ｗを用いて、立体内部の点Ｐを次式（６）と表すことができる。
【数６】
【００１７】
Ｂm3（ｗ）は式（２）で表される１変数３次 Bernstein 基底関数、Ｂijk3（ｕ，ｖ）は式（４）で表される２変数３次 Bernstein 基底関数である。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特許第４１８９２７６号公報
【特許文献２】特許第２８３４７９０号公報
【非特許文献】
【００１９】
【非特許文献１】Brian Price and William Barrett,“Object-Based Vectorization for Interactive Image Editing”, Visual Computer, 22, 2006年8月, p.661-670
【非特許文献２】Yu-Kun Lai, Shi-Min Hu and Ralph R. Martin,“Automatic and Topology-Preserving Gradient Mesh Generation for Image Vectorization”, ACM Transactions on Graphics, Vol. 28, No. 3(SIGGRAPH 2009), 2009年8月, Article 85:1-8
【非特許文献３】Tian Xia, Binbin Liao, Yizhou Yu,“Patch-based Image Vectorization with Aut omatic Curvilinear Feature Alignment”, ACM Transactions on Graphics, Vol. 28, No. 5(SIGGRAPH Asia 2009), 2009年12月, Article 115:1-10
【非特許文献４】Thomas W. Sederberg and Scott R. Parry,“Free-Form Deformation of Solid Geometric Models”, Computer Graphics, Vol. 20, No. 4(Proceedings of SIGGRAPH 1986), 1986年, p.151-160
【非特許文献５】Jue Wang, Yingqing Xu, Heugn-Yeung Shum and Michael F. Cohen,“Video tooning”, ACM Transactions on Graphics, Vol. 23, No. 3(SIGGRAPH 2004), 2004年8月, p.574-583
【発明の概要】
【発明が解決しようとする課題】
【００２０】
動画像のベクトルデータについては、例えば、円や四角形などの図形要素の運動を、時間軸方向に沿った軌跡や運動方程式で表現すること、すなわち、アニメーションとして表現することが考えられる。しかしながら、ビデオカメラ等で撮影された実写動画像をこのようなアニメーションとして表現することは容易ではない。被写体となるオブジェクトは形状の変化を伴ったり隠蔽されたりして、動画像に撮影されている全ての被写体の形状と運動とを数式として復元することが困難だからである。
【００２１】
これに対し、動画像内のオブジェクトではなく画素に着目し、初期フレームの全ての画素の色情報と、その画素の時間変化を直線近似する手法が開示されている。例えば、特許文献１には、初期フレームと終了フレームの対応する画素を直線で結んで途中の任意の時刻での画像を生成する手法が開示されている。特許文献２には、静止剛体を等速直線運動するカメラで撮影した動画像を対象に、先頭フレームの画素を以降のフレームにわたって追跡し、直線で近似する手法が開示されている。
【００２２】
しかしながら、これらの手法では被写体が動いたり変形する場合への適用が困難であるという問題がある。被写体が動いたり変形したりする動画像に対し、非特許文献５では、画素や被写体の境界を滑らかな曲線で近似し、さらに時間軸方向にも滑らかにつなぎ、イラスト調の画像を生成する手法が開示されているが、もとの画像を写実的に再構成することは困難である。
【００２３】
本発明は、上記に鑑みてなされたものであり、動画像をベクトルデータで表現することを目的とする。
【課題を解決するための手段】
【００２４】
第１の本発明に係る動画像処理装置は、動画像データを読み込み蓄積手段に蓄積する読込手段と、前記蓄積手段から前記動画像データの指定されたフレーム画像を読み出し、当該フレーム画像内の類似した色値を持つ閉領域を曲面パッチに分割し、曲面パッチの辺の端を頂点として頂点リストに登録し、その辺を構成するための点を制御点として制御点リストに登録するベクトル化手段と、前記動画像データから時系列順にフレーム画像を読み出し、前記曲面パッチ毎に、読み出したフレーム画像から前記頂点リストに登録された頂点に対応する対応点を検出してそのフレーム画像における頂点として頂点リストに登録する頂点追跡手段と、時系列順に読み出したフレーム画像毎に、前記曲面パッチそれぞれについて、前記頂点リストに登録された頂点を前記曲面パッチの辺の端としたときに前記曲面パッチの辺を構成するための制御点の位置を、その頂点の位置関係に基づいて推定してそのフレーム画像における制御点として制御点リストに登録する制御点追跡手段と、前記頂点リストおよび前記制御点リストを参照し、前記ベクトル化手段により登録された頂点および制御点それぞれの時間軸方向の軌跡をパラメトリック曲線で近似する曲線近似手段と、前記曲線近似手段が近似したパラメトリック曲線の頂点および制御点に対応する色値を前記動画像データのフレーム画像から取得する色値取得手段と、前記パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力する出力手段と、を有することを特徴とする。
【００２５】
第２の本発明に係る動画像処理方法は、読込手段による、動画像データを読み込み蓄積手段に蓄積するステップと、ベクトル化手段による、前記蓄積手段から前記動画像データの指定されたフレーム画像を読み出し、当該フレーム画像内の類似した色値を持つ閉領域を曲面パッチに分割し、曲面パッチの辺の端を頂点として頂点リストに登録し、その辺を構成するための点を制御点として制御点リストに登録するステップと、頂点追跡手段による、前記動画像データから時系列順にフレーム画像を読み出し、前記曲面パッチ毎に、読み出したフレーム画像から前記頂点リストに登録された頂点に対応する対応点を検出してそのフレーム画像における頂点として頂点リストに登録するステップと、制御点追跡手段による、時系列順に読み出したフレーム画像毎に、前記曲面パッチそれぞれについて、前記頂点リストに登録された頂点を前記曲面パッチの辺の端としたときに前記曲面パッチの辺を構成するための制御点の位置を、その頂点の位置関係に基づいて推定してそのフレーム画像における制御点として制御点リストに登録するステップと、曲線近似手段による、前記頂点リストおよび前記制御点リストを参照し、前記ベクトル化手段により登録された頂点および制御点それぞれの時間軸方向の軌跡をパラメトリック曲線で近似するステップと、色値取得手段による、前記曲線近似手段が近似したパラメトリック曲線の頂点および制御点に対応する色値を前記動画像データのフレーム画像から取得するステップと、出力手段による、前記パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力するステップと、を有することを特徴とする。
【００２６】
第３の本発明に係る動画像処理プログラムは、上記動画像処理装置としてコンピュータを機能させることを特徴とする。
【発明の効果】
【００２７】
本発明によれば、動画像をベクトルデータで表現することができる。
【図面の簡単な説明】
【００２８】
【図１】本実施の形態における動画像処理装置の構成を示す機能ブロック図である。
【図２】開始フレーム画像の静止画像をベクトル化する処理の流れを示すフローチャートである。
【図３】ベクトル化したデータの時間軸方向の軌跡を追跡する処理の流れを示すフローチャートである。
【図４】ベクトル化したデータの動きをパラメトリック立体で表す処理の流れを示すフローチャートである。
【図５】頂点を追跡する様子を示す図である。
【図６】頂点と制御点の位置関係の変化を示す図である。
【図７】制御点の評価を説明する図である。
【図８】四角形ベジエパッチを時間軸方向に追跡したベジエ６面体の例を示す図である。
【図９】三角形ベジエパッチを時間軸方向に追跡したベシエ三角柱の例を示す図である。
【図１０】ベジエ曲線の分割を説明する図である。
【図１１】パッチの辺を色々な方法で近似した際のパッチの辺と制御点の位置を示す図である。
【図１２】色値を補間する様子を示す図である。
【図１３】ビットマップ形式の画像をベクトル形式のデータに変換する様子を示す図である。
【発明を実施するための形態】
【００２９】
以下、本発明の実施の形態について図面を用いて説明する。
【００３０】
図１は、本実施の形態における動画像処理装置の構成を示す機能ブロック図である。同図に示す動画像処理装置は、動画像読込部１１、静止画像ベクトル化部１２、頂点追跡部１３、制御点追跡部１４、パラメトリック立体化部１５、色値取得部１６、出力部１７、および蓄積部１８を備える。動画像処理装置が備える各部は、演算処理装置、記憶装置等を備えたコンピュータにより構成して、各部の処理がプログラムによって実行されるものとしてもよい。このプログラムは動画像処理装置が備える記憶装置に記憶されており、磁気ディスク、光ディスク、半導体メモリ等の記録媒体に記録することも、ネットワークを通して提供することも可能である。以下、各部について説明する。
【００３１】
動画像読込部１１は、動画像ファイルを読み込み動画像データを蓄積部１８に蓄積する。
【００３２】
静止画像ベクトル化部１２は、蓄積部１８から動画像データの開始フレーム画像を読み出して、開始フレーム画像内の類似した色値を持つ閉領域を三角形あるいは四角形の曲面パッチに分割し、閉領域の輪郭をパラメトリック曲線で近似する。分割した曲面パッチをパッチリストに、曲面パッチの辺の両端を頂点、曲面パッチの辺を構成するために必要な点を制御点として、頂点リスト、制御点リストに登録する。
【００３３】
頂点追跡部１３は、データリスト処理部１３１、頂点追跡判定部１３２、時間長判定部１３３を備え、蓄積部１８に蓄積された動画像データから時系列順にフレーム画像を読み出して、フレーム画像内の閉領域の角などの特徴点を頂点に対応する対応点として検出し、検出した対応点を対応する頂点に関連付けて対応点リストに登録する。データリスト処理部１３１は対応点をフレーム画像から対応点を検出し、頂点追跡判定部１３２は対応点が見つかったか否か判定して対応点の存在を示す存在フラグを設定するとともに、対応点が見つからない場合は、前フレームを参照し、対応点を決定する、あるいは、対応点が消失したと判定する。時間長判定部１３３は、対応点が消失した場合、その対応点を有する曲面パッチの持続時間を設定するとともにパッチリストから削除する。パッチリストから削除された曲面パッチについては以降のフレームで処理しない。
【００３４】
制御点追跡部１４は、一次結合近似部１４１、制御点評価補正部１４２を備え、前のフレームにおける頂点（対応点）、制御点間の位置関係と、頂点追跡部１３が現在処理対象のフレームから検出した対応点の位置関係から、各パッチの辺を構成するために必要な制御点の位置を求めて制御点リストに登録する。一次結合近似部１４１は、前のフレームにおける頂点と制御点の位置関係を一次結合で表して結合係数を求め、頂点追跡部１３が検出した対応点と求めた結合係数により制御点の位置を推定する。制御点評価補正部１４２は、一次結合近似部１４１が推定した制御点により構成される曲面パッチの辺とフレーム画像から抽出したエッジを構成する点との距離に基づいて制御点の位置を補正する。
【００３５】
パラメトリック立体化部１５は、曲線近似部１５１、誤差評価分割部１５２を備え、頂点追跡部１３、制御点追跡部１４が求めた頂点、制御点を時間軸方向に追跡して動画像をパラメトリック立体で表現する。曲線近似部１５１は、頂点、制御点の時間軸方向の軌跡をベジエ曲線で近似する。誤差評価分割部１５２は、曲線近似部１５１が近似した曲線と近似対象の頂点、制御点の対応点列との最大距離を評価し、最大距離が所定の閾値よりも大きい場合は近似した曲線を分割する。なお、本実施の形態におけるパラメトリック立体は、底面がパラメトリック曲面パッチである多角形であり、側面がパラメトリック曲面パッチである四角形から構成される立体を指す。
【００３６】
色値取得部１６は、生成したパラメトリック立体の頂点、制御点の色値を動画像データのフレーム画像から取得する。フレーム画像から色値が直接取得できない制御点については、取得できる色値を補間して決定する。
【００３７】
出力部１７は、全てのパラメトリック立体について、頂点、制御点の時空間座標値、その座標値における色値（ｘ，ｙ，ｔ，ｃ）のデータをファイルとして出力する。
【００３８】
次に、本実施の形態における動画像処理装置の処理の流れについて説明する。
【００３９】
図２〜４は、本実施の形態における動画像処理装置の処理の流れを示すフローチャートである。図２に示す処理で開始フレーム画像の静止画像をベクトル化し、図３に示す処理でベクトル化したデータの時間軸方向の軌跡を追跡し、図４に示す処理でベクトル化したデータの動きをパラメトリック立体で表している。以下、図２に示す処理から順に説明する。
【００４０】
まず、図２に示す静止画像のベクトル化処理について説明する。
【００４１】
動画像読込部１１が、動画像ファイルを読み込んで動画像データを蓄積部１８に蓄積する（ステップＳ１０１）。このときに、利用者からベクトル化の対象とする時間的範囲（開始フレームと終了フレーム）の指定を受け付けてもよい（ステップＳ１０２）。
【００４２】
続いて、静止画像ベクトル化部１２が、蓄積部１８から動画像データの開始フレーム画像を読み出し、開始フレーム画像のベクトル化を実施する（ステップＳ１０３）。開始フレーム画像はビットマップ形式の画像であり、ビットマップ形式の画像のベクトル化は、非特許文献１，２，ないし３に記載された手法、あるいは他の手法を用いることができる。開始フレーム画像のベクトル化の際に、利用者からベクトル化の対象とする被写体の指定を受け付けてもよい（ステップＳ１０４）。
【００４３】
静止画像ベクトル化部１２により、開始フレーム画像内の閉領域が三角形あるいは四角形の曲面パッチにより分割され、曲面パッチの辺で被写体オブジェクトの輪郭が良好に近似される。ベクトル化により、画像を四角形ベジエパッチで近似する場合は、ひとつのパッチあたり、４個の頂点と１２個の制御点が生成される。画像を三角形ベジエパッチで近似する場合は、ひとつのパッチあたり、３個の頂点と７個の制御点が生成される。なお、本実施の形態では、曲面の「高さ」に相当する変数を、「色値」に置き換えている。カラー画像の場合、例えばＲＧＢ表示系であれば、Ｒ（赤）、Ｇ（緑）、Ｂ（青）の各色ごとに曲面パッチを生成してもよい。ここでは、色成分の数や表示系については言及しないが、応用する状況に応じてカラー画像もグレー画像も用いることができる。
【００４４】
生成された各曲面パッチの頂点、制御点の各リストは蓄積部１８に蓄積される（ステップＳ１０５）。このとき、各頂点がどの曲面パッチに属するかを記憶させる。例えば、曲面パッチ、頂点それぞれに識別子を付与し、曲面パッチを指定するとその曲面パッチを構成する頂点の識別子を取得でき、または、頂点を指定するとその頂点を含む曲面パッチ（ひとつではない場合もある）の識別子を取得できるようにしておく。同様に、頂点と制御点も関連付けておく。
【００４５】
次に、図３に示す、ベクトル化したデータの時間軸方向の軌跡を追跡する処理について説明する。
【００４６】
データリスト処理部１３１は、動画像ファイルの次フレーム画像を蓄積部１８から読み出し、読み出したフレーム画像における各曲面パッチの各頂点に対応する対応点を検出する（ステップＳ２０１）。また、各曲面パッチに対して読み出したフレーム画像のフレーム番号あるいは持続時間を付与する。曲面パッチの辺はフレーム画像の閉領域のエッジを近似しており、曲面パッチの頂点は曲面パッチの辺（曲線）の両端であるので、各頂点は、フレーム画像内の閉領域の角などの特徴点となり、検出しやすい。そこで、データリスト処理部１３１は、読み出したフレーム画像の閉領域の角を頂点の対応点として検出する。
【００４７】
図５は、頂点を追跡する様子を示す図である。フレームＴ１→Ｔ２→Ｔ３→Ｔ４と変化するものとする。同図では、わかりやすくするため、曲面パッチの辺も記載している。同図の頂点Ｐ１，Ｐ２，Ｐ３で構成される三角形パッチにおいて、フレームＴ２では、頂点Ｐ１，Ｐ２，Ｐ３の対応点が見つかっており、フレームＴ３では、頂点Ｐ２または頂点Ｐ３の対応点が見つからず、フレームＴ４では、再び頂点Ｐ１，Ｐ２，Ｐ３の対応点が見つかっている。
【００４８】
フレーム画像を読み出して対応点を検出した後、各曲面パッチについて、以下に示す頂点の追跡処理を行う。
【００４９】
頂点追跡判定部１３２は、曲面パッチから１つの頂点を選択し、その頂点の対応点が存在するか否か判定する（ステップＳ２０２）。
【００５０】
対応点が存在する場合は、その頂点に対する対応点として対応点リストに座標値を追加し、頂点に対応する対応点の存在を示す存在フラグをオンとする（ステップＳ２０３）。
【００５１】
曲面パッチのすべての頂点について対応点の存在を判定する処理が終了した場合は次の曲面パッチについての処理へ進み、曲面パッチ内にまだ処理していない頂点が存在する場合はステップＳ２０２に戻る（ステップＳ２０４）。なお、隣接する曲面パッチでは頂点を共有しているため、すでに対応点が存在していることが明らかな頂点については処理済みとする。
【００５２】
一方、対応点が存在しない場合は、前フレームではその頂点の対応点が存在していたか否か判定する（ステップＳ２０５）。頂点に対応する存在フラグを評価することで対応点が存在していたか否か判定できる。
【００５３】
前フレームで対応点が存在していた場合は、頂点を含む曲面パッチの前フレームにおける面積を計算し（ステップＳ２０６）、計算した面積が所定の閾値より大きいか否か判定する（ステップＳ２０７）。本実施の形態では、曲面パッチの面積として、図５の点線で示される各頂点Ｐ１，Ｐ２，Ｐ３を結んだ三角形の面積を計算する。
【００５４】
計算した面積が所定の閾値よりも大きい場合は、頂点に対応する対応点として前フレームにおける対応点の座標値を現在処理対象のフレームの対応点として対応点リストに追加する（ステップＳ２０８）。
【００５５】
計算した面積が所定の閾値以下の場合は、現在のフレームで曲面パッチが消失したと判定する。消失した曲面パッチについては、パッチリストから削除し、時間長判定部１３３が、消失した曲面パッチは、開始フレームから前フレームまで持続したとし、フレーム数あるいはフレーム番号をその曲面パッチのデータとして付与し、以降のフレームではその曲面パッチについての処理を行わない（ステップＳ２０９）。
【００５６】
一方、ステップＳ２０５において前フレームにも対応点が存在していなかった、つまり、２フレーム連続で対応点が存在していなかったと判定された頂点を含む曲面パッチも消失したと判定する。時間長判定部１３３は、消失した曲面パッチは、２つ前のフレームまで持続したとし、フレーム数あるいはフレーム番号をその曲面パッチのデータとして付与する。なお、本実施の形態では、２フレーム続けて対応点が見つからない場合に曲面パッチが消失したと判定しているが、このフレーム数は２に限るものではない。
【００５７】
図５に示す例では、フレームＴ３において、頂点Ｐ１，Ｐ２の対応点は見つかったが、頂点Ｐ３の対応点が見つかっていないので、フレームＴ２における三角形Ｐ１／Ｐ２／Ｐ３の面積を計算して、頂点Ｐ３の追跡処理を続行するか否か判定する。計算した面積が所定の閾値より大きければ、フレームＴ２の頂点Ｐ３の対応点の座標値をフレームＴ３における頂点Ｐ３の対応点（Ｐ３’）として対応点リストに追加する。同図に示す例では、フレームＴ４において頂点Ｐ３の対応点が見つかったので、フレームＴ３の頂点Ｐ３の対応点をＰ３’とみなしてフレームＴ４以降も頂点Ｐ３の追跡処理を行う。なお、フレームＴ４においても頂点Ｐ３の対応点が見つからなかった場合は、フレームＴ３において頂点Ｐ１，Ｐ２，Ｐ３で構成される曲面パッチは消失したと判定される。
【００５８】
以上ステップＳ２０２からステップＳ２０９までの処理を全ての曲面パッチについて行う。まだ処理していない曲面パッチが存在する場合はステップＳ２０２に戻り（ステップＳ２１０）、その曲面パッチの各頂点について処理を行う。
【００５９】
全ての曲面パッチについて頂点の追跡処理が終了したら、制御点追跡部１４が、各曲面パッチの辺の曲線を生成するための制御点の追跡処理を行う。３次ベジエ曲線においては、１つの曲線セグメントを生成するために２つの端点と２つの制御点が必要となる。２つの端点は、曲面パッチの２つの頂点に該当する。また、３次ベジエ曲線において一般に生成される曲線は制御点を通過しないため、制御点はフレーム画像内の閉領域のエッジやコーナーなどの特徴点となるとは限らない。
【００６０】
各フレームごとに被写体オブジェクトのエッジを抽出し、エッジを近似するベジエ曲線を生成するように制御点を決定する方法もあるが、本実施の形態では、フレーム間で曲面パッチの辺を形成する頂点（端点）と制御点の相互の位置関係が大きく変化しないと仮定し、前フレームにおける各頂点と各制御点の位置関係と現在のフレームの各頂点の位置関係に基づいて制御点を推定する。
【００６１】
まず、一次結合近似部１４１が、ある頂点に対する制御点の位置ベクトルをある頂点に対する曲面パッチの辺を構成する２つの頂点の位置ベクトルの一次結合で表す（ステップＳ２１１）。具体的には、次式（７）に示すように、前フレームにおける、頂点Ｐ１，Ｐ２を結ぶ曲線の制御点Ｃ１，Ｃ２それぞれを、その曲線を構成しない同じ曲面パッチの別の頂点Ｐ３対する頂点Ｐ１，Ｐ２の位置ベクトルで表す。
【数７】
【００６２】
図６に示すように、現在のフレームにおいても前フレームにおける頂点と制御点の位置関係が大きく変化しないと仮定し、式（７）の一次結合係数ａ，ｂ，ｃ，ｄが保存されるとして、次式（８）に示すように、一次結合係数ａ，ｂ，ｃ，ｄを用いて、現在のフレームにおける制御点Ｃ１’，Ｃ２’それぞれを頂点Ｐ３’に対する頂点Ｐ１’，Ｐ２’の位置ベクトルで表す。
【数８】
【００６３】
なお、パッチ形状が四角形の場合は、辺を構成する頂点以外に２つの頂点が存在するが、いずれか一方を位置ベクトルの始点と定めればよい。
【００６４】
続いて、制御点評価補正部１４２が、頂点Ｐ１’，Ｐ２’と制御点Ｃ１’，Ｃ２’で生成されるベジエ曲線と、現在処理対象のフレーム画像内の閉領域のエッジとの差分を評価して制御点Ｃ１’，Ｃ２’の位置を補正する（ステップＳ２１２）。エッジを構成する画素とベジエ曲線との差分を計算すると計算量が多くなるため、本実施の形態では、エッジ上の２点とベジエ曲線との距離で評価する。
【００６５】
具体的には、図７に示すように、制御点Ｃ１’とベジエ曲線との距離が最小となるベジエ曲線上の点をＢ１、直線Ｃ１’Ｂ１とエッジとの交点をＥ１として、点Ｂ１，Ｅ１間の距離が所定の閾値よりも小さければ制御点Ｃ１’の位置を補正せず、点Ｂ１，Ｅ１間の距離が所定の閾値以上で、点Ｃ１’，Ｂ１間の距離≦点Ｃ１’，Ｅ１間の距離であれば、制御点Ｃ１’を点Ｃ１’から点Ｂ１の方向に所定の距離移動させて新たな制御点Ｃ１’とし、点Ｃ１’，Ｂ１間の距離≧点Ｃ１’，Ｅ１間の距離であれば、制御点Ｃ１’を点Ｂ１から点Ｃ１’の方向に所定の距離移動させて新たな制御点Ｃ１’とする。制御点Ｃ１’を移動させる距離は、例えば、点Ｃ１’Ｂ１間の距離に適当な実数（例えば、０．５）を乗じた値とする。制御点Ｃ２’についても同様の処理を行い、頂点Ｐ１’，Ｐ２’と新たな制御点Ｃ１’，Ｃ２’で生成されるベジエ曲線について、点Ｂ１，Ｅ１間、点Ｂ２，Ｅ２間の距離が所定の閾値よりも小さくなるまで上記の補正処理を繰り返す。
【００６６】
任意の点とベジエ曲線との最短距離を計算し、最短距離となるベジエ曲線上の点を求める方法は、例えば、Philip J. Schneider,“Solving the Nearest-point-on-curve Problem”, Graphics Gems, Morgan Kaufmann Publishers（参考文献１）や Philip J. Schneider,“An Algorithm for Automatically Fitting Digitized Curves”, Graphics Gems, Morgan Kaufmann Publishers（参考文献２）に解説されている。
【００６７】
以上の制御点の追跡処理を全ての制御点について行う（ステップＳ２１３）。なお、三角形ベジエパッチの場合はさらに三角形内部にひとつの制御点があり、四角形ベシエパッチの場合は内部に４つの制御点がある。これらの制御点は、上記ステップＳ２１１の一次結合係数の保存のみで評価してもよい。
【００６８】
すべての制御点の追跡処理が終了したら、ステップＳ２０１に戻り次のフレーム画像を読み込んでそのフレーム画像の頂点、制御点を求め、全フレームについて処理が終了した場合、あるいは、全ての曲面パッチが消失した場合は、ベクトル化したデータの動きをパラメトリック立体で表現する処理に進む（ステップＳ２１４）。
【００６９】
次に、図４に示す、ベクトル化したデータの動きをパラメトリック立体で表現する処理について説明する。図４に示す処理では、頂点、制御点の時間軸方向の軌跡をベジエ曲線で近似し、その結果生成される制御点を用いてパラメトリック立体を生成する。
【００７０】
曲線近似部１５１は、各曲面パッチについて、曲面パッチを構成する全ての頂点、制御点の時間軸方向の軌跡をベジエ曲線で近似する（ステップＳ３０１）。例えば、参考文献２で解説されている手法により、３次の区分的ベジエ曲線により近似する。
【００７１】
図８に、四角形ベジエパッチを時間軸方向に追跡したベジエ６面体の例を示す。図８（ａ）は、頂点追跡部１３で追跡した頂点の時間軸方向の軌跡を図示した図であり、図８（ｂ）は、図８（ａ）の軌跡を近似するベジエ曲線を構成する制御点を図示した図である。図８（ｃ）には、図８（ａ）に示すベジエ立体における各パラメータの定義域を示している。また、同様に、図９に、三角形ベジエパッチを時間軸方向に追跡したベシエ三角柱の例を示しておく。
【００７２】
頂点、制御点の軌跡を近似したベジエ曲線の開始フレーム、終了フレームにおける端（頂点、制御点）は、（ｘ，ｙ，ｔ）空間において同じｔを持つ。軌跡を近似したベジエ曲線を構成する各曲面パッチの頂点、制御点のうち、時間軸方向の添字が等しいもの、例えば、図８（ｂ）におけるＰｉｊ１となる１６点は、（ｘ，ｙ，ｔ）空間において同じｔを持つとよい。同様に、Ｐｉｊ２となる１６点についても同じｔを持つと良い。また、図８（ｂ）におけるＰｉｊｋ，１となる１０点、およびＰｉｊｋ，２となる１０点も（ｘ，ｙ，ｔ）空間においてそれぞれ同じｔを持つと良い。これにより、図８，９に示すパラメトリック立体において、パラメータ（ｕ，ｖ，ｗ）のｗの値を一つ決めると、ｔが一意に決まり、あとの計算処理が容易になる。
【００７３】
続いて、誤差評価分割部１５２が、頂点、制御点の時間軸方向の軌跡を近似した曲線と近似対象の頂点、制御点の対応点列との最大距離を評価する（ステップＳ３０２）。そして、ひとつの曲面パッチを構成する頂点、制御点の時間軸方向の軌跡を近似した曲線のうち、もっとも誤差が大きいものを選び、その誤差と所定の閾値と比較する（ステップＳ３０３）。
【００７４】
最大誤差が所定の閾値よりも大きい場合、誤差評価分割部１５２は、もっとも誤差が大きい曲線を分割する（ステップＳ３０４）。曲線の分割方法は、２次元平面上の曲線について、参考文献２に記載されている。３次元曲線についても本質的に同様の処理で実現できる。図１０に２次元平面上のベジエ曲線を分割する例を示す。例えば、図１０の点線で示す頂点Ｐ１から頂点Ｐ２までの追跡点列を図１０の実線で示すベジエ曲線で近似しようとしても誤差が大きくなる場合、追跡点列とベジエ曲線の距離が最も大きくなる点Ｐ１２を分割点として選び、新たに分割点の前後それぞれにおいてベジエ曲線で近似する。図１０に示すように、ベジエ曲線を分割した場合、ベジエ曲線上の分割点が新たな頂点Ｐ１２となり、頂点Ｐ１，Ｐ１２を結ぶベジエ曲線の２つの制御点Ｃ１１，Ｃ１２、頂点Ｐ１２，Ｐ２を結ぶベジエ曲線の２つの制御点Ｃ２１，Ｃ２２が新たに追加される。
【００７５】
さらに、同じ曲面パッチを構成する他の頂点、制御点の時間軸方向の軌跡を近似した曲線も分割し（ステップＳ３０５）、分割で生じた新たな立体に対応する曲面パッチをパッチリストに追加する（ステップＳ３０６）。他の曲線を分割する際には、ステップＳ３０４で曲線の分割に用いたパラメータ値Ｗに対応する時間変数Ｔを求め、時間変数Ｔに相当するパラメータ値で分割する。この分割処理は、図７（ａ），８（ａ）で示した立体を時間軸に垂直な面で切断することに相当する。なお、隣接するパッチにおいて、頂点、制御点を共有する場合もあるが、片方のパッチでは分割が行われ、他方のパッチでは分割が行われないという場合も生じる。
【００７６】
一方、最大誤差が所定の閾値以下の場合は、色値取得部１６が、パッチを時間軸方向に追跡して生成されたベジエ立体の頂点、制御点の色値を確定させる（ステップＳ３０７）。具体的には、パッチの開始フレーム、終了フレームにおける色値は、パッチの各頂点、制御点の座標値における色値をそのフレームから取得することで得られる。制御点がパッチの内部にある場合は、該当座標値の色値を用い、制御点がパッチの外部にある場合は、適当な初期値、例えば、制御点に最も近いパッチの辺上の点の色値を与える。あるいは、数式（５），（６）で時間変数ｔを初期値または終了値に固定した際のＰ（ｕ，ｖ，ｗ）の各画素位置に該当する値を計算し、色値の最大誤差が所定の値より小さくなるように色値を変化させながら非線形最小二乗法、例えば、Ｌｅｖｅｎｂｅｒｇ−Ｍａｒｑｕａｒｄｔ法を用いて色値を求めてもよい。このとき、計算を容易化するために、オブジェクトの境界となるパッチの辺は曲線で表し、オブジェクトの内部は辺が線分となる三角形で表現してもよい。例えば、開始フレームや終了フレームにおいて、図１１（ａ）では全ての辺が曲線から構成されるパッチを用いて近似し、図１１（ｂ）ではオブジェクトの輪郭のみを曲線で表し、内部の辺は線分となるパッチを用いて近似し、図１１（ｃ）ではオブジェクトの輪郭も含めて全ての辺が線分となるパッチを用いて近似している。辺が線分で構成される三角形では、制御点は辺上にあるため、辺を３分割する点を制御点とみなしてその座標値での色値を用いる。図１１（ａ）のように辺が曲線で構成されるパッチを用いる場合でも、図１１（ｃ）のように頂点を結んだ線分を３分割する点の位置の色値を用いてもよい。また、頂点の色値を初期値として非線形最小二乗法で反復計算して求めてもよい。
【００７７】
パッチの開始フレーム、終了フレーム以外の制御点の色値、および、分割された場合の頂点、制御点の色値については、対応する頂点、制御点の開始フレームにおける色値を用いてもよいし、図１２に示すように補間してもよい。図１２に示す例では、分割をした際の時間変数Ｔの前後のフレームをＴｆ，Ｔｂ（Ｔｆ＜Ｔｂ）として、Ｔｆでの色値をＣｆ、Ｔｂでの色値をＣｂとおき、Ｔにおける色値Ｃ（Ｔ）を次式（９）で補間する。
【００７８】
Ｃ（Ｔ）＝（（Ｔ−Ｔｂ）Ｃｆ ＋ （Ｔｆ−Ｔ）Ｃｂ）／Ｔｂ−Ｔｆ （９）
以上ステップＳ３０１からステップＳ３０７までの処理を全てのパッチについて行う。まだ処理していないパッチが存在する場合はステップＳ３０１に戻り（ステップＳ３０８）、そのパッチの動きをパラメトリック立体で表現する。
【００７９】
全てのパッチについて、頂点、制御点の時空間座標値およびその座標値における色値（ｘ，ｙ，ｔ，ｃ）を決定し、データをファイルとして出力する（Ｓ３０９）。出力するデータは、パッチ毎に、パッチＩＤ、パッチの開始時刻、パッチの終了時刻、ベジエ三角柱の場合は４０個の頂点および制御点のｘ座標値、ｙ座標値、ｔ座標値、色値を有している。ベジエ６面体を利用する場合は６４個の頂点および制御点のデータとなる。
【００８０】
次に、出力されたベクトルデータから動画像を生成する手順について説明する。
【００８１】
座標（ｘ，ｙ）を指定し、ベクトルデータがベジエ６面体の場合は式（５）、ベジエ三角形の場合は式（６）を用いて、時空間座標値（ｘ，ｙ，ｔ）となるパラメータ（ｕ，ｖ，ｗ）を Newton-Raphson を用いて求め、パラメータ（ｕ，ｖ，ｗ）を用いて式（５）または式（６）に代入し、（ｘ，ｙ，ｔ）における色値を計算する。座標値（ｘ，ｙ）をディジタル画像における画素の中心位置、ｔをディジタル画像のおけるフレーム位置と解釈すれば、ベクトルデータからディジタル動画像を生成することが可能となる。
【００８２】
以上説明したように、本実施の形態によれば、動画像データの開始フレーム画像内の類似した色値を持つ閉領域を四角形の曲面パッチに分割し、曲面パッチの頂点、制御点を動画像データのフレームを参照して時系列順に追跡し、頂点、制御点の時間軸方向の軌跡をパラメトリック曲線で近似し、パラメトリック曲線の頂点および制御点に対応する色値を動画像データのフレーム画像から取得して、パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力することにより、動画像データをベクトルデータで表現することが可能となり、より少ないデータ量で、拡大縮小しても画質を損なわず表現することができる。また、オブジェクトあるいはパッチレベルでの内容の編集や修正を行うことができる。
【００８３】
なお、本実施の形態では、パラメトリック曲線や曲面、立体において、ベジエ曲線、ベジエ曲面、ベジエ立体を念頭に説明したが、本質的にはどのようなパラメトリック曲線／曲面／立体を用いてもよい。例えば、有理ベジエ立体やＢスプライン立体としても適用可能である。また、従来手法においては、パラメトリック曲面パッチの次数として３次で表現されることが多い。これについても、本質的には２次以上であれば次数はいくつでもよいが、処理の容易さから次数３のものが用いられることが多い。
【符号の説明】
【００８４】
１１…動画像読込部
１２…静止画像ベクトル化部
１３…頂点追跡部
１３１…データリスト処理部
１３２…頂点追跡判定部
１３３…時間長判定部
１４…制御点追跡部
１４１…一次結合近似部
１４２…制御点評価補正部
１５…パラメトリック立体化部
１５１…曲線近似部
１５２…誤差評価分割部
１６…色値取得部
１７…出力部
１８…蓄積部
【特許請求の範囲】
【請求項１】
動画像データを読み込み蓄積手段に蓄積する読込手段と、
前記蓄積手段から前記動画像データの指定されたフレーム画像を読み出し、当該フレーム画像内の類似した色値を持つ閉領域を曲面パッチに分割し、曲面パッチの辺の端を頂点として頂点リストに登録し、その辺を構成するための点を制御点として制御点リストに登録するベクトル化手段と、
前記動画像データから時系列順にフレーム画像を読み出し、前記曲面パッチ毎に、読み出したフレーム画像から前記頂点リストに登録された頂点に対応する対応点を検出してそのフレーム画像における頂点として頂点リストに登録する頂点追跡手段と、
時系列順に読み出したフレーム画像毎に、前記曲面パッチそれぞれについて、前記頂点リストに登録された頂点を前記曲面パッチの辺の端としたときに前記曲面パッチの辺を構成するための制御点の位置を、その頂点の位置関係に基づいて推定してそのフレーム画像における制御点として制御点リストに登録する制御点追跡手段と、
前記頂点リストおよび前記制御点リストを参照し、前記ベクトル化手段により登録された頂点および制御点それぞれの時間軸方向の軌跡をパラメトリック曲線で近似する曲線近似手段と、
前記曲線近似手段が近似したパラメトリック曲線の頂点および制御点に対応する色値を前記動画像データのフレーム画像から取得する色値取得手段と、
前記パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力する出力手段と、
を有することを特徴とする動画像処理装置。
【請求項２】
前記制御点追跡手段は、
前のフレームにおける前記頂点と前記制御点の位置関係を当該制御点により構成される曲面パッチの辺の両端の頂点と別の頂点の一次結合で表して結合係数を求め、前記制御点の位置を求めるフレームにおける前記頂点と前記結合係数により前記制御点の位置を推定する一次結合近似手段と、
推定した前記制御点により構成される曲面パッチの辺とフレーム画像から抽出したエッジを構成する点との距離に基づいて前記制御点の位置を補正する補正手段と、
を有することを特徴とする請求項１記載の動画像処理装置。
【請求項３】
前記頂点追跡手段は、
前記対応点が検出できない場合に、当該対応点を含む前のフレームにおける曲面パッチの各頂点を結んで構成される図形の面積を計算し、当該面積が所定の閾値よりも小さい場合は対応点なしと判定し、当該面積が所定の閾値以上の場合は前のフレームにおける対応点の位置を今のフレームにおける対応点の位置とする判定手段と、
前記判定手段が所定の数のフレームに渡って対応点なし判定した場合に、当該対応点を含む前記曲面パッチについて以降のフレームについて処理を行わないとする消失手段と、
を有することを特徴とする請求項１又は２記載の動画像処理装置。
【請求項４】
読込手段による、動画像データを読み込み蓄積手段に蓄積するステップと、
ベクトル化手段による、前記蓄積手段から前記動画像データの指定されたフレーム画像を読み出し、当該フレーム画像内の類似した色値を持つ閉領域を曲面パッチに分割し、曲面パッチの辺の端を頂点として頂点リストに登録し、その辺を構成するための点を制御点として制御点リストに登録するステップと、
頂点追跡手段による、前記動画像データから時系列順にフレーム画像を読み出し、前記曲面パッチ毎に、読み出したフレーム画像から前記頂点リストに登録された頂点に対応する対応点を検出してそのフレーム画像における頂点として頂点リストに登録するステップと、
制御点追跡手段による、時系列順に読み出したフレーム画像毎に、前記曲面パッチそれぞれについて、前記頂点リストに登録された頂点を前記曲面パッチの辺の端としたときに前記曲面パッチの辺を構成するための制御点の位置を、その頂点の位置関係に基づいて推定してそのフレーム画像における制御点として制御点リストに登録するステップと、
曲線近似手段による、前記頂点リストおよび前記制御点リストを参照し、前記ベクトル化手段により登録された頂点および制御点それぞれの時間軸方向の軌跡をパラメトリック曲線で近似するステップと、
色値取得手段による、前記曲線近似手段が近似したパラメトリック曲線の頂点および制御点に対応する色値を前記動画像データのフレーム画像から取得するステップと、
出力手段による、前記パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力するステップと、
を有することを特徴とする動画像処理方法。
【請求項５】
前記制御点追跡手段による前記制御点リストに登録するステップは、
一次結合近似手段による、前のフレームにおける前記頂点と前記制御点の位置関係を当該制御点により構成される曲面パッチの辺の両端の頂点と別の頂点の一次結合で表して結合係数を求め、前記制御点の位置を求めるフレームにおける前記頂点と前記結合係数により前記制御点の位置を推定するステップと、
補正手段による、推定した前記制御点により構成される曲面パッチの辺とフレーム画像から抽出したエッジを構成する点との距離に基づいて前記制御点の位置を補正するステップと、
を有することを特徴とする請求項４記載の動画像処理方法。
【請求項６】
前記頂点追跡手段による前記頂点リストに登録するステップは、
判定手段による、前記対応点が検出できない場合に、当該対応点を含む前のフレームにおける曲面パッチの各頂点を結んで構成される図形の面積を計算し、当該面積が所定の閾値よりも小さい場合は対応点なしと判定し、当該面積が所定の閾値以上の場合は前のフレームにおける対応点の位置を今のフレームにおける対応点の位置とするステップと、
消失手段による、前記判定手段が所定の数のフレームに渡って対応点なし判定した場合に、当該対応点を含む前記曲面パッチについて以降のフレームについて処理を行わないとするステップと、
を有することを特徴とする請求項４又は５記載の動画像処理方法。
【請求項７】
請求項１乃至３のいずれかに記載の動画像処理装置としてコンピュータを機能させることを特徴とする動画像処理プログラム。
【請求項１】
動画像データを読み込み蓄積手段に蓄積する読込手段と、
前記蓄積手段から前記動画像データの指定されたフレーム画像を読み出し、当該フレーム画像内の類似した色値を持つ閉領域を曲面パッチに分割し、曲面パッチの辺の端を頂点として頂点リストに登録し、その辺を構成するための点を制御点として制御点リストに登録するベクトル化手段と、
前記動画像データから時系列順にフレーム画像を読み出し、前記曲面パッチ毎に、読み出したフレーム画像から前記頂点リストに登録された頂点に対応する対応点を検出してそのフレーム画像における頂点として頂点リストに登録する頂点追跡手段と、
時系列順に読み出したフレーム画像毎に、前記曲面パッチそれぞれについて、前記頂点リストに登録された頂点を前記曲面パッチの辺の端としたときに前記曲面パッチの辺を構成するための制御点の位置を、その頂点の位置関係に基づいて推定してそのフレーム画像における制御点として制御点リストに登録する制御点追跡手段と、
前記頂点リストおよび前記制御点リストを参照し、前記ベクトル化手段により登録された頂点および制御点それぞれの時間軸方向の軌跡をパラメトリック曲線で近似する曲線近似手段と、
前記曲線近似手段が近似したパラメトリック曲線の頂点および制御点に対応する色値を前記動画像データのフレーム画像から取得する色値取得手段と、
前記パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力する出力手段と、
を有することを特徴とする動画像処理装置。
【請求項２】
前記制御点追跡手段は、
前のフレームにおける前記頂点と前記制御点の位置関係を当該制御点により構成される曲面パッチの辺の両端の頂点と別の頂点の一次結合で表して結合係数を求め、前記制御点の位置を求めるフレームにおける前記頂点と前記結合係数により前記制御点の位置を推定する一次結合近似手段と、
推定した前記制御点により構成される曲面パッチの辺とフレーム画像から抽出したエッジを構成する点との距離に基づいて前記制御点の位置を補正する補正手段と、
を有することを特徴とする請求項１記載の動画像処理装置。
【請求項３】
前記頂点追跡手段は、
前記対応点が検出できない場合に、当該対応点を含む前のフレームにおける曲面パッチの各頂点を結んで構成される図形の面積を計算し、当該面積が所定の閾値よりも小さい場合は対応点なしと判定し、当該面積が所定の閾値以上の場合は前のフレームにおける対応点の位置を今のフレームにおける対応点の位置とする判定手段と、
前記判定手段が所定の数のフレームに渡って対応点なし判定した場合に、当該対応点を含む前記曲面パッチについて以降のフレームについて処理を行わないとする消失手段と、
を有することを特徴とする請求項１又は２記載の動画像処理装置。
【請求項４】
読込手段による、動画像データを読み込み蓄積手段に蓄積するステップと、
ベクトル化手段による、前記蓄積手段から前記動画像データの指定されたフレーム画像を読み出し、当該フレーム画像内の類似した色値を持つ閉領域を曲面パッチに分割し、曲面パッチの辺の端を頂点として頂点リストに登録し、その辺を構成するための点を制御点として制御点リストに登録するステップと、
頂点追跡手段による、前記動画像データから時系列順にフレーム画像を読み出し、前記曲面パッチ毎に、読み出したフレーム画像から前記頂点リストに登録された頂点に対応する対応点を検出してそのフレーム画像における頂点として頂点リストに登録するステップと、
制御点追跡手段による、時系列順に読み出したフレーム画像毎に、前記曲面パッチそれぞれについて、前記頂点リストに登録された頂点を前記曲面パッチの辺の端としたときに前記曲面パッチの辺を構成するための制御点の位置を、その頂点の位置関係に基づいて推定してそのフレーム画像における制御点として制御点リストに登録するステップと、
曲線近似手段による、前記頂点リストおよび前記制御点リストを参照し、前記ベクトル化手段により登録された頂点および制御点それぞれの時間軸方向の軌跡をパラメトリック曲線で近似するステップと、
色値取得手段による、前記曲線近似手段が近似したパラメトリック曲線の頂点および制御点に対応する色値を前記動画像データのフレーム画像から取得するステップと、
出力手段による、前記パラメトリック曲線の頂点および制御点の時空間座標値と対応する色値を出力するステップと、
を有することを特徴とする動画像処理方法。
【請求項５】
前記制御点追跡手段による前記制御点リストに登録するステップは、
一次結合近似手段による、前のフレームにおける前記頂点と前記制御点の位置関係を当該制御点により構成される曲面パッチの辺の両端の頂点と別の頂点の一次結合で表して結合係数を求め、前記制御点の位置を求めるフレームにおける前記頂点と前記結合係数により前記制御点の位置を推定するステップと、
補正手段による、推定した前記制御点により構成される曲面パッチの辺とフレーム画像から抽出したエッジを構成する点との距離に基づいて前記制御点の位置を補正するステップと、
を有することを特徴とする請求項４記載の動画像処理方法。
【請求項６】
前記頂点追跡手段による前記頂点リストに登録するステップは、
判定手段による、前記対応点が検出できない場合に、当該対応点を含む前のフレームにおける曲面パッチの各頂点を結んで構成される図形の面積を計算し、当該面積が所定の閾値よりも小さい場合は対応点なしと判定し、当該面積が所定の閾値以上の場合は前のフレームにおける対応点の位置を今のフレームにおける対応点の位置とするステップと、
消失手段による、前記判定手段が所定の数のフレームに渡って対応点なし判定した場合に、当該対応点を含む前記曲面パッチについて以降のフレームについて処理を行わないとするステップと、
を有することを特徴とする請求項４又は５記載の動画像処理方法。
【請求項７】
請求項１乃至３のいずれかに記載の動画像処理装置としてコンピュータを機能させることを特徴とする動画像処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１２−２５６２８０（Ｐ２０１２−２５６２８０Ａ）
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願番号】特願２０１１−１３００１０（Ｐ２０１１−１３００１０）
【出願日】平成２３年６月１０日（２０１１．６．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願日】平成２３年６月１０日（２０１１．６．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]