223
Introdução ao Processamento Digital de Imagens José Raphael Teixeira Marques DI/PPGI [email protected] raphaelmarques.wordpress.com Prof. Leonardo Vidal Batista DI/PPGI/PPGEM [email protected] [email protected] http://www.di.ufpb.br/leonardo

Slides PDI 2009 Raphael versao4

Embed Size (px)

Citation preview

Page 1: Slides PDI 2009 Raphael versao4

Introdução ao Processamento Digital de

Imagens

José Raphael Teixeira Marques – DI/PPGI

[email protected]

raphaelmarques.wordpress.com

Prof. Leonardo Vidal Batista

DI/PPGI/PPGEM

[email protected] [email protected]

http://www.di.ufpb.br/leonardo

Page 2: Slides PDI 2009 Raphael versao4

Filtros de suavização

Média, Moda, Mediana, Gaussiano...

Vizinhança m x n

Page 3: Slides PDI 2009 Raphael versao4

Filtros de aguçamento e

detecção de bordas

Efeito contrário ao de suavização: acentuam variações de intensidade entre pixels adjacentes.

Baseados no gradiente de funções bidimensionais.

Gradiente de f(x, y):

G[f(x, y)] =

y

f

x

f

2/1

22

)],([

y

f

x

fyxfG

Page 4: Slides PDI 2009 Raphael versao4

Filtros de detecção de bordas

g(i, j): aproximação discreta do módulo dovetor gradiente em f(i, j).

Aproximações usuais:

g(i, j) = {[f(i,j)-f(i+1,j)]2 + [f(i,j)-f(i,j+1)]2}1/2

g(i, j) = |f(i,j)-f(i+1,j)| + |f(i,j)-f(i,j+1)|

Gradiente de Roberts:

g(i,j) = {[f(i,j)-f(i+1,j+1)]2+[f(i+1,j)-f(i,j+1)]2}1/2

g(i, j) = |f(i,j)-f(i+1,j+1)| + |f(i+1,j)-f(i,j+1)|

Page 5: Slides PDI 2009 Raphael versao4

Filtros de detecção de bordas

Aproximações usuais:

Gradiente de Roberts:

Page 6: Slides PDI 2009 Raphael versao4

Filtros de detecção de bordas

Gradiente de Prewitt:

g(i, j) = |f(i+1,j-1) + f(i+1, j) + f(i+1, j+1)

- f(i-1, j-1) - f(i-1, j) - f(i-1, j+1)|

+|f(i-1, j+1) + f(i, j+1) + f(i+1, j+1)

- f(i-1, j-1) - f(i, j-1) - f(i+1, j-1)|

Gradiente de Sobel:

g(i, j) = |f(i+1, j-1) + 2f(i+1, j) + f(i+1, j+1)

- f(i-1, j-1) - 2f(i-1, j) - f(i-1, j+1)|

+ |f(i-1,j+1) + 2f(i,j+1) + f(i+1, j+1)

- f(i-1, j-1) - 2f(i, j-1) - f(i+1, j-1)|

Page 7: Slides PDI 2009 Raphael versao4

Filtros de detecção de bordas

Gradiente de Prewitt:

Gradiente de Sobel:

Page 8: Slides PDI 2009 Raphael versao4

Gradiente de Roberts

Limiares 15, 30 e 60

Page 9: Slides PDI 2009 Raphael versao4

Processamento de Histograma

Se o nível de cinza l ocorre nl vezes emimagem com n pixels, então

n

nlP l)(

Histograma da imagem é umarepresentação gráfica de nl ou P(l)

Page 10: Slides PDI 2009 Raphael versao4

Histograma

3 3

Histograma

Imagem

l

nl

7

6

5

4

3

2

1

0

3 2 1 0

0 0 1

3 3 3 0 0

3 3 1 1 1

Imagem 3 x 5 (L = 4) e seu histograma

Page 11: Slides PDI 2009 Raphael versao4

Histograma

O histograma representa a distribuição

estatística de níveis de cinza de uma imagem

l

nl

255 0

l

nl

255 0

l

nl

255 0

Page 12: Slides PDI 2009 Raphael versao4

Histograma

0 50 100 150 200 250

0

2000

4000

6000

8000

10000

Page 13: Slides PDI 2009 Raphael versao4

Histograma

0 50 100 150 200 250

0

500

1000

1500

Page 14: Slides PDI 2009 Raphael versao4

Expansão de Histograma

Quando uma faixa reduzida de níveis de cinza é utilizada, a expansão de histograma pode produzir uma imagem mais rica.

l

nl

L-1 m0=0 l

nl

L-1 0 l

nl

m1=L-1 0 m0 m1

A B C

m1 m0

Page 15: Slides PDI 2009 Raphael versao4

Expansão de Histograma

Quando uma faixa reduzida de níveis de cinza é utilizada, a expansão de histograma pode produzir uma imagem

mais rica:

)1()(

minmax

min Lrr

rrroundrTs

Page 16: Slides PDI 2009 Raphael versao4

Expansão de Histograma

0 50 100 150 200 250

0

500

1000

1500

0 50 100 150 200 250

0

500

1000

1500

Page 17: Slides PDI 2009 Raphael versao4

Expansão de Histograma

Expansão é ineficaz nos seguintes casos:

l

nl

L-1 0 l

nl

L-1 0 l

nl

L-1 0 m0 m1

A B C

L-1

Page 18: Slides PDI 2009 Raphael versao4

Equalização de Histograma

Se a imagem apresenta pixels de valor 0 e L-1 (ou próximos a esses extremos) a expansão de histograma é ineficaz.

Nestas situações a equalização de histograma pode produzir bons resultados.

O objetivo da equalização de histograma é gerar uma imagem com uma distribuição de níveis de cinza uniforme.

Page 19: Slides PDI 2009 Raphael versao4

Equalização de Histograma

r

lln

RC

LroundrTs

0

1)(

0 50 100 150 200 250

0

500

1000

1500

0 50 100 150 200 250

0

500

1000

1500

Page 20: Slides PDI 2009 Raphael versao4

Equalização de Histograma

Exemplo: imagem 64 x 64, L = 8

l nl

0 790

1 1023

2 850

3 656

4 329

5 245

6 122

7 81

l

nl

1200

1000

800

600

400

200

0

7 6 5 4 3 2 1 0

Page 21: Slides PDI 2009 Raphael versao4

Equalização de Histograma

Exemplo (cont.):

r = 0 s = round(790 x 7 / 4096) = 1

r = 1 s = round(1813 x 7 / 4096) = 3

r = 2 s = round(2663 x 7 / 4096) = 5

r = 3 s = round(3319 x 7 / 4096) = 6

r = 4 s = round(3648 x 7 / 4096) = 6

r = 5 s = round(3893 x 7 / 4096) = 7

r = 6 s = round(4015 x 7 / 4096) = 7

r = 7 s = round(4096 x 7 / 4096) = 7

Page 22: Slides PDI 2009 Raphael versao4

Equalização de Histograma

Exemplo: imagem 64 x 64, L = 8

l nl

0 0

1 790

2 0

3 1023

4 0

5 850

6 985

7 448

k

nk

1200

1000

800

600

400

200

0

7 6 5 4 3 2 1 0

Page 23: Slides PDI 2009 Raphael versao4

Equalização de Histograma

l

nl

L-1 0 l

nl

L-1 0 l

nl

L-1 0 m0 m1

Hist. Original Hist. Equal. (Ideal)

L-1

Hist. Equal. (Real)

Page 24: Slides PDI 2009 Raphael versao4

Equalização de Histograma

Expansão de histograma é pontual ou local? E equalização de histograma?

O que ocorre quando uma imagem com um único nível passa pela operação de equalização de histograma?

Melhor fazer equalização seguido por expansão de histograma, o inverso, ou a ordem não importa?

Page 25: Slides PDI 2009 Raphael versao4

Equalização de Histograma Local

Para cada posição (i,j) de f

• Calcular histograma na vizinhança de (i,j)

• Calcular s = T(r) para equalização de histograma na vizinhança

• G(i,j) = s

Page 26: Slides PDI 2009 Raphael versao4

Controle de contraste adaptativo

0),();,(

0),()];,(),([),(

),(),(

jijif

jijijifji

cji

jig

)( ponto do visinhança

na padrão desvio),(

i,jji

)( ponto do visinhança

na média),(

i,jji

Page 27: Slides PDI 2009 Raphael versao4

Controle de contraste adaptativo

Original c < σ c > σ

Page 28: Slides PDI 2009 Raphael versao4

Pseudo-cor

Nível de cinza

R G B

0 15 20 30

1 15 25 40

...

L-1 200 0 0

Page 29: Slides PDI 2009 Raphael versao4

Pseudo-cor

Page 30: Slides PDI 2009 Raphael versao4

Pseudo-cor

Page 31: Slides PDI 2009 Raphael versao4

Outros filtros:

Curtose, máximo, mínimo etc.

Filtros de suavização + filtros de aguçamento

Laplaciano do Gaussiano (LoG)

“Emboss”

Aumento de saturação

Correção de gama

...

Page 32: Slides PDI 2009 Raphael versao4

Filtros Lineares e Invariantes ao Deslocamento

Filtro linear:

T [af1 + bf2] = aT [f1] + bT [f2]

para constantes arbitrárias a e b.

Filtro invariante ao deslocamento:

Se g[i, j] = T [f[i, j]]

então g[i - a, j – b] = T [f[i - a, j – b]].

Se i e j são coordenadas espaciais: filtros espacialmente invariantes.

Page 34: Slides PDI 2009 Raphael versao4

Dissolve Cruzado

t = 0,3 t = 0,5 t = 0,7

Page 35: Slides PDI 2009 Raphael versao4

Dissolve Cruzado Não-Uniforme

ht(i, j)= [1 - t(i, j)] f(i, j) + t(i, j) g(i, j)

t é uma matriz com as mesmasdimensões de f e g cujos elementosassumem valores no intervalo [0, 1]

Page 36: Slides PDI 2009 Raphael versao4

Dissolve Cruzado Não-Uniforme

t(i,j)=(i+j)/(R+C-2) t(i,j)=j/(C-1) t(i,j)=i/(R-1)

Page 37: Slides PDI 2009 Raphael versao4

Detecção de Movimento

contrario caso ,0

|| se ,1 21 tLffLg

f1 f2 g

Page 38: Slides PDI 2009 Raphael versao4

Detecção de Movimento

Page 39: Slides PDI 2009 Raphael versao4

Redução de Ruído por Média de Imagens

f[i, j] imagem sem ruído

nk(i, j) ruído de média m

gk[i,j] = f[i,j] + nk(i,j)

M

k

k jigM

jig

1

],[1

],[

Page 40: Slides PDI 2009 Raphael versao4

Redução de Ruído por Média de Imagens

)),(],[(1

],[

1

jinjifM

jig k

M

k

M

k

k jinM

jifjig

1

),(1

],[],[

mjifjig ],[],[

Para M grande:

Page 41: Slides PDI 2009 Raphael versao4

Operações Topológicas

Rígidas

Translação

Rebatimento

Rotação

Mudança de Escala

Não rígidas (Warping)

Page 42: Slides PDI 2009 Raphael versao4

Rotação

Rotação em torno de (ic, jc)

http://jose.raphael.marques.googlepages.com/PDI_Rotation.jnlp

ccc

ccc

jjjiij

ijjiii

cos)(sen)('

sen)(cos)('

Page 43: Slides PDI 2009 Raphael versao4

Rotação e Rebatimento

Imagem original Rebatimento pela diagonal

Rotação de 90 graus em torno de (R/2,C/2)

Page 44: Slides PDI 2009 Raphael versao4

Ampliação (Zoom in)

10 10

20 30

10 10 10 10 10 10

10 10 10 10 10 10

10 10 10 10 10 10

20 20 20 30 30 30

20 20 20 30 30 30

20 20 20 30 30 30

Por replicação de pixels

Original Ampliação por fator 3

Page 45: Slides PDI 2009 Raphael versao4

Ampliação (Zoom in)

10 10

20 30

10 10 10 10 10 10

20 22 24 26 28 30

Por interpolação bilinear

Original Ampliação por fator 3

Interpolação nas linhas

Passos de níveis de cinza:

10 a 10: 0

20 a 30: (30-20)/5 = 2

Page 46: Slides PDI 2009 Raphael versao4

Ampliação (Zoom in)

10 10

20 30

10 10 10 10 10 10

12 12 13 13 14 14

14 15 16 16 17 18

16 17 18 20 21 22

18 20 21 23 24 26

20 22 24 26 28 30

Por interpolação bilinear

Original Ampliação por fator 3

Interpolação nas colunas

Passos de níveis de cinza:

10 a 20: (20-10)/5 = 2

10 a 22: (22-10)/5 = 2.4

...

10 a 30: (30-10)/5 = 4

Page 47: Slides PDI 2009 Raphael versao4

Ampliação (Zoom in)

Por interpolação bilinear

passos:

12/5 = 2.4

12/9 = 1.333... (dízima)

}..0{, nin

ix

n

nixx

ban

bai

Page 48: Slides PDI 2009 Raphael versao4

Ampliação (Zoom in)

Exemplo: Ampliação por fator 10

Original Replicação Interpolação

Page 49: Slides PDI 2009 Raphael versao4

Redução (Zoom out)

14 18

28 41

10 10 10 10 10 10

13 14 16 17 18 19

17 19 21 23 25 28

20 23 27 30 33 37

23 27 33 37 41 46

27 32 38 43 48 55

Por eliminação de pixel

Por Média

Original Redução por média por fator 3

Page 50: Slides PDI 2009 Raphael versao4

Reconstrução de Imagens

Zoom por fatores não inteiros

Ex: F = 3,75432

Operações elásticas, etc.

Técnicas mais avançadas devem ser utilizadas

Uma dessas técnicas é a reconstrução de imagens

Page 51: Slides PDI 2009 Raphael versao4

Reconstrução de imagens

Dados f(i,j), f(i,j+1), f(i+1,j), f(i+1,j+1)

(i, j)

(x,y)

(i, j+1)

(i+1, j) (i+1, j+1)

(i, y)

(i+1, y)

Reconstrução:

Encontrar f(x,y),

x em [i, i+1]

y em [j, j+1]

Page 52: Slides PDI 2009 Raphael versao4

Reconstrução de imagens por interpolação bilinear

(i, j)

(x,y)

(i, j+1)

(i+1, j) (i+1, j+1)

(i, y)

(i+1, y)

f(i, y) = f(i, j)+(y–j)[f(i, j+1)-f(i, j)]

f(i+1,y)=f(i+1,j)+(y–j)[f(i+1,j+1)-f(i+1, j)]

f(x, y) = f(i, y) + (x – i) [f(i+1, y) - f(i, y)]

Page 53: Slides PDI 2009 Raphael versao4

Reconstrução de imagens

Ex: f(10.5, 15.2)=?

f(10, 15) = 10

f(10, 16) = 20

f(11,15) = 30

f(11, 16) = 30

Page 54: Slides PDI 2009 Raphael versao4

Reconstrução de imagens

Solução:

x = 10.5; y = 15.2 => i = 10; j = 15

f(i, y) = f(i, j)+(y–j)[f(i, j+1)-f(i, j)]

f(10, 15.2)=f(10,15)+(15.2-15)*[f(10,16)-f(10,15) = 10 + 0.2*[20 – 10] = 12

f(i+1,y)=f(i+1,j)+(y–j)[f(i+1,j+1)-f(i+1, j)]

f(11, 15.2)=f(11,15)+(15.2-15)*[f(11,16)-f(11,15) =30 + 0.2*[30 – 30] = 30

f(x, y) = f(i, y) + (x–i) [f(i+1, y) - f(i, y)]

f(10.5, 15.2)=12+(10.5-10)*[30-12] =21

Page 55: Slides PDI 2009 Raphael versao4

Zoom por reconstrução de imagens

Ex: Ampliação por fator 2.3

Passo para as coordenadas: 1/2.3 = 0.43

x = 0, 0.43, 0. 87, 1.30, 1.74, 2.17, 2.61, 3.04...y = 0, 0.43, 0. 87, 1.30, 1.74, 2.17, 2.61, 3.04... g(0,0) = f(0,0); g(0,1) = f(0, 0.43);g(0,2) = f(0, 0.87); g(0,3) = f(0, 1.30);...

Ex: Redução por fator 2.3

x = 0, 2.3, 4.6, 6.9, 9.2, 11.5, 13.8...y = 0, 2.3, 4.6, 6.9, 9.2, 11.5, 13.8...g(0,0) = f(0,0); g(0,1) = f(0, 2.3);g(0,2) = f(0, 4.6); g(0,3) = f(0,6.9);...

Page 56: Slides PDI 2009 Raphael versao4

Operações Topológicas Não Rígidas (warping)

Warping = distorção

Zoom por fator F(i, j)

Rotação por ângulo teta(i,j)

Translação com deslocamento d(i,j)

Warping especificado pelo usuário

Page 57: Slides PDI 2009 Raphael versao4

Warping (Deformação)

Page 58: Slides PDI 2009 Raphael versao4

Warping (Deformação)

Page 59: Slides PDI 2009 Raphael versao4

Warping (Deformação)

Page 60: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Entretenimento

Efeitos especiais, morphing

Correção de distorções óticas

Alinhamento de elementos correspondentes em duas ou mais imagens (registro)

Modelagem e visualização de deformações físicas

Page 61: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

1. Características importantes da imagem são marcados por segmentos de reta orientados (vetores de referência)

2. Para cada vetor de referência, um vetor alvo é especificado, indicando a transformação que se pretende realizar

Page 62: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

3. Para cada par de vetores referência-alvo, encontra-se o ponto X’ para onde um ponto X da imagem deve migrar, de forma que as relações espaciais entre X’ e o vetor alvo sejam idênticas àquelas entre X e o vetor de referência

4. Parâmetros para as relações espaciais : u e v

Page 63: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Page 64: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

u: representa o deslocamento normalizado de P até O no sentido do vetor PQ (Normalizado: dividido pelo módulo de PQ)

|v|: distância de Xà reta suporte de PQ

Page 65: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Se O=P, u = 0

Se O=Q, u = 1

Se O entre P eQ, 0<u<1;

Se O após Q, u>1

Se O antes de P, u<0

Page 67: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Encontrar u e v: norma, produto interno, vetores perpendiculares, projeção de um vetor sobre outro.

Vetores a = (x1, y1) e b = (x2, y2)

Norma de a:

Produto interno:

a.b = x1x2 +y1y2

2

1

2

1|||| yx a

Page 68: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

“Norma” da projeção de a sobre b (o sinal indica o sentido em relação a b)

a

b

c

||||||||

b

a.b c

Page 69: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Vetor b = (x2, y2) perpendicular a a = (x1, y1) e de norma igual à de a:

ab

Perpendicularidade: x1x2 +y1y2 = 0

Mesma norma: x22 + y2

2 = x12 + y1

2

Page 70: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Soluções:

x2 = y1, y2 = -x1

x2 = -y1, y2 = x1

ab

b’

Page 71: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Parâmetro u: “norma” da projeção de PXsobre PQ, dividido pela norma de PQ

2|||| PQ

PQPXu

.

Page 72: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

P = (xp,yp), Q = (xq, yq), X = (x,y)

2|||| PQ

PQPXu

.

u = (x - xp).(xq - xp) + (y -yp)(yq – yp)

(xq-xp)2 + (yq-yp)

2

Page 73: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Parâmetro v: distância de X à reta suporte de PQ

|||| PQ

PQPXv

.

v: vetor perpendicular a v e de mesma norma que este.

Page 74: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

PQ = (Xq-Xp, Yq-Yp)

PQ1 = (Yq–Yp, Xp-Xq)

PQ2 = (Yp–Yq, Xq-Xp)

Vamos usar PQ1

P

Q

Page 75: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Parâmetro v:

|||| PQ

PQPXv

.

v = (x-xp)(yq-yp) + (y-yp)(xp–xq)

[(xq-xp)2 + (yq-yp)

2]1/2

Page 76: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Cálculo de X’:

||''||

''''.''

QP

QPvQPuPX

.

Page 77: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

2|||| PQ

PQPXu

.

||''||

''''.''

QP

QPvQPuPX

.

|||| PQ

PQPXv

.

Page 78: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Quando há mais de um par de vetores referência-alvo, cada pixel sofre a influência de todos os pares de vetores

Será encontrado um ponto Xi’ diferente para cada par de vetores referência-alvo.

Os diferentes pontos para os quais o ponto X da imagem original seria levado por cada par de vetores referência-alvo são combinados por intermédio de uma média ponderada, produzindo o ponto X’ para onde X será efetivamente levado.

Page 79: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Page 81: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Peso da coordenada definida pelo i-ésimo par de vetores de referência-alvo:

di: Distância entre X e o segmento PiQi

li: ||Pi Qi||a, b e p : Parâmetros não negativos

Page 82: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Relação inversa com a distância entre a reta e o ponto X

Parâmetro a : Aderência ao segmento

a = 0 (Peso infinito ou aderência máxima)

Page 83: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Parâmetro p controla a importância do tamanho do segmento

p = 0: independe do tamanho do segmento

Page 84: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Parâmetro b controla a forma como a influência decresce em função da distância

b = 0: peso independe da distância

Page 85: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Bons resultados são obtidos com:

a entre 0 e 1

b = 2

p = 0 ou p = 1.

Page 86: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Exemplo:

P0 = (40, 10); Q0 = (20, 5) P0’ = (35, 15); Q0’ = (25, 20)P1 = (20, 30); Q1 = (10, 35)P1’ = (25, 50); Q1’ = (5, 40)X = (20, 25)u0 = [(20-40) (20-40) + (25-

10)(5-10)] / [(20-40)2+ (5-10)2] = 0.76

v0 = [(20-40) (5-10) + (25-10)(40-20)] / [(20-40)2+ (5-10)2]1/2 = 19.40

X0’ = (35, 10) + 0.76 (25-35, 20-15) + 19.4 (20-15, 35-25) / [(25-35)2 + (20-15)2]1/2

X0’ = (36.03, 31.17)

0 5 10 15 20 25 30 35 40 45 50 6055

0

5

10

15

20

25

30

35

40

45

50

Q0

P0

P0’

Q0’P1

P1’

Q1’

Q1

X

X0’

Page 87: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Exemplo (cont):

u1 = [(20-20) (10-20) + (25-30)(35-30)] / [(10-20)2+ (35-30)2] = - 0.2

v1 = [(20-20) (35-30) + (25-30)(20-10)] / [(10-20)2+ (35-30)2]1/2 = -4,47

X1’ = (25, 50) - 0.2 (5-25, 40-50) -4,47 (40-50, 25-5) / [(25-5)2 + (40-50)2]1/2

X1’ = (25, 50) + (4.6, 2) + (2, -3.99) = (31.6, 48,01)

0 5 10 15 20 25 30 35 40 45 50 6055

0

5

10

15

20

25

30

35

40

45

50

Q0

P0

P0’

Q0’P1

P1’

Q1’

Q1

X

X0’

X1’

Page 88: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

Exemplo (cont):

Dados a = 0.1; b = 2; p= 0wi = 1/[0.1+di]

2

d0 = v0 = 19.4 => w0 = 0.0026

d1 = distância de X a P1 = [(20-20)2 + (25-30)2]1/2

= 5 =>: w1 = 0.0384X’ = [0.0026* (36.03,

31.17) + 0.0384*(31.6, 48,01)]/( 0.0026+ 0.0384)

X’ = (31.88, 46,94)

0 5 10 15 20 25 30 35 40 45 50 6055

0

5

10

15

20

25

30

35

40

45

50

Q0

P0

P0’

Q0’P1

P1’

Q1’

Q1

X

X0’

X1’

X’

Page 89: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

0 5 10 15 20 25 30 35 40 45 50 6055

0

5

10

15

20

25

30

35

40

45

50

Q0

P0

P0’

Q0’P1

P1’

Q1’

Q1

X

X0’

Page 90: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

0 5 10 15 20 25 30 35 40 45 50 6055

0

5

10

15

20

25

30

35

40

45

50

Q0

P0

P0’

Q0’P1

P1’

Q1’

Q1

X

X0’

X1’

Page 91: Slides PDI 2009 Raphael versao4

Warping baseado em Campos

0 5 10 15 20 25 30 35 40 45 50 6055

0

5

10

15

20

25

30

35

40

45

50

Q0

P0

P0’

Q0’P1

P1’

Q1’

Q1

X

X0’

X1’

X’

Page 93: Slides PDI 2009 Raphael versao4

Morphing

Interpolação de formas e cores entre duas imagens distintas(f0 e fN-1)

Encontrar imagens f1, f2, ..., fN-2: transição gradual de f0 a fN-1

Efeitos especiais na publicidade e na indústria cinematográfica; realidade virtual; compressão de vídeo; etc.

Page 94: Slides PDI 2009 Raphael versao4

Morphing

Inicial FinalWarping

Page 95: Slides PDI 2009 Raphael versao4

Morphing

Inicial Final

Warping I

Warping F

Page 96: Slides PDI 2009 Raphael versao4

Morphing

Inicial Final

Warping I

Warping F

Page 97: Slides PDI 2009 Raphael versao4

Morphing

Inicial FinalWarping

Page 98: Slides PDI 2009 Raphael versao4

Morphing

Page 99: Slides PDI 2009 Raphael versao4

Morphing

Page 100: Slides PDI 2009 Raphael versao4

Morphing

ai

bi

c1i

c2i

c3i

c4i

c5i

c6i

c7i

c8i

c9i

Page 101: Slides PDI 2009 Raphael versao4

Morphing

Inicial 0 Final 4Warping 2 Warping 3Warping 1

Page 102: Slides PDI 2009 Raphael versao4

Morphing

Inicial 0 Final 4

Warping 2 I Warping 3 IWarping 1 I

Warping 2 F Warping 3 FWarping 1 F

Page 103: Slides PDI 2009 Raphael versao4

Morphing

Exemplo:

http://www.youtube.com/watch?v=wZurRt0TidI

Page 104: Slides PDI 2009 Raphael versao4

Convolução

Convolução de s(t) e h(t):

dthsthtstg )()()(*)()(

Page 105: Slides PDI 2009 Raphael versao4

Convolução

dthsthtstg )()()(*)()(

t2 t3

)(h

0

-t2 -t3 0

)( h

-t2+t -t3+t

)( th

t0 t1 (0,0)

s(t)

t

Page 106: Slides PDI 2009 Raphael versao4

Convolução

Observe que g(t) = 0 para

][ 3120 t, t ttt

Page 107: Slides PDI 2009 Raphael versao4

Convolução Discreta Linear

Convolução linear entre s[n] e h[n]

][][][*][][ nhsnhnsng

Se s[n] e h[n] têm N0 e N1 amostras,respectivamente => extensão com zeros:

1

0

][][][*][][N

nhsnhnsng

com N = N0 + N1 – 1.

Page 108: Slides PDI 2009 Raphael versao4

Convolução Discreta Linear

0 1 2 3 4 5 6

2

4

6 )(s

0 1 2 3 4 5

2

4

6 )(h

0 -1

2

4

6

-2 -3 -4 1 -5

)( h

2

4

6

n

)( nh

Page 109: Slides PDI 2009 Raphael versao4

Convolução Discreta Linear

g[0] = 3

0 1 2 3 4 5 6

2

4

6 )(s

0 -1

2

4

6

-2 -3 -4 1 -5

)( h

Page 110: Slides PDI 2009 Raphael versao4

Convolução Discreta Linear

g[0] = 3

g[1] = 8

0 1 2 3 4 5 6

2

4

6 )(s

0 -1

2

4

6

-2 -3 -4 1 -5

)1( h

Page 111: Slides PDI 2009 Raphael versao4

Convolução Discreta Linear

0 1 2 3 4 5 6

2

4

6 s[n]

n

0 1 2 3 4 5

2

4

6 h[n]

n

0 1 2 3 4 5 6 7 8 9 10 11

10

20

30 g[n] = s[n]* h[n]

n

Page 112: Slides PDI 2009 Raphael versao4

Convolução Discreta Linear

Filtro

h[n]

s[n] g[n]

][][][*][][ nhsnhnsng

Page 113: Slides PDI 2009 Raphael versao4

Impulso Unitário

Delta de Dirac ou impulso unitário contínuo

1

(t)

0 t

Delta de Kronecker ou impulso unitário discreto

1

[n]

n 0

Duração = 0

Área = 1

Page 114: Slides PDI 2009 Raphael versao4

Sinais = somatório de impulsos

Delta de Kronecker

A

A[n-n0]

n0 0 n

)]1([]1[....]1[]1[][]0[][ NnNsnsnsns

1

0

][][][

N

nsns

Page 115: Slides PDI 2009 Raphael versao4

Resposta ao impulso

Resposta de um filtro a s[n]:

1

0

1

0

][][][][][NN

nshnhsng

Resposta de um filtro ao impulso

1

0

1

0

][][][][][

NN

hnnhng

1

0

][][][

N

hnnh

Page 116: Slides PDI 2009 Raphael versao4

Resposta ao impulso

h[n]: Resposta ao impulso

Máscara convolucional

Kernel do filtro

Vetor de coeficientes do filtro

Page 117: Slides PDI 2009 Raphael versao4

Convolução Discreta Circular

Sinais s[n] e h[n] com N0 e N1 amostras,respectivamente => extensão com zeros:

NnN

Nnnsnse

0

0

,0

0 ],[][

NnN

Nnnhnhe

1

1

,0

0 ],[][

Extensão periódica: considera-se quese[n] e he[n] são períodos de sp[n] e hp[n]

Convolução circular:

1

0

][][][][][N

ppp nhsnhnsng

Page 118: Slides PDI 2009 Raphael versao4

Convolução Circular x Linear

Fazendo-se N = N0 + N1 – 1

][*][][][ nhnsnhns

Page 119: Slides PDI 2009 Raphael versao4

Convolução de Imagens

f[i, j] (R0xC0) e h[i, j] (R1xC1): extensãopor zeros

1

0

1

0

],[],[],[*],[],[R C

jihfjihjifjig

1

0

1

0

],[],[],[],[],[R C

ppp jihfjihjifjig

Iguais se R=R0+R1–1 e C=C0+C1–1

Page 120: Slides PDI 2009 Raphael versao4

Máscaras Convolucionais

1 1 1

0 0 0

-1 -1 -1

1 0 -1

1 0 -1

1 0 -1

-1 -1 -1

-1 8 -1

-1 -1 -1

1/9 1/9 1/9

1/9 1/9 1/9

1/9 1/9 1/9

0.025 0.1 0.025

0.1 0.5 0.1

0.025 0.1 0.025

Page 121: Slides PDI 2009 Raphael versao4

Operador de Bordas de Kirsch

5 5 5

-3 0 -3

-3 -3 -3

-3 5 5

-3 0 5

-3 -3 -3

-3 -3 5

-3 0 5

-3 -3 5

-3 -3 -3

-3 0 5

-3 5 5

-3 -3 -3

-3 0 -3

5 5 5

...

Filtragem sucessiva com cada máscara Pixel de saída recebe o valor máximo

Page 122: Slides PDI 2009 Raphael versao4

Máscaras Convolucionais

Em geral:

Máscaras de integração somam para 1

Máscaras de diferenciação somam para 0

Page 123: Slides PDI 2009 Raphael versao4

Correlação

Convolução:

][][][*][][ nhsnhnsng

Correlação:

][][][][][ nhsnhnsng

Quando um dos sinais é par, correlação = convolução

Page 124: Slides PDI 2009 Raphael versao4

Correlação

Exemplo:

h[-1] = 3; h[0] = 7; h[1] = 5;

s[0..15] = {3, 2, 4, 1, 3, 8, 4, 0, 3, 8, 0,

7, 7, 7, 1, 2}

Extensão com zeros

Page 125: Slides PDI 2009 Raphael versao4

Correlação

Exemplo:

...

39]1[]3[]0[]2[]1[]1[]2[][]2[

43]1[]2[]0[]1[]1[]0[]1[][]1[

31]1[]1[]0[]0[][][]0[

15]1[]0[]1[

3

1

2

0

1

0

hshshshsg

hshshshsg

hshshsg

hsg

Page 126: Slides PDI 2009 Raphael versao4

Correlação

Exemplo:

g[0..15] = 31, 43, 39, 34, 64, 85, 52, 27, 61, 65, 59, 84, 105, 75, 38, 27

Observe que g[5] é elevado, pois é obtido centrando h em s[5] e calculando a correlação entre (3, 7, 5) e (3, 8, 4)

Mas g[12] é ainda maior, devido aos valores elevados de s[11..13]

Page 127: Slides PDI 2009 Raphael versao4

Correlação Normalizada

A correlação normalizada elimina a dependência dos valores absolutos dos sinais:

22 ])[(])[(

][][

][][][

nhs

nhs

nhnsng

Page 128: Slides PDI 2009 Raphael versao4

Correlação Normalizada

Resultado para o exemplo anterior:

g[0..15] = .??? .877 .934 .73 .81 .989 .64 .59 .78 .835 .61 .931 .95 .83 .57 .???

Valor máximo: g[5]

Page 129: Slides PDI 2009 Raphael versao4

Técnicas no Domínio da Freqüência

Conversão ao domínio da freqüência: transformadas

Processamento e análise no domínio da freqüência

Fourier, Cosseno Discreta, Wavelets,etc.

Page 130: Slides PDI 2009 Raphael versao4

Cosseno Analógico

f: freqüência

T=1/f: período

: fase

A: amplitude

Gráfico para fase nula e A>0

ftAtx 2cos)(

T

A

Page 131: Slides PDI 2009 Raphael versao4

Uma Família de Funções Cosseno Analógicas

fk: freqüência do k-ésimo cosseno

Tk =1/fk: período do k-ésimo cosseno

: fase do k-ésimo cosseno

Ak: amplitude do k-ésimo cosseno

1..., ,1 ,0 ,2cos)( NktfAtx kkkk

k

Page 132: Slides PDI 2009 Raphael versao4

Uma Família de Funções Cosseno Discretas

k = 0,1,...N-1

110 ,2cos][ ,...,N,nnfAnx kkkk

Page 133: Slides PDI 2009 Raphael versao4

Uma Família de Funções Cosseno Discretas

1-... 2, 1,para 1

0para 1/21/2

Nk

kck

N

kfk

2

k

NTk

2

N

kk

2

110 ,2

)12(cos

2][

2/1

,...,N,n

N

knXc

Nnx kkk

kkk XcN

A

2/12

Page 134: Slides PDI 2009 Raphael versao4

Uma Família de Funções Cosseno Discretas

110 ,2

)12(cos

2][

2/1

,...,N,n

N

knXc

Nnx kkk

110 ,2

12][ 0

2/12/1

0

,...,N,nX

Nnx

0

00

0

0

fk

NTN

fk 22

11 11 (meio-período em N amostras)

1

2

2

11 11

N

NT

N

NfNk NN

Page 135: Slides PDI 2009 Raphael versao4

Uma Família de Funções Cosseno Discretas

xk[n] (N = 64, Xk = 10).

0 10 20 30 40 50 60 70-2

-1

0

1

2

k=1

Meio-ciclo

Page 136: Slides PDI 2009 Raphael versao4

Uma Família de Funções Cosseno Discretas

k=2

1 ciclo

0 10 20 30 40 50 60 70-2

-1

0

1

2

0 10 20 30 40 50 60 70 -2

-1

0

1

2

k=3

1,5 ciclo

Page 137: Slides PDI 2009 Raphael versao4

Uma Família de Funções Cosseno Discretas

k=32

16 ciclos

Para

visualização

0 10 20 30 40 50 60 70-2

-1

0

1

2

0 10 20 30 40 50 60 70-2

-1

0

1

2

Page 138: Slides PDI 2009 Raphael versao4

Uma Família de Funções Cosseno Discretas

k=63

31,5 ciclos

Para

visualização

0 10 20 30 40 50 60 70-2

-1

0

1

2

0 10 20 30 40 50 60 70-2

-1

0

1

2

Page 139: Slides PDI 2009 Raphael versao4

Uma Família de Funções Cosseno Discretas

Amostragem de um sinal periódico não necessariamente produz um sinal de mesmo período (ou mesmo periódico).

Page 140: Slides PDI 2009 Raphael versao4

Somando Cossenos Discretos

Criar um sinal x[n] somando-se os sinais xk[n], k = 0...N-1, amostra a amostra:

110 ],[][1

0

,...,N,nnxnxN

kk

110 ,2

)12(cos

2][

1

0

2/1

,...,N,nN

knXc

Nnx

N

kkk

Page 141: Slides PDI 2009 Raphael versao4

Somando Cossenos Discretos

Exemplo:

N = 8; X0 = 10; X1 = 5; X2 = 8,5; X3 = 2; X4 = 1; X5 = 1,5; X6 = 0; X7 = 0,1.

0 2 4 6 8 2

3

4

5

102

1

2

1][

2/1

0

nx

=3.5355

Page 142: Slides PDI 2009 Raphael versao4

Somando Cossenos Discretos

X1 = 5

=2.4520; 2.0787; 1.3889; 0.4877; -0.4877; -1.3889; -2.0787; -2.4520

0 2 4 6 8 -4

-2

0

2

4

16

)12(cos

2

5][1

nnx

0 2 4 6 8 0

2

4

6

x0[n]+x1[n]

Page 143: Slides PDI 2009 Raphael versao4

Somando Cossenos Discretos

X2 = 8,5

= 3.9265; 1.6264; -1.6264; -3.9265; -3.9265; -1.626; 1.6264; 3.9265

x0[n]+x1[n] +x2[n]

0 2 4 6 8 -4

-2

0

2

4

16

2)12(cos

2

5.8][2

nnx

0 2 4 6 8 -5

0

5

10

Page 144: Slides PDI 2009 Raphael versao4

Somando Cossenos Discretos

X3 = 2

= 0.8315; -0.1951; -0.9808; -0.5556; 0.5556; 0.9808; 0.1951; -0.8315

x0[n]+x1[n]+x2[n]+x3[n]

0 2 4 6 8 -1

-0.5

0

0.5

1

16

3)12(cos

2

2][3

nnx

0 2 4 6 8 -5

0

5

10

15

Page 145: Slides PDI 2009 Raphael versao4

Somando Cossenos Discretos

X4 = 1

= 0.3536; -0.3536; -0.3536; 0.3536; 0.3536; -0.3536; -0.3536; 0.3536

x0[n]+x1[n]+x2[n]+x3[n] +x4[n]

0 2 4 6 8 -0.4

-0.2

0

0.2

0.4

16

4)12(cos

2

1][4

nnx

0 2 4 6 8 -5

0

5

10

15

Page 146: Slides PDI 2009 Raphael versao4

Somando Cossenos Discretos

X5 = 1,5

= 0.4167 -0.7356 0.1463 0.6236 -0.6236 -0.1463 0.7356 -0.4167

x0[n]+x1[n]+x2[n]+x3[n] +x4[n]+x5[n]

16

5)12(cos

2

5.1][5

nnx

0 2 4 6 8 -1

-0.5

0

0.5

1

0 2 4 6 8 -5

0

5

10

15

Page 147: Slides PDI 2009 Raphael versao4

Somando Cossenos Discretos

X6 = 0

= 0

x0[n]+x1[n]+x2[n]+x3[n] +x4[n]+x5[n]+x6[n]

0 2 4 6 8 -5

0

5

10

15

0 2 4 6 8 -1

-0.5

0

0.5

1

16

6)12(cos

2

0][6

nnx

Page 148: Slides PDI 2009 Raphael versao4

Somando Cossenos Discretos

X7 = 0,1

= 0.0098; -0.0278; 0.0416; -0.0490’; 0.0490; -0.0416; 0.0278; -0.0098

x[n]=x0[n]+x1[n]+x2[n]+ x3[n] +x4[n]+x5[n]+x6[n] +x7[n]

0 2 4 6 8 -0.05

0

0.05

16

7)12(cos

2

1.0][7

nnx

0 2 4 6 8 -5

0

5

10

15

Page 149: Slides PDI 2009 Raphael versao4

Somando Cossenos Discretos

X[k] é um sinal digital: X[k]= X0, X1,...XN-1

Exemplo: X[k]=10;5;8.5;2;1;1.5;0;0.1

Dado X[k] pode-se obter x[n]

X[k]: representação alternativa para x[n]

0 2 4 6 8 -5

0

5

10

15

X[k]

0 2 4 6 8 0

5

10

x[n]

Page 150: Slides PDI 2009 Raphael versao4

Somando Cossenos Discretos

xk[n]: cosseno componente de x[n], de freqüência fk = k/2N; ou

xk[n]: componente de freqüência fk = k/2N;

X[k]: Diretamente relacionado com a amplitude da componente de freqüência fk = k/2N

X[k] representa a importância da componente de freqüência fk = k/2N

Page 151: Slides PDI 2009 Raphael versao4

Transformada Cosseno Discreta (DCT)

DCT de x[n]:

110 ,2

)12(cos][

2][

1

0

2/1

,...,N,nN

knkXc

Nnx

N

kk

110 ,2

)12(cos][

2][

1

0

2/1

,...,N,kN

knnxc

NkX

N

nk

Transformada DCT inversa (IDCT) de X[k]:

Page 152: Slides PDI 2009 Raphael versao4

Transformada Cosseno Discreta (DCT)

X[k]: coeficientes DCT

X: representação de x no domínio da freqüência

X[0]: coeficiente DC (Direct Current)

X[1]...X[N-1]: coeficientes AC (Alternate Current)

Complexidade

Algoritmos eficientes: FDCT

Page 153: Slides PDI 2009 Raphael versao4

DCT – Exemplo 1

0 20 40 60 80 100 120 -0.2

-0.1

0

0.1

g1

0 20 40 60 80 100 120

-2

-1

0

1

2

g3

0 20 40 60 80 100 120

-2

-1

0

1

2

g1+ g3

Page 154: Slides PDI 2009 Raphael versao4

DCT – Exemplo 1 (Cont.)

0 20 40 60 80 100 120

-2

-1

0

1

2

g10

0 20 40 60 80 100 120

-2

-1

0

1

2

g1+g3+g10

0 20 40 60 80 100 120 -0.2

-0.1

0

0.1

g118

0 20 40 60 80 100 120

-2

-1

0

1

2

g1+g3+g10+g118

+

Page 155: Slides PDI 2009 Raphael versao4

DCT – Exemplo 2

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

1π2cos29.99][1

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

2π2cos48.54][2

0 10 20 30 40 50 60 -100

-50

0

50

100

150 21 ff

Page 156: Slides PDI 2009 Raphael versao4

DCT – Exemplo 2 (Cont.)

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

3π2cos34.23][3

0 10 20 30 40 50 60 -100

-50

0

50

100

150 321 fff

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

4π2cos-35.19][4

0 10 20 30 40 50 60 -100

-50

0

50

100

150 421 ... fff

Page 157: Slides PDI 2009 Raphael versao4

DCT – Exemplo 2 (Cont.)

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

5π2cos-34.55][5

0 10 20 30 40 50 60

-100

-50

0

50

100

150 621 ... fff

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

6π2cos-33.29][6

0 10 20 30 40 50 60

-100

-50

0

50

100

150 621 ... fff

Page 158: Slides PDI 2009 Raphael versao4

DCT – Exemplo 2 (Cont.)

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

7π2cos-63.42][7

0 10 20 30 40 50 60

-100

-50

0

50

100

150

200 721 ... fff

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

8π2cos-42.82][8

0 10 20 30 40 50 60

-100

-50

0

50

100

150

200 821 ... fff

Page 159: Slides PDI 2009 Raphael versao4

DCT – Exemplo 2 (Cont.)

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

9π2cos-10.31][9

0 10 20 30 40 50 60

-100

-50

0

50

100

150

200 921 ... fff

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

10π2cos7.18][10

0 10 20 30 40 50 60

-100

-50

0

50

100

150

200 1021 ... fff

Page 160: Slides PDI 2009 Raphael versao4

DCT – Exemplo 2 (Cont.)

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

20π2cos-62.24][20

0 10 20 30 40 50 60 -200

0

200

400

600 2021 ... fff

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

40π2cos35.54][40

0 10 20 30 40 50 60

-200

0

200

400

600

800

1000

4021 ... fff

Page 161: Slides PDI 2009 Raphael versao4

DCT – Exemplo 2 (Cont.)

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

60π2cos-6.73][60

0 10 20 30 40 50 60

-200

0

200

400

600

800

1000

1200

6021 ... fff

0 10 20 30 40 50 60

-60

-40

-20

0

20

40

60

Nn

Nnf

2

π

2

63π2cos-1.51][63

0 10 20 30 40 50 60

-200

0

200

400

600

800

1000

1200

6321 ... fff

Page 162: Slides PDI 2009 Raphael versao4

DCT – Exemplo 3

0 500 1000 1500 2000 850

900

950

1000

1050

1100

1150

1200

1250

Sinal eletrocardiográfico,

2048 amostras

0 500 1000 1500 2000 -400

-200

0

200

400

DCT do sinal eletrocardiográfico (sem termo DC)

Page 163: Slides PDI 2009 Raphael versao4

DCT – Exemplo 4

Onda Quadrada

DCT da Onda Quadrada

0 10 20 30 40 50 60 -20

-10

0

10

20

0 10 20 30 40 50 60 -60

-40

-20

0

20

40

60

Page 164: Slides PDI 2009 Raphael versao4

Freqüências em Hz

Ta = 1/fa (Período de amostragem)

N amostras ---- (N-1)Ta segundos

HzN

f

TNf

Nf a

a )1(2)1(2

1nal)(adimensio

2

111

Hzf

N

fNf aa

N2)1(2

)1(1

Page 165: Slides PDI 2009 Raphael versao4

Freqüências em Hz

Aumentar N melhora a resolução de freqüência.

Aumentar fa aumenta a freqüência máxima digitalizável, em Hz.

Dualidade com o domínio do tempo

Page 166: Slides PDI 2009 Raphael versao4

Freqüências em Hz

Sinal de ECG, N= 2048, fa=360Hz

Valores em Hz para k = 14, 70, 683 e 2047

70 683 2047

14

Page 167: Slides PDI 2009 Raphael versao4

Freqüências em Hz

f1 = fa/[2(N-1)] Hz = 360/(2x2047) = 0,087933561

f14 = 14f1 = 1,23 Hz

f70 = 70f1 = 6,16 Hz

f683 = 683f1 = 60,06 Hz

f2047 = 2047f1 = 180 Hz

Page 168: Slides PDI 2009 Raphael versao4

Freqüências em Hz

Observações

fa = 360 Hz <=> Ta = 0,002778 Hz

Tempo total para 2048 amostras = 5,69s

Um batimento cardíaco: aprox. 0,8 s

“Freqüência” Cardíaca: aprox. 1,25 bat./s = 1,25 Hz, ou 75 batimentos/min.

“Freqüência” Cardíaca aprox. igual a f14

Page 169: Slides PDI 2009 Raphael versao4

Freqüências em Hz

Onda quadrada, N = 64, fa = 1Hz

Valores em Hz para k = 7, 8, 9 e 63

0 7 63 -60

-40

-20

0

20

40

60

9

Page 170: Slides PDI 2009 Raphael versao4

Freqüências em Hz

f1 = fa/[2(N-1)] Hz = 1/(2x63) = 0,007936507

f7 = 7f1 = 0,0556 Hz

f8 = 8f1 = 0,0625 Hz

f9 = 9f1 = 0,0714 Hz

f63 = 63f1 = 0,5 Hz

Obs:

Período do sinal = 16 s

Freqüência da onda = 0,0625

Page 171: Slides PDI 2009 Raphael versao4

Freqüências e Conteúdo de Freqüência

Sinal periódico

Freqüência

Freqüências componentes

Sinal não-periódico:

Freqüências componentes

Page 172: Slides PDI 2009 Raphael versao4

Sinais analógicos senoidais

Representação em freqüência de um sinal analógico senoidal?

fa mínimo para digitalização adequada?

Se f não é múltiplo de f1?

Sinal analógico senoidal, de freqüência f

Page 173: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

Cosseno com f=10Hz, fa=100Hz, N=26

0 0.05 0.1 0.15 0.2 0.25-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

Page 174: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

DCT do cosseno com f = 10Hz, fa=100Hz, N=26

0 5 10 15 20 25 30 35 40 45 50-0.5

0

0.5

1

1.5

2

2.5

3

3.5

4

Page 175: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

Vazamento de freqüência: mais de uma componente de freqüência para uma senóide

Minimizar vazamento de freqüência: aumentar N

Page 176: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

Cosseno com f = 30Hz, fa=100Hz, N=26

0 0.05 0.1 0.15 0.2 0.25-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

Page 177: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

DCT do cosseno com f = 30Hz, fa=100Hz, N=26

0 5 10 15 20 25 30 35 40 45 50-1.5

-1

-0.5

0

0.5

1

1.5

2

2.5

3

3.5

Page 178: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

Cosseno com f = 48Hz, fa=100Hz, N=26

0 0.05 0.1 0.15 0.2 0.25-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

Page 179: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

DCT do cosseno com f = 48Hz, fa=100Hz, N=26

0 5 10 15 20 25 30 35 40 45 50-0.5

0

0.5

1

1.5

2

2.5

3

3.5

Page 180: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

Cosseno com f = 50Hz, fa=100Hz, N=26

0 0.05 0.1 0.15 0.2 0.25-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

Page 181: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

DCT do cosseno com f = 50Hz, fa=100Hz, N=26

0 5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Page 182: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

Cosseno com f = 52Hz, fa=100Hz, N=26

0 0.05 0.1 0.15 0.2 0.25-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

Page 183: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

DCT do cosseno com f = 52Hz, fa=100Hz, N=26

0 5 10 15 20 25 30 35 40 45 50-0.5

0

0.5

1

1.5

2

2.5

3

3.5

Page 184: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

Sinal digital obtido a partir do cosseno de 52Hz é idêntico ao obtido a partir do cosseno de 48 Hz

0 0.0

5

0.1 0.1

5

0.2 0.2

5

-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

0 0.0

5

0.1 0.1

5

0.2 0.2

5

-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

Page 185: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

Cosseno com f = 70Hz, fa=100Hz, N=26

0 0.05 0.1 0.15 0.2 0.25-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

Page 186: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

DCT do cosseno com f = 70Hz, fa=100Hz, N=26

0 5 10 15 20 25 30 35 40 45 50-1.5

-1

-0.5

0

0.5

1

1.5

2

2.5

3

3.5

Page 187: Slides PDI 2009 Raphael versao4

Amostragem de Senóides

Sinal digital obtido a partir do cosseno de 70Hz é idêntico ao obtido a partir do cosseno de 30 Hz

0 0.0

5

0.1 0.1

5

0.2 0.2

5

-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

0 0.0

5

0.1 0.1

5

0.2 0.2

5

-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

Page 188: Slides PDI 2009 Raphael versao4

Aliasing

Na DCT, a maior freqüência é fa/2

Aliasing: sinais senoidais de freqüência f > fa/2 são discretizados como sinais senoidais de freqüência fd < fa / 2 (fd=fa–f, para fa/2 < f < fa)

Page 189: Slides PDI 2009 Raphael versao4

Aliasing

Page 190: Slides PDI 2009 Raphael versao4

Teorema de Shannon-Nyquist

Sinal analógico com fmax Hz (componente)

Digitalizar com fa Hz, tal que:

maxmax 22

ffff

aa

2fmax: Freq. de Nyquist

Page 191: Slides PDI 2009 Raphael versao4

Digitalização de áudio

Ouvido humano é sensível a freq. entre 20Hz e 22KHz (aprox.)

Digitalizar com 44KHz?

Sons podem ter freqüências componentes acima de 22KHz

Digitalização a 44KHz: aliasing.

Filtro passa-baixas com freqüência de corte em 22KHz = Filtro anti-aliasing

Page 192: Slides PDI 2009 Raphael versao4

Eliminação de pixels revisitada

Por que redução de imagens por eliminação de pixel deve ser evitada?

Sinal original digitalizado com fa =2fmax

No. de amostras do sinal digital reduzido pela metade por eliminação de amostras -> nova freqüência de amostragem f’a = fa/2 = fmax

->

freqüência máxima do sinal analógico digitalizada sem aliasing = f’a/2 = fmax/2

Page 193: Slides PDI 2009 Raphael versao4

Eliminação de pixels revisitada

Por que redução de imagens (ou outros sinais) por eliminação de pixel (ou amostras) deve ser evitada?

Usar filtro passa-baixas!

Aliasing!

Page 194: Slides PDI 2009 Raphael versao4

Filtros no domínio da freqüência

Multiplicar o sinal no domínio da freq., S, pela função de transferência do filtro, H

Filtros:

Passa-baixas

Passa-altas

Passa-faixa

Corta-baixas

Corta-altas

Corta-faixa (faixa estreita: notch)

Page 195: Slides PDI 2009 Raphael versao4

Filtros no domínio da freq.

H

fc N-1

1

Passa-baixas

(corta-altas)

H

fc N-1

1

Passa-altas

(corta-baixas)

H

fc1 N-1

1

Passa-faixa

fc2

H

fc1 N-1

1

corta-faixa

fc2

Ideais

Page 196: Slides PDI 2009 Raphael versao4

Filtros no domínio da freqüência

Combinação de filtros

Filtros não-ideais (corte suave, |H(fc)|=(1/2)1/2 ou |H(fc)|=1/2)

Page 197: Slides PDI 2009 Raphael versao4

DCT 2-D

Operação separável

Complexidade elevada

N

ln

N

kmnmxcc

NlkX

N

m

N

nlk

2

)12(cos

2

)12(cos],[

2

1],[

1

0

1

0

N

nl

N

mklkXcc

Nnmx

N

k

N

llk

2

)12(cos

2

)12(cos],[

2

1],[

1

0

1

0

Page 198: Slides PDI 2009 Raphael versao4

DCT 2-D

Imagem “cosseno na vertical”, 256 x 256, 8 ciclos (k = 16) e sua DCT normalizada

Page 199: Slides PDI 2009 Raphael versao4

DCT 2-D

Imagem “cosseno na vertical”, 256 x 256, 16 ciclos (k = 32) e sua DCT normalizada

Page 200: Slides PDI 2009 Raphael versao4

DCT 2-D

Imagem “cosseno na horizontal x cosseno na vertical”, 256 x 256, 16 ciclos (k = 32) e sua DCT normalizada

Page 201: Slides PDI 2009 Raphael versao4

DCT 2-D

Imagem “cosseno na horizontal x cosseno na vertical”, 256 x 256, 8 x 16 ciclos e sua DCT normalizada

Page 202: Slides PDI 2009 Raphael versao4

DCT 2-D

Imagem “Lena” (256x256) e sua DCT normalizada

Page 203: Slides PDI 2009 Raphael versao4

DCT 2-D

Imagem “Lena” (256x256) e o log(DCT+1) normalizado

Page 204: Slides PDI 2009 Raphael versao4

Transformada de Fourier Discreta (DFT)

n, u = 0, 1, ..., N-1

1

0

2

][1

][N

n

N

unj

ensN

uF

1

0

2

][][N

u

N

unj

euFns

Direta:

Inversa:

1j

Fórmula de Euler: sencos je j

Page 205: Slides PDI 2009 Raphael versao4

Duas propriedades essenciais

|F[-u]| = ?

?][ NuF

Page 206: Slides PDI 2009 Raphael versao4

Duas propriedades essenciais

|F[u]| = |F[-u]|

)(][ uFNuF

Espectro de Fourier é função par:

DFT é periódica de período N:

Page 207: Slides PDI 2009 Raphael versao4

Esboço do Espectro de Fourier

N/2 -N/2 N-1 u

|F[u]|

u = 0, N, 2N,...: freq. 0

u = N/2, 3N/2,...: freq. máxima (N par)

u = (N-1)/2,...: freq. máxima (N ímpar)

Page 208: Slides PDI 2009 Raphael versao4

Freqüências em Hz

Ta = 1/fa (Período de amostragem)

N amostras ---- (N-1)Ta segundos

HzN

f

TNf

Nf a

a 1)1(

1nal)(adimensio

111

Hzf

N

fNf aa

N2)1(2

12/)1(

Page 209: Slides PDI 2009 Raphael versao4

Fourier 2-D

Operação separável

Complexidade elevada

1

0

1

0

)//(2],[1

],[C

m

R

n

RvnCumjenmsRC

vuF

1

0

1

0

)//(2],[],[C

u

R

v

RvnCumjevuFnms

Page 210: Slides PDI 2009 Raphael versao4

Exibição do Espectro de Fourier 2-D

Flog[u, v] = round[(L - 1) log(1+|F[u, v]|)/Fmax2]

Page 211: Slides PDI 2009 Raphael versao4

Teorema da Convolução

Se

Então:

G[u,v] = H[u,v]F[u,v]

onde

G[u,v]: DFT de g[m,n]

F[u,v]: DFT de s[m,n]

H[u,v]: DFT de h[m,n]

],[],[ ],[ nmhnmsnmg

H[u,v]: Função de transferência do filtro

Page 212: Slides PDI 2009 Raphael versao4

Filtros: espaço x freqüência

Projeto de filtro no domínio da freqüência (Fourier)

Método imediato: H[k], k = 0..N-1

Como filtrar sinais no domínio do tempo, em tempo real?

Convolução com h[n], n = 0..N-1 pode ser proibitiva para n grande

Encontrar ht[n], n = 0..M-1, com M < N, de modo a obter uma aproximação adequada para H[k].

Page 213: Slides PDI 2009 Raphael versao4

Filtros: espaço x freqüência

Para eficiência computacional e redução de custos, o número de coeficientes do filtro deve ser o menor possível

Projetar filtros relativamente imunes ao truncamento

Page 214: Slides PDI 2009 Raphael versao4

Questões do PosComp 2002

51. Histograma de uma imagem com K tons de cinza é : a) Contagem dos pixels da imagem. b) Contagem do número de tons de cinza que ocorreram na imagem.

