Resumen

Transmisión de Datos Multimedia - Master IC 2006/2007Transmisión de Datos Multimedia - Master IC 2006/2007

Resumen.Resumen.

1. Introducción.2. Características de la imagen.

2.1 Captura y digitalización de imagen. 2.2 Tipos de imagen (según su resolución)

3. Compresión de imagen. Redundancia espacial. 3.1 Estándar JPEG 3.2 JPEG Escalado 3.2 Wavelets

EZW JPEG 2000 LTW

4. Conclusiones.

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

2

3.2 Redundancia espacial: Wavelets (DWT).

Discrete Wavelet Transform (DWT): Se basa en un conjunto de funciones básicas que se derivan de una función prototipo (“madre”). Estas funciones son escalados y desplazamientos de la función prototipo. Permiten analizar regiones de la señal con diferente detalle (resolución). Analiza de forma independiente las bajas y altas frecuencias de la

señal (realmente actúa como un filtro).

Problemas con la DCT Efectos de borde en los

bloques Base ortonormal fija

(cosenos a distinta frec)

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

3

Esquema general de un codificador basado en DWT.

QQ Cod. Coef.Q.

Cod. Coef.Q.

Transmisión / Almac.

Transmisión / Almac.

IDWT (T -1)

IDWT (T -1)

Q -1Q -1 Dec. Coef.Q.

Dec. Coef.Q.

DWT (T)

DWT (T)

P C=T(P) C q =Q(C)

C q C’=Q -1(C q)P’=T -1(C’)

bitstream

1ª parte del compresor

2ª parte del compresor

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

4

Implementación descomposición 1DWavelet : filtros.

Dos funciones: Función generadora del espacio wavelet ()

Función de escalado () que define la señal en el espacio original a distintas escalas

Esquema general de la 1D FWT y la 1D IWT calculada con filtros

2

Paso bajo

2

2

Paso alto

S S

2

Análisis Síntesis

p0,φ

kh

kg

p1,φ

p1,ψ

kh~

kg~ p0,φ

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

5

Aplicación del filtro paso bajo a una componente n, utilizando un filtro con cinco taps

El esquema Filter-Bank

s0 s1 s2 … sn-2 sn-1 sn sn+1 sn+2 sm-2 sm-1 sm…

+

0h 1h

2h1h

2h

rn/2

221101122 hshshshshsr nnnnni donde i = n/2


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

6

Aplicación del filtro paso bajo a una componente n+2, utilizando un filtro con cinco taps



+

0h 1h

2h1h

2h

r(n/2)+1

2413021121 hshshshshsr nnnnni donde i = n/2


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

7

Aplicación del filtro paso bajo a la última componente, utilizando un filtro con cinco taps



+

0h 1h

2h1h

2h

? ?

Tanto en el inicio de la señal como en el final no disponemos de suficientes elementos para tratar la señal de la misma forma que el resto de elementos


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

8

Aplicación del filtro paso bajo a la última componente, utilizando un filtro con cinco taps


rm/2

+

0h 1h

2h1h

2h

s1s2 sm-1 sm-2s0 s1 s2 … sn-2 sn-1 sn sn+1 sn+2 sm-2 sm-1 sm…

Aplicamos extensión simétrica

2211011222/ hshshshshsr mmmmmm


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

9

Aplicación del esquema Filter-Bank directo sobre una señal 1-D


s1s2 sm-1 sm-2

ancho / 2


ancho

filtro paso bajo

r0 r1 r(m/2)-1 rm/2…

ancho / 2

filtro paso alto

d0 d1 d(m/2)-1 dm/2…

Se puede volver a aplicar la WT


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

10

Aplicación de varios niveles de descomposición (I)

s

s

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

11

Aplicación de varios niveles de descomposición (II)

s

H

G 2

2

r1

d1

r1 d1

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

12

Aplicación de varios niveles de descomposición (III)

s

H

G 2

2

H

G 2

2r1

r2

d2

d1

r2 d1d2

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

13

Aplicación de varios niveles de descomposición (IV)

s

H

