複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステム及び方法
【課題】複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステム及び方法を提供する。
【解決手段】複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステムは、複数のビューに対応する複数のフレームのうちの少なくとも１つのフレームの多重表現を、該多重表現ごとに異なる参照フレームを使用して符号化するように構成されるエンコーダを備える。本システムは、複数のフレーム及び多重表現を含む符号化木を作成するように構成されるコントローラも備える。本システムは、符号化木を記憶するように構成されるデータ記憶装置をさらに備える。コントローラは、データ記憶装置の記憶制約を特定すると共に、符号化木から多重表現のうちの少なくとも１つを省略して、データ記憶装置内に記憶される複数のフレームが記憶制約内に留まるようにするようにさらに構成される。
【解決手段】複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステムは、複数のビューに対応する複数のフレームのうちの少なくとも１つのフレームの多重表現を、該多重表現ごとに異なる参照フレームを使用して符号化するように構成されるエンコーダを備える。本システムは、複数のフレーム及び多重表現を含む符号化木を作成するように構成されるコントローラも備える。本システムは、符号化木を記憶するように構成されるデータ記憶装置をさらに備える。コントローラは、データ記憶装置の記憶制約を特定すると共に、符号化木から多重表現のうちの少なくとも１つを省略して、データ記憶装置内に記憶される複数のフレームが記憶制約内に留まるようにするようにさらに構成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施の形態は、複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステム及び方法に関する。
【背景技術】
【０００２】
ビデオは通常、イントラ符号化フレーム（Ｉフレーム）及びインターフレーム又は予測フレーム（Ｐフレーム）を使用して圧縮される。
Ｉフレームは、他のフレームからの予測無しで符号化されるため参照フレームを必要としないフレームである。
Ｐフレームは、参照フレームからの予測を使用するフレームである。
Ｉフレームはまたイントラマクロブロックのみを含み、一方、Ｐフレームはイントラマクロブロック又は予測マクロブロックのいずれかを含む。
Ｐフレームは、復号化されるために何らかの他の参照フレームを先行して復号化することを必要とし、多くの場合に、符号化のためにＩフレームよりも少ないビットを必要とする。
【０００３】
１つのシーンの複数のビュー（マルチビュー）が、同時に取り込まれ、Ｉフレーム及び／又はＰフレームを使用して符号化され、そしてユーザに送られるビデオアプリケーションがますます開発されるようになってきている。
これらのタイプのビデオアプリケーションでは、ユーザは、複数のビューをリアルタイムで切り替えることができ、したがって、従来のビデオアプリケーションを用いる場合よりも高いレベルの対話性を与えられる。
マルチビュービデオ符号化（ＭＶＣ）ツールのためのアプリケーションの中には、ユーザが再生のために、これらのビュー、又は潜在的には、実際に取り込まれたビデオデータから生成される仮想ビューのサブセットのみを選択することが可能なアプリケーションもある。
【０００４】
サーバにおいて符号化されてクライアントに通信されるＩフレーム（Ｉ（ｉ，ｊ））に基づく従来の符号化木１００の概略図を図１に示す。
ここで、ｉは時間インデックスであり、ｊはビューである。
この図内に示されているように、符号化木１００はＩフレームのみに基づいて符号化され、したがってＩフレームのうちの幾つかは、差分符号化のための参照フレームを必要とすることなく、他のＩフレームと比較して異なるビューを生成することができる。
しかしながら、図１に示されている符号化木１００は大きな送信コストを必要とする。
これは、Ｉフレームは通常、上述したようにＰフレームよりも数倍大きいためである。
【０００５】
ＭＶＣにおける最近の活動のうちの多くは画像取り込み及び圧縮に重点を置いてきた。
たとえば、ＭＶＣ標準化過程は、レート歪みが最適であるように、マルチビューシーケンスにおける全てのフレームを符号化するための新たな圧縮アルゴリズムの開発に集中してきた。
したがって、ストリーミングビデオのより効率的なマルチビュー制御をクライアントに提供することはあまり考慮されてこなかった。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】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）の予測フレームシーケンスの準備及び記憶に起因して、Ｉフレームの記憶と比較して指数関数的に増大することである。
記憶要件は、本明細書において後述する符号化木４００及び５００の使用を通じて低減される。
【００２５】
まず図４を参照すると、一実施例による、幾つかのフレームが省略又は除去されており、それによって符号化フレームの記憶空間要件が低減される符号化木４００が示されている。
図４に示されている符号化木４００は、あり得る符号化木の例示的な実施例に過ぎず、したがって、いかなる点においても本発明を限定するものと解釈されるべきではないことを理解されたい。
【００２６】
符号化木４００は、フレームの適切な復号化を可能にするために必要なそれぞれのシーケンスに従って配置される複数のフレームを含む符号化木の一実施例を示している。
符号化木４００は、異なる参照フレームを使用して符号化されたフレームの多重表現を含む。
図４内に示されているように、フレームの幾つかの多重表現が破線で示されており、エンコーダ２０４がこれらのフレームを符号化していないこと及び／又はこれらのフレームがデータ記憶装置２１０に記憶されていないことを示している。
したがって、データ記憶装置２１０内にフレーム及び予測フレームシーケンスを記憶するのに必要とされる空間の量は、図３に示されている符号化木３００によって必要とされる空間と比較して大幅に低減される。
図３では、要求が特定のフレームに関して受信されると、複数の経路のうちのいずれかを辿って、クライアントに適切なフレームシーケンスを提供し、クライアントがその特定のフレームを復号化することを可能にすることができる。
加えて、図３における符号化木３００に示されている選択される経路のそれぞれは、同じ送信コストを必要とする。
【００２７】
しかしながら、図４を参照すると、送信コストは経路に依存している。
すなわち、経路のうちの幾つかは、いずれのフレームが既にクライアント２２０に送信されているかによって、より大きな送信コストを必要とする。
この点をさらに示すために、クライアント２２０が現在Ｐ１（２，１）を見ており、フレームＰ（１，１）及びＩ（０，０）を受信済みであると仮定する。
加えて、クライアント２２０がフレームＰ（３，２）を要求済みであると仮定する。
図示されているように、フレームＰ１（２，１）及びＰ（１，１）からの経路を辿ると、フレームＰ（３，２）は符号化及び記憶されていない。
この状況において、コントローラ２０８は、フレームＰ（３，２）の適切な復号化を可能にするために、符号化木４００の全体にわたって代替のルートを捜し求める。
【００２８】
コントローラ２０８が選択し得るルートのうちの１つは、再ルーティングＡ４０２であり、別のルートは再ルーティングＢ４０４である。
再ルーティングＡ４０２では、コントローラ２０８は、フレームＰ（１，１）及びＩ（０，０）が既にクライアント２２０に送信されているため、フレームＰ１（２，２）及びＰ（３，２）を送信する必要がある。
再ルーティングＢ４０４では、コントローラ２０８は、フレームＩ（０，０）が既にクライアント２２０に送信されたため、フレームＰ（１，２）、Ｐ２（２，１）、及びＰ（３，２）を送信する必要がある。
フレームＰ２（２，１）はフレームＰ１（２，１）とは異なることに留意されたい。
これは、これらのフレームがそれぞれ、異なる参照フレームＰ（１，１）及びＰ（１，２）を使用して作成されたためである。
加えて、コントローラ２０８は、実質的に最小の送信コストを要求する再ルーティング経路を選択するように構成される。
この例では、再ルーティング経路４０４は、再ルーティング経路４０２よりも多くの送信コストを要求する。
これは、経路４０４がさらなるフレーム（Ｐ２（２，１））の送信を要求するためである。
【００２９】
したがって、フレームのうちの少なくとも幾つかが除去又は省略されており且つ本明細書に開示されるような最小送信コストを必要とする経路の選択が行われる符号化木４００は、データ記憶装置２１０の記憶コスト制約内に留まりながら、クライアントがストリーミングビデオと対話する、たとえばマルチビューストリーミングビデオ内のビューを変更することができる１つの方法である。
【００３０】
ここで図５を参照すると、一実施例による、幾つかのフレームが省略又は除去されており、それによって符号化フレームの記憶空間要件が低減され、且つＰフレームがＩフレームに置き換えられている符号化木５００が示されている。
図５に示されている符号化木５００は、あり得る符号化木の例示的な実施例に過ぎず、したがって、いかなる点においても本発明を限定するものと解釈されるべきではないことを理解されたい。
【００３１】
図５に図示されているように、破線によって示されているように且つ図４と比較すると、符号化木５００からフレームＰ（２，２）の多重表現が省略又は除去されている。
加えて、ＩフレームＩ（２，２）が、それらの以前の位置において符号化木５００内に置かれている。
ＩフレームＩ（２，２）は、単一のＰフレームＰ（２，２）よりも大きな記憶コスト及び送信コストを必要とし得るが、ＩフレームＩ（２，２）の使用は結果的に、単一のＰフレームＰ（２，２）からの派生Ｐフレーム及び単一のＰフレームＰ（２，２）自体の数の減少に起因して、記憶コストを低減することができる。
加えて、符号化木５００を通る再ルーティングも、ＩフレームＩ（２，２）が独立フレームを含むため、より小さい送信コストを必要とし得る。
【００３２】
この点をさらに示すために、クライアント２２０が現在Ｐ１（２，１）を見ており、フレームＰ（１，１）及びＩ（０，０）を受信済みであると仮定する。
加えて、クライアント２２０がフレームＰ（３，２）を要求済みであると仮定する。
図示されているように、フレームＰ１（２，１）及びＰ（１，１）からの経路を辿ると、フレームＰ（３，２）は符号化及び記憶されていない。
この状況において、コントローラ２０８は、フレームＰ（３，２）の適切な符号化を可能にするために、符号化木５００の全体にわたって代替のルートを探索する。
【００３３】
コントローラ２０８が選択し得るルートのうちの１つは、再ルーティングＡ５０２であり、別のルートは再ルーティングＢ５０４である。
再ルーティングＡ５０２では、コントローラ２０８は、フレームＩ（２，２）がイントラ符号化フレームであり、したがって参照フレームを必要としないため、フレームＩ（２，２）及びＰ（３，２）を送信する必要がある。
再ルーティングＢ５０４では、コントローラ２０８は、フレームＩ（０，０）が既にクライアント２２０に送信されたため、フレームＰ（１，２）、Ｐ２（２，１）、及びＰ（３，２）を送信する必要がある。
この例では、したがって、２つの根ノード、フレームＩ（０，０）及びフレームＩ（２，２）が存在する。
コントローラ２０８は、再ルーティング経路５０２及び５０４のそれぞれに関連付けられる送信コストを求めると共に、最小送信コストを必要とする再ルーティング経路を選択するように構成される。
この例では、再ルーティングＡ５０２は、必ずしも最小送信コストを必要としなくてもよい。
これは、ＩフレームＩ（２，２）が複数のＰフレームの代わりに通信されるためである。
【００３４】
これより、システム２００を使用して複数のフレームから成るビデオデータを管理することができる方法の例を、それぞれ図６及び図７に示されている方法６００及び７００の以下のフロー図を参照して説明する。
方法６００及び７００の範囲から逸脱することなく他のステップを追加することができるか又は既存のステップを除去、変更、若しくは再構成することができることが当業者には明らかであるはずである。
【００３５】
方法６００及び７００を図２に示されているシステム２００を参照して説明する。
したがって、該システムに挙げられている要素をこの説明において参照する。
しかしながら、方法６００及び７００は、システム２００に記載されている要素に限定されないことを理解されたい。
そうではなく、方法６００及び７００は、システム２００に記載されている構成とは異なる構成を有するシステムによって実践することができることを理解されたい。
【００３６】
方法６００及び７００に記載されている動作のうちの幾つか又は全ては、任意の所望のコンピュータアクセス可能媒体内に、ユーティリティ、プログラム、又はサブプログラムとして含むことができる。
加えて、方法６００及び７００は、アクティブ及び非アクティブの双方の様々な形態で存在することができるコンピュータプログラムによって具現化することができる。
たとえば、これらの方法は、ソースコード、オブジェクトコード、実行可能コード、又は他のフォーマットのプログラム命令から成るソフトウェアプログラム（複数可）として存在することができる。
上記のうちのいずれも、コンピュータ可読媒体上で具現化することができる。
【００３７】
例示的なコンピュータ可読記憶装置は、従来のコンピュータシステムＲＡＭ、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、及び磁気又は光ディスク又はテープを含む。
上記のものの具体的な例は、ＣＤ ＲＯＭ上での又はインターネットダウンロードを介するプログラムの配布を含む。
したがって、上記で説明した機能を実行することができる任意の電子装置が上記で列挙した機能を実施することができることを理解されたい。
【００３８】
図６を参照すると、一実施例による、複数のフレームから成るマルチビューストリーミングビデオデータを管理する方法６００のフロー図が示されている。
上述したように、ビデオデータは、ビデオデータの符号化フレームを送信することに関連付けられるコストと、フレームの予測シーケンスと共に符号化フレームを記憶することに関連付けられるコストとの間のトレードオフを最適化するように管理することができる。
或る点においては、フレームは、共通のシーンの複数のビューのような、クライアント２２０によって受信されるコンテンツに対する比較的効率的な対話的制御を可能にするように符号化される。
【００３９】
ステップ６０２において、複数のフレームから成るマルチビューストリーミングビデオデータを、たとえば、データ記憶装置２１０、又は、複数のロケーションに位置決めされると共に共通のシーンを取り込むように構成される複数のビデオカメラのような他のソースから取得する。
ステップ６０４において、コントローラ２０８は、データ記憶装置２１０の記憶制約を特定する。
データ記憶装置２１０の記憶制約は、データ記憶装置２１０の最大記憶容量のような物理的記憶制約を含む場合がある。
付加的に又は代替的に、記憶制約は、データ記憶装置２１０内での符号化フレームの記憶に関して設定される、課せられる制限を含む場合がある。
【００４０】
ステップ６０６において、エンコーダ２０４は、複数のフレームのうちの少なくとも１つのフレームの多重表現を、該多重表現ごとに異なる参照フレームを使用して符号化する。
ここで、多重表現は共通の時間インデックス及び共通のビューに対応する。
加えて、ステップ６０８において、コントローラ２０８は、データ記憶装置２１０の記憶制約を考慮して、たとえば図４及び図５に図示されているような、複数のフレーム及び多重表現を含む符号化木を作成する。
より詳細には、コントローラ２０８は、符号化木が記憶要件よりも少ない空間を必要とするように多重表現のうちの少なくとも１つが符号化木から省略されている符号化木を作成する。
【００４１】
一実施例によれば、多重表現のうちのいずれを符号化木から省略するかの決定において、コントローラ２０８は、クライアント２２０が時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装するように構成される。
対話モデルは、たとえば他の参照フレームの受信に続いていずれのフレームが選択されたかに関する履歴情報に基づいてこの確率を求めることができる。
加えて、コントローラ２０８は、データ記憶装置の記憶制約内に留まるために、まず、要求される可能性が最も少ないフレームが符号化木から省略されるように、対話モデルに基づいて符号化木内の複数のフレームを配置するように構成される。
【００４２】
ステップ６０８において符号化木を作成する際、コントローラ２０８は、少なくとも１つのフレームの多重表現をクライアント２２０に通信することに関連付けられる送信コストを計算するようにさらに構成することができる。
加えて、コントローラ２０８は、記憶コストを削減するために、存在する場合にはいずれのＰフレームをＩフレームで置き換えるかを決定すると共に、データ記憶装置２１０の記憶制約内に留まりながら、計算される送信コストを実質的に最小化する送信Ｐフレーム及びＩフレームの組み合わせを決定するように構成することができる。
【００４３】
ステップ６１０において、コントローラ２０８はデータ記憶装置２１０内に符号化木を記憶する。
【００４４】
コントローラ２０８を、特定のフレームを省略するように符号化木を作成するものとして説明したが、コントローラ２０８は、データ記憶装置２１０の記憶制約内に留まるために、多重表現（複数可）を、それらが符号化木内に含まれた後に除去することができることを理解されたい。
【００４５】
方法６００の実施を通じて、コントローラ２０８は、図４及び図５に示されている符号化木と同様の符号化木を生成するように構成される。
したがって、コントローラ２０８は、少なくとも１つのフレームの多重表現のうちの少なくとも１つが各時間インデックスにおける各ビューに対応する符号化木を作成するように構成される。
コントローラ２０８によって作成される符号化木はまた、符号化木を通る２つ以上のルートが利用可能となることを可能にし、それによって、クライアント２２０が、符号化木から選択されたフレームを受信すると共に適切に復号化することを可能にすることができる。
符号化木を通るルートを選択して送信コストを実質的に最小化することができる方法の一例を図７を参照して説明する。
【００４６】
より詳細には図７は、一実施例による、方法６００に対する促進のための、複数のフレームから成るビデオデータを管理する方法７００のフロー図を示している。
より詳細には図７は、送信コストを実質的に最小化するように、方法６００を通じて生成された符号化木を実装するステップを示している。
実際には方法７００は、上述したフレーム及び経路の再ルーティングと同様である。
【００４７】
ステップ７０２において、コントローラ２０８は第１のフレームをクライアント２２０に通信する。
ステップ７０４において、コントローラ２０８は、第２のフレームを求める要求をクライアント２２０から受信する。
ステップ７０６において、コントローラ２０８は、第２のフレームがクライアント２２０において適切に復号化されるために、少なくとも１つのフレームの多重表現のうちの１つが必要とされると判断する。
ステップ７０８において、コントローラ２０８は、多重表現のそれぞれを通信することに関連付けられる送信コストを求める。
加えて、ステップ７１０において、コントローラ２０８は、最低送信コストに関連付けられる少なくとも１つのフレームの多重表現のうちの１つをクライアント２２０に送信する。
【００４８】
これより、コントローラ２０８が符号化木を作成することができる方法の一例を説明する。
大まかに述べると、エンコーダ２０４は、マルチビュービデオの個別のフレームを符号化すると共に、データ記憶装置２１０内に個別の符号化フレームを記憶するように構成される。
所与のフレーム取り込み時刻における取り込まれたビューの数は定数Ｋである。
換言すると、シーンのＫ個の異なるビューが同時に周期的に取り込まれる。
上述したように、所与のフレームの異なるビューは、複数のカメラによって、又は、フレームバッファからの複数のフレームから、たとえば仮想世界表現から取り込むことができる。
【００４９】
冗長符号化構造４００を再び参照して、ＩフレームＩ（０，０）によって示される、時間インデックス０の第１のフレーム取り込みインスタンスは単一のビュー［Ｋ／２］のものであり、合計でＮ個のフレーム取り込みインスタンスが存在すると仮定する。
符号化構造４００は、該符号化構造が同じフレームの多重表現を含み、多重表現のそれぞれが異なる参照フレームを有するため、冗長とみなされる。
【００５０】
図４は異なる２つのビュー（Ｋ＝２）と、４つのフレーム取り込みインスタンス（Ｎ＝４）を示している。
加えて、根がＩ（０，０）にある１つの基本依存木が存在する。
冗長符号化構造４００は、フレームのほとんどが、それぞれが異なる参照フレームを使用してＩフレーム及び／又はＰフレーム（複数可）として多重表現に符号化されることを示している。
したがって、クライアント２２０が時間インデックスｉ及びビューｊのフレームＦｉ，ｊの特定の表現を見た後に次の時間インデックスｉ＋１のビューｋを要求する場合、コントローラ２０８は、利用可能であればＩフレームＩｉ＋１，ｋ、利用可能であればＦｉ，ｊを使用して動き補償されたＰフレームＰｉ＋１，ｋ、又は異なる参照フレームＦ≠Ｆｉ，ｊを使用して動き補償された代替のＰフレームＰｉ＋１，ｋのうちのいずれかを選択する。
この最後の代替フレームでは、Ｆを含む参照フレーム（複数可）も、Ｐｉ＋１，ｋの正確な復号化のためにクライアント２２０に送信しなければならない。
【００５１】
時間インデックスｉ及びビューｊの元のフレーム
【００５２】
【数１】
【００５３】
は、多数の表現Ｆｉ，ｊに、また、ＩフレームＩｉ，ｊとして又は複数の異なる参照Ｆを使用して動き補償されたＰフレームPｉ，ｊ（Ｆ）として少なくとも１つの表現に符号化することができる。
単純にするために、ＰフレームPｉ，ｊ（Ｆ）を、時間インデックスｉ−１、及びｍａｘ（１，ｊ−１）とｍｉｎ（Ｋ，ｊ＋１）との間のビューの符号化フレームＦを参照として使用して動き補償されるものとしてのみ仮定する。
【００５４】
特定の表現の符号化フレームの全ては、異なる根フレームのＳ個の基本依存木から成る集合
【００５５】
【数２】
【００５６】
に編成することができる。
固有の根Ｉフレーム
【００５７】
【数４】
【００５８】
を有する木
【００５９】
【数３】
【００６０】
は以下のように再帰的に定義される。
【００６１】
【数５】
式（１）
【００６２】
式（１）は、フレームＦを根とする木Ｔ（Ｆ）が、フレームＦと、フレームＦから分岐する（部分）木とから成るフレーム集合であることを示す。
基本依存木は、Ｉフレームとして符号化される根フレームを有する木である。
木集合τを使用して、フレームＦの依存経路ｐ（Ｆ）を、Ｆが属する基本依存木において根ＩフレームからフレームＦまで進む全てのフレームの順序集合とする。
より詳細には、依存経路
【００６３】
【数６】
【００６４】
はＩフレームである。
【００６５】
実際的な目的のために、各元フレーム
【００６６】
【数７】
【００６７】
をＭ個を超える表現に符号化することはできないと仮定する。
したがって、基本依存木の集合内の最大ノード数はＭＮＫによって制限される。
そうでない場合、基本依存木の集合は、元フレームＮＫの関数として指数関数的に大きいノード数を有し得る。実際的な目的のために、各元フレーム
【００６８】
【数８】
【００６９】
をＭ個を超える表現に符号化することはできないと仮定する。
したがって、基本依存木の集合内の最大ノード数はＭＮＫによって制限される。
そうでない場合、基本依存木の集合は、元フレームＮＫの関数として指数関数的に大きいノード数を有し得る。
【００７０】
マルチビュービデオの表現のための実現可能な空間
【００７１】
【数９】
【００７２】
は、各元フレーム
【００７３】
【数１０】
【００７４】
が、Ｉフレームとして又は
【００７５】
【数１１】
【００７６】
の場合に符号化フレームＦｉ−１，Ｋを使用してＰフレームとして、Ｍ回を超えないように、しかし少なくとも１回符号化されるように、式（１）に記載されているように、基本依存木の集合τとして定義することができる。
それぞれの選択された木集合
【００７７】
【数１２】
【００７８】
は記憶コスト及び送信コストの双方を暗示する。
【００７９】
これより、データ記憶装置２１０内に記憶される符号化木４００の記憶コストを計算することができる方法の一例を論じる。
Ｉフレームに関して、｜Ｉｉ，ｊ｜は、Ｉフレームとして元のフレーム
【００８０】
【数１３】
【００８１】
を符号化することのバイト数を表すものとする。
｜Ｉｉ，ｊ｜＝∞は、
【００８２】
【数１４】
【００８３】
がＩフレームとして符号化されなかった場合を表す。
同様に、Ｐフレームに関して、｜Ｐｉ，ｊ（Ｆ）｜は、フレームＦを動き補償のために使用して
【００８４】
【数１５】
【００８５】
をＰフレームとして符号化するのに必要とされるバイト数を表す。
｜Ｐｉ，ｊ（Ｆ）｜＝∞は、
【００８６】
【数１６】
【００８７】
が、Ｆを動き補償のために使用してＰフレームとして符号化されなかった場合を表す。
表現τの記憶コストＢ（τ）は以下のように記述することができる。
【００８８】
【数１７】
式（２）
【００８９】
換言すると、Ｆを根とする符号化木τ（Ｆ）を符号化する記憶コストは、根フレームのサイズ｜Ｆ｜にＦから分岐する木を加算したものである。
【００９０】
これより、フレーム間送信コストを計算することができる方法の一例を論じる。
ユーザが、依存経路ｐ＝ｐ（Ｆｉ，ｊ）を有する符号化フレームＦｉ，ｊを見た後、ビューｋの時刻ｉ＋１におけるフレームを見ることを選択すると仮定する。
コントローラ２０８は、以下のように、Ｆｉ，ｊ及びｋに基づいてクライアント２２０に送信するフレーム
【００９１】
【数１８】
【００９２】
の符号化表現を決定論的に判断する。
まず、符号化ＩフレームＩｉ＋１，ｋ又はＰフレームＰｉ＋１，ｋ（Ｆｉ，ｊ）のいずれかが利用可能である場合、コントローラ２０８は、復号化及び表示のためにクライアント２２０にそれらのうちのいずれかを送信することができる。
【００９３】
これらのフレームのうちのいずれもが利用可能でない場合、コントローラ２０８は、代替のＰフレームＰｉ＋１，ｋ（Ｆ'），Ｆ'≠Ｆｉ，ｊ、たとえばその参照フレームがクライアント２２０において利用可能でないＰフレームを、代替の経路ｑ＝ｐ（Ｆ'）を用いて求める。
ここで、ｉ）経路ｐ及びｑは重なり合わない経路であるか、又はｉｉ）経路ｐ及びｑは重なり合い、経路ｑのフレーム
【００９４】
【数１９】
【００９５】
後に初めて分かれる。
ここで、「重なり合わない」とは、動き補償されたＦｉ，ｊ及びＦが共通の復号化履歴を共有しないことを意味するように意図されている。
そして「重なり合う」とは、Ｆｉ，ｊ及びＦが
【００９６】
【数２０】
【００９７】
まで復号化履歴を共有することを意味するように意図されている。
この第１の場合では、コントローラ２０８は、時間インデックスｉ＋１及びビューｋを有するフレームの正確な復号化のために、依存経路
【００９８】
【数２１】
【００９９】
における全てのフレームとＰフレームＰｉ＋１，ｋ（Ｆ'）自体とを送信する必要があり、この場合、デコーダ２２４は復号化ＰフレームＰｉ＋１，ｋ（Ｆ'）のみを表示する。
第２の場合では、コントローラ２０８は、経路ｑの部分経路
【０１００】
【数２２】
【０１０１】
とＰフレームＰｉ＋１，ｋ（Ｆ'）とを送信する必要がある。
したがって、これらの２つの場合のそれぞれに関して、ｐからｑへ依存経路を再ルーティングする総送信コストｒ（ｐ，ｑ）は以下のようになる。
【０１０２】
【数２３】
式（３）
【０１０３】
異なる複数の参照Ｆ'及び代替の経路ｐ（Ｆ'）に関して複数の代替のＰフレームＰｉ＋１，ｋ（Ｆ'）が存在し得る。
したがって、コントローラ２０８は、以下のように、依存経路ｐ（Ｆｉ，ｊ）及び所望のビューｋを所与として、最低送信コストφ（ｐ，ｋ）を有する経路を求める必要がある。
【０１０４】
【数２４】
式（４）
【０１０５】
したがって、ユーザが符号化フレームＦｉ，ｊ，Φ（Ｆｉ，ｊ，ｋ）の観察後にビューｋを選択することに関する送信コストは、場合によっては利用可能なIフレーム、Pフレーム、及び代替のＰフレーム（複数可）の最小送信コストである。
【０１０６】
【数２５】
式（５）
【０１０７】
これより、記憶コスト及び送信コストの最適化を求めることができる方法の一例を説明する。
Ｃ（τ）は、木集合τを所与とした、Ｎフレーム対話的マルチビューストリーミングの予想送信コストを表すものとする。
元のフレーム
【０１０８】
【数２６】
【０１０９】
の符号化表現の観察後、ユーザが、確率αｉ，ｊ（ｋ）で次の時間インデックスｉ＋１において次のビューｋを見ると仮定する。
ここで、Σｋαｉ，ｊ（ｋ）＝１である。
式（５）からのフレーム間送信コストの導出を使用して、予想送信コストＣ（τ）を以下のように記述することができる。
【０１１０】
【数２７】
式（６）
【０１１１】
式（６）は、再帰的に効率的に計算することができる。
第１に、ｃ（Ｆｉ，ｊ）は最大で３項の総和である。
第２に、Φ（Ｆｉ，ｊ，ｋ）におけるφ（ｐ（Ｆｉ，ｊ），ｋ）は、試験用に最大でＭ個の参照Ｆ'（Ｆｉ＋１，ｋの最大Ｍ個の表現）を有する。
参照Ｆ'ごとに、再ルーティングコストｒ（ｐ（Ｆｉ，ｊ），ｐ（Ｆ'））は最大でＮ回の加算を有する。
最初に計算されたｃ（Ｆｉ，ｊ）は、後のｃ（Ｆｉ，ｊ）に対する再帰呼び出しが単に計算された値を返すことができるように、テーブルに記憶される。
式（６）の計算量はしたがって、木集合τ内の最大ノード数のＭ×Ｎ倍であり、すなわちＯ（Ｍ２Ｎ２Ｋ）である。
【０１１２】
記憶コストの計算は、元のフレームの全ての可能な符号化表現のＰフレームの正確な符号化コストを求める代わりに、Ｉｉ，ｊ＝ｒＩｉ，ｊであること、且つ、元のフレーム
【０１１３】
【数２８】
【０１１４】
の任意の符号化表現Ｆｉ−１，ｋに関してＰｉ，ｊ（Ｆｉ−１，ｋ）＝ｒＰｉ，ｊ（ｋ）であることを仮定することによって単純化することができる。
ここで、ＩＭＶＳとして表される対話的マルチビューストリーミング最適化を以下のように形式化することができる。
Ｋ個のビューから成るマルチビュービデオのＮ個のフレームの場合の推移確率αｉ，ｊ（ｋ）及び符号化レートｒＩｉ，ｊ及び
【０１１５】
【数２９】
【０１１６】
を所与として、記憶制約
【０１１７】
【数３１】
【０１１８】
下で予想送信コストＣ（τ）を最小化する実現可能空間
【０１１９】
【数３０】
【０１２０】
において最適な木集合τを求める。
これは以下のように数学的に記述することができる。
【０１２１】
【数３２】
式（７）
【０１２２】
これより、近似アルゴリズムを使用してＩＭＶＳを最適化することができる方法の一例を論じる。
初期解τＩとして、各ビューの各フレームが１回だけ符号化される、全てのビューの全てのフレームのための最小記憶空間を必要とする最小記憶解を求める。
Ｉフレーム｜Ｉｉ，ｊ｜のサイズがその対応するＰフレームのサイズ｜Ｐｉ，ｊ（Ｆｉ−１，ｋ）｜よりも大きいと仮定すると、最小記憶解τＩは全てのＰフレームが後続するＩフレームである。
最小記憶解τＩは以下のように数学的に求めることができる。
【０１２３】
【数３３】
式（８）
【０１２４】
式（８）において、節（clause）ｃが真である場合Ｕ（ｃ）＝１であり、そうでない場合は０である。
加えて、式（８）は基本的に、元のフレーム
【０１２５】
【数３４】
【０１２６】
ごとに最小ＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）を求める。
【０１２７】
次のステップは、τＩから局所最適解を求めることである。
これは、一連の拡大（augmentation）を定義すると共に、選択されたコスト関数においてより大きな低減を提供する拡大をこれらのうちから選択することによって反復的に行うことができる。
適切な拡大の例は、ＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）をＩフレームＩｉ，ｊに変更すること、異なる参照フレームＦ'をＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）のために選択すること、新たなＩフレームＩｉ，ｊを追加すること、及び新たなＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）を追加することを含む。
最初の２つの拡大は所与のフレームの表現の数を増加させず、一方、次の２つの拡大のそれぞれは表現の数を１だけ増加させる。
したがって、最後の２つの拡大は、そのフレームの表現の数がＭより小さい場合に実施することができる。
結果的に得られる解は常に、各ビューの各フレームの少なくとも１つの表現を有する。
【０１２８】
新たなＩフレームＩｉ，ｊを加えて既存のＰフレーム（複数可）を「補償する」場合、既存のＰフレーム（複数可）のいずれの子が親を新たに加えられたＩフレームに切り替えるべきかが判断される。
これは貪欲に行われ得る。
すなわち、切り替えによって送信コストが低下する場合、既存のＰフレームの子が切り替えられる。
同様に、新たなＰフレームを追加する場合の最適な親及び子ノード選択も貪欲に実施される。
【０１２９】
上述した拡大を所与として、２つの呼び出し関数を有する２つのアルゴリズムを提案する。
第１の提案はラグランジュコストである。
【０１３０】
【数３５】
式（９）
【０１３１】
式（９）において、λ≧０はラグランジュ乗数である。
各反復において、ラグランジュコストにおいて最大低減を提供する拡大を選択する。
加えて、本アルゴリズムは、λを所与としてさらなるコスト低減が可能でないときに停止する。
さらに、記憶コストと送信コストとの間のトレードオフは、複数の異なるλの使用を通じて変化することができる。
【０１３２】
代替的に、各反復において、現在解τにおける全てのフレームＦｉ，ｊの拡大は、送信コストの低減ΔＣ（τ）と、記憶コストの増加ΔＢ（τ）との比が最大であるように選択することができる。
このアルゴリズムは、次のこのような有益な拡大が記憶制約
【０１３３】
【数３６】
【０１３４】
を超える場合に停止することができる。
【０１３５】
図８は、一実施例による、図６及び図７に示されている方法６００及び７００を実装又は実行するように構成される計算装置８００のブロック図を示している。
この点において、計算装置８００は、図１に示されているサーバ２０２に関して上記で説明した機能のうちの１つ又は複数を実行するためのプラットフォームとして使用することができる。
【０１３６】
計算装置８００は、方法６００及び７００において説明されたステップのうちの幾つかまたは全てを実装又は実行することができるプロセッサ８０２を備える。
プロセッサ８０２からのコマンド及びデータは通信バス８０４を介して通信される。
計算装置８００はまた、ランダムアクセスメモリ（ＲＡＭ）のようなメインメモリ８０６を備える。
該メインメモリにおいて、プロセッサ８０２に対するプログラムコードが実行時間中に実行されることができる。
また該計算装置は２次メモリ８０８を備える。
２次メモリ８０８は、たとえば、フロッピー（登録商標）ディスクドライブ、磁気テープドライブ、コンパクトディスクドライブ等を表す１つ又は複数のハードディスクドライブ８１０及び／又は着脱可能記憶ドライブ８１２を含み、これらにおいて、方法６００及び７００のプログラムコードのコピーを記憶することができる。
【０１３７】
着脱可能記憶ドライブ８１２は、既知の方法で着脱可能記憶ユニット８１４との間で読み書きを行う。
ユーザ入力及び出力装置は、キーボード８１６、マウス８１８、及びディスプレイ８２０を含むことができる。
ディスプレイアダプタ８２２は、通信バス８０４及びディスプレイ８２０とインタフェースすることができ、プロセッサ８０２から表示データを受信して、該表示データをディスプレイ８２０に対する表示コマンドに変換することができる。
加えて、プロセッサ（複数可）８０２は、ネットワークアダプタ８２４を通じてネットワーク、たとえばインターネット、ＬＡＮ等を介して通信することができる。
【０１３８】
当業者には、計算装置８００において他の既知の電子部品を追加するか又は代わりに用いることができることが明らかであろう。
図８に示されている部品のうちの１つ又は複数は任意選択とすることができる（たとえば、ユーザ入力装置、２次メモリ等）ことも明らかであるはずである。
【０１３９】
本明細書において説明及び例示してきたものは、本発明の好ましい一実施形態、及びその変形形態のうちの幾つかである。
本明細書において使用される用語、説明、及び図面は、例示のためにのみ記載され、限定を意味するものではない。
当業者は、別途指示されない限り全ての用語がその最も広い適切な意味を有するように意図されている以下の特許請求の範囲及びその均等物によって規定されるように意図されている本発明の範囲内で多数の変形形態が可能であることを認識するであろう。
【符号の説明】
【０１４０】
１００・・・符号化木，
２００・・・システム，
２０２・・・サーバ，
２０４・・・エンコーダ，
２０６，２２２・・・送受信機，
２０８・・・コントローラ，
２１０・・・データ記憶装置，
２２０・・・クライアント，
２２４・・・デコーダ，
２２６・・・インタフェース，
２２８・・・入力，
３００・・・符号化木，
３０２・・・基本Ｉフレーム，
４００・・・符号化木，
４０２・・・再ルーティングＡ，
４０４・・・再ルーティングＢ，
５００・・・符号化木，
５０２・・・再ルーティングＡ，
５０４・・・再ルーティングＢ，
８００・・・計算装置，
８０２・・・プロセッサ，
８０４・・・通信バス，
８０６・・・メインメモリ，
８０８・・・２次メモリ，
８１０・・・ハードディスクドライブ，
８１２・・・着脱可能記憶装置，
８１４・・・着脱可能記憶ユニット，
８１６・・・キーボード，
８１８・・・マウス，
８２０・・・ディスプレイ，
８２２・・・ディスプレイアダプタ，
８２４・・・ネットワークアダプタ，
【技術分野】
【０００１】
本発明の実施の形態は、複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステム及び方法に関する。
【背景技術】
【０００２】
ビデオは通常、イントラ符号化フレーム（Ｉフレーム）及びインターフレーム又は予測フレーム（Ｐフレーム）を使用して圧縮される。
Ｉフレームは、他のフレームからの予測無しで符号化されるため参照フレームを必要としないフレームである。
Ｐフレームは、参照フレームからの予測を使用するフレームである。
Ｉフレームはまたイントラマクロブロックのみを含み、一方、Ｐフレームはイントラマクロブロック又は予測マクロブロックのいずれかを含む。
Ｐフレームは、復号化されるために何らかの他の参照フレームを先行して復号化することを必要とし、多くの場合に、符号化のためにＩフレームよりも少ないビットを必要とする。
【０００３】
１つのシーンの複数のビュー（マルチビュー）が、同時に取り込まれ、Ｉフレーム及び／又はＰフレームを使用して符号化され、そしてユーザに送られるビデオアプリケーションがますます開発されるようになってきている。
これらのタイプのビデオアプリケーションでは、ユーザは、複数のビューをリアルタイムで切り替えることができ、したがって、従来のビデオアプリケーションを用いる場合よりも高いレベルの対話性を与えられる。
マルチビュービデオ符号化（ＭＶＣ）ツールのためのアプリケーションの中には、ユーザが再生のために、これらのビュー、又は潜在的には、実際に取り込まれたビデオデータから生成される仮想ビューのサブセットのみを選択することが可能なアプリケーションもある。
【０００４】
サーバにおいて符号化されてクライアントに通信されるＩフレーム（Ｉ（ｉ，ｊ））に基づく従来の符号化木１００の概略図を図１に示す。
ここで、ｉは時間インデックスであり、ｊはビューである。
この図内に示されているように、符号化木１００はＩフレームのみに基づいて符号化され、したがってＩフレームのうちの幾つかは、差分符号化のための参照フレームを必要とすることなく、他のＩフレームと比較して異なるビューを生成することができる。
しかしながら、図１に示されている符号化木１００は大きな送信コストを必要とする。
これは、Ｉフレームは通常、上述したようにＰフレームよりも数倍大きいためである。
【０００５】
ＭＶＣにおける最近の活動のうちの多くは画像取り込み及び圧縮に重点を置いてきた。
たとえば、ＭＶＣ標準化過程は、レート歪みが最適であるように、マルチビューシーケンスにおける全てのフレームを符号化するための新たな圧縮アルゴリズムの開発に集中してきた。
したがって、ストリーミングビデオのより効率的なマルチビュー制御をクライアントに提供することはあまり考慮されてこなかった。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】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）の予測フレームシーケンスの準備及び記憶に起因して、Ｉフレームの記憶と比較して指数関数的に増大することである。
記憶要件は、本明細書において後述する符号化木４００及び５００の使用を通じて低減される。
【００２５】
まず図４を参照すると、一実施例による、幾つかのフレームが省略又は除去されており、それによって符号化フレームの記憶空間要件が低減される符号化木４００が示されている。
図４に示されている符号化木４００は、あり得る符号化木の例示的な実施例に過ぎず、したがって、いかなる点においても本発明を限定するものと解釈されるべきではないことを理解されたい。
【００２６】
符号化木４００は、フレームの適切な復号化を可能にするために必要なそれぞれのシーケンスに従って配置される複数のフレームを含む符号化木の一実施例を示している。
符号化木４００は、異なる参照フレームを使用して符号化されたフレームの多重表現を含む。
図４内に示されているように、フレームの幾つかの多重表現が破線で示されており、エンコーダ２０４がこれらのフレームを符号化していないこと及び／又はこれらのフレームがデータ記憶装置２１０に記憶されていないことを示している。
したがって、データ記憶装置２１０内にフレーム及び予測フレームシーケンスを記憶するのに必要とされる空間の量は、図３に示されている符号化木３００によって必要とされる空間と比較して大幅に低減される。
図３では、要求が特定のフレームに関して受信されると、複数の経路のうちのいずれかを辿って、クライアントに適切なフレームシーケンスを提供し、クライアントがその特定のフレームを復号化することを可能にすることができる。
加えて、図３における符号化木３００に示されている選択される経路のそれぞれは、同じ送信コストを必要とする。
【００２７】
しかしながら、図４を参照すると、送信コストは経路に依存している。
すなわち、経路のうちの幾つかは、いずれのフレームが既にクライアント２２０に送信されているかによって、より大きな送信コストを必要とする。
この点をさらに示すために、クライアント２２０が現在Ｐ１（２，１）を見ており、フレームＰ（１，１）及びＩ（０，０）を受信済みであると仮定する。
加えて、クライアント２２０がフレームＰ（３，２）を要求済みであると仮定する。
図示されているように、フレームＰ１（２，１）及びＰ（１，１）からの経路を辿ると、フレームＰ（３，２）は符号化及び記憶されていない。
この状況において、コントローラ２０８は、フレームＰ（３，２）の適切な復号化を可能にするために、符号化木４００の全体にわたって代替のルートを捜し求める。
【００２８】
コントローラ２０８が選択し得るルートのうちの１つは、再ルーティングＡ４０２であり、別のルートは再ルーティングＢ４０４である。
再ルーティングＡ４０２では、コントローラ２０８は、フレームＰ（１，１）及びＩ（０，０）が既にクライアント２２０に送信されているため、フレームＰ１（２，２）及びＰ（３，２）を送信する必要がある。
再ルーティングＢ４０４では、コントローラ２０８は、フレームＩ（０，０）が既にクライアント２２０に送信されたため、フレームＰ（１，２）、Ｐ２（２，１）、及びＰ（３，２）を送信する必要がある。
フレームＰ２（２，１）はフレームＰ１（２，１）とは異なることに留意されたい。
これは、これらのフレームがそれぞれ、異なる参照フレームＰ（１，１）及びＰ（１，２）を使用して作成されたためである。
加えて、コントローラ２０８は、実質的に最小の送信コストを要求する再ルーティング経路を選択するように構成される。
この例では、再ルーティング経路４０４は、再ルーティング経路４０２よりも多くの送信コストを要求する。
これは、経路４０４がさらなるフレーム（Ｐ２（２，１））の送信を要求するためである。
【００２９】
したがって、フレームのうちの少なくとも幾つかが除去又は省略されており且つ本明細書に開示されるような最小送信コストを必要とする経路の選択が行われる符号化木４００は、データ記憶装置２１０の記憶コスト制約内に留まりながら、クライアントがストリーミングビデオと対話する、たとえばマルチビューストリーミングビデオ内のビューを変更することができる１つの方法である。
【００３０】
ここで図５を参照すると、一実施例による、幾つかのフレームが省略又は除去されており、それによって符号化フレームの記憶空間要件が低減され、且つＰフレームがＩフレームに置き換えられている符号化木５００が示されている。
図５に示されている符号化木５００は、あり得る符号化木の例示的な実施例に過ぎず、したがって、いかなる点においても本発明を限定するものと解釈されるべきではないことを理解されたい。
【００３１】
図５に図示されているように、破線によって示されているように且つ図４と比較すると、符号化木５００からフレームＰ（２，２）の多重表現が省略又は除去されている。
加えて、ＩフレームＩ（２，２）が、それらの以前の位置において符号化木５００内に置かれている。
ＩフレームＩ（２，２）は、単一のＰフレームＰ（２，２）よりも大きな記憶コスト及び送信コストを必要とし得るが、ＩフレームＩ（２，２）の使用は結果的に、単一のＰフレームＰ（２，２）からの派生Ｐフレーム及び単一のＰフレームＰ（２，２）自体の数の減少に起因して、記憶コストを低減することができる。
加えて、符号化木５００を通る再ルーティングも、ＩフレームＩ（２，２）が独立フレームを含むため、より小さい送信コストを必要とし得る。
【００３２】
この点をさらに示すために、クライアント２２０が現在Ｐ１（２，１）を見ており、フレームＰ（１，１）及びＩ（０，０）を受信済みであると仮定する。
加えて、クライアント２２０がフレームＰ（３，２）を要求済みであると仮定する。
図示されているように、フレームＰ１（２，１）及びＰ（１，１）からの経路を辿ると、フレームＰ（３，２）は符号化及び記憶されていない。
この状況において、コントローラ２０８は、フレームＰ（３，２）の適切な符号化を可能にするために、符号化木５００の全体にわたって代替のルートを探索する。
【００３３】
コントローラ２０８が選択し得るルートのうちの１つは、再ルーティングＡ５０２であり、別のルートは再ルーティングＢ５０４である。
再ルーティングＡ５０２では、コントローラ２０８は、フレームＩ（２，２）がイントラ符号化フレームであり、したがって参照フレームを必要としないため、フレームＩ（２，２）及びＰ（３，２）を送信する必要がある。
再ルーティングＢ５０４では、コントローラ２０８は、フレームＩ（０，０）が既にクライアント２２０に送信されたため、フレームＰ（１，２）、Ｐ２（２，１）、及びＰ（３，２）を送信する必要がある。
この例では、したがって、２つの根ノード、フレームＩ（０，０）及びフレームＩ（２，２）が存在する。
コントローラ２０８は、再ルーティング経路５０２及び５０４のそれぞれに関連付けられる送信コストを求めると共に、最小送信コストを必要とする再ルーティング経路を選択するように構成される。
この例では、再ルーティングＡ５０２は、必ずしも最小送信コストを必要としなくてもよい。
これは、ＩフレームＩ（２，２）が複数のＰフレームの代わりに通信されるためである。
【００３４】
これより、システム２００を使用して複数のフレームから成るビデオデータを管理することができる方法の例を、それぞれ図６及び図７に示されている方法６００及び７００の以下のフロー図を参照して説明する。
方法６００及び７００の範囲から逸脱することなく他のステップを追加することができるか又は既存のステップを除去、変更、若しくは再構成することができることが当業者には明らかであるはずである。
【００３５】
方法６００及び７００を図２に示されているシステム２００を参照して説明する。
したがって、該システムに挙げられている要素をこの説明において参照する。
しかしながら、方法６００及び７００は、システム２００に記載されている要素に限定されないことを理解されたい。
そうではなく、方法６００及び７００は、システム２００に記載されている構成とは異なる構成を有するシステムによって実践することができることを理解されたい。
【００３６】
方法６００及び７００に記載されている動作のうちの幾つか又は全ては、任意の所望のコンピュータアクセス可能媒体内に、ユーティリティ、プログラム、又はサブプログラムとして含むことができる。
加えて、方法６００及び７００は、アクティブ及び非アクティブの双方の様々な形態で存在することができるコンピュータプログラムによって具現化することができる。
たとえば、これらの方法は、ソースコード、オブジェクトコード、実行可能コード、又は他のフォーマットのプログラム命令から成るソフトウェアプログラム（複数可）として存在することができる。
上記のうちのいずれも、コンピュータ可読媒体上で具現化することができる。
【００３７】
例示的なコンピュータ可読記憶装置は、従来のコンピュータシステムＲＡＭ、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、及び磁気又は光ディスク又はテープを含む。
上記のものの具体的な例は、ＣＤ ＲＯＭ上での又はインターネットダウンロードを介するプログラムの配布を含む。
したがって、上記で説明した機能を実行することができる任意の電子装置が上記で列挙した機能を実施することができることを理解されたい。
【００３８】
図６を参照すると、一実施例による、複数のフレームから成るマルチビューストリーミングビデオデータを管理する方法６００のフロー図が示されている。
上述したように、ビデオデータは、ビデオデータの符号化フレームを送信することに関連付けられるコストと、フレームの予測シーケンスと共に符号化フレームを記憶することに関連付けられるコストとの間のトレードオフを最適化するように管理することができる。
或る点においては、フレームは、共通のシーンの複数のビューのような、クライアント２２０によって受信されるコンテンツに対する比較的効率的な対話的制御を可能にするように符号化される。
【００３９】
ステップ６０２において、複数のフレームから成るマルチビューストリーミングビデオデータを、たとえば、データ記憶装置２１０、又は、複数のロケーションに位置決めされると共に共通のシーンを取り込むように構成される複数のビデオカメラのような他のソースから取得する。
ステップ６０４において、コントローラ２０８は、データ記憶装置２１０の記憶制約を特定する。
データ記憶装置２１０の記憶制約は、データ記憶装置２１０の最大記憶容量のような物理的記憶制約を含む場合がある。
付加的に又は代替的に、記憶制約は、データ記憶装置２１０内での符号化フレームの記憶に関して設定される、課せられる制限を含む場合がある。
【００４０】
ステップ６０６において、エンコーダ２０４は、複数のフレームのうちの少なくとも１つのフレームの多重表現を、該多重表現ごとに異なる参照フレームを使用して符号化する。
ここで、多重表現は共通の時間インデックス及び共通のビューに対応する。
加えて、ステップ６０８において、コントローラ２０８は、データ記憶装置２１０の記憶制約を考慮して、たとえば図４及び図５に図示されているような、複数のフレーム及び多重表現を含む符号化木を作成する。
より詳細には、コントローラ２０８は、符号化木が記憶要件よりも少ない空間を必要とするように多重表現のうちの少なくとも１つが符号化木から省略されている符号化木を作成する。
【００４１】
一実施例によれば、多重表現のうちのいずれを符号化木から省略するかの決定において、コントローラ２０８は、クライアント２２０が時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装するように構成される。
対話モデルは、たとえば他の参照フレームの受信に続いていずれのフレームが選択されたかに関する履歴情報に基づいてこの確率を求めることができる。
加えて、コントローラ２０８は、データ記憶装置の記憶制約内に留まるために、まず、要求される可能性が最も少ないフレームが符号化木から省略されるように、対話モデルに基づいて符号化木内の複数のフレームを配置するように構成される。
【００４２】
ステップ６０８において符号化木を作成する際、コントローラ２０８は、少なくとも１つのフレームの多重表現をクライアント２２０に通信することに関連付けられる送信コストを計算するようにさらに構成することができる。
加えて、コントローラ２０８は、記憶コストを削減するために、存在する場合にはいずれのＰフレームをＩフレームで置き換えるかを決定すると共に、データ記憶装置２１０の記憶制約内に留まりながら、計算される送信コストを実質的に最小化する送信Ｐフレーム及びＩフレームの組み合わせを決定するように構成することができる。
【００４３】
ステップ６１０において、コントローラ２０８はデータ記憶装置２１０内に符号化木を記憶する。
【００４４】
コントローラ２０８を、特定のフレームを省略するように符号化木を作成するものとして説明したが、コントローラ２０８は、データ記憶装置２１０の記憶制約内に留まるために、多重表現（複数可）を、それらが符号化木内に含まれた後に除去することができることを理解されたい。
【００４５】
方法６００の実施を通じて、コントローラ２０８は、図４及び図５に示されている符号化木と同様の符号化木を生成するように構成される。
したがって、コントローラ２０８は、少なくとも１つのフレームの多重表現のうちの少なくとも１つが各時間インデックスにおける各ビューに対応する符号化木を作成するように構成される。
コントローラ２０８によって作成される符号化木はまた、符号化木を通る２つ以上のルートが利用可能となることを可能にし、それによって、クライアント２２０が、符号化木から選択されたフレームを受信すると共に適切に復号化することを可能にすることができる。
符号化木を通るルートを選択して送信コストを実質的に最小化することができる方法の一例を図７を参照して説明する。
【００４６】
より詳細には図７は、一実施例による、方法６００に対する促進のための、複数のフレームから成るビデオデータを管理する方法７００のフロー図を示している。
より詳細には図７は、送信コストを実質的に最小化するように、方法６００を通じて生成された符号化木を実装するステップを示している。
実際には方法７００は、上述したフレーム及び経路の再ルーティングと同様である。
【００４７】
ステップ７０２において、コントローラ２０８は第１のフレームをクライアント２２０に通信する。
ステップ７０４において、コントローラ２０８は、第２のフレームを求める要求をクライアント２２０から受信する。
ステップ７０６において、コントローラ２０８は、第２のフレームがクライアント２２０において適切に復号化されるために、少なくとも１つのフレームの多重表現のうちの１つが必要とされると判断する。
ステップ７０８において、コントローラ２０８は、多重表現のそれぞれを通信することに関連付けられる送信コストを求める。
加えて、ステップ７１０において、コントローラ２０８は、最低送信コストに関連付けられる少なくとも１つのフレームの多重表現のうちの１つをクライアント２２０に送信する。
【００４８】
これより、コントローラ２０８が符号化木を作成することができる方法の一例を説明する。
大まかに述べると、エンコーダ２０４は、マルチビュービデオの個別のフレームを符号化すると共に、データ記憶装置２１０内に個別の符号化フレームを記憶するように構成される。
所与のフレーム取り込み時刻における取り込まれたビューの数は定数Ｋである。
換言すると、シーンのＫ個の異なるビューが同時に周期的に取り込まれる。
上述したように、所与のフレームの異なるビューは、複数のカメラによって、又は、フレームバッファからの複数のフレームから、たとえば仮想世界表現から取り込むことができる。
【００４９】
冗長符号化構造４００を再び参照して、ＩフレームＩ（０，０）によって示される、時間インデックス０の第１のフレーム取り込みインスタンスは単一のビュー［Ｋ／２］のものであり、合計でＮ個のフレーム取り込みインスタンスが存在すると仮定する。
符号化構造４００は、該符号化構造が同じフレームの多重表現を含み、多重表現のそれぞれが異なる参照フレームを有するため、冗長とみなされる。
【００５０】
図４は異なる２つのビュー（Ｋ＝２）と、４つのフレーム取り込みインスタンス（Ｎ＝４）を示している。
加えて、根がＩ（０，０）にある１つの基本依存木が存在する。
冗長符号化構造４００は、フレームのほとんどが、それぞれが異なる参照フレームを使用してＩフレーム及び／又はＰフレーム（複数可）として多重表現に符号化されることを示している。
したがって、クライアント２２０が時間インデックスｉ及びビューｊのフレームＦｉ，ｊの特定の表現を見た後に次の時間インデックスｉ＋１のビューｋを要求する場合、コントローラ２０８は、利用可能であればＩフレームＩｉ＋１，ｋ、利用可能であればＦｉ，ｊを使用して動き補償されたＰフレームＰｉ＋１，ｋ、又は異なる参照フレームＦ≠Ｆｉ，ｊを使用して動き補償された代替のＰフレームＰｉ＋１，ｋのうちのいずれかを選択する。
この最後の代替フレームでは、Ｆを含む参照フレーム（複数可）も、Ｐｉ＋１，ｋの正確な復号化のためにクライアント２２０に送信しなければならない。
【００５１】
時間インデックスｉ及びビューｊの元のフレーム
【００５２】
【数１】
【００５３】
は、多数の表現Ｆｉ，ｊに、また、ＩフレームＩｉ，ｊとして又は複数の異なる参照Ｆを使用して動き補償されたＰフレームPｉ，ｊ（Ｆ）として少なくとも１つの表現に符号化することができる。
単純にするために、ＰフレームPｉ，ｊ（Ｆ）を、時間インデックスｉ−１、及びｍａｘ（１，ｊ−１）とｍｉｎ（Ｋ，ｊ＋１）との間のビューの符号化フレームＦを参照として使用して動き補償されるものとしてのみ仮定する。
【００５４】
特定の表現の符号化フレームの全ては、異なる根フレームのＳ個の基本依存木から成る集合
【００５５】
【数２】
【００５６】
に編成することができる。
固有の根Ｉフレーム
【００５７】
【数４】
【００５８】
を有する木
【００５９】
【数３】
【００６０】
は以下のように再帰的に定義される。
【００６１】
【数５】
式（１）
【００６２】
式（１）は、フレームＦを根とする木Ｔ（Ｆ）が、フレームＦと、フレームＦから分岐する（部分）木とから成るフレーム集合であることを示す。
基本依存木は、Ｉフレームとして符号化される根フレームを有する木である。
木集合τを使用して、フレームＦの依存経路ｐ（Ｆ）を、Ｆが属する基本依存木において根ＩフレームからフレームＦまで進む全てのフレームの順序集合とする。
より詳細には、依存経路
【００６３】
【数６】
【００６４】
はＩフレームである。
【００６５】
実際的な目的のために、各元フレーム
【００６６】
【数７】
【００６７】
をＭ個を超える表現に符号化することはできないと仮定する。
したがって、基本依存木の集合内の最大ノード数はＭＮＫによって制限される。
そうでない場合、基本依存木の集合は、元フレームＮＫの関数として指数関数的に大きいノード数を有し得る。実際的な目的のために、各元フレーム
【００６８】
【数８】
【００６９】
をＭ個を超える表現に符号化することはできないと仮定する。
したがって、基本依存木の集合内の最大ノード数はＭＮＫによって制限される。
そうでない場合、基本依存木の集合は、元フレームＮＫの関数として指数関数的に大きいノード数を有し得る。
【００７０】
マルチビュービデオの表現のための実現可能な空間
【００７１】
【数９】
【００７２】
は、各元フレーム
【００７３】
【数１０】
【００７４】
が、Ｉフレームとして又は
【００７５】
【数１１】
【００７６】
の場合に符号化フレームＦｉ−１，Ｋを使用してＰフレームとして、Ｍ回を超えないように、しかし少なくとも１回符号化されるように、式（１）に記載されているように、基本依存木の集合τとして定義することができる。
それぞれの選択された木集合
【００７７】
【数１２】
【００７８】
は記憶コスト及び送信コストの双方を暗示する。
【００７９】
これより、データ記憶装置２１０内に記憶される符号化木４００の記憶コストを計算することができる方法の一例を論じる。
Ｉフレームに関して、｜Ｉｉ，ｊ｜は、Ｉフレームとして元のフレーム
【００８０】
【数１３】
【００８１】
を符号化することのバイト数を表すものとする。
｜Ｉｉ，ｊ｜＝∞は、
【００８２】
【数１４】
【００８３】
がＩフレームとして符号化されなかった場合を表す。
同様に、Ｐフレームに関して、｜Ｐｉ，ｊ（Ｆ）｜は、フレームＦを動き補償のために使用して
【００８４】
【数１５】
【００８５】
をＰフレームとして符号化するのに必要とされるバイト数を表す。
｜Ｐｉ，ｊ（Ｆ）｜＝∞は、
【００８６】
【数１６】
【００８７】
が、Ｆを動き補償のために使用してＰフレームとして符号化されなかった場合を表す。
表現τの記憶コストＢ（τ）は以下のように記述することができる。
【００８８】
【数１７】
式（２）
【００８９】
換言すると、Ｆを根とする符号化木τ（Ｆ）を符号化する記憶コストは、根フレームのサイズ｜Ｆ｜にＦから分岐する木を加算したものである。
【００９０】
これより、フレーム間送信コストを計算することができる方法の一例を論じる。
ユーザが、依存経路ｐ＝ｐ（Ｆｉ，ｊ）を有する符号化フレームＦｉ，ｊを見た後、ビューｋの時刻ｉ＋１におけるフレームを見ることを選択すると仮定する。
コントローラ２０８は、以下のように、Ｆｉ，ｊ及びｋに基づいてクライアント２２０に送信するフレーム
【００９１】
【数１８】
【００９２】
の符号化表現を決定論的に判断する。
まず、符号化ＩフレームＩｉ＋１，ｋ又はＰフレームＰｉ＋１，ｋ（Ｆｉ，ｊ）のいずれかが利用可能である場合、コントローラ２０８は、復号化及び表示のためにクライアント２２０にそれらのうちのいずれかを送信することができる。
【００９３】
これらのフレームのうちのいずれもが利用可能でない場合、コントローラ２０８は、代替のＰフレームＰｉ＋１，ｋ（Ｆ'），Ｆ'≠Ｆｉ，ｊ、たとえばその参照フレームがクライアント２２０において利用可能でないＰフレームを、代替の経路ｑ＝ｐ（Ｆ'）を用いて求める。
ここで、ｉ）経路ｐ及びｑは重なり合わない経路であるか、又はｉｉ）経路ｐ及びｑは重なり合い、経路ｑのフレーム
【００９４】
【数１９】
【００９５】
後に初めて分かれる。
ここで、「重なり合わない」とは、動き補償されたＦｉ，ｊ及びＦが共通の復号化履歴を共有しないことを意味するように意図されている。
そして「重なり合う」とは、Ｆｉ，ｊ及びＦが
【００９６】
【数２０】
【００９７】
まで復号化履歴を共有することを意味するように意図されている。
この第１の場合では、コントローラ２０８は、時間インデックスｉ＋１及びビューｋを有するフレームの正確な復号化のために、依存経路
【００９８】
【数２１】
【００９９】
における全てのフレームとＰフレームＰｉ＋１，ｋ（Ｆ'）自体とを送信する必要があり、この場合、デコーダ２２４は復号化ＰフレームＰｉ＋１，ｋ（Ｆ'）のみを表示する。
第２の場合では、コントローラ２０８は、経路ｑの部分経路
【０１００】
【数２２】
【０１０１】
とＰフレームＰｉ＋１，ｋ（Ｆ'）とを送信する必要がある。
したがって、これらの２つの場合のそれぞれに関して、ｐからｑへ依存経路を再ルーティングする総送信コストｒ（ｐ，ｑ）は以下のようになる。
【０１０２】
【数２３】
式（３）
【０１０３】
異なる複数の参照Ｆ'及び代替の経路ｐ（Ｆ'）に関して複数の代替のＰフレームＰｉ＋１，ｋ（Ｆ'）が存在し得る。
したがって、コントローラ２０８は、以下のように、依存経路ｐ（Ｆｉ，ｊ）及び所望のビューｋを所与として、最低送信コストφ（ｐ，ｋ）を有する経路を求める必要がある。
【０１０４】
【数２４】
式（４）
【０１０５】
したがって、ユーザが符号化フレームＦｉ，ｊ，Φ（Ｆｉ，ｊ，ｋ）の観察後にビューｋを選択することに関する送信コストは、場合によっては利用可能なIフレーム、Pフレーム、及び代替のＰフレーム（複数可）の最小送信コストである。
【０１０６】
【数２５】
式（５）
【０１０７】
これより、記憶コスト及び送信コストの最適化を求めることができる方法の一例を説明する。
Ｃ（τ）は、木集合τを所与とした、Ｎフレーム対話的マルチビューストリーミングの予想送信コストを表すものとする。
元のフレーム
【０１０８】
【数２６】
【０１０９】
の符号化表現の観察後、ユーザが、確率αｉ，ｊ（ｋ）で次の時間インデックスｉ＋１において次のビューｋを見ると仮定する。
ここで、Σｋαｉ，ｊ（ｋ）＝１である。
式（５）からのフレーム間送信コストの導出を使用して、予想送信コストＣ（τ）を以下のように記述することができる。
【０１１０】
【数２７】
式（６）
【０１１１】
式（６）は、再帰的に効率的に計算することができる。
第１に、ｃ（Ｆｉ，ｊ）は最大で３項の総和である。
第２に、Φ（Ｆｉ，ｊ，ｋ）におけるφ（ｐ（Ｆｉ，ｊ），ｋ）は、試験用に最大でＭ個の参照Ｆ'（Ｆｉ＋１，ｋの最大Ｍ個の表現）を有する。
参照Ｆ'ごとに、再ルーティングコストｒ（ｐ（Ｆｉ，ｊ），ｐ（Ｆ'））は最大でＮ回の加算を有する。
最初に計算されたｃ（Ｆｉ，ｊ）は、後のｃ（Ｆｉ，ｊ）に対する再帰呼び出しが単に計算された値を返すことができるように、テーブルに記憶される。
式（６）の計算量はしたがって、木集合τ内の最大ノード数のＭ×Ｎ倍であり、すなわちＯ（Ｍ２Ｎ２Ｋ）である。
【０１１２】
記憶コストの計算は、元のフレームの全ての可能な符号化表現のＰフレームの正確な符号化コストを求める代わりに、Ｉｉ，ｊ＝ｒＩｉ，ｊであること、且つ、元のフレーム
【０１１３】
【数２８】
【０１１４】
の任意の符号化表現Ｆｉ−１，ｋに関してＰｉ，ｊ（Ｆｉ−１，ｋ）＝ｒＰｉ，ｊ（ｋ）であることを仮定することによって単純化することができる。
ここで、ＩＭＶＳとして表される対話的マルチビューストリーミング最適化を以下のように形式化することができる。
Ｋ個のビューから成るマルチビュービデオのＮ個のフレームの場合の推移確率αｉ，ｊ（ｋ）及び符号化レートｒＩｉ，ｊ及び
【０１１５】
【数２９】
【０１１６】
を所与として、記憶制約
【０１１７】
【数３１】
【０１１８】
下で予想送信コストＣ（τ）を最小化する実現可能空間
【０１１９】
【数３０】
【０１２０】
において最適な木集合τを求める。
これは以下のように数学的に記述することができる。
【０１２１】
【数３２】
式（７）
【０１２２】
これより、近似アルゴリズムを使用してＩＭＶＳを最適化することができる方法の一例を論じる。
初期解τＩとして、各ビューの各フレームが１回だけ符号化される、全てのビューの全てのフレームのための最小記憶空間を必要とする最小記憶解を求める。
Ｉフレーム｜Ｉｉ，ｊ｜のサイズがその対応するＰフレームのサイズ｜Ｐｉ，ｊ（Ｆｉ−１，ｋ）｜よりも大きいと仮定すると、最小記憶解τＩは全てのＰフレームが後続するＩフレームである。
最小記憶解τＩは以下のように数学的に求めることができる。
【０１２３】
【数３３】
式（８）
【０１２４】
式（８）において、節（clause）ｃが真である場合Ｕ（ｃ）＝１であり、そうでない場合は０である。
加えて、式（８）は基本的に、元のフレーム
【０１２５】
【数３４】
【０１２６】
ごとに最小ＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）を求める。
【０１２７】
次のステップは、τＩから局所最適解を求めることである。
これは、一連の拡大（augmentation）を定義すると共に、選択されたコスト関数においてより大きな低減を提供する拡大をこれらのうちから選択することによって反復的に行うことができる。
適切な拡大の例は、ＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）をＩフレームＩｉ，ｊに変更すること、異なる参照フレームＦ'をＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）のために選択すること、新たなＩフレームＩｉ，ｊを追加すること、及び新たなＰフレームＰｉ，ｊ（Ｆｉ−１，ｋ）を追加することを含む。
最初の２つの拡大は所与のフレームの表現の数を増加させず、一方、次の２つの拡大のそれぞれは表現の数を１だけ増加させる。
したがって、最後の２つの拡大は、そのフレームの表現の数がＭより小さい場合に実施することができる。
結果的に得られる解は常に、各ビューの各フレームの少なくとも１つの表現を有する。
【０１２８】
新たなＩフレームＩｉ，ｊを加えて既存のＰフレーム（複数可）を「補償する」場合、既存のＰフレーム（複数可）のいずれの子が親を新たに加えられたＩフレームに切り替えるべきかが判断される。
これは貪欲に行われ得る。
すなわち、切り替えによって送信コストが低下する場合、既存のＰフレームの子が切り替えられる。
同様に、新たなＰフレームを追加する場合の最適な親及び子ノード選択も貪欲に実施される。
【０１２９】
上述した拡大を所与として、２つの呼び出し関数を有する２つのアルゴリズムを提案する。
第１の提案はラグランジュコストである。
【０１３０】
【数３５】
式（９）
【０１３１】
式（９）において、λ≧０はラグランジュ乗数である。
各反復において、ラグランジュコストにおいて最大低減を提供する拡大を選択する。
加えて、本アルゴリズムは、λを所与としてさらなるコスト低減が可能でないときに停止する。
さらに、記憶コストと送信コストとの間のトレードオフは、複数の異なるλの使用を通じて変化することができる。
【０１３２】
代替的に、各反復において、現在解τにおける全てのフレームＦｉ，ｊの拡大は、送信コストの低減ΔＣ（τ）と、記憶コストの増加ΔＢ（τ）との比が最大であるように選択することができる。
このアルゴリズムは、次のこのような有益な拡大が記憶制約
【０１３３】
【数３６】
【０１３４】
を超える場合に停止することができる。
【０１３５】
図８は、一実施例による、図６及び図７に示されている方法６００及び７００を実装又は実行するように構成される計算装置８００のブロック図を示している。
この点において、計算装置８００は、図１に示されているサーバ２０２に関して上記で説明した機能のうちの１つ又は複数を実行するためのプラットフォームとして使用することができる。
【０１３６】
計算装置８００は、方法６００及び７００において説明されたステップのうちの幾つかまたは全てを実装又は実行することができるプロセッサ８０２を備える。
プロセッサ８０２からのコマンド及びデータは通信バス８０４を介して通信される。
計算装置８００はまた、ランダムアクセスメモリ（ＲＡＭ）のようなメインメモリ８０６を備える。
該メインメモリにおいて、プロセッサ８０２に対するプログラムコードが実行時間中に実行されることができる。
また該計算装置は２次メモリ８０８を備える。
２次メモリ８０８は、たとえば、フロッピー（登録商標）ディスクドライブ、磁気テープドライブ、コンパクトディスクドライブ等を表す１つ又は複数のハードディスクドライブ８１０及び／又は着脱可能記憶ドライブ８１２を含み、これらにおいて、方法６００及び７００のプログラムコードのコピーを記憶することができる。
【０１３７】
着脱可能記憶ドライブ８１２は、既知の方法で着脱可能記憶ユニット８１４との間で読み書きを行う。
ユーザ入力及び出力装置は、キーボード８１６、マウス８１８、及びディスプレイ８２０を含むことができる。
ディスプレイアダプタ８２２は、通信バス８０４及びディスプレイ８２０とインタフェースすることができ、プロセッサ８０２から表示データを受信して、該表示データをディスプレイ８２０に対する表示コマンドに変換することができる。
加えて、プロセッサ（複数可）８０２は、ネットワークアダプタ８２４を通じてネットワーク、たとえばインターネット、ＬＡＮ等を介して通信することができる。
【０１３８】
当業者には、計算装置８００において他の既知の電子部品を追加するか又は代わりに用いることができることが明らかであろう。
図８に示されている部品のうちの１つ又は複数は任意選択とすることができる（たとえば、ユーザ入力装置、２次メモリ等）ことも明らかであるはずである。
【０１３９】
本明細書において説明及び例示してきたものは、本発明の好ましい一実施形態、及びその変形形態のうちの幾つかである。
本明細書において使用される用語、説明、及び図面は、例示のためにのみ記載され、限定を意味するものではない。
当業者は、別途指示されない限り全ての用語がその最も広い適切な意味を有するように意図されている以下の特許請求の範囲及びその均等物によって規定されるように意図されている本発明の範囲内で多数の変形形態が可能であることを認識するであろう。
【符号の説明】
【０１４０】
１００・・・符号化木，
２００・・・システム，
２０２・・・サーバ，
２０４・・・エンコーダ，
２０６，２２２・・・送受信機，
２０８・・・コントローラ，
２１０・・・データ記憶装置，
２２０・・・クライアント，
２２４・・・デコーダ，
２２６・・・インタフェース，
２２８・・・入力，
３００・・・符号化木，
３０２・・・基本Ｉフレーム，
４００・・・符号化木，
４０２・・・再ルーティングＡ，
４０４・・・再ルーティングＢ，
５００・・・符号化木，
５０２・・・再ルーティングＡ，
５０４・・・再ルーティングＢ，
８００・・・計算装置，
８０２・・・プロセッサ，
８０４・・・通信バス，
８０６・・・メインメモリ，
８０８・・・２次メモリ，
８１０・・・ハードディスクドライブ，
８１２・・・着脱可能記憶装置，
８１４・・・着脱可能記憶ユニット，
８１６・・・キーボード，
８１８・・・マウス，
８２０・・・ディスプレイ，
８２２・・・ディスプレイアダプタ，
８２４・・・ネットワークアダプタ，
【特許請求の範囲】
【請求項１】
複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステムであって、
複数のビューに対応する前記複数のフレームのうちの少なくとも１つのフレームの多重表現を、前記多重表現ごとに異なる参照フレームを使用して符号化するように構成されるエンコーダであって、前記少なくとも１つのフレームの前記多重表現は共通時刻及び共通ビューに対応する、エンコーダと、
前記複数のフレーム及び前記多重表現を含む符号化木を作成するように構成されるコントローラであって、前記符号化木は、前記フレームのうちのいずれが他のフレームのための参照フレームを含むかを特定するフレーム経路を前記複数の符号化フレームごとに示し、前記コントローラは、前記多重表現のうちの少なくとも１つを、各時刻における各ビューに対応する、Ｐフレーム及びＩフレームのうちの一方として維持するようにさらに構成される、コントローラと、
前記符号化木を記憶するように構成されるデータ記憶装置であって、前記コントローラは、前記データ記憶装置の記憶制約を特定すると共に、前記多重表現のうちの少なくとも１つを前記符号化木から省略して、前記データ記憶装置内に記憶される前記複数のフレームが前記記憶制約内に留まるようにするようにさらに構成される、データ記憶装置と
を備えるシステム。
【請求項２】
前記コントローラは、クライアントが時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装すると共に、要求される可能性が最も少ないフレームを前記符号化木からまず省略して前記データ記憶装置の前記記憶制約内に留まるように、前記対話モデルに基づいて前記複数のフレームを配置するようにさらに構成される
請求項１に記載のシステム。
【請求項３】
前記コントローラは、前記多重表現をクライアントに通信することに関連付けられる送信コストを計算するようにさらに構成され、
前記複数のフレームの前記多重表現はＰフレームを含み、
前記コントローラは、前記少なくとも１つフレームの前記多重表現の前記ＰフレームをＩフレームで置き換えると共に、前記Ｉフレームを前記符号化木内の前記少なくとも１つのフレームのノードとして記憶し、それによって、前記データ記憶装置の前記記憶制約内に留まりながら、前記計算された送信コストを最小化するようにさらに構成される
請求項１に記載のシステム。
【請求項４】
前記コントローラは、第１のフレームをクライアントに通信し、前記クライアントから第２のフレームを求める要求を受信し、前記第２のフレームが前記クライアントにおいて適切に復号化されるために前記少なくとも１つのフレームの前記多重表現のうちの１つの表現が必要とされると判断し、前記クライアントにおける前記第２のフレームの適切な復号化のために、前記符号化木を通る複数の経路に沿って、前記少なくとも１つのフレームの前記多重表現のそれぞれを通信することに関連付けられる送信コストを求め、最低送信コストに関連付けられる前記少なくとも１つのフレームの前記多重表現のうちの前記１つの表現を前記クライアントに通信するようにさらに構成される
請求項１に記載のシステム。
【請求項５】
複数のフレームから成るマルチビューストリーミングビデオデータを管理する方法であって、
前記マルチビューストリーミングビデオを記憶するように構成されるデータ記憶装置の記憶制約を特定することと、
複数のビューに対応する前記複数のフレームのうちの少なくとも１つのフレームの多重表現を、前記多重表現ごとに異なる参照フレームを使用して符号化することであって、前記多重表現は共通時刻及び共通ビューに対応する、符号化することと、
前記多重表現のうちの少なくとも１つを省略することによって、前記データ記憶装置の前記記憶制約を考慮して、前記複数のフレーム及び前記多重表現を含む符号化木を作成することであって、前記符号化木は、前記多重表現のうちの少なくとも１つを、各時刻における各ビューに対応する、Ｐフレーム及びＩフレームのうちの一方として維持する、作成することと、
前記符号化木を前記データ記憶装置内に記憶することと
を含む方法。
【請求項６】
前記方法は、クライアントが時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装することをさらに含み、
前記符号化木を作成することは、要求される可能性が最も少ないフレームを前記符号化木からまず省略して前記データ記憶装置の前記記憶制約内に留まるように、前記対話モデルに基づいて前記複数のフレームを配置することをさらに含む
請求項５に記載の方法。
【請求項７】
前記複数のフレームの前記多重表現はＰフレームを含み、前記方法は、
前記多重表現をクライアントに通信することに関連付けられる送信コストを計算することと、
前記少なくとも１つのフレームの前記多重表現の前記ＰフレームをＩフレームで置き換えることと、
前記Ｉフレームを前記符号化木内の前記少なくとも１つのフレームのノードとして記憶することであって、それによって、前記データ記憶装置の前記記憶制約内に留まりながら、前記計算された送信コストを最小化する、記憶することと
をさらに含む請求項５に方法。
【請求項８】
第１のフレームをクライアントに通信することと、
前記クライアントから第２のフレームを求める要求を受信することと、
前記第２のフレームが前記クライアントにおいて適切に復号化されるために前記少なくとも１つのフレームの前記多重表現のうちの１つの表現が必要とされると判断することと、
前記クライアントにおける前記第２のフレームの適切な復号化のために、前記符号化木を通る複数の経路に沿って前記多重表現のそれぞれを通信することに関連付けられる送信コストを求めることと、
最低送信コストに関連付けられる前記多重表現のうちの前記１つの表現を前記クライアントに通信することと
をさらに含む請求項５に記載の方法。
【請求項９】
１つ又は複数のプログラムが組み込まれているコンピュータ可読記憶媒体であって、前記１つ又は複数のコンピュータプログラムは、複数のフレームから成るマルチビューストリーミングビデオデータを管理する方法を実装し、前記１つ又は複数のコンピュータプログラムは、
前記マルチビューストリーミングビデオを記憶するように構成される前記データ記憶装置の記憶制約を特定することと、
複数のビューに対応する前記複数のフレームのうちの少なくとも１つのフレームの多重表現を、前記複数のバージョンごとに異なる参照フレームを使用して符号化することであって、前記多重表現は共通時刻及び共通ビューに対応する、符号化することと、
前記多重表現のうちの少なくとも１つを省略することによって、前記データ記憶装置の前記記憶制約を考慮して、前記複数のフレーム及び前記多重表現を含む符号化木を作成することであって、前記符号化木は、前記多重表現のうちの少なくとも１つを、各時刻における各ビューに対応する、Ｐフレーム及びＩフレームのうちの一方として維持する、作成することと、
前記符号化木を前記データ記憶装置内に記憶することと
のためのコンピュータ可読コードを含むコンピュータ可読記憶媒体。
【請求項１０】
前記１つ又は複数のコンピュータプログラムは、
クライアントが時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装することのためのコンピュータ可読コードをさらに含み、
前記符号化木を作成することは、要求される可能性が最も少ないフレームを前記符号化木からまず省略して前記データ記憶装置の前記記憶制約内に留まるように、前記対話モデルに基づいて前記複数のフレームを配置することをさらに含む
請求項９に記載のコンピュータ可読記憶媒体。
【請求項１１】
前記１つ又は複数のコンピュータプログラムは、
前記多重表現をクライアントに通信することに関連付けられる送信コストを計算することと、
前記少なくとも１つのフレームの前記多重表現の前記ＰフレームをＩフレームで置き換えることと、
前記Ｉフレームを前記符号化木内の前記少なくとも１つのフレームのノードとして記憶することであって、それによって、前記データ記憶装置の前記記憶制約内に留まりながら、前記計算された送信コストを最小化する、記憶することと
のためのコンピュータ可読コードをさらに含む請求項９に記載のコンピュータ可読記憶媒体。
【請求項１２】
前記１つ又は複数のコンピュータプログラムは、
第１のフレームをクライアントに通信することと、
前記クライアントから第２のフレームを求める要求を受信することと、
前記第２のフレームが前記クライアントにおいて適切に復号化されるために前記少なくとも１つのフレームの前記多重表現のうちの１つの表現が必要とされると判断することと、
前記クライアントにおける前記第２のフレームの適切な復号化のために、前記符号化木を通る複数の経路に沿って、前記多重表現のそれぞれを通信することに関連付けられる送信コストを求めることと、
最低送信コストに関連付けられる前記多重表現のうちの前記１つの表現を前記クライアントに通信することと
のためのコンピュータ可読コードをさらに含む請求項９に記載のコンピュータ可読記憶媒体。
【請求項１】
複数のフレームから成るマルチビューストリーミングビデオデータを管理するシステムであって、
複数のビューに対応する前記複数のフレームのうちの少なくとも１つのフレームの多重表現を、前記多重表現ごとに異なる参照フレームを使用して符号化するように構成されるエンコーダであって、前記少なくとも１つのフレームの前記多重表現は共通時刻及び共通ビューに対応する、エンコーダと、
前記複数のフレーム及び前記多重表現を含む符号化木を作成するように構成されるコントローラであって、前記符号化木は、前記フレームのうちのいずれが他のフレームのための参照フレームを含むかを特定するフレーム経路を前記複数の符号化フレームごとに示し、前記コントローラは、前記多重表現のうちの少なくとも１つを、各時刻における各ビューに対応する、Ｐフレーム及びＩフレームのうちの一方として維持するようにさらに構成される、コントローラと、
前記符号化木を記憶するように構成されるデータ記憶装置であって、前記コントローラは、前記データ記憶装置の記憶制約を特定すると共に、前記多重表現のうちの少なくとも１つを前記符号化木から省略して、前記データ記憶装置内に記憶される前記複数のフレームが前記記憶制約内に留まるようにするようにさらに構成される、データ記憶装置と
を備えるシステム。
【請求項２】
前記コントローラは、クライアントが時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装すると共に、要求される可能性が最も少ないフレームを前記符号化木からまず省略して前記データ記憶装置の前記記憶制約内に留まるように、前記対話モデルに基づいて前記複数のフレームを配置するようにさらに構成される
請求項１に記載のシステム。
【請求項３】
前記コントローラは、前記多重表現をクライアントに通信することに関連付けられる送信コストを計算するようにさらに構成され、
前記複数のフレームの前記多重表現はＰフレームを含み、
前記コントローラは、前記少なくとも１つフレームの前記多重表現の前記ＰフレームをＩフレームで置き換えると共に、前記Ｉフレームを前記符号化木内の前記少なくとも１つのフレームのノードとして記憶し、それによって、前記データ記憶装置の前記記憶制約内に留まりながら、前記計算された送信コストを最小化するようにさらに構成される
請求項１に記載のシステム。
【請求項４】
前記コントローラは、第１のフレームをクライアントに通信し、前記クライアントから第２のフレームを求める要求を受信し、前記第２のフレームが前記クライアントにおいて適切に復号化されるために前記少なくとも１つのフレームの前記多重表現のうちの１つの表現が必要とされると判断し、前記クライアントにおける前記第２のフレームの適切な復号化のために、前記符号化木を通る複数の経路に沿って、前記少なくとも１つのフレームの前記多重表現のそれぞれを通信することに関連付けられる送信コストを求め、最低送信コストに関連付けられる前記少なくとも１つのフレームの前記多重表現のうちの前記１つの表現を前記クライアントに通信するようにさらに構成される
請求項１に記載のシステム。
【請求項５】
複数のフレームから成るマルチビューストリーミングビデオデータを管理する方法であって、
前記マルチビューストリーミングビデオを記憶するように構成されるデータ記憶装置の記憶制約を特定することと、
複数のビューに対応する前記複数のフレームのうちの少なくとも１つのフレームの多重表現を、前記多重表現ごとに異なる参照フレームを使用して符号化することであって、前記多重表現は共通時刻及び共通ビューに対応する、符号化することと、
前記多重表現のうちの少なくとも１つを省略することによって、前記データ記憶装置の前記記憶制約を考慮して、前記複数のフレーム及び前記多重表現を含む符号化木を作成することであって、前記符号化木は、前記多重表現のうちの少なくとも１つを、各時刻における各ビューに対応する、Ｐフレーム及びＩフレームのうちの一方として維持する、作成することと、
前記符号化木を前記データ記憶装置内に記憶することと
を含む方法。
【請求項６】
前記方法は、クライアントが時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装することをさらに含み、
前記符号化木を作成することは、要求される可能性が最も少ないフレームを前記符号化木からまず省略して前記データ記憶装置の前記記憶制約内に留まるように、前記対話モデルに基づいて前記複数のフレームを配置することをさらに含む
請求項５に記載の方法。
【請求項７】
前記複数のフレームの前記多重表現はＰフレームを含み、前記方法は、
前記多重表現をクライアントに通信することに関連付けられる送信コストを計算することと、
前記少なくとも１つのフレームの前記多重表現の前記ＰフレームをＩフレームで置き換えることと、
前記Ｉフレームを前記符号化木内の前記少なくとも１つのフレームのノードとして記憶することであって、それによって、前記データ記憶装置の前記記憶制約内に留まりながら、前記計算された送信コストを最小化する、記憶することと
をさらに含む請求項５に方法。
【請求項８】
第１のフレームをクライアントに通信することと、
前記クライアントから第２のフレームを求める要求を受信することと、
前記第２のフレームが前記クライアントにおいて適切に復号化されるために前記少なくとも１つのフレームの前記多重表現のうちの１つの表現が必要とされると判断することと、
前記クライアントにおける前記第２のフレームの適切な復号化のために、前記符号化木を通る複数の経路に沿って前記多重表現のそれぞれを通信することに関連付けられる送信コストを求めることと、
最低送信コストに関連付けられる前記多重表現のうちの前記１つの表現を前記クライアントに通信することと
をさらに含む請求項５に記載の方法。
【請求項９】
１つ又は複数のプログラムが組み込まれているコンピュータ可読記憶媒体であって、前記１つ又は複数のコンピュータプログラムは、複数のフレームから成るマルチビューストリーミングビデオデータを管理する方法を実装し、前記１つ又は複数のコンピュータプログラムは、
前記マルチビューストリーミングビデオを記憶するように構成される前記データ記憶装置の記憶制約を特定することと、
複数のビューに対応する前記複数のフレームのうちの少なくとも１つのフレームの多重表現を、前記複数のバージョンごとに異なる参照フレームを使用して符号化することであって、前記多重表現は共通時刻及び共通ビューに対応する、符号化することと、
前記多重表現のうちの少なくとも１つを省略することによって、前記データ記憶装置の前記記憶制約を考慮して、前記複数のフレーム及び前記多重表現を含む符号化木を作成することであって、前記符号化木は、前記多重表現のうちの少なくとも１つを、各時刻における各ビューに対応する、Ｐフレーム及びＩフレームのうちの一方として維持する、作成することと、
前記符号化木を前記データ記憶装置内に記憶することと
のためのコンピュータ可読コードを含むコンピュータ可読記憶媒体。
【請求項１０】
前記１つ又は複数のコンピュータプログラムは、
クライアントが時刻（ｉ）及びビュー（ｊ）を有するフレームを見た後に時刻（ｉ＋１）及びビュー（ｋ）を有する特定のフレームを要求する確率を記述する対話モデルを実装することのためのコンピュータ可読コードをさらに含み、
前記符号化木を作成することは、要求される可能性が最も少ないフレームを前記符号化木からまず省略して前記データ記憶装置の前記記憶制約内に留まるように、前記対話モデルに基づいて前記複数のフレームを配置することをさらに含む
請求項９に記載のコンピュータ可読記憶媒体。
【請求項１１】
前記１つ又は複数のコンピュータプログラムは、
前記多重表現をクライアントに通信することに関連付けられる送信コストを計算することと、
前記少なくとも１つのフレームの前記多重表現の前記ＰフレームをＩフレームで置き換えることと、
前記Ｉフレームを前記符号化木内の前記少なくとも１つのフレームのノードとして記憶することであって、それによって、前記データ記憶装置の前記記憶制約内に留まりながら、前記計算された送信コストを最小化する、記憶することと
のためのコンピュータ可読コードをさらに含む請求項９に記載のコンピュータ可読記憶媒体。
【請求項１２】
前記１つ又は複数のコンピュータプログラムは、
第１のフレームをクライアントに通信することと、
前記クライアントから第２のフレームを求める要求を受信することと、
前記第２のフレームが前記クライアントにおいて適切に復号化されるために前記少なくとも１つのフレームの前記多重表現のうちの１つの表現が必要とされると判断することと、
前記クライアントにおける前記第２のフレームの適切な復号化のために、前記符号化木を通る複数の経路に沿って、前記多重表現のそれぞれを通信することに関連付けられる送信コストを求めることと、
最低送信コストに関連付けられる前記多重表現のうちの前記１つの表現を前記クライアントに通信することと
のためのコンピュータ可読コードをさらに含む請求項９に記載のコンピュータ可読記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１０−９３８０７（Ｐ２０１０−９３８０７Ａ）
【公開日】平成２２年４月２２日（２０１０．４．２２）
【国際特許分類】
【外国語出願】
【出願番号】特願２００９−２３０６６６（Ｐ２００９−２３０６６６）
【出願日】平成２１年１０月２日（２００９．１０．２）
【出願人】（５０３００３８５４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (1,145)
【Ｆターム（参考）】
【公開日】平成２２年４月２２日（２０１０．４．２２）
【国際特許分類】
【出願番号】特願２００９−２３０６６６（Ｐ２００９−２３０６６６）
【出願日】平成２１年１０月２日（２００９．１０．２）
【出願人】（５０３００３８５４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (1,145)
【Ｆターム（参考）】
[ Back to top ]