ANALIZA CZ
STOTLIWOŚCIOWA
SYGNAA
ÓW DYSKRETNYCH
Spis treści
1. Zależności pomiędzy analizą częstotliwościową sygnałów
analogowych i dyskretnych
2. Definicja i własności dyskretnej transformacji Fouriera
3. Analiza częstotliwościowa dyskretnych obrazów
1
Dyskretna transformacja Fouriera
ang. Discrete Fourier Transform DFT
2
1.5
1
0.5
0
1 2 3 4 5 6 7 8
czas
8
6
4
2
0
1 2 3 4 5 6 7 8
częstotliwość
1
0.5
0
-0.5
-1
1 2 3 4 5 6 7 8
2
częstotliwość
sygnał
widmo fazowe
widmo amplitudowe
Baron Jean Baptiste Joseph
Trochę historii
FOURIER (1768-1830)
Z wyróżnieniem ukończył szkolę wojskową w
Auxerre.
Został nauczycielem Ecole Normal a potem
Politechniki w Paryżu.
Napoleon mianował go zarządcą Dolnego Egiptu w
wyniku ekspedycji z 1798 roku.
Po powrocie do Francji został prefektem w Grenoble.
Baronem został w 1809 roku. Ostatecznie w 1816
roku został sekretarzem Akademii Nauk a następnie
jej członkiem w 1817.
W okresie od 1808 roku do 1825 roku napisał 21
tomowy Opis Egiptu.
Równaniem ciepła zainteresował się w 1807 roku. W opublikowanej w 1822 roku
pracy pokazał jak szereg zbudowany z sinusów i kosinusów można wykorzystać do
analizy przewodnictwa ciepła w ciałach stałych. Nad szeregami
trygonometrycznymi pracował do końca życia, rozszerzając tę problematykę na
3
transformację całkową.
Geneza transformacji sygnału
jednowymiarowego
Widmo impulsu analogowego
T
s" (n)
j f t
%5ńa ( f ) =
a
+"s (t)e-2Ą dt
0
0 1 2 3 4 5 6 7
gdzie T jest czasem trwania sygnału.
s" (n) = sa (n"t)
Wprowadz
my dyskretyzację
gdzie:
n = 01,..., N - 1
,
N - ilość próbek
gęstość dyskretyzacji "t = T / ( N - 1)
Wartość całki oznaczonej aproksymujemy  metodą prostokątów
N -1
j f n"t
%5ńa ( f ) H" "t
"s (n) e-2Ą
"
n=0
4
Dyskretyzacja w dziedzinie częstotliwości
Dyskretne widmo będziemy wyznaczać w punktach
%5ń( f )
fk = k "f
Aby były rozłożone równomiernie i obejmowały
zarówno dodatnie jak i ujemne wartości
k "{- (N -1) / 2, - (N - 3) / 2, ..., (N - 3) / 2, (N -1) / 2}
0
kHz
-1 0 1
Położenie skrajnych punktów musi uwzględniać założenia tw. Shanona
i wynikać z powyższych założeń. Otrzymamy zatem dwa warunki
N -1
f( N -1) / 2 = < fm = f / 2
p
2"tN
11
a z nich wynika
"f ==
N - 1
N "t T + "t
f( N -1)/2 = "f
2
5
Prototyp DFT
Przybliżone wartości widma analogowego
N -1
j f n"t
%5ńa ( f ) H" "t
"s (n) e-2Ą
"
n=0
k
fk = k "f =
obliczamy dla wybranych częstotliwości
N"t
2Ą
N -1
otrzymując - j kn
N
%5ńa ( fk ) H" %5ń" (k) = "t
"s (n) e
"
n=0
Wprowadzając oznaczenie
2Ą
- j
N
w = e = cos(2Ą / N) - j sin(2Ą / N)
otrzymujemy wartości widma dyskretnego
N -1
kn
$
s (k ) = "t s (n) w
"
""
n = 0
6
Odwrotna dyskretna transformacja Fouriera
ang. Inverse Discrete Fourier Transform IDFT
Z widma ciągłego odtwarzamy sygnał analogowy
fm
j f t
sa (t) =
a
+"%5ń ( f )e2Ą df
- fm
Aproksymując wartość całki  metodą prostokątów spodziewamy się otrzymać
dyskretne wartości sygnału
$
s" (n) = "f
"s (k) w-kn
"
k
gdzie
2Ą
- j
N
w = e
7
Wzajemna jednoznaczność transformacji
DFT oraz IDFT
N -1
kn
$
$ s" (n) = "f
s (k ) = "t s (n) w
"s (k) w-kn
"
"
""
k
n = 0
N -1
1 �#
-kn
$
s" (n) = =
ź#
"s (k) w-kn = 1 "w "tś#"s (m) wkm ś#
N "tk " N "tk �#m=0 " #
N -1
1 Im(wk(m-n))
k (m-n)
= = s" (n)
"s (m)"w
"
6
N
w8
m=0 k
5 7
w8 w8
0 dla m `" n
ż#
k (m-n)
8 0
= 4
�#
"w
w8 = w8 =1
w8
k
�#N dla m = n
Re(wk(m-n))
Ą
3
- j
w8
4
w8 = e
2Ą Ą
- j - j
2
N 2
8
wN = e w8 = e
Przykład
Jakie jest widmo dyskretne sygnału
s" = [1 0 - 1 0 1 0]T
jeśli gęstość próbkowania wynosi
"t = 10-3[s]?
Sygnał posiada N=6 próbek. Spodziewamy się, że reprezentuje drgania
kosinusoidalne o okresie
� = 4 "t = 4 �"10-3[s]
czyli o częstotliwości
f = 250[Hz].
9
Zakończenie przykładu
Numery próbek n "{0,1, 2, 3, 4, 5}
Dyskretne widmo ma numerację
k "{- 2,5; -1,5; - 0,5; 0,5;1,5; 2,5}
Gęstość dyskretyzacji w dziedzinie częstotliwości
1 1
"f = = = 500 / 3[Hz]
N "t 6 �"10-3
Zatem widmo dyskretne jest obliczane dla częstotliwości [Hz]
{-1250 / 3, - 250, - 250 / 3, 250 / 3, 250,1250 / 3}
N -1
kn
W oparciu o wzór
%5ń" (k ) = "t s" (n)w
"
n = 0
Ą
gdzie - j
1 3
3
w = e = cos(Ą / 3) - j sin(Ą / 3) = - j
2 2
otrzymujemy
T
%5ń" =[0 3�"10-3 0 0 3�"10-3 0]
10
Macierzowy zapis rozwiązania przykładu
N�N
gdzie
%5ń = "tW s
W =[wkn]"C
Macierz współczynników
0
Ą# -2,5 -5 -7,5 -10 -12,5
ń#
ó#0 -1,5 -3 -4,5 -6 -7,5 Ą#
ó# Ą#
ó# -0,5 -1 -1,5 -2 -2,5
Ą#
0
kn =
[ ]
ó# Ą#
ó#0 0,5 1 1,5 2 2,5 Ą#
ó#0 1,5 3 4,5 6 7,5 Ą#
ó# Ą#
Ł#0 2,5 5 7,5 10 12,5 Ś#
Ą
- j
1 3
3
wyznacza obroty wektora
w6 = e = - j
2 2
k "{- 2,5; -1,5; - 0,5; 0,5;1,5; 2,5}
Numer wiersza
11
n "{0,1, 2, 3, 4, 5}
Numer kolumny
Koniec przykładu w zapisie macierzowym
Dla rozważanego przykładu macierz przekształcenia ma postać
Ą# ń#
3 j 1 3 1 3 3 j
+ - j j - - j +
ó#1 - Ą#
2 2 2 2 2 2 2 2
ó#1 Ą#
j -1 - j 1 j
ó# Ą#
ó# 3 j 1 3 1 3 3 j Ą#
+
ó#1 2 + 2 2 + 2 j j - + 2 j -
2 2 2Ą#
W =[wkn]=ó#
Ą#
3 j 1 3 1 3 3 j
ó#1 Ą#
- - j - j - - j - -
ó# Ą#
2 2 2 2 2 2 2 2
ó# Ą#
1 - j -1 j 1 - j
ó# Ą#
3 j
ó#1 - 3 j 1 + 3 j - j - 1 + 3 j Ą#
- -
Ł# 2 2 2 2 2 2 2 2 Ś#
i otrzymujemy
T
%5ń" = "t W s" = [0 3�"10-3 0 0 3�"10-3 0]
dla częstotliwości
T
f = [-1250 / 3, - 250, - 250 / 3, 250 / 3, 250,1250 / 3]
12
Okresowość widma DFT
N -1
kn
Otrzymaliśmy wzór
$
s" (k ) = "t s" (n) w
"
n = 0
2Ą
gdzie
- j
N
w = e = cos(2Ą / N) - j sin(2Ą / N)
N -1
czyli
%5ń" (k ) = "t s" (n)[cos (2Ąnk / N )- j sin (2Ąnk / N )]
"
n = 0
Funkcje trygonometryczne powodują, że widmo jest funkcją o okresie N, tzn.
$ $
s" (k + N ) = s" (k)
bo
N -1
%5ń" (k ) = "t s" (n)[cos (2Ąnk / N + 2Ąn)- j sin (2Ąnk / N + 2Ąn)]
"
n = 0
13
Racjonalizacja DFT
k = 0,1,2,..., N - 1
Przyjmujemy
Skoro f = k " f
k
T
[fk ]= [0,"f ,2"f ,...,(N -1)"f ] "!N
to
Wprowadzamy nową funkcję dyskretną
%5ń" (k)
%5ń(k) =
"t
Przy tych dwóch założeniach wzór
N -1
kn
$
s" (k ) = "t s (n) w
"
"
n = 0
przyjmie ostateczną postać dyskretnej transformacji Fouriera.
14
Definicja DFT oraz IDFT
N -1
kn
%5ń(k) =
Dyskretna transformacja Fouriera zdefiniowana jest wzorem "s(n)w
n=0
N -1
1
a odwrotna dyskretna transformacja Fouriera wzorem
$
s(n) =
"s(k) w-kn
N
k =0
$
Przekształcenie DFT można zapisać macierzowo
s = W s
N�N
gdzie
W =[wkn]"C
Elementy macierzy W powstają przez podniesienie do potęgi kn wartości zespolonej
2Ą
- j
N
w = e = cos(2Ą / N) - j sin(2Ą / N)
przy czym k jest numerem wiersza a n numerem kolumny. Numeracja rozpoczyna się
od zera bo k, n "{0,1,2,K, N -1}
-1
Macierz przekształcenia w odwrotnej dyskretnej transformacji Fouriera
s = W %5ń
ma postać
1 1
-1 * N�N
W = [w-kn]= W "C
N N
15
Własności DFT
1. Zależność pomiędzy widmem dyskretnym a widmem sygnału
analogowego
%5ń(k) "t H" %5ńa (k"f )
2. Ilość dyskretnych wartości widma jest równa ilości próbek
czasowych sygnału.
3. Gęstość dyskretyzacji widma
1
-1
"f == T + "t
()
N "t
gdzie
"t = T / ( N - 1)
16
Własności DFT
4. Szerokość widma:
Dla nieparzystej ilości próbek
N - 1 N - 1 (N - 1)2
f = f = = f =
N -1
max p
2
2"t N 2 N 2 T N
Dla otrzymujemy
N "
f f / 2
max p
Dla parzystej ilości próbek
f
1 N -1
p
fmax = f = ==
N
2
2 "t 2 2T
17
Własności DFT
5. Macierz W jest nieosobliwa i symetryczna, jej elementy są na ogół
zespolone a ich moduły są zawsze równe 1. Odwrotna do niej
-1
W =W" / N
as1(n) + bs2(n) �! a%5ń1(k) + b%5ń2(k)
6. Liniowość DFT, tzn.
bo
W(as1 + bs2)= aWs1 + bWs2
0
$
s(n - n0 ) �! s(k) wkn
7. Przesunięcie w dziedzinie czasu
N -n0 -1
N -1
0
bo
"s(n - n0) wkn = wkn "s(m) wkm
n=0 m=-n0
N -1
1
$ $
8. Modulacja s1(n) s2 (n) �!
"s (m) s2 (k - m)
1
N
m=0
9. Zachowanie energii czyli dyskretna postać twierdzenia Parsevala
N -1 N -1
2
2
18
%5ń(k)
"s (n) = 1 "
N
n=0 k =0
Graficzna prezentacja przykładu DFT
2
1.5
1
0.5
0
1 2 3 4 5 6 7 8
czas
8
6
4
2
0
1 2 3 4 5 6 7 8
częstotliwość
1
0.5
0
-0.5
-1
1 2 3 4 5 6 7 8
19
częstotliwość
sygnał
widmo fazowe
widmo amplitudowe
Prezentacja przykładu
,
Gęstość próbkowania wynosi "t = 0001 [s] . Jakie jest widmo
dyskretne sygnału
T
s =[2 1 0 1 2 1 0 1] ?
2Ą
Obliczamy
- j
1 j
8
w8 = e = cos(Ą / 4) - j sin(Ą / 4) = -
2 2
Podnoszą tę liczbę do potęgi całkowitej otrzymamy tylko jedną
z ośmiu możliwości przedstawionych na poniższym rysunku.
k
1 j
Im(w )
= -

2 2
Np. dla N=8
= - 1 j
-
2 2
1 j
+
= -
2 2
k
Re(w )
1 j
= +

2 2
20
Macierzowy zapis przykładu
,
Gęstość próbkowania wynosi "t = 0001 [s] . Jakie jest widmo
dyskretne sygnału
T
s =[2 1 0 1 2 1 0 1] ?
Udowodnimy, że sygnał zawiera składową stałą i drgania o okresie 4 [ms],
czyli o częstotliwości
f = 250[Hz]
1 j
= - 1 j = - 1 + j = 1 + j
= -
-

2 2
2 2 2 2 2 2
%5ń(0) s(0)
Ą# ń# Ą# ń#Ą# ń#
ó# Ą#ó# Ą#
%5ń(1)Ą# ó# �! �! ę! s(1)
ó# Ą# ó# Ą#ó# Ą#
ó# Ą# ó# Ą#ó# Ą#
%5ń(2) �! �! ę! �! �! ę! s(2)
ó# Ą# ó# Ą#ó# Ą#
ę! �! �!
ó#%5ń(3)Ą# ó# Ą#ó#s(3)Ą#
=
ó#%5ń(4)Ą# ó# �! �! �! �!Ą#ó#s(4)Ą#
ó# Ą# ó# Ą#ó# Ą#
�! �! ę!
ó#%5ń(5)Ą# ó# Ą#ó#s(5)Ą#
ó#%5ń(6)Ą# ó# ę! �! �! ę! �! �! Ą#ó#s(6)Ą#
ó# Ą# ó# Ą#ó# Ą#
ę! �! �!
ó# Ą#ó#
Ś# Ł# Ś#
Ł#%5ń(7)Ą# ó# Ś#Ł#s(7)Ą#
21
Rozwiązanie przykładu
Wyliczamy
T
%5ń = [8 0 4 0 0 0 4 0]
Próbkowanie częstotliwości
1
"f == 125[Hz]
N "t
Sygnał ma składową stałą i drgania oczęstotliwości
2 "f = 250[Hz]
Szerokość widma wynosi
fmax = f4 = 500 [Hz]
czyli jest równa częstotliwości Nyquista.
22
Dwuwymiarowa transformacja Fouriera jako
geneza dyskretnej transformacji obrazów
Widmo częstotliwościowe obrazu analogowego zdefiniowane jest wzorem
" "
x y
$
s( f , f ) = s(x, y) e-2Ą j ( f x+ f y)dx dy
x y
+" +"
-"-"
Odtwarzanie obrazu analogowego z jego widma częstotliwościowego
dokonywane jest przy pomocy wzoru
" "
x y
$
s(x, y) = s( f , f ) e2Ą j ( f x+ f y)df df
x y x y
+" +"
-"-"
Wzory te wykorzystamy do wyprowadzenia dyskretnej transformacji
sygnałów dwuwymiarowych, czyli 2-D DFT.
23
Geneza dyskretnej transformacji obrazów
Obliczając przybliżone wartości całek oznaczonych
" "
x y
$
s( f , f ) = s(x, y) e-2Ą j ( f x+ f y)dx dy
x y
+" +"
-"-"
" "
x y
$
s(x, y) = s( f , f ) e2Ą j ( f x+ f y)df df
x y x y
+" +"
-"-"
otrzymujemy
kxnx kyny
%5ń" (nx ,ny ) = "x"y
""s (nx ,ny ) wx wy
"
nx ny
-kxnx -kyny
s" (nx ,ny ) = "fx "f
y ""%5ń (kx ,ky ) wx wy
"
kx ky
gdzie
2Ą
2Ą
- j
- j
N
Nx y
wy = e
24
wx = e
Dyskretna transformacja sygnału
dwuwymiarowego
Przyjmujemy kx = 0,1,2,...,Nx -1 oraz ky = 0,1,2,...,N -1
y
i wprowadzamy nową funkcję dyskretną
%5ń" (kx, ky ) %5ń(kx"fx, ky"f )
y
%5ń(kx, ky ) = H"
"x"y "x"y
Przy tych dwóch założeniach otrzymujemy wzory:
- dyskretnej transformacji Fouriera obrazów
N -1
Nx -1
y
nxkx nyky
()
%5ń kx , ky = ()
" "s nx ,ny wx wy
nx =0 ny =0
- odwrotnej dyskretnej transformacji Fouriera obrazów
N -1
Nx -1
y
-nyky
-nxkx
()1 " "%5ń kx ,ky wx wy
s nx ,ny = ()
Nx N
kx =0 ky =0
y
25
Macierzowy zapis 2-D DFT
=
%5ń = WxsWy
s
%5ń Wx
Wy
gdzie
Nx �N
x y y
s = [s(nx, ny )]"!N �N %5ń = [%5ń(kx, ky )]"C
nxkx N �N nyk N �N
x x y y y
Wx = [wx ]"C
Wy =[wy ]"C
k , ny = 0,..., N -1
kx , nx = 0,..., Nx -1
y y
ny
numer kolumny
kx numer kolumny macierzy
k numer wiersza
nx numer wiersza macierzy
y
oraz Wy są macierzami symetrycznymi
Wx
26
Przykład 2-D DFT
27