Fouriertransformation - Warum, Wieso?

TonyW
Neuling
Neuling
Beiträge: 7
Registriert: 6. Mär 2012 10:55

Fouriertransformation - Warum, Wieso?

Beitrag von TonyW » 19. Jul 2012 10:08

Hallo zusammen,

was ich bis jetzt verstanden habe ist, das man die Fouriertransformation zum umrechnen vom Ortsraum in den Frequenzraum benötigt, weil dort das Anwenden von Filtern mathematisch einfacher zu berechnen ist. Aber warum ist das so? Was bringt mir das ganze dann?

Gruß Tony

Thomas Huxhorn
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 171
Registriert: 6. Okt 2011 15:25

Re: Fouriertransformation - Warum, Wieso?

Beitrag von Thomas Huxhorn » 19. Jul 2012 10:33

Nicht einfacher sondern schneller.
Was du im Ortsraum durch eine Faltung berechnest, ist in Frequenzraum nur eine Multiplikation.

TonyW
Neuling
Neuling
Beiträge: 7
Registriert: 6. Mär 2012 10:55

Re: Fouriertransformation - Warum, Wieso?

Beitrag von TonyW » 19. Jul 2012 10:40

Ich glaub da liegt der Hund bei mir begraben. Verstehe leider nicht warum die Faltung so viel langsamer sein soll, bzw. warum die Multiplikation soviel schneller ist.

Thomas Huxhorn
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 171
Registriert: 6. Okt 2011 15:25

Re: Fouriertransformation - Warum, Wieso?

Beitrag von Thomas Huxhorn » 19. Jul 2012 11:47

Die Faltung ist grob gesagt die Summe über das Produkt zweier Funktionen. Du hast also n viel Multiplikationen (Subtraktionen auch noch) statt nur einer einzelnen Multiplikation.

Man hat das umrechnen in den Fourierraum und zurück so stark optimiert, so dass es schneller als eine Faltung ist. Coole Sache wa ;)

Benutzeravatar
hymGo
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 209
Registriert: 4. Okt 2009 23:17

Re: Fouriertransformation - Warum, Wieso?

Beitrag von hymGo » 29. Jul 2012 00:05

TonyW hat geschrieben:Hallo zusammen,
Aber warum ist das so? Was bringt mir das ganze dann?
Die FIlter im Ortsraum (Tiefpass, Hochpass) sind auch alles nur approximationen der Originale. Im Frequenzraum sind sie dagegen "richtig" definiert.

Daki
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 4. Nov 2010 14:34

Re: Fouriertransformation - Warum, Wieso?

Beitrag von Daki » 30. Jul 2012 00:16

hymGo hat geschrieben:Die FIlter im Ortsraum (Tiefpass, Hochpass) sind auch alles nur approximationen der Originale. Im Frequenzraum sind sie dagegen "richtig" definiert.
Ich gebe zu, dass ich nicht verstehe, was du damit sagen willst. Beziehst du dich auf Folie 30 (11.05.2012)?

@TonyW:
Bei kleinen Filtermasken, also nur wenigen von 0 verschiedenen Gewichten, bringt eine DFT nicht unbedingt die ultimative Laufzeitverbesserung. Mit ein bisschen Pech ist deine Filtermaske aber z.B. so groß, dass du für jeden einzelnen Punkt im Zielbild jeweils alle Punkte des Originalbilds heranziehen (sprich: gewichten und aufsummieren) musst. Ein naiver Ansatz zur Berechnung der DFT eines Bildes würde dies auf jeden Fall auch erfordern (die Berechnung der Inversen ebenfalls), insofern wäre da noch nichts gewonnen. Der Witz ist aber, dass man unter gewissen Umständen die DFT (und die Inverse dazu) sehr viel schneller berechnen kann ("FFT"). Die "gewissen Umstände" haben etwas mit der Primfaktorenzerlegung der Bildmaße (Höhe und Breite des Bildes) zu tun. Wer seinen Rechenknecht mit einer diskreten Fouriertransformation so richtig ins Schwitzen bringen will, sollte möglichst große Primfaktoren in die Bildmaße einarbeiten. Will man dagegen seinen Rechner schonen, verwendet man möglichst kleine Primfaktoren, sprich: die Zwei. Deswegen akzeptieren viele FFT-Implementierungen nur Fenster in der Größe von Zweierpotenzen.
Nein, mein Nick hat nichts mit Kissen zu tun!

Antworten

Zurück zu „Archiv“