• Author / Uploaded
• Salvador Gallardo

• Categories
• Transformada discreta de Fourier
• Transformada de Fourier
• Matriz (Matemáticas)
• Densidad espectral
• Píxel

Citation preview

Procesamiento Digital de Imágenes Capítulo 2

parte 1 Ingeniería Civil Biomédica

Pamela Guevara 1

Contenidos –

Redundancia • • •

en el código entre píxeles psicovisual

–

Transformada de Fourier

–

Transformada del Coseno Discreta

2

Representación de Imágenes Digitales •

•

Representar una imagen de n x n píxeles mediante una matriz requiere: –

n2 bits si es binaria

–

n2 log2 (L) bits si la imagen es en niveles de gris, con L niveles

–

3n2 log2 (L) bits si la imagen es a color (RGB) con L niveles.

Existen representaciones de imágenes que pueden ser más económicas que la representación matricial, ya que se elimina información redundante.

3

Redundancia •

Una imagen tiene redundancia cuando su representación o significado abunda en la repetición de patrones o modelos.

•

En una imagen digital hay tres tipos de redundancia: –

Redundancia en el código. •

–

Redundancia entre píxeles. •

–

Código es un sistema de símbolos usado para representar la información. A veces, la longitud de las palabras usadas en el código es mayor de lo necesario. Debida a la correlación espacial entre un píxel y sus vecinos.

Redundancia psicovisual. •

Parte de la información es ignorada por el ojo humano. 4

Redundancia •

Ejemplos de imágenes redundantes:

redundancia en el código

redundancia entre píxeles

redundancia psicovisual 5

Redundancia •

La compresión de imágenes consiste en eliminar una o más de estas redundancias.

•

Se pueden clasificar las distintas formas de compresión de imágenes en: –

con pérdida de información en la imagen: • eliminan la redundancia psicovisual

–

sin pérdida de información en la imagen: • eliminan la redundancia de código y/o entre píxeles no producen errores.

6

Compresión de imágenes eliminando la redundancia de código •

Código de longitud variable tal que a aquellos valores con más probabilidad se le asigna un menor número de bits, entonces se consigue que el promedio sea menor. –

Ej. Código de Huffman • •

La codificación de Huffman consigue el número más pequeño posible de símbolos de código. Codificación sin pérdida en imágenes en escala de grises

7

Código de Huffman Ejemplo: Consideremos una imagen con 6 niveles de grises: p(a1)=0,1 p(a2)=0,4 p(a3)=0,06

p(a4)=0,1 p(a5)=0,04

p(a6)=0,3

Observemos que si usamos el código binario natural, necesitamos 3 bits para codificar cada valor: Valor

Valor codificado

a1

000

a2

001

a3

010

a4

011

a5

100

a6

101 8

Código de Huffman El código de Huffman, en función de la probabilidad será: Valor Probabilidad Valor codificado con el código de Huffman a1 0,1 011

a2 a3 a4 a5 a6

0,4

1

0,06

01010

0,1

0100

0,04

01011

0,3

00

Ahora, el promedio de bits necesario es: 3(0,1) + 0,4 + 5(0,06) + 4(0,1) + 5(0,04) + 2(0,3) = 2,2 El radio de compresión sería: CR = 3/2,2 = 1,36 y la redundancia relativa es: R D = 1-(1/1,36) = 0,26. Por tanto, el 26% del primer código era redundante.

redundancia relativa : RD= 1 - (1/CR)

9

Compresión de imagen eliminando la redundancia entre píxeles •

Representación por filas o Run-Length Coding –

Cada fila de una imagen está completamente determinada mediante la especificación de las longitudes y los valores de secuencias de píxeles sucesivos del mismo color.

–

Si hay sólo unas pocas secuencias (r es "pequeño"), esta representación es muy económica.

10

