Mostrar/Ocultar TOC

Tabla de Contenidos del Libro
Prefacio
Capítulo 1: Introducción
Capítulo 2: Fundamentos
Capítulo 3: Mapas de Bits
Capítulo 4: Archivos Vectoriales
Capítulo 5: Metaarchivos
Capítulo 6: Dependencias de Plataforma
Capítulo 7: Conversión de Formatos
Capítulo 8: Trabajando con Archivos Gráficos  
Capítulo 9: Compresión
Capítulo 10: Multimedia
Formato: Adobe Illustrator
Formato: Adobe Photoshop
Formato: Atari ST
Formato: AutoCAD DXF
Formato: Autodesk 3D Studio
Formato: BDF
Formato: BRL-CAD
Formato: BUFR
Formato: CALS Raster
Formato: CGM
Formato: CMU
Formato: DKB
Formato: Dore Raster
Formato: DPX
Formato: Dr. Halo
Formato: DVM Movie
Formato: PostScript Encapsulado
Formato: FaceSaver
Formato: FAX
Formato: FITS
Formato: FLI
Formato: GEM Raster
Formato: GEM VDI
Formato: GIF
Texto en Inglés del Capítulo 9
Imagen del CD-ROM de la 2° Edición
Imagen del CD-ROM de la 1° Edición (Torrent y HTTPS)
Versión Hipertexto del CD-ROM de la 2° Edición (En Inglés)
Versión Hipertexto del CD-ROM de la 2° Edición (En Ruso)

Capítulo 9 — Compresión de Datos

Capítulo 9 — Compresión de Datos

La compressión es el proceso usado para reducir el tamaño físico de un bloque de información. En gráficos de computadora, estamos interesados en reducir el tamaño de un bloque da datos gráficos para que podamos guardar más información en un espacio de almacenamiento físico dado. También podríamos usar la compresión para guardar imágenes más grandes en un bloque de memoria de un tamaño dado. Cuando examinas la especificación de un formato de archivo particular que el término codificación de datos se usa para referirse a algoritmos que efectúan compresión. La codificación de datos de hecho es un término más amplio que la compresión de datos. La compresión de datos es un tipo de codificación de datos, y una que se usa para reducir el tamaño de los datos. Otros tipos de codificación de datos están involucrados en la encriptación (criptografía) y la transmisión de los datos (por ejemplo, el código Morse).

Un compresor, naturalmente, efectúa compresión, y un descompresor recostruye los datos originales. Si bien esto puede parecer obvio, un descompresor puede operar solo usando el conocimiento del algoritmo de compresión usado para convertir los datos originales en su forma comprimida. Lo que esto significa en la práctica es que no hay manera en que puedas evitar tener que comprender los algoritmos de compresión en el mercado hoy en día si es que estás interesado en manipular archivos de datos. Como mínimo, necesitas conocimiento general de las bases conceptuales de los algoritmos.

Si lees un número de documentos de especificación, encontrarás que la mayoría de formatos incorporan algún tipo de método de compresión, sin importar cuán rudimentario sea. También encontrarás que solo hay unos pocos diferentes esquemas de compresión en uso común a través de la industria. Los más comunes de estos esquemas son variantes de los siguientes métodos, los cuales discutimos en las siguientes secciones.

Además, discutimos el empacado de pixeles, el cual no es un método de compresión en sí mismo (per se) sino una forma eficiente de almacenar datos en bytes contiguos de memoria.

La compresión de datos funciona de forma un tanto diferente para los tres tipos de datos gráficos: mapa de bits, vectorial, y metaarchivos. En los archivos de mapa de bits, solamente los datos de imagen son comprimidos usualmente; la cabecera y cualquier otro dato (mapa de color, pie, y así sucesivamente) siempre se dejan sin comprimir. Los datos sin comprimir conforman solo una pequeña porción de un archivo de mapa de bits típico.

Los archivos vectoriales normalmente no incorporan un método nativo de compresión de datos. Estos archivos almacenan una descripción matemática de una imagen en lugar de los datos de imagen en cuestión. Hay razones por las que los archivos vectoriales raramente están comprimidos:

Si un archivo vectorial está comprimido de cualquier forma, usualmente encontrarás que el archivo entero lo está, con todo y cabecera.

En los metaarchivos, los esquemas de compresión a menudo se parecen a los usados para comprimir archivos de mapa de bits, dependiendo del tipo de datos que los metaarchivos contienen.

Los programadores comúnmente confunden los algoritmos de compresión con los archivos en los que se usan. Muchos programadores les preguntan a los fabricantes en los grupos de noticias las especificaciones de los formatos de archivo CCITT o JPG. No existen semejantes especificaciones. Los algoritmos de compresión definen solamente cómo se codifican los datos, no cómo están almacenados en el disco. Para información detallada sobre cómo se almacenan los datos en disco, dale un vistazo a una especificación de formato de archivo de imagen en cuestión, tal como BMP o GIF, la cual definirá las cabeceras de archivo, orden de bytes, y otros problemas que no se cubren por las discusiones sobre los algoritmos de compresión. Formatos más complejos, tales como TIFF, puede que incorporen varios algoritmos de compresión diferentes.

La siguientes secciones introducen los términos usados en las discusiones sobre compresión de datos y cada uno de los tipos principales de algoritmos de compresión usados por los formatos de archivo gráfico hoy en día.



Terminología de Compresión de Datos

Esta sección describe los términos que encontrarás cuando leas sobre esquemas de compresión de datos en este capítulo y en las especificaciones de formatos de archivo gráficos.

El término datos decodificados y datos crudos (raw data) describen datos antes de haberse comprimido, y los términos datos codificados y datos comprimidos describen la misma información después de haberse comprimido.

El término tasa de compresión se usa para referirse a la tasa de datos descomprimidos a datos comprimidos. Así, una tasa de compresión de 10:1 se considera cinco veces más eficiente que una 2:1. Por supuesto, datos comprimidos usando un algoritmo que produce una compresión de 10:1 es cinco veces más pequeña que los mismos datos comprimidos usando un algoritmo que produce una compresión de 2:1. En la práctica, ya que solo los datos de imagen se comprimen normalmente, el análisis de las tasas de compresión ofrecidas por varios algoritmos debe tomar en cuenta los tamaños absolutos de los archivos probados.

Compresión Física y Lógica

Los algoritmos de compresión a menudo se describen como unos que exprimen, aplastan, trituran e implosionan datos, pero estas no son descripciones muy precisas de lo que realmente está pasando. Si bien el uso principal de la compresión es hacer que los datos usen menos espacio en disco, la compresión realmente no empaca físicamente los datos en un paquete de menor tamaño en ningún sentido significativo.

En lugar de eso, los algoritmos de compresión se usan para recodificar los datos en una representacióndiferente diferente y más compacta que transmite la misma información. En otras palabras, se usan menos palabras para transmitir el mismo significado, sin realmente decir la misma cosa.

La distinción entre los métodos de compresión física y lógica se hace en la base de cómo se comprimen los datos o, más precisamente, cómo se reordenan los datos en una forma más compacta. La compresión física se efectúa en datos exclusivos de la información que contienen; solamente traduce una serie de bits de un patrón a otro más compacto. Si bien los datos comprimidos resultantes pueden estar relacionados con los datos originales de una manera mecánica, la relación no será obvia para nosotros.

Los métodos de compresión física típicamente producen cadenas de ruido, al menos relativo al contenido de información de los datos originales. El bloque resultante de datos comprimidos normalmente es más pequeño que el original porque el algoritmo de compresión física ha eliminado la redunncia que existía en los datos en cuestión. La mayoría de los métodos de compresión discutidos en este capítulo son métodos físicos.

La compresión lógica se logra a través del proceso de sustitución lógica — es decir, reemplazar un símbolo alfabético, numérico o binario con otro. Cambiar "United States of America" a "USA" es un buen ejemplo de sustitución lógica, porque "USA" se deriva directamente de la información contenida en la cadena "United States of America" y retiene parte de su significado. De forma similar, el inglés "can't" no se puede sustituir lógicamente por "cannot". La compresión lógica solo funciona en los datos a nivel de caracteres o superior y se basa exclusivamente en información contenida dentro de los datos. La compresión lógica generalmente no se usa en la compresión de datos de imagen.

Compresión Simétrica y Asimétrica

Los algoritmos de compresión también pueden dividirse en dos categorías: simétricos y asimétricos. Un método de compresión simétrico usa aproximadamente los mismos algoritmos y efectúa la misma cantidad de trabajo, tanto para la compresión como para la descompresión. Por ejemplo, una aplicación de transmisión de datos en la que la compresión y la descompresión se hacen en tiempo real usualmente requiere un algoritmo simétrico para la máxima eficiencia.

Los métodos asimétricos requieren sustancialmente más trabajo para ir en una dirección que para ir en la otra. Usualmente, el paso de la compresión toma mucho más tiempo y recursos de sistema que el paso de descompresión. En el mundo real esto tiene sentido. Por ejemplo, si estamos haciendo una base de datos de imagen en la que una imagen será comprimida una vez para almacenarse, pero descomprimida muchas veces para ser vista, entonces probablemente podemos tolerar un tiempo de compresión mucho más largo que para la descompresión. Un algoritmo asimétrico que usa mucho tiempo de CPU para la compresión, pero que es rápido de decodificar, funcionaría bien en este caso

Los algoritmos que son asimétricos en la otra dirección son menos comunes pero tienen algunas aplicaciones. Al hacer copias de respaldo rutinarias, por ejemplo, esperamos totalmente que muchos de los archivos de respaldo nunca serán leídos. Un algoritmo de compresión rápido que es caro de descomprimir puede ser útil en este caso.

Codificación Adaptiva, Semi-Adaptiva y No Adaptiva

Ciertos codificadores basados en diccionario, tales como los algoritmos de compresión CCITT (ver la sección más adelante en este capítulo llamada "Codificación CCITT (Huffman)") están diseñados para comprimir solo tipos de datos específicos. Estos codificadores no adaptivos contienen un diccionario estático de cadenas predefinidas que se conoce que ocurren con alta frecuencia en los datos a ser codificados. Un codificador no adaptivo diseñado específicamente para comprimir el lenguaje Inglés contendría un diccionario con subcadenas predefinidas tales como "and", "but", "of", y "the", porque estas subcadenas aparecen con mucha frecuencia en el texto en Inglés.

Un codificador adaptivo, por otro lado, no tiene heurísticas preconcebidas sobre los datos que va a comprimir. Los compresores adaptivos, tales como LZW, logran independencia de datos al construir sus diccionarios completamente desde cero. Estos no tienen una lista predefinida de subcadenas estáticas sino que en su lugar construyen frases dinámicamente a medida que codifican.

La compresión adaptiva es capaz de ajustarse a cualquier tipo de entrada de datos y de devolver una salida usando la mejor tasa de compresión posible. Esto es en contraste a los compresores no adaptivos, los cuales son capaces de codificar eficientemente solo un tipo muy selecto de datos de entrada para los que están diseñados.

Una mezcla de estos dos métodos de codificacción de diccionario es el método de codificación semiadaptivo. Un codificador semiadaptivo efectúa una pasada inicial sobre los datos para construir el diccionario y una segunda pasada para efectuar la codificación en cuestión. Al usar este método, se construye un diccionario óptimo antes de que cualquier codificación tenga realmente lugar.

Compresión Lossy y Lossless

La mayoría de esquemas de compresión con los que tratamos en este capítulo son llamados lossless (sin pérdida). ¿Qué significa esto? Cuando una porción de datos se comprime y luego se descomprime, la información original contenida en los datos se preserva. No se ha perdido o descartado ningún dato; los datos no han sido alterados de ninguna manera.

Los métodos de compresión lossy (con pérdida), sin embargo, descartan una parte de los datos en la imagen a fin de lograr tasas de compresión mejores que las de la mayoría de métodos de compresión sin pérdida. Algunos métodos contienen elaborados algoritmos heurísticos que se ajustan a sí mismos para dar la mayor cantidad de compresión al tiempo que cambian tan poco de los detalles visibles como sea posible. Otros algoritmos menos elegantes pueden simplemente descartar una porción menos significativa de cada pixel, y, en términos de calidad de imagen, esperar lo mejor.

Los términos lossy o lossless a menudo se usan erróneamente para describir la calidad de una imagen comprimida. Algunas personas asum,en que si cualquier dato de imagen se pierde, esto solo podría degradar la imagen. La suposición es que nunca querríamos perder ningún detalle en absoluto. Esto ciertamente es verdad si nuestros datos consisten de texto o datos numéricos asociados con un archivo, tal como una hoja de cálculo o un capítulo de nuestra grandiosa novela Americana. En aplicaciones gráficas, sin embargo, bajo ciertas circunstancias, la pérdida de datos puede ser aceptable, e incluso recomendada.

En la práctica, un pequeño cambio en el valor de un pixel puede ser invisible, especialmente en imágenes de alta resolución en donde un pixel individual es apenas visible de todos modos. A las imágenes que contienen 256 o más colores pueden cambiársele valores selectivos de pixeles sin un efecto notable en la imagen.

En imágenes blanco y negro, sin embargo, obviamente no hay tal cosa como un pequeño cambio en el valor de un pixel: cada pixel solo puede ser blanco o negro. Incluso en imágenes blanco y negro, sin embargo, si el cambio simplemente mueve los límites entre una región negra y otra blanca en un pixel, el cambio puede ser difícil de ver y por lo tanto aceptable.

Como mencionamos en el Capítulo 2, Fundamentos de Gráficos de Computadora, el ojo humano está limitado en el número de colores que puede distinguir simultáneamente, particularmente si esos colores no están inmediatamente adyacentes en la imágen, o son definidamente contrastantes. Un algoritmo de compresión inteligente puede sacar ventaja de estas limitaciones, analizar una imagen sobre esta base, y lograr reducciones significativas al tamaño de los datos basándose en la remoción de la información de color que no es fácil de notar por la mayoría de gente.

En caso de que esto suene demasiado como magia, puedes estar seguro de que se ha hecho mucho esfuerzo para desarrollar los así llamados esquemas de compresión con pérdidas en años recientes, y muchos de estos algoritmos pueden lograr tasas de compresión sustanciales a la vez que retienen imágenes con buena calidad. Este es un campo de desarrollo activo, y es probable que veamos más desarrollos a medida que nuestro conocimiento del sistema humano de visión evolucione, y como resultado de que la aceptación de las imágenes lossy en los mercados comerciales relacionados tenga influencia de vuelta hasta la academia.

Para mayor información sobre la compresión lossy (con pérdida), mire la sección sobre JPEG más adelante en este capítulo.



Empacado de Pixeles

El empacado de pixeles no es tanto un método de compresión de datos ya que es una forma eficiente de almacenar datos en bytes contiguos de memoria. La mayoría de formatos de mapa de bits usan el empacado de pixeles para conservar la cantidad de memoria o espacio en disco requerida para almacenar un mapa de bits. Si estás trabajando con datos de imagen que contienen cuatro bits por pixel, puedes encontrar conveniente almacenar cada pixel en un byte de memoria, porque un byte típicamente es el área de memoria direccionable más pequeña en la mayoría de sistemas de computadora. Sin embargo deberías notar rápidamente que al usar este arreglo, la mitad de cada byte no se usa por los datos de pixel (mostrados en la Figura 9-1, a). Los datos de imagen que contienen 4096 pixeles de 4 bits requerirán 4096 bytes de memoria para almacenarse, la mitad de los cuales se desperdician.

Para almacenar memoria, podrías recurrir al empacado de pixeles: en lugar de almacenar un pixel de 4 bits por byte, podrías almacenar dos pixeles de 4 bits por byte (mostrado en la Figura 9-1, b). El tamaño de la memoria requerida para almacenar la imagen de 4096 pixeles de 4 bits disminuye de 4096 bytes a 2048 bytes, solo la mitad de la memoria que era requerida antes.

El empacado de pixeles puede parecer sentido común, pero este no está libre de un costo. El hardware de pantalla basado en memoria usualmente organiza los datos de imagen como un arreglo de bytes, cada uno de los cuales almacena un pixel o menos. En este caso, será de hecho más rápido almacenar solo un pixel de 4 bits por byte y leer estos datos directamente en la memoria en el formato apropiado en lugar de almacenar dos pixeles de 4 bits por byte, lo cual requiere enmascarar y desplazar cada byte de datos para extraer y escribir los valores de pixel apropiados. La compensación son tiempos de lectura y escritura más rápidos versus tamaño reducido del archivo de imagen. Este es un buen ejemplo de uno de los costos de la compresión de datos.

Figura 9-1: Empacado de pixeles
FIGURA 9-1: Empacado de pixeles

La compresión siempre tiene un costo. En este caso, el costo está en el tiempo que toma desempacar cada byte en dos pixeles de 4 bits. Otros factores pueden entrar en juego cuando se descomprimen los datos de imagen: los búferes necesitan ser reservados y manejados; las operaciones intensivas en uso de CPU deben ser ejecutadas y recibir servicio; se debe mantener actualizado el registro de scan lines. Si estás escribiendo un lector de archivo, usualmente no tienes opción; tú debes soportar todos los esquemas de compresión definidos en la especificación del formato. Si estás programando un escritor de archivos, sin embargo, siempre necesitas identificar los costos y compensaciones involucradas en la escritura de archivos comprimidos.

En un momento en la historia de la computación, no era necesaria ninguna decisión; el espacio en disco era escaso y caro, así que los archivos de imagen necesitaban estar comprimidos. Ahora, sin embargo, las cosas son diferentes. Los discos duros son relativamente baratos, y los medios de distribución y almacenamiento (los CD-ROM por ejemplo) lo son aún más. Ahora más y más aplicaciones escriben archivos de imagen descomprimidos por defecto. Tú necesitas examinar cuidadosamente el mercado de destino de tu aplicación antes de decidir si comprimir o no.