G 2

2

H

G 2

2

H

G 2

2

r1

r2 r3

d3

d2

d1

r3 d1d2d3

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

14

Descomposición Wavelet: ejemplo Haar Wavelet.

Filtros: Filtro paso bajo (), H={h0,h1}={0.5, 0.5}

Filtro paso alto (), G={g0,g1}= {0.5, -0,5}

3

-5

2

6

s=

-1

4

4

-2

s1=

+

+

-

-

1.5

-2.5

4

-2

s2=

+

-

Versión ortogonal de la Haar Wavelet

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

15

Una familia de wavelets: Haar wavelet I

caso otroen ,0

1t0.5 si ,1

0.5t0 si ,1

)(t

caso otroen ,0

1t0 si ,1)(t

)12()2()( ttt

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

16

Una familia de wavelets: Haar wavelet II

caso otroen ,0

1t0 si ,1)(t

)2()(0,1 tt

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

17

Una familia de wavelets: Haar wavelet III

caso otroen ,0

1t0 si ,1)(t

)2()(0,1 tt

)12()(1,1 tt

1-2k0

),2(2)(n

,

ktt nnkn

n: Escalak: Desplazamiento

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

18

Otras wavelets

El filtro más utilizado para compresión de imagen es el Bi-ortogonal(9,7)

k Análisis paso bajo k Análisis paso alto

0 0.602949018236360 1 0.557543526228500

1 0.266864118442875 2, 0 0.295635881557125

2 0.078223266528990 3, 1 0.028771763114250

3 0.016864118442875 4, 2 0.045635881557125

4 0.026748757410810

k Síntesis paso bajo k Síntesis paso alto

0 0.557543526228500 1 0.602949018236360

1 0.295635881557125 0, 2 0.266864118442875

2 0.028771763114250 1, 3 0.078223266528990

3 0.045635881557125 2, 4 0.016864118442875

3, 5 0.026748757410810

kh kg

kh~ kg~

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

19

Aplicación de wavelets sobre imágenes I (2D)

MN

Imagen

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

20

Aplicación de wavelets sobre imágenes II (2D)

Hf

Gf

2

2

MN

M/2

N Low

High

HighLow

Esquema Filter-Bank sobre una señal 2-D: Aplicar 1-D sobre filas

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

21

Aplicación de wavelets sobre imágenes III (2D)

Hf

Gf

2

2

Hc 2

Gc 2

Hc 2

Gc 2

MN

M/2

N Low

High

M/2N/2

LL

LH

HL

HH

LL

HH

HL

LH

Esquema Filter-Bank sobre una señal 2-D: Aplicar 1-D sobre columnas

LL -> Subbanda de baja frecuencia

LH, HL y HH -> Subbandas de alta frecuencia

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

22

Aplicación de wavelets sobre imágenes IV (2D)

Hf

Gf

2

2

Hc 2

Gc 2

Hc 2

Gc 2

MN

M/2

N Low

High

M/2N/2

LL

LH

HL

HH

Esquema Filter-Bank sobre una señal 2-D: Segundo nivel de descomposición

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

23

Aplicar la 1D DWT primero por filas y luego por columnas

LH1 HH1

HL1LL1

Mayor parte de la energía

en subbanda LL

LH1 HH1

HL1LH2 HH2

HL2LL2

Aplicación de wavelets sobre imágenes V (2D)

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

24

Aplicación sobre imágenes, ejemplo I

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

25

Aplicación sobre imágenes, ejemplo II

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

26

Aplicación sobre imágenes, ejemplo III

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

27

Aplicación sobre imágenes, ejemplo IV

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

28

Implementación descomposición 1DWavelet : lifting.

Sucesivos pasos de predicción y actualización

Ventajas del cálculo por lifting: Asintóticamente es el doble de rápido Permite cálculo in-situ (ahorro de memoria / desordenados) Transformada inversa fácil de calcular (sentido inverso) Permite cálculo con enteros sin pérdidas (redondeo)

K1

p1,ψ

p0,φ

K0

p1,φ

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

29

El esquema Lifting

Transformada general del esquema Lifting

{si0}T

ransformada

Lazy

P1(z){xi}

U1(z) PN(z) UN(z)

+ +

K1

K0

{di0}

{si1} {si

N}

{di1} {di

N}

Salida paso bajo

Salida paso alto,

,11 k

nkn

ni

ni skPdd Nn ,,2,1

k

nkn

ni

ni dkUss ,1 Nn ,,2,1

Implementación descomposición 1DWavelet : lifting.

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

30

Principales inconvenientes de la DWT para imágenes: Requiere la imagen entera en memoria

Afecta dispositivos de memoria limitada como PDAs, cámaras, etc. Problema en general para imágenes grandes (GIS)

Pobre aprovechamiento de la caché (accesos múltiples)

Propuestas iniciales para reducir memoria Dividir la imagen en trozos más reducidos (tiling en JPEG2K)

Reaparecen los efectos de borde en los bloques Menor eficiencia: no se elimina correlación de toda la imagen

Algoritmos basados en líneas (line based)

““Deshacerse de los coeficientes wavelets tan pronto Deshacerse de los coeficientes wavelets tan pronto como sea posible”como sea posible”

Algoritmos basados en línea para la 2D DWT

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

31

Primer nivel de descomposición: Entrada: líneas de la imagen Se calcula la transformada 1D de cada línea y se almacenan en un

buffer (tamaño 2N+1) Cuando el buffer está lleno aplicamos un paso de transformada por

columnas (primero filtro paso alto, luego filtro paso bajo) Se obtiene una línea de cada subbanda wavelet y una línea de la

subbanda LL1

Buffer de primer nivel2N+1

HL1

LH1

HH1

ancho/2

ancholínea de la imagen (LL0 )

LL1


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

32

Primer nivel de descomposición: Las líneas HL1, HH1, LH1 son parte del resultado final (almacenar,

comprimir, etc.) La línea LL1 es entrada del siguiente nivel Continúa el cálculo a este nivel:

se desplaza el buffer dos veces (se descartan las dos líneas superiores y se introducen dos nuevas líneas de la imagen)

se repite el mismo proceso


HL1

LH1

HH1

ancho/2


LL1


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

33

Segundo nivel de descomposición: Entrada: líneas LL1 del primer nivel Se repite el mismo proceso que en el nivel anterior


HL1

LH1

HH1

ancho/2


LL1

Buffer de segundo nivel

ancho/2

ancho/4LL2


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

34

Nivel n-ésimo de descomposición:


HL1

LH1

HH1

ancho/2


LL1

Buffer de segundo nivel

ancho/2

ancho/4LL2

nlevel

LLnlevel ancho/2nlevel-1

…

El esquema se repite hasta alcanzar el nivel n-ésimo de descomposición deseado

Uso de memoria Algoritmo line-based (asintótico,

cuando nlevel tiende a infinito)“Dos veces el ancho del primer buffer”

vsAlgoritmo normal“Ancho de imagen × alto de imagen”



Resumen.Resumen.



3. Compresión de imagen. Redundancia espacial. 3.1 Estándar JPEG 3.2 Wavelets

EZW JPEG 2000 LTW

4. Conclusiones.

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

36

Wavelets: Cuantización y codificación.

Una vez descompuesta la imagen en sub-bandas, se procede a cuantificar los coeficientes wavelets. La mayor parte de la energía está concentrada en las

bandas de menor frecuencia. Existe una relación clara entre los coeficientes de la misma

posición espacial en las diferentes bandas (ver imagen ejemplo).

Algoritmos propuestos: Embedded Zero-tree Wavelet (EZW) Set Partitioning In Hierarchical Trees (SPIHT) Set Partitioning Embedded Block (SPECK) Embedded block coding with Opt. Truncation (EBCOT)

(JP2K) Lower-Tree Wavelet (LTW)

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

37

Wavelets: Algoritmo EZW.

Basado en la definición de árboles de coeficientes Hay coeficientes en diferentes subbandas que

representan la misma posición espacial en la imagen. En imágenes naturales, la mayor parte de

energía se centra en las bandas de menor frecuencia. Cuanto más cerca del nodo raíz está

un coeficiente, mayor magnitud tiene Si un nodo es menor que un umbral,

posiblemente sus descendientes también lo serán.

El algoritmo realiza aproximaciones sucesivas (planos de bits) con dos pasos por plano

Utiliza un codificador aritmético 4 símbolos: sp, sn, zr, iz

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

38


INICIALIZACION: n: número de bits necesarios para codificar el mayor coeficiente.

PASO DOMINANTE (se almacena el mapa para localizar coeficientes) 1) Los coeficientes que necesitan exactamente n bits para ser

