Fouriertransformationen und ihre Anwendung

(Proseminarschrift von Stephan Heinersdorff)


 
Diese Proseminarschrift basiert auf dem Buch "Einführung in die digitale Bildverarbeitung" von Wolfgang Abmayr
(Teubner Verlag 1994).

Der französische Mathematiker Baron Jean Baptiste Joseph Fourier 1768-1830 war Staatssekretär für die
Mathematischen Wissenschaften unter Ludwig dem XVIII.
Durch seine Arbeiten über Thermodynamik entdeckete er die sogenannten Fourierreihen, die in vielen Bereichen
Anwendung finden, so auch in der digitalen Bildverarbeitung.

 

 I. Eindimensionale Fouriertransformation

A. Graphische Interpretation

 

Eindimensionale Signale wie z.B. eine Bild- bzw. Grauwerte-Zeile können durch Abtastung über einen bestimmten
Zeitraum in zweidimensionale Signale umgewandelt werden.
Den zweidimensionalen Graphen einer solchen Abtastung bezeichnet man als Darstellung des Signals
(hier: der Grauwerte-Zeile) im Ortsbereich.

Als Beispiel sei hier ein Signal b1(x) gegeben, das aus einer sinusförmigen Grauwerteverteilung
entlang der x-Achse besteht.

Desweiteren seien gegeben zwei Oberwellen b2(x) und b3(x).
b1(x) habe die Periodenlänge X0 bzw. die Grundfrequenz fx0 = 1/X0.

                                                  b1(x)       = 
 
                                                  b2(x)       = 

                                                  b3(x)       = 

Durch Addition der Grundschwingung b1(x) mit den harmonischen Oberschwingungen erhält man die Gleichung
für das Summensignal b'(x) :

                       b'(x) = b1(x) + b2(x) + b3(x)        = 

 

Die Darstellung solcher Funktionen im Ortsbereich ist bekannt und vertraut.
Ungewöhnlicher scheint jedoch die Darstellung von b'(x) im Ortsfrequenzbereich.
 

                 Ortsbereich:
 

Um sich den Zusammenhang zwischen den Darstellungsformen bildlich vorzustellen betrachtet man die einzelnen
Summenelemente als 'gewöhnliche' Graphen jedoch räumlich gegeneinander verschoben entlang der neu
hinzugekommenen z-Achse. (die Grafik enthält zusätzlich b'(x))
Die z-Position entspricht dabei der Frequenz der Funktion .

Nun betrachtet man die Summenelemente b1(x), b2(x), b3(x) in negative x-Richtung blickend und bewegt sich auf der Diagonalen D: y = 0, x = z >0 .   Man betrachtet die Funktionen also 'frontal'.

Auf diese Weise läßt sich ein zweidimensionaler Graph zeichnen auf dem die x-Achse die Frequenzen und die
y-Achse die Amplituden der Summenelemente repräsentiert.

Die Information der beiden Darstellungen ist die Gleiche, es lassen sich jedoch in der Darstellung im
Ortsfrequenzbereich andere Eigenschaften erkennen - insbesondere aus welchen Frequenzanteilen sich
das Bild zusammensetzt.

 

 

 
B. Die Fourierreihe

 a. Reale Schreibweise
Die Erweiterung der Summmenformel für b(x)' auf  ergibt eine Fourierreihe deren Graph wie folgt aussieht:
 

 
Ganz allgemein läßt sich jede stückweise periodische Funktion b(x) durch eine Reihe aus Sinus- und Cosinusgliedern beschreiben.

Die zugehörige Reihe ist die Fourierreihe und hat die Form :

 

 Wobei die Fourierkoeffizienten ak , bk die Amplituden der Cosinus- und Sinusfunktionen repräsentieren und
die Frequenzen.

 

 

 b. Komplexe Schreibweise

Im Komplexen hat b(x) die Exponentialform 

 

Die Koeffizienten 

 sind im allgemeinen komplexe Zahlen mit Realteil  und Imaginärteil  ,

 
dem Betrag 

 und der Phase 

 

C. Die Fouriertransformation (FT)

Mit Hilfe der Fourierreihe lassen sich periodische Signale wie oben besprochen behandeln.
Zur Behandlung beliebiger Signale muß man jedoch auf die Fouriertransformation zurückgreifen.

Dazu ist ein Übergang vom Linienspektrum des Frequenzbereiches im obigen Beispiels (siehe Graphische Interpretation)
in ein kontinuierliches Spektrum notwendig.
Graphisch erfolgt dies approximativ durch die Verbindung der 'Spitzen' des Linienspektrums: 

 

 

 


    -k                           Linienspektrum                              +k                     -fx                kontinuierliches Spektrum     fx

 

 

 


Zur mathematischen Realisation kann man folgende Umformung an der komplexen Fourierreihe vornehmen:

                            i.) 

                            ii.) 

                            iii.) 

 Damit erhält man die eindimensionale inverse Fouriertransformation

 

 ,die aus dem Ortsfrequenzspektrum S(fx) die Ortsfunkion b(x) berechnet.

 
