JP4972095B2

JP4972095B2 - 映像概要を生成する方法およびシステム

Info

Publication number: JP4972095B2
Application number: JP2008539616A
Authority: JP
Inventors: ペレグ，シュムエル; ラヴ−アチャ，アレクサンダー
Original assignee: イッサムリサーチディベロップメントカンパニーオブザヘブライユニバーシティーオブエルサレム
Priority date: 2005-11-15
Filing date: 2006-11-15
Publication date: 2012-07-11
Anticipated expiration: 2026-11-15
Also published as: US8514248B2; CN101366027B; CA2640834C; CA2640834A1; WO2007057893A3; BRPI0620497B1; WO2007057893A2; US20090219300A1; BRPI0620497A2; KR101420885B1; US20120092446A1; JP2009516257A; DK1955205T3; KR20080082963A; EP1955205B1; EP1955205A2; AU2006314066A1; AU2006314066B2; CN101366027A; US8102406B2

Description

関連出願
本出願は、２００６年１１月２日に出願された米国第１０／５５６，６０１（Ｐｅｌｅｇ等）「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）」と同義であり、これは、ポスト処理に従うコンピュータ画像ファイルとしてアクセス可能であり、任意の種類の動画ファイル、例えばデジタル、アナログを含む。カメラは、回転およびズームが可能な所定の位置にあることが好適であるが、これまで提案された技術で行われるような影響を受けやすい並進運動ではない。本発明に関連するシーンは、例えば、米国特許６，６６５，００３［２２］および動的なシーンを表示しない立体的な画像の表示を目的とする他の引例で処理される静的なシーンと反対に動的であり、連続したフレームが空間的および時間的な連続性を有する。本発明の一の多様によるうと、我々はこの問題を、グラフ上の最大の流れを見つけることにより多項式時間で説くことができる単一の最小のカットの問題として定式化する［５］。

本発明を説明するために、「空間時間量」と称する構成が利用され、動的なパノラマ映像を生成する。空間時間量は、総てのフレームを時間軸に沿って順次スタックすることにより画像の入力シーケンスから構成される。しかしながら、実際の実施に関する限り、例えば、動的なソースシーンの２Ｄフレームを時間内にスタックすることにより空間時間量を実際に構成する必要はないことを理解すべきである。さらに通常は、ソースフレームは、ターゲットフレームを構成するために個々に処理されるが、空間時間量を概念的な構成でなく物理的な構成であるかのように参照することは理解を助けるであろう。

本発明を理解し、本発明が実際にどのように実行されるか理解するために、好適な実施例は、限定ではなく添付図面を参照することにより説明される。

１．活動検出
本発明は、総ての入力ピクセルが「重要度」のレベルが付されていると仮定する。これ以降、活動レベルを「重要度」のレベルとして使用するが、所望の応用例に基づいて他の測定値を「重要度」として使用できることは明らかであろう。重要度（あるいは活動）レベルの評価が想定され、それ自体は本発明の特徴ではない。これは、不規則性を検出し［４，１７］、オブジェクト検出を移動させ、オブジェクトトラッキングを行う様々な手段のうちの一つを利用して行うことができる。代替的に、これは、顔認識などの認識アルゴリズムに基づいて行うことができる。

例えば、単一且つ共通で使用される活動インジケータが選択され、入力ピクセルＩ（ｘ，ｙ，ｔ）は、位置（ｘ，ｙ）における時間的なメジアンからの色差が所定の閾値よりも大きい場合、「アクティブ」とされる。アクティブピクセルは、特有の関数により既定される。

活動インジケータからノイズを除去すべく、メジアンフィルタが、概要（synopsis）処理を継続する前にχに適用される。

連続的な活動測定を利用できるが、本発明は２元の事例に焦点を合わせる。連続的な活動の測定は、以下の詳細な説明のほぼ総ての等式を僅かに変更するだけで行うことができる［４，１７，１］。

我々は、映像概要の算出のための２つの異なる実施例を記載する。１つのアプローチ（セクション２）は、グラフカットを用いたグラフ表現および費用関数の最適化を利用する。別のアプローチ（セクション３）は、オブジェクトセグメンテーションおよびトラッキングを利用する。

２．エネルギーの最小化による映像概要
入力映像シーケンスのＮ個のフレームを３Ｄの空間時間量Ｉ（ｘ，ｙ，ｚ）で表示させ、この場合、（ｘ，ｙ）はこのピクセルの空間的な座標であり、１≦ｔ≦Ｎがフレームの数である。

我々は、以下の特性を有する映像概要Ｓ（ｘ，ｙ，ｚ）を生成する。
・映像概要Ｓは、オリジナル映像Ｉよりも実質的に短くあるべきである。
・オリジナル映像の最大の「活動」は、要約映像内で現れるべきである。
・映像概要内のオブジェクトの動作は、オリジナル映像内の動作と同様であるべきである。
・映像概要は、見栄えがよく、目に見える継ぎ目（シーム）あるいは断片化したオブジェクトは阻止されるべきである。

前述した特性を有する映像概要Ｓは、マッピングＭを利用して生成され、概要Ｓ内の総ての座標（ｘ，ｙ，ｚ）に、Ｉからのソースピクセルの座標を割り当てる。我々は、空間的な位置を固定しつつ、ピクセルのタイムシフトに焦点を合わせる。したがって、概要ピクセルＳ（ｘ，ｙ，ｚ）は、入力ピクセルＩ（ｘ，ｙ，Ｍ（ｘ，ｙ，ｔ））から生じる。タイムシフトＭは、エネルギーの最小化の問題を解決することにより得られ、費用関数は、以下の等式により得られる。

ここで、Ｅ_ａ（Ｍ）は活動の損失を示し、Ｅ_ｄ（Ｍ）は継ぎ目における不連続性を示す。活動の損失は、映像概要Ｓ内で現れない入力映像Ｉのアクティブピクセルの数であろう。

不連続性費用（discontinuity cost）Ｅ_ｄは、映像概要内の空間および時間的な隣接部分と、入力映像内の対応する隣接部分との間の継ぎ目における色差の合計として既定される（同様の等式が[１]に存在する）。

ここで、ｅ_ｉは、６つの空間および時間的な隣接部分を表わす６つのユニットである。

