JP2000295618A - 埋込み型ゼロトリーパターン及びビットプレーンを使用する画像符号化方法 - Google Patents

Abstract

(57)【要約】 【課題】 符号化記号を、分離した値ビット及びトリー
ビットに分割し、子ノードクラスタ内で符号化するゼロ
トリー画像符号化方法を提供することである。 【解決手段】 本画像符号化方法は、ウェーブレット分
解を使用し、重要度及びリファインメントのための値ビ
ットと、トリー構造重要度のためのトリービットとを含
む４つの子係数のクラスタをビットプレーンについて符
号化する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ディジタル画像圧
縮、及び符号化（コーディング）及び復号（デコーディ
ング）に関する。

【０００２】

【従来の技術】ＪＰＥＧ、またはＭＰＥＧ内のＩフレー
ムにおけるように単一のフレームを符号化及び圧縮する
ために、Shapiroは、41 IEEE Tr. Sig, Proc. 3445 (19
93)に所載のEmbedded Image Coding Using Zerotrees o
f Wavelet Coefficientsにおいて、ウェーブレット係数
を異なるスケールでグループ化し、スケールにまたがる
ゼロ係数を予測するウェーブレット階層サブバンド分解
を提唱している。これは、低めのビットレートのビット
ストリームが、高めのビットレートのビットストリーム
内に埋込まれることから、等化及び完全埋込み型のビッ
トストリームを提供する。図２ａ−２ｃはウェーブレッ
ト変換分解を示している。

【０００３】符号化効率は、解像力に関して、どのよう
な画像圧縮方法にとっても重要である。しかしながら、
符号化方法の特色または特性が、その方法を実行する時
の有用性を決定する上で益々重要な役割を果たすように
なってきた。スケーラビリティは、ディジタル写真、イ
ンターネット、画像データベース等のような多くの応用
におけるどの画像符号化方法にとっても極めて重要な特
色である。スケーラビリティ特性には多くの面が存在す
るが、それらは以下のように要約することができる。

【０００４】品質スケーラビリティ：ビットストリーム
は、（複雑な処理をしなくとも）元の画像とは異なる品
質で再構成するように復号可能なサブビットストリーム
にパーズすることができる。重要なケースは累進（プロ
グレッシブ）品質スケーラビリティであり、これはビッ
トストリームを累進的に復号し、受信されるビットが多
くなるにつれて再構成される画像を益々良好にすること
ができることを意味している。

【０００５】分解能スケーラビリティ：ビットストリー
ムは、元の画像とは異なる分解能で表現するサブビット
ストリームにパーズ(parse)することができる。累進分
解能スケーラビリティが特別なケースである。

【０００６】計算の複雑さスケーラビリティ：この品質
によって、応用は、殆どの符号化モジュールの変更を最
小に抑えながら、符号化／復号の複雑さを容易に調整す
ることができる。

【０００７】デコーダが、符号化時には決定することが
できないそれ自体の制約に従って望ましい分解能及び望
ましいレートを選択できるようにするために、品質及び
分解能の両スケーラビリティを同一のビットストリーム
内に存在させることが望まれることが多い。計算の複雑
さスケーラビリティは、主として、この方法のメモリ要
求及び速度プロファイルに関係がある。多くの埋込み型
システムにおいては、メモリは重大な制約であり、符号
化／復号の速度は非常に重要である（例えば、ディジタ
ルスチールカメラにおいては、１つのショットから次の
ショットまでの遅れがカメラを評価する上で重要な品質
ファクタである）。

【０００８】良好な符号化方法は、これらの全ての要求
の間を良好に平衡させることができるべきである。

【０００９】

【関連出願とのクロスレファレンス】本願は、03/08/99
付暫定特許出願一連番号第60/123,330号からの優先権を
請求する。以下の係属出願は関連内容を開示している。

【００１０】

【発明の概要】本発明は、符号化記号を、分離した値ビ
ットとトリー（木）ビットに分割し、子ノードクラスタ
内で符号化するゼロトリー画像符号化方法を提供する。
この「埋込み型ゼロトリーパターン及びビットプレー
ン」（ embedded zerotree patterns and bitplanes ：
ＥＺＰＡＢ）方法は、ゼロ係数の大きいクラスタを符号
化するゼロトリーと、非ゼロ係数の大きさを符号化する
ビットプレーン符号化とを使用する。

