Compresión de imágenes

Para esta tarea de compresión de imágenes he decidido implementar una combinación del algoritmo de Huffman con un método de reducción de colores.

Reducción de colores

Para reducir los colores lo que se realizo es por parámetros definir el "paso" de los colores, por ejemplo de 20, lo primero que se hizo fue agarrar todas las posiciones de los píxeles que tienen un valor de color de 0 a 19, entonces se busca el valor de color que es mas frecuente y ese es el que se usa en vez de todos los demás entonces en vez de utilizar por ejemplo 0, 1, 2 o 3 en color, si el color 2 es el más frecuente en la figura ese es el que voy a utilizar.
Cuando el paso es 20, en vez de tener una lista con 255 colores posibles se tiene una con 13.

Huffman

Codificar
Después se escribió un archivo binario, que contenía todos los códigos de los píxeles en el ejemplo anterior que mencioné se puede decir que solo había 13 códigos posibles ya que elegimos un paso de 20, entonces el árbol no estaba muy extenso, si no se hubiera hecho lo de la reducción de colores se hubieran tenido 255 códigos posibles lo cual no es algo satisfactorio. Este fue el objetivo de la reducción de colores que no se tuviera un árbol  muy extenso.

Decodificar
Y se leyó el archivo binario, y teniendo el árbol fue fácil descomprimir, se realizó igual que la tarea pasada, se fueron buscando los colores que estuvieran en el diccionario para ir pintando los colores.

Resultados:

Tabla de frecuencias

Porcentaje de compresión

Tiempo

Código:



Las imágenes decodificadas:

Original

 Paso 20

Paso 60

Original

Paso 60

Conclusiones

Se puede observar que se obtienen mejores resultados cuando se utilizan menos valores RGB sin embargo se pierde más calidad en la imagen, pero el método puede tener aplicaciones cuando lo que se necesita es que el archivo pese poco y no se requiere una muy calidad de la imagen. También que el tiempo baja conforme se aumenta el paso para codificar.

REED-SOLOMON CODES

Aplicaciones

Almacenamiento

CDs

Los CD están expuestos a muchos tipos de fallas, para que los datos se puedan leer correctamente es necesario utilizar un método de codificación que al guardar 0 y 1 los errores puedan ser recuperados y traducidos.
Una de las principales aplicaciones de codificación digital es el disco compacto de audio o CD. Los CDs utilizan una forma modificada del código Reed-Solomon llamado la Cruz Interleaved código Reed-Solomon, o CIRC.

El reproductor de CD utiliza Cross-Interleaved Reed-Solomon Coding. Comienza tomando las 24 palabras de 8 bits en la codificación en un (28,24) código RS. Con 4 símbolos de comprobación de paridad, 2 de corrección de errores. Los datos se intercalan, esto permite que los errores sobre una gran parte del disco se distribuyan en muchas pequeñas partes del disco. Esto permite más errores que deben corregirse y evita arruinar toda la información.

Utilizando esta codificación en los CDs de audio se puede corregir los errores de de hasta 3500 bits (2,4 mm) y se puede interpolar el error de hasta 12.000 bits (8,5 mm). Los avances en la tecnología en los últimos 20 años han dado lugar a más aplicaciones para la tecnología de CD, incluyendo DVD. La corrección de errores en un CD garantiza que la música de alta calidad se puede disfrutar de manera consistente y confiable.

Discos duros

Los discos duros modernos utilizan códigos CRC para detectar errores y códigos Reed-Solomon para corregir errores menores en la lectura de datos, y para recuperar datos de sectores que han "dañado" y almacenar los datos en los sectores de repuesto.
Ellos hacen posible que rascarse que se dale el disco y seguir disfrutando de los archivos guardados.

Wireless

Teléfonos celulares

También los teléfonos móviles requieren códigos de corrección de errores porque en la práctica casi todos los canales son ruidosos.
En general, los atacantes tratan de introducir algunos cambios en la imagen al destruir la marca de agua. Estos cambios afectarán la información incrustada y esto dará como resultado la extracción del número de teléfono equivocado de la imagen. Para proteger la propiedad de los derechos, el número de teléfono puede ser codificada en el código Reed-Solomon.

