Präsentation

Fast Fourier Transformation FFT

Michael Weiser 5HIB 2005/2006

Über Joseph Fourier

Joseph Fourier wurde am 21. März 1768 in Auxerre geboren und starb am 16. Mai 1830 in Paris. Er wurde Professor an der Ecole Polytechnique und war seit 1816 Mitglied der Academie des Sciences. Man sagte, dass „Fouriers Theorie analytique de la chaleur [Paris, 1822] ist die Bibel des mathematischen Physikers. Nicht nur werden hier die nach ihm benannten trigonometrischen Fourier‐Reihen und Integrale entwickelt, sondern es wird auch das allgemeine Problem der Randwertaufagben an dem Beispiel der Wärmeleitung vorbildlich durchgeführt“.

Fourier befaßte sich auch ausführlich mit der Fehlerauwertung physikalischer Messungen. Quelle: Armin Hermann Lexikon – Geschichte der Physik A-Z, Aulis-Verlag Deubner & Co

Fouriertransformation – Einführung Im Allgemeinen führen Transformatinen zu einer Vereinfachung der Problemlösung. Die Fouriertransformation hat sich zur Problemvereinfachung als wichtigstes mathematisches Werkzeug in wissenschaftlichen und industriellen Anwendungsgebieten als sehr effektiv erwisen.

Die Fourier-Transformation kommt in verschiedenen Gebieten zur Anwendung wie: ⇒ Biomedizin 

Untersuchung von Herzkranken Untersuchung von Magenerkrankungen 

⇒ Radartechnik Erfassung bewegter Ziele Doppler‐Messung 

⇒ Nachrichtentechnik Sprachverschlüsselung Video‐Bandbreitenkompression 

⇒ Signalverarbeitung angepasste Filter Spracherkennung 

Praktische-Anwendungsgebiete der FFT: ⇒ Bildrestauration ⇒ Kompressionsverfahren ⇒ Gesichterkennung ⇒ Untersuchung von Einschwingvorgängen 

 Folgender Flussdiagram demonstriert den allgemeinen Zusammenhang zwischen den konventionellen analytischen und den transformations-analytischen Methoden, am einfachen Beispiel, nämlich am Beispiel der logarithmieschen Transformation.  

Bild 1 : Zusammenhang zwischen der konventionellen Analysis und der Transformation-Analysis

Grundkonzept der Fouriertransformation Die Logarithmustransformation, die in Bild1 zu finden ist, wurde wohl aufgrund ihrer eindimensionalität leicht verstanden. Die Logarithmusfunktion transformiert nämlich einen einzählnen Wert X in einen einzählnen Wert log (X). Die Fouriertransformation kann man nicht in gleich einfacher Weise interpretieren, da wir hier mit Funktionen zu tun haben, deren Definitionsbereich sich von -_ bis +_ erstreckt. Wir müssen jetzt eine Funktion einer Variable, defieniert von -_ bis +_, in eine andere Funktion einer anderen Variable, definiert ebenfalls im Bereich von -_ bis +_, transformieren. Das Prinzip der Fourier-Transformation ist daher nichts anderes als ein beliebiges Signal als Summe von Sinusfunktionen unterschiedlicher Frequenz, Amplitude und Phase.

(Bild 2) Auf diesem Bild wird eine direkte Intrpretation der Fouriertransformation gezeigt. Die Hauptaufgabe der Fouriertransformation eines Signals (um neben dem mathematischen auch den physikalisch-technischen Aspekt der Fouriertransformation hervorzuheben, gebrauche ich die Begriffe Signal und Funktion als synonym) bestehtdaran, dass man das Signal in eine Summe von Sinusfunktionen unterschiedlicher Frequenzen zerlegt. Wenn aus diesen Sinusfunktionen durch Überlagerung das urspunliche Signal wiedergewonnen werden kann, dann hat man die Fouriertransformierte des Signals gefunden! Man stellt die Fouriertransformierte in einem Diagram dar, in welchem Amplituden, Phasen und Frequenzen der sinusförmigen Komponenten des Signals aufgetragen werden. Wir haben hier als Beispiel die Fourier-Transformierte eines einfachen Signals. (Bild2) Die Fourier-Transformierte besteht aus zwei sinusförmigen Signalen, die nach Überlagerung das ursprüngliche Signal wiedergeben.

