O que é RLE?
RLE é um algorítimo de compressão de dados que é suportado pela maioria dos formatos de arquivos de bitmap, como TIFF, BMP e PCX. Esse algorítimo é adequado para comprimir qualquer tipo de dados, independente do seu conteúdo de informação, mas o conteúdo dos dados irão afetar a taxa de compressão conseguindo RLE. Embora a maioria dos algorítimos de RLE não poderem alcançar as altas taxas de compressão porem exitem outros métodos mais avançados.
Funcionamento:
Ele funciona reduzindo o tamanho físico de uma sequência de repetição de caracteres. Esta cadeia de repetição, chamada de corrida, é normalmente codificados em dois bytes. O primeiro byte representa o número de caracteres na corrida e é chamado de contagem de prazo. Na prática, uma execução codificada pode conter de 1 a 128 ou 256 caracteres, a contagem de execução geralmente contém, como o número de caracteres menos um (um valor na gama de 0 a 127 ou 255). O segundo byte é o valor do caractere na corrida, que é na faixa de 0 a 255, e é chamado o valor de execução.
Sem compressão, uma corrida de caráter 15 caracteres A, normalmente, necessitam de 15 bytes para armazenar:
[highlight]AAAAAAAAAAAAAAA[/highlight]
A mesma cadeia após a codificação RLE exigiria apenas dois bytes:
[highlight]15A[/highlight]
O código gerado 15A para representar a cadeia de caracteres é chamado de um pacote RLE. Aqui, o primeiro byte, 15, é a contagem de execução e contém o número de repetições. O segundo byte, A, é o valor de execução e contém o valor repetido real no prazo. Um novo pacote é gerado toda vez que o personagem correr muda, ou cada vez que o número de caracteres no prazo excede a contagem máxima.
Suponha que nossa sequência de 15 caracteres agora contém quatro corridas de personagens diferentes:
[highlight]AAAAAAbbbXXXXXt[/highlight]
Usando a codificação run-length isso poderia ser comprimido em quatro pacotes de 2 bytes:
[highlight]6A3b5X1t[/highlight]
Fonte: fileformat.info
[ads1]
Desafio:
Um simples desafio que me foi proposto durante o terceiro semestre da faculdade pelo Prof. Derig Almeida Vidal, MSc, já a algum tempo, mais que me foi de grande valor e tive que estudar um pouquinho a respeito… e sim acho que consegui a resolução.
Um dos algorítimos mais fáceis para compactar uma imagem é aquele já conhecemos por RLE (Run Length Encoding). Basicamente esse algorítimo percorre uma imagem “bitmap” linha a linha e, se em uma linha ele encontrar dois ou mais bits consecutivos com a mesma cor, lê compacta essa informação escrevendo o número de vezes que o bit foi repetido e em seguida a informação da cor.
Por exemplo, considere que temos uma imagem de 8 por 8 bits, em preto e branco. Uma maneira de representá-la seria por meio de uma matriz 8 x 8, como a figura abaixo:
Os dois únicos valores presentes na Matriz são os números 0 e 1, representando, respectivamente, pixels brancos e pretos da imagem. Observe que existe uma representação de valores 1 e 0 consecutivos em algumas linhas (ou colunas) da matriz. Pode-se também representar essa imagem como um vetor de caracteres, no qual o valor 0 será representado pela letra (B) e o valor 1 pela letra (P). Dessa forma, levando em conta as repetições de cores, pode-se codificar a primeira linha assim: 8B (8 pixels repetidos da cor branca). E a terceira linha desse modo: 1B 1P 4B 1P 1B (1 branco, 1preto, 4 brancos, 1 preto e 1 braco).
Agora surge a dúvida:
Como armazenar a imagem inteira?
Pode-se definir o número (0) como indicador de separação de linhas.
E o fim da imagem?
Utilize dois zeros (00) como marcador de fim da imagem. Então, a imagem pode ser codificada como se fosse o seguinte vetor de caracteres:
[highlight]’8B02B4P2B01B1P4B1P1B01P1B1P2B1P1B1P01P6B1P01B1P1B2P1B1P1B01B1P4B1P1B02B4P2B00′[/highlight]
Desenvolver um algorítimo que leia uma imagem bitmap (valores inteiros 0 e 1) em uma matriz 8 x 8 e que compacte essa imagem em um vetor de tamanho máximo 64, conforme o método discutido anteriormente.
/**
*
* @author Francisco de Assis de Souza Rodrigues
*
*/
public class CompactacaoRLE {
public static void main(String[] args) {
// Variavel ultilizadas.
// Contador Branco.
int B = 0;
// Contador Preto .
int P = 0;
// Contador Linha.
int cont = 0;
// Matriz bidimensional iniciada com a imagem representada pelos bits 0
// e 1.
int imagem[][] = {
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 0, 0, 1, 0 },
{ 1, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 1 },
{ 0, 1, 0, 1, 1, 0, 1, 0 },
{ 0, 1, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 1, 1, 1, 1, 0, 0 }
};
// Loop que percorre as linhas da matriz.
for (int linha = 0; linha < imagem.length; linha++) {
// Loop que percorre as colunas da matriz.
for (int coluna = 0; coluna < imagem[linha].length; coluna++) { // Condição que verifica qual a linha que está sendo lida. if (linha == cont) { // Variavel ValorImagem recebe o valor armazenado na posição // atual. int ValorImagem = imagem[linha][coluna]; // Condição que verifica se o ValorImagem é igual a zero e // se // o contador Preto é maior que zero. if ((ValorImagem == 0) & (P > 0)) {
// Se a condição for Verdadeira Imprime o valor do
// Contador Preto.
System.out.print(P + "P");
P = 0;// Zera o contador Preto.
B++;// Incrementa o contador Branco.
}
// Condição que Verifica se o ValorImagem é igual a zero.
else if (ValorImagem == 0) {
// Se for verdadeira incrementa no contador Branco.
B++;
}
// Condição que verifica se o valor da Imagem é igual a um e
// o contador Branco é mairo que zero.
else if ((ValorImagem == 1) & (B > 0)) {
// Se a condiçao for verdadeira, imprime o valor do
// contador Branco.
System.out.print(B + "B");
B = 0;// Zera contador Branco.
P++;// Incrementa contador Preto.
}
// Condição que verifica se o ValorImagem é igual a um.
else if (ValorImagem == 1) {
// Se a condição for verdadeira incrementa o contador
// Preto.
P++;
}
}
// Se a condição a cima for falsa. (Essa condição é execultada
// quando a condição que verifica linha é falsa).
else {
// Verifica se o contador Branco maior que zero.
if (B > 0) {
// Se a condição for verdadeira, Imprime valor contador
// Branco.
System.out.print(B + "B");
B = 0;// Zera contador Branco.
}
// Verifica se o contador Preto maior que Zero.
else if (P > 0) {
// Se a condição for verdadeira, imprime valor do
// contador Preto.
System.out.print(P + "P");
P = 0;// zera contador Preto.l
}
// Imprime Zero (indicador de separação de linhas).
System.out.print("0");
// Verifica se o valor da posição atual é iqual a zero.
if (imagem[linha][coluna] == 0) {
B++;// Incrementa contador Branco.
}
// Se não
else {
// Incrementa contador Preto.
P++;
}
// Incrementa Contador Linha.
cont++;
}
}
}
// Verifica se Contador Branco maior que zero
if (B > 0) {
// Imprime valor contador Branco.
System.out.println(B + "B");
}
// Verifica se o contador Preto Maior que Zero.
else if (P > 0) {
// Imprime valor contador Preto.
System.out.println(P + "P");
}
// Imprime zero, zero (marcador de fim da imagem).
System.out.println("00");
}
}
Fonte: Livro ALGORITMOS E LOGICA DE PROGRAMAÇÃO
[ads2]
Até a próxima.
Adooooro este site Java Run Length Encoding – (RLE), AlgorÃtimo de compressão de dados | Clube dos Geeks por que existe tantiiiisima coisa lega por aqui.