(57)【特許請求の範囲】
【請求項１】
階層的な動き予測を使用することで、画像データストリームを生成する方法であって、
ａ）現在の画像のそれぞれのソースマクロブロックについて、参照画像の低解像度のバージョンにおけるソースマクロブロックの予備の整合により、前記参照画像の低解像度のバージョンにおける予備の動きベクトルを決定する段階と、
ｂ）前記予備の動きベクトルに基づいて、前記参照画像の低解像度のバージョンよりも高い解像度を有する前記参照画像の高解像度のバージョンにおける対応する探索領域であって、ソースマクロブロックのサイズよりも大きいサイズを有する対応する探索領域を、前記現在の画像のソースマクロブロックに割り当て、前記参照画像の高解像度のバージョンを幾つかのセグメントに分割する段階と、それぞれのセグメントは、前記参照画像の高解像度のバージョンのマクロブロックの一部を含み、
ｃ）それぞれのソースマクロブロックについて、前記参照画像の高解像度のバージョンにおける探索領域における最良の整合を決定し、対応する動きベクトル及び対応する残差値のブロックを決定する段階と、前記ソースマクロブロックの前記最良の整合の決定の処理順序は、ソースマクロブロックの最良の整合の位置の探索が、前記幾つかのセグメントのうちの最初のセグメントに属する関連する探索領域のマクロブロックにおいて開始し、前記参照画像の高解像度のバージョンにおいてセグメント毎に継続する順序であり、
ｄ）それぞれのソースマクロブロックの前記最良の整合に従って、データストリームにおける前記現在の画像の前記ソースマクロブロックの前記対応する残差値のブロックと前記対応する動きベクトルを符号化する段階と、
ｅ）前記段階ａ）〜ｄ）を後続の画像について繰り返す段階と、
を含むことを特徴とする方法。
【請求項２】
オリジナルの参照画像をダウンサンプリングするか、又は、前記オリジナルの参照画像の画素をマージすることによって、前記参照画像の低解像度のバージョンを生成する段階を更に含む、
請求項１記載の方法。
【請求項３】
前記段階（ｃ）における処理順序は、前記探索領域の交点に依存する、
請求項１又は２記載の方法。
【請求項４】
前記参照画像の高解像度のバージョンは、マクロブロック毎にアクセス可能な格納装置に格納され、任意の探索領域を再構成することは、前記格納装置からマクロブロックのセットを読み出すことを必要とし、
第一のソースマクロブロックの探索領域を読み出すために必要とされる前記参照画像の高解像度のバージョンのマクロブロックの第一のセットは、第二のソースマクロブロックの探索領域を読み出すために必要とされる前記参照画像の高解像度の参照画像のマクロブロックの第二のセットと共通する最も多い数のマクロブロックを有し、
第三のソースマクロブロックの残差値は、前記第三のソースマクロブロックの最良の整合が前記マクロブロックから共通して読み出し可能である場合に、前記第一のソースマクロブロックの最良の整合の残差値と前記第二のソースマクロブロックの残差値との間で画像データストリームで符号化される、
請求項１記載の方法。
【請求項５】
前記ソースマクロブロックの位置に関する情報、及び／又は前記最良の整合の位置に関する情報は、前記画像データストリームに含まれる、
請求項１乃至４の何れか記載の方法。
【請求項６】
階層的な動き予測を使用することで、画像データストリームを生成する装置であって、
現在の画像のそれぞれのソースマクロブロックについて、参照画像の低解像度のバージョンにおけるソースマクロブロックの予備の整合により、前記参照画像の低解像度のバージョンにおける予備の動きベクトルを決定する手段と、
前記予備の動きベクトルに基づいて、前記参照画像の低解像度のバージョンよりも高い解像度を有する前記参照画像の高解像度のバージョンにおける対応する探索領域であって、ソースマクロブロックのサイズよりも大きいサイズを有する対応する探索領域を、前記現在の画像のソースマクロブロックに割り当て、前記参照画像の高解像度のバージョンを幾つかのセグメントに分割する手段と、それぞれのセグメントは、前記参照画像の高解像度のバージョンのマクロブロックの一部を含み、
それぞれのソースマクロブロックについて、前記参照画像の高解像度のバージョンにおける探索領域における最良の整合を決定し、対応する動きベクトル及び対応する残差値のブロックを決定する手段と、前記ソースマクロブロックの前記最良の整合の決定の処理順序は、ソースマクロブロックの最良の整合の位置の探索が、前記幾つかのセグメントのうちの最初のセグメントに属する関連する探索領域のマクロブロックにおいて開始し、前記参照画像の高解像度のバージョンにおいてセグメント毎に継続する順序であり、
それぞれのソースマクロブロックの前記最良の整合に従って、データストリームにおける前記現在の画像の前記ソースマクロブロックの前記対応する残差値のブロックと前記対応する動きベクトルを符号化し、前記決定する手段における処理を繰り返す手段と、
を備えることを特徴とする装置。
【請求項７】
請求項１記載の方法により生成された画像データストリームから現在の画像を再構成する方法であって、前記現在の画像は、前に符号化された参照画像を使用して符号化されており、
当該方法は、
前記画像データストリームからの動きベクトル及び残差値を復号化するステップと、前記動きベクトル及び前記残差値は、ソースマクロブロックに関連しており、
前記動きベクトルを使用して前記参照画像の参照マクロブロックを読み出し、前記残差値と前記参照マクロブロックとを使用することで前記現在の画像のソースマクロブロックを再構成するステップとを含み、前記処理順序は、前記動きベクトルが示す前記参照画像のセグメントに依存する、
ことを特徴とする方法。
【請求項８】
請求項１記載の方法により生成された画像データストリームから現在の画像を再構成する装置であって、前記現在の画像は、前に符号化された参照画像を使用して符号化されており、
当該装置は、
前記画像データストリームからの動きベクトル及び残差値を復号化する手段と、前記動きベクトル及び前記残差値は、ソースマクロブロックに関連しており、
前記動きベクトルを使用して前記参照画像の参照マクロブロックを読み出し、前記残差値と前記参照マクロブロックとを使用することで前記現在の画像のソースマクロブロックを再構成する手段とを備え、前記処理順序は、前記動きベクトルが示す前記参照画像のセグメントに依存する、
ことを特徴とする装置。
【請求項９】
コンピュータに、請求項１乃至５の何れか記載の方法を実行させる命令を含むコンピュータプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１０】
コンピュータに、請求項７記載の方法を実行させる命令を含むコンピュータプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データストリームを生成することに関する。本発明は、また、画像を画像データストリームから再構成することに関する。より詳しくは、本発明は、現在の画像を、参照画像の助けにより符号化することに関し、かつ、符号化された現在の画像を、復号することに関する。
【背景技術】
【０００２】
既知の符号化技法は、以前に符号化された参照画像に含まれる情報を利用する。このことは、次のようにして行われる。即ち、現在の画像のソースマクロブロックの各々について、参照画像において最良に合致する参照マクロブロックを探す。このことにより、参照マクロブロックと、ソースマクロブロックの間の残差が、最小になるようにする。次に、ソースマクロブロックを符号化する。この際に、残差の助けと、動きベクトルの助けを借りる。動きベクトルは、ソースマクロブロックと、最良に合致した参照マクロブロックの間の、空間的な関係を示す。最良に合致する参照マクロブロックを探す処理を、動き推定ともいう。
【０００３】
最良に合致する参照マクロブロックが、参照画像のどこに潜んでいるかは、判らない。従って、最良に合致する参照マクロブロックを探すことは、計算量が嵩む作業である。
【０００４】
この計算量を減らす１つの方法が、階層的な動き推定である。階層的な動き推定は、次の考えに基づく。即ち、第１の工程では、ソース画像と参照画像を縮小する。この縮小を、画素をマージすること、又は、ダウンサンプリングすることによって行う。次の工程では、縮小した画像について、完全な動き推定を行う。縮小した画像は、ごく少数のマクロブロックのみを含む。従って、次のことを行うには、それほど計算量はかからない。即ち、縮小したソース画像のソースマクロブロックの各々を、縮小した参照画像の参照マクロブロックの全てと突き合わせる計算をする。また、その計算結果により、最良に合致するブロックを選ぶ。更に、その最良の合致に対応する予備的な動きベクトルを求める。
【０００５】
縮小したソース画像のソースブロックの全ての、予備的な動きベクトルを使って、本来の解像度の画像における動きベクトルを予測する。本来の解像度の参照画像の、最良に合致する参照マクロブロックを、次に探す。この際に探す範囲は小さい。探索範囲は、予備的な動きベクトルの助けによって、狭められているからである。従って、本来の解像度の画像についての動きベクトルを求めるための計算量を、顕著に減らせる。
【０００６】
この方法を更に改良するために、複数の予備的な動きベクトルを求めてもよい。複数の予備的な動きベクトルは、空間的に又は時間的に隣接するマクロブロックの動きベクトルに基づく。
【０００７】
この方法を繰り返してもよい。即ち、縮小した画像を、更に縮小してもよい。第１段階の予備的な動きベクトルを、更に縮小した画像における完全探索の結果によって定めてもよい。縮小した画像における第２段階の予備的な動きベクトルを求める範囲を、第１段階の予備的な動きベクトルの助けによって定めた探索範囲に限定してもよい。次に、第２段階の予備的な動きベクトルを使って、本来の解像度の画像における動きベクトルを予測する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
階層的な動き推定は、高速ではある。しかし、階層的な動き推定は、広い帯域を必要とする。帯域がより広くなってしまうのは、参照画像を収めている、基礎にある格納媒体が、マクロブロックに整列している格納器の編成をしている場合である。
【０００９】
マクロブロックに整列している格納器の編成には、次の利点がある。即ち、通常の位置にある参照マクロブロックへのアクセスを、直接行えるので、高速である。この利点には、次の欠点が付随する。即ち、通常の位置でない位置にあるマクロブロックを、直接にアクセスできない。通常の位置にないマクロブロックを再構成するためには、次のことを行う必要がある。即ち、その通常の位置にないマクロブロックに交わる、通常の位置にあるマクロブロックを、最高４つまで取得し、かつ、取得した通常の位置にあるマクロブロックの部分から、通常の位置にないマクロブロックを合成する。
【００１０】
従って、画像ストリームを生成する方法を提示することが望ましい。この方法は、高速であり、かつ、必要なのは、より狭い帯域である。
【課題を解決するための手段】
【００１１】
従って、本発明は、画像データストリームを生成するための方法及び装置を提案する。この方法は、請求項１の特徴を含む。また、この装置は、請求項７の特徴を含む。本発明は、画像データストリームから、現在の画像を再構成するための方法及び装置を、更に提案する。この再構成するための方法は、請求項９の特徴を含む。また、この再構成するための装置は、請求項１０の特徴を含む。本発明は、請求項８の特徴を含む画像データストリームを、また更に提案する。本発明は、請求項１１による格納媒体を、また更に提案する。この格納媒体は、前述の提案の画像データストリームを収める。
【図面の簡単な説明】
【００１２】
【図１】縮小した画像をピラミッド状に重ねた例の図を示す。
【図２】選んだ参照マクロブロックの位置の例を、格納器から直接に取得できる参照マクロブロックとの関連で示す。格納器は、マクロブロックに整列している格納器の編成を持つ。
【図３】ソースマクロブロックの集合及びいくつかの参照マクロブロックを例として示す。また、予測器試行命令の単一のリストを例として示す。
【図４】ソースマクロブロックの集合及びいくつかの参照マクロブロックを例として示す。また、予測器試行命令のリストの集合を例として示す。
【図５】重なる断片の概念を例として示す。
【図６】予測器試行命令の再順序付けの実施例の流れ図を示す。
【発明を実施するための形態】
【００１３】
画像データストリームを生成するための方法は、次の工程を含む：
（ａ）参照画像における探索領域を、現在の画像のソースマクロブロックに割り当てる工程；
（ｂ）探索領域における最良の合致及び対応する残差を決定する工程；及び
（ｃ）決定した残差をデータストリーム中に符号化する工程。
【００１４】
この方法の更なる特徴は、次の事実に関する。即ち、工程（ｂ）及び工程（ｃ）のうちの、少なくとも１つの工程において、マクロブロックを処理する順は、参照画像における探索領域の位置に依存する。
【００１５】
最良の合致を決定する工程における処理の順を変えることにより、２つの異なるソースマクロブロックに連続して割り当てられた探索領域において、最良の合致の探索を実行できる。従って、２つの探索マクロブロックに割り当てられた探索領域を読み込む必要があるのは、ただ一度だけである。
【００１６】
符号化の最中に処理の順を変えることによって、復号器は、参照マクロブロックの交わる部分を取得できる。この取得は、ただ一度だけであり、いかなる再順序付けも必要としない。従って、最良の合致を、より効率的に決定できる。及び／又は、復号器側の処理量を減らせる。これは、符号化の順のおかげである。
【００１７】
ある実施形態では、この方法は、低解像度の画像を生成する工程を更に含む。この工程は、参照画像をダウンサンプリングすること、又は、参照画像の画素をマージすることによる。ここで、工程（ａ）は、次の工程を含む：
低解像度の画像におけるソースマクロブロックの予備的な合致の助けによって、予備的な動きベクトルを決定する工程；及び
予備的な動きベクトルの助けによって、探索領域を決定する工程。
【００１８】
このことは、探索領域を決定する、効率的な方法である。
【００１９】
更なる実施形態では、工程（ｂ）における処理の順は、探索領域の交わりに依存する。
【００２０】
また更なる実施形態では、参照画像を、第１の断片と、少なくとも第２の断片とに、断片化する。ここで、第１の断片に含まれる、探索領域及び／又は最良の合致を、持つソースマクロブロックは、少なくとも第２の断片に含まれる、探索領域及び／又は最良の合致を、持つソースマクロブロックよりも先に、工程（ｂ）及び／又は工程（ｃ）において、処理される。
【００２１】
また更なる実施形態では、第１のソースマクロブロックは、第２のソースマクロブロックの探索領域との、最も大きな交わりを持つ探索領域を持つ。また、第３のソースマクロブロックの最良の合致は、その第３のソースマクロブロックの探索領域が、その最も大きな交わりに含まれる場合には、第１のソースマクロブロックの最良の合致を決定する工程と、第２のソースマクロブロックの最良の合致を決定する工程との間で決定される。互いに交わる探索領域の後続の処理により、その交わりを２度取得することを避け、従って、処理を加速する。
【００２２】
また更なる実施形態では、参照画像は、マクロブロックについてアクセス可能な格納装置に格納される。任意の探索領域を再構成することは、その格納装置からマクロブロックの集合を取得することを含む。第４のソースマクロブロックの探索領域を再構成するために要求されるマクロブロックの第１の集合は、第５のソースマクロブロックの探索領域を再構成するために要求されるマクロブロックの第２の集合と共通する最も多くの数のマクロブロックを持つ。第６のソースマクロブロックの最良の合致は、その第６のソースマクロブロックの最良の合致を、共通のマクロブロックから再構成できる場合には、第４のソースマクロブロックの最良の合致を決定する工程と、第５のソースマクロブロックの最良の合致を決定する工程との間で決定される。
【００２３】
別の実施形態では、第７のソースマクロブロックの最良の合致は、第８のソースマクロブロックの最良の合致と最も大きな交わりを持つ。第９のソースマクロブロックの残差は、その第９のソースマクロブロックの最良の合致が、その最も大きな交わりに含まれる場合には、第７のソースマクロブロックの残差を符号化する工程と、第８のソースマクロブロックの残差を符号化する工程との間で符号化される。
【００２４】
また別の実施形態では、参照画像は、マクロブロックについてアクセス可能な格納装置に格納される。任意のマクロブロックを再構成することは、その格納装置から、上限４個までのマクロブロックの更なる集合を取得することを含む。第１０のソースマクロブロックの最良の合致を再構成するために要求される第１の更なる集合は、第１１のソースマクロブロックの最良の合致を再構成するために要求される第２の更なる集合と共通する大部分のマクロブロックを持つ。第１２のソースマクロブロックの残差は、その第１２のソースマクロブロックの最良の合致が、共通のマクロブロックから再構成可能な場合には、第１０のソースマクロブロックの残差を符号化する工程と、第１１のソースマクロブロックの残差を符号化する工程との間で決定される。
【００２５】
更にまた別の実施形態では、ソースマクロブロックの位置の情報、及び／又は、最良の合致の位置の情報は、残差に共に符号化される。
【実施例】
【００２６】
本発明の実施例を図面に示す。本発明の実施例を次に、より細かく説明する。
【００２７】
図１を参照する。階層的な動き推定を初めに説明する。
【００２８】
第１の工程では、参照画像と、縮小したソース画像を、ピラミッド状に積み重ねる。この例を図１に示す。例えば、縮小率として２を使う。すると、結果となる画像のピラミッドは、本来の解像度の段階０から、最も低い解像度の段階ｎまでの段階となる。図に示す例では、段階０は７２０画素ｘ５７６画素の解像度である。また、ｎは４である。
【００２９】
段階０（本来の解像度）：７２０画素ｘ５７６画素。
【００３０】
段階１：３６０画素ｘ２８８画素。
【００３１】
段階２：１８０画素ｘ１４４画素。
【００３２】
段階３：９０画素ｘ７２画素。
【００３３】
段階４：４５画素ｘ３６画素。
【００３４】
次の工程では、ソースピラミッドの最も高い段階である段階４について、動き推定を行う。この段階４は、ごく少数のマクロブロックのみを含む。従って、次のことを行っても、それほど計算量は多くならない。即ち、各ソースブロックの合致を全ての参照ブロックに対して計算し、全ての合致の中から最良の合致を決定し、かつ、最良の合致に対応する動きベクトルを決定する。つまり、探索領域として、参照ピラミッドの最も高い段階の全体を使う。
【００３５】
最も高い段階ｎからの、結果の動きベクトルを使って、段階ｎ−１についての動きベクトルを予測する。すると、段階ｎ−１についての動きベクトルの探索を、最も高い段階ｎからの動きベクトルが示す位置を囲む探索領域に限定できる。次のことも可能である。即ち、段階ｎ−１についての動きベクトルを予測する場合に、空間的に隣接するマクロブロックからの、最も高い段階の動きベクトルを更に考慮に入れる。加えて又は代わりに、直前の画像のマクロブロックについて決定された動きベクトルを考慮に入れてもよい。最も高い段階及び／又は直前の画像から予測された動きベクトルの中で、最も低い歪みのものを選ぶ。又は、より広い探索範囲を形成する。このより広い探索範囲は、動きベクトルの予測が示す一部又は全部の位置を含む。
【００３６】
この方法を何回か繰り返し、本来の解像度である段階０に至るまで行う。
【００３７】
１つより多い動きベクトルの予測を使う場合は、少なくとも２つの処理工程が、各ソースマクロブロックについて、各段階で、必要となる。これにより、最良に合致する動きベクトルを見つける。この２つの処理工程を次に示す。
【００３８】
第１の工程で、予測器試行命令の集合を計算する。予測器試行命令の各々は、１つの動きベクトルの予測に対応する。予測器試行命令を実行する場合に、ソースマクロブロックについての歪み関数を計算する。この計算を、参照画像のただ１つの探索マクロブロックについて行う。この探索マクロブロックを、対応する動きベクトルの予測が決定する。さて、予測器試行命令の集合を全て実行すると、最良に合致する動きベクトルの予測が決定される。最良に合致する動きベクトルの予測により、歪みが最小になる。
【００３９】
第２の工程では、最良に合致する動きベクトルの予測の周りで、完全探索命令の集合を計算する。完全探索命令の各々は、最良に合致する動きベクトルの予測を囲む小さな探索領域の内部の、１つの探索マクロブロックの位置に対応する。
【００４０】
さて、完全探索命令の集合を全て実行すると、最良に合致する動きベクトルが決定される。最良に合致する動きベクトルにより、現在の段階について、歪みが最小になる。
【００４１】
この算法は、参照する記憶装置に、極めて大きな帯域を要求する。記憶装置に参照ピラミッドを格納する。平均して８個の予測器試行命令が、本来の解像度である段階０におけるソースマクロブロックの各々について、必要になると仮定する。１９２０画素ｘ１０８０画素でフレームレートが２５ＨｚのＨＤ画像については、この仮定によると、最小の帯域として、１９８０ｘ１０８０ｘ８ｘ２５≒４２８Ｍバイト／秒が、参照データを読むために必要となる。これは、理想的な場合であることに注意。即ち、この場合では、参照画像における位置及び記憶装置における位置からは独立に、厳密に、その参照探索マクロブロックにアクセスできるという、理想的な仮定をしている。しかし、現実的には、参照データがマクロブロックに整列している格納器の編成であれば、任意の位置にある参照マクロブロックを取得することは、遥かにより広い帯域を要求することに繋がる。マクロブロックに整列している格納器の編成手段により、整列した参照マクロブロックを、全体として高速にアクセスできる。即ち、記憶装置に、アドレスが１つずつ増える連続的なバーストアクセスを行える。しかし、この場合、整列していない参照探索マクロブロックにアクセスするには手間がかかる。整列していない参照探索マクロブロックは、画像のどこにあってもよい。整列していない参照探索マクロブロックは、マクロブロックに整列している構造にはうまく収まらない。
【００４２】
参照データについて、このようなマクロブロックに整列している編成を仮定する。図２は、次のことを示す。即ち、選んだマクロブロックであるＳＲＭを取得するためには、おそらく、４つの隣接して整列している参照マクロブロックであるＡＲＭ１、ＡＲＭ２、ＡＲＭ３、及びＡＲＭ４を、記憶装置から読み出す必要がある。この読み出しにより、整列していない参照探索マクロブロックであるＳＲＭを構築する。このことにより、記憶装置に要求される最大の帯域は、１つの参照フレームについて、１．７Ｇバイト／秒となる。複数の参照フレームがこの探索に含まれる場合には、帯域の要求もそれに応じて増えることになる。即ち、例えば、３つの参照フレームを使う場合には、５．１Ｇバイト／秒の帯域が、単に階層的な動き推定の予測器試行命令の集合を実行するためだけに、必要となる。
【００４３】
このような帯域を、外部記憶装置で実現することは、極めて困難である。従って、階層的な動き推定器は、大量のオンチップ記憶装置を使って作られる。オンチップ記憶装置は、必要となる帯域を提供する。しかし、参照フレームの全体を格納する必要があるため、このオンチップ記憶装置のダイの大きさが膨れ上がってしまう。
【００４４】
従来の技術では、予測器試行命令を、その命令が属するソースマクロブロックの順で実行する。即ち、最初のソースマクロブロックであるＳＭＢ＃０についての全ての予測器試行命令であるＰＴＣ（ＳＭＢ＃０，ＳＲＭ＃＊）を、最初に全て計算する。次に、その次のソースマクロブロックであるＳＭＢ＃１についての全ての予測器試行命令であるＰＴＣ（ＳＭＢ＃１，ＳＲＭ＃＊）を全て計算する。以下同様。これを図３に示す。
【００４５】
本発明は、予測器試行命令の順を入れ替えることを提案する。この入れ替えは、予測器試行命令が指している参照探索マクロブロックによる。
【００４６】
このことを行うために、参照画像をｋ個の断片に分ける。図４に、ｋ＝４の例を示す。次に、予測器試行命令ＰＴＣ（）を、ｋ＝４個のリストであるＬ１、Ｌ２、Ｌ３、及びＬ４に再順序付けする。この再順序付けを次のように行う。即ち、特定の断片であるＳＥＧ１、ＳＥＧ２、ＳＥＧ３、及びＳＥＧ４に位置する参照探索マクロブロックであるＳＲＭを指す予測器試行命令ＰＴＣ（）を、それぞれの断片に対応する１つのリストに格納する。予測器試行命令であるＰＴＣ（ＳＭＢ＃Ｍ，ＳＲＭ＃Ｌ）が、断片ＳＥＧ１、ＳＥＧ２、ＳＥＧ３、及びＳＥＧ４のうちの２つ以上に位置する参照探索マクロブロックＳＲＭを指すことを避けるために、断片が重なることが必要になる。この重なりの例を図５に示す。図５の左側の例の、垂直方向に重なる断片が無い場合には、断片ＳＥＧ１の境界に位置する参照探索マクロブロックは、垂直方向に隣接する断片ＳＥＧ２にも部分的に位置してもよい。図５の右側に、垂直方向に２つの断片が重なる例を示す。この重なりの垂直方向の大きさは、参照マクロブロックの垂直方向の大きさと等しい。この重なりがあることによって、各参照探索マクロブロックは、断片ＳＥＧ１’又はＳＥＧ２’のうちの少なくとも片方の、完全な内側に位置することになる。
【００４７】
予測器試行命令のための並び替えの算法の実施例の流れ図を、図６に示す。図６に示す通り、予測器試行命令の並び替えは、極めて単純で高速な処理である。
【００４８】
工程「始め」では、ｋ（例えばｋ＝４）個のリストであるＬ１、Ｌ２、Ｌ３、及びＬ４の集合を初期化する。ここで、ｋは、重なる断片であるＳＥＧ１’、ＳＥＧ２’等の数である。ｋ個の重なる断片に、画像を分ける。次の工程「生成／読み込み」では、予測器試行命令であるＰＴＣ（ＳＭＢ＃Ｍ，ＳＲＭ＃Ｌ）を生成する、又は、既に生成されている、予測器試行命令であるＰＴＣ（ＳＭＢ＃Ｍ，ＳＲＭ＃Ｌ）を読み込む。ＰＴＣ（ＳＭＢ＃Ｍ，ＳＲＭ＃Ｌ）は、Ｍ番目のソースマクロブロックであるＳＭＢ＃Ｍを、Ｌ番目の選んだ参照マクロブロックＳＲＭ＃Ｌと比べるための予測器試行命令である。次に、工程「初期化」では、計数変数であるＮを、値１に初期化し、位置変数であるＰを、選んだ参照マクロブロックであるＳＲＭ＃Ｌの位置に初期化する。次に、工程「Ｐ＝Ｐ−Ｓ」で、繰り返しに入る。ＰからＳを引く。Ｓは、断片の幅の値である。工程「Ｐ＜０？」の判断によって、直前の工程でＳを引いた結果、Ｐが０より小さければ、繰り返しを抜け出す。そうでない場合は、工程「Ｎ＝Ｎ＋１」でＮを１増やし、次に、ＰからＳを引くことを繰り返す。この繰り返しを抜け出したら、工程「加える」で、予測器試行命令であるＰＴＣ（ＳＭＢ＃Ｍ，ＳＲＭ＃Ｌ）を、Ｎ番目のリストであるＬＮに加える。次に、工程「終わったか？」で、予測器試行命令であるＰＴＣ（ＳＭＢ＃Ｍ，ＳＲＭ＃Ｌ）を生成できる又は読み込める、更なる比較が残っているかを確認する。残っていれば、まだ終わっていないので、工程「生成／読み込み」に戻る。残っていなければ、終わったことになるので、工程「終り」で並び替えは終わる。
【００４９】
並び替えの処理が終わると、予測器試行命令であるＰＴＣ（ＳＭＢ＃Ｍ，ＳＲＭ＃Ｌ）の、ｋ個のリストができている。各リストを処理するためには、参照フレームの断片であるＳＥＧ１’、ＳＥＧ２’等のうちの、ただ１つの断片のみを、局所記憶装置に格納する必要がある。なぜならば、その前の並び替えの工程で、このリストの中の全ての予測器試行命令ＰＴＣ（）は、処理の対象として、参照画像の同じ１つの断片（ＳＥＧ１’、ＳＥＧ２’等のうちの、ただ１つの断片）のみを必要とすることが確実になっているからである。このことにより、オンチップで必要な記憶容量を、１／ｋに減らせる。
【００５０】
次の点に注意。即ち、参照データ断片ｋ＋１を、参照データ断片ｋを処理している最中に、局所記憶装置に読み込める。従って、リストｋ＋１の計算を、リストｋの計算が終わった直後に始められる。このことにより、オンチップで必要な記憶容量が倍になる。しかし、断片の数を増やせば、１つの断片あたりの容量が減るので、このことを補償できる。
【００５１】
参照データを読み込むために必要な記憶装置の帯域を減らすのと全く同じ考え方を、階層的な動き推定の第２工程にも適用できる。第２工程とは、最良に合致した予測器試行の周囲の、小さな完全探索である。完全探索命令の列を、その命令が指す参照画像の断片について並び替えることにより、予測器試行命令の並び替えの場合と同じくらい、オンチップの記憶容量を減らせる。この方法のためには、完全探索命令の列を、命令のｋ個のリストに並び替える必要がある。各リストは、参照データ断片ＳＥＧ１、ＳＥＧ２、ＳＥＧ３、及びＳＥＧ４（ｋ＝４の場合）のうちの、同じ１つの断片を指す完全探索命令のみを含む。すると、オンチップで必要な記憶容量を、１／ｋに減らせる。更に、断片の大きさを、予測器試行命令の処理の場合と同じくなるように選べば、同じ局所記憶装置を使ってもよい。
【００５２】
最後に、次の点に注意。即ち、前述の方法により、階層的な動き推定のための効率的な並列処理を行える。予測器試行命令ＰＴＣ（ＳＭＢ＃Ｍ，ＳＲＭ＃Ｌ）又は完全探索命令の、複数のリストＬ１、Ｌ２、Ｌ３、及びＬ４を、対応する参照データ断片ＳＥＧ１、ＳＥＧ２、ＳＥＧ３、及びＳＥＧ４と共に、複数の処理要素に分散してもよい。複数の処理要素とは、例えば、Ｃｅｌｌ  Ｂｒｏａｄｂａｎｄ  Ｅｎｇｉｎｅ（商標）にある、複数のＳｙｎｅｒｇｉｓｔｉｃ  Ｐｒｏｃｅｓｓｏｒ  Ｅｌｅｍｅｎｔである。すると、階層的な動き推定の算法の、独立した並列処理を、複数の処理要素を最大に活用して行える。
【００５３】
普通は、ソースマクロブロックの差分は、決定した動きベクトルと共に、ソース画像における位置に従って、画像データストリームに符号化される。既知の手法では、画像データストリームにおいて隣接する２つの差分は、現在の画像における２つの隣接するソースマクロブロックを参照する。動きベクトルは、予測できない仕方で、参照画像のあらゆる箇所を指し示してもよい。従って、動き補償のために参照マクロブロックへの記憶アクセスを行うと、動き推定について前述したのと同じ帯域の問題が生じる。
【００５４】
従って、復号器は、まず、現在の画像に関する、全ての差分と動きベクトルを受け取ってもよい。次に、復号器は、差分と動きベクトルを、複数のリストに並べ替えてもよい。即ち、各リストにある差分と動きベクトルを全て、参照画像の同じ断片（例えばＳＥＧ１、ＳＥＧ２、ＳＥＧ３、及びＳＥＧ４のうちの１つ）に関するようにする。すると、１つのリストにある差分と動きベクトルに関してマクロブロックを再構成する際には、参照画像のただ１つの断片のみ（例えばＳＥＧ１、ＳＥＧ２、ＳＥＧ３、及びＳＥＧ４のうちのただ１つのみ）が、局所記憶装置又はキャッシュ記憶装置に存在する必要がある。参照画像の全体は不要である。従って、局所記憶装置又はキャッシュ記憶装置は小さくてもよい。
【００５５】
復号器における再順序付けは、符号化器における再順序付けと同じである。従って、復号器における再順序付けが冗長になりうるのは、差分と動きベクトルを、符号化器で再順序付けしたまま送る場合である。即ち、たとえ復号器側で動き推定のために何の再順序付けも行わないとしても、符号化器で再順序付けしてから送れば、復号器側で再順序付けしたのと同じことになる。従って符号化器側の再順序付けは有用であってもよい。
【００５６】
従って、本発明は、次のことを提案する。即ち、同じ１つの断片（例えばＳＥＧ１、ＳＥＧ２、ＳＥＧ３、及びＳＥＧ４のうちの１つ）に関する、差分と、その差分に対応する動きベクトルとを、画像データストリームの個別の連続する区画に符号化する。次に、各部分区画を復号する際には、参照画像のただ１つの断片のみ（例えばＳＥＧ１、ＳＥＧ２、ＳＥＧ３、及びＳＥＧ４のうちのただ１つのみ）が、局所記憶装置又はキャッシュ記憶装置に存在する必要がある。参照画像の全体は不要である。従って、局所記憶装置又はキャッシュ記憶装置は小さくてもよい。符号化器の場合と同様に、オンチップに必要な記憶容量及び外部記憶装置に必要な帯域を、処理の順を再順序付けすることによって、著しく減らせる。
【００５７】
再順序付けすると、ある差分が属するソースマクロブロックの位置は、画像データストリームにおけるその差分の位置からは、もう導き出せない。従って、ソース画像におけるソースマクロブロックの位置に関する情報を、画像データストリームに含ませる。この情報を、前に参照した参照マクロブロックに対する、現在参照している参照マクロブロックの相対位置から作ってもよい。すると、現在のソースマクロブロックの位置を、動きベクトルの助けによって導き出せる。このことにより、位置情報を送るために必要な追加の帯域を最小化する。
【００５８】
従って、符号化器は、主に、本提案の方法で動き推定をするためにマクロブロックの処理を再順序付けする必要がある。このことにより、後続して処理されるマクロブロックの動きベクトルが、同じ参照領域を指すことを確実にする。差分を厳密にこの順で送れば、復号器での再順序付けの工程は不要である。本提案は、符号化器及び復号器における、オンチップで必要な記憶容量が少ないという利点及び必要な帯域が狭いという利点を、復号器における、動き補償のための処理時間が短いという利点に、組み合わせる。
【図１】
0005266096.tif 000002
【図２】
0005266096.tif 000003
【図３】
0005266096.tif 000004
【図４】
0005266096.tif 000005
【図５】
0005266096.tif 000006
【図６】
0005266096.tif 000007