Universidade Federal do Paraná Setor de Tecnologia

Departamento de Engenharia Elétrica

Disciplina: Processamento Digital de Sinais.

Nilson Teixeira de Lima Jr                GRR20033150

2007

 

Introdução

Uma vez que a quantidade de transmissão de dados de qualquer tipo sejam eles músicas, textos, imagens ou vídeos, teve um grande aumento nos últimos anos não ficou difícil prever que isso representaria um problema a ser resolvido. Por se tratar de dados com uma grande diversidade, sendo eles provindos de uma grande e crescente quantidade de pessoas, para os mais variados fins, tanto a manipulação, o armazenamento e a transmissão desses dados ficou comprometida.

Isto porque tais necessitam de uma quantidade considerável de dados para serem representados, e consequentemente, certa largura de banda também grande, se faz necessário para a transmissão desses dados. Dessa forma, como não se fazia possível a não transmissão desses dados, nem a diminuição do fluxo por parte dos usuários, a solução acabou sendo a diminuição do tamanho dos dados a serem transmitidos. Tal diminuição, conhecida como compressão de dados, permitiu que as informações dos dados ocupassem um espaço considerado aceitável para armazenamento em um disco rígido, ou outro dispositivo de memória não volátil, como também serem transmitidas em rede em taxas razoáveis. Certamente que o compartilhamento de imagens, sons, vídeos e todo o design da internet seria muito diferente sem os  algoritmos desenvolvidos para a compressão de dados.

Neste processo de compressão, como já citado, o objetivo é reduzir a quantidade de dados que se fazem necessários para representar a imagem digital em questão (ou outro tipo de arquivo). No entanto a redução por si só não representa grande desafio, pois o que se considera é ideal é a redução do tamanho em conjunto sem a perda de qualidade da imagem original. Para tanto a redução se ocupa com a remoção de dados redundantes presentes na imagem original, processo feito antes do armazenamento definitivo ou da transmissão da imagem.

Existem vários algoritmos de compressão que lidam com imagens, entre eles JPEG, GIF, PNG, etc. O JPEG (Joint Photographic Experts Group) se caracteriza como sendo um dos algoritmos de compressão mais populares e bem sucedidos da atualidade, sendo que seu sistema de compressão tem por base a Transformada Discreta do Coesseno (DCT - Discrete Cosine Transform). Este será o algoritmo focado neste trabalho.

 

Princípios de Compressão - Redundância de Dados

A redundância baseia-se, como o próprio nome sugere, na existência de dados que não são vitais para a transmissão de uma mesma informação, o que impacta diretamente na quantidade de dados utilizados. Alguns tipos de redundância existentes são:

Redundância de codificação (entrópica): acontece quando os níveis de cinza presentes em uma imagem são codificados com mais símbolos do que seria necessário. Por exemplo, considerando que o símbolo necessário é 2. Em um sistema de oito bits tal representação seria “00000010”, no entanto são apenas necessários dois bits (10), os demais bits são redundantes e podem ser eliminados.

Redundância interpixel ou redundância espacial: ocorre quando os pixels vizinhos em uma imagem são muito parecidos ou iguais. Ou seja, são correlações das relações geométricas ou estruturais dos objetos na imagem. Uma forma de lidar com esta redundância é utilizar uma representação diferencial, utilizando dessa forma menos bits por pixel para representar certa área da imagem.

Redundância espectral: existente em imagens que possuem mais de uma faixa espectral, pois é freqüente haver uma correlação entre os valores espectrais em uma mesma posição da matriz de pixels de cada uma das bandas. Uma técnica que permite remover essa redundância é a geração por componentes principais, a qual produz um novo conjunto onde as informações presentes em bandas individuais não se repetem em outras.

Redundância psicovisual: o olho humano não possui a mesma percepção para com as diferentes informações visuais. Algumas possuem mais importância do que as outras, em um exemplo, o sistema visual humano é mais sensível às informações de brilho do que de cor. Sendo assim, as informações que se apresentam menos importantes ao olho humano são ditas psicovisualmente redundantes e podem ser removidas sem mudanças notáveis na qualidade da imagem. No caso citado acima não se faz necessário representar o brilho e as cores com a mesma quantidade de dados, sendo que a relação entre as componentes de cores (YCbCr) não precisa ser 1:1:1, e sim 4:2:2 ou 4:2:0.

