(57)【要約】本発明は、マルコフデシジョンプロセスとしてモデルリングすることでスケーラブルビデオアプリケーションを制御するためのシステム及び方法に関する。モデルは、アプリケーション相対的なプログレスを測定することに基づいており、相対的なプログレスは、フレームを処理するために割り当てられたＣＰＵバジェットとフレームの処理で使用される実際のＣＰＵサイクルとの間の違いである。この制御ストラテジーは、受信されたレイヤの数（最大の品質レベル）とバジェットされたＣＰＵ時間とに基づいて次のフレームのためにデコードされる、最近にデコードされたレベル数及び最大レベルに基づいている。目的は、品質レベルを最大にしつつ、デッドラインのミス（完全にデコードされていないフレーム）の数と品質レベルの変化の数の両者を最小にする品質レベルの制御ストラテジーを開発することで、フレーム間の品質の遷移を平滑にすることである。品質レベルの変化が少なくなると、視聴される画像が平滑になる。
2007515866.tif 000002
【特許請求の範囲】
【請求項１】
メディア処理アプリケーションによりメディアフレームの出力画像の品質レベルを設定する方法であって、
前記メディアフレームを処理するために使用されるリソースの量を決定するステップと、
ａ）マイルストーンで計算された前記メディア処理アプリケーションの相対的なプログレス、ｂ）前記出力画像のための選択することが可能な最大の品質レベル、ｃ）出力画像の以前に使用された品質レベル、及び、ｄ）受信されたレイヤ数に基づいた最大の品質レベルに基づいて前記出力画像の品質レベルを制御するステップと、
を含むことを特徴とする方法。
【請求項２】
前記品質レベルは、次のフレームを処理するために可能な最高の品質レベルと前記出力画像の品質を保持するために必要とされる最高の品質レベルとの最小値に基づいて選択される、
請求項１記載の方法。
【請求項３】
前記メディアフレームの品質レベルを制御するステップは、状態のセット、デシジョンのセット、遷移確率のセット及びレベニューのセットを有するマルコフデシジョンの問題としてモデル化され、
前記マルコフデシジョンの問題を解いて最適なストラテジーを導出するステップと、
この解に基づいてデコードされるメディアフレームのレイヤ数を決定するステップとを含む、
請求項１記載の方法。
【請求項４】
マイルストーンで前記メディア処理アプリケーションの相対的なプログレス及び前記以前に使用された品質レベルを含むための状態のセットを定義するステップと、
前記メディア処理アプリケーションが提供することができる複数の品質レベルを含むためのデシジョンのセットを定義するステップと、
前記複数の品質レベルの所与の品質レベルについて、現在のマイルストーンでの状態のセットのあるセットから次のマイルストーンでの状態のセットの他のセットに遷移がなされる確率を含むために遷移確率のセットを定義するステップと、
前記メディアフレームの品質レベルに関連する正のレベニュー、デッドラインのミスに関連する負のレベニュー、及び品質レベルの変化に関連する負のレベニューを含むためにレベニューのセットを定義するステップと、
を更に含むことを特徴とする方法。
【請求項５】
スケーラブルメディア処理アプリケーションによりメディアフレームの出力画像の品質レベルを設定するシステムであって、
前記メディアフレームを処理するために使用されるリソースの量を決定する決定手段と、
ａ）マイルストーンで計算された前記メディア処理アプリケーションの相対的なプログレス、ｂ）前記メディアフレームの前記出力画像のために選択することが可能な最大の品質レベル、ｃ）メディアフレームの出力画像の以前に使用された品質レベル、及び、ｄ）受信されたレイヤ数に基づいた最大の品質レベルに基づいて前記メディアフレームの前記出力画像の品質レベルを制御する制御手段と、
を有することを特徴とするシステム。
【請求項６】
前記品質レベルは、次のフレームを処理するために可能な最高の品質レベルと前記出力画像の品質を保持するために必要とされる最高の品質レベルとの最小値に基づいて選択される、
請求項５記載のシステム。
【請求項７】
前記制御手段は、状態のセット、デシジョンのセット、遷移確率のセット及びレベニューのセットを有するマルコフデシジョンの問題として前記メディアフレームの品質レベルの制御をモデル化し、
デシジョンストラテジーを使用して前記マルコフデシジョンの問題への解とし、
この解に基づいて前記メディアフレームの品質レベルを設定するために更に構成される、
請求項５記載のシステム。
【請求項８】
前記状態のセットは、マイルストーンで前記メディア処理アプリケーションの相対的なプログレス及び以前のメディアフレームの前記以前に使用された品質レベルを含み、
前記デシジョンのセットは、前記メディア処理アプリケーションが提供することができる複数の品質レベルを含み、
前記遷移確率のセットは、前記複数の品質の所与の品質レベルについて、現在のマイルストーンでの状態のセットのあるセットから次のマイルストーンでの状態のセットの他のセットに遷移がなされる確率を含み、
前記レベニューのセットは、前記メディアフレームの品質レベルに関連する正のレベニュー、デッドラインのミスに関連する負のレベニュー、及び品質レベルの変化に関連する負のレベニューを含む、
請求項７記載のシステム。
【請求項９】
請求項１記載の方法を実行するために設計されるコンピュータプログラムプロダクト。
【請求項１０】
請求項９記載のコンピュータプログラムプロダクトを含む記憶装置。
【請求項１１】
請求項５記載のシステムを含むテレビジョンセット。
【請求項１２】
請求項５記載のシステムを含むセットトップボックス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全体の品質を平滑化するために無線媒体を通して伝送されるビデオフレームのデコード品質を制御するためのスケーラブルビデオアプリケーションのための方法に関する。
【背景技術】
【０００２】
（たとえばＩＥＥＥ８０２．１１）無線媒体の帯域幅の変動は、一般的に非常に大きい。無線媒体を通して伝送されるビデオの合理的な視聴経験を可能にするため、ベースレイヤ（ＢＬ）及び１以上のエンハンスメントレイヤ（ＥＬ）（たとえばＭＰＥＧ４又はＭＰＥＧ２スケーラブルプロファイル）としてコードが送出される。この技術は、スケーラブルビデオストリームと呼ばれる。スケーラブルビデオのコンセプトは、ＢＬの伝送及びデコードが認識可能な品質のビデオを再構成するのに十分であって、ＥＬの伝送及び処理が受信されたビデオ系列の品質の更なる改善のためにのみ必要とされるようなやり方で、ビデオデータをＢＬ及びＥＬに区分することを提案する。たとえば、１つのＥＬをもつＢＬは、合理的な品質の画像を伝送し、全てのＥＬをもつＢＬは、最大の品質のビデオ画像を伝達する。ＢＬは、それぞれのフレームについてネットワークを通して最初に送出され、そのフレームに属する連続するＥＬ部分が後続する。
【０００３】
帯域幅がかなり変動するとき、ＢＬのみが１つのフレームについて到達し、他のフレームについて１以上のＥＬをもつＢＬがディスプレイに到達する。これにより、一定に変化する画質が得られる。品質におけるかかる変化は、受信された画像を視聴しているエンドユーザにより理解されない。
【発明の開示】
【課題を解決するための手段】
【０００４】
本発明は、複数の品質レベルで、たとえばビデオフレームといったメディアフレームを処理することができるメディア処理アプリケーションの全体の出力品質を制御するためのシステム及び方法を提供する。品質レベルは、ＢＬ及び特定の数のＥＬ（ゼロ以上）の処理に対応する。それぞれの品質レベルは、区別可能な（しかし必ずしも固定されない）量のリソース、たとえばＣＰＵを必要とする。より高い品質レベル（すなわち、処理される大きな数のＥＬ）は、高いリソースの使用量のコストで、良好な品質の画像が得られる。品質レベルは、フレーム毎に選択される。リソースは有限であるので、処理は、この出力処理の完了のデッドラインによる所与のレベルの出力品質について完了されない場合があり、すなわちデッドラインのミスが生じる。それぞれのデッドラインのミスにより、出力において厳しいアーチファクトが生じる。無線媒体の性質のため、所与のフレームについて受信されるレイヤ数は、時間を通して変動し、これはフレームについて選択された品質レベルの数を制限する。好適な実施の形態では、たとえばビデオフレームといったメディアフレームが受信され、表示されるたびに、受信されたレイヤ数が調べられる。処理することができる最大のレイヤ数は、フレームについて受信されたレイヤの数、及び対応するデッドラインを失う最小のリスクをもつそのフレームのレイヤを処理するのにＣＰＵが利用可能である回数により決定される。しかし、品質レベルの変化は、知覚し得るアーチファクトとなる場合がある。時間につれての品質レベルのジャンプの数を最小にすること、すなわち時間につれての受信される画像を平滑化することで、ユーザはかなり安定な品質を有する画像を視聴する。この平滑化は、好適な実施の形態では、マルコフ連鎖を設定し、バリューファンクションを定義することで行われる。ネットワーク状態により引き起こされない品質レベルの変化は、負の値を生じる。ネットワークの変動により引き起こされる品質レベルの変化は、品質の低下の場合にゼロ値を生じる。画像を全く表示しないことは最も高いペナルティを受ける。他方で、より高い数の処理されたレイヤは、高い値を生じる。他方で、より高い数の処理されたレイヤは、より高い値を生じる。
【０００５】
現実的なパケットの損失をもつ多くのビデオを再生することで、バリューファンクションに関して最適化されるレイヤの選択手順が開発される。このようなやり方で開発された最適化されたレイヤの選択機能は、所与のフレーム及び先行するフレームについて受信されたレイヤの機能として表示される必要があるレイヤ数を決定するために使用される。
【０００６】
リソースの消費を最適化すること、及び出力品質を最大にすることに対処する多数のアプローチが存在する。１つは、スケーラブルビデオアルゴリズムをスケーラブルビデオのデコードに適用する本発明のアプローチである。品質レベルは、処理されるべきレイヤ数として定義される。従来技術のアルゴリズムは、（ＤＶＤのような）安定な入力を仮定している。安定な入力は、伝送の間に情報の損失がないことを意味しており、したがって、ビデオデータのデコードの間に如何なる品質レベルをも選択することができることを意味している。本発明は、不安定な入力も同様に対処する。本発明は、ＣＰＵの可用性で見るだけでなく、アプリケーションの入力でも見ることで、デコード（及び可能であれば、後処理）ストラテジーを最適化する。基本的に、本発明は、ネットワークからの依存性を制御ストラテジーに導入する。したがって、本発明は、安定（たとえばＣＤ、ＤＶＤ、ＨＤＤ）かつ不安定な（無線ネットワーク）入力で機能することができる。
【発明を実施するための最良の形態】
【０００７】
以下の説明は例示するためのものであって、限定するものではないことが当業者により理解されるべきである。当業者であれば、本発明の精神及び特許請求の範囲に含まれる多くの変形が存在することを理解されるであろう。公知の機能及び動作の不必要な詳細は、本発明を曖昧にしないように、ここでの記載から省略される場合がある。
【０００８】
本発明は、リソースの利用と出力品質の間のトレードオフを解決するための内部設定の動的な変更を可能にするスケーラブルビデオアプリケーションを制御するビデオ制御メカニズムのシステム及び方法を提供する。図１は、パラメータのセット１０３によりスケーラブルアプリケーション１０１の挙動に影響を及ぼす制御メカニズム１０２をもつスケーラブルビデオプロセッサの基本コンセプトを説明する。ビデオ処理を達成するためのスケーラブルアプリケーションの使用は、出力品質を達成することができるように、アプリケーションの一部が容易にスケーリングされるのを可能にし、これによりリソースの消費量が出力品質に対してバランスされるのを可能にする。
【０００９】
スケーラブルビデオアプリケーション（ＳＶＡ）としてビデオデコーダを考える。このビデオデコーダは、品質の出力ビデオストリームを生成するためにその内部設定を変えることで制御することができる。表１に例示されるように、デコーダは、最も低い品質レベルで動作するときにベースレイヤのみを処理する。品質レベルの増加により、デコーダは、処理時間（及び、明らかにリソースの消費量）と同様に、処理されるべきレイヤの数を増加させる。
【００１０】
【表１】
2007515866.tif 000003
しかし、全てのレイヤが常に利用可能ではない。デコーダがネットワークからレイヤを受けると仮定すると、時間的な如何なる瞬間でデコーダに入力されるレイヤ数について保証がない。したがって、幾つのレイヤ数が次に処理されるかが確かでない。利用可能なレイヤ数に関する情報は、入力バッファから得ることができる。
【００１１】
一般に、本発明のスケーラブルアプリケーションによる処理は以下のように記載される。アプリケーションは、入力バッファからワークユニット“a  unit  of  work”（フレーム）を引き出し、それを処理して、結果を出力バッファに送出する。アプリケーションは、ワークユニット、すなわちビデオフレームを処理するためのＣＰＵ時間の固定されたバジェット“budget”を受ける。ワークユニットは、サイズ及び複雑さの点で異なり、このことは、ワークユニットを処理するために必要とされる時間における差となる。ワークユニットの完了は、マイルストーンと呼ばれ、かかるマイルストーンのそれぞれについてデッドラインが存在する。スケーラブルビデオアプリケーションの環境では、フレームのデコードは、厳密に周期的なデッドラインを有するワークユニットであり、すなわちデッドラインは、所与の固定された周期Ｐで生じる。デッドラインのミスが防止されることになる。
【００１２】
それぞれのマイルストーンで、デッドライン周期で表現されるマイルストーンのデッドラインにまで残っている保証されるリソースのバジェットの量として相対的なプログレス“progress”が計算される。バッファサイズは有限であるので、バッファが含むフレーム数に上限が存在する。このフレーム数は、以下のように前もってデコードすることができるフレーム数の範囲を提供するために使用することができる。
｛min［入力バッファにおけるフレーム数］，max［出力バッファにおけるフレーム数］｝
マイルストーンでの相対的なプログレスが負となる場合、少なくとも１つのデッドラインが失われ、すなわち相対的なプログレスが負であったように少なくとも１つのフレームを処理するために保証されたバジェットよりも多くを要する。測定が行われないとき、かかるデッドラインのミスの影響は累積的である。かかる累積的なデッドラインのミスを防止するため、アプリケーションは、それぞれのマイルストーンで実行される品質レベルを調整する。
【００１３】
品質レベルを選択するために３つの目的が調整される。
１．  品質レベルが最大にされる。
２．  デッドラインのミスが最小にされる。
３．  品質レベルの変化が最小にされる。
本発明の適用により、後処理が考慮されない。
【００１４】
これらの目的を言い換えると、スケーラブルメディア処理アプリケーションについて品質レベルの制御ストラテジーが必要とされ、これは、デッドラインのミスの数及び品質レベルの変化の数の両者を最小にし、品質レベルを最大にするように、固定されたＣＰＵのバジェットが割り当てられている。
【００１５】
本発明によれば、この問題は、マルコフデシジョン（Markov  Decision）モデルとしてモデル化される。このモデルは、そのマイルストーンでのアプリケーションの相対的なプログレスを計算することに基づいている。マルコフデシジョンの問題を解決することで、オーバヘッドを殆ど受けることなしに、実行時間の間に適用することができる品質レベルの制御ストラテジーとなる。
【００１６】
セットトップボックス及びデジタルＴＶセットのような消費者の端末は、オープンかつフレキシブルとなることが市場により必要とされる。このことは、等価なメディア処理アプリケーションが実行する中央処理装置（ＣＰＵ）により、幾つかの専用のハードウェアコンポーネントを置き換え、特定のメディア処理アプリケーションを実行することで達成される。ＣＰＵ時間、メモリ及びバス帯域幅のようなリソースは、これらのアプリケーションの間で共有される。ここで、好ましくは、ＣＰＵリソースのみが考慮される。
【００１７】
それぞれのマイルストーンで、相対的なアプリケーションのプログレスが計算される。ここで、マイルストーンでの相対的なプログレスは、デッドラインの周期で表現されるマイルストーンのデッドラインまでの時間として定義される。
【００１８】
マイルストーンでの相対的なプログレスは以下のように計算することができる。一般性を欠くことなしに、アプリケーションは時間ｔ＝０で処理を始めるものとする。マイルストーンｍの時間はｃmにより示される。つぎに、マイルストーンのデッドラインは、ｄmにより示される。デッドラインは、厳密に周期的であって、これは、以下のように書くことができることを示す。
ｄm＝ｄ0＋ｍ*Ｐ
ここでＰは２つの連続するデッドライン間の周期であって、ｄ0はオフセットである。ρmで示されるマイルストーンでの相対的なプログレスは、以下に与えられる。
【００１９】
【数１】
2007515866.tif 000004
相対的なプログレスの計算を説明するため、図２に示される例示的なタイムラインを考える。この例では、Ｐ＝１及びｄ0＝１である。式（１）を使用して計算された１〜５までのマイルストーンでの相対的なプログレスは、ρ1＝（ｄ1−ｃ1）／Ｐ＝（２−１）／１，ρ2＝１．５，ρ3＝１，ρ4＝０及びρ5＝０．５により与えられる。なお、マイルストーン４は時間的に間に合った状態である。
【００２０】
マイルストーン（ｍ＋１）番目の相対的なプログレスがゼロ以下に下がった場合、ｍ番目以降のマイルストーンから［−ρm+1］（−ρm+1までの次の大きな整数）デッドラインのミスが生じる。どのようにデッドラインのミスが対処されるかは、アプリケーションに特化する。ここで、ちょうど作成された出力が捨てられないが、何かに使用されることを意味する、機能維持アプローチが想定される。１つのやり方は、この出力を最初の次のデッドラインで使用することであり、これは調整された相対的なプログレス
ρ’m＝ρm＋［−ρm］≧０
が得られることを意味する。連続するアプローチは、ρ’m＝０、すなわち最も低い可能な値とされ、この値はある意味では、作成に応じた直後の出力を使用することに対応する。言い換えれば、デッドラインｄm及びその後のデッドラインは、−ρm*Ｐの量を延ばす。結果的に、式（１）を使用したマイルストーンでの相対的なプログレスを計算することができるが、新たなオフセットｄ0’＝ｄ0−ρm*Ｐをもつ。
【００２１】
このプロセスは、図３に示される例示的なタイムラインにより説明される。この例では、Ｐ＝１及びｄ0＝０．５である。式（１）を使用して、以下を導出することができる。ρ1＝０．５，ρ2＝０．５及びρ3＝−０．５。マイルストーン３での相対的なプログレスは、ゼロ以下に下がり、したがってマイルストーン２、すなわちｔ＝３．５以降で［−ρ3］＝１のデッドラインのミスが生じる。つぎに、デッドラインｄ3は、ｄ’3＝ｃ3＝４に延ばされ、更なるデッドラインは、０．５の量だけ延ばされる。続いて、ρ4＝０．５及びρ5＝０．５が発見される。
【００２２】
マイルストーンでのアプリケーションの状態は、その相対的なプログレスにより与えられる。これは、しかし、無限に大きな状態のセットを与え、マルコフデシジョンプロセスは、有限のセットを必要とする。後者は以下のように達成され、ｐ＞０が相対的なプログレスに関する所与の上限を示すとする。数ｐは、アプリケーションが前に機能した周期の数の測定であり、これは先に説明されたバッファサイズから導出される。０とｐとの間の相対的なプログレス空間は、有限のセットΠ＝｛π0，．．．，πn-1｝  ｎ≧１に分割され、ここでプログレスのインターバルは以下に示される。
【００２３】
【数２】
2007515866.tif 000005
プログレスのインターバルπの下限及び上限は、
（外１）
2007515866.tif 000006
によりそれぞれ示される。
【００２４】
それぞれのマイルストーンで、次のワークユニット処理される品質レベルに関する判定が行われる必要がある。したがって、ある状態、すなわちマルコフデシジョンの問題で行うことができる判定のセットは、アプリケーションが実行することのできる品質レベルのセットに対応する。このセットはＱで示される。
【００２５】
それぞれの品質レベルは、処理されるレイヤの数に対応する。したがって、所与のフレームについて入力バッファに存在するよりも多くのレイヤをデコードする必要がある品質レベルを選択することは不可能である。このように、選択することのできる最大の品質レベルは、受信されたレイヤの数により与えられ、ｍａｘｑ（ｉ）により定義される。
【００２６】
品質レベルの変化が考慮され、それぞれのマイルストーンで、以前に使用された品質レベルが知られる必要がある。このことは、品質レベルで状態のセットを拡張することで実現することができる。したがって、状態ｉは、以下により定義される。
・π（ｉ）により示される状態ｉでの相対的なプログレスのインターバル。
・ｍａｘｑ（ｉ）により示される状態ｉにおける次のワークユニットについて選択するのが可能な最大の品質レベル。
・ｑ（ｉ）により示される状態ｉにおける以前に使用された品質レベル。
したがって、状態のセットはΠ×Ｑ×Ｑとなる。
【００２７】
マルコフデシジョンの問題が構成される第二のエレメントは、遷移確率のセットからなる。ｐijqを、次のワークユニットを処理するための品質レベルｑが選択される場合、現在のマイルストーンでの状態ｉから次のマイルストーンでの状態ｊへの遷移をなす遷移確率を示すとする。遷移の後、ｑ（ｉ）＝ｑ及びｍａｘｑ（ｉ）≧ｑであり、これはｑ≠ｑ（ｊ）又はｑ＞ｍａｘｑ（ｉ）の場合にｐijq＝０であることを意味する。
【００２８】
一般性を欠くことなしに、アプリケーションがマイルストーンｍで状態ｉにあると仮定する。それぞれの品質レベルｑについて、ランダム変数Ｘqを導入し、これは品質レベルｑにおける１つのワークユニットを処理するのにアプリケーションが必要な時間を与える。アプリケーションが周期Ｐ当たり計算のバジェットｂを受けるとする場合、相対的なプログレスρm+1は、再帰的な式によりρmで表現することができる。
【００２９】
【数３】
2007515866.tif 000007
ここで表記が使用される。
【００３０】
【数４】
2007515866.tif 000008
Ｙπ,ρm,maxqm,maxqm+1は、ランダム変数とし、このランダム変数は、現在のマイルストーンでの相対的なプログレスはρmであり、最大の品質レベルはｍａｘｑm+1であり、品質レベルｑが選択されると仮定して、次のマイルストーンｍ＋１でのアプリケーションの相対的なプログレスρm+1はプログレスのインターバルπにある確率を与え、このマイルストーンで選択することができる最大の品質レベルはｍａｘｑm+1である。
【００３１】
変数Ｙπ,ρm,maxqm,maxqm+1は、２つの独立なイベントの確率を記載し、次のマイルストーンにおけるアプリケーションは、プログレスのインターバルπにあり、最大の品質レベルｍａｘｑmは、ｍａｘｑm+1に設定される。したがって、以下を得る。
【００３２】
【数５】
2007515866.tif 000009
その後、以下が導出される。
【００３３】
【数６】
2007515866.tif 000010
ＦqはＸqの累積の分布関数を示し、インターバル
【００３４】
【数７】
2007515866.tif 000011
における最も低い値を選択することでρmの悲観的な近似をなす。上記が与えられると、確率ｐijqは以下により近似することができる。
【００３５】
【数８】
2007515866.tif 000012
更に多くのプログレスのインターバルが選択され、より正確な遷移確率のモデリングが行われると、式（３）における近似が良好になる。
【００３６】
マルコフデシジョンの問題を構成する第三のエレメントは、レベニュー“revenue”である。状態ｉでの品質レベルｑを選択するレベニューはｒiqにより示される。レベニューは、３つの問題の目的を実現するために使用される。
【００３７】
はじめに、ワークユニットが処理される品質レベルは、できるだけ高くあるべきである。これは、関数ｕ（ｑ）により与えられる、それぞれｒiqに報酬を割り当てることで実現される。この関数は、ユーティリティ関数と呼ばれる。この関数は、品質レベルｑで実行されているアプリケーションの出力の知覚される品質に直接関連される正の値をリターンする。
【００３８】
第二に、デッドラインのミスの数は、できるだけ低くするべきである。デッドラインのミスのペナルティ関数は、品質レベルｑが現在の状態で選択される場合に、ミスするのを期待するデッドラインの数に関連する正の値をリターンする。この値は、レベニューから引かれる。最後に、品質レベルの変化の数は、できるだけ低くあるべきである。これは、それぞれのｒiqからｃ（ｑ（ｉ），ｑ）により与えられるペナルティを引くことで達成される。この関数は、正の値をリターンし、このことは、ｑ（ｉ）≠ｑの場合にｑ（ｉ）とｑとの間のギャップのサイズで増加し、その他の場合にゼロである場合がある。さらに、品質レベルにおける増加は、品質レベルにおける減少よりも低いペナルティが与えられる場合がある。関数ｃ（ｑ（ｉ），ｑ）は、品質の変化の関数と呼ばれる。
【００３９】
有限の数の遷移のみが考慮される場合（いわゆる有限時間の限界）、マルコフデシジョンの問題のソリューションは、ダイナミックプログラミングにより発見される全ての遷移を通したレベニューの合計を最大にするデシジョンストラテジーにより与えられる。しかし、遷移の数を制限することができないので、無限の時間の限界が存在する。そのケースでは、最大化するための有効な基準は、遷移当たりの平均のレベニューにより与えられる。この基準は、全ての遷移が等しく重要であることを強調している。連続近似、ポリシーイタレーション、及びリニアプログラミングのような無限時間の限界のマルコフデシジョンの問題のための多数の解決技法が存在する。たとえば、Martin  L.  Putermanによる“Markov  Decision  Processes:  Discrete  Stochastic  Dynamic  Programming”,  Wiley  Series  in  Probability  and  mathematical  Statistics,  John  Wiley  &  Sons  Inc.  1994、及びD.J.Whiteによる“Markov  Decision  Processes”,  John  Wiley  &  Sons  Inc.  1993を参照されたい。ここで記載される経験について連続近似が使用される。
【００４０】
マルコフデシジョンの問題を解決することで、最適な固定したストラテジーが得られる。ここで「固定した」とは、適用されるデシジョンストラテジーが全てのマイルストーンで同一であること、すなわちマイルストーンの数に依存しないことを意味する。｜Π｜＝３００，ｂ＝４００００μｓについて、例示的な制御ストラテジーが図４に示されている。この図は、たとえば、特定のマイルストーンでの相対的なプログレスが１に等しい場合、及び、前に使用された品質レベルがｑ3であり、次のフレームの最大の品質レベルがｑ3である場合、品質レベルｑ3は、次のワークユニット、すなわち次のフレームを処理するために選択される。
【００４１】
最適性を失うことなしに、いわゆる単調な制御ストラテジーを使用することができ、すなわち前に使用された品質レベル当たり、より高い相対的なプログレスにより、高いか又は等しい品質レベルの選択が得られると仮定することができる。次いで、最適な制御ストラテジーを記憶するため、前に使用された品質レベル当たり、制御ストラテジーが特定の品質レベルから別の品質レベルに変化する相対的なプログレスの境界のみが記憶される必要がある。したがって、制御ストラテジーは、プログレスのインターバルの数に独立であるＯ（｜Ｑ｜2）のスペースの複雑さを有する。
【００４２】
マルコフデシジョンの問題は、アプリケーションが実行を開始する前にオフラインで解くことができる。つぎに、結果的に得られる制御ストラテジーを以下のようにオンラインで適用する。それぞれのマイルストーンで、前に使用された品質及び最大の品質レベルが知られており、アプリケーションの相対的なプログレスが計算される。次いで、次のワークユニットが処理されるべき品質レベルが調べられる。このアプローチは、オーバヘッドを受けない。
【００４３】
経験のための入力として、１２００００フレームからなるビデオ系列のＭＰＥＧ−２信号対雑音比（ＳＮＲ）デコーディングトレースファイルが使用される。このトレースファイルは、それぞれのフレームについて、増加する品質レベルの順序で、ｑ0〜ｑ3にまでラベル付けされる、４つの異なる品質レベルのそれぞれにおいて、ＴｒｉＭｅｄｉａでのＣＰＵサイクルで表現される、それをデコードするために必要とされる処理時間を含む。すなわち、エンハンスメントレイヤの数は３に設定され、全てのレイヤのビットレートは等しい。
【００４４】
本発明の評価における最初のステップとして、ある最大の品質レベルから別の品質レベルへの遷移の確率が等しいことが想定される。したがって、マイルストーンｍで、変数Ｙmaxqm,maxqm+1は、如何なるペアｍａｘｑm及びｍａｘｑm+1について同じ値を有する。
【００４５】
第二に、問題のパラメータは、以下のように定義される。相対的なプログレスｐでの上限は、２に等しく選択され、これは、少なくとも２つのデコードされたフレームを記憶することができる出力バッファが使用されるものとする。また、入力バッファが何れかの時間の瞬間で少なくとも２つのフレームを含むとする。ビデオの知覚的な品質は、ビデオストリームの実際のビットレートに依存し、これは品質レベルに直接連結される。それぞれの品質レベルの増加によりファクタ２だけ品質のファクタが増加されるとすると、ユーティリティ関数は、ｕ（ｑ0）＝２  ｕ（ｑ1）＝４  ｕ（ｑ2）＝７．５  ｕ（ｑ3）＝１２、により定義される。
【００４６】
デッドラインのミスのペナルティは１０００００に等しく選択され、これは８０００フレーム当たりおおまかに約１つのデッドラインのミスが許容されることを意味する。言い換えれば、５秒のビデオ当たり多くとも１フレームがスキップされる。
【００４７】
品質レベルを増加する品質レベルの変化のペナルティは５に設定され、品質レベルが１、２及び３によりそれぞれ増加される場合に５、５０及び５００に設定される。品質レベルを減少するため、ペナルティは１、２及び３レベルでそれぞれ減少するために５０，５００及び５０００に設定される。状態ｊにおける利用可能なレイヤの数が与えられると、状態ｊの最大品質レベルがｑ（ｊ）に等しいため、品質レベルがｑ（ｉ）〜ｑ（ｊ）に減少される場合、これは強制された変化であると考えられ、品質レベルの変化のペナルティは、ゼロに設定される。
【００４８】
できるだけ多くのレイヤが所与のＣＰＵのバジェットでデコードされる簡単なアルゴリズムに本発明を比較する評価が行われる。先に記載されたように、連続的なアルゴリズムは、問題の瞬間を解くために使用される。計算の不正確さから離れて、連続的な近似は、最適な制御ストラテジーを発見する。０．００１の値は不正確さの耐性のために使用された。結果的に得られる制御ストラテジーは、相対的なプログレス、前に使用された品質レベル、及び最大の品質レベルが与えられると、それぞれのマイルストーンで次のフレームがデコードされるべき品質レベルを与える。
【００４９】
ｉ．テスト１  
最初のテストは、４０ｍｓ及び最大の品質レベルのバジェットを使用し、ネットワークのスループットが全てのレイヤの伝達について十分であるとしている。表２は、本発明のスケーラブルアプリケーションの品質レベルにおける変化を含む。表３は、簡単なアプリケーションの品質レベルにおける変化を含む。表２及び表３に示されるように、簡単なアルゴリズムは、平均して４番目のフレーム毎の品質レベルにおける変化をなし、本発明によりなされる変化の数の１３００倍である。同時に、表４に例示されるように本発明のスケーラブルアプリケーションの平均の品質は、簡単なアプリケーションについてよりも高く、表４は、品質レベルの使用量のパーセンテージを例示する。
【００５０】
【表２】
2007515866.tif 000013
表２−テスト１におけるスケーラブルアプリケーションの品質レベルの変化
【００５１】
【表３】
2007515866.tif 000014
表３−テスト１における簡単（straightforward）なアプリケーションの品質レベルの変化
【００５２】
【表４】
2007515866.tif 000015
表４−テスト１における品質レベルの使用量におけるパーセンテージ
ｉｉ．テスト２  
第二のテストについて、予算は４０ｍｓであり、フレームを処理するために選択することができる最大の品質レベル（バッファで利用可能なフレームのレイヤ数）はランダムに生成される。表５〜表７で示されるように、（最大の品質レベルの変化の数が１２２８であるとき）第二のテストでは、本発明のスケーラブルアプリケーションによりなされる幾つかの変化はあるレベルから別のレベルへの頻繁に発生する遷移を平滑化する試みにより生じる。
【００５３】
【表５】
2007515866.tif 000016
表５−テスト２におけるスケーラブルアプリケーションの品質レベルの変化
【００５４】
【表６】
2007515866.tif 000017
表６−テスト２における簡単なアプリケーションの品質レベルの変化
【００５５】
【表７】
2007515866.tif 000018
表７−品質レベルの使用量のパーセンテージ
ｉｉｉ．比較  
両方のアプリケーションは、デッドラインのミスを受ける。図６は、バジェット及び固定された最大品質レベルを変えるために両方のアプリケーションのデッドラインのミスと平均品質レベルのパーセンテージを例示している。簡単なアプリケーションは、所与のＣＰＵバジェットで残されつつ、異なる品質レベル間で容易に移動する。したがって、低いＣＰＵバジェットの状態下で、簡単なアプリケーションの平均品質は、本発明の平均品質よりもかなり高い。しかし、品質レベルにおける不必要な増加のペナルティは、膨大な数のデッドラインのミスである。本発明の好適な実施の形態のスケーラブルビデオアプリケーションは、所与のＣＰＵバジェットのデッドラインのミスが８０００フレーム当たり１の予め定義された制限にあることを保証することができる後にのみ品質レベルの増加を許容する。
【００５６】
図７は、最大の品質レベルがランダムに選択されたときのケースについて結果を示している。図７から分かるように、最大の品質レベルが頻繁に変化するとき、簡単なアプリケーションは、平均で、本発明のスケーラブルアプリケーションよりも高い品質を有する。これは、スケーラブルアプリケーションが品質レベルのジャンプを平滑にした事実により引き起こされ、これにより品質レベルが下がった後に品質レベルの緩やかな成長となる。
【００５７】
固定されたＣＰＵバジェットを有するスケーラブルメディア処理アプリケーションの品質レベルの制御は、モデルは、マイルストーンで計算されたアプリケーションの相対的なプログレス、及び、アプリケーションの入力バッファにおける（たとえば受信されたレイヤといった）利用可能なビデオデータの量に基づいている。３つの目的は、品質レベルを選択するために適合され、受信されたレイヤの数により決定される最大の品質レベルを考慮して、１．品質レベルが最大にされ、２．デッドラインのミスが最小にされ、３．品質レベルの変化が最小にされる。後処理は考慮されない。
【００５８】
これらの目的を再始動して、品質レベルの制御ストラテジーは、スケーラブルメディア処理アプリケーションについて開発され、これは、品質レベルを最大にしつつ、デッドラインのミスの数及び品質レベルの変化の数の両者を最小にするように、固定されたＣＰＵバジェットが割り当てられている。モデルにおけるパラメータは、品質レベルの変化の数である。変化の数が少ないと、視聴される画像が平滑化される。
【００５９】
図８は、概念的なやり方で本発明に係るシステム１２００を例示している。システム１２００は、ソフトウェアバス１２０８を介して中央処理ユニット１２１０と通信するメモリ１２０２を有する。メモリ１２０２は、先に記載されたようにメディアフレームを処理するために使用されるＣＰＵサイクルの量を決定するために設計されるコンピュータ読取り可能なコード１２０４を有する。さらに、メモリ１２０２は、マイルストーンで計算されたメディア処理アプリケーションの相対的なプログレスに基づいてメディアフレームの品質レベルを制御するために設計されるコンピュータ読取り可能なコード１２０６を有する。好ましくは、メディアフレームを処理する品質レベルは、先に記載された多数のメディアフレームを処理するためにモデル化されるマルコフデシジョンの問題に基づいて設定される。コンピュータ読取り可能なコードは、本発明に係る方法を実行するために設計されるコンピュータプログラムプロダクトを有するストレージ装置１２１２から更新することができる。ストレージ装置は、システム１２００に接続される、たとえばＣＤリーダ１２１４といった適切な読取装置により読取られる。システムは、ハードウェア及びソフトウェアの両者で、又はソフトウェアを動作可能な他の標準的なアーキテクチャで実現することができる。
【００６０】
図９は、本発明に係るシステムの実施の形態を有する、概念的な方法での本発明に係るテレビジョンセット１３１０を例示している。ここで、アンテナ１３３０は、テレビジョン信号を受信する。たとえばサテライトディッシュ、ケーブル、ストレージ装置、インターネット、又はイーサネット（登録商標）のようなテレビジョン信号を受信又は再生可能な装置もアンテナ１３００を置き換えることができる。受信機１３０２は、テレビジョン信号を受信する。受信機１３０２の代わりに、テレビジョンセットは、たとえばプログラマブル集積回路といったプログラマブルコンポーネント１３０４を含む。このプログラマブルコンポーネントは、本発明に従ってシステム１３０６を含む。テレビジョンスクリーン１３０８は、受信機１３０２により受信され、プログラマブルコンポーネント１３０４により処理される文書を表示する。テレビジョンセット１３１０は、任意に、テレビジョン信号を供給するＤＶＤプレーヤ１３１２を有するか、ＤＶＤプレーヤに接続することができる。
【００６１】
図１０は、概念的なやり方で、本発明に係るシステムの実施の形態を有するセットトップボックス１４０２の大部分の重要な部分を説明する。ここで、アンテナ１４００は、テレビジョン信号を受信する。また、アンテナは、たとえばサテライトディッシュ、ケーブル、ストレージ装置、インターネット、又はテレビジョン信号を受信可能な他の装置である場合があり、セットトップボックス１４０２は、信号を受信する。信号はたとえばデジタルである。ここでは示されないが、セットトップボックスに含まれる通常の部材の他に、セットトップボックスは、本発明１４０４に係るシステムを含む。テレビジョン信号は、セットトップボックス１４０２に接続されるテレビジョンセット１４０６で表示される。
【００６２】
先に記載された実施の形態は本発明を限定するよりはむしろ例示するものであり、当業者であれば、特許請求の範囲から逸脱することなしに多くの代替的な実施の形態を設計することが可能である。本発明は、幾つかの個別のエレメントを有するハードウェア、適切にプログラムされたコンピュータにより実現される。さらに、特定の状況に適合するために多くの変更がなされ、本発明の教示は、その中心的な範囲から逸脱することなしに等価であるやり方で適合することができる。したがって、本発明を実行することが意図される最良のモードとして開示される特定の実施の形態に本発明が制限されることが意図されないが、本発明は特許請求の範囲に含まれる全ての実施の形態を含むことが意図される。
【図面の簡単な説明】
【００６３】
【図１】スケーラブルビデオアプリケーションの一般的なビューを例示する図である。
【図２】本発明の実施の形態に係るスケーラブルビデオアプリケーションの例示的なタイムラインを説明する図である。
【図３】デッドライン（ｄ3）が失われた例示的なタイムラインを説明する図である。
【図４】本発明に係る最適なストラテジーのためのｑ0、ｑ1、ｑ2及びｑ3についての前に使用された品質レベルに対する相対的なプログレスを説明する図であり、ここでｂ＝４００００及び｜Π｜＝３００。
【図５】本発明に係るスケーラブルアプリケーションの挙動を説明する図である。
【図６】簡単な用途との本発明に係るスケーラブルビデオアプリケーションの定量的な比較を説明する図である。
【図７】最大の品質レベルの１０００の変化について本発明にかかるスケーラブルビデオアプリケーションの定量的な比較を説明する図である。
【図８】本発明の実施の形態に係るシステムのアーキテクチャを説明する簡略化されたブロック図である。
【図９】本発明に従って変更されたＴＶセットを説明する図である。
【図１０】本発明に従って変更されたセットトップボックスを説明する図である。
【図１】
2007515866.tif 000019
【図２】
2007515866.tif 000020
【図３】
2007515866.tif 000021
【図４ａ】
2007515866.tif 000022
【図４ｂ】
2007515866.tif 000023
【図４ｃ】
2007515866.tif 000024
【図４ｄ】
2007515866.tif 000025
【図５】
2007515866.tif 000026
【図６】
2007515866.tif 000027
【図７】
2007515866.tif 000028
【図８】
2007515866.tif 000029
【図９】
2007515866.tif 000030
【図１０】
2007515866.tif 000031
【国際調査報告】
2007515866.tif 000032
2007515866.tif 000033
2007515866.tif 000034