ウェーブレット変換の埋め込みゼロツリー

ウェーブレット変換の埋め込みゼロツリー（EZW）は、非可逆画像圧縮アルゴリズムです。低ビットレート、つまり高圧縮率では、サブバンド変換（ウェーブレット変換など）によって生成される係数のほとんどがゼロ、またはゼロに非常に近くなります。これは、「現実世界」の画像が主に低周波情報（高い相関性）を含む傾向があるためです。しかし、高周波情報（画像のエッジなど）が発生する場合、これは人間の画質知覚において特に重要であり、あらゆる高品質符号化方式において正確に表現されなければなりません。

変換された係数を、最低周波数の係数がルートノードにあり、各ツリー ノードの子が次に高い周波数のサブバンドの空間的に関連した係数である 1 つ以上のサブツリーがゼロまたはほぼゼロの係数のみで構成される可能性が高くなります。このようなサブツリーはゼロツリーと呼ばれます。このため、ノードと係数という用語は互換的に使用し、係数の子とは、その係数が配置されているツリーのノードの子係数を意味します。子とは、ツリーの下位にある直接接続されたノードを指し、子孫とは、直接接続されていない場合でも、ツリーの特定のノードの下にあるすべてのノードを指します。

EZW やSPIHTなどのゼロツリー ベースの画像圧縮方式では、重要な係数の位置を効率的にコード化するために、ツリーの統計的特性を使用することを目的としています。係数のほとんどは 0 または 0 に近いため、重要な係数の空間位置は、一般的な圧縮画像の合計サイズの大部分を占めます。係数 (ツリーも同様) は、その大きさ (ツリーの場合はノードとそのすべての子孫の大きさ) が特定のしきい値を超える場合に重要です。最大係数大きさに近いしきい値から始めて、しきい値を繰り返し下げることで、段階的に細かい詳細を追加する画像の圧縮表現を作成できます。ツリーの構造により、特定の周波数帯域の係数が重要でない場合は、そのすべての子孫 (空間的に関連するより高い周波数帯域の係数) も重要でなくなる可能性が高くなります。

EZW は 4 つのシンボルを使用して、(a) ゼロツリー ルート、(b) 孤立したゼロ (重要ではないが重要な子孫を持つ係数)、(c) 重要な正の係数、および (d) 重要な負の係数を表します。したがって、シンボルは 2 つのバイナリ ビットで表されます。圧縮アルゴリズムは、ドミナント パスと従属パスを通る多数の反復で構成され、しきい値は各反復の後に更新されます (2 分の 1 に減少)。ドミナント パスは、ツリーをスキャンして 4 つのシンボルのいずれかを発行することにより、以前の反復でまだ重要と判断されなかった係数の重要性をエンコードします。係数の子は、係数が重要であると判断された場合、または係数が孤立したゼロであった場合にのみスキャンされます。従属パスは、以前の重要性パスで重要であると判断された各係数に対して 1 ビット (これまでに発行されていない各係数の最上位ビット) を発行します。したがって、従属パスはビットプレーン コーディングに似ています。

注目すべき重要な特徴がいくつかあります。まず、圧縮アルゴリズムをいつでも停止して元の画像の近似値を取得できます。受信ビット数が多いほど、画像の品質が向上します。次に、圧縮アルゴリズムが一連の決定として構成されているため、デコーダーで同じアルゴリズムを実行して係数を再構成できますが、決定は入力ビットストリームに基づいて行われます。実際の実装では、主パスのパフォーマンスをさらに向上させるために、算術符号などのエントロピー符号を使用するのが一般的です。従属パスからのビットは通常、十分にランダムであるため、エントロピー符号化によってそれ以上の符号化ゲインは得られません。

それ以来、EZW のコーディング パフォーマンスは、SPIHTとその多くの派生形式によって上回られています。

導入

1993年にJ. Shapiroによって開発された埋め込みゼロツリーウェーブレットアルゴリズム（EZW）は、スケーラブルな画像伝送と復号化を可能にします。EZWは4つの主要な概念に基づいています。第一に、離散ウェーブレット変換または階層的サブバンド分解であること、第二に、画像に固有の自己相似性を探索する際に重要な情報が欠落していることを予測すること、第三に、エントロピー符号化された逐次近似量子化を採用していること、そして第四に、適応算術符号化によって普遍的なロスレスデータ圧縮を実現できることです。

さらに、EZW アルゴリズムには次の機能も含まれています。

  1. 画像内でコンパクトなマルチ解像度表現を使用できる離散ウェーブレット変換。
  2. 重要性マップのコンパクトなマルチ解像度表現を提供するゼロツリー コーディング。
  3. 重要な係数のコンパクトな多精度表現のための逐次近似。
  4. ウェーブレット係数の精度、大きさ、スケール、空間位置の順に重要度を決定する優先順位付けプロトコル。
  5. 適応型マルチレベル算術符号化は、シンボルの文字列をエントロピー符号化する高速かつ効率的な方法です。

埋め込みゼロツリーウェーブレット符号化

A. 有意性マップの係数のエンコード

有意性マップでは、係数は以下の4つの異なる記号で表すことができます。これらの記号を用いて画像情報を表現することで、コーディングの複雑さを軽減できます。

1. ゼロツリールート

係数の大きさが閾値T未満であり、かつそのすべての子孫がT未満である場合、この係数はゼロツリールートと呼ばれます。また、係数がゼロツリールートとしてラベル付けされている場合、そのすべての子孫が重要ではないため、子孫にラベルを付ける必要はありません。

2. 孤立ゼロ

係数の大きさが閾値 T より低いが、依然として重要な子孫がいくつかある場合、この係数は孤立したゼロと呼ばれます。