Compresión de imagen eliminando la redundancia entre píxeles Ejemplo de Representación por filas. Caso Imagen binaria. Sólo hay que indicar el primer elemento de la fila y las longitudes de las secuencias alternadas.

11

Compresión de imagen eliminando la redundancia entre píxeles •

Representación por bloques: Árboles cuaternarios (quadtrees) –

Asumimos por simplicidad que las imágenes S son binarias y de tamaño 2k x 2k .

Método: –

El nodo raíz del árbol representa la imagen completa.

–

Si un bloque tiene valor constante, su nodo es un nodo hoja; en otro caso, su nodo tiene cuatro descendientes correspondientes a los cuatro cuadrantes del bloque.

–

El proceso se repite entonces para cada uno de esos nuevos nodos; así sucesivamente y como máximo k veces. 12

Compresión de imagen eliminando la redundancia entre píxeles •

Representación por bloques: Árboles cuaternarios Ejemplo: imagen binaria 23 x 23 Árbol cuaternario de altura 3. El orden de los hijos de cada fila es NO, NE, SO, SE. El espacio para almacenar el árbol es proporcional al número de nodos. No hay redundancia en cuanto a píxeles que aparezcan en dos nodos.

13

Compresión de imagen eliminando la redundancia entre píxeles •

Los quadtrees tienen otras aplicaciones como indexación, segmentación de imágenes, análisis de elementos finitos, detección de colisiones, etc.

•

En 3D se usan octrees.

14

Compresión de imagen eliminando la redundancia psicovisual •

La codificación con pérdida se basa en la idea de comprometer la precisión de la imagen descomprimida con el fin de lograr una mayor compresión.

•

Se necesitan indicadores que nos permitan medir el error que se comete después de comprimir y descomprimir con respecto a la imagen original.

•

Por ejemplo, el error cuadrático medio en una imagen MxN, viene dado por:

con f(x,y) la imagen original y f (x,y) la imagen obtenida después de comprimir y descomprimir. 15

Codificación por transformación en bloques •

La imagen se divide en bloques de nxn y en cada uno de ellos se realiza una codificación por transformación.

•

Para codificar se utiliza una transformada lineal, reversible, para hacer corresponder la imagen con un conjunto de coeficientes de la transformada, que después se cuantifican y se codifican.

16

Codificación por transformación en bloques •

En la mayor parte de las imágenes naturales, un número significativo de coeficientes (en el dominio transformado) tiene pequeñas magnitudes y se pueden cuantificar de forma poco precisa (o se pueden eliminar totalmente) sin que ello suponga una distorsión apreciable en la imagen.

•

En general no se utiliza compresión con pérdida en Imágenes Médicas

17

Transformadas de la Imagen •

Suponiendo que la imagen tiene tamaño NxN, su transformada puede expresarse de la forma:

Donde: – T(u,v) es la transformada de f(x,y); – g(x,y,u,v) es el núcleo (o kernel) de la transformada directa; – u y v toman valores de 0 a N-1.

•

La transformada inversa se expresa como:

donde h(x,y,u,v) es el núcleo de la transformada inversa.

18

Codificación por transformación en bloques •

El núcleo directo es separable si g(x,y,u,v) = g1(x,u) g2(y,v).

– •

Luego, la transformada bidimensional se puede calcular realizando dos transformadas unidimensionales

Además el núcleo es simétrico si g1 y g2 son iguales.

19

Codificación por transformación en bloques Expresión matricial: •

Si el núcleo g(x,y,u,v) es separable y simétrico, la transformada se puede expresar en forma matricial. Sean F, G y T las matrices de elementos:

•

La transformada: puede escribirse de la forma:

•

Para obtener la transformada inversa, se multiplica a derecha e izquierda por la matriz inversa de G y de su traspuesta: 20

La Transformada de Fourier •

La transformada de Fourier es una importante herramienta de procesamiento.

•

Se usa para descomponer una imagen en sus componentes de seno y coseno.