codificados se etiquetan como significantes (positivo sp o negativo sn), se añaden a una lista de significantes y ya no se procesan en otros pasos dominantes.

2) El resto de coeficientes (que necesitan menos de n bits): Si todos sus descendientes también necesitan menos de n

bits, se etiqueta todo el árbol como raíz de un árbol de ceros (zr)

Sino, se etiqueta ese coeficiente como cero aislado (iz) PASO SUBORDINADO (se almacenan los bits de los

coeficientes) Se codifica el bit n de los coeficientes de la lista de significantes

Si no se ha alcanzado la tasa de bits deseada (embedded): Se decrementa n en uno (vamos al siguiente bit de menor peso) Procedemos a realizar una nueva iteración (pasos dominante y

subordinado)

max2log cn

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

39

11 4 -1 2-6 3 2 1 4 2 7 1 3 0 2 2

Wavelets: Algoritmo EZW. Ejemplo I

24 3 0

-6

17 2 2

3

2-1 2 1

4

11

Símbolos = {sp,zr,zr,zr}Bits={}Lista signif = {}

Símbolos = {sp,zr,zr,zr, sp,sn,iz,zr,zr,zr,zr, sp,zr,zr,zr, sp,zr,zr,zr}

Bits={0}Lista signif = {1011}

1011 0100 0001 00100110 0011 0010 00010100 0010 0111 00010011 0000 0010 0010

