JPH11225076A

JPH11225076A - データ圧縮方法

Info

Publication number: JPH11225076A
Application number: JP10274702A
Authority: JP
Inventors: James Philip Andrew; フィリップアンドリュージェームス; Andrew Peter Bradley; ペーターブラッドリーアンドリュー
Original assignee: Canon Information Systems Research Australia Pty Ltd; Canon Inc
Current assignee: Canon Information Systems Research Australia Pty Ltd; Canon Inc
Priority date: 1997-09-29
Filing date: 1998-09-29
Publication date: 1999-08-17
Also published as: CN1135847C; EP0905979A2; AUPO951497A0; US6263110B1; EP0905979B1; DE69840203D1; CN1218356A; EP0905979A3

Abstract

(57)【要約】（修正有）【課題】ウエーブレット変換された画像データの符号
化方法を提供する。【解決手段】データを異なる周波数特性を有する一連の
要素で、前記要素を各々一連の係数を含んだものに変換
し、コンパクト形式で２進数の数列を含んだ前記係数を
符号化し、前記符号化は、前記２進数の数列のうち先行
するゼロの番号を符号化するための第一の効率的な符号
化技術を提供すること含み、さらに、丸められた係数が
先行するゼロの効率的な符号化の有意性を変えないよう
に前記係数の丸めを含むものである。望ましくは、前記
丸めは有意でない係数の最初の番号を切捨てることと、
係数がゼロでない、より有意な係数に１を加えることを
含む。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、デジタルの画像圧
縮およびデジタルの映像圧縮に特有のアプリケーション
を有するデジタルデータ圧縮の分野に関連する。特に、
本発明は、符号化しているビット面を使用する画像圧縮
方法のための変換画像係数の効果的な量子化と関連し、
変換された画像と映像信号のビット面符号化に先がけ
た、効率的な丸めを含む。

【０００２】

【従来の技術】デジタルデータの圧縮、特にデジタルの
画像圧縮は、しばらくの間大きな関心が寄せられていた
分野である。デジタルの画像圧縮の分野では、多くの様
々な技術が利用されている。特に、1つのポピュラーな
技術が、画像の標準的なサイズのブロックを対応する余
弦要素に変換するための離散的な余弦変換（DCT）を利
用するJPEG基準である。この点において、より高い周波
数の余弦要素は、実体的な圧縮要因を得ることを補助す
るために密に量子化される。その密な量子化は画像圧縮
の「lossy」技術の一例である。JPEG基準は、また、変
換された係数の次のlossless圧縮に備える。

【０００３】最近では、ウエーブレット変換の分野はデ
ータ圧縮に代わる形式として大きい注目を集めている。
ウエーブレット変換は、鋭いエッジなどの切れ目を持っ
ている代表的なデータに非常に適していることが明らか
にされている。そのような切れ目は画像データまたはそ
れに類するデータでしばしば存在する。

【０００４】本発明の好ましい実施形態は画像データの
圧縮に関連して記述されるが、そこにおいて、好ましい
実施形態が制限されないことは明白である。信号に対す
るウエーブレット解析の様々な適用例に関しては、ブル
ース他による「ウエーブレット解析」1996年10月ページ
26-35のIEEEスペクトラムの一覧ができる。コンピュー
タ・グラフィックスにおけるウエーブレットの異なった
アプリケーションの議論のために、リファレンスはMorg
an Kaufmann Publishers , Inc.によって1996年出版さ
れた“Wavelets for Computer Graphics”、I. Stollin
itz他、によって作られる。

【０００５】画像圧縮の多くの効率的な方法は、変換画
像データのビット平面符号化を使用する。例えば、以下
の符号化方法は、変換（通常は離散的なウエーブレット
変換）画像データのビット面の符号化を効果的に使用す
る、米国特許5,412,741、5,315,670そして5,321,776の
方法に属するゼロ-ツリーウエーブレット (EZW) 及び変
換画像ビット平面の２進コンテキストエントロピー符号
化の例がある。これらの方法のうちのすべては、レート
／歪み／複雑トレードオフについて、現在利用可能な最
も競合する性能のうちのいくらかを提供する。

【０００６】ビット面符号化技術によって、通常、すべ
てのビット面が符号化される。下の最も重要なビット面
だけが、前もって決定された最小のビット面に符号化さ
れる。例えば、8ビットの２進表現10000111を有する係
数135の符号化を考慮し、下向きの係数のビット面の符
号化を伴ったビット面3を含む（最上位のビットで、ビ
ット面0から番号付を開始する）。係数は、それぞれビ
ット平面7, 6, 5, 4および3でビットである10000ビット
で、符号化される。デコーダは、この情報を受け取って
その時ビット面7、6、5、4、および3のこれらのビット
を複製できるが、下のビット面のビットは認識できな
い。下位のビット面で全てのビットが0であると仮定す
る代わりに、係数が135の場合は、デコーダがビット平
面2を1に仮定できる10000000の2進数（128の10進数）と
して復号される。そして、係数が135の場合で、他の下
位のビット面の0は10000100の2進数（132の10進数）と
して復号される。これは、丸めの一般化した形式であ
り、よりよい結果を一般に提供する。なぜなら、それは
復号された係数とオリジナルの（平均的な）違いを減ら
すからである。

【０００７】選択枝として、この一般化された丸めはエ
ンコーダにおいて実行される。ビット平面2の1は符号化
に先がけて135 （10000111+00000100＝10001011または1
39の小数）に付加され得る。下位のビット面3を続いて
符号化することで、係数は10001として符号化され、100
01000または136の10進数として復号される。実際、これ
は均一な量子化の簡単な形式である。

【０００８】効率的なビット面符号化技術に関して、例
えば、SWEET（以下を参照）やEZWファミリーなど、エン
コーダ（または、均一な量子化）において丸めることは
効率的ではなく、圧縮性能を低下させる。この理由は以
下において議論される。

【０００９】

【発明の概要】本発明の目的は、先行技術の1またはそ
れ以上の不利を改善することにある。

【００１０】本発明の第一の概要によると、提供される
データ符号化方法は、前記データを異なる周波数特性を
有する一連の要素で、前記要素は各々一連の係数を含ん
だものに変換し、コンパクト形式で前記係数を符号化
し、前記係数は２進数の数列を含み、前記符号化は、前
記２進数の数列のうち先行するゼロの番号を符号化する
ための第一の効率的な符号化技術を提供すること含み、
さらに、丸められた係数がその先行するゼロの番号を変
えないように前記係数の丸めを含む。

【００１１】本発明の第二の概要によると、提供される
データ符号化方法は、前記データを異なる周波数特性を
有する一連の要素で、前記要素は各々一連の係数を含ん
だものに変換し、前記要素を所定のブロックに分割し、
前記ブロックの各々について符号化し、前記係数はコン
パクト形式で、２進数の数列を含み、さらに前記符号化
は各々のブロックで最も大きな係数のうち先行するゼロ
の番号を符号化するための第一の効率的な符号化技術を
提供すること含み、さらに、丸められた係数は、前記ブ
ロックにおいて、最も大きいマグニチュードの先行する
ゼロの番号を変えないことを保証する丸めを含む。

【００１２】本発明の第三の概要によると、提供される
データ符号化装置は、前記データを異なる周波数特性を
有する一連の要素で、前記要素は各々一連の係数を含ん
だものに変換するための変換手段と、コンパクト形式で
前記係数を符号化し、前記係数は２進数の数列を含み、
前記符号化は、前記２進数の数列のうち先行するゼロの
番号を符号化するための第一の効率的な符号化技術を提
供すること含み、さらに、丸められた係数がその先行す
るゼロの番号を変えないように前記係数を丸めるための
エンコーダ手段と、を含む。

【００１３】本発明の第四の概要によると、提供される
データ符号化装置は、前記データを異なる周波数特性を
有する一連の要素で、前記要素は各々一連の係数を含ん
だものに変換するための変換手段と、前記要素を所定の
ブロックに分割するための分割手段と、前記ブロックの
各々について符号化し、前記係数はコンパクト形式で、
２進数の数列を含み、さらに前記符号化は各々のブロッ
クで最も大きな係数のうち先行するゼロの番号を符号化
するための第一の効率的な符号化技術を提供すること含
み、さらに、丸められた係数は、前記ブロックにおい
て、最も大きいマグニチュードの先行するゼロの番号を
変えないことを保証して丸めるためのエンコーダ手段
と、を含む。

【００１４】本発明の第五の概要によると、提供される
コンピュータプログラム製品は、データ符号化のための
コンピュータプログラムが記録されたコンピュータ可読
媒体を含み、前記コンピュータプログラム製品は、前記
データを異なる周波数特性を有する一連の要素で、前記
要素は各々一連の係数を含んだものに変換するための変
換手段と、コンパクト形式で前記係数を符号化し、前記
係数は２進数の数列を含み、前記符号化は、前記２進数
の数列のうち先行するゼロの番号を符号化するための第
一の効率的な符号化技術を提供すること含み、さらに、
丸められた係数がその先行するゼロの番号を変えないよ
うに前記係数を丸めるためのエンコーダ手段と、を含
む。

