Compressão de imagens

Diego da Rosa

Estêvão Rohr

Fábio Martinazzo

Gustavo Neuberger

Tipos de imagens

raster (quadriculadas, digitalizadas)

vetoriais

Imagens raster

Mapas de bits (bitmaps)

feitas de pontos individuais (pixels)

grade de x pixels de largura por y pixels de altura

dimensões fixas

tamanho do arquivo aumenta com o tamanho e resolução da imagem

screen art

Imagens vetoriais

descrições matemáticas de uma imagem

independentes de resolução

arquivos muito menores que os de imagens raster

line art

Principais formatos de imagens raster:

bitmap (.bmp)

GIF (.gif)

JPEG (.jpg)

Fractal Image Compression (.fif)

Bitmapformato nativo de bitmaps no MS Windows

versão original muito simples, sem compressão, sem paleta de cores fixa. Chamado de Device Dependent Bitmap (DDB)

no Windows 2.0 foi adicionada suporte a tabela de cores programável, sendo agora chamado de Device Independent Bitmap (DIB)

suporte para compressão RLE no Windows 3.0

Quatro formatos BMP distintos:

Monocromático (2 cores)

4 bits por pixel (16 cores)

8 bits por pixel (256 cores)

24 bits por pixel (16777216 cores)

Compressão

RLE4 run-length encoding para bitmaps de4 bits

RLE8 run-length encoding para bitmaps de8 bits

Dois modos: Encode e Absolutepodem ocorrer juntos no mesmo bitmap

Estrutura do arquivo

bitmap-file header14 bytes informações de tipo e tamanho do arquivo

bitmap-information header40 bytes informações de resolução, compressão, tamanho

e número de cores utilizadas

color table array

bitmap data

Color table array

Informações sobre cores utilizadas

Cada entrada com 4 bytes

Informações sobre intensidades relativas de azul, verde e vermelho

Bitmap data

Pixels armazenados da esquerda para direita e de baixo para cima

3 tipos de compressãoBI-RGBBI-RLE 8BI-RLE 4

Compressões RLE

Encoded ModeDois bytesNúmero de pixels seguido pelo índice da

cor

Absolute ModeDois ou mais bytesPrimeiro sempre igual a 0Segundo byte é valor de escape

GIF (Graphics Interchange Format)

Formato desenvolvido e licenciado pela empresa Unisys

Principais característicasPrincipais características

Compressão sem perdas

Trata de imagens indexadas de até 8 bits (256 cores)

Comprime na ordem de 4:1

Utilização

Pequenas figuras e line art

Não recomendado para compressão de imagens fotográficas

Algoritmo de CompressãoAlgoritmo de Compressão

LZW (Lempel – Ziv – Welch)

Codificação de extensão horizontal

Linhas de varredura

Freqüência de cores

Exemplosfuncionamento do LZW

Gifs Animados

Não há maior compressão da imagem ao animá-la com outras

O Padrão JPEG

JPEG é a sigla de Joint Photographic Experts Group, nome do comitê que definiu o padrão no final dos anos 80.

Foi criado pois não havia um padrão adequado para compressão de imagens de 24 bits por pixel.

Características Básicas

Comprime imagens coloridas e em grayscale.

Explora a pouca sensibilidade do olho humano a certos aspectos das imagens.

Produz uma compressão de até 100:1 (normalmente de 10:1 a 20:1 sem perdas significativas).

Imagem final diferente da original.

Algoritmo de Compressão

O algoritmo de compressão utilizado pelo formato JPEG pode ser dividido em 4 etapas básicas:

Criação da Matriz e conversão do espaço colorido;

Transformação DCT;

Quantização;

Codificação adicional.

Criação da Matriz e Conversão das Cores

A imagem original é quebrada em unidades de 8X8 pixels.

Conversão do espaço colorido. Geralmente o RGB é normalizado e convertido para YUV (ou outro). Após, alguns dados são descartados. Este passo não é necessário, mas pode aumentar o desempenho.

A Transformada DCT (Discrete Cosine Transformation)

Gera uma matriz de coeficientes com grande número de zeros e com as freqüências mais importantes agrupadas no canto superior esquerdo da matriz.