•

La salida de la transformada es una imagen en el dominio de Fourier (dominio de la Frecuencia), mientras que la imagen de entrada está en el dominio espacial.

•

En el dominio frecuencial, cada punto de la imagen representa una frecuencia particular contenida en el dominio espacial.

•

Aplicaciones en análisis, filtrado, reconstrucción y compresión de imágenes. 21

La Transformada de Fourier • La transformada de Fourier de una función continua e integrable en una variable real x, se define por:

• La transformada multiplica la función por un set de funciones bases de senos y cosenos de frecuencia creciente:

e iux=cos  ux  +i∗sen  ux 

i= −1

• La variable u recibe el nombre de variable de frecuencia. • La transformada de una función real es una función compleja. F(u) = R(u) + I(u)i, donde R(u) e I(u) son la parte real e imaginaria de F(u). 22

La Transformada de Fourier • Ejemplo de funciones base: senos y cosenos, donde varía la frecuencia. • Las amplitudes de éstas son calculadas mediante la TF y dependen de la función analizada.

23

La Transformada de Fourier Ejemplo para una señal unidimensional periódica (utiliza Serie de Fourier) señal unidimensional peródica aproximación con una función base aproximación con dos funciones base aproximación con tres función base

24

La Transformada de Fourier

(A) oscilación sobre un valor medio (B) representacón por una forma lineal (C) y (E) representación por una suma de ondas: La onda C describe la forma B mucho peor que las cinco ondas del gráfico D que vemos sumadas en E.

• Ejemplo para una señal periódica (utiliza Serie de Fourier) • Componentes en Frecuencia de la Señal 25

La Transformada de Fourier •

El módulo de F(u),  F  u   =  R  u 2 +I  u 2  Espectro de Fourier.

•

El cuadrado del espectro se denomina espectro de potencias ó densidad espectral de f(x).

•

Su ángulo P(u) = arctg( I(u)/R(u) ) recibe el nombre de fase.

recibe el nombre del

niveles

densidad espectral frecuencia tiempo

fase

• ejemplo para una señal transitoria frecuencia

26

La Transformada de Fourier •

La inversa de su transformada se define como:

•

Análogamente, se define la Transformada de Fourier de una función continua e integrable de 2 variables:

y su inversa como:

27

La Transformada de Fourier Discreta (DFT) Bidimensional •

Sea f(a,b) una imagen en niveles de grises (dominio espacial), tal que: –

x=0,1,...,N-1, y=0,1,…,N-1 (imagen cuadrada de NxN)

–

f(a,b) toma valores discretos representando el nivel de gris del píxel (a,b)

entonces, la Transformada Discreta de Fourier de la imagen consiste en una función F(k,l) tal que k=0,1,...,N-1 y l=0,1,...,N-1:

el término exponencial es la función base correspondiente al punto F(k,l) en el espacio de Fourier.

y su inversa como:

28

La Transformada de Fourier discreta •

La DFT no contiene todas las frecuencias que forman la imagen, pero el número de muestras es suficiente para describir la imagen en el dominio espacial.

•

El número de frecuencias corresponde al número de píxeles en el dominio espacial de la imagen, i. e., las imágenes en los dominio Espacial y de Fourier tienen el mismo tamaño.

INTREPRETACIÓN El valor de cada punto F(k,l) es obtenido al multiplicar la imagen espacial con la función base correspondiente y adicionar el resultado. Las funciones base son el seno y el coseno con frecuencias crecientes. F(0,0) representa el valor promedio de la imagen. F(N-1,N-1) representa la más alta frecuencia. 29

Propiedades de la Transformada de Fourier Transformada de Fourier Discreta (TFD) bidimensional Núcleo separable y simétrico •

La ventaja que aporta esta propiedad es el hecho de poder obtener la transformada F(k,l) (o la inversa f(a,b)) en dos pasos, mediante la aplicación de la Transformada de Fourier 1-D (o su inversa):