c) Contagem do número de vezes que cada um dos K tons de cinza ocorreu na imagem.

d) Contagem do número de objetos encontrados na imagem. e) Nenhuma alternativa acima.

52. filtro da mediana é : a) Indicado para detectar bordas em imagens.

b) Indicado para atenuar ruído com preservação de bordas (i.é rápidas transições de nível em

imagens). c) Indicado para detectar formas específicas em imagens. d) Indicado para detectar tonalidades específicas em uma imagem.

e) Nenhuma das respostas acima.

Page 215: Slides PDI 2009 Raphael versao4

Questões do PosComp 2002

51. Histograma de uma imagem com K tons de cinza é : a) Contagem dos pixels da imagem. b) Contagem do número de tons de cinza que ocorreram na imagem.

c) Contagem do número de vezes que cada um dos K tons de cinza ocorreu na imagem.

d) Contagem do número de objetos encontrados na imagem. e) Nenhuma alternativa acima.

52. filtro da mediana é : a) Indicado para detectar bordas em imagens.

b) Indicado para atenuar ruído com preservação de bordas (i.é rápidas transições de nível em

imagens). c) Indicado para detectar formas específicas em imagens. d) Indicado para detectar tonalidades específicas em uma imagem.

e) Nenhuma das respostas acima.