Ihre Umkehrfunktion ist die eindimensionale Fouriertransformation :

 

Sie unterscheidet sich von der inversen Fouriertransformation nur durch das Vorzeichen des e-Exponenten.
Die Ortsfrequenzfunktion S(fx) konvergiert, wenn b(x) ein endliches Signal ist.

 
 
 

II. Zweidimensionale Fouriertransformation

 

Für die Erweiterung von der eindimensionalen zur zweidimensionalen Fouriertransformation sind folgende
Übergänge nötig :

 

 
 

 man erhält somit die zweidimensionale Fouriertransformation

 

 und analog die inverse zweidimensionale Fouriertransformation

 

 
Die Ortsfrequenzfunktion S(fx, fy) , die auch Spektralfunktion genannt wird, konvergiert wieder,
wenn es sich bei b(x, y) um ein endliches Signal handelt.

b(x,y) und S(fx, fy) heißen korrespondierende Fouriertransformationspaare - in Zeichen :

 
 
 
 

Im Gegensatz zur Ortsfunktion, ist die Ortsfrequenzfunktion im allgemeinen eine komplexe Funktion mit Real- und Imaginärteil

 

 oder analog zur komplexen Schreibweise der Fourierreihe (siehe I.B.b)

 

 

 
Das Betrags - oder Amplitudenspektrum ist

 

 sein Quadrat heißt Leistungs- bzw. Powerspektrum P(fx, fy) und bietet multiple Verwendungsmöglichkeiten.

 

Schließlich erhält man mit

      das Phasenspektrum.

 

 

 

III. Eigenschaften der Fouriertransformation

 
Zum besseren Verständnis einiger Eigenschaften wird an dieser Stelle ein Einschub
über das Faltungsintegral vorgenommen.

 Das Faltungsintegral

Die Faltung zweier Signale ist eine Operation, die aus den beiden Eingangssignalen ein neues Signal bildet.
Symbolisch hierfür verwendet man den Faltungsoperator '' .

Graphisch kann man sich die Faltung zweier Signale als die Auswertung einer Folge von Produkten
der Form  bei einer stetigen Erhöhung von  vorstellen.

 

 

Besondere Aufmerksamkeit verdient die Faltung einer beliebigen Funktion mit einer Diracfunktion.
Eine Diracfunktion  ist an ihrer Auftreffstelle  und sonst 0.
Das Integral über die Diracfunktion ist stets 1.

Die Faltung eines Signals mit einer  - Funktion ergibt wieder das Signal.
Die Faltung eines Signals b(x) mit einer Folge von  -Funktionen h(x) bewirkt eine Vervielfältigung des Signals
mit der Anzahl der Diracimpulse.
Man erhält also ein periodisches Signal bp(x) mit einer, dem Abstand der Diracimpulse entsprechenden Periodenlänge.

 
 
 
 
 

A. Linearität

Da die Fouriertransformation eine lineare Gleichung ist gilt das Superpositionsprinzip :

 

 

  

 

Das Spektrum (F) der Summe (E) der Bilder (A), (C) im Ortsbereich ist also gleich der Summe der Spektren (B), (D) :

 

      Ortsbereich :                                                                           Frequenzbereich :
 
(A) (B) 

 

(C) 

 

(D) 

 

(E) (F)
 

 
 
 
 
 