図２ａおよび２ｂは、費用関数を最小化することにより短い映像概要を生成する空間および時間的な処理を表わす概略図であり、移動するオブジェクトの動作は、図中の「活動ストリップ」により表わされる。上図はオリジナルの映像を示しており、下図は映像概要を示している。特に図２ａでは、短い映像概要Ｓは、多くのアクティブピクセルを含むことにより入力映像ｌから生成される。円滑にすべく、Ｓ内のピクセルＡがｌ内のピクセルＢに対応する場合、「境界を越えた」隣接部分は同様であるべきである。最適なＭ最小化（３）を発見することは、非常に大きな最適化の問題である。近似解が図２ｂに示されており、映像概要内の連続したピクセルは、連続した入力ピクセルから生成されるように限定されている。

費用関数Ｅ（Ｍ）（等式１）は３次元のマルコフ確率場に対応し、各ノードは、出力映像の３次元体積内のピクセルに対応し、入力フレームに対応する時間的価値が割り当てることができることに留意する。ノードの重みは、活動費用により決定され、ノード間のエッジは、不連続性費用に応じて決定される。したがって、費用関数は、反復するグラフカット（iterative graph-cuts）などのアルゴリズムにより最小化することができる［９］。

２．１．２Ｄグラフを利用した限定的な解決方法
映像概要内の各ピクセルが任意の時間に生じることを可能にする等式（１）の最適化は、大きな問題である。例えば、５秒の映像概要に要約される３分の入力映像は、それぞれが５４００ラベルを有する約２^２５ノードを有するグラフを生じる。

水平な経路を移動する動的なテクスチャあるいはオブジェクトの場合、３次元のＭＲＦは、この問題を１次元の問題に低減させることにより効果的に解決できることが［２］に記載されていた。この研究において、我々は、より一般的な方法で移動するオブジェクトに取り組み、したがって、我々は異なる制約を用いる。映像概要Ｓ内の連続したピクセルは、入力映像Ｉ内の連続したピクセルから生じるように制限されている。この制限の下では、３次元のグラフは、２次元のグラフに減らされ、各ノードは、概要動画内の空間的な位置に対応する。各ノードＭ（ｘ，ｙ）のラベルは、図２ｂに示すように、Ｓの第１のフレームに示すＩ内のフレーム数ｔを決定する。Ｍ（ｘ_１，ｙ_１）≠Ｍ（ｘ_２，ｙ_２）の場合、継ぎ目は、２つの隣接する位置（ｘ_１，ｙ_１）と（ｘ_２，ｙ_２）との間に存在し、継ぎ目に沿った不連続性費用Ｅ_ｄ（Ｍ）は、Ｓ内の総てのフレームに跨るこの空間的な位置における色差の合計である。

ここで、ｅ_ｉは、４つの空間的な隣接部分を示す４つの単位ベクトルである。

各ノードのラベルの数はＮ−Ｋであり、ＮおよびＫは、入力および出力映像それぞれのフレームの数である。各ピクセルの活動の損失は、

である。

３．オブジェクトに基づく概要
前述した動的な映像概要の低いレベルのアプローチは、目に見える継ぎ目を防止するといった局所的な特性に限定されている。高いレベルのオブジェクトに基づく特性は、オブジェクトが検出できる場合に取り入れることができる。例えば、ストロボ効果を避けることは、体積内の各オブジェクトの検出およびトラッキングを必要とする。このセクションでは、動的な映像概要のためのオブジェクトに基づくアプローチの実施について説明する。いくつかのオブジェクトに基づく映像の要約方法は、文献（例えば、［７，５，１６］）に存在し、これらは総て、重要なフレームの選択するために、検出されたオブジェクトを利用する。これらの方法とは違い、本発明は、時間内にオブジェクトを移動させ、入力シーケンス内に現れない新しい概要フレームを生成し、空間および時間を有効に利用する。

一実施例では、移動するオブジェクトは、前述したように、各ピクセルを時間的なメジアンと比較し、この違いを閾値化することにより検出される。この後、空間的なメジアンフィルタを利用したノイズクリーニングが行われ、空間および時間的に関連する構成要素が組み合わされる。文献内には、このタスクのために利用されるオブジェクト検出およびトラッキングのための多くの他の方法が存在することは理解できるであろう（例えば、［７，１７，２１］）。オブジェクト検出およびトラッキングの各処理は、一組のオブジェクトを生成し、各オブジェクトｂは、特有の関数により表わされる。

図３ａ，３ｂ，３ｃは、本発明による時間的な再配置の例を示した図である。各図の上図は、オリジナルの映像を表わしており、下図は、映像概要を表わしており、移動するオブジェクトの動作は、図中の「活動ストリップ」により表わされる。図３ａは、異なる時間に記録され、映像概要の同じ時間間隔で移動する２つのオブジェクトを示している。図３ｂは、長い期間移動し、短い時間間隔を有するセグメントに分割される単一のオブジェクトを示しており、これは、同時に表示され、動的なストロボ効果を生成する。図３ｃは、オブジェクトの体積がセグメントに分割される場合に、オブジェクトの交差が概要を妨げないことを示している。

各オブジェクトから、セグメントは、オブジェクトが現れるフレームのサブセットを選択することにより生成される。このようなセグメントは、異なる時間間隔を表わすことができ、任意で異なる標本化レートで取得される。

映像概要Ｓは、以下の処理を用いて、入力映像Ｉから構成される。
（１）オブジェクトｂ_１．．．ｂ_ｒは、入力映像Ｉから抽出される。
（２）一組の重ならないセグメントＢは、オリジナルのオブジェクトから選択される。
（３）時間的なシフトＭは、選択された各セグメントに適用され、短い映像概要を生成するとともに、オブジェクト間の重なりを阻止し、継ぎ目のないステッチ（stitching）を可能にする。これは、図１および図３ａ乃至３ｃに説明されている。図４は、映像概要の単一のフレームが図３ｂに示す動的なストロボ効果を利用する例を示した図である。

我々が処理（２）および（３）を時間内に選択およびシフトさせ、短くて継ぎ目の無い映像概要を取得するため、処理（２）および（３）は関連している。前述した処理（２）および（３）は、完全である必要はないことは理解できるであろう。「空間的に重複しないセグメント（non-spatially overlapping segment)」という場合には、小さな重複部分が許容され、「重なりを阻止する」という場合には、時間内に移動するオブジェクト間の小さな重なりは許容されるが、これは、視覚的に魅力的な映像を得るために最小限にすべきである。

