Compressão de Imagens
Guilherme Defreitas Juraszek
Por que precisamos da compressão de
imagens?
1920 x 1080 x 24
Altura
Largura
= 6MB
Cores
(RGB, 8 bits cada)
= 1 frame!
Por que precisamos da compressão de
imagens?
6MB x
Quadro
30 x
fps
60
1 min
= vídeo de
1 minuto
= +10GB
Por que precisamos da compressão de
imagens?
Hubble transmitia 120GB de dados
por SEMANA.
Fonte: http://ssd.jpl.nasa.gov/horizons.cgi#results
Curiosity se comunica com a terra a 32kbps,
ou 2mbps através de satélites intermediários
(janela de comunicação de 8 minutos por dia)
Fonte: https://www.aiaa.org/SecondaryTwoColumn.aspx?id=13350
Por que precisamos da compressão de
imagens?
*Requisito: 2Gbps (GIGA)
Como podemos comprimir?
• A maioria das imagens não apresentam pixels
com cores completamente diferentes entre si.
© 1992–2008 R. C. Gonzalez & R. E. Woods
Compressão de Imagens
Compressão de Imagens
JPEG
Mapping
8x8
DCT
Codificação de
Huffman
JPEG – Blocos 8x8
• Uma imagem RGB pode ser decomposta em 3
matrizes, uma R, uma G e B.
JPEG – Blocos 8x8
• JPEG transforma o RGB para o espaço de cores
YCbCr
JPEG – Blocos 8x8
• Subdividir a imagem em blocos de 8x8
DCT – Discrete Cosine Transform
• Com a imagem dividida em pedaços de 8x8 (64
pixels)
– A ideia é transformar esse pedaço para um domínio
onde o primeiro elemento possibilite recriar a imagem
com o menor erro possível (root mean square error),
os demais 63 elementos são descartados.
– Kahunen-Loève Transform
• É dependente da imagem
• Lento para calcular
• Necessita da imagem inteira para gerar os dados para o
cálculo, não pode ser calculado de forma “online” ou “on the
fly”.
DCT – Discrete Cosine Transform
n-1
n-1
x=0
y=0
n-1
n-1
x=0
y=0
T(u,v) = Σ Σ f(x,y) . R(x,y,u,v)
nxn
F(x,y) = Σ Σ T(x,y) . S(x,y,u,v)
nxn
Usando Kahunen-Loève R e S tem valores específicos de acordo com a imagem, usando
DCT os valores são fixos para todas as imagens.
DCT – Discrete Cosine Transform
R(x,y,u,v) = S(x,y,u,v)
= α(x) α(v) cos
(2x + 1)uπ
2n
1/n
se u = 0
2/n
se u ≠ 0
+
(2y + 1)vπ
2n
α(x) =
n = tamanho do bloco
n=4
8x8
DCT vs DFT
JPEG
Mapping
8x8
DCT
Codificação de
Huffman
Quantização
Quantização
Quantização
Quantização
JPEG
Mapping
8x8
DCT
Codificação de
Huffman
Codificação/Compressão de Huffman
Codificação/Compressão de Huffman
Codificação/Compressão de Huffman
Exercício
• Executar manualmente a codificação de
Huffman
1
1
0
128:0.47
0.53
1
0
87:0.25
0.28
1
255:0.03
0
186:0.25
Codificação/Compressão de Huffman
Como saber se vou ter uma boa compactação dos dados usando Huffman?
R: Entropia – Ela diz qual é a média do tamanho da representação dos símbolos
após a codificação.
P(s) = Probabilidade do símbolo S
Entropia = H =
- Σ p(s) log2 p(s)
Símbolos
Exercícios
• Implementar o algoritmo JPEG
–
–
–
–
–
Implementar em tons de cinza
Usar a implementação DCT do adessowiki
Efetuar a quantização usando a tabela do slide 20
Representar usando a forma do slide figura d
Não precisa implementar Huffman
1. Imagem Original -> DCT -> Quantização
2. Quantização inversa -> DCT inversa -> Exibe
imagem