Imagem Digital
Conceitos, Processamento e
Análise
Parte 1: Conceitos básicos
1. Imagem e funções
2. Imagem digital: amostragem, quantização e codificação
3. Re-amostragem de funções
4. Séries e Transformadas de Fourier e de Cosseno
5. Teorema de Nyquist e Alias
Imagem:
Modelo Matemático: Função
Níveis de cinza
100%
80%
60%
40%
20%
0%
x
Posição ao longo da linha
L
L : 0, w 0, h  2  C
u 
   L
v
L(u,v)
v
u
Função
Imagem colorida
v
G
R
u
B
Imagem coloridas como 3 canais de cor
canal verde
Imagem Digital
Amostragem, quantização e
codificação
Amostragem, quantização e
codificação de f(x)
f(x)
amostra
partição do eixo x
x
Amostragem, quantização e
codificação de f(x)
f(x)
6

5

4
3
2


amostra
quantizada









1
0
x
codificação = (3, 4, 5, 5, 4, 2, 2, 3, 5, 5, 4, 2)
Digitalização de Imagens
Discretização espacial (amostragem)
Processos básicos
64x54
amostragem
Imagem de tons
contínuos
Imagem amostrada
quantização
55 55 55 55 55 55 55
55 20 22 23 45 55 55
64x54 - 16 cores
55 55 10 09 11 55 55
55 55 43 42 70 55 55
55 55 28 76 22 55 55
8*55, 1*20, 1*22, 1*23, ….
55 55 55 55 55
55
55
codificação
Imagem amostrada,
quantizada e codificada
Imagem amostrada e
quantizada
Imagem Digital:
Histogramas
Uma outra maneira de ver a informação da imagem: probabilidade de
ocorrência de um determinado valor, uso do intervalo [0,255], contraste,...
Histogramas de Imagem Colorida
Propriedades básicas de uma
Imagem Digital
Problemas associados a re-amostragem de
um sinal digital f(x)
f(x)
6

5

4
3
2
1

função original






função reconstruída
pelo vizinho mais
próximo



0
função reconstruída
por interpolação
linear

x
(a) aumento de resolução
Re-amostragem de f(x)
f(x)
6

5

4
3
2
1

função original






função reconstruída
pelo vizinho mais
próximo



0
função reconstruída
por interpolação
linear

x
(b) redução de resolução
Freqüência de Amostragem
f(x)
x
f(x)
x
Estudo de sinais digitais
Transformadas para o domínio da
freqüencia
Teorema de Nyquist e Alias
revisão
Harmônicos
8
A
T
6
4
t+
-A
A cos(t   ) A
2
0
-2 0
0.01
0.02
0.03
0.04
-4
-6
-8
f 
1
( Hz )
T
t  2ft 
2
t (rad )
T
0.05
Integrais de senos e cosenos em [-,]
revisão
sin(nx)
cos(nx)
n=1
n=2
sin(nx)cos(nx)
Áreas se compensam.
Integrais resultam em 0.
revisão
Integrais de senos e cosenos em [-,]
Funções ortogonais
Série de Fourier
f(t)
Jean Baptiste Joseph Fourier (1768-1830)
Paper de 1807 para o Institut de France:
Joseph Louis Lagrange
0 (1736-1813), and Pierre Simon de Laplace (1749-1827).
T
t
2kt
2kt
f (t )  a0  2 (ak cos
 bk sin
)
T
T
k 1

Exemplo: Série de harmônicos
1.15
1.15
1.15
0.95
0.95
0.95
0.75
0.75
0.75
0.55
0.55
0.35
0.35
0.35
0.15
0.15
0.15
-0.05
-0.05
-0.05
-0.25
-0.25
-0.25
f(t)
Série de Fourier: cálculo de a0
2 kt
2 kt
f (t )  a0  2 (ak cos
 bk sin
)
T
T
k 1

0
T

0
T

0
T
T
f (t )dt  
0
t
T
2 nkt
2 kt 
 T
ao dt    ak  cos(
)dt  bk  sin(
)dt 
0
0
T
T

k 1 

f (t )dt  a0T  0  0
1
a0 
T

T
0
f (t ) dt
Série de Fourier: an e bn
f(t)
2 kt
2 kt
f (t )  a0  2 (ak cos
 bk sin
)
T
T
k 1

0

T
0
T
t

T
2 nt
2 n t
2 k t
0

2
a
cos(
)
cos(
)dt  0
cos(
) f (t )dt 

