Cyfrowe przetwarzanie sygnałów Transformaty ortogonalne (05) Sławomir Kulesza Wykład fakultatywny dla studentów III r. spec. Informatyka ogólna Rok akademicki 2012/2013 Transformaty skończone
Każde przekształcenie skończonego w sensie czasu trwania sygnału z dyskretnym czasem na sygnał o tej samej długości zależny od innej wielkości nazywamy transformatą.
Transformata mapuje sygnał z dziedziny czasu na przeciwdziedzinę (np. częstości).
Transformata odwrotna mapuje sygnał z przeciwdziedziny z powrotem na dziedzinę czasu. Para transformat
Niech x[n] bÄ™dzie sygnaÅ‚em z dyskretnym czasem (o dÅ‚ugoÅ›ci N), zaÅ› X[k] niech bÄ™dzie N-punktowym ciÄ…giem współczynników jego transformaty, wówczas prostÄ… transformatÄ™: N -1 X [k ]= x[n]¨"[k , n] " n=0 nazywamy równaniem analizy sygnaÅ‚u Para transformat
Analogicznie, transformatÄ™ odwrotnÄ…: N -1 1 x [n]= X [k ] ¨[k , n] " N n=0 okreÅ›la siÄ™ mianem równania syntezy sygnaÅ‚u.
WystÄ™pujÄ…cy w obu transformatach sygnaÅ‚ ¨[k,n] nazywany jest bazÄ… transformaty. Transformaty ortogonalne
SpoÅ›ród licznych transformat skoÅ„czonych, wyróżnionÄ… grupÄ™ stanowiÄ… transformaty ortogonalne speÅ‚niajÄ…ce warunek: N -1 1 1Ô!l=k ¨[k ,n]¨"[l , n]= " { N 0Ô!l`"k n=0
Transformaty ortogonalne zbudowane są zatem w oparciu o ortogonalne sygnały bazowe Zachowanie energii
Transformaty ortogonalne zachowują energię sygnału: N -1 N -1 N -1 1 #"x[n]#"2= x[n] x"[n]= #"X [k ]#"2 " " " N n=0 n=0 n=0 Jest to tzw. równość Parsevala Dyskretna transformata Fouriera
N-punktowa dyskretna transformata Fouriera (Discrete Fourier Transform DFT) jest zdefiniowana jako: N -1 X [k ]= x[n]e- j2 Ä„ kn/ N , k=0,1 ,... N -1 " n=0
Gdzie sygnaÅ‚ bazowy zespolonym ciÄ…giem wykÅ‚adniczym: j2 Ä„ k n/ N ¨[k , n]=e Ortogonalność sygnałów bazowych
Sprawdzmy ortogonalność sygnałów bazowych DFT: N -1 N -1 1 1 j 2 Ä„(k-l)n/ N ¨[k , n]¨"[l , n]= e " " N N n=0 n=0
Podstawmy: N -1 N -1 j 2 Ą(k-l)n/ N S = e = un " " N -1 n=0 n=0 Ortogonalność sygnałów bazowych
Suma szeregu wynosi: N S =1-u N -1 1-u
Po podstawieniu: j 2 Ä„(k-l) 1-e 1Ô!l=k +r $! S = = N -1 j 2 Ä„(k-l)/ N { 0Ô!l`"k 1-e Dyskretna Transformata Fouriera
PodstawiajÄ…c: wN=e- j 2 Ä„/ N
DFT można zapisać jako: N -1 X [k ]= x[n]wkn , k=0,1 ,... , N -1 " N n=0
Transformata odwrotna iDFT ma postać: N -1 1 x [n]= X [k ]w-kn , k=0,1 ,... , N -1 " N N k=0 Szybka Transformata Fouriera
Aby ograniczyć złożoność obliczeniową DFT opracowano algorytmy rzędu N(log2N), które określane są mianem szybkiej transformaty Fouriera (Fast Fourier Transform FFT).
FFT jest identyczna z DFT, tyle że prowadzi do wyniku w krótszym czasie, zwłaszcza gdy N=2k. Związki między DTFT a DFT
DTFT sygnaÅ‚u z dyskretnym czasem jest dana jako: N -1 " j É X (e )= x[n]e- j É n= x[n]e- j É n " " n=0 n=0
PróbkujÄ…c widmo DTFT w równoodlegÅ‚ych czÄ™stoÅ›ciach: 2 Ä„ k Ék= , k=0,1 ,... , N -1 N ZwiÄ…zki miÄ™dzy DTFT a DFT
PróbkowanÄ… DTFT można zapisać jako: N -1 j É X (e )#"É = x[n]e- j 2Ä„ k n/ N " k n=0
Przez porównanie widać, że N-punktowa DFT X[k] jest ciÄ…giem próbek transformaty DTFT X(ejÉ) zebranych w N-równooldlegÅ‚ych punktach widma Ék. Zero-padding
Jeśli chcemy obliczyć transformatę DTFT na gęstej siatce M-punktów dla sygnału N- punktowego, możemy ten sygnał uzupełnić (M-N)-zerami (zero padding): x [n] x [n]=[ x ,0,0,0,0,0] p
Wówczas: N -1 M -1 j Ék X (e )= x[n]e- j 2 Ä„ k n/ M= x [n]e- j 2 Ä„ kn/ M " " p n=0 n=0 Zero-padding KoÅ‚owe przesuniÄ™cie sygnaÅ‚u
Ponieważ własności DFT wykorzystują przesuwanie sygnału w dziedzinie i przeciwdziedzinie, należy zdefiniować te operacje.
Jeśli wyjściowy sygnał x[n] jest N-punktowy (0d"nd"N-1), to jego przesunięta kopia nie może wyjść poza ten zakres. Wykorzystuje się w tym celu operację modulo, definiując przesunięcie kołowe (circular shift). Kołowe przesunięcie sygnału Kołowe przesunięcie sygnału
Zauważmy przy tym, że: xs[n]=x[(n-n0)N ]=x[(n-N +n0)N ]
Tak więc przesunięcie w prawo o n0-próbek jest tożsame przesunięciu w lewo o (N-n0)- próbek. Kołowe przesunięcie sygnału Kołowe zawinięcie sygnału Splot kołowy
Przypomnijmy, że splot dwóch N-punktowych sygnałów x[n] oraz h[n] ma postać: N -1 yL[n]=x"h= x[m]h[n-m], 0d"nd"2N-2 " m=0
Aby jednak zachować długość ciągu wynikowego, musimy operację splotu zdefiniować wykorzystując operację kołowego przesunięcia i odbicia sygnału. Splot kołowy
Splot kołowy zdefiniowany jest jako: N -1 yc[n]= x[n]h[(n-m)N ]=x "h " m=0
Splot kołowy jest zawsze ciągiem N- punktowym. Obliczanie splotu kołowego Obliczanie splotu kołowego
Metoda macierzowa Obliczanie splotu liniowego przy pomocy splotu kołowego Filtracja sygnałów
Mając wydajne algorytmy obliczania DFT Fast Fourier Transform (FFT) możemy szybko liczyć transformaty dowolnych sygnałów i transformaty odwrotne.
Każdy sygnał czasu dyskretnego można przedstawić jako sumę składowych sprzężonych kołowo: symetrycznej xcs[n] oraz antysymetrycznej xca[n]: x [n]=xcs[n]+ xca[n] 1 xcs[n]= ( x[n]+ x"[(-n)N ]) 2 1 xca[n]= ( x[n]ax"[(-n)N ]) 2 Sygnały parzyste i nieparzyste
N-punktowy sygnał rzeczywisty czasu dyskretnego rozkłada się według powyższego wzoru na dwie składowe rzeczywiste: parzystą (zespoloną symetryczną) oraz nieparzystą (zespoloną antysymetryczną). Symetrie geometryczne
N-punktowy sygnał x[n] jest symetryczny, gdy: x [n]=x[ N -1-n]
N-punktowy sygnał x[n] jest antysymetryczny, gdy: x [n]=-x[ N -1-n] Symetrie geometryczne Związki DFT z symetriami
W ogólności, DFT jest sygnału z dyskretnym czasem jest sygnałem zespolonym postaci: X [k ]= X [k ]= X [k ] ! ! gdzie poszczególne składowe liczy się ze wzorów: " X [k ]=1 ( X [k ]+ X [k ]) ! 2 1 " X [k ]= ( X [k ]- X [k ]) ! 2 Związki DFT z symetriami
W ogólności, DFT jest sygnału z dyskretnym czasem jest sygnałem zespolonym postaci: X [k ]= X [k ]= X [k ] ! ! gdzie poszczególne składowe liczy się ze wzorów: " X [k ]=1 ( X [k ]+ X [k ]) ! 2 1 " X [k ]= ( X [k ]- X [k ]) ! 2 Symetrie DFT dla sygnałów zespolonych Symetrie DFT dla sygnałów rzeczywistych Własności DFT Nadmiarowość DFT
Pamiętamy, że N-punktowa DFT sygnału rzeczywistego jest sygnałem zespolonym spełniającym warunek symetrii: " X [k ]= X [(-k)N ]
Dla parzystego N, próbki X[0] oraz X[(N-2)/2] są rzeczywiste, zaś pozostałe (N-2)-próbki są zespolone, jednak tylko połowa z nich jest różna od reszty. Nadmiarowość DFT
Dla nieparzystego N, X[0] jest próbką rzeczywistą, a pozostałe (N-1) zespolone, jednak tylko połowa z nich jest odmienna od reszty dzięki symetrycznemu sprzężeniu.
Świadczy to o nadmiarowości sygnału (redundancy). Przedłużanie sygnału
4 możliwe schematy przedłużania sygnału:
WS whole-sample symmetry
WA whole-sample antisymmetry
HS half-sample symmetry
HA half-sample antisymmetry
Po przedłużeniu obu końców sygnału dostajemy 16 możliwych schematów przedłużania, z czego 8 symetrycznych stanowi bazę DCT, zaś 8 antysymetrycznych bazę DST Przedłużanie sygnału
Jeśli sygnał wyjściowy ma postać: x[n] = [a,b,c,d], to jego okresowy, przedłużony odpowiednik ma postać:
xWSWS[n] = [a,b,c,d,c,b] typ I
xHSHS[n] = [a,b,c,d,d,c,b,a] typ II Przedłużanie sygnału DCT typ II
Standardem używanym do kodowania JPEG, MPEG oraz H.261 jest transformata kosinusowa bazująca na przedłużaniu typu II.
Ta transformata jest nazywana także parzystą, symetryczną DCT. DCT typu II
Niech dany jest N-punktowy sygnał x[n].
Najpierw sygnaÅ‚ ten jest uzupeÅ‚niany zerami: x [n]Ô!0d"nd"N -1 xzp[n]= { 0Ô! N d"nd"2N-1
NastÄ™pnie tworzy siÄ™ sygnaÅ‚ symetryczny typu II y[n]: y[n]=xzp[n]+xzp[2N-1-n]=& x[n]Ô!0d"nd"N -1 & { x [2N-1-n]Ô! N d"nd"2N-1 DCT typu II
Powstały sygnał spełnia warunek symetrii: y [n]= y[2N-1-n]
2N-punktowa transformata DFT tego sygnału ma postać: 2N-1 Y [k ]= y[n]wkn , k=0,1 ,... , 2N-1 " 2N n=0 DCT typu II
Po przekształceniach: N -1 Ą k (2n+1) Y [k ]=w-k /2 2x [n]cos ,& " 2N ( ) 2N n=0 0d"kd"2N-1
N-punktowa transformata DCT typu II powstaje przez wybranie pierwszych N-próbek powyższej transformaty DFT i przemnożenie ich przez w2Nk/2 DCT typu II
DCT typu II ma ostatecznie postać: N -1 Ą k (2n+1) X [k ]= 2 x[n]cos , 0d"kd"N -1 " DCT ( ) 2N n=0
Zauważmy, że dla rzeczywistego x[n], XDCT jest także rzeczywiste. iDCT
Odwrotna transformata kosinusowa N- punktowego DCT ma postać: N -1 Ą k (2n+1) 1 x [n]= ą[k ] X [k ]cos ,0d"nd"N -1 " DCT ( ) N 2N k=0
N-punktowa transformata Haara ma postać: X =H Å"x[n] Haar N
O ile współczynniki transformat DFT oraz DCT były powiązane ze specyficznymi częstościami, transformata Haara (i inne transformaty falkowe) odzwierciedla różne położenia i skale składowych sygnału. Własności transformaty Haara
Ortogonalność: 1 t H-1= H N N N wynika stąd łatwość liczenia transformaty odwrotnej: 1 t x [n]= H X N Haar N Własności transformaty Haara
Zachowanie energii sygnału: N -1 N -1 1 #"x[n]#"2= #"X [k ]#"2 " " Haar N n=0 k=0 Kompaktowość transformat