Numerisches Programmieren (IN0019) 7. Fourier ... · Kontinuierliche Fourier-Transformation C-Vektorräume Fourier Transformation Fourier-Reihe FFT Faltung IN0019 - Numerisches Programmieren

Numerisches Programmieren(IN0019)

Frank R. Schmidt

Winter Semester 2016/2017

7. Fourier Transformation

C-Vektorräume Fourier Transformation Fourier-Reihe FFT Faltung

C-Vektorräume


Komplexe Zahlen


IN0019 - Numerisches Programmieren 7. Fourier Transformation – 4 / 34

Die komplexen Zahlen C sind die reellen Zahlen R, die um die imaginäre Einheiti adjungiert sind, wobei i eine Nullstelle von x2 ` 1 ist.

Jede komplexe Zahl z P C lässt sich als z “ a ` ib darstellen, wobei wir mita “: ℜpzq den Realteil und mit b “: ℑpzq den Imaginärteil bezeichnen.Mit z :“ a ´ ib bezeichnen wir die komplex konjugierte Zahl und mit|z| :“ ?

a2 ` b2 den Betrag von z.

Die komplexen Zahlen sind wie die reellen Zahlen ein Körper zusammen mit denfolgenden Operationen:

pa ` ibq ` pc ` idq “pa ` cq ` ipb ` dqpa ` ibq ¨ pc ` diq “pac ´ bdq ` ipad ` bcq

´pa ` ibq “páq ` ip´bqpa ` ibq´1 “ a ´ ib

a2 ` b2

Eulersche Formel



Da C ein Körper ist, kann man zu jedem z P C die Reihe

exppzq “8ÿ

n“0

zn

n!

berechnen und das Ergebnis in seinen Real- und Imaginärteil zerlegen.

Zusammen mit der Eulerschen Formel

exppibq “8ÿ

n“0

p´1qn b2n

p2nq! ` i8ÿ

n“0

p´1qn b2n`1

p2n ` 1q! “ cospbq ` i sinpbq

erhalten wir

exppa ` ibq “ exppaq ¨ pcospbq ` i sinpbqq

Polarkoordinaten



Jede komplexe Zahl z P C besitzt eine Polardarstellung

z “ |z| ¨ pcospϕq ` i sinpϕqq “ |z| ¨ exppiϕqDamit erhalten wir

z “ |z| ¨ exppíϕqz1 ¨ z2 “ |z1| |z2| ¨ exppipϕ1 ` ϕ2qq

zz “ |z|2zn “ |z|n ¨ exppipnϕqq

Insbesondere sind die n-ten Einheitswurzeln, d.h. die n Lösungen von xn “ 1:

1 “ ω0n, ω

1n, . . . , ω

n´1n ωn :“ exp

î2π

n

˙

Einheitswurzeln (Beispiele)



ℜ

ℑ

ω03

ω13

ω23

ℜ

ℑ

ω05

ω15

ω25

ω35

ω45

ℜ

ℑ

ω07

ω17

ω27

ω37

ω47

ω57

ω67

ℜ

ℑ

ω02ω1

2 ℜ

ℑ

ω04

ω14

ω24

ω34

ℜ

ℑ

ω08

ω18

ω28

ω38

ω48

ω58

ω68

ω78

C-Vektorraum



Da C ein Körper ist, können wir C-Vektorräume W betrachten.

Jeder C-Vektorraum W ist automatisch auch ein R-Vektorraum, denn jedeC-Skalarmultiplikation λ ¨ w definiert auch eine R-Skalarmultiplikation (Wähleλ P R Ă C). Allerdings gilt

dimRW “ 2 ¨ dimCW

Interessanterweise kann man aber auch jeden R-Vektorraum V in einenC-Vektorraum W verwandeln:

V “ spanRpv1, . . . , vnq ñ W :“ spanCpv1, . . . , vnq.mit dimCW “ dimR V .

Man schreibt hierfür üblicherweise W :“ V b C.

Skalarprodukt



Für C-Vektorräume W erfüllt ein Skalarprodukt x¨, ÿ : W ˆ W Ñ C folgendeEigenschaften:

xαx ` βy, zy “α xx, zy ` β xy, zy (Semilinear in der ersten Komponente)xx, αy ` βzy “α xx, yy ` β xx, zy (Linear in der zweiten Komponente)

xx, yy “xy, xy (Hermitesch)xx, xy PR`

0

xx, xy “ 0 ô x “ 0 (Positiv-Definit)

Ist V “ spanpv1, . . . , vnq ein R-Vektorraum mit aij “ xvi, vjy so wird dadurch einSkalarprodukt auf W :“ V b C definiert.

