Quantization by Dummies

Every time it happens to me, I remember the episode in The Simpsons where Homer wants to get a raise when he was working at Bowlarama, he proposes to Al to triple the business, then you can see Homer reading “Advanced Marketing”, next scene the book is in trash bin and Homer is reading “Basic Marketing”, after that you can see a pile of books in the trash and Homer looking for the word “marketing” at the dictionary…

I had to read an technical article related to Quantization and present an explanation for the Digital Image Processing class in a workshop session. The teacher gave us a list of articles related to quantization and she asked us to choose one of them. The first problem we faced was the availability of the papers, although the university has some kind of subscription with IEEE and ScienceDirect, the number of articles available for us to download was very limited and the date of them was quite old.

While looking at the titles of the papers “the” question was arisen, which article should I choose? First of all looked at the articles that sounded good to me, then I realized that none of them were available from IEEE, and couldn’t connect to ScienceDirect from school. Then I started searching any article from the list available from IEEE was “Generalized Scalar Quantizer Design Using Dynamic Programming” (bear in mind that if you don’t have a subscription you can’t see the article). The article is three pages long, but I couldn’t get to understand it enough to make a presentation.

I gave up searching the articles from the list and started surfing with Saint Google, I don’t remember the keywords I used to search, but I came up with “Optimal Entropy-Constrained Scalar Quantization of a Uniform Source”. It’s funny because while writing this post I was looking for the link to this file and found that the one of the coauthors of the article, ANDRÁS GYÖRGY,  has a bunch of his papers published listed in his publication's page, are available to download and some of them are about quantization.

After that, troubles has just begun, I started reading the article, and realized that most of the ideas were unclear to me, then I had to go to the books to search for the definition of the term I was stuck with, but while reading the definition I found also some things that for the moment I wasn’t able to understand, besides that I couldn’t found any ‘for dummies’ book about digital image processing, go figure, and it’s obvious there is no such thing. So I was reading in circles, finally, I put some kind of order in my ideas and made a presentation with the concepts I got. Still, it wasn’t enough to be clear the concept proposed in the paper, at least for me.

The best thing that I recall from this exercise is that it helped me to understand that research is not easy, but reading and sharing the little knowledge acquired, is the only way to start learning new things, it opens the mind to a different level, because we can see the work other people involved in the same field is doing, and also get fresh ideas from our peers, remember that feedback is always good and there is no such thing as “constructive nor destructive” critics.

¿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?

¿Cómo demonios se supone que debo interpretar esto? Cuantización escalar uniforme de una imagen en MATLAB

Una parte fundamental del procesamiento digital de imágenes, es la representación de una imagen. De manera muy general, si vemos una imagen como parte de un sistema de adquisición de datos, el sensor es el que se encarga de capturar el brillo de la luz y convertirla a valores que puedan ser usados digitalmente, es nuestro convertidor análogo a digital. De acuerdo a lo que establece Sonka, Hlavac y Boyle en Image Processing, Analysis, and Machine Vision (Ed. Thompson, 2008, USA), la transición entre los valores continuos de la función de la  imagen (brillo) y sus equivalentes en el mundo digital se le llama cuantización, y el número de niveles de cuantización debe ser lo suficientemente grande como para permitir que el ser humano perciba los detalles finos del sombreado en la imagen. 

En este ejemplo vamos a trabajar con una imagen PGM, que al leerla en MATLAB nos regresa una matriz de tamaño NxM. Cada elemento representa un pixel en la imagen, con valores que van de 0 a 255, es decir 256 valores diferentes (8bits). A esta imagen también le podemos aplicar una cuantización ya que con menos bits es posible representar la imagen, con pérdidas debido a que son menos niveles de grises disponibles para mostrar la imagen.

