Post on 18-Oct-2015
transcript
Transformadas de Imagen
Autores:Jos Luis Alba, Fernando Martn - Universidad de Vigo
Jess Cid - Universidad Carlos III de Madrid
Ultima revisin: mayo de 2006
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 2
Introduccin
Igual que en el procesado unidimensional las transformadas nos permiten un cambio de dominio.
Veremos diferentes transformadas para imgenes en escala de grises (y tamao NxN): T. Fourier (y DFT). T. Coseno (DCT). Karhunen Love (KLT).
Comentaremos sus aplicaciones: Procesado. Reconocimiento. Codificacin.
Tambin se pueden aplicar a las componentes de una imagen en color (RGB, YUV, HSV).
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 3
Transformada de Fourier
Imagen discreta Funcin continuaN N
j(mw nw )
m n
U(w ,w ) u[m,n]e += =
= 1 21 11 20 0
T. directa (ec. de anlisis)
T. inversa
(ec. de sntesis)
Dos frecuencias (w1 y w2) horizontal y vertical:
j(mw nw )u[m,n] U(w ,w )e dw dw+< > < >
= 1 21 2 1 22 2 214
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 4
Transformada de Fourier (II)
U(w1, w2) es peridica en w1 y w2 con periodo 2. Si u[m,n] es real (casi siempre):
*U(w ,w ) U ( w , w )= 1 2 1 22 2 Simetra
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 5
Transformada de Fourier Discreta, DFT
Imagen discreta Imagen discreta (compleja)N N j (mk nl)
N
m n
v[k,l] u[m,n]e +
= == 21 1
0 0
T. directa (ec. de anlisis)
T. inversa (ec. de sntesis)
V[k,l] es un muestreo de la transformada continua:
N N j (mk n l)N
m n
u[m,n] v[k,l]eN
+
= == 21 12
0 0
1
v[k,l] U(k ,l )N N = 2 2
Si u es real, v es simtrica: *v[k,l] v [N k, N l]=
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 6
Transformada de Fourier Discreta, DFT (II)
V[k,l] slo est definida entre 0 y N-1 para k y l. Suele extenderse peridicamente (como en una
dimensin):
v[k,l] v[k N,l] v[k,l N]v[k N,l N].....
= = ==
Con esta extensin es peridica en k y en l con periodo N.
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 7
Matlab:
I1 = fft2 (i1) % Transformada directa (algoritmo rpido)
i1=uint8(real(ifft2(I1))) % Transformada inversa (algoritmo rpido)
Icentrada = fftshift(I1) % Centrar la transformada (para verla mejor)
% Propiedad: X == fftshitf(fftshift(X))
DFT, Implementacin
FFTSHIFT FFTSHIFT
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 8
Matlab:
i1 = imread(lenna2.bmp);
I1=fft2(i1); % Transformada
Ilog = log(abs(I1)); % Escala logartmica
Ishow = mat2gray(fftshitf(Ilog));% Centrar y reescalarimshow(Ishow) % Mostrarla como imagen
colormap(jet),colorbar% Representar en color mesh(Ishow)% Representacin en 3D
Ejemplo
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 9
Transformadas Ortogonales
T. General: Imagen discreta Imagen discreta
T. directa (ec. de anlisis)
T. inversa (ec. de sntesis)
Condiciones de los coeficientes de la transformacin:
N N
klm n
v[k,l] u[m,n]a [m,n]
= == 1 1
0 0N N
*kl
k 0 l 0
u[m,n] v[k,l]a [m,n]
= == 1 1
N N*
k ' l 'klm n
a [m,n]a [m,n] [k k ',l l ']
= == 1 1
0 0Ortonormalidad
N N*
klklk l
a [m,n]a [m',n '] [m m',n n ']
= == 1 1
0 0Completitud
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 10
Transformadas Ortogonales (II)
La propiedad de completitud asegura que la transformada es invertible.
La de ortonormalidad asegura que la energa se concentra en los primeros coeficientes:
Aproximacin de orden P,Q
(filtrado paso-bajo)
QP*
klPQk l
u [m,n] v[k,l]a [m,n]
P,Q N
= ==
11
0 0
La ortonormalidad minimiza el error cuadrtico:N N
PQm n
(u[m,n] u [m,n])
= = = 1 12 2
0 00NQP 2 ===
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 11
Transformadas Separables
Si se cumple: La transformada es separable y se definen:
):(][][],[ (ln)/2)(/2ln)(/2 NjkmNjkmNjlkkl eeeejnbmanma == +
]n[bb,]m[aa,
lln
kkm
==
BA
Si se cumple la ortonormalidad, A y B son otogonales:
I)B(B
I,)A(A*
*
==
t
t
Transformada en forma matricial: Muchas veces, A=B,
tAUBV =tAUAV =
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 12
Matrices (o imgenes) Base
a*k es la k-sima columna de (A*)t. O atk es la k-sima fila de A. Se define la matriz base kl: La t. inversa se puede escribir:
tk
*k
*kl
* )(aaA =
N N*
klm n
v[k,l]
= == U A1 1
0 0
Esta frmula se puede usar en
decodificacin progresiva
v[k,l] se puede hallar como proyeccin (producto escalar): >=< kl*,]l,k[v AU
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 13
Decodificacin Progresiva
DCT en bloques 8x8. 1, 3, 6, 15, 36 y 64 coeficientes.
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 14
DFT Normalizada
Normalizando las frmulas de la DFT:
T. directa (ec. de anlisis)
T. inversa (ec. de sntesis)
Se consigue que sea ortogonal y separable:
N N j (km ln)N
m n
v[k,l] u[m,n]eN
+
= == 21 1
0 0
1
=
=+= 1N
0k
1N
0l
ln)km(N2j
e]l,k[vN1]n,m[u
j (km ln)N
kl k l
j kmN
k
a [m,n] e a [m]a [n]N
a [m] eN
+
= =
=
2
2
1
1
akl[m,n] cumplen las dos
propiedades. Las matrices A y B son iguales.
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 15
Transformada Discreta del Coseno, DCT
Las frmulas son:
T. directa (ec. de anlisis)
T. inversa (ec. de sntesis)
=
=
++=1
0
1
0
)2
)12(cos()2
)12(cos(],[][][],[N
m
N
n Nln
NkmnmulklkU
=
=
++=1
0
1
0
)2
)12(cos()2
)12(cos(][][],[],[N
k
N
l Nln
NlmlklkUnmu
=
=02
01
x,N
x,N]x[
Donde:
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 16
Transformada Discreta del Coseno, DCT (II)
Es ortogonal y separable:
La DCT es una matriz real. Significado fsico muy similar a DFT. No aparece replicada y no tiene simetras. No posee la propiedad de convolucin.
akl [m,n] cumplen las dos
propiedades. Las matrices A y B son iguales.
)2
)12(cos(][][a
][a][a)2
)12(cos()2
)12(cos(][][],[a
Nkmkm
nmN
lnN
kmlknm
k
lkkl
+=
=++=
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 17
Transformada Discreta del Coseno, DCT (III)
La DCT concentra mucho la informacin en los primeros coeficientes, es la ms usada en codificacin.
DFT DCT
Con imagen real la DFT es redundante y sobra la mitad del cuadrado. La DCT guarda la misma informacin (la imagen original) en el doble de espacio (pero es real).
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 18
Matlab:
Idct = dct2 (i1) % Transformada directa
i1=uint8(idct2(Idct)) % Transformada inversa
DCT, Implementacin
Existen algoritmos rpidos para la DCT: Basados en tcnicas matriciales. Basados en FFT.
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 19
Codificacin por transformadas
El estndar JPEG est basado en este tipo (JointPhoto-graphic Experts Group)
La transformacin ms utilizada es la DCT
Codificacinde entropaCuantificacinTransformacin
DCT Cuantif
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 20
Codificacin JPEG bsica o JFIF
La imagen se divide en bloques 8x8. Se hace la DCT de cada bloque (restando 128 previamente). Se cuantifica cada DCT (aqu estn las prdidas y la
primera compresin).
A cada bloque se le aplica compresin sin prdidas:RLE (Run Length Encoding) + VLC (Variable Length Code, tipo Huffman).
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 21
Transformacin por bloques La DCT en bloques de la imagen The cameraman
DCT(bloques 8x8)
Codificacin JPEG (II)
Funciones base de la DCT
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 22
Codificacin JPEG (III)
Efecto de la cuantificacin Efecto de eliminar el 43% de los coeficientes
IDCTCuantif.
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 23
Efecto de eliminar el 56% de los coeficientes Se aprecia el ringling effect: oscilaciones en los bordes
Efecto de eliminar el 85% de los coeficientes Se aprecia blocking effect
IDCT
IDCT
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 24
Codificacin JPEG (IV) Cuantificacin de los coeficientes
de la DCT. Pasos: a Cuantificacin de los 64
coeficientes (muchos de ellos se reducen a cero).
b Los coeficientes son codificados en umbral, usando una matriz de cuantificacin. (A la matriz de cuantificacin se le
pueden aplicar factores de escala para obtener diversos niveles de compresin).
c Preparacin de los coeficientes para la codificacin de entropa (cadena unidimensional de 64
coeficientes en orden cuasi ascendente de las componentes de frecuencia).
Para ello se reordenan los coeficientes usando una exploracin en zig-zag.
El primer coeficiente del barrido en zig-zag se conoce como coeficiente DC mientras que el resto son los coeficientes AC
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 25
Codificacin JPEG (V) Imagen en color:
Se repite el proceso para Y, U y V. U y V se diezman por 2 en horizontal y/o vertical.
El coeficiente DC de cada bloque se codifica independientemente usando DPCM (codifica la diferencia entre coeficiente DC del presente bloque y el del bloque previamente codificado).
Recorrido en zig-zag (frecuencia decreciente): La cuantificacin produce muchos ceros en coeficientes AC. Este orden crea series de ceros. Es til para compresin RLE.
Asignacin de cdigo de longitud variable Los coeficientes AC no nulos se codifican utilizando un cdigo de longitud
variable que define el valor del coeficiente y el nmero de ceros precedentes.
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 26
Codificacin JPEG (VI)
Compresin RLE: transforma una secuencia de nmeros en una secuencia de pares de smbolos (longitud, valor).
Codificacin Huffman: Codifica smbolos en secuencias de bits de longitud variable, de acuerdo con la
frecuencia con que se repiten. Premisa:
Si el smbolo sk es ms frecuente que el smbolo sj sk debe ocupar menos bits que sj. Pasos:
(1) Ordena los smbolos en orden de probabilidades decrecientes.
(2) Genera iterativamente un rbol agrupando las ramas de menor probabilidad
11111000110101000000 (5,1) (3,0) (2,1) (1,0) (1,1)RLC
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 27
Codificacin JPEG (VII)
Modos con y sin prdidas Rendimiento:
8-1 (2 bits/pxel): Calidad indistinguible
10.7-1 (1.5 b/p): Excelente
21.4-1 (0.75 b/p): Muy buena
32 - 1 (0.5 b/p): Buena
64 - 1: (0.25 b/p) Aceptable
IDCTQ-1DeCodentropa
Bloque 8x8
Tabla deespecs.
Tabla deespecs.
DECODIFICADORDatos
DCT Q Codificadorentropa
Datos
Tabla deespecificaciones
Tabla deespecificaciones
CODIFICADORBloque
8x8 pixels
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 28
Codificacin JPEG (VIII)
Esquema de codificacin JPEG
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 29
Codificacin JPEG-2000 Caractersticas bsicas:
Modos con y sin prdidas Rendimiento: excelente a tasas de 32-1 (0.5 b/p). Compresin eficiente de documentos mixtos Codificacin de regiones de inters Codificacin progresiva y escalabilidad Representacin en multi-resolucin Mejor robustez: resistencia a errores Mecanismos de proteccin: Marcas de agua Descripcin de contenidos
Aplicaciones: Imgenes para WWW e Internet Teledeteccin Compresin cuadro a cuadro en vdeo Bibliotecas digitales. Telemedicina, Televigilancia Scanner, fax Fotografa electrnica ...
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 30
Compresin: 1. La imagen se divide
en componentes. 2. Cada componente
de divide en baldosas rectangulares (tamao a elegir)
3. Cada baldosa de divide en componentes multirresolucin(mediante la transformada wavelet)
4. Cada subbanda se cuantifica de modo independiente.
Wavelettransform Q
Codificadorentropa
Datos
CODIFICADOR
Baldosarectan-gular
Imagen Componente Baldosa
Codificacin JPEG-2000 (II)
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 31
Efecto del embaldosado:
(a) Original (b)-(d)
Compresin JPEG2000 a 0.255 bpp:
(b) Sin embaldosado
(c) Embaldosado 128 x 128
(d) Embaldosado 64 x 64
Codificacin JPEG-2000 (III)
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 32
Tecnologa de compresin: Wavelets
FPB
FPA
2
2
FPB
FPA
2
2
FPB
FPA
2
2
Cod
FPB
FPA
2
2
Cod
Cod
......H V
Codificacin JPEG-2000 (IV)
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 33
Cuantificacin: Se utiliza un cuantificador escalar uniforme con una zona muerta
en torno al origen. El paso de cuantificacin, b, determina las prdidas del
compresor, y la tasas de compresin. b = 1 Compresin sin prdidas (reversible). b > 1 Compresin con prdidas. El valor del parmetro debe
incluirse en el tren de datos codificados. Puede utilizarse un paso de cuantificacin por cada subbanda.
Elimina ruido y aumenta la frecuencia de ceros, lo que facilita la codificacin posterior
Codificacin JPEG-2000 (V)
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 34
Codificacin JPEG-2000 (VI)
Regiones de inters en JPEG-2000
Tasa: 0.1 bppDefinicin de Regiones de Inters (ROI)
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 35
Original JPEG 2000: 80:1 JPEG, 56:1
(a) Original, 256x256, 24 bit RGB
(b) JPEG, 43:1 (c) JPEG2000 43:1
JPEG-2000 V.S. JPEG
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 36
JPEG-2000 V.S. JPEG
Compresina 0.25 b/p (Izda)
JPEG (Dcha)
JPEG-2000
Compresina 0.2 b/p (Izda)
JPEG (Dcha)
JPEG-2000
(b)
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 37
Transformada de Karhunen-Love, KLT
Caso particular de anlisis por componentes principales (PCA, Principal Component Analysis).
Supongamos el conjunto de vectores de la figura:
Es posible realizar un cambio de ejes ptimo para representarlos
La KLT no es determinista: no tiene una frmula fija, los coeficientes dependen del tipo de imgenes de inters (los vectores).
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 38
Transformada KLT (II)
Una imagen u se representa como un vector J ordenando los coeficientes por columnas (en matlab J = u(:) ).
Hay que tener un conjunto de vectores Jm (muestra de las imgenes de inters, m=0...M-1).
Calculamos:
Media Matriz de covarianza(autocorrelacin)
=
= 10
1 M
mmJM
J =
= 10
1 M
m
tmm )JJ)(JJ(M
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 39
Transformada KLT (III)
es una matriz NxN. N=mxn si las imgenes tienen m filas y n columnas.
Adems es simtrica y definida positiva (autovalores reales y positivos).
Sus autovectores son una base ortonormal de RN. Matriz de autovectores:
Es ortogonal:( )Nv...vvV 21= I)V(V *t = Los autovectores vi se ordenan segn autovalor
asociado decreciente (1> 2>...> N).
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 40
Transformada KLT (IV)
Cualquier imagen (vector de RN ) se puede expresar en funcin de los autovectores:
NNv...vvJ +++= 2211 Los is son los coeficientes de la transformada KLT de J. Se pueden hallar matricialmente: O como proyeccin (producto escalar): Tambin se puede recuperar la imagen original a partir
de ellos: Los autovectores son imgenes (autoimgenes).
J)V( *tGG =
>=
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 41
Transformada KLT (V)
Podemos recuperar la imagen usando menos coeficientes:
NKv...vvJ KKK
+++= 2211
Si los vis estn ordenados el error cuadrtico de JK es menor que el de JK-1: 212
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 42
Transformada de Karhunen-Love, Aplicaciones
Codificacin: Es ptima en sentido MSE porque concentra al mximo la energa
en menos coeficientes para las imgenes dadas. Slo se puede usar pre-calculndola para el tipo de imgenes de
inters. Por eso (y por los algoritmos rpidos) se usa ms la
transformada determinista que ms concentra la energa (DCT).
Reconocimiento: Muy usada como extractor de caractersticas previo a la decisin. Se desprecian los coeficientes de mayor orden. Usada con xito en caracteres, teledeteccin, caras, huellas
dactilares...
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 43
Se busca un conjunto de imgenes ortonormales Ik tales que: cualquier imagen de cara se puede poner como una combinacin lineal de las Ik (cambio de base): si se ponen a cero los coeficientes a partir de k > K se verifica que:
Con valores de K ~ 20 se consiguen representaciones muy eficientes del espacio de caras, con lo que representando una cara por sus K coeficientes (proyecciones sobre las bases) podemos ahorrar memoria y tiempo de clculo en las comparaciones de un clasificador.
NNmmmmm IwIwIwIwJ ++++= "332211
NKKEJJJJKE
IwIwIwIwJ
RmmK
mmK
R
KKmmmmmK
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 44
Clculo de la imgenes de la nueva base ortonormal: Se parte de un conjunto de imgenes de caras representadas como vectores de dimensin N = FxC y se calcula su matriz de covarianza:
Clculo de los autovectores y autovalores de la matriz de covarianza:
MxM tamao
M)N (como 1-M rango pero NxN tamao
][1 211
=>>=
=== =T
M
TN
MmmM
m mJJJ
MJ G"GGGGGGG
( ) ( )
=====
==
kk
kkkkk
Tkkk
TkM
kkkT
kN
vvvvvvv
vvv
GGGGGGG
GGG
Ejemplo: Reconocimiento de Caras (II)
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 45
Seleccin de la representacin: Los autovectores son las imgenes que forman la base ortonormal
Se construye un subespacio seleccionando los K autovectores asociados a los K autovalores de mayor tamao:
Ejemplo: Reconocimiento de Caras (III)
Jos Luis Alba, Fernando Martn - Universidad de Vigo, Jess Cid - Universidad Carlos III 46
Proyeccin de cada cara (de media cero) en el nuevo subespacio (representacin compacta):
Ejemplo: Reconocimiento de Caras (IV)
Transformadas de ImagenIntroduccinTransformada de FourierTransformada de Fourier (II)Transformada de Fourier Discreta, DFTTransformada de Fourier Discreta, DFT (II) DFT, Implementacin EjemploTransformadas OrtogonalesTransformadas Ortogonales (II)Transformadas SeparablesMatrices (o imgenes) BaseDecodificacin ProgresivaDFT NormalizadaTransformada Discreta del Coseno, DCTTransformada Discreta del Coseno, DCT (II)Transformada Discreta del Coseno, DCT (III) DCT, ImplementacinCodificacin por transformadasCodificacin JPEG bsica o JFIF Codificacin JPEG (II)Codificacin JPEG (III)Codificacin JPEG (IV)Codificacin JPEG (V)Codificacin JPEG (VI) Codificacin JPEG (VII) Codificacin JPEG (VIII)Codificacin JPEG-2000Codificacin JPEG-2000 (II)Codificacin JPEG-2000 (III)Codificacin JPEG-2000 (IV)Codificacin JPEG-2000 (V)Codificacin JPEG-2000 (VI)JPEG-2000 V.S. JPEGJPEG-2000 V.S. JPEGTransformada de Karhunen-Love, KLTTransformada KLT (II)Transformada KLT (III)Transformada KLT (IV)Transformada KLT (V)Transformada de Karhunen-Love, Aplicaciones