Trabalho de DSP

A necessidade de um padrão internacional para compressão de imagem estática resultou , em 1986, na formação do Joint Photographic Experts Group (JPEG). O termo Joint (conjunto) refere-se à colaboração entre o CCITT e a ISSO para a formação do grupo. Depois de alguns estudos iniciais, o grupo definiu, em 1988, uma técnica de compressão baseada no Discrete Cosine Transform (DCT). De 1988 a 1990, o comitê JPEG refinou vários aspectos da codificação sem perdas a ser utilizado. Este processo tem a vantagem do fato de que o olho humano é bem mais sensível a pequenas variações na luminosidade do que a pequenas variações de cor, particularmente no final do espectro.

O objetivo do JPEG foi desenvolver um método para compressão de imagens de tons contínuos que atendesse aos seguintes requisitos:

O JPEG pode ser utilizado com imagens de tamanho entre 1x1 pixel a 65535x65535 pixels, onde cada pixel pode ter até 255 componentes de cores. Uma imagem pode ser representada em diferentes sistemas de cores dependendo do número de componentes necessário à sua representação. Para as imagens coloridas usuais, um bom número é 3 e os sistemas mais utilizados são:

YCrCb – componente de luminância e duas componentes de crominância correspondentes ao vermelho e ao azul.

Conforme mencionado anteriormente, o codificador JPEG deve trabalhar com qualquer formato de imagem. Para facilitar a compreensão do algoritmo, consideraremos uma imagem em preto e branco, isto é, composta de tons de cinza. No caso de imagens com mais de uma componente, o algoritmo é aplicado de maneira análoga à cada uma das componentes.

Inicialmente, cada componente de cor é dividida em blocos não sobrepostos de 8x8 pixels. Cada bloco tem seu nível médio subtraído de 128 (offset) de modo que a faixa dinâmica dos pixels fique entre –128 e +127. A seguir, é aplicada a Transformada Discreta Cosseno (DCT) bidimensional. A definição da DCT é dada por:

Extrapolando esta definição para o caso bidimensional e definindo como 8x8 o tamanho do bloco, temos:

Dada a forte relação entre DCT e a DFT ( Discrete Fourier Transform), podemos interpretar as componentes u e v como sendo freqüências espaciais horizontal e vertical, respectivamente. Deste modo, podemos chamar o coeficiente correspondente a u=0 e v=0 de componente DC do bloco. Os outros 63 coeficientes são denotados coeficientes AC por não serem relacionados com as freqüências espaciais nulas. Em imagens reais, a maior parte da energia está geralmente concentrada nos componentes de baixa freqüência. Logo, utilizando a DCT conseguimos uma concentração da energia do bloco no coeficiente DC e nos coeficientes AC de baixas freqüências.

O coeficiente DC é codificado usando DPCM. São usados os coeficientes DC do quadro atual e do anterior. Os 63 coeficientes AC são quantizados linearmente usando uma tabela específica. Passos de quantização, e consequentemente, quantidades de bits, diferentes são utilizados para cada componente de freqüência. O CCITT define 4 tabelas de quantização. A tabela a ser utilizada deve ser escolhida de acordo com as características do bloco.

Os 63 coeficientes AC são ordenados de forma aproximadamente crescente em freqüência. Após a etapa de quantização, estes coeficientes apresentam um elevado número de zeros.

Após a etapa de ordenação, os coeficientes são codificados usando um código de tamanho variável (VLC – Variable Length Coding). Dois exemplos são o código de Huffman e a codificação aritmética, ambos em combinação em codificação run length. Estes códigos são também definidos através de tabelas.

A compressão de imagens se dá com perdas na qualidade da imagem reconstruída. Apesar da boa qualidade conseguida com altas taxas de compressão, existem aplicações que requerem técnicas de compressão sem perdas. A recomendação JPEG especifica também um método de compressão sem perdas. Este modo de compressão é especialmente indicado para aplicações em que qualquer tipo de distorção da imagem reconstruída em relação à original é intolerável.

Este modo de codificação sem perdas utiliza técnicas de predição ao invés da DCT. Seguindo recomendação JPEG, um preditor linear combina os valores de três pixels vizinhos para formar uma predição de um determinado pixel.

A seguir tentaremos explicar mais detalhadamente tudo que foi visto nesta introdução.

Desde os tempos de Newton, sabe-se que um largo espectro de cores pode ser gerado a partir de um conjunto de três cores primárias: vermelho, amarelo e azul. O tubo de televisão produz cores misturando a luz das cores: vermelho, verde e azul. Embora dois sistemas primários possam ser usados – geralmente um vermelho-laranja e um verde-azul – a imagem apresentada não é "viva". O espaço de cores obtido da combinação das três cores pode ser determinado desenhando-se um triângulo em um gráfico de cores especial com cada uma das cores básicas como pontos finais. O gráfico de cores clássico usado nas primeiras especificações para a televisão foi estabelecido em 1931 pela Comissão Internacional de L’Eclairage (CIE). Um dos conceitos especiais introduzidos pelo gráfico da CIE neste ano foi o isolamento da luminância, ou brilho, da crominância, ou matiz.

Usando o gráfico do CIE como guia, a National Television System Committee(NTSC) definiu a transmissão de sinais em um formato de luminância e crominância, ao invés de um formato envolvendo as três cores componentes da televisão à fósforo. O novo espaço de cor foi denominado de YIQ, representando as coordenadas de luminância, crominância de fase, e a crominancia de quadratura respectivamente. Na Europa, dois padrões de televisão foram estabelecidos mais tarde, o formato Phase-alternation-line (PAL) e o Sequentiel couleur a memoire (SECAM), ambos com um espaço de cor idêntico, YUV. A única mudança entre o espaço de cor de PAL/SECAM YUV e o espaço de cor de NTSC YIQ é uma rotação de 33 graus no espaço UV. O equivalente digital do YUV é YCbCr, onde o componente de crominância Cr corresponde ao componente analógico V, e o componente de crominância Cb corresponde ao componente analógico U, embora com fatores de escala diferentes. Nós usaremos os termos Y, U, e V para Y, Cb e Cr para uma descrição resumida do espaço de cor digital de YCbCr.

A conversão entre o formato padrão RGB e o formato YCbCr é ligeiramente diferente para sinais digitais do que para sinais analógicos. Para a convenção do formato JPEG JFIF, a escala inteira de 8 bits é usada para Y, Cb, e Cr. A conversão digital assegura que se a entrada RGB está entre 0 e 255, (normalizada de modo que valor igual represente branco de referência), então a saída Y tem valores entre 0 e 255 e Cb e Cr têm valores entre 0 e 8 bits em sinal, assim os valores de Cb e Cr estão em um nível diferente somando-se 128, de modo que os valores sejam sempre positivos ou iguais a zero, e se Cb e Cr iguais a 256, são passados para 255.

Inversamente, nem todo o espaço de YCbCr traça o espaço legitimo do RGB. Assim os valores para o RGB devem ser "apertados" após a conversão de espaço de cor de 0 a 255. A outra conversão comum de YCbCr executa o escalonamento ligeiramente diferente, por especificações da recomendação 601 da CCIR. A escala nominal YCbCr da CCIR está entre 16 e 235 para a luminância, e de 16 a 240 para as crominâncias . Assim este espaço de cor é apenas uma reescala e mudança nas fórmula descritas acima (isto é: Y' = 219/255 * Y + 16, Cb' = 224/255 * Cb + 128, Cr' = 224/255 * Cr + 128 (supondo que Cb e Cr não têm mudanças de nível antes do escalonamento, mas Cb' e Cr' têm)). O formato YCbCr, similar ao formato YIQ, concentra mais informação da imagem na luminância e menos na crominância. O resultado é que os elementos de YCbCr estão menos correlacionados e, consequentemente, podem ser codificados separadamente sem muita perda na eficiência.

A conversão no espaço de cor é geralmente a primeira etapa para comprimir a imagem. Agora nós consideraremos a etapa seguinte, o modelo de compressão de linha de base.

Para satisfazer a demanda do mercado comercial, o método da linha de base deve ser capaz de fornecer imagens de boa qualidade com taxas de compressão de pelo menos 16:1 e com uma especificação de elemento de pixel entre 4 e 12 bits.

O modelo da linha de base do JPEG, mostrado acima, consiste de quatro estágios: um estágio de transformação, um estágio de quantização da perda, e dois estágios de codificação com menos perdas. A transformada inicial concentra a energia da informação nos primeiros coeficientes transformados, o quantizador causa uma perda controlada da informação, e os dois estágios de codificação comprimem mais os dados. Conforme mencionado anteriormente, os componentes individuais de cor no espaço de cor YCbCr são menos correlacionados do que no espaço de cor RGB. Consequentemente, nós podemos aplicar este modelo para comprimir individualmente cada componente de YCbCr.

O modelo da linha de base do JPEG é considerado um compressor com perdas, porque a imagem reconstruída não é idêntica à original. Os codificadores de redução de perda, que criam imagens idênticas ao original, conseguem uma compressão muito deficiente porque os bits menos significativos de cada componente da cor se tornam progressivamente mais aleatórios e mais difíceis de codificar.

Para cada componente da cor separado, a imagem pode ser dividida em blocos 8 por 8 dos elementos da imagem que juntam as extremidades ao longo da imagem. Cada bloco tipicamente tem energia de vídeo espalhada através dos elementos, a energia definida pelos valores quadráticos de cada elemento. Se a energia de vídeo for de freqüência espacial baixa, variando lentamente, então uma transformação pode ser usada concentrar a energia em alguns poucos coeficientes. O método da transformação escolhido pelo JPEG é a DCT (Discrete Cosine Transform) bidimensional 8 por 8, uma transformada estudada extensivamente para a compressão de imagens.

Uma fórmula explícita para o DCT bidimensional 8 por 8 pode ser escrita. A complexidade do DCT pode ser simplificada tremendamente. Por exemplo, no DCT unidimensional de 8 elementos, as multiplicações podem ser reduzidas a 12;

A saída transformada da DCT bidimensional será requisitada de modo que o valor médio, o coeficiente DC, esteja no canto esquerdo superior e os coeficientes de uma freqüência mais elevada progridam por distância do coeficiente DC. As freqüências verticais mais altas são representadas por linha de números mais altos e as freqüências horizontais mais altas são representadas por colunas de números mais altos. Mesmo que a distribuição da energia mude, a energia total permanece a mesma, porque a DCT é uma transformação unitária (mas por um DCT equilibrado envolver a raiz quadrada do comprimento dos dados, a DCT é definida às vezes com normalização desbalanceada). Além disso, sendo a DCT unitária, o máximo valor de cada coeficiente DCT 8x8 é limitado por um fator oito vezes os valores originais; e após arredondar-se, um valor da entrada de oito bits pode ser representado por um valor transformado de onze bits. Coincidentemente, a IDCT deste bloco, quando arredondado para o inteiro mais próximo, fornece os valores originais, mas uma reconstrução perfeitamente exata não é sempre possível com um valor DCT inteiro.

Os coeficientes do DCT são quantizados para reduzir suas magnitudes e para aumentar o número de valores zero dos coeficientes. O quantizador uniforme de meio passo é usado para o método da linha de base do JPEG, onde o tamanho do passo é variado de acordo com a posição do coeficiente e cujo componente da cor é codificado. A equação para o quantizador pode ser escrita como:

onde C(u; v) é o coeficiente quantizado, F(u; v) é o coeficiente da freqüência de DCT, e Q(u; v) é o quantizador de tamanho de passo para o elemento (u; v) no bloco. O quantizador inverso é:

A quantização é o estágio de perdas na codificação JPEG. Se quantizarmos grosseiramente, podemos terminar com imagens que parecem blocos, mas se quantizarmos muito bem, podemos acabar com os bits inúteis que codificam (essencialmente) ruído. Podemos controlar a quantização pelo Fator de Qualidade (Quality Factor – Q-Factor), um número que muda a matriz padrão da quantização usando um fator multiplicativo eficaz. Um Q-Factor mais elevado dá uma compressão melhor, um Q-Factor mais baixo dá uma imagem melhor em qualidade. Duas tabelas quantizadas são necessárias para crominância e luminância e somente uma para os componentes do RGB.

O modelo de codificação rearranja os coeficientes quantizados de DCT em um padrão zigzag, com as freqüências mais baixas primeiro e as freqüências mais altas por último. O padrão zigzag é usado para aumentar o tempo de funcionamento dos coeficientes zero encontrados no bloco. A suposição é que as freqüências mais baixas tendem a ter coeficientes maiores e as freqüências mais altas são, pela natureza da maioria das imagens, predominantemente zero. Como ilustrado abaixo, o primeiro coeficiente (0,0) é chamado de coeficiente DC e o resto dos coeficientes são chamados de coeficientes AC. Os coeficientes AC são "atravessados" pelo padrão zigzag da posição (0,1) até a posição (7,7).

O padrão zigzag para reordenar os coeficiente da DCT bidimensional para uma disposição unidimensional

Os coeficientes DC da imagem geralmente variam ligeiramente entre blocos sucessivos. O codificador do coeficiente DC explora esta propriedade com a Modulação Diferencial de Código de Pulso (Differential Pulse Code Modulation - DPCM). Esta técnica codifica a diferença entre o coeficiente DC quantizado do bloco atual e o coeficiente DC quantizado do bloco anterior. O DPCM inverso calcula o valor atual do coeficiente DC somando o código atual de DPCM com o valor anterior do coeficiente DC.

A codificação DPCM pega a diferença entre o coeficiente DC e o coeficiente DC encontrado anteriormente.

A codificação de tempo de funcionamento cria um código fora do tempo do funcionamento dos zeros precedendo um coeficiente não-zero e o número de bits do coeficiente não-zero. Se o funcionamento dos zeros for maior que 16, uma sinalização especial é usada (ZRL) e é codificada como (15,0). Sinalizações EOB (0,0..14) são usadas para indicar o fim de um bloco.

O número de bits para a amplitude é dado do código de tempo de funcionamento (com amplitudes SSSS e AC).

SSSS (número de bits para a amplitude)	Coeficiente AC
1	-1, 1
2	-3, -2, 2, 3
3	-7,...,-4, 4,..., 7
4	-15,..., -8, 8,...,15
5	-31,...,-16, 16,...,31
6	-63,..., -32, 32,..., 63
7	-127,..., -64, 64,..., 127
8	-255,..., -128, 128,..., 255
9	-511,..., -128, 128,..., 511
10	-1023,..., -512, 512,..., 1023
11	-2047,..., -1024,..., 1024,..., 2047

Os códigos de bloco de DPCM e de modelos de tempo podem ser mais comprimidos usando o código de entropia. Para o método de linha de base do JPEG, o codificador de Huffman é usado para comprimir os dados mais próximos da entropia de símbolo. Uma razão para usar o codificador de Huffman é que é fácil executar no hardware. Para comprimir símbolos de dados, o codificador de Huffman cria códigos mais curtos para símbolos que ocorrem freqüentemente e códigos mais longos para símbolos que ocorrem ocasionalmente.

Com o SSSS e o número dos bits, você olha as tabelas de Hufmann e obtém um número binário (não necessário para DC)

Se o coeficiente da AC (ou DC) for positivo, você deve adicionar ao código anterior os bits de ordem mais baixa de SSSS do código. Se o coeficiente AC for negativo, você deve remover 1 e adicionar os bits de ordem mais baixa da SSS do resultado. As tabelas de Hufmann são definidas para crominância e o luminância. Você necessita assim duas tabelas se trabalhar com tais componentes.

As tabelas de Huffman podem ser predefinidas das estatísticas geradas de conjuntos de imagens ou calculados em uma base de imagem por imagem. Normalmente, as tabelas padrão de Huffman reduzem o número de bits emitidos por menos de 10 por cento sobre tabelas predefinidas. Para o sistema apresentado aqui, o método padrão é usar tabelas definidas.

Uma imagem pode ser composta de diversos componentes, por exemplo, verde, vermelho e azul. Se nós transferirmos um componente da cor da imagem de cada vez, o chamamos de método não-intercalado. Este método, embora mais simples, requereria um amortecedor de frames para armazenar todos os componentes, exceto o último, porque o valor completo de um pixel é desconhecido até que todos seus valores componentes sejam recebidos. Por exemplo, não sabemos o valor do primeiro pixel RGB sem todos os componentes de R e os componentes de G terem sido recebidos primeiramente. O método intercalado resolve este problema. Pegamos um pequeno bloco de um componente, alguns blocos do componente seguinte, e assim por diante, até que tenhamos blocos de todos os componentes. Então podemos determinar os valores do pixel do subconjunto da imagem recebida. Isto é, caso enviemos um bloco vermelho, um bloco verde, um bloco azul, um bloco vermelho, etc., então depois que um trio do bloco RGB, podemos determinar os valores de todos os 24 bits dos pixels dentro daquele bloco.

O JPEG foi desenvolvido para comprimir tanto imagens coloridas como em escalas de cinza. Funciona bem para imagens mais elaboradas, como fotografias e pinturas, mas não tão bem para desenhos simples e escrita.

Para alguns tipos de imagens, o formato GIF é superior em qualidade de imagem, tamanho de arquivo, ou ambos. O que precisamos saber é para que tipo de imagens devemos aplicar JPEG. De maneira geral, JPEG é melhor aplicado a imagens com variações de cor - fotografias digitalizadas, por exemplo - coloridas ou com no mínimo 16 níveis em tons de cinza. Quanto mais complexa a imagem, melhor o resultado com JPEG. GIF é melhor para imagens com cores lisas (bordas, áreas com cores "puras") realizando, nesses casos, uma compressão muito melhor do que JPEG faria. Nestes casos, JPEG produz imagens desfocadas. Por isso, imagens em preto-e-branco puros (sem tons de cinza) não devem ser processados em JPEG.

Estes exemplos ilustram um pouco sobre o que foi comentado anteriormente (Quando usar GIF e quando usar JPEG).

O primeiro exemplo compara uma imagem digital, gerada por uma câmera de vídeo, e armazenada segundo os formatos GIF e JPEG:

Embora neste exemplo a imagem final não pareça sofrer muito a diferença de compactação, vemos que o formato JPEG lidou melhor com a complexidade da imagem (tons de cor), gerando um arquivo bem menor - e isso será refletido na velocidade de carregamento da imagem.

Além do formato JPEG ter gerado um arquivo maior, a imagem ficou um pouco borrada ao redor das linhas pretas. É um exemplo de que o formato JPEG "não serve" para imagens em cores lisas.


Imagem GIF: 21KB	Imagem JPEG: 6KB


Imagem GIF: 2KB	Imagem JPEG: 5KB