Como a remoção dos dados psicovisualmente redundantes é uma perda de informação (comumente denominada quantização), e como esse tipo de operação é irreversível, a quantização é tida como uma técnica de compressão de dados com perda, uma vez que parte da informação visual é perdida.

 

Métodos de Codificação de Imagem

Também conhecidos como modos da imagem, ou modos de cor da imagem, descrevem como os pixels desta estão organizados. Seguem os principais:

RGB (24bits): é um sistema que utiliza três cores por pixels, comportando assim até 16,7 milhões de cores. Cada cor tem sua representação feita em 8 bits (1 byte), podendo ter assim 256 valores de cores. Nessa representação o (0,0,0) de R, G e B corresponde ao preto, enquanto que o (255,255,255) corresponde ao branco. R, G e B são tidas como cores primárias e o sistema se baseia na combinação aditiva destas.

CMYK (32bits): este sistema usa quatro cores por pixel. Igual ao RGB cada cor também é representada por 8 bits com um total de 256 variações. No entanto o CMYK tem como base a qualidade da luz absorvida por essas cores quando impressas em um papel. Os valores de CMYK representam as porcentagens de cada “tinta” que seria depositada no papel. Ao contrário do RGB o valor 0 % corresponde ao branco e o 100% ao preto. Por ocupar 1 byte a mais por pixel, ele ocupa 33% mais espaço do que o RGB.

Escala de Cinza (8 bits): é um sistema que usa um byte por nível (256 níveis de cinza por pixel). Igual ao RGB, o 0 equivale ao preto e 255 ao branco. Modo recomendado para o armazenamento de imagens preto e branco guardando tons contínuos.

Preto e Branco(1bit): modo conhecido como Bitmap, onde cada pixel é representado um único bit. O valor 0 corresponde ao preto e o 1 ao branco. Aplicativos costumam possuir quatro modos de conversão preto e branco: linha artística (Threshold de 50%), difusão de erro, ordenado e meio-tom. Dentre todos os modos de cores, é o que resulta na imagem de menor tamanho.

Cor Indexada (1 a 8 bits): conhecido como modo 256 cores. Nele, cada pixel assume um valor de cor em uma paleta de 256 cores. As paletas podem ser customizadas na maior parte dos aplicativos, criando novas amostras a partir das imagens a serem convertidas.

 

Técnicas de Compressão

Basicamente a compressão de dados é uma codificação de um grupo de informação de forma que o código gerado pelo processo seja menor do que o código fonte (original). Ou seja, considerando o dado de entrada como sendo X, passando por um processo de codificação (H), o resultado final do processo (Y), deve ter menos bits do que X, levando em conta que o resultado Y reconstruído deve ser o mais próximo possível de X. Para tanto existem praticamente dois tipos de codificação (ou algoritmo), os sem perda e ou com perda de informação.

Os codificadores sem perda de informação (lossless), também conhecidos como codificadores universais ou compactadores de imagem, possuem a característica de manter a integridade da informação codificada (Y é igual a X), possuindo taxas de compressão menores do que os com perda, devido ao limite entrópico do conjunto de dados. A entropia do conjunto de dados pode ser definida como a quantidade real de informação presente no conjunto de dados codificado em relação ao original.

Já os codificadores com perda de informação (lossy), conhecidos como quantizadores, pois os dados da imagem original são submetidos a um processo de quantização, possuem taxas maiores de compressão ao custo da perda de fidelidade da informação, uma vez que Y não será igual a X, e sim uma aproximação.

Existem vários tipos de técnicas utilizadas para remover as redundâncias citadas, cada qual adequada para a sua aplicação. A compressão JPEG por sua vez se destaca pelas altas taxas de compressão que obtêm, mantendo uma boa qualidade de imagem. Como já citado, a compressão JPEG utiliza a Transformada Discreta do Cosseno, a qual possui como ponto forte a fácil implementação e a capacidade de reduzir a redundância espectral dos pixels da imagem.

