Matemática Computacional
Filtrado en el dominio de la Frecuencia
MATEMÁTICA COMPUTACIONAL - MA475
1
Logro El alumno, al término de la sesión, será capaz de entender el filtrado en el dominio de la frecuencia y su relación con la Transformada de Fourier, sus propiedades y algunas de sus aplicaciones al procesamiento de imágenes.
MATEMÁTICA COMPUTACIONAL - MA475
2
Cuantificación
Cuando se captan las señales de la imagen por un registrador, tenemos lo siguiente, línea por línea:
Muestreo Línea AB trazada para digitalizar la imagen
Función contínua generada por la línea AB del registrador colocada en escala de grises y puntos del muestreo
Para poder generar la digitalización de la imagen (muestreo) usaremos la Transformada de Fourier. Esto se hace en los filtros de paso banda como veremos más adelante. MATEMÁTICA COMPUTACIONAL - MA475
3
Filtrado en el dominio de la frecuencia • Un filtro puede verse como un mecanismo de cambio o transformación de una señal de entrada a la que se le aplica una función, conocida como función de transferencia, para obtener una señal de salida. • Todas estas señales y funciones pueden ser discretas o continuas, aunque en el tratamiento de imágenes se usan señales y funciones discretas.
Filtro discreto con entrada E, salida S y función de transferencia H.
MATEMÁTICA COMPUTACIONAL - MA475
4
• Las representaciones en el dominio de la frecuencia, debido a que explican cómo se repiten los píxeles de una imagen, consiguen representar la información de tal imagen. • Esta representación es especialmente útil, ya que teniendo la frecuencia de repetición de los elementos que componen una imagen, se pueden apreciar y alterar directamente elementos como el ruido, los bordes, las texturas, etc. • Transformadas en el dominio de la frecuencia usadas en tratamiento de imágenes: Transformada de Fourier (funciones base: senos y cosenos) Transformadas del coseno (funciones base: cosenos) Transformadas wavelets (funciones base: Haar, Daubechies, …) Transformada de Karhaunen-Loeve o Análisis de Componentes Principales (PCA)
MATEMÁTICA COMPUTACIONAL - MA475
5
Transformada de Fourier • Una serie de Fourier puede considerarse como la suma de un conjunto de funciones sinusoidales de diferentes frecuencias, promediada por unos coeficientes, con el objetivo de aproximarse a una función 𝑓(𝑥). • Una función periódica en el tiempo, de periodo 𝑇0 (𝑇0 = como :
2𝜋 ) 𝜔
, puede expresarse
• El conjunto de señales sinusoidales (senos y cosenos), constituyen una base de funciones en el dominio de la frecuencia. • La transformada de Fourier de una función f(x) es una extensión de las series de Fourier a señales no periódicas.
MATEMÁTICA COMPUTACIONAL - MA475
6
Ejemplo Calcule la transformada de Fourier de la función 𝐴,
−
𝑓 𝑡 = 0,
𝑊 𝑊 ≤𝑡≤ 2 2
𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
Solución: Usaremos la fórmula de Euler: 𝑒 𝑗𝜔𝑡 = cos 𝜔𝑡 + 𝑗𝑆𝑒𝑛(𝜔𝑡) 𝑊/2
∞
𝐹 𝜇 = න −∞
𝑓(𝑡)𝑒 −𝑗(2𝜋𝜇)𝑡 𝑑𝑡
= න
𝐴𝑒 −𝑗(2𝜋𝜇)𝑡 𝑑𝑡
−𝑊/2
−𝐴 −𝑗 = 𝑒 𝑗2𝜋𝜇
2𝜋𝜇 𝑡
𝑠𝑒𝑛(𝜋𝜇𝑊) = 𝐴𝑊 𝜋𝜇𝑊
MATEMÁTICA COMPUTACIONAL - MA475
7
Otras definiciones: • La expresión obtenida al final del cálculo del ejemplo, es conocida como función sinc. 𝑠𝑖𝑛𝑐(𝑚) = 𝑠𝑒𝑛(𝜋𝑚) 𝜋𝑚
• El valor absoluto de la transformada, |𝐹 𝜇 | , espectro de Fourier o espectro de frecuencia • La función impulso unitario está definida por:
se conoce como
Para una variable contínua 𝒕
∞ , 𝛿(𝑡 − 𝑡0 ) = ቊ 0 ,
𝑠𝑖 𝑡 = 𝑡0 𝑠𝑖 𝑡 ≠ 𝑡0
Para una variable discreta 𝒙
1 𝛿(𝑥 − 𝑥0 ) = ቊ 0
, ,
𝑠𝑖 𝑥 = 𝑥0 𝑠𝑖 𝑥 ≠ 𝑥0 MATEMÁTICA COMPUTACIONAL - MA475
8
La función del ejemplo anterior, junto a su transformada y a su espectro, aparecen graficadas aquí.
Gráfica de la función f(t)
Gráfica de la transformada de Fourier de f(t)
Gráfica del espectro de Fourier de f(t)
Se puede observar, de los gráficos, que las posiciones de los CEROS (tanto de 𝐹 𝜇 como de 𝐹 𝜇 ) son inversamente proporcionales al largo de la función rectangular (𝑊) y que la altura de las curvas disminuye en función de la distancia al origen. Eso es muy importante al momento de analizar los filtros. MATEMÁTICA COMPUTACIONAL - MA475
9
Ejemplos: 1. Halle la transformada de Fourier de:
1 , 𝑓 𝑥 = ቐ2𝜀 0 ,
2, 1 − 𝑥 2. Halle la transformada de Fourier de: 𝑓 𝑥 = ቊ 0 ,
MATEMÁTICA COMPUTACIONAL - MA475
|𝑥| ≤ 𝜀 𝑥 >𝜀
𝑥 1
10
Propiedades importantes: • La función impulso tiene la “propiedad de selección” en lo que se refiere a la integración. Esta propiedad consiste en que ella nos informa el valor de la función 𝑓(𝑡) en la posición del impulso, 𝑡0 . Es ∞ decir: ∞ , 𝑠𝑖 𝑡 = 𝑡 𝛿(𝑡 − 𝑡0 ) = ቊ
0
0
,
𝑠𝑖 𝑡 ≠ 𝑡0
න 𝑓(𝑡)𝛿(𝑡 − 𝑡0 ) 𝑑𝑡 = 𝑓(𝑡0 )
−∞
• La transformada de Fourier de un impulso unitario con el impulso posicionado en 𝑡0 , es: ∞
𝐹 𝜇 = න 𝛿(𝑡 − 𝑡0 )𝑒 −𝑗(2𝜋𝜇)𝑡 𝑑𝑡 = 𝑒 −𝑗(2𝜋𝜇)𝑡0 = cos 2𝜋𝜇𝑡0 − 𝑗sen(2𝜋𝜇𝑡0 ) −∞
MATEMÁTICA COMPUTACIONAL - MA475
11
Convolución Sean 𝑓1 (𝑡) y 𝑓2 (𝑡) dos funciones continuas. La convolución de 𝑓1 (𝑡) y 𝑓2 (𝑡) está definida por la función: ∞
𝑓 𝑡 = 𝑓1 𝑡 ∗ 𝑓2 𝑡 = න 𝑓1 (𝑥)𝑓2 (𝑡 − 𝑥)𝑑𝑥 −∞
Ejemplo: Compruebe que: 𝑓 𝑡 ∗ 𝛿 𝑡 = 𝛿 𝑡 ∗ 𝑓 𝑡 = 𝑓(𝑡)
MATEMÁTICA COMPUTACIONAL - MA475
12
Ejemplo: Halle la convolución de las funciones:
MATEMÁTICA COMPUTACIONAL - MA475
13
Ejemplo: Calcule la transformada de Fourier de 𝑓 𝑡 ∗ ℎ 𝑡 Solución:
∞
𝑓 𝑡 ∗ ℎ 𝑡 = න 𝑓 𝑥 ℎ 𝑡 − 𝑥 𝑑𝑥 −∞
Sean 𝐹(𝜇) y 𝐻 𝜇 las transformadas de Fourier de 𝑓 𝑡 y ℎ 𝑡 , respectivamente. ∞
F 𝑓 𝑡 ∗ℎ 𝑡
= න
∞
න 𝑓 𝑥 ℎ 𝑡 − 𝑥 𝑑𝑥 𝑒 −𝑗2𝜋𝜇𝑡 𝑑𝑡
−∞ −∞ ∞
= න𝑓 𝑥 −∞ ∞
∞
න ℎ 𝑡 − 𝑥 𝑒 −𝑗2𝜋𝜇(𝑡−𝑥) 𝑑𝑡 𝑒 −𝑗2𝜋𝜇𝑥 𝑑𝑥 −∞ ∞
= න 𝑓 𝑥 𝑒 −𝑗2𝜋𝜇𝑥 𝑑𝑥 = 𝐻 𝜇 න 𝑓 𝑥 𝑒 −𝑗2𝜋𝜇𝑥 𝑑𝑥 = 𝐻 𝜇 𝐹(𝜇) −∞
F 𝑓 𝑡 ∗ℎ 𝑡
−∞
= 𝐹(𝜇)𝐻 𝜇 MATEMÁTICA COMPUTACIONAL - MA475
Esto relaciona al dominio espacial con el dominio de la frecuencia
14
Transformada de Fourier para imágenes • La transformada de Fourier para imágenes es una función sobre un espacio bidimensional discreto y está dada por:
Transformada de Fourier
Espectro de la Imagen
Imagen original MATEMÁTICA COMPUTACIONAL - MA475
15
Ejemplo de Aplicación Supongamos que tenemos la siguiente imagen y que cada uno de los cuadros representa un píxel cuya intensidad (en escala de grises) va representada por 8 bits.
Calculemos el espectro de dicha imagen. Solución: Para facilitar los cálculos, asumamos que los niveles de gris son 0 y 1, y al final los multiplicaremos por 255 para que nos de el resultado real.
MATEMÁTICA COMPUTACIONAL - MA475
16
Ejemplo de Aplicación Ahora, usemos la transformada de Fourier para generar nuestra matriz con u y v. Para esto se asume que si "𝑥" va de 0 a M-1 e "𝑦" va de 0 a N-1, entonces 𝑢 y 𝑣 tendrán los mismos intervalos discretos. Entonces, tendremos:
2
2
1 −𝑗(2𝜋) 𝐹 𝑢, 𝑣 = 𝑓(𝑥, 𝑦)𝑒 9
𝑢𝑥 𝑣𝑦 + 3 3
𝑥=0 𝑦=0
Como tenemos que :
𝑓 0,0 = 1; 𝑓 0,1 = 0; 𝑓 0,2 = 1; 𝑓 1,0 = 0; 𝑓 1,1 = 1; 𝑓 1,2 = 0; 𝑓 2,0 = 1; 𝑓 2,1 = 0; 𝑓 2,2 = 1
Entonces : 1 −𝑗 𝐹 𝑢, 𝑣 = 1+𝑒 9
4𝜋 3 𝑣+
2𝜋 −𝑗( 3 ) 𝑢+𝑣 𝑒
+
4𝜋 −𝑗 3 𝑢 𝑒 +
MATEMÁTICA COMPUTACIONAL - MA475
4𝜋 −𝑗 3 (𝑢+𝑣) 𝑒
17
Ejemplo de Aplicación Usando que 𝑒 𝑗𝑤 = cos 𝑤 + 𝑗𝑆𝑒𝑛 𝑤 , se puede comprobar que: 𝐹 0,0 =
5 ; 9
2 𝐹 1,2 = ; 9
𝐹 0,1 =
1+𝑗 3 1−𝑗 3 1+𝑗 3 −1 + 𝑗 3 ; 𝐹 0,2 = ; 𝐹 1,0 = ; 𝐹 1,1 = ; 18 18 18 9
1−𝑗 3 2 −1 − 𝑗 3 𝐹 2,0 = ; 𝐹 2,1 = ; 𝐹 2,2 = 18 9 9
Pero, el espectro de Fourier es el módulo de F(u,v), por lo tanto, la matriz del espectro será: x 255 0,5 0,1 0,1 128 26 26 0,1 0,1
0,2 0,2 0,2 0,2
26 51 51 26 51 51 Espectro de la Imagen
MATEMÁTICA COMPUTACIONAL - MA475
18
Transformada de Fourier inversa para imágenes • La transformada de Fourier Inversa para imágenes es una función sobre un espacio bidimensional y está dada por:
Recuperación
Imagen parecida a la original
Espectro de la Imagen MATEMÁTICA COMPUTACIONAL - MA475
19
Pasos para la Recuperación • Paso 1: Se aplica la transformada de Fourier inversa. En el caso anterior, tenemos: 2
2
1 𝑗(2𝜋) 𝑓 𝑥, 𝑦 = 𝐹(𝑢, 𝑣)𝑒 9
𝑢𝑥 𝑣𝑦 3+3
𝑢=0 𝑣=0
y
128 26 26
26 51 51
26 51 51
• Paso 2: Se reordena la matriz resultante, de tal manera que el f(0,0) se encuentre en el centro de la nueva matriz. Para esto se cambia a "𝑥" por (x+k mod M) , "𝑦" por (y+t mod N). En el caso del ejemplo anterior, tendríamos que k=t=1. 128 26 26 Si la matriz fuese entonces, la matriz cambiada sería: 51 26 26 26
51 51
51 51
51 51
128 26
• Paso 3: A partir de la matriz obtenida en el paso anterior, se calcula una nueva matriz en base a la siguiente fórmula: 𝑠 = 𝐿𝑛(1 + 𝑚𝑎𝑡𝑟𝑖𝑧 ) , donde 𝑚𝑎𝑡𝑟𝑖𝑧 es el módulo de cada uno de los números complejos de la matriz. MATEMÁTICA COMPUTACIONAL - MA475
20
51 26 51
• Paso 4: Se reescalan los valores obtenidos a la escala del 0 al 255, usando la técnica de reescalamiento enseñada anteriormente.
Ejemplo de Aplicación Recupere la imagen cuyo espectro está dado por Solución:
128 26 26
26 51 51
26 51 51
Paso 1: Se aplica la transformada de Fourier Inversa y obtenemos la matriz: 436 52 52
52 127 127
52 127 127
MATEMÁTICA COMPUTACIONAL - MA475
21
Paso 2: Se aplica el intercambio a la matriz. En este caso, también k=t=1. 127 52 127
52 436 52
127 52 127
• Paso 3: Aplicamos la fórmula: 𝑠 = 𝐿𝑛(1 + 𝑚𝑎𝑡𝑟𝑖𝑧 ) y obtenemos: 4,8520 3,9703 4,8520
3,9703 6,0799 3,9703
4,8520 3,9703 4,8520
• Paso 4: Se reescalan los valores obtenidos a la escala del 0 al 255, usando la 𝑦 = 120,87363 ∗ (𝑥 − 3,9703) fórmula: Con esto obtenemos:
107 0 107
0 255 0
107 0 107
Y esta matriz se parece mucho a la imagen original. MATEMÁTICA COMPUTACIONAL - MA475
22
Filtros de Paso bajo • Se usan para eliminar altas frecuencias, dejando «pasar» bajas frecuencias (aquellas que están por debajo de una frecuencia de corte). • Se ponen a cero los módulos de los coeficientes de Fourier relativos a las altas frecuencias, dejando sin modificar los relativos a las bajas frecuencias.
Espectro sin filtro
Espectro con filtro paso bajo
MATEMÁTICA COMPUTACIONAL - MA475
Imagen recuperada
23
Filtros de Paso alto • Se usan para eliminar bajas frecuencias, dejando «pasar» altas frecuencias (aquellas que están por encima de una frecuencia de corte). • Se ponen a cero los módulos de los coeficientes de Fourier relativos a las bajas frecuencias, dejando sin modificar los relativos a las altas frecuencias.
Espectro sin filtro
Espectro con filtro paso alto
MATEMÁTICA COMPUTACIONAL - MA475
Imagen recuperada
24
Filtros de Paso banda • Permanece inalterada una banda (o rango) de frecuencias • Sirve para eliminar ruido estructural.
MATEMÁTICA COMPUTACIONAL - MA475
25