Técnicas de Codificação de Áudio e Vídeocabm/pds/PDS_Aula10_Video_Audio.pdf · Carlos Alexandre Mello – [email protected] 26 Compressão de Vídeo Redução de Redundância

1 Carlos Alexandre Mello – [email protected]

Técnicas de Codificação de Áudio e

Vídeo

Carlos Alexandre Mello


Compressão de Dados



Introdução

Compressão de Dados

Espaço de Armazenamento

Velocidade de Transmissão

Teoria de Códigos

Teoria da Informação

Claude Shannon

Algoritmos de Compressão

Estáticos ou Dinâmicos

Com Perda ou Sem Perda

3


Algoritmos de Compressão

Sem Perdas

Run-Length

Huffman

Lempel-Ziv

Com Perdas

Wavelets

Quantização Vetorial

4


Introdução

Motivação:

Para que compressão?

Um vídeo é uma sequência de quadros (frames)

Em boa qualidade, um vídeo tem 30 fps

Se cada frame corresponde a uma imagem de

640x480 pixels, com 24 bits/pixel, precisaríamos de

27MB para cada segundo de vídeo

5


Teoria dos Códigos

De Comprimento Variável

De bloco

Singular

Não-singular

Não-unicamente decodificáveis

Unicamente decodificáveis

Instantâneos

Não-instantâneos

6


SINGULAR

NÃO INSTANTÂNEO INSTANTÂNEO

UNICAMENTE DECODIFICÁVEL NÃO UNICAMENTE DECODIFICÁVEL

NÃO-SINGULAR

BLOCO COMPRIMENTO VARIÁVEL

CÓDIGO

Teoria dos Códigos

7


Teoria dos Códigos

Bloco

A = 00

B = 010

Comprimento variável

A = 00 ou 1

O comprimento pode variar dentro na

codificação de uma mesma palavra

8


Teoria dos Códigos

Não singulares

Todas as palavras do código são distintas

A = 00

B = 01

Singulares

A = 00

B = 00

C = 01

9


Teoria dos Códigos

Não-Unicamente Decodificável

A = 0

B = 1

C = 01

Como decodificar a sequência: 0101

ABC, ABAB, CC, CAB

Unicamente Decodificável

10


Teoria dos Códigos

Instantâneo

Não depende de informações futuras

Não-Instantâneo

Depende de informações futuras

A = 10

B = 100

C = 1000

D = 10000

Como decodificar 101001000

11


Teoria dos Códigos Prefixo

Uma condição necessária e suficiente para

um código ser unicamente decodificável é

que nenhuma palavra completa do código

seja prefixo de outra palavra qualquer.

12


Teoria dos Códigos Desigualdade de Kraft

Garante que um código com palavras com

comprimento Li é instantâneo

q

i=1

r -Li

1

Exemplo: Considere o código A = 0 comprimento Li=1 B = 01 comprimento Li=2 C = 11 comprimento Li=2 Número binário base r=2

Ou seja, 2-1+2-2+2-2=1

13


i=1

r -Li

1

Teoria dos Códigos Desigualdade de McMillan

Garante que um código com palavras com

comprimento Li é unicamente decodificável

q

14


i=1

Pi*Li

q

L =

Teoria dos Códigos Comprimento Médio

Um código é dito compacto para uma

fonte S se seu comprimento médio é menor

ou igual ao comprimento médio de todos os

outros códigos unicamente decodificáveis

para a mesma fonte S.

15


C =

COMPRIMENTO DO ARQUIVO

ORIGINAL

COMPRIMENTO DO ARQUIVO

COMPACTADO

Teoria dos Códigos Taxa de Compressão

16

Em geral, mas não é apropriado para imagens....


Algoritmos de Codificação

Algoritmos de compressão sem perda

Run-Length

Código de Huffman

Lempel-Ziv-Welch

17

Usados em codificação

de Áudio e Vídeo


Algoritmos de Codificação Run-Length

Contagem de carreiras de símbolos de

mesmo valor

Codificação: <contador, símbolo>

Exemplo:

120 120 120 30 45 45 45 60

Codificação:

<3, 120> <1, 30> <3, 45> <1, 60>

18


Algoritmos de Codificação Lempel-Ziv Welch [1984]

Variação do Lempel-Ziv desenvolvida por

Terry Welch

Implementada no formato GIF para

armazenamento de imagens

19