Page 216: Slides PDI 2009 Raphael versao4

Questões do PosComp 2004

56) Considerando as declarações abaixo, é incorreto afirmar: a) Filtros passa-altas são utilizados para detecção de bordas em imagens b) A transformada discreta de Fourier nos permite obter uma representação de

uma imagem no domínio freqüência c) Filtragem no domínio espacial é realizada por meio de uma operação chamada

“convolução” d) Os filtros Gaussiano e Laplaciano são exemplos de filtro passa-baixas e) O filtro da mediana pode ser utilizado para redução de ruído em uma imagem

58) Identifique a declaração incorreta: a) As operações de ajuste de brilho e contraste são operações lineares b) A equalização de histograma é uma transformação não-linear e específica

para cada imagem c) A transformação necessária para calcular o negativo de uma imagem pode ser

aplicada simultaneamente (i.e., em paralelo) a todos pixels da imagem original d) A equalização de histograma pode ser obtida a partir de um histograma

cumulativo da imagem original e) O objetivo da equalização de histograma é reduzir o constrastre nas regiões

da imagem que correspondem à porção do histograma com maior concentração de pixels

Page 217: Slides PDI 2009 Raphael versao4

Questões do PosComp 2004

56) Considerando as declarações abaixo, é incorreto afirmar: a) Filtros passa-altas são utilizados para detecção de bordas em imagens b) A transformada discreta de Fourier nos permite obter uma representação de

