Compresión de Imágenes

Teoría de la Información y Métodos de Codificación
Tarea 6

Para la última tarea se nos pidió hacer un programa que lograra comprimir imágenes. Este programa no debería de usar funciones explícitas para compresión de imágenes, pero era posible usar paquetes para el manejo de las mismas, así como paquetes adicionales como el de Transformadas de Wavelet.

Ya que había estado usando un poco PyWavelets en otra tarea, me decidí por seguir usando esta herramienta para tratar con imágenes, y en este caso usar la transformada haar para comprimirlas.

Realicé un programa que toma como entrada una imagen en formato PNG, la cuál pasa por una función la cuál aplica las funciones necesarias para comprimirla, y esta es comprimida usando varios umbrales. El valor del umbral mientras más pequeño sea, la imagen no se comprimirá mucho, pero la calidad seguirá siendo casi la misma. Si el valor del umbral es grande, la imagen se logra comprimir mucho más, pero ésta pierde calidad.

Prueba 1

Primero tenemos la imagen original la cual se paso como parámetro desde la terminal. Esta imagen tiene un tamaño de 512x384 pixeles, y un tamaño de archivo de 104.5 KB.

Al ejecutar el programa se puede ir viendo el porcentaje de compresión por cada prueba con diferentes umbrales. AL final de la ejecución se muestra la gráfica de estos datos y se imprime el tiempo promedio de ejecución por cada prueba.

Podemos ver que el tiempo promedio para esta imagen fue de 0.4547. En la siguiente imagen podemos ver la gráfica del porcentaje de compresión logrado con el valor que se dio como umbral.

Mientras mayor sea el umbral, mayor la compresión de la imagen, pero este llega a un punto en el que la compresión ya no cambia tan drásticamente como al inicio.

En las siguientes dos imágenes se puede observar la imagen original en comparación con una de las imágenes resultantes con un umbral indicado en el nombre de la imagen que se ve en el título de la ventana. Abriendo la imagen en pantalla completa es posible notar la pérdida en la calidad de la imagen cuando el umbral aplicado fue mayor.

En la parte inferior de cada imagen es posible ver el tamaño en KBs de la imagen.

Prueba 2

Se realizó la misma prueba pero con una imagen de mayor tamaño en dimensiones y peso. Esta imagen es de 1024x769 pixeles con un tamaño de archivo de 234.7 KB.

Podemos observar que al ser una imagen de mayor resolución, se logro llegar a un porcentaje de compresión mayor que en la imagen anterior.

Y como es de esperarse el tiempo de ejecución aumento aproximadamente cuatro veces en relación con la prueba anterior.

En seguida tenemos también dos comparativas de la imagen original con una de las imágenes comprimidas con un cierto umbral.

Algo que se puede notar para imágenes de dimensiones como la anterior, es que la pérdida en la calidad de la imagen es menos notoria.

Código

El código completo es el siguiente. Esta incluido lo necesario para mostrar al final de la ejecución la gráfica de porcentaje contra valor de umbral.


APIs consultadas:
Discrete Wavelet Transform (DWT)
Python Imaging Library (PIL)

Referencias:
Gleb V. Tcheslavski, "Basic Image Compression Methods", 2008. [En línea]. Disponible en: http://ee.lamar.edu/gleb/dip/08-2%20-%20Image%20compression.pdf

Panrong Xiao, "Image Compression by Wavelet Transform", 2001. [En línea]. Disponible en: http://dc.etsu.edu/cgi/viewcontent.cgi?article=1108&context=etd

Corrección de Errores

Teoría de la Información y Métodos de Codificación
Tarea 5

Esta entrada trata de la corrección de errores de transmisión en un canal de comunicación, y particularmente la implementación del algoritmo para corrección de errores llamado Hamming(7, 4), que es un caso específico de los códigos Hamming.

Lo que se intenta hacer con estos códigos de bloques (en este caso bloques de bits), es transformar estos bloques por una cadena de bits un poco más larga, agregando los llamados bits de paridad, que son bits con los que luego es posible recuperarse de un error en la transmisión.

Cuando se transmiten bloques de bits por un canal de transmisión, se pueden presentar dos escenarios distintos. Primero, que el bloque de bits transmitido sea un código válido y no se tenga que hacer otra cosa más que decodificarlo y continuar con el siguiente bloque. Y segundo, que el bloque de bits no haya sido un código válido, y por lo tanto se tanga que recurrir a dos alternativas: (a) pedir al transmisor que vuelva a enviar el bloque, (b) poder recrear el bloque original mediante el código que se recibió.