INICIALIZA DICIONÁRIO

[Prefixo] <- 0

C RECEBE O PRÓXIMO SÍMBOLO NO CÓDIGO

[Prefixo]C ESTÁ NO DICIONÁRIO?

SIM: [Prefixo] RECEBE [Prefixo]C E VOLTA A (3)

NÃO:

[Prefixo]C É ACRESCENTADO AO DICIONÁRIO

SAÍDA RECEBE CÓDIGO DE [Prefixo]

[Prefixo] <- C E VOLTA A (3)

Lempel-Ziv Welch Esquema de Codificação


Dicionário básico:

X = #0

Y = #1

Z = #2

W = #3

Entrada do codificador:

XYXZXYXW

Algoritmos de Codificação Algoritmo de Lempel-Ziv-Welch

21


Codificação Final

#0#1#0#2#4#0#3

Dicionário

X = #0 Y = #1

Z = #2 W = #3

XY = #4 YX = #5

XZ = #6 ZX = #7

XYX = #8 XW = #9

Algoritmos de Codificação Lempel-Ziv-Welch

22


Decodificação

#0#1#0#2#4#0#3

Dicionário Básico

X = #0 Y = #1

Z = #2 W = #3

Algoritmos de Codificação Lempel-Ziv-Welch

23


Compressão de Vídeo




A fim de avaliar sistemas de compressão de

vídeo, os seguintes parâmetros devem ser

considerados quanto ao desempenho da

compressão:

Taxa de compactação

Qualidade da Imagem

Velocidade da compactação e descompactação

25



Redução de Redundância

Algumas áreas do frame possuem a mesma cor que se

espalha por mais de um pixel (redundância espacial);

Quando a cena ou parte dela contém

predominantemente objetos orientados verticalmente

existe grande probabilidade que duas linhas adjacentes

sejam as mesmas (redundância espacial);

Imagens onde alguns pixels se repetem por diversos

frames (redundância temporal).

26



Redundância

Espacial

Redundância

Temporal

27



Artefatos de codificação/transmissão

Motion blur

28




Blocking

29




Ringing

30




Aliasing

31




Judder

32




Outros artefatos

33




Problemas de imparidade temporal

Freezing

34



Outras questão: avaliação subjetiva do ser

humano

Um freezing de 1 seg é igual a 10 de 0,1 seg?

Um borramento no centro da imagem é igual a

um borramento no canto?

Ou seja, é preciso avaliar o quão “agressivo”

um artefato é para a percepção humana

35


Compressão de Vídeo Principais Técnicas

Color LookUp Table

Run-Length

Interpolação

Predição (DPCM, ADPCM)

Uso de Transformadas (DCT)

Codificação Estatística (Huffman)

36



Padrão de Cores

RGB comum para imagens

MPEG usa o YCbCr Mais apropriado para percepção do sistema visual

humano

RGB -> YCbCr Y = 0,299R + 0,587G + 0,114B

Cb = -0,1687R – 0,3313G + 0,5B + 128

Cr = 0,5R -0,4187G -0,0813B + 128 (120; 60; 30)RGB -> (74,52; 102,88; 160,44)YCbCr

37



O padrão MPEG especifica 3 tipos de quadros comprimidos no arquivo de saída:

Nos quadros I (Intraframe) somente se aplicam algoritmos de redução de redundância espacial

Nos quadros P (Predicted) e B (Bidirectionally Predicted) também se aplicam algoritmos de redução de redundância temporal

No caso dos quadros B a predição de movimento é bidirecional, ou seja, é feita com quadros no passado e no futuro em relação ao quadro sendo codificado

38


Compressão de Vídeo Algoritmos - MPEG

Diferentes taxas de compressão nos

quadros

I = 10-20:1

P = 20-30:1

B = 30-50:1

39



Quanto maior a compressão, maiores as

perdas de qualidade sofridas nos quadros

Por isso, há a necessidade de intercalar

quadros I de tempos em tempos para permitir

a “restauração” da qualidade do sinal e

também acesso aleatório aos quadros do

filme

40



41

I B B P B B P …



A predição bilateral é importante para

utilizar informações de elementos que não

estão presentes em frames anteriores

42



Também fazem parte do padrão:

DCT + Quantização + Run-Length

Redução de Redundância Espacial

Motion Estimation e Motion Compensation

(MEC) preditiva e interpolativa

Redução de redundância temporal