B. Verschiebung

 Eine Verschiebung im Orts- bzw. Frequenzbereich bewirkt lediglich eine Verschiebung des Phasenspektrums:

 

 
 

 
Das Amplitudenspektrum jedoch bleibt unverändert.
Diese Eigenschaft kann man sich zu Nutze machen ; wenn es z.B. um Objekterkennung geht wird eine Zentrierung des Objekts für die Erkennung im Amplitudenspektrum nämlich überflüssig.

 

 

 C. Drehung

 Einer Drehung eines Bildes im Ortsbereich entspricht eine gleichartige Drehung im Ortsfrequenzbereich:

 

 

D. Ähnlichkeit

Bei einer Dehnung der Bildfunktion in einer Richtung wird die entsprechende Frequenzfunktion entlang dieser Richtung gegen die Nullfrequenz zusammengeschoben.

Mathematisch ergibt sich folgender Zusammenhang:

 

 

 

E. Faltung

Die zweidimensionale Faltung ist analog zur eindimensionalen definiert , nämlich als Integral über letzterer.
Die Faltung zweier Ortssignale führt zu einer Multiplikation der Frequenzfunktionen ebenso führt eine Multiplikation im
Ortsbereich zur Faltung der korrespondierenden Frequenzdarstellungen.

Diese Eigenschaft nennt man das Faltungstheorem
Es hilft einem z.B. bei der Aufwandsabschätzung für eine Bildfilterung wenn man beurteilen kann ob man lieber eine Multiplikation der Ortssignale oder eine Faltung der Frequenzen vornehmen soll.
 

               Ortsbereich :                                                                          Frequenzbereich :
 
(A) (B) 

 

(C) 
 

Faltung :

(D) 
 

Multiplikation :

(E) (F)
 
 
 
 
 

IV. Abtasten von Bildern
 

A. Bilddarstellung im Frequenzbereich

Für die Verarbeitung von Bildern ist eine Umwandlung von (analogen) Bildsignalen b(x,y)
in diskrete Signale bd(mx , ny) erforderlich.
Dies wird mittels zweidimensionaler Abtastung realisiert.

Der Koordinatenursprung eines Bildes ist links oben im Gegensatz zu dem des
Frequenzspektrums der sich, ähnlich dem mathematischen Ursprung, in der 'Mitte' befindet.

Nahe letzterem befinden sich die niederfrequenten Bildanteile im Frequenzspektrum während die hochfrequenten am Frequenzbild-Rand zu finden sind.
Zum Beispiel sagt also der Grauwert eines Punktes am Frequenzbild-Rand aus, wie stark auf seiner Verbindungslinie zum Bildmittelpunkt hochfrequente Anteile vertreten sind.

Die physikalische Dimension der Ortsfrequenzen ist Bildpunkte/mm - die höchste darstellbare Ortsfrequenz bezeichnet
man als Auflösung.

Da es sich bei diskreten Bildsignalen um Abtastwerte einer orts- und intensitätskontinuierlichen Funktion handelt, muß bei
der Interpretation und Darstellung der zweidimensionalen Spektrums die Nyquistbedingung berücksichtigt werden.

Sie besagt, daß ein begrenztes Signal mit mindestens dem zweifachen seiner höchsten vorkommenden Frequenz
abgetastet werden muß, damit eine eindeutige Signalrekonstruktion aus den Abtastwerten gewährleistet ist.

 Es gilt  mit fs als Abtast- und F als höchster Signalfrequenz (= Bandbreite).

 Bei gegebener Abtastfrequenz fs sind somit fx , fy die höchsten fehlerlos rekonstruierbaren Frequenzen des Bildsignals wobei
 
 
 
 
 

B. Eindimensionale Abtastung

 Ein Abtaster multipliziert das kontinuierliche Eingangssignal b(x) mit einer Abtastfunktion a(x) und erzeugt so
das diskrete Ausgangssignal 

 Idealerweise besteht a(x) aus einer periodischen Dirac-Impulsfolge mit Abtastintervall und Abtastfrequenz  :
 

 

Das Produktsignal
 
nimmt an den Auftreffstellen von a(x) die Gewichte der Funktionswerte von b(x) an.
Reale Abtaster arbeiten mit Impulsen die, im Gegensatz zum Ideal der-Funktion, endliche Dauer besitzen.
 
 
 
 