uma imagem no domínio freqüência c) Filtragem no domínio espacial é realizada por meio de uma operação chamada

“convolução” d) Os filtros Gaussiano e Laplaciano são exemplos de filtro passa-baixas e) O filtro da mediana pode ser utilizado para redução de ruído em uma imagem

58) Identifique a declaração incorreta: a) As operações de ajuste de brilho e contraste são operações lineares b) A equalização de histograma é uma transformação não-linear e específica

para cada imagem c) A transformação necessária para calcular o negativo de uma imagem pode ser

aplicada simultaneamente (i.e., em paralelo) a todos pixels da imagem original d) A equalização de histograma pode ser obtida a partir de um histograma

cumulativo da imagem original e) O objetivo da equalização de histograma é reduzir o constrastre nas regiões

da imagem que correspondem à porção do histograma com maior concentração de pixels

Page 218: Slides PDI 2009 Raphael versao4

Questões do PosComp 2005

59. O processo de análise de imagens é uma seqüência de etapas que são iniciadas a partir da definição do problema. A seqüência correta destas etapas é: (a) pré-processamento, aquisição, segmentação, representação, reconhecimento. (b) aquisição, pré-processamento, segmentação, representação, reconhecimento. (c) aquisição, pré-processamento, representação, segmentação, reconhecimento. (d) aquisição, representação, pré-processamento, segmentação, reconhecimento. (e) pré-processamento, aquisição, representação, segmentação, reconhecimento.

