Compressão - Unicampmartino/disciplinas/ea978/na4.pdf · arquivos de imagens que precisam ser armazenadas e/ou transmitidas em um canal de comunicação. O Processo de Compressão

EA978 Sistemas de Informações Gráficas - Prof. J. Mario De Martino 97____________________________________________________________________________

____________________________________________________________________________Compressão

ÿ Compressão

� Compressão é o processo de reduzir o tamanho físico de umbloco de informação. Em particular, na ComputaçãoGráfica estamos interessados em reduzir o tamanho dearquivos de imagens que precisam ser armazenadas e/outransmitidas em um canal de comunicação.

� O Processo de Compressão está associado a duas fasesdistintas e inversas: Compressão e Descompressão.

� A idéia básica da compressão é representar elementos queocorrem com maior freqüência com um menor número debits.

� Os diferentes métodos de compressão podem serclassificados segundo os seguintes aspectos:

� Simetria

� Perda

� Adaptabilidade


____________________________________________________________________________Compressão

ÿ Simetria

� Refere-se à simetria da complexidade computacional dosalgoritmos de compressão e descompressão.

� Compressão simétrica: os algoritmos de compressãoe descompressão possuem a mesma complexidade,estando associado a aproximadamente o mesmo tempode processamento. Procedimentos simétricos sãoindicados em aplicação que envolvem a transmissão eapresentação das imagens simultaneamente (on thefly).

� Compressão Assimétrica: há um fortedesbalanceamento do tempo de processamento entre acompressão e descompressão. Uma aplicação típica decompressão assimétrica, com o processo dedescompressão mais rápido que o de compressão éaplicação envolvendo um banco de dados de imagens(uma imagem será armazenada apenas uma vez, porémserá lida várias vezes). Procedimentos debackuptendem a privilegiar uma compressão mais rápida emdetrimento do tempo necessário à descompressão.


____________________________________________________________________________Compressão

ÿ Perda

� Perda refere-se à característica do processo decompressão/descompressão de reconstituir os dadosexatamente iguais aos originais ou com alguma perda(alteração).

� A perda está associada a um fator de compressão maior (háum descarte controlado de informação).

� No aspecto de perda é possível classificar o processo decompressão em:

� Sem Perda(lossless)

� Com Perda(lossy)

� É importante observar que uma imagem possui altaredundância de informação e, portanto, a perda deinformação pode implicar em perda de qualidade sem,entretanto, comprometer profundamente a interpretação doconteúdo da imagem. Há aplicações entretanto, que umcompressão com perda é intolerável - considere, porexemplo, a compressão dos dados das contas dos clientesde um banco.


____________________________________________________________________________Compressão

ÿ Adaptabilidade

� A adaptabilidade refere-se à característica doprocesso/algoritmo de se adaptar aos dados de entrada. Épossível identificar segundo este aspecto as seguintesvariação:

� Não-adaptativos: em gera, baseiam-se em dicionárioestáticos definidos à priori em função de estatística defreqüência de dados. Um dicionário decodificação/compressão é em essência uma tabela queassocia símbolos a códigos de menor tamanho.

� Adaptativos: não se baseiam em dicionário pré-definidos, construindo o dicionário em função dosdados de entrada.

� Semi-adaptativos: em geral, é efetuado em doispassos. No primeiro é efetuada uma estatística daentrada, gerando um dicionário. Na segunda fase éefetuada a codificação/compressão propriamente dita.


____________________________________________________________________________Compressão - RLE

ÿ Compressão RLE (Run-Length Encoding)

� A compressão RLE é suportada por vários formatos deimagem do tipobitmapexistentes, tais como, TIFF (TagImage File Format), BMP (Microsoft Windows Bitmap),PCX (PC Paintbrush File Format), MacPaint (MacintoshPaint) e TGA (Truevision Graphics Adapter).

� RLE é de fácil implementação e de execução rápida, masque não produz taxas de compressão comparáveis commétodos mais complexos, porém mais lentos

� RLE procura explora a redundância existente entre ospixels de uma imagem (a tendência de que pixelsadjacentes possuem valores iguais).

� RLE é um método de compressão simétrico, sem perdas eadaptativo.


____________________________________________________________________________Compressão - RLE

ÿ Compressão - RLE (Run-Length Encoding)

� O método RLE opera reduzindo o tamanho de seqüênciasde símbolos repetidos.

� A estratégia em geral utilizada é definir um símbolo comosendo um byte e codificar seqüências de símbolosrepetidos, denominada de seqüência de repetição (run),com dois bytes. O primeiro, denominado contador derepetição (run count), representa o número de vezes que osímbolo se repete - na verdade indica o número de vezesmenos 1. O segundo byte indica o valo de repetição (runvalue), ou seja, o próprio símbolo.

� Exemplo:

� 41 41 41 41 41 41 41 41 41 41 41 41 41 41

� 0D 41

� Obs.: Taxa de compressão: 7:1 (redução de≈ 86%)


____________________________________________________________________________Compressão - RLE


� Os dois bytes (no exemplo 0D 41) é denominado pacoteRLE (RLE run packet). Um novo pacote é gerado todovez que que o símbolo repetido muda ou o valor máximodo contador é atingido..

� Exemplo:

� 41 41 41 41 41 41 62 5A 5A 5A 5A 5A 5A 5A

� 05 41 00 62 07 5A



____________________________________________________________________________Compressão - RLE


CONTADOR = 0;

� VALOR_A = leitura dado de entrada ;

� while ( ainda existir dado de entrada ) {

� VALOR_B = próximo dado de entrada ;

� if ( VALOR_A == VALOR_B &&

� CONTADOR <valor máximo contador ) {

� CONTADOR = CONTADOR + 1;

� }

� else {

� sair com CONTADOR;

� sair com VALOR_A;

� VALOR_A = VALOR_B;

� CONTADOR = 0;

� }

� }

� sair com CONTADOR;

� sair com VALOR_A;


____________________________________________________________________________Compressão - RLE


� Os formatos gráficos que utilizam a compressão RLE,também adotam um estratégia para codificar seqüênciasde bytes diferente. Estas seqüências são denominadas depacotes brutos - raw packets. Os pacotes brutos sãocodificados com um contador inicial seguido seguido daseqüência de bytes. Para diferenciar os pacotes rle dospacotes brutos, utliza-se o bit mais significativo do bytecontador (bit = 1ÿ pacote rle; bit = 0 pacote bruto).

� Exemplo:

� 41 41 41 41 41 41 62 5A 3B 47 72 56 56 56 56 56 56 56

� 85 41 04 62 5A 3B 47 72 86



____________________________________________________________________________Compressão - RLE


� Variações:

� Ordem da codificação

� Definição dos símbolos (3 na prática) : bit, byte, pixel.

(a) (b)

(c) (d)


____________________________________________________________________________Compressão - RLE


� Observação finais:

� Simples e rápido tanto para a compressão quanto paraa descompressão

� Taxa de compressão fortemente dependente da entradade dados:

� Imagem preto branco de texto ouline art -contém grande regiões brancas e serácomprimida significativamente.

� Imagem com cores chapadas (ilustraçõescoloridas -color artwork) tendem a apresentarextensas regiões de mesma cor - compressão boa

� Imagem fotográfica: por apresentar muitas e sutisvariações de cores/tons tende a não apresentarum boa taxa de compressão RLE.

�


____________________________________________________________________________Compressão - LZW

ÿ Compressão - LZW (Lempel-Ziv-Welch)

� O nome do algoritmo é derivado dos nomes de seusdesenvolvedores: Abraham Lempel, Jakob Ziv e TerryWelch

� Os três trabalhavam na Sperry Corporation, que patentou oalgoritmo. Atualmente a patente é da Unisys (fusão daSperry com a Burroughs)

� O algoritmo LZW é simétrico, adaptativo e sem perdas.

� Utiliza estratégia de compressão baseada em dicionário(tabela de associação código - símbolo)

� O filosofia do LZW é substituir seqüências de símbolos porcódigos. Em geral, os códigos são menores que asseqüências que representam, implicando em uma reduçãodo tamanho.


____________________________________________________________________________Compressão - LZW


� SEQUENCIA =dado de entrada ;

� while ( ainda existe dado de entrada ) {

� CARATER =próximo dado de entrada ;

� if ( concatenação SEQUENCIA CARATERno

dicionário ) {

� SEQUENCIA =concatenação SEQUENCIA CARATER;

� }

� else {

� sair com código da SEQUENCIAconstante no

dicionário ;

� adicionar concatenação SEQUENCIA CARATER ao

� dicionário ;

� SEQUENCIA = CARATER;

� }

� }

� sair com código da SEQUENCIAconstante no

dicionário ;


____________________________________________________________________________Compressão - LZW


� Exemplo

� Apenas 3 símbolos: A B C

� Seqüência de entrada

� ABABCBABABAAAAAA

� Dicionário inicial (apenas símbolos primitivos pré-definidos):

Seqüência Código

A 1

B 2

C 3


____________________________________________________________________________Compressão - LZW


A

B

A

B

C

B

A

B

A

B

A

A

A

A

A

A

1

2

4

3

5

8

1

10

11

AB 4

BA 5

ABC 6

CB 7

BAB 8

BABA 9

AA 10

AAA 11

Entrada SaídaInserçãoDicionário


____________________________________________________________________________Compressão - LZW


� Dicionário Gerado

Dicionário

Seqüência Código

A 1

B 2

C 3

AB 4

BA 5

ABC 6

CB 7

BAB 8

BABA 9

AA 10

AAA 11

Dicionário Otimizado

Seqüência Código

A 1

B 2

C 3

1B 4

2A 5

4C 6

3B 7

5B 8

8A 9

1A 10

10A 11


____________________________________________________________________________Compressão - LZW

ÿ Descompressão - LZW (Lempel-Ziv-Welch)

� CODIGO_ANTIGO =dado de entrada;

� sair com caráter associado aoCODIGO_ANTIGO;

� while ( ainda existir dado de entrada) {

� CODIGO_NOVO =dado de entrada;

� if ( CODIGO_NOVOnão existir no dicionário) {

� SEQUENCIA =decodificação doCODIGO_ANTIGO;

� SEQUENCIA =concatenaçãoSEQUENCIA CARATER;

� }

� else {

� SEQUENCIA =decodificação doCODIGO_NOVO;

� }

� sair com SEQUENCIA;

� CARATER = primeirocaráter da SEQUENCIA;

� inserir concatenação de CODIGO_ANTIGO CARATERno dicionário;

� CODIGO_ANTIGO = CODIGO_NOVO;

� }