Nach dem Faltungstheorem (s. oben) entspricht die Multiplikation des Ortssignals b(x) mit der Abtastfunktion a(x)
einer Faltung des Frequenzspektrums S(fx) mit der Fouriertransformierten A(fx) von a(x).
Da letztere wiederum eine Dirac-Impulsfolge ist, entsteht ein periodisches Linien(frequenz)spektrum :

 

 

A(fx) hat eine Periodenlänge von 
Wenn nun dieser Abstand zwischen den Spektren zu gering ist kann es zu Überlappungen kommen.
Ihr Auftreten hängt mit von der Einhaltung der Nyquistbedingung ab:

 

wobei F die höchste vorkommende Frequenz des Ortsbereiches sei.

 

Ist die Nyquistbedingung erfüllt, so überlagern sich die periodischen Spektralanteile nicht und eine fehlerlose
Rekonstruktion des Ausgangssignals ist möglich.
Bei Nichteinhaltung können sich die Frequenzspektren überlappen, was eine fehlerhafte Rekonstruktion mit
Signalartefakten nach sich zieht.

Solche, auf einer Unterabtastung basierende, Fehler nennt man Überlappungsfehler oder Aliasingfehler.

 

 

 
         (A)                                                                                     ( B)
 

                                        (A) Abtastung mit 512x512 Bildpunkten - geringer Aliasingfehler
                                                      (B) Abtastung mit 128x128 Bildpunkten - großer Aliasingfehler

 
 
 
 


                                        Abtastung eines Signals mit einer zu großen Abtastperiode (links).
                                  Es liegt Unterabtastung vor, die zu einer Überlappung der Spektren (rechts) führt.

 
 

Zur Vermeidung von Aliasingfehlern empfiehlt sich vor der Abtastung eine Bandbegrenzung (= Frequenzbegrenzung)
mittels eines Tiefpaßfilters vorzunehmen.
Der Tiefpaßfilter begrenzt den Frequenzbereich auf die Hälfte der Abtastfrequenz.
Ein derart begrenztes Signal kann eindeutig rekonstruiert werden.

 

Die Rekonstruktion des Signals aus den diskreten (abgetasteten) Signal erfolgt im Frequenzbereich durch Multiplikation mit einem Tiefpaß der Grenzfrequenz F =    (bzw. mittels entsprechender Faltung im Ortsbereich).
 
Im Gegensatz zur Unterabtastung ist bei Überabtastung eines Signals eine fehlerlose Rekonstruktion möglich - es erhöht sich lediglich der Aufwand.

Die obigen (sowie folgenden) Überlegungen beziehen sich auf das Ideal des unendlich ausgedehnten ortskontinuierlichen Signals.
Tatsächlich arbeitet man jedoch mit Signalen, die im Ortsbereich durch Multiplikation mit einer Fensterfunktion begrenzt wurden. Diese Operation führt unweigerlich zu Aliasingfehlern, die es, durch die Wahl einer geeigneten Fensterfunkion, möglichst gering zu halten gilt.
 
 
 
 

C. Zweidimensionale Abtastung

 Analog zur eindimensionalen Abtastung erhält man ein ortsdiskretes Bild

 mit den Abtastintervallen  in x-, y-Richtung.

 

Mathematisch wird die Abtastfunktion definiert als

 

 

 
Da die Fouriertransformierte von a(x,y) wieder eine zweidimensionale Dirac-Impulsfolge ist ergibt sich das
Frequenzspektrum von bd(x,y)
 

 Auch hier ist die Nyquistbedingung erfüllt, wenn sich die periodischen Spektren nicht überlagern (weder in x- noch in y-Richtung).

Die Rekonstruktion erfolgt wieder mit einem Tiefpaß.
 
 
 
 

V. Diskrete Fouriertransformation (DFT)

 

A. Eindimensional

Bisher wurde nur die kontinuierliche FT behandelt. Die diskrete FT kann als Spezialfall der kontinuierlichen betrachtet werden.

