Dct Slides

Transformada Discreta do Cosseno

Hugo Vieira Neto

UTFPR

17 de maio de 2010

Hugo Vieira Neto (UTFPR) Transformada Discreta do Cosseno 17 de maio de 2010 1 / 14


A Transformada Discreta do Cosseno (DCT) e utilizada no padraoJPEG de compressao de imagens para a exploracao da redundanciapsicovisual (com perdas), num processo conhecido como codificacaopor transformadas.

No padrao JPEG, o processo de codificacao por transformadasmapeia os pixels da imagem para um espaco de coeficientes maiscompacto e em seguida faz uso de uma etapa de quantizacao dessescoeficientes, antes de submete-los ao processo de geracao final dobitstream (ordenacao zig-zag e codificacao por entropia).



Transformada direta (8× 8): FDCT{f (x , y)} = F (u, v)

F (u, v) =14

C(u)C(v)7∑

x=0

7∑y=0

f (x , y) cos(2x + 1)uπ

16cos

(2y + 1)vπ16

Transformada inversa (8× 8): IDCT{F (u, v)} = f (x , y)

f (x , y) =14

7∑x=0

7∑y=0

C(u)C(v)F (u, v) cos(2x + 1)uπ

16cos

(2y + 1)vπ16

Onde: C(z) =

{1√2

se z = 01 se z 6= 0


Padrao de Ordenacao Zig-zag

F00 F01-

F10

��

F20?

F11

��

F02

��

F03-

F12

��

F21

��

F30

��

F40?

F31

��

F22

��

F13

��

F04

��

F05-

F14

��

F23

��

F32

��

F41

��

F50

��

F60?

F51

��

F42

��

F33

��

F24

��

F15

��

F06

��

F07-

F16

��

F25

��

F34

��

F43

��

F52

��

F61

��

F70

��F71-

F62

��

F53

��

F44

��

F35

��

F26

��

F17

��F27?

F36

��

F45

��

F54

��

F63

��

F72

��F73-

F64

��

F55

��

F46

��

F37

��F47?

F56

��

F65

��

F74

��F75-

F66

��

F57

��F67?

F76

��F77-


Padrao de Ordenacao Zig-zag

F00 = coeficiente DCF01 a F77 = coeficientes AC

Os 63 coeficientes AC de cada bloco sao reordenados em zig-zagvisando otimizar a etapa de codificacao por entropia (intermediaria +Huffman). Essa reordenacao coloca os coeficientes de baixafrequencia, com maior probabilidade de serem diferentes de zero,antes dos coeficientes de alta frequencia. Ja os coeficientes DC, querepresentam os valores medios de cada bloco de 64 pixels, saocodificados por meio de tecnicas preditivas, devido a forte correlacaoexistente entre os coeficientes DC de blocos adjacentes:

DIFF = DCi − DCi−1


Codificador Baseline JPEG

FDCT Quantizador

Tabela deQuantizacao

Codificador

Dados Comprimidos(Bitstream)

01101000...

Imagem Original(Blocos 8x8)

Tabela deCodificacao

6

----

6


Codificador Baseline JPEG Monocromatico

1 Adicao de linhas e colunas (multiplos de 8*)2 Deslocamento dos valores dos pixels:

[0,255]⇒ [−128,127]

3 Calculo da Transformada do Cosseno Direta4 Quantizacao:

FQ(u, v) = round[

F (u, v)

Q(u, v)

]5 Ordenacao zig-zag6 Codificacao intermediaria7 Codificacao de Huffman


Codificador Baseline JPEG Policromatico

Alem das etapas descritas anteriormente, a codificacao baselineJPEG policromatica necessita tratar adequadamente a informacao decor das imagens, isto e, em um codificador policromatico devem serrealizadas as seguintes etapas adicionais antes da Transformada doCosseno direta:

1 Conversao do espaco de cores RGB para o espaco de coresYCbCr

2 Subamostragem dos canais de crominancia (4:1:1)

*No caso de imagens policromaticas, a adicao de linhas e colunasdeve resultar em dimensoes multiplas de 16, devido ao uso dasubamostragem 4:1:1


Codificador Baseline JPEG Policromatico

Sao utilizadas tabelas de quantizacao e de codificacao diferenciadaspara os canais de luminancia (Y) e crominancia (Cb e Cr), com oobjetivo de otimizar ao maximo o fator de compressao obtido.

O bitstream e codificado na forma de uma sequencia de MCUs(minimum coded units), intercalando as informacoes dos canais Y, Cbe Cr para cada bloco da imagem.


Recapitulacao – Projeto Final de PDI

Implementar uma funcao imwrite para o Octave capaz de gerararquivos JFIF (Baseline JPEG) de imagens em cores a partir dematrizes genericas:

imwrite(A, ’imagem.jpg’, q)A funcao devera obrigatoriamente receber um parametro deselecao do grau de compactacao (qualidade) da imagem

No estagio atual do desenvolvimento do projeto, e importantıssimo lernovamente a documentacao disponıvel (referencias bibliograficas)


O que ja foi feito (Praticas 1 e 2)

?

-

-

-

?

-

Imagem YCbCr (M × N)

Imagem RGB (M × N)

ConversaoRGB para YCbCr

(rgb2ycbcr)

Imagem RGB de Entrada (H ×W )Ajuste de

Dimensoes(imfill)

Subamostragem

(imdec411)4:1:1

Componente Y (M × N)

Componente Cb (M/2× N/2)

Componente Cr (M/2× N/2)


O que deve ser feito agora (Pratica 7)

?

?

-

-

?

-

Transformada

Componente (Y, Cr ou Cr)

Discreta doCosseno

QuantizacaoTabela de Quantizacao

(luminancia / crominancia)

Blocos ordenados (Y, Cb ou Cr)

Blocos quantizados

Blocos de coeficientes

Blocos de pixels

Divisao emBlocos 8× 8

OrdenadorZig-zag


O que deve ser feito em seguida (Pratica 8)

?

?

-

?

-

-

-

Blocos ordenados (Y, Cb ou Cr)

Blocos RLE

OrganizadorJFIF

(DC / AC, luminancia / crominancia)Tabelas de Huffman

Blocos Huffman

Organizadorde MCU

Blocos MCU (4× Y + Cb + Cr) = bitstream

de HuffmanCodificacao

IntermediariaCodificacao

(×3)

(×3)

Arquivo JPEG/JFIFInformacoes adicionais

(dimensoes, tabelas, etc.)


Conclusao

Estes slides nao dispensam a consulta direta a bibliografiarecomendada (Wallace, 1992; CCITT, 1993; Hamilton, 1992)Nao sera necessaria a entrega do relatorio referente a pratica 7


Documents

Dct Slides