Uso de Codificação de Huffman

Compressão efetivamente

43



A DCT faz uma transformação na imagem,

mudando o domínio de representação da

mesma

Este processo não introduz perdas de qualidade

na imagem, sua utilização se dá porque ela

permite uma representação mais compacta da

imagem, facilitando a compressão

O uso da DCT faz com que as maiores

frequências se concentrem no canto superior

esquerdo da matriz

44




DCT

45

Bloco da imagem (YCbCr) Resultado após DCT




DCT

Exemplo: imagem inteira

46




DCT

Perdas

47



Após a aplicação da DCT, uma

quantização é feita tomando uma matriz

de quantização fixa

Cada valor da matriz gerada pela DCT é

dividido pelo valor correspondente na

máscara de quantização e arredondado

para um inteiro

48




Quantização

49

Matriz de quantização Bloco quantizado




Run-Length

Objetivo: agrupar os valores nulos

Dada a disposição deles, usa-se uma leitura em

zig-zag

50



Motion Estimation e Motion Compensation

(MEC) preditiva e interpolativa

51

Quadro m Quadro m+1

Não mudou…

Mudou…



Avaliação de codificação

Packet loss

Avaliação de rede

Imparidade temporal

Para um vídeo contínuo, difícil de avaliar, pois

pode ser um vídeo sem movimento

Qualidade visual

52



Avaliação de codificação

Qualidade visual

Full Reference

Reduced Reference

No Reference

53



Avaliação de codificação No Reference

BLIINDS

VIIDEO

Difíceis de desenvolver (modelam a percepção

humana)

Geram uma estimativa de qualidade

Muitas aplicações

54



Avaliação de codificação Full Reference

SSIM (e variações) – Structure Similarity Index

Avaliação de qualidade de imagem..

55


O que é Qualidade?

Qual dessas é a melhor imagem?

Original

JPG 80%

JPG 30%

JPG 90% sobre

a de 80%


O que é Qualidade?

Pior ainda!! Está imagem é de boa

qualidade??


O que é Qualidade?

Qual a diferença entre os dois exemplos

anteriores?

Qualidade x Fidelidade


Avaliação de Fidelidade

Comparação entre a Imagem de Referência

e a Imagem Alvo

Comparação Pixel-a-Pixel

Diversas medidas existentes:

MOS (Mean Opinion Score)

MSE (Mean Square Error)

PSNR (Peak Signal to Noise Ratio)

ANOVA (Analysis of Variance)

Aplicada sobre o cálculo de propriedades das imagens



MOS (Mean Opinion Score)

Avaliação Subjetiva

Pessoas observam as imagens e atribuem valores: 1 – Ruim

...

5 – Excelente

Impensável quando falamos de grandes acervos de imagens!!

Dependente do usuário



MSE (Mean Squared Error)

Raiz quadrada do Somatório do quadrado de

erros pontuais

200 177

20 99

201 176

18 101

Erro = 1 Erro = -1

Erro = -2 Erro = 2

MSE = 12 + (-1)2 + (-2)2 + 22 = 10 = 3,16



MSE (Mean Squared Error)

Problema: E se a imagem estiver deslocada de

um pixel apenas?



Diferença

Alto MSE !!



MSE (Mean Squared

Error)

Problemas

Imagem

Original



PSNR

Medida logarítmica baseada em MSE

ANOVA

Análise de diferenças estatísticas entre

imagens

Diz se existem diferenças estatisticamente

significantes ou não

Baseada no cálculo e avaliação de parâmetros

(média, desvio padrão, energia, entropia, etc)



Fidelidade de Imagens

Índice de Z.Wang et al

Z.Wang, A.C.Bovik and Ligang Lu. A Universal

Quality Index, IEEE Signal Processing Letters, Vol. 9,

no. 3, pp. 81-84, 2002



Aplicação: Avaliação de Perda de JPG

Imagem Original JPG 15% de perda JPG 30% de perda

JPG 80% de perda JPG 90% sobre 80% de perda



Aplicação: Avaliação de Perda de JPG

Valores do Índice de Z.Wang:

Comparação com a imagem original



Aplicação a Vídeo

VSSIM

Comparação entre vídeos

Full reference

Para aumentar o tempo de processamento, janelas

aleatórias são definidas para avaliar os frames

As janelas devem ter alto contraste

Vídeo em YCbCr

SSIM roda em cada componente e uma média ponderada é

