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

ウェーブレット変換の埋め込みゼロツリー( EZW ) は、非可逆画像圧縮 アルゴリズムです。低ビット レート、つまり高圧縮率では、サブバンド変換(ウェーブレット変換など) によって生成される係数のほとんどがゼロ、またはゼロに非常に近くなります。これは、「現実世界」の画像には主に低周波情報 (相関性が高い) が含まれる傾向があるためです。ただし、高周波情報が発生する場合 (画像のエッジなど)、これは人間の画像品質の認識という点で特に重要であり、したがって、高品質のコーディング スキームでは正確に表現される必要があります。

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

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

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

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

EZW のコーディング性能は、それ以来SPIHTとその多くの派生によって上回られています。

1993 年に J. Shapiro が開発した埋め込みゼロツリー ウェーブレット アルゴリズム(EZW) は、スケーラブルな画像伝送とデコードを可能にします。このアルゴリズムは、次の 4 つの主要な概念に基づいています。第 1 に、離散ウェーブレット変換または階層サブバンド分解であること、第 2 に、画像に固有の自己相似性を調査する際に重要な情報が存在しないことを予測すること、第 3 に、エントロピー符号化された逐次近似量子化があること、第 4 に、適応算術符号化によってユニバーサルなロスレス データ圧縮を実現できることです。

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

（１）画像内のコンパクトな多重解像度表現を使用できる離散ウェーブレット変換。

（２）有意性マップのコンパクトな多重解像度表現を提供するゼロツリー符号化。

（３）重要な係数のコンパクトな多倍長表現のための逐次近似法。

（４）ウェーブレット係数の精度、大きさ、スケール、空間位置の順に重要度を決定する優先順位付けプロトコル。

（５）適応型多値算術符号化は、記号列をエントロピー符号化する高速かつ効率的な方法である。

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

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

係数の大きさが閾値 T 未満であるが、依然としていくつかの有意な子孫が存在する場合、この係数は孤立したゼロと呼ばれます。

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

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

上記で使用したしきい値は、以下のタイプとして定義できます。

ラスタースキャンは、画像キャプチャと再構成の長方形パターンです。EZW 変換でこのスキャンを使用すると、子ノードが親ノードの前にスキャンされないように係数のスキャンが実行されます。また、特定のサブバンド内のすべての位置は、次のサブバンドに移動する前にスキャンされます。

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

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

この方法では、まだ重要とみなされていない各係数のビットをコード化します。重要と判断されると、重要な係数は、リファインメント パスでさらにリファインメントするためにリストに追加されます。また、すでにゼロであることがわかっている係数は、再度コード化されることはありません。

DCT データ ZeroTree スキャン順序 (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: zzzzzzzztznzzzzpttptpptpnptnttttptpnpppptttttptptttpnp
S4: 1101 11 11011001000001 110110100010010101100
D5: zzzzzzzzzzztpzzzttpttttnptppttptttnppnttttpnnpttpttppttt
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
体脂肪 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-1T<320。
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 = 逆再構築値）

• 階層ツリーにおけるセット分割(SPIHT)

• JM Shapiro (1993). 「ウェーブレット係数のゼロツリーを使用した埋め込み画像コーディング」. IEEE Transactions on Signal Processing . 41 (12): 3445–3462. CiteSeerX  10.1.1.131.5757 . doi :10.1109/78.258085. ISSN  1053-587X. S2CID  18047405. Zbl  0841.94020. Wikidata  Q56883112.

ウィキメディア・コモンズには、 EZWに関連するメディアがあります。

• Clemens Valens (2003-08-24). 「EZW エンコーディング」。2009-02-03 にオリジナルからアーカイブされました。