Voraussetzungen für die FT: ⇒ Die Anzahl der Unstetigkeiten innerhalb einer Periode ist endlich. ⇒ Die Anzahl der Maxima und Minima innerhalb einer Periode ist endlich. ⇒ Die Funktion ist in jeder Periode integrierbar (d.h., die Fläche unter dem Betrag der Funktion

ist in jeder Periode endlich)

Definition der Fourier-Transformation Gegeben sei ein reelles oder komplexwertiges Signal x(t). Wir setzen zun¨achst nur voraus, daß x(t) st¨uckweise glatt und ¨uber (−∞,∞) absolut integrierbar ist, d. h., daß das Integral

konvergiert. Die Fourier-Transformierte von x(t) wird dann definiert durch

Dieser ¨Ubergang von der Zeitfunktion x(t) zu der Funktion X( jω) heißt Fourier-Transformation und wird symbolisch durch ausgedrückt.

Historischer Überblick über die schnelle Fouriertransformation Während einer Sitzung des Wissenschaftlischen Beratungskomitees des US-Päsidenren stellte Richard L. Garwin fest, dass John W. Tukey sich mit der Erstellung von Programmen für die Fouriertransformation beschäftigte. Garwin, der selbst für seine Forschungsarbeit hoffnungslos auf der Suche nach einer schnellen Methode zur Berechnung der Fouriertransformation war, fragte Tukey nach dessen Kenntnissen über Rechenverfahren für die Fouriertransformation. Tukey umriß für Garwin im wesentlichen das, was später zu dem berühmten Cooley-Tukey-Algorithmus führte. Gerwin ging zum Rechenzentrum des IBM-Forschungszentrums in Yorktown Heights, um das Verfahren programmieren zu lassen. James W. Cooley war ein relativ neuer Mitarbeiter im Stab des IBM-Forschungszentrums und wurde nach eigenem Bekunden mit der Bearbeitung der Aufgabe beauftragt, weil er der einzige war, der nichts wichtigeres zu tun hatte. Auf das Drängen von Garwin stellte Cooley schnell ein Computerprogramm auf und kehrte zu seiner eigenen Arbeit zurück, mit der Hoffnung, daß das Projekt erledigt sei und bald vergessen werden könnte. Da sich jedoch Nachfragen für Kopien des Programms und desse schriftlichen Dokumentation zu häufen begannen, wurde Cooley um eine Veröffentlicheung über das Programm gebeten. 1965 publizierten Colley und Tukey den jetzt weltberühmten Aufsatz „An Algorithm for the Machine Calculation of Complex Fourier Series” Ohne das Beharrungsvermögen von Garwin wäre die schnelle Fouriertransformation vielleicht heute noch relativ unbekannt geblieben.

Gesichtserkennung mit der 2-dimensionalen diskreten Fourier-Transformation Die Grundidee für die Gesichtererkennung mit Hilfe der Fourier-Transformation besteht darin, das Originalbild und das Vergleichsbild in den Frequenzbereich zu transformieren, um dort die Spektren der beiden Bilder einfacher vergleichen zu können. Bei der Fourier-Transformation handelt es sich um einen globalen Operator, also um einen Operator, der alle Pixel des Eingangsbilds benötigt, um ein Pixel des Ausgangsbilds zu berechnen. Die 1-dimensionale Fourier-Transformation wird bei der Verarbeitung 1-

dimensionaler kontinuierlicher oder diskreter Zeitsignale verwendet. Dabei werden die Zeitsignale aus dem Zeitbereich in den Frequenzbereich transformiert und als Frequenzspektrum dargestellt. Für die Verarbeitung von Bildern dagegen wird die 2- dimensionale diskrete Fourier-Transformation (DFT) verwendet, da Bilder digitale (diskrete) 2-dimensionale Ortssignale sind. Die Transformation erfolgt also vom Ortsbereich in den Frequenzbereich, der häufig auch als Ortsfrequenzbereich bezeichnet wird. Das folgende Verfahren der Gesichtserkennung wurde von Hagen Spies in seiner Masterarbeit vorgestellt: Jedes Gesicht kann durch die Fourier-Transformation in den Frequenzbereich transformiert werden.

