|
|
|
Faltung im Frequenz oder Zeitbereich? |
|
| Pheeenix |
Forum-Anfänger
|
 |
Beiträge: 29
|
|
|
|
Anmeldedatum: 01.07.10
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
 |
|
Verfasst am: 16.12.2010, 18:14
Titel: Faltung im Frequenz oder Zeitbereich?
|
 |
Hallo,
ich habe eine kleines Verständnisproblem im Bezug auf Faltung im Zeit bzw. Frequenzbereich.
Eine Faltung im Frequenzbereich ist einfacher, das ist mir klar, da dies ja eine Multiplikation darstellt.
Aber jetzt kommt der Knackpunkt. Angenommen ich will ein Bild mit einem Filter falten: Ich habe gelesen dass es Fälle gibt bei denen die Fouriertransformation+Multiplikation im Frequenzbereich langsamer ist als die direkte Faltung im Zeitbereich.
Gibt es irgendwelche Mathematischen "Richtlinien" (oder so) wann eine Faltung im Zeitbereich schneller ist als im Frequenzbereich? Von was hängt das ab? (größe der Filtermaske, größe des Bildes? ... und wieso?)
google konnte mir leider noch keine Lösung liefern die ich auch verstehe 
Vielen Dank im Voraus für euer bemühen!!!
|
|
|
|
|
|
| Scriptor |
Forum-Century
|
|
Beiträge: 217
|
|
|
|
Anmeldedatum: 22.02.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 21.12.2010, 03:57
Titel:
|
|
| |
 |
 |
Die diskrete Fouriertransformation ist nicht viel anderes als eine Faltung, nur dass die Glieder der zu transformierenden Funktion mit einer Faltungsfunktion wie mit einer Matrixmultiplikation multipliziert werden, deren Glieder wiederum Exponenten von e sind. Ihre Rechenintensität hätte daher die einer Faltung + noch die Multiplikation einzelner Spektrenglieder mit dem Fenster zurfolge. Jede Faltung hat die Komplexität , die sich aus der Multiplikation der Glieder heraus entwickelt. Da eine FFT sowohl die gleiche Anzahl an Bild und Realpunkten hat, ergibt sich also für die Anzahl der Glieder der Faltungsmatrix das Quadrat der Menge Samples N² (wenn man die dft direkt berechnen würde).
Die FFT ist als solches aber ein sehr schnelles Verfahren. Aufgrund der Struktur der Fouriermatrix und deren Abfolge der Multipliktation ergibt sich eine geringere Komplexität N*log(N). Daraus ergibt sich für mich die Vermutung, dass für eine schnellere Durchführung einer Faltung über den Umweg fft und Multiplikation folgende Bedingungen erfüllt sein. Die Größe der zu faltenden Funktion muss die selbe Größe haben wie die der Faltungsfunktion. Je größer der Datensatz, umso sinnvoller ist der Umweg über die FFT.
Kurz zusammengefasst würde ich sagen:
1) Nur wenn Größe der zu faltenden Funktionen gleich ist.
2) Kleine Datensätze können auch direkt gefaltet werden. Dürfte nicht soviel ausmachen. Hierfür habe ich jetzt aber keine genauen Zahlen parat.
Hoffe das hilft,
Mfg Scriptor
|
|
|
|
|
|
|
Einstellungen und Berechtigungen
|
|
Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
|
|
Impressum
| Nutzungsbedingungen
| Datenschutz
| FAQ
|  RSS
Hosted by:
Copyright © 2007 - 2024
goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
|
|