n
0
T
T
k 1
T
 Tan
1
an 
T

T
0
2 n t
f (t ) cos(
)dt ...
T
1
bn 
T

T
0
2 n t
f (t ) sin(
)dt
T
Resumindo
f(t)
0
T
t
2 kt
2 kt
f (t )  a0  2 (ak cos
 bk sin
)
T
T
k 1

1 T
2 kt
ak   f (t ) cos(
)dt
0
T
T
1
bk 
T

T
0
2 kt
f (t ) sin(
)dt
T
k  0,1,2,3,...
k  1,2,3,...
2 k
k 
T
2
 
T
Domínios
f(t)
0
T
t
tempo ou
espaço
ak
0
bk
0
 
2
T
w
freqüencia
w
Coeficientes de funções pares e ímpares
1
0.8
0.6
0.4
0.2
0
-0.2
0
0.2
0.4
0.6
0.8
-0.4
-0.6
-0.8
-1
cos
cos
sin
f-ímpar
ak = 0
f-par
bk = 0
sin
1
Periodicidade da Série de Fourier
f(t)
0
t
T

 2 k

 2 k

f (t  T )  a0  2  ak cos
(t  T )   bk sin
(t  T )    f (t )
 T

 T

k 1 

f(t)
0
T
t
revisão
Números complexos
eixo
imagnário
y
q
x
eixo
real
•
•
•
•
x é a parte real
y é a parte imaginária
A é a magnitude
q é a fase
z  x  iy  A(cosq  i sin q )
i  1
revisão
Operação básicas com complexos
( x1  iy1 )  ( x2  iy2 )  ( x1  x2 )  i( y1  y2 )
a( x  iy )  ax  iay
i 2  1
( x1  iy1 )(x2  iy2 )  ( x1 x2  i 2 y1 y2 )  i( x2 y1  x1 y2 )  ( x1 x2  y1 y2 )  i( x2 y1  x1 y2 )
2
2
2
2
( x  iy)(x  iy)  ( x  y )  i( xy  xy)  x  y
x  iy1 x2  iy2   1 x  iy x  iy 
x1  iy1
 1
x2  iy2 x2  iy2  x22  y22 1 1 2 2
x2  iy2
eiq  cosq  i sin q
revisão
Derivada de eit
d it
e  i  e i t
dt
d
cos t  i sin t    sin t  i cos t
dt
1
 i ( sin t  cos t )
i
1
i i
 2 
i
i
i
1
 i(i sin t  cost )
C.Q.D.
Outras propriedades úteis
eiq  cosq  i sin q
i
ei  1
-1
e
i

2
i
1
revisão
Outras propriedades úteis (2)
e iq  cosq  i sin q
eiq  cosq  i sin q
iq
cosq  (e  e
1
2
revisão
iq
)
cost  12 (eit  eit )
i
-1
t
1
t
-i
o cosseno
corresponde a
média de
dois
harmônicos de
freqüências
w e -w
Outras propriedades úteis (2)
revisão
e iq  cosq  i sin q
eiq  cosq  i sin q
1

i
i
i

 i
2
1
i
sin q  21i (eiq  eiq )  2i (eiq  eiq )
t
i
-1
t
1
-i
o seno também
corresponde a
dois harmônicos:
w e -w
Outras propriedades úteis (3)
z1  A1eiq1  A1 (cosq1  i sin q1 )
z2  A2eiq2  A2 (cosq2  i sin q2 )
z1 z2  A1 A2e
i (q1 q 2 )
z1 A1 i (q1 q 2 )

e
z2 A2
revisão
revisão
Amplitude e fase de complexos
Dado um valor:
z  A(cosq  i sin q )  x  iy
A2  x 2  y 2  zz
A sin q
-A
Amplitude
q
A cos q
A
y
tan q 
x
Fase
Série de Fourier com números complexos
eiq  e iq
cosq 
2
eiq  e iq
sin q 
2i

 2kt 
 2kt  
f (t )  a0  2  ak cos
  bn sin
 
 T 
 T 
k 1 

2kt
  i 2kt
i
 b
T
f (t )  a0    ak  e
 e T   k

k 1 

 i

2kt
i
 i 2Tkt

T 
e
e




1

i

bk  i 2Tkt 
bk  i 2Tkt 

f (t )  a0     ak  e
  ak  e

i 
i 

k 1  


2kt
2kt
i
i


T
T

f (t )  F0    Fk e
 F k e

