(57)【要約】コンピュータが実施する方法およびシステムが、第１の動的シーンの映像フレームの第１のシーケンスを、第２の動的なシーンを示す少なくとも２つの映像フレームの第２のシーケンスに変換する。各ｘ，ｙ座標に配置された複数のピクセルを有する少なくとも一つのオブジェクトの動作を表示する第１のシーケンス内の映像フレームのサブセットが取得され、第１の動的シーン内の少なくとも一つのオブジェクトの空間的に重ならない外観を示すサブセットの部分が選択される。この部分は、オブジェクト内のピクセルの各ｘ，ｙ座標を変更することなく、少なくとも３つの異なる入力フレームから、第２のシーケンスの少なくとも２つの連続するフレームにコピーされ、第２のシーケンスの少なくとも一つのフレームが、第１のシーケンス内の異なるフレームで現れる少なくとも２つの部分を含む。【選択図】図１
2009516257.tif 000002
【特許請求の範囲】
【請求項１】
第１の動的シーンの映像フレームの第１のシーケンスを、第２の動的シーンを表示する少なくとも２つの映像フレームの第２のシーケンスに変換するコンピュータが実施する方法であって、当該方法が、
（ａ）ｘ，ｙ座標それぞれに配置された複数のピクセルを備える少なくとも一つのオブジェクトの動作を示す前記第１のシーケンスの映像フレームのサブセットを取得するステップと、
（ｂ）前記第１の動的シーン内の少なくとも１つのオブジェクトの空間的に重複しない外観を示す前記サブセット部分から選択するステップと、
（ｃ）前記オブジェクトのピクセルのｘ，ｙ座標それぞれを変更することなく、前記部分を、少なくとも３つの異なる入力フレームから前記第２のシーケンスの少なくとも２つの連続したフレームにコピーして、前記第２のシーケンスのうちの少なくとも一つのフレームが、前記第１のシーケンスの異なるフレームで現れる少なくとも２つの部分を含むようにするステップとを備えることを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記少なくとも２つの部分が、共通のオブジェクトに関連することを特徴とする方法。
【請求項３】
請求項１または２に記載の方法において、前記サブセットから部分を選択するステップが、関心のあるスコアを決定することを特徴とする方法。
【請求項４】
請求項３に記載の方法において、前記関心のあるスコアが、活動の基準であることを特徴とする方法。
【請求項５】
請求項１乃至４のいずれか１項に記載の方法において、前記第２のシーケンスは、前記第１の動的シーン内の関心のある総てのオブジェクトを含むことを特徴とする方法。
【請求項６】
請求項１乃至４のいずれか１項に記載の方法において、前記第２のシーケンスで現れる前記第１の動的シーン内の関心のある多数のオブジェクトは、前記第２のシーケンスの視覚的な外観を維持しつつ前記オブジェクトの数を最大にすることと矛盾することを特徴とする方法。
【請求項７】
請求項１乃至６のいずれか１項に記載の方法において、前記第１の動的シーンが、所定の位置のカメラによって取得されることを特徴とする方法。
【請求項８】
請求項７に記載の方法において、前記カメラは、前記所定の位置で軸に対して回転し、前記ｘ，ｙ座標がグローバル座標であることを特徴とする方法。
【請求項９】
請求項１乃至８のいずれか１項に記載の方法において、前記第１のシーケンスの少なくとも３つの異なるフレームが、一時的に隣接することを特徴とする方法。
【請求項１０】
請求項１乃至９のいずれか１項に記載の方法であって、前記第２のシーケンスをコピーする前に、少なくとも２つの前記部分を空間的に移動させるステップを含むことを特徴とする方法。
【請求項１１】
請求項１乃至１０のいずれか１項に記載の方法において、選択された部分が、前記第１の動的シーン内で空間的に隣接することを特徴とする方法。
【請求項１２】
請求項１乃至１１のいずれか１項に記載の方法であって、
（ａ）前記第１のシーケンスのフレーム間の画像モーションパラメータを算出し、
（ｂ）前記第１のシーケンス内の映像フレームを移動させて、前記第１の動的シーン内の静止したオブジェクトを映像内で静止させることにより、調整された時空量を生成すべく、映像フレームの第１のシーケンスを事前に整列させるステップを含むことを特徴とする方法。
【請求項１３】
請求項１乃至１２のいずれか１項に記載の方法において、少なくとも一つの選択された部分が、素速く移動するオブジェクトに関連することを特徴とする方法。
【請求項１４】
請求項１２に記載の方法において、画像スライスを選択するステップが、「タイムフロント」表面により前記整列された時空量を一掃し、一連のタイムスライスを生成することを特徴とする方法。
【請求項１５】
請求項１乃至１４のいすれか１項に記載の方法において、前記第１のビデオシーケンス内で同時に発生する２つのイベントが、前記第２のビデオシーケンス内の異なる時間に表示されることを特徴とする方法。
【請求項１６】
請求項１乃至１５のいずれか１項に記載の方法であって、ビデオの概要ために用いられることを特徴とする方法。
【請求項１７】
請求項１６に記載の方法であって、監視のために用いられることを特徴とする方法。
【請求項１８】
請求項１６に記載の方法であって、動画の活動密度（activity density）を増加させるために用いられることを特徴とする方法。
【請求項１９】
請求項１６に記載の方法であって、ビデオインテックスのために用いられることを特徴とする方法。
【請求項２０】
請求項１９に記載の方法であって、前記第２のシーケンス内の各ピクセルのために、前記第１のシーケンス内の対応するピクセルへのポインタを維持するステップを含むことを特徴とする方法。
【請求項２１】
動的シーンを表示する一連の出力映像フレームを明確に実現するデータ記憶媒体であって、前記出力映像フレームの少なくとも２つの連続したフレームが、ｘ，ｙ座標それぞれを有する複数のピクセルであって、オブジェクト内のピクセルのｘ，ｙ座標それぞれを変更することなく、少なくとも３つの異なる入力フレームのオブジェクトの部分から生じる複数のピクセルを備え、前記出力映像フレームのうちの少なくとも一つが、異なる入力フレームで現れる少なくとも２つの部分を含むことを特徴とするデータ記憶媒体。
【請求項２２】
第１の動的シーンの映像フレームの第１のシーケンスを、第２の動的シーンを表示する少なくとも２つの映像フレームの第２のシーケンスに変換するシステム（１０）であって、当該システムが、
ｘ，ｙ座標それぞれに配置された複数のピクセルを備える少なくとも一つのオブジェクトの動作を示す前記第１のシーケンス内の映像フレームのサブセットを格納する第１のメモリ（１２）と、
前記第１の動的シーン内の少なくとも一つのオブジェクトの空間的に重複しない外観を示す前記サブセット部分から選択するための、前記第１のメモリに連結される選択ユニット（１３）と、
前記オブジェクト内のピクセルのｘ，ｙ座標それぞれを変更することなく、前記部分を、少なくとも３つの異なる入力フレームから、前記第２のシーケンスの少なくとも２つの連続したフレームにコピーし、前記第２のシーケンスのフレームのうちの少なくとも一つが、前記第１のシーケンス内の異なるフレームで現れる少なくとも２つの部分を含むフレーム生成部（１４）と、
前記第２のシーケンスのフレームを蓄積する第２のメモリ（１５）とを備えることを特徴とするシステム。
【請求項２３】
請求項２２に記載のシステムがさらに、前記第２の動的シーンを表示すべく、前記第２のメモリに連結されたディスプレイ装置（１６）を備えることを特徴とするシステム。
【請求項２４】
請求項２２または２３に記載のシステムにおいて、前記少なくとも３つの異なる入力フレームが、一時的に隣接することを特徴とするシステム。
【請求項２５】
請求項２２乃至２４のいずれか１項に記載のシステムにおいて、前記フレーム生成部が、前記第２のシーケンスをコピーする前に、少なくとも２つの前記部分を空間的に移動させる移動ユニット（１７）を備えることを特徴とするシステム。
【請求項２６】
請求項２２乃至２５のいずれか１項に記載のシステムがさらに、
（ａ）前記第１のシーケンスのフレーム間の画像モーションパラメータを算出し、
（ｂ）前記第１のシーケンス内の映像フレームを移動させて、前記第１の動的シーン内の静止したオブジェクトを映像内で静止させることにより、映像フレームの第１のシーケンスを事前に整列させる、前記第１のメモリに連結された整列ユニット（１８）を備えることを特徴とするシステム。
【請求項２７】
請求項２２乃至２６のいずれか１項に記載のシステムであって、「タイムフロント」表面により前記整列された時空量を一掃し、一連のタイムスライスを生成すべく、前記選択ユニットに連結されたタイムスライス生成部（１９）を備えることを特徴とするシステム。
【請求項２８】
コンピュータプログラムであって、当該プログラムがコンピュータ上で実行されるときに、請求項１乃至２０のいずれか１項に記載の方法を実行するコンピュータプログラムコード手段を備えることを特徴とするコンピュータプログラム。
【請求項２９】
請求項２８に記載のコンピュータプログラムであって、コンピュータ読み取り可能な媒体に組み込まれることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本出願は、２００６年１１月２日に出願された米国第１０／５５６，６０１（Ｐｅｌｅｇ等）「Method and sytem for spatio-temporal video warping」の一部継続出願であり、２００６年５月１１日に公開されたＷＯ２００６／０４８８７５に対応し、さらに、２００５年１１月１５日に出願された暫定出願第６０／７３６，３１３および２００６年１月１７日に出願された６０／７５９，０４４の優先権を主張し、これらの出願の総ての内容は、参照によりここに組み込まれている。
【０００２】
本発明は、一般に、新しい画像および映像が、シーンの複数のオリジナル映像から部分を統合することにより生成されるレンダリングに基づく画像および映像に関連する。特に、本発明は、映像の抽象化あるいは概要（synopsis）を目的とするこのような技術に関連する。
【０００３】
従来技術
本発明の背景として関連があると考えられる従来技術の引例が、以下に記載されており、これらの内容は、ここに組み込まれている。追加の引例が、前述した米国暫定出願第６０／７３６，３１３および６０／７５９，０４４に記載されており、これらの内容は、参照によりここに組み込まれている。ここに記載された引用の確認は、ここに開示された本発明の特許性に関連する方法であることを意味するものではない。各引用は、角括弧に囲まれた数字により特定され、したがって、従来技術は、明細書全体を通して、角括弧に囲まれた数字により引用される。
［１］ A. Agarwala, M. Dontcheva, M. Agrawala, S. Drucker, A. Colburn, B. Curless, D. Salesin, and M. Cohen. Interactive digital photomontage. ２００４年のシーグラフ（SIGGRAPH）の２９４から３０２ページ。
［２］ A. Agarwala, K. C. Zheng, C. Pal, M. Agrawala, M. Cohen, B. Curless, D. Salesin, and R. Szeliski. Panoramic video textures. ２００５年のシーグラフの８２１から８２７ページ。
［３］ J. Assa, Y. Caspi, and D. Cohen-Or. Action synopsis: Pose selection and illustration. ２００５年のシーグラフの６６７から６７６ページ。
［４］ O. Boiman and M. Irani. Detecting irregularities in images and in video. ２００５年北京におけるＩＣＣＶのページＩ：４６２から４６９。
［５］ A. M. Ferman and A. M. Tekalp. Multiscale content extraction and representation for video indexing. Proc. of SPIE, 3229:23-31, 1997.
［６］ M. Irani, P. Anandan, J. Bergen, R. Kumar, and S. Hsu. Efficient representations of video sequences and their applications. Signal Processing: Image Communi- cation, 8(4):327-351, 1996.
［７］ C. Kim and J. Hwang. An integrated scheme for object-based video abstraction. ２００年ニューヨークにおけるＡＣＭマルチメディア（ACM Multimedia）の３０３−３１１。
［８］ S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 4598(13):671-680, 1983.
［９］ V. Kolmogorov and R. Zabih. What energy functions can be minimized via graph cuts? ２００２年ＥＣＣＶのページ６５から８１。
［１０］ Y. Li, T. Zhang, and D. Tretter. An overview of video abstraction techniques. Technical Report HPL-2001-191, HP Laboratory, 2001.
［１１］ J. Oh, Q. Wen, J. lee, and S. Hwang. Video abstraction. In S. Deb, editor, Video Data Mangement and Information Retrieval, pages 321-346. Idea Group Inc. and IRM Press, 2004.
［１２］ C. Pal and N. Jojic. Interactive montages of sprites for indexing and summarizing security video. In Video Proceedings of CVPR05, page II: 1192, 2005.
［１３］ A. Pope, R. Kumar, H. Sawhney, and C.Wan. Video abstraction: Summarizing video content for retrieval and visualization. In Signals, Systems and Computers, pages 915-919, 1998. 
［１４］ WO2006/048875 Method and system for spatio-temporal video warping, pub. May 11, 2006 by S. Peleg, A. Rav-Acha and D. Lischinski. これは、２００５年１１月２日に出願された米国第１０／５５６，６０１に対応する。
［１５］ A. M. Smith and T. Kanade. Video skimming and characterization through the combination of image and language understanding. １９９８年のＣＡＴＶＤの６１から７０ページ。
［１６］ A. Stefanidis, P. Partsinevelos, P. Agouris, and P. Doucette. Summarizing video datasets in the spatiotemporal domain. ２０００年のＤＥＸＡのワークショップの９０６から９１２。
［１７］ H. Zhong, J. Shi, and M. Visontai. Detecting unusual activity in video.２００４年のＣＶＰＲのページ８１９から８２６。
［１８］ X. Zhu, X. Wu, J. Fan, A. K. Elmagarmid, and W. G. Aref. Exploring video content structure for hierarchical summarization. Multimedia Syst, 10(2): 98-115, 2004.
［１９］ J. Barron, D. Fleet, S. Beauchemin and T. Burkitt.. Performance of optical flow techniques, volume 92, pages 236-242.
［２０］ V. Kwatra, A. Schδdl, I. Essa, G. Turk and A. Bobick. Graphcut textures: image and video synthesis using graph cuts. ２００３年のシーグラフの２２７から２８６ページ。
［２１］ C. Kim and J. Hwang, Fast and Automatic Video Object Segmentation and Tracking for Content-Based Applications, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 12, No. 2, February 2002, pp 122-129.
［２２］米国特許第６，６６５，００３
【背景技術】
【０００４】
映像の概要（video synopsis）は、映像のブラウジングおよび検索を可能にする一時的なコンパクト表現である。
【０００５】
映像の概要のための２つの主要なアプローチがある。一方のアプローチでは、一組の特徴的な画像（キーフレーム）が、オリジナルの映像シーケンスから選択される。選択されたキーフレームは、映像を最もよく表わすフレームである［７，１８］。他方のアプローチでは、短い映像シーケンスの収集が選択される［１５］。第２のアプローチは、コンパクトではないが、シーンの動的性（dynamics）に良い影響を与える。これらのアプローチ（および他のアプローチ）は、映像の抽象化の広範囲な調査に記されている［１０，１１］。
【０００６】
前述した双方のアプローチでは、総てのフレームが、基礎的な基本的要素として利用される。別の方法は、映像のインデックスのためにメタデータと共にモザイク画像を利用する［６，１３，１２］。この方法では、静的な概要画像（synopsis image）は、時間の異なるオブジェクトを含む。
【０００７】
オブジェクトに基づくアプローチが知られており、このアプローチでは、オブジェクトが入力映像から抽出される［７，５，１６］。しかしながら、これらの方法は、重要なキーフレームを特定するオブジェクトの検出を利用し、異なる時間間隔の活動を組み合わせない。
【０００８】
繰り返される最小のカット（iterated min-cut）を利用して単一のパノラマ画像を生成し［１］、繰り返される最小のカットを利用してパノラマ映像を生成する［２］する方法が、本分野で知られている。この２つの方法では、（入力フレームの数の）指数の複雑さに関する問題が近似され、したがって、これらは、少数のフレームにより適切である。本分野の関連する研究は、最小のカットを利用して２つの映像を組み合わせることに関連する［２０］。
【０００９】
ＷＯ２００６／０４８８７５［１４］は、映像の一時的な流れを操作する方法およびシステムを開示している。第１の動的シーンの映像フレームの第１のシーケンスは、第２の動的シーンを表示する映像フレームの第２のシーケンスに変換され、一の態様では、第１の動的シーン内の少なくとも一つの特徴の場合、映像フレームの第１のシーケンスの各部分は、映像フレームの第１のシーケンスの周辺部分よりも異なるレートで標本化され、標本化された部分は、第２のシーケンスの対応するフレームにコピーされる。これにより、動的シーン内の特徴の一時的な同期が変更できる。
【発明の開示】
【課題を解決するための手段】
【００１０】
本発明の第１の態様によると、第１の動的シーンの映像フレームの第１のシーケンスを、第２の動的シーンを表示する少なくとも２つの映像フレームの第２のシーケンスに変換するコンピュータが実施する方法が提供され、当該方法が、
（ａ）ｘ，ｙ座標それぞれに配置された複数のピクセルを備える少なくとも一つのオブジェクトの動作を示す前記第１のシーケンスの映像フレームのサブセットを取得するステップと、
（ｂ）前記第１の動的シーン内の少なくとも１つのオブジェクトの空間的に重複しない外観（non-spatially overlapping appearance）を示す前記サブセット部分から選択するステップと、
（ｃ）前記オブジェクトのピクセルのｘ，ｙ座標それぞれを変更することなく、前記部分を、少なくとも３つの異なる入力フレームから前記第２のシーケンスの少なくとも２つの連続したフレームにコピーして、前記第２のシーケンスのうちの少なくとも一つのフレームが、前記第１のシーケンスの異なるフレームで現れる少なくとも２つの部分を含むようにするステップとを備える。
【００１１】
本発明の第２の態様によると、第１の動的シーンの映像フレームの第１のシーケンスを、第２の動的シーンを表示する少なくとも２つの映像フレームの第２のシーケンスに変換するシステムが提供され、当該システムが、
ｘ，ｙ座標に配置された複数のピクセルを備える少なくとも一つのオブジェクトの動作を示す前記第１のシーケンス内の映像フレームのサブセットを格納する第１のメモリと、
前記第１の動的シーン内の少なくとも一つのオブジェクトの空間的に重複しない外観を示す前記サブセット部分から選択するための、前記第１のメモリに連結される選択ユニットと、
前記オブジェクト内のｘ，ｙ座標それぞれを変更することなく、前記部分を、少なくとも３つの異なる入力フレームから、前記第２のシーケンスの少なくとも２つの連続したフレームにコピーし、前記第２のシーケンスのフレームのうちの少なくとも一つが、前記第１のシーケンス内の異なるフレームで現れる少なくとも２つの部分を含むフレーム生成部と、
前記第２のシーケンスのフレームを蓄積する第２のメモリとを備える。
【００１２】
本発明の第３の態様はさらに、動的シーンを表示する一連の出力映像フレームを確実に実施するデータキャリアを備えており、前記出力映像の少なくとも２つの連続したフレームは、ｘ，ｙ座標それぞれを有する複数のピクセルであって、オブジェクト内のピクセルのｘ，ｙ座標それぞれを変更することなく、少なくとも３つの異なる入力フレームのオブジェクトの部分から生じる複数のピクセルを備え、前記出力映像フレームのうちの少なくとも一つが、異なる入力フレームで現れる少なくとも２つの部分を含む。
【００１３】
本発明により開示された動的な映像概要（video synopsis）は、前述した従来の映像の抽象化手段と、以下の２つの特定において相違する。（ｉ）映像概要自体が、シーンの動的性を表示する映像である。（ｉｉ）時空間の重複（spatio-temporal redundancy）をできる限り低減すべく、活動の相対的なタイミングを変更する。
【００１４】
例えば、図１の空間時間量（space-time volume）で表わされる概略的な映像クリップを検討する。映像は、地面を歩く人で始まり、活動のない期間の後、鳥が空を飛んでいる。活動のないフレームは、多くの映像の抽象化の方法では省略される。映像概要は、人と鳥を同時に表示することにより実質的によりコンパクトである。これは、他の活動がこの空間的な位置で生じない場合、オリジナルの時間間隔から別の時間間隔にイベントをシフトさせることによる画像領域の最適利用を可能にする。このような操作は、初めに［１４］に示したように、年代のコンシステンシー（chronological consistency）を緩和する。
【００１５】
また、本発明は低レベルの方法を提供し、マルコフ確率場の最適化を利用して概要映像を生成する。
【００１６】
本発明により提供される選択肢のうちの一つは、単一のオブジェクトの複数の動的な外観を表示する能力である。この効果は、移動するオブジェクトの従来の映像概要で用いられる「ストロボ観察（strobo-scopic）」画像の一般化である［６，１］。これを実行する２つの異なるスキームが提供される。第１のスキームでは、異なる時間の事例におけるオブジェクトのスナップショットは、開始位置から終了位置までの映像全体のオブジェクトの経過の指標を提供すべく出力映像で提供される。第２のスキームでは、オブジェクトは、開始あるいは終了位置を定義しないが、ランダムに予測不可能に移動する。この場合、異なる時間の事例におけるオブジェクトのスナップショットが再び、出力映像として提供されるが、この時間は、実際よりも多いオブジェクトの印象を与える。双方のスキームが共通点は、入力映像から異なる時間に取得される複数のスナップショットが、空間的な重複を避け、且つ関心のあるオブジェクトの動的な経過に寄与しないコピーしない方法により、入力映像から出力映像にコピーされることである。
【００１７】
本発明の内容および添付の請求項では、「映像（video）」の語は、最も一般的な用語の「動画（movie）」と同義であり、これは、ポスト処理に従うコンピュータ画像ファイルとしてアクセス可能であり、任意の種類の動画ファイル、例えばデジタル、アナログを含む。カメラは、回転およびズームが可能な所定の位置にあることが好適であるが、これまで提案された技術で行われるような影響を受けやすい並進運動ではない。本発明に関連するシーンは、例えば、米国特許６，６６５，００３［２２］および動的なシーンを表示しない立体的な画像の表示を目的とする他の引例で処理される静的なシーンと反対に動的であり、連続したフレームが空間的および時間的な連続性を有する。本発明の一の多様によるうと、我々はこの問題を、グラフ上の最大の流れを見つけることにより多項式時間で説くことができる単一の最小のカットの問題として定式化する［５］。
【００１８】
本発明を説明するために、「空間時間量」と称する構成が利用され、動的なパノラマ映像を生成する。空間時間量は、総てのフレームを時間軸に沿って順次スタックすることにより画像の入力シーケンスから構成される。しかしながら、実際の実施に関する限り、例えば、動的なソースシーンの２Ｄフレームを時間内にスタックすることにより空間時間量を実際に構成する必要はないことを理解すべきである。さらに通常は、ソースフレームは、ターゲットフレームを構成するために個々に処理されるが、空間時間量を概念的な構成でなく物理的な構成であるかのように参照することは理解を助けるであろう。
【００１９】
本発明を理解し、本発明が実際にどのように実行されるか理解するために、好適な実施例は、限定ではなく添付図面を参照することにより説明される。
【発明を実施するための最良の形態】
【００２０】
１．活動検出
本発明は、総ての入力ピクセルが「重要度」のレベルが付されていると仮定する。これ以降、活動レベルを「重要度」のレベルとして使用するが、所望の応用例に基づいて他の測定値を「重要度」として使用できることは明らかであろう。重要度（あるいは活動）レベルの評価が想定され、それ自体は本発明の特徴ではない。これは、不規則性を検出し［４，１７］、オブジェクト検出を移動させ、オブジェクトトラッキングを行う様々な手段のうちの一つを利用して行うことができる。代替的に、これは、顔認識などの認識アルゴリズムに基づいて行うことができる。
【００２１】
例えば、単一且つ共通で使用される活動インジケータが選択され、入力ピクセルＩ（ｘ，ｙ，ｔ）は、位置（ｘ，ｙ）における時間的なメジアンからの色差が所定の閾値よりも大きい場合、「アクティブ」とされる。アクティブピクセルは、特有の関数により既定される。
2009516257.tif 000003
【００２２】
活動インジケータからノイズを除去すべく、メジアンフィルタが、概要（synopsis）処理を継続する前にχに適用される。
【００２３】
連続的な活動測定を利用できるが、本発明は２元の事例に焦点を合わせる。連続的な活動の測定は、以下の詳細な説明のほぼ総ての等式を僅かに変更するだけで行うことができる［４，１７，１］。
【００２４】
我々は、映像概要の算出のための２つの異なる実施例を記載する。１つのアプローチ（セクション２）は、グラフカットを用いたグラフ表現および費用関数の最適化を利用する。別のアプローチ（セクション３）は、オブジェクトセグメンテーションおよびトラッキングを利用する。
【００２５】
２．エネルギーの最小化による映像概要
入力映像シーケンスのＮ個のフレームを３Ｄの空間時間量Ｉ（ｘ，ｙ，ｚ）で表示させ、この場合、（ｘ，ｙ）はこのピクセルの空間的な座標であり、１≦ｔ≦Ｎがフレームの数である。
【００２６】
我々は、以下の特性を有する概要映像Ｓ（ｘ，ｙ，ｚ）を生成する。
・映像概要Ｓは、オリジナル映像Ｉよりも実質的に短くあるべきである。
・オリジナル映像の最大の「活動」は、要約映像内で現れるべきである。
・映像概要内のオブジェクトの動作は、オリジナル映像内の動作と同様であるべきである。
・映像概要は、見栄えがよく、目に見える継ぎ目（シーム）あるいは断片化したオブジェクトは阻止されるべきである。
【００２７】
前述した特性を有する概要映像Ｓは、マッピングＭを利用して生成され、概要Ｓ内の総ての座標（ｘ，ｙ，ｚ）に、Ｉからのソースピクセルの座標を割り当てる。我々は、空間的な位置を固定しつつ、ピクセルのタイムシフトに焦点を合わせる。したがって、概要ピクセルＳ（ｘ，ｙ，ｚ）は、入力ピクセルＩ（ｘ，ｙ，Ｍ（ｘ，ｙ，ｔ））から生じる。タイムシフトＭは、エネルギーの最小化の問題を解決することにより得られ、費用関数は、以下の等式により得られる。
2009516257.tif 000004
ここで、Ｅａ（Ｍ）は活動の損失を示し、Ｅｄ（Ｍ）は継ぎ目における不連続性を示す。活動の損失は、概要映像Ｓ内で現れない入力映像Ｉのアクティブピクセルの数であろう。
2009516257.tif 000005
【００２８】
不連続性費用（discontinuity cost）Ｅｄは、概要映像内の空間および時間的な隣接部分と、入力映像内の対応する隣接部分との間の継ぎ目における色差の合計として既定される（同様の等式が[１]に存在する）。
2009516257.tif 000006
ここで、ｅｉは、６つの空間および時間的な隣接部分を表わす６つのユニットである。
【００２９】
図２ａおよび２ｂは、費用関数を最小化することにより短い映像概要を生成する空間および時間的な処理を表わす概略図であり、移動するオブジェクトの動作は、図中の「活動ストリップ」により表わされる。上図はオリジナルの映像を示しており、下図は映像概要を示している。特に図２ａでは、短い映像概要Ｓは、多くのアクティブピクセルを含むことにより入力映像ｌから生成される。円滑にすべく、Ｓ内のピクセルＡがｌ内のピクセルＢに対応する場合、「境界を越えた」隣接部分は同様であるべきである。最適なＭ最小化（３）を発見することは、非常に大きな最適化の問題である。近似解が図２ｂに示されており、概要映像内の連続したピクセルは、連続した入力ピクセルから生成されるように限定されている。
【００３０】
費用関数Ｅ（Ｍ）（等式１）は３次元のマルコフ確率場に対応し、各ノードは、出力映像の３次元体積内のピクセルに対応し、入力フレームに対応する時間的価値が割り当てることができることに留意する。ノードの重みは、活動費用により決定され、ノード間のエッジは、不連続性費用に応じて決定される。したがって、費用関数は、反復するグラフカット（iterative graph-cuts）などのアルゴリズムにより最小化することができる［９］。
【００３１】
２．１．２Ｄグラフを利用した限定的な解決方法
映像概要内の各ピクセルが任意の時間に生じることを可能にする等式（１）の最適化は、大きな問題である。例えば、５秒の映像概要に要約される３分の入力映像は、それぞれが５４００ラベルを有する約２２５ノードを有するグラフを生じる。
【００３２】
水平な経路を移動する動的なテクスチャあるいはオブジェクトの場合、３次元のＭＲＦは、この問題を１次元の問題に低減させることにより効果的に解決できることが［２］に記載されていた。この研究において、我々は、より一般的な方法で移動するオブジェクトに取り組み、したがって、我々は異なる制約を用いる。概要映像Ｓ内の連続したピクセルは、入力映像Ｉ内の連続したピクセルから生じるように制限されている。この制限の下では、３次元のグラフは、２次元のグラフに減らされ、各ノードは、概要動画内の空間的な位置に対応する。各ノードＭ（ｘ，ｙ）のラベルは、図２ｂに示すように、Ｓの第１のフレームに示すＩ内のフレーム数ｔを決定する。Ｍ（ｘ１，ｙ１）≠Ｍ（ｘ２，ｙ２）の場合、継ぎ目は、２つの隣接する位置（ｘ１，ｙ１）と（ｘ２，ｙ２）との間に存在し、継ぎ目に沿った不連続性費用Ｅｄ（Ｍ）は、Ｓ内の総てのフレームに跨るこの空間的な位置における色差の合計である。
2009516257.tif 000007
ここで、ｅｉは、４つの空間的な隣接部分を示す４つの単位ベクトルである。
【００３３】
各ノードのラベルの数はＮ−Ｋであり、ＮおよびＫは、入力および出力映像それぞれのフレームの数である。各ピクセルの活動の損失は、
2009516257.tif 000008
である。
【００３４】
３．オブジェクトに基づく概要
前述した動的な映像概要の低いレベルのアプローチは、目に見える継ぎ目を防止するといった局所的な特性に限定されている。高いレベルのオブジェクトに基づく特性は、オブジェクトが検出できる場合に取り入れることができる。例えば、ストロボ効果を避けることは、体積内の各オブジェクトの検出およびトラッキングを必要とする。このセクションでは、動的な映像概要のためのオブジェクトに基づくアプローチの実施について説明する。いくつかのオブジェクトに基づく映像の要約方法は、文献（例えば、［７，５，１６］）に存在し、これらは総て、重要なフレームの選択するために、検出されたオブジェクトを利用する。これらの方法とは違い、本発明は、時間内にオブジェクトを移動させ、入力シーケンス内に現れない新しい概要フレームを生成し、空間および時間を有効に利用する。
【００３５】
一実施例では、移動するオブジェクトは、前述したように、各ピクセルを時間的なメジアンと比較し、この違いを閾値化することにより検出される。この後、空間的なメジアンフィルタを利用したノイズクリーニングが行われ、空間および時間的に関連する構成要素が組み合わされる。文献内には、このタスクのために利用されるオブジェクト検出およびトラッキングのための多くの他の方法が存在することは理解できるであろう（例えば、［７，１７，２１］）。オブジェクト検出およびトラッキングの各処理は、一組のオブジェクトを生成し、各オブジェクトｂは、特有の関数により表わされる。
2009516257.tif 000009
【００３６】
図３ａ，３ｂ，３ｃは、本発明による時間的な再配置の例を示した図である。各図の上図は、オリジナルの映像を表わしており、下図は、映像概要を表わしており、移動するオブジェクトの動作は、図中の「活動ストリップ」により表わされる。図３ａは、異なる時間に記録され、映像概要の同じ時間間隔で移動する２つのオブジェクトを示している。図３ｂは、長い期間移動し、短い時間間隔を有するセグメントに分割される単一のオブジェクトを示しており、これは、同時に表示され、動的なストロボ効果を生成する。図３ｃは、オブジェクトの体積がセグメントに分割される場合に、オブジェクトの交差が概要を妨げないことを示している。
【００３７】
各オブジェクトから、セグメントは、オブジェクトが現れるフレームのサブセットを選択することにより生成される。このようなセグメントは、異なる時間間隔を表わすことができ、任意で異なる標本化レートで取得される。
【００３８】
映像概要Ｓは、以下の処理を用いて、入力映像Ｉから構成される。
（１）オブジェクトｂ１．．．ｂｒは、入力映像Ｉから抽出される。
（２）一組の重ならないセグメントＢは、オリジナルのオブジェクトから選択される。
（３）時間的なシフトＭは、選択された各セグメントに適用され、短い映像概要を生成するとともに、オブジェクト間の重なりを阻止し、継ぎ目のないステッチ（stitching）を可能にする。これは、図１および図３ａ乃至３ｃに説明されている。図４は、映像概要の単一のフレームが図３ｂに示す動的なストロボ効果を利用する例を示した図である。
【００３９】
我々が処理（２）および（３）を時間内に選択およびシフトさせ、短くて継ぎ目の無い映像概要を取得するため、処理（２）および（３）は関連している。前述した処理（２）および（３）は、完全である必要はないことは理解できるであろう。「空間的に重複しないセグメント（non-spatially overlapping segment)」という場合には、小さな重複部分が許容され、「重なりを阻止する」という場合には、時間内に移動するオブジェクト間の小さな重なりは許容されるが、これは、視覚的に魅力的な映像を得るために最小限にすべきである。
【００４０】
オブジェクトに基づく表示では、生成された概要内のピクセルは、複数のソース（異なるオブジェクトから生成され）を有し、したがって、我々は、総てのオブジェクトが統合される後の処理ステップを付加する。背景画像は、シーケンスの総てのフレームにおけるピクセルのメジアン値を取得することにより生成される。次に、選択されたオブジェクト」は、各フレーム内のピクセルとメジアン画像との間の距離（ＲＧＢ空間内）に比例した重み付けを利用して融合可能である。このステッチ機構は、［６］で使用されるものと同様である。
【００４１】
我々は、単一の概要ピクセルにマップされる一組の総てのピクセル（ｘ，ｙ，ｔ）∈Ｓを、ｓｒｃ（ｘ，ｙ，ｔ）として規定し、我々は、オブジェクト（あるいはセグメント）ｂ内の（アクティブ）ピクセルの数を＃ｂ＝Σｘ，ｙ，ｔ∈Ｉχｂ（ｘ，ｙ，ｔ）とする。
【００４２】
我々は、セグメントＢのサブセット選択および時間的なシフトＭの費用を測定するエネルギー関数を定める。費用は、活動の損失Ｅα、オブジェクトＥＯ間の重なりのペナルティ、および長い概要映像にペナルティを課す項Ｅｌを含む。
2009516257.tif 000010
ここで、
2009516257.tif 000011
である。
【００４３】
３．１．所定の長さを有する映像−概要
ここで、所定の長さＫの短い概要映像が、長い映像で構成される事例を説明する。このスキームの場合、各オブジェクトは、長さＫを有する重複し連続するセグメントに分割される。総てのセグメントは、時間的に推移してタイムｔ＝１で開始し、いずれのセグメントが概要映像内に含まれるか決定する必要がある。明らかに、このスキームでは、いくつかのオブジェクトが概要データ内に現れない。
【００４４】
初めに、我々はセグメントの総ての対の重なりの費用を決定する。ｂｉおよびｂｊ
を出現時間ｔｉおよびｔｊを有する２つのセグメントとし、各セグメントのサポートを（等式５のような）特有の関数χにより表わす。
【００４５】
これらの２つのセグメントの費用は、時間ｔ＝１になった後の２つのセグメントの色差の合計として決定される。
2009516257.tif 000012
【００４６】
概要映像の場合、我々は、等式６の費用を最小化するセグメントＢの部分的なセットを選択し、ここでは、Ｅｌは、定数Ｋであり、重なり費用は、
2009516257.tif 000013
により求められる。
【００４７】
同じ空間および時間ピクセルが２回表示される（これは、許容可能であるが無駄である）のを阻止すべく、我々は、オリジナルの動画を横切るセグメントｂｉおよびｂｊのために、ｖ（ｂｉ，ｂｊ）＝∞と設定する。さらに、ストロボ効果が必要ない場合、ストロボ効果は、同じオブジェクトから標本化された総てのｂｉおよびｂｊのために、ｖ（ｂｉ，ｂｊ）＝∞と設定することにより避けられる。
【００４８】
擬似的なアニーリング（simulated annealing）［８］は、エネルギー関数を最小化するために利用される。各状態は、概要内に含まれるセグメントのサブセットを示しており、隣接する状態が、設定するために取得され、セグメントが取り除かれ、追加され、あるいは別のセグメントと交換される。
【００４９】
セグメントの選択の後、長さＫの概要動画は、総ての変化したセグメントを結合することにより構成される。この手段を利用した映像概要の一つのフレームの例が。図４に示されている。
【００５０】
２．２．無損失映像概要
映像監視などのいくつかの応用例の場合、我々は、長い概要映像を好むが、総ての活動が現れるのが保証される。この場合、オブジェクトは、先行するセクションで行われた一組のオブジェクトのセグメントを選択するためのものでないが、オブジェクトのセグメントのコンパクトな時間的な再配置を発見するためのものである。
【００５１】
さらに、我々は、擬似アニーリングを用いてエネルギーを最小化する。この場合、状態は、総てのセグメントの一組のタイムシフトに対応し、２つの状態は、タイムシフトが単一のセグメントのためにのみ変化する場合、隣接部分として定義される。この場合、注意すべき２つの問題がある。
・最初あるいは最後のフレーム内で現れるオブジェクトのセグメントは、概要映像内に残るべきである（さもなければ、これらは突然現れるか消える）。我々は、各状態が、これら総てのオブジェクトの時間的なシフトを結果的に固定することにより、この制約を満足させることに留意する。
・入力映像の時間的な配置は、共通するエネルギー関数の局所的な最小化であり、したがって、アニーリング処理を初期化する好適な選択肢ではない。我々は、短い映像を有する擬似アニーリングを初期化し、総てのオブジェクトが重なる。
【００５２】
図５ａ，５ｂおよび５ｃは、短い概要が、ストロボ効果がなく活動の損失がない長いシーケンスを表示可能である場合に、この手段を示す図である。３つのオブジェクトは、同時に表示されるようにタイムシフトできる。特に、図５ａは、オリジナルの映像（上図）および映像概要（下図）の空間および時間的な概略図である。図５ｂは、オリジナルの映像の３つのフレームを示しており、図５ａに示すように、オリジナルの映像では、各人物が個別に現れているが、概要映像では、３つの総てのオブジェクトが一緒に現れる。図５ｃは、３人を同時に示す概要映像の１つのフレームを示している。
【００５３】
４．パノラマの映像概要
ビデオカメラがシーンをスキャンする場合、パノラマのモザイクを用いて多くの冗長な部分が取り除かれる。しかし、従来の方法は、シーンの動的性が損なわれる単一のパノラマ画像を構成する。制限された動的性は、ストロボ画像により表わすことができ［６，１，３］、移動するオブジェクトは、これらの経路に沿っていくつかの位置で表示される。
【００５４】
パノラマの概要映像は、異なる時間にシーンの異なる位置で行われる活動を同時に表示させることにより生成できる。実質的な圧縮が得られ、各オブジェクトの活動の期間が時間に制限されるため、カメラにより表示される。特別な事例は、カメラが、図６に示す走っているライオンなどのオブジェクトをトラックする場合である。カメラが、走っているライオンをトラックする場合、概要映像は、背景のパノラマのモザイクであり、前景は、走っているライオンのいくつかの動的なコピーを含む。この場合、短い映像概要は、ストロボ効果を許可するだけで取得できる。
【００５５】
パノラマの映像概要を構成することは、総てのフレームをいくつかの基準フレームに整列させる予備の段階で、通常の映像概要と同様の方法により行われる。整列の後、オブジェクトの画像の座標が、入力画像のうちの一つの座標系であるグローバル座標から取得される。
【００５６】
映像を処理を可能にすべく、移動するオブジェクトのセグメンテーションが完全でない場合でさえ、我々は、重なった部分を完全に阻止する代わりに当該部分にペネルティを課す。この重なった部分のペナルティにより、オブジェクトの時間的な配置の順応性を可能にし、セグメンテーションが完全でない場合でさえ、オブジェクトのピクセルは、いくつかの背景を含む。
【００５７】
付加的な期間が追加され、概要映像の時間的な順序を入力映像の順序に偏向させる。
【００５８】
総ての可能なセグメントセクションＢおよび時間的なシフトＭの前述したエネルギーを最小化することは、可能性が非常に多いため、非常に消耗的である。しかしながら、問題は、解決手段を制限することにより小さくすることができる。２つの制限されたスキームは、以下のセクションに記載される。
【００５９】
５．監視例
映像概要の関心のある応用例は、記録された監視映像へのアクセスである。映像内の特定のイベントを調査する必要がある場合、調査は、映像概要を用いることにより非常に早く行うことができる。
【００６０】
前述したように、図５は、いずれの活動を失うことなく総ての活動を短い期間に凝縮した映像概要のパワーの例を示している。これは、コーヒーステーションを監視するカメラが収集した映像を用いて行われた。２つの例は、実際の監視カメラから得られたものである。図８ａ，８ｂおよび８ｃは、ストリートの監視の映像概要の詳細を示す図である。図８ａは、オリジナル映像の通常のフレーム（２２秒）を示している。図８ｂは、凝縮された活動を示す映像概要動画（２秒）のフレームを示している。図８ｃは、短い映像概要（０．７秒）のフレームを示しており、さらに凝縮された活動を示している。これらの図に示す画像は、街路を監視するカメラにより取得された映像から生成され、歩行者が時折視界を横切っている。これらの多くは、非常に凝縮された概要に集められる。
【００６１】
図８ａおよび８ｂは、フェンスの監視の映像概要の詳細を示す図である。フェンスの近くでは非常に少ない活動があり、時折、兵士が巡回するのが確認できる。映像概要は、巡回および歩いている兵士の総ての事例を同時に示しており、任意で、ストロボ効果により表示させることにより概要映像を短くすることさえ可能である。
【００６２】
６．映像概要による映像インデックス
映像概要は、映像インデックスとして利用することができ、映像内の行動にアクセスする効率的で直観的なリンクをユーザに提供する。これは、総ての概要ピクセルを、オリジナル映像の対応するオブジェクトの外観へのポインタと関連させることにより行うことができる。映像概要では、映像の情報は、「活動の空間」に投影され、活動は、時間的な内容に拘わらず（我々は空間的な内容を保護できるが）重要である。活動は短い期間内に集中するため、映像内の特定の活動は容易にアクセスできる。
【００６３】
前述した説明から、ビデオカメラが動的なシーンをスキャンニングする場合、領域が入力映像内で確認できるようになる絶対的な「年代順の時間」が、シーンの動的性の一部でないことは理解できるであろう。各領域の可視期間内の「ローカルタイム」は、シーン内の動的性の描写とより関連しており、動的なモザイクを構成する場合に保護されるべきである。前述した実施例は、本発明の第１の態様である。第２の態様では、我々は、継ぎ目のないパノラマのモザイクを生成すり方法を示しており、当該実施例では、シーン内のオブジェクトが移動する場合に、画像間のステッチが、可能な限りシーン内のオブジェクトの部分を省略することを阻止する。
【００６４】
７．３次元の最小カットを用いたパノラマ画像の生成
Ｉｌ，．．．．，ＩＮは、入力シーケンスのフレームである。我々は、シーケンスが、従来の方法のうちの一つを用いて、単一の基準フレームに整列された場合を想定する。説明を簡単にするために、我々は、整列後の総てのフレームが、同じ大きさであると仮定する（カメラの視界の外のピクセルは、無効として記録される）。また、カメラは時計回りにパンすると仮定する（別の動作は、同じような方法で処理できる）。
【００６５】
Ｐ（ｘ，ｙ）は、構成されたパノラマ画像とする。Ｐ内の各ピクセル（ｘ，ｙ）の場合、我々は、このピクセルが取得されるフレームＭ（ｘ，ｙ）を選択する必要がある（すなわち、Ｍ（ｘ，ｙ）＝ｋの場合、Ｐ（ｘ，ｙ）＝Ｉｋ（ｘ，ｙ）である）。カメラが時計回りにパンすると仮定した場合、左側の列は最初のフレームから取得され、一方、右側の列は、最後のフレームから取得されることは明らかである（視野の小さなパノラマ画像を生成するために、他の境界条件を選択できる）。
【００６６】
我々の目的は、継ぎ目のないパノラマ画像を生成することである。このため、我々は、特に、オブジェクトが移動している場合、オブジェクト内のステッチの防止を試みる。我々は、［１］で使用されるスコアと同様の継ぎ目のスコアを利用するが、ＮＰの難しい問題を（近似により）解決する代わりに、より限定された問題の最適な解決方法を発見する。
【００６７】
８．エネルギー最小化問題などの問題の定式化
前述した等式との主な違いは、
2009516257.tif 000014
により求められるステッチ費用である。ここで、
ｍｉｎ＝ｍｉｎ（Ｍ（ｘ，ｙ），Ｍ（ｘ’，ｙ’））、
ｍａｘ＝ｍａｘ（Ｍ（ｘ，ｙ），Ｍ（ｘ’，ｙ’））である。
【００６８】
この費用は、フレームの割り当てが連続的であると仮定すると妥当であり、すなわち、（ｘ，ｙ）および（ｘ’，ｙ’）が隣接するピクセルの場合、これらのソースフレームＭ（ｘ，ｙ）およびＭ（ｘ’，ｙ’）は近い。この費用の主な利点は、この問題を図上の最小カットの問題として解決できることである。
【００６９】
我々が最小化するエネルギー関数は、
2009516257.tif 000015
であり、ここでは、
Ｎ（ｘ，ｙ）は、（ｘ，ｙ）の隣接するピクセルである。
Ｅ（ｘ，ｙ，ｘ’，ｙ’）は、等式１で説明したように、隣接する各ピクセルのステッチ費用である。
Ｖａｌｉｄ（ｘ，ｙ，ｋ）は１であり、Ｉｋ（ｘ，ｙ）は、有効ピクセル（即ち、カメラの視界内）である。
Ｄは、非常に大きな数である（無限大を意味する）。
【００７０】
９．単一のパノラマの生成
次に、我々は、（複雑な指数を有する）２次元の複数のラベルの問題を、（複雑な多項式を有するが実際には即座に解決できる）３次元の２つのラベルの問題に変換する方法を示す。各ピクセルｘ，ｙおよび入力フレームｋの場合、我々は、Ｘ（ｘ，ｙ）＜＝ｋの場合に１に等しい２値変数ｂ（ｘ，ｙ，ｋ）を決定する（Ｍ（ｘ，ｙ）は、ピクセル（ｘ，ｙ）のソースフレームである）。ｂ （ｘ，ｙ，ｋ）＝１であることは明らかである。
【００７１】
各１≦ｋ≦Ｎでｂ（ｘ，ｙ，ｋ）の場合、我々は、ｂ（ｘ，ｙ，ｋ）＝１の最小のｋとしてＭ（ｘ，ｙ）を定める。我々は、最小化が継ぎ目のないパノラマを与えるエネルギー項を記載する。各隣接するピクセル（ｘ，ｙ）および（ｘ’，ｙ’）と、各ｋの場合、我々は、ｂ（ｘ，ｙ，ｋ）≠ｂ（ｘ’，ｙ’，ｋ）の割り当てのために誤差項（error term）を追加する（この誤差項は対称である）。
2009516257.tif 000016
【００７２】
また、我々は、ｂ（ｘ，ｙ，ｋ）＝１であるがｂ（ｘ，ｙ，ｋ＋１）＝０である割り当ての無限のペネルティを追加する（Ｍ（ｘ，ｙ）＜＝ｋであるがＭ（ｘ，ｙ）＞ｋが可能でないため）。
【００７３】
最後に、Ｉｋ（ｘ，ｙ）が無効なピクセルである場合、我々は、無限のペナルティを割り当てに与えることにより、ｋ＞１の場合ｂ（ｘ，ｙ，ｋ）＝１∧ｂ（ｘ，ｙ，ｋ＋１）＝０あるいはｋ＝１の場合ｂ（ｘ，ｙ，ｋ）＝１、このピクセルを選択することを阻止することができる（これらの割り当ては、Ｍ（ｘ，ｙ）＝ｋであることを意味している）。
【００７４】
前述した総ての項は、３次元グリッドの変数の対であり、したがって、我々は、３次元バイナリＭＲＦのエネルギー関数を最小化として説明でき、最小カットを用いて多項式時間内でそれを最小化できる［９］。
【００７５】
１０．４次元最小カットを用いたパノラマ動画の生成
（長さＬの）パノラマ動画を生成すべく、我々は、一連のパノラマ画像を生成すべきである。時間的な整合性が強化されないため、各パノラマ画像を個別に生成することはよくない。別の方法は、連続的なモザイク画像が、先行するモザイクで使用された連続するフレームから各ピクセルを取得する場合、最初のフレームとして最初のモザイク画像で開始する（Ｍｌ（ｘ，ｙ）＝Ｍ（ｘ，ｙ）＋１）。この可能性は、図２ｂを参照して前述したのと同様である。
【００７６】
本発明の第２の態様では、我々は、１のパノラマフレームから別のパノラマフレームに変化する機会をステッチに与える別の式を代わりに使用し、これは、移動するオブジェクトを上手くステッチするのに非常に重要である。
【００７７】
我々は、前述した３次元図の事例Ｌで構成される４次元の図を生成する。
2009516257.tif 000017
【００７８】
時間的な整合性を強化すべく、我々は、無限のペナルティを割り当てに課す、即ちｌ＜Ｌそれぞれの場合はｂ（ｘ，ｙ，Ｎ，ｌ）＝１、ｌ＞１それぞれの場合はｂ（ｘ，ｙ，１，ｌ）＝０。
【００７９】
さらに、各（ｘ，ｙ，ｋ，ｌ）（１≦ｌ≦Ｌ−１，１≦ｋ≦Ｎ−１）の場合、我々は、
割り当てｂ（ｘ，ｙ，ｋ，ｌ）＝１≠ｂ（ｘ，ｙ，ｋ＋１，ｌ＋１）のための費用関数を設定する（ｋ＝Ｎ−１の場合、我々は費用の左項のみを使用する）。
2009516257.tif 000018
この費用は、生成された動画内で（時間的に）連続したピクセルを表示するのを強化する（ただし、例えば、これらのピクセルは背景内である）。
【００８０】
この方法の変更例は、各ピクセル（ｘ，ｙ）を、連続したフレームの同じピクセルに接続するのではなく、ピクセル（ｕ，ｖ）におけるオプティカルフローにより、対応するピクセル（ｘ＋ｕ，ｙ＋ｖ）に接続する。オプティカルフローを算出する好適な方法は、例えば［１９］にある。オプティカルフローを用いることにより、移動するオブジェクトの事例をよりよく処理する。
【００８１】
さらに我々は、４次元図の最小カットを用いてエネルギー関数を最小化することができ、バイナリの解決方法は、ステッチの問題を軽減するパノラマ動画を決定する。
【００８２】
１１．実用的な改良
４次元の図を保存するには、非常に大きなメモリが必要である。したがって、我々は、メモリ要求とアルゴリズムの動作時間の双方を低減するいくつかの改良点を利用する。
・前述したように、エネルギーは、無効なピクセルのための頂点（vertices）を明確に保存することなく最小化できる。したがって、頂点の数は、入力映像内のピクセルの数に減少し、出力映像内のフレームの数により増加する。
・出力映像内の各フレームを解決する代わりに、我々は、出力フレームの標本化されたセットのみを解決し、これらの間にステッチ関数を挿入する。この改良点は、シーン内の動作があまり大きくないことを想定している。
・我々は、入力フレームの部分的なセットからのみ各ピクセルを生成することができる。これは、特に映像から取得される一連のフレームに有用であり、連続したフレームの各対の間の動作は非常に小さい。この場合、我々は、各ピクセルのために一組のソースフレームを標本化することにより、多くを失うことがない。しかし、一貫性のある方法によりソースフレームを標本化することが好適である。例えば、フレームｋが、ｌ−ｔｈ出力フレーム内のピクセル（ｘ，ｙ）のために可能なソースである場合、ｋ＋１フレームは、ｌ＋１−ｔｈ出力フレーム内のピクセル（ｘ，ｙ）のために可能なソースフレームであるべきである。
・我々は、複数の解像度のフレームワーク（multi-resolution framework）を利用し（例えば、［２］で利用されたような）、粗い解決（solution）が低解像度の画像のために発見され（バッファリングおよび標本化の後に）、解決は境界においてのみ洗練される。
【００８３】
ここで、我々は、関心のあるスコアにより動画を結合する方法を説明する。密度の高い（denser）あるいは薄い（sparser）活動を含む動画を生成し、あるいはユーザが特定する方法でシーンを制御するといったいくつかの応用例が存在する。
【００８４】
［１４］に記載された動的なパノラマは、特別な事例として考えることができ、同じ動画の異なる部分が結合されて、より大きな視界の動画が取得され、この場合、我々は、各時間の各ピクセルの「視認性」により、関心のあるスコアを決定する。さらに一般的には、同じ動画の異なる部分（時間あるいは空間的にシフトする）を結合することは、他の事例でも利用できる。例えば、動画内の活動の密度を高めるために、我々は、アクションが生じる動画の異なる部分を、多くのアクションを有する新しい動画に結合する。図１から８を参照して前述した実施例は、活動の特別な事例を説明しており、異なる方法を利用している。
【００８５】
取り組むべき２つの問題は、
１．動画を「見た目のよい」動画に結合する方法。例えば、我々はステッチの問題を避けたい。
２．関心のあるスコアを最大化する。
【００８６】
我々は、使用可能な異なるスコアを説明することから開始し、動画を結合するのに用いられるスキームを説明する。
【００８７】
関心のある特徴（interest function）として使用可能な主要な特徴の一つは、ピクセルの「重要度」のレベルである。我々の実験では、我々は、ピクセル内の「活動」をその重要度を示すために考慮しているが、重要度の他の測定も同様に好適である。活動レベルの評価は、本発明の特徴自体ではないが、前述したセクション１で参照された様々な方法のうちの一つ（活動検出）を利用して行うことができる。
【００８８】
１３．他のスコア
動画を結合するのに利用可能な他のスコア：
・視認性スコア：カメラが移動する場合、あるいは映像内の穴を埋めようとする場合、見ることができないピクセルが存在する。我々は、（必ずしも無限のスコアによってではなく）無効なピクセルにペナルティを課することができる。この方法では、我々は、穴を埋めることを促進できるが（あるいは視野を広げることができるが）、悪いステッチが生じた場合には、穴を埋めることを望まなくてもよく、あるいは小さな視野を利用してもよい。
・方向：活動の測定は、方向の測定と置き換えることができる。例えば、我々は、垂直に移動する領域よりも水平に移動する領域を好むだろう。
・ユーザ仕様：ユーザは、色、テクスチャ等の好適な関心のある特徴を指定する。さらに、ユーザは、異なるスコアにより手動で領域（およびタイムスロット）を指定する。例えば、１が、最大の活動が所望されることを意味し、０が、活動がないことが所望されることを意味するマスクを描くことにより、ユーザは、シーン内の動的性を制御でき、すなわち、特定の位置で発生させることができる。
【００８９】
１４．アルゴリズム
我々は、以下の変更を有する［２０］により使用される方法と同様の方法を利用する。
・我々は、１の動画あるいは別の動画から選択される各ピクセルのための関心のある領域を追加する。このスコアは、各動画の各ピクセルのエッジを利用して端末の頂点（ソースおよびシンク）に追加され、これらのエッジの重みは、関心のあるスコアである。
・我々は、（任意で）フレームの連続した各対の間のオプティカルフローを算出する。次に、一貫性を強化すべく、我々は、時間的に隣接する部分のエッジ（（ｘ，ｙ，ｔ）から（ｘ，ｙ，ｔ＋１））を、オプティカルフローによる隣接部分のエッジ（（ｘ，ｙ，ｔ）から（ｘ＋ｕ（ｘ，ｙ），ｙ＋ｖ（ｘ，ｙ），ｔ＋１））と交換できる。これは、ステッチが顕著でないフローに従うように奨励するように、ステッチ動画間の遷移を強化する。
・動画のいずれの部分（あるいは移動する部分）が結合されるかを決定する場合、ステッチ費用だけでなく、関心のあるスコアを考慮すべきである。例えば、密度の高い活動レベルを有する動画を生成する場合、我々は、スコアを最大化する動画のセットＳを選択する。
2009516257.tif 000019
【００９０】
図９ｂは、動画の増加した活動密度のような効果を示した図であり、オリジナルのフレームは図９ａに示されている。２つ以上の動画が結合された場合、我々は反復手段を利用し、この反復により、新しい動画が、生成された動画に結合される。正確に行うために、以前の反復により生成された古い継ぎ目およびスコアを考慮すべきである。関心のあるスコアが無いにも拘わらず、このスキームは［２０］に記載されている。生成された映像のサンプルフレームが、図９ｂに示されている。
【００９１】
図１０は、処理の概略図である。この例では、映像は、時間的にシフトした映像と結合される。結合は、前述した基準、すなわちステッチ費用を最小限にしつつ関心のあるスコアを最大化することに基づいて、最小カットを用いて行われる。
【００９２】
ここで図１１を参照すると、カメラ１１により取得された第１の動的シーンの映像フレームの第１のシーケンスを、第２の動的シーンを示す少なくとも２つの映像フレームの第２のシーケンスに変換する本発明に係るシステム１０のブロック図が示されている。このシステムは、各ｘ，ｙ座標に配置された複数のピクセルを備える少なくとも一つのオブジェクトの動作を示す第１のシーケンス無いの映像フレームのサブセットを記憶する第１のメモリ１２を備えている。第１の動的なシーン内の少なくとも一つのオブジェクトの空間的に重ならない外観を示すサブセット部分から選択する選択ユニット１３が、第１のメモリ１２に連結される。フレーム生成部１４は、オブジェクト内のピクセルの各ｘ，ｙ座標を変更することなく、少なくとも３つの異なる入力フレームの部分を、第２のシーケンスの少なくとも２つの連続したフレームにコピーし、第２のシーケンスの少なくとも一つのフレームが、第１のシーケンス内の異なるフレームに現れる少なくとも２つの部分を含む。第２のシーケンスのフレームは、ディスプレイユニット１６による後の処理あるいは表示のために、第２のメモリ１５に格納される。フレーム生成部１４は、第２のシーケンスをコピーする前に少なくとも２つの部分を空間的に移動させる移動ユニット（warping unit）１７を備えてもよい。
【００９３】
実際には、システム１０は、本分野で周知のように、グラフィックカードあるいはワークステーションおよび好適な周辺機器を有する最適にプログラムされたコンピュータにより実現される。
【００９４】
システム１０では、少なくとも３つの異なる入力フレームは時間的に近い。システム１０はさらに、映像フレームの第１のシーケンスを予め整列させるために、第１のメモリに結合された任意の整列ユニット１８を備えてもよい。この場合、カメラ１１は、第１のメモリ１２内の予め整列された映像フレームを格納するために整列ユニット１８に連結される。整列ユニット１８は、
第１のシーケンス内のフレーム間の画像動作パラメータを算出し、
第１の動的シーン内の静止したオブジェクトが映像内で静止するように、第１のシーケンス内の映像フレームを移動させることにより動作する。
【００９５】
同様に、システム１０は、整列された空間および時間量を「タイムフロント」表面により一掃し、一連のタイムスライスを生成するために、選択ユニット１３に連結された任意のタイムスライス生成部１９を備えてもよい。
【００９６】
これらの任意の特徴は、「タイムフロント」および「タイムスライス」の語は、参照されている前述したＷＯ２００６／０４８８７５に完全に記載されているのと同様であるため、詳細には説明されていない。
【００９７】
完全にするために、図１２は、本発明に係るシステム１０により実行される主要な処理を示すフロー図である。
【００９８】
１５．考察
映像概要は、映像内の活動を非常に短い期間に凝縮する手段として提案されている。この凝縮された表示は、映像シーケンス内の活動への効率的なアクセスを可能にする。２つの手段が提案されており、１つの手段は、低いレベルのグラフの最適化を用い、概要映像内の各ピクセルは、このグラフ内のノードである。この手段は、入力映像から直接的に概要映像を取得する利点を有しているが、解決（solution）の複雑度が非常に高い。代替的な手段は、最初に移動するオブジェクトを検出し、検出されたオブジェクトを最適化することである。第２の手段では動作のセグメンテーションの予備段階が必要とされるが、これは非常に高速であり、オブジェクトに基づく制約が可能である。生成される映像概要の活動は、オリジナルの映像よりも非常に凝縮されており、このような概要は、これを利用したことのない者にとっては扱い難いかもしれない。しかし、多くの情報を短い時間内で観察することを目的とする場合、映像概要はこの目的を達成する。特別な注意が、動的なストロボスコープを取得する可能性に払われるべきである。映像概要の長さをさらに減少させるとともに、動的なストロボスコープはユーザからの調整を必要としてもよい。単一のオブジェクトの複数の空間的な出現は、長い活動時間を示すことが分かることにはいくらかの訓練を必要とする。我々は、動的な映像概要の特定の実施例を説明しているが、多くの拡張も可能である。例えば、バイナリの「活動」インジケータを有するのではなく、活動インジケータが連続していてもよい。連続的な活動は、例えば、活動レベルに基づいて、表示されたオブジェクトの速度を制御することにより、概要映像を生成可能な選択肢を広げることができる。また、映像概要は、多くのショットから成る長い動画のために用いてもよい。理論的に、我々のアルゴリズムは、重なり（あるいは不連続性）による不利益のために、異なるシーンの部分を結合させない。この場合、単一のショットに利用される単一の背景モデルは、調整可能な背景推定器と交換される。長い動画に利用される別の手段は、ショットのバイナリ検出の従来の方法を利用し、ショット毎に個別に映像概要を生成することである。
【００９９】
本発明に係るシステムは、プログラムされたコンピュータに最適であることは理解できるであろう。同様に本発明は、本発明の方法を実行すべく、コンピュータにより読み取り可能なコンピュータプログラムを意図する。さらに本発明は、本発明の方法を実施する機械により実行可能なプログラム命令を明確に実行する機械読み取り可能なメモリを意図する。
【図面の簡単な説明】
【０１００】
【図１】図１は、時間的に配置された特徴を同時に表示することによりコンパクトな映像概要を生成する本発明のアプローチを示す図である。
【図２ａ】図２ａは、本発明により生成される映像概要を表わす概略図である。
【図２ｂ】図２ｂは、本発明により生成される映像概要を表わす概略図である。
【図３ａ】図３ａは、本発明による一時的な再配置の例を示す図である。
【図３ｂ】図３ｂは、本発明による一時的な再配置の例を示す図である。
【図３ｃ】図３ｃは、本発明による一時的な再配置の例を示す図である。
【図４】図４は、図３ｂに示す動的なストロボ効果を利用した映像概要の単一のフレームを示す図である。
【図５ａ】図５ａは、短い概要が、活動を損なうことなく且つストロボ効果なしで、長いシーケンスを表示できる場合の例を示す図である。
【図５ｂ】図５ｂは、短い概要が、活動を損なうことなく且つストロボ効果なしで、長いシーケンスを表示できる場合の例を示す図である。
【図５ｃ】図５ｃは、短い概要が、活動を損なうことなく且つストロボ効果なしで、長いシーケンスを表示できる場合の例を示す図である。
【図６】図６は、本発明によるパノラマの映像概要の更なる例を示す図である。
【図７ａ】図７ａは、ストリートの監視の映像概要の詳細を示す図である。
【図７ｂ】図７ｂは、ストリートの監視の映像概要の詳細を示す図である。
【図７ｃ】図７ｃは、ストリートの監視の映像概要の詳細を示す図である。
【図８ａ】図８ａは、フェンスの監視の映像概要の詳細を示す図である。
【図８ｂ】図８ｂは、フェンスの監視の映像概要の詳細を示す図である。
【図９ａ】図９ａは、本発明の更なる実施例による動画の増加する活動密度を示す図である。
【図９ｂ】図９ｂは、本発明の更なる実施例による動画の増加する活動密度を示す図である。
【図１０】図１０は、図１０に示す動画を生成するのに利用される処理の概略図である。
【図１１】図１１は、本発明によるシステムの主要な機能を示すブロック図である。
【図１２】図１２は、本発明により実行される主要な動作を示すフロー図である。
【図１】
2009516257.tif 000020
【図２ａ】
2009516257.tif 000021
【図２ｂ】
2009516257.tif 000022
【図３ａ】
2009516257.tif 000023
【図３ｂ】
2009516257.tif 000024
【図３ｃ】
2009516257.tif 000025
【図４】
2009516257.tif 000026
【図５ａ】
2009516257.tif 000027
【図５ｂ】
2009516257.tif 000028
【図５ｃ】
2009516257.tif 000029
【図６】
2009516257.tif 000030
【図７ａ】
2009516257.tif 000031
【図７ｂ】
2009516257.tif 000032
【図７ｃ】
2009516257.tif 000033
【図８ａ】
2009516257.tif 000034
【図８ｂ】
2009516257.tif 000035
【図９ａ】
2009516257.tif 000036
【図９ｂ】
2009516257.tif 000037
【図１０】
2009516257.tif 000038
【図１１】
2009516257.tif 000039
【図１２】
2009516257.tif 000040
【国際調査報告】
2009516257.tif 000041
2009516257.tif 000042
2009516257.tif 000043