donde:

La matriz de la transformada se puede obtener mediante un producto de matrices T=AT FA

30

Propiedades de la Transformada de Fourier La linealidad •

La transformada de Fourier y su inversa son transformaciones lineales, es decir, poseen la propiedad distributiva respecto de la suma.

La traslación

[

TF f  a,b  e

i2pi  Ka+Ly N

] =F  k − K,l− L 

TF [ f  a− A,b−B  ] =F  k,l  e •

−i2pi  kA+lB N

(se traslada el origen de la transformada a (K, L))

Caso particular: mover el origen de la TF de f(a,b) al centro de la matriz N X N, es decir al punto (N/2,N/2). Para ello, podemos hacer uso de que:

TF[ f(a,b)(-1)x+ya] se hace corresponder con F(k-N/2, l-N/2). •

Un desplazamiento en la función f(a,n), no provocará un cambio en la magnitud de su transformada de Fourier:

 F  k,l  e

−i2pi  kA+lB  N

= F  k,l  

31

La Transformada de Fourier La simetría y periodicidad •

Si f(a,b) es real, la transformada de Fourier satisface:

|F(k,l)|=|F(-k, -l)| •

La transformada discreta de Fourier y su inversa son funciones periódicas de periodo N; es decir,

F(k,l) = F(k+N, l) = F(k, l+N) = F(k+N, l+N) Consecuencia: •

Si se desplaza el origen de la transformada al punto (N/2, N/2), para calcular la transformada de Fourier, F(k-N/2, l-N/2), en un periodo completo sólo necesitamos calcularla en los N/2 + 1 puntos primeros. 32

La Transformada de Fourier La simetría y periocidad

imagen

Espectro de Fourier sin desplazamiento

Espectro de Fourier sin desplazado al centro de la imagen 33

La Transformada de Fourier La rotación Si rotamos la función f(a,b) un ángulo determinado, la transformada de Fourier también será afectada por una rotación del mismo ángulo. Esta propiedad también se da a la inversa, es decir, si la transformada se rota en un determinado ángulo, la transformada inversa también se verá rotada ese mismo ángulo.

34

La Transformada de Fourier Representación del logaritmo del espectro •

El espectro de Fourier suele tener un rango mucho mayor que los usuales para mostrar una imagen. Una técnica usual es considerar el logaritmo del espectro usando la fórmula

D(k,l) = C( log( 1+|F(k,l)| ) )

donde C es una constante adecuada de reescalamiento de la imagen, que se aplica para obtener valores dentro de la paleta de colores disponible. 35

La Transformada de Fourier Valor Promedio •

Una definición ampliamente utilizada del valor promedio de una función discreta de dos dimensiones es:

Propiedad:

Esto quiere decir que en el centro de la imagen (si tenemos la FT centrada), tenemos el valor medio de la imagen o componente constante. 36

La Transformada de Fourier imagen

en procesamiento de imágenes normalmente se usa sólo la magnitud para obtener información pero la fase es necesaria para aplicar la transformada inversa

DFT (punto amplificado)

DFT escala logarítmica

fase

imagen reconstruida sin fase

37

La Transformada de Fourier Imagen con líneas verticales de 2 píxeles de ancho

componente DC (valor promedio)

imagen

DFT (puntos amplificados)

La frecuencia máxima que puede representar la imagen es: fmax = 1 / (2 píxeles) La frecuencia que contiene la imagen es: f = 1 / (4 píxeles) = fmax / 2 (en la mitad del rango)

38

La Transformada de Fourier Imagen con líneas oblícuas

imagen

DFT (puntos amplificados)

Se necesitan más frecuencias para representar las líneas en diagonal con las funciones base. 39

La Transformada de Fourier Imagen con líneas oblícuas

DFT en escala logarítmica

DFT (puntos obtenidos con segmentación por valor umbral y amplificados)