【００１１】これは、この方法が品質及び空間分解能に
おいてだけではなく、計算の複雑さにおいてもよりスケ
ーラブルであることが、他のウェーブレットコーダ（他
のゼロトリーベースの画像コーダを含む）に優る長所で
ある。ＥＺＰＡＢは、無エントロピー符号化モード、及
び、計算の複雑さ／電力消費と符号化効率との間に良好
なトレードオフを与える文脈ベースの算術符号化モード
をオプションで使用できるようになっている。同時に、
それは最少量のメモリを使用し、そのサイズは画像サイ
ズとは無関係である。

【００１２】

【発明の実施の形態】概要 好ましい実施の形態の埋込み型ゼロトリーパターン及び
ビットプレーン（ＥＺＰＡＢ）符号化方法は、画像のウ
ェーブレット係数をビットプレーン毎に符号化する。Ｈ
Ｈ、ＬＨ、またはＨＬサブバンド（最精分解レベル以外
の）内の各位置に、ビットプレーン内のその位置に関連
する２つのビット、即ち、その位置におけるウェーブレ
ット係数の値を表すビット（値ビット）、及びその位置
に根付いたクウォッドトリーの重要度を表すビット（ト
リービット）が存在する。同じ親を有する４つの全ての
近傍のための値ビット及びトリービットを符号化し、１
つの４係数クラスタから次のクラスタへ、最粗分解レベ
ルから最精分解レベルへ、及び１つのトリーブロックか
ら次のトリーブロックへ進む。値ビットは、重要度値ビ
ット、符号値ビット、及び（大きさの）リファインメン
ト値ビットとして更に分類することができる。走査手順
の後に、たとえエントロピー符号化（即ち、単に、符号
化されていないビットをビットストリーム内に配置す
る）をどのようにも使用しなくても、良好な符号化効率
を達成することができる。別のオプションは、文脈ベー
スの算術符号化を用いてこれらの値ビット及びトリービ
ットを符号化することである。符号化効率が約10−15％
良くなり、これは公知の最良コーダに匹敵しているにも
拘わらず、メモリに対する要求が少なく、且つより高速
であるという長所を有している。

【００１３】システム 図１は、ＥＺＰＡＢコーダの総合手順を示している。画
像は、ブロック毎のモード、またはライン毎のモードの
何れかで入力することができる。画像をウェーブレット
係数に変換するために、局所化ウェーブレット変換が使
用される。次いで、これらのウェーブレット係数はトリ
ー構造データに編成され、トリーバッファ内に格納され
る。ゼロトリーの準備が整うと、システムはＥＺＰＡＢ
符号化モジュールを要求してトリー構造化データをＥＺ
ＰＡＢモジュールへ送る。バッファ内にトリーが残され
ていなくなると、バッファは、さらなる画像データを入
力するように（この場合も、ブロック毎に、またはライ
ン毎に）入力モジュールへ信号を送る。符号化システム
の中枢部分は、単一のフルデプス（ full depth ）ゼロ
トリーに作用するＥＺＰＡＢコーディングモジュールで
ある。単一のゼロトリーのための符号化手順に関して
は、次のセクションにおいて詳述する。ビットは、ＥＺ
ＰＡＢ符号化モジュールから直接伝送することも、また
は伝送のために先ず算術的に符号化することもできる。
大きさスケールは、最小の量子化レベルで全てのトリー
が符号化されて伝送バッファ内に入れられた後に、単に
先行重要度ビットプレーンを削除することによって決定
される。

【００１４】単一のゼロトリー上のＥＺＰＡＢ符号化 図２ｄは、４レベル分解のケースのためのフルデプスゼ
ロトリーの構造を示している。各非葉ノード（Ｐ）は４
つの子ノードを有している。これら４つの子ノードクラ
スタ（Ａ、Ｂ、Ｃ、Ｄ）が、ＥＺＰＡＢの基本符号化単
位である。トップレベルから下方に、また左から右へ進
む。各クラスタ毎に、先ずそれらの重要度、または大き
さリファインメントビットを、次いでゼロトリーの重要
度を指示する３ビット（最精分解レベルのためのものを
除く）を符号化する。

【００１５】重要度ビットＳ（Ａ）、Ｓ（Ｂ）、Ｓ
（Ｃ）、及びＳ（Ｄ）の符号化 符号化文脈からその重要度を導出することができない４
つの各子クラスタ（即ち、それらは、現ビットプレーン
において無意味であることが既に見出されているゼロト
リーの部分ではない）毎に、それらの重要度を明示的に
符号化する。

【００１６】ＡからＤまでの重要度ビットを符号化し、
有意であることが既に見出されている係数のために、代
わりにリファインメント（大きさ）ビットを送る。新し
い有意係数のために、その符号ビットを符号化する。

