Implementación de un cuantizador “midtread” en MATLAB 7.0

La cuantización es el paso necesario para convertir una señal analógica a una digital, cuando se muestrea una señal se convierte del mundo analógico al mundo digital, y es necesario expresarlo en 0s y 1s, dícese bits. Aunque no necesariamente es el proceso de una señal analógica per se, puede ser también, por ejemplo, una imagen que necesita ser representada con una cantidad menor de bits, y por lo consiguiente comprimirla, con pérdidas claro está.

Existen variados tipos de cuantización. El tipo de cuantizador se elige dependiendo de la aplicación en que vaya a ser implementado, esto, de acuerdo a las características de la señal. En este caso se hará un pequeño ejemplo con un cuantizador midtread la grafica siguiente muestra el comportamiento de un cuantizador midtread de 3bits.

Figura 1. Características de un cuantizador midtread de 3 bits

El principal uso de este cuantizador es cuando tenemos una señal simétrica en el espectro positivo y negativo, por ejemplo una señal de audio, aunque también se puede aplicar en una imagen, como se muestra en el párrafo siguiente.

En la Figura 1 el eje equis (x) representa la señal a cuantizar y el eje ye (y) es la información ya cuantizada, delta () son los incrementos en los que se va a dividir la señal y esto depende del número de bits que sea el cuantizador, de lo anterior se puede desprender la siguiente tabla:

Código binario	Nivel de Cuantización (y)	Rango de la señal de entrada (x)
011	-3∆	–3.5∆ <= x < –2.5∆
010	-2∆	–2.5∆ <= x < –1.5∆
001	-1∆	–1.5∆ <= x < –0.5∆
000	0	–0.5∆ <= x < 0
100	0	0 <= x < 0.5∆
101	1∆	0.5∆ <= x < 1.5∆
110	2∆	1.5∆ <= x < 2.5∆
111	3∆	2.5∆ <= x < 3.5∆

La variable delta (∆) puede ser calculada de la siguiente manera

Ora si, vamos a ver el siguiente ejemplo, tenemos la señal de entrada x(n) = 254 254 252 254 255 253 y el rango válido de datos es de 250 a 255, que bien puede ser parte de una imagen ;) .

El primer paso es calcular delta.

Sustituyendo ∆ en la tabla anterior tenemos:

Código binario	Nivel de Cuantización (y)	Rango de la señal de entrada (x)
011	-3(0.71428) = -2.14284	–2.5 <= x < –1.7857
010	-2(0.71428) = -1.42856	–1.7857 <= x < –1.07142
001	-1(0.71428) = 0.71428	–1.07142 <= x < –0.35714
000	0	–0.35714 <= x < 0
100	0	0 <= x < 0.35714
101	1(0.71428) = 0.71428	0.35714<= x < 1.07142
110	2(0.71428) = 1.42856	1.07142 <= x < 1.7857
111	3(0.71428) = 2.14284	1.7857 <= x < 2.5

Para poder tener los datos de forma como se muestra en la Figura 1, es necesario definir cual es la media de nuestro rango, que en este caso es:

Si restamos a la señal de entrada la media obtenida en el paso anterior tenemos que:

x(n) – µ = 1.5 1.5 -0.5 1.5 2.5 0.5

ahora el siguiente paso es cuantizar cada valor utilizando la tablita arriba descrita…

x(0) = 1.5, cae entre 1.07142 y 1.7857 a lo cual corresponde un valor de cuantización de 1.42856 o sea 110 binario.

x(1) = 1.5, cae entre 1.07142 y 1.7857 a lo cual corresponde un valor de cuantización de 1.42856 o sea 110 binario.

x(2) = –0.5, cae entre –0.35714 y –1.07142 a lo cual corresponde un valor de cuantización de –1.42856 o sea 010 binario.

x(3) = 1.5, cae entre 1.07142 y 1.7857 a lo cual corresponde un valor de cuantización de 1.42856 o sea 110 binario.

x(4) = 2.5, cae entre 1.7857 y 2.5 a lo cual corresponde un valor de cuantización de 2.14284 o sea 111 binario.

x(5) = 0.5 cae entre 0.35714 y 1.07142 a lo cual corresponde un valor de cuantización de 1.42856 o sea 010 binario.

A continuación se presenta el código en MATLAB 7.0 para llevar a cabo esta cuantización:

x = [254 254 252 254 255 253];

bits = 3;
rango_superior = 255;
rango_inferior = 250;

delta = (rango_superior - rango_inferior)/((2^bits)-1)

mu = ((rango_superior - rango_inferior)/2) + rango_inferior

x_centrada = x - mu

x_cuantizada = floor(x_centrada/delta+0.5) * delta

y los resultados son:

delta =

    0.7143

mu =

  252.5000

x_centrada =

    1.5000    1.5000   -0.5000    1.5000    2.5000    0.5000

x_cuantizada =

    1.4286    1.4286   -0.7143    1.4286    2.8571    0.7143

DPCM (Differential Pulse Code Modulation), Método diferencial para compresión de señales, Parte I, puro rollo

