Transmisión de datos EMI

La compresión RLE (Run-Length Encoding) es una compresión relativamente antigua y

muy usada. Se usa frecuentemente en archivos de imágenes como PCX (PiCture
eXchange), PSD (PhotoShop Document), TGA, etc.

Se usa también en muchos juegos debido a la sencillez de su implementación, velocidad

de descompresión y baja memoria temporal necesaria. El algoritmo RLE se usa
conjuntamente con el LZ77 para obtener un algoritmo que se comporta bastante bien con
cadenas con muchos bytes seguidos repetidos y con secuencias repetidas.

Si una señal tiene una alta probabilidad de ocurrencia de uno de sus símbolos, entonces
se procederá a agrupar éste, colocando el valor de ese símbolo seguido del número de
veces que se repite.

A medida que la señal tienda a ser más estable la codificación será más eficiente, ya que
los grupos son más numerosos. Para agruparlos se debe primero definir cuál de los
símbolos se agrupará (en el caso binario el “0” o el “1”), así podemos seleccionar el más
probable para esta agrupación. Luego se debe seleccionar el valor de m, el cual
representa la cantidad de bits utilizados para expresar el número de veces que se repite
el símbolo seleccionado. Para valores pequeños de m, el código se hace ineficiente
cuando los tramos repetidos son grandes, mientras que si este número es muy grande,
se perderán muchos bits transmitidos por el “overhead” introducido.

La compresión RLE o Run-length encoding es una forma muy simple de compresión de

datos en la que secuencias de datos con el mismo valor consecutivas son almacenadas
como un único valor más su recuento. Esto es más útil en datos que contienen muchas
de estas "secuencias"; por ejemplo, gráficos sencillos con áreas de color plano, como
iconos y logotipos.
Transmisión de datos EMI

El código Run-Length Encoding consta de escribir primero el valor del símbolo repetido,
y luego con m bits la cantidad de bits repetidos menos 1 (esto es para aprovechar los m
bits completos). Los otros símbolos se copian en el código de manera normal y directa.

Se puede observar un código Run-Length por agrupación del símbolo “0” y con m=3, de
modo que se pueden agrupar hasta 8 bits:

Para este código la Tasa de Compresión (TC) se define como:

En la ecuación, NCod es el número total de bits en la palabra codificada, mientras que

NOri es el número total de bits en la palabra original.

Para tener una idea de las razones compresión producidas por RLE, consideramos una
cadena de N caracteres, que necesita ser comprimida. Se supone que la cadena contiene
M repeticiones, con una longitud media de L elementos cada una.
Transmisión de datos EMI

Cada una de las M repeticiones, se sustituye por 3 caracteres (el cambio de código, el
contador y el dato), por lo que el tamaño de la cadena comprimida y el factor de
compresión es:

Una variante de la codificación Run-Length Encoding para textos es la codificación de

diagramas. Este método es adecuado cuando el número de elementos distintos del
bloque a comprimir se reduce sólo, a un número limitado de caracteres, por ejemplo
solamente las letras, los dígitos y los signos de puntuación

Por ejemplo, considera una pantalla que contiene texto en negro sobre un fondo
blanco. Habría muchas secuencias de este tipo con píxeles blancos en los márgenes
vacíos, y otras secuencias de píxeles negros en la zona del texto.

Supongamos una única línea (o scanline), con N representando las zonas en negro y
B las de blanco:

BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBB
NBBBBBBBBBBBBBB

Si aplicamos la codificación run-length a esta línea, obtendríamos lo siguiente:

12B1N12B3N24B1N14B

Interpretado esto como 12 letras B, 1 letra N, 12 letras B, 3 letras N, etc. El código

run-length representa el original de 67 caracteres en tan sólo 16.
Transmisión de datos EMI

Esto quiere decir que la línea original pesa 67 bytes y la cadena codificada pesa sólo
16 bytes. Esta codificación traducida a binario, cuyo principio es el mismo, se utiliza
para el almacenamiento de imágenes. Incluso ficheros de datos binarios pueden ser
comprimidos utilizando este método.

El primer byte contiene un número que representa el número de veces que el carácter
está repetido. El segundo byte contiene al propio carácter. En otros casos se codifican
en un solo byte: 1 bit (0 o 1) y 7 bits para especificar el número de caracteres
consecutivos.

Sin embargo, sistemas de compresión más modernos a menudo usan el algoritmo de

deflación u otros algoritmos basados en el LZ77, el cual tiene la ventaja de utilizar
secuencias de cadenas de caracteres.

Algunos formatos que utilizan esta codificación incluyen Packbits, PCX e ILBM.

La codificación run-length realiza una compresión de datos sin pérdidas y es muy

utilizado en imágenes de 8 bits indexadas (en un principio fue utilizado para imágenes
en blanco y negro).

No funciona tan bien en imágenes donde varía constantemente el color de los píxels
como fotografías, aunque JPEG lo utiliza de forma efectiva en los coeficientes que
quedan después de transformar y cuantificar bloques de imágenes.

El método de compresión RLE es utilizado por muchos formatos de imagen (BMP, PCX,
TIFF). Se basa en la repetición de elementos consecutivos.

El principio fundamental consiste en codificar un primer elemento al dar el número de

