(57)【要約】【課題】画像または画像シーケンスを効率よく圧縮できる装置を提供する。【解決手段】符号化器６１４は、ｋ番目の画像の木構造を生成し、その木構造を、バッファ６１６に記憶されたライブラリに追加し、その木構造をビットストリームに加える。符号化器６１４は、ｋ＋１番目の画像の木構造を生成する。この木構造は、ｋ番目の画像の木構造と同一である。符号化器６１４は、ｋ＋１番目の画像の木構造をビットストリームに加える代わりに、インデックス番号をビットストリームに加える。復号器６２４は、ビットストリームを受信し、ビットストリームからｋ番目の画像の木構造を読み出し、その木構造を、自身のバッファ６２６に記憶されたライブラリに追加する。後に、復号器６２４は、ｋ＋１番目の画像のインデックスを読み出し、そのインデックスを使用して、自身のバッファ６２６に記憶されたライブラリから木構造にアクセスする。
2005524319.tif 000002
【特許請求の範囲】
【請求項１】
画像の圧縮を実行する装置であって、
画像を領域に適応的に区画するエンコーダを有し、
少なくとも１つの領域に対して、パレット化およびフレーム間符号化の少なくとも１つを、選択的に実行する
装置。
【請求項２】
前記エンコーダは、類似の統計値を有するより小さな領域を、より大きな領域に、選択的にマージすることにより、前記領域を適応的に区画する
請求項１に記載の装置。
【請求項３】
前記エンコーダは、非類似の統計値を有する残存する領域を、単一のブロックにマージする
請求項２に記載の装置。
【請求項４】
前記エンコーダは、ツリー構造を使って、区画された画像を表現する
請求項１に記載の装置。
【請求項５】
前記ツリー構造またはその一部は、先に生成された少なくとも１つのツリー構造から記述される
請求項４に記載の装置。
【請求項６】
前記エンコーダは、
ツリー構造ライブラリをつくり、
このライブラリへのインデックスとして、前記ツリー構造またはその一部を記述する
請求項４に記載の装置。
【請求項７】
前記エンコーダは、先に生成された少なくとも１つのツリー構造の関数として、前記ツリー構造またはその一部を予測する
請求項４に記載の装置。
【請求項８】
前記ツリー構造は、２分木構造である
請求項４に記載の装置。
【請求項９】
前記エンコーダは、類似の統計値を有する一定のリーフを取り除き、次いで、類似の統計値を有する一定のノードを取り除く
請求項４に記載の装置。
【請求項１０】
前記エンコーダは、前記ツリー構造を、ビットストリームに書き込み、次いで、符号化された領域を、ビットストリームに書き込み、
前記領域は、前記ツリー構造ごとに符号化される
請求項４に記載の装置。
【請求項１１】
前記エンコーダは、次の統計値
（ａ）色のリスト、
（ｂ）圧縮性の尺度
を、領域それぞれに関係づける
請求項１に記載の装置。
【請求項１２】
前記画像は、画像シーケンスの一部であり、
前記エンコーダは、次のさらなる統計値
（ｃ）先行領域との色の差分のリスト、
（ｄ）先行領域との差分の圧縮性の尺度
を、領域それぞれに関係づける
請求項１１に記載の装置。
【請求項１３】
前記先行領域は、先の画像において、同じ空間的な位置で対応する領域である
請求項１２に記載の装置。
【請求項１４】
前記先行領域は、先の画像において、対応する動き補償領域である
請求項１２に記載の装置。
【請求項１５】
前記エンコーダは、前記先行領域を統合する
請求項１２に記載の装置。
【請求項１６】
前記エンコーダは、前記領域を分類し、
類似の分類を有する領域は、マージの候補である
請求項１に記載の装置。
【請求項１７】
差分領域が、現在の領域より十分に圧縮できる場合には、領域は、インター(Inter)として分類され、
現在の領域が、差分領域より十分に圧縮できる場合には、領域は、イントラ(Intra)として分類される
請求項１６に記載の装置。
【請求項１８】
現在の領域が、差分領域とほぼ同程度に圧縮できる場合には、領域は、ドンドケア(Don't_Care)として分類され、
ドントケアブロックは、インター、イントラおよび他のドントケアブロックとマージされうる
請求項１７に記載の装置。
【請求項１９】
前記領域が適応的に決定された後に、多数の符号化選択肢が、前記領域の少なくともいくつかに利用可能であり、
前記エンコーダは、前記多数の符号化選択肢を有する前記領域に対して、最終的な符号化を決定する
請求項１に記載の装置。
【請求項２０】
前記エンコーダは、一組の基準を用いて、前記領域を適応的に決定する
請求項１に記載の装置。
【請求項２１】
前記基準は、領域をマージするときに、非パレット化圧縮より、パレット化に優先権を与えることを含み、
パレット化は、少なくともいくつかの領域に対して実行され、
非パレット化圧縮は、他の領域に対して実行される
請求項２０に記載の装置。
【請求項２２】
前記領域は、表１にリストされた前記基準に従って、適応的に決定される
請求項２０に記載の装置。
【請求項２３】
パレット化は、前記画像の一定の領域に対して実行される
請求項１に記載の装置。
【請求項２４】
パレット化に用いられるパレットは、先に生成された少なくとも一つのパレットから記述される
請求項２３に記載の装置。
【請求項２５】
前記エンコーダは、
パレットライブラリをつくり、
このパレットライブラリへのインデックスとして、パレット化に用いられるパレットを記述する
請求項２３に記載の装置。
【請求項２６】
パレット化に用いられるパレットは、先に生成された少なくとも１つのパレットの関数として予測される
請求項２３に記載の装置。
【請求項２７】
前記エンコーダは、前記画像の一定の領域に対して、フレーム間符号化を実行し、
前記画像は、画像シーケンスの一部である
請求項１に記載の装置。
【請求項２８】
画像シーケンスの画像に対して圧縮を実行する装置であって、
前記画像を、領域に区画するプロセッサを有し、
類似の統計値を有するより小さい領域を、より大きい領域にマージし、
適切な場所でマージされた領域に対して、パレット化を実行し、
パレット化は、前記画像の領域に対して、選択的に実行される
装置。
【請求項２９】
コンピュータプログラムであって、
前記プログラムが実行されたときには、連続して画像を圧縮することを、プロセッサに実行させ、
前記画像の一定の領域に対して、パレット化およびフレーム間符号化の少なくとも１つを選択的に実行することを、プロセッサに実行させ、
前記領域は、適応的に決定される
コンピュータプログラム。
【請求項３０】
デジタル画像を、領域に、適応的に区画する第１の手段と、
前記領域の少なくとも１つに対して、パレット化およびフレーム間符号化の少なくとも１つを選択的に実行する第２の手段と
を有するシステム。
【請求項３１】
前記第２の手段により生成されたビットストリーム内のツリー構造および符号化された領域を読み出す第３の手段と、
前記ツリー構造ごとに前記領域をデコードする手段であって、前記領域の少なくともいくつかは、パレットから再構成される第４の手段と、
前記デコードされた領域から画像を再構成する第５の手段と
をさらに有する
請求項３０に記載のシステム。
【請求項３２】
ビットストリーム内のツリー構造および符号化された領域を読み出す手段と、
前記ツリー構造ごとに前記領域をデコードする手段であって、前記領域の少なくともいくつかは、パレットから再構成される手段と、
前記デコードされた領域から画像を再構成する手段と
を有するシステム。
【請求項３３】
信号をデコードする装置であって、
前記信号内のツリー構造および符号化された領域を読み出すデコーダを有し、
前記ツリー構造ごとに前記領域をデコードし、
前記領域の少なくともいくつかは、パレットから再構成され、
前記デコードされた領域から画像を再構成する
装置。
【請求項３４】
前記ツリー構造またはその一部は、先に生成された少なくとも１つのツリー構造から記述される
請求項３３に記載の装置。
【請求項３５】
前記デコーダは、
ツリー構造ライブラリをつくり、
このライブラリへのインデックスから、前記ツリー構造またはその一部にアクセスし、
前記インデックスは、前記信号内に供給される
請求項３３に記載の装置。
【請求項３６】
前記デコーダは、先に生成された少なくとも１つのツリー構造の関数として、ツリー構造またはその一部を予測する
請求項３３に記載の装置。
【請求項３７】
パレットの少なくとも１つは、先に生成された少なくとも１つのパレットから記述される
請求項３３に記載の装置。
【請求項３８】
前記デコーダは、
パレットライブラリをつくり、
このパレットライブラリへのインデックスから、前記パレットの少なくとも１つにアクセスし、
前記インデックスは、前記信号内に供給される
請求項３３に記載の装置。
【請求項３９】
前記デコーダは、先に生成された少なくとも１つのパレットの関数として、パレットの少なくとも１つを予測する
請求項３３に記載の装置。
【請求項４０】
コンピュータプログラムであって、
前記プログラムが実行されたときには、連続して画像を再構成することを、プロセッサに実行させ、
ビットストリームからツリー構造および符号化された領域を読み、
前記ツリー構造ごとに前記領域をデコードし、
前記領域の少なくともいくつかは、パレットから再構成され、
前記デコードされた領域から画像を再構成する
ことをプロセッサに実行させる
コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像および画像シーケンスを圧縮する装置に関する。
【背景技術】
【０００２】
［背景］
データ圧縮は、大きなデータファイルをコンピュータに記憶するコストを削減するために使用される。
また、データ圧縮は、コンピュータ間で大きなデータファイルを伝送する時間を削減するためにも使用される。
【０００３】
一定の技法は、一定の画像を圧縮するには優れているが、他の画像を圧縮するには優れていない。
一例として、パレット化は、少数の色だけしか有さない画像の可逆圧縮には、優れたビットレートを供給する。
しかしながら、多数の色を有する画像には、ビットレートがかなり悪くなる可能性がある。
場合によっては、パレット化は、パレットを記述するコストのために、ファイルサイズを増加させる可能性がある。
【０００４】
別の例として、ＪＰＥＧ−ＬＳ等の可逆圧縮技法は、画像ラインをスキャンし、局所的な画像統計値に従って、適応的に変化する。
しかしながら、画像統計値は、垂直方向の空間的局所性（vertical spatial locality）を限定的にしか利用しない。
加えて、ビットレートは、画像の一部が数個の非類似の色しか含まない場合には、十分には活用されない。
【特許文献１】欧州特許出願公開第０９８７６５６号
【特許文献２】米国特許第５９３０３９０号
【特許文献３】国際公開第９８／４０８４２号
【特許文献４】国際公開第０１／３１４９７号
【特許文献５】英国特許出願公開第２３２４２２０号
【特許文献６】英国特許出願公開第２２５１５２８号
【特許文献７】米国特許第５２８５２７５号
【特許文献８】国際公開第９２／１５１７３号
【発明の開示】
【発明が解決しようとする課題】
【０００５】
さらに、パレット化やＪＰＥＧ−ＬＳ等の圧縮技法は、単一の画像よりも効率的には、画像シーケンスを圧縮しない。
【課題を解決するための手段】
【０００６】
［詳細な説明］
例示の目的で図面に示すように、本発明は、画像圧縮を行う方法に具体化される。
圧縮は、単一の画像または画像シーケンスに対して行われうる。
一般に、画像は、パレット化およびフレーム間符号化の少なくとも一方を、画像の一定の領域に対して選択的に行うことによって圧縮される。
これらの領域は、適応的に決定される。
本方法は、画像区画化およびパレット化を使用することによって、従来の可逆圧縮技法の性能を改善する。
本方法は、画像シーケンスに適用されると、時間的局所性を利用することによって、従来の可逆圧縮技法の性能を改善する。
本方法は、スクリーンショットシーケンスおよび他の人工的な画像の圧縮に特に有効である。
【発明を実施するための最良の形態】
【０００７】
画像圧縮は、画像シーケンスとの関連で説明される。
シーケンスにおける画像は、１，…，ｋ，…，Ｎの番号が付けられる。
シーケンスにおける各画像は、ピクセルの配列を含む。
空間領域では、各ピクセルは、ｎビットワードによって表される。
ＲＧＢ色空間を表す一般的な２４ビットワードでは、８ビットが赤成分を表し、８ビットが緑成分を表し、８ビットが青成分を表す。
【０００８】
図１を参照する。
図１は、画像シーケンスにおけるｋ番目の画像の圧縮方法を示している。
ｋ番目の画像の区画が生成される（１１０）。
この区画は、ｋ番目の画像の交わらない領域を表す。
まず、画像は、「マイクロブロック」と呼ばれる領域に区画される。
マイクロブロックは、区画の最小の領域である。
マイクロブロックのサイズは、固定されてもよいし、比較的小さくてもよい。
マイクロブロックは、正方形（例えば、３２×３２ピクセル）でもよいし、長方形でもよい。
長方形のマイクロブロックは、例えば、幅対高さの比が４：１または８：１とすることができる。
ｋ番目の画像の区画は、木構造によって表されうる。
【０００９】
ｋ番目の画像の区画を表す木構造が生成される（１１２）。
この木構造は、リーフおよびノードを含む。
マイクロブロックは、木構造のリーフに対応する。
木構造の内部ノードは、その内部ノードをルートとする部分木のリーフを表すマイクロブロックの和集合（union）に対応する。
木構造は、使用されて、マイクロブロックを、ボトムアップで連続領域にグループ化できる。
２分木構造では、２つの兄弟ノードは、２つの領域に区画された、それらの共通の親ノードの区画に対応する。
この区画の方向は、木構造を降下すると共に、水平方向と垂直方向とを交互に繰り返す。
４分木構造では、４つの兄弟ノードが、双方の方向に区画された、それらの共通の親ノードの区画に対応する。
ほとんどの可逆圧縮技法は、実行および符号化に水平方向を好むので、垂直方向の空間的局所性を、非常に限定的にしか利用できない。
したがって、２分木構造は、より精細なスケーリング（scaling）を可能にするので、連続した区画については、２分木構造は、４分木構造よりも好まれる。
区画化された例示の画像２１０および対応する木構造２１４が、図２ａおよび図２ｂに示される（マイクロブロックは、参照符号２１２によって示され、リーフは、参照符号２１６によって示され、内部ノードは、参照符号２１８によって示される）。
【００１０】
各リーフの統計値が計算される（１１４）。
各リーフについて、「現」領域の統計値が計算される（まず、各領域がマイクロブロックに対応する）。
リーフの現領域は、ｋ番目の画像におけるそのリーフの対応する領域を指す。
各リーフについて、「差分」領域の統計値も、生成されうる。
差分領域は、現領域と、ｋ−１番目の画像の同じ空間位置における領域との間の差分を指す。
差分領域の統計値は、シーケンスの最初の画像の現領域については生成されないし、本方法が単一の画像に適用されている場合にも生成されない。
【００１１】
統計値は、（１）現領域の色のリスト、および、（２）差分領域の色の差分のリスト（すなわち、現領域と、ｋ−１番目の画像の同じ空間位置における対応する領域との間の色の差分のリスト）を含むことができる。
簡単な例として、リーフの統計値は、現領域の３色、および、１色の領域の差分を含むことができる。
それによって、現領域は、ｋ−１番目の画像の同じ空間位置における領域と同じ色を有する。
色の個数は、領域がパレット化されうるかどうかの指標を提供する。
【００１２】
各リーフの統計値は、（３）パレット化を伴わない現領域の圧縮性の尺度、および、（４）パレット化を伴わない差分領域の圧縮性の尺度、をさらに含むことができる。
圧縮性の尺度は、その領域の圧縮に最終的に使用される圧縮方法に関係付けられる必要はない。
経験的エントロピー（empirical entropy）は、簡易で単純な圧縮性の尺度として使用されうる。
現領域または差分領域の経験的エントロピーは、その領域内における各色平面の各ピクセル値の、統計に基づくエントロピーの総和として、計算されうる。
色平面の経験的エントロピーが合計されて、最終値が得られる。
以下の方程式が使用されて、色平面の現領域または差分領域の経験的エントロピーが計算されうる。
【００１３】
【数１】
2005524319.tif 000003
【００１４】
ここで、ａは、現領域または差分領域の値であり、ｚは、現領域または差分領域のピクセルの個数であり、ｎ（ａ）は、値ａの発生頻度である。
フレーム内予測誤差値のカウントが、ｎ（ａ）の代わりに使用されうる。
この場合、予測誤差は、領域の圧縮に最終的に使用される非パレット化圧縮方法における予測ステップに対応する。
【００１５】
リーフが、それらの統計値に従って分類される（１１６）。
例示の分類は、「イントラ（Intra）」、「インタ（Inter）」および「ドントケア（Don't_Care）」を含むことができる。
非パレット化圧縮に関して、現領域が差分領域よりも大幅に圧縮可能である（例えば、現領域のエントロピーが、差分領域のエントロピーよりも大幅に小さい）場合には、リーフは、イントラとして分類される。
イントラとして分類された領域は、先行フレームの情報を使用することなく圧縮される。
差分領域が現領域よりも大幅に圧縮可能である（例えば、現領域のエントロピーが、差分領域のエントロピーよりも大幅に高い）場合には、リーフは、インタとして分類される。
インタとして分類された領域は、先行画像の情報を使用して圧縮される。
インタおよびイントラの圧縮性がほぼ同じである場合には、リーフは、ドントケアとして分類される。
ドントケアと決定された結果、インタまたはイントラのいずれかとしての分類は、後に延期される。
【００１６】
木構造は、一組の切り取り判定基準に従うことを条件として、切り取られる（１１８）。
２分木構造は、後行順走査で巡回されうる。
リーフに対応する現領域が同様の圧縮性の統計値を有する場合、もしくは、リーフに対応する差分領域が同様の圧縮性の統計値を有する場合、または、マージされた領域の和集合の色の個数がパレット化を可能にするだけ十分に少ない場合、もしくは、ｋ番目の画像のマージされた領域とｋ−１番目の画像のマージされた領域との間の異なる色の個数がパレット化を可能にするたけ十分少ない場合には、そのリーフは切り取られる。
２つのリーフを切り取った結果、２つの領域は、マージされる。
切り取り後に残ったノードは、その後、リーフとして扱われ、その後、切り取られうる（部分木の２つのノードは、同様の統計値を有する場合に、切り取られる）。
【００１７】
最初の区画が切り取られた後、少なくとも１回の切り取りが、追加して実行される。
追加された各回の切り取りの期間中、ノードはリーフとして扱われ、それによって、一組の切り取り判定基準に従うことを条件として、同様の統計値を有するノードが切り取られる。
領域をそれ以上マージできなくなるまで、切り取りを行う回が、追加されて、実行される。
【００１８】
一組の切り取り判定基準は、どの特定の一組のルールにも限定されない。
表１の擬似コードは、切り取り判定基準を提供するが、これは、単なる一例にすぎない。
【００１９】
表１の擬似コードは、次のように要約されうる。
２つの領域は、表２（表２は、例示の分類を有する領域をマージするための判断を示している）のように同じ分類を有する場合に、マージされる。
一方、可能ならば、パレット化を維持するために、可能性のある和集合の色の個数も、考慮される。
【００２０】
【表１】
2005524319.tif 000004
【００２１】
マイクロブロックの色の個数は、少なくなる傾向にある。
たとえパレット化が好ましい場合であっても、領域が、パレット化の選択肢を失う代償に、しきい値サイズまで成長できる（すなわち、マージされうる）ことが望ましい。
領域のパレット化は、色の個数が一定のしきい値未満となる場合に、許可される。
いずれかの領域がすでにパレット化されているが、マージされた領域のピクセルの総数がしきい値（このしきい値は、マージされた領域がパレット化されえないことを意味する）を超えている場合には、領域は、マージされない。
推定するところ、領域の少なくとも１つが、大きく、多くの色を有する。
大きな領域は、依然としてパレット化されることが好ましい。
例えば、パレットのインデックスが８ビット長を有する場合に、しきい値の色の個数は、２５６であってもよい。
したがって、領域のマージを行った結果、マージされた領域が２５８色を有する場合には、これら２つの領域は、マージされない。
同様の考慮事項は、差分領域についても行われる。
【００２２】
【表２】
2005524319.tif 000005
【００２３】
マージされた領域を含む例示の画像３１０が、図３ａに示される。
マージされた領域は、Ａ、Ｂ、ＣおよびＤとラベル付けされている。
対応する切り取られた木構造が、図３ｂに示される。
Ａ、Ｂ、ＣおよびＤとラベル付けされたノードは、マージされた領域Ａ、Ｂ、ＣおよびＤに対応する。
【００２４】
切り取り後、複数の圧縮選択肢が、領域のいくつかに対して残される。
これらの選択肢は、イントラ領域のパレット化、インタ領域のパレット化、イントラ領域の非パレット化圧縮、および、インタ領域の非パレット化圧縮を含む。
【００２５】
最終的な符号化の決定は、切り取られた木構造の各領域に対して行われる（１２０）。
この決定（インタまたはイントラに対して、可能な場合にはパレット化または非パレット化圧縮）は、実際の符号化技法を用いて生成される最良のビットレートに基づくことができる。
パレットを記述するコストが、考慮される。
パレット化がより良いビットレートを供給する場合には、パレット化が選択される。
非パレット化圧縮がより良いビットレートを供給する場合には、その選択肢が選択される。
【００２６】
パレット化のビットレートを決定するために、複数の異なるパレット順序付け技法が、使用されうる。
例えば、「輝度」の順序付けは、加重和を計算し、各成分は、人間に知覚される輝度に対するその寄与に応じて、重み付けされる。
「インオーダ」順序付けは、所与の領域のラインスキャン時にパレットが現れる順序で、パレットを取り込むことを含む。
領域をマージすると、第１の領域の色が最初に使用され、次いで、順序付けされ、これらのすべての後に、第１の領域になかった第２の領域の色が、出現順で加えられる。
この方法は、領域の単なる再スキャンとは異なり、この多くの時間を要する動作を回避し、また、空間的局所性をより良く保存する。
【００２７】
領域が単一の色を有する場合には、その単一の色のみが、符号化される必要がある。
したがって、この特別なタイプの符号化が、選択される。
【００２８】
図４をさらに参照する。
画像開始コードおよび画像番号が、ビットストリームに書き込まれ、その後、切り取られた木構造の説明が、書き込まれる（１２２）。
【００２９】
木構造は、画像がどのように圧縮されるかを記述する。
木構造の最初の数バイトは、木構造の幅および高さを記述できる。
これによって、復号のための適切な割り当てが可能になる。
後続のビットは、再帰的な木構造に基づきうる。
例えば、最初のビットは、部分（木）が自明（trivial）かどうかを示しうる。
（部分）木が自明である場合には、次の数ビットは、分類（例えば、領域が、イントラとして分類されるのか、それとも、インタとして分類されるのか）およびその領域の圧縮に使用されるアルゴリズムを示しうる。
（部分）木が自明でない場合には、次の数ビットは、左の（部分）木の第１ビットおよび左の部分木の説明を示し、その後、右の（部分）木の第１ビットおよび右の部分木の説明を示しうる。
【００３０】
木構造がビットストリームに書き込まれた後、領域は、木構造ごとに符号化され、符号化された領域は、ビットストリームに書き込まれる（１２４）。
【００３１】
小さな領域は、パレットに追加するオーバーヘッドのため、パレット化の候補となる可能性は低い。
さらに、小さな領域は、可逆圧縮の候補となる可能性も低い。
領域のサイズがしきい値未満である場合には、その領域は、小さいとみなされうる。
異なる分類を有する小さな領域を、単一の異種マクロブロックにマージすることによって、ビットレートは、さらに改善されうる（１２１）。
異種マクロブロックの各領域の分類を特定するオーバーヘッドが、ビットストリームに追加される。
マクロブロックは、単一の圧縮技法を使用して、圧縮されうる。
マイクロブロックのサイズは、局所的な振る舞いと一致するように比較的小さい一方、マクロブロックのサイズは、符号化可能な最小単位に対応する。
【００３２】
画像全体が処理されるまで、すべての領域が、ビットストリームに書き込まれる（１２６）。
最初の画像を除いて、同じステップが、シーケンスの他の画像に対しても実行される。
最初の画像の前に画像は存在しないので、最初の画像の領域は、すべてイントラに分類される。
【００３３】
図１の方法のハードウェアの実施態様は、どの特定のタイプにも限定されない。
例えば、本方法は、図５に示すマシンによって実行されうる。
マシン５１０は、プロセッサ５１２と、プログラム５１６で符号化されたメモリ５１４とを含む。
プログラム５１６は、実行されると、プロセッサ５１２に指令して、画像のシーケンスをロードさせ、図１の方法を実行させる。
プロセッサ５１２は、ビットストリームを表す信号５１８を出力する。
信号５１８は、マシン５１０に記憶されうるし、他の場所に送信されうるし、または、記憶媒体（例えば、光ディスク）５２０に記録されうる。
【００３４】
本発明は、本方法および今説明した装置に限定されない。
区画された画像は、木構造以外のデータ構造によっても表されうる。
小さな領域を大きな領域にクラスタリングできる任意の「ブロック保持（blockkeeping）」方法が、使用されうる。
例えば、領域のリストが、保持されうる。
【００３５】
本方法をＲＧＢ色空間との関連で説明したが、本方法は、そのように限定されない。
ＹＵＶ色空間等の他の色空間も、使用されうる。
ＹＵＶ色空間では、クロミナンスチャネル（ＵおよびＶ）は、ルミナンスチャネル（Ｙ）と同じまたは異なるサンプリングレートを有することができる。
【００３６】
非パレット化圧縮を可逆圧縮として説明したが、本発明は、そのように限定されない。
非パレット化圧縮は、非可逆であってもよい。
さらに、パレット化は、非可逆であってもよいし、可逆であってもよい。
【００３７】
差分領域は、ｋ番目の画像の領域と、ｋ−１番目の画像の同じ空間位置における領域との間の差分に限定されない。
動き補償が、差分領域に対してなされて、それによって、ｋ−１番目の画像の領域を、異なる空間位置にできる。
動き補償は、異なる空間位置を指し示す動きベクトルを生成する。
動き補償は、一定の判定基準に従いうる。
例えば、判定基準は、動きベクトルを符号化するコストを含みうる。
動き補償が、ビットレートを改善しない場合には、その動き補償は、実行されない。
【００３８】
差分領域は、ｋ−１番目のフレームの領域との差分に限定されない。
差分は、あらゆる先行領域との差分でありうる（例えば、ｋ−４番目のフレーム等の先のフレームの領域、ｋ番目のフレームの領域であって先に処理された領域）。
先行領域は、すでに処理された領域の変形（例えば、回転、ズームまたは他の動き）でありうる。
差分は、実際の領域にも限定されない。
差分は、先行領域から合成された（例えば、推定された）領域との差分でありうる。
例えば、領域は、先行領域の線形結合から合成されうる（復号器が、領域を合成するのに十分な画像データを記憶できるという条件で）。
先行領域が復号時に再現されうる限り、どの差分も、生成されうる。
【００３９】
図６を参照する。
図６は、動き補償を行う符号化器・復号器システム６１０を示している。
符号化器サブシステム６１２は、符号化器６１４を含む。
符号化器６１４は、図１に示される機能のすべてを実行できる。
符号化器６１４は、図５に示す構成を有しうるし、ＡＳＩＣ、状態マシンまたは他のハードウェアの実施態様でありうる。
符号化器６１４は、画像データを受け取り、各画像の現領域および差分領域を決定する。
差分領域は、現領域および先行領域から生成される。
先行領域は、バッファ６１６に記憶される。
動き補償は、動きベクトルを推定する第１の回路６１８、および、先行領域に動きベクトルを適用する第２の回路６２０により、先行領域に対して任意選択に実行される。
加算接合部６２１は、符号化器６１４の要求に応じて、先行領域に対して動き補償を行う。
符号化器６１４は、動きベクトルを符号化し、符号化された動きベクトルをビットストリームに書き込む。
【００４０】
符号化器サブシステム６１２は、ビットストリームを表す信号（Ｓ１）を生成する。
このビットストリームは、符号化された動きベクトル、木構造の説明および符号化された領域を含む。
また、ビットストリームは、領域が現領域であるのか、それとも差分領域であるのかも示す。
信号（Ｓ１）は、復号器サブシステム６２２に送信される。
【００４１】
さらに、図７を参照する。
符号化器・復号器システム６１０は、符号化器サブシステム６１２のみによって木構造が生成される点で、非対称である。
復号器サブシステム６２２は、木構造および符号化された領域を読み出し（７１０）、木構造ごとに符号化された領域を復号し（７１２）、復号された領域から画像を再構築する（７１４）。
領域のいくつかは、再構築にパレットを使用できる。
再構築された画像は、先行領域の再構築での使用のために、バッファ６２６に記憶される。
また、再構築された画像も、記憶されうるし、別のデバイス（例えば、表示デバイス）に送出等されうる。
【００４２】
復号器６２４が差分領域を復号し、その差分領域が動き補償された先行領域から生成されていた場合、復号器６２４は、動きベクトルを復号し、動き補償器６２８にその動きベクトルを供給する。
動き補償器６２８は、先行領域に対して動き補償を行う。
先行領域は、復号器６２４によって供給された復号された差分領域に対して動き補償された領域に加算される。
この合計が、復号された現領域となる。
【００４３】
復号器６２４は、図５に示される構成を有しうるし、ＡＳＩＣ、状態マシンまたは他のハードウェアの実施態様でありうる。
【００４４】
本発明を、画像情報から直接生成される木構造との関連で説明してきた。
しかしながら、本発明は、そのようには限定されない。
木構造は、先に生成された木構造から生成されうる。
【００４５】
図６に示される符号化器・復号器システム６１０を参照して、以下の例を考察する。
第１の例として、符号化器６１４は、ｋ番目の画像の木構造を生成し、その木構造を、バッファ６１６に記憶されたライブラリに追加し、その木構造をビットストリームに加える。
符号化器６１４は、ｋ＋１番目の画像の木構造を生成する。
この木構造は、ｋ番目の画像の木構造と同一である。
符号化器６１４は、ｋ＋１番目の画像の木構造をビットストリームに加える代わりに、インデックス番号をビットストリームに加える。
復号器６２４は、ビットストリームを受信し、ビットストリームからｋ番目の画像の木構造を読み出し、その木構造を、自身のバッファ６２６に記憶されたライブラリに追加する。
後に、復号器６２４は、ｋ＋１番目の画像のインデックスを読み出し、そのインデックスを使用して、自身のバッファ６２６に記憶されたライブラリから木構造にアクセスする。
より一般的には、符号化器６１４および復号器６２４は共に、木構造の同一のライブラリを生成でき、符号化器６１４は、木構造またはその一部を、自身のライブラリにおいて当該木構造またはその一部を単にインデックスすることによって、符号化でき、復号器６２４は、そのインデックスを使用して、自身のライブラリから当該木構造またはその一部にアクセスできる。
【００４６】
バッファ６１６および６２６に記憶されたライブラリは、最初に、標準的なアプリオリの木構造を含みうる。
符号化器６１４および復号器６２４は、先に生成された木構造を自身のライブラリに追加することによって、自身のライブラリを構築できる。
【００４７】
第２の例として、符号化器６１４は、ｋ番目の画像の木構造またはその一部を予測するアルゴリズムを使用する。
ｋ番目の画像の木構造は、バッファ６１６に記憶された、先に生成された木構造に応じて、予測される。
ｋ番目の画像の木構造は、先に生成された木構造の１つ（例えば、ｋ−３番目の画像の木構造）を使用することによって、または、先に生成された数個の木構造（例えば、ｋ―１番目、ｋ−２番目およびｋ−３番目の画像の木構造）の合成として予測されうる。
復号器６２４は、同じアルゴリズムおよび先に生成された同じ木構造を使用して、ｋ番目の画像の木構造を予測する。
【００４８】
先に生成されたパレットは、先に生成された木構造と同じように使用されうる。
一例として、符号化器６１４および復号器６２４は共に、先に生成されたパレットから、パレットの同一のライブラリを構築でき、符号化器６１４は、自身のライブラリにおいてパレットをインデックスすることによって、画像の領域のパレットを符号化でき、復号器６２４は、そのインデックスを使用して、自身のライブラリからパレットにアクセスできる。
【００４９】
別の例として、符号化器６１４は、画像の領域の１つまたは複数のパレットを予測するアルゴリズムを使用する。
これらのパレットは、バッファ６１６に記憶された、先に生成されたパレットに応じて、予測されうる。
復号器６２４は、同じアルゴリズムおよび先に生成された同じパレットを使用して、画像の領域のパレットを予測する。
【００５０】
本発明は、どの特定の用途にも限定されない。
例えば、この圧縮は、専用の高速ローカルエリアネットワークを介した高品質で高解像度の対話型ビデオに使用されうる。
高性能サーバまたはサーバのクラスタは、グラフィックスまたはビデオを生成し、圧縮し、圧縮されたグラフィックスまたはビデオを、高速リンクを介して、ワークステーション（複数可）に送信できる。
【００５１】
本発明は、上記に説明および図示した特定の実施の形態に限定されない。
かわりに、本発明は、添付の特許請求の範囲に従って解釈される。
【図面の簡単な説明】
【００５２】
【図１】本発明の一実施の形態による画像シーケンスを圧縮する方法の図である。
【図２ａ】切り取り前の区画された画像の図である。
【図２ｂ】切り取り前の対応する木構造の図である。
【図３ａ】切り取り後の区画された画像の図である。
【図３ｂ】切り取り後の対応する木構造の図である。
【図４】図１の方法の結果生成されたビットストリームの一部の図である。
【図５】本発明の一実施の形態による画像シーケンスを圧縮するマシンの図である。
【図６】本発明の一実施の形態による符号化器・復号器システムの図である。
【図７】本発明の一実施の形態によるビットストリームを復号する方法の図である。
【符号の説明】
【００５３】
２１０・・・画像
２１２・・・マイクロブロック
２１４・・・木構造
２１６・・・リーフ
２１８・・・内部ノード
３１０・・・画像
５１０・・・マシン
５１２・・・プロセッサ
５１４・・・メモリ
５１６・・・プログラム
５１８・・・信号
５２０・・・記憶媒体
６１０・・・符号化器・復号器システム
６１２・・・符号化器サブシステム
６１４・・・符号化器
６１６・・・バッファ
６１８・・・動き推定
６２０・・・動き補償
６２１・・・加算接合部
６２２・・・復号器サブシステム
６２４・・・復号器
６２６・・・バッファ
６２８・・・動き補償
【図１】
2005524319.tif 000006
【図２ａ】
2005524319.tif 000007
【図２ｂ】
2005524319.tif 000008
【図３ａ】
2005524319.tif 000009
【図３ｂ】
2005524319.tif 000010
【図４】
2005524319.tif 000011
【図５】
2005524319.tif 000012
【図６】
2005524319.tif 000013
【図７】
2005524319.tif 000014
【国際調査報告】
2005524319.tif 000015
2005524319.tif 000016
2005524319.tif 000017