Differences

This shows you the differences between two versions of the page.

--- kurse:efcomputergrafik:kw43 [2019/10/23 12:40] – [Anwendung Datenkomprimierung Linienzeichnungen] Marcel Metzler
+++ kurse:efcomputergrafik:kw43 [2019/10/29 14:15] (current) – [Anwendung Datenkomprimierung von Linienzeichnungen] Marcel Metzler
@@ Line 1: / Line 1: @@
+====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.