オブジェクトに基づく表示では、生成された概要内のピクセルは、複数のソース（異なるオブジェクトから生成され）を有し、したがって、我々は、総てのオブジェクトが統合される後の処理ステップを付加する。背景画像は、シーケンスの総てのフレームにおけるピクセルのメジアン値を取得することにより生成される。次に、選択されたオブジェクト」は、各フレーム内のピクセルとメジアン画像との間の距離（ＲＧＢ空間内）に比例した重み付けを利用して融合可能である。このステッチ機構は、［６］で使用されるものと同様である。

我々は、単一の概要ピクセルにマップされる一組の総てのピクセル（ｘ，ｙ，ｔ）∈Ｓを、ｓｒｃ（ｘ，ｙ，ｔ）として規定し、我々は、オブジェクト（あるいはセグメント）ｂ内の（アクティブ）ピクセルの数を＃ｂ＝Σ_{ｘ，ｙ，ｔ∈Ｉ}χ_ｂ（ｘ，ｙ，ｔ）とする。

我々は、セグメントＢのサブセット選択および時間的なシフトＭの費用を測定するエネルギー関数を定める。費用は、活動の損失Ｅ_α、オブジェクトＥ_Ｏ間の重なりのペナルティ、および長い映像概要にペナルティを課す項Ｅ_ｌを含む。

ここで、

である。

３．１．所定の長さを有する映像−概要
ここで、所定の長さＫの短い映像概要が、長い映像で構成される事例を説明する。このスキームの場合、各オブジェクトは、長さＫを有する重複し連続するセグメントに分割される。総てのセグメントは、時間的に推移してタイムｔ＝１で開始し、いずれのセグメントが映像概要内に含まれるか決定する必要がある。明らかに、このスキームでは、いくつかのオブジェクトが概要データ内に現れない。

初めに、我々はセグメントの総ての対の重なりの費用を決定する。ｂ_ｉおよびｂ_ｊ
を出現時間ｔ_ｉおよびｔ_ｊを有する２つのセグメントとし、各セグメントのサポートを（等式５のような）特有の関数χにより表わす。

これらの２つのセグメントの費用は、時間ｔ＝１になった後の２つのセグメントの色差の合計として決定される。

映像概要の場合、我々は、等式６の費用を最小化するセグメントＢの部分的なセットを選択し、ここでは、Ｅ_ｌは、定数Ｋであり、重なり費用は、

により求められる。

同じ空間および時間ピクセルが２回表示される（これは、許容可能であるが無駄である）のを阻止すべく、我々は、オリジナルの動画を横切るセグメントｂ_ｉおよびｂ_ｊのために、ｖ（ｂ_ｉ，ｂ_ｊ）＝∞と設定する。さらに、ストロボ効果が必要ない場合、ストロボ効果は、同じオブジェクトから標本化された総てのｂ_ｉおよびｂ_ｊのために、ｖ（ｂ_ｉ，ｂ_ｊ）＝∞と設定することにより避けられる。

擬似的なアニーリング（simulated annealing）［８］は、エネルギー関数を最小化するために利用される。各状態は、概要内に含まれるセグメントのサブセットを示しており、隣接する状態が、設定するために取得され、セグメントが取り除かれ、追加され、あるいは別のセグメントと交換される。

セグメントの選択の後、長さＫの概要動画は、総ての変化したセグメントを結合することにより構成される。この手段を利用した映像概要の一つのフレームの例が。図４に示されている。

３．２．無損失映像概要
映像監視などのいくつかの応用例の場合、我々は、長い映像概要を好むが、総ての活動が現れるのが保証される。この場合、オブジェクトは、先行するセクションで行われた一組のオブジェクトのセグメントを選択するためのものでないが、オブジェクトのセグメントのコンパクトな時間的な再配置を発見するためのものである。

さらに、我々は、擬似アニーリングを用いてエネルギーを最小化する。この場合、状態は、総てのセグメントの一組のタイムシフトに対応し、２つの状態は、タイムシフトが単一のセグメントのためにのみ変化する場合、隣接部分として定義される。この場合、注意すべき２つの問題がある。
・最初あるいは最後のフレーム内で現れるオブジェクトのセグメントは、映像概要内に残るべきである（さもなければ、これらは突然現れるか消える）。我々は、各状態が、これら総てのオブジェクトの時間的なシフトを結果的に固定することにより、この制約を満足させることに留意する。
・入力映像の時間的な配置は、共通するエネルギー関数の局所的な最小化であり、したがって、アニーリング処理を初期化する好適な選択肢ではない。我々は、短い映像を有する擬似アニーリングを初期化し、総てのオブジェクトが重なる。

図５ａ，５ｂおよび５ｃは、短い概要が、ストロボ効果がなく活動の損失がない長いシーケンスを表示可能である場合に、この手段を示す図である。３つのオブジェクトは、同時に表示されるようにタイムシフトできる。特に、図５ａは、オリジナルの映像（上図）および映像概要（下図）の空間および時間的な概略図である。図５ｂは、オリジナルの映像の３つのフレームを示しており、図５ａに示すように、オリジナルの映像では、各人物が個別に現れているが、映像概要では、３つの総てのオブジェクトが一緒に現れる。図５ｃは、３人を同時に示す映像概要の１つのフレームを示している。

４．パノラマの映像概要
ビデオカメラがシーンをスキャンする場合、パノラマのモザイクを用いて多くの冗長な部分が取り除かれる。しかし、従来の方法は、シーンの動的性が損なわれる単一のパノラマ画像を構成する。制限された動的性は、ストロボ画像により表わすことができ［６，１，３］、移動するオブジェクトは、これらの経路に沿っていくつかの位置で表示される。

パノラマの映像概要は、異なる時間にシーンの異なる位置で行われる活動を同時に表示させることにより生成できる。実質的な圧縮が得られ、各オブジェクトの活動の期間が時間に制限されるため、カメラにより表示される。特別な事例は、カメラが、図６に示す走っているライオンなどのオブジェクトをトラックする場合である。カメラが、走っているライオンをトラックする場合、映像概要は、背景のパノラマのモザイクであり、前景は、走っているライオンのいくつかの動的なコピーを含む。この場合、短い映像概要は、ストロボ効果を許可するだけで取得できる。