Lo que nos interesa es conocer el algoritmo para lograr recrear el bloque original, a partir del bloque recibido con errores.

Como podemos ver en la siguiente imagen, nosotros definimos un tamaño de bloque de k bits, el cual entra a la función encargada de codificarla, para dar como resultado un bloque codificado, de n bits, donde n>k. Esto último es por que se habrán agregado los bits de paridad. Y para el caso en especifico que trataré, usamos bloques de 4 bits, que resultan en un código Hamming de 7 bits.

Para el caso de Hamming(7, 4), cuando existe un error en un bit, es posible recuperar el mensaje completo sin ninguna afectación. Y esto es porque cuanto menor sea la distancia entre bloques de código válidos, más difícil es recuperar lo que era la palabra clave correcta.

Este funciona haciendo uso de álgebra lineal simple, haciendo uso de matrices y multiplicaciones de matrices, lo que lo hace más eficiente que hacer uso de listas, ya que el consumo de memoria es menor, así como del procesamiento necesario.

Obtener el código Hamming es sencillo, solo es necesario multiplicar las matrices. Supongamos que tenemos un mensaje de 4 bits x = [1 1 0 1] y deseamos obtener su respectivo código Hamming, entonces hacemos lo siguiente.

$xG = \begin{bmatrix}{1}&&{1}&&{0}&&{1}\end{bmatrix} \begin{bmatrix} {1}&&{0}&&{0}&&{0}&&{0}&&{1}&&{1}\\ {0}&&{1}&&{0}&&{0}&&{1}&&{0}&&{1}\\ {0}&&{0}&&{1}&&{0}&&{1}&&{1}&&{0}\\ {0}&&{0}&&{0}&&{1}&&{1}&&{1}&&{1}\end{bmatrix}$

$xG = \begin{bmatrix}{1}&&{1}&&{0}&&{1}&&{0}&&{0}&&{1}\end{bmatrix}$

Este código de 7 bits es el que se transmite, y una vez recibido por el receptor, este verifica si es válido o no de la siguiente manera.

$Hy = \begin{bmatrix} {0}&&{0}&&{0}&&{1}&&{1}&&{1}&&{1}\\ {0}&&{1}&&{1}&&{0}&&{0}&&{1}&&{1}\\ {1}&&{0}&&{1}&&{0}&&{1}&&{0}&&{1}\end{bmatrix} \begin{bmatrix}{1}\\{1}\\{0}\\{1}\\{0}\\{0}\\{1}\end{bmatrix}$

$Hy = \begin{bmatrix}{0}\\{0}\\{0}\end{bmatrix}$

Cuando la suma de los elementos de esta última matriz no da cero, significa que existe un error. Supongamos que en vez de resultar ser Hy = [0; 0; 0] fuera Hy = [1; 0; 1], estos 3 bits se unen para formar un número binario el cual convertido a decimal sería 5, lo cual indicaría que el bit en la posición 5 es el que tiene el error, y lo que se hace es cambiar el 0 por un 1 o viceversa según sea el caso.

Código y pruebas

La prueba que realicé es sencilla, se trata de generar bloques de 4 bits para ser transmitidos, y comparo si lo que se mando se logró decodificar para obtener el original, y voy contando las veces que salió correcta la transmisión.

Referencias:
University of Wyoming, "Encoding and Decoding with the Hamming Code" [En línea]. [Fecha de consulta: 9 de Mayo, 2013].
Disponible en: http://www.uwyo.edu/moorhouse/courses/4600/encoding.pdf

Muhamad Asvial, "Channel coding, linear block codes, Hamming and cyclic codes" [En línea]. Fecha de consulta: 9 de Mayo, 2013].
Disponible en: http://staff.ui.ac.id/internal/132094574/material/KomDig_8.pdf

Diana Palsetia, "Error Detection and Correction", 2008 [En línea]. [Fecha de consulta: 9 de Mayo, 2013].
Disponible en: http://www.cis.upenn.edu/~palsetia/cit595s08/Lectures08/ErrorCD.pdf

Métodos de Diccionario: Byte Pair Encoding

Teoría de la Información y Métodos de Codificación
Puntos Extra