【００１５】本発明の第六の概要によると、提供される
コンピュータプログラム製品は、データ符号化のための
コンピュータプログラムが記録されたコンピュータ可読
媒体を含み、前記コンピュータプログラム製品は、前記
データを異なる周波数特性を有する一連の要素で、前記
要素は各々一連の係数を含んだものに変換するための変
換手段と、前記要素を所定のブロックに分割するための
分割手段と、前記ブロックの各々について符号化し、前
記係数はコンパクト形式で、２進数の数列を含み、さら
に前記符号化は各々のブロックで最も大きな係数のうち
先行するゼロの番号を符号化するための第一の効率的な
符号化技術を提供すること含み、さらに、丸められた係
数は、前記ブロックにおいて、最も大きいマグニチュー
ドの先行するゼロの番号を変えないことを保証して丸め
るためのエンコーダ手段と、を含む。

【００１６】

【実施形態の詳細な説明】付随図面のうちの1つあるい
はそれ以上で、ステップおよび／または特徴にされる参
照箇所は、同じ参照数字を持ち、反対の意図が示されな
い限り、それらのステップおよび／または特徴は、この
記述の目的のために同一の機能および／または動作をす
るものとする。

【００１７】好ましい実施形態を説明する前に、オース
トラリア暫定的特許出願No．PO4728、キャノンインフ
ォメーションシステムズリサーチオーストラリア
Pty．Ltd．により1997年1月22日に出願された、名称
が「デジタル画像圧縮」において開示された画像圧縮と
復号の方法であるSWEETについて説明する。

【００１８】この圧縮と復号の方法は、以下に表題が付
けられた節、「1.0 SWEET画像圧縮方法の概観」「1.1
第一のSWEET画像圧縮方法の符号化処理」「1.2 第一
のSWEET画像圧縮方法の復号処理」「1.3 ２次元の
例」、そして「1.4 第二のSWEET画像圧縮方法の符号化
処理」で説明される。

【００１９】（1.0 SWEET画像圧縮方法の概観）符号化
方法の概観を提供するために、図1において高レベルの
ブロック図が説明される。対応する変換係数112を生成
するために、入力画像102は、好ましくは線形変換であ
る、変換ブロック110に提供される。離散的なウエーブ
レット変換（DWT）は好ましく使用される。画像の二次
元のDWTは、その画像に対する低周波数の近似と3つの高
周波数の詳細要素とを用いて画像を表現する変換であ
る。因襲的に、これらの構成要素はサブバンドと名付け
られる。DWTにより成形された4つのサブ画像のうちのそ
れぞれが、オリジナルの画像のサイズのある4分の1とな
る。低周波数の画像はオリジナルの画像についての情報
のほとんどを包含する。この情報、あるいはエネルギー
の密集した構成は、画像圧縮のために利用される離散的
なウエーブレット変換の画像サブバンドの特徴である。

【００２０】単一レベルのDWTは、低周波数の画像、す
なわちサブバンドに対して任意の回数、再帰的に適用さ
れうる。例えば、画像のレベル3のDWTは、変換を1回適
用し、その変換の結果低いサブバンドに対してDWTを適
用することによって得られる。従って、このような変換
では、9つの詳細なサブバンドと1つの（非常に）低周波
数のサブバンドに帰着する。DWTsのレベル3の後でさ
え、結果として生じる低周波数のサブバンドはオリジナ
ルの画像の重要な情報量を依然として包含し、まだ64倍
小さいが（1/4x1/4x1/4）、圧縮において64のファクタ
ーに影響を与える。

【００２１】しかしながら、画像データを相関のないも
のにするために他の線形変換が実行されてもよい。例え
ば、離散的な余弦変換（DCT）は実行できる。変換係数1
12、特にそのビット数列を表示する値は符号化表現122
を与えるために、効率的な方式でビットを再配列するブ
ロック120により符号化される。

【００２２】復号プロセスは単にこの符号化プロセスの
逆である。符号化された係数は、変化係数に復号され
る。その時、（変換領域）画像はオリジナルの画像また
はその近似を成形するために逆変換される。

【００２３】実施形態の説明を続ける前に、以後、使用
される専門用語の簡単な検討を提供する。2進整数表現
の数値、「ビットn」、または「ビット数n」は最下位ビ
ットの左側で2進数の桁ｎ番目を表す。例えば、8ビット
の２進表現を仮定すると、１０進数の９は00001001とし
て表示される。この数では、ビット3は1と等しい一方、
ビット2、1、および0は、0、0、および1とそれぞれ等し
い。さらに、ビット数列によって表現されたそれぞれの
係数を、列と行において配列した係数を有する行列とし
て表現してもよい。概念的にいう行列は、３つの次元を
有するとみなされるかもしれない。列方向の第１次元、
行方向の第2次元、ビットシーケンス方向の第3次元であ
る。各ビットシーケンスを同一ビット番号において通過
する3次元空間における１平面はビットプレーンと呼ば
れる。

【００２４】変換符号化のアプリケーションのため、係
数の可能な範囲を表現するために必要とされる係数あた
りのビット数は、線形変換と入力画像の（画素あたりの
ビットで）各画素の解像度によって決定される。各画素
に関する値の範囲は代表的には、変換係数の大部分の値
に対して相対的に大きく、大半の係数はゼロが先行する
多くの数を有する。例えば、数値９は８ビット表現で４
個のゼロが先行し、16ビットの表現では１２個のゼロが
先行する。圧縮方法と装置は、効率的な方法で、係数ブ
ロックに関して、これら先行するゼロを表現する（ある
いは符号化する）。残りのビットと数値の符号は修正な
しに直接符号化される。

【００２５】説明の簡単化のために、以降において、変
換係数は符号のない２進数の形に１つの符号ビットを付
けて表現されるものと仮定する。すなわち、10進数−９
と９は同じビット列、即ち、１００１で表現され、前者
は１に等しい符号ビットを有して負の値であることを表
現し、後者は０に等しい符号ビットを有して正の値を表
現する。先行するゼロの数は変換係数の範囲によって決
定される。整数表現を用いると、その係数はすでに暗黙
のうちに最も近い整数に量子化されるが、このことは本
発明においては、必ずしも必要でない。さらに、圧縮の
目的のために、小数点以下のビットに含まれる何らかの
情報は通常無視される。

【００２６】領域は一組の連続的な画像係数を含む。係
数という語は以後、画素と相互変換可能なように用いら
れるが、当業者には良く理解されるように、前者は変換
ドメイン（例えば、DWTドメイン）内の画素を参照する
ために用いられるのが代表的である。

【００２７】（1.1 第一のSWEET画像圧縮方法の符号化
処理）最初の画像圧縮方法のより詳細な説明は図３及び
図４の参照により与えられる。

【００２８】図３は最初の画像符号化方法を示している
フローチャートである。ステップ３０２において、入力
画像を用いて処理が開始され、ステップ３０４で、入力
画像は線形変換、好ましくは離散ウエーブレット変換を
用いて変換される。初期領域は画像全体となるように定
義される。例えば、入力画像の３レベルＤＷＴの場合、
得られる係数は１０個のサブバンドから構成され、領域
として特定できる。これ以外に、各々のサブバンドを別
々に処理し、各々の初期領域を問題とするサブバンド全
体に設定することができる。

【００２９】ステップ３０６では、絶対値が最大の変換
係数の最上位ビット（ｍｓｂ）が決定され、パラメータ
maxBitNumberはこの係数値にセットされる。例えば、最
大の変換係数が2進数の値００００１００１（１０進数
の９）の場合、パラメータmaxBitNumberは３にセットさ
れるが、これはｍｓｂがビット数３のためである、最大
の変換係数のＭＳＢより大きい変換係数のｍｓｂより大
きい値がセットされてもよい。

【００３０】さらに、ステップ３０６で、符号化パラメ
ータ、minBitNumberは符号化された画像の品質を指定す
るためにセットされる。さらに詳しくは、この符号化パ
ラメータは変換される画像の全ての係数の精度を指定
し、必要に応じて変更できる。例えば、minBitNumberが
３では、値が１より元の画像がより粗くなる。

【００３１】オプションとして、本技術は入力画像の符
号化表現で出力ヘッダを提供するステップ３０８を含
む。こうすれば、実際の実行の際、ヘッダ情報は符号化
表現の一部として出力される。例えば、本発明の出力ヘ
ッダは画像の高さと幅、DWTのレベル数、DCサブバンド
の平均値、maxBitNumberパラメータ、minBitNumberパラ
メータについての情報を含む。

【００３２】ステップ310が始まると、変換画像の各々
のサブバンドがステップ312とステップ314とで、別々に
符号化される。各サブバンドは独立して低周波数から高
周波数の順番に符号化される。DCサブバンドに関して
は、符号化に先行して平均値が除去され、ステップ３０
８でヘッダ情報に符号化される。ステップ３１２で、各
々のサブバンドはサブバンド全体として初期領域をセッ
トすることにより符号化される。ステップ３１４では、
パラメータとして maxBitNumberとminBitNumberとによ
り、領域が符号化される。これは、画像の低解像度バー
ジョンが高解像度以前のビットストリームに符号化され
るために階層化コードを提供する。処理はステップ３１
６で終了する。