Codificación Run-Length (RLE)

Este es un algoritmo de compresión de datos que se soporta por la mayoría de formatos de mapa de bits, tales como TIFF, BMP y PCX. RLE es adecuado para comprimir cualquier tipo de datos sin importar los contenidos de su información, pero el contenido de los datos afectarán la tasa de compresión lograda por RLE. Si bien la mayoría de algoritmos RLE no pueden lograr las altas tasas de compresión de los métodos de compresión más avanzados, RLE es tanto fácil de implementar como rápido de ejecutar, haciéndolo una buena alternativa tanto de usar un algoritmo complejo de compresión como de dejar tus datos de imagen sin comprimir.

RLE trabaja al reducir el tamaño físico de una cadena de caracteres repetitiva. Esta cadena repetitiva, llamada una corrida, típicamente se codifica en dos bytes. El primer byte representa el número de caracteres en la corrida y es llamada la cuenta de la corrida. En la práctica, una corrida codificada puede contener de 1 a 128 o 256 caracteres; la cuenta de la corrida usualmente contiene el número de caracteres menos uno (un valor en el rango de 0 a 127 o 255). El segundo byte es el valor del carácter en la corrida, la cual está en el rango de 0 a 255, y es llamada el valor de la corrida.

Estando descomprimida, una corrida de caracteres de 15 caracteres A normalmente requeriría 15 bytes para almacenarse:

   AAAAAAAAAAAAAAA

La misma cadena después de la codificación RLE requeriría solo dos bytes:

   15A

El código 15A generado para representar la cadena de caracteres es llamada un paquete RLE. Aquí, el primer byte, 15, es la cuenta de la corrida y contiene el número de repeticiones. El segundo byte, A, es el valor de corrida y contiene el valor repetido en cuestión en la corrida.

Un nuevo paquete es generado cada vez que el carácter de la corrida cambia, o cada vez que el número de caracteres en la corrida excede la cuenta máxima. Asume que nuestra cadena de 15 caracteres ahora contiene cuatro corridas de caracteres diferentes:

   AAAAAAbbbXXXXXt

Usando la codificación run-length esto podría comprimirse en 4 paquetes de 2 bytes:

   6A3b5X1t

Así, después de la codificación run-length, la cadena de 15 bytes requeriría solo ocho bytes de datos para representar la cadena, a diferencia de los 15 bytes originales. En este caso, la codificación run-length produjo una tasa de compresión de casi 2 a 1.

Las corridas largas son raras en ciertos tipos de datos. Por ejemplo, texto plano ASCII (tal como el texto en las páginas de este libro) raramente contiene corridas largas. En el ejemplo anterior, la última corrida (que contiene el carácter t) tenía solo un carácter individual de longitud; una corrida de 1 carácter aún es una corrida. Se debe escribir tanto una cuenta de corrida y un valor de corrida para cada corrida de 2 caracteres. Codificar una corrida en RLE requiere un máximo de dos caracteres de información; por lo tanto, una corrida de caracteres individuales de hecho ocupa más espacio. Por las misma razones, los datos que consisten enteramente de corridas de 2 caracteres permanecen del mismo tamaño después de la codificación RLE.

En nuestro ejemplo, codificar el carácter individual al final como dos bytes no dañó notablementa nuestra tasa de compresión porque había muchas corridas largas de caracteres en el resto de los datos. Pero observa cómo la codificación RLE dobla el tamaño de la siguiente cadena de 14 caracteres:

   Xtmprsqzntwlfb

Después de la codificación RLE, esta cadena se convierte en:

   1X1t1m1p1r1s1q1z1n1t1w1l1f1b

Los esquemas RLE son simples y rápidos, pero su eficiencia de compresión depende del tipo de datos de imagen que se está codificando. Una imagen blanco y negro que es mayormente blanca, tal como la página de un libro, se codificará muy bien, debido a la gran cantidad de datos contiguos que son del mismo color. Una imagen con muchos colores que tiene una apariencia muy variada, sin embargo, tal como una fotografía, no se codificará muy bien. Esto es porque la complejidad de la imagen se expresa como un número grande de colores diferentes. Y a causa de esta complejidad habrá relativamente pocas corridas del mismo color.

Variantes de la Codificación Run-Length

Hay un número de variantes de la codificación run-length. Los datos de imagen normalmente se codifican con run-length en un proceso secuencial que trata los datos de imagen como un flujo unidimensional. en lugar de un mapa de datos bidimensional. En el procesamiento secuencial, un mapa de bits se codifica comenzando en la esquina superior izquierda y procediendo de izquierda a derecha a lo largo de cada scan line (el eje X) hasta la esquina inferior derecha del mapa de bits (mostrado en la figura 9-2, a). Pero se pueden escribir esquemas alternativos de RLE para codificar los datos por la longitud de un mapa de bits (el eje Y) a lo largo de las columnas (mostrado en la figura 9-2, b), para codificar un mapa de bits en azulejos bidimensionales (mostrado en la Figura 9-2, c), o incluso para codificar pixeles en una diagonal en un patrón de zig-zag (mostrado en la Figura 9-2, d). Variantes extrañas de RLE tal como esta última pueden usarse en aplicaciones altamente especializadas pero usualmente son muy raras.

Otra variante RLE raramente encontrada es un algoritmo de codificación run-length con pérdida (lossy). Los algoritmos RLE normalmente no tienen pérdida de datos en su operación. Sin embargo, descartar datos durante el proceso de codificación, usualmente al poner a cero uno o dos bits de menor peso en cada pixel, puede incrementar las tasas de compresión sin afectar adversamente la apariencia de imágenes muy complejas. Esta variante RLE funciona bien solo con imágenes del mundo real que contienen muchas variaciones sutiles en los valores de los pixeles.

Figura 9-2: Variantes de codificación run-length
FIGURA 9-2: Variantes de codificación run-length

Asegúrate de que tu codificador RLE siempre se detenga al final de cada scan line de datos de mapa de bits que se está codificando. Existen varios beneficios de hacerlo así. Codificar solo una simple scan line a la vez significa que solo se requiere un tamaño de búfer mínimo. Codificar solo una simple línea por vez también evita un problema conocido como cross-coding (codificación cruzada).

La codificación cruzada es la fusión de scan lines que ocurre cuando el proceso de codificación pierde la distinción entre los scan lines originales. Si los datos de los scan lines individuales se fusionan por el algoritmo RLE, el punto en donde un scan line terminaba y otro empezaba se pierde o, al menos, es muy difícil de detectar rápidamente.

La codificación cruzada a veces se hace, aunque nosotros aconsejamos contra esta. Esta puede ahorrarte unos pocos bytes extra de compresión de datos, pero complica el proceso de codificación, agregando costos de tiempo. Para los formatos de archivo de mapa de bits, esta técnica pierde el punto de organizar una imagen de mapa de bits por scan lines en primer lugar. Si bien muchas especificaciones de formatos de archivo explícitamente declaran que los scan lines deberían codificarse individualmente, muchas aplicaciones codifican los datos de imagen como un flujo continuo, ignorando los límites de scan lines.

¿Alguna vez has encontrado un archivo de imagen codificado con RLE que pudiera desplegarse usando una aplicación pero no otra? La codificación cruzada a menudo es la razón. Para estar seguro, las aplicaciones de decodificación y visualización deben tomar en cuenta la codificación cruzada y no asumir que una corrida codificada siempre se detendrá al final de un scan line.

Cuando un codificador está codificando una imagen, se coloca un final de scan line en los datos codificados para informarle al software de decodificación que el final del scan line se ha alcanzado. Este marcador es usualmente un paquete único, explícitamente definido en la especificación RLE, el cual no puede confundirse con ningún otro paquete de datos. Los marcadores de final de scan line usualmente tienen solo un byte de longitud, así que no contribuyen adversamente al tamaño de los datos codificados.

Codificar las líneas de scan line individualmente tiene ventajas cuando una aplicación necesita usar solo parte de una imagen. Digamos que una imagen contiene 512 scan lines, y necesitamos desplegar solo las líneas 100 a la 110. Si no supiéramos dónde comienzan y terminan los scan lines en los datos de imagen codificados, nuestra aplicación tendría que decodificar las líneas 1 a la 100 de la imagen antes de encontrar las diez líneas que necesitaba. Por supuesto, si las transiciones entre scan lines estuvieran marcadas con algún tipo de marcador delimitador fácilmente reconocible, la aplicación podría simlemente leer a través de los datos codificados, contando los marcadores hasta que llegara a las líneas que necesitaba. Pero este enfoque sería uno muy ineficiente.

Otra opción para localizar el punto inicial de cualquier línea particular en un scan line en un bloque de datos codificados es construir una tabla de scan lines. Una tabla de scan lines usualmente contiene un elemento para cada scan line en la imagen, y cada elemento contiene el valor de offset de su scan line correspondiente. Para encontrar el primer paquete RLE del scan line 10, todo lo que un decodificador necesita hacer es moverse a la posición del valor de offset almacenado en el décimo elemento de la tabla de lookup de scan lines. Una tabla de scan lines también podría contener el número de bytes usados para codificar cada scan line. Usando este método, para encontrar el primer paquete RLE del scan line 10, tu decodificador agregaría todos los valores de los primeros nueve elementos de la tabla de scan line. El primer paquete para el scan line 10 comenzaría en este offset de byte desde el inicio de los datos de imagen codificados con RLE.

Esquemas RLE de Nivel de Bits, Bytes y Pixeles

El flujo básico de todos los algoritmos RLE es el mismo, como se ilustra en la Figura 9-3.

Figura 9-3: Flujo de codificación del run-length básico
FIGURA 9-3: Flujo de codificación del run-length básico

Las partes que difieren del algoritmo run-length son las decisiones que se hacen basándose en el tipo de datos a decodificar (tales como la longitud de las corridas de datos). Los esquemas RLE usados para codificar gráficos de mapa de bits usualmente se dividen en clases por el tipo de elementos atómicos (es decir, los más fundamentales) que codifican. Las tres clases usadas por la mayoría de formatos de archivo gráficos son RLE a nivel de bits, bytes y pixeles.

Los esquemas de codificación RLE de nivel de bits codifican corridas de múltiples bits en un scan line e ignoran los límites de bytes y palabras. Solo las imágenes monocromáticas (blanco y negro) de 1 bit contienen un número suficiente de corridas de bits para hacer que esta clase de codificación RLE sea eficiente. Un esquema típico de nivel de bits codifica corridas de 1 a 128 bits de longitud en un paquete de un único byte. Los 7 bits de menor peso contienen la cuenta de la corrida menos uno, y el bit más significativo contiene el valor de la cuenta de bits, ya sea 0 o 1 (mostrado en la Figura 9-4, a). Una corrida mayor de 128 pixeles se parte entre varios paquetes codificados con RLE.

Los esquemas de codificación RLE de nivel de bytes codifican corridas de valores de bytes idénticos, ignorando límites de bits y palabras individuales dentro de un scan line. El esquema RLE de nivel de bytes más común codifica corridas de bytes en paquetes de 2 bytes. El primer byte contiene la cuenta de la corrida de 0 a 255, y el segundo byte contiene el valor de la corrida de bytes. También es común suplementar el esquema de codificación de 2 bytes con la habilidad de almacenar corridas de bytes literales sin codificar dentro del flujo de datos codificados también.

En dicho esquema, los siete bits de menor peso del primer byte mantienen la cuenta de la corrida menos 1, y el bit más significativo del primer byte es el indicador del tipo de corrida que sigue al byte de cuenta de la corrida (mostrado en la Figura 9-4, b). Si el bit más significativo está a 1, este denota una corrida codificada (mostrada en la Figura 9-4, c). Las corridas codificadas se decodifican al leer el valor de la corrida y repetirlo el número de veces indicadas en la cuenta de la corrida. Si el bit más significativo está a 0, se indica una corrida literal, lo que significa que los siguientes bytes de cuenta de corrida se leen literalmente desde los datos de imagen codificados (mostrado en la Figura 9-4, d). El byte de cuenta de la corrida entonces contiene un valor en el rango de 0 a 127 (la cuenta de la corrida menos uno). Los esquemas de RLE a nivel de bytes son buenos para datos de imagen que se almacenan como un byte por pixel.

Los esquemas RLE de nivel de pixeles se usan cuando dos o más bytes consecutivos de los datos de imagen se usan para almacenar valores de pixeles individuales. A nivel de pixeles, los bits se ignoran, y los bytes se cuentan solo para identificar cada valor de pixeles. Los tamaños de paquetes codificados varían dependiendo del tamaño de los valores de pixeles a codificar. El número de bits o bytes por pixel se almacena en la cabecera del archivo de imagen. Una corrida de datos de imagen almacenados como valores de pixel de 3 bytes se codifica como un paquete de 4 bytes, con un byte de cuenta de corrida seguido por tres bytes de valores de corrida (mostrado en la Figura 9-4, e). El método de codificación permanece igual que con el RLE orientado a bytes.

También es posible emplear una codificación literal de corrida de pixeles usando el bit más significativo de la cuenta de la corrida como en el esquema RLE de nivel de bytes. Recuerda que la cuenta de corrida en los esquemas RLE de nivel de pixeles son el número de pixeles y no el número de bytes en la corrida.

Más atrás en esta sección, examinamos una situación en la que la cadena "Xtmprsqzntwlfb" de hecho se duplicaba en tamaño cuando se comprimía usando un método RLE convencional. Cada corrida de 1 carácter en la cadena se convertía en 2 caracteres. ¿Cómo podemos evitar esta compresión negativa y todavía usar RLE?

Normalmente, un método RLE debe analizar de alguna manera el flujo de datos descomprimidos para determinar si debe usar o no una corrida literal de pixeles. Un flujo de datos necesitaría contener muchas corridas de 1 y 2 pixeles para hacer que usar una corrida literal sea eficiente al codificar todas las corridas en un único paquete. Sin emgargo, hay otro método que permite agregar corridas literales de pixeles a un flujo de datos codificados sin que estén encapsuladas en paquetes.

Considera un esquema RLE que use 3 bytes en lugar de 2, para representar una corrida (mostrada en la Figura 9-5). El primer byte es un valor de bandera que indica que los siguientes dos bytes son parte de un paquete codificado. El segundo byte es el valor de cuenta, y el tercer byte es el valor de la corrida. Cuando se está codificando, si se encuentra una corrida de 1, 2 o 3 bytes, los valores de los caracteres se escriben directamente al flujo de datos comprimidos. Ya que no se escriben caracteres adicionales, no se incurre en un gasto adicional.

Cuando se decodifica, se lee un carácter; si el carácter es un valor de bandera, la cuenta de corrida y los valores de corrida son leídos, expandidos, y la corrida resultante es escrita al flujo de datos. Si el carácter leído no es un valor de bandera, se escribe directamente al flujo de datos descomprimidos.

Hay dos desventajas potenciales con este método:

Figura 9-4: Esquemas RLE de nivel de bits, bytes y pixeles
FIGURA 9-4: Esquemas RLE de nivel de bits, bytes y pixeles

Figura 9-5: Esquema RLE con tres bytes
FIGURA 9-5: Esquema RLE con tres bytes

Paquetes de Replicación Vertical

Algunos esquemas RLE usan otros tipos de paquetes de codificación para aumentar la eficiencia de la compresión. Uno de los más útiles entre estos paquetes es el paquete de repetición de scan line, también conocido como el paquete de replicación vertical. Este paquete no almacena datos de scan line en cuestión; en su lugar, simplemente indica una cuenta del scan line anterior. Aquí está un ejemplo de cómo funciona esto.

Asume que tienes una imagen que contiene un scan line de 640 bytes de anchura y que todos los pixeles en el scan line tienen el mismo color. Esto requerirá 10 bytes para codificar la longitud de la corrida; asumiendo que pueden codificarse hasta 128 bytes por paquete y que cada paquete tiene dos bytes de tamaño. Asumamos también que las primeras 100 scan lines de esta imagen son del mismo color. Con 10 bytes por scan line, eso produciría 1000 bytes de datos codificados en run-length. Si en lugar de eso usáramos un paquete de replicación vertical que tuviera solo un byte de tamaño (prosiblemente un paquete run-length con una cuenta de corrida de 0) simplemente codificaríamos con run-length el primer scan line (10 bytes) y lo seguiríamos con 99 paquetes de replicación vertical (99 bytes). Los datos codificados con run-length resultantes entonces solo ocuparían 109 bytes.

Si el paquete de replicación vertical contiene un byte de cuenta del número de scan lines a repetir, solo necesitaríamos un paquete con un valor de cuenta de 99. Los 10 bytes resultantes de paquetes de datos de scan line y dos bytes de paquete de replicación vertical codificarían los primeros 100 scan lines de la imagen, que contienen 64,000 bytes, como solo 12 bytes — un ahorro considerable.

La Figura 9-6 ilustra los paquetes de replicación vertical de 1 y 2 bytes.

Figura 9-6: Esquema RLE con paquetes de replicación vertical de 1 y 2 bytes
FIGURA 9-6: Esquema RLE con paquetes de replicación vertical de 1 y 2 bytes

Desafortunadamente, las definiciones de los paquetes de replicación vertical son dependientes de la aplicación. Al menos dos formatos comunes, el de Metaarchivos Gráficos de WordPerfect (WPG) y GEM Raster (IMG), hacen uso de los paquetes de repetición de scan line para mejorar el desempeño de la compresión. WPG usa un esquema simple de paquete de 2 bytes, como lo describimos previamente. Si el primer byte de un paquete RLE es cero, entonces se trata de un paquete de replicación vertical. El siguiente byte que sigue indica el número de veces a repetir el scan line anterior.

