Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Elementos de Teoría de la Información (página 3)




Enviado por Pablo Turmero



Partes: 1, 2, 3

Monografias.com

41
Códigos eficientes
41
l i longitud de la palabra codificada del mensaje m i
r : # de símbolos del alfabeto del código

L = S pi l i : Longitud promedio de la palabra*
Estrategia: Asignar palabras más cortas a símbolos más probables

Monografias.com

42
Relación entre L y H !!!
42
log r : Cantidad promedio máxima de información de un símbolo del código.
L log r ? H(s)
(Gp:) Eficiencia del código :
h = H (S) / (L log r)

Monografias.com

43

Monografias.com

44

Monografias.com

45
Nos falta encontrar el segundo término pendiente en la definición de cantidad de información: codificador óptimo.
Introduciendo el signo negativo dentro del logaritmo en la expresión de la entropía, ésta nos quedará como:
H(X) = ? p(x) log2 [1/p(x)]
i
La expresión log2 [1/p(x)] representa el número necesario de bits para codificar el mensaje X en un codificador óptimo.
Codificador óptimo es aquel que para codificar un mensaje X usa el menor número posible de bits.
Codificador óptimo
Veamos un ejemplo de codificación

Monografias.com

46
M = 1 “ ” = 01 A = 000 I = 0010 E = 0011
Código óptimo:
Mensaje: MI MAMA ME MIMA
Mensaje: 1 0010 01 1 000 1 000 01 1 0011 01 1 0010 1 000 (33 bits)
Pregunta: ¿Con cuántos bits se codificaría si se usara ASCII? Saque conclusiones.
Creación del árbol de
frecuencias observadas
Codificación de Huffman

Monografias.com

47
Compresión de las señales
Consiste en la reducción del volumen de información tratable (procesar, transmitir o grabar).
En principio, con la compresión se pretende transportar la misma información, pero empleando la menor cantidad de espacio.
Ocupación espectral de 30 Mbits / seg a 40 Mbits / seg, para poder sr utilizado por una transmisión:
via satélite de 27 Mhz a 36 Mhz
canal de cable de 6 Mhz a 8 Mhz
El espacio que ocupa una información codificada (datos, señal digital, etc.) sin compresión es el cociente entre la frecuencia de muestreo y la resolución.
Por tanto, cuantos más bits se empleen mayor será el tamaño del archivo.

Monografias.com

48
Técnicas de Compresión

Monografias.com

49
Compresión de las señales
Proceso

Se buscan repeticiones en la serie de datos.

Se almacena solo el dato junto al número de veces que se repite.

Ejemplo: Si en un archivo aparece una secuencia como "AAAAAA", ocupando 6 bytes, se podría almacenar simplemente "6A" que ocupa solo 2 bytes.

Monografias.com

50
Compresión de las señales
Algoritmos de compresión

Huffman: Examina los caracteres más repetidos, luego los codifica en una forma mas corta.

LZW: Construye un diccionario con los patrones encontrados, a los cuales se hace referencia posteriormente.

Monografias.com

51
Lectura Opcional
Sub Compresión
DCT
JPEG

Monografias.com

52
Compresión de las señales
Conceptos
Redundancia: Datos que son repetitivos o previsibles.

Entropía: Diferencia entre la cantidad total de datos de un mensaje y su redundancia.

Irrelevante: Información que no podemos apreciar y cuya eliminación no afecta al contenido del mensaje.

Básica: Información relevante. No es redundante ni irrelevante. Debe ser transmitida en su totalidad para que se pueda reconstruir la señal.

Monografias.com

53
Compresión de las señales
Tipos
Sin pérdidas reales: La transmisión es equivalente a la entropía del mensaje ( toda la información básica e irrelevante, pero eliminando la redundante ).

Subjetivamente sin pérdidas: Se elimina la información redundante y la irrelevante.

Subjetivamente con pérdidas: Se elimina cierta cantidad de información básica, por lo que el mensaje se reconstruirá con errores perceptibles pero tolerables.

Monografias.com

54
Tipos de codificación de las señales
R L C ( Run Length Coding )

Uso: Cuando la información contiene series largas de elementos idénticos.

Codificación: El elemento y su Nro. de repeticiones.

Reversibilidad: Total, no se pierde información.

Aplicación: Informática. Archivos Zip, Arc, etc.

Monografias.com

55
Tipos de codificación de las señales
V L C ( Variable Length Coding )

Base de uso: La probabilidad de que todos los elementos componentes de una información no tendrán la misma codificación.
Codificación:
Menos bits los elementos de aparición frecuente.
Más bits los elementos mas raros.
Inconveniente: Conocer previamente la serie de elementos que hay que transmitir, esto es totalmente incompatible con el “ Tiempo Real ”.

Monografias.com

56
DCT (Discrete Cosine Transform)
Es un caso particular de la transformada de Fourier , aplicada a las señales discretas ( muestreos ).
Transformada de Fourier: Cualquier señal periódica puede ser representada por una serie de sumas trigonométricas en senos y cosenos relacionadas armónicamente.
Imagen:
Trabajar a partir de una señal muestreada bidimensional.
Analizar en horizontal y vertical
Armar un bloque de N x N pixels con los valores discretos de luminancia (o crominancia).
Transformar el bloque anterior en otro de N x N coeficientes, que corresponderán a la amplitud de cada una de las funciones cosenos armónicos.

