kurse:efcomputergrafik:kw43 [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====KW43: Fourier====
Stell dir vor, du hast ein Signal $x(t)=\hat{x}\cdot \sin(\omega t + \varphi) +x_0$. Du musst dieses Signal in eine Datei abspeichern. Was machst du?
===Zwei Möglichkeiten===
Ein Möglichkeit besteht darin, zu verschiedenen Zeitpunkunten $t_i$ mit einem konstanten Zeitabstand $\Delta t = t_{i}-t_{_i-1}$ (äquidistant) den Funktionswert zu bestimmen (messen) und abzuspeichern. Machen wir dazu ein Rechenbeispiel:
  * $\Delta t = 2.27\mu s$, dass entspricht einer Abtastfrequenz $f_s=44.1kHz$, d.h. CD Qualität.
  * Jeder Wert $x(t)$ wird 16 Bit gewandelt, d.h. braucht 2 Byte Speicherplatz pro Messwert.
  * Das Signal (Lied) dauert 3 Minuten und 40 Sekunden.
Alles zusammen ergibt $$44100\frac{\text{Sample}}{sec.}\cdot \frac{2\;Byte}{\text{Sample}}\cdot 220\sec.=19.4 MByte$$

Eine andere Möglichkeit wäre:
  * Amplitude abspeichern ergibt 2 Byte
  * Phasenlange abspeichern ergibt 2 Byte
  * Kreisfrequenz abspeichern ergibt 2 Byte
  * Startzeitpunkt und Endzeitpunkt abspeichern ergibt 2 mal 2 Byte, also 4 Byte
Alles zusammen ergibt dies $$10\; Byte$$ Speicherplatz und dies bei mit einer viel höheren Auflösung, da eine Sinusfunktion eine beliebige Auflösung hat!

Die zweite Möglichkeit braucht viel weniger Speicherplatz und ist daher zu bevorzugen.

===Bemerkungen===
  * Bei der ersten Möglichkeit haben wir Funktionswerte im **Zeit**bereich abgespeichert.
  * Bei der zweiten Möglichkeit haben wir einen Funktionswert im **Frequenz**bereich abgespeichert.

===2-$\pi$-periodische Funktionen===
Mit den Basisfunktionen $\sin$ und $\cos$ lässt sich ein reelles trigonometrisches Polynom $T_n$ definieren. Es gilt: $$T_n(t)=\frac{a_0}{2}+\sum_{k=1}^n \left(a_k\cos(kt)+b_k\sin(kt) \right) $$
Mit den reellen Fourierkoeffizienten $$a_k=\frac{1}{\pi}\int_0^{2\pi}T_n(t)cos(kt)dt, \qquad k=0,1,...,n $$
und $$b_k=\frac{1}{\pi}\int_0^{2\pi}T_n(t)sin(kt)dt, \qquad k=1,2,...,n $$
Es lässt sich zeigen, dass mit einem trigonometrischen Polynom $T_n(t)$ eine stetig differenzierbare $2\pi$-periodische Funktion $f(t)$ beliebig genau approximiert werden kann. D.h. $$T_n(t)\approx f(t)$$ für den Grenzübergang gilt sogar Gleichheit, d.h. $$ f(t)=\lim_{n\to\infty}T_n(t)$$
Eine Begründung für die obigen Aussagen liefern die Orthogonalitätsbeziehungen.

====Orthogonalitätsbeziehungen====
Es sei $m,n\in\mathbb{Z}$ und $a\in\mathbb{R}$, dann gelten folgende Orthogonalitätsbeziehungen:
\begin{eqnarray}
(1)&\qquad \frac{1}{2\pi}\int_a^{a+2\pi}\exp(imt)\exp(-int)dt & = &\begin{cases} 0, \quad \text{falls }m\neq n\\ 1, \quad \text{falls } m=n\end{cases} \\
(2)&\qquad \frac{1}{\pi}\int_a^{a+2\pi}\sin(mt)\sin(nt)dt & = &\begin{cases} 0, \quad \text{falls }m\neq n\\ 1, \quad \text{falls } m=n\end{cases} \\
(3)&\qquad \frac{1}{\pi}\int_a^{a+2\pi}\cos(mt)\cos(nt)dt & = &\begin{cases} 0, \quad \text{falls }m\neq n\\ 1, \quad \text{falls } m=n \\ 2, \quad \text{falls } m=n=0 \end{cases} \\
(4)&\qquad \int_a^{a+2\pi}\cos(mt)\sin(nt)dt & = & 0
\end{eqnarray}

**Aufgabe 1**

Beweise min. eine dieser vier Aussagen. Dafür brauchst du die Additionstheoreme.
\begin{eqnarray}
(1) & \qquad\sin(x+y) & = & \sin(x)\cos(y)+\sin(y)\cos(x) \\
(2) & \qquad\sin(x-y) & = & \sin(x)\cos(y)-\sin(y)\cos(x) \\
(3) & \qquad\cos(x+y) & = & \cos(x)\cos(y)-\sin(x)\sin(y) \\
(4) & \qquad\cos(x-y) & = & \cos(x)\cos(y)+\sin(x)\sin(y)
\end{eqnarray}
====Fourier Koeffizienten====
Mit den Orthogonalitätsbeziehungen lässt sich die Korrektheit der obigen Definition der Fourierkoeffizienten $a_k$ und $b_k$ beweisen. Wir setzen ein und rechnen nach.
\begin{eqnarray}
a_k & = & \frac{1}{\pi}\int_0^{2\pi}T_n(t)\cos(kt)dt \\
    & = & \frac{1}{\pi}\int_0^{2\pi}\left( \frac{a_0}{2}+\sum_{m=1}^n \left(a_m\cos(mt)+b_m\sin(mt) \right) \right)\cos(kt)dt\\
    & & …\\
    & = &a_k
\end{eqnarray}
und
\begin{eqnarray}
b_k & = & \frac{1}{\pi}\int_0^{2\pi}T_n(t)\sin(kt)dt \\
    & = & \frac{1}{\pi}\int_0^{2\pi}\left( \frac{a_0}{2}+\sum_{m=1}^n \left(a_m\cos(mt)+b_m\sin(mt) \right) \right)\sin(kt)dt\\
    & & …\\
    & = &b_k
\end{eqnarray}

**Aufgabe 2**

Rechne $a_k$ vollständig durch.
====Anwendung Datenkomprimierung von Linienzeichnungen====

**Aufgabe 3**

Analysiere folgendes Programm. Was ist neu?
<code python Fourier.py>
from gpanel import *
import math
import cmath
import time

def onMousePressed(x, y):
    move(x,y)

def onMouseDragged(x, y):
    draw(x,y)
    Koordinaten.append([x,y])
    f.write(str(x) + "," + str(y) + "\n")

makeGPanel(0,100,0,100,
           mousePressed = onMousePressed, 
           mouseDragged = onMouseDragged)

nameD=time.strftime("Daten_%Y_%m_%d_%H_%M_%S.txt")
nameF=time.strftime("Fourier_%Y_%m_%d_%H_%M_%S.txt")
Koordinaten=[]
f=open(nameD,"w")
fopen=1;

while fopen==1:
    key = getKeyCodeWait()
    if key==27:
       f.close()
       fopen=0
print("Daten erfasst")
</code>

===Konventionen und Anpassungen für die Datenkomprimierung===
Sei $f$ eine 1-periodische Funktion, welche unser Bild beschreibt.
$$ f: \; \left[0,1\right] \; \rightarrow \; \mathbb{C}, \quad t \;\mapsto z=x+i\cdot y $$
D.h. wir fassen die Bildpunkte $P(x|y)$ als Punkte in der komplexen Zahlenebene auf. Der erste Punkt $P_0(x_0|y_0)$ ist $f(0)=x_0+i\cdot y_0$, der letzte Punkt $P_n(x_n|y_n)$ ist $f(1)=x_n+i\cdot y_n$, dazwischen wird linear interpoliert, d.h. mit $$\Delta t = \frac{1}{n-1}$$ folgt dann für ein $k\in \{1,2,3,...,n\}$, dass $P_k(x_k|y_k)$ als $f((k-1)\Delta t)=x_k+i\cdot y_k$ interpretiert wird.

Wir wollen unser $f$ welches wir nun anhand von einer endlichen Anzahl von Punkten kennen mit einem komplexen Fourierreihe approximieren, darstellen. 
$$f(t)=\sum_{k=-\infty}^{\infty}c_k \cdot e^{ikt}  \approx \sum_{k=-n}^{n}c_k \cdot e^{ikt}$$
Für den komplexen Fourierkoeffizienten $c_k$ gilt:
$$c_k=\frac{1}{2\pi}\int_0^{2\pi} f(t)\cdot e^{-ikt}dt $$
Aufgrund unserer Anpassung, d.h. weil $f$ 1-periodisch ist ergibt sich folgende Vereinfachung.
$$c_k=\int_0^1 f(t)\cdot e^{-2\pi ikt}dt $$
Das Integral berechnen wir über eine "Riemann"-Summe, d.h.
$$c_k=\int_0^1 f(t)\cdot e^{-ikt}dt \approx \sum_{j=0}^{n-1}f(j\cdot \Delta t)\cdot e^{-2\pi ikj\cdot \Delta t}\cdot \Delta t$$

**Aufgabe 4**

Ergänze das obige Programm so, dass
  * die komplexen Fourierkoeffizienten $c_k$ berechnet werden und
  * diese in einem File abgespeichert werden. Pro Zeile soll nur ein Fourierkoeffizient stehen.