y aquí un pequeño experimento:

Satélites

En el espacio, el uno de los principales problemas de comunicación por satélite es la radiación, la radiación puede provocar que el contenido almacenado cambie de '0 'y '1', lo que hace que genera códigos de error. Por lo tanto, lo común es añadir diversos métodos de corrección de errores de codificación para el enlace de datos, por consiguiente en la codificación de corrección de errores ha habido un interés general de la investigación en las comunicaciones por satélite. Reed-Solomon tiene un funcionamiento más excelente.

El Reed Solomon codificador es un circuito en el que la división es compuesta de registros de desplazamiento, y tiene tres módulos:
multiplicadores en GF (2⁸), sumadores en GF (2⁸) y los registros de retardo de la unidad, como se muestra en la siguiente figura:

Digital television


Códigos Reed-Solomon se utilizan como parte de la estrategia orientada hacia el de corrección de errores de la tecnología digital la transmisión de señales en los cuatro sistemas de televisión de alta definición totalmente digitales propuestos.
En el medio terrestre en el entorno de la radiodifusión, a menudo hay errores aleatorios que resultan de diversas interferencias.
Se usan los códigos Reed-Solomon para los códigos de control de errores para la transmisión digital de televisión de alta definición

Como conclusión de lo que he investigado el RS sirve para recuperar de errores que se producen de manera muy común y seguido, y tiene la capacidad de reparar de manera rápida y óptima para poder seguir escuchando música, ver imágenes, u otras cosas que son más cotidianas de lo que pensamos.
Es una gran área de oportunidad ya que hay muchas variaciones del código para poder mejorarlo aún más.

Referencias

Leo Zheng. (2012). How NASA deals with packet loss when transmitting to Mars del sitio http://www.onsip.com/blog/2012/08/10/how-nasa-deals-with-packet-loss-when-transmitting-to-from-mars
Stan Hanley, (2002), Reed-Solomon Codes and CD Encoding del sitio http://www.usna.edu/Users/math/wdj/_files/documents/reed-sol.htm
Frequently Asked Questions About Compact Discs www.mscience.com/faq28.html
Reed-Solomon Codes http://www.4i2i.com/reed_solomon_codes.htm

Hamming

Para esta tarea yo decidí realizar el código Hamming(7,4)

En mi caso usaré (7, 4), que significa que codifica 4 bits de datos en 7 bits adicionando 3 bits de paridad. Este código Hamming permite corregir los errores de un bit o detectar todos los errores de un bit y dos bits.

Por ejemplo para codificar la siguiente matriz:



Entonces vamos a codificar una palabra "x" de 4 bits por ejemplo x = [1,0,1,1].
Para obtener el código de 7 bits se hace la multiplicación de G * x y se puede obtener el código correspondiente:

Tenemos que "1011" se codificó en "1011010", entonces podemos verificar que el código se ha enviado correctamente, Si se recibe una palabra y de la longitud 7, anticipamos primera comprobación para ver si y es una palabra en clave, si es así, se recupera el mensaje original como los primeros 4 bits de y. Para esto se utiliza H la matriz de 3 × 7 :



Para buscar los errores se multiplica la "y" transpuesta por la H, y se obtiene una matriz de 1x3, que si es 0 en todas las posiciones significa que no  hay error, si hay algún 1 ya hay un error.


Pero si en vez de transmitirse 1011010 se transmite por ejemplo 1111010 se obtiene lo siguiente que nos indica la posición donde hubo una falla y la podemos arreglar:

Para este experimento tome en cuenta tres factores:

• La probabilidad de fallo al enviar el bit, esto quiere decir que porcentaje tiene de probabilidad de que el bit se envíe de manera correcta y de manera incorrecta.
• El numero de replicas, es el numero de veces que se corre el experimento.
• La cantidad de bits que cambian en la palabra, es el número de bits que puede cambiar la palabra.

Replicas 10000

Bits que cambian 1

Probabilidad de fallo .3

Replicas 10000

Bits que cambian 2

Probabilidad de fallo .5