Em qualquer compressão por transformada, é utilizada uma transformação linear inversível no mapeamento da imagem para um conjunto de coeficientes, que por sua vez sofrem um processo de quantização e codificação. Em grande parte das imagens muitos dos coeficientes destas possuem pequena magnitude, podendo ser removidos sem notável distorção da imagem. Assim sendo o processo de transformada tem por fim descorrelacionar os pixels da imagem, ou seja, reduzir a informação na menor quantidade possível de coeficientes, removendo os que apresentam pouca informação. Para finalizar, os coeficientes quantizados são codificados (no caso da compressão JPEG a codificação de Huffman ou a codificação aritmética). Vale ressaltar que a taxa de compressão é alcançada devido à quantização dos coeficientes e não devido à transformada.

 

 

Quantização

Ao se realizar a transformada do cosseno em uma imagem, a matriz de pixels desta que originalmente era composta de elementos inteiros, possui agora coeficientes reais. Para se reduzir adequadamente esses coeficientes reais é aplicada a quantização, que nada mais é do que o processo de um valor real reduzido em sua precisão para se tornar um valor inteiro. Devido a essa redução, que causa a modificação dos coeficientes, mais detalhadamente na precisão destes, que ocorre a perda de informação.

A quantização é realizada através de uma matriz de quantização que vai reduzir  a precisão de cada elemento da matriz dos coeficientes da imagem. Cada elemento desta é divido pelo elemento correspondente da matriz de quantização e o resultado é arredondado para o inteiro mais próximo.

Na compressão JPEG é utilizada um matriz de quantização Q[i,j] a qual gera um nível estável e considerado bom de compressão. A seguinte expressão exemplifica uma matriz desse tipo:

Q[i, j] = 1 + (1 + i + j) * fator_de_quantização (1)

Sendo que o fator_de_quantização varia entre 2 a 25 e os índices iniciam no zero. Vale notar que essa não é a única possibilidade presente para a criação dessa matriz de quantização.

Como a matriz dos coeficientes reais será divida pela matriz de quantização fica claro que ao aumentar o valor do fator_de_quantização as perdas serão maiores, pois maior será o coeficiente divisor. À medida que o fator_de_quantização fica muito grande (por exemplo, valores maiores que 25 no exemplo dado) será possível notar grande perda de qualidade e deformação da imagem reconstruída. Essa quantização é realizada por zona, ou seja, os coeficientes de altas freqüências são quantizados de forma diferente dos de baixa freqüência, nesse caso, com maior severidade.

Feita a quantização os coeficientes obtidos são reordenados em ziguezague, indo da posição inicial até a final da matriz (considerando um padrão de matriz JPEG 8x8, a posição inicial será (0,0) e a final (0,7) ) para que assim a codificação seja mais eficiente, pois um número maior de coeficientes nulos serão alcançado numa mesma varredura.

 

 

Codificação de Huffman

A codificação de Huffman é uma técnica de compressão a qual faz uso da probabilidade de ocorrência dos símbolos no determinado conjunto de dados que irá sofrer a compressão, para a definição dos códigos de tamanho variável para cada símbolo. Ele foi desenvolvido em 1952 por David A. Huffman.

Tendo as probabilidades de ocorrência dos símbolos, e a partir da junção dos dois símbolos que possuem menor probabilidade, que são somados em símbolos auxiliares e estes tomando parte no conjunto de símbolos, a árvore de Huffman (uma árvore binária completa) é recursivamente formada. O processo é finalizado quando todos os símbolos foram unidos na forma de símbolos auxiliares, resultando assim na árvore binária. Essa árvore então é percorrida, e para cada uma de suas arestas um valor binário (1 ou 0) é atribuído, gerando os códigos a partir desse percurso.

Em termos aproximados, a codificação de Huffman produz uma redução de 25% no tamanho de arquivos de imagem, sendo que pode aumentar até 60% em casos de imagens com pouca variação nas suas cores e tons. Os melhores desempenhos da codificação de Huffman acontecem quando as probabilidades de ocorrência dos símbolos são potências negativas de dois. Outra vantagem da codificação Huffman é que a codificação gerada não é ambígua, afinal nenhum código pode ser o prefixo de qualquer outro código.

 

 

Transformada Discreta do Cosseno (DCT)

De forma resumida a Transformada Discreta do Cosseno converte um bloco de pixels em uma matriz de coeficientes, fazendo a descorrelação da informação da imagem, transformando nesse processo a imagem do domínio espacial para o domínio da freqüência. Essa descorrelação consiste em separar a imagem em sub-bandas espectrais que possuem importâncias diversas, segundo as redundâncias, como os brilhos e as cores para a sensibilidade psicovisual.