60. O termo imagem se refere a uma função bidimensional de intensidade de luz, denotada por f(x; y), onde o valor ou amplitude de f nas coordenadas espaciais (x; y) representa a intensidade (brilho) da imagem neste ponto. Para que uma imagem possa ser processada num computador, a função f(x; y) deve ser discretizada tanto espacialmente quanto em amplitude. Estes dois processos recebem as seguintes denominações, respectivamente: (a) translação e escala. (b) resolução e escala. (c) resolução e ampliação. (d) amostragem e quantização. (e) resolução e quantização.

Page 219: Slides PDI 2009 Raphael versao4

Questões do PosComp 2005

59. O processo de análise de imagens é uma seqüência de etapas que são iniciadas a partir da definição do problema. A seqüência correta destas etapas é: (a) pré-processamento, aquisição, segmentação, representação, reconhecimento. (b) aquisição, pré-processamento, segmentação, representação, reconhecimento. (c) aquisição, pré-processamento, representação, segmentação, reconhecimento. (d) aquisição, representação, pré-processamento, segmentação, reconhecimento. (e) pré-processamento, aquisição, representação, segmentação, reconhecimento.

60. O termo imagem se refere a uma função bidimensional de intensidade de luz, denotada por f(x; y), onde o valor ou amplitude de f nas coordenadas espaciais (x; y) representa a intensidade (brilho) da imagem neste ponto. Para que uma imagem possa ser processada num computador, a função f(x; y) deve ser discretizada tanto espacialmente quanto em amplitude. Estes dois processos recebem as seguintes denominações, respectivamente: (a) translação e escala. (b) resolução e escala. (c) resolução e ampliação. (d) amostragem e quantização. (e) resolução e quantização.