La teoría del siguiente choro mareador y las figuras pirateadas fueron tomad@s de:
Data Compression: The Complete Reference. David Salomon. Fourth Edition. Springer. 2007. Section 4.26: DPCM
Digital Signal Processing: Fundamentals and Applications. Li Tan. Academic Press. 2008. Section 11.3: Examples of Differential Pulse Code Modulation, and Adaptive DPCM G.721

La compresión por DPCM es parte de la familia de métodos compresión por codificación diferencial. La idea general es usar valores pasados recuperados como base para predecir el dato actual de entrada. Esto se basa en el hecho, por ejemplo, que los pixeles en una imagen o muestras adyacentes en el audio digitalizado se encuentran correlacionadas. Los valores correlacionados son generalmente similares, así que sus diferencias son pequeñas, esto resultando en una compresión.
A continuación se muestra el esquema simple de compresión diferencial para poder entender el principio del DPCM.



                           Codificador                                 Decodificador

Figura 1. CoDec Diferencial

La imagen anterior muestra un ejemplo de un codificador diferencial, se observa como el dato actual se almacena en una unidad de almacenamiento, llámese “Delay” (o retardo pues si no les gusta agringarse), para ser usado para codificar el siguiente dato, o sea, . Claro, la explicación anterior esta sumamente simplificada, en este ejemplo se muestra el uso de un cuantizador, eso significa que se tiene una compresión con perdidas o “lossy” y esto significa que nuestro dato codificado es realmente el cual ya contiene un error de cuantización. Esto significa que la codificación por diferencias (o diferencial, como ustedes gusten y manden) nos mete en un nuevo problema: La acumulación de errores.

Entonces hay que tomar ventaja de lo que se menciona anteriormente, los datos que se van a comprimir están correlacionados. Esto significa que en general un dato depende de varios de sus vecinos, no solamente del anterior. Una mejor predicción puede ser lograda usando N de los datos previos para codificar el valor actual , entonces tendremos una función , para predecir el dato actual .

Ora si, en seguida pueden observar (jeje, como visita al museo) el diagrama del DPCM. (oooooohhhh!)


                          Codificador                                   Decodificador

Figura 2. DPCM

Oquey, oquey, haber encuentren la(s) diferencia(s) entre la Figura 1 y la Figura 2. ¿Está fácil? ¿que no? …

…

…

Pues si, cambiamos “Delay” por “Pred.” y se acabo el asunto.

Si.

Como se explicaba antes, el predictor viene siendo la funcioncica esta:

En donde tenemos que es una función que nos afecta un conjunto de N pixeles y en base a esto obtenemos una mejor predicción de nuestro valor actual, es decir tratamos de minimizar el error introducido por la cuantificación.

Esta es la primera parte de dos, en esta ocasión fue el rollo previo a un ejemplo peque para poder explicar la DPCM.

¿Qué es compresión de Imágenes?

Antes de terminar el compresor (que en estos momentos creo que no va a servir mas que de práctica, je je je, bueno, de todos modos no pensaba desbancar al JPG, todavía), quiero explicar un poco que es la compresión de imágenes. Voy a empezar por poner un par de definiciones:

Según Gonzalez et al:

"La compresión de imágenes aborda el problema de reducir la cantidad de datos para representar una imagen digital. La compresión se logra removiendo una o más de las tres posibles redundancias básicas. (a)Redundancia de código: cuando se usan códigos de palabra menos óptimos (de menor longitud). (b)Redundancia interpixelaria: Que resulta de la correlación entre pixeles de una imagen. (c)Redundancia psicovisual: La cual se da debido a los datos que el sistema de visión humano ignora"¹

Según Wikipedia:

"Compresión de imágenes es la aplicación de la compresión de datos en imágenes digitales. En efecto, el objetivo es reducir redundancias en la imagen con el objetivo de transmitirla o almacenarla en una manera eficiente. La compresión puede ser con pérdidas (lossy), o sin pérdidas (lossless). La compresión con pérdidas que produce diferencias imperceptibles se llama también visualmente sin pérdidas (visual lossless)."²

Entonces podemos decir que se trata de reducir el número de bits con necesarios para representar una imagen. Y hay de dos tipos (que pueden ser tres, y no es el chiste del gato). Con pérdidas, sin pérdidas y visualmente sin pérdidas. En el ejemplo de compresor que estoy tratando de hacer, es un compresor con pérdidas, de una imagen en escala de grises de 8 bits.

Pero bueno, ¿cómo le hacemos para saber si el compresor que estamos haciendo vale la pena? Pues fácil, hacemos un montón de pruebas, observamos las imágenes resultantes y la que no se vea tan peor pues decimos que es nuestra imagen codificada usando un compresor con pérdidas. También lo podemos hacer de la manera fancy, usamos PSNR o MSE o cualquier otra medida de error matemática para ver que tanto se distorsiona en referencia con la imagen original.

---

1. Digital Image Processing 2nd Edition (DIP/2e)
   by Gonzalez and Woods
   © 2002. Prentice Hall
   
2. Image Compression
   From Wikipedia, the free encyclopedia. Extracted July 28th, 2009
   