パノラマの映像概要を構成することは、総てのフレームをいくつかの基準フレームに整列させる予備の段階で、通常の映像概要と同様の方法により行われる。整列の後、オブジェクトの画像の座標が、入力画像のうちの一つの座標系であるグローバル座標から取得される。

映像を処理を可能にすべく、移動するオブジェクトのセグメンテーションが完全でない場合でさえ、我々は、重なった部分を完全に阻止する代わりに当該部分にペネルティを課す。この重なった部分のペナルティにより、オブジェクトの時間的な配置の順応性を可能にし、セグメンテーションが完全でない場合でさえ、オブジェクトのピクセルは、いくつかの背景を含む。

付加的な期間が追加され、映像概要の時間的な順序を入力映像の順序に偏向させる。

総ての可能なセグメントセクションＢおよび時間的なシフトＭの前述したエネルギーを最小化することは、可能性が非常に多いため、非常に消耗的である。しかしながら、問題は、解決手段を制限することにより小さくすることができる。２つの制限されたスキームは、以下のセクションに記載される。

５．監視例
映像概要の関心のある応用例は、記録された監視映像へのアクセスである。映像内の特定のイベントを調査する必要がある場合、調査は、映像概要を用いることにより非常に早く行うことができる。

前述したように、図５は、いずれの活動を失うことなく総ての活動を短い期間に凝縮した映像概要のパワーの例を示している。これは、コーヒーステーションを監視するカメラが収集した映像を用いて行われた。２つの例は、実際の監視カメラから得られたものである。図８ａ，８ｂおよび８ｃは、ストリートの監視の映像概要の詳細を示す図である。図８ａは、オリジナル映像の通常のフレーム（２２秒）を示している。図８ｂは、凝縮された活動を示す映像概要動画（２秒）のフレームを示している。図８ｃは、短い映像概要（０．７秒）のフレームを示しており、さらに凝縮された活動を示している。これらの図に示す画像は、街路を監視するカメラにより取得された映像から生成され、歩行者が時折視界を横切っている。これらの多くは、非常に凝縮された概要に集められる。

図８ａおよび８ｂは、フェンスの監視の映像概要の詳細を示す図である。フェンスの近くでは非常に少ない活動があり、時折、兵士が巡回するのが確認できる。映像概要は、巡回および歩いている兵士の総ての事例を同時に示しており、任意で、ストロボ効果により表示させることにより映像概要を短くすることさえ可能である。

６．映像概要による映像インデックス
映像概要は、映像インデックスとして利用することができ、映像内の行動にアクセスする効率的で直観的なリンクをユーザに提供する。これは、総ての概要ピクセルを、オリジナル映像の対応するオブジェクトの外観へのポインタと関連させることにより行うことができる。映像概要では、映像の情報は、「活動の空間」に投影され、活動は、時間的な内容に拘わらず（我々は空間的な内容を保護できるが）重要である。活動は短い期間内に集中するため、映像内の特定の活動は容易にアクセスできる。

前述した説明から、ビデオカメラが動的なシーンをスキャンニングする場合、領域が入力映像内で確認できるようになる絶対的な「年代順の時間」が、シーンの動的性の一部でないことは理解できるであろう。各領域の可視期間内の「ローカルタイム」は、シーン内の動的性の描写とより関連しており、動的なモザイクを構成する場合に保護されるべきである。前述した実施例は、本発明の第１の態様である。第２の態様では、我々は、継ぎ目のないパノラマのモザイクを生成すり方法を示しており、当該実施例では、シーン内のオブジェクトが移動する場合に、画像間のステッチが、可能な限りシーン内のオブジェクトの部分を省略することを阻止する。

７．３次元の最小カットを用いたパノラマ画像の生成
Ｉ_ｌ，．．．．，Ｉ_Ｎは、入力シーケンスのフレームである。我々は、シーケンスが、従来の方法のうちの一つを用いて、単一の基準フレームに整列された場合を想定する。説明を簡単にするために、我々は、整列後の総てのフレームが、同じ大きさであると仮定する（カメラの視界の外のピクセルは、無効として記録される）。また、カメラは時計回りにパンすると仮定する（別の動作は、同じような方法で処理できる）。

Ｐ（ｘ，ｙ）は、構成されたパノラマ画像とする。Ｐ内の各ピクセル（ｘ，ｙ）の場合、我々は、このピクセルが取得されるフレームＭ（ｘ，ｙ）を選択する必要がある（すなわち、Ｍ（ｘ，ｙ）＝ｋの場合、Ｐ（ｘ，ｙ）＝Ｉ_ｋ（ｘ，ｙ）である）。カメラが時計回りにパンすると仮定した場合、左側の列は最初のフレームから取得され、一方、右側の列は、最後のフレームから取得されることは明らかである（視野の小さなパノラマ画像を生成するために、他の境界条件を選択できる）。

我々の目的は、継ぎ目のないパノラマ画像を生成することである。このため、我々は、特に、オブジェクトが移動している場合、オブジェクト内のステッチの防止を試みる。我々は、［１］で使用されるスコアと同様の継ぎ目のスコアを利用するが、ＮＰの難しい問題を（近似により）解決する代わりに、より限定された問題の最適な解決方法を発見する。

８．エネルギー最小化問題などの問題の定式化
前述した等式との主な違いは、

により求められるステッチ費用である。ここで、
ｍｉｎ＝ｍｉｎ（Ｍ（ｘ，ｙ），Ｍ（ｘ’，ｙ’））、
ｍａｘ＝ｍａｘ（Ｍ（ｘ，ｙ），Ｍ（ｘ’，ｙ’））である。

この費用は、フレームの割り当てが連続的であると仮定すると妥当であり、すなわち、（ｘ，ｙ）および（ｘ’，ｙ’）が隣接するピクセルの場合、これらのソースフレームＭ（ｘ，ｙ）およびＭ（ｘ’，ｙ’）は近い。この費用の主な利点は、この問題を図上の最小カットの問題として解決できることである。

我々が最小化するエネルギー関数は、

であり、ここでは、
Ｎ（ｘ，ｙ）は、（ｘ，ｙ）の隣接するピクセルである。
Ｅ（ｘ，ｙ，ｘ’，ｙ’）は、等式１で説明したように、隣接する各ピクセルのステッチ費用である。
Ｖａｌｉｄ（ｘ，ｙ，ｋ）は１であり、Ｉ_ｋ（ｘ，ｙ）は、有効ピクセル（即ち、カメラの視界内）である。
Ｄは、非常に大きな数である（無限大を意味する）。

９．単一のパノラマの生成
次に、我々は、（複雑な指数を有する）２次元の複数のラベルの問題を、（複雑な多項式を有するが実際には即座に解決できる）３次元の２つのラベルの問題に変換する方法を示す。各ピクセルｘ，ｙおよび入力フレームｋの場合、我々は、Ｘ（ｘ，ｙ）＜＝ｋの場合に１に等しい２値変数ｂ（ｘ，ｙ，ｋ）を決定する（Ｍ（ｘ，ｙ）は、ピクセル（ｘ，ｙ）のソースフレームである）。ｂ（ｘ，ｙ，ｋ）＝１であることは明らかである。

各１≦ｋ≦Ｎでｂ（ｘ，ｙ，ｋ）の場合、我々は、ｂ（ｘ，ｙ，ｋ）＝１の最小のｋとしてＭ（ｘ，ｙ）を定める。我々は、最小化が継ぎ目のないパノラマを与えるエネルギー項を記載する。各隣接するピクセル（ｘ，ｙ）および（ｘ’，ｙ’）と、各ｋの場合、我々は、ｂ（ｘ，ｙ，ｋ）≠ｂ（ｘ’，ｙ’，ｋ）の割り当てのために誤差項（error term）を追加する（この誤差項は対称である）。

また、我々は、ｂ（ｘ，ｙ，ｋ）＝１であるがｂ（ｘ，ｙ，ｋ＋１）＝０である割り当ての無限のペネルティを追加する（Ｍ（ｘ，ｙ）＜＝ｋであるがＭ（ｘ，ｙ）＞ｋが可能でないため）。

最後に、Ｉ_ｋ（ｘ，ｙ）が無効なピクセルである場合、我々は、無限のペナルティを割り当てに与えることにより、ｋ＞１の場合ｂ（ｘ，ｙ，ｋ）＝１∧ｂ（ｘ，ｙ，ｋ＋１）＝０あるいはｋ＝１の場合ｂ（ｘ，ｙ，ｋ）＝１、このピクセルを選択することを阻止することができる（これらの割り当ては、Ｍ（ｘ，ｙ）＝ｋであることを意味している）。

前述した総ての項は、３次元グリッドの変数の対であり、したがって、我々は、３次元バイナリＭＲＦのエネルギー関数を最小化として説明でき、最小カットを用いて多項式時間内でそれを最小化できる［９］。

１０．４次元最小カットを用いたパノラマ動画の生成
（長さＬの）パノラマ動画を生成すべく、我々は、一連のパノラマ画像を生成すべきである。時間的な整合性が強化されないため、各パノラマ画像を個別に生成することはよくない。別の方法は、連続的なモザイク画像が、先行するモザイクで使用された連続するフレームから各ピクセルを取得する場合、最初のフレームとして最初のモザイク画像で開始する（Ｍ_ｌ（ｘ，ｙ）＝Ｍ（ｘ，ｙ）＋１）。この可能性は、図２ｂを参照して前述したのと同様である。

本発明の第２の態様では、我々は、１のパノラマフレームから別のパノラマフレームに変化する機会をステッチに与える別の式を代わりに使用し、これは、移動するオブジェクトを上手くステッチするのに非常に重要である。

我々は、前述した３次元図の事例Ｌで構成される４次元の図を生成する。

時間的な整合性を強化すべく、我々は、無限のペナルティを割り当てに課す、即ちｌ＜Ｌそれぞれの場合はｂ（ｘ，ｙ，Ｎ，ｌ）＝１、ｌ＞１それぞれの場合はｂ（ｘ，ｙ，１，ｌ）＝０。

さらに、各（ｘ，ｙ，ｋ，ｌ）（１≦ｌ≦Ｌ−１，１≦ｋ≦Ｎ−１）の場合、我々は、
割り当てｂ（ｘ，ｙ，ｋ，ｌ）＝１≠ｂ（ｘ，ｙ，ｋ＋１，ｌ＋１）のための費用関数を設定する（ｋ＝Ｎ−１の場合、我々は費用の左項のみを使用する）。

この費用は、生成された動画内で（時間的に）連続したピクセルを表示するのを強化する（ただし、例えば、これらのピクセルは背景内である）。

この方法の変更例は、各ピクセル（ｘ，ｙ）を、連続したフレームの同じピクセルに接続するのではなく、ピクセル（ｕ，ｖ）におけるオプティカルフローにより、対応するピクセル（ｘ＋ｕ，ｙ＋ｖ）に接続する。オプティカルフローを算出する好適な方法は、例えば［１９］にある。オプティカルフローを用いることにより、移動するオブジェクトの事例をよりよく処理する。

さらに我々は、４次元図の最小カットを用いてエネルギー関数を最小化することができ、バイナリの解決方法は、ステッチの問題を軽減するパノラマ動画を決定する。

１１．実用的な改良
４次元の図を保存するには、非常に大きなメモリが必要である。したがって、我々は、メモリ要求とアルゴリズムの動作時間の双方を低減するいくつかの改良点を利用する。
・前述したように、エネルギーは、無効なピクセルのための頂点（vertices）を明確に保存することなく最小化できる。したがって、頂点の数は、入力映像内のピクセルの数に減少し、出力映像内のフレームの数により増加する。
・出力映像内の各フレームを解決する代わりに、我々は、出力フレームの標本化されたセットのみを解決し、これらの間にステッチ関数を挿入する。この改良点は、シーン内の動作があまり大きくないことを想定している。
・我々は、入力フレームの部分的なセットからのみ各ピクセルを生成することができる。これは、特に映像から取得される一連のフレームに有用であり、連続したフレームの各対の間の動作は非常に小さい。この場合、我々は、各ピクセルのために一組のソースフレームを標本化することにより、多くを失うことがない。しかし、一貫性のある方法によりソースフレームを標本化することが好適である。例えば、フレームｋが、ｌ−ｔｈ出力フレーム内のピクセル（ｘ，ｙ）のために可能なソースである場合、ｋ＋１フレームは、ｌ＋１−ｔｈ出力フレーム内のピクセル（ｘ，ｙ）のために可能なソースフレームであるべきである。
・我々は、複数の解像度のフレームワーク（multi-resolution framework）を利用し（例えば、［２］で利用されたような）、粗い解決（solution）が低解像度の画像のために発見され（バッファリングおよび標本化の後に）、解決は境界においてのみ洗練される。