____________________________________________________________________________Compressão - LZW


� Exemplo

1

2

4

3

5

8

1

10

11

A

B

AB

C

BA

BAB

A

AA

AAA

1B 4

2A 5

4C 6

3B 7

5B 8

8A 9

1A 10

10A 11

Entrada SaídaInserçãoDicionário


____________________________________________________________________________Compressão - LZW


� Observações Finais

� LZW pode ser utilizado para a compressão da arquivostipo texto, imagem e dados.

� Utilizado nos formatos GIF (Graphics InterchangeFormat) e TIFF (Tag Image File Format).

� O maior problema de implementação do algoritmoenvolve o gerenciamento da tabela que implementa odicionário - é interessante utilizar estratégiahashingpara facilitar a busca.


____________________________________________________________________________Compressão - JPEG

ÿ Compressão - JPEG

� CCITT e ISO/IEC estabeleceram um padrão para acompressão de imagens estáticas coloridas ou em tons decinza.

� Este padrão ficou conhecido pelo nome de JPEG em razãodo grupo de trabalha da ISO responsável pela sua definição.JPEG - Joint Photographic Expert Group.

� ITU (International Telecommunication Union) é umaagência da ONU no campo das telecomunicações.

� CCIT (Comité Consultatif International Télegraphique etTéléphonique) é um orgão permanente da ITU responsávelpela definição de padrões internacionais emtelecomunicações (Recommendations). O CCIT éatualmente denominado ITU-T.

� ISO (International Standardizing Organization) é umaorganização internacional de padronização que atua emdiversas áreas.

� IEC - International Electrotechnical Commission

� O padrão JPEG é definido pela ITU-T RecommendationT.81.


____________________________________________________________________________Compressão - JPEG


� O Padrão JPE define 4 modos para a compressão JPEG:

� Seqüencial baseado na transformação DCT (sequentialDCT-based).

� Progressivo baseado na DCT (progressive DCT-based)

� Sem Perdas (lossless)

� Hierárquico (hierarchical).

� Trataremos apenas o primeiro modo: Seqüencial baseadona DCT

� O padrão JPEG define o modo seqüencial comoobrigatório para qualquer aplicação aderente à norma, é odenominado modo básico.

� Para os mais interessados na página do curso temos o textoda norma - Recommendation T.81

� JFIF é JPEG File Interchange Format é um formato dearquivo baseado na codificação JPEG. Este é o formato dearquivo gráfico conhecido como JPEG.


____________________________________________________________________________Compressão - JPEG

ÿ Compressão/Descompressão - JPEG/JFIFmodo básico (baseline)

� Passos

Transfomaçãode Cor

Sub-Amostragem

TranformaçãoDCT

Quantização Codificação

Super-Amostragem

InversaDCT

De-quantização

ImagemComprimida

ImagemOriginal

Compressão JPEG

Descompressão JPEG

DecodificaçãoTransfomaçãode Cor


____________________________________________________________________________Compressão - JPEG

ÿ Compressão - JPEG/JFIF

� Transformação de Cor para imagem coloridas (truecolor):

� JPEG produz melhores resultados para imagensrepresentadas por informação de de luminância ecrominância;

� JFIF adotou as seguintes componentes de luminânciae crominâncias

� OBS: R, G e B podem assumir valores entre 0 - 255(codificação em 8 bits).

� É possível ainda sub-amostrar os canais decrominância segundo os esquemas 4:2:2, 4:2:0.

� O valores dos 3 canais sofrem ainda um deslocamentode nível de -128.

1280813,04187,05,0

1285,03313,01687,0

114,0587,0299,0

+−−=++−−=

++=

BGRC

BGRCb

BGRY

r


____________________________________________________________________________Compressão - JPEG


� Transformação RBG em Y Cb Cr codificado em 8 bits

� (R-Y) (B-Y) entre -0,5 e +0,5

� Valores entre 0 e 255

BGRYR

BGRYB

BGRY