Para ser possível a utilização da DCT em uma imagem antes é necessário dividir a imagem original no formato de blocos. Isso possibilita uma melhor taxa de compressão e uma maior rapidez nos processamento desses dados. Esses blocos podem ser de 4x4, 8x8, 16x16, 32x32 ou 64x64. O padrão para JPEG são blocos de 8x8. O tamanho dos blocos tem grande impacto na taxa de compressão, sendo que quanto maiores os blocos, menor será a taxa de compressão.

Tendo esses blocos em mãos, os coeficientes iniciais destes (já transformados), guardam as informações vitais da imagem, portanto deve-se garantir que certo número de coeficientes de baixa posição sejam armazenados. Como a DCT fornece uma série de cossenos (convergentes), os coeficientes diminuem em amplitude à medida que os índices aumentam. Devido a isso que se torna possível quantizar os coeficientes por zona, descartando os menos significantes e conseguindo o principal ganho na taxa de compressão.

Tomando o padrão de um bloco de 8x8 para uma compressão JPEG, o primeiro passo é amostrar os valores da imagem, representando-os em 8 bits, o que corresponde a uma faixa de valores variando de 0 a 255 (2⁸). Somado a isso o JPEG necessita que os valores mínimo e máximo sejam deslocados de 128 bits, ou seja, ao invés de começar em 0 e terminar em 255, começará em -128 e terminará em 127. Tal deslocamento deve ser feito antes da aplicação da transformada, uma vez que esse deslocamento causa a redução de magnitude do primeiro coeficiente da DCT. No entanto, essa redução ocorre apenas no primeiro coeficiente. Vale lembrar que antes de aplicar a reordenação dos coeficientes é necessário reverter esse deslocamento, uma vez feita a transformada inversa da DCT.

A DCT é definida por:

 

A Transformada Inversa do Cosseno é dada por:

A forma matricial da DCT pode ser obtida através da fórmula T = MVM^T e sua inversa pela V = M^TTM, sendo V o bloco considerado (8x8) e M uma matriz de cossenos (Figura 1). Através da fatoração de M (possível devido a suas simetrias) é possível otimizar o cálculo da DCT, reduzindo de 120 operações para 40 operações, ou seja, três vezes menos.

 

 

Compressão JPEG

O padrão JPEG foi desenvolvido pelo ISO/IEC em colaboração com a ITU-TS, em 1992. A norma que regulariza os algoritmos de compressão desse formato é denominada ISO/IEC 10981-1. Considerada um dos mais eficientes algoritmos de compressão de imagem, o JPEG possui uma taxa média de compressão de 15:1, sendo que pode chegar até a 25:1 sem degradação, dependendo da imagem.

Devido a sua popularização hoje é comum encontra-lo em diversas aplicações, principalmente na internet. Podendo ser implementado em software e hardware, sendo uma técnica que evoluiu além da sua proposta original (imagens) para a compressão de vídeos, através da nomenclatura JPEG tempo-real ou Motion JPEG (MJPEG).

O formato JPEG é comumente usado em fotografias ou outras imagens que possuem tons contínuos, especialmente em documentos HTML da Internet ou outros serviços online. O JPEG suporta os seguintes modos de cores: CMYK, RGB e Grayscale (escala de cinza), porém não suporta os canais alpha. Ao contrário do formato GIF, o JPEG mantém toda a informação sobre cores em uma imagem no modo RGB, mas a compressão é feita através de um descarte seletivo de dados.

Uma imagem JPEG sofre descompressão automaticamente quando aberta, sendo que um alto nível de compressão irá fatalmente resultar em uma imagem de baixa qualidade e vice-versa. Na maior parte dos aplicativos, a escolha de qualidade máxima irá resultar numa imagem de tamanho menor do que a original, porém indistinguível desta.

Uma vez que o JPEG permite ao usuário a seleção da taxa de compressão em relação à qualidade resultante, o que é feito modificando os parâmetros do codificador,  é possível ao JPEG trabalhar com uma grande faixa de qualidade de imagens. Outra meta alcançada por este padrão foi a possibilidade de operação em uma grande gama de computadores, os quais nem sempre possuindo grandes capacidades de processamento. Devido a todas essas exigências houve a criação de quatro modos de operação, sendo eles: seqüencial, progressivo, hierárquico e sem perdas (lossless).

