(57)【要約】【課題】複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステム及び方法を提供する。【解決手段】複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステムは、複数のビューに対応する複数のフレームのうちの少なくとも１つのフレームの多重表現を、該多重表現ごとに異なる参照フレームを使用して符号化するように構成されるエンコーダを備える。本システムは、複数のフレーム及び多重表現を含む符号化木を作成するように構成されるコントローラも備える。本システムは、符号化木を記憶するように構成されるデータ記憶装置をさらに備える。コントローラは、データ記憶装置の記憶制約を特定すると共に、符号化木から多重表現のうちの少なくとも１つを省略して、データ記憶装置内に記憶される複数のフレームが記憶制約内に留まるようにするようにさらに構成される。【選択図】図２
2010093807.tif 000002
【特許請求の範囲】
【請求項１】
複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステムであって、
複数のビューに対応する前記複数のフレームのうちの少なくとも１つのフレームの多重表現を、前記多重表現ごとに異なる参照フレームを使用して符号化するように構成されるエンコーダであって、前記少なくとも１つのフレームの前記多重表現は共通時刻及び共通ビューに対応する、エンコーダと、
前記複数のフレーム及び前記多重表現を含む符号化木を作成するように構成されるコントローラであって、前記符号化木は、前記フレームのうちのいずれが他のフレームのための参照フレームを含むかを特定するフレーム経路を前記複数の符号化フレームごとに示し、前記コントローラは、前記多重表現のうちの少なくとも１つを、各時刻における各ビューに対応する、Ｐフレーム及びＩフレームのうちの一方として維持するようにさらに構成される、コントローラと、
前記符号化木を記憶するように構成されるデータ記憶装置であって、前記コントローラは、前記データ記憶装置の記憶制約を特定すると共に、前記多重表現のうちの少なくとも１つを前記符号化木から省略して、前記データ記憶装置内に記憶される前記複数のフレームが前記記憶制約内に留まるようにするようにさらに構成される、データ記憶装置と
を備えるシステム。
【請求項２】
前記コントローラは、クライアントが時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装すると共に、要求される可能性が最も少ないフレームを前記符号化木からまず省略して前記データ記憶装置の前記記憶制約内に留まるように、前記対話モデルに基づいて前記複数のフレームを配置するようにさらに構成される
請求項１に記載のシステム。
【請求項３】
前記コントローラは、前記多重表現をクライアントに通信することに関連付けられる送信コストを計算するようにさらに構成され、
前記複数のフレームの前記多重表現はＰフレームを含み、
前記コントローラは、前記少なくとも１つフレームの前記多重表現の前記ＰフレームをＩフレームで置き換えると共に、前記Ｉフレームを前記符号化木内の前記少なくとも１つのフレームのノードとして記憶し、それによって、前記データ記憶装置の前記記憶制約内に留まりながら、前記計算された送信コストを最小化するようにさらに構成される
請求項１に記載のシステム。
【請求項４】
前記コントローラは、第１のフレームをクライアントに通信し、前記クライアントから第２のフレームを求める要求を受信し、前記第２のフレームが前記クライアントにおいて適切に復号化されるために前記少なくとも１つのフレームの前記多重表現のうちの１つの表現が必要とされると判断し、前記クライアントにおける前記第２のフレームの適切な復号化のために、前記符号化木を通る複数の経路に沿って、前記少なくとも１つのフレームの前記多重表現のそれぞれを通信することに関連付けられる送信コストを求め、最低送信コストに関連付けられる前記少なくとも１つのフレームの前記多重表現のうちの前記１つの表現を前記クライアントに通信するようにさらに構成される
請求項１に記載のシステム。
【請求項５】
複数のフレームから成るマルチビューストリーミングビデオデータを管理する方法であって、
前記マルチビューストリーミングビデオを記憶するように構成されるデータ記憶装置の記憶制約を特定することと、
複数のビューに対応する前記複数のフレームのうちの少なくとも１つのフレームの多重表現を、前記多重表現ごとに異なる参照フレームを使用して符号化することであって、前記多重表現は共通時刻及び共通ビューに対応する、符号化することと、
前記多重表現のうちの少なくとも１つを省略することによって、前記データ記憶装置の前記記憶制約を考慮して、前記複数のフレーム及び前記多重表現を含む符号化木を作成することであって、前記符号化木は、前記多重表現のうちの少なくとも１つを、各時刻における各ビューに対応する、Ｐフレーム及びＩフレームのうちの一方として維持する、作成することと、
前記符号化木を前記データ記憶装置内に記憶することと
を含む方法。
【請求項６】
前記方法は、クライアントが時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装することをさらに含み、
前記符号化木を作成することは、要求される可能性が最も少ないフレームを前記符号化木からまず省略して前記データ記憶装置の前記記憶制約内に留まるように、前記対話モデルに基づいて前記複数のフレームを配置することをさらに含む
請求項５に記載の方法。
【請求項７】
前記複数のフレームの前記多重表現はＰフレームを含み、前記方法は、
前記多重表現をクライアントに通信することに関連付けられる送信コストを計算することと、
前記少なくとも１つのフレームの前記多重表現の前記ＰフレームをＩフレームで置き換えることと、
前記Ｉフレームを前記符号化木内の前記少なくとも１つのフレームのノードとして記憶することであって、それによって、前記データ記憶装置の前記記憶制約内に留まりながら、前記計算された送信コストを最小化する、記憶することと
をさらに含む請求項５に方法。
【請求項８】
第１のフレームをクライアントに通信することと、
前記クライアントから第２のフレームを求める要求を受信することと、
前記第２のフレームが前記クライアントにおいて適切に復号化されるために前記少なくとも１つのフレームの前記多重表現のうちの１つの表現が必要とされると判断することと、
前記クライアントにおける前記第２のフレームの適切な復号化のために、前記符号化木を通る複数の経路に沿って前記多重表現のそれぞれを通信することに関連付けられる送信コストを求めることと、
最低送信コストに関連付けられる前記多重表現のうちの前記１つの表現を前記クライアントに通信することと
をさらに含む請求項５に記載の方法。
【請求項９】
１つ又は複数のプログラムが組み込まれているコンピュータ可読記憶媒体であって、前記１つ又は複数のコンピュータプログラムは、複数のフレームから成るマルチビューストリーミングビデオデータを管理する方法を実装し、前記１つ又は複数のコンピュータプログラムは、
前記マルチビューストリーミングビデオを記憶するように構成される前記データ記憶装置の記憶制約を特定することと、
複数のビューに対応する前記複数のフレームのうちの少なくとも１つのフレームの多重表現を、前記複数のバージョンごとに異なる参照フレームを使用して符号化することであって、前記多重表現は共通時刻及び共通ビューに対応する、符号化することと、
前記多重表現のうちの少なくとも１つを省略することによって、前記データ記憶装置の前記記憶制約を考慮して、前記複数のフレーム及び前記多重表現を含む符号化木を作成することであって、前記符号化木は、前記多重表現のうちの少なくとも１つを、各時刻における各ビューに対応する、Ｐフレーム及びＩフレームのうちの一方として維持する、作成することと、
前記符号化木を前記データ記憶装置内に記憶することと
のためのコンピュータ可読コードを含むコンピュータ可読記憶媒体。
【請求項１０】
前記１つ又は複数のコンピュータプログラムは、
クライアントが時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装することのためのコンピュータ可読コードをさらに含み、
前記符号化木を作成することは、要求される可能性が最も少ないフレームを前記符号化木からまず省略して前記データ記憶装置の前記記憶制約内に留まるように、前記対話モデルに基づいて前記複数のフレームを配置することをさらに含む
請求項９に記載のコンピュータ可読記憶媒体。
【請求項１１】
前記１つ又は複数のコンピュータプログラムは、
前記多重表現をクライアントに通信することに関連付けられる送信コストを計算することと、
前記少なくとも１つのフレームの前記多重表現の前記ＰフレームをＩフレームで置き換えることと、
前記Ｉフレームを前記符号化木内の前記少なくとも１つのフレームのノードとして記憶することであって、それによって、前記データ記憶装置の前記記憶制約内に留まりながら、前記計算された送信コストを最小化する、記憶することと
のためのコンピュータ可読コードをさらに含む請求項９に記載のコンピュータ可読記憶媒体。
【請求項１２】
前記１つ又は複数のコンピュータプログラムは、
第１のフレームをクライアントに通信することと、
前記クライアントから第２のフレームを求める要求を受信することと、
前記第２のフレームが前記クライアントにおいて適切に復号化されるために前記少なくとも１つのフレームの前記多重表現のうちの１つの表現が必要とされると判断することと、
前記クライアントにおける前記第２のフレームの適切な復号化のために、前記符号化木を通る複数の経路に沿って、前記多重表現のそれぞれを通信することに関連付けられる送信コストを求めることと、
最低送信コストに関連付けられる前記多重表現のうちの前記１つの表現を前記クライアントに通信することと
のためのコンピュータ可読コードをさらに含む請求項９に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施の形態は、複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステム及び方法に関する。
【背景技術】
【０００２】
ビデオは通常、イントラ符号化フレーム（Ｉフレーム）及びインターフレーム又は予測フレーム（Ｐフレーム）を使用して圧縮される。
Ｉフレームは、他のフレームからの予測無しで符号化されるため参照フレームを必要としないフレームである。
Ｐフレームは、参照フレームからの予測を使用するフレームである。
Ｉフレームはまたイントラマクロブロックのみを含み、一方、Ｐフレームはイントラマクロブロック又は予測マクロブロックのいずれかを含む。
Ｐフレームは、復号化されるために何らかの他の参照フレームを先行して復号化することを必要とし、多くの場合に、符号化のためにＩフレームよりも少ないビットを必要とする。
【０００３】
１つのシーンの複数のビュー（マルチビュー）が、同時に取り込まれ、Ｉフレーム及び／又はＰフレームを使用して符号化され、そしてユーザに送られるビデオアプリケーションがますます開発されるようになってきている。
これらのタイプのビデオアプリケーションでは、ユーザは、複数のビューをリアルタイムで切り替えることができ、したがって、従来のビデオアプリケーションを用いる場合よりも高いレベルの対話性を与えられる。
マルチビュービデオ符号化（ＭＶＣ）ツールのためのアプリケーションの中には、ユーザが再生のために、これらのビュー、又は潜在的には、実際に取り込まれたビデオデータから生成される仮想ビューのサブセットのみを選択することが可能なアプリケーションもある。
【０００４】
サーバにおいて符号化されてクライアントに通信されるＩフレーム（Ｉ（ｉ，ｊ））に基づく従来の符号化木１００の概略図を図１に示す。
ここで、ｉは時間インデックスであり、ｊはビューである。
この図内に示されているように、符号化木１００はＩフレームのみに基づいて符号化され、したがってＩフレームのうちの幾つかは、差分符号化のための参照フレームを必要とすることなく、他のＩフレームと比較して異なるビューを生成することができる。
しかしながら、図１に示されている符号化木１００は大きな送信コストを必要とする。
これは、Ｉフレームは通常、上述したようにＰフレームよりも数倍大きいためである。
【０００５】
ＭＶＣにおける最近の活動のうちの多くは画像取り込み及び圧縮に重点を置いてきた。
たとえば、ＭＶＣ標準化過程は、レート歪みが最適であるように、マルチビューシーケンスにおける全てのフレームを符号化するための新たな圧縮アルゴリズムの開発に集中してきた。
したがって、ストリーミングビデオのより効率的なマルチビュー制御をクライアントに提供することはあまり考慮されてこなかった。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】MERKLE, P.他, 「Efficient Prediction Structures for Multiview Coding」, IEEE Transactions on Circuits and Systems for Video Technology, 2007年11月
【非特許文献２】FLIERL, M. 他, 「Motion and Disparity Compensated Coding for Multiview Video」, IEEE Transactions on Circuits and Systems for Video Technology, 2007年11月
【非特許文献３】「Second life: Official site of the 3D online virtual world」, , downloaded 2008年10月6日
【非特許文献４】「Warsow-A Fast Paced First Person Shooter Game」, , downloaded 2008年10月6日
【非特許文献５】「Half-Life TV」, downloaded 2008年10月6日
【非特許文献６】「Serious Games Initiative」, downloaded 2008年10月6日
【非特許文献７】CHEUNG, G. 他,「Graphics-to-video encoding for 3G mobile game viewer multicast using depth values」, IEEE international Conf. on Image Processing, 2004年10月, Abstract
【非特許文献８】CHEUNG, G. 他,「ECHO: A Community Video Streaming System with Interactive Visual Overlays」, 2008年1月
【非特許文献９】CHEUNG, G. 他,「Fast H.264 Mode Selection Using Depth Information for Distributed Game Viewing」, 2008年1月
【非特許文献１０】SCHULZRINE, H.他, Real Time Streaming Protocol (RTSP)」, 1998年4月
【非特許文献１１】CHEUNG, N. 他,「Distributed Source Coding Application to Low-Delay Free Viewpoint Switching in Multiview Compression」,2007年11月
【非特許文献１２】KARCZEWICZ, M.他,「The SP-and SI-frames design for H.264/AVC」, IEEE Transactions on Circuits and Systems for Technology, 2003年7月
【非特許文献１３】「The TML Project Web-Page and Archive」, downloaded 2008年10月6日
【非特許文献１４】「Test Squares at MERL」, ftp://ftp.merl.com/pub/avetro/mvc-testseq, downloaded 2008年10月6日
【発明の概要】
【０００７】
本発明は、複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステム及び方法を提供する。
【０００８】
当業者には、本発明の特徴は図面を参照する以下の説明から明らかとなるであろう。
【図面の簡単な説明】
【０００９】
【図１】Ｉフレームに基づく従来の符号化木の概略図である。
【図２】本発明の一実施形態による、マルチビューストリームデータコンテンツがサーバからクライアントにおいて消費されることを可能にするシステムの単純なブロック図を示す。
【図３】本発明の一実施形態による、複数のフレームから成る対話的マルチビューストリーミングビデオデータを可能にするための符号化木であって、該複数のフレームは根Ｉフレーム及び複数のＰフレームに基づいて該複数のフレームの多重表現として符号化されている、符号化木を示す。
【図４】本発明の一実施形態による、幾つかのフレームが省略又は除去されており、それによって符号化フレームの記憶空間要件が低減される符号化木を示す。
【図５】本発明の一実施形態による、幾つかのフレームが省略又は除去されており、それによって符号化フレームの記憶空間要件が低減される符号化木を示す。
【図６】本発明の一実施形態による、複数のフレームから成るマルチビューストリーミングビデオデータを管理する方法のフロー図を示す。
【図７】本発明の一実施形態による、複数のフレームから成るマルチビューストリーミングビデオデータを管理する方法のフロー図を示す。
【図８】本発明の一実施形態による、図６及び図７において示される方法を実装又は実行するように構成される計算装置のブロック図を示す。
【発明を実施するための形態】
【００１０】
単純にする目的及び例示する目的のために、本発明を、主に本発明の例示的な一実施形態を参照して説明する。
以下の説明では、本発明の完全な理解を提供するために多数の具体的な詳細を述べる。
しかしながら、当業者には、本発明をこれらの具体的な詳細に限定することなく実践することができることが明らかであろう。
他の例においては、既知の方法及び構造は、不必要に本発明を不明瞭にしないように詳細に説明していない。
【００１１】
本明細書には、複数のフレームから成るビデオデータを管理するシステム及び方法が開示される。
本明細書に開示されるシステム及び方法は、符号化フレームの記憶コストと送信コストとの間の最適なトレードオフを可能にする符号化構造を作成するように構成される。
或る点においては、トレードオフは、特定のフレームを１回よりも多く選択的に符号化し、それによって、符号化構造が、異なる参照フレームを使用して生成される、これらの選択されたフレームの多重表現を含むことによって為される場合がある。
全てのフレームではなく、フレームのうちの選択されたフレームを選択的に符号化することによって、本発明の符号化構造は、フレームの多重表現の全てが符号化されている符号化木と比較してはるかに少ない空間を必要とする。
【００１２】
符号化構造を使用して、マルチビュービデオストリーミングデータがクライアントに通信されることを可能にし、クライアントのユーザが対話的にサーバからフレームを受け取ることを可能にすることができる。
例として、符号化木を使用して、フレームの最も効率的な通信を提供する、複数のフレームを経由するルートを特定して、クライアントが所望のフレームを再構築することを可能にすることができる。
【００１３】
図２を参照すると、一実施例による、マルチビューストリーミングデータコンテンツがサーバ２０２からクライアント２２０において消費されることを可能にするシステム２００の単純なブロック図が示されている。
或る点においては、以下において本明細書に開示される方法は、本明細書において以下でより詳細に論じるように、システム２００において実施することができる。
システム２００は追加の構成要素を含むことができること、並びに、本明細書において説明される該構成要素のうちの幾つかは、システム２００の範囲から逸脱することなく除去及び／又は変更することができることを理解されたい。
【００１４】
図２に示すように、システム２００は、ネットワーク２３０を介してクライアント２２０と通信するサーバ２０２を備える。
単一のサーバ２０２、単一のクライアント２２０、及び単一のネットワーク２３０が図２に示されているが、システム２００は、任意の数のサーバ２０２、クライアント２２０、及びネットワーク２３０を備えることができる。
ネットワーク２３０は、イントラネットのようなローカルエリアネットワーク、又はインターネットのようなワイドエリアネットワークを含むことができる。
【００１５】
いかなる点においても、サーバ２０２は概して、符号化コンテンツをクライアント２２０に提供するように構成されるウェブベースコンテンツプロバイダのようなコンテンツプロバイダを含む。
符号化コンテンツはストリーミングビデオの符号化フレームを含む。
一実施例によれば、サーバ２０２は、ストリーミングビデオにおける共通のシーンの複数のビューを選択すること及び見ることを可能にする。
ユーザはしたがって、互いに対して異なるロケーションに位置決めされた複数のカメラによって取り込まれたコンテンツ、コンピュータ生成データから導出された仮想の複数のビュー等のような、複数のビューから取り込まれるか又は見られる同じシナリオを対話的に見るようにクライアント２２０を実装することができる。
したがって、サーバ２０２は映画、説明ビデオ、コンピュータゲーム等における同じシーンの複数のビューを示す複数のフレームをクライアント２２０に提供することができる。
したがって、たとえば、ユーザは、複数のビューからの特定のシーンを見ることを対話的に制御するようにクライアント２２０を実装することができる。
【００１６】
サーバ２０２はエンコーダ２０４を備える。
該エンコーダは、サーバ２０２における全ての予め符号化されているビデオデータの記憶コスト制約下で、フレームデータを符号化して、ビデオの対話的ストリーミングに関連付けられる送信コストを実質的に最小化するように構成される。
エンコーダ２０２が動作して、ビデオを符号化し、これらの目的を達成する様々な方法を本明細書において以下でより詳細に説明する。
エンコーダ２０４は概して、本明細書において後述する機能を実施するように構成されるソフトウェア及び／又はハードウェアを含む。
【００１７】
サーバ２０２はまた、送受信機２０６、コントローラ２０８、及びデータ記憶装置２１０を備える。
送受信機２０６は概して、１つ又は複数のクライアント２２０との通信を可能にするように構成されるソフトウェア及び／又はハードウェアを含む。
送受信機２０６はしたがって、選択されたビデオがクライアント（複数可）２２０に通信され、命令がクライアント（複数可）２２０から受信されることを可能にする。
コントローラ２０８は概して、エンコーダ２０４、送受信機２０６、及びデータ記憶装置２１０を含むサーバ構成要素の動作を制御するように構成されるプロセッサ、ＡＳＩＣ、マイクロコントローラ等を含む。
【００１８】
データ記憶装置２１０は、ＥＥＰＲＯＭ又はＣＤＲＯＭ等のような半導体素子、磁気ディスクメモリ装置、不揮発性メモリ装置のような、情報の記憶が可能な任意の装置又は情報の記憶が可能な装置の任意の組み合わせを含む。
データ記憶装置２１０はまた、固定式の又は着脱可能なデータ記憶装置を含むことができる。
符号化ビデオの記憶に加えて、データ記憶装置２１０はまた、コントローラ２０８が、たとえばエンコーダ２０４及び送受信機２０６における様々な動作の実施時に実行することができる１つ又は複数のプログラム命令を記憶することができる。
データ記憶装置２１０をサーバ２０２とは別個の構成要素を形成するものとして示したが、データ記憶装置２１０は、本明細書において論じられるシステム２００の範囲から逸脱することなく、サーバ２０２と一体化することができる。
【００１９】
クライアント２２０は、送受信機２２２、デコーダ２２４、及びインタフェース２２６を備える。
図示されていないが、クライアント２２０は、コントローラ、データ記憶装置、及び他の構成要素のような複数の追加の構成要素を備えることができる。
例として、クライアント２２０は、インターネットを介してサーバ２０２にネットワーク接続される計算装置を備えることができる。
別の例として、クライアント２２０は、ケーブル又は衛星接続を介してサーバ２０２からコンテンツを受信するように構成されるテレビジョン受信機を備えることができる。
【００２０】
いかなる点においても、送受信機２２２は、１つ又は複数のサーバ２０２との通信を可能にするように構成されるソフトウェア及び／又はハードウェアを含む。
送受信機２２２はしたがって、ユーザが対話的にサーバ（複数可）２０２と通信すること、たとえば、サーバ（複数可）２０２から現在受信しているコンテンツのビューを変えるための命令を通信することを可能にする。
デコーダ２２４は、サーバ（複数可）２０２から受信される符号化ビデオを復号化するように構成されるソフトウェア及び／又はハードウェアを含む。
【００２１】
インタフェース２２６は、クライアント２２０とユーザとの間の対話を可能にするように構成されるソフトウェア及び／又はハードウェアを含む。
インタフェース２２６は、入力２２８を通じてユーザからの命令を受信するように構成される。
該インタフェースは、キーボード、マウス、タッチパッド、遠隔制御装置、マイクロフォン等のようなユーザインタフェースを含むことができる。
インタフェース２２６はまた、コンピュータモニタ、テレビモニタ等のような出力２３０上での復号化ビデオの表示を可能にするように構成される。
【００２２】
動作時に、ユーザは、サーバ２０２との対話的マルチビューストリーミングセッションを開始する前に、ビデオストリーミングデータを受信するようにクライアント２２０を実装することができる。
この動作において、クライアント２２０は、時刻ｉ及びビューｊに対応するフレーム（Ｆｉ，ｊ）を受信済みであることができる。
このフレーム（Ｆｉ，ｊ）の受信に続いて、クライアント２２０は、時刻ｉ＋１及びビューｋにおけるフレーム（Ｆｉ＋１，ｋ）の受信をリアルタイムで要求することができる。
ここで、ビューｋはビューｊに等しい場合もあるし、等しくない場合もある。
応答において、サーバ２０２は、デコーダ２２４がフレーム（Ｆｉ＋１，ｋ）を復号化することができるように、データ記憶装置２１０内に準備及び記憶されている符号化データの適切なセットをクライアント２２０に送信する。
符号化データの適切なセットの送信は、１つ又は複数の参照フレーム（Ｐフレーム又はＩフレーム）の送信を含み、デコーダ２２４が適切にフレーム（Ｆｉ＋１，ｋ）を復号化することを可能にすることができる。
【００２３】
一実施例によれば、エンコーダ２０４は、マルチビュービデオのフレーム（Ｆ）の送信に関連付けられるコストを大幅に削減するようにマルチビュービデオのフレーム（Ｆ）を符号化するように構成される。
サーバ２０２が動作してこの目的を達成する１つの方法を図３を参照して説明する。
別の実施例によれば、エンコーダ２０４は、符号化フレームを送信することに関連付けられるコストと、フレームの予測シーケンスと共に符号化フレームを記憶することに関連付けられるコストとの間のトレードオフを実質的に最適化するように、マルチビュービデオのフレーム（Ｆ）を符号化するように構成される。
サーバ２０２が動作してこの目的を達成する１つの方法を図４を参照して説明する。
サーバ２０２が動作してこの目的を達成する別の方法を図５を参照して説明する。
以下の図面の全てにおいて、各時間インデックスにおける各ビューの少なくとも１つのフレームを符号化し、デコーダが適切にフレームの全てを復号化するのを可能にするためにエンコーダ２０４が必要とされることを理解されたい。
【００２４】
まず図３を参照すると、符号化木３００の概略図が示されている。
該符号化木は基本Ｉフレーム３０２及び複数のＰフレームを含む。
図示されているように、Ｐフレームは、差分符号化のための参照フレームとして先行するＰフレーム又はＩフレーム３０２に依拠する。
加えて、符号化木３００は、フレームのうちの幾つかの多重表現を含む。
ここで、多重表現のそれぞれは、差分符号化のための異なる参照フレームに依拠する。
図３に示されている符号化木３００によれば、クライアントは、複数のビューから選択を行うことができ、事前に準備された一連の適切なＰフレームを選択されたビューに従って受信することができる。
或る点においては、Ｐフレームの通信に関連付けられる送信コストは、図１を参照して上述したＩフレームの送信に関連付けられる送信コストよりも比較的小さい。
図３に示されている符号化木３００を記憶することの１つの欠点は、Ｉフレーム及びＰフレームの記憶に関連付けられるコストが、全てのあり得るビュー走査（traversal）の予測フレームシーケンスの準備及び記憶に起因して、Ｉフレームの記憶と比較して指数関数的に増大することである。
記憶要件は、本明細書において後述する符号化木４００及び５００の使用を通じて低減される。
【００２５】
まず図４を参照すると、一実施例による、幾つかのフレームが省略又は除去されており、それによって符号化フレームの記憶空間要件が低減される符号化木４００が示されている。
図４に示されている符号化木４００は、あり得る符号化木の例示的な実施例に過ぎず、したがって、いかなる点においても本発明を限定するものと解釈されるべきではないことを理解されたい。
【００２６】
符号化木４００は、フレームの適切な復号化を可能にするために必要なそれぞれのシーケンスに従って配置される複数のフレームを含む符号化木の一実施例を示している。
符号化木４００は、異なる参照フレームを使用して符号化されたフレームの多重表現を含む。
図４内に示されているように、フレームの幾つかの多重表現が破線で示されており、エンコーダ２０４がこれらのフレームを符号化していないこと及び／又はこれらのフレームがデータ記憶装置２１０に記憶されていないことを示している。
したがって、データ記憶装置２１０内にフレーム及び予測フレームシーケンスを記憶するのに必要とされる空間の量は、図３に示されている符号化木３００によって必要とされる空間と比較して大幅に低減される。
図３では、要求が特定のフレームに関して受信されると、複数の経路のうちのいずれかを辿って、クライアントに適切なフレームシーケンスを提供し、クライアントがその特定のフレームを復号化することを可能にすることができる。
加えて、図３における符号化木３００に示されている選択される経路のそれぞれは、同じ送信コストを必要とする。
【００２７】
しかしながら、図４を参照すると、送信コストは経路に依存している。
すなわち、経路のうちの幾つかは、いずれのフレームが既にクライアント２２０に送信されているかによって、より大きな送信コストを必要とする。
この点をさらに示すために、クライアント２２０が現在Ｐ１（２，１）を見ており、フレームＰ（１，１）及びＩ（０，０）を受信済みであると仮定する。
加えて、クライアント２２０がフレームＰ（３，２）を要求済みであると仮定する。
図示されているように、フレームＰ１（２，１）及びＰ（１，１）からの経路を辿ると、フレームＰ（３，２）は符号化及び記憶されていない。
この状況において、コントローラ２０８は、フレームＰ（３，２）の適切な復号化を可能にするために、符号化木４００の全体にわたって代替のルートを捜し求める。
【００２８】
コントローラ２０８が選択し得るルートのうちの１つは、再ルーティングＡ４０２であり、別のルートは再ルーティングＢ４０４である。
再ルーティングＡ４０２では、コントローラ２０８は、フレームＰ（１，１）及びＩ（０，０）が既にクライアント２２０に送信されているため、フレームＰ１（２，２）及びＰ（３，２）を送信する必要がある。
再ルーティングＢ４０４では、コントローラ２０８は、フレームＩ（０，０）が既にクライアント２２０に送信されたため、フレームＰ（１，２）、Ｐ２（２，１）、及びＰ（３，２）を送信する必要がある。
フレームＰ２（２，１）はフレームＰ１（２，１）とは異なることに留意されたい。
これは、これらのフレームがそれぞれ、異なる参照フレームＰ（１，１）及びＰ（１，２）を使用して作成されたためである。
加えて、コントローラ２０８は、実質的に最小の送信コストを要求する再ルーティング経路を選択するように構成される。
この例では、再ルーティング経路４０４は、再ルーティング経路４０２よりも多くの送信コストを要求する。
これは、経路４０４がさらなるフレーム（Ｐ２（２，１））の送信を要求するためである。
【００２９】
したがって、フレームのうちの少なくとも幾つかが除去又は省略されており且つ本明細書に開示されるような最小送信コストを必要とする経路の選択が行われる符号化木４００は、データ記憶装置２１０の記憶コスト制約内に留まりながら、クライアントがストリーミングビデオと対話する、たとえばマルチビューストリーミングビデオ内のビューを変更することができる１つの方法である。
【００３０】
ここで図５を参照すると、一実施例による、幾つかのフレームが省略又は除去されており、それによって符号化フレームの記憶空間要件が低減され、且つＰフレームがＩフレームに置き換えられている符号化木５００が示されている。
図５に示されている符号化木５００は、あり得る符号化木の例示的な実施例に過ぎず、したがって、いかなる点においても本発明を限定するものと解釈されるべきではないことを理解されたい。
【００３１】
図５に図示されているように、破線によって示されているように且つ図４と比較すると、符号化木５００からフレームＰ（２，２）の多重表現が省略又は除去されている。
加えて、ＩフレームＩ（２，２）が、それらの以前の位置において符号化木５００内に置かれている。
ＩフレームＩ（２，２）は、単一のＰフレームＰ（２，２）よりも大きな記憶コスト及び送信コストを必要とし得るが、ＩフレームＩ（２，２）の使用は結果的に、単一のＰフレームＰ（２，２）からの派生Ｐフレーム及び単一のＰフレームＰ（２，２）自体の数の減少に起因して、記憶コストを低減することができる。
加えて、符号化木５００を通る再ルーティングも、ＩフレームＩ（２，２）が独立フレームを含むため、より小さい送信コストを必要とし得る。
【００３２】
この点をさらに示すために、クライアント２２０が現在Ｐ１（２，１）を見ており、フレームＰ（１，１）及びＩ（０，０）を受信済みであると仮定する。
加えて、クライアント２２０がフレームＰ（３，２）を要求済みであると仮定する。
図示されているように、フレームＰ１（２，１）及びＰ（１，１）からの経路を辿ると、フレームＰ（３，２）は符号化及び記憶されていない。
この状況において、コントローラ２０８は、フレームＰ（３，２）の適切な符号化を可能にするために、符号化木５００の全体にわたって代替のルートを探索する。
【００３３】
コントローラ２０８が選択し得るルートのうちの１つは、再ルーティングＡ５０２であり、別のルートは再ルーティングＢ５０４である。
再ルーティングＡ５０２では、コントローラ２０８は、フレームＩ（２，２）がイントラ符号化フレームであり、したがって参照フレームを必要としないため、フレームＩ（２，２）及びＰ（３，２）を送信する必要がある。
再ルーティングＢ５０４では、コントローラ２０８は、フレームＩ（０，０）が既にクライアント２２０に送信されたため、フレームＰ（１，２）、Ｐ２（２，１）、及びＰ（３，２）を送信する必要がある。
この例では、したがって、２つの根ノード、フレームＩ（０，０）及びフレームＩ（２，２）が存在する。
コントローラ２０８は、再ルーティング経路５０２及び５０４のそれぞれに関連付けられる送信コストを求めると共に、最小送信コストを必要とする再ルーティング経路を選択するように構成される。
この例では、再ルーティングＡ５０２は、必ずしも最小送信コストを必要としなくてもよい。
これは、ＩフレームＩ（２，２）が複数のＰフレームの代わりに通信されるためである。
【００３４】
これより、システム２００を使用して複数のフレームから成るビデオデータを管理することができる方法の例を、それぞれ図６及び図７に示されている方法６００及び７００の以下のフロー図を参照して説明する。
方法６００及び７００の範囲から逸脱することなく他のステップを追加することができるか又は既存のステップを除去、変更、若しくは再構成することができることが当業者には明らかであるはずである。
【００３５】
方法６００及び７００を図２に示されているシステム２００を参照して説明する。
したがって、該システムに挙げられている要素をこの説明において参照する。
しかしながら、方法６００及び７００は、システム２００に記載されている要素に限定されないことを理解されたい。
そうではなく、方法６００及び７００は、システム２００に記載されている構成とは異なる構成を有するシステムによって実践することができることを理解されたい。
【００３６】
方法６００及び７００に記載されている動作のうちの幾つか又は全ては、任意の所望のコンピュータアクセス可能媒体内に、ユーティリティ、プログラム、又はサブプログラムとして含むことができる。
加えて、方法６００及び７００は、アクティブ及び非アクティブの双方の様々な形態で存在することができるコンピュータプログラムによって具現化することができる。
たとえば、これらの方法は、ソースコード、オブジェクトコード、実行可能コード、又は他のフォーマットのプログラム命令から成るソフトウェアプログラム（複数可）として存在することができる。
上記のうちのいずれも、コンピュータ可読媒体上で具現化することができる。
【００３７】
例示的なコンピュータ可読記憶装置は、従来のコンピュータシステムＲＡＭ、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、及び磁気又は光ディスク又はテープを含む。
上記のものの具体的な例は、ＣＤ  ＲＯＭ上での又はインターネットダウンロードを介するプログラムの配布を含む。
したがって、上記で説明した機能を実行することができる任意の電子装置が上記で列挙した機能を実施することができることを理解されたい。
【００３８】
図６を参照すると、一実施例による、複数のフレームから成るマルチビューストリーミングビデオデータを管理する方法６００のフロー図が示されている。
上述したように、ビデオデータは、ビデオデータの符号化フレームを送信することに関連付けられるコストと、フレームの予測シーケンスと共に符号化フレームを記憶することに関連付けられるコストとの間のトレードオフを最適化するように管理することができる。
或る点においては、フレームは、共通のシーンの複数のビューのような、クライアント２２０によって受信されるコンテンツに対する比較的効率的な対話的制御を可能にするように符号化される。
【００３９】
ステップ６０２において、複数のフレームから成るマルチビューストリーミングビデオデータを、たとえば、データ記憶装置２１０、又は、複数のロケーションに位置決めされると共に共通のシーンを取り込むように構成される複数のビデオカメラのような他のソースから取得する。
ステップ６０４において、コントローラ２０８は、データ記憶装置２１０の記憶制約を特定する。
データ記憶装置２１０の記憶制約は、データ記憶装置２１０の最大記憶容量のような物理的記憶制約を含む場合がある。
付加的に又は代替的に、記憶制約は、データ記憶装置２１０内での符号化フレームの記憶に関して設定される、課せられる制限を含む場合がある。
【００４０】
ステップ６０６において、エンコーダ２０４は、複数のフレームのうちの少なくとも１つのフレームの多重表現を、該多重表現ごとに異なる参照フレームを使用して符号化する。
ここで、多重表現は共通の時間インデックス及び共通のビューに対応する。
加えて、ステップ６０８において、コントローラ２０８は、データ記憶装置２１０の記憶制約を考慮して、たとえば図４及び図５に図示されているような、複数のフレーム及び多重表現を含む符号化木を作成する。
より詳細には、コントローラ２０８は、符号化木が記憶要件よりも少ない空間を必要とするように多重表現のうちの少なくとも１つが符号化木から省略されている符号化木を作成する。
【００４１】
一実施例によれば、多重表現のうちのいずれを符号化木から省略するかの決定において、コントローラ２０８は、クライアント２２０が時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装するように構成される。
対話モデルは、たとえば他の参照フレームの受信に続いていずれのフレームが選択されたかに関する履歴情報に基づいてこの確率を求めることができる。
加えて、コントローラ２０８は、データ記憶装置の記憶制約内に留まるために、まず、要求される可能性が最も少ないフレームが符号化木から省略されるように、対話モデルに基づいて符号化木内の複数のフレームを配置するように構成される。
【００４２】
ステップ６０８において符号化木を作成する際、コントローラ２０８は、少なくとも１つのフレームの多重表現をクライアント２２０に通信することに関連付けられる送信コストを計算するようにさらに構成することができる。
加えて、コントローラ２０８は、記憶コストを削減するために、存在する場合にはいずれのＰフレームをＩフレームで置き換えるかを決定すると共に、データ記憶装置２１０の記憶制約内に留まりながら、計算される送信コストを実質的に最小化する送信Ｐフレーム及びＩフレームの組み合わせを決定するように構成することができる。
【００４３】
ステップ６１０において、コントローラ２０８はデータ記憶装置２１０内に符号化木を記憶する。
【００４４】
コントローラ２０８を、特定のフレームを省略するように符号化木を作成するものとして説明したが、コントローラ２０８は、データ記憶装置２１０の記憶制約内に留まるために、多重表現（複数可）を、それらが符号化木内に含まれた後に除去することができることを理解されたい。
【００４５】
方法６００の実施を通じて、コントローラ２０８は、図４及び図５に示されている符号化木と同様の符号化木を生成するように構成される。
したがって、コントローラ２０８は、少なくとも１つのフレームの多重表現のうちの少なくとも１つが各時間インデックスにおける各ビューに対応する符号化木を作成するように構成される。
コントローラ２０８によって作成される符号化木はまた、符号化木を通る２つ以上のルートが利用可能となることを可能にし、それによって、クライアント２２０が、符号化木から選択されたフレームを受信すると共に適切に復号化することを可能にすることができる。
符号化木を通るルートを選択して送信コストを実質的に最小化することができる方法の一例を図７を参照して説明する。
【００４６】
より詳細には図７は、一実施例による、方法６００に対する促進のための、複数のフレームから成るビデオデータを管理する方法７００のフロー図を示している。
より詳細には図７は、送信コストを実質的に最小化するように、方法６００を通じて生成された符号化木を実装するステップを示している。
実際には方法７００は、上述したフレーム及び経路の再ルーティングと同様である。
【００４７】
ステップ７０２において、コントローラ２０８は第１のフレームをクライアント２２０に通信する。
ステップ７０４において、コントローラ２０８は、第２のフレームを求める要求をクライアント２２０から受信する。
ステップ７０６において、コントローラ２０８は、第２のフレームがクライアント２２０において適切に復号化されるために、少なくとも１つのフレームの多重表現のうちの１つが必要とされると判断する。
ステップ７０８において、コントローラ２０８は、多重表現のそれぞれを通信することに関連付けられる送信コストを求める。
加えて、ステップ７１０において、コントローラ２０８は、最低送信コストに関連付けられる少なくとも１つのフレームの多重表現のうちの１つをクライアント２２０に送信する。
【００４８】
これより、コントローラ２０８が符号化木を作成することができる方法の一例を説明する。
大まかに述べると、エンコーダ２０４は、マルチビュービデオの個別のフレームを符号化すると共に、データ記憶装置２１０内に個別の符号化フレームを記憶するように構成される。
所与のフレーム取り込み時刻における取り込まれたビューの数は定数Ｋである。
換言すると、シーンのＫ個の異なるビューが同時に周期的に取り込まれる。
上述したように、所与のフレームの異なるビューは、複数のカメラによって、又は、フレームバッファからの複数のフレームから、たとえば仮想世界表現から取り込むことができる。
【００４９】
冗長符号化構造４００を再び参照して、ＩフレームＩ（０，０）によって示される、時間インデックス０の第１のフレーム取り込みインスタンスは単一のビュー［Ｋ／２］のものであり、合計でＮ個のフレーム取り込みインスタンスが存在すると仮定する。
符号化構造４００は、該符号化構造が同じフレームの多重表現を含み、多重表現のそれぞれが異なる参照フレームを有するため、冗長とみなされる。
【００５０】
図４は異なる２つのビュー（Ｋ＝２）と、４つのフレーム取り込みインスタンス（Ｎ＝４）を示している。
加えて、根がＩ（０，０）にある１つの基本依存木が存在する。
冗長符号化構造４００は、フレームのほとんどが、それぞれが異なる参照フレームを使用してＩフレーム及び／又はＰフレーム（複数可）として多重表現に符号化されることを示している。
したがって、クライアント２２０が時間インデックスｉ及びビューｊのフレームＦｉ，ｊの特定の表現を見た後に次の時間インデックスｉ＋１のビューｋを要求する場合、コントローラ２０８は、利用可能であればＩフレームＩｉ＋１，ｋ、利用可能であればＦｉ，ｊを使用して動き補償されたＰフレームＰｉ＋１，ｋ、又は異なる参照フレームＦ≠Ｆｉ，ｊを使用して動き補償された代替のＰフレームＰｉ＋１，ｋのうちのいずれかを選択する。
この最後の代替フレームでは、Ｆを含む参照フレーム（複数可）も、Ｐｉ＋１，ｋの正確な復号化のためにクライアント２２０に送信しなければならない。
【００５１】
時間インデックスｉ及びビューｊの元のフレーム
【００５２】
【数１】
2010093807.tif 000003
【００５３】
は、多数の表現Ｆｉ，ｊに、また、ＩフレームＩｉ，ｊとして又は複数の異なる参照Ｆを使用して動き補償されたＰフレームPｉ，ｊ（Ｆ）として少なくとも１つの表現に符号化することができる。
単純にするために、ＰフレームPｉ，ｊ（Ｆ）を、時間インデックスｉ−１、及びｍａｘ（１，ｊ−１）とｍｉｎ（Ｋ，ｊ＋１）との間のビューの符号化フレームＦを参照として使用して動き補償されるものとしてのみ仮定する。
【００５４】
特定の表現の符号化フレームの全ては、異なる根フレームのＳ個の基本依存木から成る集合
【００５５】
【数２】
2010093807.tif 000004
【００５６】
に編成することができる。
固有の根Ｉフレーム
【００５７】
【数４】
2010093807.tif 000005
【００５８】
を有する木
【００５９】
【数３】
2010093807.tif 000006
【００６０】
は以下のように再帰的に定義される。
【００６１】
【数５】
2010093807.tif 000007
式（１）
【００６２】
式（１）は、フレームＦを根とする木Ｔ（Ｆ）が、フレームＦと、フレームＦから分岐する（部分）木とから成るフレーム集合であることを示す。
基本依存木は、Ｉフレームとして符号化される根フレームを有する木である。
木集合τを使用して、フレームＦの依存経路ｐ（Ｆ）を、Ｆが属する基本依存木において根ＩフレームからフレームＦまで進む全てのフレームの順序集合とする。
より詳細には、依存経路
【００６３】
【数６】
2010093807.tif 000008
【００６４】
はＩフレームである。
【００６５】
実際的な目的のために、各元フレーム
【００６６】
【数７】
2010093807.tif 000009
【００６７】
をＭ個を超える表現に符号化することはできないと仮定する。
したがって、基本依存木の集合内の最大ノード数はＭＮＫによって制限される。
そうでない場合、基本依存木の集合は、元フレームＮＫの関数として指数関数的に大きいノード数を有し得る。実際的な目的のために、各元フレーム
【００６８】
【数８】
2010093807.tif 000010
【００６９】
をＭ個を超える表現に符号化することはできないと仮定する。
したがって、基本依存木の集合内の最大ノード数はＭＮＫによって制限される。
そうでない場合、基本依存木の集合は、元フレームＮＫの関数として指数関数的に大きいノード数を有し得る。
【００７０】
マルチビュービデオの表現のための実現可能な空間
【００７１】
【数９】
2010093807.tif 000011
【００７２】
は、各元フレーム
【００７３】
【数１０】
2010093807.tif 000012
【００７４】
が、Ｉフレームとして又は
【００７５】
【数１１】
2010093807.tif 000013
【００７６】
の場合に符号化フレームＦｉ−１，Ｋを使用してＰフレームとして、Ｍ回を超えないように、しかし少なくとも１回符号化されるように、式（１）に記載されているように、基本依存木の集合τとして定義することができる。
それぞれの選択された木集合
【００７７】
【数１２】
2010093807.tif 000014
【００７８】
は記憶コスト及び送信コストの双方を暗示する。
【００７９】
これより、データ記憶装置２１０内に記憶される符号化木４００の記憶コストを計算することができる方法の一例を論じる。
Ｉフレームに関して、｜Ｉｉ，ｊ｜は、Ｉフレームとして元のフレーム
【００８０】
【数１３】
2010093807.tif 000015
【００８１】
を符号化することのバイト数を表すものとする。
｜Ｉｉ，ｊ｜＝∞は、
【００８２】
【数１４】
2010093807.tif 000016
【００８３】
がＩフレームとして符号化されなかった場合を表す。
同様に、Ｐフレームに関して、｜Ｐｉ，ｊ（Ｆ）｜は、フレームＦを動き補償のために使用して
【００８４】
【数１５】
2010093807.tif 000017
【００８５】
をＰフレームとして符号化するのに必要とされるバイト数を表す。
｜Ｐｉ，ｊ（Ｆ）｜＝∞は、
【００８６】
【数１６】
2010093807.tif 000018
【００８７】
が、Ｆを動き補償のために使用してＰフレームとして符号化されなかった場合を表す。
表現τの記憶コストＢ（τ）は以下のように記述することができる。
【００８８】
【数１７】
2010093807.tif 000019
式（２）
【００８９】
換言すると、Ｆを根とする符号化木τ（Ｆ）を符号化する記憶コストは、根フレームのサイズ｜Ｆ｜にＦから分岐する木を加算したものである。
【００９０】
これより、フレーム間送信コストを計算することができる方法の一例を論じる。
ユーザが、依存経路ｐ＝ｐ（Ｆｉ，ｊ）を有する符号化フレームＦｉ，ｊを見た後、ビューｋの時刻ｉ＋１におけるフレームを見ることを選択すると仮定する。
コントローラ２０８は、以下のように、Ｆｉ，ｊ及びｋに基づいてクライアント２２０に送信するフレーム
【００９１】
【数１８】
2010093807.tif 000020
【００９２】
の符号化表現を決定論的に判断する。
まず、符号化ＩフレームＩｉ＋１，ｋ又はＰフレームＰｉ＋１，ｋ（Ｆｉ，ｊ）のいずれかが利用可能である場合、コントローラ２０８は、復号化及び表示のためにクライアント２２０にそれらのうちのいずれかを送信することができる。
【００９３】
これらのフレームのうちのいずれもが利用可能でない場合、コントローラ２０８は、代替のＰフレームＰｉ＋１，ｋ（Ｆ'），Ｆ'≠Ｆｉ，ｊ、たとえばその参照フレームがクライアント２２０において利用可能でないＰフレームを、代替の経路ｑ＝ｐ（Ｆ'）を用いて求める。
ここで、ｉ）経路ｐ及びｑは重なり合わない経路であるか、又はｉｉ）経路ｐ及びｑは重なり合い、経路ｑのフレーム
【００９４】
【数１９】
2010093807.tif 000021
【００９５】
後に初めて分かれる。
ここで、「重なり合わない」とは、動き補償されたＦｉ，ｊ及びＦが共通の復号化履歴を共有しないことを意味するように意図されている。
そして「重なり合う」とは、Ｆｉ，ｊ及びＦが
【００９６】
【数２０】
2010093807.tif 000022
【００９７】
まで復号化履歴を共有することを意味するように意図されている。
この第１の場合では、コントローラ２０８は、時間インデックスｉ＋１及びビューｋを有するフレームの正確な復号化のために、依存経路
【００９８】
【数２１】
2010093807.tif 000023
【００９９】
における全てのフレームとＰフレームＰｉ＋１，ｋ（Ｆ'）自体とを送信する必要があり、この場合、デコーダ２２４は復号化ＰフレームＰｉ＋１，ｋ（Ｆ'）のみを表示する。
第２の場合では、コントローラ２０８は、経路ｑの部分経路
【０１００】
【数２２】
2010093807.tif 000024
【０１０１】
とＰフレームＰｉ＋１，ｋ（Ｆ'）とを送信する必要がある。
したがって、これらの２つの場合のそれぞれに関して、ｐからｑへ依存経路を再ルーティングする総送信コストｒ（ｐ，ｑ）は以下のようになる。
【０１０２】
【数２３】
2010093807.tif 000025
式（３）
【０１０３】
異なる複数の参照Ｆ'及び代替の経路ｐ（Ｆ'）に関して複数の代替のＰフレームＰｉ＋１，ｋ（Ｆ'）が存在し得る。
したがって、コントローラ２０８は、以下のように、依存経路ｐ（Ｆｉ，ｊ）及び所望のビューｋを所与として、最低送信コストφ（ｐ，ｋ）を有する経路を求める必要がある。
【０１０４】
【数２４】
2010093807.tif 000026
式（４）
【０１０５】
したがって、ユーザが符号化フレームＦｉ，ｊ，Φ（Ｆｉ，ｊ，ｋ）の観察後にビューｋを選択することに関する送信コストは、場合によっては利用可能なIフレーム、Pフレーム、及び代替のＰフレーム（複数可）の最小送信コストである。
【０１０６】
【数２５】
2010093807.tif 000027
式（５）
【０１０７】
これより、記憶コスト及び送信コストの最適化を求めることができる方法の一例を説明する。
Ｃ（τ）は、木集合τを所与とした、Ｎフレーム対話的マルチビューストリーミングの予想送信コストを表すものとする。
元のフレーム
【０１０８】
【数２６】
2010093807.tif 000028
【０１０９】
の符号化表現の観察後、ユーザが、確率αｉ，ｊ（ｋ）で次の時間インデックスｉ＋１において次のビューｋを見ると仮定する。
ここで、Σｋαｉ，ｊ（ｋ）＝１である。
式（５）からのフレーム間送信コストの導出を使用して、予想送信コストＣ（τ）を以下のように記述することができる。
【０１１０】
【数２７】
2010093807.tif 000029
式（６）
【０１１１】
式（６）は、再帰的に効率的に計算することができる。
第１に、ｃ（Ｆｉ，ｊ）は最大で３項の総和である。
第２に、Φ（Ｆｉ，ｊ，ｋ）におけるφ（ｐ（Ｆｉ，ｊ），ｋ）は、試験用に最大でＭ個の参照Ｆ'（Ｆｉ＋１，ｋの最大Ｍ個の表現）を有する。
参照Ｆ'ごとに、再ルーティングコストｒ（ｐ（Ｆｉ，ｊ），ｐ（Ｆ'））は最大でＮ回の加算を有する。
最初に計算されたｃ（Ｆｉ，ｊ）は、後のｃ（Ｆｉ，ｊ）に対する再帰呼び出しが単に計算された値を返すことができるように、テーブルに記憶される。
式（６）の計算量はしたがって、木集合τ内の最大ノード数のＭ×Ｎ倍であり、すなわちＯ（Ｍ２Ｎ２Ｋ）である。
【０１１２】
記憶コストの計算は、元のフレームの全ての可能な符号化表現のＰフレームの正確な符号化コストを求める代わりに、Ｉｉ，ｊ＝ｒＩｉ，ｊであること、且つ、元のフレーム
【０１１３】
【数２８】
2010093807.tif 000030
【０１１４】
の任意の符号化表現Ｆｉ−１，ｋに関してＰｉ，ｊ（Ｆｉ−１，ｋ）＝ｒＰｉ，ｊ（ｋ）であることを仮定することによって単純化することができる。
ここで、ＩＭＶＳとして表される対話的マルチビューストリーミング最適化を以下のように形式化することができる。
Ｋ個のビューから成るマルチビュービデオのＮ個のフレームの場合の推移確率αｉ，ｊ（ｋ）及び符号化レートｒＩｉ，ｊ及び
【０１１５】
【数２９】
2010093807.tif 000031
【０１１６】
を所与として、記憶制約
【０１１７】
【数３１】
2010093807.tif 000032
【０１１８】
下で予想送信コストＣ（τ）を最小化する実現可能空間
【０１１９】
【数３０】
2010093807.tif 000033
【０１２０】
において最適な木集合τを求める。
これは以下のように数学的に記述することができる。
【０１２１】
【数３２】
2010093807.tif 000034
式（７）
【０１２２】
これより、近似アルゴリズムを使用してＩＭＶＳを最適化することができる方法の一例を論じる。
初期解τＩとして、各ビューの各フレームが１回だけ符号化される、全てのビューの全てのフレームのための最小記憶空間を必要とする最小記憶解を求める。
Ｉフレーム｜Ｉｉ，ｊ｜のサイズがその対応するＰフレームのサイズ｜Ｐｉ，ｊ（Ｆｉ−１，ｋ）｜よりも大きいと仮定すると、最小記憶解τＩは全てのＰフレームが後続するＩフレームである。
最小記憶解τＩは以下のように数学的に求めることができる。
【０１２３】
【数３３】
2010093807.tif 000035
式（８）
【０１２４】
式（８）において、節（clause）ｃが真である場合Ｕ（ｃ）＝１であり、そうでない場合は０である。
加えて、式（８）は基本的に、元のフレーム
【０１２５】
【数３４】
2010093807.tif 000036
【０１２６】
ごとに最小ＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）を求める。
【０１２７】
次のステップは、τＩから局所最適解を求めることである。
これは、一連の拡大（augmentation）を定義すると共に、選択されたコスト関数においてより大きな低減を提供する拡大をこれらのうちから選択することによって反復的に行うことができる。
適切な拡大の例は、ＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）をＩフレームＩｉ，ｊに変更すること、異なる参照フレームＦ'をＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）のために選択すること、新たなＩフレームＩｉ，ｊを追加すること、及び新たなＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）を追加することを含む。
最初の２つの拡大は所与のフレームの表現の数を増加させず、一方、次の２つの拡大のそれぞれは表現の数を１だけ増加させる。
したがって、最後の２つの拡大は、そのフレームの表現の数がＭより小さい場合に実施することができる。
結果的に得られる解は常に、各ビューの各フレームの少なくとも１つの表現を有する。
【０１２８】
新たなＩフレームＩｉ，ｊを加えて既存のＰフレーム（複数可）を「補償する」場合、既存のＰフレーム（複数可）のいずれの子が親を新たに加えられたＩフレームに切り替えるべきかが判断される。
これは貪欲に行われ得る。
すなわち、切り替えによって送信コストが低下する場合、既存のＰフレームの子が切り替えられる。
同様に、新たなＰフレームを追加する場合の最適な親及び子ノード選択も貪欲に実施される。
【０１２９】
上述した拡大を所与として、２つの呼び出し関数を有する２つのアルゴリズムを提案する。
第１の提案はラグランジュコストである。
【０１３０】
【数３５】
2010093807.tif 000037
式（９）
【０１３１】
式（９）において、λ≧０はラグランジュ乗数である。
各反復において、ラグランジュコストにおいて最大低減を提供する拡大を選択する。
加えて、本アルゴリズムは、λを所与としてさらなるコスト低減が可能でないときに停止する。
さらに、記憶コストと送信コストとの間のトレードオフは、複数の異なるλの使用を通じて変化することができる。
【０１３２】
代替的に、各反復において、現在解τにおける全てのフレームＦｉ，ｊの拡大は、送信コストの低減ΔＣ（τ）と、記憶コストの増加ΔＢ（τ）との比が最大であるように選択することができる。
このアルゴリズムは、次のこのような有益な拡大が記憶制約
【０１３３】
【数３６】
2010093807.tif 000038
【０１３４】
を超える場合に停止することができる。
【０１３５】
図８は、一実施例による、図６及び図７に示されている方法６００及び７００を実装又は実行するように構成される計算装置８００のブロック図を示している。
この点において、計算装置８００は、図１に示されているサーバ２０２に関して上記で説明した機能のうちの１つ又は複数を実行するためのプラットフォームとして使用することができる。
【０１３６】
計算装置８００は、方法６００及び７００において説明されたステップのうちの幾つかまたは全てを実装又は実行することができるプロセッサ８０２を備える。
プロセッサ８０２からのコマンド及びデータは通信バス８０４を介して通信される。
計算装置８００はまた、ランダムアクセスメモリ（ＲＡＭ）のようなメインメモリ８０６を備える。
該メインメモリにおいて、プロセッサ８０２に対するプログラムコードが実行時間中に実行されることができる。
また該計算装置は２次メモリ８０８を備える。
２次メモリ８０８は、たとえば、フロッピー（登録商標）ディスクドライブ、磁気テープドライブ、コンパクトディスクドライブ等を表す１つ又は複数のハードディスクドライブ８１０及び／又は着脱可能記憶ドライブ８１２を含み、これらにおいて、方法６００及び７００のプログラムコードのコピーを記憶することができる。
【０１３７】
着脱可能記憶ドライブ８１２は、既知の方法で着脱可能記憶ユニット８１４との間で読み書きを行う。
ユーザ入力及び出力装置は、キーボード８１６、マウス８１８、及びディスプレイ８２０を含むことができる。
ディスプレイアダプタ８２２は、通信バス８０４及びディスプレイ８２０とインタフェースすることができ、プロセッサ８０２から表示データを受信して、該表示データをディスプレイ８２０に対する表示コマンドに変換することができる。
加えて、プロセッサ（複数可）８０２は、ネットワークアダプタ８２４を通じてネットワーク、たとえばインターネット、ＬＡＮ等を介して通信することができる。
【０１３８】
当業者には、計算装置８００において他の既知の電子部品を追加するか又は代わりに用いることができることが明らかであろう。
図８に示されている部品のうちの１つ又は複数は任意選択とすることができる（たとえば、ユーザ入力装置、２次メモリ等）ことも明らかであるはずである。
【０１３９】
本明細書において説明及び例示してきたものは、本発明の好ましい一実施形態、及びその変形形態のうちの幾つかである。
本明細書において使用される用語、説明、及び図面は、例示のためにのみ記載され、限定を意味するものではない。
当業者は、別途指示されない限り全ての用語がその最も広い適切な意味を有するように意図されている以下の特許請求の範囲及びその均等物によって規定されるように意図されている本発明の範囲内で多数の変形形態が可能であることを認識するであろう。
【符号の説明】
【０１４０】
１００・・・符号化木，
２００・・・システム，
２０２・・・サーバ，
２０４・・・エンコーダ，
２０６，２２２・・・送受信機，
２０８・・・コントローラ，
２１０・・・データ記憶装置，
２２０・・・クライアント，
２２４・・・デコーダ，
２２６・・・インタフェース，
２２８・・・入力，
３００・・・符号化木，
３０２・・・基本Ｉフレーム，
４００・・・符号化木，
４０２・・・再ルーティングＡ，
４０４・・・再ルーティングＢ，
５００・・・符号化木，
５０２・・・再ルーティングＡ，
５０４・・・再ルーティングＢ，
８００・・・計算装置，
８０２・・・プロセッサ，
８０４・・・通信バス，
８０６・・・メインメモリ，
８０８・・・２次メモリ，
８１０・・・ハードディスクドライブ，
８１２・・・着脱可能記憶装置，
８１４・・・着脱可能記憶ユニット，
８１６・・・キーボード，
８１８・・・マウス，
８２０・・・ディスプレイ，
８２２・・・ディスプレイアダプタ，
８２４・・・ネットワークアダプタ，
【図１】
2010093807.tif 000039
【図２】
2010093807.tif 000040
【図３】
2010093807.tif 000041
【図４】
2010093807.tif 000042
【図５】
2010093807.tif 000043
【図６】
2010093807.tif 000044
【図７】
2010093807.tif 000045
【図８】
2010093807.tif 000046
【外国語明細書】
【発明の名称】 MANAGING MULTIVIEW STREAMING VIDEO DATA COMPOSED OF FRAMES
【背景技術】
【０００１】
BACKGROUND 
Video is typically compressed using Intra coded frames (I-frames) and Inter or Predicted frames (P-frames).  I-frames are frames that are coded without prediction from other frames and thus do not require reference frames.  P-frames are those frames that use prediction from a reference frame.  I-frames also contain only intra macroblocks, whereas, P-frames contain either intra macroblocks or predicted macroblocks.  P-frames require prior decoding of some other reference frame in order to be decoded and often require fewer bits for encoding than I-frames.
【０００２】
There has been increased development of video applications where multiple views (multiviews) of a scene are captured simultaneously, encoded using I-frames and/or P-frames, and delivered to users.  In these types of video applications, users are given the ability to switch among the multiple views in real-time and are thus afforded greater levels of interactivity than with conventional video applications.  Among applications for multiview video coding (MVC) tools are those where users are allowed to select for playback only a subset of those views or, potentially, virtual views generated from the actual captured video data.  
【０００３】
A schematic diagram of a conventional coding tree 100 based on I-frames (I(i,j)), wherein i is the time index and j is the view, encoded at a server and communicated to a client is depicted in FIG. 1.  As shown therein, the coding tree 100 is encoded based solely on I-frames and thus, some of the I-frames may generate different views as compared with other I-frames, without requiring reference frames for differential coding.  However, the coding tree 100 depicted in FIG. 1 requires large transmission costs because I-frames are typically several times larger than P-frames, as discussed above.  
【０００４】
Many of the recent activities in MVC have focused on image capture and compression.  For example, the MVC standardization process has concentrated on developing new compression algorithms to encode all of the frames in the multiview sequence in a rate-distortion optimal manner.  As such, much consideration has not been given to affording more efficient multiview control of streaming video to clients. 
【図面の簡単な説明】
【０００５】
BRIEF DESCRIPTION OF THE DRAWINGS
Features of the present invention will become apparent to those skilled in the art from the following description with reference to the figures, in which:
【０００６】
FIG. 1 depicts a schematic diagram of a conventional coding tree based on I-frames;
【０００７】
FIG. 2 shows a simplified block diagram of a system for enabling multiview stream data content to be consumed at a client from a server, according to an embodiment of the invention; 
【０００８】
FIG. 3 depicts a coding tree for enabling interactive multiview streaming video data composed of frames have been encoded as multiple representations of the frames based on a root I-frame and a plurality of P-frames, according to an embodiment of the invention;
【０００９】
FIGS. 4 and 5, respectively show coding trees in which a number of frames have been omitted or removed to thus reduce the storage space requirements of the encoded frames, according to an embodiment of the invention; 
【００１０】
FIGS. 6 and 7, respectively show a flow diagram of a method of managing multiview streaming video data composed of a plurality of frames, according to an embodiment of the invention; and
【００１１】
FIG. 8 shows a block diagram of a computing apparatus configured to implement or execute the methods depicted in FIGS. 6 and 7, according to an embodiment of the invention.
【発明を実施するための形態】
【００１２】
DETAILED DESCRIPTION 
For simplicity and illustrative purposes, the present invention is described by referring mainly to an exemplary embodiment thereof.  In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent however, to one of ordinary skill in the art, that the present invention may be practiced without limitation to these specific details.  In other instances, well known methods and structures have not been described in detail so as not to unnecessarily obscure the present invention.  
【００１３】
Disclosed herein are a system and method of managing video data composed of a plurality of frames.  The system and method disclosed herein are configured to create a coding structure that enables an optimal trade-off between storage cost and transmission cost of encoded frames.  In one regard, the trade-off may be made by selectively encoding certain frames more than once such that the coding structure includes multiple representations of those selected frames created using different reference frames.  By selectively encoding selected ones of the frames instead of all of the frames, the coding structure of the present invention requires substantially less space as compared with a coding tree in which all of the multiple representations of the frames have been encoded.
【００１４】
The coding structure may be employed to enable multiview video streaming data to be communicated to a client to enable a user of the client to interactively receive frames from a server.  By way of example, the coding tree may be employed to identify the route through the frames that provides the most efficient communication of frames to enable the client to reconstruct a desired frame.  
【００１５】
With reference to FIG. 2, there is shown a simplified block diagram of a system 200 for enabling multiview streaming data content to be consumed at a client 220 from a server 202, according to an example.  In one regard, the methods disclosed herein below may be implemented in the system 200 as discussed in greater detail herein below.  It should be understood that the system 200 may include additional components and that some of the components described herein may be removed and/or modified without departing from a scope of the system 200.  
【００１６】
As shown in FIG. 2, the system 200 includes a server 202 in communication with a client 220 over a network 230.  Although a single server 202, a single client 220, and a single network 230 have been depicted in FIG. 2, the system 200 may include any number of servers 202, clients 220, and networks 230.  The network 230 may comprise a local area network, such as an Intranet, or a wide area network, such as the Internet.
【００１７】
In any regard, the server 202 generally comprises a content provider, such as, a web-based content provider configured to supply encoded content to the client 220.  The encoded content comprises encoded frames of a streaming video.  According to an example, the server 202 enables selection and viewing of multiple views of a common scene in the streaming video.  A user may thus implement the client 220 to interactively view the same scenario, such as, content captured by cameras positioned at different locations with respect to each other, virtual multiple views derived from computer generated data, etc., as captured or viewed from multiple views.  As such, the server 202 may supply the client 220 with frames depicting multiple views of the same scene in a movie, an instructional video, a computer game, etc.  Thus, for instance, a user may implement the client 220 to interactively control viewing of a particular scene from multiple views. 
【００１８】
The server 202 includes an encoder 204 configured to encode the frame data to substantially minimize transmission costs associated with the interactive streaming of the video, subject to a storage cost constraint of all of the prepared encoded video data at the server 202.  Various manners in which encoder 202 operates to encode the video to achieve these goals are described in greater detail herein below.  The encoder 204 generally comprises software and/or hardware configured to perform the functions discussed herein below.
【００１９】
The server 204 also includes a transceiver 206, a controller 208, and a data store 210.  The transceiver 208 generally comprises software and/or hardware configured to enable communications with one or more clients 220.  The transceiver 208 thus enables selected video to be communicated to and instructions to be received from the client(s) 220.  The controller 208 generally comprises a processor, ASIC, microcontroller, etc., configured to control the operations of the server components, including, the encoder 204, the transceiver 206, and the data store 210.  
【００２０】
The data store 210 comprises any device capable of storage of information or any combination of devices capable of storage of information, such as, a semiconductor device, a magnetic disk memory device, nonvolatile memory devices, such as, an EEPROM or CDROM, etc.  The data store 210 may also comprise a fixed or removable data storage device.  In addition to storing the encoded video, the data store 210 may also store one or more program instructions, which the controller 208 may execute in performing various operations in the encoder 204 and the transceiver 206, for instance.  Although the data store 210 has been depicted as forming a separate component from the server 202, the data store 210 may be integrated with the server 202 without departing from a scope of the system 200 discussed herein.
【００２１】
The client 220 includes a transceiver 222, a decoder 224, and an interface 226.  Although not shown, the client 220 may include a number of additional components, such as, a controller, a data store, and other components.  By way of example, the client 220 may comprise a computing device networked to the server 202 via the Internet.  As another example, the client 220 may comprise a television receiver configured to receive content from the server 202 via a cable or satellite connection.
【００２２】
In any regard, the transceiver 222 comprises software and/or hardware configured to enable communications with one or more servers 202.  The transceiver 222 thus enables a user to interactively communicate with the server(s) 202, for instance, to communicate instructions to change a view of content currently being received from the server(s) 202.  The decoder 224 comprises software and/or hardware configured to decode the encoded video received from the server(s) 202.  
【００２３】
The interface 226 comprises software and/or hardware configured to enable interactions between the client 220 and a user.  The interface 226 is configured to receive instructions from a user through an input 228, which may comprise, a user interface, such as, a keyboard, a mouse, a touchpad, a remote control, a microphone, etc.  The interface 226 is also configured to enable display of the decoded video on an output 230, such as, a computer monitor, a television monitor, etc.
【００２４】
In operation, a user may implement the client 220 to receive video streaming data prior to initiating an interactive multiview streaming session with the server 202.  In this operation, the client 220 may have received a frame (Fi,j) corresponding to time instant i and view j.  Following receipt of that frame (Fi,j), the client 220 may request, in real-time, receipt of the frame (Fi+1,k) at time instant i+1 and view k, where the view k may or may not equal view j.  In response, the server 202 sends an appropriate set of encoded data, which has been prepared and stored in the data store 210, to the client 220, such that the decoder 224 may decode the frame (Fi+1,k).  The transmission of the appropriate set of encoded data may include transmission of one or more reference frames (P-frames or I-frames) to enable the decoder 224 to appropriately decode the frame (Fi+1,k). 
【００２５】
According to an example, the encoder 204 is configured to encode the frames (F) of a multiview video in a manner that substantially reduces costs associated with transmitting the frames (F) of a multiview video.  One manner in which the server 202 operates to achieve this goal is described with respect to FIG. 3.  According to another example, the encoder 204 is configured to encode the frames (F) of a multiview video in a manner that substantially optimizes a tradeoff between costs associated with transmitting the encoded frames and costs associated with storing the encoded frames along with the predicted sequences of the frames.  One manner in which the server 202 operates to achieve this goal is described with respect to FIG. 4.  Another manner in which the server 202 operates to achieve this goal is described with respect to FIG. 5.  In all of the following figures, it should be understood that the encoder 204 is required to encode at least one frame for each view in each time index to enable the decoder to appropriately decode all of the frames.
【００２６】
With reference first to FIG. 3, there is shown a schematic diagram of a coding tree 300, which is includes a base I-frame 302 and a plurality of P-frames.  As shown, the P-frames rely upon prior P-frames or the I-frame 302 as reference frames for differential coding.  In addition, the coding tree 300 includes multiple representations of some of the frames, in which each of the multiple representations relies upon a different reference frame for differential coding.  According to the coding tree 300 depicted in FIG. 3, the client may select from multiple views and may receive the string of appropriate P-frames, which were prepared a priori, according to the selected views.  In one regard, the transmission costs associated with communicating the P-frames is relatively less than those associated with transmitting the I-frames discussed above with respect to FIG. 1.  One drawback of storing the coding tree 300 depicted in FIG. 3 is that the costs associated with storing the I-frames and the P-frames is increased exponentially as compared with storing the I-frames due to the preparation and storage of predicted frame sequences of all of the possible view traversals.  The storage requirement is reduced through use of the coding trees 400 and 500 discussed herein below.
【００２７】
With reference first to FIG. 4, there is shown a coding tree 400 in which a number of frames have been omitted or removed to thus reduce the storage space requirements of the encoded frames, according to an example.  It should be understood that the coding tree 400 depicted in FIG. 4 is merely an illustrative example of a possible coding tree and should thus not be construed as limiting the invention in any respect. 
【００２８】
The coding tree 400 illustrates an example of a coding tree containing frames arranged according to their respective required sequences to enable appropriate decoding of the frames.  The coding tree 400 includes multiple representations of frames that have been encoded using different reference frames.  As shown therein, a number of the multiple representations of the frames have been depicted with dashed lines to indicate that the encoder 204 has not encoded those frames and/or that those frames have not been stored in the data store 210.  As such, the amount of space required to store the frames and the predicted frame sequences in the data store 210 is substantially reduced as compared with the space required by the coding tree 300 depicted in FIG. 3.  In FIG. 3, when a request is received for a particular frame, any of a number of paths may be followed to supply the client with the appropriate frame sequences to enable the client to decode that particular frame.  In addition, each of the selected paths depicted in the coding tree 300 in FIG. 3 requires the same transmission costs.
【００２９】
With regard to FIG. 4, however, the transmission costs are path-dependent.  That is, some of the paths require a larger transmission cost depending upon which of the frames have already been sent to the client 220.  To illustrate this point further, assume that the client 220 is currently viewing frame P1(2,1) and has received frames P(1,1) and I(0,0).  In addition, assume that the client 220 has requested frame P(3,2).  As shown, the frame P(3,2) has not been encoded and stored following the path from frame P1(2,1) and P(1,1).  In this situation, the controller 208 seeks alternative routes through the coding tree 400 to enable appropriate decoding of the frame P(3,2).  
【００３０】
One of the routes that the controller 208 may select is re-routing A 402 and another route is re-routing B 404.  In re-routing A 402, the controller 208 needs to send frames P1(2,2) and P(3,2) since frames P(1,1) and I(0,0) have previously been sent to the client 220.  In re-routing B 404, the controller 208 is required to send frames P(1,2), P2(2,1), and P(3,2) because frame I(0,0) was previously sent to the client 220. It should be noted that the frame P2(2,1) differs from the frame P1(2,1) because they were created using different reference fames P(1,1,) and P(2,2), respectively.  In addition, the controller 208 is configured to select the re-routing path that requires the substantially minimal transmission cost.  In this example, the re-routing path 404 requires more transmission cost that the re-routing path 402 because path 404 requires transmission of an additional frame (P2(2,1)).
【００３１】
As such, the coding tree 400 with at least some of the frames removed or omitted and selection of a path that requires the least transmission cost as disclosed herein is one manner in which a client may be given the ability to interact with a streaming video, for instance, to change views in a multiview streaming video, while remaining within a storage cost constraint of the data store 210.   
【００３２】
Turning now to FIG. 5, there is shown a coding tree 500 in which a number of frames have been omitted or removed to thus reduce the storage space requirements of the encoded frames and in which a P-frame has been replaced with an I-frame, according to an example.  It should be understood that the coding tree 500 depicted in FIG. 5 is merely an illustrative example of a possible coding tree and should thus not be construed as limiting the invention in any respect. 
【００３３】
As shown in FIG. 5, multiple representations of frame P(2,2) have been omitted or removed from the coding tree 500 as denoted by the dashed lines and as compared with FIG. 4.  In addition, an I-frame I(2,2) has been placed in their previous position in the coding tree 500.  Although the I-frame I(2,2) may require greater storage costs and transmission costs than a single P-frame P(2,2), the use of the I-frame I(2,2) may result in reduced storage costs due to the reduction in the number of descendent P-frames from the single P-frames P(2,2) and the single P-frames P(2,2) themselves.  In addition, re-routing through the coding tree 500 may also require less transmission costs because the I-frame I(2,2) comprises an independent frame.  
【００３４】
To illustrate this point further, assume that the client 220 is currently viewing frame P1(2,1) and has received frames P(1,1) and I(0,0).  In addition, assume that the client 220 has requested frame P(3,2).  As shown, the frame P(3,2) has not been encoded and stored following the path from frame P1(2,1) and P(1,1).  In this situation, the controller 208 seeks alternative routes through the coding tree 500 to enable appropriate decoding of the frame P(3,2).  
【００３５】
One of the routes that the controller 208 may select is re-routing A 502 and another route is re-routing B 504.  In re-routing A 502, the controller 208 needs to send frames I(2,2) and P(3,2), since frame I(2,2) is an intra coded frame and thus does not require a reference frame.  In re-routing B 504, the controller 208 is required to send frames P(1,2), P2(2,1), and P(3,2) because frame I(0,0) was previously sent to the client 220.  In this example, there are thus two root nodes, frame I(0,0) and frame I(2,2).  The controller 208 is configured to determine the transmission costs associated with each of the re-routing paths 502 and 504 and to select the re-routing path that requires the minimum transmission cost.  In this example, the re-routing A 502 may not necessarily require the least transmission cost because an I-frame I(0,0) is communicated in place of multiple P-frames.
【００３６】
Examples of methods in which the system 200 may be employed to manage video data composed of a plurality of frames will now be described with respect to the following flow diagrams of the methods 600 and 700 respectively depicted in FIGS. 6 and 7.  It should be apparent to those of ordinary skill in the art that other steps may be added or existing steps may be removed, modified or rearranged without departing from the scopes of the methods 600 and 700. 
【００３７】
The descriptions of the methods 600 and 700 are made with reference to the system 200 illustrated in FIG. 2, and thus makes reference to the elements cited therein.  It should, however, be understood that the methods 600 and 700 are not limited to the elements set forth in the system 200.  Instead, it should be understood that the methods 600 and 700 may be practiced by a system having a different configuration than that set forth in the system 200.  
【００３８】
Some or all of the operations set forth in the methods 600 and 700 may be contained as utilities, programs, or subprograms, in any desired computer accessible medium.  In addition, the methods 600 and 700 may be embodied by computer programs, which may exist in a variety of forms both active and inactive.  For example, they may exist as software program(s) comprised of program instructions in source code, object code, executable code or other formats.  Any of the above may be embodied on a computer readable medium.  
【００３９】
Exemplary computer readable storage devices include conventional computer system RAM, ROM, EPROM, EEPROM, and magnetic or optical disks or tapes.  Concrete examples of the foregoing include distribution of the programs on a CD ROM or via Internet download.  It is therefore to be understood that any electronic device capable of executing the above-described functions may perform those functions enumerated above.
【００４０】
With reference first to FIG. 6, there is shown a flow diagram of a method 600 of managing multiview streaming video data composed of a plurality of frames, according to an example.  As discussed above, the video data may be managed to optimize a tradeoff between costs associated with transmitting the encoded frames of the video data and costs associated with storing the encoded frames along with predicted sequences of the frames.  In one regard, the frames are encoded to enable relatively efficient interactive control over content received by a client 220, such as, multiple views of a common scene.
【００４１】
At step 602, multiview streaming video data composed of a plurality of frames is obtained from, for instance, the data store 210 or other sources, such as, video cameras positioned at multiple locations and configured capture a common scene.  At step 604, the controller 208 identifies a storage constraint of the data store 210.  The storage constraint of the data store 210 may comprise a physical storage constraint, such as, the maximum storage capacity of the data store 210.  In addition, or alternatively, the storage constraint may comprise an imposed limit set for storage of the encoded frames in the data store 210.  
【００４２】
At step 606, the encoder 204 encodes multiple representations of at least one frame of the plurality of frames using different reference frames for each of the multiple representations, wherein the multiple representations correspond to a common time index and a common view.  In addition, at step 608, the controller 208 creates a coding tree containing the plurality of frames and the multiple representations in light of the storage constraint of the data store 210, for instance, as shown in Figures 4 and 5.  More particularly, the controller 208 creates the coding tree with at least one of the multiple representations omitted from the coding tree such that the coding tree requires less space than the storage constraint.  
【００４３】
According to an example, in determining which of the multiple representations to omit from the coding tree, the controller 208 is configured to implement an interaction model that describes a probability of a client 220 requesting a particular frame having a time instant (i+1) and view (k) after viewing a frame having a time instant (i) and a view (j).  The interaction model may determine the probability, for instance, based upon historical information pertaining to which frames have been selected following receipt of other reference frames.  In addition, the controller 208 is configured to arrange the plurality of frames in the coding tree based upon the interaction model, such that, those frames that have the least likelihood of being requested are omitted from the coding tree first to remain with the storage constraint of the data store. 
【００４４】
In creating the coding tree at step 608, the controller 208 may be further configured to calculate transmission costs associated with communicating the multiple representations of the at least one frame to a client 220.  In addition, the controller 208 may be configured to determine which of the P-frames, if any, to replace with I-frames to reduce the storage costs and to determine a combination of the P-frames and the I-frames that substantially minimizes the calculated transmission costs while remaining within the storage constraint of the data store 210.  
【００４５】
At step 610, the controller 208 stores the coding tree in the data store 210. 
【００４６】
Although the controller 208 has been described as creating the coding tree to omit particular frames from the coding tree, it should be understood that the controller 208 may remove the multiple representation(s) after being included in the coding tree in order to remain within the storage constraint of the data store 210.
【００４７】
Through implementation of the method 600, the controller 208 is configured to generate a coding tree similar to those depicted in FIGS. 4 and 5.  Thus, the controller 208 is configured to create a coding tree in which at least one of the multiple representations of the at least one frame corresponds to each view in each time index.  The coding tree created by the controller 208 may also enable more than one route through the coding tree to be available, to thus enable the client 220 to receive and appropriately decode selected frames from the coding tree.  An example of a manner in which the route through the coding tree may be selected to substantially minimize transmission costs is described with respect to FIG. 7. 
【００４８】
FIG. 7, more particularly, shows a flow diagram of a method 700 of managing video data composed of a plurality of frames in furtherance to the method 600, according to an example.  FIG. 7, more particularly, depicts steps for implementing the coding tree generated through the method 600 to substantially minimize transmission costs.  In effect, the method 700 is similar to the re-routing of frames and paths discussed above.
【００４９】
At step 702, the controller 208 communicates a first frame to a client 220.  At step 704, the controller 208 receives a request for a second frame from the client 220.  At step 706, the controller 208 determines that one of the multiple representations of the at least one frame is required for the second frame to be appropriately decoded at the client 220.  At step 708, the controller 208 determines transmission costs associated with communicating each of the multiple representations.  In addition, at step 710, the controller 208 communicates the one of the multiple representations of the at least one frame associated with a lowest transmission cost to the client 220.
【００５０】
An example of a manner in which the controller 208 may create the coding trees will now be described.  Generally speaking, the encoder 204 is configured to encode individual frames of a multiview video and to store the encoded individual frames in the data store 210.  The number of captured views at a given frame capturing instant is a constant K.  In other words, K different views of a scene are simultaneously captured periodically.  As discussed above, the different views of a given frame may be captured by multiple cameras or from multiple frames from frame buffers, for instance, from a virtual world representation.
【００５１】
With reference back to the redundant coding structure 400, it is assumed that the first frame-capturing instance of time index 0, denoted by I-frame I(0,0), is of a single view [K/２], and there are N frame-capturing instances in total.  The coding structure 400 is considered to be redundant because it contains multiple representations of the same frames, with each of the multiple representations having different reference frames.
【００５２】
FIG. 4 depicts two different views (K=2) and four frame-capturing instances (N=4).  In addition, there is one basic dependency tree with a root at I(0,0).  The redundant coding structure 400 illustrates that most of the frames are encoded into multiple representations as an I-frame and/or P-frame(s), each using a different reference frame.  Thus, when a client 220 requests a view K for a next time index i+1 after viewing a particular representation of a frame Fi,j of the time index i and view j, the controller 208 selects either an I-frame Ii+1,k if available, a P-frame Pi+1,k motion compensated using Fi,j, if available or an alternative P-frame Pi+1,k motion-compensated using a different reference frame F≠Fi,j.  In the last alternative, reference frame(s) including F must also be sent to the client 220 for correct decoding of Pi+1,k.
【００５３】
An original frame 
【００５４】
【数１】
2010093807.tif 000047
【００５５】
of time index I and view j may be encoded into numerous representations Fi,j and at least one representation as an I-frame Ii,j or a P-frame Pi,j(F) motion-compensated using different references F's.  For simplicity, a P-frame Pi,j(F) is only assumed to be motion-compensated using as reference an encoded frame F of time index i-1 and of view between max(1,j-1) and min(K,j+1).  
【００５６】
All of the encoded frames of a particular representation may be organized into a set of S basic dependency trees 
【００５７】
【数２】
2010093807.tif 000048
【００５８】
of different root frames.  A tree 
【００５９】
【数３】
2010093807.tif 000049
,
【００６０】
with a unique root I-frame 
【００６１】
【数４】
2010093807.tif 000050
,
【００６２】
is recursively define as follows:
【００６３】
【数５】
Equation (1):
2010093807.tif 000051
【００６４】
Equation (1) indicates that a tree T(F) rooted at a frame F is a frame set composed of frame F and (sub-)trees stemming from frame F.  A basic dependency tree is a tree with a root frame encoded as an I-frame.  Using tree set τ, a dependency path of a frame F, p(F), as the ordered set of all frames that proceed from the root I-frame to frame F in the basic dependency tree to which F belongs.  More particularly, the dependency path 
【００６５】
【数６】
2010093807.tif 000052
【００６６】
is an I-frame.
【００６７】
For practical purposes, it is assumed that each original frame 
【００６８】
【数７】
2010093807.tif 000053
【００６９】
cannot be encoded in more than M representations.  As such, the maximum number of nodes in a set of basic dependency trees is bounded by M N K.  Otherwise, a set of basic dependency trees may have an exponentially large number of nodes as a function of the original fames N K.For practical purposes, it is assumed that each original frame 
【００７０】
【数８】
2010093807.tif 000054
【００７１】
cannot be encoded in more than M representations.  As such, the maximum number of nodes in a set of basic dependency trees is bounded by M N K.  Otherwise, a set of basic dependency trees may have an exponentially large number of nodes as a function of the original fames N K.
【００７２】
The feasible space for the representation of the multiview video
【００７３】
【数９】
2010093807.tif 000055
【００７４】
may be defined as the set of basic dependency trees τ, as described in Equation (1), such that each original frame 
【００７５】
【数１０】
2010093807.tif 000056
【００７６】
Is encoded no more than M times but at least once, either as an I-frame or as a P-frame using an encoded Fi-1,K, for 
【００７７】
【数１１】
2010093807.tif 000057
.
【００７８】
Each chosen tree set 
【００７９】
【数１２】
2010093807.tif 000058
【００８０】
implies both a storage and transmission cost.  
【００８１】        An example of a manner in which the storage costs of a coding tree 400 stored in a data store 210 may be calculated will now be discussed.  For I-frames, let |Ii,j| denote the byte count of encoding original frame 
【００８２】
【数１３】
2010093807.tif 000059
【００８３】
as I-frame |Ii,j| = ∞ denotes the case when 
【００８４】
【数１４】
2010093807.tif 000060
【００８５】
was not encoded as an I-frame.  Similarly, for P-frames, let |Pi,j(F)| denote the byte count required to encode 
【００８６】
【数１５】
2010093807.tif 000061
【００８７】
as a P-frame using frame F for motion compensation. |Pi,j(F)| =∞ will denote the case when 
【００８８】
【数１６】
2010093807.tif 000062
【００８９】
was not encoded as a P-frame using F for motion compensation.  The storage cost of the representation τ, B(τ) may be written as:
【００９０】
【数１７】
Equation (2):
2010093807.tif 000063
.
【００９１】
In other words, the storage cost of a coding tree τ(F)  rooted at F is the size of the root frame |F| plus trees stemming from F.
【００９２】
An example of a manner in which frame-to-frame transmission costs may be calculated will now be discussed.  Assume that after viewing an encoded frame Fi,j, with dependency path p=p(Fi,j), the user chooses for viewing a frame at time i+1 of view k.  The controller 208 makes a deterministic decision on which encoded representation of the frame 
【００９３】
【数１８】
2010093807.tif 000064
.
【００９４】
to send to the client 220 based on Fi,j and k as follows.  First, if either encoded I-frame Ii+1,k or P-frame Pi+1,k (Fi,j)is available, the controller 208 may send either to the client 220 for decoding and display.  
【００９５】
If neither of these frames is available, the controller 208 finds an alternative P-frame Pi+1,k(F'), F≠Fi,j, for instance, a P-frame whose reference frame is not available at the client 220, with an alternative path q=p(F'), where either: i) paths p and q are non-overlapping paths; or ii) paths p and q overlap and first diverge after frame 
【００９６】
【数１９】
2010093807.tif 000065
.
【００９７】
of path q.  "Non-overlapping" here is intended to mean that motion-compensated Fi,j and F share no common decoding history, and "overlapping" is intended to mean that Fi,j and F share, and decoding history up until 
【００９８】
【数２０】
2010093807.tif 000066
.
【００９９】
In the first case, the controller 208 needs to send all of the frames in the dependency path     
【０１００】
【数２１】
2010093807.tif 000067
.
【０１０１】
and the P-frame Pi+1,k(F') itself for correct decoding of the frame with the time index i+1 and view k, in which case, the decoder 224 will display only the decoded P-frame Pi+1,k(F').  In the second case, the controller 208 needs to send sub-path 
【０１０２】
【数２２】
2010093807.tif 000068
.
【０１０３】
of path q and the P-frame Pi+1,k(F').  Thus, the total transmission cost of re-routing the dependency path from p to q, r(p,q), for each of these two cases is as follows:
【０１０４】
【数２３】
Equation (3):
2010093807.tif 000069
.
【０１０５】        There may be multiple alternative P-frames Pi+1,k(F') for different references F''s and alternative paths p(F')'s.  Thus, the controller 208 needs to find one with the lowest transmission cost φ(p,k) given dependency path p(Fi,j) and desired view k as follows:
【０１０６】
【数２４】
Equation (4):
2010093807.tif 000070
.
【０１０７】
The transmission cost for the user to choose view k after observing encoded frame Fi,jΦ(Fi,j,k), is then the minimum transmission cost of the possibly available I-frame, P-frame, and alternative P-frame(s):
【０１０８】
【数２５】
Equation (5):
2010093807.tif 000071
.
【０１０９】
An example of a manner in which the optimization of the storage costs and the transmission costs may be determined will now be discussed.  Let C(τ) denote the expected transmission cost of an N-frame interactive multiview streaming given a tree set τ.  After observing an encoded representation of original frame 
【０１１０】
【数２６】
2010093807.tif 000072
,
【０１１１】
assume that the user watches the next view k at the next time index i+1 with a probability αi,k(k), where Σkαi,k(k) = 1.  Using a derivation of frame-to-frame transmission cost from equation (5), the expected transmission cost C(τ) may be written as:
【０１１２】
【数２７】
Equation (6):
2010093807.tif 000073
,
【０１１３】
Equation (6) may efficiently be calculated in a recursive manner.  First, c(Fi,j) is a sum of at most three terms.  Second, φ(p(Fi,j),k) in Φ(Fi,j,k) has at most M references F'' (maximum M representations of Fi+1,k) to test.  For each reference F', rerouting cost r(p(Fi,j), p(F')) has at most N additions.  A first time computed c(Fi,j) is stored in a table so that a future recursive call to c(Fi,j) may simply return the calculated value.  The computation complexity of equation (6) is therefore M*N times the maximum number of nodes in tree set τ, or O(M2N2K).   
【０１１４】
The calculation of the storage cost may be simplified by instead of finding exact encoding costs of P-frames for all possible encoded representations of an original frame, assuming that Ii,j = rIi,j for any encoded representation Fi-1,k of an original frame 
【０１１５】
【数２８】
2010093807.tif 000074
.
【０１１６】
The interactive multiview streaming optimization, denoted as IMVS, may now be formalized as follows.  Given transition probabilities αi,j(k)'s and encoding rates rIi,j's and 
【０１１７】
【数２９】
2010093807.tif 000075
's
【０１１８】
for N frames of multiview video of K views, find the optimal tree set τ in a feasible space 
【０１１９】
【数３０】
2010093807.tif 000076
【０１２０】
that minimizes expected transmission cost C(τ) subject to a storage constraint 
【０１２１】
【数３１】
2010093807.tif 000077
,
【０１２２】
which may be written mathematically as:
【０１２３】
【数３２】
Equation (7):
2010093807.tif 000078
.
【０１２４】
An example of a manner in which approximation algorithms may be employed to optimize the IMVS will now be discussed.  As an initial solution τI, a minimum storage solution, one that requires a minimum storage space for all frames of all views, where each frame of each view is encoded only once is found.  Assuming that the size of an I-frame |Ii,j| Is larger than its P-frame counterpart |Pi,j(Fi-1,k)|, the minimum storage solution τI is the I-frame followed by all of the P-frames.  The minimum storage solution τI may be found mathematically as:
【０１２５】
【数３３】
Equation (8):
2010093807.tif 000079
.
【０１２６】
In equation (8), U(c)=1 if clause c is true and 0 otherwise.  In addition, equation (8) basically finds the smallest P-frame Pi,j(Fi-1,k) for each original frame 
【０１２７】
【数３４】
2010093807.tif 000080
.
【０１２８】
The next step is to find a locally optimal solution from τI.  This may be done iteratively by defining a series of augmentations and selecting among those the one that provides the greater decrease in a chosen cost function.  Examples of suitable augmentations include, changing a P-frame Pi,j(Fi-1,k) to an I-frame Ii,j, selecting a different reference frame F' for a P-frame Pi,j(Fi-1,k), adding a new I-frame Ii,j, and adding a new P-frame Pi,j(Fi-1,k).  The first two augmentations do not increase the number of representations of a given frame, while each of the next two augmentations increases the number of representations by one.  As such, the last two augmentations may be implemented when the number of representations of that frame is less than M.  The resulting solution will always have at least one representation of each frame of each view.  
【０１２９】
When a new I-frame Ii,j Is added to "complement" existing P-frame(s), a determination of which children of the existing P-frame(s) should switch parents to the newly added I-frame.  This may be done greedily, that is, a child of an existing P-frame is switched if by switching, the transmission cost goes down.  Similarly, optimum parent and child node selections are also performed greedily when adding a new P-frame.
【０１３０】
Given the augmentations discussed above, two algorithms with two calls functions are proposed.  The first proposal is a Lagrangian cost:
【０１３１】
【数３５】
Equation (9): 
2010093807.tif 000081
.
【０１３２】
In equation (9), λ = 0 or >0 is the Lagrangian multiplier.  At each iteration, the augmentation providing the greatest decrease in Lagrangian cost is selected.  In addition, the algorithm is stopped when no further cost reductions are possible given λ.  Moreover, tradeoffs between storage and transmission costs may be varied through use of different λ's.
【０１３３】
Alternatively, at each iteration the augmentation of all of the frames Fi,j's in a current solution τ may be selected such that the ratio of the decrease in transmission cost Δc(τ) to increase in storage cost ΔB(τ) Is the largest.  This algorithm may stop when the next such beneficial augmentation will exceed a storage constraint 
【０１３４】
【数３６】
2010093807.tif 000082
.
【０１３５】
FIG. 8 illustrates a block diagram of a computing apparatus 800 configured to implement or execute the methods 600 and 700 depicted in FIGS. 6 and 7, according to an example.  In this respect, the computing apparatus 800 may be used as a platform for executing one or more of the functions described hereinabove with respect to the server 202 depicted in FIG. 1.  
【０１３６】
The computing apparatus 800 includes a processor 802 that may implement or execute some or all of the steps described in the methods 600 and 700.  Commands and data from the processor 802 are communicated over a communication bus 804.  The computing apparatus 800 also includes a main memory 806, such as a random access memory (RAM), where the program code for the processor 802, may be executed during runtime, and a secondary memory 808.  The secondary memory 808 includes, for example, one or more hard disk drives 810 and/or a removable storage drive 812, representing a floppy diskette drive, a magnetic tape drive, a compact disk drive, etc., where a copy of the program code for the methods 600 and 700 may be stored. 
【０１３７】
The removable storage drive 812 reads from and/or writes to a removable storage unit 814 in a well-known manner.  User input and output devices may include a keyboard 816, a mouse 818, and a display 820.  A display adaptor 822 may interface with the communication bus 804 and the display 820 and may receive display data from the processor 802 and convert the display data into display commands for the display 820.  In addition, the processor(s) 802 may communicate over a network, for instance, the Internet, LAN, etc., through a network adaptor 824.
【０１３８】
It will be apparent to one of ordinary skill in the art that other known electronic components may be added or substituted in the computing apparatus 800.  It should also be apparent that one or more of the components depicted in FIG. 8 may be optional (for instance, user input devices, secondary memory, etc.).
【０１３９】
What has been described and illustrated herein is a preferred embodiment of the invention along with some of its variations.  The terms, descriptions and figures used herein are set forth by way of illustration only and are not meant as limitations.  Those skilled in the art will recognize that many variations are possible within the scope of the invention, which is intended to be defined by the following claims -- and their equivalents -- in which all terms are meant in their broadest reasonable sense unless otherwise indicated.
What is claimed is:
1.    A system for managing multiview streaming video data composed of a plurality of frames, said system comprising:
an encoder configured to encode multiple representations of at least one frame of the plurality of frames corresponding to multiple views using different reference frames for each of the multiple representations, wherein the multiple representations of the at least one frame correspond to a common time index and a common view; 
a controller configured to create a coding tree containing the plurality of frames and the multiple representations, wherein the coding tree depicts frame paths for each of the encoded plurality of frames that identify which of the frames comprise reference frames for other frames, and wherein the controller is further configured to maintain at least one of the multiple representations as one of a P-frame and an I-frame that corresponds to each view in each time instant;
a data store configured to store the coding tree, wherein the controller is further configured to identify a storage constraint of the data store and to omit at least one of the multiple representations from the coding tree to cause the plurality of frames stored in the data store to remain within the storage constraint.
2.    The system according to claim 1, wherein the controller is further configured to implement an interaction model that describes a probability of a client requesting a particular frame having a time instant (i+1) and view (k) after viewing a frame having a time instant (i) and a view (j) and to arrange the plurality of frames based upon the interaction model, such that, those frames that have the least likelihood of being requested are omitted from the coding tree first to remain with the storage constraint of the data store. 
3.    The system according to claim 1, wherein the multiple representations of the plurality of frames comprise P-frames, and wherein the controller is further configured to replace the P-frames of the multiple representations of the at least one frame with an I-frame and to store the I-frame as a node of the at least one frame in the coding tree to thereby reduce storage costs while enabling interactive multiview streaming.
4.    The system according to claim 1, wherein the controller is further configured to communicate a first frame to a client, to receive a request for a second frame from the client, to determine that one of the multiple representations of the at least one frame is required for the second frame to be appropriately decoded at the client, to determine transmission costs associated with communicating each of the multiple representations of the at least one frame along multiple paths through the coding tree for appropriately decoding the second frame at the client, and to communicate the one of the multiple representations of the at least one frame associated with a lowest transmission cost to the client.
5.    A method of managing multiview streaming video data composed of a plurality of frames, said method comprising:
identifying a storage constraint of a data store configured to store the multiview streaming video;
encoding multiple representations of at least one frame of the plurality of frames corresponding to multiple views using different reference frames for each of the multiple representations, wherein the multiple representations correspond to a common time index and a common view;
creating a coding tree containing the plurality of frames and the multiple representations in light of the storage constraint of the data store by omitting at least one of the multiple representations, wherein the coding tree maintains at least one of the multiple representations as one of a P-frame and an I-frame that corresponds to each view in each time instant; and
storing the coding tree in a data store. 
6.    The method according to claim 5, further comprising:
implementing an interaction model that describes a probability of a client requesting a particular frame having a time instant (i+1) and view (k) after viewing a frame having a time instant (i) and a view (j); and
wherein creating the coding tree further comprises arranging the plurality of frames based upon the interaction model, such that, those frames that have the least likelihood of being requested are omitted from the coding tree first to remain with the storage constraint of the data store. 
7.    The method according to claim 5, wherein the multiple representations of the plurality of frames comprise P-frames, said method further comprising:
replacing the P-frames of the multiple representations of the at least one frame with an I-frame; and
storing the I-frame as a node of the at least one frame in a coding tree to thereby reduce storage costs while enabling interactive multiview streaming.
8.    The method according to claim 5, further comprising: 
communicating a first frame to a client;
receiving a request for a second frame from the client;
determining that one of the multiple representations of the at least one frame is required for the second frame to be appropriately decoded at the client;
determining transmission costs associated with communicating each of the multiple representations along multiple paths through the coding tree for appropriately decoding the second frame at the client; and
communicating the one of the multiple representations associated with a lowest transmission cost to the client.
9.    A computer readable storage medium on which is embedded one or more computer programs, said one or more computer programs implementing a method of managing multiview streaming video data composed of a plurality of frames, said one or more computer programs comprising computer readable code for:
identifying a storage constraint of the data store configured to store the multiview streaming video;
encoding multiple representations of at least one frame of the plurality of frames corresponding to multiple views using different reference frames for each of the multiple versions, wherein the multiple representations correspond to a common time index and a common view;
creating a coding tree containing the plurality of frames and the multiple representations in light of the storage constraint of the data store by omitting at least one of the multiple representations, wherein the coding tree maintains at least one of the multiple representations as one of a P-frame and an I-frame that corresponds to each view in each time instant; and
storing the coding tree in a data store. 
10.    The computer readable storage medium according to claim 9, said one or more computer programs further comprising computer readable code for:
implementing an interaction model that describes a probability of a client requesting a particular frame having a time instant (i+1) and view (k) after viewing a frame having a time instant (i) and a view (j); and
wherein creating the coding tree further comprises arranging the plurality of frames based upon the interaction model, such that, those frames that have the least likelihood of being requested are omitted from the coding tree first to remain with the storage constraint of the data store. 
11.    The computer readable storage medium according to claim 9, said one or more computer programs further comprising computer readable code for:
replacing the P-frames of the multiple representations of the at least one frame with an I-frame; and
storing the I-frame as a node of the at least one frame in a coding tree to thereby reduce storage costs while enabling interactive multiview streaming.
12.    The computer readable storage medium according to claim 9, said one or more computer programs further comprising computer readable code for:
communicating a first frame to a client;
receiving a request for a second frame from the client;
determining that one of the multiple representations of the at least one frame is required for the second frame to be appropriately decoded at the client;
determining transmission costs associated with communicating each of the multiple representations along multiple paths through the coding tree for appropriately decoding the second frame at the client; and
communicating the one of the multiple representations associated with a lowest transmission cost to the client.
【要約】
ABSTRACT OF THE DISCLOSURE
A system for managing multiview streaming video data composed of a plurality of frames includes an encoder configured to encode multiple representations of at least one frame of the plurality of frames corresponding to multiple views using different reference frames for each of the multiple representations.  The system also includes a controller configured to create a coding tree containing the plurality of frames and the multiple representations.  The system further includes a data store configured to store the coding tree, wherein the controller is further configured to identify a storage constraint of the data store and to omit at least one of the multiple representations from the coding tree to cause the plurality of frames stored in the data store to remain within the storage constraint.
【図１】
2010093807.tif 000083
【図２】
2010093807.tif 000084
【図３】
2010093807.tif 000085
【図４】
2010093807.tif 000086
【図５】
2010093807.tif 000087
【図６】
2010093807.tif 000088
【図７】
2010093807.tif 000089
【図８】
2010093807.tif 000090