114,0587,0701,0)(

886,0587,0299,0)(

114,0587,0299,0

−−=−+−−=−

++=

)(713,0)(701,0

5,0

)(564,0)(886,0

5,0

YRYR

YBYB

−=−

−=−

1280813,04187,05,0

1285,03313,01687,0

+−−=++−−=

BGRC

BGRCb

r


____________________________________________________________________________Compressão - JPEG


� Transformação de Cor:

� Imagem em tons de cinza(grayscale) 8 bits

� O próprio valor.

� Também sofre um deslocamento de nível (-128)


____________________________________________________________________________Compressão - JPEG

ÿ Compressão - JPEG/JFIFExemplo (imagem em tons de cinza)

� Imagem original

52 55 61 66 70 61 64 73

63 59 66 90 109 85 69 72

62 59 68 113 144 104 66 73

63 58 71 122 154 106 70 69

67 61 68 104 126 88 68 70

79 65 60 70 77 63 58 75

85 71 64 59 55 61 65 83

87 79 69 68 65 76 78 94


____________________________________________________________________________Compressão - JPEG

ÿ Compressão - JPEG/JFIFExemplo (imagem em tons de cinza)

� Deslocamento de nível (-128 )

-76 -73 -67 -62 -58 -67 -64 -55

-65 -69 -62 -38 -19 -43 -59 -56

-66 -69 -60 -15 16 -24 -62 -55

-65 -70 -57 -6 26 -22 -58 -59

-61 -67 -60 -24 -2 -40 -60 -58

-49 -63 -68 -58 -51 -60 -70 -53

-43 -57 -64 -69 -73 -67 -63 -45

-41 -49 -59 -60 -63 -52 -50 -34


____________________________________________________________________________Compressão - JPEG


� Transformada DCT (Discrete Cosine Transform) aplicada ablocos de 8x8

� Transformada Inversa

( ) ( ) ( )ÿ�

��

��

�� +

��

�� += � �

= = 16

12cos

16

12cos),()()(

4

1,

7

0

7

0

ππ vyuxxyfuCvCuvF

y x

( )��

��

≠

==01

02

1

zse

zsezC

( ) ( ) ( )ÿ�

��

��

�� +

��

�� += � �

= = 16

12cos

16

12cos),()()(

4

1,

7

0

7

0

ππ vyuxuvFuCvCxyf

v u


____________________________________________________________________________Compressão - JPEG


� Transformada DCT

� v= u = 0

� Interpretação: “valor médio” - componente constante -componente DC

( ) ÿ�

��

�= � �

= =

7

0

7

0

),()()(4

10,0

y x

xyfuCvCF

( ) ( ) ( ) ( ) ( ) ( ) ( )[ ]7,70,77,10,17,00,08

10,0 ffffffF ++++++++= ÿÿÿ


____________________________________________________________________________Compressão - JPEG


� Transformada DCT (Discrete Cosine Transform):

� v=0; u =1

� Medida variação lenta na direção x - componente AC

( ) ( )ÿ�

��

��

�� += � �

= =

7

0

7

0 16

12cos),()()(

4

11,0

y x

xxyfuCvCF

π

( ) ( ) ( ) ( ) ( ) ÿ�

��

��

��++�

��

��++�

��

��++�

��

��=

16

15cos7,7

16cos0,7

16

15cos7,0

16cos0,0

24

11,0

ππππffffF ÿÿÿ


____________________________________________________________________________Compressão - JPEG

ÿ Compressão - JPEG/JFIF - DCT

980785,016

15cos

83147,016

13cos

55557,016

11cos

19509,016

9cos

19509,016

7cos

55557,016

5cos

83147,016

3cos

980785,016

cos

−=ÿ��

��

−=ÿ��

��

−=ÿ��

��

−=ÿ��

��

=ÿ��

��

=ÿ��

��

=ÿ��

��

=ÿ��

��

π

π

π

π

π

π

π

π


____________________________________________________________________________Compressão - JPEG


� Transformada DCT (Discrete Cosine Transform):

� v= 0; u = 2

� Medida da variação um pouco pouco mais rápida nadireção x - Componente AC

( ) ( )ÿ�

��

��

�� += � �

= =

7

0

7

0 16

212cos),()()(

4

12,0

y x

xxyfuCvCF

π

( ) ( ) ( ) ( ) ( ) ÿ�

��

��

��++�

��

��++�

��

��++�

��

��=

16

30cos7,7

16

6cos1,7

16

30cos7,0

16

2cos0,0

24

12,0

ππππffffF ÿÿÿ


____________________________________________________________________________Compressão - JPEG


92388,016

30cos

3826837,016

16cos

382683,016

22cos

92388,016

18cos

92388,016

14cos

382683,016

10cos

382683,016

6cos

92388,016

2cos

=ÿ��

��

=ÿ��

��

−=ÿ��

��

−=ÿ��

��

−=ÿ��

��

−=ÿ��

��

=ÿ��

��

=ÿ��

��

π

π

π

π

π

π

π

π


____________________________________________________________________________Compressão - JPEG


F00 F01 F02 F07F06F05F04F03

F11 F12 F17F16F15F14F13

F20 F21 F22 F27F26F25F24F23

F31 F32 F37F36F35F34F33

F40 F41 F42 F47F46F45F44F43

F51 F52 F57F56F55F54F53

F60 F61 F62 F67F66F65F64F63

F70 F71 F72 F77F76F75F74F73

F30

F10

F50

u

v

freqüência crescente em u

freqüência

crescente

em

v


____________________________________________________________________________Compressão - JPEG

ÿ Compressão - JPEG/JFIFExemplo (imagem em tons de cinza) - cont.

� DCT

-415 -29 -62 25 55 -20 -1 3

7 -21 -62 9 11 -7 -6 6

-46 8 77 -25 -30 10 7 -5

-50 13 35 -15 -9 6 0 3

11 -8 -13 -2 -1 1 -4 1

-10 1 3 -3 -1 0 2 -1

-4 -1 2 -1 2 -3 1 -2

-1 -1 -1 -2 -1 -1 0 -1


____________________________________________________________________________Compressão - JPEG


� Quantização (normalização)

� A perdas (descarte controlado de informação) sãointroduzidas neste estágio.

� Quanto maior o Q(v,u) maior é o descarte de informaçãoassociado à componente v,u.

( ) ( )( )

( )( )( ) oquantizaçãdeecoeficientuvQ

inicialvaloruvF

quantizadovaloruvF

onde

uvQ

uvFrounduvF

quant

quant

−−

−

ÿÿ�

��

�=

,

,

,

:

,

,,


____________________________________________________________________________Compressão - JPEG


� Quantização - Exemplo de matriz de Quantização(luminância)

� Observar que a taxa de maior crescimento dos pesosencontra-se na diagonal. Eliminação das componentes deAC de alta-freqüência.

� Para imagens coloridas utiliza-se tabelas diferentes para aluminância e crominâncias

16 11 10 16 24 40 51 61

12 12 14 19 26 58 60 55

14 13 16 24 40 57 69 56

14 17 22 29 51 87 80 62

18 22 37 56 68 109 103 77

24 35 55 64 81 104 113 92

49 64 78 87 103 121 120 101

72 92 95 98 112 100 103 99


____________________________________________________________________________Compressão - JPEG


� Quantização (normalização)

-26 -3 -6 2 2 0 0 0

1 -2 -4 0 0 0 0 0

-3 1 5 -1 -1 0 0 0

-4 1 2 -1 0 0 0 0

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0


____________________________________________________________________________Compressão - JPEG


� Após a quantização, é efetuada a serialização dos dadossegundo um padrão Zig-Zag.

F00 F01 F02 F07F06F05F04F03

F11 F12 F17F16F15F14F13

F20 F21 F22 F27F26F25F24F23

F31 F32 F37F36F35F34F33

F40 F41 F42 F47F46F45F44F43

F51 F52 F57F56F55F54F53

F60 F61 F62 F67F66F65F64F63

F70 F71 F72 F77F76F75F74F73

F30

F10

F50


____________________________________________________________________________Compressão - JPEG


� Serialização Zig-Zag

EOB1100000210

02051141426231326

−−−

−−−−−−−


____________________________________________________________________________Compressão - JPEG


� Codificação

� As componentes DC E AC sãocodificadas/decodificadas por códigos de Huffmanespecificados em tabelas.

� Existem dois tipos de tabelas:

� Tabela de codificação para a componente DC.

� Tabela de codificação para as componentes AC.

� As tabelas de codificação são enviadas junto com aimagem. Não mais do que 2 tabelas são enviadas paraa codificação DC e 2 para a codificação AC (em geral,uma para luminância e outra para as crominâncias).

� A componente DC é tratada de forma diferente dascomponentes AC


____________________________________________________________________________Compressão - JPEG

ÿ Codificação DC

� A componente DC de um bloco é codificadadiferencialmente tomando-se a diferença do valor DC dobloco atual com o valor DC do bloco anterior (caso nãoexista o bloco anterior, o valor do bloco anterior éconsiderado igual a zero).

� O valor da diferença DC a ser codificado é classificado emuma categoria e um valor dentro desta categoria.

� A codificação é dada pela codificação Huffman dacategoria concatenada com bits adicionais que especificamo valor dentro da categoria.

� A codificação Huffman da categoria é dada por uma tabelade codificação que é enviada/armazenada junto com aimagem.

� O código de Huffman de uma determinada categoria possuino máximo 16 bits.


____________________________________________________________________________Compressão - JPEG

ÿ Categorias para a codificação DC

� A categoria especifica quantos bits são necessários paraespecificar o valor dentro da categoria.

� A especificação do valor dentro da categoria segue a regra:

� Valor positivo: o próprio valor representado com onúmero de bits dado pela categoria

� Valor negativo: os c bits menos significativos de(valor –1), onde c é a categoria.

Categoria Faixa de Valor

0 0

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, ..., -256, 256, ..., 511

10 -1023, ..., -512, 512, ..., 1023

11 -2047, ..., -1024, 1024, ..., 2047


____________________________________________________________________________Compressão - JPEG

ÿ Exemplos codificação DC:

� Um valor de diferença DC igual a 18 teria:

� Categoria: 5

� Valor: 10010 (valor 18)

� Um valor de diferença DC igual a –18 teria:

� Categoria: 5

� Valor: 01101 (últimos 5 bits de –19)


____________________________________________________________________________Compressão - JPEG

ÿ Tabela de codificação DC de categorias(um exemplo)

Categoria Código

0 010

1 011

2 100

3 00

4 101

5 110

6 1110

7 11110

8 111110

9 1111110

10 11111110

11 111111110


____________________________________________________________________________Compressão - JPEG


� Codificação DC

� Valor DC bloco atual = -26

� Supondo, por exemplo, bloco anterior com nível DCigual a -17.

� Diferença DC = -9

� Código: (Código da Categoria) (Código do Valor):

� -9ÿ Categoria 4

� Código da Categoria: 101

� -9ÿ Código Valor: 0110

� Código: 1010110


____________________________________________________________________________Compressão - JPEG

ÿ Codificação AC

� A codificação AC procura codificar apenas os coeficientesAC diferentes de zero.

� Cada coeficiente AC diferente de zero é descrito por 8 bitsna forma: RRRRSSSS (onde R e S representam númerosbinários).

� Os quatro bits RRRR especifica a repetição de coeficienteszeros que ocorre antes do coeficiente não zero (run-lengthde zeros).

� Os quatro bits SSSS define a categoria do valor docoeficiente AC.

� A representação RRRRSSSS é codificada com o auxilio detabela de codificação Huffman armazenada/transmitidajunto com a imagem.

� A codificação Huffman de RRRRSSSS é seguida por bitsadicionais que especificam o valor dentro da categoria.


____________________________________________________________________________Compressão - JPEG

ÿ Codificação AC

� O valor RRRRSSSS = 00000000 (EOB – End of Block)especifica que todos os coeficientes que se seguem até ofinal do bloco são iguais a zero.

� O valor RRRRSSSS = 11110000 especifica que temos 16zeros e é utilizado para a codificação de 16 ou maiscoeficientes zeros seguidos, utilizando-se tantas seqüências11110000 quanto forem necessárias.


____________________________________________________________________________Compressão - JPEG

ÿ Categorias para a codificação AC

� A categoria especifica quantos bits são necessários paraespecificar o valor dentro da categoria.

� A especificação do valor dentro da categoria segue a regra:

� Valor positivo: o próprio valor representado com onúmero de bits dado pela categoria

� Valor negativo: os c bits menos significativos de(valor –1), onde c é a categoria.

Categoria Faixa de Valor

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, ..., -256, 256, ..., 511

10 -1023, ..., -512, 512, ..., 1023


____________________________________________________________________________Compressão - JPEG

ÿ Tabela de codificação AC (um exemplo)R/C Código R/C Código R/C Código R/C Código

0/0 1010 (=EOB)

0/1 00 4/1 111011 8/1 11111010 C/1 1111111010

0/2 01 4/2 1111111000 8/2 111111111000000 C/2 1111111111011010

0/3 100 4/3 1111111110010111 8/3 1111111110110111 C/3 1111111111011011

0/4 1001 4/4 1111111110011000 8/4 1111111110111000 C/4 1111111111011100

0/5 11010 4/5 1111111110011001 8/5 1111111110111001 C/5 1111111111011101

0/6 111000 4/6 1111111110011010 8/6 1111111110111010 C/6 1111111111011110

0/7 1111000 4/7 1111111110011011 8/7 1111111110111011 C/7 1111111111011111

0/8 1111110110 4/8 1111111110011100 8/8 1111111110111100 C/8 1111111111100000

0/9 1111111110000010 4/9 1111111110011101 8/9 1111111110111101 C/9 1111111111100001

0/A 1111111110000011 4/A 1111111110011110 8/A 1111111110111110 C/A 1111111111100010

1/1 1100 5/1 1111010 9/1 111111000 D/1 11111111010

1/2 111001 5/2 1111111001 9/2 1111111110111111 C/2 1111111111100011

1/3 1111001 5/3 1111111110011111 9/3 1111111111000000 C/3 1111111111100100

1/4 111110110 5/4 1111111110100000 9/4 1111111111000001 D/4 1111111111100101

1/5 11111110110 5/5 1111111110100001 9/5 1111111111000010 D/5 1111111111100110

1/6 1111111110000100 5/6 1111111110100010 9/6 1111111111000011 D/6 1111111111100111

1/7 1111111110000101 5/7 1111111110100011 9/7 1111111111000100 D/7 1111111111101000

1/8 1111111110000110 5/8 1111111110100100 9/8 1111111111000101 D/8 1111111111101001

1/9 1111111110000111 5/9 1111111110100101 9/9 1111111111000110 D/9 1111111111101010

1/A 1111111110001000 5/A 1111111110100110 9/A 1111111111000111 D/A 1111111111101011

2/1 11011 6/1 1111011 A/1 111111001 E/1 111111110110

2/2 11111000 6/2 11111111000 A/2 1111111111001000 E/2 1111111111101100

2/3 1111110111 6/3 1111111110100111 A/3 1111111111001001 E/3 1111111111101101

2/4 1111111110001000 6/4 1111111110101000 A/4 1111111111001010 E/4 1111111111101110

2/5 1111111110001010 6/5 1111111110101001 A/5 1111111111001011 E/5 1111111111101111

2/6 1111111110001011 6/6 1111111110101010 A/6 1111111111001100 E/6 1111111111110000

2/7 1111111110001100 6/7 1111111110101011 A/7 1111111111001101 E/7 1111111111110001

2/8 1111111110001101 6/8 1111111110101100 A/8 1111111111001110 E/8 1111111111110010

2/9 1111111110001110 6/9 1111111110101101 A/9 1111111111001111 E/9 1111111111110011

2/A 1111111110001111 6/A 1111111110101110 A/A 1111111111010000 E/A 1111111111110100

3/1 111010 7/1 11111001 B/1 111111010 F/0 111111110111

3/2 111110111 7/2 11111111001 B/2 1111111111010001 F/1 1111111111110101

3/3 11111110111 7/3 1111111110101111 B/3 1111111111010010 F/2 1111111111110110

3/4 1111111110010000 7/4 1111111110110000 B/4 1111111111010011 F/3 1111111111110111

3/5 1111111110010001 7/5 1111111110110001 B/5 1111111111010100 F/4 1111111111111000

3/6 1111111110010010 7/6 1111111110110010 B/6 1111111111010101 F/5 1111111111111001

3/7 1111111110010011 7/7 1111111110110011 B/7 1111111111010110 F/6 1111111111111010

3/8 1111111110010100 7/8 1111111110110100 B/8 1111111111010111 F/7 1111111111111011

3/9 1111111110010101 7/9 1111111110111101 B/9 1111111111011000 F/8 1111111111111100

3/A 1111111110010110 7/A 1111111110110110 B/A 1111111111011001 F/9 1111111111111101

F/A 1111111111111110


____________________________________________________________________________Compressão - JPEG


� Codificação AC

� Codificação:(Código R/ C) (Código Valor)

� Codificar cada um dos valores AC

EOB1100000210

020511414262313

−−−−−−−−−− 26


____________________________________________________________________________Compressão - JPEG



� Coeficiente AC = -3

� Código: (Código R/C) (Código Valor)

� Repetição de zerosÿ Repetição: 0

� -3ÿ Categoria: 2

� (0/2)ÿ Código R/C: 01


� Código: 0100

EOB1100000210

0205114142623126

−−−−−−−−−− 3


____________________________________________________________________________Compressão - JPEG



� Coeficiente AC = 1



� 1ÿ Categoria: 1

� (0/1)ÿ Código R/C: 00

� 1ÿ Código Valor: 1

� Código: 001

EOB1100000210

0205114142623326

−−−−−−−−−− 1


____________________________________________________________________________Compressão - JPEG



� Coeficiente AC = 2



� 2ÿ Categoria: 2

� (1/2)ÿ Código R/C: 111001

� 2ÿ Código Valor: 10

� Código: 11100110

EOB1100000210

051141426231326

−−−−−−−−−− 20


____________________________________________________________________________Compressão - JPEG



� Coeficiente AC = -1



� -1ÿ Categoria: 1

� (5/1)ÿ Código R/C: 1111010


� Código: 11110100

EOB1210

02051141426231326

−−−−−−−−−−

100000


____________________________________________________________________________Compressão - JPEG


� Codificação do Bloco

101000011110100011011011011100110100101001001

10001100110001101101000010101010000101001010110

EOB1100000210

02051141426231326

−−−

−−−−−−−


____________________________________________________________________________Compressão - JPEG

ÿ Descompressão - JPEG/JFIFExemplo (imagem em tons de cinza)

� Valores de Entrada

� Após busca nas tabelas de codificação Huffman

101000011110100011011011011100110100101001001

10001100110001101101000010101010000101001010110

-26 -3 -6 2 2 0 0 0

1 -2 -4 0 0 0 0 0

-3 1 5 -1 -1 0 0 0

-4 1 2 -1 0 0 0 0

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0


____________________________________________________________________________Compressão - JPEG


� De-quantização

( ) ( ) ( )

( )( )( ) oquantizaçãdeecoeficientuvQ

quantizadovaloruvF

aproximadooriginalvaloruvF

onde

uvQuvFuvF

quant

quant

−

−−

=

,

,

,

:

,*,,

-416 -33 -60 32 48 0 0 0

12 -24 -56 0 0 0 0 0

-42 13 80 -24 -40 0 0 0

-56 17 44 -29 0 0 0 0

18 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0


____________________________________________________________________________Compressão - JPEG


� DCT inversa

-70 -64 -61 -64 -69 -66 -58 -50

-72 -73 -61 -39 -30 -40 -54 -59

-68 -78 -58 -9 13 -12 -48 -64

-59 -77 -57 0 22 -13 -51 -60

-54 -75 -64 -23 -13 -44 -63 -56

-52 -71 -72 -54 -54 -71 -71 -54

-45 -59 -70 -68 -67 -67 -61 -50

-35 -47 -61 -66 -60 -48 -44 -44


____________________________________________________________________________Compressão - JPEG


� Deslocamento de nível (+128)

58 64 67 64 59 62 70 78

56 55 67 89 98 88 74 69

60 50 70 119 141 116 80 64

69 51 71 128 150 115 77 68

74 53 64 105 115 84 65 72

76 57 56 74 74 57 57 74

83 69 58 60 61 61 67 78

93 81 67 62 68 80 84 84


____________________________________________________________________________Compressão - JPEG


� Imagem original

� Imagem reconstruída

58 64 67 64 59 62 70 78

56 55 67 89 98 88 74 69

60 50 70 119 141 116 80 64

69 51 71 128 150 115 77 68

74 53 64 105 115 84 65 72

76 57 56 74 74 57 57 74

83 69 58 60 61 61 67 78

93 81 67 62 68 80 84 84

52 55 61 66 70 61 64 73

63 59 66 90 109 85 69 72

62 59 68 113 144 104 66 73

63 58 71 122 154 106 70 69

67 61 68 104 126 88 68 70

79 65 60 70 77 63 58 75

85 71 64 59 55 61 65 83

87 79 69 68 65 76 78 94


____________________________________________________________________________Compressão - JPEG


� Diferença entre imagem original e reconstruída (faixa deerro entre -14 e =11). Erro quadrático médio≈ 5.9

-6 -9 -6 2 11 -1 -6 -5

7 4 -1 1 11 -3 -5 3

2 9 -2 -6 3 -12 -14 9

-6 7 0 -6 4 -9 -7 1

-7 8 4 -1 11 4 3 -2

3 8 4 -4 3 6 1 1

2 2 6 -1 -6 0 -2 5

-6 -2 2 6 -3 -4 -6 10


____________________________________________________________________________Compressão - JPEG

ÿ Especificação das Tabelas de Codificação

� Observações iniciais:

� A tabela de codificação DC tem 12 entradas:

� Categorias de 0 a 11

� A tabela de codificação AC tem 162 entradas:

� 10 categorias (Categorias de 1 a 10)

� Para cada categoria 16 possibilidades derepetição de zeros (0 até 15)

� 2 entradas especiais (0/0 e F/0)


____________________________________________________________________________Compressão - JPEG


� A tabela de codificação DC é especificadas através deinformação que é armazenada/transmitida junto com aimagem constituída por:

� Vetor de 16 bytes, denominado BITS, que especificaos tamanhos dos códigos a serem gerados (quantoscódigos de cada tamanho).

� Vetor de 12 bytes , denominado HUFFVAL, queespecificam a associação categoria↔ código

� A tabela de codificação AC é também especificadasatravés de informação que é armazenada/transmitida juntocom a imagem constituída por:

� Vetor de 16 bytes, denominado BITS, que especificaos tamanhos dos códigos a serem gerados (quantoscódigos de cada tamanho)..

� Vetor de 162 bytes , denominado HUFFVAL, queespecificam a associação R/C↔ código


____________________________________________________________________________Compressão - JPEG

ÿ Especificação Tabela DC (exemplo)

� Vetor BITS (16 bytes em hexadecimal)

� Vetor HUFFVAL (12 bytes em hexadecimal)

00000000000000010101010101050100

0B0A09080706050402010003


____________________________________________________________________________Compressão - JPEG

ÿ Especificação Tabela AC (exemplo)

� Vetor BITS (16 bytes em hexadecimal)

� Vetor HUFFVAL (12 bytes em hexadecimal – cada byteRRRRSSSS)

7D010000040405050304020303010200

FAF9

F8F7F6F5F4F3F2F1EAE9E8E7E6E5E4E3

E2E1DAD9D8D7D6D5D4D3D2CAC9C8C7C6

C5C4C3C2BAB9B8B7B6B5B4B3B2AAA9A8

A7A6A5A4A3A29A99989796959493928A

898887868584837A797877767574736A

696867666564635A595857565554534A

494847464544433A3938373635342A29

282726251A191817160A098272623324

F0D15215C1B1422308A1918132147122

07615113064131211205110400030201


____________________________________________________________________________Compressão - JPEG


� Existem 3 procedimentos para gerar uma tabela decodificação (AC ou DC) a partir de sua especificação:

� GERSIZE: que gera uma tabela dos tamanhos doscódigos de Huffman;

� GERCODE: que gera os códigos de Huffman

� SORTCODE: que ordena os códigos, fazendo aassociação categoria↔ código ou R/C↔ código,dependendo se DC ou AC.


____________________________________________________________________________Compressão - JPEG


� GERSIZE: que gera um tabela dos tamanhos dos códigosde Huffman - HUFFSIZE

i = 0; // i indice BITS

// i + 1 tamanho codigo

j = 1;

k = 0; // k indice HUFFSIZE

do {

while ( j <= BITS[i] ) {

HUFFSIZE[k] = i + 1;

k++;

j++;

}

i++;

j = 1;

} while ( i < 16 )

HUFFSIZE[k] = 0;

LASTK = k;


____________________________________________________________________________Compressão - JPEG

ÿ Especificação das Tabelas de Codificação(exemplo GERSIZE)

� BITS (bytes em hexadecimal)

� HUFFSIZE (valores em decimal)

� LASTK = 12

0987654333332

00000000000000010101010101050100


____________________________________________________________________________Compressão - JPEG


� GERCODE: que gera os códigos de Huffman -HUFFCODE

k = 0;

SI = HUFFSIZE[k];

CODE = 0

while ( HUFFSIZE[k] != 0) {

while ( HUFFSIZE[k] != SI ) {

SI++;

CODE= CODE << 1;

}

while ( HUFFSIZE[k] == SI )

HUFFCODE[k] = CODE;

CODE = CODE + 1;

k++;

}

}


