Ir al contenido

PGD | §2.5 – Métodos de compresión en la práctica

< §2.4 – Almacenamiento de una imagen digital

Los diferentes métodos de compresión pueden clasificarse en dos grandes grupos:

  • Métodos de compresión sin pérdida (lossless compression), en los cuales la información obtenida luego de la descompresión es idéntica a la original, es decir, son completamente reversibles. Estos métodos se aplican a cualquier tipo de archivo y son los se utilizan en las aplicaciones comerciales de compresión (por ejemplo WinZip© y WinRAR© en Windows™, StuffIt© en Macintosh™, etc);
  • Métodos de compresión con pérdida (lossy compression), donde parte de la información original se descarta para lograr una descripción de un tamaño aún menor, es decir, una mayor compresión. Esta técnica exige conocer el tipo de información que se comprime y requiere de un criterio que permita saber qué puede descartarse y qué no. En todos los casos se aplican a magnitudes que en última instancia serán percibidas por un ser humano (cuya discriminación no es perfecta) y que se desarrollan para un ámbito específico, por ejemplo imágenes, audio y video. Estos métodos son irreversibles, ya que no es posible obtener exactamente la información original (a menos, claro está, que se disponga de una copia anterior de la misma). Aún más: compresiones y descompresiones sucesivas pueden deteriorar de manera creciente esa información.

La bondad de un método de compresión se mide a través de cuánto es capaz de reducir la información a comprimir, y se expresa a través de un índice o factor de compresión (compression index, compression ratio) que se define como la relación k entre el peso de la información sin comprimir y el peso de la información comprimida:

Índice o factor de compresión:

k = (Peso de la información sin comprimir) / (Peso de la información comprimida)

En el caso de las imágenes, es posible utilizar cualquiera de estos métodos. Naturalmente, en el segundo caso es posible obtener índices de compresión mayores a expensas de una pérdida de calidad. Veamos unos pocos algoritmos comunes.

RLE (Run-length Encoding)

Este es un método simple, sencillo de implementar, sin pérdida, pero que no logra índices de compresión elevados. Literalmente significa codificación por longitud de corrida y se basa en detectar la ocurrencia de patrones repetitivos en los datos para luego describirlos de manera concisa. Es útil donde es muy probable la ocurrencia de tales repeticiones. Una de sus aplicaciones se encuentra en  la transmisión de datos por fax, ya que por su naturaleza (imagen tipo bitmap) es común la aparición de muchos bits que indican blanco (el papel) interrumpido ocasionalmente por otros que indican negro (el texto).

Para dar una idea, supongamos que la información que debemos comprimir fuera la siguiente secuencia de 20 bytes:

125 125 125 125 125 200 200 133 133 133 45 45 45 45 45 45 3 3 3 3.

Esta secuencia podría comprimirse en RLE mediante pares de números (longitud, dato) de esta manera:

5 125 2 200 3 133 6 45 4 3,

donde el primer número de cada par indica cuántas veces debe repetirse el otro. La misma secuencia quedó ahora descripta por otra de 10 bytes; hemos logrado así un índice de compresión, según nuestra definición anterior,  de 20 bytes / 10 bytes = 2, también expresado como 2:1.

En la práctica la compresión suele hacerse a nivel de bit en lugar de bytes, pero el principio es esencialmente el mismo.

LZW (Lempel-Ziv-Welch)

Este algoritmo sin pérdida está basado en un desarrollo previo de los científicos Abraham Lempel y Jacob Ziv quienes crearon el método LZ en 1978, el cual fue posteriormente mejorado por Terry Welch y publicado en 1984 como LZW. El método se basa en analizar y guardar patrones en una tabla a medida que se lee la información, para luego tratar de identificar ocurrencias de próximas secuencias con las ya analizadas, reemplazándolas por el índice que ocupan en la tabla. Si bien las nuevas secuencias que se agregan a la tabla hacen que ésta crezca de manera más o menos rápida, cada nueva entrada aumenta la chance de que poder identificar futuras secuencias y reemplazarlas por un índice.

Los índices de compresión alcanzables son mejores que RLE, pero no son óptimos debido a que la compresión se basa en la información leída hasta cierto punto del análisis y no en toda la información completa. No obstante, al momento de su publicación era el mejor algoritmo de uso general disponible, y ganó con ello una considerable popularidad.

El algoritmo es complejo, pero para dar alguna idea, digamos que LZW utiliza una tabla de 12 bits para guardar cada patrón que va encontrando en los datos. Antes de iniciarse la compresión, la tabla se llena con todas las secuencias posibles de 1 byte de longitud (es decir 256 entradas para datos de 8 bits); luego se agregan las de longitud 2 que se van encontrando en los datos, las de longitud 3 que pueden expresarse como combinación de secuencias ya encontradas de longitud 1 y 2, etc., hasta un máximo de 212 = 4096 entradas en total.

Deflate

Se trata de un algoritmo de compresión sin pérdida creado por el autor de un popular programa de compresión bajo DOS, denominado PKZip, que combina una versión temprana del método LZ de 1977 y un sistema de codificación Huffman. Luego del surgimiento de Windows, este programa dio origen a la conocida aplicación WinZip® de compresión de archivos. La especificación del formato ZIP es libre y gratuita.

