Integer (1 Byte) Datentransformation DCT (FFT) gesucht

[Möbius]

Ja sicher gerne
Natürlich mit Google.
Dabei bin ich auf einige Bücher gestossen welche ich z.T. bestellt habe.
-> Besslich diskrete Orthogonaltransformationen.
-> K. R. Rao Fast Fourier Transform: Algorithms and Applications.

Das Problem bei den Büchern ist, dass sie sehr viel mathematischen Background enthalten aber wenn es um Integer Implementationen geht dann wird nur kurz von irgendeinem "Leverage Faktor" gesprochen. Zudem ist in den sog. "Butterfly" Diagrammen nicht ganz klar wie eine beliebige Datenmenge bearbeitet werden kann. Also auf eine Konstruktion eines Algorhitmuses in einer beliebigen Sprache gehen die Bücher nicht ein. Schon Pseudocode würde helfen.

Weitere Suche im Internet hat ein bisschen Code z.B. bei Rosetta Code zu Tage gefördert. Jedoch nur teilweise brauchbar. Auch in den Büchern steht, dass die DCT über den Umweg einer DFT gemacht werden kann. Aber eben auch wenn Integer ist diese komplexwertig und es ist mir nicht gelungen ohne den Imaginärteil eine Rücktransformation zu machen. Ist ja auch irgendwie klar. Der Realteil einer DFT stellt das Frequenzspektrum dar während der Imaginärteil die Phasenlagen des Signals darstellt.

Tja Deine Hilfestellung hat Hoffnungen geweckt, aber die Codes übersetzt in Delphi brauchen ca. 10 Minuten für 32 KiloByte .
Es ist eben auch nur eine DCT und keine FCT.
Die Bücher sagen aber eine solche soll möglich sein.

Was ich wirklich brauche ist ein Algorithmus der mir ein Signal (Daten beliebiger Grösse N -> also wenn möglich ohne Nullen die auf 2^n verfüllen) vom Zeitbereich in den Frequenzbereich transformiert und wieder zurück. Dies aber nur reelwertig und auf Integer (Bytes) basierend.

Ach ja und mit den Codes aus dem Netz stimmt etwas nicht. Weil sie scheinen kein erwartetes Spektrum darzustellen.

Um was geht es überhaupt:
Ich arbeite an einem Daten-Kompressionsalgorithmus. Der ist schon sehr weit fortgeschritten und sieht derzeit mit den Daten aus dem ->Calgary Corpus bzw. dem ->Canterbury Corpus oder auch dem ->Large Corpus sehr gut aus.
Jedoch wie üblich mit relativ unstrukturierten Daten mit hoher Entropie (also auf Deutsch gesagt eine Sauordnung), da schneidet er permanent mit rund 100% (und nur sehr wenig mehr bei moderat grossen Files) ab! Wohlgemerkt gemessen an RAD-Daten (randomisierten Files).
Die Sachlage ist klar, wenn ich das nur um ein paar % runterdrücken kann, dann habe ich einen Kompressor der sich selber komprimieren kann! Die Konsequenzen bei einer iterativen Anwendung dürften klar sein.
Somit dürfte schon klar sein, dass mir eine FFT sehr wenig nützt. Ob nun integer oder nicht. Der Frequenzanteil (reel) (bei meiner eigenen Float64 basierten FFT) sieht wir erwartet gut aus bei solchen Daten. Ich bin ja von Haus aus Elektroniker und Toningenieur (ist schon eine Weile her ). Aber eben solche RAD-Daten bezeichnet man im Audio-Jargon als statistisches weisses Rauschen. Und dieses Zeichnet sich aus durch sehr kleine Schwankungen der Amplituden (infinitesimal wohl gar keine) im Spektrum.

Und genau diese kleinen Schwankungen könnten dazu führen, dass mein Algorithmus die Daten besser verarbeiten kann.

Wie gesagt. Ist reine Theorie und Forschungsarbeit.

Ach ja, die DCT aus dem Netz von Deinem Tipp rechnet nicht nur ewig (eine FCT wäre natürlich besser), Sie zeigt auch ein Spektrum von sehr stark schwankenden Amplituden der Frequenanteile - Da kann etwas nicht stimmen. Die müssten eigentlich näher beisamen liegen.
Ganz klar ist, dass am Anfang des Spektrums sehr hohe Amplituden auftreten wenn ich die Daten als rein positive Werte (Bytes) einspeise. Dieser DC-Anteil schlägt hier natürlich zu Buche. Wenn ich die Daten als Int8 einspeise sieht das schon besser aus, die realtiv hohen Werte am Anfang der Sequenz dürften Verzerrungen sein, die sich ergeben weil ich kein kontinuierliches Signal einspeise. Damit liesse sich leben wenn die Rücktransformation diese Verzerrungen richtig heraus rechnet.