En la primera gráfica podemos ver que se corrigen más datos que los que no esto es porque se esta cambiando solo un bit y el algoritmo es muy bueno haciendo esto, y vemos que esta muy abajo lo de mandado sin errores y los que se mandan ta cual también representan gran parte de los datos ya que se estaba usando una probabilidad de 0.3.
En la segunda gráfica se puede ver que como se aumento la cantidad de bits que se cambian también afecto mucho en la corrección ya que ahora la mayoría se mandan con errores sin corregir, y muy pocos se logran recuperar totalmente, además de que se aumentó la probabilidad a 0.5.

El código que hace lo ya explicado es el siguiente:

Referencias

Elisa Schaeffer - Error correcting codes
Encoding and Decoding with the Hamming Code

Métodos de diccionario-Byte pair encoding

Este método consiste en encontrar el par de bytes que más se repita en la cadena y sustituirlo por otro carácter que no se este usando.

Compresión
El string que usaré es "cdabcaabfeedefeede"

• El que más se repite que podemos ver es el par "ee", entonces sustituimos este por X, lo qe nos da 
• cdabcaabfXdefXde
• X = ee
• Ahora el que más se repite es "de" y lo podemos sustituir con Y, 
• cdabcaabfXYfXY
• Y = de
• "XY" es ahora si el que más se repite y podemos sustituirlo con Z, de la siguiente manera:
• cdabcaabfZfZ
• Z = XY
• "fZ" es ahora el que más se repite y cambiamos "fZ" por M, lo que nos da:
• cdabcaabMM
• M = fZ
• El siguiente que hay que sustituir es "aa", lo podemos hacer con Q, y queda así:
• cdabcQbMM
• Q = aa
• Y por último se sustituye "MM" por algun otro que puede ser R:
• cdabcQbR
• R = MM

Lo que nos da como resultado de "cdabcaabfeedefeede" a "cdabcQbR" se redujo de 18 a 8 bytes.

Descompresión

Para esto se usa el diccionario que ya tenemos que es el siguiente:

• R = MM
• Q = aa
• M = fZ
• Z = XY
• Y = de
• X = ee
  
  
•  Comenzamos con "cdabcQbR" y se tiene que R = MM:
• cdabcQbMM
• Lo siguiente es sistituir la "Q" por "aa"
• cdabcaabMM
• Ahora la M por fZ:
• cdabcaabfZfZ
• Enseguida se sustituye la "Z" por "XY"
• cdabcaabfXYfXY
• Despues "Y" por "de"
• cdabcaabfXdefXde
• Y por ultimo "X" por "ee" y tenemos la cadena inicial:
• cdabcaabfeedefeede

 Referencias

Byte pair encoding (). . [ONLINE] Available at: http://www.csse.monash.edu.au/cluster/RJK/Compress/problem.html. [Last Accessed 25 de abril de 2013].

Huffman adaptativo

Codificación adaptativa

La manera en que hice mi algoritmo adaptativo fue ir pasando carácter por carácter al codificador, entonces de manera que el primer carácter que entrara tuviera la frecuencia 1, pero que la raíz  siempre tuviera dos hijos, el derecho y el izquierdo en donde el izquierdo es un nodo auxiliar que es el que va a ayudar a ir colocando los nuevos símbolos en el árbol  cuando se encuentra que se colocó en un nodo algunas frecuencias al revés  por ejemplo "casualmente aparecen al principio 10 letras "e" y  5 letras "a" " con eso el árbol piensa que e merece un código más pequeño, pero después empiezan a aparecer las letras "a" y entonces se modifican los nodos para que siempre se cumpla con esa regla.  Cada vez que entra un nuevo carácter se va modificando la tabla de frecuencia y con esto podemos acomodar los nuevos nodos.

Decodificación

Para la decodificación se fueron guardando cada una de las tablas de frecuencia, y así al igual que en la entrada pasada simplemente, se leyó el archivo con la entrada y se empezó a decodificar cada uno de estos con los caracteres que ya se tenían previamente. Se fue leyendo el árbol para así poder decodificar y escribir en otro archivo el texto decodificado.

Experimento