3

* 0100 0001 00100110 0011 0010 00010100 0010 0111 00010011 0000 0010 0010

2

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

40

Wavelets: Algoritmo EZW. Ejemplo II

11 4 -1 2-6 3 2 1 4 2 7 1 3 0 2 2

24 3 0

-6

17 2 2

3

2-1 2 1

4

11

Símbolos = {sp,zr,zr,zr, sp,sn,iz,zr,zr,zr,zr, sp,zr,zr,zr, sp,zr,zr,zr,sp, zr,sp,sp,zr, sp,sp,zr, zr,sp,sp}

Bits={0, 1, 0, 1, 0, 1}Lista signif = {

1011, 0100, 0110, 0100, 0111}

* * 0001 0010 * 0011 0010 0001 * 0010 * 00010011 0000 0010 0010

1

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

41


11 4 -1 2-6 3 2 1 4 2 7 1 3 0 2 2

24 3 0

-6

17 2 2

3

2-1 2 1

4

11

¿Cuándo dejamos de codificar? Cuando terminamos con la cuota de bits

Varias opciones a la hora de que el decodificador complete los bits no transmitidos: Relleno de ceros (p.ej 101xxx 101000) Relleno de unos (p.ej 101xxx 101111) Reducir el intervalo de error (p.ej 101xxx 101100)


Resumen.Resumen.




EZW

JPEG 2000 LTW

4. Conclusiones.

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

43

3.2 Redundancia espacial: JPEG 2000.

Estándar ISO/ITU (‘01) que amplía y mejora el anterior JPEG. Mejora la compresión usa transformada Wavelet Hay versión con pérdidas y sin pérdidas. Permite multiresolución (gracias al análisis Wavelet). Permite dividir la imagen en bloques de cualquier

tamaño (no solo 8x8) (incluso un único bloque) Permite codificar Regiones de Interés (ROI) Es más robusto frente a errores.

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

44

JPEG 2000: Motivación