Sei w1 “ řni“1 αivi und w2 “ řn

i“1 βivi, dann ist dieses W -Skalarprodukt

xw1, w2y “ xα, Aβy “ αJAβ

Fourier Transformation


Polynom-Interpolation



Im Folgenden betrachten wir das Interpolationsproblem für ein Polynom

ppzq “n´1ÿ

j“0

ajzj P Πn´1

mit den n Einheitswurzeln als Stützstellen:

ppωjnq “ yj j “ 0, . . . , n ´ 1

Das führt zum linearen Gleichungssystem mit der Vandermonde-Matrix V :

V ¨ a “y V P Cnˆn, a, y P Cn

mit vjk “ ωj¨kn für j, k “ 0, . . . , n ´ 1.

Diskrete Fourier Transformation



Bezeichnen wir mit V ˚ :“ V J die adjungierte Matrix bzgl. V , so gilt

pV ˚V qjk “n´1ÿ

m“0

vjmvmk “n´1ÿ

m“0

ω´pjmq`mkn “

n´1ÿ

m“0

´ωk´jn

¯m “ n ¨ Ijk

Das heißt wir haben V ´1 “ 1nV

˚ und es gilt

ak “ 1

n

n´1ÿ

j“0

yj ωjkn yk “

n´1ÿ

j“0

ajωjkn

Die erste Operation ist die Diskrete Fourier Transformation (DFT) und diezweite ist die inverse DFT (IDFT).

In der Literatur werden manchmal andere Faktoren benutzt, d.h. 1 und 1n sind

vertauscht oder in beiden Fällen wird 1?n

benutzt.

Fourier-Reihe


Trigonometrische Orthonormalbasis



Die Name der Fourier-Transformation hat seinen Ursprung in der Fourier-Reihe,die auf folgendem Skalarprodukt beruht:

xf, gy :“ 1

π

ż π

´πfpxqgpxqdx .

Dieses Skalarprodukt kann zur Approximation von Funktionen benutzt werden. Manprojiziert dann eine Funktion f auf den Vektorraum, der von endlich vielenFunktionen fi aufgespannt ist.

Man kann zeigen, dass bzgl. des obigen Skalarprodukts die folgenden Funktioneneine Orthonormalbasis bilden:

"1?2, cospxq, sinpxq, . . . , cospnxq, sinpnxq

*

Damit erhalten wir also fpxq « a0 ` řnk“1 ak cospkxq ` bk sinpkxq.

Koeffizienten der Fourier-Reihe



Die Koeffizienten dieser Fourier-Reihe

fnpxq “ a0 `nÿ

k“1

ak cospkxq ` bk sinpkxq

erhält man, indem man f mit den Basisfunktionen multipliziert.

Die Fourier-Koeffizienten sind also

xfpxq, cospkxqy “ak xfpxq, sinpkxqy “bk xfpxq, 1y “a02

Diese Darstellung wird benutzt, um hohe Frequenzen in Signalen zu entfernen. Dasist der wesentliche Unterschied zwischen WAV- und MP3-Dateien.

Setzt man ck :“ ak ` ibk, so kann man die Notationen vereinfachen. Dazuverwandelt man den R-Vektorraum C0pr´π, πs,Rq in den C-VektorraumC0pr´π, πs,Cq.

Komplexe Orthonormalbasis



Betrachten wir nun das Skalarprodukt

xf, gy :“ 1

2π

ż π

´πfpxqgpxqdx,

so bilden folgenden Funktionen eine Orthonormalbasis:

texppínxq, . . . , exppíxq, 1, exppixq, . . . , exppinxquDamit erhalten wir also

fpxq «nÿ

k“ń

ak exppikxq

mit

ak “ xf, exppikxqy “ 1

2π

ż π

´πfpxq exppíkxqdx .

Kontinuierliche Fourier-Transformation



Motiviert durch diese Beobachtung, definiert man die kontinuierliche, zyklischeFourier-Transformation als

fpαq “ 1

2π

ż π

´πfpxqeíαx dx

Benutzt man die Trapezregel als Diskretisierung, so erhält man mit der Notationxj “ ´π ` 2π

n j und ωn “ exp`2πn i

˘gerade

f

ˆ2π

nj

˙« 1

2π

n´1ÿ

j“0

fpxjqωjn ¨ 2π

n

Dies entspricht genau der diskreten Fourier-Transformation.

FFT


Motivation der FFT



Die IDFT

yk “n´1ÿ

j“0

ajωjkn