So suche ich also weiter...

Hoffe Dir aber den Werdegang meiner Idee und Suche etwas näher gebracht zu haben.

[TiGü]

Aber es ist doch auch möglich, dass du dich beim Übersetzen vertan hast?!

Welches Codebeispiel hast du denn nach Delphi übersetzt?
Das Java- oder das C-Beispiel?!

[Möbius]

Ja könnte natürlich auch sein.

Hier die Übersetzungen (non integer):

Delphi-Quellcode:

class procedure TCompressOSCT.DCT(const Input: TFloat64Array; out Output: TFloat64Array);  //1 double[] DCT (double[] g) { // forward DCT on signal g
var
  M, mCnt, uCnt: Int64;
  s, cm, sums, Phi: Float64;
begin
  M := Length(Input); //2 int M = g.length;
  s := sqrt(2.0 / M); //3 double s = Math.sqrt(2.0 / M); // common scale factor
  SetLength(Output, M); //4 double[] G = new double[M];
  for mCnt := 0 to High(Input) do //5 for (int m = 0; m < M; m++) {
  begin
    cm := 1; // 6 double cm = 1.0;
    if mCnt = 0 then // 7 if (m == 0)
    begin
      cm := 1 / sqrt(2); // 8 cm = 1.0 / Math.sqrt(2);
    end;
    sums := 0; // 9 double sum = 0;
    for uCnt := 0 to High(Input) do // 10 for (int u = 0; u < M; u++) {
    begin
      Phi := Pi * mCnt * (2 * uCnt + 1) / (2 * M); //11 double Phi = Math.PI * m * (2 * u + 1) / (2 * M);
      sums := sums + (Input[uCnt] * cm * cos(Phi)); // 12 sum += g[u] * cm * Math.cos(Phi); }
    end;
    Output[mCnt] := s * sums; // 14 G[m] = s * sum; }
  end;
end;

class procedure TCompressOSCT.InvDCT(const Input: TFloat64Array; out Output: TFloat64Array);  // 20 double[] iDCT (double[] G) { // inverse DCT on spectrum G
var
  M, mCnt, uCnt: Int64;
  s, cm, sums, Phi: Float64;
begin
  M := Length(Input); // 21 int M = G.length;
  s := sqrt(2.0 / M); // 22 double s = Math.sqrt(2.0 / M); //common scale factor
  SetLength(Output, M); // 23 double[] g = new double[M];
  for uCnt := 0 to High(Input) do // 24 for (int u = 0; u < M; u++) {
  begin
    sums := 0; // 25 double sum = 0;
    for mCnt := 0 to High(Input) do //26 for (int m = 0; m < M; m++) {
    begin
      cm := 1; // 27 double cm = 1.0;
      if mCnt = 0 then // 28 if (m == 0)
      begin
        cm := 1 / sqrt(2); // 29 cm = 1.0 / Math.sqrt(2);
      end;
      Phi := Pi * mCnt * (2 * uCnt + 1) / (2 * M); // 30 double Phi = Math.PI * m * (2 * u + 1) / (2 * M);
      sums := sums + (Input[mCnt] * cm * cos(Phi)); // 31 sum += G[m] * cm * Math.cos(Phi); 32 }
    end;
    Output[uCnt] := s * sums; // 33 g[u] = s * sum; 34 }
  end;
end;

[freimatz]

"0 to High(Input)" - müsste das nicht -1 sein? Passt vermutlich. "Low(Input) to High(Input)" wäre schöner.

[TiGü]

Warum zwei geschachtelte Schleifen?
In der Wikipediadefintion von DCT-I bis DCT-IV sehe ich immer nur ein Summenzeichen?

[Blup]

Ich habe mal versucht zu optimieren.
Unnötige doppelte Operationen mit Hilfe von Zwischenvariablen aus Schleifen ziehen.
Multiplikation durch Addition ersetzen, wenn das möglich ist.
Ob das eine merkliche Verbesserung der Laufzeit bringt, müsste man in der Praxis testen.

Delphi-Quellcode:

class procedure TCompressOSCT.DCT(const Input: TFloat64Array; out Output: TFloat64Array);
var
  M, mCnt, uCnt: Int64;
  s, sums, Phi, Pi2M, Pi2MmCnt: Float64;
