(57)【特許請求の範囲】
【請求項１】
第１動画と、第２動画と、を合成する動画処理装置であって、前記第１動画には、第１オブジェクトが描かれ、前記第１オブジェクトの奥行情報を伴い、前記第２動画には、第２オブジェクトが描かれ、前記第２オブジェクトの奥行情報を伴い、
前記第１動画と、前記第２動画と、を合成した第３動画を生成する動画生成部、
前記第３動画において、前記第１オブジェクトの奥行情報ならびに前記第２オブジェクトの奥行情報を参照して、前記第１オブジェクトと、前記第２オブジェクトと、の、干渉の度合を表す干渉量を計算し、前記第１オブジェクトと、前記第２オブジェクトと、が、干渉条件を満たすか否かを判定する干渉判定部、
前記干渉条件が満たされる、と判定された場合、前記計算された干渉量に基づいて、前記第２オブジェクトの時間経過に応じた３次元空間内の移動を表す軌跡の形状の修正箇所および修正量を表す変換パラメータを更新し、前記更新された変換パラメータにより変形変換を施すことにより、前記第２動画を修正する修正部
を備えることを特徴とする動画処理装置。
【請求項２】
請求項１に記載の動画処理装置であって、
前記干渉条件が満たされないように、前記変換パラメータを更新する
ことを特徴とする動画処理装置。
【請求項３】
請求項２に記載の動画処理装置であって、
前記干渉条件は、前記第１オブジェクトと、前記第２オブジェクトと、が、干渉すれば、満たされる
ことを特徴とする動画処理装置。
【請求項４】
請求項１に記載の動画処理装置であって、
前記修正部は、前記干渉量と、前記変換パラメータと、により定められる評価関数を最小化するように、前記変換パラメータを更新する
ことを特徴とする動画処理装置。
【請求項５】
請求項１に記載の動画処理装置であって、
前記修正部は、前記干渉量が最大となるフレームにおいて、前記第２オブジェクトの位置を前記干渉量がゼロになるように修正し、当該位置の修正量を減少させながら隣接するフレームに伝播させて前記第２オブジェクトの位置を修正することを繰り返すことにより、前記変換パラメータを更新する
ことを特徴とする動画処理装置。
【請求項６】
請求項１に記載の動画処理装置であって、
前記変形変換は、前記軌跡の接ベクトルの大きさは保ちつつ、主法線ベクトルの大きさを変化させる
ことを特徴とする動画処理装置。
【請求項７】
請求項１に記載の動画処理装置であって、
前記干渉量は、各フレームにおける前記第１オブジェクトの奥行情報に基いて推定される前記第１オブジェクトの形状と、前記第２オブジェクトの奥行情報に基づいて推定される前記第２オブジェクトの形状と、が、重複する体積の総和である
ことを特徴とする動画処理装置。
【請求項８】
請求項１に記載の動画処理装置であって、
前記干渉量は、各フレームにおける前記第１オブジェクトが描画されるべき領域と、前記第２オブジェクトが描画されるべき領域と、が、重複する面積の総和である
ことを特徴とする動画処理装置。
【請求項９】
第１動画と、第２動画と、を合成する動画処理装置であって、前記第１動画には、第１オブジェクトが描かれ、前記第１オブジェクトの奥行情報を伴い、前記第２動画には、第２オブジェクトが描かれ、前記第２オブジェクトの奥行情報を伴い、
前記第１動画と、前記第２動画と、を合成した第３動画を生成する動画生成部、
前記第３動画に含まれるフレームにおいて、前記第１オブジェクトと、前記第２オブジェクトと、が、干渉条件を満たすか否かを、前記第１オブジェクトの奥行情報ならびに前記第２オブジェクトの奥行情報を参照して判定する干渉判定部、
前記干渉条件が満たされる、と判定された場合、少なくとも前記干渉条件が満たされると判定されたフレームにおいて、前記第２オブジェクトの奥行情報を変更せずに２次元画面上の描画位置を変更する変換を施すことにより、前記第２動画を修正する修正部
を備えることを特徴とする動画処理装置。
【請求項１０】
第１動画と、第２動画と、を合成する動画処理方法であって、前記第１動画には、第１オブジェクトが描かれ、前記第１オブジェクトの奥行情報を伴い、前記第２動画には、第２オブジェクトが描かれ、前記第２オブジェクトの奥行情報を伴い、
前記第１動画と、前記第２動画と、を合成した第３動画を生成する動画生成工程、
前記第３動画において、前記第１オブジェクトの奥行情報ならびに前記第２オブジェクトの奥行情報を参照して、前記第１オブジェクトと、前記第２オブジェクトと、の、干渉の度合を表す干渉量を計算し、前記第１オブジェクトと、前記第２オブジェクトと、が、干渉条件を満たすか否かを判定する干渉判定工程、
前記干渉条件が満たされる、と判定された場合、前記計算された干渉量に基づいて、前記第２オブジェクトの時間経過に応じた３次元空間内の移動を表す軌跡の形状の修正箇所および修正量を表す変換パラメータを更新し、前記更新された変換パラメータにより変形変換を施すことにより、前記第２動画を修正する修正工程
を備えることを特徴とする動画処理方法。
【請求項１１】
第１動画と、第２動画と、を合成する動画処理方法であって、前記第１動画には、第１オブジェクトが描かれ、前記第１オブジェクトの奥行情報を伴い、前記第２動画には、第２オブジェクトが描かれ、前記第２オブジェクトの奥行情報を伴い、
前記第１動画と、前記第２動画と、を合成した第３動画を生成する動画生成工程、
前記第３動画に含まれるフレームにおいて、前記第１オブジェクトと、前記第２オブジェクトと、が、干渉条件を満たすか否かを、前記第１オブジェクトの奥行情報ならびに前記第２オブジェクトの奥行情報を参照して判定する干渉判定工程、
前記干渉条件が満たされる、と判定された場合、少なくとも前記干渉条件が満たされると判定されたフレームにおいて、前記第２オブジェクトの奥行情報を変更せずに２次元画面上の描画位置を変更する変換を施すことにより、前記第２動画を修正する修正工程
を備えることを特徴とする動画処理方法。
【請求項１２】
第１動画と、第２動画と、を合成するプログラムであって、前記第１動画には、第１オブジェクトが描かれ、前記第１オブジェクトの奥行情報を伴い、前記第２動画には、第２オブジェクトが描かれ、前記第２オブジェクトの奥行情報を伴い、
前記プログラムは、コンピュータを、
前記第１動画と、前記第２動画と、を合成した第３動画を生成する動画生成部、
前記第３動画において、前記第１オブジェクトの奥行情報ならびに前記第２オブジェクトの奥行情報を参照して、前記第１オブジェクトと、前記第２オブジェクトと、の、干渉の度合を表す干渉量を計算し、前記第１オブジェクトと、前記第２オブジェクトと、が、干渉条件を満たすか否かを判定する干渉判定部、
前記干渉条件が満たされる、と判定された場合、前記計算された干渉量に基づいて、前記第２オブジェクトの時間経過に応じた３次元空間内の移動を表す軌跡の形状の修正箇所および修正量を表す変換パラメータを更新し、前記更新された変換パラメータにより変形変換を施すことにより、前記第２動画を修正する修正部
として機能させることを特徴とするプログラム。
【請求項１３】
第１動画と、第２動画と、を合成するプログラムであって、前記第１動画には、第１オブジェクトが描かれ、前記第１オブジェクトの奥行情報を伴い、前記第２動画には、第２オブジェクトが描かれ、前記第２オブジェクトの奥行情報を伴い、
前記プログラムは、コンピュータを、
前記第１動画と、前記第２動画と、を合成した第３動画を生成する動画生成部、
前記第３動画に含まれるフレームにおいて、前記第１オブジェクトと、前記第２オブジェクトと、が、干渉条件を満たすか否かを、前記第１オブジェクトの奥行情報ならびに前記第２オブジェクトの奥行情報を参照して判定する干渉判定部、
前記干渉条件が満たされる、と判定された場合、少なくとも前記干渉条件が満たされると判定されたフレームにおいて、前記第２オブジェクトの奥行情報を変更せずに２次元画面上の描画位置を変更する変換を施すことにより、前記第２動画を修正する修正部
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画処理装置、動画処理方法、ならびに、情報記録媒体に関し、複数の動画に描かれた奥行情報を伴うオブジェクトを１つの動画にまとめようとするときに、オブジェクト同士が干渉条件を満たさないようにするものである。
【背景技術】
【０００２】
従来から、撮影されるオブジェクトとカメラとの距離（奥行、Ｚ距離）を取得して、奥行情報を伴う画像を作成する技術が提案されている。このような画像は、２.５次元画像と呼ばれることがある（たとえば、非特許文献１参照）。【０００３】
一方で、オブジェクトが位置や形状、色彩などを変化させる様子を描く動画から、ほぼ静止した背景が描かれている領域と移動するオブジェクトが描かれている領域とを分離する技術も提案されている（たとえば、特許文献１参照）。【０００４】
これらの技術を組み合わせることにより、背景とその前で移動するオブジェクトを分離した上で、背景の奥行とオブジェクトの奥行を区別した２.５次元動画を生成することができる。２.５次元動画を構成するフレームには、カメラから見えるオブジェクトの表面（オブジェクトの前面）が描かれ、当該オブジェクトが描かれた描画領域に含まれる画素には、当該画素に対応付けられるオブジェクトの表面部分の色彩のほか、当該表面部分までの奥行（前面奥行）が対応付けられる。【０００５】
このような２.５次元動画は、現実世界をＣＣＤカメラで撮影すると同時に深度センサによる検知を利用したり、現実世界を立体視用のステレオカメラで撮影して対応する画素ごとに視差を求め、その視差から深度を計算することにより得られる。ここで、現実世界を撮影した２.５次元動画には、フレーム内に描かれていないオブジェクトの表面（オブジェクトの背面）の様子は撮影されていないし、背面までの奥行の情報もわからない。【０００６】
このほか、仮想空間内にオブジェクトを配置して移動等をさせる様子を表す動画を３次元グラフィックスにより生成した後、当該動画の各画素における前面奥行のみを付加することによっても、２.５次元動画を得ることができる。このような変換が行われるのは、２.５次元動画とフォーマットの整合性が保てることや、動画編集がしやすくなる等の理由で便利であるためである。【０００７】
なお、３次元グラフィックスの分野では、仮想空間内を移動するオブジェクトが干渉しないように、オブジェクトが占める領域が互いに食い込んだり、一方が他方に貫通するような状況を防止するための、衝突判定の技術が広く用いられている。ここでいう衝突とは、オブジェクト同士の表面の接触は勿論、互いの占める領域が重複するような場合や、実際には両者は離間しているにもかかわらず互いの距離がある閾値よりも近い場合を含むものであり、日常的な語義より広い意味を有する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００９−０８０６６０号公報
【非特許文献】
【０００９】
【非特許文献１】「２.５Ｄ」の項、フリー百科辞典『ウィキペディア』英語版、http://en.wikipedia.org/wiki/2.5D、２０１２年７月１８日に取得
【発明の概要】
【発明が解決しようとする課題】
【００１０】
ここで、異なる２.５次元動画に描かれた複数のオブジェクトを一つの動画にまとめるときに、複数のオブジェクトが同じ領域に重ねて描画されるのであれば、奥行の大小によって、いずれのオブジェクトを優先して描画するかを決めることなる。しかしながら、そもそも、オブジェクト同士が互いに食い込んだり貫通する等、オブジェクト同士が衝突しては、最終的な動画も不自然なものとなってしまう。そこで、オブジェクト同士の位置についての干渉条件を考慮する必要がある。【００１１】
したがって、複数の動画をまとめる際に、動画に描かれたオブジェクトが３次元空間を移動する軌跡を変形する変形変換を施すことにより、オブジェクト同士が干渉条件を満たさないようにする対策が求められている。【００１２】
本発明は、上記のような課題を解決するもので、複数の動画に描かれた奥行情報を伴うオブジェクトを１つの動画にまとめようとするときに、オブジェクトが干渉条件を満たさないようにするのに好適な動画処理装置、動画処理方法、ならびに、情報記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明に係る動画処理装置は、第１動画と、第２動画と、を合成し、前記第１動画には、第１オブジェクトが描かれ、前記第１オブジェクトの奥行情報を伴い、前記第２動画には、第２オブジェクトが描かれ、前記第２オブジェクトの奥行情報を伴い、
前記第１動画と、前記第２動画と、を合成した第３動画を生成する動画生成部、
前記第３動画において、前記第１オブジェクトと、前記第２オブジェクトと、が、干渉条件を満たすか否かを、前記第１オブジェクトの奥行情報ならびに前記第２オブジェクトの奥行情報を参照して判定する干渉判定部、
前記干渉条件が満たされる、と判定された場合、前記第２オブジェクトの時間経過に応じた３次元空間内の移動を表す軌跡の形状を変形する変形変換を施すことにより、前記第２動画を修正する修正部
を備えるように構成する。【００１４】
また、本発明の動画処理装置において、
前記軌跡の形状の修正箇所および修正量を表す変換パラメータにより前記変形変換を施し、更新干渉条件を満たさないように、前記変換パラメータを更新する
ように構成することができる。【００１５】
また、本発明の動画処理装置において、
前記干渉条件は、前記第１オブジェクトと、前記第２オブジェクトと、が、衝突すれば、満たされる
ように構成することができる。【００１６】
また、本発明の動画処理装置において、
前記干渉判定部は、前記第２オブジェクトと前記第１オブジェクトとの衝突の度合を表す衝突量を計算し、
前記修正部は、前記衝突量と、前記変換パラメータと、により定められる評価関数を最小化するように、前記変換パラメータを更新する
ように構成することができる。【００１７】
また、本発明の動画処理装置において、
前記修正部は、前記衝突量が最大となるフレームにおいて、前記１つ以上のオブジェクトの位置を前記衝突量がゼロになるように修正し、当該位置の修正量を減少させながら隣接するフレームに伝播させて前記１つ以上のオブジェクトの位置を修正することを繰り返すことにより、前記変更パラメータを更新する
ように構成することができる。【００１８】
また、本発明の動画処理装置において、
前記変形変換は、前記軌跡の接ベクトルの大きさは保ちつつ、主法線ベクトルの大きさを変化させる
ように構成することができる。【００１９】
また、本発明の動画処理装置において、
前記衝突量は、各フレームにおける前記第１オブジェクトの奥行情報に基づいて推定される前記第１オブジェクトの形状と、前記第２オブジェクトの奥行情報に基づいて推定される前記第２オブジェクトの形状と、が、重複する体積の総和である
ように構成することができる。【００２０】
また、本発明の動画処理装置において、
前記衝突量は、各フレームにおける前記第１オブジェクトが描画されるべき領域と、前記第２オブジェクトが描画されるべき領域と、が、重複する面積の総和である
ように構成することができる。【００２１】
また、本発明の動画処理装置において、
前記軌跡が修正される１つ以上のオブジェクトは、当該１つ以上のオブジェクトの代表点の水平方向、垂直方向および奥行情報の位置に直交変換を施し、当該直交変換後の位置に基づいて、当該１つ以上のオブジェクトが描かれている画像に水平方向および垂直方向における相似変換を施す
ように構成することができる。【００２２】
本発明に係る動画処理方法は、第１動画と、第２動画と、を合成し、前記第１動画には、第１オブジェクトが描かれ、前記第１オブジェクトの奥行情報を伴い、前記第２動画には、第２オブジェクトが描かれ、前記第２オブジェクトの奥行情報を伴い、
前記第１動画と、前記第２動画と、を合成した第３動画を生成する動画生成工程、
前記第３動画において、前記第１オブジェクトと、前記第２オブジェクトと、が、干渉条件を満たすか否かを、前記第１オブジェクトの奥行情報ならびに前記第２オブジェクトの奥行情報を参照して判定する干渉判定工程、
前記干渉条件が満たされる、と判定された場合、前記第２オブジェクトの時間経過に応じた３次元空間内の移動を表す軌跡の形状を変形する変形変換を施すことにより、前記第２動画を修正する修正工程
を備えるように構成する。【００２３】
本発明に係るコンピュータ読取可能な情報記録媒体には、第１動画と、第２動画と、を合成するプログラムが記録され、前記第１動画には、第１オブジェクトが描かれ、前記第１オブジェクトの奥行情報を伴い、前記第２動画には、第２オブジェクトが描かれ、前記第２オブジェクトの奥行情報を伴い、
前記プログラムは、コンピュータを、
前記第１動画と、前記第２動画と、を合成した第３動画を生成する動画生成部、
前記第３動画において、前記第１オブジェクトと、前記第２オブジェクトと、が、干渉条件を満たすか否かを、前記第１オブジェクトの奥行情報ならびに前記第２オブジェクトの奥行情報を参照して判定する干渉判定部、
前記干渉条件が満たされる、と判定された場合、前記第２オブジェクトの時間経過に応じた３次元空間内の移動を表す軌跡の形状を変形する変形変換を施すことにより、前記第２動画を修正する修正部
として機能させるように構成する。【００２４】
上記のプログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読み取り可能な非一時的（non-transitory）な情報記録媒体に記録することができる。この情報記録媒体は、コンピュータとは独立して配布・販売することができる。【００２５】
さらに、上記のプログラムは、プログラムが実行されるコンピュータとは独立して、コンピュータ通信網等の伝送媒体を介して配布・販売することができる。
【発明の効果】
【００２６】
本発明によれば、複数の動画に描かれた奥行情報を伴うオブジェクトを１つの動画にまとめようとするときに、オブジェクトが干渉条件を満たさないようにするのに好適な動画処理装置、動画処理方法、ならびに、情報記録媒体を提供することができる。
【図面の簡単な説明】
【００２７】
【図１】２.５次元動画に描かれるオブジェクトとその諸元の関係を表す説明図である。
【図２Ａ】オブジェクトの断面図である。
【図２Ｂ】オブジェクトの前面を表す断面図である。
【図２Ｃ】厚みを一定とすることにより背面の形状を推定したオブジェクトの断面図である。
【図２Ｄ】オブジェクトの代表的な前面奥行を求め、これに厚みを加算したものを背面奥行とすることにより、オブジェクトの背面の形状を推定したオブジェクトの断面図である。
【図２Ｅ】オブジェクトの背面の形状を球面と推定したオブジェクトの断面図である。
【図３】動画処理装置において、衝突判定を行う要素の概要構成を示す説明図である。
【図４】衝突判定処理の流れを示すフローチャートである。
【図５Ａ】ドラッグが開始される以前の画面の様子を示す説明図である。
【図５Ｂ】ドラッグが開始される時点の画面の様子を示す説明図である。
【図５Ｃ】ドラッグの途中の時点の画面の様子を示す説明図である。
【図５Ｄ】ドロップがされた時点の画面の様子を示す説明図である。
【図６】動画処理装置のドラッグアンドドロップ処理に係る部分の概要構成を示す説明図である。
【図７】ドラッグアンドドロップ処理の制御の流れを示すフローチャートである。
【図８】自動調整処理の制御の流れを示すフローチャートである。
【図９Ａ】ドラッグが開始される以前の画面の様子を示す説明図である。
【図９Ｂ】ドラッグが開始される時点の画面の様子を示す説明図である。
【図９Ｃ】ドラッグの途中の時点の画面の様子を示す説明図である。
【図９Ｄ】ドロップがされた時点の画面の様子を示す説明図である。
【図９Ｅ】ドロップ後に、ドロップ位置の自動修正を行った様子を示す説明図である。
【図１０】ドロップ可能領域の強調表示処理の制御の流れを示すフローチャートである。
【図１１Ａ】軌跡pos[X,i](t)と軌跡pos[Y,j](t)の様子を示す説明図である。
【図１１Ｂ】軌跡pos[X,i](t)と軌跡pos[W,j](t)の様子を示す説明図である。
【図１２Ａ】処理を繰り返すことによって、軌跡が次第に変形していく様子を示す説明図である。
【図１２Ｂ】処理を繰り返すことによって、軌跡が次第に変形していく様子を示す説明図である。
【図１２Ｃ】処理を繰り返すことによって、軌跡が次第に変形していく様子を示す説明図である。
【図１２Ｄ】処理を繰り返すことによって、軌跡が次第に変形していく様子を示す説明図である。
【図１３】衝突を避けるために、軌跡の特定部分において主法線ベクトルを調整した様子を示す説明図である。
【発明を実施するための形態】
【００２８】
以下に本発明の実施形態を説明する。なお、本実施形態は説明のためのものであり、本願発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本発明の範囲に含まれる。
【００２９】
なお、以下に説明する実施形態に係る動画処理装置は、コンピュータがプログラムを実行することによって実現される。ここで、プログラムは、ＲＯＭ（Read Only Memory）やハードディスク等の非一時的（non-transitory）な記憶装置からＲＡＭ（Random Access Memory）等の一時的（temporary）な記憶装置に読み出される。ＣＰＵ（Central Processing Unit）は、ＲＡＭに読み出されたプログラムを順次解釈し、各種記憶装置との間でデータの読み書きをしたり、データに対する計算処理を行ったりする。また、ＣＰＵは、プログラムの制御下で、キーボードやマウス、タッチパネル、ディスプレイ、ネットワークインターフェース等の入出力装置とのやりとりを制御する。
【００３０】
ただし、本発明に係る動画処理装置は、プログラムを実行するコンピュータにより実現されるものに限られない。たとえば、画像処理用の専用の電子回路やＦＰＧＡ（Field Programmable Gate array）、ＤＳＰ（Digital Signal Processor）等を利用すれば、同様の機能を実現することが可能である。
【００３１】
なお、３次元グラフィックスの分野では、オブジェクト同士の干渉を、衝突と呼ぶこともある。日常的な語法では、衝突とは、物体が激しくぶつかり、互いの表面が接触して、場合によっては物体の形状が変形することを意味するが、オブジェクトの干渉、あるいは、オブジェクトの衝突といった場合には、表面が接触することのほか、オブジェクトが占める３次元空間内の領域が食い込んだり貫通したりするような場合、オブジェクトが離間してはいるものの、その距離が十分に近い場合等を含む。以下の実施例では、理解を容易にするため、「干渉」という用語にかえて、適宜「衝突」という用語を用いる。
【００３２】
（２.５次元動画とオブジェクトの関係）
以下では、理解を容易にするため、２.５次元動画に描かれるオブジェクトを表現するための記法について整理する。図１は、２.５次元動画に描かれるオブジェクトとその諸元の関係を表す説明図である。以下、本図を参照して説明する。
【００３３】
なお、以下の説明では、理解を容易にするため、「２.５次元動画」を適宜「動画」と略記する。
【００３４】
ある動画Xに含まれるフレームのうち、再生の開始時点からの経過時間t（典型的には、フレーム番号で表現される。）に再生されるフレームをX(t)と表記する。
【００３５】
各フレームに固定された画素座標系において、フレームX(t)において、水平方向の座標値x、垂直方向の座標値yに配置される画素をX(t)[x,y]と表記する。
【００３６】
水平方向の座標値xならびに垂直方向の座標値yが動画Xの各フレームにおいて有効な値であることを、[x,y]∈Xと表記する。すなわち、[x,y]は、画素の位置を意味する。
【００３７】
図１は、３次元グラフィックス技術を用いて、仮想空間内にオブジェクトが配置される様子を動画のフレームに描く状況を真横から見て図示したものであるが、現実世界をカメラで撮影する場合も、同様の状況が成立する、と考えることができる。
【００３８】
本図に示すように、空間内では、撮影点１１から、投影面１２上に配置されたフレームX(t)内の画素X(t)[x,y]に向かう半直線１３がオブジェクト１４の表面の衝突点１５でぶつかるとき、画素X(t)[x,y]には、当該ぶつかった衝突点１５の様子が描かれる。これが一般的な透視投影である。
【００３９】
上記のように、本図は撮影の様子を真横から見たものである。したがって、本図では、投影面１２は直線により表現されることになる。
【００４０】
撮影点１１は、カメラの位置や観察位置に相当するものであり、撮影点１１と投影面１２との距離は、レンズの焦点距離や画素の長さの単位によって決まる。また、撮影方向１６は、撮影点１１から投影面１２に垂らした垂線の方向である。
【００４１】
以下では、画素X(t)[x,y]の色彩ならびに前面奥行を、それぞれ、X(t)[x,y].colorならびにX(t)[x,y].foreと表記する。
【００４２】
X(t)[x,y].colorは、衝突点１５における色彩やライティングの状況、撮影点１１と衝突点１５の距離等に基づいて定まる。X(t)[x,y].colorは、ＲＧＢ、ＣＹＭＫ、ＨＳＶなどの各種の色空間における座標値を表すもので、色空間の間での座標値の変換は定式化されている。また、透明度を表すα値をX(t)[x,y].colorに追加することとしても良い。
【００４３】
X(t)[x,y].foreは、画素X(t)[x,y]に描かれているオブジェクト１４の衝突点１５に当る部分と、撮影点１１と、の間の奥行距離を表す。奥行距離としては、撮影点１１から衝突点１５までのベクトルの撮影方向１６の成分の長さ１７（いわゆる「Ｚ距離」に相当する。）を採用するのが一般的であるが、その近似値として、撮影点１１から衝突点１５までの距離を採用しても良い。
【００４４】
奥行距離は種々の単位系で表現が可能である。画素が正方形により構成されている場合に、当該画素の辺の長さを単位とすると、複数の動画における奥行の正規化が可能となる。以下では、奥行は正規化がされていることを前提に説明する。
【００４５】
一般には、動画Xには、移動するオブジェクトのほか、背景も描画されていることがある。背景は、ほとんど移動しないオブジェクトと考えることができる。
【００４６】
そこで、特許文献１に開示される技術などを利用して動画の各フレームを分析すれば、画素X(t)[x,y]には背景が描かれているのか、それとも、移動するオブジェクトが描かれているのか、を識別することができる。
【００４７】
以下では、理解を容易にするため、識別されたオブジェクトには識別番号が振られるものとする。背景を表すオブジェクトの識別番号は0、それ以外のオブジェクトの識別番号は1，2，3，…のように割り振るものとする。
【００４８】
さらに、画素X(t)[x,y]に部分が描かれているオブジェクトの識別番号を、X(t)[x,y].idと表記し、動画Xに出現するオブジェクトの識別番号の最大値をX.maxidと表記する。
【００４９】
動画Xに出現するオブジェクトの識別番号が0，1，2，3，…，Nであれば、X.maxid = Nである。
【００５０】
動画Xにおいて、X(t)[x,y].id≠0を満たす画素X(t)[x,y]のみを抽出すれば、オブジェクトのみの情報（背景を除去した情報）が得られることになる。また、i番目のオブジェクトのみの動画を得るには、X(t)[x,y].id=iを満たす画素X(t)[x,y]のみを抽出すれば良い。これらは、従来の動画技術におけるブルーバックを利用したクロマキー合成用の動画に相当するものである。
【００５１】
ここで、上記のような抽出を行った結果、処理の対象とならなくなった画素には、理解を容易にするため、識別番号として負の値が与えられるものとする。すなわち、X(t)[x,y].id<0であれば、画素X(t)[x,y]は、透明な画素と解釈される。ここでいう「透明」とは、クロマキー合成の際のブルーバックに相当するものである。
【００５２】
この解釈に基づけば、[x,y]∈Xが成立しない場合に、X(t)[x,y].idとして負の値が設定される、と考えることもできる。以下、理解を容易にするため、処理の対象とならない画素や、動画のフレーム外の位置における「画素」については、.idとして負の値が設定されるものとして説明を続ける。
【００５３】
（２.５次元動画に対する各種の変換）
以下では、ある動画から、別の動画を生成するための変換手法について説明する。このような変換手法には、以下のようなものがある。
（１）動画のフレームに沿った上下左右の平行移動
（２）動画の拡大縮小
（３）動画の奥行方向の平行移動
（４）動画の水平軸、垂直軸、奥行軸周りの回転
（５）動画の時間方向の移動
（６）動画から特定のオブジェクトのみを選択
（７）ある動画に別の動画を重ねる合成
以下、順に説明する。
【００５４】
まず、動画のフレームに沿った上下左右の平行移動について考える。動画Yが、動画Xをフレーム内で水平方向にp、垂直方向にqだけ平行移動することによって得られるものであれば、
Y(t)[x+p,y+q] = X(t)[x,y]
ならびに、
Y(t)[x,y] = X(t)[x-p,y-q]
が成立する。ここで、上記の等号は、.colorや.foreなど、各画素に割り当てられた値が、いずれも互いに等しいことを意味する。
【００５５】
以下、動画Xをフレーム内で水平方向にp、垂直方向にqだけ平行移動することにより得られる動画をmove(p,q,X)と表記する。
【００５６】
次に、動画の拡大縮小について考える。透視投影においては、c倍に大きく描かれる、ということは、奥行が1/c倍になって撮影点が近くなった、ということを意味する。したがって、動画Yが、動画Xをフレーム内でc倍に拡大したものであれば、各画素に割り当てられた.fore以外については、
Y(t)[c×x,c×y] = X(t)[x,y]
すなわち
Y(t)[x,y] = X(t)[x/c,y/c]
が成立する。
【００５７】
また、各画素に割り当てられた.foreについては、
Y(t)[c×x,c×y].fore = X(t)[x,y].fore/c
すなわち
Y(t)[x,y].fore = X(t)[x/c,y/c].fore/c
が成立する。
【００５８】
以下、動画Xをフレーム内でc倍に拡大することにより得られる動画を、scale(c,X)と表記する。
【００５９】
ついで、動画の奥行方向の移動について考える。動画Yが、動画Xに撮影されたものを奥行方向rだけ遠ざけると、X(t)[x,y]の奥行距離は、X(t)[x,y].foreからX(t)[x,y].fore + rに変化する。すなわち、奥行距離は、(X(t)[x,y].fore + r)/X(t)[x,y].fore = k倍になる。
【００６０】
透視投影において、撮影点との距離がk倍になったのであれば、投影面に描画されるサイズは、1/k倍に拡縮される。したがって、各画素に割り当てられた.fore以外については、
Y(t)[x/k,y/k] = X(t)[x,y]
が成立し、.foreについては、
Y(t)[x/k,y/k].fore = X(t)[x,y].fore + r
が成立する。
【００６１】
以下、動画Xを奥行方向にrだけ移動することにより得られる動画を、push(r,X)と表記する。
【００６２】
さらに、動画の水平軸、垂直軸、奥行軸周りの回転について考える。動画Yが、動画Xを水平軸周りにθだけ回転して得られるものであれば、.fore以外の要素について、
Y(t)[x,y] = X(t)[x,X(t)[x,y].fore×cosθ-y×sinθ]
とし、.foreについて、
Y(t)[x,y].fore = X(t)[x,y].fore×sinθ+y×cosθ
が成立する。
【００６３】
同様に、動画Yが、動画Xを垂直軸周りにφだけ回転して得られるものであれば、.fore以外の要素について、
Y(t)[x,y] = X(t)[X(t)[x,y].fore×cosφ-x×sinφ,y]
とし、.foreについて、
Y(t)[x,y].fore = X(t)[x,y].fore×sinφ+x×cosφ
が成立する。
【００６４】
また、動画Yが、動画Xを奥行軸周りにψだけ回転して得られるものであれば、
Y(t)[x,y] = X(t)[x×cosψ-y×sinψ,x×sinψ+y×cosψ]
が成立する。
【００６５】
以下、それぞれの回転により得られる動画を、rothor(θ,X)、rotver(φ,X)、rotdep(ψ,X)のように表記する。
【００６６】
なお、これらの変換を行う場合においては、画素の座標値が整数値でなくなったり、座標値に抜けが生じることがある。このような場合には、各画素に割り当てられた.colorや.fore等の値を補間して、アンチエイリアスを行うこととし、.idについては、当該座標に最も近い格子点における値を採用する等の手法を採用することができるほか、.idが変化する境界がどこに位置するか、を補間により調べて、その境界に基づいて、.idを決定すれば良い。
【００６７】
平行移動等によって動画のフレームの範囲外となる画素は、透明な画素と考えれば良いから、上記のように、.idを負の値に設定すれば良い。
【００６８】
ついで、動画の時間方向の移動について考える。動画Yが、動画Xの時間をdだけずらしたものであれば、
Y(t)[x,y] = X(t-d)[x,y]
が成立する。
【００６９】
以下、動画Xの時間をdだけずらした動画をshift(d,X)と表記する。
【００７０】
さらに、動画から特定のオブジェクトのみを選択する処理について考える。動画Yが、動画Xに識別番号i番目のオブジェクトのみを描くものであれば、.id以外の要素について、
Y(t)[x,y] = X(t)[x,y]，  if X(t)[x,y].id = i；
が成立する。また、.idについては、
Y(t)[x,y].id = 1，  if X(t)[x,y].id = iかつi>0；
Y(t)[x,y].id = 0，  if X(t)[x,y].id = iかつi=0；
Y(t)[x,y].id = -1， otherwise
とすれば、動画Yにおける識別番号の最大値Y.maxidをできるだけ小さくすることができる。
【００７１】
以下、動画Xに描かれた識別番号iのオブジェクトのみを描く動画を、select(i,X)と表記する。
【００７２】
最後に、ある動画に別の動画を重ねる（superimpose）処理について考える。動画X，Yに描かれているオブジェクトに衝突がなければ、動画X（背景を含んでいても良いし、背景以外のオブジェクトのみでも良い。）に、動画Yの背景以外のオブジェクトを重ねることにより、動画Xに描かれたオブジェクトと、動画Yに描かれたオブジェクトと、を１つにまとめた動画Zが得られる。
【００７３】
動画Zでは、.id以外については、
Z(t)[x,y] = X(t)[x,y]，  if Y(t)[x,y].id≦0；
Z(t)[x,y] = X(t)[x,y]，  if X(t)[x,y].fore<Y(t)[x,y].fore；
Z(t)[x,y] = Y(t)[x,y]，  otherwise
が成立する。また、.idについては、
Z(t)[x,y].id = X(t)[x,y].id，  if Y(t)[x,y].id≦0；
Z(t)[x,y].id = X(t)[x,y].id，  if X(t)[x,y].fore<Y(t)[x,y].fore；
Z(t)[x,y].id = Y(t)[x,y].id+X.maxid，  otherwise
とすれば、オブジェクトの識別番号の重複を避けることができる。
【００７４】
また、整数1，2，…，Z.maxidのうち、Z(t)[x,y].idの値として出現しないものがあれば、以降のオブジェクトの.idをずらすことによって、Z.maxidを最小化することも可能である。
【００７５】
以下、動画Xに、動画Yの背景以外のオブジェクトを重ねることにより得られる動画を、superimpose(Y,X)と表記する。
【００７６】
上記のmove，scale，push, rothor，rotver，rotdep，select，superimpose等の処理をコンピュータで行う際には、ＣＰＵ(Central Processing Unit)が有する計算機能を用いる他、グラフィックス処理用のプロセッサを利用する等により、高速な計算が可能である。
【００７７】
なお、scale，pushにおいては、原点を中心に拡縮や奥行の移動を考え、rothor，rotver，rotdepおいては、回転軸が原点を通ることを前提としている。
【００７８】
したがって、画像X内の任意の位置[p,q]を中心に拡縮や奥行の移動を行いたい場合には、一旦[p,q]を原点に上下左右に移動し、拡縮や奥行移動を行ってから、逆の上下左右の移動を行えば良い。すなわち、
move(p,q，scale(c，move(-p,-q，X)))；
move(p,q，push(r，move(-p,-q，X)))
などを利用すれば良い。
【００７９】
回転軸の位置を上下左右や奥行方向にずらしたい場合も、同様に、一旦回転軸が原点を通るように上下左右や奥行の移動をしてから、回転を行い、その後に、逆の上下左右や奥行の移動を行うことになる。
【００８０】
このほか、scaleやpush等、奥行が移動される変換においては、その度合に応じて.colorの明度や彩度などの修正することとしても良い。
【００８１】
なお、動画の正規化は、撮影時の設定等に基づいて行うことも可能であるが、ユーザの希望に応じて設定をしたり、自動的に行ったりすることも可能である。
【００８２】
ユーザの設定による場合には、まず、ユーザの指示等に基づいて動画の高さや幅を単純に拡縮したり、解像度を調整することで画像内に描かれるオブジェクトの大きさを所望のものとする。scaleでは、対応する画素の奥行距離に、拡大率に応じた係数を乗じるが、正規化の際には、対応する画素の奥行距離をそのまま用いる。
【００８３】
その後に、ユーザは係数を選択し、各画素の奥行距離を一括して当該係数倍にする。
【００８４】
なお、動画Xにオブジェクトiが描かれ、動画Yにオブジェクトjが描かれている状況で、オブジェクトiとオブジェクトjが一緒に描かれるような動画Zを生成しようとする場合には、オブジェクトiの大きさと、オブジェクトjの大きさと、が、ほぼ等しく、オブジェクトiの奥行と、オブジェクトjの奥行と、が、ほぼ等しくなるようにすることが望ましいことが多い。このような前提が成立する場合には、自動的な正規化も可能である。
【００８５】
すなわち、動画Yにおいてオブジェクトjが描かれている領域の平均面積や平均高さ等が、動画Xにおけるオブジェクトiの対応する値と一致するように、動画Yを単純拡縮して動画Zを得る。すなわち、.foreを含むすべての値について、
Z(t)[x,y] = Y(t)[x/c,y/c]
とする。
【００８６】
そして、動画Zにおけるオブジェクトjの平均奥行と動画Xにおけるオブジェクトiの平均奥行とが一致するように、動画Zにおける奥行を一括して係数倍して、動画Wを得る。すなわち、.fore以外については、
W(t)[x,y] = Z(t)[x,y]
とし、.foreについては、
W(t)[x,y].fore = k×Z(t)[x,y].fore
とする。
【００８７】
上記の条件を満たすようにcやkを、自動設定すれば、動画Wは、オブジェクトjがオブジェクトiに見合うように、動画Yを正規化したものとなる。もちろん、上述の通り、cやkをユーザの希望に応じて設定することによって、正規化を行うこととしても良い。
【００８８】
以上、動画の種々の特徴量の表記や各種の変換について説明したが、これらの表記、変換は理解を容易にするためのものである。特に、.colorや.fore、.idなどは、他のフォーマットによって表現することも可能である。動画処理に用いられる種々のフォーマットにおいて、これと等価な形式や変換を採用した場合にも、本発明の技術的範囲に含まれることは言うまでもない。
【実施例１】
【００８９】
本実施例は、動画Xに動画Yを重ねたときに、動画Xにおける識別番号iのオブジェクトiと、動画Yにおける識別番号jのオブジェクトjと、が衝突するか否かを判定するものである。【００９０】
オブジェクトiと、オブジェクトjと、の衝突が比較的容易に判定できる場合としては、以下のような状況が考えられる。【００９１】
まず、オブジェクトiの前面（動画Xに描画されている表面）と、オブジェクトjの前面（動画Yに描画されている表面）と、が、同じ３次元位置を占める瞬間がある場合である。すなわち、いずれかのt,x,yにおいて、
X(t)[x,y].id = i；
Y(t)[x,y].id = j；
であれば、位置[x,y]は、オブジェクトiが描画されるべき領域ならびにオブジェクトjが描画されるべき領域の両方に重複して含まれることになる。【００９２】
この位置[x,y]において、
X(t)[x,y].fore = Y(t)[x,y].fore
が成立すれば、オブジェクトiとオブジェクトjが衝突する、と判定できる。【００９３】
この手法では、オブジェクトi，jオブジェクトjは、背面には何もないオブジェクトで、厚みを持たず、前面の形状のみからなる面状オブジェクトである、と、想定している。【００９４】
オブジェクトi，jの前面がある画素X(t)[x,y]に投影される位置で同じ奥行を有する、ということは、その位置でオブジェクトi，jの前面が重なっていることを意味する。そこで、この場合には、両者が衝突する、と判定することができる。【００９５】
この判定基準を時間方向に拡張することもできる。以下では、経過時間tがフレーム番号で表現される場合、すなわち、時刻t+1のフレームが時刻tのフレームに続く場合を想定する。【００９６】
すると、いずれかのt，x，yにおいて
X(t)[x,y].id = X(t+1)[x,y].id = i；
Y(t)[x,y].id = Y(t+1)[x,y].id = j；
X(t)[x,y].fore < Y(t)[x,y].fore；
X(t+1)[x,y].fore > Y(t+1)[x,y].fore
が成立すれば、時刻tから時刻t+1にかけてオブジェクトjがオブジェクトiの後から前にすり抜けて出てきた、と考えられる。また、
X(t)[x,y].id = X(t+1)[x,y].id = i；
Y(t)[x,y].id = Y(t+1)[x,y].id = j；
X(t)[x,y].fore > Y(t)[x,y].fore；
X(t+1)[x,y].fore < Y(t+1)[x,y].fore
が成立すれば、時刻tから時刻t+1にかけてオブジェクトiがオブジェクトjの後から前にすり抜けて出てきた、と考えられる。【００９７】
そこで、このような「すり抜け」が生じる場合には、オブジェクトの衝突が生じた、と判定する。【００９８】
これらの条件によるオブジェクトi，jの衝突判定では、オブジェクトi，jが、その前面のみの形状からなる、と想定している。オブジェクトが薄板状のオブジェクトである場合には、オブジェクトの厚みはゼロであり、オブジェクトの前面とオブジェクトの背面とが一致する、と考えることができる。したがって、これらの手法によって衝突判定を行うことにより、簡易かつ高速な判定が可能となる。【００９９】
図２Ａは、図１に示すオブジェクト１４の断面図であり、図２Ｂは、オブジェクト１４の前面を表す断面図である。以下、本図を参照して説明する。【０１００】
図２Ａに示す通り、オブジェクト１４は厚みを持ち、その断面には広がりがある。【０１０１】
しかしながら、２.５次元動画に含まれる情報によってオブジェクト１４を表現すると、図２Ｂに示す通り、その形状はオブジェクト１４の前面のみからなる面状オブジェクトとなってしまう。なお、本図は断面図であるから、面状オブジェクトは曲線により表現されている。【０１０２】
したがって、オブジェクト同士の衝突判定をより正確に行うためには、図２Ｂに示すような面状オブジェクトの情報から、オブジェクト１４の背面の形状を設定あるいは推定する必要がある。【０１０３】
ここで、オブジェクト１４の前面までの奥行は２.５次元動画に付随する情報により得られているから、オブジェクト１４の厚みを知るためには、オブジェクト１４の背面までの奥行が得られれば良い。【０１０４】
以下、動画Xにおいてある時刻tに画素X(t)[x,y]に描かれたオブジェクトの背面までの奥行を、X(t)[x,y].backと表記し、この背面奥行を取得する手法について説明する。【０１０５】
第１の手法は、各オブジェクトについて、前面と背面との距離をユーザがあらかじめ設定する、というものである。【０１０６】
すなわち、動画Xにおけるオブジェクトiについての前面と背面との距離（厚み）が定数thick(i)と設定されていれば、
X(t)[x,y].back = X(t)[x,y].fore + thick(X(t)[x,y].id)
とするものである。【０１０７】
図２Ｃは、厚みを一定とすることにより背面の形状を推定したオブジェクトの断面図である。本図に示す通り、オブジェクト１４の背面は、オブジェクト１４の前面を、撮影方向１６に平行移動した形状となっている。【０１０８】
このほか、オブジェクトiについての代表的な前面奥行を定め、これにthick(i)を加算したものを背面奥行とする、という手法がある。【０１０９】
ある時刻tにおけるオブジェクトiの代表的な前面奥行repfore(X,t,i)としては、以下のようなものが考えられる。
（１）オブジェクトiの前面奥行の最大値を採用する。
repfore(X,t,i) = maxx,y；X(t)[x,y].id=i X(t)[x,y].fore
（２）オブジェクトiの前面奥行の平均値を採用する。
repfore(X,t,i) = avgx,y；X(t)[x,y].id=i X(t)[x,y].fore【０１１０】
ここで、maxやavgは、その添字部分において、セミコロンの前に並べられた変数を、セミコロンの後に置かれた条件を満たす範囲で変化させたときの、本体部分の値の最大値や平均値を意味する。なお、条件として「常に成立する」を採用する場合には、変数のみを添字部分として表記する。【０１１１】
すなわち、上記（１）（２）では、与えられたX,t,iの下で、X(t)[x,y].id=iを満たすx,yの組み合わせを列挙し、その組み合わせのそれぞれについてX(t)[x,y].foreの値を求めて、その最大値や平均値を求めることになる。【０１１２】
このように定められたrepfore(X,t,i)を用いれば、画素X(t)[x,y]にオブジェクトiが描かれているとき（i = X(t)[x,y].id）の画素X(t)[x,y]の背面奥行は、
X(t)[x,y].back = repfore(X,t,i) + thick(i)
あるいは、
X(t)[x,y].back = max〔repfore(X,t,i) + thick(i)，X(t)[x,y].fore〕
のように定めることができる。ここで、max〔...〕は、括弧内に並べられた値の最大値を意味する。【０１１３】
図２Ｄは、オブジェクトの代表的な前面奥行を求め、これに厚みを加算したものを背面奥行とすることにより、オブジェクトの背面の形状を推定したオブジェクトの断面図である。本図に示す通り、オブジェクト１４の背面は、撮影方向１６に垂直な平面となっており、オブジェクト１４は、撮影方向１６に伸びる柱状の形状により近似されることになる。【０１１４】
このほか、時点tにおけるオブジェクトiの代表点を定め、当該代表点を中心とする球面により、背面を近似する手法もある。【０１１５】
まず、動画X内で時刻tにおいてオブジェクトiが描画されている領域の画素数area(X,t,i)を以下のように求める。
area(X,t,i) = Σx,y；X(t)[x,y].id=i 1
ここで、Σの添字は、maxやavgと同じ意味を有する。【０１１６】
時刻tにおけるオブジェクトiの代表点の水平座標xc(X,t,i)および垂直座標yc(X,t,i)は、以下のように定められる。
xc(X,t,i) = Σx,y；X(t)[x,y].id=i x/area(X,t,i)；
yc(X,t,i) = Σx,y；X(t)[x,y].id=i y/area(X,t,i)【０１１７】
また、動画X内で時刻tにおいてオブジェクトiが描画されている領域の幅w(X,t,i)および高さh(X,t,i)は、以下のように定められる。
w(X,t,i) = maxx,y；X(t)[x,y].id=i x - minx,y；X(t)[x,y].id=i x；
h(X,t,i) = maxx,y；X(t)[x,y].id=i y - minx,y；X(t)[x,y].id=i y【０１１８】
球面の直径D(X,t,i)は、たとえば、以下のような、種々の定め方がありうる。
D(X,t,i) = max〔w(X,t,i),h(X,t,i)〕；
D(X,t,i) = (w(X,t,i)2+h(X,t,i)2）1/2；
D(X,t,i) = area(X,t,i)1/2；
D(X,t,i) = maxx,y；X(t)[x,y].id=i ((x-xc(X,t,i))2+(y-yc(X,t,i))2)1/2；
D(X,t,i) = avgt area(X,t,i)3/2/area(X,t,i)【０１１９】
なお、avgt area(X,t,i)は、動画Xにおいてオブジェクトiが描かれている領域の時間平均を意味する。したがって、avgt area(X,t,i)3/2は、オブジェクトiが占める体積の推定値に相当し、これをarea(X,t,i)で割ることで、奥行長の推定値が得られることになる。【０１２０】
さて、直径D(X,t,i)が定まれば、代表点の奥行座標zc(X,t,i)は、以下のように定めることができる。
zc(X,t,i) = X(t)[xc(X,t,i),yc(X,t,i)].fore + D(X,t,i)/2【０１２１】
このほか、単純に以下のように定めても良い。
zc(X,t,i) = X(t)[xc(X,t,i),yc(X,t,i)].fore【０１２２】
すると、画素X(t)[x,y]にオブジェクトiが描かれているとき（i = X(t)[x,y].id）の画素X(t)[x,y]の背面奥行は、
X(t)[x,y].back = max〔zc(X,t,i)+〔max〔(D(X,t,i)/2)2-(x-xc(X,t,i))2-(y-yc(X,t,i))2〕，0〕1/2，X(t)[x,y].fore〕
のように定めれば、球面により近似したことになるし、
X(t)[x,y].back = max〔zc(X,t,i)+D，X(t)[x,y].fore〕
のように定めれば、円柱により近似したことになる。【０１２３】
図２Ｅは、オブジェクトの背面の形状を球面と推定したオブジェクトの断面図である。本図に示す例では、オブジェクト１４の背面は、代表点２１を中心とする球面となっているが、オブジェクト１４の前面から球面までは、撮影方向１６に伸びる柱状の形状により近似されている。【０１２４】
ここまでは、移動するオブジェクトの背面奥行を設定、推定する手法について説明したが、背景に相当するオブジェクトについては、背面奥行は、∞と考えれば良い。すなわち、
X(t)[x,y].id = 0
が成立する場合には、
X(t)[x,y].back = ∞
とする。【０１２５】
さて、時刻tにおける動画X内の画素X(t)[x,y]に描かれるオブジェクトX(t)[x,y].idが画素X(t)[x,y]において占有する奥行方向の占有区間は、前面奥行X(t)[x,y].foreから背面奥行X(t)[x,y].backまでとなる。【０１２６】
ここで、同じ画素位置に描かれる２つのオブジェクトの前面奥行から背面奥行までの占有区間に重複があれば、当該２つのオブジェクトは衝突していることになる。【０１２７】
したがって、いずれかのt,x,yにおいて、
X(t)[x,y].id = i；
Y(t)[x,y].id = j
であり、かつ、
（１）X(t)[x,y].fore≦Y(t)[x,y].fore≦X(t)[x,y].back；
（２）X(t)[x,y].fore≦Y(t)[x,y].back≦X(t)[x,y].back；
（３）Y(t)[x,y].fore≦X(t)[x,y].fore≦Y(t)[x,y].back；
（４）Y(t)[x,y].fore≦X(t)[x,y].back≦Y(t)[x,y].back
の４つのいずれか少なくとも１つが成立すれば、動画Xと動画Yを重ねたときに、動画Xに描かれるオブジェクトiと動画Yに描かれるオブジェクトjとが衝突する、と判定することができる。【０１２８】
以下、２つの占有区間の重複量を、overlap(X,Y,t,x,y)と表記することとする。上記（１）−（４）のいずれも成立しなければ、overlap(X,Y,t,x,y)=0であり、overlap(X,Y,t,x,y)>0であれば、オブジェクトi,jは衝突することになる。【０１２９】
具体的には、上記（１）の場合は、
overlap(X,Y,t,x,y) = min〔X(t)[x,y].back,Y(t)[x,y].back〕-Y(t)[x,y].fore
であり、上記（２）の場合は、
overlap(X,Y,t,x,y) = Y(t)[x,y].back-max〔X(t)[x,y].fore,Y(t)[x,y].fore〕
であり、上記（３）の場合は、
overlap(X,Y,t,x,y) = min〔X(t)[x,y].back,Y(t)[x,y].back〕-X(t)[x,y].fore
であり、上記（４）の場合は、
overlap(X,Y,t,x,y) = X(t)[x,y].back-max〔X(t)[x,y].fore,Y(t)[x,y].fore〕
である。ここで、min〔...〕は、max〔...〕とは逆に、括弧内の値の最小値を返す。【０１３０】
なお、上記（１）−（４）のいずれかが成立し、かつ、overlap(X,Y,t,x,y)=0の場合には、オブジェクトi,jは、離間しているのではなく、互いに接する、と考えることができる。したがって、互いに喰い込んでしまう衝突と、表面が接するだけの衝突と、を、区別して判定することも可能である。【０１３１】
このほか、衝突判定に、上記の占有区間そのものを用いるのではなく、その上限や下限にマージンを持たせて占有区間を少し広げてから、重複があるか否かを調べることとしても良い。この場合には、オブジェクトi,jの衝突判定にマージンを持たせたことになり、オブジェクトi,jは、ある程度の距離離れていなければ、衝突する（おそれがある）と判定されることになる。【０１３２】
一方で、上記のマージンを負にすれば、少々食い込むような衝突を許容できるようになる。これは、オブジェクトに弾性があり、凹むことが想定される場合等に好適である。【０１３３】
図３は、本実施形態に係る動画処理装置において、衝突判定を行う要素の概要構成を示す説明図である。以下、本図を参照して説明する。【０１３４】
本図に示すように、動画処理装置１０１のうち、衝突判定を行う要素は、背面奥行取得部１０２、および、衝突判定部１０３からなる。【０１３５】
動画処理装置１０１は、第１動画Xおよび第２動画Yを処理の対象とする。たとえば、
（ａ）第１動画Xとして、現実世界においてダンサーがダンスをしている様子を撮影した２.５次元画像を採用し、
（ｂ１）第２動画Yとして、キャラクターが無背景で踊っている様子を表す動画を採用したり、
（ｂ２）第２動画Yとして、他のユーザがダンスをしている様子を撮影した後に当該他のユーザが編集を行い、背景の情報をすべて除去して、当該他のユーザが無背景で踊っている様子を表す動画を採用する。
なお、本実施態様における動画処理装置１０１は、最終的には、ダンサーがキャラクタあるいは他のユーザと一緒に踊っている第３動画を合成する。【０１３６】
このため、まず、動画処理装置１０１は、第１動画Xに描かれた第１オブジェクトiと、第１動画Xに重ねられるべき第２動画Yに描かれた第２オブジェクトjと、の衝突を判定する。動画処理装置１０１は、典型的には、コンピュータでプログラムを実行することによって実現される。【０１３７】
ここで、第１動画Xは、第１動画Xに描かれている側の第１オブジェクトiの第１前面奥行を伴い、第２動画Yは、第２動画Yに描かれている側の第２オブジェクトjの第２前面奥行を伴う。【０１３８】
上記の表記を用いれば、第１動画Xに含まれる時刻tのフレームX(t)において位置[x,y]の画素に第１オブジェクトiが描かれていれば、X(t)[x,y].id = iであり、その第１前面奥行は、X(t)[x,y].foreである。【０１３９】
第１動画Xは、移動するオブジェクトのみからなるものとしても良いし、背景を含むものとしても良い。前者の場合には、第１オブジェクトとしてi>0のものを採用することになるし、後者の場合には、第１オブジェクトとしてi≧0のものを採用することになる。【０１４０】
また、第２動画Yに含まれる時刻tのフレームY(t)において位置[x,y]の画素に第２オブジェクトjが描かれていれば、Y(t)[x,y].id = jであり、その第２前面奥行は、Y(t)[x,y].foreである。【０１４１】
第２動画Yにおいて衝突判定の対象となるオブジェクトは、背景は含まないものとする。すなわち、第２オブジェクトとしては、j>0のものを採用することになる。【０１４２】
まず、背面奥行取得部１０２は、第１動画Xに描かれていない側の第１オブジェクトiの第１背面奥行と、第２動画Yに描かれていない側の第２オブジェクトjの第２背面奥行と、を取得する。【０１４３】
上記の表記を用いれば、背面奥行取得部１０２は、時刻t、位置[x,y]のうち、X(t)[x,y].id = iを満たすものについて、上記の手法により、第１背面奥行X(t)[x,y].backを求める。また、背面奥行取得部１０２は、時刻t、位置[x,y]のうち、Y(t)[x,y].id = jを満たすものについて、上記の手法により、第２背面奥行Y(t)[x,y].backを求める。【０１４４】
一方、衝突判定部１０３は、オブジェクト同士の干渉を判定する干渉判定部として機能する。そして、衝突判定部１０３は、第１動画Xと、第２動画Yと、が重ねられることによって、第１オブジェクトiが描かれるべき第１描画領域と、第２オブジェクトjが描かれるべき第２描画領域と、が重なり、かつ、第１描画領域と、第２描画領域と、が重なる重複領域において、第１オブジェクトiの第１前面奥行から第１背面奥行までの第１占有区間と、第２オブジェクトjの第２前面奥行から第２背面奥行までの第２占有区間と、が重なれば、第１オブジェクトと、第２オブジェクトと、が衝突する、と判定する。【０１４５】
上記の表記を用いれば、ある時刻tにおける第１描画領域とは、X(t)[x,y].id = iを満たす位置[x,y]の集合であり、ある時刻tにおける第２描画領域とは、Y(t)[x,y].id = jを満たす位置[x,y]の集合である。これらの集合の共通部分が空集合でなければ、時刻tにおいて、第１描画領域と、第２描画領域と、が重なることになり、これらの集合の共通部分が時刻tにおける重複領域に相当する。【０１４６】
時刻tにおける重複領域の要素である位置[x,y]については、明らかに
X(t)[x,y].id = i；
Y(t)[x,y].id = j
が成立する。【０１４７】
この位置[x,y]において、第１オブジェクトiは、奥行として、X(t)[x,y].foreからX(t)[x,y].backまでの第１占有区間を占有する。また、第１オブジェクトjは、Y(t)[x,y].foreからY(t)[x,y].backまでの第２占有区間を占有する。【０１４８】
第１占有区間と、第２占有区間と、が、重なる場合、すなわち、第１占有区間に第２前面奥行もしくは第２背面奥行が含まれ、または、第２占有区間に第１前面奥行もしくは第１背面奥行が含まれる場合には、時刻t、位置[x,y]において、第１オブジェクトiと、第２オブジェクトjと、は、衝突する、と判定されることになる。【０１４９】
上記の説明では、時刻tにおけるフレームにおいて、第１オブジェクトiが描かれる第１描画領域と、第２オブジェクトjが描かれる第２描画領域と、が重なれば、背面奥行の情報を利用して、当該時刻tにおけるフレームにおける第１オブジェクトiと第２オブジェクトjとの衝突判定を行うものとしている。【０１５０】
したがって、動画全体において衝突が生じないことを確認するためには、第１動画Xおよび第２動画Yの全フレームについて、順次tを設定して、上記の衝突判定を行うこととすればよい。【０１５１】
図４は、本実施形態に係る衝突判定処理の流れを示すフローチャートである。以下では、本図を参照して、本実施形態に係る動画処理装置１０１にて実行される衝突判定処理について説明する。【０１５２】
まず、動画処理装置１０１は、衝突判定の対象となる第１動画Xと第２動画Yとを受け付ける（ステップＳ１５１）。第１動画Xと第２動画Yにはオブジェクトが描かれており、オブジェクトの奥行情報が付随している。【０１５３】
ついで、第１動画Xおよび第２動画Yのフレームを先頭から順に走査する処理を繰り返す（ステップＳ１５２）。【０１５４】
すなわち、現在走査しているフレームにおいて、第１動画Xにおいてオブジェクトが描かれている領域と、第２動画Yにおいてオブジェクトが描かれている領域と、に、重なりがあるか否かを判定する（ステップＳ１５３）。重なりがなければ（ステップＳ１５３；Ｎｏ）、ステップＳ１５７に進んで、処理を繰り返す。【０１５５】
重なりがあれば（ステップＳ１５３；Ｙｅｓ）、当該描画領域に重なりがある第１動画X内のオブジェクト（上記の「第１オブジェクト」に相当する。）の奥行情報と、第２動画Y内のオブジェクト（上記の「第２オブジェクト」に相当する。）の奥行情報と、を、取得する（ステップＳ１５４）。【０１５６】
そして、当該奥行情報から得られるオブジェクトの占有区間に、重なりがあるか否かを判定する（ステップＳ１５５）。重なりがなければ、ステップＳ１５７に進んで、処理を繰り返す。【０１５７】
重なりがあれば（ステップＳ１５５；Ｙｅｓ）、第１動画Xに描かれたオブジェクトと、第２動画Yに描かれたオブジェクトと、が、衝突する旨の判定結果を出力して（ステップＳ１５６）、本処理を終了する。【０１５８】
ステップＳ１５２−Ｓ１５７の繰り返しが終了したら、第１動画Xに描かれたオブジェクトと、第２動画Yに描かれたオブジェクトと、が、衝突することはない旨の判定結果を出力して（ステップＳ１５８）、本処理を終了する。【０１５９】
なお、上記の説明では、理解を容易にするため、第１動画Xには第１オブジェクトだけが１つ描かれ、第２動画Yには第２オブジェクトだけが１つ描かれている状況を想定しているが、オブジェクトが複数となる場合には、各オブジェクトについて同様の処理を繰り返せば良い。【０１６０】
また、上記の説明では、全フレームについて、描画領域の重複ならびに奥行情報に基づく占有区間の重複の判定を行っているが、フレーム数が多い場合には、適宜間引きを行うことも可能である。【０１６１】
たとえば、当初は等間隔にスキップしながらフレームを選び、第１描画領域と第２描画領域が重なるかを判定し、重なる場合は、その前後でのフレームの間引きをやめる、という手法を採用すれば、動画全体の衝突判定に要する計算時間を節約することができる。【０１６２】
さて、一般に、「いずれかの時刻、いずれかの位置において、第１動画Xに描かれたいずれかのオブジェクトと、第２動画Yに描かれたいずれかのオブジェクトと、が、衝突する」と判定されなかった場合、すなわち、衝突が一切生じない場合には、第１動画Xに第２動画Yを重ねても、オブジェクトの前後関係に矛盾が生じることはない。したがって、第１動画Xに第２動画Yを重ねた第３動画superimpose(Y,X)を求めることができる。【０１６３】
一方、「いずれかの時刻、いずれかの位置において、第１動画Xに描かれたいずれかのオブジェクトと、第２動画Yに描かれたいずれかのオブジェクトと、が、衝突する」と判定された場合には、第１動画Xと第２動画Yとを重ねることはできない。したがって、以下に開示するような工夫が必要となる。
【実施例２】
【０１６４】
本実施例は、ユーザが、マウスを用いたドラッグアンドドロップ操作等により、第１動画Xに対して第２動画Yをずらしてから重ねる際のユーザインターフェースを工夫するものである。【０１６５】
本実施例では、理解を容易にするため、ユーザのドラッグアンドドロップ操作により、第１動画Xに対して第２動画Yをずらしてから重ねるための上下左右の平行移動量を指定する場合を想定する。ただし、本実施例の操作体系は、必ずしもドラッグアンドドロップに限られるものではなく、タッチスクリーンに対するスライド動作や、クリック操作を２回繰り返す操作等、種々の指示入力操作を採用することによってドラッグアンドドロップにかえることも可能である。【０１６６】
図５Ａは、ドラッグが開始される以前の画面の様子を示す説明図であり、図５Ｂは、ドラッグが開始される時点の画面の様子を示す説明図であり、図５Ｃは、ドラッグの途中の時点の画面の様子を示す説明図であり、図５Ｄは、ドロップがされた時点の画面の様子を示す説明図である。【０１６７】
また、図６は、動画処理装置１０１のドラッグアンドドロップ処理に係る部分の概要構成を示す説明図である。図７は、本実施例に係る動画処理装置１０１によって実行されるドラッグアンドドロップ処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。【０１６８】
本実施例に係るドラッグアンドドロップ処理では、動画処理装置１０１において、ずらし量設定部１０４、ならびに、動画生成部１０５が、ユーザのドラッグアンドドロップ操作に基づいて動作する。【０１６９】
動画処理装置１０１は、第１動画Xに対して第２動画Yをずらしてから重ねる際に、オブジェクトの位置関係が所定の位置条件を満たすようにするため、位置条件を満たすか否かを判定するための干渉判定部を備える。【０１７０】
ただし、本実施例では、位置条件として、オブジェクトの衝突が生じないことを採用するため、干渉判定部として、上記の衝突判定部１０３を採用して、その判定結果を利用している。本図では、なお、衝突判定部１０３に先立つ背面奥行取得部１０２は図示を省略している。【０１７１】
後述するように、位置条件として、オブジェクトが干渉しない、すなわち、干渉条件を満たさないことに加えて、さらに他の条件、たとえば、特定のオブジェクト同士がぎりぎりまで近接する等を設定することも可能である。上述の衝突判定部１０３による判定結果は、オブジェクトの干渉以外の位置関係を参照した位置条件の判定にも利用することができる。【０１７２】
また、本図に図示されている修正部１０６は省略可能な要素であり、その機能については、後続する実施例について説明する。【０１７３】
まず、動画処理装置１０１は、第１動画Xの代表的なフレームと、第２動画Yの代表的なフレームと、を、画面に表示する（ステップＳ１８１）。たとえば、図５Ａに示すように、画面４０１内には、第１動画Xのウィンドウ４１１と、第２動画Yのウィンドウ４１２と、カーソル４１３と、が表示される。【０１７４】
本図では、第１動画Xは背景付きの動画であり、ウィンドウ４１１の縁は実線で描かれている。一方、第２動画Yは背景なしの動画であり、ウィンドウ４１２の周縁は透明色で描かれ、その縁も点線で描かれている。なお、ウィンドウ４１２の縁は、必ずしも画面４０１に表示する必要はない。この場合には、ユーザには、あたかも、第２動画Y内に描かれた背景でないオブジェクトのみが、画面４０１に表示されているかのように見えることになる。【０１７５】
ついで、動画処理装置１０１は、ユーザによる第２動画Yのウィンドウ４１２内のクリック動作（ドラッグの開始）を受け付ける（ステップＳ１８２）。ここで、図５Ｂに示すように、ユーザがマウスを用いてカーソル４１３を移動させ、第２動画Y内の位置[s,t]をクリックしたとする。【０１７６】
さらに、動画処理装置は、ユーザによるドラッグが継続している間（ステップＳ１８３；Ｙｅｓ）、これに応じて、第２動画Yのウィンドウ４１２の表示位置を移動する（ステップＳ１８４）。たとえば、ユーザが、図５Ｃに示すように、クリックを維持したままカーソル４１３を移動させると、カーソル４１３が第２動画Y内の位置[s,t]を指したままとなるように、ウィンドウ４１２全体が移動される。【０１７７】
さて、ユーザが、図５Ｄに示すように、カーソル４１３を第１動画X内の位置[u,v]まで移動させて、クリックをやめ、ウィンドウ４１２をウィンドウ４１１にドロップしたとする。【０１７８】
すると、第１動画X内の位置[u,v]と、第２動画Y内の位置[s,t]と、が重なることになる。したがって、ユーザは、第２動画Yを、水平方向にu-s、垂直方向にv-tだけ移動するような変換を行ってから、第１動画Xに重ねようとしていると考えられる。【０１７９】
このように、ユーザによるドラッグが終わると（ステップＳ１８３；Ｎｏ）、動画処理装置１０１のずらし量設定部１０４は、ずらし量として、水平方向u-s、垂直方向v-tを設定する（ステップＳ１８５）。すなわち、動画処理装置１０１は、ユーザが、第１動画Xに対して、第２動画をフレームに平行に上下左右に移動することにより得られる動画move(u-s,v-t,Y)を、重ねようとしている、と解釈する。【０１８０】
そこで、動画処理装置１０１は、衝突判定部１０３を利用して、第１動画Xに描かれたオブジェクトと、第２動画Yをずらした中間動画move(u-s,v-t,Y)に描かれたオブジェクトと、が、いずれかのフレーム時刻、いずれかのフレーム内位置において衝突するか、それとも、衝突が一切生じないか、を判定する（ステップＳ１８６）。【０１８１】
図５Ｃに示すドロップ操作の結果、衝突が一切生じない場合（ステップＳ１８６；Ｎｏ）、動画処理装置１０１の動画生成部１０５は、合成により第３動画superimpose(move(u-s,v-t,Y),X)を出力して（ステップＳ１８７）、本処理を終了する。【０１８２】
このような構成により、ユーザは、動画Yに描かれたオブジェクトが動画X内のオブジェクトとは衝突しないように位置付けた第３動画を得ることができる。第３動画では、動画Yに描かれたオブジェクト同士の衝突が生じないから、オブジェクト同士が互いに噛み合ってしまうような不自然な描写を防止することができる。【０１８３】
一方、図５Ｃに示すドロップ操作をしたとしても、衝突が生じてしまう場合には（ステップＳ１８６；Ｙｅｓ）、動画処理装置１０１は、音声や振動、画面表示などで警告を発して（ステップＳ１８８）、本処理を終了し、新たな動画は出力しない。すなわち、ユーザの指示が適切であれば、第３動画が生成されるが、不適切であれば、警告が生じるのみで第３動画が生成されない。【０１８４】
なお、上記の各種の変換は、フレーム単位で行われる。したがって、ある動画に変換を施して別の動画を得る際に、全フレームに対するmove等の変換処理をまとめて行ってから、衝突判定等の他の計算処理を実行しても良いし、変換処理をデマンドドリブンに行う遅延評価を採用しても良い。【０１８５】
以降の実施例を含め、変換処理をデマンドドリブンに行うのであれば、あるフレームについての重複判定等を行う必要があって初めて、当該フレームについての変換が行われることになる。したがって、衝突が一切生じないという結論を得るためには、全フレームについての変換が必要であるが、動画の途中のフレームで衝突が判明した場合には、以降のフレームに対する変換処理は実行されない。【０１８６】
このほか、ドラッグアンドドロップによりずらし量を指定する手法では、ずらし量は、ドロップされた第２動画Y用のウィンドウ４１２の位置が、第１動画X用のウィンドウ４１１の位置に対してどれだけずれているか、により表現される。ただし、ずらし量は、第２動画Yに対して適用される量であるから、ずらし量の入力に際しては、第１動画Xとの対比は必須ではない。したがって、ユーザがキーボードを利用して直接数値を入力したり、マウスなどを利用して視覚的にずらし量を入力する手法を採用しても良い。【０１８７】
以下では、ユーザの指示が不適切である場合に、単に警告を発するのにかえて、自動調整を行う手法について説明する。
【実施例３】
【０１８８】
本実施形態は、ユーザから指定された第２動画Yの平行移動量では、第１動画Xのオブジェクトと第２動画Yのオブジェクトが衝突してしまう場合に、その衝突を避けたり、第２動画Yのオブジェクトが第１動画Xの床や天井に接しているかのように配置するための自動調整を行うものである。【０１８９】
この自動調整では、第２動画Yを上下左右に平行移動しては衝突が生じるかを判別する試行を少なくとも一回、多くの状況では複数回繰り返して実行する。この処理は、動画処理装置１０１の修正部１０６が行う。図８は、本実施例に係る自動調整処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。【０１９０】
一回の試行における上下左右の移動量は、水平方向Δp、垂直方向Δqで表記することとする。Δp,Δqに定数を採用した場合には、第２動画Yをあらかじめ設定された方向にずらしながら調整することになる。【０１９１】
理解を容易にするため、図５Ａ乃至図５Ｄと同様に、ユーザが第２動画Y内の位置[s,t]をクリックし、クリックを維持したまま第１動画X内の位置[u,v]までドラッグした後に、クリックをやめてドロップした場合を考える。【０１９２】
この場合、本実施例の動画処理装置１０１は、以下の処理を行う。【０１９３】
まず、動画処理装置１０１のずらし量設定部１０４は、変数pの初期値としてuを、変数qの初期値としてvを、それぞれ設定する（ステップＳ１９１）。これにより、水平方向のずらし量の初期値としてp-s = u-sが、垂直方向のずらし量の初期値としてq-t = v-tが、それぞれ設定されたことになｒｉ，ずらし量設定部１０４は、初期値設定部として機能する。【０１９４】
次に、動画処理装置１０１の衝突判定部１０３は、位置条件「第１動画Xと、設定されたずらし量だけ第２動画Yをずらした中間動画move(p-s,q-t,Y)と、の間でオブジェクト衝突が生じない」が成立するか否かを判定する（ステップＳ１９２）。【０１９５】
成立すれば（ステップＳ１９２；Ｙｅｓ）、動画生成部１０５は、合成により第３動画superimpose(move(p-s,q-t,Y),X)を出力して（ステップＳ１９３）、本処理を終了する。【０１９６】
一方、成立しなければ、修正部１０６は、変数pの値をΔpだけ増やし、変数qの値をΔqだけ増やす（ステップＳ１９４）。これにより、ずらし量が微小に更新される。【０１９７】
そして、動画Yの平行移動量(p-s,q-t)が大きくなりすぎた場合や、繰り返し回数が所定の閾値を超えた場合等、断念条件が満たされた場合には（ステップＳ１９５；Ｙｅｓ）、衝突が避けなれないと判断し、警告を発して（ステップＳ１９６）、本処理を終了する。【０１９８】
一方、断念条件が満たされず、繰り返しを継続する場合（ステップＳ１９５；Ｎｏ）、動画処理装置１０１の制御は、ステップＳ１９２に戻る。【０１９９】
さて、多くの動画の座標系では、垂直方向の座標値を大きくする方向は、画面下向きの方向に相当する。第２動画Yに描かれているオブジェクトを画面の下方向に移動させて配置するには、(Δp,Δq) = (0,1)と設定すれば良い。【０２００】
また、当初は、(Δp,Δq) = (0,1)に設定して、上記の自動調整処理を実行した結果、衝突が避けられないと判定された場合には、(Δp,Δq) = (0,-1)に再設定して、同様の自動調整処理を再度実行することとしても良い。【０２０１】
これは、まず、上から下へ移動しながら衝突が避けられる平行移動量を探し、見つからなければ、今度は、下から上へ移動しながら衝突が避けられる平行移動量を探すことに相当する。【０２０２】
さて、上記の説明では、干渉判定部として、単に衝突判定部１０３を採用している。これは、オブジェクト同士の位置関係について、オブジェクト衝突が生じない、という位置条件を課したことに相当する。しかしながら、衝突判定部１０３による判定結果を利用すれば、干渉判定部における位置条件として他の条件を採用することもできる。【０２０３】
たとえば、位置条件を『「第１動画Xと動画move(p-s,q-t,Y)との間でオブジェクト衝突が生じない」かつ「第１動画Xと動画move(p-s,q+1-t,Y)との間でオブジェクト衝突が生じる」』に変更することもできる。このように変更すると、第２動画Yに描かれたオブジェクトを第１動画Xに重ねる際に、第２動画Yに描かれたオブジェクトが地面にほぼ接するように位置合わせしたことになる。【０２０４】
また、位置条件を、『「第１動画Xと動画move(p-s,q-t,Y)との間でオブジェクト衝突が生じない」かつ「第１動画Xと動画move(p+Δp-s,q+Δq-t,Y)との間でオブジェクト衝突が生じる」』に変更することもできる。【０２０５】
この場合には、ある方向への平行移動量を探す際には、できるだけ先に進むように設定して、試行を繰り返すことになる。たとえば、上から下へ移動する際には、第２動画Yのオブジェクトが第１動画Xの床に接するまで移動することになり、下から上に移動する際には、第２動画Yのオブジェクトが第１動画Xの天井に接するまで移動することになる。【０２０６】
なお、第１動画Xに地面が描かれており、第２動画Yに平面上を移動するオブジェクトが描かれていて、第１動画Xにおけるカメラの地面に対する向きが第２動画Yにおけるカメラの平面に対する向きにほぼ一致する場合等には、上記の処理を行えば、第２動画Yに描かれたオブジェクトを第１動画Xに重ねる際に、第２動画Yに描かれたオブジェクトが地面にほぼ接するか、もしくは、地面から離間して浮くように位置合わせしたことになる。【０２０７】
ここで、第１動画Xに描かれているオブジェクトが地面や天井、壁などのように静止しているオブジェクトであることがわかっている場合がある。たとえば、事前にユーザがあるフレームにおいてオブジェクトを指定したことにより確定している場合、ユーザによる過去の編集履歴によりわかっている場合、第１動画Xの各フレームを対比することによりわかっている場合等である。【０２０８】
この場合には、位置条件を上記のように設定することは、合成されるオブジェクトが、３次元空間において占めることができる可動範囲を設定したことを意味する。すなわち、「オブジェクトは、衝突さえしなければ宙に浮いていても良い」「オブジェクトは、床や地面に接している」「オブジェクトは、天井に接している」など、３次元空間におけるオブジェクトの可動範囲の条件を課した動画合成を行うことができる。【０２０９】
さて、上記のように、(Δp,Δq)は、第２動画Yに描かれるオブジェクトの描画位置の変位を表すベクトルであり、この向きを設定することによって、移動方向や移動量を適宜変更することが可能である。【０２１０】
上記の態様では、第２動画Yをあらかじめ設定された方向に沿って移動してから第１動画Xに重ねることで、第１動画Xおよび第２動画Yに描かれたオブジェクトが互いに衝突しないような新たな動画を生成することとしており、動画Yの上下方向のみの平行移動を想定していた。【０２１１】
しかしながら、上記のような移動を行った後に、位置条件を満たしつつも、ずらし量とユーザに設定された初期値との相違が最小となるように、ずらし量を修正しても良い。この場合には、ユーザの指定に最も近いずらし量が採用されることになる。【０２１２】
また、(Δp,Δq)の方向として、第１オブジェクトの代表点と、第２オブジェクトの代表点と、の、ベクトル差を採用することもできる。この場合には、第２オブジェクトが、第１オブジェクトに近付く方向、もしくは、第１オブジェクトから遠ざかる方向に移動するような平行移動がなされることになる。【０２１３】
これらの手法をさらに進めて、評価関数を適切に定め、これを最小化することで、オブジェクトの衝突を避ける手法を採用しても良い。ここでは、オブジェクトが衝突するときの「衝突量」を最小化することを考える。【０２１４】
ここで、動画Xと動画Yとの衝突量を、動画Xと動画Yにおいて衝突するオブジェクトが描画されている衝突領域の面積の総和と考えると、当該衝突量は、
collision(Y,X) =Σt,x,y；X(t)[x,y].id≧0,Y(t)[x,y].id>0,overlap(X,Y,t,x,y)>0 1
によって計算が可能である。【０２１５】
また、衝突するオブジェクトが３次元空間において重複している体積の総和の推定量を衝突量とする場合には、
collision(Y,X) =Σt,x,y；X(t)[x,y].id≧0,Y(t)[x,y].id>0,overlap(X,Y,t,x,y)>0 overlap(X,Y,t,x,y)
を採用することができる。このように計算される衝突量を評価関数とする。【０２１６】
衝突量を最小化するには、未定変数の更新方向(Δp,Δq)をランダムウォーク、最急降下法、共役勾配法により定めたり、(Δp,Δq)の候補として、あらかじめ(1,0)，(0,1)，(-1,0)，(0,-1)等を用意し、それぞれを採用した場合の衝突量の変化を求め、衝突量が最も減少するものを選択することによって、p，q等、動画Yをずらす程度を表す変数の値の更新を繰り返せば良い。【０２１７】
たとえば、平行移動を行う場合には、s,t,u,vを上記のように定め、変数p,qの初期値をu,vとし、collision(move(p-s,q-t,Y),X)を最小化するp,qを求め、到達した最終点において、collision(move(p-s,q-t,Y),X)=0が成立すれば、オブジェクト同士の衝突を避けた平行移動量p-s,q-tを求めることができたことになる。【０２１８】
このほか、上下左右の平行移動のほか、奥行方向の平行移動や回転、拡大縮小、時間ずらしを任意に組み合わせても良い。【０２１９】
たとえば、上下左右と奥行方向の平行移動を組み合わせる場合には、s,t,u,vを上記のように定め、p,q,rの初期値をu,v,0とし、collision(push(r,move(p-s,q-t,Y)),X)を最小化するp,q,rを求める。【０２２０】
水平軸および垂直軸周りの回転と平行移動を組み合わせる場合には、s,t,u,vを上記のように定め、p,q,θ,φの初期値をu,v,0,0とし、collision(rotver(φ,rothor(θ,move(p-s,q-t,Y))),X)を最小化するp,q,θ,φを求める。【０２２１】
さて、極端な平行移動や回転が生じると、本来であればオブジェクトの背面の描画が必要となることがある。しかしながら、動画Yは２.５次元動画であるから、オブジェクトの背面の情報は持っていない。そこで、平行移動量p-s,q-t,rや回転量θ,φ,ψ等には、あらかじめ上限および下限を設けておくことで、動画Yのオブジェクトの移動が不自然に見えてしまうことを防止することができる。【０２２２】
このほか、できるだけずらし量を小さくするため、平行移動量p-s,q-t,rや回転量θ,φ,ψ等の変換パラメータの絶対値あるいは自乗値に所定の整定数を乗じた値と上記の衝突量とを加算した結果を、評価関数としつつ、衝突量が０になるまで、変換パラメータの更新を続ける、という手法もある。変換パラメータの初期値をユーザが指定した値とした場合には、変換パラメータの変位を評価関数に組み込めば、ユーザが指定した値にもっとも近いずらし量を見つけることも可能である。【０２２３】
さらに以下では、ユーザの指示により、奥行方向の平行移動量を調整するような態様を考える。【０２２４】
まず、奥行方向の平行移動量を0としたまま、上記の手法で、オブジェクトが床に接するようにp,qを選ぶ。その結果、第１動画Xに動画move(p-s,q-t,Y)を重ねた動画が得られたものとする。【０２２５】
この後、ユーザは、マウスのホイール操作等によって奥行方向の平行移動量rを指定する。【０２２６】
そして、条件『「第１動画Xと動画push(r，move(p-s,q-t,Y))との間でオブジェクトが衝突しない」かつ「第１動画Xと動画push(r，move(p-s,q+1-t,Y))との間でオブジェクトが衝突する」』が満たされるまで、上記の態様と同様に、(Δp,Δq)を用いて変数(p,q)の更新を繰り返す。【０２２７】
これらの態様を採用することにより、ユーザが指定した平行移動量だけ奥行移動をしつつも、オブジェクトは床に触れたままとした動画を生成することが可能となる。【０２２８】
なお、自動調整の際には、まず、第１動画Xと第２動画Y（あるいは、第２動画Yをユーザの指示にしたがってずらした動画）を合成した第３動画Zを生成してしまう態様を採用することもできる。この態様では、合成の際に、第３動画Zにおける各画素がいずれのオブジェクトに由来するものであるか、ならびに、あるオブジェクトが別のオブジェクトを隠して描画されたものであれば、当該隠されたオブジェクトの当該隠された領域における画素値と奥行情報を別途保存しておく。【０２２９】
そして、オブジェクトの衝突が生じないように、これらの保存した情報を参照しつつ、第３動画Zを修正するのである。なお、修正の際には、オブジェクトの奥行方向が変化することがありうる。この場合には、オブジェクトがフレーム内に描かれる際に拡縮を行うから、オブジェクトの外観の精度をできるだけ保つために、元の第２動画Yにおける画素情報を参照するのようにしても良い。【０２３０】
これらの態様は、上記の手法と比べると、情報の記憶手法を異なる態様とし、計算処理の順序の入れ換えを行っただけであり、その動作原理は実質的に同一であるとみなすことができる。【０２３１】
このほか、衝突量は、オブジェクト同士の食い込みの量を示すものと考えられるから、「オブジェクト同士がある程度食い込んでも良い」という条件を課して動画の合成を行うことも可能である。【０２３２】
さて、上記の種々の手法を採用したとしても、オブジェクトの衝突を避けられないことがある。このような場合には、以下に説明するような工夫が必要となる。
【実施例４】
【０２３３】
上記の実施例では、ユーザが動画Yのオブジェクトの上下左右の平行移動量を指定して動画Xに重ねようとして、オブジェクトの衝突が生じてしまう場合に、警告を発する態様（実施例２）と、自動的に平行移動量を調整する態様（実施例３）と、を説明した。【０２３４】
本実施例は、上記の実施例の両方に適用が可能なもので、ユーザがドロップ可能な領域、すなわち、ユーザのドロップ操作によってオブジェクトが衝突しない動画が生成されるようなドロップ位置からなる領域を、ユーザのドロップ操作の前に理解しやすく提示しようとするものである。【０２３５】
図９Ａは、ドラッグが開始される以前の画面の様子を示す説明図であり、図９Ｂは、ドラッグが開始される時点の画面の様子を示す説明図であり、図９Ｃは、ドラッグの途中の時点の画面の様子を示す説明図であり、図９Ｄは、ドロップがされた時点の画面の様子を示す説明図である。以下、これらの図を参照して説明する。【０２３６】
図１０は、ドロップ可能領域の強調表示処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。【０２３７】
まず、第２動画Yを水平方向、垂直方向にずらす際に採用可能な任意のずらし量の候補を添字とする配列FをＲＡＭ内に用意する（ステップＳ５０１）。なお、以下では添字として[ps,qt]を採用するが、ps,qtは、負の値をとることもありうる。すなわち、psは、第２動画Yの幅の符号を反転した値から第１動画Xの幅と第２動画Yの幅の和までの間の整数、qtは、第２動画Yの高さの符号を反転した値から第１動画Xの高さと第２動画Yの高さの和までの間の整数とすれば良い。【０２３８】
そして、第２動画Yに対して、採用可能なずらし量の候補[ps,qt]について（ステップＳ５０１）、第１動画Xと、第２動画Yをずらした中間動画move(ps,qt,Y)との間で、オブジェクトの衝突判定を行い（ステップＳ５０２）、配列Fの要素F[ps,qt]に衝突判定の結果を代入する（ステップＳ５０３）処理を繰り返す（ステップＳ５０４）。【０２３９】
この後、上記実施例と同様に、第１動画Xのウィンドウ４１１と、第２動画Yのウィンドウ４１２と、を画面に表示し（ステップＳ５０６）。ドラッグの開始を受け付ける（ステップＳ５０７）。【０２４０】
ここで、ユーザがマウスを用いて、第２動画Y内の位置[s,t]をクリックしてドラッグが開始されたとする。【０２４１】
ここで、第２動画Yの位置[s,t]が、第１動画X内の位置[p,q]にドロップされたとすると、第２動画Yをずらした中間動画は、move(p-s,q-t,Y)となる。【０２４２】
したがって、第１動画Xと、中間動画move(p-s,q-t,Y)と、の間で、オブジェクトが衝突するか否かは、配列の要素F[p-s,q-t]を参照すれば良い。【０２４３】
そこで、動画処理装置１０１は、第１動画X内の各位置[p,q]について（ステップＳ５０８）、F[p-s,q-t]の値に応じて、第１動画X内の各位置[p,q]の画素の色彩（彩度、明度、色相のいずれか、もしくは、これらの組み合わせ）を変化させる（ステップＳ５０９）処理を繰り返す（ステップＳ５１０）。【０２４４】
これにより、ユーザによるドロップが可能な領域と、不可能な領域と、が、区別され、一方が強調表示されることになる。【０２４５】
強調表示の手法としては、「強調表示すべき画素の色彩を変化させるが、それ以外の画素の色彩は変化させない」あるいは「強調表示すべき画素の色彩は変化させずに、それ以外の画素の色彩を変化させる」手法がありうる。【０２４６】
上記実施例におけるこの後は、ステップＳ１８３に進めば良い。【０２４７】
以下、実例を掲げて説明する。ドラッグを開始する前は、図９Ａに示す通り、ウィンドウ４１１には、第１動画Xがそのまま描かれている。【０２４８】
ドラッグが開始された瞬間に、動画処理装置は、ドロップが可能な領域を計算する。そして、図９Ｂに示すように、ウィンドウ４１１内のドロップ可能領域を強調表示する。本図では、強調表示はハッチングにより図示されている。【０２４９】
ユーザは、図９Ｃに示すように、カーソル４１３をドロップ可能領域内にドラッグしてから、図９Ｄに示すようにドロップ処理を行えば、オブジェクトが衝突しない第３動画が得られることになる。【０２５０】
上記の手法では、クリックをした後の強調表示の体感速度を向上させることができ、クリックをやり直した場合（図示せず）の再描画を高速に行うことができる。【０２５１】
ただし、十分な計算速度が実現できる場合には、ユーザのドラッグ操作が開始され、[s,t]が確定してから第１画像X内の任意の位置[p,q]について、ずらし量[p-s,q-t]に基づく衝突判定を行い、強調表示をすることとしても良い。【０２５２】
このように、本手法では、ユーザは、第２動画Yに対するドラッグを開始すると、第１動画Xのどこにドロップ操作を行えば新たな動画が得られるか、が、容易にわかる。【０２５３】
ここで、実施例３における平行移動量の自動調整は、ドロップ可能領域外にドロップがされてしまった場合に、ドロップ位置をドロップ可能領域内に修正することに相当する。【０２５４】
本実施例では、動画Xのフレーム内のすべての位置について、ドロップ可能か否かが判定されるから、本実施例を採用した場合には、ドロップ可能領域外にドロップがされてしまったら、「ドロップ可能領域内のうちそのドロップ位置から最も近い点」や、「ドロップ可能領域内の中心点」などに、ドロップ位置を修正するだけで、上下左右の平行移動量の自動調整が可能となる。【０２５５】
なお、ドロップ可能領域とドロップ可能領域外とを区切る境界に、ドロップ位置を修正する、ということは、第１動画のオブジェクトと、第２動画のオブジェクトと、が、互いに接触する瞬間があることを意味する。【０２５６】
したがって、オブジェクトができるだけ床に接するようにするには、ドロップ可能領域の下限にドロップ位置を修正すれば良い、と考えられる。【０２５７】
図９Ｅは、ドロップ後に、ドロップ位置の自動修正を行った様子を示す説明図である。本図に示すように、ウィンドウ４１２内の位置[s,t]は、ウィンドウ４１１内の位置[u,v]の下方の、ドロップ可能領域の下限に重なるように配置修正されている。【０２５８】
本実施例によれば、ユーザがドロップ可能な位置を容易に理解できるようになるとともに、ドロップできない位置にドロップをした場合であっても、すでに計算された情報を利用して、容易にドロップ位置を修正できるようになる。
【実施例５】
【０２５９】
動画Xに描かれるオブジェクトiの、３次元空間における代表点の座標は、上記のように、(xc(X,t,i),yc(X,t,i),zc(X,t,i))と表記することができる。これは時刻tによって変化する３次元の位置ベクトルpos[X,i](t)と見ることができる。【０２６０】
上記の実施例では、動画Yに描かれているオブジェクトjを動画Xに重ねようとする際に、オブジェクトjが動画Xに描かれているオブジェクトに衝突してしまう場合には、動画Yを上下左右や奥行方向に平行移動したり、回転したり、時間ずらしをした動画Wを得て、動画Xに重ねていた。【０２６１】
平行移動や回転等は、合同変換であるから、これらの変換のみを利用した場合には、オブジェクトjの軌跡である位置ベクトルpos[Y,j](t)と、位置ベクトルpos[W,j](t)と、は、向きや位置は異なるかもしれないが、形状は同じである。すなわち、軌跡を変形しない非変形変換が施されたため、軌跡pos[Y,j](t)と、軌跡pos[W,j](t)と、は、合同である。【０２６２】
図１１Ａは、軌跡pos[X,i](t)と軌跡pos[Y,j](t)の様子を示す説明図である。【０２６３】
図１１Ｂは、軌跡pos[X,i](t)と軌跡pos[W,j](t)の様子を示す説明図である。【０２６４】
これらの図では、横軸に各軌跡の水平方向の位置が、縦軸に時間の経過が図示されている。また、各軌跡には、そのオブジェクトの水平方向の広がりを示す細長い長方形が付してある。【０２６５】
図１１Ｂにおける軌跡pos[W,j](t)は、図１１Ａにおける軌跡pos[Y,j](t)を水平方向に移動したもので、両者の形状は合同である。【０２６６】
動画Xのオブジェクトiと、動画Yのオブジェクトjと、が、時刻Tにおいて衝突していれば、図１１Ａに示すように、軌跡pos[X,i](t)と軌跡pos[Y,i](t)は、時刻Tにおいて近接しており、オブジェクトの水平方向の広がりを表す長方形が重なることになる。【０２６７】
一方、動画Xのオブジェクトiと、動画Wのオブジェクトjと、の間では、衝突は生じない。したがって、図１１Ｂに示すように、オブジェクトの水平方向の広がりを表す長方形に重なりはない。【０２６８】
しかしながら、このような合同変換のみでは、衝突が避けられない場合もある。そこで、本実施例では、修正部１０６が、オブジェクトの軌跡を変形するような変形変換を動画に施すこととして、オブジェクト同士の衝突を防止する。【０２６９】
以下では、背景を持つ動画Xに描かれているオブジェクトiの軌跡pos[X,i](t)そのものは変形せず、動画Xに重ねられる動画Yに描かれたオブジェクトjの軌跡pos[Y,j](t)を変形する手法について説明する。【０２７０】
まず、軌跡を表す位置ベクトルpos[Y,j](t)が変形して位置ベクトルmorph(t)になったものとする。【０２７１】
以下では、.x，.y，.zを付加することによって、位置ベクトルの各座標値を表記する。【０２７２】
軌跡の変形によって、奥行は、morph(t).z/pos[Y,j](t).z倍になる。これは、時刻tにおいてオブジェクトjを動画Yのフレーム内でpos[Y,j](t).z/morph(t).z倍に拡大することを意味する。【０２７３】
また、時刻tにおいてオブジェクトjは、水平方向および垂直方向にも移動される。その移動量は、それぞれ、(morph(t).x-pos[Y,j](t).x)×pos[Y,j](t).z/morph(t).z，(morph(t).y-pos[Y,j](t).y)×pos[Y,j](t).z/morph(t).zである。【０２７４】
したがって、軌跡を変形した場合には、オブジェクトの選択、平行移動や拡大縮小を組み合わせることによって、あるオブジェクトの軌跡変形済みの動画を得ることができる。【０２７５】
軌跡の変形がオブジェクト同士の衝突を避けるように行われていれば、軌跡変形済みの動画を重ね合わせることで、複数の動画に描かれていたオブジェクト同士が衝突せずに移動する様子を描いた１つの動画を生成することが可能となる。【０２７６】
以下では、軌跡の変形の種々の手法について、説明する。【０２７７】
第１の手法は、overlap(X,Y,t,x,y)>0が成立している時刻tにおいて、動画Yに含まれるオブジェクトj=Y(t)[x,y].idの代表点の位置pos[Y,j](t)を、動画Xに含まれるオブジェクトi=X(t)[x,y].idの代表点の位置pos[X,i](t)から遠ざかる方向、あるいは、軌跡pos[Y,j](t)の主法線ベクトルの方向に移動するように、オブジェクトjの軌跡を変形する処理を、時間前後における変形の度合の変化が小さくなるように繰り返して、いずれの時刻においてもoverlap(X,Y,t,x,y)=0が成立するようにするものである。【０２７８】
図１２Ａ乃至図１２Ｄは、処理を繰り返すことによって、軌跡が次第に変形していく様子を示す説明図である。以下、本図を参照して説明する。【０２７９】
図１２Ａは、図１１Ａと同様に、軌跡pos[X,i](t)と、軌跡pos[Y,j](t)と、が、時刻Tで近接している。【０２８０】
そこで、図１２Ｂでは、衝突が生じないように、時刻Tにおけるオブジェクトjの位置を、修正している。【０２８１】
この修正量が大きかったため、図１２Ｃでは、時刻Tの前後T-1，T+1におけるオブジェクトjの位置を、図１２Ｂにおける修正量よりも小さい量だけ、修正している。【０２８２】
この修正量がまだ大きかったため、図１２Ｄでは、前回の修正の前後T-2,T+2におけるオブジェクトjの位置を、図１２Ｃにおける修正量よりも小さい量だけ、さらに修正している。【０２８３】
これで修正は十分となり、図１２Ｄに図示される軌跡が、最終的に得られた軌跡morph(t)に相当する。【０２８４】
なお、隣接するフレームに対して伝播させる修正量は、自身のフレームに対する修正量に０以上１未満の定数を乗ずることにより減衰させ、修正量が所定の閾値より小さくなったら、伝播を終了させれば良い。【０２８５】
なお、軌跡の変形の際には、上記のように時刻の前後に修正を伝播するのではなく、スプライン補間などを利用することで、滑らかな修正を行うこととしても良い。【０２８６】
また、本手法では、衝突量が最大の時点に達して上記のような修正ならびに修正量の伝播を行い、まだ衝突が生じていたら、同じ処理を繰り返すこととすれば、修正量および修正回数をできるだけ小さくすることができる。【０２８７】
第２の手法は、時刻tにおいて軌跡pos[Y,j](t)を変形する際に、軌跡の接ベクトル（速度ベクトルに相当する）の大きさは変化させず、主法線ベクトル（速度ベクトルに直交するベクトルで、速度ベクトルの向きを曲げようとする方向に相当する。）の大きさのみを変化させることとし、collision(Y,X)を最小化して０にするとともに、当該主法線ベクトルの大きさの変化の総和（典型的には自乗和）も最小化するという手法である。【０２８８】
図８は、衝突を避けるために、軌跡の特定部分において主法線ベクトルを調整した様子を示す説明図である。本図は、軌跡の形状をそのまま表すものである。【０２８９】
本図では、軌跡pox[X,i](t)が、軌跡pos[Y,j](t)と、時刻Tで衝突する。そこで、時刻Tの前後の調整区間T-a〜T+aで、衝突が生じないように、軌跡pos[Y,j](t)の曲がり方を調整して、修正後の軌跡morph(t)を得る。【０２９０】
軌跡pos[Y,j](t)と、軌跡morph(t)と、は、時刻T+a以降の形状は合同である。【０２９１】
第１の手法は、計算が簡易であるものの、動画によって表現されているオブジェクトjの動きと軌跡とのずれが大きくなってしまうことがあり、このときには、オブジェクトjが突然「ムーンウォーク」をしたかのように、見えてしまうことがある。【０２９２】
オブジェクトjが不自然が動きをしたか否かは、オブジェクトjの軌跡の接線ベクトルの大きさや向き、主法線ベクトルの大きさ（これは、軌跡の曲率に相当する値である。）や向きの変化が所定の閾値を超えたか否かによって判定することも可能である。【０２９３】
軌跡の変形によってオブジェクトの動きが不自然であると判断された場合には、その旨の警告を出力すれば、ユーザにとって利便性が高い。【０２９４】
なお、軌跡の変形処理の繰り返しにおいて、軌跡の変形量にあらかじめ上限を設定しておくこととしても良い。この場合には、オブジェクトの動きが不自然となることはないが、衝突を避けることができない可能性がある。【０２９５】
第２の手法は、計算は煩雑ではあるが、オブジェクトjの移動方向が微小に変化するのみであり、移動速度の大きさは変化しないので、「ムーンウォーク」は生じない。【０２９６】
動画Xに、オブジェクトiのほか、背景も描かれている場合には、オブジェクトiの軌跡を変化させると、背景とオブジェクトiの間に画素情報がない隙間が生じてしまうことがある。そこで、本実施形態では、動画Yに描かれているオブジェクトjの軌跡のみを変形することとしている。【０２９７】
しかしながら、動画Xに、背景が含まれない場合には、オブジェクトiとオブジェクトjが衝突する場合に、両方の軌跡を変形させても良い。第１の手法では、オブジェクトiとオブジェクトjとが互いに遠ざかる方向に移動させれば良いし、第２の手法では、オブジェクトiの軌跡の主法線ベクトルの変化量と、オブジェクトjの軌跡の主法線ベクトルの変化量と、の、両方を最小化すれば良い。【０２９８】
なお、本手法においても、主法線ベクトルの変化量に上限を設けるか、あるいは、主法線ベクトルの変化量が所定の閾値を超えた場合には警告を発するなどして、オブジェクトの不自然な動きを防止し、ユーザの利便性を向上させることができる。【０２９９】
本態様では、動画内に描かれたオブジェクトの単純な平行移動、回転、拡大縮小などでは衝突が避けられない場合であっても、軌跡を変形することによって、衝突を防止することができるようになる。【０３００】
なお、本実施例ならびに上記の実施例においては、オブジェクトの衝突を避けるための手法を開示している。しかしながら、所望の時点においてオブジェクトの表面の接触が生じる、という制約条件を課すことも可能である。【０３０１】
すなわち、所望の時点において、２つのオブジェクトが重なって描画される位置における当該２つのオブジェクトの前面奥行から背面奥行までの占有区間に重複があり、かつ、overlapが０である、という制約を課した上で、その制約を満たすようなオブジェクトの移動や軌跡の変形を行うことになる。【０３０２】
このほか、両動画X，Yに描かれるオブジェクトi，jの軌跡の両方を変形させることとしても良い。この場合には、オブジェクトi用の変形パラメータと、オブジェクトj用の変形パラメータと、を、まとめて取扱い、衝突量の最小化を図るような変形を行えば良い。
【実施例６】
【０３０３】
動画Yに描かれるオブジェクトjが、平面の上でダンスをするようなオブジェクトであり、動画Xにおける背景に床が含まれる場合には、オブジェクトjが動画Xの床の上でダンスをするように重ね合わせることが望ましい。本実施例は、これを実現するものである。【０３０４】
上記の実施例では、動画Xにおける地面に対するカメラの傾きと、動画Yにおける平面に対するカメラの傾きと、が一致する状況について説明したが、本実施例は、必ずしもこれらの一致を要しない。【０３０５】
まず、動画Yに描かれるオブジェクトjの代表点として、画面の最も下方に描かれている点を選択する。オブジェクトjがダンスをするキャラクターである場合には、ここで選択される代表点は、当該キャラクターの足先に相当する。【０３０６】
代表点の画素位置[xb(Y,t,j),yb(Y,t,j)]は、たとえば、以下のように計算することができる。
yb(Y,t,j) = minx,y；Y(t)[x,y].id=j y；
xb(Y,t,j) = minx；Y(t)[x,yb(Y,t,j)].id=j x【０３０７】
ここで、オブジェクトjの最下点と、動画Xの床とが接していれば、
X(t)[xb(Y,t,j),xb(Y,t,j)].id = 0；
Y(t)[xb(Y,t,j),xb(Y,t,j)].id = j；
X(t)[xb(Y,t,j),xb(Y,t,j)].fore = Y(t)[xb(Y,t,j),xb(Y,t,j)].fore
が成立するはずである。【０３０８】
したがって、collision(Y,X)を最小化して０にするとともに、X(t)[xb(Y,t,j),xb(Y,t,j)].foreとY(t)[xb(Y,t,j),xb(Y,t,j)].foreの差の総和（典型的には自乗和）も最小化するように、動画Yに対する上下左右ならびに奥行の平行移動量や各軸周りの回転量を定めれば、動画Yに描かれたオブジェクトjが、動画Xに描かれる床面に接するようになる。【０３０９】
なお、オブジェクトjがダンスの途中で床からジャンプした場合は、X(t)[xb(Y,t,j),xb(Y,t,j)].foreとY(t)[xb(Y,t,j),xb(Y,t,j)].foreを完全に一致させることはできないが、最小化を行うことで、ジャンプをしていない瞬間に床から離間してしまう状況は防止することができる。【０３１０】
また、最小化によって、できるだけ動画Yにおいてオブジェクトjが乗っていた床と、動画Xにおける床とを、できるだけ一致させて、動画Xに重ねられるオブジェクトjの振舞いをできるだけ自然にすることができる。
【実施例７】
【０３１１】
上記の実施例では、２.５次元動画に対する各種の変換において、一つのオブジェクト内の各位置および各奥行情報に情報に対して個別な計算処理を行って、これらをできるだけ反映させるような演算を行っていた。本実施例では、オブジェクトの代表点を利用して近似を行うことで、演算負荷をさらに小さくする。【０３１２】
すなわち、本実施例では、動画Xの時点tにおけるオブジェクトiの代表点の動画X内における座標(xc(X,t,i),yc(X,t,i))ならびに代表点の奥行座標zc(X,t,i)が計算される。【０３１３】
ここで、オブジェクトiは、全体としてひとまとまりの動きをするから、オブジェクトiの各部の奥行座標は、zc(X,t,i)で近似できる。したがって、代表点の奥行がzc(X,t,i)からzc(X,t,i)+rに変化するときに、各位置における奥行が〔zc(X,t,i)+r〕/zc(X,t,i)倍になった、と近似するのである。このような近似が効果的であるのは、動画の奥行方法の平行移動、水平軸、垂直軸周りの回転である。【０３１４】
具体的には、平行移動や水平軸、垂直軸周りの回転の対象となるオブジェクトiの代表点のみの移動先を、上記の実施例と同様の演算により求める。そして、その移動先を中心に、代表点の奥行の変化に応じて動画を拡大縮小して配置することで、上記の演算を簡略化する。【０３１５】
本実施例における変換では、オブジェクトiの形状を、奥行方向に垂直な板の表面に絵が描かれた物体と仮定して、奥行方法の平行移動や水平軸、垂直軸周りの回転がされた場合であっても、この板を奥行方向に垂直なまま移動することに相当する。【０３１６】
奥行方向の平行移動では、板は奥行方向に垂直なままである。本実施例では、水平軸、垂直軸周りの回転角に上限を設けることにより、回転角は数度程度までとして、板の位置は回転によって変化させるが、板の向きは奥行方向に垂直なままと考える。【０３１７】
以下、具体的な変換の演算について説明する。【０３１８】
動画Xに描かれたオブジェクトiを奥行方向にrだけ移動することにより得られる動画は、以下の処理を行うことによって得られる。
（ａ）動画Xからオブジェクトiのみを選択し、
（ｂ）フレームに沿って(xc(X,t,i),yc(X,t,i))が原点になるように平行移動し、
（ｃ）zc(X,t,i)/〔zc(X,t,i)+r〕倍に動画を拡大縮小し、
（ｄ）フレームに沿って原点が(xc(X,t,i),yc(X,t,i))になるように平行移動する。【０３１９】
したがって、動画Xに描かれたオブジェクトiを奥行方向にrだけ移動する変換をpush'(i,r,X)と標記すると、
push'(i,r,X) = move(xc(X,t,i),yc(X,t,i),
scale(zc(X,t,i)/〔zc(X,t,i)+r〕,
move(-xc(X,t,i),-yc(X,t,i),
select(i,X))))
となる。【０３２０】
また、動画Xに描かれたオブジェクトiを水平軸周りにθだけ回転すると、オブジェクトの代表点の動画内における座標は、(xc(X,t,i),yc(X,t,i))から(xc(X,t,i),zc(X,t,i)×cosθ-yc(X,t,i)×sinθ)へ移動し、奥行は、zc(X,t,i)からzc(X,t,i)×sinθ+yc(X,t,i)×cosθへ移動する。すなわち、以下の処理を行えば良い。
（ａ）動画Xからオブジェクトiのみを選択し、
（ｂ）フレームに沿って(xc(X,t,i),yc(X,t,i))を(xc(X,t,i),zc(X,t,i)×cosθ-yc(X,t,i)×sinθ)へ移動し、
（ｃ）zc(X,t,i)/〔zc(X,t,i)×sinθ+yc(X,t,i)×cosθ〕倍に動画を拡大縮小する。【０３２１】
したがって、動画Xに描かれたオブジェクトiを水平軸周りにθだけ回転する変換をrothor'(i,θ,X)と標記すると、
rothor'(i,θ,X) = scale(zc(X,t,i)/〔zc(X,t,i)×sinθ+yc(X,t,i)×cosθ〕,
move(0,zc(X,t,i)×cosθ-yc(X,t,i)×sinθ-yc(X,t,i),
select(i,X)))
となる。【０３２２】
動画Xに描かれたオブジェクトiを垂直軸周りにφだけ回転する変換rotver'(i,θ,X)も、同様に定義される。すなわち、
rotver'(i,φ,X) = scale(zc(X,t,i)/〔zc(X,t,i)×sinθ+xc(X,t,i)×cosθ〕,
move(zc(X,t,i)×cosθ-xc(X,t,i)×sinθ-xc(X,t,i),0
select(i,X)))
となる。【０３２３】
本実施例では、動画に描かれた一つのオブジェクトに対する変換を計算負荷が軽い演算move，select，scaleの組み合わせによって実現するため、処理の高速化を図ることができる。
【実施例８】
【０３２４】
上記実施例では、動画Xの時間をdだけずらす変換shift(d,X)としたが、動画Xをスロー再生したり早送りしたりする変換を考えることもできる。【０３２５】
動画Yが、動画Xをa倍に早送りしたものであれば、
Y(t)[x,y] = X(t/a)[x,y]
が成立する。以下、この変換をfastforward(a,X)と表記する。【０３２６】
動画Xに描かれるオブジェクトiと、動画Yに描かれるオブジェクトjと、が、いずれも、ある動作を繰り返し行うもので、オブジェクトiとオブジェクトjとが、動画内における特定の場所に交互に登場するような動画Zを合成したい場合に、shift，fastforwardの組み合わせが利用できる。【０３２７】
たとえば、臼の中の餅を杵で搗く動作をする人物（オブジェクトi）を撮影した動画Xと、同じ臼の中の餅を手でこねる動作をする人物（オブジェクトj）を撮影した動画Yと、を合成して、人物Ａ、人物Ｂが共同して餅搗きする様子を表す動画を生成したい場合などである。【０３２８】
臼におよび周辺の様子、ならびに、撮影を行ったカメラの位置および向きが、動画X、動画Yにおいて共通する場合には、衝突量を表す評価関数を最小化するように、shift，fastforwardに対するパラメータを求めれば良いことになる。【０３２９】
このほか、家具や電気製品を家屋内に配置できるか否かを動画から判定したい場合に、これらの変換を適用することもできる。【０３３０】
たとえば、扉が開閉する洗濯機が、自宅の洗面所に配置できるか否かを、動画から判定したい場合には、以下のような処理を行えば良い。【０３３１】
すなわち、電気製品メーカーもしくは電気製品の販売者は、洗濯機の扉が周期的に開閉する様子を正面から撮影した動画Xをウェブなどにおいて提供する。【０３３２】
一方、洗濯機の購入を検討しているユーザは、洗濯機を設置しようと考えている部屋の箇所における部屋の扉や家具の扉が周期的に開閉する様子を正面から撮影した動画Yを用意する。【０３３３】
動画Xにおけるカメラから洗濯機までの距離と、動画Yにおけるカメラから洗濯機設置の候補箇所までの距離と、がほぼ一致するように、正規化を行った後、ユーザは、動画Xにおける洗濯機のオブジェクトを、動画Yにおける設置候補の箇所にドラッグアンドドロップする。【０３３４】
そして、動画X，Yにおけるオブジェクトの衝突量を求める。衝突がなければ、洗濯機は所望の箇所に設置できる、と推定できる。また、衝突が生じた場合であっても、衝突量を最小化するようなshift，fastforwardに対するパラメータを求めて、衝突が生じないようにすることができれば、やはり、洗濯機は所望の箇所に設置できる、と推定できる。【０３３５】
なお、ユーザが部屋の中を撮影する際に、撮影方向が限られることもある。この場合には、扉が周期的に開閉する洗濯機を、正面から撮影した様子のほか、左側から撮影した様子、右側から撮影した様子等、種々の方向から撮影した動画を提供することとし、ユーザが部屋を撮影した方向と同じ方向で撮影された動画を選択させることとしても良い。
【実施例９】
【０３３６】
上記実施例では、オブジェクトが互いに喰い込むような衝突をしないように動画の合成ができるほか、オブジェクトの表面が所望の瞬間に接触したり、オブジェクトの底が床に接触し続けたりするような動画の合成が可能となる。以下では、上記実施例の具体的な応用について種々説明する。【０３３７】
第１の応用例は、インターネットオークション等の電子市場において、商品の様子を表す動画を出品者が容易に準備できるようにするものである。【０３３８】
すなわち、電子市場の運営者は、各種の動画の編集ツールを提供するとともに、ユーザが自由に利用できるような動画素材を提供する。この動画素材は、電子市場の出品者や入札者が用意するものでも良いし、パブリック利用が可能な動画をアップロードして他のユーザに閲覧させるような動画配信システムを別途用意し、この動画配信システムに蓄積された動画を再利用することとしても良い。【０３３９】
出品者は、自宅の部屋の中等で、背景を表す動画をあらかじめ撮影しておくか、この際には、商品を見栄えよく見せるための装飾台や屏風などを用意しても良いし、部屋内の物品を整理整頓し、掃除して、プライベートな情報がわからないようにしても良い。また、背景動画は、動画素材の中から選択することとしても良い。【０３４０】
この後、出品者が、新たな商品を出品しようと考えた場合には、部屋の中の好きな場所で、物品の整理整頓や掃除を行わないままで、撮影を行うことができる。【０３４１】
この後、出品者は、撮影された新たな商品の動画を、あらかじめ撮影した背景動画にドラッグアンドドロップする。すると、上記の衝突の回避および位置の自動調整により、商品が背景画像の物品（屏風等）には衝突せず、かつ、背景画像の床（装飾台の上面等）に接する様子を表す動画が合成できる。【０３４２】
なお、商品動画の背景動画に対する合成は、出品者だけではなく、入札者ができるようにしても良い。たとえば、パーティ用のドレスを出品されており、出品者等のモデルがそのドレスを着用して歩いたり回ったりしている様子を表す商品動画が提供されているものとする。【０３４３】
入札者は、自分がドレスを着用して出席しようとするパーティが開催された会場内を撮影した背景動画を、自分で撮影したり、動画素材の中から選んだりしておく。そして、入札者は、パーティ会場の背景動画に、モデルに着用されたドレスの商品動画を合成する。【０３４４】
上記の実施例を適用することにより、モデルは床の上を移動するが、会場内の他の人物や家具、設備とは衝突しないような動画が合成されることになる。【０３４５】
入札者は、この動画を閲覧することにより、入札の前に、商品として出品されているドレスがパーティ会場の雰囲気にマッチしているか否かを、事前にチェックすることができるようになる。【０３４６】
第２の応用例は、動画素材のさらなる活用である。【０３４７】
たとえば、著名な芸能人が音楽に合わせて踊っている様子を表す背景動画が動画素材として提供されていれば、ユーザが自分で踊っている動画を撮影して合成することで、ユーザが著名な歌手と一緒に踊っている様子を表す動画を生成することが可能である。【０３４８】
また、メリーゴーラウンドが空席のまま動いている様子を表す背景動画が動画素材として提供されている場合には、ユーザが自転車や台車等、別の乗物に乗って、メリーゴーラウンドとほぼ同じ軌跡を移動する動画を撮影してから、「ユーザがメリーゴーラウンドに接し続ける」という制約条件を課して、動画の合成を行うことで、ユーザがメリーゴーラウンドに乗っている様子を表す動画を生成することができる。【０３４９】
このほか、ボールが床に激しくぶつかって衝突する背景動画に、ユーザが腕やラケットを強く振り下ろす動画を合成する際に、ユーザが腕を振り下ろした瞬間にユーザの手やラケットとボールが接する、という制約条件を課すこととすれば、ユーザがバレーボールのスパイクやテニスのスマッシュをしている様子を表す動画が生成可能である。【０３５０】
さらに、フェンシングや剣道の練習を一人で行っている様子を撮影した動画素材を複数合成し、撮影されたプレイヤーが決め技を行った瞬間にオブジェクト同士がタイミングで接する、という条件を課すこととすれば、あたかも試合が行われているかのような動画を合成することも可能である。【０３５１】
なお、本願においては、２０１２年７月２０日にされた日本国特許出願特願２０１２−１６１９２４を基礎とする優先権を主張するものとし、指定国の法令が許す限り、当該基礎出願の内容を本願に取り込むものとする。
【産業上の利用可能性】
【０３５２】
本発明によれば、複数の動画に描かれた奥行情報を伴うオブジェクトを１つの動画にまとめようとするときに、オブジェクトが干渉条件を満たさないようにするのに好適な動画処理装置、動画処理方法、ならびに、情報記録媒体を提供することができる。
【符号の説明】
【０３５３】
１１    撮影点
１２    投影面
１３    半直線
１４    オブジェクト
１５    衝突点
１７    Ｚ距離
２１    代表点
１０１  動画処理装置
１０２  背面奥行取得部
１０３  衝突判定部
１０４  ずらし量設定部
１０５  動画生成部
１０６  修正部
４０１  画面
４１１  ウィンドウ
４１２  ウィンドウ
４１３  カーソル
【要約】
動画処理装置（１０１）は、第１動画と、第２動画と、を合成する。第１動画には、第１オブジェクトが描かれ、第１オブジェクトの奥行情報を伴う。第２動画には、第２オブジェクトが描かれ、第２オブジェクトの奥行情報を伴う。動画生成部（１０５）は、第１動画と、第２動画と、を合成した第３動画を生成する。干渉判定部として働く衝突判定部（１０３）は、第３動画において、第１オブジェクトと、第２オブジェクトと、が、干渉条件を満たすか否かを、第１オブジェクトの奥行情報ならびに第２オブジェクトの奥行情報を参照して判定する。干渉条件が満たされる、と判定された場合、修正部（１０６）は、第２オブジェクトの３次元空間内における移動の軌跡の形状の修正に応じた変形変換を施すことにより、第２動画を修正する。【図１】
0005451955.tif 000002
【図２Ａ】
0005451955.tif 000003
【図２Ｂ】
0005451955.tif 000004
【図２Ｃ】
0005451955.tif 000005
【図２Ｄ】
0005451955.tif 000006
【図２Ｅ】
0005451955.tif 000007
【図３】
0005451955.tif 000008
【図４】
0005451955.tif 000009
【図５Ａ】
0005451955.tif 000010
【図５Ｂ】
0005451955.tif 000011
【図５Ｃ】
0005451955.tif 000012
【図５Ｄ】
0005451955.tif 000013
【図６】
0005451955.tif 000014
【図７】
0005451955.tif 000015
【図８】
0005451955.tif 000016
【図９Ａ】
0005451955.tif 000017
【図９Ｂ】
0005451955.tif 000018
【図９Ｃ】
0005451955.tif 000019
【図９Ｄ】
0005451955.tif 000020
【図９Ｅ】
0005451955.tif 000021
【図１０】
0005451955.tif 000022
【図１１Ａ】
0005451955.tif 000023
【図１１Ｂ】
0005451955.tif 000024
【図１２Ａ】
0005451955.tif 000025
【図１２Ｂ】
0005451955.tif 000026
【図１２Ｃ】
0005451955.tif 000027
【図１２Ｄ】
0005451955.tif 000028
【図１３】
0005451955.tif 000029