Veamos un ejemplo sencillo de compresión de información usando el método Byte Pair Encoding.

Codificación

La cadena de texto que voy a decodificar es la siguiente:

bbadefedbbafecedbbade

• La parte que más se repite en el texto es bba y la sustituimos por W.
  WdefedWfecedWde
• Luego tenemos cuatro posibles alternativas, sustituir ed, fe, Wde y edW ya que aparecen la misma cantidad de veces, pero como las últimas dos tienen más caracteres será mejor elegir uno de ellos. Cambiaré Wde por X.
  XfedWfecedX
• Y como ya no hay muchos elementos que se repiten cambiaremos fe por Y.
  XYdWYcedX

Nos resulta una tabla para decodificación como sigue.

W = bba
X = Wde
Y = fe

Y la cadena codificaca resulto así:
XYdWYcedX

Decodificación

Entonces si partimos de la tabla anterior, podemos recuperar la cadena original.

• De XYdWYcedX primero cambiamos las Y por fe.
  XfedWfecedX
• Ahora cambiamos las X por Wde.
  WdefedWfecedWde
• Y por último la W la cambiamos por bba.
  bbadefedbbafecedbbade

Y con esto logramos llegar a la cadena de texto original.

Referencias:
Byte Pair Encoding

Código Adaptativo

Teoría de la Información y Métodos de Codificación
Tarea 4

Para la entrega de esta tarea se nos pidió crear desde nuestras propias ideas el código adaptativo de la codificación Huffman, por lo tanto si estabas buscando una explicación del algoritmo de Huffman Adaptativo, este no es el mejor lugar ya que el método propuesto es de mi propia creación y no se asegura su funcionalidad.

Diseño del método adaptativo

Como idea para el método adaptativo pensé en algo muy simple, que seguramente en la evaluación de desempeño no logre mejorar al algoritmo simple de codificación Huffman. Lo que realicé fue crear un generador que recibe como entrada desde línea de comandos el parámetro del largo del texto que se irá generando carácter por carácter, y que se almacena en un buffer de un largo que también se define desde línea de comandos.

Lo que hace el programa es ir generando al momento el texto, que por el momento solo use los caracteres para letras minúsculas, y cuando el buffer llega al tamaño indicado, se crea un primer árbol de codificación, lo cual genera los códigos en binario necesarios para escribir los caracteres en menos de 8 bits. Después se libera este buffer y se espera a que se vuelva a llenar para volver a contar la frecuencia de cada carácter y poder generar un nuevo árbol que genere una codificación diferente.

Lo que sucede es que conforme se van generando los caracteres se genera un árbol completamente nuevo con los códigos actualizados, y después de un cierto tiempo el árbol llega a ser completo e incluir todos los caracteres incluidos, y el diccionario para codificar y decodificar empieza a cambiar menos drásticamente que al inicio.

Código

La siguiente imagen es una ejecución del programa donde como parámetros se le dio 500 para el largo del texto que ira creando y usando un buffer de 5 caracteres.

Se puede ver que no todos los caracteres cambiaron de codificación en las dos últimas creaciones del nuevo árbol.

Y en la siguiente imagen vemos que el archivo con 500 caracteres a comparación con el binario creado por el programa es 4 veces más pequeño, por lo que comprobamos que el código no es el indicado para comprimir archivos de texto.

Sugerencia para mejorar el método

El método propuesto no es el indicado para ahorrar espacio en memoria como su objetivo lo propone, porque en realidad ocupa más espacio el estar almacenando los nuevos diccionarios cada que se genera el nuevo árbol, además de que el proceso de decodificación resultaría algo más complicado.

La sugerencia de mejora es no crear un árbol nuevo cada vez que se llena el buffer sino actualizar el anterior, evitando modificar la codificación para un carácter cuando la frecuencia no incrementa mucho en comparación con la anterior tabla.

Codificación Huffman

Teoría de la Información y Métodos de Codificación
Tarea 3

La codificación Huffman es un algoritmo usado para compresión de datos.

El término se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como un carácter), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo.

El algoritmo consiste en la creación de un árbol binario que tiene cada uno de los símbolos en una hoja, y construido de tal forma que siguiéndolo desde la raíz a cada una de sus hojas se obtiene el código Huffman asociado.

Pasos:

1. Crear un nodo hoja para cada símbolo, asociando un peso según su frecuencia de aparición e insertarlo en la lista ordenada ascendentemente.
2. Mientras haya mas de un nodo en la lista:
   • Eliminar los dos nodos con menor probabilidad de la lista.
   • Crear un nuevo nodo interno que enlace a los nodos anteriores, asignándole como peso la suma de los pesos de los nodos hijos.
   • Insertar el nuevo nodo en la lista, (en el lugar que le corresponda según el peso).
3. El nodo que quede es el nodo raíz del árbol.

Con este árbol se puede conocer el código asociado a un símbolo, así como obtener el símbolo asociado a un determinado código.

Para obtener el código asociado a un símbolo se debe proceder del siguiente modo:

1. Comenzar con un código vacío.
2. Iniciar el recorrido del árbol en la hoja asociada al símbolo.
3. Comenzar un recorrido del árbol hacia arriba.
4. Cada vez que se suba un nivel, añadir al código la etiqueta de la rama que se ha recorrido.
5. Tras llegar a la raíz, invertir el código.
6. El resultado es el código Huffman deseado.

Un ejemplo de un árbol dibujado es el siguiente donde los nodos hijos finales son a los que les corresponde un símbolo y una frecuencia, y los nodos padres de estos últimos se conectan como pequeños árboles a otros nodos. Los nodos con puros números indican la suma de las frecuencias de los nodos hijos correspondientes.

Código

Pruebas con diferentes textos.

El algoritmo de Huffman aplicado sobre un alfabeto de únicamente dos símbolos distintos, asignará siempre un 1 al primero y un 0 al segundo, independientemente de la frecuencia de aparición de dichos símbolos. En este caso, de hecho uno de los peores casos, nunca se realiza compresión de los datos, mientras que otros algoritmos sí podrían conseguirlo.

Otra prueba de ejecución con un texto algo mas extenso que las anteriores.

Referencias:
Codificación Huffman
Ejemplo de Codificación Huffman Python dictionary

Karp-Rabin Algorithm

Information Theory and Coding Methods
Extra Assignment

The Karp-Rabin algorithm is a string searching algorithm created by Michael Rabin and Richard Karp in 1987 that uses hashing to find any one of a set of pattern strings in a text.

For text of length m and p patterns of combined length n, its average and best case running time is O(m+n), but its worst case time is O(mn).

Arithmetic replaces comparisons

Definition: For a test string $T$, let $T^n_{r}$ denote the n-length substring of $T$ starting at character r. Usually, n is known by context, and $T^n_{r}$ will be replaced by $T_{r}$.

Definition: For the binary pattern $P$, let
$$H(P) = \sum^{i=n}_{i=1} 2^{n-1}P(i)$$ Similarly, let
$$H(T_r) = \sum^{i=n}_{i=1} 2^{n-1}T(r+i-1)$$
That is, consider $P$ to be an n-bit binary number. Similarly, consider $T^n_{r}$ to be an n-bit binary number.

Theorem: There is an occurrence of $P$ staring at position $r$ of $T$ if and only if $H(P) = H(T_r)$.

Code

I implemented the Karp-Rabin algorithm using python. I try to strictly follow the mathematical method, but it some confusing because in the mathematical method we know that the index 1 of the substring is the first element of it, but thinking in how write code for this, we need to change some parts because normally the indexes of a string or list of elements start at 0, so as we can see in the code, some parts doesn't seems to be the same that the mathematical method, but it happens because I use the indexes starting at 0, like python do regularly.

In the first code I am using the definitions mentioned above only for get the result of $H(P)$ and $H(T_r)$. The program asks for the value of $r$ at the beginning and then calculate the result of both.

If the $r$ value is the start position of an occurrence in the complete string, we will get the same result in both definitions.

And the next code shows the complete implementation of the algorithm, where I calculate the hash for $H(P)$, then in the iteration I compare if $H(P)$ is equals to $H(T_r)$, if it is true, I add the index in a list, and at the end the matching positions of the substring in the complete string are printed.

References:
Algorithms on Strings, Trees, and Sequences, Dan Guesfiel, pp. 77-80
Rabin-Karp String Searching

Búsqueda de Cadenas

Teoría de la Información y Métodos de Codificación
Tarea 2

Boyer-Moore