3. 有意な正の係数

係数の大きさがレベル T のしきい値 T より大きく、かつ正である場合、その係数は有意な正の係数です。

4. 有意な負の係数

係数の大きさがレベル T のしきい値 T より大きく、かつ負である場合、それは負の有意な係数です。

B. 閾値の定義

上記で使用したしきい値は次のように定義できます。

1. 初期閾値T 0（C maxが最大係数であると仮定）

T0＝2⌊ログ2⁡Cメートル1つの×⌋{\displaystyle T_{0}=2^{\lfloor \log _{2}C_{\mathit {max}}\rfloor }}

2. 閾値T iは、前の閾値の半分まで反復的に減少する。

T私＝12T私−1{\displaystyle T_{i}={\frac {1}{2}}T_{i-1}}

C. 係数のスキャン順序

ラスタースキャンは、子ノードが親ノードより先にスキャンされることなく実行されます。また、特定のサブバンド内のすべての係数は、次のサブバンドの係数より先にスキャンされます。

D. 2パスビットプレーン符号化

（１）精製パス（または従属パス）

これにより、係数が区間[Ti, 2Ti)内にあるかどうかが判定されます。また、重要な係数ごとに改良ビットが符号化されます。

この方法では、サブバンド内の大きさとラスター順序に従って重要な係数を参照します。

（２）有意パス（または優位パス）

この手法では、まだ有意と判断されていない係数ごとにビットをコード化します。有意と判断されると、有意な係数はリファインメントパスにおける更なるリファインメントのためにリストに追加されます。また、既にゼロであると判明している係数は、再度コード化されることはありません。

例

DCTデータゼロツリースキャン順序（EZW） 63 -34 49 10 7 13 -12 7 AB BE BF E1 E2 F1 F2 -31 23 14 -13 3 4 6 -1 CD BG BH E3 E4 F3 F4 15 14 3 -12 5 -7 3 9 CI CJ DM DN G1 G2 H1 H2 -9 -7 -14 8 4 -2 3 2 CK CL DO DP G3 G4 H3 H4 -5 9 -1 47 4 6 -2 2 I1 I2 J1 J2 M1 M2 N1 N2 3 0 -3 2 3 -2 0 4 I3 I4 J3 J4 M3 M4 N3 N4 2 -3 6 -4 3 6 3 6 K1 K2 L1 L2 O1 O2 P1 P2 5 11 5 6 0 3 -4 4 K3 K4 L3 L4 O3 O4 P3 P4 D1: pnzt p ttt tztt tttttptt (20 コード) PNZT P(t) TTT TZTT TPTT (M-EZW による D1、16 コード) PNZT P(t) Z(t) TZ(p) TPZ(p) (NM-EZWによるD1、11コード) PN (t)、ゼロツリースキャンを超えるPまたはN PNZ(tp)、p=ペアT、t=トリプルT、D1コードではP/N + TT/TTT S1: 1010 D2: ztnp tttttttt S2: 1001 10 (Shapiro PDFはここまで) D3: zzzz zppnppnttnnp tpttnttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt S3: 1001 11 01111011011000 D4: zzzzzzzztznzzzzpttptpptpnptntttttptpnpppptttttptptttpnp S4: 1101 11 11011001000001 110110100010010101100 D5: zzzzztzzzzztpzzzttpttttnptppttptttnppnttttpnnpttpttppttt S5: 1011 11 00110100010111 110101101100100000000 110110110011000111 D6: zzzttzttzttttttnnttt （ http://www.polyvalens.com/wavelets/ezw/ ） 詳細: (新しい S が最初で、その他は前のサイクルによって計算されます) sステップ 1 21 321 値 D1 S1 R1 D2 S2 R2 D3 S3。 ... R3 ... D4、S4... A 63 P 1 >=48 56 Z .1 >=56 60 Z ..1 >=60 62 B -34 N 0 <48 -40 T .0 <40 -36 Z ..0 <36 -36 C -31 IZ <32 0 N 1. >=24 -28 Z .1。 >=28 -30 D 23 T <32 0 P 0. <24 20 Z .1. >=20 22 BE 49 P 1 >=48 56 .0 <56 52 Z ..0 <52 50 BF 10 T <32 0 P 0 <12 10 BG 14 T <32 0 P 1 >=12 14 BH -13 T <32 0 N 1 >=12 -14 CI 15 T <32 0 T <16 0 P 1 >=12 14 CJ 14 IZ <32 0 T <16 0 P 1 >=12 14 CK -9 T <32 0 T <16 0 N 0 <12 -10 CL -7 T <32 0 T <16 0 T <8 0 DM 3 T <16 0 T <8 0 DN -12 T <16 0 N 1 >=12 -14 DO -14 T <16 0 N 1 >=12 -14 DP 8 T <16 0 P <12 10 E1 7 T <32 0 .E,F,G,H(1,2,3,4) E2 13 T <32 0 .I,J,K(1,2,3,4) E3 3 T <32 0 .N,O,P(1,2,3,4) E4 4 T <32 0 . J1 -1 T <32 0 . J2 47 P 0 >48 40 1 >=40 44 。 J3 -3 T <32 0 J4 2 T <32 0 D = ドミナントパス (P = 正、N = 負、T = ゼロツリー、IZ = ゼロ反転) S = 従属パス; （R = 逆再構成値）

参照

参考文献

ウィキメディア コモンズには、 EZWに関連するメディアがあります。
「 https://en.wikipedia.org/w/index.php?title=Embedded_zerotrees_of_wavelet_transforms&oldid=1320622758」から取得