(57)【特許請求の範囲】
【請求項１】
動画データの画素数を減少させる減少手段と、
前記減少手段によって画素数が減少した動画データの時間区間である第１の区間と第２の区間とを指定する指定手段と、
前記第１の区間の動画データ及び前記第２の区間の動画データを構成する複数の静止画データの２次元座標が揃うように該複数の静止画データが時系列順に並べられた静止画群が占める空間における、前記２次元座標の横方向に隣接する２つの画素の間、前記２次元座標の縦方向に隣接する２つの画素の間、及び、前記静止画群の時間方向に隣接する２つの画素の間、を通って該空間を分割する面であって、前記第１の区間における該面よりも前の動画データと前記第２の区間における該面よりも後の動画データとを接合するための接合面を決定する決定手段と、
前記減少手段における画素数の減少率を下げ、且つ、前記指定手段が指定する前記第１の区間及び前記第２の区間のそれぞれを該それぞれの区間において決定された前記接合面を含むような区間に狭めて、前記減少手段、前記指定手段、及び、前記決定手段の処理を、繰り返し実行する繰返し手段と、
前記第１の区間における接合面よりも前の動画データと、前記第２の区間における接合面よりも後の動画データと、が順に繋ぎ合わされた動画データを生成する生成手段と、
を備える動画生成装置。
【請求項２】
前記指定手段は、１つの動画データの時間区間を前記第１の区間として指定し、該１つの動画データの一部の時間区間であって前記第１の区間よりも前の区間を前記第２の区間として指定し、
前記生成手段は、前記１つの動画データのうちの前記第１の区間における接合面よりも前であって前記第２の区間における接合面よりも後の動画データが繰り返し繋ぎ合わされた動画データを生成する、
ことを特徴とする請求項１に記載の動画生成装置。
【請求項３】
前記決定手段は、前記第１の区間における接合面と前記第２の区間における接合面との間の時間長が前記生成される動画データの繰り返し周期のあらかじめ設定された最小値以上となるように、前記接合面を決定する、
ことを特徴とする請求項２に記載の動画生成装置。
【請求項４】
前記指定手段は、２つの動画データのうちの第１の動画データの時間区間を前記第１の区間として指定し、該２つの動画データのうちの第２の動画データの時間区間を前記第２の区間として指定し、
前記生成手段は、前記第１の動画データのうちの前記第１の区間における接合面よりも前の動画データと、前記第２の動画データのうちの前記第２の区間における接合面よりも後の動画データと、が順に繋ぎ合わされた動画データを生成する、
ことを特徴とする請求項１に記載の動画生成装置。
【請求項５】
前記決定手段は、前記第１の動画データの先頭から前記第１の区間における接合面までの時間長と、前記第２の動画データの末尾から前記第２の区間における接合面までの時間長と、の和が前記生成される動画データの先頭から末尾までの時間長のあらかじめ設定された最小値以上となるように、前記接合面を決定する、
ことを特徴とする請求項４に記載の動画生成装置。
【請求項６】
前記決定手段は、前記静止画群が占める空間において隣接する２つの画素の間を通る前記接合面の候補のうち、該接合面の候補を挟んで隣接する２つの画素に対応付けられた隣接項の値の、該接合面の候補を挟んで隣接する２つの画素の組合せのそれぞれについての加算値が最小となる接合面の候補を、前記接合面として決定する、
ことを特徴とする請求項１乃至５のいずれか１項に記載の動画生成装置。
【請求項７】
前記隣接項の値は、前記接合面の候補を挟んで隣接する２つの画素のうち、
一方の画素の画素値と、前記第１の区間と前記第２の区間のうち該一方の画素が属する区間と異なる区間において該接合面の候補の位置を基準に該一方の画素と同じ位置にある画素の画素値と、の差と、
他方の画素の画素値と、前記第１の区間と前記第２の区間のうち該他方の画素が属する区間と異なる区間において該接合面の候補の位置を基準に該他方の画素と同じ位置にある画素の画素値と、の差と、
の和として定められる、
ことを特徴とする請求項６に記載の動画生成装置。
【請求項８】
前記繰返し手段は、前記決定された接合面の前記加算値が小さいほど前記減少手段における画素数の減少率を下げる程度を大きくする、
ことを特徴とする請求項６又は７に記載の動画生成装置。
【請求項９】
前記繰返し手段は、前記指定手段が指定する前記第１の区間及び前記第２の区間のそれぞれを該それぞれの区間において決定された前記接合面が占める時間長の前後に該それぞれの区間における画素１つの時間長を加算した時間長の区間に狭めて、前記減少手段、前記指定手段、及び、前記決定手段の処理を、繰り返し実行する、
ことを特徴とする請求項１乃至８のいずれか１項に記載の動画生成装置。
【請求項１０】
前記決定手段は、前記減少手段における画素数の減少率が所定の閾値以下となるまでは、前記静止画群が占める空間における前記時間方向に隣接する２つの画素の間を通って該空間を該時間方向に垂直に分割する面を前記接合面として決定する、
ことを特徴とする請求項１乃至９のいずれか１項に記載の動画生成装置。
【請求項１１】
前記繰返し手段は、前記減少率を０に下げた場合における前記減少手段、前記指定手段、及び、前記決定手段の処理が実行されるまで繰り返す、
ことを特徴とする請求項１乃至１０のいずれか１項に記載の動画生成装置。
【請求項１２】
動画データの画素数を減少させる減少ステップと、
前記減少ステップによって画素数が減少した動画データの時間区間である第１の区間と第２の区間とを指定する指定ステップと、
前記第１の区間の動画データ及び前記第２の区間の動画データを構成する複数の静止画データの２次元座標が揃うように該複数の静止画データが時系列順に並べられた静止画群が占める空間における、前記２次元座標の横方向に隣接する２つの画素の間、前記２次元座標の縦方向に隣接する２つの画素の間、及び、前記静止画群の時間方向に隣接する２つの画素の間、を通って該空間を分割する面であって、前記第１の区間における該面よりも前の動画データと前記第２の区間における該面よりも後の動画データとを接合するための接合面を決定する決定ステップと、
前記減少ステップにおける画素数の減少率を下げ、且つ、前記指定ステップで指定する前記第１の区間及び前記第２の区間のそれぞれを該それぞれの区間において決定された前記接合面を含むような区間に狭めて、前記減少ステップ、前記指定ステップ、及び、前記決定ステップの処理を、繰り返し実行する繰返しステップと、
前記第１の区間における接合面よりも前の動画データと、前記第２の区間における接合面よりも後の動画データと、が順に繋ぎ合わされた動画データを生成する生成ステップと、
を含むことを特徴とする動画生成方法。
【請求項１３】
コンピュータに、
動画データの画素数を減少させる減少機能、
前記減少機能によって画素数が減少した動画データの時間区間である第１の区間と第２の区間とを指定する指定機能、
前記第１の区間の動画データ及び前記第２の区間の動画データを構成する複数の静止画データの２次元座標が揃うように該複数の静止画データが時系列順に並べられた静止画群が占める空間における、前記２次元座標の横方向に隣接する２つの画素の間、前記２次元座標の縦方向に隣接する２つの画素の間、及び、前記静止画群の時間方向に隣接する２つの画素の間、を通って該空間を分割する面であって、前記第１の区間における該面よりも前の動画データと前記第２の区間における該面よりも後の動画データとを接合するための接合面を決定する決定機能、
前記減少機能における画素数の減少率を下げ、且つ、前記指定機能で指定する前記第１の区間及び前記第２の区間のそれぞれを該それぞれの区間において決定された前記接合面を含むような区間に狭めて、前記減少機能、前記指定機能、及び、前記決定機能の処理を、繰り返し実行する繰返し機能、
前記第１の区間における接合面よりも前の動画データと、前記第２の区間における接合面よりも後の動画データと、が順に繋ぎ合わされた動画データを生成する生成機能、
を実現させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画生成装置、動画生成方法、及び、プログラムに関する。
【背景技術】
【０００２】
２つの動画を接続して１つの動画を生成する、あるいは、１つの動画の先頭と末尾を接続してループする動画を生成する技術がある。このような接合された動画を生成する技術において、異なる区間の動画データを滑らかに繋げ、その接合部分をなるべく目立たせないようにするための手法が開発されている。
【０００３】
例えば、非特許文献１は、３次元のグラフカットの手法を利用して、２つの動画データを接合可能な接合面のうち接合部分が最も滑らかになるような接合面を決定し、決定された接合面を境界として２つの動画データを接合する技術を開示している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｇｒａｐｈｃｕｔ  Ｔｅｘｔｕｒｅｓ：  Ｉｍａｇｅ  ａｎｄ  Ｖｉｄｅｏ  Ｓｙｎｔｈｅｓｉｓ  Ｕｓｉｎｇ  Ｇｒａｐｈ  Ｃｕｔｓ，  Ｖ．Ｋｗａｔｒａ，  Ａ．Ｓｃｈｏｄｌ，  Ｉ．Ｅｓｓａ，  Ｇ．Ｔｕｒｋ，  Ａ．Ｂｏｂｉｃｋ，  ＳＩＧＧＲＡＰＨ２００３
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記のグラフカットの手法を利用して接合面を求める処理は、画素数やフレーム数が多くなればなるほど計算量が多くなる。とくに入力動画データの広い範囲を探査して最適な接合面を見つけるためには多くの計算量が必要となる。そのため、計算量を抑制しつつ入力動画データのなるべく広い範囲から最適な接合面を見つけて、動画データを滑らかに接合したいという要望があった。
【０００６】
本発明は、以上のような課題を解決するためのものであり、計算量を抑制しつつ、動画データを滑らかに接合して新たな動画データを生成するのに好適な動画生成装置、動画生成方法、及び、プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明にかかる動画生成装置は、
動画データの画素数を減少させる減少手段と、
前記減少手段によって画素数が減少した動画データの時間区間である第１の区間と第２の区間とを指定する指定手段と、
前記第１の区間の動画データ及び前記第２の区間の動画データを構成する複数の静止画データの２次元座標が揃うように該複数の静止画データが時系列順に並べられた静止画群が占める空間における、前記２次元座標の横方向に隣接する２つの画素の間、前記２次元座標の縦方向に隣接する２つの画素の間、及び、前記静止画群の時間方向に隣接する２つの画素の間、を通って該空間を分割する面であって、前記第１の区間における該面よりも前の動画データと前記第２の区間における該面よりも後の動画データとを接合するための接合面を決定する決定手段と、
前記減少手段における画素数の減少率を下げ、且つ、前記指定手段が指定する前記第１の区間及び前記第２の区間のそれぞれを該それぞれの区間において決定された前記接合面を含むような区間に狭めて、前記減少手段、前記指定手段、及び、前記決定手段の処理を、繰り返し実行する繰返し手段と、
前記第１の区間における接合面よりも前の動画データと、前記第２の区間における接合面よりも後の動画データと、が順に繋ぎ合わされた動画データを生成する生成手段と、
を備える。
【発明の効果】
【０００８】
本発明によれば、計算量を抑制しつつ、動画データを滑らかに接合して新たな動画データを生成することができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施形態に係る動画生成装置の物理構成の一例を示す図である。
【図２】本発明の実施形態に係る動画生成装置の機能構成の一例を示す図である。
【図３】実施形態１に係る動画生成処理の概要を示す図である。
【図４】実施形態１に係る接合面の決定処理の概要を示す図である。
【図５】実施形態１に係る動画生成装置の処理の流れを示すフローチャートである。
【図６】実施形態１に係る接合面の決定処理の流れを示すフローチャートである。
【図７】実施形態１に係る周縁フレームを説明するための図である。
【図８】実施形態１に係る隣接項を説明するための図である。
【図９】実施形態１に係る接合面を説明するための図である。
【図１０】実施形態１に係る接合面のコストを説明するための図である。
【図１１】実施形態１において、探査区間の時間長を設定する様子を説明するための図である。
【図１２】実施形態２に係る動画生成処理の概要を示す図である。
【図１３】実施形態２に係る動画生成装置の処理の流れを示すフローチャートである。
【図１４】実施形態２に係る接合面を説明するための図である。
【発明を実施するための形態】
【００１０】
以下、本発明の実施形態について、図面を参照して説明する。なお、図中同一又は相当する部分には同一符号を付す。
【００１１】
以下に説明する実施形態は説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であれば下記の各構成要素を均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本発明の範囲に含まれる。また、以下の説明では、本発明の理解を容易にするため、重要でない公知の技術的事項の説明を適宜省略する。
【００１２】
（実施形態１）
実施形態１に係る動画生成装置は、物理的には図１に示すように構成される。動画生成装置１は、制御部１０と、記憶部１１と、操作部１２と、表示部１３と、Ｉ／Ｆ部１４と、通信部１５と、を備える。これら各部は、命令やデータを転送するための伝送経路であるシステムバスを介して相互に接続される。
【００１３】
制御部１０は、例えばＣＰＵ（Central Processing Unit）１０ａ、ＲＯＭ（Read Only Memory）１０ｂ、ＲＡＭ（Random Access Memory）１０ｃ、画像処理部１０ｄ等によって構成される。
【００１４】
制御部１０では、ＣＰＵ１０ａが、ＲＡＭ１０ｃをワークメモリとして用いてＲＯＭ１０ｂや記憶部１１等に記憶されている各種プログラムを適宜実行することにより、動画生成装置１の各部の動作を制御する。また、制御部１０では、画像処理部１０ｄが、供給された画像（静止画及び動画）データを画像演算プロセッサによって加工処理し、フレームメモリに記録する。画像処理部１０ｄは、画像データを重ね合わせ演算やアルファブレンディング等の透過演算、各種の飽和演算を実行できる。
【００１５】
記憶部１１は、例えばハードディスクやフラッシュメモリのような不揮発性メモリ等によって構成される。記憶部１１は、入力動画データや出力動画データ、また動画生成処理に必要となる各種情報を記憶する。
【００１６】
操作部１２は、操作者によって操作され、各種の指示入力を受け付ける。操作部１２は、例えばキーボードや各種の入力ボタン、マウス等によって構成される。あるいは、操作部１２は、タッチセンサのような接触を検知する入力装置から構成されてもよい。操作者は、操作部１２を操作して、動画生成の指示や、出力動画データの時間長の設定指示等を入力できる。
【００１７】
表示部１３は、画像を表示する。表示部１３は、例えばＣＲＴ（Cathode Ray Tube）やＬＣＤ（Liquid Crystal Display）等のような表示装置（モニタ）と、表示コントローラとによって構成される。表示コントローラは、画像処理部１０ｄによって加工され、フレームメモリに記録された画像データを所定の同期タイミングで表示信号に変換して表示装置に出力する。例えば、表示部１３は、出力された動画を表示したり、動画生成における各処理の結果を表示したりする。
【００１８】
なお、操作部１２と表示部１３は、タッチパネル（タッチスクリーン）等によって構成されてもよい。この場合、タッチパネルに内蔵された入力装置と表示装置が、それぞれ操作部１２と表示部１３とを構成する。
【００１９】
Ｉ／Ｆ部１４は、外部とのインターフェース（Ｉ／Ｆ）である。Ｉ／Ｆ部１４は、例えば、メディアコントローラ等を備える読取書込装置によって構成される。制御部１０は、Ｉ／Ｆ部１４を介して、例えばフラッシュメモリを備えるメモリカードのような各種の記憶媒体に対してデータを読み書きする。
【００２０】
通信部１５は、例えばモデム等の適宜の通信装置によって構成される。通信部１５は、有線又は無線で、ネットワーク１６に接続される。通信部１５は、制御部１０による制御のもと、例えばネットワーク１６上にある入力動画データを受信したり、ネットワーク１６を介して出力動画データを他の通信装置に送信したりすることができる。
【００２１】
また、動画生成装置１は、さらに音声処理部を備えてもよい。例えば、音声処理部は、制御部１０の制御のもと、供給された音声データをアナログ信号に変換し、表示部１３に表示される動画データの再生にあわせて変換された信号をスピーカから出力させる。
【００２２】
動画生成装置１は、機能的には図２に示すように構成される。動画生成装置１は、減少手段２０と、指定手段２１と、決定手段２２と、繰返し手段２３と、生成手段２４と、を備える。これら各手段は、制御部１０におけるＣＰＵ１０ａ、ＲＯＭ１０ｂ、ＲＡＭ１０ｃ、画像処理部１０ｄ等が協働することによって実現される。
【００２３】
減少手段２０は、１つ又は２つの入力動画データの画素数を、例えば画素を間引く又はビニングすることによって減少させる。減少手段２０は、画素数が減少した動画データの情報を、指定手段２１に供給する。
【００２４】
指定手段２１は、減少手段２０から供給された画素数が減少した動画データの時間区間である２つの探査区間であって、接合面を探査するための区間を指定する。指定手段２１は、指定した２つの探査区間の情報を、決定手段２２に供給する。
【００２５】
決定手段２２は、指定手段２１から供給された２つの探査区間の動画データを滑らかに接合するための接合面を、探査区間のそれぞれを分割する面のうちから、３次元グラフカットの手法を用いて決定する。決定手段２２は、決定した接合面の情報を、繰返し手段２３に供給する。
【００２６】
繰返し手段２３は、減少手段２０における画素数の減少率を下げ、且つ、決定手段２２から供給された接合面を含むような時間長の区間に指定手段２１が指定する２つの探査区間を狭めて、減少手段２０、指定手段２１、及び、決定手段２２の処理を繰り返す。そのために、繰返し手段２３は、減少率を下げ、そして探査区間を狭めた条件のもとでの繰返し処理の命令を減少手段２０に送る。繰返し手段２３は、減少手段２０における画素数の減少率が０にまで下げられた条件のもとで接合面が決定されるまで、減少手段２０、指定手段２１、及び、決定手段２２の処理を繰り返す。繰返し手段２３は、決定手段２２によって最終的に決定された接合面の情報を、生成手段２４に供給する。
【００２７】
生成手段２４は、繰返し手段２３から供給された最終的に決定された接合面で、入力動画データの２つの区間の動画データを繋ぎ合わせて、出力動画データを生成する。
【００２８】
以下、実施形態１では、動画生成装置１が実行する処理のうち、１つの動画データのうちの２つの区間の動画データを繋ぎ合わせてループする動画データを生成する処理について説明する。
【００２９】
実施形態１に係る動画生成装置１は、図３に示すような動画生成処理を実行する。動画生成装置１は、１つの入力動画データ３０ａのうちの前方の区間の動画データと後方の区間の動画データを接合して、ループする新たな動画データ３０ｂを生成する。入力動画データ３０ａが静止画データ３１ｐ〜３１ｒを含む複数の静止画データによって構成される場合、新たな動画データ３０ｂは、静止画データ３１ｐ〜３１ｒ等が繰り返される動画データとなる。
【００３０】
動画生成装置１は、入力動画データ３０ａのうちの前方の区間の動画データと後方の区間の動画データを接合する。そのために、動画生成装置１は、入力動画データ３０ａにおける前方と後方に位置する同じ形状の面であって、接合面周辺の動画データが滑らかに繋がるような接合面４１ａを決定する。そして、動画生成装置１は、この接合面４１ａを境界として、後方の接合面４１ａよりも前の動画データの後に前方の接合面４１ａよりも後の動画データが繋がるように、接合処理を行う。例えば、入力動画データ３０ａ内の前方の接合面４１ａと後方の接合面４１ａとが時間長“Ｄ”だけ離れている場合、新たな動画データ３０ｂは、入力動画データ３０ａを構成していた静止画データ３１ｐ〜３１ｒ等が、周期“Ｄ”の時間長で繰り返される動画データとなる。
【００３１】
前方に位置する接合面４１ａは、この面で入力動画データ３０ａを分割したときの前端となるため、以下では、前端面という。同様に、後方に位置する接合面４１ａは、この面で入力動画データ３０ａを分割したときの後端となるため、以下では、後端面という。
【００３２】
図３における動画データ３０ａ，３０ｂは、動画データを構成する複数の静止画データ３１ｐ，３１ｑ，３１ｒ等が、静止画における縦横の２次元座標が複数の静止画データ間で一致するように、すなわちモニタの同じ位置に表示されるべき画素が時間方向に重なるように、時系列順に並べられて示されている。このような時系列順に並べられた静止画群が占める空間を、以下では、動画空間という。動画空間内の任意の位置は、静止画の縦方向の座標（縦座標）と横方向の座標（横座標）、そして動画の時間方向の座標（時間座標）という３つの座標によって定義できる。
【００３３】
なお、一般的に、動画データにおける静止画データは、直前のフレームの静止画データとの差分のデータとして記憶される場合がある。しかし、そのような場合においても、動画空間を構成する静止画データは、各フレームにおいてモニタに表示されるべき静止画全体のデータを表すものとして、以下、説明する。
【００３４】
次に、図４を参照して、異なる区間の動画データを接合するための接合面を決定する処理の概要について説明する。
【００３５】
理解を容易にするために、図４は、入力動画データ３０ａ等の動画データの動画空間を真横から見たときの様子、すなわち動画空間を縦方向及び時間方向の２次元の形式で表したときの様子を示す。動画生成装置１が実行する接合面の決定処理は、初期階層、中間階層、最終階層の３つの階層に分けることができる。
【００３６】
初期階層では、入力動画データ３０ａの画素を間引く又はビニングすることによって、動画空間における横方向・縦方向・時間方向のそれぞれの方向において画素数が所定の割合で減少した動画データ３０ｃが生成される。そして、画素数が減少した動画データ３０ｃの前方と後方の動画データを繋げて新たな動画データを生成するための接合面であって、前端面４２ａとなる接合面と後端面４３ａとなる接合面とが決定される。このとき、接合面周辺の動画データを滑らかに接合するために最適な前端面４２ａと後端面４３ａとは、画素数が減少した動画データ３０ｃ全体の探査区間（図４における斜線部）のうちから探査される。
【００３７】
中間階層では、初期階層よりも減少率が下げられ、初期階層よりも多くの画素を有する動画データ３０ｄが、入力動画データ３０ａから生成される。そして、生成された動画データ３０ｄにおいて、同様に、接合面周辺の動画データを滑らかに接合するために最適な前端面４２ｂと後端面４３ｂとが決定される。このとき、前端面４２ｂの探査区間として、初期階層において決定された前端面４２ａを含む区間であって、初期階層における探査区間よりも短い区間が指定される。同様に、後端面４３ｂの探査区間として、初期階層において決定された後端面４３ａを含む区間であって、初期階層における探査区間よりも短い区間が指定される。具体的には、中間階層における接合面の探査区間は、図４における中間階層の図において斜線で示されるような区間になる。
【００３８】
中間階層では、さらに直前の階層よりも低下した減少率と短縮された探査区間のもとで、接合面周辺の動画データを滑らかに接合するための最適な前端面と後端面とを決定する処理が繰り返される。例えば、動画データ３０ｄよりも多くの画素を有する動画データ３０ｅでは、前端面４２ｂと後端面４３ｂとが決定された探査区間よりも狭い区間において、前端面４２ｃと後端面４３ｃとが決定される。このように中間階層では、動画生成装置１は、画素数の減少率を１から０までの範囲で徐々に下げていき、減少率が下がれば下がるほど接合面の探査区間を狭めて、接合面周辺の動画データが最も滑らかに接合されるような前端面と後端面を決定する。
【００３９】
最終階層では、減少率が０に設定され、画素数が減少されない動画データ、すなわち元の入力動画データ３０ａにおけるさらに狭められた探査区間において、同様に、接合面周辺の動画データを滑らかに接合するための最適な前端面４２ｄと後端面４３ｄとが決定される。最終階層において決定された前端面４２ｄと後端面４３ｄが、最終的に入力動画データ３０ａから新たな動画データ３０ｂを生成するための接合面となる。
【００４０】
このように、動画生成装置１は、探査区間が広い階層では、横方向・縦方向・時間方向のそれぞれの方向において画素数が削減された動画データのもとで最適な接合面を決定し、画素数を入力動画データ３０ａの元の画素数に徐々に近づけながら探査区間を決定された接合面周辺の区間に狭めていく。一般的な動画データにおける各画素の画素値は、隣接する複数の画素を通じて徐々に変化することが多く、画素１つ毎に大きく変化することは少ないため、接合面を粗い動画データから段階的に探査しても元の入力動画データにおける最適な接合面の位置と大きく異なってしまうことは少ないと考えられる。そのため、新たな動画データにおける接合面周辺の動画データが最も滑らかに接合される２つの接合面を、効率的に探査することができる。
【００４１】
以上のような実施形態１に係る動画生成装置１が実行する処理の流れについて、以下、図５に示すフローチャートを参照して説明する。
【００４２】
動画生成装置１において、まず制御部１０が、動画生成の指示があったか否かを判別する（ステップＳ１０１）。制御部１０は、例えば操作部１２を介して操作者からの動画生成の指示があったか否かを判別する。
【００４３】
動画生成の指示がないと（ステップＳ１０１；ＮＯ）、処理はステップＳ１０１に留まる。すなわち、制御部１０は、動画生成の指示があると判別されるまで、引き続き動画生成の指示があったか否かを判別する。
【００４４】
一方、動画生成の指示があったと判別されると（ステップＳ１０１；ＹＥＳ）、制御部１０は、動画生成に用いる１つの入力動画データを取得する（ステップＳ１０２）。制御部１０は、例えば記憶部１１に記憶された動画データを読み出したり、Ｉ／Ｆ部１４を介して各種の記憶媒体に記憶された動画データを読み出したり、通信部１５を介してネットワーク１６上にある動画データを受信したりすることによって入力動画データを取得する。
【００４５】
入力動画データを取得すると、制御部１０は、出力動画データの最小周期を設定する（ステップＳ１０３）。すなわち、接合面となる前端面と後端面との間の時間長“Ｄ”が出力動画データの周期“Ｄ”となるため、前端面と後端面とが入力動画データ内のどの位置になるかによって出力動画データの周期が変わる。そのため、制御部１０は、出力動画データの周期が極端に短くならないように、最低限の周期を設定する。
【００４６】
設定される最小周期は、予めＲＯＭ１０ｂや記憶部１１に記憶されていてもよい。あるいは、操作者が、操作部１２を介して生成したい新たな動画データの最低限の周期を入力し、最小周期として設定できるようにしてもよい。
【００４７】
出力動画データの最小周期を設定すると、動画生成装置１の処理は、画素数の減少率と接合面の探査区間を段階的に変化させて最適な接合面を決定する処理に移行する。
【００４８】
まず初期階層では、制御部１０は、入力動画データの画素数を予め設定された減少率で減少させ（ステップＳ１０４）、画素数が減少した動画データを生成する。例えば、入力動画データを構成する複数の静止画データが横方向にＭ個及び縦方向にＮ個の合計Ｍ×Ｎ個の画素を有し、かつ、入力動画データのフレーム数がＴ個、すなわち入力動画データがＴ個の静止画データを有する場合、入力動画データの画素数は合わせてＭ×Ｎ×Ｔ個となる。制御部１０は、このような入力動画データの画素数を、動画空間における横方向、縦方向、時間方向のそれぞれの方向において１／ｐに減少させ、（Ｍ／ｐ）×（Ｎ／ｐ）×（Ｔ／ｐ）個の画素を有する動画データを生成する。
【００４９】
画素数を減少させる方法として、制御部１０は、画素を間引いてもよいし、ビニングしてもよいし、他の方法を用いてもよい。画素を間引く場合、制御部１０は、動画空間における横方向、縦方向、時間方向のそれぞれの方向において隣接するｐ個の画素ごとに、そのうちの１個の画素を残すように他の（ｐ−１）個の画素を間引くことによって、画素数が減少した動画データを生成する。一方、ビニングする場合、制御部１０は、動画空間における横方向、縦方向、時間方向のそれぞれの方向において隣接するｐ個の画素ごとに、これらの画素値の合計値又は平均値を画素値とする１個の画素にまとめることによって、画素数が減少した動画データを生成する。
【００５０】
なお、動画空間における横方向、縦方向、時間方向のそれぞれの方向において同じ割合で画素数を減少させることに限らず、制御部１０は、それぞれの方向において異なる割合で画素数を減少してもよい。例えば、制御部１０は、Ｍ×Ｎ×Ｔ個の画素を有する入力動画データの画素数を、横方向に１／ｍ、縦方向に１／ｎ、時間方向に１／ｔの割合で減少し、（Ｍ／ｍ）×（Ｎ／ｎ）×（Ｔ／ｔ）個の画素を有する動画データを生成するようにしてもよい。
【００５１】
画素数が減少した動画データを生成すると、制御部１０は、接合面の探査区間を、画素数が減少した動画データ全体を接合面の探査区間に指定する（ステップＳ１０５）。すなわち、図４に示したように、初期階層では、画素数が削減された動画データ３０ｃの区間全体が動画データを接合するための最適な接合面となるべき前端面４２ａと後端面４３ａとを探査するための探査区間として指定される。
【００５２】
接合面の探査区間を指定すると、制御部１０は、グラフカットの手法を用いて、探索区間内の動画データを接合するための接合面を決定する（ステップＳ１０６）。接合面の決定処理の詳細は、後述するように、図６のフローチャートに示される。
【００５３】
接合面を決定すると、制御部１０は、画素数を減少させた際の減少率が０であるか否かを判別する（ステップＳ１０７）。初期階層では、減少率は複数の階層の中で最大の値であって０ではないため、ステップＳ１０７ではＮＯと判別される。そして、動画生成装置１の処理は、中間階層の処理へと移行する。
【００５４】
中間階層では、制御部１０は、画素数を減少させる際の減少率を下げ（ステップＳ１０８）、初期階層で用いられた減少率よりも低い減少率に変更する。そして、変更した減少率で入力動画データの画素数を横方向・縦方向・時間方向それぞれの方向において減少させた動画データを生成する。このときの減少率を下げる程度の情報は、予めＲＯＭ１０ｂや記憶部１１に記憶されていてもよいし、操作部１２を介して操作者によって設定できるようにしてもよい。
【００５５】
初期階層よりも多くの画素を有する動画データを生成すると、制御部１０は、探査区間を狭める（ステップＳ１０９）。図４の例を参照して説明すると、制御部１０は、中間階層における動画データ３０ｄにおける前端面４２ｂを探査するための探査区間を、初期階層において決定された前端面４２ａを含むような動画データの一部の区間に狭めて指定し直す。同様に、制御部１０は、後端面４３ｂを探査するための探査区間を、初期階層において決定された後端面４３ａを含むような動画データの一部の区間に狭めて指定し直す。
【００５６】
そして、動画生成装置１の処理はステップＳ１０６に戻り、制御部１０は、グラフカットの手法を用いて、幅が狭められて指定された探索区間内の動画データを接合するための接合面を決定する（ステップＳ１０６）。そして、再び制御部１０は、変更された減少率が０であるか否かを判別する（ステップＳ１０７）。
【００５７】
このように、ステップＳ１０７においてＹＥＳと判別されるまで、すなわち減少率が０に設定されるまで、ステップＳ１０６〜Ｓ１０９の処理が繰り返される。すなわち、制御部１０は、最終階層において画素の間引き又はビニングがされない元の入力動画データでの最適な接合面が決定されるまで、探査区間を徐々に狭め、画素数を徐々に増やしながら最適な接合面を繰り返し探査する。
【００５８】
最終階層の処理まで実行され、画素数の減少率が０であると判別されると（ステップＳ１０７；ＹＥＳ）、制御部１０は、最終的に決定された接合面で入力動画データをループさせた出力動画データを生成する（ステップＳ１１０）。そして、動画生成処理は終了する。
【００５９】
図３の例を用いて具体的に説明すると、制御部１０は、入力動画データ３０ａのうちの後端面である接合面４１ａよりも前であって前端面である接合面４１ａよりも後の動画データが繰り返し繋ぎ合わされた新たな動画データ３０ｂを生成する。生成された動画データ３０ｂは、例えば記憶部１１に保存され、制御部１０の制御のもと表示部１３を介して再生表示されたり、Ｉ／Ｆ部１４や通信部１５を介して外部に提供されたりする。
【００６０】
以下、接合面の決定処理（図５のフローチャートにおけるステップＳ１０６の処理）の詳細について、図６のフローチャートを参照して説明する。
【００６１】
接合面の決定処理が開始されると、制御部１０は、指定された２つの探査区間における周縁フレーム及び隣接項を設定する（ステップＳ２０１）。
【００６２】
周縁フレームとは、探査区間の動画データを時間方向において前後に分割するような接合面を決定するために設定されるフレームである。周縁フレームの概要を、図７を参照して説明する。図７は、ある階層において、画素の間引き又はビニングがされた動画データ３０ｆを真横から見た様子を示す。縦方向及び時間方向の２次元状に拡がって描かれた格子のそれぞれは、動画空間の横方向、縦方向、及び、時間方向において画素の間引き又はビニングがされた後の動画データにおける１つの画素を表す。
【００６３】
制御部１０は、その階層において指定された探査区間の最初のフレームと最後のフレームを、それぞれ周縁フレームに設定する。図７の例では、後端面を探査すべき第１の探査区間５１ａ及び前端面を探査すべき第２の探査区間５１ｂにおける最初のフレームと最後のフレーム（図７において斜線が付されたフレーム）が、それぞれ周縁フレーム５２ａ〜５２ｄに設定される。接合面が周縁フレームの画素を横切るように定められると接合面が指定された探査区間内に収まらなくなるため、制御部１０は、接合面が周縁フレーム５２ａ〜５２ｄを横切らないという条件のもと、接合面を決定する。
【００６４】
なお、初期階層では、後端面を探査すべき第１の探査区間と前端面を探査すべき第２の探査区間としてともに動画データの区間全体が指定されるため、周縁フレームは、動画データの最初のフレームと最後のフレームの２つとなる。
【００６５】
一方、隣接項とは、探査区間における画素のそれぞれに対応付けられた項であって、探査区間の動画データを接合する際に滑らかに接合するための指標となるものである。以下、隣接項について、図８を参照して説明する。
【００６６】
図８の上段の図は、第１の探査区間の動画データ及び第２の探査区間の動画データの画素であって、横方向と縦方向において同じ位置にある９つの画素を拡大した様子を示す。斜線で表された中心の画素とその周囲の画素に付された値は、画素の色の輝度を表す値である。理解を容易にするために、本実施形態では、各画素は１つの値を有する、すなわち各動画データはグレースケールの動画であるとして説明する。
【００６７】
制御部１０は、第１の探査区間の動画データの画素と第２の探査区間の動画データの画素であって、動画空間において横座標と縦座標とが同じ位置にある２つの画素の画素値の差分を計算する。そして、制御部１０は、２つの動画データの各画素について計算した差分の絶対値によって表される差分データを生成する。具体的に、図８の上段に示された画素の画素値の差分の絶対値がとられた差分データは、図８の中段に示される差分データのようになる。例えば、２つの動画データにおける斜線で表された中心の画素から生成される差分データの値は、画素値“５”と画素値“７”の差分の絶対値である“２”の値となる。
【００６８】
差分データを生成すると、制御部１０は、差分データにおいて隣接する２つの値の和を計算することによって隣接項を求める。そして、制御部１０は、探査区間の動画データの画素と画素との間に対応させて、求めた隣接項を設定する。例えば、図８の中段に示された差分データのうちの中央の値に対して縦方向及び時間方向に隣接する値との間では、図８の下段に示されるような４つの隣接項５３ａ〜５３ｄが設定される。具体的に説明すると、隣接項５３ａの値は“２”と“０”との和である“２”と設定され、隣接項５３ｂの値は“２”と“１”との和である“３”と設定され、隣接項５３ｃの値は“２”と“３”との和である“５”と設定され、隣接項５３ｄの値は“２”と“５”との和である“７”と設定される。
【００６９】
なお、動画空間における横方向も考慮すると、さらに２つの隣接項が設定できる。すなわち、１つの画素には最大で６つの隣接項が対応付けられる。制御部１０は、このような隣接項の設定を、第１の探査区間における画素と、この画素と横座標と縦座標が同じであって、ステップＳ１０３において設定された最小周期の値以上時間長が離れた第２の探査区間における画素との組合せのそれぞれについて行い、設定された隣接項を探査区間の隣接する２つの画素のそれぞれの画素間に対応付けて、ＲＡＭ１０ｃに記憶する。
【００７０】
より一般的に説明すると、２つの探査区間のうちの一方の探査区間における隣接する２つの画素の値がそれぞれ“Ａ”と“Ｂ”であって、他方の探査区間においてこの２つの画素と横方向と縦方向において同じ位置にある隣接する２つの画素の値が“Ｃ”と“Ｄ”であるときの隣接項の値は、これらの画素の値の差分の絶対値を加算した値、すなわち“｜Ａ−Ｃ｜＋｜Ｂ−Ｄ｜”と表される。ＡとＣが等しく、且つ、ＢとＤも等しい場合、すなわち、２つの探査区間で横座標と縦座標とが同じ画素の値が隣接する２つの画素のいずれについても等しい場合、隣接項の値は最小値である０となる。一方、２つの探査区間で横座標と縦座標とが同じ画素の値の差が大きくなればなるほど、隣接項の値は大きくなる。
【００７１】
図６のフローチャートに戻って、探査区間の周縁フレーム及び隣接項を設定すると、制御部１０は、第２の探査区間において、前端面の候補を１つ選択し（ステップＳ２０２）、第１の探査区間において、後端面の候補を１つ選択する（ステップＳ２０３）。そして、制御部１０は、候補として選択された前端面と後端面とで探査区間内の動画データを接合したときのコストを計算する（ステップＳ２０４）。
【００７２】
図９は、図７と同様に、第１の探査区間５１ａの動画データと第２の探査区間５１ｂの動画データ３０ｆの動画空間を真横から見た様子を示す。制御部１０は、第１の探査区間５１ａの動画データと第２の探査区間５１ｂの動画データとを接合して１つの新たな動画データを生成するための接合面であって、第１の探査区間５１ａと第２の探査区間５１ｂとで、同じ形状の前端面と後端面の候補を１組選択する。
【００７３】
制御部１０は、例えば前端面の候補４４ａと後端面の候補４５ａのように、探査区間内の動画空間を画素単位で、すなわち、画素数が削減された動画データ３０ｆにおける１つのフレームの静止画データ内において横方向・縦方向に隣接する２つの画素の間、及び、時間方向に連続する２つのフレームの間、のいずれも通ることが可能な折れ曲がった面を選択する。また、制御部１０は、探査区間における動画空間を時間方向に前後に分割するため、前端面が周縁フレーム５２ａ，５２ｂを横切らないという条件、及び、後端面が周縁フレーム５２ｃ，５２ｄを横切らないという条件にも基づいて、前端面と後端面の候補を選択する。
【００７４】
このとき、制御部１０は、ステップＳ１０３において設定した出力動画データの最小周期の値も制約として加えて、前端面の候補４４ａと後端面の候補４５ａとを選ぶ。出力動画データの繰り返し周期の時間長は、動画データ３０ｆにおける前端面の候補４４ａと後端面の候補４５ａとの間の時間長“Ｄ”となる。そのため、制御部１０は、この時間長“Ｄ”があらかじめ設定された出力動画データの繰り返し周期の最小値以上になるように、前端面の候補４４ａと後端面の候補４５ａとを選ぶ。
【００７５】
制御部１０は、候補として選択した前端面と後端面とで探査区間内の動画データを接合したときのコストを計算する。接合面のコストは、その接合面を用いたときの接合面周辺の動画データの滑らかさの指標であって、予め定義される。具体的には、接合面のコストは、第１の探査区間５１ａと第２の探査区間５１ｂとの動画データを接合した場合に、接合面を挟んで隣接する２つの画素の間に設定された隣接項の値を、接合面を挟んで横方向・縦方向・時間方向に隣接する２つの画素の組合せのそれぞれについて加算した値として定義される。
【００７６】
図１０は、前端面の候補４４ａと後端面の候補４５ａとを接合面４１ｂとして第１の探査区間５１ａと第２の探査区間５１ｂとの動画データとを接合した様子を示す。斜線を破線で付した画素は、接合面４１ｂを挟んで隣接する２つの画素のうちの、第１の探査区間５１ａの動画データを構成していた画素である。これらの画素は、矢印を付した方向において、接合面４１ｂと接する。
【００７７】
制御部１０は、これらの画素と、接合面４１ｂを挟んで隣接する第２の探査区間５１ｂの動画データの画素と、の間に設定された隣接項を選択する。隣接項は、接合面４１ｂを挟んで隣接する２つの画素の組合せの数（図１０の例では矢印の数）だけ選択される。そして、制御部１０は、選択した隣接項の値の和を計算し、計算した値をこの接合面４１ｂのコストとしてＲＡＭ１０ｃに記憶する。
【００７８】
再び図６のフローチャートに戻って、候補として選択された前端面と後端面を接合面とした場合のコストを計算すると、制御部１０は、後端面の候補の探査を完了したか否かを判別する（ステップＳ２０５）。すなわち、制御部１０は、第１の探査区間５１ａにおいて選択可能な後端面の候補のそれぞれを選択して、それを前端面と組み合わせた場合の接合面のコストを計算し終えたか否かを判別する。
【００７９】
後端面の探査を完了していないと（ステップＳ２０５；ＮＯ）、制御部１０は、第１の探査区間５１ａ内の後端面の別の候補を１つ選択する（ステップＳ２０６）。すなわち、制御部１０は、第１の探査区間５１ａにおける動画空間内を画素単位で分割する面であって、選択された前端面と同じ形状の面のうちすでにコストを計算した後端面の候補とは異なる面を選択する。このとき、制御部１０は、前端面の候補との間の時間長が設定された最小周期の時間長以上となるように、後端面の別の候補を選択する。
【００８０】
後端面の別の候補を選択すると、接合面の決定処理はステップＳ２０４に戻り、制御部１０は、新たに候補として選択した後端面と既に選択した前端面とで接合したときのコストを計算する。このように、制御部１０は、選択された前端面と組み合せ可能な後端面の候補のそれぞれを選択して、それらを用いた場合の接合面のコストを計算し終えるまで、ステップＳ２０４〜Ｓ２０６の処理を繰り返す。
【００８１】
後端面の探査を完了すると（ステップＳ２０５；ＹＥＳ）、次に制御部１０は、前端面の探査を完了したか否かを判別する（ステップＳ２０７）。すなわち、制御部１０は、第２の探査区間５１ｂにおいて選択可能な前端面の候補のそれぞれを選択して、それを後端面と組み合わせた場合の接合面のコストを計算し終えたか否かを判別する。
【００８２】
前端面の探査を完了していないと（ステップＳ２０７；ＮＯ）、制御部１０は、第２の探査区間５１ｂ内の前端面の別の候補を１つ選択する（ステップＳ２０８）。すなわち、制御部１０は、第２の探査区間５１ｂにおける動画空間内を画素単位で分割する面のうち、すでにコストを計算した前端面とは異なる面を選択する。
【００８３】
前端面の別の候補を選択すると、接合面の決定処理はステップＳ２０３に戻り、制御部１０は、新たに候補として選択した前端面と組み合せ可能な後端面を選択し、それらを用いた場合の接合面のコストを計算する。このように、制御部１０は、第１の探査区間５１ａの後端面の候補と第２の探査区間５１ｂの前端面の候補との組合せのうち、選択可能な組合せのそれぞれを選択して、それらを用いた場合の接合面のコストを計算し終えるまで、ステップＳ２０３〜Ｓ２０８の処理を繰り返す。
【００８４】
その後、前端面の探査を完了すると（ステップＳ２０７；ＹＥＳ）、制御部１０は、ＲＡＭ１０ｃに記憶された接合面の候補のコストを比較して、計算されたコストのうち最小のものを接合面として決定する（ステップＳ２０９）。その後、図６のフローチャートにおける接合面の決定処理は終了する。
【００８５】
このように、制御部１０は、３次元グラフカットの手法に基づいて、２つの探査区間の動画データを接合するための接合面のコストを計算し、コストが最小の接合面を選択する。コストが最小の接合面を選択することによって、接合面を挟んで横方向・縦方向・時間方向に隣接する画素の画素値の、接合される前の動画データとの画素値との差がなるべく少なくなるように、２つの区間の動画データを接合することができる。
【００８６】
制御部１０は、このような接合面の決定処理を、探査区間を徐々に狭め、画素数を徐々に増やしながら複数の階層にわたって実行する。探査区間の幅を狭めて指定する様子を、図１１を参照して説明する。
【００８７】
図１１は、第Ｎ階層において最終的に決定された後端面４３ｅと、第Ｎ＋１階層における探査区間の幅の関係を示す。第Ｎ＋１階層の動画データ３０ｇは、横方向・縦方向・時間方向の各方向において第Ｎ階層の動画データ３０ｆよりも２倍の画素を有する。第Ｎ階層において決定された後端面４３ｅは、第１の探査区間５１ａ内において時間方向に画素３個分の幅“Ｗ”をもつ。
【００８８】
この後端面４３ｅは、第Ｎ階層の動画データ３０ｆにおける画素単位の精度で決定された最もコストが低い接合面であるため、次の第Ｎ＋１階層で最適な接合面を探査するには、直前の第Ｎ階層で決定した接合面の前後１画素分の範囲に限定すればよい。そのため、制御部１０は、第Ｎ階層において決定された後端面４３ｅの幅の前後に画素１つ分の時間方向の幅“Ｕ”を加算した値“Ｗ＋２Ｕ”を、第Ｎ＋１階層における後端面を探査すべき第１の探査区間５１ｃの時間長として設定する。なお、制御部１０は、前端面を探査すべき第２の探査区間についても、同様に新たな探査区間の時間長を設定する。
【００８９】
このように、各階層における接合面の探査区間の時間長を、直前の階層において決定された接合面が占める時間方向の幅の前後にこの階層における画素１つ分の幅を加算した値の時間長に狭めて設定することで、過不足のない範囲に絞って最適な接合面を探査することができる。
【００９０】
以上説明したように、実施形態１の動画生成装置１は、１つの入力動画データのうちの２つの区間の動画データを繋げてループさせた新たな動画データを生成する。その際、動画生成装置１は、３次元グラフカットの手法を用いてコストが最小となる接合面を、入力動画データの画素数を減らした動画データから元の入力動画データまで、探査区間を徐々に狭め、画素数を徐々に増やしながら階層的に探査する。そのため、２つの区間の動画データを空間方向及び時間方向に滑らかに接合するために最適な接合面を、計算量を抑制しつつ、入力動画データのなるべく広い範囲から見つけることができる。
【００９１】
（実施形態２）
次に、本発明の実施形態２について説明する。実施形態１では、１つの入力動画データ３０ａのうちの後方の区間の動画データの後に前方の区間の動画データを繋ぎ合わせてループする動画データ３０ｂを生成する処理について説明した。これに対し、実施形態２では、動画生成装置１が実行する処理のうち、２つの入力動画データを繋げて新たな１つの動画データを生成する処理について説明する。
【００９２】
実施形態２に係る動画生成装置１は、実施形態１における図１及び図２と同様な物理構成及び機能構成を備えるため、ここでは説明を省略する。
【００９３】
実施形態１に係る動画生成装置１は、図１２に示すような動画生成処理を実行する。動画生成装置１は、２つの入力動画データである第１の動画データ３０ｐと第２の動画データ３０ｑとを接合して、新たな動画データ３０ｒを生成する。第１の動画データ３０ｐが静止画データ３１ａ〜３１ｃから始まる複数の静止画データによって構成され、第２の動画データ３０ｑが静止画データ３１ｘ〜３１ｚで終わる複数の静止画データによって構成される場合、新たな動画データ３０ｒは、静止画データ３１ａ〜３１ｃから始まり静止画データ３１ｘ〜３１ｚで終わる動画データとなる。
【００９４】
動画生成装置１は、新たな動画データ３０ｒを生成するための接合面として、第１の動画データ３０ｐと第２の動画データ３０ｑとで同じ形状の面であって、接合面周辺の動画データが滑らかに繋がるような接合面４１ｐを決定する。そして、動画生成装置１は、この接合面４１ｐを境界として、第１の動画データ３０ｐの後に第２の動画データ３０ｑが繋がるように、接合処理を行う。例えば、第１の動画データ３０ｐの先頭と接合面４１ｐとの間の時間長が“Ｄ１”であり、第２の動画データ３０ｑの末尾と接合面４１ｐとの間の時間長が“Ｄ２”である場合、新たな動画データ３０ｒは、先頭から末尾まで“Ｄ１＋Ｄ２”の時間長を有する動画データとなる。
【００９５】
実施形態２に係る動画生成装置１が実行する処理の流れについて、以下、図１３に示すフローチャートを参照して説明する。
【００９６】
動画生成装置１において、まず制御部１０が、動画生成の指示があったか否かを判別する（ステップＳ３０１）。制御部１０は、例えば操作部１２を介して操作者からの動画生成の指示があったか否かを判別する。
【００９７】
動画生成の指示がないと（ステップＳ３０１；ＮＯ）、処理はステップＳ３０１に留まる。すなわち、制御部１０は、動画生成の指示があると判別されるまで、引き続き動画生成の指示があったか否かを判別する。
【００９８】
一方、動画生成の指示があったと判別されると（ステップＳ３０１；ＹＥＳ）、制御部１０は、動画生成に用いる２つの入力動画データを取得する（ステップＳ３０２）。制御部１０は、例えば記憶部１１に記憶された動画データを読み出したり、Ｉ／Ｆ部１４を介して各種の記憶媒体に記憶された動画データを読み出したり、通信部１５を介してネットワーク１６上にある動画データを受信したりすることによって２つの入力動画データを取得する。
【００９９】
２つの入力動画データを取得すると、制御部１０は、出力動画データの最小時間長を設定する（ステップＳ３０３）。すなわち、接合面となる前端面と後端面とが２つの入力データ内のどの位置になるかによって、出力動画データの先頭から末尾までの時間長が変わる。そのため、制御部１０は、出力動画データの時間長が極端に短くならないように、最低限の時間長を設定する。
【０１００】
設定される最小時間長は、予めＲＯＭ１０ｂや記憶部１１に記憶されていてもよい。あるいは、操作者が、操作部１２を介して生成したい新たな動画データの最低限の長さを入力し、最小時間長として設定できるようにしてもよい。
【０１０１】
出力動画データの最小時間長を設定すると、動画生成装置１の処理は、画素数の減少率と接合面の探査区間を段階的に変化させて最適な接合面を決定する処理に移行する。
【０１０２】
まず初期階層では、制御部１０は、２つの入力動画データの画素数を予め設定された減少率で減少させ（ステップＳ３０４）、画素数が減少した２つの動画データを生成する。すなわち、制御部１０は、２つの入力動画データを構成する複数の静止画データ内において横方向と縦方向に並べられた画素、及び、２つの入力動画データのフレーム数を減らす。画素数を減少させる方法として、制御部１０は、実施形態１と同様、画素を間引いてもよいし、ビニングしてもよい。
【０１０３】
画素数が減少した動画データを生成すると、制御部１０は、画素数が減少した２つの動画データ全体を接合面の探査区間に指定する（ステップＳ３０５）。すなわち、初期階層では、第１の動画データの区間全体が後端面を探査するための第１の探査区間に指定され、第２の動画データの区間全体が前端面を探査するための第２の探査区間に指定される。
【０１０４】
接合面の探査区間を指定すると、制御部１０は、グラフカットの手法を用いて、探索区間内の動画データを接合するための接合面を決定する（ステップＳ３０６）。接合面の決定処理の詳細は、２つの入力動画データのうちの第１の動画データにおける接合面が後端面となり、第２の動画データにおける接合面が前端面として対応させることで、図６のフローチャートを用いて実施形態１と同様に説明できる。そのため、ここでは説明を省略する。
【０１０５】
接合面を決定すると、制御部１０は、画素数を減少させた際の減少率が０であるか否かを判別する（ステップＳ３０７）。初期階層では、減少率は複数の階層の中で最大の値であって０ではないため、ステップＳ３０７ではＮＯと判別される。そして、動画生成装置１の処理は、中間階層の処理へと移行する。
【０１０６】
中間階層では、制御部１０は、画素数を減少させる際の減少率を下げ（ステップＳ３０８）、初期階層で用いられた減少率よりも低い減少率に変更する。そして、変更した減少率で２つの入力動画データの画素数を減少させた２つの動画データを生成する。
【０１０７】
初期階層よりも多くの画素を有する動画データを生成すると、制御部１０は、探査区間を狭める（ステップＳ３０９）。すなわち、制御部１０は、中間階層における動画データにおいて前端面を探査するための探査区間を、初期階層において決定された前端面を含むような動画データの一部の区間に狭めて指定し直す。同様に、制御部１０は、後端面を探査するための探査区間を、初期階層において決定された前端面を含むような動画データの一部の区間に狭めて指定し直す。
【０１０８】
そして、動画生成装置１の処理はステップＳ３０６に戻り、制御部１０は、グラフカットの手法を用いて、幅が狭められて指定された探索区間内の動画データを接合するための接合面を決定する（ステップＳ３０６）。そして、再び制御部１０は、変更された減少率が０であるか否かを判別する（ステップＳ３０７）。このように、最終階層において減少率が０に設定され、画素の間引き又はビニングがされない元の入力動画データでの最適な接合面が決定されるまで、ステップＳ３０６〜Ｓ３０９の処理が繰り返される。
【０１０９】
例えば、ある中間階層において接合面を決定する様子を図１４に示す。制御部１０は、画素数が削減された第１の動画データ３０ｓと第２の動画データ３０ｔを接合するための接合面であって、第１の探査区間５１ｐと第２の探査区間５１ｑとで同じ形状の前端面の候補４４ｐと後端面の候補４５ｐを１組選択する。
【０１１０】
このとき、制御部１０は、ステップＳ３０３において設定した出力動画データの最小時間長の値も制約として加えて、前端面の候補４４ｐと後端面の候補４５ｐとを選ぶ。出力動画データの先頭から末尾までの時間長は、第１の動画データ３０ｓの先頭から後端面の候補４５ｐまでの時間長“Ｄ１”と、第２の動画データ３０ｔの末尾から前端面の候補４４ｐまでの時間長“Ｄ２”と、の和として表される。そのため、制御部１０は、この和“Ｄ１＋Ｄ２”があらかじめ設定された出力動画データの時間長の最小値以上となるように、前端面の候補４４ｐと後端面の候補４５ｐとを選ぶ。
【０１１１】
図１３のフローチャートに戻って、最終階層の処理まで実行され、画素数の減少率が０であると判別されると（ステップＳ３０７；ＹＥＳ）、制御部１０は、最終的に決定された接合面で２つの入力動画データを繋げた出力動画データを生成する（ステップＳ３１０）。そして、動画生成処理は終了する。
【０１１２】
図１２の例を用いて具体的に説明すると、制御部１０は、第１の動画データ３０ｐのうちの後端面である接合面４１ｐよりも前の動画データと、第２の動画データ３０ｑのうちの前端面である接合面４１ｐよりも後の動画データが繋ぎ合わされた新たな動画データ３０ｒを生成する。生成された動画データ３０ｒは、例えば記憶部１１に保存され、制御部１０の制御のもと、表示部１３を介して再生表示されたり、Ｉ／Ｆ部１４や通信部１５を介して外部に提供されたりする。
【０１１３】
以上説明したように、実施形態２の動画生成装置１は、２つの入力動画データを接合して新たな１つの動画データを生成する。その際、動画生成装置１は、３次元グラフカットの手法を用いてコストが最小となる接合面を、入力動画データの画素数を減らした動画データから元の入力動画データまで、探査区間を徐々に狭め、画素数を徐々に増やしながら階層的に探査する。そのため、２つの区間の動画データを空間方向及び時間方向に滑らかに接合するために最適な接合面を、計算量を抑制しつつ、入力動画データのなるべく広い範囲から見つけることができる。
【０１１４】
（他の実施形態）
以上に本発明の実施形態１及び２について説明したが、これらの実施形態は一例であり、本発明の適用範囲はこれに限られない。すなわち、本発明の実施形態は種々の応用が可能であり、あらゆる実施の形態が本発明の範囲に含まれる。
【０１１５】
例えば、上記実施形態では、１つ又は２つの入力動画データの区間全体が、接合面の決定処理の初期階層における接合面の探査区間に指定され、区間全体において選択可能な接合面の候補のうちから最適な接合面が決定された。しかし、本発明では、初期階層における接合面の探査区間として、入力動画データの区間全体が指定されることに限らず、入力動画データの一部の区間が指定されてもよい。例えば、操作者が接合させたい部分があらかじめ入力動画データ内の一部の区間に限定されているような場合、初期階層における接合面の探査区間を入力動画データの一部の区間に限定する方が、入力動画データの区間全体に設定するより効果的である。
【０１１６】
入力動画データのどの区間を初期階層における探査区間に指定するべきかの情報は、予めＲＯＭ１０ｂや記憶部１１に記憶されていてもよいし、操作部１２を介して操作者から受け付けられてもよい。探査区間は、例えば動画データの先頭又は末尾からの秒数やフレーム数のように、時間長を用いて指定されてもよい。また、例えば動画データの第Ｍフレームから第Ｎフレームまでの区間のように、区間の始期と終期を用いて指定されてもよい。
【０１１７】
また、出力動画データの最小周期や最小時間長を設定するかわりに、初期階層における接合面の探査区間として入力動画データの一部の区間を指定することによって、操作者が、出力動画データの周期や時間長を調整できるようにしてもよい。あるいは、出力動画データの最小周期又は最小時間長と、初期階層における接合面の探査区間との両方を設定できるようにしてもよい。
【０１１８】
また、上記実施形態に係る動画生成装置１は、初期階層から最終階層までのいずれの階層においても、探査区間の動画データの隣接する２つの画素のうち横方向・縦方向・時間方向のいずれの方向に隣接する２つの画素の間も通ることが可能な折れ曲がった面を、接合面の候補として選択した。しかし、例えば、画素数の減少率が相対的に大きい前半の階層では、横方向・縦方向・時間方向のうち時間方向に隣接する２つの画素の間のみを通る面であって、動画空間を時間方向に垂直に分割する面を接合面として選ぶようにしてもよい。そして、画素数の減少率が相対的に小さい後半の階層では、横方向・縦方向・時間方向のうちいずれの方向に隣接する２つの画素の間を通ることができる折れ曲がった面のうちから接合面の候補を選ぶようにしてもよい。
【０１１９】
このように動画空間における横方向・縦方向・時間方向のうち、階層が進んで画素数の減少率が所定の閾値以下となるまでは時間方向に隣接する２つの画素の間のみを通る面を接合面とすることによって、浅い階層では候補となる接合面の数が抑制される。そのため、接合面の決定処理をさらに効率化することができる。
【０１２０】
また、本発明の動画生成装置は、各階層において接合面を決定して次の階層の処理へ移行する際の入力動画データの画素数の減少率を下げる程度を、決定された接合面のコストの大きさに応じて変更するようにしてもよい。ある階層において決定された接合面のコストが相対的に小さい場合は、最適な接合面をすぐに見つけられる可能性が高い。一方、接合面のコストが相対的に大きい場合は、最適な接合面を見つけるためには多くの階層に分けて手間をかけて探査したようがよいと考えられる。
【０１２１】
そのため、例えば接合面のコストが小さくなるほど減少率の低下度が大きくなるような接合面のコストと減少率の低下度の関係をＲＯＭ１０ｂや記憶部１１に記憶しておき、制御部１０が、記憶された関係に基づいて入力動画データの画素数を減少させ、接合面を探査する階層数を減らすようにしてもよい。これにより、より効率的に最適な接合面を探査することができるようになる。
【０１２２】
また、上記実施形態では、接合面のコストは、接合面を挟んで隣接する２つの画素の間に対応付けられた隣接項の、接合面を挟んで隣接する２つの画素の組合せのそれぞれについての和として定義された。しかし、本発明の動画生成処理における接合面のコストは、このような定義に限らない。例えば、上記の和は、隣接項の値の自乗について計算されてもよい。その他にも、接合面のコストは、計算に用いられる隣接項の値が大きくなるほどコストが大きくなるような定義の仕方であれば、どのように定義されてもよい。
【０１２３】
また、上記実施形態では、各動画データはグレースケールの動画であって、各画素は１つの画素値を有するとして説明した。しかし、本発明の動画生成装置が動画生成処理を実行するための入力動画データ及び出力動画データは、グレースケールの動画に限らない。例えば、動画データの各画素は、Ｒ（レッド）、Ｇ（グリーン）、Ｂ（ブルー）、の３つの画素値を有してもよい。
【０１２４】
このようなカラーの動画データを扱う場合、上述した隣接項の設定処理や接合面のコストの計算処理において、ＲＧＢの３つの画素値のそれぞれについて独立に処理が行われてもよい。あるいは、１つの画素が有するＲＧＢの３つの画素値を１つのベクトル値として、上記の処理が行われてもよい。
【０１２５】
また、上記実施形態では、減少率が０に設定されるまで、探査区間を徐々に狭め、画素数を徐々に増やしながら最適な接合面を繰り返し探査するとして説明した。しかし、所望の解像度、或いは画素数を満たす減少率が設定されるまで、探査区間を徐々に狭め、画素数を徐々に増やしながら最適な接合面を繰り返し探査し、所望の解像度、或いは画素数の動画データを探査された接合面で接合してもよい。これにより、入力動画データから所望の解像度、或いは画素数の動画データが接合された動画データを生成することができる。
【０１２６】
また、動画生成装置１は、操作部１２と表示部１３とを備えなくともよい。例えば、動画生成装置１は、操作部１２と表示部１３を備えたクライアント端末とネットワーク１６を介して接続されたサーバ装置のように機能してもよい。この場合、動画生成装置１は、クライアント端末の操作部１２によって受け付けられた指示入力を、通信部１５を介して受け付ける。また、動画生成装置１は、処理の結果を示す画像データを、通信部１５を介してクライアント端末に送信し、クライアント端末の表示部１３に画像を表示する。
【０１２７】
なお、本発明に係る機能を実現するための構成を予め備えた動画生成装置として提供できることはもとより、プログラムの適用により、既存のパーソナルコンピュータや情報端末機器等を、本発明に係る動画生成装置として機能させることもできる。すなわち、上記実施形態で例示した動画生成装置１による各機能構成を実現させるためのプログラムを、既存のパーソナルコンピュータや情報端末機器等を制御するＣＰＵ等が実行できるように適用することで、本発明に係る動画生成装置１として機能させることができる。また、本発明に係る動画生成方法は、動画生成装置１を用いて実施できる。
【０１２８】
また、このようなプログラムの適用方法は任意である。プログラムを、例えば、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、メモリカード等のコンピュータ読み取り可能な記憶媒体に格納して適用できる。さらに、プログラムを搬送波に重畳し、インターネットなどの通信媒体を介して適用することもできる。例えば、通信ネットワーク上の掲示板（ＢＢＳ：Bulletin Board System）にプログラムを掲示して配信してもよい。そして、このプログラムを起動し、ＯＳの制御下で、他のアプリケーションプログラムと同様に実行することにより、上記の処理を実行できるように構成してもよい。
【０１２９】
以上、本発明の好ましい実施形態について説明したが、本発明は係る特定の実施形態に限定されるものではなく、本発明には、特許請求の範囲に記載された発明とその均等の範囲が含まれる。以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
【０１３０】
（付記１）
動画データの画素数を減少させる減少手段と、
前記減少手段によって画素数が減少した動画データの時間区間である第１の区間と第２の区間とを指定する指定手段と、
前記第１の区間の動画データ及び前記第２の区間の動画データを構成する複数の静止画データの２次元座標が揃うように該複数の静止画データが時系列順に並べられた静止画群が占める空間における、前記２次元座標の横方向に隣接する２つの画素の間、前記２次元座標の縦方向に隣接する２つの画素の間、及び、前記静止画群の時間方向に隣接する２つの画素の間、を通って該空間を分割する面であって、前記第１の区間における該面よりも前の動画データと前記第２の区間における該面よりも後の動画データとを接合するための接合面を決定する決定手段と、
前記減少手段における画素数の減少率を下げ、且つ、前記指定手段が指定する前記第１の区間及び前記第２の区間のそれぞれを該それぞれの区間において決定された前記接合面を含むような区間に狭めて、前記減少手段、前記指定手段、及び、前記決定手段の処理を、繰り返し実行する繰返し手段と、
前記第１の区間における接合面よりも前の動画データと、前記第２の区間における接合面よりも後の動画データと、が順に繋ぎ合わされた動画データを生成する生成手段と、
を備える動画生成装置。
【０１３１】
（付記２）
前記指定手段は、１つの動画データの時間区間を前記第１の区間として指定し、該１つの動画データの一部の時間区間であって前記第１の区間よりも前の区間を前記第２の区間として指定し、
前記生成手段は、前記１つの動画データのうちの前記第１の区間における接合面よりも前であって前記第２の区間における接合面よりも後の動画データが繰り返し繋ぎ合わされた動画データを生成する、
ことを特徴とする付記１に記載の動画生成装置。
【０１３２】
（付記３）
前記決定手段は、前記第１の区間における接合面と前記第２の区間における接合面との間の時間長が前記生成される動画データの繰り返し周期のあらかじめ設定された最小値以上となるように、前記接合面を決定する、
ことを特徴とする付記２に記載の動画生成装置。
【０１３３】
（付記４）
前記指定手段は、２つの動画データのうちの第１の動画データの時間区間を前記第１の区間として指定し、該２つの動画データのうちの第２の動画データの時間区間を前記第２の区間として指定し、
前記生成手段は、前記第１の動画データのうちの前記第１の区間における接合面よりも前の動画データと、前記第２の動画データのうちの前記第２の区間における接合面よりも後の動画データと、が順に繋ぎ合わされた動画データを生成する、
ことを特徴とする付記１に記載の動画生成装置。
【０１３４】
（付記５）
前記決定手段は、前記第１の動画データの先頭から前記第１の区間における接合面までの時間長と、前記第２の動画データの末尾から前記第２の区間における接合面までの時間長と、の和が前記生成される動画データの先頭から末尾までの時間長のあらかじめ設定された最小値以上となるように、前記接合面を決定する、
ことを特徴とする付記４に記載の動画生成装置。
【０１３５】
（付記６）
前記決定手段は、前記静止画群が占める空間において隣接する２つの画素の間を通る前記接合面の候補のうち、該接合面の候補を挟んで隣接する２つの画素に対応付けられた隣接項の値の、該接合面の候補を挟んで隣接する２つの画素の組合せのそれぞれについての加算値が最小となる接合面の候補を、前記接合面として決定する、
ことを特徴とする付記１乃至５のいずれか１つに記載の動画生成装置。
【０１３６】
（付記７）
前記隣接項の値は、前記接合面の候補を挟んで隣接する２つの画素のうち、
一方の画素の画素値と、前記第１の区間と前記第２の区間のうち該一方の画素が属する区間と異なる区間において該接合面の候補の位置を基準に該一方の画素と同じ位置にある画素の画素値と、の差と、
他方の画素の画素値と、前記第１の区間と前記第２の区間のうち該他方の画素が属する区間と異なる区間において該接合面の候補の位置を基準に該他方の画素と同じ位置にある画素の画素値と、の差と、
の和として定められる、
ことを特徴とする付記６に記載の動画生成装置。
【０１３７】
（付記８）
前記繰返し手段は、前記決定された接合面の前記加算値が小さいほど前記減少手段における画素数の減少率を下げる程度を大きくする、
ことを特徴とする付記６又は７に記載の動画生成装置。
【０１３８】
（付記９）
前記繰返し手段は、前記指定手段が指定する前記第１の区間及び前記第２の区間のそれぞれを該それぞれの区間において決定された前記接合面が占める時間長の前後に該それぞれの区間における画素１つの時間長を加算した時間長の区間に狭めて、前記減少手段、前記指定手段、及び、前記決定手段の処理を、繰り返し実行する、
ことを特徴とする付記１乃至８のいずれか１つに記載の動画生成装置。
【０１３９】
（付記１０）
前記決定手段は、前記減少手段における画素数の減少率が所定の閾値以下となるまでは、前記静止画群が占める空間における前記時間方向に隣接する２つの画素の間を通って該空間を該時間方向に垂直に分割する面を前記接合面として決定する、
ことを特徴とする付記１乃至９のいずれか１つに記載の動画生成装置。
【０１４０】
（付記１１）
前記繰返し手段は、前記減少率を０に下げた場合における前記減少手段、前記指定手段、及び、前記決定手段の処理が実行されるまで繰り返す、
ことを特徴とする付記１乃至１０のいずれか１つに記載の動画生成装置。
【０１４１】
（付記１２）
動画データの画素数を減少させる減少ステップと、
前記減少ステップによって画素数が減少した動画データの時間区間である第１の区間と第２の区間とを指定する指定ステップと、
前記第１の区間の動画データ及び前記第２の区間の動画データを構成する複数の静止画データの２次元座標が揃うように該複数の静止画データが時系列順に並べられた静止画群が占める空間における、前記２次元座標の横方向に隣接する２つの画素の間、前記２次元座標の縦方向に隣接する２つの画素の間、及び、前記静止画群の時間方向に隣接する２つの画素の間、を通って該空間を分割する面であって、前記第１の区間における該面よりも前の動画データと前記第２の区間における該面よりも後の動画データとを接合するための接合面を決定する決定ステップと、
前記減少ステップにおける画素数の減少率を下げ、且つ、前記指定ステップで指定する前記第１の区間及び前記第２の区間のそれぞれを該それぞれの区間において決定された前記接合面を含むような区間に狭めて、前記減少ステップ、前記指定ステップ、及び、前記決定ステップの処理を、繰り返し実行する繰返しステップと、
前記第１の区間における接合面よりも前の動画データと、前記第２の区間における接合面よりも後の動画データと、が順に繋ぎ合わされた動画データを生成する生成ステップと、
を含むことを特徴とする動画生成方法。
【０１４２】
（付記１３）
コンピュータに、
動画データの画素数を減少させる減少機能、
前記減少機能によって画素数が減少した動画データの時間区間である第１の区間と第２の区間とを指定する指定機能、
前記第１の区間の動画データ及び前記第２の区間の動画データを構成する複数の静止画データの２次元座標が揃うように該複数の静止画データが時系列順に並べられた静止画群が占める空間における、前記２次元座標の横方向に隣接する２つの画素の間、前記２次元座標の縦方向に隣接する２つの画素の間、及び、前記静止画群の時間方向に隣接する２つの画素の間、を通って該空間を分割する面であって、前記第１の区間における該面よりも前の動画データと前記第２の区間における該面よりも後の動画データとを接合するための接合面を決定する決定機能、
前記減少機能における画素数の減少率を下げ、且つ、前記指定機能で指定する前記第１の区間及び前記第２の区間のそれぞれを該それぞれの区間において決定された前記接合面を含むような区間に狭めて、前記減少機能、前記指定機能、及び、前記決定機能の処理を、繰り返し実行する繰返し機能、
前記第１の区間における接合面よりも前の動画データと、前記第２の区間における接合面よりも後の動画データと、が順に繋ぎ合わされた動画データを生成する生成機能、
を実現させることを特徴とするプログラム。
【符号の説明】
【０１４３】
１…動画生成装置、１０…制御部、１０ａ…ＣＰＵ、１０ｂ…ＲＯＭ、１０ｃ…ＲＡＭ、１０ｄ…画像処理部、１１…記憶部、１２…操作部、１３…表示部、１４…Ｉ／Ｆ部、１５…通信部、１６…ネットワーク、２０…減少手段、２１…指定手段、２２…決定手段、２３…繰返し手段、２４…生成手段、３０ａ〜３０ｇ，３０ｐ〜３０ｔ…動画データ、３１ａ〜３１ｃ，３１ｐ〜３１ｒ，３１ｘ〜３１ｚ…静止画データ、４１ａ，４１ｐ…接合面、４２ａ〜４２ｄ…前端面、４３ａ〜４３ｅ…後端面、４４ａ，４４ｐ…前端面の候補、４５ａ，４５ｂ，４５ｐ…後端面の候補、５１ａ〜５１ｃ，５１ｐ，５１ｑ…探査区間、５２ａ〜５２ｆ，５２ｐ〜５２ｓ…周縁フレーム、５３ａ〜５３ｄ…隣接項
【図１】
0005874538.tif 000002
【図２】
0005874538.tif 000003
【図３】
0005874538.tif 000004
【図４】
0005874538.tif 000005
【図５】
0005874538.tif 000006
【図６】
0005874538.tif 000007
【図７】
0005874538.tif 000008
【図８】
0005874538.tif 000009
【図９】
0005874538.tif 000010
【図１０】
0005874538.tif 000011
【図１１】
0005874538.tif 000012
【図１２】
0005874538.tif 000013
【図１３】
0005874538.tif 000014
【図１４】
0005874538.tif 000015