【００３３】図４は各々の領域を符号化するために図３
のステップ３１４でコールされる手順"Code region(cur
rentBitNumber, minBitNumber)"の詳細なフローチャー
トである。ここで、maxBitNumberがcurrentBitNumberと
して提供される。ステップ４０２で処理が始まる。図４
の領域符号化処理に対する入力はcurrentBitNumberとmi
nBitNumberパラメータとを含む。望ましくは、本方法は
選択された領域または部分領域で処理がそれ自体をコー
ルできるような再帰てきな技術として実行される。しか
しながら、処理は非再帰的な方法により実行してもよ
い。

【００３４】決定ブロック４０４で、currentBitNumber
パラメータがminBitNumberパラメータより小さいかを決
定するためのチェックがされる。それ以外に、決定ブロ
ック４０４が真（ｙｅｓ）を返す場合には何も行わずに
処理はステップ４０６の呼び出し手順に戻る。この条件
は選択された領域の全ての係数がminBitNumberより小さ
いｍｓｂ番号を有することを表している。決定ブロック
４０４は偽（ｎｏ）を返す場合、処理は決定ブロック４
０８に続く。

【００３５】決定ブロック４０８では、選択された領域
が 1 x 1画素であるか決定するためのチェックを行う。
決定ブロック４０８が真（ｙｅｓ）を返す場合、処理は
ステップ４１０に進む。ステップ４１０では、1 x 1画
素が符号化される。望ましくは、これは符号化表現にmi
nBitNumberより上の残りのビットを直接出力することを
含む。ステップ４１２では、処理は呼び出し手順に戻
る。それ以外のの場合、決定ブロック４０８が偽（ｎ
ｏ）を返す場合、領域は1つ以上の係数を含んでおり、
決定ブロック４１４に処理は続く。

【００３６】決定ブロック４１４では、それが有意かで
あるかを決定するために選択された領域をチェックす
る。つまり、領域の有意性が調べられる。領域内で、各
々の係数がのｍｓｂ数がcurrentBitNumberパラメータの
値より小さい場合、その領域は有意でないとされる。領
域の有意性の概念を正確にするために、数学的定義は数
式１で与えられる。与えられたビット数で、仮にcurren
tBitNumber = nで、領域は以下の場合は有意でないとさ
れる。

【００３７】

【数１】

【００３８】ここでRは領域、またCijは領域内の係数を
示す。

【００３９】決定ブロック４１４が偽（ｎｏ）を返すな
らば、処理はステップ４１６に続く。ステップ４１６で
は、値０（すなわち第一のトークン）は符号化された表
現ストリームに出力され、currentBitNumberパラメータ
は１だけ減される。すなわち、この領域の次に低いビッ
トプレーンが処理のために選択される。処理は決定ブロ
ック４０４に続き、ここでパラメータcurrentBitNumber
-1とminBitNumberによりその領域が再処理される。それ
以外の場合、決定ブロック４１４が真（ｙｅｓ）を返し
た場合、つまり領域が有意な場合、処理はステップ４１
８に続く。

【００４０】ステップ４１８では、値１（すなわち、第
二のトークン）が符号化表現ストリームに出力される。
ステップ４２０では、指定した分割アルゴリズムを用い
て選択領域が予め決められた数（望ましくは４）の部分
領域に分割される。使用する分割アルゴリズムはデコー
ダに知られる。

【００４１】この方法では、矩形領域が使用される。領
域は４個の等しいサイズの（正方形）部分領域に分割さ
れるのが望ましい。図２に示すように、選択された領域
（R）２００はM×M係数のサイズを有し、4つの等しいサ
イズの部分領域２１０、２１２、２１４そして２１６に
分割される。部分領域の各々はN×Nのサイズで、NはM／
２に等しい。初期領域のサイズと形状によってはこれが
常に可能とならない。不可能な場合は、初期領域を多数
の正方形領域に分割し、各々が２のべき乗の寸法をとる
ようにし、これらの区画を別々に符号化できる。いずれ
の場合も、インテリジェントな方法で行わなければ、全
体的な結果に対してこの初期化は最小の効果をもたら
す。選択的に、ブロック単位のコーダに適している異な
る分割が用いられてもよい。

【００４２】ステップ４２２では、各々の部分領域が同
じcurrentBitNumberとminBitNumberパラメータで符号化
される。これは、図４の手順 "Code region(currentBit
Number, minBitNumber)"の再帰的呼び出しを用いて行う
のが望ましい。部分領域の符号化は並列または逐次敵に
実施できる。後者の場合、処理は低周波数のサブバンド
から高周波数のサブバンドに向かって開始する。

【００４３】符号化された表現において、変換係数はcu
rrentBitNumberからminBitNumberに画素ビットを単に出
力することにより符号化される。望ましくは、標記に従
い、係数ビットがゼロでない場合のみ符号を出力する。
例えば、currentBitNumber =3の場合で、minBitNumber
= 1であれば−９（00001001）は符号ビット「１」に続
く「１００」に符号化される。

【００４４】（1.2 第一のSWEET画像圧縮方法の復号
処理）図５は、図３及び４の処理を用いて得られた画像
の符号化表現を復号する方法を示すフロー図である。ス
テップ５０２では、符号化表現を用いて処理を開始す
る。ステップ５０４では、ヘッダ情報が符号化表現から
読取られて、もとの画像のサイズを決定し、これによっ
て、初期領域サイズを決定する。また、maxBitNumber
（符号化処理における初期currentBitNumberに等しい）
やminBitNumberなどの情報が入力される。更に、情報は
DCサブバンドの平均値を含む。

【００４５】ステップ５０６では、各サブバンドの復号
が各々のサブバンドへ領域を設定することから開始され
る。ステップ５０８では、maxBitNumberとminBitNumber
パラメータを用いて選択領域が復号される。ステップ５
１０では、逆DWTを復号した選択領域に適用する。処理
はステップ５１２で終了する。

【００４６】図６は手順コール"Decode region(current
BitNumber, minBitNumber)"を用いて各領域を復号化す
るための図５のステップ５０８の詳細なフロー図であ
る。ここで、maxBitNumberはcurrentBitNumberとして提
供される。ステップ６０２では、処理は開始する。図６
の領域復号処理に対する入力はcurrentBitNumberとminB
itNumberパラメータである。また、本方法は再帰的技術
として実行されることが望ましい。しかしながら、処理
は非再帰的な方法で実行することができる。

【００４７】決定ブロック６０４では、currentBitNumb
erがminBitNumberより小さいか決定するためのチェック
をする。決定ブロック６０４が真（ｙｅｓ）を返す場
合、処理はステップ６０６に続き、ここで、呼び出し手
順に処理が戻る。それ以外の場合、決定ブロック６０４
が偽（ｎｏ）を返した場合、処理は決定ブロック６０８
に続く。

【００４８】決定ブロック６０８では、選択された領域
が１×１画素のサイズを有するか決定するためのチェッ
クを行う。決定ブロック６０８が真（ｙｅｓ）を返す場
合、処理はステップ６１０に続き、ステップ６１０で
は、１×１領域が復号される。処理は、ステップ６１２
で呼び出し手順に戻る。決定ブロック６０８が偽（ｎ
ｏ）を返す場合、処理はステップ６１４に続き、ステッ
プ６１４では、符号化表現からビットが入力される。

【００４９】決定ブロック６１６で、ビットが１に等し
いか決定するためのチェックを行う。即ち、その領域が
有意であるか決定するために入力はチェックされる。決
定ブロック６１６が偽（ｎｏ）を返した場合、処理はス
テップ６１８に続く。ステップ６１８では、currentBit
Numberが決定され、処理は決定ブロック６０４に続く。
それ以外の場合、決定ブロック６１６が真（ｙｅｓ）を
返した場合、処理はステップ６２０に続く。ステップ６
２０では、領域は所定の個数（望ましくは４）の部分領
域に分割される。ステップ６２２では、部分領域の各々
がcurrentBitNumberとminBitNumberを用いて復号され
る。このことは図６に示されている手順を再帰的に呼び
出す手段により実行される。ステップ６２４では、処理
は呼び出し手順に戻る。

【００５０】このように、エンコーダでの有意性の決定
から出力されたビットはアルゴリズムが採るパスをデコ
ーダに指示し、こうして、エンコーダに倣う。画素、可
能な符号は適当なビット数（ currentBitNumberからmin
BitNumberまで、及び、それら非ゼロがある場合には符
号ビット）で単純に読み出し復号される。

【００５１】（1.3 2次元の例）本方法は大部分の変
換係数の先行するゼロを効率的に符号化し、その一方で
最上位の有意なビットから予め決められた最下位の有意
ビットに、minBitNumberパラメータにより指定されるビ
ットを符号化し、符号は単にそのままとする。このよう
にして、本圧縮方法は先行するゼロを上手に表現してい
る。本方法は、ある状況、即ち、離散ウエーブレット変
換画像係数の符号化に関して、非常に効果的であり、典
型的に大きなダイナミックレンジを示す。典型的には少
数の係数は非常に大きな値を有し、その一方で、大半は
非常に小さい値を有している。

