teoría de la información - cs.uns.edu.arldm/mypage/data/ss/info/teoria_de_la_inform...y la...

2 de mar de 2004 Codificación de imágenes y video

Teoría de la Información

2 de mar de 2004 Codificación de imágenes y video 2

El clima en el Río de la Plata...

...NLNNLSN

...NLLTLLL

...NNLSNLL

...NSLSSTT

...SNNSSLN

...NSNTNNN

...LSTLNLN

p(N)=0.5, p(S)=0.25, p(L)=0.125, p(T)=0.125

N: nublado; S: soleado; L: lluvia; T: tormenta


Motivación

Para comunicar estos cuatro símbolos se acuerda usar el siguiente código:

C(N) = 00C(S) = 01C(L) = 10C(T) = 11

Típicamente uno se pasa usando el código C(N)=00. La pregunta es: ¿existe otra codificación más eficiente?


Formalización

Se puede considerar al estado del tiempo como una variable aleatoria discreta X, con un alfabeto

A={N,L,T,S}

y una función de probabilidad

p(x)=Probabilidad(X=x)

con x en A.


Formalización: información

Dado que típicamente esta nublado, el símbolo Ncontiene poca “información”, es “predecible”, es más probable, “no es noticia”.

Información. Una medida de la información podría ser:

I(x) = -log2(p(x))

I(N) = 1, I(S) = 2, I(L) = 3, I(T) = 3


Información

¿Qué pasa si supiéramos que siempre está nublado (p(N)=1)?. En este caso I(N) = 0, podemos predecir con probabilidad 1 que va a estar nublado, no hay incertidumbre, no hay información.

La situación de mayor incertidumbre es cuando p(N)=p(L)=p(S)=p(T)=1/4.


Información

Si pudiéramos elegir libremente (símbolos equiprobables) entre 2 símbolos necesitaríamos 1 bit, para 16 símbolos necesitaríamos 4 bits y en general para N símbolos se necesitan log2(N) bits.

log2(N) = -log2(1/N), lo que nos dice que hay una relación entre información y cantidad de bits necesarios.


Entropía

La entropía H(X) es la media de la información de la fuente:

Idea: La entropía mide la información media, y por tanto, la cantidad media de símbolos necesarios.

X