ここで、我々は、関心のあるスコアにより動画を結合する方法を説明する。密度の高い（denser）あるいは薄い（sparser）活動を含む動画を生成し、あるいはユーザが特定する方法でシーンを制御するといったいくつかの応用例が存在する。

［１４］に記載された動的なパノラマは、特別な事例として考えることができ、同じ動画の異なる部分が結合されて、より大きな視界の動画が取得され、この場合、我々は、各時間の各ピクセルの「視認性」により、関心のあるスコアを決定する。さらに一般的には、同じ動画の異なる部分（時間あるいは空間的にシフトする）を結合することは、他の事例でも利用できる。例えば、動画内の活動の密度を高めるために、我々は、アクションが生じる動画の異なる部分を、多くのアクションを有する新しい動画に結合する。図１から８を参照して前述した実施例は、活動の特別な事例を説明しており、異なる方法を利用している。

取り組むべき２つの問題は、
１．動画を「見た目のよい」動画に結合する方法。例えば、我々はステッチの問題を避けたい。
２．関心のあるスコアを最大化する。

我々は、使用可能な異なるスコアを説明することから開始し、動画を結合するのに用いられるスキームを説明する。

関心のある特徴（interest function）として使用可能な主要な特徴の一つは、ピクセルの「重要度」のレベルである。我々の実験では、我々は、ピクセル内の「活動」をその重要度を示すために考慮しているが、重要度の他の測定も同様に好適である。活動レベルの評価は、本発明の特徴自体ではないが、前述したセクション１で参照された様々な方法のうちの一つ（活動検出）を利用して行うことができる。

１３．他のスコア
動画を結合するのに利用可能な他のスコア：
・視認性スコア：カメラが移動する場合、あるいは映像内の穴を埋めようとする場合、見ることができないピクセルが存在する。我々は、（必ずしも無限のスコアによってではなく）無効なピクセルにペナルティを課することができる。この方法では、我々は、穴を埋めることを促進できるが（あるいは視野を広げることができるが）、悪いステッチが生じた場合には、穴を埋めることを望まなくてもよく、あるいは小さな視野を利用してもよい。
・方向：活動の測定は、方向の測定と置き換えることができる。例えば、我々は、垂直に移動する領域よりも水平に移動する領域を好むだろう。
・ユーザ仕様：ユーザは、色、テクスチャ等の好適な関心のある特徴を指定する。さらに、ユーザは、異なるスコアにより手動で領域（およびタイムスロット）を指定する。例えば、１が、最大の活動が所望されることを意味し、０が、活動がないことが所望されることを意味するマスクを描くことにより、ユーザは、シーン内の動的性を制御でき、すなわち、特定の位置で発生させることができる。

１４．アルゴリズム
我々は、以下の変更を有する［２０］により使用される方法と同様の方法を利用する。
・我々は、１の動画あるいは別の動画から選択される各ピクセルのための関心のある領域を追加する。このスコアは、各動画の各ピクセルのエッジを利用して端末の頂点（ソースおよびシンク）に追加され、これらのエッジの重みは、関心のあるスコアである。
・我々は、（任意で）フレームの連続した各対の間のオプティカルフローを算出する。次に、一貫性を強化すべく、我々は、時間的に隣接する部分のエッジ（（ｘ，ｙ，ｔ）から（ｘ，ｙ，ｔ＋１））を、オプティカルフローによる隣接部分のエッジ（（ｘ，ｙ，ｔ）から（ｘ＋ｕ（ｘ，ｙ），ｙ＋ｖ（ｘ，ｙ），ｔ＋１））と交換できる。これは、ステッチが顕著でないフローに従うように奨励するように、ステッチ動画間の遷移を強化する。
・動画のいずれの部分（あるいは移動する部分）が結合されるかを決定する場合、ステッチ費用だけでなく、関心のあるスコアを考慮すべきである。例えば、密度の高い活動レベルを有する動画を生成する場合、我々は、スコアを最大化する動画のセットＳを選択する。

図９ｂは、動画の増加した活動密度のような効果を示した図であり、オリジナルのフレームは図９ａに示されている。２つ以上の動画が結合された場合、我々は反復手段を利用し、この反復により、新しい動画が、生成された動画に結合される。正確に行うために、以前の反復により生成された古い継ぎ目およびスコアを考慮すべきである。関心のあるスコアが無いにも拘わらず、このスキームは［２０］に記載されている。生成された映像のサンプルフレームが、図９ｂに示されている。

図１０は、処理の概略図である。この例では、映像は、時間的にシフトした映像と結合される。結合は、前述した基準、すなわちステッチ費用を最小限にしつつ関心のあるスコアを最大化することに基づいて、最小カットを用いて行われる。

ここで図１１を参照すると、カメラ１１により取得された第１の動的シーンの映像フレームの第１のシーケンスを、第２の動的シーンを示す少なくとも２つの映像フレームの第２のシーケンスに変換する本発明に係るシステム１０のブロック図が示されている。このシステムは、各ｘ，ｙ座標に配置された複数のピクセルを備える少なくとも一つのオブジェクトの動作を示す第１のシーケンス無いの映像フレームのサブセットを記憶する第１のメモリ１２を備えている。第１の動的なシーン内の少なくとも一つのオブジェクトの空間的に重ならない外観を示すサブセット部分から選択する選択ユニット１３が、第１のメモリ１２に連結される。フレーム生成部１４は、オブジェクト内のピクセルの各ｘ，ｙ座標を変更することなく、少なくとも３つの異なる入力フレームの部分を、第２のシーケンスの少なくとも２つの連続したフレームにコピーし、第２のシーケンスの少なくとも一つのフレームが、第１のシーケンス内の異なるフレームに現れる少なくとも２つの部分を含む。第２のシーケンスのフレームは、ディスプレイユニット１６による後の処理あるいは表示のために、第２のメモリ１５に格納される。フレーム生成部１４は、第２のシーケンスをコピーする前に少なくとも２つの部分を空間的に移動させる移動ユニット（warping unit）１７を備えてもよい。

