Introducción a la compresión de datos.
Muchas aplicaciones multimedia requieren volúmenes de información importantes:
CD-ROM: 648 MB
72’ sonido estéreo.
30’’ de vídeo (estudio TV).
Una película de 90’ ocuparía 120 GB.
Una foto (35 mm) a resolución 2000×2000 ocuparía 10MB.
Un canal de HDTV requiere un ancho de banda de 2Gbps.
Por esta razón se emplean técnicas de compresión que permitan reducir el volumen de información
1
Introducción a la compresión de datos (II).
Un sistema de compresión consta de:
Codificador y decodificador
Codificador y decodificador pueden ser:
Asimétricos
El codificador suele ser más complejo y lento que el decodificador (Ej.: Vídeo por demanda)
Simétricos
Coste computacional similar (Ej: Videoconferencia).
Con pérdidas (lossy compression) o irreversible
Adecuada para medios continuos (audio y vídeo).
Mayores tasas de compresión.
Sin pérdidas (lossless compression) o reversible:
Ficheros de datos, imágenes médicas, etc.
2
Factores en el diseño de un codificador.
3
Eficiencia
– Tasa de compresión
Complejidad
Espacio de memoria
Potencia (mW)
Operaciones/Seg.
Retardo
Calidad de la señal
BER (Bit Error Ratio)
SNR (Signal/Noise)
MOS (Mean Opinion Score)
Dos clases de técnicas de compresión.
Entropy encoding
Codifica los datos sin necesidad de conocer la naturaleza de estos.
De propósito general (todo tipo de datos).
Son técnicas de compresión sin pérdidas.
Ejemplos: Statistical (Huffman, aritmética,etc.), Run-length.
Source encoding
Codifica los datos basándose en las características y propiedades de estos.
Suelen ser técnicas de compresión con pérdidas.
Se obtienen tasas de compresión elevadas.
Codificadores/decodificadores de propósito específico.
Ejemplos:
Differential, transform, vector quantization, etc.
4
Codificación basada en la entropía.
Entropía:
Valor medio de información de un conjunto de símbolos procedente de una fuente de información (es imposible de medir en la práctica).
(pi = probabilidad del símbolo i)
Por ejemplo: Sea S = {4,5,6,7,8,9}, en donde la probabilidad de cada símbolo es la misma (1/6).
Según la teoría de la información (Shannon), esta fuente no puede ser codificada (sin pérdidas) con menos de 2.585 bits por símbolo.
5
Statistical encoding
Trata de identificar los símbolos (patrones de bits) que más se repiten en el conjunto de datos de entrada.
Se codifican con pocos bits los símbolos más frecuentes, mientras que los menos frecuentes son codificados con más bits.
Ejemplos:
Codificación Morse
E: ‘•’ y Q:’–•-’
Codificación Huffman.
Codificación aritmética.
6
Codificación Huffman
Representan los símbolos con un número de bits inversamente proporcional a su frecuencia.
Algoritmo genérico:
Se construye un árbol binario de abajo hacia arriba agrupando los símbolos de menor frecuencia y asignado la suma de las probabilidades de ambos al nodo padre del árbol.
Cada símbolo estará representado por una hoja del árbol y su código serán los bits recorridos hasta la raíz del mismo.
Ejemplo:
7
Codificación Huffman: Ejemplo
8
(Gp:) ABCDE(39)
(Gp:) 0
(Gp:) 1
(Gp:) DE(11)
(Gp:) 1
(Gp:) 0
(Gp:) BC(13)
(Gp:) 1
(Gp:) 0
(Gp:) BCDE(24)
(Gp:) 1
(Gp:) 0
A(15) B(7) C(6) D(6) E(5)
Codificación aritmética
Identifica una secuencia de símbolos asignándoles una representación binaria de un intervalo de una longitud inferior a la unidad.
Siempre son más eficientes que los códigos Huffman
Separa el modelo probabilístico de la asignación de bits pudiendo definir codificadores adaptativos.
Es computacionalmente eficiente, aunque está sujeto a patentes.
Ejemplo:
Supongamos sólo dos símbolos, A y B con una probabilidad de P(A)=1/3 y P(B)=2/3.
9
Codificación aritmética: Ejemplo
10
(Gp:) A
(Gp:) B
(Gp:) 2/3
(Gp:) 4/9
(Gp:) 8/9
(Gp:) AA
(Gp:) AB
(Gp:) BA
(Gp:) BB
(Gp:) 16/27
(Gp:) 8/27
(Gp:) AAA
(Gp:) AAB
(Gp:) ABA
(Gp:) ABB
(Gp:) BAA
(Gp:) BAB
(Gp:) BBA
(Gp:) BBB
(Gp:) 0
(Gp:) 1
(Gp:) P(A) = 1/3 P(B) = 2/3
(Gp:) segmento
(Gp:) 31/32
(Gp:) 15/16
(Gp:) 14/16
(Gp:) 6/8
(Gp:) 3/8
(Gp:) 1/4
(Gp:) 10/16
(Gp:) 4/8
(Gp:) código
(Gp:) .11111
(Gp:) .110
(Gp:) .1010
(Gp:) .100
(Gp:) .1111
(Gp:) .1110
(Gp:) .01
(Gp:) .011
Run-length encoding
Se basa en detectar las repeticiones de símbolos (bits, números, etc) en los datos a codificar.
Ejemplo:
11
(Gp:) Datos a codificar (42):
(Gp:) 3150000000376541111111127000000000000003
(Gp:) 315A0737654A1827A0143
(Gp:) Datos codificados (21):
(Gp:) Tasa de compresión: 50%
Este patrón es frecuente en multimedia:
Audio: Tiras de ceros que representan silencios.
Vídeo e imagen: Fondos del mismo color (paredes, cielos, etc.)
Codificación basada en la fuente.
Se basan fundamentalmente en las propiedades de la fuente de datos a codificar.
Suelen tolerar pérdidas en la codificación (lossy codecs) que perceptualmente pasan inadvertidas para el usuario.
Son codificadores de propósito específico.
Por término general obtienen mayores prestaciones que los codificadores basados en la entropía.
12
Página siguiente  |