DFT/FFT - Wertebereich

[dizzy]

Heyo DP!

Kann mir jemand fix bei einer Frage zur Fourier-Transformation helfen? Ich finde die Antwort die ich suche ums Verrecken nicht...

Eigentlich ganz einfach: In welchen Intervall bewegen sich die Fourierkoeffizienten? Also angenommen ich gebe eine Messreihe vor, bei der jedes Sample 0-255 sein kann. Wie groß/klein wird dann der größte/kleinste Fourierkoeffizient nach der Transformation sein (Frequenz und Phase)?

Eine zweite Frage, die thematisch zu verwand ist um dafür einen eigenen Thread zu basteln: Die Hälfte der Koeffizienten ist ja letztlich nur relevant (Nyquist Theorem), und ich habe nun schon des öfteren gelesen, dass sich diese Hälfte aus der anderen berechnen ließe. Ich würde zur Speicherung gerne diese Redundanz los werden, aber ich habe bisher nicht finden können wie man diese Berechnung anstellt.

Antworten hierauf würden mich Kilometer weiter bringen :)

Danke schonmal!

[dizzy]

*stups* :oops:

[sirius]

Da du ja schon pushst gebe ich mal ne Antowrt, ohne wirklich sicher zu sein, dass die richtig ist.

Also die Frequenzen, die du bekommst sind ja abhängig von der Länge des betrachteten Zeitraums. die diskreten Frequenzen haben die Werte (n * 1/T) wobei T die Dauer der Funktion ist, welche du in die DFT schickst.
für jede dieser Frequenzen bekommst du eine Amplitude und eine Phase. Welche Genauigkeit die haben (in Abhängigkeit von der Genauigkeit des digitalen Eingangssignals) weis ich jetzt grad nicht. Für die Amplitude sehe eine direkte Abhängigkeit nicht. Sie wird wahrscheinlich potnziert mit der Anzahl der Werte und dürfte damit sehr hoch sein. Für die Phase dürfte ähnliches gelten. Aber vielleicht habe ich etwas übersehen.

Nyquist:
Was du aus der DFT herausbekommst ist einmal direkt der Gleichanteil und dann n verschiedene Frequenzen (abhängig von der Anzahl der Abtastwerte) wobei du nur die erste Hälfte der Werte nutzen kannst. Entsprechend sollten auch keine anderen Frequenzen im Ausgangsignal sein.

[dizzy]

Zitat:

Zitat von sirius

Da du ja schon pushst gebe ich mal ne Antowrt, ohne wirklich sicher zu sein, dass die richtig ist.

Das ist schon mehr als ich zu hoffen gewagt habe nach einem Tag Stille :thumb:

Zitat:

Zitat von sirius

Also die Frequenzen, die du bekommst sind ja abhängig von der Länge des betrachteten Zeitraums. die diskreten Frequenzen haben die Werte (n * 1/T) wobei T die Dauer der Funktion ist, welche du in die DFT schickst.

Das klingt schon so, als ob es in die richtige Richtung geht. Was mich gerade daran nur verwirrt, ist die Zeitkomponente - und zwar weil ich gar kein Zeitsignal habe ;). Es geht mir um Bilddaten, und da wäre vermutlich im weitesten Sinne n=T oder?

Zitat:

Zitat von sirius

für jede dieser Frequenzen bekommst du eine Amplitude und eine Phase. Welche Genauigkeit die haben (in Abhängigkeit von der Genauigkeit des digitalen Eingangssignals) weis ich jetzt grad nicht. Für die Amplitude sehe eine direkte Abhängigkeit nicht. Sie wird wahrscheinlich potnziert mit der Anzahl der Werte und dürfte damit sehr hoch sein. Für die Phase dürfte ähnliches gelten. Aber vielleicht habe ich etwas übersehen.

Jetzt muss ich fragen: Genauigkeit = maximaler Zahlenwert in diesem Fall, oder Signifikanz der Stellen? Für den ersten Fall würde allerdings gelten müssen, dass eine DFT von 4192 Samples jegliche Grenzen handelsüblicher Datentypen um Längen sprengen müsste für die Koeffizienten. Tut sie das, und ich hab es nur nicht bemerkt? :shock:

Worauf das am Ende abzielt ist: Ich bekommen nach einer DFT eines Arrays von Werten zwei genau so lange Arrays mit je dem Frequenzspektrum und der Phase zurück. Wie groß sind meine Arrayelemente maximal/minimal, und wie kann ich das aus den Informationen "Sampleanzahl" und "Wertebereich der Eingangsgrößen" bestimmen?
Ich hoffe doch, dass das geht! Ziel ist es nachher auf 1 zu normieren. D.h. ich will, dass kein Element nachher über 1 ist. Dafür muss ich aber wissen womit ich maximal rechnen muss.
Da am Ende eine dreidimensionale DFT stehen soll, ist ein abfahren aller Werte zur Bestimmung des Maximums eigentlich zu zeitaufwändig. Daher suche ich nach einem Weg das generell zu lösen.

Zitat:

Zitat von sirius

Nyquist:

Mh, ich habe in meinen transformierten Arrays Werte <> 0 über der Hälfte ihrer Länge stehen. Setzte ich diese "künstlich" 0 und wende die iDFT an, ist das Ergebnis vom Original verschieden. Ich hatte das so verstanden, dass sich diese 2. Hälfte ohne weiteres Zutun aus der ersten Hälfte berechnen ließe, so dass ich auf die Speicherung der 2. Hälfte verzichten kann.
Was an sich auch logisch ist, da ich ja 2 Arrays heraus bekomme, also doppelt so viele Daten wie der Eingang. Informationsmehrung wäre neu :) Daher darf letztlich ja nur je die Hälfte der 2 Arrays relevant sein, aber plumpes Wegschneiden verändert die Information offenbar. Daaaa ist mein Problem :drunken:


Danke dir schon mal!

[3_of_8]

Am besten du betrachtest das Ergebnis einer DFT immer relativ. Also du betrachtest sie am besten immer im Bezug auf den Maximalwert. Denn wie genau die Größenordnung der Werte ist, lässt sich schlecht sagen.

[jbaertle]

Guten Abend dizzy,

so wie ich Dich verstehe, verwendest Du für die Eingabe ein Byte-Array und möchtest das auch für die Ausgabe so haben.
Vorsicht: Ohne Vorwissen um die Beschaffenheit des Signals kannst Du nicht sicherstellen, dass Deine Koeffizienten nicht größer als 255 sind, Du solltest also ein Integer-Array für die Ausgabe spendieren.
Bei unbekanntem Signal lassen sich lediglich pauschale Aussagen über die Koeffizienten insgesamt machen (Stichwort Wiener-Chintschin-Theorem), mehr ist aber nicht drin.


MfG Jani.

[dizzy]

Zitat:

Zitat von 3_of_8

Am besten du betrachtest das Ergebnis einer DFT immer relativ. Also du betrachtest sie am besten immer im Bezug auf den Maximalwert. Denn wie genau die Größenordnung der Werte ist, lässt sich schlecht sagen.

Mh, genau das will ich ja verhindern, weil bei 512x480x512 = 125.829.120 Werten, und das mehrere Male hintereinander wird das Raussuchen des global höchsten Wertes zu einem echten zeitkritischen Problem. Klar die FFT braucht auch schon ganz schön dabei, aber man merkts leider tatsächlich.

Zitat:

Zitat von jbaertle

so wie ich Dich verstehe, verwendest Du für die Eingabe ein Byte-Array und möchtest das auch für die Ausgabe so haben.

Jain, ich schmeiss das Ergebnis in Double-Arrays zunächst, eben aus besagter Unkenntnis heraus.

Zitat:

Zitat von jbaertle

Bei unbekanntem Signal lassen sich lediglich pauschale Aussagen über die Koeffizienten insgesamt machen (Stichwort Wiener-Chintschin-Theorem), mehr ist aber nicht drin.

Das ist doch ein prima Suchansatz! Danke dir schon mal. Ich hoffe das lässt sich irgendwie verwenden. Und es geht mir ja gerade um pauschale Aussagen - daher bin ich grad guter Dinge. Aber erstmal in Suchmodus gehen :)

Best Fishes!

[dizzy]

Ich habe recherchiert, und das genannte Theorem scheint wohl nicht wirklich weiter zu helfen - zumindest nicht unmittelbar - und selbst wenn, sind die nötigen Berechnungen wohl leider noch aufwändiger als ein Vergleichen aller Ergebniselemente.

Allerdings habe ich gerade ein wenig mit Excel herumgespielt, und bin zu folgendem Schluss gekommen bisher:
Der überhaupt maximal auftretende Wert ist der DC Anteil. Er ist maximal I*N (I = maximaler Wert eines diskrteten Eingangswertes; N = Anzahl Eingangswerte). Hab ich also 10 Elemente die maximal 255 sind, ist der DC maximal 2550. Das hatte ich soweit erwartet.

Die restlichen Koeffizienten liegen da jedoch deutlich drunter, so dass dort noch Bits gespart werden könnten. Ich habe zum Test den "schlimmsten" Fall angenommen als: Alle Eingangswerte = 255, sprich eine konstante Funktion. Der spannende Teil kommt jetzt: A(1), also die Grundfrequenz sollte dabei ja mit voller Amplitude eingehen, und der knaller ist, dass es scheint als stünden I und If (If = maximaler Wert eines Bandes) ganz einfach über ein Verhältnis in Zusammenhang. Und das Verhältnis ist zudem auch noch ein ganz besonders schönes, nämlich 1,618. Das ist der goldene Schnitt!

Daher komme ich zu folgender Annahme:
Mit Ausnahme des DC ist der maximal zu erwartende Wert der einzelnen Fourierkoeffizienten I*1,618. Klingt mir fast schon zu einfach :) Und gilt zunächst einmal nur für das Amplitudenspektrum. Die Phase muss ich mir noch ansehen.


Ich hoffe ich hab nu keinen groben Mist veranstaltet, aber das sollte die Praxis nachher ja zeigen. Falls obiges jemand wissentlich dementieren kann, bitte ich darum! Mag mich nicht auf dem falschen Pfad nun zu genau umsehen :)

[3_of_8]

Wie willst du bei 125829120 eine FFT anwenden? O_o Divide&Conquer haut da nicht wirklich hin.

[jbaertle]

Guten Abend dizzy,

ganz genau. Du kannst lediglich über die Summe der Quadrate der Koeffizienten Aussagen treffen (wie so oft...).

Eine Bemerkung noch: Wenn Du - wie Du sagt - ein konstantes Signal fouriertransformieren willst, dann sollte der Algorithmus nur einen, von Null verschiedenen Koeffizienten im Spektrum ausgeben (a0 o.ä).

MfG Jani.