Java Run Length Encoding – (RLE), Algorítimo de compressão de dados

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.