Es un eficiente algoritmo de búsqueda de cadenas, y ha sido el punto de referencia estándar para la literatura de búsqueda de cadenas. Fue desarrollado por Bob Boyer y J. Strother Moore en 1977. El algoritmo preprocesa la cadena objetivo que está siendo buscada, pero no en la cadena en que se busca. El tiempo de ejecución del algoritmo Boyer-Moore, aunque es lineal en el tamaño de la cadena siendo buscada, puede tener un factor significativamente más bajo que muchos otros algoritmos de búsqueda ya que no necesita comprobar cada carácter de la cadena que es buscada, puesto que salta algunos de ellos. Generalmente el algoritmo es más rápido cuanto más grande es la clave que es buscada, usa la información conseguida desde un intento para descartar tantas posiciones del texto como sean posibles en donde la cadena no coincida. [1]

Knuth-Morris-Pratt

Es un algoritmo de búsqueda de cadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí, para determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca. El algoritmo originalmente fue elaborado por Donald Knuth y Vaughan Pratt y de modo independiente por James H. Morris en 1977, pero lo publicaron juntos los tres. [2]

Código

En el siguiente código pueden encontrar los tres algoritmos más conocidos para la búsqueda de cadenas, que son Naive, Boyer-Moore (BM) y Knuth-Morris-Pratt (KMP).

El programa recibe como parámetros el largo del patrón y el largo del texto, ya que he incluido también un generador para ello.

Análisis

Analíticamente se sabe que el algoritmo Boyer-More tiene en promedio un tiempo de ejecución de $$O(n \log(m/n))$$ en el mejor caso, pero en el peor caso se llega a tener $$O(m*n)$$ en cambio para el algoritmo Knuth-Morris-Pratt se tiene $$O(n + m)$$ lo que significa que es muy rápido.

En seguida las gráficas para los dos algoritmos donde el color de cada rectángulo es el tiempo promedio para encontrar los patrones de largo mencionado en el eje x, en un texto de largo mencionado en el eje y.

BM

KMP

Según interpreto los resultados, el algoritmo BM parece ser más rápido en tiempo de ejecución ya que mientras más tiende a ser oscuro el color, indica que el tiempo fue mucho menor.

Ahora veamos las gráficas para la cantidad de comparaciones hechas por cada algoritmo, esto lo hice ya que es evidente que el tiempo de ejecución no solo depende del algoritmo usado, sino que también esta involucrado el sistema operativo, y una forma más práctica de conocer su eficiencia, es contando la cantidad de comparaciones que se hace dentro del algoritmo.

BM

KMP

Aquí también podemos notar que BM realizó menos comparaciones que el KMP.

En conclusión podríamos decir que BM es ligeramente mejor que que KMP, y digo ligeramente por que a comparación con el algoritmo Naive, estos dos no tienen resultados muy distantes.

Por último para hablar de los algoritmos en términos de uso de memoria, tanto BM como KMP usan un arreglo de tamaño del largo del patrón, para almacenar los saltos debidos, y también los arreglos de tamaño n y m, donde n es el largo del texto, y m el largo del patrón, por lo que concluyo que en cuanto a memoria, los dos algoritmos prácticamente usan lo mismo.

Referencias:
[1] Knuth-Morris-Pratt
[2] Boyer-Moore
Boyer-Moore Exact Pattern Match
Algoritmo Boyer-Moore

Noisy Channel

Information Theory and Coding Methods
Assignment 1

I realized that plotting the length of the word against the transmission success rate, in all probability graphs using different frequency zeros, seem to be related to the same function, which I believe is exponential.

This is one of the graphics given.

In the next two graphics we can appreciate all the information given by the programs and script.

The next graphic is for word length versus frequency of zeros, and the color is given by the average percentage of correct transmitions, so yellow indicate high percentage of correct transmitions and black is practically a bad level.

And here we have the same but with the difference that the average is releated with the radius of the bubbles.

Código

For this assignment I write code in different languages, but I only run channel.sh in the terminal, and then channel.R inside the R console.

channel.py


channel.sh


channel.awk


channel.plot


channel.R


References:
Noisy channel by Elisa Schaeffer

Traducción

Teoría de la Información y Métodos de Codificación
Puntos Extra

Participe en la traducción del siguiente documento de C. E. Shannon:

A Mathematical Theory of Communication

En las páginas 32, 33, 34, 35, 46 y 47, que corresponden a los archivos ramon.tex y ramon2.tex del siguiente repositorio.

TraduccionShannonPaper