lässt sich als Matrix-Vektor-Multiplikation darstellen, d.h. sie kann in Opn2qberechnet werden. Das Ziel der schnellen Fourier-Transformation (FFT)besteht darin, diese Berechnung in Opn logpnqq durchzuführen.

Idee Zerlege die Summen geschickt in zwei Teilsummen halber Länge, aus denensich die ursprünglichen Summen leicht gewinnen lassen.

Voraussetzung Es wird also in jedem Schritt benötigt, dass n gerade ist, d.h.insgesamt n “ 2N .

Zerlegung der IDFT



Es sei n “ 2m. Dann gilt:

yk “2m´1ÿ

j“0

ajωjkn

“m´1ÿ

j“0

a2jω2jkn `

m´1ÿ

j“0

a2j`1ωp2j`1qkn

“m´1ÿ

j“0

a2jωjkm ` ωk

n ¨m´1ÿ

j“0

a2j`1ωjkm

Die erste Summe ist die m-elementige IDFT der geraden Koeffizienten.

Die zweite Summe ist die m-elementige IDFT der ungeraden Koeffizienten.

Rekursive IDFT



Angenommen, dass n “ 2m und wir haben die IDFT bzgl. m berechnet:

a2k “m´1ÿ

j“0

a2jωjkm a2k`1 “

m´1ÿ

j“0

a2j`1ωjkm

Dann gilt für k ă m

yk “m´1ÿ

j“0

a2jωjkm ` ωk

n ¨m´1ÿ

j“0

a2j`1ωjkm “a2k ` ωk

n ¨ a2k`1

yk`m “m´1ÿ

j“0

a2jωjpk`mqm ` ωk`m

n ¨m´1ÿ

j“0

a2pk`mq`1ωjpk`mqm “a2k ´ ωk

n ¨ a2k`1

Diese Operation wird auch Butterfly-Schritt genannt.Falls die IDFT für die beiden m-elementigen Vektoren berechnet wurde, benötigenwir lediglich Opnq für den Kombinationsschritt.

Laufzeit IFFT



Ohne Rekursion benötigen wir jeweils n2 Operationen (` sowie ¨).Wird die Rekursion einmal benutzt, ist die Anzahl der Operationen

2ń

2

¯2 ` n “ 1

2n2 ` n

Wird die Rekursion k-mal benutzt, ist die Anzahl der Operationen

2k´ n

2k

¯2 ` k ¨ n “ 1

2kn2 ` k ¨ n

Ist n “ 2N , ist die Anzahl der Operationen (bei N Rekursionen)

2N´ n

2N

¯2 ` N ¨ n “ n ` logpnq ¨ n

Aufrufabfolge der Rekursion



pa0, a1, a2, a3, a4, a5, a6, a7q

pa0, a2, a4, a6q

pa0, a4q

a0 a4

pa2, a6q

a2 a6

pa1, a3, a5, a7q

pa1, a5q

a1 a5

pa3, a7q

a3 a7

Id 0 4 2 6 1 5 3 7Binär 000 100 010 110 001 101 011 111

Bit-Reversal 000 001 010 011 100 101 110 111Dezimal 0 1 2 3 4 5 6 7

Iterative IFFT



Um die rekursive IFFT-Berechnung in eine iterative IFFT-Berechnung zuverwandeln, zerlegen wir die Berechnung in drei Phasen.

In der ersten Phase (Sortierung) permutieren wir die Einträge ai derart, dass siebzgl. ihres Bit-Reversals πpiq sortiert sind.

In der zweiten Phase (Kombinationsphase) werden genau logpnqKombinationsschritte durchgeführt.

In der dritten Phase (Inverse Sortierung) permutieren wir die Einträge ai, so dasssie wieder bzgl. i sortiert sind.

Da beim Bit-Reversal lediglich paarweise die Einträge ausgetauscht werden, ist dieerste Phase mit der dritten Phase identisch.

Das Bit-Reversal kann in Linearzeit berechnet werden. Hierfür iterieren wir überalle Einträge i und führen einen Austausch zwischen i und πpiq durch genau wennπpiq ą i.

Faltung


Polynom-Multiplikation



Man kann die diskrete Fourier-Transformation auch benutzen, um zwei Polynomeeffizient zu multiplizieren. Sei hierzu

ppxq “nÿ

k“0

akxk qpxq “

nÿ

k“0

bkxk

Dann gilt für das Produkt r :“ p ¨ q P Π2n gerade

rpxq “2nÿ

k“0

ckxk ck “

kÿ

j“0

ajbk´j

Diese Berechnung benötigt Opn2q Operationen.

Allerdings wird r eindeutig durch 2n verschiedene Stützstellen definiert. Das istdie Kernidee, um das Produkt mit Hilfe der FFT zu berechnen.

