Upload
raphael-marques
View
987
Download
6
Embed Size (px)
Citation preview
Introdução ao Processamento Digital de
Imagens
José Raphael Teixeira Marques – DI/PPGI
raphaelmarques.wordpress.com
Prof. Leonardo Vidal Batista
DI/PPGI/PPGEM
[email protected] [email protected]
http://www.di.ufpb.br/leonardo
Filtros de suavização
Média, Moda, Mediana, Gaussiano...
Vizinhança m x n
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
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)|
Filtros de detecção de bordas
Aproximações usuais:
Gradiente de Roberts:
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)|
Filtros de detecção de bordas
Gradiente de Prewitt:
Gradiente de Sobel:
Gradiente de Roberts
Limiares 15, 30 e 60
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)
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
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
Histograma
0 50 100 150 200 250
0
2000
4000
6000
8000
10000
Histograma
0 50 100 150 200 250
0
500
1000
1500
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
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
Expansão de Histograma
0 50 100 150 200 250
0
500
1000
1500
0 50 100 150 200 250
0
500
1000
1500
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
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.
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
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
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
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
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)
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?
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
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
Controle de contraste adaptativo
Original c < σ c > σ
Pseudo-cor
Nível de cinza
R G B
0 15 20 30
1 15 25 40
...
L-1 200 0 0
Pseudo-cor
Pseudo-cor
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
...
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.
Dissolve Cruzado
ht (i, j)= (1 - t) f(i, j) + t g(i, j)
t é um escalar no intervalo [0, 1]
http://jose.raphael.marques.googlepages.com/PDI_Dissolve.jnlp
Dissolve Cruzado
t = 0,3 t = 0,5 t = 0,7
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]
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)
Detecção de Movimento
contrario caso ,0
|| se ,1 21 tLffLg
f1 f2 g
Detecção de Movimento
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
],[
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:
Operações Topológicas
Rígidas
Translação
Rebatimento
Rotação
Mudança de Escala
Não rígidas (Warping)
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)('
Rotação e Rebatimento
Imagem original Rebatimento pela diagonal
Rotação de 90 graus em torno de (R/2,C/2)
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
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
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
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
Ampliação (Zoom in)
Exemplo: Ampliação por fator 10
Original Replicação Interpolação
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
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
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]
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)]
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
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
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);...
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
Warping (Deformação)
Warping (Deformação)
Warping (Deformação)
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
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
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
Warping baseado em Campos
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
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
Warping baseado em Campos
http://sites.google.com/site/joseraphaelmarques/arquivos/PDI_UV.jnlp
http://sites.google.com/site/joseraphaelmarques/arquivos/PDI_Warping.jnlp
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
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
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
Warping baseado em Campos
Soluções:
x2 = y1, y2 = -x1
x2 = -y1, y2 = x1
ab
b’
Warping baseado em Campos
Parâmetro u: “norma” da projeção de PXsobre PQ, dividido pela norma de PQ
2|||| PQ
PQPXu
.
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
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.
Warping baseado em Campos
PQ = (Xq-Xp, Yq-Yp)
PQ1 = (Yq–Yp, Xp-Xq)
PQ2 = (Yp–Yq, Xq-Xp)
Vamos usar PQ1
P
Q
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
Warping baseado em Campos
Cálculo de X’:
||''||
''''.''
QP
QPvQPuPX
.
Warping baseado em Campos
2|||| PQ
PQPXu
.
||''||
''''.''
QP
QPvQPuPX
.
|||| PQ
PQPXv
.
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.
Warping baseado em Campos
Warping baseado em Campos
http://sites.google.com/site/joseraphaelmarques/arquivos/PDI_UV2.jnlp
http://sites.google.com/site/joseraphaelmarques/arquivos/PDI_Warping2.jnlp
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
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)
Warping baseado em Campos
Parâmetro p controla a importância do tamanho do segmento
p = 0: independe do tamanho do segmento
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
Warping baseado em Campos
Bons resultados são obtidos com:
a entre 0 e 1
b = 2
p = 0 ou p = 1.
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’
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’
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’
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’
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’
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’
Warping baseado em Campos
http://sites.google.com/site/joseraphaelmarques/arquivos/PDI_WarpingN.jnlp
http://sites.google.com/site/joseraphaelmarques/arquivos/PDI_WarpingN_FixSize.jnlp
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.
Morphing
Inicial FinalWarping
Morphing
Inicial Final
Warping I
Warping F
Morphing
Inicial Final
Warping I
Warping F
Morphing
Inicial FinalWarping
Morphing
Morphing
Morphing
ai
bi
c1i
c2i
c3i
c4i
c5i
c6i
c7i
c8i
c9i
Morphing
Inicial 0 Final 4Warping 2 Warping 3Warping 1
Morphing
Inicial 0 Final 4
Warping 2 I Warping 3 IWarping 1 I
Warping 2 F Warping 3 FWarping 1 F
Morphing
Exemplo:
http://www.youtube.com/watch?v=wZurRt0TidI
Convolução
Convolução de s(t) e h(t):
dthsthtstg )()()(*)()(
Convolução
dthsthtstg )()()(*)()(
t2 t3
)(h
0
-t2 -t3 0
)( h
-t2+t -t3+t
)( th
t0 t1 (0,0)
s(t)
t
Convolução
Observe que g(t) = 0 para
][ 3120 t, t ttt
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.
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
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
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
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
Convolução Discreta Linear
Filtro
h[n]
s[n] g[n]
][][][*][][ nhsnhnsng
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
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
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
Resposta ao impulso
h[n]: Resposta ao impulso
Máscara convolucional
Kernel do filtro
Vetor de coeficientes do filtro
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
Convolução Circular x Linear
Fazendo-se N = N0 + N1 – 1
][*][][][ nhnsnhns
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
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
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
Máscaras Convolucionais
Em geral:
Máscaras de integração somam para 1
Máscaras de diferenciação somam para 0
Correlação
Convolução:
][][][*][][ nhsnhnsng
Correlação:
][][][][][ nhsnhnsng
Quando um dos sinais é par, correlação = convolução
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
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
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]
Correlação Normalizada
A correlação normalizada elimina a dependência dos valores absolutos dos sinais:
22 ])[(])[(
][][
][][][
nhs
nhs
nhnsng
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]
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.
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
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
Uma Família de Funções Cosseno Discretas
k = 0,1,...N-1
110 ,2cos][ ,...,N,nnfAnx kkkk
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
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
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
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
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
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
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).
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
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
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]
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
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
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
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
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
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
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]
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
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]:
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
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
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
+
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
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
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
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
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
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
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
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)
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
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
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
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
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
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
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
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
Freqüências e Conteúdo de Freqüência
Sinal periódico
Freqüência
Freqüências componentes
Sinal não-periódico:
Freqüências componentes
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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)
Aliasing
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
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
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
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!
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)
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
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)
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
DCT 2-D
Imagem “cosseno na vertical”, 256 x 256, 8 ciclos (k = 16) e sua DCT normalizada
DCT 2-D
Imagem “cosseno na vertical”, 256 x 256, 16 ciclos (k = 32) e sua DCT normalizada
DCT 2-D
Imagem “cosseno na horizontal x cosseno na vertical”, 256 x 256, 16 ciclos (k = 32) e sua DCT normalizada
DCT 2-D
Imagem “cosseno na horizontal x cosseno na vertical”, 256 x 256, 8 x 16 ciclos e sua DCT normalizada
DCT 2-D
Imagem “Lena” (256x256) e sua DCT normalizada
DCT 2-D
Imagem “Lena” (256x256) e o log(DCT+1) normalizado
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
Duas propriedades essenciais
|F[-u]| = ?
?][ NuF
Duas propriedades essenciais
|F[u]| = |F[-u]|
)(][ uFNuF
Espectro de Fourier é função par:
DFT é periódica de período N:
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)
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(
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
Exibição do Espectro de Fourier 2-D
Flog[u, v] = round[(L - 1) log(1+|F[u, v]|)/Fmax2]
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
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].
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
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.
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.
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
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
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.
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.
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
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
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
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.