1. %Lee imagene PGM
2. imagen = double(imread('peppers.pgm'));
3. %Crea variables temporales
4. imgQuantized = zeros(512,512);
5. imgQuantizedToDisplay = zeros(512,512);
6. n = 2; %Define bits para cuantización
7. figure();
8. imgQuantized = floor(imagen/(256/(2^n)-1)); %Cuantizar
9. imgQuantizedToDisplay = ((imgQuantized)*(256/2^n));
10. imshow(uint8(imgQuantizedToDisplay));
11. title(['Cuantización a ', num2str(n) ,' bits']);
12. n = 4; %Define bits para cuantización
13. figure();
14. imgQuantized = floor(imagen/(256/(2^n)-1)); %Cuantizar
15. imgQuantizedToDisplay = ((imgQuantized)*(256/2^n));
16. imshow(uint8(imgQuantizedToDisplay));
17. title(['Cuantización a ', num2str(n) ,' bits']);
18. n = 6; %Define bits para cuantización
19. figure();
20. imgQuantized = floor(imagen/(256/(2^n)-1)); %Cuantizar
21. imgQuantizedToDisplay = ((imgQuantized)*(256/2^n));
22. imshow(uint8(imgQuantizedToDisplay));
23. title(['Cuantización a ', num2str(n) ,' bits']);

 

Con n=2 bits podemos representar 2^n=2^2=4 niveles distintos de grises. Así mismo, con n=4 bits podemos representar 2^n=2^4= 16 niveles y con n=6 bits se representan 2^n=2^6=64 niveles en escala de grises.

El impacto de una revelación inesperada

¿A poco no cambian las cosas cuando en el momento menos esperado descubres de una u otra manera algo que por algún tiempo había vagado sin rumbo aparente por los pasillos del inconsciente? Siempre sucede de la misma manera. Al estar buscando  respuestas a los grandes enigmas universales, uno se encuentra en el mundo de las tinieblas ya que la claridad nunca llega en el momento indicado y más aún, siempre surgen dudas adicionales en el camino. Pero, también todo es diferente cuando en un solo instante las cosas parecen aclararse, no me refiero a resolver los enigmas, sino que a raíz de dicha epifanía uno cree comprender el porqué de las cosas, tampoco significa que tienes que estar de acuerdo con ellas…, pero así sucede, desgraciadamente .

Si tenemos una imagen en formato PGM, que según sus autores “está designado para ser extremadamente fácil de aprender”, ya que cada uno de los valores de los datos representa un pixel en escala de grises de 8 bits, no representa en mayor problema hacer un programa para obtener la imagen del archivo. Afortunadamente no es este el caso, en MATLAB leemos un archivo pgm de la siguiente manera:

imagen = imread('peppers.pgm','pgm');

Ahora, imagen es una variable que contiene una matriz de MxN pixeles, donde N y M dependen del tamaño de la imagen. A esto lo vemos como nuestra señal, y le aplicamos la Transformada de Fourier Discreta, pero al ser una imagen y como lo mencionaba antes, es una matriz de 2 dimensiones, lo que quiere decir que tenemos que realizar la transformada a través de los renglones y después de las columnas. El código que se presenta a continuación fue sacado de aquí, aunque lo modifique ligeramente para solamente pasarle los datos y calcular automáticamente el tiempo y las frecuencias a partir de esto, lo que realiza esta función es calcular la DFT a los datos de entrada:

1. function X=dft(x)
2. [sx1 sx2] =size(x); %Obtener el tamaño de la matriz
3. t = [0:sx2-1];     %Calcular la base de tiempo
4. f = [0:(1/sx2):(1-(1/sx2))];    %Calcular las frecuencias
5. t = t(:); % Formatear 't' en vector columna
6. x = x(:); % Formatear 'x' en vector columna
7. f = f(:); % Formatear 'f' en vector columna
8. W = exp(-2*pi*j * f*t');
9. X = W * double(x);

Código 1. Función que realiza la DFT en MATLAB

Las últimas dos líneas de código representan en esencia la transformada de fourier. Tengo que hacer referencia al post que escribí iniciando este tema, ya que no recuerdo de que fuente tomé la ecuación en el post anterior, pero noto que es diferente en cuanto X(k)  y x(n) está representadas como X(k+1) y x(n+1), creo que la diferencia radica en donde se tomen los coeficientes.

Ok, otra vez, la ecuación siguiente nos muestra la transformada de fourier discreta (Tomada de: Practical Digital Signal Processing for Engineers and Technicians, pp 63)

Ecuación 1

Ahora, viendo el programa relacionamos la línea 8 con lo siguiente:

   Ecuación 2

Podemos observar de la ecuación anterior que k es el equivalente a la líneas 3 y  n/N es la línea 4. Esto es, k es el ‘tiempo’ o mas bien dicho cada muestra en la imagen  y las frecuencias en las que contienen son n/N. (Si, esto me sigue causando problemas emocionales todavía). En la última línea del código anterior (la nueve) tenemos las muestras x(n) con los componentes de frecuencia (lo representado en la ecuación 2).

1. imagen = imread('peppers.pgm','pgm');
2. imfinfo('peppers.pgm')
3. figure(1); imshow(imagen);
4. [s1 s2]= size(imagen);
5. dftimagen = zeros(s1);
6. for i=1:s2
7.     dftimagen(i,:) = dft(imagen(i,:));
8. end
9. dftimagen= dftimagen.';
10. for i=1:s2
11.     dftimagen(i,:) = dft(dftimagen(i,:));
12. end
13. dftimagen = dftimagen.';
14. figure(2);imshow(uint8(ifft2(dftimagen)));

Código 2. Programa que realiza la DFT a una imagen de 8 bits escala de grises en MATLAB

De las líneas 1 a la 3 se lee la imagen y muestra en pantalla, en las líneas 4 y 5 se crea una nueva variable para almacenar el resultado de la transformada (este código tiene el inconveniente que da por hecho que es una matriz cuadrada).  Las líneas 6 a 8 realizan la DFT a cada renglón de la imagen, posteriormente se realiza una traspuesta (en la línea 9) a la imagen para realizar la DFT a lo largo de las columnas en las lineas 10 a 12 y se regresa con la traspuesta de la línea 13.

Por último, se toma la variable que tiene almacenada la imagen transformada y usando la transformada inversa que viene incluida en MATLAB se recupera la imagen original y se muestra en pantalla (línea 14) para verificar que se halla realizado correctamente la DFT.

Solo para terminar esta imagen en la que hice pruebas es una imagen de 512 x 512 pixeles y es bastante lento, no tengo los datos de cuanto se tarda, pero no se compara con la función que trae integrada MATLAB para realizar la FFT (no de en vano se llama Fast Fourier Transform, claro)

Isn’t ironic? Don’t you think?

Blogger, Windows Live Writer, Windows, y demás chinches no son amigables para escribir textos matemáticos o cómo la lógica del diseño del software e interfaz de usuario frustran cualquier intento de poner ideas claras en la red

Al empezar a escribir mis intentos de explicaciones, he estado de una manera u otra tratando de evitar el uso del editor de ecuaciones de Micro$oft, y recordando aquellos días en los que más de una vez me di de topes por no poder escribir una integral en alguna tarea o reporte, divagando sobre eso, me acordé de usar LaTEX (no, no tiene nada que ver con la planificación familiar o la prevención de ETS) para escribir ecuaciones matemáticas y en general texto con buen formato desde su redacción.

Haciendo uso de San Google, fui a parar con un par de herramientas para insertar código de LaTEX en blogger, pero oh sorprais, es un real dolor de cabeza el tratar de poner más de cinco ecuaciones, y más aún, una vez que las pusiste, se ven horribles, porque lo único que se hace es instalar un pequeño jscript en blogger y mediante un botón, conviertes el código de LaTEX en imágenes que quedan almacenadas en agún lugar del ciberespeis, así que no se integran naturalmente en el texto como en un documento .tex,  si no que se ven como imágenes sin ningun tipo de orden dentro del párrafo.

Si eso no es suficiente, lo tienes que hacer con Firefox y Greasemonkey en una de las opciones que encontré o simplemente con un pequeño código en HTML que la verdad en este momento no quiero ni explicar, así es que o te amarran a FF y GM (no es que sean malos pero a mi opinión Chrome está ganando terreno) o lo haces con HTML, lo cual se convierte en un problema al querer usar el Windows Live Writer, que no está del todo mal, de hecho es lo que he usado para redactar los posts, pero igual para darle formato a las ecuaciónes termina en un lío y también los convierte a imágenes, que en este caso ni siquiera se ponen en línea con el texto, si no que agrega un salto de línea antes y despues de la ecuación.

Y sólo para concluir, – así es corazón de mi vida, siempre has tenido razón, ‘inches ingenieretes no somos nada prácticos

PD. Cuando edité el post porque me equivoqué en algunas cosas en el título, me dí cuenta que desde blogger no podía editar el título del post debido a la longitud del texto, así que tuve que entrar al windows live writer para modificarlo (adivinaron, WLW todavía no tiene corrector ortográfico, ni falta que hace, jeje)…

The feared Discrete Fourier Transform (aka:DFT)

Why we should care about the Discrete Fourier Transform?

I will start talking about the applications in which DFT is used, as Gonzalez says in his image processing book, besides being the cornerstone in linear filtering, it offers considerable flexibility in the design and implementation of filtering solutions in areas as image compression, image restoration, image enhancement, and many other applications of practical interest. Now, we are ready to cheerfully start studying the DFT in deep. (Yeah, right)  

By definition, the DFT is represented as follows:

Mmmm, and as you easily can see from the equation above, :P, we have:

• X(k) = Is the Discrete Fourier Transform of our signal, is its representation in the frequency domain (what?)

• x(n) = Is our signal in the spatial domain, ie. an audio signal

So, if we see the equation, each sample X(k) will be the sum of the multiplication of all the input signal values by the frequency components of the signal.  Yes, is that e raised to two pi divided by N times minus i times k times n.

Without looking for more troubles with efficiency measurement algorithms, we can see (not so clearly) that while we have more samples in our signal, the amount of multiplications and additions is raised exponentially, that inconvenience was solved with the FFT, but that is something that I will not touch so far.

Here I stop with this little explanation of the DFT, but I will continue with an example of it coded in MATLAB in a later post.

(So far I can’t get to understand this)

I need the same thing that Fourier was smoking…

Definitely I don’t understand the Discrete Fourier Transform, and even more, the troubles are elevated to square when I try to comprehend it applied to an image, ha!

As Mr. Marley used to say…

Necesito lo que fumaba Fourier…

Definitivamente no alcanzo a comprender la Transformada de Fourier Discreta, y mis problemas se elevan al cuadrado cuando quiero comprenderla aplicada a una imagen, já!

Como el Sr. Marley solía decir…

La temible Transformada de Fourier Discreta (aka: DFT)

¿Por qué nos puede llegar a importar la transformada de Fourier Discreta?

Voy a empezar hablando de las aplicaciones dadas a la DFT, como lo dice Gonzalez en su libro de procesamiento de imagenes, aparte de ser la piedra angular en los filtros lineales, ofrece una considerable flexibilidad  en el diseño e implementación de soluciones de filtrado para compresión de imágenes, restauración de imágenes, mejora de imágenes, así como otras aplicaciones de igual interés. Ahora si, esto es suficiente para darnos ánimos y conocer la DFT a fondo. (Si, ajá)

Por definición, la DFT se representa de la siguiente manera:

Mmmm, y como se puede observar claramente en la ecuación anterior, (jeje, no!, ya en serio) tenemos que:

• X(k) = Es la transformada de fourier discreta de nuestra señal, es decir su representación en el dominio de la frecuencia.
• x(n) = Es nuestra señal en el dominio espacial, por ejemplo una señal de audio

Así es que si vemos detenidamente, cada muestra X(k) será la sumatoria de la multiplicación de todos los valores de la señal de entrada por los componentes de frecuencia de la señal. Si, es esa e elevada a la dos pi sobre N multiplicada por menos i multiplicada por k multiplicada por n.

Sin meternos en tanto rollo de medición de eficiencia de algoritmos podemos ver (tal vez no tan claramente) que mientras más muestras tenga nuestra señal, pues la cantidad de multiplicaciones y sumas se eleva exponencialmente, esto es un problema que se resolvió con la FFT, pero eso es harina de otro costal por ahorita.

Aquí le dejo con esta pequeña explicación de la DFT, pero continuaré con un ejemplo de ésta, codificada en MATLAB en un post futuro.

(Hasta ahorita sigo sin entenderle).

PD: Feliz cumpleaños Tris!!!

Begining

to Ivonne

Time to begin.

The objective of this blog is to share ideas, homework, articles, essays, events, links and any thing related to the development of my thesis in Master of Science in Electrical Engineering at the University of Juarez. This is meant to make available in a global manner the knowledge that could be generated at some point, and to create also a hub of discussion regarding topics related to digital image processing.

The main idea of the thesis is based on the Wavelet transform. The main purpose of a transform in the digital signal processing world, is to change in domain a signal, this is, represent in a “different” way a signal; with the objective of being able to see characteristics that would not be noticeable otherwise into the original domain. There are a bunch of transforms available; among them is the Fourier Transform, the Discrete Cosine Transform, the Wavelet, the Contourlet, etc.

Based on the fact that a domain transform an alternative approach can be achieved to the analysis of the signal, in comparison with the representation in the original domain. A characterization of images is pretended (based on the fact that an image is indeed a 2D signal) in the transformed domain, using in this particular case the Wavelet transform and be able to obtain in a systematic manner information that could be used in the different fields of digital image processing, like in the patter recognition as an example.

This blog is born due to the response of a personal need of clarify all the ideas that are brought in the way towards the making of the thesis project, perhaps the focus of this blog is oriented to the academic world, but it is obvious that can not be limited only to serve that purpose. I want to thank deeply to the love of my life, which always gives me her support and with out herself I would not never think about writing this Blog.

Inicio

A Ivonne

Cuando es tiempo de iniciar.

La creación este blog tiene como objetivo el compartir ideas, trabajos, tareas, artículos, eventos, links y cualquier cosa relacionada con el desarrollo de mi tesis para la Maestría en Ciencias en Ingeniería Eléctrica en la Universidad Autónoma de Ciudad Juárez. Esto, con la finalidad de hacer disponible de manera global el conocimiento que se pueda generar en algún momento y también crear un punto de discusión con los temas de interés relacionados con el procesamiento digital de imágenes.

La idea principal de la tesis se basa en la transformada Wavelet. La función principal de una transformada en el mundo del procesamiento de señales, es cambiar de dominio una señal, esto es, representar de manera “diferente” (para llamarle de alguna manera) una señal, para así poder observar características que en el dominio original son imperceptibles. Hay una buena cantidad de transformadas existentes, entre las cuales se encuentra la Transformada de Fourier, la de Coseno Discreta, la Wavelet, la Contourlet, etc.

Así es que basados en el hecho de que mediante una transformación de dominio se puede lograr un acercamiento alterno al análisis de una señal, comparado con la representación en el dominio original; se pretende hacer una caracterización de imágenes, (ya que una imagen es una señal en 2D) en el dominio transformado, usando en este caso una transformada Wavelet y llegar a obtener de manera sistemática información que pueda ser usada en los diferentes campos del procesamiento digital de imágenes, como por ejemplo el reconocimiento de patrones.

Este blog nace como respuesta a la necesidad de poner en claro las ideas que van saliendo en el camino de la realización del proyecto de tesis, aunque el enfoque de este blog es de carácter académico, claro que no puede ser limitado solamente a ello. Quiero agradecer infinitamente al amor de mi vida que me a apoya en absolutamente todo y sin su aliento no me hubiera animado siquiera a iniciar este Blog.