(57)【特許請求の範囲】
【請求項１】
デジタル画像の変換係数を有するコード・ブロックを表すシンボルをエントロピ符号化する方法であって、第１のビットプレーンから所定の最下位ビットプレーンまでの各ビットプレーンについて、
現在のビットプレーン内にゼロの有意状態を持つ係数であって、現在のビットプレーン内に１の有意状態を持つ近傍係数を持つ係数に属するシンボルである、現在のビットプレーン内の全てのシンボルのエントロピ符号化を行うシグニフィカンス・プロパゲーションステップと、
前回のビットプレーン内に１の有意状態を持つ係数に属するシンボルである、現在のビットプレーン内の全てのシンボルのエントロピ符号化を行うマグニチュード・リファインメント・ステップと、
現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップ又は前記マグニチュード・リファインメント・ステップ中、それ以前にエントロピ符号化されなかったシンボルである、現在のビットプレーン内の全てのシンボルのエントロピ符号化を行うクリーンアップ・ステップとを実行し、
更に、
現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップ中、エントロピ符号化の対象となるシンボルを持つ係数である、前記コード・ブロック内の前記係数の位置の第１のリストを、現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップに先行して生成するステップと、
現在のビットプレーンの前記マグニチュード・リファインメント・ステップ中、エントロピ符号化の対象となるシンボルを持つ係数である、前記コード・ブロック内の前記係数の位置の第２のリストを、現在のビットプレーンの前記マグニチュード・リファインメント・ステップに先行して生成するステップと、
現在のビットプレーンの前記クリーンアップ・ステップ中、エントロピ符号化の対象となるシンボルを持つ係数である、前記コード・ブロック内の前記係数の位置の第３のリストを、現在のビットプレーンの前記クリーンアップ・ステップに先行して生成するステップと、
を有することを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記第１及び第２のリストを生成する前記ステップが、前回のビットプレーンの前記クリーンアップ・ステップ中に行われることを特徴とする方法。
【請求項３】
請求項１に記載の方法において、前記第３のリストを生成する前記ステップが、現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップ中に行われることを特徴とする方法。
【請求項４】
請求項１に記載の方法において、
現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップは、
前回のビットプレーンの前記クリーンアップ・ステップによって生成される前記第１のリスト内の前記位置に対応するシンボルである、現在のビットプレーン内のシンボルのエントロピ符号化を行うサブステップと、
ゼロの非有意状態を持つ、現在のビットプレーン内の任意のシンボルであって、現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップ中に１の有意状態に変化する近傍として、現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップ中、予めエントロピ符号化されたシンボルを持つ係数を有する任意のシンボルである、所定の走査順で前記近傍に後続する任意のシンボルのエントロピ符号化を行うサブステップと、
ゼロの非有意状態を持つ、コードブックの係数の位置と、１の有意状態を持つ現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップでエントロピ符号化されるシンボルを有する前記係数に隣接する係数の位置の第４のリストを生成するサブステップと、
現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップ中、１の有意状態に変化する前記係数の前記第１のリストの前記位置にタグを付けるサブステップと、
現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップ中、１の有意状態に変化する前記係数の前記第４のリストの前記位置にタグを付けるサブステップと、
前記コード・ブロック内の係数の位置の前記第３のリストを生成するサブステップと、
を有することを特徴とする方法。
【請求項５】
請求項１に記載の方法において、前記第１のビットプレーンは、有意係数を持つ前記コード・ブロックの最上位ビットプレーンより下の次のビットプレーンであることを特徴とする方法。
【請求項６】
請求項１に記載の方法において、前記エントロピ符号化が、前記シンボルのエントロピ符号化または復号化を行うことが可能であることを特徴とする方法。
【請求項７】
請求項１に記載の方法において、前記エントロピ符号化が前記シンボルのエントロピ符号化を行う方法であって、現在のビットプレーン用の前記第１と、第２と、第３のリストを生成する前記ステップが、現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップに先行して生成されることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般にデータ圧縮と解凍に関し、特に、エントロピ符号化方法に関する。
【０００２】
【従来の技術】
新しいＪＰＥＧ-２０００規格に対する提案要求が最近出され、“情報技術−ＪＰＥＧ２０００画像符号化システム−ＪＰＥＧ２０００委員会草案バージョン１.０（１９９９年１２月９日）という表題の規格草案（本明細書では以後ＪＰＥＧ２０００と呼ぶ）が発表された。
【０００３】
ＪＰＥＧ２０００では１以上の画像タイル成分に画像全体を分割し、次いで、この画像タイル成分の各々の２次元離散ウェーブレット変換を行うことが提案されている。次いで、各画像タイル成分の変換係数がサブバンドにグループ化される。次いで、各コード・ブロックがエントロピ符号化される前に、該サブバンドは分割されて矩形のコード・ブロックに変えられる。各コード・ブロックの変換係数はエントロピ符号化に先行して符号絶対値で表現される。エントロピ符号化は、コンテキスト生成部と算術符号化部の２つの部分から構成される。算術符号化部は、符号化の対象となる係数のビット・シンボルと、そのビット・シンボルのコンテキストとを入力としている。ある係数のビット・シンボルのコンテキストは、コード・ブロックの同じビットプレーン内の８個の包囲係数の‘有意（significance）’状態に基づいている。該ビット・シンボルは算術符号化部によって符号化される。係数の‘有意’状態とは、２進値変数Ｓi[ｍ，ｎ]であり、該２進値変数は０に初期化されるが、係数の第１のノンゼロ・ビット値が符号化された直後にこの変数は１に変化する。図１は、係数“Ｘ[ｍ，ｎ]”の８個の包囲係数の近傍有意状態Ｓi[ｍ−１，ｎ−１]、Ｓi[ｍ−１，ｎ]、Ｓi[ｍ−１，ｎ＋１]、Ｓi[ｍ，ｎ−１]、Ｓi[ｍ，ｎ＋１]、Ｓi[ｍ＋１，ｎ−１]、Ｓi[ｍ＋１，ｎ]とＳi[ｍ＋１，ｎ＋１]を示す。但し、ｍ、ｎはそれぞれコード・ブロックの行番号と列番号であり、Ｓi［］は、係数Ｘ[ｍ，ｎ]のビット・シンボルｉが符号化される直前の有意状態である。これらの近傍有意状態は係数Ｘ[ｍ，ｎ]の３×３近傍有意状態と呼ばれることもある。
【０００４】
算術符号化部[ｍ，ｎ]は、１つのコード・ブロックの最上位ビットプレーンの全てのビット・シンボルをまず符号化し、次いで、コード・ブロックの次に低いビットプレーンの全てのビット・シンボル等々を符号化し、最後に最下位ビットプレーンの全てのビット・シンボルを符号化する。１つのコード・ブロックの各ビットプレーンの範囲内で、算術符号化部は所定の順序の３つのパスで係数のビット・シンボルを符号化する。
【０００５】
ビットプレーンの第１のパスはシグニフィカンス・プロパゲーション・パス（ＳＰパス）と呼ばれ、ビットプレーンの第２のパスはマグニチュード・リファインメント・パス（ＭＲパス）呼ばれ、ビットプレーンの第３で最後のパスはクリーンアップ・パス（Ｎパス）と呼ばれる。ＳＰパス中で、符号化対象ビット・シンボルは１の有意状態を持っているが、該ビット・シンボル自身が０の有意状態を持つ近傍ビット・シンボルを持っている場合、ビットプレーンのビット・シンボルは符号化される。ＭＲパス中で、ビットプレーンのビット・シンボルがまだ符号化されていない場合、該ビット・シンボルの係数が前回の符号化ビットプレーンですでに有意であれば、該ビット・シンボルは符号化される。Ｎパス中で、予め符号化されなかったビットプレーンの残りのビット・シンボルはこの時符号化される。
【０００６】
このコンテキストは符号化対象ビットと共に算術符号化部へ転送され、符号化されたシンボルはビット・ストリームへ出力される。符号化対象のこのビット・シンボルの値が１で、かつ、その有意状態がゼロであれば、いったんビット・シンボルが符号化され、かつ、直後の符号化対象ビット・シンボルが係数用の符号ビットであった場合、有意状態は１にセットされる。上記条件を満たさない場合には有意状態はゼロ（０）のままである。連続する係数とパスのコンテキストを考慮する場合、この係数の最も現在の有意状態が用いられる。
【０００７】
算術符号化部は、所定の同じ順序で３つのパス（ＳＰ、ＭＲ、Ｎ）内のビットプレーンのビット・シンボルを符号化する。算術符号化部はまず中にノンゼロ・ビットを持つ最上位ビットプレーンへ進み、ＳＰ、ＭＲパスをスキップし、Ｎパスから始まる。次いで、算術符号化部は次に低いビットプレーンへ進み、３つのパス（ＳＰ、ＭＲ、Ｎ）で、その順序でビット・シンボルを符号化する。次いで、算術符号化部は次に低いビットプレーンへ進み、同順のパス（ＳＰ、ＭＲ、Ｎ）でビット・シンボル等々を符号化し、最後に最下位ビットプレーンを符号化する。
【０００８】
さらに、コード・ブロックの各ビットプレーンは特別の順序で走査される。最上部左側から始まり、列の最初の４個のビット・シンボルが走査される。次いで、コード・ブロックの幅がカバーされてしまうまで、第２列の最初の４個のビット・シンボルが走査される。次いで、第１列の第２番目の４個のビット・シンボル等々と走査される。任意の残りの行について、サブバンドの最下位コード・ブロック内で同様の走査が続けられる。図２は、８×８ブロックで構成される６４個の変換係数を持つコード・ブロックについてのコード・ブロック走査パターンの一例を示す。この例でわかるように、走査は４つの行の連続するストリップ（細長い片）で行われる。コード・ブロックは８×８ブロックに限定されるものではなく、６４×６４のコード・ブロック等のさらに大きなコード・ブロックが考えられる。後者の場合、４つの行の１６個の連続するストリップが生じる。説明を簡単にするために、本明細書ではこの走査順をＪＰＥＧ２０００走査順と呼ぶことにする。
【０００９】
ＪＰＥＧ２０００に記述されているエントロピ復号化は、エントロピ符号化と鏡像の関係になる。例えば、デコーダは符号化の場合と同順でシンボルを復号する。エントロピ復号化はまた、コンテキスト生成部と算術復号部の２つのセクションから構成される。算術復号化部は、復号の対象となるシンボルと、復号の対象となるそのシンボルのコンテキストとを入力として受け取る。復号の対象となる走査順序シンボルのコンテキストは、コード・ブロックの同じビットプレーン内の８個の包囲係数の‘有意’状態に基づき、該シンボルは算術復号化部によって復号される。係数の‘有意’状態は２進値変数Ｓ[ｍ，ｎ]であり、該２進値変数は０に初期化されるが、係数の第１のノンゼロ・ビットプレーン値が復号されると１に変化する。このように、復号化段階中の係数の有意状態は符号化段階中の係数の有意状態と鏡像関係になる（図２参照）。
【００１０】
ＪＰＥＧ２０００では、算術符号化と復号化とは最上位ビットプレーンから最下位ビットプレーンへビットプレーン毎に行われる。初めに、符号化／復号化は、その中にゼロしか含まないすべてのビットプレーンをスキップし、その中にノンゼロ要素を持つ第１のビットプレーンに対するオペレーションを開始する。いったん符号化／復号化が、その中にノンゼロ要素を持つ第１のビットプレーンに達すると、シグニフィカンス・プロパゲーション・パスと、マグニチュード・リファインメント・パスと、クリーンアップ・パスの３つのパスで、コーデックは各連続ビットプレーンに対して作用する。
【００１１】
ビットプレーン全体にわたるコーデック走査を有し、或る特徴を持つ位置の配置を定めるＪＰＥＧ２０００を実現するエントロピ・コーデックが提案されている。例えば、シグニフィカンス・プロパゲーション・パスで、コーデックは、位置自体は有意でないが、その位置の３×３の近傍に少なくとも１つの有意係数を持つ位置を探す。マグニチュード・リファインメント・パスで、コーデックは既に有意な位置を探す。クリーンアップ・パスで、コーデックは前に符号化／復号化されていない位置を探す。したがって、この提案されたコーデックでは、全てのビットプレーンについて３回の走査が行われる。これは、最大スループットが３サイクル当たり１シンボルであることを含意する。
【００１２】
上記から解るように、提案されたコーデックの主要な問題点として、各パスについて、コーデックが全ての位置を走査し、現在のパスで符号化／復号化が行われているかどうかを判定する必要があるという点が挙げられる。これは、符号化の必要がない位置を走査してサイクルが浪費されることを意味する。
【００１３】
【発明が解決しようとする課題】
本構成及び／又は提案の１以上の問題点を実質的に解決または少なくとも改善することが本発明の目的である。
【００１４】
【課題を解決するための手段】
本発明の第１の態様によれば、デジタル画像の変換係数を有するコード・ブロックを表すシンボルをエントロピ符号化する方法が提供される。該方法は第１のビットプレーンから所定の最下位ビットプレーンまでの各ビットプレーンについて以下のステップ：現在のビットプレーン内にゼロの有意状態を持つ係数であって、現在のビットプレーン内に１の有意状態を持つ近傍係数を持つ係数に属するシンボルである、現在のビットプレーン内のすべてのシンボルのエントロピ符号化を行うシグニフィカンス・プロパゲーション・ステップと、；前回のビットプレーン内に１の有意状態を持つ係数に属するシンボルである、現在のビットプレーン内のすべてのシンボルのエントロピ符号化を行うマグニチュード・リファインメント・ステップと、；現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップまたはマグニチュード・リファインメント・ステップ中、それ以前にエントロピ符号化されなかったシンボルである、現在のビットプレーン内のすべてのシンボルのエントロピ符号化を行うクリーンアップ・ステップと、を実行する方法において、現在のビットプレーンのシグニフィカンス・プロパゲーション・ステップ中エントロピ符号化の対象となるシンボルを持つ係数である、前記コード・ブロック内の前記係数の位置の第１のリストを、現在のビットプレーンの前記シグニフィカンス・プロパゲーション・ステップに先行して生成するステップと、；現在のビットプレーンのマグニチュード・リファインメント・ステップ中エントロピ符号化の対象となるシンボルを持つ係数である、前記コード・ブロック内の前記係数の位置の第２のリストを、現在のビットプレーンのマグニチュード・リファインメント・ステップに先行して生成するステップと、；現在のビットプレーンの前記クリーンアップ・ステップ中エントロピ符号化の対象となるシンボルを持つ係数である、前記コード・ブロック内の前記係数の位置の第３のリストを、現在のビットプレーンのクリーンアップ・ステップに先行して生成するステップとをさらに有する。
【００２３】
【発明の実施の形態】
本発明のいくつかの好ましい実施の形態について、以下に図面を参照しながら説明する。
【００２４】
ステップ及び／又は特徴を示す同じ参照番号を持つ１以上のいずれかの添付図面で参照が行われる場合、それらのステップ及び／又は特徴は、逆の意図が現れない限り、この説明の目的のために同じ機能または作用を持つ。
【００２５】
本明細書に記載の好ましい装置と方法の原理は、データ圧縮と解凍に対して一般的適用性を持つ。しかし、説明を簡単にするために、上述のＪＰＥＧ２０００に従うデジタル画像の圧縮と解凍を参照しながら好ましい装置と方法について説明する。しかし、これは記載の方法及び装置に本発明を限定することを意図するものではない。例えば、本発明はデジタル・ビデオの圧縮と解凍に適用することも可能である。
【００２６】
好ましい方法についての詳細な説明に進む前に、好ましい方法の簡単な概観について以下説明する。まず、画像全体は１以上の画像タイル成分に分割され、次いで、これら画像タイル成分の各々に対して２次元離散ウェーブレット変換が行われる。次いで、各画像タイル成分の変換係数がサブバンドにグループ化される。次いで、該サブバンドは、各コード・ブロックがエントロピ符号化される前にさらに矩形のコード・ブロックに分割される。
【００２７】
次に図３に目を向けると、第１の構成に従ってコード・ブロックの変換係数のシンボルをエントロピ符号化する方法を示すフローチャート３００が示されている。好適には、方法３００が画像の各コード・ブロックを呼び出すことが望ましい。本方法はコーデック法で機能する。すなわち、本方法はシンボルを復号もしくは符号化することができる。符号化あるいは復号のいずれかが行われる間、本方法はほぼ同一のステップを実行する。復号処理は、シグニフィカンス・プロパゲーションリストと、マグニチュード・リファインメント・リストと、クリーンアップ・リストとを利用するという点で符号化処理と鏡像関係になる。しかし、復号化中、ビットプレーンに分割されるソースコード・ブロックは存在せず、最上位ビットプレーンのロケーションが既に与えられている。説明を簡単にするために、符号化処理を参照しながら主としてエントロピ符号化法について説明を行う。
【００２８】
方法３００は、ステップ３０２から始まり、いずれかの必要なパラメータが初期化される。初期化段階中、方法３００は有効値テーブルを生成する。この有効値テーブルは符号化の対象となるコード・ブロックの係数の有意状態を示す２次元配列を有する。最初に、配列の各エントリは、各係数が非有意状態を持っていることを示すゼロ（０）にセットされる。ある係数の第１のノンゼロ・ビットプレーン値が符号化され、配列の対応するエントリが（１）にリセットされたとき、その係数の有意状態は（１）に遷移する。任意の呼び出されたシグニフィカンス・プロパゲーション符号化パス中にまたは、任意のクリーンアップ符号化パス中に有効値テーブルの更新を行うことができる。
【００２９】
また初期化段階中、本方法によって、本明細書でシグニフィカンス・プロパゲーションリスト（ＳＰリスト）、マグニチュード・リファインメント・リスト（ＭＲリスト）及びクリーンアップ・リスト（Ｎリスト）と名付けられる３つのリストが生成される。これらのリストには、コード・ブロックの範囲内の、現在のパス中符号化の対象となるビット・シンボルの位置が含まれる。例えば、シグニフィカンス・プロパゲーションリストには、コード・ブロックの範囲内に、現在のシグニフィカンス・プロパゲーション・パス中符号化の対象となるビット・シンボルのすべての位置リストが含まれる。ビット・シンボルの位置という用語は、本明細書では、そのビット・シンボルが一部を形成する変換係数のコード・ブロックの範囲内の配列位置を意味する。さらに、これらのリストの各々の範囲内の位置は、コード・ブロック走査順に従って索引化される（図２参照）。最初、シグニフィカンス・プロパゲーションリスト（ＳＰリスト）と最大リファインメント・リスト（ＭＲリスト）とは空である。一方、クリーンアップ・リスト（Ｎリスト）はコード・ブロックの範囲内のすべての位置をリストし、ノンゼロ・ビットを持つ最上位のビットプレーンの符号化に使用される。
【００３０】
ＳＰリストとＭＲリストとは、必要に応じてさらなる位置の追加と削除とにより本方法の処理中更新することができる。さらに、現在のＮリストは現在のＳＰとＭＲリスト内に含まれていない位置を含むようにＳＰ符号化パス中生成される。
【００３１】
開始３０２後、コード・ブロックの変換係数が受け取られ、ビットプレーンに分割される（３０４）。次のステップ３０６で、コード・ブロックのビットプレーンがチェックされ、どのビットプレーンがその中に最上位ノンゼロ・ビットを持っているかが決定される。
【００３２】
次いで、本方法はステップ３０８へ進み、このステップで最上位ビットを持つビットプレーンが単一クリーンアップ・パス内でエントロピ符号化される。具体的には、ノンゼロ・ビットの最上位ビットを持つビットプレーンに属するビット・シンボルが各々エントロピ符号化される。これらのビット・シンボルは、例えば図２に図示のように、所定の走査順でエントロピ符号化される。エントロピ符号化ステップ３０８は、入力として符号化対象ビット・シンボルとそのコンテキストとをとる。該コンテキストはＪＰＥＧ２０００に従って好適に決定される。同時に、シグニフィカンス・プロパゲーション・パスとマグニチュード・リファインメント・パスとの中で処理の対象となる位置のリストが生成され、その結果、本方法は次のビットプレーン内でのビットの効率的処理が可能となる。最初のクリーンアップ・パス３０８中、ビット・シンボルが有意であることが判明した場合、その関連する位置が現在のＭＲリストに追加される。最初のクリーンアップ符号化パス中に本方法は、有意であることが判明した位置の３×３の近傍内の非有意近傍も決定する。次いで、これらの位置は現在のＳＰリストに追加される。
【００３３】
ステップ３０８の完了後、本方法は判定ブロック３１０へ進み、そこで処理の対象となるビットプレーンがさらに存在するかどうかのチェックが行われる。もし存在すれば、本方法はステップ３１２へ進み、そこで次のビットプレーンのビット・シンボルが検索される。
【００３４】
次いで、本方法は、関連するビット・シンボルを現在のビットプレーンのシグニフィカンス・プロパゲーション・パスで処理するステップ３１４へ進む。このステップ３１４で、現在のＳＰリスト内の位置に対応する現在のビットプレーン内のビット・シンボルがエントロピ符号化される。ＳＰ符号化パス３１４中、ビット・シンボルが有意であることが判明した場合、その関連する位置が新しいＭＲリストに追加される。２回の符号化を避けるために、次のクリーンアップ符号化パス３１８の完了後、この新しいＭＲリストは現在のＭＲリストと併合される。またＳＰ符号化パス３１４中、ビット・シンボルが有意であることが判明したとき、本方法はその有効ビット・シンボルの位置（Ｐ）の非有意近傍を決定する。次いで、本方法は、走査順でその位置（Ｐ）に先行するこれらの非有意近傍の中のいずれの非有意近傍も新しいＳＰリストに追加する。一方、本方法は、走査順でその位置（Ｐ）の後にあるこれらの非有意近傍のいずれの非有意近傍をも現在のＳＰリストに追加する。次いで、本方法は更新された現在のＳＰリストの再索引化を行う。ＳＰ符号化パス３１４中、本方法は、更新された現在のリストＳＰと現在のＭＲリストとを用いてＮリストの生成も開始する。
【００３５】
ＳＰ符号化パス３１４の完了後、本方法はマグニチュード・リファインメント符号化パス３１６へ進む。このステップ３１６で、マグニチュード・リファインメント・リスト内の位置に対応する現在のビットプレーン内のすべてのビット・シンボルがエントロピ符号化される。
【００３６】
ＭＲ符号化パス３１６の完了後、本方法はクリーンアップ符号化パス３１８へ進む。クリーンアップ符号化ステップ３１８で、（前回の符号化パス中生成された）現在のクリーンアップＮリスト内の位置に対応する現在のビットプレーン内のすべてのビット・シンボルがエントロピ符号化される。クリーンアップ符号化パス３１８中、ビット・シンボルが有意であることが判明したとき、その関連する位置は新しいＭＲリストに追加される。本方法は新しいＭＲリスト内の位置リストの非有意近傍も決定する。次いで、これらの非有意近傍の位置はクリーンアップ・リストから削除され、新しいＳＰリストに追加される。次いで、新しいＭＲリストと新しいＳＰリストはそれぞれ現在のＭＲリストとＳＰリストと併合される。次いで、新しく併合されたＭＲとＳＰリストとは走査順に従って再索引化される。
【００３７】
クリーンアップ符号化パス３１８の完了後、本方法は任意のさらなるビットプレーン処理を行うために判定ブロック３１０へ戻る。判定ブロックが真（イエス）を返した場合、すなわち、処理の対象となるさらなるビットプレーンが存在しない場合本方法は終了する（３００）。好適には、本方法は、最上位ビットプレーンから所定の最下位ビットプレーンまで有効ビットを含むビットプレーンを処理することが望ましい。符号化段階中、本方法は、符号化されたビット・ストリームのヘッダへ情報を追加する。該情報によって最上位ビットプレーンと所定の最下位ビットプレーンとが特定される。復号段階では、本方法は符号化されたビット・ストリームの復号化時にこのヘッダ情報を使用する。
【００３８】
次に図４を参照すると、図３に図示のエントロピ符号化法で用いられる最初のクリーンアップ符号化ステップ３０８のフローチャートが示されている。クリーンアップ符号化ステップ３０８は、その中に有効ビットを持つ最上位ビットプレーンの処理を開始する。最初のクリーンアップ符号化ステップ３０８の開始時に、シグニフィカンス・プロパゲーション（ＳＰ）リストとマグニチュード・リファインメント（ＭＲ）リストは空であり、すべての係数はこのクリーンアップ・パス中符号化される。このビットプレーンの各係数について、最初のクリーンアップ符号化ステップ３０８は、以下の演算を実行する：（１）係数がこのビットプレーン内で有意である場合、その係数はＭＲリストに追加される。（２）その係数の３×３の近傍のいずれかの係数が有意であって、しかも、その係数自身が有意でない場合、その係数はＳＰリストに追加される。
【００３９】
最初のクリーンアップ符号化ステップ３０８の最後に、ＭＲリストとＳＰリストとは完全なものとなり、次のステップ用として使用される準備ができている。最初のクリーンアップ符号化ステップ３０８は、前処理ステップ４１２中このビットプレーン内で係数の各ビット・シンボルを符号化することにより、さらに、現在前処理されている（４１２）係数の有効値に関する情報、および、有意係数の３×３の近傍の範囲内の任意の非有意近傍に関する情報をメモリに書き込むことにより、これらの演算を実行する。以下さらに詳細に説明するように、ビット・シンボルが前処理されている間、該メモリは更新を受ける継続状態にある。クリーンアップ符号化ステップ３０８は、以下さらに詳細に説明するように、メモリに書き込まれた情報を利用することにより、後処理ステップ４１８中、係数をＭＲリストに加えるべきか、それとも、ＳＰリストに加えるべきかについての決定も行う。
【００４０】
最初のクリーンアップ符号化ステップ３０８はサブ・プロシージャであり、有効ビットをその中に持つ最上位ビットプレーンを処理する主要な方法３００によって呼び出される。最初の符号化ステップ３０８はステップ４０２から始まる。次いで、このサブ・プロシージャは変数ｉとｊが双方とも１にセットされるステップ４０４と４０６へ進む。変数ｊは列カウンタとして、変数ｉはストリップ・カウンタとして使用され、最初のクリーンアップ符号化ステップ３０８がＪＰＥＧ２０００の走査順でコード・ブロックのビットプレーンの列とストリップを処理することが可能になる。コード・ブロックはビット・シンボルのＮ列のＭストリップを持つ。ＭとＮの値はコード・ブロックのサイズに応じて変動する。
【００４１】
次いで、最初のクリーンアップ符号化ステップ３０８は判定ブロック４０８へ進み、ここで、ストリップ・カウンタｉが１以上か、コード・ブロック内のストリップＭの総数以下であるかどうかのチェックが行われる。判定ブロック４０８がイエス（真）を返した場合、最初のクリーンアップ符号化ステップ３０８は判定ブロック４１０へ進む。次いで、判定ブロック４１０は、列カウンタｊがコード・ブロック内で１以上であるか、列Ｎの総数以下であるかをチェックする。判定ブロック４１０がイエス（真）を返した場合、最初のクリーンアップ符号化ステップ３０８は前処理ステップ４１２へ進み、この前処理ステップ４１２はそのビットプレーンのｉ番目のストリップのｊ番目の列を前処理し、メモリに情報を書き込む。この前処理ステップ４１２について図５を参照しながら以下さらに詳細に後述する。前処理ステップ４１２の完了後、最初のクリーンアップ符号化ステップ３０８はステップ４２０へ進む。判定ブロック４０８と４１０のうちのいずれか一方がノー（偽）を返した場合、最初のクリーンアップ符号化ステップ３０８は前処理ステップ４１２をバイパスし、ステップ４２０へ直接進む。
【００４２】
同時に、最初のクリーンアップ符号化ステップ３０８は判定ブロック４１４へ進み、そこでストリップ・カウンタｉが２以上でかつ（Ｍ＋１）以下であるかどうかのチェックが行われる。但し、Ｍはコード・ブロック内のストリップの総数である。判定ブロック４１４がイエス（真）を返した場合、最初のクリーンアップ符号化ステップ３０８は判定ブロック４１６へ進み、列カウンタｊが３以上で、かつ（Ｎ＋２）以下であるかどうかのチェックが行われる。但し、Ｎはストリップ内の列の総数である。判定ブロック４１６がイエス（真）を返した場合、最初のクリーンアップ符号化ステップ３０８は、（ｉ−１）番目のストリップの（ｊ−２）番目の列を後処理する後処理ステップ４１８へ進む。後処理ステップ４１８は、メモリに既に書き込まれた情報を利用して、係数をＭＲリストに加えるべきか、それともＳＰリストに加えるべきかについての決定を行う。この後処理ステップ４１８について図６を参照しながら以下さらに詳細に後述する。後処理ステップ４１８の完了後、最初のクリーンアップ符号化ステップ３０８はステップ４２０へ進む。判定ブロック４１４と４１６のうちいずれか一方がノー（偽）を返した場合、サブ・プロシージャ３０８はこの後処理ステップ４１８をバイパスし、ステップ４２０へ直接進む。このようにして、後処理ステップ４１８が（ｉ−１）番目のストリップの（ｊ−２）番目の列を処理している間、前処理ステップ４１２はｉ番目のストリップのｊ番目の列を処理する。
【００４３】
ステップ４２０中、最初のクリーンアップ符号化ステップ３０８が列カウンタｊを１だけ増分する。次いで、最初のクリーンアップ符号化ステップ３０８は判定ブロック４２２へ進み、そこで列カウンタｊが（Ｎ＋２）以下であるかどうかのチェックが行われる。但し、Ｎはストリップ内の列の総数である。判定ブロック４２２がイエス（真）を返した場合、最初のクリーンアップ符号化パス３０８は次の列ｊを処理する判定ブロック４０８と４１４へ戻る。一方、判定ブロック４２２がノー（偽）を返した場合、最初のクリーンアップ符号化ステップ３０８はステップ４２４へ進み、そこでストリップ・カウンタｉは１だけ増分される。次いで、最初のクリーンアップ符号化ステップ３０８が判定ブロック４２６へ進み、そこでストリップ・カウンタｉが（Ｍ＋１）以下であるかどうかのチェックが行われる。但し、Ｍはコード・ブロック内のストリップの総数である。判定ブロック４２６がイエス（真）を返した場合、最初のクリーンアップ符号化ステップ３０８は次のストリップのさらなる処理のためにステップ４０６へ戻る。
【００４４】
上述のように、クリーンアップ符号化ステップ３０８はメモリに書き込まれた情報を読み出して、係数をＭＲリストに加えるべきか、それとも、ＳＰリストに加えるべきかについての決定を行う。このメモリは、現在のストリップ・レジスタ、前回のストリップ・レジスタ、次のストリップ・ライン・ストア、前回のストリップ・ライン・ストア、および前回のストリップ・ライン・ストアの形になる。
【００４５】
前回のストリップ・レジスタと現在のストリップ・レジスタとは、４つの行とＮ列を有する４×Ｎレジスタ配列として各々構成される。この配列は合計で４Ｎのエントリを有する。前のストリップ・レジスタと現在のストリップ・レジスタとからなる本構成はダブル・バッファリング構成として機能する。前のストリップ・レジスタの４つの行は、それぞれ、コード・ブロックの（ｉ−１）番目のストリップの連続する４つの行に対応し、前のストリップ・レジスタのＮ列はコード・ブロックの（ｉ−１）番目のストリップのＮ列に対応する。一方、現在のストリップ・レジスタの４つの行はそれぞれ、コード・ブロックのｉ番目のストリップの連続する４つの行に対応し、現在のストリップ・レジスタのＮ列はコード・ブロックのｉ番目のストリップのＮ列に対応する。前のストリップ・レジスタと現在のストリップ・レジスタの各エントリは、コード・ブロックの係数に対応しており、２つのビットＮ、Ｓを有する。Ｓビットは、そのエントリに対応する係数が有意であるかどうかを示す。Ｎビットはそのエントリに対応する係数が有意係数の３×３の近傍に存在するかどうかを示す。現在のストリップ・レジスタは、前処理ステップ４１２中継続的に更新される。例えば、ｉ番目のストリップのｊ番目の列の前処理４１２中、現在のストリップ・レジスタのｊ番目の列のＳビットが更新され、コード・ブロックのｉ番目のストリップのｊ番目の列の係数の有効値に応じて対応するＮビットが列（ｊ−１）、ｊ、（ｊ＋１）について更新される。ｉ番目のストリップの最後の列の前処理（ステップ４２４中）の完了後、現在のストリップ・レジスタの内容が前のストリップ・レジスタへ出力され、現在のストリップ・レジスタのＮ、Ｓビットはゼロにリセットされる。したがって、（ｉ＋１）番目のストリップの前処理中の前のストリップ・レジスタには、ｉ番目のストリップに対する現在のストリップ・レジスタの完全な更新が含まれる。前処理ステップ４１２がｉ番目のストリップ用の現在のストリップ・レジスタを更新中同時に、後処理４１８は前のストリップ・レジスタからＮ、Ｓビットを読み出している。
【００４６】
前回のストリップ・ライン・ストアと次のストリップ・ライン・ストアとは、１×Ｎライン・ストアとして各々構成される。前回のストリップ・ライン・ストアと次のストリップ・ライン・ストアとから成る本構成はダブル・バッファリング構成として機能する。前回のストリップ・ライン・ストアはｉ番目のストリップの第１の行に対応する。前回のストリップ・ライン・ストアは、その位置の３×３の近傍内の（ｉ−１）番目のストリップの最後の行に有意係数を持つ位置であって、ｉ番目のストリップの第１の行内の非有意係数の位置の列番号を格納する。次のストリップ・ライン・ストアの行は、（ｉ＋１）番目のストリップの第１の行に対応する。次のストリップ・ライン・ストアは、その位置の３×３の近傍内のｉ番目のストリップの最後の行に有意係数を持つ位置であって、（ｉ＋１）番目のストリップの第１の行の非有意係数の位置の列番号を格納する。いずれの場合も、列番号はＪＰＥＧ２０００の走査順でライン・ストアの先頭から次々にライン・ストア内に格納される。いずれの１回についても、次のストリップ・ライン・ストアと前回のストリップ・ライン・ストアの双方ともＮ列番号まで格納することができる。Ｎ未満の列番号しかない場合、ライン・ストアの残りのエントリと最後の部分はブランク状態のままに放置される。次のストリップ・ライン・ストアは、前処理ステップ４１２中継続的に更新される。例えば、ｉ番目のストリップのｊ番目の列の前処理４１２中、ｉ番目のストリップのｊ番目の列の有意係数の３×３の近傍の範囲内に在る、（ｉ＋１）番目のストリップの第１の行の範囲内のいずれの位置の列番号も、次のストリップ・ライン・ストアに追加される。ｉ番目のストリップの最後の列（ステップ４２４中）の前処理の完了後、次のストリップ・ライン・ストアの内容は前回のストリップ・ライン・ストアへ出力され、次のストリップ・ライン・ストアのエントリはゼロにリセットされる。したがって、（ｉ＋１）番目のストリップの前処理中の前回のストリップ・ライン・ストアには、ｉ番目のストリップに対する次のストリップ・ライン・ストアの完全な更新が含まれる。ｉ番目のストリップの処理中の前処理ステップ４１２は、（ｉ＋１）番目用のストリップの次のストリップ・ライン・ストアを更新し、ｉ番目のストリップの前回のストリップ・ライン・ストアを読み出す。
【００４７】
前回のストリップ・ライン・ストアは１×４ライン・ストアとして構成される。前回のストリップ・ライン・ストアの行は、列（ｊ−２）、（ｊ−１）、ｊ、（ｊ＋１）の（ｉ−１）番目のストリップの最後の行に対応する。前回のストリップ・ライン・ストアは、その位置の３×３の近傍のｉ番目のストリップの第１の行に有意係数を持つ位置であって、（ｉ−１）番目のストリップの最後の行の非有意係数の位置の列番号を格納する。列番号はＪＰＥＧ２０００の走査順で格納される。前回のストリップ・ライン・ストアは前処理ステップ４１２中継続的に更新される。例えば、ｉ番目のストリップのｊ番目の列の前処理４１２中、ｉ番目のストリップのｊ番目の列の有意係数の３×３の近傍の範囲内にある（ｉ−１）番目のストリップの最後の行の範囲内の任意の位置の列番号は、（予めそこに存在しない場合）前回のストリップ・ライン・ストアに追加される。同時に、後処理ステップ４１８は、前回のストリップ・ライン・ストアの第１のエントリを読み出している。これらの列番号は、ライン・ストアの先頭から始まるライン・ストアの前回のストリップ・ライン・ストアの中にＪＰＥＧ２０００の走査順に次々に格納される。いずれの１回についても、前回のストリップ・ライン・ストアは４までの列番号を格納することができる。４未満の列番号しかない場合、前回のストリップ・ライン・ストアの残りのエントリと最後の部分はブランク状態のままに放置される。
【００４８】
次に図５を参照して、図４に描かれているようなｉ番目のストリップのｊ番目の列の前処理ステップ４１２のフローチャートが更に詳細に説明する。前処理ステップ４１２はステップ５０２から始まり、ステップ５０４へ進む。ここで、ｉ番目のストリップのｊ番目の列の第１のビット・シンボルが検索される。この検索対象ビット・シンボルは、ｊ番目の列でかつｉ番目のストリップのＪＰＥＧ２０００の走査順で最初（即ち、行１）のビット・シンボルである。次いで、前処理ステップ４１２はステップ５０６へ進み、そこでＪＰＥＧ２０００に従って検索対象ビット・シンボルに対する符号化とコンテキスト生成とが行われる。符号化の完了後、ステップ５０６は必要に応じて有効値テーブルの更新も行う。係数の第１のノンゼロ・ビットプレーン値が符号化されると、係数の有意状態は（１）に変化し、テーブルの配列の対応するエントリは（１）にリセットされる。具体的には、ある係数に属する現在の符号化されたビット・シンボルが（１）である場合、有効値テーブルに格納される係数の有効値は（１）にセットされる。ステップ５０６の完了後、前処理ステップ４１２は判定ブロック５０８へ進み、そこで符号化されたビットが有意な係数に属するかどうかのチェックが行われる。判定ブロック５０８がイエス（真）を返した場合、前処理ステップ４１２はステップ５１０へ進み、そこで検索対象のビット・シンボルに対応するｊ番目の列であって、現在のストリップ・レジスタのｊ番目の列のビットＳは（１）にセットされる。判定ブロック５０８がノー（偽）を返した場合（即ち、係数が有意ではない場合）、前処理ステップ４１２は判定ブロック５３４へ直接進む。
【００４９】
ステップ５１０の後、前処理ステップ４１２はループ５１４から５２６へ進み、そこで現在の有意係数の３×３の近傍内の各非有意近傍が順に処理される。ステップ５１４中、前処理ステップ４１２は、（もし存在する場合には）現在の有意係数の非有意近傍を取得する。ステップ５１４は、有効値テーブルを調べることにより現在の有意係数の非有意近傍を決定する。非有意近傍が存在しなければ、前処理ステップ４１２は判定ブロック５３４へ直接進む（図示せず）。一方、非有意近傍が存在する場合、前処理ステップ４１２は判定ブロック５１６へ進み、そこで現在の近傍が前回のストリップ（ｉ−１）内にあるかどうかのチェックが行われる。判定ブロック５１６がイエス（真）を返した場合、前処理ステップ４１２はステップ５１８へ進み、そこで現在の近傍の列番号が前回のストリップ・ライン・ストアに追加される。ステップ５１８の後、前処理ステップ４１２は判定ブロック５２６へ進む。一方、判定ブロック５１６がノー（偽）を返した場合、前処理ステップ４１２は判定ブロック５２０へ進み、そこで現在の近傍が次のストリップ（ｉ＋１）にあるかどうかのチェックが行われる。判定ブロック５２０がイエス（真）を返した場合、前処理ステップ４１２はステップ５２２へ進み、そこで列番号が次のストリップ・ライン・ストアに追加される。ステップ５２２後、前処理ステップ４１２は判定ブロック５２６へ進む。一方、判定ブロック５２０がノー（偽）を返した場合、前処理ステップ４１２はステップ５２４へ進む。ステップ５２４中、前処理ステップ４１２は、現在の近傍に対応する現在のストリップ・レジスタのエントリ内でビットＮを（１）にセットする。ステップ５２４後、前処理ステップ４１２は判定ブロック５２６へ進む。判定ブロック５２６は、ループ５１４〜５２６によってまだ処理されていない近傍が、現在の有意係数の３×３の近傍内にさらに存在するか否かをチェックする。判定ブロック５２６がイエス（真）を返した場合、現在の有意係数の次の近傍の処理を行うために前処理ステップ４１２はステップ５１４へ戻る。判定ブロック５２６がノー（偽）を返した場合、前処理ステップはステップ５２８へ進む。
【００５０】
ステップ５２８中、前処理ステップ４１２は、ＪＰＥＧ２０００の走査順に従う前回のストリップ・ライン・ストアの第１のエントリである前回のストリップ・ライン・ストアの先頭を検索し、それを変数headSPに割り振る。ｉ番目のストリップの最初の前処理ステップ４１２中（即ち、ｊ＝１）、前回のストリップ・ライン・ストアは、ｉ番目のストリップの第１の行に対応し、次いで、それらの３×３の近傍の（ｉ−１）番目のストリップ内の有意係数を持つ位置の列番号を格納する。従って、ｉ番目のストリップの最初の前処理ステップ４１２（即ち、ｊ＝１）中、ある位置のｉ番目のストリップの第１の行の前回のストリップ・ライン・ストア内の変数headSPにＪＰＥＧ２０００の走査順で格納された第１列番号が含まれる。この位置は（ｉ−１）番目のストリップ内のその位置の３×３の近傍に有意係数を持つ。ステップ５２８後、前処理ステップ４１２は判定ブロック５３０へ進み、そこでｊ＝headSPかどうかのチェックが行われる。判定ブロック５３０がイエス（真）を返した場合、前処理ステップ４１２はステップ５３２へ進み、そこでＮビットは位置（１，ｊ）に対応する現在のストリップ・レジスタのエントリ用として（１）にセットされる。このようにして、（ｉ−１）番目のストリップ内の有意係数のｉ番目のストリップの非有意近傍がそれらの対応するＮビットをセットすることにより現在のストリップ・レジスタ内に特定される。また、ステップ５３２中、前処理ステップ４１２によって前回のストリップ・ライン・ストアの現在の先頭が取り除かれる。さらに、残りの列番号はすべて前回のストリップ・ライン・ストアの先頭へ一度にシフトされる。ステップ５３２の完了後、前処理ステップ４１２は判定ブロック５３４へ進む。一方、判定ブロック５３０がノー（偽）を返した場合、前処理ステップ４１２は判定ブロック５３４へ直接進む。当業者には明らかなように、前回のストリップ・ライン・ストアはＮまでの列番号を最初に格納する。前処理ステップ４１２が各列ｊ＝１，…，Ｎについて呼び出されると、前処理ステップ４１２は、判定ブロック５３０の間、前回のストリップ・ライン・ストア内に対応する列番号が存在するかどうかをチェックする。もし対応する列番号が存在すれば、非有意近傍はその列の第１の行に存在するものとして特定され、現在のストリップ・レジスタに入力され、前回のストリップ・ライン・ストアから取り除かれる。
【００５１】
判定ブロック５３４は、前処理ステップ４１２によってまだ処理されていないビット・シンボルがｊ番目の列の中に更に存在するかどうかを判定する。判定ブロック５３４がイエス（真）を返した場合、前処理ステップ４１２はステップ５３６へ進み、そこで列内の次のビット・シンボルが検索される。次いで、前処理ステップ４１２は、この検索されたビット・シンボルを処理するステップ５０６へ戻る。一方、列ｊの中にそれ以上処理すべきビット・シンボルが存在しなければ、判定ブロック５３４はノー（偽）を返し、前処理ステップ４１２は終了し（５３８）、さらなる処理を行うために最初のクリーンアップ符号化ステップ３０８へ戻る。
【００５２】
次に図６に目を転じると、図４に描かれているような、（ｉ−１）番目のストリップの（ｊ−２）番目の列の後処理ステップ４１８のフローチャートがさらに詳細に示されている。前述したように、前処理ステップ４１２がｉ番目のストリップのｊ番目の列を処理している間、後処理ステップ４１８は（ｉ−１）番目のストリップの（ｊ−２）番目の列を処理する。
【００５３】
後処理ステップ４１８はステップ６０２から始まり、ステップ６０４へ進み、そこで変数position1は（１，ｊ−２）にセットされる。この変数position1は、後処理ステップによって処理される前のストリップ・レジスタ内に現在位置の（行、列）座標を格納する。ステップ６０４の完了後、後処理ステップ４１８はステップ６１０へ進み、そこで前回のストリップ・ライン・ストアの先頭に格納されたエントリが検索され、変数headSPの中に格納される。この変数headSPは、或る位置の３×３の近傍に在るｉ番目のストリップの中に有意係数を持つ（ｉ−１）番目のストリップの中に位置の列番号を格納する。前回のストリップ・ライン・ストアが空の場合、ステップ６０６は変数headSPをヌルにセットする。
【００５４】
ステップ６０６の完了後、後処理ステップ４１８は判定ブロック６０８へ進み、そこで変数headSP＝（ｊ−２）かどうかのチェックが行われる。判定ブロック６０８がイエス（真）を返した場合、後処理ステップ４１８はステップ６１０へ進み、そこで変数positon2は（4、headSP）にセットされる。この変数positon2は、（ｉ−１）番目のストリップ内のビット・シンボルの（行、列）を示し、該シンボルはｉ番目のストリップ内のその３×３の近傍に有意係数を持っている。判定ブロック６０８がノー（偽）を返した場合、この変数positon2はヌルにセットされる（６１２）。ステップ６１２の完了後、後処理ステップ４１８はステップ６１４へ進む。
【００５５】
ステップ６１４中、後処理ステップ４１８は変数position1とpositon2を比較し、ＪＰＥＧ２０００の走査順でposition1がpositon2より前に存在するかどうかを判定する。存在するならば、後処理ステップ４１８は変数winning_position内に変数position1を格納する。存在しなければ、後処理ステップ４１８は変数winning_positionに変数positon2を格納する。ステップ６１４の完了後、後処理ステップ４１８は判定ブロック６１６へ進み、そこで変数winning_positionに格納された座標が変数positon2（即ち、前回のストリップ・ライン・ストア）であるかどうかのチェックが行われる。
【００５６】
判定ブロック６１６がイエス（真）を返した場合、後処理ステップはステップ６１８へ進み、そこでheadSPに対応する前回のストリップ・ライン・ストアの先頭が取り除かれる。また、前回のストリップ・ライン・ストアの残りのエントリは先頭へ１だけ各々シフトされる。ステップ６１８の完了後、後処理ステップはステップ６２０へ進み、そこで変数winning_positionに格納された位置に対応する前のストリップ・レジスタ内の位置にあるＮビットは（１）にセットされる。ステップ６２０の完了後、後処理ステップ４１８は判定ブロック６２２へ進む。判定ブロック６１２がノー（偽）を返した場合、後処理ステップは判定ブロック６２２へ直接進む。
【００５７】
判定ブロック６２２は、変数winning_positionに格納された位置に対応する前のストリップ・レジスタ内の位置のＳビットが（１）であるかどうかをチェックする。判定ブロック６２２がイエス（真）を返した場合、後処理ステップ４１８はステップ６２４へ進み、そこで変数winning_positionに格納された位置はＭＲリストに追加される。ステップ６２４の完了後、後処理ステップ４１８は判定ブロック６３０へ進む。判定ブロック６２２がノー（偽）を返した場合、後処理ステップ４１８は判定ブロック６２６へ進む。判定ブロック６２６は、変数winning_positionに格納された位置に対応する前のストリップ・レジスタ内の位置のＮビットが（１）であるかどうかをチェックする。判定ブロック６２６がイエス（真）を返した場合、後処理ステップ４１８はステップ６２８へ進み、そこで変数winning_positionに格納された位置はＳＰリストに追加される。ステップ６２８の完了後、後処理ステップ４１８は判定ブロック６３０へ進む。判定ブロック６２６がノー（偽）を返した場合、後処理ステップ４１８は判定ブロック６３０へ直接進む。
【００５８】
判定ブロック６３０は、（ｊ−２）番目の列の中に処理の対象となる位置がさらに存在するかどうかをチェックする。すなわち、判定ブロック６３０は、変数winning_positionに格納された現在位置の行が４に等しいかどうかをチェックする。判定ブロック６３０がノー（偽）を返した場合、後処理ステップ４１８はステップ６３２へ進み、そこで変数position1内の行番号は（１）だけ増分される。ステップ６３２後、後処理ステップ４１８はステップ６０６へ進み、そこで変数position1に格納された新しい値に対して後処理４１８が再開される。一方、判定ブロック６３０がイエス（真）を返した場合、後処理ステップ４１８は終了し（６３４）、更なる処理を行うためにクリーンアップ符号化ステップ３０８へ戻る。
【００５９】
上記から解るように、ｉ番目のストリップに対する前処理ステップ４１２は、現在のストリップ・レジスタ内に格納するために現在のＮ、Ｓビットを生成する。これらのＮ、Ｓビットは、ｉ番目のストリップ用として前処理ステップの終了時に存在し、次いで、前のストリップ・レジスタへ出力される。ｉ番目のストリップの前処理ステップ４１２と同時に、後処理ステップ４１８は、前のストリップ・レジスタに現在格納されている（ｉ−１）番目のストリップのＮ、Ｓビットを処理する。このＮ、Ｓビットは、前回の前処理ステップ４１２中（ｉ−１）番目のストリップ用として生成されたものである。ｉ番目のストリップの前処理ステップ４１２は、ｉ番目のストリップ内の有意係数とその非有意近傍とを特定し、現在のストリップ・レジスタの対応する位置のＮ、Ｓビットとしてそれらを格納する。前処理ステップ４１２は、（ｉ−１）番目のストリップ内の有意係数のｉ番目のストリップの第１の行のいずれの非有意近傍も特定し、現在のレジスタの対応する位置にＮビットとしてこれらを格納する。ｉ番目のストリップの前処理ステップ４１２は、前回のストリップ・ライン・ストアに現在格納されている任意のこのような非有意近傍の列番号を検索することにより後者の処理を行う。これらの非有意近傍は（ｉ−１）番目のストリップの前回の前処理ステップで特定され、次のストリップ・ライン・ストアに格納され、（ｉ−１）番目のストリップの前処理ステップの最後に、前回のストリップ・ライン・ストアへ出力される。ｉ番目のストリップの前処理ステップ４１２によって、ｉ番目のストリップの第１の行内の有意係数に起因する非有意近傍であって、（ｉ−１）番目のストリップの最後の行内のいずれの非有意近傍も特定される。前処理ステップ４１２は、これらの非有意近傍の列番号を前回のストリップ・ライン・ストアに追加する。次いで、（ｉ−１）番目のストリップに対する後処理ステップ４１８は、前回のストリップ・ライン・ストアの中からこれらの列番号を検索し、前のストリップ・レジスタ内の任意の対応するＮビットを更新する。（ｉ−１）番目のストリップに対する後処理ステップ４１８は、更新された前のストリップ・レジスタに格納されているＮ、Ｓビットを利用して、ＳＰリスト又はＭＲリストに追加が可能な位置を特定する。具体的には、１にセットされたＳビットを有する更新された前のストリップ・レジスタ内の位置はＭＲリストの中に格納され、Ｓ＝１とＮ＝０を持つ更新された前のストリップ・レジスタ内の位置がＳＰリストの中に格納される。
【００６０】
図３に戻ると、最初のクリーンアップ符号化ステップ３０８の完了後、本方法は判定ブロック３１０へ進み、そこで処理の対象となるビットプレーンがさらに存在するかどうかのチェックが行われる。もし存在すれば、本方法はステップ３１２へ進み、そこで次のビットプレーンのビット・シンボルが検索される。次いで、本方法は、現在のビットプレーンのシグニフィカンス・プロパゲーション・パスで、関連するビット・シンボルの処理を行うステップ３１４へ進む。
【００６１】
次に図７Ａと図７Ｂに目を転じると、図３のシグニフィカンス・プロパゲーション（ＳＰ）符号化ステップ３１４のフローチャートがさらに詳細に示されている。この符号化ステップ３１４は、最初のクリーンアップ符号化ステップ３０８の後に最初続き、その後、初期ビットプレーンの後の各ビットプレーン用のクリーンアップ符号化ステップ３１８に続く。ＳＰ符号化ステップ３１４は、エントロピ符号化法３００と呼ばれサブ・プロシージャの形をとる。この符号化ステップ３１４は、現在のＳＰリスト（本明細書では、以後オリジナルのＳＰリストと呼ぶ）が処理を行うためにＳＰ符号化ステップ３１４へ渡されたところから始まる（７０２）。前回の最初のクリーンアップ・ステップ３０８又はクリーンアップ符号化ステップ３１８によって、このオリジナルのＳＰリストは生成される。ＳＰ符号化ステップ３１４は、ＳＰ符号化ステップ３１４へ渡されるオリジナルのＳＰリストと、近傍ＳＰリストと、次のストリップＳＰリストと、前回のストリップＳＰリストと、新しいＳＰリストの５つのリストを利用する。ＳＰ符号化パス３１４によって後者の４つのリストが生成される。近傍ＳＰリストと、前回のストリップＳＰリストと、次のストリップＳＰリストとは、それらのリストの利用がＳＰ符号化ステップ３１４に限定されるという点でローカルなものである。一方、生成された新しいＳＰリストと更新されたオリジナルのＳＰリストとはステップ３１８中さらなる処理を行うためにエントロピ符号化法へ渡される。
【００６２】
現在のＳＰ符号化ステップ２１４中後で有意になる係数である、このリストに格納されている位置に対応する任意の係数をタグ付けによって特定するために、ＳＰ符号化ステップ３１４中オリジナルのＳＰリストの更新を行うことができる。この目的のために、オリジナルのＳＰリストの各エントリは、そのロケーション３×３の近傍に有意係数を有するロケーションであって、非有意係数の現在のビットプレーン内のビット・シンボルのロケーションを示す（行、列）座標と、現在のＳＰ符号化ステップ２１４後にビット・シンボルの有効値を示すフラグとを有する。
【００６３】
新しいＳＰリストは、そのロケーションの３×３の近傍に任意の新しい有意係数を持つ非有意係数のビット・シンボルのロケーションの（行、列）座標を有する。これらの新しい有意係数は、現在のビットプレーン内にビット・シンボルを持つ、符号化された有意係数であり、これらの有意係数の有意状態は現在のＳＰ符号化ステップ３１４中、１に変化する（有意へ変わる）。現在のＳＰ符号化ステップ３１４中後で有意になる係数である、このリストに格納された位置に対応する任意の係数をタグ付けによって特定するために、ＳＰ符号化ステップ３１４中新しいＳＰリストの更新を行うことができる。この目的のために、新しいＳＰリストの各エントリは、そのロケーションの３×３の近傍に新しい有意係数を有するロケーションであって、非有意係数のビット・シンボルのロケーションの（行、列）座標と、現在のＳＰ符号化ステップ３１４後にビット・シンボルの有効値を示すフラグとを有する。
【００６４】
近傍ＳＰリストはいくつかのビット・シンボルのコード・ブロックの範囲内にロケーションの（行、列）座標を有する。近傍ＳＰリストは新しいＳＰリストのサブセットである。すなわち、近傍ＳＰリスト内のすべての位置はこの新しいリストの中に含まれる。近傍ＳＰリストには、ＳＰ符号化ステップ３１４中復号化されたばかりの現在の有意係数の３×３の近傍の範囲内に、非有意係数の位置（但し、必ずしも全ての位置ではない）が含まれる。近傍ＳＰリストは、現在の有意係数と同じコード・ブロックのストリップ内に在り、かつ、ＪＰＥＧ２０００の走査順で現在の有意係数の後に在る、３×３の近傍の範囲内の位置しか格納しない。
【００６５】
次のストリップＳＰリストは、ＳＰ符号化ステップ３１４中有意であることが判明した、現在のストリップ内の係数の３×３の近傍の範囲内の次のストリップの第１の行の範囲内に非有意係数のロケーションの列座標を有する。次のストリップＳＰリストは、近傍ＳＰリスト内のすべての位置が新しいリストに含まれるという点で、新しいＳＰリストのサブセットである。
【００６６】
前回のストリップＳＰリストは、ＳＰ符号化ステップ３１４中有意であることが判明した、前回のストリップ内の係数の３×３の近傍の範囲内の現在のストリップの第１の行の範囲内に非有意係数のロケーションの列座標を有する。
【００６７】
開始後、ＳＰ符号化ステップ３１４は初期化ステップ７０４へ進み、そこで近傍ＳＰリストに対するエントリと、次のストリップＳＰリストと、前回のストリップＳＰリストと、新しいＳＰリストとがゼロ（０）にリセットされる。初期化ステップ７０４後、サブ・プロシージャは判定ブロック７０６へ進み、そこでオリジナルのＳＰリスト内に何らかの位置が存在するかどうかのチェックが行われる。判定ブロック７０６がノー（偽）を返した場合、ＳＰ符号化ステップ３１４は終了し（７１４）、エントロピ符号化法はＭＲ符号化ステップ３１６へ進む。コード・ブロックの範囲内のすべての位置が有意で、ＭＲ符号化ステップ３１６中符号化の対象となる場合、上記の事態が生じることもある。判定ブロック７０６がイエス（真）を返した場合、ＳＰ符号化ステップ３１４はループ（ステップ７１０〜７２８）と、クリーンアップ・リスト生成ステップ７０８とへ同時に進む。ＳＰ符号化ステップ３１４がＳＰ位置を符号化し、上述のＳＰリストを生成している間、クリーンアップ・リスト生成ステップ７０８はクリーンアップ・リストを生成する。以下より詳細にクリーンアップ・リスト生成ステップ７０８について説明する。
【００６８】
ループ（７１０〜７２８）は、ループの各パスについてオリジナルのＳＰリスト内と、近傍ＳＰリスト内と、前回のストリップＳＰリスト内の各位置を処理する。ループの任意のパス中にＳＰ符号化ステップ３１４は、オリジナルのＳＰリスト内と、近傍ＳＰリスト内と、前回のストリップＳＰリスト内の次の位置であって、前回のパス中検索されなかった次の位置を検索する（７２０）。これらのリスト内の位置は、ＪＰＥＧ２０００の走査順に従ってループのパス中次々に検索される。これらの位置の検索方法について図８を参照しながら以下さらに詳細に後述する。一方、これらのリストの範囲内に前に検索されなかった位置がそれ以上存在しなかった場合、ＳＰ符号化ステップ３１４はループ（ステップ７１０〜７２８）から抜けてステップ７１２へ進む。
【００６９】
初期化ステップ７０４の完了後、ＳＰ符号化ステップ３１４は判定ブロック７０６へ進み、そこでオリジナルのＳＰリスト内、近傍ＳＰリスト内及び前回のストリップＳＰリスト内に位置がさらに存在するかどうかのチェックが行われる。これらのリストの範囲内に残りの位置が存在すれば、判定ブロックはイエス（真）を返し、ＳＰ符号化ステップ３１４は判定ブロック７１０へ進む。
【００７０】
判定ブロック７１６はコード・ブロックの現在のストリップ内、オリジナルのＳＰリスト内、近傍ＳＰリスト内及び前回のストリップＳＰリスト内に、前に検索されなかった位置がさらに存在するかどうかをチェックする。ＳＰ符号化ステップ３１４は、第１のストリップからコード・ブロックのストリップを処理し、ＪＰＥＧ２０００に記載されている走査順で、最後のストリップまでずっと処理を継続する。判定ブロック７１６の最初のパス中、現在のストリップはコード・ブロックの第１のストリップである。判定ブロック７１６がノー（偽）を返した場合、ＳＰ符号化ステップ３１４はステップ７１８へ進み、そこで次のストリップＳＰリスト内の列位置が前回のストリップＳＰリストへ出力され、次のストリップＳＰリストのエントリはゼロにセットされる。前述したように、次のストリップＳＰリストは、ＳＰ符号化ステップ３１４中有意であることが判明した係数である、現在のストリップ内の係数の３×３の近傍の範囲内の次のストリップの第１の行の範囲内の非有意係数のロケーションの列座標を有する。前回のストリップＳＰリストは、ＳＰ符号化ステップ３１４中有意であることが判明した係数である、前回のストリップ内の係数の３×３の近傍の範囲内の現在のストリップの第１の行の範囲内の非有意係数のロケーションの列座標を有する。ＳＰ符号化ステップ３１４は、次のストリップＳＰリストに列番号を追加し（ステップ７３８）、ＳＰ符号化コード・ブロックの任意のストリップの処理中、前回のストリップＳＰリストの中から列番号を検索する。現在のストリップの範囲内にそれ以上位置が存在しなければ、次のストリップＳＰリストの列番号が前回のストリップＳＰリストへ出力され（７１８）、次のストリップＳＰリストのエントリがゼロにセットされ、次のストリップが現在のストリップになる。ステップ７１８の完了後、ＳＰ符号化ステップ３１４はステップ７２０へ進む。
【００７１】
一方、判定ブロック７１６がイエス（真）を返した場合、ＳＰ符号化ステップ３１４はステップ７２０へ直接進む。ステップ７２０中、ＳＰ符号化ステップ３１４はオリジナルのＳＰリスト内と、近傍ＳＰリスト内と、前回のストリップＳＰリスト内の次の位置であって、ループの前回のパス中検索されなかった位置を検索する。以下これについて図８を参照しながらより詳細に説明する。ステップ７２０の完了後、ＳＰ符号化ステップ３１４はステップ７２２へ進み、そこでコンテキスト生成とビット・シンボルの符号化とがその（検索）位置において行われる。この符号化とコンテキスト生成とは、ＪＰＥＧ２０００に従って好適に行われる。符号化の完了後、ステップ７２２は必要な場合に有効値テーブルの更新も行う。係数の第１のノンゼロ・ビットプレーン値が符号化され、テーブルの配列の対応するエントリが（１）にリセットされた場合、係数の有意状態は（１）に変化する。具体的には、ある係数に属する現在の符号化されたビット・シンボルが（１）である場合、有効値テーブルに格納されるその係数の有効値は（１）にセットされる。
【００７２】
符号化ステップ７２２の完了後、ＳＰ符号化ステップ３１４は判定ブロック７２４へ進む。判定ブロック７２４では、その（検索）位置における符号化されたビット・シンボルが（１）の有意状態を持っているかどうかのチェックが行われる。判定ブロック７２４がノー（偽）を返した場合、ＳＰ符号化ステップ３１４はステップ７１０へ戻り、そこで、オリジナルのＳＰリスト内と、近傍ＳＰリスト内と、前回のストリップＳＰリスト内の次の位置であって、ループの前回のパス中検索されなかった次の位置が検索される。一方、判定ブロック７２４がイエス（真）を返した場合、ＳＰ符号化ステップ３１４はステップ７２６へ進み、そこでオリジナルのリスト内又は新しいＳＰリスト内の対応する（検索された）位置のフラグに有効なものとしてタグが付けられる。このようにして、次のクリーンアップ符号化ステップ３１８中、ＭＲリストへの後続する追加を行うためにこの位置が特定される。
【００７３】
ステップ７２６の完了後、ＳＰ符号化ステップ３１４は、新しいＳＰに非有意近傍を追加するための処理へこの非有意近傍の（行、列）座標を渡す（７３２）。これについては図１３Ａと図１３Ｂを参照しながらさらに詳細に後述する。この処理はＳＰ符号化ステップ３１４の開始から始まり、ＳＰ符号化ステップ３１４の完了で終了する。
【００７４】
ステップ７２６の完了後、ＳＰ符号化ステップ３１４はサブループ７２８〜７３８、７４０へ進み、そこで現在の符号化されたビット・シンボルを有する現在の有意係数の３×３の近傍内の非有意係数がサブループの各パスについて順に処理される。サブループ７２８〜７３８、７４０は判定ブロック７２８を有し、この判定ブロックで、サブループによって前に処理されなかったような、現在の有意係数の非有意近傍がさらに存在するかどうかのチェックが行われる。判定ブロック７２８は有効値テーブルを参照してこの判定を行う。判定ブロック７２８がノー（偽）を返した場合、ＳＰ符号化ステップ３１４はさらなる処理を行うために判定ブロック７１０へ戻る。一方、判定ブロック７２８がイエス（真）を返した場合、ＳＰ符号化ステップ３１４はステップ７３０へ進み、そこで（行、列）座標としての非有意近傍の位置が有効値テーブルから検索される。ステップ７３０の完了後、ＳＰ符号化ステップ３１４は判定ブロック７３４へ進み、そこで現在の非有意近傍の位置が、ＪＰＥＧ２０００の走査順で現在の符号化されたビット・シンボルを有する係数の位置の後に在るかどうかのチェックが行われる。判定ブロック７３４がノー（偽）を返した場合、さらなる処理を行うために、ＳＰ符号化ステップ３１４は判定ブロック７２８へ戻る。一方、判定ブロック７３４がイエス（真）を返した場合、ＳＰ符号化ステップ３１４は判定ブロック７３６へ進み、そこで現在の符号化されたビット・シンボルが属する相手先の現在のストリップ後、現在の非有意近傍が次のストリップに属するかどうかのチェックが行われる。判定ブロック７３６がイエス（真）を返した場合、ＳＰ符号化ステップ３１４はステップ７３８へ進み、そこで現在の非有意近傍の位置の列番号が次のストリップＳＰリストの最後に追加される。ステップ７３８の完了後、ＳＰ符号化ステップ３１４はさらなる処理を行うために判定ブロック７２８へ戻る。一方、判定ブロック７３８がノー（偽）を返した場合、ＳＰ符号化ステップ３１４はステップ７４０へ進み、そこで現在の非有意近傍の位置の（行、列）座標が近傍ＳＰリストの最後に追加される。ステップ７４０の完了後、ＳＰ符号化ステップ３１４はさらなる処理を行うために判定ブロック７２８へ戻る。
【００７５】
次に図８に目を転じると、ＳＰ符号化ステップ３１４のステップ７２０のフローチャートがさらに詳細に示されている。ステップ７２０はＪＰＥＧ２０００の走査順に従って、オリジナルのＳＰリスト内、近傍ＳＰリスト内、または、前回のストリップＳＰリスト内に格納される第１の位置であって、前に検索され、処理されなかった第１の位置を検索する。以上から明らかなように、オリジナルのＳＰリスト内、近傍ＳＰリスト内、及び、前回のストリップＳＰリスト内に格納された位置は、ＪＰＥＧ２０００に従ってソートされる。ステップ７２０に対する第１のコール中、３つのヘッド・ポインタはそれぞれ、オリジナルのＳＰリストへの第１のエントリと、近傍ＳＰリストへの第１のエントリと、前回のストリップＳＰリストへの第１のエントリを指している。各後続するコールについて、これらのヘッド・ポインタの中の１つはリスト内の次の項目へ移動する。ステップ７１８が次のストリップＳＰリストの内容を前回のストリップＳＰリストへ出力した場合、前回のストリップＳＰリストのためのヘッド・ポインタは、前回のストリップＳＰリストの第１のエントリにリセットされる。ヘッド・ポインタの位置は、現在のエントロピ・ステップ３１４内の、ステップ７２０への各コールの間で保持される。現在のエントロピ・ステップ３１４が完了されるとすぐにヘッド・ポインタはリセットされる。
【００７６】
ステップ７２０はステップ８０２から始まり、判定ブロック８０４、８０６、８０８へ同時に進む。判定ブロック８０４で、ステップ７２０は、ヘッド・ポインタがオリジナルのＳＰリスト内の有意な（即ち、ヌルでない）位置を指しているかどうかをチェックする。判定ブロック８０４がイエス（真）を返した場合、ステップ７２０はステップ８１２へ進み、そこでステップ７２０は、ヘッド・ポインタが指しているオリジナルのＳＰリスト内のその位置の（行、列）座標を検索し、変数origSPにこの座標を格納する。一方、判定ブロック８０４がノー（偽）を返した場合、ステップ７２０は変数origSPをヌルにセットする。判定ブロック８０６で、ステップ７２０はヘッド・ポインタが近傍ＳＰリスト内で有意な（即ち、ヌルでない）位置を指しているかどうかをチェックする。判定ブロック８０６がイエス（真）を返した場合、ステップ７２０はステップ８１６へ進み、そこでステップ７２０は、ヘッド・ポインタが指している、近傍ＳＰリスト内のその位置の（行、列）座標を検索し、変数neighSPにこの座標を格納する。一方、判定ブロック８０６がノー（偽）を返した場合、ステップ７２０は変数neighSPをヌルにセットする。判定ブロック８０８で、ステップ７２０はヘッド・ポインタが前回のストリップＳＰリストの中で有意な（即ち、ヌルでない）位置を指しているかどうかをチェックする。判定ブロック８０８がイエス（真）を返した場合、ステップ７２０はステップ８２０へ進み、そこでステップ７２０はヘッド・ポインタが指している前回のストリップＳＰリスト内のその位置の列番号を検索する。この列番号は変数nextstripSP内の座標（１、列番号）として格納される。上述のように、前回のＳＰリストは、前回のストリップのＳＰ符号化ステップ３１４中符号化された有意係数に起因する非有意近傍であって、ストリップの第１の行の任意の非有意近傍の列番号を格納する。一方、判定ブロック８０８がノー（偽）を返した場合、ステップ７２０は変数nextstripSPをヌルにセットする。
【００７７】
ステップ８１０〜８２０の完了後、ステップ７２０はステップ８２２へ進む。ステップ８２２中、変数origSPと、neighSPと、nextstripSPとに格納された位置のロケーションが比較され、これらの３つの位置から成る位置であって、ＪＰＥＧ２０００の走査順で第１となる当該位置が発見される。ステップ８２２の完了後、ステップ７２０はステップ８２４へ進み、そこでこの‘第１の’位置を含むエントリへのヘッド・ポインタは、対応するリスト内でこの第１のエントリから離れた方向へ１エントリだけ移される。比較ステップ８２２によって得られるこの‘第１の’位置は、次いで、さらなる処理を行うために、ＳＰ符号化ステップ３１４の符号化ステップ７２２とクリーンアップ・リスト生成ステップ７０８とへ渡される。次いで、ステップ７２０は終了する。
【００７８】
ＳＰ符号化ステップ３１４がステップ７１０〜７４０を実行中している間、ＳＰ符号化ステップ３１４はクリーンアップ・リスト生成ステップ７０８を実行する。これについて以下より詳細に説明する。
【００７９】
次に図１３Ａと図１３Ｂに目を転じると、非有意近傍を新しいＳＰリストに追加する処理を示すフローチャートが示されている。ＳＰ符号化ステップ３１４は、ＳＰ符号化パス３１４中有意であることが判明した係数の、非有意近傍の（行、列）座標をステップ７３２（図７Ａ）中に渡す。これらの位置は、非有意近傍を新しいＳＰリストに追加するための処理１３００へ渡される。この処理１３００は、ＳＰ符号化ステップ３１４の開始から始まり、ＳＰ符号化ステップ３１４の完了で終了する。この処理１３００の目的は、有意係数の非有意近傍の任意のオーバーラップ部分を取り除くことである。例えば、２つの有意係数からなる非有意近傍である係数が存在するため、新しいＳＰリストへの追加を１回しか必要としない場合がある。これらの非有意近傍は、新しいＳＰリストに追加され、ＪＰＥＧ２０００の走査順にＳＰリスト内でソーティングが行われる。処理１３００は、４×Ｎの前のストリップ・レジスタと、４×Ｎの現在のストリップ・レジスタと、１×Ｎの前回のストリップ・ライン・ストアと、１×Ｎの次のストリップ・ライン・ストアと、前述した１×４の前回のストリップ・ライン・ストアとを利用する。但し、Ｎはブロックの幅である。処理１３００は、最初のクリーンアップ符号化パス３０８で用いられたような前処理ステップに多少類似した方法で前処理ステップとして機能する。処理１３００は、前回のストリップ・レジスタと前回のストリップ・ライン・ストアとの内容を後処理プロセス１４００へ送る。これについては図１４を参照してさらに詳細に後述する。この後処理プロセス１４００は、最初のクリーンアップ符号化パス３０８で用いられた方法と多少類似した方法で後処理ステップとして機能する。例えば、処理１３００がｉ番目のストリップを前処理している間、処理１４００は（ｉ−１）番目のストリップを後処理していることになる。
【００８０】
前処理プロセス１３００は、ｉ番目のストリップ内の有意係数の３×３の近傍の範囲内に存在する非有意係数である、同じｉ番目のストリップ内の対応する非有意係数用の４×Ｎの現在のストリップ・レジスタのエントリのＮビットを（１）にセットする。前処理プロセス１３００はまた、（ｉ−１）番目のストリップの最後の行に在り、かつ、ｉ番目のストリップの第１の行の有意係数の３×３の近傍に在る非有意係数の列番号を前回のストリップ・ライン・ストア内に格納する。一旦、ｉ番目のストリップが前処理されると、該ｉ番目のストリップは後処理を行うために処理１４００へ送られる。処理１４００はまた前回のストリップ・ライン・ストア内のエントリであって、（ｉ＋１）番目のストリップの前処理中、前回のストリップ・ライン・ストアに現在追加されているエントリをフェッチする。即ち、後処理するプロセス１４００は、ｉ番目のストリップの最後の行内に在り、かつ（ｉ＋１）番目のストリップの第１の行の有意係数内の３×３の近傍に在る非有意係数の列番号を順にフェッチする。
【００８１】
処理１３００はステップ１３０２から始まり、そこで、上述のレジスタのエントリとライン・ストアとはゼロにセットされる。次いで、処理１３００はステップ１３０４へ進み、そこでステップ７３２中に渡された有意係数の（行、列）座標がフェッチされる。このフェッチされた（行、列）座標は変数CurPosに格納される。次いで、処理１３００は判定ブロック１３０６へ進み、そこでCurPosに格納された、位置の３×３の近傍内に非有意係数が存在するかどうかのチェックが行われる。
【００８２】
判定ブロック１３０６がイエス（真）を返した場合、処理１３００はループ１３１２〜１３２４へ進み、そこで位置CurPosの３×３の近傍内の非有意近傍が順にフェッチされ、処理される。具体的には、処理１３００はステップ１３１２へ進み、そこで次の非有意近傍の（行、列）座標がフェッチされ、変数NextNに格納される。次いで、処理１３００は判定ブロック１３１４へ進み、そこで位置NextNが現在のストリップの前のストリップの中に存在するかどうかのチェックが行われる。判定ブロック１３１４がイエス（真）を返した場合、位置NextNの列番号が、前回のストリップ・ライン・ストアに追加される（１３１６）。イエス（真）を返さなかった場合、処理１３００は判定ブロック１３２０へ進み、そこで位置NextNが、現在のストリップの次のストリップの中に存在するかどうかのチェックが行われる。判定ブロック１３２０がイエス（真）を返した場合、位置NextNの列番号は次のストリップ・ライン・ストアに追加される（１３１８）。一方、判定ブロック１３２０がノー（偽）を返した場合、処理１３００は、位置NextNに対応する現在のレジスタ内のエントリに対してビットＮを（１）にセットする。ステップ１３１６、１３１８、又は１３２２の完了後、処理１３００は判定ブロック１３２４へ進む。判定ブロック１３２４で、非有意近傍がさらに存在するかどうかのチェックが行われる。判定ブロック１３２４がイエス（真）を返した場合、処理１３００はステップ１３１２へ戻り、次の非有意近傍のさらなる処理を行う。イエス（真）を返さなかった場合ステップは１３２８へ続く。
【００８３】
ステップ１３２８で、変数PrevPosは変数CurPosにセットされる。次いで、処理１３００はステップ１３３０へ続き、そこで、処理１３００はステップ７３２（図７Ａ）中に渡された次の位置の（行、列）座標をフェッチする。このフェッチされた（行、列）座標は変数CurPosに格納される。この次の位置がまだ利用可能でない場合、処理１３００は利用可能になるまで待機する。それ以上利用可能な位置が存在しなければ、処理１３００はステップ１３３４へ直接進む（図示せず）。
【００８４】
ステップ１３３０の完了後、処理は判定ブロック１３３２へ進み、そこで変数CurPos内に格納された位置が、変数PrevPosに格納された位置に関して、次のストリップ内に存在するかどうかのチェックが行われる。判定ブロック１３３２がノー（偽）を返した場合、処理１３００は判定ブロック１３０６へ戻り、変数CurPosの中に格納された新しい位置のさらなる処理が行われる。判定ブロック１３３２がイエス（真）を返した場合、処理１３００はステップ１３３４へ続く。
【００８５】
ステップ１３３４中、処理１３００は現在のストリップ・レジスタの内容を前のストリップ・レジスタへ移動させ、現在のストリップ・レジスタ内のエントリをゼロにセットする。ステップ１３３４は、前回のストリップ・ライン・ストアへ次のストリップ・ライン・ストアの内容を移動させ、次いで、次のストリップ・ライン・ストア内のエントリをゼロにセットする。ステップ１３３４の完了後、処理はステップ１３３６と１３３８とへ同時に続く。ステップ１３３６中、処理１３００は、前のストリップ・レジスタを後処理する。これについては以下図１４を参照しながらさらに詳細に説明する。ステップ１３３８中、処理１３００は、前回のストリップ・ライン・ストア内に現在格納されている位置に対応する現在のストリップ・レジスタ内のエントリ用としてビットＮを（１）にセットする。ステップ１３３６と１３３８との完了後、処理は、非有意近傍をさらに処理するために判定ブロック１３０６へ続く。
【００８６】
判定ブロック１３０６がノー（偽）を返した場合、即ち、非有意近傍が存在しない場合、処理１３００は判定ブロック１３０８へ続く。判定ブロック１３０８は、ステップ７３２（図７Ａ）によって渡された位置がさらに存在するかどうかのチェックを行う。判定ブロック１３０８がイエス（真）を返した場合、処理１３００はステップ１３０４へ進み、そこでその位置はフェッチされる。現在利用可能な位置が存在しない場合には、判定ブロック１３０８は、位置が生じるまで待機するか、あるいは、ＳＰ符号化パス３１４は、処理が終了する（１３１０）終了時刻にＳＰ符号化パス３１４が終了するまで待機する。
【００８７】
次に図１４に目を転じると、図１３Ａと１３Ｂの前処理１３００と共に使用される後処理１４００のフローチャートが示されている。後処理ステップ１４００はＳＰ符号化パス３１４と同時に始まる。後処理１４００は１４０２を開始し、ステップ１３３６中に後処理１４００へ渡される前のストリップ・レジスタを待機する（１４０４）。前のストリップ・レジスタが後処理１４００へ渡された後、処理１４００はループ１４０６〜１４１６へ進む。ループ１４０６〜１４１６は、前のストリップ・レジスタ内の各エントリ（即ち、位置）であって、（１）にセットされたＮビットを持つ各エントリを順に処理し、前回のライン・ストア内に現在格納されているエントリ（列番号）とそのエントリとを比較し、ＪＰＥＧ２０００の走査順での以前の位置を新しいリストＳＰに追加する。ループ１４０６は、ＪＰＥＧ２０００の走査順に前のストリップ・レジスタ内のエントリを処理する。上記から明らかなように、前処理１３００は、エントリを追加することにより後処理１４００中も前回のライン・ストアを継続的に更新している。
【００８８】
ループ１４０６〜１４１６は判定ブロック１４０６とステップ１４０８とを有する。判定ブロック１４０６で、処理１４００は、（１）にセットされたＮビットを持つ、前のストリップ・レジスタ内に何らかのエントリ（即ち、位置）が、または、前回のストリップ・ライン・ストア内に何らかの位置が存在するかどうかのチェックを行う。判定ブロック１４０６がイエス（真）を返した場合、処理１４００はステップ１４０８と１４１０へ同時に進む。ステップ１４０８で、処理１４００は、現在前回のライン・ストア内に在る次の（第１の）列番号をフェッチし、変数LinePosに該列番号を格納をする。前回のライン・ストア内に現在エントリが存在しなければ、変数LinePosはヌルにセットされる。同時に、ステップ１４１０は、前にフェッチされなかった次の位置であって、（１）にセットされたＮビットを持つ次の位置を前のストリップ・レジスタからＪＰＥＧ２０００の走査順にフェッチし、変数StripPosにその位置を格納する。ステップ１４０８と１４１０の後、処理１４００はステップ１４１２へ進み、そこで処理は、変数LinePosとStripPos内に格納された位置の比較を行う。ステップ１４１２は、変数LinePosとStripPosに格納された該位置であって、ＪＰＥＧ２０００の走査順で早い位置にある該位置を決定し、変数WinPosにその位置を格納する。ステップ１４１２の完了後、処理はステップ１４１４へ進み、そこでその位置が前回のライン・ストア内に存在する場合、変数WinPosに格納された位置は、前回のライン・ストアから取り除かれる。ステップ１４１６の完了後、処理はステップ１４１６へ進み、そこで変数WinPosに格納された位置は新しいＳＰリストに追加される。処理１４００は更なる処理を行うために判定ブロック１４０６へ戻る。判定ブロック１４０６がノー（偽）を返した場合、処理１４００は終了する（１４１８）。
【００８９】
次に図９に目を転じると、ＳＰ符号化ステップ３１４のクリーンアップ・リスト生成ステップ７０８のフローチャートが示されている。クリーンアップ・リスト生成ステップ７０８はステップ９０２から始まり、ステップ９０４へ進み、そこでループの第１のパス（７１０〜７４０）中ステップ７２０で定められた位置を取得する。この位置がＪＰＥＧ２０００の走査順に従う第１の位置であり、この位置は、オリジナルのＳＰリスト、または近傍ＳＰリスト、または前回のストリップＳＰリストのいずれかの中に格納される。この位置は変数headSP内に格納される。また、ステップ９０４は、ＭＲリストに格納されている第１の位置をＪＰＥＧ２０００の走査順に従って取得し、変数headMRの中にこの位置を格納する。ステップ９０４の完了後、クリーンアップ生成ステップ７０８はループ９０６へ進む。
【００９０】
ループ９０６は、ＪＰＥＧ２０００の走査順でコード・ブロックの各位置Ｐ(x,y)を通して１だけ増分する。コード・ブロックの新しい位置Ｐ(x,y)に対する各々の増分後、ループ９０６は判定ブロック９０８へ進む。判定ブロック９０８は、ループの現在位置Ｐ(x,y)が変数headSP内に格納された位置に等しいかどうかをチェックする。判定ブロックがノー（偽）を返した場合、クリーンアップ生成ステップ７０８は判定ブロック９１２へ進み、そこでループの現在位置Ｐ(x,y)が、変数headMRに格納された位置に等しいかどうかのチェックが行われる。判定ブロックがノー（偽）を返した場合、クリーンアップ生成ステップ７０８はステップ９１６へ進み、そこで現在位置Ｐ(x,y)がクリーンアップ・リストに追加される。ステップ９１６の完了後、クリーンアップ生成ステップ７０８はループ９０６へ戻り、そこで、位置Ｐ(x,y)はＪＰＥＧ２０００の走査順で次の位置へ増分される。
【００９１】
一方、判定ブロック９０８がイエス（真）を返した場合、クリーンアップ生成ステップ７０８はステップ９１０へ進む。ステップ９１０中、ステップ７２０で定められた次の位置が利用可能な場合、クリーンアップ生成ステップ７０８はその位置を取得し、変数headSPにその位置を格納する。このようにして、クリーンアップ生成ステップ７０８は、ステップ７２０のパス中に定められた位置を次々に検索し、ステップ９１０をコールする度に、変数headSPに格納された現在位置を次の位置と置き換える。次の位置が現在利用できない場合が時としてある。そのような状況では、クリーンアップ生成ステップ７０８はその位置が利用可能になるまで待機する。さらに、判定ブロック７１０（図７Ａ）がノー（偽）を返した場合、クリーンアップ生成ステップ７０８は、待機する代わりに、このステップ９１０中に、変数headSPをヌルにセットする。後者の場合、ＳＰ符号化ステップ中符号化の対象となる位置はそれ以上存在しない。しかし、ＳＰ符号化ステップ中、クリーンアップ・リストに追加する必要がある、符号化の対象となる位置が最後の位置の後に存在する可能性がある。変数headSPをヌルにセットすることにより、ループ９０６の後続パス中、これらの位置をクリーンアップ・リストに追加することができる。ステップ９１０の完了後、クリーンアップ生成ステップはループ９０６へ戻り、そこで、位置Ｐ(x,y)はＪＰＥＧ２０００の走査順で１だけ増分される。
【００９２】
さらに、判定ブロック９１２がイエス（真）を返した場合、クリーンアップ生成ステップ７０８はステップ９１４へ進み、そこでＭＲリスト内の次の位置が変数headMRに格納される。このようにして、クリーンアップ生成ステップはＭＲリスト内の位置を次々に検索し、変数headMRに格納された現在位置をステップ９１４の各コールを用いて次の位置と置き換える。ＭＲリストに残された位置がそれ以上存在しなければ、ステップ９１２は変数headMRをヌルにセットする。ステップ９１４の完了後、クリーンアップ生成ステップはループ９０６へ戻り、位置Ｐ(x,y)は、ＪＰＥＧ２０００の走査順で１だけ増分される。
【００９３】
コード・ブロックの範囲内のすべての位置Ｐ(x,y)がクリーンアップ生成ステップ７０８によって処理された後クリーンアップ生成ステップ７０８は終了する。
【００９４】
このようにして、現在位置が現在のＳＰパス内で処理されている間、その位置はクリーンアップ・リスト生成ステップ７０８へも送られる。このステップ７０８では、ＪＰＥＧ２０００の走査順にブロック内のすべての座標を通るループが存在する。生成された座標は現在のＳＰ符号化パス内の次の位置と比較される。上記座標と位置とが等しければ、その位置は現在のパス内で予め処理され、その処理が続けられて現在のＳＰ符号化パス内に次の位置が取得され、その処理は次の座標を生成する。現在のＳＰ符号化パスから得られる次の位置が存在しなければ、位置が生じるまで、或いは、ＳＰ符号化が完了するまで処理は待機する。現在の座標が変数headSPに等しくない場合、現在の座標は変数headSPに格納されている座標より前の位置に存在し、したがってこの座標はクリーンアップ・リストの候補である。次いで、この座標は変数headMRと比較される。上記座標と位置とが等しくない場合、その座標は既にＭＲリストに在るため、処理はＭＲリスト内の次の位置を取得し、変数headMR内にそれを格納し、次の座標を生成する。この生成された座標が変数headMRに等しくない場合、この座標はクリーンアップ・リストの中へ挿入される。一旦、全ての位置が符号化されてしまうと、変数headSPをヌルにセットすることができる。同様に、いったんＭＲリストの全てのＭＲ位置が処理されてしまった場合、変数headMRはヌルにセットすることができる。このようにして、ＳＰリストとＭＲリストの最後の後の座標はクリーンアップ・リストに追加することができる。
【００９５】
本構成の変更例では、処理が、ストリップ内の或る列の４つの位置がすべてクリーンアップ・リストに在ることを検出した場合、処理はクリーンアップ・リストの中で１つの合成座標にその４つの位置を圧縮することができる。この合成座標は、符号化が可能な場合、後の符号化／復号化のクリーンアップ段階で利用することができる。
【００９６】
図７Ａに戻って、終了ステップ７１４中、ＳＰ符号化ステップ３１４はクリーンアップ符号化パス３１８中に新しいＳＰリストと更新されたオリジナルのＳＰリストとを返す。一方、エントロピ符号化法３００はマグニチュード・リファインメント符号化パス３１６へ進む。
【００９７】
次に図１０に目を転じると、マグニチュード・リファインメント符号化パス３１６のフローチャートがさらに詳細に示されている。マグニチュード・リファインメント符号化パス３１６はステップ１００２から始まり、ループ１００４〜１００８へ進み、そこでループ１００４〜１００８のそれぞれのパス用のＭＲリスト内の位置がＪＰＥＧ２０００の走査順で検索される。ステップ１００２後、マグニチュード・リファインメント符号化パス３１６は、ＭＲリスト内の第１の位置の処理を行うためにループのステップ１００４と１００６とへまず進む。ステップ１００６の完了後、マグニチュード・リファインメント符号化パス３１６は判定ブロック１００８へ進み、そこで前に処理されなかった、処理の対象となる位置がＭＲリストの中にさらに存在するかどうかのチェックが行われる。判定ブロック１００８がイエス（真）を返した場合、マグニチュード・リファインメント符号化パス３１６はステップ１００４へ戻り、そこで、ＭＲリストの次の位置が検索される。ステップ１００４中、マグニチュード・リファインメント符号化パス３１６は、ＭＲリストから現在位置をフェッチし、この現在位置を用いてメモリから対応するシンボルをフェッチする。マグニチュード・リファインメント符号化パス３１６はまた、現在位置の３×３の近傍内の有意値を有効値テーブルからフェッチする。ステップ１００４の完了後、マグニチュード・リファインメント符号化パス３１６はステップ１００６へ進む。ステップ１００６中、これらの有効値はコンテキスト生成処理へ送出されてコンテキストが生成され、対応するシンボルの符号化が行われ、さらに、そのシンボルに対して算術符号化が行われる。これらのステップ１００４と１００６とは１サイクル当たり１つの位置のレートで行うことができる。符号化処理では、ビットプレーン・メモリから必要なデータ・ビットをフェッチするために位置の座標が利用される。復号化処理では、出力用バッファの中に復号ビットを書き込むために位置の座標が利用される。判定ブロック１００８がノー（偽）を返した場合、マグニチュード・リファインメント符号化パス３１６は終了し（１０１０）、次いで、エントロピ符号化法はクリーンアップ符号化パス３１８へ進む。
【００９８】
次に図１１に目を転じると、クリーンアップ符号化パス３１８のフローチャートが示されている。クリーンアップ符号化パス３１８はステップ１１０２から始まる。このステップ１１０２中、前回のシグニフィカンス・プロパゲーション符号化パス３１４中生成されたクリーンアップ・リストは現在のクリーンアップ符号化パス３１８へ渡される。また、前回のクリーンアップ符号化パス３０８または３１８に中生成され、前回の符号化パス３１４中に更新されたオリジナルのＳＰリストは、クリーンアップ符号化パス３１８へ渡される。さらに、前回の符号化パス３１４中生成された新しいＳＰリストは、クリーンアップ符号化パス３１８へ渡される。開始ステップ１１０２中、クリーンアップ符号化パス３１８は、位置の（行、列）座標を格納するためのクリーンアップ−有意係数リストとクリーンアップ非有意近傍リストと呼ばれる２つのリストも初期化し、それらのリストのエントリをヌルにセットする。最後に、前回のクリーンアップ符号化パス３０８または３１８中に生成されたＭＲリストは現在のクリーンアップ符号化パス３１８へ渡される。
【００９９】
開始ステップ１１０２後、クリーンアップ符号化パス３１８はループ１１０４〜１１１４へ進み、そこでクリーンアップ・リスト内の位置は、ＪＰＥＧ２０００の走査順でループ１１０４〜１１１４のそれぞれのパス中検索される。ステップ１１０２後、クリーンアップ符号化パス３１８は判定ブロック１１０４へ進み、そこで現在のクリーンアップ符号化パス３１８によって検索されなかった位置がクリーンアップ・リストの中にさらに存在するかどうかのチェックが行われる。判定ブロック１１０４がイエス（真）を返した場合、クリーンアップ符号化パス３１８はステップ１１０６へ進み、そこで前に検索されなかった、クリーンアップ・リスト内の次の位置がフェッチされる。これらの位置は、ＪＰＥＧ２０００の走査順でクリーンアップ・リストから検索される。この位置がフェッチされた後、クリーンアップ符号化パス３１８はステップ１１０８へ進む。ステップ１１０８中、クリーンアップ符号化パス３１８はこの現在位置を利用して、その位置のビットプレーン・メモリから対応するビット・シンボルをフェッチする。クリーンアップ符号化パス３１８は、現在位置の３×３の近傍の有効値テーブルから有効値もフェッチする。さらに、これらの有意値はコンテキスト生成処理へ送出され、現在のシンボルの符号化用コンテキストが生成される。次いで、この現在のシンボルは算術符号化される。
【０１００】
ステップ１１０８の完了後、クリーンアップ符号化パス３１８は判定ブロック１１１０へ進み、そこで符号化された現在のビット・シンボルが有意であるかどうかのチェックが行われる。判定ブロック１１１０がノー（偽）を返した場合、クリーンアップ符号化パス３１８は、クリーンアップ・リスト内の次の位置（もし存在する場合）の処理を行うために判定ブロック１１０４へ戻る。一方、判定ブロック１１１０がイエス（真）を返した場合、クリーンアップ符号化パスはステップ１１１２へ進み、そこで現在位置の（行、列）座標がクリーンアップ−有意係数リストに追加される。クリーンアップ−有意係数リスト内の位置はＪＰＥＧ２０００の走査順に格納される。ステップ１１１２の完了後、クリーンアップ符号化パス３１８はステップ１１１４へ進む。
【０１０１】
ステップ１１１４中、クリーンアップ符号化パス３１８は、現在位置の３×３の近傍の範囲内の非有意係数を決定し、これらの非有意近傍の位置をクリーンアップ非有意近傍リストに追加する。クリーンアップ非有意近傍リスト内の後者の位置はＪＰＥＧ２０００の走査順に従ってソートされる。当業者には明らかなように、クリーンアップ非有意近傍リストは、クリーンアップ・リスト自身にない係数の位置を有することができる。これらの非有意係数をクリーンアップ非有意近傍リストに追加する方法は、新しいＳＰリストへの非有意係数の追加と関連して説明した方法（図１３Ａ、１３Ｂ、１４）と類似している。前者の場合、クリーンアップ符号化パス３１８は、図１３Ａ、１３Ｂ、１４を参照しながら説明したものと同じ処理を利用するが、以下の変更を伴う。クリーンアップ符号化パス３１８によって現在符号化されている有意係数の（行、列）座標は、ステップ１１１４中ステップ１３０４（図１３Ａ）へ渡され、代わりにステップ１４１４で変数WinPosがクリーンアップ非有意近傍リストに追加される。このようにして非有意係数のいずれのオーバーラップも取り除かれる。
【０１０２】
ステップ１１１４の完了後、クリーンアップ符号化パス３１８はＪＰＥＧ２０００に従って符号ビットを符号化し（図示せず）、次いで、判定ブロック１１０４へ戻る。判定ブロック１１０４がノー（偽）を返した場合、即ち、検索され、処理されたクリーンアップ・リストに位置がそれ以上存在しない場合、クリーンアップ符号化パス３１８はステップ１１１６へ進み、そこでクリーンアップ符号化パス３１８は終了する。
【０１０３】
クリーンアップ符号化パス３１８がクリーンアップ・リスト内の各位置の処理を行っている間のと同時に、クリーンアップ符号化パスは、次のＳＰ符号化パス３１４とＭＲ符号化パス３１６中、後続する処理を行うために、新しいオリジナルのＳＰリストと新しいＭＲリストとを生成する（１１１６）。
【０１０４】
次に図１２に目を転じると、新しいオリジナルのＳＰリストと新しいＭＲリストとを生成するステップ１１１６のフローチャートがさらに詳細に示されている。ステップ１１１６は１２０２から始まり、そこで、更新されたオリジナルのＳＰリストと、新しいＳＰリストと、オリジナルのＭＲリストと、クリーンアップ−有意係数リストと、クリーンアップ非有意近傍リストとが入力される。リスト・メモリ内のオリジナルのＳＰリストは、前回の符号化ステップ３１４中更新された有意タグを用いてソートされ（１２０４）、２つのリストに変えられる。オリジナルのＳＰ有意係数リストは、オリジナルのＳＰリストの位置であって、現在のビットプレーン内の対応する有意係数を持つものとしてタグが付けられた位置を有する。後者の位置は新しいオリジナルＭＲリストに追加される。オリジナルのＳＰ非有意係数リストは、オリジナルのＳＰリストの位置を有する。該位置のタグは、現在のビットプレーン内の対応する非有意係数を持つ位置を示す。この後者の位置は、新しいオリジナルのＳＰリストに追加される。同様に、新しいＳＰリストは、前回の符号化ステップ３１４中に生成された有意タグを用いてソートされ（１２０６）、２つのリストに変えられる。新しいＳＰ有意係数リストは、新しいＳＰリストの位置であって、現在のビットプレーン内の対応する有意係数を持つものとしてタグが付けられた位置を有する。後者の位置は、新しいＭＲリストに追加される。新しいＳＰリストの位置を有する新しいＳＰ非有意係数リストであって、これらの位置を示すタグを持つオリジナルのＳＰ非有意係数リストは、現在のビットプレーン内の対応する非有意係数を持つ。後者の位置は新しいＳＰリストに追加される。
【０１０５】
オリジナルのＳＰ−非有意係数リストの位置と、オリジナルのＳＰ−有意係数リストと、新しいＳＰ−非有意係数リストと、新しいＳＰ−有意係数リストと、オリジナルのＭＲリストと、クリーンアップ−有意係数リストと、クリーンアップ−非有意近傍リストとは、すべてのサブリストを一緒に併合する、２つの同一の‘比較と併合’処理１２０８と１２１０の中を通る。第１の‘比較と併合’処理１２０８は、オリジナルのＳＰ−有意係数リストの位置と、新しいＳＰ−有意係数リストと、オリジナルのＭＲリストと、クリーンアップ−有意係数リストとを比較し併合する（本明細書では、以後第１サブリストと呼ぶ）。第２の‘比較と併合’処理１２１０は、オリジナルＳＰ−非有意係数リストの位置と、新しいＳＰ−非有意係数リストと、クリーンアップ−非有意近傍リストとを比較し併合する（本明細書では、以後第２サブリストと呼ぶ）。‘比較と併合’処理１２０８と１２１０とは、クリーンアップ符号化ステップ３１８のループ１１０４〜１１１４によって現在処理されているクリーンアップ・リストの現在位置も入力として受け取る。
【０１０６】
‘比較と併合’処理１２１０は、第２のサブリストの中の各１つから１つの位置を受け入れ、それらを比較して、どれがＪＰＥＧ２０００の走査順で最も早い位置に在るかを調べる。次いで、‘比較と併合’処理１２１０は、ステップ１２１１へその結果を出力し、次いで、選択されたサブリストから次の位置を受け入れる。２つのサブリストが同じ位置を持っている場合、双方とも取り除かれ、１つだけが出力される。‘比較と併合’処理１２０８は、‘比較と併合’処理１２１０と同様に実行されるが、第１のサブリストからその位置を受け入れる。このソートティング処理は、１クロック・サイクル当たりのリスト当たり少なくとも１つの位置を生成することでき、したがってスループットは、サイクル当たり１係数／ビットのままであることが望ましい。しかし、ループ１１０４〜１１１４によって処理される現在の座標が、これら全ての‘比較と併合’処理が出力しようとしている座標より前に在る場合、この‘比較と併合’処理は機能が停止する。この処理によって、新しいオリジナルＳＰとＭＲリスト内の座標の欠落が防止される。
【０１０７】
実際には有意である非有意係数の位置が、第２のサブリストに存在する場合もある。これらの位置は、ステップ１２１１中、比較と併合処理１２１０の出力から取り除かれる。このステップ１２１１中、比較と併合処理１２１０によって出力される各位置は、有効値テーブル１２１３内のその位置における対応する係数の現在の有意状態と比較される。当該係数が有意であることが有効値テーブル１２１３によって示された場合、仮定上非有意係数の位置は、ステップ１２１１において取り除かれる。一方、当該係数が非有意であることが有効値テーブル１２１３によって示された場合、比較と併合処理１２１０によって出力された位置は取り除かれず、新しいオリジナルのＳＰリストの一部を形成する。
【０１０８】
比較有意ステップ１２１１と比較と併合処理１２０８とは、新しいオリジナルのＳＰリストと、新しいオリジナルのＭＲリストとをそれぞれ出力し、これらのリストは後続するＳＰ符号化パス３１４とＭＲ符号化パス３１６で使用される。新しいオリジナルＳＰリストとＭＲリストとを生成するステップ１１１６は、リストの完了後、１２１２で終了する。
【０１０９】
本構成の変更例では、新しいオリジナルのＳＰ／ＭＲリスト生成処理は継続し、次のビットプレーンのＳＰ符号化パス３１４に入る。次のＳＰ符号化パス３１４が始まるときまでに、新しいオリジナルのＳＰリストの先頭が準備ができていることが望ましい。それにより機能停止が不要となる。しかし、クリーンアップ符号化パス処理に起因する機能停止が生じないので、リスト生成処理は最大レートで進むはずである。
【０１１０】
本構成のさらなる変更例では、オリジナルのＳＰリストと新しいＳＰリストのタグなしで済ますことが可能となる。現在のビットプレーンで有意であるかどうかを示す有効値テーブルから、これらのリストに格納された位置に対応する係数の有効値を読み出すことにより、リスト生成ステップ１１１６中、これらのリストをソートすることができる。更なる変更例では、リスト・メモリ内に、ビットが有意か否かを示す１ビットを設けて、その係数が以前に処理されたものであれば、このビットが書き込まれる。有効値テーブルへのアクセスを減らすという理由でこのアプローチは好適である。上記ビットはリスト・メモリとして同じメモリ内に在ってもよいし、或いは、別個のメモリ内に在ってもよい。
【０１１１】
上述のように、クリーンアップ符号化パス３１８の完了後、本方法は任意のさらなるビットプレーンの処理を行うために判定ブロック３１０へ戻る。判定ブロックが真（イエス）を返した場合、即ち、処理の対象となる更なるビットプレーンが存在しない場合、本方法は終了する（３００）。
【０１１２】
次に図１５に目を転じると、図３に図示のエントロピ符号化法を実行するためのエントロピ・コーデックが示されている。このエントロピ・コーデックは、リスト・メモリ・マネージャ１５０２と、ビットプレーン・スプリッタ１５０４と、ビットプレーン・メモリ１５０８と、有効値テーブル１５１０と、リスト・メモリ１５０６と、コンテキスト生成論理回路１５１２と、算術符号化部（図示せず）とを有する。リスト・メモリ・マネージャ１５０２は、専用集積回路の形をとり、その機能は図３のエントロピ符号化法の演算と関連づけられるリスト作成を実現することである。リスト・メモリ・マネージャ１５０２によって作成されたこれらのリスト（例えば新しいＳＰリスト）は、リスト・メモリ・マネージャ１５０２によって、半導体メモリの形のリスト・メモリ１５０６内に格納される。リスト・メモリ・マネージャ１５０２は、図３のエントロピ符号化法自体のコンテキスト生成ステップと符号化ステップとを実行せず、コンテキスト生成論理回路１５１２とコーデック（図示せず）によって行われる、これらの操作の制御を行う。同様に、リスト・メモリ・マネージャ１５０２は、ビットプレーン分割操作３０４と操作３０６とを行わず、ビットプレーン・スプリッタ１５０４によって実行される、これらの操作の制御を行う。
【０１１３】
コーデック１５００は以下のように図３のエントロピ符号化法を実行する。コード・ブロックのウェーブレット係数がＤＷＴユニット（図示せず）から入力されている間、このコード・ブロックを構成するビットプレーンは、ビットプレーン・スプリッタ１５０４によってそれぞれのビットプレーン・メモリ１５０８の中へ書き込まれる。同時に、ビットプレーン・スプリッタ１５０４は、各係数が有意となり始めるビットプレーンを決定し、有効値テーブル１５１０内にその情報を格納する。また同時に、ビットプレーン・スプリッタ１５０４は、どれがビットプレーン内で有効ビットを持つ最上位ビットプレーンであるかを決定し、リスト・メモリ・マネージャ１５０２へ最上位ビットプレーン番号を送出する。リスト・メモリ・マネージャ１５０２はまた、符号化の対象となる最下位ビットプレーンのビットプレーン番号もフェッチする。リスト・メモリ・マネージャ１５０２は、最上位ビットプレーンから始まり、次いで、各ビットプレーンについて、シグニフィカンス・プロパゲーション・パス３１４のオペレーションと、マグニチュード・リファインメント・パス３１６と、クリーンアップ・パス３０８または３１８とを符号化の対象となる最下位ビットプレーンまで実行する。各パスで、リスト・メモリ・マネージャ１５０２は、そのパスで符号化／復号を行う必要がある全ての係数である、リスト・メモリ１３０６の中に格納されている全ての係数の位置リストを作成する。シグニフィカンス・プロパゲーション・パス３１４の場合、リスト・メモリ・マネージャ１５０２がオリジナルのＳＰリストの中を通るとき、新しいＳＰリストが生成される。
【０１１４】
リスト・メモリ・マネージャ１５０２は、符号化の対象となるシンボルの位置を決定するとすぐに、有効値テーブル１５１０から読み出してコンテキスト生成論理回路１５１２上へ渡すべきその位置の３×３の近傍内の係数の有意値を指示する。リスト・メモリ・マネージャ１５０２はまた、現在のビットプレーン内のその位置におけるシンボルをビットプレーン・メモリ１５０８から検索する。次いで、コンテキスト生成論理回路１５１２は、この有効値情報に基づいてコンテキストを計算し、算術符号化部（図示せず）へその情報を渡す。また、現在のビットプレーン内のその位置におけるシンボルは算術符号化部（図示せず）上へ渡される。
【０１１５】
次に図１６に目を転じると、コード・ブロックの変換係数のシンボルのエントロピ符号化を行う別の方法１６００を示すフローチャートが示されている。シンボルのエントロピ符号化を行うこの方法１６００は、図３を参照しながら説明したシンボルの符号化を行う方法より単純である。しかし、この方法１６００は係数のうちの数ビットを予め知っている必要があるので、エントロピ復号化を行うために、この方法を用いることはできない。したがって、この方法は、単純ではあるものの、エントロピ符号化時にしか利用することができない。
【０１１６】
本方法１６００はステップ１６０２から始まり、このステップで必要なパラメータが全て初期化される。初期化段階１６０２中、本方法１６００は有効値テーブルを生成する。この有効値テーブルは、符号化の対象となるコード・ブロックの係数の有意状態の２次元配列を有する。本方法１６００は、コード・ブロック全体を処理し、各係数が有意となり始める位置に在るビットプレーンを決定し、有効値テーブル内にその情報を格納する。次いで、本方法１６００は、その係数と関連する有効値テーブルに格納されるビットプレーン番号に関して、現在のビットプレーンにおける係数の有意状態を決定することができる。例えば、有効値テーブル内に、ある係数と関連づけられて格納されている現在のビットプレーンがビットプレーン番号より大きい場合、その係数はその現在のビットプレーンについて非有意となる。現在のビットプレーンがビットプレーン番号より大きくない場合にはその係数は有意になる。このビットプレーン番号は、コード・ブロックの範囲内の係数位置に対応する配列を示す（行、列）座標と共に、配列として有効値テーブルの中に格納される。
【０１１７】
また初期化段階１６０２中、本方法は、シグニフィカンス・プロパゲーションリスト（ＳＰリスト）と、マグニチュード・リファインメント・リスト（ＭＲリスト）と、クリーンアップ・リスト（Ｎリスト）として本明細書で名付けられた３つのリストを生成する。これらのリストには、現在のパス中、符号化されるコード・ブロックの範囲内のビット・シンボルの位置が含まれる。例えば、このシグニフィカンス・プロパゲーションリストには、現在のシグニフィカンス・プロパゲーション・パスで符号化されるコード・ブロックの範囲内の全てのビット・シンボルの位置リストが含まれる。‘ビット・シンボルの位置’という用語は、そのビット・シンボルが一部を形成する変換係数のコード・ブロックの範囲内の配列位置を、本明細書では意味する。さらに、これらのリストの各々の範囲内の位置は、ＪＰＥＧ２０００の走査順に従って索引化される（図２参照）。最初、シグニフィカンス・プロパゲーションリスト（ＳＰリスト）とマグニチュード・リファインメント・リスト（ＭＲリスト）とは空である。一方、クリーンアップ・リスト（Ｎリスト）は、コード・ブロックの範囲内の全ての位置をリストし、ノンゼロ・ビットを持つ最上位ビットプレーンの符号化を行うために使用される。
【０１１８】
開始１６０２後、コード・ブロックの変換係数が受け取られ、ビットプレーンに分割される（１６０４）。次のステップ１６０６では、コード・ブロックのビットプレーンがチェックされ、どのビットプレーンが最上位ノンゼロ・ビットを所有するかが判定される。
【０１１９】
次いで、本方法はステップ１６０８へ進み、そこで最上位ビットを持つビットプレーンは、１回の単一クリーンアップ・パスでエントロピ符号化される。具体的には、最上位ノンゼロ・ビットを持つビットプレーンに属するビット・シンボルが各々エントロピ符号化される。これらのビット・シンボルは、例えば、図２に図示のように、ＪＰＥＧ２０００の走査順でエントロピ符号化される。エントロピ符号化ステップ１６０８は、符号化対象ビット・シンボルと、そのビット・シンボルのコンテキストとを入力として受け取り、該コンテキストはＪＰＥＧ２０００に従って好適に決定される。
【０１２０】
ステップ１６０８の完了後、本方法は判定ブロック１６１０へ進み、そこで処理の対象となるビットプレーンがさらに存在するかどうかのチェックが行われる。もし存在すれば、本方法はステップ１６１２へ進み、そこで次のビットプレーンのビット・シンボルが検索される。
【０１２１】
ステップ１６１２の完了後、本方法１６００はステップ１６１３へ進む。ステップ１６１３中、本方法１６００は、まずシグニフィカンス・プロパゲーションリスト（ＳＰリスト）と、マグニチュード・リファインメント・リスト（ＭＲリスト）と、クリーンアップ・リスト（Ｎリスト）とをクリアする。その後、ステップ１６１３では、コード・ブロックの範囲内のすべての位置をソートし、シグニフィカンス・プロパゲーションリスト（ＳＰリスト）と、マグニチュード・リファインメント・リスト（ＭＲリスト）と、クリーンアップ・リスト（Ｎリスト）との中にこれらの位置を格納する。ソート・ステップ１６１３は、これらのリストのうちの１つだけに各位置が格納されるように、これらの位置を格納する。これらの格納された位置は、コード・ブロック内の対応する係数の（行、列）座標を示す。
【０１２２】
ソート・ステップ１６１３中、本方法はＪＰＥＧ２０００の走査順にコード・ブロックの全ての位置に亙って増分を行う。
【０１２３】
現在の位置走査中、ソート・ステップ１６１３は、現在走査中の位置を取り囲む３×３の近傍の位置に対応する、有効値テーブルに格納されたビットプレーン番号を検索する。ソート・ステップはまた、現在走査中の位置に対応する有効値テーブル内に格納されたビットプレーン番号も検索する。上述のように、有効値テーブルに格納されたビットプレーン番号は、その係数が有意になる位置に存在するビットプレーンを示す。次いでソート・ステップ１６１３は、現在位置の係数の有意状態を含む、３×３の近傍の各係数の有意状態を、現在のビットプレーンにおいて決定する。次いで、ソート・ステップ１６１３は、以下の規則に従って、ＳＰ、ＭＲまたはＮリストのうちのいずれに、その位置を格納すべきかを判定する。
【０１２４】
規則１：走査中の現在位置Ｐ(x,y)の係数が有意状態≧Ｎ（但し、Ｎは処理中の現在のビットプレーン）を持っていれば、現在位置はＭＲリストに進む。
【０１２５】
規則２：走査中の現在位置Ｐ(x,y)の係数が、Ｎより小さい（＜Ｎ）有意状態を持ち、かつ、ＪＰＥＧ２０００の走査順で現在位置Ｐ(x,y)の前に在る係数である、現在位置Ｐ(x,y)の３×３の近傍内の任意の係数が、有意状態≧Ｎ（但し、Ｎは処理中の現在のビットプレーン）を持つ係数を持っていれば、現在位置Ｐ(x,y)はＳＰリストに入る。
【０１２６】
規則３：走査中の現在位置Ｐ(x,y)の係数が、Ｎより小さい有意状態（＜Ｎ）を持ち、かつ、ＪＰＥＧ２０００の走査順で現在位置Ｐ(x,y)の後に在る現在位置Ｐ(x,y)の３×３の近傍内の任意の位置であって、有意状態＞Ｎ（但し、Ｎは処理中の現在のビットプレーン）を持つ位置を持っていれば、現在位置Ｐ(x,y)はＳＰリストに入る。
【０１２７】
規則４：走査中の現在位置Ｐ(x,y)がＭＲリスト又はＳＰリストに格納されていなければ、その位置はＮリストに格納される。即ち、クリーンアップ（Ｎ）リストには、ＳＰリストとＭＲリストにない位置が含まれる。
【０１２８】
このようにして、ソート・ステップ１６１３は、係数の位置をソートしてビットプレーンＮ用のＳＰ、ＭＲ、Ｎリストの中へ入れる。次いで、これらのリストを送って、シグニフィカンス・プロパゲーション・パスと、マグニチュード・リファインメント・パスと、クリーンアップ・パスとの中で符号化を行うことができる。
【０１２９】
ソート・ステップ１６１３の完了後、本方法はステップ１６１４へ進み、現在のビットプレーンのシグニフィカンス・プロパゲーション・パス内で関連するビット・シンボルの処理が行われる。このステップ１６１４で、ステップ１６１３で生成されたビット・シンボルである、現在のＳＰリスト内の位置に対応する現在のビットプレーン内のビット・シンボルがエントロピ符号化される。
【０１３０】
ＳＰ符号化パス１６１４の完了後、本方法はマグニチュード・リファインメント符号化パス１６１６へ進む。このステップ１６１６で、ステップ１６１３で生成されたビット・シンボルである、現在のマグニチュード・リファインメント・リスト内の位置に対応する現在のビットプレーン内の全てのビット・シンボルがエントロピ符号化される。
【０１３１】
ＭＲ符号化パス１６１６の完了後、本方法はクリーンアップ符号化パス１６１８へ進む。クリーンアップ符号化ステップ１６１８で、（前回の符号化パス中生成されたビット・シンボルである）、現在のクリーンアップＮリスト内の位置に対応する、現在のビットプレーン内の全てのビット・シンボルがエントロピ符号化される。
【０１３２】
クリーンアップ符号化パス１６１８の完了後、本方法は判定ブロック１６１０へ戻り、任意の更なるビットプレーンの処理が行われる。判定ブロックが真（イエス）を返した場合、即ち、処理の対象となる更なるビットプレーンが存在しない場合、本方法は終了し（１６２０）、コール方法へ戻る。判定ブロックが真（イエス）を返さなかった場合、本方法は、次のビットプレーンの処理を行うためにステップ１６１２へ進む。好適には、本方法は所定の最下位ビットプレーンまでビットプレーン処理を続けることが望ましい。
【０１３３】
好適には、本方法が全ての３つのリスト、即ち、ＳＰ、ＭＲ及びＮリストを生成することが望ましい。本構成の変更例では、本方法はＳＰ、ＭＲ及びＮリストのうちの少なくとも１つのリストを生成することができる。この場合、本方法はリストを持っていない任意のパス中コード・ブロック全体を走査する。
【０１３４】
次に図１７に目を転じると、図１６に図示のエントロピ符号化法を実行するエントロピ符号器が示されている。エントロピ符号器１７００は、図１６を参照しながら上述した規則に従って現在のビットプレーンの係数の位置をソートする係数ソータと、操作１６０４と１６０６とを行うためのビットプレーン・スプリッタ（図示せず）と、コード・ブロックの各ビットプレーンのビット・シンボルを格納するためのビットプレーン・メモリ（図示せず）と、有意値を格納するための有効値テーブル１７１０とを有する。エントロピ符号器はまた、係数ソータ１７０２によって生成されるＳＰリストを格納するためのＳＰリスト・メモリ１７０４と、係数ソータ１７０２によって生成されるＭＲリストを格納するためのＭＲリスト・メモリ１７０６と、係数ソータ１７０２によって生成されるクリーンアップ・リストを格納するためのクリーンアップ・リスト・メモリ１７０８をも有する。エントロピ符号器は、図１６を参照しながら説明したように、コンテキスト生成論理回路１７１２と、ＳＰリストと、ＭＲリストと、クリーンアップ・リスト内に、それらのリストのそれぞれのパス中格納された位置に対応するビット・シンボルを符号化するための算術符号化部（図示せず）とを更に有する。ＳＰリスト・メモリ１７０４は、ダブルバッファ構成である。係数ソータ１７０２が、ビットプレーンｎのＳＰリスト用の位置を生成して、それらの位置をＳＰリスト・メモリ１７０４内に格納している間、コンテキスト生成論理回路１７１２はビットプレーン（ｎ＋１）用の完成したＳＰリストを読み出している。ＭＲリスト・メモリ１７０６とクリーンアップ・リスト・メモリ１７０８とはまた、ＳＰリスト・メモリ１７０４と同様の方法でダブルバッファとしても機能する。
【０１３５】
図３と図１６を参照しながら説明した前述の好ましい方法は、ある特別の制御フローを有する。これらの方法には、本発明の精神または範囲から逸脱することなく様々な制御フローを用いる他の多くの変形例が存在する。例えば、図３のエントロピ符号化法は、いくつかの並列操作を部分的に有する。図３のエントロピ符号化法を改変して、当業者には明らかであるようなシーケンシャルな操作であるかのように、これらの並列操作を実現することもできる。後者（シーケンシャルなオペレーション）の場合、図３のこの改変されたエントロピ符号化法は、汎用コンピュータのソフトウェアとしての実現に適している。例えば、前処理ステップ４１２と後処理ステップ４１８とは、いくつかの改変例についてはシーケンシャルに機能してもよい。汎用コンピュータのソフトウェアとして図１６のエントロピ符号化法を実現してもよい。
【０１３６】
次に図１８に目を転じると、前述の方法を実行することができる汎用コンピュータが示されている。コンピュータ・システム１８００の範囲内で実行するアプリケーション・プログラムのようなソフトウェアとして、これらの方法の処理を実行してもよい。特に、前述の方法のステップは、コンピュータによって実行されるソフトウェア内の命令によって実行される。例えば、以下説明する記憶装置を含むコンピュータ可読媒体にこのソフトウェアを格納してもよい。このソフトウェアは、コンピュータ可読媒体からコンピュータの中へロードされ、次いで、コンピュータによって実行される。コンピュータ可読媒体に保存されるようなソフトウェアまたはコンピュータ・プログラムを持つコンピュータ可読媒体は、コンピュータ・プログラム製品である。
【０１３７】
コンピュータ・システム１８００は、コンピュータ・モジュール１８０１と、キーボード１８０２とマウス１８０３等の入力装置と、プリンタ１８１５と表示装置１８１４とを含む出力装置とを有する。コンピュータ・モジュール１８０１は、電話回線１８２１またはその他の機能媒体を介して接続可能な通信ネットワーク１８２０と交信するための変復調（モデム）送受装置１８１６を使用する。モデム１８１６を使用して、インターネットやローカル・エリア・ネットワーク（ＬＡＮ）や広域ネットワーク（ＷＡＮ）等の他のネットワーク・システムにアクセスすることもできる。
【０１３８】
コンピュータ・モジュール１８０１には、少なくとも１つのプロセッサ・ユニット１８０５と、例えば半導体ランダム・アクセス・メモリ（ＲＡＭ）やリード・オンリ・メモリ（ＲＯＭ）から形成される記憶装置（メモリ）１８０６と、ビデオ・インターフェース１８０７を含む入力／出力（Ｉ/Ｏ）インターフェースと、キーボード１８０２とマウス１８０３およびオプションとしてジョイ・スティック（例示せず）用のＩ/Ｏインターフェース１８１３と、モデム１８１６用のインターフェース１８０８とが一般に含まれる。記憶装置１８０９が提供され、この装置には一般にハードディスク・ドライブ１８１０とフロッピーディスク・ドライブ１８１１とが含まれる。磁気テープ駆動装置（例示せず）を使用することもできる。不揮発性データソースとしてＣＤ−ＲＯＭ駆動装置１８１２が一般に設けられる。コンピュータ・モジュール１８０１の構成要素１８０５〜１８１３は、一般に、相互接続バス１８０４を介して、また、コンピュータ・システム１８００の従来の動作モードで結果として得られる当業者に公知の方法で交信を行う。実施の形態の実行が可能なコンピュータの例には、ＩＢＭ−ＰＣおよび互換機、Sun Sparstationやそこから進化した同様のコンピュータ・システムが含まれる。
【０１３９】
一般に、前述の方法のアプリケーション・プログラムはハードディスク・ドライブ１８１０に常駐し、プログラムの実行時にプロセッサ１８０５によって読み出され、制御される。半導体メモリ１８０６を用いて、おそらくハードディスク・ドライブ１８１０に従って、ネットワーク１８２０からフェッチされたプログラムと任意のデータの中間的格納を行うことができる。いくつかの例では、ＣＤ−ＲＯＭやフロッピーディスクに符号化され、対応する駆動装置１８１２や１８１１を介して読み出されるアプリケーション・プログラムや、或いは、ユーザーがネットワーク１８２０からモデム装置１８１６を介して読み出すことができるアプリケーション・プログラムをユーザへ供給することができる。さらに、磁気テープ、ＲＯＭあるいは集積回路、光磁気ディスク、コンピュータ・モジュール１８０１と別の装置との間の無線伝送チャネルまたは赤外線伝送チャネル、ＰＣＭＣＩＡカードのようなコンピュータ可読カード、ウェブ等に保存されるｅ−メール伝送と情報を含むインターネットとイントラネットを含む他のコンピュータ可読媒体からコンピュータ・システム１８００の中へソフトウェアをロードすることもできる。上述のものは単に関連するコンピュータ可読媒体の例示にすぎない。本発明の範囲と精神から逸脱することなく、他のコンピュータ可読媒体を実際に使用することも可能である。
【０１４０】
本発明の実施の形態がコンピュータ産業とビデオ画像産業、並びに、ビデオ及びカメラ産業のような関連分野に適用可能であることは、以上のことから明らかである。
【０１４１】
上述のことは、本発明のいくつかの実施の形態について説明するものにすぎず、本発明の範囲と精神から逸脱することなく改変及び／又は変更を行うことが可能であり、以上の実施の形態は例示的なものであって、限定なものではない。
【図面の簡単な説明】
【図１】従来技術のＪＰＥＧ２０００で利用される係数“Ｘ[ｍ，ｎ]”の８個の包囲係数の近傍有意状態を示す図である。
【図２】従来技術のＪＰＥＧ２０００で利用されるコード・ブロック用のコード・ブロック走査パターンの一例を例示する概略ブロック図である。
【図３】第１の構成に従うエントロピ符号化法を示すフローチャートである。
【図４】図３に図示のエントロピ符号化法で用いられる最初のクリーンアップ符号化ステップ３０８の詳細処理を示すフローチャートである。
【図５】図４に描かれるようなｉ番目のストリップのｊ番目の列の前処理ステップ４１２をさらに詳細に示すフローチャートである。
【図６】図４に描かれるような（ｉ-１）番目のストリップの（ｊ−２）番目の列の後処理ステップ４１８をさらに詳細に示すフローチャートである。
【図７Ａ】、
【図７Ｂ】図３のシグニフィカンス・プロパゲーション（ＳＰ）符号化ステップ３７４をさらに詳細に示すフローチャートである。
【図８】ＳＰ符号化ステップ３１４のステップ７２０をさらに詳細に示すフローチャートである。
【図９】ＳＰ符号化ステップ３１４のクリーンアップ・リスト生成ステップ７０８をさらに詳細に示すフローチャートである。
【図１０】マグニチュード・リファインメント符号化パス３１６をさらに詳細に示すフローチャートである。
【図１１】図３のクリーンアップ符号化パス３１８をさらに詳細に示すフローチャートである。
【図１２】新しいオリジナルのＳＰリストと新しいＭＲリストとを生成するためのステップ１１１６をさらに詳細に示すフローチャートである。
【図１３Ａ】、
【図１３Ｂ】図７Ａのステップ７３２によって渡される新しいＳＰリストに非有意近傍を加える処理を示すフローチャートである。
【図１４】図１３Ａと図１３Ｂの前処理プロセスとともに使用する後処理プロセスを示すフローチャートである。
【図１５】図３に図示のようなエントロピ符号化法を実現するためのエントロピ・コーデックの概略図を示す図である。
【図１６】第２の構成に従うエントロピ符号化法を示すフローチャートである。
【図１７】図１６に示すエントロピ符号化法を実現するためのエントロピ符号器の概略図である。
【図１８】図３と図１６の方法を実行する汎用コンピュータの概略図である。
【図１】
0004721390.tif 000002
【図２】
0004721390.tif 000003
【図３】
0004721390.tif 000004
【図４】
0004721390.tif 000005
【図５】
0004721390.tif 000006
【図６】
0004721390.tif 000007
【図７Ａ】
0004721390.tif 000008
【図７Ｂ】
0004721390.tif 000009
【図８】
0004721390.tif 000010
【図９】
0004721390.tif 000011
【図１０】
0004721390.tif 000012
【図１１】
0004721390.tif 000013
【図１２】
0004721390.tif 000014
【図１３Ａ】
0004721390.tif 000015
【図１３Ｂ】
0004721390.tif 000016
【図１４】
0004721390.tif 000017
【図１５】
0004721390.tif 000018
【図１６】
0004721390.tif 000019
【図１７】
0004721390.tif 000020
【図１８】
0004721390.tif 000021