Page 220: Slides PDI 2009 Raphael versao4

Questões do PosComp 2006

47. [TE] Considere os filtros espaciais da média (m) e Mediana (M) aplicados em imagens em níveis de cinza f e g. Qual par de termos ou expressões a seguir não está associado, respectivamente, a características gerais de m e M? (a) m(f + g) = m(f) + m(g); M(f + g) != M(f) + M(g) (b) ruído gaussiano; ruído impulsivo (c) convolução; filtro estatístico da ordem (d) preservação de pequenos componentes; não preservação de pequenos

componentes (e) filtragem com preservação de contornos; filtragem sem preservação de

contornos

48. [TE] A convolução da máscara [-1 2 -1] com uma linha de uma imagem contendo uma seqüência de pixels do tipo [... 3 4 5 6 7 8 9 10 ...] resulta na transformação (sem considerar efeitos de borda): (a) [...3 4 5 6 7 8 9 10...] e representa o filtro da média com 2-vizinhos mais

próximos (b) [...0 0 0 0 0 0 0 0...] e representa o laplaciano no espaço discreto (c) [...0 0 0 0 0 0 0 0...] e representa uma erosão morfológica (d) [...1 1 1 1 1 1 1 1...] e é equivalente a um filtro passa-baixas (e) [...7 9 11 13 15 17 19...] e é equivalente a um filtro passa-altas