【００５２】４×４の係数を含んでいる２次元領域の符
号化の例は、図７Ａから７Dを参照して説明される。図
７Aの４×４領域７００の処理は、全ての係数のうちで
最大のビット番号（ビット平面）である７にmaxBitNumb
erをセットして開始する。

【００５３】

【数２】

【００５４】図示の目的において、minBitNumberは３に
セットされる。ヘッダーはmaxBitNumberとminBitNumber
を含む符号化表現で出力されることが好ましい。このと
き、領域７００の符号化処理は以下のようになる。

【００５５】currentBitNumber = 7で、領域７００はビ
ット番号７（図４の決定ブロック４０４、４０８、４１
４、及びステップ４１８を参照）に関して有意であるの
で１（１）が出力される。領域７００は、図７Aの左上
領域７１０、右上領域７１２、左下領域７１４、そして
右下領域７１６の４つの部分領域に分割される（図４の
ステップ４２０を参照）。各部分領域は２×２の係数を
含む。

【００５６】図７Aの部分領域７１０、７１２、７１４
そして７１６は図７Bに示された所定の処理シーケンス
で順番に符号化される。ここで領域７５０は部分領域７
５０Aから７５０Dの４つを含む。図中に示されている３
つの矢印は、処理の順番あるいはシーケンス、すなわ
ち、左上部分領域７５０A、右上部分領域７５０B、左下
部分領域７５０Cそして右下部分領域７５０Dそれぞれの
処理を示す。

【００５７】図７Aの部分領域７１０は最初に符号化さ
れる（図４のステップ４２２を参照）。CurrentBitNumb
erが７に等しい場合、１（１）が符号化表現で出力され
る。部分領域７１０は１０進数の値２００、１３、−１
３、３を有する４個の１×１画素に分割される。これら
の係数の各々はcurrentBitNumber = 7からminBitNumber
= 3までの各係数のビットを出力することで符号化され
る（図４の決定ブロック４０８とステップ４１０を参
照）。要求されれば符号ビットは出力される。このよう
にして、１０進数の値２００は符号ビット０により続け
て１１００１と符号化される。係数値１３は符号ビット
０を伴い００００１として符号化される。係数値−１３
は符号ビット１を伴い００００１として符号化される。
最後に、係数値３は０００００として符号化される（符
号ビットなし）。各係数の符号化表現は、currentBitN
umberと minBitNumberの間に係数「２００」のビットに
先行する２つの「１」ビットを含む。これで、左上の部
分領域７１０の符号化は完了する。この状態での符号化
出力は以下のようになる。

【００５８】

【数３】

【００５９】ヘッダ情報は前述の表現に示されていな
い。

【００６０】右上の部分領域７１２は次に符号化される
（図７B参照）。領域７１２は７、６，５、そして４に
等しいcurrentBitNumberの各々について有意でないの
で、これらのビット番号に関してゼロ（０）が出力され
る。currentBitNumber = 3で１（１）が出力されるの
は、このビット平面はビット番号３に関して有意である
からである。部分領域７１２は値−１１、−８、―４、
−３を有する１×１画素の4つに分割される。これらの
１０進数の値は符号ビット１を伴ったビット値１と符号
ビットのないビット値０として、それぞれ符号化され
る。従って、この段階で、符号化表現は以下のようにな
る。

【００６１】

【数４】

【００６２】左下の部分領域７１４は次に符号化され
る。

【００６３】領域７１４は７，６、５、４に等しいcurr
entBitNumberの各々について有意でないので、これらの
ビット番号に関してゼロ（０）が出力される。currentB
itNumber＝３では１（１）が出力されるのは、このビッ
ト平面はビット数３に関して有意でであるためである。
部分領域７１４は値８，１、２、そして−１を有する１
×１画素４つに分割される。これらは符号ビット０を伴
う２進数の値１と、符号ビットのない２進数の値０，０
そして０としてそれぞれ符号化される。

【００６４】最後に、値−２、−２、−３、そして−３
を有する右下の部分領域７１６が符号化される。curren
tBitNumber = 7, 6, 5, 4, 3の各々で部分領域７１６は
これらのビット数に対して有意でないためゼロ（０）が
出力される。符号ビットが出力されない。つまり、符号
化表現は以下のようになる。

【００６５】

【数５】111100100000100000110000000001111100000011
000000000.

【００６６】デコーダは単に符号化処理に倣って図７C
に示されたように符号化表現から領域を再編成する。

【００６７】復号処理は多数の方法で「よりスマート」
に行うことができる。そのような「よりスマート」な方
法の１つは図７Dに図示される。この場合、非ゼロ係数
の大きさは２のminBitNumberのべき乗の半分ずつ各々増
加する。このことは図７Dに示される。この方法では、
「スマート」な復号処理は復号された係数ともとの係数
との間の平均二乗誤差を一般的に減少できる。さらに、
エンコーダは、これ以外にもこのような（タイプの）演
算を実行することができ、これによって、デコーダに図
７Cに図示した最も簡単な方法を利用させる。

【００６８】（1.4 第二のSWEET画像圧縮方法の符号化
処理）他の方法による符号化処理は図９から１２を参照
して説明される。

【００６９】デジタル画像全体の離散ウエーブレット変
換はブロック単位で実行することができる。各ブロック
の変換の結果は一組の係数となり、これは画像全体の離
散ウエーブレット変換の一組の空間的に対応する係数と
等しい。例えば、画像全体に関して、離散ウエーブレッ
ト変換の所定の係数の組から、デジタル画像の一部また
はブロックは指定された細部まで再現できる。周波数領
域から所定の係数の組を選択することは実質的に空間領
域からデジタル画像（ブロック）の対応する部分を表現
することになる。デジタル画像のブロック単位の離散ウ
エーブレット変換は画像を複数ブロックに分解し、各ブ
ロックに対して独立に変換を適用することにより実行で
き、これによって実質的に現在の空間的な位置に関連し
たDWT係数を評価することができる。ブロック単位の変
換を採用する利点は、その画像の他のブロックから最小
限の相互作用（実質的には独立）を伴ってブロックを実
質的に符号化できることである。ブロック単位の技術は
本質的にメモリーにローカライズされており、コンピュ
ータシステムに適用して実施された場合、一般的に効率
的である。

【００７０】図９は第２の符号化方法に関するブロック
単位の符号化処理を説明するフロー図である。処理はス
テップ９０２で始まる。ステップ９０４で、ヘッダが出
力される。この情報は画像の高さと、幅、ブロックサイ
ズ、DWTのレベル数、２つの符号化パラメータmaxBitNum
berとminBitNumberを含むのが望ましい。オプションと
して、多かれ少なかれ、ヘッダ情報は用途によって使用
できる。

【００７１】符号化パラメータ maxBitNumberは様々な
方法により選択できる。全ての画像ブロックについて、
これらのうちのいずれかを符号化する前にブロックＤＷ
Ｔが実行される場合、maxBitNumberは全部のＤＷＴブロ
ックにわたって最も大きい係数のＭＳＢ番号となるよう
に選択できる。例えば、最大の係数が１０００００１
（１０進数の値で１２９）であるとすると、maxBitNumb
erはＭＳＢはビット番号７であるので、７にセットされ
る。これ以外に、入力画像の変換と解像度によって決ま
る決定範囲を用いることができる。例えば、８ビットの
入力画像（プラス符号７ビットに対してシフトされるレ
ベル）とＨａａｒ変換とを伴って、最大のＭＳＢはＪ
＋７で区切られ、ＪはＤＷＴのレベル数である。ブロッ
クが小さい場合、このパラメータの選択は圧縮に対して
有意な効果を有し得る。場合によっては、より洗練され
たmaxBitNumberを選択する方法が採用されてもよい。し
かしながら、これは特定のアプリケーションに依存す
る。

【００７２】パラメータminBitNumberは圧縮比に対する
画質の兼合いを決定し、変更することができる。例え
ば、略直交変換では、値３は８ビットグレースケールま
たは２４ビットＲＧＢ画像で十分な画質を与える。

【００７３】ステップ９０６では、画像はブロックに分
解される（あるいは、画像ブロックが形成される）。画
像は重複するブロックに分解されるのが望ましい。しか
しながら、重複しないブロックが採用されるかもしれな
い。係数のブロックはもとの画像全体と同程度の大きさ
とするか、８×８係数（３レベル変換に関して）のブロ
ックと同程度の小ささにすることができる。メモリの少
ないアプリケーションについて、できる限り小さいブロ
ックが採用され得る。一般に、１６係数のブロックサイ
ズは３乃至４レベルのＤＷＴによる高レベルの圧縮に対
して十分である。３レベルＤＷＴでの８×８係数のブロ
ックサイズは各ブロックのＤＣ係数の対して差動パルス
符号変調（ＤＰＣＭ）を用いることにより、良好な符号
化効率を維持することができる。

【００７４】ステップ９０８では、各ブロックはレベル
シフトされ、変換は実行される。望ましくは、ＤＷＴが
使用される。画像の値はレベルシフトされ（例えば、８
ビット画像では１２８だけシフトされる）、望ましくな
い平均バイアスを減少あるいは排除し、画像のそれぞれ
の空間ブロックが変換される。ＤＷＴでは。通常、現在
のブロックを取囲むブロックについて何らかの知識が要
求されるが、これは厳密には要求されない。

