33
Waldeck Torres & Michele Hemerly Waldeck Torres & Michele Hemerly Waldeck Torres & Michele Hemerly Waldeck Torres & Michele Hemerly Waldeck Torres & Michele Hemerly Waldeck Torres & Michele Hemerly Waldeck Torres & Michele Hemerly Waldeck Torres & Michele Hemerly

Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

  • Upload
    others

  • View
    3

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Waldeck Torres & Michele HemerlyWaldeck Torres & Michele HemerlyWaldeck Torres & Michele HemerlyWaldeck Torres & Michele HemerlyWaldeck Torres & Michele HemerlyWaldeck Torres & Michele HemerlyWaldeck Torres & Michele HemerlyWaldeck Torres & Michele Hemerly

Page 2: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Índice

• Processo de Codificação do JPEG 2000

• Transformada de Ondulas (DWT)• Separação da Imagem em Blocos quantizados• Divisão da Freqüência em Sub-bandas• Quantização dos Blocos

• EZW - Codificação dos Coeficientes da WT • Codificação Aritmética Binária Adaptativa• Exemplos de varreduras do EZW

• Exemplos Práticos• Vantagens no uso do JPEG2000• Dificuldades de implementação do padrão JPEG2000• Slides de Suporte & Formulários

Page 3: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Processo de codificação do JPEG2000

JPEG 2000

DWT /Quantization

Entropy Coding in JPEG2000

ContextModeling CX

DImage

D: DecisionCX: Context

Code-BlockMemory

ArithmeticCoding

Output

CompressedData

DataOrdering

Page 4: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

A Transformada de Fourier x A Transformada de ôndulas

JPEG 2000

Sinal de 50 Hertz

Transformada de Fourier do Sinal de 50 Hz

A Transformada de Fourier apenas indicaquais são as freqüências que compõem O espectro

Page 5: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

A Transformada de Fourier x A Transformada de ôndulas

JPEG 2000

Sinal x(t)=cos(2*pi*10*t)+cos(2*pi*25*t)+cos(2*pi*50*t)+cos(2*pi*100*t)

Transformada de Fourier do Sinal ao Lado

Para Sinais cujas certas frequencias se repetem oprocesso é o mesmo, mas se as freqüências não se

Repetem, como saber a que momento ocorreu tais mudanças ?

Page 6: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

A Transformada discreta de ôndulas• Características da Transformada discreta Características da Transformada discreta Características da Transformada discreta Características da Transformada discreta de de de de ôndulasôndulasôndulasôndulas

• Cada transformada é computada separadamente para os diferentes segmentosdo sinal no domínio do tempo e nas diferentes freqüências em que eles foram coletados

• Resolução Multi-Análise : Analiza o sinal nas diferentes freqüências fornecendoresoluções diferentes e independententes uma das outras ( Anterior/Posterior )

• A Analise de Multipla Resolução foi projetada para fornecer uma rica resoluçãode de tempo e uma pobre resolução de freqüências nas frequencias mais altas nas componentes da imagem e uma rica resolução de freqüência e pobre resolução de tempo para as componentes de baixa frequencia da imagem

• Possui uma ótima aplicação para sinais que possuem componentes de altafreqüência para pequenas durações e grande quantidade de componentes de baixa freqüência por longa duração, tais como imagens em altaissima resolução e quadro de vídeo

Page 7: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

A Transformada de Fourier x A Transformada de ôndulas

Sinal Exemplo

Transformada de Ôndulas do Sinal exemplo

A Idéia da transformada de ôndulas é obter, além da composição das freqüências do sinal e sua amplitude como na transformada de fourier, o tempo em quando elas ocorrem durante o Período de amostragem. Por causa da sua natureza multiresolução inerente a transformada é utilizada em aplicações onde escalabilidade e tolerância a degradação é muito importante

A transformada de ôndulas são obtidas de umaôndula protótipo y(t) chamada de “ôndula mãe” e pela

