Hispanopedia WikiEl algoritmo EZW ( Embedded zerotrees of wavelet transforms ) es un algoritmo de compresión de imágenes con pérdida . A bajas tasas de bits, es decir, con altas relaciones de compresión, la mayoría de los coeficientes generados por una transformada de subbanda (como la transformada wavelet ) serán cero o muy cercanos a cero. Esto se debe a que 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 los bordes de la imagen), esta es particularmente importante para 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 varios árboles) con los coeficientes de menor frecuencia 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 estén compuestos enteramente por coeficientes iguales o casi iguales a cero; dichos subárboles se denominan árboles cero . Por ello, utilizamos 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 dicho coeficiente. Utilizamos el término hijos para referirnos a los nodos conectados directamente en niveles inferiores del árbol y descendientes para referirnos a todos los nodos que se encuentran 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 de ceros, como EZW y SPIHT , el objetivo es utilizar las propiedades estadísticas de los árboles para codificar de manera eficiente la ubicación 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 las magnitudes de un nodo y todos sus descendientes en el caso de un árbol) supera un umbral determinado. Al comenzar con un umbral cercano a las magnitudes máximas de los coeficientes y disminuirlo iterativamente, es posible crear una representación comprimida de una imagen que añade 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 no es significativo, entonces todos sus descendientes (los coeficientes de bandas de frecuencia más altas espacialmente relacionados) también lo serán.
EZW utiliza cuatro símbolos para representar (a) una raíz de árbol de ceros, (b) un cero aislado (un coeficiente insignificante, pero con descendientes significativos), (c) un coeficiente positivo significativo y (d) un coeficiente negativo significativo. Los símbolos pueden representarse mediante dos bits binarios. El algoritmo de compresión consta de varias iteraciones a través de una pasada dominante y una pasada subordinada ; el umbral se actualiza (se reduce a la mitad) después de cada iteración. La pasada dominante codifica la significancia de los coeficientes que aún no se han considerado significativos en iteraciones anteriores, escaneando los árboles y emitiendo uno de los cuatro símbolos. Los hijos de un coeficiente solo se escanean si el coeficiente se ha considerado significativo o si el coeficiente era un cero aislado. La pasada subordinada emite un bit (el bit más significativo de cada coeficiente que aún no se ha emitido) por cada coeficiente que se ha considerado significativo en las pasadas de significancia anteriores. Por lo tanto, la pasada subordinada es similar a la codificación de plano de bits.
Cabe destacar varias características importantes. 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 estructura del algoritmo de compresión, que se basa en una serie de decisiones, se puede ejecutar el mismo algoritmo en el decodificador para reconstruir los coeficientes, pero con decisiones que se toman en función del flujo de bits de entrada. En implementaciones prácticas, se suele utilizar un código de entropía, como un código aritmético, para mejorar aún más el rendimiento de la pasada dominante. Los bits de la pasada subordinada suelen ser lo suficientemente aleatorios como para que la codificación de entropía no proporcione ninguna mejora adicional.
El rendimiento de codificación de EZW ha sido superado desde entonces por SPIHT y sus numerosos derivados.
Introducción
El algoritmo de ondículas de árbol cero integrado (EZW), desarrollado por J. Shapiro en 1993, permite la transmisión y decodificación de imágenes a gran escala. Se basa en cuatro conceptos clave: primero, debe ser una transformada discreta de ondículas o una 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, posee una cuantizació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 incluye las siguientes características:
- Una transformada wavelet discreta que puede utilizar una representación multirresolución compacta en la imagen.
- Codificación Zerotree, que proporciona una representación multirresolución compacta de mapas de significancia.
- Aproximación sucesiva para una representación compacta de precisión múltiple de los coeficientes significativos.
- Un protocolo de priorización en el que la importancia se determina por la precisión, magnitud, escala y ubicación espacial de los coeficientes wavelet en orden.
- Codificación aritmética multinivel adaptativa, un método rápido y eficiente para la codificación entrópica de cadenas de símbolos.
Codificación wavelet zerotree incrustada
A. Codificación de un coeficiente del mapa de significancia
En un mapa de significancia, los coeficientes se pueden representar mediante los siguientes cuatro símbolos diferentes. Al usar estos símbolos para representar la información de la imagen, la codificación será menos compleja.
1. Raíz de Zerotree
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 etiquetarlos.
2. Cero aislado
Si la magnitud de un coeficiente es menor que un umbral T, pero aún tiene algunos descendientes significativos, entonces este coeficiente se denomina cero aislado.
3. Coeficiente positivo significativo
Si la magnitud de un coeficiente es mayor que un umbral T en el nivel T, y además es positivo, entonces es un coeficiente significativo positivo.
4. Coeficiente negativo significativo
Si la magnitud de un coeficiente es mayor que un umbral T en el nivel T, y además es negativo, entonces es un coeficiente negativo significativo.
B. Definición del umbral
El umbral utilizado anteriormente se puede definir de la siguiente manera.
1. Umbral inicial T 0 , suponiendo que C max es el coeficiente más grande
2. El umbral T i se reduce iterativamente a la mitad del valor del umbral anterior.
C. Orden de escaneo para los coeficientes
El escaneo raster se utiliza de tal manera que ningún nodo hijo se escanea antes que sus nodos padres. Además, todos los coeficientes de una subbanda determinada se escanean antes que los de la siguiente subbanda.
D. Codificación de planos de bits de dos pasadas
(1) Paso de refinamiento (o paso subordinado)
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 analizarán los coeficientes significativos según la magnitud y el orden del ráster dentro de las subbandas.
(2) Pase significativo (o pase dominante)
Este método codificará un bit para cada coeficiente que aún no se considere significativo. Una vez que se determine su significancia, el coeficiente significativo se incluirá en una lista para su posterior refinamiento en la fase de refinamiento. Si algún coeficiente ya se sabe que es cero, no se volverá a codificar.
Ejemplo
Orden de escaneo 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 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 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 de árbol cero PNZ(tp), p=par T, t=triple T, P/N + TT/TTT en código D1 S1: 1010 D2: ztnp tttttttt S2: 1001 10 (Fin del PDF de Shapiro) D3: zzzz zppnppnttnnp tpttntttttttttptttptttttttttpttttttttttttt S3: 1001 11 01111011011000 D4: zzzzzzztztznzzzzpttptpptpnptntttttptpnppppttttttptptttpnp S4: 1101 11 11011001000001 110110100010010101100 D5: zzzzztzzzzztpzzzttpttttnptppttptttnppnttttpnnpttpttppttt S5: 1011 11 00110100010111 110101101100100000000 110110110011000111 D6: zzzttztttztttttnnttt ( http://www.polyvalens.com/wavelets/ezw/ ) Detallado: (primero se calcula el nuevo S, los demás se calculan antes de los ciclos) s-step 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 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 = paso dominante (P=positivo, N=negativo, T=Árbol de ceros, IZ=cero izolado) S = pase subordinado; (R = valor reconstruido)
Véase también
Referencias
Enlaces externos
- Clemens Valens (24 de agosto de 2003). "Codificación EZW" . Archivado del original el 3 de febrero de 2009.
- Compresión de imágenes
- Árboles (estructuras de datos)
- Algoritmos de compresión con pérdida
- Compresión de datos