【００１７】以下は、この手順を記述する擬似コードで
ある。 for (T in [A,B,C,D]) { if (T is already found significant) send/encode refinement bit ; continue ; if (T is not at the finest decomposition level, or, T is not at loca tion D) { send/encode S(T), the significance bit of T ; if(T is significant) send/encode sign bit of T ; } else /* T is at the finest decomposition level and at D */ { if (A, B, C) are all insignificant) T must be significant, no need to send any significance bit send/encode the sign bit of T Else Send/encode S(T) if (T is significant) send/encode the sign bit of T } }

【００１８】そのクラスタは有意ではあるがノードＡ、
Ｂ、及びＣは有意ではない場合のように、最精分解レベ
ル内のノードＤは、それらのコードが先行コードによっ
て決定される場合にはスキップできることに注目された
い。

【００１９】Ａ、Ｂ、Ｃ、Ｄのための値ビットを符号化
した後に、これら４つの位置に関連する４つのトリービ
ットを符号化する。葉は如何なる子も有していないの
で、最精分解レベルのためのトリービットを符号化する
必要がないことに注目されたい。以下は、トリービット
を符号化するための手順を記述している。 if (all A,B,C,D tree-bits are insignificant) send/encode one bit to indicate that all A,B,C,D are insignifican t ; else { for (Tree routed at [A,B,C,D] { if (Tree is already found significant) continue ; if (Tree is not at location D) send/encode the significance of Tree ; else if (trees at A,B,C are all insignificant) no need to send any bit, Tree at D must be significant else send/encode the significance bit } }

【００２０】この場合も、クラスタが少なくとも１つの
有意トリービットを有しているがノードＡ、Ｂ、及びＣ
は有意トリービットを有していない場合のように、ノー
ドＤは、それらのコードが先行コードによって決定され
る場合にはスキップできることに注目されたい。

【００２１】また、以上の全てにおいては、より大きい
ゼロトリーの部分ではない４つの近傍クラスタのための
トリービットまたは値ビットだけが符号化されている。
そうでない場合には、それらの重要度をプロセスの文脈
から導出することができる。

【００２２】上述した両手順の“送れ（send）”または
“符号化せよ（encode）”は、２つのモードのどちらを
動作可能にするのかを指示するために使用されている。
極めて低い複雑さモードの場合には“送れ”が使用さ
れ、これは、ここではエントロピー符号化は行われず、
ビットをビットストリーム内に配置するだけであること
を意味している。計算集中モードの場合には“符号化せ
よ”が使用され、これは、文脈ベースの算術符号化でビ
ットを符号化することを意味する。値ビットの場合に
は、文脈は、同一クラスタ内の有意係数の数、並びに現
係数（Ａ、Ｂ、Ｃ、またはＤ）の位置（４×４＝16文脈
の合計である）によって決定される。トリービットの場
合には、文脈は、同一クラスタ内の有意トリーの数、及
び同一位置における係数の重要度（４×２＝８文脈の合
計である）によって決定される。

【００２３】以上説明したように、異なる特色の全ての
間を収支決算する符号化方法が提供されている。これに
より、算術またはハフマン符号化を必要としないモード
が可能になる。ゼロトリーパターンを表すビット、係数
符号、及び大きさビットは、最終ビットストリームへ直
接出力される。一方、符号化手順を何等変更することな
く（同一の変換、係数走査、ゼロトリー形成手順で）、
これらの同一ビットを文脈ベースの算術符号化を用いて
符号化することができる。これら２つのモードの間で
は、全ての特色及びメモリ要求は同一に維持されている
が、算術符号化及び文脈形成を排除したことによって重
要なスピードアップを達成することができる。

【００２４】図４は、符号化の例を示している。詳述す
れば、図４はフルデプストリーを通る垂直スライス内の
４つのノードの符号化を表している。列は最も左が最上
位ビットであるビットプレーンを表し、行は最粗から最
精分解レベル（最も上が最粗）の値ビット及びトリービ
ットを表している。従って、符号化はトリーを通してト
ップからボトムへ進み、またビットプレーンを通して左
から右へ進む。第１列のトップに示されている０は、最
上ビットプレーン内の最粗レベルにおける無意味値を表
している。この０の下の１は、この最粗レベルノードが
ゼロトリーの根であること（即ち、最上ビットプレーン
内では、このフルデプストリーの全ての子孫のは無意味
である）を示している。全ての子ノード係数が無意味で
あるので、第１列の残余に示されているように、それら
は符号化の際にスキップされる。

【００２５】第２列の最も上のエントリの１は、最粗レ
ベルノードが次に最上のビットプレーン内において有意
である（即ち、対応係数の値がこのビットプレーン内の
その第１の非０ビットを有している）ことを表し、±
は、その係数の符号を表すために第２の値ビットが使用
されていることを表している。第２行内の１は、全ての
子が未だに無意味であり、スキップされることを表して
いる。

【００２６】第３列の最も上のエントリは、最粗レベル
ノードにおける係数の２進展開の第２（リファインメン
ト）ビットを表している。ここでも、第２行内の１はゼ
ロトリーであり、これらの子もスキップされることを表
している。

【００２７】第４列の最も上のエントリは、最粗レベル
ノードにおける係数の第３（リファインメント）ビット
を表している。第２行内の０は、子ノードの少なくとも
１つが第４ビットプレーン内に有意係数を有しているこ
とを表している。従って、第２レベルの４つの子のクラ
スタは、それらの値ビットと、符号化されるそれらのト
リービットとを有している。第３行内の第２レベルの
（クラスタの）子ノードの値ビットが０であることは、
その係数がこの（第４）ビットプレーン内では未だに無
意味であることを示しているが、トリービットが０であ
ることは第３または第４の何れかのレベル内の少なくと
も１つの子孫が有意であることを表している。第５行内
の１は、この第３レベルの子ノードの係数がこのビット
プレーン内にその先行非０ビットを有していることを表
し、またこの場合も±は符号を表しており、そのクラス
タ内の他の３つのノードはこの時点に符号化されるそれ
らの値ビットを有している。第６行内の１は、この第３
レベルの子がゼロトリーの根であり、従ってその４つの
子はスキップされることを表している。そのクラスタ内
の他の３つのノードは、この時点に符号化されるそれら
のトリービットを有している。

【００２８】第５列（ビットプレーン）はトップからボ
トムへ、最粗レベルノード係数のための第４（リファイ
ンメント）ビットと、トリーが既に第４列において有意
であることが見出されているためにトリービットの第２
行のスキップとを有している。第３行の１及び±は、こ
の第２レベルの子の係数がこのビットプレーン内にその
第１有意（非０）ビットと、その符号とを有しているこ
とを示す２つのビットである。トリーが既に第４ビット
プレーンにおいて有意であることが見出されているの
で、第４行のトリービットはスキップされる。第５行は
第３レベルの子の係数のための第２（リファインメン
ト）ビットであり、第６行の０は第４レベルの少なくと
も１つの子がこのビットプレーンにおいて有意であるこ
とを指示している。第７行の１及び±は、この第４レベ
ルの子の係数がこのビットプレーン内にその第１有意
（非０）ビットと、その符号とを有していることを示す
２つのビットである。第６列（ビットプレーン）は、リ
ファインメントビットとしての値ビット、及び先行トリ
ー重要度の故にトリービットがスキップされることを示
している。

【００２９】復号 ビットストリームの復号は、ＥＺＰＡＢ符号化に従って
ビットを解釈してウェーブレット係数を回復し（どのよ
うな数のリファインメントビットが使用可能である
か）、次いで逆ウェーブレット変換を遂行して画像を回
復する。勿論、伝送または格納のために、誤り修正及び
他のチャンネル符号化を賦課することができる。

【００３０】実験結果 このセクションにおいては、提唱した方法を使用した符
号化の結果を説明する。この実験にはＥＺＰＡＢコーダ
の両オプション、即ち、オプションＡ：無エントロピー
符号化、及びＢ：算術符号化の使用、を使用した。広く
使用されている画像Lena (512×512)を選択した。結果
は、各ビットプレーンにおける各サブバンド毎に４バイ
トの再同期マーカー（重大なオーバヘッドではあるが、
誤り許容特性を良好にするために必要である）を含む全
てのオーバヘッドを含んでいる。

【００３１】表 １． 符号化の結果

【００３２】以上の記載に関連して、以下の各項を開示
する。

【００３３】１． 画像符号化方法であって、 （ａ）ディジタル画像の一部分を、係数の階層トリーに
ウェーブレット変換するステップと、（ｂ）上記階層ト
リーの第１のトリーに対して、及び上記第１のトリーの
第１の親ノードから導出した複数の子ノードの第１のク
ラスタに対して、上記第１の親ノードを符号化した後に
上記第１のクラスタ内の複数の各子ノード毎に値及びト
リー指示を符号化するステップと、を含み、(i)上記値
及びトリー指示は、上記第１の親ノードの上記符号化が
そのように指示している時にはスキップされ、(ii)上記
複数の子ノードの第１のものの上記トリー指示は、上記
複数の子ノードの上記第１のものの子孫ノードの重要度
を指示し、(iii) 上記複数の子ノードの上記第１のもの
の上記値は、上記複数の子ノードの上記第１のものの重
要度を指示し、(iv)上記複数の子ノードの１つの上記値
及びトリー指示は、上記第１のクラスタの上記複数の子
ノードの他のものの符号化から決定可能である時にはス
キップされ、そして、(v)上記トリー指示は、もし上記
第１のクラスタ内の上記複数の子ノードが子孫ノードを
有していなければ省略されるようになっており、（ｃ）
上記ステップ（ｂ）を、上記第１のトリーの第２、第
３、・・・、及び第Ｎの親ノードから導出された複数の
子ノードの第２、第３、・・、及び第Ｎのクラスタにつ
いて繰り返すステップと、（ｄ）上記ステップ（ｂ）−
（ｃ）を、上記階層トリーの第２、第３、・・、及び第
Ｍのトリーについて繰り返すステップと、を更に含んで
いることを特徴とする画像符号化方法。

【００３４】２． （ａ）ステップ（ｂ）−（ｃ）を、
上記係数の各ビットプレーン毎に繰り返すことを特徴と
する上記１．に記載の方法。

【００３５】３． （ａ）ステップ（ｂ）−（ｃ）は、
１つの子ノードに関して、共通クラスタの他の複数のノ
ードを含む文脈を使用して上記位及びトリー指示の算術
符号化を含んでいることを特徴とする上記１．に記載の
方法。

【００３６】４．（ａ）上記値は、重要度ビットと符号
ビット、無意味ビット、リファインメントビット、及び
スキップからなるグループのメンバーである上記２．に
記載の方法。

【００３７】５．（ａ）上記トリー指示は、ゼロトリー
の根、有意子孫ノード、及びスキップからなるグループ
のメンバーである上記２．に記載の方法。

【００３８】６． ウェーブレット分解を使用し、重要
度及びリファインメントのための値ビットと、トリー構
造重要度のためのトリービットとを含む４つの子係数の
クラスタをビットプレーンに関して符号化する画像符号
化方法。

【図面の簡単な説明】

【図１】ＥＺＰＡＢコーダの総合手順を示す流れ図であ
る。

【図２】ａ−ｄは、ウェーブレット分解及びトリー構造
を示す図である。

【図３】流れ図である。

【図４】例を示す図である。

Claims (1)

【特許請求の範囲】
1. 【請求項１】 画像符号化方法であって、 （ａ）ディジタル画像の一部分を、係数の階層トリーに
   ウェーブレット変換するステップと、 （ｂ）上記階層トリーの第１のトリーに対して、及び上
   記第１のトリーの第１の親ノードから導出した複数の子
   ノードの第１のクラスタに対して、上記第１の親ノード
   を符号化した後に上記第１のクラスタ内の複数の各子ノ
   ード毎に値及びトリー指示を符号化するステップと、を
   含み、 (i)上記値及びトリー指示は、上記第１の親ノードの上
   記符号化がそのように指示している時にはスキップさ
   れ、(ii)上記複数の子ノードの第１のものの上記トリー
   指示は、上記複数の子ノードの上記第１のものの子孫ノ
   ードの重要度を指示し、(iii) 上記複数の子ノードの上
   記第１のものの上記値は、上記複数の子ノードの上記第
   １のものの重要度を指示し、(iv)上記複数の子ノードの
   １つの上記値及びトリー指示は、上記第１のクラスタの
   上記複数の子ノードの他のものの符号化から決定可能で
   ある時にはスキップされ、そして、(v)上記トリー指示
   は、もし上記第１のクラスタ内の上記複数の子ノードが
   子孫ノードを有していなければ省略されるようになって
   おり、 （ｃ）上記ステップ（ｂ）を、上記第１のトリーの第
   ２、第３、・・・、及び第Ｎの親ノードから導出された
   複数の子ノードの第２、第３、・・、及び第Ｎのクラス
   タについて繰り返すステップと、 （ｄ）上記ステップ（ｂ）−（ｃ）を、上記階層トリー
   の第２、第３、・・、及び第Ｍのトリーについて繰り返
   すステップと、を更に含んでいることを特徴とする画像
   符号化方法。