(57)【特許請求の範囲】
【請求項１】
画像または音声の符号化データを復号する装置であって、
前記符号化データを供給するソースであって、該符号化データが独立して復号可能な複数の要素データからなり、該複数の要素データの各々が少なくとも一つのブロックからなる、前記ソースと、
前記少なくとも一つのブロックのうち、最初に処理される第１のブロックを特定するブロック情報を生成する第１の処理手段と、
前記最初のブロックに後続するブロックに対応するブロック情報を生成する複数の第２の処理手段であって、該ブロック情報がそのブロックが含まれる前記要素データにおける復号処理の順序と、該ブロックと該ブロックが含まれる要素データとは別の要素データに含まれるブロックとの間の復号処理の順序を決める優先度が計算され、その計算された優先度とを含む、該複数の第２の処理手段と、
前記生成されたブロック情報に対応するブロックを並列して復号する複数の復号手段であって、前記要素データにおける最も早い前記復号処理の順序および最も高い前記計算された優先度の両方を含む前記ブロック情報に対応するブロックが前のブロックの復号処理が終了した該複数の復号手段のうちの一つに割り当てられて復号される、該複数の復号手段と、
前記復号されたブロックを格納するとともに、そのブロックに対応する復号された要素データを形成する記憶手段と、
を備える、前記装置。
【請求項２】
前記優先度は、前記複数の要素データの各々の要素データ毎にその要素データに含まれるブロックに対する復号処理の進捗度に基いて算出され、該進捗度が低いほど優先度が高い、請求項１記載の装置。
【請求項３】
前記優先度は、前記複数の要素データの各々の要素データ毎にその要素データに含まれる未処理のブロックに対する予測された処理時間に基いて算出され、該予測された処理時間が長いほど優先度が高い、請求項１または２記載の装置。
【請求項４】
前記生成されたブロック情報を格納する記憶手段をさらに備え、
前記優先度は、前記ブロック情報を格納した時刻に基いて算出され、該格納した時刻が現在に近いほど該格納されたブロック情報に対応するブロックと同じ要素データに含まれるブロックの優先度が高い、請求項１または２記載の装置。
【請求項５】
画像または音声の符号化データを復号する方法であって、該符号化データが独立して復号可能な複数の要素データからなり、該複数の要素データの各々が少なくとも一つのブロックからなり、前記方法は、
プロセッサが前記少なくとも一つのブロックのうち、最初に処理される第１のブロックを特定するブロック情報を生成するステップと、
プロセッサが前記最初のブロックに後続するブロックに対応するブロック情報を生成するステップであって、該ブロック情報がそのブロックが含まれる前記要素データにおける復号処理の順序と、該ブロックと該ブロックが含まれる要素データとは別の要素データに含まれるブロックとの間の復号処理の順序を決める優先度が計算され、その計算された優先度とを含む、該ステップと、
複数のプロセッサが前記生成されたブロック情報に対応するブロックを並列して復号するステップであって、前記要素データにおける最も早い前記復号処理の順序および最も高い前記計算された優先度の両方を含む前記ブロック情報に対応するブロックが前のブロックの復号処理が終了した該複数のプロセッサのうちの一つに割り当てられて復号される、該ステップと、
プロセッサが前記復号されたブロックを格納するとともに、そのブロックに対応する復号された要素データを形成するステップと、
を含む、前記方法。
【請求項６】
前記優先度は、前記複数の要素データの各々の要素データ毎にその要素データに含まれるブロックに対する復号処理の進捗度に基いて算出され、該進捗度が低いほど優先度が高い、請求項５記載の方法。
【請求項７】
前記優先度は、前記複数の要素データの各々の要素データ毎にその要素データに含まれる未処理のブロックに対する予測された処理時間に基いて算出され、該予測された処理時間が長いほど優先度が高い、請求項５または６記載の方法。
【請求項８】
前記生成されたブロック情報をメモリに格納するステップをさらに含み、
前記優先度は、前記ブロック情報を格納した時刻に基いて算出され、該格納した時刻が現在に近いほど該格納されたブロック情報に対応するブロックと同じ要素データに含まれるブロックの優先度が高い、請求項５または６記載の方法。
【請求項９】
画像または音声の符号化データを復号するプログラムであって、該符号化データが独立して復号可能な複数の要素データからなり、該複数の要素データの各々が少なくとも一つのブロックからなり、
プロセッサが前記少なくとも一つのブロックのうち、最初に処理される第１のブロックを特定するブロック情報を生成するステップと、
プロセッサが前記最初のブロックに後続するブロックに対応するブロック情報を生成するステップであって、該ブロック情報がそのブロックが含まれる前記要素データにおける復号処理の順序と、該ブロックと該ブロックが含まれる要素データとは別の要素データに含まれるブロックとの間の復号処理の順序を決める優先度が計算され、その計算された優先度とを含む、該ステップと、
複数のプロセッサが前記生成されたブロック情報に対応するブロックを並列して復号するステップであって、前記要素データにおける最も早い前記復号処理の順序および最も高い前記計算された優先度の両方を含む前記ブロック情報に対応するブロックが前のブロックの復号処理が終了した該複数のプロセッサのうちの一つに割り当てられて復号される、該ステップと、
プロセッサが前記復号されたブロックを格納するとともに、そのブロックに対応する復号された要素データを形成するステップと、を実行するように構成した、前記プログラム。
【請求項１０】
編集装置であって、
画像または音声の符号化データを供給するソースであって、該符号化データが独立して復号可能な複数の要素データからなり、該複数の要素データの各々が少なくとも一つのブロックからなる、前記ソースと、
前記最初のブロックに後続するブロックに対応するブロック情報を生成する複数の第２の処理手段であって、該ブロック情報がそのブロックが含まれる前記要素データにおける復号処理の順序と、該ブロックと該ブロックが含まれる要素データとは別の要素データに含まれるブロックとの間の復号処理の順序を決める優先度が計算され、その計算された優先度とを含む、該複数の第２の処理手段と、
前記生成されたブロック情報に対応するブロックを並列して復号する複数の復号手段であって、前記要素データにおける最も早い前記復号処理の順序および最も高い前記計算された優先度の両方を含む前記ブロック情報に対応するブロックが前のブロックの復号処理が終了した該複数の復号手段のうちの一つに割り当てられて復号される、該複数の復号手段と、
前記復号されたブロックを格納するとともに、そのブロックに対応する復号された要素データを形成する記憶手段と、
前記復号された要素データを編集する編集手段と、
を備える、前記編集装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化されたデータの復号装置および復号方法に関し、特に複数のプロセッサが並列的に動作する符号化データの復号処理に関する。
【背景技術】
【０００２】
ＣＰＵがプログラムを実行するときの処理の単位として、プロセスとスレッドがある。オペレーティングシステムのマルチタスク機能を利用して、複数のプロセスは並列的に動作することができる。複数のプロセスが並列的に動作して処理を行うことはマルチプロセスと呼ばれる。しかし、個々のプロセス間では基本的にメモリが共有されないため、同一メモリ上のデータへのアクセスが必要な処理を行う場合、マルチプロセスでは処理効率が悪い。
【０００３】
一方、１つのプログラムは、複数のスレッドを生成して各スレッドを並列的に動作させることができる。複数のスレッドが並列的に動作して処理を行うことはマルチスレッドと呼ばれる。個々のスレッド間ではメモリが共有されるので、同一メモリ上のデータへのアクセスが必要な処理を行う場合、マルチスレッドの方が、処理効率が良い。複数のＣＰＵに対して個々のスレッドを割り当てて処理を行うことにより、処理効率はさらに上がる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−２０３２３号公報
【特許文献２】特開２００８−１１８６１６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
以下では、ＣＰＵリソースを利用して処理を実行するＮ個の処理部を効率的に使って、１つの処理を、独立に実行できるＭ個の処理単位に分割して処理することを考える。ただし、Ｎ，Ｍは整数であり、Ｎ≧１、Ｍ≧１とする。これらＭ個の処理単位は、ＭＰＥＧ２のスライスとする。Ｎ個の処理部はＮ個のプロセッサ（ＣＰＵコア）に一対一に対応するものとする。
【０００６】
すべてのスライスを処理し終えるまで、すべての処理部になるべく均等に処理を割り当てることで、処理部を効率的に使用することができる。また、処理部のアイドル時間を減らし、全体の処理時間を短くすることができる。ただし、スライスの処理中に、Ｉ／Ｏ処理（入出力処理）などによって処理部がアイドル状態になることはないと仮定する。
【０００７】
Ｍ≦Ｎのとき、Ｍ個のスライスをＮ個の処理部のうちのＭ個に一対一に対応させ、それぞれのスライスをそれぞれの処理部で処理することが効率的であることは明らかである。
【０００８】
ＭがＮよりも十分に大きい場合で、各スライスの処理時間が事前に分かっている、もしくは各スライスの処理時間をある程度の正確さで予測できるときには、処理時間がなるべく均等になるように、Ｍ個のスライスを処理部の数と同じＮ個のグループに分け、Ｎ個のグループをＮ個の処理部に一対一に対応させればよい。このようにすることで、Ｍ≦Ｎのときと同様にそれぞれのスライスをそれぞれの処理部で処理することができる。
【０００９】
しかしながら、ＭがＮよりも十分に大きい場合で、例えば、ＭがＮの整数倍とならないときや、各スライスの処理時間が事前に分からない、もしくは各スライスの処理時間を正確に予測できないときに、スライスを処理部に効率的に割り当てることは困難である。このような場合、複数のスライスで構成されるデータを処理する場合に、十分な処理速度を得ることができないという問題点がある。
【００１０】
そこで、本発明の目的は、新規かつ有用な復号装置、復号方法、および編集装置を提供することである。本発明の具体的な目的は、符号化されたデータを復号する際の処理速度を向上した復号装置、復号方法、および編集装置を提供することである。
【課題を解決するための手段】
【００１１】
本発明の一観点によれば、画像または音声の符号化データを復号する装置であって、前記符号化データを供給するソースであって、該符号化データが独立して復号可能な複数の要素データからなり、該複数の要素データの各々が少なくとも一つのブロックからなる、前記ソースと、前記少なくとも一つのブロックのうち、最初に処理される第１のブロックを特定するブロック情報を生成する第１の処理手段と、前記第１のブロックの後続のブロックを特定するブロック情報を、その対応する要素データにおける復号処理の順序に基づいて、生成する複数の第２の処理手段と、前記生成されたブロック情報のうち、未参照の１つのブロック情報を参照することにより特定されるブロックを、並列して復号する複数の復号手段と、前記復号されたブロックを格納するとともに、そのブロックに対応する復号された要素データを形成する記憶手段と、を備える、前記装置が提供される。
【００１２】
本発明によれば、複数の復号手段が、要素データを構成するブロックを処理単位として要素データを復号する。復号の際は、未参照の１つのブロック情報を参照することにより特定されるブロックが復号される。また、最初のブロックの後続のブロックを特定するブロック情報が、その対応する要素データにおける復号処理の順序に基づいて、生成される。このため、ブロック情報に従って、予め定められている処理の順番で各ブロックが復号される。このように、要素データを構成するブロックを処理単位とすることで、要素データを処理単位とするよりも、いずれかの復号手段が処理の順番待ちのために処理対象が供給されずに休止することを抑制できる。そのため、復号手段全体の休止時間の合計が減少する。その結果、復号手段全体の利用効率が高まる。よって、符号化されたデータを復号する際の処理速度を向上することが可能となる。
【００１３】
本発明の他の観点によれば、画像または音声の符号化データを復号する方法であって、プロセッサが、前記符号化データに含まれる複数の要素データの各々を構成する少なくとも一つのブロックのうち、最初に処理されるブロックを特定するブロック情報を生成するステップであって、前記要素データが独立して復号可能であり、前記ブロックが、対応する要素データにおいて復号処理の順序が付けられる、前記ステップと、複数のプロセッサが並列に、生成された未参照の１つのブロック情報を参照することにより特定されるブロックを復号するステップと、複数のプロセッサが並列に、前記復号処理の順序に基づいて、復号したブロックが構成する要素データに属する、次のブロックを特定するブロック情報を生成するステップと、すべてのブロックを復号するまで、復号するステップと次のブロックを特定するブロック情報を生成するステップとを繰り返すステップと、を含む、前記方法が提供される。
【００１４】
本発明によれば、複数のプロセッサが、要素データを構成するブロックを処理単位として要素データを復号する。復号の際は、未参照の１つのブロック情報を参照することにより特定されるブロックが復号される。次いで、復号されたブロックが構成する要素データに属する、次のブロックを特定するブロック情報が生成される。このため、ブロック情報に従って、予め定められている処理の順番で、各ブロックが復号される。このように、要素データを構成するブロックを処理単位とすることで、要素データを処理単位とするよりも、いずれかの復号手段が処理の順番待ちのために処理対象が供給されずに休止することを抑制できる。そのため、復号手段全体の休止時間の合計が減少する。その結果、復号手段全体の利用効率が高まる。よって、符号化されたデータを復号する際の処理速度を向上することが可能となる。
【発明の効果】
【００１５】
本発明によれば、符号化されたデータを復号する際の処理速度を向上した復号装置、復号方法、および編集装置を提供できる。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１の実施形態に係る復号装置の構成を示すブロック図である。
【図２】ＭＰＥＧ−２のスライスとマクロブロックを示す図である。
【図３】本発明の第１の実施形態に係る復号装置の機能構成図である。
【図４】各ワーカー処理部にブロックを割り当てる様子を示す図である。
【図５Ａ】本発明の第１の実施形態に係るメイン処理部の復号処理を示すフローチャートである。
【図５Ｂ】本発明の第１の実施形態に係るワーカー処理部の復号処理を示すフローチャートである。
【図６】本発明の第１の実施形態に係るワーカー処理部の他の復号処理を示すフローチャートである。
【図７】スライスとブロックの例を示す図である。
【図８】２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを復号処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。
【図９】キューの状態を示す図である。
【図１０】１スライス当たりのブロックの数Ｋに対するスピードアップ率Ｒを示すグラフである。
【図１１】スライスとブロックの例を示す図である。
【図１２】２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを復号処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。
【図１３】キューの状態を示す図である。
【図１４】２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを復号処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。
【図１５】キューの状態を示す図である。
【図１６】スライスとブロックの例を示す図である。
【図１７】２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを復号処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。
【図１８】キューの状態を示す図である。
【図１９】２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを復号処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。
【図２０】キューの状態を示す図である。
【図２１】スライスとブロックの例を示す図である。
【図２２】２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを復号処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。
【図２３】キューの状態を示す図である。
【図２４】本発明の第２の実施形態に係る編集装置のハードウェア構成を示すブロック図である。
【図２５】本発明の第２の実施形態に係る編集装置の機能構成図である。
【図２６】本発明の第２の実施形態に係る編集装置の編集画面の一例を示す図である。
【図２７】本発明の第２の実施形態に係る編集方法を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、図面に基づいて本発明に係る実施形態を説明する。
【００１８】
｛第１の実施形態｝
本発明の第１の実施形態は、符号化された画像データを復号する復号装置および復号方法についての例である。以下の具体例では、第１の実施形態に係る復号装置および復号方法が、符号化された画像データに対してＭＰＥＧ−２に準拠した復号処理を実行するとして説明する。
【００１９】
図１は、本発明の第１の実施形態に係る復号装置の構成を示すブロック図である。
【００２０】
図１を参照するに、復号装置１０は、復号処理を実行する複数のＣＰＵ２０，２１と、符号化された画像データを記憶するＲＡＭ２２と、ＣＰＵ２０，２１が実行するプログラムを格納したＲＯＭ２３と、ＣＰＵ２０，２１、ＲＡＭ２２、ＲＯＭ２３を接続するバス２４とを有している。
【００２１】
ＣＰＵ２０，２１は、ＲＯＭ２３に記録されているプログラムをＲＡＭ２２に展開し、復号処理を実行する。ＣＰＵ２０，２１はそれぞれ１個ずつプロセッサ（ＣＰＵコア）を有しているが、ＣＰＵ２０，２１の少なくとも一方が２個以上のプロセッサを有するＣＰＵモジュールとして構成されていてもよい。復号装置１０が有するプロセッサの数は２個以上であれば何個でもよい。
【００２２】
ＲＡＭ２２は、符号化された画像データなどを記憶している。
【００２３】
符号化された画像データは、この画像データを構成する要素であるスライスを複数備えている。スライスは複数のブロックで構成されており、ブロック単位で復号される。説明を簡単にするため、スライスとブロックは以下のように定義される。すなわち、スライスはＭＰＥＧ−２のスライスである。また、ブロックはＭＰＥＧ−２のマクロブロックである。
【００２４】
図２は、ＭＰＥＧ−２のスライスとマクロブロックを示す図である。
【００２５】
図２を参照するに、ＭＰＥＧ−２では１枚の画面１０００が１６ライン幅のスライス１１００で構成されている。スライス１１００は１６ライン×１６画素のマクロブロック１２００で構成されている。
【００２６】
第１の実施形態では、スライスを構成するブロックの単位で処理部に復号処理が割り当てられる。ブロックは、スライスよりもデータサイズが小さい。ブロックの単位で処理部に復号処理を割り当てることで、従来よりも処理部に対する復号処理の割り当てがより効率的となる。以下では、説明を簡単にするため、符号化フレームのうち、Ｉ（Ｉｎｔｒａ）フレームのみを使用すると仮定する。なお、以下の説明は、同様にＰ（Ｐｒｅｄｉｃｔｉｖｅ）フレームやＢ（Ｂｉｄｉｒｅｃｔｉｏｎａｌｌｙ  Ｐｒｅｄｉｃｔｉｖｅ）フレームの復号処理にも拡張できる。
【００２７】
図３は、本発明の第１の実施形態に係る復号装置の機能構成図である。
【００２８】
図３を参照するに、復号装置１０は、復号処理部３０として動作する。ＣＰＵ２０は、ＲＡＭ２２上に展開されるプログラムによって、メイン処理部３１、ワーカー処理部３２ａ、スライスデコーダ３３ａとして動作する。ＣＰＵ２１は、ＲＡＭ２２上に展開されるプログラムによって、ワーカー処理部３２ｂ、スライスデコーダ３３ｂとして動作する。
【００２９】
メイン処理部３１は、各スライスのブロックの復号処理を開始するために必要な処理を実行する。図３では、ＣＰＵ２０にメイン処理部３１が割り当てられているが、ＣＰＵ２１にメイン処理部３１が割り当てられていてもよい。ワーカー処理部３２ａ，３２ｂは、スライスデコーダ３３ａ，３３ｂにブロックを割り当て、割り当てたブロックの復号処理を実行させる。
【００３０】
スライスデコーダ３３ａ，３３ｂは、ワーカー処理部３２ａ，３２ｂによって割り当てられたブロックの復号処理を実行する。各ワーカー処理部と各スライスデコーダは一対一の対応関係を有する。すなわち、ワーカー処理部３２ａはスライスデコーダ３３ａと対応関係を有しており、スライスデコーダ３３ａにブロックを割り当て、割り当てたブロックの復号処理を実行させる。また、ワーカー処理部３２ｂはスライスデコーダ３３ｂと対応関係を有しており、スライスデコーダ３３ｂにブロックを割り当て、割り当てたブロックの復号処理を実行させる。この例では、スライスデコーダがソフトウェアで実現されることを想定しているが、ハードウェアで実現されてもよい。
【００３１】
ＲＡＭ２２は、キュー３４、スライスバッファ３５、ビデオメモリ３６、スライスコンテキスト３７、カウンタ３８を有している。
【００３２】
キュー３４にはラッパーブロックが格納される。ラッパーブロックは、処理対象のブロックの情報を含む。スライスバッファ３５には、符号化されたスライスが格納される。ビデオメモリ３６には、復号処理されたスライスが格納される。スライスコンテキスト３７には、スライスの復号処理の状態に関する情報が格納される。スライスの復号処理の状態に関する情報は、具体的にはスライスの符号の開始位置の情報と、そのスライスの出力先のビデオメモリ３６の位置の情報とを含む。カウンタ３８には、復号処理の開始時に初期化され各スライスの復号処理が完了するごとに更新される値が格納される。
【００３３】
スライスデコーダ３３ａ，３３ｂによる復号処理は、より詳細には以下のように行われる。スライスコンテキスト３７は、スライスの符号の開始位置の情報と、そのスライスの出力先のビデオメモリ３６の位置の情報とが与えられて初期化される。スライスデコーダ３３ａ，３３ｂは、与えられたスライスコンテキスト３７に従って、スライスの先頭のブロックから１個ずつ順番にブロックを復号し、復号したブロックをビデオメモリ３６に出力する。スライスデコーダ３３ａ，３３ｂは、スライスのブロックを復号する毎にスライスコンテキスト３７を更新する。
【００３４】
＜スライスを構成するブロック＞
ＭＰＥＧ−２のスライスは、独立に復号処理できるデータであるが、同じスライスに属するブロック（マクロブロック）は、スライス先頭のブロックを除いて、次の３つの依存関係を持つ。
【００３５】
（１）ＤＣ予測：ラスタ順で１個前のブロックから現在のブロックのＤＣ成分が予測される。
【００３６】
（２）量子化スケール：ラスタ順で１個前のブロックの量子化スケールと同じ量子化スケールを使う場合、ブロックの量子化スケールを省略できる。
【００３７】
（３）符号の開始位置：あるブロックの符号の開始位置は、それまでのブロックの符号をすべて復号しなければ明らかにならない。
【００３８】
上記のＤＣ予測、量子化スケール、符号の開始位置はスライスコンテキストとして保存される。
【００３９】
符号化されたストリームの各スライスを復号するには、ＭＰＥＧヘッダ（シーケンスヘッダやピクチャヘッダなど）に含まれる、スライスに共通の情報（クロマサブサンプリング、ＤＣ精度、量子化マトリクスなど）が必要である。説明を簡単にするため、スライスが復号される前にこの情報が解析され、スライスデコーダに暗黙的にこの情報が与えられると仮定する。
【００４０】
各スライスの符号の開始位置は、ストリーム中のスライスヘッダによって合図される。ストリームからこのスライスヘッダを探すことで、各スライスの符号の開始位置が得られる。ただし、スライス中のブロックの符号の開始位置を復号処理される前に予め知ることはできない。
【００４１】
本発明の第１の実施形態では、スライスＳはＫ個のブロックに分割する。１つのスライスＳを分割したＫ個のブロックをＳ０／Ｋ，Ｓ１／Ｋ，・・・Ｓ（Ｋ−１）／Ｋとする。なお、ブロックの個数Ｋは１以上であれば、いずれの整数を選択してもよいが、以下の点を考慮することが好ましい。
【００４２】
スライスをブロックに分割する方法は任意であるが、分割幅は適当に決める必要がある。分割幅はブロックの処理時間と関係するため、分割幅が大きすぎると、各ワーカー処理部に処理を均等に割り当てることが難しくなる。逆に、分割幅が小さすぎると、キューへのアクセス、スライスの処理状態（スライスコンテキスト）の保存・復元、スライスの処理におけるキャッシュミスなどによるオーバーヘッドが増加する。
【００４３】
＜ブロックの依存関係（ラッパーブロック）＞
１つのスライスＳを構成するＫ個のブロックＳ０／Ｋ，Ｓ１／Ｋ，・・・Ｓ（Ｋ−１）／Ｋには依存関係（逐次性）がある。依存関係とは、２つのブロックに関して、一方のブロックの処理を開始する前に他方のブロックの処理が完了しているということである。この依存関係は、Ｓ０／Ｋ→Ｓ１／Ｋ→・・・Ｓ（Ｋ−１）／Ｋと表される。Ｓｋ／Ｋ→Ｓ（ｋ＋１）／Ｋ（ｋ＝０，・・・，Ｋ−１）は、ブロックＳ（ｋ＋１）／Ｋの処理を開始する前にブロックＳｋ／Ｋの処理が完了していることを表す。
【００４４】
ラッパーブロックは、各スライスＳのブロックの処理の依存関係の情報を有し、特に、処理対象のブロックを特定する情報を含んでいる。各スライスＳのラッパーブロックＷｋ／Ｋがキュー３４から取り出されると、以下の処理が実行される。
【００４５】
０≦ｋ＜Ｋ−１の場合：ブロックＳｋ／Ｋが処理される。その後、次に処理されるブロックＳ（ｋ＋１）／Ｋに関するラッパーブロックＷ（ｋ＋１）／Ｋがキューに追加される。
【００４６】
ｋ＝Ｋ−１の場合：ブロックＳｋ／Ｋが処理され、スライスＳの復号処理が完了する。
【００４７】
復号処理の初期状態において、各スライスの最初のラッパーブロックＷ０／Ｋが生成され、キュー３４に格納される。ワーカー処理部３２ａ，３２ｂは、スライスＳのラッパーブロックＷｋ／Ｋをキュー３４から取り出して、ラッパーブロックＷｋ／Ｋが指定するスライスＳのブロックＳｋ／Ｋの処理を行った後、スライスＳの次のブロックＳ（ｋ＋１）／Ｋの処理に関するラッパーブロックＷ（ｋ＋１）／Ｋをキューに追加する。このようにすることで、スライスＳのブロックＳ（ｋ＋１）／Ｋの処理を開始する前にスライスＳのブロックＳｋ／Ｋの処理が完了しているという依存関係が保証される。
【００４８】
＜キューの制御＞
図４は、各ワーカー処理部にラッパーブロックを割り当てる様子を示す図である。図４を参照するに、キュー３４には処理待ちのラッパーブロックが置かれ、ワーカー処理部３２ａ，３２ｂはキュー３４からラッパーブロックを取り出し、取り出したラッパーブロックを処理する。
【００４９】
図４に示す例では、キュー３４は３つのラッパーブロックを格納することができる。キュー３４にラッパーブロックが追加されるときには、ラッパーブロックからなる列の最後尾にラッパーブロックが追加される。また、キュー３４からラッパーブロックが取り出されるときには、ラッパーブロックからなる列の先頭のラッパーブロックが取り出される。ただし、ラッパーブロックに優先度を関連付けておき、キュー３４に格納されたラッパーブロックを、そのラッパーブロックに関連付けられた優先度の高い順に取り出してもよい。図４では、キュー３４に３つのラッパーブロックＡ，Ｂ，Ｃが格納された状態において、ラッパーブロック列の先頭のブロックＡが取り出され、取り出されたラッパーブロックＡがワーカー処理部３２ａによって処理される様子が示されている。
【００５０】
キュー３４からラッパーブロックを取り出す、あるいはキュー３４にラッパーブロックを追加するため、複数のワーカー処理部が同時にキュー３４にアクセスすると、そのアクセスは排他制御される。すなわち、同時に１つのワーカー処理部からのアクセスのみが許可され、他のワーカー処理部がアクセスできない。この制御によって、２つ以上のワーカー処理部が同一のラッパーブロックをキュー３４から取り出して処理することはなくなり、キュー３４の状態の整合性が保たれる。
【００５１】
＜ブロックを処理する優先度＞
スライスを分割したブロックに対して、優先度という指標を与え、複数のスライスについてそれぞれブロックがキュー３４にある場合に、優先度の高いブロックを優先的に処理することで、ワーカー処理部３２ａ，３２ｂに対する処理の割り当てが、より効率的になりやすくなる。本発明の第１の実施形態では、３つの優先度Ｐ０，Ｐ１，Ｐ２が定義される。それぞれの優先度はブロック毎に与えられる。
【００５２】
優先度Ｐ０は、スライスにおけるブロックの処理の進捗割合に基づく指標である。ブロックＳｋ／Ｋの優先度Ｐ０（Ｓｋ／Ｋ）は、ブロックＳｋ／Ｋを含む以降のブロックの処理時間とスライスＳ全体の処理時間の比として（１）式のように定義される。
【数１】
0005698156.tif 000002
【００５３】
（１）式において、Ｔ（Ｓｊ／Ｋ）はブロックＳｊ／Ｋの処理時間であり、Ｔ（Ｓ）はスライスＳ全体の処理時間である。実際には、Ｔ（Ｓｊ／Ｋ）とＴ（Ｓ）が未知であっても、それらの比がある程度の正確さで予測できれば、優先度Ｐ０を求めることができる。（１）式は（２）式と等価である。
【数２】
0005698156.tif 000003
【００５４】
（２）式は、進捗割合の低いスライスのブロックが優先的に処理されることを示している。各ブロックの処理時間が同一であると仮定すると、Ｋ個のブロックのうちブロックＳ０／ＫからブロックＳｋ−１／Ｋまでのｋ個のブロックの処理が終了したときの進捗割合はｋ／Ｋと表される。したがって、（２）式から優先度Ｐ０は（３）式となる。
【数３】
0005698156.tif 000004
【００５５】
優先度Ｐ１は、スライスにおける未処理のブロックの処理時間に基づく指標である。ブロックＳｋ／Ｋの優先度Ｐ１（Ｓｋ／Ｋ）は、ブロックＳｋ／Ｋを含む以降のブロックの処理時間として（４）式のように定義される。
【数４】
0005698156.tif 000005
【００５６】
（４）式において、Ｔ（Ｓｊ／Ｋ）はブロックＳｊ／Ｋの処理時間である。
【００５７】
Ｔ（Ｓｊ／Ｋ）が未知の場合には、例えば、処理が終了しているブロックの処理時間からＴ（Ｓｊ／Ｋ）を予測すればよい。（４）式は、残りの処理時間（残りの処理時間の予測値）が長いスライスのブロックが優先的に処理されることを示している。
【００５８】
優先度Ｐ２は、ブロックに対応するラッパーブロックがキュー３４に追加されたタイミングに基づく指標である。ブロックＳｋ／Ｋの優先度Ｐ２（Ｓｋ／Ｋ）は、ブロックＳｋ／Ｋに対応するラッパーブロックがキュー３４に追加された時刻ｔｋ／Ｋとして（５）式のように定義される。
【数５】
0005698156.tif 000006
【００５９】
（５）式に従って、最後に処理されたブロックが属するスライスと同じスライスのブロックの処理を優先的に行うことで、キャッシュの利用効率が高まり、処理速度が向上する。
【００６０】
ブロックの分割幅（ブロックの処理時間）がある程度大きく、スライス全体で同一の優先度Ｐ０を持つブロックが多数存在するとき、例えば、優先度Ｐ１，Ｐ２を導入すると、ワーカー処理部３２ａ，３２ｂに対して、より均等にブロックの処理を割り当てることができる。
【００６１】
図５Ａは、本発明の第１の実施形態に係るメイン処理部３１の復号処理を示すフローチャートである。
【００６２】
図５Ａを参照するに、メイン処理部３１は処理Ｓ１０を実行する。処理Ｓ１０は次に説明するステップＳ１００、Ｓ１０１、Ｓ１０５、Ｓ１１０、Ｓ１１６、Ｓ１１５、Ｓ１２０、およびＳ１２５を含んでいる。
【００６３】
最初に、ステップＳ１００では、１つのシーンまたはクリップの復号処理が終了したか否かの判定結果に応じて、処理が分岐する。
【００６４】
１つのシーンまたはクリップの復号処理が終了していない場合、ステップＳ１０１では、メイン処理部３１は、１つのシーンまたはクリップを構成する１つのフレームにおいて処理対象とするスライスを選択する。
【００６５】
次いで、ステップＳ１０５では、メイン処理部３１は、処理対象とするスライスの数と同じ値をカウンタ３８に格納する。
【００６６】
次いで、ステップＳ１１０では、メイン処理部３１は、各スライスの最初のラッパーブロックを生成する。このとき、スライスの数と同数のラッパーブロックが生成される。
【００６７】
生成されたラッパーブロックには、スライスコンテキストが含まれている。このスライスコンテキストには、復号処理すべきスライスの符号が格納されているスライスバッファ３５の位置の情報と、そのスライスの出力先のビデオメモリ３６の位置の情報と、そのラッパーブロックが属するスライスの復号処理の進捗割合と、優先度とが含まれている。
【００６８】
スライスバッファ３５の位置は、復号処理すべきスライスのブロックの開始位置を示す。ビデオメモリ３６の位置は、復号処理後のブロックを格納する位置を示す。
【００６９】
進捗割合は、例えば（復号処理されたブロックの数）／（スライスに含まれる全てのブロックの数）として計算される。または、進捗割合を、（復号処理されたブロックの符号長の累積値）／（スライスに含まれる全てのブロックの符号長の合計値）として計算することもできる。
【００７０】
進捗割合の計算に使用される、スライスに含まれる全てのブロックの数や、スライスに含まれる全てのブロックの符号長の合計値は、スライス全体の復号処理が開始される前にスライスコンテキスト３７に保存されている。ブロックが復号処理される毎に、復号処理されたブロックの数や、復号処理されたブロックの符号長の累積値が更新され、スライスコンテキスト３７に保存される。
【００７１】
優先度は、１から進捗割合を引いた値として定義される。この優先度は、優先度Ｐ０に相当する。この例では、優先度Ｐ０のみを使用するが、優先度Ｐ０に加えて優先度Ｐ１や優先度Ｐ２を使用してもよい。
【００７２】
ステップＳ１１０では、各スライスの進捗割合が０なので、各スライスの最初のラッパーブロックに関連付けられる優先度は１である。各スライスの最初のラッパーブロックがキュー３４から取り出されるとき、各ラッパーブロックは、キュー３４に入れられた順番で取り出される。
【００７３】
次いで、ステップＳ１１５では、メイン処理部３１は、生成したラッパーブロックをキュー３４に入れる。
【００７４】
次いで、ステップＳ１１６では、メイン処理部３１は、ワーカー処理部３２ａ，３２ｂから、ステップＳ１０１で選択したスライスの復号処理の終了が通知されるまで待機する。
【００７５】
ワーカー処理部３２ａ，３２ｂから、ステップＳ１０１で選択したスライスの復号処理の終了が通知されるとステップＳ１２０に進む。ステップＳ１２０では、１つのフレームの全てのスライスの復号処理が終了したか否かの判定結果に応じて、処理が分岐する。続けて他のスライスの復号処理を行う場合、ステップＳ１０１からの処理が再度実行される。１つのフレームの全てのスライスの復号処理が終了した場合、ステップＳ１００からの処理が再度実行される。
【００７６】
ステップＳ１００において１つのシーンまたはクリップの復号処理が終了した場合、ステップＳ１２５では、メイン処理部３１は、ワーカー処理部３２ａ，３２ｂの数と同じ数の終了用のラッパーブロックを生成してキュー３４に入れる。終了用のラッパーブロックには例えば終了を明示する情報が含まれているため、終了用のラッパーブロックとステップＳ１１０で生成されたラッパーブロックとを区別することが可能である。終了用のラッパーブロックをキュー３４に入れた後、メイン処理部３１は処理Ｓ１０を終了する。
【００７７】
図５Ｂは、本発明の第１の実施形態に係るワーカー処理部３２ａ，３２ｂの復号処理を示すフローチャートである。
【００７８】
図５Ｂを参照するに、ワーカー処理部３２ａ，３２ｂはそれぞれ処理Ｓ２０ａ、Ｓ２０ｂを実行し、ワーカー処理部３２ａ，３２ｂはこれらの処理Ｓ２０ａ、Ｓ２０ｂを並列して実行する。処理Ｓ２０ａは次に説明するステップＳ２００、Ｓ２０５、Ｓ２０６、Ｓ２１０、Ｓ２１５、Ｓ２２０、Ｓ２２５、Ｓ２３０、Ｓ２３５、Ｓ２４０、Ｓ２４５、およびＳ２５０を含んでいる。処理Ｓ２０ｂは処理Ｓ２０ａと同様であるので、フローの詳細の図示を省略している。
【００７９】
最初に、図示を省略しているが、ワーカー処理部３２ａ，３２ｂは、キュー３４にラッパーブロックがない場合、キュー３４にラッパーブロックが追加されるまで待機する。
【００８０】
キュー３４にラッパーブロックがある場合、ステップＳ２００では、ワーカー処理部３２ａ，３２ｂはキュー３４から先頭のラッパーブロックを取り出す。
【００８１】
次いで、ワーカー処理部３２ａ，３２ｂは、ステップＳ２００でキュー３４から取り出したラッパーブロックが終了用のラッパーブロックであるか否かを確認する。ステップＳ２００でキュー３４から取り出したラッパーブロックが終了用のラッパーブロックである場合、ステップＳ２０６では、ワーカー処理部３２ａ，３２ｂは、自身が使用しているＲＡＭ２２の領域を解放するなどの終了処理を行い、処理Ｓ２０ａ，Ｓ２０ｂを終了する。
【００８２】
ステップＳ２００でキュー３４から取り出したラッパーブロックが終了用のラッパーブロックでない場合、ステップＳ２１０では、ワーカー処理部３２ａ，３２ｂは、キュー３４から取り出したラッパーブロックが示す処理対象のブロックの復号処理をスライスデコーダ３３ａ，３３ｂに行わせる。
【００８３】
具体的には、ステップＳ２１０では以下の処理が行われる。ラッパーブロックには、スライスコンテキストが含まれている。前述したように、このスライスコンテキストには、復号処理すべきスライスの符号が格納されているスライスバッファ３５の位置の情報と、そのスライスの出力先のビデオメモリ３６の位置の情報とが含まれている。ワーカー処理部３２ａ，３２ｂはこれらの情報をスライスデコーダ３３ａ，３３ｂに与える。
【００８４】
スライスデコーダ３３ａ，３３ｂは、符号化されたスライスのデータをビット単位またはバイト単位でスライスバッファ３５から読み出し、読み出したデータを復号処理する。ブロックの復号処理が終了すると、スライスデコーダ３３ａ，３３ｂは、復号処理したブロックのデータをビデオメモリ３６に保存し、スライスコンテキスト３７を更新する。
【００８５】
ワーカー処理部３２ａ，３２ｂがスライスデコーダ３３ａ，３３ｂに与える、スライスの出力先のビデオメモリ３６の位置の情報は、フレーム中のスライスの位置とそのスライス中のブロックの位置とに対応したビデオメモリ３６中の位置を示している。スライスデコーダ３３ａ，３３ｂは、復号処理したブロックのデータを、上記の情報が示す位置に保存する。１フレームを構成する全てのスライスに含まれる全てのブロックの復号処理が終了したとき、ビデオメモリ３６に保存されている各ブロックは、符号化された各スライスに対応した、復号処理されたスライスを構成している。
【００８６】
次いで、ステップＳ２１５では、ワーカー処理部３２ａ，３２ｂは、スライスコンテキスト３７に基づいて、復号処理されたブロックが属するスライスの進捗割合と優先度を計算する。前述したように、進捗割合は、例えば（復号処理されたブロックの数）／（スライスに含まれる全てのブロックの数）、または（復号処理されたブロックの符号長の累積値）／（スライスに含まれる全てのブロックの符号長の合計値）として計算される。優先度は、１から進捗割合を引いた値として計算される。
【００８７】
次いで、ステップＳ２２０では、スライスの最後のラッパーブロックが処理されたか否かの判定結果に応じて、処理が分岐する。進捗割合の値を使用すれば、スライスの最後のラッパーブロックが処理されたか否かの判定を行うことができる。すなわち、進捗割合が１より小さければ、スライスの最後のラッパーブロックはまだ処理されていない。また、進捗割合が１であれば、スライスの最後のラッパーブロックが処理されたことになる。
【００８８】
スライスの最後のラッパーブロックが処理されたとき、ステップＳ２２５では、ワーカー処理部３２ａ，３２ｂは、カウンタ３８の値を１つデクリメントする。複数のワーカー処理部が同時にカウンタ３８にアクセスすると、そのアクセスは排他制御される。
【００８９】
次いで、ステップＳ２３０では、ワーカー処理部３２ａ，３２ｂは、カウンタ３８の値を確認する。ステップＳ１０５でスライスの数と同じ値に設定されたカウンタ３８の値は、各スライスの最後のブロックが復号処理されるごとに、ステップＳ２２５で１ずつデクリメントされる。このため、カウンタの値が０でなければ、復号処理が終了していないスライスが存在しているので、ステップＳ２００からの処理が再度実行される。また、カウンタの値が０になったとき、全てのスライスのラッパーブロックの処理が終わっているので、ステップＳ２５０では、ワーカー処理部３２ａ，３２ｂは、図５ＡのステップＳ１０１で選択されたスライスの復号処理の終了をメイン処理部３１に通知する。次いで、ステップＳ２００からの処理が再度実行される。
【００９０】
ステップＳ２２０でスライスの最後のラッパーブロックがまだ処理されていないとき、ステップＳ２３５では、ワーカー処理部３２ａ，３２ｂは、ステップＳ２１０で復号処理したブロックが属するスライスと同じスライスに属するブロックであって、ステップＳ２１０で復号処理したブロックの次のブロックを特定する情報を含むラッパーブロックを生成する。
【００９１】
生成されたラッパーブロックには、スライスコンテキストが含まれている。このスライスコンテキストには、復号処理後に更新されたスライスコンテキスト３７から得られる、復号処理すべきスライスの符号が格納されているスライスバッファ３５の位置の情報と、そのスライスの出力先のビデオメモリ３６の位置の情報と、ステップＳ２１５で算出された、そのラッパーブロックが属するスライスの復号処理の進捗割合と、優先度とが含まれる。
【００９２】
次いで、ステップＳ２４０では、ワーカー処理部３２ａ，３２ｂは、生成したラッパーブロックをキュー３４に入れる。
【００９３】
次いで、ステップＳ２４５では、ワーカー処理部３２ａ，３２ｂは、ステップＳ２４０でキュー３４に追加されたラッパーブロックを含むキュー３４内のラッパーブロックを、各ラッパーブロックに関連付けられた優先度の降順に整列する。次いで、ステップＳ２００からの処理が再度実行される。
【００９４】
スライスを含む１枚のフレーム全体の符号化された画像データは以下のように復号処理される。例えば、１枚のフレームがＵ個のスライスで構成され、フレームの上から順に１，２，・・・，Ｕの番号が各スライスに付与されていると仮定する。Ｖ個（Ｖ≦Ｕ）以下のスライスを単位として、復号処理が実行される。例えば、１番目からＶ番目までのＶ個のスライスが処理対象として選択され（図５ＡのステップＳ１０１に対応）、図５Ａに示すフローチャートに従って処理される。Ｖ個のスライスの復号処理が終了すると、Ｖ＋１番目から２Ｖ番目までのＶ個のスライスが処理対象として選択され（図５ＡのステップＳ１０１に対応）、図５Ａに示すフローチャートに従って処理される。残りのスライスがＶ個以下となったとき、残りの全てのスライスが処理対象として選択され（図５ＡのステップＳ１０１に対応）、図５Ａに示すフローチャートに従って復号処理される。以上によって、１枚のフレーム全体の符号化された画像データが復号処理される。
【００９５】
符号化された動画データを復号処理する場合、１枚のフレーム全体の符号化された画像データの復号処理が終了したら、次のフレームに係る、フレーム全体の符号化された画像データの復号処理が開始される。上記の処理は実施可能な処理の一例であり、上記に限定されない。例えば、各々のスライスの復号処理は独立に実行できるので、必ずしもフレーム内で連続して配置されたスライスを単位として復号処理を実行しなくてもよい。
【００９６】
図６は、本発明の第１の実施形態に係るワーカー処理部３２ａ，３２ｂの他の復号処理を示すフローチャートである。
【００９７】
図６を参照するに、第１の実施形態に係る他の復号方法では、優先度は使用されない。この点が先の図５Ｂに示すフローチャートと異なっている。このため、ラッパーブロックがキュー３４から取り出されるとき、各ラッパーブロックは、キュー３４に入れられた順番で取り出される。図６では、図５Ｂに示す処理と同じ処理には同じステップ番号が付してあり、以下ではその説明を省略し、図５Ｂに示すフローチャートと異なる箇所のみを説明する。
【００９８】
図６に示すフローチャートでは、ステップＳ２１５でスライスの進捗割合と優先度が計算されるが、優先度が使用されないため、ステップＳ２５５では進捗割合のみが計算される。また、図６に示すフローチャートでは、図５ＢのステップＳ２４５の処理は実行されない。
【００９９】
＜復号処理の例＞
ワーカー処理部の振る舞い（同時に複数のワーカー処理部がキューにアクセスした場合の調停やブロックの処理時間など）は、割り込みの発生などの要因によって非決定論的であり、実装によって異なる可能性がある。第１の実施形態では、キューを使用した典型的な復号処理の例を示す。また、説明を簡単にするため、キューへのアクセスに必要な時間を無視できるものと考える。
【０１００】
以下では、Ｍ＝３、Ｎ＝２の場合のスライスの復号処理の一例を示す。以下の例で示されるスライスの処理方法は必ずしも最適であるとは限らない。説明を簡単にするため、以下ではラッパーブロックと、スライスを分割したブロックとを区別せず、単にブロックと記載する。
【０１０１】
図７は、スライスとブロックの例を示す図である。図７を参照するに、３つのスライスＡ，Ｂ，Ｃは、同一の処理時間を必要とする、分割幅の等しい２つのブロックに分割できる。例えば、スライスＡはブロックＡ０／２とブロックＡ１／２とに分割できる。各ブロックの右上に付与された符号は各ブロックの処理の順番を表している。例えば、ブロックＡ０／２については、「０／２」が処理の順番を表している。「０／２」の「２」はブロックの総数を表している。ブロックＡ０／２はブロックＡ１／２よりも先に処理される。
【０１０２】
スライスＢはブロックＢ０／２とブロックＢ１／２とに分割できる。ブロックＢ０／２はブロックＢ１／２よりも先に処理される。スライスＣはブロックＣ０／２とブロックＣ１／２とに分割できる。ブロックＣ０／２はブロックＣ１／２よりも先に処理される。
【０１０３】
図８は、２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。図９は、キューの状態を示す図である。
【０１０４】
時刻ｔ＝ｔ０に全てのスライスの最初のブロックＡ０／２，Ｂ０／２，Ｃ０／２がキューに追加される（図５ＡのステップＳ１１５に対応）。
【０１０５】
時刻ｔ＝ｔ０＋Δｔ（時刻ｔ＝ｔ０の直後）にキューから先頭のブロックＡ０／２とその次のブロックＢ０／２が取り出され、ブロックＡ０／２の処理がワーカー処理部＃０に割り当てられ、ブロックＢ０／２の処理がワーカー処理部＃１に割り当てられる（図６のステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に処理を開始する（図６のステップＳ２１０に対応）。
【０１０６】
時刻ｔ＝ｔ１にブロックＡ０／２とブロックＢ０／２の処理が終了すると、ブロックＡ０／２の次に処理すべきブロックＡ１／２と、ブロックＢ０／２の次に処理すべきブロックＢ１／２とがキューに追加される（図６のステップＳ２４０に対応）。時刻ｔ＝ｔ０では最後尾のブロックであったブロックＣ０／２が時刻ｔ＝ｔ１では先頭のブロックとなり、ブロックＣ０／２の後にブロックＡ１／２とブロックＢ１／２が追加されている。
【０１０７】
時刻ｔ＝ｔ１＋Δｔにキューから先頭のブロックＣ０／２とその次のブロックＡ１／２が取り出され、ブロックＣ０／２の処理がワーカー処理部＃０に割り当てられ、ブロックＡ１／２の処理がワーカー処理部＃１に割り当てられる（図６のステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に各ブロックの処理を行う（図６のステップＳ２１０に対応）。
【０１０８】
時刻ｔ＝ｔ２にブロックＣ０／２とブロックＡ１／２の処理が終了すると、ブロックＣ０／２の次に処理すべきブロックＣ１／２がキューに追加される（図６のステップＳ２４０に対応）。ブロックＡ１／２の処理が終了したため、スライスＡの処理は終了する。時刻ｔ＝ｔ１では最後尾のブロックであったブロックＢ１／２が時刻ｔ＝ｔ２では先頭のブロックとなり、ブロックＢ１／２の後にブロックＣ１／２が追加されている。
【０１０９】
時刻ｔ＝ｔ２＋Δｔにキューから先頭のブロックＢ１／２とその次のブロックＣ１／２が取り出され、ブロックＢ１／２の処理がワーカー処理部＃０に割り当てられ、ブロックＣ１／２の処理がワーカー処理部＃１に割り当てられる（図６のステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に各ブロックの処理を行う（図６のステップＳ２１０に対応）。
【０１１０】
ブロックＢ１／２とブロックＣ１／２の処理が終了すると、スライスＢとスライスＣの処理は終了する。この時点よりも前にスライスＡの処理は終了しているため、ブロックＢ１／２とブロックＣ１／２の処理が終了した時点で、全てのスライスの処理は終了している。
【０１１１】
この例では、全てのスライスが同一の処理時間のブロックに均等に分割されており、ブロックの総数がワーカー処理部の数の倍数になっている。このため、図８に示すように、２つのワーカー処理部に対して均等にブロックの処理を割り当てることができる。
【０１１２】
＜復号処理性能＞
第１の実施形態の復号方法による処理性能について一実施例を挙げて、以下に説明する。以下の説明では、ワーカー処理部の処理がスレッドにより実行されるとする。また、ワーカー処理部の数Ｎとスライスの数Ｍの関係はＭ≧Ｎであるとし、全てのスライスの実行時間（実行時間の予測値）は等しく、その時間はＴであるとする。実施例では、全てのスライスは均一にＫ個のブロックに分けられ、それぞれのブロックはＴ／Ｋの実行時間を必要とする。説明を簡単にするため、ワーカー処理部による処理の切り替えに要する時間や、キューへのアクセス時間などのオーバーヘッドは無視できるものと考える。
【０１１３】
ワーカー処理部に割り当てられるタイムクォンタムは、典型的には、数１０ミリ秒から数１００ミリ秒程度である。ビデオフレームは、典型的には、毎秒３０枚のフレームからなり、実時間で画像を再生するには、１フレームを少なくとも１／３０秒すなわち約３３ミリ秒で復号処理する必要がある。実際のアプリケーション、例えばビデオ編集システムでは、複数のビデオクリップを同時に再生したり、ビデオエフェクトやトランジションを適用したりするため、３３ミリ秒よりも短い復号処理時間が求められる。
【０１１４】
参考例として、タイムクォンタムが１スライスの処理時間Ｔと同じ、またはそれよりも大きい場合に、Ｍ個のスライスの処理をＭ個のワーカー処理部によって実行することを考える。タイムクォンタムはタイムスライスとも呼ばれ、ＯＳがワーカー処理部による処理の実行を切り替える間隔を意味する。まず、プロセッサの数Ｎと同数のスライスの処理が、それぞれに対応するワーカー処理部によって開始される。
【０１１５】
Ｎ個のスライスは並列に処理され、タイムクォンタムを使い切るまでに処理が完了する。Ｎ個のスライスの処理が完了すると、残りのスライスの数がＮ個より少なくなるまで、同様にＮ個のスライスが並列に処理される。
【０１１６】
以下の議論では、以下の記号（Ｐ１）と記号（Ｐ２）を使用する。記号（Ｐ１）はＸを上回らない最大の整数を示しており、記号（Ｐ２）はＸを下回らない最小の整数を示している。
【数６】
0005698156.tif 000007
【数７】
0005698156.tif 000008
【０１１７】
ＭがＮで割り切れる場合、Ｍ／Ｎ回の並列処理を行えば、全てのスライスの処理が完了する。ＭがＮで割り切れない場合、Ｄ（（６）式）回の並列処理が行われた後、最後にＥ（（７）式）個のスライスが並列に処理される。この最後の並列処理では、スライスが割り当てられないＦ（（８）式）個のワーカー処理部は停止している。
【数８】
0005698156.tif 000009
【数９】
0005698156.tif 000010
【数１０】
0005698156.tif 000011
【０１１８】
参考例では、合計の処理時間Ｔ１は（９）式となる。
【数１１】
0005698156.tif 000012
【０１１９】
本発明では、ＭＫ個のブロックの処理を、Ｎ個のワーカー処理部により、ブロック間の依存関係を保ったまま並列に実行することができる。１スライスの処理時間がＴであり、１スライスはＫ個のブロックからなるので、各ブロックの処理時間はＴ／Ｋである。各ワーカー処理部は１個のＣＰＵに対応するので、スライスの処理中にはワーカー処理部の切り替えが発生しない。参考例の性能の議論で用いた（９）式において、ＭをＭＫに置き換え、ＴをＴ／Ｋに置き換えると、本発明の合計の処理時間Ｔ２を（１０）式のように求めることができる。
【数１２】
0005698156.tif 000013
【０１２０】
参考例の処理性能と本発明の処理性能を比較する指標であるスピードアップ率Ｒは（１１）式で定義される。
【数１３】
0005698156.tif 000014
【０１２１】
参考例の処理時間Ｔ１が本発明の処理時間Ｔ２と同じとき、Ｒ＝１となる。このため、参考例の処理性能と本発明の処理性能は同等となる。また、参考例の処理時間Ｔ１が本発明の処理時間Ｔ２よりも長くなると、Ｒ＞１となる。そうすると、本発明の処理性能が参考例の処理性能を上回る。
【０１２２】
以下に、いくつかのＮ，Ｍの組み合わせに対して、Ｋとスピードアップ率Ｒの関係を示す。図１０は、１スライス当たりのブロックの数Ｋに対するスピードアップ率Ｒを示すグラフである。
【０１２３】
Ｋ＝１のとき、スピードアップ率は１となり、参考例と本発明の処理性能は同等である。合計のブロック数ＭＫがＮの倍数となるとき、スピードアップ率Ｒは最大値Ｒｍａｘ（（１２）式）となる。
【数１４】
0005698156.tif 000015
【０１２４】
Ｎ＝２，Ｍ＝３の場合とＮ＝４とＭ＝１０の場合には、Ｋが２以上になる。そうすると、スピードアップ率が１を超え、本発明の処理性能が参考例の処理性能を上回る。Ｎ＝３，Ｍ＝８の場合には、Ｋが３以上になると、スピードアップ率が１を超える。そうすると、本発明の処理性能が参考例の処理性能を上回る。また、Ｋが大きくなればなるほど、すなわち、スライスの分割が細かくなればなるほど、スピードアップ率ＲがＲｍａｘに近づいていく。
【０１２５】
このように、本発明では、各スライスを所定数以上のブロックに分割できる場合には、ワーカー処理部に対する処理の割り当てが効率的になり、参考例よりも処理速度が向上する。
【０１２６】
＜優先度Ｐ０を使用したスライスの復号処理の例＞
第１の実施形態に係る復号処理方法として、優先度Ｐ０を使用しない場合の復号処理の例と、優先度Ｐ０を使用する場合の復号処理の例を示す。説明を簡単にするため、キューへのアクセスに必要な時間やブロックの並べ替えに必要な時間を無視できるものと考える。
【０１２７】
図１１は、スライスとブロックの例を示す図である。図１１を参照するに、３つのスライスＡ，Ｂ，Ｃがある。スライスＡ，Ｂは３個のブロックからなり、スライスＣは４個のブロックからなる。スライスＡ，Ｂ，Ｃのブロックの分割幅（ブロックの処理時間）は同一である。このため、スライスＣの処理時間はスライスＡ，Ｂの処理時間よりも長い。
【０１２８】
スライスＡはブロックＡ０／３とブロックＡ１／３とブロックＡ２／３とに分割される。スライスＡの各ブロックは、ブロックＡ０／３、ブロックＡ１／３、ブロックＡ２／３の順に処理される。スライスＢはブロックＢ０／３とブロックＢ１／３とブロックＢ２／３とに分割される。スライスＢの各ブロックは、ブロックＢ０／３、ブロックＢ１／３、ブロックＢ２／３の順に処理される。スライスＣはブロックＣ０／４とブロックＣ１／４とブロックＣ２／４とブロックＣ３／４とに分割される。スライスＣの各ブロックは、ブロックＣ０／４、ブロックＣ１／４、ブロックＣ２／４、ブロックＣ３／４の順に処理される。
【０１２９】
図１２は、２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。図１３は、キューの状態を示す図である。図１２と図１３に示す例では、優先度Ｐ０は使用しない。
【０１３０】
時刻ｔ＝ｔ０に全てのスライスの最初のブロックＡ０／３，Ｂ０／３，Ｃ０／４がキューに追加される（図５ＡのステップＳ１１５に対応）。
【０１３１】
時刻ｔ＝ｔ０＋Δｔにキューから先頭のブロックＡ０／３とその次のブロックＢ０／３が取り出され、ブロックＡ０／３の処理がワーカー処理部＃０に割り当てられ、ブロックＢ０／３の処理がワーカー処理部＃１に割り当てられる（図６のステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に処理を開始する（図６のステップＳ２１０に対応）。
【０１３２】
時刻ｔ＝ｔ１にブロックＡ０／３とブロックＢ０／３の処理が終了すると、ブロックＡ０／３の次に処理すべきブロックＡ１／３と、ブロックＢ０／３の次に処理すべきブロックＢ１／３とがキューに追加される（図６のステップＳ２４０に対応）。時刻ｔ＝ｔ０では最後尾のブロックであったブロックＣ０／４が時刻ｔ＝ｔ１では先頭のブロックとなり、ブロックＣ０／４の後にブロックＡ１／３とブロックＢ１／３が追加されている。
【０１３３】
時刻ｔ＝ｔ１＋Δｔにキューから先頭のブロックＣ０／４とその次のブロックＡ１／３が取り出され、ブロックＣ０／４の処理がワーカー処理部＃０に割り当てられ、ブロックＡ１／３の処理がワーカー処理部＃１に割り当てられる（図６のステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に各ブロックの処理を行う（図６のステップＳ２１０に対応）。
【０１３４】
時刻ｔ＝ｔ２にブロックＣ０／４とブロックＡ１／３の処理が終了すると、ブロックＣ０／４の次に処理すべきブロックＣ１／４と、ブロックＡ１／３の次に処理すべきブロックＡ２／３とがキューに追加される（図６のステップＳ２４０に対応）。時刻ｔ＝ｔ１では最後尾のブロックであったブロックＢ１／３が時刻ｔ＝ｔ２では先頭のブロックとなり、ブロックＢ１／３の後にブロックＣ１／４とブロックＡ２／３が追加されている。
【０１３５】
時刻ｔ＝ｔ２＋Δｔにキューから先頭のブロックＢ１／３とその次のブロックＣ１／４が取り出され、ブロックＢ１／３の処理がワーカー処理部＃０に割り当てられ、ブロックＣ１／４の処理がワーカー処理部＃１に割り当てられる（図６のステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に各ブロックの処理を行う（図６のステップＳ２１０に対応）。
【０１３６】
時刻ｔ＝ｔ３にブロックＢ１／３とブロックＣ１／４の処理が終了すると、ブロックＢ１／３の次に処理すべきブロックＢ２／３と、ブロックＣ１／４の次に処理すべきブロックＣ２／４とがキューに追加される（図６のステップＳ２４０に対応）。時刻ｔ＝ｔ２では最後尾のブロックであったブロックＡ２／３が時刻ｔ＝ｔ３では先頭のブロックとなり、ブロックＡ２／３の後にブロックＢ２／３とブロックＣ２／４が追加されている。
【０１３７】
時刻ｔ＝ｔ３＋Δｔにキューから先頭のブロックＡ２／３とその次のブロックＢ２／３が取り出され、ブロックＡ２／３の処理がワーカー処理部＃０に割り当てられ、ブロックＢ２／３の処理がワーカー処理部＃１に割り当てられる（図６のステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に各ブロックの処理を行う（図６のステップＳ２１０に対応）。
【０１３８】
時刻ｔ＝ｔ４にブロックＡ２／３とブロックＢ２／３の処理が終了すると、スライスＡとスライスＢの処理は終了する。時刻ｔ＝ｔ４ではキューにブロックは追加されないので、キューにあるブロックはブロックＣ２／４だけである。
【０１３９】
時刻ｔ＝ｔ４＋ΔｔにキューからブロックＣ２／４が取り出され、ブロックＣ２／４の処理がワーカー処理部＃０に割り当てられる（図６のステップＳ２０５に対応）。ワーカー処理部＃０にブロックＣ２／４の処理が割り当てられると、ワーカー処理部＃０はブロックＣ２／４の処理を行う（図６のステップＳ２１０に対応）。ワーカー処理部＃１にはブロックの処理が割り当てられず、ワーカー処理部＃１は停止している。
【０１４０】
時刻ｔ＝ｔ５にブロックＣ２／４の処理が終了すると、ブロックＣ２／４の次に処理すべきブロックＣ３／４がキューに追加される（図６のステップＳ２４０に対応）。時刻ｔ＝ｔ５では、キューにあるブロックはブロックＣ３／４だけである。
【０１４１】
時刻ｔ＝ｔ５＋ΔｔにキューからブロックＣ３／４が取り出され、ブロックＣ３／４の処理がワーカー処理部＃０に割り当てられる（図６のステップＳ２０５に対応）。ワーカー処理部＃０にブロックＣ３／４の処理が割り当てられると、ワーカー処理部＃０はブロックＣ３／４の処理を行う（図６のステップＳ２１０に対応）。ワーカー処理部＃１にはブロックの処理が割り当てられず、ワーカー処理部＃１は停止している。
【０１４２】
ブロックＣ３／４の処理が終了すると、スライスＣの処理は終了する。この時点よりも前にスライスＡ，Ｂの処理は終了しているため、ブロックＣ３／４の処理が終了した時点で、全てのスライスの処理は終了している。
【０１４３】
この例では、スライスＣの処理がスライスＡ，Ｂの処理よりも相対的に遅れるので、スライスＡ，Ｂの処理が終了した時点で、並列に処理できないスライスＣのブロックＣ２／４，Ｃ３／４が残ってしまう。
【０１４４】
以下では、優先度Ｐ０を使用する場合の復号処理の例を示す。図１４は、２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを復号処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。図１５は、キューの状態を示す図である。図１４と図１５に示す例では、優先度Ｐ０が使用される。優先度Ｐ０を使用する場合の復号処理の例で用いるスライスは、図１１に示したスライスと同じである。
【０１４５】
優先度Ｐ０は次のように使用される。ブロックがキューに追加されたときに、ブロック毎の優先度Ｐ０の高い順にブロックが並べられる。この結果、優先度Ｐ０の最も高いブロックがキューの先頭に配置され、優先的に取り出される。優先度Ｐ０が同じブロックが複数存在するとき、それら複数のブロックは、キューに追加された順に並べられる。キュー内のブロックの順番を変更するのは、ブロックがキューに追加されたときでなくてもよく、ブロックがキューから取り出される直前などでもよい。以上に述べたキューの実装は必ずしも最適ではない。例えば、ヒープ（heap）などのデータ構造を使うとより効率的な実装になる。
【０１４６】
時刻ｔ＝ｔ０に全てのスライスの最初のブロックＡ０／３，Ｂ０／３，Ｃ０／４がキューに追加される（図５ＡのステップＳ１１５に対応）。このとき、ブロックＡ０／３，Ｂ０／３，Ｃ０／４の順にブロックがキューに追加されると仮定する。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ａ０／３）＝Ｐ０（Ｂ０／３）＝Ｐ０（Ｃ０／４）＝１である。３つのブロックの優先度Ｐ０が等しいので、キュー内のブロックの順番は変わらない。
【０１４７】
時刻ｔ＝ｔ０＋Δｔにキューから先頭のブロックＡ０／３とその次のブロックＢ０／３が取り出され、ブロックＡ０／３の処理がワーカー処理部＃０に割り当てられ、ブロックＢ０／３の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に処理を開始する（図５ＢのステップＳ２１０に対応）。
【０１４８】
時刻ｔ＝ｔ１にブロックＡ０／３とブロックＢ０／３の処理が終了すると、ブロックＡ０／３の次に処理すべきブロックＡ１／３と、ブロックＢ０／３の次に処理すべきブロックＢ１／３とがキューに追加される（図５ＢのステップＳ２４０に対応）。このとき、ブロックＡ１／３，Ｂ１／３の順にブロックがキューに追加されると仮定する。時刻ｔ＝ｔ１では、ブロックＣ０／４とブロックＡ１／３とブロックＢ１／３とがキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ｃ０／４）＝１、Ｐ０（Ａ１／３）＝Ｐ０（Ｂ１／３）＝２／３となるので、ブロックＣ０／４，Ａ１／３，Ｂ１／３の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０１４９】
時刻ｔ＝ｔ１＋Δｔにキューから先頭のブロックＣ０／４とその次のブロックＡ１／３が取り出され、ブロックＣ０／４の処理がワーカー処理部＃０に割り当てられ、ブロックＡ１／３の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に各ブロックの処理を行う（図５ＢのステップＳ２１０に対応）。
【０１５０】
時刻ｔ＝ｔ２にブロックＣ０／４とブロックＡ１／３の処理が終了すると、ブロックＣ０／４の次に処理すべきブロックＣ１／４と、ブロックＡ１／３の次に処理すべきブロックＡ２／３とがキューに追加される（図５ＢのステップＳ２４０に対応）。時刻ｔ＝ｔ２では、ブロックＢ１／３とブロックＣ１／４とブロックＡ２／３とがキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ｂ１／３）＝２／３、Ｐ０（Ｃ１／４）＝３／４、Ｐ０（Ａ２／３）＝１／３となるので、ブロックＣ１／４，Ｂ１／３，Ａ２／３の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０１５１】
時刻ｔ＝ｔ２＋Δｔにキューから先頭のブロックＣ１／４とその次のブロックＢ１／３が取り出され、ブロックＣ１／４の処理がワーカー処理部＃０に割り当てられ、ブロックＢ１／３の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に各ブロックの処理を行う（図５ＢのステップＳ２１０に対応）。
【０１５２】
時刻ｔ＝ｔ３にブロックＣ１／４とブロックＢ１／３の処理が終了すると、ブロックＣ１／４の次に処理すべきブロックＣ２／４と、ブロックＢ１／３の次に処理すべきブロックＢ２／３とがキューに追加される（図５ＢのステップＳ２４０に対応）。時刻ｔ＝ｔ３では、ブロックＡ２／３とブロックＣ２／４とブロックＢ２／３とがキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ａ２／３）＝Ｐ０（Ｂ２／３）＝１／３、Ｐ０（Ｃ２／４）＝２／４となるので、ブロックＣ２／４，Ａ２／３，Ｂ２／３の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０１５３】
時刻ｔ＝ｔ３＋Δｔにキューから先頭のブロックＣ２／４とその次のブロックＡ２／３が取り出され、ブロックＣ２／４の処理がワーカー処理部＃０に割り当てられ、ブロックＡ２／３の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に各ブロックの処理を行う（図５ＢのステップＳ２１０に対応）。
【０１５４】
時刻ｔ＝ｔ４にブロックＣ２／４とブロックＡ２／３の処理が終了すると、ブロックＣ２／４の次に処理すべきブロックＣ３／４がキューに追加される（図５ＢのステップＳ２４０に対応）。ブロックＡ２／３の処理が終了したため、スライスＡの処理は終了する。時刻ｔ＝ｔ４では、ブロックＢ２／３とブロックＣ３／４とがキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ｂ２／３）＝１／３、Ｐ０（Ｃ３／４）＝１／４となるので、ブロックＢ２／３，Ｃ３／４の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０１５５】
時刻ｔ＝ｔ４＋Δｔにキューから先頭のブロックＢ２／３とその次のブロックＣ３／４が取り出され、ブロックＢ２／３の処理がワーカー処理部＃０に割り当てられ、ブロックＣ３／４の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に各ブロックの処理を行う（図５ＢのステップＳ２１０に対応）。
【０１５６】
ブロックＢ２／３とブロックＣ３／４の処理が終了すると、スライスＢとスライスＣの処理は終了する。この時点よりも前にスライスＡの処理は終了しているため、ブロックＢ２／３とブロックＣ３／４の処理が終了した時点で、全てのスライスの処理は終了している。
【０１５７】
この例では、優先度Ｐ０を使用しないとスライスＡ，Ｂの処理よりも相対的に遅れてしまうスライスＣの処理を優先的に進めることで、スライスＡ，Ｂ，Ｃの処理がほぼ均等に進むので、並列に処理できないブロックが最後に残ってしまうことはない。
【０１５８】
このように、優先度Ｐ０を使用することで、全てのスライスの処理の進捗割合をできるだけ同一に保ったまま並列処理を進めることができる。たとえ、処理時間が正確に予測できない場合であっても、全てのスライスの処理の進捗割合ができるだけ同一に保たれるので、全てのスライスの処理がほぼ同時に終了する。このため、並列に処理できないブロックが最後に残りにくくなり、最後にワーカー処理部にブロックの処理が割り当てられない状態が発生しにくくなる。よって、スライスの並列処理を効率的に行うことができる。
【０１５９】
＜優先度Ｐ０，Ｐ１を使用したスライスの復号処理の例＞
優先度Ｐ０を使用した場合の復号処理の例と、優先度Ｐ０，Ｐ１を使用した場合の復号処理の例を示す。説明を簡単にするため、キューへのアクセスに必要な時間やブロックの並べ替えに必要な時間を無視できるものと考える。
【０１６０】
図１６は、スライスとブロックの例を示す図である。図１６を参照するに、３つのスライスＡ，Ｂ，Ｃがある。スライスＡ，Ｂ，Ｃは２個のブロックからなる。スライスＡ，Ｂのブロックの分割幅は同一であるが、スライスＣのブロックの分割幅はスライスＡ，Ｂのブロックの分割幅の２倍である。このため、スライスＣの処理時間はスライスＡ，Ｂの処理時間の２倍となる。
【０１６１】
スライスＡはブロックＡ０／２とブロックＡ１／２とに分割される。スライスＡの各ブロックは、ブロックＡ０／２、ブロックＡ１／２の順に処理される。スライスＢはブロックＢ０／２とブロックＢ１／２とに分割される。スライスＢの各ブロックは、ブロックＢ０／２、ブロックＢ１／２の順に処理される。スライスＣはブロックＣ０／２とブロックＣ１／２とに分割される。スライスＣの各ブロックは、ブロックＣ０／２、ブロックＣ１／２の順に処理される。
【０１６２】
図１７は、２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。図１８は、キューの状態を示す図である。図１７と図１８に示す例では、優先度Ｐ０が使用される。
【０１６３】
時刻ｔ＝ｔ０に全てのスライスの最初のブロックＡ０／２，Ｂ０／２，Ｃ０／２がキューに追加される（図５ＡのステップＳ１１５に対応）。このとき、ブロックＡ０／２，Ｂ０／２，Ｃ０／２の順にブロックがキューに追加されると仮定する。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ａ０／２）＝Ｐ０（Ｂ０／２）＝Ｐ０（Ｃ０／２）＝１である。３つのブロックの優先度Ｐ０が等しいので、キュー内のブロックの順番は変わらない。
【０１６４】
時刻ｔ＝ｔ０＋Δｔにキューから先頭のブロックＡ０／２とその次のブロックＢ０／２が取り出され、ブロックＡ０／２の処理がワーカー処理部＃０に割り当てられ、ブロックＢ０／２の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に処理を開始する（図５ＢのステップＳ２１０に対応）。
【０１６５】
時刻ｔ＝ｔ１にブロックＡ０／２とブロックＢ０／２の処理が終了すると、ブロックＡ０／２の次に処理すべきブロックＡ１／２と、ブロックＢ０／２の次に処理すべきブロックＢ１／２とがキューに追加される（図５ＢのステップＳ２４０に対応）。このとき、ブロックＡ１／２，Ｂ１／２の順にブロックがキューに追加されると仮定する。（１）式によれば、時刻ｔ＝ｔ１にキューに置かれている各ブロックの優先度Ｐ０は、Ｐ０（Ｃ０／２）＝１、Ｐ０（Ａ１／２）＝Ｐ０（Ｂ１／２）＝１／２となるので、ブロックＣ０／２，Ａ１／２，Ｂ１／２の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０１６６】
時刻ｔ＝ｔ１＋Δｔにキューから先頭のブロックＣ０／２とその次のブロックＡ１／２が取り出され、ブロックＣ０／２の処理がワーカー処理部＃０に割り当てられ、ブロックＡ１／２の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に各ブロックの処理を行う（図５ＢのステップＳ２１０に対応）。
【０１６７】
時刻ｔ＝ｔ２にブロックＡ１／２の処理が終了する。この時点でブロックＣ０／２の処理は終了していない。ブロックＡ１／２の処理が終了したため、スライスＡの処理は終了する。時刻ｔ＝ｔ２では、ブロックＢ１／２のみがキューに置かれている。
【０１６８】
時刻ｔ＝ｔ２＋ΔｔにキューからブロックＢ１／２が取り出され、ブロックＢ１／２の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。ワーカー処理部＃１にブロックＢ１／２の処理が割り当てられると、ワーカー処理部＃１はブロックＢ１／２の処理を行う（図５ＢのステップＳ２１０に対応）。このとき、ワーカー処理部＃０はブロックＣ０／２の処理を継続している。
【０１６９】
時刻ｔ＝ｔ３にブロックＢ１／２とブロックＣ０／２の処理が終了すると、ブロックＣ０／２の次に処理すべきブロックＣ１／２がキューに追加される（図５ＢのステップＳ２４０に対応）。ブロックＢ１／２の処理が終了したため、スライスＢの処理は終了する。時刻ｔ＝ｔ３では、ブロックＣ１／２のみがキューに置かれている。
【０１７０】
時刻ｔ＝ｔ３＋ΔｔにキューからブロックＣ１／２が取り出され、ブロックＣ１／２の処理がワーカー処理部＃０に割り当てられる（図５ＢのステップＳ２０５に対応）。ワーカー処理部＃０にブロックＣ１／２の処理が割り当てられると、ワーカー処理部＃０はブロックＣ１／２の処理を行う（図５ＢのステップＳ２１０に対応）。ワーカー処理部＃１にはブロックの処理が割り当てられず、ワーカー処理部＃１は停止している。
【０１７１】
ブロックＣ１／２の処理が終了すると、スライスＣの処理は終了する。この時点よりも前にスライスＡ，Ｂの処理は終了しているため、ブロックＣ１／２の処理が終了した時点で、全てのスライスの処理は終了している。
【０１７２】
この例では、スライスＡ，Ｂのブロックよりも処理時間がかかるスライスＣのブロックが最後に残ってしまう。
【０１７３】
以下では、優先度Ｐ０に加えて優先度Ｐ１を使用する場合の処理の例を示す。図１９は、２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。図２０は、キューの状態を示す図である。図１９と図２０に示す例では、優先度Ｐ０，Ｐ１が使用される。優先度Ｐ０，Ｐ１を使用する場合の処理の例で用いるスライスは、図１６に示したスライスと同じである。スライスＡ，Ｂの処理時間をＴとし、スライスＣの処理時間を２Ｔとする。
【０１７４】
優先度Ｐ０，Ｐ１は次のように使用される。ブロックがキューに追加されたときに、ブロック毎の優先度Ｐ０に基づいて、キュー内のブロックの順番が決定される。優先度Ｐ０が同じブロックが複数存在するとき、それら複数のブロックの順番は、ブロック毎の優先度Ｐ１に基づいて決定される。優先度Ｐ１が同じブロックが複数存在するとき、それら複数のブロックは、キューに追加された順に並べられる。キュー内のブロックの順番を変更するのは、ブロックがキューに追加されたときでなくてもよく、ブロックがキューから取り出される直前などでもよい。
【０１７５】
時刻ｔ＝ｔ０に全てのスライスの最初のブロックＡ０／２，Ｂ０／２，Ｃ０／２がキューに追加される（図５ＡのステップＳ１１５に対応）。このとき、ブロックＡ０／２，Ｂ０／２，Ｃ０／２の順にブロックがキューに追加されると仮定する。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ａ０／２）＝Ｐ０（Ｂ０／２）＝Ｐ０（Ｃ０／２）＝１である。３つのブロックの優先度Ｐ０が等しいので、優先度Ｐ１が使用される。（４）式によれば、Ｐ１（Ａ０／２）＝Ｐ１（Ｂ０／２）＝Ｔ、Ｐ１（Ｃ０／２）＝２Ｔとなるので、ブロックＣ０／２，Ａ０／２，Ｂ０／２の順にブロックが並ぶ。
【０１７６】
時刻ｔ＝ｔ０＋Δｔにキューから先頭のブロックＣ０／２とその次のブロックＡ０／２が取り出され、ブロックＣ０／２の処理がワーカー処理部＃０に割り当てられ、ブロックＡ０／２の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に処理を開始する（図５ＢのステップＳ２１０に対応）。
【０１７７】
時刻ｔ＝ｔ１にブロックＡ０／２の処理が終了すると、ブロックＡ０／２の次に処理すべきブロックＡ１／２がキューに追加される（図５ＢのステップＳ２４０に対応）。この時点でブロックＣ０／２の処理は終了していない。時刻ｔ＝ｔ１では、ブロックＢ０／２とブロックＡ１／２がキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ｂ０／２）＝１、Ｐ０（Ａ１／２）＝１／２であるので、ブロックＢ０／２，Ａ１／２の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０１７８】
時刻ｔ＝ｔ１＋Δｔにキューから先頭のブロックＢ０／２が取り出され、ブロックＢ０／２の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。ワーカー処理部＃１にブロックＢ０／２の処理が割り当てられると、ワーカー処理部＃１はブロックＢ０／２の処理を行う（図５ＢのステップＳ２１０に対応）。このとき、ワーカー処理部＃０はブロックＣ０／２の処理を継続している。
【０１７９】
時刻ｔ＝ｔ２にブロックＣ０／２とブロックＢ０／２の処理が終了すると、ブロックＣ０／２の次に処理すべきブロックＣ１／２と、ブロックＢ０／２の次に処理すべきブロックＢ１／２とがキューに追加される（図５ＢのステップＳ２４０に対応）。時刻ｔ＝ｔ２では、ブロックＡ１／２とブロックＣ１／２とブロックＢ１／２とがキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ａ１／２）＝Ｐ０（Ｃ１／２）＝Ｐ０（Ｂ１／２）＝１／２となる。３つのブロックの優先度Ｐ０が等しいので、優先度Ｐ１が使用される。（４）式によれば、Ｐ１（Ｃ１／２）＝Ｔ、Ｐ１（Ａ１／２）＝Ｐ１（Ｂ１／２）＝Ｔ／２、となるので、ブロックＣ１／２，Ａ１／２，Ｂ１／２の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０１８０】
時刻ｔ＝ｔ２＋Δｔにキューから先頭のブロックＣ１／２とその次のブロックＡ１／２が取り出され、ブロックＣ１／２の処理がワーカー処理部＃０に割り当てられ、ブロックＡ１／２の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に各ブロックの処理を行う（図５ＢのステップＳ２１０に対応）。
【０１８１】
時刻ｔ＝ｔ３にブロックＡ１／２の処理が終了する。ブロックＡ１／２の処理が終了したため、スライスＡの処理は終了する。この時点でブロックＣ１／２の処理は終了していない。時刻ｔ＝ｔ３では、ブロックＢ１／２がキューに置かれている。
【０１８２】
時刻ｔ＝ｔ３＋Δｔにキューから先頭のブロックＢ１／２が取り出され、ブロックＢ１／２の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。ワーカー処理部＃１にブロックＢ１／２の処理が割り当てられると、ワーカー処理部＃１はブロックＢ１／２の処理を行う（図５ＢのステップＳ２１０に対応）。このとき、ワーカー処理部＃０はブロックＣ１／２の処理を継続している。
【０１８３】
ブロックＣ１／２とブロックＢ１／２の処理が終了すると、スライスＣとスライスＢの処理は終了する。この時点よりも前にスライスＡの処理は終了しているため、ブロックＣ１／２とブロックＢ１／２の処理が終了した時点で、全てのスライスの処理は終了している。
【０１８４】
この例では、スライスＡ，Ｂよりも処理時間がかかるスライスＣの処理を優先的に進めることで、スライスＣのブロックが最後に単独で残ってしまうことはない。
【０１８５】
このように、優先度Ｐ１を使用することで、処理時間が相対的に長いスライスのブロックが最後に残りにくくなる。このため、最後にワーカー処理部にブロックの処理が割り当てられない状態が発生しにくくなる。よって、スライスの並列処理を効率的に行うことができる。
【０１８６】
＜優先度Ｐ０，Ｐ１，Ｐ２を使用したスライスの復号処理の例＞
優先度Ｐ０，Ｐ１，Ｐ２を使用した場合のより複雑な復号処理の例を示す。説明を簡単にするため、キューへのアクセスに必要な時間やブロックの並べ替えに必要な時間を無視できるものと考える。
【０１８７】
図２１は、スライスとブロックの例を示す図である。図２１を参照するに、３つのスライスＡ，Ｂ，Ｃがある。スライスＡ，Ｂは４個のブロックからなり、スライスＣは３個のブロックからなる。スライスＡ，Ｂは均等に４つのブロックに分割されるが、スライスＣは１：２：１の比で３つのブロックに分割される。スライスＢ，Ｃの処理時間は同じであるが、スライスＡの処理時間はスライスＢ，Ｃの処理時間の１．５倍である。
【０１８８】
スライスＡは、処理時間が等しいブロックＡ０／４とブロックＡ１／４とブロックＡ２／４とブロックＡ３／４とに分割される。スライスＡの各ブロックは、ブロックＡ０／４、ブロックＡ１／４、ブロックＡ２／４、ブロックＡ３／４の順に処理される。スライスＡの処理時間を６Ｔとする。
【０１８９】
スライスＢは、処理時間が等しいブロックＢ０／４とブロックＢ１／４とブロックＢ２／４とブロックＢ３／４とに分割される。スライスＢの各ブロックは、ブロックＢ０／４、ブロックＢ１／４、ブロックＢ２／４、ブロックＢ３／４の順に処理される。スライスＢの処理時間を４Ｔとする。
【０１９０】
スライスＣはブロックＣ０／４とブロックＣ１／４とブロックＣ３／４とに分割される。ブロックＣ０／４，Ｃ３／４の処理時間は等しいが、ブロックＣ１／４の処理時間はブロックＣ０／４，Ｃ３／４の処理時間の２倍である。スライスＣの各ブロックは、ブロックＣ０／４、ブロックＣ１／４、ブロックＣ３／４の順に処理される。
【０１９１】
図２２は、２つのワーカー処理部＃０，＃１が３つのスライスＡ，Ｂ，Ｃを復号処理するときに各ワーカー処理部に対してブロックが割り当てられる様子を示す図である。図２３は、キューの状態を示す図である。図２２と図２３に示す例では、優先度Ｐ０，Ｐ１，Ｐ２が使用される。
【０１９２】
優先度Ｐ０，Ｐ１，Ｐ２は次のように使用される。ブロックがキューに追加されたときに、ブロック毎の優先度Ｐ０に基づいて、キュー内のブロックの順番が決定される。優先度Ｐ０が同じブロックが複数存在するとき、それら複数のブロックの順番は、ブロック毎の優先度Ｐ１に基づいて決定される。優先度Ｐ１が同じブロックが複数存在するとき、それら複数のブロックの順番は、ブロック毎の優先度Ｐ２に基づいて決定される。キュー内のブロックの順番を変更するのは、ブロックがキューに追加されたときでなくてもよく、ブロックがキューから取り出される直前などでもよい。
【０１９３】
時刻ｔ＝ｔ０に全てのスライスの最初のブロックＡ０／４，Ｂ０／４，Ｃ０／４がキューに追加される（図５ＡのステップＳ１１５に対応）。このとき、ブロックＡ０／４，Ｂ０／４，Ｃ０／４の順にブロックがキューに追加されると仮定する。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ａ０／４）＝Ｐ０（Ｂ０／４）＝Ｐ０（Ｃ０／４）＝１である。３つのブロックの優先度Ｐ０が等しいので、優先度Ｐ１が使用される。（４）式によれば、Ｐ１（Ａ０／４）＝６Ｔ、Ｐ１（Ｂ０／４）＝Ｐ１（Ｃ０／４）＝４Ｔとなるので、ブロックＡ０／４はブロックＢ０／４，Ｃ０／４よりも前に置かれる。
【０１９４】
また、２つのブロックＢ０／４，Ｃ０／４の優先度Ｐ１が等しいので、優先度Ｐ２が使用される。ブロックＢ０／４，Ｃ０／４がキューに追加された時刻は同じなので、ブロックＢ０／４，Ｃ０／４の優先度Ｐ２は等しい。このため、ブロックＢ０／４，Ｃ０／４の順番は変更されない。よって、時刻ｔ＝ｔ０では、ブロックＡ０／４，Ｂ０／４，Ｃ０／４の順にブロックが並ぶ。
【０１９５】
時刻ｔ＝ｔ０＋Δｔにキューから先頭のブロックＡ０／４とその次のブロックＢ０／４が取り出され、ブロックＡ０／４の処理がワーカー処理部＃０に割り当てられ、ブロックＢ０／４の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に処理を開始する（図５ＢのステップＳ２１０に対応）。
【０１９６】
時刻ｔ＝ｔ１にブロックＢ０／４の処理が終了すると、ブロックＢ０／４の次に処理すべきブロックＢ１／４がキューに追加される（図５ＢのステップＳ２４０に対応）。この時点でブロックＡ０／４の処理は終了していない。時刻ｔ＝ｔ１では、ブロックＣ０／４とブロックＢ１／４がキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ｃ０／４）＝１、Ｐ０（Ｂ１／４）＝３／４となるので、ブロックＣ０／４，Ｂ１／４の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０１９７】
時刻ｔ＝ｔ１＋Δｔにキューから先頭のブロックＣ０／４が取り出され、ブロックＣ０／４の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。ワーカー処理部＃１にブロックＣ０／４の処理が割り当てられると、ワーカー処理部＃１はブロックＣ０／４の処理を行う（図５ＢのステップＳ２１０に対応）。このとき、ワーカー処理部＃０はブロックＡ０／４の処理を継続している。
【０１９８】
時刻ｔ＝ｔ２にブロックＡ０／４の処理が終了すると、ブロックＡ０／４の次に処理すべきブロックＡ１／４がキューに追加される（図５ＢのステップＳ２４０に対応）。この時点でブロックＣ０／４の処理は終了していない。時刻ｔ＝ｔ２では、ブロックＢ１／４とブロックＡ１／４がキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ｂ１／４）＝３／４、Ｐ０（Ａ１／４）＝３／４となる。各ブロックの優先度Ｐ０が等しいので、優先度Ｐ１が使用される。（４）式によれば、Ｐ１（Ｂ１／４）＝３Ｔ、Ｐ１（Ａ１／４）＝４．５Ｔとなるので、ブロックＡ１／４，Ｂ１／４の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０１９９】
時刻ｔ＝ｔ２＋Δｔにキューから先頭のブロックＡ１／４が取り出され、ブロックＡ１／４の処理がワーカー処理部＃０に割り当てられる（図５ＢのステップＳ２０５に対応）。ワーカー処理部＃０にブロックＡ１／４の処理が割り当てられると、ワーカー処理部＃０はブロックＡ１／４の処理を行う（図５ＢのステップＳ２１０に対応）。このとき、ワーカー処理部＃１はブロックＣ０／４の処理を継続している。
【０２００】
時刻ｔ＝ｔ３にブロックＣ０／４の処理が終了すると、ブロックＣ０／４の次に処理すべきブロックＣ１／４がキューに追加される（図５ＢのステップＳ２０５に対応）。この時点でブロックＡ１／４の処理は終了していない。時刻ｔ＝ｔ３では、ブロックＢ１／４とブロックＣ１／４がキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ｂ１／４）＝３／４、Ｐ０（Ｃ１／４）＝３／４となる。各ブロックの優先度Ｐ０が等しいので、優先度Ｐ１が使用される。（４）式によれば、Ｐ１（Ｂ１／４）＝３Ｔ、Ｐ１（Ｃ１／４）＝３Ｔとなる。
【０２０１】
各ブロックの優先度Ｐ１が等しいので、優先度Ｐ２が使用される。各ブロックの優先度Ｐ２は、Ｐ２（Ｂ１／４）＝ｔ１、Ｐ２（Ｃ１／４）＝ｔ３となる。優先度Ｐ２を使用すると、ブロックＣ１／４，Ｂ１／４の順にブロックが並び（図５ＢのステップＳ２４５に対応）、より遅い時刻にキューに追加されたブロックが、より早い時刻にキューに追加されたブロックよりも優先的に処理されるようになる。
【０２０２】
時刻ｔ＝ｔ３＋Δｔにキューから先頭のブロックＣ１／４が取り出され、ブロックＣ１／４の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。ワーカー処理部＃１にブロックＣ１／４の処理が割り当てられると、ワーカー処理部＃１はブロックＣ１／４の処理を行う（図５ＢのステップＳ２１０に対応）。このとき、ワーカー処理部＃０はブロックＡ１／４の処理を継続している。
【０２０３】
時刻ｔ＝ｔ４にブロックＡ１／４の処理が終了すると、ブロックＡ１／４の次に処理すべきブロックＡ２／４がキューに追加される（図５ＢのステップＳ２４０に対応）。この時点でブロックＣ１／４の処理は終了していない。時刻ｔ＝ｔ４では、ブロックＢ１／４とブロックＡ２／４がキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ｂ１／４）＝３／４、Ｐ０（Ａ２／４）＝２／４となるので、ブロックＢ１／４，Ａ２／４の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０２０４】
時刻ｔ＝ｔ４＋Δｔにキューから先頭のブロックＢ１／４が取り出され、ブロックＢ１／４の処理がワーカー処理部＃０に割り当てられる（図５ＢのステップＳ２０５に対応）。ワーカー処理部＃０にブロックＢ１／４の処理が割り当てられると、ワーカー処理部＃０はブロックＢ１／４の処理を行う（図５ＢのステップＳ２１０に対応）。このとき、ワーカー処理部＃１はブロックＣ１／４の処理を継続している。
【０２０５】
時刻ｔ＝ｔ５にブロックＢ１／４とブロックＣ１／４の処理が終了すると、ブロックＢ１／４の次に処理すべきブロックＢ２／４と、ブロックＣ１／４の次に処理すべきブロックＣ３／４とがキューに追加される（図５ＢのステップＳ２４０に対応）。時刻ｔ＝ｔ５では、ブロックＡ２／４とブロックＢ２／４とブロックＣ３／４とがキューに置かれている。
【０２０６】
（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ａ２／４）＝Ｐ０（Ｂ２／４）＝２／４、Ｐ０（Ｃ３／４）＝１／４となるので、ブロックＡ２／４，Ｂ２／４はブロックＣ３／４よりも前に置かれる。２つのブロックＡ２／４，Ｂ２／４の優先度Ｐ０が等しいので、優先度Ｐ１が使用される。（４）式によれば、Ｐ１（Ａ２／４）＝３Ｔ、Ｐ１（Ｂ２／４）＝２Ｔとなるので、ブロックＡ２／４はブロックＢ２／４よりも前に置かれる。よって、時刻ｔ＝ｔ５では、ブロックＡ２／４，Ｂ２／４，Ｃ３／４の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０２０７】
時刻ｔ＝ｔ５＋Δｔにキューから先頭のブロックＡ２／４とその次のブロックＢ２／４が取り出され、ブロックＡ２／４の処理がワーカー処理部＃０に割り当てられ、ブロックＢ２／４の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。各ワーカー処理部にブロックの処理が割り当てられると、各ワーカー処理部は並列に処理を開始する（図５ＢのステップＳ２１０に対応）。
【０２０８】
時刻ｔ＝ｔ６にブロックＢ２／４の処理が終了すると、ブロックＢ２／４の次に処理すべきブロックＢ３／４がキューに追加される（図５ＢのステップＳ２４０に対応）。この時点でブロックＡ２／４の処理は終了していない。時刻ｔ＝ｔ６では、ブロックＣ３／４とブロックＢ３／４がキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ｃ３／４）＝Ｐ０（Ｂ３／４）＝１／４となる。各ブロックの優先度Ｐ０が等しいので、優先度Ｐ１が使用される。（４）式によれば、Ｐ１（Ｃ３／４）＝Ｐ１（Ｂ３／４）＝Ｔとなる。
【０２０９】
各ブロックの優先度Ｐ１が等しいので、優先度Ｐ２が使用される。各ブロックの優先度Ｐ２は、Ｐ２（Ｃ３／４）＝ｔ５、Ｐ２（Ｂ３／４）＝ｔ６となる。優先度Ｐ２を使用すると、より遅い時刻にキューに追加されたブロックが、より早い時刻にキューに追加されたブロックよりも優先的に処理される。このため、ブロックＢ３／４，Ｃ３／４の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０２１０】
時刻ｔ＝ｔ６＋Δｔにキューから先頭のブロックＢ３／４が取り出され、ブロックＢ３／４の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。ワーカー処理部＃１にブロックＢ３／４の処理が割り当てられると、ワーカー処理部＃１はブロックＢ３／４の処理を行う（図５ＢのステップＳ２１０に対応）。このとき、ワーカー処理部＃０はブロックＡ２／４の処理を継続している。
【０２１１】
時刻ｔ＝ｔ７にブロックＡ２／４の処理が終了すると、ブロックＡ２／４の次に処理すべきブロックＡ３／４がキューに追加される（図５ＢのステップＳ２４０に対応）。この時点でブロックＢ３／４の処理は終了していない。時刻ｔ＝ｔ７では、ブロックＣ３／４とブロックＡ３／４がキューに置かれている。（１）式によれば、各ブロックの優先度Ｐ０は、Ｐ０（Ｃ３／４）＝Ｐ０（Ａ３／４）＝１／４となる。各ブロックの優先度Ｐ０が等しいので、優先度Ｐ１が使用される。（４）式によれば、Ｐ１（Ｃ３／４）＝Ｔ、Ｐ１（Ａ３／４）＝１．５Ｔとなるので、ブロックＡ３／４，Ｃ３／４の順にブロックが並ぶ（図５ＢのステップＳ２４５に対応）。
【０２１２】
時刻ｔ＝ｔ７＋Δｔにキューから先頭のブロックＡ３／４が取り出され、ブロックＡ３／４の処理がワーカー処理部＃０に割り当てられる（図５ＢのステップＳ２０５に対応）。ワーカー処理部＃０にブロックＡ３／４の処理が割り当てられると、ワーカー処理部＃０はブロックＡ３／４の処理を行う（図５ＢのステップＳ２１０に対応）。このとき、ワーカー処理部＃１はブロックＢ３／４の処理を継続している。
【０２１３】
時刻ｔ＝ｔ８にブロックＢ３／４の処理が終了する。ブロックＢ３／４の処理が終了したため、スライスＢの処理は終了する。この時点でブロックＡ３／４の処理は終了していない。時刻ｔ＝ｔ８では、ブロックＣ３／４がキューに置かれている。
【０２１４】
時刻ｔ＝ｔ８＋Δｔにキューから先頭のブロックＣ３／４が取り出され、ブロックＣ３／４の処理がワーカー処理部＃１に割り当てられる（図５ＢのステップＳ２０５に対応）。ワーカー処理部＃１にブロックＣ３／４の処理が割り当てられると、ワーカー処理部＃１はブロックＣ３／４の処理を行う（図５ＢのステップＳ２１０に対応）。このとき、ワーカー処理部＃０はブロックＡ３／４の処理を継続している。
【０２１５】
ブロックＡ３／４とブロックＣ３／４の処理が終了すると、スライスＡとスライスＣの処理は終了する。この時点よりも前にスライスＢの処理は終了しているため、ブロックＡ３／４とブロックＣ３／４の処理が終了した時点で、全てのスライスの処理は終了している。
【０２１６】
この例では、優先度Ｐ０を使用することで、全てのスライスの処理の進捗割合をできるだけ同一に保ったまま並列処理を進めることができる。また、優先度Ｐ１を使用することで、処理時間が相対的に長いスライスＡのブロックが最後に単独で残ることはない。よって、スライスの並列処理を効率的に行うことができる。
【０２１７】
また、この例では、優先度Ｐ２を使用することで、ワーカー処理部＃１がスライスＣのブロックＣ０／４，Ｃ１／４の処理を連続して行い、スライスＢのブロックＢ２／４，Ｂ３／４の処理を連続して行っている。このように、同じスライスのブロックの処理を連続して行うことで、キャッシュの利用効率が高まり、処理速度が向上する。
【０２１８】
以上説明したように、第１の実施形態によれば、スライスを分割したブロックの単位でワーカー処理部に処理が割り当てられるので、スライスの単位でワーカー処理部に処理が割り当てられる場合と比較して、いずれかのワーカー処理部が処理の順番待ちのために処理対象が供給されずに休止することを抑制できる。そのため、ワーカー処理部全体の休止時間の合計が減少する。その結果、ワーカー処理部全体の利用効率が高まる。したがって、符号化されたスライスの復号処理の速度が向上する。
【０２１９】
プロセッサの数Ｎとスライスの数Ｍにかかわらず、同一の方法で全てのワーカー処理部に、なるべく均等にスライスの処理が割り当てられる。特に、各スライスの処理時間が事前に分からない、もしくは各スライスの処理時間を正確に予測できない場合でも、全てのスライスの進捗状況がほぼ同一に保たれたまま処理が進む。このため、全体の処理時間に占める、並列に処理できる時間の割合が高くなり、効率的にワーカー処理部を使うことができる。
【０２２０】
ＣＰＵに一対一に対応した、プロセッサの数と同数のワーカー処理部のみが使用されるため、スライスの処理中には、ワーカー処理部のコンテキストスイッチが起こらない。コンテキストスイッチとは、複数のワーカー処理部が同じプロセッサを共有するために、プロセッサの実行状態（コンテキスト）を保存または復元する操作のことである。ワーカー処理部のコンテキストスイッチが起こらないため、処理速度の低下が防止される。
【０２２１】
スライスの処理時間がＯＳのタイムクォンタムに比べて小さい場合でも、各ワーカー処理部はブロック単位で並列に処理を行うことができる。短い間隔で複数のスライスを切り替えながら処理を実行することで、プロセッサの数よりも多いスライスを擬似的に並列に処理することができる。
【０２２２】
キューには並列処理可能なブロックのみが置かれており、キューから取り出されたラッパーブロックは、すぐに任意のワーカー処理部に割り当てられる。このため、スライスの処理中には、キューへのアクセス以外の同期処理が不要である。
【０２２３】
｛第２の実施形態｝
本発明の第２の実施形態は、符号化された画像データを復号処理する編集装置および編集方法についての例である。
【０２２４】
図２４は、本発明の第２の実施形態に係る編集装置のハードウェア構成を示すブロック図である。なお、第１の実施形態と共通する要素については同じ符号を付し、その説明を省略する。
【０２２５】
図２４を参照するに、編集装置１００は、光ディスクやその他の記録媒体を駆動するためのドライブ１０１、ＣＰＵ２０、ＣＰＵ２１、ＣＰＵ１０２、ＲＯＭ２３、ＲＯＭ１０３、ＲＡＭ２２、ＲＡＭ１０４、ＨＤＤ１０５、通信インターフェース１０６、入力インターフェース１０７、出力インターフェース１０８、ビデオ・オーディオインターフェース１１４、およびこれらを接続するバス１１０を備えている。
【０２２６】
編集装置１００は、先の図１に示したＣＰＵ２０、ＣＰＵ２１、ＲＡＭ２２、およびＲＯＭ２３からなる第１の実施形態に係る復号装置と同様の復号装置を有する。さらに、図２４においては、図示を省略するが、編集装置１００は、先の図３に示した機能構成と同様の機能構成を有する。編集装置１００は、さらに、符号化処理機能と、編集機能を有する。なお、編集装置１００において、符号化処理機能は必須ではない。
【０２２７】
ドライブ１０１にはリムーバブルメディア１０１ａが装着され、このリムーバブルメディア１０１ａからデータの読み出しが行われる。ドライブ１０１は外付けのドライブであってもよい。ドライブ１０１は、光ディスク、磁気ディスク、光磁気ディスク、ブルーレイディスク、半導体メモリなどを採用することができる。素材データの読み出しは、通信インターフェース１０６を介して接続可能なネットワーク上のリソースから行ってもよい。
【０２２８】
ＣＰＵ１０２は、ＲＯＭ１０３に記録されている制御プログラムをＲＡＭ１０４に展開し、編集装置１００全体の動作を制御する。
【０２２９】
ＨＤＤ１０５は、編集装置としてのアプリケーションプログラムが格納されている。ＣＰＵ１０２がこのアプリケーションプログラムをＲＡＭ１０４上で展開し、コンピュータを編集装置として機能させる。また、リムーバブルメディア１０１ａから読み出された素材データや各クリップの編集データなどをこのＨＤＤ１０５に格納してもよい。
【０２３０】
通信インターフェース１０６は、たとえばＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、ＬＡＮ、ＨＤＭＩ等のインターフェースである。
【０２３１】
入力インターフェース１０７は、キーボードやマウスなどの操作部４００を介してユーザが入力する指示を受け付け、バス１１０を介してＣＰＵ１０２に操作信号を供給する。
【０２３２】
出力インターフェース１０８は、ＬＣＤ（液晶表示装置）やＣＲＴなどの表示装置、スピーカなどの出力装置５００に、ＣＰＵ１０２からの画像データや音声データを供給する。
【０２３３】
ビデオ・オーディオインターフェース１１４は、編集装置１００の外部の装置とバス１１０との間でデータの受け渡しを行う。ビデオ・オーディオインターフェース１１４は、例えば、ＳＤＩ（Ｓｅｒｉａｌ  Ｄｉｇｉｔａｌ  Ｉｎｔｅｒｆａｃｅ）などに準拠したインターフェースである。
【０２３４】
図２５は、本発明の第２の実施形態に係る編集装置の機能構成図である。
【０２３５】
図２５を参照するに、編集装置１００のＣＰＵ１０２は、メモリ上に展開されるアプリケーションプログラムによって、ユーザインターフェース部７０、編集部７３、情報入力部７４、情報出力部７５の各機能ブロックを構成する。
【０２３６】
このような各機能ブロックにより、素材データと編集データを含むプロジェクトファイルのインポート機能、各クリップに対する編集機能、素材データおよび／または編集データを含むプロジェクトファイルのエクスポート機能、プロジェクトファイルのエクスポート時における素材データに対するマージン設定機能などを実現する。以下、編集機能について詳細に説明する。
【０２３７】
図２６は、本発明の第２の実施形態に係る編集装置の編集画面の一例を示す図である。
【０２３８】
図２６を図２５とともに参照するに、編集画面の表示データが表示制御部７２により生成され、出力装置５００のディスプレイに出力される。
【０２３９】
編集画面１５０は、編集されたコンテンツや取得した素材データの再生画面を表示する再生ウィンドウ１５１、各クリップがタイムラインに沿って配置される複数のトラックで構成されるタイムラインウィンドウ１５２、取得した素材データをアイコンで表示するビンウィンドウ１５３などを備えている。
【０２４０】
ユーザインターフェース部７０は、操作部４００を介してユーザが入力した指示を受け付ける指示受付部７１、ディスプレイやスピーカなどの出力装置５００に対する表示制御を行う表示制御部７２を含んでいる。
【０２４１】
編集部７３は、操作部４００を介してユーザから入力された指示により指定されたクリップが参照する素材データ、あるいはデフォルトで指定されているプロジェクト情報を備えるクリップが参照する素材データを、情報入力部７４を介して取得する。また、編集部７３は、操作部４００を介してユーザから入力された指示により、後述するクリップのタイムラインウィンドウ上の配置、クリップのトリミングや、シーン間のトランジッションの設定や、ビデオフィルタをかける等の編集処理を行う。
【０２４２】
情報入力部７４は、ＨＤＤ１０５内に記録されている素材データが指定された場合には、ビンウィンドウ１５３にアイコンを表示する。ＨＤＤ１０５内に記録されていない素材データが指定された場合には、ネットワーク上のリソースやリムーバブルメディアなどから素材データを読み出してビンウィンドウ１５３にアイコンを表示する。図示した例では、３つの素材データがアイコンＩＣ１〜ＩＣ３で表示されている。
【０２４３】
指示受付部７１は、編集に用いるクリップと、素材データの参照範囲と、その参照範囲がコンテンツの時間軸上にしめる時間位置との指定を編集画面上で受け付ける。具体的には、指示受付部７１は、クリップＩＤ、参照範囲の開始点および時間長、クリップが配置されるコンテンツ上の時間情報などの指定を受け付ける。このためにユーザは、表示されているクリップ名を手がかりに、所望の素材データのアイコンをタイムライン上にドラッグ＆ドロップする。指示受付部７１は、この操作によるクリップＩＤの指定を受け付けて、選択されたクリップが参照する参照範囲に応じた時間長でトラック上にクリップが配置される。
【０２４４】
トラック上に配置されたクリップは、クリップの開始点、終了点、タイムライン上の時間的な配置などを適宜変更することが可能となっている。例えば、編集画面上に表示されるマウスカーソルを移動させて所定の操作を行うことで指示を入力することが可能である。
【０２４５】
図２７は、本発明の第２の実施形態に係る編集方法を示すフローチャートである。圧縮符号化された素材データを編集する場合を例に挙げて、図２７を参照しつつ、本発明の第２の実施形態に係る編集方法を説明する。
【０２４６】
最初に、ステップＳ４００では、ユーザによりＨＤＤ１０５に記録されている、符号化された素材データが指定されると、ＣＰＵ１０２はその指定を受付けて、その素材データをビンウィンドウ１５３にアイコンとして表示する。さらに、ユーザにより、その表示されたアイコンをタイムラインウィンドウ１５２に配置する指示がされると、ＣＰＵ１０２はその指示を受付けて、素材のクリップをタイムラインウィンドウ１５２に配置する。
【０２４７】
次いで、ステップＳ４１０では、ユーザにより、素材について、操作部４００を介した所定の操作により表示される編集内容の中から、例えば復号処理および伸張処理が選択されると、ＣＰＵ１０２はその選択を受け付ける。
【０２４８】
次いで、ステップＳ４２０では、復号処理および伸張処理の指示を受け付けたＣＰＵ１０２は、ＣＰＵ２０，２１に復号処理および伸張処理の指示を出力する。ＣＰＵ１０２から復号処理および伸張処理の指示が入力されたＣＰＵ２０，２１は、圧縮符号化された素材データを復号処理および伸張処理する。この際、ＣＰＵ２０，２１は、第１の実施形態に係る復号方法を実行して、復号処理された素材データを生成する。
【０２４９】
次いで、ステップＳ４３０では、ＣＰＵ２０，２１は、ステップＳ４２０で生成された素材データを、バス１１０を介してＲＡＭ２２に格納する。ＲＡＭ２２に一時的に格納された素材データはＨＤＤ１０５に記録される。なお、ＨＤＤに記録する代わりに、編集装置外の装置に素材データを出力してもよい。
【０２５０】
なお、上記のステップＳ４００とＳ４１０との間に、クリップのトリミングや、シーン間のトランジッションの設定や、ビデオフィルタをかけてもよい。これらの処理を行う場合は、処理の対象となるクリップやクリップの一部について、ステップＳ４２０の復号処理および伸張処理を行う。その後に処理されたクリップやクリップの一部は記憶される。その後のレンダリングの際に他のクリップやクリップの他の部分と合成される。
【０２５１】
第２の実施形態によれば、編集装置は、第１の実施の形態と同様の復号装置を有し、第１の実施の形態と同様の復号方法を用いて、符号化された素材データを復号処理するので、第１の実施形態と同様の効果が得られ、復号処理の効率が向上する。
【０２５２】
なお、復号処理の際に、ＣＰＵ１０２が、ＣＰＵ２０およびＣＰＵ２１と同様のステップを実行してもよい。特に、ＣＰＵ１０２が復号処理以外の処理を行わない期間に実行することが好ましい。
【０２５３】
以上、本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、請求の範囲に記載された本発明の範囲内において、種々の変形・変更が可能である。例えば、符号化された音声データの復号処理に本発明を適用してもよい。たとえば、上述した実施形態では、ＭＰＥＧ−２に準拠した復号処理を例に説明したが、ＭＰＥＧ−２に限定されず、他の画像符号化方式、たとえば、ＭＰＥＧ−４ヴィジュアル、ＭＰＥＧ−４  ＡＶＣ、ＦＲＥｘｔ（Ｆｉｄｅｌｉｔｙ  Ｒａｎｇｅ  Ｅｘｔｅｎｓｉｏｎ）や音声符号化方式にも適用できることはいうまでもない。
【符号の説明】
【０２５４】
１０  復号装置
２０，２１  ＣＰＵ
２２  ＲＡＭ
２３  ＲＯＭ
３０  復号処理部
３１  メイン処理部
３２ａ，３２ｂ  ワーカー処理部
３３ａ，３３ｂ  スライスデコーダ
３４  キュー
３５  スライスバッファ
３６  ビデオメモリ
３７  スライスコンテキスト
７３  編集部
１００  編集装置
【図１】
0005698156.tif 000016
【図２】
0005698156.tif 000017
【図３】
0005698156.tif 000018
【図４】
0005698156.tif 000019
【図５Ａ】
0005698156.tif 000020
【図５Ｂ】
0005698156.tif 000021
【図６】
0005698156.tif 000022
【図７】
0005698156.tif 000023
【図８】
0005698156.tif 000024
【図９】
0005698156.tif 000025
【図１０】
0005698156.tif 000026
【図１１】
0005698156.tif 000027
【図１２】
0005698156.tif 000028
【図１３】
0005698156.tif 000029
【図１４】
0005698156.tif 000030
【図１５】
0005698156.tif 000031
【図１６】
0005698156.tif 000032
【図１７】
0005698156.tif 000033
【図１８】
0005698156.tif 000034
【図１９】
0005698156.tif 000035
【図２０】
0005698156.tif 000036
【図２１】
0005698156.tif 000037
【図２２】
0005698156.tif 000038
【図２３】
0005698156.tif 000039
【図２４】
0005698156.tif 000040
【図２５】
0005698156.tif 000041
【図２６】
0005698156.tif 000042
【図２７】
0005698156.tif 000043