Da die obige abgetastete Funktion bd(x) unendlich viele Abtastwerte berücksichtigt ist sie für die numerische Auswertung ungeeignet.
Es ist also notwendig sie mittels Multiplikation mit einer Fensterfunktion zeitlich zu begrenzen um lediglich N Abtastwerte zu erhalten.
(Im Frequenzbereich führt dies zur entsprechenden Faltung und bewirkt Welligkeiten im Frequenzspektrum die es durch geeignete Wahl der Fensterfunktion gering zu halten gilt.)

Da das Frequenzspektrum eines so gebildeten diskreten Signals noch immer kontinuierlich ist muß dieses nun seinerseits
mittels einer Frequenz-Abtastfunktion A1(fx) diskretisiert werden.
(Die entsprechende Faltung im Ortsbereich wandelt das Ortssignal bd(x) in ein periodisches um.)

 
Zusammenfassend werden also diskrete Ortsfunktion sowie diskretes Frequenzspektrum jeweils durch N Abtastwerte pro Periode angenähert.

 

Die Formel für die DFT erhält man durch Umwandlung der Formel für die FT. (x wird ersetzt durch  ,
das Integral wird approximiert durch die Summe der Rechtecke mit Seiten  und  . Die Multiplikation mit dem Abtastintervall wird jedoch nicht in die Formel aufgenommen.)

 

Die DFT ist eine eigenständige eindeutige und umkehrbare Transformation, die sich zur Verarbeitung mit einem Digitalrecher eignet.

 

 

B. Zweidimensional

Analog zur eindimensionalen wird für die zweidimensionale DFT die kontinuierliche FT auf N Abtastwerte in x-Richtung und M Abtastwerte in y-Richtung begrenzt.

 

 
M, N stehen für die Anzahl der Spalten bzw. Zeilen des diskreten Bildes.
Für den Fall M = N läßt sich die zweidimensionale DFT aufteilen in zwei eindimensionale DFTs aufteilen (je eine für Spalten und Zeilen).
Für die Implementierung bedeutet das ein Überführen des Bildes B(x,y) in ein Zwischenergebnis H(fx,y) welches schließlich in die DFT Sd(fx, fy) übergeführt wird.

 
 
 
 
 

VI. Schnelle Fouriertransformation (FFT)

Die schnelle Fouriertransformation nach Cooley und Tukey ist der schnellste bekannte Algorithmus zur Auswertung der
diskreten Fouriertransformation.
Seine Anwendung und der Grund für seine Effizienz sollen hier erläutert werden.

 

Durch geeignete Substitution läßt sich die DFT schreiben als

 

 
Sei  so folgt :

 
 

 
für (hier sei i = 2) erhält man die Gleichungen :

 

oder als Matrix :

 

 

Sowohl W als auch bd0 können komplexe Werte annehmen ,was bei der Berechnung des Matrizenprodukts zu N2
komplexen Multiplikationen sowie N(N-1) komplexen Additionen führt.
Dank des FFT-Algorithmus kann die Anzahl der erforderlichen Operationen jedoch erheblich reduziert werden.

 
Infolge der Periodenlänge N des diskreten Signals ergibt sich  und somit

 

 

Durch Vertauschen der Zeilen 2 und 3 der W-Matrix und der entsprechenden Vertauschung in der Sd-Matrix ergibt sich

 

Die Faktorisierung im obigen Schritt ist der Hauptgrund für die Leistungsfähigkeit des FFT-Algorithmus

 

 
 

Zur Berechnung des ersten Matrizen(teil)produkts bedarf es 4 komplexer Additionen und 2 komplexer Multiplikationen.
Auch für das zweite Produkt sind 4 komplexe Additionen und 2 komplexe Multiplikationen notwendig
( W3bd(3) = -W1 bd(3) und muß daher kein zweites Mal berechnet werden)
 

Offensichtlich schneidet man hier mit 8 Additionen und 4 Multiplikationen besser ab als nach der direkten Methode mit 12 Additionen und 16 Multiplikationen.

 

Allgemein benötigt die FFT  komplexe Multiplikationen und  komplexe Additionen. Die Rechenzeit entspricht
ungefähr der Anzahl der komplexen Multiplikationen, was bedeutet, daß der FFT-Algorithmus annähernd  mal
schneller ist als die direkte Methode.

Bei N=1024 Abtastwerten ergibt sich also eine Rechenzeitverkürzung um .


E-Mail an heinersd@in.tum.de