begin
  M := Length(Input);
  SetLength(Output, M);
  if M > 0 then
  begin
    s := sqrt(2.0 / M);
    Pi2M := Pi / (2 * M);
    Pi2MmCnt := 0;
    for mCnt := 0 to M - 1 do
    begin
      sums := 0;
      Phi  := Pi2MmCnt;
      for uCnt := 0 to M - 1 do
      begin
        sums := sums + (Input[uCnt] * cos(Phi));
        Phi := Phi + Pi2MmCnt + Pi2MmCnt;
      end;
      Output[mCnt] := s * sums;
      Pi2MmCnt := Pi2MmCnt + Pi2M;
    end;
    Output[0] := Output[0] / sqrt(2);
  end;
end;

Warum wird eigentlich ausgerechnet nur Output[0] durch sqrt(2) dividiert?

[Möbius]

@Freimatz
Nein das ist schon richtig so, Dynamische Arrays sind bei Delphi immer 0 basiert. D.h. Low(Array) und 0 sind äquivalent.

Vielen Dank für's optimieren, aber das Problem sind effekvtiv immer noch die 2 geschachtelten Schleifen. Ich rauch es aber sowieso Byte(Integer).

Eben wegen dieser "Sachlage". Ich arbeite schon einige Zeit an einem völlig neuartigen Kompressor und der hat mittlerweile echt gute Resultate. Bei Calgary und Canterbury Corpus kann er sicher vorne mitreden.
Aber es fehlt halt noch das i-Tüpfelchen.
Das Argument, dass man eine Nachricht N mit n Buchstaben nicht kürzer als N codieren kann, ohne dass man "Opfer" auf der anderen längeren Seite bringen muss, will mir nicht so recht in den Kopf.
Z.B. kann man ein Kartenspiel so lange perfekt mischen bis es sortiert ist. Dann braucht man bloss die Zahl der Mischvorgänge zu übermitteln um dies wieder rückgängig zu machen. Zauberkünstler nutzen diesen Trick übrigens für manche Kartenkunststücke. Man muss freilich die Kunst beherrschen ein Karttendeck wiederholt exakt in der mitte zu teilen und perfekt Karte links auf Karte rechts jeweils mischen können. Ein Deck mit 52 Karten ist verblüffender Weise nach 5 Durchgängen wieder sortiert.
Okay in der Praxis sind hier normalerweise viele Permutationen nötig.

Die Idee letztlich mit der FCT(Fast Cosinus Trandorm) jedenfalls könnte sich imho für völlig zufällige Daten eignen. Da rein zufällige Daten im Prinzip dem weissen Rauschen gleichkommen, müsste doch eigentlich eine Tranformation vom Zeitbereich in den Frequenzbereich ein Spektrum mit sehr kleinen Differenzen in den Amplituden der Spektralanteile liefern.
Das könnte schon ein interessanter input sein für irgended einen Codierer.

[Michael II]

Zitat von Möbius:

Jedoch wie üblich mit relativ unstrukturierten Daten mit hoher Entropie (also auf Deutsch gesagt eine Sauordnung), da schneidet er permanent mit rund 100% (und nur sehr wenig mehr bei moderat grossen Files) ab! Wohlgemerkt gemessen an RAD-Daten (randomisierten Files).
Die Sachlage ist klar, wenn ich das nur um ein paar % runterdrücken kann, dann habe ich einen Kompressor der sich selber komprimieren kann!

Mir ist diese "Sachlage" alles andere als klar. Wenn du mal kurz Zeit hast, dann wäre es cool, wenn du ein paar Zeilen mehr dazu schreiben würdest.

Das liest sich für mich als würdest du völlig zufällige Bitfolgen komprimieren wollen. Und das klappt natürlich nicht. Wenn du die Menge D aller möglichen Wörter bis Länge n Bit deinem Kompressor füttern willst, dann hast du in D 2^n Wörter der Länge n, 2^n-1 der Länge n-1,... 2^1 Wörter der Länge 1.
Deine Kompression k muss zwei voneinander verschiedenen Wörtern w1 und w2 aus D voneinander verschiedene Werte k(w1) und k(w2) zuordnen (k injektiv); sonst könntest du nicht dekomprimieren. Wenn W die Menge aller Werte k(wi), für alle wi aus D ist, dann gilt also: W und D haben gleich viele Elemente.
Es gibt natürlich zig verschiedene solche Funktionen k; eine davon (die einfachste) ist k = id, also k(w) = w.
Oder anders geschrieben: Bei völlig zufälligen Zeichenfolgen rechnet dein Kompressor am besten gar nichts und gibt w als Wert aus.

Wahrscheinlich denkst du in eine andere Richtung (?)...