k 1 

i
i

 i
2
1
i

F0  a0 , Fk  ak  ibk , Fk  an  ibn
Fk  Fk
f (t ) 
i (
1 T
Fk   f (t )e
T 0

F e
k  
2kt
)
T
i
2kt
T
k
dt k  1,2,3,...
Escrevendo em complexos
2kt
2kt
f (t )  a0  2 (ak cos
 bk sin
)   Fk e
T
T
k 1
k  


 2 kt 
i

T


Fk  ak  ibk
1 T
2kt
1 T
2kt
ak   f (t ) cos(
)dt , bk   f (t ) sin(
)dt
0
0
T
T
T
T
e
i (
2kt
)
T
2kt
2kt
 cos(
)  i sin(
)
T
T
1
Fk   f (t )e
T 0
T
k  0,1,2,3,...
i (
2kt
)
T
dt k  0,1,2,3,...
Serie de Fourier de Sinais Discretos
Sinal discreto
f (t )
fr
0
1
2
3
t
4
5
6
r
N-1
t  rt
T  N t
 fo , f1, f 2 ,, f r ,, f N 2 , f N 1,
t
f (t ) cos(
2kt
)
T
0
t
1 2 3 4 5
tr  rt
N
t
T  N t
T
1
ak 
T

T
0
2kt
f (t ) cos(
)dt
T
1 N 1
2 kr
ak   f r cos(
)
N r 0
N
1 N 1
 2krt 

f k cos
t

Nt r 0
 Nt 
...
1 N 1
 2 kr 
bk   f k sin

N r 0
 N 
1 N 1
2 kr
ak   f r cos(
)
N r 0
N
 c00
 a0 
 c
 a 
 1   1  10
   N 



c( N 1) 0
a N 1 
 s00
 b0 
 s
 b 
1
 1    10
   N 



b
 s( N 1) 0
 N 1 
c01
c11

c( N 1)1
s01
s11

s( N 1)1
1 N 1
 2 kr 
bk   f k sin

N r 0
 N 
c0 ( N 1)   f 0 

c1( N 1)   f1 


  




 c( N 1)( N 1)   f N 1 

s0 ( N 1)   f 0 

s1( N 1)   f1 


  




 s( N 1)( N 1)   f N 1 

onde:
2 kr
ckr  cos(
)
N
onde:
2 kr
skr  sin(
)
N
N 1
1
Fk  ak  ibk   f s e
N s 0
 E00
 F0 
 E
 F 
1
 1    10
   N 



F
 E( N 1) 0
 N 1 
N 1
f k   Fr e
i(
E01
E11

E( N 1)1
i (
2ks
)
N
E0( N 1)   f 0 

E1( N 1)   f1 


  




 E( N 1)( N 1)   f N 1 

onde:
Ekr  e
i
2 kr
N
2kr
)
N
r 0
 f 0   E '00
 f   E'
10
 1 
    

 
 f N 1   E '( N 1) 0
E '01
E '11

E '( N 1)1
E '0 ( N 1)   F0 

E '1( N 1)   F1 


  




 E '( N 1)( N 1)   FN 1 

onde:
E 'kr  e
i
2 kr
N
Inversa da inversa
N 1
f k   Fr e
i(
2 kr
)
N
1 N 1 i (
Fr   f s e
N s 0
onde:
r 0
fk 
1
N
N 1

r 0
i(
Fr e
2kr
)
N
N 1 N 1
  f se
i (

N 1  1 N 1

 N
r 0 

1

N



N 1 N 1
  f se
s 0 r 0
N 1 i 2r ( k  s )
N
N 1
 f e
s 0
2rs  2kr
) i(
)
N e N
s 0
2 rs
2 kr
) i(
)
N e N
r 0 s 0
1
N
 f se
i (
s
r 0
2 r s
)
N
Qual o valor?
i (
2 rs
2 kr
) i(
)
N e N

2 r ( k  s )
N 1 i
N
e


r 0
Se s=k
r
2

(
k

s
)

N 1  i
e N 

r 0 
N 1 i 2r ( k  s )
N
e
r 0



 1  q  q 2    q N 1 q  e
N 1
 1  1  1    1  N
r 0
Se s ≠ k é a soma de uma PG de N termos e razão q.
N
Mas
2 ( k  s )
i


N
i 2 ( k  s )
N
q  e
1
 e