El formato GEM Raster es más complicado. La secuencia de bytes, 00h 00h FFh, debe aparecer al inicio de un scan line codificado para indicar un paquete de replicación vertical. El byte que le sigue a esta secuencia es el número de veces a repetir el scan line anterior menos uno.

NOTA

Muchos de los conceptos que hemos cubierto en esta sección no se limitan a RLE. Todos los algoritmos de compresión de mapa de bits necesitan considerar los conceptos de la codificación cruzada, procesamiento secuencial, codificación de datos eficiente basada en los datos a codificar, y maneras de detectar y evitar la compresión negativa.




Para Mayor Información Sobre RLE

La mayoría de libros sobre compresión de datos tienen información sobre algoritmos de codificación run-length. Las siguientes referencias contienen información sobre RLE:

Held, Gilbert, Data Compression: Techniques and Applications, Hardware and Software Considerations, second edition, John Wiley & Sons, New York, NY, 1987.

Lynch, Thomas D., Data Compression Techniques and Applications, Lifetime Learning Publications, Belmont, CA, 1985.

Nelson, Mark R., The Data Compression Book, M&T Books, Redwood City, CA, 1991.

Storer, James A., Data Compression: Methods and Theory, Computer Science Press, Rockville, MD, 1988.




Compresión Lempel-Ziv-Welch (LZW)

Uno de los algoritmos más comúnmente usados en gráficos de computadora es el esquema de compresión Lempel-Ziv-Welch, o LZW. Este método sin pérdida (lossless) de compresión de datos se encuentra en varios formatos de imagen, tales como GIF y TIFF, y es también parte del estándar moderno de compresión V.42bis y de PostScript Nivel 2.

En 1977, Abraham Lempel y Jakob Ziv crearon el inicio de lo que ahora llamamos la familia LZ de compresores sustitucionales. Los algoritmos de compresión LZ77 se encuentran comúnmente en los programas de compresión y archivamiento de texto, tales como compress, zoo, lha, pkzip y arj. Los algoritmos de compresión LZ78 son usados más comúnmente para comprimir datos binarios, tales como mapas de bits.

En 1984, mientras trabajaba para Unisys, Terry Welch modificó el compresor LZ78 para la implementación en controladores de disco de alto desempeño. El resultado fue el algoritmo LZW que se encuentra comúnmente hoy.

LZW es un algoritmo general de compresión capaz de trabajar en casi cualquier tipo de datos. Generalmente es rápido tanto en comprimir como en descomprimir datos y no requiere el uso de operaciones de punto flotante. También, ya que LZW escribe datos comprimidos como bytes y no como palabras, la salida condificada con LZW puede ser idéntica tanto en sistemas Big Endian como Little Endian, aunque aún puede que encuentres problemas de orden de bits y de orden de rellenado. (Mira el Capítulo 6, Dependencias de Plataforma, para una discusión sobre dichos sistemas.)

A LZW se le refiere como un algoritmo sustitucional o algoritmo de codificación basado en diccionario. El algoritmo construye un diccionario de datos (también llamado una tabla de traducción o tabla de cadenas) de datos que ocurren en un flujo de datos comprimidos. Los patrones de datos (subcadenas) son identificados en el flujo de datos y son correspondidos con entradas en el diccionario. Si la cadena no está presente en el diccionario, se crea una frase de código basándose en el contenido de los datos de la subcadena, y esta se almacena en el diccionario. La frase es luego escrita al flujo de salida comprimida.

Cuando se identifica una recurrencia de una subcadena en los datos, la frase de la subcadena ya almacenada en el diccionario se escribe a la salida. Ya que el valor de la frase tiene un tamaño físico que es menor que la subcadena que representa, se logra la compresión de datos.

Decodificar los datos LZW es lo contrario de la codificación. El descompresor lee un código desde el flujo de datos comprimidos y agrega el código al diccionario de datos si todavía no está allí. El código se traduce luego a la cadena que representa y se escribe al flujo de salida sin comprimir.

LZW va más allá que la mayoría de compresores basados en diccionarios en el sentido de que no es necesario preservar el diccionario para decodificar el flujo de datos LZW. Esto puede ahorrar una buena cantidad de espacio cuando se almacenan los datos codificados con LZW. Cuando se comprimen archivos de texto, LZW inicializa las primeras 256 entradas del diccionario con el conjunto de caracteres ASCII de 8 bits (valores 00h hasta FFh) como frases. Estas frases representan todos los valores posibles de byte individual que pueden ocurrir en el flujo de datos, y todas las cadenas a su vez se construyen a partir de estas frases. Ya que tanto los codificadores y decodificadores LZW comienzan con diccionarios inicializados a estos valores, un decodificador no necesita tener el diccionario original y en su lugar construirá un diccionario duplicado a medida que decodifica.

TIFF, entre otros formatos de archivo, aplica el mismo método para los archivos gráficos. En TIFF, los datos de pixeles se empacan en bytes antes de presentarse a LZW, así que un byte fuente de LZW podría ser un valor de pixel, parte de un valor de pixel, o varios valores de pixel, dependiendo de la profundidad de bits de la imagen y el número de canales de color.

GIF requiere que cada símbolo de entrada LZW sea un valor de pixel. Ya que GIF permite imágenes con profundidades de bits desde 1 hasta 8 bits, hay entre 2 y 256 símbolos de entrada LZW en GIF, y el diccionario LZW se inicializa acorde a esto. La manera en la que los pixeles pudieron haberse empacado es irrelevante en el almacenamiento original; LZW los tratará como una secuencia de símbolos.

El enfoque de TIFF no funciona muy bien para pixeles con tamaño impar, porque empacar los pixeles en bytes crea secuencias de bytes que no se corresponden con las secuencias originales de pixeles, y cualquier patrón en los pixeles se oscurece. Si los límites de pixeles y de bytes encajan (por ejemplo, dos pixeles de 4 bits por byte, o un pixel de 16 bits cada dos bytes), entonces el método TIFF funciona bien.

El enfoque GIF funciona mejor para profundidades de bits de tamaño impar, pero es difícil extenderlo a más de ocho bits por pixel porque el diccionario LZW debe volverse muy grande para lograr una compresión útil en alfabetos de entrada grandes.

Remoción de Ruido y Diferenciación

LZW hace un muy buen trabajo al comprimir datos de imagen con una variedad grande de profundidades de pixeles. Las imágenes de 1, 8 y 24 bits se comprimen al menos tan bien como lo hacen usando esquemas de codificación RLE. Las imágenes ruidosas, sin embargo, pueden degradar significativamente la efectividad de la compresión LZW. Eliminar el ruido de una imagen, usualmente poniendo a cero uno o dos de los planos de bits menos significativos de la imagen, es recomendado para aumentar la eficiencia de la compresión. En otras palabras, si tus datos no se comprimen bien en su forma presente, transfórmalos a una forma diferente que comprima bien.

Un método que se usa para hacer que los datos sean más "compresibles" al reducir la cantidad de información extrana en una imagen, es llamado diferenciación (differencing). La idea es que datos no relacionados podrían convertirse fácilmente por una transformación invertible en una forma que pueda ser comprimida más eficientemente por un algoritmo de compresión. La diferenciación logra esto usando el hecho de que pixeles adyacentes en muchas imágenes de tono continuo varían solo ligeramente en valor. Si reemplazamos el valor de un pixel con la diferencia entre el pixel y el pixel adyacente, reduciremos la cantidad de información almacenada, sin perder ningún dato.

Con imágenes monocromáticas de 1 bit e imágenes de escala de grises de 8 bits, los valores de pixeles en cuestión son diferenciados. Los pixeles RGB deben diferenciar cada uno de sus canales de color de forma separada, en lugar del valor absoluto de la diferencia de los pixeles RGB (diferenciar rojo de rojo, verde de verde, y azul de azul).

La diferenciación se aplica usualmente en un plano horizontal a lo largo de scan lines. En el siguiente ejemplo de código, el algoritmo comienza en el último pixel del primer scan line de los datos de mapa de bits. La diferencia entre los dos pixeles en la línea se calcula, y el último pixel se pone a este valor. El algoritmo luego se mueve al siguiente al último pixel y continúa por el scan line y hacia abajo del mapa de bits hasta que termina, como se muestra en el siguiente pseudocódigo:

/* Diferenciar horizontalmente un mapa de bits */
for (Linea = 0; Linea < NumeroDeLineas; Linea++)
	for (Pixel = NumeroDePixelesPorLinea - 1; Pixel >= 1; Pixel--)
		Bitmap[Linea][Pixel] -= Bitmap[Linea][Pixel-1];

La diferenciación vertical y bidimensional podría también lograrse de la misma manera. El tipo de diferenciación usado tendrá efectividad variada dependiendo del contenido de la imagen. Y, sin importar el método usado, las imágenes diferenciadas se comprimen mucho más eficientemente usando LZW.

Variaciones del Algoritmo LZW

Múltiples variaciones del algoritmo LZW aumentan su eficiencia en algunas aplicaciones. Una variación común usa punteros de índices que varían en longitud, usualmente comenzando en 9 bits y creciendo hasta 12 o 13 bits. Cuando un puntero de índice de una longitud particular ha sido usada, otro bit se agrega para aumentar la precisión.

Otra variación popular en los compresores LZW involucra monitorear constantemente el proceso de compresión buscando cualquier caída en la eficiencia. Si se nota una caída, las frases menos usadas recientemente (Least Recently Used, o LRU) en el diccionario, se descartan para hacer lugar para nuevas frases, o el diccionario entero se descarta y se reconstruye.

La variante LZMW del método de compresión LZW construye frases al concatenar dos de ellas, en lugar de concatenar la frase actual y el siguiente dato de caracteres. Esto provoca una construcción más rápida de cadenas más largas con el costo de un diccionario de datos más complejo.

LZW es un algoritmo simple que es difícil de implementar eficientemente. Decidir cuándo descartar frases del diccionario e incluso cómo buscar en el diccionario de datos durante la codificación (usando un esquema basado en hash o árboles) es necesario para mejorar la eficiencia y la velocidad.

Las variaciones del algoritmo LZW estándar son más comunes de lo que un programador puede darse cuenta. Por ejemplo, los formatos TIFF y GIF usan las características estándar del algoritmo LZW, tales como un código de Despeje (Clear, que es la indicación para descartar la tabla de cadenas), el código EOF (fin del archivo), y un límite de 12 bits en el tamaño de los símbolos codificados. Sin embargo, GIF trata cada valor de pixel como un símbolo separado de entrada. Por lo tanto, el tamaño del alfabeto de entrada, el tamaño de inicio de símbolo comprimido, y el valor de los códigos Clear y EOF variará dependiend de la profundidad de pixeles de la imagen a comprimir.

GIF también almacena códigos comprimidos con el bit más significativo primero, sin importar el orden de bits nativo de la máquina en la que el algoritmo se implementa. Cuando aparecen dos códigos en el mismo byte, el primer código está en los bits de menor peso. Cuando un código cruza un límite de byte, sus bits menos significativos aparecen en los bytes más tempranos.

La variación LZW de TIFF siempre lee símbolos de entrada de 8 bits desde los datos descomprimidos sin importar la profundidad del pixel. Por lo tanto, ada símbolo puede contener un pixel, más de un pixel, o solo parte de un pixel, dependiendo de la profundidad de los pixeles en la imagen. TIFF siempre almacena los códigos comprimidos con el bit más significativo primero, lo contrario de GIF. (No confundas el indicador del orden de los bytes en la cabecera TIFF, o el valor de la etiqueta FillOrder, con el orden de los bits de los datos comprimidos con LZW. En un archivo TIFF, los datos comprimidos con LZW siempre se almacenan con el bit más significativo primero.)

El LZW de TIFF también contiene un poco de remiendos. Las longitudes de los códigos comprimidos necesitan incrementarse en un código tan pronto como sea realmente necesario. Por ejemplo, el compresor cambia de códigos de 9 bits a códigos de 10 bits después de agregar el código 511 a su tabla en lugar de esperar hasta que se agregue el código 512, desperdiciando así un bit.

Comprendemos que la explicación de esta práctica es que la implementación de LZW proporcionada por Aldus en la Revisión 5.0 del Kit de Herramientas del Desarrollador TIFF contenía este error, aunque la especificación TIFF 5.0 en cuestión especificaba el algoritmo LZW correctamente. Para el momento en el que el problema fue identificado (por Samm Leffler, el líder del Comité Asesor de TIFF), existían demasiadas aplicaciones que usaban la implementación equivocada, y no había manera de identificar los datos LZW incorrectamente codificados. La solución fue simplemente cambiar la especificación TIFF para que requiriera esta "variación" en el algoritmo TIFF, en lugar de cambiar el código, echar a perder todas las aplicaciones LZW de TIFF existentes, y considerar a todas las imágenes TIFF 5.0 LZW creadas anteriormente como incorrectas e inservibles.

Problemas Legales de LZW

En Diciembre 22 de 1994, CompuServe Information Service anunción que ha entrado en un acuerdo de licencia con Unisys Corporation para el uso del método de compresión/descompresión LZW en el formato de archivo GIF de CompuServe.

NOTA

Esta sección intenta proporcionar información que te ayudará a comprender las legalidades que puedas enfrentar cuando uses los algoritmos de compresión/descompresión LZW. Hemos usado la información más precisa a nuestra disposición al momento de imprimir. Sin embargo, no somos abogados ni somos empleados de Unisys. Por lo tanto, este texto no debería considerarse de ninguna manera como una publicación de Unisys Corporation, o como aprobada por Unisys, o de ninguna manera obligando a Unisys a entrar en un acuerdo de licencia basado en los términos, interpretaciones, y/o respuestas a las preguntas proporcionadas en este texto. Nota que Unisys aconseja que las políticas de licencia de Unisys han sido revisadas para reflejar cambios en el uso de LZW y las necesidades de sus licencias existentes y futuras.

CompuServe también anunció que todos los desarrolladores que creen o modifiquen tecnología de hardware o software que accediera la información de CompuServe Information Service y que usaran GIF deberían obtener un acuerdo de licencia directamente de CompuServe y pagar regalías por cada copia de su producto vendido. El acuerdo de CompuServe cubría solo el uso de GIF en CompuServe; ya que Unisys poseía la patente de LZW, Unisys afirmó que cualquier software que usara GIF estaba sujeto a licencia.

La comunidad de gráficos y online reaccionó con enojo y pánico. Ellos fueron engañados por CompuServe para asumir que el formato GIF había estado libremente disponible para su uso sin restricciones desde su invención en 1987. Ya para 1994, GIF había ascendido para reemplazar a PCX como el formato de archivo más usado para los gráficos de 8 bits de color. Todos los paquetes de edición y visualización gráfica, incluyendo navegadores online, soportaban el formato GIF. Y ahora, parecía que el formato GIF no estaba en el dominio público. ¿Qué estaba pasando?

CompuServa explicó que habían sido abordados por Unisys Corporation, la cual poseía la patente del algoritmo de compresión/descompresión LZW. Aparentemente, CompuServe no había hecho su tarea cuando incluyó los algoritmos patentados LZW en el formato de archivo GIF. El resultado fue que CompuServe tuvo que tomar una licencia de parte de Unisys para el uso de LZW en los GIF. CompuServe decidió extender un requerimiento de licencia a cualquiera que hubiera desarrollado cualquier producto que usara GIF que interfaceara a las redes de CompuServe. Todo el dinero recolectado por CompuServe esencialmente iría para pagar la propia licencia del acuerdo de CompuServe con Unisys. Parecía como si CompuServe estuviera pidiéndole a los desarrolladores de software para GIF que pagaran la licencia de Unisys que CompuServe tenía que tomar a causa de su falla en verificar si GIF estaba libre de responsabilidades de patentes.

Algunas personas tenían sospechas sobre el tiempo que tomó el anuncio de CompuServe. Por muchos años se supo en la comunidad de programadores que GIF usaba LZW y que LZW estaba patentado por Unisys. Aún así CompuServe continuó promoviendo el uso de los GIF. Unisys afirmó que la compañía solo recientemente había descubierto que los GIF usaban LZW. También era un hecho que la industria de la WWW estaba explotando y que los GIF eran un medio integral de intercambio para transferir gráficos de baja resolución a través de Internet.

Después de que el humo se disipó, la patente LZW de Unisys y los acuerdos de licencia se mantuvieron rápido. Unisys suavizó la carga de los desarrolladores de GIF al reducir sustancialmente las cuotas de la licencia que cambió antes de 1995, ofreciendo así cuotas de licencia muy razonables. Además, Unisys anunció que no buscaría cuotas de licencia por una infracción inadvertida por productos de software GIF entregados antes de 1995. (Sin embargo, se requieren licencias de actualizaciones entregadas después de 1995.)

La gente se dio cuenta, luego de un examen más minucioso, que no era ilegar poseer, transmitir, o recibir archivos GIF (siempre y cuando no ocurriera compresión y/o descompresión sin licencia de los archivos). Era, de hecho, la implementación del algoritmo LZW el que estaba bajo restricción de licencia. Sin embargo, ya que cada archivo GIF contiene datos codificados con LZW, esto no hizo sentir mucho mejor a la gente. Muchos desarrolladores renunciaron a usar GIF, mientras que todavía otros iniciaron proyectos base dirigidos a desarrollar un formato de archivo para un día reemplazar a los GIF. Sin embago, el uso amplio de los GIF permanece y no es probable que desaparezca en algún momento cercano, si es que acaso sucede alguna vez.

Un Poco de Historia

Para comprender mejor lo que el acuerdo de licencia LZW de Unisys puede significar para ti, primero volvamos un poco más atrás en la historia.

Desde 1990, cientos de compañías han entrado en acuerdos de licencia LZW con Unisys.

Para Mayor Información Sobre LZW

