Reny

Trabajo Pr´ctico 2 a Compresi´n de Im´genes o a
Organizaci´n del Computador 2 o 2do. Cuatrimestre 2008

1.

Introduci´n te´rica o o

Los algoritmos usuales de compresi´n de datos e im´genes constan de tres etapas bien o a definidas: transformaci´n, cuantizaci´n y codificaci´n. La transformaci´n de los datos o o o o es un procedimiento gen´rico que se utiliza para representar la informaci´nen una forma e o alternativa y en la que, en principio, resulta m´s evidente la redundancia existente en los a datos originales. Es necesario que esta transformaci´n sea inversible, es decir, que a partir de o los datos transformados podamos recuperar exactamente la informaci´n original. La transforo maci´n de los datos puede ser de naturaleza muy distinta, o incluso, no resultar necesario si oexisten procedimientos eficientes para la compresi´n directa. o La compresi´n de datos puede ser con p´rdidas (lossy) o sin p´rdidas (lossless) en funo e e ci´n de si la informaci´n que se recupera coincide exactamente con la original o es s´lo una o o o aproximaci´n. Los m´todos de codificaci´n sin p´rdidas se utilizan sobre todo en aplicaciones o e o e de codificaci´n de datos binarios de aplicacionesinform´ticas en los que es absolutamente o a necesario recuperar la informaci´n original. Los formatos m´s populares son el ZIP y el ARJ. o a En procesamiento de im´genes los m´todos de compresi´n sin p´rdidas encuentran su aplia e o e caci´n en la codificaci´n de im´genes m´dicas o cient´ o o a e ıficas en las que puede resultar cr´ ıtico la p´rdida de parte de la informaci´n. Un ejemplo deformato de compresi´n de im´genes sin e o o a p´rdida de informaci´n es el PNG. e o La compresi´n con p´rdidas es la m´s habitual en la codificaci´n de se˜ales de v´ o e a o n ıdeo y audio. Evidentemente, las p´rdidas son tolerables siempre que la calidad de las se˜ales e n decodificadas sean aceptables. El principio general sobre el que se sustenta la codificaci´n con o p´rdidas es que no resultanecesario codificar aquellas componentes de la informaci´n que e o no son observables por los sistemas de percepci´n humana. Por lo tanto, estos m´todos se o e fundamentan en las caracter´ ısticas psicofisil´gicas de los sistemas auditivo y visual, que son, o en ultima instancia, los que deben evaluar la calidad del algoritmo de compresi´n. Por ello, ´ o es fundamental comprender las limitaciones ycaracter´ ısticas de estos sistemas de percepci´n o para dise˜ar codificadores en los que las p´rdidas de informaci´n resulten poco evidentes o n e o incluso inapreciables. La principal ventaja de estas estrategias de codificaci´n es que consiguen o unos factores de compresi´n muy superiores a los que se obtienen con los m´todos sin p´rdidas. o e e La p´rdida se produce en la etapa de cuantizaci´n. En ´stase reduce un intervalo de valores e o e a un s´lo valor que representa a todos los valores del intervalo. o Por ultimo, la etapa de codificaci´n consiste en establecer una correspondencia entre cada ´ o uno de los s´ ımbolos que componen los datos que deseamos comprimir y una secuencia de c´digos. Como la correspondencia entre los s´ o ımbolos y sus respectivos c´digos es un´ o ıvoca, esta 1estapa resulta tambi´n sin p´rdida de informaci´n. En el Trabajo Pr´ctico 1 presentamos la e e o a codificaci´n de Huffman. o

2.

Algoritmo de compresi´n o

JPEG es un formato muy utilizado para comprimir im´genes fotogr´ficas (donde hay una a a alta gama de colores). La compresi´n se logra a trav´s de la eliminaci´n de informaci´n o e o o redundante y/o irrelevante. Es un tipo de compresi´n conp´rdida. o e En el presente trabajo vamos a estudiar una simplificaci´n de este formato. Para eso o utilizaremos el siguiente algoritmo de compresi´n1 : o 1. Leer los datos de la imagen. 2. Separar los datos de la imagen en sus canales R, G y B. 3. Para cada canal: 4. Dividir la imagen en bloques (submatrices) de 8 × 8. 5. Para cada bloque: 6. Transformar el bloque. 7. Cuantizar el resultado de...