Gesicht und seine Transformation in den Frequenzbereich: links: Originalbild, rechts: Spektrum des Bilds (Amplitudenspektrum). Ein erster wichtiger Punkt bei der Betrachtung der Frequenzspektren ist, daß der Großteil der Bildinformation in den niedrigen Frequenzen enthalten ist. Mit Hilfe der Varianz werden die Frequenzen berechnet, die Informationen über Unterschiede zwischen den Bildern enthalten. Diese Varianz wird sowohl für den Realteil, als auch für den Imaginärteil berechnet. Es stellt sich heraus, daß auch die Informationen über Bildunterschiede zum großen Teil in den Fourierkoeffizienten niedriger Ordnung enthalten sind. Diese Informationen sind letztendlich die relevanten Informationen für die Gesichtserkennung. Die Fourierkoeffizienten werden nun entsprechend ihres Informationsgehalts angeordnet und nur die ersten N Koeffizienten für die Gesichtserkennung verwendet. Die Anzahl N der Koeffizienten kann vom Benutzer gewählt werden, abhängig von der gewünschten Anwendung. Bei der Herleitung der DFT-Transformationsgleichungen wird eine periodische Funktion im Zeitbereich unterstellt. Dies läßt sich jedoch mit Hilfe der Systemtheorie begründen. Tastet man eine Funktion im Zeitbereich ab, so entsteht nach Shannon eine periodische Funktion im Frequenzbereich. Entwickelt man eine periodische Funktion in eine Fourierreihe, so entstehen die diskreten Fourierkoeffizienten im Frequenzbereich. Um dies noch einmal gegenüber zu stellen: Abtastung im Zeitbereich (also Diskretisierung) => Periodizität im Frequenzbereich Periodizität im Zeitbereich => Diskrete Koeffizienten im Frequenzbereich Bei der diskreten Fouriertransformation hat man, wie bei jedem numerischen Verfahren, das Problem, daß man eine Funktion nur mit einer bestimmten Anzahl von Stützstellen beschreiben bzw. speichern kann. Daher liegen bei der DFT auch im Spektralbereich diskrete Koeffizienten vor, zugleich ist das Spektrum periodisch. Mit den obigen Sätzen der Systemtheorie folgt zwingend,

daß dann die Zeitfunktion diskret (ist durch Abtastung erfüllt) und periodisch sein muß. In allen zuvor verwendeten Gleichungen wird für den Index der Folge im Zeitbereich der Buchstabe n, für den Index der Folge im Frequenzbereich der Buchstabe m verwendet. Dies allein ist natürlich etwas unbefriedigend, da für eine physikalische Interpretation auch physikalische Größen benötigt werden.

Die Diskrete Fourier-Transformation (DFT) Sie ist ein Spezial fall der kontinuierlichen Fourier Transformation.

⇒ Approximation der Fourier-Transformierten eines nicht-analytischen Signals ⇒ Berechnung auf einem digitalen Rechner: ⇒ Verarbeitung einer endlichen Anzahl von Abtastwerten ⇒ Diskretisierung der Frequenzvariablen

Berechnung der DFT mit Hilfe der schnellen Fourier-Transformation (Fast Fourier Transform – FFT, Cooley & Tukey, 1965)

Rechenaufwand bei der DFT o Auswertung an einer Frequenzstelle k : N Multiplikationen und N−1

Additionen o Auswertung an N Frequenzstellen: N × N Multiplikationen und N × (N−1)

Additionen o Verminderung des Rechenaufwands für

durch:

Signalflussdiagramm einer 8-Punkte-DFT, aufgespaltet in zwei 4-Punkte-DFTs

Signalflussdiagramm einer 8-Punkte-DFT, aufgespaltet in vier 2-Punkte-DFTs

Vollständige Zerlegung einer 8-Punkte-DFT