Caso típico.- Para el experimento se tomo un texto de 100000 (el mismo de la tarea pasada)caracteres de un libro en inglés para poder representar el caso típico.
Peor caso.- Se escogió con random.choice de una lista que contiene ascci, del mismo largo que el texto que se tomo de ejemplo.
Y con estos dos textos de prueba se hicieron las pruebas con las siguientes variaciones:

• Se cambió el largo que va agarrando, a lo que yo llamé "paso en el código", se fue cambiando de 10 en 10.
• Se tomaron 10000 pruebas para gráficar.

Obviamente la impresión de esto es casi imposible así que solo para mostrar como corre el programa aquí dejo una captura con muy pocos caracteres:

Y el árbol de manera gráfica de otro ejemplo muy simple:

Aquí aun aparecía más veces la "b"

Después apareció más veces la "a" y cambiaron las posiciones

Este es el código:



Y las gráficas generadas se ven así:

Se puede apreciar ligeramente que el caso típico hace menos tiempo que el peor caso

Con lo que podemos concluir que el algoritmo funciona  mejor cuando se empieza a pasar de más de 100 caracteres, además podemos comprobar también que funciona mejor para el caso típico en cuestión de tiempo y ratio que para el peor caso.

Además se puede ver que el algoritmo funciona bien cuando el archivo es grande pero la tasa de compresión alcanzable es desfavorable al comienzo de la codificación o para archivos pequeños.

Para mejorarlo se podría tener ya una lista de probabilidades estándar en el idioma que se usa para así poder ir acomodando los nodos mientras van llegando sabiendo cual es su frecuencia también establecer siempre que el paso de caracteres sea siempre el mínimo por default 100 por ejemplo para poder evitar que entren pocos caracteres y se hagan probabilidades erróneas.

Referencias

Elisa Schaeffer-Métodos adaptativos

Replacement via encoding scheme

Problema obtenido de la página 123 del libro "Introduction to Information Theory and Data Compression", D.R. Hankerson, Greg A. Harris, Peter D. Johnson.

Exercise 5.1.4. Find the compression ratio if the original file in the example in this section
is parsed using S = {0, 1}³ and encoded using the scheme.

• s₁=000→1111111
• s₂=001→1111110
• s₃=010→111110
• s₄=011→11110
• s₅=100→1110
• s₆=101→110
• s₇=110→10
• s₈=111→0

En el ejemplo en el libro viene el siguiente archivo orginal:

111110111111101110111101110110

Para el cual nosotros tenemos el siguiente esquema de codificación:

• s₁=0
• s₂=10
• s₃=110
• s₄=1110
• s₅=1111

Por lo cual podemos deducir que el archivo se puede pasar a la cadena s₅s₂s₅s₄s₄s₅s₁s₄s₃, entonces tenemos que el archivo original tiene 30 bits de largo.

Teniendo los bits de entrada podemos comenzar a sustituir a mano con el esquema propuesto por el ejercicio lo que quedaría algo así primero se toman los primeros tres bits que son "111" esto es equivalente a "0" y a el s₈, después los siguientes 3 bits que son "110" que son corresponde a "10" y a s₇ y así sucesivamente dando como resultado los bits:

010001101001101010, o también se puede respresentar como s₈s₇s₈s₈s₆s₇s₈s₆s₇s₇
Lo que nos da un archivo de salida de 18 bits, comparado con 30 del archivo original, lo que nos da un compression ratio de 5/3.

Para simular esto podemos hacer un pequeño programa en python, con un archivo de entrada que contenga los bits ya mostrados.
archivo.txt

Text compression

Program: Implement the tree-based Huffman coding for Unicode strings, implementing the tree structure yourself.

For this first part I implemented a binary tree to find the codes for each symbol.

1. The first thing that I did was to create a frequency table.
2. Then I put in pairs the lighter weights until the end of the list.
3. I searched the tree to find the codes for each leaf

I have done a web application to display the Huffman coding in a binary tree, this is the URL:

http://huffmandemo.appspot.com/

And here is the example:

After the decoding algorithm, I did take the text file that I wrote in binary, and I found the equivalent to the tree that I had already done.

This is the example in the terminal encoding and decoding:

Analyze an experiment to determine the worst-case and typical-case complexity and compression ratio


