kurse:efcomputergrafik:kw43

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 Zeitbereich abgespeichert.
  • Bei der zweiten Möglichkeit haben wir einen Funktionswert im Frequenzbereich 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.

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}

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.

Aufgabe 3

Analysiere folgendes Programm. Was ist neu?

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")

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.
  • kurse/efcomputergrafik/kw43.txt
  • Last modified: 2019/10/29 15:15
  • by Marcel Metzler