(57)【特許請求の範囲】
【請求項１】
最上位ビットから下位ビットへ初期的に全て零ではない係数のビットプレーンに対して、各係数を有意プロパゲーション・パス、リファインメント・パス、又はクリーンアップ・パスのサブビットプレーンパスのうちの１つのパスで符号化する方法であって、
係数毎に、１ビットプレーンのサブビットプレーンパスが識別された所定のブロックに対する有意状態情報に応じて、処理される情報が有意プロパゲーション・パス、リファインメント・パス、又は、クリーンアップ・パスに属するかどうかを判定する手順と、
前記所定のブロックが、有意プロパゲーション・パス、リファインメント・パス、又は、クリーンアップ・パスの係数を有するかどうかを表わす信号をアサートする手順と、
前記リファインメント・パス及びクリーンアップ・パスに対する係数の個数のランカウント及び異なるパスに含まれる後続係数の個数のスキップカウントを識別すると共に、有意プロパゲーション・パスの係数のビットを符号化する手順と、
前記リファインメント・パスにあるものとして識別された係数のビット及びクリーンアップ・パスにあるものとして識別された係数のビットを処理する手順と、を有する方法。
【請求項２】
先行ビットが有意プロパゲーション・ビットであり、現在ビットが有意プロパゲーション・ビットではないとき、リファインメント・パス又はクリーンアップ・パスのいずれかに対する新しいランを開始する手順を更に有する請求項１記載の方法。
【請求項３】
前記有意プロパゲーションパスが実行される各サブ領域は４×４領域により構成される請求項１記載の方法。
【請求項４】
前記有意プロパゲーションパスが実行される各サブ領域で有意係数の個数をカウントする手順を更に有する請求項１記載の方法。
【請求項５】
前記カウントが各サブ領域のサイズと一致する場合、各サブ領域における全てのビットをリファインメントとして処理する手順を更に有する請求項４記載の方法。
【請求項６】
前記カウントが零と一致し、有意な近傍が存在しない場合、各サブ領域における全てのビットをクリーンアップとして処理する手順を更に有する請求項４記載の方法。
【請求項７】
最上位ビットから下位ビットへ初期的に全て零ではない係数のビットプレーンに対して、各係数を有意プロパゲーション・パス、リファインメント・パス、又はクリーンアップ・パスのサブビットプレーンパスのうちの１つのパスで符号化する画像処理装置であって、
係数毎に、１ビットプレーンのサブビットプレーンパスが識別された所定のブロックに対する有意状態情報に応じて、処理される情報が有意プロパゲーション・パス、リファインメント・パス、又は、クリーンアップ・パスに属するかどうかを判定する手段と、
前記所定のブロックが、有意プロパゲーション・パス、リファインメント・パス、又は、クリーンアップ・パスの係数を有するかどうかを表わす信号をアサートする手段と、
前記リファインメント・パス及びクリーンアップ・パスに対する係数の個数のランカウント及び異なるパスに含まれる後続係数の個数のスキップカウントを識別すると共に、有意プロパゲーション・パスの係数のビットを符号化する手段と、
前記リファインメント・パスにあるものとして識別された係数のビット及びクリーンアップ・パスにあるものとして識別された係数のビットを処理する手段とを有する画像処理装置。
【請求項８】
先行ビットが有意プロパゲーション・ビットであり、現在ビットが有意プロパゲーション・ビットではないとき、リファインメント・パス又はクリーンアップ・パスのいずれかに対する新しいランを開始する手段を更に有する、請求項７記載の画像処理装置。
【請求項９】
前記有意プロパゲーションパスが実行される各サブ領域は４×４領域により構成される、請求項７記載の画像処理装置。
【請求項１０】
前記有意プロパゲーションパスが実行される各サブ領域で有意係数の個数をカウントする手段を更に有する、請求項７記載の画像処理装置。
【請求項１１】
前記カウントが各サブ領域のサイズと一致する場合、各サブ領域における全てのビットをリファインメントとして処理する手段を更に有する、請求項１０記載の画像処理装置。
【請求項１２】
前記カウントが零と一致し、有意な近傍が存在しない場合、各サブ領域における全てのビットをクリーンアップとして処理する手段を更に有する請求項１０記載の画像処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、圧縮及び伸張の技術に係り、特に、ラン・スキップカウントに基づくコンテキストモデル・スキッピング技術及びメモリアクセス技術に関する。
【０００２】
【従来の技術】
データ圧縮は、大量のデータを蓄積、伝送するための非常に有効なツールである。たとえば、文書のファクシミリ伝送のような画像を伝送するために要する時間は、画像を提示するために必要なビット数を減少させるため圧縮が使用されると、劇的に削減される。
【０００３】
従来技術では、多種多様なデータ圧縮技術が知られている。圧縮技術は、損失のある符号化と損失の無い符号化の二つのカテゴリーに大別される。損失のある符号化には、原データの完全な再構成が保証されないような情報の損失を生じる符号化が含まれる。損失のある圧縮の目標は、原データへの変更が邪魔にならないか、又は、検出できないように行なわれることである。損失の無い圧縮の場合、全ての情報が保持され、完全な再構成ができるようにデータを圧縮することである。
【０００４】
損失の無い圧縮の場合、入力シンボル又は強度データは、出力符号語に変換される。入力は、画像、オーディオ、１次元データ（たとえば、空間的に変化するデータ）、２次元データ（たとえば、空間的な２方向で変化するデータ）、又は、多次元／多重スペクトルデータを含む。圧縮が成功した場合、符号語は、入力信号（若しくは強度データ）の「ノーマル」表現におけるビット数よりも少ないビットで表現される。損失の無い符号化方法は、辞書的な符号化法（たとえば、Lempel-Ziv法）、ランレングス符号化法、エニュメラティブ(enumerative)符号化法、及び、エントロピー符号化法を含む。損失の無い画像圧縮の場合、圧縮は、予測又はコンテキストと符号化に基づく。ファクシミリ圧縮用のJBIG標準と、連続階調画像用のDPCM（差分パルス符号変調−JPEG標準における一つのオプション）は、損失の無い画像用圧縮の例である。損失のある圧縮の場合、入力シンボル又は強度データは、出力符号語へ変換する前に量子化される。量子化は、重要ではない特性を除去すると共に、関連性のあるデータの特性を保存するよう意図されている。量子化の前に、損失のある圧縮システムは、屡々、エネルギー集約を行なうため変換を使用する。JPEGは、画像データ用の損失のある符号化方法の一例である。
【０００５】
可逆変換（ウェーブレット変換、コンポーネント変換）は、損失のある圧縮、及び、損失の無い圧縮の両方の圧縮に使用される。不可逆変換（ウェーブレット、コンポーネント、離散コサイン）は、損失のある圧縮だけに使用される。
【０００６】
新たなJPEG 2000復号化標準は、変換を利用し、画像用の新しい符号化体系及び符号ストリーム規定を提供する。JPEG 2000標準は復号化標準であり、復号器のあるべき形を定義するが、この定義は、特に、損失の無い圧縮用の符号器を制約する。JPEG 2000標準の下で、各画像は矩形タイルに分割される。２個以上のタイルが存在する場合、画像のタイル張りによって、タイルコンポーネントが生成される。画像は多数のコンポーネントを含む。たとえば、カラー画像は、赤、緑及び青のコンポーネントを有する。タイルコンポーネントは、相互に独立に抽出若しくは復号化される。
【０００７】
画像のタイル張り後、タイルコンポーネントは、ウェーブレット変換を用いて一つ以上の異なる分解レベルに分解される。これらの分解レベルは、原タイル・コンポーネントの水平及び空間周波数特性を記述する係数で占められた多数のサブバンドを収容する。係数は、画像全体ではなく、局所領域に関する周波数情報を与える。すなわち、少数の係数が単一のサンプルを完全に記述する。分解レベルは、サブバンドの連続した分解レベルの水平分解能及び垂直分解能が前の分解レベルの約半分になるように、空間的な倍率２で次の分解レベルに関連付けられる。
【０００８】
サンプルと同数の係数が存在するが、情報内容は、数個の係数だけに集中する傾向がある。量子化によって、多数の係数の数値精度は、不釣合いに低い歪み（量子化ノイズ）の導入と共に減少する。エントロピー符号器による付加的な処理は、これらの量子化された係数を表現するため要求されるビット数を減少させ、場合によっては原画像よりも著しく減少させる。
【０００９】
タイル・ンポーネントの個別のサブバンドは、さらに、符号ブロックに分割される。符号ブロックは、区域にグループ化される。これらの係数の矩形状アレイは、独立に抽出され得る。符号ブロック中の係数の個別のビットプレーンは、３段階の符号化パスでエントロピー符号化される。３段階のうちの各符号化パスは、ビットプレーン圧縮画像データに関するコンテキスト（前後関係）情報を収集する。
【００１０】
これらの符号化パスから生成されたビットストリーム圧縮画像データは、レイヤにグループ分けされる。レイヤは、符号ブロックからの連続した符号化パスの任意のグループ分けである。レイヤ化は柔軟性に富んでいるが、連続した各レイヤがより高品質の画像に寄与することが前提である。各分解能レベルでのサブバンド係数の符号ブロックは、区域(precincts)と呼ばれる矩形領域に分割される。
【００１１】
パケットは、圧縮符号ストリームの基本単位である。パケットは、一つのタイルコンポーネントの一つの分解能レベルの一つの予測レイヤからの圧縮画像データを含む。これらのパケットは、符号ストリーム中に定められた順序で配置される。
【００１２】
タイルに関連した符号ストリームは、パケットに構成され、一つ以上のタイル部分に並べられる。タイル部分ヘッダは、マーカー及びマーカーセグメント、又は、タグの系列によって構成され、あらゆるタイルコンポーネントの位置を見つけ、抽出し、復号し、再構築するために必要な種々の仕組み及び符号化スタイルに関する情報を収容する。全符号ストリームの先頭には、マーカー及びマーカーセグメントにより構成された主ヘッダがあり、主ヘッダは、原画像に関する情報並びに類似した情報を提供する。
【００１３】
符号ストリームは、アプリケーションが画像の意味、及び、画像に関するその他の情報の意味を解釈できるように、随意的にファイルフォーマットにまとめられる。このファイルフォーマットは、符号ストリーム以外のデータを収容する。
【００１４】
JPEG 2000符号ストリームの復号化は、符号化手順の順序を逆転させることにより実行される。図１には、圧縮画像データ符号ストリームに作用するJPEG 2000標準符号化体系のブロック図が示されている。図１を参照するに、最初に、ビットストリームがデータ順序付けブロック１０１によって受信され、データ順序付けブロック１０１は、レイヤ及びサブバンド係数を再グループ分けする。算術符号器１０２は、前に符号化された、ビットモデリングブロック１０３から与えられたビット・プレーン圧縮画像データに関する係数及びビットモデリングブロック１０３の内部状態からのコンテキスト情報を使用して、圧縮ビットストリームを復号化する。
【００１５】
次に、符号ストリームは、量子化ブロック１０４によって量子化され、量子化ブロック１０４は、ROI（領域選択画質向上）ブロック１０５によって示されるような領域選択画質向上処理(ROI)に基づいて量子化を行なう。量子化後、逆ウェーブレット／空間変換が変換ブロック１０６によって係数に適用され、その後に、DCレベルシフト及び選択的コンポーネント変換ブロック１０７が続く。これにより、再生画像が生成される。
【００１６】
【発明が解決しようとする課題】
本発明は、情報を符号化及び復号化する方法並びに装置の提供を目的とする。
【００１７】
【課題を解決するための手段】
一実施例において、本発明の装置は、メモリ及び復号化ハードウェアを含む。メモリは、ラン・カウント、及び／又は、スキップ・カウントを蓄積し、復号化ハードウェアはラン・カウント、及び／又は、復号化中にメモリから取得されたスキップ・カウントを復号化する。
【００１８】
本発明は、以下の実施例の記載及び添付図面を参照することによって十分に理解されるであろう。しかし、実施例の記載及び添付図面は、本発明を特定の実施例に限定するものではなく、本発明の説明と解明を意図するものである。
【００１９】
【発明の実施の形態】
符号化を実行する技術について説明する。符号化を実行する技術は、JPEG 2000標準を実現するため、特徴セットを操作するため、或いは、特徴セットへ追加するため使用される。すなわち、JPEG 2000標準として、参考のため引用したITU-T Rec. T.800|ISO/IEC FDIS 15444: 2000 JPEG Image Coding Systemに記載されている情報テクノロジー−JPEG 2000画像符号化システムであるCore Coding System（コア・コーディング・システム）は、導入者に多数の選択の範囲を残す。上記文献に記載された技術の目的は、ソフトウェア、ハードウェア及び／又はファームウェアにおいて、高速、低価格、小メモリ容量、及び／又は、性能豊富な手段を実現するため、JPEG 2000での選択の範囲を利用することである。
【００２０】
以下では、本発明が完全に理解できるように、多数の細部について説明する。しかし、本発明がこれらの特定の細部を用いることなく実施されることは、当業者には明らかであろう。その他の場合、周知の構成及び装置は、本発明の本質がわかり難くなることを避けるために、詳細図ではなくブロック図の形式で示されている。さらに、詳細には記載されていないブロック、ロジック又は機能は、周知の手段を用いて実現されるか、或いは、当業者によって周知のハードウェア、ソフトウェア及び／又はファームウェアを用いて容易に実現される。一部の技術及び手段は、疑似コードを用いて記述されていることに注意する必要がある。しかし、このことは、この一部の技術及び手段が、ソフトウェアだけによって実現されることを意味するわけではなく、むしろ、このような記載は、当業者が容易に理解するであろう項目の機能を簡単に説明するために、屡々、選択される。
【００２１】
以下の詳細な説明の一部分は、コンピュータメモリ内のデータビットに対する演算のアルゴリズムと記号的表現とを用いて提示される。これらのアルゴリズム的記述及び表現は、データ処理技術の分野の当業者が、自分の業績をその分野の当業者に最も効率的に伝えるために使用する手段である。ここで、アルゴリズムは、一般的に、所望の結果を導く一貫した手順のシーケンスであると考えられる。これらの手順は、物理量の実際的な操作を必要とする手順である。通常、必ずしも不可欠ではないが、これらの物理量は、記憶、転送、合成、比較、或いは、操作することが可能な電気信号又は磁気信号の形式で得られる。主として、一般的な用法であるとの理由から、これらの信号は、ビット、値、要素、シンボル、文字、項、数などによって指定することが時に好都合であることがわかる。
【００２２】
しかし、これらの用語及び類義語は、適切な物理量と関連付けられ、物理量に与えられた便宜的なラベルに過ぎない。特に断らない限り、以下の説明から明らかであるように、「処理」、「コンピューティング」、「計算」、「決定」、或いは、「表示」のような用語を利用する記述は、コンピュータシステム若しくは類似した電子コンピューティング装置の動作及び処理を示すものであり、コンピュータシステムのレジスタ及びメモリ内で物理（電子）量として表現されたデータを操作し、同じように、コンピュータシステムのメモリ若しくはレジスタ、又は、他の情報記憶装置、情報伝送装置、若しくは、情報表示装置内で物理量として表現された他のデータへ変換する。
【００２３】
本発明は、以下で説明する動作を実行する装置に関する。この装置は、特に、要求された用途に応じて構成されるか、或いは、選択的に作動され、若しくは、コンピュータに記憶されたコンピュータプログラムを用いて再構成される汎用コンピュータを含む。このようなコンピュータプログラムは、たとえば、フレキシブルディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスクなどを含む任意のタイプのディスクや、読み出し専用メモリ（ＲＯＭ）や、ランダム・アクセス・メモリ（ＲＡＭ）や、ＥＰＲＯＭや、ＥＥＰＲＯＭや、磁気若しくは光カードや、電子命令を記憶するため適した任意のタイプの媒体のような、コンピュータシステムバスに接続された、コンピュータ読み取り可能な記憶媒体に記憶されるが、これらの例示的な記憶媒体に制限されるものではない。
【００２４】
ここで説明するアルゴリズム及びディスプレイは、本来的に特定のコンピュータ若しくはその他の装置に関連付けられたものではない。種々の汎用システムが、ここで教示された事項に応じたプログラムと共に使用される。或いは、要求された方法の手順を実行するため、より専用化された装置を構成した方が便利な場合もある。多様なこれらのシステムに対し要求される構成は、以下の記載から明らかになる。さらに、本発明は、特定のプログラミング言語に基づいて説明されていない。以下で説明するような本発明の教示事項を実現するために、多様なプログラミング言語を使用できることが認められるであろう。
【００２５】
機械読み取り可能な媒体は、機械（たとえば、コンピュータ）によって読み取り可能な形式で情報を記憶若しくは伝送する任意のメカニズムを含む。たとえば、機械読み取り可能な媒体は、読み出し専用メモリ（ＲＯＭ）と、ランダム・アクセス・メモリ（ＲＡＭ）と、磁気ディスク記憶媒体と、光記憶媒体と、フラッシュメモリ装置と、電気的、光学的、音響的若しくはその他の形式の伝搬信号（たとえば、搬送波、赤外線信号、デジタル信号など）と、を含む。
【００２６】
〔概要〕
図２９は、符号器の一実施例のブロック図である。図２９を参照するに、データ・インタフェース（Ｉ／Ｆ）２９０１は、符号化されるべきデータ、或いは、復号化後に出力されるべきデータを受信するため接続される。ＤＣレベルシフタ２９０２は、データ・インタフェース２９０１に接続され、符号化中及び復号化中にＤＣレベルシフトを実行する。ウェーブレット変換器２９０３は、ＤＣレベルシフタ２９０２に接続され、処理フローの方向に依存して、順ウェーブレット変換又は逆ウェーブレット変換を実行する。一実施例において、ウェーブレット変換器２９０３は、５，３−可逆ウェーブレット変換、及び、５，３−不可逆ウェーブレット変換を実行し、画像を２乃至５レベルに分解する。ラインバッファ２９０４は、ウェーブレット変換器２９０３に接続され、ウェーブレット変換を実行する際に、ウェーブレット変換器２９０３にデータを供給する。
【００２７】
スカラー量子化／逆量子化ブロック２９０５は、ウェーブレット変換器２９０３に接続され、スカラー量子化を実行する。一実施例において、スカラー量子化は、５，３−ウェーブレット変換だけのため使用される。プリコーダ２９０６は、スカラー量子化ブロック２９０５に接続され、プリコーディングを行なう。一実施例において、プリコーダ２９０６は、係数を２の補数から符号付きの尺度（大きさ）に変換する（復号化の場合には、逆変換する）。プリコーダは、零ビットプレーンを決定する。ワークメモリＡ及びワークメモリＢは、パケットヘッダ処理器２９０７と共に、プリコーダ２９０６に接続される。ワークメモリＡ及びワークメモリＢと、パケットヘッダ処理器２９０７へのインタフェースは、ビットモデリングＭＱ符号器２９０８１−Ｎにも接続される。各ＭＱ符号器２９０８１−Ｎは、符号化データ(JPEG 2000の用語では圧縮データ）を保持する個別の符号メモリ２９１１Ｎに接続される。符号メモリからの符号化データと、パケットヘッダ処理器２９０７からのパケットヘッダは、符号化データとして出力される。これは、JPEG 2000ビットストリームである。付加的な機能ブロック（図示しない）は、主ヘッダ及びタイル部ヘッダの作成／読出しのため使用される。ビットストリーム及びヘッダは、JPEG 2000符号ストリームを形成する。
【００２８】
〔サブビットプレーンに対するスキップを含むコンテキスト・モデル・データ構造〕
JPEG 2000において、（最上位ビット（ＭＳＢ）から始めて下位ビットへ）初期的に全零ではない係数のビットプレーンに対して、各係数は、有意プロパゲーション、リファインメント、クリーンアップの三つのサブビットプレーンパスのうちの一つのパスで符号化される。図２Ａには、係数毎に、１ビットプレーンのサブビットプレーンパスが識別された８×８符号ブロックの一例が示されている。図２Ａを参照すると、ＳＰは、有意プロパゲーション・パスを表わし、Ｒは、リファインメント・パスを表わし、Ｃは、クリーンアップ・パスを表わす。図２Ａにおける指数０〜６３は、符号ブロック走査順序を示す。このようにして、走査順序は、下向きに４係数、次に、最上位行に戻るという動作を符号ブロック全体に亘って繰り返す。符号ブロック全体の走査が終了した後、次に、走査は、各列の５番目の係数から下向きに、残りの符号ブロックの全域に亘って続けられる。
【００２９】
典型的な実現例では、ビットプレーンの符号化パス毎に１回ずつの合計３回に亘って係数のブロック全体を読み出す。この技術は、各ビットプレーンの有意プロパゲーション・パスに対し係数ブロックの全体を読み出し、リファインメント・パスとクリーンアップ・パスに対して実際に必要とされる係数だけを読み出す方法を説明する。
【００３０】
図２Ａの各セルの左側において、実線は、リファインメント・サブビットプレーンパスの係数を示し、点線は、リファインメント・サブビットプレーンパスでスキップされた係数を表わす。図２Ａの各セルの右側の実線は、クリーンアップ・サブビットプレーンパスに対する係数を示す。パスが係数毎に識別されると、係数が処理される。
【００３１】
データ構造は、後述の処理を用いて、有意プロパゲーション・パス中に構築される。このデータ構造は、メモリへのアクセス回数を低減させるため、コンテキストモデルによって使用される。このデータ構造を用いることによって、情報が属するパスがどのパスであるかを判定するためセル毎に検査し、セルをスキップする必要があったのに対して、コンテキストモデルは、メモリに１回だけアクセスすればよい。さらに、このデータ構造は、たとえば、クリーンアップ・ビットが同時に４ビットだけ符号化されるときのように、多数の場所へ同時にアクセスすることを可能にさせる。
【００３２】
表１及び表２は、それぞれ、リファインメント・サブビットプレーンパスにおける係数の場所及びクリーンアップ・サブビットプレーンパスにおける係数の場所を記述する。インデックス毎に、サブビットプレーンパスにおける係数の個数のランカウントと、異なるパスに含まれる後続係数の個数のスキップカウントが示されている。これらのデータ構造は、サブビットプレーンパスを効率的に符号化することを可能にさせる。そのために、他のパスにおける係数をスキップできるようにする。
【００３３】
【表１】
0004061104.tif 000002
【００３４】
【表２】
0004061104.tif 000003
この処理は、ハードウェア、ソフトウェア、又は、両方の組み合わせを含む処理ロジックによって実行される。一実施例において、データ構造を作成し、データ構造を使用するこの処理ロジックは、図２９のビットモデルングＭＱ符号器２９０８１−Ｎに設けられる。処理中に、これらのデータ構造を作成するため、データ構造が最初に初期化される。
【００３５】
ri=0                //リファインメント用インデックス
ci=0                //クリーンアップ用インデックス
r_run[ri]=0        //リファインメント用ランカウント
r_skip[ri]=0        //リファインメント用スキップカウント
c_run[ci]=0        //クリーンアップ用ランカウント
c_skip[ci]=0        //クリーンアップ用スキップカウント
state=INITIAL        //状態stateは、INITIAL、SIG_PROP、REFINE又はCLEANUPである。
【００３６】
状態変数は、実行（ラン）の開始と中央を区別するため使用される。状態変数は、前の係数用の符号化パスを示す。現在の係数が同じである場合、ラン若しくはスキップのサイズは増加し、異なる場合、新しいランが開始される。符号ブロックの各係数は、別々のカウントを生成するため、符号ブロック走査順に考慮される。
【００３７】
0004061104.tif 000004
上記コードにおいて、y1の最大値は、符号ブロックの高さ（"(height-1)&〜3"）よりも小さい４の最大の整数倍である。xの最大値は、符号ブロックの"width-1"である。y2の最大値は、３と"height-y1-1"の小さい方である。各係数を処理する手続の一実施例は、以下の通りである。
【００３８】
0004061104.tif 000005
【００３９】
この手続を適用した結果、有意プロパゲーション・パスの全係数は符号化され、リファインメント・ビット及びクリーンアップ・ビットに対するデータ構造が作成される。
【００４０】
必要に応じて、ランカウントは、行を超えて元に戻らないようにすることができる。この行のラップアラウンドを防止するための処理の一実施例は、以下の疑似コードに記載される。これにより、境界を非常に簡単に取り扱うことが可能になる。
【００４１】
0004061104.tif 000006
【００４２】
ソフトウェアの場合、ラン値及びスキップ値を整数（３２ビットコンピュータの場合には、３２ビットなど）として保持することが最も好都合である。最悪のケースは、長さ０のランでスタートした長さ１のランである。JPEG 2000において、符号ブロックの係数は、最大で４０９６個に制限される。符号ブロックの幅と高さも最大で１０２４個の係数に制限される。全部で４０９６個の係数の任意のサイズの符号ブロックに対し、ランカウントが行のグループの全域で継続する場合、４０９７個のメモリロケーションが、そのメモリサイズに対するメモリロケーションの最大数である。６４×６４の符号ブロックに対し、ランカウントが４行ずつのグループ毎にスタートする場合、（４×６４＋１）×（６４／４）＝４１１２個のメモリロケーションが最大値である。１０２４×４の符号ブロックに対し、ランカウントが４行ずつのグループ毎にスタートする場合、（４×４＋１）×（１０２４／４）＝４３５２個のメモリロケーションが最大値である。
【００４３】
ハードウェアのメモリを節約するため、最小限の固定数のビットがランカウント及びスキップカウントのため使用され得る。最初のカウントがランカウントとスキップカウントのどちらであるかを示す標識が信号（たとえば、１ビット信号標識）で示されたとき、ランカウントは１よりも大きい（かつ、０を符号化する能力は要求されない）。全部で４０９６個の係数をもつ任意のサイズの符号ブロックに対して、ライン（行）のグループに対してランカウントが継続する場合、最初のカウントがランであるか、又は、スキップであるかを示すために、１ビットが使用され、４９，１５３ビット全体に対して、４０９６×１２ビットが使用される。６４×６４符号ブロックに対して、ランカウントが４行ずつのグループ毎に始まる場合、４行ずつの各グループに対し最初のカウントがランであるかスキップであるかを示すため１ビットが使用される。かくして、ビット数は、１×６４／４＋４０９６×１２＝４９，１６８ビットである。１０２４×３の符号ブロックに対し、ランカウントが４行のグループ毎に始まる場合、ビット数は、１×１０２４／４＋４０９６×１２＝４９，４０８ビットである。
【００４４】
可変長符号の一実施例は、カウントを表現するため使用され得る。表３では、小さいカウントが少数のビット（たとえば、３ビット）で表現され、大きいカウントは、多数のビット（たとえば、１３ビット）で表現される。このようなアプローチの目標は、比較的小さい符号語を頻繁に使用できるように、殆どのカウントを、１、２、３若しくは４で表わすことである。より簡単に実現するために、二つのサイズだけが使用される。しかし、三つ以上のサイズを使用して、複雑さを増しても構わない。
【００４５】
【表３】
0004061104.tif 000007
この符号の場合、全てのランレングスが１（すなわち、全符号語が３ビット）となるときに最悪の状況が生ずる。３通りの状況（行を横断してカウントする状況、４行ずつのグループによる６４×６４符号ブロックの状況、４行ずつのグループによる１０２４×４符号ブロックの状況）に対し、総ビット数は、それぞれ、１２，２８９ビット、１２，３０４ビット、及び、１２，５４４ビットになる。
【００４６】
メモリ使用量の削減は、もっと複雑な可変長符号を用いることによって達成される。優れた構造の符号は、表４に示されるような、ガンマ符号、γ１又はγ（BBell, Cleary, Whitten "Text Compression", Prenice Hall, NJ, 1990のAppendix A）である。
【００４７】
【表４】
0004061104.tif 000008
γ１とγは、符号語のビットの並べ方だけが相違する。γ１符号語中の"_"は、符号語の一部ではなく、カウンタからプレフィックスを分離することによって見易くさせるためのものである。最悪の状況は、３ビットを必要とする２のカウントの場合に生じる。３通りの状況（行を横断してカウントする状況、４行ずつのグループによる６４×６４符号ブロックの状況、４行ずつのグループによる１０２４×４符号ブロックの状況）に対し、必要とされる総ビット数は、それぞれ、６，１４５ビット、６，１６０ビット、及び、６，４００ビットになる。
【００４８】
表５は、最長符号語が１６ビットで表わされるカウント１．．．４０９６に対する符号の一実施例である。カウント１、２、３、４又は５は、それぞれ、１、２、３、４及び５によって表現される。カウント６〜２１は、８ビットで表わされる。カウント２２〜４０９６は、１６ビットで表わされる。３及び６のカウントは、最悪の状況である。３通りの状況（行を横断してカウントする状況、４行ずつのグループによる６４×６４符号ブロックの状況、４行ずつのグループによる１０２４×４符号ブロックの状況）に対し、総ビット数は、それぞれ、５，４６３ビット、５，４７８ビット、及び、５，７１８ビットである。
【００４９】
【表５】
0004061104.tif 000009
ハードウェアによる可変長符号を使用する場合、同じクロックサイクル中にランカウントとスキップカウントの両方へアクセスすることが望ましい。一実施例において、メモリは、最小サイズよりも１語（たとえば、１６ビット）分だけ大きいので、フラッシュが簡単である。たとえば、１６ビット語の場合、ランカウントは１６３ビットを使用する。したがって、最後の語は３ビットだけを使用する。これにより、１語を完成するために、１３ビットをパディングする必要が生じる。スキップカウントは８５ビットを使用する。したがって、最後の語は、５ビットしか使用しない。このため、１語を完成するには、１１ビットをパディングする必要がある。メモリサイズが、
メモリサイズ≧（（１６３＋１３）／１６）＋（（８５＋１１）／１６）
すなわち、
メモリサイズ≧１７
であるならば、ランカウントとスキップカウントのパディングは独立でもよい。サイズが１６であるならば、１語は、ランカウントと、スキップカウントと、両者の間のパティングとを含む。図３０には、ランカウントとスキップカウントの両方を備えた１６ビット語の一例が示されている。
【００５０】
図２Ｂは、可変長ラン・スキップカウント用のメモリの説明図である。このメモリ構造によれば、ランカウントをメモリの一方側（２０１）から開始し、スキップカウントをメモリの他方側（２０２）から開始させることが可能である。メモリの一方側２０１は、始まりでも終わりでもよく、他方側２０２は、終わりでも始まりでもよい。これにより、１ラン可変語と１スキップ可変語のスタートは、同時にわかっているので、ランカウントとスキップカウントを同時並行的に復号化できるようになる。そのため、ランカウントを先に復号化し、その長さを判定し、次に、スキップカウントを復号化しなくてもよい。直列的である場合（ラン・スキップ・ラン、以下同様である場合）、（一方を復号化しない限り他方を見つけられないので）一つずつ判明することになる。
【００５１】
別個のスキップカウント及びランカウントは、図２Ｂに示されたメモリで情報を復号化するため使用される。或いは、１台の復号器をスキップカウントとランカウントの両方で共用してもよい。
【００５２】
〔コンテキストモデル用ハードウェア〕
コンテキストモデルはハードウェアに実現される。ハードウェアにおいて、一つの目標は、ＭＱ符号器が待機状態にならないように、できる限り早く次のコンテキストを生成することである。
【００５３】
〔メモリ構成〕
図３の（Ａ）〜（Ｄ）は、コンテキストモデルの実施例のための近傍係数及びメモリ構成を示す図である。個別の係数用のコンテキストモデルは、図３Ａに示されるように、高々、３×３近傍に基づいている。一実施例において、４ビットが同時に処理される。このような状況において、４個の係数３１１〜３１４のグループに対するコンテキストモデルは、図３Ｂに示されるように、高々、３×６近傍に基づいている。ハードウェアへのメモリアクセスは、２のべき乗でグループ化されたデータを処理することが屡々望ましい。したがって、３×６領域を含むような２のべき乗に基づく領域は、４×８領域である。図３の（Ｃ）は、係数の４×８領域の部分集合である３×６近傍を示す図である。図３の（Ｃ）の４×８領域全体へのアクセスは、同一のメモリ若しくは同一ではないメモリはの別々のアクセスとして実行される。図３の（Ｄ）は、４個の２×４領域３０１〜３０４に分割された４×８領域を示す。２×４領域は、並行したランダムアクセスのため、異なるメモリへ個別に格納される。このメモリ構造によって、係数のグループからのコンテンツを判定するため必要な全ての情報をメモリから、順番にではなく、同時に読み出すことが可能になる。すなわち、係数情報の４×８ブロック全体は、同時にアクセスされる。
【００５４】
図４は、１６×１６符号ブロックに対するランダムアクセス用の有意メモリ構成の一実施例を示す図である。一実施例では、たとえば、３２×３２、６４×６４のような他のサイズを取り扱うことができるが、これらのサイズには限定されない。図４を参照するに、各係数は、４個のメモリ（Ａ、Ｂ、Ｃ又はＤ）のうちの一つに割り当てられる。一部のグループ（一番上の２行と一番下の２行）は、他のグループのサイズの半分のサイズである。その理由は、図３の（Ｄ）において、符号ブロックの最初の２行に対し、一番上の２行が符号ブロックの外側にある（エッジから外れている）からである。同様な境界条件は、符号ブロックの一番下にも現れる。
【００５５】
一実施例において、メモリは、有意状態用の係数に対し１ビット（１アドレスについて全部で８ビット）を記憶する。他の一実施例において、メモリは、有意状態用の係数とサイン毎に２ビット（１アドレスについて全部で１６ビット）を記憶する。さらに別の一実施例において、これらのメモリは、全係数（Ｎが１個の係数のサイズを表わすとき、８Ｎビット）を記憶する。他の一実施例において、全部の係数がこれらのメモリに記憶されない場合、１係数毎に１個のアドレスを備えた補助的な一つのメモリが使用される。
【００５６】
以下のベリログ(Verilog)コードは、２個の６ビットアドレス入力（"x"及び"y")を、（６４×６４符号ブロック用）コンテキストモデルの制御ロジックから、メモリＡ、Ｂ、Ｃ、若しくはＤを指定するための、メモリへの７ビットアドレス出力("addr")と、２ビットバンク選択とに変換する、一実施例である。
【００５７】
0004061104.tif 000010
【００５８】
１番目のアサイン文は、境界に対するオフセットを設定する。すなわち、オフセット"assign yp2 = y + 2"は、図４に示されるように４行のグループの適切な配置を行なうため使用される。２番目のアサイン文は、入力yのビット５〜３と、入力xのビット５〜２と連結したオフセットの合計へのアドレスを、数の下位部分としてセットする。３番目のアサイン文は、入力yのビット２と、入力xのビット１と連結したオフセットの合計と一致するバンクを設定する。
【００５９】
〔有意プロパゲーション・パス〕
図５は、ランダムアクセス用の有意プロパゲーション・パスに使用されるメモリ及びレジスタの一実施例を示す図である。図５によれば、アドレスＡは、データ出力を生成するためメモリＡへ入力され、データ出力はレジスタ５０１にも保持される。アドレスＢに応答して、メモリＢは、データを出力し、出力されたデータは、レジスタレジスタ５０２にも保持される。同様に、メモリＣは、アドレスＣに応答してデータを出力し、出力はレジスタ５０３に保持される。最後に、メモリＤは、アドレスＤに応答してデータを出力し、そのデータはレジスタ５０４に記憶される。一実施例において、各メモリＡ〜Ｄの出力は、２×４領域であり、全体として、４×８領域（たとえば、図６の領域６０１）を作成する。
【００６０】
図５に示されたメモリ及びレジスタの全出力は、全体として、有意ビットの６×６領域を与える。これは、他の実施例では、有意状態及びサイン、又は、実際の係数になり得ることに注意する必要がある。すなわち、メモリＡ〜Ｄからの並列に使用されるデータは、前のサイクルにメモリＡ〜Ｄから読み出されレジスタ５０１〜５０４に保持されたデータと組み合わされる。この有意ビットと、コンテキストモデルからのフィードバックを合わせた領域は、係数の４×４領域が存在するパスを決定するために十分な領域である。
【００６１】
図６は、メモリから読み出され、ランダムアクセスのためレジスタに保持された有意状態を示す図である。図６によれば、領域６０１は、メモリから読み出された４×８領域を示す。領域６０２は、メモリＡ〜Ｄから読み出され、コンテキストモデリングのため使用される３×６領域を示す。領域６０３は、レジスタ５０１から５０４に記憶され、コンテキストモデリングに使用される３×６領域を示す。領域６０４は、処理される係数の４×４領域を示す。図６には、メモリＡ〜Ｄのメモリロケーション及びレジスタから得られた８×８ブロックの典型的な２×４部分が示されている。
【００６２】
有意プロパゲーション・パス用のアドレス生成ロジックの一実施例は、以下の疑似コードに記載される。アドレッシングはデータに依存しないこと、及び、零データは境界に設けられることに注意する必要がある
0004061104.tif 000011
0004061104.tif 000012
【００６３】
４×４ブロックを処理するため、同じパスのビットのランは一緒に取り扱われる。リファインメント・パスの行にＮ個の係数が存在する場合、以下の疑似コードがそれらを処理するため使用される。
【００６４】
0004061104.tif 000013
【００６５】
この疑似コードは、１個の係数ではなく、Ｎ個の係数が処理されていることを示すため、１の代わりにＮが使用されている点を除くと、上述のコードと類似していることに注意する必要がある。
【００６６】
Ｎ個の係数がクリーンアップ・パスの行に存在する場合、以下の疑似コードは、係数を処理するためのプロセスの一実施例を表わす。
【００６７】
0004061104.tif 000014
【００６８】
図７は、有意プロパゲーション・パスロジックの一実施例のブロック図である。一実施例において、このロジックは、図２９のビットモデリングＭＱ符号器２９０８１−Ｎに含まれる。係数毎のパスは、１係数当たりにつき、有意プロパゲーション又はそれ以外、リファインメント又はそれ以外、及び、クリーンアップ又はそれ以外の３ビットで表現された４×４領域に対するパスである。図５において、メモリＡ〜Ｄのアクセス動作を制御することによって、４×４ブロックがメモリから取り出され、有意プロパゲーション・パスが実行される。各４×４ブロックを調べると、多数のパス中のランが識別され、有意パス中の係数を符号化する必要があり、一方、リファインメント・オア及びクリーンアップ・パスに対するランカウント及びスキップカウントは、同時に一つのランを処理するため識別される。ブロック内で（走査順による）前のビット（或いは、新しい符号ブロックの始まりの場合には前の符号ブロック）は、有意プロパゲーション・ビットであり、現在状態は有意プロパゲーションではなく、新しいランが始まる。このような場合に、インデックスは、ラン・スキップカウントを保持するテーブル内でインクリメントされる（たとえば、スキップを零にセットし、ランを第１の値にセットする）。ランカウントとスキップカウントの両方のテーブルは、このようにしてインクリメントされ、同時に、４×４ブロックを処理する。４×４ブロックの前のビットがリファインメント・パス又はクリーンアップ・パスにあり、より多くのこのようなデータが後に続くとき、現在ランのカウントはインクリメントされる。Ｎが２のべき乗を表わすとき、たとえば、４×Ｎ領域を含む他のサイズの領域を使用してもよい。
【００６９】
図７を参照するに、８×８領域用の有意状態７０１は、パスを決定するロジック７０２への入力である。図３１は、典型的な８×８領域の説明図である。有意状態７０１は、たとえば、リファインメント・パスの行にＮ個の係数が存在することを示す情報を含む。このような情報は、上述のようなテーブルからアクセスされる。決定パスロジック７０２は、８×８領域の中央の６×６領域内の１６個の３×３領域を調べる。係数Ａ〜Ｉは、１番目の３×３領域を表現する。図３２は、決定パスロジック７０２の一実施例の構成図である。図３２におけるロジックは、４×４ブロック内の各係数に対して１回ずつとして、１６回繰り返される。領域は、３×３領域以外のサイズでもよく、処理される領域の数は、同時に１６個より多くても少なくても構わないことに注意する必要がある。
【００７０】
図３２を参照するに、係数Ａ〜Ｃの全ビットは、ＯＲゲート３２０１へ入力される。係数Ｄ及びＦの全ビットは、ＯＲゲート３２０２の入力へ供給される。係数Ｇ〜Ｉの全ビットは、ＯＲゲート３２０３の入力へ供給される。ＯＲゲート３２０１〜３２０３の出力は、ＯＲゲート３２０４の入力へ接続される。ＯＲゲート３２０４の出力は、インバータ３２０６の入力と、ＡＮＤゲート３２０８の入力とに接続される。係数Ｅは、リファインメント信号７０４の１６ビット出力を表わし、インバータ３２０５の入力へ供給され、インバータ３２０５の出力はＡＮＤゲート３２０８の別の入力と、ＡＮＤゲート３２０７の入力とに供給される。ＡＮＤゲート３２０８の出力は、有意プロパゲーション信号７０３である。インバータ３２０６の出力は、ＡＮＤゲート３２０７の他の入力へ供給される。ＡＮＤゲート３２０７の出力は、クリーンアップ信号７０５である。
【００７１】
動作中に、有意状態ビットＥのいずれかが０である場合、ＡＮＤゲート３２０８の出力は、０であるビットのビット位置に対応し、有意状態が係数Ａ〜Ｄ若しくは係数Ｆ〜Ｉのいずれかに対して１である場合に、有意プロパゲーション信号７０４は、１に変化する。同様に、有意状態ビットＥのいずれかのビットが０である場合、ＡＮＤゲート３２０７の出力は、そのビットのビット位置に対応し、これにより、クリーンアップ信号７０５は、係数Ａ〜Ｄ若しくは係数Ｆ〜Ｉに対する有意状態ビットが全て０である場合、１に変化する。
【００７２】
決定の結果として、ロジック７０２は、有意プロパゲーション信号７０３、リファインメント・パス信号７０４、又は、クリーンアップ・パス信号７０５のうちのいずれかをアサート（真の状態に）する。一実施例において、各信号７０３〜７０５は、１６ビット幅である。信号７０３、７０４及び７０５における対応した各ビットに対し、唯一のビットが１であり、他の２個のビットが０である。かくして、１６個のロケーションに３通りの確率が存在する。ロジック７０２の各出力は、選択ロジック（たとえば、マルチプレクサ（ＭＵＸ））７０７の一方の入力へ供給される。
【００７３】
選択ロジック７０７は、現在の係数に関して、現在の係数に対するパスを示す３個のパスビットを生成し、パスビットを制御ロジック７０９へ送る。３個のパスビットのうちの１ビットだけが、制御ロジック７０９から出力されたカウント信号７０８に応答してアサートされる。カウント信号７０８は、４×４ブロック内の１６個の係数のうちの何れの係数が現在処理中の係数であるかを示す。リファインメント・ビットラン及びクリーンアップ・ビットランを取り扱うとき、カウント信号７０８は１よりも大きい数でインクリメントされる。かくして、決定パスロジック７０２の各出力の１６ビットのうちで、その係数に対応した３個の出力毎のビットが出力される。
【００７４】
リファインメント・パス信号７０４及びクリーンアップ・パス信号７０５は、フィードバックカウント信号７０８と共に、マスク７０５へ入力される。カウント信号７０８は、４×４領域内の現在の係数位置、たとえば、０．．．１５である。これらの入力に応答して、マスク７０５は、カウント７０８によって示されるように、既に実行された係数をマスクし、未だ符号化されていない係数だけを組み入れる。たとえば、３個の係数が既に処理されているとき、マスク７０５は、リファインメント出力及びクリーンアップ出力（７０４及び７０５）の夫々の３個の信号ラインをマスクする。
【００７５】
マスク７０５は、（一実施例において）一部の信号が１にマスクされた信号７０４及び信号７０５を表現する２個の出力を生成し、優先度符号器７０６へ供給する。マスク７０５の出力は、マスクされたリファインメント標識及びマスクされたクリーンアップ標識（たとえば、信号）である。
【００７６】
２個の入力に応じて、優先度符号器７０６は、次のリファインメント・ビット（又は係数）と、有意プロパゲーション・パスに対する次の非クリーンアップ・ビットとを検出し、これらのビットを制御ロジック７０９へ入力する。一実施例において、優先度符号器７０６は、零検出優先度符号器である。その際、優先度符号器７０６は、符号ブロック内のビット（若しくは係数）の現在位置を先行する零のカウントに変換する。一実施例において、これは、以下の真理値表を使用して行なわれる。
【００７７】
真理値表
入力                    ｜    出力
１  ×  ×  ×  ×  ×  ｜    ０
０  １  ×  ×  ×  ×  ｜    １
０  １  １  ×  ×  ×  ｜    ２
(以下、同様に続く）。
【００７８】
マスク７０５、優先度符号器７０６、及び選択ロジック７０７は、決定パスユニット７０２からの出力を受信し、次の非リファインメント係数及び次の非クリーンアップ係数を示す出力と、現在係数に対するパスとを生成する処理ユニットを構成する。
【００７９】
入力に応答して、制御ロジック７０９は、リファインメント・次のインデックス、リファインメント・ラン標識、リファインメント・スキップ標識、クリーンアップ・次のインデックス、クリーンアップ・ラン標識、クリーンアップ・スキップ標識、及び、有意プロパゲーション標識を生成する。制御ロジックへの入力は、以下の通りである。
【００８０】
0004061104.tif 000015
【００８１】
以下の疑似コードは、図７に示された有意プロパゲーション・パスロジックの動作を説明する。
【００８２】
0004061104.tif 000016
【００８３】
有意状態は、"1"係数が有意プロパゲーション・パスで符号化されるときにいつでも、ＭＱ復号器（符号化中には、ＭＱ符号器、若しくは、係数値）から更新される。
【００８４】
コンテキストモデが１クロックサイクルで動作し、ＭＱ符号器が１クロックサイクルで動作する場合を考えると、二つのクロックサイクルはフィードバックが存在するときに必要とされる。図８には、最悪の状況が起こる可能性のある４×４ブロック上での性能の一例が示されている。８個のコンテキストモデルと、コンポーネントクロックレートの２倍で並列的に動作するＭＱ符号器は、１係数について７個のビットプレーンを復号化できなければならない（８×２／２．２５≒７）。有意プロパゲーション・パス内でスキップが生じない場合、最悪の状況の性能は、最大で１係数当たりについて５．５ビットプレーンまで低下する。何れのパスにおいてもスキップが生じない場合、最悪の状況における性能は、１係数あたりについて高々４ビットプレーンまで低下する。
【００８５】
〔ソフトウェアによる有意プロパゲーション・パススキップ〕
ソフトウェアの場合、多数のメモリからの並列アクセスは実現不可能である。そのため、一実施例では、符号ブロックは、係数の４×４グループに分割される。グループ毎に、カウントは、有意なビット数を維持する。このような場合、必要な最大メモリ量は、２５６×５ビットである。リファインメント・パスに存在する全ての係数のブロックのカウントは１６である。カウント０のブロックは、全てクリーンアップでもよく、全部がクリーンアップであるかどうかを調べるためには、近傍を検査するだけでよい。
【００８６】
〔クリーンアップ・パス及びリファインメント・パス〕
クリーンアップ・パスの場合、アドレッシングは、データに依存し、以下の疑似コードを用いて生成される。クリーンアップ・パス内の次の係数のアドレスｘ，ｙは、入力される。
【００８７】
0004061104.tif 000017
【００８８】
クリーンアップ・パスに使用されるアドレッシングは、リファインメント・パスにも使用される。しかし、リファインメント・パスの場合、より小さい近傍でも十分に足りる。
【００８９】
0004061104.tif 000018
【００９０】
〔全てのパスに対する逐次的なアドレッシング〕
全てのパスに対し逐次的なアドレッシングを行なう場合、二つのメモリを使用するより簡単なメモリ構成が用いられる。図９を参照するに、各４×４領域は、二つのメモリＡ又はＢのうちの一方に割り当てられる。これにより、１６×１６ブロックに対し要求されるあらゆる並列アクセスが可能になる。１番目の符号ブロックは半分しか使用されない。なぜならば、オフセットは上述のオフセットと類似し、一番上の２行が実際に処理されるデータを収容しない図６に示されるような８×８ブロックを処理するとき、係数の２行分だけが該当するからである。
【００９１】
図１０には、有意プロパゲーション・パスのため使用されるメモリ路のメモリ及びレジスタの一実施例が示されている。図１０によると、メモリＡは、アドレスＡに応答してデータ出力を生成する。同様に、メモリＢは、アドレスＢに応答してデータ出力を生成する。２×２クロスバー１００３は、メモリＡ及びＢの出力に接続された入力を有する。クロスバーの一方の出力はレジスタ１００１と、メモリ路の一方の出力と、に接続される。クロスバーのもう一方の出力は、レジスタ１００２と、メモリ路のもう一方の出力と、に接続される。かくして、メモリＡ及びＢの出力は、いずれかのレジスタ１００１及び１００２に保持され、いずれかのメモリ路へ出力される。メモリＡ及びＢから読み出されるデータは４×４領域に対するデータである。レジスタ１００１及び１００２は、５×４領域を格納する。レジスタがロードされたとき、最も右側の１×４列は、最も左側の１×４列へ移され、その他の列は、メモリデータ出力から入れられる。クロスバー１００３は、データが１行ずつ処理されるときに、データを出力へ行き来させることにより、メモリＡ及びＢからメモリ路の適切な出力へのデータの出力を制御する。
【００９２】
図１１は、図１０のメモリ及びレジスタがコンテキストモデル動作のため適切な領域を設けるため使用される状況を説明する図である。図１１によれば、領域１１０２は、処理されるべき係数の４×４領域である。領域１１０１は、コンテキストモデリングのため使用されたレジスタ１００１及び１００２に格納された５×６領域（５×６領域よりも上及び下の５×１領域は無視される）を表現する。領域１１０３は、メモリからの４×８領域である。領域１１０４は、コンテキストモデリングのため使用されたメモリからの１×６領域である。
【００９３】
三つの符号化パスの全てに対するメモリアドレッシング用の疑似コードの一実施例を以下に説明する。
【００９４】
0004061104.tif 000019
メモリは、リファインメント・パス及びクリーンアップ・パスのための正しいパスを示すため状態を収容する。状態は、三つの状態（有意プロパゲーション、クリーンアップ及びリファインメント）を識別するため、１係数毎に２ビットである。
【００９５】
有意プロパゲーション・パス中に、状態は、１６個の全ての係数に関して並列に、有意係数の場合にはリファインメントに設定され、非有意係数の場合にはクリーンアップに設定される。１６個の係数に関する処理が継続すると共に、有意プロパゲーション・パスに存在する係数の状態は、クリーンアップから有意プロパゲーションへ変更される。状態は、１係数毎に１ビットであり、この１ビットをパスビットと呼ぶ。一実施例において、有意状態及びパスビットは、正しいパスを決定するため使用される。表６は、パスビットの用法を例示する。係数１個について１ビットが使用されるので、メモリ使用量は、ここで説明するラン・スキップカウント法よりも減少する。
【００９６】
【表６】
0004061104.tif 000020
一実施例において、表６のリファインメント・パス内＊は、４×４ブロックに対する処理のスタート時に全１６係数に関して並列に行なわれる。
【００９７】
２×４領域へのアクセスを与えるメモリは、係数毎に有意状態と、パスビットと、サインビットとを備えた４８ビット幅でもよい。
【００９８】
図１２は、上記の表６を実現し、現在パスに存在する各係数を検出するため優先度符号器を使用するパス決定ロジックの一実施例のブロック図である。図１２を参照するに、決定パスロジック１２０３は、６×６領域に対する有意状態１２０１と、４×４領域に対するパスビット１２０２と、現在パスを示す現在パス信号（又はその他の標識）１２２０と、を受け取る。パスビット１２０２は、４×４領域内の係数毎の信号（すなわち、１６個の信号）を含む。これらの入力に応答して、決定パスロジック１２０３は、４×４領域に対するパスを指定するため出力を生成する。その際に、４×４領域における各係数に対し、決定パスロジック１２０３は、有意プロパゲーション・パス内の有意プロパゲーション・パスビットを示す信号１２０４、リファインメント・パス内の係数に対するリファインメント・パスビットを示す信号１２０５、又は、クリーンアップ・パス内の係数に対するクリーンアップ・パスを示す信号１２０６をアサートする。
【００９９】
選択ロジック１２０７は、現在パス信号１２２０に応答し、標識１２０４〜１２０６のうちの一つをマスクロジック１２０８へ出力する。一実施例において、選択ロジック１２０７は、１６×３：１マルチプレクサ（ＭＵＸ）を含む。マスクロジック１２０８は、カウント信号１２０１０に応答して信号を生成し、カウント信号は、現在処理されている係数を指定する。マスク１２０８の出力は、優先度符号器１２０９へ供給され、優先度符号器１２０９は、その信号を制御ロジック１２１２へ出力する。マスクロジック１２０８及び優先度符号器１２０９は、図７に示された同じ名前のロジック及び符号器と同じように動作する。制御ロジック１２１２は、入力に応答して、符号若しくはアイドル状態標識を信号ライン１２１３に生成し、カウント信号１２１０を生成する。
【０１００】
次のパスビットロジック１２１１は、優先度符号器１２０９からの（現在処理中の位置を示す）出力と、現在パス信号１２２０と、ＭＱ符号器からの新しい有意状態１２２１と、リファインメント・パス信号１２０５と、を受け取る。リファインメント・パス信号１２０５は、先行の係数が有意であるかどうかを示すことにより、有意状態情報を表現する。現在パス信号１２２０と、新しい有意状態１２２１は、全体として、処理がクリーンアップ・パスで行なわれているかどうかを示す。この入力に応答して、次のパスロジック１２１１は、次のパスビットを生成し、この次のパスビットは、表６における符号０のケースと符号１のケースを区別するために出力として使用される。次のパスビットは、メモリに保持され、次に、パスビット１２０２として使用される。
【０１０１】
次に、図１２におけるロジックの動作を疑似コードで説明する。このような機能は、ＭＱ符号器２９０８１−Ｎに組み込まれる。有意状態及びパスビットは、１回目のクリーンアップ・パスを処理する前にクリアされる。
【０１０２】
0004061104.tif 000021
【０１０３】
上記コードにおいて、変数in_passは、３：１多重化関数の出力である。変数maskは、マスクを表現し、変数in_pass_maskedは、マスクを適用した結果を表現する。変数Nは、パス中の次の係数を表現し、優先度符号器の出力である。変数Nが検出されると、符号体系の制御機能がその後に続く。
【０１０４】
上述のコードcode coeff Nは、係数が現在パスに存在するときに、係数を符号化することを意味する。コードidle for coeff Nは、ランを処理中に実行される。
【０１０５】
〔２重コンテキスト生成〕
コンテキストは、屡々、最後に符号化されたビットに依存し、復号化の際にＭＱ符号器とコンテキストモデルの間に時間的に重大なフィードバックループを生じさせる。このコンテキストモデル遅延を単純な多重化のための時間まで短縮するため、コンテキストモデルは、復号化中の現在ビットが０であるときのための一方のコンテキストと、復号化中の現在ビットが１であるときのためのもう一方のコンテキストの二つのコンテキストを生成することができる。ビットが既知である場合、コンテキストの選択が行なわれる。
【０１０６】
図１３は、２重コンテキスト生成ロジックの一実施例のブロック図である。図１３を参照するに、コンテキストモデルは、コンテキスト０、イネーブル０、コンテキスト１、及びイネーブル１を生成する。コンテキストモデルは、２個のコンテキスト０及び１を生成し、両方のコンテキストがマルチプレクサ（ＭＵＸ）１３０２へ送られる。マルチプレクサ１３０２は、信号を受信するよう接続され、コンテキストが有効であるかどうかを示すコンテキスト標識と、ビットを符号化すべきであるかどうかを示すイネーブル標識を生成する。これらの出力は、ＭＱ符号器１３０３の入力へ供給され、ＭＱ符号器はビットを生成する。ＭＱ符号器１３０３からの出力ビットは、ＭＱ符号器１３０３へ出力されるべきコンテキストを選択するためマルチプレクサ１３０２によって使用される。かくして、コンテキストモデルは、現在ビットが０として復号化されたときのコンテキストと、現在ビットが１として符号化されたときの別のコンテキストの２個のコンテキストを生成し、ＭＱ符号器１３０３のための出力ビットは、正しい方のコンテキストを選択する。
【０１０７】
クリーンアップ・パス用のランレングス符号化に対し、表７は、ケース毎に、二つの起こり得る次のコンテキストを示し、JPEG 2000標準に記載されたクリーンアップ・パスのフローに従う。ランレングスコンテキストで符号化されたビットの値は、次のコンテキストが次の４係数のグループ用であるか、現在の４係数のグループ用の均一のコンテキストであるかを判定するため使用される。このビットが０である場合、１回の判定で４係数を表現する際に後に続き、後のサイクルのためＭＱ符号器をアイドル状態にさせるランレングス符号化は、速度性能に重大な悪影響を与えない。２番目の均一コンテキスト（ユニフォームＢ）で符号化されたビットの後は、JPEG 2000標準において、（ＸＯＲビット０によって）コンテキスト９で常に直接的に符号化されるサインビットである。ここで、ＸＯＲビットが０であるとき、サインは反転されないことを意味する。
【０１０８】
【表７】
0004061104.tif 000022
表７中のＡ及びＢは、JPEG 2000標準のセクションＤ３．４に「均一なコンテキストと共に返される次の２ビット(the next two bits, returned with the UNIFORM context)」のようにに記載された２個のビットを表わす。
【０１０９】
有意プロパゲーション及びクリーンアップ符号化パスの場合に、ランレングス符号化を用いない例が表８に示されている。大きさビットは符号化されるが、コンテキストは、現在の係数が０であると仮定して次の係数の大きさに対して生成され、或いは、現在の係数に対してサインビットコンテキストが生成される。
【０１１０】
【表８】
0004061104.tif 000023
リファインメント・パスの場合、先に符号化されたリファインメント係数はコンテキストに影響を与えない。
【０１１１】
〔ＭＱ符号器〕
レートコンテキストを伴うＭＱ復号器データフロー
図１４Ｂは、典型的な復号化実現例のブロック図である。図１４Ｂにおいて、コンテキストモデル１４３０は、メモリ１４３１にコンテキストを供給し、メモリで確率状態が決定される。確率状態は、ロジック１４３２を用いて、算術符号器１４３３のためのＱｅ値に変換され、算術符号器１４３３は、内部Ａ＆Ｃレジスタを更新し、判定結果（ＭＰＳ又はＬＰＳ）を決定する。これらは、全て、典型的に次のコンテキストが決定できる前に行なわれる。殆どのハードウェア実現例の場合、復号化速度は、（コンテキストモデル１４３１へフィードバックする）大きいフィードバックループによって制限される。
【０１１２】
これに対し、図１４Ａは、初期コンテキストＭＱ復号器の一実施例のブロック図である。本例の場合、フィードバックループは、復号化動作全体の代わりに、非常に簡単なロジック１４０７を具備する。したがって、殆どの復号及び更新は、下位フィードバックループ１４０１を用いて並列的に行なわれ得る。
【０１１３】
図１４Ａを参照するに、符号ストリーム１４００が入力され、内部状態１４０１を更新する。一実施例において、内部状態のＡ及びＣレジスタは、JPEG 2000標準の付録Ｃに記載されているように、現在インターバルを指定する。レジスタＡは現在インターバルを指定し、符号レジスタＣは、ChighアンドClowレジスタの連結である。
【０１１４】
コンテキスト１４０２は、コンテキストモデル１４１０によって与えられる。コンテキスト１４０２は、メモリ１４０３の確率状態１４０４を調べるため使用され、確率状態は、ロジック１４０５によって確率クラス（Ｑｅ値）１４０６に変換される。Ｑｅ値１４０６は、低確率シンボル（ＬＰＳ）の現在推定値を表現する。Ｑｅ値１４０６は、ロジック１４０７を用いて、出力判定結果１４０８を生成するため、ＭＱ符号器の内部状態のJPEG 2000標準の図Ｃ−１５に記載されているＡレジスタ値及びＣレジスタ値と比較される。出力判定結果は、より確率が高い高確率シンボル（ＭＰＳ）若しくはＬＰＳである。出力判定結果１４０８は、コンテキストモデル１４１０へ入力される。一実施例において、Ｑｅ値及び内部状態に関する演算は、１６ビット演算を必要とする。これらのブロックの演算は、JPEG 2000標準のセクションＣ．３．２に記載されているような判定結果の復号化を実施する。
【０１１５】
図１５は、後期コンテキストＭＱ復号器の一実施例のブロック図である。図１５では、１６ビット処理がコンテキストモデルフィードバックループから除去されている。符号ストリーム１６０１は、更新ロジック１５０３への入力として受信され、更新ロジックは、内部状態を更新し、現在インターバルを指定するＡレジスタ及びＣレジスタを含む。新しいＡレジスタ値及びＣレジスタ値、並びに、符号ストリームは、ロジック１５０４へ入力され、ロジック１５０４は、以下で説明するような二つのｐクラス(pclass)、すなわち、ｐクラス１５０９及びｐクラス１５１０を生成する。二つのｐクラスは比較ロジック１５１１及び１５１２へ入力される。
【０１１６】
コンテキストモデル１５２０は、コンテキスト１５０２を生成する。コンテキスト１５０２は、メモリ１５０５の確率状態１５０６を調べるため使用される。一実施例において、メモリ１５０５は、ルックアップテーブルを含む。確率状態１５０６を確認することによって、Ｑｅ値を決定できるようになる。メモリ１５０５から出力された確率状態１５０６は、ロジック１５０７によって、確率クラス（インデックス）１５０８へ変換される。
【０１１７】
比較ロジック１５１１は、ｐクラス１５０９が確率クラスインデックス１５０８よりも大きいかどうかを判定し、比較ロジック１５１２は、確率クラスインデックス１５０８がｐクラス１５１０よりも大きいかどうかを判定するため比較を行なう。両方の比較ロジック１５１１及び１５１２の結果は、両方の比較結果が真である場合に、判定結果が出力されるように、ＡＮＤゲート１５１３へ入力される。この判定結果は、ＭＰＳ若しくはＬＰＳである。かくして、コンテキスト１５０２は、（JPEG 2000では、Ｑｅ値に対し３２個の値を取り得るので）５ビット確率クラスインデックス１５０８へ変換される。内部状態は、二つの５ビット確率クラスインデックスを生成するため使用される。コンテキストに対応したインデックスが状態から生成された二つのインデックスの外側にあるとき、判定結果はＭＰＳであり、さもなければ、判定結果はＬＰＳである（すなわち、二つのインデックスの内側にある）。
【０１１８】
図１５の実施例の重要な利点は、内部状態更新が、図１４Ｂに示されるように逐次的ではなく、次の確率クラス（インデックス）１５０８の生成と並行して行なわれることである。また、二つの確率クラスは、５ビットだけがｐクラスインデックスと比較されるので、演算は非常に簡単化される。
【０１１９】
図１５のロジック１５０４は、図１６Ａに示される情報を作成する。Ａレジスタ及びＢレジスタに値が与えられると、ロジック１５０４は、ｐクラスに対する二つの分割点が何であるかを決定し、次に、符号が分割点の間にあるか、又は、外側にあるかを判定する。これは，並列に行なってもよい。
【０１２０】
図１６Ａは、確率クラスインデックスの比較がどのように行なわれるかを示す図である。図１６Ａにおいて、ｐクラス０は、殆どのインターバルがＭＰＳへ向けられる非常に歪んだケースである。ｐクラス１からｐクラス４に対し、この歪みは小さくなり、ＭＰＳインターバルは縮小する。ｐクラス５は、ＭＰＳに５０％付近の確率に対して生じる条件付き交換を与える。既知状態は、一部の確率クラスに対してＭＰＳであり、他の確率クラスに対してＬＰＳである符号ストリーム値（符号）を有する。確率クラスは順序付けられているので、符号がＭＰＳであるか、ＬＰＳであるかを判定するためには、２回の比較だけで十分である。すなわち、図１６Ａにおいて、符号のロケーションが既知状態で与えられた場合、判定結果は、ｐクラス０〜３に対してＭＰＳであり、ｐクラス４に対しては常にＬＰＳであり、ｐクラス５に対してもＭＰＳである。各確率クラスに対しＭＰＳであるか、ＬＰＳであるかを見つけるのではなく、（ｐクラス３とｐクラス４の間のブレークポイント、及び、ｐクラス４とｐクラス５の間のブレークポイントの）二つのブレークポイントだけを判定すればよい。したがって、ＱＥ値が与えられたとき（確率クラス／インデックスが既知であるとき）、ブレークポイントが存在する空間に実際に現れる確率クラスが何であるかが決定される。
【０１２１】
ハードウェアにおける同様の方法は、起こり得るＱｅ値毎にＭＰＳかＬＰＳかを判定し、次に、その結果を多重化するために使用される。たとえば、図１６Ｂには、多数の入力を有するマルチプレクサ１６１０が示され、各入力はｐクラスと関連づけられ、符号に応じて、ＭＰＳ若しくはＬＰＳのいずれかを出力として生ずる。
【０１２２】
〔ＭＱ符号器による多重ビット復号化〕
多数のＭＰＳは、正規化を必要とするＭＰＳが存在しない限り、又は、最後のＭＰＳだけが正規化を必要とする限り、（同じＰクラスを継続して使用するため）同時に復号化可能である。図１７は、多重ＭＰＳ復号化のためのインターバルを示す。標準的に、ＡレジスタとＣレジスタによって指定されたインターバルに対する符号ストリームの場所と、Ｑｅ値との差が２以上であるならば、多数のＭＰＳを符号化することが可能である。インターバルサイズがＱｅ値によって分割され、復号器が同じコンテキストに留まる場合、すなわち、同じ確率クラスに留まる場合、多数のＭＰＳを同時に復号化することが可能である。たとえば、符号ストリームを調べ、処理されるのが１６ビットであることがわかったとき、ＡレジスタとＣレジスタによって指定されたインターバル内の符号ストリームの場所は、Ｑｅ値の倍数だけ離間し、同じコンテキスト、つまり、同じ確率クラスが多数のサイクルのデータを処理するために使用される予定であることを示し、多数のＭＰＳが同時に復号化される。つまり、
｛（ＡレジスタとＢレジスタによって指定されたインターバル）−（符号ストリームの場所）｝／Ｑｅ
が判定され、この値よりも大きい最小の整数に丸められたとき、その結果は、同時に復号化されるＭＰＳの個数を表わす。この計算は周知のハードウェアによって実行される。
【０１２３】
〔５，３フィルタの典型的な実現形態〕
一実施例において。可逆及び不可逆５，３ウェーブレットフィルタが使用される。ここで、５，３は、ウェーブレットフィルタ内のタップ数、すなわち、カーネルの基底関数サポートにおける非零（連続）値の数である。可逆とは、順変換と逆変換を実行すると、入力と厳密に同じ数が出力で得られることを意味する。入力精度に関して適度で予測可能な精度の増加が中間数学的項のため要求される。すなわち、数学的精度によって規則歪みは導入されない。不可逆とは、数学的歪みの無いこと（正確な再生）を保証するために、非常に高い精度が要求されることを意味する。しかし、実際上、不可逆フィルタは、殆どの場合に、規則的数学精度歪みを圧倒する歪みを生ずる量子化と組み合わされる。
【０１２４】
図２４には、順変換フィルタの一実施例が示されている。図２４によると、高域通過（ハイパス）フィルタ２４０２は、ラインバッファ２４０１からラインｘ０ｘ１及び最終ｘ０を受け取り、低域通過（ローパス）フィルタ２４０４の一つの入力へ供給され、ラインバッファ２４０３に保持される出力を生成する。ラインバッファ２４０１及び２４０３は、タイル幅を有する１本のラインを保持する。ローパスフィルタ２４０４は、ハイパスフィルタ２４０２の前のサイクルの出力、すなわち、ラインバッファ２４０３からの出力を、現在のｘ０ラインと共に受け取り、出力を生成する。過去の２クロックサイクルに対するローパスフィルタ２４０４の出力は、遅延器２４０５及び２４０６によって遅延され、１サイクル前のフィルタ出力と、２サイクル前のフィルタ出力を与える。
【０１２５】
ハイパスフィルタ２４０２の過去の出力は、遅延器２４０７及び２４０８によって遅延され、ハイパスフィルタ２４０２の現在出力と、ハイパスフィルタ２４０２の最後の２個の出力が、ハイパスフィルタ２４１３へ供給される。ハイパスフィルタ２４１３の出力は、ＨＨサブバンドにおける係数であり、ハイパスフィルタ２４０２の２サイクル前の過去の出力、すなわち、遅延器２４０８からの出力、及び、ハイパスフィルタ２４１３の前の出力と共に、ローパスフィルタ２４１５へ供給される。ローパスフィルタ２４１５の出力はＨＬサブバンドからの出力である。
【０１２６】
ローパスフィルタ２４０４の出力は、遅延器２４０５及び２４０６の出力と共に、ハイパスフィルタ２４０９へ供給される。ハイパスフィルタ２４０９の出力はＬＨサブバンドである。
【０１２７】
ハイパスフィルタ２４０９の出力は、遅延器２４０６の出力、及び、遅延器２４１０によって遅延されたハイパスフィルタ２４０９の前の出力と共に、ローパスフィルタ２４１１の入力へ供給される。ローパスフィルタ２４１１の出力はＬＬサブバンドである。ローパスフィルタ２４１１の出力であるＬＬサブバンドがラインバッファ２４１２へ供給されるとき、ラインバッファ２４１２の出力は、ローパスフィルタ２４１１の出力と共に、ウェーブレット変換の次のレベルへの入力を表わす。ウェーブレット変換の次のレベルは、図２４に示されたウェーブレット変換を縦続接続したものである。
【０１２８】
図２５Ａは、ここで説明される変換（たとえば、上述の５，３変換）で使用されるようなローパスフィルタの一実施例の説明図である。ローパスフィルタは、−ｘ０＋２ｘ１−ｘ２
に従う関数に基づいて出力を生成するよう設計される。可逆変換の場合、ローパスフィルタは、次式
【０１２９】
【数１】
0004061104.tif 000024
に従って動作する。
【０１３０】
図２５Ａを参照すると、加算器２５０１は、最後のｘ０ラインを現在のｘ０ラインと加算する。最下位ビット出力は、図２５Ｂのハイパスフィルタの出力を表わし、不可逆変換のため使用される。残りのビットは、減算器２５０２へ供給され、最上位ビットを表現する出力を生成するためｘ１入力から減算される。これらの最上位ビットは、すべて可逆変換の場合に必要である。逆ウェーブレット変換の場合、図２５Ａのフィルタを、逆変換で奇数（ハイパス）フィルタとして使用するための逆ウェーブレットフィルタに切り替えるため、減算器２５０２は加算器で置換される。このような一例は、図２５Ｂのハイパスフィルタに示されている。
【０１３１】
図２６Ａは、ここで説明する変換に使用されるハイパスフィルタの一実施例の説明図である。不可逆変換の場合、ハイパスフィルタは、以下の式、
４ｘ１−ｘ０−ｘ２
に従って動作する。
【０１３２】
可逆変換の場合、ハイパスフィルタは、次式、
【０１３３】
【数２】
0004061104.tif 000025
に従って動作する。
【０１３４】
図２６Ａを参照すると、加算器２６０１は、最後のｘ０ラインの可逆側又は不可逆側のいずれかを現在のｘ０ラインに加算する。加算器２６０１の出力は、加算器２６０３を用いて丸め項に加算される。丸め項は、可逆側の場合には２であり、不可逆側の場合には０であり、マルチプレクサ２６０２によって供給される。加算器２６０３の下位２ビットを除く出力は、加算器２６０４を用いて、ｘ１ラインに加算され、可逆側出力を生ずる。加算器２６０３の出力の下位２ビット、及び、加算器２６０４の出力は、不可逆側出力を表わす。
【０１３５】
マルチプレクサ２６０２を用いることによって、可逆側と不可逆側を切り替えるために、両方の機能のための完全に別個のハードウェアを必要とすることなく、或いは、可逆側丸めが不可逆側出力に影響を与えることを要することなく、簡単な切り替えを実現できるようになる。
【０１３６】
逆ウェーブレット変換の場合に、図２６Ａのフィルタを、逆変換中の偶数（ローパスフィルタ）として使用するための逆ウェーブレットフィルタに切り替えるため、加算器２６０４は減算器で置換される。このような一例は、図２６Ｂのローパスフィルタに示されている。
【０１３７】
図２７は、図２４における変換の代替的な実施例を示す図であり、イメージ境界でミラーイメージ処理を実行するためのマルチプレクサを含む。マルチプレクサは、マルチプレクサ２７０１から２７１２により構成される。たとえば、マルチプレクサ２７０１は、バッファ２４０１にラインが存在しないとき（たとえば、タイルの一番上）、境界において最後のｘ０ラインの代わりにｘ０ラインを使用する。マルチプレクサ２７０２は、タイルの一番下に到達したときに入力されるべき更なるｘ０ラインが存在しない場合、ラインバッファが他の入力をローパスフィルタ２４０４へ供給できるようにする。同様に、マルチプレクサ２７０３は、バッファ２４０３にラインが存在しない場合、ハイパスフィルタ２４０２の出力がローパスフィルタ２４０２への入力として利用できるようにさせる。マルチプレクサ２７０４は、ハイパスフィルタ２４０２からの出力が無い場合、ローパスフィルタ２４０４への入力を、ラインバッファ２４０３から供給できるようにする。マルチプレクサ２７０５及び２７０６は、ローパスフィルタ２４０４への出力及び遅延器２４０６からの出力が利用できないとき、ハイパスフィルタ２４０９への入力に、それぞれ、遅延器２４０６の出力、及び、ローパスフィルタ２４０４の出力を供給できるようにする。マルチプレクサ２７０９及び２７０１と、マルチプレクサ２７０７及び２７０８と、マルチプレクサ２７１１及び２７１２についても、マルチプレクサ２７０５及び２７０６と同様のことが成り立つ。
【０１３８】
図２８は、逆５，３変換の一実施例のブロック図である。図２８を参照するに、偶数フィルタ２８１５は、ＬＬ係数、ＨＬ係数、及び、遅延器２８８０１からの前のサイクルのＨＬ係数を、受け取るように接続されている。偶数フィルタ２８１５の出力は、偶数フィルタ２８１１の一入力と、遅延器２８０２の一入力と、奇数フィルタ２８０３の一入力とへ接続される。奇数フィルタ２８０３の別の入力には、遅延器２８０１を介して前のサイクルのＨＬ係数が供給され、遅延器２８０２を介して、偶数フィルタ２８１５の前のサイクルの出力が供給される。奇数フィルタ２８０３の出力は偶数フィルタ２８１０の一入力へ接続される。
【０１３９】
フィルタ２８０５は、現在のＨＨ係数及びＬＨ係数と、遅延器２８０４からの前のサイクルにおけるＨＨ係数とを受け取るように接続されているので、上記の構成と同じような構成がＬＨ係数及びＨＨ係数に関しても存在する。偶数フィルタ２８０５の出力は、偶数フィルタ２８１１の一入力と、遅延器２８０６の入力と、奇数フィルタ２８０７の一入力とへ接続される。奇数フィルタ２８０７の別の入力には、前のサイクルのＨＬ係数（すなわち、遅延器２８０４の出力）と、偶数フィルタ２８０５の前のサイクルの出力（すなわち、遅延器２８０６の出力）と、が供給される。奇数フィルタ２８０７の出力は偶数フィルタ２８１０の一入力へ接続される。
【０１４０】
偶数フィルタ２８０５の出力及び奇数フィルタ２８０７の出力は、それぞれ、ラインバッファ２８０８及びラインバッファ２８０９へ供給され、保持されることに注意する必要がある。ラインバッファ２８０８及び２８０９のサイズは、タイル幅の１／２に一致する。ラインバッファ２８０８の出力は、偶数フィルタ２８１１の別の入力と、奇数フィルタ２８１５の一つの入力とに接続される。ラインバッファ２８０８の出力は、偶数フィルタ２８１０の一つの入力と、奇数フィルタ２８１４の一つの入力とに接続される。
【０１４１】
偶数フィルタ２８１０の出力は、出力される画像データの”Ｃ”部分であり、ラインバッファ２８１２に保持され、奇数フィルタ２８１４の入力に供給される。一実施例において、ラインバッファ２８１２のサイズは、タイル幅の１／４に一致する。この入力に応答して、奇数フィルタ２８１４は、画像データの”Ａ”部分に対応するデータを生成する。
【０１４２】
偶数フィルタ２８１１の出力は、画像データの”Ｄ”部分に対応し、奇数フィルタ２８１５の一つの入力へ供給され、ラインバッファ２８１３に保持される。一実施例において、ラインバッファ２８１３のサイズは、タイル幅の１／４である。ラインバッファ２８１３の出力は奇数フィルタ２８１５の別の入力へ接続される。奇数フィルタ２８１５の出力は、画像データの”Ｂ”部分に対応する。
【０１４３】
〔その他の並列方式実施技術〕
符号ブロックの並列用符号器への割り付け
ハードウェアの実施例の場合、同じタイル内で並列に多数の符号ブロックを符号化することが有効である。図２１は、多数のＭＱ符号器を含む符号器の一実施例のメモリ使用量説明図である。各ＭＱ符号器は、関連したコンテキストモデルを具備し、多数の符号ブロックを処理するため使用される。
【０１４４】
図２１を参照すると、各ＭＱ符号器は、メモリ（たとえば、別々のメモリ、単一若しくは多数のメモリの一部）が割り付けられる。一実施例において、割り付けられたメモリのある部分は、符号化データを保持し、長さ、零ビットプレーン、及び、符号化パスはメモリの別の部分に保持される。
【０１４５】
図１８〜２０には、１２８×１２８タイル、６４×６４符号ブロック、及び、夫々の変換レベルに関する符号ブロックの並列ユニットへの割当が示されている。割当は、並列符号器毎に実行される符号化の量が均衡するに行なわれる。一実施例において、符号ブロックの割当は、各ＭＱ符号器が、できるだけ可能な範囲で、上位レベル係数と下位レベル係数の間で均衡を保ちながら略同数の係数を符号化するように、行なわれる。これ以外の構成も実現可能である。
【０１４６】
図１８Ａ、Ｂ及びＣには、それぞれ、４台、６台及び８台のＭＱ符号器が並列に使用された場合の４：４：４データに関する符号ブロックの割当の実施例が示されている。図１８Ｃにおいて、８個のユニットが並列である場合、並列ユニット”Ｈ”（１ＨＨクロミナンスサブバンド）に割り当てられた符号ブロックは、屡々、重く量子化されるので（符号化すべき非零ビットプレーンが殆ど存在しないので）、このユニットは、単位時間当たりに処理できる係数の数が他のユニットよりも多くなる可能性が高い。
【０１４７】
図１９Ａ、Ｂ及びＣには、それぞれ、４台、６台及び８台のＭＱ符号器が並列に使用された場合の４：２：２データに関する符号ブロックの割当の実施例が示されている。
【０１４８】
図２０Ａ、Ｂ及びＣには、それぞれ、４台、６台及び８台のＭＱ符号器が並列に使用された場合の４：１：１データに関する符号ブロックの割当の実施例が示されている。図２０Ｃにおいて、８個のユニットが並列である場合、ユニットＣ、Ｄ及びＥが単位時間当たりに処理できる係数の数は、他のユニットよりも多くなることが予想される。
【０１４９】
図２９の符号器は、上述の符号化を実行するため使用される。たとえば、ビットモデリングＭＱ符号器２９０８１−ＮのＮ台のＭＱ符号器のうちの各符号器は、図１８乃至２０に示されたＡ〜Ｈのいずれかに割り当てられる。
【０１５０】
図１８乃至２０に関して、偶数台のＭＱ符号器が並列にされているが、並列にされるＭＱ符号器の台数は奇数台でも構わない。
【０１５１】
係数をハードウェアに格納するためのメモリ節約
無損失の復号化ではないときに、係数を保持するメモリ使用量を削減するために、零ビットプレーン変換を利用することが可能である。ハードウェアが係数毎にＮ個のビットプレーンを保持できる場合、復号化は、Ｎ個のビットプレーンが復号化された後に終了する。後続のビットプレーンは量子化（丸め処理）を行なうことが可能である。
【０１５２】
図２２Ａは、符号化中に、係数毎に、メモリの有限個のビットプレーンを使用する例が示されている。たとえば、メモリの８個のビットプレーン（Ｎ＝８）は、標準的な表現形式で、係数を１６ビットによって符号化するため使用され得る。これらの係数は、（ＬＬサブバンド係数は量子化されない）ＬＬサブバンド以外のサブバンドの一部であり、ウェーブレット変換を画像データに適用した結果として生成される。一実施例において、ウェーブレット変換は、５，３ウェーブレット変換を含む。ウェーブレット変換は、ＬＬサブバンド、ＨＨサブバンド、ＬＨサブバンド及びＨＬサブバンドを並列に生成するため、並行動作する多数の５，３ウェーブレット変換により構成しても構わない。ウェーブレット変換からの係数を保持するメモリは、係数ビットに基づく符号化を実行するため、コンテキストモデルによってアクセスされる。
【０１５３】
符号化中に、係数は、零ビットプレーンの数が既知になる前に保存される。カウンタは、上位のビットプレーン８〜１５に対する初期零の数をカウントする。ビットプレーン８〜１５が全て零である限り、メモリは、対応したビットプレーン０〜７に対する情報（大きさ）を保持する。ビットプレーン８〜１５に１が出現した場合、対応したカウンタは停止し、メモリは対応したビットプレーン８〜１５の情報を保持する。符号ブロックの符号化の最後に、カウンタがビットプレーン８〜１５に対し全て零を指定し、対応したビットプレーン０〜７は、カウンタがメモリの最後に値を格納した場合にメモリに収容するか、又は、カウンタはメモリ内のビットプレーン８〜１５に対する開始アドレスを指定し、対応したビットプレーン０〜７を丸め処理（量子化）する必要がある。かくして、カウントは、サイドバンド情報として作用し、行の始まりからカウントによって指定された行内の位置までメモリアレイに保持された情報が必要の無いデータになったことを示す。
【０１５４】
メモリの別々のビットプレーンはサイン情報を保持するため使用されるか、又は、サイン情報は有意状態と共に保持される。
【０１５５】
他の実施例において、小量のメモリが、カウンタの代わりに、可変長（ＶＬ）符号情報（たとえば、ランレングス符号）のため使用される。これにより、少数の”１”ビットを含むビットプレーンを、ビットプレーン毎にメモリの一部分に格納することが可能になる。ビットをメモリに格納した後、コンテキストモデルは，ビットを取得するためメモリにアクセスする。しかし、各行は、潜在的に、量子化されるべきデータを含んでいるので、コンテキストモデルによってアクセスされ、使用される必要が無い。図２２Ｂは、メモリへのアクセスを制御するための制御ロジックの一実施例のブロック図である。このロジックは、メモリをアクセスするコンテキストモデルと協働して、或いは、コンテキストモデルの一部として動作する。
【０１５６】
図２２Ｂを参照するに、アドレスａｄｄｒは、ビットを生成するメモリアレイ２２０１にアクセスする。アドレス、及び、アドレスを収容したメモリの行と関連したカウンタ値は、比較ロジック２２１０へ供給される。比較ロジック２２１０において、アドレスが行に対するカウンタ値以上であると判定された場合、メモリアレイ２２０１からの１ビット出力が生成され、そうでなければ、零が出力される。
【０１５７】
図２３は、ＶＬ符号からのメモリの一部分と、係数を格納するメモリアレイとを示す図である。ＶＬ符号は、行内で次の”１”が現れるまでスキップするビット数を示すことによって１ビットの有無を指定するため使用される。かくして、このＶＬ符号は、アクセスロジックが次のビットプレーンの場所を知ることができるように２個のカウントを指定するため作成される。他のＶＬ符号は、３個以上のカウントを与えるため使用される。ＶＬ符号を使用することによって、典型的に、満杯よりも一つ少ないメモリのビットプレーンを使用できるようになる。小容量メモリのサイズが（１ビットプレーン当たり）符号ブロックのサイズの１／３２であるならば、Ｒ２［８］符号又はＲ２［７］符号を使用してもよい。Ｒ２［８］、Ｒ２［６］、及びＲ２［７］符号の詳細な情報は、本願の譲受人に譲受された、米国特許第5,381,145号、発明の名称"Method and Apparatus for Parallel Decoding and Encoding of Data"、1995年1月10日発行に記載されている。
【０１５８】
変換及びコンテキストモデル／ＭＱ符号器の並列動作が望ましいビデオの場合、２個のメモリバンクが必要になる。静止画像アプリケーションの場合、変換及びコンテキストモデル／ＭＱ符号器の逐次的動作のために１個のメモリバンクで十分である。
【０１５９】
上記のメモリ節約技術は行に関して説明されているが、たとえば、列、ブロック、ページ、領域などの任意のメモリ領域を使用することができる。或いは、別個のメモリを使用してもよい。
【０１６０】
パケットヘッダ処理
たとえば、JPEG 2000符号ストリーム（又は、ビットストリーム）のような符号ストリームを作成するため、パケットヘッダが作成される。一実施例において、この情報は、任意の個数の符号ブロックを取り扱うためタグ木構造を伴う。ある種の状況では、制限された個数の符号ブロックを備えたタイル用のタイルヘッダが作成される。たとえば、タイルが、４個の１２８×１２８サブバンドを含み、各サブバンドが６４×６４符号ブロックに分割される場合、一体として符号化される符号ブロックの個数は４個である。パケットヘッダは、特定の符号ブロックに対するデータが存在するかどうか、データが存在する場合の零ビットプレーンの個数、符号化データの長さ、及び、データに含まれる符号化用パスの個数を指定する。
【０１６１】
以下の表９は、２×２符号ブロック及び１レイヤを含むパケット用のパケット構造の一実施例を示す。表９を参照するに、タグ木構造は、２レベルの深さしかない。記号”ｚ”は、最高レベルの零ビットプレーンのタグ木構造情報の場所を示し、記号”＿”で示された場所は、残りの零ビットプレーン、符号化用パス及び長さ情報の置かれる場所を示す。
【０１６２】
【表９】
0004061104.tif 000026
表中、＊は、０又は１０又は１１００００を表わす。
【０１６３】
一実施例において、符号110000は、実現例の便宜上、符号ブロックが包含されない場合に使用される。
【０１６４】
制限された数の符号ブロック及び単一レイヤを備えたタイル用のパケットヘッダを書き込む手続の一実施例は、以下のような初期化：
サブバンド毎に、零ビットプレーン最小値ＭＺＰに最大値を設定
から始まる。
【０１６５】
一実施例において、ＭＺＰの最大値は、１５ビットプレーンまでの場合、0xFであり、３１ビットプレーンまでの場合、0x1Fである。使用される値が大きくなると共に、実施例で取り扱い得るビットプレーンの数が増加する。
【０１６６】
次に、パケット内で各符号ブロックの係数を符号化するとき、
Save included or not bit（包含又は包含されないビットを保存）
Save number of zero bitplanes（零ビットプレーンの個数を保存）
If zero bitplanes less than MZP then MZP = zero bitplanee（零ビットプレーンがＭＺＰ未満であるならば、ＭＺＰ＝零ビットプレーン）
Save number of coding passes（符号化用パスの個数を保存）
Save Length（長さを保存）
を実行する。
【０１６７】
Save included or not bitは、（量子化後の）全ての係数が零である場合に、セットされ、符号ブロックが包含されないことを指定する。最終的に、タイル若しくはサブバンドの情報が処理された後、パケットヘッダは以下のように記述される。
【０１６８】
0004061104.tif 000027
ここで、Lblockは、JPEG 2000標準のセクションB.10.7.1に規定されている。
【０１６９】
パケットヘッダは、少なくとも１バイトであり、JPEG 2000準拠式復号器は、書き込まれた情報を認識できることに注意する必要がある。
【０１７０】
多数のレイヤが存在する場合、ＭＺＰ変数の初期化は、１レイヤのバイト同様に行なわれる。各符号ブロックの符号化中に、包含又は非包含の指標、符号化用パスの個数、及び、長さがレイヤ毎に保存される。さらに、以下の初期化処理が好ましい。
【０１７１】
first_flag = 1
initialize Lblock for each code-block    initialize already included for each code-block to false一実施例において、Lblockは３へ初期化される。"already included"が真であるとき、一部の先行レイヤがデータを符号化したことを意味する（すなわち、符号ブロックが過去に出現している）。
【０１７２】
レイヤ毎にパケットを書き込むため、以下の手続が使用される。
【０１７３】
0004061104.tif 000028
"already included"情報は、各符号ブロックに対し別個のビットでも構わない。或いは、零ビットプレーンの使用されない値を"already included"を指定するため使用してもよい。たとえば、１４個のビットプレーンが存在する場合、零ビットプレーンを１５(0xF)にセットすることによって、"already included"を示すことが可能である。
【０１７４】
”０”パケットを使用しない圧縮符号化データ
JPEG 2000の場合、パケットヘッダはバイト単位に丸められる。一部のケースでは、しかし、パケットヘッダは、唯一の零ビット、若しくは、パケットヘッダをバイト境界に収容するために必要なビット数よりも少ない多数のビットを格納する。パケットヘッダは、一般的に、パッディングによってバイトに丸められる。また、パケットヘッダ表現形式は、固有ではなく、典型的には、できるだけ短い表現形式の使用が望まれるが、一実施例では、使用される過剰ビットがパッディングによって埋められるであろうビット場所の代わりをするならば、考えられる最短の形式ではない表現形式が使用される。これは、過剰ビットで符号化された情報がタイルコンポーネントレベル分割における次のパケットに関する情報を示す場合に、特に有効である。
【０１７５】
たとえば、単一のサブバンドが存在し、２×２ブロックが包含される場合、零パケットを出力する。しかし、同じ空間量で、パケットに何かが存在し、タグ木構造の一番上のレベルには何も包含されていない、ということを示すために零を出力してもよい。或いは、タグ木構造に何かが存在し、それが００００である（すなわち、４箇所に個別には何も存在しない）ことを示すことも可能である。かくして、これらの過剰ビットは、より多くのタグ木構造情報を与えるため使用される。このタグ木構造情報は、後でパケットヘッダに出現し、必ず繰り上げられるであろう情報である。ビットを先行のパケットヘッダへ繰り上げることにより、符号ストリーム全体のサイズを１バイトずつ（或いは、それ以上）縮小することが可能である。
【０１７６】
以上の説明から、本発明の多数の代替及び変更が当業者に明らかになるであろう。しかし、例示のために解説され、図示された具体的な実施例は、本発明を制限することを意図していないことに注意する必要がある。したがって、多数の実施例の詳細の説明は、本発明に不可欠であると考えられる事項だけが記載された請求項に挙げられた事項の範囲を制限することを意図したものではない。
【図面の簡単な説明】
【図１】  JPEG2000復号化体系のブロック図である。
【図２Ａ】係数毎にサブビットプレーンパスが識別され、各符号化パスのための処理の順序を示すラベルが付けられた係数の８×８符号ブロックの一例を示す図である。
【図２Ｂ】可変長ラン・スキップカウント用メモリの説明図である。
【図３】（Ａ）〜（Ｄ）は、コンテキストモデルの一実施例に対する近傍係数とメモリ構成を示す図である。
【図４】１６×１６符号ブロックのランダムアクセス用の有意メモリ構成の一実施例の説明図である。
【図５】ランダムアクセス用の有意プロパゲーション・パスに使用されるメモリ及びレジスタを示す図である。
【図６】メモリからランダムアクセス用レジスタに格納された有意状態を示す図である。
【図７】有意プロパゲーション・パスロジックの一実施例のブロック図である。
【図８】４×４ブロック上のコンテキストモデルの一実施例の性能の一例を示す図である。
【図９】１６×１６符号ブロックのシーケンシャルアクセス用有意メモリの構成の一実施例の説明図である。
【図１０】有意プロパゲーション・パスのため使用されるメモリ及びレジスタの一実施例の説明図である。
【図１１】コンテキストモデル動作用の適切な領域を与えるためのメモリ及びレジスタの使用法の説明図である。
【図１２】パス決定ロジックの一実施例のブロック図である。
【図１３】２重コンテキスト生成ロジックの一実施例のブロック図である。
【図１４Ａ】初期コンテキスト型ＭＱ符号器の一実施例のブロック図である。
【図１４Ｂ】典型的な復号化実現方式の一実施例の説明図である。
【図１５】後期コンテキスト型ＭＱ符号器の一実施例のブロック図である。
【図１６Ａ】確率クラスインデックスの比較の動作状態の説明図である。
【図１６Ｂ】各Ｑｅ値に対するＭＰＳ又はＬＰＳを決定するマルチプレクサのブロック図である。
【図１７】多重ＭＰＳ復号化のためのインターバルの説明図である。
【図１８】４：４：４データに対する並列的な符号ブロックの割当の一実施例の説明図である。
【図１９】４：２：２データに対する並列的な符号ブロックの割当の一実施例の説明図である。
【図２０】４：１：１データに対する並列的な符号ブロックの割当の他の一実施例の説明図である。
【図２１】個々に関連性コンテキストモデルを有する多数のＭＱ符号器を含む符号器の一実施例のメモリの構成図である。
【図２２Ａ】符号化中に各係数に対し制限された数のメモリのビットプレーンを使用する例の説明図である。
【図２２Ｂ】メモリへのアクセスを制御するための制御ロジックの一実施例のブロック図である。
【図２３】カウンタの代わりに、可変長（ＶＬ）符号情報用の小容量のメモリを使用する例の説明図である。
【図２４】順変換の一実施例のブロック図である。
【図２５Ａ】ローパスフィルタの一実施例のブロック図である。
【図２５Ｂ】ハイパスフィルタの一実施例のブロック図である。
【図２６Ａ】ハイパスフィルタの一実施例のブロック図である。
【図２６Ｂ】ローパスフィルタの一実施例のブロック図である。
【図２７】順変換の他の一実施例のブロック図である。
【図２８】逆変換の一実施例のブロック図である。
【図２９】符号器／復号器の一実施例のブロック図である。
【図３０】ランカウント及びスキップカウントの両方を有する１６ビット語の一例の説明図である。
【図３１】符号化パスを決定する有意状態ビットの典型的な８×８領域の説明図である。
【図３２】パスロジックを決定する一実施例の構成図である。
【符号の説明】
２９０１    画像データインタフェース
２９０２    ＤＣレベルシフタ
２９０３    ウェーブレット変換器
２９０５    スカラー量子化／逆量子化器
２９０６    プリコーダ
２９０７    パケットヘッダ処理器
２９０８    ビットモデリングＭＱ符号器
２９１１    符号メモリ
Ａ，Ｂ      ワークメモリ
【図１】
0004061104.tif 000029
【図２Ａ】
0004061104.tif 000030
【図２Ｂ】
0004061104.tif 000031
【図３】
0004061104.tif 000032
【図４】
0004061104.tif 000033
【図５】
0004061104.tif 000034
【図６】
0004061104.tif 000035
【図７】
0004061104.tif 000036
【図８】
0004061104.tif 000037
【図９】
0004061104.tif 000038
【図１０】
0004061104.tif 000039
【図１１】
0004061104.tif 000040
【図１２】
0004061104.tif 000041
【図１３】
0004061104.tif 000042
【図１４Ａ】
0004061104.tif 000043
【図１４Ｂ】
0004061104.tif 000044
【図１５】
0004061104.tif 000045
【図１６Ａ】
0004061104.tif 000046
【図１６Ｂ】
0004061104.tif 000047
【図１７】
0004061104.tif 000048
【図１８】
0004061104.tif 000049
【図１９】
0004061104.tif 000050
【図２０】
0004061104.tif 000051
【図２１】
0004061104.tif 000052
【図２２Ａ】
0004061104.tif 000053
【図２２Ｂ】
0004061104.tif 000054
【図２３】
0004061104.tif 000055
【図２４】
0004061104.tif 000056
【図２５Ａ】
0004061104.tif 000057
【図２５Ｂ】
0004061104.tif 000058
【図２６Ａ】
0004061104.tif 000059
【図２６Ｂ】
0004061104.tif 000060
【図２７】
0004061104.tif 000061
【図２８】
0004061104.tif 000062
【図２９】
0004061104.tif 000063
【図３０】
0004061104.tif 000064
【図３１】
0004061104.tif 000065
【図３２】
0004061104.tif 000066