【００７５】ステップ９１０では、maxBitNumberとminB
itNumberパラメータを用いてブロックが符号化される。
処理はステップ９１２で終了する。

【００７６】ブロックを符号化するためのステップ９１
０は、図１０のフロー図に詳細に図示されている。図１
０のブロック符号化処理への入力はcurrentBitNumberと
theminBitNumberパラメータを含む。図９のステップ９
１０を参照して、maxBitNumberはcurrentBitNumberパラ
メータとして入力される。処理はステップ１００２で開
始する。決定ブロック１００４で、currentBitNumberが
minBitNumberより小さいかを決定するためのチェックが
される。もし、決定ブロック１００４が真（ｙｅｓ）を
返した場合、処理はステップ１００６に続く。ステップ
１００６では、実行は呼出し処理に戻り、これによっ
て、ブロック内の全ての係数はminBitNumberより小さい
ＭＳＢ番号を有することを示す。それ以外の場合で、決
定ブロック１００４は偽（ｎｏ）を返すと、処理は決定
ブロック１００８に続く。

【００７７】決定ブロック１００８では、現在のブロッ
クが有意であるかを決定するためのチェックを行う。決
定ブロック１００８が偽（ｎｏ）を返すと、処理はステ
ップ１０１０に続く。ステップ１０１０で、符号化表現
でゼロ（０）が出力され、currentBitNumberは減ぜら
れ、すなわち、次に低いビット平面が選択される。処理
は決定ブロック１００４に続く。これ以外の場合、決定
ブロック１００８が真（ｙｅｓ）を返すと、処理はステ
ップ１０１２に続く。

【００７８】ステップ１０１０を併せて、決定ブロック
１００４と１００８とにより、処理はブロック内で最大
の係数のＭＳＢ番号を見つけ出すことができるようにな
る。ブロック内の全ての係数のＭＳＢ番号がcurrentBit
Numberより小さければ、currentBitNumberに対してブロ
ックは有意でない。これは、ブロックのビット平面が有
意かまたはminBitNumberよりcurrentBitNumberが小さく
なるまで繰り返される。

【００７９】ステップ１０１２で、ビット平面は有意で
あることを示すために、符号化表現に１（１）が出力さ
れる。ステップ１０１４で、ＤＣサブバンドは符号化さ
れる。ステップ１０１６では、ブロックの細部は、パラ
メータＪ、currentBitNumber及びminBitNumberを用いて
符号化される。ステップ１０１８では、実行は呼出し処
理に戻る。つまり、ブロックが有意であれば、ステップ
１０１２、１０１４、そして、１０１６は実行され、
（一般化）クワドツリーセグメンテーションを用いて
minBitNumberより大きなＭＳＢ番号を有する全ての係数
を見つける。ブロックが有意の場合、ＤＣサブバンド係
数と残りの係数を含むレベルＪに対して、「ブロック細
部」と呼ばれるブロックの、２つの「サブブロック」に
分割される。これは、全ての低いレベルでレベルＪのブ
ロックについて高い周波数情報を表すためである。

【００８０】ＤＣサブバンドの符号化に関する図１０の
ステップ１０１４は図１２のフロー図により詳細に図示
される。すなわち、図１２はcurrentBitNumberとminBit
Numberパラメータｗｐ用いてサブバンドあるいはサブブ
ロックを符号化する処理を示している。ステップ１２０
２では、処理が開始する。決定ブロック１２０４では、
currentBitNumberがminBitNumberより小さいかを判断す
るチェックを行う。決定ブロック１２０４が真（ｙｅ
ｓ）を返すと、処理はステップ１２０６に続く。ステッ
プ１２０６では、実行は呼出し手順に戻る。それ以外の
場合、決定ブロック１２０４が偽（ｎｏ）を返すと、処
理は決定ブロック１２８に続く。

【００８１】決定ブロック１２０８では、（サブバン
ド）ブロックサイズが１×１画素であるかを決定するた
めのチェックを行う。決定ブロック１２０８が真（ｙｅ
ｓ）を返すと、処理はステップ１２１０に続く。ステッ
プ１２１０で、１×１画素は符号化される。これは、必
要ならば、符号ビットに続けてcurrentBitNumberとminB
itNumberを含めて、これらの間にあるビットを出力する
ことを伴う。処理はステップ１２１２で呼出し手順に戻
る。それ以外の場合、決定ブロック１２０８が偽（ｎ
ｏ）を返すと、処理は決定ブロック１２１４に続く。

【００８２】決定ブロック１２１４では、（サブバン
ド）ブロックが有意であるかを決定するためのチェック
を行う。決定ブロック１２１４が偽（ｎｏ）を返すと、
処理はステップ１２１６に続く。ステップ１２１６で、
符号化表現でゼロ（０）が出力され、currentBitNumber
は減じられる。処理は決定ブロック１２０４に続く。そ
れ以外の場合、決定ブロック１２１４が真（ｙｅｓ）を
返すと、処理はステップ１２１８に続く。

【００８３】ステップ１２１８では、（サブバンド）ブ
ロックが有意であることを示すために符号化表現で１が
出力される。ステップ１２２０で、（サブバンド）ブロ
ックは４つのサブブロックに分割される。ステップ１２
２２で、各々のサブブロックは図１２の処理に対して再
帰的な呼出しによりパラメータcurrentBitNumberとminB
itNumberとを用いて符号化される。

【００８４】つまり、図１２の処理では、サブバンドま
たはそのサブブロックは符号化される。最大のＭＳＢ番
号は前述のように分離される。サブブロックが１つの画
素のみを包含する場合、単一の係数として符号化され
る。それ以外の場合、currentBitNumberは減じられ、cu
rrentBitNumberがminBitNumberより小さくなるまで、あ
るいは、サブバンド（サブブロック）が有意になるまで
符号化表現にゼロ（０）が出力される。サブバンド（サ
ブブロック）が有意である場合、４個の（できるだけ等
しくなるように）サブブロックに分割され、順番にこれ
らは符号化される。単一の係数は例えば、ＤＣ係数は、
currentBitNumberからminBitNumberへ係数ビットを出力
することにより符号化される。また、符号は係数ビット
の幾つかが非ゼロの場合のみ出力されるのが望ましい。

【００８５】ブロック細部を符号化するための図１０の
ステップ１０１６は図１１のフロー図により図示され
る。ステップ１１０２で、処理は開始する。決定ブロッ
ク１１０４では、currentBitNumberがminBitNumberより
小さいか判定するためのチェックをする。決定ブロック
１１０４が真（ｙｅｓ）を返すと、実行はステップ１１
０６で呼出し手順に戻る。それ以外の場合、決定ブロッ
ク１１０４が偽（ｎｏ）を返すと、処理は決定ブロック
１１０８に続く。

【００８６】決定ブロック１１０８で、ブロック（細
部）が有意か決定するためのチェックを行う。決定ブロ
ック１１０８が偽（ｎｏ）を返すと、処理はステップ１
１１０に続く。ステップ１１１０で、符号化表現でゼロ
（０）が出力され、currentBitNumberは減じられる。処
理は次に決定ブロック１１０４に進む。それ以外の場
合、決定ブロック１１０８は真（ｙｅｓ）を返すと、処
理はステップ１１１２に進む。

【００８７】ステップ１１１２では、ブロック（細部）
が有意であることを示すために符号化表現に１が出力さ
れる。ステップ１１１４では、ｈｉｇｈ-ｌｏｗ（Ｈ
Ｌ），ｌｏｗ-ｈｉｇｈ（ＬＨ），そしてｈｉｇｈ−ｈ
ｉｇｈ（ＨＨ）周波数サブバンドの各々が符号化され
る。ＨＬ、ＬＨそしてＨＨ周波数サブバンド各々の解像
度は共通にＡＣサブバンドと呼ばれる。これらのサブバ
ンドの各々は図１２の処理に従って符号化される。ステ
ップ１１１６では、（ブロック詳細が存在するならば）
図１１に図示されている再帰的な呼出し手順によって、
パラメータＪ−１、currentBitNumberとminBitNumberを
用いてブロック細部が符号化される。実行はステップ１
１１８で呼出し手順に戻る。

【００８８】このように、レベルＪに関するブロック詳
細は最大の係数ＭＳＢ番号を最初に分離するように処理
される。これは、currentBitNumberを減じ、ブロックが
有意になるまでゼロを出力することにより行われる。ブ
ロックは次にレベルＪでの３個の高周波数サブバンドと
レベルＪ−１について（Ｊ−１が０より大きい場合）ブ
ロック詳細に分割される。この分割アプローチはいわゆ
る１／ｆタイプのスペクトルモデルにより導き出され
る。

【００８９】第２の方法に関する復号処理は図９から１
２を参照して説明した符号化処理に倣うことで実行され
得る。