Update del Compresor que estoy haciendo

• Ya tengo el algoritmo para hacer la extracción de Bits.
• Ya tengo el código para codificar la imagen binaria en RLE (gracias JMG, ya lo tenía arrinconado)
• Ya tengo el código para decodificar la imagen codificada con lo anterior

Ahora solo me falta hacer pruebas suficientes para llegar a una conclusión.

Lo voy a terminar...

... algún día.

Idea para un compresor de imágenes con pérdidas usando extracción de bits y codificación RLE a una imagen PGM

Tengo una idea para hacer un compresor de imágenes PGM (por si se preguntan, no, no tengo fijación alguna con este tipo de imágenes solo que es sencillo, ¡gulp!, trabajar con ellas) con pérdidas usando la extracción de bits (medio explicada aquí) y codificación RLE. La idea principal viene de el hecho de que al aplicar un algoritmo extracción de bits a una imagen tenemos un arreglo binario como resultado, tendremos 1 arreglo 2D de ceros y unos por cada bit extraído, es decir que para una imagen de 8-bits, tendremos 8 arreglos de binarios. De esto podemos observar que cada imagen resultante contiene información de la imagen, y se puede observar una degradación empezando del bit más significativo hacia abajo. Se pueden emplear un par de estas imágenes para codificarlas usando un algoritmo de RLE aprovechando que tendremos secuencias de unos y ceros; luego al recuperarlas y aplicarles algún tipo de técnica de Diethering, para mejorar la calidad de la imagen resultante, claro, con pérdida de información con respecto a la original.

A continuación listo los pasos que creo que son necesarios para este algoritmo:

• Aplicar la extracción de bits a la imagen. Resultado: 8 imágenes (1 por bit en este caso)
• Seleccionar las imágenes que serán empleadas para la codificación RLE. Resultado: conjunto de imágenes a comprimir.
• Aplicar RLE a un cada una de las imágenes seleccionadas en el paso anterior. Resultado: n número de conjuntos de datos (1 por imagen). El total de datos obtenidos aquí nos dará como resultado una compresión.
• Para descomprimir la imagen, aplicamos RLE inversa a los conjuntos de datos. Resultado: n número de imágenes binarias.
• Se combinan las imágenes obtenidas en el paso anterior (esto es posible asignando cada bit y reconstruyendo la imagen de 8bits). Resultado: Imagen de 8bits con pérdida de información.
• A la imagen resultante le aplicamos algún tipo de Diethering para mejorar la calidad. Resultado imagen codificada y decodificada con pérdidas.

No se hasta que punto sea posible obtener una buena imagen como resultado, o que tan buena compresión se pueda lograr para mantener un balance entre calidad de imagen y compresión.

Ya pondré los resultados en un post en cuanto tenga algo que valga la pena. :)

¿Qué tan gacha se ve la foto matemáticamente hablando? Parámetros para medir el desempeño de un algoritmo de compresión de datos con pérdidas

En la compresión de datos, lo que se busca presisamente es comprimir, valga la redundancia (y no es chiste), o sea, reducir en tamaño los datos originales, y esto es principalmente con dos fines: almacenamiento y transmisión. Existen dos tipos de compresión usados comúnmente:

1. Con pérdidas (Loosy): Se refiere a los algoritmos que comprimen los datos, pero que al recuperarlos no se tiene la información original, sino un aproximado, todo se basa en la subjetividad.
2. Sin pérdidas (Lossless): Como su nombre lo indica, se reduce el número de datos para representar la información, pero al recuperarse se reproduce tal como la original.

Usualmente, el primero ofrece una compresión mayor en comparación con el otro, y esto es de una manera obvio, debido a que al ser un algoritmo que permite pérdidas, entonces es menor la cantidad de información necesaria.

Una de las medidas más usadas en imágenes y audio es el promedio de errores cuadrados (MSE: mean square error):

Ahora, si queremos el error relativo a la señal se calcula el error de la señal reconstruida y el MSE, y a esta relación se le llama relación de señal a ruido (SNR: Signal to Noise Ratio) y esta dada por:

El SNR se mide comúnmente en escala logarítmica, en decibeles (dB) y se representa cómo:

 

Hay veces que es necesario conocer el error relativo al valor máximo, o valor pico de la señal, y a esto se le llama Razón de la Señal Pico al Ruido (PSNR: Peak Signal to Noise Ratio) y se calcula de la siguiente manera:

Existen otras medidas que se emplean para medir la distorción de manera frecuente, un ejemplo usado para evaluar algoritmos de compresion de imágenes es el del promedio de diferencias absolutas:

Cuando la distorción es imperceptible entonces se calcula el valor de la magnitud del error:

Los parámetros mencionados en este post, son como ya se mencionó, para medir el desempeño de los algoritmos de compresión, y una pregunta que me hice al empezar a estudiar esto, ¿y qué demonios me dice esto o para que me sirve? A, pues medio simple, son números que nos sirven para determinar que tan “fiel” a la original esta la señal y se usan estos números para tomar un tipo de decisión o llegar a una conclusión en cuanto al algoritmo utilizado.

¿Capish?