実際には、システム１０は、本分野で周知のように、グラフィックカードあるいはワークステーションおよび好適な周辺機器を有する最適にプログラムされたコンピュータにより実現される。

システム１０では、少なくとも３つの異なる入力フレームは時間的に近い。システム１０はさらに、映像フレームの第１のシーケンスを予め整列させるために、第１のメモリに結合された任意の整列ユニット１８を備えてもよい。この場合、カメラ１１は、第１のメモリ１２内の予め整列された映像フレームを格納するために整列ユニット１８に連結される。整列ユニット１８は、
第１のシーケンス内のフレーム間の画像動作パラメータを算出し、
第１の動的シーン内の静止したオブジェクトが映像内で静止するように、第１のシーケンス内の映像フレームを移動させることにより動作する。

同様に、システム１０は、整列された空間および時間量を「タイムフロント」表面により一掃し、一連のタイムスライスを生成するために、選択ユニット１３に連結された任意のタイムスライス生成部１９を備えてもよい。

これらの任意の特徴は、「タイムフロント」および「タイムスライス」の語は、参照されている前述したＷＯ２００６／０４８８７５に完全に記載されているのと同様であるため、詳細には説明されていない。

完全にするために、図１２は、本発明に係るシステム１０により実行される主要な処理を示すフロー図である。

１５．考察
映像概要は、映像内の活動を非常に短い期間に凝縮する手段として提案されている。この凝縮された表示は、映像シーケンス内の活動への効率的なアクセスを可能にする。２つの手段が提案されており、１つの手段は、低いレベルのグラフの最適化を用い、映像概要内の各ピクセルは、このグラフ内のノードである。この手段は、入力映像から直接的に映像概要を取得する利点を有しているが、解決（solution）の複雑度が非常に高い。代替的な手段は、最初に移動するオブジェクトを検出し、検出されたオブジェクトを最適化することである。第２の手段では動作のセグメンテーションの予備段階が必要とされるが、これは非常に高速であり、オブジェクトに基づく制約が可能である。生成される映像概要の活動は、オリジナルの映像よりも非常に凝縮されており、このような概要は、これを利用したことのない者にとっては扱い難いかもしれない。しかし、多くの情報を短い時間内で観察することを目的とする場合、映像概要はこの目的を達成する。特別な注意が、動的なストロボスコープを取得する可能性に払われるべきである。映像概要の長さをさらに減少させるとともに、動的なストロボスコープはユーザからの調整を必要としてもよい。単一のオブジェクトの複数の空間的な出現は、長い活動時間を示すことが分かることにはいくらかの訓練を必要とする。我々は、動的な映像概要の特定の実施例を説明しているが、多くの拡張も可能である。例えば、バイナリの「活動」インジケータを有するのではなく、活動インジケータが連続していてもよい。連続的な活動は、例えば、活動レベルに基づいて、表示されたオブジェクトの速度を制御することにより、映像概要を生成可能な選択肢を広げることができる。また、映像概要は、多くのショットから成る長い動画のために用いてもよい。理論的に、我々のアルゴリズムは、重なり（あるいは不連続性）による不利益のために、異なるシーンの部分を結合させない。この場合、単一のショットに利用される単一の背景モデルは、調整可能な背景推定器と交換される。長い動画に利用される別の手段は、ショットのバイナリ検出の従来の方法を利用し、ショット毎に個別に映像概要を生成することである。

本発明に係るシステムは、プログラムされたコンピュータに最適であることは理解できるであろう。同様に本発明は、本発明の方法を実行すべく、コンピュータにより読み取り可能なコンピュータプログラムを意図する。さらに本発明は、本発明の方法を実施する機械により実行可能なプログラム命令を明確に実行する機械読み取り可能なメモリを意図する。

図１は、時間的に配置された特徴を同時に表示することによりコンパクトな映像概要を生成する本発明のアプローチを示す図である。図２ａは、本発明により生成される映像概要を表わす概略図である。図２ｂは、本発明により生成される映像概要を表わす概略図である。図３ａは、本発明による一時的な再配置の例を示す図である。図３ｂは、本発明による一時的な再配置の例を示す図である。図３ｃは、本発明による一時的な再配置の例を示す図である。図４は、図３ｂに示す動的なストロボ効果を利用した映像概要の単一のフレームを示す図である。図５ａは、短い概要が、活動を損なうことなく且つストロボ効果なしで、長いシーケンスを表示できる場合の例を示す図である。図５ｂは、短い概要が、活動を損なうことなく且つストロボ効果なしで、長いシーケンスを表示できる場合の例を示す図である。図５ｃは、短い概要が、活動を損なうことなく且つストロボ効果なしで、長いシーケンスを表示できる場合の例を示す図である。図６は、本発明によるパノラマの映像概要の更なる例を示す図である。図７ａは、ストリートの監視の映像概要の詳細を示す図である。図７ｂは、ストリートの監視の映像概要の詳細を示す図である。図７ｃは、ストリートの監視の映像概要の詳細を示す図である。図８ａは、フェンスの監視の映像概要の詳細を示す図である。図８ｂは、フェンスの監視の映像概要の詳細を示す図である。図９ａは、本発明の更なる実施例による動画の増加する活動密度を示す図である。図９ｂは、本発明の更なる実施例による動画の増加する活動密度を示す図である。図１０は、図９に示す動画を生成するのに利用される処理の概略図である。図１１は、本発明によるシステムの主要な機能を示すブロック図である。図１２は、本発明により実行される主要な動作を示すフロー図である。

Claims

