Compressão de Dados Parte 1 - Aula de Introdução à Multimídia

Prévia do material em texto

IF687 - Introdução à Multimídia
Prof. Daniel Cunha - CIn/UFPE 1
INTRODUÇÃO À MULTIMÍDIA
Compressão de Dados – Parte 1
Prof. Daniel Cunha
dcunha@cin.ufpe.br
2 / 18
Roteiro
 Introdução
 Tipos de Compressão
 Conceitos Básicos de Teoria da Informação
 Informação (incerteza)
 Propriedades intuitivas
 Fonte de informação discreta
 Entropia de uma fonte discreta
 Extensão de uma fonte discreta sem memória
 Conclusões
3 / 18
Introdução
 Evolução dos sistemas de telecomunicações
 Redução nos custos.
 Aumento da capacidade de processamento e transmissão.
 Eficiência das redes
 Evolução das tecnologias de compressão de dados.
 Compressão de dados
 Redução intencional no conteúdo da informação.
 Agilidade na transmissão de dados.
 Possibilidade da expansão de uma rede de computadores.
 Concepção de sistemas multimídia modernos.
IF687 - Introdução à Multimídia
Prof. Daniel Cunha - CIn/UFPE 2
4 / 18
Introdução
Sistema típico de compressão de dados. 
5 / 18
Tipos de Compressão
 Compressão com Perdas (lossy compression)
 Informação original: quantização.
 Altas taxas de compressão.
 Perda de fidelidade (ex. compressão JPEG).
 Compressão sem Perdas (lossless compression)
 Sinal original não sofre distorção.
 Taxas de compressão mais modestas.
 Limite entrópico da mensagem.
 Objetivo: Abordar conceitos básicos sobre teoria da informação e 
conhecer alguns algoritmos de compressão sem perdas.
6 / 18
Teoria da Informação
 Conceitos Básicos
 Informação: medidas e aplicações.
 Como medir a informação?
 Medida de Informação (Hartley)
 Símbolo de mensagem: “s” possibilidades.
 Qtde. de informação: logaritmo.
 Algumas “lacunas”.
Ralph Hartley (1888 -1970)
Fundamentos de Teoria da Informação.
IF687 - Introdução à Multimídia
Prof. Daniel Cunha - CIn/UFPE 3
7 / 18
Teoria da Informação
 Contribuições de Shannon
 Extensão do conceito de informação.
 Associação com probabilidade.
 Medida de Hartley: caso particular.
Claude E. Shannon (1916 -2001)
Pai da Teoria da Informação.
8 / 18
Teoria da Informação
 Incerteza (informação)
 Evento E
 Quantidade de informação associada ao evento E
( ),k k kE e P E e p= = =
( ) 1log logk k
k
I e p
p
 
= = − 
 
9 / 18
Teoria da Informação
 Quantidade de Informação (propriedades)
( ) 0 1,k kI e p= =
( ) 0 0 1,k kI e p≥ ≤ ≤
( ) ( ) ( ),k n k nI e e I e I e= +
(se os eventos forem estatisticamente independentes)
IF687 - Introdução à Multimídia
Prof. Daniel Cunha - CIn/UFPE 4
10 / 18
Teoria da Informação
 Quantidade de Informação (unidades)
 Base 2:
 Base natural:
 Base 10:
 Exercício 1
Verificar que 1 Hartley = 3,32 bits e que 1 nat = 1,44 bits.
( ) ( )2 1logk
k
I e p=
( ) ( )1lnk
k
I e p=
bits (binary units)
nats (natural units)
( ) ( )10 1logk
k
I e p= Hartleys
11 / 18
Teoria da Informação
 Fonte de Informação Discreta
Seja uma fonte de informação S que emite símbolos em
sequência a partir de um alfabeto fonte finito. Cada símbolo
ocorre com uma probabilidade fixa.
 Emite símbolos estatisticamente independentes.
 É descrita por seu alfabeto e suas probabilidades.
{ }1 2, ,..., qS s s s=
1 2, ,..., qp p p
12 / 18
Teoria da Informação
 Fonte de Informação Discreta
 Quantidade de info. por símbolo:
 Quantidade de info. média por símbolo da fonte:
( )
( )2
1
logk
k
I s
p s
 
=  
 
( ) ( )
( )
1
logk
k k
H S p s
p s
 
=  
 
∑
(ENTROPIA DE UMA FONTE DISCRETA SEM MEMÓRIA)
IF687 - Introdução à Multimídia
Prof. Daniel Cunha - CIn/UFPE 5
13 / 18
Teoria da Informação
 Interpretação da Entropia
“Quantidade média de incerteza que o observador possui
antes de observar a saída da fonte”.
 Exercício 2
Calcule a entropia da fonte S.
{ }1 2 3, ,S s s s= ( ) ( ) ( )1 2 3
1 1
2 4,p s p s p s
 = = = 
 
14 / 18
Teoria da Informação
 Extensão de uma Fonte Discreta sem Memória
 Aumento da quantidade de símbolos da fonte.
 E se considerarmos blocos de símbolos?
Seja S uma fonte sem memória com alfabeto S e
probabilidades p(si), i=1,...,q. A extensão de ordem n de S
(Sn) é uma fonte (estendida) sem memória com qn símbolos.
{ }1 2, ,..., nqσ σ σ ( )ip σ
15 / 18
Teoria da Informação
 Extensão de uma Fonte Discreta sem Memória
 Como obter os novos símbolos e probabilidades?
 Exemplo:
( )1 2, ,...,i i i ins s sσ = ( ) 1 2...i i i inp p p pσ =
{ }1 2 3, ,S s s s= 1 2 3, ,p p p
{ }2 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3, , , , , , , ,S s s s s s s s s s s s s s s s s s s=
( )
1 2 3 4 5 6 7 8 9
2 2 2
1 1 2 1 3 2 1 2 2 3 3 1 3 2 3
:
:
i
ip p p p p p p p p p p p p p p p
σ σ σ σ σ σ σ σ σ σ
σ
IF687 - Introdução à Multimídia
Prof. Daniel Cunha - CIn/UFPE 6
16 / 18
Teoria da Informação
 Extensão de uma Fonte Discreta sem Memória
 Como calcular a entropia da fonte estendida?
É possível demonstrar que
( ) ( ) ( ) ( ) ( )1
1 1
log log
n
n
q
n
i i
i Si i
H S p p
p p
σ σ
σ σ=
= =∑ ∑
( ) ( )nH S nH S=
17 / 18
Teoria da Informação
 Exercício 3
Calcule a entropia da fonte estendida S2 (de duas formas).
{ }1 2 3, ,S s s s= ( ) ( ) ( )1 2 3
1 1
2 4,p s p s p s
 = = = 
 
18 / 18
Conclusões
 Introdução
 Tipos de Compressão
 Conceitos Básicos de Teoria da Informação
 Informação (incerteza)
 Propriedades intuitivas
 Fonte de informação discreta
 Entropia de uma fonte discreta
 Extensão de uma fonte discreta sem memória
Pedro Torres