Inconvenientes del EZW: Debido a las estructuras de árboles, los errores se propagan

de unas subbandas a otras → Menor robustez frente a errores.

Debido a la codificación progresiva por planos de bits, no hay escalabilidad espacial (sólo de calidad SNR).

JPEG 2000 corrige estos inconvenientes: Codifica las distintas subbandas por bloques y de forma

independiente, sin utilizar árboles (algoritmo Embedded Block Coding with Optimized Truncation, EBCOT). Se utiliza un nuevo algoritmo de optimización de Lagrange para

suplir la pérdida de eficiencia al no aprovechar la redundancia existente entre subbandas.

Se introduce una etapa de reordenación de coeficientes que permite todo tipo de escalabilidad (al no haber árboles los coeficientes se reordenan con mayor facilidad).

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

45

JPEG 2000: Estructura

Estructura de un codificador JPEG 2000: Una imagen se puede dividir en bloques denominados tiles

(normalmente hay sólo uno). A cada tile se le aplica el algoritmo JPEG2000:

Se calcula su transformada Wavelet.Se cuantizan los coeficientes.Se aplica el algoritmo EBCOT por bloques (de 32x32 ó

64x64 coeficientes) (tier 1 coding)Se organiza el bit stream (tier 2 coding) según la

escalabilidad deseada.– Escalabilidad espacial: Se sitúan primero las subbandas

de menor frecuencia.– Escalabilidad SNR o en calidad: Se codifica primero los

planos de bits de los coeficientes de mayor magnitud.

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

46

JPEG 2000: Comparativa JPEG-JPEG2000

Comparación objetiva

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

47

JPEG 2000: Comparativa JPEG-JPEG2000

Original: 700 kbytes Comprimida con JPEG6,1 kbytes - 1:115

Comparación subjetiva

Comprimida con JPEG 20006,1 kbytes - 1:115


Resúmen.Resúmen.




EZW JPEG 2000

LTW

4. Conclusiones.

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

49

3.2 Lower Tree Wavelet (LTW) Encoder

Propuesta del LTW: Codificar los coeficientes sin hacer una pasada por cada

plano de bits La cuantización se realiza con dos estrategias:

Cuantización fina: Es una cuantización escalar uniforme de todos los coeficientes

Cuantización gruesa: Eliminar algunos bits menos significativos de los coeficientes rplanes: número de bits menos significativos a eliminar

Un coeficiente es significativo si es distinto de 0 después de descartar los primeros rplanes bits ( c ≥ 2rplanes )

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

50

LTW: Algoritmo I, una aproximación sin árboles

Recorrer todas las subbandas Para cada coeficiente de esa subbanda

Calcular el número de bits necesario para representarlo (nbits)

Si es significativo (c ≥ 2rplanes i.e., nbits > rplanes),

– Arithmetic_output nbits

– Binary_output los bits significantes y el signo

Sino (no es significante),

– Arithmetic_output LOWER

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

51

0

01

1

-1

0 -1

0

0

+1

0

1

1

-10

+1

rplanes=2

0 1 -1 2

3 1 -8 3

47 -2 -1 4

6,+,{011

}L L

3,+,{}

L L4,-,{0}

L L L L L

LTW: Ejemplo del algoritmo simple

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

52

El algoritmo tiene escalabilidad espacial (codificando las subbandas de mayor a menor)

No hay dependencia entre (inter) subbandas

Mayor posibilidad de robustezMenor nivel de compresión

Siempre se codifica un símbolo por coeficiente

3/4 partes del tiempo de ejecución se pasan en el codificador aritmético““Hay que agrupar los coeficientes Hay que agrupar los coeficientes insignificantes”insignificantes”

Características del algoritmo simple

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

53

Usar árboles (quad-trees) como una forma rápida y eficiente de agrupar coeficientes

Rápida: forma sencilla de agrupar coeficientesEficiente: elimina redundancia entre subbandas

Otras propuestas usan árboles de coeficientes pero

Con codificación por planos de bits, y múltiples pasadas a la imagen (EZW, SPIHT, etc.)