____________________________________________________________________________Compressão - JPEG


� HUFFSIZE

� HUFFCODE (valores em binário)

0987654333332

11111111011111110

111111011111011110111011010110001101000


____________________________________________________________________________Compressão - JPEG


� SORTCODE: que ordena os códigos, fazendo a associaçãocategoria↔ código ou R/C↔ código.

for ( k = 0 ; k < LASTK; k++) {

i = HUFFVAL[k];

EHUFCO[i] = HUFFCODE[k];

EHUFSI[i] = HUFFSIZE[k];

}

�


____________________________________________________________________________Compressão - JPEG


� HUFFVAL

� HUFFCODE

� HUFFSIZE

� Tabela

0B0A09080706050402010003

11111111011111110

111111011111011110111011010110001101000

0987654333332

EHUFCO EHUFSICategoria Código Tamanho

0 010 31 011 32 100 33 00 24 101 35 110 36 1110 47 11110 58 111110 69 1111110 710 11111110 811 111111110 9


____________________________________________________________________________Compressão - JPEG


� Considerações finais:

� JPEG define várias estratégias de compressão;

� Na estratégia básica é possível ao usuário configurar ofator de qualidade da compressão/descompressão(compromisso qualidade x taxa compressão).

� JPEG é apropriado para comprimir imagensfotográficastruecolor - 24 bits.

� JPEG não é apropriado para comprimir imagens comgrandes áreas de mesma cor (line-art & artworks).

� JPEG implementado em software pode se lento. Se umcompressão rápida é exigida pela aplicação é possívelencontrar no mercado soluções hardware.

Documents

Compressão - Unicampmartino/disciplinas/ea978/na4.pdf · arquivos de imagens que precisam ser armazenadas e/ou transmitidas em um canal de comunicação. O Processo de Compressão