Codificação seqüencial: é um modo com perdas em que cada componente de cor é codificado em uma única varredura, da esquerda para a direita e de cima para baixo. Isso resulta em um bloco de dados comprimido diretamente da imagem, para uma ou mais componentes. Este modo também é chamado baseline por ser um modo básico que deve estar presente em qualquer implementação com JPEG.

Codificação progressiva: outro modo com perdas, baseado em DCT expandida, é um avanço do modo seqüencial. A principal mudança é que neste modo as componentes da imagem são codificadas através de varreduras múltiplas, produzindo uma imagem de maneira rápida e disforme quando a taxa de transmissão é baixa, sendo que ela vai ganhando definição à medida que os demais dados da imagem são recebidos. A grande vantagem nesse processo é que o usuário tem uma idéia do conteúdo da imagem com uma pequena quantidade de dados. O número mínimo de varreduras neste caso é dois, porém, devido a sua complexidade, exige melhores capacidades de processamento do que a codificação seqüencial.

Codificação hierárquica: similar à codificação progressiva, porém neste caso a imagem é subdividida em frames (parcelas da imagem), sendo que uma frame é o conjunto de uma ou mais varreduras. Como no caso anterior, o primeiro frame cria uma versão básica e disforme da imagem, e as frames subseqüentes vão aprimorando a imagem básica. Em termos técnicos se trata de uma codificação piramidal com resoluções espaciais múltiplas. As desvantagens desse método são: a exigência de uma maior capacidade de processamento, maior quantidade de dados transmitidos e uma menor taxa de compressão.

Codificação sem perda: como o próprio nome delata, não há perdas nesse modo, e, portanto o processo de compressão é reversível, sendo que a imagem original será perfeitamente reproduzida. Útil para casos específicos onde se preza a integridade da imagem.

 

 

Algoritmo de Compressão JPEG

O algoritmo JPEG funciona da seguinte forma. Primeiramente a imagem da entrada é decomposta em blocos com tamanho N (padrão 8x8), após isso estes são transformados para o domínio da freqüência, através da DCT. A DCT separa as componentes de alta e baixa freqüência da imagem, sendo que as de alta freqüência podem ser selecionadas e modificadas, dependendo da qualidade a ser alcançada no processo.

O padrão JPEG explora as limitações da sensibilidade visual humana para conseguir boas taxas de compressão, uma vez que o olho humano responde de maneira diversa dependendo da freqüência das componentes da imagem. Uma vez que o olho humano é menos sensível às componentes de alta freqüência, estas podem ser  removidas ou reduzidas sem apresentar modificações visíveis na imagem resultante. Devido à seletividade que o JPEG apresenta dependendo da taxa de compressão escolhida pelo usuário a quantidade de componentes de alta freqüência que serão desprezados.

Um sinal discreto contendo 64 pontos (um por pixel) após ser transformado se torna uma função com duas dimensões espaciais, x e y. Os coeficientes dessa função são chamados de coeficientes DCT, ou também de freqüências espaciais. Com um bloco padrão 8x8 esses coeficientes terão seus valores próximos de zero e, portanto, não apresentam necessidade de modificação. Uma vez terminada essa etapa do processo de compressão, os coeficientes DCT são quantificados por valores contidos em uma tabela de quantificação, especificada pela taxa de compressão.

O processo de quantificação reduz a amplitude dos coeficientes que apresentam redundâncias, não afetando de maneira prejudicial a imagem resultante. Essa redução termina por aumentar o número de coeficientes nulos.

Passada a quantificação, os coeficientes DCT são ordenados em uma seqüência zig-zag (Figura 2), podendo assim ser obtida uma seqüência unidimensional dos dados que serão utilizados na codificação por entropia. Uma varredura em zig-zag é posteriormente realizada, pois dessa forma, os coeficientes ordenados apresentarão uma ordem crescente de freqüência espectral, ou seja, os coeficientes de alta freqüência (canto direito inferior) terão os valores mais próximos de zero do que os de baixa. Tal fato aumenta a eficiência da codificação por entropia.