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(m
x
, n
y) 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
.