【００９０】符号化、復号化方法及び装置は画像を記憶
するか、送信するかのいずれか或いは両方のために適し
た表現形式で、効率的かつ柔軟性のある方法でデジタル
画像データを表現する。符号化技術は一般的に変換係数
の配列を表現するために使用することができ、また、離
散ウエーブレット変換領域において画像を表現すること
により効率的な表現を提供するために使用できる。特
に、方法と装置は入力画像から得られた変換係数のブロ
ックの先行するゼロを表現する（あるいは符号化す
る）。本技術は、与えられたサイズのコードに関して元
画像の良好な再生を与える点と、高速な復号を与える点
に関して効率的である。さらに、本技術は線形変換から
得られた係数がエントロピー符号化を用いることなく独
立して符号化される点で柔軟性がある。本方法の有利な
側面は符号化の深さ第１の性質を含む。さらに、サブバ
ンドを符号化する場合、本方法の有利な側面は、各々の
サブバンドを別々に階層符号化することが含まれる。

【００９１】（2. 方法の望ましい実施形態）好ましい
実施形態は画像データのウエーブレット変換によって最
初に処理される。ウエーブレット変換処理の説明は多く
の標準的なテキスト、特に、前記のStollnitzらによる
本で与えられる。標準的なウエーブレット処理の概観は
添付図面を参照して説明される。最初に図13を参照し
て、オリジナル画像1は離散ウエーブレット変換（ＤＷ
Ｔ）を利用して４つのサブ画像３−６に変換される。サ
ブ画像あるいはサブバンドは通常LL1、HL1、LH1、およ
びHH1で示される。サブバンド名の一つの接尾辞はレベ
ル1を示す。LL1サブバンドはオリジナル画像の低域通過
のデシメイトされたバージョンである。利用されたウエ
ーブレット変換は、例えば、Haar基礎機能、Daubechies
基礎機能などを変化させ、包含することができる。LL1
サブバンドはその時次々と利用され、サブバンド、LL2
（8）、HL2 （9）、LH2 （10）、HH2 （11）を与える図
14に示されるように2番目の離散ウエーブレット変換が
適用される。例えば、この処理は、LL4サブバンドが説
明される図15において説明されるように続けられて、LL
4バンド分解処理はＤＣサブバンドと呼ばれるＬＬ４サ
ブバンドを伴ったオクターブバンドフィルタバンクとし
て参照される。明らかに、さらに進んだ分解のレベルは
入力画像のサイズに依存して供給される。各々単一レベ
ルのDWTは、元画像を得るために次々逆にされる。この
ため、ＪレベルのＤＷＴはＪの単一レベルの逆ＤＷＴの
直列として逆変換することができる。

【００９２】階層的に符号化された画像はＤＣサブバン
ドを符号化することで処理できる。次に、残りのサブバ
ンドは減少レベルの順序で符号化される。4レベルのDWT
に関して、レベル4のサブバンドはDCサブバンド（LL4）
の後で符号化される。それはＨＬ４、ＬＨ４、そしてＨ
Ｈ４サブバンドである。レベル3（HL3、LH3、およびHH
3）のサブバンドは、次に符号化されて、レベル2（HL
2、LH2、およびHH2）とレベル1（HL1、LH1、およびHH
1）が続く。

【００９３】標準の画像によって、符号化されたサブバ
ンドは通常、画像中の「詳細な」情報を含む。それゆ
え、それらはしばしば値のまばらな配列を含み、現実の
圧縮は、サブバンドの量子化とそれらのまばらな行列フ
ォームの効率的な符号化により達成できる。

【００９４】図16に説明をうつして、フローチャート２
０に図示されている望ましい実施形態は前述したように
入力画像データの離散ウエーブレット変換２１を最初に
求める構成を含む。次に、各々のサブバンドは階層順に
より処理される２２。次に、各々のサブバンドの係数が
調べられる２３。係数は、後に説明される丸め効果を考
慮した効率的な符号化の修正を伴った前述のSWEET符号
化方法を利用して符号化される２４。

【００９５】図１７に説明をうつして, 復号処理３０は
符号化に対して逆の処理が適用されることを図示してい
る。復号処理３０は階層順３１で各々のサブバンドにわ
たってループする構成を含む。各々のサブバンドに関し
て、各係数が調べられる３２。各々の係数のビット平面
は、係数が本来あるように再構成するSWEET法を利用し
て、復号される33。後で、いったん係数が復号された
ら、逆離散ウエーブレット変換35は、オリジナルなデー
タを再生するために適用される。

【００９６】SWEET符号化方法は、ここおよびオースト
ラリア仮明細書番号ＰＯ４７２８において説明されてい
るように、DWTサブバンド係数を符号化、復号化するた
めに使用される。SWEETはビット平面を符号化する方法
である、即ち、係数の組はデータセットからなるビット
平面を単純に符号化することで効率的に符号化すること
ができる。例えば、図１８において、４つの番号（１３
５、７、１９１、９９）と１０進数の形式４１に加えて
８ビットの２進数表現４２のグループを示すテーブル４
０が図示されている。ビット平面符号化は暗黙のうち
に、あるいは明示的にビット平面７，６、５、４．．と
所定の最小ビット平面番号まで符号化することで、この
グループを単純に符号化することができる。ビット平面
の符号化を実行するには様々な方法がある。例えば、最
小ビット平面番号が３で、伝達されるべきデータが以下
に無い場合、一つのオプションはビット平面７（明示的
に１０１０）で全てのビットを符号化することであり、
そのとき、ビット平面６（０００１）内の全てのビット
とビット平面３までの全てのビットが符号化される。代
わりに、係数7(0000)に関するビット平面7からビット平
面3の全てのビットを辿って、同様に、係数１９１（１
０１１１）（０００００）に関してビット平面7からビ
ット平面3まで全てのビットを辿ると、係数の135(1000
0)を符号化することができる。

【００９７】しかしながら、好ましい実施形態の効率的
な丸め方法の記述が関係する限り、選ばれる符号化の実
際の順序は不適切なものである。

【００９８】最小ビット平面番号がビット平面0である
とすると、次に、整数係数に関して、係数は損失なく符
号化される。しかしながら、損失のある画像圧縮アプリ
ケーションに関しては、最小ビット平面番号は通常これ
より大きく、係数は通常は整数でなく、幾らかの損失が
発生するだろう。図１８の例の場合、最小ビット平面は
ビット平面３であった。この場合、ビット平面７からビ
ット平面３までの全てのビット４２はエンコーダにより
符号化され（少なくとも暗黙のうちに）そしてデコー
ダに送られる。デコーダは、次に、これら符号化された
ビット面42を正確に再構築し、単純な場合、残りのビッ
ト平面（ビット平面２，１、０）を0で満たす。

【００９９】望ましい実施形態において、上述の簡単化
したアプローチを超えて、符号化効率を高めるために、
2つの技術が適用される。一つは、デコーダで丸める、
あるいはエンコーダで丸める、均一な量子化の形態を最
初に用いることができる。デコーダでの丸めを実行する
ために、係数は降冪にビット平面n_minまで符号化される
とすると、ビット平面 n_min−1内の１は平均誤差を減ら
すために係数に加えることができる。図１８の例にこれ
を適用すると、その結果は図１９に示されたようにな
る。係数１３５は単純に１２８として復号されるが、ビ
ット平面２で１を付加することは１３２として復号され
ることを意味する。元の係数と復号された係数との間の
誤差は単純なケースでは７であるが、図１９の例ではわ
ずか３である。

【０１００】改良として、０まで符号化されていない係
数のみをエンコーダで丸める際に、丸められる。ビット
平面内で最も有意なビットがビット平面内で符号化され
た最小値より小さければ、係数はゼロまで符号化され
る。例えば、カラム51で、番号７は不変であり続けてい
る、より高いビット平面内に帰着する。

【０１０１】ビット平面の符号化の前で、符号化された
ビット平面の最小値はビット平面n_m _inであり、ビット平
面n_min−1に１を加えることができる。図１８及び１９
の例を繰り返して、１０進数の係数１３５（４５）に関
してビット平面２で１を加えることは (10000111 + 000
00100 = 10001011 ２進数) １０進数139（図１９の５
２）を与える。符号器は、前と同じようにビット平面を
n_min (53)まで符号化し、デコーダは非符号化平面をゼ
ロで満たす。従って、１３５は(10001000) 136として復
号される。

【０１０２】典型的な画像またはデータに関して、圧縮
の有意量は、画像の典型的な変換が、０に向かって重み
傾斜した大きさの分布を有するという事実に依存する。
これは、小さいマグニチュードを有する係数の確率が高
いことを示す図20において概念的に説明される一方、大
きいマグニチュードを有する確率は、増加するマグニチ
ュードによって急速に減少する。図２０は更に、n_minの
大部分の値に関して、２^ｎminより下位に多くの係数が
存在することを図示する。

