Hat jemand Ahnung von der 2D-DFT?

NOFX

Grand Admiral Special
Mitglied seit
02.09.2002
Beiträge
4.532
Renomée
287
Standort
Brühl
  • RCN Russia
  • Spinhenge ESL
Wie im Titel schon steht: Hat jemand Ahnung von der 2D-DFT?

Im Speziellen habe ich ein Verständisproblem mit der Separabilität dieser.
 
Also prinzipiell kenne ich mich mit 2D-DFTs aus.
Wo ist dort dein Problem?
 
Ersteinmal Danke für die Antwort!

Die normale 2D-DFT besteht ja in einfachster Form aus der folgenden Doppelsumme:

42b0ba1b7ec75200f274d07d9b05e344.png

(Wikipedia: DFT)

Um diese vernünftig zu implementieren soll man diese separieren können. Die einzigen Anhaltspunkte dazu habe ich jedoch darin gefunden, dass ersteinmal eine Matrix mit den e-Potenzen berechnet wird, diese dann aber wieder für jedes â(k,l) in einer Doppelsumme mit den a(m,n) multipliziert wird.

Das wiederum führt dazu, dass wieder N^4 (N=M=Seitenlänge des Bildes) Operationen durchgeführt werden müssen, die dann nur keine komplexe Multiplikation mehr beeinhalten. Das dürfte zwar einen Faktor bis evtl. 10 in der Geschwindigkeit ausmachen (da viele, bzw. fast alle komplexen Multiplikationen wegfallen), aber trotzdem noch extrem lange dauern.
 
OK, dass sieht schonmal besser aus, ich lasse also "einfach" in x-Richtung erstmal die 1D-DFT durchrechnen, und danach in den y-Richtung.

Nach der Formel, die ich in Jähnes Digitaler Bildverarbeitung gefunden habe, war die DFT nur sperabel in ein Skalarprodukt für jeden EIntrag, was halt auch wieder zu n^4 Berechnungen geführt hätte. So liegt der Aufwand ja bei n^3 für die Vorberechnung der 1D-DFT und ebenfalls bei n^3 für die in der zweiten Richtung.

Wie die da auf n^2 * log n kommen weiß ich nicht ???
 
Das macht aber auch wieder n^3...

Ich bin gerade noch am schwanken, wie ich besser die komplexen Zahlen als Klasse in Java implementiere, besser als Exponentialdarstellung oder als a+bi? Da eigentlich die Anzahl der Additionen ungefähr gleich der der Multiplikationen ist, sollte es imho egal sein, oder?
 
Also die 2D-FFT hat, soweit ich weiß, eine Laufzeitkomplexität von O(n² log n) (Bild n*n Pixeln).

(FFT = Fast Fourier Transform)
 
Musst du es denn wirklich selber implementieren? Wenn nicht, schau dir mal fftw an. Ich denke mal, da dürfte dir ein Großteil der Arbeit schon sehr gut abgenommen sein.
 
Ja, muss ich selber implementieren. Ist für meine Bachelor-Arbeit bei der halt mit Fouriertransformation und Trägheitsachsen Hauptrichtung in Texturen gefunden werden sollen.

Die FFT hat bei den einfachen Algortihmen das Problem, dass sie nur Zweierpotenzen unterstützt. Bei Bildern im Format 640x480 natürlich ist das natürlich ein wenig unpraktisch.
 
Gut, aber mit der einfachen DFT wirst Du wohl nicht unter O(n³) kommen.
 
Was prinzipiell schon reichen würde, so hoffe ich es zumindest.

Momentan habe ich nur ein kleines Problem bei der Implementierung, sodass die Laufzeit zwar super ist, die Ergebnisbilder aber alle schwarz. *lol*
 
Die einfachste Methode das zu umgehen: Mit Nullen auffüllen.
Berechnen kann man sie dann schon, nur die Ergebnisse sind kann ich halt nicht gebruachen, weil scharfe Kanten halt das Ergebnis völlig verfälschen.
 
Man kann ja überabtasten und dann die hohen Frequenzen wegwerfen.
Die hohen Frequenzen brauche ich ja nachher. Die Fehler, die durch dadruch entstehen würden, wären imho größer als der Nutzen der Geschwindigkeit.

Ich bin jetzt bei ca. 3min für ein 640x480 großes Bild, das ist soweit OK.


Welche Werte sind eigentlich am sinnvollsten für die spätere Ausgabe als Bild, der Absolutbetrag der komplexen Werte? Oder lieber der Realteil, oder oder oder...
 
Die hohen Frequenzen brauche ich ja nachher. Die Fehler, die durch dadruch entstehen würden, wären imho größer als der Nutzen der Geschwindigkeit.

Ich bin jetzt bei ca. 3min für ein 640x480 großes Bild, das ist soweit OK.


Welche Werte sind eigentlich am sinnvollsten für die spätere Ausgabe als Bild, der Absolutbetrag der komplexen Werte? Oder lieber der Realteil, oder oder oder...

Nunja, die hohen Frequenzen würden ja nur durch die harten Kanten entstehen, die ja künstlich hinzugefügt wurden. Vll. habe ich aber auch einen Denkfehler.

Bei der Darstellung kommt es wohl auf die Anwendung an, z.B. würde man sich bei soetwas wie QPSK nur für die Phase, also den Winkel interessieren. Aber meistens nimmt man wohl den Absolutwert.
 
Die sehr hohen Frequenzen hängen stark von scharfen Kanten ab, das stimmt, da aber die Struktur die erkannt werden soll ist manchmal auch nur wenige Pixel breit, je nach Größe des Eingangsbildes.

Ich benutze jetzt den Absolutwert, das sieht "gut" aus und die Ergebnisse stimmen jetzt auch.



Falls das irgendjemanden interessiert kann ich auch ein paar Bilder posten. ;)
 
jo mach mal bitte
 
So hier mal ein paar Bilder:
attachment.php
 
Und noch eins für die freundlichen Mannen des sympathischsten CPU-Hersteller:
attachment.php
 
Zurück
Oben Unten