Lehrstuhl für
Multimediakommunikation und Signalverarbeitung
Prof. Dr.-Ing. André Kaup

Entwicklung einer optimierten 2D-FFT Bibliothek

Betreuer:M.Sc. Nils Genser (Raum 01.178)
Hochschullehrer:Prof. Dr.-Ing. André Kaup
Student:Appel, Simon
Info:

Ein wichtiges Arbeitsgebiet der digitalen Signalverarbeitung beschäftigt sich mit der Rekonstruktion von Bild- und Videosignalen. Hierbei ist es oft notwendig ein digitales Signal in seine Frequenzanteile zu zerlegen und diese anschließend weiter zu analysieren und zu verarbeiten. Üblicherweise wird zur effizienten Berechnung der diskreten Fourier-Transformation (DFT) das Verfahren der schnellen Fourier-Transformation (FFT) verwendet.

In der Bildverarbeitung ist besonders die 2D-FFT von Interesse, da die Eingangssignale zweidimensional vorliegen. Für ein reelwertiges 2D-Eingangssignal erhält man den entsprechenden Real- und Imaginärteil, wie in Abbildung 1 gezeigt.

 

 

 

 

 

 

 

 

Wie man erkennt, lässt sich hier eine DFT-Symmetrieeigenschaft erkennen. So können jeweils zwei Quadranten des Spektrums durch Spiegelung am Mittelpunkt erzeugt werden. Diese Symmetrie lässt sich ausnutzen, um nur einen Teil des Spektrums berechnen zu müssen und die fehlenden Werte im Anschluss zu kopieren. Somit sinkt der erforderliche Rechenaufwand stark.

Ein weiterer Punkt ist die Skalierung der FFT. Hier gibt es mehrere Möglichkeiten, die FFT bzw. die inverse FFT zu formulieren. Da je nach Verarbeitung der Werte eine andere Skalierung von Vorteil sein kann, soll diese voreinstellbar bzw. vollständig deaktivierbar sein.

Intuitive FFT-Implementierungen arbeiten als rekursiver Algorithmus. Das heißt, die Eingangswerte werden rekursiv in Listen zerlegt, die FFT berechnet und die Listen wieder zusammengefügt ("Butterfly"-Prinzip). Eine rekursive Zerlegung ist zwar intuitiv, jedoch auch rechenaufwendig, da für jeden Funktionsaufruf der Kontext gesichert und Methodeneintrittscode gespeichert werden muss. Durch eine
entsprechende, nicht-rekursive bzw. iterative FFT-Umsetzung wird eine bessere Performanz erreicht.

In dieser Bachelorarbeit soll eine effiziente C/C++ Implementierung der FFT umgesetzt werden, welche sowohl die zweidimensionalen Symmetrieeigenschaften, als auch eine variable Skalierung erlaubt. Für eine schnellere Berechnung soll die FFT als nicht-rekursiver Algorithmus implementiert werden. Hierfür wird als Vorlage eine nicht-rekursive 1D-FFT zur Verfügung gestellt, welche entsprechend den Anforderungen angepasst werden soll.

Typ:Bachelorarbeit
Status:Laufend