【０１０３】係数の大多数がゼロとして符号化される
（すなわち、２^ｎminより小さい大きさを有する）の
で、圧縮の有意量によるビット平面符号化技術を利用す
ることは可能である。ＳＷＥＥＴ符号化方法、および、
大部分の効率的な画像符号化方法は、効率的な方法、代
表的にはゼロ（符号化された）係数あたりのビットの分
数を伴って、ゼロ（符号化された）係数の大多数を符号
化する。また、図２０で図示されたことは、２^ｎminよ
り小さいマグニチュードを有する係数の有意な数は存在
するが、２^ｎminより大きいマグニチュードを伴う係数
の数に対する比較で、２^ｎminに密なものであるという
ことである。これは、最小のビット平面n_minが何である
としても、ビット平面符号化前の通常の丸めはゼロに対
して符号化されない係数値を有意に増加させる（符号化
の前に丸めが実行されないケースと比べて、２^ｎminよ
り小さく、２^ｎmin-2より大きいですべての係数は２
^ｎminまで丸められ、その後、ゼロまで符号化されな
い）。符号化の歪みを減少させることは確保できるが、
この処理はより多くの非ゼロ係数を結果として生じてい
るので、より正確な復号を通じて、圧縮比はかなり小さ
くなるだろう（ＳＷＥＥＴ法及び大部分の他の方法の有
効性は、より多くの非ゼロ符号化係数を伴ってかなり限
定される）。

【０１０４】従って、画像圧縮アプリケーションのため
に、ビット平面符号化に先がけた丸めは、記述されたよ
うに、一般に望ましくない。しかしながら、特定のビッ
ト平面符号化方式の知識で、ビット平面符号化に先立つ
効率的な丸めの形式を実行することは可能である。もし
係数がゼロに符号化されなければ、ゼロの係数（係数は
ゼロに符号化）の同じ数を残して、ビット平面 n_min-1
で１ビットを加えることは可能である。

【０１０５】更なる改良は、ＳＷＥＥＴ（および、EZW
符号化方法における一定の変形）のような符号化方法を
作ることができる。時々、ビット平面n_min-1で1が係数
に付加される時には、係数の最も有意なビットのビット
平面番号が一つ増加する（例えば、00000100は00001011
を与えるために00000111に付加される時）。このことは
、係数、あるいは係数のグループに先行するゼロ（最
も有意なビットの上のゼロ）を効率的に符号化すること
に一般的に依存したＳＷＥＥＴのような効率的なビット
平面符号化方式では、時として望ましくない。そして、
これは圧縮効率に影響を与えうる。SWEET（さらにEZW符
号化方法の一定の変形）によって、係数の2×2のブロッ
クのうちの先行する0が効率的に符号化される。

【０１０６】そのポイントを図示するために図２１に示
したような２×２の係数ブロックの例を考える（１次元
形式において）。ビット平面４より上の0ビット平面
は、これらのビット平面が効率的に符号化されるSWEET
（あるいはEZW）のような方法を用いているので示され
ていない。これら先行するゼロを効率的に符号化するこ
とで、ＳＷＥＥＴは他のビット平面をも同様に容易に符
号化する。例えば、n_min=3（60）で、ビット平面4と3は
（１００１と００１１）として、1つの平面あたりの合
計で4ビットまたは8ビットを必要とされる。もし、最も
有意なビットのビット平面番号が、ビット平面番号4を
越えていないならば、その時1ビットはビット平面2で個
々の係数に付加される。従って、ビット平面2で1は、１
６、８、そして１６として符号化／復号化される係数１
６、７そして１４に付加される。その時、最も有意なビ
ットがビット平面5に並べられるので、ビット平面2で1
ビットは２９に付加されず、従って、先行する0の符号
化の効率に影響を及ぼすことになる。

【０１０７】デコーダ丸めの前の形式を用いるとき、０
まで符号化される７は８まで符号化されることに注意す
るべきである。ビット平面符号化に先行した、この丸め
の形式は、非ゼロ符号化係数の数を増加させるが、その
ような方法は圧縮比に有意な効果をもたらさない。とに
かく係数7に関して符号化が必要なビット平面4および3
以上が与えられた例では、丸めに余分な負担はない。
（符号がつけられたデータに関しては、非ゼロ符号化係
数の符号ビットを送信することが必要で、従って、８と
して７を符号化することは符号に関して追加ビットを１
つ要求する。）切上げが圧縮比に有意な影響をもたらす
他の多くの係数が存在し、それゆえ丸めはこれらのケー
スでは実行されない。従って、典型的な変換画像係数に
関して、丸めのこの形式は、デコーダにおいて丸めるよ
り一般的に優れている。さらに、それはエンコーダで単
なるハードウェア内で行うことができ、従って、実行す
ることは非常に簡単である。係数が符号化される時に、
ビット平面n_min-1で1ビットを付加することが係数の最
も有意なビットのビット平面番号を、与えられた所望の
最大値を超えて増大させるか否か、テストをすることは
簡単である。デコーダはまた非常に簡単であり、単に、
エンコーダにより送られたビットを再構築し、0によっ
て残りの下位ビット面を（暗黙に）満たす。

【０１０８】（2.1 装置の望ましい実施形態）符号化処
理は、むしろ、図８で示されているような、従来の汎用
目的のコンピュータを用いて実行され、図13から21まで
のプロセスがコンピュータで実行できるソフトウェアと
して実行され得る。特に、符号化方法のステップは、コ
ンピュータにより実行されるソフトウェアの指示により
実行される。ソフトウェアは2つの部分に分割できる；
符号化方法を実行するための１つの部分；さらに、ユー
ザーとの間のユーザーインタフェースを管理する別の部
分、である。例えば、ソフトウェアは、コンピュータ可
読媒体、以下で説明される記憶装置を含む、に保存され
る。ソフトウエアはコンピュータ可読媒体からコンピュ
ータにロードされ、コンピュータにより実行される。そ
のようなソフトウエアあるいは、コンピュータプログラ
ムが記録されたものを有するコンピュータ可読媒体はコ
ンピュータプログラム製品である。コンピュータでコン
ピュータプログラム製品を使用するのは、むしろ、本発
明の実施形態に従ってデジタル画像の符号化表現にとっ
て、有利な装置をもたらす。

【０１０９】コンピュータシステム800は、コンピュー
タ802、ビデオディスプレイ816、および入力装置818と8
20を含む。さらに、コンピュータシステム800は、ライ
ンプリンタ、レーザープリンタ、プロッター、およびコ
ンピュータ802と接続された他の再生機器を含む多くの
他の出力装置を備えることができる。コンピュータシス
テム800は、モデム通信パス、コンピュータネットワー
ク、あるいはその類似の適切な通信チャンネル830を使
って通信インタフェース808cを経た1台以上の他のコン
ピュータと接続できる。コンピュータネットワークに
は、ローカルエリアネットワーク（LAN）と広域ネット
ワーク（ＷＡＮ）とイントラネットおよび／またはイン
ターネットを含んでもよい。

【０１１０】コンピュータ802自身は、中央処理装置
（単に、以下、プロセッサという）804、ランダムアク
セスメモリー（RAM）と読み出し専用メモリ（ROM）、入
出力（IO）インタフェース808a、808bおよび808c、ビデ
オインタフェース810、および図8のブロック812に、一
般に表されている1つ以上の記憶装置を含む。記憶装置8
12は以下のうちの1つ以上を含むことができる、フロッ
ピーディスク、ハードディスクドライブ、磁気光学式の
ディスクドライブ、CD-ROM、磁気テープ、またはその技
術分野の当業者に既知の多くの不揮発性の記憶装置など
である。804から812までの構成要素のそれぞれは、デー
タ、アドレス、およびコントロールバスを順に含むこと
ができるバス814を経由した１つ以上の他の装置と典型
的に接続される。

【０１１１】ビデオインタフェース810はビデオディス
プレイ816に接続され、コンピュータ８０２からビデオ
ディスプレイ８１６に表示するためのビデオ信号を供給
する。コンピュータ802を動作させるためのユーザー入
力は、1つ以上の入力装置808bによって与えることがで
きる。例えば、オペレータはコンピュータ802へ入力を
与えるために、キーボード818および／またはマウス820
などのポインティングディバイスを使用できる。

【０１１２】システム800は、単に実例的な目的に関し
て与えられるものであり、本発明の範囲及び趣旨から逸
脱することなく他の形態を採用することは可能である。
実施形態が実行できる模範的なコンピュータは、IBM-PC
/ATs、あるいは互換機、またはPCs、Sｕｎ Sparcstati
on（TM）、または同類のマッキントッシュ（TM）ファミ
リーのうちの1つを含む。前述は、単に本発明の実施形
態が実行できるコンピュータのタイプの模範的なもので
ある。典型的に、以下に説明される実施形態のプロセス
は、ソフトウエア、あるいはコンピュータ可読媒体とし
てのハードディスクドライブ（一般的には図８のブロッ
ク８１２に図示）に記録されたプログラムとして常駐
し、プロセッサ８０４を用いて読取り、制御される。ネ
ットワークから取り出されたプログラム、画素データ、
およびその他のデータの中間的な保存はハードディスク
ドライブ812とできる限り協調して、半導体メモリー806
を使って遂行できる。いくつかの例において、プログラ
ムは、CD-ROMまたはフロッピーディスク（両者は一般に
ブロック812によって示される）において符号化されて
ユーザーに供給できるか、または例えばコンピュータと
接続されたモデム機器を経たネットワークからユーザー
により読取られる。さらに、ソフトウェアは、また、他
のコンピュータ可読媒体で磁気テープ、ROM、あるいは
集積回路、磁気光学式のディスク、ラジオ、またはコン
ピュータと他の機器との間の赤外線伝送チャンネル、PC
MCIAのようなコンピュータ可読カード、及びインターネ
ット、さらに電子メール伝送、websites上で記録された
情報等を含むイントラネットを含むものから、コンピュ
ータシステム800にロードされる。前述のものは適切な
コンピュータ可読媒体の単なる模範である。他のコンピ
ュータ可読媒体は本発明の範囲と趣旨を逸脱せずに実行
できる。

