Señor


Clase 7
RLE (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. Por ejemplo, considera una pantalla quecontiene 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, con N representando las zonas en negro y B las de blanco:
BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBB-
BBBBBBB
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. 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. Elprimer 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 cualtiene la ventaja de utilizar secuencias de cadenas de caracteres. Algunos formatos que utilizan esta codificación incluyen Packbits, PCX, 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 colorde los pixels 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.
Es el método para comprimir señales FAX más simple y más eficiente. Para transmitir una página FAX la máquina escruta la página línea a línea midiendo la intensidad de la luz reflejada en puntos regularmente espaciados a lo largo de cadalínea.
Esto resulta en una secuencia de bits que indican si los puntos en las líneas son negros o blancos: 1 ó 0 respectivamente. Si la máquina de un barrido de 200 líneas por pulgada y mide 200 puntos por línea a lo largo de cada página y si el tamaño de página es 8.5x11 pulgadas, se la representa por 200*200*8.5*11=3.73*106 bits. Con un módem de 9600 bps se tardarían 6,5 minutos en enviarlo.Si lo podemos reducir 20 veces el número de bits se tardarían 20 segundos.
Para alcanzar este factor de compresión la máquina transmite el número de 0s sucesivos entre dos 1s en vez de una larga secuencia de 0s.
Por ejemplo la cadena 10a10b10c10dcon 0i representando i ceros consecutivos se codifica como ABCD donde I es la representación binaria de i. Luego si a=600 entonces A=1001011000 y 600ceros se reemplazan por 10 bits.
El factor de compresión RLE es aproximadamente:



donde X es una Variable Aleatoria Discreta que representa el número típico de ceros sucesivos entre dos unos y E{x} es su valor esperado (media). el factor de compresión es de entre 20 y 30.

Se trata de un método de compresión sin error. Por ejemplo, en imágenes binarias, se puede codificar el número de cerosentre dos unos sucesivos. Es útil cuando hay largas secuencias de ceros. Se suele trabajar con longitudes máximas de ceros de longitud M de forma que, por lo que necesitan m bits para codificar cada patrón con un código de longitud fija.
En el caso de imágenes multinivel, el RLE consigue eliminar la redundancia de repeticiones consecutivas de un mismo color o nivel de gris. El modelo más...