Los árboles cero integrados de transformadas wavelet ( EZW ) son un algoritmo de compresión de imágenes con pérdida . A tasas de bits bajas, es decir, relaciones de compresión altas, la mayoría de los coeficientes producidos por una transformación de subbanda (como la transformada wavelet ) serán cero o muy cercanos a cero. Esto ocurre porque las imágenes del "mundo real" tienden a contener principalmente información de baja frecuencia (altamente correlacionada). Sin embargo, cuando aparece información de alta frecuencia (como bordes en la imagen), esto es particularmente importante en términos de la percepción humana de la calidad de la imagen y, por lo tanto, debe representarse con precisión en cualquier esquema de codificación de alta calidad.
Al considerar los coeficientes transformados como un árbol (o árboles) con los coeficientes de frecuencia más bajos en el nodo raíz y con los hijos de cada nodo del árbol siendo los coeficientes relacionados espacialmente en la siguiente subbanda de frecuencia más alta, existe una alta probabilidad de que uno o más subárboles consistan completamente de coeficientes que sean cero o casi cero, dichos subárboles se denominan árboles cero . Debido a esto, usamos los términos nodo y coeficiente indistintamente, y cuando nos referimos a los hijos de un coeficiente, nos referimos a los coeficientes hijos del nodo en el árbol donde se encuentra ese coeficiente. Usamos hijos para referirnos a nodos conectados directamente más abajo en el árbol y descendientes para referirnos a todos los nodos que están debajo de un nodo particular en el árbol, incluso si no están conectados directamente.
En los esquemas de compresión de imágenes basados en árboles cero, como EZW y SPIHT , la intención es utilizar las propiedades estadísticas de los árboles para codificar de manera eficiente las ubicaciones de los coeficientes significativos. Dado que la mayoría de los coeficientes serán cero o cercanos a cero, las ubicaciones espaciales de los coeficientes significativos constituyen una gran parte del tamaño total de una imagen comprimida típica. Un coeficiente (al igual que un árbol) se considera significativo si su magnitud (o magnitudes de un nodo y todos sus descendientes en el caso de un árbol) está por encima de un umbral particular. Al comenzar con un umbral que está cerca de las magnitudes máximas del coeficiente y disminuir iterativamente el umbral, es posible crear una representación comprimida de una imagen que agrega progresivamente detalles más finos. Debido a la estructura de los árboles, es muy probable que si un coeficiente en una banda de frecuencia particular es insignificante, entonces todos sus descendientes (los coeficientes de banda de frecuencia más alta relacionados espacialmente) también serán insignificantes.
EZW utiliza cuatro símbolos para representar (a) una raíz de árbol cero, (b) un cero aislado (un coeficiente que es insignificante, pero que tiene descendientes significativos), (c) un coeficiente positivo significativo y (d) un coeficiente negativo significativo. Los símbolos pueden representarse por lo tanto por dos bits binarios. El algoritmo de compresión consiste en una serie de iteraciones a través de un paso dominante y un paso subordinado , el umbral se actualiza (se reduce por un factor de dos) después de cada iteración. El paso dominante codifica la significancia de los coeficientes que aún no se han encontrado significativos en iteraciones anteriores, escaneando los árboles y emitiendo uno de los cuatro símbolos. Los hijos de un coeficiente solo se escanean si se encontró que el coeficiente era significativo, o si el coeficiente era un cero aislado. El paso subordinado emite un bit (el bit más significativo de cada coeficiente no emitido hasta ahora) para cada coeficiente que se ha encontrado significativo en los pasos de significancia anteriores. El paso subordinado es por lo tanto similar a la codificación de plano de bits.
Hay varias características importantes a tener en cuenta. En primer lugar, es posible detener el algoritmo de compresión en cualquier momento y obtener una aproximación de la imagen original, cuanto mayor sea el número de bits recibidos, mejor será la imagen. En segundo lugar, debido a la forma en que el algoritmo de compresión está estructurado como una serie de decisiones, el mismo algoritmo se puede ejecutar en el decodificador para reconstruir los coeficientes, pero con las decisiones tomadas de acuerdo con el flujo de bits entrante. En implementaciones prácticas, sería habitual utilizar un código de entropía como el código aritmético para mejorar aún más el rendimiento del paso dominante. Los bits del paso subordinado suelen ser lo suficientemente aleatorios como para que la codificación de entropía no proporcione más ganancia de codificación.
Desde entonces, el rendimiento de codificación de EZW ha sido superado por SPIHT y sus numerosos derivados.
El algoritmo wavelet de árbol cero integrado (EZW) desarrollado por J. Shapiro en 1993 permite la transmisión y decodificación de imágenes escalables. Se basa en cuatro conceptos clave: primero, debe ser una transformada wavelet discreta o descomposición jerárquica de subbandas; segundo, debe predecir la ausencia de información significativa al explorar la autosimilitud inherente a las imágenes; tercero, tiene cuantificación de aproximación sucesiva codificada por entropía y, cuarto, permite lograr una compresión de datos universal sin pérdidas mediante codificación aritmética adaptativa.
Además, el algoritmo EZW también contiene las siguientes características:
(1) Una transformada wavelet discreta que puede utilizar una representación multirresolución compacta en la imagen.
(2) Codificación Zerotree que proporciona una representación compacta de múltiples resoluciones de mapas de significancia.
(3) Aproximación sucesiva para una representación multiprecisión compacta de los coeficientes significativos.
(4) Un protocolo de priorización cuya importancia está determinada por la precisión, magnitud, escala y ubicación espacial de los coeficientes wavelet en orden.
(5) Codificación aritmética multinivel adaptativa, que es un método rápido y eficiente para codificar por entropía cadenas de símbolos.
En un mapa de significancia, los coeficientes se pueden representar mediante los siguientes cuatro símbolos diferentes. Al utilizar estos símbolos para representar la información de la imagen, la codificación será menos complicada.
Si la magnitud de un coeficiente es menor que un umbral T y todos sus descendientes son menores que T, entonces este coeficiente se denomina raíz de árbol cero. Y si un coeficiente ha sido etiquetado como raíz de árbol cero, significa que todos sus descendientes son insignificantes, por lo que no es necesario etiquetar a sus descendientes.
Si la magnitud de un coeficiente es menor que un umbral T, pero aún tiene algunos descendientes significativos, entonces este coeficiente se llama cero aislado.
Si la magnitud de un coeficiente es mayor que un umbral T en el nivel T, y también es positivo, entonces es un coeficiente significativo positivo.
Si la magnitud de un coeficiente es mayor que un umbral T en el nivel T, y también es negativo, entonces es un coeficiente significativo negativo.
El umbral utilizado anteriormente se puede definir como el tipo siguiente.
El escaneo de trama es el patrón rectangular de captura y reconstrucción de imágenes. El uso de este escaneo en la transformación EZW consiste en escanear los coeficientes de manera que ningún nodo secundario se escanee antes que su nodo principal. Además, se escanean todas las posiciones en una subbanda determinada antes de pasar a la siguiente subbanda.
Esto determina si el coeficiente está en el intervalo [Ti, 2Ti). Y se codifica un bit de refinamiento para cada coeficiente significativo.
En este método, se visitarán los coeficientes significativos según la magnitud y el orden ráster dentro de las subbandas.
Este método codificará un bit para cada coeficiente que aún no se considere significativo. Una vez que se ha determinado la significancia, el coeficiente significativo se incluye en una lista para un refinamiento adicional en el paso de refinamiento. Y si ya se sabe que algún coeficiente es cero, no se codificará nuevamente.
Orden de escaneo de ZeroTree de datos 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 HACER 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 P4D1: pnzt p ttt tztt tttttptt (20 códigos) PNZT P(t) TTT TZTT TPTT (D1 por M-EZW, 16 códigos) PNZT P(t) Z(t) TZ(p) TPZ(p) (D1 por NM-EZW, 11 códigos) PN (t), P o N por encima del escaneo del árbol cero PNZ(tp), p=par T, t=triple T, P/N + TT/TTT en código D1T1: 1010D2: ztnp ttttttttS2: 1001 10 (El PDF de Shapiro termina aquí)D3: zzzz zppnppnttnnp tpttntttttttttptttptttttttttptttttttttttttS3: 1001 11 01111011011000D4: zzzzzzztztznzzzzpttptpptpnptntttttptpnppppttttptptttpnpS4: 1101 11 11011001000001 110110100010010101100D5: zzzzztzzzzztpzzzttpttttnptppttptttnppnttttpnnpttpttpptttS5: 1011 11 00110100010111 110101101100100000000 110110110011000111D6: zzzttztttztttttnnttt(http://www.polyvalens.com/wavelets/ezw/)Detallado: (el nuevo S es el primero, los demás se calculan mediante ciclos anteriores)s-paso 1 21 321 valor D1 S1 R1 D2 S2 R2 D3 S3. ... R3 ... D4,S4...A 63 P 1 >=48 56 Z .1 >=56 60 Z ..1 >=60 62B -34 N 0 <48 -40 T .0 <40 -36 Z ..0 <36 -36C -31 IZ <32 0 N 1. >=24 -28 Z .1. >=28-30D 23 T <32 0 P 0. <24 20 Z .1. >=20 22ES 49 P 1 >=48 56 .0 <56 52 Z ..0 <52 50BF 10 T <32 0 P 0 <12 10BG 14 T <32 0 P 1 >=12 14BH-13 T <32 0 N 1 >=12 -14CI 15 T <32 0 T <16 0 P 1 >=12 14CJ 14 IZ <32 0 T <16 0 P 1 >=12 14CK -9 T < 32 0 T < 16 0 N 0 < 12 -10CL -7 T < 32 0 T < 16 0 T < 8 0DM3 T <16 0 T <8 0DN-12 T <16 0 N 1 >=12 -14HACER -14 T <16 0 N 1 >=12 -14DP 8 T < 16 0 P < 12 10E1 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-3T <32 0J4 2 T <32 0D = pase dominante (P=positivo, N=negativo, T=ZeroTree, IZ=cero aislado)S = pase subordinado;(R = valor reconstruido posterior)
