(57)【特許請求の範囲】
【請求項１】
離散ウエーブレット変換(DWT)により変換して所定レベルに分解でき、かつ各ブロックが一次元および二次元の複数の係数を含む特定のブロックサイズを有しブロック単位で符号化される複数の画素を含むデジタル画像を符号化する方法であって、
ａ）各タイルが、ＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、またＤＷＴ分解の前記所定レベルで前記ブロックの二次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、画像を複数のタイルに分割する工程と、
ｂ）前記複数のタイルの中から、ＤＷＴ分解の対象となる処理対象タイルを選択する工程と、
ｃ）ＤＷＴを使用して前記処理対象タイルをＤＷＴ分解の少なくとも一つのレベルに分解してＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドを含む複数のサブバンドを形成する工程と、
ｄ）ＬＨ、ＨＬおよびＨＨサブバンドの各サブバンド内の係数を蓄積して前記特定のブロックサイズのブロックを形成するとともに、各ブロックをビットストリームに符号化する工程と、
ｅ）前記ＬＬサブバンドの係数を蓄積するとともに、当該ＬＬサブバンドの所定数の係数が蓄積されるまで、前記工程ｂ）からｅ）を繰り返す工程と、
ｆ）前記処理対象タイルとして、蓄積されたＬＬサブバンドの係数の前記所定数を割り当てる工程と、
ｇ）前記ＤＷＴ分解の前記所定レベルに達するまで、前記工程ｃ）からｇ）を繰り返す工程と、
ｈ）前記ＬＬサブバンドをビットストリームに符号化する工程と、
を含むことを特徴とするデジタル画像を符号化する符号化方法。
【請求項２】
前記ＤＷＴ分解は、Daubechies９／７フィルタを使用することを特徴とする請求項１に記載の符号化方法。
【請求項３】
前記ＤＷＴ分解は、Haarフィルタを使用することを特徴とする請求項１に記載の符号化方法。
【請求項４】
離散ウエーブレット変換(DWT)により変換して所定レベルに分解でき、かつ各ブロックが一次元および二次元の複数の係数を含む特定のブロックサイズを有しブロック単位で符号化される複数の画素を含むデジタル画像を符号化する符号化方法であって、
ａ）各タイルがＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、また、ＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、画像を複数のタイルに分割する工程と、
ｂ）前記複数のタイルの中から、ＤＷＴ分解の対象となる処理対象タイルを選択する工程と、
ｃ）ＤＷＴを使用して前記処理対象タイルをＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドの複数の係数を提供するように分解する工程と、
ｄ）工程（ｃ）で得られた現在レベルのＬＨ、ＨＬ、ＨＨサブバンドの係数をビットストリームに符号化する工程と、
ｅ）前記現在レベルが前記所定レベルであるかどうかを判定し、
ｅａ）前記現在レベルが前記所定レベルであれば、前記ＬＬサブバンドの係数をビットストリームに符号化し、前記工程ｂ）からｅ）を繰り返し、
ｅｂ）前記現在レベルが前記所定レベルでなければ、前記ＬＬサブバンドの前回符号化されていない係数を記憶する工程と、
ｆ）前記現在レベルにおける前記ＬＬサブバンドの前記記憶された係数の数が少なくとも所定数であるかどうかを判定する工程と、
ｆａ）前記記憶された係数の数が少なくとも前記所定数であれば、処理対象タイルとして前記係数の前記所定数を処理対象タイルに割り当て、前記工程ｃ）からｆ）を繰り返す工程と、
ｆｂ）記憶された前記係数の数が前記所定数より少なければ、前記工程ｂ）からｆ）を繰り返す工程と、
を含むことを特徴とするデジタル画像を符号化する符号化方法。
【請求項５】
離散ウエーブレット変換(DWT)により変換して所定レベルに分解でき、かつ各ブロックが一次元および二次元の複数の係数を含む特定のブロックサイズを有しブロック単位で符号化される複数の画素を含むデジタル画像を符号化する符号化装置であって、
ａ）各タイルが、ＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、またＤＷＴ分解の前記所定レベルで前記ブロックの二次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、画像を複数のタイルに分割する分割手段と、
ｂ）前記複数のタイルの中から、ＤＷＴ分解の対象となる処理対象タイルを選択する選択手段と、
ｃ）ＤＷＴを使用して前記処理対象タイルをＤＷＴ分解の少なくとも一つのレベルに分解してＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドを含む複数のサブバンドを形成する分解手段と、
ｄ）前記ＬＬサブバンドの係数の所定数を蓄積する手段と、
ｅ）蓄積された前記係数の前記所定数を処理対象タイルとして割り当てる手段と、
ｆ）前記処理対象タイルをさらなるレベルの分解度に分解するために処理対象タイルを前記分解手段に帰還させる手段と、
ｇ）ＬＨ、ＨＬおよびＨＨサブバンドの各サブバンド内の係数を蓄積して前記特定のブロックサイズのブロックを形成するとともに、前記所定レベルでＬＬサブバンド内の前記特定のブロックサイズの少なくとも一つのブロックを蓄積する手段と、
ｈ）各前記ブロックをビットストリームに符号化する符号化手段と、
を有することを特徴とする符号化装置。
【請求項６】
離散ウエーブレット変換(DWT)により変換して所定レベルに分解でき、かつ各ブロックが一次元および二次元の複数の係数を含む特定のブロックサイズを有しブロック単位で符号化される複数の画素を含むデジタル画像を符号化する符号化装置であって、
各画像の部分がＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、また、ＤＷＴ分解の前記所定レベルで前記ブロックの二次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、前記画像の少なくとも一部を記憶する手段と、
リニア変換を前記画像の前記一部の一次元および二次元それぞれに適用して、各サブバスバンドが少なくとも一つの係数を含むＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドを提供する第１および第２フィルタ手段と、
前記ＬＬサブバンドの係数を所定数蓄積し、前記第１および第２フィルタ手段によってリフィルタして次のレベル分解を達成するための画像部分として、蓄積された前記係数を使用する部分バンド記憶手段と、
前記ＬＨ，ＨＬおよびＨＨサブバンド内の各レベルに対する前記特定のブロックサイズの前記ブロックを蓄積し、また前記所定レベルの分解レベルにおけるＬＬサブバンド内の前記特定のブロックサイズの前記ブロックを蓄積するためのサブバンド記憶手段と、
各蓄積したブロックをビットストリームに符号化する符号化手段と、
を具備することを特徴とする符号化装置。
【請求項７】
離散ウエーブレット変換(DWT)により変換して所定レベルに分解でき、かつ各ブロックが一次元および二次元の複数の係数を含む特定のブロックサイズを有しブロック単位で符号化される複数の画素を含むデジタル画像を符号化する装置のためのプログラムを記憶するコンピュータにより読取可能な記憶媒体において、前記プログラムは前記コンピュータに、
ａ）各タイルが、ＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、またＤＷＴ分解の前記所定レベルで前記ブロックの二次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、画像を複数のタイルに分割する工程と、
ｂ）前記複数のタイルの中から、ＤＷＴ分解の対象となる処理対象タイルを選択する工程と、
ｃ）ＤＷＴを使用して前記処理対象タイルをＤＷＴ分解の少なくとも一つのレベルに分解してＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドを含む複数のサブバンドを形成する分解工程と、
ｄ）ＬＨ、ＨＬおよびＨＨサブバンドの各サブバンドの係数を蓄積して前記特定のブロックサイズのブロックを形成するとともに、各ブロックをビットストリームに符号化する工程と、
ｅ）前記ＬＬサブバンドの係数を蓄積するとともに、当該ＬＬサブバンドの係数が所定数が蓄積されるまで、工程ｂ）からｅ）を繰り返す工程と、
ｆ）前記処理対象タイルに、蓄積されたＬＬサブバンドの前記係数の前記所定数を割り当てる割り当て工程と、
ｇ）前記ＤＷＴ分解の前記所定レベルに達するまで、工程ｃ）からｇ）を繰り返す繰り返し工程と、
ｈ）前記ＬＬサブバンドをビットストリームに符号化する符号化工程と実行させるプログラムであることを特徴とする記憶媒体。
【請求項８】
離散ウエーブレット変換(DWT)により変換して所定レベルに分解でき、かつ各ブロックが一次元および二次元の複数の係数を含む特定のブロックサイズを有しブロック単位で符号化される複数の画素を含むデジタル画像を符号化する装置のためのプログラムを記憶するコンピュータにより読取可能な記憶媒体において、前記プログラムは前記コンピュータに、
ａ）各タイルが、ＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、またＤＷＴ分解の前記所定レベルで前記ブロックの二次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、画像を複数のタイルに分割する工程と、
ｂ）前記複数のタイルの中から、ＤＷＴ分解の対象となる処理対象タイルを選択する選択工程と、
ｃ）ＤＷＴを使用して前記処理対象タイルをＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドの複数の係数を提供するように分解する工程と、
ｄ）工程（ｃ）で得られた現在レベルのＬＨ、ＨＬ、ＨＨサブバンドの係数をビットストリームに符号化する符号化工程と、
ｅ）前記現在レベルが前記所定レベルであるかどうかを判定する判定工程と、
ｅａ）前記現在レベルが前記所定レベルであれば、前記ＬＬサブバンドの係数をビットストリームに符号化する工程と；工程ｂ）からｅ）を繰り返す工程と；
ｅｂ）前記現在レベルが前記所定レベルでなければ、前記ＬＬサブバンドの前回符号化されていない係数を記憶する記憶工程と；
ｆ）前記現在レベルにおけるＬＬサブバンドの前記記憶された係数が、少なくとも所定数であるかどうかを判定する工程と；
ｆａ）記憶された前記係数の数が少なくとも前記所定数であれば、処理対象タイルとして前記係数の前記所定数を割り当てる割当工程と；工程ｃ）からｆ）を繰り返す工程と；
ｆｂ）記憶された前記係数の数が前記所定数より小さければ、工程ｂ）からｆ）を繰り返す繰返工程と；
を実行させるプログラムであることを特徴とする記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、デジタル画像圧縮分野、特に画像のウエーブレット分解を実行する符号化方法および装置に関する。
【０００２】
【従来の技術】
デジタル・データ圧縮、および特にデジタル画像圧縮の分野は、一時非常に注目されていたが、特に最近、離散ウエーブレット変換(DWT) に基づく圧縮技術がますます一般的になってきている。これはＤＷＴが画像の非冗長階層的分解を提供し、また、画像の圧縮結果が良好な定歪み統計値を提供するからである。
【０００３】
一般的に、画像の離散ウエーブレット変換(DWT) は、一連の一次元ＤＷＴを用いて実行される。信号（すなわち、画像の行）の一次元ＤＷＴが、ロウパスおよびハイパスフィルタリングされ、各フィルタされた信号を２つおきに選んで実行される。この２つおきに取り出すのは、フィルタリング処理されたサンプルを２つおきに計算して保持することを意味する。たたみこみ（フィルタリング）が実行されると、フィルタは、普通は一つのサンプルであるのとは代わって、一度に二つのサンプル毎に進行する。この方法において、Ｎ個のサンプルの信号に対して、Ｎ個のＤＷＴのサンプル、すなわち、実質的にＮ／２のロウパス・サンプルと実質的にＮ／２のハイパス・サンプルがある。
【０００４】
【発明が解決しようとする課題】
これはランダム・アクセス・メモリ（ＲＡＭ）のようなコンピュータ・メモリ内で全画像をバッファリングすることによって実行されるのが一般的で、バッファされた画像にＤＷＴが実行され、その変換された画像が符号化される。あいにく、このアプローチには大量のメモリ、特に2000画素×2000画素或いはそれ以上を必要とし、十分な処理速度を達成しなければならない場合には、相当なバンド幅を必要とする。
【０００５】
本発明は上記従来例に鑑みてなされたもので、本発明の目的は、既存の構成の一つのまたはそれ以上の欠点を実質上克服するか、ないしは少なくともこれを改善することにある。例えば、少ないバッファの容量で、複数レベルのＤＷＴ実行できる構成を提供する。
【０００６】
【課題を解決するための手段】
本発明の第１の態様によれば、離散ウエーブレット変換(DWT)により変換して所定レベルに分解され、各ブロックが一次元および二次元における係数による特定ブロック・サイズを有するブロック単位で符号化できる複数の画素を含むデジタル画像を符号化する方法を提供することにあり、この方法は、
ａ）画像を複数のタイルに分割する工程であって、各タイルが、ＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、またＤＷＴ分解の前記所定レベルで前記ブロックのニ次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、画像を複数のタイルに分割する工程と；
ｂ）前記複数のタイルの中から、ＤＷＴ分解の対象となる処理対象タイルを選択する工程と；
ｃ）ＤＷＴを使用して前記処理対象タイルをＤＷＴ分解の少なくとも一つのレベルに分解してＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドを含む複数のサブバンドを形成する工程と；
ｄ）ＬＨ、ＨＬおよびＨＨサブバンドの各サブバンド内の係数を蓄積して前記特定のブロックサイズのブロックを形成するとともに、各ブロックをビットストリームに符号化する工程と；
ｅ）前記ＬＬサブバンドの係数を蓄積するとともに、当該ＬＬサブバンドの所定数の係数が蓄積されるまで、前記工程ｂ）からｅ）を繰り返す工程と；
ｆ）前記処理対象タイルとして、蓄積されたＬＬサブバンドの前記所定数の係数を割り当てる工程と；
ｇ）前記ＤＷＴ分解の前記所定レベルに達するまで、前記工程ｃ）からｇ）を繰り返す工程と；
ｈ）前記ＬＬサブバンドをビットストリームに符号化する工程と；
を含んでいる。
【０００７】
本発明の第２の態様によれば、
離散ウエーブレット変換(DWT)により変換して所定レベルに分解でき、かつ各ブロックが一次元および二次元の複数の係数を含む特定のブロックサイズを有しブロック単位で符号化される複数の画素を含むデジタル画像を符号化する符号化方法であって、
ａ）各タイルがＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、また、ＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、画像を複数のタイルに分割する工程と、；
ｂ）前記複数のタイルの中から、ＤＷＴ分解の対象となる処理対象タイルを選択する工程と；
ｃ）ＤＷＴを使用して前記処理対象タイルをＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドの複数の係数を提供するように分解する工程と；
ｄ）前記工程（ｃ）で得られた現在レベルのＬＨ、ＨＬ、ＨＨサブバンドの係数をビットストリームに符号化する工程と；
ｅ）前記現在レベルが前記所定レベルであるかどうかを判定し：
ｅａ）前記現在レベルが前記所定レベルであれば、前記ＬＬサブバンドの係数をビットストリームに符号化し、前記工程ｂ）からｅ）を繰り返し；
ｅｂ）前記現在レベルが前記所定レベルでなければ、前記ＬＬサブバンドの前回符号化されていない係数を記憶する工程と；
ｆ）前記現在レベルにおける前記ＬＬサブバンドの前記記憶された係数が少なくとも所定数であるかどうかを判定する工程と；
ｆａ）前記記憶されたＬＬ係数が少なくとも前記所定数であれば、処理対象タイルとして前記係数の前記所定数を処理対象タイルに割り当て、前記工程ｃ）からｆ）を繰り返す工程と；
ｆｂ）記憶された前記係数の数が前記所定数より少なければ、前記工程ｂ）からｆ）を繰り返す工程と；
を含む符号化方法が提供される。
【０００８】
本発明の第３の態様によれば、
離散ウエーブレット変換(DWT)により変換して所定レベルに分解でき、かつ各ブロックが一次元および二次元の複数の係数を含む特定のブロックサイズを有しブロック単位で符号化される複数の画素を含むデジタル画像を符号化する符号化装置であって、
ａ）各タイルが、ＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、またＤＷＴ分解の前記所定レベルで前記ブロックの二次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、画像を複数のタイルに分割する手段；
ｂ）前記複数のタイルの中から、ＤＷＴ分解の対象となる処理対象タイルを選択する選択手段と；
ｃ）ＤＷＴを使用して、前記処理対象タイルをＤＷＴ分解の少なくとも一つのレベルに分解してＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドを含む複数のサブバンドを形成する分解手段と；
ｄ）前記ＬＬサブバンド係数の所定数を蓄積する手段と；
ｅ）蓄積された前記係数の前記所定数を処理対象タイルとして割り当てる手段と；
ｆ）前記処理対象タイルをさらなるレベルの分解度に分解するために処理対象タイルを前記分解手段に帰還させる手段と；
ｇ）ＬＨ、ＨＬおよびＨＨサブバンドの各サブバンド内の係数を蓄積して前記特定のブロックサイズのブロックを形成するとともに、前記所定レベルでＬＬサブバンド内の前記特定のブロックサイズの少なくとも一つのブロックを蓄積する手段と；
ｈ）各前記ブロックをビットストリームに符号化する符号化手段と；
を有することを特徴とする符号化装置が提供される。
【０００９】
本発明の第４の態様によれば、
離散ウエーブレット変換(DWT)により変換して所定レベルに分解でき、かつ各ブロックが一次元および二次元の複数の係数を含む特定のブロックサイズを有しブロック単位で符号化される複数の画素を含むデジタル画像を符号化する符号化装置であって、
各画像の部分がＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、また、ＤＷＴ分解の前記所定レベルで前記ブロックの二次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、前記画像の少なくとも一部を記憶する手段と；
リニア変換を前記画像の前記一部の一次元および二次元それぞれに適用して、各サブバンドが少なくとも一つの係数を含むＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドを提供する第１および第２フィルタ手段と；
ＬＬサブバンドの係数を所定数蓄積し、前記第１および第２フィルタ手段によってリフィルタして次のレベル分解を達成するための画像部分として、蓄積された前記係数を使用する部分バンド記憶手段と；
ＬＨ，ＨＬおよびＨＨサブバンド内の各レベルに対する前記特定のブロックサイズの前記ブロックを蓄積し、また前記所定レベルの分解レベルにおけるＬＬサブバンド内の前記特定のブロックサイズの前記ブロックを蓄積するためのサブバンド記憶手段と；
各蓄積ブロックをビットストリームに符号化する符号化手段と；
を具備する符号化装置が提供される。
【００１０】
本発明の第５の態様によれば、
離散ウエーブレット変換(DWT)により変換して所定レベルに分解でき、かつ各ブロックが一次元および二次元の複数の係数を含む特定のブロックサイズを有しブロック単位で符号化される複数の画素を含むデジタル画像を符号化する装置のためのプログラムを記憶するコンピュータにより読取可能な記憶媒体において、前記プログラムは前記コンピュータに、
ａ）各タイルが、ＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、またＤＷＴ分解の前記所定レベルで前記ブロックの二次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、画像を複数のタイルに分割する工程と、
ｂ）前記複数のタイルの中から、ＤＷＴ分解の対象となる処理対象タイルを選択する工程と、
ｃ）ＤＷＴを使用して前記処理対象タイルをＤＷＴ分解の少なくとも一つのレベルに分解してＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドを含む複数のサブバンドを形成する分解工程と、
ｄ）ＬＨ、ＨＬおよびＨＨサブバンドの各サブバンドの係数を蓄積して前記特定のブロックサイズのブロックを形成するとともに、各ブロックをビットストリームに符号化する工程と、
ｅ）前記ＬＬサブバンドの係数を蓄積するとともに、当該ＬＬサブバンドの係数が所定数が蓄積されるまで、工程ｂ）からｅ）を繰り返す工程と、
ｆ）前記処理対象タイルに、蓄積されたＬＬサブバンドの前記係数の前記所定数を割り当てる割り当て工程と、
ｇ）前記ＤＷＴ分解の前記所定レベルに達するまで、工程ｃ）からｇ）を繰り返す繰り返し工程と、
ｈ）前記ＬＬサブバンドをビットストリームに符号化する符号化工程と実行させるプログラムであることを特徴とする記憶媒体が提供される。
【００１１】
本発明の第６の態様によれば、
離散ウエーブレット変換(DWT)により変換して所定レベルに分解でき、かつ各ブロックが一次元および二次元の複数の係数を含む特定のブロックサイズを有しブロック単位で符号化される複数の画素を含むデジタル画像を符号化する装置のためのプログラムを記憶するコンピュータにより読取可能な記憶媒体において、前記プログラムは前記コンピュータに、
ａ）各タイルが、ＤＷＴ分解の前記所定レベルで前記ブロックの一次元における係数を発生するのに必要とされる画素の最小数を有し、またＤＷＴ分解の前記所定レベルで前記ブロックの二次元における係数を発生するのに必要とされる画素の最小数より少ない数を有し、１回のＤＷＴ分解で得られるＬＨ，ＨＬ，ＨＨから前記特定のブロックサイズのブロックを形成できる画素数を有するように、画像を複数のタイルに分割する工程と、
ｂ）前記複数のタイルの中から、ＤＷＴ分解の対象となる処理対象タイルを選択する選択工程と、
ｃ）ＤＷＴを使用して前記処理対象タイルをＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドの複数の係数を提供するように分解する工程と、
ｄ）工程（ｃ）で得られた現在レベルのＬＨ、ＨＬ、ＨＨサブバンドの係数をビットストリームに符号化する符号化工程と、
ｅ）前記現在レベルが前記所定レベルであるかどうかを判定する判定工程と、
ｅａ）前記現在レベルが前記所定レベルであれば、前記ＬＬサブバンドの係数をビットストリームに符号化する工程と；工程ｂ）からｅ）を繰り返す工程と；
ｅｂ）前記現在レベルが前記所定レベルでなければ、前記ＬＬサブバンドの前回符号化されていない係数を記憶する記憶工程と；
ｆ）前記現在レベルにおけるＬＬサブバンドの前記記憶された係数が、少なくとも所定数であるかどうかを判定する工程と；
ｆａ）記憶された前記係数の数が少なくとも前記所定数であれば、処理対象タイルとして前記係数の前記所定数を割り当てる割当工程と；工程ｃ）からｆ）を繰り返す工程と；
ｆｂ）記憶された前記係数の数が前記所定数より小さければ、工程ｂ）からｆ）を繰り返す繰返工程と；
を実行させるプログラムであることを特徴とする記憶媒体が提供される。
【００１３】
【発明の実施の形態】
以下、添付図面を参照して本発明の好適な実施の形態を詳細に説明する。なお、添付図面のいずれか一つまたはそれ以上において、同じ工程および（または）特徴に同じ参照符号を付して参照するものとし、強調しない限り、これらの工程および（または）特徴は、この説明の目的としては、同じ機能または動作を有するのものである。
【００１４】
図１を参照して、４レベルまでの画像の離散ウエーブレット分散を示す。最高レベルにおいて、すなわち、レベル４において、ロウ−ロウ（ＬＬ）周波数サブバンド（またはＤＣサブバンド）およびハイ−ロウ（ＨＬ４）周波数サブバンド、ロウ−ハイ（ＬＨ４）周波数サブバンドおよびハイ−ハイ（ＨＨ４）周波数サブバンドがある。次のレベルに下がると、そのレベルに対してハイ−ロウ（ＨＬ３）周波数サブバンド、ロウ−ハイ（ＬＨ３）周波数サブバンド、ロウ−ハイ（ＬＨ３）周波数サブバンドおよびハイ−ハイ（ＨＨ３）周波数サブバンドがある。また最低レベルにおいて、ハイ−ロウ（ＨＬ１）周波数サブバンド、ロウ−ハイ（ＬＨ１）周波数サブバンドおよびハイ−ハイ（ＨＨ１）周波数サブバンドがある。
【００１５】
各レベルは、（単一レベル）離散ウエーブレット変換(DWT) の適用によって発生される。従って、ＤＷＴを画像へ適用することは、第１レベルのＤＣサブバンドと、それよりも３つ高い周波数サブバンドＨＬ１、ＬＨ１およびＨＨ１を発生することになる。こうして、ＤＷＴが第１レベルのＤＣ（またはＬＬ）サブバンドに適用されて、第２レベルのＤＣサブバンドと、それよりも３つ高い周波数サブバンドＨＬ２、ＬＨ２およびＨＨ２が発生される。次に、第２レベルのＤＣサブバンドに更にＤＷＴを適用することにより、第三レベルのＤＣサブバンドと、それよりも３つ高いサブバンドＨＬ３、ＬＨ３およびＨＨ３などが発生され、所望のレベルに分解される。その結果、上述の四つのレベルの分解が、（単一レベル）ＤＷＴの４つの適用、すなわち、画像への第１の適用と、上述した再帰（回帰）方法により得られたロウ−ロウ（ＬＬ）周波数サブバンドへの後続の適用とを必要とする。
【００１６】
本発明の好適な実施の形態は、メモリ効率（エフィシェント）と低メモリ・バンド幅（画素当りのバイト）を実現といった点で、所定のレベルの分解を達成する。好ましい実施の形態の更なる実施は、分解されるべき画像のサイズ（１Ｋ画素×１Ｋ画素より一般的に大きい画像に対して）とは実質上無関係である。すなわち、所定レベルにおける画像の離散ウエーブレット分解は、全画像を記憶するのに必要とする量よりも小さいメモリ容量で、また、画像の幅または高さとはほぼ無関係なメモリ・バッファによって提供される。
【００１７】
本発明の好適な実施の形態は、ＤＷＴ分解の最大レベル数を固定にし、分解されるべき画像を複数のタイルに分割し、また、各タイルの一次元が、ＤＷＴ分解の最大レベルにおけるＤＣブロックの対応する（第１）次元の所定サイズＤＣブロックを生成するのに必要な略最小画素数となるように分割することによって、十分なメモリ・バッファと低メモリ・バンド幅を達成する。さらに、各タイルの二次元は、所定サイズのＤＣブロックの対応する（第２）次元を生成するのに必要とする略最小画素数より少ない。好ましくは、各タイルの二次元は、画素で測定した最小長さを有していることであり、これは最大レベルにおける所定サイズＤＣブロックの対応する次元の（フラクション）サブ−マルチプルを生成することを必要とされるからである。
【００１８】
例えば、好ましい実施の形態によれば、Daubechies  ９／７ＤＷＴフィルタ（すなわち、９タップ・ロウパスと７タップ・ハイパス）、および各レベルにおいて３２係数×３２係数（高さ×幅）のエントロピー符号化ＤＷＴブロック（アレイ）を使用して、各レベルにおいて、ＤＷＴ分解の４レベルの最大まで、画像を複数のオーバラップするタイルにサブ分割する必要があり、各タイルは一次元（例えば、タイルの高さ）内で６１７画素となり、二次元（例えば、タイルの幅）内で７１画素となる。各タイルは、分解の各反復において、ロウ−ロウ周波数部分の中間バッファリングにより４レベルにＤＷＴ分解され、所定数のＤＣ係数が生成される。この種のタイルで約９回処理すると、ＤＣ係数の３２×３２ブロックがリカバーされ、エントロピー符号化される。各反復を通して、より高い周波数係数（例えば、各レベルにおけるＨＬ、ＬＨおよびＨＨ）の３２×３２ブロックもエントロピー符号化される。
【００１９】
次に、好ましい実施の形態につき、まず最初に、Daubechies  ９／７ＤＷＴフィルタを使用する画像の４レベルＤＷＴ分解を参照し、続いてＤＷＴ係数の３２×３２ブロックのエントロピー符号化を説明するが、本発明はこれに限定されるものではない。ブロックのエントロピー符号化の前に、分解レベルの異なる所定最大数、異なるフィルタおよび／または蓄積された係数の異なるブロックサイズが、本発明の範囲と概念から逸脱することなしに使用することができる。例えば、５レベルＤＷＴ分解が実行でき、および／またはＤＷＴ係数の６４×６４ブロックを、１つのブロックのエントロピー符号化の前に蓄積することができる。さらに、多数のウエーブレット・フィルタが「ＨＡＡＲ」フィルタ、「LeGall 5/3」 「LeGall 10/18」を含めて使用することができる。この種の変形例により、次に説明するハードウエア・アーキテクチャを対応して変更してもよい。
【００２０】
ここで、図２および図３を参照して、本発明の好適な実施の形態による画像のタイリングを示す。すなわち、好ましくは画像を部分的にオーバラップさせて、複数のタイルにサブ分割する。各タイルの大きさは、分解のレベル、エントロピー符号化の前に蓄積されたブロック・サイズ、および使用されるＤＷＴフィルタの種類等の所定パラメータを固定することによって決定される。各タイルは、タイルの一つの次元の７１画素に、他の次元の６１７画素を掛けたものからなる。図２において、タイルは水平方向に配置され、すなわち、タイルの長手側が画像の走査線と略平行にレイアウトされている。図３は、タイルが垂直方向に配置された別の構成を示しており、短手側が画像の走査線と略平行である。図２および図３の各タイルは、「タイルｎ」の符号が付けるられるが、ここでｎは正の整数で、符号付け（ラベリング）は複数のタイルのうちの好ましい処理順序を示す。例えば、「タイル１」は「タイル２」の前に処理され、「タイル２」は「タイル３」の前に処理されるという具合である。さらに、各タイルは次に説明するように決定された近接のタイルと所定のオーバラップ域２００と２０１を有している。
【００２１】
一般的に、ＤＷＴの第２レベルにおいてサブバンドのＨラインを生成するために、Daubechies  ９／７ＤＷＴフィルタを使用して、ＬＬ１サブバンドの（２Ｈ＋７）ラインが必要で、次に、これには画像の｛２（２Ｈ＋７）＋７＝４Ｈ＋１４＋７｝ラインが必要である。２Ｈラインに７ラインを付加することは、Daubechies  ９／７ＤＷＴフィルタによって必要とされ、このことが「オーバラップ」２００として表されている。好適には、このオーバラップは、処理されるべき２Ｈラインの前３ラインと、処理されるべき２Ｈラインの後４ラインとして分布されることである。
【００２２】
数学的帰納法によれば、一つの次元において、いずれかのサブバンドのＨラインを形成してレベルＪにするには、
２J Ｈ＋（２J-1 ・・＋２1 ＋２0 ）・７＝２J Ｈ＋７（２J −１）  式１
の画像ラインが必要である。上式の第２項が必要とされるオーバラップである。もちろん、これは他の次元に対しても同様に適用される。例えば、Daubechies ９／７フィルタを使用する４レベル分解（Ｊ＝４）と、３２画素幅（水平方向）Ｗ＝３２のブロックを蓄積するためには、式１によれば（１６×３２＋７×１５＝５１２＋１０５）幅のタイルを必要とし、ここでオーバラップ２００は、１０５画素である。すなわち、図２中の「タイル１」と「タイル１１」間のオーバラップ２００は、水平方向の１０５画素に垂直方向の７１画素（２Ｈ＋７）を掛けたものである。
【００２３】
本実施の形態では、一度に２Ｈ＋７ラインを変換し、大きくなるラベル番号順に次の（オーバラップした）タイルを処理して、ＨＬ１、ＬＨ１およびＨＨ１サブバンドの各々からＨラインを生成する。これらのサブバンド部分は、このような画素（Ｈライン倍した）Ｗ（この例ではＷ＝３２画素）、すなわち、２Ｈ画素列が入力されると、上述した場合のように、直ちにコード化できる。タイルの第１パス（すなわち、一つの分解レベルにおける一つのタイル）の処理の終了時点において、ＬＬ１サブバンドの１ライン当たり｛２J-1 Ｗ＋７（２J-1 −１）｝倍したＨラインをバッファする必要がある。ＬＬ１サブバンドの１ライン当たりのこの係数値は、トップ・レベル（レベルＪ）におけるＷ幅ブロックを形成するために必要である。図２において、タイル「タイル１」が処理された後、「タイル２」がほぼ同様にして処理される。すなわち、画像の他の｛（２Ｈ＋７）×（２ＪＷ＋７（２J −１））｝画素のタイルが処理される。ここで、「タイル２」が処理されると、ＬＬ１サブバンドの他のＨラインが発生され、二つのタイルが処理された後、合計２Ｈラインとなる。ＬＬ１サブバンドをさらに分解してＬＬ２サブバンドのＨラインを生成するためには、ＬＬ１サブバンドの（２Ｈ＋７）ラインが必要である。「タイル２」の処理後には、２Ｈラインが生成され、「タイル３」の処理後は、（２Ｈ＋７）ラインを提供するための合計３Ｈを提供できる。これにより次のレベルの分解を実行してＬＬ２サブバンドのＨラインを生成する。即ち、各タイル毎にＤＷＴを行い、ＬＬ１を生成するが、次のＬＬ２を生成するために３つのタイルのＬＬ１を用いて更にＤＷＴを実行する。この方法によれば、小さいタイル単位（小さいバッファ容量）で２レベルのＤＷＴが実行できる。同様にして、この方法を続行して少なくとも｛２J Ｈ＋７（２J −１）｝ラインを処理すると、分解のＪ番目のレベルにおける係数のＨラインを生成することになる。即ち、レベル３（ＬＬ３）以降のＬＬｎの作成のためにも、そのＬＬｎの作成に必要な複数タイル分のＬＬ（ｎ−１）を利用することにより、ＨラインのＬＬｊを最終的に生成する。ラインが｛２J-1 Ｗ＋７（２J-1 −１）｝画素（またはＤＷＴ係数の長さ）であり、画像の幅または長さを必要としないことに注意されたい。次のレベルの分解を得るために各々の繰り返しにおいて、ＬＬ周波数のサブバンドの合成係数がバッファされ、他方で現在レベルにおいて発生されたより高い周波数（すなわち、ＬＨ、ＨＬ、ＨＨ）の各Ｈ×Ｗブロックが符号化のためにエントロピー符号化器に送られる。
【００２４】
普通、出力デバイスおよび特に表示デバイスは、ラスタ走査順に、左から右へ、また、上から下へ画像を表示する。従って、本実施の形態の好ましい実施においては、図３に示したタイル配列となる。オーバラップするタイルは、タイルの最短次元が画像の走査ラインと平行になるように配列されるのが好ましい。好ましくは、タイルはタイルの次の列が処理される前に、画像の幅を横切って処理される。この配列は、タイルが左から右へ、また上から下へ（すなわち、ラスタ走査タイプ順）に処理できるので好ましいが、他の順序も本発明の範囲と概念から外れることなしに使用することができる。例えば、図２のタイル配列は図３のものとは別の配列である。
【００２５】
図３の配列において、各タイルはサイズ（２J Ｈ＋７（２J −１））×（２Ｗ＋７）画素であり、ラスタ走査順で処理される。Ｊ＝４レベルＤＷＴ分解に対し、またエントロピー符号化のためにＨ＝３２×Ｗ＝３２係数ブロックサイズを得るために、画像の各タイルは、１タイルのライン当たり次元（５１２＋１０５＝６１７ライン）×（２×３２＋７＝７１係数（または画素））を有している。
【００２６】
図４を参照すると、図４はエンコーダ（符号化器）４００のブロック図を示し、非圧縮画像４０１を取り入れて、画像を表す圧縮ビットストリーム４０２を生成する。このエンコーダ４００は、所定量の外部メモリ４０３、好ましくはダイナミック・ランダム・アクセス・メモリＤＲＡＭと、それ自体所定量の内部メモリ４０５、一般的にはスタテッィク・アクセス・メモリＳＲＡＭを含む圧縮エンジン４０４とを備えている。このエンコーダ４００と、特に圧縮エンジン４０４は必要とされる工程を実行し、非圧縮画像４０１から圧縮画像ビットストリーム４０２を生成し、リニア変換（ＤＷＴ）の実行と、その変換係数をエントロピー符号化するエントロピー符号化器を含んでいる。さらに、圧縮エンジン４０４は単一チップとして設けられ、そのチップを通してマスター画素クロック信号clk を使用するのが好ましい。
【００２７】
非圧縮画像４０１は、エンコーダ４００の外部ＤＲＡＭによりバッファリングされ、かつ、圧縮エンジン４０４によって制御される。外部ＤＲＡＭは、これまでに説明したタイル（６１７×７１画素又は係数）に略対応する非圧縮画像の一部をバッファするのに使用されるのが好ましい。圧縮エンジン４０４は、各ラインに沿った７１画素または係数に対応するデータの短いバーストを読み取り、タイルをジグザグ順に上から下に走査する。
【００２８】
図５はジグザグ順５００を示し、この順に各タイルが走査され、図３の配列よりも詳しいイラストを画像５０２の部分で示す。これまでに説明したように、タイルの幅は（２Ｗ＋７）であり、Ｗ＝３２を所望のブロック幅とすると、タイル幅（またはタイル内のラインの長さ）は７１画素（すなわち、６４＋７、７は水平方向のオーバラップ２０１）となる。従って、圧縮エンジン４０４は、６１７ライン、すなわち、Ｈ＝３２としたとき、（２J Ｈ＋７（２J −１））ラインが読み取られるまで、同時にジグザグ順で走査されてタイルの１本のラインを一つ読み取るのが好ましい。すなわち、前回の説明部分は、近接するタイル間のオーバラップ域２００の垂直方向の寸法を構成している。例えば、四つのレベルＤＷＴに対し、オーバラップ域２００は、タイルの長さ方向における１０５画素に幅（７１画素）を掛けたのものである。より高い周波数要素（ＬＨ、ＨＬ、ＨＨ）の各３２×３２（Ｈ×Ｗ）変換ブロックが発生されると、このブロックは中間バッファリングなしにエントロピー符号化される。したがって、好ましい実施の形態において、水平方向における二つの近接するタイル（例えば、「タイル１」と「タイル２」）間のオーバラップ域２０１は、略７画素幅にタイルの長さを掛けたもので、垂直方向の二つの近接するタイル（例えば、「タイル１」と「タイルｉ」）間のオーバラップ域２００は、略１０５画素長さにタイルの幅を掛けたものである。
次に図６は、図４の圧縮エンジン４０４をより詳細に示す。圧縮エンジン４０４は：アドレス・バス６０３を介してＤＲＡＭに伝送されるメモリ・アドレスに応答して、外部ＤＲＡＭ４０３からの６０２データを受取るリオーダ（再配列）・バッファ・モジュール６０１と；制御状態マシン・モジュール６０４と；垂直フィルタ６０５と；水平フィルタ・モジュール６０６と；サブバンド・バッファ６０７と；部分バンド・バッファ６０８と；エントロピー符号化ユニット（符号化器）６０９を含んでいる。
【００２９】
リオーダ・バッファ・モジュール６０１は、外部ＤＲＡＭ４０３に対する読み取りと書き込みを制御するとともに、ＤＲＡＭ４０３から受信したデータを組立て、所定順序で垂直フィルタ６０５で読み取りできるようにする。このリオーダ・バッファ・モジュール６０１は９バイト（７２ビット）のデータを一度に、垂直フィルタ・モジュール６０５に送る。垂直フィルタ・モジュール６０５は、第１次元（図３のタイルの垂直方向）で、ロウパスおよびハイパス・フィルタリングを実行する。垂直フィルタ・モジュール６０５からの二つの出力６１１と６１０があり、それぞれデータのロウパスおよびハイパス・フィルタリングに対応している。各出力６１０および６１１は、水平フィルタ・モジュール６０６内の分離水平フィルタにパスされ、ここで同一のフィルタ操作が第２次元（図３のタイルの水平方向）において実行される。水平フィルタ・モジュール６０６は、ＬＬ、ＬＨ、ＨＬおよびＨＨサブバンド信号に対応する四つの出力信号を提供する。高い周波数成分（すなわち、ＬＨ、ＨＬおよびＨＨ）を含むサブバンド信号が、エントロピー符号化器６０９によって符号化される前に、サブバンド・バッファ・モジュール６０７内で一時的にバッファされ、６１３に符号化ビットストリームを出力する。ＬＬサブバンド信号が部分バンドバッファ６０８にパスされ、ここで、より大きいブロックに合成され、後続の変換レベルのために垂直フィルタ・モジュール６０５に帰還される。最終レベル（例えば、レベル４）においてのみ、ＬＬサブバンド信号が出力ビットストリーム（出力６１３を介して）に符号化される。制御状態マシン・モジュール６０４が、圧縮エンジン４０４の動作を管理し、適切なデータが正しい場所に記憶されるか、また、その動作が正しい時刻に正しいデータで実行されるかどうかを確認する。
【００３０】
次に図７を参照して、図６のリオーダ・バッファ・モジュール６０１をより詳しく説明する。このリオーダ・バッファ・モジュール６０１は、外部メモリ４０３から受信した中間生データ６０２を記憶するランダム・アクセス・メモリ（以下、リオーダＲＡＭという）７００と、外部ＤＲＡＭサブモジュール４０３を制御するためのＤＲＡＭコントローラを含むリオーダ・アドレス・ジェネレータ・サブモジュール７０１とを含んでいる。data_valid（データ・ヴァリッド）信号７０２は、（生）の画素データ４０１をＤＲＡＭ４０３に供給する外部デバイスから供給される信号であって、ＤＲＡＭデータ・ピン上の現在データが有効であることを示している。data_ack信号７０３は、データがＤＲＡＭ４０３に読み取られたことを確認する。外部ＤＲＡＭ４０３が、その入力を外部画素供給源（図示省略）から直接取り入れる。リオーダ・アドレス・ジェネレータ７０１は、アドレス７０４を決定してリオーダＲＡＭ７００に供給し、そのＲＡＭ７００への書き込みを制御する。
【００３１】
リオーダＲＡＭ７００からのデータ・アウト(Data Out)（ＤＯ）ピンが、同じリオーダＲＡＭ７００のデータ・イン(Data In)（ＤＩ）ピンに、８ビットシフトして接続されている。すなわち、ＤＯ（ｎ＋７：ｎ）ピンがＤＩ（ｎ＋１５：ｎ＋８）ピンに接続され、ここで、ｎは低い方のビット数を表している。例えば、７２ビット・ワード・データ・アウトの少なくとも８個の重要なビットを表すＤＯ（7:0)ピンが、７２ビット・ワード・データ・インの第２の少なくとも８個の重要なビットに対応するＤＩ（15:8) に接続されている。データが、読取−修正−書込（リード・モディファイ）技術を使用してリオーダＲＡＭ７００に書き込まれる。７２ビット・ワード・データ・インの第２の少なくとも８個の重要なビット、すなわち、ＤＩ（7:0)ピンへのバイト入力が外部ＤＲＡＭ４０３から入り(DRAM Data)、一方残りの入力データ・ワードが上述したシフトされた態様でリオーダＲＡＭ７００の出力から入力されている。従って、リオーダＲＡＭ７００は、大きいバイト幅をアドレス可能なシフト・レジスタのように、９ワード深さと７１ワード幅で作動する。データが、画像の走査線（すなわち、タイルのライン）に沿って７１ワードのバースト内で外部ＤＲＡＭから読み取られる。画像データの二つのライン（７１バイト×２）が、垂直フィルタ・モジュール６０５によって使用されるサンプルの各列（ライン）に対してリオーダＲＡＭ７００に書き込まれる。これはＤＷＴによって必要とされる垂直方向内の画像データのダウン・サンプリング（１／２に減らすこと）を構成ないし提供する。
【００３２】
上述したように、リオーダＲＡＭ７００からのリオーダ・データが、ro_data バス７０５を介して、一度に９バイト（７２ビット）が垂直フィルタ・モジュール６０５に供給される。
【００３３】
図８は図７のリオーダ・バッファ６０１の構成を表したものである。好適な実施の形態のリオーダ・バッファ６０１は、７１画素幅と９ラインで構成されている。このバッファ６０１は、図７において矢印８０１で示したように左から右に書かれる。各ラインが左から右に書かれると、１ライン分の画素が一度にライン分プッシュダウンされる。すなわち、バッファの９ラインが書込まれると、（９×７１＝）６３９画素がバッファを占有し、６３９画素の最初（左上）の画素が、バッファの９番目のライン８０４の最初の位置にあるバッファのセル８０２の位置のバッファに入り、一方６３９画素の最後（右下）の画素が最初のライン８０５上のバッファのセル８０３の位置のバッファに入る。メモリ７００（リオーダＲＡＭ）が７２ビットの７１ワードとして編成される。ここで７２ビットは垂直方向のディメンジョン（寸法）である９画素を表している。９ラインが同じ７１アドレスに繰り返して（一度に８ビット）書き込まれると、全バッファ６０１が満たされる。６３９画素の最終７１バイト（画素）がトップ・ラインに書き込まれると、読取−修正−書込サイクル（全７２ビット）が使用されている間、データが読み取られて垂直フィルタ・モジュール６０５にロードされる。一度、リオーダ・バッファ６０１が満たされると、データがバッファ６０１にロードされる画像データのどの第２ラインからでも垂直フィルタ・モジュール６０５によって使用される。これは垂直方向におけるサブ・サンプリングとなる。
【００３４】
垂直方向におけるサブ・サンプリングは次のようにして達成される。最初に、垂直フィルタ・モジュール６０５がリオーダ・バッファの９ラインを処理する。このとき、９タップ・フィルタの内の１番目のタップが、リオーダ・バッファの最終ライン８０５からのデータを使用するようにアレンジされ、一方、フィルタの最終タップがリオーダ・バッファ６０１の第１ライン８０４からのデータを使用して、例えば、部分バンド・バッファ６０８内に記憶されることになるロウ・パス・フィルタされたデータの１ラインを生成する。当然、１番目のタップと最終タップの間のタップは、リオーダ・バッファ６０１の対応するラインからのデータを使用する。次に、リオーダ・バッファ６０１の各ラインのデータはプッシュダウンされ、リオーダ・バッファ６０１の最終ライン８０４は除去され（バッファから押し出され）、各先行ラインからのデータがリオーダ・バッファ６０１の次のラインに書き込まれる。すなわち、バッファの８番目のライン８０６からのデータが、９番目のライン８０４に、また、バッファの７番目のラインからのデータが８番目のライン８０６に書き込まれ、６番目のラインからのデータが７番目のラインにというようにして書き込まれる。リオーダ・バッファ６０１の初頭ライン８０５において、新しいラインデータが外部ＤＲＡＭ４０３から入力される。このプッシュダウンが、リオーダ・バッファ６０１に入力された全てのラインに対して繰り返される。こうして、第２ラインのデータがリオーダ・バッファ６０１に入力された後、垂直方向内のサブ・サンプリングが、リオーダ・バッファの９ラインの読み取りと処理によって実行される。このリオーダ・バッファは、タイルの開始時点で完全に再充填され、全画像が処理されるまで、上述の処理が繰り返される。
【００３５】
画像の略７１ラインが外部メモリ４０３から検索され、かつ、リオーダ・バッファ６０１に伝送された後、サブバンド・バッファ６０７がエンコーディングを開始するための十分な変換係数を含んでいる。好適な実施の形態において、サブバンド・バッファ６０７がいっぱいになり、リオーダ・バッファ６０１がさらに更新される前に、係数が符号化される必要がある。より高いレベルの係数がフィルタリングされている間、次のレベルのフィルタ操作の準備のために、新しいデータがリオーダ・バッファにロードされる。
【００３６】
リオーダ・アドレス・ジェネレータ７０１は、リオーダ・バッファ６０１のために、単純に０から７０までの周期でアドレスを発生するが、読み取り中、図５を参照してこれまでに説明したように、ジグザグに外部ＤＲＡＭ４０３をアドレスする。このリオーダ・アドレス・ジェネレータ７０１は、画像を外部ＤＲＡＭ４０３に書き込み中、ラスタ走査順の制御もする。外部ＤＲＡＭ４０３は、画像の少なくともフルに６１７幅のラインを記憶するのに十分な大きさであるのが好ましい。実際には、十分なバンド幅はデュアル・ポートＤＲＡＭで実現でき、あるいはオプションとして、ビデオ・ランダム・アクセス・メモリ（ＶＲＡＭ）が外部メモリ４０３として使用できる。
【００３７】
図９は図６の垂直フィルタ・モジュール６０５をより詳細に示す図である。この垂直フィルタ・モジュール６０５はマルチプレクサ９０１を備えており、レベル１の分解を実行するときのリオーダ・バッファ６０１からのデータか、又は後続の分解レベル中、部分バンドバッファ６０８からのデータのいずれかを選択する。リオーダ・バッファ６０１から受信されたデータの９バイト×８ビットが１６ビットの９ワードに変換される。これは未使用ビットをゼロにすることによって、部分バンド・バッファ６０８からのデータと一致する。マルチプアレクサ９０１は、制御状態マシン・モジュール６０４によって制御される。一般的に、１画素データ当り８ビットのカラー・チャネルが１６ビットの精密ＤＷＴ係数に変換され、これによって情報の最小量が係数値に対する丸め効果のために失われる。
【００３８】
さらに、垂直フィルタ・モジュール６０５は垂直ロウ・パス・フィルタ９０２と、垂直ハイ・パス・フィルタ９０３を含み、これらはマルチプレクサ９０１の選択に基づいてデータを受信する。垂直ロウ・パス・フィルタ９０２は、９×１６ビットのサンプルを得て、データに対してマトリックス操作（乗算−蓄積）を実行し、入力の全９ワードから１６ビットの結果(vfl_data)を生成する。垂直ハイ・パス・フィルタ９０３は、７×１６ビット・サンプルのみを必要とし、そのマトリックス操作を実行し、再度１６ビットの結果(vfh_data)を生成する。これまでに説明したように、本実施の形態のフィルタはDaubechies ９／７ＤＷＴに基づいているが、他のウエーブレット・フィルタも使用できる。
【００３９】
図１０は、図６の水平フィルタ・モジュール６０６のより詳しい説明図である。この水平フィルタ・モジュール６０６は、垂直フィルタ・モジュール６０５からのデータを処理する二つのほぼ同様のセクション１００４と１００５を含んでいる。各セクションは９ステージ・シフト・レジスタ１００１、水平ロウ・パス・フィルタ１００２および水平ハイパス・フィルタ１００３を含んでいる。データはまず最初に、垂直フィルタ・モジュール６０５から受信された最大９個の連続するサンプルをバッファする、一対の９ステージ・シフト・レジスタを通過して同時に処理される。一方、二つのセクション１００４と１００５はほぼ同じ方法でデータを処理するが、各セクションのためのデータ源は異なる。一つのセクション１００４が、垂直ロウ・パス・フィルタ信号vfl_dataを受取り、一方、他方のセクション１００５が垂直ハイ・パス・フィルタ信号vfh_dataを受取る。
【００４０】
各セクションの水平ロウ・パス・フィルタ１００２が９×１６ビット・サンプルを取り込み、そのデータにマトリックス操作（乗算−蓄積）を実行し、入力の全９ワードの各々の結果から１６ビットを生成し、セクション１００４と１００５それぞれからll_data 信号１００６とhl_data 信号１００７を生成する。各セクションの水平ハイ・パス・フィルタ１００３は７×１６ビット・サンプルのみを必要とし、マトリックス操作を実行し、再度各ハイ・パス・フィルタ１００３が１６ビット結果を生成する。セクション１００４の水平ハイ・パス・フィルタが信号lh_data1１００８を提供し、セクション１００５の水平ハイ・パス・フィルタが信号hh_data １００９を提供する。その結果得られたサブバンド・データ、すなわち、ＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドの係数に対応する信号ll_data、lh_data、 hl_data、およびhh_data 信号がサブバンド・バッファ・モジュール６０７に送られる。
【００４１】
９ワード・サンプルの処理後、両９ステージ・シフト・レジスタがデータを２だけシフトし、水平方向にサブ・サンプリング（１／２に減少）のためにアカウントする。
【００４２】
ＤＷＴ分解の現在レベルにおけるＬＬサブバンドの係数に対応するll_data 信号１００６も、分解の続くレベルのために部分バンド・バッファ・モジュール６０８に送られる。
【００４３】
図６のサブバンド・バッファ・モジュール６０７を図１１により詳しく示す。このサブバンド・バッファ６０７は、ＬＬ、ＬＨ、ＨＬおよびＨＨサブバンドの各々から所定数の係数を記憶する所定数のランダム・アクセス・メモリ（ＲＡＭ）１１０１と；サブバンド・バッファ・アドレス・ジェネレータ・サブモジュール１１０２とマルチプレクサ１１０３を含んでいる。サブバンド・バッファ・アドレス・ジェネレータ・サブモジュール１１０２は、サブバンドＲＡＭ１１０１にアドレスを供給するとともに、制御状態マシン・モジュール６０４の制御下でＲＡＭへの書き込みの制御もする。
【００４４】
マルチプレクサ１１０３は、エントロピー符号化ユニット（エントロピー符号化器）６０９によって符号化するために四つのサブバンドの一つから、データと係数を選択する。
【００４５】
図１２を参照して、図１１のサブバンド・バッファのデータ構成ないし編成の態様を説明する。サブバンド・バッファは、３２×３２個の係数からなる四つのバンク１２０１を保有しており、各係数は１６ビット値で表わされる。従って、サブバンドＲＡＭは合計６４キロビットの容量で、１ワード６４ビットで１０２４ワードで構成されており、各メモリ位置で並行して、各サブバンドからの１つの係数をストアする。即ち、現レベルで、各サブバンドからの１つの係数、計四つの係数が、それぞれ６４ビット・ワードの１６ビットとして表わされる。バッファ１１０１、特に各バンク１２０１が、図１２に示したジグザグ・パターン１２０２によって示された上から下へのラスター操作順に満たされる。エンコーディング中、エントロピー符号化ユニットにおいて、サブバンドＲＡＭ１１０１が４分木(quadtree)方式で読み取りされる。
【００４６】
図１３を参照して、図６のエントロピー符号化ユニット６０９をより詳しく説明する。このエントロピー符号化ユニット６０９は、ビットプレーン・コンバータ・モジュール１３０１と１６個のビットプレーン・メモリを含むビットプレーン・バッファ・サブモジュール１３０２と；複数のビットプレーン・ツリー・ビルダー・ユニット１３０３と対応するビットプレーン・ツリー・バッファ・ユニット１３０４と；ビットプレーン・エンコーダ１３０５と；ビットプレーン・エンコーダ１３０５によって使用されるデータの中間記憶のための複数の中間バッファ１３０６とを備えている。サブバンドＲＡＭ１１０１に記憶されたデータがサブバンド・バッファ・モジュール６０７からクワドトリー順に読み取られる。ビットプレーン・コンバータ・モジュール１３０１は、各ビットプレーンのデータを分離するとともに、ビットプレーン・バッファ・サブモジュール１３０２内の１６個のビットプレーン・メモリの各々に書き込む。データはまた、処理されたビットプレーン・ツリー構造情報を、対応するビットプレーン・ツリー・バッファ１３０４に書き込む複数のビットプレーン・ツリー・ビルダーによって走査される。ビットプレーン・ツリー１３０４とビットプレーン・バッファ１３０２の各々からのデータが、ビットプレーン・エンコーダ１３０５によって使用され、ビットストリームの発生を実行して、これが（バス６１３を介して）出力される。ビットプレーン・エンコーダ１３０５は制御状態マシン・モジュール６０４によって同期化（制御）される。中間バッファ１３０６は、重要な係数のリスト（ＬＳＣ）を一時的に記憶するバッファと；重要でない係数（ＬＩＣ）のリストを一時的に記憶するバッファと；域バッファの第１リストと域バッファの第２リストとしての二つのバッファとして実現できる古い重要でない域（ＯＩＲ）リストを一時的に記憶するバッファ（図１３では不図示）を含んでいる。さらに、エントロピー符号化ユニット６０９は、サイン・ビット・バッファ（図１３では不図示）を含み、これはビットプレーン・コンバータ・モジュール１３０１の出力と、サイン・ビットをビットストリームに符号化するビットプレーン・エンコーダ１３０５とに接続されている。エントロピー符号化ユニットの一例を本明細書中の、見出し「エントロピーエンコーダ」で後ほど詳細に説明する。
【００４７】
本発明の好適な実施の形態を、上述したクワドトリー・ビットプレーン・エンコーディングを実行するエントロピー符号化ユニットを参照して説明するが、他のエントロピー符号化器も本発明の範囲と概念から外れることなく使用することができる。例えば、ビットプレーン演算コーダが変換係数を符号化するのに使用でき、または随意に、一部クワドトリー・エンコーディングとＤＷＴ係数の一部演算コーディングを実行するハイブリッド・エンコーダを使用できる。
【００４８】
図１４を参照して、図６の部分バンド・バッファ・モジュールをより詳しく説明する。部分バンド・バッファ・モジュール６０８は：分解の各レベルに対するＬＬサブバンド・データ（すなわち、図６の水平フィルタ・モジュール６０６によって発生されたll_data１００６) を記憶するＲＡＭ１４０１と；部分バンド・バッファ・アドレス・ジェネレータ・サブモジュール１４０２と、バレル・シフト・レジスタ（バレル・シフター）１４０３とを含んでいる。部分バンド・バッファ・アドレス・ジェネレータ１４０２がアドレスを部分バンドＲＡＭ１４０１に供給するとともに、制御状態マシン・モジュール６０４の制御下で、そのＲＡＭへの書き込みを制御する。
【００４９】
部分バンド・バッファは、十分なサンプルが分解の次のレベルをフィルタするのに利用可能になるまで、圧縮の各レベルからＬＬサブバンド・データを保持する。一旦、十分なサンプルがいずれか一つのレベルにおいて利用可能になると、データがバレル・シフター１４０３を介して垂直フィルタ・モジュール６０５に読み取られ、分解の次のレベルがフィルタされる。概念的に、ＲＡＭ１４０１は三つの別々のバッファを含み、各々１００個のセル幅を有し、各セルは１６ビット値を記憶することができる。これら三つの別個のバッファの内の第１バッファは３０５行(row)（ライン）深さで、第２バッファは１４９行の深さで、第三バッファは７１行の深さであり、総計５２５行（ライン）になる。しかし、垂直フィルタ・モジュール６０５が、Daubechies  ９／７フィルタによって必要とされる９個の値を取るので、行（ライン）の合計は９の倍数であるのが望ましい。従って、余分の６行のセルがバッファに付加され、結果として合計５３１行（すなわち、９の５９倍）になる。本実施の形態において、この結果は少なくとも５９×１００×１４４＝５３１×１００×１６ビット、すなわち、約０．８１メガバイトのメモリ・サイズになる。
【００５０】
バレル・シフト・レジスタ１４０３が、データの単一クロック・アライメントを垂直フィルタ・モジュール６０５によって必要とされる所望の行にすることを許容する。部分バンドＲＡＭ１４０１から読み取って垂直フィルタ６０５のための単一ワードを生成するために所定のメモリ位置が必要となる。必要とされる単一ワードが９ラインの境界線に沿って包括される場合、二つの近接するメモリ位置が読み取られる必要がある。これは一般的に、９ライン・セット（各セットは９ラインからなる）の内８本に発生する。この場合、データは、両ワードが読み取りされ、全ての必要とされるビットが利用可能、かつ、適切に配置されるまで、バレル・シフター１４０３内にラッチされる。
【００５１】
図１５を参照して、部分バンド・バッファ６０８のデータ編成の態様を説明する。部分バンド・バッファ６０８は、１００係数幅と５２５係数高さと、上述したように、これに１００係数幅の行（図１５では不図示）につき、余分の６を加えたのもである。部分バンド・バッファ６０８は、タイルの少なくとも一つのレベルＤＷＴ分解が実行された後、データ（係数）に書き込まれる。従って、分解の１レベル後で、画像のタイル（２J Ｈ＋７（２J −１））×（２Ｗ＋７）が、係数のタイルを少なくする。すなわち、分解の第１レベルが３０５×３２係数のタイルまで少なくなった後、６１７×７１画素タイルになる。好適な実施の形態の部分バンド・バッファ６０８は、１００係数幅において、少なくとも幅方向に三つの３２係数幅タイル１５０１と４係数幅ブロック１５０２を収容するように設計される。各３２係数幅のタイルが、図１５に示すように一度に１レベルで、左から右に、また、上から下の走査ライン順に書き込みされる。すなわち、第２レベル分解（各々、長さ２５６＋４９＝３０５係数）のための三つの３２係数幅のタイル１５０１が、各々ジグザグ順に満たされる。４係数幅のブロック１５０２が、少なくとも最初のタイル処理のために、最初の３２係数幅タイル１５０１（以後、「パッディング(padding)」ないし「パッデッド(padded)」という）の係数の最初の４カラムの鏡像で満たされる。このパッディングは普通、画素境界線外の画素データが存在しない画像の境界線のためにアカウントするように実行される。他のパッディング技術が、画像境界線のためにアカウントするのに利用できる。例えば、最も簡単な、しかしベストである必要はない、オプションが、画像の境界線をゼロ（０）でパッドするものである。
【００５２】
第２レベルの分解のための係数が、垂直フィルタ６０５と水平フィルタ６０６モジュールを介して処理されると、第三レベルの分解のための係数が、次のレベルの３２係数幅のタイル１５０４と長さ方向（１２８＋２１＝）１４９係数に蓄積される。再度、最初に４係数幅ブロック１５０３が対応する（近接）タイル１５０４の係数でパッドされる。第三レベル分解の係数が垂直フィルタ６０５と水平フィルタ６０６モジュールを介して処理されると、４レベル分解のための係数が次のレベル３２係数幅のタイル１５０６に蓄積される。再度、最初に４係数幅のブロック１５０５が、対応する（近接）タイル１５０６の係数でパッドされる。画像の境界線において、４係数幅・ブロック１５０２、１５０３および１５０５がパッドされるべきとき以外の場合において、４係数幅ブロックが先行タイルの最終４カラムを含み、このレベルで処理される。
【００５３】
各レベルにおいて４係数幅ブロックが、水平線をフィルタするためのオーバラップとして使用される。１レベルにおいて、一つの完全な３２係数幅タイルを発生するために、先行レベルにおいて７１係数幅が必要である。第２レベルの分解のための３０５×７１係数からなる図１５の隠れたエリア１５０７には、第三レベルの分解のための１４９×３２のタイルを発生することが要求される。この隠れたエリア１５０７内の係数は、走査ライン順に，１ラインの左から右へ７１カラム分、また上から下へ本読み取られる。一度、部分バンド・バッファ６０８が次の（高い）レベルで所望の量（例えば７１カラム）まで満たされると、現在レベルにおけるカラム・アドレスが６４カラムだけ右に増大し、アドレスが１００番目のカラムを越えると第１カラムを包み込む。これは、例えば、現在レベルにおいて、係数の次の７１カラムの処理が、バッファ６０８の６４番目のカラム１５０８で開始され、バッファ６０８の第１カラムの近くまで包み込まれる。カラム６４からカラム６８までが、ここで４係数幅ブロック１５０９のオーバラップの必要性を提供し、データのもう一つの７１カラムを処理する必要がある。
【００５４】
部分バンド・バッファ６０８の各レベルがフィルタされると、フィルタ（ＬＬサブバンド・係数）の結果が、図１５に示した部分バンド・バッファ６０８の次の高いレベルに書き込まれる。最も高いレベルがフィルタされてしまうと（例えば、図１５の「レベル４」）、得られたＬＬサブバンド・係数が、これらの係数を部分バンド・バッファ６０８にさらに書き込みせずに、サブバンド・バッファ６０７に書き込み、さらにフィルタせずにストレートに符号化される。
【００５５】
部分バンド・バッファの読み取りの際に、９×１６＝１４４ビットが一度に読み取られる。これらの９ワードはバッファの単一カラムからの９個の垂直係数を表している。このバッファから完全に読み取られるライン間で、ライン・アドレスが２だけ増大するので、１４４ビットストリームがバレル・シフタを通り、このデータと垂直フィルタへのデータ・バスに整列される必要がある。さらに、続いて２ワードを読み取り、一つの１４４ビット・ワードを得て、レジスタ内に第１ワードの必要とするビットを保持することによってワードの二つの部分を構築し、他方で第２アクセスから必要とされるビットがフェッチされる。ライン・アドレスの一致が９の倍数であるときのみ、一つのフェッチだけが必要である。一度に１４４ビットをフェッチできるようにするために、メモリは物理的に１４４ビット幅にしなければならない。余分なデコーディングが、メモリ・アレイに書き込み可能な形態にする必要がある（従って、ちょうど１６ビットが同時に書き込みできるようにする）。
【００５６】
図１６は、図６の制御状態マシン・モジュール６０４のための流れ図を示す。この制御状態マシン・モジュール６０４は、各モジュール６０１、６０４〜６０９の機能を制御すること、およびデータを各モジュールにモジュール機能と同期させて（すなわち、正確な時間で）正しくルーティング（経路指示）する。
【００５７】
画像圧縮の開始１６０１において、「レベル」変数が１６０２で１に設定される。これは一般的に実行されるべき分解の第１レベルを表している。決定ブロック１６０３は、ＤＷＴ分解の現在レベルが第１レベルにあるかどうかを判定する工程に入る。この決定ブロック１６０３が真（ＹＥＳ）の返答であれば、ＤＲＡＭ（図４）に記憶された画像の最初の９ラインがフィルタされ（１６０４）、サブバンド・データの第１ラインが生成される。入力データがレベル１のために外部ＤＲＡＭ４０３から取り出される。そうでなければ、決定ブロック１６０３が、偽（ＮＯ）の返答をし、ブロック１６０５にこれを送って、ここでデータが内部部分バンド・バッファ６０８から取り出され、フィルタ（次のレベルにＤＷＴ分解）される。十分なデータが部分バンド・バッファ６０８から取り出され、次のレベルのＤＷＴ係数のタイル内のラインを生成する。これらの結果はこれまでに説明したように対応するレベルのためのロケーションの部分バンド・バッファ６０８に記憶される。
【００５８】
データの７１ラインがフィルタされた後、サブバンド・バッファ６０７の３２ラインがいっぱいにされる。この時点において、流れ図１６００はサブバンド・バッファ６０７がいっぱいであるかどうかをチェックする。このチェック１６０６が偽（ＮＯ）の返答をすれば、処理流れは決定ブロック１６０３に戻り、決定ブロック１６０３を参照して上述した処理を続行する。チェック・ブロック１６０６が真（ＹＥＳ）を返答すれば、さらなる決定（ないしチェック）ブロック１６０７に進み、データがフィルタされるべきレベルのためのオーバラップ域内にあるかどうかがチェックされる。この域になければ、ブロック１６０７が偽（ＮＯ）を返答し、サブバンド・バッファ６０７内に記憶された三つのサブバンドＬＨ、ＨＬおよびＨＨが符号化される（１６０８）。これら三つのサブバンドのエンコーディングに続いて、決定ブロック１６０９に進み、分解の現在レベルが最大レベル（すなわち、レベル４）であるかどうかがチェックされる。現在レベルが４であれば、決定ブロック１６０９が真（ＹＥＳ）を返答し、サブバンド・バッファ６０７内のＬＬサブバンドも符号化され（１６１０）、流れ処理が決定ブロック１６１１において続行される。さらに、決定ブロック１６０９において、偽（ＮＯ）が返答されれば、サブバンド・バッファ６０７内のＬＬサブバンドが符号化されずに、流れ処理が決定ブロック１６１１で続行される。
【００５９】
決定ブロック１６０７を介して、ブロック１６１１への他のエントリがあり、ここで決定ブロック１６０７が真（ＹＥＳ）を返答してくる、即ち、処理されるべきデータが、近接するタイルのオーバラップ域２０１または２００内にある場合にブロック１６１１に進む。この決定ブロック１６０７において実行されたチェックは、オーバラップ域の符号化を二度することを回避するためで、決定ブロック１６０７が真（ＹＥＳ）を返答したときに、決定ブロック１６１１に進行する。
【００６０】
決定ブロック１６１１において、部分バンド・バッファ６０８（図６）のレベル２において、（２５６＋１０５）行で７１カラムの完全な係数のセットを有しているかどうかがチェックされる。もしそうであれば、「レベル」変数が１６１２で２にセットされ、処理が決定ブロック１６０３において再開され、上述したように工程１６０５から１６１１までが続行される。
【００６１】
レベル２で部分バンド・バッファがまだ一杯にされていなければ、即ち、完全なセット（すなわち、７１×３６１係数からなるレベル２）が部分バンド・バッファ６０８になければ、偽が決定ブロック１６１１によって戻され、チェック（決定）ブロック１６１３に進む。チェック・ブロック１６１３が、部分バンド・バッファのレベル３において、（１２８＋２１）行の７１カラムの完全な係数セットが存在するかどうかをチェックする。もしそうであれば、「レベル」変数が１６１４で３にセットされ、処理が決定ブロック１６０３で再開され、部分バンド・バッファ６０８のレベル３から回収されたデータで、上述したように工程１６０５から１６１３が続行される。
【００６２】
レベル３で部分バンド・バッファがまだ一杯にされていなければ、即ち、完全なセット（即ち、７１×１４９係数からなるレベル３）が部分バンド・バッファ６０８になければ、偽が決定ブロック１６１３によって戻され、チェック（決定）ブロック１６１５に進む。チェック・ブロック１６１５が、部分バンド・バッファのレベル４において、（６４＋７）行の７１カラムの完全な係数のセットが存在するかどうかをチェックする。もしそうであれば、「レベル」変数が１６１６で４にセットされ、処理が決定ブロック１６０３で再開され、部分バンド・バッファ６０８のレベル４から回収されたデータで、上述したように工程１６０５から１６１５が続行される。
【００６３】
レベル４で部分バンド・バッファがまだ一杯にされておらず、従って、偽（ＮＯ）が決定ブロック１６１５によって返答されると、チェック（決定）ブロック１６１７に進む。ブロック１６１７において、全画像が完全に処理されたかどうかがチェックされる。この場合に、決定ブロック１６１７が真（ＹＥＳ）を返答し、流れ処理が終了する（１６１８）。そうでなければ、決定ブロック１６１７が偽（ＮＯ）を返答し、処理がブロック１６０２で再開され、「レベル」変数に１を割り当てて、上述したように工程１６０２から１６１７が再度、外部ＤＲＡＭ４０３から取り出されたデータに対して処理が続行される。
【００６４】
説明した実施の形態において、９本のソース・ラインが係数の第１ラインを発生するのに必要とし、一方、２本のソース・ラインが次のおよび係数の各続くラインを発生するのに必要となる。７１画素（または係数）の最小７１ラインが３２係数の３２ラインを形成する必要がある。部分バンド・バッファ６０８が、次のレベルを処理するために、係数の三つのタイルを最初にロードする。次のレベルにおいて発生されるべき全ての連続するタイルに対して、入力の二つの付加的なタイルのみが必要である。これは部分バンド・バッファ６０８が既に前回のロード・データから少なくとも一つのタイルを含んでいるからである。本実施の形態において、７１カラムの係数が必要であり、部分バンド・バッファにおいて、現在レベルのために次のレベルフィルタする必要がある。すなわち、フィルタ操作は前回処理されたタイルから４カラムの係数で開始され、二つの付加的（完全な）タイル（各々３２カラム）と、７１カラムのタイルを形成するのに処理されるべき次のタイルからの３カラムとを使用する。随意に、部分バンド・バッファ６０８は、図１５に示したような単一のバッファ・メモリとしてバッファ６０８を設けるのではなく、分解の各レベルの一つに対する三つの分離メモリ・ユニットとして設けることができる。このオプションは分離した読取・書込アドレス・ジェネレータを必要とする。
【００６５】
デジタル画像を符号化する方法は、図１７に示したような従来の汎用コンピュータ・システム１７００を使用して実行でき、例えば、図２、３および５に関する処理が、コンピュータ・システム１７００内に存在するアプリケーション・プログラムのようなソフトウエアとして備えることができる。特に、デジタル画像を符号化する方法中の工程は、コンピュータによって実行されるソフトウエア内の命令によって実行される。このソフトウエアは二つのパーツに分割することができ、その一つはエンコーディング方法を実行し、他の一つは後者とユーザ間のユーザ・インターフェイスを管理する。ソフトウエアはコンピュータ読取可能媒体内に記憶することができ、例えば次に説明する記憶デバイスを含んでいる。このソフトウエアは、コンピュータ読取可能媒体からコンピュータにロードされ、コンピュータによって実行される。この種のソフトウエア、またはこれに記憶されたコンピュータ・プログラムを有するコンピュータ読取可能媒体は、コンピュータ・プログラム製品である。コンピュータ内のコンピュータ・プログラム製品を使用すると、本発明の実施の形態に基づくデジタル画像を符号化するための装置が好適に実行される。
【００６６】
コンピュータ・システム１７００は、コンピュータ・モジュール１７０１、キーボード１７０２およびマウス１７０３のような入力デバイス、プリンタ１７１５および表示デバイス１７１４を含む出力デバイスを備えている。モジュレータ−デモジュレータ（モデム）受信デバイス１７１６が、例えば、電話回線１７２１または他の機能媒体を介して接続可能な通信ネットワーク１７２０間を相互連絡するコンピュータ・モジュール１７０１によって使用される。モデム１７１６はインターネット、および、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）のような他のネットワーク・システムへのアクセスを得るのに使用することも可能である。
【００６７】
コンピュータ・モジュール１７０１は、一般的に、少なくとも一つのプロセッサ・ユニット１７０５と、、例えば、半導体ランダム・アクセス・メモリ（ＲＡＭ）とリード・オンリ・メモリ（ＲＯＭ）から形成されたメモリ・ユニット１７０６と、ビデオ・インターフェイス１７０７を含む入力／出力（Ｉ／Ｏ）インターフェイスと、キーボード１７０２とマウス１７０３およびオプションとしてジョイステック（図示省略）のためのＩ／Ｏインターフェイス１７１３と、モデム１７１６のためのインターフェイス１７０８とを備えている。記憶デバイス１７０９を備えており、一般的にハードディスク・ドライブ１７１０とフロッピー・ディスク１７１１を含んでいる。磁気テープ・ドライブ（図示省略）も使用できる。ＣＤ−ＲＯＭドライブ１７１２が、一般的にデータの不揮発性ソースとして備えられている。コンピュータ・モジュール１７０１の要素１７０５から１７１３は、一般的に相互連結バス１７０４を介して、当該技術において知られているコンピュータ・システム１７００の従来操作モードとなる方法で連絡されている。実施の形態を実行できるコンピュータの例としては、ＩＢＭ−ＰＣおよび互換性のあるサン・スパークステーションまたはこれから発展されたこれと同様のコンピュータ・システムが含まれる。
【００６８】
一般的に、好適な実施の形態のアプリケーション・プログラムは、ハードディスク・ドライブ１７１０に存在し、プロセッサ１７０５によるその実行が読み取られるとともに制御される。プログラムの中間記憶およびネットワーク１７２０からくるどのデータも、多分ハードディスク・ドライブ１７１０と提携して半導体メモリ１７０６を使用して達成される。ある例において、アプリケーション・プログラムは、ユーザに提供され、ＣＤ−ＲＯＭまたはフロッピー・ディスクに符号化され、対応するドライブ１７１２または１７１１を介して読み取られるか、或いは別の方法として、モデム・デバイス１７１６を介してネットワーク１７２０からユーザによって読み取ることもできる。さらに、ソフトウエアも他のコンピュータ読取可能媒体からコンピュータ・システム１７００にロードできる。この媒体には磁気テープ、ＲＯＭまたは集積回路、磁気−光学ディスク、コンピュータ・モジュール１７０１と他のデバイス間の無線または赤外線伝送チャネルと、ＰＣＭＣＩＡカードのようなコンピュータ読取可能カード、およびインターネットと、Ｅメール伝送とウエブサイトに記憶された情報を含むイントラネット等々を含む。上述のものはコンピュータ読取可能媒体の単なる例である。他のコンピュータ読取可能媒体も、本発明の範囲と概念から外れることなく実行できる。
【００６９】
デジタル画像を符号化する方法は、別の方法としてデジタル画像を符号化する機能、又はサブ・ファンクションを実行する一つまたはそれ以上の集積回路のような専用ハードウエア内で実行できるのが好ましい。この種の専用ハードウエアにはグラフィック・プロセッサ、デジタル・プロセッサ、あるいは一つのまたはそれ以上のマイクロプロセッサおよび関連するメモリを含む。
［エントロピー符号化器（エンコーダ）］
デジタル画像のコード化表現を発生するためのエンコーダを次に説明する。
【００７０】
画像の変換係数のコード化表現を生成するための方法を説明する。特に、この方法はクワドツリー（４分木）を使用する埋め込みブロック・コーディングに関する。
【００７１】
この方法は画像データのウエーブレット変換により最初に処理される。ウエーブレット処理の概観を添付図面を参照して次に説明する。
【００７２】
図１８を最初に参照して、元の画像１８０１が離散ウエーブレット変換(DWT) を使用して四つのサブ画像１８０３乃至１８０６に変換される。このサブ画像ないしサブバンドは、通常ＬＬ１、ＨＬ１、ＨＬ１およびＨＨ１で示される。サブバンド名に付いている１の添え字はレベル１を示している。ＬＬ１サブバンドは、元の画像のロウパス・デシメート・変形である。
【００７３】
ここで使用されるウエーブレット変換は、例えばハール(Haar)基本ファンクション、Daubechies基本ファンクション等で変形でき、またこれを含めることができる。ＬＬ１サブバンドは次に使用され、第２離散ウエーブレット変換が図１９に示したように適用され、サブバンドＬＬ２（１９０８）、ＨＬ２（１９０９）、ＬＨ２（１９１０）、ＨＨ２（１９１１）で示される。この処理は例えば図２０に示したように続行され、ここにはＬＬ４サブバンドが示されている。明らかに、分解の第四レベルは入力画像のサイズに依存して提供できる。最も低い周波数のサブバンドはＤＣサブバンドに該当される。図２０の場合には、ＤＣサブバンドはＬＬ４サブバンドである。
【００７４】
次に、各単一レベルＤＷＴは、元の画像を得るように順次変換される。従って、Ｊ−レベルＤＷＴは一連のＪ単一レベルの逆ＤＷＴに逆変換できる。
【００７５】
階層的に画像をコード化するために、ＤＣサブバンドが最初にコード化される。こうして、残りのサブバンドがレベルを小さくする順にコード化される。これは４レベルＤＷＴに対してであり、レベル４のサブバンドはＤＣサブバンド（ＬＬ４）の後にコード化される。すなわち、ＨＬ４、ＬＨ４およびＨＨ４サブバンドである。レベル３（ＨＬ３、ＬＨ３およびＨＨ３）のサブバンドが次にコード化され、これに続いてレベル２（ＨＬ２、ＬＨ２およびＨＨ２）が、次にレベル１（ＨＬ１、ＬＨ１およびＨＨ１）がコード化される。
【００７６】
標準画像では、符号化化サブバンドは通常、画像中に「詳細」情報を含んでいる。量子化後のサブバンドは、しばしば値が希薄なアレイになり、実質的な圧縮がその希薄なマトリックス形態の有効なエンコーディングによって達成される。
【００７７】
ここで図２１を参照して、ＨＨ１のようなサブバンドのタイリングを示す。このサブバンドは、左上のコーナーから始まる３２×３２ブロックの係数を有するタイル２１１０、２１２０、２１３０、２１４０および２１５０であるのが好ましい。３２×３２なる用語は、それぞれ３２の行(row)、×３２列(column)を意味している。
【００７８】
以下の実施の形態の説明を進める前に、以後に使用する技術用語につき簡単に説明する。２進整数を表す数に対して、「ビットｎ」または「ビット数ｎ」は、２進数ｎに該当し、例えば、８ビットの２進表現を仮定すると、１０進数の９は、00001001として表される。この数において、ビット３は１に等しく、ビット２、１および０はそれぞれ０、０、１に等しい。さらに、画像の変換は、ビット・シーケンスによって表された各係数による横列と縦列に配列された係数を有するマトリックスとして表すことができる。結果的に、マトリックスについて話すと、三つのディメンジョン（次元）を有していると考えることができ、一番目のディメンジョンは横方向、二番目は縦方向、三番目はビットのシーケンス方向である。同じビット番号で各ビット・シーケンスを通っているこの三つのディメンジョン（３次元）空間内の平面は、「ビットプレーン」または「ビットプレーン」と呼ばれる。用語「ビットプレーン数ｎ」は、ビット番号ｎを通るビットプレーンを意味する。
【００７９】
説明を簡潔にするために、変換係数は、以後、固定小数点で符号のない２進整数フォーマットに、付加的な単一サイン・ビットを付して表す。すなわち、１０進数の−９および９は、同じビット・シーケンス、すなわち、１００１で表し、前者は負数を示す１に等しいサイン・ビットを有し、後者は正数を表す０に等しいサイン・ビットを有する。整数表示を使用することにおいて、係数は最も近い整数値に既に暗黙のうちに量子化されているが、これは必要ではない。さらに、圧縮の目的で、端数ビットに含まれるどの情報も通常無視される。
【００８０】
画像フレームの域は、一連の隣接する画像係数を含んでいる。用語「係数」は、以後「画素」と交換可能に使用されるが、当該技術に習熟した人にとってよく理解される点では、前者が変換ドメイン（例えば、ＤＷＴドメイン）中で画素という意味で使用されるのが一般的である。これらのセットないし域Ｔは、（ｉ，ｊ）を係数座標としたとき、変換画像係数｛ｃi,j ｝を有するのもとして規定され、固定小数点でサインのない２進整数フォーマットに付加的な単一サイン・ビットを付して表わされる。
【００８１】
現在ビットプレーンにおける画素のセット或いは域Ｔは、域中の各係数のＭＳＢの数が現在のビットプレーンの値より小さい場合、重要ではないと言える。域の意味の概念を正確にするために、数学的規定が式（１）で与えられる。画素のセット或いは域Ｔは、次式であれば、ビットプレーンｎに関して（またはこれにおいて）重要でないと言える。
｜ci,j｜＜２ｎ，全ての ci,j∈T に対して      （１）
座標の集合類別Ｔにより、次の部分集合Ｔのコレクション｛Ｔm｝を定める。
【００８２】
【数１】
0004532653.tif 000002
【００８３】
換言すれば、一つのci,j∈T 、従ってci,j∈Tmは、ただ一つの部分集合Ｔm である。本件のＴは正方域であり、集合｛Ｔm ｝は、Ｔの４象限からなる集合（セット）である。
【００８４】
提案された方法は、４分木を使用して埋め込み方法で一連の係数を符号化する。用語「埋め込み」の使用は、より低いビットプレーンでいずれかのビットをコード化する前に、より高いビットプレーン中の全てのビットをコード化することを意味している。次に、ビットプレーン６のいずれかのビットがコード化される前に、ビットプレーン７の各ビットがコード化され、順番に、ビットプレーン５のいずれかのビットがコード化される前に、ビットプレーン６の全ビットがコード化されるという順にコード化される。
【００８５】
提案された方法の好適な実施の形態は、次の疑似コードを使用して実行される。この提案された方法は、係数の正方ブロックを符号化するのが好ましく、ブロックのサイズは２の累乗（一般的に３２×３２の係数）したものである。更に、この提案方法は４分木類別を使用している。すなわち、各セット（集合）或いは域は、その四つの象限に類別され、これによって、常時２の累乗に等しいディメンジョンで正方域が維持される。開始時に、提案方法は三つのリストを初期化する。すなわち、重要でない域（有効数字でない部分）（ＬＩＲ）のリストと；重要でない係数のリスト（ＬＩＣ）と；重要な（有効数字部分）係数のリスト（ＬＳＣ）である。単一の係数が、係数の重要性に依存して、重要でないセットのリスト（ＬＩＲ）から除去されると、これらのセットは、重要でない係数のリスト（ＬＩＣ）か、重要な係数のリスト（ＬＳＣ）のいずれかに付加される。
【００８６】
この提案方法は次のように初期化される。ＬＩＣおよびＬＳＣは空になるように初期化される。ＬＩＲは入力ブロックの４象限を包含するセット（集合）である。この方法はｎmax を見つけて、コード化することによって開始され、ここでｎmax はセット内の全ての係数に対して１ビットを含む最大のビットプレーンである。従って、この提案方法は次のようにして進行される：
１．  ｎ＝ｎmax に設定
２．  重要でない係数のリスト（ＬＩＣ）中の各係数に対し、
・  係数のコード・ビットｎ（すなわち、その重要度（有効数字）
・  ビットが１（即ち、重要である場合）、サイン・ビットにコード化される。係数をＬＳＣの最後に付加され、ＬＩＣから係数が除去される。
【００８７】
３．  重要でない域のリスト（ＬＩＲ）中の各域Ｔに対し、
・  重要なＴ（シグニフィカンス）をコード化。
【００８８】
・  Ｔが重要（有効数）であり、一つより多い係数から構成され、従って、Ｔがその４象限に仕切られ、それらがＬＩＲの最後に付加される。Ｔがリストから除去される。
【００８９】
・Ｔが単一係数であれば、
・ＴがＬＩＲから除去される。
【００９０】
・Ｔが有効数であれば、サイン・ビットがコード化され、ＴがＬＳＣの最後に付加される。
【００９１】
・他に、ＴをＬＩＣのリストの最後に付加する。
【００９２】
４．  重要な係数ＬＳＣ（ステップ３中のリストに付加されたものを除く）のリスト中の各係数ｃi,j に対し、
・ｃi,j のビットｎをコード化、
５．  ｎを小さくして、ステップ２に進む。
【００９３】
上述のことから、出力ビットストリームは普通、次の形態をとる、
... ＬＩＣ’ＬＩＲ’ＬＳＣ’.......
ここで、ＬＩＲ’はステップ３で実行されたコード化表現であり；ＬＩＣ’はステップ２で実行されたコード化表現であり；ＬＳＣ’はステップ４で実行されたコード化表現である。しかし、エンコーディング工程の最初の繰り返し中、ＬＩＣとＬＳＣは空であり、従って、最初の繰り返しの出力ビットストリームはＬＩＲ’の形態をとることに注意しなければならない。
【００９４】
この提案した方法に加えて、ＬＩＣおよびＬＳＣをコード化するときに、簡単なHuffman コード（またはより良いのはGolombコード）をビットのグループ（例えば４ビットのグループ）がコード化するのに使用される。さらに、域の各象限の有効数をコード化するときに、１５レベルのHuffman コードが４象限（１象限は重要でなければならず、従って、重要なパターンは１５（１６ではない）の内の一つとなる）のそれぞれの異なるパターンの重要なパターンを示すのに使用できる。エントロピー符号化の他の形態として、例えば２進演算コーディングなど使用して、残りの冗長性を利用する。
【００９５】
別の実施の形態として、Ｔが２×２ブロックの係数からなる場合、ステップ３における提案された方法は、次のサブステップを形成する。２×２ブロックの各係数の重要度（意味）をコード化して出力すると直ちに、これらが重要であれば、対応するサインが出力されるとともに、その係数が適切にＬＳＣまたはＬＩＣの最後に付加される。後者のサブステップにおいて、重要でない係数がＬＩＣリストに付加される。
【００９６】
好ましくは、この提案した方法は３２×３２ブロックのデータ・係数を符号化する。説明の目的のみで、４×４ブロックの係数の次なる例が、この提案した方法に基づいて符号化される。
【００９７】
【数２】
0004532653.tif 000003
【００９８】
上述のブロックは四つの象限Ａ、Ｂ、ＣおよびＤからなる。シンボルＡは、ブロックの左上（２×２）象限、Ｂは右上、Ｃは左下、また、Ｄは右下の象限を表す。さらに、シンボルＡ１はそれぞれＡの左上の画素、Ａ２は右上、Ａ３は左下、Ａ４は右下の画素を示している。同様にして、Ｂ１はＢの左上、というように画素の残りの部分にも適用される。
【００９９】
この提案方法によれば、ｎmax が最初に決定されるが、この場合４である。すなわち、各係数の最も重要なビットはビットプレーン４またはそれ以下にある。注意しなければならないのは、ビットプレーンの番号付けは０から始まることである。変数ｎmax は４ビットでコード化される（係数が圧迫されているので、ｎmax は０から１５の間となる）。最初に、
ＬＩＣ＝φ，ＬＩＲ＝｛Ａ，Ｂ，Ｃ，Ｄ｝およびＬＳＣ＝φであり、ここにシンボルφは、空きリストを示すのに使用される。
【０１００】
従って、この提案方法によれば、ビットプレーンは繰り返してコード化される。この処理はビットプレーンｎ＝ｎmax ＝４で開始され、減少数ｎは各繰り返しにつき１ずつである。
１．ｎ＝ｎmax ＝４につき、
・  最初に、リストＬＩＣ中の各係数がコード化される。何もないので、コード化は実行されない。
・  次に、リストＬＩＲ中の各域の重要度がコード化される。
【０１０１】
・域Ａに対して、ビットプレーンｎ＝４において重要であるから、１ビットが出力される。次に、Ａの４象限が、すなわち、Ａ１、Ａ２、Ａ３およびＡ４がリストＬＩＲの最後に付加され、Ａが除去される。ここでＬＩＲ＝｛Ｂ、Ｃ、Ｄ、Ａ１、Ａ２、Ａ３、Ａ４｝である。
【０１０２】
・域Ｂに対して、ビットプレーンｎ＝４において重要でないから、０ビットが出力される。
【０１０３】
・域Ｃに対して、０ビットが出力される。
【０１０４】
・域Ｄに対して、０ビットが出力される。
【０１０５】
・域Ａ１に対して、１ビットが出力される。Ａ１が単一係数３１からなるので、Ａ１がＬＩＲから除去される。３１（またはＡ１）が重要であるから、これがＬＳＣに（またはそのロケーションがブロックに）付加される。Ａ１のサイン・ビットは（０）も出力される。
【０１０６】
・域Ａ２に対して、１ビットが出力される。Ａ２が単一の重要な係数１６からなるので、ＬＩＲから除去され、ＬＳＣの最後に付加される。Ａ２のサイン・ビット（０）も出力される。ここでＬＳＣ＝｛３１、１６｝である。
【０１０７】
・域Ａ３に対して、０ビットが出力される。単一の重要でない係数であるから、ＬＩＲから除去され、係数１５がＬＩＣに付加される。ここに、ＬＩＣ＝｛１５｝である。
【０１０８】
・域Ａ４に対して、１ビットが出力される。Ａ４が単一の重要な係数１７からなるので、ＬＩＲから除去され、ＬＳＣの最後に付加される。Ａ４のサイン・ビット（０）も出力される。ここで、ＬＳＣ＝｛３１、１６、１７｝である。
・  最終ステップにおいて付加されなかったＬＳＣ中の各係数がここでコード化される。何もないので、コード化は実行されない。
【０１０９】
従って、第１繰り返しにおいて、この提案した方法が次のビットストリームを出力する。
１０００１０１００１０
この段階において、ビットプレーン４（及びこれより高い）中の全てのビットがコード化される。符号化されたビットストリームからビットを読み出すことにより、復号器がビットプレーン４（及びより高い）を再構築できる。このデコーディング方法は、重要度の判定がビットストリーム（これが、なぜ重要度の決定がビットストリームに書き込まれるかの理由である）からの読取りによって決定されることを除いて、同じである。他の係数・ビットがそのままで簡単に読み取られる。デコーダ実行パスは、エンコーダのものと同様であり、これによってデコーダは、読み取られた新しい各ビットの意味がわかっていることに注意しなければならない。
２．ｎ＝３につき、
最初に、ＬＩＣ＝｛１５｝、ＬＩＲ＝｛Ｂ、Ｃ、Ｄ｝およびＬＳＣ＝｛３１、１６、１７｝である。
・  第１に、ＬＩＣ中の各係数のビットｎ＝３をコード化する。すなわち、１ビットが係数１５と、サイン・ビット（０）に対して出力される。これは重要であるので（１ビットが出力される）、サイン・ビットが出力され、係数１５がＬＩＣから除去され、ＬＳＣの最後に付加される。これによって、ＬＳＣ＝｛３１、１６、１７、１５｝となる。
・  ＬＩＲ中の域の各々の重要度がここでコード化される。
【０１１０】
・  域Ｂに対して、０ビットが出力される。
【０１１１】
・  域Ｃに対して、ビットプレーンｎ＝３において重要であるから、１ビットが出力される。域Ｃが４象限Ｃ００、Ｃ０１、Ｃ１０およびＣ１１に仕切られ、ＬＩＲの最後に付加される。ＣがＬＩＲから除去される。従って、ここにＬＩＲ＝｛Ｂ、Ｄ、Ｃ００、Ｃ０１、Ｃ１０、Ｃ１１｝である。
【０１１２】
・  域Ｄに対して、０ビットが出力される。
【０１１３】
・  位置Ｃ００に対して、１ビットが出力される。Ｃ００が単一の重要な係数９からなるので、ＬＩＲから除去され、ＬＳＣの最後に付加される。Ｃ００のサイン・ビット（０）も出力される。ここにＬＳＣ＝｛３１、１６、１７、１５、９｝を得る。
【０１１４】
・  域Ｃ０１に対して、０ビットが出力される。単一の重要でない係数であるから、ＬＩＲからこれを除去し、係数７をＬＩＣに付加する。ここでＬＩＣ＝｛７｝である。
【０１１５】
・  域Ｃ１０に対して、０ビットが出力される。単一の重要でない係数であるから、ＬＩＲからこれを除去し、係数５をＬＩＣに付加する。ここにＬＩＣ＝｛７、５｝である。
【０１１６】
・  域Ｃ１１に対して、０ビットが出力される。単一の重要でない係数であるから、ＬＩＲからこれを除去し、係数３をＬＩＣに付加する。ここにＬＩＣ＝｛７、５、３｝である。
・  ここで、ＬＳＣの各係数のビットｎ＝３をコード化する（上記に単に付加するだけではない）。
【０１１７】
・３１、１６および１７のビットｎ＝３として、それぞれ１、０および０を出力する。
【０１１８】
従って、二回目の繰り返しにおいて、この提案した方法は次のビットストリームを出力する。
１００１０１００００１００
３．ｎ＝２につき、
最初に、ＬＩＣ＝｛７、５、３｝、ＬＩＲ＝｛Ｃ、Ｄ｝およびＬＳＣ＝｛３１、１６、１７、１５、９｝を得る。
・  第１に、ＬＩＣ中の各係数のビットｎ＝２（またはビットプレーンｎ＝２における重要度と等価である）をコード化する。すなわち、７、５および３それぞれに対して１、１および０を出力する。加うるに、７（０）および５（０）のためのサイン・ビットが出力され、これらの係数がＬＳＣに移動される。ＬＩＣ中に３が残る。
・  次に、ＬＩＲ中の各域の有効数が符号化される。
【０１１９】
・域Ｂに対して、０ビットが出力され、また、域Ｄに対して０ビットが出力される。
・  最後に、ＬＳＣ中の係数の各々に対するビットｎ＝２を更新する（上記に付加せず）。
【０１２０】
・３１、１６、１７、１５および９に対して、それぞれ１、０、０、１および０を出力する。
【０１２１】
従って、三回目の繰り返しにおいて、この提案した方法は次のビットストリームを出力する。
１０１００００１００１０
ビットプレーン０、またはいくつかの他の有限点まで、この態様を続行する。特定の有限コードを使用した場合、（三つの）サブパスのどれか一つの後、終了することができることに注意しなければならない。（基本的に、ＦＦは有限コードとしてリザーブされ、有限コードを慎重に挿入しなければ、コード化ビットストリームを決して強制的にＦＦに含ませることはない。
【０１２２】
これまでに説明したように、この方法は係数の３２×３２ブロックをエンコーディングするのに好適に利用できる。これらの状況において、元の象限Ａ、Ｂ、Ｃ、Ｄは各々１６×１６の係数からなり、また域Ａ１、Ａ２、．．．Ｄ４は各々８×８の係数からなる。従って、３２×３２ブロックの符号化において、ブロックは４分木方法に基づいて５回仕切られるが、一方、与えれた例においては４×４ブロックが２回のみで仕切られる。
【０１２３】
デコーディング工程は、エンコーディング工程を単に模倣してコード化された表現から画素を再構築する。
【０１２４】
図２２を参照して、この提案方法を実行するための第１の好ましい実施の形態に基づくエンコーダを説明する。係数・エンコーダ２２００は、対応するデータ２２０２を得て、出力符号化データ２２０４の連続した流れを提供するように設計されている。このエンコーダ２２００は、次のロジック部を含んでいる。すなわち、ビットプレーン・コンバータ２２０６；ビットプレーン・ツリー・ビルダー２２０８−０から２２０８−１５；ビットプレーン・エンコーダ２２１０である。
【０１２５】
エンコーダ２２００は、ビットプレーンで３２×３２の係数を記憶するためのメモリ２２１４と；係数のサイン・ビットを記憶するためのメモリ２２１６と；ビットプレーン０から１５を記憶するためのメモリ２２１８−１５から２２１８−０も含んでいる。エンコーダ２２００は、域の第１リストを記憶するためのメモリ２２２６と；域の第２リストを記憶するためのＦＩＦＯメモリ２２２８と；ＬＳＣ値のリストを記憶するためのメモリ２２２２と；ＬＩＣ値のリストを記憶するためのメモリ２２２４をさらに含んでいる。
【０１２６】
エンコーダ２２２０は、次のようにして動作する。最初に、３２×３２入力係数・データがラスタ順にメモリ２２１２に記憶される。ビットプレーン・コンバータ２２０６は、入力係数・データを読み取り、このデータを、ビットプレーン０からビットプレーン１５までの１６のビットプレーンに変換し、このデータは続いてメモリ２２１４に記憶される。ビットプレーン・コンバータ２２０６はまた３２×３２ブロックの係数のサイン・ビットも判定し、このサイン・ビットがメモリ２２１６に記憶される。
【０１２７】
ビットプレーン・ツリー・ビルダー２２０８−０から２２０８−１５が各々３２×３２係数・データを読み取り、域に対応するノードと１×１の画素を有する４分木構造を構築する。各ツリーにおいて、ノードは、域またはこのノードに対応する画素がビットプレーンのために重要であれば、１にセットされる。そのノードに対応する域又は画素のための重要なビットが、ビットプレーンより大きいか、又は小さければ、ノードはゼロにセットされる。
【０１２８】
次に図２３を参照して、３２×３２ブロックのためのビットプレーンｎにおけるビットプレーン・ツリービルダー２２０８−ｎによって構成された構築ツリー２３００を説明する。簡潔にする目的で、ツリーの一部のみを示す。このツリー２３００は、１×１画素レベルまで下げたブロックの各４分木の仕切りを表すノードを含んでいる。この場合において、全３２×３２ブロックがシンボル０によって表される。１６×１６の左上象限がノードＡで表され、１６×１６右上象限がＢで表され、１６×１６の左下象限がノードＣで表され、１６×１６の右下象限がノードＤで表される。ノードＡ１、Ａ２、Ａ３およびＡ４が、４分木のＡの左上、右上、左下および右下の８×８の４分木の仕切りをそれぞれ表している。同様にして、ノードＡ１１、Ａ１２、Ａ１３およびＡ１４は、象限Ａ１の４分木の左上、右上、左下および右下の４×４４分木の仕切りをそれぞれ表している。同様にして、ノードＡ１１１、Ａ１１２、Ａ１１３およびＡ１１４は、象限Ａ１１の４分木の左上、右上、左下および右下の２×２の４分木の仕切りをそれぞれ表している。最後に、ノードＡ１１１１、Ａ１１１２、Ａ１１１３およびＡ１１１４は、象限Ａ１１１の４分木の左上、右上、左下および右下の１×１４分木の仕切りをそれぞれ表している。ツリーの残りの部分（図示省略）は３２×３２ブロックの各１×１象限まで下がって同様の方法で表される。
【０１２９】
ビットプレーン・ツリー・ビルダー２２０８−ｎが、象限順（例えば、Ａ１１１１、Ａ１１１２、Ａ１１１３およびＡ１１１４）で係数を読み取ることによってビットプレーンｎを逆からこの種のツリーを構築する。そのノードに対応する域又は画素のための重要なビットが、ビットプレーンより大きいか、又は小さければ、ノードはツリービルダーによってゼロにセットされる。こうして、ビットプレーン・ツリー・ビルダーは、次のフォーマットで各ノードのための重要な情報を出力する。
【０１３０】
ＡＢＣＤＡ１Ａ２Ａ３Ａ４Ａ11Ａ12Ａ13Ａ14Ａ21,..., Ｄ44Ａ111,...,Ｄ444,...,Ａ1111, Ｄ4444
ビットプレーン・ツリー・ビルダー２２０８−０から２２０８−１５の各々からの出力は、それぞれのビットプレーン・ツリー・メモリ２２１８−０から２２１８−１５に記憶される。
【０１３１】
ビットプレーン・エンコーダ２２１０が、ビットプレーン・ツリー・メモリの各々を読み取り、次にビットプレーン・ツリー・メモリ２２１８−１５で開始する。ビットプレーン・エンコーダ２２１０が、ノードＡ、Ｂ、ＣおよびＤに対応するビットプレーン・メモリ２２１８−１５内に記憶された四つの重要なビットＡ、Ｂ、ＣおよびＤを次に読み取ることによって処理が開始される。ビットプレーン・エンコーダは、メモリ２２２６内の域の第１リスト中のこれらのノード｛Ａ、Ｂ、Ｃ、Ｄ｝のリストを記憶する。ビットプレーン・エンコーダ２２１０が次の操作に進行する：
１．  ビットプレーン・エンコーダ２２１０が、第１域リスト上の第１ノード（域）に対応するビットプレーン・ツリー内のビットを読み取る。
【０１３２】
ａ．ビットが重要であれば、エンコーダが２進の１を出力する。エンコーダがＦＩＦＯ２２２８上の第２域リスト内のノードのチルドレン（子供）を記憶し、第１域リスト２２２６からのノードを除去する。
【０１３３】
ｂ．ビットが重要でない場合、エンコーダが２進の０を出力し、第１域リスト２２２６上のノードを維持する。
【０１３４】
２．  ビットプレーン・エンコーダ２２１０が、第１域リスト内の全てのノードが読み取られるまで、ステップ１を繰り返す。
【０１３５】
３．  ビットプレーン・エンコーダが、ＦＩＦＯ２２２８上の第２域リスト内の第１ノードに対応するビットプレーン・ツリー中のビットを読み取る。
【０１３６】
ａ．ビットが重要であり、そのノードに関する子供がある（すなわち、ツリー内のそのノードの直下にノードがある）場合、エンコーダが２進のゼロを出力し、このノードを第１域リスト２２２６上のノードに入れる。
【０１３７】
ｂ．ビットが重要であり、そのノードに関する子供がなければ、エンコーダが２進のゼロを出力し、このノードが対応する画素に対するインデックスとしてＬＩＣリスト２２２４に記憶される。
【０１３８】
ｃ．ビットが重要であり、そのノードに関する子供がなければ、エンコーダが２進の１と対応するサイン・ビットを出力し、このノードが対応する画素に対するインデックスとしてＬＩＣリスト２２２２に記憶される。
【０１３９】
ｄ．ビットが重要であり、そのノードに関する子供があれば、エンコーダが２進の１を出力し、第２域リストからノードを除去する。さらに、ノードの子供を第２域リストに付加する。
【０１４０】
ｅ．第２域が空きであれば、エンコーディング工程がそのビットプレーン・ツリーを完成させる。
【０１４１】
ビットプレーン・エンコーダが残りのビットプレーン・ツリーに対して次にこの操作を繰り返す。現在のビットプレーン・ツリーへの操作の開始時における域の第１リストには、前回のビットプレーン・ツリーへの前回操作から残っている域が含まれている。これらの出力は出力ストリームのＬＩＲ部分に対応する。現在のビットプレーン・ツリーに対する現在の操作の完了後、ビットプレーン・エンコーダがＬＩＣとＬＳＣビットを符号化し、出力する。
【０１４２】
ビットプレーン・エンコーダが、リスト上の第１画素に対するインデックスのためのＬＩＣリストを読み取り、ビットプレーン・メモリ２２１４から必要とされるビットを選択する現在ビットプレーン数を使用することによってＬＩＣビットを符号化する。選択されたビットが２進の０であれば、エンコーダがゼロを出力する。選択されたビットが２進の１であれば、エンコーダが２進の１を、メモリ２２１６からの画素のサイン・ビットとともに出力する。こうしてエンコーダはＬＩＣからインデックスを除去し、これをＬＳＣリストに付加する。一度、インデックスがリストから除去されると、残りのインデックスは再編成されるのが好ましい。エンコーディング（符号化）は、一度、ＬＩＣが通過すると、完了する。
【０１４３】
ビットプレーン・エンコーダが、リスト上の第１画素に対するインデックスのためのＬＩＣリストを読み取り、ビットプレーン・メモリ２２１４から必要とされるビットを選択する現在ビットプレーン数を使用することによってＬＩＣビットを符号化する。こうして、選択されたビットが出力される。ビット・プレン・エンコーダは、読み取られるべきＬＳＣリスト中の画素数を示す長さ値を記憶するためのカウンタも含んでいる。ＬＳＣ符号化の終了後、この値が更新され、ＬＩＲとＬＩＣからの新しい要素を付加することができる。
【０１４４】
この提案方法のエンコーディング（符号化）とデコーディング（復号）工程は、図２４に示したような従来の汎用コンピュータを使用して実行されるのが好ましく、その工程がこのコンピュータを実行するソフトウエアとして備えることができる。特に、コーディング及び（又は）デコーディング方法のステップは、コンピュータによって実行されるソフトウエア内の命令によって実行される。ソフトウエアは二つの別々のパーツに分かれており、その一つがデコーディング及び（又は）コーディング方法を実行し、また他方の一つが後者とユーザ間のユーザ・インターフェイスを制御する。ソフトウエアは、例えば次に説明する記憶デバイスを含むコンピュータにより読取可能な記憶媒体内に記憶できる。このソフトウエアはコンピュータ読取可能な記憶媒体からコンピュータ内にロードされ、コンピュータによって実行される。この種のソフトウエア、又はこれに記録されたコンピュータ・プログラムを有するコンピュータにより読取可能な記憶媒体は、コンピュータ・プログラム製品である。コンピュータ内でこのコンピュータ・プログラム製品の使用は、本発明によるデジタル画像をエンコーディング（符号化）し、また、デジタル画像のコード化された表現をデコーディングするための有利な装置を好適に実行する。
【０１４５】
コンピュータ・システム２４００は、コンピュータ２４０１と、ビデオ表示装置２４１６と、入力デバイス２４０２、２４０３を備えている。加うるに、コンピュータ・システム２４００は、通信インターフェイス２４２１を介して、一つまたはそれ以上の他のコンピュータに、モデム通信パス、コンピュータ・ネットワーク等々のような適切な通信チャネル２４２２を使用して接続することができる。コンピュータ・ネットワークはローカル・エリア・ネットワーク（ＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、イントラネットおよび（または）インターネットを含めることもできる。
【０１４６】
コンピュータ２４０１自体は、中央処理装置（以後単にプロセッサという）２４０５と、ランダム・アクセス・メモリ（ＲＡＭ）とリード・オンリー・メモリ（ＲＯＭ）とを含むメモリ２４０６と、入力／出力（Ｉ／Ｏ）インターフェイス２４０８と、ビデオ・インターフェイス２４０７と、図２４のブロック２４０９で概略的に示された一つまたはそれ以上の記憶デバイスとを備えている。記憶デバイス２４０９は、次の内の一つまたはそれ以上を含んでいる。すなわち、フロッピー・ディスク、ハードディスク・ドライブ、磁気−光学ディスク・ドライブ、ＣＤ−ＲＯＭ、磁気テープまたは当該技術において周知の他の多数の不揮発性記憶デバイスである。要素２４０５から２４０９、２４２１はそれぞれ一般的に、データ、アドレスおよび制御バスからなるバス２４１４を介して一つ、またはそれ以上の他のデバイスに接続される。
【０１４７】
ビデオ・インターフェイス２４０７がビデオ表示装置２４１６に接続され、コンピュータ２４０１からのビデオ信号を提供してこのビデオ表示装置２４１６に表示する。コンピュータ２４０１を作動させるユーザ入力は、一つ又はそれ以上の入力デバイス２４０２，２４０３によって提供できる。例えば、オペレータはキーボード２４０２および（または）マウス２４０３のような指示デバイスを使用することができる。
【０１４８】
システム２４００は図示の目的で簡潔に示されているが、他の形態も使用できる。実施の形態を実行できる例としてのコンピュータには、ＩＢＭ−ＰＣ／ＡＴまたは互換機を含み、その一つにＰＣのマッキントッシュ（商標名）ファミリ、サン・スパークステーション（商標名）等々がある。上述したものは実施の形態を実行できるコンピュータのタイプの単なる一例である。一般的には、以後に説明する実施の形態の処理は、プロセッサ２４０５を使用する読取りおよび制御されたコンピュータにより読取可能な記憶媒体としてハードディスク・ドライブ（図２４において通常、ブロック２４０９で示される）に記憶されたソフトウエアまたはプログラムとして内在している。プログラムと画素データおよびネットワークから取り入れられたデータの中間記憶は、半導体メモリ２４０６を使用して、ハード・ディスク・ドライブ２４０９と提携して達成することができる。
【０１４９】
ある例において、プログラムは、ＣＤ−ＲＯＭまたはフロッピー・ディスク（両者ともブロック２４２３で概略的に示す）上に符号化されユーザに提供されるか、または別の方法として例えば、コンピュータに接続されたモデム・デバイスを介してネットワークからユーザが読み取ることができる。さらに、ソフトウエアは、他のコンピュータ読取可能媒体からコンピュータ・システム２４００にロードすることもできる。この媒体には磁気テープ、ＲＯＭまたは集積回路、磁気−光学ディスク、コンピュータと他のデバイス間の無線または赤外線伝送チャネル、ＰＣＭＣＩＡカードのようなコンピュータ読取可能カード、およびＥメール通信を含むインターネットおよびイントラネットと、ウエブサイト等に記憶された情報を含む。上述したものは適切なコンピュータ読取可能媒体の単なる例である。他のコンピュータ読取可能媒体も実行可能である。
【０１５０】
エントロピー符号化器から転じて符号化方法及び装置に説明を戻したが、逆に、符号化された画像を復号により再生しても良い。この場合、画像はまず最初に完全にエントロピー復号され、その復号された画像に、前述の符号化方法の略逆の処理が適用される。
【０１５１】
上述の説明から明白なように、本発明の実施の形態はコンピュータおよび画像／データ処理産業に適用可能である。
【０１５２】
これまでに説明したものは、本発明のある実施の形態のみで、修正および（または）変更も本発明の範囲と概念から外れることなく可能であり、実施の形態は例であって、限定ではない。
【０１５３】
【発明の効果】
以上説明したように本発明によれば、例えば少ないバッファの容量で、複数レベルのＤＷＴを効率良く行うことができるという効果がある。
【図面の簡単な説明】
【図１】画像の４レベルの離散ウエーブレット変換の種々のサブバンドを示す図である。
【図２】本発明の好適な実施の形態の変形例としての画像の水平タイリングを示す図である。
【図３】本発明の好適な実施の形態に係る画像の垂直タイリングを示す図である。
【図４】本発明の好適な実施の形態の符号化器を示す図である。
【図５】図３のタイリングと好適なタイル走査順を示す図である。
【図６】図４の圧縮エンジンをより詳しく示す図である。
【図７】本発明の好適な実施の形態に係るリオーダ・バッファを示す図である。
【図８】図７のリオーダ・バッファの充填順を示す図である。
【図９】本発明の好適な実施の形態に係る垂直フィルタのハードウエア構成を示す図である。
【図１０】本発明の好適な実施の形態に係る水平フィルタのハードウエア構成を示す図である。
【図１１】本発明の好適な実施の形態に係るサブバンド・バッファのハードウエア構成を示す図である。
【図１２】図１１のサブバンド・バッファの充填順および走査順を示す図である。
【図１３】本発明の好適な実施の形態に係る制御状態マシンのハードウエア構成を示す図である。
【図１４】本発明の好適な実施の形態に係る部分バンド・バッファのハードウエア構成を示す図である。
【図１５】図１４の部分バンド・バッファの充填順および走査順を示す図である。
【図１６】図６の制御状態マシン・モジュールによる処理の流れを示すフローチャートである。
【図１７】本発明の好適な実施の形態を実行する汎用コンピュータの概略ブロック図である。
【図１８】元の画像とそのＤＷＴ変換を示す図である。
【図１９】図１８の元の画像の第２レベルＤＷＴ変換を示す図である。
【図２０】図１８の元になる画像の４レベルＤＷＴ変換を示す図である。
【図２１】３２×３２ブロックにサブバンドをタイリングする図である。
【図２２】符号化器の実施の形態を示す図である。
【図２３】図２２のビットプレーン・ツリー・ビルダーによって構築されたツリーの一部を示す図である。
【図２４】説明した符号化方法を実行するための汎用コンピュータの構成を示すブロック図である。
【図１】
0004532653.tif 000004
【図２】
0004532653.tif 000005
【図３】
0004532653.tif 000006
【図４】
0004532653.tif 000007
【図５】
0004532653.tif 000008
【図６】
0004532653.tif 000009
【図７】
0004532653.tif 000010
【図８】
0004532653.tif 000011
【図９】
0004532653.tif 000012
【図１０】
0004532653.tif 000013
【図１１】
0004532653.tif 000014
【図１２】
0004532653.tif 000015
【図１３】
0004532653.tif 000016
【図１４】
0004532653.tif 000017
【図１５】
0004532653.tif 000018
【図１６】
0004532653.tif 000019
【図１７】
0004532653.tif 000020
【図１８】
0004532653.tif 000021
【図１９】
0004532653.tif 000022
【図２０】
0004532653.tif 000023
【図２１】
0004532653.tif 000024
【図２２】
0004532653.tif 000025
【図２３】
0004532653.tif 000026
【図２４】
0004532653.tif 000027