# Ausgangslage
Normalerweise nimmt man ja die euklidische Distanz / Metrik. Bei der DFT
hat man einen Vektor von N Werten, und man bekommt N Frequenzamplituden
& Phasen, für Frequenzen 0,1,2,3,...,N-1 als Vektor heraus. Das ist auch
wieder umkehrbar. Bei der normalen DFT geht das ja so:
## Normale Diskrete Fourier Transformation
Wenn ich bei einem Punkt die Distanz zum Nullpunkt haben will, dann ist
das sqrt(x^2+y^2).
Bei sqrt(x^2+y^2)=1 hat man einen Einheitskreis in der Euklidischen
Metrik.
Mit sin(w) / cos(w) kriegt man die x y Koordinaten von einem Punkt,
angefangen mittig oben, und wenn man w linear erhöht, geht der Punkt
linear entlang dem Kreis herum.
Mit atan2(y,x) bekommt man den Winkel wieder.
Wir haben also diese N Eingabe Werte.
Und von jeder der Frequenzen nehmen wir N sample, mit sin() und cos()
können wir die erzeugen:
Wir haben also eine Matrix mit den Wellenformen, und einen Vektor mit
den Eingabewerten. Die multipliziert man einfach, und man bekommt
zurück, wie gut die korrelieren. Jeweils für Sin und Cos, die sind ja
90deg Phasenversetzt.
Bei diesen 2 Vektoren muss man nur noch die Distanz (sqrt(x^2+y^2)) und
die Phase (atan2(y,x)) ermitteln, x/y sind jeweils die
korrespondierenden Werte dieser Vektoren.
Und schon hat man die gesuchten Frequenzanteile und Phasen.
Das Umkehren ist dann ja einfach. Man nimmt N Samples von jeder
Frequenz, mit der jeweiligen Phase, mit sin, multipliziert es mit der
Amplitude, und addiert die Resultate der unterschiedlichen Frequenzen
zusammen.
Das unschöne an euklidisch ist halt, mit sin / cos bekommt man
irrationale Zahlen da braucht man Floats und verliert Genauigkeit. Darum
dachte ich mir:
## Diskrete Fourier Transformation mit Taxicab Metrik
Das vorgehen müsste ja gleich sein. Aber statt dass die Distanz durch
sqrt(x^2+y^2) definiert ist, ist es in der Taxicab Metrik |x|+|y|.
Ein Einheitskreis ja durch eine Distanz zum Zentrum von 1 definiert.
|x|+|y|=1 ergibt ein um 45deg gedrehtes Quadrat. In der Taxicab Metrik ist das der
Einheitskreis.
Statt Sin / Cos hat man dann eine Dreieck Welle. Das kommt dabei raus,
wenn man einem Punkt dem "Kreis" entlang folgt.
Die Funktion, um aus X/Y wieder den Winkel zu kriegen, muss auch
angepasst werden.
Alles andere müsste ja gleich bleiben.
## Das Problem
Also habe ich das mal Ausprobiert (siehe Anhang). DFT, und wieder
umkehren. Ich dachte schon, es hätte Funktioniert. 1 beliebiger Wert
geht. 2 beliebige Werte gehen. 4 beliebige Werte gehen. Einfache Sachen
wie 5 4 3 4 5 4 3 4 gehen. Sachen wie 5 4 3 4 5 4 7 4 auch.
Aber bei so ziemlich allen anderen Situationen, liege ich mit Taxicab
doch etwas daneben... (euklidisch geht einwandfrei)
Woran könnte das liegen? Mache ich was falsch? Geht das einfach nicht?
Sind meine floats nicht genau genug?
## Wozu das ganze
Bei Taxicab habe ich nur Additionen, Multiplikationen, und Lineare
Funktionen. Es müsste eigentlich machbar sein, sich auszurechnen, wie
Gross ein integer sein muss, um alle Zustände abzubilden und die müssten
da dann ja alle genau da rein passen. Dann bräuchte ich keine Floats
mehr, und könnte die Daten verlustfrei übertragen.
Ich wollte das auf ein Bild anwenden. Die Idee war, statt wie bei
anderen Bildformaten nur Blöcke begrenzter Grösse so umzuwandeln, das
mit dem ganzen Bild zu machen, und zwar verlustfrei.
Und das wiederum wollte ich für das progressive Laden von Bildern in
einer Anwendung verwenden. Die dft Daten hätte ich deflate komprimiert
übertragen. Es hätte viele Bilder geben können, deren Daten ich
abwechselnd in kleinen Stückchen über die selbe Verbindung übertragen
hätte. Das hätte ich priorisiert, je nachdem ob die Bilder in der nähe
des Sichtbereichs sind oder nicht.
Dann würden die Bilder währen dem Laden immer schärfer, biss ich das
Original rekonstruiert hätte.
Bei Webseiten werden normalerwiese Tricks verwendet. z.B. ein "Blur
Hash" (also ein weiteres, kleines, unscharfes vorgeladenes Bild). Ok
z.B. JPEG kann progressives laden, aber mit den Blöcken sieht es nicht
so schön aus. Irgendwie eckig.
Mit dem Ansatz wäre das ohne Hacks gegangen...
(PS: Meine Anwendung ist keine Webseite)
Kontinuierliche und diskrete Fourier-Transformationen beruhen beide auf
Skalarprodukten. (gewöhnliches) Skalarprodukt eines Vektors mit sich
selbst ergibt - euklidische Norm zum Quadrat. D. h. in dem Fall stammt
die Metrik von einem Skalarprodukt. Die 1-Norm (|x|+|y|) kann man
dagegen nicht durch ein Skalarprodukt erhalten, denn die erfüllt die
sog. Parallelogrammidentität nicht.
"Die multipliziert man einfach, und man bekommt zurück, wie gut die
korrelieren." Naja, das ist halt nix anderes als ein Skalarprodukt zu
bilden ...
Ich habe leider gerade wenig Zeit, daher kann ich nicht auf deine
DFT-Fragestellung eingehen. Eine Sache fällt mir aber direkt auf bzw.
ein: Warum nutzt du keine DWT mit einem Haar-Wavelet? Wenn ich mich
nicht täusche, dann kriegst du da mehr oder minder das, was du willst.
Ich muss mir das mit der Parallelogrammidentität usw. mal genauer
anschauen, und das alles nochmal schritt für schritt Durchgehen.
Von DWT + Haar-Wavelet hatte ich bisher noch nichts gehört. Sieht
vielversprechend aus, ich muss mir mal anschauen, ob das für mein
Vorhaben geeignet ist.
Bezüglich Lambda-Kalkül... Naja, ich weiss ja nicht. Ich glaube das wäre
mir zu umständlich. Da probiere ich lieber einen theorem prover wie z.B.
Coq.
Nachdem ich diverses über Orthogonale Funktionen, Matrizen, etc. gelesen
habe, ist mir einiges klar geworden. Mit einer DFT Matrix, ist die
transponiert-konjugierte Matrix die Inverse der Matrix (zumindest, wenn
man sie richtig skaliert).
Eine Matrix mal ihre Inverse gibt eine Identity Matrix.
Die transponiert-konjugierte Matrix der Dreiecksfunktion war hingegen
nicht die Inverse der Matrix, also hat es sich nicht mehr aufgehoben.
Soweit ich das bisher ausprobiert habe, hat die Matrix aus der
Dreiecksfunktion aber in der Regel eine Inverse, kann also umgekehrt
werden. Ich hoffe mal dass sie immer eine hat, aber ich wüsste nicht,
warum das nicht der Fall sein sollte. Sieht so aus, als bestünde die
Inverse Matrix aus Rationalen Zahlen, aber ich muss noch genauer
nachsehen, welche Eigenschaften diese hat, und wie diese zustande kommt.
Ich bin auch noch auf die Hadamard Matrizen / Transformationen
gestossen. Die haben einige interessante Eigenschaften. Bestehen nur aus
1 und -1, sind ihre eigene Inverse (abgesehen von der Skalierung). Und
richtig sortiert hat es ähnliche Eigenschaften wie eine Fourier
Transform. Es gibt sogar auch eine FHT ähnlich wie bei der FFT.
Ich habe mit ein paar Python Skripten mal etwas ausprobiert, um zu
sehen, wie gut diese geeignet sind, um ein Bild mit zunehmender
Auflösung zu übertragen, und ob die Unschärfe dabei auch gut aussieht.
Ich habe einen FFT shift direkt auf die Matrizen angewendet, in der
Mitte ein Rechteck, Kreis, oder Rhombus ausgeschnitten, und dann mit der
Inversen Matrix Multipliziert.
Hadamard Pixelliert das Bild, und man sieht am Wenigsten mit der
Transformation.
Fourier sieht, wie zu erwarten, am besten aus.
Dreiecksfunktion hat ein paar Streifen drin, sieht aber eigentlich auch
sehr gut aus. Muss ich definitiv genauer anschauen, die kann ich sicher
so skalieren, dass ich nur Integer in der Matrize und der Inversen habe.
Im Anhang noch die Skripte und ein paar Testbilder zum Vergleich. Das
s<nummer> gibt die Anzahl Samples an, die genutzt wurden.
Noch ein weiterer Vergleich. Bei Interlacing für progressives Laden wird
ja jedes n-te Pixel verwendet. Also habe ich mal 32x32 Pixel vom Bild
oben genommen, und wieder auf 512 Pixel vergrössert. Beim vergrössern,
einmal nearest (Pixelliert), und einmal Kubisch.
Ich würde sagen, besser als Hadamard, aber weniger gut als die anderen
DFTs.
Daniel A. schrieb:> Sieht so aus, als bestünde die> Inverse Matrix aus Rationalen Zahlen, aber ich muss noch genauer> nachsehen, welche Eigenschaften diese hat, und wie diese zustande kommt.
Ich habe gerade mal nachgesehen, wie Gross die DFT Matrix Werte mit der
Dreiecksfunktion würden, wenn ich diese mit einem Faktor multipliziere,
so dass ich nur Integer habe. Die grösste Zahl einer N x N Matrize wäre
A003418(N), das least common multiple aller Zahlen bis und mit N.
Für das 512 x 512 Bild, wäre das
375026415669090809097743724029736852849746122969256702517192881539751776
000522246584191067268146335481145805434847443584445052937732940842524910
624915896569456364560836494555294310705271982600428121152801922326939969
80672000.
Der Ansatz ist also nicht besonders praktikabel.
Bei Hadamard wäre es zwar machbar, aber da das Ergebnis schlechter als
bei simplem Interlacing wäre, lohnt es sich nicht.
Eventuell könnte ich eine normale FFT nehmen, und am Ende die Differenz
zum Original berechnen, und wieder hinzufügen. Aber float Berechnungen
sind nicht besonders deterministisch. Selbst wenn 2 Platformen beide
IEEE754 floats verwenden, kann es geringe Unterschiede bei Berechnungen
geben, besonders auch bei Grafikkarten, das kann ich hier nicht
brauchen...
Edit: Ich habe gerade von der Number-theoretic transform (NTT) gelesen.
Die muss ich mal ausprobieren, vielleicht ist das ja, wonach ich gesucht
habe.
Die NTT war hierfür nicht zu gebrauchen.
Aber ich weiss jetzt, wie ich es wohl am besten umsetze. Ich nehme eine
gewöhnliche DFT, aber verwende Fixed Point statt Floating Point für die
Berechnungen. Damit habe ich die Genauigkeit bei jedem Schritt ja genau
im griff, und müsste die so wählen können, dass am Ende alles wieder
exakt passt. Unterschiede zwischen Platformen gibt es auch keine
Relevanten.
Manchmal sind die einfachsten & offensichtlichsten Lösungen die
besten...
Hi,
>>>> Damit habe ich die Genauigkeit bei jedem Schritt ja genau
im griff,
Ja genau, die FFTs rechnest Du mit integer und führst eine Skalierung
mit. Bei einer 512er FFT hast Du log2(512)=9 stages, jedesmal kuckst Du
auf den Wertebereich und skalierst ggf. runter. Modernere Proz.
benötigen für 32Bit float aber genauso lange wie für 32 Bit integer, die
Zeite wo man mit integer sparen konnte sind imho vorbei.
Die Hadamard Transformation ist super, da gibts noch viel zu entdecken:
Beitrag "Hadamard Transformation"
Cheers
Detlef
Announcement: there is an English version of this forum on 
Thread beobachten
Seitenaufteilung abschalten