Polynom-Multiplikation mittels FFT



Es seien die Koeffizientenvektoren a, b P Rn gegeben, die die Polynome p und qbeschreiben. Nun möchte man den Koeffizientenvektor c P R2n finden, der dasPolynom r “ p ¨ q beschreibt.

1 // Füllen mit Nullen2 for (j=0; j<n; j++) a[n+j] = 0; b[n+j] = 0; 3 // IFFT4 A = ifft(a); B = ifft(b);5 // Punktweise Multiplikation6 for (j=0; j<2*n; j++) 7 C[j] = A[j]*B[j]; // Komplexe Multiplikation8 9 // FFT

10 c = fft(C);

Die Anzahl der Flops ist

2n ` 4n ¨ logp2nq ` 2n ` 2n ¨ logp2nq “ Opn ¨ logpnqq

Faltung



Ähnlich wie die Fourier-Transformation hat auch diese Operation einkontinuierliches Analogon, die sogenannte Faltung. Hierzu seien zwei stetigeFunktionen f, g : r´π, πs Ñ R gegeben, die periodisch fortgesetzt werden, d.h.

fpx ` 2kπq “fpxq gpx ` 2kπq “gpxq @k P Z

Wir schreiben die Faltung von f und g als

f ˚ g : r´π, πs ÑR

x ÞÑż π

´πfpyqgpx ´ yqdy

und es gilt f ˚ g “ g ˚ f .

Faltung (Beispiel)



x

y

* x

y

= x

y

x

y

* x

y

= x

y

Sei g : R Ñ R eine positive C8-Funktion mitşgpxqdx “ 1, so ist f ˚ g eine

C8-Approximation von f . Die Operation nennt man auch Glättung.

Fourier-Transformation der Faltung



Für die Fourier-Transformation der Faltung erhalten wir

zf ˚ gpαq “ 1

2π

ż π

´πf ˚ gpxqeíαx dx

“ 1

2π

ż π

´π

ż π

´πfpyqgpx ´ yqeíαyeíαpxýq dx dy

“ 1

2π

ż π

´π

ż π

´πfpyqgpxqeíαyeíαx dx dy

“ 1

2π

„ż π

´πgpxqeíαx dx

„ż π

´πfpyqeíαy dy

“2πfpαq ¨ gpαqInsgesamt verhält sich die Fourier-Transformation der Faltung ähnlich zurdiskreten Fourier-Transformation der Polynom-Multiplikation.

Verallgemeinerungen



Das Konzept der Fourier-Transformation und der Faltung kann man auch für höhereDimension verallgemeinern. Z.B. gilt für die Dimension d “ 2 und Funktionenf, g : r´π, πs ˆ r´π, πs Ñ R gerade

f ˚ g : r´π, πs ˆ r´π, πs ÑR

px1, x2q ÞÑż π

´π

ż π

´πfpy1, y2qgpx1 ´ y1, x2 ´ y2qdy1 dy2

sowie

fpα1, α2q “ 1

p2πq2ż π

´π

ż π

´πfpy1, y2qe´xα,yy dy1 dy2

und es gilt

zf ˚ gpαq “ p2πq2 ¨ fpαq ¨ gpαq

Bildglättung (Beispiel)



*

=

Laufzeit: 1.94 Sekunden (ohne FFT)Laufzeit: 0.17 Sekunden (mit FFT)

Suche in Bildern



I : Ω Ñ R3 P : Ω0 Ñ R3 P : Ω0 Ñ R3

Wir suchen nach dem Pixelort x P Ω Ă R2 im Bild I : Ω Ñ R3, in dem sich dasZentrum des Bildausschnitts P : Ω0 Ñ R3 befindet, d.h. wir sind auf der Suchenach dem Minimum von:

Epxq “ż

Ω0

rP pyq ´ Ipx ` yqs2 dy “ż

Ω0

“P pyq ´ Ipx ´ yq‰2

dy

“ż

Ω0

P pyq2 ´ 2P pyqIpx ´ yq ` Ipx ´ yq2 dy“ const` “´2pP ˚ Iq ` I2 ˚ 1

‰ pxq

Bildsuche mittels FFT



Eingabe: Ø

I P und P

FFT:

P ˚ I I2 ˚ 1

Ausgabe:

2 ¨ P ˚ I ´ I2 ˚ 1 Ergebnis

Documents

Numerisches Programmieren (IN0019) 7. Fourier ... · Kontinuierliche Fourier-Transformation C-Vektorräume Fourier Transformation Fourier-Reihe FFT Faltung IN0019 - Numerisches Programmieren