I use texts of 3000 words, for the worst case I have done texts with the same frequency and for the typical case I take random Internet texts

Here I show some plots that I got when I did the experiment:

compression ratio

The best case is when all the probabilities of the symbols change in powers of 2. And the worst is when all the probabilities are equal.

The complexity of the algorithm is O(nlog n). Since it has an internal loop with logn complexity and then repeated n times, where n is the set of symbols.


And this is the code:


References

Huffman compression

Huffman coding

Traducciones

Páginas 4-5 y 28-31.

String matching

Programa

• "Program: Implement both BM and KMP in Python"

He implementado dos algoritmos en Python para poder encontrar un patron de caracteres en una cadena.
El primero que hice es el de KMP, para comenzar a hacer este algoritmo lo primero que hay que hacer es una tabla de fallos, esta tabla consiste en no permitir que se examine T (el texto) más de una vez. Esto se puede hacer si se compara un fragmento de la cadena donde se busca con un fragmento de la cadena que se busca, y esto nos da un sitio potencial para que haya una nueva coincidencia.
Ejemplos de Textos y su tabla de fallo:

La palabra a buscar es ANA
La tabla de fallos es [-1, 0, 0]

La palabra a buscar es BCABCBABCABC
La tabla de fallos es [-1, 0, 0, 0, 1, 2, 1, 0, 1, 2, 3, 4]

Después en el algoritmo de KMP teniendo esta tabla cada ves que se examinan las cadenas entre si se usa la tabla de fallos para hacer saltos cuando se localiza un fallo.
Este es el algoritmo que implementé:


Algunas ejecuciones:

Después implemente el algoritmo de Boyer-Moore que el objetivo es el mismo pero lo hace de manera distinta primero procesa la cadena objetivo que esta siendo buscada, generalmente este algoritmo es más rápido mientras la cadena sea más grande.
El código con comentarios:


Este es un ejemplo:

• Design, document, and analyze an experiment to determine the worst-case time complexities of the two.
  

Para esta parte he creado palabras y textos de diferentes tamaños en python para poder analizar como se comporta el algoritmo, genero dos archivos uno que se llama bm.dat y otro que se llama kmp.dat, cada uno tiene en la primera columna la longitud del texto, el la segunda columna la longitud del patron y por último el tiempo de ejecución, este es el código:

Podemos ver que el algoritmo Boyer-Moore tiene un mejor tiempo cuando las cadenas son más largas, Boyer-Moore es más rápido ya que compara las palabras de derecha a izquierda, y tan pronto como se encuentra una carta en el texto que no está presente en el patrón de búsqueda se mueve, lugares m adelante, por lo que para archivos de gran tamaño, es de esperar que muchos de estos movimientos estarían allí por lo que una gran cantidad de caracteres de texto no será accesible ni una sola vez a diferencia de KMP donde se accede a cada letra al menos una vez.

Y en número de comparaciones se ve algo así:

Podemos notar que el Boyer-Moore es más eficiente que el KMP ya que hace mucho menor número de comparaciones. El promedio del KMP es de O(n+m). El algoritmo Boyer-More cuenta con un promedio de tiempo de ejecución de O(nlog(m/n)) (en el mejor caso), en el peor caso es de O(m*n).

Para los experimientos se hicieron 30 repeticiones.

Referencias

KMP
BM

Noisy channel

Python creates certain number words that come as a parameter, then sends the same word many times to see the probability of success or failure
Python:


In the shell script I do repetitions of words of a certain length, also i change the length of the word and the probability of 0 and 1, then in an awk script I can get the standard deviation and the averange, and send this data to the final file and process the data.

Shell script


In awk script I get the average and standard deviation
AWK script


With gnuplot I produce a graph to know what happened in the experiment.


And some plots that can help us to underestand the results.

q0 = 0.1
q1 = 0.1

 After I implemented more functions to analyze probabilities of 0 and 1 (q0, q1), and also compute the standard deviation.

While the length of the chain grows the probability of success is weakened and if the frequency of 0 is high but the probability of success to 0 It is not as high like the probability of 1 then while the frequencies of 0 going up so these will lose the success rate because In longer words are more failures.

Teoría de la información y métodos de codificación