(57)【要約】  ソースビデオからシノプシス ビデオを生成するためのシステムおよび方法では、１つ以上の定義された制約に従って、少なくとも３つの異なるソース対象物が選択され、各ソース対象物は、ソースビデオの少なくとも３つの異なるフレームからのイメージポイントが連結されたサブセットである。特定の期間から抽出されたイメージポイントを用いた時間的なサンプリングにより、各選択されたソース対象物から、１つ以上のシノプシス対象物がサンプリングされる。各シノプシス対象物について、シノプシス ビデオにおける表示を開始するための時間が各々決定され、かつ、各シノプシス対象物および各フレームについて、シノプシス対象物を表示するための各々の色変換が決定され得る。それら各時間および色変換で、選択されたシノプシス対象物を表示することにより、シノプシス ビデオが表示され、それにより、シノプシス ビデオ中には、ソースビデオ中の各々異なる時間から抽出された少なくとも３つのポイントが同時に表示される。【選択図】図１５
2010518673.tif 000002
【特許請求の範囲】
【請求項１】
ソースビデオからシノプシス ビデオを生成するための、コンピュータで実施される方法であって、当該方法は、
１つ以上の定義された制約に従って、少なくとも３つの異なるソース対象物を選択することを有し、各ソース対象物は、ソースビデオの少なくとも３つの異なるフレームからのイメージポイントからなる連結されたサブセットであり、
各選択されたソース対象物から、１つ以上のシノプシス対象物をサンプリングすることを有し、該サンプリングは、特定の期間から抽出されたイメージポイントを用いた時間的サンプリングによって行い、
各シノプシス対象物に対して、シノプシス ビデオ中での表示を開始するためのそれぞれの時間を決定することを有し、かつ、
前記のそれぞれの時間において、選択されたシノプシス対象物またはそれらから抽出された対象物を表示することによって、シノプシス ビデオを表示することを有し、
それにより、シノプシス ビデオ中には、ソースビデオ中の異なるそれぞれの時間から各々抽出された少なくとも３つのポイントが、同時に表示されるようになっている、
前記方法。
【請求項２】
さらに、
各シノプシス対象物および各フレームについて、そのシノプシス対象物を表示するための各々の色変換を決定すること、および、
選択されたシノプシス対象物またはそれらから抽出された対象物を、それらの各々の色変換で表示すること、
を有する、請求項１に記載の方法。
【請求項３】
対象物の一つが、背景対象物である、請求項１または２に記載の方法。
【請求項４】
背景のタイムラプスビデオを構築することを含んでいる、請求項３に記載の方法。
【請求項５】
対象物と背景とを、継ぎ目のないビデオ中にステッチングすることを含んでいる、請求項３または４に記載の方法。
【請求項６】
コスト関数を最適化するように、ソース対象物が選択されかつ各シノプシス対象物のための各々の時間が決定される、請求項１から５のいずれか１項に記載の方法。
【請求項７】
背景対象物が合成により生成される、請求項１から６のいずれか１項に記載の方法。
【請求項８】
シノプシス ビデオ中の各対象物が、ソースビデオ中のセグメントを指し示し、該セグメントでそれぞれの対象物を見ることができる、請求項１から７のいずれか１項に記載の方法。
【請求項９】
対象物を選択することによって、その選択された対象物によって指し示されたソースビデオ中のセグメントが再生される、請求項８に記載の方法。
【請求項１０】
シノプシス ビデオ中の少なくとも一つの対象物が、ソースビデオ中の対応する対象物を予め定められたシンボルで置き換えることによって形成される、請求項１から９のいずれか１項に記載の方法。
【請求項１１】
対象物が類似のクラスへと先ず集団化され、かつ、シノプシス ビデオが、少なくとも予め定められた個数のクラスからの対象物を含んでいる、請求項１から１０のいずれか１項に記載の方法。
【請求項１２】
対象物が類似のクラスへと先ず集団化され、かつ、少なくとも一つの選択されたクラスからの対象物が表示されない、請求項１から１１のいずれか１項に記載の方法。
【請求項１３】
対象物が類似のクラスに先ず集団化され、かつ、対象物の選択が、選択された対象物と同じクラスからの対象物のみを含むビデオ シノプシスを指し示す、請求項８または９に記載の方法。
【請求項１４】
１つ以上のソース対象物の選択が、
シノプシス対象物をステッチングするためのコスト関数を計算すること、および、
得ることができる最適物にコスト関数が近いと判断されるシノプシス対象物を選択すること、
を含んでいる、請求項１から１３のいずれか１項に記載の方法。
【請求項１５】
少なくとも３つのオーバーラップしないソース対象物を選択することが、特定の時間ウィンドウ中に現れるソース対象物に限定される、請求項１から１４のいずれか１項に記載の方法。
【請求項１６】
少なくとも３つのオーバーラップしないソース対象物を選択することが、興味のスコアを決定することを含んでいる、請求項１から１５のいずれか１項に記載の方法。
【請求項１７】
興味のスコアが活動の指標である、請求項１６に記載の方法。
【請求項１８】
シノプシス ビデオが、ソースビデオ中の興味を引く全ての対象物を含んでいる、請求項１から１７のいずれか１項に記載の方法。
【請求項１９】
シノプシス ビデオ中においても現れる、ソースビデオ中の興味を引く対象物の個数が、その個数を最大化することと、同時に該シノプシス ビデオの視覚的なアピールを維持することとの間のトレードオフである、請求項１から１７のいずれか１項に記載の方法。
【請求項２０】
ソースビデオが単一のカメラによって記録される、請求項１から１９のいずれか１項に記載の方法。
【請求項２１】
単一のカメラを固定された位置に保つことを有する、請求項２０に記載の方法。
【請求項２２】
カメラが、固定された位置において、軸に関して回転される、請求項２１に記載の方法。
【請求項２３】
シノプシス対象物の少なくとも一つを、その表示の前に、空間的に歪ませることを有する、請求項１から２２のいずれか１項に記載の方法。
【請求項２４】
安定化されたソースビデオを作成するように、ソースビデオを事前位置合わせすることを有し、事前位置合わせを、
（ａ）ソースビデオ中のフレーム同士の間でイメージモーションのパラメータを計算することによって、
（ｂ）ソースビデオ中のビデオフレームを、動いていない対象物が安定化されたソースビデオ中に静止して現れるように、歪ませることによって、
行うものである、
請求項１から２３のいずれか１項に記載の方法。
【請求項２５】
ソースビデオ中に同時に出現する２つの活動が、シノプシス ビデオ中では異なる時点で表示される、請求項１から２４のいずれか１項に記載の方法。
【請求項２６】
ビデオ監視のために使用される、請求項１から２５のいずれか１項に記載の方法。
【請求項２７】
ビデオの索引付けと、ビデオの閲覧と、ビデオの検索とからなる群の中の、少なくとも一つのために使用される、請求項１から２５のいずれか１項に記載の方法。
【請求項２８】
シノプシス ビデオ中の各ピクセルについて、ソースビデオ中に対応するピクセルへのポインタを保つことを有する、請求項２７に記載の方法。
【請求項２９】
ソースビデオが連続的に記録される、請求項１から２８のいずれか１項に記載の方法。
【請求項３０】
制約が予め定義される、請求項１から２９のいずれか１項に記載の方法。
【請求項３１】
制約がユーザーによって定義される、請求項１から２９のいずれか１項に記載の方法。
【請求項３２】
コンピュータプログラムであって、
当該プログラムがコンピュータ上で実行されるときに、請求項１から３１のいずれか１項に記載の方法を実行するためのコンピュータプログラムコード手段を有している、前記コンピュータプログラム。
【請求項３３】
コンピュータ読み取り可能な媒体に記録されている、請求項３２に記載のコンピュータプログラム。
【請求項３４】
ソースビデオからシノプシス ビデオを生成するためのシステム（１０）であって、当該システムは、
ソース対象物選択器（１８）を有し、該ソース対象物選択器は、ソースビデオ中の対象物を格納する対象物メモリ（１６）に結合されるように構成され、１つ以上の定義された制約に従って少なくとも３つの異なるソース対象物を選択するためのものであって、各ソース対象物は、ソースビデオの少なくとも３つの異なるフレームからのイメージポイントによる連結されたサブセットであり、
シノプシス対象物サンプラー（２０）を有し、該シノプシス対象物サンプラーは、ソース対象物選択器（１８）に結合され、特定の期間から抽出されたイメージポイントを用いた時間的なサンプリングによって、各選択されたソース対象物から、１つ以上のシノプシス対象物をサンプリングするためのものであり、
時間選択ユニット（２３）を有し、該時間選択ユニットは、シノプシス対象物サンプラー（２０）に結合され、各シノプシス対象物について、シノプシス ビデオ中にその表示を開始するためのそれぞれの時間を決定するためのものであり、
ステッチングユニット（２６）を有し、該ステッチングユニットは、時間選択ユニット（２３）に結合され、選択されたシノプシス対象物を、または、それらのそれぞれの時間においてそれらから抽出された対象物をステッチングし、連続的なシノプシス ビデオフレームを生成するためのものであり、それにより、該シノプシス ビデオフレームでは、ソースビデオにおける各々異なるそれぞれの時間から抽出された少なくとも３つのポイントが、同時に表示されるようになっており、かつ、
シノプシスフレームメモリ（２７）を有し、該シノプシスフレームメモリは、ステッチングユニット（２６）に結合され、該シノプシス ビデオフレームを格納するためのものである、
前記システム。
【請求項３５】
さらに、表示ユニット（２８）を有し、該表示ユニットは、ステッチングユニット（２５）に結合され、シノプシス ビデオを表示するためのものである、請求項３４に記載のシステム。
【請求項３６】
さらに、色変換ユニット（２４）を有し、該色変換ユニットは、時間選択ユニット（２３）に結合され、各シノプシス対象物および各フレームに対して、該シノプシス対象物の表示のための各々の色変換を決定するためのものであり、
選択されたシノプシス対象物を、または、それらから抽出された対象物を、それらの各々の色変換においてステッチングするために、ステッチングユニット（２６）が、該色変換ユニット（２４）に結合されている、
請求項３４または３５に記載のシステム。
【請求項３７】
さらに、ユーザーインターフェース（１７）を有し、該ユーザーインターフェースは、対象物メモリ（１６）に結合され、ユーザー定義の制約が定義されるのを可能とするためのものである、請求項３４から３６のいずれか１項に記載のシステム。
【請求項３８】
さらに、集団化ユニット（１９）を有し、該集団化ユニットは、定義された基準に従って、対象物を集団化するためのものである、請求項３４から３７のいずれか１項に記載のシステム。
【請求項３９】
さらに、前置プロセッサ（１３）を有し、該前置プロセッサは、オンラインで記録されたビデオを処理しソースビデオ中の対象物を検出するためのものであり、該前置プロセッサ（１３）は、対象物メモリ（１６）に対象物メモリ（１６）に結合され、対象物をそこに格納するように構成されている、請求項３４から３８のいずれか１項に記載のシステム。
【請求項４０】
前置プロセッサ（１３）が、ソースビデオ中のビデオフレームを事前位置合わせするための位置合わせユニット（１４）を有している、請求項３９に記載のシステム。
【請求項４１】
位置合わせユニット（１４）が、
第一のシークエンス中のフレーム間でのイメージモーションのパラメータを計算するように構成され、かつ、
第一の動的なシーン中の静止している対象物が、該ビデオ中で静止するように、第一のシークエンス中のビデオフレームを歪ませるように構成されている、
請求項４０に記載のシステム。
【請求項４２】
フレームジェネレータがワーピングユニット（２５）を有し、該ワーピングユニットは、シノプシス ビデオへのステッチングの前に、少なくとも一つの対象物を空間的に歪ませるためのものである、請求項３４から４１のいずれか１項に記載のシステム。
【請求項４３】
ビデオの索引付けと、ビデオの閲覧と、ビデオの検索とからなる群の中の、少なくとも一つのために構成されている、請求項３４から４２のいずれか１項に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本出願は、2007年5月24日に公開された ＷＯ2007/057893（Rav-Acha et al.） "Method and system for producing a video synopsis（ビデオシノプシスを生成するための方法とシステム）"（出願日2006年11月15日）の一部継続出願であり、さらに、2007年2月1日に出願された仮特許出願第60/898,698号；2007年4月13日に出願された同第60/911,839号および2007年9月12日に出願された同第60/971,582号（これらの内容の全ては、参照することにより本明細書に組み込まれる）の利益を主張する。
【０００２】
発明の分野
本発明は、ビデオの要約化（summarization）およびビデオの索引付け（indexing）の分野に関する。
【背景技術】
【０００３】
先行技術
本発明の背景として関連すると思われる先行技術文献を以下に挙げる。これらの内容は、参照することによって本明細書に組み込まれる。更なる参照文献は、上記米国仮特許出願第60/898,698号；同第60/911,839号および同第60/971,582号で言及されており、それらの内容は参照することによって本明細書に組み込まれる。本明細書での参照文献の確認は、それらが本明細書に開示された発明の特許性に何らかの関係があることを意味するものとして推測されてはならない。各参照文献は、角括弧で囲まれた数字によって特定され、従って、先行技術を、本明細書全体を通じて、角括弧で囲まれた数字で呼ぶ。
【０００４】
[1] A. Agarwala, M. Dontcheva, M. Agrawala, S. Drucker, A. Colburn, B. Curless, D. Salesin, and M. Cohen. Interactive digital photomontage. In SIGGRAPH, pages 294-302, 2004.
[2] Y. Boykov and V. Kolmogorov. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans, on Pattern Analysis and Machine Intelligence, 26(9):1124-1137, Sep. 2004. 
[3] S. Cohen. Background estimation as a labeling problem. In ICCV'05, pages
1034-1041, Washington, DC, 2005. 
[4] A. Divakaran, K. Peker, R. Radhakrishnan, Z. Xiong, and R. Cabasson. Video summarization using mpeg-7 motion activity and audio descriptors. Technical Report TR-2003-34, MERL - A Mitsubishi Electric Research Laboratory, Cambridge, Massachusetts, May 2003. 
[5] G. Doretto, A. Chiuso, Y. Wu, and S. Soatto. Dynamic textures. Int. J. Computer Vision, 51 :91-109, 2003.
[6] M. Irani, P. Anandan, J. Bergen, R. Kumar, and S. Hsu. Efficient representations of video sequences and their applications. Signal Processing: Image Communication, 8(4):327-351, 1996. 
[7] H. Kang, Y. Matsushita, X. Tang, and X. Chen. Space-time video montage. In
CVPR'06, pages 1331-1338, New-York, June 2006.
[8] C. Kim and J. Hwang. An integrated scheme for object-based video abstraction. In ACM Multimedia, pages 303-311, New York, 2000.
[9] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 4598(13):671-680, 1983. 
[10] V. Kolmogorov and R. Zabih. What energy functions can be minimized via graph cuts? In ECCV, pages 65-81, 2002. 
[11] Y. Li, T. Zhang, and D. Tretter. An overview of video abstraction techniques. Technical Report HPL-2001-191, HP Laboratory, 2001. 
[12] J. Nam and A. Tewfik. Video abstract of video. In 3rd IEEE Workshop on
Multimedia Signal Processing, pages 117-122, Copenhagen, Sept. 1999. 
[13] 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. 
[14] M. Oren, C. Papageorgiou, P. Shinha, E. Osuna, , and T. Poggio. A trainable system for people detection. In Proceedings of Image Understanding Workshop, pages 207-214, 1997. 
[15] M. Gangnet P. Perez and A. Blake. Poisson image editing. In SIGGRAPH, pages 313-318, July 2003. 
[16] C. Pal and N. Jojic. Interactive montages of sprites for indexing and summarizing security video. In Video Proceedings of CVPR05, page II: 1192, 2005. 
[17] R. Patil, P. Rybski, T. Kanade, and M. Veloso. People detection and tracking in high resolution panoramic video mosaic. In Int. Conf. on Intelligent Robots and Systems (IROS 2004), volume 1, pages 1323-1328, October 2004.
[18] N. Petrovic, N. Jojic, and T. Huang. Adaptive video fast forward. Multimedia Tools and Applications, 26(3):327-344, August 2005. 
[19] 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.
[20] A. Rav-Acha, Y. Pritch, and S. Peleg. Making a long video short: Dynamic video synopsis. In CVPR'06, pages 435-441, New-York, June 2006. 
[21] A. M. Smith and T. Kanade. Video skimming and characterization through the combination of image and language understanding. In CAIVD, pages 61-70, 1998.
[22] J. Sun, W. Zhang, X. Tang, and H. Shum. Background cut. In ECCV, pages 628-641, 2006. 
[23] Y. Weiss and W.T. Freeman. On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs. IEEE Transactions on Information Theory, 47(2): 723-735, 2001.
[24] 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.
[25] S. Peleg and A. Rav-Acha, WO2007/057893 "Method and system for producing a video synopsis"
[26] J. Assa, Y. Caspi, and D. Cohen-Or. Action synopsis: Pose selection and illustration. In SIGGRAPH, pages 667-676, 2005. 
[27] Carsten Rother, Lucas Bordeaux, Youssef Hamadi, and Andrew Blake. Autocollage. ACM Transactions on Graphics, 25(3):847-852, July 2006. 
[28] Aseem Agarwala. Efficient gradient-domain compositing using quadtrees. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2007), 2007. 
[29] G. Brostow and I. Essa. Motion based decompositing of video. In ICCV'99, pages 8-13, Corfu, 1999. 
[30] J. Shi and J. Malik, Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888-905, 2000.
[31] O. Boiman and M. Irani. Detecting irregularities in images and in video. In ICCV, pages I: 462-469, Beijing, 2005. 
[32] B.M. Carvalho, G.T. Herman, and T. Y. Kong. Simultaneous fuzzy segmentation of multiple objects. Discrete Applied Mathematics, VoI 151, No. 1-3, Oct 2005, pp 55-77.
[33] G.T. Herman and B.M. Carvalho. Multiseeded Segmentation Using Fuzzy Connectedness. IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 no.5, pp. 460-474, May 2001.
[34] A. Levin, A. Rav-Acha, and D. Lischinski. Spectral Matting. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), Minneapolis, June 2007.
[35] N. E. Apostoloff and A. W. Fitzgibbon. Bayesian video matting using learnt image priors. In Proceedings IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), June 2004, Washington DC.
【０００５】
発明の背景
手を加えていない（未加工）ビデオのコレクションをソートすることは、興味を引く何か（anything of interest）が記録されているかどうかを確認すべくビデオクリップを見る必要があるので、時間がかかる。この退屈な作業は、個人のビデオコレクションでは実行可能であるかもしれないが、監視カメラやウェブカメラによって記録されたような、終わりのないビデオが関係する場合には、受け入れがたいことである。何百万ものウェブカメラが世界中をカバーし、１日２４時間、それらの視界を記録している。ＵＫだけでも、街の通りを覆う何百万もの監視カメラがあると報告されている。多くのウェブカメラは、誰もが見られるように、公共へのインターネットを通じてそれらのビデオの発信さえしている。多くの監視カメラもまた、店、空港および他の公共の場所においてオンラインで利用可能である。
【０００６】
ウェブカメラを利用するにあたっての一つの問題点は、それらが未加工、未編集のデータを提供しているということである。それゆえ、たいていの監視ビデオは、決して見られもしないし、調べられもしない。以前のＷＯ2007/057893 [25]において、我々は、複数のオリジナルのシーンのイメージから、選択された部分を組み合わせることにより、短縮されたビデオを生成するためのビデオ シノプシス（video synopsis、ビデオの概要、ビデオのあらまし）のための方法を提案した。
ビデオクリップは時間に沿って視覚的に活動（activities）を表現し、また、時間軸の圧縮により、そのようなクリップの要約を短い時間で見ることが可能となる。いくつかのフレームが選択されたフレームの間でスキップされる早送りが、ビデオの要約のために使用される最も一般的なツールである。早送りの特殊なケースは、「タイムラプス（time lapse、微速度）」と呼ばれるものであり、それは、花の成長などのような、非常に遅いプロセスのビデオを生成する。早送りは、抜け落ちたフレームの間の速い活動（fast activities）を失うことがあり得るため、適応性のある（adaptive）早送りのための方法が開発された[12, 18, 4]。そのような方法は、低い興味のまたは活動がより低いピリオドにおけるフレームをスキップし、より強い興味を引くまたはより高い活動のピリオドにおけるフレームを保とうとするものである。同様のアプローチにより、ビデオから、その内容を最も良く表す短いビデオ シークエンス（video sequences、動画像列）の集まりが抽出される[21]。
【０００７】
ビデオ シノプシスのための多くのアプローチは、時間軸を完全に排除し、数個のキーとなるフレームを選択することによってビデオ シノプシスを示すものである[8, 24]。これらのキーとなるフレームは、任意に選択され得るか、あるいは何らかの重要性の基準に従って選択され得る。しかし、キーとなるフレームの表現は、ビデオの動的な側面を失う。ビデオの抽象化についての総合的な概観は、[11, 13]に見られる。
【０００８】
上記の両アプローチでは、全フレームが基本となるビルディングブロックとして使用される。異なる方法論では、ビデオの索引付けのための何らかのメタデータと共に、寄せ集めのイメージが使用される[6, 19, 16]。この場合、静止したシノプシスのイメージには、異なる時点からの対象物（オブジェクト）が含まれる。
【０００９】
ビデオ シノプシスのための対象物ベースの（対象物に基づいた）アプローチは、[20, 7]で提示されたのが最初であり、それらでは、動く対象物が空間・時間ドメイン中に表現されている。ビデオの連続的なフレームにわたって対象物または活動を表現するイメージ部分の連結は「チューブ（tubes）」と呼ばれる。
対象物は、チューブによって空間・時間ボリューム（space-time volume）で表現されるため、用語「対象物」および「チューブ」は、以下の説明では交換可能に使用される。
これらの論文[20, 7]は、異なる時点からの活動を組み合わせたシノプシス ビデオを生成するという新たな概念を導入した（図１参照）。
【００１０】
対象物ベースのアプローチの例は、本願出願人に譲渡されたＷＯ2007/057893 [25]で開示されており、そこでは、１つ以上の対象物の動きを示す入力ビデオ中のフレームのサブセットが得られる。サブセットからの選択された部分（それは、一つ目の動的なシーンにおける空間的にオーバーラップしない対象物の出現を示す）が、複数の入力フレームから出力ビデオ列における減少した個数のフレームへとコピーされ、入力ビデオにおいては異なる時点で見られる対象物の複数の位置が、出力ビデオでは同時に示されるようになっている。
【００１１】
参照文献[20, 7]で開示されたアプローチは、時間的順序を強制しなければ、より短いビデオにおいてより多くの活動を示すことができるという見解に基づいている。所望の限度にまで出力ビデオの時間的長さ（duration）を制限するために、そしてそれにも関わらず特徴が失われるリスクを低減する制御された様式でそれを行うために、終わりのないビデオシークエンス（監視カメラを用いて得られるようなもの）のシノプシスに対して、そのようなアプローチを拡張することは有用であろう。
【００１２】
長いビデオの効率的な索引付け（indexing）、検索（retrieval）および、閲覧（browsing、ブラウジング）は、特に、終わることなくビデオを収集する監視カメラの数が急速に増加していることを考えると、重要性を増している。従来のビデオの索引付けは、キーワードを用いたビデオのマニュアルでのアノテーションを使用しているが、この方法は時間がかかり、監視カメラのためには実用的でない。更なるビデオの索引付けの方法が提案されており、それは、入力ビデオからの、代表的なキーフレームまたは代表的な時間的区間（タイム インターバル）の選択に基づいている。
【００１３】
カバーされた期間（タイム ピリオド）中の多くの対象物が短いシノプシス ビデオで示されるため、ビデオ シノプシスは、索引付け、検索、および、閲覧のために使用され得る。しかしながら、多くの異なる対象物が同時に示されるため、単純なシノプシス ビデオであっても調べるのは厄介であろう。
【発明の概要】
【００１４】
発明の要旨
本発明の第一の態様に従えば、ソースビデオからシノプシス ビデオを生成するための、コンピュータで実施される方法が提供され、当該方法は、
１つ以上の定義された制約に従って、少なくとも３つの異なるソース対象物を選択することを有し、各ソース対象物は、ソースビデオの少なくとも３つの異なるフレームからのイメージポイント（image points）からなる連結されたサブセットであり、
各選択されたソース対象物から、１つ以上のシノプシス対象物をサンプリングすることを有し、該サンプリングは、特定の期間から抽出されたイメージポイントを用いた時間的サンプリングによって行い、
各シノプシス対象物に対して、シノプシス ビデオ中での表示を開始するためのそれぞれの時間を決定することを有し、かつ、
前記のそれぞれの時間において、選択されたシノプシス対象物またはそれらから抽出された対象物を表示することによって、シノプシス ビデオを表示することを有し、
それにより、シノプシス ビデオ中には、ソースビデオ中の異なるそれぞれの時間から各々抽出された少なくとも３つのポイントが、同時に表示されるようになっている。
【００１５】
本発明の第二の態様に従えば、ソースビデオからシノプシス ビデオを生成するためのシステム（１０）が提供され、当該システムは、
ソース対象物選択器（１８）を有し、該ソース対象物選択器は、ソースビデオ中の対象物を格納する対象物メモリ（１６）に結合されるように構成され、１つ以上の定義された制約に従って少なくとも３つの異なるソース対象物を選択するためのものであって、各ソース対象物は、ソースビデオの少なくとも３つの異なるフレームからのイメージポイントによる連結されたサブセットであり、
シノプシス対象物サンプラー（２０）を有し、該シノプシス対象物サンプラーは、ソース対象物選択器（１８）に結合され、特定の期間から抽出されたイメージポイントを用いた時間的なサンプリングによって、各選択されたソース対象物から、１つ以上のシノプシス対象物をサンプリングするためのものであり、
時間選択ユニット（２３）を有し、該時間選択ユニットは、シノプシス対象物サンプラー（２０）に結合され、各シノプシス対象物について、シノプシス ビデオ中にその表示を開始するためのそれぞれの時間を決定するためのものであり、
ステッチング（つなぎ合わせ）ユニット（２６）を有し、該ステッチングユニットは、時間選択ユニット（２３）に結合され、選択されたシノプシス対象物を、または、それらのそれぞれの時間においてそれらから抽出された対象物をステッチングし、連続的なシノプシス ビデオフレームを生成するためのものであり、それにより、該シノプシス ビデオフレームでは、ソースビデオにおける各々異なるそれぞれの時間から抽出された少なくとも３つのポイントが、同時に表示されるようになっており、かつ、
シノプシスフレームメモリ（２７）を有し、該シノプシスフレームメモリは、ステッチングユニット（２６）に結合され、該シノプシス ビデオフレームを格納するためのものである。
【００１６】
本発明によって開示されるビデオ シノプシスは、時間的にコンパクトなビデオの表現であり、それは、ビデオの閲覧および検索を可能とし、かつ、選択された特徴が分離されることおよび特定の時間的区間での時間的な進行が表示されることを可能とするようにして、異なる特徴の索引付けを可能とする。本発明の一部の実施形態によれば、ビデオ シノプシスに基づく階層的なビデオ索引付けが採用され、そこでは、索引付けは、所望の対象物または活動のクラスを最初に選択し、そしてその後にのみ、個々の対象物または活動を選択することに基づく。この手順は、マルチレベルの階層的な索引付けが可能となるように、繰り返されても良い。
【００１７】
本発明に関係するビデオ シノプシスの一般的なタイプの例は、図１に示した空間・時間ボリュームに関連して、[25]に記載されている。該ビデオは、地面を歩く人間で始まり、そして無活動（inactivity）のピリオド（期間）の後、鳥が空を飛んでいる。無活動のフレームは、殆どのビデオ抽象化の方法で抜き落とされる。ビデオ シノプシスは、実質的によりコンパクトであり、人間と鳥とが同時に行動をとる。これは、それらの空間的位置において他の活動が生じていないときに、イベントを元々の時間的区間から他の時間的区間へシフトさせることにより、イメージ領域の使用を最適なものにする。そのような操作によって、イベントの時間的な一貫性が緩和される。同様の技術が本発明によって採用され得る程度までは、それらはここでは繰り返さない。読者は、完全な説明のためには、ＷＯ2007/057893を参照すべきである。簡潔さのため、および、ある側面では、ＷＯ2007/057893の改良と見ることもできる本発明を分かり難くしないように、本発明に関係する特徴のみを詳細に説明する。
【００１８】
ウェブカメラおよび監視カメラによって得られた（obtain）ような限りの無い（infinite）ビデオに対してこの原理を適用することには、多くの更なる挑戦が伴う：
・無限の記憶装置はないため、限りの無いビデオが要約される場合には、イベントを「忘れる（forget）」必要がある。
・背景の様子は、長いビデオではかなり変動する（例、昼から夜へ）。これらの変化は、シノプシスの背景を生成するとき、および、背景に対象物を挿入するときに対処されなければならない。
・異なる時間からの活動が、同時にかつ別の時間からの背景においてさえ現れることができるため、それら全てをステッチング（stitching、つなぎ合わせ）して出力ビデオとするときには、特別注意されなければならない。
・データの量が非常に大きいにも関わらず、ユーザーのクエリに対する迅速な応答が必要とされる。
【００１９】
視聴者が、ライブのビデオの流れに加えて、終わりのないビデオの要約を見ることを可能とすることにより、ビデオ シノプシスは、監視カメラおよびウェブカメラをより有用にすることができる。これを可能とするために、シノプシスのサーバーは、ライブのビデオ放送を見ることができ、興味を引くイベントについてビデオを分析することができ、かつ対象物ベースのビデオの説明を記録することができる。この説明は、各ウェブカメラに対して、興味を引く対象物、それらの時間的長さ、場所、およびそれらの外観のリストを挙げる。
【００２０】
当該システムによって回答され得るクエリは、「私は、前の１時間の間に記録したこのウェブカメラからのビデオ シノプシスを１分で観たい」、または、「私は、先週のシノプシスを５分で観たい」などと似たものであってよい。そのようなクエリに応じて、最も興味を引くイベント（「チューブ」）が所望のピリオドから集められ、かつ所望の長さのシノプシス ビデオに組立てられる。該シノプシス ビデオは、各対象物がその元々の時間へのポインタを含むため、元々のビデオ中の索引（インデックス）である。
【００２１】
ウェブカム（webcam、ウェブカメラ）のビデオは終わりがなく、また対象物の個数は制限されない一方で、各ウェブカムのために利用可能なデータ記憶装置は限られたものであり得る。有限の対象物の待ち行列（queue、キュー）を保持するために、我々は、スペースが使い尽くされたときには、この待ち行列から対象物を削除するための手順を提案する。待ち行列からの対象物の削除は、最終的な最適化で調べられる対象物がより少なくなるように、シノプシスに含めるための対象物の選択のときに行われたのと同様の重要性の基準に従って行われるべきである。
【００２２】
本発明および添付の特許請求の範囲の内容において、用語「ビデオ」は、後処理を受け入れるコンピュータイメージファイルとしてアクセス可能であり、かつ、あらゆる種類の動画ファイル（例、デジタル、アナログ）を含みさえすれば、その最も一般的な用語における「動画（movie）」と同義である。カメラは、固定された位置にあることが好ましく、それによって意味されるのは、回転およびズームができるが、これまで提案された技術においてなされるような並進運動には供されない。本発明と関係するシーンは、少なくとも一部の時間において動的（dynamic）である。
【００２３】
本発明を説明するために、我々が「空間・時間ボリューム」と呼ぶ、シノプシス ビデオを生成するための構成物が使用される。空間・時間ボリュームは、時間軸に沿った全てのフレームを連続的にスタックすることにより、イメージの入力列から構成され得る。
しかしながら、現実の実施に関する限り、例えば動的なソースのシーンの２Ｄフレームを実際に時間的にスタックすることによって、空間・時間ボリュームを実際に構成する必要はないことを理解すべきである。より典型的には、ソースのフレームは、目的とするフレームを構成するために個々に処理されるが、概念的な構成物というよりむしろ、物理的な構成物であるかのように空間時間ボリュームに言及することが理解を助けるであろう。
【００２４】
図面の簡単な説明
本発明を理解するためおよび実際にどのように実施され得るかを見るために、添付の図面を参照して、非限定的な例のみによって、実施形態をこれより説明する。
【図面の簡単な説明】
【００２５】
【図１】図１は、時間的に離れた特徴（features）を同時に映すことによって、コンパクトなビデオ シノプシスを生成するための先行技術のアプローチを示す、絵的に表現したものである。
【図２】図２ａから２ｄは、シュトゥットガルト空港での異なる時点における監視カメラからの背景イメージを示す。
【図３】図３ａから３ｄは、図２aから２dからの対応する背景上で「平坦化（flattened）」されて示された４つの抽出されたチューブを示す。
【図４】図４ａおよび４ｂは、「ビリヤード」のシーンからの２つの抽出されたチューブを示す。
【図５】図５ａおよび５ｂは、図２に示した空港のシーンにおける活動の空間的な分布を示す。
【図６】図６は、動く対象物の個数によって測られた、図２に示した空港のシーンにおける活動の時間的な分布をグラフで示す。
【図７】図７は、本発明の実施形態に従った、シノプシスベースの階層的なビデオの索引付けおよびサーチの構造を示すブロックダイヤグラムである。
【図８】図８は、図１２に示した駐車場の監視ビデオに現れた対象物の集団化の結果を示す。
【図９】図９は、異なるクラスターの代表が同時に提示されている図１３に示された駐車場のビデオの索引付けの階層における「トップレベルのシノプシス」からのフレームを示す。
【図１０】図１０ａおよび１０ｂは、シュトゥットガルト空港で２４時間にわたって記録されたビデオからのシノプシスフレームを示す。
【図１１】図１１は、ビリヤードクラブにおいて９時間にわたって記録されたビデオから取られた３つのフレームから生成されたシノプシスのフレームを示す。
【図１２】図１２ａおよび１２ｂは、サンクト・ペテルスブルグにおいて夜通し記録されたビデオから生成されたシノプシスのフレームを示す。
【図１３】図１３ａおよび１３ｂは、静かな駐車場で５時間にわたって撮られたウェブカメラから生成されたシノプシスのフレームを示す。
【図１４】図１４は、本発明に従ったシステムの主な機能を示すフローダイヤグラムである。
【図１５】図１５は、本発明に従って実行される（carried）主要な操作を示すフローダイヤグラムである。
【発明を実施するための形態】
【００２６】
図面において代表的なフレームとして示したようなビデオ シノプシスの例は、当然ながら、最も良くは、ビデオで観られる。例は、http://www.vision.huji.ac.il/video-synopsis/でアクセスできる。
【００２７】
実施形態の詳細な説明
活動チューブの計算（computing）
対象物が現れるフレームのサブセットを選択することによって、各対象物から、セグメントが作られる。そのようなセグメントは、異なる時間的区間（タイム インターバル）を表現することができ、オプションとしては、互いに異なるサンプリングレートで撮られていても良い。
【００２８】
終わりのないビデオの有用なシノプシスを生成するためのそのような技術を適用するために、興味を引く対象物と活動（activities）（チューブ（tubes））が特定されなければならない。多くの場合、興味の目安（indication）は単純であり：動く対象物が興味を引くということである。我々は、多くの例で、興味の目安として対象物の動きを使用するが、例外を留意しなければならない。木の葉または空の雲のように、いくつかの動きは、殆ど重要性を持たないこともある。シーンにおける人間または他の大きな動物は、それらが動いていなくても重要であり得る。これらの例外を我々は扱わないが、対象物の認識（例、人間の検出[14, 17]）、動的テクスチャ（dynamic texture）[5]、または、普通でない活動の検出[31]を組み込むことができる。我々は、異なる対象物のクラスに対して優先権を与える、ビデオ シノプシスの単純な例を与える。
【００２９】
背景の構築
動いている前景の対象物のセグメント化を可能とするために、我々は、背景の構築から始める。短いビデオクリップでは、背景の外観は変化せず、クリップ全体にわたる時間的な平均を用いることによってそれを構築することができる。監視カメラの場合、背景の外観は、明暗の変化、背景対象物の変化などによって時間と共に変化する。この場合、各時点のための背景は、各フレームの前後数分間にわたる時間的な平均を使用することによって計算することができる。我々は通常、４分間の平均を使用する。より短い時間的ウィンドウ（temporal window）を使うときでさえ、背景を構築するための他の方法が可能であるが[3, 9]、我々は効率性のために平均を使用した。
【００３０】
図２ａから２ｄは、シュトゥットガルト空港での監視カメラからの背景イメージを示している。図２ａおよび２ｂは、昼の光のイメージを示し、一方、図２ｃおよび２ｄは、夜におけるものである。駐車された車および停められた飛行機は、背景の一部となる。
【００３１】
我々は、[22]の単純化を使用して、動的な対象物を表現する空間・時間チューブを計算した。これは、背景除去（background subtraction）を、前景対象物の滑らかなセグメント化を得るための最小カット（mincut）と組み合わせることによって行われる。[22]におけるように、背景の勾配と一致するイメージの勾配は、動きの境界と関係する可能性が低いため、弱められる。得られる「チューブ」は、３Ｄの空間・時間ボリューム中の結合されたコンポーネントであり、それらの生成を以下に簡単に説明する。
【００３２】
Ｂを現在の背景イメージとし、Ｉを処理される現在のイメージとする。ＶをＩにおける全てのピクセルの集合とし、ＮをＩにおける隣接する全てのピクセルペアの集合とする。ラベル付け関数（labeling function）ｆは、イメージ中の各ピクセルｒを、前景（ｆｒ＝１）または背景（ｆｒ＝０）としてラベル付けする。望ましいラベル付けｆは、通常、ギッブスエネルギーを最小化する[2]：
【００３３】
【数１】
2010518673.tif 000003
【００３４】
上式中、E1(fr)は１変数の色の項であり、E2(fr,fs)は隣接するピクセルｒとｓとの間のペアワイズのコントラストの項であり、かつλはユーザー定義の重みである。
【００３５】
ペアワイズのコントラストの項として、我々は[22]で示唆された式を使用した：
【００３６】
【数２】
2010518673.tif 000004
【００３７】
上式中、
2010518673.tif 000005
は、重みファクターであり（＜・＞は、イメージサンプルにわたっての期待値である）、drs は、背景の勾配によって弱められたイメージの勾配であって、次式によって与えられる。
【００３８】
【数３】
2010518673.tif 000006
【００３９】
この式において、zrs は前景と背景との間の相違を評価し：
【００４０】
【数４】
2010518673.tif 000007
【００４１】
かつ、Kおよびσzは、[22]によって示唆されたように、それぞれ５および１０に設定されるパラメータである。
【００４２】
１変数の色の項に関して、
2010518673.tif 000008
を、イメージＩと現在の背景Ｂとの間の色の差異とする。ピクセルｒについての前景（１）および背景（０）のコスト（costs）を次のように設定する：
【００４３】
【数５】
2010518673.tif 000009
【００４４】
上式中、k1 およびk2 はユーザー定義の閾値である）に設定する。経験的に、k1 ＝３０／２５５、k2 ＝６０／２５５が、我々の実施例ではよく機能した。
【００４５】
我々は、無限の重みを持った低い閾値を使用しない。それは、我々のアルゴリズムの後のステージでは、誤って前景として同定されたピクセルを、ロバストに（robustly、強力に）処理することができるからである。同様の理由から、空間・時間ボリューム中の全ての前景のピクセルのマスクを作成し、３Ｄの形態的な膨張をこのマスクに適用する。結果として、各対象物は、背景からのいくつかのピクセルによって囲まれる。このことが、ステッチングアルゴリズムによって後に使われることになる。
【００４６】
最終的に、３Ｄのマスクは、「活動チューブ（activity tubes）」として示される結合されたコンポーネントにグループ化される。図３ａから３ｄは、図２からの対応する背景上で「平坦化」して示された４つの抽出されたチューブを示している。左のチューブは、地上の乗り物に対応し、一方、右のチューブは、後ろの滑走路上の飛行機に対応する。図４ａおよび４ｂは、時間的に離れた多数の競技者が一つのフレーム中に表現されるようにして、「ビリヤード」のシーンからの２つの抽出されたチューブを使用して生成されたシノプシスフレームを示す。
【００４７】
各チューブｂは、その特性関数である次式によって表わされる。
【００４８】
【数６】
2010518673.tif 000010
【００４９】
上式中、Ｂ(x,y,t)は、背景イメージ中のピクセルであり、Ｉ(x,y,t)は、入力イメージ中の各ピクセルであり、かつ、ｔb は、この対象物が存在する時間的区間である。
【００５０】
動く対象物のセグメント化のための他の方法が可能である。例えば、２値のセグメント化では、イメージ中の全ての要素は、対象物に属するとして、または、対象物に属さないとして分類され得る。セグメント化はまた、ファジーであってもよく、これは、イメージ中の各要素に対して対象物におけるメンバーシップのグレードを付与する。好適なアプローチは、[32, 33, 34, 35]に記載されている。ファジーでの結合の概念は、[33]に説明されている。ファジーのセグメント化は、時に、ファジーマッティング（Fuzzy matting）と呼ばれ[35]、異なる背景の対象物の挿入のために、グラフィックスにおいて広く使われている[35]。我々の研究では、全ての対象物を２値として扱う。しかしながら、ファジーの対象物への拡張は単純なものである。例えば、コスト関数（cost functions）の全ての要素を、関連する要素のファジーのメンバーシップ値で乗じればよい。また、ファジーの対象物がイメージ中に挿入される場合、メンバーシップ値を「アルファ マッティング（alpha matting）」で使用して、透明効果を可能とすることができる。
【００５１】
チューブ間のエネルギー
ここで我々は、チューブ間の相互作用のエネルギーを定義する。このエネルギーは、後に最適化ステージで使われて、対象物間の不一致およびオーバーラップを回避しながら、最大の活動を有するシノプシスを生成することになる。Ｂを全ての活動チューブの集合とする。各チューブbは、元となるビデオストリーム中の有限の時間セグメント
2010518673.tif 000011
にわたって定義される。
【００５２】
シノプシス ビデオは、対象物ｂを、入力ビデオ中の元々の時間から、ビデオ シノプシスにおける時間セグメント
2010518673.tif 000012
へ時間的にシフトさせる時間的なマッピングＭに基づいて生成される。
2010518673.tif 000013
はシノプシスへのチューブｂの時間的シフトを示し、ｂが出力シノプシスにマッピングされない場合には、
2010518673.tif 000014
である。
我々は、次式のエネルギー関数を最小化するものとして、最適なシノプシス ビデオを定義する：
【００５３】
【数７】
2010518673.tif 000015
【００５４】
上式中、Ea は活動コスト（activity cost）であり、Et は時間的整合性コスト（temporal consistency cost）であり、かつEc は不一致コスト（collision cost）であり、全て以下で定義される。
重みαおよびβは、特定のクエリに対するそれらの総体的な重要度に応じて、ユーザーによって設定される。例えば、不一致コストの重みを減少させることにより、対象物がオーバーラップし得る、より高密度のビデオが生じる。この重みを増加させることにより、対象物がオーバーラップせず、現れる活動がより少ない、より希薄なビデオが生じる。βを変化させることによって得られる異なるシノプシスの例を、図１０ｂに与える。
【００５５】
活動チューブの抽出後、ピクセルベースのコストは、対象物ベースのコストで置き換えられ得る。具体的には、[25]で論じられたような先行技術のアプローチと関連するステッチングコストが、式（７）における不一致コスト（以下で説明する）によって置き換えられる。このコストは、たとえ外観が似ていたとしても（例、２人の人間）、２つの異なる対象物のステッチングについてペナルティを課す。加えて「時間的整合性（Temporal Consistency）」コストが定義され、対象物（またはチューブ）間の時間的関係の違反についてペナルティを課す。そのようなシノプシスの特徴は、ピクセルベースのコストの観点では、表現することが難しい。
【００５６】
活動コスト
活動コストは、最大の活動を有するシノプシス映像を優位に置く。これは、シノプシス中で妥当な時間にマッピングされていない対象物についてペナルティを課す。あるチューブがシノプシスから除外される場合、即ち、
2010518673.tif 000016
である場合、次式となる。
【００５７】
【数８】
2010518673.tif 000017
【００５８】
上式中、χb(x,y,t)は、式（６）で定義される特性関数である。
各チューブｂについて、そのマッピング
2010518673.tif 000018
が最終的なシノプシスに部分的に含められ、我々は、式（８）に似た活動コストを定義するが、シノプシス中に入れられなかったピクセルのみが活動コストに加えられる。
【００５９】
不一致コスト
あらゆる２つの「シフトされた」チューブ、および、それらの間のあらゆる相対的な時間シフトに対して、我々は、それらの活動の指標（measures）によって重み付けされた空間的・時間的オーバーラップのボリュームとして、不一致コストを定義する：
【００６０】
【数９】
2010518673.tif 000019
【００６１】
上式中、
2010518673.tif 000020
は、シノプシス ビデオにおけるｂおよびｂ’の時間的共通部分である。この表現は、背景に似た色であるが、形態的な膨張処理において活動チューブに加えられたピクセルに対して低いペナルティを与えることになる。不一致コストEc の重みを変化させることにより、図１０ｂに示すように、シノプシス ビデオにおける対象物の密度が変化する。
【００６２】
時間的整合性コスト
時間的整合性コストは、イベントの時間的順序の保存に対して付勢（バイアス）を加える。時間的順序の保存は、強い相互作用を有するチューブに対してより重要である。例えば、互いに話をしている２人の人間の相対的な時間を保つこと、あるいは論理的な関係のある２つのイベントの時間的順序を保つことが好ましい。しかし、そのような相互作用を検出することは非常に難しい。代わりに、チューブの各ペアの間の相互作用ｄ（ｂ，ｂ’）の量が、後述のように、それらの相対的な空間的・時間的距離について見積もられる：
【００６３】
【数１０】
2010518673.tif 000021
【００６４】
上式中、ｄ（ｂ,ｂ’,ｔ）は、フレームｔにおけるｂおよびｂ’からの最も近いアクティブなピクセルのペアの間のユークリッド距離であり、σspace はチューブ間の空間的相互作用の範囲を決定する。
【００６５】
チューブｂおよびｂ’がシノプシス ビデオにおいて共通の時間を共有せず、かつ、ｂがｂ’よりも前の時間にマッピングされているとすれば、それらの相互作用は、時間と共に指数関数的に減少し、次のようになる：
【００６６】
【数１１】
2010518673.tif 000022
【００６７】
上式中、σtime は、イベントがまだ時間的な相互作用を有していると考えられる時間の範囲を定義するパラメータである。
【００６８】
時間的整合性コストは、対象物間の時間的関係が破られた場合にペナルティを課すことによって、それらの関係を維持することへの優先を生成する：
【００６９】
【数１２】
2010518673.tif 000023
【００７０】
上式中、Ｃは時間的整合性を保存しないイベントに対する定数のペナルティである。
【００７１】
エネルギーの最小化
式（７）および（１５）における大域的エネルギー関数は、単一チューブまたはチューブのペアで定義されたエネルギー項の和として書かれるため、Belief Propagation [23]、または、Graph Cuts [10]などの種々のＭＲＦベースの技術によって最小化され得る。
我々の実施では、より単純なシミュレーテッド・アニーリング法（simulated annealing method）[9]を使用し、これは良好な結果を与えた。シミュレーテッド・アニーリングは、チューブがシノプシス ビデオにおいて全く使用されない特殊なケースを含む可能なあらゆる時間的なマッピングＭの空間において適用された。
【００７２】
各状態は、シノプシスに含められるチューブのサブセットを記述し、隣り合う状態は、単一の活動チューブが削除されるか、あるいは、シノプシスへのそのマッピングが変化した状態として定義される。初期状態として、我々は、全てのチューブがシノプシス映像の開始にシフトされた状態を使用した。また、計算を加速するために、チューブの時間的シフトを、１０フレームのジャンプ内に制限することが可能である。
【００７３】
終わりのないビデオのシノプシス
上述したように、何百万ものウェブカメラおよび監視カメラが世界中をカバーし、１日２４時間、それらの視界を記録している。これらのカメラを利用するに当たっての問題の一つは、それらが未編集の未加工のデータを供給するということである。例えば、２時間の長編映画は、通常、数百時間、または、数千時間もの未加工のビデオの撮影から作られる。編集なしでは、殆どのウェブカメラデータは適切でない。また、時差のため、他の大陸にあるカメラを見るのに都合がよいのは、無活動の時間の間だけかもしれない。
【００７４】
本発明の重要な特徴は、視聴者が、カメラによって提供される生のビデオストリームに加えて、終わりのないビデオの要約を視聴することを可能とすることにより、ウェブカメラのリソースをより有用にすることである。ユーザーは、前の週の間に記録した全てのコンテンツのシノプシスを５分で観ることを望むかもしれない。これを可能とするために、我々は、ＷＯ2007/057893に記載されたような対象物ベースのシノプシスに基づいたものであり得るが、終わりのないビデオの処理を可能とする更なるコンポーネントを有するシステムを説明する。
【００７５】
このシステムでは、サーバーは、ライブのビデオ映像を視聴すること、興味を引くイベントに関してビデオを解析すること、および、ビデオの対象物ベースの説明を記録することができる。この説明は、各カメラについて、興味を引く対象物、その時間的長さ、場所、および、それらの外観（appearance）をリストする。
【００７６】
終わりのないビデオ シノプシスのための、２つのフェーズ（two phase、２局面）の処理を提案する：
１）ビデオキャプチャー中のオンラインのフェーズ。このフェーズは、リアルタイムで行われる。
・対象物（チューブ）の検出およびセグメント化
・検出した対象物の、対象物待ち行列への挿入
・スペースの限界に達したときの、対象物待ち行列からの対象物の削除
２）ユーザーのクエリに応じたシノプシスを構築する応答フェーズ。このフェーズは、興味を引く期間における活動の量に応じて、数分間かかることもあり得る。このフェーズは、つぎの事を含む：
・変化する背景のタイムラプスビデオの構築。背景の変化は、通常、昼と夜の違いによって引き起こされるが、動きを始める（停止する）対象物の結果でもあり得る。
・シノプシス ビデオに含められるチューブの選択およびこれらのチューブの視覚的に訴える（visually appealing）時間的構成の計算。
・コヒーレント（coherent）ビデオへの、チューブおよび背景のステッチング。このアクションは、異なる時間からの活動が、同時にそしてまた別の時間から背景上に現れ得ることを考慮に入れなければならない。
【００７７】
前処理−動かないフレームの除去
多くの監視カメラおよびウェブカメラは、長時間にわたって活動を示さないシーンを撮像する。記憶容量の効率のために、そのような期間に対応するフレームは、通例、オンラインフェーズの間に除去される。残りのフレームの元々の時間は、各フレームと共に記録される。一つの実施では、フレームは、２つの基準に従って記録された：（１）シーンにおける大域的な変化。これは、入ってきたフレームと最後の保存されたフレームとの間の２乗差の和（sum of squared difference）（ＳＳＤ）によって測られる。この基準は、全フレームでの段階的な明るさの変化によって表現される明暗の変化を追跡する。（２）動く対象物の存在。これは、小ウインドウ内の最大のＳＳＤによって測られる。
【００７８】
非常に短い時間的長さ（例、１秒未満）で動く対象物は重要でないと仮定することにより、ビデオの活動は、数フレームにおいて一度だけで測ることができる。
【００７９】
対象物待ち行列（The Object Queue、対象物 キュー）
終わりのないビデオの処理における主要な困難の一つは、新たな対象物が出てきたときに、古い対象物を「忘れる（forget）」スキームの開発である。ユーザーは、全時間からの対象物を含み得る長い時間的期間の要約を得ることを望むこともあり得るため、最も古い活動を破棄するという安直なスキームは良くない。その代わりに、我々は、各対象物の、あり得る未来のクエリに対する重要性を見積もり、それに従って対象物を破棄することを目的とする代替的なスキームを提案する。
【００８０】
空間・時間ボリューム中でチューブとして表現される全ての検出された対象物は、ユーザーのクエリを待つ待ち行列に格納される。対象物が待ち行列に挿入されたとき、シノプシス ビデオの将来の構築を加速するために、その活動コスト（式（８））が計算される。ウェブカメラによって生成されるビデオは終わりがないため、ある時点において、割り当てられたスペースが使い尽くされ、対象物が待ち行列から削除されなければならなくなる可能性がある。
【００８１】
待ち行列から対象物（チューブ）を削除するとき、我々は、最終的なシノプシスに含められる可能性が最も低い対象物を削除する方を好ましいとする。我々の実施例では、効率的に計算され得る３つの単純な基準を使用した：「重要度」（活動）、「不一致の潜在性」、および、「エイジ（age）」である。しかし、例えば、特定の外観または活動が興味を引くものであるときには、他のオプションも可能である。
【００８２】
対象物の重要度のあり得る指標（measure）は、式（８）に定義されるような特性関数の和である。
【００８３】
ユーザーのクエリを受け取る前には、不一致コストは計算され得ないため、チューブの不一致コストの見積もりは、シーンにおける空間的な活動の分布を使用して行われる。この空間的な活動は、各空間的位置における全ての対象物のアクティブなピクセルの和であって、和が１となるように正規化されたイメージによって表される。同様の空間的な活動の分布が各個別の対象物について計算される（このときには、正規化されない）。これらの２つの活動の分布の間の相関が、この対象物についての「潜在的な不一致（potential collision）」のコストとして使用される。
図５ａおよび５ｂは、図２に示した空港のシーンにおける活動の空間的分布を示しており、強度は活動の値のログ（log）である。図５ａは、単一チューブの活動の分布を示し、図５ｂは、全チューブにわたる平均を示している。予期されるように、最も高い活動は、車線上および滑走路上である。チューブの潜在的な不一致は、より高い活動を有する領域でより高い。
【００８４】
シノプシスにおける対象物の所望の分布を考慮に入れた、待ち行列からの古い対象物の削除を扱ういくつかの可能なアプローチが存在する。例えば、ユーザーは、より新しいイベントに焦点を合わせることに興味を持つが、重要な場合には古いイベントについての何らかの表現を残しておくことに興味が持つことがあり得る。あるいは、シノプシスは、あらゆる時間的区間の均一な表現を有しなければならない。例えば、２４時間のシノプシスにおいて、ユーザーは、妥当であれば、ありとあらゆる時間からの対象物を見ることに興味を持つかもしれない。
【００８５】
第一のアプローチでは、我々は、待ち行列における対象物の密度が、対象物のエイジと共に指数関数的に減少すると想定することができる。例えば、離散的な時間的区間にエイジの軸を分割すれば、ｔの区間での対象物の個数Ｎt は、次式のように比例するはずである
【００８６】
【数１３】
2010518673.tif 000024
【００８７】
上式中、σは減衰係数であり、Ｋは待ち行列における対象物の総数を制御するために決定される。対象物が待ち行列から削除されるべきときには、各時間的区間ｔにおける対象物の個数がＮt に対して比較される。母集団（population、ポピュレーション）がＮt を越える時間的区間ｔからの対象物のみが、活動コストおよび潜在的な不一致を用いて評価されることになる。最小の活動および最大の不一致を有する対象物が削除されることになる。
【００８８】
図６には、待ち行列中に到達した対象物の時間的な分布の例が示され、これは、図２の空港のシーンにおける２９時間にわたる動く対象物の個数によって測った、活動の時間的な分布をグラフで表している。このピリオドの間に、１９２０の対象物が存在する。待ち行列における対象物の指数関数的な減衰は、減衰する指数関数を乗じて到達する分布に比例するエイジ分布を生じることになる。
【００８９】
シノプシスの生成
対象物待ち行列は、「このカメラの放送の過去の日の期間の１分間のシノプシスがほしい」などのクエリを通じてアクセスされ得る。入力ビデオからの所望のピリオドおよびシノプシスの所望の長さを与えられると、４つの操作を用いてシノプシス ビデオが生成される。（i）背景ビデオの生成。（ii）背景ビデオが定義されると、各対象物に対して、およびシノプシス中の可能な各時間に対して不一致コストが計算される。（iii）エネルギー最小化ステップが、どのチューブ（空間・時間の対象物）が、どの時間に、シノプシスにおいて現れるかを決定する。（iv）選択されたチューブが、背景のタイムラプスと結合されて最終的なシノプシスを与える。これらの操作は、このセクションで説明される。対象物ベースの表現への元々のビデオの縮小により、クエリへの迅速な応答が可能となる。
【００９０】
ユーザーのクエリの後、所望の期間からの対象物のみを有する、第２の（より小さい）対象物待ち行列が生成される。迅速な最適化を可能とするために、そのより小さい待ち行列におけるあらゆる２つの対象物の間の式（９）での不一致コストが前以て計算される。
【００９１】
タイムラプスの背景
シノプシス ビデオの背景は、タイムラプスの背景ビデオであり、活動チューブをシノプシスに加える前に生成される。背景ビデオは、２つの役割を有する：（i）経時的な背景の変化（例、昼と夜の推移など）を表現しなければならない。（ii）活動チューブの背景を表現しなければならない。活動チューブの背景の表現は、例えば殆どの夜の時間を無視して、背景のビデオがアクティブなピリオドのみを覆うときに最もよく為されることになるため、これら２つの目標は相反するものである。
【００９２】
我々は、２つの時間的分布を構築することによってこの二律背反に対処する。（i）図６に示すようなビデオストリームの時間的な活動の分布Ｈa 。（ii）均一な時間的分布Ｈt 。我々は、２つの時間的分布を補間することによって第３の時間的分布
2010518673.tif 000025
（ここでλはユーザーによって与えられる重みである）を計算する。λ＝０では、背景のタイムラプスビデオは、活動にかかわらず時間的に均一となり、一方、λ＝１では、背景のタイムラプスビデオは、アクティブなピリオドからのみの背景を含むことになる。通常、０．２５＜λ＜０．５が用いられる。
【００９３】
背景フレームは、補間された時間的分布に従って、タイムラプスの背景ビデオのために選択される。この選択は、あらゆる２つの選択された背景フレーム間のヒストグラム領域が等しくなるようにして為される。アクティブな時間的長さ（time duration）からはより多くのフレームが選択され、一方、アクティブでないピリオドは完全に無視される。
【００９４】
代替的には、背景は、合成の背景によって置き換えられてもよく、そして対象物はこの合成の背景の上に置かれることになる。
【００９５】
背景との整合性（consistency）
我々は、動く対象物の正確なセグメント化を想定していないため、類似の外観を有する背景イメージへチューブをステッチングする方を好ましいとする。このチューブの、背景に対する整合性は、新たなエネルギー項Ｅb （Ｍ）を追加することによって考慮され得る。この項は、対象物をタイムラプスの背景にステッチングするコストを測る。形式的には、
2010518673.tif 000026
をマッピングされたチューブ
2010518673.tif 000027
の色の値とし、Ｂout (x,y,t)をタイムラプスの背景の色の値とする。我々は、次式のように設定する：
【００９６】
【数１４】
2010518673.tif 000028
【００９７】
上式中、
2010518673.tif 000029
はマッピングされた活動チューブ
2010518673.tif 000030
の境界線におけるピクセルの集合であり、tout は出力シノプシスの時間的長さである。このコストは、各チューブがその元々の背景からのピクセルによって囲まれていることを想定している（活動のマスクの形態的な拡張に由来する）。
【００９８】
式（１４）における背景の整合性の項は、式（７）に記載されたエネルギー関数に加えられて、次式を与える：
【００９９】
【数１５】
2010518673.tif 000031
【０１００】
上式中、α、β、γは、クエリに依存する、ユーザーによって選択される重みである。
【０１０１】
シノプシス ビデオのステッチング
異なる期間（タイム ピリオド）からのチューブのステッチングは、既存の方法（[1, 16]など）に対する挑戦を提示する。一度に全てのチューブをステッチングすることで、異なる対象物からの色が混ざる結果になり得、これは望ましくない効果である。異なる対象物間のはっきりした移り変わりを保つと同時に、対象物と背景との間でのみ継ぎ目を除去する方が良い。対象物の正確なセグメント化がこの問題を解決し得るが、正確なセグメント化は現実的でない。その代わりに、各チューブの境界が背景ピクセルからなり、それは、活動チューブを生成するときに我々が適用する形態的な拡張（morphological dilation）に起因する。
【０１０２】
[27]で提案されたαポアソンイメージブレンディング（α-Poisson Image Blending）は、対象物間のステッチングのための良好な解決策となり得るが、背景への対象物のステッチングのためにはポアソン・エディティング[15]ほどは良くない。示唆されたアプローチは、全ての対象物が（明るさの変化次第で）似た背景を有するという観察を利用するものであり、各チューブをタイムラプスの背景に対して独立にステッチングする。あらゆるブレンド方法が可能であり、そして、我々はポアソン・エディティングの改良を用いた：たとえ対象物が異なる明暗条件での背景イメージにステッチングされても（例、晩の時間の背景の上にステッチングされる日中見られた人間）、対象物の元々の外観を保つ規制を加えた。
【０１０３】
背景に貼り付けられた対象物は、ソースビデオにおける対応する対象物に図形的に同一である必要はないことにも留意すべきである。例えば、シノプシス ビデオにおける少なくとも一つの対象物は、所定の記号またはアイコンによって、対象物を空間的に歪ませるか、または、ソースビデオにおける対応する対象物を置き換えることによって形成され得る。また、対象物がシノプシス ビデオに加えられるとき、対象物のピクセル値は、必ずしも背景の値を置き換えないかもしれない。新たな値は、透明効果を作り出す、背景と対象物との平均であってもよい。
【０１０４】
Ωを、境界∂Ωを有するイメージ領域とする。ｆ、ｂを、前景対象物（チューブ）および背景（タイムラプス）のピクセルの各色とし、ｓを、Ωの内部にわたってステッチングされた対象物の未知の値とする。規制付きのポアソンブレンディングの結果は、次式で与えられる。
【０１０５】
【数１６】
2010518673.tif 000032
【０１０６】
上式中、λは規制の項の重みである。[28]では、勾配領域でのステッチングが非常に効率的になされ得ることが示された。
【０１０７】
各チューブを背景にステッチングした後、各ピクセルを、活動の指標
2010518673.tif 000033
に比例する重みで重み付けされた、ステッチングされた活動チューブ
2010518673.tif 000034
からの対応するピクセルの平均とすることによって、オーバーラップしたチューブがブレンドされる。代替的には、重み付けされた平均の代わりに、最大の活動の指標を有するピクセルを採用することにより、透明性が回避され得る。
【０１０８】
「対象物のチューブ」が結合されるとき、深さの順序を用いることを可能としてもよく、ここで、より近くのチューブがより遠くのチューブを埋める（occlude）ことになる。単純な「グラウンドプレーン（ground plane）」のヒューリスティック（発見的手法）を用いることができ、それは、鉛直方向のイメージの位置がより低い対象物が、より近くにあると仮定するものである。その他の深さの順序の方法としては[29]が挙げられる。対象物を埋めるケースの頻度は、他のコストに対する（そのようなケースを防ぐ）不一致コストの相対的な重みに依存する。
【０１０９】
索引付け
シノプシスベースの階層的なビデオの索引付けは、監視カメラの場合のように終わりのないビデオに対してさえも、ビジュアルなクエリを用いて、ビデオの内容を表現および閲覧するコンパクトかつ容易な方法を提供することを目的とする。図７は、シノプシスベースの階層的なビデオの索引付けおよびサーチの概念的構造を示す。このシステムでは、索引付けが望まれるビデオは既に選択されていることを想定している（例、「前の１時間」、「前の３６時間」など）。
【０１１０】
提案された索引（インデックス）を構築するために、先ずビデオが分析され、ビデオからアクティブな／重要な対象物が抽出されて、ビデオの対象物ベースの表現が生成される。
【０１１１】
索引付けの第２のステージでは、任意の集団化（clustering、クラスター化）方法を用いて、対象物が、類似の対象物のクラスターへと集団化される。そのような集団化を行うためのあり得る方法は、あらゆる対象物のペアの間で、何らかの類似性の指標に基づいて、親和性（類似性）マトリックスを構築することである。
【０１１２】
対象物間の親和性（類似性）
対象物間の親和性（affinity）の指標は、以下に限定されないが、対象物の空間・時間の表現の間の相関を含む種々の特徴に基づき得る。効率的な類似性の指標化を行うために、ビデオの空間・時間の表現における３Ｄチューブとして表現される対象物は、先ず、共通の座標系へと歪ませられ、また、あり得るそれらの異なる位置およびスケールを克服するために、空間的時間的な位置合わせが行われることができる。そのような歪みは、ビデオ中の対象物の空間的・時間的位置に対して、および、種々の射影変換に対して、不変である類似の指標をもたらし得るため有用であり得る。ビデオ中で類似の動きの経路を有するが位置が異なる類似の対象物は、たとえそれらの元々の外観が遠近法の効果のために異なっていても、類似と考えられる。更なる親和性の指標は、対象物の形、サイズまたは色ならびに当該技術において知られる他の多くの可能な類似性の指標であってもよい。
【０１１３】
集団化
いったん親和性マトリックスが構築されると、[30]などの集団化方法が、各対象物を対応するクラスに分類するために使用され得る。集団化処理はまた、「イレギュラーな」対象物および挙動を特定する助けとなるためにも使用され得ることに留意することが重要である。いかなるクラスにもうまくクラスター化されない対象物は、「ユニーク」または「イレギュラー」である疑いがあり得、後述するシノプシス生成のプロセスにおいて特殊なマーキングを用いて視覚化され得る。
【０１１４】
駐車場内で撮影された２４時間のビデオシークエンスから抽出された対象物に対するそのような自動的な集団化処理の例を、図８に示している。図８に表現された６つのフレームでは、６つのクラスからの対象物が示されている：（i）右へ歩いている人々；（ii）左へ歩いている人々；（iii）ビルの隣を歩いている人々；（iv）右へ動いている車；（v）左へ動いている車；（vi）駐車場に入るまたは駐車場から出る車。
【０１１５】
代替的には、確率的な集団化を用いることもでき、それによって、どの対象物がどのクラスに属するかについてはっきり決定する代わりに、各対象物および異なるクラスに対して、確率ベクトルが定義され得る。これは、階層的な索引付けのプロセスにおいて使用され得る。例えば、ある対象物が、１つより多くのクラスに十分フィットする場合には、それらのクラスに関連付けられ得る。また、異なるクラスに対して実質的に等しい確率で属する対象物に見られるような、イレギュラーな活動が検出される場合にも使用され得る。
【０１１６】
階層的なインデックス
クラスターが決定され、対象物がクラスターにグループ化されると、索引付けのための階層的なビデオ シノプシスシークエンスのコレクションが、この集団化に基づいて生成され得る（シノプシス・フロム・クラスターズ（Synopsis from Clusters）−ＳＦＣ）。
【０１１７】
可能な索引付けの階層は、最初に、ユーザーに対して「トップレベルのシノプシス」を提示し得：それは、各クラスターからの数個の代表のみを含むシノプシス ビデオである。例えば、図８に示したクラスターからは、「トップレベル」のシノプシスは、各クラスから一つの対象物を表現し得：それは、右へ動く一台の車、左へ動く一台の車、右へ歩く一人の人間、左へ歩く一人の人間、などである。そのようなシノプシスからの一つのフレームは、図９に見ることができ、図９では、異なるクラスターの代表が同時に提示されている。ユーザーは、「トップレベル」のシノプシスにおける対象物の一つを選択することにより、対象物のクラスの全体を選択することができる。この選択により、選択されたクラスター内の対象物のみを示すシノプシス ビデオがユーザーに提示されることになる。
【０１１８】
トップレベルのシノプシスは、元々のビデオにおける所望の各対象物または活動に達するためのインタラクティブな（相互作用的な）索引付けツールとして使用され得る。ユーザーが特定のクラスターまたはクラスターの集まりを選択すると、階層内の次のシノプシスが表示される。そのようなシノプシスは、それらのクラスターからのより多くの代表または対象物全てでさえもを含むことになる。この段階では、ユーザーは、所望の対象物を指定して、入力ビデオでのその元々の時間に達することができる。各クラス内に多くの対象物があり、短いシノプシスを生成するのが困難な場合、階層により多くのレベルを加え、元々の各クラスターからいくつかのサブクラスターを生成することが可能である。例えば、「右へ動く車」のクラスターを選択すると、トラックおよびセダンの２つのサブクラスターが生成され得る。この場合、サブクラスターの一つの選択は、元々の対象物の殆どを有するシノプシスを示すサーチの最終結果に達する前である必要がある。
【０１１９】
そのようなアプローチは、非常に大きなビデオ中に、非常に迅速なサーチと索引付けツールとを提供し、それは、視覚的なクエリに基づくものであり、かつ、それは、元々のビデオ中のあらゆる対象物および活動へ適度な時間内に到達することを可能にする。
【０１２０】
実施例
インターネットからキャプチャー（獲得）した数個のビデオストリームに、ビデオ シノプシスをテストした。フレーム率（frame rate）がインターネットを超えて一定でないので、また、フレームが周期的に脱落するので、時間的な近傍を用いるときには常に、フレームの個数をカウントせず、各フレームの絶対的な時間を用いる。
【０１２１】
図１０および１２は、屋外に置かれたカメラからのものであり、図１１は、一定の照明がある屋内に置かれたカメラからのものである。殆どの例では、各チューブの主な「興味（interest）」は、その中での動くピクセルの数であった。
【０１２２】
図１０ａおよび１０ｂは、ビデオ シノプシス中の対象物の密度の不一致コストの選択の効果を示している。図１０ａは、シュトゥットガルト空港で２４時間にわたって記録されたビデオの２０秒間のシノプシスからのフレームを示している。図１０ｂは、コスト関数における「不一致ペナルティ」の減小は、実質的に対象物の密度を増加させ、それにより対象物間のより多くのオーバーラップを可能とすることを示している。
図１２は、形状ベースの（形状に基づいた）選択（preferences）を示している。図１２ａでは、通常のコスト関数が用いられ、大きな対象物（動く車）の方が選ばれた。図１２ｂでは、小さい、暗い対象物の方が選ばれ、完全に異なった歩行の活動を示している。図１１は、ビリヤードクラブで９時間にわたって記録されたビデオの短いシノプシスからのフレームを示している。該シノプシスには、テーブルあたり複数の競技者がいることに注目されたい。
【０１２３】
カスタマイズされたエネルギー関数
たいていの場合、全ての対象物が興味を引く、ということはない。交通監視カメラは車にのみ興味があるかもしれず、他のアプリケーションは歩行者を好むかもしれない。対象物のフィルタリングはいくつかの場所で為され得る。対象物は待ち行列に入る前に除去され得、この場合、それを取り戻すことは決してできなくなる。代替的には、対象物はクエリの段階においてのみ除去され得る。この場合、待ち行列は全ての対象物を含むことになり、異なるクエリにより、待ち行列からは異なる対象物が抽出され得る。各アプリケーションのためにカスタマイズされたエネルギー関数を作り出すことも可能である。
【０１２４】
カスタマイゼーションの単純な例を図１２ｂに示しており、図１２ｂでは、小さく、暗い対象物のみが待ち行列から選択された。元々のシノプシスに含まれているのは殆どが車であったが、新たなシノプシスに含まれるのは殆どが歩行者である。
別の例は、図１３に見られ、図１３では、エネルギー関数は、動く対象物が止まって背景の一部となるときの「フェーズ変化（phase transition）」の要素を含んでいた。図１３ａは、静かな駐車場を観測しているウェブカメラからの５時間にわたって撮られた短いシノプシスからのフレームを示す。高いスコアがフェーズ変化（例、止まって背景となる動く対象物）に与えられた。ビデオ シノプシスに含まれるのは、駐車に関係する車が殆どである。図１３ｂは、フェーズ変化のない対象物が好まれているために通り過ぎる車および歩行者のみが示されている代替的なシノプシスを示している。
【０１２５】
シノプシスの指定
ビデオ シノプシスの時間的長さおよび質を指定するためのいくつかのスキームが存在する。
（ａ）ビデオ シノプシスの所望の時間的長さおよび対象物の不一致のペナルティをユーザーが指定するのを許す。この場合、最適化ステージは、指定された制約下でシノプシスに含められ得る活動の量を最大化することになる。
（ｂ）ビデオ シノプシスの所望の時間的長さおよびそこに含められ得る活動のパーセンテージをユーザーが指定するのを許す。最適化ステージは、指定された制約下で最小の不一致となるビデオ シノプシスを生成することになる。
（ｃ）失われる対象物の許容されるパーセンテージおよび対象物の不一致についてのペナルティをユーザーが指定するのを許す。最適化ステージは、指定された制約下でシノプシスの時間的長さを最小化することになる。
【０１２６】
我々の実験では、オプション（ａ）を実施し、ビデオ シノプシスの時間的長さは確固とした制約としてユーザーによって決定された。監視ビデオでは、殆どの対象物がシノプシスに表示されることになると想定すれば、オプション（ｂ）または（ｃ）が好まれるかもしれない。
【０１２７】
対象物ベースのスピード変化
早送りは、ビデオ要約のために使用される最も一般的なツールであり、常に全フレームに対して適用されてきた。例えば、「タイムラプス」ビデオは、短い時間に、花の成長などのような遅いプロセスを表示する。現行の方法の中には、適応性のある早送り[12, 18, 4]を示唆するものもあるが、それでもなお、全フレームの枠組みに限定されている。ビデオ シノプシスでは、各対象物は、それ自身の「早送り」を、その重要度に基づいたもの、またはその元々の速度に基づいたものにすることができる。遅い対象物は加速されるかもしれず、速い対象物は加速されないかもしれない。代替的には、速い対象物は、視るのをより容易にするために減速され得る。
【０１２８】
対象物のスピードの変化は、例えば、全ての動く対象物を均一の速度にするといった、単純な方法で行われ得る。この目的のために、遅い対象物はスピードを上げられ、速い対象物は減速されることになる。代替的には、対象物のスピードの変化は、最適化ステージの間に、対象物のスピード変化に対する何らかのペナルティを与えて決定され得る。対象物ベースのスピード変化を最適化ステージに加えることにより、最適化の複雑さを増すことを犠牲にして、シノプシス ビデオの時間的な圧縮率がさらに向上され得る。
【０１２９】
対象物のスピード変化は、何らかの選択された期間における対象物からのピクセルをサンプリングすることによって行われてもよい。選択された期間の数がチューブ中のフレームの数よりも少なければ、全体的な効果としては、対象物がスピードアップされるということである。選択された期間の数がチューブ中のフレームの数よりも大きければ、対象物は減速される。選択された期間が正確にはフレームにかからないときには、この時点でのピクセルは、選択された時間に対して時間的に最も近い隣接するフレームにおける隣接するピクセルから補間され得る。可能な任意の補間方法が使用され得る。
【０１３０】
前景・背景のフェーズ変化
フェーズ変化は、動く対象物が動かなくなり、背景と同化したとき、または、動いていない対象物が動き始めたときに生じる。例としては、駐車される車または駐車から出る車である。大抵の場合、フェーズ変化は、意義のあるイベントであり、我々は、クエリステージにおける使用のために各フェーズ変化を検出およびマークする。
【０１３１】
チューブの始まりおよび終わりに対応する背景の変化を探すことによって、フェーズ変化を見出すことができる。これらの変化は、背景の変化を説明するため、重要である。
フェーズ変化は背景の変化に対応するため、背景へのフェーズ変化のステッチングには、特別の注意が与えられなければならない。フェーズ変化が正しい時間の背景に挿入されないとき、２つの効果がシノプシス ビデオにおいて生じ得る。（i）背景対象物が理由もなく生じては消え、フリッカー効果（flickering effect）を招く。（ii）動く対象物が、それらが動くのをやめたときに、背景の一部となるよりむしろ、消失する。ビデオ シノプシスにおけるそのような効果を最小化するために、フェーズ変化を、元々の時間に対応する時間で、タイムラプスの背景に挿入しなければならない。
【０１３２】
システムハードウェア
ここで図１４を参照すると、本発明に従ったシステム１０のブロックダイヤグラムが示されており、これは、カメラ１１によって記録されたソースビデオからのシノプシス ビデオを生成するためのものである。当該システム１０は、ビデオメモリ１２を含んでおり、該メモリは、第一のソースビデオのビデオフレームのサブセットを格納するためのものであり、それらは、少なくとも一つの対象物の動きを示しており、その対象物は、各々にｘ、ｙ座標に位置する複数のピクセルを有している。前置プロセッサ（pre-processor）１３は、オンラインで、記録されたビデオを処理する。該前置プロセッサ１３は、ビデオフレームを事前位置合わせ（pre-aligning）するための位置合わせユニット（alignment unit）１４を含んでもよい。この場合、カメラ１１は、事前位置合わせされたビデオフレームをビデオメモリ１２に格納するために、位置合わせユニット１４に結合される。該位置合わせユニット１４は：
ソースビデオ中のフレーム間でのイメージモーションのパラメータを計算すること；
撮像されたシーン中の動いていない対象物がビデオ中で動かないようにして、ソースビデオ中のビデオフレームを歪ませること
によって作動し得る。
【０１３３】
前置プロセッサ１３はまた、ソース対象物検出器１５を含み、該検出器は、ソースビデオ中の対象物を検出し、かつ検出した対象物を対象物メモリ１６中の待ち行列に入れる。上記したように、対象物が待ち行列に挿入されるとき、未来におけるシノプシス ビデオの構築を加速するために、その活動コスト（式（８））が計算され、これもまた前置プロセッサ１３によって為される。前置プロセッサ１３は、終わりのないソースビデオからシノプシス ビデオを生成するときに使用されることに起因してその完全性のために示されていることを理解すべきである。本発明はまた、対象物待ち行列を操作して、定義された基準に従ってシノプシス ビデオを生成するために対象物メモリ１６に結合されるように構成される前置プロセッサ１３を有さない、縮小されたシステムも意図する。そのようなシステムは、これより説明するように、図１４における残りのコンポーネントによって実現される。
【０１３４】
即ち、ユーザーインターフェース１７は、ユーザー定義の制約が定義されるのを可能とするために、対象物メモリ１６に結合される。そのような制約は、例えば、要約されるべきソースビデオ中の時間ウィンドウを定義するために使用され得る。それはまた、シノプシス ビデオの必要とされる時間的長さを定義するためにも使用され得る。ユーザーインターフェース１７は、索引付けの目的のための対象物または対象物クラスを選択するためにも使用される。制約はまた、予め定義されてもよく、その場合、本発明の一部の実施形態はユーザーインターフェース１７を必要としないことが理解されよう。
【０１３５】
ソース対象物選択器１８は、ユーザー定義の制約またはシステムによって定義されるデフォルトの制約に従って、サブセットから少なくとも３つの異なるソース対象物を選択するために、対象物メモリ１６に接続される。異なるソース対象物のそれぞれは、ソースビデオの少なくとも３つの異なるフレームからのイメージポイントの結合されたサブセットである。
ユーザーインターフェース１７を用いてユーザーによって指定され得る定義された基準に従って対象物を集団化するために、集団化ユニット１９を任意でソース対象物選択器１８に結合してもよい。
シノプシス対象物サンプラー２０がソース対象物選択器１８、または備えられたときには集団化ユニット１９に結合され、これは、いくつかの選択されたフレームから抽出されたイメージポイントを用いた時間的な選択によって、各選択されたソース対象物から、１つ以上のシノプシス対象物をサンプリングするためのものである。「サンプラー」は、個々の対象物のスピードを変化させるために使用され得る。フレームジェネレータ２１は、クラスター選択器２２を含み、クラスター選択器２２は、選択されたクラスターのみがシノプシス ビデオに含められるのを可能とする。フレームジェネレータ２１はまた、時間選択器２３を含み、時間選択器２３は、各シノプシス対象物に対して、シノプシス ビデオにおいて表示を開始するための各々の時間を選択するためのものである。フレームジェネレータ２１は、色変換ユニット２４をさらに含み、色変換ユニット２４は、各シノプシス対象物および各フレームに対して、シノプシス対象物の表示のための各々の色変換を選択するためのものである。任意選択で、フレームジェネレータ２１は、ワーピング（warping、歪ませる）ユニット２５を含んでもよく、該ワーピングユニットは、シノプシス ビデオへのステッチングに対象物を空間的に歪ませすためのものである。本明細書の文脈および添付の特許請求の文脈では、該用語「ワーピング（warping）」は、対象物の任意の空間的編集を包含することが意図されている。上記したように、これは、アイコンなどの別の対象物によって、対象物をその全体として置き換えることを含んでもよく；あるいは、シノプシス ビデオ中にステッチングされる前に、対象物に対して、単にわずかな幾何学的調整を施すことを伴い得る。フレームジェネレータ２１中のステッチングユニット２６は、連続したシノプシス ビデオフレームを生成するために、選択された色変換されたシノプシス対象物をステッチングする。シノプシス ビデオのフレームは、後の処理のために、または、時間的にシフトされた対象物を、指定された時間および色変換で表示するディスプレイユニット２８によって表示するために、シノプシスフレームメモリ２７に格納される。
【０１３６】
システム１０は、実際には、全て当該分野で周知であるような、グラフィックカードまたはワークステーションおよび好適な周辺機器を有する好適にプログラミングされたコンピューターによって実現され得る。
【０１３７】
図１５は、本発明の実施形態に従うシステム１０によって為される主要な操作を示すフローダイヤグラムである。
【０１３８】
結論
対象物ベースのシノプシスは、短いビデオを作るために使用され得、その短いビデオは、監視カメラによって記録されるような終わりのないビデオストリームのシノプシスである。当該方法は、２つのフェーズを含む。リアルタイムで行われる入力フェーズでは、ビデオストリームが分析され、興味を引く対象物が検出されかつ背景からセグメント化される。動きに基づく対象物の興味の関数を説明したが、対象物を検出、認識、およびセグメント化するための任意の他のアプローチを、「チューブ」 − 各対象物の３Ｄの空間的・時間的表現の生成のために使用することができる。
【０１３９】
終わりのないビデオと有限の記憶装置との間のギャップを橋渡しするために、および、ユーザーのクエリに対して迅速な応答を可能とするために、待ち行列の管理が必要である。いっぱいになったときに待ち行列からどの対象物を削除すべきかを決定するためのいくつかの方法論を説明したが、他の方法論も可能である。待ち行列からの削除のために対象物のランダムな選択ですらよく機能するかもしれない。
【０１４０】
第２のフェーズは、ユーザーのクエリが与えられた後に生じる。待ち行列のサブセットが興味を引くピリオドに基づいて抽出され、最適なビデオ シノプシスを生成するために対象物のチューブが（時間的なシフトによって）並べられる。オフラインの計算を必要とするこのステージは、ユーザーに対してビデオ シノプシスを供給する。
【０１４１】
ある非常に興味深い側面は、背景の周期性に関する。昼と夜の周期は、特に、検出しやすい。単一のシノプシスによって数日がカバーされるたいていの場合、タイムラプスの背景は一日のみをカバーするかもしれず、一方、活動は全ての日にあるであろう。これは、クエリを指定するユーザーに対して与えられるオプションであるべきである。
【０１４２】
２値のセグメント化に明確に限定していない限り、「イメージポイント」への言及は、補間、またはファジーセグメント化などの非２値のセグメント化方法によって決定されるようなイメージポイントも包含することが意図されていることが理解されよう。
【０１４３】
ソースビデオがモノクロの場合、ステッチングの前に選択されたシノプシス対象物に対して適用される適当なグレイスケール変換を決定するために、色変換ユニットが使用され得ることも理解すべきである。それゆえ、添付の特許請求の文脈では、用語「色」は、RGBのみに限定されないことが意図され、モノクロでもあり得る。
【０１４４】
色またはグレイスケールの変換は、ステッチングの前に選択されたシノプシス対象物に対して適用され得る変換の一種に過ぎないことも留意すべきである。上で説明したように、背景の一貫性を保証するために、長い時間的長さにわたるソースビデオからシノプシス ビデオを生成するときにこれは特に有益である。しかし、シノプシス ビデオが、背景の色相が必要とされる時間ウィンドウの間に十分一定であるソースビデオから抽出されるときには、これはあまり重要ではないかもしれない。
【０１４５】
本発明に従うシステムは、好適にプログラミングされたコンピュータであり得ることも理解されよう。同様に、本発明は、本発明の方法を実行するためのコンピュータコンピュータによって読み込み可能なコンピュータプログラムを意図する。本発明はさらに、本発明の方法を実施するための機械によって実行可能な指示のプログラムを具体的に具現化した機械読み込み可能なメモリを意図している。
【図６】
2010518673.tif 000035
【図７】
2010518673.tif 000036
【図１】
2010518673.tif 000037
【図２】
2010518673.tif 000038
【図３】
2010518673.tif 000039
【図４】
2010518673.tif 000040
【図５】
2010518673.tif 000041
【図８】
2010518673.tif 000042
【図９】
2010518673.tif 000043
【図１０】
2010518673.tif 000044
【図１１】
2010518673.tif 000045
【図１２】
2010518673.tif 000046
【図１３】
2010518673.tif 000047
【図１４】
2010518673.tif 000048
【図１５】
2010518673.tif 000049
【国際調査報告】
2010518673.tif 000050
2010518673.tif 000051
2010518673.tif 000052