Page 221: Slides PDI 2009 Raphael versao4

Questões do PosComp 2006

47. [TE] Considere os filtros espaciais da média (m) e Mediana (M) aplicados em imagens em níveis de cinza f e g. Qual par de termos ou expressões a seguir não está associado, respectivamente, a características gerais de m e M? (a) m(f + g) = m(f) + m(g); M(f + g) != M(f) + M(g) (b) ruído gaussiano; ruído impulsivo (c) convolução; filtro estatístico da ordem (d) preservação de pequenos componentes; não preservação de pequenos

componentes (e) filtragem com preservação de contornos; filtragem sem preservação de

contornos

48. [TE] A convolução da máscara [-1 2 -1] com uma linha de uma imagem contendo uma seqüência de pixels do tipo [... 3 4 5 6 7 8 9 10 ...] resulta na transformação (sem considerar efeitos de borda): (a) [...3 4 5 6 7 8 9 10...] e representa o filtro da média com 2-vizinhos mais

próximos (b) [...0 0 0 0 0 0 0 0...] e representa o laplaciano no espaço discreto (c) [...0 0 0 0 0 0 0 0...] e representa uma erosão morfológica (d) [...1 1 1 1 1 1 1 1...] e é equivalente a um filtro passa-baixas (e) [...7 9 11 13 15 17 19...] e é equivalente a um filtro passa-altas