Muchos libros sobre compresión de datos contienen información sobre los algoritmos de compresión LZ y LZW. La primer referencia a continuación es la fuente definitiva para una explicación muy general sobre el algoritmo LZW en sí y no se enfoca específicamente en datos de imagen de mapa de bits.

Welch, T. A., "A Technique for High Performance Data Compression," IEEE Computer, vol. 17, no. 6, June 1984.

La especificación TIFF (tanto las revisiones 5.0 y 6.0), contienen una explicación de la variación TIFF de la compresión LZW. Refiérete a la sección "Para Mayor Información" del artículo de TIFF para más información y mira el CD-ROM para la especificación misma.

Los siguientes artículos y manuscritos también están específicamente relacionados a LZW:

Bell, Timothy C., "Better OPM/L Text Compression," IEEE Transactions on Communications, vol. 34, no. 12, December 1986, 1176-1182.

Bernstein, Daniel J., Y coding, Draft 4b, March 19, 1991, parte del manuscrito del paquete de Codificación Yabba Y Coding.

Blackstock, Steve, LZW and GIF Explained, manuscrito en el dominio público, 1987.

Montgomery, Bob, LZW Compression Used to Encode/Decode a GIF File, manuscrito en el dominio público, 1988.

Nelson, Mark R., "LZW Data Compression," Dr. Dobbs Journal, October 1989, pp. 29-36.

Phillips, Dwayne, "LZW Data Compression," The Computer Applications Journal, Circuit Cellar Ink, vol. 27, June/July 1992, pp. 36-48.

Rodriguez, Karen, "Graphics file format patent Unisys seeks royalties from GIF developers," InfoWorld, vol. 17, January 9, 1995, p. 3.

Thomborson, Clark, "The V.42bis standard for data-compressing modems," IEEE Micro, October 1992, pp. 41-53.

Ziv, J., and A. Lempel, "A Universal Algorithm for Sequential Data Compression," IEEE Transactions on Information Theory, vol. 23, no. 3, 1977, pp. 337-343.

Ziv, J., and A. Lempel, "Compression of Individual Sequences via Variable-Rate Coding," IEEE Transactions on Information Theory, vol. 24, no. 5, September 1978.

Puedes obtener información adicional sobre LZW, y aprender sobre la licencia LZW, contactando a Unisys:

Welch Patent Licensing Department
Unisys Corporation
Mail Stop C1SW19
P.O. Box 500
Blue Bell, PA 19424 USA
FAX: 215-986-3090
Email: lzw_info@unisys.com

Información general de licencia puede obtenerse también de la página de inicio del servidor web de Unisys:

   http://www.unisys.com

En particular, mira:

   http://www.unisys.com/LeadStory/lzwterms.html
   http://www.unisys.com/LeadStory/lzwfaq.html

Los grupos de noticias comp.graphics.misc y comp.compression de USENET contienen discusiones frecuentes de los problemas técnicos de LZW y algunas discusiones de los problemas de patentes. El grupo de noticias oficial en donde tiene lugar mucha discusión es alt.gif-agreement. Puede que también encuentres información en los grupos de noticias misc.legal.computing, misc.legal.int-property y comp.patents.

Asegúrate de verificar las FAQs de compresión y formatos de archivo gráficos también. Ambas contienen una cantidad sustancial de información sobre LZW y los problemas de patentes.

Puedes obtener una copia de la patente LZW en cuestión desde la Oficina de Patentes de Estados Unidos. La patente también está disponible en muchos sitios de Internet, incluyendo:

   ftp://cs.columbia.edu/archives/mirror2/world-info/obi/USPatents/lzw-patent.gz
   ftp://ftp.std.com/obi/USPatents/lzw-patent.Z
   ftp://ftp.uu.net/doc/literary/obi/USPatents/lzw-patent.Z
   ftp://gatekeeper.dec.com/.8/misc/lzw-patent.Z




Codificación CCITT (Huffman)

Muchos formatos de archivo de imagen para facsímile y documentos soportan una forma de compresión de datos sin pérdida a menudo descrita como la codificación CCITT. El CCITT (International Telegraph and Telephone Consultative Committee) es una organización de estándares que ha desarrollado una serie de protocolos de comunicación para la transmisión de facsímil de imágenes en blanco y negro sobre líneas de teléfono y redes de datos. Estos protocolos se conocen oficialmente como los etándares CCITT T.4 y T.6 pero son referidos más comúnmente como compresión CCITT Grupo 3 y Grupo 4, respectivamente.

A veces la codificación CCITT se refiere como codificación Huffman, algo no del todo preciso. La codificación Huffman es un algoritmo de compresión simple introducido por David Huffman en 1952. La codificación CCITT unidimensional, descrita en una subsección a continuación, es un tipo específico de codificación Huffman. Los otros tipos de codificaciones CCITT sin embargo, no son implementaciones del esquema Huffman.

Las codificaciones Grupo 3 y Grupo 4 son algoritmos de compresión que están diseñados específicamente para codificar datos de imagen de 1 bit. Muchos formatos de archivo de documentos y FAX soportan la compresión Grupo 3, y varios, incluyendo TIFF, también soportan el Grupo 4.

La codificación Grupo 3 fue diseñada específicamente para telecomunicaciones de datos de imágenes blanco y negro de nivel de bits. Todas las máquinas modernas de FAX y los FAX módems soportan la transmisión de facsímil del Grupo 3. La codificación y decodificación del Grupo 3 es rápida, mantiene una buena tasa de compresión para un amplio rango de datos de documentos, y contiene información que ayuda a un decodificador de Grupo 3 a detectar y corregir errores sin hardware específico.

El Grupo 4 es una forma más eficiente de compresión de nivel de bits que ha reemplazado casi totalmente el uso del Grupo 3 en muchos sistemas de almacenamiento convencionales de imágenes de documentos. (Una excepción son los sistemas de almacenamiento de documentos de facsímil en donde a las imágenes originales del Grupo 3 se les requiere estar almacenadas en un estado inalterado.)

Los datos codificados con Grupo 4 tienen aproximadamente la mitad del tamaño que los datos unidimensionales codificados con Grupo 3. Si bien el Grupo 4 es bastante difícil de implementar eficientemente, es más rápido. Además, el Grupo 4 fue diseñado para usarse en redes de datos, así que no contiene los códigos de sincronización usados para la detección de errores para el Grupo 3, haciéndolo una pobre elección para un protocolo de transferencia de imágenes.

El Grupo 4 a veces se confunde con el método de compresión IBM MMR (Modified Modified READ). De hecho, el Grupo 4 y MMR son casi exactamente el mismo algoritmo y logran resultados de compresión casi idénticos. IBM publicó el MMR en 1979 con la introducción de su producto Scanmaster antes de que el Grupo 4 fuera estandarizado. MMR se convirtió en el estándar de compresión propio de IBM a todavía se usa en muchos sistemas de imagen de IBM hoy en día.

Los sistemas de imágenes de documentos que almacenan grandes cantidades de datos de facsímil han adoptado estos esquemas de compresión CCITT para conservar espacio en disco. Los datos codificados con CCITT pueden descomprimirse rápidamente para impresión y visualización (asumiendo que hay suficientes recursos de memoria y CPU disponibles). Los mismos datos pueden también transmitirse usando tecnología de módem o protocolo de facsímil sin necesitar ser codificado primero.

Los algoritmos CCITT son no adaptivos. Es decir, no ajustan el algoritmo de codificación para codificar cada mapa de bits con eficiencia óptima. Estos usan una tabla fija de valores de códigos que fueron seleccionadas de acuerdo a un con junto de referencia de dcocumentos que contiene tanto texto como gráficos. El conjunto de referencia de documentos se consideró representativo de documentos que serían transmitidos por facsímil.

El Grupo 3 normalmente logran una tasa de compresión de 5:1 a 8:1 en un documento estándar de 200 dpi (204x196 dpi) con tamaño A4. Los resultados del Grupo 4 son aproximadamente el doble de eficientes que el Grupo 3, logrando tasas de compresión de hasta 15:1 con el mismo documento. Las afirmaciones de que los algoritmos CCITT son capaces de una compresión muchísimo mejor en documentos de negocio estándar son exageradas — principalmente por vendedores de hardware.

Ya que los algoritmos CCITT han sido optimizados para documentos tipográficos y escritos a mano, es razonable que imágenes radicalmente diferentes en composición no se comprimirán muy bien. Todo esto es muy cierto. Mapas de bits de dos niveles que contienen una alta frecuencia de corridas cortas, como se encuentran típicamente en imágenes de tono continuo hechas digitalmente de tonos medios, no se comprimen tan bien usando los algoritmos CCITT. Tales imágenes usualmente resultarán en una tasa de compresión de 3:1 o incluso menor, y muchas de hecho se comprimirán a un tamaño mayor que el original.

El CCITT de hecho define tres algoritmos para codificar datos de imagen de dos niveles:

G31D es el algoritmo más simple y el más fácil de implementar. Por esta razón, se discute en su totalidad en la primer subsección a continuación. G32D y G42D son mucho más complejos en su diseño y operación y se describen solo en términos generales a continuación.

Los algoritmos de Grupo 3 y Grupo 4 son estándares y por lo tanto producen los mismos resultados de compresión para todos. Si has escuchado cualquier afirmación de lo contrario, es por una de estas razones:

Grupo 3 Unidimensional (G31D)

La codificación Grupo 3 Unidimensional (G31D) es una variación del esquema de compresión por claves de Huffman. Una imagen de dos niveles se compone de una serie de corridas de pixeles blanco y negro de 1 bit de varias longitudes (1 = negro y 0 = blanco). Un codificador Grupo 3 determina la longitud de una corrida de pixeles en un scan line y produce una salida de longitud variable de palabras binarias de código que representan la longitud y el color de la corrida. Ya que la palabra de código producida como salida es más corta que la entrada, se logra la compresión de los datos de pixeles.

Las palabras de código run-length se toman de una tabla de valores predefinida que representa corridas de pixeles blanco y negro. Esta tabla es parte de la especificación T.4 y se usa para codificar y decodificar todos los datos de Grupo 3.

El tamaño de las palabras de código se determinaron originalmente por el CCITT, basándose estadísticamente en la frecuencia promedio de corridas blanco y negro que ocurren en documentos tipográficos y escritos a mano. Los documentos incluían delineados artísticos y se escribieron en varios idiomas diferentes. A las longitudes de corrida que ocurrían más frecuentemente se les asignaban palabras de código más pequeñas mientras que a las longitudes de corrida que ocurrían menos frecuentemente se les asignaban palabras de código más grandes.

En documentos impresos y escritos a mano, las corridas cortas ocurren más frecuentemente que las corridas largas. Las más frecuentes en ocurrir son corridas de 2 a 4 pixeles negros. El tamaño máximo de una longitud de corrida se limita por la longitud máxima de un scan line de Grupo 3.

Las longitudes de corrida se representan por dos tipos de palabras de código: construcción (makeup) y de terminación. Una corrida codificada de pixeles está conformada de cero o más palabras de código de construcción y una palabra de código de terminación. Las palabras de código de terminación representan corridas más cortas, y los códigos de construcción representan corridas más largas. Hay palabras de código de terminación y de construcción separadas tanto para corridas de blanco y de negro.

Las corridas de pixeles con una longitud de 0 a 63 se codifican usando un único código de terminación. Corridas de 64 a 2623 pixeles se codifican por un único código de construcción y un código de terminación. Las corridas de código más grandes de 2623 pixeles se codifican usando uno o más códigos de construcción y un código de terminación. La longitud de corrida es la suma de los valores de longitud representados por cada palabra de código.

Aquí hay algunos ejemplos de diferentes corridas codificadas:

Figura 9-7: Codificación CCITT Grupo 3
FIGURA 9-7: Codificación CCITT Grupo 3

El uso de longitudes de corrida codificadas con múltiples códigos de construcción se ha convertido en una extensión de facto al Grupo 3, porque dichos codificadores son necesarios para imágenes con resoluciones mayores. Y si bien la mayoría de codificadores de Grupo 3 soportan esta extensión, no esperes que lo hagan en todos los casos.

Decodificar datos del Grupo 3 requiere métodos diferentes a los de la mayoría de otros esquemas de compresión. Ya que cada palabra de código varía en longitud, el flujo de datos codificados debe leerse un bit a la vez hasta que se reconozca una palabra de código. Este puede ser un proceso lento y tedioso en el mejor de los casos. Para hacer que este trabajo sea fácil, se puede usar una tabla de estados para procesar los datos codificados un bit a la vez. Esta es la forma más rápida y eficiente de implementar un decodificador CCITT.

Todos los scan lines se codifican para comenzar con un a palabra de código run-length blanca (la mayoría de scan lines de imágenes de documentos comienzan con longitudes de corrida blancas). Si un scan line en cuestión comienza con una corrida blanca, se antepondrá una palabra de código de longitud de corrida blanca con longitud cero al scan line.

Un decodificador lleva el control del color de la corrida que está decodificando. Comparar el patrón de bits actual a valores en la tabla de bits de color opuesta es un desperdicio. Es decir, si se está decodificando una corrida negra, no hay razón para verificar la tabla para los códigos de run-length blancos.

También se definen varias palabras de código en un flujo de datos codificado con Grupo 3. Estos códigos se usan para proporcionar sincronización en el evento de que una transmisión telefónica experimente una ráfaga de ruido. Al reconocer este código especial, un decodificador CCITT puede identificar errores de transmisión e intentar aplicar un algoritmo de recuperación que se aproxime a los datos perdidos.

El código EOL es una palabra de código de 12 bits que comienza cada línea en una transmisión de Grupo 3. Esta palabra de código única se usa para detectar el inicio/fin de un scan line durante la transmisión de la imagen. Si una ráfaga de ruido corrompe temporalmente la señal, un decodificador de Grupo 3 descarta los datos no reconocidos que recibe hasta que encuentre un código EOL. Entonces el decodificador comenzaría a recibir la transmisión normalmente de nuevo, asumiendo que los datos que siguen al EOL, son el inicio del siguiente scan line. El decodificador podría también reemplazar la línea mala con un conjunto predefinido de datos, tal como un scan line blanco.

Un decodificador también usa los códigos EOL para varios propósitos. Los usa para llevar el control de la anchura de un scan line decodificado. (Una anchura incorrecta de scan line puede ser un error, o puede ser una indicación para rellenar con pixeles blancos hacia el EOl.) Además, usa los códigos EOL para llevar el control del número de scan lines en una imagen, a fin de detectar una imagen pequeña. Si encuentra una, rellena la longitud restante con scan lines con todos los pixeles en blanco. Un código EOL de Grupo 3 se ilustra en la Figura 9-8.

Figura 9-8: Codificación CCITT de Grupo 3 (código EOL)
FIGURA 9-8: Codificación CCITT de Grupo 3 (código EOL)

La mayoría de máquinas de FAX transmiten datos de una "longitud ilimitada", en cuyo caso el decodificador no puede detectar cuán larga se supone que es la imagen. Además, es más rápido no transmitir el espacio de solo blancos al final de una página, y muchas máquinas de FAX se detienen cuando detectan que el resto de la página es toda blanca; esperan que el receptor efectúe el rellenado con blanco al final del tamaño de página negociado.

Cuando los datos del Grupo 3 se encapsulan en un archivo de imagen, la información sobre la longitud y anchura de la imagen típicamente se almacena en la cabecera del archivo de imagen y el decodificador la lee antes de decodificarla.

Las transmisiones del mensaje de Grupo 3 se terminan por un código de retorno de control (Return to Control, o RTC) que se adjunta al final de cada flujo de datos del Grupo 3 y se usa para indicar el final de la transmisión del mensaje. Una palabra de código RTC simplemente tiene seis códigos EOL que ocurren consecutivamente. El RTC es de hacho parte del protocolo de facsímil y no es parte de los datos del mensaje codificados. Se usa para indicarle al receptor que debería liberar el portador de alta velocidad del mensaje y escuchar en el portador de baja velocidad para el comando post-página. Un código RTC del Grupo 3 se ilustra en la Figura 9-9.

Figura 9-9: Codificación CCITT Grupo 3 (código RTC)
FIGURA 9-9: Codificación CCITT Grupo 3 (código RTC)

Un relleno (FILL) no es realmente una palabra de código sino una corrida de uno o más bits a cero que ocurren entre el scan line codificado y el código EOL (pero nunca en la línea de scan line codificada en cuestión). Los bits de relleno se usan para rellenar la longitud de un scan line para aumentar el tiempo de transmisión de la línea a una longitud requerida. Los bits de relleno también pueden usarse para rellenar la palabra de código RTC para terminar en un límite de byte.

Compresión TIFF Tipo 2

El esquema de compresión TIFF Tipo 2 (en el cual el valor de la etiqueta de compresión es igual a 2) es una variación de la codificación CCITT G31D. Los métodos de compresión TIFF Tipo 3 y TIFF Tipo 4 siguen exactamente las especificaciones CCITT Grupo 3 y CCITT Grupo 4, respectivamente. La compresión de Tipo 2, por otro lado, implementa la codificación de Grupo 3 pero no usa palabras de código EOL o RTC. Por esta razón, la compresión TIFF Tipo 2 también es llamada "Grupo 3, Sin EOLs". Además, los bits de relleno nunca se unsan excepto para rellenar el último byte en un scan line hasta el siguiente límite de byte.

Estas modificaciones fueron incorporadas en la especificación TIFF porque los códigos EOL y RTC no se necesitan para leer datos almacenados en cinta o disco. Una imagen típica de tamaño carta (1728x2200 pixeles) contendría 26,484 bits (3310.5 bytes) de información EOL y RTC. Cuando se almacenan datos de Grupo 3 en un archivo, los siguientes no se necesitan:

Los codificadores convencionales del Grupo 3 no pueden manejar estas modificaciones y bien se negarán a leer los datos codificados con TIFF Tipo 2 o simplemente devolverán un flujo de basura de codificada. Sin embargo, se han desarrollado muchos decodificadores para aceptar estas "modificaciones" triviales del Grupo 3 y no tienen problemas al leer este tipo de datos. La codificación del Grupo 3 se ilustra en la Figura 9-10.

Figura 9-10: Codificación CCITT Grupo 3 (Compresión TIFF Tipo 2)
FIGURA 9-10: Codificación CCITT Grupo 3 (Compresión TIFF Tipo 2)

TIFF Clase F

Existe casi un formato de archivo de facsímil para cada marca de hardware y software de FAX de computadora que ha sido creado. Muchos comprimen los datos de facsímil usando RLE (presumiblemente para que sean más rápidos de desplegar) o los almacenan en su codificación de Grupo 3 original. Tal vez el formato de archivo de FAX más ampliamente usado es el formato no oficial TIFF Clase F. (Mira el artículo sobre TIFF en la Parte Dos de este libro para mayor información sobre TIFF Clase F.)

Aun con la última versión de TIFF, la revisión 6.0, la Clase F nunca se ha incluido oficialmente en el estándar, a pesar de los deseos del Concilio Asesor de TIFF. La razón para esto es que Aldus siente que soportar aplicaciones que requieran almacenamiento y recuperación de datos de facsímil está fuera del alcance de TIFF. (TIFF se diseñó principalmente con escáneres y publicación de escritorio en mente.) Esto es muy malo, considerando que una de las metas principales de TIFF es ayudar a promover la intercambiabilidad de datos de imagen entre plataformas de hardware y aplicaciones de software.

Grupo 3 Bidimensional (G32D)

La codificación Unidimensional del Grupo 3 (G31D), la cual discutimos antes, codifica cada scan line independientemente de las otras scan lines. Solo se considera una longitud de corrida a la vez durante el proceso de codificación y decodificación. Los datos que ocurren antes y después de cada longitud de corrida no son importantes para el paso de la codificación, solo los datos en la corrida presente son necesarios.

Con la codificación Bidimensional del Grupo 3 (G32D), por otro lado, la manera en que un scan line se codifica puede depender de los datos del scan line inmediatamente anterior. Muchas imágenes tienen un alto grado de coherencia vertical (redundancia). Al describir las diferencias entre dos scan lines, en lugar de describir los contenidos del scan line, la codificación 2D logra una mejor compresión.

El primer pixel de cada longitud de corrida es llamado un elemento cambiante. Cada elemento cambiante marca una transición de color dentro de un scan line (el punto en donde una corrida de un color termina y una corrida del siguiente color comienza).

La posición de cada elemento cambiante en un scan line se describe como estando a un cierto número de pixeles desde un elemento cambiante en la actual, línea de codificación (se efectúa codificación horizontal) o en la anterior, línea de referencia (se efectúa codificación vertical). Los códigos de salida usados para describir la información posicional en cuestión son llamados códigos Designados Relativos de Dirección de Elemento (Relative Element Address Designate, o READ).

Las palabras de código más cortas se usan para describir las transiciones de color que están a menos de cuatro pixeles de distancia entre sí en la línea de codificación o la línea de referencia. Se usan palabras de código más largas para describir transiciones de color que están a distancias mayores que las del elemento cambiante actual.

La codificación 2D es más eficiente que la unidimensional porque los datos usuales que se comprimen (documentos tipográficos o escritos a mano) contienen una gran cantidad de coherencia 2D.

Ya que un scan line codificado con G32D es dependiente de la exactitud del scan line anterior, un error, tal como una ráfaga de ruido de línea, puede afectar múltiples scan lines codificados bidimensionalmente. Si un error de transmisión corrompe un segmento de los datos de un scan line, esa línea no se puede decodificar. Pero aún peor, todas las scan lines que ocurren después de esta también se decodificarán incorrectamente.

Para minimizar el daño creado por el ruido, G32D usa una variable llamada un factor K y codifica bidimensionalmente K-1 líneas seguidas por una línea codificada unidimensionalmente. Si ocurre corrupción en la transmisión de datos, solo se perderán K-1 líneas de datos. El decodificador podrá resincronizar la decodificación en el siguiente código EOL disponible.

El valor típico para K es 2 o 4. Los datos G32D que se codifican con un valor K de 4 aparecen como un único bloque de datos. Cada bloque contiene tres líneas de datos 2D de scan line seguidos por un scan line de datos codificados unidimensionalmente.

La variable K no se usa normalmente al decodificar datos G32D. En lugar de eso, el código EOL se modifica para indicarle al algoritmo usado que codifique la línea que le sigue. Si se adjunta un bit a 1 al código EOL, la línea que le sigue se codifica unidimensionalmente. Todas las otras palabras marcadoras de códigos de transmisión (FILL y RTC) siguen la misma regla que en la codificación G31D. K solo se necesita al decodificar si la regeneración del scan line anterior codificado unidimensionalmente es necesaria para la recuperación de errores.

Grupo 4 Bidimensional (G42D)

La codificación Bidimensional de Grupo 4 (G42D) se desarrolló a partir del algoritmo G32D como un mejor esquema de compresión 2D — tanto mejor, de hecho, que el Grupo 4 ha reemplazado casi completamente al G32D en uso comercial.

La codificación del Grupo 4 es idéntica a la G32D excepto por unas pocas modificaciones. El Grupo 4 es básicamente el algoritmo G32D sin códigos EOL y una variable K establecida al infinito. El Grupo 4 fue diseñado específicamente para codificar datos que residen en unidades de disco y redes de datos. La detección/corrección integrada de errores de transmisión encontrada en el Grupo 3 por lo tanto no se necesita por los datos del Grupo 4.

La primer línea de referencia en la codificación de Grupo 4 es un scan line imaginario que contiene solo pixeles blancos. En la codificación G32D, la primer línea de referencia es el primer scan line de la imagen. En la codificación del Grupo 4, la palabra de código RTC se reemplaza por un código de final de bloque de facsímil (EOFB), el cual consiste de dos palabras de código EOL del Grupo 3. Tal como el RTC del Grupo 3, el EOFB también es parte del protocolo de transmisión y no es de hecho parte de los datos de imagen. Además, los datos de imagen codificados con los el Grupo 4 puede rellenarse con bits de relleno después del EOFB para terminar en un límite de byte.

La codificación de Grupo 4 usualmente resulta en una imagen comprimida dos veces más pequeña que si estuviera codificada con G31D. La compensación principal es que la codificación del Grupo 4 es más compleja y requiere más tiempo para llevarse a cabo. Cuando se implementa en hardware, sin embargo, la diferencia en la velocidad de ejecución entre los algoritmos del Grupo 3 y el Grupo 4 no es significativa, lo cual hace que el Grupo 4 sea una mejor elección en la mayoría de implementaciones de sistemas de imagen.

Tips para Diseñar Codificadores y Decodificadores CCITT

Aquí hay algunas pautas generales a seguir si estás usando el método de codificación CCITT para codificar o decodificar.

Para Mayor Información Sobre CCITT

Las especificaciones originales para los algoritmos CCITT Grupo 3 y Grupo 4 están en CCITT (1985) Volumen VII, Fascículo VII.3, Recomendaciones T.4 y T.6:

"Standardization of Group 3 Facsimile Apparatus for Document Transmission," Recommendation T.4, Volume VII, Fascicle VII.3, Terminal Equipment and Protocols for Telematic Services, The International Telegraph and Telephone Consultative Committee (CCITT), Geneva, Switzerland, 1985, pp. 16-31.

"Facsimile Coding Schemes and Coding Control Functions for Group 4 Facsimile Apparatus," Recommendation T.6, Volume VII, Fascicle VII.3, Terminal Equipment and Protocols for Telematic Services, The International Telegraph and Telephone Consultative Committee (CCITT), Geneva, Switzerland, 1985, pp. 40-48.

La especificación más reciente es la CCITT (1992) Volumen VII, Fascículo VII.3, Recomendaciones T.0 hasta T.63.

Tanto los documentos de CCITT y ANSI pueden obtenerse de la siguiente fuente:

American National Standards Institute, Inc.
Attn: Sales
1430 Broadway
New York, NY 10018 USA
Voice: 212-642-4900

Mira también las siguientes referencias. (Para información sobre obtener RFCs [Request for Comments], envía un email a rfc-info@isi.edu con una línea de asunto de "getting rfcs" y un cuerpo de "help: ways_to_get_rfcs".)

Hunter, R. and A.H. Robinson, "International Digital Facsimile Coding Standards," Proceedings of the IEEE, vol. 68, no. 7, July 1980, pp. 854-867.

RFC 804—CCITT Draft Recommendation T.4 (Standardization of Group 3 Facsimile Apparatus for Document Transmission).

RFC 1314—A File Format for the Exchange of Images in the Internet.

FAX: Digital Facsimile Technology & Applications, McConnell, Artech House, Norwood, MA; second edition, 1992.

Marking, Michael P., "Decoding Group 3 Images," The C Users Journal, June 1990, pp. 45-54.

Información sobre la codificación MMR puede encontrarse en las siguientes referencias:

"Binary-image-manipulation Algorithms in the Image View Facility," IBM Journal of Research and Development, vol. 31, no. 1, January 1987.

Información sobre la codificación Huffman puede encontrarse en las siguientes referencias:

Huffman, David, "A Method for the Construction of Minimum Redundancy Codes," Proceedings of the IRE, vol. 40, no. 9, 1952, pp. 1098-1101.

Kruger, Anton, "Huffman Data Compression," C Gazette, vol. 5, no. 4, 1991, pp.71-77.

Compresión JPEG

Uno de los temas más calientes en la tecnología de compresión de imágenes hoy en día es JPEG. El acrónimo JPEG significa Joint Photographic Experts Group (Grupo Conjunto de Expertos Fotográficos), un comité de estándares que tuvo sus orígenes dentro de la Organización Internacional de Estándares (ISO). En 1982, ISO formó el Grupo de Expertos Fotográficos (EG) para investigar métodos de transmisión de video, imágenes estáticas, y texto sobre líneas ISDN (Integrated Services Digital Network). La meta de PEG era producir un conjunto de estándares de la industria para la transmisión de gráficos y datos de imagen sobre redes de comunicación digital.

En 1986, un subgrupo de CCITT comenzó a investigar métodos de compresión de color y datos de escala de grises para transmisión de facsímil. Los métodos de compresión necesarios para los sistemas de facsímil a color eran muy similares a los investigados por PEG. Por lo tanto se acordó que los dos grupos deberían combinar sus recursos y trabajo conjunto hacia un único estándar.

Si bien los creadores de JPEG pueden haber visualizado una multitud de aplicaciones comerciales para la compresión JPEG, un público consumidor hecho hambriento por las promesas de mercadeo sobre tecnología de imágenes y multimedia se están beneficiando grandemente también. La mayoría de métodos de compresión anteriormente desarrollados hacen un trabajo relativamente pobre de comprimir datos de imagen de tono continuo; es decir, imágenes que contienen cientos de miles de colores tomados de sujetos del mundo real. Y muy pocos formatos de archivo pueden soportar imágenes de rastro de 24 bits.

GIF, por ejemplo, solo puede almacenar imágenes con una profundidad de pixel máxima de ocho bits, para un máximo de 256 colores. Y su algoritmo de compresión LZW no funciona muy bien en datos de imagen escaneados típicos. El ruido de bajo nivel comúnmente encontrado en dichos datos derrota la habilidad de reconocer patrones repetidos.

Tanto TIFF como BMP son capaces de almacenar datos de 24 bits, pero en sus versiones anteriores a JPEG solo son capaces de usar esquemas de codificación (LZW y RLE, respectivamente) que no comprimen este tipo de datos de imagen muy bien.

JPEG provee un método de compresión que es capaz de comprimir datos de imagen de tono continuo con una profundidad de pixel de 6 a 24 bits con velocidad y eficiencia razonables. Y si bien JPEG mismo no define un formato de archivo de imagen estándar, se han inventado o modificado varios para suplir las necesidades del almacenamiento de datos JPEG.

JPEG en Perspectiva

A diferencia de todos los otros métodos de compresión descritos hasta ahora en este capítulo, JPEG no es un único algoritmo. En su lugar, puede pensarse en este como un kit de herramientas de métodos de compresión de imagen que pueden alterarse para suplir las necesidades del usuario. JPEG puede ajustarse para producir imágenes comprimidas muy pequeñas que tienen apariencia de calidad relativamente pobre pero aún adecuadas para muchas aplicaciones. Igualmente, JPEG es capaz de producir imágenes comprimidas de muy alta calidad que son aún mucho más pequeñas que los datos originales descomprimidos.

JPEG también es diferente en que es primariamente un método de compresión con pérdida. La mayoría de esquemas de compresión de formatos de imagen populares, tales como RLE, LZW, o los estándares CCITT, son métodos de compresión sin pérdida. Es decir, no descarta ningún dato durante el proceso de codificación. Una imagen comprimida usando un método sin pérdida garantiza ser idéntica a la imagen original cuando se descomprime.

Los esquemas con pérdidas, por otro lado, descartan datos inútiles durante la codificación. Esta es, de hecho, la manera en la que los esquemas con pérdidas logran obtener tasas de compresión superior sobre la mayoría de esquemas sin pérdida. JPEG fue diseñado específicamente para descartar información que el ojo humano no puede ver fácilmente. Cambios ligeros de color no se perciben bien por el ojo humano, mientras que cambios ligeros en la intensidad (luz y sombra) sí lo son. Por lo tanto la codificación con pérdida de JPEG tiende a ser más frugal con la parte de escala de grises de una imagen y más frívola con el color.

JPEG se diseñó para comprimir imágenes a color o de escala de grises con tono continuo de sujetos del mundo real: fotografías, instantáneas de video, o cualquier gráfico complejo que recuerde sujetos naturales. Las animaciones, ray tracing, delineados artísticos, documentos blanco y netgro, y gráficos vectoriales típicos no se comprimen muy bien bajo JPEG y no se debería esperar que lo hagan. A, si bien JPEG se usa ahora para proveer compresión de video en movimiento, el estándar no hace provisiones especiales para tal aplicación.

El hecho de que JPEG tenga pérdida y funciona solo sobre un tipo selecto de datos de imagen puede hacerte preguntar: "¿Por qué molestarse en usarlo?" Depende de tus necesidades. JPEG es una manera excelente de almacenar imágenes fotográficas de 24 bits, tales como las usadas en aplicaciones de imagen y multimedia. Las imágenes JPEG de 24 bits (16 millones de colores) son superiores en apariencia a las imágenes de 8 bits (256 colores) en una pantalla VGA y están en su apariencia más espectacular cuando se usan en hardware de pantalla de 24 bits (el cual es ahora bastante barato).

La cantidad de compresión lograda depende del contenido de los datos de imagen. Una imagen de calidad fotográfica típica puede comprimirse desde 20:1 a 25:1 sin experimentar ninguna degradación notable en la calidad. Tasas de compresión mayores resultarán en archivos de imagen que difieren notablemente del original pero aún tienen una calidad de imagen total buena. Y lograr una tasa de compresión de 20:1 o mejor en muchos casos no solo ahorra espacio en disco, sino también reduce los tiempos de transmisión a través de redes de datos y líneas telefónicas.

Un usuario final puede "ajustar" la calidad de un codificador JPEG usando un parámetro a veces llamado una configuración de calidad o un factor Q. Si bien diferentes implementaciones tienen escalas variables de factores Q, un rango de 1 a 100 es típico. Un factor de 1 produce las imágenes más pequeñas y de peor calidad; un factor de 100 produce las imágenes más grandes de mejor calidad. El factor Q óptimo depende del contenido de la imagen y por lo tanto es diferente para cada imagen. El arte de la compresión JPEG es encontrar el menor factor Q que produce una imagen que es visiblemente aceptable, y preferiblemente tan cercana al original como sea posible.

La librería JPEG proporcionada por el Independent JPEG Group (incluida en el CD-ROM que acompaña este libro) usa una escala de configuración de calidad de 1 a 100. Para encontrar la compresión óptima para una imagen usando la librería JPEG, sigue estos pasos:

  1. Codifica la imagen usando una configuración de calidad de 75 (-Q 75).

  2. Si observas defectos inaceptables en la imagen, aumenta el valor, y recodifica la imagen.

  3. Si la calidad de la imagen es aceptable, disminuye la configuración hasta que la calidad de la imagen sea apenas aceptable. Esta será la configuración de calidad óptima para esta imagen.

  4. Repite este proceso para cada imagen que tengas (o simplemente codifícalas todas usando una configuración de calidad de 75).

JPEG no siempre es una solución de compresión ideal. Hay varias razones:

JPEG Básico

La especificación JPEG define un subconjunto mínimo del estándar llamado JPEG básico (baseline JPEG), que es todo lo que se requiere que las aplicaciones conscientes de JPEG soporten. Esta base usa un esquema de codificación basado en la Transformada Discreta de Coseno (Discrete Cosine Transform, o DCT) para lograr la compresión. DCT es un nombre genérico para una clase de operaciones identificadas y publicadas hace algunos años. Los algoritmos basados en DCT desde entonces se han abierto paso en varios métodos de compresión.

Los algoritmos de codificación basados en DCT siempre tienen pérdida por naturaleza. Los algoritmos DCT son capaces de lograr un alto grado de compresión con solo pérdida mínima de los datos. Este esquema es efectivo solo para comprimir imágenes de tono continuo en las que las diferencias entre pixeles adyacentes son usualmente pequeñas. En la práctica, JPEG funciona bien solo en imágenes con profundidades de por lo menos cuatro u ocho bits por canal de color. El estándar base de hecho especifica ocho bits por muestra de entrada. Datos de menos profundidad de bits pueden manejarse al escalarlos hasta ocho bits por muestra, pero los resultados serán malos para datos fuente de baja profundidad de bits, a causa de los saltos grandes entre valores adyacentes de pixeles. Por razones similares, datos fuente mapeados con color no funcionan muy bien, especialmente si a la imagen se le ha aplicado dithering.