usada posteriormente para definir o score final



Aplicação a Vídeo

VSSIM

Vantagem: Fácil de computar

Desvantagem: Não é sensível a imparidades

temporais

Variações

MSSSIM, 3-SSIM, stSSIM, GSSIM

Validação feita com o MOS

Bases: VQEG Phase I, LIVE VQA, ReTRiEVED, ...


Chroma Subsampling

É um tipo de compressão que reduz a informação

de cores em um sinal, favorecendo os dados

relacionados a luminância

Isso reduz a necessidade por largura de banda

sem afetar significativamente a qualidade da

imagem

Um sinal de vídeo é dividido em dois: informação

de cor e informação de luminância


Chroma Subsampling

Luminância (luma): Define a maior parte da imagem já que as formas que notamos são formadas pelo contraste entre cores Considere uma imagem em tons de cinza, por exemplo

Crominância (chroma): Define a informação da cor propriamente dita

Chroma subsampling reduz a quantidade de informação de cor, mantendo a informação de luma No modelo YUV, luma é apenas 1/3 do sinal; assim, há

bastante redução nos dados...


Chroma Subsampling

Luminância e Crominância


Chroma Subsampling

4:4:4 vs 4:2:2 vs 4:2:0

O primeiro número (4) é o tamanho da amostra

Os números seguintes se referem ao chroma,

estão relacionados com o primeiro número e

definem a amostragem horizontal e vertical

Um sinal com chroma 4:4:4 não tem compressão

e carrega as informações de chroma e luma

completamente


Chroma Subsampling

4:4:4 vs 4:2:2 vs 4:2:0

Um sinal com chroma 4:2:2 tem metade do

chroma de 4:4:4, metade da taxa de amostragem

na horizontal, mas mantém a amostragem na

vertical


Chroma Subsampling

4:4:4 vs 4:2:2 vs 4:2:0

Um sinal com chroma 4:2:0 tem um quarto do

chroma de 4:4:4, amostra cores em metade dos

pixels da primeira linha e ignora a segunda linha

da amostra completamente


Chroma Subsampling

4:4:4 vs 4:2:2 vs 4:2:0


Chroma Subsampling

4:4:4 vs 4:2:2 vs 4:2:0

Comparação:

4:4:4

4:2:2

4:2:0


Chroma Subsampling

4:4:4 vs 4:2:2 vs 4:2:0

Apesar da baixa qualidade, o formato 4:2:0 é bastante utilizado em padrões internacionais

A questão aqui é que as falhas muitas vezes não são percebidas em imagens em movimento

Usualmente, uma câmera captura uma imagem em 4:4:4, converte para 4:2:2 via filtragem e amostragem horizontal e então para 4:2:0 via nova filtragem e amostragem vertical


Chroma Subsampling

4:4:4 vs 4:2:2 vs 4:2:0

Ambas as filtragens são feitas através de

filtros FIR


Compressão de Áudio



Compressão de Áudio Algoritmos – Blocos de Silêncio

Blocos de silêncio são marcadores que contêm

um valor de duração do tempo que representa a

extensão do silêncio ou quase silêncio

Janela de

Silêncio

Dados de Silêncio

82



Semelhante ao Run-Length

Usado em arquivos VOC

Silêncio é definido como a amplitude da forma

de onda que não ultrapassa a janela de silêncio

Uma extensão de silêncio menor que a janela é

considerada muito curta para merecer a conversão

para bloco de silêncio

Problema: 1) Os blocos de silêncio não existem

na maioria dos sons gravados

83



Problema: 2) Difícil distinguir silêncio do

início de alguns sons (para sinais de voz)

Como os fricativos inaudíveis (/f/, /s/, /sh/)

84

Início do som /s/ da palavra “Sapo”


Compressão de Áudio Algoritmos – MP3 – MPEG-1 Layer 3

Terceira camada do formato MPEG-1

Destinada a codificação de áudio

Taxa de compressão: 10:1, podendo

chegar até 12:1

Uso de elementos de psicoacústica

85



Um erro comum é confundir o MP3 com

MPEG-3. MPEG-3 é um formato morto,

pois o formato MPEG-4 o suplantou com

muitas vantagens

Enquanto o MPEG-3 deveria ter sido um

formato para compressão tanto de áudio

como de vídeo, o MP3 responde apenas

pela compressão de áudio do MPEG-1

