Contenido principal
Principios de ciencias de la computación avanzados (AP Computer Science Principles)
Curso: Principios de ciencias de la computación avanzados (AP Computer Science Principles) > Unidad 1
Lección 6: Compresión de datos sin pérdidaCompresión de imágenes sin pérdida
Hay imágenes a todo nuestro alrededor, desde iconos de aplicaciones hasta GIFs animados y fotos. Los archivos de imágenes pueden ocupar mucho espacio, y las computadoras emplean un repertorio de algoritmos para comprimir archivos de imágenes.
Para las imágenes más simples, las computadoras pueden usar un algoritmo de compresión llamado codificación por longitud de secuencias (RLE o run-length encoding).
Bitmaps
Antes de explorar la compresión de imágenes, veamos cómo podemos representar una imagen en binario sin ninguna compresión.
Aquí hay una imagen simple, un icono de corazón de 16x16:
Hagamos un acercamiento y superponemos una cuadrícula encima, de manera que sea fácil ver exactamente cuáles píxeles son rojos y cuáles son blancos:
El icono de corazón consta de solo dos colores, rojo y blanco, así que una computadora puede representarlo en binario con un mapeo de píxeles rojos a 1, y píxeles blancos a 0. Esto se llama un bitmap (mapa de bits), pues mapea píxeles a bits.
Con este método, el icono del corazón se representa así:
1,100,000,110,000
11,110,001,111,000
111,111,011,111,000
1,111,111,111,110,000
1,111,111,111,110,000
1,111,111,111,110,000
1,111,111,111,110,000
1,111,111,111,110,000
111,111,111,111,000
11,111,111,111,000
1,111,111,110,000
111,111,100,000
11,111,000,000
1,110,000,000
100,000,000Imagina que debes leer esos bits para que alguien los copie. Después de un rato, podrías decir cosas como "cinco ceros" en lugar de "cero cero cero cero cero". Pues bien, la computadora también puede hacer eso...
Algoritmo de compresión RLE
En la codificación por longitud de secuencias, la computadora reemplaza cada renglón con números que dicen cuántos píxeles consecutivos son del mismo color, siempre empezando por el número de píxeles blancos.
Por ejemplo, el primer renglón tiene 3 píxeles blancos, 2 píxeles rojos, 5 píxeles blancos, 2 píxeles rojos, luego 4 píxeles blancos:
1,100,000,110,000Esto se representa así:
3,2,5,2,4La cuarta fila es interesante porque empieza con un pixel rojo . En la codificación por longitud de secuencias se inicia con el número de píxeles blancos, así que se representa de esta manera:
0,15,1Descompresión RLE
Cuando una computadora utiliza codificación por longitud de secuencias, debe poder recrear perfectamente la imagen de la representación comprimida, y también podemos, si seguimos la estrategia de la computadora.
Intentemos. Aquí hay una representación con RLE de un icono en blanco y negro:
4, 9, 3
4, 7, 2, 1, 2
4, 7, 2, 1, 2
4, 9, 3
4, 7, 5
4, 7, 5
5, 5, 6
0, 15, 1
1, 13, 2El primer renglón tiene 4 píxeles blancos, luego 9 píxeles negros, luego 3 blancos. Eso se ve así:
El siguiente renglón tiene 4 píxeles blancos, luego 7 negros, 2 blancos, 1 negro y 2 blancos. Así:
Si proseguimos, el icono final es una taza y un plato:
Razón de compresión
Hemos afirmado que la codificación RLE puede ahorrarnos espacio al almacenar imágenes simples, pero ¿cuánto espacio?
Para averiguarlo, escribí un programa para codificar con RLE mapas de bits en blanco y negro. Esta tabla resume los resultados en tres iconos de corazón de tamaño creciente:
| Imagen | Dimensiones | Sin compresión | Con RLE | Ahorro de espacio |
|---|---|---|---|---|
| 16x16 | 256 | 228 | 10.9% | |
| 32x32 | 1024 | 532 | 48.0% | |
| 128x128 | 16384 | 2898 | 82.3% |
Dale un vistazo a la columna final, los ahorros de espacio. ¿Observas un patrón? Ahorramos mucho más espacio a medida que el tamaño aumenta ya que las secuencias son mucho más largas.
¿Qué pasa con imágenes del mismo tamaño? Esta tabla resume los resultados de comprimir tres iconos grandes con RLE:
| Imagen | Dimensiones | Sin compresión | Con RLE | Ahorro de espacio |
|---|---|---|---|---|
| 128x128 | 16384 | 2898 | 82.3% | |
| 128x128 | 16384 | 8298 | 49.4% | |
| 128x128 | 16384 | 8730 | 46.7% |
Ahora puedes ver por qué elegimos un icono de corazón como ejemplo: comprime muy bien, debido a sus múltiples secuencias de blanco o negro. La compresión RLE todavía reduce a la mitad el tamaño de los otros iconos, pero no ahorra tanto espacio.
De hecho, a veces RLE no puede ahorrar nada de espacio...
Límites de RLE
¿Qué pasa con este icono de 16x16?
Hagamos un acercamiento para poder visualizar cada píxel:
Cada píxel en ese icono es de un color diferente, y hay no hay secuencias.
La codificación por longitud de secuencias no puede comprimir en absoluto una imagen como esa. Es un ejemplo que hicimos solo para este artículo (generado con este programa), y puede que no sea muy común.
Resulta que las imágenes fotográficas son similares a ese icono: el mundo real está lleno con detalles que interrumpen las secuencias.
La página del personal de Khan Academy incluye esta linda foto de un perro que mira una pantalla de computadora:
En resolución normal, parece que hay bloques de color similar, como en el pelambre del perro o el gris en la pantalla de la computadora.
Hagamos un acercarniento a los píxeles:
Ahora puedes ver que incluso la aparentemente simple pantalla de computadora es un gran arreglo con una variedad de colores similares pero no iguales. Una codificación por longitud de secuencias de píxeles no hará mucho para reducir el tamaño del archivo.
Usos de RLE
La compresión RLE fue una técnica muy popular cuando la mayoría de las imágenes de la computadora eran iconos con paletas limitadas de color.
En estos días, nuestras imágenes son más complejas y no contienen tantas secuencias del mismo color.
¿Dónde se utiliza RLE actualmente? Las máquinas de fax todavía usan RLE para comprimir los documentos enviados, ya que solo necesitan representar letras en blanco y negro. Las imágenes JPEG utilizan RLE en la fase final de compresión, pero primero utilizan un algoritmo más complejo para comprimir los detalles fotográficos. Eso lo exploraremos pronto.
🙋🏽🙋🏻♀️🙋🏿♂️¿Tienes alguna pregunta sobre este tópico? Nos encantaría contestarte; ¡simplemente pregunta en el area de preguntas abajo!
¿Quieres unirte a la conversación?
Nota: Para la compresión de imágenes se usa la codificación de longitud de secuencias en donde se puede ahorrar espacio observando las secuencias de pixeles en una imagen y con verterlas a numero, mientras mas detallada menos se podrá comprimir.(3 votos)
¿Cómo puedo hacer la cara de perro en pixeles?(2 votos)
Por que si la primera fila del corazon empieza por blanco (0), le ponen 0 (rojo)? Es confuso y no se entiende. Gracias(1 voto)