(57)【要約】【課題】  改良された手法で、マルチメディアフレームを処理する品質レベルの変更を制御する、品質レベルの制御戦略を用いる方法を提供すること。【解決手段】  本発明は、環境が拘束されている時間およびリソース内で、理解されているユーザ品質の最大化を達成するために用いることができるマルコフ決定問題のような、適合可能なスケジューリングおよびリソース制御技術に関する。
2005512465.tif 000002
【特許請求の範囲】
【請求項１】
マルチメディアフレームを処理するために用いられるリソース量を決定するステップと、
マイルストーンで計算された前記マルチメディア処理アプリケーションの相対的な進度に基づいて前記マルチメディアフレームの品質を制御するステップと、
を備える、
マルチメディア処理アプリケーションによるマルチメディアフレームの品質設定方法。
【請求項２】
前記マルチメディアフレームの前記品質を制御するステップは、1組の状態、1組の決定、1組の転移確率、および1組の収益を備えているマルコフ決定問題としてモデル化することであって、
この方法は、
マイルストーンでの前記マルチメディア処理アプリケーションの前記相対的な進度と、以前のマルチメディアフレームの、以前に用いられた品質とを備える前記1組の状態を規定するステップと、
前記マルチメディア処理アプリケーションを提供することができる複数の品質を備える前記1組の決定を規定するステップと、
前記複数の品質から1つの品質が選択される場合に、現在のマイルストーンでの前記1組の状態の一の状態から、次のマイルストーンでの前記1組の状態の他の状態に転移する確率を備える前記1組の転移確率を規定するステップと、
前記マルチメディアフレームのプラスの品質に関連するプラスの収益と、デッドライン・ミスに関連するマイナスの収益と、品質変更に関連するマイナスの収益と、を備える前記1組の収益を規定するステップと、
を備え、
決定戦略を用いることによってこのマルコフ決定問題を解き、かつ、この解に基づいて前記マルチメディアフレームの前記品質を設定する、請求項1に記載のマルチメディアフレームの品質設定方法。
【請求項３】
前記決定戦略は、全ての前記転移に渡って収益の合計を最大化するステップを備える、請求項2に記載のマルチメディアフレームの品質設定方法。
【請求項４】
前記決定戦略は、前記転移あたりの平均的な収益を最大化するステップを備える、請求項2に記載のマルチメディアフレームの品質設定方法。
【請求項５】
マルチメディアフレームを処理するために用いられるリソース量を決定するように着想された決定手段と、
マイルストーンで計算された前記マルチメディア処理アプリケーションの相対的な進度に基づいて前記マルチメディアフレームの品質を制御するように着想された制御手段と、
を備える、
マルチメディア処理アプリケーションによるマルチメディアフレームの品質設定方法。
【請求項６】
前記制御手段は、1組の状態、1組の決定、1組の転移確率、および1組の収益を備えているマルコフ決定問題として前記マルチメディアフレームの前記品質の前記制御をモデル化すると着想されており、
前記1組の状態は、マイルストーンでの前記マルチメディア処理アプリケーションの前記相対的な進度と、以前のマルチメディアフレームの、以前に用いられた品質とを備え、
前記1組の決定は、前記マルチメディア処理アプリケーションを提供することができる複数の品質を備え、
前記1組の転移確率は、前記複数の品質から1つの品質が選択される場合に、現在のマイルストーンでの前記1組の状態の一の状態から、次のマイルストーンでの前記1組の状態の他方の状態に転移させる確率を備え、
前記1組の収益は、前記マルチメディアフレームのプラスの品質に関連するプラスの収益と、デッドライン・ミスに関連するマイナスの収益と、品質変更に関連するマイナスの収益とを備え、
前記制御手段は、さらに、決定戦略を用いることによってこのマルコフ決定問題を解き、かつ、この解に基づいて前記マルチメディアフレームの前記品質を設定ように着想された、請求項5に記載のマルチメディアフレームの品質設定方法。
【請求項７】
請求項1に記載の方法を遂行するように設計されているコンピュータプログラム製品。
【請求項８】
請求項7に記載のコンピュータプログラム製品を備えている記憶デバイス。
【請求項９】
請求項6に記載のシステムを備えているテレビ機器。
【請求項１０】
請求項6に記載のシステムを備えているセットトップボックス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチメディアフレームの品質を設定する方法に関する。
【０００２】
本発明は、更に、マルチメディアフレームの品質を設定するシステムに関する。
【０００３】
本発明は、更に、このような方法を遂行するように設計されているコンピュータプログラム製品に関する。
【０００４】
本発明は、更に、このようなコンピュータプログラム製品を備えている記憶デバイスに関する。
【０００５】
本発明は、更に、このようなシステムを備えているテレビおよびセットトップボックスに関する。
【背景技術】
【０００６】
上記の種類の方法およびシステムの実施例は、引用文献1に記載されている。ここでは、アルゴリズムを実行する方法、および、VCR、DVD−RW、ハードディスク、またはインターネット接続のようなシステムの、スケーラブルなプログラムが可能なデバイスについて説明されている。このアルゴリズムは、マルチメディアフレーム（たとえば、ビデオフレーム）を処理するように設計されていて、複数の品質レベルの処理を提供する。各々の品質レベルには、ある量のリソースが必要である。マルチメディアフレームの受け入れ可能な出力品質を提供するために、異なる品質レベルに対する異なる必要条件に従って、利用可能なリソースのバジェットが、アルゴリズムに割り当てられる。しかしながら、時間の経過により、マルチメディアストリームのコンテンツが変わるので、結局、マルチメディア処理アルゴリズムのリソースの必要条件は、時間の経過とともに異なる。リソースは有限であるので、デッドライン・ミスが発生する可能性がある。これを軽減するために、マルチメディアアルゴリズムを、デフォルトの品質レベルよりも低い品質レベルで動作させ、これにより、リソース要求が低くなる。
【０００７】
本発明の目的は、改良された方法でマルチメディアフレームを処理する品質レベルの変更を制御する、品質レベルの制御戦略を用いた於いて書きの方法を提供することである。
【０００８】
【特許文献１】欧州特許第0109691出願明細書（代理人参照番号PHNL010327）
【発明の開示】
【課題を解決するための手段】
【０００９】
この目的を達成するために、マルチメディア処理アプリケーションによってマルチメディアフレームの品質を設定する方法は、
前記マルチメディアフレームを処理するために用いられるリソース量を決定するステップと、
マイルストーンで計算された前記マルチメディア処理アプリケーションの相対的な進度に基づいて前記マルチメディアフレームの前記品質を制御するステップと、
を備える。
【００１０】
デッドライン期間と表現される、マイルストーンのデッドラインまでの時間のような、周期的なデッドラインに関する、アプリケーションの相対的な進度を用いることによって、デッドライン・ミスが発生しそうか否かを決定することができる。デッドライン・ミスを防止するために、マルチメディア処理アルゴリズムの品質を、マイルストーンで、適合化させることができる。これにより、マルチメディアフレームを、ユーザによって了解される品質に、改良することができる。品質レベルを変更することは、ユーザにより無品質とみなされる場合があるので、許容可能な品質レベルを保持しつつ、品質レベルの変更の数をよりよく制御することができるということは、更なる利点である。
【００１１】
本発明の方法の実施例は、請求項2で説明されている。品質制御戦略を、マルコフ決定問題としてモデル化することによって、品質制御戦略を、確率論的な決定問題と見ることができる。確率論的な決定問題は、1980年に、アムステルダムの数学センターの、J.van der Wal著の確率論的な動的計画法（Stochastic Dynamic Programming）という博士論文に開示されている。マルコフ決定問題を解くことによって、異なる戦略の品質効果を、より容易に予測することができる。
【００１２】
本発明の方法の実施例は、請求項3で説明されている。全ての転移に渡って収益の合計を最大化する決定戦略を用いることによって、デッドライン・ミスを、よりよく防止することができる。
【００１３】
本発明の方法の実施例は、請求項4で説明されている。転移あたりの平均的な収益を最大化する決定戦略を用いることによって、品質変更の数を、よりよく制御することができる。
【００１４】
更なる本発明の目的は、改良された手法で、品質レベルの変更を制御する、品質レベルの制御戦略を用いる、於いて書きのシステムを提供することである。この目的を達成するために、マルチメディア処理アプリケーションによってマルチメディアフレームの品質を設定するシステムは、
前記マルチメディアフレームを処理するために用いられるリソース量を決定するように着想された決定手段と、
マイルストーンで計算された前記マルチメディア処理アプリケーションの相対的な進度に基づいて前記マルチメディアフレームの前記品質を制御するように着想された制御手段と、
を備える。
【発明を実施するための最良の形態】
【００１５】
本発明のこれらのおよび他の態様は、各図に示すように以下に記載する実施例の参照により説明され、かつ、明らかになる。
【００１６】
今日、多くのマルチメディア処理アプリケーションは、ある時間内でかなり変化するCPU負荷を生成する。それゆえ、最悪な場合の負荷状況で必要なものよりも低いCPUバジェットが、このようなメディア処理アプリケーションに、割り当てられる場合には、デッドライン・ミスが発生しやすくなる。この問題は、マルチメディア処理アプリケーションをスケーラブルな形態で設計することによって、低減させることができる。スケーラブルなマルチメディア処理アプリケーションは、デフォルトの品質レベルよりも低い品質で動作させることができるので、リソース要求が低くなる。1つの問題は、CPUの固定バジェットが割り当てられていた、スケーラブルなマルチメディア処理アプリケーションに対する品質レベルの制御戦略を見い出すことである。このような制御戦略は、品質レベルを最大にしつつ、デッドライン・ミスの数および品質レベル変更の数を最小にすべきである。
【００１７】
本発明によれば、この問題は、マルコフ決定問題としてモデル化される。このモデルは、アプリケーションのマイルストーンで、アプリケーションの相対的な進度を計算することに基づく。マルコフ決定問題を解くことは、実行時間の間に、少しのオーバーヘッドのみで適合化させることができる品質レベルの制御戦略に帰する。このアプローチは、スケーラブルなMPEG-2デコーダに関連する実際の具体例によって評価される。
【００１８】
セットトップボックス、およびデジタル・テレビ機器のような、消費者向けの端末装置は、オープンでかつ適応性があることを、市場は要求する。これは、特定のマルチメディア処理アプリケーションを遂行するいくつかの専用のハードウェア素子を、等価のマルチメディア処理アプリケーションが実行される中央演算処理装置（CPU）によって置換することによって達成される。CPU時間、メモリ、およびバス帯域幅のようなリソースは、これらのアプリケーションの間で共有される。ここで、CPUのリソースについて、考察することは好ましい。
【００１９】
マルチメディア処理アプリケーションは、2つの重要な特性を有する。第1の特性として、マルチメディア処理アプリケーションは、ある時間内でかなり変化する可能性があるリソース要求を有する。これは、マルチメディア処理アプリケーションが処理する、マルチメディアデータのサイズおよび複雑さの変化に起因する。第2の特性として、マルチメディア処理アプリケーションは、たとえば、出力が一時的に中断することを回避するために、ミスされることが無いデッドラインが結果的に得られる、リアルタイム要求を有する。それゆえ、少なくとも、最悪の場合の負荷状況で必要とされるリソース量を、マルチメディア処理アプリケーションに割り当てることによって、理想的な処理動作が得られる。しかしながら、CPUは専用素子と比較して高価である。費用効率を高めるためには、リソース量は、平均的な負荷状況により近い状況に割り当てられるべきである。これは、一般的に、マルチメディア処理アプリケーションが、これらのリアルタイム要求を満たすことができない状況をもたらす。
【００２０】
この問題は、マルチメディア処理アプリケーションを、デフォルトの品質レベルよりも低い品質で動作させ、リソース要求がこれに対応して低くなるように設計することにより、対処することができる。このようなスケーラブルなマルチメディア処理アプリケーションは、デッドライン・ミスが発生する危険がある場合には、その品質レベルを減らすように設定される。このようにして、リアルタイム要求を満たすことができ、この結果、システムが頑丈になる。
【００２１】
一つのスケーラブルなマルチメディア処理アプリケーション（以下では、「アプリケーション」と称する）について考察する。このアプリケーションは、絶えず、入力バッファから作業ユニットをフェッチして、それらを処理して、それらを出力バッファに書き込む。このために、このアプリケーションは、固定されたバジェットを、処理のために周期的に受けとる。処理のサイズおよび複雑さは、作業ユニットごとに、異なっていても良いので、一つの作業ユニットを処理するために必要な時間は、固定されていない。一つの作業ユニットの完了は、マイルストーンと呼ばれている。各々のマイルストーンには、デッドラインが存在する。これらのデッドラインは、時間的に完全に周期的であると仮定されている。デッドライン・ミスが、防止されるべきであることは、明らかである。
【００２２】
各々のマイルストーンで、周期的なデッドラインに対する相対的な進度が、アプリケーションについて計算される。マイルストーンでの相対的な進度は、デッドライン期間と表現される、マイルストーンのデッドラインまでの時間として、規定されている。この相対的な進度が、負であってはならないことは明らかである。さらに、バッファ・サイズに制限があるために、相対的な進度には上限がある。
【００２３】
相対的な進度が、マイルストーンで、負であることが判明した場合、一つ以上のデッドライン・ミスが発生したことになる。これを防止するために、アプリケーションが各々のマイルストーンで実行する品質レベルが、適合化される。この問題は、以下の3つの目的が満たされるように、この品質レベルを選択することである。第1に、作業ユニットが処理される品質レベルは、できる限り高くすべきである。第2に、デッドライン・ミスの数は、できる限り小さくすべきである。最後に、品質レベルの変更が無品質とみなされるので、品質レベル変更の数も、できる限り小さくすべきである。
【００２４】
その結果得られる品質レベルの制御戦略は、オンラインで適用されるべきであり、かつアプリケーションと同じCPUによって実行されることに留意されたい。それゆえ、品質レベルの制御戦略は、要求されるCPU時間の量において、効率的であるべきである。
【００２５】
確率論的な決定問題を取り扱う一般的な手法は、それを、マルコフ決定問題としてモデル化することである。1980年、アムステルダムの数学センターの、J. vander Wal著の確率論的な動的計画法（Stochastic Dynamic Programming）という博士論文を参照されたい。
【００２６】
アプリケーションの相対的な進度は、各々のマイルストーンで、計算される。ここで、マイルストーンでの相対的な進度は、デッドライン期間と表現される、マイルストーンのデッドラインまでの時間として、規定されている。
【００２７】
マイルストーンでの相対的な進度は、以下のように計算することができる。一般性を失うことなく、アプリケーションが、時刻t＝0で処理を始めると仮定する。マイルストーンmの時刻は、cmと表示される。つぎに、マイルストーンmのデッドラインは、dmと表示される。各デッドラインは、完全に周期的であり、それらは、以下のように記すことができることを意味する。
2005512465.tif 000003
ここで、Pは2つの逐次デッドライン間の期間であり、d0はオフセットである。つぎに、ρmと表示される、マイルストーンmでの相対的な進度は、方程式(1)により与えられる。
2005512465.tif 000004
【００２８】
各相対的な進度の計算を示すために、図1に示されるタイムラインの例について考察する。この例では、P＝1、かつ、d0＝1である。方程式（1）を用いることによって計算される、マイルストーン1から5までの相対的な進度は、ρ1＝（d1−c1）／P＝（2−1）／1＝1、ρ2＝1.5、ρ3＝1、ρ4＝0、およびρ5＝0.5となる。マイルストーン4は、時間のずれがないことに留意すべきである。
【００２９】
マイルストーンmでの相対的な進度が、ゼロ以下に低下する場合には、［−ρm］のデッドライン・ミスが、以前のマイルストーンから発生していたことになる。デッドライン・ミスに対処する方法は、アプリケーションに固有である。ここで、生成されたばかりの出力が、捨て去られるのではなく、いずれにせよ用いられることを意味する、作業維持アプローチが、仮定される。1つの手法は、この出力を、最初の次のデッドラインで用いることであろう。これは、適合化された相対的な進度ρ'm＝ρm＋［−ρm］≧0が得られていることを意味する。保守的なアプローチは、ρ'm＝0、すなわち、可能最小値を選択することにより、仮定される。これは、ある意味で、生成に応じて即座に出力を用いることに対応する。換言すれば、デッドラインdmおよび次のデッドラインの位置は、−ρmP延期される。その結果、方程式（1）を用いて、マイルストーンでの相対的な進度は、新しいオフセットd'0＝d0−ρmPによって計算することが可能となる。
【００３０】
この処理は、図2に示されるタイムラインの例で示されている。この例では、P＝1、かつ、d0＝0.5である。方程式（1）を用いることによって、ρ1＝0.5、ρ2＝0.5、およびρ3＝−0.5が導出される。マイルストーン3での相対的な進度が、ゼロ以下に低下した。従って、［−ρ3］＝1デッドライン・ミスが、マイルストーン2、すなわち、t＝3.5から発生していたことになる。つぎに、デッドラインd3は、d'3＝c3＝4まで延期され、そして、もっと先の各デッドラインも、0.5ずつ延期されている。続いて、ρ4＝0.5、およびρ5＝0.5が、見出されている。
【００３１】
マイルストーンでのアプリケーションの状態は、当然、その相対的な進度によって与えられる。しかしながら、保守的なアプローチは、無限に多くの組の状態を与えるのに対して、マルコフ決定問題は、有限の組を必要とする。後者は、以下のように達成される。p＞0が、相対的な進度の所定の上限を表示するものとする。0とpとの間の相対的な進度空間は、k＝0，…，n−1に対し、n≧1の進度インターバル
2005512465.tif 000005
の有限設定Π＝｛π0，…，πn-1｝に分割される。進度インターバルπの上限および下限は、それぞれ、
2005512465.tif 000006
および
2005512465.tif 000007
と表示される。
【００３２】
各々のマイルストーンで、次の作業ユニットが処理されるであろう品質レベルが、決定されなければならない。それゆえ、マルコフ決定問題における1組の決定は、アプリケーションが実行可能となる1組の品質レベルに対応する。この組は、Qと表示される。
【００３３】
品質レベルの変更も、考察される。したがって、以前に用いられた品質レベルは、各々のマイルストーンで、知られていなければならない。これは、品質レベルとともに1組の状態を延長することによって、実現させることができる。それゆえ、1組の状態は、Π×Qになる。状態iにおけるアプリケーションの、進度インターバルおよび以前に用いられた品質レベルは、それぞれ、π（i）およびq（i）で表示される。
【００３４】
マルコフ決定問題が含む第2の要素は、転移確率である。次の作業ユニットを処理するのに品質レベルqが選択される場合には、現在のマイルストーンで状態iから、次のマイルストーンで状態jまで、転移させるための転移確率は
2005512465.tif 000008
と表示される。転移の後、q（j）＝qとなり、これは、q≠q（j）の場合には、
2005512465.tif 000009
となることを意味する。
【００３５】
他の場合の転移確率は、以下のように導出される。アプリケーションが、マイルストーンmで、状態iであると、一般性を失うことなく、仮定しよう。各々の品質レベルqに対して、我々は、アプリケーションが、品質レベルqで1つの作業ユニットを処理するために必要である時間を与える、確率変数Xqを導入する。アプリケーションが、期間Pにつき、計算バジェットbを受けとると仮定する場合には、相対的な進度ρm＋1は、再帰方程式（2）によってρmで表現することができる。
2005512465.tif 000010
ここで、次の関係が用いられる。
2005512465.tif 000011
【００３６】
現在のマイルストーンでの相対的な進度がρmであり、品質レベルqが選択されるという条件ならば、次のマイルストーンでのアプリケーションの相対的な進度ρm＋1が、進度インターバルπ内であるという確率を与える確率変数を、Yπρmqとする。その後、確率変数Yπρmqは、以下のように導出される。すなわち、
2005512465.tif 000012
【００３７】
Xqの累積分布関数をFqと表示する。再帰方程式（2）を用いることによって、0＜x≦pの場合、
2005512465.tif 000013
が導出される。
【００３８】
x＝0の場合、P(ρm+1≧x)＝1となる。これは、方程式（2）から直接わかる。
【００３９】
残念なことに、進度インターバルπ（i）内のρmの位置は、未知である。ρmの悲観的な近似値は、インターバルの最も低い数値を選択することによって得られる。これは、近似値を与える。
2005512465.tif 000014
【００４０】
上記のように近似値を与えることで、確率
2005512465.tif 000015
を、以下のように、近似することができる。
2005512465.tif 000016
【００４１】
進度インターバルを選択すればするほど、（3）の近似値は良くなるので、転移確率が、ますます正確にモデル化される。
【００４２】
マルコフ決定問題が含む第3の要素は、収益である。状態iにおける品質レベルqを選択するための収益は、
2005512465.tif 000017
と表示される。収益は、第3の問題対象を実現するために用いられる。
【００４３】
第1に、作業ユニットを処理する品質レベルは、できる限り高くすべきである。これは、関数u（q）によって与えられる報酬を、各
2005512465.tif 000018
に割り当てることによって実現される。この関数は、効用関数と称される。この関数は、品質レベルqで実行しているアプリケーションの出力の了解される品質に直接関連して、プラスの数値に戻る。
【００４４】
第2に、デッドライン・ミスの数を、できる限り少なくすべきである。マイルストーンでの相対的な進度がゼロ以下に低下する場合には、1つ以上のデッドライン・ミスが発生したことになる。アプリケーションが、マイルストーンmで、状態iであると仮定するならば、予想されるデッドライン・ミスの数は、マイルストーンm＋1に到達する前に、以下のように与えられる。
2005512465.tif 000019
【００４５】
この予想されたデッドライン・ミスの数にプラスの定数（デッドライン・ミス・ペナルティと呼ばれる）を乗算した後、我々は、デッドライン・ミスにペナルティを実行するために、各
2005512465.tif 000020
からそれを減算する。
【００４６】
最後に、品質レベル変更の数は、できる限り小さくすべきである。これは、各
2005512465.tif 000021
から、関数c（q（i），q）によって与えられるペナルティを減算することによって達成される。この関数は、プラスの数値に戻る。これにより、q（i）≠<i> </i>q、かつ、そうでなければ0の場合には、q（i）とqとの間のギャップのサイズが増加する。さらに、品質レベルの向上に、品質レベルの低下よりも低いペナルティを与えることが出来る。関数c（q（i），q）は、品質変更関数と称される。
【００４７】
有限数の転移（いわゆる有限時間範囲）のみ考察すれば、マルコフ決定問題の解は、全ての転移に渡る収益の合計を最大化する決定戦略によって与えられる。これは、動的計画法によって見い出すことができる。しかしながら、我々は、転移の数を制限することができないので、無限時間範囲について考察する。その場合、全ての転移に渡って収益の合計の最大化のために役立つ基準というのは、転移あたりの平均的な収益によって与えられる。この基準は、全ての転移が一様に重要であると強調する。無限時間範囲のマルコフ決定問題のためには、多くの解法（例えば、逐次近似、政策反復および線形計画法）がある。たとえば、ジョン・ワイリー社1994発行のMartinL. Puterman著の確率および数学的確率（Probability and Mathematical Statistics）のワイリーシリーズの、マルコフ決定問題：離散的な確率論的な動的計画法（MarkovDecision Processes: Discrete Stochastic Dynamic Programming）、および、ジョン・ワイリー社1993発行のD.J.White著のマルコフ判断処理（Markov Decision Processes）を参照せよ。ここで説明されている実験には、逐次近似が使用されている。
【００４８】
マルコフ決定問題を解くことにより、ステーショナリ戦略が最適になる。ここでのステーショナリは、適合される決定戦略が、全てのマイルストーンで同一であること、すなわち、それが、マイルストーンの数に、依存しないことを意味する。図4には、|Π|＝1014、|Q|＝4、およびp＝2の場合の、制御戦略の例が示されている。これは、たとえば、特定のマイルストーンで、相対的な進度が1で、かつ、以前に用いられた品質レベルがq1である場合には、次の作業ユニットを処理するために、品質レベルq2が選択されるべきである、ということを示している。
【００４９】
最適性を失うことなく、いわゆる単調制御戦略を、用いることができる。すなわち、以前に用いられた品質レベルごとに、より高い相対的な進度は、より高いまたは同等の品質レベルの結果をもたらすと、仮定することができる。その後、最適な制御戦略を格納するために、制御戦略が、特定の品質レベルから他の品質レベルまで変更する相対的な進度の境界のみを、以前に用いられた品質レベルごとに、格納すべきである。それゆえに、制御戦略は、進度インターバルの数から独立している、O(|Q|2)の空間複雑度を有する。
【００５０】
マルコフ決定問題は、アプリケーションが実行を始める前に、オフラインで解くことができる。つぎに、以下のように、我々は、その結果得られる制御戦略を、オンラインで適用する。各々のマイルストーンで、以前に用いられた品質レベルは既知であり、さらに、アプリケーションの相対的な進度が計算される。その後、処理されるべき、次の作業ユニットの品質レベルが調べられる。このアプローチでは、オーバーヘッドがほとんど不要である。
【００５１】
実験に対する入力として、539フレームのムービーフラグメントのMPEG-2デコーディング・トレース・ファイルが使用される。このファイルは、各々のフレームごとに、品質順位が高くなっていくq0からq3までと命名されている4つの品質レベルの各々において、トライメディアでCPUサイクルと表現される、入力をデコードするために必要な処理時間を含む。図３に示されるように、このトレース・ファイルから、各品質レベルに対し、1つのフレームをデコードするために必要な処理時間の累積分布関数が、導出される。図3は、q0からq3までの品質レベルごとに、1つのフレームをデコードするために必要な処理時間の累積分布関数を示す。
【００５２】
問題パラメータは、以下のように規定される。相対的な進度pの上限は2に等しくなるように選択される。これにより、2つのデコードされたフレームを格納することができる出力バッファが用いられることが仮定される。効用関数は、u（q0）＝1、u（q1）＝5、u（q2）＝7.5、およびu（q3）＝10と規定される。デッドライン・ミス・ペナルティは1000に等しくなるように選択される。これは、おおよそ、100フレームあたり約1つのデッドライン・ミスが許されることを意味する。品質変更関数は、品質レベルを増加するための各品質レベル数の差の5倍のペナルティ、および、品質レベルを減少させるためのそれの6倍のペナルティにより、規定される。つぎに、増加ステップが25,000というCPUサイクルを用いて、CPUサイクルを2,200,000から3,600,000まで変化させながら、バジェットbに対して、57の異なる数値を用いる。1.2の乗算ステップによって、|Π|＝30から|Π|＝1014まで変化させながら、各々のバジェットbに対して、20の異なる数の進度インターバルが選択される。このような方法で、総計1140のマルコフ決定問題事例が規定される。
【００５３】
前述したように、逐次近似アルゴリズムは、問題事例を解くために用いられる。計算の不正確性から離れて、このアルゴリズムは、最適な制御戦略を見い出す。我々は、不正確パラメータに対して、0.001という数値を用いる。この結果得られる制御戦略は、相対的な進度と以前に用いた品質レベルに対し、各々のマイルストーンで、次のフレームがデコードされるべき品質レベルを与える。この制御戦略を用いることによって、各々の計算された制御戦略に対する、スケーラブルなMPEG-2デコーダの遂行についてのシミュレーションが行われる。これらのシミュレーションは、539フレームの代わりに30,000フレームからなる、所定の処理時間の配分に基づいて合成的に生成されたトレース・ファイルからの処理時間を利用する。各々のシミュレーションでは、最初の品質レベルとしてq0が選択され、そして、転移あたりの実際の平均的な収益、品質レベルの利用、デッドライン・ミスのパーセンテージ、および品質レベルの変更が、測定される。
【００５４】
1.2の乗算ステップを行うことによって、進度インターバル|Π|の数は30から1014まで変化する。これにより、バジェットあたり20の問題事例の結果が得られる。図4は、b＝3,100,000および|Π|＝1014に対して得られる最適な制御戦略を示す。このように、制御戦略が、実際に用いた品質レベルを維持する傾向を示すことがわかる。
【００５５】
図5は、問題事例を解くために必要とされる計算と、シミュレーションにおいて測定された実際の数値とがわかるように、b＝3,100,000での20の問題事例に対する転移あたりの平均的な収益を示す。シミュレーションでは、制御戦略が、約8.27の値まで急速に収束する。計算の平均的な収益は、（3）の悲観的な近似値に起因して、この数値まで収束するために、より多くの進度インターバルを必要とするにもかかわらず、シミュレーションでは、制御戦略が、|Π|が約200のときに、すぐに、平均的な収益が、約8.27になる。換言すれば、それほど多くの進度インターバルは、最適（それに近い）な制御戦略を見い出すためには不要である。
【００５６】
つぎに、図6〜図8は、|Π|＝1014での全ての問題事例のシミュレーションにおいて測定された収益の3つの要素を示す。図6は、品質レベルの利用を示し、図7は、デッドライン・ミスのパーセンテージを示し、図8は、品質レベルの平均的な増加を示す。品質レベルの平均的な減少量は、品質レベルの平均的な増加量と、ほとんど同じであるため、表していない。バジェットが増加する場合、より頻繁に、高い品質レベルが選択され、かつ、デッドライン・ミスのパーセンテージは、b＝2,650,000で急速にゼロに低下する。大きいバジェットに対して、デッドライン・ミスのパーセンテージが低いのは、デッドライン・ミス・ペナルティが相対的に高いことに起因する。品質レベルの平均的な増加量および平均的な減少量が、低いことが更に観測される。したがって、3つ全ての問題の目的が満たされていると、結論付けることができる。
【００５７】
3つの要素が、平均的な収益にどのように貢献するかと言う例を与えるために、|Π|＝1014およびb＝3,100,000の場合を考察する。この場合、平均的な品質レベルの効用が、0.0033×1＋0.0102×5＋0.5953×7.5＋0.3911×10＝8.43であり、平均的なデッドライン・ミス・ペナルティが、0×1000＝0であり、平均的な品質レベルの増加ペナルティが、0.0145×5＝0.07であり、平均的な品質レベルの減少ペナルティが、0.0144×6＝0.09である。これにより、フレームあたりの平均的な収益の総計が8.27になる。
【００５８】
マルコフ決定問題を逐次近似を用いて解くことは、Π×Qの各々の状態に対する数値を含む性質の状態ベクトルに関係する。通常、状態ベクトルは、ゼロベクトルに初期化される。その後、反復的に、全ての状態に対して最適な判断が決定され、さらに、状態ベクトルがアップデートされる。2つの逐次状態ベクトル間の差が、全ての（またはそれに近い）同一エントリー（転移あたりの平均的な収益）を含む場合、すなわち、最小と最大との差が、指定された不正確な範囲内にある場合には、反復的な進行は終了する。
【００５９】
我々は、各々のバジェットbに対し、異なる数の進度インターバルで、同じマルコフ決定問題を繰り返し解くので、状態ベクトルを初期化するために、異なる方法が使われる。我々が、各々のバジェットbに対して、初めてマルコフ決定問題を解く場合、すなわち、進度インターバルの数が最も低い場合（30）には、初期化のためにゼロベクトルを用いる。次に低い進度インターバルの数の各々に対しては、状態ベクトルは、以前の数の進度インターバルで実行した最後の状態ベクトルを入れることによって初期化される。このようにして、逐次近似アルゴリズムが、収束のために、少ない反復しか必要としないことが期待される。
【００６０】
この補間ベクトル・アプローチが、どれくらいうまく機能するかについてテストするために、このアプローチを、ゼロベクトルを常に最初のベクトルとして選択する直接アプローチと比較する。このために、我々は、進度インターバルの数を、1.5の乗算ステップを行うことによって、|Π|＝30から|Π|＝1749まで変化させ、双方のベクトル・アプローチを用いて、b＝3,100,000の場合のマルコフ決定問題を解いた。図9は、双方のアプローチに必要な反復の数を示す。図10は、PentiumII Xeon 400MHz（登録商標）のプロセッサを用いて測定された、両方のアプローチの計算時間を示す。後の図には、補間ベクトル・アプローチに対する累積的な計算時間も示される。この図は、多数の進度インターバルに対して、このマルコフ決定問題を解く場合には、進度インターバルの数を増加させるために、多くの補間ベクトル・アプローチを用い、かつ、マルコフ決定問題を数回解くことが、より良いことであることを示す。その理由は、我々が、要求される進度インターバルの数に対して、直接、マルコフ決定問題を解く場合よりも、計算の総時間が短くなるからである。
【００６１】
CPUのバジェットが固定されている、スケーラブルなマルチメディア処理アプリケーションに対する品質レベル制御は、マルコフ決定問題としてモデル化された。このモデルは、マイルストーンで計算されるアプリケーションの相対的な進度に基づく。作業ユニットの処理の際の品質レベルを最大化し、デッドライン・ミスの数を最小化し、品質レベルの変更の数を最小化することによって、3つの問題目的が規定された。このモデルのパラメータは、進度インターバルの数である。
【００６２】
進度インターバルを多く選択すればするほど、問題のモデル化はますます正確になる。マルコフ決定問題を解くことは、わずかなオーバーヘッドで、実行時間の間に、適用することができる最適な制御戦略という結果になる。
【００６３】
アプローチを評価するために、スケーラブルなMPEG-2デコーダについて、総計で1140の問題事例が解かれた。その結果得られた制御戦略の各々に対して、デコーダの遂行がシミュレートされた。この実験から、このモデルによる良い近似値を有するために、いくつかの進度インターバルが必要であったが、相対的に少ない進度インターバルによって、最適な制御戦略を得ることができると、結論づけることが出来た。さらに、この実験に対して、アプローチが3つの問題目的に対処すると結論づけることができる。
【００６４】
マルコフ決定問題を、逐次近似を用いて解く場合には、状態ベクトルが、補間ベクトル・アプローチを用いて初期化された。進度インターバルの数を増加させるために、多数の進度インターバルに対して、多くの補間ベクトル・アプローチを用いることができ、かつ、この問題を数回解くことできることが観測される。その理由は、これにより、要求される進度インターバルの数に対して、直接、その問題を解く場合よりも、計算の総数が少なくなるからである。
【００６５】
その結果得られる品質レベルの制御戦略は、オンラインで適用することができ、それにより、アプリケーションを遂行するプロセッサと同じプロセッサで遂行することができる。
【００６６】
他の作業維持アプローチは、最初の次のデッドラインでの出力を用いることである。これにより、適合される相対的な進度ρmは、以下のようになる。これは、たとえばMPEG-2デコーダに適用できる。ここで、デッドライン・ミスで、前にデコードされたフレームを表示することができ、新しくデコードされたフレームは、1フレーム期間後に表示することができる。
2005512465.tif 000022
以下示す新しいオフセットd0を有するが、方程式（1）を用いてマイルストーンで相対的な進度を計算することができる。我々は、このアプローチをスキッピング・デッドライン・ミス・アプローチと称する。
2005512465.tif 000023
【００６７】
スキッピング・デッドライン・ミス・アプローチは、図11に示されるタイムラインの例によって示されている。この例では、P＝1、かつ、d0＝0である。方程式（1）を用いることによって、ρ1＝0.5、ρ2＝0、およびρ3＝−0.5が導出される。マイルストーン3で、相対的な進度はゼロ以下に低下し、それにより、
2005512465.tif 000024
のデッドライン・ミスは、マイルストーン2から、すなわち時間t＝3から発生することになった。つぎに、ρ3が、0.5に適合し、かつ、新しいオフセット
2005512465.tif 000025
が用いられ、その後、ρ4＝1、かつ、ρ5＝0が見い出される。
【００６８】
指定された境界内で、負の相対的な進度を可能にするという方法で、このモデルを一般化することができることに留意する。しかしながら、ここでは、下限がゼロであると仮定される。
【００６９】
一般性を失うことなく、アプリケーションが、マイルストーンmで、状態iであると仮定する。各々の品質レベルqに対して、アプリケーションが、品質レベルqで、タイプtの1つの作業ユニットを処理するために必要な時間を与える、確率変数Xtqを導入する。アプリケーションが、期間Pにつき、計算バジェットbを受けとると仮定する場合には、ρm+1は、以下のようにρmで表現することができる。第1に、相対的な進度の境界0およびpを考慮しないと、新規な相対的な進度は、以下のように、なる。
2005512465.tif 000026
【００７０】
しかしながら、これがゼロ以下に低下する場合には、デッドライン・ミスが発生するので、適合化された相対的な進度が見い出される。さらに、
2005512465.tif 000027
がpを上回る場合には、出力バッファがいっぱいになるので、プロセッサは、失速しているであろう。この場合には、pが適合化された相対的な進度が存在する。保守的なデッドライン・ミス・アプローチが適用される場合、新規な相対的な進度は、方程式（5）と与えられる。
2005512465.tif 000028
ここで、次の関係が用いられる。
2005512465.tif 000029
【００７１】
スキッピング・デッドライン・ミス・アプローチが用いられる場合、新規な相対的な進度は、方程式（6）と与えられる。
2005512465.tif 000030
ここで、次の関係が用いられる。
2005512465.tif 000031
【００７２】
マイルストーンmでの相対的な進度がρmであり、マイルストーンmでの次の作業ユニットのタイプがtmであり、この作業ユニットを処理するために、品質レベルqが選択されるという条件ならば、マイルストーンm＋1でのアプリケーションの相対的な進度ρm＋1が、進度インターバルπ内であり、かつ、マイルストーンm＋1での次の作業ユニットのタイプがtm＋1である確率を与える確率変数は、
2005512465.tif 000032
となる。さらに、タイプtmの作業ユニットに続くタイプtm＋1の作業ユニットでの確率を、Pr（Tm,Tm＋1）と表示する。その後、確率変数は、以下のように導出される。
2005512465.tif 000033
【００７３】
Xtqの累積分布関数は、Ftqと表示する。すなわち、Ftq（x）＝Pr（Xtq≦x）と表示する。
【００７４】
この累積分布関数は、保守的なデッドライン・ミス・アプローチに対して、再帰方程式(3)を用いることによって、0＜x≦pの場合、以下のように導出される。
2005512465.tif 000034
【００７５】
この累積分布関数は、スキッピング・デッドライン・ミス・アプローチに対して、再帰方程式(6)を用いることによって、0＜x＜1の場合、以下のように導出される。
【００７６】
2005512465.tif 000035
そして、1≦x≦pの場合、この累積分布関数は、以下のように導出される。
2005512465.tif 000036
【００７７】
残念なことに、進度インターバルπ（i）内のρmの正確な位置は、未知である。ρmの悲観的な近似値は、インターバルの最も低い数値を選択することによって得られる。これは、以下の近似値を与える。
2005512465.tif 000037
【００７８】
保守的なデッドライン・ミス・アプローチは、上記のように近似値を与えることで、転移確率
2005512465.tif 000038
を、以下のように近似することができる。
2005512465.tif 000039
そして、スキッピング・デッドライン・ミス・アプローチは、以下のように近似することができる。
2005512465.tif 000040
【００７９】
明らかに、進度インターバルを選択すればするほど、方程式（7）の近似値がより良くなるので、転移確率がますます正確にモデル化される。保守的なデッドライン・ミス・アプローチは、スキッピング・デッドライン・ミス・アプローチに対して、最悪のシナリオであることに留意すべきである。そして、スキッピング・デッドライン・ミス・アプローチを適用するときに、保守的なデッドライン・ミス・アプローチの転移確率を、マルコフ決定問題を解くために用いることができる。
【００８０】
マルコフ決定問題を解くことは、
2005512465.tif 000041
の多くの反復された事例を必要とする。最初に、全ての数値
2005512465.tif 000042
を計算して、格納することは、進度インターバル転移の確率に対する
2005512465.tif 000043
の空間複雑度、およびタイプ転移の確率に対する
2005512465.tif 000044
の空間複雑度を必要とする。
2005512465.tif 000045
が小さいと仮定すると、小さな数の進度インターバルがある場合には、これは実行可能なだけである。そうでないと、高速で数値
2005512465.tif 000046
を計算しなければ解けないことになる。しかしながら、これでは、それぞれ、累積分布関数にアクセスすることを含む、多くの冗長な計算をすることになる。累積分布関数Fの数値を計算することは、Fの粒度の対数関数的時間複雑度がある。
【００８１】
保守的なデッドライン・ミス・アプローチが適用される場合、以下の代替方法で、転移確率を計算することはしばしば有利である。一般性を失うことなく、アプリケーションは、マイルストーンmで、状態iであると仮定する。
2005512465.tif 000047
および1の進度インターバルの幅が
2005512465.tif 000048
と与えられると想定する。悲観的な近似値（7）を用いることによって、品質レベルqのタイプt（i）の次の作業ユニットを処理した後に、移動したkの進度インターバルを有する確率を、
2005512465.tif 000049
と表示する。この確率は、以下のように与えられる。
2005512465.tif 000050
【００８２】
つぎに、
2005512465.tif 000051
によって規定される整数をaおよびbとする。その後、さらに、転移確率
2005512465.tif 000052
も、方程式（8）と与えられる。
2005512465.tif 000053
【００８３】
数値
2005512465.tif 000054
は、前もって計算させることができ、
2005512465.tif 000055
に線形である進度インターバル転移の確率に対する
2005512465.tif 000056
の空間複雑度、および、タイプ転移の確率に対する
2005512465.tif 000057
の空間複雑度で格納させることができる。この転移確率を計算する代替手法は、非常に、マルコフ決定問題を解く速度を上げる。
【００８４】
図12は、線図的に、本発明のシステム1200を示す。システム1200は、ソフトウェア・バス1208を介して、中央演算処理装置1210と通信するメモリ1202を備える。メモリ1202は、前述したように、マルチメディアフレームを処理するために用いられるCPUサイクル量を決定するように設計されているコンピュータ可読コード1204を備える。
【００８５】
更に、メモリ1202は、マイルストーンで計算されるマルチメディア処理アプリケーションの相対的な進度に基づいて、マルチメディアフレームの品質を制御するように設計されているコンピュータ可読コード1206を備える。マルチメディアフレームを処理する品質は、前述したように、多くのマルチメディアフレームを処理するためにモデル化される、マルコフ決定問題に基づいて設定されることが好ましい。コンピュータ可読コードは、本発明の方法を遂行するように設計されている、コンピュータプログラム製品を備える記憶デバイス1212から、アップデートすることができる。記憶デバイスは、適切な読出装置（例えば、システム1200に接続されるCD読出し装置1214）によって読み出される。このシステムは、ハードウェアとソフトウェアとの双方、またはソフトウェアを操作することが可能な他のいかなる標準のアーキテクチャーにおいて実現することができる。
【００８６】
図13は、線図的に、本発明のシステムの実施例を備える本発明のテレビ機器1310を示す。ここで、アンテナ1300は、テレビ信号を受信する。アンテナ1300は、テレビ信号を受信する、または再生成することができるいかなるデバイス（たとえば、衛星アンテナ、ケーブル、記憶デバイス、インターネットまたはイーサネット）とも置きかえることができる。レシーバ1302は、テレビ信号を受信する。テレビ機器1310は、レシーバ1302の他に、プログラム可能な素子（たとえばプログラム可能な集積回路）1304を備える。このプログラム可能な素子1304は、本発明のシステム1306を備える。テレビ・スクリーン1308は、レシーバ1302によって受信され、かつ、プログラム可能な素子1304によって処理されるドキュメントを示す。テレビ機器1310は、オプションとして、テレビ信号を提供するDVDプレーヤ1312を備える、または、これに接続することができる。
【００８７】
図14は、線図的に、本発明のシステムの実施例を備えるセットトップボックス1402の最も重要な部分を示す。ここで、アンテナ1400は、テレビ信号を受信する。アンテナ1400も、たとえば、衛星アンテナ、ケーブル、記憶デバイス、インターネット、イーサネット、または、テレビ信号を受信することが可能な他のいかなるデバイスとしてもよい。セットトップボックス1402は、信号を受信する。この信号は、例えばデジタル信号でもよい。ここでは図示しないが、セットトップボックス1402は、セットトップボックス1402に含まれる通常部分の他に、本発明のシステム1404を備える。テレビ信号は、セットトップボックス1402に接続されるテレビ機器1406に表示される。
【００８８】
上述した実施例は、本発明を制限するものではなく明示するのであり、かつ当業者が、添付の請求項の範囲内で別の多くの実施例を設計することが可能であることは、留意すべきである。請求項において、括弧の間に配置されているいかなる引用符号も、請求項を制限するものと解釈すべきではない。「備える」という語は、請求項に示されていない要素またはステップの存在を除外するものではない。ある要素の前の「1つの」という語は、そのような要素が複数存在することを除外するものではない。本発明は、いくつかの別個の要素を有するハードウェアと、適切にプログラムされたコンピュータとによって、実現可能である。いくつかの手段を列挙しているシステムに関する請求項の場合、これらの手段の幾つかを、同一のハードウェア部材によって実施することも可能である。特定の手段が相互に異なる従属請求項において引用されるという事実のみが、これらの手段の組合せを有利に用いることができないことを示すことにはならない。
【図面の簡単な説明】
【００８９】
【図１】タイムラインの例を示す。
【図２】タイムラインの更なる例を示す。
【図３】1つのフレームをデコードするために必要な処理時間の累積分布関数を示す。
【図４】制御戦略の例を示す。
【図５】問題事例に対する転移あたりの平均的な収益を示す。
【図６】品質レベルの利用を示す。
【図７】デッドライン・ミスのパーセンテージを示す。
【図８】品質レベルの平均的な増加量を示す。
【図９】反復（例えばアプローチ）の数を示す。
【図１０】測定される計算時間を示す。
【図１１】スキッピング・デッドライン・ミス・アプローチを示す。
【図１２】線図的に、本発明のシステムを示す。
【図１３】線図的に、本発明のテレビ機器を示す。
【図１４】線図的に、本発明のセットトップボックスを示す。
【符号の説明】
【００９０】
1200  システム
1202  メモリ
1204  コンピュータ可読コード
1206  コンピュータ可読コード
1208  ソフトウェア・バス
1210  中央演算処理装置
1212  記憶デバイス
1214  CD読出し装置
1300  アンテナ
1302  レシーバ
1304  プログラム可能な素子（プログラム可能な集積回路）
1306  システム
1308  テレビ・スクリーン
1310  テレビ機器
1312  DVDプレーヤ
1402  セットトップボックス
1400  アンテナ
1404  システム
1406  テレビ機器
【図１】
2005512465.tif 000058
【図２】
2005512465.tif 000059
【図３】
2005512465.tif 000060
【図４】
2005512465.tif 000061
【図５】
2005512465.tif 000062
【図６】
2005512465.tif 000063
【図７】
2005512465.tif 000064
【図８】
2005512465.tif 000065
【図９】
2005512465.tif 000066
【図１０】
2005512465.tif 000067
【図１１】
2005512465.tif 000068
【図１２】
2005512465.tif 000069
【図１３】
2005512465.tif 000070
【図１４】
2005512465.tif 000071
【国際調査報告】
2005512465.tif 000072
2005512465.tif 000073