ビデオカメラによって取得された第１の動的シーンの映像フレームのソースシーケンスを、第２の動的シーンを表示する映像フレームのより短い概要シーケンスに変換することによって、映像概要（ｖｉｄｅｏｓｙｎｏｐｓｉｓ）を生成するための方法であって、当該方法が、
少なくとも一つのオブジェクトの動作を示す前記ソースシーケンスの映像フレームのサブセットを取得するステップであって、各オブジェクトが、前記ソースシーケンスの少なくとも３の異なるフレームからの、各フレーム内で互いに連結されたピクセルのサブセットであるステップを具え、当該方法が、
前記ソースシーケンスから少なくとも３のソースオブジェクトを選択し、時間サンプリング（ｔｅｍｐｏｒａｌｓａｍｐｌｉｎｇ）によって、各々の選択されたソースオブジェクトから１又はそれ以上の概要オブジェクトをサンプリングするステップであって、前記時間サンプリングが、ソースシーケンスのＮ個のフレームを映像シーケンスのＭ個（ＮはＭとは異なる）のフレームにマッピングするものであり、前記選択が、オブジェクトの現れる時間、オブジェクトの種類、およびオブジェクトの動作の種類のうちの少なくとも１つを含む選択基準に基づくものであるステップと、
各概要オブジェクトについて前記映像概要における表示を開始する各表示時間を決定するステップであって、映像概要の全体の再生時間が前記ソースシーケンスの再生時間よりも短くなるように、概要オブジェクトの各々について表示時間を決定するステップと、
前記ソースシーケンスのそれぞれ異なる時間で得られた少なくとも２の概要オブジェクトが、前記映像概要中に同時に表示されるように、前記第１の動的シーンの前記オブジェクトの空間的な位置を変更することなく、概要オブジェクトをそれぞれの所定の表示時間で表示することによって前記映像概要を生成するステップと、によって特徴付けられる方法。
請求項１に記載の方法において、前記オブジェクトのうちの１つが背景オブジェクトであることを特徴とする方法。
請求項２に記載の方法において、前記オブジェクトと前記背景とを継ぎ目のない映像につなぎ合わせることを特徴とする方法。
請求項１乃至３のいずれか１項に記載の方法において、前記ソースオブジェクトが選択され、各概要オブジェクトの表示を開始する各時間が費用関数を最適化するように決定され、前記費用関数が、前記映像概要の長さとその質的な映像基準（ｑｕａｌｉｔａｔｉｖｅｖｉｄｅｏｍｅｔｒｉｃｓ）との間の妥協点を決定するものであることを特徴とする方法。
請求項１乃至４のいずれか１項に記載の方法において、前記ソースシーケンスが固定位置で軸に対し回転するカメラによって取得され、前記概要シーケンスにコピーする前に少なくとも前記ソースオブジェクトの少なくとも２つを空間的に移動させることを特徴とする方法。
請求項１乃至４のいずれか１項に記載の方法において、前記ソースシーケンスが固定位置で静止カメラによって取得されることを特徴とする方法。
請求項１乃至６のいずれか１項に記載の方法において、少なくとも３の異なるソースフレームが時間的に連続していることを特徴とする方法。
請求項１乃至７のいずれか１項に記載の方法において、前記ソース映像シーケンスにおいて同時に発生する２のイベントが、前記概要シーケンスにおいて異なる時間に表示されることを特徴とする方法。
請求項１乃至８のいずれか１項に記載の方法が、監視用映像概要、動画の活動密度（ａｃｔｉｖｉｔｙｄｅｎｓｉｔｙ）の増加、映像インデックスのいずれかに用いられることを特徴とする方法。
請求項９に記載の方法が、前記概要シーケンス内の各ピクセルについて、前記ソースシーケンス内の対応するピクセルへのポインタを維持するステップを含むことを特徴とする方法。
請求項１乃至１０のいずれか１項に記載の方法であって、
（ａ）前記ソースシーケンスのフレーム間の画像動作パラメータを算出し、
（ｂ）前記第１の動的シーン内の静止したオブジェクトが整列されたソースシーケンス内で静止するように、前記ソースシーケンス内の映像フレームを移動させることにより、前記整列されたソースシーケンスを与えるように、当該ソースシーケンスを事前に整列させるステップを含むことを特徴とする方法。
第１の動的シーンの映像フレームのソースシーケンスを、第２の動的シーンを表示する少なくとも２つの映像フレームの概要シーケンスに変換するシステム（１０）であって、当該システムが、
少なくとも一つのオブジェクトの動作を示す前記ソースシーケンス内の映像フレームのサブセットを格納し、各々のオブジェクトが、少なくとも３の異なるソースフレームからの、各フレーム内で互いに連結されたピクセルのサブセットであり、前記時間サンプリングが、ソースシーケンスのＮ個のフレームを映像シーケンスのＭ個のフレーム（ＮはＭとは異なる）にマッピングするものであり、前記選択が、オブジェクトの現れる時間、オブジェクトの種類、およびオブジェクトの動作の種類のうちの少なくとも１つを含む選択基準に基づくものである、第１のメモリ（１２）を具え、前記システムが、
前記ソースシーケンスから少なくとも３のオブジェクトを選択し、時間サンプリングによって、各々の選択されたソースオブジェクトから１又はそれ以上の概要オブジェクトをサンプリングする、前記第１のメモリ（１２）に連結された選択ユニット（１３）と、
各概要オブジェクトについて、映像概要における表示を開始するために各表示時間を決定し、前記ソースシーケンスのそれぞれ異なる時間で得た少なくとも２の概要オブジェクトが、前記映像概要中に同時に表示されるように、前記オブジェクトの空間的位置又は前記第１の動的シーンにおいてそこから得られる前記それぞれのオブジェクトを変更することなく、概要オブジェクト、又は、各所定の表示時間でそこから得られたオブジェクトとを表示することによって前記映像概要を生成する、フレーム生成部であって、映像概要の全体の再生時間が前記ソースシーケンスの再生時間よりも短くなるように、概要オブジェクトの各々について表示時間を決定するフレーム生成部（１４）と、
前記フレーム生成部に連結されて、前記概要シーケンスのフレームを蓄積する、第２のメモリ（１５）と、
前記第２の動的シーンを表示すべく、前記第２のメモリ（１５）にディスプレイ装置（１６）を連結する手段とによって特徴付けられるシステム。
請求項１２に記載のシステムにおいて、前記フレーム生成部（１４）が、前記概要シーケンスにコピーする前に、前記ソースオブジェクトの少なくとも２つを空間的に移動させる移動ユニット（１７）を具えることを特徴とするシステム。
コンピュータプログラムであって、当該プログラムがコンピュータ上で実行されるときに、請求項１乃至１１のいずれか１項に記載の方法を実行するコンピュータプログラムコードを具えることを特徴とするコンピュータプログラム。