Monografias.com

57
DCT (Discrete Cosine Transform
Proceso

720 pxels – 90 bloques
576 pixels – bloques
Bloque
La imagen se divide en bloques de 8 x 8 pixels.
Imagen dividida en bloques
En el bloque transformado, los coeficientes de las frecuencias horizontales van de izquierda a derecha sobre el eje horizontal y los de las frecuencias horizontales, crecientes de arriba a abajo sobre le eje vertical

Monografias.com

58
DCT (Discrete Cosine Transform) Proceso
Bloque de 8 x 8 pixels.
Los valores representan la intensidad luminosa de un píxel

Monografias.com

59
DCT (Discrete Cosine Transform) Proceso
A los coeficientes se les resta 128 para que queden números entorno al 0, entre -128 y 127.

Monografias.com

60
DCT (Discrete Cosine Transform) Proceso
La DCT transforma el contenido del bloque en una matriz de 8 x 8 coeficientes.
El primero (arriba a la izquierda, coordenadas 0, 0) indica la componente continua (DC) que representa la intensidad media del bloque.
El último ( abajo a la derecha ), da la componente de frecuencia espacial mas elevada para los dos ejes.

Monografias.com

61
DCT (Discrete Cosine Transform)
Representación en forma visual de la contribución de cada uno de los coeficientes al aspecto del bloque de 8 x 8 pixels originales.

Monografias.com

62
DCT (Discrete Cosine Transform)
Consideraciones finales

Los coeficientes dependen del Nro. de detalles contenidos en el bloque.

Normalmente la energía del bloque se concentra en unos pocos coeficientes en el ángulo superior izquierdo.

Los coeficientes son independientes unos de otros.

Los coeficientes tienen menor precisión cuando la frecuencia aumenta.

Monografias.com

63
Cuantificación
Características del ojo humano

Detecta pequeños cambios de brillo en áreas grandes.

No detecta rápidos cambios de brillo en áreas pequeñas, variaciones de alta frecuencia.

Monografias.com

64
Cuantificación
Lo anterior nos permite eliminar las altas frecuencias, sin perder excesiva calidad visual.

Esto se observa en los coeficientes correspondientes tendiendo a 0 (cero).

Este proceso es en el que se pierde la mayor parte de la información (y calidad) cuando una imagen es procesada por este proceso.

Monografias.com

65
Cuantificación
Ejemplo de una matriz de cuantificación típica

Monografias.com

66
Cuantificación
La matriz cuantificada se obtiene dividiendo cada coeficiente de la matriz de la imagen transformada con cada coeficiente de la matriz de cuantificación.

Monografias.com

67
Compresión de imágenes fijas
JPEG
Joint Photographic Experts Group

Se basa en una norma de compresión de imágenes fotográficas de resolución variable, en forma Y, Cb, Cr.

Puede realizarse con o sin pérdida (reversible), según la finalidad y la tasa de compresión.

En los usos mas habituales se toleran ciertas pérdidas lo que permite alcanzar índices de compresión superiores a 10 sin una degradación apreciable.

Monografias.com

68
JPEG
La compresión se descompone en 6 etapas

1.- Descomposición en bloques.
2.- Transformación mediante DCT.
3.- Discriminación por umbral y cuantificación.
4.- Lectura en zigzag.
5.- Codificación RLC.
6.- Codificación entrópica de Huffman ( VLC ).

Monografias.com

69
JPEG
1.- Descomposición en bloques

La imagen original de forma Y,Cb,Cr, se divide en bloques elementales de 8 x 8 pixels.

Imagen en formato CCIR 601 de 720 x 576 pixels, hay
6.480 bloques de luminancia.
3.240 bloques para cada una de las crominancias.

Digitalización de 8 bits
cada bloque forma una matriz de 64 números
de 0 a 255 para la luminancia
de – 128 a + 128 para las crominancias

Monografias.com

70
JPEG
2.- Transformación mediante DCT

Genera por cada bloque Y,Cb,Cr una matriz de 8 x 8 pixels, con los coeficientes de las componentes de frecuencias espaciales.

Monografias.com

71
JPEG
3.- Discriminación por umbral y cuantificación

Se tiene en cuenta las particularidades de la visión humana.

El ojo no distingue los detalles finos por debajo de cierto nivel de luminancia ( Y ).

Como consecuencia se ponen en 0 ( cero ) los coeficientes inferiores a un valor predeterminado.

Los coeficientes restantes se codifican con una precisión decreciente a medida que la frecuencia aumenta.

Monografias.com

72
JPEG
4.- Lectura en zigzag

Con la excepción del primer coeficiente ( CC – luminancia ), los 63 restantes ( coeficientes de CA, crominancia ) se leen en zigzag para transformar la matriz en una corriente de datos en serie, para ser utilizada en las otras etapas.

Monografias.com

73
JPEG
5.- Codificación RLC

Se codifica el número de ocurrencias de los coeficientes.

Se tiene máxima atención a los nulos y al próximo no nulo.

Monografias.com

74
JPEG
6.- Codificación entrópica de Huffman (VLC)

Esta última etapa consiste en codificar los coeficientes con una longitud tanto mas corta cuanto mas frecuentes sean estadísticamente.

Partes: 1, 2, 3
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter