Codificação de Informação 2010/2011 JPEG com perdas

10/19/10
Codificação
de
Informação
2010/2011
Sumário:
• As
normas
JPEG
• Compressão
de
video
• redundância
espacial
e
temporal
• normas
MPEG
JPEG
com
perdas
Processamento
em
várias
fases
• Divisão
em
blocos
de
8x8
pixels
(macroblock)
• DCT:
transforma
a
imagem
do
domínio
espacial
para
um
sinal
equivalente
no
domínio
da
frequência
(sem
perdas)
• Arredonadamento
e
mudança
de
escala
(com
perdas)
• Codificação
RLE
e
Huffman
(sem
perdas)
19/10/09
2
1
10/19/10
Preparação
da
imagem
• Sinal
Rs,
Gs,
Bs
converYdo
para:
• Luminância
YS
=
0,299*Rs
+
0.587*Gs
+
0.114*Bs
• Crominância
Azul
Cb
=
Bs
‐
Ys
• Crominância
Vermelha
Cr
=
Rs
–Ys
• O
olho
humano
não
é
sensível
a
variações
rápidas
de
crominância
• Passa‐se
de
3
matrizes
NxN,
para
uma
matriz
NxN
(luminância)
e
duas
de
(N/2)*(N/2)
para
as
crominâncias
19/10/09
3
Preparação
da
imagem
19/10/09
4
2
10/19/10
DCT
–
Discrete
Cosine
Transform
• Para
a
luminância,
em
cada
bloco
o
valor
é
converYdo
de
valores
0…255
a
‐128…+127
• A
cada
bloco
é
aplicada
a
transformação
DCT
com
o
objecYvo
de
obter
uma
representação
mais
compacta
dos
dados
iniciais
• Transformação
da
matriz
8x8
numa
outra
(também
de
8x8):
– Sem
perdas
– Preparação
para
fases
posteriores
19/10/09
5
DCT
–
Discrete
Cosine
Transform
Função
que
transforma
uma
matriz
8x8
noutra
matriz
8x8
P[8][8]:
matriz
da
luminância
ou
crominância
de
um
macro‐bloco
T[8][8]:
matriz
obYda
por
aplicação
da
transformação
DCT
19/10/09
6
3
10/19/10
DCT
–
Discrete
Cosine
Transform
A
matriz
T
contém
um
conjunto
de
valores
chamado
frequências
espaciais.
As
frequências
espaciais
reflectem
quanto
é
que
o
valor
da
luminância
varia
de
acordo
com
a
sua
posição
no
bloco
• T[0][0]
é
o
coeficiente
DC
e
está
relacionado
com
o
valor
médio
dos
valores
P[i][j]
• Para
qualquer
T[i][j]
há
contribuição
de
todos
os
P[x][y]
• Para
i
!=
0
e
j!=
0,
T[i][j]
são
os
coeficientes
AC;
para
valores
maiores
de
i
e
j,
os
valores
são
mulYplicados
por
funções
coseno
com
período
mais
curto
(ou
frequência
mais
elevada)
19/10/09
7
DCT
–
Contribuições
de
cada
coeficiente
X[0,7]
X[0.0]
X[7.0]
19/10/09
X[7,7]
8
4
10/19/10
DCT
–
Discrete
Cosine
Transform
• DCT
decompõe
cada
bloco
da
imagem
de
entrada
numa
série
de
formas
de
onda,
cada
uma
com
a
sua
frequência
espacial
parYcular
• ParYndo
do
canto
superior
esquerdo
(frequência
espacial
nula),
a
frequência
verYcal
vai
aumentado
à
medida
que
nos
deslocamos
para
baixo
e
a
horizontal
aumenta
para
o
lado
direito
• DCT
calcula
o
peso
associado
a
cada
uma
das
64
funções
de
base
de
modo
a
permiYr
que
o
somatório
das
64
formas
de
onda
às
quais
se
aplicou
o
respecYvo
factor
de
escala,
resulte
na
versão
reconstruída
do
bloco
da
imagem
original.
19/10/09
9
DCT
–
Discrete
Cosine
Transform
• Suponha‐se
um
macrobloco
com
valores
constantes:
P[x][y]
pode
ser
posto
em
evidência
e
todos
os
coeficientes
AC
são
nulos
• Se
houver
poucas
variações,
muitos
(mas
não
todos
os)
coeficientes
AC
anulam‐se
• Se
há
muita
variação
de
P[x][y]
nenhum
coeficente
AC
se
anula
19/10/09
10
5
10/19/10
DCT
–
Discrete
Cosine
Transform
20 30 40 50 60 70 80 90
30 40 50 60 70 80 90 100
40 50 60 70 80 90 100 110
50 60 70 80 90 100 110 120
60 70 80 90 100 110 120 130
70 80 90 100 110 120 130 140
80 90 100 110 120 130 140 150
90 100 110 120 130 140 150 160
1 -182 0 -19
-182
0 0
0
0
0 0
0
-19
0 0
0
0
0 0
0
0
0 0
0
-1
0 0
0
0
0
0
0
0
0
0
-6
0
0
0
0
0
0
0 1
0 0
0 0
0 0
0 0
0 0
0 0
DCT
Valores de P variam uniformemente; muitos coeficientes AC
são 0 – imagem não tem variações rápidas
19/10/09
11
DCT
–
Discrete
Cosine
Transform
100 150 50 100 100 150 200 120
2 10 110 20 200 120 30 120
10 200 130 30 200
5
20 150 50
10 200 200 120 90 190 20 200
70 10 100
5 -56
69
-38
3 -60 -36 11
14 -60
-71
110
130 105 -37 81
-17
24
-27
-48
5 -3
6 -71 -24 -56 -40 -36
-23 -18
9 30 150 10 10 120 190 10
120 120 50 100 10 190
15 -17 59
-32 -9
10 90 190 120 200 10 10
150 120 20 200 150
1 8 10 120
13
32 -14
27 -12
4 54
-37 -53
30 28
-66 152
67 -189
-61
35
15 -80 -185
-62
52 -93 -210 -48
-76
80
DCT
Valores
de
P
variam
muito
ao
longo
da
imagem
–
corresponde
a
uma
zona
com
muitas
variações
rápidas.
Os
coeficientes
AC
são
não
nulos
19/10/09
12
6
10/19/10
DCT
–
Discrete
Cosine
Transform
Quando
a
luminância
varia
muito,
os
coeficientes
AC
não
são
nulos;
estes
coeficientes
são
uma
medida
da
variação
entre
pixels
Uma
imagem
com
poucas
variações
será
mais
fácil
de
comprimir
que
uma
imagem
com
muitos
detalhes.
DCT
não
tem
perdas
(a
menos
dos
arredondamentos).
A
parYr
das
frequências
espaciais
é
possível
reconstruir
o
valor
dos
pixels
19/10/09
13
QuanYficação
• Para
efectuar
uma
digitalização
eficiente
é
necessário
reduzir
o
número
total
de
valores
diferentes
• Fase
com
perdas
Para
i
e
j
de
0
a
7
A
escolha
da
matriz
Q
tenta
fazer
o
melhor
compromisso
entre
a
qualidade
da
imagem
e
a
taxa
de
compressão
conseguida
19/10/09
14
7
10/19/10
QuanYficação
e
Codificação
Consideremos
3
casos
para
as
tabelas
e
quanYficação:
• Matriz
unitária:
nada
se
altera,
não
há
perdas
• Matriz
com
todos
os
elementos
iguais:
mudança
de
escala
e
portanto
há
perda
de
informação;
reduz
o
nº
de
valores
diferentes
e
favorece
a
codificação
contextual
e
esta|sYca
que
se
segue
• Matriz
com
valores
pequenos
perto
da
origem
e
maiores
longe:
torna
muito
pequenos
(provalvelmente
0)
os
coeficientes
que
estão
longe
da
origem.
Esses
coeficientes
são
os
que
representam
variações
rápidas
da
imagem.
Ao
perder‐se
essa
conYbuição
as
variações
rápidas
desaparecem
(o
olho
humano
é
pouco
sensível
a
essas
variações)
19/10/09
15
QuanYficação
Aplicação
da
tabela
de
quanYficação
19/10/09
16
8
10/19/10
Tabelas
de
quanYficação
19/10/09
17
Tabela
de
quanYficação
e
qualidade
de
imagem
Original
–
11K
19/10/09
Qualidade
050
–
2K
Qualidade
100‐1K
18
9
10/19/10
Codificação
esta|sYca
Coeficientes
DC
• Q[0][0]
• Codificados
de
forma
diferencial
em
relação
ao
coeficiente
DC
do
bloco
anterior
Coeficientes
AC
• Todos
os
que
não
são
o
Q[0][0]
• RLE
com
percurso
em
Zig
Zag.
• Codificação
de
Huffman
• Formato:(
nº
zeros,
nº
repeYções)
valor
• Codificação
de
Huffman
aplicada
a
estes
termos
19/10/09
19
RLE
• Codificação
em
zig‐zag
• RLE
obtém
muito
melhores
resultados
19/10/09
20
10
10/19/10
Descodificação
JPEG
19/10/09
21
Fluxo
JPEG
Cabeçalhos
Tabelas
Tabelas
de
quanYficação
+
Tabelas
de
codificação
Dados
da
imagem
19/10/09
22
11
10/19/10
Codificação
de
Informação
2010/2011
Sumário:
• As
normas
JPEG
• Compressão
de
video
• redundância
espacial
e
temporal
• normas
MPEG
Vídeo
sem
compressão
é
enorme!!
• Televisão
de
alta
definição:
1920x1080,
30
frames/s
requer
186
Mbyte/s
sem
compressão
• Mas
os
canais
de
televisão
só
suportam
18
Mbit/s
• É
preciso
comprimir
a
83:1
• Com
boa
qualidade
(sem
rectângulos,
…)
19/10/09
24
12
10/19/10
MPEG
–
MoYon
Picture
Experts
Group
(ISO)
• MPEG1
1991,
vídeo
CDs
– DesYnada
a
352x288,
25
fps
PAL
opYmizado
para
bitrate
~1.5
Mbyte/s
• MPEG2
1994,
TV
digital
– 720x480,
30
fps
NTSC
~15
Mbyte/s
– Estendido
para
HDTV
(high
definiYon
TV)
(1920x1080,
30
fps,
80
Mbyte/s)
– Usado
nos
DVD
(720x480,
30
fps,
10Mb/s)
• MPEG4
1999,
DivX
– Norma
abrangente,
compressão
por
“wavelets”
19/10/09
25
Redundância
espacial
e
temporal
Exemplo de
redundância
espacial
Exemplo de
redundância
espacial
Exemplo de
redundância
temporal
19/10/09
26
13
10/19/10
Redundância
temporal
• Existe
uma
forte
correlação
entre
valores
consecuYvos
do
sinal,
por
esse
moYvo
é
possível
prever
o
próximo
valor
do
sinal
com
base
em
amostras
anteriores,
transmiYndo‐se
apenas
o
erro
(diferença)
entre
o
valor
real
e
o
valor
predito
• Esquemas
de
codificação
prediYva
linear
e
fixa
entre
frames
exploram
a
reduzida
diferença
entre
frame
consecuYvas
• Quando
a
diferença
entre
frames
é
grande
uYlizam‐
se
esquemas
adaptaYvos
de
predição
de
movimentos,
que
se
baseiam
na
esYmação
do
movimento
dos
objectos
entre
frames
19/10/09
27
Tecnologia
base
• Codificacção
intra‐frame
(dentro
de
uma
“frame”)
– Semelhante
ao
usado
no
JPEG
(DCT,
…)
– Redundância
espacial
• Codificação
inter‐frame
– Comprime
uma
frame
fazendo
referência
às
vizinhas
no
tempo
– Redundância
temporal
– Procura
blocos
em
frames
vizinhas,
prevê
o
seu
movimento
e
codifica
as
diferenças
• Tirou
parYdo
do
trabalho
feito
na
norma
H.261
19/10/09
28
14
10/19/10
H.261
• A
recomendação
ITU‐T
H.261,
é
para
transmissão
de
vídeo
sobre
linhas
telefónicas
ISDN
(64Kbps)
• H.261
faz
parte
de
um
conjunto
de
normas
que
especifica
os
diferentes
componentes
de
um
sistema
de
vídeo
conferência
para
uma
largura
de
banda
limitada
• H.261
Yra
parYdo
da
redundâcia
espacial
e
temporal
das
sequências
de
vídeo
para
aYngir
altas
taxas
de
compressão
• Resoluções
suportadas:
– Common
Intermediate
Format
(CIF)
352x288
pixels
– Quarter
CIF
(QCIF)
176x144
pixels
• Ritmo
máximo
é
30
frames
por
segundo
(fps)
que
pode
ser
reduzido
de
acordo
com
a
aplicação
e
a
largura
de
banda
disponível
19/10/09
29
Codificação
usada
no
H
261
• Há
dois
Ypos
de
codificação
para
um
frame
– I‐frames
ou
“Intra‐coded
frames”:
Codificadas
explorando
a
redundância
dentro
da
frame
• Muito
semelhante
à
codificação
JPEG
• São
referências
(âncoras
na
sequência)
– P‐frames
ou
“Inter‐coded
frames”
• Explora‐se
a
similaridade
com
“frames”
anteriores
• Também
chamadas
frames
previstas
ou
pseudo
frames
• Exemplo
de
uma
sequência
de
frames
I
J
P
E
G
19/10/09
P
P
P
I
J
P
E
G
P
P
I
J
P
E
G
30
15
10/19/10
Frames
I
(intra
pictures)
• Codificadas
sem
referência
a
outras
frames
(codificação
“intra‐frame”)
• Compressão
recorre
a
redundância
espacial
• Tipo
de
frame
que
dá
um
ponto
de
entrada
na
bitstream,
sendo
possível
começar
a
descodificar
sem
nenhuma
dependência
de
outras
frames
19/10/09
31
Frames
P
(predicYve
pictures)
• São
codificadas
usando
predição
com
compensação
de
movimento
uYlizando
como
referência,
frames
Ypo
I
ou
Ypo
P
• Se
não
há
coincidências,
a
frame
é
codificada
como
uma
frame
I
• Compressão
assimétrica
– A
procura
de
coinsidência
é
parte
computacionalmente
mais
exigente
– Muito
di„cil
de
fazer
“on
the
fly”
sem
hardware
especializado
– Claro
que
o
descodificador
tem
muito
menos
trabalho
…
19/10/09
32
16
10/19/10
Codificação
“Intra‐Frame”
• Codificação
de
Macroblocks
– Um
macroblock
cobre
uma
área
de
16x16
pixel
com
4
blocos
Y
(Luminância),
um
bloco
Cr
(Crominância
R)
e
um
bloco
Cb
(Crominância
B)
• Um
bloco
8x8
pixels
– Usa
uma
matriz
de
quanYficação
uniforme
Y
Cr
DCT
Cb
Macrobloco
Unif-Q
8x8
8x8
Resto do
JPEG
19/10/09
33
Codificação
“Inter‐Frame”
• Codificar
a
“diferença”
do
macro
bloco
a
codificar
em
relação
a
uma
“frame”
de
referência
descodificada
– A
frame
de
referência
é
sempre
a
anterior
frame
I
– Vector
de
movimento:
deslocamento
x,y
para
a
melhor
correspondência
doutro
macrobloco
com
este
Alvo
+
Macrobloco(16x16)
+
-
Vector de
Movimento
Referência (Descodificado)
19/10/09
Y
Cr
Cb
DCT+Q+RLE+Huff
Vector de Formatação
Movimento
Saída
34
17
10/19/10
Codificação
da
“P‐frame”
Vector
de
movimento
Como
se
procura
a
melhor
correspondência
Reference
Target
(x,y)
(x,y)
Searching
region
Reference
(x,y)
Motion
Vector(u,v)
MAE(Mean Absolute Error):
❒ C[x..x+15][y..y+15] é o bloco que está a ser comprimido
❒ R[x+u..x+u+15][y+v,y+v+15] é o bloco de referência
19/10/09
35
Vector
de
Movimento?
Procura‐se
numa
região
o
par
(x,y)
tal
que
MAE
(u,v)
é
um
mínimo
Mecanismo
de
busca
• Procura
completa
– Procura‐se
sequencialmente
em
toda
a
região
(indicada
a
tracejado
na
figura)
– Desvantagem,
é
uma
procura
exausYva,
por
consequência
muito
lenta
• Procura
logaritmica
2D
• EsYmação
hierárquica
• Outras
melhoria
– Em
vez
de
uYlizar
deslocamentos
inteiros
permiYr
deslocamentos
reais
19/10/09
36
18
10/19/10
Procura
logarítmica
2
D
Comparação
iteraYva
do
MAE
em
9
pontos
vizinhos
• RepeYr
até
ao
tamanho
da
região
de
busca
ter
um
pixel
de
lado:
1
2
2
1. Escolher
entre
as
9
localizações
a
que
corresponde
ao
MAE
mínimo
2. Considerar
uma
nova
região
de
busca
com
metade
do
tamanho
da
anterior
e
centrada
na
localização
encontrada
no
passo
1
2
1
1
2
1
2
1
3 3 3
2 3 2 32
3 3 3
1
1
1
1
19/10/09
37
EsYmação
hierárquica
• Formar
uma
colecção
de
amostras
da
imagem
corrente
e
da
imagem
de
referência
com
resolução
cada
vez
menor
• Encontrar
um
vector
de
movimento
(usando
um
dos
métodos
anteriores)
usando
as
imagens
de
resolução
mais
baixa
• Usando
a
resposta
encontrada
como
ponto
de
parYda
a
tentar
encontrar
o
menor
MAE
numa
imagem
de
resolução
imediatamente
superior
• RepeYr
o
processo
até
à
resolução
máxima
Estimar Movimento
Amost 1/2
Vector de Movimento
Estimativa do Vector de Moviemtno Nível 1
Estimar Movimento
Amost 1/2
Estimativa do Vector de Movimento Nível 2
Estimar Movimento
19/10/09
38
19
10/19/10
Diagrama
de
Blocos
Codificador
Descodificador
19/10/09
39
Controlo
do
ritmo
de
transmissão
H.261
é
usado
para
transmiYr
num
canal
de
ritmo
constante
(e.g.
384kbps).
O
out
do
codificador
depende
da
quanYdade
de
movimento
da
cena.
É
preciso
um
mecanismo
de
controlo
do
ritmo
para
acomodar
o
ritmo
de
entrada
variável
ao
ritmo
constante
do
canal
19/10/09
40
20
10/19/10
Solução
• A
sequência
de
bits
é
depositada
no
buffer
e
este
é
esvaziado
a
ritmo
constante
para
o
canal
• Um
aumento
de
acYvidade
da
cena
tem
por
consequência
o
enchimento
do
buffer
– O
valor
dos
coeficientes
da
matriz
de
quanYficação
é
aumentado
de
forma
a
aumentar
o
factor
de
compressão
e
a
diminuir
o
ritmo
de
saída
de
bits
do
codificador
• Se
o
buffer
começa
a
esvaziar,
o
valor
da
matriz
de
quanYficação
é
diminuido
o
que
reduz
a
taxa
de
compressão
e
aumenta
o
ritmo
de
saída
do
codificador
• A
compressão,
e
a
qualidade,
podem
variar
muito
dependendo
da
quanYdade
de
movimento
da
cena:
– Cenas
relaYvamente
”estáYcas"
levam
a
baixa
compressão
e
alta
qualidade
– Cenas
"acYvas”
conduzem
a
maior
compressão
e
baixa
de
qualidade
Controlo
do débito
Sequência Codificador
de vídeo
Canal
Buffer
19/10/09
41
MPEG
• "Moving
Picture
Coding
Experts
Group",
organismo
criado
para
normalizar
os
formatos
para
o
transporte
de
audio
e
video
• ObjecYvo
do
MPEG‐1
:
Qualidade
de
VHS
num
CD‐ROM
ou
Video
CD
(VCD)
(352
x
240
+
CD
audio
@
1.5
Mbits/sec)
• MPEG‐2
permite
vários
níveis
de
qualidade
• A
norma
tem
4
partes:
– Video:
Define
o
compressor/descompressor
de
vídeo
– Audio:
Define
o
compressor/descompressor
de
audio
– Sistema:
Descreve
como
os
vários
Ypos
de
dados(video,
audio
ou
dados
genéricos)
são
combinados
e
sincronizados
– CerYficação:
Define
um
conjunto
de
testes
que
cerYfica
que
uma
dada
realização
obedece
à
norma.
19/10/09
42
21
10/19/10
Normas
MPEG
MPEG Standards
Bit-rate
Utilização
MPEG-1
1.5Mbps
Vídeo CD
MPEG-2
10-40 Mbps
DVD, SVCD, HDTV
MPEG-4
Scalable
QuickTime, DivX
19/10/09
43
Camadas
do
MPEG
• Camada
de
sistema:
combinação
de
“streams”
de
audio
e
video
comprimidos
num
único
“bitstream”.
– Cada
bitstream
é
uma
sequência
de
“packs”
– Cada
“pack”
é
um
conjunto
de
pacotes
(packets)
que
contêm
vídeo
e
áudio,
19/10/09
44
22
10/19/10
Problema
• Alguns
macroblocos
precisam
de
informação
que
não
está
na
frame
de
referência.
– Mas
pode
estar
na
frame
seguinte
Frame anterior
Frame corrente
Frame seguinte
❒ Acrescentar um terceiro tipo de frame (B-frame): Para
construir um B-frame, procurar macroblocks semelhantes nas
frames do passado e do futuro.
❒ Um padrão típico é is IBBPBBPBB IBBPBBPBB IBBPBBPBB.
19/10/09
45
Frames
B
(bidirecYonal
prediYve
pictures)
• Usam
predição
com
compensação
de
movimento,
tendo
como
referência
frame
anterior
e/ou
seguinte
do
Ypo
I
ou
P
• Para
permiYr
uma
predição
para
trás
com
base
numa
frame
futura
o
codificador
tem
que
alterar
a
ordem
natural
de
reprodução
de
frames
• Frame
só
pode
ser
transmiYda
depois
das
frames
passadas
e
futuras
das
quais
depende.
Isto
introduz
um
atraso
que
é
dependente
do
número
de
frames
B
consecuYvas.
19/10/09
46
23
10/19/10
Ordem
de
transmissão
vs
Ordem
de
“Display”
Ordem
de
transmissão:
1(I),
4(P),
2(B),
3(B),
7(P),
5(B),
6(B),
10(I),
8(B),
9(B)
P
B
B
I
B
B
P
B
B
P
B
B
I
B
-3
-2
-1
1
2
3
4
5
6
7
8
9
10
11
19/10/09
47
Previsão
Bidireccional
• As
B‐frames
permite
prever
áreas
da
imagem
corrente
que
não
são
visíveis
em
frames
anteriores
mas
são
visíveis
em
frames
posteriores.
• É
|pica
uma
relação
de
5:3:1
para
os
bits
gastos
em
frames
I,
P
and
B,
respecYvamente.
19/10/09
48
24
10/19/10
Limites
para
os
parâmetros
do
MPEG1
Parametro
Limite
Tamanho horizontal
< 720 pixels
Tamanho vertical
< 576 linhas
Total # de macroblocks por imagem
< 396
Total # of macroblocks per imagem
< 396 x 25 (or 396 x 30)
Frame / seg
< 30
Bit rate
< 1.86 Mbps
Buffer de descodificação
< 376832 bits
19/10/09
49
MPEG2
• Enquanto
o
MPEG‐1
é
uma
norma
para
armazenar
e
mostrar
video
num
só
computador
a
bitrates
baixos,
o
MPEG‐2
é
uma
norma
para
TV
digital.
Cumpre
os
requisitos
do
HDTV
e
DVD
(Digital
Video/VersaYle
Disc).
• O
MPEG2
suporta
os
seguintes
nívels:
19/10/09
Level
Tamanho
Low
352 x 288 x 30
Pixels/sec
3M
Bit-rate(Mbps)
4
Aplicação
Main
720 x 576 x 30
12 M
15
Estúdio TV
High 1440
1440 x 1152 x 60
96 M
60
HDTV
High
1920 x 1152 x 60
128 M
80
Produção de filmes
50
25
10/19/10
MPEG
4
standard
(2000)
• Suporte
para
diferentes
bitrates
(HBR
–
VLBR)
• Uso
de
objectos
audio‐visuais
(Audio/visual
objects)
• Hierarquia
de
objectos
• Descrição
da
cena
incluindo:
• Objectos
de
texto
• Imagens
fixas
(background)
• Objectos
móveis
• Sons
• Novos
algoritmos
para
previsão
de
movimento
• Trabalhos
na
mesma
direcção
no
MPEG‐7
e
MPEG‐21
19/10/09
51
26