xpxpxIEXH )(log)()()( 2


Entropía

Se puede ver fácilmente H(X)>=0. Esto corresponde al caso de menor incertidumbre

Además, H(X)<=log(|A|), |A|=cantidad de elementos A. Lo que corresponde al caso de mayor incertidumbre, símbolos equiprobables.


Entropía

Definición: x es una variable aleatoria discreta(V.A.D.) con probabilidad p(x) y un conjunto de mensajes posibles A={x1,...,xN}.

Definición: Entropía

Observación: H(X) = E{ -log p(X) }

Ax

xpxpXH )(log)()(


Ejemplos de códigos

111110.125Tormenta

110100.125Lluvia

10010.25Sol

0000.5Nublado

Código 2Código 1ProbabilidadEvento


Largo medio

El largo medio de estos códigos es:

donde C(x) es el largo de x. Para este caso

L1 = 2L2 = 0.5 x 1 + 0.25 x 2 + 0.125 x 3 + 0.125 x 3 = 1.75

H(x) =1.75

Alcanzamos la entropía.

X

xCxpxCEL )()()}({


Largo medio: ejemplo

Fuente con dos símbolos X={x1,x2}, con probabilidades p1 y p2.

Caso 1p1=p2=0.5; x1=”0”; x2=”1”

H(X)=0.5 x log2(2) + 0.5 x log2(2) = 1

L = 0.5 x 1 + 0.5 x 1 = 1

Caso 2

p1=0.1; p2=0.9; x1=”0”; x2=”1”

H(X)=0.1 x log2(10) + 0.9 x log2(10/9) = 0.467

L = 0.1 x 1 + 0.9 x 1 = 1


Shannon

Se puede demostrar que no existe ningún código que permita codificar a un bit-rate menor a la entropía.

Teorema (Shannon 1948)

Se puede demostrar también que el bit rate se puede acercar arbitrariamente a la entropía.

)(}min{ XHL


Entropía conjunta

Definición: La entropía conjunta H(X,Y) de un par de variables aleatorias con distribución p(x,y) es:

Teorema (Regla de la cadena):

),(log),()},(log{),(yxpyxpyxpEYXH

)|()(),( XYHXHYXH


Entropía Condicional

Definición: La entropía condicional de dos variables (X,Y)~p(x,y) es:

Observación: A(X) es el alfabeto de X

)( )(

)(

)|(log),(

)|()()|(

XAx YAy

XAx

xypyxp

xXYHxpXYH


Kullback-Leibler

Definición: La entropía relativa o “distancia” Kullback-Leibler entre dos distribuciones de probabilidad p(x) y q(x) se define como:

Teorema:

y la igualdad se cumple si p(x)=q(x)

Ax xqxpE

xqxpxpqpD

)(

)(log

)(

)(log)()||(

0)||( qpD


Kullback-Leibler: Aplicaciones

Teorema: H(X) <= log(|A|)

Teorema: El condicionar reduce la entropía, H(Y|X) <= H(Y)

y la igualdad se da si X e Y son independientes.


Extensión de una fuente

Extensión de orden Nzi=(xi1, xi2, ... , xiN)

p(zi)= p(xi1) p(xi2)... p(xiN)

Teorema:

H(XN)=N.H(X)


Extensión de una fuente: ejemplo

Fuente con dos símbolos X={x1,x2}, con probabilidades p1=0.1 y p2=0.9

Z={x1x1, x1x2, x2x1, x2x2}

p(Z)={0.01, 0.09, 0.09, 0.81}

H(Z)=0.01 x log2(100) + 2 x ( 0.09 x log2(100/9) )

+ 0.81xlog2(100/81) = 0.934=2 x 0.467

C1={“00”,“01”,“10”,“11”}L1 = 0.01 x 2 + 2 x ( 0.09 x 2 ) + 0.81 x 2 = 2

C2={“111”,“110”,“10”,“0”}L2 = 0.01 x 3 + 0.09 x 3 + 0.09 x 2 + 0.81 x 1 = 1,29


Regla de la cadena

Teorema: (Regla de la cadena) (X1,...,Xn) ~ p(x1,...,xn):

Teorema:

n

iiin XXXHXXH

1111 ),...,|(),...,(

n

iin XHXXH

11 )(),...,(


Dependencia

Observando el estado del tiempo en días sucesivos se ve que el estado del tiempo en un día depende del día anterior y condiciona el siguiente.

No es simplemente una variable aleatoria sin memoria.


Formalización: Markov de orden k

Una fuente se dice Markov de orden k si símbolos sucesivos son estadísticamente dependientes, i.e. cada símbolo depende de los k anteriores

Una fuente MKS se especifica con:

kiXXxXp kiii ,),,|( 1


MKS: Entropía

La entropía de una fuente markov se define a partir de la entropía condicional

En general HMKS(X) < HDMS(X), por lo tanto, podríamos comprimir aún más!

Vale el resultado H(XN)=N.H(X)

),,|(),,()( 11 kiikiiMKS XXXHXXpXH

),,|(log),,|(),,|(

121

1

kiiikiii

kii

XXxXpXXxXpXXXH


Métodos para símbolos dependientes

Codificación condicional: Se calculan las nuevas probabilidades dado el símbolo anterior. (H(X|Y)<H(X) )

Codificación en bloques: Se agrupan símbolos consecutivos en bloques (nuevos símbolos).

Codificación predictiva: Dado Xi predecimos Xi+1 y codificamos la diferencia.


Ejemplo: codificación predictiva de imágenes

Idea: Usa la redundancia presente en la imagen (la correlación entre los píxeles) para estimar el nivel de gris en (i,j): Î(i,j). Error: e(i,j)=Î(i,j)-I(i,j).

Compresión con pérdidas. Los valores de e(i,j) son cuantificados y comprimidos.

Compresión sin pérdidas. La señal e no es cuantificada.


Predicción lineal. T: template con píxeles anteriores

El alfabeto de los errores de predicción será el doble de grande que el original.

Un buen predictor minimiza el error; el símbolo más probable será el 0.

Ti

iixax̂



La predicción es Î=(a+b+c+d)/4.



Imagen diferencia y su histograma



¿Cómo hallar los ai ?

Si asumimos I estacionario con media 0. Encontramos los ai minimizando la esperanza del error.

),1()1,1()1,(ˆ321 jiIajiIajiIaI

)1,0()0,0()0,1()1,1()1,1()0,1()0,0()1,0()0,1()1,1()1,0()0,0(

321

321

321

RRaRaRaRRaRaRaRRaRaRa



Códigos

Definición: Un código de fuente C, para una V.A.D, es un mapeo de A a D*, el conjunto de secuencias finitas de símbolos de una alfabeto D.

Observación: C(x) es el código para x y l(x) su largo

Observación: Típicamente usaremos: D =B = {0,1}

N

i

iDD1

*


Códigos: Largo Esperado

Definición: El largo esperado de un código de fuente C es:

Ejemplo: A={N,S,L,T} p(N)=1/2 p(S)=1/4 p(L)=p(T)=1/8C(N)=0 C(S)=10 C(L)=110 C(T)=111.l(N)=1 l(S)=2 l(L)=l(T)=3L (C)=1,75

Ax

xlxpCL )()()(


Códigos no singulares

Definición: Un código se dice no singular si cada elemento de A se mapea en un elemento diferente en D*.

Definición: La extensión C* de C es el mapeo de secuencias de símbolos de A en secuencias de D,

C(x1x2...xn)=C(x1)C(x2)...C(xn)


Códigos de decodificación única

Definición: Un código se dice de decodificación únicasi su extensión es no singular.

Definición: Un código es instantáneo si ninguna palabra de código es prefijo de otra.

códigos

singulares

nosingulares

unívocamentedecodificables

nounívocamentedecodificables

instantáneos

noinstantáneos


Desigualdad de Kraft

Teorema: Para cada código instantáneo sobre un alfabeto de dimensión d=|D|, los largos de las palabras del código, li , deben satisfacer:

Dados li que cumplen lo anterior, existe un código instantáneo con esos largos.

1

i

lid


Códigos óptimos

Teorema: El largo esperado (L) de cualquier código instantáneo (C) para una V.A.D cumple

y se da la igualdad si y solo si d-li = pi

(1er. Teorema de Shannon)

XHCL


Cotas para el L óptimo

Motivación para

Teorema: Sean li* los largos de los códigos óptimos y L* el largo esperado asociado entonces:

1)(*)( XHLXH

xp1log


Codificación en bloques

¿Que pasa si juntamos símbolos?

C(x1...xn), l(x1...xn)

Definición: Largo esperado por símbolo

Corolario: Para Xi I.I.D

)...(),...,(111 nnn xxlxxp

nL

nXHLXH n

1)()(


Códigos de Huffman

¿Podemos llegar a codificar con H(X) bits? Idea: Usar códigos más cortos para símbolos más

probables (Código Morse).

Ejemplo. C(N)=0, C(S)=10, C(L)=110, C(T)=111.

¿Cómo encontrar el código óptimo de forma sistemática?


Algoritmo de Huffman

p(N)=0.5

p(S)=0.25

p(L)=0.125

p(T)=0.125

p(X)=0.25

p(Y)=0.5

p(N)=0.5p(N)=0.5

p(S)=0.25

0

10

11

0

10

110

111

1

00

10

110

111


Run Length Encoding

Útil cuando símbolos consecutivos son idénticos. Cada símbolo es seguido por el número de repeticiones.

Zero run length coding

teoría de la información - cs.uns.edu.arldm/mypage/data/ss/info/teoria_de_la_inform...y la...

Documents