JPH1084484A - データ圧縮システム - Google Patents

データ圧縮システム

Info

Publication number
JPH1084484A
JPH1084484A JP10979097A JP10979097A JPH1084484A JP H1084484 A JPH1084484 A JP H1084484A JP 10979097 A JP10979097 A JP 10979097A JP 10979097 A JP10979097 A JP 10979097A JP H1084484 A JPH1084484 A JP H1084484A
Authority
JP
Japan
Prior art keywords
data compression
compression system
image
data
bit
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP10979097A
Other languages
English (en)
Other versions
JP3989999B2 (ja
Inventor
F Keith Alexander
エフ キース アレクサンダー
L Schwarz Edward
エル シュワルツ エドワード
Zandi Ahmad
ザンディ アーマド
Borlick Martin
ボーリック マーティン
J Gomissh Michael
ジェー ゴーミッシュ マイケル
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Ricoh Co Ltd
Original Assignee
Ricoh Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from US08/642,518 external-priority patent/US5881176A/en
Application filed by Ricoh Co Ltd filed Critical Ricoh Co Ltd
Publication of JPH1084484A publication Critical patent/JPH1084484A/ja
Application granted granted Critical
Publication of JP3989999B2 publication Critical patent/JP3989999B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Landscapes

  • Compression Of Band Width Or Redundancy In Fax (AREA)
  • Image Processing (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)

Abstract

(57)【要約】 【課題】自然連続階調の画像、2値/ノイズフリー/浅
画素深度の画像、それら2種類の画像を含む画像を同じ
システムで的確に圧縮する。 【解決手段】方式選択機構110は、入力画像データ1
01が連続階調画像か2値画像か、あるいは、画像のど
の部分がそのような特性を持っているかを判定してモー
ドを選択し、入力画像データ又はその部分を、ウェーブ
レット方式のコーダ(可逆ウェーブレット変換ブロック
102,埋め込み順序付け量子化ブロック103,水平
コンテキストモデル・ブロック105)又はバイナリ方
式のコーダ(グレイ符号化ブロック104)へ送る。各
コーダは同じエントロピー・コーダ106を共有する。

Description

【発明の詳細な説明】
【0001】
【発明の属する技術分野】本発明はデータ圧縮及び伸長
システムの分野に係り、特に、圧縮/伸長システムにお
けるデータの非損失性(lossless)及び損失性(loss
y)の符号化及び復号化の方法と装置に関する。
【0002】
【従来の技術】データ圧縮は、大量のデータの蓄積及び
伝送のために非常に有用なツールである。例えば、文書
のファクシミリ伝送のような画像伝送に要する時間は、
圧縮を利用して画像再生に必要とされるビット数を減ら
すと飛躍的に短縮される。
【0003】従来より、多くの様々なデータ圧縮手法が
存在している。圧縮手法は、おおまかに分類すると2つ
のカテゴリー、つまり損失性符号化と非損失性符号化と
に分けることができる。損失性符号化とは、情報の損失
を生じ、したがって元のデータの完全な再現が保証され
ない符号化のことである。損失性符号化の目標とすると
ころは、元のデータから変わったとしても、その変化が
不快であったり目だったりしないようにすることであ
る。非損失性圧縮では、情報がすべて保存され、データ
は完全な復元が可能な方法で圧縮される。
【0004】非損失性圧縮では、入力シンボルもしくは
輝度データが出力符号語に変換される。入力としては、
画像データ、音声データ、1次元データ(例えば空間的
または時間的に変化するデータ)、2次元データ(例え
ば2つの空間軸方向に変化する(または1つの空間次元
と1つの時間次元で変化する)データ)、あるいは多次
元/マルチスペクトルのデータがあろう。圧縮がうまく
いけば、その符号語は、符号化前の入力シンボル(また
は輝度データ)のために必要とされたビット数より少な
いビット数で表現される。非損失性符号化法には、辞書
符号化方式(例えば、Lempel-Ziv 方式)、ランレング
ス符号化方式、計数符号化方式、エントロピー符号化方
式がある。非損失性の画像圧縮では、圧縮は予測または
コンテキストと符号化に基づいている。ファクシミリ圧
縮用JBIG規格と、連続階調画像用のDPCM(差分
パルス符号変調−JPEG規格のオプション)は画像用
の非損失性圧縮の例である。損失性圧縮では、入力シン
ボルまたは輝度データは、量子化されてから出力符号語
へ変換される。量子化は、データの重要な特徴量を保存
する一方、重要でない特徴量を除去することを目的とし
ている。損失性圧縮システムは、量子化に先立ち、エネ
ルギー集中をするための変換を利用することが多い。J
PEGは画像データ用の損失性符号化法の一例である。
【0005】画像信号処理における近年の開発は、効率
的かつ高精度のデータ圧縮符号化方式を追求することに
関心を集中してきた。変換またはピラミッド信号処理の
様々な方式が提案されており、その中に多重解像度ピラ
ミッド処理方式とウエーブレット(wavelet)ピラミッ
ド処理方式とがある。これら2方式はサブバンド処理方
式及び階層処理方式とも呼ばれる。画像データのウエー
ブレット・ピラミッド処理方式は、直交ミラーフィルタ
(QMF)を用いてオリジナル画像のサブバンド分解を
する特殊な多重解像度ピラミッド処理方式である。他の
非QMFウエーブレット方式もある。ウエーブレット処
理方式に関し、これ以上の情報を得るにはAntonini,
M.,et al.,”Image Coding Using Wavelet Tra
nsform”, IEEE Transactions on Image Processin
g,Vol.1,No.2,April1992、及びShapiro,
J.,”An Embedded Hierarchical Image CoderU
sing Zerotrees of Wavelet Coefficients”,Pro
c.IEEE DataCompression Conference,pgs.214-22
3,1993を参照されたい。また、可逆変換に関する情報
を得るには、Said,A.and Pearlman,W.”Revers
ibleImage Compression via Multiresolution Repr
esentation and PredictiveCoding”,Dept.of El
ectrical,Computer and System Engineering,Ren
ssealaer Polytechnic Institute,Troy,NY 1993
を参照されたい。
【0006】圧縮は、しばしば非常に時間がかかり、ま
た膨大なメモリを必要とする。より高速に、かつ/又
は、可能なかぎり少ないメモリで、圧縮を行うのが望ま
しい。品質を保証できない、圧縮率が不十分である、あ
るいはデータレートが制御可能でないという理由で、圧
縮を利用しなかった応用分野もある。しかし、伝送及び
/又は記憶すべき情報量を減らすため圧縮を利用するの
が望ましい。
【0007】従来技術に、自然連続階調画像を扱うため
の圧縮システムがある。その一例が、国際標準Dis.10
918-1,”Digital Compression and Coding ofCont
inuous-Tone Still Images”,CCITT勧告T.81で
あり、これは通常、JPEGと呼ばれる。従来技術に、
2値/ノイズフリー/浅画素深度画像を扱うための圧縮
システムもある。そのようなシステムの一例が、国際標
準ISO/IEC 11544,”Information Technology
-Coded Repersentation of Picture and Audio In
formation-Progressive Bi-level Image Compressi
on”,CCITT勧告T.82であり、これは通常、JBIG
と呼ばれる。しかしながら、従来技術には両方を適切に
処理するシステムがない。そのようなシステムがあると
望ましい。
【0008】パーサ(parser)はコンピュータ科学にお
いて周知である。パーサは、構造が初めは分かっていな
いオブジェクトの種々の部分に意義付けする役割があ
る。例えば、コンパイラの一部として動作するあるパー
サは、プログラム・ファイル中のある文字列が”識別
子”であり、別の文字列が予約語を構成し、また別の文
字列がコメントの部分であると決定するだろう。このパ
ーサは、文字列がどういう”意味”であるかを判定する
のではなく、対象のどういう種類の部分であるかを判断
するだけである。
【0009】ほとんどの画像記憶フォーマットは単一用
途のものである。すなわち、単一の解像度または単一の
品質レベルしか利用できない。他の画像フォーマットは
多用途が可能である。従来技術の多用途画像フォーマッ
トの中には、2つ又は3つの解像度/品質の選択肢をサ
ポートするものもあるが、解像度又は品質の一方しか指
定できず、両方は指定できないものもある。利用できる
解像度及び品質の選択肢を増加させることが望ましい。
【0010】例えば、インターネットのワールド・ワイ
ド・ウェブサーバーは、現在、大量のデータの中から必
要とされる情報を提供する。普通、ユーザは画面上で多
数の画像を閲覧し、いくつかを印刷することに決めるこ
とができる。しかし残念ながら、閲覧ツールの現状で
は、画像が主にモニタ用のものであると印刷出力の品質
がかなり悪くなってしまい、画像が主に印刷用のもので
あると閲覧時間が極端に長くなってしまう。”非損失
の”画像の取得は、不可能であるか、あるいは、全く独
自のダウンロードとしてなされねばならない。
【0011】
【発明が解決しようとする課題】本発明の一般的な目的
は、良好なエネルギー集中をもたらす変換を利用する損
失性及び非損失性のデータ圧縮システムを提供すること
にある。より具体的に述べれば、本発明の目的は、自然
連続階調の画像、2値/ノイズフリー/浅画素深度の画
像、及び、その両方の種類のデータを含む画像を適切に
処理できるデータ処理システムを提供すること、様々な
解像度/品質の画像フォーマットをサポートできるデー
タ圧縮システムを提供すること、並びに、画像出力装置
より与えられる装置特性に応じて装置依存の量子化を遂
行するパーサを含むデータ圧縮装置を提供することにあ
る。
【0012】
【課題を解決するための手段】請求項1乃至11の各項
記載の発明によるデータ圧縮システムは、可逆埋め込み
ウェーブレットにより画像データを圧縮するウェーブレ
ット方式のコーダ、バイナリ符号化スキームにより画像
データを圧縮するバイナリ方式のコーダ、及び、ウェー
ブレット方式又はバイナリ方式を選択するために接続さ
れた選択制御部からなる。請求項2記載の発明によれ
ば、ウェーブレット方式のコーダは可逆ウェーブレット
変換部、該可逆ウェーブレット変換部に接続された埋め
込み順序付け量子化器、及び、該埋め込み順序付け量子
化器に接続されたコンテキストモデルからなる。請求項
3記載の発明によれば、ウェーブレット方式のコーダは
エントロピー・コーダをさらに含む。請求項4記載の発
明によれば、ウェーブレット方式はグレイ符号化を実行
する。また、請求項5記載の発明によれば、ウェーブレ
ット方式とバイナリ方式は一つの符号化器を共有する。
請求項6記載の発明によれば、データ圧縮システムはエ
ントロピー・コーダをさらに含む。請求項7記載の発明
によればエントロピー・コーダは有限状態マシン・コー
ダからなり、請求項8記載の発明によれば、有限状態マ
シン・コーダはルックアップテーブルからなる。請求項
9記載の発明によればエントロピー・コーダはQコーダ
からなり、請求項10記載の発明によればエントロピー
・コーダはQMコーダからなり、請求項11記載の発明
によれば並列コーダからなる。
【0013】請求項12乃至19の各項記載の発明によ
るデータ圧縮システムは、可逆ウェーブレット変換部、
該可逆ウェーブレット変換部に接続された埋め込み順序
付け量子化器、該埋め込み順序付け量子化器に接続され
たコンテキストモデル、埋め込みバイナリ方式符号化機
構、及び該コンテキストモデル及び該埋め込みバイナリ
方式符号化機構に接続されたエントロピー・コーダを含
み、該可逆ウェーブレット変換、該埋め込み順序付け量
子化器及び該コンテキストモデルは可逆埋め込みウェー
ブレットにより画像データを圧縮するように動作可能で
あり、該バイナリ方式符号化機構はバイナリ符号化スキ
ームにより画像データを圧縮するように動作可能であ
り、さらに、当該システムはウェーブレット方式又はバ
イナリ方式を選択するために接続された選択制御部を含
む。請求項13記載の発明によればバイナリ方式はグレ
イ符号化を実行する。請求項14記載の発明によればエ
ントロピー・コーダは有限状態マシン・コーダからな
り、請求項15記載の発明によれば有限状態マシン・コ
ーダはルックアップテーブルからなる。請求項16記載
の発明によればエントロピー・コーダはQコーダからな
り、請求項17記載の発明によればエントロピー・コー
ダはQMコーダからなり、請求項18記載の発明によれ
ばエントロピー・コーダは並列コーダからなる。請求項
19記載の発明によれば、フォワード変換は可逆ウェー
ブレットからなる。
【0014】請求項20乃至26の各項記載の発明によ
るデータ圧縮システムは、ヒストグラム圧縮機構、該ヒ
ストグラム圧縮機構に接続された可逆ウェーブレット変
換部、該可逆ウェーブレット変換部に接続された埋め込
み順序付け量子化器、該埋め込み順序付け量子化器に接
続されたコンテキスト・モデリング機構、及び該コンテ
キスト・モデリング機構に接続されたコーダからなる。
請求項21記載の発明によればヒストグラム圧縮機構は
ブーリアンヒストグラムを作り、請求項22記載の発明
によればヒストグラム圧縮機構は整数値を画像データ中
の全ての可能な画素値に写像する。請求項23記載の発
明によれば、ヒストグラム圧縮機構で利用されたマッピ
ングを復号化器に通知するために接続された通知機構を
さらに含む。請求項24記載の発明によれば、マッピン
グは復号化器に受け取られた圧縮データに含まれるヘッ
ダで通知される。請求項25記載の発明によれば、ヘッ
ダ中の1つのビットが、それがセットされたときに、カ
レント・タイルのために別のヒストグラムが利用される
ことを復号化器に指示する。請求項26記載の発明によ
れば、復号化器は、値のダイナミックレンジと等しい、
ある数のビットを送ることによって通知され、該ある数
のビット中の各ビットはダイナミックレンジ内の対応し
た値が使われるときにセットされる。
【0015】請求項27乃至43の各項記載の発明によ
るデータ圧縮システムは、少なくとも1つのマーカーを
持つヘッダを有する符号ストリームを格納するメモリ、
少なくとも1つの出力装置、該メモリに接続され、か
つ、該少なくとも1つの出力装置より装置特性を受け取
るように接続されたパーサからなり、該パーサは装置依
存の量子化を実行するように動作可能である。請求項2
8記載の発明によれば、符号ストリームは非損失性圧縮
データからなり、請求項29記載の発明によれば、少な
くとも1つのマーカーは符号ストリーム中の各タイルの
ために用いられた成分の数、サブサンプリング及びアラ
インメントを示し、請求項30記載の発明によれば、符
号ストリームは主ヘッダを含み、符号ストリーム中の各
タイルの前にローカルヘッダが置かれる。請求項31記
載の発明によれば、主ヘッダは符号ストリーム中の全て
のタイルに適用され、各ローカルヘッダは関連したタイ
ルにのみ適用される、請求項32記載の発明によれば、
ローカルヘッダ中の少なくとも1つは主ヘッダに優先す
る。請求項33記載の発明によれば、パーサは符号スト
リーム中のマーカーを符号ストリームを量子化するため
に利用し、請求項34記載の発明によれば、マーカー中
の少なくとも1つは周波数情報を示す。請求項35記載
の発明によれば、データ圧縮システムは符号ストリーム
を生成するための圧縮装置をさらに含む。請求項36記
載の発明によれば、パーサは量子化選択装置からなり、
請求項37記載の発明によれば、量子化選択装置は画像
の集合の変換及び量子化を、様々な係数のビットプレー
ンを捨てることによって行う。請求項38記載の発明に
よれば、タグの1つは各タイル中のデータ内の重要性レ
ベルを示し、請求項39記載の発明によれば、タグは重
要性レベルロケータ信号を示し、該信号に従って該パー
サは打ち切りをする。請求項40記載の発明によれば、
タグは保存すべき重要性レベルの数を示し、請求項41
記載の発明によれば、タグは保存すべきバイトの数を示
す。請求項42記載の発明によれば、タグは重要性レベ
ルとバイト数を関連付ける指示を各タイルに含み、請求
項43記載の発明によれば、少なくとも1つのマーカー
は各タイル中の重要性レベルのバイト数を示す。
【0016】
【発明の実施の形態】圧縮及び伸長のための方法及び装
置について述べる。以下の本発明に関する詳細な説明に
おいて、本発明を完全に理解してもらうために、コーダ
の種類、ビット数、信号名等々、様々な具体例が示され
る。しかし、当業者には、そのような具体例によらずに
本発明を実施し得ることは明白になろう。他方、本発明
をいたずらに難解にしないため、周知の構造及びデバイ
スはブロック図の形式で表し、詳しくは示さない。
【0017】以下の詳細説明のかなりの部分は、コンピ
ュータメモリ内のデータビットに対する演算のアルゴリ
ズム及び記号表現によって与えられる。このようなアル
ゴリズム記述及び表現は、データ処理技術分野の当業者
によって、その研究の内容を他の当業者に対し最も効率
的に伝えるために用いられる手段である。あるアルゴリ
ズムがあり、それが概して、希望する結果に至る自己矛
盾のないステップ系列だと考えられるとしよう。これら
のステップは、物理量の物理的処理を必要とするもので
ある。必ずという訳ではないが、これらの物理量は記
憶、転送、結合、比較、その他処理が可能な電気的また
は磁気的信号の形をとるのが普通である。これらの信号
をビット、値、要素、記号、文字、用語、数字等で表わ
すのが、主に慣用上の理由から、時に都合がよいことが
分かっている。
【0018】しかしながら、このような用語は、適切な
物理量と関係付けられるべきであり、また、これら物理
量につけた便宜上のラベルに過ぎないということに留意
すべきである。以下の説明から明らかなように、特に断
わらない限り、”処理””演算””計算””判定””表
示”等々の用語を用いて論じることは、コンピュータシ
ステムのレジスタ及びメモリ内の物理的(電子的)な量
として表現されたデータを処理して、コンピュータシス
テムのメモリまたはレジスタ、同様の情報記憶装置、情
報伝送装置あるいは表示装置の内部の同様に物理量とし
て表現された他のデータへ変換する、コンピュータシス
テムあるいは同様の電子演算装置の作用及びプロセスを
指すものである。
【0019】本発明はまた、本明細書に述べる操作を実
行するための装置にも関係する。この装置は、要求目的
のために専用に作られてもよいし、あるいは、汎用コン
ピュータを内蔵プログラムにより選択的に駆動または再
構成したものでもよい。本明細書に提示されるアルゴリ
ズム及び表示は、本質的に、いかなる特定のコンピュー
タやその他装置とも関係がない。様々な汎用マシンを本
明細書に述べたところに従うプログラムで利用してもよ
いし、あるいは、必要な方法ステップの実行のためによ
り特化した装置を作るほうが好都合であるかもしれな
い。これら多様なマシンに要求される構造は以下の説明
より明らかになろう。さらに、本発明を説明するにあた
り、いかなる特定のプログラミング言語とも関連付けな
い。本明細書において述べるように、本発明の教えると
ころを実現するために多様なプログラミング言語を使用
してよいことが分かるであろう。
【0020】下記用語が以下の説明に用いられる。それ
ら各種用語にはすでに語義がある。しかし、規定された
語義は、それら用語が当該分野において知られている範
囲に限定して考えられるべきでない。これら語義は、本
発明の理解を手助けするために規定されたものである。
【0021】アラインメント(alignment):ある周波
数帯域内の変換係数の、他の周波数帯域に対するシフト
度合。
【0022】バイナリ符号化方式:2値、有限画素深度
の、又はノイズフリーのデータのための符号化の一方
式。一実施例にあっては、バイナリ符号化方式は画素の
グレイ(Gray)符号化と特有のコンテキスト・モデルから
なる。
【0023】ビット・シグニフィカンス(bit-signific
ance):符号(sign)絶対値表現に似た数表現で、ヘッ
ド(head)ビットの後に符号(sign)ビットが続き、さら
に、テール(tail)ビットがあれば、その後に続く。埋め
込み(embedding)は、この数表現に対しビットプレーン
順に符号化する。
【0024】コンテキスト・モデル:符号化しようとす
るカレント・ビットに関する原因として利用可能な情報
で、カレント・ビットに関する過去に学習した情報を提
供し、エントロピー符号化のための条件付確率予測を可
能にする。
【0025】埋め込み量子化:符号ストリームに包含さ
れる量子化。例えば、重要性レベルが、最高のレベルか
ら最低のレベルへと順に並べられているときには、符号
ストリームの単なる打ち切りによって量子化が行われ
る。タグ、マーカー、ポインタ、その他の信号によって
同じ作用を得ることができる。
【0026】エントロピー・コーダ:カレント・ビット
を、確率予測に基づいて符号化又は復号化する装置。
【0027】エントロピー・コーダは、本明細書では多
重コンテキスト・バイナリ・コーダとも呼ばれるであろ
う。カレント・ビットのコンテキストは”近傍”ビット
に関するいくつかの選ばれた配置であり、カレント・ビ
ット(1ビットまたは複数ビット)の最適表現のための
確率予測を可能にする。一実施例では、エントロピー・
コーダはバイナリ・コーダ又はハフマン・コーダを含
む。
【0028】固定長:データの特定ブロックを圧縮デー
タの特定ブロックへ変換する方式。例えばBTC(ブロ
ック打ち切り符号化)、VQ(ベクトル量子化)のいく
つかの方式。固定長符号は固定レート・固定サイズのア
プリケーションに適するが、レート・歪み性能は可変レ
ート方式に比べ劣ることが多い。
【0029】固定レート:ある一定の画素レートを維持
しなければならず、帯域幅の限定された通信路を持つア
プリケーション又は方式。この目的を成し遂げるには、
全体的に平均して圧縮するというよりも、局所的に平均
して圧縮することが必要である。例えば、MPEGは固
定レートを要求する。
【0030】固定サイズ:限られたサイズのバッファを
持つアプリケーション又は方式。この目的を成し遂げる
ため、全体的に平均した圧縮が達成される、例えば、印
刷バッファ。(アプリケーションは、固定レートでかつ
固定サイズのことも、そのどちらかのこともある。) 周波数帯域:各周波数帯域は、同じフィルタ処理系列に
よりもたらされる一群の係数を表す。
【0031】ヘッド・ビット:ビット・シグニフィカン
ス表現において、ヘッドビットとは、最上位ビッから最
初の非ゼロのビットまでの、該最初の非ゼロビットを含
めた絶対値ビットである。
【0032】水平コンテキストモデル:(一実施例で
は)埋め込みウエーブレット係数及びバイナリ・エント
ロピー・コーダのためのコンテキスト・モデル。
【0033】ベキ等:画像を損失性形式で伸長してから
同じ損失性符号語へ再圧縮することを可能にする符号
化。
【0034】画像タイル:それぞれが同一のパラメータ
を持つ、オーバーラップのない連続した部分画像の格子
の定義を可能にするため選ばれた矩形領域。画像タイル
は、ウエーブレット方式符号化において変換の計算のた
め必要になるバッファ・サイズに影響を及ぼす。画像タ
イルはランダムにアドレスできる。符号化操作は1画像
タイル中の画素及び係数データを処理用する。このた
め、画像タイルを乱順に構文解析又は復号化することが
できる。すなわち、画像タイルを、ランダムにアドレス
し、又は注目領域の伸長の様々な歪みレベルに応じて復
号化することができる。一実施例では、画像タイルは最
上部及び最下部のもの以外は全て同一サイズである。画
像タイルは、画像全体のサイズ以下の任意サイズにして
よい。
【0035】重要性レベル:特定の体系を定義すること
により、入力データ(画素データ、係数、誤差信号等)
は視覚的効果が同じ複数のグループに論理的に分類され
る。例えば、最上位の一つまたは複数のビットプレーン
は、多分、それより下位のビットプレーンより視覚的に
重要であろう。また、低い周波数の情報は一般に高い周
波数の情報より重要である。”視覚的重要性”の実用定
義の殆どは、後述のように本発明も含め、何らかの誤差
基準に関係している。しかし、それよりも良好な視覚的
尺度が、視覚的重要性の体系定義に組み入れられるかも
しれない。データの種類が異なれば視覚的重要性レベル
も異なる。例えば、音声データは音声の重要性レベルを
持つ。
【0036】オーバーラップ変換:単一のソース標本点
が同一周波数の複数の係数に寄与する変換。その例に、
多くのウエーブレットとオーバーラップ直交変換(Lapp
edOrthogonal Tansform)がある。
【0037】プログレッシブ:符号化データの一部から
矛盾のない伸長結果を得られ、かつデータを増やすこと
で精度を上げることができるように順序付けられた符号
ストリーム。データのビットプレーンが浅いほうから深
いほうへ順序付けられた符号ストリーム;この場合は、
普通、ウエーブレット係数データをさす。
【0038】プログレッシブ画素深度:データのビット
プレーンが浅いほうから深いほうへ順序付けられた符号
ストリーム。
【0039】プログレッシブ・ピラミッド:解像度が下
がる毎に大きさが2分の1(面積では4分の1)になる
解像度成分の連続。
【0040】可逆変換:一実施例では、圧縮結果を元に
復元できる、整数演算により実施される効率的変換。
【0041】S変換:1つの2タップ・ローパスフィル
タと1つの2タップ・ハイパスフィルタからなる特殊な
可逆ウエーブレットフィルタ対。
【0042】テール:ビット・シグニフィカンス表現
で、テール(tail)ビットとは最上位の非ゼロのビットよ
り下位の低い絶対値ビットである。
【0043】テール情報:一実施例では、ビット・シグ
ニフィカンス表現で表された係数のためにとり得る4つ
の状態。係数及びカレント・ビットプレーンの関数であ
り、水平コンテキスト・モデルのために利用される。
【0044】テール・オン(tail-on):一実施例では、
テール情報の状態がゼロか非ゼロであるかに依存した2
つの状態。水平コンテキスト・モデルのために利用され
る。
【0045】タイルデータ(tile data)セグメント:
一つの画像タイルを完全に記述する符号ストリームの部
分。一実施例においては、画像タイルの始まり(SO
T)を定義するタグから、次のSOTまで、又は画像の
終わり(EOI)のタグまでの全データ。
【0046】変換係数:ウエーブレット変換を適用した
結果。ウエーブレット変換においては、係数は対数分割
された周波数スケールを表す。
【0047】TS変換:2・6(Two-Six)変換。1つ
の2タップ・ローパス分析フィルタと1つの6タップ・
ハイパス分析フィルタからなる特殊な可逆ウエーブレッ
トフィルタ対。合成フィルタは、分析フィルタの直交ミ
ラー・フィルタである。
【0048】TT変換:2・10(Two-Ten)変換。1
つの2タップ・ローパス分析フィルタと1つの10タッ
プ・ハイパス分析フィルタからなる特殊な可逆ウエーブ
レットフィルタ対。合成フィルタは分析フィルタの直交
ミラー・フィルタである。
【0049】統合型(unified)非損失性/損失性:同
じ圧縮システムが、非損失性又は損失性の復元が可能な
符号データストリームを提供する。
【0050】ウエーブレット・フィルタ:ウエーブレッ
ト変換に使われるハイパスとローパスの合成フィルタ及
び分析フィルタ。
【0051】ウエーブレット変換:”周波数”及び”時
間(空間)”領域の両方の拘束条件を用いる変換。説明
する一実施例では、1つのハイパスフィルタと1つのロ
ーパスフィルタからなる変換である。結果として得られ
る係数は2:1の間引きを施され(臨界フィルタ処
理)、次にそれらフィルタがローパス係数にかけられ
る。
【0052】ウエーブレット・ツリー:最高レベルのウ
エーブレット分解のLL部内の単一の係数と関係付けら
れた係数群。係数の個数はレベル数の関数である。ウエ
ーブレット・ツリーのスパンは、分解レベル数に依存す
る。例えば、1レベル分解の場合には、ウエーブレット
・ツリーのスパンは4画素、2レベル分解では16画
素、等々である。
【0053】本発明の概要 本発明は、符号化部及び復号化部を持つ圧縮/伸長シス
テムを提供する。符号化部は入力データを符号化して圧
縮データを生成する働きをし、他方、復号化部は既に符
号化されたデータを復号化して元の入力データの再構成
データを生成する働きをする。入力データには、画像
(静止画像あるいは動画像)、音声等々の様々な種類の
データが含まれる。一実施例では、データはデジタル信
号データであるが、デジタル化したアナログデータ、テ
キストデータ形式、その他の形式も可能である。そのデ
ータのソースは、例えば符号化部及び/または復号化部
のためのメモリまたは通信路である。
【0054】本発明において、符号化部及び/または復
号化部の構成要素は、ハードウエア又はコンピュータシ
ステム上で利用されるソフトウエアによって実現し得
る。本発明は、非損失性の圧縮/伸長システムを提供す
る。本発明はまた、損失性の圧縮/伸長を実行するよう
にも構成し得る。本発明は、圧縮データの構文解析を、
伸長をすることなく実行するように構成し得る。
【0055】本発明のシステムの概要 本発明は、自然画像に見られる滑らかなエッジと平坦な
領域を非常に良好に表現する。本発明は、可逆埋め込み
ウエーブレットを利用して、画素深度の深い画像を圧縮
する。しかしながら、可逆埋め込みウエーブレット、他
のウエーブレット変換方式及びシヌソイド変換方式は、
テキストや図形画像に見られるシャープなエッジを表現
するのは得意ではない。この種の画像は、グレイ(Gra
y)符号化を行ってからJBIGのようなコンテキスト
・ベースのビットプレーン符号化を行うことにより良好
に圧縮できる。さらに、ノイズフリーのコンピュータ生
成画像は、バイナリ方式により良好にモデル化される。
【0056】本発明は、2値画像及び図形画像の圧縮の
ためのバイナリ方式を提供する。このバイナリ方式は、
ダイナミックレンジ全体を使わないある種の画像に対す
る圧縮も改善する。このバイナリ方式においては、本発
明は変換を使わないで画像のビットプレーンを符号化す
る。
【0057】図1は、バイナリ方式を採用した本発明の
圧縮システムの一実施例のブロック図である。なお、シ
ステムの復号化部は逆の順序で動作し、データフローも
同様である。図1において、入力画像101は多成分処
理機構111に入力される。この多成分処理機構111
は、オプションの色空間変換、及び、サブサンプリング
を施された画像成分に関するオプションの処理を提供す
る。方式選択機構110は、画像が連続階調画像か2値
画像か、あるいは、画像のどの部分がそのような特性を
持っているかを判定する。画像データは方式選択機構1
10へ送られ、方式選択機構110は、その画像データ
又はその部分をウエーブレット方式処理(ブロック10
2,103,105)又はバイナリ方式処理(ブロック
104)へ送る。本発明においては、どのモードを利用
するかの決定は、データに依存して決まる。一実施例で
は、方式選択機構110はマルチプレクサからなる。方
式選択機構110は、復号化動作中は利用されない。
【0058】ウエーブレット方式では、可逆ウエーブレ
ット変換ブロック102が可逆ウエーブレット変換を実
行する。同ブロック102の出力は係数の系列である。
埋め込み順序付け量子化ブロック103は、(可逆ウエ
ーブレット変換ブロック102により生成された)入力
画像101中の係数全部のアラインメントを生成するた
め、係数をビット・シグニフィカンス表現にしてからラ
ベル付けする。
【0059】画像データ101が受け取られ、そして
(適切な多成分処理の後)可逆ウエーブレット変換ブロ
ック102において後に説明されるように可逆ウエーブ
レットを利用して変換されることにより、画像の多重解
像度分解を表す係数の系列が生成される。本発明の可逆
ウエーブレット変換は、計算が複雑でない。この変換
は、ソフトウエア又はハードウエアにより、全く系統誤
差を生じさせないで実行できる。さらに、本発明のウエ
ーブレットはエネルギー集中及び圧縮性能に優れてい
る。これらの係数は埋め込み順序付け量子化ブロック1
03に受け取られる。
【0060】埋め込み順序付け量子化ブロック103
は、後述のように埋め込み順序付け量子化をする。その
結果は埋め込み(embedded)データストリームである。
この埋め込みデータストリームは、符号化時、伝送時又
は復号化時に、結果の符号ストリームの量子化を許す。
一実施例においては、埋め込み順序付け量子化ブロック
103は、係数を順序付けして符号・絶対値形式に変換
する。
【0061】埋め込みデータストリームは水平コンテキ
ストモデル・ブロック105に受け取られる。水平コン
テキストモデル・ブロック105は、埋め込みデータス
トリーム中のデータをその重要性に基づきモデル化する
(後述)。変換モードでは、”ビットプレーン”は変換
係数の重要性レベル・プレーンであり、水平コンテキス
トモデル・ブロック105はウエーブレット係数をビッ
ト・シグニフィカンス表現に整える。
【0062】順序付け及びモデリングの結果は、エント
ロピー・コーダ106により符号化すべきデシジョン(d
ecisions)(又はシンボル)である。一実施例では、全
てのデシジョンが一つのコーダへ送られる。他の実施例
では、デシジョンは重要性によってラベル付けされ、各
重要性レベルのデシジョンは別々の複数の(物理または
仮想)コーダによって処理される。ビットストリーム
は、エントロピー・コーダ106により重要性の順に符
号化される。一実施例では、エントロピー・コーダ10
6は1つ又は複数のバイナリ・エントロピー・コーダか
らなる。別の実施例では、ハフマン符号化が利用され
る。
【0063】バイナリ方式では、グレイ(Gray)符号化ブ
ロック104が入力画像101の画素に対しグレイ符号
化を行う。グレイ符号化は画素のビットプレーン間の相
関の一部を利用するビット操作である。それは、任意の
値xとx+1に対し、gray(x)とgray(x+1)は<その基数
2の表現で異なるのは1ビットだけであるからである。
一実施例では、グレー符号化ブロック104は8ビット
画素に対し点毎の変換、すなわち gray(x)=x XOR x/2 を実行する。本発明は、この形式のグレー符号化を利用
することに限定されるわけでも、8ビットのサイズの画
素を利用しなければならないわけでもない。しかし、上
記式を利用すると、ビットプレーン単位のプログレッシ
ブ伝送の場合のように、利用可能な最上位ビットの一部
だけで画素を再構成できるという利点がある。言い換え
ると、この形式のグレー符号化はビット・シグニフィカ
ンスの順序付けを保存する。
【0064】バイナリ方式では、グレイ符号化ブロック
104及びエントロピー・コーダ106を利用し、デー
タはビットプレーン毎に符号化される。一実施例では、
グレイ符号化ブロック104内のコンテキストモデル
は、カレント・ビットを、空間及び重要性レベル情報を
利用して条件付けする。
【0065】バイナリ方式の場合、グレイ符号化画素に
対しJBIGのようなコンテキストモデルが利用され
る。一実施例においては、画像タイルの各ビットプレー
ンは別々に符号化され、それぞれのビットは、周辺の1
0画素の値を利用し、ラスター順に条件付けされて符号
化される。図2はバイナリ方式における各ビットプレー
ンの各ビットのためのコンテキストモデルの幾何学的関
係を示す。このビットの条件付けは、固有パターン毎の
適応的確率予測をもたらす。なお、バイナリ・エントロ
ピー・コーダがグレイ符号化値のビットプレーン・エン
トロピー符号化に利用されるときには、いくつかのテン
プレートがバイナリ・エントロピー・コーダのコンテキ
ストモデルのために用いられてもよい。図3は29 個の
コンテキスト・ビン(bin)のための7画素と2ビットの
ビットプレーン情報を示す。
【0066】このコンテキストとカレント・ビットの値
を利用して、エントロピー・コーダ106はビットスト
リームを生成する。この同じバイナリ・エントロピー・
コーダ106が、変換モードとバイナリ方式の両方のデ
ータの符号化に利用される。一実施例では、エントロピ
ー・コーダ106はルックアップ・テーブルで実現され
る有限状態マシンからなる。なお、本発明は、Qコー
ダ、QMコーダ、高速並列コーダのような任意のバイナ
リ・エントロピー・コーダと一緒に利用し得る。
【0067】エントロピー・コーダ106はいずれの方
式についても同じものであり、かつ、バイナリ・コンテ
キストモデルは単純であるため、同一システムでバイナ
リ方式と変換方式を実現するのに、ごく僅かな追加資源
しか必要とされない。さらに、コンテキストモデルの構
成は異なるが、両モードのための必要資源は同じであ
る。すなわち、両方のモードで、コンテキスト格納のた
めに同じメモリを利用し、また、同じバイナリ・エント
ロピー・コーダを利用する。
【0068】本発明は、画像全体に対して実行されても
よいし、あるいは、より一般的であるが、画像のタイリ
ングされたセグメントに対して実行されてもよい。タイ
ルの中には、変換方式による方が圧縮が良好なものと、
バイナリ方式による方が良好なものとがある。使用すべ
きモードの選択アルゴリズムは様々なものが可能であ
る。タイルが利用されるときには、タイル単位のランダ
ムアクセスが可能である。また、注目領域は各別に高精
度に復号化することができる。最後に、変換方式とバイ
ナリ方式のいずれを選択するかは、1つ1つのタイル毎
に決定することができる。
【0069】また、画像は、本発明のデュアルモード・
システムを利用してもビットプレーンに関しプログレッ
シブであり、JBIGに教えられるように階層形式に符
号化し得ることに注意されたい。
【0070】復号化に関しては、タイルのヘッダ中の1
ビットを、データの符号化に利用された方式を指定する
ために利用してよい。方式選択機構110は用いられな
い。元のダイナミックレンジから低いダイナミックレン
ジへの非損失性マッピング、例えばヒストグラム圧縮
(後述)によるようなものが可能であれば、さらに役に
立つことがある。JBIGにおけるようなルック・アヘ
ッド(look ahead)を利用してもよい。このルック・ア
ヘッドは、JBIGにおけるような普通の予測又は決定
論的予測を使用してよい。
【0071】バイナリ方式又は変換方式の選択 方式選択機構110は、バイナリ方式と変換方式の選択
をする。一実施例では、入力画像は両方の方式で符号化
され、方式選択機構110は得られたビットレートが低
い方の方式を選択する(非損失性圧縮を仮定)。つま
り、よく圧縮する方のモードが選ばれる。この方法は、
コストが高いと思われるかもしれないが、それほどでは
ない。というのは、バイナリ方式と変換方式は共に、ソ
フトウエアが比較的高速であり、かつ、ハードウエアも
小規模であるからである。この方法から派生する方法
は、コーダをバイパスし、エントロピー値を利用して低
い方のビットレートを判定する方法である。
【0072】別の実施例においては、本発明は画像の画
素値の完全な(又は部分的な)ヒストグラム、又は、隣
接画素値のペア間の差分のヒストグラムを生成する。画
素値のヒストグラムの場合、そのヒストグラムのピーク
が、画素深度のダイナミックレンジより遥かに小さな値
で生じたならば、バイナリ方式を選ぶ、というようなデ
ータの統計的解析を使う。
【0073】一実施例では、本発明は隣接画素のペア間
の第1次差分の完全な(又は部分的な)ヒストグラムが
生成される。標準的な画像では、そのようなヒストグラ
ムは正にラプラシアン分布であり、ウエーブレット方式
が利用されよう。しかし、ヒストグラムがラプラシアン
分布のピークを持たないときには、バイナリ方式が利用
される。
【0074】両方の種類のヒストグラムを生成し、方式
の選択のために一緒に利用してもよい。
【0075】いずれも後述するが、TS変換又はTT変
換のdn フィルタ出力は第1次統計量に近い。これは、
変換が実行されヒストグラムが生成される方法を示唆す
る。そのヒストグラムに基づいて、方式が選択される。
その方式が変換方式のときには、システムは既に生成さ
れた変換係数を続けて処理する。バイナリ方式が選択さ
れると、変換係数は捨てられ(又は、画素がセーブされ
たか否かによっては逆変換され)、システムはバイナリ
方式を開始する。
【0076】別の実施例では、領域分割及び/又は文書
種類に関する以前の知識が、どちらの方式を選択すべき
の決定を支援するかもしれない。
【0077】もっとより長い符号化時間を利用できるな
らば、2方式の利点を最大にするようにタイリングのサ
イズを選ぶことができる。
【0078】なお、一実施例においては、本発明のシス
テムはバイナリ方式符号化を含まず、したがって、可逆
埋め込みウエーブレット圧縮(CREW)及び伸長だけ
を利用することに注意されたい。
【0079】ウエーブレット分解 本発明は、最初に、可逆ウエーブレットを利用して、
(画像データとしての)画像または他のデータ信号の分
解を実行する。本発明において、可逆ウエーブレット変
換は、整数係数を持つ信号の非損失性復元が可能な完全
再構成システムを整数演算で実現する。効率的な可逆変
換は、行列式が1(又はほぼ1)の変換行列によるもの
である。
【0080】本発明は、可逆ウエーブレットを利用する
ことにより、有限精度の演算で非損失性圧縮を提供する
ことができる。画像データに可逆ウエーブレット変換を
適用することにより生成される結果は、係数の系列であ
る。
【0081】本発明の可逆ウエーブレット変換は、フィ
ルタの集合を用いて実現し得る。一実施例では、そのフ
ィルタは1つの2タップ・ローパスフィルタと1つの6
タップ・ハイパスフィルタである。一実施例では、これ
らフィルタは加減算(とハードワイヤのビットシフト)
だけで実現される。
【0082】Hadamard変換を利用する本発明の一実施
例は、完全再構成システムである。
【0083】Hadamard変換に関する情報を得るには、
Anil K.Jain,”Fundamentals ofImage Process
ing”,P.155を読まれたい。Hadamard変換の逆変換
は、本明細書においてS変換と呼ばれる。
【0084】S変換は、一般添数nを用いて出力を次の
ように定義することができる。
【0085】
【数1】
【0086】なお、変換係数アドレッシングにおける因
数2は、暗黙の1/2サブサンプリングの結果である。
この変換は可逆であり、その逆変換は次の通りである。
【0087】
【数2】
【0088】記号
【0089】
【外1】
【0090】は、切り捨てて丸めること、つまり打ち切
りを意味し、床関数と呼ばれることがある。同様に、天
井関数
【0091】
【外2】
【0092】は最も近い整数へ切り上げて丸めることを
意味する。
【0093】完全再構成システムのもう一つの例は2・
6(TS)変換である。可逆TS変換は、ローパスとハ
イパスのフィルタの2つの出力に関する次の式により定
義される。
【0094】
【数3】
【0095】TS変換は可逆であり、その逆変換は次の
通りである。
【0096】
【数4】
【0097】ここで、次式によりp(n)がまず計算さ
れなければならない。
【0098】
【数5】
【0099】ローパスフィルタからの結果を、ハイパス
フィルタにおいて2度(第1項と第2項で)利用でき
る。したがって、ほかに2つの加算を行うだけで、ハイ
パスフィルタの結果を得られる。
【0100】完全再構成システムのもう一つの例は2・
10(TT)変換である。可逆TT変換は、ローパスと
ハイパスのフィルタの2つの出力に関する次式により定
義される。
【0101】
【数6】
【0102】このd(n)の式はs(n)を使って単純
化することができる(さらに、64による整数除算は、
分子に32を足すことにより丸めることができる)。こ
れにより次式が得られる。
【0103】
【数7】
【0104】このTT変換は可逆であり、その逆変換は
次式である。
【0105】
【数8】
【0106】ここで、p(n)は次式によりまず計算さ
れなければならない。
【0107】
【数9】
【0108】TS変換とTT変換のいずれにおいても、
S変換と同様、ローパスフィルタは、入力信号x(n)の
レンジが出力信号s(n)のレンジと同じになるように作
られる。すなわち、平滑出力の増大はまったくない。入
力信号がbビットの深さのときには、出力信号もbビッ
トの深さである。例えば、信号が8ビット画像の場合、
ローパスフィルタの出力も8ビットである。このこと
は、例えばローパスフィルタを連続して適用することに
より平滑出力がさらに分解されるピラミッド・システム
のために重要な特性である。従来技術のシステムにおい
ては、出力信号のレンジが入力信号のレンジより大き
く、このことがフィルタの連続的適用を困難にしてい
る。また、変換を整数演算で行う際の丸めによる系統誤
差がないので、損失性システムの全ての誤差を量子化に
より制御可能である。さらに、ローパスフィルタは、2
つのタップしか持たないため、非オーバーラップ・フィ
ルタになる。この特性は、ハードウエア化のために重要
である。
【0109】一実施例では、3と22による乗算は、図
22に示すようなシフトと加算により実現される。図2
2において、s(n)入力は乗算器1501に接続され、
乗算器1501はs(n)入力に2を乗じる。一実施例で
は、この乗算は、s(n)信号のビットの1桁左シフトと
して実現される。乗算器1501の出力は加算器150
2によりs(n)信号と加算される。加算器1502の出
力は、3s(n)信号である。加算器1502の出力はま
た、乗算器1503により2を乗じられる。乗算器15
03は、1桁左シフトとして実現される。乗算器150
3の出力は加算器1505により乗算器1504の出力
と加算され、乗算器1504はs(n)信号を4桁左シフ
トにより16倍する。加算器1505の出力は22s
(n)信号である。
【0110】フィルタに対する厳格な可逆性要件は、次
のことに着目することによって緩和することができる。
ハイパス係数は、ある順序で符号化されて復号化され
る。前に復号化されたハイパス係数に対応する画素値
は、正確に分かっているので、カレント・ハイパスフィ
ルタ処理に用いることができる。
【0111】TS変換及びTT変換は非オーバーラップ
のローパス合成フィルタとハイパス分析フィルタを有す
る。ハイパス合成フィルタとローパス分析フィルタだけ
がオーバーラップ・フィルタである。
【0112】TSフィルタは、タイル境界に関し良好な
特性を有する。タイルのサイズがツリーのサイズの倍数
である場合を考える。そして、画像がタイルに分割され
る場合に生じるような、ある信号の一部に対する変換の
適用を考察する。ローパス分析フィルタはオーバーラッ
プ・フィルタではないので、ローパス係数はタイリング
による影響を受けない。すなわち、信号のその部分が均
一個数の信号を持つ場合、そのローパス係数は信号全体
を変換したときのそれと同じである。
【0113】復号化中に、量子化のためハイパス係数が
存在せず、画像がSS係数だけを使って最高圧縮率で再
構成される場合には、タイル境界にまたがってローパス
合成フィルタが使われてよく、逆変換はローパス係数を
用いて信号全体について実行される。SS係数のタイリ
ングによって変化しないので、解はタイリングが利用さ
れないときと全く同じである。これにより、信号の一部
分に対しフォワード変換を実行することにより生じるア
ーティファクト(artifacts)が除去される。
【0114】復号化中に、ハイパス係数が存在する(し
かし、ハイパス係数はそれらの値が幾分の不確定性を持
つように量子化されている)場合には、オーバーラップ
1Dローパス分析フィルタ演算がある境界を横切って別
の部分へ入る場所の標本に対し次のことを行うことがで
きる。タイル境界を横切らない標本について、実際に利
用されたフィルタに基づき、可能な最小及び最大の再構
成値が決定される。その標本に関し、ローパス係数(と
ローパスフィルタ)だけを用い、そしてタイル境界を横
切ることによって、そうであったであろう再構成値(す
なわちオーバーラップ予測値)が決定される。そのオー
バーラップ予測値が可能な最小と最大の再構成値の間
(それらの値も含む)であれば、そのオーバーラップ予
測値が用いられる。そうでなければ、その可能な最大と
最小の再構成値のうちの、オーバーラップ予測値に近い
方の値が用いられる。こうすることによって、信号の断
片に対しフォワード変換を実行することにより生じるア
ーティファクトを減らす。
【0115】1Dフィルタ演算が実行される度に再構成
値が選ばれる。これが正しく行われると、各ハイパス係
数はちょうど一つの有効な再構成値が与えられ、選択に
より誤差を変換の複数レベルに伝搬し得なくなる。
【0116】非線形画像モデル 本発明の一実施例は、TS変換又はTT変換のような線
形フィルタの可逆近似であるウエーブレット・フィルタ
を利用する。一実施例では、可逆非線形フィルタが用い
られるかもしれない。TS変換及びTT変換に類似した
非線形フィルタの一種は次のとおりである。
【0117】
【数10】
【0118】その逆変換はTS変換及びTT変換の場合
と同じであるが、ただしp(n)は次の通りである。
【0119】
【数11】
【0120】この実施例において、q(n)は平滑(smoot
h)係数(及び必要なら前の詳細(detail)係数)からのx
(2n)-x(2n+1)に関する予測である。この予測は非線形
画像モデルを利用する。一実施例では、非線形画像モデ
ルはHuber-Markov確率場である。この非線形画像モデ
ルは、フォーワード変換と逆変換sにおいて全く同一で
ある。反復画像モデルの場合、反復の回数と次数は同一
である。
【0121】非線形画像モデルの一例は次の通りであ
る。ある一定の反復回数の場合に、それぞれの値(画素
又はローパス係数)x(k)は新たな値x'(k)に調整され
る(ただし、kは2n又は2n+1である)。任意の反
復回数を用いてよいが、一実施例では3回の繰り返しが
用いられる。最終の反復からq(n)の値が求まる。
【0122】
【数12】
【0123】反復の度に、各x(k)に対する変化y(k)が
計算される。
【0124】
【数13】
【0125】ここでAは変化率であり、これは任意の正
値でよい。一実施例ではA=1である。Biは差分検出
子である。例えば、1次元の場合、Biは次の通りであ
る。
【0126】
【数14】
【0127】2次元の場合、水平、垂直、及び2つの対
角線方向の差分を検出するための4つのBi値があろ
う。Biとして他の差分演算子を用いてもよい。
【0128】
【数15】
【0129】ここで、Tは閾値であり、これは任意の正
値でよい。Tは画像のエッジを構成する差分を表す。一
実施例では、T=8である。
【0130】x'(2n)+x'(2n+1)=x(2n)+x(2n+
1)の拘束条件のもとに、値x'(2n),x'(2n+1)のペ
アは変化y(2n),y(2n+1)のペアによって調整され
る。これは、変化y(2n),y(2n+1)を結合して単一の
変化y'(2n)、つまり、両変化にサポートされる最大の
変化にすることによって達成される。
【0131】y(n)とy(2n+1)が両方とも正か負のとき
には、 y'(sn)=0 である。そうでない場合、|y(2n)|<|y(2n+1)|な
らば、 y'(2n)=y(2n) であり、そうでなければ y'(sn)=−y(2n+1) である。そして x'(2n)=x(2n)+y'(2n) x'(2n+1)=x(2n+1)−y'(2n) である。Huber−Markov確率場に関するこれ以上の情
報を得るには、R.R.Schultz and R.L.Steven
son,”Improved definition imageexpansion”,Pro
ceedings of IEEE International Conference on Ac
oust.,Speech and Signal Processing,vol.III,
pp.173-176,San Fransisco,March 1992 を見られ
たい。
【0132】いくつかの実施例では、変換は1次元から
2次元へ拡張されるが、その拡張のためにまずq(n)=
0として各次元に対し別々に変換を行う。次に、画像モ
デルの同様の適用によってLH,HL,HH値のための
3つのq(n)値を計算する。
【0133】2次元ウエーブレット分解 本発明のローパスフィルタ及びハイパスフィルタを用い
て、多重解像度分解が行なわれる。分解レベル数は可変
であり任意数でよいが、現在のところ分解レベル数は2
レベル乃至5レベルである。最大レベル数は、log2
(長さ又は幅の最大値)である。
【0134】画像のような2次元データに対し変換を実
行する最も普通のやり方は、1次元フィルタを別々に適
用する方法、つまり、行に沿って適用したのち列に沿っ
て適用するという方法である。第1レベルの分解により
4つの異なった係数バンドが得られ、これら係数バンド
は本明細書ではLL,HL,LH,HHと呼ぶ。これら
文字は、前に定義した平滑(smooth)フィルタと詳細(det
ail)フィルタの適用を意味するロー(L)とハイ(H)
を表す。したがって、LLバンドは行方向及び列方向の
平滑フィルタより得られた係数からなっている。ウエー
ブレット係数を図4乃至図7のような形に配置するのが
一般的なやりかたである。
【0135】ウエーブレット分解の各周波数サブバンド
はさらに分解することができる。最も普通のやりかたは
LLサブブロックだけをさらに分解する方法であり、こ
れは各分解レベルのLL周波数サブバンドが生成された
時にそれをさらに分解することを含むであろう。このよ
うな多重分解はピラミッド分解と呼ばれる(図4乃至図
7)。記号LL,LH,HL,HHと分解レベル番号に
よって各分解を示す。なお、本発明のTSフィルタ、T
Tフィルタのいずれによっても、ピラミッド分解は係数
サイズを増加させない。
【0136】例えば、可逆ウエーブレット変換が再帰的
に1つの画像に適用されると、第1レベルの分解は最も
細かいディテールもしくは解像度に対し作用する。第1
分解レベルで、画像は4つのサブ画像(すなわちサブバ
ンド)に分解される。各サブバンドは、1つの空間周波
数帯域を表わしている。第1レベルのサブバンドはLL
0,LH0,HL0,HH0と表される。元の画像を分解す
るプロセスは、水平,垂直の両次元における1/2サブ
サンプリングを含むので、図4に示されるように、第1
レベルのサブバンドLL0,LH0,HL0,HH0はそれ
ぞれ、入力が持っていた画像の画素(または係数)の個
数の4分の1の個数の係数を持つ。
【0137】サブバンドLL0は、水平方向の低い周波
数情報と垂直方向の低い周波数情報を同時に含んでい
る。一般に、画像エネルギーの大部分は当該サブバンド
に集中している。サブバンドLH0は、水平方向の低い
周波数情報と垂直方向の高い周波数情報(例えば水平方
向エッジの情報)を含んでいる。サブバンドHL0は、
水平方向の高い周波数情報と垂直方向の低い周波数情報
(例えば垂直方向エッジの情報)を含んでいる。サブバ
ンドHH0は、水平方向の高い周波数情報と垂直方向の
高い周波数情報(例えばテクスチャ又は斜めエッジの情
報)を含んでいる。
【0138】この後に続く第2、第3、第4の下位分解
レベルはそれぞれ、前レベルの低周波数LLサブバンド
を分解することによって作られる。第1レベルの当該サ
ブバンドLL0が分解されることによって、図5に示す
ように、やや精細な第2レベルのサブバンドLL1,L
H1,HL1,HH1が作られる。同様に、サブバンドL
L1が分割されることによって、図6に示すように、精
細度の粗い第3レベルのサブバンドLL2,LH2,HL
2,HH2が生成される。また、図7に示すように、サブ
バンドLL2が分割されることにより、精細度がより粗
い第4レベルのサブバンドLL3,LH3,HL3,HH3
が作られる。2:1のサブサンプリングにより、第2レ
ベルの各サブバンドは、原画像の16分の1の大きさで
ある。このレベルの各標本(つまり画素)は、原画像中
の同一位置のやや細いディテールを表す。同様に、第3
レベルの各サブバンドは、原画像の64分の1の大きさ
である。第3レベルでの各画素は、原画像中の同一位置
のかなり粗いディテールを表す。また、第4レベルの各
サブバンドは原画像の256分の1の大きさである。
【0139】分解画像はサブサンプリングのため原画像
より物理的に小さいので、原画像の格納のために使用さ
れたメモリを利用して、分解サブバンド全部を格納でき
る。つまり、3レベル分割の場合、原画像と分解サブバ
ンドLL0,LL1は捨てられ、保存されない。
【0140】4つのサブバンド分解レベルだけを示した
が、個々のシステムの要件に応じて、それ以上のレベル
を生成することも可能である。また、DCTのような他
の変換又は一次元配置のサブバンドによって、様々な親
子関係を定義してもよい。
【0141】ピラミッド分解 ウエーブレット分解の各周波数サブバンドはさらに分解
することができる。一実施例においては、LL周波数サ
ブバンドだけが分解される。本明細書では、このような
分解はピラミッド分解と呼ばれる。記号LL,LH,H
L,HHと分解レベル番号で各分解を表示する。なお、
本発明のウエーブレット・フィルタによれば、ピラミッ
ド分解は係数サイズを増大させない。
【0142】別の実施例では、LLに加えて他のサブバ
ンドも分解されるかもしれない。以下の説明におい
て、”LL”なる用語は”SS”(”L”=”S”)と
入れ替えて用いてよい。同様に、”H”なる用語も”
D”と入れ替えて用いてもよい。
【0143】ウエーブレットのツリー構造 ピラミッド分解のウエーブレット係数には自然で有用な
ツリー構造がある。なお、LL周波数サブブロックは最
終の分解レベルに対応したただ一つしかない。これに対
し、LH,HL,HHのバンドはレベル数と同数存在す
る。このツリー構造により、ある周波数帯域内の係数の
親は、それより低い解像度の同じ周波数帯域内の係数で
あり、かつ同じ空間位置関係にあることが明らかにな
る。
【0144】各ツリーのルートは、純粋に平滑な係数で
ある。画像のような2次元の信号の場合、ツリーのルー
トは3つの”子”を持ち、ほかのノードはそれぞれ4つ
の子を持つ。この階層的ツリーは2次元信号に限定され
ない。例えば、1次元信号の場合、ルートは1つの子を
持ち、ルート以外のノードはそれぞれ2つの子を持つ。
これ以上高い次元は、1次元の場合及び2次元の場合よ
り導かれる。
【0145】図8は連続した2レベル間の親子関係を表
している。図8において、Aの係数は、B,C,Dに対
する直接の親であるが、B,C,Dを親とする係数(E
とH,FとI,GとJ)に対する親でもある。例えば、
Bは、E付近の4係数、H付近の16係数、等々に対す
る親である。
【0146】多重解像度分解のプロセスは、フィルタ系
列を使って遂行し得る。
【0147】1次元の模範的フィルタを使って実現され
る1次元2レベル変換の例については、米国特許出願第
08/498,695号(1995年6月30日受
理、”Method and Apparatus For Compression Us
ing Reversible WaveletTransforms and an Embedd
ed Codestream”)及び米国特許出願第08/498,
036号(1995年6月30日受理”Reversible W
avelet Transformand Embedded Code-stream Manip
ulation”)を見られたい。
【0148】フォワード・ウエーブレット変換の実行 本発明では、水平方向の1−D(次元)パス、次で垂直
方向の1−Dパスによってウエーブレット変換が実行さ
れる。レベル数で反復回数が決まる。図9は前に定義し
たようなフォワードTT変換フィルタを使う4レベル分
解を表す。
【0149】別の実施例では、任意のレベルの水平又は
垂直のウエーブレット変換の任意の時点のTT変換の代
わりに、S変換のような別の可逆ウエーブレット変換フ
ィルタを用いることができる。一実施例では、水平方向
と垂直方向の両方にTT変換を利用して4レベル分解が
実行される。一実施例では、4レベル分解において、4
つのTT変換の中の2つがS変換で置き換えられる。こ
れは圧縮の損失は少ないが、メモリ使用量に対する効果
は大きい。水平方向の変換と垂直方向の変換は交互に適
用されるであろう。
【0150】なお、S変換とTT変換の組合せが水平方
向及び垂直方向の変換を実施するために用いられてもよ
い。変換の順序は雑多でよいが、完全に可逆的であるた
めには、復号化器はその順序を知って逆の順序で逆操作
を実行しなければならない。後述のように、復号化器は
変換順序をヘッダで知らされるかもしれない。
【0151】埋め込み順序付け 本発明では、ウエーブレット分解の結果として生成され
た係数はエントロピー符号化される。本発明において
は、係数は最初に埋め込み符号化(embeddedcoding)を
施されるが、この符号化では、視覚的に重要な順に係数
が順序付けられ、または、より一般的に、何等かの誤差
規準(例えば、歪み規準)を考慮して係数が順序付けら
れる。誤差または歪みの規準には、ピーク誤差と平均2
乗誤差(MSE)が含まれる。また、ビット・シグニフ
ィカンス空間配置(bit-significance spatial locatio
n)より、データベース照会のための妥当性を優先させ
るように、また方向別に(垂直、水平、斜め等)順序付
けてもよい。
【0152】データの順序付けは、符号ストリームの埋
め込み量子化したものを生成するために行われる。本発
明においては、2つの順序付け方法が用いられる。その
一つは係数を順序付けするためのものであり、もう一つ
は係数中の2進値を順序付けするためのものである。本
発明の順序付けは、ビットストリームを生成し、このビ
ットストリームはその後にバイナリ・エントロピー・コ
ーダにより符号化される。
【0153】タイル 本発明においては、変換と符号化の前に、画像はタイル
に分割される。タイルは、完全独立に符号化される全体
画像の部分画像であり、図11のように番号がつけられ
た画像上に配置された規則的な矩形格子により定義され
る。右端と下端のタイルは、原画像及びタイル・サイズ
に応じて色々なサイズになる。
【0154】タイルは画像サイズ以下の任意の高さ、幅
にしてよいが、タイル・サイズの選び方は性能に影響す
る。小さなタイル、特にラスタ順画像の垂直方向の寸法
が小さいタイルは、作業域用メモりを減らすことができ
る。しかし、タイルが小さすぎると、合図のための(si
gnaling)オーバーヘッド、タイル境界での変換効率の
損失、エントロピー・コーダの立ち上がり適応という3
つの要因により圧縮効率が下がる。タイルの寸法を、最
も低い周波数成分の大きさの倍数(CREWツリー)、
つまりレベル数の関数(2のレベル数乗)にするのが有
利である。原画像のサイズによるが、128×128又
は256×256のタイルが多くのアプリケーションに
適当と思われる。
【0155】タイルは一連の画像の圧縮のために利用さ
れるかもしれない。したがって、タイルされた画像は、
時間的に異なる画像(映画のような)又は空間的に異な
る画像(MRIの如き3D断面のような)かもしれな
い。これを知らせる格別の方法はないが、CMTが利用
されるかもしれない。
【0156】変換、コンテキスト・モデル、エントロピ
ー符号化は1つの画像タイルの画素及び係数だけに作用
する。それゆえに、画像タイルは順序によらずに解析又
は復号化することができ、すなわちランダムにアドレス
することができ、あるいは、注目領域の伸長のため様々
な歪みレベルに復号化することができる。
【0157】1つの画像タイルの画素データは全部、符
号化器で一度に利用できる、例えばメモリにバッファさ
れる。ひとたび画素データが変換されれば、全ての係数
データを水平コンテキスト・モデルに利用できる。全て
の係数をランダムにアクセスできるので、画像タイル内
部の埋め込みの順序は、符号化器及び復号化器が知って
いる限り任意でよい。エントロピー・コーダは、この順
序付けに関し無頓着であるから、その順序は圧縮率に大
きな影響を及ぼすので注意して選ばねばならない。
【0158】画像タイルは矩形配置されたツリー(LL
係数及びその全ての子孫)の番号により定義される。各
ツリー内の画素の数はウエーブレット分解のレベル数の
関数である。
【0159】画像基準格子は、各成分の大きさが格子点
の整数倍である最小の格子面である。このことは、殆ど
の画像で、画像基準格子が最頻成分と同一であることを
暗に意味する。
【0160】1成分の画像又は全成分が同一サイズの画
像の場合、画像基準格子は画像と同一サイズである(例
えば格子点は画像の画素である)。複数の成分の全部が
同一サイズというわけではない画像の場合、そのサイズ
は画像基準格子点の整数倍と定義される。例えば、CC
IR601 YCrCb色成分系は、各Cr及びCb成分に対し
2つのY成分を持つように定義される。したがって、Y
成分は画像基準格子を定義し、Cr成分とCb成分はそれ
ぞれ水平方向に2単位を、垂直方向に1単位をカバーす
る。
【0161】ビット・シグニフィカンス表現 一実施例では、係数内の2進値に対し用いられる埋め込
み順序はビットプレーン順である。係数はビット・シグ
ニフィカンス表現で表される。ビット・シグニフィカン
ス表現は、最上位ビット(MSB)ではなくて符号(si
gn)ビットが、最初の非ゼロの絶対値ビットと共に符号
化される符号・絶対値表現である。
【0162】ビット・シグニフィカンス形式で表現され
る数には3種類のビット、すなわちヘッド(head)ビッ
ト、テール(tail)ビット及び符号(sign)ビットがある。
ヘッドビットとは、MSBから最初の非ゼロ絶対値ビッ
トまでの全てのゼロビットと、その最初の非ゼロ絶対値
ビットである。その最初の非ゼロ絶対値ビットが存在す
るビットプレーンで、係数の重要性が定まる。最初の非
ゼロ絶対値ビットの後からLSBまでのビットがテール
ビットである。符号ビットは符号(sign)を表わすにすぎ
ない。MSBが非ゼロビットの数、例えば±2n は、ヘ
ッドビットを1ビットしか持たない。ゼロの係数は、テ
ールビットも符号ビットも持たない。図12にビット・
シグニフィカンス表現の例を示す。
【0163】画素の輝度に関連して起こるような、値が
非負整数の場合、採用し得る順序はビットプレーン順
(例えば、最上位ビットプレーンから最下位ビットプレ
ーンへの順)である。2の補数による負整数も許容され
る実施例では、符号ビットの埋め込み順序は、整数の絶
対値の最初の非ゼロビットと同じである。したがって、
1つの非ゼロビットが符号化されるまで、符号ビットは
考慮されない。例えば、符号・絶対値表記法によれば、
−7の16ビット数は 1000000000000111 である。ビットプレーン・ベースで、初めの12デシジ
ョン(decision)は”無意味”すなわちゼロとなる。最
初の1のビットは13番目のデシジョンに見つかる。次
に符号ビット(”負”)が符号化される。符号ビットが
符号化された後、テールビットが処理される。14番目
と15番目のデシジョンは共に”1”である。
【0164】係数は最上位のビットプレーンから最下位
のビットプレーンへと符号化されるので、データのビッ
トプレーン数が正確にわからなければならない。本発明
においては、データから計算される、又は画像の深度及
びフィルタ係数から導き出される係数値の絶対値の上限
を見つけることによって、ビットプレーン数が決定され
る。例えば、その上限が149のときには、有意な8ビ
ットつまり8つのビットプレーンがある。ソフトウエア
の速度のため、ビットプレーン符号化は用いられないか
もしれない。別の実施例では、ビットプレーンが符号化
されるのは、係数が2進数として意味をなす時だけであ
る。
【0165】係数アラインメント(alignment) 本発明は、ビットプレーン符号化の前に係数相互のアラ
インメントを行う。これは、FFTやDCTと同様、異
なった周波数サブバンド内の係数は異なった周波数を表
すからである。本発明は、係数のアラインメントを行う
ことにより量子化を可能にする。量子化の重さが小さい
係数ほど早いビットプレーン側へアラインメントされる
(例えば左へシフトされる)。よって、ストリームが打
ち切りされる場合、これらの係数は、それを定義するビ
ットが、より重く量子化された係数に比べ多くなる。
【0166】一実施例では、係数はSNR又はMSEの
見地から最高のレート・歪み性能が得られるようにアラ
インメントがなされる。MSEのような統計的誤差基準
から見てほぼ最適のアラインメントを含め、多くのアラ
インメントが可能である。あるいは、アラインメントは
係数データの物理視覚的(physchovisual)量子化を許す
かもしれない。アラインメントは画像品質に(換言すれ
ばレート・歪み曲線に)相当な影響を及ぼすが、非損失
性システムの最終的な圧縮率には殆ど影響しない。他の
アラインメントは、特殊な量子化である注目領域忠実度
符号化や解像度プログレッシブアラインメントに対応す
るかもしれない。
【0167】アラインメントは、圧縮データのヘッダで
通知されるかもしれない。係数はビット・シグニフィカ
ンス順に符号化されるが、最上位の重要性レベルは符号
化単位中の係数から導き出される。各係数の符号ビット
は、その係数が非ゼロの絶対値ビットを持つ最も上位の
重要性レベルまで符号化されない。これは、絶対値がゼ
ロの係数の符号ビットを符号化しないという利点があ
る。また、符号ビットは、埋め込み符号ストリーム中の
それが関連する点まで符号化されない。様々なサイズの
係数に関するアラインメントは、符号化器及び復号化器
のいずれも分かっているので、エントロピー・コーダの
効率に全く影響を与えない。
【0168】bビット/画素の画像の2レベルのTS変
換及びTT変換分解における係数のビット深度を図13
に示す。図14は、本発明における係数アラインメント
に用いられる周波数帯域用乗数の例である。係数のアラ
インメントのために、1-HH係数のサイズが基準として用
いられ、このサイズに対し相対的にシフトが与えられ
る。
【0169】一実施例では、画像中の全ての係数のアラ
インメントを生成するため、係数は最大の係数の絶対値
を考えてシフトされる。アラインメント後の係数は、次
に、重要性レベルと呼ばれるビットプレーン単位で、最
上位の重要性レベル(MSIL)より最下位の重要性レ
ベル(LSIL)へと処理される。符号(sign)ビット
は、MSILの一部ではないので、各係数の最後のヘッ
ドビットまで符号化されない。重要なことは、アライン
メントはエントロピー・コーダへビットが送られる順序
を制御するに過ぎないことである。割増の0のビットの
パッディング、シフト、格納、符号化が実際に行われる
わけではない。
【0170】表1はアラインメントの例を示す。
【0171】
【表1】
【0172】様々なサイズの係数に関するアラインメン
トは、符号化器と復号化器の両方に分かっているので、
エントロピー・コーダの効率にはまったく影響を与えな
い。
【0173】同じデータセットの符号化単位が異なった
アラインメントを持っても構わないことに注意された
い。
【0174】符号ストリームの順序付け 図15は、符号化ストリームの順序付けと符号化単位内
における順序付けを示している。図15において、ヘッ
ダ1001の後に、符号化単位1002が最も上の帯域
より最も下の帯域へと順に続く。符号化単位の内部で
は、LL係数1003は符号化されずにラスター(ライ
ン)順に格納される。LL係数の後に、重要性レベル
が、1ビットプレーンずつ、最上位のビットプレーンか
ら最下位のビットプレーンへと順にエントロピー符号化
される。この時、すべての係数の第1ビットプレーンが
符号化され、次に第2ビットプレーンが符号化され、以
下同様に符号化される。一実施例では、アラインメント
はヘッダ1001中に指定される。
【0175】一実施例では、LL係数は、それが8ビッ
ト値のときは、符号化されずにラスター順に格納される
にすぎない。LL係数のサイズが8ビット未満のときに
は、LL係数はパッディングにより8ビットにされる。
LL係数が8ビットより長いときには、LL係数は次の
ように格納される。まず、各係数の最上位の8ビットが
符号化されずラスター順に格納される。次に、係数の残
りの下位ビットはパックされてラスター順に格納され
る。例えば、10ビットのLL係数の場合、4個のLL
係数の最下位ビットは1バイトにパックされる。このよ
うにして、実際の画像の深度にかかわらず、係数毎に8
ビットのLLデータを得られるので、簡略画像もしくは
プレビュー画像の素早い生成が可能になる。
【0176】各ビットプレーン期間内に係数が処理され
る順序は、低い解像度より高い解像度へ、かつ低い周波
数より高い周波数への順である。各ビットプレーン内の
係数サブバンドの順序は、高いレベル(低解像度、低周
波数)より低いレベル(高分解能、高周波数)への順で
ある。各周波数サブバンドの内部において、符号化はあ
る決まった順序でなされる。一実施例では、その順序は
ラスター順、2×2ブロック順、ジグザグ順、Peanoス
キャン順、等々である。
【0177】図15の符号ストリームを用いる4レベル
分解の場合、その順序は次のとおりである。 4-LL,4-HL,4-LH,4-HH,3-HL,3-LH,3-HH,2-HL,2-LH,2-HH,
1-HL,1-LH,1-HH 。
【0178】符号ストリーム・データを重要性によって
分けると、データを媒体に格納したり、ノイズのある通
信路により伝送するのに有利である。データの異なった
部分に、異なった冗長度を持つ誤り訂正/検出符号を用
いることができる。最も高い冗長度の符号をLL係数の
ヘッダに用いることができる。(重要度を基準にして)
重要性の低いエントロピー符号化データは、冗長度の低
い誤り訂正/検出符号を用いることができる。訂正不可
能な誤りが生じたときには、データのパケットを廃棄
(量子化)すべきか、または、通信路より再送信すべき
か、もしくは記憶装置から再読みだしすべきかを決定す
るために、そのデータの重要性レベルも利用できる。例
えば、高冗長度の誤り訂正BCH符号(Reed-Solomon
符号など)が、ヘッダデータ、LLデータ、エントロピ
ー符号化データの最も重要な4分の1のために用いられ
るかもしれない。エントロピー符号化データの残りの4
分の3は、低冗長度の誤り検出チェックサム又はCRC
(巡回冗長検査)によって保護されるであろう。一実施
例では、BCH符号を用いるパケットは常に再送信され
て廃棄されず、一方、チェックサム又はCRC符号を持
つパケットは再送信されず、データの送信を試みて失敗
した後に廃棄されるであろう。
【0179】一実施例においては、ヘッダデータがデー
タの各部分に使用される誤り訂正/検出符号を指定す
る。言い換えれば、ヘッダ中の情報が、誤り訂正符号を
切り替えるべき時点を指示する。一実施例では、誤り訂
正/検出符号は、通信路に利用されるパケット間で、又
は記憶媒体に利用されるブロック間で変更されるだけで
ある。
【0180】図26は、ヘッダ1901の後に符号化さ
れないLL係数(1902)とエントロピー符号化デー
タ1903が埋め込み順に続く符号ストリームを示す。
図示のように、ヘッダ1901とLL係数1902は最
高冗長度の符号を使用するが、エントロピー符号化デー
タ1903は最低冗長度の符号を使用する。本発明は、
最高の冗長度から最低の冗長度までの多くの異なった符
号が使用されるスライディングスケールを採用すること
もできる。
【0181】水平コンテキストモデル 本発明に利用される水平コンテキストモデルの一実施例
を以下に説明する。このモデルは、係数の空間及びスペ
クトル従属性に基づいて符号化単位内のビットを利用す
る。隣接した係数及び親係数の利用可能な2進値を、コ
ンテキストを生成するために使用してもよい。しかし、
コンテキストはデコーダビリティを左右し、また、多少
は効率的適応に影響を及ぼす。
【0182】水平コンテキストモデルによる係数のモデ
リング 本発明は、バイナリ・エントロピー・コーダのための埋
め込みビット・シグニフィカンス順の係数により生成さ
れた符号ストリームをモデル化するためのコンテキスト
・モデルを提供する。一実施例では、コンテキスト・モ
デルはランレングス・カウント(count)、空間モデ
ル、符号(sign)ビット・モデル、テールビット・モデ
ルからなる。ランレングス・カウントは、同じ状態のビ
ットのランを測定する。空間モデルは、ヘッドビットに
関する近傍係数及び親係数の情報を含んでいる。
【0183】図16は、符号化単位の全ての係数の隣接
係数を表す。図16において、隣接係数は分かりやすい
地理的表記法で表されている(例えば、N=北、NE=
北東、等々)。ある係数、例えば図16のPと、カレン
ト・ビットプレーンが与えられたとすると、コンテキス
トモデルは、そのビットプレーンより前の符号化単位全
てから得られるどの情報も利用することができる。本コ
ンテキストモデルの場合、注目係数の親係数も利用され
る。
【0184】水平ヘッドビット・コンテキストモデル ヘッドビットは、最も圧縮できるデータである。したが
って、圧縮率を上げるため、大量のコンテキストもしく
は条件付けが使われる。隣接係数又は親係数の値を注目
係数の注目ビットに対するコンテキストを決定するため
に利用するというよりもむしろ、その情報は本明細書に
おいてテール情報と呼ぶ2ビットにまとめられる。この
情報は、メモリに格納されてもよいし、隣接係数又は親
係数から動的に計算されてもよい。テール情報は、最初
の非ゼロの絶対値ビットがすでに見つかったか否か(例
えば最初の”オン”ビットがすでに見つかったか否か)
を示し、そして、すでに見つかっているならば、幾つ前
のビットプレーンであったかを示す。表2はテール情報
ビットの説明である。
【0185】
【表2】
【0186】この2ビットのテール情報から、そのテー
ル情報がゼロか否かを示す1ビットの”テール・オン”
ビットが合成される。一実施例では、テール情報とテー
ル・オンビットは係数が符号化された直後に更新され
る。別の実施例では、その更新は、並列的コンテキスト
生成を可能にするため、もっと後に行われる。
【0187】さらに、この2ビットは、符号化される重
要性レベルを示すために利用される。最初の2ビットプ
レーンは値0、第2の2ビットプレーンは値1、第3の
2ビットプレーンは値2、残りのビットプレーンは値3
を使用する。さらに、すべてゼロのヘッドビットのラン
レングス符号化がある。
【0188】ヘッドビットのための10ビットのコンテ
キストは、親係数及びW係数それぞれの2ビット情報、
N,E,SW,S各係数の1ビット情報、2ビットの重
要性レベル情報からなる。
【0189】一実施例では、一部又は全ての周波数帯域
についてテール情報は用いられない。こうすることによ
り、周波数帯域を、その親を前もって復号化すねことな
く復号化できるようになる。
【0190】別の実施例では、各周波数帯域のビットプ
レーンの重要性レベルへの割り当てに、一つのアライン
メントを用いる。親のテール・オン情報の決定に、もう
一つのアラインメントを利用するが、これが利用する親
のビットプレーンは実際に符号化されているビットプレ
ーンより少ない。これにより、ある周波数帯域のいくつ
かのビットプレーンが、同じ重要性レベルの対応した親
ビットプレーンを復号化せずに復号化できるようになる
(図51参照)。例えば、MSEアラインメントに基づ
いた親のテール・オン情報によらず、ピラミッド・アラ
インメントにより画像を符号化できる(図50参照)。
これにより、復号化器は、MSE アラインメントを模
擬し、又はピラミッド・アラインメントとMSEアライ
ンメントの間の任意のアラインメントを模擬し、ピラミ
ッド・アラインメントで復号化することができる。
【0191】図29はコンテキスト従属関係を示す。子
はその親に条件付けられる。したがって、親は、その子
を復号化する前に復号化されなければならない、特に符
号化時に用いたアラインメントと異なるアラインメント
を用いて復号化する時にはそうである。
【0192】水平符号(sign)ビット・コンテキストモデ
ル 最後のヘッドビットの後で、符号ビットが符号化され
る。符号のコンテキストは、N係数が正であるか負であ
るか、符号がまだ符号化されていないかによって、3つ
存在する。
【0193】水平テールビット・コンテキストモデル テールビットのためのコンテキストは、注目係数のテー
ル情報の値によって3つ存在する。(テールビットを符
号化しようとしているときには、テール情報値は1,2
又は3に限られることに注意されたい) 水平コンテキストモデルのためのステップ システムのコンテキストモデルは、コンテキストを記述
するために最高11ビットを使う。この数がまるまる指
定されなくともよい。各ビット位置の意味は、前の2進
値に依存する。まず第1に、ヘッドビットのある”ラン
符号化”を提供するために、ただ1つのコンテキストが
用いられる。ヘッドビットのランがないとにきは、各ビ
ットは、あるコンテキストに寄与する隣接係数及び親係
数により符号化される。ステップの具体例は以下のとお
りである。
【0194】1)ルックアヘッド(look-ahead)をすべ
きか判定する。 次のN個の係数とそれらの北側に隣接する係数のテール
情報がすべてゼロならば、システムはステップ2に進
む。そうでなければ、次のN個の係数のためステップ3
に進む。一実施例では、N=16である。
【0195】2)ルックアヘッド手順を行う。 次のN個の係数の符号化すべきカレント・ビットプレー
ンのビットがゼロならば、1つの0が符号化され、シス
テムはステップ1から次のN係数に移行する。そうでな
ければ、1つの1が符号化され、システムは次のN係数
のためステップ3に進む。
【0196】3)注目係数の状態を判定し符号化する。 注目係数のテール情報が0ならば、注目係数のカレント
・ビットプレーンのビットは、西の係数と親係数(オプ
ション)のテール情報の2ビット、北西、東、南西、南
の係数のテールオンビット、及び重要性レベル情報の2
ビットにより作られる1024個の可能なコンテキスト
により符号化され、システムはステップ4に進む。な
お、一実施例では、親係数は利用されないため、コンテ
キストは隣接係数と重要性レベル情報だけから作られ
る。注目係数のテール情報が0でなければ、注目係数の
カレント・ビットプレーンのビットはテールビットであ
り、注目係数のテール情報の2ビットから作られる3つ
のコンテキストにより符号化される。
【0197】4)カレント・ヘッドビットの状態を判定
し、必要なら符号(sign)ビットを符号化する。 注目係数のカレント・ビットプレーンのビットが1なら
ば、注目係数の符号(sign)は、北係数のテールオンビ
ット及び符号ビットにより作られる3つの可能なコンテ
キストにより符号化される。
【0198】図17は前述のプロセスのフローチャート
である。図17において、白いブロックは符号化と関係
がなく、黒いブロックは符号化に関係がある。図に示さ
ないが、各エントロピー符号化デシジョン(decision)
に対し1つのコンテキストが定義される。前述の作用及
びフローは、当業者には理解できるであろう。
【0199】水平コンテキストモデルの一例が、入力係
数を符号/絶対値形式に変換する符号/絶対値ユニット
の一例とともに、米国特許出願第08/498,695
号(1995年6月30日受理、”Method and Appar
atus For CompressionUsing Reversible Wavelet
Transforms and an Embedded Codestream”)、及
び、米国特許出願第08/498,036号(1995
年6月30日受理、”Reversible Wavelet Transfor
m and Embedded CodestreamManipulation")に記述
されている。
【0200】エントロピー符号化 一実施例では、本発明により実施されるエントロピー符
号化は、バイナリ・エントロピー・コーダによって実行
される。一実施例では、エントロピー・コーダ106は
Qコーダ、QMコーダ、有限状態マシン、又は高速並列
コーダ等からなる。単一のコーダを用いて単一の出力符
号ストリームを生成してもよい。あるいは、複数の(物
理又は仮想)コーダを用い、複数の(物理又は仮想)デ
ータストリームを生成してもよい。
【0201】一実施例では、本発明のバイナリ・エント
ロピー・コーダはQコーダからなる。Qコーダに関する
情報を得るには、Pennebaker,W.B.,et al.,”A
nOverview of the Basic Principles of the Q-cod
er Adaptive BinaryArithmetic,”IBM Journal of
Research and Development,Vol.32,pg.717-26,19
88 を読まれたい。別の実施例では、バイナリ・エント
ロピー・コーダは、周知の効率的なバイナリ・エントロ
ピー・コーダであるQMコーダを用いる。QMコーダ
は、確率スキューが非常に高いビットに対し特に効率的
である。QMコーダはJPEG規格とJBIG規格の両
方で利用される。
【0202】バイナリ・エントロピー・コーダは、有限
状態マシン(FSM)コーダでもよい。このようなコー
ダは、確率及び事象(outcome)から圧縮ビットストリー
ムへの単純な変換を提供する。一実施例では、有限状態
マシン・コーダは、符号化器、復号化器の両方として、
テーブルルックアップにより実現される。多様な確率予
測法を、このような有限状態マシンコーダに利用でき
る。0.5に近い確率に対する圧縮率が非常によい。大
きくスキューした確率に対する圧縮率は、用いられるル
ックアップテーブルのサイズに依存する。QMコーダと
同様、有限状態マシン・コーダは、デシジョンが発生順
に符号化されるので、埋め込みビットストリームに有効
である。出力はルックアップテーブルにより決められる
ので、”キャリーオーバー”(carry over)問題が起こる
心配は全くない。実際には、QコーダやQMコーダと違
って、符号化と圧縮出力ビットの生成との間に最大の遅
延がある。一実施例では、本発明の有限状態マシン・コ
ーダは、1993年12月21日発行の米国特許第5,
272,478号”Method and Apparatus forEntro
py Coding”に述べられているBコーダからなる。
【0203】一実施例では、本発明のバイナリ・エント
ロピー・コーダは高速並列コーダからなる。QMコーダ
もFSMコーダも、1ビットずつ符号化又は復号化され
る必要がある。高速並列コーダは、数ビットを並列に処
理する。一実施例では、高速並列コーダは、圧縮性能を
犠牲にすることなく、VLSIハードウエア又はマルチ
プロセッサ・コンピュータで実現される。本発明におい
て利用し得る高速並列コーダの一例が、1995年1月
10日発行の米国特許第5,381,145号”Metho
d and Apparatus for Parallel Decoding and Enco
ding of Data”に述べられている。
【0204】殆どの効率的なバイナリ・エントロピー・
コーダは、基本フィードバックループによって速度が制
限される。考えられる一解決法は、入力データストリー
ムを複数のストリームに分割して並列の複数の符号化器
に与えることである。それら符号化器の出力は、複数の
可変長符号化データ・ストリームである。この種の方法
の一つの課題は、データを単一のチャンネルでどのよう
にして伝送するかである。米国特許第5,381,14
5号に述べられている高速並列コーダは、この課題を、
それら符号化データストリームをインターリーブする方
法によって解決する。
【0205】本発明において利用されるコンテキストの
多くは定確率であり、このことがBコーダのような有限
状態マシン・コーダを特に有効なものにする。なお、シ
ステムが0.5に近い確率を利用する場合、上記特許に
開示された高速並列コーダ及び有限状態マシン・コーダ
は共にQコーダより効率よく動作する。よって、それら
両方のコーダは、本発明のコンテキストモデルに対し本
質的な圧縮上の強みを持っている。
【0206】別の実施例では、バイナリ・エントロピー
・コーダ及び高速m元コーダの両方が利用される。高速
m元コーダはハフマン・コーダでよい。
【0207】本発明の符号化及び復号化のプロセス 図18乃至図20のフローチャートは、本発明の符号化
プロセス及び復号化プロセスの例を表している。処理ロ
ジックは、ソフトウエア及び/又はハードウエアによっ
て実現してよい。
【0208】図18は本発明の符号化プロセスの一例を
示す。図18において、符号化プロセスの最初で、処理
ロジックが1タイル分の入力データを取得する(処理ブ
ロック1201)。
【0209】処理ロジックは次に、バイナリ符号化を実
行しなければならないか判定する(処理ブロック120
2)。バイナリ符号化を実行すべきときには、プロセス
は処理ブロック1211に進み、処理ロジックは入力デ
ータに対しGray符号化を実行し、そして各係数の各
ビットをバイナリ方式コンテキストモデルによりモデル
化する(処理ブロック1212)。処理は処理ブロック
1208へ進む。
【0210】バイナリ符号化を実行する必要がなけれ
ば、プロセスは処理ブロック1203へ進み、処理ロジ
ックはデータに可逆フィルタをかける。可逆フィルタを
かけた後、処理ロジックは別の分解レベルが必要か判定
する(処理ブロック1204)。別の分解レベルが必要
ならば、処理ロジックはLL係数に可逆フィルタをかけ
(処理ブロック1205)、そして処理は処理ブロック
1204へ戻り再び判定を行う。別の分解レベルが必要
でないならば、プロセスは処理ブロック1206へ進
み、処理ロジックは係数を符号・絶対値形式へ変換す
る。それから、処理ロジックは各係数の各ビットを水平
コンテキストモデルによりモデル化し(処理ブロック1
207)、プロセスは処理ブロック1208へ進む。
【0211】処理ブロック1208で、処理ロジックは
各係数の各ビットを符号化する。そして、処理ブロック
は各符号化データを送信又は格納する(処理ブロック1
209)。
【0212】処理ブロックは、次に、画像中に他にもタ
イルが使われているか判定する(処理ブロック121
0)。画像中に他のタイルがあるならば、処理ロジック
は処理ブロック1201へループバックし処理が繰り返
されるが、他のタイルがなければプロセスは終了する。
【0213】図19は、本発明の復号化プロセスの一例
を示す。図19において、プロセスはまず1タイル分の
符号化データを取得する(処理ブロック1301)。次
に、処理ロジックはその符号化データをエントロピー復
号化する(処理ブロック1302)。そして、処理ロジ
ックは、そのデータがバイナリ復号化されなければなら
ないか判定する(処理ブロック1203)。そのデータ
がビット毎にバイナリ復号化されなければならないとき
には、プロセスは処理ブロック1311へ進み、処理ロ
ジックは各係数の各ビットをバイナリ方式コンテキスト
モデルによりモデル化し、そして、そのデータに対し逆
Gray符号化を施す(処理ブロック1312)。この
逆グレイ符号化の後、プロセスは処理ブロック1309
へ進む。
【0214】バイナリ復号化が実行される必要がないと
きには、プロセスは処理ブロック1304へ進み、処理
ロジックは各係数の各ビットを水平コンテキストモデル
によりモデル化する。そして、処理ロジックは各係数を
フィルタ処理に適した形式へ変換し(処理ブロック13
05)、係数に可逆フィルタをかける(処理ブロック1
306)。
【0215】可逆フィルタをかけた後、処理ロジックは
別のレベルの分解があるか判定する(処理ブロック13
07)。別レベルの分解があるならば、プロセスは処理
ブロック1308へ進み、処理ロジックは係数に可逆フ
ィルタをかけ、そしてプロセスは処理ブロック1307
へループバックする。別の分解レベルが必要でなけれ
ば、プロセスは処理ブロック1309へ進み、再構成さ
れたデータは送信されるか格納される。
【0216】次に、処理ロジックは画像中に他にタイル
があるか判定する(処理ブロック1310)。画像中に
ほかにタイルがあるときには、処理は処理ブロック13
01へループバックして処理が繰り返されが、他にタイ
ルがなければ、プロセスは終了する。
【0217】図20は本発明によるビット・モデル化の
ためのプロセスの一例を示す。図20において、ビット
・モデル化プロセスは初めに係数変数Cを最初の係数に
設定する(処理ブロック1401)。つぎに、|c|>
S の判定を行う(処理ブロック1402)。判定結果
がyesのときには、処理は処理ブロック1403に進
み、処理ロジックはテールビット用モデルを用いて係数
CのビットSを符号化し、そして処理ブロック1408
に処理が進む。このテールビット用モデルは静的(非適
応型)モデルでかまわない。|c|が2S より大きくな
いときには、処理は処理ブロック1404に進み、処理
ロジックはテンプレートをヘッドビット(頭の0と最初
の”1”ビット)に適用する。テンプレートを適用した
後、処理ロジックは係数CのビットSを符号化する(処
理ブロック1405)。可能なテンプレートを図21に
示す。
【0218】次に、係数CのビットSがオンであるか判
定する(処理ブロック1406)。係数CのビットSが
オンでなければ、処理ブロック1408へ進む。一方、
係数CのビットSがオンならば、処理は処理ブロック1
407に進み、処理ロジックは符号(sign)ビットを符号
化する。そして処理は処理ブロック1408へ進む。
【0219】処理ブロック1408で、係数Cが最後の
係数であるか判定する。係数Cが最後の係数でなけれ
ば、処理は処理ブロック1409に進み、係数変数Cは
次の係数に設定され、そして処理ブロック1402から
処理を続ける。一方、係数Cが最後の係数ならば、処理
ブロック1410に進み、Sが最後のビットプレーンで
あるか判定する。Sが最後のビットプレーンでなけれ
ば、ビットプレーン変数Sが1だけデクリメントされ
(処理ブロック1411)、処理ブロック1401から
処理を続ける。Sが最後のビットプレーンならば、処理
は終了する。
【0220】TS変換設計 本発明は、一実施例において、バッファメモリ内の適所
においてTS変換を計算する。これを行う際、計算値を
再配置するためのメモリの余分なライン及び余分な時間
は必要とされない。TS変換については既に述べたが、
本発明は、臨界サンプリングしたものに対しオーバーラ
ップ変換を適用する。別の実施例では、TT変換が用い
られる。
【0221】図24(A)乃至図24(C)は、本発明
の変換の計算中に本発明により採用されるメモリ操作方
法を示す。図24(A)はメモリの初期状態を示す。図
24(A)において、メモリの最初の行には、前の値(n
-1)の平滑("S")係数及び詳細("D")係数(計算済
み)、カレント値(n)の平滑("S")係数及び部分的に
完成した詳細係数("B")が、4つの入力標本("X")の
値(X2n+2,X2n+2,X2n+4,X2n+5)とともに入って
いる。変換計算の中間結果は、図24(B)の同じメモ
リ行に示されている。この行の変更点は、第5記憶エレ
メント及び第6記憶エレメントにおいて、X2n+2とX2n
+3の値がSn+1とBn+1の値に置き換わったことだけであ
ることに注意されたい。このように、もはや必要でない
格納値を変換計算中に生成された結果によって置き換え
ることにより、本発明はメモリスペースを節約する。図
24(C)は変換が完了し詳細出力Dn を生成後におけ
る同じメモリ行を示す。図24(B)から唯一変わった
点は部分的に完成した詳細係数Bn が詳細出力Dn で置
き換わったことである。
【0222】nに関し詳細出力が計算された後、変換計
算プロセスは、詳細出力Dn+1を計算するために行を下
げて計算を続ける。
【0223】次に示すコード例を、変換を行うため用い
てよい。フォワード変換とリバース変換のための水平コ
ードが含まれていることに注意されたい。
【0224】以下において、変数sooはSn-1値を指
し、変数osoはSn値を指し、変数oosはSn+1を指
す。
【0225】フォワードTS変換の一例のためのコード
(C言語)の具体例は以下の通りである。 /* TSFoword_1() */ void TSForward_1(long *x,int width) { long *start=x; long *ox=x+2; long soo; long oso; long oos; oso=(*x+*(x+1))>>1; oos=(*ox+*(ox+1))>>1; soo=oos; *(x+1)=*x-*(x+1); *x=oso; while((ox+2)-start<width){ x=ox; os+=2; soo=oso; oso=oos; oos=(*ox+*(ox+1))>>1; *(x+1)=*x-*(x+1)+((oos-soo+2)>>2); *x=oso; } x=ox; soo=oso; oso=oos; oos-soo; *(x+1)=*x-*(x+1); *x=oso; } 。
【0226】インバースTS変換の一例のためのコード
(C言語)の具体例は以下のとおりである。 /* TSReverse_1() */ void TSReverse_1(long *x,int width) { long *start=x; long *d=x+1; long ns=*(x+1); long P; while(x+2-start<width){ p=*d-((*(x+2)-ns+2)>>2); ns=*x; *d=*x-(P>>1); *x+=((p+1)>>1); x+=2; d=x+1; } p=*d; *d=*x-(p>>1); *x=((p+1)>>1); 。
【0227】1次元の例のみ示したが、本発明は多次元
及び多レベルにも利用し得る。なお、この手法は、他の
計算のためにもはや必要でなくなった値を部分的又は最
終的結果により1対1に置き換える任意のオーバーラッ
プ変換に利用できる。
【0228】図25は、3レベル用のメモリバッフアの
2次元表現を示す。図25において、各ブロック180
1〜1804のメモリロケーションには係数値が入って
いる。すなわち、ブロック1801〜1804のそれぞ
れは、係数値の8×8ブロックである。
【0229】係数は、2の自然数乗の間隔で配置され
る。レベルと、S又はDのオフセットが与えられれば、
どの係数もアクセスできる。それゆえに、特定のレベル
と水平及び垂直周波数を選択することによって、アクセ
スをすることができる。バッファはラスター順にアクセ
スされてもよい。
【0230】ユニット・バッファ構成 本発明の一実施例においては、単一のバッファで圧縮シ
ステムの変換ブロック、コンテキストモデル・ブロッ
ク、符号化ブロックをサポートする。このバッファは、
係数を効率的にアクセスでき他にメモりを必要としない
2次元のスクローリング・メモリバッファである。バッ
ファの各ラインはライン・アクセス・バッファに格納さ
れたポインタを介してアクセスされる。図23(A)及
び図23(B)は、このスクローリング・バッファの構
成を示し、ライン・アクセス・バッファ1601にバッ
ファ1602の各ラインを指すポインタが入っている。
【0231】スクロールは、ライン・アクセス・バッフ
ァに格納されるポインタを並べ直すことによりなされ
る。その例が図23(A)及び図23(B)に示されて
いる。図23(A)はバッファの初期状態を示す。図2
3(B)を見るに、ラインA,B,Cがバッフアから取
り除かれ、ラインG,H,Iによってそれぞれで置き換
えられた後に、バッファにスクローリング・バッファの
作用を付与するため、ライン・アクセス・バッファのポ
インタは、第1のポインタがバッファ内のラインDを指
し、第2のポインタがラインEを指し、第3のポインタ
がラインFを指すように変更される。次に、ラインG,
H,Iを指すポインタがライン・アクセス・バッファの
最後の3つの位置を占める。なお、6ラインのバッファ
を持つことに本発明が限定されるわけではなく、これは
あくまで一例として用いられるにすぎない。もっとライ
ン数の多いバッファが一般的に使用されるが、これは当
業者には周知であろう。しかして、ライン・アクセス・
バッファ経由のアクセスは、記憶を物理的に移動させる
ことなく、ユニット・バッファがスクロールするような
外観を呈する。これにより、スピードを犠牲にせずに、
最小限のメモリを使用できるようになる。
【0232】本発明においては、そのようなユニット・
バッファを用いることにより、常に画像の1つの帯域の
みメモリに記憶しつつ、画像全体に対するオーバーラッ
プ変換の適用をサポートする。これを達成するため、少
なくとも1バンドのウェーブレット・ユニットを構成す
るウエーブレット係数のセットを完全に計算するために
必要な数分の画像のラインに対してだけウエーブレット
変換を適用する。このような場合には、計算の完了した
ウェーブレット係数のセットを、モデル化し、エントロ
ピー符号化し、そしてウエーブレット・ユニット・バッ
ファの該当部分より取り除くことができる。計算が未完
のウエーブレット係数は、次の反復で計算を完了させる
ために、そのまま残る。そして、ライン・ポインタを並
べ替えることによりウェーブレット・ユニット・バッフ
ァをスクロールし、ウェーブレット・ユニット・バッフ
ァの空き部分にほかのデータを入れることができる。こ
れで、計算途中のウェーブレット係数を完全に計算する
ことができる。
【0233】一例として、ハイパスフィルタがカレント
係数及び次のローパスフィルタ係数に依存するオーバー
ラップ変換を適用することを考える。この例の場合、た
った2レベルの分解が画像データに適用されるであろう
が、これは1つのウエーブレット・ユニットが4エレメ
ント長であることを暗に示す。
【0234】少なくとも1つの帯域のウエーブレット・
ユニットを構成するウエーブレット係数のセットを完全
に計算するために、ウエーブレット・ユニット・バッフ
ァの高さは少なくとも8ラインつまり2ウェーブレット
・ユニットである。
【0235】2次元のウェーブレット・ユニット・バッ
ファに対しウェーブレット変換を適用する際には、まず
1次元のウェーブレット変換がバッファの各行(ライ
ン)に対し適用される。それから、1次元のウェーブレ
ット変換がバッファの各列に対し適用される。
【0236】ウェーブレット・ユニット・バッファの各
列に対し1次元ウェーブレット変換を適用する時に、ユ
ニット・バッファに格納されていない画像のエレメント
に依存する各列の最後のエレメントについては、ハイパ
スフィルタの計算を部分的にしか終わらせることができ
ない。これが図55に示されている。
【0237】第2レベルのウェーブレット分解を実行す
る時に、再び、各列の最後のエレメントについては、ハ
イパスフィルタの計算を部分的にしか終わらせることが
できない。これが図56に示されている。
【0238】なお、一実施例においては、多くの分解レ
ベルを利用する時に、SS係数(第2分解レベルの場合
は図55の1SS、第3レベルの場合は図56の2S
S)にのみウェーブレット変換が適用されるだろう。こ
のような場合、ユニット・バッファの行及び列のロケー
ションは、バッファの適切なエントリーの読み書きを保
証するようスキップされるだろう。
【0239】この例では、バッファの上半分には計算が
完了したウェーブレット係数のセットが入っており、こ
のウェーブレット係数セットは1帯域のウェーブレット
・ユニットを構成しており、モデル化し、エントロピー
符号化し、そしてバッファから取り除くことができる。
【0240】バッファの上半分が空くと、バッファを高
さの半分だけスクロースすることができる。ここで、画
像の次の4ラインをバッファに読み込むことができる。
バッファに格納された新たなラインそれぞれに対し、1
次元ウェーブレット変換を適用することができる。バッ
ファの列方向に、部分的に計算された係数を完全に計算
することができるが、再び、各列の最後のエレメントは
部分的にしか計算することができない。
【0241】第2レベルのウェーブレット分解のために
も同様のことが行われる。再び、バッファの上半分は計
算の完了したウェーブレット係数が入り、その段階でプ
ロセスはほかに処理すべき画像のラインがなくなるまで
反復する。
【0242】ライン・アクセス・バッファ内のライン・
ポインタの並べ替えは、様々なやり方で行うことができ
る。一つのやり方は、新しいライン・アクセス・バッフ
ァを作り、それに旧ライン・アクセス・バッファからポ
インタをコピーする方法である。ウェーブレット・ユニ
ット・バッファの高さを法としてスクロールするために
は、旧ライン・アクセス・バッファのエレメントiに格
納されているポインタが、インデックス(i+ライン
数)にコピーされることになろう。
【0243】なお、圧縮システムの3つのステージは、
バッファ内のデータに対し、そのデータがバッファより
出される前に遂行されるので、係数は一般的に様々に順
序つけられること留意すべきである。ラスター順データ
操作が行われる場合には、本発明のスクロール・バッフ
ァは最小限のメモリで間に合う。
【0244】ソフトウエア(及び/又はハードウエア)
によりライン・アクセス・バッファを管理してポインタ
を操作する。このソフトウエアも、バッファ内のどのデ
ータが処理を完了しバッファから出してよいか知ってい
る。
【0245】アラインメント法 本発明は、係数値を左へ任意量だけシフトする。一実施
例では、このアラインメントは、仮想的アラインメント
法によって行われる。この仮想的アラインメント法は、
係数を実際にシフトしない。その代わりとして、係数を
1ビットプレーンずつ処理する間に、特定の係数につい
てアラインメントが必要とされる実際のビットプレーン
が計算される。重要性レベルと特定の係数に対し適用さ
れるべきシフト量とが与えられれば、本発明は、その係
数の所望の絶対ビットプレーンを、それが可能なビット
プレーンの範囲内にあればアクセスする。すなわち、特
定の係数の所望の絶対ビットプレーンは、カレント重要
性レベルから該係数に適用されるべきシフト量を差し引
いたものにより与えられる。この所望ビットプレーン
は、それが最小の有効な絶対ビットプレーンより大きい
か又は等しく、かつ最大の有効な絶対ビットプレーンよ
り小さいか又は等しいときに有効とみなされる。
【0246】2つのアラインメント法が普通である。そ
の中の第1の方法は、平均2乗誤差(MSE)法と呼ば
れるもので、フルフレーム(full-frame)の再構成画像
を原画像と比較した時にMSEが縮小もしくは最小化さ
れるように、係数をアラインメントする方法である。図
50は、このアラインメントの一例である。図51も参
照のこと。
【0247】第2の方法は、ピラミッド型のアラインメ
ント法であり、画像がピラミッド・レベルのサイズに再
構成される場合に良好なレート・歪み性能を提供する。
ここでは、隣接レベルの係数は共通の重要レベルを持た
ない、つまりオーバーラップがない。図51の左側にあ
るアラインメントは、3レベルTS変換のための厳密に
ピラミッド型のアラインメントを表す。図51の右側
は、レベル2のピラミッド型アラインメントを表す。
(図51の厳密にピラミッド型の部分は、レベル3と2
のピラミッド型アラインメントと呼んでよかろう。)
各場合において、レベル内部の係数はMSEに関連して
アラインメントされる。
【0248】図52は、メモリ記憶係数と一つのアライ
ンメントとの間の典型的な関係を示す。
【0249】本発明によれば、実際のシフト操作を行う
必要がないため、メモリサイズの制約がなくなる。さら
に、本発明は、余分なメモリを必要とせず、任意のアラ
インメント法を簡単に実施できる。
【0250】ヒストグラム圧縮 本発明はヒストグラム圧縮を利用してもよい。一実施例
では、変換又はバイナリ方式の処理を施される前にヒス
トグラム圧縮が利用される。ヒストグラム圧縮は、一部
の画像に対する圧縮率を向上させる。そのような画像は
通常、ダイナミックレンジの一部の値がどの画素にも使
われない画像である。言い換えれば、画像のダイナミッ
クレンジにギャップが存在する。例えば、ある画像が合
計256の値の中の0と255の値しかとらないときに
は、その原画像と一対一対応を持つが、ダイナミックレ
ンジのずっと小さな新たな画像を生成できる。この画像
生成は、整数を画像のとる値に写像する増加関数を定義
することにより達成される。例えば、画像が0と255
の値しか使わないときには、マッピングで0を0に、1
を255に写像する。別の実施例では、画像が偶数(又
は奇数)画素しか持たないときには、画素値を0〜12
8の値に再写像する。
【0251】ヒストグラム圧縮を行った後に、画像デー
タに本発明の可逆埋め込みウェーブレットによる圧縮を
施してよい。このように、ヒストグラム圧縮は前処理モ
ードで用いられる。一実施例では、ヒストグラムは、ブ
ーリアン(Boolean)ヒストグラムを基礎としており、
値が生じるか否かのリストを保持するようなものであ
る。まず、全ての生起数が昇順に記録される。次に、そ
れぞれの値は0から順に写像される。
【0252】一実施例では、誤差の影響を減らすためガ
ード(guard)画素値が用いられる。隣接した再写像画
素値が大きなギャップで隔てられた実画素値に対応する
かもしれないので、再写像値の小さな誤差が実値の大き
な誤差をもたらすことがある。再写像値の近くに割増値
を追加することにより、そのような誤差の影響は減少す
るであろう。
【0253】原画像を再構成するために、マッピングが
利用されたことが復号化器へ通知される。このマッピン
グをヘッダ中に指示してもよい。これにより、復号化器
において後処理のために同様のテーブルを作成できるよ
うになる。一実施例では、復号化器はレンジをタイル毎
に通知される。一実施例では、本発明は、まず当該マッ
ピングが行われることを知らせ、次に欠落した値(例え
ば上例の254)の数を知らせる。ヒストグラム圧縮の
利用の有無を知らせるためのコストは、たったの1ビッ
トである。このビットの後に、全ての再写像値のテーブ
ルが続くことになろう。
【0254】一実施例では、1タイルずつヒストグラム
圧縮を実行する時の通知量を減らすため、1つのビット
で、新しいブーリアン・ヒストグラムが直前に使用した
ブーリアン・ヒストグラムと同じか違うかを知らせる。
このような場合、新たなブーリアン・ヒストグラムが復
号化器に通知されるのは、それが直前のヒストグラムと
異なるとき(のみ)である。新しいブーリアン・ヒスト
グラムが前のものと違う場合でも、その間に類似点があ
るのが普通である。より詳しくいえば、2つのヒストグ
ラムの排他的論理和はエントロピー・コーダによる圧縮
性がより高いので、それを生成して復号化器へ通知して
もよい。
【0255】ヒストグラムは、サイズのダイナミックレ
ンジと同じくらいのビット数(例えば8ビット深度の場
合は256ビット)を送信することにより通知できる。
そのビットの並び順は画素値に対応する。この場合、あ
るビットが1であるのは、それに対応した値が画像中に
用いられるときである。ヘッダのコストを削減もくしは
最小化するため、このビット列を、第1次マルコフ(Ma
rkov)コンテキストモデルのもとでエントロピー符号化
してもよい。
【0256】別の実施例では、欠落した値が過半数のと
きには発生した値が順に記録されるであろうが、そうで
ないときには欠落した値が順に記録される。
【0257】一実施例では、本発明のバイナリ方式が、
パレット化された画像の圧縮のために利用されるであろ
う。パレットはヘッダに格納されるであろう。しかし、
パレット化画像は埋め込まれないであろうから、損失性
伸長のための量子化は妥当な結果をもたらさない。別の
実施例では、パレット化画像は連続階調(カラー又はグ
レースケール)画像に変換され、各成分が変換方式又は
バイナリ方式により圧縮されるかもしれない。これは妥
当な損失性圧縮が可能である。
【0258】ある種の画像は、1つの指定色(又は指定
色の小サブセット)が特定の目的のために使用された連
続階調画像である。その特定目的色は注記用かもしれな
い。例えば、グレースケールの医用画像には、その画像
を識別するためのコンピュータ生成のカラー文字がある
かもしれない。もう一つの特定目的色は、オーバーレイ
画像において画素が透過であって、下側の画像の画素が
代わりに表示されることを示すかもしれない。禁止され
た色は別の成分画像に分解されるであろう。そして、連
続階調成分及び特殊色成分は、変換方式又はバイナリ方
式で圧縮/伸長されるであろう。
【0259】なお、変換方式及びバイナリ方式は輝度デ
ータのために利用されることが多いが、アルファ混合用
のアルファ・チャネルのような他の形式の2次元データ
が用いられてもよい。
【0260】パーサ(parser) 本発明によれば、符号ストリームを、伸長することな
く、送信又は復号化の前に構文解析できるようになる。
この構文解析は、ビットストリームを打ち切り、特定の
量子化のために必要な量の情報だけを伝達することがで
きるパーサによって実行される。このパーサを支援する
ため、マーカー(marker)及びポインタがビットストリ
ーム内の符号化単位の各ビットプレーンの位置を決定す
る。
【0261】本発明は、画像圧縮システムにおいて構文
解析によって実施される装置依存の量子化を提供する。
圧縮システムにおいてマーカーを用いることにより、符
号化後に装置に応じ選択される量子化が可能になる。出
力装置はその特性をパーサに報告し、パーサはその特定
装置向けに符号化済みファイルを量子化する。この量子
化は、ファイルの一部を省くことによる。可逆ウェーブ
レット変換の利用は、画像の非損失復元、あるいは、装
置に応じた視覚的に非損失の色々な歪みでの画像の復元
を可能にする。
【0262】本発明によれば、量子化を符号化後に実行
することが可能になる。図27及び図28は、パーサを
備えた圧縮システムのブロック図である。図27及び図
28において、元の圧縮されていない画像2101が本
発明の圧縮装置2102に入力される。圧縮装置210
2は、画像2101を圧縮ビットストリーム2103へ
非損失圧縮するとともとに、圧縮ビットストリーム21
03にマーカーを付加する。
【0263】圧縮ビットストリーム2103はパーサ2
104に入力し、パーサ2104は圧縮ビットストリー
ム2103のある部分を出力として提供する。そのある
部分は、圧縮ビットストリーム2103の全部であるか
もしれないし、その一部分だけかもしれない。要求側の
エージェントもしくは装置は、伸長画像が必要とされる
時に、その装置特性をパーサ2104に与える。それに
応じて、パーサ2104は圧縮ビットストリーム210
4の適切な部分を選択して送出する。パーサ2104は
画素もしくは係数レベルの演算もエントロピー符号化/
復号化も行わない。別の実施例では、パーサ2104は
そのような働きを多少は果たすかもしれない。
【0264】パーサ2104は、低解像度用の圧縮係数
を選択することにより、モニタに画像を表示するための
符号化データを提供することができる。それと異なる要
求に対しては、パーサ2104は注目領域(ROI)の
非損失性伸長を可能にするように圧縮データを選択す
る。一実施例では、パーサ2104は、要求に従って、
プレビュー画像からプリンタ解像度画像又はフルサイズ
の医用モニタ画像(恐らく16ビットの画素深度を持
つ)までの変化に必要なビットを送出する。
【0265】パーサ2104により提供されたデータは
通信路及び/又は記憶装置2106へ出力される。伸長
装置2107は、そのデータにアクセスし、圧縮データ
を伸長する。伸長された、すなわち再構成されたデータ
は、伸長画像2108として出力される。
【0266】図29において、2HH周波数帯域内のビ
ットプレーンは3HH周波数帯域からの情報を利用して
符号化される。ビットプレーンをより明瞭に示すため、
図50及び図51に図29が書き直されている。図50
のように係数が格納される場合(MSE)には、圧縮ビ
ットストリームの打ち切りはMSEレート・歪み最適量
子化とほとんど同一である。この打ち切りが、図50に
陰をつけたマーカーで示されている。図30を調べる
と、この配列はプリンタには適切かもしれないが、モニ
タには十分でないであろう。図51に示すように、係数
が”ピラミッド状に”格納される場合、つまり、ある周
波数帯域の全ビットが最初に格納される場合には、ビッ
トストリームの打ち切りは様々な解像度の画像を提供す
る。
【0267】マーカーを巧みに使えば、両タイプの打ち
切りが可能になり、解像度の低い、忠実度の低い画像を
発生するであろう。図50及び図51中の濃淡の変化
は、最高解像度で低忠実度のビットストリームを発生す
るであろうビットストリームの打ち切りを表す。LH,
HL,HH係数の全部をさらに打ち切れば、画像の解像
度を下げることになろう。
【0268】多くの画像圧縮の応用では、画像は、一度
だけ圧縮されるが、何度も伸長されるかもしれない。あ
いにく、たいていの圧縮システムは、許容される損失量
と適当な量子化とが符号化の時点で決定されなければな
らない。プログレッシブ・システムは段々に精細になる
一揃いの画像を与えるが、非損失性再構成は一般にでき
ない、すなわちプログレッシブ・ビルドアップと関係の
ない非損失な方法で符号化された”差分画像”を送り出
すことにより、非損失性再構成が提供される。
【0269】本発明においては、符号化器は、種々の係
数を周波数及びビットプレーン要素に分解するに足るだ
けの情報を保存する。一実施例では、次のエントロピー
符号化データ単位に何が入っているか知らせるためのマ
ーカーがビットストリームに挿入される。例えば、マー
カーは、次のエントロピー符号化データ単位に、最上位
より3番目のビットプレーンのためのHH周波数情報が
入っていることを示すかもしれない。
【0270】誰かがモニタ上で画像を調べたいとする
と、低解像度のグレースケール画像を生成するために必
要な情報を要求するであろう。そのユーザがその画像を
印刷したいときには、高解像度の2値画像を生成するた
めに必要な情報が要求されるであろう。最後に、そのユ
ーザが圧縮試験を実施したいとき、あるいはセンサ雑音
の統計分析や医療診断を行いたいときには、その画像の
非損失版が要求されるであろう。
【0271】図31は、パーサ、復号化器、出力装置と
のやりとりに関するブロック図である。図31におい
て、パーサ2402は、マーカー付の非損失性圧縮デー
タ、並びに1つ以上の出力装置、例えば図示のディスプ
レイ・モジュール2405の装置特性を受け取るように
接続される。この装置特性に基づき、パーサ2402は
圧縮データの適当な部分を選択し、それを通信路240
3へ送り、通信路2403はそのデータを伸長装置24
04へ転送する。伸長装置2404はそのデータを復号
化し、復号化データをディスプレイ・モジュール240
5に与える。
【0272】本発明は、ワールド・ワイド・ウェブ、そ
の他の画像サーバーに対する改良したサポートをデータ
ストリームに与える。データストリームのある部分はモ
ニタ用の低空間解像度・高画素深度の画像をサポートす
ることができる。別の部分は、高空間解像度・低画素深
度のプリンタをサポートすることができる。データスト
リーム全体は非損失性伝送を提供する。これら3つの使
い方が同じ圧縮データによりサポートされるので、ブラ
ウザがモニタ画像、印刷画像及び非損失性画像を順番に
要求するならば、余分なデータを全く送る必要がない。
伝送されたモニタ画像用情報で印刷画像のために必要と
されるものは、印刷画像のために再利用できる。伝送さ
れたモニタ画像と印刷画像のための情報は、非損失画像
のために再利用できる。本発明は、閲覧のための伝送時
間(伝送費用)を減らし、また、サーバーに格納しなけ
ればならないデータ量を最小にする。
【0273】本発明のシステムにおいては、画像は1度
だけ圧縮されるが、データが何であるかを示すために様
々なマーカーが格納される。その後、ワールド・ワイド
・ウェブ(WEB)サーバーは、表示の要求を受信し、
必要な係数を提供するであろう。WEBサーバーは、圧
縮とか伸長とか何もする必要がなく、送るべきビットス
トリームの適当な部分を選択するだけである。
【0274】このような構文解析システムによる量子化
は、可逆ウェーブレット及びコンテキストモデルによる
高度の非損失性圧縮がないとしても、帯域幅の実質的な
増加をもたらす。この構文解析システムは高品質の注目
領域の選択にも利用できる。
【0275】図32は量子化選択装置を示す。一実施例
では、この選択装置はソフトウエアによって、各種装置
のための適切な量子化プロファイルを決定するよう構成
される。画像は変換され、様々な周波数帯域のビットプ
レーンを捨てることによって量子化される。次に逆ウェ
ーブレット変換が実行される。再構成画像は表示に矛盾
しない何らかの方法で処理される。モニタに表示される
高解像度画像については、その処理はある種のスケーリ
ングであろう。プリンタの場合には、ある種の閾値処理
又はディザ処理かもしれない。同じ処理が原画像に適用
され、圧縮画像と比較される。平均2乗誤差が例として
用いられたが、どのような視覚的差異基準を用いてもよ
い。様々なビットプレーンの量子化による誤差を利用
し、ビットレートの節減による歪みが最低となるように
ビットプレーンを選択し量子化する。このプロセスは所
望のビットレート又は歪みに達するまで続けられるであ
ろう。各種画像処理操作のための代表的な量子化がいっ
たん決まったならば、量子化をシミュレートする必要は
なく、代表値が用いられるであろう。
【0276】勿論、スケーリングのような単純な画像処
理操作に関しては、様々な周波数帯域の量子化の効果を
解析的に決定できる。その他のディザ処理やコントラス
ト・マスキングのような操作に関しては、シミュレーシ
ョンによりほぼ最適な量子化を見つけるのはずっと簡単
である。
【0277】図32において、符号ストリーム2500
は、量子化を含む伸長2501及び非損失性伸長250
3を施される。その伸長結果に対し、画像処理又は歪み
モデル2502,2504が適用される。その出力は画
像であり、MSE又はHV5差モデル2505のような
差モデルを適用される。その差判定の結果に基づき、ア
ラインメントが調節され(2504)、したがって量子
化も調節される。
【0278】構文解析を容易にするため、本発明は一連
のヘッダによる合図を利用する。一実施例では、本発明
の符号ストリーム構造は、1つ以上のタグ値を持つ主ヘ
ッダを含む。主ヘッダ中のタグは、符号ストリーム中の
すべてのタイルのために用いられた成分の数、サブサン
プリング及びアラインメント等の情報を知らせる。一実
施例では、符号ストリーム中の各タイルの前に、そのヘ
ッダがある。タイル・ヘッダの情報は、当該タイルに対
してのみ適用され、また主ヘッダの情報をくつがえすか
もしれない。
【0279】ヘッダはそれぞれ1つ以上のタグを含む。
一実施例では、インライン・マーカーはない。ヘッダ・
タグは、ある既知の点からユーザがコーダをリセットす
る所までの圧縮データの量を示す。一実施例では、どの
タグもみな16の倍数のビット数である。したがって、
主ヘッダ及びタイル・ヘッダはどれもみな16の倍数の
ビット数である。なお、どのタグも、16以外の数の倍
数のビット数でも構わないことに注意されたい。どのタ
イルデータ・セグメントも、16の倍数のビット数にな
るよう適当数の0が挿入される。
【0280】一実施例では、各タイル・ヘッダはそのタ
イル・サイズを指示するかもしれない。別の実施例で
は、各タイルは、どこで次のタイルが始まるか指示する
かもしれない。なお、符号ストリームのバックトラック
が可能なときには、そのような情報をすべて主ヘッダに
挿入することにより、符号化が簡単になるかもしれな
い。パーサは、符号ストリームに関する情報をその量子
化を実行するために利用することができる。
【0281】一実施例では、タイル・ヘッダはタイルが
ウェーブレット方式とバイナリ方式のいずれで符号化さ
れたか指示するかもしれない。重要性レベル・インディ
ケータは、タイルのデータと重要性レベルとを関係付け
る。重要性レベル・ロケータ(locator)は、可能な打
ち切り位置を知らせる。例えば、各タイルに対し同じ歪
みが望まれるときには、どの重要性レベルがその所望の
歪みレベルと等しいか分かれば、パーサは符号ストリー
ムを適切な位置で打ち切ることができる。一実施例で
は、各タイルは、同じビット数を持つのではなく、ほぼ
同じ歪みを持つ。
【0282】本発明は、重要性レベル・ロケータ・タグ
を持つことにより、複数のタイルと、各タイルのどこで
終わるべきかの指示を持ち得るようにしている。
【0283】タグとポインタ 復号化又は構文解析に用いられる構文解析用マーカー及
びその他の情報が、タグに入れられてもよい。一実施例
では、ヘッダは以下のルールに従うタグによって制御情
報を与える。
【0284】タグは固定サイズでも可変サイズでもよ
い。成分数、タイル数、レベル数、又はリセットもしく
は所望情報の数により、タグは長さが変わってもよい。
【0285】画像が構文解析され量子化されるならば、
それらのタグは新しい画像特性を表すように変更され
る。
【0286】データストリーム中のリセット点は、8の
倍数のビット数になるように0を挿入される。エントロ
ピー・コーダを符号ストリームのある点でリセットでき
るが、その点は符号化時に決定される(しかし、それを
行うことができるのは、一つの重要性レベルの符号化の
終わりでだけである)。このリセットは、エントロピー
・コーダにおける全ての状態情報(コンテキスト及び確
率)が既知の初期状態に戻されることを意味する。次
に、符号ストリームは次の8の倍数のビット数まで0を
挿入される。
【0287】パーサは、画像を量子化する際に符号スト
リーム・タグだけを手がかりとして用いる。一実施例で
は、この量子化処理のために、タイル長、成分長、リセ
ット、ビット対重要性レベル、及び、重要性レベル・ロ
ケータの各タグが用いられる。
【0288】パーサによって画像が量子化された後、そ
のタグはすべて新しい符号ストリームを反映するよう変
更される。これは画像と、タイルサイズ、成分数、成分
のスパン、全ての長さとポインタ等々に影響を及ぼすの
が普通である。さらに、画像がどのように量子化された
かを記述する情報タグも含まれる。
【0289】表3は、本発明の一実施例における全ての
タグの一覧表である。説明と用語はしばしばJPEGと
は異なるが、可能な場合には同じマーカーと識別子が用
いられる。どの画像も少なくとも2つのヘッダ、すなわ
ち、画像の始まりにある主ヘッダと、各タイルの始まり
にあるタイルヘッダとを有する。(どの符号ストリーム
もみな少なくとも1つのタイルを含む)3種類のタグ、
すなわち区切りタグ、機能タグ及び情報タグも用いられ
る。区切りタグは、ヘッダ及びデータのフレーミングの
ために用いられる。機能タグは、利用される符号化機能
を記述するために使われる。情報タグはデータに関する
オプションの情報を提供する。
【0290】
【表3】
【0291】なお、”x”は当該タグが当該ヘッダ中で
用いられないことを意味する。ヘッダ中のTLMタグ又
は各タイル中のTLTタグのどちかが必要とされるが、
その両方は必要でない。成分ポインタが必要であるの
は、2つ以上の成分があるときだけである。
【0292】図33は本発明の符号ストリームにおける
区切りタグの配置を表す。各符号ストリームは、1つの
SOIタグ、1つのSOCタグ、1つのEOIタグだけ
(及び少なくとも1つのタイル)を持つ。各タイルは1
つのSOTタグと1つのSOSタグを持つ。各区切りタ
グは16ビットで、長さ情報を含まない。
【0293】SOIタグは、JPEGファイルの始まり
を示し、16ビットのJPEGマジックナンバー(magi
c number)である。
【0294】SOCタグはファイルの始まりを示し、S
OIタグの直後にくる。SOIタグとSOCタグは全体
として、ユニーク数を形成する16ビットとなる。
【0295】SOTタグはタイルの始まりを示す。符号
ストリームには少なくとも1つのタイルがある。SOT
はストリームがまだ同期していることを保証するための
チェックとして働く。
【0296】SOSタグは”スキャン”の始まりを示
し、その後にタイルの実画像データが続く。SOSはタ
イル・ヘッダの終わりを示し、また、CREW符号スト
リームには少なくとも1つのSOSがなければならな
い。SOSとその次のSOT又はEOI(画像の終わ
り)との間のデータは16の倍数のビット数であり、こ
の符号ストリームは必要であれば0が挿入される。
【0297】EOIタグは画像の終わりを示す。EOI
はストリームがまだ同期していることを保証するための
チェックとして働く。符号ストリーム中に少なくとも1
つのEOIがある。
【0298】機能タグは、タイル又は画像の全体を符号
化するために利用される機能を記述する。これらタグの
中には、主ヘッダに用いられるが、個々のタイルの符号
化中に別の値を持つ同じタグを使って覆すことができる
ものもある。SIZタグは画像格子の幅と高さ、タイル
の幅と高さ、成分数、色空間変換(必要なとき)、各成
分のサイズ(画素深度)、及び成分が基準格子をどのよ
うに埋めるかを定義する。このタグは主ヘッダにのみ出
現し、タイル・ヘッダ中には出現しない。各タイルは、
その成分のすべてに同じ特性を提供させる。ここで定義
されたパラメータの多くは他のタグのためにも用いられ
るため、SIZタグはSOCタグのすぐ後に続かねばな
らない。このタグの長さは、SIZの後の最初のフィー
ルドであるLsizに保存されるが、成分数に依存する。
図34はSIZタグに関する画像とタイルのサイズのシ
ンタックスを示す。
【0299】以下は各要素のサイズと値の説明リストで
ある。
【0300】SIZ:マーカー。
【0301】Lsiz:マーカを含めない、バイト数で
表したタグの長さ(偶数でなければならない)。
【0302】Xsiz:画像基準格子の幅(1成分の画
像又は共通のサブサンプリングによる色成分を持つ画像
では画像幅と同じ)。
【0303】Ysiz:画像基準格子の高さ(1成分の
画像又は共通のサブサンプリングによる色成分を持つ画
像では画像の高さと同じ)。
【0304】XTsiz:1タイル画像基準格子の幅。
タイルは、あらゆる成分の1標本を持てるだけの幅でな
ければならない。画像幅内のタイルの数は
【0305】
【外3】
【0306】に等しい。
【0307】YTsiz:1タイル画像基準格子の高
さ。タイルは、あらゆる成分の1標本を持てるだけの高
さでなければならない。画像高さ内のタイルの数は
【0308】
【外4】
【0309】に等しい。
【0310】Csiz:画像中の成分の数。
【0311】CSsiz:色空間変換の種類(必要なと
き)。このタグは包括的ではない。(多くの多成分空間
変換はここでは指定できない。それらは本発明のファイ
ルフォーマット内でない、ほかの場所で指示される必要
がある)。表4に色空間変換のための値を示す。
【0312】
【表4】
【0313】このタグにおいて記述されるサブサンプリ
ングは、各成分に最高解像度を利用できない画像に適用
される。本発明のシステムは、最高解像度を利用できる
時に重要性の低い成分のサイズを縮小する別の方法があ
る。
【0314】Ssizi: 第i成分の精度(画素深
度)。このパラメータ、XRsiz及びYRsizは全
ての成分ために繰り返される。
【0315】XRsizi:第i成分のX次元の大き
さ。例えば、数字2は当該成分が2つの水平基準格子点
に寄与することを意味する。このパラメータと、Ssi
z、YRsizは全ての成分のために繰り返される。
【0316】YRsizi:第i成分のY次元の大き
さ。例えば、数字2は当該成分が2つの垂直基準格子点
に寄与することを意味する。このパラメータと、Xsi
z、XRsizは全ての成分のために繰り返される。
【0317】res:必要なときに最後に置かれる0の
埋め草バイト。
【0318】
【表5】
【0319】CODタグは、画像又はタイルに用いられ
たバイナリ方式やウェーブレット方式といった符号化方
式、変換フィルタ及びエントロピー・コーダを記述す
る。このタグは主ヘッダに含まれ、またタイルヘッダに
も使用できる。このタグの長さは成分数に依存する。図
35は、符号化方式シンタックスを示す。表6は符号化
方式のためのサイズと値を示す。
【0320】
【表6】
【0321】COD:マーカー。
【0322】Lcod:マーカーを含めない、バイト数
で表したタグの長さ(偶数でなければならない)。
【0323】Ccodi:各成分の符号化方式。
【0324】res:必要なときに最後に置かれる0の
埋め草バイト。
【0325】
【表7】
【0326】各成分毎に、ALGタグはピラミッドレベ
ル数と係数のアラインメントを記述する。ALGは主ヘ
ッダに用いられ、またタイルヘッダにも用いることがで
きる。このタグの長さは、成分数に依存し、場合によっ
てはレベル数にも依存する。図36は、本発明の成分ア
ラインメント・シンタックスの一例を示す。図36にお
いて、以下の成分が含まれる。
【0327】ALG:このマーカーは、成分アラインメ
ント・パラメータのサイズと値を示す。
【0328】
【表8】
【0329】Lalg:マーカーを含めない、バイト数
で表したタグの長さ(偶数である)。
【0330】Palgi:第i成分のピラミッド分解レ
ベル数。このパラメータとAalg、場合によってはS
algも、各成分毎に1レコードとして繰り返される。
【0331】Aslgi:第i成分のアラインメント。
このテーブル・エントリーは、係数のアラインメントを
記述し、あらゆる成分のために繰り返される。表9にA
algパラメータの値を表す。
【0332】
【表9】
【0333】Palg、場合によってはSalgも、各
成分毎に1レコードとして繰り返される。
【0334】Talgi:表10にテール情報選択方法
を示す。
【0335】
【表10】
【0336】Salgij:第i成分の第jサブブロック
のアラインメント値であり、当該成分のためのAalg
iの値が”カスタム・アラインメント"であるときにのみ
用いられる。この数は、どの カスタム・アラインメン
トが選ばれるかにより8ビット又は16ビットであり、
また、当該成分に関し、画像のあらゆる周波数帯域のた
めに順番に繰り返される。(バイナリ方式に関しては、
Salgijは第iピラミッドレベルのアラインメント値
である) Salgijが用いられる時には、Salgij
と、Aalg及びPalgは各成分毎に1レコードとし
て繰り返される。
【0337】res:必要なときに最後に置かれる0の
埋め草バイト。
【0338】TLMタグは、画像中のあらゆるタイルの
長さを記述する。各タイルの長さは、SOTタグの第1
バイトから(次のタイルの)次のSOTタグの第1バイ
ト、又はEOI(画像の終わり)までを測った長さであ
る。言い換えれば、この長さはタイルへのポインタのリ
スト又はデイジーチェーンである。
【0339】符号ストリームは、単一のTLMタグ又は
各タイル毎のTTLタグのいずれかを含むが、その両方
は含まない。主ヘッダ中にTLMタグが使用される時に
は、TLTタグは用いられない。逆に、各タイルがTL
Tタグで終わるときには、TLMタグは用いられない。
TLMヘッダ中の個々のタイル長の値は、TLMが使わ
れないとしたならば対応TLTタグのために用いられる
であろう値と同じである。TLMタグの長さは、画像中
のタイル数に依存する。図37はタイル長・主ヘッダの
シンタックスの一例を示す。
【0340】TLM:表11に、タイル長・主ヘッダパ
ラメータのサイズと値を示す。
【0341】
【表11】
【0342】Ltlm:マーカーを含めない、バイト数
で表したタグの長さ(偶数である)。
【0343】Ptlmi:第iタイルのSOTマーカー
から次のSOT(又はEOI)マーカーまでのバイト数
で表した長さ。これは、画像中のあらゆるタイルのため
に繰り返される。
【0344】TLTタグはカレント・タイルの長さを記
述するが、この長さは、SOTタグの第1バイトから次
のタイルのSOTタグの第1バイトまで(又はEOIま
で)を測った長さである。言い換えれば、TLTは次の
タイルへのポインタである。TLTシンタックスの一例
を図38に示す。
【0345】TLMタグかTLTタグのいずれかが必要
とされ、両方は必要とされない。TLTタグは、使用さ
れる時には、全てのタイルヘッダに必要とされ、そして
TLMタグは使われない。これらのタイル長の値は両マ
ーカーとも同一である。
【0346】TLT:表12に、タイル長・タイルヘッ
ダパラメータのサイズと値を示す。
【0347】
【表12】
【0348】Ltlt:マーカーを含めない、バイト数
で表したタグの長さ(偶数である)。
【0349】Ptlt:タイルのSOTマーカーから次
のSOTマーカー(又はEOIマーカー)までの長さ
(バイト数)。
【0350】CPTタグは、SOTの第1バイトより、
タイル中の第1成分以外のすべての成分の第1バイトを
指し示す。成分符号化データは各タイル内にノンインタ
ーリーブ形式で配置され、8ビット境界から始まる。こ
の点でエントロピー・コーダはリセットされる。
【0351】画像が2つ以上の成分を含むときに、この
タグはあらゆるタイルのタイルヘッダに使用される。こ
の可変長タグのサイズは、画像中の成分数に依存する。
成分ポインタのシンタックスの一例を図39に示す。
【0352】CPT:表13に、成分ポインタのパラメ
ータのサイズと値を示す。
【0353】
【表13】
【0354】Lcpt:マーカーを含めない、バイト数
で表したタグの長さ(偶数である)。
【0355】Pcpti:カレント・タイルのSOTタ
グから次の成分の始まりまでのバイト数。第1成分のデ
ータはSOSタグの直後に始まるため、Pcpt値の数
は成分数より小さい。新たな成分データは8ビット境界
上で始まる。
【0356】IRSタグは、カレント・タイルのSOT
タグの第1バイトよりデータ中のリセットを指し示す。
これらのリセットは、符号化が完了した重要レベルの終
わりの後の8ビット境界に見出される。リセットが生じ
る点の成分は、CPTタグ値とリセット・ポインタとの
間の関係によって決定できる。このタグの長さは、復号
化器に利用されたリセットの数に依存する。重要性レベ
ル・リセット・シンタックスの一例を図40に示す。
【0357】IRS:表14に重要性レベル・リセット
のパラメータのサイズと値を表す。
【0358】
【表14】
【0359】Lirs:マーカーを含めない、バイト数
で表したタグの長さ(偶数である)。
【0360】Iirsi:第iリセットでのカレント重
要性レベルの番号。このIirsタグと、対応したPi
rsタグとが一種のレコードを形成し、これは各リセッ
ト毎に繰り返される。これらのレコードは、リセットを
持つ最も高い重要性レベルからリセットを持つ最低の重
要性レベルへと続き、その次の成分の重要性レベルのも
のが続き、同様にして最後の成分まで続く順序である。
【0361】Pirsi:カレント・タイルのSOTタ
グから第iリセットのバイトまでのバイト数。このPi
rsタグとIirsタグとが一種のレコードを形成し、
これは各リセットに対し繰り返される。これらのレコー
ドは、最小のポインタから最大のポインタへの順序でな
ければならない。すなわち、これらのレコードは、各リ
セットバイトを符号ストリーム中で出現した順に指し示
す(数が小さくなるほど、物理的には先に出現するバイ
トを指す)。
【0362】特定の情報タグがもっぱら情報目的のため
に含まれる。これらの情報タグは、復号化器のためには
必要ではないが、パーサの助けとなろう。
【0363】例えば、VERタグはメジャー・バージョ
ン番号及びマイナー・バージョン番号を記述する。この
タグは、主ヘッダに使われる。このタグは、規定されて
はいるが、画像の復号化に必要とされる機能レベルを意
味しない。実は、その目的は、あらゆる復号化器及びパ
ーサを、本発明のどのバージョンの符号ストリームも復
号化及び構文解析できるようにすることである。本発明
のバージョン番号のシンタックスの一例を図41に示
す。
【0364】VER:表15にバージョン番号パラメー
タのサイズと値を示す。
【0365】
【表15】
【0366】Lver:マーカーを含めない、バイト数
で表した卓の長さ(偶数である)。
【0367】Vver:メジャー・バージョン番号。
【0368】Rver:マイナー・バージョン番号。
【0369】BVIタグは、画像幅を基準にして、ビッ
トの数を重要性レベルに関連付ける。このオプションの
タグは、主ヘッダに用いられる。この可変長タグのサイ
ズは、符号化器によって数え上げられた重要性レベルの
数に依存する。ビット対重要性レベル・シンタックスの
一例を図42に示す。
【0370】BVI:表16に、タイル長主ヘッダ・パ
ラメータのサイズと値を示す。
【0371】
【表16】
【0372】Lbvi:マーカーを含めない、ビット数
で表したタグの長さ(偶数である)。
【0373】Cbvii:これは、どの成分データが記
述されるのか知らせる。このCbviパラメータはIb
vi及びPbviと共に、1レコードを形成し、これは
記述されたすべての成分及び重要性レベルについて繰り
返される。最初の成分の全ての重要性レベル記述、次の
成分の全ての重要性レベル記述、等々と続くような順序
でなければならない。
【0374】Ibvii:カレント成分において、Pb
vii内のバイト数につき符号化された重要性レベルの
番号。この番号(1つ又は複数)は、レート・歪み曲線
の関心点を伝えるために符号化時に選択される。このI
bviパラメータはCbvi及びPbviとともに1レ
コードを形成し、これは記述されたすべての成分及び重
要性レベルについて繰り返される。
【0375】Pbvii:主ヘッダとタイルヘッダ、及
び、Ibvii内の重要性レベルの数に関連した全ての
データを含む符号化ファイル中のバイト数。このPbv
iパラメータはCbvi及びIbviとともに1レコー
ドを形成し、これは記述されたすべての成分及び重要性
レベルについて繰り返される。
【0376】res:必要なときに最後に置かれる0の
埋め草バイト。
【0377】ILLタグは、符号化データの重要性レベ
ルの終わりに対応した符号ストリームへのポインタを記
述する。ILLタグは、IRSタグと似ているけれど
も、リセットも8ビット境界へのビット挿入もないデー
タを指し示す。このタグにより、パーサは、画像幅基準
でほぼ同じひずみのタイルを見つけて打ち切ることが可
能になる。このタグは、オプションであり、タイルヘッ
ダ中でだけ使われる。このタグの長さは、数え上げられ
た重要性レベルの数に依存する。重要性レベル・ロケー
タのシンタックスの一例を図43に示す。
【0378】ILL:マーカー。表17に、重要性レベ
ル・ロケータのパラメータのサイズと値を示す。
【0379】
【表17】
【0380】Lill:マーカーを含めない、バイト数
で表したタグの長さ(偶数である)。
【0381】Iilli:Pilli内のバイト数に関し
符号化される重要性レベルの番号。それら番号はそれぞ
れ、レート・歪み曲線の関心点を伝達するため符号化時
に選択される。このIill番号はPillパラメータ
と共に1レコードを形成するが、これは最も速い成分に
おいて最高重要度レベルから最低重要性レベルへの順に
繰り返され、以下、後の成分における重要な最高重要性
レベルから最低重要性レベルまでを特定する同様レコー
ドが続く。
【0382】Pilli:カレント・タイルのSOTの
第1バイトより、当該タイルの符号化データ中のIil
liの重要性レベルが完了するバイトを指し示す。この
Pill数はIillパラメータと共に1レコードを形
成し、これは最も速い成分において最高の重要性レベル
から最低の重要性レベルへの順に繰り返され、以下、後
の成分における重要な最高重要性レベルから最低重要レ
ベルまでを特定する同様レコードが続く。
【0383】RXYタグは、実寸法に関する画像基準格
子のX解像度及びY解像度を定義する。このタグは主ヘ
ッダにのみ用いられる。解像度(画素/単位)のシンタ
ックスの一例を図44に示す。
【0384】RXY:表18に、解像度(画素/単位)
を指定するためのパラメータのサイズと値を示す。
【0385】
【表18】
【0386】Lrxy:マーカーを含めない、バイト数
で表したタグの長さ(偶数である)。
【0387】Xrxy:単位あたりの基準格子画素数。
【0388】Yrxy:単位あたりの基準格子ライン
数。
【0389】RXrxy:X次元の単位。したがって、
水平方向の解像度は、Xrxy格子画素/10(RXr
xy−128)メートルである。
【0390】RYrxy:Y次元の単位。したがって、
垂直方向の解像度はYrxy格子ライン/10(RYr
xy−128)メートルである。
【0391】CMTタグはヘッダ内の非構造化データを
許す。このタグは、主ヘッダとタイルヘッダのいずれに
も使用できる。このタグの長さは、コメントの長さに依
存する。コメントのシンタックスの一例を図45に示
す。
【0392】CMT:表19にコメント・パラメータの
大きさと値を示す。
【0393】
【表19】
【0394】Lcmt:マーカーを含めない、バイト数
で表したタグの長さ(偶数である)。
【0395】Rcmt:タグのレジストレーション(re
gistration)値。表20に、レジストレーション・パラ
メータの値を示す。
【0396】
【表20】
【0397】Ccmti:非構造化データのバイト。任
意に繰り返される。
【0398】res:必要なときに、最後に置かれる0
の埋め草バイト。
【0399】QCSタグは、量子化符号データがどこま
で量子化済みかを記述する。パーサ又は符号化器により
量子化が実行される時に、このタグは、符号化器が、重
要性レベルに関しどこまで符号化すべきかを大まかに判
断するのを助ける。このタグは、オプションであり、タ
イルヘッダにのみ使用される。量子化符号ストリームの
シンタックスの一例を図46に示す。
【0400】QCS:表21に、量子化符号ストリーム
のパラメータのサイズと値を示す。
【0401】
【表21】
【0402】Lqcs:マーカーを含めない、バイト数
で表したタグの長さ(偶数である)。
【0403】Cilli:カレント成分の番号。このC
ill番号はIqcsとともに1レコードを形成し、こ
れは最も速い成分における最高重要性レベルから最低重
要性レベルへの順に繰り返され、以下、後の成分におけ
る重要な最高重要性レベルから最低重要レベルまでを特
定する同様レコードが続く。
【0404】Iqcsi:これは、符号化データの少な
くとも一部分が残っている重要性レベルである。当該点
から次のリセットまでに残っているデータは全て、打ち
切り済み(量子化済み)である。
【0405】res:必要に応じて最後に置かれる0の
埋め草バイト。
【0406】損失性係数再構成 本発明は、一実施例において、値を所定の整数値の集合
に丸めることで損失性再構成を行う。例えば、0と31
の間の全ての係数は0に量子化され、32〜63の間の
全ての係数は32に量子化される等々である。図47
は、量子化しないときの係数の代表的分布を示す。各係
数の最も下のビットが分かっていない場合に、そのよう
な量子化が行われるかもしれない。別の実施例では、各
値域の中央の値が、その係数群を表すより正確な値を提
供するかもしれない。例えば、64と127の間の全て
の係数が95に量子化される。値がある点へ量子化され
るとき、その点は再構成点と呼ばれる。
【0407】画像間の差異により、得られる分布は形が
ゆがむ。例えば、図47中の曲線2701と曲線270
2を比較されたい。
【0408】本発明においては、再構成点は、その分布
に基づいて選ばれる。一実施例では、分布が推定され、
その推定分布に基づき再構成点が選ばれる。推定分布
は、既に分かったデータに基づき生成される。データを
収集する以前は、デフォルトの再構成点が用いられるで
あろう。このように、本発明は、適応的な損失性再構成
方法を提供する。さらに、本発明は、係数再構成を改善
する非反復の方法である。分布の差異によって値域の使
用が不均一になることを補償するため、本発明は次のよ
うに規定する。
【0409】
【数16】
【0410】ただし、2S は利用できるデータを基に復
号化器により測定された標本分散であり、Qは復号化器
に知らされた量子化である。次に、非ゼロ係数を0から
遠ざけることによって、それを修正する。
【0411】
【数17】
【0412】ただし、iは任意の整数である。
【0413】一実施例では、全部の復号化が完了した後
に、非ゼロ係数はすべて、ある再構成レベルに調整され
る。この調整をするためには、各係数を読み込み、恐ら
く修正し、そして書き込むことが必要である。
【0414】別の実施例では、各係数の各ビットプレー
ンが処理される時に、その係数が非ゼロならば、その係
数の適当な再構成値が記憶される。復号化が止まった時
に、全係数がそれらの適当な再構成値に設定される。こ
うすることにより、再構成レベルの設定のため別にメモ
リを経由する必要がなくなる。
【0415】カラー 本発明は、カラー画像(及びデータ)に適用できる。図
1の多成分処理機構101は、カラーデータのために必
要とされる処理を実行する。例えば、YUV色空間に
は、3つの成分、つまりY成分、U成分、V成分があ
り、各成分は別々に符号化される。
【0416】一実施例では、各成分のエントロピー符号
化データは、他の成分のエントロピー符号化データから
分離される。この実施例においては、成分のインターリ
ービングはない。成分別にデータを分けることは、ピラ
ミッド・アラインメントと組み合わされると、復号化器
又はパーサが異なった成分を容易に別々に量子化できる
ようにするのに役立つ。
【0417】他の実施例では、異なった成分のエントロ
ピー符号化データが周波数帯域単位又は重要性レベル単
位でインターリーブされる。これは、MSEアラインメ
ントと組み合わされると、共通の打ち切りを全成分のデ
ータの量子化に利用できるので有益である。このインタ
ーリービング方式のためには、符号化器が異なった成分
の周波数帯域間又は重要性レベル間の関係を提供する必
要がある。周波数帯域又は重要性レベルはかなり大量の
符号化データであろうから、パーサ又は復号化器はマー
カーを利用し成分を独立に量子化できるであろう。
【0418】さらに別の実施例では、異なった成分のエ
ントロピー符号化データは、画素毎又は係数毎にインタ
ーリーブされる。これは、MSEアラインメントと組み
合わされると、全成分に共通の打ち切りが作用するので
有益である。画素単位のインターリービングの場合、復
号化器及びパーサは符号化器で定義されのと同じ成分間
関係を利用しなければならない。
【0419】本発明によれば、同じシステムでサブサン
プリングを実行できる。
【0420】一実施例では、各成分は別々に記憶され
る。伸長装置及びパーサを使うことにより、損失性出力
画像を生成する時には、別々の成分メモリのそれぞれか
ら分解レベル及び成分の選択されたものだけが取得され
るであろう。例えば、YUV色空間において、Y色成分
については分解レベルの全部が取得されるであろうが、
U成分とY成分については第1分解レベル以外の分解レ
ベルがすべて取得されるであろう。結果として得られる
画像の組合せは、4:1:1画像である。なお、メモリ
に格納されているデータの異なった部分を用いることに
より、別の型式の画像を得ることもできる。
【0421】多くの型式の多成分画像を処理可能であ
る。画像データは、YUVのほかに、RGB(赤、緑、
青)、CMY(シアン、マゼンタ、黄)、CMYK(シ
アン、マゼンタ、黄、黒)又はCCIR601 YCrCb
でもよい。多重スペクトル画像データ(例えば、リモー
トセンシング・データ)も用い得る。RGBやCMYの
ような視覚的データに対しては、米国特許出願第08/
436,662号(1995年5月8日受理、" Metho
d and Apparatus for Reversible ColorCompressio
n "に述べられているような非損失性色空間変換を利用
できる。
【0422】ビット抽出 本発明は、ビット抽出を高めるようにコンテキストモデ
ルを計算しビットを符号化することができる。具体的に
は、ヘッドビットのためのコンテキストモデルは、隣接
画素より与えられる情報を基礎にしている。しばしば、
特に損失性圧縮を行う時に、このコンテキストは0であ
る。ヘッドビット・コンテキストの近似統計量のため、
本発明はヘッドビットのためのコンテキストを保持する
機構を提供する。
【0423】一実施例では、符号化に先だってメモリが
クリアされる。コンテキストは、その親、隣接画素の一
つ、又は注目画素が変わるまで、そのままである。変化
した時に、影響を受ける全てのコンテキストに関しコン
テクスト・メモリが更新される。テール情報を利用する
ときには、隣接画素と子だけが更新される。ヘッドビッ
トがオンの時に1係数につき1度だけメモリが更新され
る。
【0424】一実施例では、各係数は、符号(sign)の1
ビット、テールオン情報の4ビット、コンテキストの8
ビット、その後に続く係数の19ビットからなる32ビ
ット整数として記憶される。係数の一例を図48に示
す。
【0425】一実施例では、テールオン情報の4ビット
を利用して5つの異なったケースを生成する。
【0426】テールオン情報の4ビットの値が0のケー
スにおいては、カレント係数の絶対値ビットのカレント
・ビットプレーンのビットは、コンテキストビットを利
用して符号化される。該ビットが0ならば、プロセスは
終了する。該ビットが1ならば、係数の符号が符号化さ
れる。それから、テールオン情報の第1ビットが反転さ
れ、北、北東、西、南、東及び4つの子のコンテキスト
が更新され、プロセスは終了する。
【0427】テールオン情報の4ビットの値が1のケー
スにおいては、カレント係数の絶対値ビットのカレント
・ビットプレーンのビットは当該ケースのための一定の
コンテキストを使って符号化される。テールオン情報の
第2ビットが反転される。カレント係数の東と子のコン
テキストが更新される。プロセスは終了する。
【0428】テールオン情報の4ビットの値が7のケー
スにおいては、カレント係数の絶対値ビットのカレント
・ビットプレーンのビットは当該ケースのための一定の
コンテキストを使って符号化される。テールオン情報の
第3ビットが反転される。どのコンテキストも更新不要
である。プロセスは終了する。
【0429】テールオン情報の4ビットの値が3のケー
スにおいては、カレント係数の絶対値ビットのカレント
・ビットプレーンのビットは、当該ケース用の一定のコ
ンテキストを用いて符号化される。テールオン情報の第
4ビットが反転される。カレント係数の東と子のコンテ
キストが更新される。プロセスは終了する。
【0430】テールオン情報の4ビットの値が15のケ
ースにおいては、カレント係数の絶対値ビットのカレン
ト・ビットプレーンのビットは、当該ケースのための一
定のコンテキストを使って符号化される。テールオン情
報のどのビットも反転不要である。プロセスは終了す
る。
【0431】図48は本発明の係数の例を示す。図48
において、係数2801は、符号ビット2802と、そ
れに続くテールネオン情報ビット2803、それに続く
コンテキストビット2804、それに続く係数絶対値ビ
ット2805とからなる。前述のプロセスが図49のフ
ローチャートに示されている。
【0432】変化が生じた時に全コンテキストを更新す
る当該手法を使うことにより、ヘッドビットが圧倒的に
0である限り、コンテキスト・モデリングが高速に働
く。特に損失性符号化の場合にそうである。
【0433】可逆ウェーブレット係数のハフマン符号化 本発明は、一実施例において、ハフマン符号化を使って
ウェーブレット係数を符号化する。ハフマン符号化のた
めのアルファベットは2つの部分からなる。第1の部分
は0係数のランの長さに等しく、第2の部分は0でない
ターミネータ(terminator)係数のハッシュ値である。
図53にアルファベット・フォーマットを示すが、これ
は0係数の数、換言すれば、そのランの長さを示す4ビ
ットと、それに続く0から15までのハッシュ値を表す
4ビットとからなる。
【0434】このハッシュ値は値Nであり、このNは0
でないターミネータ係数の絶対値の、2を底とする対数
の整数部分である。一実施例では、このハッシュ値は値
Nを表すのに必要なビット数である。例えば、N=−
1,1の場合、ハッシュ値は1である。他方、N=−
3,−2,2,3の場合、値Nを表すのに必要なビット
数は2である。同様の対応はJPEGに用いられてい
る。
【0435】このようなシチュエーションでは、許容さ
れる0係数のランの最大長は15である。ランが15を
超えるときには、0が16個のランの後に新たなランが
続くことを表すため特殊なトークンが使われるであろ
う。このような例外トークンの一つは、最初の4ビット
と最後の4ビットの両方とも全部0である。一実施例で
は、2番目の4ビットが0の16個のトークンが全部、
例外ケースのために用いられる。したがって、256個
の8ビットのハフマン・トークンがある。
【0436】一実施例では、ハフマン・トークンに関す
るテーブルが作られる。一実施例では、そのテーブルが
全ての画像に対して用いられる。別の実施例では、多く
のテーブルが作成され、量子化に応じて1つの特定のテ
ーブルが選ばれる。各テーブルは、量子化しようとする
ビット数に基づいて選択される。すなわち、量子化する
ビット数が1ビット、2ビット、3ビット等々であるか
によって、テーブルがそれぞれ選択されるわけである。
別の実施例では、ハフマン符号は特定画像向けのもので
あり、画像と一緒に記憶/伝送される。
【0437】テーブルを利用するために、一つのハフマ
ン・トークンが生成される。そして、このトークンが、
それが符号化されるテーブルに送られる。
【0438】ハフマン・トークンは0のランの長さ及び
非0のターミネータ・シンボルのハッシュ値を特定する
が、ターミネータ・シンボルを一意的に特定するために
割増のビットが必要になる。本発明の一実施例は、これ
ら割増ビットを用意する。ハフマン・トークンが(例え
ばテーブル等から得られる)ハフマン符号語で置き換え
られた後、ターミネータ・シンボルのハッシュ値に等し
い割増ビットが書かれる。例えば、−1,1のケースで
は割増の1ビットが書かれるが、−3,−2,2,3の
ケースにおいては割増の2ビットが書かれる。このよう
に、本発明は、ターミネータ・シンボルを一意的に特定
する、割増ビットによってサイズが可変のハフマン符号
化を提供する。
【0439】なお、他のm元コーダを用いてもよい。例
えば、あるアルファベットとm元符号を0係数のために
用い、別のアルファベットとm元符号をハッシュ値のた
めに用いてもよい。
【0440】一実施例では、量子化レベル毎のハフマン
・テーブルのセットが予め計算され、殆どの画像に対し
て利用される。様々なテーブル間で選択するために、あ
るテーブルを使用中に圧縮がモニタされるであろう。そ
のテーブルを使用した結果に基づいて、スキューがもっ
と大きい又は小さいテーブルへの切り替えが行われるで
あろう。
【0441】本発明の係数はすべて、あるバッファに入
れられる。各バッファ毎に、どのテーブルを使用すべき
かの決定がなされるであろう。8つのハフマン・テーブ
ルのどれを利用すべきか指示するため、3ビットと1つ
のヘッダが用いられるかもしれない。しかして、そのヘ
ッダを知らせることによって、テーブル選択がなされる
であろう。
【0442】係数が符号化される順序は重要である。従
来技術の係数符号化では、例えばJPEGでは、係数は
ジグザグ順に圧縮されることに注意されたい。本発明に
おいては、係数全部があるバッファ内にあるので、ジグ
ザグ順にすることはできない。ジグザグ順は、低い周波
数から高い周波数への順序と理解されるなら、埋め込み
ウェーブレットによる圧縮(ツリー順)に拡張すること
ができる。
【0443】一実施例では、バッファ全体について直線
的な順序で係数が符号化される。そのような例を図54
に示す。なお、この実施例において、平滑係数の最初の
ブロックは除外されることに注意されたい。
【0444】別の実施例では、すべてのブロックは、低
い周波数のブロックより高い周波数のブロックへと、ラ
スター順に符号化される。そのような例を図54(B)
に示す。メモリの制約のため、1つの周波数パスの全部
は、別の周波数パスが始まる前に完了しないかもしれな
い。メモリによって制限される場合、もう一つの方法は
1つのツリーを一度に符号化する方法である。ルートか
ら初めて、すべてのツリーが横方向に符号化される。た
だし、平滑係数であるところのルートは含めない。この
方法が図54(C)に示されている。図54(C)には
最初のツリーが示されており、最初のサブブロックのセ
ットより1ラインが取られ、その次のサブブロックのセ
ットより2ラインが取られ、その次のサブブロックのセ
ットより4ラインが取られる。これらラインは他のライ
ンが利用可能になる以前に利用可能であるため、このよ
うな実施例が可能である。
【0445】残りのツリーが0係数からなることを示す
ため、例外トークンを保存してもよい。これは、16個
の0を示す同じトークンが何度も何度も使用されないよ
うにする。
【0446】一実施例では、全ての重要性レベルがハフ
マン符号化によって符号化される。別の実施例では、複
数の重要性レベルからなる1又は複数のグループがハフ
マン符号化によって符号化される。別々のグループ毎に
全ての重要性レベルをハフマン符号化により符号化して
もよいし、あるいは、一部の重要性レベルをハフマン符
号化で符号化し、残りの重要性レベルを水平コンテキス
トモデルとバイナリ・エントロピー・コーダにより符号
化してもよい。
【0447】重要性レベルの1グループのハフマン符号
化による符号化は、以下のように行われる。そのグルー
プ内の重要性レベルの係数のビットが全てヘッドビット
のときには、その係数は0係数として(多分、ラン・カ
ウントの一部として)ハフマン符号化される。その係数
のビットが全てテールビットならば、それらビットは
(多分、ランを終結させる)割増ビットとして符号化さ
れる。ハフマン符号語は使われない。その係数のビット
が(ヘッドビット又はテールビットのほかに)に符号(s
ign)ビットを含んでいるときには、(多分、ランを終結
させる)ハフマン符号語と割増ビットの両方が符号化さ
れる。
【0448】複数の重要性レベルをハフマン符号化すれ
ば、実行コストは減少する。しかし、ハフマン符号化デ
ータの中途での打ち切りは、レート・歪みの悪化を招
く。重要性レベルのグループをハフマン符号化すれば、
レート・歪みが良好になるようグループの始まり/終わ
りでの打ち切りが可能になる。用途によっては、限定数
の必要とされる量子化点が符号化時に分かっている。量
子化点のない重要性レベルは、それに続くレベルと一緒
にしてハフマン符号化することができる。
【0449】用途 本発明は多くの用途に利用できる。そのような用途のい
くつかを例として以下に述べる。具体的には、解像度が
高く画素深度が大きいハンエンドの用途及びアーティフ
ァクト(artifact)を許容しない用途に、本発明を利用で
きる。本発明によれば、ハイエンドの用途は高品質環境
で最高品質を維持でき、同時に、帯域幅、データ記憶又
は表示機能がさらに制限される用途でも同じ圧縮データ
を利用可能である。これはまさに、ウエブ・ブラウザの
ような近頃の画像応用分野に一般に要求される装置独立
な表現である。
【0450】画素深度の深い画像(10ビット〜16ビ
ット/画素)に対する本発明の優れた非損失圧縮性能
は、医用画像のために理想的である。非損失性圧縮のみ
ならず、本発明は、ブロックベース圧縮装置に知られて
いる多くのアーティファクトのない真の損失性圧縮装置
である。本発明を利用することに由来する損失性アーテ
ィファクトは、急峻なエッジに沿う傾向があるので、人
間の視覚系の視覚マスキング現象によって見えないこと
が多い。
【0451】本発明は、画像が非常に高解像度で高い画
素深度を持つことの多いプリプレス(pre-press)業に関
連した用途に利用できる。本発明のピラミッド分解によ
れば、プリプレス・オペレータが(モニタ上の)画像の
低解像度損失性バージョンに対し画像処理操作を行うの
が容易である。操作が終わったならば、同じ操作を非損
失性バージョンに対して実行できる。
【0452】本発明は、圧縮しないと送信に要する時間
があまりに長くなりやすいファクシミリ文書の用途にも
適用可能である。本発明によれば、様々な空間解像度及
び画素解像度のファクス装置より、非常に高品位の画像
出力が可能になる。
【0453】本発明は、圧縮を必要とする画像アーカイ
ブシステムに、特に記憶容量を増加させるために、利用
することもできる。本発明の装置独立な出力は、帯域幅
が異なる資源、メモリ及びディスプレイを持つシステム
により画像アーカイブシステムをアクセスでき、有益で
ある。本発明のプログレッシブ伝送機能は、ブラウジン
グのためにも有益である。最後に、画像アーカイブシス
テムの出力装置用に望ましい非損失性圧縮が本発明によ
り提供される。
【0454】本発明の非損失性又は高品質損失性データ
ストリームの階層プログレッシブ性により、本発明はワ
ールド・ワイド・ウェブ用に、特に装置独立性、プログ
レッシブ伝送及び高品質が必須な場合に理想的である。
【0455】本発明は、衛星画像、特に高画素深度及び
高解像度になる傾向のある衛星画像にも適用できる。さ
らに、衛星画像の用途は通信路の帯域幅が制限される。
本発明はフレキシビリティがあり、またプログレッシブ
伝送特性があるので、本発明を利用すれば人間による画
像のブラウジング又はプレビューが可能になろう。
【0456】ATMネットワークのような”固定レー
ト”で帯域幅が制限される用途は、データが利用可能な
帯域幅をオーバーフローしたときにデータを減少させる
手段を必要とする。しかしながら、十分な帯域幅がある
ときには(あるいはデータが高度に圧縮可能なときに
は)、品質上の不利益があってはならない。同様に、コ
ンピュータや他の画像装置におけるメモリが制限された
フレーム記憶装置のような”固定サイズ”の用途も、メ
モリが満杯になったときにデータを減少させる手段を必
要とする。繰り返すが、適当なメモリ量に非損失圧縮す
ることが可能な画像に対して不利益があってはならな
い。
【0457】本発明の埋め込み符号ストリームは、これ
ら両方の用途にかなう。埋め込み操作は、損失性画像の
伝送又は記憶のために符号ストリームが切り捨てもしく
は打ち切りされることを無条件に許す。切りつめもしく
は打ち切りが必要でなければ、画像は非損失で届く。
【0458】要するに、本発明は、単一連続階調画像圧
縮システムを提供する。本発明のシステムは、同じ符号
ストリームに対して非損失性かつ損失性であり、埋め込
みの量子化(符号ストリームに含まれる)を利用する。
本発明のシステムはまた、ピラミッド型であり、プログ
レッシブであり、補間手段を提供し、かつ、実施が容易
である。したがって、本発明はフレキシブルな”装置独
立の”圧縮システムを提供する。
【0459】統合型の損失性及び非損失性圧縮システム
は非常に有用である。同じシステムで最新の損失性及び
非損失性圧縮を実行でき、その上、同じ符号ストリーム
である。このシステムは、画像の非損失性符号を保存す
るか打ち切って損失性バージョンにするかを、符号化
中、符号ストリームの格納又は伝送中あるいは復号化中
に決定することができる。
【0460】本発明により提供される損失性圧縮は、埋
め込み量子化によって達成される。すなわち、符号スト
リームは量子化を含んでいる。実際の量子化(又は視覚
的重要性)レベルは、復号化器又は通信路との相関点要
素であることもあり、必ずしも符号化器との相関的要素
ではない。バンド幅、記憶及びディスプレイ資源が許す
なら、画像は非損失で復元される。そうでないならば、
画像は最も制約された資源に要求されるだけ量子化され
る。
【0461】本発明に用いられるウエーブレットはピラ
ミッド型であり、差分画像のない、画像の1/2分解が
実行される。これは非常に特殊な階層分解である。画像
のブラウジングのため又は低解像度装置による表示のた
めに縮小画像(thumbnails)を必要とする用途に、本発明
のピラミッド性は理想的である。
【0462】本発明における埋め込みの使い方はプログ
レッシブであり、より具体的にはビットプレーン順であ
る、すなわちMSBの後に下位ビットが続く順である。
具体的には本発明はウエーブレット領域においてプログ
レッシブであるが、空間領域及びウエーブレット領域の
両方ともプログレッシブに分解してもよい。プリンタの
ような、空間解像度はあるが画素解像度は低い用途にと
って、本発明におけるビットのプログレッシブな順序づ
けは理想的である。これらの特徴を同一符号ストリーム
で得られる。
【0463】本発明は、ソフトウエアでもハードウエア
でも比較的容易に実施できる。ウエーブレット変換は、
ハイパス、ローパスの各係数ペアにつき4つの加算/減
算操作と、いくつかのシフトだけで計算することができ
る。埋め込み及び符号化は、単純な”コンテキストモデ
ル”とバイナリ又はm元”エントロピー・コーダ”によ
って実行される。このエントロピー・コーダは、有限状
態マシン、並列コーダ又はハフマン・コーダによって実
現できる。
【0464】
【発明の効果】以上の説明から明らかな如く、本発明の
データ圧縮システムによれば、良好なエネルギー集中を
もたらす変換を利用し画像データ等の効率的な損失性又
は非損失性の圧縮が可能であり、また、自然連続階調の
画像、2値/ノイズフリー/浅画素深度の画像、及び、
その両方の種類のデータを含む画像を同じシステムで適
切に処理することができ、さらに、様々な解像度/品質
の画像フォーマットを柔軟にサポートすることができ、
またさらに、パーサは符号データを伸長することなく、
画像出力装置の特性に応じて符号データストリームの適
切な量子化を行うことができる等々の効果を有するもの
である。
【図面の簡単な説明】
【図1】本発明の圧縮システムの一実施例のブロック図
である。
【図2】バイナリ方式における各ビットプレーンの各ビ
ットに対するコンテキストモデルの可能な幾何学的関係
の一例を示す図である。
【図3】バイナリ方式における各ビットプレーンの各ビ
ットに対するコンテキストモデルの可能な幾何学的関係
の一例を示す図である。
【図4】第1レベルの分解を示す図である。
【図5】第2レベルの分解を示す図である。
【図6】第3レベルの分解を示す図である。
【図7】第4レベルの分解を示す図である。
【図8】前後2レベル間の親子関係を示す。
【図9】TT変換だけを利用するウエーブレット分解過
程の一例を示す図である。
【図10】TT変換とS変換を利用するウエーブレット
分解過程の一例を示す図である。
【図11】画像のタイリングの説明図である。
【図12】ビット・シグニフィカンス表現の例を示す図
である。
【図13】本発明における係数サイズを示す図である。
【図14】本発明における係数アラインメントのために
使われる周波数帯域用乗数の例を示す図である。
【図15】符号ストリームの構成の一例を示す図であ
る。
【図16】係数(又は画素)間の隣接関係を示す図であ
る。
【図17】テール・ビット処理プロセスのフローチャー
トである。
【図18】本発明の符号化プロセスの一例のフローチャ
ートである。
【図19】本発明の復号化プロセスの一例のフローチャ
ートである。
【図20】本発明のモデリング・プロセスのフローチャ
ートである。
【図21】モデリング・プロセスに利用可能なテンプレ
ートを示す図である。
【図22】TT変換フィルタの一部分の一例を示すブロ
ック図である。
【図23】本発明のスクロール・バッファの説明図であ
る。
【図24】本発明に採用されるメモリ操作の説明図であ
る。
【図25】3レベル用メモリ・バッファの2次元表現を
示す図である。
【図26】本発明の符号ストリームの一例を示す図であ
る。
【図27】パーサを備えた圧縮システムのブロック図で
ある
【図28】図27の圧縮システムに対応する伸長システ
ムのブロック図である。
【図29】コンテキスト従属関係を示す図である。
【図30】画素深度及び空間解像度の面から定義された
用途を示す図である。
【図31】パーサ、復号化器及びそれらの出力装置との
相互作用の一例を示すブロック図である。
【図32】量子化選択装置の一例を示すブロック図であ
る。
【図33】符号ストリーム中の区切りタグの配置を示す
図である。
【図34】SIZタグの説明図である。
【図35】CODタグの説明図である。
【図36】ALGタグの説明図である。
【図37】TLMタグの説明図である。
【図38】TLTタグの説明図である。
【図39】CPTタグの説明図である。
【図40】IRSタグの説明図である。
【図41】VERタグの説明図である。
【図42】BVIタグの説明図である。
【図43】ILLタグの説明図である。
【図44】RXYタグの説明図である。
【図45】CMTタグの説明図である。
【図46】QCSタグの説明図である。
【図47】損失性再構成のための典型的分布を示すグラ
フである。
【図48】典型的な係数を示す図である。
【図49】テール情報解析プロセスのフローチャートで
ある。
【図50】MSEアラインメント法を説明するための図
である。
【図51】ピラミッド・アラインメント法を説明するた
めの図である。
【図52】メモリ記憶係数とアラインメントの間の典型
的な関係を示す図である。
【図53】符号語の一例を示す図である。
【図54】ハフマン符号化法による係数の構文解析の方
法を説明するための図である。
【図55】ユニットバッファを用い第2レベルのウェー
ブレット分解を実行する場合の2Dメモリの中間形式を
示す図である。
【図56】ユニットバッファを用い第3レベルのウェー
ブレット分解を実行する場合の2Dメモリの中間型式を
示す図である。
【符号の説明】
101 入力画像データ 102 可逆ウェーブレット変換ブロック 103 埋め込み順序付け量子化ブロック 104 グレイ(Gray)符号化ブロック 105 水平コンテキストモデル・ブロック 106 エントロピー・コーダ 110 方式選択機構 111 多成分処理機構 1001 ヘッダ 1002 符号化単位 1003 LL係数 1004 第1ビットプレーン 1005 第2ビットプレーン 1006 最終ビットプレーン 1501 乗算器 1502 加算器 1503 乗算器 1504 乗算器 1505 加算器 1601 ラインアクセスバッファ 1602 バッファ 1901 ヘッダ 1902 LL係数 1903 エントロピー符号化データ 2101 圧縮されていない原画像 2102 圧縮装置 2103 マーカ付き非損失性圧縮ビットストリーム 2104 パーサ 2106 通信路又は記憶装置 2107 伸長装置 2108 伸長画像 2401 マーカ付きの非損失性圧縮データ 2402 パーサ 2403 通信路 2404 伸長装置 2405 ディスプレイ・モジュール 2500 符号ストリーム 2501 量子化を含む伸長 2502 画像処理又は歪みモデル 2503 非損失性伸長 2504 画像処理又は歪みモデル 2505 MSE又はHVS差モデル 2506 アラインメント調整 2801 係数 2802 符号ビット 2803 テールオン情報 2804 コンテキストビット 2805 係数ビット
─────────────────────────────────────────────────────
【手続補正書】
【提出日】平成9年7月2日
【手続補正1】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正内容】
【図1】
【図2】
【図3】
【図11】
【図12】
【図16】
【図41】
【図4】
【図5】
【図6】
【図13】
【図21】
【図22】
【図35】
【図38】
【図7】
【図8】
【図9】
【図14】
【図28】
【図29】
【図10】
【図15】
【図24】
【図26】
【図30】
【図36】
【図37】
【図39】
【図40】
【図42】
【図43】
【図44】
【図17】
【図18】
【図19】
【図23】
【図45】
【図46】
【図20】
【図27】
【図53】
【図25】
【図31】
【図33】
【図32】
【図34】
【図47】
【図48】
【図49】
【図50】
【図51】
【図54】
【図52】
【図55】
【図56】
───────────────────────────────────────────────────── フロントページの続き (72)発明者 アーマド ザンディ アメリカ合衆国 カリフォルニア州 94025 メンローパーク サンド ヒル ロード 2882 リコーコーポレーション内 (72)発明者 マーティン ボーリック アメリカ合衆国 カリフォルニア州 94025 メンローパーク サンド ヒル ロード 2882 リコーコーポレーション内 (72)発明者 マイケル ジェー ゴーミッシュ アメリカ合衆国 カリフォルニア州 94025 メンローパーク サンド ヒル ロード 2882 リコーコーポレーション内

Claims (43)

    【特許請求の範囲】
  1. 【請求項1】 可逆埋め込みウェーブレットにより画像
    データを圧縮するウェーブレット方式のコーダ、 バイナリ符号化スキームにより画像データを圧縮するバ
    イナリ方式のコーダ、及びウェーブレット方式又はバイ
    ナリ方式を選択するために接続された選択制御部からな
    るデータ圧縮システム。
  2. 【請求項2】 請求項1記載のデータ圧縮システムにお
    いて、ウェーブレット方式のコーダは、可逆ウェーブレ
    ット変換部、該可逆ウェーブレット変換部に接続された
    埋め込み順序付け量子化器、及び、該埋め込み順序付け
    量子化器に接続されたコンテキストモデルからなること
    を特徴とするデータ圧縮システム。
  3. 【請求項3】 請求項1記載のデータ圧縮システムにお
    いて、ウェーブレット方式のコーダはエントロピー・コ
    ーダをさらに含むことを特徴とするデータ圧縮システ
    ム。
  4. 【請求項4】 請求項1記載のデータ圧縮システムにお
    いて、ウェーブレット方式はグレイ符号化を実行するこ
    とを特徴とするデータ圧縮システム。
  5. 【請求項5】 請求項1記載のデータ圧縮システムにお
    いて、ウェーブレット方式とバイナリ方式は一つの符号
    化器を共有することを特徴とするデータ圧縮システム。
  6. 【請求項6】 エントロピー・コーダをさらに含むこと
    を特徴する請求項1記載のデータ圧縮システム。
  7. 【請求項7】 請求項6記載のデータ圧縮システムにお
    いて、エントロピー・コーダは有限状態マシン・コーダ
    からなることを特徴とするデータ圧縮システム。
  8. 【請求項8】 請求項7記載のデータ圧縮システムにお
    いて、有限状態マシン・コーダはルックアップテーブル
    からなることを特徴とするデータ圧縮システム。
  9. 【請求項9】 請求項6記載のデータ圧縮システムにお
    いて、エントロピー・コーダはQコーダからなることを
    特徴とするデータ圧縮システム。
  10. 【請求項10】 請求項6記載のデータ圧縮システムに
    おいて、エントロピー・コーダはQMコーダからなるこ
    とを特徴とするデータ圧縮システム。
  11. 【請求項11】 請求項6記載のデータ圧縮システムに
    おいて、エントロピー・コーダは並列コーダからなるこ
    とを特徴とするデータ圧縮システム。
  12. 【請求項12】 可逆ウェーブレット変換部、 該可逆ウェーブレット変換部に接続された埋め込み順序
    付け量子化器、 該埋め込み順序付け量子化器に接続されたコンテキスト
    モデル、 埋め込みバイナリ方式符号化機構、及び該コンテキスト
    モデル及び該埋め込みバイナリ方式符号化機構に接続さ
    れたエントロピー・コーダを含み、該可逆ウェーブレッ
    ト変換、該埋め込み順序付け量子化器及び該コンテキス
    トモデルは可逆埋め込みウェーブレットにより画像デー
    タを圧縮するように動作可能であり、該バイナリ方式符
    号化機構はバイナリ符号化スキームにより画像データを
    圧縮するように動作可能であり、さらに、 ウェーブレット方式又はバイナリ方式を選択するために
    接続された選択制御部を含んでなるデータ圧縮システ
    ム。
  13. 【請求項13】 請求項12記載のデータ圧縮システム
    において、バイナリ方式はグレイ符号化を実行すること
    を特徴とするデータ圧縮システム。
  14. 【請求項14】 請求項12記載のデータ圧縮システム
    において、エントロピー・コーダは有限状態マシン・コ
    ーダからなることを特徴とするデータ圧縮システム。
  15. 【請求項15】 請求項14記載のデータ圧縮システム
    において、有限状態マシン・コーダはルックアップテー
    ブルからなることを特徴とするデータ圧縮システム。
  16. 【請求項16】 請求項12記載のデータ圧縮システム
    において、エントロピー・コーダはQコーダからなるこ
    とを特徴とするデータ圧縮システム。
  17. 【請求項17】 請求項12記載のデータ圧縮システム
    において、エントロピー・コーダはQMコーダからなる
    ことを特徴とするデータ圧縮システム。
  18. 【請求項18】 請求項12記載のデータ圧縮システム
    において、エントロピー・コーダは並列コーダからなる
    ことを特徴とするデータ圧縮システム。
  19. 【請求項19】 請求項17記載のデータ圧縮システム
    において、フォワード変換は可逆ウェーブレットからな
    ることを特徴とするデータ圧縮システム。
  20. 【請求項20】 ヒストグラム圧縮機構、 該ヒストグラム圧縮機構に接続された可逆ウェーブレッ
    ト変換部、 該可逆ウェーブレット変換部に接続された埋め込み順序
    付け量子化器、 該埋め込み順序付け量子化器に接続されたコンテキスト
    ・モデリング機構、及び該コンテキスト・モデリング機
    構に接続されたコーダからなるシステム。
  21. 【請求項21】 請求項20記載のシステムにおいて、
    ヒストグラム圧縮機構はブーリアンヒストグラムを作る
    ことを特徴とするデータ圧縮システム。
  22. 【請求項22】 請求項20記載のデータ圧縮システム
    において、ヒストグラム圧縮機構は整数値を画像データ
    中の全ての可能な画素値に写像することを特徴とするデ
    ータ圧縮システム。
  23. 【請求項23】 ヒストグラム圧縮機構で利用されたマ
    ッピングを復号化器に通知するために接続された通知機
    構をさらに含むことを特徴する請求項20記載のデータ
    圧縮システム。
  24. 【請求項24】 請求項23記載のデータ圧縮システム
    において、マッピングは復号化器に受け取られた圧縮デ
    ータに含まれるヘッダで通知されることを特徴とするデ
    ータ圧縮システム。
  25. 【請求項25】 請求項23記載のデータ圧縮システム
    において、ヘッダ中の1つのビットが、それがセットさ
    れたときに、カレント・タイルのために別のヒストグラ
    ムが利用されることを復号化器に指示することを特徴と
    するデータ圧縮システム。
  26. 【請求項26】 請求項23記載のデータ圧縮システム
    において、復号化器は、値のダイナミックレンジと等し
    い、ある数のビットを送ることによって通知され、該あ
    る数のビット中の各ビットはダイナミックレンジ内の対
    応した値が使われるときにセットされることを特徴とす
    るデータ圧縮システム。
  27. 【請求項27】 少なくとも1つのマーカーを持つヘッ
    ダを有する符号ストリームを格納するメモリ、 少なくとも1つの出力装置、 該メモリに接続され、かつ、該少なくとも1つの出力装
    置より装置特性を受け取るように接続されたパーサから
    なり、該パーサは装置依存の量子化を実行するように動
    作可能であるデータ圧縮システム。
  28. 【請求項28】 請求項27記載のデータ圧縮システム
    において、符号ストリームは非損失性圧縮データからな
    ることを特徴とするデータ圧縮システム。
  29. 【請求項29】 請求項27記載のデータ圧縮システム
    において、少なくとも1つのマーカーは符号ストリーム
    中の各タイルのために用いられた成分の数、サブサンプ
    リング及びアラインメントを示すことを特徴とするデー
    タ圧縮システム。
  30. 【請求項30】 請求項27記載のデータ圧縮システム
    において、符号ストリームは主ヘッダを含み、符号スト
    リーム中の各タイルの前にローカルヘッダが置かれるこ
    とを特徴とするデータ圧縮システム。
  31. 【請求項31】 請求項30記載のデータ圧縮システム
    において、主ヘッダは符号ストリーム中の全てのタイル
    に適用され、各ローカルヘッダは関連したタイルにのみ
    適用されることを特徴とするデータ圧縮システム。
  32. 【請求項32】 請求項31記載のデータ圧縮システム
    において、ローカルヘッダ中の少なくとも1つは主ヘッ
    ダに優先することを特徴とするデータ圧縮システム。
  33. 【請求項33】 請求項27記載のデータ圧縮システム
    において、パーサは符号ストリーム中のマーカーを符号
    ストリームを量子化するために利用することを特徴とす
    るデータ圧縮システム。
  34. 【請求項34】 請求項33記載のデータ圧縮システム
    において、マーカー中の少なくとも1つは周波数情報を
    示すことを特徴とするデータ圧縮システム。
  35. 【請求項35】 符号ストリームを生成するための圧縮
    装置をさらに含むことを特徴とする請求項27記載のデ
    ータ圧縮システム。
  36. 【請求項36】 請求項27記載のデータ圧縮システム
    において、パーサは量子化選択装置からなることを特徴
    とするデータ圧縮システム。
  37. 【請求項37】 請求項36記載のデータ圧縮システム
    において、量子化選択装置は画像の集合の変換及び量子
    化を、様々な係数のビットプレーンを捨てることによっ
    て行うことを特徴とするデータ圧縮システム。
  38. 【請求項38】 請求項27記載のデータ圧縮システム
    において、タグの1つは各タイル中のデータ内の重要性
    レベルを示すことを特徴とするデータ圧縮システム。
  39. 【請求項39】 請求項27記載のデータ圧縮システム
    において、タグは重要性レベルロケータ信号を示し、該
    信号に従って該パーサは打ち切りをすることを特徴とす
    るデータ圧縮システム。
  40. 【請求項40】 請求項27記載のデータ圧縮システム
    において、タグは保存すべき重要性レベルの数を示すこ
    とを特徴とするデータ圧縮システム。
  41. 【請求項41】 請求項27記載のデータ圧縮システム
    において、タグは保存すべきバイトの数を示すことを特
    徴とするデータ圧縮システム。
  42. 【請求項42】 請求項27記載のデータ圧縮システム
    において、タグは重要性レベルとバイト数を関連付ける
    指示を各タイルに含むことを特徴とするデータ圧縮シス
    テム。
  43. 【請求項43】 請求項33記載のデータ圧縮システム
    において、少なくとも1つのマーカーは各タイル中の重
    要性レベルのバイト数を示すことを特徴とするデータ圧
    縮システム。
JP10979097A 1996-05-03 1997-04-25 データ圧縮システム Expired - Fee Related JP3989999B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/642518 1996-05-03
US08/642,518 US5881176A (en) 1994-09-21 1996-05-03 Compression and decompression with wavelet style and binary style including quantization by device-dependent parser

Related Child Applications (1)

Application Number Title Priority Date Filing Date
JP2005044810A Division JP2005218124A (ja) 1996-05-03 2005-02-21 データ圧縮システム

Publications (2)

Publication Number Publication Date
JPH1084484A true JPH1084484A (ja) 1998-03-31
JP3989999B2 JP3989999B2 (ja) 2007-10-10

Family

ID=24576918

Family Applications (2)

Application Number Title Priority Date Filing Date
JP10979097A Expired - Fee Related JP3989999B2 (ja) 1996-05-03 1997-04-25 データ圧縮システム
JP2005044810A Pending JP2005218124A (ja) 1996-05-03 2005-02-21 データ圧縮システム

Family Applications After (1)

Application Number Title Priority Date Filing Date
JP2005044810A Pending JP2005218124A (ja) 1996-05-03 2005-02-21 データ圧縮システム

Country Status (1)

Country Link
JP (2) JP3989999B2 (ja)

Cited By (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2002159009A (ja) * 2000-09-01 2002-05-31 Canon Inc エントロピ符号化及び復号化方法とその装置
US6792150B1 (en) 1999-11-02 2004-09-14 Ricoh Company, Ltd. Method, apparatus and computer program product for image data compression and decompression capable of high-speed processing
JP2005205746A (ja) * 2004-01-23 2005-08-04 Fuji Xerox Co Ltd 画像形成システム並びにその制御装置、制御方法及び制御プログラム
US7349579B2 (en) 2001-09-25 2008-03-25 Ricoh Company, Ltd. Image processing device, image processing method, and image reading method
US7751586B2 (en) 2004-09-29 2010-07-06 Ricoh Company, Ltd. Image processing apparatus, image processing method, and computer product
US8179548B2 (en) 2006-06-06 2012-05-15 Ricoh Company, Ltd. Apparatus and method for data processing
EP3435240A1 (en) * 2017-07-28 2019-01-30 Apple Inc. Systems and methods for performing memory compression
CN110750757A (zh) * 2019-10-29 2020-02-04 哈尔滨工业大学 一种基于灰度线性建模及金字塔分解的图像抖动量计算方法
CN111049527A (zh) * 2019-12-23 2020-04-21 云南大学 一种图像编码解码方法
CN116245711A (zh) * 2021-12-08 2023-06-09 西安电子科技大学青岛计算技术研究院 一种基于arm-neon移位指令的图像快速量化方法

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2429593A (en) 2005-08-26 2007-02-28 Electrosonic Ltd Data compressing using a wavelet compression scheme
WO2008126139A1 (ja) * 2007-03-30 2008-10-23 Fujitsu Limited 画像データ圧縮装置及び復号装置
US9992252B2 (en) 2015-09-29 2018-06-05 Rgb Systems, Inc. Method and apparatus for adaptively compressing streaming video
CN112188200A (zh) * 2020-09-30 2021-01-05 深圳壹账通智能科技有限公司 一种图像处理方法、装置、设备及储存介质
US12579610B2 (en) 2022-05-25 2026-03-17 Intel Corporation Lossy compression technology for small image tiles

Cited By (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6792150B1 (en) 1999-11-02 2004-09-14 Ricoh Company, Ltd. Method, apparatus and computer program product for image data compression and decompression capable of high-speed processing
US7020341B2 (en) 1999-11-02 2006-03-28 Ricoh Company, Ltd. Method, apparatus and computer program product for image data compression and decompression capable of high-speed processing
JP2002159009A (ja) * 2000-09-01 2002-05-31 Canon Inc エントロピ符号化及び復号化方法とその装置
US7349579B2 (en) 2001-09-25 2008-03-25 Ricoh Company, Ltd. Image processing device, image processing method, and image reading method
JP2005205746A (ja) * 2004-01-23 2005-08-04 Fuji Xerox Co Ltd 画像形成システム並びにその制御装置、制御方法及び制御プログラム
US7751586B2 (en) 2004-09-29 2010-07-06 Ricoh Company, Ltd. Image processing apparatus, image processing method, and computer product
US8179548B2 (en) 2006-06-06 2012-05-15 Ricoh Company, Ltd. Apparatus and method for data processing
CN109308192A (zh) * 2017-07-28 2019-02-05 苹果公司 用于执行存储器压缩的系统和方法
EP3435240A1 (en) * 2017-07-28 2019-01-30 Apple Inc. Systems and methods for performing memory compression
US10331558B2 (en) 2017-07-28 2019-06-25 Apple Inc. Systems and methods for performing memory compression
EP3671471A1 (en) * 2017-07-28 2020-06-24 Apple Inc. Systems and methods for performing memory compression
US10769065B2 (en) 2017-07-28 2020-09-08 Apple Inc. Systems and methods for performing memory compression
CN109308192B (zh) * 2017-07-28 2023-07-21 苹果公司 用于执行存储器压缩的系统和方法
CN110750757A (zh) * 2019-10-29 2020-02-04 哈尔滨工业大学 一种基于灰度线性建模及金字塔分解的图像抖动量计算方法
CN110750757B (zh) * 2019-10-29 2023-04-07 哈尔滨工业大学 一种基于灰度线性建模及金字塔分解的图像抖动量计算方法
CN111049527A (zh) * 2019-12-23 2020-04-21 云南大学 一种图像编码解码方法
CN116245711A (zh) * 2021-12-08 2023-06-09 西安电子科技大学青岛计算技术研究院 一种基于arm-neon移位指令的图像快速量化方法

Also Published As

Publication number Publication date
JP3989999B2 (ja) 2007-10-10
JP2005218124A (ja) 2005-08-11

Similar Documents

Publication Publication Date Title
US7634145B2 (en) Compression and decompression with wavelet style and binary style including quantization by device-dependent parser
US5966465A (en) Compression/decompression using reversible embedded wavelets
US6757437B1 (en) Compression/decompression using reversible embedded wavelets
US7289677B2 (en) Reversible embedded wavelet system implementation
US7016545B1 (en) Reversible embedded wavelet system implementation
JP3653183B2 (ja) ウェーブレット係数再構成処理方法及び装置、並びに記録媒体
US6873734B1 (en) Method and apparatus for compression using reversible wavelet transforms and an embedded codestream
CN100568969C (zh) 可逆子波变换和嵌入代码流处理方法
US6195465B1 (en) Method and apparatus for compression using reversible wavelet transforms and an embedded codestream
US7492955B2 (en) Method and apparatus for compression using reversible wavelet transforms and an embedded codestream
JP2007267384A (ja) 圧縮装置及び圧縮方法
JP3989999B2 (ja) データ圧縮システム
GB2313757A (en) Method using an embedded codestream
Lossless Compress System couple crowd lax lena man woman1 woman2

Legal Events

Date Code Title Description
A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20041221

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20050221

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20050426

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20050627

A911 Transfer of reconsideration by examiner before appeal (zenchi)

Free format text: JAPANESE INTERMEDIATE CODE: A911

Effective date: 20050701

A912 Removal of reconsideration by examiner before appeal (zenchi)

Free format text: JAPANESE INTERMEDIATE CODE: A912

Effective date: 20050722

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20070719

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100727

Year of fee payment: 3

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110727

Year of fee payment: 4

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120727

Year of fee payment: 5

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120727

Year of fee payment: 5

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130727

Year of fee payment: 6

LAPS Cancellation because of no payment of annual fees