El esquema de compresión JPEG se divide en las siguientes etapas:

  1. Transformar la imagen en un espacio de color óptimo.

  2. Submuestrear los componentes de crominancia al promediar juntos grupos de pixeles.

  3. Aplicar una Transformada Discreta de Coseno (DCT) a bloques de pixeles, removiendo así imágenes de datos redundantes.

  4. Cuantizar cada bloque de coeficientes DCT usando funciones de ponderación (weighting) optimizadas para el ojo humano.

  5. Codificar los coeficientes resultantes (datos de imagen) usando un algoritmo de Huffman de longitud de palabra variable para eliminar redundancias en los coeficientes.

La Figura 9-11 resume estos pasos, y las siguientes subsecciones miran cada uno de ellos a su vez. Nota que la decodificación de JPEG efectúa los pasos inversos a estos.

Figura 9-11: Compresión y descompresión JPEG
FIGURA 9-11: Compresión y descompresión JPEG

Transformar la Imagen

El algoritmo JPEG es capaz de codificar imágenes que usan cualquier tipo de espacio de color. El JPEG mismo codifica cada componente en un modelo de color separadamente, y es completamente independiente de cualquier modelo de espacio de color, tal como RGB, HSI, o CMY. Las mejores tasas de compresión resultan si un espacio de color de luminancia/crominancia, tal como YUV o YCbCr, es usado. (Mira el Capítulo 2 para una descripción de estos espacios de color.)

La mayoría de la información visual a la que los ojos humanos son más sensibles se encuentra en el componente de alta frecuencia, de escala de grises, de crominancia (Y) del espacio de color YCbCr. Los otros dos componentes de crominancia (Cb y Cr) contienen información de color de alta frecuencia a la cual el ojo humano es menos sensible. Por lo tanto la mayoría de esta información puede descartarse.

En comparación, los modelos de color RGB, HSI, y CMY propagan su información visual de la imagen uniformemente a través de cada uno de los tres componentes de color, haciendo que descartar selectivamente la información sea muy difícil. Todos estos tres componentes de color necesitarían codificarse a la más alta calidad, resultando en una tasa de compresión más pobre. Las imágenes de escala de grises no tienen un espacio de color como tal y por lo tanto no requieren transformación.

Submuestrear (Downsample) los componentes de crominancia

La manera más simple de explotar la sensitividad menor del ojo a la información de crominancia es simplemente usar menos pixeles para los canales de crominancia. Por ejemplo, en una imagen nominalmente de 1000x1000, podríamos usar todos los 1000x1000 pixeles pero solo 500x500 pixeles para cada componente de crominancia. En esta representación, cada pixel de crominancia cubre la misma área que un bloque de 2x2 de pixeles de luminancia. Almacenamos un total de seis valores de pixeles para cada bloque de 2x2 (cuatro valores de luminancia, uno para cada uno de los dos canales de crominancia), en lugar de doce valores necesarios si cada componente se representara en resolución completa. Sorprendentementen, esta reducción del 50 por ciento en el volumen de datos casi no tiene efecto en la calidad percibida de la mayoría de imágenes. Ahorros equivalentes no son posibles con modelos de color convencionales tales como RGB, porque en RGB cada canal de color acarrea alguna información de luminancia y por lo tanto cualquier pérdida de resolución es muy visible.

Cuando se suministran datos descomprimidos en un formato convencional (la misma resolución para todos los canales), un compresor JPEG debe reducir la resolución de los canales de crominancia al submuestrear, o promediar juntos, grupos de pixeles. El estándar JPEG permite varias opciones diferentes para las tasas de muestreo, o tamaños relativos, de los canales submuestreados. El canal de luminancia siempre se deja en su resolución completa (muestreo de 1:1). Típicamente ambos canales de crominancia se submuestrean a 2:1 y a 1:1 o 2:1 verticalmente, lo que significa que un pixel de crominancia cubre la misma área que un bloque de 2x1 o 2x1 pixeles de luminancia. JPEG se refiere a estos procesos de submuestreo como muestreos 2h1v y 2h2v, respectivamente.

Otra notación comúnmente usada es el muestreo 4:2:2 para 2h1v y 4:2:0 para 2h2v; esta notación se deriva de las costumbres de la televisión (la transformación de color y el submuestreo han estado en uso desde el comienzo de la transmisión de TV a color). El muestreo 2h1v es muy común porque corresponde a la práctica estándar de TV de National Television Standards Committee (NTSC), pero ofrece menos compresión que el muestreo 2h2v, difícilmente con alguna ganancia en la calidad percibida.

Aplicar una Transformada Discreta del Coseno

Los datos de imagen se dividen en bloques de pixeles de 8x8. (A partir de este punto, cada componente de color se procesa independientemente, así que un "pixel" significa un valor individual, incluso en una imagen a color.) Se aplica una DCT a cada bloque de 8x8. La DCT convierte la representación espacial de la imagen en un mapa de frecuencia: el término de orden inferior "DC" representa el valor promedio en el bloque, mientras que los términos sucesivos de orden superior ("AC") representan la fuerza de cambios más y más rápidos a través de la anchura o altura del bloque. El término AC más alto representa la fuerza de una onda de coseno que alterna de máximo a mínimo en pixeles adyacentes.

El cálculo del DCT es bastante complejo; de hecho, este es el paso más costoso en la compresión JPEG. El punto de hacer esto es que ahora hemos separado la información de alta y baja frecuencia presente en la imagen. Podemos descartar fácilmente los datos de alta frecuencia sin perder la información de baja frecuencia. El paso DCT en sí no tiene pérdida excepto por errores de redondeo.

Cuantizar cada bloque

Para descartar una cantidad apropiada de información, el compresor divide cada valor de salida DCT entre un "coeficiente de cuantización" y redondea el resultado a un entero. Entre mayor sea el coeficiente de cuantización, más datos se perderán, porque el valor DCT en cuestión se representa con cada vez menos precisión. Cada una de las 64 posiciones del bloque de salida DCT tienen su propio coeficiente de cuantización, con los términos de orden mayor siendo cuantizados más pesadamente que los términos de orden inferior (es decir, los términos de orden mayor tienen coeficientes de cuantización más grandes). Además, se emplean tablas de cuantización separadas para los datos de luminancia y crominancia, con los datos de crominancia siendo cuantizados más pesadamente que los datos de luminancia. Esto le permite al JPEG explotar más la diferente sensitividad del ojo a la luminancia y la crominancia.

Es este paso el que se controla por la configuración de "calidad" de la mayoría de compresores JPEG. El compresor comienza desde una tabla integrada que es apropiada para una configuración de calidad media e incrementa o disminuye el valor de cada entrada de la tabla en proporción invversa a la calidad solicitada. Las tablas de cuantización completas usadas realmente se registran en el archivo comprimido para que el descompresor sepa cómo reconstruir (aproximadamente) los coeficientes DCT.

La selección de una tabla de cuantización apropiada es de alguna manera un arte oscuro. La mayoría de compresores existentes comienzan a partir de una tabla de muestras desarrollada por el comité ISO JPEG. Es posible que investigación futura producirá mejores tablas que ofrezcan más compresión para la misma calidad percibida de imagen. La implementación de tablas mejoradas no debería causar ningún problema de compatibilidad, porque el descompresor meramente lee las tablas desde el archivo comprimido; no les importa cómo fue elegida la tabla.

Codificar los coeficientes resultantes

Los coeficientes resultantes contienen una cantidad significativa de datos redundantes. La compresión Huffman eliminará las redundancias sin pérdida, reultando en datos JPEG más pequeños. Una extensión opcional a la especificación JPEG permite usar codificación aritmética en lugar de Huffman para una tasa de compresión aún mayor. (Mira la sección llamada "Extensiones de JPEG (Parte 1)" a continuación.) En este punto, el flujo de datos JPEG está listo para ser transmitido a través de canales de comunicación encapsulado dentro de un formato de archivo de imagen.

Extensiones de JPEG (Parte 1)

Lo que hemos examinado hasta ahora es solo la especificación base de JPEG. Se ha definido un número de extensiones en la Parte 1 de la especificación JPEG que ofrecen construcción progresiva de imagen, tasas de compresión mejoradas usando codificación aritmética, y un esquema de compresión sin pérdida. Estas características van más allá de las necesidades de la mayoría de implementaciones JPEG y por lo tanto se han definido como extensiones "no requeridas para ser soportadas" por el estándar JPEG.

Construcción progresiva de imagen

La construcción progresiva de la imagen es una extensión para usarse en aplicaciones que necesitan recibir flujos de datos JPEG y desplegarlos en tiempo real. Una imagen JPEG básica solo puede desplegarse después de que todos los datos de la imagen se han recibido y decodificado. Pero algunas aplicaciones requieren que la imagen se despliegue después de haber recibido solo parte de los datos. Usando un método de compresión convencional, esto significa desplegar las primeras pocas scan lines de la imagen a medida que se decodifica. En este caso, incluso si los scan lines estuvieran entrelazados, necesitarías al menos 50 por ciento de los datos de la imagen para tener una buena idea de los contenidos de la imagen. La extensión de construcción progresiva del JPEG ofrece una mejor solución.

La construcción progresiva le permite a una imagen ser enviada en capas en lugar de scan lines. Pero en lugar de transmitir cada plano de bits o canal de color en secuencia (lo cual no sería muy útil), se envía una sucesión de imágenes construidas de aproximaciones de la imagen original. El primer escaneo proporciona una representación de baja precisión de la imagen entera — de hecho, una imagen comprimida con JPEG de muy baja calidad. Escaneos subsecuentes refinan gradualmente la imagen al aumentar el valor efectivo de calidad. Si los datos se despliegan en tiempo real, primero verías una renderización tosca pero reconocible de la imagen completa. Esta aparecería muy rápido porque solo se necesitaría enviar una pequeña cantidad de datos para producirla. Cada escaneo subsecuente mejoraría la calidad de la imagen desplegada un bloque a la vez.

Una limitación del JPEG progresivo es que cada escaneo ocupa esencialmente un ciclo completo de JPEG para desplegarse. Por lo tanto, con las tasas de transmisión de datos típicas, se necesitaría un decodificador JPEG muy rápido (probablemente hardware especializado) para hacer uso efectivo de la transmisión progresiva.

Una extensión relacionada del JPEG ofrece almacenamiento jerárquico de la misma imagen en múltiples resoluciones. Por ejemplo, una imagen podría almacenarse en 250x250, 500x500, 1000x1000 y 2000x2000 pixeles, de modo que el mismo archivo de imagen podría soportar el despliegue en pantallas de baja resolución, impresores láser de mediana resolución, e imagesetters de alta resolución. Las imágenes de mayor resolución se almacenan como diferencias de las de menor resolución, así que necesitan menos espacio de lo que necesitarían si estuvieran almacenadas independientemente. Esto no es lo mismo que las series progresivas, porque cada imagen está disponible individualmente en su propio derecho a la calidad deseada completa.

Codificación aritmética

El estándar básico JPEG define la compresión Huffman como el paso final en el proceso de codificación. Una extensión JPEG reemplaza el motor Huffman con un codificador de entropía de aritmética binaria. El uso de un codificador aritmético reduce el tamaño resultante de los datos JPEG en 10 o 15 porciento adicional sobre los resultados que se obtendrían con el codificador Huffman. Sin cambios en la calidad resultante de la imagen, esta ganancia podría ser de importancia en implementaciones en donde se archivan enormes cantidades de imágenes JPEG.

La codificación aritmética tiene varias desventajas:

Compresión lossless de JPEG

Una pregunta que surge comúnmente es "¿En qué factor Q el JPEG se vuelve sin pérdida?" La respuesta es "nunca." El JPEG básico es un método de compresión con pérdida sin importar los ajustes que puedas hacer en los parámetros. De hecho, los codificadores basados en DCT siempre tienen pérdida, porque los errores de redondeo son inevitables en la conversión de color y los pasos DCT. Puedes suprimir la pérdida de información deliberada en los pasos de submuestreo y cuantización, pero todavía no obtendrás una rereación exacta de los bits originales. Además, esta configuración de pérdida mínima es una manera muy ineficiente de usar el JPEG sin pérdida.

El estándar JPEG ofrece un modo separado sin pérdida. Este modo no tiene nada en común con los algoritmos regulares basados en DCT, y actualmente está implementado solo en unas pocas aplicaciones comerciales. El JPEG sin pérdida es una forma de Codificación Predictiva Sin Pérdida usando un equema de Modulación de Código de Pulso Diferencial (Differential Pulse Code Modulation, o DPCM). La premisa básica es que el valor de un pixel se combina con los valores e hasta tres pixeles adyacentes para formar un valor predictor. El valor predictor luego se resta del valor original del pixel. Cuando se ha procesado el mapa de bits entero, los predictores resultantes se comprimen usando ya sea los métodos de codificación de entropía Huffman o la de aritmética binaria descritos en el estándar JPEG.

El JPEG sin pérdida funciona en imágenes con 2 a 16 bits por pixel, pero tiene mejor rendimiento sobre imágenes con 6 o más bits por pixel. Para dichas imágenes, la tasa de compresión típica lograda es 2:1. Para datos de imagen con menos bits por pixel, otros esquemas de compresión logran mejores resultados.

Extensiones de JPEG (Parte 3)

Las siguientes extensiones de JPEG se describen en la Parte 3 de la especificación JPEG.

Cuantización variable

Esta es una mejora disponible a los procedimiento de cuantización basados en DCT. Esta mejora puede usarse con cualquiera de los procesos basados en DCT definidos por JPEG a excepción del proceso básico.

El proceso de cuantización usado en JPEG cuantiza cada uno de los 64 coeficientes DCT usando un valor correspondiente a partir de una tabla de cuantización. Los valores de cuantización pueden redefinirse antes de iniciar un escaneo pero no deben cambiarse una vez que están dentro de un escaneo del flujo de datos comprimidos.

La cuantización de variables permite escalar los valores de cuantización dentro del flujo de datos comprimidos. Al inicio de cada bloque de 8x8 está un factor de escala de cuantizador usado para escalar los valores de la tabla de cuantización dentro de un componente de imagen y para corresponder estos valores con los coeficientes AC almacenados en los datos comprimidos. Los valores de cuantización pueden entonces localizarse y cambiarse según se necesite.

La cuantización variable permite que las características de una imagen sean cambiadas para controlar la calidad de la salida basándose en un modelo dado. El cuantizador variable puede ajustarse constantemente durante la decodificación para ofrecer una salida óptima.

La cantidad de datos de salida también puede disminuirse o aumentarse al elevar o disminuir el factor de escala de cuantizador. El tamaño máximo del archivo JPEG o flujo de datos resultante puede imponerse por ajustes adaptivos constantes efectuados por el cuantizador variable.

La extensión de cuantización de variable también permite al JPEG almacenar datos de imagen originalmente codificados usando un esquema de cuantización variable, tal como MPEG. Para que los datos MPEG sean transcodificados con precisión en otro formato, el otro formato debe soportar cuantización variable para mantener una alta tasa de compresión. Esta extensión le permite al JPEG soportar un flujo de datos originalmente derivado de una fuente variablemente cuantizada, tal como un I-frame MPEG.

Refinamiento selectivo

Este se usa para seleccionar una región de imagen para mejoras adicionales. Este realce mejora la resolución y el detalle de una región de una imagen. JPEG soporta tres tipos de refinamiento selectivo: jerárquico, progresivo, y componente. Cada uno de estos procesos de refinamiento difiere en su aplicación, efectividad, complejidad y cantidad de memoria requerida.

Enlosado de imagen

Este se usa para dividir una imagen individual en dos o más subimágenes más pequeñas. El enlosado permite poner más fácil en un búferes a los datos de la imagen en memoria, acceso aleatorio más rápido en el disco, y el almacenamiento de imágenes más grandes que muestras de 64Kx64K de tamaño. JPEG soporta tres tipos de enlosado: simple, piramidal, y compuesto.

SPIFF (Still Picture Interchange File Format)

SPIFF es un formato de archivo oficialmente sancionado que está pensado para reemplazar el formato JFIF defacto (JPEG File Interchange Format) usado hoy en día. SPIFF incluye todfas las características de JFIF y agrega varias funcionalidades adicionales. SPIFF está diseñado para que lectores JFIF apropiadamente escritos lean archivos SPIFF JPEG también.

Para mayor información, mira el artículo sobre SPIFF en la Parte Dos de este libro.

Otras Extensiones

Otras extensiones de JPEG incluyen la adición de un segmento marcador de versión que almacena el nivel mínimo de funcionalidad requerido para decodificar el flujo de datos JPEG. Pueden incluirse múltiples marcadores de versión para marcar áreas del flujo de datos que tienen requerimientos de funcionalidad mínima que difiere. El marcador de versión también contiene información que indica los procesos y extensiones usados para codificar el flujo de datos JPEG.

Para Mayor Información Sobre JPEG

El estándar JPEG está disponible en Inglés, Francés o Español, y como copia en papel o un documento PostScript o de Word para Windows desde la Organización Internacional de Estándares (ISO) o Unión Internacional de Telecomunicaciones (International Telecommunication Union, o ITU). Copias de estos estándares pueden ordenarse desde:

American National Standards Institute, Inc.
Attention: Customer Service
11 West 42nd St.
New York, NY 10036 USA
Voice: 212-642-4900

El estándar está publicado tanto como una Recomendación de ITU y como un Estándar Internacional ISO/IEC, y está dividido en tres partes. La Parte 1 es la especificación en cuestión. La Parte 2 cubre métodos de prueba de conformidad, y la Parte 3 cubre las extensiones de la especificación JPEG. Las Partes 1 y 2 están en estado de Estándar Internacional. Mira estos documentos:

"Digital Compression and Coding of Continuous-Tone Still Images, Requirements and Guidelines," Documento número ITU-T T.81 o ISO/IEC 10918-1.

"Digital Compression and Coding of Continuous-Tone Still Images, Compliance testing," Documento número ITU-T T.83 o ISO/IEC 10918-2.

La Parte 3 todavía está en estado de Borrador del Comité. Mira este documento:

"Digital Compression and Coding of Continuous-Tone Still Images, Extensions," Documento número ITU-T T.84 o ISO/IEC 10918-3.

Nueva información sobre JPEG y algoritmos relacionados está apareciendo constantemente. La mayoría de trabajo comercial para JPEG está siendo realizado en estas compañías:

Eastman Kodak Corporation
232 State Street
Rochester, NY 14650
Voice: 800-242-2424
WWW: http://www.kodak.com

C-Cube Microsystems
1778 McCarthy Boulevard
Milpitas, CA 95035
Voice: 408-944-6300

Mira el artículo sobre el formato de archivo JFIF soportado por C-Cube en la Parte Dos de este libro y el formato de archivo SPIFF definido por la Parte 3 de la especificación JPEG.

La FAQ de JPEG es una fuente útil de información general sobre JPEG. Esta FAQ está incluida en el CD-ROM que acompaña este libro; sin embargo, ya que la FAQ se actualiza frecuentemente, la versión del CD-ROM debería usarse solo para información general. La FAQ se envía cada dos semanas a los grupos de noticias de USENET comp.graphics.misc, news.answers, y comp.answers. Puedes obtener la última versión de esta FAQ desde el archivo news.answers en:

   ftp://rtfm.mit.edu/pub/usenet/news.answers/jpeg-faq

También puedes obtener esta FAQ enviando un email a:

   mail-server@rtfm.mit.edu

con el mensaje "send usenet/news.answers/jpeg-faq" en el cuerpo.

Un consorcio de programadores, el Grupo Independiente de JPEG (Independent JPEG Group, o IJG), ha producido una versión de dominio público del codificador y decodificador JPEG en forma de código fuente de C. Hemos incluido este código en el CD-ROM que acompaña este libro. Puedes obtener la librería IJG desde varios sitios FTP, servicios de información, y bulletin boards de computadoras.

La mejor introducción corta del algoritmo de compresión JPEG es:

Wallace, Gregory K., "The JPEG Still Picture Compression Standard," Communications of the ACM, vol. 34, no. 4, April 1991, pp. 30-44.

Una explicación más completa de JPEG puede encontrarse en los siguientes textos:

Pennebaker, William B. and Joan L. Mitchell, JPEG: Still Image Data Compression Standard, Van Nostrand Reinhold, New York, 1993.

Este libro contiene el texto completo de los estándarares ISO JPEG. (DIS 10918-1 y 10918-2). Esta es por mucho la exposición más completa de JPEG en existencia y es altamente recomendada.

Nelson, Mark, The Data Compression Book, M&T Books, Redwood City, CA. 1991.

Este libro ofrece buenas explicaciones y código C de ejemplo para una multitud de métodos de compresión, incluyendo JPEG. Es una fuente excelente si te sientes cómodo leyendo código de C pero no sabes mucho sobre compresión de datos en general. El código de muestra de JPEG del libro está incompleto y no es muy robusto, pero el libro es un buen tutorial.

Aquí hay una bibliografía corta de lectura adicional de JPEG:

Barda, J.F., "Codage et Compression des Grandes Images," Proceedings of AFNOR Multimedia and Standardization Conference, vol. 1, March 1993, pp. 300-315.

Hudson, G., H. Yasuda, and I. Sebestyen, "The International Standardization of Still Picture Compression Technique," Proceedings of the IEEE Global Telecommunications Conference, November 1988, pp. 1016-1021.

Leger, A., J. Mitchell, and Y. Yamazaki, "Still Picture Compression Algorithms Evaluated for International Standardization," Proceedings of the IEEE Global Telecommunications Conference, November 1988, pp. 1028-1032.

Leger, A., T. Omachi, and T.K. Wallace, "JPEG Still Picture Compression Algorithm," Optical Engineering, vol. 30, no. 7, July 1991, pp. 947-954. Mitchell, J.L., and W.B. Pennebaker, "Evolving JPEG Color Data Compression Standard," en Standards for Electronic Imaging Systems, Neir, M. and M.E. Courtot, eds., vol. CR37, SPIE Press, 1991, pp. 68-97.

Netravali, A.N., and B.G. Haskell, Digital Pictures: Representation and Compression, Plenum Press, New York, 1988.

Rabbani, M., and Jones, P., Digital Image Compression Techniques, Tutorial Texts in Optical Engineering, vol. TT7, SPIE Press, 1991.




Compresión JBIG

JBIG es un método para comprimir datos de imagen bi-nivel (dos colores). El acrónimo JBIG significa Joint Bi-level Image Experts Group, un comité de estándares que tuvo sus orígenes dentro de la Organización Internacional de Estándares (ISO). El estándar de compresión que desarrollaron lleva el nombre de este comité.

En 1988, ISO y CCITT formaron JBIG al unir el grupo ISO/IEC JTCV1/SC29/WG9 y el subgrupo CCITT SGVIII para el propósito conjunto de desarrollar un método estándar sin pérdida para comprimir datos bi-nivel. En 1993, el estándar que definía el método JBIG de la codificación de datos bi-nivel fue finalizado y liberado.

Las características principales de JBIG son:

JBIG está pensado para reemplazar completamente los algoritmos de compresión menos eficientes MR (Modified READ) y MMR (Modified Modified READ) usados por los protocolos de transmisión de datos CCITT Grupo 3 (G3) y Grupo 4 (G4), respectivamente. En 1995, la Unión Internacional de Telecomunicaciones (International Telecommunication Union, o ITU), propuso una extensión de los estándares G3 y G4 para permitir el uso de datos de imagen comprimida JBIG en conjunto con estos protocolos (Refiérete a la sección sobre la compresión CCITT para más detalles sobre los protocoloes G3 y G4.)

En imágenes escaneadas de delineados artísticos y texto impreso, JBIG logra tasas de compresión 10 por ciento a 50 por ciento mayores que las de G4, y hasta 500 porciento mayores en imágenes generadas por computadora o texto impreso. Las imágenes bi-nivel procesados con tonos medios (half-toning) o dithering se comprimen de 2 a 30 veces más pequeñas que cuando se comprimen con G4.

JBIG logra estas tasas de compresión impresionantes al adaptarse al contenido de información de los datos de imagen a comprimir. Se usa un codificador adaptivo aritmético para predecir y codificar símbolos de datos futuros basándose en las características de los datos que se están codificando actualmente. G3 y G4, sin embargo, son no adaptivos y usan los mismos patrones fijos y algoritmos para codificar todos los datos de la imagen sin importar el contenido.

JBIG también soporta tanto métodos de codificación secuencial y progresiva. La codificación secuencial lee datos desde la parte más alta a la parte más baja y de izquierda a derecha de una imagen y la codifica como una única imagen. La codificación progresiva permite almacenar una serie de versiones de resoluciones múltiples de los mismos datos de imagen dentro de un único flujo de datos JBIG. En contraste, G3 y G4 solo soportan la codificación secuencial a una resolución fija.

JBIG es independiente de plataforma y se implementa fácilmente sobre una amplia variedad de entornos distribuidos. Esta logra tasas de compresión excelentes en imágenes bi-nivel y es capaz de codificar eficientemente algunos tipos de imágenes a color y de escala de grises también. Las capacidades de codificación progresiva de JBIG aparentan convertirlo en la elección obvia para transmitir y almacenar información bi-nivel en entornos en red, tales como la WWW. Así que, ¿por qué JBIG no es más popular y extendido?

Es cuestionable cuánto éxito tendrá JBIG en reemplazar ya sea a G3 o G4. G3 y MR son el protocolo y método de compresión más ampliamente usados, respectivamente, para transmisión de facsímil, y ya se soportan por la mayoría de equipo de telecomunicación que usa datos de imagen bi-nivel. Y G4, si bien típicamente requiere demasiado ancho de banda para propósitos convencionales de facsímil, es un método primario de compresión de datos en la mayoría de sistemas de imágenes de documentos, G4 logra tasas de compresión efectivas de hasta 20 a 1 tanto en datos de imagen de documentos bi-nivel escaneados y generados por computadora.

Tal vez la mayor ventaja que los protocolos CCITT ofrecen sobre JBIG es que son libres y no cubiertos por patentes y disputas legales. Cualquiera puede implementar libremente y distribuir códecs G4 y G4 sin la necesidad de acuerdos de licencia o pagos de regalías. JBIG, por otro lado, contiene muchos procesos patentados (se listan 24 en la Recomendación JBIG); el más prominente es el Q-coder aritmético de IBM, el cual es una opción en JPEG, pero es obligatorio en JBIG.

Fundamentos de JBIG

Las imágenes bi-nivel solo contienen dos colores y se almacenan usando un único bit por pixel. Las imágenes blanco y negro, talas como las páginas de un libro, son el tipo más común de imágenes bi-nivel. Sin embargo, se pueden representar cualquiera de dos colores por los estados 1 (color de frente) o 0 (color de fondo) de un bit individual.

Los algoritmos típicos de compresión codifican solo una única scan line a la vez usando una técnica de codificación run-length. Dichos algoritmos son referidos como métodos de codificación 1D. Los métodos de codificación 2D codifican corridas de pixeles al describir las diferencias entre los valores de pixeles en el scan line actual y el anterior.

JBIG codifica datos de imagen redundantes al comparar un pixel en un scan line con un conjunto de pixeles ya escaneados por el codificador. Estos pixeles adicionales son llamados una plantilla (template), y forman un mapa simple del patrón de pixeles que rodea el pixel que está siendo codificado. Los valores de estos pixeles se usan para identificar patrones redundantes en los datos de imagen. Estos patrones son luego comprimidos usando un codificador adaptivo de compresión aritmética.

La naturaleza adaptiva de las plantillas permite que el color de los valores de los pixeles sea codificado para ser predecido con un alto grado de éxito. Para imágenes de escala de grises con halftoning, las tasas de compresión se aumentan tanto como hasta 80 por ciento sobre métodos no adaptivos.

Si bien ha sido diseñado primariamente como un método de compresión de datos de imagen bi-nivel, JBIG es capaz de comprimir imágenes a color o de escala de grises con una profundidad de hasta 255 bits por pixel. Tales imágenes de pixeles multibit se comprimen por planos de bits en lugar de por pixel. Por ejemplo, una imagen de 8 bits comprimida usando JBIG sería codificada en ocho planos de bits separados.

Este tipo de codificación puede usarse como una alternativa al JPEG sin pérdida. Se ha encontrado que JBIG produce mejores resultados de compresión que el JPEG sin pérdida (usando el Q-coder) en imágenes con dos a cuatro bits por pixel y produce resultados idénticos sobre datos de imagen con pixeles de seis a ocho bits en profundidad.

Es recomendable que cada plano de bits sea procesado con un algoritmo de codificación en grises para normalizar los cambios entre valores de bits adyacentes en los datos de imagen. El proceso aumenta la eficiencia del codificador JBIG.

Las imágenes JBIG pueden codificarse secuencialmente o progresivamente. Las imágenes codificadas secuencialmente se almacenan en una capa individual en resolución completa y sin otras imágenes de mejor resolución almacenadas en el mismo flujo de datos. Esta imagen JBIG secuencial es equivalente en función y aplicación a una imagen G4. Dicha imagen se decodifica en una pasada individual y tiene al menos tan buena tasa de compresión como G4.

Las imágenes codificadas progresivamente comienzan con la imagen de mayor resolución y terminan con la más baja. La imagen de alta resolución se almacena en una capa separada y luego se usa para producir una imagen de menor resolución, también almacenada en su propia capa. Cada capa después de la primera es llamada un duplicado de resolución. Se dice que una imagen con dos capas tiene dos duplicados.

No hay límite impuesto en el número de duplicados que se pueden codificar. Por ejemplo, una imagen de 1200 dpi puede codificarse como una capa (1200 dpi), tres capas (1200, 600 , y 300 dpi), o cinco capas (1200, 600, 300, 150 y 75 dpi). La menor resolución se determina por lo que sea que sea considerado útil. Incluso una imagen de 10 dpi, si bien ilegible, es aún útil como un icono.

La decodificación progresiva es el proceso opuesto, decodificando primero la imagen de menor resolución, seguida por resoluciones en aumento de la imagen hasta que se logra la resolución completa. Esta técnica tiene la ventaja de permitir que aparezcan datos inmediatamente en el dispositivo de salida. Solo se necesita decodificar y enviar datos hasta la resolución apropiada del dispositivo de salida.

Tanto la codificación secuencial como progresiva de JBIG son completamente compatibles. Las imágenes comprimidas usando la codificación secuencial son legibles por decodificadores JBIG progresivos. Los decodificadores JBIG secuenciales solo son capaces de leer la primera capa de más baja resolución dentro de una imagen JBIG codificada progresivamente.

Muchas aplicaciones que usan JBIG pueden solo usar codificación y decodificación secuencial, especialmente aquellas usadas para la transmisión de facsímil. Por lo tanto es posible implementar un algoritmo JBIG simplificado que solo codifique la primera capa en un flujo de datos JBIG. Dichos codificadores producen un flujo de datos válido codificado con JBIG que es legible por todos los decodificadores JBIG.

La codificación progresiva no agrega muchos más datos a un flujo de datos JBIG de lo que hace la codificación secuencial, pero tiene requerimientos de memoria mayores. Ya que una imagen de menor resolución se codifica a partir de los datos de la siguiente imagen de mayor resolución (y viceversa cuando se decodifica), se debe usar un frame buffer para almacenar los datos de imagen que están siendo usados como una referencia.

Para Mayor Información Sobre JBIG

JBIG está publicado tanto como una recomendación ITU como un Estándar ISO/IEC:

ITU-T Recommendation T.82|ISO/IEC 11544:1993, Coded representation of Picture and Audio Information—Progressive Bi-Level Image Compression.

Este documento está disponible por un costo, desde el ITU, ISO, y muchos servicios de doocumentos. Para mayor información sobre ITU e ISO, por favor visita su sitio Web:

http://www.itu.ch
http://www.iso.ch

La publicación de Noviembre de 1988 del IBM Journal of Research and Development contiene un conjunto de cinco artículos que describen el Q-coder de IBM y un codificador básico de imagen bi-nivel que implementa el Q-coder. Mira:

Pennebaker, W.B., J.L. Mitchell, G.G. Langdon, and R.B. Arps, "An Overview of the Basic Principles of the Q-coder Adaptive Binary Arithmetic Coder," IBM Journal of Research and Development, vol. 32, no. 6, November 1988, pp. 717-726.

El Q-coder también se describe como una extensión en la Parte 1 de la Recomendación JPEG ITU-T, T.81, y el Estándar ISO/IEC 10918-1.

El siguiente documento técnico cubre T.4, T.6, JBIG, y otros protocolos de comunicación de facsímil:

Urban, Stephen J., "Review of Standards for Electronic Imaging for Facsimile Systems," Journal of Electronic Imaging, vol. 1, no. 1, January 1992, pp. 5-21.

El JBIG-KIT, un kit de herramientas de compresión de imagen bi-nivel, se proporciona en el CD-ROM y también está disponible a través de FTP anónimo de cualquiera de las siguientes direcciones:

ftp://ftp.informatik.uni-erlangen.de/pub/doc/ISO/JBIG/jbigkit-0.8.tar.gz
ftp://nic.funet.fi/pub/textonly/misc/test-images/jbig.tar.gz

JBIG-KIT es una implementación ANSI C del estándar de codificación JBIG en la forma dfe una librería portable usada para codificar y decodificar flujos de datos JBIG. Esta librería está diseñada específicamente para arquitecturas de máquina de 32 bits (y superiores), aunque también se soportan sistemas de 16 bits.

JBIG-KIT es software libre bajo la GNU General Public License y proporciona código completo y documentación. Una copia de borrador de 1992 de la Recomendación CCITT T.82 para JBIG también está incluida actualmente en esta distribución.

NOTA

Debido a restricciones de patente, no asumas que es legal usar el código en JBIG-KIT, o cualquier otra implementación JBIG, a menos que se hayan obtenido los acuerdos de licencia apropiados.

El autor de JBIG-KIT, Markus Kuhn, puede ser contactado en:

   mskuhn@cip.informatik.uni-erlangen.de
   http://wwwcip.informatik.uni-erlangen.de/user/mskuhn

Información y discusiones sobre JBIG también se pueden encontrar en USENET en el grupo de noticias comp.compression.research y en la lista de FAQ para comp.compression, encontrada en los grupos de noticias news.answers, comp.answers, y comp.compression y en el CD-ROM que acompaña este libro.



Compresión ART

ART es un esquema de compresión propietario diseñado y promovido por Johnson-Grace, una firma de desarrollo de software fundada en 1992 por Steve Johnson y Chris Grace. Johnson-Grace desarrolla herramientas de software tales como navegadores Web para servicios en línea y usuarios finales.

Fundamentos de ART

Como con JPEG, el grado de compresión en ART es ajustable, y las tasas de compresión mayores tienen pérdidas. También hay un modo sin pérdida. Johnson-Grace está anunciando comercialmete el ART como un compresor de múltiples propósitos al mercado en línea y espera adaptarlo para soportar audio, animación, y video de movimiento completo en el futuro. Como tal, competirá directamente con códecs como el Indeo de Intel y el paquete codificador/decodificador de Cinepak y Microsoft. Johnson-Grace también planea soportar el intercalado de texto, gráficos, audio y video en el futuro.

Johnson-Grace afirma que ART proporciona tasas de compresión que son típicamente tres veces más pequeños que ya sea JPEG o GIF. Esto por supuesto, sería una bendición para la comunidad en línea si la compresión fuera comparable a la de GIF, por ejemplo. La documentación de Johnson-Grace sugiere que el navegador web de America Online, TurboWeb, soporta imágenes comprimidas con ART.

Si bien los detalles del algoritmo se mantienen secretos, Johnson-Grace ha publicado alguna información descriptiva. El algoritmo busca analizar una imagen e identificar un número de características clave, tales como color, ruido, esquinas y características repetitivas, las cuales son luego priorizadas por la contribución relativa de cada cacterística a la calidad de la imagen. El motor de priorización usa lo que Johnson-Grace llama lógica difusa (fuzzy logic) para clasificar y priorizar características de la imagen que está siendo comprimida. Características respectivas se identifican y son enlazadas en la imagen usando un método propietario. Los componentes de la imagen son cuantizados, y las características de baja prioridad se ignoran. Como con JPEG, el grado de pérdida de información aumenta con el grado de compresión y se compensa por el grado de redundancia de una tasa de compresión particular.

ART aparentemente usa una variedad de métodos de compresión conocidos, incluyendo compresión de wavelet, para optimizar la compresión de los datos. Presumiblemente, el algoritmo de compresión usado se corresponde a la profundidad de pixeles de la imagen que está siendo comprimida, porque Johnson-Grace afirma competir tanto con GIF (256 colores) y JPEG (color de 24 bits). Johnson-Grace afirma que las imágenes comprimidas con ART tienen típicamente menos de 10K de tamaño, lo cual mejora lo que ellos llaman "velocidad a la pantalla".

Las imágenes comprimidas con ART pueden estar por capas, lo que significa que pueden transmitirse por etapas sobre líneas de módem de ancho de banda bajo, y pueden ofrecer despliegue de imágenes casi inmediato, aunque de bajoa calidad, en el dispositivo de visualización del cliente. La calidad de la visualización entonces mejora a medida que el resto de la información se recibe y se renderiza progresivamente.

Las imágenes se comprimen con el kit the herramientas ART llamado ART Press (MAC ART Tools en la Macintosh). Johnson-Grace estuvo distribuyendo el kit de herramientas ART gratuitamente hasta el final de 1995. Los precios no habían sido fijados a la fecha de esta edición.

Tecnológicamente, el esquema de compresión ART representa un paso hacia adelante en inteligencia y se augura bien para el futuro de la compresión. Los resultados superiores se obtienen al corresponder la tecnología de compresión apropiada con la imagen a comprimir. Aún queda por verse si Johnson-Grace será capaz de popularizar su sistema en su comunidad dirigida online:

Para Mayor Información Sobre ART

Para mayor información, contacta:

Johnson-Grace
2 Corporate Plaza
Newport Beach CA 92660-7929
Voice: 714-759-0700 x245
FAX: 714-729-4643

Johnson-Grace también tiene un sitio Web, y puedes encontrar mayor información en:

   http://www.jgc.com/cpi/art/
   http://www.jgc.com/cpi/art/artcomp.html
   http://www.jgc.com/freedemo/



Compresión Fractal de Imagen

La codificación fractal es un proceso matemático usado para codificar mapas de bits que contienen una imagen del mundo real como un conjunto de datos matemáticos que describen las propiedades fractales de la imagen. La codificación fractal depende del hecho de que todos los objetos naturales, y la mayoría de objetos artificiales, contienen información redundante en la forma de patrones similares y repetitivos llamados fractales.

Fundamentos de Fractales

Un fractal es una estructura que está conformada de formas y patrones similares que ocurren en muchos tamaños diferentes. El término fractal fue usado por primera vez por Benoit Mandelbrot para describir patrones repetitivos que el observó ocurrir en muchas estructuras diferentes. Estos patrones parecían casi idénticos en forma a cualquier tamaño y ocurrían naturalmente en todas las cosas. Mandelbrot también descubrió que estos fractales podrían describirse en términos matemáticos y podrían crearse usando algoritmos y datos muy pequeños y finitos.

Veamos un ejemplo del mundo real. Si miras la superficie de un objeto tal como el piso actualmente debajo de tus pies, notarás que hay muchos patrones repetitivos en su textura. La superficie del piso puede ser de madera, concreto, losas, carpeta, o incluso suciedad, pero aún contiene patrones repetitivos que van de tamaños muy pequeños a muy grandes.

Si hacemos una copia de una pequeña parte de la superficie del piso y lo comparamos a todas las demás partes del piso, encontraríamos varias áreas que son casi idénticas en apariencia a nuestra copia. Si cambiamos la copia ligeramente al escalarla, rotarla, o reflejarla como en espejo, podemos hacerla corresponder con más partes del piso. Una vez que se encuentra una correspondencia, podemos ya sea crear una descripción matemática de nuestra copia, incluyendo cualquier alteración que hayamos hecho, y podemos almacenarla, y la ubicación de todas las partes del piso con las que se corresponde, como datos.

Si repetimos este proceso para el piso completo, terminaremos con un conjunto de ecuaciones matemáticas llamadas códigos fractales que describen la superficie entera del piso en términos de sus propiedades fractales. Estas ecuaciones matemáticas pueden entonces usarse para recrear una imagen en el piso entero.

El proceso ilustrado en este ejemplo es muy similar en concepto a los gráficos vectoriales (2D) y 3D, en donde se almacenan descripciones matemáticas de los objetos, en lugar de imágenes en cuestión de los objetos. La diferencia importante entre los gráficos vectoriales y los fractales es que las descripciones fractales se derivan de patrones ecofactuales reales encontrados en objetos del mundo real, mientras que los objetos vectoriales y 3D son estructuras generadas puramente de forma artificial que no contienen naturalmente patrones fractales.

La codificación fractal es ampliamente usada para convertir imágenes de mapa de bits a códigos fractales. La decodificación fractal es simplemente lo contrario, en donde un conjunto de códigos fractales se convierten a un mapa de bits.

El proceso de codificación es extremadamente intensivo computacionalmente. Se necesitan millones o billones de iteraciones para encontrar los patrones fractales en una imagen. Dependiendo de la resolución y los contenidos de los datos de entrada de mapa de bits, y la calidad de la salida, tiempo de compresión, y parámetros de tamaño de archivo seleccionados, comprimir una imagen individual podría tomar de unos pocos segundos a unas pocas horas (o más) incluso en una computadora muy rápida.

Decodificar una imagen fractal es un proceso mucho más simple. El trabajo duro fue efectuado al encontrar todos los fractales durante el proceso de codificación. Todo lo que el proceso de decodificación necesita hacer es interpretar los códigos fractales y traducirlos a una imagen de mapa de bits.

Actualmente, el método más popular de codificación fractal es un proceso llamado la Transformada Fractal creada en 1988 por Michael F. Barnsley de Iterated Systems. La transformada de Barnsley fue el primer algoritmo práctico usado para describir matemáticamente una imagen de mapa de bits del mundo real en términos de sus propiedades fractales.

Dos beneficios tremendos son inmediatamente visibles al convertir imágenes de mapa de bits convencionales a datos fractales. La primera es la habilidad de escalar cualquier imagen fractal a un tamaño mayor o menor sin la introducción de artefactos de imagen o una pérdida en los detalles que ocurre en las imágenes de mapa de bits. Este proceso de "zooming fractal" es independiente de la resolución de la imagen de mapa de bits original, y el zooming está limitado solo por la cantidad de memoria disponible en la computadora.

El segundo beneficio es el hecho de que el tamaño de los datos físicos usados para almacenar los códigos fractales es mucho menor que el tamaño de los datos originales del mapa de bits. De hecho, no es raro para las imágenes fractales alcanzar tamaños 100 veces menores que sus fuentes de mapa de bits. Es este aspecto de la tecnología fractal, llamado compresión fractal, que ha promovido el máximo interés dentro de la industria de imágenes de computadora.

La compresión fractal tiene pérdidas. El proceso de corresponder fractales no involucra buscar correspondencias exactas, sino buscar las correspondencias "que mejor se ajustan" basándose en los patrones de compresión (tiempo de codificación, calidad de imagen, y tamaño de la salida). Pero el proceso de codificación puede controlarse al punto en donde la imagen "no tiene pérdidas visuales". Es decir, no deberías poder ser capaz de notar dónde se perdieron los datos.

La compresión fractal difiere de otros métodos de compresión con pérdida, tales como JPEG, en un número de maneras. JPEG logra la compresión al descartar datos de imagen que no se requieren por el ojo humano para percibir la imagen. Los datos resultantes se comprimen adicionalmente usando un método sin pérdida de compresión. Para lograr tasas de compresión mayores, se deben descartar más datos de la imagen, resultando en una calidad de imagen más pobre con una apariencia pixelada (de bloques).

Las imágenes fractales no están basadas en un mapa de pixeles, ni se pondera la codificación a las características visuales del ojo humano. En su lugar, los datos de mapa de bits se descartan cuando se requiere crear un patrón fractal con la mejor correspondencia. Tasas de compresión mayores se logran usando mayores transformadas computacionalmente intensivas que pueden degradar la imagen, pero la distorsión parece mucho más natural debido a los componentes fractales.

La mayoría de otros métodos con pérdida también son simétricos en naturaleza. Es decir, una secuencia particular de pasos se usa para comprimir una imagen, y se usan los pasos inversos para descomprimirla. La compresión y descompresión también tomará aproximadamente el mismo tiempo. La compresión fractal es un proceso asimétrico, que toma mucho más tiempo en comprimir una imagen que en descomprimirla. Estas características limitan la utilidad de los datos comprimidos fractalmente a aplicaciones donde los datos de imagen son constantemente descomprimidos pero nunca recomprimidos. Por lo tanto, la compresión fractal es altamente adecuada para usarse en bases de datos de imagen y en aplicaciones de CD-ROM.

El contenido y la resolución de los mapas de bits fuente puede afectar grandemente la compresión. Las imágenes con un alto contenido fractal (por ejemplo, rostros, paisajes, y texturas intrincadas) resultan en tasas de compresión mucho más altas que las imágenes con un contenido fractal bajo (por ejemplo, gráficos —charts—, diagramas, texto, y texturas planas). Las imágenes de alta resolución pueden comprimirse para lograr tasas de compresión mayores y aún retendrán una alta calidad de imagen. Para retener una alta calidad para imágenes de menor resolución, la tasa de compresión será mucho más baja. Las imágenes con una gran profundidad de bits (tales como imágenes de color verdadero de 24 bits) también se comprimirán más eficientemente que imágenes con menos bits por pixel (tales como imágenes de escala de grises de 8 bits).

El proceso de compresión fractal no está de ninguna manera en el dominio público. Hay muchas patentes que reclaman un método de compresión de datos de imagen basándose en transformadas fractales. Además, el proceso exacto usado por algunos paquetes fractales —incluyendo la Transformada Fractal de Barnsley— se considera propietario.

Para Mayor Información Sobre Compresión Fractal

Una gran cantidad de información sobre la compresión fractal está disponible tanto en la WWW como en tu librería técnica local. En la Web, los siguientes sitios te proveerán con bastante material de lectura y con enlaces a otros sitios que contienen información de fractales:

http://links.waterloo.ca/
   Waterloo fractal compression page

http://inls.ucsd.edu/y/Fractals/
   Yuval Fisher's fractal image compression page

http://www-rocq.inria.fr/fractales/
   Groupe Fractales

http://spanky.triumf.ca/
   The Spanky Fractal Database

ftp://ftp.informatik.uni-freiburg.de/documents/papers/fractal/
   Dietmar Supe's FTP site for fractal papers

Paquetes de software fractal en Internet incluyen:

http://www.iyu.fi/~kuru/fractalCompression/
   RGB fractal compression tools

http://nic.funet.fi/pub/textonly/packages/fractal/fractal-2.0.tar
   Yuval Fisher's fractal decompression code

Información sobre codificación fractal también puede encontrarse en los grupos de noticias de USENET sci.fractals, comp.compression y sci.math.

El documento técnico "Fractal Image Compression", SIGGRAPH '92 Course Notes, es una muy buena introducción a la compresión fractal y está disponible como un documento PostScript en:

   ftp://nic.funet.fi/pub/textonly/packages/fractal-image-compression/

Hay muchos libros sobre fractales y compresión fractal. Probablemente el mejor para darle impulso a un programador en la tecnología fractal es:

Yuval Fisher, ed., Fractal Image Compression: Theory and Application to Digital Images, Springer Verlag, New York, 1995.

Este libro es una colección de artículos sobre codificación fractal que incluye una introducción no matemática a la compresión fractal, descripción de módemos para el proceso de codificación y decodificación, y código fuente de C de un codificador y decodificador fractal.

Los siguientes libros también contienen resúmenes muy buenos sobre la tecnología fractal:

Barnsley, Michael F., Fractals Everywhere, second edition, Academic Press, San Diego, 1993.

Barnsley, Michael F., The Desktop Fractal Design System Versions 1 and 2, second edition, Academic Press, San Diego, 1992.

Barnsley, Michael F., and Lyman P. Hurd, Fractal Image Compression, AK Peters Limited, 1993.

Puede que también quieras mirar el texto original de Mandelbrot:

Mandelbrot, Benoit B., The Fractal Geometry of Nature, WH Freeman & Co., New York, 1983.

Los siguientes artículos de periódico también son recomendados:

Anson, L.A., "Fractal Image Compression," Byte Magazine, October 1993.

Sloane, M.F and A.D., "A Better Way to Compress Images," Byte Magazine, January 1988.

McGregor, D.R., R.J. Fryer, P. Cockshott, and P. Murray, "Fast Fractal Compression," Dr. Dobb's Journal, vol. 21, no. 243, January 1996.

Iterated Systems produce la aplicación de imágenes fractales Images Incorporated. Esta aplicación soporta la codificación y decodificación de imágenes fractales de más de 20 diferentes formatos de archivos de mapa de bits. Iterated también vende una librería de rutinas fractales que puedes incorporar directamente en tus propios programas. Puedes contactar Iterated Systems en:

Iterated Systems, Inc.
3525 Piedmont Road
Seven Piedmont Center, Suite 600
Atlanta GA 30305-1530
Voice: 800-437-2285
Fax: 404-264-8300 (sales)
Email: support@iterated.com (soporte técnico)
WWW: http://www.iterated.com/

Dos documentos a leer son la FAQ Fractal de Iterated Systems en:

 http://www.iterated.com/nfaq.htm

y el documento Bienvenido a los Fractales e Imágenes en:  http://www.iterated.com/nwelbook.htm

El sitio Web de Iterated Systems también proporciona mucha información útil, incluyendo los reclamos de patentes sobre la tecnología fractal y el formato Fractal Image File (FIF).



Para Mayor Información Sobre Compresión de Datos

En USENET, el artículo FAQ del grupo de noticias comp.compression provee una fuente útil de información sobre una variedad de diferentes métodos de compresión. También incluye información sobre muchos programas de archivamiento (pkzip, lzh, zoo, etc.) y patentes pertenecientes a algoritmos de compresión. Esta FAQ está incluida en el CD-ROM que acompaña este libro; sin embargo, ya que la FAQ se actualiza frecuentemente, la versión del CD-ROM debería usarse solo para información general. Puedes obtener la última versión de esta FAQ desde el grupo de noticias news.answers en:

   ftp://rtfm.mit.edu/pub/usenet/comp.compression/compression-faq

en donde se mantiene en tres partes: part1, part2, y part3. Esta FAQ también puede obtenerse enviando email a:

   mail-server@rtfm.mit.edu

con el mensaje

   send usenet/comp.compression/compression-faq/part1
   send usenet/comp.compression/compression-faq/part2
   send usenet/comp.compression/compression-faq/part3

en el cuerpo.

Hay muchos libros sobre codificación de datos y compresión. La mayoría de libros más antiguos contienen solo descripciones matemáticas de los algoritmos de codificación. Algunos libros más nuevos, sin embargo, han tomado la moda altamente deseable de incluir ejemplos de código C funcional (eso esperamos) en su texto e incluso hacer que los ejemplos de código estén disponibles en línea o en disco.

Las siguientes referencias contienen buenas discusiones generales de muchos de los algoritmos de compresión discutidos en este capítulo:

Bell, T.C, I.H. Witten, and J.G. Cleary, "Modeling for Text Compression," ACM Computing Surveys, vol. 21, no. 4, December 1989, p. 557.

Bell, T.C, I.H. Witten, and J.G. Cleary, Text Compression, Prentice-Hall, Englewood Cliffs, N.J, 1990.

Huffman, D.A., "A Method for the Construction of Minimum-Redundancy Codes," Communications of the ACM, vol. 40, no. 9, September 1952, pp. 1098-1101.

Jain, Anil K., Paul M. Farrelle, and V. Ralph Angazi, Image Data Compression: Digital Image Processing Techniques, Academic Press, San Diego, CA, 1984, pp. 171-226.

Lelewer, D.A, and D.S. Hirschberg, "Data Compression," ACM Computing Surveys, vol. 19, no. 3, September 1987, p. 261.

Storer, James A., Data Compression: Methods and Theory, Computer Science Press, Rockville, MD, 1988.

Storer, James A., ed., Image and Text Compression, Kluwer Books, Boston, MA, 1992.

Williams, R., Adaptive Data Compression, Kluwer Books, Boston, MA, 1990, pp. 30-44.

 n0HCo(-JT' &N5i5詗7c'wOưQ|c!@|%A"@[0d1̖Y'zb,5͔Ow( 2+FcI`Fqlzv(7LX rfYvNzzYOA#.E-94Zn!S 52@K9my;.}U݀r&jn2WWHJ`Q}u_tro {rWL;=_ؼ