86



A utilização dos limites da audição

humana baseia-se em três princípios

básicos:

Faixa de frequência audível dos seres

humanos;

Limiar de audição na faixa de frequência

audível;

Mascaramento em frequência e

mascaramento temporal

87




humanos

O ouvido humano, devido às suas limitações

físicas, é capaz de detectar sons em uma

faixa de frequência que varia de 20 Hz a 20

KHz, sendo que estes valores podem variar

de indivíduo para indivíduo e também com a

idade (com o envelhecimento perdemos a

capacidade de ouvir frequências mais altas)

88



Faixa de frequência audível dos seres humanos

Desta forma, não faz sentido armazenar dados referentes a sons fora desta faixa de frequência, pois ao serem reproduzidos, os mesmos não serão percebidos por um ser humano.

Esta é a primeira limitação da audição humana do qual o sistema MP3 faz uso para alcançar altas taxas de compressão.

89




humanos

De acordo com o Teorema de Nyquist, para

garantir a reprodução de um sinal, temos de

amostrá-lo pelo menos a duas vezes sua

frequência máxima

Ou seja, neste caso, como a frequência

máxima de interesse é 20 KHz, basta

amostrar a 40 KHz

90



Faixa de frequência audível dos seres humanos

Utiliza-se 44.100 Hz como taxa de amostragem, pois

leva-se em consideração uma tolerância e busca-se

um valor produto dos quatro primeiros números

primos ao quadrado

Obs: (2x3x5x7)2 = 44100

Desta forma, esta taxa de amostragem funciona como

um filtro passa-baixa, que remove todos os

componentes de frequência fora da faixa de interesse,

neste caso, acima de 20 Khz

91



Limiar de audição na faixa de frequência

audível

Outro fator utilizado pela codificação MP3 é a

curva de percepção da audição humana

dentro da faixa de frequências audíveis, ou

Limiar de Audição

Apesar da faixa de audição humana variar

entre 20 Hz e 20 KHz, a sensibilidade para

sons dentro desta faixa não é uniforme

92



Limiar de audição na faixa de frequência audível

Ou seja, a percepção da intensidade de um som varia com a frequência em que este se encontra

Por isso, o MP3 utiliza-se desta propriedade para obter compressão em arquivos de áudios

Esta abordagem é bastante intuitiva, sendo que o que se faz é descartar amostras que se encontrem abaixo deste limiar

93



Mascaramento em frequência e mascaramento

temporal

Por fim, uma última propriedade da audição humana

ainda é utilizada pelo método é o chamado

mascaramento auditivo, ou “audiabilidade diminuída

de um som devido à presença de outro”, podendo

este ser em frequência ou no tempo

O mascaramento em frequência ocorre quando um

som que normalmente poderia ser ouvido é

mascarado por outro, de maior intensidade, que se

encontra em uma frequência próxima

94



Mascaramento em frequência e mascaramento temporal

O mascaramento em frequência depende da frequência em que o sinal se encontra, podendo variar de 100 Hz a 4 KHz

Em função deste comportamento, o que o método de compressão do MP3 faz é identificar casos de mascaramento em frequência e descartar sinais que não serão audíveis devido a este fenômeno

95



Mascaramento em frequência e mascaramento temporal O mascaramento no tempo ocorre quando um som forte é

precedido por um mais fraco que se encontra em uma frequência próxima à do primeiro

Se o intervalo de tempo entre os dois for suficientemente pequeno, este som mais fraco não será percebido pela audição humana

Se um som é mascarado após um som mais forte, temos o chamado pós-mascaramento

No caso de um som ser mascarado antes do som mais forte, temos o que chamamos de pré-mascaramento

O pré-mascaramento existe só por um curto momento, cerca de 20ms, enquanto que o pós-mascaramento tem efeito por até 200 ms

96


Técnicas de Codificação de Áudio e

Vídeo

Referências:

The Essential Guide to Video Processing,

A.C.Bovik, Academic Press, 2009

A Practical Guide to Video and Audio

Compression, C.Wootton, Focal Press, 2005

Introduction to Information Theory and Data

Compression, D.Hankersson, CRC Press, 2003

97

Documents

Técnicas de Codificação de Áudio e Vídeocabm/pds/PDS_Aula10_Video_Audio.pdf · Carlos Alexandre Mello – [email protected] 26 Compressão de Vídeo Redução de Redundância