q N 1
Som a
q 1
1 1
Som a
0
q 1
i
2 ( k  s )
N
N 1
f k   Fr e
i(
2 kr
)
N
1 N 1 i (
Fr   f s e
N s 0
onde:
r 0
fk 
1
N
N 1
i(
 Fr e
2kr
)
N
r 0
N 1 N 1
 
r 0 s 0
1
N
i (
f se

 
r 0  N

 f se
i (
2rs  2kr
) i(
)
N e N
s 0
2 rs
2 kr
) i(
)
N e N

1
N



N 1 N 1
  f se
 f e
s
r 0
i (
2 rs
2 kr
) i(
)
N e N

s 0 r 0
N 1 i 2r ( k  s )
N
N 1
s 0
N 1  1 N 1
2 r s
)
N
Qual o valor?
1

fk N  fk
N
C.Q.D.
 i ( 2Nk ) 
e
?

k 0 

N 1
imaginário
e
1
 iq
e
q
i (
2k
)
N
2k
2k
 cos
 i sin
N
N
real
N=3
N=4
N=5
N=6
Transformada Discreta
f (t )  sin(2 10t )
1.5
1
0.5
f a  200Hz
0
0
0.2
0.4
0.6
0.8
1
1.2
-0.5
N  256
-1
-1.5
1
t 
 0.005sec
fa
T  0.005  256  1.28 sec
T - não é o período do sinal!
N
T  N  t 
fa
sT
f s  sin( 2 10 )
N
1.4
Transformada Discreta de Fourier
sT
f s  sin( 2 10 )
N
2ks
N 1

i
(
)
1
N
Fk   f s e
N s 0
k 1
1.5
1
0.5
0
0
0.2
0.4
0.6
0.8
1
1.2
1.4
-0.5
-1
-1.5
ampl
0.5
1
f   0.7813 /sec
T
2
 
 4.91 rad /sec