ine Zerlegungsebene besteht aus N/2 Butterfly- bzw. Schmetterlings-Graphen

echenaufwand ene zwei komplexwertige Multiplikationen und Additionen

E

R– Pro Zerlegungseb– Anzahl der Zerlegungsebenen entspricht dem Wert q, wobei N = 2q

Aufgrund der Identität

kann die Anzahl der Multiplikationen nochmals um den Faktor 2 reduziert werden • Vereinfachter Butterfly bzw. Schmetterlings-Graph

ie schnelle Diskrete-Fouriertransformation

r Rechneranwendung von ouriertransformationen ist die sogenannte "FFT", oder ausführlich Fast Fourier Transform, zu

hlt,

T ist e

equenzen anwendbar, deren Länge N iner Zweierpotenz entspricht

D Der wahrscheinlich bekannteste Begriff im Zusammenhang mit deFdeutsch also schnelle Fouriertransformation. Dieser Begriff ist allerdings etwas unscharf gewädenn es wird eigentlich keine Fouriertransformation, sondern eine diskrete Fouriertransformationdurchgeführt. Der FFT-Algorithmus ist keine eigenständige Transformation, vielmehr liefert er exakt das gleiche Ergebnis wie die DFT-Gleichungen, die zuvor besprochen wurden. Wenn also vom FFT-Algorithmus als ein "Näherungsverfahren" gesprochen wird, so bedeutet dies: die DFeine Näherung zur kontinuierlichen Fouriertransformation, also ist auch der FFT-Algorithmus einNäherung zur kontinuierlichen Fouriertransformation - dennoch ist das Ergebnis von FFT und DFT identisch, also keine weitere Näherung mehr. FFT-Algorithmus ist ausschließlich auf SignalseSie ermöglicht eine schnellere Auswertung der DFT

Komplexitätsvergleich DFT – FFT

o FFT benötigt für N=1024 Abtastwerte, ca. 99% weniger Rechenoperationen o Aufwand der DFT: X(n²)

Natürlich wird die Geschwindigkeitseinsparung nicht immer genauso stark sein, wie die obige Grafik zeigt. Dennoch wird deutlich, daß sich der Mehraufwand für die Implementierung einer FFT immer lohnt. Abtastwerte DFT FFT 8 64 12 32 1024 80 128 16384 448 256 65536 1024 512 262144 2304 1024 1048576 5120 2048 4194304 11264 4096 16777216 24576

Meßtechnische Probleme der DFT - die Wahl des Zeitfensters Um die prinzipielle Problematik der meßtechnischen Anwendung der DFT aufzuzeigen, muß zu Beginn eine kurze Analyse der zu untersuchenden Signale stehen. Daß es überhaupt Probleme bei der Anwendung der DFT auf kontinuierliche Signale gibt, sollte leicht einzusehen sein. Schließlich wendet man ein numerisches Näherungsverfahren (also diskretes Verfahren) auf die (heile) analoge Welt an, und muß damit auch gewisse Fehler in Kauf nehmen. Die im wesentlichen auftauchenden Signale lassen sich in 3 Gruppen einteilen: a. periodische Signale mit einer solchen Frequenz, daß die Abtastfrequenz ein ganzzahliges Vielfaches der Signalfrequenz ist

⇒ ein beliebiges periodisches Signal oder periodisches Signalgemisch ⇒ ein transientes (d.h. nichtperiodisches) Signal

Ein Signal der Gruppe a. ist unproblematisch. Wendet man die DFT auf dieses Signal an, so erhält man in der Tat im Spektrum nur eine einzige Linie, deren Amplitude linear von der Amplitude des Signals abhängt. Allerdings ist dieser Fall eher akademischer Natur: in der Regel wendet man eine Frequenzanalyse ja auf Signale an, deren Frequenz unbekannt ist. Wie soll da die Forderung, daß die Abtastfrequenz ein Vielfaches der Signalfrequenz ist, überhaupt eingehalten werden?