Con lentos algoritmos iterativos de optimización R/D (SFQ)

LTW: Algoritmo II, con árboles

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

54

Un coeficiente es raíz de un lower-tree si este coeficiente y todos sus descendientes son insignificantes (esto es, menores que 2rplanes)

La raíz del árbol se etiquetará como LOWER (L)El resto de coeficientes son LOWER_COMPONENTS (*) y NO

necesitan ser almacenados.

Si un coeficiente es insignificante, pero tiene algún descendiente significante, no forma un árbol:

Se etiqueta como ISOLATED_LOWER (I)

LTW: Definiciones para uso de árboles

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

55

Es un algoritmo de dos pasadas Primera pasada: Los coeficientes se etiquetan según su

significancia

Las subbandas se recorren en bloques de 2x2

Si todos los coeficientes del bloque y sus descendientes son insignificantes Etiquetar con (*)

Si algún coeficiente del bloque (o descendientes) son significantes Cada coeficiente se etiqueta con (L), (I ) o (nbits) según su significancia

Segunda pasada: Los coeficientes se codifican de manera similar al Algoritmo I, usando los símbolos calculados en la primera pasada

Algoritmo LTW

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

56

Queremos codificar una imagen de ejemplo de 8x8 rplanes=2, los coeficientes en el intervalo ] 22, -(22)[ son insignificantes

51 42 -9 2 4 4 0 -1

25 17 10 11 3 1 0 2

12 3 3 -2 2 -2 -5 3

-9 -3 3 -3 0 3 -1 2

-4 1 1 2 0 2 1 3

2 -3 0 2 1 -1 -1 -2

1 3 2 1 1 2 -3 1

-2 -3 3 -12 2 0 2 1

Nos centramos en el 1er nivel

En este bloque -4 es significante, y necesita 3 bits

El resto son insignificantes (LOWER)

Algoritmo LTW: un ejemplo

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

57


51 42 -9 2 4 4 0 -1

25 17 10 11 3 1 0 2

12 3 3 -2 2 -2 -5 3

-9 -3 3 -3 0 3 -1 2

3 L 1 2 0 2 1 3

L L 0 2 1 -1 -1 -2

1 3 2 1 1 2 -3 1

-2 -3 3 -12 2 0 2 1

Estos bloques no son significantes y sus componentes se etiquetan como LOWER_COMPONENT *


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

58


51 42 -9 2 4 4 0 -1

25 17 10 11 3 1 0 2

12 3 3 -2 2 -2 -5 3

-9 -3 3 -3 0 3 -1 2

3 L * * 0 2 1 3

L L * * 1 -1 -1 -2

* * 2 1 1 2 -3 1

* * 3 -12 2 0 2 1

En este bloque hay otro significante


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

59


51 42 -9 2 4 4 0 -1

25 17 10 11 3 1 0 2

12 3 3 -2 2 -2 -5 3

-9 -3 3 -3 0 3 -1 2

3 L * * 0 2 1 3

L L * * 1 -1 -1 -2

* * L L 1 2 -3 1

* * L 4 2 0 2 1

Todos los bloques de esta subbanda son insignificantes


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

60


51 42 -9 2 4 4 0 -1

25 17 10 11 3 1 0 2

12 3 3 -2 2 -2 -5 3

-9 -3 3 -3 0 3 -1 2

3 L * * * * * *

L L * * * * * *

* * L L * * * *

* * L 4 * * * *

Estos bloques tienen significantes


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

61


51 42 -9 2 3 3 0 -1

25 17 10 11 L L 0 2

12 3 3 -2 2 -2 3 L

-9 -3 3 -3 0 3 L L

3 L * * * * * *

L L * * * * * *

* * L L * * * *

* * L 4 * * * *

Estos bloques tienen significantes

Mientras que estos son insignificantes


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

62


51 42 -9 2 3 3 * *

25 17 10 11 L L * *

12 3 3 -2 * * 3 L

-9 -3 3 -3 * * L L

3 L * * * * * *

L L * * * * * *

* * L L * * * *

* * L 4 * * * *

Ahora nos centramos en el siguiente nivel

Este coeficiente y todos sus descendientes son insignificantes: símbolo LOWER


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

63


51 42 -9 2 3 3 * *

25 17 10 11 L L * *

12 L 3 -2 * * 3 L

-9 -3 3 -3 * * L L

3 L * * * * * *

L L * * * * * *

* * L L * * * *

* * L 4 * * * *

Este coeficiente es insignificante, pero tiene un descendiente significante: símbolo ISOLATED_LOWER


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

64


51 42 -9 2 3 3 * *

25 17 10 11 L L * *

12 L 3 -2 * * 3 L

-9 I 3 -3 * * L L

3 L * * * * * *

L L * * * * * *

* * L L * * * *

* * L 4 * * * *

Este coeficiente es signficante, lo representamos con nbits (4)


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

65


51 42 -9 2 3 3 * *

25 17 10 11 L L * *

4 L 3 -2 * * 3 L

-9 I 3 -3 * * L L

3 L * * * * * *

L L * * * * * *

* * L L * * * *

* * L 4 * * * *

Este coeficiente es significante, pero sus descendientes no: forma un lower-tree especial (con raíz significante) y se codifica con un símbolo nbits especial


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

66


51 42 -9 2 3 3 * *

25 17 10 11 L L * *

4 L 3 -2 * * 3 L

4L I 3 -3 * * L L

3 L * * * * * *

L L * * * * * *

* * L L * * * *

* * L 4 * * * *

Este bloque y todos sus descendientes son insignificantes: el árbol puede continuar creciendo


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

67


51 42 -9 2 3 3 * *

25 17 10 11 L L * *

4 L * * * * 3 L

4L I * * * * L L

3 L * * * * * *

L L * * * * * *

* * L L * * * *

* * L 4 * * * *

El primer paso terminaría al calcular el resto de símbolos


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

68


6 6 4 L 3 3 * *

5 5L 4L 4 L L * *

4 L * * * * 3 L

4L I * * * * L L

3 L * * * * * *

L L * * * * * *

* * L L * * * *

* * L 4 * * * *

En el segundo paso, todos los símbolos (excepto (*)) se codifican como en el Algoritmo I.

Orden en el que se recorren las subbandas (escalabilidad espacial)


Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

69

En nivel del compresión, el LTW funciona igual o mejor que la mayor parte de compresores

LTW: comparación con Lena usando Rate/PSNR

codec\rate

EZW SPIHTStack Run

Embedded Run-length

JPEG2000

LTW

2 n/a 45.07 n/a n/a 44.62 45.46

1 39.55 40.41 n/a 40.28 40.31 40.50

0.5 36.28 37.21 36.79 37.09 37.22 37.35

0.25 33.17 34.11 33.63 34.01 34.04 34.31

0.125 30.23 31.10 n/a n/a 30.84 31.27

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

70

Lena codificada a 0.125 bpp

LTW

LTW: comparación subjetiva con Lena

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

71

Lena codificada a 0.125 bpp

JPEG 2000

LTW: comparación subjetiva con Lena

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

72

Codificador LTW: Hasta 13 veces más rápido que J2K, y 3 veces más rápido que

SPIHT Decodificador LTW:

Hasta 2 veces más rápido que J2K, y 2.5 veces más rápido que SPIHT

LTW: Comparación en tiempo de ejecución

café coding café decoding

codec\rate

SPIHT JPEG 2000 LTW SPIHT JPEG 2000 LTW

2 4368.7 7393.1 1494 3775 2373.0 1505.6

1 2400.1 6907.6 963 1935 1475.2 911.6

0.5 1399.3 6543.9 654 1024 991.8 569.5

0.25 889.8 6246.2 476 586 763.6 366.6

Tiempo en millones de ciclos de CPU (sin la DWT)

Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7Tra

nsm

isió

n d

e D

ato

s M

ult

imed

ia -

Mast

er

IC 2

00

6/2

00

7

73

Mas información en…

http://www.grc.upv.es/

Documents

Resumen