repeticiones de un valor y después el valor que va a repetirse.

Por lo tanto, según este principio, la cadena “AAAAAHHHHHHHHHHHHHH” cuando está

comprimida da como resultado "5A14H".

La ganancia de compresión es (19-5) / 19, es decir, aproximadamente 73,7%.

Transmisión de datos EMI

Por otro lado, para la cadena "CORRECTLY", donde hay poca repetición de caracteres,
el resultado de la compresión es “1C1O2R1E1C1T1L1Y”. Por lo tanto, la compresión
genera un costo muy elevado y una ganancia de compresión negativa de (9-16) / 9, es
decir, ¡-78%!

En realidad, la compresión RLE está regida por reglas particulares que permiten que se
ejecute la compresión cuando sea necesario y que se deje la cadena como está cuando
la compresión genere pérdida. Las reglas son las siguientes:

Si se repiten tres o más elementos consecutivamente, se utiliza el método de

compresión RLE.

De lo contrario, se inserta un carácter de control (00) seguido del número de

elementos de la cadena no comprimida y después la última.

Si el número de elementos de la cadena es extraño, se agrega el carácter de

control (00) al final.

Finalmente, se definen los caracteres de control específicos según el código:

o un final de línea (00 01)

o el final de la imagen (00 00)

o un desplazamiento de puntero sobre la imagen de XX columnas e YY filas

en la dirección de lectura (00 02 XX YY).

Por lo tanto, no tiene sentido utilizar la compresión RLE excepto para datos con diversos
elementos repetidos de forma consecutiva, en imágenes particulares con áreas grandes
y uniformes.

Sin embargo, la ventaja de este método es que es de fácil implementación. Existen

alternativas en las que la imagen está codificada en bloques de píxeles, en filas o incluso
en zigzag.
Transmisión de datos EMI
Transmisión de datos EMI

Compresión RLE de imágenes

La idea funciona así: sabemos que una imagen en tonos de gris contiene una serie de
números que se repiten, en particular tripletas de pixeles (en sus componentes R, G y B),
los cuales son el mismo color.

Si tenemos regiones en donde se repiten estos valores R, G y B, bien podríamos pensar

en sustituirlos por el byte que hemos leído y un contador que nos indique cuantas veces
se repite el mismo. Esto es básicamente el RLE.

Supongamos que tenemos una imagen de puntos al azar, de todos los posibles tonos de
gris. Si son al azar, probablemente no tengamos secuencias largas de un solo tono de
gris, por lo que por ejemplo, si la imagen original contiene los siguientes bytes (en
hexadecimal):

de de de de de de de de 98 98 98 98 98 98 ff ff 01
Transmisión de datos EMI

Podríamos crear un nuevo archivo que tuviese los siguientes valores:

de 08 98 06 ff 02 01 01

Lo cual nos diría que tendríamos 08 bytes con el valor de, 06 bytes con el valor 98, 2
bytes con el valor ff y finalmente un byte con el valor 01.

Cabe señalar que el esquema RLE bien podría usarse para comprimir no solamente
imágenes, sino cualquier archivo, aunque muchos no son muy susceptibles de sacar
ventaja de la repetición de símbolos.

Por ejemplo, sería mala idea usar RLE para comprimir textos, pues estos no tienen
repeticiones de letras contíguas. Por ende, no es el mejor de los esquemas para archivos
de esa naturaleza.

Los algoritmos básicos de codificación y decodificación son los siguientes

DECODIFICACIÓN:
Transmisión de datos EMI

CODIFICACIÓN RLE:
Transmisión de datos EMI

Nótese que este par de rutinas funcionan con todo el archivo que se desea procesar, lo
cual no necesariamente es la mejor idea. Lo más sensato es usar el “canvas” (en donde
reside la imagen en un eventual software de procesamiento de imágenes) y aplicar RLE
a los pixeles.

De hecho, si se procesa, como en este caso, un archivo completo, estamos intentando

también comprimir el encabezado que muchos formatos gráficos tienen, incluso los
archivos BMP. De nuevo, se advierte que esto es simplemente una idea y el artículo
muestra una primera implementación general para ilustrar lo que hay que hacer.

En pruebas hechas con estos algoritmos se halló que una imagen en tonos de grises (que
contenía simplemente un bloque en un solo tono de gris), que ocupaba originalmente 212
Kbytes, se redujo a 3Kbytes. Para saber el factor de compresión, dividimos (3K / 212K) *
100, lo cual entrega 1.415, es decir, el archivo comprimido ocupa menos del 2% del
archivo [Link] luego, las imágenes cotidianas no son tan buenas para la
compresión. Sin embargo, en casos como en el del ejemplo, es espectacular la
compresión de las imágenes.

Si por ejemplo, usásemos este algoritmo para procesar una imagen en tonos de gris que
están al azar en una imagen, pudiese no tener ni remotamente los resultados
mencionados. Utilizando la siguiente imagen
Transmisión de datos EMI

Hallamos que la compresión llego a 141 KBytes, cuando la imagen original fue de 212
KB. Es decir, 66.50 % de compresión sobre la imagen original.

BIBLIOGRAFIA

 [Link]
 [Link]
codificaciondecodificacion-rle-parte-ii/
 [Link]