Filtros en el dominio espacial - Lección 05 · 2017-07-03 · Operaciones sobre los valores de vecindades Teor a de sistemas y ltrado espacial Filtros en el dominio espacial Lecci

Operaciones sobre los valores de vecindadesTeorıa de sistemas y filtrado espacial

Filtros en el dominio espacialLeccion 05.1

Dr. Pablo Alvarado Moya

CE5201 Procesamiento y Analisis de Imagenes DigitalesArea de Ingenierıa en Computadores

Tecnologico de Costa Rica

I Semestre, 2017

P. Alvarado — TEC — 2017 Operaciones espaciales 1 / 24


Contenido

1 Operaciones sobre los valores de vecindades

2 Teorıa de sistemas y filtrado espacialLinealidad e Invarianza a la traslacionConvolucion

Separabilidad

Correlacion



Operaciones espaciales

1 Operaciones geometricas

2 Operaciones sobre valores de pıxeles

3 Transformaciones de dominio




Operaciones sobre los valores de vecindades

Para imagen de entrada A, la imagen de salida B es

B = {b | b = 〈x,d〉 , d = T (val(N(a))), a = 〈x, c〉 ∈ A}



Linealidad e Invarianza a la traslacionConvolucionCorrelacion

Teorıa de sistemasTres tareas basicas

a(x , y) b(x , y)T [·]

1 Simulacion de sistemas: T y a conocidos, determinar b

2 Reconstruccion de senales: T y b conocidos, determinar a

3 Identificacion de sistemas: a y b conocidos, determinar T




Diferencias de PDI con PDS tradicional

1 la senales se definen en el espacio y no en el tiempo

2 dos variables independientes espaciales en vez de unatemporal.




Linealidad

a(x , y) b(x , y)T [·]

Si bi (x , y) = T [ai (x , y)] entonces

T [k1a1(x , y) + k2a2(x , y)] = k1T [a1(x , y)] + k2T [a2(x , y)]

o en general

T

[N∑

k=1

kiai (x , y)

]=

N∑k=1

kiT [ai (x , y)] =N∑

k=1

kibi (x , y)




Invarianza a la traslacion

a(x , y) b(x , y)T [·]

Si b(x , y) = T [a(x , y)] entonces:

b(x − x0, y − y0) = T [a(x − x0, y − y0)]




Sistemas LSI

LSI: Linear and Shift InvariantLTI: Linear and Translation Invariant

( Equivalente a los sistemas LTI en el tiempo )




Impulso unitario bidimensional

δ(x , y) = δ(x)δ(y) =