Page 222: Slides PDI 2009 Raphael versao4

Questões do PosComp 2007

61. [TE] O realce de imagem tem como objetivo destacar detalhes finos procurando obter uma representação mais adequada do que a imagem original para uma determinada aplicação. Dessa forma, sobre as técnicas utilizadas no realce de imagens, é CORRETO afirmar que (a) o melhor resultado obtido depende do filtro aplicado na imagem.

Normalmente, o mais aplicado é o filtro da mediana. (b) o melhor resultado é obtido com a aplicação de filtros passa-

baixas, cujos parâmetros dependem do resultado desejado. (c) a aplicação de filtros da média sempre oferece resultado adequado

no realce de imagens. (d) o resultado mais adequado no realce de imagens está associado à

aplicação de filtro passa-altas e da interpretação subjetiva do observador que deverá ter conhecimento a priori da imagem original.

(e) o resultado mais adequado no realce de imagens está associado à aplicação de filtro passa-baixas e da interpretação subjetiva do observador que deverá ter conhecimento a priori da imagem original.

62 e 63

Page 223: Slides PDI 2009 Raphael versao4

Questões do PosComp 2007

61. [TE] O realce de imagem tem como objetivo destacar detalhes finos procurando obter uma representação mais adequada do que a imagem original para uma determinada aplicação. Dessa forma, sobre as técnicas utilizadas no realce de imagens, é CORRETO afirmar que (a) o melhor resultado obtido depende do filtro aplicado na imagem.

Normalmente, o mais aplicado é o filtro da mediana. (b) o melhor resultado é obtido com a aplicação de filtros passa-

baixas, cujos parâmetros dependem do resultado desejado. (c) a aplicação de filtros da média sempre oferece resultado adequado

no realce de imagens. (d) o resultado mais adequado no realce de imagens está associado à

aplicação de filtro passa-altas e da interpretação subjetiva do observador que deverá ter conhecimento a priori da imagem original.

(e) o resultado mais adequado no realce de imagens está associado à aplicação de filtro passa-baixas e da interpretação subjetiva do observador que deverá ter conhecimento a priori da imagem original.