Transformação de Imagens

ComputerVision

Transformação de Imagens

Paulo Sérgio RodriguesPEL205

ComputerVision AVISO• O assunto da aula de Hoje pode ser encontrado em

sua completude nas seguintes Bibliografia:

• Digital Image Processing, First Edition, 1993, Rafael Gonzalez e Richard Woods, Addison-Wesley, Chapter 3

• Digital Image Processing, Third Edition, 2008, Rafael Gonzalez e Richard Woods, Prentice Hall, Chpater 4

• Um Curso de Cálculo, Hamilton Guidorizzi, 1988, Livros Técnicos e Científicos, Volume 4, Capítulo 50

ComputerVision Introdução a Transformada de Fourier

ComputerVision Séries de Fourier

Chama-se série trigonométrica, uma série da forma:

)2()2cos()()cos(2 2211

0 xsenbxaxsenbxaa

1

0 )()cos(2 k

kk kxsenbkxaa

ComputerVision Séries de Fourier

1

0 )()cos(2 k

kk kxsenbkxaa

As constantes a0, ak e bk (1,2,...) são os coeficientes da sérietrigonométrica

Se essa série trigonométrica convergir, a sua soma é uma função periódica f(x) de período 2π, dado que sen(kx) e cos(kx) são funções periódicas de período 2π. De modo que:

f(x) = f(x + 2π)

ComputerVision Séries de Fourier

•Problema: para uma função periódica f(x) de período 2π, quais as condições impostas a f(x) de modo que exista uma sérietrigonométrica convergente para f(x)?

f(x)

1

0 )()cos(2

)(k

kk kxsenbkxaaxf

ComputerVision Séries de Fourier

1

0 )()cos(2

)(k

kk kxsenbkxaaxf

A série acima pode ser então integrável de –π a π.

1

0 cos2

)(k

kk dxkxsenbdxkxadxadxxf

ComputerVision Séries de Fourier

1

0 cos2

)(k

kk dxkxsenbdxkxadxadxxf

0cos

0coscos

2 00

kkxbdxkxsenbdxkxsenb

kkxsenadxkxadxkxa

adxa

kkk

kkk

0

ComputerVision Séries de Fourier

1

0 cos2

)(k

kk dxkxsenbdxkxadxadxxf

dxxfa

adxa

)(1

2

0

00

Agora só falta de determinar ak e bk !!

ComputerVision Séries de Fourier

1

0 )()cos(2

)(k

kk kxsenbkxaaxf

Multipliquemos os dois membros da equação acima por cos(nx)

1

0 cos)(cos)cos(cos2

cos)(k

kk nxkxsenbnxkxanxanxxf

ComputerVision Séries de Fourier

1

0 cos)(cos)cos(cos2

cos)(k

kk nxkxsenbnxkxanxanxxf

1

0 coscoscoscos2

cos)(k

kk dxnxkxsenbdxnxkxadxnxadxnxxf

Integrando de –π a π termo a termo ambos os membros da equação acima

ComputerVision Séries de Fourier

1

0 coscoscoscos2

cos)(k

kk dxnxkxsenbdxnxkxadxnxadxnxxf

Zknknkn

dxnxkx

, , se se 0

coscos

Lembrando que:

kk adxnxkxadxkxxf

)cos(coscos)(

dxkxxfak cos)(1

0cos)(

dxnxkxsen

0 0

ComputerVision Séries de Fourier

1

0 coscoscoscos2

cos)(k

kk dxnxkxsenbdxnxkxadxnxadxnxxf

dxkxxfak cos)(1

De maneira análoga, multiplicando a equação acima por sen(nx) aoinvés de cos(nx), chegamos a:

dxkxsenxfbk )(1

dxxfa )(1

0que se junta a:

ComputerVision Séries de Fourier

dxkxxfak cos)(1

dxkxsenxfbk )(1

dxxfa )(1

0

1

0 )()cos(2

)(k

kk kxsenbkxaaxf

ComputerVision Série de Fourier

)2sin2cos(2)(1

0 Tkxb

Tkxaaxf k

kk

Jean Baptiste Joseph Fourier (1768-1830) Paper de 1807 para o Institut de France: Joseph Louis Lagrange (1736-1813), and Pierre Simon de Laplace (1749-1827).

ComputerVision Coeficientes da Série

)2sin2cos(2)(1

0 Tkxb

Tkxaaxf k

kk

T

k kdtTkxxf

Ta

0,...3,2,1,0)2cos()(1

T

k kdtTkxxf

Tb

0,...3,2,1)2sin()(1

t

f(t)

0 T

ComputerVision

Série de Fourier com números complexos

10

2sin2cos2)(k

nk Tkxb

Tkxaaxf 2

cos

ii ee

iee ii

2sin

1

22

0)(k

Tkxi

kTkxi

k eFeFFxf

k

Tkxi

keFxf2

)(

1

2222

0)(k

Tkxi

Tkxi

kTkxi

Tkxi

k eei

beeaaxf

1

22

0)(k

Tkxi

kk

Tkxi

kk e

ibae

ibaaxf

T

Tkxi

k kdtexfT

F0

)2(,...3,2,1)(1

i1

2ii ii

1

kkkkkk ibaFibaF ,

ComputerVision Transformada de Fourier

dweuFxf uxi 2)()(

dxexfuF uxi 2)()(DIRETA

INVERSA

ComputerVision

dxexfuFxf uxj 2

1 jonde

dueuFxfuF uxj 21

Transformada de Fourier (outra notação)

ComputerVision

Introdução a Transformada de Fourier

uIuRuFuP 222

ComputerVision

Introdução a Transformada de Fourier

dxdyeyxfvuFyxf vyuxj 2,,,

dudvevuFyxfvuF vyuxj 21 ,,,

ComputerVision

Introdução a Transformada de Fourier

vuIvuRvuFvuP ,,,, 222

ComputerVision Introdução a Transformada de Fourier

vuIvuRvuFvuP ,,,, 222

ComputerVision Transformada Discreta de Fourier

xNxfxxfxxfxf 1,,2,, 0000

1

0

/21 N

x

NujexfN

uF

1

0

/2N

u

NujeuFxf

ComputerVision Transformada Discreta de Fourier

xNxfxxfxxfxf 1,,2,, 0000

1

0

1

0

//2,1,M

x

N

y

NvyMuxjeyxfMN

vuF

1

0

1

0

//2,,M

u

N

v

NvyMuxjevuFyxf

ComputerVision

Resultados daTransformada de Fourier

ComputerVision Exemplo 1: Função caixa (box)

f(x)

x

]2,202[20

)( bbxsebxseabxse

xf

a

dxexfwF wxi 2)()(

2/2/

2

2b

bwxie

wia

2/

2/

2b

b

wxi dxea

wbiwbi eewi

a

2

iee

wa wbiwbi

2

)sin( wb

wa

b

wbwbabwF

)sin()(

ComputerVision Transformada da função box

bwbwabwF

)sin()(

F(w)

0 1/b 2/b 3/b-1/b-2/b-3/b

abw

wbwbabwF

)sin()(

f(x)

x

a

b

ComputerVision Distribuição normal: Gaussiana

2

2

22

1)(

x

exGaus

ComputerVision Exemplo 2: Gaussiana

-0,02

0,03

0,08

0,13

0,18

-0,02

0,03

0,08

0,13

0,18

2

2

2

21)(

x

exf

2

2

12)(

w

ewF

f(x)

x

|| F(w) ||

w 1

ComputerVision

Exemplos

Considere a função mostrada abaixo:

f(x)

2f(x0)

f(x0 + dx)

f(x0 + 2dx) f(x0 +3 dx)

x

3

4

0.5 0.75 1.0 1.25 x

f(x)=f(x + dx)

2

3

4

0.5 0.75 1.0 1.25

ComputerVision Exemplos

1

0

/2)(1)(N

x

NuxjexfN

uF

f(x) = [2, 3, 4, 4]

25.3)0(

25.3)4432(41)]3()2()1()0([

41

)(41)(

41)0(

3

0

03

0

02

F

ffff

exfexfFxx

j

ComputerVision Exemplos

1

0

/2)(1)(N

x

NuxjexfN

uF

f(x) = [2, 3, 4, 4]

)2(41)1(

)2(41]4432[

41

)(41)1(

2/32/0

3

0

4/2

jF

jeeee

exfF

jjj

x

xj

ComputerVision Exemplos

1

0

/2)(1)(N

x

NuxjexfN

uF

f(x) = [2, 3, 4, 4]

)2(41)3(

)01(41)2(

)2(41)1(

25.3)0(

jF

jF

jF

F

ComputerVision Exemplos

F(u) = [3.25, -0.5+j0.25, -0.25, -0.5-0.25j]

45

41

42)3(

41

40

41)2(

45

41

42)1(

25.3)0(

2/122

2/122

2/122

F

F

F

F

ComputerVision

Algumas Propriedades Importantes da Transformada de Fourier

Paulo Sérgio RodriguesPEL205

ComputerVision Separabilidade

• Lembrando o par de Transformadas de Fourier

1

0

1

0

//2,1,M

x

N

y

NvyMuxjeyxfMN

vuF

1

0

1

0

//2,,M

u

N

v

NvyMuxjevuFyxf

ComputerVision Separabilidade

• Ou, considerando M = N para simplificar ainda mais:

1

0

1

0

/)(2,1,N

x

N

y

NvyuxjeyxfN

vuF

1

0

1

0

/)(2,,N

u

N

v

NvyuxjevuFyxf

ComputerVision Separabilidade

• Expandindo e arrumando:

1

0

1

0

/2/2,1,N

x

N

y

NvyjNuxj eeyxfN

vuF

1

0

1

0

/)(2,1,N

x

N

y

NvyuxjeyxfN

vuF

1

0

1

0

/2/2 ,1,N

x

N

y

NvyjNuxj eyxfeN

vuF

ComputerVision Separabilidade

• Da mesma forma, para a transformada inversa:

1

0

1

0

/2/2 ,1,N

x

N

y

NvyjNuxj eyxfeN

vuF

1

0

1

0

/2/2 ,1,N

u

N

v

NvyjNuxj evuFeN

yxf

ComputerVision Separabilidade

• Pode-se ver cada parte como uma transformada 1D

1

0

1

0

/2/2 ,1,N

x

N

y

NvyjNuxj eyxfeN

vuF

1

0

/2),(1),(N

y

NvyjeyxfN

NvxF

ComputerVision Separabilidade

• Pode-se ver cada parte como uma transformada 1D

1

0

/2),(1),(N

y

NvyjeyxfN

NvxF

1

0

/2),(1),(N

x

NuxjevxFN

vuF

ComputerVision Translação

Um “problema” para visualizar o espectro de Fourier deUma função f(x,y) é o fato do pico mais alto ocorrer no eixo x = 0

ComputerVision Translação

No caso de uma imagem f(x,y), a qualidade da visualizaçãoPode ficar comprometida

f(x,y) |F(u,v)|

ComputerVision Translação

),(),( 00/2 00 vvuuFeyxf Nyvxuj

No entanto, pode-se provar que, para constantes u0, v0, x0, y0:

NvyuxjevuFyyxxf /200

00),(),(

e

ComputerVision Translação

(1) /

222

/2 00 yxjNyNxNj

Nyvxuj eee

)2( 1 cos como jjy esenyjye

Mas, quando M = N e u0 = v0 = N/2 :

Substituindo (2) em (1), concluímos que:

yxNyvxuje )1(/)(2 00

ComputerVision Translação

),(),( 002 00 vvuuFeyxf yvxuj

Finalmente, baseado nos resultados dos slides 10 e 11:

)2/,2/()1)(,( NvNuFyxf yx

Conclusão: Para se deslocar o espectro de Fourier para o centro do sistema de coordenadas, basta multiplicar cada ponto (x,y) de sua inversa por -1 elevado a soma x + y

2/ se 00 Nvu

ComputerVision Translação

No caso de uma imagem f(x,y), a qualidade da visualizaçãoé claramente melhor

f(x,y)|F(u,v)| sem Shift

yxf ,

|F(u,v)| com Shift yxyxf )1(,

ComputerVision Periodicidade e Simetria Conjugada

),(),(),(),( NvNuFNvuFvNuFvuF

A transformada de Fourier é periódica de período N; isto é:

1

0

1

0

/2),(1),(

em e de direta ãosubstituiç de através provadoser pode isso

N

x

N

y

NvyuxjeyxfN

vuF

NvNu

ComputerVision Rotação

senvursenyrx cos cos

),( e ),( : tornamse ),( e ),( FrfvuFyxf

Se introduzirmos coordenadas polares:

Substituindo diretamente em f(x,y) e F(u,v), temos:

),(),( 00 Frf

ComputerVision Rotação

Exemplo de Rotação

ComputerVision Distributividade

),(),(),(),( 2121 yxfyxfyxfyxf

Uma vez que:

A transformada de Fourier é DISTRIBUTIVA sobre ADIÇÃO

Mas ...

),(),(),(),( 2121 yxfyxfyxfyxf

A transformada de Fourier NÃO é DISTRIBUTIVA sobre MULTIPLICAÇÃO

ComputerVision Escala

Para dois escalares a e b

vuaFyxaf ,,

bvauFab

byaxf /,/1

ComputerVision Valor Médio

1

0

1

0

1 ,, 2

N

x

N

yN

yxfyxf

1

0

1

0

/2,1,

em 0 fazendoN

x

N

y

NvyuxjeyxfN

vuF

vu

1

0

1

0

,10,0N

x

N

y

yxfN

F

ComputerVision Valor Médio

0,01, FN

yxf

1

0

1

0

,10,0N

x

N

y

yxfN

F

1

0

1

0

1 ,, 2

N

x

N

yN

yxfyxf

ComputerVision Transformada do Delta de Dirac

f(x)

x

1)()( 02

edxexwF wxi (x)

|| F(w) ||

w

1

ComputerVision Pares importantes

ComputerVision Propriedades da transformada

ComputerVision

Ainda há muita Teoria pra falar sobre a Transformada de Fourier!

Mas já dá para brincar com imagens utilizando o com o MatLab!

ComputerVision Filtragem no Domínio da Frequência

ComputerVision Filtragem no Domínio da Frequência

ComputerVision Filtragem no Domínio da Frequência

ComputerVision Filtragem no Domínio da Frequência

ComputerVision

Resultado F(0,0) = 0

Filtragem no Domínio da Frequência

ComputerVision Filtragem no Domínio da Frequência com uma função Gaussiana

Passa-Baixa

Passa-Alta

ComputerVision Filtragem no Domínio da Frequência com uma função Gaussiana

ComputerVision

Filtragem no Domínio da Frequência com Ideal Lowpass Filter (ILPF)

ComputerVision

Filtragem no Domínio da Frequência com Ideal Lowpass Filter (ILPF)

ComputerVision

Filtragem no Domínio da Frequência com Ideal Lowpass Filter (ILPF)

ComputerVision

Filtragem no Domínio da Frequência com Butterworh Lowpass Filter (BLPF)

ComputerVision

Filtragem no Domínio da Frequência com Butterworh Lowpass Filter (BLPF)

ComputerVision

ILPF BLPF

ComputerVision

Filtragem no Domínio da Frequência com Butterworh Lowpass Filter (BLPF)

ComputerVision

Chapter 4

Image Enhancement in the

Frequency Domain

Filtragem no Domínio da Frequência com Gaussian Lowpass Filter (BLPF)

ComputerVision

Filtragem no Domínio da Frequência com Gaussian Lowpass Filter (BLPF)

ComputerVision

Filtragem no Domínio da Frequência: Comparação Gaussian-Butterworth Lowpass Filters

ComputerVision

Filtragem no Domínio da Frequência com Gaussian Lowpass Filter (GLPF)

ComputerVision

Filtragem no Domínio da Frequência com Gaussian Lowpass Filter (GLPF)

ComputerVision

Filtragem no Domínio da Frequência com Gaussian Lowpass Filter (GLPF)

ComputerVision

Filtragem no Domínio da Frequência

ComputerVision

Filtragem no Domínio da Frequência: Highpass Filters

ComputerVision

Filtragem no Domínio da Frequência: IHPF

ComputerVision

Filtragem no Domínio da Frequência: BHPF

ComputerVision

Filtragem no Domínio da Frequência: GHPF

ComputerVision

IDEAL

BUTTERWORTH

GAUSSIAN

ComputerVision Filtragem no Domínio da Frequência

ComputerVision

Compressão JPEG

Paulo Sérgio RodriguesPEL205

ComputerVision Compressão JPEG

JPEG é o anacrônico para Joint Photographic Experts Group

Baseia-se nos seguintes passos:

Subdivisão da Imagem em blocos de 8 x 8 pixels

Quantização com a matriz de normalizaçãoDa JPEG

Cálculo de DCT

Codificação baseadano tamanho das variáveis

Compressão

Decodificação baseadano tamanho das variáveis

Desquantização com a matriz de normalizaçãoDa JPEG

Cálculo DCT Inversa

Composição da Imagem usando os em blocos de 8 x 8 pixels Descompressão

ComputerVision

Transformada Discreta de Cosseno

1212 0

)(

2)12(cos

2)12(cos)()(),(),(

2)12(cos

2)12(cos)()(),(),(

1

1

0

1

0

1

0

1

0

,...,n-, for u n

for u u

nvy

nuxvuvuTyxg

nvy

nuxvuyxgvuT

n

n

x

n

y

n

x

n

y

ComputerVision Compressão JPEG

Compressão: Passo 1, subdivisão da Imagem em Blocos de 8 x 8 pixels

8 x 8 8 x 8 8 x 8 8 x 8

8 x 8 8 x 8 8 x 8 8 x 8

8 x 8 8 x 8 8 x 8 8 x 8

ComputerVision Compressão JPEG

Compressão: Passo 2, Cálculo da DCT em cada Bloco

Exemplo de Bloco 8 x 8

55 52 61 66 70 61 64 7363 59 66 90 109 85 69 7262 59 68 113 144 104 66 7363 58 71 122 154 106 70 6967 61 68 104 126 88 68 7079 65 60 70 77 68 58 7585 71 64 59 55 61 65 8387 79 69 68 65 76 78 94

ComputerVision Compressão JPEG

Compressão: Passo 2, Cálculo da DCT em cada Bloco

Shift de -128

-76 -73 -67 -62 -58 -67 -64 -55-65 -69 -62 -38 -19 -43 -59 -56-66 -69 -60 -15 16 -24 -62 -55-65 -70 -57 -6 26 -22 -58 -59-61 -67 -60 -24 -2 -40 -60 -58-49 -63 -68 -58 -51 -65 -70 -53-43 -57 -64 -69 -73 -67 -63 -45-41 -49 -59 -60 -63 -52 -50 -34

ComputerVision Compressão JPEG

Compressão: Passo 2, Cálculo da DCT em cada Bloco

-415 -29 -62 25 55 -20 -1 3

7 -21 -62 9 11 -7 -6 6

-46 8 77 -25 -30 10 7 -5

-50 13 35 -15 -9 6 0 3

11 -8 -13 -2 -1 1 -4 1

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

-4 -1 2 -1 2 -3 1 -2

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

ComputerVision Compressão JPEG

Compressão: Passo 3, Quantização

Matriz de Normalização JPEG

ComputerVision Compressão JPEG

Compressão: Passo 3, Quantização

Suponha que um coeficiente DCT encontrado seja: T(0,0) = -415,

De acordo com a matriz de quantização JPEG, o valor correspondenteé Z(0,0) = 16.

Sendo assim, o cálculo do novo valor, quantizado, será:

2616415

)0,0()0,0(0,0ˆ

round

ZTroundT

ComputerVision Compressão JPEG

Compressão: Passo 3, Quantização

O principal resultado da quantização é a geração de uma matriz esparssa

-26 -3 -6 2 2 0 0 0

1 -2 -4 0 0 0 0 0

-3 1 5 -1 0 0 0 0

-4 1 2 -1 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

ComputerVision Compressão JPEG

Compressão: Passo 3, Quantização

O que permite algum tipo de codificação eficiente:

-26 -3 -6 2 2 0 0 0

1 -2 -4 0 0 0 0 0

-3 1 5 -1 0 0 0 0

-4 1 2 -1 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

[-26 -3 1 -3 -2 -6 2 -4 1 -4 1 1 5 0 2 0 -1 2 0 0 0 0 -1 -1 EOB]

Mais de 60% deCompressão no Bloco

ComputerVision Descompressão JPEG

Compressão: Passo 1, Descodificação

-26 -3 -6 2 2 0 0 0

1 -2 -4 0 0 0 0 0

-3 1 5 -1 0 0 0 0

-4 1 2 -1 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

[-26 -3 1 -3 -2 -6 2 -4 1 -4 1 1 5 0 2 0 -1 2 0 0 0 0 -1 -1 EOB]

ComputerVision Descompressão JPEG

Compressão: Passo 2, Desquantização

-416 -33 -60 32 48 0 0 0

12 -24 -56 0 0 0 0 0

-42 13 80 -24 -40 0 0 0

-56 17 44 -29 0 0 0 0

18 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

A desquantização pode ser obtida pela inversa:

416)16)(26()0,0()0,0(ˆ)0,0( ZTT

ComputerVision Descompressão JPEG

Compressão: Passo 3, cálculo da DCT Infersa

-70 -64 -61 -64 -69 -66 -58 -50

-72 -73 -61 -39 -30 -40 -54 -59

-68 -78 -58 -9 13 -12 -48 -64

-59 -77 -57 0 22 -13 -51 -60

-54 -75 -64 -23 -13 -44 -63 -56

-52 -71 -72 -54 -54 -71 -71 -54

-45 -59 -70 -68 -67 -67 -61 -50

-35 -47 -61 -66 -60 -48 -44 -44

ComputerVision Descompressão JPEG

Compressão: Passo 4, Shifting de 128

58 64 67 64 59 62 70 78

56 55 67 89 98 88 74 69

60 50 70 119 141 116 80 64

69 51 71 128 149 115 77 68

74 53 64 105 115 84 65 72

76 57 56 74 75 57 57 74

83 69 59 60 61 61 67 78

93 81 67 62 69 80 84 84

ComputerVision Descompressão JPEG

Diferença entre a Imagem (Bloco) original e o descomprimido

-6 -9 -6 2 11 -1 -6 -5

7 4 -1 1 11 -3 -5 3

2 9 -2 -6 -3 -12 -14 9

-6 7 0 -4 -5 -9 -7 1

-7 8 4 -1 11 4 3 -2

3 8 4 -4 2 11 1 1

2 2 5 -1 -6 0 -2 5

-6 -2 2 6 -4 -4 -6 10

< 1% de erro