(57)【特許請求の範囲】
【請求項１】
動画を形成する複数枚の時系列画像を記憶する手段と、
時間軸方向に隣接する第１の画像及び第２の画像のピクセル位置情報及びピクセル値情報を用いた最適化計算によって、第１の画像のピクセル値の線形結合として、第２の画像の各ピクセル値を規定する継承行列を生成する継承行列生成手段と、
前記第１の画像を編集するための第１の編集情報マップが記憶されており、前記継承行列を用いて、前記第１の編集情報マップから前記第２の画像に対応する第２の編集情報マップを生成する編集情報マップ生成手段と、
前記第２の画像に対して、前記第２の編集情報マップを適用して当該第２の画像の編集画像を生成する編集画像生成手段と、
を備えた動画編集装置。
【請求項２】
前記複数枚の時系列画像から選択された少なくとも１枚の画像を編集するための初期編集情報マップを生成する初期編集情報マップ生成手段を備えており、
前記第１の画像は前記選択された画像であり、前記第１の画像を編集するための編集情報マップは前記初期編集情報マップである、
請求項１に記載の動画編集装置。
【請求項３】
前記初期編集情報マップ生成手段は、ユーザ入力に基づいて前記初期編集情報マップを生成する、請求項２に記載の動画編集装置。
【請求項４】
前記初期編集情報マップから出発して、前記継承行列生成手段及び前記編集情報マップ生成手段を用いて、各時系列画像に対応する編集情報マップを時間軸方向に順次生成し、
前記編集画像生成手段によって、各時系列画像を、対応する編集情報マップを用いて編集することで複数枚の時系列編集画像からなる動画を生成する、
請求項２、３いずれか１項に記載の動画編集装置。
【請求項５】
前記編集情報マップは、動画を形成する各画像のピクセル数と同数のピクセル数からなり、当該編集情報マップの全てあるいは一部のピクセルに編集パラメータが割り当てられている、請求項１〜４いずれか１項に記載の動画編集装置。
【請求項６】
前記継承行列生成手段は、編集情報マップの時間軸方向の連続性を保証する項と、同じフレーム内での編集パラメータの一貫性を保証する項と、を含む関数の最適化計算によって継承行列を生成する、請求項１〜５いずれか１項に記載の動画編集装置。
【請求項７】
前記関数は、
0005846663.tif 000067
であり、
0005846663.tif 000068
であり、
etはフレームtにおける編集情報（編集パラメータ）、
et＋1はフレームt＋1における編集情報（編集パラメータ）、
ctiはフレームtの位置iに存在するピクセルのL＊a＊b＊色情報、
xtiはフレームtのピクセルの位置情報（座標）、
σctは時間軸方向における色情報の差に関する重み定数、
σsは位置情報に関する重み定数、
σcは色情報に関する重み定数、
||・||２はベクトルのＬ２ノルム、
である、請求項６に記載の動画編集装置。
【請求項８】
前記関数は、
0005846663.tif 000069
であり、
ζklijは、フレームkのピクセルiとフレームlのピクセルjの類似度 であって、
0005846663.tif 000070
であり、
ｆkiは、フレームkのピクセルiが持つ画素特徴であり、
ekiは、フレームkのピクセルiに対する編集パラメータであり、
nは、動画の各フレームに含まれるピクセル数である、請求項６に記載の動画編集装置。
【請求項９】
前記継承行列生成手段は、継承行列の計算において密行列が含まれる場合には、当該密行列をより小さなサイズの行列同士の積に分解して近似する近似手段を備えており、
編集情報マップ生成手段は、前記近似手段によって生成された近似継承行列を用いて編集情報マップを生成する、
請求項１〜８いずれか１項に記載の動画編集装置。
【請求項１０】
前記近似手段は、Nystrom法を用いた近似手段である、請求項９に記載の動画編集装置。
【請求項１１】
動画を形成する複数枚の時系列画像において時間軸方向に隣接する第１の画像及び第２の画像のピクセル位置情報及びピクセル値情報を用いた最適化計算によって、第１の画像のピクセル値の線形結合として、第２の画像の各ピクセル値を規定する継承行列を生成する継承行列生成ステップと、
前記第１の画像を編集するための第１の編集情報マップが記憶されており、前記継承行列を用いて、前記第１の編集情報マップから前記第２の画像に対応する第２の編集情報マップを生成する編集情報マップ生成ステップと、
前記第２の画像に対して、前記第２の編集情報マップを適用して当該第２の画像の編集画像を生成する編集画像生成ステップと、
を備えた動画編集方法。
【請求項１２】
前記複数枚の時系列画像から選択された少なくとも１枚の画像を編集するための初期編集情報マップを生成する初期編集情報マップ生成ステップを備えており、
前記第１の画像は前記選択された画像であり、前記第１の画像を編集するための編集情報マップは前記初期編集情報マップである、
請求項１１に記載の動画編集方法。
【請求項１３】
前記初期編集情報マップ生成ステップは、ユーザ入力に基づいて前記初期編集情報マップを生成する、請求項１２に記載の動画編集方法。
【請求項１４】
前記初期編集情報マップから出発して、各時系列画像に対応する編集情報マップを時間軸方向に順次生成し、
各時系列画像を、対応する編集情報マップを用いて編集することで複数枚の時系列編集画像からなる動画を生成する、
請求項１２、１３いずれか１項に記載の動画編集方法。
【請求項１５】
前記編集情報マップは、動画を形成する各画像のピクセル数と同数のピクセル数からなり、当該編集情報マップの全てあるいは一部のピクセルに編集パラメータが割り当てられている、請求項１１〜１４いずれか１項に記載の動画編集方法。
【請求項１６】
前記継承行列生成ステップは、編集情報マップの時間軸方向の連続性を保証する項と、同じフレーム内での編集パラメータの一貫性を保証する項と、を含む関数の最適化計算によって継承行列を生成する、請求項１１〜１５いずれか１項に記載の動画編集方法。
【請求項１７】
前記関数は、
0005846663.tif 000071
であり、
0005846663.tif 000072
であり、
etはフレームtにおける編集情報（編集パラメータ）、
et＋1はフレームt＋1における編集情報（編集パラメータ）、
ctiはフレームtの位置iに存在するピクセルのL＊a＊b＊色情報、
xtiはフレームtのピクセルの位置情報（座標）、
σctは時間軸方向における色情報の差に関する重み定数、
σsは位置情報に関する重み定数、
σcは色情報に関する重み定数、
||・||２はベクトルのＬ２ノルム、
である、請求項１６に記載の動画編集方法。
【請求項１８】
前記関数は、
0005846663.tif 000073
であり、
ζklijは、フレームkのピクセルiとフレームlのピクセルjの類似度 であって、
0005846663.tif 000074
であり、
ｆkiは、フレームkのピクセルiが持つ画素特徴であり、
ekiは、フレームkのピクセルiに対する編集パラメータであり、
nは、動画の各フレームに含まれるピクセル数である、請求項１６に記載の動画編集方法。
【請求項１９】
前記継承行列生成ステップは、継承行列の計算において密行列が含まれる場合に、当該密行列をより小さなサイズの行列同士の積に分解して近似する近似ステップを備えており、
編集情報マップ生成ステップでは、前記近似ステップによって生成された近似継承行列を用いて編集情報マップを生成する、
請求項１１〜１８いずれか１項に記載の動画編集方法。
【請求項２０】
前記近似ステップは、Nystrom法を用いた近似である、請求項１９に記載の動画編集方法。
【請求項２１】
請求項１１〜２０いずれか１項に記載の動画編集方法をコンピュータに実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画を形成するフレーム間の連続性を保持する動画編集方法及び装置に係り、詳しくは、動画におけるフレーム間の連続性を保持しながら、動画の色調やテクスチャなどを編集するための手法に関する。
【背景技術】
【０００２】
近年、携帯電話やデジタルカメラなどの比較的安価なデバイスを用いて動画が撮影できるようになったことで、これまで一部の映像制作においてしか用いられてこなかった動画の編集技術に対する一般利用者からの要望が高まりつつある。【０００３】
静止画の外観、すなわち色調や露光、テクスチャなどを編集するための技術は多く研究がなされている。近年では、ユーザの入力を元にして静止画を編集する手法が数多く提案されており、例えば、ユーザ制御によるモノクロ画像の着色（非特許文献１）やトーン・マッピング（非特許文献２）、色調補正（非特許文献３）、色転写（非特許文献４）などが挙げられる。これらの手法は、少ないユーザの入力情報から静止画全体を編集するものであり、ユーザが画像の一部にストロークの形で入力した編集パラメータを元にして、静止画の全てのピクセルに編集パラメータを割り当てる。これらの手法の特徴は、割り当てられた編集パラメータが静止画中の物体領域をマスクするだけでなく、領域の境界における合成の程度も同時に計算できるという点にある。【０００４】
上記手法に一貫する技術思想は、ユーザによる入力を基にした最適化問題を解くことにより、ユーザ入力に潜む意図を静止画全体に適応するというものであり、この考え方は動画においても有用と考えられる。しかしながら、動画は多くのフレームから構成されるが故に、静止画における既存手法を動画にそのまま適応しようとする場合には多くのユーザ入力が必要である。より具体的には、ビデオなどの動画像に対して、部分的な編集処理（例えば、特定の物体の色を変えるなど）を施そうとすると、１フレームごとに指示するか、多くても１０〜２０フレームに１枚に指示を入れる必要がある。ビデオは１秒間に３０フレームを含むため、ちょっとした長さであっても相当の手間が必要となる。【０００５】
ここで、特定のフレームに施されたユーザ入力を元にして、ユーザの意図をフレーム間で次々に移送していく手法が考えられる。従来、動画処理におけるフレーム間の連続性は、オプティカルフローと呼ばれる連続する２枚のフレーム間での位置の対応関係を基本としていた。しかし、物体や背景が他の物体によって遮られて見えなくなったり、フレームから出入りしたりする現象が頻繁に発生するために、位置の対応関係を採り続けることは非常に困難であり、自動的な対応関係付けは数十フレームがせいぜいであった。【０００６】
また、オプティカルフローを利用しようとすると、対応のつかない部分が生じるために、当該部分を埋めるべく平滑化などの処理によって不特定領域を解消する必要があった。この平滑化は、ぼかし操作に相当するもので、編集対象部分が過度に平均化されてしまうという不具合がある。【０００７】
一般に、オプティカルフローを用いる手法では、(i)フレームの全てのピクセルに位置の対応関係を正確に与えるのに時間を要する、(ii)遮蔽などの影響で全てのピクセルに対応関係を与えることができない場合がある、という課題があり、対応のつかない場所に情報を与える目的でエッジ保持フィルタなどが用いられるが（例えば、非特許文献５には、エッジ保存型平滑化フィルタに基づく近似的なオプティカルフローを用いて、領域分割のラベルを移送する手法が開示されている）、対応付けの失敗や対応関係の不足により、移送に失敗することがある。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Levin, A., Lischinski, D. and Weiss, Y.: Colorization using optimization, ACM Trans. Graph., Vol. 23, No. 3, pp. 689-694 (2004).
【非特許文献２】Lischinski, D., Farbman, Z., Uyttendaele, M. and Szeliski, R.: Interactive local adjustment of tonal values, ACM Trans. Graph., Vol. 25, No. 3, pp. 646-653(2006).
【非特許文献３】An, X. and Pellacini, F.: AppProp: all-pairs appearancespace edit propagation, ACM Trans. Graph., Vol. 27, No. 3, pp. 40:1-40:9 (2008).
【非特許文献４】An, X. and Pellacini, F.: User-Controllable Color Transfer, Computer Graphics Forum, Vol. 29, No. 2, pp. 263-271 (2010).
【非特許文献５】Lang, M., Wang, O., Aydin, T., Smolic, A. and Gross, M.: Practical temporal consistency for image-based graphics applications, ACM Trans. Graph., Vol. 31, No. 4, pp. 34:1-34:8 (2012).
【非特許文献６】Williams, C. and Seeger, M.: Using the Nystrom Method to Speed Up Kernel Machines, Advances in Neural Information Processing Systems 13, pp. 682-688 (2001).
【非特許文献７】ZHANG K., TSANG I. W., KWOK J. T.: Improved nystrom low-rank approximation and error analysis. In Proc. of Int'l Conf. on Machine Learning (2008), pp. 1232-1239.
【非特許文献８】Gastal, E. S. L. and Oliveira, M. M.: Domain transform for edge-aware image and video processing, ACM Trans. Graph., Vol. 30, No. 4, pp. 69:1-69:12 (2011).
【非特許文献９】Yatziv, L. and Sapiro, G.: Fast image and video colorization using chrominance blending, IEEE Trans. On Image Processing, Vol. 15, No. 5, pp. 1120-1129 (2006).
【非特許文献１０】Farbman, Z. and Lischinski, D.: Tonal stabilization of video, ACM Trans. Graph., Vol. 30, No. 4, pp. 89:1-89:10 (2011).
【非特許文献１１】Reinhard, E., Adhikhmin, M., Gooch, B. and Shirley, P.: Color transfer between images, Computer Graphics and Applications, IEEE, Vol. 21, No. 5, pp. 34 -41 (2001).
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、このような位置の対応関係に基づかないフレーム間の編集パラメータの移送を用いたフレーム間の連続性を保持する動画編集方法及び装置を提供することを目的とするものである。
【課題を解決するための手段】
【００１０】
本発明は、
動画を形成する複数枚の時系列画像を記憶する手段と、
時間軸方向に隣接する２枚の画像、すなわち第１の画像及び第２の画像のピクセル位置情報及びピクセル値情報を用いた最適化計算によって、第１の画像のピクセル値の線形結合として、第２の画像の各ピクセル値を規定する継承行列を生成する継承行列生成手段と、
前記第１の画像を編集するための第１の編集情報マップが記憶されており、前記継承行列を用いて、前記第１の編集情報マップから前記第２の画像に対応する第２の編集情報マップを生成する編集情報マップ生成手段と、
前記第２の画像に対して、前記第２の編集情報マップを適用して当該第２画像の編集画像を生成する編集画像生成手段と、
を備えた動画編集装置、である。【００１１】
１つの態様では、前記複数枚の時系列画像から選択された少なくとも１枚の画像（後述する「アンカーフレーム」）を編集するための初期編集情報マップを生成する初期編集情報マップ生成手段を備えており、
前記第１の画像は前記選択された画像であり、前記第１の画像を編集するための編集情報マップは前記初期編集情報マップである。
１つの態様では、前記初期編集情報マップ生成手段は、ユーザ入力に基づいて前記初期編集情報マップを生成する。
ユーザ入力（例えば、ポインティングデバイスを用いた入力）によって静止画を編集する手段としては、様々な手法が当業者に知られており、ある画像を編集するための編集情報（編集情報マップ）が得られるものであれば、初期編集情報マップ生成手段の具体的な構成は限定されない。【００１２】
１つの態様では、前記初期編集情報マップから出発して、前記継承行列生成手段及び前記編集情報マップ生成手段を用いて、各時系列画像に対応する編集情報マップを時間軸方向に順次生成（移送）し、
前記編集画像生成手段によって、各時系列画像を、対応する編集情報マップを用いて編集することで複数枚の時系列編集画像からなる動画を生成する。
１つの態様では、継承行列の計算及び当該継承行列を用いた編集情報マップの移送は、早い時刻から遅い時刻（t→t+1）への処理として実行されるが、継承行列の計算及び当該継承行列を用いた編集情報マップの移送は、遅い時刻から早い時刻（t→t‐1）への処理として実行してもよい。
１つの態様では、１枚のアンカーフレームtから早い時刻から遅い時刻（t→t+1）、遅い時刻から早い時刻（t→t‐1）の両方向に処理を実行してもよい。
１つの態様では、時間軸方向に離隔した２枚のアンカーフレームが選択され、一方のアンカーフレームを基準に早い時刻から遅い時刻（t→t+1）へ処理が実行され、他方のアンカーフレームを基準に遅い時刻から早い時刻（t→t‐1）へ処理が実行される。
１つの態様では、編集情報マップ生成時に計算された継承行列（近似継承行列を含む）は、記憶部に記憶しておいても、あるいは、対応する編集情報マップを生成した後に破棄してもよい。
１つの態様では、時間軸方向に隣接する各画像対の間の継承行列は、編集情報マップを生成する前に予め取得され記憶部に記憶されている。【００１３】
１つの態様では、前記編集情報マップは、動画を形成する各画像のピクセル数と同数のピクセル数からなり、当該編集情報マップの全てあるいは一部のピクセルに編集パラメータが割り当てられている。
本発明に用いることができる編集処理の種類は、各ピクセルを編集するための関数が特定の有限個のパラメータからなっているものであればいかなる編集処理であってもよく、編集処理の種類は限定されない。
編集処理の種類としては、色調変換（色転写、グレースケールの着色を含む）、色変化の安定化、テクスチャの鮮明化等が例示される。
編集情報ないし編集パラメータは、編集処理の具体的な内容に応じて当業者において適宜設定される。【００１４】
前記継承行列生成手段は、編集情報マップの時間軸方向の連続性を保証する項と、同じフレーム内での編集パラメータの一貫性を保証する項と、を含む関数の最適化計算によって継承行列を生成する。
最適化計算に用いるエネルギー関数について説明する。
表１は、後述する実施形態で用いたエネルギー関数であり、左の列に示しているものが、正方向の継承、すなわちtフレームからt+1フレームへの継承行列を導き出すための式に係るものであり、右の列に示しているものは逆方向の継承、すなわちt+1フレームからtフレームへの継承を表す継承行列を導き出すための式を示している。
【表１】
0005846663.tif 000002
上記高速版t→t+1において、
0005846663.tif 000003
上記高速版t+1→tにおいて、
0005846663.tif 000004
である。
etはフレームtにおける編集情報（編集パラメータ、定数）、
et＋1はフレームt＋1における編集情報（編集パラメータ、変数）、
ctiはフレームtの位置iに存在するピクセルのL＊a＊b＊色情報、
xtiはフレームtのピクセルの位置情報（座標）、
σctは時間軸方向における色情報の差に関する重み定数、
σsは位置情報に関する重み定数、
σcは色情報に関する重み定数、
||・||２はベクトルのＬ２ノルム、
である。
表２は、上記の高速版をより一般的な形で記載したものである。
【表２】
0005846663.tif 000005
上記一般化版t→t+1において、
0005846663.tif 000006
上記一般化版t+1→tにおいて、
0005846663.tif 000007
である。
各記号の説明については、上述の記載を援用することができる。
σstは、時間軸方向を含めた位置の差に対する重み定数、である。
上記複数の式について、ある技術思想を表現する数式の形は当業者において適宜設定し得るものであり、当業者において等価な式は、本発明の技術的範囲に属するものである。
１つの態様では、編集情報マップの時間軸方向の連続性を保証する項は、「隣接する二枚のフレームにおいて同じ位置にあるピクセルが、類似した色を持つ場合には、その二つのピクセルがもつ編集パラメータも類似している。」という仮定に基づき、同じフレーム内での編集パラメータの一貫性を保証する項は、「ある一枚のフレームに注目すると、そのフレーム内で距離が近く、色が類似している場合には、その二つのピクセルが持つ編集パラメータも類似している。」という仮定に基づくものである。
後述する実施形態（tフレームからt+1フレーム）では、前記関数は、
0005846663.tif 000008
であり、
0005846663.tif 000009
である。
各記号の説明については、上述の記載を援用することができる。
後述する他の実施形態では、継承行列は、以下の目的関数を用いたフレーム間でのエネルギー最小化問題として定義される。
0005846663.tif 000010
この目的関数は、画素特徴が類似した画素同士には同じような編集パラメータが割り当てられるという仮定に基づく。前項は前フレームからの拘束、後項は現フレーム内での拘束を表す。
ζklijは、フレームkのピクセルiとフレームlのピクセルjの類似度 であり、詳しくは、
0005846663.tif 000011
となる。
ｆkiは、フレームkのピクセルiが持つ画素特徴。一般にはL*a*b*色表現が3次元、フレーム内位置(x, y)が2次元、時間成分tが1次元の計6次元ベクトルである。
ekiは、フレームkのピクセルiに対する編集パラメータである。
nは、動画の各フレームに含まれるピクセル数である。【００１５】
継承行列の計算において、密行列が含まれる場合には、当該密行列をより小さなサイズの行列同士の積に分解して近似し、疎行列のみの場合には、そのまま計算することも可能である。そして、編集情報マップの生成手段は、前記の近似手段ないし直接計算によって生成された継承行列を用いて、編集情報マップを生成することができる。
後述する実施形態では、前記継承行列生成手段は、密行列が含まれる場合には、当該密行列をより小さなサイズの行列同士の積に分解して近似する近似手段を備えており、
編集情報マップ生成手段は、前記近似手段によって生成された近似継承行列を用いて編集情報マップを生成する。
１つの態様では、前記近似手段は、Nystrom法を用いた近似手段である。後述する実施形態では、k-means法に基づくNystrom法を採用している。
なお、行列計算を高速に行なう手段としては、幾つかの手法が当業者に知られており、例えば、行列が疎行列の場合には値を持つ要素のみを計算することで高速に計算してもよい。【００１６】
本発明は、方法の発明としても規定することができ、
時間軸方向に隣接する第１の画像及び第２の画像のピクセル位置情報及びピクセル値情報を用いた最適化計算によって、第１の画像のピクセル値の線形結合として、第２の画像の各ピクセル値を規定する継承行列を生成する継承行列生成ステップと、
前記第１の画像を編集するための第１の編集情報マップが記憶されており、前記継承行列を用いて、前記第１の編集情報マップから前記第２の画像に対応する第２の編集情報マップを生成する編集情報マップ生成ステップと、
前記第２の画像に対して、前記第２の編集情報マップを適用して当該第２画像の編集画像を生成する編集画像生成ステップと、
を備えた動画編集方法、である。【００１７】
本発明に係る動画像編集装置を構成する各手段のハードウェア構成は、１つあるいは複数のコンピュータから構成することができる。コンピュータは、典型的には、動画像を形成する複数の時系列画像、各種画像編集プログラム、編集情報マップ、編集処理画像等の各種データを格納する記憶部、各種計算を行う演算処理部、各映像（元動画像、編集動画像）を表示する表示部、コンピュータを操作するための入力部、計算結果等のデータを出力する出力部、を備えており、汎用コンピュータ（入力部、出力部、演算部、記憶部、表示部等を備える）を用いることができる。
本発明に係る動画像編集方法は、１つあるいは複数のコンピュータによって実行することができる。
本発明は、さらに、動画編集方法をコンピュータに実行させるためのコンピュータプログラム、あるいは、当該コンピュータプログラムが記録された記録媒体としても定義される。
【発明の効果】
【００１８】
本発明はオプティカルフローには依拠せずに、連続するフレームのピクセル間の対応関係を表現し、編集操作の伝播を実行するものであり、位置の対応関係を用いた処理に起因する課題を解決でき、また、ユーザが一部のフレームに対して入力した編集パラメータの安定な移送を実現する。従来、物体による相互遮蔽やフレームアウトなどに起因する対応関係の欠落を避けられないオプティカルフローでは、平滑化処理などを必要とするが、結果として、編集情報が急速に平均化され、数十フレーム程度で消失してしまうという問題があった。継承行列表現を用いることによって、この問題を解決し、安定的に編集情報を伝播することが可能となる。【００１９】
本発明は、編集情報と独立して得られる継承行列により生成される編集情報マップを用いることで、多くの編集処理に対応できる。編集操作の表現は、あるピクセルを編集するための関数を規定するパラメータから成る多次元情報である。たとえば、色調補正において、色相、彩度、明度を編集することを考えた場合には、各ピクセルはそれぞれの変化量を表す三次元ベクトルを有することになる。すなわち、編集操作の表現は、汎用的な表現となっており、多くの応用に適用できる。例えば、部分的な色の変更、色変化の安定化、テクスチャの鮮明化など、様々な応用が考えられる。
【図面の簡単な説明】
【００２０】
【図１】提案手法の概念図である。
【図１Ａ】提案手法を示すブロック図である。記憶部には、時系列元画像セット（元動画）が格納されており、元動画は表示部に表示される。編集処理部は、初期編集情報マップ生成手段、継承行列生成手段、編集情報マップ生成手段、編集画像生成手段を備えている。選択された画像に対して入力部が編集入力を行うことで、初期編集情報マップ生成手段によって初期編集情報マップが生成され、編集情報マップデータとして記憶部に記憶される。継承行列生成手段は、時間軸方向に隣接する画像のピクセル情報を用いて、継承行列を生成する。継承行列は継承行列データとして記憶部に記憶してもよい。編集情報マップ生成手段は、時間軸方向に隣接する画像間の継承行列と時間軸方向に隣接する継承元画像の編集情報マップを用いて、着目する画像の編集情報マップを生成する。編集情報マップは編集情報マップデータとして記憶部に記憶される。編集画像生成手段は、着目する画像の編集情報マップを用いて、当該着目する画像の編集画像を生成する。編集画像は事例列編集画像（編集動画）として記憶部に記憶され、編集動画は表示部に表示される。
【図２】継承行列による動画の色調補正結果を示す図である。この結果は最初のフレームにのみユーザ入力を行って作成したものである。行ったユーザ入力は上段の一番左に示した（ワイングラスの中のワインを指定するストローク、フレーム上下の略直線状の２本のストローク、ワイングラスの背景の波状のストロークの４つの入力がある）。実際の第１フレームの画像では、赤ワインの色を明るくする編集処理を行っている。この動画では最初のフレームに写っている片方のワイングラスにしか入力を入れていないが、のちに現れるワインボトルから注がれるワインについても適切に色（明るい赤色）が編集されている。
【図３】動画に対する詳細強調の結果を示す図である。この結果は継承行列により伝搬したパラメータに基づいて、定義域変換によるエッジ保存フィルタ（非特許文献８）を用いたマルチスケール分解で詳細強調を行っている。この動画では花の部分の詳細が強調されている一方で背景や葉の部分にはぼかしをかけている。
【図４】２つのアンカーフレーム（第１フレーム、第２２４フレーム）を用いた色調変換の結果を示す図である。元の動画では黄色のモミジの葉が風で揺られているが、最初と最後のフレームに異なる色調変化を与えるユーザ入力を行うことで徐々に葉の色が変化するよう編集を行った。この結果は、２つのアンカーフレームから得られるパラメータを線形補間することにより作成しているが、補間の仕方は線形に限らず、例えばシグモイドカーネルのようなものを用いて補間を行ってもよい。実際には、第１フレーム上では、元画像のモミジの黄色をより鮮やかな色へと変更する編集（彩度を上げている）が入力され、第２２４フレームでは、元画像のモミジの黄色を赤とする編集が入力されている。
【図５】グレースケール動画に対する着色処理を示す図である。この結果はアンカーフレームに対してグラフ探索によるグレースケール画像の着色処理（非特許文献９）を行い、その結果を継承行列により伝搬したものである。実際の編集画像において、熱帯魚がオレンジ、イソギンチャクがパープル、背景がブルーに着色されている。
【図６】動画の色調安定化結果を示す図である。この結果では入力動画において見られる色度の揺れが、出力動画において除去されていることがわかる。また従来手法（非特許文献１０）と比べるとわずかな違いではあるがソファー周辺の色がより安定していることがわかる。
【図７】継承行列を用いた静止画から動画への色転写の結果を示す図である。入力動画の１フレーム目および参照画像にユーザ入力が行われている。入力画像の花の色はイエローであり、参照画像のチューリップのオレンジを入力画像の花の色に転写する。また、参照画像の背景のテクスチャを入力画像の背景に転写する。入力動画の方にのみ存在する赤の入力は蝶の部分の色調が変化しないようにするためのものである。
【図８】Langらによる近似的なオプティカルフローを用いた編集情報マップの伝搬法（非特許文献５）との比較を示す。 この画像は同じ編集情報マップをフレーム分伝搬した結果であり、従来法が部分的にしか適切な伝搬を行えていない一方で、提案手法は適切かつ安定に伝搬を行えている。
【発明を実施するための形態】
【００２１】
［１］概要
フレーム間連続性を保持する動画編集法の実施形態について説明する。本実施形態の概念図を図1に示す。上段が元動画の時系列画像（入力画像）、中段が編集情報（編集情報マップ）、下段が編集時系列画像（出力画像）である。本実施形態では、時間軸方向に隣接するフレーム（静止画）間の位置の対応関係を用いず、フレーム間の対応関係を１つの正方行列により記述する。これは、あるフレームの各ピクセルが持つ性質は、前のフレームのピクセルが持つ性質の線形結合（凸結合）により表現できるという仮定に基づいている。この線形結合の係数により構成される正方行列によってフレーム間の対応関係を記述する。本明細書ではこの行列を「継承行列(inheritance matrix)」ないし編集量伝搬行列（Edit-Propagation Matrix）と呼ぶ。なお、各フレームに含まれる画素数が同じ場合は正方行列となるが、本発明に係る手法は正方行列を用いるものに限定されない。
【００２２】
継承行列において、ｔ＋１フレームの画像の各ピクセルが、ｔフレームの画像のピクセルの重み付けで表される。重み付けの計算には、ピクセル間の類似性が用いられる。類似性は、空間的な距離の類似（近さ）、色としての類似（色が近い）で測る。継承行列によって、ｔ＋１フレームの画像の全てのピクセルが、前のフレームｔの画像の類似したピクセルの重み付けで表現される。これに対して、オプティカルフローを用いた処理では、ｔ＋１フレームの画像でフレームインしたピクセル、ｔフレームの画像では隠されていたピクセルは、前のｔフレームの画像のピクセルとｔフレームの画像のピクセルの組み合わせとしては表現できない。
【００２３】
本明細書において、ユーザが入力を行うフレーム（静止画）をアンカーフレームと呼び、最初にアンカーフレーム上の編集情報を作成する。この編集情報を以下では編集情報マップと呼ぶ。編集情報マップは、以下のような要件を備えている。
（i）動画像を形成する各画像（フレーム）のピクセル数と同数のピクセル数からなる。なお、要件(i)は、典型的な実施態様を示すものであり、編集情報マップのピクセル数と動画を形成する各画像のピクセル数は同数でなくてもよい。
（ii）各画像ｔに対応して編集情報マップｔが存在する。
（iii）一部あるいは全てのピクセルに編集パラメータが割り当てられている。一部のピクセルに編集パラメータが割り当てられている場合には、編集を要しないピクセルには編集パラメータが割り当てられていない。全てのピクセルに編集パラメータが割り当てられている場合に、編集を要しないピクセルについては、編集情報マップに保存されている編集度合の大きさは0である。編集パラメータは、各ピクセルのピクセル値をどのように編集するかの関数を決定する。例えば、編集パラメータ＝（元の色情報→編集後の色情報の変化量）として規定できる。また、ある画像のピクセルiがIiであり、変更後のピクセルを、編集パラメータeiを用いて、I'i=f(Ii, ei)のように決定する。たとえば、Iiがピクセルの色(c1,c2,c3)であり、変更後の色が(c'1,c'2,c'3)=(a1*c1,a2*c2,a3*c3)のように計算される場合に、(a1,a2,a3)が編集パラメータとなる。
（iv）画像ｔの各ピクセルについて、編集情報マップｔの対応するピクセルの編集パラメータによって編集処理を適用することで編集画像ｔが得られる。
【００２４】
編集情報マップを逐次、時間軸方向の隣接フレームに移送していくことで、動画全体に編集情報の付与を行う。本実施形態では動画の特定のフレームに対して施した編集結果それ自体を移送するのではなく、あるフレームのピクセルごとに割り当てられる編集パラメータを編集情報マップの形で、次のフレームに移送する。継承行列により編集情報マップを移送することで、ユーザの意図に沿った編集を、より少ないユーザ入力で動画全体に実現する。本実施形態に係る手法は大きく２つの処理に分けられる。
【００２５】
第１の処理は、ユーザが入力を行ったフレーム（アンカーフレーム）上での処理である。静止画上でユーザ入力から画像全体の編集情報マップを推定する手法はすでに幾つか提案されており、本実施形態ではAnとPellaciniによる外観編集法（非特許文献３）を用いる。なお、本発明に適用される編集情報マップの推定法は非特許文献３に係る手法に限定されるものではない。
【００２６】
第２の処理は、アンカーフレームに対して作成された編集情報マップを隣接するフレームに移送する処理である。この処理は隣接する２枚の画像から計算される継承行列を用いて行われる。継承行列はエネルギー関数の最適化により求められる行列であり、移送するマップの種類や値に依存しないという特徴を持つ。
【００２７】
本実施形態に係る手法をより詳細に説明すると、以下のようなソフトウェアモジュールないしステップから構成される。
１．編集情報の初期化
アンカーフレームに対するユーザからの入力（scribble）をもとに、動画像と同じ画素数からなる「編集情報マップe0」を生成する。
【００２８】
２．編集情報の適用
編集情報マップに応じて、当該フレームに編集処理を施す。
【００２９】
３．最適化による継承行列の計算
現在のフレームｔの画像のピクセルの位置情報及びピクセル値情報（色情報）と、次のフレームｔ＋１の画像のピクセルの位置情報及びピクセル値情報（色情報）と、を用いた最適化計算によって時間軸方向に隣接する２つのフレームの画像のピクセル同士の対応関係である「継承行列Mt+1/t」を求める。継承行列は、次のフレームｔ＋１の各ピクセル値を、現在のフレームｔのピクセル値の線形結合によって表現する。
【００３０】
４．編集情報の更新
現在のフレームｔの画像に対応する編集情報マップetに、継承行列Mt+1/tを適用して、次のフレームｔ＋１の編集情報マップet+1を作成する。
【００３１】
［２］アンカーフレームにおける編集情報マップの作成
動画の各フレームがnピクセルから成るとすると、各ピクセルに対してi=1,….,nという番号を与えることができる。ここで、ユーザによりピクセルiに与えられる編集パラメータを＾giとおく。またユーザ入力が行われているかを表すラベルを＾wiとおく。具体的には＾wiはピクセルiに入力が行われているとき1、行われていないとき0をとる。
【００３２】
最終的にピクセルiに与えられる編集パラメータを＾eiを求めるためのエネルギー関数＾Eを次のように定義することができる。
0005846663.tif 000012
この式において＾zijはピクセルiとjの間の類似度を表し、次のように定義される:
0005846663.tif 000013
ここで、＾xiはピクセルiの位置情報、＾ciはピクセルiのL＊a＊b＊からなる色情報を表すベクトルである。また、定数σsおよびσcは編集情報マップの一貫性を保つべき位置および色近傍の範囲を制御するパラメータである。具体的には、定数σsは位置情報に関する重み付け、定数σcは色情報に関する重み付けである。式(1)は狭義凸関数をなすので、各＾eiでの偏微分が全て0になる点で最小値を取る。||・||２はベクトルのＬ２ノルムである。上記エネルギー関数は、２つの項からなり、前項は、ユーザ入力の編集パラメータと最終の編集情報マップの編集パラメータとの整合性を保証しており、後項は、類似の色を備えた近隣のピクセルには同様の編集パラメータが割り当てられることを保証している。定数＾λは、上記２つの項をバランスさせるものであり、当業者により適宜設定できる。
【００３３】
よって、式(1)を最小化する＾eiはベクトル形式で次のように得られる。
0005846663.tif 000014
ここで＾Zは＾zijを成分に持つ行列であり、＾D、＾Wはi番目の対角成分にそれぞれ
0005846663.tif 000015
を持つ対角行列である。また、gはピクセルiに入力された編集パラメータgiを成分に持つベクトルを表す。式(2)は大規模密行列＾Zを含むため、一般の計算機によってこれを計算することは困難である。そこで＾Zが低ランクかつ半正定値であるという特徴を用いた近似法であるNystrom 法を用いて近似を行う（非特許文献３参照）。
0005846663.tif 000016
【００３４】
［３］継承行列による編集情報マップの移送
アンカーフレームにおいて計算された編集情報マップは継承行列によって、隣接するフレームから順々に伝搬されていく。継承行列は、隣接する２枚のフレームのピクセルの位置情報及びピクセル値情報から計算される行列であり、２枚のフレームが持つピクセルの色を縦に並べたベクトルをIt, It+1のように置くと、
0005846663.tif 000017
のような関係を持つ。
【００３５】
式(3)において、
0005846663.tif 000018
が継承行列であり、右上の添え字は、フレームtからフレームt+1の継承を表す行列であることを示す。
【００３６】
本発明では、各フレームに与えられるべき編集情報マップが式(3)のような関係を持っていることを仮定している。すなわち、フレームtにおける編集情報マップをetのように表すことにすれば、次のような関係式が成り立っていることを仮定している。
0005846663.tif 000019
【００３７】
ここで解くべき問題は、このような線形の関係式を導くような継承行列Mt+1/tをどのように導くかということである。今、あるエネルギー関数の最適解として、式(4)が与えられると考えると、そのエネルギー関数はある行列に関する二次形式をしていると考えられる。そのようなエネルギー関数を定義するために、次のような仮定を置く。
【００３８】
(i)隣接する二枚のフレームにおいて同じ位置にあるピクセルが、類似した色を持つ場合には、その二つのピクセルがもつ編集パラメータも類似している。
(ii)ある一枚のフレームに注目すると、そのフレーム内で距離が近く、色が類似している場合には、その二つのピクセルが持つ編集パラメータも類似している。
【００３９】
この仮定をもとに次のような二つの重みづけ関数を定義する。
0005846663.tif 000020
式(5)および(6)において、ctiはフレームtの位置iに存在するピクセルのL＊a＊b＊色情報を表し、xtiはフレームtのピクセルの位置を表す。またこれらの式において用いられている三種類のパラメータσct、σsおよびσcは各成分の違いをどの程度許容するかという値になっている。具体的には、定数σctは時間軸方向における色情報の差に関する重み付け、定数σsは位置情報に関する重み付け、定数σcは色情報に関する重み付けであり、当業者により適宜設定される。
実験において用いられているパラメータは表３に示した。
【００４０】
これらの重み付け関数を用いて、次のようなエネルギー関数を定義する。
0005846663.tif 000021
エネルギー関数は２つの項からなる。前項は、編集情報マップの時間軸方向の連続性を保証するものであり、後項は、同じフレーム内での編集パラメータの一貫性を保証している。式(6)に規定するように、編集パラメータの一貫性は、ピクセルの空間位置及び色の類似性に従うものである。λは、上記２つの項をバランスさせる定数であり、当業者により適宜設定される。このエネルギー関数も式(1)同様に狭義凸関数をなすため、これを最小化するような解は一つに決まる。
【００４１】
式(7) を各et+1i、i=1,….,nで偏微分することで得られるn本の方程式が0になるとすると、
0005846663.tif 000022
という関係式が得られる。これを改めてベクトルと行列を用いて書き直すと次のようになる。
0005846663.tif 000023
ただしDt+1/tはn×nの対角行列で、そのi番目の対角要素が
0005846663.tif 000024
となっている。
Wt+1/tも同様にn×nの対角行列で、その対角要素はwt+1/tiである。この関係式は式(4)と同じ形をしており、目的の継承行列が求められている。この継承行列も計算のためには大規模密行列Zt+1の積を計算する必要があり、式(2)同様にNystrom法を用いた近似が必要である。
【００４２】
次に、改良された編集量伝搬行列の導出について説明する。あるフレームに与えられた編集量を伝搬する問題では一般にフレームtからt+1への編集量の伝搬を考える。ここでは簡単のため、フレーム1から2 への伝搬を説明する。前処理として、フレーム1について予め編集量を計算しておく。各フレームに含まれる画素数をn として、フレーム1に対する編集量をe1=(e11,…,e1n)Tのように表す。目的は、このe1からe2を求めることである。e2 を求めるため、色と位置が近い二つの画素は似た編集量を持つと仮定して目的関数を導く。
画素特徴ベクトルf ti (t=1,2,i=1,…,n) を画素のL*a*b*色情報と位置(xti, yti )から、
0005846663.tif 000025
と表す。この際、ftiの各成分は色成分がσcで、位置成分がσsで適当にスケーリングされている。画素間の類似度はftiから、
0005846663.tif 000026
と定義する。先ほどの仮定に基づくと、e2を求めるための目的関数は次のようになる。
0005846663.tif 000027
この目的関数を最小化するe2が編集量である。
目的関数を最小化するため、目的関数を各e2iで偏微分すると、次式が得られる。
0005846663.tif 000028
各iに対して求まる式を行列形式で書き直す。そのために、新たに二つのｎ次正方行列Zkl、Dklを次のように定める。
0005846663.tif 000029
但し、diag{・・・}は{・・・}を対角成分に持つ対角行列を表す。すると、上記式は、
0005846663.tif 000030
と書き直せる。証明は省略するがD22＋1/2D21−Z22は正定値行列なので逆行列が求まり、
0005846663.tif 000031
となる。M21が編集量伝搬行列である。
編集量伝搬行列 は大規模行列の積によって書き表されるため、そのまま計算するのは現実的でない。そこで従来法（非特許文献３）と同様Nystrom 法を用いて行列を近似する。提案法と従来法 の相違点は以下の二点である。
1) 一般のNystrom 法を拡張し、非対称の類似度行列を近似する。
2) 行列自体の近似精度ではなく、行列とベクトルの積の近似精度に注目する。
一般のNystrom 法は対称半正定値行列を対象としているため、Z21のような非対称の類似度行列を扱うことはできない。そこで、次のようなブロック行列を考える。
0005846663.tif 000032
この行列は対称半正定値であり、Nystrom法により近似できる。
【００４３】
［４］継承行列の近似
継承行列を含め、式(2)なども計算には大規模密行列Zt+1/tあるいは＾Zの計算を行う必要がある。ところが、これらの行列は画像のピクセル数nに対してn×nの大きさであり、一般的な計算機で計算を行うことは、行列を保持するための記憶部の容量と計算時間の両面から困難である。以下では、簡単のために、行列の添え字を省略する。
【００４４】
Nystrom法の適用方法
Nystrom法は行列が低ランクである場合、少ない数の固有値と固有ベクトルだけを用いて効率的に行列を近似することができる。この固有値および固有ベクトルを近似的に求めるためにNystrom 法では元の行列の列ないし行をサンプリングする（非特許文献６）。
【００４５】
本手法は2枚の隣接するフレームごとにNystrom法による近似が必要であるため、従来の列をサンプリングするNystrom法では精度が不十分であった。そのため、本実施形態ではZhangらが提案したk-means法に基づくNystrom法（非特許文献７）を用いる。
【００４６】
まず、入力されたフレームをピクセルのL＊a＊b＊色情報と位置の情報に基づきk-means法でクラスタリングする。本来は、行列Zのランクを用いてk個のクラスタに分割するのが理想的であるが、実際にこのkを求めるには、ある程度の計算量が必要であること、無視しても差し支えない小さな固有値によりkが必要以上に大きくなってしまうことを防ぐためサンプル数mを設定する。入力データをm個のクラスタに分解したとすると、それぞれのクラスタについてクラスタ中心
0005846663.tif 000033
が得られる。これを用いて、次の行列
0005846663.tif 000034
を計算する。
0005846663.tif 000035
【００４７】
この行列UおよびAを用いると、Nystrom 法により
0005846663.tif 000036
という近似が得られる。
継承行列の近似に必要な残りの計算は
0005846663.tif 000037
であるが、これはWoodburyの公式あるいは逆行列の補題と呼ばれる定理を用いることで次のように計算が可能である。
0005846663.tif 000038
この式は、小さな行列同士の積のみから成り立っており、実際に計算が可能である。以上の計算方法を用いることで、継承行列は以下のように近似される。
0005846663.tif 000039
この近似した継承行列をアンカーフレームにおいて計算された編集情報マップに順々に適用していくことで、最終的な動画編集の結果を得る。
行列Ｚは、下記のように、より小さなサイズの行列Ｕ、Ａの積で表現され、継承行列を再現するためには上述の式の行列Ｕ、行列Ａ、行列Ｗを保存しておけばよい。
0005846663.tif 000040
【００４８】
さらに、Nystrom法による近似の他の態様について説明する。
通常のNystrom 法は半正定値対象行列Z とその低ランク近似Z〜の間で、
0005846663.tif 000041
ができる限り小さくなるように行列を近似をする。このとき‖・‖＊は行列のスペクトル・ノルムあるいはフロベニウス・ノルムを指す。スペクトル・ノルムとは行列の最大特異値に対応する値であり、フロベニウス・ノルムとは行列の各成分の二乗和の平方根をとったもので、それぞれ次のように表される。
0005846663.tif 000042
応用においては半正定値行列Z がデータ列｛ｘi｝Ni=1からガウス・カーネルを用いて計算される行列として、
0005846663.tif 000043
のように計算されることが多い。ただし、Z = (zij)1≦I,j≦Nのように書くとき、Zの(i,j)成分がzijであることを表すものとする。この式に示す行列を、データ列から計算される類似度行列とよぶ。
Zhangらのk-means法を用いたNystrom法はこのデータ列をあらかじめK個のクラスタに分割する。これを{ck}Kk=1とする。元の行列Zは次のように近似される。
0005846663.tif 000044
提案するNystrom 法におけるサンプリングについて説明する。本発明に係る動画編集法では第1フレームと第2フレームがそれぞれもつN個の画素、すなわち合計2N個の画素特徴から計算される巨大な行列を近似する必要がある。一般にk-means法の計算量は入力データ数n、出力クラスタ数k、反復回数sに対してO(nks)となり、それほど高速でない。
また、ZhangらのNystrom法をそのまま適用すると編集パラメータの情報を全く反映することなくクラスタ中心が計算されるため、比較的小さな画像領域に編集パラメータが割り当てられている場合に適切な編集結果が得られないことがある。
そこで、より高速に、かつ編集パラメータを反映した行列近似を行うことを考える。
改良手法では、k-means 法により特徴ベクトルをクラスタリングする際、第1フレームと第2フレームでは画素特徴(色と位置と編集パラメータ)の分布が非常に近いと仮定し、第1フレームのみを以下の距離関数に従ってクラスタリングする。すなわち、画像情報（色情報、位置情報）に加えて編集パラメータもクラスタリングに利用する。
0005846663.tif 000045
ただし画素特徴fi 〜はこれまでの色と位置のみによる定義fiから
0005846663.tif 000046
という定義に拡張したものである。この画素特徴ベクトルを拡張画素特徴ベクトルと呼ぶ。
これにより得られたクラスタ中心を{ck〜} とする。各ck〜は拡張画素特徴ベクトルと同じ次元を持つ。このクラスタ中心から色と位置の成分だけを取り出した物をckとする。あとはこれをサンプル点として上述の近似式に従い、Zhang らのNystrom 法を実行する。
【００４９】
［５］動画編集の結果
本実施形態に係る手法による動画編集の結果を図2、3および4に示す。それぞれの結果から、継承行列を用いた動画編集法の特徴について説明を行う。なお、各図はグレースケール画像であるが、望ましいと考えた場合には、審査時に物件提出書でカラー画像を提出する用意がある。
【００５０】
図2に注目すると、入力を行ったフレームに写りこんでいなかった物体についても同系統の色調を有するものを自動的に編集できていることがわかる。これはエネルギー関数である式(7)の第二項においてフレーム内での編集の一貫性を考慮しているためで、新たな物体が入り込んでくるたびにユーザ入力を追加しなくても良いというのは動画編集において利点となるといってもよい。
【００５１】
図3には詳細強調の結果を示した。この詳細強調は定義域変換(domain transform)によるエッジ保存フィルタ（非特許文献８）を用いて各フレームをマルチスケール分解(multi scale decomposition)した後、どのスケールの詳細をどの程度、強調・抑制するかを決定するパラメータ（テクスチャの細かさの度合いを表すパラメータ）を継承行列により伝搬している。この結果からもわかる通り、本手法はどのような編集を行うかという目的に依存せず、その編集が独立したいくつかのパラメータにより行われている場合にはいかなる編集法にも適応が可能である。
【００５２】
図4には複数のアンカーフレームにユーザ入力を行った場合の編集結果を示した。通常、複数のフレームにユーザ入力を行う目的は、フレームの進行に伴い蓄積したエラーが原因で起こる不適切な領域分割を防ぐためであることが多い。本手法でもそのような目的でユーザ入力を追加することは可能であるが、実験を行ったいくつかの動画について、編集パラメータの伝搬は適切かつ安定に行われており、その必要性は低いと考えられる。その一方で複数のアンカーフレームに異なる編集を施すことで、より自由度の高い編集を行うことが可能であり、図4には元の動画において黄色であるモミジの葉を、時間経過とともに徐々に赤色に色づかせるという編集を行っている。このように、編集パラメータを安定的に伝搬できるようになったことで、従来は行うことの難しかった複数フレームに対するユーザ入力の可能性を示すことができた。t+1フレームからtフレームへの継承を表す継承行列を導き出すためのエネルギー関数は、表１の右列の式を用いた。
【００５３】
［６］提案手法の応用
本実施形態に係る継承行列を用いた動画編集法は処理の過程を少し変更するだけで、様々な応用が可能である。本節では、その応用例として、グレースケール動画に対する着色処理、動画の色調安定化、および静止画から動画への色転写の手法を紹介する。
【００５４】
［６−１］グレースケール動画の着色処理
グレースケールの静止画に色をつけるという処理は、従来から多くの研究が存在しており、大きく分けると、ユーザ入力をもとにした着色処理（非特許文献１、９）と参照画像を用いた処理に分けられる。ここでは、前者のユーザ入力をもとにした手法を継承行列を用いて動画に拡張する。
【００５５】
着色処理に対し、式(7)をそのまま用いようとすると、第二項のフレーム内の一貫性を保つ項が強く働きすぎてしまい、全体的にぼやけた着色結果となってしまう。これは、グレースケールの画像ないし動画において、全てのピクセルが輝度値の一次元情報のみを持っており、なおかつ全体でその輝度値がそれほど大きくは変わらないということに原因があると考えられる。そこで、本手法を着色処理に用いる場合には、式(7)の第二項をピクセルの近傍のみとの一貫性を保つように変更する。
【００５６】
具体的には以下のような式となる。
0005846663.tif 000047
ただし、この式においてN4(i)はピクセルiの四近傍を指す。この式を用いて得られた動画の着色結果を図5に示す。この結果はアンカーフレームをグラフ探索による静止画像の着色処理（非特許文献９）において行い、その結果を継承行列で伝搬している。
ここで、着色処理について、表１、表２に示す４つの式に対応してまとめると、以下の通りとなる。
0005846663.tif 000048
【００５７】
［６−２］色調安定化処理
動画の色調安定化処理とは、安価なデジタルカメラや携帯電話で動画を撮影した際に起こる色度の揺れを除去する処理である。近年、FarbmanとLischinskiにより提案されたこの処理は、基準となるアンカーフレームから他のフレームの各画素がどの程度色度のずれを起こしているかというのを計算することで実現される（非特許文献１０）。従来手法においては、各フレームごとに信頼度マップやアピアランスマップと呼ばれる複数のパラメータマップを計算する必要があったが、継承行列を用いることで、これらの処理を単純化することが可能である。
【００５８】
あるフレームtにおいて、各ピクセルがアンカーフレームからどの程度の色度のずれを持つかという情報（編集パラメータ）をetiと表すことにする。フレームの進行に伴い、色度のずれは蓄積されていくと考えられるので、その増加分をフレーム間の色度の差により
0005846663.tif 000049
のように表す。
【００５９】
すると、フレームt +1における色度のずれは次のようにして与えられる。
0005846663.tif 000050
ただしLtはフレームtにおける各ピクセルの色度Ltiを成分に持つベクトルで
0005846663.tif 000051
を表す。このようにして得られた動画の色調安定化の結果を図6に示す。
【００６０】
［６−３］画像から動画への色転写
色転写(color transfer)とは、目的とする静止画の色調を参照する静止画の色調に合わせるという手法である（非特許文献１１）。色転写の基本的な考え方は、画像をヒストグラムやガウス混合モデルなどの確率モデルにし、その目的画像の確率モデルを参照画像の確率モデルに近づけることで、目的画像の色調を変化させるというものである。
【００６１】
本手法による静止画から動画への色転写は、まずユーザ入力により領域間の対応付けを行い、その領域間でReinhardのガウス分布に基づいた色転写のパラメータを計算する。Reinhardの手法はL＊a＊b＊の各色成分が目的画像と参照画像の両方でガウス分布をしていると仮定する。今、目的画像のk番目の色成分の平均を
0005846663.tif 000052
標準偏差を
0005846663.tif 000053
参照画像のk 番目の色成分の平均を
0005846663.tif 000054
標準偏差を
0005846663.tif 000055
と表すことにする。
【００６２】
目的画像の元の色を
0005846663.tif 000056
とすると、色転写後の目的画像の色
0005846663.tif 000057
は次のように表される。
0005846663.tif 000058
式（10）は、
0005846663.tif 000059
とおくことで
0005846663.tif 000060
と表せる。そこで本研究ではL＊a＊b＊色空間で各成分についてakおよびbkを計算し、計6次元の情報を継承行列により伝搬した。これにより得られた色転写の結果を図7に示す。
【００６３】
［７］付記
［７−１］継承行列の性質
継承行列Mt+1/tは添え字などを省略すると、対称半正定値行列
0005846663.tif 000061
と二つの対角行列
0005846663.tif 000062
および実数定数
0005846663.tif 000063
を用いて
0005846663.tif 000064
の形で表せる。この行列は次のような特性を持つ。
【００６４】
(i)行列(D−Z)が正則であり、かつWが0かつ非負の対角成分を持つためMt+1/tも正則であり、ゆえに逆行列(Mt+1/t)−1が存在する。
(ii)継承行列Mt+1/tに逆行列が存在すれば式(4)から、それはフレームt+1からフレームtへの逆方向のパラメータの継承を表す。すなわち(Mt+1/t)−1＝Mt+1/tである。
(iii)フレームtからフレームt + kまでの間の継承行列Mt+1/t，…, Mt+k-1/t+kの積はフレームtからフレームt + kへのパラメータの継承を表す。すなわち
0005846663.tif 000065
である。
【００６５】
(i)および(ii)の性質はオプティカルフローなどの位置の対応関係を考えた場合には存在しない性質である。位置の対応関係を行列として表現する場合を考えると、フレーム間でピクセルとピクセル同士の一対一の対応関係が与えられている場合にのみその行列は逆行列を持つ、すなわちフレームt+1のあるピクセルiがフレームtの二つ以上のピクセルと対応関係を持つ場合には、その行列表現が逆行列を持たない。これは位置の対応関係を取る場合においてしばしば起こりうることであり、その点で継承行列は性質が優れた行列であるといってよい。
【００６６】
(iii)の性質は例えばあるフレームに対して行ったユーザ入力から100フレーム後の結果をいきなり求めたい場合などに役に立つ。実際には、Mt/t+kという行列は大規模な行列であり、あらかじめ計算しておくことはできない。そのため、フレームの順序にしたがって結果を求めていく。大容量記憶部を用意して、継承行列を記憶部に保存しておくことで、継承行列をより有用に扱うことができる。
【００６７】
［７−２］編集伝搬の精度とパラメータ
時間軸方向の伝搬の精度は従来法と比べて著しい改善が行えている。なお、フレーム内での編集伝搬の精度については、あまりに細かなユーザ入力を適切に伝搬することは簡単ではない。細かなユーザ入力を区別するためには一貫性を保つべきピクセルの近傍範囲を制御するパラメータσsを小さな値にすることが採用され得るが、σsが0に近づくと類似度行列Zの低ランクであるという性質が失われてしまい、Nystrom法による近似の精度が低下するおそれがある。
【００６８】
近似的なオプティカルフローにより領域ラベルの伝搬を行う従来法（非特許文献５）との比較を図8に示した。従来法は細かなテクスチャに対応できず、またフレームの進行に伴うエラー蓄積も大きいが、本手法では各結果画像に示した通り一般的な動画で5秒程度にあたる150フレームを超えてもおおむね良好に編集の伝搬が行えている。なお、本手法の実装はMATLABおよびC++を用いて行っており、実験は3.6GHzのCPU上で行った。実験で用いたパラメータを表３に示す。ｍは、継承行列の近似におけるサンプル数、ｓは、継承行列計算内の近似にあたって利用されるk-means法の繰り返し計算の回数である。
【表３】
0005846663.tif 000066
【産業上の利用可能性】
【００６９】
本発明は、フレーム間の連続性を保持した動画編集法に係り、従来の動画を扱う処理において一般的であるとされてきたフレーム間の位置の対応関係に頼らず、継承行列を用いたフレーム間の線形結合性によってこれを実現した。継承行列による動画編集は従来法と比べ安定的に編集の伝搬を行うことが可能で、本手法により動画の編集がより少ない手間で行えるようになることが期待される。また継承行列の適応範囲は、色調補正や詳細強調といった単純な編集に限らない。グレースケール動画の着色や色調の安定化、静止画像から動画への色転写など、様々な用途への応用が可能である。本手法の安定性や適応範囲の広さは有用である。
【図１Ａ】
0005846663.tif 000075
【図１】
0005846663.tif 000076
【図２】
0005846663.tif 000077
【図３】
0005846663.tif 000078
【図４】
0005846663.tif 000079
【図５】
0005846663.tif 000080
【図６】
0005846663.tif 000081
【図７】
0005846663.tif 000082
【図８】
0005846663.tif 000083