Em cada bloco 8X8 é aplicada uma transformação DCT bidimensional dada pela fórmula:(f(m,n) são pixels e t(i,j) coeficientes de freqüências)

A Quantização

Os valores da matriz de coeficientes são divididos por constantes pre-definidas e arredondados para inteiros.

As freqüências menos importantes são perdidas, enquanto as mais importantes perdem a sua precisão inicial.

Codificação Adicional

A matriz é passada para um array unidimensional através do reordemento zig-zag, no qual as baixas freqüências ficam na frente das altas.

Os dados são então codificados pelo método de Huffman ou pelo aritmético. O mais utilizado atualmente é o de Huffman.

Os Tipos de JPEG

Os dois tipos de JPEG mais utilizados são o baseline e o progressive JPEG.

Baseline JPEG: imprime linha por linha, até a imagem completa ser mostrada.

Progressive JPEG: reordena os dados comprimidos. Imprime primeiro a imagem inteira com baixa qualidade e depois vai melhorando-a. Usado na Internet.

O Problema da Transparência

O formato GIF define uma cor que não tenha sido usada na figura para marcar a área da imagem que será transparente. Já o JPEG não possui tal sistema. Durante a compressão, o valor de uma célula é combinado com o valor das células vizinhas e arredondado. A cada compressão o valor é mudado, e não há como saber a cor exata do pixel após a próxima descompressão. Por isso o GIF é mais usado para ícones.

Compressão de imagens com fractais

Iterated Function Systems (IFS):

Baseia-se em transformações afins, que, aplicadas a um ponto (x,y), produzem rotações, redimensionamento e translações no mesmo.

Aplicado a uma imagem *, consiste num mapa W definido pela coleção

de transformadas:

Define o atrator ou ponto fixo:

Compressão de imagens com fractais

Partitioned Iterated Function Systems (PIFS):

Variação do IFS, sendo o sistema utilizado na prática para compressão de imagens, através da transformada afim modificada:

Havendo duas partes (f e g) similares em uma imagem, aplica-se uma w(x,y,z) que transforme f em g.

Aplica-se sucessivamente a outras partes da imagem, até chegar a |W|.

Sendo as partes de imagem utilizadas similares, mas não idênticas, obtém-se, na verdade, um |W|’ => ponto fixo “aproximado”

Compressão de imagens com fractais

Taxa e tempo de compressão e qualidade (comparação com JPEG):

Taxa de compressão com qualidade máxima: similar

Taxa de compressão com qualidade mínima: de duas a quatro vezes maior

Sendo a compressão de imagens com fractais um processo assimétrico (ao contrário do padrão JPEG), a qualidade da imagem após a compressão é menor.

Tempos de compressão e descompressão para imagem de 640 × 480 pixels, com cores de 24 bits:

Compressão Descompressão

Fractais 68 s 1 s

JPEG 6 s 6 s

Compressão de imagens com fractais

A grande vantagem da compressão com fractais

Devido à aplicação das transformadas afins no processo de compressão, provocando redimensionamento da imagem, estas se tornam independentes de resolução, não tendo um tamanho mais “natural” que outro.

Com esse advento, deixa de ocorrer a “pixelização” da imagem, no caso de uma ampliação, por exemplo:

Essa capacidade é exclusiva da compressão de imagem com fractais.

Compressão de imagens com fractais

Utilização

É uma idéia relativamente nova (IFS - 1981; PIFS - 1988)

Problema do longo tempo de compressão ainda não foi resolvido: não se sabe, ainda, como obter exatamente a melhor transformada afim a ser aplicada.

A extensão FIF (Fractal Image Format) não é padronizada, tampouco reconhecida pela maioria dos brownsers.

Está, porém, em franco desenvolvimento. Foram publicados 280 novos artigos sobre o assunto no ano passado.

Tendência de crescimento na sua utilização.

Fontes

Torres, Rosane Beatriz O. S. Um Estudo Sobre Compressão de Imagens Digitais, CPGCC-UFRGS abril 1993

Data Compression Reference Center www.rasip.fer.hr/research/compress/ algorithms/adv/index.html