【０１１３】符号化の方法はその機能またはサブ機能を
実行する1つ以上の集積回路などの専用ハードウェアで
代わりに実行される。そのような専用ハードウェアは、
グラフィックプロセッサ、デジタル信号プロセッサ、ま
たは1つ以上のマイクロプロセッサー、および関連した
メモリーを含んでもよい。

【０１１４】前記の内容は本発明の実施形態のわずかな
部分を説明したにすぎず、修正、および／あるいは、変
化は、本発明の範囲と趣旨を逸脱せずにその技術分野に
おける当業者によってなされ得るものである。それゆえ
に、本実施形態は図解となるべき全ての点を考慮するも
ので、制限的ではない。

【０１１５】

【図面の簡単な説明】

本発明の実施形態は、例示により、図面を参照して説明
される。

【図１】図1は本特許出願で説明された画像表現技術を
示す高レベルブロック図である。

【図２】図２は本特許出願で説明された分割を示す図で
ある。

【図３】図３は本特許出願で説明された画像の表現また
は符号化の方法を示すフロー図である。

【図４】図４は図３での領域の符号化ステップを示す詳
細なフロー図である。

【図５】図５は図３の方法に従って作成した画像の符号
化表現の復号方法を示すフロー図である。

【図６】図６は図５での領域の復号ステップを示す詳細
なフロー図である。

【図７】図３から６の符号化および復号化の方法に従っ
た２次元、８係数領域の処理を示す図である。

【図８】図８は汎用目的のコンピュータのブロック線図
である。

【図９】図９は本特許出願で説明された別の方法による
画像表現または符号化を示すフロー図である。

【図１０】図１０は本特許出願で説明された別の方法に
よる画像表現または符号化を示すフロー図である。

【図１１】図１１は本特許出願で説明された別の方法に
よる画像表現または符号化を示すフロー図である。

【図１２】図１２は本特許出願で説明された別の方法に
よる画像表現または符号化を示すフロー図である。

【図１３】図１３は画像データをウエーブレット変換の
処理を説明する図である。

【図１４】図１４は画像データをウエーブレット変換の
処理を説明する図である。

【図１５】図１５は画像データをウエーブレット変換の
処理を説明する図である。

【図１６】図１６は符号化処理のフローチャートを示す
図である。

【図１７】図１７は復号化処理のフローチャートを示す
図である。

【図１８】図18は一連の数の初期のビット平面を表現す
る図である。

【図１９】図１９は望ましい実施形態の最初の方法を適
用した後のビット平面の形式を示す図である。

【図２０】図20は変換画像係数の大きさの典型的な分布
を示す図である。

【図２１】図２１は代わりの実施形態において用いられ
るように、多くの数のビット平面表現を説明する図であ
る。

───────────────────────────────────────────────────── フロントページの続き (71)出願人 000001007 キヤノン株式会社東京都大田区下丸子３丁目30番２号 (72)発明者ジェームスフィリップアンドリューオーストラリア国 2113 ニューサウスウェールズ州，ノースライド，トーマスホルトドライブ１キヤノンインフォメーションシステムズリサーチオーストラリアプロプライエタリーリミテツド内 (72)発明者アンドリューペーターブラッドリーオーストラリア国 2113 ニューサウスウェールズ州，ノースライド，トーマスホルトドライブ１キヤノンインフォメーションシステムズリサーチオーストラリアプロプライエタリーリミテツド内

Claims

【特許請求の範囲】

【請求項１】データ符号化方法であって、前記データを異なる周波数特性を有する一連の要素で、
前記要素は各々一連の係数を含んだものに変換し、コンパクト形式で前記係数を符号化し、前記係数は２進
数の数列を含み、前記符号化は、前記２進数の数列のう
ち先行するゼロの番号を符号化するための第一の効率的
な符号化技術を提供すること含み、さらに、丸められた
係数がその先行するゼロの番号を変えないように前記係
数の丸めを含むことを特徴とするデータ符号化方法。
【請求項２】前記丸めは有意でない係数の最初の番号
を切捨てることと、係数がゼロでない、より有意な係数
に１を加えることを含むことを特徴とする請求項１に記
載された方法。
【請求項３】データ符号化方法であって、前記データを異なる周波数特性を有する一連の要素で、
前記要素は各々一連の係数を含んだものに変換し、前記要素を所定のブロックに分割し、前記ブロックの各々について符号化し、前記係数はコン
パクト形式で、２進数の数列を含み、さらに前記符号化
は各々のブロックで最も大きな係数のうち先行するゼロ
の番号を符号化するための第一の効率的な符号化技術を
提供すること含み、さらに、丸められた係数は、前記ブ
ロックにおいて、最も大きいマグニチュードの先行する
ゼロの番号を変えないことを保証する丸めを含むことを
特徴とするデータ符号化方法。
【請求項４】前記変換は前記データのウエーブレット
変換を含むことを特徴とする請求項１または３に記載の
方法。
【請求項５】前記データはデジタル画像データを含む
ことを特徴とする請求項１または３に記載の方法。
【請求項６】データ符号化装置であって、前記データを異なる周波数特性を有する一連の要素で、
前記要素は各々一連の係数を含んだものに変換するため
の変換手段と、コンパクト形式で前記係数を符号化し、前記係数は２進
数の数列を含み、前記符号化は、前記２進数の数列のう
ち先行するゼロの番号を符号化するための第一の効率的
な符号化技術を提供すること含み、さらに、丸められた
係数がその先行するゼロの番号を変えないように前記係
数を丸めるためのエンコーダ手段と、を含むことを特徴
とするデータ符号化装置。
【請求項７】前記丸めは有意でない係数の最初の番号
を切捨てることと、係数がゼロでない、より有意な係数
に１を加えることを含むことを特徴とする請求項６に記
載された装置。
【請求項８】データ符号化装置であって、前記データを異なる周波数特性を有する一連の要素で、
前記要素は各々一連の係数を含んだものに変換するため
の変換手段と、前記要素を所定のブロックに分割するための分割手段
と、前記ブロックの各々について符号化し、前記係数はコン
パクト形式で、２進数の数列を含み、さらに前記符号化
は各々のブロックで最も大きな係数のうち先行するゼロ
の番号を符号化するための第一の効率的な符号化技術を
提供すること含み、さらに、丸められた係数は、前記ブ
ロックにおいて、最も大きいマグニチュードの先行する
ゼロの番号を変えないことを保証して丸めるためのエン
コーダ手段と、を含むことを特徴とするデータ符号化装
置。
【請求項９】前記変換は前記データのウエーブレット
変換を含むことを特徴とする請求項６または８に記載さ
れた装置。
【請求項１０】前記データはデジタル画像データを含む
ことを特徴とする請求項６または８に記載された装置。
【請求項１１】データ符号化のためのコンピュータプロ
グラムが記録されたコンピュータ可読媒体を含むコンピ
ュータプログラム製品であって、前記コンピュータプロ
グラム製品は、前記データを異なる周波数特性を有する一連の要素で、
前記要素は各々一連の係数を含んだものに変換するため
の変換手段と、コンパクト形式で前記係数を符号化し、前記係数は２進
数の数列を含み、前記符号化は、前記２進数の数列のう
ち先行するゼロの番号を符号化するための第一の効率的
な符号化技術を提供すること含み、さらに、丸められた
係数がその先行するゼロの番号を変えないように前記係
数を丸めるためのエンコーダ手段と、を含むことを特徴
とするコンピュータプログラム製品。
【請求項１２】前記丸めは有意でない係数の最初の番号
を切捨てることと、係数がゼロでない、より有意な係数
に１を加えることを含むことを特徴とする請求項１１に
記載のコンピュータプログラム製品。
【請求項１３】データ符号化のためのコンピュータプロ
グラムが記録されたコンピュータ可読媒体を含むコンピ
ュータプログラム製品であって、前記コンピュータプロ
グラム製品は、前記データを異なる周波数特性を有する一連の要素で、
前記要素は各々一連の係数を含んだものに変換するため
の変換手段と、前記要素を所定のブロックに分割するための分割手段
と、前記ブロックの各々について符号化し、前記係数はコン
パクト形式で、２進数の数列を含み、さらに前記符号化
は各々のブロックで最も大きな係数のうち先行するゼロ
の番号を符号化するための第一の効率的な符号化技術を
提供すること含み、さらに、丸められた係数は、前記ブ
ロックにおいて、最も大きいマグニチュードの先行する
ゼロの番号を変えないことを保証して丸めるためのエン
コーダ手段と、を含むことを特徴とするコンピュータプ
ログラム製品。
【請求項１４】前記変換は前記データのウエーブレット
変換を含むことを特徴とする請求項１１または１３に記
載されたコンピュータプログラム製品。
【請求項１５】前記データはデジタル画像データを含む
ことを特徴とする請求項１１または１３に記載されたコ
ンピュータプログラム製品。