{1 si x = y = 0

0 en el resto

Propiedad de muestreo:

u

vu

v

Pıxel en posicion (u, v): f (x , y)δ(x − u, y − v)




Imagen como suma de pıxeles

f (x , y) =∑(u,v)

f (u, v)δ(x − u, y − v) = f (x , y) ∗ δ(x , y)




Convolucion

Sea T un sistema LSI

g(x , y) = T [f (x , y)] = T

∑(u,v)

f (u, v)δ(x − u, y − v)

=

∑(u,v)

T [f (u, v)δ(x − u, y − v)]

=∑(u,v)

f (u, v)T [δ(x − u, y − v)]

=∑(u,v)

f (u, v)h(x − u, y − v)

= f (x , y) ∗ h(x , y)

con respuesta al impulso h(x , y) = T [δ(x , y)]




Funcion de dispersion puntual

La respuesta al impulso h(x , y) = T [δ(x , y)] llamada en PDItambien funcion de dispersion puntual o PSF por point spreadfunction




Pasos de la convolucion

f (x , y) ∗ h(x , y) =∑(u,v)

f (u, v)h(x − u, y − v)

Cuatro pasos:

1 Invertir h tanto en x como en y (rotacion en 180◦)

2 Trasladar origen de h invertida a pıxel de interes en (x , y)

3 Multiplicar punto a punto h invertida y trasladada con x

4 Sumar todos los productos anteriores y asignarlos al resultadog(x , y).




Otra interpretacionConvolucion

f (x , y) ∗ h(x , y) =∑(u,v)

f (u, v)h(x − u, y − v)

superposicion de la PSF desplazada a cada (u, v) y amplificada porel respectivo f (u, v) (sistema LSI).




PropiedadesConvolucion

Conmutatividad:

a(x , y) ∗ b(x , y) = b(x , y) ∗ a(x , y)

Asociatividad:

a(x , y) ∗ b(x , y) ∗ c(x , y) = [a(x , y) ∗ b(x , y)] ∗ c(x , y)

= a(x , y) ∗ [b(x , y) ∗ c(x , y)]

Distributividad:

a(x , y)∗(b(x , y)+c(x , y)) = a(x , y)∗b(x , y)+a(x , y)∗c(x , y)




Costo de la convolucion

Imagen f (x , y) tiene R filas y C columnas

h(x , y) (kernel, nucleo, mascara, PSF) tiene N filas yM columnas con x ∈ {xi , . . . , xf }, y ∈ {yi , . . . , yf },N = yf − yi + 1, M = xf − xi + 1

La convolucion se puede reescribir

f (x , y) ∗ h(x , y) =

y−yi∑v=y−yf

x−xi∑u=x−xf

f (u, v)h(x − u, y − v)

para recorrer la mascara.

Tamano mascara: K = NM, tamano imagen: S = RC

Cada pıxel: K productos, K − 1 sumas

Total operaciones: SK productos, S(K − 1) sumas




Filtro separable

Kernel h(x , y) separable si

h(x , y) = hh(x)hv (y)




Convolucion con filtro separable

f (x , y) ∗ h(x , y) =

y−yi∑v=y−yf

x−xi∑u=x−xf

f (u, v)hh(x − u)hv (y − v)

=

y−yi∑v=y−yf

hv (y − v)

x−xi∑u=x−xf

f (u, v)hh(x − u)

La suma interna gx(x , v) =

x−xi∑u=x−xf

f (u, v)hh(x − u) es un filtrado

unidimensional para cada fila v de f (x , y), y ası:

f (x , y) ∗ h(x , y) =

y−yi∑v=y−yf

h(y − v)gx(x , v)




Costo de convolucion separable

Pıxel en una fila: M productos, M − 1 sumas(Producto punto)

Fila: MC productos y C (M − 1) sumas

Todas las filas MRC = MS productos,RC (M − 1) = S(M − 1) sumas.

Pıxel en una columna: N productos, N − 1 sumas.

Columna: NR productos y R(N − 1) sumas.

Todas las columnas NRC = NS productos,RC (N − 1) = S(N − 1) sumas.

Gran total: S(N + M) productos, S(N + M − 2) sumas




Comparacion de mascaras separables y no separables

Asumase N = M, R = C (mascara e imagen cuadradas)

Mascara no separable: R2N2 productos, R2(N2 − 1)

Mascara separable: R22N productos, R2(2N − 2) sumas

O(N2) contra O(N)




Correlacion

Correlacion:

f (x , y)◦h(x , y) = f (x , y)∗h(−x ,−y) =∑u,v

f (u, v)h(x+u, y+v)

La mascara no se rota, como la convolucion

Se utiliza para buscar patrones similares a h




Resumen


2 Teorıa de sistemas y filtrado espacialLinealidad e Invarianza a la traslacionConvolucion

Separabilidad

Correlacion




Este documento ha sido elaborado con software libre incluyendo LATEX, Beamer, GNUPlot, GNU/Octave, XFig,Inkscape, LTI-Lib-2, GNU-Make y Subversion en GNU/Linux

Este trabajo se encuentra bajo una Licencia Creative Commons Atribucion-NoComercial-LicenciarIgual 3.0 Unpor-ted. Para ver una copia de esta Licencia, visite http://creativecommons.org/licenses/by-nc-sa/3.0/ o envıeuna carta a Creative Commons, 444 Castro Street, Suite 900, Mountain View, California, 94041, USA.

© 2005-2017 Pablo Alvarado-Moya Area de Ingenierıa en Computadores Instituto Tecnologico de Costa Rica


http://creativecommons.org/licenses/by-nc-sa/3.0/

Documents

Filtros en el dominio espacial - Lección 05 · 2017-07-03 · Operaciones sobre los valores de vecindades Teor a de sistemas y ltrado espacial Filtros en el dominio espacial Lecci