(57)【特許請求の範囲】
【請求項１】
画像をタイル分割し、各タイル毎に独立にウェーブレット変換して得られたウェーブレット係数データを再構成するウェーブレット係数再構成処理方法であって、
ａ）タイル境界によって影響を受けるＤＳ係数及びＤＤ係数をセーブするステップ、
ｂ）前記ＳＤ係数の値を所定の重み係数を用いて計算して置き換えて、該ＳＤ係数を前記タイル境界をまたいで平滑になるように再構成するステップ、
ｃ）逆垂直変換を各タイルに独立に適用するステップ、
ｄ）前記逆垂直変換して得られるＤ係数の値を所定の重み係数を用いて計算して置き換えて、該Ｄ係数を前記タイル境界をまたいで平滑になるように再構成するステップ、
及び
ｅ）逆水平変換を各タイルに独立に適用するステップ、
からなることを特徴とするウェーブレット係数再構成処理方法。
【請求項２】
各階層レベルのウェーブレット係数データに対して、前記ａ）からｅ）までのステップを繰り返すステップをさらに有することを特徴とする請求項１記載のウェーブレット係数再構成処理方法。
【請求項３】
前記ＳＤ係数及びＤ係数を実際の量子化係数と矛盾しないようにクリッピングするステップをさらに有することを特徴とする請求項１記載のウェーブレット係数再構成処理方法。
【請求項４】
画像をタイル分割し、各タイル毎に独立にウェーブレット変換して得られたウェーブレット係数データを再構成するウェーブレット係数再構成処理装置であって、
タイル境界によって影響を受けたＤＳ係数及びＤＤ係数をセーブする手段、
前記ＳＤ係数の値を所定の重み係数を用いて計算して置き換えて、該ＳＤ係数を前記タイル境界をまたいで平滑になるように再構成する手段、
逆垂直変換を各タイルに独立に適用する手段、
前記逆垂直変換して得られるＤ係数の値を所定の重み係数を用いて計算して置き換えて、該Ｄ係数を前記タイル境界をまたいで平滑になるように再構成する手段、
及び
逆水平変換を各タイルに独立に適用する手段、
からなることを特徴とするウェーブレット係数再構成処理装置。
【請求項５】
前記のセーブする手段、ＳＤ係数を再構成する手段、逆垂直変換を適用する手段、Ｄ係数を再構成する手段、及び、逆水平変換を適用する手段が、各階層レベルのウェーブレット係数データに対し独立に作用することを特徴とする請求項４記載のウェーブレット係数再構成処理装置。
【請求項６】
前記ＳＤ係数及びＤ係数を実際の量子化係数と矛盾しないようにクリッピングする手段をさらに有することを特徴とする請求項４記載のウェーブレット係数再構成処理装置。
【請求項７】
画像をタイル分割し、各タイル毎に独立にウェーブレット変換して得られたウェーブレット係数データを再構成処理するためのプログラムが記録された記録媒体であって、
タイル境界によって影響を受けるＤＳ係数及びＤＤ係数をセーブする処理、
前記ＳＤ係数の値を所定の重み係数を用いて計算して置き換えて、該ＳＤ係数を前記タイル境界をまたいで平滑になるように再構成する処理、
逆垂直変換を各タイルに独立に適用する処理、
前記逆垂直変換して得られるＤ係数の値を所定の重み係数を用いて計算して置き換えて、該Ｄ係数を前記タイル境界をまたいで平滑になるように再構成する処理、
及び
逆水平変換を各タイルに独立に適用する処理を、
コンピュータに実行させるプログラムが記録されたことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ圧縮及び伸長システムの分野に係り、特に、圧縮／伸長システムにおけるロスレス及びロッシーのデータ符号化及び復号化に関し、詳しくは、ウェーブレツト変換係数の再構成処理技術に関する。
【０００２】
【従来の技術】
データ圧縮は、大量のデータの蓄積及び伝送のために非常に有用なツールである。例えば、文書のファクシミリ伝送のような画像伝送に要する時間は、圧縮を利用して画像の再生に必要とされるビット数を減らすと飛躍的に短縮される。
【０００３】
従来より、多くの様々なデータ圧縮手法が存在している。圧縮手法は、おおまかに分類すると２つのカテゴリー、つまりロッシー符号化とロスレス符号化とに分けることができる。ロッシー符号化とは、情報の損失が生じ、したがって元のデータの完全な再現が保証されない符号化のことである。ロッシー符号化の目標とするところは、元のデータから変わったとしても、その変化が不快であったり目だったりしないようにすることである。ロスレス圧縮では、情報がすべて保存され、データは完全に復元可能な方法で圧縮される。
【０００４】
ロスレス圧縮では、入力シンボルもしくは輝度データが出力符号語に変換される。入力としては、画像データ、音声データ、１次元データ（例えば空間的または時間的に変化するデータ）、２次元データ（例えば２つの空間軸方向に変化する（または１つの空間次元と１つの時間次元で変化する）データ）、あるいは多次元／多スペクトルのデータがあろう。圧縮がうまくいけば、その符号語は、符号化前の入力シンボル（または輝度データ）のために必要とされたビット数より少ないビット数で表現される。ロスレス符号化法には、辞書符号化方式（例えば、Lempel-Ziv方式）、ランレングス符号化方式、計数符号化方式、エントロピー符号化方式がある。ロスレス画像圧縮の場合、圧縮の基礎となっているのは予測または文脈と符号化である。ファクシミリ圧縮用のＪＢＩＧ標準（ISO/IEC  11544)と、ＤＰＣＭ（差分パルス符号変調−連続階調画像用のＪＰＥＧ標準のオプション）は画像用のロスレス圧縮の例である。ロッシー圧縮では、入力シンボルまたは輝度データは、量子化された後に出力符号語へ変換される。量子化の目的とするところは、データの重要な特徴量を保存する一方で、重要でない特徴量を除去することである。ロッシー圧縮システムは、量子化に先立ち、エネルギー集中をするため変換を利用することが多い。ＪＰＥＧは画像データ用のロッシー符号化法の一例である。
【０００５】
画像信号処理における近年の開発は、効率的かつ高精度のデータ圧縮符号化方式を追求することに関心を集中してきた。様々な変換またはピラミッド信号処理の方式が提案されており、その中に多重解像度ピラミッド処理方式とウェーブレット・ピラミッド処理方式とがある。これら２方式はサブバンド処理方式及び階層処理方式とも呼ばれる。画像データのウェーブレット・ピラミッド処理方式は、例えばクァドレチャーミラーフィルタ（Quadrature  Mirror  filter；ＱＭＦ）を用いてオリジナル画像のサブバンド分割をする特殊な多重解像度ピラミッド処理方式である。なお、非ＱＭＦの他のウェーブレット方式もあることに注意されたい。ウェーブレット処理方式に関し、これ以上の情報を得るには、Antonini，M.，et  al.，"Image  Coding  Using  Wavelet  Transform"，IEEE  Transactions  on  Image  Processing，Vol.1，No.2，April  1992、及び、Shapiro，J.，"An  Embedded  Hierarchical  Image  Coder  Using  Zerotrees  of  Wavelet  Coefficients"，Proc．IEEE  Data  Compression  Conference，pgs.214-223,1993を参照されたい。
可逆変換に関する情報を得るには、Said，A.and  Pearlman，W.，"Reversible  Image  Compression  via  Multiresolution  Representation  and  Predictive  Coding"，Dept.of  Electrical，Computer  and  Systems  Engineering，Renssealaer  Polytechnic  Institute，Troy，NY  1993を参照されたい。
【０００６】
ウェーブレット係数を量子化すると良好な画像が得られる。これはウェーブレット・フィルタが重複フィルタであるからである。これに対し、ブロック・ベースの非重複変換の係数を量子化すると、境界部に不快な歪みが生じる欠点がある。
【０００７】
ＤＣＴのような従来のブロック・ベースの変換からブロック歪みを除去することは多くの理由で困難である。境界が全ての係数に影響を及ぼす。各変換係数が多くの空間領域位置に影響を及ぼす。変換領域での滑らかさのためには、多数の係数間に重複関係がなければならない。例えば、空間領域における全ての斜め線の類は、良好なＤＣＴ表現がない。変換領域での滑らかさの条件と量子化の条件とを両立させることは難しい。一般的に、画質向上処理（平滑化／リンギング抑制／エッジ強調）を空間領域で行ってから変換領域で、その画質向上を量子化誤差内に納めるように制限する、ということを繰り返して解を求める方法が用いられる。
【０００８】
画像においては、エッジが歪みの原因であることが多い。エッジ抽出は、当該技術分野において、エッジを識別して画像から除去する方法として周知である。エッジ検出にはガウシアン・エッジ抽出方法が長いあいだ利用されてきた。例えば、E．Marr  and  E．Hildreth，"Theory  of  Edged  Section，"Proc．R．SOC．London，Vol.207，pp.187-217，1980、V.T.  and  Thomaso  A．Poggio，"On  Edge  Detection，"IEEE  Trans．on  Pattern  Analysis  and  Machine  Intelligence，Vol.8，pp.147-63，1986、L.Basano，D.caprile，et.al.，"Edge-Detection  Schemes  Highly  Suitable  for  Hardware  Implementation，"J.Opt.Soc.Am.，Vol.5，pp.1170-1175，1998、及び、S.Mallate  and  S.Zhong，"Characterization  of  Signals  from  Multiscale  Edges，"IEEE  Trans.on  Pattern  Analysis  and  Machine  Intelligence，Vol.14，pp.710-732，1992を参照されたい。しかし、これらのエッジ検出方法が従来から存在していたにも拘わらず、近傍に歪みのないシャープなエッジを復元できるように、エッジ検出を改良したいという要望が常に存在している。
【０００９】
圧縮は、非常に時間がかかり、また膨大なメモリを必要とすることが多い。より高速に、かつ／又は可能ならばより少ないメモリで、圧縮を行うことができれば望ましいことである。品質を保証できない、圧縮率が十分に高くない、あるいはデータレートが制御可能でないという理由で、圧縮が全く利用されなかった応用分野もある。しかし、伝送及び／又は記憶すべき情報量を減らすために、圧縮を利用することが望ましい。
【００１０】
【発明が解決しようとする課題】
本発明の一般的な目的は、より優れたデータ圧縮／伸長システムを実現することにある。本発明のより具体的な目的は、画像のタイリングを行う場合のタイル境界歪みの減少などを達成することである。
【００１１】
【課題を解決するための手段】
本発明は、上記目的を達成するため、以下の方法、装置又は記録媒体を提供する。
【００１２】
（１）画像をタイル分割し、各タイル毎に独立にウェーブレット変換して得られたウェーブレット係数データを再構成するウェーブレット係数再構成処理方法であって、ａ）タイル境界によって影響を受けるＤＳ係数及びＤＤ係数をセーブするステップ、ｂ）前記ＳＤ係数の値を所定の重み係数を用いて計算して置き換えて、該ＳＤ係数を前記タイル境界をまたいで平滑になるように再構成するステップ、ｃ）逆垂直変換を各タイルに独立に適用するステップ、ｄ）前記逆垂直変換して得られるＤ係数の値を所定の重み係数を用いて計算して置き換えて、該Ｄ係数を前記タイル境界をまたいで平滑になるように再構成するステップ、及び、ｅ）逆水平変換を各タイルに独立に適用するステップからなることを特徴とするウェーブレット係数再構成処理方法。
【００１３】
（２）前記（１）において、各階層レベルのウェーブレット係数データに対して、前記ａ）からｅ）までのステップを繰り返すステップをさらに有するウェーブレット係数再構成処理方法。
【００１５】
（３）前記（１）において、前記ＳＤ係数及びＤ係数を実際の量子化係数と矛盾しないようにクリッピングするステップをさらに有するウェーブレット係数再構成処理方法。
【００１６】
（４）画像をタイル分割し、各タイル毎に独立にウェーブレット変換して得られたウェーブレット係数データを再構成するウェーブレット係数再構成処理装置であって、タイル境界によって影響を受けたＤＳ係数及びＤＤ係数をセーブする手段、前記ＳＤ係数の値を所定の重み係数を用いて計算して置き換えて、該ＳＤ係数を前記タイル境界をまたいで平滑になるように再構成する手段、逆垂直変換を各タイルに独立に適用する手段、前記逆垂直変換して得られるＤ係数の値を所定の重み係数を用いて計算して置き換えて、該Ｄ係数を前記タイル境界をまたいで平滑になるように再構成する手段、及び、逆水平変換を各タイルに独立に適用する手段からなることを特徴とするウェーブレット係数再構成処理装置。
【００１７】
（５）前記（４）において、前記のセーブする手段、ＳＤ係数を再構成する手段、逆垂直変換を適用する手段、Ｄ係数を再構成する手段、及び、逆水平変換を適用する手段が、各階層レベルのウェーブレット係数データに対して、前記独立に作用するウェーブレット係数再構成処理装置。
【００１９】
（６）前記（４）において、前記ＳＤ係数及びＤ係数を実際の量子化係数と矛盾しないようにクリッピングする手段をさらに有するウェーブレット係数再構成処理装置。
【００２０】
（７）画像をタイル分割し、各タイル毎に独立にウェーブレット変換して得られたウェーブレット係数データを再構成処理するためのプログラムが記録された記録媒体であって、タイル境界によって影響を受けたＤＳ係数及びＤＤ係数をセーブする処理、前記ＳＤ係数の値を所定の重み係数を用いて計算して置き換えて、該ＳＤ係数を前記境界をまたいで平滑になるように再構成する処理、逆垂直変換を各タイルに独立に適用する処理、前記逆垂直変換して得られるＤ係数の値を所定の重み係数を用いて計算して置き換えて、該Ｄ係数を前記タイル境界をまたいで平滑になるように再構成する処理、及び、逆水平変換を各タイルに独立に適用する処理をコンピュータに実行させるプログラムが記録されたことを特徴とするコンピュータ読み取り可能な記録媒体。
【００２１】
【発明の実施の形態】
以下、本発明の実施の形態について、添付図面を参照して説明する。以下の説明においてビット数、ビットレート、フィルタの種類等々、様々な具体例が示される。しかし、当業者には、そのような具体例によらずに本発明を実施し得ることは明白になろう。他方、本発明をいたずらに難解にしないため、周知の構造やびデバイスはブロック図として表し、詳しくは示さない。
【００２２】
以下の詳細説明には、コンピュータメモリ内のデータビットに対する演算のアルゴリズム及び記号表現によって表現された部分がある。このようなアルゴリズム記述及び表現は、データ処理技術分野の当業者によって、その研究の内容を他の当業者に対し最も効率的に伝えるために用いられる手段である。あるアルゴリズムがあり、それが概して期待した結果に至る自己矛盾のないステップ系列だと考えられるとする。これらのステップは、物理量を物理的に処理する必要があるものである。必ずという訳ではないが、これらの物理量は記憶、転送、結合、比較、その他の処理が可能な電気的または磁気的信号の形をとるのが普通である。これらの信号をビット、値、要素、記号、文字、用語、数値等で表わすと、主に慣用上の理由から、便利な場合があることが分かっている。
【００２３】
しかしながら、このような用語や同様の用語は、適切な物理量と関係付けられるべきであり、また、これら物理量につけた便宜上のラベルに過ぎないということに留意すべきである。以下の説明から明らかなように、特に断わらない限り、「処理」「演算」「計算」「判定」「表示」等々の用語を用いて論じることは、コンピュータシステムのレジスタ及びメモリの内部の物理的（電子的）な量として表現されたデータを処理して、コンピュータシステムのメモリまたはレジスタ、同様の情報記憶装置、情報伝送装置あるいは表示装置の内部の同様に物理量として表現された他のデータへ変換する、コンピュータシステムあるいは同様の電子演算装置の作用及びプロセスを指すものである。
【００２４】
本発明は、本明細書に述べる操作を実行するための装置にも関係するものである。この装置は、希望する目的に専用に作ってもよいし、あるいは、汎用コンピュータを内蔵プログラムにより選択的に駆動または再構成したものでもよい。そのようなプログラムは、コンピュータが読み取り可能などのような種類の記憶媒体に格納してもよい。例えば、これに限定されるものではないが、フロッピーディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスクなどの任意の種類のディスク、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード又は光カードなど、電子的命令の格納に適した、コンピュータのシステムバスに接続された任意種類の媒体でよい。本明細書に提示したアルゴリズム及び表示は、本質的に、いかなる特定のコンピュータ、その他の装置とも関わりがない。様々な汎用マシンを、本明細書に述べたところに従ったプログラムに利用してもよいが、必要な方法ステップの実行用に、より特化した装置を作るほうが好都合であるかもしれない。これら多様なマシンに要求される構造は以下の説明から明らかになろう。さらに、いかなる特定のプログラミング言語とも関連付けることなく本発明を説明する。本明細書における説明から理解されるように、本発明の内容を実装するのに様々なプログラミング言語を使用できる。
【００２５】
下記の用語が以下の説明に用いられる。これら各用語はすでに語義がある。しかし、ここに挙げた語義は、それら用語が当該分野において知られている語義の範囲に限定して考えられるべきでない。これら語義は、本発明の理解を容易にするために提示したものである。
【００２６】
桁揃え(alignment)：  ある周波数帯域内の変換係数の、他の周波数帯域に対するシフト度合。
【００２７】
算術符号化：  有限精度演算によるShannon/Elias符号化、バイナリ・エントロピー・コーダーに限らない。
【００２８】
Ｂ符号化：  圧縮に有限状態マシンを用いるバイナリ・エントロピー・コーダー。ハフマンn符号化と違い、有限状態マシンを用いることによりバイナリ・シンボルをうまく処理し、ある範囲の入力確率に対し有効である。
【００２９】
バイナリ・エントロピー・コーダー：  最高確率シンボル（ｍｐｓ）及び最低確率シンボル（ｌｐｓ）として表現されることの多いバイナリ(yes/no)デシジョンに基づいて動作するノイズレス・コーダー。
【００３０】
バイナリ方式：  画素のエッジ−フィル(edge-fill)グレイ符号化と特殊な文脈モデルを用いる符号化方式。
【００３１】
バイナリ方式文脈モデル：  ２値及び階調数の少ない画像データのための文脈モデル。
【００３２】
ビット・シグニフィカンス（bit-significance)：  符号（sign）絶対値表現に似た数表現で、ヘッド(head)ビットの後に符号(sign)ビットが続き、さらに、テール(tail)ビットがあれば、その後に続く。この数表現に対しビットプレーン順に埋め込み符号化が行われる。
【００３３】
子ベース(child-based)順：  ２次元画像のスキャン順。ラスタ順に似ているが、２×２ブロック単位でスキャンが進行する。「親」周波数帯域をラスタ順にスキャンすることを考える。各係数は４個の子を持っているであろう。これらの子は、左上のものから始めて右上、左下、右下と順序付けられ、その後に次の親と次の４つの子の組が続き、以下同様にラインの終わりまで続く。そして処理は次の２ラインに戻り、最終的に右下コーナーで終わる。どのラインもスキップされない。子ベース順は２×２ブロック順とも呼ばれる。
【００３４】
コードストリーム：  画像データのコード部分で、ヘッダ信号を含む。他の実施例では、ヘッダ信号は含めない。
【００３５】
係数：  変換後の成分。
【００３６】
成分：  画像の構成要素。成分によって画素を構成する。例えば、赤、緑、青の帯域は成分帯域である。個々の画素は赤、緑、青の成分から構成される。成分と成分帯域に、画像への空間写像を持つ任意の種類の情報を含めることができる。
【００３７】
文脈モデル：  符号化しようとするカレント・ビットに関し因果的に利用できる情報で、カレント・ビットに関する過去に学習した情報を提供してエントロピー符号化のための条件付確率予測を可能にする。
【００３８】
効率変換：  係数への最高のエネルギー集中を達成すると同時に最小のビット数を用いてそれら係数を表現する変換。
【００３９】
埋め込み文脈モデル：  重要度の高い値が保存されれば効率的なロッシー圧縮が得られるように、文脈ビンと結果を重要度レベルに分割する文脈モデル。
【００４０】
順序付け埋め込み：  埋め込み文脈モデルの特殊ケースであり、明示的な重要度のラベリングはなく、最も重要なデータが初めの部分にくるように圧縮データが順序付けされる。
【００４１】
埋め込み量子化：  コードストリームに包含された量子化。例えば、重要度レベルが最高レベルから最低レベルへと順に並べられているときには、コードストリームの単なる打ち切りによって量子化が行われる。タグ、マーカー、ポインタ、その他信号を使って同じ働きを得ることができる。復号化時には画像に対し様々な多重量子化を行うことができるが、符号化時にはただ一つの埋め込み量子化しか行うことができない。
【００４２】
エントロピー・コーダー：  確率予測値に基づいてカレント・ビットを符号化又は復号化する装置。本明細書では、エントロピー・コーダーは多重文脈バイナリ・コーダーとも呼ばれることがある。カレント・ビットの文脈は、何らかの選ばれた配置の「近傍」ビットであり、カレント・ビット１ビットまたは複数ビット）の最適表現のための確率予測を可能にする。一実施例では、エントロピー・コーダーはバイナリ・コーダー、並列ランレングス・コーダー、又はハフマン・コーダーである。
【００４３】
エントリー・ポイント：  ある既知の符号化状態から始まる符号化データ中のポイント。復号化器は、このポイントから、その前データを復号化することなく復号化を開始できる。これには、大抵の場合、文脈とバイナリ・エントロピー・コーダーを所期状態にリセットする必要がある。各符号化単位の符号化データはエントリー・ポイントから始まる。
【００４４】
固定長：  データの特定ブロックを、圧縮データの特定ブロックへ変換する方式。例えば、ＢＴＣ（ブロック・トランケーション符号化）と、ＶＱ（ベクトル量子化）のいくつかの方式。固定長コードは、固定レート・固定サイズのアプリケーションに適するが、レート・歪み性能は可変レート方式に比べ劣ることが多い。
【００４５】
固定レート：  ある一定の画素レートを維持し、帯域幅の限定された通信路を持つアプリケーション又は方式。一実施例においては、この目標を達成するため、全体的に平均した圧縮ではなく、局所的に平均した圧縮がなされる。例えば、ＭＰＥＧは固定レートを必要とする。
【００４６】
固定サイズ：  限定サイズのバッファを持つアプリケーション又は方式。一実施例では、この目標を達成するため全体的に平均した圧縮がなされる。例えば、プリント・バッファ。（アプリケーションは、固定レートのことも、固定サイズのことも、その両方のこともある。）
周波数帯域：  各周波数帯域は、同じフィルタ処理系列により得られる一群の係数のことである。
【００４７】
ヘッド・ビット：  ビット・シグニフィカンス表現において、ヘッド・ビットとは、最上位ビットから最初の非０ビットまでの、該非０ビットを含めた絶対値ビットのことである。
【００４８】
ハフマン・コーダー：  一般に、各シンボルに対して整数個のビットを発生する固定長コーダー。
【００４９】
ベキ等：  画像をロッシー形式で伸長してから同じロッシー・コードストリームへ再圧縮することを可能にする符号化。
【００５０】
画像タイル：  それぞれが同一のパラメータを持つ、オーバーラップのない連続した部分画像の格子を定義可能にするため選ばれた矩形領域。一実施例では、符号化操作で１つの画像タイル中の画素及び係数データだけを処理する。このように制限することで、ランダム・アクセスと注目領域の伸長が可能になる。一実施例では、画像タイルは、恐らく最上部と最下部のもの以外は、全て同一サイズである。一実施例では、画像タイルは、画像全体の大きさままでの任意のサイズにすることができる。
【００５１】
重要度レベル：  符号化単位で、圧縮される前は、埋め込みデータの１つのビットプレーン全体に対応する。重要度レベルは、様々な係数周波数帯域の適切なビットプレーンを全て含む。
【００５２】
ＬＰＳ（最低確率シンボル）：  バイナリ・デシジョンにおいて確率が５０％未満の事象（outcome）。２つの事象が等確率の時にどちらがｍｐｓ又はｌｐｓに選ばれるかは、符号化器と復号化器が同じ選定をするならば重要なことではない。
【００５３】
ロスレス／ノイズレス／可逆符号化：  原データの完全な再構成を可能にする方法によるデータ圧縮。
【００５４】
ロッシー符号化：  原データの完全な再構成を保証しないデータの符号化。視覚的に不快であったり目立ったりしないように、原データから変化してもよい。多くの場合、固定レートが可能である。
【００５５】
ＭＰＳ（最高確率シンボル）：  ２値判定において確率が５０％を超える事象。
重複変換：  単一の源標本点が同じ周波数の複数の係数に寄与する変換。その例として、多くのウェーブレット及び重複直交変換がある。
【００５６】
親係数：  カレント係数又はカレント画素と同じ画像空間をカバーする、すぐ上の階層レベルの係数又は画素。例えば図１において、１ＳＤ係数の親は２ＳＤ係数であり、この２ＳＤ係数は３ＳＤ係数の親である。
【００５７】
確率予測マシン／モジュール：  文脈内での確率を追跡する、符号化システムの要素。
【００５８】
プログレッシブ画素深さ：  データのビットプレーンを浅いほうからフル画像解像度まで順序付けたコードストリーム。
【００５９】
プログレッシブ・ピラミッド：  解像度が下がる毎に各次元が２分の１（面積では４分の１）になる解像度成分の系列。
【００６０】
階層レベル：  ウェーブレット分解ピラミッドにおける位置。階層レベルは解像度と直接関係する。
【００６１】
Ｑコーダー：  乗算が加算によって置き換えられ、確率が離散値に限定され、確率予測値がビット出力時に更新されるバイナリ算術コーダー。
【００６２】
量子化：  データ又は情報を選択的に削除する、つまり利用しない。量子化すれば必然的に不完全（ロッシー）再構成となる。しかし、巧妙な量子化によれば、決まったデータ量で良好な品質を得ることができる。
【００６３】
ラスター順：  ２次元画像のスキャン順の一つ。左上コーナーからスタートして左から右へ移動し、それから次ラインの左端に戻り、最終的に右下コーナーで終了する。どのラインもスキップされない。
【００６４】
可逆変換：  一実施例では、圧縮結果を原データに復元可能な、整数演算により実現される効率変換。
【００６５】
タグ：  コードストリームの非符号化部分で、符号化特性及びコードストリームの区間に関する情報を知らせる。一実施例では、タグは、その役割を知らせるための識別番号を持っている。
【００６６】
テール・ビット（又はテール）：  ビット・シグニフィカンス表現で、テール・ビットとは、最も上位の非０ビットより下位の絶対値ビットである。
タイル・データ・セグメント：  １つの符号化単位を完全に記述する、コードストリームの部分。
【００６７】
変換方式：  ウェーブレット変換をエネルギー集中に利用する符号化方式。
【００６８】
ＴＳ変換：  ２・６（Two-Six）変換。２タップのローパス分析フィルタと６タップのハイパス分析フィルタを用いる特殊な可逆ウェーブレットフィルタ対。その合成フィルタは、分析フィルタのクァドレチャー・ミラー・フィルタである。
【００６９】
ＴＴ変換：  ２・１０（Two-Ten）変換。２タップのローパス分析フィルタと１０タップのハイパス分析フィルタを用いる特殊な可逆ウェーブレットフィルタ対。その合成フィルタは、分析フィルタのクァドレチャー・ミラー・フィルタである。
【００７０】
統合型ロスレス／ロッシー：  同じ圧縮システムで、ロスレス再構成又はロッシー再構成が可能なコードストリームを提供する。本発明の一実施例では、このコードストリームは符号化器に対する設定情報も指令もなくてよい。
【００７１】
ウェーブレット・フィルタ：  ウェーブレット変換に用いられるハイパスとローパスの合成フィルタ及び分析フィルタ。
【００７２】
ウェーブレット変換：  「周波数」領域と「時間（又は空間）」領域の両方の拘束条件を用いる変換。一実施例では、ハイパスフィルタとローパスフィルタからなる変換である。得られた係数は１／２に間引かれ（臨界フィルタ処理）、そして、そのローパス係数にそれらフィルタが適用される。
【００７３】
ウェーブレット木：  最高レベルのウェーブレット分解のＳＳ部内の単一の係数に関係がある係数及び画素。係数の個数はレベル数の関数である。図１は、ウェーブレット木に含まれる係数を説明している。ウェーブレット木のスパンは、分解レベル数に依存する。例えば、ウェーブレット木のスパンは、１レベル分解では４画素、２レベル分解では１６画素、等々である。下記の表１は、１つのウェーブレット木が影響を及ぼす画素の個数を、様々なレベル数の場合について示している。２次元の場合、各ウェーブレット木はＳＤ，ＤＤ，ＤＳと呼ばれる３つの部分木からなる。
【００７４】
【表１】
0003653183.tif 000002
【００７５】
〈システムの概要〉
本発明の実施形態は、符号化部及び復号化部を持つ圧縮／伸長システムを提供する。符号化部は入力データを符号化して圧縮データを生成する働きをし、他方、復号化部は符号化データを復号化して元の入力データの再構成データを生成する働きをする。入力データは様々な種類のデータで、例えば、画像（静止画像あるいは動画像）、音声等々である。一実施例では、データはデジタル信号データであるが、デジタル化したアナログデータ、テキストデータ形式、その他の形式も可能である。そのデータのソースは、例えば符号化部及び／又は復号化部のためのメモリ又は通信路である。
【００７６】
実施形態において、符号化部及び／または復号化部の構成要素は、ハードウェアによって実現されてもよいし、あるいはコンピュータシステム上で利用されるようなソフトウェアによって実現されてもよい。本発明は、ロスレス圧縮／伸長システムを提供する。本発明は、ロッシー圧縮／伸長を実行するようにも構成できる。本発明は、伸長を行うことなく圧縮データの構文解析を実行するように構成できる。
【００７７】
実施形態は、自然画像に見られる滑らかなエッジと平坦な領域を非常に良好に表現する。本発明は、可逆埋め込みウェーブレットを利用して、深い画素の画像を圧縮する。しかしながら、可逆埋め込みウェーブレット、他のウェーブレット変換方式及びシヌソイド変換方式は、テキストやグラフィック画像に見られるシャープなエッジを表現することは得意ではない。この種の画像は、ＪＢＩＧのように、グレイ符号化に続いて文脈ベースのビットプレーン符号化を行う方法で良好に圧縮できる。さらに、ノイズのないコンピュータ生成画像は、バイナリ方式により良好にモデル化される。
【００７８】
実施形態は、２値画像及びグラフィック画像の圧縮のためのバイナリ方式を提供する。このバイナリ方式は、ダイナミックレンジ全体を利用しない、ある種の画像に対する圧縮も改善する。このバイナリ方式においては、ウェーブレット変換を利用しないで画像のビットプレーンを符号化する。
【００７９】
図２は、バイナリ方式を利用する実施形態の圧縮システムの一実施例のブロック図である。なお、システムの復号化部は逆の順序で動作し、データフローも同様であることに注意されたい。図２において、画像データ２０１が多成分処理機構２１１に入力する。この多成分処理機構２１１は、オプションの色空間変換、及び、サブサンプリング後の画像成分に関するオプション処理が可能である。方式選択機構２１０は、画像が連続階調画像か２値画像か、あるいは、画像のどの部分がそのような特性を持っているか判定する。画像データは方式選択機構２１０へ送られ、方式選択機構１１０は、その画像データ又はその部分をウェーブレット方式処理部（ブロック２０２，２０３，２０５）又はバイナリ方式符号化ブロック２０４へ送る。どちらのモードを利用すべきかは、データに依存して決定される。一実施例では、方式選択機構２１０はマルチプレクサからなる。方式選択機構２１０は、復号化動作中は利用されない。
【００８０】
ウェーブレット方式の場合、可逆ウェーブレット変換ブロック２０２が可逆ウェーブレット変換を実行する。同ブロック２０２の出力は係数の系列である。埋め込み順序量子化ブロック２０３は、（可逆ウェーブレット変換ブロック２０２により生成された）入力画像データ２０１中の係数全部の桁揃えを生成するため、係数をビット・シグニフィカンス表現にしてからラベル付けする。
【００８１】
画像データ２０１が受け取られ、そして（適切な多成分処理の後）ウェーブレット変換ブロック２０２において、後に説明されるように、可逆ウェーブレットを利用して変換されることにより、画像の多重解像度分解を表す係数系列が生成される。可逆ウェーブレット変換は、計算が複雑でない。この変換は、ソフトウェア又はハードウェアにより、全く系統誤差を生じさせないで実行できる。さらに、ウェーブレットはエネルギー集中及び圧縮性能が優れている。これらの係数は埋め込み順序量子化ブロック２０３に受け取られる。
【００８２】
埋め込み順序量子化ブロック１０３は、後述のように、埋め込み順序量子化を行う。その結果は埋め込みデータストリームである。この埋め込みデータストリームは、符号化時、伝送時又は復号化時に量子化可能である。一実施例においては、埋め込み順序量子化ブロック２０３は、係数を順序付けして符号・絶対値形式に変換する。
【００８３】
埋め込みデータストリームは文脈モデル２０５に受け取られる。この文脈モデル２０５は、埋め込みデータストリーム中のデータを、その重要度に基づいてモデル化する（後述）。変換モードの場合、”ビットプレーン”が変換係数の重要度レベル・プレーンであり、文脈モデル２０５はウェーブレット係数をビット・シグニフィカンス表現に変換する。
【００８４】
順序付けとモデル化の結果が、エントロピー・コーダー２０６で符号化すべきデシジョン（又はシンボル）を構成する。一実施例では、全てのデシジョンが１つのコーダーへ送られる。他の実施例では、デシジョンは重要度によってラベル付けされ、各重要度レベル毎に複数の別々の（物理または仮想）コーダーによって処理される。ビットストリームは、エントロピー・コーダー２０６により、重要度の順に符号化される。一実施例では、エントロピー・コーダー２０６は、１つ又はそれ以上のバイナリ・エントロピー・コーダーからなる。別の実施例では、ハフマン符号化が利用される。
【００８５】
バイナリ方式では、バイナリ方式符号化ブロック２０４が入力画像２０１の画素に対するグレイ符号化を実行する。グレイ符号化は画素のビットプレーン間の相関の一部を利用するビット操作である。その理由は、任意の値ｘとｘ＋１に関し、gray(x)とgray(x+1)が、その基数２の表現において１ビットしか相異しないからである。一実施例では、バイナリ方式符号化ブロック２０４は８ビット画素に対し点単位変換、すなわち
gray(x)＝x  XOR  x/2
を実行する。実施形態は、この形式のグレイ符号化を利用することに限定されるわけでも、８ビット・サイズの画素を利用しなければならないわけでもない。しかし、上記式を利用すると、ビットプレーン単位のプログレッシブ伝送の場合のように、利用可能な最上位ビットの一部だけで画素を再構成できるという利点がある。言い換えると、この形式のグレイ符号化はビット・シグニフィカンスの順序付けを保存する。
【００８６】
バイナリ方式では、バイナリ方式符号化ブロック２０４及びエントロピー・コーダー２０６を利用し、データがビットプレーン単位で符号化される。一実施例では、バイナリ方式符号化ブロック２０４内の文脈モデルは、カレント・ビットを、位置と重要度レベルの情報を利用して条件付けする。
【００８７】
バイナリ方式の場合、グレイ符号化画素に対しＪＢＩＧのような文脈モデルが利用される。一実施例においては、画像タイルの各ビットプレーンは別々に符号化され、その際、個々のビットはそれぞれ周辺の１０画素の値を利用してラスター順に条件付けされ、符号化される。図３は、バイナリ方式における各ビットプレーンの各ビットのための文脈モデルの幾何学的関係を示す。これらの条件付けビットは、個別パターン毎の適応的確率予測に役立つ。なお、バイナリ・エントロピー・コーダーがグレイ符号化値のビットプレーン・エントロピー符号化に利用されるときには、少し異なったテンプレートをバイナリ・エントロピー・コーダーの文脈モデルとして用いてもよい。図４は、２の９乗個の文脈ビンのための７画素と２ビットのビットプレーン情報を示す。
【００８８】
この文脈とカレント・ビットの値を利用して、（バイナリ）エントロピー・コーダー２０６はビットストリームを生成する。この同じ（バイナリ）エントロピー・コーダー２０６が、変換モードとバイナリ方式の両方からのデータの符号化に利用される。一実施例では、（バイナリ）エントロピー・コーダー２０６は、ルックアップ・テーブルを用いて実現される有限状態マシンからなる。なお、本発明は、Ｑコーダー、ＱＭコーダー、高速並列コーダーなど、どのようなバイナリ・エントロピー・コーダーにも利用できる。
【００８９】
（バイナリ）エントロピー・コーダー２０６はいずれの方式の場合も同じものであり、かつ、グレイ符号化とバイナリ方式文脈モデルは単純であるため、同一システムでバイナリ方式と変換方式を実現するのに、ごく僅かな追加資源しか必要とされない。また、文脈モデルの構成は異なるといっても、両モードに必要な資源は同じである。すなわち、両方のモードで、文脈の格納に同じメモリを利用し、また、同じ（バイナリ）エントロピー・コーダーを利用する。
【００９０】
本実施形態は、画像全体に対し実行されてもよいし、より普通には、画像のタイル化セグメントに対し実行されてもよい。変換方式による方が圧縮の良好なタイルも、バイナリ方式による方が良好なタイルもある。どちらのモードを使用すべきか選択するために利用できるアルゴリズムはいくらでもある。タイルが利用されるときには、タイル単位のランダムアクセスが可能である。また、重要な領域を別個に、より高精度に復号化してもよい。最後に、変換方式とバイナリ方式のどちらを利用するかの選択は、個々のタイル毎に決定してよい。
【００９１】
また、デュアルモード・システムを利用しても、画像はビットプレーン単位でプログレッシブであり、ＪＢＩＧの教える階層形式に符号化できる。
【００９２】
復号化に関しては、タイルのヘッダ中の１ビットを、データの符号化に利用された方式を指定するために利用してよい。方式選択機構２１０は利用されない。例えばヒストグラム圧縮（後述）により、元のダイナミックレンジから低いダイナミックレンジへのロスレス変換が可能であれば、さらに役に立つことがある。ＪＢＩＧにおけるようなルックアヘッド（look  ahead）を利用してもよい。このルックアヘッドには、ＪＢＩＧにおけるような一般的な予測又は決定論的予測を使用してよい。
【００９３】
〈バイナリ方式と変換方式の選択〉
方式選択機構２１０は、バイナリ方式と変換方式の選択を行う。一実施例では、入力画像は両方の方式で符号化され、方式選択機構２１０は得られたビットレートが低い方の方式を選択する（ロスレス圧縮を想定した場合）。つまり、よく圧縮する方のモードが選ばれる。このような方法は、コストが高いと思われるかもしれないが、それほどではない。というのは、バイナリ方式と変換方式は共に、ソフトウェアが比較的高速であり、かつ、ハードウェアも小規模であるからである。この方法から派生する方法の一つは、コーダーをバイパスし、エントロピー値を用いてビットレートの低い方を判定する方法である。
【００９４】
別の実施例においては、画像の画素値の完全な（又は部分的な）ヒストグラム、又は、隣接画素値のペア間の差分のヒストグラムを生成する。画素値のヒストグラムの場合、当該データの統計的解析を行い、例えば、そのヒストグラムのピークが、画素深さのダイナミックレンジより遥かに小さな、いくつかの値で生じたならば、バイナリ方式を選ぶ。
【００９５】
一実施例では、隣接画素のペア間の第１次差分の完全な（又は部分的な）ヒストグラムを生成する。標準的な画像では、そのようなヒストグラムは正にラプラシアン分布であり、ウェーブレット方式が利用されることになろう。しかし、このヒストグラムがラプラシアン分布のピークを持たないときには、バイナリ方式が利用される。
【００９６】
両方の種類のヒストグラムを生成し、一緒に方式選択に利用してもよい。
【００９７】
ＴＳ変換又はＴＴ変換のｄnフィルタ出力は、それぞれ後述するが、第１次統計量に近い。これは、変換が実行されヒストグラムが生成される方法を暗示している。ヒストグラムに基づいて方式が選択される。選択された方式が変換方式ならば、システムは既に生成されている変換係数を処理する。バイナリ方式が選択されたときには、変換係数は捨てられ（あるいは、画素がセーブされたか否かによっては逆変換される）、システムはバイナリ方式を開始する。
【００９８】
別の実施例では、どちらの方式を選択すべきかの決定を補助するため、領域分割及び／又は文書の種類に関する以前の知識が利用されるかもしれない。
【００９９】
実施例によっては、タイルのサイズは２方式の利点を最大限に発揮させるように選ばれる。
【０１００】
なお、一実施例においては、システムはバイナリ方式符号化を含まず、したがって、可逆埋め込みウェーブレット圧縮（ＣＲＥＷ）及び伸長だけを利用する。
【０１０１】
また、実施形態は伸長システムを提供する。伸長システムは、ロスレス、ロッシーのいずれにしても、圧縮システムで実行される処理と逆の処理をする構成要素からなる。難解にしないため、伸長システムについては、圧縮システムと相異する点についてのみ説明する（データの流れは単に逆向きになるだけである）。
【０１０２】
〈コードストリーム〉
実施形態の画像圧縮システムにおいては、デジタル画像はタイルと呼ぶ矩形領域に分割され、タイルは独立に符号化される。さらに、デジタル画像は複数の成分から構成され、各成分は１つ又は複数の画素の異なった特質を表す。（最も一般的な例は色成分であり、各色成分は赤、緑、青などの特定の色の量を表す。）これらの画像成分も独立に符号化される。
【０１０３】
画像タイルは、全体画像の完全な独立に符号化された部分画像であり、画像上に配置された規則的な矩形格子により定義され、図５に示すようにラスター順に番号が付けられる。右端と下端にあるタイルは、原画像及びタイルのサイズによって様々なサイズになる。（これらの半端なサイズのタイルについて、余分な符号化が必要となることはない。）タイルのサイズは、符号化の段階でユーザが決めることができ、画像サイズ以下の任意の高さ及び幅にすることができる。
【０１０４】
タイル・サイズの選び方は、性能を大きく左右する。タイルが小さいと、特にラスター順画像の垂直方向の寸法が小さいと、より小さな作業域用メモリを利用できる。しかし、タイルが小さすぎると、３つの要因、すなわち、信号のためのオーバーヘッド、タイル境界での符号化効率の悪化、エントロピー・コーダーの立ち上がり適応により、圧縮効率が下がる。タイルの寸法を、最も低い周波数成分の大きさの倍数（ＣＲＥＷツリー）、つまりレベル数の関数（２のレベル数乗）にするのが有利である。原画像のサイズによるが、１２８×１２８又は２５６×２５６のタイルが多くのアプリケーションに適当と思われる。
【０１０５】
タイルの定義やシンタックスには、画像シーケンスの圧縮を妨げるものは何もない。したがって、タイル化された画像は、（映画のような）時間的に変化する画像や（ＭＲＩの如き３Ｄ断面図のような）空間的に変化する画像であってもよいだろう。
【０１０６】
各タイルは１つ又はそれ以上の成分からなる。各成分はタイル全体に及ぶが、各成分の解像度が異なってもよい。一実施例では、どのタイルも各成分からの少なくとも１つのサンプルを有する。これらの成分は、画素深さが異なってもよく、また、異なった方式で符号化されてもよい。各成分は独立に符号化されるが、符号化データは重要度レベルを基準としてインターリーブされてもよい。
【０１０７】
〈ヘッダ及びタグ〉
実施形態は、コードストリームの区切りと特性の通知のためタグを利用する。コードストリームは全て、少なくとも２つのヘッダを持つ。すなわち、画像の初めにあるメイン・ヘッダと、各タイルの初めにあるタイル・ヘッダの２つである（すべてのコードストリームは少なくとも１つのタイルを含む）。
【０１０８】
一実施例にあっては、５種類のタグ、すなわち、区切りタグ、固定情報タグ、機能タグ、ポインタ・タグ、情報タグが用いられる。区切りタグは、ヘッダ及びデータの区切りのために用いられる。固定情報タグは、画像に関する必要情報を記述する。機能タグはタイル又は画像の全体の符号化に使われた符号化機能を記述する。ポインタ・タグは、タイルにおける重要度レベル（又は、その次のタイル）を指示する。情報タグは、データに関するオプションの情報を与える。
【０１０９】
〈ポインタ・タグ〉
ポインタ・タグは、長さ又はコードストリームへのポインタを提供する。ポインタ・タグは、メイン・ヘッダ中に出現し、又は、タイル・ヘッダの全てに出現する。後述するＩＥＭタグ又はＩＥＴタグは、コードストリーム中にエントリー・ポイントがあるか、複数の成分があるときに使用される。（エントリー・ポイントは、符号化される成分が変わる時に必ず必要とされる。複数成分タイルの最初の成分が成分０であるときには、エントリーポイントが必要になる。）ＩＬＭタグとＩＴＬタグは、オプションであり、一つの重要度レベルにおける符号化データの始まりを指示する。
【０１１０】
これらタグのどれかがメイン・ヘッダ中にあれば、このメイン・ヘッダ中に、これらタグが全てあるということを意味する。これらのタグのどれもメイン・ヘッダにない時には、それらタグは全てタイル・ヘッダにあるであろう。ポインタ・タグを全てメイン・ヘッダに出現させる利点は、復号化器又はパーサーが、後戻りすることなく、コードストリームを選択し、かつ／又は量子化することができることである。このようなことが可能であると、復号化器及び／又はパーサーが高速でなければならない、あるいは、その個数を限定しなければならないアプリケーションにとっては有利であろう。符号化器がメイン・ヘッダまで後戻りできない場合、ポインタ・タグをタイル・ヘッダに配置することができる。このような配置は、非常に大きな画像を符号化する場合や、コードストリームの後戻りや蓄積が困難なハードウェアの符号化器を使用する有利である。
【０１１１】
〈重要度レベル・エントリーポイント、メイン・ヘッダ（ＩＥＭ）〉
ＩＥＭタグは、所定の成分のための、全タイル中の全エントリー・ポイントを指し示すポインタのリストからなる。１つの成分に対し１つのＩＥＭタグがある。エントリー・ポイントは、重要度レベルの先頭の８ビット境界にある。エントリー・ポイントを有する重要度レベルは符号化時に選ばれる。しかし、データストリーム中の成分が変わる度に、エントリー・ポイントが必要になる。また、最初の成分が０番成分でなければ、ポインタ値が０のＩＥＭポインタのエントリーが必要とされる。各エントリー・ポイントで、エントロピー・コーダーはリセットされる。よって、これらのエントリー・ポイントは、復号化器によって取り扱われる。
【０１１２】
全てのＩＥＭポインタのエントリーは正しくなければならないが、重複したエントリー（コピー）があってもよい。それらエントリーは、ポインタ長の小さい方から順に格納されなければならない。なお、成分は重要度レベル単位でインターリーブできるから、異なった成分に対するＩＥＭタグをインターリーブしてよいであろう。
【０１１３】
一実施例においては、タイル中にエントリー・ポイントがある場合、ＩＥＴタグ（後述）がどのタイル・ヘッダにも使用されなければ、ＩＥＭタグがメイン・ヘッダに使用される。ＩＥＭタグは１成分あたり１回だけ出現する。ただし、恐らく成分０については例外である。成分０に対するエントリー・ポイントだけがＰiem＝０ならば、成分０についてはタグは不要である。
【０１１４】
ＩＥＭタグの長さは、画像中のタイル数と各タイル中のエントリー・ポイントの個数に応じて変化する。
【０１１５】
図６はＩＥＭタグに関する重要度レベル・エントリー・ポイント、メイン・ヘッダのシンタックスを示し、以下に説明するフィールドからなる。
【０１１６】
ＩＥＭ：  マーカー。
【０１１７】
Ｌiem：  マーカーを含めない、タグの長さ（バイト数）。
【０１１８】
Ｃiem：  当該タグが適用される成分。成分は０，１，２，．．．と番号が付けられる。
【０１１９】
Ｎiemi：  第ｉ番目のタイル中のエントリー・ポイントの個数。画像中の各タイル毎に１つのＮiemがある。エントリー・ポイントが存在しないタイルに対しても、１つのＮiemがある。
【０１２０】
Ｉiemij：  Ｃiem成分についての、第ｉ番目のタイル中の第ｊ番目のエントリー・ポイントから始まる重要度レベルの番号。このＩiemタグと、対応したＰiemタグとで１種のレコードを構成し、このレコードは各エントリー・ポイント毎に繰り返し現れる。これらのレコードは、エントリー・ポイントを有する重要度レベルで最も高いレベルから最も低いレベルへと向かう順序でなければならない。
【０１２１】
Ｐiemij：  タイル・ヘッダの終わり、又はタイル中の全符号化データの先頭から、第ｊ番目のエントリー・ポイントのバイトまでのバイト数。これらのレコードは、最小のポインタから最大のポインタへと向かう順序でなければならない。
【０１２２】
res：  必要に応じて最後に置かれる、０からなるフィラー・バイト。
【０１２３】
〈重要度レベル・エントリー・ポイント、タイル・ヘッダー（ＩＥＴ）〉
ＩＥＴタグは、所定の成分についての、タイル中の全エントリー・ポイントを指し示すポインタのリストである。個々の成分に対し１つのＩＥＴタグがある。これらのエントリー・ポイントは、重要度レベルの先頭の８ビット境界にある。エントリー・ポイントを有する重要度レベルは符号化器によって選ばれる。しかし、データストリーム中の成分が変わる度に、エントリー・ポイントが必要になる。また、最初の成分が０番成分でなければ、ポインタ値が０のエントリー・ポイントが必要とされる。各エントリー・ポイントで、エントロピー・コーダーは既知の状態にリセットされる。よって、これらのエントリー・ポイントは復号化器で処理されなければならない。
【０１２４】
全てのＩＥＴポインタのエントリーは正しいが、重複したエントリー（コピー）があってもよい。それらエントリーは、ポインタ長の小さい方から大きいへと順に格納されなければならない。なお、成分は重要度レベル単位でインターリーブできるから、異なった成分に対するＩＥＴタグをインターリーブしてもよいであろう。
【０１２５】
ＩＥＭタグがメイン・ヘッダ中に使用されないときには、エントリー・ポイントを有するタイルの全てのタイル・ヘッダにＩＥＴタグが使用される。また、恐らく成分０を除き、１成分につきＩＥＴタグが１回だけ出現する。成分０に対するエントリー・ポイントだけがＰiem＝０ならば、成分０についてはタグが不要である。
【０１２６】
ＩＥＴタグの長さは、各タイル中のエントリー・ポイントの個数に応じて変化する。
【０１２７】
図７はＩＥＴタグに関する重要度レベル・エントリー・ポイント、メイン・ヘッダのシンタックスを示し、以下のフィールドからなる。
【０１２８】
ＩＥＴ：  マーカー。
【０１２９】
Ｌiet：  マーカーを含めない、タグの長さ（バイト数）。
【０１３０】
Ｃiet：  当該タグが適用される成分。成分は０，１，２，．．．と番号が付けられる。
【０１３１】
Ｉieti：  Ｃiet成分についての、第ｉ番目のエントリー・ポイントから始まる重要度レベルの番号。このＩietタグと、対応したＰietタグとで、１種のレコードを構成し、このレコードは各エントリー・ポイント毎に繰り返し現れる。これらのレコードは、エントリー・ポイントを有する重要度レベルで最も高いレベルから最も低いレベルへと向かう順序である。
【０１３２】
Ｐieti：  タイル・ヘッダの終わり、又はタイル中の全符号化データの先頭から、第ｉ番目のエントリー・ポイントのバイトまでのバイト数。これらのレコードは、最小のポインタから最大のポインタへと向かう順序でなければならない。
【０１３３】
res：  最後に置かれる、０からなるフィラー・バイト。
【０１３４】
〈重要度レベル・ロケーター、メイン・ヘッダー（ＩＬＭ）〉
ＩＬＭタグは、所定の成分についての、全てのタイルにおいて符号化器が選択した重要度レベルを指示するポインタのリストである。これらの重要度レベルは、８ビット境界に必ずしも見つからない。これらのポインタが、探索対象の重要度レベルのデータを含む（かつ、前の重要度レベルからのデータを含まない）最初のバイトを指し示すのが、最も望ましいことである。しかし、これらのポインタが、当該重要度レベルのデータを含む、どのようなデータ・バイトを指し示してもよい。
【０１３５】
全てのＩＬＭポインタのエントリーは正しいが、重複したエントリー（コピー）があってもよい。それらエントリーは、ポインタ長の小さい方から大きいへと順に格納される。なお、成分は重要度レベル単位でインターリーブできるから、異なった成分に対するＩＬＭタグをインターリーブしてもよいであろう。
【０１３６】
ＩＬＭタグはメイン・ヘッダーにおけるオプションのタグであるが、タイル・ヘッダー中にポインタ・タグがあるときにはＩＬＭタグを使用してはいけない。メイン・ヘッダーには、１成分につき１個以下のＩＬＭタグがある。
【０１３７】
ＩＬＭタグの長さは、画像中のタイルの個数及び各タイル中のロケーター・ポイントの個数に応じて変化する。
【０１３８】
図８はＩＬＭタグに関する重要度レベル・ロケーター、メイン・ヘッダーのシンタックスを示し、以下のフィールドからなる。
【０１３９】
ＩＬＭ：  マーカー。
【０１４０】
Ｌilm：  マーカーを含めない、タグの長さ（バイト数）。
【０１４１】
Ｃilm：  当該タグが適用される成分。
【０１４２】
Ｎilmi：  第ｉ番目のタイル中のロケーターの個数。画像中の各タイルに対し、タイル中にロケーターが存在しない場合でも、Ｎilmは存在する。
【０１４３】
Ｉilmij：  Ｃilm成分についての、第ｉ番目のタイルから始まる第ｊ番目の重要度レベルの番号。このＩilmタグと、対応したＰilmタグとで、１種のレコードを構成し、このレコードは各ロケーター毎に繰り返し現れる。これらのレコードは、最も高い重要度レベルから最も低い重要度レベルへと向かう順序でなければならない。
【０１４４】
Ｐilmij：  タイル・ヘッダの終わり、又はタイル中の全符号化データの先頭から、第ｊ番目の重要度レベルのデータを含むデータ・バイトまでのバイト数。これらのレコードは、最小のポインタから最大のポインタへと向かう順序である。
【０１４５】
res：  必要に応じて最後に置かれる、０からなるフィラー・バイト。
【０１４６】
〈重要度レベル・ロケーター、タイル・ヘッダ（ＩＬＴ）〉
ＩＬＴタグは、所定の成分についての、全てのタイルにおいて符号化器が選択した重要度レベルを指示するポインタのリストである。これらの重要度レベルは、８ビット境界に必ずしも見つからない。これらのポインタが、探索対象の重要度レベルのデータを含む（かつ、前の重要度レベルからのデータを含まない）最初のバイトを指し示すのが、最も望ましいことである。しかし、これらのポインタが、当該重要度レベルのデータを含む、どのようなデータ・バイトを指し示してもよい。
【０１４７】
全てのＩＬＴポインタのエントリーは正しいが、重複したエントリー（コピー）があってもよい。それらエントリーは、ポインタ長の小さい方から大きいへと順に格納される。なお、成分は重要度レベル単位でインターリーブできるから、異なった成分に対するＩＬＴタグをインターリーブしてもよいであろう。
【０１４８】
ＩＬＴタグは、１成分につき１個までタイル・ヘッダにあるが、メイン・ヘッダにポインタ・タグがあるときには使用してはいけない。ＩＬＴタグの長さは、各タイル中のロケーター・ポイントの個数に応じて変化する。
【０１４９】
図９はＩＬＴタグに関する重要度レベル・ロケーター、タイル・ヘッダのシンタックスを示し、以下のフィールドからなる。
【０１５０】
ＩＬＴ：  マーカー。
【０１５１】
Ｌilt：  マーカーを含めない、タグの長さ（バイト数）。
【０１５２】
Ｃilt：  当該タグが適用される成分。成分は０，１，２，．．．と番号が付けられる。
【０１５３】
Ｉilti：  Ｃilt成分についての、第ｉ番目のエントリー・ポイントから始まる重要度レベルの番号。このＩiltタグと、対応したＰiltタグとで、１種のレコードを構成し、このレコードは各ロケーター毎に繰り返し現れる。これらのレコードは、ロケーターを持つ最も高い重要度レベルから最も低い重要度レベルへと向かう順序でなければならない。
【０１５４】
Ｐiltj：  タイル・ヘッダの終わり、又はタイル中の全符号化データの先頭から、第ｊ番目の重要度レベルからのデータを含むデータ・バイトまでのバイト数。これらのレコードは、最小のポインタから最大のポインタへと向かう順序である。
【０１５５】
res：  最後に置かれる、０からなるフィラー・バイト。
【０１５６】
〈情報タグ〉
情報タグは、正に情報であり、復号化器にとっては必ずしも必要でない。しかし、これらのタグは、パーサー又は復号化器に役に立つであろう。ビット対重要度レベル（ＢＶＩ）タグは、情報ダグの一例であり、図４１に示されているが、その詳細は後述する。
【０１５７】
〈可逆ウェーブレット〉
実施形態は、可逆ウェーブレットによる圧縮を利用する。
【０１５８】
〈ウェーブレット分解〉
初めに、可逆ウェーブレットによって、（画像データとしての）画像または他のデータ信号の分解を行う。可逆ウェーブレット変換は、整数係数を持つ信号のロスレス復元が可能な完全再構成システムを整数演算で実現する。効率逆変換は、行列式が１（又はほぼ１）の変換行列を使用する可逆変換である。
【０１５９】
可逆ウェーブレットを用いることにより、有限精度の演算でロスレス圧縮をすることできる。画像データに可逆ウェーブレット変換を適用することにより生成される結果は、係数の系列である。
【０１６０】
可逆ウェーブレット変換は、１組のフィルタを用いて実現できる。一実施例では、それらのフィルタは、２タップのローパス・フィルタと６タップのハイパス・フィルタで、本明細書においてＴＳ変換もしくは２・６変換と呼ぶ変換を行うためのものである。他の一実施例では、それらのフィルタは、２タップのローパス・フィルタと１０タップのハイパス・フィルタで、本明細書においてＴＴ変換もしくは２・１０変換と呼ぶ変換を行うためのものである。
【０１６１】
〈２次元ウェーブレット分解〉
ローパス・フィルタとハイパス・フィルタを用いて、多重解像度分解が行なわれる。分解レベル数は可変であり任意数でよいが、現在のところ分解レベル数は２レベルから８レベルまでである。最大レベル数は、［入力の長さ又は幅の最大値］の２を底とする対数に等しい。
【０１６２】
画像のような２次元データに対する変換を実行する最も普通のやり方は、１次元フィルタを別々に適用する方法、つまり、行方向に適用し、次に列方向に適用するという方法である。第１レベルの分解により４つの異なった帯域の係数が得られ、これらは本明細書ではＳＳ，ＤＳ，ＳＤ，ＤＤと呼ばれる。これら文字は前述のスムーズ(Ｓ)フィルタとディテール(Ｄ)フィルタを指し、それぞれロー（Ｌ）パス・フィルタとハイ（Ｈ）パス・フィルタに対応する。したがって、ＳＳ帯域は行方向及び列方向の両方向のスムーズ・フィルタより得られた係数からなっている。
【０１６３】
ウェーブレット分解の各周波数サブバンドはさらに分解することができる。最も普通のやりかたはＳＳ周波数サブバンドだけをさらに分解する方法であり、各分解レベルのＳＳ周波数周サブバンドが生成された時に、それをさらに分解することになろう。このような多重分解はピラミッド分解と呼ばれる。記号ＳＳ，ＳＤ，ＤＳ，ＤＤと分解レベル番号とによって各分解を表す。
【０１６４】
なお、ＴＳ変換、ＴＴ変換のどちらを用いても、ピラミッド分解は係数のサイズを増加させない。
【０１６５】
可逆ウェーブレット変換が再帰的に画像に適用される場合、第１分解レベルは最も細かいディテールつまり解像度に作用する。第１分解レベルで、画像は４つの部分画像（すなわちサブバンド）に分解される。各サブバンドは、１つの空間周波数帯域を表わしている。第１レベルのサブバンドは１ＳＳ，１ＳＤ，１ＤＳ，１ＤＤと表される。原画像の分解プロセスは水平、垂直両次元の１／２サブサンプリングを含むため、第１レベルのサブバンド１ＳＳ，１ＳＤ，１ＤＳ，１ＤＤがそれぞれ有する係数の個数は、入力が有する画像の画素（または係数）の個数の１／４である。
【０１６６】
サブバンド１ＳＳは、水平方向に低い周波数で垂直方向に低い周波数の情報を含んでいる。一般に、画像エネルギーの大部分は、このサブバンドに集中する。サブバンド１ＳＤは、水平方向に低い周波数で垂直方向に高い周波数の情報（例えば水平方向エッジの情報）を含んでいる。サブバンド１ＤＳは、水平方向の高い周波数の情報と垂直方向の低い周波数の情報（例えば垂直方向エッジの情報）を含んでいる。サブバンド１ＤＤは、水平方向の高い周波数の情報と垂直方向の高い周波数の情報（例えばテクスチャや斜めエッジの情報）を含んでいる。
【０１６７】
この後に続く下位の第２、第３、第４分解レベルはそれぞれ、前レベルの低周波ＳＳサブバンドを分解することにより作られる。第１レベルのサブバンド１ＳＳが分解されて、やや精細な第２レベルのサブバンド２ＳＳ，２ＳＤ，２ＤＳ，２ＤＤが作られる。同様に、サブバンド２ＳＳの分解によって、精細度の粗い第３レベルのサブバンド３ＳＳ，３ＳＤ，３ＤＳ，３ＤＤが生成される。また、サブバンド３ＳＳが分割されることにより、精細度がより粗い第４レベルのサブバンド４ＳＳ，４ＳＤ，４ＤＳ，４ＤＤが作られる。１／２サブサンプリングが行われるので、第２レベルの各サブバンドは原画像の１／１６の大きさである。このレベルの各サンプル（例えば画素）は、原画像中の同一位置のやや細いディテールを表す。同様に、第３レベルの各サブバンドは、原画像の１／６４の大きさである。このレベルでの各画素は、原画像中の同一位置のかなり粗いディテールを表す。また、第４レベルの各サブバンドは原画像の１／２５６の大きさである。
【０１６８】
分解画像はサブサンプリングのために原画像より大きさが小さいので、原画像の格納に使用されたメモリを利用して、分解されたサブバンド全部を格納することができる。言い換えれば、３レベル分解の場合、原画像と分解サブバンド１ＳＳ，２ＳＳは捨てられ、保存されない。
【０１６９】
４つのサブバンド分解レベルについてだけ説明したが、個々のシステムの要求に応じて、それ以上のレベルを生成することも可能である。また、ＤＣＴのような他の変換や一次元配置のサブバンドを用い、様々な親子関係を定義してもよい。
【０１７０】
なお、本発明のウェーブレットフィルタを利用すれば、ピラミッド分解で係数のサイズは増加しない。
【０１７１】
他の実施例では、ＳＳサブバンドに加えて他のサブバンドも分解されるかもしれない。
【０１７２】
〈ウェーブレットの木構造〉
ピラミッド分解のウェーブレット係数には自然で有用な木構造がある。サブバンド分解の結果は、最終の分解レベルに対応した１つのＳＳ周波数サブバンドだけである。一方、レベル数と同数のＳＤ，ＤＳ，ＤＤ帯域がある。この木構造は、ある周波数帯域内のある係数の親は、それより低解像度の同じ周波数帯域内のある係数であり、かつ同じ空間位置関係にあることを明らかにする。
【０１７３】
各木は、ＳＳ係数と、３つの部分木すなわちＤＳ，ＳＤ，ＤＤの部分木からなる。本発明の処理は、通常、これら３つの部分木に対して行われる。各木のルートは、真に平滑な係数である。画像のような２次元信号の場合、３つの部分木があり、それぞれの部分木は４つの子を持つ。この木階層構造は２次元信号に限定されない。例えば、１次元信号の場合、各部分木は１つの子を持つ。これ以上の高い次元は１次元の場合と２次元の場合から理解できる。
【０１７４】
多重解像度分割のプロセスは、フィルタ系によって行うことができる。１次元の典型的フィルタを使って実現される２次元２レベル変換の例については、米国特許出願第08/498,695号（出願日：1995年６月30日，発明の名称：Method  and  Apparatus  For  Compression  Using  Reversible  Wavelet  Transforms  and  an  Embedded  Codestream）及び米国特許出願第08/498,036号（出願日：1995年６月30日，発明の名称：Reversible  Wavelet  Transform  and  Embedded  Codestream  Manipulation）を参照されたい。
【０１７５】
〈順ウェーブレット変換の実行〉
実施形態では、２回の1-D演算によって、すなわち、まず水平方向の1-D演算を行い、次に垂直方向の1-D演算を行うことによって、ウェーブレット変換が実施される。一実施例においては、あるハードウェアで水平方向の演算を実行し、別のハードウェアで垂直方向の演算を実行する。
【０１７６】
レベル数で反復回数が決まる。一実施例では、水平、垂直両方向にＴＴ変換を用いて４レベル分解が行われる。別の実施例では、ＴＴ変換に代えＴＳ変換を用いて４レベル分解が行われる。
【０１７７】
変換は、演算効率がよい。一実施例においては、オンチップ及びオフチップのメモリの必要容量と必要帯域幅を減らすように、変換で実行される演算を順序付けする。
【０１７８】
〈１つのウェーブレット木の計算〉
以下の式はＴＳ変換とＴＴ変換の両方を定義するものである。入力x(n)に対し、ローパス・フィルタの出力であるスムーズ信号s(n)と、ハイパス・フィルタの出力であるディテール信号d(n)は次式に示すように計算される。
【０１７９】
【数１】
0003653183.tif 000003
【０１８０】
その逆変換は次式で示される。
【０１８１】
【数２】
0003653183.tif 000004
【０１８２】
ただし、p(n)は次式により計算される。
【０１８３】
【数３】
0003653183.tif 000005
【０１８４】
ＴＳ変換とＴＴ変換はt(n)の定義が異なる。
【０１８５】
ＴＳ変換の場合は次のとおりである。
【０１８６】
【数４】
0003653183.tif 000006
【０１８７】
ＴＴ変換の場合は次のとおりである。
【０１８８】
【数５】
0003653183.tif 000007
【０１８９】
なお、以下の説明において、記号|_・_|は切り捨てて丸めること、つまり打ち切りを意味し、床関数と呼ばれることがある。
【０１９０】
これらのフィルタは、加減算（と配線によるビットシフト）だけで実現できる。例えば、３の乗算と２２の乗算はシフトと加算で実行できる。
【０１９１】
なお、逆ＴＳ変換と逆ＴＴ変換においては、Ｓ変換と同様、入力信号ｘ(n)のレンジが出力信号ｓ(n)と同じになるようにローパス・フィルタが作られる。すなわち、スムーズ出力のビット数は増加しない。入力信号がｂビットの深さの画像であるときには、ローパス・フィルタの出力もｂビットである。例えば、入力信号が８ビット画像のときには、ローパス・フィルタの出力も８ビットである。このことはピラミッド・システムにとって重要な特性である。ピラミッド・システムでは、スムーズ出力が、例えばローパス・フィルタを連続的に適用することにより分解されるからである。従来技術のシステムでは、出力信号のレンジが入力信号のレンジより大きく、このことがフィルタを連続的に適用することを困難にしている。また、変換を整数演算で行う際の丸めによる系統誤差がないため、ロッシー・システムにおける全ての誤差を量子化によって制御可能である。
【０１９２】
さらに、ローパス・フィルタのタップは２タップだけであるため、非重複フィルタとなる。この特性は、ローパス・フィルタをハードウェアで実現する場合に重要である。
【０１９３】
〈埋め込み順序づけ〉
実施形態では、ウェーブレット分解の結果として生成された係数がエントロピー符号化される。係数は最初に埋め込み順序付けを施され、視覚的に重要な順に係数が順序付けられる。より一般的には、何等かの誤差距離（例えば、歪み距離）に関連して係数が順序付けされる。誤差距離または歪み距離としては、例えば、ピーク誤差と平均二乗誤差（ＭＳＥ）がある。また、順序付けは、ビット・シグニフィカンスの空間配置、データベース照会の検索能力、及び、方向性（垂直、水平、斜め等）を重視するように、順序付けを行うこともできる。
【０１９４】
データの順序付けが行われることにより、コードストリームの埋め込み量子化がなされる。本発明においては、２つの順序付け方法が用いられる。その一つは係数を順序付けするためのものであり、もう一つは係数中の２進値を順序付けするためのものである。本発明の順序付けはビットストリームを生成し、このビットストリームはその後にバイナリ・エントロピー・コーダーによって符号化される。
【０１９５】
〈ビット・シグニフィカンス表現〉
原成分が符号無しの時でも、大抵の変換係数は符号付き数値である（少なくとも１つのディテール・フィルタから出力される係数はどれも符号付きである）。一実施例では、係数内の２進値に用いられる埋め込み順序は、ビットプレーン順である。係数は、符号化される前に、ビット・シグニフィカンス表現で表される。ビット・シグニフィカンス表現は、一種の符号・絶対値表現であり、最上位ビット（ＭＳＢ）ではなく符号(sign)ビットが、最初の非０の絶対値ビットと一緒にエンコードされる。すなわち、符号ビットは、絶対値ビット全体の前に来るのではなく、最初の非０絶対値ビットの次に来る。また、符号ビットは、最上位の非０絶対値ビットと同じビットプレーン内にあるとみなされる。
【０１９６】
ビット・シグニフィカンス形式は３組のビット、すなわちヘッド・ビット、テール・ビット及び符号ビットによって数値を表現する。ヘッド・ビットとは、ＭＳＢから最初の非０絶対値ビットまでの全ての０ビットと、その最初の非０絶対値ビットである。最初の非０絶対値ビットが現れるビットプレーンで、係数の重要度が定まる。テール・ビットは、最初の非０絶対値ビットの次からＬＳＢまでの絶対値ビットからなる。符号ビットは符号(sign)を表わすにすぎず、例えば０は正を、１は負を表す。±（２のｎ乗）のような、ＭＳＢが非０ビットの数値は、ヘッド・ビットが１ビットしかない。０の係数は、テール・ビットも符号ビットも持たない。図１２は、ビット・シグニフィカンス表現の例を示す。表２は、−７から８までの４ビット係数の取り得る全ての値を示す。
【０１９７】
【表２】
0003653183.tif 000008
【０１９８】
表２に示されたビット・シグニフィカンス表現は、各列に１ビット又は２ビットを含んでいる。２ビットの場合、その最初のビットは最初の１のビットであり、その後に符号ビットが来る。
【０１９９】
画素の輝度に関して起こるような、値が非負整数の場合、採用し得る順序はビットプレーン順（例えば、最上位ビットプレーンから最下位ビットプレーンへの順）である。２の補数による負整数も許容される実施例では、符号ビットの埋め込み順序は、その整数の絶対値の最初の非０ロビットと同じである。したがって、１つの非０ビットが符号化されるまで、符号ビットは考慮されない。例えば、符号・絶対値表記法によれば、１６ビット数の−７は
１００００００００００００１１１
である。ビットプレーン・ベースでは、初めの１２デシジョン(decision)は「非有意」すなわち０となる。最初の１のビットは１３番目のデシジョンに現れる。次に符号ビット（「負」）が符号化される。符号ビットの符号化後、テール・ビットが処理される。１５番目と１６番目のデシジョンは共に１である。
【０２００】
係数は最上位のビットプレーンから最下位のビットプレーンへと符号化されるので、データのビットプレーン数が決まらなければならない。実施形態においては、データから計算される、又は画像の深さ及びフィルタ係数から導き出される係数値の絶対値の上界を見つけることによって、ビットプレーン数が判断される。例えば、その上界が１４９のときには、有意な８ビットつまり８つのビットプレーンがある。ソフトウェアの速度では、ビットプレーン符号化を利用できない場合がある。別の実施例では、ビットプレーンが符号化されるのは、係数が２進数として意味をなす時だけである。
【０２０１】
〈係数の桁揃え〉
実施形態では、ビットプレーン符号化の前に、係数を相互に桁揃えする。このようにする理由は、ＦＦＴやＤＣＴと同様、異なった周波数サブバンド内の係数は異なった周波数を表すからである。係数を桁揃えすることにより量子化を制御する。軽く量子化される係数ほど、早いビットプレーン側へ桁揃えされる（例えば左へシフトされる）。よって、ストリームが打ち切られると、これら軽く量子化された係数ほど、それを定義するためのビットが、重く量子化された係数のそれにより多くなる。
【０２０２】
図３９と図４０は、正規化桁揃えとピラミッド桁揃えをそれぞれ示す。
一実施例では、ＳＮＲ又はＭＳＥの観点から最高のレート・歪み性能が得られるように係数が桁揃えされる。多くの桁揃えが可能であり、例えばＭＳＥのような統計的誤差距離の点でほぼ最適な桁揃えがある。あるいは、桁揃えは、係数データの物理視覚的（physchovisual)量子化が可能かもしれない。桁揃えは、画像品質に（換言すればレート・歪み曲線に）相当な影響を及ぼすが、ロスレス・システムの最終的な圧縮率には殆ど影響を与えない。特殊な量子化には、他の桁揃え、注目領域忠実度符号化や解像度プログレッシブ桁揃えが適するかもしれない。
【０２０３】
桁揃えは、圧縮データのヘッダー中で指示してもよいし、特定のアプリケーション用に固定してもよい（すなわちシステムが１つの桁揃えしか持たない）。様々なサイズの係数に関する桁揃えは、符号化器及び復号化器の両方で分かっているので、エントロピー・コーダーの効率には影響しない。
【０２０４】
ｂビット／画素の入力画像を２レベルのＴＳ変換とＴＴ変換により分解した場合における各種係数のビット深さが図１０に示されている。図１１は、係数桁揃えに用いられる周波数帯域用の乗数の一例である。係数の桁揃えのために、1-ＤＤ係数のサイズが基準として用いられ、シフトはこのサイズに関して与えられる。シフトｎは、２のｎ乗倍することである。
【０２０５】
一実施例では、最大の係数の絶対値に関して係数がシフトされることにより、画像中の全係数の桁揃えが行われる。そして、桁揃え後の係数は、重要度レベルと呼ばれるビットプレーン単位で、最上位の重要度レベルより最下位の重要度レベルへと処理される。符号は、各係数の最後のヘッド・ビットと一緒に符号化される。符号ビットは最後のヘッド・ビットと同じ重要度レベルにある。重要なことは、桁揃えはエントロピー・コーダーへビットが送られる順序を制御するに過ぎないことである。余分な０ビットのパッディング、シフト、格納、符号化が実際に行われるわけではない。
【０２０６】
表３は、図３９に示したような正規化桁揃えに係数を揃えるためのシフト数の一例を示す。
【０２０７】
【表３】
0003653183.tif 000009
【０２０８】
様々なサイズの係数に関する桁揃えは、符号化器と復号化器の両方に分かっているのでエントロピー・コーダーの効率にはまったく影響を与えない。
【０２０９】
なお、同じデータセットの符号化単位でも桁揃えが異なる場合があることに注意されたい。
【０２１０】
〈コードストリームの順序付けと文脈モデル〉
一実施例において、コードストリームはメイン・ヘッダー、タイル・ヘッダー及びタイル・データからなる。各タイルは、画像におれる各成分の、少なくとも１つのデータ・ポイントを有する。成分データは、（変換方式又はバイナリ方式の符号化によって）変換されてから重要度レベルに桁揃えされる。そして、これらの重要度レベルは適当な文脈モデルとコーダー（例えばＦＳＭコーダー）を利用しエントロピー符号化される。
【０２１１】
なお、一実施例においては、モデル化と符号化は１つの連続したプロセスである。データの並べ替えは行われない。したがって、エントロピー符号化された重要度レベルは、データストリーム中の最小符号化単位である。エントリー・ポイントが重要度レベルの前に置かれているときには（すなわち、データが固定長である場合）、そのエントリー・ポイントより、コードストリームの符号化を開始できる。
【０２１２】
ＳＳ係数は、最上位の重要度レベルとされる。（なお、バイナリ方式符号化が用いられ、成分が０レベルに分解されるときには、係数はＤＤ周波数帯域にあるとみなされる。）これらの係数は（変換方式であってもバイナリ方式であっても）エントロピー符号化されない。ＳＳ係数はラスタ順にコードストリームに詰め込まれ、その最上位ビット（ＭＳＢ）が先頭、最下位ビット（ＬＳＢ）が最後であり、その順序は係数の深さとは関係ない。有符号成分は、２＾（深さ−１）だけオフセットさせた無符号値として格納される。例えば、８ビット深さの有符号成分は、−１２８から１２７までの値をとるが、１２８を加算されて０から２５５までの無符号値として格納される。
【０２１３】
一実施例では、各成分毎に、重要度レベルがコードストリーム中に最上位レベル（最高の番号）から最下位レベルへと順序付けられる。
【０２１４】
エントリー・ポイントを利用すれば、特定の重要ポイントから入って復号化することができる。エントリー・ポイントは、ＩＥＭタグ又はＩＥＴタグによって指示される。エントロピー・コーダーはコードストリームのある一定の点でリセットできるが、その点は、符号化時に決定され、重要レベルの先頭にのみ置くことができる。このリセットでエントリー・ポイントが生じ、符号化状態情報（文脈及び確率値）は既知の初期状態となる。コードストリームは、次の８の倍数ビットになるまでビットを詰められる。
【０２１５】
文脈モデルは、データが符号化される順序と、そのデータの特定ビット用の条件付けの両方を決定する。順序がまず考慮される。
【０２１６】
各ビットプレーン内で係数が処理される順序は、低い解像度から高い解像度へ向かう順（低い周波数から高い周波数へ向かう順）である。各ビットプレーン内における係数サブバンドの順序は、高いレベル（低解像度、低周波数）から低いレベル（高解像度、高周波数）への順である。各周波数サブバンド内では、符号化はある決まった順序で行われる。一実施例では、その順序はラスター順、２×２ブロック順、Ｓ字状(serpentine)順、Ｐｅａｎｏスキャン順、等々である。
【０２１７】
本発明の一実施例のコードストリームを利用する４レベル分解の場合、その順序は次のとおりである。
4-SS,4-DS,4-SD,4-DD,3-DS,3-SD,3-DD,2-DS,2-SD,2-DD,1-DS,1-SD,1-DD
【０２１８】
実施形態で利用される文脈モデルの一実施例を以下に説明する。このモデルは、符号化単位内のビットを、係数の空間・スペクトル従属関係に基づいて利用する。近傍係数及び親係数の利用可能な２進値を、文脈生成のために利用できる。しかし、文脈はデコーダビリティを左右し、また、多少は適応効率に影響する。
【０２１９】
実施形態は、バイナリ・エントロピー・コーダーのために、埋め込みビット・シグニフィカンス順に係数で作られたビットストリームをモデル化するための文脈モデルを提供する。
【０２２０】
図１３は、符号化単位の各係数の近傍係数を表す。図１３において、近傍係数は分かりやすい地理的表記で表されている（例えば、Ｎ＝北、ＮＥ＝北東、等々）。ある係数、例えば図１３のＰと、カレント・ビットプレーンが与えられたとすると、文脈モデルは、そのビットプレーンより前の符号化単位全ての、どんな情報を利用してもよい。当該文脈モデルの場合、注目係数の親係数も利用する。
【０２２１】
ヘッド・ビットは、最も圧縮性がよいデータである。したがって、圧縮率を上げるため、大量の文脈もしくは条件付けが利用される。
【０２２２】
〈文脈モデル−変換方式〉
文脈モデルの一実施例を以下に説明する。このモデルは、符号化単位内のビットを、係数の空間・スペクトル従属関係に基づいて利用する。近傍係数及び親係数の利用可能な２進値を、文脈生成のために利用できる。しかし、文脈はデコーダビリティを左右し、また、多少は適応効率に影響する。
【０２２３】
符号ビットの文脈モデルは、最後のヘッド・ビットの後で符号の符号化を行う構成である。Ｎ係数が正か負か又は符号の符号化前か否かにより、符号に対する文脈が複数ある。
【０２２４】
〈子ベース順〉
一実施例では、個々の周波数帯域のビットプレーンは、ＳＳ  ＤＳn  ＤＤn...ＤＳi  ＳＤi  ＤＤi...ＤＳ1  ＳＤ1  ＤＤ1の順に符号化される。一実施例では、周波数帯域内における個々の符号化並びにルックアヘッドの順序は、子ベース順である。子ベース順は２次元画像のスキャン順の一つであり、ラスタ順に似ているが、２ライン、２×２ブロックの順である点が異なる。「親」周波数帯域をラスタ順にスキャンすることを考える。各係数は４個の子を持っているであろう。これらの子は、左上、右上、左下、右下というように順序付けられる。次に、左端に戻って次の２ラインに戻り、最終的に右下コーナーで終わる。どのラインもスキップされない。図１４は、この子ベース順を示している。
【０２２５】
〈周波数帯域ビットプレーンのルックアヘッド〉
一実施例では、重要度レベル内のビットは周波数帯域順に符号化される。ある周波数帯域のあるビットプレーンを符号化する時に、最初の出力ビットはそのビットプレーン全体が０であるか否かを指示する。最初の出力ビットが０ならば、０のビットがエントロピー・コーダーへ送られる。周波数帯域ビットプレーンのルックアヘッドのための文脈はただ１つである。エントロピー・コーダーは次の周波数帯域のビットプレーンに進む。
【０２２６】
ビットプレーン中に１のビットが少なくとも１つあれば、１のビットがエントロピー・コーダーへ送られ、そのビットプレーンは後述のように符号化される。（なお、ビットプレーンの全ビットが０のときにも、エントロピー・コーダーへ１のビットを送ってもよい。この場合、そのビットプレーンは後述のように符号化される。）当該パスは、データを含んでいる可能性のあるビットプレーン全部に必要とされる。桁揃え及び係数の深さからカレント重要度レベルに０のビットがあるはずのない周波数帯域、又は、係数を含まない周波数帯域については、符号化されるビットは全くない。
【０２２７】
一実施例では、タイルのエッジであるため存在しない近傍及び親の係数ＤＳ，ＳＤ，ＤＤ係数は、０として処理される。この処理は、ルックアヘッド、ポスト・ルックアヘッド・ヘッドビット文脈モデル、ヘッドビット文脈モデルを試みるかどうか判断するプロセスにも適用される。
【０２２８】
本明細書で述べる文脈モデルの多くは、他の係数（同じ周波数帯域の近傍係数と親係数など）のビットを利用する。一実施例では、調べるビットは、近傍係数の種類によって決まる。最上位ビットを符号化するときには、親係数の参照ビットはその次位のビットであり、西、北西、北及び北東の近傍係数の参照ビットも最上位ビットであり、また、東及び南の近傍係数の参照ビットは、最上位ビットより上位のビットであるので０と仮定される。利用すべき参照ビットは図１５に示されている。最下位ビットを符号化する時には、親係数は現実の最下位ビットの下位にもう１つの０のビットがあると仮定される。親係数の参照ビットがカレント・ビットより下位の重要度レベルにあるときには、その親係数は０のヘッドビットと仮定される（その親係数は利用されない）。
【０２２９】
〈１６ビット・ルックアヘッド〉
実施形態ではルックアヘッドが利用される。このルックアヘッドは、コーダーにより符号化されるデシジョンの冗長性を減らすように設計される。ルックアヘッドを利用するか否かは、因果関係及び予測可能性のあるデータのみに基づいて決定される。ルックアヘッドを利用しないときには、データは何も符号化されず、各係数は以下のセクションで述べるように独立に符号化される。ルックアヘッドを試み成功したときには、１つの０のビットがルックアヘッド文脈によって符号化され、１６係数がスキップされる。ルックアヘッドを試み成功しなかったときには、１つの１のビットがルックアヘッド文脈によって符号化され、各係数は以下の説明中で述べるように符号化される。（なお、ルックアヘッドが不成功でも１つの１のビットを符号化できることに注意されたい。こうすることで、符号化器はルックアヘッド・プロセスを回避できる。）
一実施例では、ルックアヘッドを試みるか否かは、１６個のターゲット係数（子ベース順）、それらターゲット係数の４個の親係数、又は、ターゲット係数の北側の８個の近傍係数に、これまでに１のビットが見つかったか否かによって決まる。ルックアヘッドが試みられるのは、親係数の参照ビット、北側の近傍係数の参照ビット、及び１６個のターゲット係数の前ビットプレーンのビットが全て０のヘッドビットのときである。つまり、全ての参照ビットが０であるだけでなく、参照ビットより上位のビットも全て０である。タイル又は画像のエッジにおいては、２行中に利用できる１６個のターゲット係数がないことがあるが、この場合にはルックアヘッドは試みられない。（図２０のフローチャートの問に対する答えはｎｏである。）
なお、親係数が（桁揃えにより、又は不存在であることにより）利用できないか、利用されないときには、１のビットが今までに見つかっていないと仮定される。一実施例では、最高レベルのＤＳ，ＳＤ，ＤＤ係数についても、同じ考え方をするが、これはＳＳ係数が親係数として利用されないからである。これらの周波数帯域については、その親係数は利用できないとみなされる。さらに、北側の近傍係数が存在しないときには（例えば、タイルの最初のライン）、これらの利用不可能なビットは０と仮定される。
【０２３０】
ルックアヘッドを行うと判断されたときには、ターゲット係数のカレント・ビットプレーンの１６ビットが、全て０のヘッドビットでないか調べられる。全て０のヘッドビットのときは、カレント周波数帯域においてカレント重要度レベルで最後に試みられたルックアヘッドからなる文脈によって、１つの０のビットが符号化される。このルックアヘッドが、カレント周波数帯域りカレント重要度レベルで最初に試みられたルックアヘッドであるときは、前ルックアヘッドは失敗したものと仮定される（前に０が符号化されたと仮定する）。その１６ビットが全て０のヘッドビットでないときには、同じ文脈によって１つの１のビットが符号化される。なお、１６個以外の係数、例えば８個又は３２個の係数を利用してもよい。利用可能なメモリ量によって、又は、０のヘッドビットではない参照ビットの位置によって、それ以外の個数を選んでもよい。
【０２３１】
〈ポスト(post)ルックアヘッド〉
ルックアヘッドを試みて失敗したとき、又は、ルックアヘッドを試みなかったときは、その１６ビット（又は、それより少数のビット）は個別に符号化される。各係数は、そのヘッドビットが最初の１のビットが現れるまで復号化され、その直後に符号が復号化される。以下、その係数はテール部分である。
【０２３２】
２つのケース、すなわち、１）ルックアヘッドを失敗したケースと、２）ルックアヘッドを試みなかったケース、のいずれに対する符号化も同様である。ただし、一実施例において、それぞれのケースで異なった文脈が用いられ、また、第１のケースでは、復号化すべき係数が全てヘッドビットであることは既知である。
【０２３３】
〈ポストルックアヘッド・ヘッドビット文脈モデル〉
ルックアヘッドを試み失敗したときは、いくつかの事実が既知である。第１に、親係数と、日田側近傍係数すなわち上の８個の係数は、全て０ヘッド状態である。第２に、ターゲット係数も全て０ヘッド状態である。最後に、少なくとも１つの１のビットがターゲットビット中に存在する。この情報は、ルックアヘッドを試みないとい場合とは全く違うから、これらヘッドビットの符号化には異なった文脈が用いられる。したがって、非常に異なった統計を一緒にしないように、これらビットに対しては異なった文脈モデルが用いられる。
【０２３４】
この文脈モデルを作るため、ある値が近傍画素から導き出される。明白なことは、親係数と最近傍係数のある情報しか利用できないことである。そうでないと、文脈モデルが極端に大きくなってしまうからである。表４は、各係数の利用する情報のタイプを示す。図１７は、近傍係数の寄与を表す。
【０２３５】
【表４】
0003653183.tif 000010
【０２３６】
タイル境界では特殊な処理をする。一実施例では、１６個（８列）未満の係数しかないときには、ルックアヘッドを試みない。また、タイルの最下部で１ラインしかないときにも、ルックアヘッドを試みない。
【０２３７】
〈ルックアヘッドを試みない場合のヘッドビット文脈モデル〉
重要度レベルのビットは、定義された周波数帯域順に符号化される。各周波数帯域内では、ビットは子ベース順に符号化される。変換方式文脈モデルのヘッドビット文脈モデル部分は、次の２つの情報源に依存する。
・  親係数、２ビット（指示されるとき）
・  最近傍係数、７ビット
これら９ビットは、ある特定の状態すなわち文脈を知らせるユニークな数値を構成する。この文脈はＦＳＭコーダーへ送られ、符号化のための確率予測の適応化に利用される。言うまでもなく、この文脈として利用される情報は、因果的なもの、すなわち復号化時に利用可能なものである。また、親係数と最近傍係数の何らかの情報しか利用できないことも明かである。表４は、各係数の利用される情報のタイプを示す。
【０２３８】
親係数が利用される時には、親係数は２ビット、文脈に寄与する（表４のタイプＡの情報）。親係数は、同じ空間領域をおおう（同じ周波数帯域の）変換レベルが１つだけ高い係数と定義される。各周波数帯域の最高レベルの係数は、親係数を持たないので（ＳＳ係数は親係数としては利用されない）、文脈への寄与は０と定義される。図１８は、親係数の一例を示す。
【０２３９】
低い変換レベルの係数を、親係数の参照ビットがカレント・ビットより下位になるように桁揃えした場合には、親係数は文脈のために利用されない（その文脈への２ビットの寄与は常に０である）。また、親係数を利用しないように指示することができ、これは、ある係数の周波数帯域を全くランダムにアクセスする場合に役に立つ。また、親係数のない係数は親係数を利用しない。
【０２４０】
近傍係数による文脈への寄与を図１９に示す。図中の各タイプは表４の通りである。
【０２４１】
〈符号ビット文脈モデル〉
すべての係数の符号ビットは、係数の最後のヘッドビット（最初の１のビット）の直後に符号化される。符号ビットは、その最後のヘッドビットが含まれる重要レベルの一部である。符号ビットのための文脈は、ヘッドビット文脈モデルともテールビット文脈モデルとも異なり、北近傍係数のカレント符号ビットに基づく３つの状態からなる。北近傍係数が存在しないときには、符号は未知である。最後のヘッドビットと符号ビットは、ごく小さな１つの単位と考えるべきである。表５は、符号化ビット用の文脈を示す。符号ビットがヘッドビット後に符号化されようと、ポスト・ルックアヘッド・ヘッドビットの後で符号化されようと、同じ符号ビット文脈が用いられる。
【０２４２】
【表５】
0003653183.tif 000011
【０２４３】
〈テールビット文脈モデル〉
テールビット文脈モデルはヘッドビット文脈モデルとも符号ビット文脈モデルとも異なる。テールビット文脈モデルは、これまでにカレント係数にテールビットがいくつあったかによって決まる３つの状態からなる。これらの値を表６に示す。
【０２４４】
【表６】
0003653183.tif 000012
【０２４５】
〈各周波数帯域ビットプレーンのモデル化方法〉
各重要度レベルの各周波数帯域の各ビットプレーンのモデル化プロセスの一実施例は、図２０のように図示することができる。ここで行われるデシジョンを表７に、コーダーへ送られるビットと文脈を表８に示す。一実施例においては、全部で５つの独立した文脈がある。
【０２４６】
【表７】
0003653183.tif 000013
【０２４７】
【表８】
0003653183.tif 000014
【０２４８】
入力係数を符号／絶対値形式に変換する符号／絶対値ユニットの一例を含む、文脈モデルの他の実施例が、米国特許出願第08/498,695号（出願日：1995年６月30日，発明の名称：Method  and  Apparatus  For  Compression  Using  Reversible  Wavelet  Transforms  and  an  Embedded  Codestream）、米国特許出願第08/498,036号（出願日：1995年６月30日，発明の名称：Reversible  Wavelet  Transform  and  Embedded  Codestream  Manipulation）、米国特許出願第08/642,518号（出願日：1996年５月３日，発明の名称：Compression  and  Decompression  with  Wavelet  Style  and  Binary  Style  Including  Quantization  by  Device-Dependent  Parser）、及び、米国特許出願第08/643,268号（出願日：1996年５月３日，発明の名称：Compression/Decompression  Using  Reversible  Embedded  Wavelets）に述べられている。
【０２４９】
この文脈モデルは、データのエントロピー符号化のための文脈を提供する。一実施例では、実行される全てのエントロピー符号化は、バイナリ・エントロピー・コーダーによって実行される。単一のコーダーを用いて単一の出力コードストリームを生成してもよい。そうではなく、複数の（物理又は仮想の）コーダーを用いて複数の（物理又は仮想の）データストリームを生成してもよい。
【０２５０】
〈バイナリ方式の文脈モデル〉
バイナリ方式のためのモデル化は、変換方式の文脈モデルと似ている。しかし、その相違点の一つは、バイナリ方式の係数は無符号数値であり、したがって、ヘッドとテールの間には符号ビットがないことである。図３６は、このバイナリ方式文脈モデルのフローを示す。
【０２５１】
〈周波数帯域ビットプレーンのルックアヘッド〉
重要度レベルのビットは、前述した周波数帯域順に符号化される。ある周波数帯域のあるビットプレーン（恐らく、ある重要度レベルの一部）を符号化する時に、文脈モデルの最初の出力ビットが、そのビットプレーン全体が同一であるか否かを決定する。全ビットが同一ならば、１のビットがエントロピー・コーダーへ送られ、そうでなければ０のビットが符号化される。そして、１つのビットがエントロピー・コーダーへ送られ、その際に、そのビットが何であるか、すなわち０か１であるかを指示する。周波数帯域ビットプレーンのルックアヘッドのための文脈と、そのビットの値のための文脈とがある。
【０２５２】
異なった２つのビットがある場合、１つの１のビットがエントロピー・コーダーへ送られ、そのビットプレーンは後述のように符号化される。なお、ビットプレーンが不変であっても、１のビットがエントロピー・コーダーへ送られることに注意されたい。この場合、ビットプレーンは後述のように符号化される。このルックアヘッドを指示するビットは、全ての周波数帯域ビットプレーンについて必要とされる。
【０２５３】
〈１６ビット・ルックアヘッド〉
この１６ビット・ルックアヘッドは、（同一ライン上の）次の１６ビットが全て同じであるか否か調べる。同じならぱ、０のビットがエントロピー・コーダーへ送られる。その際、それら１６ビットがどのビットと同じであるか指示するため、０又は１が通知される。Ｎビット・ルックアヘッド用の独自の文脈がある。ある周波数帯域の最後で、残っているビットが１６ビットに満たない場合、その残っているビットは、これと同じ方法で取り扱われる。これらの条件の全てが真でなければ、１のビットがエントロピー・コーダーへ送られる。
【０２５４】
〈空間的文脈モデル〉
重要度レベルのビットは、前述の周波数帯域順に符号化される。各周波数帯域内では、ビットはラスタ順に符号化される。この文脈モデルは、同じ周波数帯域内の７個の近傍画素に依存する。
【０２５５】
これら画素それぞれの１ビットが、ある特定の状態すなわち文脈を知らせるユニークな数値を構成する。この文脈はＦＳＭコーダーへ送られ、符号化のための確率予測の適応化に利用される。この文脈として利用される情報は、因果的なもの、すなわち復号化時に利用可能なものである。
【０２５６】
図３６中の判定ステップについて表９に説明する。
【０２５７】
【表９】
0003653183.tif 000015
【０２５８】
図３６中の符号化のボックスについて表１０に説明する。
【０２５９】
【表１０】
0003653183.tif 000016
【０２６０】
〈近傍係数〉
文脈に寄与する近傍係数を図３７に示す。それぞれの寄与するものは、当該係数のカレント・ビットプレーンにおけるビット値である。なお、各周波数帯域は原画像をサブサンプリングしたものであるから、テンプレートに利用される画素は原画像上では隣接しないであろう。
【０２６１】
〈符号化及び復号化プロセス〉
図２１は、符号化プロセスの一実施例を示す。図２１において、符号化処理は、処理ロジックが１つのタイルの入力データを取得することから始まる（処理ブロック２１０１）。
【０２６２】
処理ロジックは、次に、バイナリ符号化を実行する必要があるか否か判断する（処理ブロック２１０２）。バイナリ符号化を実行すべきときには、処理は処理ブロック２１１１へ進み、処理ロジックは入力データのグレイ符号化を行い、バイナリ方式文脈モデルによって各係数の各ビットをモデル化する（処理ブロック２１１２）。処理は処理ブロック２１０８へ進む。
【０２６３】
バイナリ符号化を行うことができない場合は、処理は処理ブロック２１０３に進み、処理ロジックは可逆フィルタをデータに適用する。可逆フィルタの適用後、処理ロジックは別のピラミッド・レベルが必要であるか調べる（処理ブロック２１０４）。別のピラミッド・レベルが必要ならば、処理ロジックは可逆フィルタをＬＬ係数に適用し（処理ブロック２１０５）、処理ブロック２１０４へ戻って再び調べる。別の分解レベルが必要でなければ、処理は処理ブロック２１０６へ進み、処理ロジックは係数を符号・絶対値形式へ変換する。次に、処理ロジックは各係数の各係数を水平文脈モデルによってモデル化し（処理ブロック２１０７）、処理は処理ブロック２１０８へ進む。
【０２６４】
処理ブロック２１０８で、処理ロジックは各係数の各ビットを符号化する。次に処理ロジックは、各符号化データを送信又は格納する（処理ブロック２１０９）。
【０２６５】
次に、処理ロジックは画像中に、まだほかにタイルが用いられているか調べる（処理ブロック２１１０）。ほかのタイルが画像中にあるならば、処理ロジックは処理ブロック２１０１に戻り、処理が繰り返される。ほかにタイルがなければ処理は終了する。
【０２６６】
図２２は、復号化プロセスの一実施例を示す。図２２において、処理の初めに１タイル分の符号化データを取得する（処理ブロック２２０１）。次に、処理ロジックは、その符号化データをエントロピー復号化する（処理ブロック２２０２）。次に処理ロジックは、データにバイナリ復号化を施すべきか判定する（処理ブロック２２０３）。データにビット毎のバイナリ復号化を施すべきならば、処理は処理ブロック２２１１に進み、処理ロジックは各係数の各ビットをバイナリ方式文脈モデルによってモデル化し、そしてデータの逆グレイ符号化を行う（処理ブロック２２１２）。逆グレイ符号化の次に処理は処理ブロック２２０９へ進む。
【０２６７】
バイナリ復号化を行うべきでない場合には、処理は処理ブロック２２０４へ進み、処理ロジックは各係数の各ビットを水平文脈モデルによってモデル化する。次に処理ロジックは、各係数をフィルタ処理に適した形式に変換し（処理ブロック２２０５）、係数に可逆フィルタを適用する（処理ブロック２２０６）。
【０２６８】
可逆フィルタの適用後、処理ロジックは別のピラミッド・レベルがあるか判定する（処理ブロック２２０７）。別の分解レベルがある場合、処理は処理ブロック２２０８へ進み、処理ロジックは可逆フィルタを係数に適用し、そして処理は処理ブロック２２０７へ戻る。別の分解レベルが不要ならば、処理は処理ブロック２２０９へ進み、再構成されたデータは送信されるか格納される。
【０２６９】
次に、処理ロジックは画像にほかにまだタイルがあるか調べる（処理ブロック２２１０）。まだタイルがあるならば、処理ブロック２２０１に戻って処理が繰り返されるが、もうほかにタイルがなければ処理は終了する。
【０２７０】
〈エントロピー符号化〉
一実施例では、エントロピー符号化は全てバイナリ・エントロピー・コーダーによって実行される。一実施例では、エントロピー・コーダーはＱコーダー、ＱＭコーダー、有限状態マシン・コーダー、高速並列コーダー等からなる。単一のコーダーを用いて単一の出力コードストリームを生成してもよいし、あるいは、複数の（物理又は仮想）コーダーを用いて複数の（物理又は仮想）データストリームを生成してもよい。
【０２７１】
一実施例では、バイナリ・エントロピー・コーダーはＱコーダーからなる。Ｑコーダーの詳細については、Pennebaker，W.B.，et  al.，"An  Overview  of  the  Basic  Principles  of  the  Q-coder  Adaptive  Binary  Arithmetic，"IBM  Journal  of  Research  and  Development，Vol.32，pg.717-26，1988を参照されたい。別の実施例では、バイナリ・エントロピー・コーダーは、ＱＭコーダーを用いる。このＱＭコーダーは周知の効率バイナリ・エントロピー・コーダーの一つである。ＱＭコーダーは、確率スキューが非常に高いビットに対し特に効率的である。ＱＭコーダーはＪＰＥＧ標準とＪＢＩＧ標準の両方で利用される。
【０２７２】
バイナリ・エントロピー・コーダーは、有限状態マシン（ＦＳＭ）コーダーによって構成してもよい。このようなコーダーは、確率及び事象(outcome)から圧縮ビットストリームへの単純な変換が可能である。一実施例では、有限状態マシン・コーダーは、テーブル・ルックアップを使い、符号化器・復号化器兼用に構成される。多様な確率予測法を、かかる有限状態マシン・コーダーに利用できる。０．５に近い確率の場合に圧縮率が非常によい。高スキュー確率の場合の圧縮率は、使用するルックアップ・テーブルのサイズに左右される。それはＱＭコーダーと同様に、埋め込みビットストリームの場合に有効である。デシジョンが発生順に符号化されるからである。出力はルックアップ・テーブルによって決定されるので、「キャリーオーバー」(carry  over)問題が起こる心配がない。実際には、ＱコーダーやＱＭコーダーと違って、最大の遅延は符号化と圧縮出力ビットの生成との間に生じる。一実施例では、有限状態マシン・コーダーは、米国特許第5,272,478号（発行日：1993年12月21日，発明の名称：Method  and  Apparatus  for  Entropy  Coding”に述べられているＢコーダーからなる。別の実施例では、この有限状態マシン・コーダーは、米国特許出願第08/719,819号(出願日：1996年９月26日，発明の名称：Apparatus  and  Method  for  Performing  M-ARY  Finite  State  Machine  Entropy  Encoding）に述べられているコーダーからなる。
【０２７３】
一実施例では、バイナリ・エントロピー・コーダーは高速並列コーダーからなる。ＱＭコーダーもＦＳＭコーダーも、１ビットずつ符号化又は復号化する必要がある。高速並列コーダーは、数ビットを並列に処理する。一実施例では、高速並列コーダーは、圧縮性能を犠牲にすることなく、ＶＬＳＩハードウェア又はマルチプロセッサ・コンピュータで実現される。実施形態において利用可能な高速並列コーダーの一例が、米国特許第5,381,145号（発行日：19995年２月10日，発明の名称：Method  and  Apparatus  for  Parallel  Decoding  and  Encoding  of  Data）に述べられている。
【０２７４】
殆どの効率バイナリ・エントロピー・コーダーは、基本フィードバックループによって速度が制限される。可能な解決法の一つは、入力データストリームを複数のストリームに分割して並列の複数の符号化器に与えることである。これらの符号化器の出力は、可変長符号化データの複数のストリームである。この種の方法の問題点の一つは、データを単一のチャンネルでどのようにして伝送するかである。米国特許第5,381,145号に述べられている高速並列コーダーは、この課題を解決するため、それら符号化データストリームをインターリーブするという方法を採用する。
【０２７５】
実施形態に利用される文脈の多くは定確率であるため、Ｂコーダーのような有限状態マシン・コーダーが特に有効である。なお、システムが０．５に近い確率を利用する場合、上記特許に開示された高速並列コーダー及び有限状態マシン・コーダーは共にＱコーダーより効率よく動作する。よって、それら両コーダーは、文脈モデルと一緒に用いれば、高い圧縮性能を発揮する可能性を持っている。
【０２７６】
別の実施例では、バイナリ・エントロピー・コーダーと高速ｍ元コーダーの両方が利用される。この高速ｍ元コーダーはハフマン・コーダーでよい。
【０２７７】
〈ロッシー圧縮再構成〉
〈ロッシー係数再構成〉
係数は量子化されているのであるから、ある範囲の数が、その妥当な再構成値内に含まれている。このような場合、係数の下位の（つまり下の）ビットは通常は未知であるから、これら下位ビットに対しビット値を割り当てる必要がある。一実施例において、値を所定の整数値の集合に切り下げることによって、量子化値のロッシー再構成を行う。例えば、一実施例では、０と３１の間の全ての係数は０に量子化され、３２〜６３の間の全ての係数は３２に量子化される、等々である。つまり、この場合には、係数の未知ビットが全て０で置き換えられる。図２３は、量子化しない場合の係数の一般的な分布を示す。
【０２７８】
別の実施例においては、各値域の中央の値が、その係数群を代表する、より正確な値として用いられる。例えば、６４と１２７の間の全ての係数が９６（あるいは９５）に量子化される。ある点に値が量子化されるとき、その点は再構成点と呼ばれる。
【０２７９】
さらに別の実施例においては、各値域の下限値から、その０．３７５（３／８）分だけ大きい値が用いられる。例えば、６４と１２７の間の全ての係数の再構成点は８８となる。個々の画像、データ分布、期待する結果、その他の基準に基づいて、どのような値を選んでも構わない。
【０２８０】
画像間の差異により、得られる分布の形がゆがむ。例えば、図２３中のカーブ２７０１とカーブ２７０２を比較されたい。
【０２８１】
再構成点は分布に基づいて選ばれる。一実施例では、分布が推定され、その推定分布に基づき再構成点が選ばれる。推定分布は、既知のデータに基づいて生成される。一実施例においては、量子化係数のヒストグラムが推定に利用される。
【０２８２】
分布の分散を符号化期間に測定してもよい。この分散を復号化期間に復号化器に与えることによって、再構成値を選択する、より良好な推定をしてもよい。ただ１つの分散を、ある周波数帯域の全ての量子化係数のために利用してもよい。一実施例では、その分散は復号化器へ通知される。この通知は、独立した信号によってもよいし、コメント・タグのようなタグを用いて分散を提供する方法で行ってもよい。
【０２８３】
なお、再構成点の選び方によっては、非０係数にノイズが入り込むことがある。どのような再構成点を選ぶかにより、画像に注入されるエネルギー量が異なるであろう。一実施例においては、異なるピラミッド・レベル又は異なるサブバンドには、異なる再構成点が用いられる。
【０２８４】
データが集まるまで、デフォルトの再構成点を用いることができる。このように、実施形態は、ロッシー再構成を行う適応的な方法を提供する。さらに、実施形態は、係数再構成を改善する非反復的方法である。
【０２８５】
分布の差異によって値域の使われ方が不均一になることに対する補償のために、次のように規定する。
【０２８６】
【数６】
0003653183.tif 000017
【０２８７】
ここで、ｓ2は利用可能なデータを基に復号化器で測定された標本分散であり、Ｑは復号化器に通知された量子化である。そして、非０係数を修正するため、その係数を０から遠ざける。すなわち
【０２８８】
【数７】
0003653183.tif 000018
【０２８９】
ここで、ｉは任意の整数である。
【０２９０】
一実施例では、全ての復号化が終わってから、全ての非０係数が、ある再構成レベルに調整される。この際、各係数を読み込み、恐らく修正しから書き込む必要がある。
【０２９１】
別の実施例では、各係数の各ビットプレーンが処理される時に、その係数が非０ならば、その係数の適切な再構成値が格納される。復号化が終わった時には、全係数がその適切な再構成値に設定済みである。したがって、再構成レベルの設定のために別途メモリを読み書きする必要がない。
【０２９２】
〈ノイズ注入〉
実施形態は、復号化されるデータにノイズを注入する方法を提供する。一実施例では、復号化されるデータは、量子化された画像データである。一実施例では、この量子化画像データは量子化された係数からなる。ウェーブレット係数の量子化は本質的にローパス処理である。例えば、データの一部分しか復号化されない場合には、データを量子化してよい。テクスチャが破壊されない限り、画像データにローパスフィルタ処理を施して構わない。このテクスチャの雰囲気は、ノイズを注入することによって回復するだろう。したがって、量子化の一機能として、ノイズを画像に注入する。
【０２９３】
一実施例においては、０の量子化係数だけを利用してノイズが画像に注入される。ランダム値が０量子化係数に加算されるであろう。０量子化係数は、一連の０ビットの後にある個数の未知ビットが続いた形で表現されるであろう。これらの未知ビットが、ランダム値を加算することによって再構成される。これらの未知ビットが４ビットの未知データの場合には、それら未知ビットは０〜１５までの数で置き換えられるであろう。その数が大きな値であるほど、ノイズは大きい。未知ビットは絶対値ビットである。符号ビットもランダムに選択してもよく、その結果、−１５と１５の間の係数が得られる。
【０２９４】
なお、レベル１変換のＤＤ係数に加算されたノイズの影響は４画素値にしか及ばないが、これは本発明の可逆ウェーブレット変換であるからである。したがって、ノイズを注入しても、近傍画素に目につくような歪みは生じない。
【０２９５】
一実施例では、０量子化係数の全部にノイズが注入されるわけではない。例えば、ピラミッド・レベル１のＤＤ係数にだけノイズが注入される。もう一つの実施例においては、ピラミッド・レベル１のＤＳ係数及びＳＤ係数にだけノイズが注入される。
【０２９６】
他の実施例では、そのノイズは、原画像中のノイズの関数である。原画像中のノイズの関数としてのノイズを注入するために、原画像中のノイズが測定されて復号化器に与えられる。一実施例では、エネルギー分布を表す空間マップが作成される。一実施例では、原画像中のノイズの分布の大きさと偏差が復号化器に通知される。この情報の復号化器への通知には、コードストリーム中のタグ、又は、独立した信号もしくは独立した情報パスを利用してよい。
【０２９７】
他の実施例では、ノイズを注入すべき場所を表すアルファ平面（alpha  plane）が作られるであろう。このアルファ平面を混合平面（blending  plane）と同様の方法で利用すれば、様々な量のノイズを注入すべき画像上の様々な場所が分かるであろう。すなわち、アルファ平面は、ある場所では、ある種のノイズの注入を指示し、別のある場所では異なった量のノイズの注入を指示するであろう。
【０２９８】
加えられるノイズは、０の囲む範囲内の値の分布によって決まる。その分布にオフセットがあり、０値近傍に中心がない場合には、ノイズを加えるだけでなく、あるバイアス値も加える必要があろう。
【０２９９】
デタイリング(detiling)とリンギング抑制
２・１０変換は、ロッシー圧縮後に再構成する場合に有利な点がいくつかある。繰り返しになるが、２・１０変換の定義は次の通りである。
【０３００】
【数８】
0003653183.tif 000019
【０３０１】
一実施例では、ロッシー圧縮のために、Ｄが量子化される。好適な再構成データを生成するため、ある場合には、Ｄ値が直接算定される。好適なＢ値が決定され、そのＢ値が、必要ならＰを用いて、Ｄ値に変換される場合もある。
【０３０２】
〈２パス逆変換用の新しい順序〉
図２４は逆ＴＴ変換の計算方法を示す。この方法は、適応的なウェーブレット係数再構成法を利用する場合に有益である。２つのパスそれぞれの出力はＳ係数である。一実施例では、このＳ係数は画像のサンプル値（画素成分）である。他の実施例では、Ｓ係数は画像の複数のサンプル値の平均値（「超画素成分」）である。Ｓ成分を空間領域の画像データとして取り扱うことにより、良好な再構成データを生成することができる。
【０３０３】
好適な再構成の基礎となるものは画像モデルである。画像モデルは、シャープなエッジと、エッジが存在しない滑らかな領域を規定するであろう。画像モデルは、画像に依存しないかもしれないし、あるいは、特定画像用の圧縮画像で記述されるかもしれない。いくつかの画像モデルを後述する。２パス逆変換を利用すれば、変換の計算及び量子化限界の決定のために中間結果をセーブする必要性が減少する。つまり、最初のパスで破壊されるＳＳ係数とＳＤ係数をセーブする必要がない。
【０３０４】
図２４において、２パス逆変換処理は第１のパスであるパス１から始まる。このパス１は、ＳＳ係数とＳＤ係数のみに対し逆垂直変換を実行する。各ＳＳ係数の量子化によって２サンプルの再構成限界が制御される。第２のパスであるパス２は一度に２ラインの係数を処理し、ＤＳ係数とＤＤ係数の逆垂直変換を行い、また、垂直方向に隣接するＳ係数とＤ係数の２つのペアに対する逆水平変換を行う。第２パスは、その２つの逆変換操作が、それらラインのデータ全部に施されるまで続く。なお、ＤＳ係数とＤＤ係数の量子化によって４サンプルの再構成限界が制御される。また、第２パスで、上のラインからのＤＳ係数は、ＤＳ係数及びＤＤ係数に対する逆垂直変換の計算のためのものである。
【０３０５】
〈再構成及びクリッピング〉
好適な再構成の生成手順の一実施例は次のとおりである。
【０３０６】
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
係数及び／又は正規再構成を解析（オプション）
ＦＯＲ  変換レベル＝max_level  ＤＯＷＮＴＯ １
ＦＯＲ  各サブバンド  ＤＯ
ＦＯＲ  各ＳＤ係数  ＤＯ
好適再構成を計算
量子化に整合するようにクリッピング
逆変換のパス１を実行
ＦＯＲ  ＤＳ，ＤＤ係数の各ペア  ＤＯ
好適再構成を計算
量子化に整合するようにクリッピング
逆変換のパス２を実行
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−    。
【０３０７】
最初の係数解析ステップが用いられるのは、係数から好適再構成が判断される時である。その一例は、エッジ抽出に関連して後述する。
【０３０８】
クリッピングとは、ある値がある値域から外れている場合に、その値を、その値域内のある値（又は値域の一端の値）に設定する操作である。再構成画像が符号化データで指定されたものと同じ量子化係数となることを保証するために、クリッピングが不可欠である。量子化するまで分からないが元はＱビットであった、ある量子化計数値Ｄに関して、必要ならば、好適再構成をクリッピングするために使用可能なＤの最小値と最大値を決定する。最小値と最大値を計算するために、一実施例である以下のコードを利用できる。
【０３０９】
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
inline  void  twoten:  :q_to_minmax(int  d，int  q)
{
int  n=(1<<q)-1;
if(d==0){
min=-n;
max=n;
} else  if(d>0){
min=d&(-n);
max=d|n;
} else{
max=-((-d)&(-n));
min=-((-d)|n);
}
}
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−    。
【０３１０】
上に例示したコードにおいて、”＆”は論理積演算を意味し、”｜”は論理和演算を意味する。Ｄ値のクリッピングのために、後述のクリッピング・ルーチン”clip”が使用される。”clip”ルーチンはＳＤとＤＳに対し有効である。一実施例では”clip”ルーチンがＤＤ係数に対しても使用される、しかし、他の実施例では、”clip_loose”のようなルーチンのほうが、関連したＤＳ値及びＤＤ値の独立したクリッピングを±１誤差で補償できるので好ましいかもしれない。なお、”clip_loose”ルーチンは、”clip”ルーチンを呼び出すことに注意されたい。”flat”パラメータは、両サンプルが同一値として再構成されるという結果をもたらすＤ値、つまり、ＴＴ変換の”Ｐ”部分である。整数丸めのバラツキがあるため、両サンプルが同一値に再構成される結果となるような±１誤差は許容される。
【０３１１】
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
inline  int  twoten::  clip(int  n,int  min,int  max)
{
if(n<min)
return  min;
if(n>max)
return  n;
}
inline  int  twoten::  clip_loose(int  n,int  min,int  max,int  flat)
{
if(min-1==flat)
return  clip(n,flat,max);
else  if(max+1==flat);
return  clip(n,min,flat);
else
return  clip(n,min,max);
}
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−    。
【０３１２】
ＤＳ値及びＤＤ値については、好適な再構成値は、通常、”ｄ”値のペアとして決定される。下記の”do_clip_pair”ルーチンは、２つのＤ値すなわち”ａ”と”ｂ”をクリッピングし、結果として”a_clip”と”b_clip”を得る。なお、このルーチンは”clip_loose”ルーチンを呼び出すことに注意されたい。
【０３１３】
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
inline  void  twoten::do_clip_pair  Itwoten  *tt_0ds,twoten  *tt_1dd,int
vert_p)
{
int  a;
int  b;
int  s;
int  d;
int  s_clip;
int  d_clip;
int  a_clip;
int  b_clip;
a=tt_0ds->d();
b=tt_1dd->d();
s=s_calc(a,b);
d=a-b+vert_p;
s_clip=clip_loose(s.tt_0ds->get_min(),tt_0ds->get_max(),vert_p);
d_clip=clip_loose(d,tt_1dd->get_min(),tt_1ss->get_max(),vert_p);
a_clip=inverse_calc0(s_clip,d_clip,vert_p);
b_clip=inverse_calc1(s_clip,d_clip,vert_p);
}
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−    。
【０３１４】
”inverse_calc0”ルーチンと”inverse_calc1”ルーチンの一実施例は次の通りである。
【０３１５】
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
inline  int  s_calc(int  s0,int  s1)(return(s0+s1)>>1:);
inline  int  twoten::inverse_calc0(int  s,int  d,int  p)
{
return  s+((d-p+1)>>1);
}
inline  int  twoten::inverse_calc1(int  s,int  d,int  p)
{
return  s-((d-p)>>1);
}
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−    。
【０３１６】
なお、これらのルーチンの一方は偶数サンプル用であり、もう一方は奇数サンプル用である。
【０３１７】
〈タイル境界の再構成〉
本発明は、タイル境界を除去するために好適な再構成データを生成する。本発明は好適な再構成データを生成するため、近傍タイルの情報を利用して、タイル境界のない状態で変換を実行しても矛盾しないような再構成データを生成する。
【０３１８】
一実施例では、好適再構成であるので、順変換はタイル毎に独立に行われる。復号化時に、復号化、再構成及び逆変換を独立に行うか否かは、ユーザ又はアプリケーションが決めることである。ＴＴ変換ウェーブレットによれば、再構成が重複変換の長所を維持可能であり、たとえ画像のタイルが独立に変換される場合でもそうである。ＴＴ変換が画像のタイルに対し独立に実行される時に、タイル境界の歪みを容易に除去できる。
【０３１９】
タイル境界歪みをＴＴ変換係数から容易に除去できるのは、以下の理由による。偶数個のサンプルがある時には、ＴＴローパス・フィルタはタイル境界によって影響を受けず、正確なＳ係数をもたらす。Ｄ係数は境界に影響を受けるが、空間的に狭い範囲の影響しかない。なお、平滑とは、ハイパス・フィルタを境界をまたいで適用した時にレスポンスがないということである。したがって、平滑化は、変換領域で容易に行うことができ、また量子化で許容される程度に容易に制限できるであろう。
【０３２０】
一実施例では、本発明は、タイル歪みを除去するため、変換を適用する都度、それに先立ち再構成を行う。タイル歪みを除去するコードの一例は次のとおりである。
【０３２１】
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
for(levle=levels;level>0;level--)
境界によって影響を受けたＤＳ，ＤＤ係数をセーブ
ＳＤ係数を境界をまたいで平滑になるように再構成
For  各タイル
タイルの垂直逆変換
Ｄ係数を境界をまたいで平滑となるように再構成
For  各タイル
タイルの水平逆変換
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−    。
【０３２２】
逆ＴＳフィルタのＰ部分はＳ係数の関数であり、次式で得られる。
【０３２３】
【数９】
0003653183.tif 000020
【０３２４】
図２５は、タイル境界にまたがってＰfを計算するのに用いられる重み係数を示す（フルフレーム）。図２６は、ミラー処理によって単一のタイル境界でのＰtの計算に用いられる重み係数を示す。タイル境界歪みは、ＰtとＰfの間に差異があるために生じる。Ｄ＝−（Ｐf−Ｐt）を利用することで平滑な結果が得られるが、これは現実の量子化係数と矛盾しないはずである。
【０３２５】
量子化値は既知であるので、ＳＤ係数を量子化値と矛盾しないようにできる。Ｑビットに量子化されたビットプレーン数が未知ならば、まず、量子化されたＳＤ値から許容される最小値と最大値を決定する。前述のように、この最小値と最大値は次のコードによって決定できる。
【０３２６】
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
N=(1<<Q)-1
if(DS==0){
MIN=-N;
MAX=N;
}else  if(DS>0){
MIN=DS&(-N);
MAX=DS|N;
}else){
MAX=-((-DS)&(-N));
MIN=-((-DS)|N);
}
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−    。
【０３２７】
このＭＩＮ値とＭＡＸ値は、-(Pf-Pt)の計算により得られた結果のクリッピングに利用される。
【０３２８】
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
PfとPtを計算
SMOOTH=-(Pf-Pt)
if(SMOOTH<MIN)
SD=MIN;
else(SMOOTH>MAX)
SD=MAX
else
SD=SMOOTH
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−    。
【０３２９】
ＤＳ，ＤＤ係数の量子化は垂直変換によって広がる。したがって、水平変換の処理は少し複雑になる。水平変換を行うために、ＤＳ係数とＤＤ係数を共有する一対のライン”ａ”，”ｂ”が同時に検討される。これらのＤＳ値とＤＤ値は、逆垂直変換に先だってセーブされているため、いままでどおり利用可能である。変換後の値がＤＡとＤＢである。ＤＳとＤＤの最小値と最大値（MIN_DS,MIN_DD,MAX_DS,MAX_DD）が、ＤＳの最小値及び最大値と同じ方法で計算される。
【０３３０】
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
第１ラインのPfa,Ptaを計算
第２ラインのPfb,Ptbを計算
SMOOTHa=-(Pfa-Pta)
SMOOTHb=-(Pfb-Ptb)
S=(SMOOTHa=SMOOTHb)>>1;
P=DD-DA+DB
D=(SMOOTHa-SMOOTHb)+P
MIN_DSとMAX_DSによってＳをクリップ
MIN_DDとMAX_DDによってＤをクリップ
DA=S+((D-P+1)>>1);
DB=S-((D-P)>>1);
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−    。
【０３３１】
高周波情報を含まない画像（ＳＳ係数以外の係数が全て０である）については、どのようなタイリングでの再構成も（各ピラミッド・レベルでサンプル数が偶数ならば）フルフレームでの再構成と同一である。
【０３３２】
再構成により適当なタイルに対しわずかな係数が生じるに過ぎないので、その計算コストもメモリコストもあまり多くない。しかし、これらのコストを削減するために可能と思われる簡略化例がいくつもある。図２７は、Pf-Ptを近似的に計算するための重み係数を例示する。整数丸めのバラツキによる±１誤差があるため、高周波を含まない画像ではフルフレームときっかり同じ結果は得られないが、実際的なアプリケーションでは差は生じないであろう。考えられるもう一つの簡略化方法は、ＳＳ係数によって他のタイルのＳＳ係数の全部を近似しメモリ使用量を減らす方法である。
【０３３３】
ＴＴフィルタはロスレスであるから、タイル歪みの除去を後処理で行うこともできる。タイル歪み除去を行わずに、画像を伸長してもよい。タイル境界の位置と量子化は、後で利用できるようセーブされる。歪みのない画像が必要な時には、画像を変換してから、タイル位置と量子化に関する情報を利用し、タイル歪みのない画像を再構成することができる。
【０３３４】
復号化を単純化することは、多くのシステムで重要である。好適再構成のために必要とされる近傍タイルの情報量は少ない。その情報を、各タイルの符号化データと一緒にコメント・タグに格納すれば、各タイルを独立して復号化することができる。また、すべての係数に好適再構成を施す必要はない。一実施例では、特定の変換レベルの係数だけ、あるいは、０に量子化された係数のみに対し、好適再構成が施される。
【０３３５】
〈ステップ・エッジの再構成〉
所定数の係数を利用してステップ・エッジを再構成する。一実施例では、Ｓ係数だけが利用され、その所定数は５である。図２８の（Ａ）と（Ｂ）５個のＳ係数の組の例を示すが、それぞれ線形（平滑）エッジ又はステップ・エッジに再構成するのが適当である。太線は、好適再構成の刻み幅を示す。
【０３３６】
線形再構成をすべきかステップ・エッジ再構成をすべきか判定する方法の一実施例は以下の通りである。なお、この方法においては、”Ｂ”値すなわち２つのサンプル間の差が計算され、係数ＤはＢ＋Ｐの加算結果と等しいことに注意されたい。
【０３３７】
画像が平坦な場所ではステップ・エッジの再構成を試みる。一実施例では、最小のＳ値と最大のＳ値の差が１０未満ならば、ステップ・エッジを再構成しない。なお、別の実施例では、しきい値１０を使用する必要はなく、異なるしきい値を使用してもよい。
【０３３８】
ステップ・エッジを再構成する際、左側の３つのＳ値を使って再構成値Ｂを計算し（このＢを”LEFT”と呼ぶ）、また、右側の３つのＳ値を使って再構成値Ｂを計算する（このＢを”RIGHT”と呼ぶ）。LEFTかRIGHTのいずれかが０ならば、Ｂ＝０を使って再構成し、処理を抜ける。
【０３３９】
LEFTとRIGHTが同じ符号を持つならば、本発明は大きさが小さい方の再構成値を利用し、処理を抜ける。また、LEFTとRIGHTの符号が異なるならば、処理を抜け、一般的な再構成値が利用される。
【０３４０】
一実施例においては、再構成値Ｂの計算をするために、まず差を測定する。Δａ値とΔｂ値で、外側のＳ値ペア間の差と内側のＳ値ペア間の差を表す。例えば、図２８の（Ａ）と（Ｂ）を参照されたい。
【０３４１】
次に｜Δａ｜＞｜Δｂ｜であるか調べる。そうであるならば、Δａを、Δａ＝Δｂに変更する。
【０３４２】
ΔａとΔｂの符号が異なるケースの処理には２つの選択肢がある。第１の選択肢は、Δａ＝０に設定する方法である。第１の選択肢によれば、このケースは急峻なエッジということになる。第２の選択肢は、Δａ＝Δｂに設定する方法である。第２の選択肢によれば、このケースは滑らかな（標準的な）２・１０変換再構成ということになる。
【０３４３】
次に、ｘ＝Δａ／Δｂに設定する。ΔａとΔｂの符号が異なる場合、B=2Δb(1+x)に設定し、そうでない場合にはB=2Δｂ(1-3/4x)に設定する。最後に、LEFTとしてＢを返し、RIGHTとして−Ｂを返す。
【０３４４】
全てのエッジないし少なくとも大半のエッジがステップ・エッジである線画やグラフィック画像の場合、このような再構成方法を全ての変換レベルに対して利用できる。自然画像の場合、このような再構成方法は高周波変換レベルに対してのみ使用できる。
【０３４５】
〈整合フィルタによる再構成〉
整合フィルタを利用する再構成の狙いは、エッジの反対側の情報を利用しないようにすることである。あるエッジが見つかった時に、そのエッジの反対側に対し対称拡張を使う。例えば、エッジが見つかるか否かにより、次に示す本発明によるフィルタ係数セットの１つを使用できる。
【０３４６】
３  −２２      ０    ２２    −３      エッジ無し
０  −１３    −９    ２５    −３      左側にエッジ
０      ０  −４８    ６４  −１６      左側にエッジ
３  −２５      ９    １３      ０      右側にエッジ
１６  −６４    ４８      ０      ０      右側にエッジ
【０３４７】
５個のＳ係数でエッジを検出するため、以下に示す整合フィルタを利用する。これらのフィルタの次数は上記フィルタと同じである。
【０３４８】
１    −４      ４    −４      １
０    −１      ３    −３    −１
０      ０      ２    −３      １
１    −３      ３    −１      ０
１    −３      ２      ０      ０
【０３４９】
一実施例では、以下の場合に拡張フィルタ係数セットが利用される。
１）その対応した整合フィルタのレスポンスの大きさが最小である。
２）その対応した整合フィルタのレスポンスの大きさがしきい値（例えば４８）より小さい。
３）４タップの整合フィルタに関し、対応した３タップ整合フィルタのレスポンスの大きさも上記しきい値未満でなければならない。
【０３５０】
整合フィルタによる再構成は、全ての周波数レベルに対し実行しても、高周波レベルに対してだけ実行してもよい。
【０３５１】
〈エッジ抽出〉
好適再構成の目標は、急峻なエッジを獲得し、かつ、エッジ近傍のリンギングを除去することである。一実施例では、再構成画像中のエッジがある場所を識別し、様々な強さのガウス平滑化によって得られるマルチスケール情報を利用する。
【０３５２】
エッジ抽出には、図２９に示すようにガウスの差分法を利用する。１画素単位の精度でエッジの位置を検出するため、サンプリングは行われない。どのような種類のローパス・フィルタを用いても構わないが、分離型の水平及び垂直フィルタが計算効率の面で都合がよい。奇数長のフィルタを使用すれば、位相シフトは生じない。最適な選択は、次のフィルタ・タップである（後で１６により除算される）：１  ４  ６  ４  １            。
【０３５３】
実施形態において、エッジ抽出処理は最初に（水平方向又は垂直方向に隣接した）隣接画素ペアの減算を行う。差の大きさが、差方向の少なくとも１つの近傍画素より大きいときには、その差を潜在的エッジ位置としてセーブする。そうではなく、小さいときには、その差は無視される。あるしきい値（例えば８）より小さい差も無視される。
【０３５４】
図２９において、ローパス・フィルタ２９００は、ローパス水平逆変換フィルタ２９０１と、ローパス垂直逆変換フィルタ２９０２からなる。ローパス・フィルタ２９０２の出力は、次の解像度のローパス・フィルタの入力として用いられる。フィルタ出力は、水平差分ブロック２９０３によって処理されて極大ユニット２９０５のために利用され、また、垂直差分ブロック２９０４によって処理されて極小ユニット２９０６のために利用される。異なる解像度でのエッジ位置が比較される。エッジ位置（極大ユニット２９０５の出力）がセーブされるのは、１つ高い解像度又は低い解像度において、対応位置又はその４近傍の１つが、セーブされている同じ符号を持つ潜在的エッジ位置である場合である。真のエッジは様々なスケールにおいて同じ位置に出現するが、歪みはそうではない（すなわち、歪みは整列していない）。
【０３５５】
エッジ位置の利用目的の一つは、リンギング歪みを減少させつつエッジを保存する適応的フィルタ処理に利用することである。このような適応的フィルタ処理を実現する方法の一つは、前節で説明した５タップのローパスフィルタを、エッジのない５サンプル窓に利用することである。５サンプル窓の中心にエッジが存在する場合には、サンプルはそのまま用いられる（フィルタ処理しない）。窓内の他の位置に１つ又はそれ以上のエッジが存在する場合には、窓の中心にあるサンプルとタップで、エッジ以外つまりエッジの外側にあるものだけが利用され、フィルタの除数は利用したタップの和である。フィルタを複数回（例えば２回）反復して利用してもよい。このフィルタは、エッジの先鋭化に役立つ。エッジに接する画素はエッジから離れた画素の影響を受け、このことがエッジの反対側の情報のボケの改善に役立つ。
【０３５６】
〈好適な空間領域画像の利用〉
本発明の実施形態では、好適な再構成を以下のようにして生成する。まず、好適な空間領域画像を生成する。例えば、前記のエッジ保存型適応フィルタが用いられる。次に、その好適画像の部分的なウェーブレット変換を行う。水平変換は普通に実行される。水平変換のＳ出力だけが垂直変換により処理される。水平変換のＤ出力は処理されない。図３０を参照されたい。次に、部分変換により得られた係数を量子化係数の妥当な範囲にクリッピングして、好適な再構成を生成する。
【０３５７】
空間領域の好適画像を、係数がクリッピングされる範囲内で更新してもよく、また、処理を必要ならば繰り返してもよい。
【０３５８】
〈エッジを包含するローパス係数〉
エッジ検出方法は１画素単位の精度でエッジの位置を検出する。逆ウェーブレット変換のＳ係数又はＳＳ係数は、複数の画素に対応する。その画素の個数は、Ｓ係数の場合には２の（２×（level-1））乗であり、ＳＳ係数の場合には２の（２×level）乗である。あるＳ係数又はＳＳ係数の対応画素位置のどれかにエッジが含まれているときには、その係数はエッジだとみなされる。
【０３５９】
５サンプル窓の中心にある、分解レベルが１より大きいＳ係数又はＳＳ係数には、
(２のlevel乗）×（２のlevel乗）や（２のlevel乗）×（２の(level-1)乗）のエッジ探索領域は望ましくないかもしれない。窓の中心にあるエッジを検出し、それが実際に境界上にあると、良好な再構成を見つける機会が減ることがある。むしろ、変換方向の大きさがもっと小さな探索領域、例えば（２の(level-1)乗）×（２のlevel乗）、（２の(level-1)乗）×（２の(level-1)乗）あるいは（２の(level-2)乗）×（２の(level-2)乗）の探索領域を利用してもよい。レベル２には−１、レベル２より大きいレベルには−２を利用してもよい。
【０３６０】
エッジを含むＳ係数又はＳＳ係数が判明したならば、エッジ又はその反対側にある係数に対してミラー処理を利用できる。
【０３６１】
〈再構成結果のクリッピング〉
特にエッジを先鋭化しようとする再構成の場合、再構成結果を近傍Ｓ係数の範囲を超えないようにクリッピングすると有益であり、リンギングを減少させる。図３１は、再構成結果のクリッピングを例示する。一実施例では、中央のサンプルの隣接サンプルか、両側の２つの近傍サンプルのうちで中央サンプルに最も値が近いサンプルが利用される。
【０３６２】
図３１は、中央のＳ係数の再構成値のサンプル値（例えば画素）の範囲が、４番目のＳ係数の値を超える場合を示している。このような場合、その再構成値が近傍サンプル、例えば４番目のＳ係数を超えるときには、その値は近傍画素、例えば４番目のＳ係数の値にクリッピングされる。同様に、中央サンプルの可能な再構成値は、２番目のＳ係数、つまり図３１で中央画素の隣りにあるＳ係数の値を含まない。このような場合、中央サンプルの許容値は、そのサンプルの値まで拡張されるであろうから、クリッピングは指示されない。しかし、いずれの場合も、再構成値の許容範囲の一端を変更すると、その範囲の他端も対応して変更させることに注意されたい。例えば、サンプルの再構成値の上限が４番目のサンプルの値を超えないようにクリッピングしなければならない場合には、同様に中央サンプルより小さい範囲も狭められる。このように、再構成値を近傍係数の範囲を超えないようにクリッピングしてリンギングを減らす。
【０３６３】
〈テクスチャ抽出〉
ウェーブレットは、エッジと平滑領域の表現に優れている。テクスチャが表現しにくいのは、テクスチャは多数の小さなエッジとして表現しなければならないからである。テクスチャを表現する方法は数多くあるが、例えば、WP.K.Pratt，Digital  Image  Processing，John  Wiley  and  Sons，1978を参照されたい。実施形態では、ＪＰＥＧのようなＤＣＴベースの圧縮法に固有のテクスチャ・モデルよりも良好なものにできるテクスチャ表現方法を提供する。シヌソイド格子が用いられる。
【０３６４】
テクスチャ抽出を可能にするため、以下に述べる操作が符号化中に行われる。ウェーブレットでは良好に表現されないテクスチャを含む残余画像を生成する。その生成のために、まず、量子化後に再構成画像を生成する。例えば、目標とするおおよその圧縮率より大きな１つのＭＳＥ重要度レベルを量子化する。次に、その量子化再構成画像を原画像から差し引く。これが残余画像である。
【０３６５】
次に、残余画像中のテクスチャをモデル化する。その方法は一つは、２次元の任意の回転と、任意の位相及び周波数を持ち、残余画像の１６×１６の各ブロックと最大の相関を持つ１次元シヌソイドを見つけることである。次に、テクスチャ・モデルのパラメータを圧縮データストリーム中にコメントとして出力する。
【０３６６】
以上のプロセスにおいて、最も重要なステップはテクスチャのモデル化である。シヌソイドとの相関計算は計算量が多い。シヌソイドの探索空間を制限するため、自己相関が用いられる。２次元自己相関が残余画像のブロックについて計算される。シヌソイドの半周期は負自己相関に対応する（図３２参照）。０の近傍の負相関の最初の領域が重要である。
【０３６７】
負自己相関の領域を以下のように探索し、領域内の各整数ｘi，ｙi位置を見つけることができる。ステップ・サイズ(step)は１／４か１／８にしてよい。しきい値は４．７５でよい。これ以外のステップ・サイズとしきい値を用いてもよい。
【０３６８】
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
ＦＯＲ  ｘ＝ｘi−１＋step  ＴＯ  ｘi  ＳＴＥＰ  step
FOR  ｙ＝ｙi−１＋step  ＴＯ  ｙi  ＳＴＥＰ  step
ｒ＝ｓｑｒｔ（ｘ2＋ｙ2）
ＩＦ  ｒ＜しきい値  ＴＨＥＮ
ｘ＝ｘ／ｒ
ｙ＝ｙ／ｒ
シヌソイドｒ，ｘ，ｙとの相関計算
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−    。
【０３６９】
ｒの値はシヌソイドの半周期である。パラメータｘ，ｙは１次元シヌソイドを回転させる角度を指定する単位ベクトルである。これらパラメータは、符号化時の最良一致の判定と復号化時のテクスチャ生成の両方に利用される。
【０３７０】
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
ＦＯＲ  シヌソイドとの相関を計算する水平領域内のｉ
θ＝π＊（ｉ＊ｘ＋ｊ＊ｙ）／ｒ
coef_c＝cosθ＊residue［ｉ，ｊ］
coef_s＝sinθ＊residue［ｉ，ｊ］
correlation＝sqrt（coef_c2＋coef_s2）
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−    。
【０３７１】
このモデルを用いる場合、ｘ，ｙ，coeff_c，coeff_sのような４つのパラメータがコメントとして符号化データストリームに格納される。パラメータcoeff_c，coeff_sは、０．５のステップで量子化してよい。
【０３７２】
復号化時に、残余画像の生成に利用される量子化画像が生成される。テクスチャ・コメント中の情報を利用してシヌソイドが生成される。このシヌソイドが量子化画像に加算されることにより、好適な再構成画像が得られる。この好適再構成画像は好適な空間領域サイズで利用される。復号化器が利用できるウェーブレット係数が、残余画像生成に利用された量子化画像で用いられているウェーブレット係数より精度が高い場合には、テクスチャ・モデルに起因する歪みのいくぶんかは除かれる。
【０３７３】
ブロック・ベースのテクスチャ・モデルに代えて、連続的な、すなわち重複型モデルを利用してもよい。
【０３７４】
上記モデルは、ストライプや同様の１次元テクスチャのモデル化に適している。上記モデルは、２次元シヌソイド格子を処理するように拡張できる。自己相関空間において、ｘ，ｙに垂直な（かつ、０，０を通る）直線に沿った領域を探索して第１の負領域を見つけることができる。その垂直方向の長さを、シヌソイドの当該方向の半周期を特定するために使用できる。
【０３７５】
負自己相関領域が他のテクスチャ・モデル化法の最初のステップとして利用されるかもしれない。例えば、負自己相関領域が、構造化ノイズを生成するために利用されるかもしれない。
【０３７６】
〈特殊なタイル用バッファ〉
一実施例において、符号化法はコンピュータシステムの１つ以上のプロセッサ上で動作するソフトウェアによって実行される。この種のシステムでは、文脈モデルは多数の係数を調べ、多数のポインタを利用して、これら係数を管理する。これら係数は、その後に符号化される、ある係数のための文脈を得るために利用される。これらポインタは、文脈として利用される係数が格納されているメモリ・ロケーションを指示する。また、ポインタを次の文脈のメモリ・ロケーションを指すよう更新する方法を決定するため、垂直、水平両方向のオフセットも保持される。水平方向のオフセットはカレント係数から東隣りの係数までの距離であり、垂直方向のオフセットはカレント係数から南隣りの係数までの距離である。これらのオフセットは、メモリと、そのメモリにおける係数の格納方法とに依存してる。文脈モデルは、エッジの存在すなわち境界条件により、文脈を得るのに必要な係数が存在しない特殊な場合を利用してエッジを処理する。
【０３７７】
図３８の（Ａ）及び（Ｂ）は、次の４係数Ｘ，Ｙ，Ｕ，Ｖのメモリ・ロケーションを指示するために保持される９個のポインタの２つの例を示す。図３８（Ａ）において、９個のポインタ中には係数Ｎ，Ｘ，Ｕ，Ｓを指示するポインタがある。Ｎ，Ｘ，Ｕ係数の左に、別の３つの係数ＮＷ，ＸＷ，ＵＷがある。右側には別の２係数ＸＥ，ＵＥがある。Ｎ，Ｘ，Ｕ，Ｓのポインタは破線の枠で示したロケーションのアクセスのために利用される。図３８（Ｂ）は画素値Ｘの別のバージョンを示しており、その９個の値は、左側のＮＷ，ＸＷ，ＵＷと、中央の１列をなすＮＸ，Ｘ，Ｕと、右側の１列をなすＮＹ，Ｙ，Ｖである。なお、この場合、ＳとＥの情報は指示用ビットに格納される。Ｕのメモリ・ロケーションを更新する時に、Ｓに関し何が生じているか判定が行われる。Ｘの符号化中にＮＸは更新され、結局はＵの位置となる。
【０３７８】
コンピュータシステムでソフトウェアにより実現される文脈モデル化の性能を上げるため、文脈提供時に各タイル用に特殊なバッファを使用する。このバッファは１つのメモリ・ブロック、すなわち連続したメモリの固定サイズ又は可変サイズの１ブロックであり、メモリ・ブロックのサイズは、それに格納されている又は格納されることになるタイル（又は周波数帯域）のサイズより大きい。例えば、タイルが縦方向、横方向とも２５６係数の大きさである場合、メモリ・ブロックは縦方向、横方向とも３８４係数の大きさにしてよい。一例を図３３に示す。このように、タイルがどのようなサイズであっても、それより大きなメモリ領域がタイルに割り当てられる。メモリ・ブロックは、そこに格納されるタイルと同じ形状である必要はない。例えば、四角形のタイルに割り当てられるメモリ・ブロックそれ自体は、四角形である必要はない。
【０３７９】
大きめなメモリ・ブロックを使用する利点は、そのポインタを、タイルの所定の点（例えば左上角）を指す１つのポインタと１組のオフセットで置き換え可能であることである。これらのオフセットは各サブバンド毎に設定される。このように、上記文脈モデルの場合、９個のポインタと２つ以上のオフセットに代えて、１つのポインタと１組のオフセットしか必要でない。一実施例では、北東（ＮＷ）係数を指示する１つのポインタが、水平方向と垂直方向の２つの固定オフセットとともに、係数アクセスのために利用される。ＮＷポインタから他の９ロケーションまで、それらオフセットは正確な回数だけ繰り返し適用される。
【０３８０】
このような方法の利点の一つは、必要なレジスタ数が少なくなることである。オフセットは、集積したコードの一部としてレジスタや記憶空間に格納する必要がない。オフセットは定数であるからである。
【０３８１】
なお、実施形態では複数のポインタを、１つのポインタ（以前より少ない）と複数のオフセットで置き換えるが、構成によっては、２個以上のポインタを、より少ないオフセットと一緒に使用してもよいことは明白である。
【０３８２】
実施形態のもう一つの利点は、メモリ・ブロックのサイズが正しく選ばれれば、タイルを横切って処理を続ける時に、そのタイルが異なったキャッシュ・ラインにヒットしやすいことである。サイズの決定には、コンパイラ又はターゲット・マシンつまりソフトウェアが走るマシンも関係する。一実施例では、バッファのサイズは、どの帯域でもキャッシュ連想サイズの倍数にならないように選ばれる。バッファのサイズが、その倍数からずれていれば、キャッシュにある可能性が高くなる。サイズの選択が適切ならば、局所的に利用されたタイルの部分が、同じキャッシュ・ラインを再度使用しなくともキャッシュ内に保存されている可能性が増加し、望ましい。このように、バッファのサイズを適切に選べば、キャッシュの利用率を向上させることができる。
【０３８３】
実施形態はまた、エッジの問題を効率よく処理する。エッジ処理のため、エッジの処理が発生するかチェツクする必要はない。エッジでは、バッファ内のタイルの外側の値は所定値であると決められるからである。つまり、ポインタ値に基づき、ある文脈のために必要な係数値でタイルの外側にあるものは、所定値となるように選ばれる。一実施例では、その所定値は０である。ミラー処理が利用される場合には、これらの値は全タイルで同一ではないかもしれない。したがって、エッジ以外の条件の修正を可能にするため、タイルに０係数を付加してバッファの余ったスペースを埋め、エッジ外条件を修正可能にする。
【０３８４】
なお、別の実施例では、タイルの外側にある値の一部が０以外の値に設定されるかもしれない。
【０３８５】
〈頻繁に出現する文脈のモデル化〉
実施形態においては、文脈モデルはある係数の近傍係数を利用して文脈と１つのビットを生成し、この文脈とビットはエントロピー・コーダーへ送られる。頻繁に（時間的に１５乃至２５％を超える頻度で）利用される文脈は、同じ文脈が連続して現れる”ラン”を作る傾向がある。
【０３８６】
ＦＳＭコーダーは、同じ文脈を入力として受け取り、各文脈に応じてフィードバックループを作動させる。このフィードバックループは、ビットのシフト、レジスタの更新などの操作を含んでいる。フィードバックループとそれに関係した操作は時間がかかるものである。このオーバーヘッドを減らすため、連続的に繰り返す文脈全部に対し、可能ならフィードバックループを１度だけ作動させるのが望ましい。
【０３８７】
一実施例では、通常、同じ文脈が次の３つの状況で発生するであろう。
１）図１６、表７のＤ２及び表８のＣ２に説明したようなルックアヘッドを行う際、Ｄ２を画像のエッジに対するカレント位置として決定できる。これは多数のルックアヘッド区間かもしれない。前のＣ２ビットが０ならば、Ｃ２は、そのルックアヘッド区間全部に対し、符号化ビットが０であるあいだは同じ文脈を使用する。
２）ＴＴ変換のためのルックアヘッドが失敗した後で（図１７及び表８の１６ビットまでのＣ３を参照）、近傍係数が０のときに、符号化ビットが０であるあいだは同じ文脈が使用される。
３）図１９及び表８のＣ５に関しては、近傍係数が０のときに、復号化ビットが０であるあいだは同じ文脈が使用される。
【０３８８】
０係数のラン数を使って復号化済みビットを格納すれば、非０の近傍ビットのすばやい判断が可能になり、したがって同じ文脈である可能性のあるランを判断できる。
【０３８９】
実施形態においては、複数の文脈中のある文脈がより頻繁に発生しているかどうかは、これら文脈中の１つ前の番号のものが発生するまで不確定であるという点で、復号化器は推論的に動作する。実施形態では、ビットストリームを調べて所定個数の同一文脈が連続して発生したか否か判定し、そうである場合には、その所定個数の文脈全部についてＦＳＭコーダーと文脈モデルを別々に更新する複数ステップの処理は無効とされ、単一の更新に置き換えられる。このようして、ＦＳＭコーダーは、ビットストリームの所定数位置だけ前方へスキップする。同じように、文脈モデルも前方へスキップする。
【０３９０】
図３４は、一実施例を示す。図３４において、ＦＳＭコーダー３４００はルックアップ・テーブル（ＬＵＴ）３４０１を含み、このルックアップ・テーブル３４０１はカレントＦＳＭ状態３４１０、文脈のカレント確率状態３４２０、及び、符号化ビットストリーム中の復号化しようとしているビット３４３０を受け取るように接続されている。同じ文脈が連続して複数回出現したときには、同文脈が出現するたびにビットが復号化される。実際のビットストリームがカレントＦＳＭ状態及び初期確率に対応したビット・パターンと一致し、所定個数（例えば５個）の同一確率クラスのデシジョンが連続して発生することを表すときには、復号化器は、ＦＳＭ状態、文脈モデルを、それらのポインタを含め更新する操作などの所定数の操作を、１操作で実行する。
【０３９１】
図３４に戻って説明する。ＬＵＴ３４０１はｎビット用であり、カレントＦＳＭ状態３４１０と初期確率３４２０を受け取るように接続される。これらの入力に基づいて、ビットストリーム最大３４１２とビットストリーム最小３４１１が出力される。これらの２つのビットストリーム出力は、コンパレータ３４０２によって実際のビットストリーム３４３０と比較される。実際のビットストリーム３４３０がビットストリーム最大３４１２以下、かつ、ビットストリーム最小３４１１以上であると、コンパレータ３４０２の出力は推論的復号化の実行許可を指示する（同出力はｙｅｓ（Ｙ）に設定される）。そうでないときには、コンパレータ３４０２の出力は、推論的復号化の実行禁止を指示する。
【０３９２】
ＬＵＴ３４０１のシフト出力は、実際のビットストリーム３４３０をシフト入力するビット・シフタに接続される。このビット・シフタは、イネーブル信号としてコンパレータ３４０２のｙｅｓ／ｎｏ出力も受け取る。次ＦＳＭ状態はＦＳＭステージ・レジスタへ送られ、このＦＳＭステージ・レジスタはフィードバックしてカレントＦＳＭ状態３４１０を与える。ＦＳＭステージ・レジスタは、イネーブル信号としてコンパレータ３４０２のｙｅｓ／ｎｏ出力も受け取る。ＬＵＴ３４０１から出力される次確率は、文脈を格納している文脈メモリへ、書き込みイネーブルとして働くコンパレータ３４０２のｙｅｓ／ｎｏ出力とともとに送られる。コンパレータ３４０２のｙｅｓ／ｎｏ出力はまた、文脈モデルへ送られることに注意されたい。
【０３９３】
なお、推論的復号化が行われない場合には、実際のビットストリーム３４３０のビットは前述したように普通に１ビットずつ復号化される。
【０３９４】
符号化器が各ＦＳＭ状態に対し１ビットを出力しない端数ビットの場合の補償のために、ビットストリーム最大３４１２とビットストリーム最小３４１１が（一方のビットストリームではない）利用される。この場合、実際のビットストリーム中の別のビットを調べなければならないことがある。すなわち、ｎビットのランに応答して、符号化器は１つのビットストリームを発生し、また、そのｎビット・ランの後のビットに応じてＦＳＭ状態を変化させる。結局、符号化器が符号化ビットストリームにビットを出力するのは、同一文脈のランの後であり、当該文脈は部分的にその元の文脈ランが基礎となっていたものである。ビットストリーム最大及びビットストリーム最小は、これらビットが確実に考慮されるようにする。
【０３９５】
一実施例では、ルックアップテーブルは、次ＦＳＭ状態、次確率予測値、及び、入力中の実際のビットストリームをシフト入力させるビット量を指定するシフト指示も出力する。なお、それら出力の一部又は全部を別々のテーブルによって与えてもよい。
【０３９６】
別の実施例では、単一のルックアップ・テーブル、例えば図３５のＬＵＴ３５０１がカレントＦＳＭ状態、初期確率及びビットストリームを受け取るであろう。これら入力に応じて、そのテーブルは、ｙ／ｎ指示、又は文脈が出現した回数の指示を出力するであろう。なお、この実施例においては、固定したランレングス（例えば４）ではなく、ランレングスは可変であり、０，１，２，３，４，５，６，７である。しかし、この実施例の一つの問題点は、テーブルが大きくなることである。
【０３９７】
〈全タイルにわたる歪み〉
本発明の一実施例においては、符号化データストリームにタグが含まれている。例えば、あるタグは、全タイルにわたって合計した、各重要度レベルで符号化されるビット数を指示する。これがＢＶＩタグである。このタグを用いることにより、均等な忠実度又はタイル別の忠実度を有する復号化データを得るための固定サイズ量子化を行うことができる。
【０３９８】
ＢＶＩタグは、画像全体について、特定数のビットを重要レベルに関連付ける。このオプションのタグはメイン・ヘッダ中で用いられる。この可変長タグのサイズは、符号化器で計数された重要度レベル数によって決まる。
【０３９９】
ＢＶＩ：  表１１はタイル長メインヘッダ・パラメータのサイズと値を示す。
【０４００】
【表１１】
0003653183.tif 000021
【０４０１】
Ｌbvi：  マーカーを含めない、タグの長さ（バイト数）。この長さは偶数である。
【０４０２】
Ｃbvii：  どの成分のデータが記述されているかを通知する。このＣbviiパラメータは、Ｉbvi及びＰbviとともに１つのレコードを構成し、このレコードは記述すべき各成分及び重要度レベル毎に繰り返し現れる。これらのタグの順序は、第１の成分の全ての重要度レベルの記述の後に、次の成分の全重要度レベルの記述が続く、という順である。
【０４０３】
Ｉbvii：  Ｐbvii内のバイト数で符号化される、カレント成分の重要度レベル数。このバイト数（又は複数のバイト数）は、レート・歪みカーブ中の重要点を伝達するため符号化時に選ばれる。このＩbviパラメータは、Ｃbvi及びＰbviとともに１つのレコードを構成し、このレコードは記述された各成分及び重要度レベル毎に繰り返し現れる。
【０４０４】
Ｐbvii：  メイン・ヘッダとタイル・ヘッダ、並びにＩbviiの重要度レベル数に関係のある全データを含む、符号化データのバイト数。このＰbviパラメータは、Ｃbvi及びＩbviとともに１つのレコードを構成し、このレコードは記述された各成分及び重要度レベル毎に繰り返し現れる。
【０４０５】
res：  必要に応じて最後に置かれる、０からなるフィラー・バイト。
【０４０６】
データがタイルを用いて符号化されたとして、そのデータを一定の忠実度で固定サイズ表現に復号化するために、重要度レベルのエントリー・ポイントを利用する。少なくとも、各タイルは１つのエントリー・ポイントを持っている。これらのエントリー・ポイントは、本明細書で説明したタグ中に指定される。なお、全タイルにわたって歪みが一定である必要がない場合、各タイルのある解像度のあるバイト数を復号化することによって、固定レート量子化を達成できる。しかし、これでは、各タイルの忠実度が同じになる保証はなく、ましてや各タイルのデータ量が同一になる保証はない。
【０４０７】
本発明の一実施例においては、各タイルの同じ重要度レベルで量子化することによって、復号化は一定の歪みを維持する。なお、このようにすると、タイル毎にデータ量が違ってくる場合があるが、各タイルの忠実度は同一になる。このように、本発明は、復号化ビットがタイル間で非比例的に（不均等に）配分されることにより、各タイルにおいて同じ歪み特性になるように復号化する方法を提供する。かくして、画像全体にわたって一定の歪みを得ることができる。
【０４０８】
同じ忠実度を得るためのデータ量がタイルによって異なることがある。その理由の一つは、大量の符号化データを必要とする複雑な自然画を含んだタイルもあれば、データをほとんど必要としない空白領域のタイルもあるからである。
【０４０９】
以上に述べた如く、画像全体にわたって、ある特定の重要度レベルのために特定数バイトを得る目的に、ＢＶＩタグを利用できる。換言すれば、ＢＶＩタグは、重要度レベルに何バイトあるか指示する。
【０４１０】
各タイルを越えて同一の歪み特性を得るため、本発明は、ｎ個のタイルに関して各重要度レベルの符号化に使用されたバイト数を測定する。この情報は、ＢＶＩタグから判断してもよい。復号化画像に所定数ｘビットが必要とされる場合、各重要度レベルのバイト数が合計され、各タイルの重要度レベルのどこで終了すべきか判定が行われる。換言すれば、あるバイト数だけ復号化して同じ忠実度を獲得し、復号化を全てのタイルの同じ重要度レベルで終了する。
【０４１１】
例えば、次のような各重要度レベルでの画像全体の合計ビット数をＢＶＩが指示しているものとする（重要度レベル１２の隣りに記載されている１６，０１１は、重要度レベル１２と重要度レベル１３の合計ビット数を表す）。
【０４１２】
重要度レベル                ビット数
１３                  ４，０９６
１２                １６，０１１
１１                ４０，０００
１０              １００，０００
９              ２５０，０００
８              ５００，０００
７          １，０００，０００
６          ２，５００，０００
５          ５，５００，０００
【０４１３】
例えば、復号化画像に750,000ビットだけ許容されるときには、復号化可能であるのは全部で（重要度レベル７の1,000,000ビットには、重要度レベル８〜１３の500,000ビットが含まれているから）重要度レベル８と重要度レベル７の半分までである。
【０４１４】
本発明は、いろいろな方法で、復号化をデータのどこで終了させるか決定できる。データが尽きるまで重要度レベルを復号化してもよいかもしれない。例えば、上例において、重要度レベル１３から重要度レベル７の中途まで復号化することに決めてもよいかもしれない。別の実施例では、各レベルについて、ある割合を決め、その割合が各重要レベルに適用されるかもしれない。例えば、レベル７の半分だけ復号化するものと決定した場合、重要度レベル８が復号化された後のデータの半分だけではなく、データが尽きるまで全レベルにこの５０％が適用されるかもしれない。この場合、予定した復号化データ量と復号化すべきデータ量の全体的な割合から、各重要度レベルに対する復号化をどこで終了させるかの決め方が決まる。このように、本発明は、各タイルの忠実度が同一の固定サイズ表現を提供できる。換言すれば、画像の目標サイズは、画像中のデータ・レートの異なる様々なセグメントによって決定される。
【０４１５】
本発明を適用する場合、桁揃えの影響を受ける。一実施例では、データは図３９に示すような正規化桁揃えである。他の実施例では、データは図４０に示すようなピラミッド桁揃えである。上記例は正規桁揃えで実行されるが、本発明は、ピラミッド桁揃えで符号化されたデータを復号化しつつ実行し、全タイルが同一忠実度で正規化桁揃えの固定サイズ画像を得ることができる。正規化桁揃えを利用すれば、二乗誤差の観点から最良の品質が得られる。繰り返すが、ＢＶＩタグ中のデータは合計バイト数を指示するが、本発明は、その合計バイト数から復号化画像に割り当てられるバイト数を差し引く。データがピラミッド桁揃えでエントリー・ポイントを持つ場合、そのエントリー・ポイントは、前方へスキップし、適切な量のデータを各セグメントで切り捨てることを可能にする。一実施例では、切り捨ては正規化された形で行われ、最良のＭＳＥが得られる。
【０４１６】
例えば、ＢＶＩタグを利用して許容されるデータ量が決定され、これに基づいて、データがピラミッド桁揃えされている各ピラミッド・レベルの重要度レベルにわたって、データの切り捨てが決定されるであろう。例えば、図４０を参照すると、データは重要度レベル３０から重要度レベル２５まで復号化され、そして、重要度レベル２４から重要度レベル２０まで切り捨てられるであろう。データの復号化はまた、重要度レベル１９から重要度レベル１５まで行われ、そして重要度レベル１４から重要度レベル１０まで切り捨てられるであろう。また、データの復号化は重要度レベル９から重要度レベル５まで行われ、重要度レベル４から重要度レベル０まで切り捨てられるであろう。このように、異なったレベルの各周波数帯域について同じデータが切り捨てられていくが、この方式では、かかる切り捨てがどのような影響を及ぼすか分かっている。これは、正規化桁揃えのデータをレベル５で切り捨てすることと等価である。
【０４１７】
もう一つのシナリオでは、正規化桁揃えの場合でも、同様の方法でピラミッド量子化が可能である。各重要度レベルの初めにエントリー・ポイントがあるならば、各重要度レベルを重要なピラミッドレベルまで復号化することができる。例えば、図４０において、画像の解像度を各方向とも１／２に減らしたい（ピラミッド・レベル１を量子化しない）場合には、重要度レベル３及び２に対応した化データが復号化される。それが完了すると、復号化器は次の重要度レベルの先頭へ移る。
【０４１８】
なお、全ての周波数帯域を、各周波数帯域が他の周波数帯域に続くピラミッド配列で表してもよい。こうすると重要度レベル数が大幅に増加する。しかし、各周波数帯域は共通の幅を持つから、データの切り捨てが容易になり、切り捨てが画像の他の部分に及ぼす影響が分かりやすくなる。なお、この方法は、適当な位置で切り捨てできるよう各周波数帯域の先頭へ戻すために、何度もリセットする必要がある。
【０４１９】
このように、一般的に、符号化時の桁揃えが正規化桁揃え、ピラミッド桁揃え、その他のどのような桁揃えであっても、タグの情報に基づいて、全タイルにわたって一定の歪みを得るようにデータを復号化できる。タグのデータは、全タイルにわたって同じ解像度の安定したターゲット画像にするために、どのデータを復号化すべきか判断するのに役立つ。
【０４２０】
各色成分毎にＢＶＩを置くことができ、そしてユーザは各色成分毎にビットの割り当て方を決めることができる。この場合、ユーザはＢＶＩを利用して各成分毎に終了すべき重要度レベルを決定することができる。したがって、成分の情報量を比較対照し、成分間にどのようにビットを割り当てるべきか決定することができる。
【０４２１】
それゆえに、ＢＶＩタグは、各成分の切り捨てるビット割合を選択できるように複数の成分を詳細に記述可能である。これによって、各タイルのレートに拘わらず、各タイルのレートやサイズが等しくなくとも、全タイルにわたって配分が保証される。
【０４２２】
ＢＶＩタグのデータを、ＩＥＴ又はＩＥＭと、ＩＬＴ又はＩＬＭのタグ情報によって合成もしくは補足することができる。これらタグはそれぞれ、タイルにおける重要レベルを指示する。これらタグが全タイルに対し存在するときには、このデータを加えてＢＶＩと同様の情報を作ることができる。
【０４２３】
以上の説明を読めば、当業者には本発明の多くの変形及び修正が明らかになるであろう。ゆえに、図示及び記述した個々の実施例はいずれも説明のためのものであって、決して限定的に考えるべきでない。
【０４２４】
【発明の効果】
以上の説明から明らかなように、本発明によれば、画像のタイリングを行う場合のタイル境界歪みを除去ないし抑制することができる。
【図面の簡単な説明】
【図１】  子がその親によって条件付けされる文脈依存関係を示す図である。
【図２】  本発明の圧縮システムの一実施例のブロック図である。
【図３】  バイナリ方式において各ビットプレーンの各ビットに対し文脈モデルがとり得る幾何学的関係の一例を示す図である。
【図４】  バイナリ方式において各ビットプレーンの各ビットに対し文脈モデルがとり得る幾何学的関係の一例を示す図である。
【図５】  タイリング画像を示す図である。
【図６】  重要度レベル・エントリーポイント、メインヘッダのシンタックスを示す図である。
【図７】重要度レベル・エントリーポイント、タイルヘッダのシンタックスを示す図である。
【図８】  重要度レベル・ロケータ、メインヘッダのシンタックスを示す図である。
【図９】  重要度レベル・ロケータ、タイルヘッドのシンタックスを示す図である。
【図１０】  ｂビット／画素の入力画像を２レベルのＴＳ変換及びＴＴ変換で分解した場合の各種係数のビット深さを示す図である。
【図１１】  係数桁揃えに用いられる周波数帯域用の乗数すなわち調整値の一例を示す図である。
【図１２】  ビット・シグニフィカンス表現の例を示す図である。
【図１３】  １符号化単位の各係数の近傍係数の説明図である。
【図１４】  子ベースのスキャン順の説明図である。
【図１５】  参照ビットの位置を示す図である。
【図１６】  ルックアヘッドを試みるべきか決定するために利用される係数を示す図である。
【図１７】  ポスト・ルックアヘッド・ヘッドビット文脈モデルの近傍係数の寄与を説明する図である。
【図１８】  親の係数及びビットプレーンの一例を示す図である。
【図１９】  ヘッドビット文脈モデルに対する近傍係数及び親係数の寄与を説明する図である。
【図２０】  変換方式文脈モデルのためのフローチャートである。
【図２１】  符号化プロセスの一例を示すフローチャートである。
【図２２】  復号化プロセスの一例を示すフローチャートである。
【図２３】  ロッシー再構成の典型的な分布を示す図である。
【図２４】  逆ＴＴ変換の計算方法を説明する図である。
【図２５】  タイル境界でＰfを計算するために用いられる重みを示す図であめ（フルフレーム）。
【図２６】  ミラー処理を利用し単一タイル境界でＰtを計算するために用いられる重みを示す図である。
【図２７】  Ｐf-Ｐtの近似計算用の重みを示す図である。
【図２８】  （Ａ）５つのＳ係数を利用して線形再構成を判断する方法の説明図である。
（Ｂ）５つのＳ係数を利用してステップ・エッジ再構成を判断する方法の説明図である。
【図２９】  ガウシアン・エッジ抽出法の差分を発生する、１解決策としてのエッジ抽出法の一実施例を示すブロック図である。
【図３０】  再構成のための部分変換を示す図である。
【図３１】  クリッピング再構成の説明図である。
【図３２】  シヌソイドの周期と負相関の間の対応を示す図である。
【図３３】  単一タイル・バッファの一実施例の説明図である。
【図３４】  頻繁に発生する文脈のモデル化に使用されるＦＳＭコーダーの一実施例の説明図である。
【図３５】  頻繁に発生する文脈のモデル化に使用されるＦＳＭコーダーに導入可能な単一ルックアップテーブルの説明図である。
【図３６】  バイナリー方式文脈モデルの一実施例のフローチャートである。
【図３７】  バイナリー方式文脈モデルの文脈に寄与する近傍係数の説明図である。
【図３８】  次の文脈のメモリロケーションを指示するため保持される９個のポインタの２つの例を示す図である。
【図３９】  正規化桁揃えを示す図である。
【図４０】  ピラミッド桁揃えを示す図である。
【図４１】  ＢＶＩタグの一例を示す図である。
【符号の説明】
２０１  画像データ
２０２  可逆ウェーブレット変換ブロック
２０３  埋め込み順序量子化ブロック
２０４  グレイ符号化ブロック（バイナリ方式符号化部）
２０５  文脈モデル
２０６  エントロピー・コーダー
２１０  方式選択機構
２１１  多成分処理機構
２９００  ローパス・フィルタ
２９０１  ローパス水平逆変換フィルタ
２９０２  ローパス垂直逆変換フィルタ
２９０３  水平差分ブロック
２９０４  垂直差分ブロック
２９０５  極大ユニット
２９０６  極小ユニット
３４００  ＦＳＭコーダー
３４０１  ルックアップ・テーブル（ＬＵＴ）
３４０２  コンパレータ
【図１】
0003653183.tif 000022
【図２】
0003653183.tif 000023
【図３】
0003653183.tif 000024
【図４】
0003653183.tif 000025
【図５】
0003653183.tif 000026
【図６】
0003653183.tif 000027
【図７】
0003653183.tif 000028
【図８】
0003653183.tif 000029
【図９】
0003653183.tif 000030
【図１０】
0003653183.tif 000031
【図１１】
0003653183.tif 000032
【図１２】
0003653183.tif 000033
【図１３】
0003653183.tif 000034
【図１４】
0003653183.tif 000035
【図１５】
0003653183.tif 000036
【図１６】
0003653183.tif 000037
【図１７】
0003653183.tif 000038
【図１８】
0003653183.tif 000039
【図１９】
0003653183.tif 000040
【図２０】
0003653183.tif 000041
【図２１】
0003653183.tif 000042
【図２２】
0003653183.tif 000043
【図２３】
0003653183.tif 000044
【図２４】
0003653183.tif 000045
【図２５】
0003653183.tif 000046
【図２６】
0003653183.tif 000047
【図２７】
0003653183.tif 000048
【図２８】
0003653183.tif 000049
【図２９】
0003653183.tif 000050
【図３０】
0003653183.tif 000051
【図３１】
0003653183.tif 000052
【図３２】
0003653183.tif 000053
【図３３】
0003653183.tif 000054
【図３４】
0003653183.tif 000055
【図３５】
0003653183.tif 000056
【図３６】
0003653183.tif 000057
【図３７】
0003653183.tif 000058
【図３８】
0003653183.tif 000059
【図３９】
0003653183.tif 000060
【図４０】
0003653183.tif 000061
【図４１】
0003653183.tif 000062