dilatações e deslocamento da Formula:

)(1)(, abt

atba

−= ψψ

Onde ‘a’ é o parâmetro de resolução e ‘b’ é o parametro de deslocamento da ‘ondade amostragem’

Page 8: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

A Transformada discreta de ôndulas

Exemplos de “ôndulas de amostragem” da transformada de ôndulas de onde os coeficientes para a quantização são retirados para codificação posterior pela amostragem da “largura” da onda azul acima

Page 9: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

A Transformada discreta de ôndulas

Na transformadadiscreta de ôndulas o Tamanho da onda de amostra define a resolução da resultante final quanto maior “mais largo” o sinal Menor a resolução, mas menor o numero de coeficientes

Page 10: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Separação da Imagem em Blocos

Cada bloco quantizado sofre a codificação por entropia independentemente

Page 11: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Nível DC

Antes da computação da transformada discreta de ondulas para cada bloco, todas as amostras dos blocos tem o seu valor de DC desviado por subtração.

Page 12: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Divisão das freqüências em sub-bandas

A transformada discreta de ôndulas para uma imagem em 2-D

Page 13: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Divisão das freqüências em sub-bandas

Demonstração do que ocorre com a imagem com a codificação em sub-bandas

Page 14: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Aqui se vê a relação entre coeficientes em diferentes sub-bandas nas ‘arvores-quadruplas’.Para um “escaneamento” de 3 níveis, Cada nível possui 4 niveis inferiores de escaneamento

O EZW (embedded ZeroTree Wavelets) é um método eficiente de codificação para os coeficientes da transformada de ondulas pois explora as similaridades entre sub-bandas

EZW - Codificação dos coeficientes da WT

Page 15: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

As relações entre coeficientes das ôndulas nas diferentes subbandas (esquerda), fazendo a varredura (direita superior) e o resultado de usar os símbolos do zerotree (T) (na parte direita mais baixa) no processo de codificação.

Um H significa que o coeficiente é mais elevado do que o ponto inicial, e um L significa que está abaixo do ponto inicial. O símbolo do zerotree (T) substitui os quatro L’s na parte esquerda mais baixa e o L na parte esquerda superior.

EZW - Codificação dos coeficientes da WT

Page 16: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

EZW - Codificação dos coeficientes da WT

Outros metodos de escaneamento dos blocos quantizados são mostrados abaixo:

A Seqüência de bits resultante passada pelo corte na dominante e na subordinada é:D1: pnztpttttztttttttpttD1: pnztpttttztttttttpttD1: pnztpttttztttttttpttD1: pnztpttttztttttttptt............S5: 10111100110100010111110101101100100000000110110110011000111S5: 10111100110100010111110101101100100000000110110110011000111S5: 10111100110100010111110101101100100000000110110110011000111S5: 10111100110100010111110101101100100000000110110110011000111D6: zzzttztttztttttnntttD6: zzzttztttztttttnntttD6: zzzttztttztttttnntttD6: zzzttztttztttttnntttPor este método a passagem da subordinada no último nível, podem ser omitidas por que estas subordinadas já são de valor zero naquele momento, não fazendo sentido então executá-las.

Page 17: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Quantização dos blocos

• Os coeficientes obtidos são quantizados com valores independentes (Bloco por Bloco) .

• Cada um dos coeficientes (ab(u,v)) da sub-banda ‘b’ é quantizado para o valor qb (u,v) de acordo com a fórmula:

qb(u,v)=sign (ab(u,v))[ab(u,v) / qb(u,v)=sign (ab(u,v))[ab(u,v) / qb(u,v)=sign (ab(u,v))[ab(u,v) / qb(u,v)=sign (ab(u,v))[ab(u,v) / ∆b] ∆b] ∆b] ∆b] • A quantização do passo ∆b é representado em relação a faixa dinâmica da sub-

banda b. • Todos os coeficientes transformados tem seus valores ‘marcados’ em “zigue-zague”

mesmo que não sejam Compatíveis com os valores de quantização. Estes coeficientes são expressados numa determinada magnitude antes da codificação, para a reversibilidade da compressão, o ‘passo’ da quantização tem que ser de valor um.

• O uso do SPHIT (Set partitioning in hierarchical trees) é uma versão mais refinada que permite uma taxa de compressão maior do que o EZW original

EZW - Codificação dos coeficientes da WT

Page 18: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

O algoritmo EZW é baseado em 4 conceitos:

�transformada discreta de ondulas ou decomposição hierárquica em sub-bandas;

�predição da ausencia de informação significante através das escalas, explorando a auto-similaridade natural em imagens;

�quantização por aproximação sucessiva codificada por entropia;

�compressão sem perdas os quais é realizado via codificação aritmética adaptativa.

EZW – O Algoritmo de compressão

Page 19: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

EZW – O Algoritmo de compressão� Baseado em [3], o codificador é separado do modelo o qual é basicamente um

histograma

� Durante a passagem pela fase ‘dominante’ é feita a escolha de um dos histogramas dependendo

�Quando da varredura o coeficiente anterior é significante ou não�Quando o qradro ‘pai’ é conhecido como significante

� Na passagem subordinada um histograma simples é usado� Na relação da codificação do plano de bits (Mais Geral e Complexo) todos os

“thresholds” são potencia de 2 e todos os coeficientes são inteiros

� MSBD (Most-significant binary digit)�Durante a passagem ‘dominante’ os bits são marcados, sua posução é

mensurada e codificada�Bits Dominantes (dígitos à esquerda e incluindo o MSBD)

�Mensurado e codificado durante a passagem dominante�Bits Subordinados (digitos a direita do MSBD)

�Mensurado e codificado durante a passagem subordinada

Page 20: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Codificação Aritmética AdaptativaCodificação Aritmética AdaptativaCodificação Aritmética AdaptativaCodificação Aritmética Adaptativa

EZW - O Algoritmo de compressão

Page 21: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Exemplo Exemplo Exemplo Exemplo

� No exemplo abaixo vê-se somente uma carreira de simbolos (Sem a codificaçãoaritmética adaptiva)

� Foi usado uma transformada de ôndula simples de 3 escalas (níveis) de uma imagem de 8x8.

� T0 = 32 (Neste caso o maior coeficiente é 63)

Exemplo

15 14

49 10

3 -12-14 8

14 -13

-9 -7

63 -34 -31 23

5 -7

-12 7

3 93 2

6 -1

4 -2

7 13 3 4

3 6

-2 2

3 6-4 4

0 4

0 3

4 6 3 -2

2 -3

-1 47

6 4

5 6

-3 2

5 11

-5 93 0

EZW - O Algoritmo de compressão

Page 22: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

• Primeira passagem dominante

15 14

49 10

3 -12-14 8

14 -13

-9 -7

63 -34-31 23

5 -7

-12 7

3 93 2

6 -1

4 -2

7 13 3 4

3 6

-2 2

3 6-4 4

0 4

0 3

4 6 3 -2

2 -3

-1 47

6 4

5 6

-3 2

5 11

-5 93 0

EZW - O Algoritmo de compressãoExemplo Exemplo Exemplo Exemplo

Page 23: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

• Primeira passagem subordinada

15 14

49 10

3 -12-14 8

14 -13

-9 -7

63 -34-31 23

5 -7

-12 7

3 93 2

6 -1

4 -2

7 13 3 4

3 6

-2 2

3 6-4 4

0 4

0 3

4 6 3 -2

2 -3

-1 47

6 4

5 6

-3 2

5 11

-5 93 0

As magnitudes são particionados dentrode intervalos de incertezas [32, 48) e [48, 64), com simbolos “0” e “1”.

EZW - O Algoritmo de compressãoExemplo Exemplo Exemplo Exemplo

Page 24: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

A Imagem ‘Lena’

(a) (b) (c)(a) Original Image256x256Pixels, 24-BitRGB (b) JPEG (DCT) Compressed with compression ratio 43:1(c) JPEG2000 (DWT) Compressed with compression ratio 43:1

Exemplos Práticos

Page 25: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

�A foto do Porsche foi salva em JPEG com Quality=30, gerando um arquivo de 77.756 bytes (76 Kb)

�CONCLUSÃO: diferença perceptível entre os dois arquivos: veja a mola vermelha

Exemplos Práticos

Page 26: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Agora a ilustração do Porsche foi salva em JPEG com Quality=0, gerando um arquivo de 38.664 bytes (38 Kb)

CONCLUSÃO: grande diferença: a imagem do arquivo JPEG2000 é muito mais detalhada nos detalhes menores (mola e reflexo dos tubos)

Exemplos Práticos

Page 27: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

�A compressão do JPEG2000 oferece várias vantagens de performance e implementação em se comparado com outros métodos;

�Com uma metodologia de compressão totalmente diferente do JPEG, o JPEG2000 consegue diminuir em média 50% o tamanho de uma imagem .jpg, sem que se perceba diferenças entre as imagens finais;

�Pode utilizar a compressão lossless (que permite compactar imagens sem perda de qualidade) e o Motion JPEG2000 (animação no formato JPEG2000);

�As imagens JPEG2000 mantêm a definição das imagens mesmo em baixa resolução. Isso demonstra que uma utilidade muito grande na Web, aonde as imagens poderão ser muito menores sem perderem a sua qualidade;

�O formato dos pacotes formados pela compressão dos dados faz com que a decodificação se torne algo mais simples.

Vantagens do JPEG2000

Page 28: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Dificuldades de Implementação do Padrão JPEG2000

Complexidade de implementação:

�A complexidade do cálculo da Transformada discreta de ôndulasdepende do “comprimento” dos filtros das ôndulas, que implica em, no mínimo, uma multiplicação por coeficiente

�Os métodos de Codificação EZW, utilizam valores em ponto-flutuante que inerementemente possui um maior ‘comprimento’ de dados e por conseqüência o ‘custo’ da computação.

�Comparativamente o JPEG2000, pelo uso da Transformada discreta de ôndulas, possui um chipset mais “caro” em comparação a um chip para o processamento de uma imagem JPEG usando DCT, como se pode ver na tabela, com um chip ASIC:

Tipo de Codificador ASIC

No. de portas lógicas necessárias

Quantidade de RAM por Codificador

Taxa de Processamento de dados

DCT 34000 128 byte 210 MSa/sec

DWT 55000 55 kbytes 150 MSa/sec

Page 29: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto
Page 30: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Slides de Suporte & FormuláriosA transformada 1-D é dado por:

A Transformada inversa 1-D é dada por:

Page 31: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Slides de Suporte & Formulários

A Transformada discreta de ôndulas, que transforma um sinal discreto no tempo para uma representação de ôndula e que converte a serie de ‘entradas’ x0, x1, ..xm nas séries de coeficientes de faixa-alta e faixa-baixa ( com um comprimento de n/2, cada), é dados por:

Onde: sm(Z) e tm(Z) São chamados de filtros de ôndulas, K ë o comprimento do filtro, e i=0, ..., [n/2]-1.

Page 32: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Slides de Suporte & Formulários

O esquema de deslocamento duplo:

Onde si(z) (Primeiros passos do deslocamento) e ti(z) (Passo de deslocamento duplo) São filtros e K é uma constante. Como esta fatoração não é única múltiplos {si(z)}, {ti(z)} e K São admissíveis:

Page 33: Waldeck Torres & Michele Hemerlydebora/fsmm/trab-2005-1/apres_jpeg...direita mais baixa) no processo de codificação. Um H significa que o coeficiente é mais elevado do que o ponto

Referências

Referencias dos Slides http://www.ii.metu.edu.tr/em2003/EM2003_presentations/DSD/benderli.pdfhttp://www.etro.vub.ac.be/Members/munteanu.adrian/_private/Conferences

/WaveletLosslessCompression_IWSSIP1998.pdfhttp://www.vlsi.ee.upatras.gr/~sklavos/Papers02/DSP02_JPEG200.pdfhttp://www.vlsilab.polito.it/Articles/mwscas00.pdfM. Martina, G. Masera , A novel VLSI architecture for integer wavelet

transform via lifting scheme, Internal report, VLSI Lab., Politecnico diTor i no, Jan. 2000, ( Não publicado)

http://www.ee.vt.edu/~ha/research/publications/islped01.pdf3. I. H. Witten, R. Neal, and J. G. Cleary, “Arithmetic coding for data

compression,” Comm. ACM, vol. 30, pp. 520-540, June 1987