Der Leckeffekt anhand eines Beispiels siehe unten: Man sieht deutlich, daß zur Zeit TF eine Sprungstelle auftaucht, die im physikalischen Signal noch nicht vorhanden war. Aus der Theorie der Fourier-Reihen weiß man aber auch, daß Sprungstellen zu Frequenzanteilen führen. Daher erzeugt die mathematische Berechnung der DFT des physikalischen Signals Frequenzanteile an Stellen, an denen eigentlich keine Frequenzanteile vorhanden sind. Dieser Effekt ist auch als Leck-Effekt (leakage) bekannt.

Die Verschmierung des Spektrums kann durch die Verwendung einer geeigneten Fensterfunktion reduziert werden Aufgrund der abrupten Übergänge, welche durch die periodische Fortsetzung des Signals verursacht werden, kommt es zu einer Verzerrung des Spektrums. Fensterfunktionen dämpfen die Abtastwerte an den Grenzen des Messintervalls und reduzieren somit den Leck-Effekt. Allerdings wird hierdurch auch die spektrale Auflösung herabgesetzt, da insgesamt weniger Information über das Signal zur Verfügung steht.

Fensterfunktionen und ihre spektralen Eigenschaften Zusammenstellung wichtiger Fensterfunktionen und deren Daten Die Fensterfunktionen sind bereits für den diskreten Fall angegeben, d.h. als Funktion von n, und nicht als Funktionen der Zeit t. Dies erleichtert die Rechnerumsetzung. Für Werte außerhalb des Bereichs 0,...,N-1 sind alle Fensterfunktionen identisch 0. Rechteckfenster:

Bild 8: Abtastwerte und Spektralfunktion des Rechteckfensters

Dreieckfenster: (auch Bartlett-Fenster genannt)

Höchster Nebenzipfel: a = − 27dB 0,045 maximaler Abtastfehler: b = 0,81 Breite des Hauptzipfels: c = 0,64⋅Δf

Bild 9: Abtastwerte und Spektralfunktion des Dreieckfensters Hamming-Fenster:

Kontinuierliches Betragsspektrum:

Höchster Nebenzipfel: a = − 43dB 0,007 maximaler Abtastfehler: b = 0,82 Breite des Hauptzipfels: c = 0,65⋅Δf

Bild 11: Abtastwerte und Spektralfunktion des Hamming-Fensters Blackman-Fenster:

Höchster Nebenzipfel: a = − 58dB 0,001 maximaler Abtastfehler: b = 0,88 Breite des Hauptzipfels: c = 0,84⋅Δf

Bild 11: Abtastwerte und Spektralfunktion des Hamming-Fensters

Quellen: FFT-Anwendungen, E. Oran Brigham, übersetzt von Seyed Ali Azizi, R. Oldenbourg Verlag München Wien 1997 Schnelle Fouriertransformation auf Metabelschen Gruppen, Gregor Errath, Dimplomarbeit zur Erlangung des akademischen Grades Magister der Naturwissenschaften an der Universität Wien Diskrete Fouriertransformation und einige Anwendungen, Judith Hergovich, Dimplomarbeit zur Erlangung des akademischen Grades Magistra der Naturwissenschaften an der Universität Wien FFT, Schnelle Fouriertransformation, E. Oran Brigham, 5. Auflage, Oldenburg Verlag 1992 Optimierung der Farbwiedergabe digitaler Kamerasystem, Dr. Peter R. Fornaro, UNI Basel Grundlagen der Signaltheorie,Professor Dr.-Ing. Klaus Meerkötter, Universität Paderborn Spektralanalyse & Drehzahlsynchrone Abtastung, Dipl. -Ing Steffen Kühn, 2005/2006 FG Fahrzeugsysteme und Grundlagen der Elektrotechnik, Dr.-Ing. Sven Semmelrodt, UNI Kassel Armin Hermann Lexikon – Geschichte der Physik A-Z, Aulis-Verlag Deubner & Co

http://www.inf.hs-zigr.de/~wagenkn/TI/Komplexitaet/ReferateSS02/ReferateSS97/fouriertransformation/html/main.html http://www.mathematik.ch/mathematiker/Four_transf.html http://www.canto-crudo.com/electric-orpheus/fourier.htm http://www.markus-hofmann.de/fourier.html