La codificación Huffman es un método de asignar secuencias de pocos bits a los símbolos más frecuentes en un mensaje, dejando las secuencias más largas para los símbolos menos frecuentes, análogamente a la manera en que Morse creó su famoso código telegráfico, asignando a cada letra, número o carácter de puntuación una secuencias de puntos y rayas cuya longitud es tanto menor cuanto mayor sea su probabilidad de ocurrencia. Deflate utiliza este principio pero sobre secuencias de símbolos en lugar de símbolos individuales, reemplazándolos por un índice en la misma forma que la tabla de patrones de LZW. El método permite elegir el grado de compresión según el tiempo que se le permite al algoritmo buscar secuencias candidatas a ser reemplazadas por índices, en un balance entre velocidad y factor de compresión. Además, Deflate incorpora una etapa previa de análisis que reemplaza secuencias en otras equivalentes y de la misma longitud pero que pueden ser mejor comprimidas, de allí que en general logra factores de compresión algo mejores que LZW.

JPEG (Joint Photographic Expert Group)

Dentro de los métodos de compresión de imágenes, es por lejos el más difundido. Consiste en un mecanismo con pérdida, producto de un desarrollo conjunto de las organizaciones ISO e IEC (International Electrotechnical Comission) a través de un comité denominado Reunión del Grupo de Expertos en Fotografía (JPEG), quien definió y publicó el estándar en 1992.

Este algoritmo utiliza un método matemático conocido DCT (Discrete Cosine Transform, transformada discreta del coseno) que analiza la imagen por sectores, e intenta hallar en cada uno de ellos una descripción basada en ciertos patrones fijos establecidos de antemano, de complejidad creciente, para luego comprimir la imagen reduciendo la información necesaria (utilizar menos bits) para especificar los patrones más complejos, en los que el ojo humano tiene mayor dificultad en detectar. Es en este punto donde se introduce la pérdida, ya que el efecto de esta reducción es descartar detalle de la imagen; el nivel de reducción empleada al codificar esos patrones determinará la compresión resultante. Cada sector se analiza de manera independiente de los otros.

Para que el algoritmo resulte más eficiente, este análisis no se realiza sobre los canales RGB de la imagen. En su lugar se convierten estos canales en otros tres: uno de luminancia (equivalente a la versión en escala de gris de la imagen) y otros dos de crominancia (que contienen la información de color). Estos últimos se submuestrean, es decir, se reduce su resolución, generalmente a la mitad, ya que el ojo humano es menos sensible a las variaciones de color que a las de brillo. Luego de esta transformación se realiza el análisis anterior independientemente sobre cada uno de estos nuevos canales.

jpeg basisEl método es considerablemente más complejo que LZW, pues mientras este último opera sobre los patrones que se encuentran en los propios datos (dominio del espacio), JPEG trabaja sobre patrones presentes en la forma y la rapidez con que éstos cambian  (dominio de la frecuencia). El análisis no se realiza sobre toda la imagen a la vez, sino en pequeños mosaicos de 8 x 8 pixeles; en ellos se trata de describir la variación de intensidad en todo el mosaico como una combinación de 64 patrones diferentes (ver imagen lateral), que corresponden a otras tantas posibles variaciones continuas y simétricas de intensidad en ambas direcciones. Obsérvese que los patrones progresan de izquierda a derecha y de arriba a abajo en orden de complejidad (número de variaciones) creciente. Esta descomposición permite poner en evidencia cuando una imagen ha pasado por este tipo de compresión, ya que si se observa con suficiente detalle es fácil percibir un patrón de mosaicos de 8 pixeles de lado.

La esencia del método JPEG consiste en aplicar a cada canal obtenido según la descomposición anterior (uno de luminosidad y dos de crominancia submuestreados) el siguiente procedimiento:

  • Se divide la imagen en cuadrados de 8 x 8 pixeles. La transformación DCT asegura que, sin importar la distribución de intensidades en cada cuadrado, existe una combinación de los 64 patrones que lo dan como resultado; entonces:
  • Para cada cuadrado, se encuentran los porcentajes (en realidad coeficientes) con los que debe aplicarse cada uno de los 64 patrones para que el resultado sea igual al cuadrado dado;
  • En este punto reemplazamos 64 valores (las intensidades de cada pixel en el cuadrado de 8 x 8) por otros 64 (los coeficientes de los patrones). Hasta aquí no hay ganancia: el núcleo del método consiste en descartar los patrones de las variaciones más rápidas (los cercanos a la esquina inferior izquierda de la imagen anterior) que son los que menos inciden en el cuadrado bajo análisis;
  • Según cuántos coeficientes descartemos, habremos logrado más o menos compresión; el ajuste entre calidad y reducción de tamaño que los programas presentan al elegir JPEG incide en esta etapa;
  • Se genera una lista con todos los coeficientes no descartados de todos los cuadrados y se los comprime mediante un algoritmo sin pérdida.

Relación entre los métodos de compresión y los formatos de archivo

En general debemos separar el método de compresión, que es una operación de índole matemática, del formato de archivo o contenedor de la información comprimida. Por un lado, un archivo (de cualquier tipo) siempre puede ser comprimido mediante cualquier sistema de compresión de uso general (por ejemplo ZIP)[1]; sin embargo, ciertos formatos de archivo de imagen incluyen en su definición el uso (muchas veces opcional, aunque en algunos casos obligatorio) de uno o más algoritmos de compresión, disponibles al seleccionar ese formato al momento de guardar la imagen. En el siguiente capítulo veremos los formatos de archivo de imagen más comunes y los algoritmos de compresión incorporados que soportan.

§2.6 – Formatos de archivo para imágenes >

1 Tener en cuenta, sin embargo, que dado un algoritmo de compresión cualquiera, siempre existirá al menos un archivo particular que ese algoritmo no pueda comprimir; una discusión del tema puede hallarse en el artículo ¿Existe el compresor perfecto?.