40

La Transformada de Fourier Distributividad con respecto a la adición

zoom

suma de las DFTs (complejas) de las 2 imágenes anteriores (puntos amplificados)

imagen reconstruida con la DFT inversa (se obtiene el equivalente a una suma de las dos imágenes originales en el dominio espacial) 41

La Transformada de Fourier Filtrado en Frecuencia (Filtro pasa bajos)

DFT en escala logarítmica (selección de bajas frecuencias)

imagen reconstruida con la DFT inversa (las líneas oblícuas presentan variaciones de más baja frecuencia en los bordes (suavizado))

42

La Transformada de Fourier Filtrado en Frecuencia (Filtro pasa bajos)

43

La Transformada de Fourier Filtrado en Frecuencia (Filtro pasa altos)

parte real positiva

FFT(espectro)

amplitud

parte real + parte DC (punto al centro del espectro)

44

La Transformada de Fourier Ejemplo: búsqueda de orientación de un texto

imagen

DFT 45

La Transformada de Fourier Ejemplo: búsqueda de orientación de un texto

imagen rotada

DFT 46

La Transformada de Fourier •

ver sitios: http://www.cs.unm.edu/~brayer/vision/fourier.html http://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm

•

ver applet: http://escher.epfl.ch/fft/

47

La Transformada Coseno •

Utiliza sólo funciones coseno.

•

Tiene la ventaja de entregar como salida una imagen real y que es una transformada rápida.

•

Se utiliza en compresión de imágenes (JPEG)

•

Después de calcular la transformada, es posible descartar los coeficientes que codifican las componentes de alta frecuencia

•

La cantidad de información puede reducirse sin afectar seriamente la forma cómo la imagen es percibida por el ojo humano.

48

Transformada del Coseno Discreta (DCT) • En la transformada del coseno discreta (DCT) los vectores base son funciones cosenos muestreadas, resultando siempre real. • La DCT muestra una alta compactación de la energía para datos altamente correlacionados, por lo que se ha convertido en una de las preferidas en cuanto a la compresión de datos de imágenes.

Transformada del Coseno Discreta (DCT) • • • •

La transformada del coseno es real y ortogonal. En 2D las funciones base son vectores. En 3D las funciones base son matrices. Debido a la ortogonalidad de las funciones base, el producto de cualquiera de estos dos vectores (o matrices), sumados a lo largo de todos los puntos de muestreo, produce un resultado nulo.

Transformada del Coseno Discreta (DCT) La DCT unidimensional se define de la siguiente forma:

De forma análoga definimos la DCT inversa:

donde, para ambas ecuaciones:

Transformada del Coseno Discreta (DCT) • Funciones bases cosinoidales 1D

Transformada del Coseno Discreta (DCT) Podemos definir ahora la DCT bidimensional donde, f (x,y) es la imagen y C(u,v) su transformada:

para u,v = 0:N-1

para x,y = 0:N-1

Transformada del Coseno Discreta (DCT) • Ejemplos de la DCT para diferentes imágenes. En este caso se calcula DCT de la imagen completa (no de un bloque).

Transformada del Coseno Discreta (DCT) • Representación gráfica de las NxN matrices base, asumiendo que cada elemento de una matriz base corresponde a un nivel de gris Conjunto de 64 funciones base cosinusoidales bidimensionales (imágenes base) que se generaron al multiplicar un conjunto de funciones base unidimensionales (de ocho puntos) orientadas horizontalmente por un conjunto verticalmente orientado de las mismas funciones.

Transformada del Coseno Discreta (DCT) • El bloque original NxN se descompone en una combinación lineal de estas matrices: Los coeficientes de la combinación lineal son los coeficientes de la DCT.

La compresión JPEG considera sólo los coeficientes más inportantes, correspondientes a las frecuencias más bajas (arriba e izquierda).

=

X

∑

y ij⋅¿ ¿