T
10.15625,
0.46776
0.4
0.3
0.2
0.1
0
0
20
40
60
todas as feqüências computadas são multiplas destas
80
100
Outro exemplo
f3( t ) := 10 cos( 2  t ) 6 sin( 10  t ) .8 cos( 40  t )
20
15
10
5
0
-5
-10
-15
-20
Transformada
fk
20
15
10
N 1
f k   Fr e
5
0
-5 0
0.2
0.4
0.6
0.8
1
1.2
1.4
-10
i(
2 kr
)
N
r 0
-15
-20
2 k s
)
N
4
3
2
1
0
0
20
20.31, 0.35
1
Fk   f s e
N s 0
i (
5
4.69, 2.41
N 1
0.78, 4.52
ampl
40
60
80
100
120
Eixo de freqüência
Tutorial com o Excel
http://www.me.psu.edu/me82/Learning/FFT/FFT.html
Discrete Cosine Transformation (DCT)
(k ) N 1
 (2s  1)k 
Ck 
f s cos


N s 0
 2N

( k )
 (2s  1)k 
fs  
Cr cos

N
 2N

k 0
N 1
1
(k )  
 2
k 0
k 0
 (2s  1)k 
cos

 2N

1
0.8
0.6
0.4
0.2
0
-0.2 1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
-0.4
-0.6
-0.8
-1
cos(  2 )  sen( )
o cosseno pode substituir o seno
31
Transformada de Fourier

F ( w)   f ( x)e
i 2wx


f ( x)   F ( w)e

i 2wx
dx
dw
Exemplo 1: Função caixa (box)
a
f(x)
 0 se x   b 2

f ( x)  a se x  [ b 2, b 2]
 0 se x  b 2

x
b

F ( w)   f ( x)e
i 2wx

a

e i 2wx
 i 2w

b/2
i 2wx

a
e
dx
dx
b / 2


a
iwb
iwb

e

e
b / 2
 i 2w
a
a eiwb  e iwb

sin(wb )

w
w
2i
sin(wb)
F ( w)  ab
wb

b/2

Transformada da função box
a
sin(wb)
F ( w)  ab
wb
f(x)
x
b
sin(bw)
F ( w)  ab
bw
ab F(w) 
sinc(bw)
-3/b -2/b -1/b 0
1/b
2/b 3/b w
Distribuição normal: Gaussiana
gaus( x ) := e
Gaus( x)  
1
2
e
x2
 2
2
2
(  x )
Exemplo 2: Gaussiana
|| F(w) ||
f(x)
0.1 8
0.1 8
0.1 3
0.1 3
0.08
0.08
0.03
0.03
w
-0.02
x
-0.02

1 
x2
 2
1
f ( x) 
e 2
 2

F ( w)  e
w2
2 1 2 
  
Transformada da Gaussiana
 1
 2 
F ( w)   
e 2 e i 2wx dx


  2

x2

 1
 2 
 
e 2 cos(2wx)  i sin(2wx)dx


  2

x2



1
 2
e
x2

2 2
cos( 2wx )dx

 1
 2 
1
2
  2 
e
 
2
 2

w2
e
2 2 x 2
Exemplo 3: Delta de Dirac
f(x)
 0 se x   b 2

 ( x)  lim1 / b se x  [ b 2, b 2]
b 0
 0 se x  b 2

1/b
-b/2 b/2
x

1
b / 2  b / 2
 b b
f ( x)dx  lim
f ( ),    , 
 f ( x) ( x)dx  lim
b 0  b
b 0
b
 2 2
b / 2

b/2

 f ( x) ( x)dx  f (0)

Delta de Dirac de Gaussianas
 ( x)  lim
 0
1

e
2
x 2
 2

9e
4e
x 2

1 2
3
 
x 2

1 2
2
 
1e

x 2
 
1
1
2
Transformada do Delta de Dirac
f(x)

F ( w)    ( x)e i 2wx dx  e0  1
(x)

x
|| F(w) ||
1
w
Transformada do cosseno
1.5
cos(w t )

F ( w) 
1
i 2wx


cos(
w
x
e
dx


0.5
0
x
-0.5
-1

  cos(w x)cos(2wx)  i sin(2wx)dx

-1.5
w


 0 se w  2
  cos(w x) cos(2wx)dx  
w

 se w 
2

Exemplo 4: Cosseno
1.5
cos(w t )
|| F(w) ||
 (w  w )
1
 (w  w )
0.5
0
x
-0.5
w
w
w
-1
-1.5
1
w
w 
F ( w)   ( w  )   ( w  )
2
2
2 
Exemplo 5: Sequência de impulsos
f(x)
-2b-1b
1b 2b3b
|| F(w) ||
x
-2/b -1/b
f(x)
-2b -1b
1/b 2/b w
|| F(w) ||
1b 2b 3b
x
-2/b -1/b
1/b 2/b
w
Pares importantes
Propriedades da transformada
convolução
Convolução

h( x)  f  g   f (u) g ( x  u)du

t 
h( x ) 
 g (t  x) f ( x)dt
t  
n 1
hi   g ( k i ) f i
k 0
Ilustação da convolução
t 
h( x ) 
g
(
t

x
)
f
(
x
)
dt

t  
Ilustração da convolução
t 
h( x ) 
g
(
t

x
)
f
(
x
)
dt

t  
An undersampled signal
sin(28t), SR = 8.5 Hz
2
1.5
1
0.5
0
-0.5
-1
-1.5
-2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
http://lcni.uoregon.edu/fft/fft.ppt
Amostragem e Reconstrução
Observando os domínio do
espaço e das freqüências
Sinal original
domínio do espaço
domínio das freqüências
Amostragem
domínio do espaço
produto
domínio das freqüências
convolução
Sinal discretizado
domínio do espaço
domínio das freqüências
Reconstrução
domínio do espaço
convolução
domínio das freqüências
produto
Retorno ao sinal original
domínio do espaço
domínio das freqüências
Sinal original com mais altas freqüências
domínio do espaço
domínio das freqüências
Mesma taxa de amostragem
domínio do espaço
produto
domínio das freqüências
convolução
Sinal amostrado
domínio do espaço
domínio das freqüências
Não temos como reconstruir sem introduzir artefatos!
Teorema de Nyquist
Para que um sinal de banda limitada (i.e. aqueles cuja a
transformada resultam em zero para freqüências f > B) seja
reconstruido plenamente ele precisa ser amostrado numa
freqüência f >= 2B.
Um sinal amostrado na freqüência (f=2B) é dito amostrado
por Nyquist e f=2B é a freqüência de Nyquist.
Não há perda de informação nos sinais amostrados na
freqüência de Nyquist, e não adicionamos nenhuma
informação se amostrarmos numa freqüência maior.
Aliasing
• Esta mistura de espectros é chamada
de aliasing.
• Existem duas maneiras de lidarmos
com aliasing.
– Passar um filtro passa-baixa no sinal.
– Aumentar a freqüência de amostragem.
Alias
Texture errors